Input Set Decomposition and Open-Loop Control in Telecommunications Networks

Proceeding of the American Control Conference, Seattle<= /st1:City>, Washington. June 1995.

= &nb= sp; Input Set Decomposition and Open-Loop Control in Telecommunications Networks=

= &nb= sp; Ziny= Flikop, NYNEX Science and Technology, Inc., 500 Westchester Ave= ., White Plains, NY, 100604.

Abstract<= o:p>

This article analyzes pro= blems of development of open-loop control systems for telecommunications networks and discusses one of several possible algorithms for decomposition of the input= set into closed convex subsets (if such decomposition is possible). This decomposition allows for creat= ion of a control rules: “Control should be the same as long as an input vect= or belongs to the subset that corresponds to a control rule. If the input vector leaves this subset then a new subset, to which the input vector belongs, must be d= efined and control should be changed to the control assassinated with a new subset= . This article presents examples of input subsets. The proposed decomposition approach= is an illustration of the methodology the scrapping in [1].

Introduction<= o:p>

In this article we consider open-lo= op control as control that is based only on information about the status of the controlled system input. As an input we consider a combination of values off traffic entering a network from different service subscribers. Each combina= tion is a vector in the input set. As a controlled parameter (output) we conside= r an average delay T that traffic undergoes in the network. Control can be executed via changes in the routin= g of traffic flow in the network. The task of the control system is to contain t= he controlled parameter below a tolerated limit _{upon fluctuation of the input vector (input traffic) into=
the
input set. A major problem in the development of open-loop control systems =
is
the creation of “input is…, then control is…” rules
that provide solutions to every input vector. If we try to define a separate
control for each possible input vector, then the size of the control rule t=
able
becomes too large. However we can reduce this table if we decompose at whole
input set into subsets and, for each subset, find a corresponding control r=
ule
[1]. Moreover, we can avoid analysis of all possible control vectors via a
properly organized routing optimization procedure. The development of contr=
ol
roles requires the availability of a network input - output transformation =
model.}

Network Model

The proposed approach is currently under investigation far possible use in the development of an on-= line performances oriented open-loop control system for highly heterogeneous fra= me relay and ATM networks. The open-loop approach was chosen to decrease the reaction time of the control system to a minimum. A network model is created and traffic routing is optimized in correspondence with [2]. The models of frame relay [3] and ATM [4] switches are the results of Ph.D. studies. Howe= ver, for demonstration we use a very simple example of the network from [5] (Fig= ure 1). To save space we don’t provide network and traffic parameters use= d in the example. These parameters can be found in either [1] or [5]. Although t= he decomposition and open-loop control studies [1] were made on a network with 30 source-des= tination couples, that is, into a 30-dimensional input set, illustrate our analysis = with a three dimensional input set. This allows us to better visualize the resul= ts of the decomposition and provide valuable information about the shape properties of the subsets. The three dimensional input set is created by varying traffic values between nodes C and A, B. and E and D and E. Traffic= for the rest of the network is fixed. Network control is executed via routing tables created for each network node.

If during routing optimiz= ation we find control for which network provides _{, then it m=
eans
the volume of input traffic can be steadily increased until T reaches its limit i.e., it is po=
ssible
to define for this control an input subset in which an input vector can
fluctuate, and condition _{will be satisfied. If we can find another control that
provides _{for an input
vector that does not belong to the already-defined input subset, then the i=
nput
set can be decomposed on a set of input subsets.}}}

Input Set Decomposition

We are proposing a decomp= osition procedure in which we assume that the inputs subsets are convex and the sub= sets are defined when their boundary sets are defined. This procedure is as foll= ows: The center of the first (initial) subset is determined via a randomly selec= ted input vector. We denote that input vector as_{. The routing (control) that provides the best possible v=
alue
of the controlled parameter T f=
or _{is defined =
via
optimization [2]. If the control that provides _{for this in=
put
vector is found, then we can define the input boundary points that correspo=
nd}}}

to_{. To do so we generate a test vector that originates at t=
he
point representing the input vector and expends from it to the boundary set=
in
a random direction. The bound=
ary
input point is defined via one – dimensional optimization executed al=
ong
this direction to minimize |_{|. Then another test vector and direction are selected an=
other
boundary point is defined.}}

After a number of boundar= y points are found, we can try to represent a created boundary set via some polynomi= al. (It is desirable for open-loop control to describe a boundary set analytica= lly). This can be down by using either the “Fit” function of [6] or s= ome other fitting algorithm. We use the optimization algorithm proposed in [2].= The result of a fitting provides us with information about the polynomial and t= he value of the least squares error corresponding to that polynomial. Using th= is polynomial allows us to speed up our process, since now we can continue selection of testing points that are very close to the boundary set. These points are ra= ndomly selected one-by-one and inch point is considered as the origin of the test vector. Additional boundary pints are defined via procedure similar to that describe it above. Each additional boundary point is used to correct the po= lynomial and recalculate the value of a least squares error define iper point. When this error is stabilized, we terminate the procedure and consid= er the polynomial found.

Figure 2 presents a bound= ary set in which no constraints are applied to network performance. Figure 3 repres= ents a set which is defined so that the load of no network circuit can exceed 66= %. For illustration we note that that boundary set in Figure 3 is represented = by _{. Received
data show that subsets are convex.
Figure 4 presents an example of input sets decomposition into two
three-dimensional sets.}

In our studies we were able to defi= ne surfaces analytically for input sets with up two 30 dimensions. The describe algorithm can be modif= ied to also allow decomposition of an output set. Moreover, input set and output s= et decomposition can be combined, thus increasing control system capabilities<= /p>

Open-Loop control

After decomposition we can employ a= variety of procedures for on-line open-loop control. One is to monitor the input ve= ctor and perform verification for conditions similar to: _.

If the condition associated with the subset is satisfied and the control role associated with this subset is currently active, than we consider that the input vector belongs to the sub= set and continued current control. If at some moment monitoring detects a viola= tion of this condition, then the subsets closest to the input vector are tested.= This process continues until a suitable subset is found and its corresponding ru= le is fired.

References

= 1.&n= bsp; Z. Flikop, “Some Problems with the Design of = Self-Learning Management Systems”, Proceedings of NAFIPS’92 Conference, NASA Conference publications 10112, Vol. 11, 1992.

= 2.&n= bsp; Z. Flikop, “Routing Optimization in Packet Switching Networks”, European Journal of Operational Research, 19, pp. 262-267, 1985.

= 3.&n= bsp; Po Liang, Ph.D. thesis: “Switching Network Analysis Based on the First Three Moments of the I= nter-arrival Time and Service Time” Polytechnic university, 1994.

= 4.&n= bsp; Derchian Tsaih, Ph.D. thesis: “Source Approximation Method for Modeling A.T. M. Netwo= rks”, Polytechnic university, 1995.

= 5.&n= bsp; A.S. Tanenbaum, “Computer networks”, Second edition, <= span style=3D'mso-spacerun:yes'> Prentice Hall<= /st1:City>, NJ, 1988.

= 6.&n= bsp; S. Wo= lfram, Mathematica, Second Edition, Addison-Wasley, Redwood City, CA, 1991.