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.

- 1. Introduction
- 2. Proposed approach
- 3. Traffic source model
- 4. An example of optimal control synthesis
- 5. Conclusions
- 6. Acknowledgments
- 7. References

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:

- the model of input variables,
- the model of object under control,
- the formal definition of efficiency criterion,
- the methods of the optimal regulator deriving,
- the set of parameters transmitted to another levels.

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 **{X _{n}}** representing the spacing of cell
flow. The process parameters have to satisfy the restrictions derived from
the traffic parameters (table 1): Mean

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
**T _{0}**.The arcs

The values **M(s _{1}), u, v**, and

Figure 1.

The transition **t _{0}** may be considered as an internal
clock of the source and has a finite firing time

Transitions **t _{1}** and

It may be shown
[5] that the model regulates, for
reproducing processes **Pr**, the firing count ratio between
**t _{1}** and

**syn(t1,t2)=^(z-q)/d^+^q/d^**,

where **^x^** denotes the greatest integer **<=x** and **d**
is the greatest common divisor of **h _{1}(Pr)** and

CASE 1. CBR class traffic source model.

The relations between the Petri net characteristics and traffic source
parameters are as follows: **M(s _{1})=1**,

Then the firing sequence of transition **t**_{1}will exactly
correspond to the CBR traffic with **PCR = 1/2T _{0}**.

CASE 2. VBR class traffic source model.

The relations between the Petri net characteristics and traffic source
parameters are as follows:

**M(s _{1})=MBS*(PCR-SCR)/w**, where

Then the firing sequence of transition **t**_{1}will exactly
correspond to the VBR traffic with **PCR=1/T _{0}**,

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(s _{1})=8, v=1, u=2, T_{0}=1/PCR**.

The possible firing sequences which start with initial marking
**M _{0}** and time diagram of cell sending are shown in figure 2,

Figure 2.

where

1 0 |
t_{i}> |
0 1 |

denotes the change of the marking **M(s _{1})=1**,

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 **t _{1}**.

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/T _{0}**.

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 **T _{0}**
of transition

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

**K _{f}(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

**K _{p}(t) = ne^{-bt}**.

In frequency domain traffic, models can be characterized by spectral
density **A _{f}(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)=x ^{2}**, then

**J=<x ^{2}>**

The requirements to minimize the cell loss ratio (CLR) value can be
expressed by means of integral limitation **<u ^{2}>
<= N_{u}** and the efficiency criterion expressed as
weighted sum

**J = m ^{2}<x^{2}> + <u^{2}> ,**

where **m ^{2}** = weight coefficient. Its value depends on the
value of

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 **N _{n}** 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 **A _{f}(w)**, which is a
Fourier transform of autocorrelation function

In case of **K _{f}(t) = (g+t)^{-b}**, the

as well as **J**

.

This value of **J** is achieved by using a linear feedback law

.

Note that if **A _{f}(w)** satisfies a Poisson-like
distribution with parameter

Figure 5.

Figure 6.

Figure 7.

- V. Zaborovski. "Bringing Internet to North- West Russia--RUSnet N/W project." Proceedings of INET'95, Honolulu, USA, 1995. ( http://info.isoc.org/HMP/PAPAR/115/abst.html)
- V. Zaborovski. "The main aspects of construction of the Northern-Western segment of Russian University and Scientific Network." Posters of JENC6. Tel Aviv, Izrael, 1995.
- V. Zaborovski, A. Vasilev. "Cooperative Network Engineering in N/W of Russia." Proceedings of MULTICUBE Collaborative Workshop, Torino - Madrid, 1996.
- T. Murata. "Petri Nets: Properties, Analysis and Applications." Proceedings of the IEEE, v. 77, N4, April 1989.
- W. Kluge, K. Lautenbach. "The Orderly Resolution of
Memory Access Conflicts Among Competing Channel Processes."
*IEEE Trans.*, 1982, v C-31, N3. - W. E. Leland. "On the Self-Similar Nature of
Ethernet
Traffic."
*Proc. SIGCOMM '93*, Vol. 23, No 4, October 1993. - ATM Forum Traffic Management Specification. Version 4.0. (http://www.atmforum.com).
- R. Jain. "Myths About Congestion Management in High-Speed Networks."( http://www.cis.ohio-state.edu/~jain).
- J. L. Peterson. "Petri Net Theory and the Modeling of Systems." Englewood Cliffs., N.J.: Prentice-Hall, Inc., 1981.