Service curves: describing what a server guarantees
The arrival curve bounds the demand; the service curve bounds the supply. It abstracts a scheduler, a link or a whole switch into a single function that lower-bounds the service it delivers.
1. Min-plus service curve
A system with input and output offers a (min-plus) service curve if
Read operationally: for every there is some instant such that the system has delivered at least bits since on top of everything that arrived before . The definition mirrors the impulse response of linear systems: an ideal pipe with latency has service curve , a constant-rate link of rate has .
2. Strict service curve
A system offers a strict service curve if, during any backlogged period of duration (an interval in which the system is never empty), the output is at least .
Every strict service curve is a min-plus service curve; the converse is false. The distinction matters because several results, in particular blind multiplexing in the multiplexing post, require the strict version. Schedulers that serve as soon as they are backlogged, possibly after a bounded interruption, are naturally described by strict service curves.
3. Rate-latency servers
The workhorse of the theory is the rate-latency function
It models a server that, after a worst-case start-up latency , serves at rate at least . Many real schedulers fall into this class, for example:
| System | Rate | Latency |
|---|---|---|
| Link of rate with processing delay | ||
| Non-preemptive link, highest priority, max lower-priority frame | ||
| Generalised Processor Sharing with weight |
Rate-latency functions are convex, so by the concatenation rule of the min-plus algebra post a tandem of rate-latency servers is again rate-latency.
4. Example: a Time-Aware Shaper window
Consider an egress queue controlled by an 802.1Qbv gate that is open for time units in every cycle of length , on a link of rate . Assume, for simplicity, that no other queue transmits during this window and ignore the guard band that prevents frames from overrunning the window.
In the worst case, the queue becomes backlogged just as its gate closes. It then waits , is served at rate for , waits again, and so on. The resulting cumulative service is a staircase whose lower corners lie on the line of slope passing through . Hence the queue receives the strict rate-latency service curve
The rate is the reserved share of the link; the latency is the longest closed interval. Accounting for the guard band and for non-preemptive blocking increases the latency and slightly decreases the effective window.
The rate-latency bound discards the staircase structure and is therefore pessimistic for traffic that is synchronised with the gate schedule. Time-triggered TSN analyses often exploit that synchronisation explicitly; network calculus remains the method of choice for traffic that is not synchronised, and for the residual service left to lower-priority classes.
5. Service curves are a contract, not a description
A service curve is a guarantee that the system at least provides, not an exact model. This has two consequences that recur in the rest of the series.
- Composability. Any lower bound of a service curve is still a service curve, so one may always simplify a complex curve to a rate-latency one and keep sound (if looser) bounds.
- Robustness. Bounds derived from service curves remain valid under any implementation that honours the curve, which is what a certificate needs.
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.
- IEEE Std 802.1Qbv-2015, Enhancements for Scheduled Traffic, now incorporated in IEEE Std 802.1Q.