Skip to main content

Service curves: describing what a server guarantees

· 4 min read
PhD candidate, LyRIDS (ECE) × CEDRIC (Cnam)

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 RR and output R∗R^* offers a (min-plus) service curve β\beta if

R∗≥R⊗β,i.e.R∗(t)≥inf⁡0≤s≤t{ R(s)+β(t−s) }.R^* \ge R \otimes \beta, \qquad \text{i.e.} \qquad R^*(t) \ge \inf_{0 \le s \le t} \{\, R(s) + \beta(t - s) \,\}.

Read operationally: for every tt there is some instant s≤ts \le t such that the system has delivered at least β(t−s)\beta(t - s) bits since ss on top of everything that arrived before ss. The definition mirrors the impulse response of linear systems: an ideal pipe with latency TT has service curve δT\delta_T, a constant-rate link of rate CC has λC\lambda_C.

2. Strict service curve​

A system offers a strict service curve β\beta if, during any backlogged period of duration uu (an interval in which the system is never empty), the output is at least β(u)\beta(u).

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

βR,T(t)=R [t−T]+=max⁡(0, R(t−T)).\beta_{R,T}(t) = R\,[t - T]^+ = \max(0,\, R(t - T)).

It models a server that, after a worst-case start-up latency TT, serves at rate at least RR. Many real schedulers fall into this class, for example:

SystemRate RRLatency TT
Link of rate CC with processing delay tproct_{proc}CCtproct_{proc}
Non-preemptive link, highest priority, max lower-priority frame LloL_{lo}CCLlo/CL_{lo}/C
Generalised Processor Sharing with weight ϕi\phi_iϕiC/∑jϕj\phi_i C / \sum_j \phi_j00

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 ww time units in every cycle of length cc, on a link of rate CC. 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 c−wc - w, is served at rate CC for ww, waits again, and so on. The resulting cumulative service is a staircase whose lower corners lie on the line of slope Cw/cCw/c passing through (c−w, 0)(c - w,\, 0). Hence the queue receives the strict rate-latency service curve

β(t)=Cwc [ t−(c−w) ]+.\beta(t) = \frac{C w}{c}\, \bigl[\, t - (c - w) \,\bigr]^+ .

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.

Modelling choice

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.

  1. 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.
  2. Robustness. Bounds derived from service curves remain valid under any implementation that honours the curve, which is what a certificate needs.

References​

  1. J.-Y. Le Boudec, P. Thiran, Network Calculus, LNCS 2050, Springer, 2001, Chapter 1. Online edition
  2. A. Bouillard, M. Boyer, E. Le Corronc, Deterministic Network Calculus, Wiley-ISTE, 2018.
  3. IEEE Std 802.1Qbv-2015, Enhancements for Scheduled Traffic, now incorporated in IEEE Std 802.1Q.