Deterministic Network Calculus

2 The (min,plus) Functions Semi-ring

As noted in Chapter 1, the minimum and the addition operators naturally appear when modeling a network element, and also in Chapter 1 we introduced the (min,plus) convolution. This operator will frequently appear in the rest of this book.

In this chapter, we will focus on the algebraic foundations of network calculus, i.e. the (min,plus) semi-ring. This structure and its developments, known as tropical algebra, was first defined in the 1980s, independently by Imre Simon and Victor Maslov, and has been studied in several fields of mathematics or computer science. We can, for example, cite tropical geometry, performance evaluation and the strong relations between (min,plus) matrices and shortest-path algorithms.

Network calculus models a network by cumulative processes, which are non-decreasing functions of time, and we will see that the set of these functions can be endowed with the minimum and the (min,plus) convolution to form a semi-ring.

This chapter gives the basics of such an algebraic structure and all the necessary background in the context of network calculus. Our aim here is to emphasize the role of the algebraic structure, so we first define the operators in the general context of semi-rings or dioids before applying them to the (min,plus) dioids. This chapter does not constitute a complete reference on (min,plus) algebras, and the interested reader may refer to [BAC 92, BLY 05] for a more detailed presentation.

This chapter is ...