Concatenation and the "pay bursts only once" principle
A flow in a TSN network crosses several bridges. There are two ways to bound its end-to-end delay: add the per-hop bounds, or first compose the hops into a single equivalent server. The second is never worse and often much better. This post explains why.
1. Concatenation theorem
If a flow crosses system offering service curve and then system offering , the concatenation offers the service curve
The proof is a one-line consequence of associativity: . The result extends to any number of hops by induction.
For rate-latency servers, the min-plus algebra post gives the closed form
The path behaves like a single server whose rate is the bottleneck rate and whose latency is the sum of the latencies.
2. Two ways to bound a two-hop path
Consider a token-bucket flow crossing two rate-latency servers and , with .
Additive (hop-by-hop) analysis. At hop 1 the delay is and the output burst is . At hop 2 the delay is . Summing,
Concatenated analysis. With ,
The additive bound pays the burst at every hop, and additionally pays the burst increase created by upstream latencies. The concatenated bound pays the burst once, at the bottleneck. This is the pay bursts only once (PBOO) principle.
3. Numerical example
Take two identical hops with Mbit/s and , and the flow bits, Mbit/s from the previous posts.
| Method | Formula | Bound |
|---|---|---|
| Additive | ||
| Concatenated |
The concatenated bound is about 43 % smaller. The gap grows linearly with the number of hops: with identical hops, the additive bound grows like whereas the concatenated bound keeps a single term.
4. Why this matters for TSN
PBOO is the reason per-flow, path-based analyses can be much tighter than per-node analyses. It is not free, however.
- It requires a per-flow service curve at each hop. When flows share a queue, one must first derive the service left to the flow of interest, the residual service curve, which is the subject of the next post.
- For aggregate scheduling, a related principle, pay multiplexing only once (PMOO), avoids paying the interference of a cross flow at every hop it shares with the flow of interest. PMOO is established for blind multiplexing; FIFO multiplexing requires different techniques.
The trade-off between per-node analyses (simple, incremental, fast) and path-based analyses (tighter, more expensive) recurs in the discussion of online admission control in the reconfiguration post.
References
- J.-Y. Le Boudec, P. Thiran, Network Calculus, LNCS 2050, Springer, 2001, Chapter 1. Online edition
- J. B. Schmitt, F. A. Zdarsky, I. Martinovic, "Improving Performance Bounds in Feed-Forward Networks by Paying Multiplexing Only Once," MMB 2008.
- A. Bouillard, M. Boyer, E. Le Corronc, Deterministic Network Calculus, Wiley-ISTE, 2018.