2 The (min,plus) Functions Semi-ring – 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 organized as follows. In section 2.1, we define 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. Sections 2.2 and 2.3 are devoted to two 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, we briefly describe the related (max,plus) dioid.

2.1. The (min,plus)-based dioids

In this section, we describe the algebraic structure on which network calculus relies, i.e. the dioid of (min,plus) functions. To reach that point, we first deal with the general definition of a dioid. Second, in section 2.1.2, we specialize this notion to the (min,plus) dioid where numbers are equipped with the minimum and the addition. Finally, in section 2.1.3, this dioid is lifted to the dioid of (min,plus) functions, which are functions that take their values in the (min,plus) dioid.

We will use the following classical notation: is the set of all real numbers, is the set of non-negative real numbers and in the set of non-negative integers.

2.1.1. Dioids

DEFINITION 2.1 (Monoid).– Let be a set and be a binary operator over . We say that is a monoid if:

  1. i) is associative:
  2. ii) possesses a neutral element: such that

The operator is:

  • commutative
  • idempotent

DEFINITION 2.2 (Commutative and idempotent monoids).– A monoid is said to be commutative if is commutative and is said to be idempotent if is both commutative and idempotent.

DEFINITION 2.3 (Semi-ring).– Let be a set and be two binary operators over . A semi-ring is a set endowed with two inner laws and such that:

  1. i) is a commutative monoid with neutral element ε, called the zero element;
  2. ii) is a monoid with neutral element e, called the unit element;
  3. iii) is left- and right-distributive over
  4. iv) ε is absorbing for

Moreover, if is commutative, then is a commutative semi-ring.

DEFINITION 2.4 (Idempotent semi-ring / dioid).– A semi-ring is said to be idempotent if (, ㊉) is an idempotent monoid. We call such an idempotent semi-ring a dioid. The operatorsand are, respectively, called the sum and the product.

REMARK 2.1.– As in the usual algebra, it can happen that operator is omitted in equations, i.e. ab denotes a b, and the operator has priority over theoperator:

THEOREM 2.1 (Order relation of a dioid).– Let (, ㊉, ) be an idempotent dioid. The relation defined by

is an order relation1. The operatorsand are isotone regarding the following order relation:

PROOF.– The relation defined as in the theorem is:

  • reflexive because ㊉ is idempotent: aa = a so a a;
  • transitive: if a b and b c, then and a c;
  • antisymmetric: if a b and b a, then ab = a = b.

Moreover, if a b, then:

  • and in the same way,

REMARK 2.2.– In fact, two different definitions of dioid can be found in the literature. In [BAC 92], a dioid is defined as an idempotent semi-ring, as we defined it here. However, in [GON 02], a dioid is a semi-ring where equation [2.1] defines an order relation, and being idempotent is only a sufficient condition to be a dioid. In the remainder of this book, we will only consider (min,plus) semi-rings, which are idempotent, and then dioids according to both definitions.

DEFINITION 2.5 (Complete dioid).– A dioid (, ㊉, ) is said to be complete if it is closed for infinite sums and if the product distributes over infinite sums on both sides. In other words,

A complete dioid has a greatest element denoted by , which is the sum of all of the elements of :

This top element is absorbing for the sum: and since ε is absorbing for the product,

2.1.2. The (min,plus) dioid

In this section, we specialize the notion of dioid with the minimum and addition operators.

THEOREM 2.2 (The (min,plus) dioid).– Set and denote the minimum operator by ˄. Then, (min, ˄, +) is a commutative dioid with zero element ε = + ∞ and unit element e = 0.

PROOF.– It should be clear to the reader that the minimum is a commutative, associative and idempotent operator. Moreover, It should also be clear that the addition is associative and commutative and distributes over ˄, and Finally, ε is absorbing:

Since in min the sum ㊉ is a minimum ˄, the dioid order (Theorem 2.1) is the opposite to the natural order:

In this book, unless otherwise stated, the term “order” refers to the natural order (denoted by ≤).

Obviously, this dioid is not complete, but it can be completed by adding and set

PROPOSITION 2.1 (The complete (min,plus) dioid).– is a complete commutative dioid, with zero element ε = +∞, unit element e = 0 and top element = –∞. Because of the absorption of ε over the product, it holds

PROOF.– It suffices to remark that the addition distributes over an arbitrary infimum.

Here, is the least element in the natural order.

Another way to obtain a complete dioid with minimum and addition operator is to consider

PROPOSITION 2.2.– is a complete commutative dioid.

PROOF.– It suffices to see that and that is stable by the minimum and the addition. Therefore, is a sub-dioid of It is complete with = 0: the infimum of a set of non-negative numbers is non-negative, and the addition distributes over the infimum.

2.1.3. The dioid of (min,plus) functions

We are now ready to define the dioid of (min,plus) functions. These functions are defined from The operators of this dioid are inherited from those of The first operator is the classical pointwise minimum operator, whereas the other operator is the (min,plus) convolution that we will now define. It can be interpreted as the (min,plus) adaptation of the classical convolution The choice ofThe shape of + for the definition domain of the functions has been discussed in Chapter 1. Another natural choice is .

DEFINITION 2.6 ((min,plus) functions).– is the set of functions defined from the set of non-negative reals + to the complete (min,plus) dioid

DEFINITION 2.7 ((min,plus) convolution).– Let f and g be two functions of . The (min,plus) convolution is defined by

[2.2]

There will be no confusion with the classical convolution in the following, so we will write convolution for short instead of (min,plus) convolution.

The shape of fg cannot easily be deduced from that of f and g. But, intuitively, it can be obtained by sliding one function along the other and taking minimum hull of this operation, as illustrated in Figure 2.1.

Figure 2.1. The convolution can be obtained by sliding one function over the other: g (dashed) slides over f (plain). The minimum hull (thick) is fg. For a color version of this figure, see www.iste.co.uk/bouillard/calculus.zip

Note that the infimum is not necessarily a minimum, i.e. there does not always exist s such that (fg)(t) = f (t - s) + g(s). This point will be discussed more precisely in Proposition 3.10 of Chapter 3.

LEMMA 2.1 (Properties of the convolution).– The convolution is commutative, associative and distributes over the minimum:

  1. 1) (commutativity) fg = gf;
  2. 2) (associativity) (fg) ∗ h = f ∗ (gh);
  3. 3) (distributivity) f ∗ (g ˄ h) = (fg) ˄ (fh);
  4. 4) (addition by a constant)

PROOF.– The commutativity is a direct consequence of equation [2.3].

The associativity also comes from the distributivity of the addition over the minimum and over the infimum:

The same can be rewritten from ((fg) ∗ h)(t), leading to equality.

The distributivity over the minimum is also straightforward, from the distributivity of the addition over the minimum:

The addition by a constant is also a consequence of the distributivity of the addition over the infimum:

LEMMA 2.2.– Let . If then . If f(0) = g(0) = 0, then fg f ˄ g.

PROOF.– If f(0) 0, then

If f(0) = g(0) = 0, then (fg)(t) min(f(0) + g(t), f(t) + g(0))= min(f(t), g(t)) = (f ˄ g)(t).

PROPOSITION 2.3 (Dioid of (min,plus) functions).– The structure (, ˄, ∗) is a complete commutative dioid. Its zero element is its unit element is and its top element is

PROOF.– The associativity, commutativity and idempotency of ˄ are direct consequences of these properties for the (min,plus) dioid proved in Proposition 2.2. The definitions of the zero element ε and the top element are also a consequence of the fact that +∞ and –∞ are, respectively, the zero element and top element of

The associativity, commutativity of the convolution and distributivity of the convolution over the minimum are proved in Lemma 2.1. It remains to check that e is the unit element: for all e(0) = f(t) as e(t - s) = +∞ as soon as s ≠ t.

From Theorem 2.1, which gives a canonical order relation for the dioid, we can directly deduce that

We have presented the general framework of the (min,plus) functions. In network calculus, however, more restricted classes of functions are often used because of the physical interpretation of the functions. Namely, those functions are often non-negative, non-decreasing or take value 0 at 0.

DEFINITION 2.8 (Main subsets of functions).–

  • is the set of non-negative functions defined from
  • is the set of non-negative functions of such that f(0) = 0:
  • is the set of non-negative and non-decreasing functions of :
  • is the set of non-negative and non-decreasing functions of with f(0) = 0:

LEMMA 2.3.– The sets of functions are stable by the minimum and the convolution.

PROOF.– It is well known that the minimum of two non-decreasing (respectively non-negative and null at 0) functions is non-decreasing (respectively non-negative and null at 0).

We now prove it for the convolution. Let . First, if f(0) = g(0) = 0, then (fg)(0) = min(f(0), g(0)) = 0.

If f and g are non-negative, then so

If moreover f and g are non-decreasing, then for all Indeed, and is either 0 if or t' - s otherwise. In all cases, So,

A consequence of this lemma and of the fact that is a complete dioid is that and are complete dioids. Note that the top element of differs: it is the constant function equal to zero. Also, note that and are not dioids, as ε is not an element of these sets.

2.2. Sub-additive closure

We will see in the following parts of this book that in network calculus the convolution and minimum operators play an important role. However, two other operators are also widely used: the sub-additive closure and the deconvolution, which will be detailed in the following two sections.

The sub-additive closure is based on the Kleene star operator that can be defined in any dioid. This operator is mainly used to compute solutions of affine equations In the specific case of the dioid of the (min,plus) functions, this operator is closely related to the sub-additive closure of a function.

2.2.1. Kleene star operator

In this section, we define the Kleene star operator for the general dioid, and then the generic notations ㊉ and are used. Remember that from Theorem 2.1, we have an order relation for the dioid

DEFINITION 2.9 (Kleene star operator).– Let (, ㊉, ) be a complete dioid. The Kleene star operator of is

We can also define the “plus” operator:

Then, a∗ = ea+ and a+ = a a∗.

LEMMA 2.4.– If is a complete dioid:

  1. 1)
  2. 2)

PROOF.– 1) We first prove by induction that if a b, then for all Indeed, this is true for i = 0 and i = 1, and using the isotony of the convolution, and by isotony of the minimum,

2) By associativity and idempotency, we have

Similarly,

Finally,

We now state the main result of this section: we exhibit a solution for the equation x = ax ㊉ b.

THEOREM 2.3 (Kleene star theorem).– Let (,㊉, ) be a complete dioid and Then, ab is the least solution of

PROOF.– First, let us check that x = ab is solution of equation [2.5]:

Now, suppose that x is a solution of equation [2.5]. Then, x = axb and the order relation of the dioid implies that x ax and x b. By isotony of the product , we have, for all

2.2.2. Sub-additive closure

We now specify the Kleene star operator for the dioid of the (min,plus) functions and show the relations with the sub-additive closure of a function. Let us first start with the definition of a sub-additive function.

In this section, we use the framework of the dioid of (min,plus) functions and its notations. In particular, remember that the order of the dioid is the reverse of the natural order:

DEFINITION 2.10 (Sub-additive function).– A function f ∈ is sub-additive if and only if

[2.6]

Some examples of sub-additive functions are:

  • the constant functions equal to K if K 0;
  • – linear functions with σ 0;
  • – the ceiling function

Sub-additive functions are stable for some operators like the addition or the convolution, but not for the minimum. For example, consider This is the minimum of two sub-additive functions, but f(1.25) = min(2, 2.5) = 2 > so f is not sub-additive.

We now prove the stability by the addition and the convolution.

PROPOSITION 2.4 (Properties of sub-additive functions).– Let f, g be two sub-additive functions. Then:

  1. 1) f + g is sub-additive;
  2. 2) fg is sub-additive.

A useful case is that f + K is sub-additive if f is sub-additive and K 0.

PROOF.– Let f and g be two sub-additive functions.

  1. 1)
  2. 2)

Let us now focus on the Kleene star operator for the dioid of the (min,plus) functions.

DEFINITION 2.11 (Sub-additive closure operator).– Let f be a function of ,

[2.7]

Note that by distributivity and associativity of the minimum and the addition, for all

and

The notation f is used instead of f since we are in the dioid of (min,plus) functions, and to highlight the difference in the generic dioid framework.

Figure 2.2. Computation of the sub-additive closure of a function. For a color version of this figure, see www.iste.co.uk/bouillard/calculus.zip

Figure 2.2 shows the construction of the sub-additive closure of function if t 1 and otherwise. It is performed by computing fi for all and taking the minimum of these functions. The name sub-additive closure is due to properties that we now explain.

LEMMA 2.5.– If f is sub-additive such that f(0) < 0, then f(0) = -∞ andt > 0, f(t) ∈ {–∞, +∞}.

PROOF.- If f(0) < 0, then f(0 + 0) f(0) + f(0), and the only solution is f(0) = -∞. For all t > 0, f(t) = f(t + 0) f(t) + f(0). As +∞ is absorbing, there are two solutions: f(t) ∈ {–∞, +∞}.

PROPOSITION 2.5.– For all is sub-additive, f f and either f (0) = 0, if f(0) 0,or f(0) = −∞, if f(0) < 0.

PROOF.– First,

Second,

so so f is sub-additive.

Finally, if f(0) < 0, then f(0) < 0, and from Lemma 2.5 f(0) = -∞ necessarily. If f(0) 0, then for all Thus, f(0) = f0 (0) = e(0) = 0.

LEMMA 2.6.– If f is sub-additive and f(0) 0, then f = f.

PROOF.– On the one hand, we already proved that f f in Proposition 2.5. On the other hand, if f is sub-additive, By isotony of the convolution, for all Moreover, if f(0) 0, then f e = f0. Finally,

THEOREM 2.4.– For all is the largest sub-additive function less than f such that f(0) 0. In other words,

[2.8]

This explains why f is called the sub-additive closure of f.

PROOF.– Suppose that is a sub-additive function such that g f and g(0) 0. By isotony, we have g f. But, from Lemma 2.6, g∗ = g, so g f.

Finally, the following relation between the minimum, convolution and sub-additive closure operators will be useful, especially when it comes to computing the sub-additive closure of a function.

PROPOSITION 2.6.– Let f, g F. Then, (f ˄ g) = fg.

PROOF.– For all

The following corollary is obtained by applying Proposition 2.6 with g = e, but it is also a direct consequence of Lemma 2.4.

COROLLARY 2.1 (Efficient sub-additive closure).– Let f be a function. Then,

[2.9]

PROOF.– Apply Proposition 2.6 with

2.3. Deconvolution

The last operator frequently used in network calculus is the deconvolution operator. It can roughly be seen as an inverse operator of the convolution. However, as the structure of the (min,plus) dioid is not a field, only a pseudo-inverse can be defined. This operator appears in the general framework of residuation in complete dioids and lattice theory. As a result, we will first present the most basic concepts of residuation before specializing them to the (min,plus) dioids.

2.3.1. Residuation theory

In algebraic structures such as fields, where all of the elements except the null element have an inverse (for all a, there exists a unique b such that a · b = 1), it is easy to define an inverse operator (b is denoted by a-1, and an operator “/” can be defined as a/b = a · b-1). This is obviously not possible in a dioid. However, in complete dioids, the greatest solution of an inequality can be defined. Indeed, we have seen that complete dioids have a lattice structure. In particular, we are interested in the greatest solution of x a b.

In this section, we again use the generic notations of dioids. ㊉ and are used, and the dioid order relation is proved in Theorem 2.1. Moreover, we do not assume that the dioid is commutative.

We do not aim here to give a complete view of residuation, but only present the minimum framework to give some understanding on the relation between the deconvolution operator that will be defined in the next section and the residuation. The interested reader can refer, for example, to [BAC 92, GON 02].

Consider a complete dioid. Define the right-hand side multiplication operator by as

[2.10]

As the dioid is complete, the product distributes over infinite sums to the right, and for all

A mapping that satisfies this property is said to be lower semi-continuous. Now, we define as, for all

This mapping is well defined because of the completeness of the dioid. We then say that Ra is a residuated mapping, and is its residual mapping.

The mappings Ra and satisfy the general properties of residuated and residual mappings. In particular, we have

Indeed,

and

is called the right-quotient and leads to the residuation operator: for all

and we have the equivalence

Note that the left-product and left-quotient can be defined in the same way. When the dioid is commutative, these notions coincide with the right-product and right-quotient.

2.3.2. (min,plus) deconvolution as a residuation operator

We now specify the quotient to the complete dioid (, ˄, ∗) and we denote and call (min,plus) deconvolution this quotient. By the last equivalence, we have (recall that the order induced by the dioid is the opposite of the natural order):

This equivalence defines a residuation operator in (, ˄, ∗), which we call the (min,plus) deconvolution.

DEFINITION 2.12 ((min,plus) deconvolution).– Let f, g ∈ be two functions. The deconvolution of f by g, denoted is defined as

[2.11]

Function f g is therefore the least solution of the inequation hg f. In the following, we will write deconvolution instead of (min,plus) deconvolution.

The next proposition enumerates some properties of the deconvolution operator. Note that, except for the last one, those properties are consequences of the algebraic structure of the dioid and are consequently true for every complete dioid.

PROPOSITION 2.7 (Properties of the deconvolution).– Let f, g, h be three functions of the complete dioid . The following properties hold:

  1. 1)
  2. 2)
  3. 3)
  4. 4)
  5. 5)
  6. 6)
  7. 7)
  8. 8)
  9. 9)

More properties of the residuation can be found in [BAC 92].

PROOF.– 1) and 2) are a rewriting of the definition of the residuation operator.

3) Take f = in the equivalence 1). Then, for all and Ø g is necessarily , the smallest element of .

4) If f g, then So with we obtain

5) If f g, then As a result, using

6) f ˄ g g, so by 4), Similarly, hence the result.

7) Let We have the following equivalences using the associativity of the convolution:

8) Let We have the following equivalences using the commutativity of the convolution:

9) We use the well-known inequality F(x, y). For all t 0,

The relation between the convolution operator and the deconvolution is natural as it comes directly from the definition of the deconvolution. Some properties can also be established between the sub-additive closure or the maximum (denoted ˅) and the deconvolution. Here again, when possible, we write proofs that use the algebraic properties of these operators to show that these properties are true in a much more general setting.

PROPOSITION 2.8 (Deconvolution and maximum).– Let f, g and h be three functions of :

  1. 1)
  2. 2)

PROOF.– These equalities are direct consequences of the associativity of the maximum operator: for all The other equality is proved in the same way.

PROPOSITION 2.9 (Deconvolution and sub-additive closure).– Let f and g be two functions of :

  1. 1)
  2. 2)
  3. 3)

PROOF.– 1) If f = f, then f is sub-additive, f(0) 0. Then, f Ø f(t) f(t) - f(0) f(t), and f f Ø f. Moreover, f = ff, so and f f Ø f. Then,

Conversely, if f = f Ø f, for all so f is sub-additive. Moreover, By Lemma 2.6, f = f.

2) f(0) 0, so gf (gf) Ø f. On the other hand, f = ff, so using the associativity of the convolution, we can write gf (gf) ∗ f. This is equivalent to gf (gf) Ø f and hence gf = (gf) Ø f.

3) f(0) 0, so g Ø f (g Ø f) ∗ f. On the other hand, g Ø f = g Ø (ff) = (g Ø f) Ø f. So we can write g Ø f (g Ø f) Ø f, which is equivalent to (g Ø f) ∗ f g Ø f. Thus, g Ø f = (g Ø f) ∗ f.

2.4. Link with (max,plus) dioid

Similarly to the (min,plus) dioid, the (max,plus) dioid can be defined as {-∞}, ˅, +), where ˅ is the maximum operator. We set The null element is –∞, and the unit element is 0. The translation from the (min,plus) dioid to the (max,plus) dioid is done by replacing an element with its opposite:

As a result, in the (max,plus) dioid, the dioid order is the same as the natural order:

and the dioid of (max,plus) functions can be defined in the same way as it was done for the (min,plus) dioid. In particular, we can define the (max,plus) deconvolution, the super-additive closure and the (max,plus) deconvolution, respectively, as

  • (max,plus)-convolution:
  • (max,plus)-deconvolution:
  • super-additive closure: and for all

Note that the super-additive closure is super-additive, i.e.

All properties of the dioid of (max,plus) function can be deduced by symmetry from those of the dioid of (min,plus) functions, or by noting that the replacement with the opposite, used in equation [2.12], is also valid for the operators on functions:

The attentive reader will have noted that the canonical order in (max,plus) is the opposite of that of (min,plus), so the properties based on the canonical order must be inverted while those based on the natural order must be preserved. Therefore, some are listed here:

[2.15]
[2.16]
[2.17]

For example, equation [2.14] is obtained from equation [2.13]: if f g, then −f g. Now, from equation [2.4], −f ∗ −h g ∗ −h, leading to Finally,

Sometimes, (min,plus) and (max,plus) operators can be mixed as in the following proposition.

PROPOSITION 2.10.– For all

PROOF.–

2.5. Summary

Dioid structure: (, ˄, ∗) is a commutative dioid.

Operator Definition Characterization
Min.
Conv.
Deconv.
Sub-add. cl.

Isotony properties:

Useful equalities: (Propositions 2.6, 2.7 and 2.9)