The three fundamental bounds: delay, backlog and output
With an arrival curve for the input and a service curve for the system, network calculus yields three bounds. They are the core results of the theory; everything that follows in this series composes them.
1. Statements
Let a flow with arrival curve cross a system offering service curve .
Backlog bound. For all ,
Delay bound. For all , the virtual delay satisfies
Output arrival curve. The output flow has arrival curve
is the vertical deviation and the horizontal deviation between the two curves. For a FIFO system the virtual delay is the actual delay of every bit, so bounds the delay of every frame of the flow.
2. Proof sketch of the backlog bound
Fix . By the service curve property there exists such that . Hence
where the second inequality uses the arrival curve property. The delay bound follows from a similar argument; the output bound follows from for a suitable and the duality property of .
3. Closed forms: token bucket through a rate-latency server
Take and with the stability condition . The three bounds become
Each formula has a direct reading.
- Delay. A burst of bits arrives just as the server starts its worst-case latency ; it is then drained at rate .
- Backlog. During the latency nothing leaves, while the burst and a further bits may arrive.
- Output burst. The long-term rate is unchanged, but the burst grows by : data held back during the latency may leave back-to-back. This burstiness increase is what makes multi-hop analysis non-trivial.
If , both and are infinite: no finite bound exists, which is the network-calculus statement of instability.
4. Numerical example
Reuse the control stream of the arrival curves post, bits, Mbit/s, and a switch port offering with Mbit/s and .
| Quantity | Formula | Value |
|---|---|---|
| Delay bound | ||
| Backlog bound | bits | |
| Output burst | bits |
The output burst is the input burst of the next hop. The next post shows that propagating it hop by hop is sound but pessimistic, and how to avoid that pessimism.
5. Tightness
For a single node with a good arrival curve and a service curve, the bounds are tight: there exist a trajectory and a system that attain them. Tightness is lost when nodes are composed or when flows are aggregated, and recovering it at acceptable computational cost is one of the active research topics of the field.
Recommended viewing
- Network Calculus: Guaranteed performance analysis in networks, LINCS seminar. YouTube.
References
- J.-Y. Le Boudec, P. Thiran, Network Calculus, LNCS 2050, Springer, 2001, Chapter 1. Online edition
- A. Bouillard, M. Boyer, E. Le Corronc, Deterministic Network Calculus, Wiley-ISTE, 2018.