Figure 1.
V. Zaborovski <vlad@stu.neva.ru>
State Technical University of Saint Petersburg
Russia
Y. Podgurski <podg@stu.neva.ru>
Institute of Robotics and Technical Cybernetics
Russia
S. Yegorov <ye@stu.neva.ru>
State Technical University of Saint Petersburg
Russia
Y. Shemanin <yuri@neva.ru>
Institute of Robotics and Technical Cybernetics
Russia
Keywords: traffic management, optimization procedure, traffic source model, automatic control.
Building of new classes of technical objects based upon emerging technologies always causes interest in process control systems for such objects. So, the creation of artificial space satellites in the early sixties has stimulated the development of optimal control algorithms. In the seventies, the development of complicated dynamic systems working under the effect of random force caused the emergence of statistically optimal and robust control algorithms. Today the most difficult aspect of high-speed network development is management design. This paper presents the results of current network traffic management research within the RUSnet project [1]. The concept of the project, based on the Intelligent Information Infrastructure model (III-model) and Telenetics paradigm, is 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, however, that mostly 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 traffic management control mechanisms.
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, there is a set of automatic control systems that 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 we discuss our considerations of choosing models and efficiency criteria oriented to a 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 an individual traffic source (IND model) as well as a multiplexed traffic source (MIX model). The robust model has to be built based on actual traffic parameters. In accordance with ATM forum specifications [7], each actual connection is specified by a traffic contract that includes the negotiated values of traffic (Traffic) and Quality of Service (QoS) parameters, as shown in 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
SCR- Sustainable Cell Rate
MCR- Minimum Cell Rate
MBS- Maximum Burst Size
CLR- Cell Loss Ratio
CDV- Cell Delay Variation
CTD- Cell Transfer Delay
That is why the ability to handle 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. 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 traffic source 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 than MBS. The analytical expression of a such cell flow is absent.
As a first step of developing a 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. The Petri net is a well-known formal tool for modeling the behavior of discrete systems and has an analytical and graph interpretation [4], [9].
The model is defined as a Petri net (figure 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 the
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.
Figure 1.
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 the 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 the 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 that constitutes a live marking of the 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 increases in the initial number of tokens in place s1. We may observe that we introduce an increasing degree of freedom as to the choice of firing either 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 the reproduction vector. It may be shown [5] that for the Petri net of figure 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 as a measure 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 be as follows: 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 start with initial marking M0 and time diagram of cell sending are shown in figure 2,
Figure 2.
where
| 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 the traffic contract. In order to use these models in statistical modeling, 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 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 the Petri net, l may be called the 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 the traffic contract) is simulated. In the case of l = 0, no burst traffic takes place. This permits creation of a model of cell flow with any dispersion allowed by the 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 an ABR class traffic source with 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 following extension: The firing time T0 of transition t0 is not constant but is enforced by ABR congestion control scheme feedback as shown in the time diagram, figure 3. The range of T0 is from 1/PCR to 1/MCR.
Figure 3.
Creating a complete source model is an important task. It is necessary to study different application traffic models to determine their consistent time and distribution characteristics as well as to evaluate the adequacy of the 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 an ATM switch relays large amounts of bursty data. To manage network resources efficiently, 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 even be 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. This 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.
We will use a function of time F(t) as a model of input packet traffic. Let q=1/PCR be the elementary 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) be a stochastic process, and we know only its autocorrelation function. Below this function will be used for optimal control synthesis.
According to [6], at every time scale, the autocorrelation function of traffic in cell-based network decays much more slowly then Poisson-like law predicts. Let us consider two variants of input function F(t). The first variant indicates the presence of long-range dependence and is given by autocorrelation function
Kf(t) = (g+t)-b,
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
Kp(t) = ne-bt.
In frequency domain traffic, models can be characterized by spectral density Af(w).
The common requirement for a mathematical model is its similarity to real system behavior. To accommodate bursty traffic, several approaches are evolving: dynamic buffering mechanism with per-VC queuing, intelligently organized packet/cell discarding algorithms, and ABR algorithms based on resource management (RM) cells. These cells indicate the presence or absence of congestion and force systems to change the amount of data being sent into the network.
Consider the cell discarding algorithm in the buffer of the cell switch. The buffer provides an additional resource for a limited time interval T. That resource is equivalent to temporarily extending channel bandwidth to smooth the burstyness of traffic. Cells from virtual circuits (VCs) 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 VCs drops until the burst has been served. We will call the buffer for VC 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 the buffer from overflow. Since the data flow has burst components, a border of the buffer's filling will oscillate around the setpoint value.
Figure 4.
The choice of the setpoint (at the set-up phase of connection) reflects a trade-off between mean cell delay, cell loss, and bandwidth loss. Let S(t) = current buffer's filling (figure 4), <S(t)> = mean value of S(t), and <F(t)> = mean value of F(t).
If a control action is done once every q time units, we can make a fluid approximation of data flow, ignore cell boundaries, and define a speed of the buffer filling dS/dt by
dS/dt = F(t) + u(t) - C,
where C is the mean service rate and u(t) is the 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 available VC bandwidth. Denote the value of a variable x(t) by
x(t) = S(t) - <S(t)>
and a variable f(t) by
f(t) = F(t) - <F(t)>.
In case of mean value <F(t)> equal to service rate C, we can write the buffer equation in derivations
dx/dt = f(t) + u(t).
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 criteria the designers have to minimize the complexity of the control value computation--in our case the function
If Q(x)=x2, then J can be written as
J=<x2>
The requirements to minimize the cell loss ratio (CLR) value can be expressed by means of integral limitation <u2> <= Nu and the efficiency criterion expressed as weighted sum
J = m2<x2> + <u2> ,
where m2 = weight coefficient. Its value depends on the value of Nu.
The first item in J enforces the minimizing of cell delay variency (CDV); the second item enforces the minimizing of CLR. Choosing the value of Nn reflects the relative significance of regulating CLR and CTD.
The depth of criterion minimum that can be reached depends on information from input data streams. To compute the minimum of J it is possible to use spectral density Af(w), which is a 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 <u2> 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 through 7 show that, in the case of exponential distribution, the intensity of optimal control is lower than in the 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 a Poisson-like distribution to define traffic flow characteristics for cell discarding algorithms. The received value of control action u(t) can be used in cell discarding algorithms as well as to change the source intensity in the ABR mode. This circumstance has to be taken under consideration to synthesize the controls needed.
Figure 5.
Figure 6.
Figure 7.