CS5239 Chap.7 Multi-Server Queues and Queueing Networks
Multi-Server Queues and Queueing Networks
Why one server is no longer enough
The single-server queue gives clean closed forms, but real systems rarely look like one counter. Clusters, thread pools, call centres and terminal rooms put several identical servers behind a common arrival stream. The Week 4 lecture keeps the Markov assumptions, Poisson arrivals and exponential service times, and changes only the departure side of the birth-death chain.
In a state with n jobs and m servers the completion rate is n times the per-server rate while some servers are idle, and it saturates at m times that rate once every server is occupied. This single change is responsible for every new formula in the M/M/m model.
Reading the M/M/m formulas in order
Start with the traffic intensity, defined per server as arrival rate divided by m times the service rate.
It must stay below one for a steady state to exist. Next comes the empty-system probability, a normalising sum that mixes a finite series for the partly idle states with a geometric tail for the states where all servers are busy. From it you obtain the probability that an arrival must queue, which is the hinge for the delay results: mean waiting time, mean response time and the waiting-time percentile all scale with it.
A useful habit is to compute and record that queueing probability before anything else, since an error there propagates into every later number.
Pooling, splitting and the fast single server
One of the most quoted lessons of the topic concerns layout rather than algebra.
Five terminals spread across five buildings behave as five separate single-server queues, each loaded exactly as heavily as the pooled room, yet the expected time in the system is far longer because a student can wait at a busy terminal while another one sits idle elsewhere. A single shared line removes that waste.
Replacing several slow servers with one server of equal total speed goes further on the mean, because an isolated job is processed at full speed, although the pooled design gives more resilience if a server goes down.
When the room has walls
The finite-capacity model caps the number of jobs in the system at K, counting those in service.
Arrivals that find all K places taken are lost, which means the chain has a last state and is stable at any load. The quantity that matters is the full-room probability: multiplying it by the offered rate gives the loss rate, subtracting that from the offered rate gives the effective rate actually admitted, and the effective rate is the correct divisor when converting mean occupancy into mean response time.
Utilization shrinks by the same factor, since rejected jobs never take service.
From single stations to networks and repair crews
Connecting stations produces a queueing network.
Tandem lines and open Jackson networks have a product-form steady state: the joint distribution of queue lengths equals the product of independent single-station distributions, provided each station is evaluated at its net arrival rate from the traffic equations. Closed networks also factorise but need a normalising constant, which the convolution algorithm supplies. The same birth-death machinery models reliability.
Machines fail and wait for a limited repair crew, so the failure rate falls as machines go down while the repair rate saturates at the crew size. Mean time to repair then includes queueing for a repairer, and the course uses this to ask how many staff keep a target share of machines running.
What this chapter covers
- 01
M/M/m birth-death rates and traffic intensity
- 02
Probability of queueing and M/M/m delay metrics
- 03
One shared queue versus separate queues versus one fast server
- 04
M/M/m/K blocking, effective arrival rate and loss rate
- 05
Product-form solutions and open Jackson networks
- 06
Data-centre reliability with MTTF, MTTR and repair staff
Worked example · free
Blocking and delay in a two-server room with five places
- 2Compute the traffic intensity and the empty-system probability p0 for M/M/2/5.
- 2Compute the full-room probability p5 and the loss rate.
- 2Find the effective arrival rate and the per-server utilization.
- 2Sum n times pn for the mean number present and divide by the effective rate.
Key terms
- Traffic Intensity
- The load per server in a multi-server queue, equal to the arrival rate divided by the number of servers times the per-server service rate; it must be below one for an infinite queue to be stable.
- Probability of Queueing
- The steady-state probability that all m servers are busy, so a new arrival has to wait; every M/M/m delay metric is proportional to it.
- Effective Arrival Rate
- The rate at which jobs are actually admitted to a finite-capacity queue, equal to the offered rate times one minus the full-system probability.
- Loss Rate
- The rate at which arrivals are turned away because the system is full, equal to the offered arrival rate times the probability of being in the last state.
- Product-Form Network
- A queueing network whose steady-state joint distribution of queue lengths factorises into a product of per-station terms, up to a normalising constant.
- Mean Time To Repair
- The average time from a machine failing to being operational again, including any time spent waiting for a free member of the repair staff.
Multi-Server Queues and Queueing Networks FAQ
Why does a single shared queue beat several separate queues with the same servers?
With separate lines a job can sit behind a busy server while another server has nothing to do, so capacity is wasted. A shared line hands the next job to whichever server frees up first. In the lecture's terminal-room comparison each design has the same per-terminal utilization, yet the mean time in the system with separate queues is two and a half times that of the pooled room.
Is an M/M/m/K queue really stable when the arrival rate exceeds total capacity?
Yes, in the sense that a steady-state distribution exists, because the chain has a final state K and cannot drift to infinity. The cost moves elsewhere: the full-room probability approaches one, losses grow, and the admitted rate stays close to total service capacity. Stability here describes the mathematics, not acceptable service.
How do I find the arrival rate at each station of an open Jackson network?
Write one balance equation per station saying that its net arrival rate equals external arrivals plus the routed outputs of other stations, then solve the linear system. For a CPU feeding a disk that sends jobs back, the CPU rate is the external rate divided by the exit probability. Each station is then analysed as an independent M/M/1 at that rate.
Why does adding repair staff stop helping after a point?
Repair time has two parts: waiting for a free repairer and the repair itself. Extra staff remove the waiting part, so MTTR falls steeply at first, but once almost no machine waits it cannot fall below the pure repair time. In the lecture's 120-machine table, going beyond about seven repairers changes the operational share by well under one percentage point.
Which quantity should I compute first in an M/M/m problem?
Compute the traffic intensity to confirm stability, then p0, then the probability of queueing. The waiting time, response time, queue length and waiting percentile all reuse that probability, so checking it once with a quick recomputation catches most arithmetic errors before they spread through the answer.
Assessment move
Build one small script that returns p0, the probability of queueing, E[w] and E[r] for M/M/m and pK, lambda' and E[r] for M/M/m/K, and check it against the lecture's terminal-room numbers. Then rework Figure 7.1 at a load of your choice to see the pooling gap change, since the tests are open book but reward fast, correct arithmetic.
Working through Multi-Server Queues and Queueing Networks in CS5239? Sia is AskSia’s AI Computer Science tutor — ask any CS5239 Multi-Server Queues and Queueing Networks question and get a clear, step-by-step explanation grounded in how CS5239 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
