A
queue or
queueing node can be thought of as nearly a
black box.
Jobs (also called
customers or
requests, depending on the field) arrive to the queue, possibly wait some time, take some time being processed, and then depart from the queue. However, the queueing node is not quite a pure black box since some information is needed about the inside of the queueing node. The queue has one or more
servers which can each be paired with an arriving job. When the job is completed and departs, that server will again be free to be paired with another arriving job. An analogy often used is that of the cashier at a supermarket. Customers arrive, are processed by the cashier, and depart. Each cashier processes one customer at a time, and hence this is a queueing node with only one server. A setting where a customer will leave immediately if the cashier is busy when the customer arrives, is referred to as a queue with no
buffer (or no
waiting area). A setting with a waiting zone for up to
n customers is called a queue with a buffer of size
n.
Birth-death process The behaviour of a single queue (also called a
queueing node) can be described by a
birth–death process, which describes the arrivals and departures from the queue, along with the number of jobs currently in the system. If
k denotes the number of jobs in the system (either being serviced or waiting if the queue has a buffer of waiting jobs), then an arrival increases
k by 1 and a departure decreases
k by 1. The system transitions between values of
k by
births and
deaths, which occur at the arrival rates \lambda_i and the departure rates \mu_i for each job i. For a queue, these rates are generally considered not to vary with the number of jobs in the queue, so a single
average rate of arrivals/departures per unit time is assumed. Under this assumption, this process has an arrival rate of \lambda = \text{avg}(\lambda_1,\lambda_2,\dots,\lambda_k) and a departure rate of \mu = \text{avg}(\mu_1, \mu_2, \dots, \mu_k).
Balance equations The
steady state equations for the birth-and-death process, known as the
balance equations, are as follows. Here P_n denotes the steady state probability to be in state
n. : \mu_1 P_1 = \lambda_0 P_0 : \lambda_0 P_0 + \mu_2 P_2 = (\lambda_1 + \mu_1) P_1 : \lambda_{n-1} P_{n-1} + \mu_{n+1} P_{n+1} = (\lambda_n + \mu_n) P_n The first two equations imply : P_1 = \frac{\lambda_0}{\mu_1} P_0 and : P_2 = \frac{\lambda_1}{\mu_2} P_1 + \frac{1}{\mu_2} (\mu_1 P_1 - \lambda_0 P_0) = \frac{\lambda_1}{\mu_2} P_1 = \frac{\lambda_1 \lambda_0}{\mu_2 \mu_1} P_0. By mathematical induction, : P_n = \frac{\lambda_{n-1} \lambda_{n-2} \cdots \lambda_0}{\mu_n \mu_{n-1} \cdots \mu_1} P_0 = P_0 \prod_{i = 0}^{n-1} \frac{\lambda_i}{\mu_{i+1}}. The condition \sum_{n = 0}^{\infty} P_n = P_0 + P_0 \sum_{n=1}^\infty \prod_{i=0}^{n-1} \frac{\lambda_i}{\mu_{i+1}} = 1 leads to : P_0 = \frac{1}{1 + \sum_{n=1}^{\infty}\prod_{i=0}^{n-1} \frac{\lambda_i}{\mu_{i+1}} } which, together with the equation for P_n (n\geq1), fully describes the required steady state probabilities.
Kendall's notation Single queueing nodes are usually described using Kendall's notation in the form A/S/
c where
A describes the distribution of durations between each arrival to the queue,
S the distribution of service times for jobs, and
c the number of servers at the node. For an example of the notation, the
M/M/1 queue is a simple model where a single server serves jobs that arrive according to a
Poisson process (where inter-arrival durations are
exponentially distributed) and have exponentially distributed service times (the M denotes a
Markov process). In an
M/G/1 queue, the G stands for
general and indicates an arbitrary
probability distribution for service times.
Example analysis of an M/M/1 queue Consider a queue with one server and the following characteristics: •
\lambda: the arrival rate (the reciprocal of the expected time between each customer arriving, e.g. 10 customers per second) •
\mu: the reciprocal of the mean service time (the expected number of consecutive service completions per the same unit time, e.g. per 30 seconds) •
n: the parameter characterizing the number of customers in the system • P_n: the probability of there being
n customers in the system in steady state Further, let E_n represent the number of times the system enters state
n, and L_n represent the number of times the system leaves state
n. Then \left\vert E_n - L_n \right\vert \in \{0, 1\} for all
n. That is, the number of times the system leaves a state differs by at most 1 from the number of times it enters that state, since it will either return into that state at some time in the future (E_n = L_n) or not (\left\vert E_n - L_n \right\vert = 1). When the system arrives at a steady state, the arrival rate should be equal to the departure rate. Thus the balance equations : \mu P_1 = \lambda P_0 : \lambda P_0 + \mu P_2 = (\lambda + \mu) P_1 : \lambda P_{n-1} + \mu P_{n+1} = (\lambda + \mu) P_n imply : P_n = \frac{\lambda}{\mu} P_{n-1},\ n=1,2,\ldots The fact that P_0 + P_1 + \cdots = 1 leads to the
geometric distribution formula : P_n = (1 - \rho) \rho^n where \rho = \frac{\lambda}{\mu} .
Simple two-equation queue A common basic queueing system is attributed to
Erlang and is a modification of
Little's Law. Given an arrival rate
λ, a dropout rate
σ, and a departure rate
μ, length of the queue
L is defined as: : L = \frac{\lambda - \sigma}{\mu}. Assuming an exponential distribution for the rates, the waiting time
W can be defined as the proportion of arrivals that are served. This is equal to the exponential survival rate of those who do not drop out over the waiting period, giving: : \frac{\mu}{\lambda} = e^{-W{\mu}} The second equation is commonly rewritten as: : W = \frac{1}{\mu} \mathrm{ln}\frac{\lambda}{\mu} The two-stage one-box model is common in
epidemiology. ==History==