Multi-server and finite-capacity queues

Section of Birth–death chains and queues, part of Stochastic processes

Type	Section
Taught in	Birth–death chains and queues
Part	Stochastic processes

With c parallel servers and one shared queue, the departure rate is \mu_n=\min(n,c)\mu, and the birth rate stays \lambda. Up through state c-1 each new customer adds a server, so the product is the same Poisson-style ratio (\lambda/\mu)^n/n! that appears for M/M/∞. From n\ge c every further step multiplies the weight by \lambda/(c\mu) and by nothing else, a geometric ratio. The geometric tail sums if and only if \lambda<c\mu. A stationary probability exists precisely in that case. The normalising constant adds the finite sum up to c-1 to the closed form of the tail:

\pi_0^{-1}=\sum_{n=0}^{c-1}\frac{(\lambda/\mu)^n}{n!}+\frac{(\lambda/\mu)^c}{c!}\cdot\frac{1}{1-\lambda/(c\mu)}.

The first sum covers the states in which at least one server is idle. The second term sums the geometric tail from c onward.

An M/M/c/K system stops at state K. An arrival that finds K customers present is blocked and does not enter. The state space is finite and irreducible for \lambda>0 and \mu>0, so a stationary distribution exists for every positive load, including \lambda\ge c\mu. The chain cannot drift to infinity because the state cannot pass K. The cost is lost arrivals. Throughput, the long-run rate of accepted arrivals, is \lambda(1-\pi_K), not the offered rate \lambda.

For the single-server finite system M/M/1/K with \rho\neq 1,

\pi_n=\frac{(1-\rho)\rho^n}{1-\rho^{K+1}}, \qquad 0\le n\le K.

At \rho=1 the weights are constant and \pi_n=1/(K+1). Blocking probability \pi_K increases with \rho. The stationary law exists on both sides of \rho=1 because the room is finite.

Used in

Taught in Birth–death chains and queues
All 3 questions on Birth–death chains and queues

Used in

See also