The (min,plus) Functions Semi‐ring
Anne Bouillard, Marc Boyer, Euriell Le Corronc · 2018
This chapter focuses on the algebraic foundations of network calculus, that is the (min,plus) semi-ring. Network calculus models a network by cumulative processes, which are non-decreasing functions of time. The chapter defines dioids and the operators on which are based the dioid of (min, plus) functions used in network calculus, namely the pointwise minimum and the (min, plus) convolution. It explores other algebraic operators that play an important role in network calculus, the sub-additive closure, which is used to express the solutions of affine functions in the (min, plus) dioid, and the deconvolution. In the general context of the dioid, the first operator is sometimes called the Kleene star operator, while the second operator can be defined in the context of residuation theory for complete dioids. Finally, the chapter briefly describes the related (max,plus) dioid.