Min-plus algebra: the language of network calculus
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 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:
- , the number of bits that have entered the system in ;
- , the number of bits that have left the system in .
Both belong to the set of wide-sense increasing functions with (for cumulative functions). Causality and lossless operation give .
Two performance quantities are read directly from these curves:
The backlog is the vertical distance between the two curves, the virtual delay their horizontal distance. For a FIFO system, is the delay experienced by the last bit that arrived at time .
2. The min-plus dioid
The structure is a dioid: plays the role of addition (neutral element ) and the role of multiplication (neutral element ). Two properties differ from ordinary arithmetic and are the source of many results:
- is idempotent: ;
- there is no inverse for , so equations are solved by inequalities and closures rather than by subtraction.
3. Min-plus convolution
For , the min-plus convolution is
Interpretation: to obtain the value at , split the interval into two parts and take the cheapest split. The operation has the following properties, all of which are used later.
| Property | Statement |
|---|---|
| Closure | |
| Associativity | |
| Commutativity | |
| Distributivity over | |
| Neutral element | , where and for |
| Isotonicity | and imply |
| Upper bound | if then |
Two closed forms cover most practical computations:
- Concave functions. If and are concave with , then .
- Convex piecewise-linear functions. If and are convex and piecewise linear, 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 ,
4. Min-plus deconvolution
The dual operation is the min-plus deconvolution
It is not the inverse of , but it satisfies the duality (residuation) property
which is the min-plus analogue of solving for . 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 is sub-additive if for all . The sub-additive closure of is
It is the largest sub-additive function below (and below ). 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
| Object | Conventional systems | Network calculus |
|---|---|---|
| Signal | Cumulative function | |
| "Addition" | ||
| "Multiplication" | ||
| System law | ||
| Impulse | Dirac | (zero at 0, elsewhere) |
Recommended viewing
- An Introduction to Network Calculus, LCA2, EPFL. YouTube.
References
- J.-Y. Le Boudec, P. Thiran, Network Calculus, LNCS 2050, Springer, 2001, Chapter 3. Online edition
- A. Bouillard, M. Boyer, E. Le Corronc, Deterministic Network Calculus, Wiley-ISTE, 2018.
- C.-S. Chang, Performance Guarantees in Communication Networks, Springer, 2000.