The most difficult aspect of high-speed network development is a management design. We propose to use existing Automatic Control approach to describe, analyze and design the network management strategy and traffic control mechanisms of different levels. This leads us to the discussion about what does "efficient control" mean? What are the adequate patterns of object under control and of input forces for different levels of management? We formulate some of this aspects taking into account the real traffic and service parameters.
Key words: traffic management, optimization procedure, traffic source model, automatic control.
Building of new classes of technical objects based upon emerging technologies always causes the interest in process control systems for such objects. So, the creating of artificial space satellites in early sixties has stimulated the development of optimal control algorithms. In seventies the development of complicated dynamic systems working under the effect of random force caused the emerging of statistically optimal and robust control algorithms. Today the most difficult aspect of high-speed network development is a management design. This paper presents the results of current network traffic management research holding within RUSnet project [1]. Theconcept of the project, based on the Intelligent Information Infrastructure model (III-model) and Telenetics paradigm, has been offered by the Saint-Petersburg State Technical University and Cybernetics Institute research group [2], [3]. One of the project's research areas is dedicated to high-speed network traffic management based on optimization and adaptation procedures.
A number of different control mechanisms have been proposed in the literature. It should be noted, mostly the verbal definitions of control functions are given without numerical characteristics of management efficiency. For comparative analysis of these schemes a formal theoretical approach is needed. With few exceptions, the wide range of control mechanisms described earlier may be classified in terms of automatic control theory. That is why we propose to use existing automatic control and operational research approaches to analyze and design the traffic management control mechanisms.
The paper is organized as follows. We first describe the main aspects of automatic control methodology, next we propose the Petri net model of individual traffic source based on the ATM forum specification. Using a continuous-time buffer model, we present a variant of a control flow for a cell discarding algorithm and show how this scheme satisfies some conventional QoS requirements. This model is used to show a basic idea of our approach.
Our proposed approach represents traffic management as a hierarchical system with different levels of control function and a formal definition of each management level. For many traffic management control functions, such a hierarchical presentation is natural and even unavoidable. For example, a complete traffic management strategy should include several congestion control and avoidance schemes that work at different protocol levels, and that can handle congestion of varying duration [8]. From the automatic control point of view, it means that there is a set of automatic control systems which have different control rates and respond to the input force changes in appropriate time intervals (short or long). Despite the differences in management goals and time scale of levels, we propose to give the formal definition of every management level and to formalize the task of control synthesis based on:
This leads us to the discussion: what does efficient management mean? What are the numerical metrics of management efficiency in general and of each control mechanism in particular? Below, without loss of generality, we discuss our considerations of choosing models and efficiency criteria oriented to high-speed network with cell-based traffic (ATM-technology).
A primary role of traffic management in ATM networks is to protect the network and end-system from congestion in order to achieve network performance objectives and use network resources efficiently. The ATM forum has defined a set of main traffic management functions that may be used in appropriate combinations depending on the service category [7].
Note that the input variables for these functions can be divided into individual source traffic (for example, for Usage Parameter Control) and total network workload (for example, for ABR Flow Control). In order to take into account data stream characteristics while synthesizing the control law, we have to develop models of individual traffic source (IND-model) as well as multiplexed traffic source (MIX-model). The robust model has to be built basing upon actual traffic parameters. In accordance with ATM forum specifications [7], each actual connection is specified by traffic contract which includes the negotiated values of traffic (Traffic) and Quality of Service (QoS) parameters, as shown in the Table 1.
| Constant Bit Rate (CBR) | Variable Bit Rate (VBR) | Available Bit Rate (ABR) | Unspecified Bit Rate (UBR) | ||||
| Traffic | QoS | Traffic | QoS | Traffic | QoS | Traffic | QoS |
| PCR | CLR CDV CTD |
PCR SCR MBS |
CLR CDV CTD |
PCR MCR |
CLR - - |
PCR | - |
|
PCR- Peak Cell Rate
|
That is why the ability to handlie those parameters to create different types of control schemes is very important. But the traffic parameters above describe the worst case restrictions of traffic contract and are not sufficient to define the traffic source behavior as a function of time and to synthesize an optimal control system. The additional information is needed to describe the stochastic nature and time dependency of a cell flow for the connection. To create an automatic control first of all the adequate model of the traffic source is needed.
The individual source traffic can be defined as a discrete parameter stochastic process {Xn} representing the spacing of cell flow. The process parameters have to satisfy the restrictions derived from the traffic parameters (Table 1): Mean {Xn}=1/SCR, Xn>=1/PCR, maximum length of continuous sequence of minimal values (Xn=1/PCR) must be not greater then MBS. The analytical expression of a such cell flow is absent.
As a first step of developing unified formal IND-model we propose a new Petri net based model of individual traffic source, which takes into account the real traffic parameters (Table 1) and may be used for both simulating and some analytical investigations. Petri net is a well-known formal tool for modeling the behavior of discrete systems and have an analytical and graph interpretation [4], [9].
The model is defined as Petri net (Fig.1) with time parameter T0.The arcs (s1,t1) and (t1,s2) of
the model both have weight u, and the arcs (s2,t2)
and (t2,s1) both have weight v. Hence,
whenever t1 fires, u tokens move from s1 to s2, and whenever t2 fires, v tokens
move from s2 to s1. The initial marking M0
of Petri net is
M0=(M(p1)=1, M(s1)=z>=u+v-1, M(s2)=0, M(p2)=0)
The values M(s1), u, v and T0 are the functions of service category and traffic parameters.
The transition t0 may be considered as an internal clock of the source and has a finite firing time T0. The interval between two consecutive occurrences of t0 then is taken to be a time slot of internal clock.
Transitions t1 and t2 fire instantly after enabling. As t1 and t2 may fire only alternately with t0 if M(p1)+M(p2)=1 the firing of t1 may be viewed as emulating the sending of a cell whereas the firing of t2 emulates the time slots during which no sending takes place.
It may be shown [5] that model regulates, for reproducing processes Pr, the firing count ratio between t1 and t2 as h1(Pr)/h2(Pr)=v/u, where hi(Pr) is the component of reproduction vector h(Pr) associated with the transition ti. The Petri net model is obviously live if z=M(s1)>=u+v- 1. The actual number of tokens z which constitutes a live marking of model determines how rigorously the firing count ratio h1(Pr)/h2(Pr)=v/u is enforced. This may be illustrated by mentally executing the Petri net with stepwise increasing the initial number of tokens in place s1. We may observe that we introduce an increasing degree of freedom as to the choice of either firing t1 or t2 under a particular token distribution. A quantitative measure for this phenomenon is a weighted synchronic distance formally defined in [5]. The synchronic distance reflects the degree to which the two transitions may deviate from the mean firing count ratio as specified by the respective components of reproduction vector. It may be shown [5] that for Petri net of Fig.1 and a live marking with M(s1)=z-q, M(s2)=q and M(p1)+M(p2)=1, the synchronic distance between t1 and t2 is given as
syn(t1,t2)=^(z-q)/d^+^q/d^,
where ^x^ denotes the greatest integer <=x and d is the greatest common divisor of h1(Pr) and h2(Pr). The synchronic distance fits very well to be a measures of maximum burst size. The different classes of traffic source may be efficiently modeled by using the proposed model, as shown below.
CASE 1. CBR class traffic source model.
The relations between the Petri net characteristics and traffic source parameters are as follows: M(s1)=1, u=v=1, T0=1/(2*PCR).
Then the firing sequence of transition t1will exactly correspond to the CBR traffic with PCR = 1/2T0.
CASE 2. VBR class traffic source model.
The relations between the Petri net characteristics and traffic source parameters are as
follows:
M(s1)=MBS*(PCR-SCR)/w, where w is the greatest common
divisor of SCR and (PCR-SCR),
u=M(s1)/MBS, v=M(s1)*SCR/[MBS*(PCR-SCR)],
T0=1/PCR.
Then the firing sequence of transition t1will exactly correspond to the VBR traffic with PCR=1/T0, SCR=1/T0*v/(u+v), MBS=M(S1)/u=Syn(t1,t2)/u, BT(Burst Tolerance)=T0*[(Syn(t1,t2)-u)/v].
For example, let the traffic parameters of VBR source are as follow: PCR, SCR=PCR/3, MBS=4. From the equations above we have:
M(s1)=8, v=1, u=2, T0=1/PCR.
The possible firing sequences which starting with initial marking Mo and time diagram of cell sending are shown in the Fig.2,
| 1 0 | ti> | 0 1 |
denotes the change of the marking M(s1)=1, M(s2)=0 into M(s1)=0 and M(s2)=1 due to the firing of the transition ti. The above traffic parameters describe the worst case restrictions of traffic contract. In order to use these models in statistical modeling the additional information is needed to describe the stochastic nature of cell sending.
A number of additional parameters may be used. We propose a simple approach based on using of one parameter - the PCR probability - l. This parameter defines the probability of next cell sending with peak (minimal) emission interval (1/PCR) if it agrees with PCR, SCR and MBS (BT). In terms of Petri net l may be called as probability of repeated firing of transition t1.
The range of l is from 0 to 1. In the case of l = 1 maximal burst traffic (in accordance with traffic contract) is simulated. In the case of l = 0 burst takes no place in traffic. It permits to create a model of cell flow with any dispersion allowed by traffic contract. So, the VBR traffic source model for simulating is defined by the parameters PCR, SCR, MBS and l.
The same Petri net may be used to model a UBR class traffic source with the PCR=1/T0.
CASE 3. ABR class traffic source model.
To model the ABR class traffic source the above Petri net model is suitable with the extension as follows: the firing time T0 of transition t0 is not constant but is enforced by ABR Congestion control scheme feedback as it shown in the time diagram Fig.3. The range of T0 is from 1/PCR to 1/MCR.
To create a complete source model is an important task. It is necessary to study different application traffic to determine their consistent time and distribution characteristics as well as to evaluate the adequacy IND-model as a Marcovian realization.
Despite all its outstanding capabilities, ATM technology has some internal features that can cause traffic related problems. According to [8], even in lightly loaded cell- switching networks it is not unusual to observe cell blocking due to network congestion. The loss of a single cell in an ATM transmission leads to higher-level packet retransmission and an exponential increase in traffic through a switch. A congestion collapse is of particular concern when ATM switch relay large amounts of bursty data. In order to efficiently manage the network resources an additional research is needed.
Measurements of LAN and VBR video traffic show that data flow in packet and cell based networks differs fundamentally from conventional telephone traffic, and may be even fractal in nature [6]. In this case some conventional QoS criteria associated with actual bursty traffic may differ drastically from that predicted by conventional models. It should be taken into account while creating the MIX-model of cell flow. Below we show that the actual nature of packet traffic has serious implications for network engineering and management approach. Consider the cell discarding algorithm.
4.1 Input variable model. We will use a function of time F(t) as a model of input packet traffic. Let q=1/PCR is the elementare time unit. The function can be observed every q time unit during interval T . If the function is well-known the control decision is possible in off-line mode. Let F(t) is a stochastic process and we know only its autocorrelation function. Bellow this function will be used for optimal control synthesis.
According to [6] at every time scale autocorrelation function of traffic in cell-based network decays much more slow then Poisson-like law predict. Let us consider two variants of input function F(t). The first variant indicates the presence of long-range dependence and given by autocorrelation function
where 0<g<1 parameter of regularization and 0<b<1.
A long-range dependence may cause heavy losses and as a result long decays during bursts.
The second model defines the Poisson-like process with an exponential curve of autocorrelation function
In the frequency domain traffic, models can be characterized by a spectral density Af(w).
4.2 The model of object under control. The common requirement for mathematical model is its adequatennes to the real system behavior. To accommodate bursty traffic, several approaches are evolving: dynamic buffering mechanism with per-VC queuing, intelligently organized packet/cell discard algorithms, and ABR algorithm wich based on Resource Management (RM) cells. This cells indicate the presence or absence of congestion and force and systems to change the amount of data being sent into network.
Consider the cell discarding algorithm in the buffer of the cell switch. The buffer provides additional resource for a limited time interval T. That resource is equivalent to temporarity extending channel bandwidth to smooth the burstness of traffic. Cells from virtual circuits (VC) are scheduled in statistical multiplexing order. If any one VC sends a large burst of data then the service rate at the buffers of all other VC drops until the burst has been served. We will call the buffer for VC as a virtual buffer (VB). To protect the VB from congestion, a cell discarding scheme may be used.
The aims of the control are to maintain the number of cells in the VB queue at a desired setpoint, and protect buffer from overflow. Since the data flow has burst components, a border of the buffer's filling will oscillate around the setpoint value.
The choosing of the setpoint (at the set up phase of connection) reflects a tradeoff between mean cell delay, cell loss and bandwidth loss. Let: S(t) - current buffer's filling (fig.4), <S(t)> - mean value of S(t), <F(t)> - mean value of F(t).
If a control action is done once every q time units we can make the fluid approximation of data flow, ignore cells boundaries and define a speed of the buffer filling dS/dt by
where C is the mean service rate and u(t) - control rate for discarding cells. In this equation S(t) can be positive as well as negative. Negative values characterize a degree of not using of available VC bandwidth. Denote the value of a variable x(t) by
and a variable f(t) by
In case of mean value <F(t)> equal to service rate C, we can write the buffer equation in derivations
4.3 Formal definition of efficiency criterion. The efficiency criteria have to reflect the aim of control and take into account the values of QoS parameters needed by the particular traffic contract (see Table 1). In addition while choosing the criterion the designers have to minimize the complexity of the control value computation. In our case the functional
The requirements to minimization of CLR value can be expressed by means of integral limitation <u²> <=Nu and efficiency criterion expressed as weighted sum
where m² - weight coefficient. Its value depends on value of Nu.
The first item in J enforse the minimizing of Cell Delay Variency(CDV) the second item enforce the minimizing of Cell Loss Ratio (CLR). The choosing the value of Nn reflectes the relative significance of CLR and CTD regulating.
4.4 The calculating of optimal regulator characteristics. The depth of criterion minimum that can be reached depends on information of input data streams. In order to compute the minimum of J it is possible to use spectral density Af(w), that is Fourier transform of autocorrelation function Kf(t).
In case of Kf(t) = (g+t)-b the Af(w) is a generalized function, and value of <u²> could be calculated
as well as J
This value of J is achieved by using a linear feedback law
Note that if Af(w) satisfies a Poisson-like distribution with parameter n=1, then J = m/(b+m). Figures 5-7 show, in case of exponential distribution, the intensity of optimal control is lower than in case of actual burst traffic. Note that the decreasing regularization parameter g of the autocorrelation function causes the rising of control intensity. Figures 5 and 6 show that not many frequency constituents of spectral density of input traffic are equally important for the system being controlled. It is enough to satisfy the conformity between the theoretical and real spectral densities in limited bandwidth only, where the module of frequency characteristic of loopbacked system can be neglected. Therefore it is possible to use Poisson-like distribution to define traffic flow characteristics for cell discarding algorithms. Note, the received value of control action u(t) can be used in discarding cells algorithm as well as to change the source intensity in ABR mode. This circumstance has to be taken under consideration to synthesize the controls needed.
Figure 5.
Figure 6.
Figure 7.