5
Fundamentals of Simulation
those vital statistics
DISCRETE TIME SIMULATION
This chapter is intended as an introduction to simulation and, in particular,
its application to cell- and packet-based queueing. For anyone wanting
a more comprehensive treatment of the subject of simulation in general,
we refer to [5.1].
We will introduce the subject of simulation by concentrating on a
discrete version of the M/D/1 queue, applicable to the study of ATM cell
buffering. There are two basic ways to simulate such a queue:
ž discrete time advance
ž discrete event advance
In the former, the simulator moves from time instant i to time instant
i C 1 regardless of whether the system state has changed, e.g. if the
M/D/1 queue is empty at i it could still be empty at i C 1andthe
program will still only advance the clock to time i C 1. These instants
can correspond to cell slots in ATM. In discrete-event simulation, the
simulator clock is advanced to the next time for which there is a change
in the state of the simulation model, e.g. a cell arrival or departure at the
M/D/1 queue.
So we have a choice: discrete time advance or discrete event advance.
The latter can run more quickly because it will cut out the slot-to-
slot transitions when the queue is empty, but the former is easier
to understand in the context of ATM because it is simpler to imple-
ment and it models the cell buffer from the point of view of the
server process, i.e. the ‘conveyor belt’ of cell slots (see Figure 1.4).
We will concentrate on the discrete time advance mechanism in this
introduction.
Introduction to IP and ATM Design Performance: With Applications Analysis Software,
Second Edition. J M Pitts, J A Schormans

serve a waiting cell
IF K > 0 THEN
K := K —1
ELSE
K := 0
store results
histogram[K] := histogram[K]+1
advance time to next time slot
i := i +1
END WHILE
END
The main program loop implements the discrete time advance mechanism
in the form of a loop counter, i. The beginning of the loop corresponds
to the start of time slot i, and the first section ‘generate new arrivals’ calls
function ‘Poisson’ which returns a random non-negative integer for the
number of cell arrivals during this current time slot. We model the queue
with an arrivals-first buffer management strategy, so the service instants
occur at the end of the time slot after any arrivals. This is dealt with by
the second section, ‘serve a waiting cell’, which decrements the queue state
variable K, if it is greater than 0, i.e. if the queue is not empty. At this
point, in ‘store results’ we record the state of the queue in a histogram. This
is simply a count of the number of times the queue is in state K,foreach
possible value of K, (see Figure 5.1), and can be converted to an estimate
of the state probability distribution by dividing each value in the array
‘histogram[]’ by the total number of time slots in the simulation run.
DISCRETE TIME SIMULATION
71
0510
10
0

END FUNCTION
The REPEAT loop corresponds to the ‘generation’ of cells, and the loop
records the number of cells in the batch in variable j, returning the
final total in variable X. Remember that with this particular simulation
program we are not interested in the arrival time of each cell within the
slot, but in the number of arrivals during a slot.
72
FUNDAMENTALS OF SIMULATION
But how do we generate the random numbers themselves? A good
random number generator (RNG) should produce a sequence of numbers
which are uniformly distributed on the range [0, 1] and which do
not exhibit any correlation between the generated numbers. It must
be fast and avoid the need for much storage. An important prop-
erty of the random number sequence is that it must be reproducible;
this aids debugging, and can be used to increase the precision of the
results.
A typical RNG is of the form:
U
i
D a Ð U
i1
C c modm
where U
i
is the ith random number generated, and m (the modulus), a
(the multiplier) and c (the increment) are all non-negative integers, as is
U
0
, the initial value which is called the ‘seed’. The values should satisfy
0 < m, a < m, c < m and U

applied. In our discrete time advance simulation, we are simulating time
slot by time slot, where each time slot can have 0 or more cell arrivals.
The RNG is called once per time slot, and then once for each cell arrival
DISCRETE TIME SIMULATION
73
during the time slot. With the discrete event advance approach, a cell-
by-cell simulator would call the RNG once per cell arrival to generate the
inter-arrival time to the next cell.
The Wichmann–Hill algorithm has a period of about 7 ð 10
12
.Thus,
so long as the number of units simulated does not exceed the period
of 7 ð 10
12
, this RNG algorithm can be applied. The computing time
required to simulate this number of cells is impractical anyway, so we can
be confident that this RNG algorithm will not introduce correlation due
to repetition of the random number sequence. Note that the period of the
Wichmann–Hill algorithm is significantly better than many of the random
number generators that are supplied in general-purpose programming
languages. So, check carefully before you use a built-in RNG.
Note that there are other ways in which correlations can appear in a
sequence of random numbers. For more details, see [5.1].
M/D/1 queue simulator in Mathcad
The following Mathcad code implements the discrete time advance
simulator pseudocode for the M/D/1 queue. Note that the WHILE loop
in the main pseudocode is vectorized (using range variable i), as is the
REPEAT loop in the Poisson function pseudocode (using range variable j).
An example of the histogram of queue state results is shown in Figure 5.1
(plotting

< a , 0 , 1
A
i
:D

j
cells
i , j
serve a waiting cell
K
i
:D max[[0 K
i1
C A
i
  1]]