Arrival curves: describing what a flow may send
An arrival curve is the traffic contract of a flow: an upper bound on how much data the flow may send in any time window. It is the first of the two envelopes on which network calculus is built.
1. Definition
A wide-sense increasing function is an arrival curve for a flow with cumulative function if
Equivalently, in min-plus notation,
The definition constrains every interval, not only intervals starting at time zero. It therefore bounds both the long-term rate and the short-term burstiness of the flow.
2. Standard families
Token bucket (leaky bucket). The affine function
states that the flow never sends more than bits instantaneously (the burst) and has a long-term rate at most . A token bucket with rate and depth is the classical device that enforces it, and 802.1Qci policers in TSN implement this kind of contract.
Peak rate. constrains a flow that cannot exceed the line rate . Combining it with a token bucket gives , which is concave.
Staircase. A strictly periodic stream with period and maximum frame size , as typical of time-triggered TSN traffic, admits
If the release instants may deviate by up to a jitter , the curve becomes . A staircase is upper-bounded by the token bucket (or with jitter); analyses frequently use the token bucket because it keeps closed forms simple, at the cost of some pessimism.
3. Good arrival curves
Not every arrival curve is informative. If is an arrival curve for , then its sub-additive closure is also one. Moreover, , so no information is lost. One may therefore restrict attention to good arrival curves, i.e. sub-additive functions with . All concave functions with , in particular token buckets, are good.
4. Greedy shapers
A greedy shaper with shaping curve (assumed good) delays bits as little as necessary so that its output has arrival curve . Its output is
Two properties make shapers attractive in network design:
- Shapers preserve arrival curves. If the input has arrival curve , the output has arrival curve , and in particular still satisfies .
- Re-shaping is for free. If a flow is already constrained by at the entrance of a network, inserting a greedy shaper with the same curve after any sub-network does not increase the end-to-end delay bound. The shaper removes the burstiness accumulated inside the network without costing anything in the worst case.
The second property is the theoretical basis of the Asynchronous Traffic Shaper (802.1Qcr), whose interleaved regulators extend it to aggregates of flows (see the TSN shapers post).
5. Worked example
Consider a control stream that emits one 1500-byte frame ( bits) every ms. Its staircase arrival curve is bits, upper-bounded by the token bucket
This pair is the input of every bound derived in the rest of the series.
Recommended viewing
- An Introduction to Network Calculus, LCA2, EPFL. YouTube.
- 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
- R. L. Cruz, "A calculus for network delay, Part I: Network elements in isolation," IEEE Transactions on Information Theory, 37(1), 1991.
- J.-Y. Le Boudec, "A Theory of Traffic Regulators for Deterministic Networks With Application to Interleaved Regulators," IEEE/ACM Transactions on Networking, 26(6), 2018.