AP01_6.vp


1 Introduction
The ATM computer network consists of switches, sources

and destinations of the transported data. The ATM network is
based on switching packets of the same length called cells.
Switches can transmit packets from their input to their output
and also get information about the intensity of the traffic.
Network traffic management is a significant process used for
proper functioning of the network. The traffic management
is based on a specific algorithm. To avoid congestion, current
ATM networks use techniques of timeout, duplicate acknowl-
edge or explicit congestion notification.

For monitoring the state of the network, special cells
called RM (Resource Management) are used in the ATM
network. RM cells inform data sources about the maximum
rate of flow acceptable by the network. The load of the net-
work varies in time, and interference of different loads in the
same point can cause congestion. When this happens, the
memories of the switches are overloaded and incoming cells
have to be refused, i.e. removed. In this paper a new method
is proposed for an earlier reaction to congestion.

An analytical model of a switch was constructed for an
analysis of the network behaviour. This model is used for ana-
lysing traffic through the network. A description of the model
is given in the sections below.

1.1 Standard traffic management
There are several classes of traffic in the ATM network.

This paper considers the class called Available Bit Rate (ABR),
used for transmissing files.

The ABR class of ATM computer networks uses feedback
information on data transport from switches and destination
to the source to control the load. The feedback mechanism is
essential for good throughput of networks enabling an earlier
reaction of sources when congestion of switches occurs.

The transported data are arranged in packets of cells.
These packets have the same length, and a special cell called
the RM cell precedes every packet. The traffic management
is based on RM cells. RM cells pass from the source to the
destination and collect information about the maximum rate
of generated load which is acceptable by a dedicated path.
After their acceptance by the destination they are sent back in
order to bring the feedback information to the source. The

rate of the traffic load is adjusted in the source according to
the value received from the RM cell.

The flow of data cells together with RM cells between
switches SW (i) and SW (i+1) is shown in Fig. 1. The RM cells
are pictured as black rectangles, and the other cells as white
rectangles. The packets of data cells with the RM cell num-
ber 8 are sent from the data source, i.e. forwards. Only RM
cells 2 and 3 are sent backwards to bring feedback informa-
tion from the destination.

The disadvantage of this method is that the source of data
obtains information about the current rate of the load, but
it does not know which particular data was lost because it was
refused within the switches. This information can be obtained
later from the destination. In other words, RM cells always
have to go along the whole path from the data source to the
destination and back, see Fig. 5, 7.

1.2 Proposed traffic model
In the proposed model all RM cells are numbered by

the source. The RM cells are returned by the switches at the
moment of their congestion. If congestion occurs, the packets
are refused. But associated RM cells are immediately sent
back to inform the source of the loss of data. In this model, the
source is informed earlier about the congestion in the net-
work because RM cells did not pass along the whole path, see
Fig. 5, 8.

2 Analytical model of the switch
In this part the behaviour of basic network components –

switches – is studied. The behaviour of the switch can be de-
scribed as a stationary queueing process. Let (M|M|1|m) be
a queueing process according to the Kendall notation.

©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 45

Acta Polytechnica Vol. 41  No. 6/2001

Analytical Model of Modified Traffic
Control in an ATM Computer Network

J. Filip

The ABR class of ATM computer networks uses feedback information that is generated by net switches and destination and is sent back to a
source of data to control the net load. A modification of the standard traffic management of the ATM network is presented, based on the idea
of using RM cells to inform the source about congestion. An analytical model of a net switch is designed and mathematical relations are
presented. The probability of queueing is considered. The analytical model of the switch was constructed for the purpose of analysing the
network behaviour. It is used for investigating of cells passing through the network. We describe the model below. The submitted analytical
results show that this method reduces congestion and improves throughput.

Keywords: Throughput, congestion control, modelling, RM cell, cell refusal.

RM

Data
1

2 3

Fig. 1: The flow of counted RM cells



The symbols denote:
M – distribution function of the cell interarrival time is

exponential with the mean
1

0
�

�, � � � and the ar-
rival times are independent;

M – distribution function of the cell service time is expo-
nential with the mean

1
0

�
�, � � � and the service

times are independent;
1 – system with one place in service;
m – system of queue length m.

Notation used in the following text:
� – average arrival intensity;
� – average service rate;
� � �� – traffic intensity.

Let us assume that cells coming to switch are stored in
a switch queue of length m. Cells are refused if all of the m
waiting places are occupied, and further arriving cells are
cancelled. The situation is shown in Fig. 2. The cell with index
0 is being transmitted and the following cells are waiting in
the queue. The other incoming cells with an index equal to
or greater than m + 1 are refused.

The behaviour of this model is described by the probabili-
ties of all possible queue lengths and by the cell waiting time
in the queueing system.

The probability that there are just k waiting cells in the
queue is:

� �
p

p
m

k m

k

k

m+2

k

for and

for

�
�

�
�

�
	

� 
 


� �

�
�

�

1
1

1

1
2

1 0, .

(1)

The probability pz of cell refusal (all places in the queue
are occupied) is pz � pm + 1 and its value equals:

� �
p

p
m

z

m+1

m+2

z

for and

for

�
�

�
�

�
	

�

� �

�
�

�

1
1

1

1
2

1.

(2)

Fig. 3 shows the dependence of probability pz on the value
m for several values of traffic intensity �.

The cell waiting time W in this queueing system is a ran-
dom variable. For a description of the analytical model, the
mean value E (W) of the waiting time W is used:

� �E W
p

k

k

m

�

�

	

�0
1

1

�
�

k. (3)

Fig. 4 shows the dependence of the mean value E (W) on
the value m for several values of traffic intensity �.

We can also use the probability of service Pp,

P pp z� �1 . (4)

Other formulas describing the behavior of the queueing
system can be found in [5].

The behavior of the system for values of traffic intensity �
close to 1 will be studied. In this case the refusal of cells occurs
more frequently.

3 Path of cell transport
It is supposed that a path of cell transport from source S

to destination D includes a sequence of n switches SW (i),
1 
 
i n. The same path is used for both forward transport
of data cells together with RM cells and backward transport
of RM cells. In the backward transport the RM cells pass
through the switches in the reverse order. The switches are
marked SW (i), n i n	 
 
1 2 . Both paths are shown in Fig. 5.

The following notation is used in Fig. 5:
S – source of cells;
D – destination of a transport;
SW (i) – i-th switch in the path;
ti – time period needed for cell transport along the line

connecting switches SW (i) and SW (i+1).

46 ©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/

Acta Polytechnica Vol. 41  No. 6/2001

REFUSED

CELL

WAITING

CELLS

CELL IN

SERVICE

m +1 m 2 1 0

Fig. 2: The structure of a switch

0
0.002
0.004
0.006
0.008

0.01
0.012
0.014
0.016
0.018

0.02
0.022
0.024
0.026
0.028

0.03
0.032
0.034

100 200 300 400 500 600

pz

m

� � 1.01

� � 1

� � 0.98

� � 0.95

Fig. 3: Probability of cell refusal

� � 1.01

� � 1

� � 0.98

� � 0.95

100

200

300

400

500

0 100 200 300 400 500 600

�E W( )

m

Fig. 4: Mean value of the waiting time in the queue



3.1 Characterization of cell transport
The following cases of cell transport from the source to the

destination were studied:

� The data cell is transported without being refused.
� The data cell is just once refused during the transport.

The formulas for transport time will be stated below, and
we will use the weighted averages of the mean values of
these time periods to compare the two models. We choose the
probabilities of possible events as weight coefficients.

We do not consider the other cases of cell transport (when
the number of refusals is greater than 1) because earlier
studies [1, 2] have shown that the associated probabilities are
negligible. The probabilities of cell refusal in a switch are
shown in Fig. 3.

We use the following notation:
pz(i) – probability of cell refusal in the i-th switch due to full

switch buffer;
Pp(i) � 1 � pz(i) – probability of service in the i-th switch;
W(i) – waiting times in the queue of the i-th switch;
E (W (i)) – mean value of W (i);
ti – time period needed for cell transport along the line

connecting switches SW (i) and SW (i+1).

The sample space of the considered events consists of
independent elementary events {0, 1, 2, …, n}. The symbols
denote:
0 – the cell is transported without being refused in any

switch;
i – the cell is just once refused within the i-th switch SW (i),

i = 1, 2, …, n.

We assume that the associated request (the RM cell trans-
mitted from the destination to the source) and repeated
sending of data cells are delivered without refusal.

The probabilities of the described events are conditional
probabilities and their values can be approximated:

� � � � � � � �
� � � � � � � �

P P P P n

P i P P i p i i n

0 1 2

1 1 1 2

�

� � �

p p p

p p z

�

� �

;

, , , , .

The values of � �P i i np , , ,� 1 � , are close to 1 and the
values pz(i) � 1, i � 1, …, n. Therefore we can approximate
the probabilities P(i), i � 0, …, n, as:

� � � � � � � �� �
� � � � � �

P P p p p n

P i P i p i i n

0 1 1 2

1

0

1

� � � � � �

� � �

z z z

z

�

�

,

, , , .
(5)

We use the values P0, P1(i), i � 1, …, n as the probabilities
of the events {0, 1, …, n}.

We note that � �P P i
i

n
0 1

1

1� �

�
	 .

We consider the individual cases of the cell transport de-
noted by the symbols {0, 1, …, n} and we calculate their
transport time.

We denote:
Tst total time period of cell transport in the standard

model;
Tst

0 total time period of cell transport without refusal in
the standard model;

� �Ts it
1 total time period of cell transport with refusal in the

i-th switch in the standard model;
Tpt total time period of cell transport in the proposed

model;
Tpt

0 total time period of cell transport without refusal in
the proposed model;

� �Tp it
1 total time period of cell transport with refusal in the

i-th switch in the proposed model.

3.2 Cell transport without refusal
The value P0 is the probability of cell transport without

refusal within any switch of the path. It is actually the prob-
ability of a successful transmission without loss of any cell.

The influence of the proposed modification does not
appear in this case and the transport times in the standard
and proposed models are the same. In both models cells pass
along the whole path from source S to destination D. This
path is shown in Fig. 6.

The total time periods Tst
0 and Tpt

0 needed for the trans-

port of a particular cell along the whole path in the standard
and proposed models are equal, and are

� �Ts Tp t W k
k

n

k

n

t
0

t
0

k� � �

�

�

�
	 	

1

1

1

(6)

©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 47

Acta Polytechnica Vol. 41  No. 6/2001

SW(j)

W(j)

SW(n+1)

W(n+1)

SW(1)

W(1)

SW(i)
W(i)

SW(n)
W(n)

SW(2n)

W(2n)

Fig. 5: Path of cell transport

RM 9
SW(i) DS

1

Fig. 6: Path of a cell transport without refusal



The mean value of time Tst(0) and Tpt(0) is

� �� �E Ts E Tp t E W k
k

n

k

n

( ) ( )t0 t0 k� � 	
�

	

�
� �

1

1

1

(7)

because only time periods W (k) are random quantities.

3.3 Cell transport with refusal of cells in the
standard model

We calculate the transport time Tst(i). The assumption is
that a cell is refused in the i-th switch SW (i). The destination
must call for repeated sending of the refused cell. The proba-
bility � � � �P i p i1 � z of this case is given in (5).

The path of a cell transport in the standard model is
shown in Fig. 7. The switch SW (i) is congested and that is
why a cell is refused. Information about a cell being refused
is not known before an uncompleted packet is received by
destination D. Such a situation results in a request for a
repeated transmission of data cells until the complete packet
arrives at its destination.

The cell and the request have to pass the path three times
and the total time period needed for the cell transport � �Ts it

1 ,
i n� 1, ,� , is

� � � � � �Ts i t W k t W kt
k

n

k

n

k n

n
1

1

1

1 2

2 2

2� 	
�

�

�
��

�

�

�
��
	 	

�

	

� � 	

	

� � �k k
k n

n

� 	
�

1

2

. (8)

The mean value of the time period � �� �E Ts it1 is

� �� � � �� �E Ts i t E W k

t

k

n

k

n

k n

n

t k

k

1

1

1

1

2

2 2

2� 	
�

�

�
��

�

�

�
��
	

	

�

	

�

� 	

	

� �

� � �� �	
� 	
�E W k

k n

n

1

2

.

(9)

3.4 Cell transport with refusal of cells in the
proposed model

In the proposed modification, the cell transport path and
the associated request are shown in Fig. 8. The request for the
repeated sending is sent immediately from the congested
switch SW (i). We can see that in this case the cell and the
associated request for its repeated sending does not very often
pass along all the way from the source to the destination.

The cell is refused in the i-th switch with the probability
� � � �P i p i1 � z .

The time periods needed for the transport along the
individual parts of the whole path are:

1. � �t W k
k

i

k

i

k

� �

�

� �	
1 1

1

This is the time period of cell transport from source S to
switch SW (i):

2. � �t W k
k n i

n

k n i

n

k

� � 	

	

� � 	
� �	
2 3

2 2

2 2

2

This is the time period needed for transmission of the
repeated sending request from switch SW (i) to source S.

3. � �t W k
k

n

k

n

k

�

	

�
� �	

1

1

1

This is the time period needed for transport of the cell
from source S to destination D.

The total time period � �Tp it
1 needed for the transport is:

� � � � � �Tp i t W k t W k
k

i

k

i

k n i

n

k n i

t
1

k k� 	 	 	

� �

�

� � 	

	

� � 	
� � �

1 1

1

2 3

2 2

2 2

� �

2

1

1

1

n

k

n

k

n

t W k

�

� �

	

	 	

�

	

�

k .

(10)

The mean value of time period � �� �E Tp it1 is

� �� � � �� �

� �� �

E Tp i t E W k t

E W k

k

i

k

i

k n i

n

k n

t
1

k k� 	 	 	

	

� �

�

� � 	

	

�

� � �
1 1

1

2 3

2 2

2

� �� �
� 	 �

	

�
� � �	 	

i

n

k

n

k

n

t E W k

2

2

1

1

1

k .

(11)

4 Comparison of cell transports
We now compare the total time period of the cell transport

in the standard model and in the proposed model. The
transport time in the individual cases denoted by indeces
{0, 1, …, n} are random variables and the corresponding
probabilities P 0, P 1(i) are given in (5). As the mean value
of the total transport time periods Tst and Tpt we use the
weighted averages of mean values � �E Tst0 , � �� �E Ts it1 and

� �� �E Tp it0 , � �� �E Tp it1 . The coefficients of weighted averages
are the probabilities P 0, P 1(i).

If we denote by E (T st) the mean value of the total time pe-
riod of the cell transport in the standard model and by E (T pt)
the same quantity in the proposed model, we obtain:

� � � � � �� � � �

� � � � � �� � � �

E Ts E Ts P E Ts i P i

E Tp E Tp P E Tp i P i

i

n

t t t

t t t

� 	

� 	

�
�0 0 1 1

1

0 0 1 1

,

.

i

n

�
�

1

48 ©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/

Acta Polytechnica Vol. 41  No. 6/2001

RM 9

SW(i) DS
RM 9

RM 9

1

3

2

Fig. 7: Path of a cell transport with refusal in the standard model

RM 9
SW(i) DS

RM 9

RM 9

1

3

2

Fig. 8: Path of a cell transport with refusal in the proposed model



The effect of the modification of the standard model is
expressed by the difference

� � � � � � � �� �

� �� � � �� �� � � �

E Ts E Tp E Ts E Tp P

E Ts i E Tp i P i

E T

i

n

t t t t

t t

� � � �

� � �

�

�
	

0 0 0

1 1 1

1

� �� � � �� �� � � �s i E Tp i P i
i

n

t t
1 1 1

1

�

�
	

(12)

where we use the equality (7) � � � �E Ts E Tpt t0 0� . The values
� �� �E Ts it1 and � �� �E Tp it1 are given in (9), (11). The last

expression depends on many parameters. We determine its
value for one simple case. In the sequel we assume that the
switches are identical, i.e. the waiting times W (k) are the same
and times tk are equal.

We denote:

� � � �� �
� � � �


 t t k n

E W E W k k n
p p k P P k k n

� � � �

� � �

� � � �

k

z z p p

, ;

, ;
, , .

1 2 2

1 2
1 2

In this case we get

� �� � � � � �� �
� �� � � � � � � �� �

E Ts i n t n E W

E Tp i n i t n i E W

i

t

t

1

1

3 3 3

2 1 2 2

1

� � �

� � � � � �

�







,

,

, ,� n.

� � � �

� � � �� �� �

� � � �� �

E Ts E Tp

p n i t E W

n n p t E W
i

n

t t

z

z

1 1

1

2 1

1

� �

� � � � �

� � �
�
	 



 .

(13)

The value � � � �E Ts E Tpt t1 1� depends on the parameters
of the switch (E (W ), pz) and the value �t. We can suppose that
the values � t � E (W ) and therefore the comparison of the
two models is demonstrated by the expression

� � � �V p E W n n� �z 1 .
The values pz, E(W) and Pp are defined in (2), (3), and (4).

The following table contains the values of V for some path
transport parameters.

Figs. 9 and 10 show the dependence of V on the number n
of the switches for several values of traffic intensity �. Fig. 11
shows this dependence for several values of buffer storage m
and traffic intensity � = 1.

The value of expression V depends on the product of the
probability pz and the mean value of the waiting time E (W).
Figs. 12 and 13 show the dependence of the product pzE (W)
on value m for several values of traffic intensity �.

Conclusion
The influence of the proposed modification of cell trans-

port in an ATM computer network is tested. Analytical
models of cell transport through standard and proposed
modification are described. Formulas for the time period
needed for cell transport for both models are presented.

©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 49

Acta Polytechnica Vol. 41  No. 6/2001

V

m n � � 1.01 � � 1 � � 0.99 � � 0.98

32 10 66.3 53.4 42.4 33.1
32 20 253 204 162 126
32 50 1536 1237 928 767
64 10 81.4 53.7 33.9 18.8
64 20 311 205 129 71.8
64 50 1887 1244 785 436
96 10 98.6 54.5 26.8 11.7
96 20 376 208 102 44.8
96 50 2285 1262 625 272

128 10 120 54.7 21.2 6.8
128 20 459 209 81 26
128 50 2788 1267 492 158

Tab. 1: Influence of modification on the transport quality

0

1000

2000

3000

4000

5000

6000

20 40 60 80 100

V

n

Fig. 9: Dependence of V on parameter n of the path

0

1000

2000

3000

4000

5000

6000

7000

20 40 60 80 100

V

n

Fig. 10: Dependence of V on parameter n of the path

0

1000

2000

3000

20 40 60 80 100

V

n

Fig. 11: Dependence of V on parameter n of the path



A comparison is made by the weighted averages of the mean
values of the time period needed for cell transport E (T st),
E (T pt). As the coefficient of weighted values, we choose
the probabilities of particular cases. We assumed transports
without refusal and with one refusal only.

The differences of the mean values E (T st) and E (T pt) (13)
are approximated by the expression V. Its values in Table 1

and the graph dependences in Figs. 9, 10 and 11 show that
the effect of the proposed modification grows with increased
values of traffic intensity �. From Table1 and Fig.12, 13 it
follows that if traffic intensity � <1, then the effect of the pro-
posed modification decreases with increased values of buffer
storage size m while for � � 1 the effect of the proposed
modification grows. This is caused by the fact that when m
increases, then the probability pz of cell refusal decreases, but
for � � 1 the mean of the waiting time E (W) increases faster,
hence the product pzE (W) increases. If � <1 then this does
not happen. We see from Tab.1 that in this case the effect of
the modification actually becomes smaller as we increase m.

References
[1] Filip, J.: Data transfer with modified RM cells. In: Proceed-

ings of Workshop 97, Prague, CTU, 1997
[2] Filip, J.: Switching an alternative for high-speed networks. In:

Proceedings of Workshop 96, Prague, CTU, 1996
[3] Filip, J.: Data Transports in ATM Networks. In: Proceed-

ings of Workshop 2000, Prague, CTU, 2000
[4] Brandt, A., Fraenken, P., Lisek, B.: Stationary Stochastic

Models. Akademie – Verlag Berlin, 1990
[5] Zitek, F.: Malé zastavení času. SPN Praha, 1975
[6] ATM Forum Technical Committee “Traffic manage-

ment Specification Version 4.0”, April 1996

Ing. Jiří Filip
e-mail: fofis@post.cz

Ministerstvo zahraničních věcí České republiky
Ministry of foreign affairs of the Czech republic
Loretánské náměstí 5,
118 00, Praha 1, Czech Republic

50 ©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/

Acta Polytechnica Vol. 41  No. 6/2001

0
0.02
0.04
0.06
0.08

0.1
0.12
0.14
0.16
0.18

0.2
0.22
0.24
0.26
0.28

0.3

40 60 80 100 120 140 160
m

p E Wz ( )

Fig. 12: Dependence of pzE (W) on value m

0.2
0.4
0.6
0.8

1
1.2
1.4
1.6
1.8

50 100 150 200 250
m

p E Wz ( )

Fig. 13: Dependence of pzE (W) on value m