CS5239 Chap.5 Queueing Systems, Kendall Notation and Little's Law
Queueing Systems, Kendall Notation and Little's Law
Why a model before a measurement
Performance questions usually arrive before the hardware does. Will the response time hold if demand doubles? Should extra capacity come as one large machine or several small ones, and should those share a single line? An analytic model answers such questions on paper.
Its inputs split into workload facts, such as how often requests arrive and how long they take, and system facts, such as how many servers exist, how much buffer space they have and how jobs are routed. Its outputs are the quantities an operator cares about: delay, completions per second, how busy each resource is, and whether the backlog stays bounded.
The price is that the answer can be no better than the assumptions, which is why the course insists that each input be backed by a measurement or an explicit assumption.
Randomness as the raw material
Requests do not arrive on a timetable, and their service demands vary, so queueing theory describes them with random variables that evolve over time.
A count of jobs present is an integer-valued process; an individual wait is a real-valued one. The memoryless (Markov) property, where only the present state matters for what happens next, makes many results tractable, and exponential gaps between arrivals give the familiar Poisson stream.
Operational analysis, covered alongside, takes a different route by reasoning only from observed averages such as busy time and completion counts.
Shapes of systems and how to name them
A single service centre has a source, an arrival stream, a line, one or more servers with their service-time distribution, and a rule that picks the next job. Centres connect into networks.
When outside traffic can come and go freely, the network is open; when a fixed set of jobs circulates, as with users at terminals who wait, read the reply and submit again, or an overnight batch that replaces each finished job, the network is closed.
Kendall’s compact label records the arrival distribution, the service distribution, the server count, the total capacity, the population size and the discipline, with the last three dropped when they take their default values of unlimited, infinite and first come, first served.
The rules that hold for every queue
Whatever the distributions, the jobs present split into those waiting and those being served, and the time inside splits into waiting and service.
A queue stays bounded only when arrivals come more slowly than the combined service rate of all servers, although being bounded says nothing about whether the delay is tolerable. Little’s law then links counts to times: average population equals throughput multiplied by average time inside, and it works separately for the line and for the servers.
Its proof needs only bookkeeping of the total job-time accumulated over a long observation window, which is why it ignores scheduling order and distribution shape.
Where students lose marks
Three slips recur. The first is mixing boundaries, for instance dividing the number waiting by the throughput and calling the result a response time.
The second is applying the law to an overloaded system, where averages never settle and any number produced is meaningless. The third arises with finite capacity: rejected jobs never complete, so the throughput used must be the accepted rate.
For a single server, the fraction of time busy equals arrival rate times mean service time, and its complement is the chance of finding the server idle; that fraction can never exceed one, and equals the traffic intensity only when nothing is lost.
What this chapter covers
- 01
Analytic models: workload and system inputs, performance predictions
- 02
Stochastic, Markov and Poisson processes
- 03
Components of a single service centre
- 04
Open versus closed queueing networks: interactive and batch
- 05
Kendall notation A/S/m/K/N/SD and its defaults
- 06
Rules for all queues and the stability condition
- 07
Little's law, its proof idea and traffic intensity
Worked example · free
Little's law on a four-node cache tier
- 1Check stability: total service rate m times 1/E[s] must exceed the arrival rate.
- 1Apply E[n] = lambda E[r] to the whole system to get the mean response time.
- 1Apply E[ns] = lambda E[s] to the servers to get the mean number in service.
- 1Use E[n] = E[nq] + E[ns] to get the mean number waiting.
- 1Use E[r] = E[w] + E[s] for the mean wait and confirm with E[nq] = lambda E[w].
- 1Divide the busy-server count by m for per-node utilization.
Key terms
- Analytic Model
- A mathematical representation of a computer system that turns workload and system parameters into predicted response time, throughput and utilization.
- Stochastic Process
- A time-indexed family of random variables that describes how a system evolves under uncertainty, such as the number of jobs at a CPU.
- Poisson Process
- An arrival stream whose gaps between arrivals are independent exponential random variables, so the count of arrivals in an interval is Poisson distributed.
- Open Queueing Network
- A network in which jobs arrive from and depart to the outside, so the number of jobs inside is not fixed.
- Closed Queueing Network
- A network with no external arrivals or departures, in which a fixed number N of jobs circulates, as in interactive or batch systems.
- Think Time
- A random variable giving the time a terminal user spends between receiving one reply and submitting the next job.
- Kendall Notation
- A label of the form A/S/m/K/N/SD naming the arrival and service distributions, server count, capacity, population and discipline.
- Little's Law
- A relation stating that the mean number of jobs in a stable system equals the mean arrival rate times the mean response time.
Queueing Systems, Kendall Notation and Little's Law FAQ
Does Little's law require exponential arrivals or FCFS service?
No. The law holds whatever the queueing order, the shape of the arrival gaps or service times, and however many queues there are. What it does need is a well-defined boundary, long-run balance between jobs entering and jobs completing, and finite averages, which in practice means a stable system observed in steady state.
What does the shorthand M/M/1 leave out of the full Kendall label?
It omits the capacity K, the population N and the discipline SD. When those slots are dropped the convention is an unlimited queue, an infinite customer source and first come, first served ordering, so M/M/1 is read as exponential gaps, exponential service and one server under those defaults.
Is a system with arrival rate below service capacity guaranteed to perform well?
Not at all. Arrivals slower than the total service rate only guarantee that the queue stays bounded in the long run. The mean delay can still be far above an acceptable target when utilization is high, so stability is a warning check to run first, not a performance verdict.
How do I decide whether a system should be modelled as open or closed?
Ask whether new jobs can enter from outside while existing ones remain inside. A public web service or router accepts outside traffic, so it is open. Terminal users who wait for each reply, or a batch pool that starts a new job as each finishes, keep the population fixed and are closed.
Why is utilization sometimes lower than traffic intensity?
Traffic intensity is the offered load, arrival rate divided by service rate. Utilization is the fraction of time the server is actually busy and is capped at 100%. When no jobs are lost the two coincide, but when a finite buffer rejects arrivals, the server never sees those jobs, so utilization falls below the offered intensity.
Assessment move
Take any two of E[n], lambda and E[r] from a scenario you invent and recover the third, then split both the count and the time into their waiting and service parts and check that each pair satisfies its own form of Little's law. Before every calculation, write the stability inequality lambda < m mu and say aloud which boundary your lambda is counted across.
Working through Queueing Systems, Kendall Notation and Little's Law in CS5239? Sia is AskSia’s AI Computer Science tutor — ask any CS5239 Queueing Systems, Kendall Notation and Little's Law 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.
