Short note: Queuing theory in delay system

A delay system (queueing system or lost-calls-delayed system) is one in which a call that finds all servers busy is not lost but waits in a queue until a server becomes free. Queueing theory gives the probability of waiting, the mean waiting time and the queue length. Examples: calls waiting for a register (dial tone delay), messages in a store-and-forward data network, callers held at a call centre, jobs waiting for an SPC processor.

Elements of a queueing system

 arrivals     queue (buffer)      n servers
 --lambda-->  [ | | | | ]  --->  [S1]
                                 [S2]  ---> departures
                                 [..]
                                 [Sn]

1. Arrival process: usually Poisson with rate $\lambda$.
2. Service time distribution: usually exponential with mean $h = 1/\mu$.
3. Number of servers $n$.
4. Queue capacity: infinite or finite.
5. Queue discipline: FIFO, LIFO, random, priority.
6. Number of sources: infinite or finite.

Kendall's notation A/B/n/K/N/D: arrival distribution / service distribution / servers / capacity / sources / discipline. Example: M/M/1, M/M/n, M/D/1 (M = Markov/exponential, D = deterministic, G = general).

Main results

Little's law (holds for any queue):

$$L = \lambda W, \qquad L_q = \lambda W_q$$

M/M/1 queue ($\rho = \lambda/\mu < 1$):

$$\begin{aligned} P(k) &= (1-\rho)\rho^k \\ L &= \frac{\rho}{1-\rho}, \quad L_q = \frac{\rho^2}{1-\rho} \\ W &= \frac{1}{\mu-\lambda}, \quad W_q = \frac{\rho}{\mu-\lambda} \end{aligned}$$

M/M/n queue (Erlang C formula). With $A = \lambda h$ erlang offered to $n$ servers ($A < n$), the probability that a call has to wait is

$$C(n,A) = \frac{\frac{A^n}{n!}\frac{n}{n-A}}{\sum_{k=0}^{n-1}\frac{A^k}{k!} + \frac{A^n}{n!}\frac{n}{n-A}}$$

Mean waiting time of all calls and of delayed calls:

$$W_q = \frac{C(n,A)\,h}{n-A}, \qquad W_{d} = \frac{h}{n-A}$$

Probability of waiting longer than $t$:

$$P(W > t) = C(n,A)\,e^{-(n-A)t/h}$$

Grade of service in delay systems

The GoS is stated as the probability of delay, or the probability of waiting more than a given time, e.g. "dial tone within 3 s for 99% of calls". Delay systems give higher server utilisation than loss systems, but need $A < n$ for stability; as $\rho \to 1$ the waiting time grows very rapidly.

Example

An M/M/1 server with $\lambda = 8$/min and $\mu = 10$/min has $\rho = 0.8$, $L = 4$, $W = 1/(10-8) = 0.5$ min and $W_q = 0.4$ min.