Misplaced Pages

Revision as of 12:07, 13 March 2006

Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues). There are several related processes, arriving at the back of the queue, waiting in the queue (essentially a storage process), and being served by the server at the front of the queue. It is applicable in transport and telecommunication and is occasionally linked to ride theory.

History and notation

Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on queueing theory in 1909.

David G. Kendall introduced an A/B/C queueing notation in 1953. Kendall's notation for describing queues and their characteristics can be found in Template:Fn. It has since been extended to 1/2/3/(4/5/6) where the numbers are replaced with:

1. A code describing the arrival process. The codes used are:
   • M stands for "Markovian", implying exponential distribution for service times or inter-arrival times.
   • D stands for "degenerate" distribution, or "deterministic" service times.
   • Ek stands for an Erlang distribution with k as the shape parameter.
   • G stands for a "General distribution". (Note that although G usually refers to independent arrivals, some authors prefer to use GI to be explicit)
2. A similar code representing the service process. The same symbols are used.
3. The Number of service channels (or servers).
4. The capacity of the system, or the maximum number of customers allowed in the system including those in service. When the number is at this maximum, further arrivals are turned away.
5. The Priority order that jobs in the line are served:
   • First Come First Served (FCFS),
   • Last Come First Served (LCFS),
   • Service In Random Order (SIRO) and
   • Processor Sharing.
6. The size of calling source. The size of the population from which the customers come. This limits the arrival rate. As more jobs queue up there are fewer available to arrive into the system.

The word queue comes from the Latin cauda, meaning tail. Most researchers in the field prefer the spelling 'queueing' over 'queuing', although the latter is somewhat more common in other contexts.

Queueing theory is directly applicable to intelligent transportation systems, call centers, PABXs, networks, telecommunications, server queueing, mainframe computer queueing of telecommunications terminals, advanced telecommunications systems, and traffic flow.

Application of queueing theory to telephony

The Public Switched Telephone Networks (PSTNs) are designed to accommodate the offered traffic intensity with only a small loss. The performance of loss systems is quantified by their Grade of Service (GoS), driven by the assumption that if insufficient capacity is available, the call is refused and lost Template:Fn. Alternatively, overflow systems make use of alternative routes to divert calls via different paths -- even these systems have a finite or maximum traffic carrying capacity Template:Fn.

However, the use of queueing in PSTNs 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 here no longer lost; they instead wait until they can be served Template:Fn. This method is used in queueing customers for the next available operator.

A queueing discipline determines the manner in which the exchange handles calls from customers Template:Fn. It defines the way they will be served, the order in which they are served, and the way in which resources are divided between the customers Template:Fn,Template:Fn. Here are details of three queueing disciplines:

• First In First Out – This principle states that customers are served one at a time and that the customer that has been waiting the longest is served first Template:Fn.
• Last In First Out – This principle also serves customers one at a time, however the customer with the shortest waiting time will be served first Template:Fn.
• Processor Sharing – Customers are served equally. Network capacity is shared between customers and they all effectively experience the same delay Template:Fn.

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

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

Classic queueing theory involves complex calculations to determine call waiting time, service time, server utilisation and many other metrics which are used to measure queueing performance Template:Fn,Template:Fn.

Queueing Networks

Queues can be chained to form queueing networks where the departures from one queue enter the next queue. Queueing networks can be classified into two catagories: open queueing networks and closed queueing networks. Open queueing networks have an external input and an external final destination. Closed queueing networks are completely contained and the customers circulate continually never leaving the network.

Limitations of the mathematical approach

Classic queueing is too mathematically restrictive to be able to model all real-world situations. This restriction arises because the underlying assumptions of the theory do not always hold in the real world. Alternative means of analysis have been devised in order to provide some insight into problems which do not fall under the scope of queueing theory, though they are often scenario-specific since they generally consist of computer simulations and/or of analysis of experimental data. See network traffic simulation. Thanks to all participants.

References

• Template:Fnb Flood, J.E. Telecommunications Switching, Traffic and Networks, Chapter 4: Telecommunications Traffic, New York: Prentice-Hall, 1998.

• Template:Fnb Bose S.J., Chapter 1 - An Introduction to Queueing Systems, Kluwer/Plenum Publishers, 2002.

• Template:Fnb Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory, .

• Template:Fnb Tijms, H.C, Algorithmic Analysis of Queues", Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003.

See also

• Little's law
• Queueing delay
• Queue area
• Random early detection (RED)
• Erlang unit
• Jackson Network

External links

• Myron Hlynka's Queueing Theory Page
• Queueing Theory Basics
• Spreadsheet-based software to solve queueing models
• Spelling of queueing/queuing

• Stochastic processes
• Production and manufacturing
• Services management and marketing
• Operations research