CS5239 Chap.9 Performance Bounds and Bottleneck Analysis
Performance Bounds and Bottleneck Analysis
Why bounds come before models
Solving a queueing network exactly needs assumptions and arithmetic; bounding one needs only a handful of measured numbers. For a closed interactive system those numbers are the service demand per job at each device, their sum D, the largest of them Dmax, the user think time Z and the population N.
From these alone the Week 5 lecture builds limits on throughput and response time that no scheduling policy can beat. That makes bounds the first tool to reach for in a capacity question: if the optimistic limit already fails the requirement, no detailed model will rescue it.
The asymptotic family
Two physical facts drive everything.
A device cannot be busy more than all of the time, so the device with the largest demand caps throughput at 1/Dmax. A single job in an empty system is served in exactly D, so no population can do better than that response time. Pairing the cap with the interactive response time law gives a second response floor, NDmax minus Z, which grows linearly with the population.
At the other end, the worst case imagines each job queued behind every other one, which yields throughput N/(ND+Z) and response time ND. The optimistic lines cross at the knee, N* = (D+Z)/Dmax. Below it, extra users mostly raise throughput; above it, they mostly raise waiting.
The pessimistic response limit is also useful for sizing: if ND must stay under a target, the largest safe population follows at once.
Reading a bottleneck correctly
Because the heavy-load ceiling depends only on Dmax, an upgrade that shrinks any other device's demand cannot raise peak throughput. It lowers D, which helps lightly loaded users a little and actually pulls the knee to a smaller population.
Conversely, relieving the bottleneck raises the ceiling only until the next largest demand takes over, so the gain is capped by the secondary bottleneck rather than by how much the primary one improved.
The lecture's advice to improve the primary bottleneck first is therefore half of a procedure; the other half is recomputing Dmax afterwards to see which device now holds the title.
Comparing modifications on one measured system
Modification analysis takes one set of measurements, converts busy times and completion counts into per-device demands, then rewrites those demands for each candidate change: a faster processor, files moved between disks to even out their load, an additional disk that takes over part of the work, or several changes combined.
Each candidate gets its own D, Dmax and knee, and the bound curves are redrawn and compared. Moving work between devices preserves D while lowering Dmax; buying a faster device lowers both only if it is the right device.
Balanced system bounds
Asymptotic limits are loose near the knee, which is where most systems are run.
Balanced system bounds tighten them for batch workloads by comparing the real system with two idealised ones. When every one of K centres carries an equal demand, each is busy for a fraction N/(N+K-1) of the time, and such a system has the highest throughput of any with the same D.
Using the average demand gives an optimistic reference, using Dmax gives a pessimistic one, and together with the 1/Dmax cap they bracket throughput and response time much more narrowly. Beyond a population labelled N+, the balanced optimistic curve merges with the asymptotic ceiling and offers no further gain.
What this chapter covers
- 01
Optimistic throughput ceiling 1/Dmax
- 02
Response-time floors D and NDmax minus Z
- 03
Pessimistic bounds N/(ND+Z) and ND
- 04
Knee population N* = (D+Z)/Dmax
- 05
Primary and secondary bottlenecks
- 06
Modification analysis of upgrade options
- 07
Balanced system bounds for batch workloads
Worked example · free
Bounding a three-tier web service before and past its knee
- 1D = 0.2 + 0.5 + 0.3 = 1.0 s; Dmax = 0.5 s at the database.
- 1N* = (D + Z)/Dmax = (1.0 + 10)/0.5 = 22 users.
- 2Throughput at N = 40: upper bound min(1/0.5, 40/11) = min(2.0, 3.64) = 2.0 requests/s; lower bound 40/(40 x 1.0 + 10) = 0.8 requests/s.
- 1Response time at N = 40: lower bound max(1.0, 40 x 0.5 - 10) = 10 s; upper bound ND = 40 s.
- 1Sizing: ND at most 15 means N at most 15 users are guaranteed the target.
Key terms
- Asymptotic Bounds
- A pair of limits on throughput and response time for any population, derived only from total demand D, largest demand Dmax and think time Z.
- Knee Population
- The number of users N* = (D+Z)/Dmax at which the optimistic response floor switches from D to NDmax minus Z; beyond it congestion is certain.
- Bottleneck Device
- The service centre with the largest demand per job; its saturation caps system throughput at 1/Dmax.
- Balanced System Bounds
- Tighter limits obtained by comparing a system with idealised systems whose centres all carry equal demand, using the average and the largest demand.
- Modification Analysis
- A method that rewrites the measured per-device demands for each proposed change and recomputes the bounds to compare the options.
Performance Bounds and Bottleneck Analysis FAQ
Why does a faster processor sometimes fail to raise peak throughput?
Peak throughput under heavy load is capped at 1/Dmax, the inverse of the largest per-job demand. If the processor is not the device with that largest demand, speeding it up lowers total demand D but leaves Dmax unchanged, so the ceiling stays where it was and only lightly loaded users notice a small improvement.
What does the knee of the bounds tell a capacity planner?
The knee N* = (D+Z)/Dmax marks the population where even the most optimistic system has its bottleneck saturated. Below it, adding users mainly raises throughput; above it, each extra user mainly adds queueing delay. Operating well past the knee guarantees congestion regardless of scheduling.
When should I use the pessimistic bounds instead of the optimistic ones?
Use the pessimistic side when you need a guarantee. The response-time limit ND assumes every job waits behind all the others, so a population chosen to keep ND below a target meets that target in any case. The optimistic side only says what cannot be beaten, which is useful for ruling designs out.
Are balanced system bounds always better than asymptotic bounds?
They are never looser, and they are much tighter near the knee, but the lecture states them for batch workloads where think time is zero. Past the population N+ the balanced optimistic curve merges with the 1/Dmax ceiling, so at very heavy load the two families give the same answer.
How do I find the secondary bottleneck?
List the per-device demands and take the second largest. After any change that reduces the primary bottleneck below that value, the secondary device becomes the new Dmax, and its demand now sets the ceiling. That is why relieving one device rarely produces a gain proportional to its improvement.
Assessment move
Take one set of per-device demands and a think time, then compute D, Dmax, N*, the throughput interval and the response-time interval at a population below and one above the knee. Repeat after shrinking a non-bottleneck demand and after splitting the bottleneck, and write down which numbers moved and why.
Working through Performance Bounds and Bottleneck Analysis in CS5239? Sia is AskSia’s AI Computer Science tutor — ask any CS5239 Performance Bounds and Bottleneck Analysis 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.
