Teletraffic engineering/What is queueing

Summary

Queues of some sort are central in the majority of models of computer and other communications systems because they represent contention for resources. The servers associated with queues correspond to resources and the customers that enter queues correspond to tasks, jobs, messages or packets that constitute the workload of the physical system.[2] Queues appear in many areas of life hence their understanding is important.

What is a Queue?

Definition

In the context of Teletraffic, a queue is said to be formed when service requests arrive at a service point or facility and are forced to wait while the server is busy working on other requests[1]. The phenomenon of queueing arises whenever a shared facility needs to be accessed for service by a large number of entities needing the services offered by the facility.

Why Study Queues?

When the nummber of service request on a system start increasing, the systems begins to get congested and the service delay in the system increases. A good understanding of the relationship between congestion and delay is essential for designing effective congestion control algorithms. In PSTNs for eaxample the use of queueing allows the systems to queue their customer's requests until free resources become available. This means that if traffic intensity levels exceed available capacity, customer’s calls are no longer lost; they instead wait until they can be served.[4] This method is used in queueing customers for the next available operator.

Queuing theory provides the tools that are needed for analyzing queues.

Queueing theory

Any queue consists of three components: an arrival process which determines when cutomers arrive at the queue and what there characterisc are; a buffer (also referred to as the queue itself) where customers wait to be served and a service time requirement for each customer at the server serving the queue.

By convention, the term queue length includes the customer currently being served, if any. Thus for an empty queue, the server is idle. Customer's service time is determined by the demand of the customer expressed in units of work and the service rate of the server specified by work units performed in unit time. Service time is then the demand divided by the rate.[2]

Queues are classified according to Kendalls notation which in its original form defines the class A/S/m as follows:

A describes the nature of the arrival process. If for example the arrival process is Poisson, A=M for Markovian or memoryless. If the inter-arrival times are constant,A=D for deterministic. For a general inter-arrival rate A=G. The arrival rate is conventionally denoted by λ which is the reciprical of the mean inter-arrival time. In general λ may depend on the number of customers in the queue

S denotes the service time distribution. We could have S=M for Markovian service time, i.e. one with exponential distribution, S=D for deterministic or constant service times.

m denotes the number of servers available to give service to the customers in the queue.

The Queueing discipline describes how the server decides which customer in the queue to pick next for service. Common disciplines are:

First in first out FIFO in which customers are served in strict order of arrival.

Last in first out LIFO under which the most recent arrival is served first.

Kendall's notation has been extended to include two additional fields that define the capacity of the buffer/waiting room, c, and the population of the customer pool, i.e. the maximum number of customers, p. The queue is then specified as A?S/m/c/p. If c and p are unspecified they are assumed to be infinite.

Little's Theorem

The average number of customers L in the system can be determined from the following equation:

L = λW

where λ is the mean arrival rate of tasks/customers; W is the mean time spent by a task/customer in the system.[2]

Figure 1: A simple queueing system

The proof of Little's theorem is presented in [2].

In a Telecommunications network, queueing is handled by control processes within exchanges, which can be modelled using state equations. Queueing systems use a particular form of state equations known as Markov chains which model the system in each state. Incoming traffic to these systems is modelled via a Poisson distribution and is subject to Erlang’s queueing theory assumptions[4]:

Pure-Chance Traffic – Call arrivals and departures are random and independent events.
Statistical Equilibrium – Probabilities within the system do not change.
Full Availability – All incoming traffic can be routed to any other customer within the network.
Congestion is cleared as soon as servers are free.

To derive a queueing model that represents a real-life system, we prefer a form that is simple or tractable, but require that it be sufficiently realistic. For queueing theory, it has been found convenient to work with probability distributions which exhibit the memoryless property, as this commonly simplifies the mathematics involved. As a result, queuing models are frequently modeled as Poisson processes.[5]

Example

A router in a computer network is able to service any ip packet in an average time of 0.1 seconds. Suppose the traffic intensity intensity is 100 packets/second, what is the mean number of of packets in the queued in the router?

Solution

Using Little's theorem,

Number of packets in queue = 100*0.1 = 10 packets

Exercise

Using Kendall's notation, describe a queue with a single server, a Markovian inter-arrival process with a constant service time.

Solution

For a single server m=1. Since the service time is constant S = D showing that it is deterministic. The inter-arrival process is Markovian hence A = M. By Kendall's notation, the queue is described as

M/D/1

References

[1] http://socr.uwindsor.ca/~hlynka/qdef.html Last accessed 21 March 2007

[2] Harrison P.G, and Patel M.N, Performance Modelling of Communication Networks and COmputer Architecture, Addison-Wesley Publishing Company, 1992

[3] http://www.eventhelix.com/RealtimeMantra/CongestionControl/queueing_theory.htm Last accessed 21 March 2007

[4] Wikipedia Queueing Theory Last accessed 21 March 2007

[5] Kennedy I. G.,Grade of Service. Teletraffic Engineering-ELEN7015 Full Lecturing Notes, School of Electrical and Information Engineering, University Of Witwatersrand, Johannesburg,2007