Skip to main content

The three fundamental bounds: delay, backlog and output

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

With an arrival curve α\alpha for the input and a service curve β\beta 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 α\alpha cross a system offering service curve β\beta.

Backlog bound. For all tt,

R(t)−R∗(t)≤v(α,β)=sup⁡s≥0{ α(s)−β(s) }.R(t) - R^*(t) \le v(\alpha, \beta) = \sup_{s \ge 0} \{\, \alpha(s) - \beta(s) \,\}.

Delay bound. For all tt, the virtual delay satisfies

d(t)≤h(α,β)=sup⁡s≥0{inf⁡{ τ≥0:α(s)≤β(s+τ) }}.d(t) \le h(\alpha, \beta) = \sup_{s \ge 0} \Bigl\{ \inf \{\, \tau \ge 0 : \alpha(s) \le \beta(s + \tau) \,\} \Bigr\}.

Output arrival curve. The output flow R∗R^* has arrival curve

α∗=α⊘β.\alpha^* = \alpha \oslash \beta .

vv is the vertical deviation and hh the horizontal deviation between the two curves. For a FIFO system the virtual delay is the actual delay of every bit, so h(α,β)h(\alpha,\beta) bounds the delay of every frame of the flow.

2. Proof sketch of the backlog bound​

Fix tt. By the service curve property there exists s≤ts \le t such that R∗(t)≥R(s)+β(t−s)R^*(t) \ge R(s) + \beta(t - s). Hence

R(t)−R∗(t)≤R(t)−R(s)−β(t−s)≤α(t−s)−β(t−s)≤v(α,β),R(t) - R^*(t) \le R(t) - R(s) - \beta(t - s) \le \alpha(t - s) - \beta(t - s) \le v(\alpha, \beta),

where the second inequality uses the arrival curve property. The delay bound follows from a similar argument; the output bound follows from R∗(t)−R∗(s)≤R(t)−R(s−u)−β(u)R^*(t) - R^*(s) \le R(t) - R(s - u) - \beta(u) for a suitable uu and the duality property of ⊘\oslash.

3. Closed forms: token bucket through a rate-latency server​

Take α=γr,b\alpha = \gamma_{r,b} and β=βR,T\beta = \beta_{R,T} with the stability condition r≤Rr \le R. The three bounds become

D=T+bR,B=b+r T,α∗=γr,  b+rT.D = T + \frac{b}{R}, \qquad B = b + r\,T, \qquad \alpha^* = \gamma_{r,\; b + r T}.
tbitsα(t) = b + r·tβ(t) = R·[t − T]⁺D = T + b/RB = b + r·TTb0
Figure 1. Delay and backlog bounds as the horizontal and vertical deviations between an arrival curve α and a service curve β (case r ≤ R).

Each formula has a direct reading.

  • Delay. A burst of bb bits arrives just as the server starts its worst-case latency TT; it is then drained at rate RR.
  • Backlog. During the latency TT nothing leaves, while the burst bb and a further rTrT bits may arrive.
  • Output burst. The long-term rate is unchanged, but the burst grows by rTrT: data held back during the latency may leave back-to-back. This burstiness increase is what makes multi-hop analysis non-trivial.

If r>Rr > R, both vv and hh 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, b=12 000b = 12\,000 bits, r=12r = 12 Mbit/s, and a switch port offering βR,T\beta_{R,T} with R=100R = 100 Mbit/s and T=20 μsT = 20\ \mu s.

QuantityFormulaValue
Delay boundT+b/RT + b/R20+120=140 μs20 + 120 = 140\ \mu s
Backlog boundb+rTb + rT12 000+240=12 24012\,000 + 240 = 12\,240 bits
Output burstb+rTb + rT12 24012\,240 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 α\alpha a good arrival curve and β\beta 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.

  • Network Calculus: Guaranteed performance analysis in networks, LINCS seminar. YouTube.

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.