Kendall's notation

Last updated
Waiting queue at Ottawa Station. Waiting in line at Ottawa Station.jpg
Waiting queue at Ottawa Station.

In queueing theory, a discipline within the mathematical theory of probability, Kendall's notation (or sometimes Kendall notation) is the standard system used to describe and classify a queueing node. D. G. Kendall proposed describing queueing models using three factors written A/S/c in 1953 [1] where A denotes the time between arrivals to the queue, S the service time distribution and c the number of service channels open at the node. It has since been extended to A/S/c/K/N/D where K is the capacity of the queue, N is the size of the population of jobs to be served, and D is the queueing discipline. [2] [3] [4]

Contents

When the final three parameters are not specified (e.g. M/M/1 queue), it is assumed K = ∞, N = ∞ and D =  FIFO. [5]

First example: M/M/1 queue

An M/M/1 queueing node. Mm1 queue.svg
An M/M/1 queueing node.

A M/M/1 queue means that the time between arrivals is Markovian (M), i.e. the inter-arrival time follows an exponential distribution of parameter λ. The second M means that the service time is Markovian: it follows an exponential distribution of parameter μ. The last parameter is the number of service channel which one (1).

Description of the parameters

In this section, we describe the parameters A/S/c/K/N/D from left to right.

A: The arrival process

A code describing the arrival process. The codes used are:

SymbolNameDescriptionExamples
M Markovian or memoryless [6] Poisson process (or random) arrival process (i.e., exponential inter-arrival times). M/M/1 queue
MXbatch Markov Poisson process with a random variable X for the number of arrivals at one time. MX/MY/1 queue
MAP Markovian arrival process Generalisation of the Poisson process.
BMAP Batch Markovian arrival process Generalisation of the MAP with multiple arrivals
MMPP Markov modulated poisson process Poisson process where arrivals are in "clusters".
D Degenerate distribution A deterministic or fixed inter-arrival time. D/M/1 queue
Ek Erlang distribution An Erlang distribution with k as the shape parameter (i.e., sum of k i.i.d. exponential random variables).
GGeneral distributionAlthough G usually refers to independent arrivals, some authors prefer to use GI to be explicit.
PH Phase-type distribution Some of the above distributions are special cases of the phase-type, often used in place of a general distribution.

S: The service time distribution

This gives the distribution of time of the service of a customer. Some common notations are:

SymbolNameDescriptionExamples
M Markovian or memoryless [6] Exponential service time. M/M/1 queue
MYbulk Markov Exponential service time with a random variable Y for the size of the batch of entities serviced at one time. MX/MY/1 queue
D Degenerate distribution A deterministic or fixed service time. M/D/1 queue
Ek Erlang distribution An Erlang distribution with k as the shape parameter (i.e., sum of k i.i.d. exponential random variables).
GGeneral distributionAlthough G usually refers to independent service time, some authors prefer to use GI to be explicit. M/G/1 queue
PH Phase-type distribution Some of the above distributions are special cases of the phase-type, often used in place of a general distribution.
MMPP Markov modulated poisson process Exponential service time distributions, where the rate parameter is controlled by a Markov chain. [7]

c: The number of servers

The number of service channels (or servers). The M/M/1 queue has a single server and the M/M/c queue c servers.

K: The number of places in the queue

The capacity of queue, or the maximum number of customers allowed in the queue. When the number is at this maximum, further arrivals are turned away. If this number is omitted, the capacity is assumed to be unlimited, or infinite.

Note: This is sometimes denoted c + K where K is the buffer size, the number of places in the queue above the number of servers c.

N: The calling population

The size of calling source. The size of the population from which the customers come. A small population will significantly affect the effective arrival rate, because, as more customers are in system, there are fewer free customers available to arrive into the system. If this number is omitted, the population is assumed to be unlimited, or infinite.

D: The queue's discipline

The Service Discipline or Priority order that jobs in the queue, or waiting line, are served:

SymbolNameDescription
FIFO/FCFSFirst In First Out/First Come First ServedThe customers are served in the order they arrived in (used by default).
LIFO/LCFSLast in First Out/Last Come First ServedThe customers are served in the reverse order to the order they arrived in.
SIROService In Random OrderThe customers are served in a random order with no regard to arrival order.
PQPriority QueuingThere are several options: Preemptive Priority Queuing, Non Preemptive Queuing, Class Based Weighted Fair Queuing, Weighted Fair Queuing.
PSProcessor SharingThe customers are served in the determine order with no regard of arrival order.
Note: An alternative notation practice is to record the queue discipline before the population and system capacity, with or without enclosing parenthesis. This does not normally cause confusion because the notation is different.

Related Research Articles

The erlang is a dimensionless unit that is used in telephony as a measure of offered load or carried load on service-providing elements such as telephone circuits or telephone switching equipment. A single cord circuit has the capacity to be used for 60 minutes in one hour. Full utilization of that capacity, 60 minutes of traffic, constitutes 1 erlang.

<span class="mw-page-title-main">Queueing theory</span> Mathematical study of waiting lines, or queues

Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. 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 a service.

In mathematical queueing theory, Little's result, theorem, lemma, law, or formula is a theorem by John Little which states that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is

In probability theory, the Lindley equation, Lindley recursion or Lindley processes is a discrete-time stochastic process An where n takes integer values and:

In queueing theory, a discipline within the mathematical theory of probability, a Markovian arrival process is a mathematical model for the time between job arrivals to a system. The simplest such process is a Poisson process where the time between each arrival is exponentially distributed.

<span class="mw-page-title-main">M/M/1 queue</span> Queue with Markov (Poisson) arrival process, exponential service time distribution and one server

In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The model name is written in Kendall's notation. The model is the most elementary of queueing models and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. An extension of this model with more than one server is the M/M/c queue.

In queueing theory, a discipline within the mathematical theory of probability, Burke's theorem is a theorem asserting that, for the M/M/1 queue, M/M/c queue or M/M/∞ queue in the steady state with arrivals is a Poisson process with rate parameter λ:

  1. The departure process is a Poisson process with rate parameter λ.
  2. At time t the number of customers in the queue is independent of the departure process prior to time t.

In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem states that "upon arrival at a station, a job observes the system as if in steady state at an arbitrary instant for the system without that job."

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers, and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

In probability theory, uniformization method, is a method to compute transient solutions of finite state continuous-time Markov chains, by approximating the process by a discrete-time Markov chain. The original chain is scaled by the fastest transition rate γ, so that transitions occur at the same rate in every state, hence the name. The method is simple to program and efficiently calculates an approximation to the transient distribution at a single point in time. The method was first introduced by Winfried Grassmann in 1977.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian, service times have a General distribution and there is a single server. The model name is written in Kendall's notation, and is an extension of the M/M/1 queue, where service times must be exponentially distributed. The classic application of the M/G/1 queue is to model performance of a fixed head hard disk.

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian, service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem.

In queueing theory, a discipline within the mathematical theory of probability, a bulk queue is a general queueing model where jobs arrive in and/or are served in groups of random size. Batch arrivals have been used to describe large deliveries and batch services to model a hospital out-patient department holding a clinic once a week, a transport link with fixed capacity and an elevator.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/∞ queue is a multi-server queueing model where every arrival experiences immediate service and does not wait. In Kendall's notation it describes a system where arrivals are governed by a Poisson process, there are infinitely many servers, so jobs do not need to wait for a server. Each job has an exponentially distributed service time. It is a limit of the M/M/c queue model where the number of servers c becomes very large.

In queueing theory, a discipline within the mathematical theory of probability, an M/D/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation. Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory. An extension of this model with more than one server is the M/D/c queue.

In queueing theory, a discipline within the mathematical theory of probability, a D/M/1 queue represents the queue length in a system having a single server, where arrivals occur at fixed regular intervals and job service requirements are random with an exponential distribution. The model name is written in Kendall's notation. Agner Krarup Erlang first published a solution to the stationary distribution of a D/M/1 and D/M/k queue, the model with k servers, in 1917 and 1920.

In queueing theory, a discipline within the mathematical theory of probability, the G/G/1 queue represents the queue length in a system with a single server where interarrival times have a general distribution and service times have a (different) general distribution. The evolution of the queue can be described by the Lindley equation.

In queueing theory, a discipline within the mathematical theory of probability, an M/D/c queue represents the queue length in a system having c servers, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation. Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory. The model is an extension of the M/D/1 queue which has only a single server.

In queueing theory, a discipline within the mathematical theory of probability, the G/M/1 queue represents the queue length in a system where interarrival times have a general distribution and service times for each job have an exponential distribution. The system is described in Kendall's notation where the G denotes a general distribution, M the exponential distribution for service times and the 1 that the model has a single server.

References

  1. ↑ Kendall, D. G. (1953). "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain". The Annals of Mathematical Statistics. 24 (3): 338–354. doi: 10.1214/aoms/1177728975 . JSTOR   2236285.
  2. ↑ Lee, Alec Miller (1966). "A Problem of Standards of Service (Chapter 15)". Applied Queueing Theory. New York: MacMillan. ISBN   0-333-04079-1.
  3. ↑ Taha, Hamdy A. (1968). Operations research: an introduction (Preliminary ed.).
  4. ↑ Sen, Rathindra P. (2010). Operations Research: Algorithms And Applications. Prentice-Hall of India. p. 518. ISBN   978-81-203-3930-9.
  5. ↑ Gautam, N. (2007). "Queueing Theory". Operations Research and Management Science Handbook. Operations Research Series. Vol. 20073432. pp. 1–2. doi:10.1201/9781420009712.ch9. ISBN   978-0-8493-9721-9.
  6. 1 2 Zonderland, M. E.; Boucherie, R. J. (2012). "Queuing Networks in Health Care Systems". Handbook of Healthcare System Scheduling. International Series in Operations Research & Management Science. Vol. 168. p. 201. doi:10.1007/978-1-4614-1734-7_9. ISBN   978-1-4614-1733-0.
  7. ↑ Zhou, Yong-Ping; Gans, Noah (October 1999). "#99-40-B: A Single-Server Queue with Markov Modulated Service Times". Financial Institutions Center, Wharton, UPenn. Archived from the original on 2010-06-21. Retrieved 2011-01-11.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.