FACTOID # 7: The top five best educated states are all in the Northeast.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Queueing theory

Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues).


The theory enables mathematical analysis of several related processes, including arriving at the (back of the) queue, waiting in the queue (essentially a storage process), and being served by the server(s) at the front of the queue. The theory permits the derivation and calculation of several performance measures including the average waiting time in the queue or the system, the expected number waiting or receiving service and the probability of encountering the system in certain states, such as empty, full, having an available server or having to wait a certain time to be served.


Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide service. It is applicable in a wide variety of situations that may be encountered in business, commerce, industry, public service and engineering. Applications are frequently encountered in customer service situations as well as transport and telecommunication (note that something called ride theory is sometimes mentioned, but it is uncertain whether it is a valid theory or a hoax). 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. Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima (profit, faster assembly line, greater crop yield, higher bandwidth, etc) or minima... // (also known as Client Service) is the provision of service to customers before, during and after a purchase. ... Copy of the original phone of Alexander Graham Bell at the Musée des Arts et Métiers in Paris Telecommunication is the assisted transmission of signals over a distance for the purpose of communication. ... Ride theory is the sociological study of transportation systems, with a particular emphasis on amusement parks and carnival rides. ... The Intelligent Transportation Systems (ITS) program is a worldwide initiative to add information and communications technology to transport infrastructure and vehicles. ... A call centre (Commonwealth English) or call center (AmE) is a centralized office of a company that answers incoming telephone calls from customers(often for the purposes of product support) , or that makes outgoing telephone calls to customers (telemarketing). ... PBX redirects here. ... A telecommunications network is a network of telecommunications links arranged so that messages may be passed from one part of the network to another over multiple links. ... Copy of the original phone of Alexander Graham Bell at the Musée des Arts et Métiers in Paris Telecommunication is the assisted transmission of signals over a distance for the purpose of communication. ... In information technology, a server is an application or device that performs services for connected clients as part of a client-server architecture. ... For other uses, see Mainframe. ... This article is about the machine. ... The mathematical study of traffic flow, and in particular vehicular traffic flow, is done with the aim to get a better understanding of these phenomena and to assist in prevention of traffic congestion problems. ...

Contents

Spelling

The word queue comes, via French, from the Latin cauda, meaning tail. Most researchers in the field prefer the spelling 'queueing' over 'queuing',[1] although the latter is somewhat more common in other contexts. Latin was the language originally spoken in the region around Rome called Latium. ...


History

Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on queueing theory in 1909. Agner Krarup Erlang (January 1, 1878–February 3, 1929) was a Danish mathematician, statistician, and engineer who invented the fields of queueing theory and traffic engineering. ... Year 1909 (MCMIX) was a common year starting on Friday (link will display full calendar) of the Gregorian calendar (or a common year starting on Thursday of the 13-day-slower Julian calendar). ...


David G. Kendall introduced an A/B/C queueing notation in 1953. David George Kendall (born January 15, 1918) is a British mathematician and statistician. ... January 7 - President Harry S. Truman announces the United States has developed a hydrogen bomb. ...


Notation

Notation for describing the characteristics of a queueing model was first suggested by David G. Kendall in 1953. Kendall's notation introduced an A/B/C queueing notation that can be found in all standard modern works on queueing theory, for example, Tijms.[2] The A/B/C notation designates a queuing system having A as interarrival time distribution, B as service time distribution, and C as number of servers. So, for instance, G/D/1 would indicate a General (may be anything) arrival process, a Deterministic (constant time) service process and a single server. More details on this notation are given in the article about queueing models. Queueing Models can be represented using Kendalls notation: A/B/S/K/N/Disc Where : A : Interarrival Time Distribution B : Service Time Distribution S : Number of Servers K : System Capacity N : Calling Population Disc : Service Discipline Some standand value of the notation: M  := Markovian (exponential distribution) Eκ := Erlang distribution... David George Kendall (born January 15, 1918) is a British mathematician and statistician. ... January 7 - President Harry S. Truman announces the United States has developed a hydrogen bomb. ... In queueing theory, Kendalls notation (or sometimes Kendall notation) is the standard system used to describe and classify the queueing model that a queueing system corresponds to. ... Queueing Models can be represented using Kendalls notation: A/B/S/K/N/Disc Where : A : Interarrival Time Distribution B : Service Time Distribution S : Number of Servers K : System Capacity N : Calling Population Disc : Service Discipline Some standand value of the notation: M  := Markovian (exponential distribution) Eκ := Erlang distribution...


Application 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.[3] 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.[3] The public switched telephone network (PSTN) is the concatenation of the worlds public circuit-switched telephone networks, in much the same way that the Internet is the concatenation of the worlds public IP-based packet-switched networks. ... This article is one of a group being considered for deletion in accordance with Wikipedias deletion policy. ... // Introduction In telecommunication, the quality of voice service is specified by two measures: The GOS (grade of service) and the QoS (quality of service). ... In the context of the public switched telephone network, routing is the process by which telephone calls are routed around the telephone network. ...


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.[4] 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.[4] 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.[4][5] 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.[5]
  • 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.[5]
  • Processor Sharing – Customers are served equally. Network capacity is shared between customers and they all effectively experience the same delay.[5]

Queueing is handled by control processes within exchanges, which can be modelled using state equations.[4][5] Queueing systems use a particular form of state equations known as Markov chains which model the system in each state.[4] Incoming traffic to these systems is modelled via a Poisson distribution and is subject to Erlang’s queueing theory assumptions viz.[3] Wikipedia does not have an article with this exact name. ... In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate, and are independent of the time since the last event. ...

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

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.[4][5]


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 categories: 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.


Role of Poisson process, exponential distributions

A useful queueing model both (a) represents a real-life system with sufficient accuracy and (b) is analytically tractable. A queuing model based on the Poisson process and its companion exponential probability distribution often meets these two requirements. A Poisson process models random events (such as a customer arrival, a request for action from a web server, or the completion of the actions requested of a web server) as emanating from a memoryless process. That is, the length of the time interval from the current time to the occurrence of the next event does not depend upon the time of occurrence of the last event. In the Poisson probability distribution, the observer records the number of events that occur in a time interval of fixed length. In the (negative) exponential probability distribution, the observer records the length of the time interval between consecutive events. In both, the underlying physical process is memoryless.


Models based on the Poisson process often respond to inputs from the environment in a manner that mimics the response of the system being modeled to those same inputs. The analytically tractable models that result yield both information about the system being modeled and the form of their solution. Even a queuing model based on the Poisson process that does a relatively poor job of mimicking detailed system performance can be useful. The fact that such models often give "worst-case" scenario evaluations appeals to system designers who prefer to include a safety factor in their designs. Also, the form of the solution of models based on the Poisson process often provides insight into the form of the solution to a queuing problem whose detailed behavior is poorly mimicked. As a result, queuing models are frequently modeled as Poisson processes through the use of the exponential distribution. In queueing theory, a queueing model is used to approximate a real queueing situation or system, so the queueing behaviour can be analysed mathematically. ... It has been suggested that this article be split into multiple articles. ... In probability theory and statistics, the exponential distributions are a class of continuous probability distribution. ...


Limitations of mathematical approach

Classic queueing theory is often too mathematically restrictive to be able to model all real-world situations exactly. This restriction arises because the underlying assumptions of the theory do not always hold in the real world.


For example; the mathematical models often assume infinite numbers of customers, or queue capacity, or no bounds on inter-arrival or service times, when it is quite apparent that these bounds must exist in reality. Often, although the bounds do exist, they can be safely ignored because the differences between the real-world and theory is not statistically significant, as the probability that such boundary situations might occur is remote compared to the expected normal situation. In other cases the theoretical solution may either prove intractable or insufficiently informative to be useful.


Alternative means of analysis have thus been devised in order to provide some insight into problems which do not fall under the mathematical 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. This article is about the general term. ... This article may be too technical for most readers to understand. ...


See also

Buzens algorithm is an algorithm related to queueing theory used to calculate the normalization constant for a closed Jackson network. ... The dimensionless unit named the Erlang is a statistical measure of telecommunications traffic used in telephony. ... Jackson Network is named after James R. Jackson, it is the first significant development in the theory of networks of queues, in which each node of the queueing network can be analyzed separately. ... In queueing theory, Littles result, theorem, or law says: The average number of customers in a stable system (over some time interval) is equal to their average arrival rate, multiplied by their average time in the system. ... In queuing theory, Markovian arrival processes are used to model the arrival customers to queue. ... Queue at US Air Force station in Iraq, for food at a birthday celebration. Queue areas are areas in which people queue (first-come, first-served), that is they wait in line for something. ... In computer engineering, a queueing delay is the time a job waits in a queue until it can be executed. ... Queueing Models can be represented using Kendalls notation: A/B/S/K/N/Disc Where : A : Interarrival Time Distribution B : Service Time Distribution S : Number of Servers K : System Capacity N : Calling Population Disc : Service Discipline Some standand value of the notation: M  := Markovian (exponential distribution) Eκ := Erlang distribution... Random early detection (RED) is a queue management algorithm. ... Renewal theory is a branch of probability theory with an interesting and varied range of applications. ... In communication networks, throughput is the amount of digital data per time unit that is delivered over a physical or logical link, or that is passing through a certain network node. ...

References

  1. ^ Spelling of queueing/queuing
  2. ^ Tijms, H.C, Algorithmic Analysis of Queues", Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003
  3. ^ a b c d e f g Flood, J.E. Telecommunications Switching, Traffic and Networks, Chapter 4: Telecommunications Traffic, New York: Prentice-Hall, 1998.
  4. ^ a b c d e f Bose S.J., Chapter 1 - An Introduction to Queueing Systems, Kluwer/Plenum Publishers, 2002.
  5. ^ a b c d e f Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory.

Further reading

  • Gross, Donald; Carl M. Harris (1998). Fundamentals of Queueing Theory. Wiley. 
  • Deitel, Harvey M. [1982] (1984). An introduction to operating systems, revisited first edition, Addison-Wesley, 673. ISBN 0-201-14502-2.  chap.15, pp.380-412

External links


  Results from FactBites:
 
Queueing theory - Wikipedia, the free encyclopedia (998 words)
Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues).
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.
For queueing theory, it is most convenient to work with probability distributions which exhibit the memoryless property, as it vastly simplifies the mathematics involved.
NationMaster - Encyclopedia: Queueing theory (1867 words)
In probability theory, memorylessness is a property of certain probability distributions: the exponential distributions and the geometric distributions.
In queueing theory, Littles result, theorem, or law says: The average number of customers in a stable system (over some time interval) is equal to their average arrival rate, multiplied by their average time in the system.
Queue areas are areas in which people queue (first-come, first-served), that is they wait in line for something.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m