Skip to main content

Min-plus algebra: the language of network calculus

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

Network calculus is often summarised as "queueing theory in the min-plus algebra". In conventional system theory, a linear time-invariant system is characterised by its impulse response and its output is a convolution in the (+,×)(+,\times) algebra. Network calculus keeps the same structure but replaces addition by minimum and multiplication by addition. This post sets up that algebra.

1. Cumulative functions​

A flow crossing a system is described by two cumulative functions:

  • R(t)R(t), the number of bits that have entered the system in [0,t][0, t];
  • R∗(t)R^*(t), the number of bits that have left the system in [0,t][0, t].

Both belong to the set F\mathcal{F} of wide-sense increasing functions f:R≥0→R≥0∪{+∞}f : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0} \cup \{+\infty\} with f(0)=0f(0) = 0 (for cumulative functions). Causality and lossless operation give R∗≤RR^* \le R.

Two performance quantities are read directly from these curves:

b(t)=R(t)−R∗(t)(backlog at time t)b(t) = R(t) - R^*(t) \qquad \text{(backlog at time } t\text{)} d(t)=inf⁡{ τ≥0:R(t)≤R∗(t+τ) }(virtual delay at time t)d(t) = \inf \{\, \tau \ge 0 : R(t) \le R^*(t + \tau) \,\} \qquad \text{(virtual delay at time } t\text{)}

The backlog is the vertical distance between the two curves, the virtual delay their horizontal distance. For a FIFO system, d(t)d(t) is the delay experienced by the last bit that arrived at time tt.

2. The min-plus dioid​

The structure (R∪{+∞},min⁡,+)(\mathbb{R} \cup \{+\infty\}, \min, +) is a dioid: min⁡\min plays the role of addition (neutral element +∞+\infty) and ++ the role of multiplication (neutral element 00). Two properties differ from ordinary arithmetic and are the source of many results:

  • min⁡\min is idempotent: min⁡(a,a)=a\min(a, a) = a;
  • there is no inverse for min⁡\min, so equations are solved by inequalities and closures rather than by subtraction.

3. Min-plus convolution​

For f,g∈Ff, g \in \mathcal{F}, the min-plus convolution is

(f⊗g)(t)=inf⁡0≤s≤t{ f(t−s)+g(s) }.(f \otimes g)(t) = \inf_{0 \le s \le t} \{\, f(t - s) + g(s) \,\}.

Interpretation: to obtain the value at tt, split the interval [0,t][0, t] into two parts and take the cheapest split. The operation has the following properties, all of which are used later.

PropertyStatement
Closuref⊗g∈Ff \otimes g \in \mathcal{F}
Associativity(f⊗g)⊗h=f⊗(g⊗h)(f \otimes g) \otimes h = f \otimes (g \otimes h)
Commutativityf⊗g=g⊗ff \otimes g = g \otimes f
Distributivity over min⁡\min(min⁡(f,g))⊗h=min⁡(f⊗h, g⊗h)(\min(f, g)) \otimes h = \min(f \otimes h,\, g \otimes h)
Neutral elementf⊗δ0=ff \otimes \delta_0 = f, where δ0(0)=0\delta_0(0) = 0 and δ0(t)=+∞\delta_0(t) = +\infty for t>0t > 0
Isotonicityf≤f′f \le f' and g≤g′g \le g' imply f⊗g≤f′⊗g′f \otimes g \le f' \otimes g'
Upper boundif f(0)=g(0)=0f(0) = g(0) = 0 then f⊗g≤min⁡(f,g)f \otimes g \le \min(f, g)

Two closed forms cover most practical computations:

  • Concave functions. If ff and gg are concave with f(0)=g(0)=0f(0) = g(0) = 0, then f⊗g=min⁡(f,g)f \otimes g = \min(f, g).
  • Convex piecewise-linear functions. If ff and gg are convex and piecewise linear, f⊗gf \otimes g is obtained by concatenating their linear segments in order of increasing slope.

The second rule gives the most frequently used identity of the theory: for rate-latency functions βR,T(t)=R [t−T]+\beta_{R,T}(t) = R\,[t - T]^+,

βR1,T1⊗βR2,T2=βmin⁡(R1,R2), T1+T2.\beta_{R_1,T_1} \otimes \beta_{R_2,T_2} = \beta_{\min(R_1,R_2),\, T_1 + T_2}.

4. Min-plus deconvolution​

The dual operation is the min-plus deconvolution

(f⊘g)(t)=sup⁡u≥0{ f(t+u)−g(u) }.(f \oslash g)(t) = \sup_{u \ge 0} \{\, f(t + u) - g(u) \,\}.

It is not the inverse of ⊗\otimes, but it satisfies the duality (residuation) property

f⊘g≤h  ⟺  f≤h⊗g,f \oslash g \le h \iff f \le h \otimes g,

which is the min-plus analogue of solving f≤h×gf \le h \times g for hh. Deconvolution is used in the fundamental bounds post to compute the arrival curve of a flow after it has crossed a server.

5. Sub-additive closure​

A function ff is sub-additive if f(s+t)≤f(s)+f(t)f(s + t) \le f(s) + f(t) for all s,ts, t. The sub-additive closure of ff is

f‾=inf⁡n≥0f(n),f(0)=δ0,  f(n)=f⊗f(n−1).\overline{f} = \inf_{n \ge 0} f^{(n)}, \qquad f^{(0)} = \delta_0,\; f^{(n)} = f \otimes f^{(n-1)}.

It is the largest sub-additive function below ff (and below δ0\delta_0). Sub-additive closures appear naturally in the study of arrival curves: any arrival curve can be replaced by its sub-additive closure without loss of information, as shown in the next post.

6. Summary​

ObjectConventional systemsNetwork calculus
Signalx(t)x(t)Cumulative function R(t)R(t)
"Addition"++min⁡\min
"Multiplication"×\times++
System lawy=h∗xy = h * xR∗≥R⊗βR^* \ge R \otimes \beta
ImpulseDirac δ\deltaδ0\delta_0 (zero at 0, +∞+\infty elsewhere)
  • An Introduction to Network Calculus, LCA2, EPFL. YouTube.

References​

  1. J.-Y. Le Boudec, P. Thiran, Network Calculus, LNCS 2050, Springer, 2001, Chapter 3. Online edition
  2. A. Bouillard, M. Boyer, E. Le Corronc, Deterministic Network Calculus, Wiley-ISTE, 2018.
  3. C.-S. Chang, Performance Guarantees in Communication Networks, Springer, 2000.