Kendall's notation


In queueing theory, a discipline within the mathematical theory of probability, Kendall's 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 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.
When the final three parameters are not specified, it is assumed K = ∞, N = ∞ and D = FIFO.

A: The arrival process

A code describing the arrival process. The codes used are:
SymbolNameDescriptionExamples
MMarkovian or memorylessPoisson process arrival process.M/M/1 queue
MXbatch MarkovPoisson process with a random variable X for the number of arrivals at one time.MX/MY/1 queue
MAPMarkovian arrival processGeneralisation of the Poisson process.
BMAPBatch Markovian arrival processGeneralisation of the MAP with multiple arrivals
MMPPMarkov modulated poisson processPoisson process where arrivals are in "clusters".
DDegenerate distributionA deterministic or fixed inter-arrival time.D/M/1 queue
EkErlang distributionAn Erlang distribution with k as the shape parameter.
GGeneral distributionAlthough G usually refers to independent arrivals, some authors prefer to use GI to be explicit.
PHPhase-type distributionSome 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
MMarkovian or memorylessExponential service time.M/M/1 queue
MYbulk MarkovExponential service time with a random variable Y for the size of the batch of entities serviced at one time.MX/MY/1 queue
DDegenerate distributionA deterministic or fixed service time.M/D/1 queue
EkErlang distributionAn Erlang distribution with k as the shape parameter.
GGeneral distributionAlthough G usually refers to independent service time, some authors prefer to use GI to be explicit.M/G/1 queue
PHPhase-type distributionSome of the above distributions are special cases of the phase-type, often used in place of a general distribution.
MMPPMarkov modulated poisson processExponential service time distributions, where the rate parameter is controlled by a Markov chain.

''c'': The number of servers

The number of service channels. 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.

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 jobs queue up, there are fewer left 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.
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 serviceThere are several options: Preemptive Priority Queuing, Non Preemptive Queuing, Class Based Weighted Fair Queuing, Weighted Fair Queuing.
PSProcessor Sharing