Why more than one server
The unit on a stationary single-server queue derived the occupancy distribution of the M/M/1 system. Real service systems often have several identical servers, and a central design question is how delay depends on the number of servers. This unit extends the birth-and-death balance argument of the M/M/1 unit to servers and adds Little's law, which converts between the average number of customers and the average time spent. The same hypotheses are used as before: exponential interarrival and service times, no abandonment and unlimited waiting room.
Model and definitions
Definition 8.8.1
()
Customers arrive according to a Poisson process of rate . There are identical servers; each service time is exponential with rate and all variables are independent. Customers are served first come, first served, and an arriving customer waits if all servers are busy. Let be the number of customers present, waiting or in service. Then is a continuous-time birth-and-death chain with birth rate from every state and death rate from state , because only servers are busy.
Definition 8.8.2
(Offered load, utilization and performance measures)
The offered load is , the mean number of servers that would be busy if they were unlimited, and the utilization is . Let denote the stationary probability of customers, the mean number in the system, the mean number waiting, and , the mean time in the system and in the queue for an arriving customer.
Main results
Theorem 8.8.3
(Stationary distribution of the M/M/c queue)
A stationary distribution exists if and only if . In that case
Proof
(Cut equations and normalization)
In a stationary birth-and-death chain the probability flow across the cut between and is the same in both directions: . Hence . For the product is . For each additional factor is , giving .
These weights are summable exactly when converges, that is ; then is the reciprocal of their sum, which is the stated formula, and the cut equations imply the balance equations. If the weights are not summable and no stationary distribution exists.
Theorem 8.8.4
(Erlang C waiting probability and mean queue length)
If , the probability that an arrival must wait is the Erlang C quantity
and the mean queue length is
Proof
(Tail sums and arrivals that see time averages)
The first formula sums the geometric tail of the stationary distribution: . The Poisson arrival stream sees the system in its stationary distribution (the PASTA property), so an arrival waits exactly when , with probability . For , put :
using .
Proof X-ray
Two different averages behind the Erlang C formula
The proof contains two quantities that look alike but are averaged differently. The sum of over is a time average: the fraction of time all servers are busy. The waiting probability is a customer average: the fraction of arrivals who find all servers busy. The only step that identifies them is the PASTA property, and it is the one place where Poisson arrivals are used beyond the birth-and-death structure. The queue-length formula, by contrast, is a time average throughout and needs no such step; it is pure algebra on the geometric tail, which exists because .
Theorem 8.8.5
(Little's law)
Suppose a system is in a stationary regime in which customers enter at long-run rate and the long-run averages exist. If is the time-average number of customers in the system and the average time a customer spends in it, then . The same relation holds for the waiting line alone, .
Proof
(The area argument, as a sketch)
Over a long horizon , the integral equals the sum, over customers, of the time each spends in the system, up to boundary terms that are negligible relative to . If about customers enter, the sum is about . Dividing by gives . The argument applies to any collection of customers and any subsystem, in particular the queue. Controlling the boundary terms rigorously is deferred.
Because a customer spends mean time in service, , and Little's law applied to the servers gives . For the formulas reduce to the M/M/1 results: , and .
Worked examples
Worked example 8.8.6
(Two servers)
Let , and per hour. Then and . The normalizing constant is , so . Then and for ; check: . The waiting probability is . Then
As a check, .
Worked example 8.8.7
(Pooled servers versus separate queues)
Compare the two-server system above with two separate single-server queues, each receiving half the arrivals: , , . Each has and, by Little's law, hours, against hours for the pooled system with the same total capacity. In the separate system a customer can wait while the other server is idle; pooling removes that possibility.
Worked example 8.8.8
(Adding a third server)
With , and : , and . Then , so . Thus , , hour, hour and . The check holds. The third server cuts the mean wait from hour to hour.
Common mistakes and subtle points
Common mistake
(Testing stability with instead of )
With and the offered load is , yet the two-server system is stable because . Conversely is exactly the stability condition; is sufficient but not necessary when .
Common mistake
(Mixing up and )
also counts customers in service, and in the M/M/c queue. In the two-server example but ; dividing the wrong one by gives in place of .
Common mistake
(Using the offered arrival rate in Little's law when customers are turned away)
Little's law uses the rate of customers who actually enter the system. If a fraction of arrivals is blocked, must be replaced by the entering rate; using the offered rate understates .
Counterexample mode
Arrivals need not see time averages without Poisson input
Claim: in any stable single-server queue, the probability that an arrival must wait equals the fraction of time the server is busy. Take deterministic arrivals at times 0, 1, 2, and so on, with every service lasting half an hour. The server is busy half of the time, but each customer leaves half an hour before the next arrives, so no arrival ever waits. The waiting probability is , not . The Erlang C identification needs Poisson arrivals, which see the stationary distribution.
The stationary distribution and the Erlang C formula depend on exponential services; Little's law does not. The comparison with separate queues holds for the same total arrival rate and identical servers, and compares means only.
Exercises
Exercise 8.8.9
(For , and per hour, compute , , and .)
Foundation
Solution(3)
- 1
Compute the loads and
and . Then , so .
- 2
Apply the Erlang C formulas
and .
- 3
Convert by Little's law
hour, hour and . Check: .
Exercise 8.8.10
(For and per hour, find the least number of servers for which a stationary distribution exists, and the utilization there.)
Foundation
Solution(2)
- 1
Write the stability condition
Stability requires , that is .
- 2
Choose the least integer
So , with . With , and no stationary distribution exists.
Exercise 8.8.11
(A stable system has on average customers present and receives customers per hour. Find . If the mean service time is hours, find and .)
Core
Solution(2)
- 1
Little's law for the whole system
hours.
- 2
Subtract the service time and apply Little's law to the queue
hour and .
Exercise 8.8.12
(For the system , , list and compute .)
Core
Solution(2)
- 1
List the stationary probabilities
Since , , , and for . The sum is .
- 2
Sum the geometric tail
, so .