Queuing Theory                                                          1

 


Queuing Theory

 

All packet systems at some time or other have to be able to store, or queue packets for transmission. It is therefor necessary to spend some time examining the nature of queues.

The standard notation used to describe a queue is of form A/B/m where:

  A = inter arrival time probability density

  B = service time probability density

  m = number of servers

The probability densities fall into three general categories:

  M - Markov or exponential

  D - deterministic where all customers have the same value

  G - general or arbitrary

The M/M/1 queuing model has well define mathematical characteristics. However, although the arrival rate may be quite random, most data networks place restrictions on the size of the data packet. Therefore the M/G/1 queue may give more accurate results although the mathematics is sometimes more cumbersome. Even more complex models are available to characterize multiserver queuing systems.

All data packets coming into a system are initially buffered in an input queue.

The processor examines the packets and determines which output queue to place it in. Note that packets, messages, calls, and arrivals are terms which may in most cases be used interchangeably.

Poisson Distribution

The probability of n packets (or calls), having an average arrival rate of l packets per second, arriving in any given d second period is given by:

Example:

If on the average, 5 packets per second arrive at a packet switch, what is the probability that 10 packets will arrive in a given second if the arrivals are to­tally random?

Solution:

This shows that there is only a 1.8% probability of 10 packets arriving in 1 second. This simple calculation forms an important basis from which to design a packet switching network, since it can be used to establish acceptable grades of service.

For stable operation, the average queue length should not vary rapidly and the number of items requiring temporary storage should not exceed the buffer size. The probability of the queue growing  depends on the rate which new customers enter the system (l). If the service time (t) is fixed, then the utilization (r) is proportional to l.

The average number of users waiting in the queues de­pends on how busy the system is. (i.e., on its utilization r)

Utilization is defined as . From this, the average waiting time may be deduced:

The average delay is the sum of the service time and waiting time:

A graph of this shows that at minimum loading or utilization of the packet switch, the minimum delay is equal to t. At 50% utilization, the delay increases to 2t since on the average, there will be one packet already in the queue. If the utilization goes up to 90%, then the delay in­creases to 10t.

Blocking Probabilities

If the connection cannot be setup when the user wishes, the call is terminated in a standard telephone system. This is generally not tolerated in packet networks, since the incoming packet can be stored until a route becomes available.

The probability of blocking (PoB) is related to the traffic demand in Erlangs (E) and the number of links (L).

Example:

Find the % of calls blocked if there is a traffic demand of 0.5 Erlangs on a single link.

Solution:

        or 33%.

Note what happens if the number of links is quadrupled, but the utilization of each link remains constant:

Although the individual line utilization remained at 0.5, and the overall traffic increased by a factor of 4, and the probability of blocking reduced to 9.6%.

This suggests that it is more efficient to combine a large amount of traffic into a single large facility than to distribute the traffic among a number of smaller systems.

For example:

is better than: