PART II
ATM Queueing and
Traffic Control
Introduction to IP and ATM Design Performance: With Applications Analysis Software,
Second Edition. J M Pitts, J A Schormans
Copyright © 2000 John Wiley & Sons Ltd
ISBNs: 0-471-49187-X (Hardback); 0-470-84166-4 (Electronic)
7
Basic Cell Switching
up against the buffers
THE QUEUEING BEHAVIOUR OF ATM CELLS IN OUTPUT
BUFFERS
In Chapter 3, we saw how teletraffic engineering results have been
used to dimension circuit-switched telecommunications networks. ATM
is a connection-orientated telecommunications network, and we can
(correctly) anticipate being able to use these methods to investigate the
connection-level behaviour of ATM traffic. However, the major difference
between circuit-switched networks and ATM is that ATM connections
consist of a cell stream, where the time between these cells will usually
be variable (at whichever point in the network that you measure them).
We now need to consider what may happen to such a cell stream as it
travels through an ATM switch (it will, in general, pass through many
such switches as it crosses the network).
The purpose of an ATM switch is to route arriving cells to the appro-
priate output. A variety of techniques have been proposed and developed
to do switching [7.1], but the most common uses output buffering. We
will therefore concentrate our analysis on the behaviour of the output
buffers in ATM switches. There are three different types of behaviour in
which we are interested: the state probabilities, by which we mean the
proportion of time that a queue is in a particular state (being in state k
means the queue contains k cells) over a very long period of time (i.e.

slot occur before the departure instant for the cell in service during the
timeslot.Thisiscalledan‘arrivals-first’ buffer management strategy. We
will also assume that if a cell arrives during time slot n, the earliest it can
be transmitted (served) is during time slot n C 1.
For our analysis, we will use a Bernoulli process with batch arrivals,
characterized by an independent and identically distributed batch of k
arrivals (k D 0, 1, 2,...)ineachcellslot:
ak D Prfk arrivals in a cell slotg
It is particularly important to note that the state probabilities refer to the
state of the queue at moments in time that are usually called the ‘end of
time-slot instants’. These instants are after the arrivals (if there are any)
and after the departure (if there is one); indeed they are usually defined
to be at a time t after the end of the slot, where t ! 0.
BALANCE EQUATIONS FOR BUFFERING
The effect of random arrivals on the queue is shown in Figure 7.2. For the
buffer to contain i cells at the end of any time slot it could have contained
any one of 0, 1,...,i C 1 at the end of the previous slot. State i can be reached
BALANCE EQUATIONS FOR BUFFERING
99
i
.
.
.
3
2
1
0
a(i-1)
a(i-2)
a(i)

s
100
BASIC CELL SWITCHING
If we now consider the service time of a cell to be one time slot, for
simplicity, then the average number of arrivals per time slot is denoted
E[a] (which is the mean of the arrival distribution ak), and the average
number of cells carried per time slot is the utilization. Thus
E[a] D 
But the utilization is just the steady-state probability that the system is
not empty, so
E[a] D  D 1  s0
and therefore
s0 D 1  E[a]
So from just the arrival rate (without any knowledge of the arrival
distribution ak) we are able to determine the probability that the system
is empty at the end of any time slot. It is worth noting that, if the applied
cell arrival rate is greater than the cell service rate (one cell per time
slot), then
s0<0
which is a very silly answer! Obviously then we need to ensure that cells
are not arriving faster (on average) than the system is able to transmit
them. If E[a]  1 cell per time slot, then it is said that the queueing system
is unstable, and the number of cells in the buffer will simply grow in an
unbounded fashion.
CALCULATING THE STATE PROBABILITY DISTRIBUTION
We can build on this value, s0, by going back to the idea of adding all
the ways in which it is possible to end up in any particular state. Starting
with state 0 (the system is empty), this can be reached from a system state
of either 1 or 0, as shown in Figure 7.3. This is saying that the system can
be in state 0 at the end of slot n  1, with no arrivals in slot n,oritcanbe

s2 D
s1  s0 Ð a1  s1 Ð a1
a0
We can continue with this process to find a similar expression for the
general state, k.
sk  1 D s0 Ð ak  1 C s1 Ð ak  1 C s2 Ð ak  2 CÐÐÐCsk  1
Ð a1 C sk Ð a0
which, when rearranged, gives:
sk D
sk  1  s0 Ð ak  1 
k1

iD1
si Ð ak  i
a0
1
0
2
a(0)
a(1)
a(1)
Figure 7.4. How to Reach State 1 at the End of a Time Slot