Simulating Queues

The simplest way to simulate a queuing system is to use a discrete event simulation. There are enough resources on the web explaining this approach, try the links page for more information. This page has three parts:

Generation of traffic

Using a random number generator, the time between two packets is determined. Using addition, the exact time of an arrival is calculated, and when the simulation reaches that time, a packet is offered to the queue. For every traffic type that you want, there is a special traffic source, and thus the packets for that traffic type are generated one after another, independent of other traffic. The size can be fixed for a traffic type, but a random size is also possible.

Several different distributions can be used to generate traffic, but there are three important ones.

  1. First, there is a rather trivial one: the constant distribution. This is not really a distribution, although you can describe it as one when imagining an infinite high probability density on a single point. (Yielding a probability mass of exactly one on that point) This is well known in signal theory as a Dirac pulse.
    The constant distribution is used to generate constant bitrate traffic, where the time between two packets is a constant. Although it is not really a distribution, it is modeled like one.
  2. The second probability distribution is the negative exponential distribution. The time between two packets is negative exponentially distributed when the process generating them is a Poisson type. This means that the time between two packets is independent of the time already spend waiting. A packet can come any moment, and the probability of a packet arriving in a certain interval only depends on the length of the interval. Since we are using a continues time scale, the probability of a packet arriving at a precise time approaches zero.
  3. The third important probability distribution is the Pareto distribution. This distribution results in a drastically varying bitrate since it has rather high (compared with negative exponential) probability for extremely large inter-arrival times. Since large inter-arrival times result in large periods of silence, the bursts of traffic between them must have large amounts of traffic to keep the average the same. This distribution is used to model data (computer) traffic, since computers tend to transmit irregular bursts of data with large silence times between them.

Back to the top

Servicing Traffic

Traffic that arrives at the queue is stored inside where it awaits service. When the buffer space in the queue is exhausted, there are two possibilities: Traffic already in the queue is dropped or the newly arrived packet is dropped. Which one of these probabilities is used depends on the priorities used.

While there is traffic in the buffer, a packet is extracted and serviced. When the time needed to service a packet is completed, the next packet is extracted from the buffer and serviced. Which packet is extracted depends again on the priorities used. When all packets are serviced the queue will stop servicing until a new packet arrives.

Back to the top

Obtaining Results

Every packet in the simulation is counted. Its arrival and departure or drop are counted and the delay is calculated. These statistics are kept on a per-queue and per-traffic basis. Since their are two queue's, there are alway two traffic data measurements (loss, delay) for each traffic class used.
When replications are made, the variance and the average of the results from the independent simulations are calculated. With this information confidence intervals are calculated and these intervals are presented are the final results.
The results are presented as follows. For each traffic class used, the delay and loss confidence intervals are presented for each queue seperately. In the applet this is done in a bar-graph with a relative scale, and on the Java-console all numbers are printed.

Back to the top

Quick Jumps

Back to the top

Copyright © 2000 Philips Business Communications, Hilversum, The Netherlands.
See legal statement for details