3.1.1. Convolution and deconvolution of the usual classes of functions

PROPOSITION 3.4 (Catalog of convolutions).–

1. 1) For all
2. 2) For all .
3. 3) For all .
4. 4) For all .
5. 5) For all .

No expression involving a staircase function is given since no simple analytic expression exists. To handle such curves, we may prefer to use algorithms which will be presented in Chapter 4. The convolution of a staircase function by a guaranteed rate is illustrated in Figure 3.2.

PROOF.– 1) and 2) are direct applications of Proposition 3.2.

3) For all .

4) .

5) From Proposition 3.1, and . Then, from Proposition 2.6, , and it is enough to prove that is sub-additive (trivially . Without loss of generality, we can assume that and (the other cases are symmetric or such that is either smaller or greater than ). There exists a unique t₀ > 0 such that . For all and for all , . Let . If , then . The same holds for with replaced by . Suppose that . Then .

□

Before introducing the catalog of deconvolution, let us define the linear function . Note that , leading, from Proposition 2.1, to .

PROPOSITION 3.5 (Catalog of deconvolutions).–

1. 1) For all .
2. 2) For all .
3. 3) For all .
4. 4) For all .
5. 5) For all .
6. 6) For all .

As in the catalog of the convolution, no expression involving a staircase function is given. An illustration is shown in Figure 3.2.

PROOF.– 1), 2) and 3) are direct applications of Proposition 3.2.

4) and 5) are a direct consequence of 6), by taking T = 0 and b = 0.

6) From the definition of the deconvolution, for all . As is non-decreasing and for all u < T, we can write .

The supremum is obtained for u = T when , hence . On the other hand, if and .

□

3.1.2. Horizontal and vertical deviations for the usual classes of functions

Let us first recall from Definition 1.5 the horizontal and vertical deviations:

We can now note that .

In practice, pure delay functions play a very important role in network calculus. The following results are often used to have a fast implementation of horizontal deviation when the second argument is a pure delay function. We prove it formally although it is quite intuitive as shown in Figure 3.3.

PROPOSITION 3.6 (Horizontal deviation and pure delay functions).– For all , and ,

[3.4]

[3.5]

PROOF.– For all and all u > d, , so , and .

We will show a slightly stronger result than the second statement: the result holds if for all t > 0, f (t) > 0. Indeed, in that case, for all , so for all . This is true for all , so , hence .

□

PROPOSITION 3.7 (Catalog of deviations).–

1. 1) For all .
2. 2) For all .
3. 3) For all .
4. 4) For all .

PROOF.– 1) is the direct application of Proposition 3.6.

3) and 4) are direct applications of Proposition 3.5, using the relation hDev(f, g) = f g(0).

, so = 0. For all t > 0,

So , and , and +∞ otherwise.

□

3.2.1. Pseudo-inverse of a function

For a bijective function (especially when is strictly increasing), inverse functions can be defined: for each value , there exists a unique t ∈ such that , and we can set . However, in the network calculus context, we deal with functions that are only non-decreasing, so we have to deal with the notion of pseudo-inverse instead.

DEFINITION 3.3 (Pseudo-inverse).– Let be a non-negative and non-decreasing function. Then, pseudo-inverse is defined by ,

[3.8]

The definition of pseudo-inverse is illustrated in Figure 3.6. An inverse cannot be defined as for all t ∈ [2,3], = 2. With our definition, , and . Note that other definitions of pseudo-inverse exist, for example, by replacing the non-strict inequality by a strict inequality. When considering two pseudo-inverses, two different notations must be used, like in [BOY 16] or in [LIE 17].

Our choice has been driven by the preservation of the left-continuity of the function, as it will be proved in Proposition 3.8. First, Lemma 3.2 gives an alternative equivalent definition of the pseudo-inverse.

LEMMA 3.2.– Let be a non-decreasing function. Then, for all ,

[3.9]

Before proving this lemma, let us introduce a notation that will be used in the next two proofs: , where . For example, .

PROOF.– We have to prove that . First note that form a partition of . Indeed, for all t ∈ , either (and t ∈ ), or . Moreover, as is non-decreasing, is an interval of the form (it can be either open or closed on the left): if t ∈ , then for all , and by consequence, is an interval of the form . Finally, .

□

In the proof, we also showed that if is non-decreasing, then and .

PROPOSITION 3.8 (Pseudo-inverse properties).– Let be a non-negative and non-decreasing function, then:

1. 1) .
2. 2) Pseudo-inversion relations: for all t ∈ and all ,
   [3.10]
   [3.11]
3. 3) is left-continuous.

PROOF.– 1) First, let be such that . Then , so , and is non-decreasing.

Second, , so 0 ∈ , and , which is equivalent to .

2) The first set of implications can be expanded to:

and the second set is the contraposition of the first set.

3) Fix . We have from Lemma 3.2 and let us denote . We want to show that for any increasing sequence converging to converges to t. As is non-decreasing, we have that, for all , so (t_n) is converging to some value . Moreover, .

Suppose that . Then, there exists s such that < s < t. For all , . The third implication comes from (3). As converges to x, this means that , and then .

□

PROPOSITION 3.9 (Catalog of pseudo-inverses).–

1. 1) For all if and otherwise.
2. 2) For all d ∈ .
3. 3) For all .
4. 4) For all R, T ∈ R > 0.

The fact that the pseudo-inverse is idempotent (i.e. in these examples is not a general property, but due to the left-continuity of the functions, and their belonging to . For example, the function defined by and have the same pseudo-inverse.

3.2.2. Convolution and continuity

In this section, we continue our investigations regarding the (left-)continuity of the function, with regard to the (min,plus) convolution. Indeed, the convolution is defined as an infimum, and one important problem that arises in network calculus is knowing whether that infimum is a minimum or not. Roughly speaking, for the convolution of and g, this would imply the existence of s such that , and simplify the reasoning.

PROPOSITION 3.10 (Convolution infimum can be a minimum).– Let be two non-decreasing functions:

1. 1) if and g are left-continuous, then ∀t ∈ , ∃s ∈ [0, t] such that
2. 2) if g is continuous, then ∀t ∈ , ∃s ∈ [0, t] such that .

The proof of the first statement is taken from [BOU 11a, Lemma 1] and the second from [LEB 01, Th 3.1.8].

PROOF.– Note that if the functions are non-decreasing, exists for all x ∈ (possibly +∞).

1. 1) Fix t ∈ and define . Let (u_n) be a sequence such that F(u_n) is decreasing and converges to . As for all n u_n ∈ [0, t], a compact set, there exists a subsequence of (u_n) that converges. Let us denote this limit by u. Moreover, it is possible to extract from this subsequence another subsequence that is either increasing or decreasing. Let us assume that (u_n) is this subsequence and, without loss of generality, that it is also increasing (by exchanging the role of and g and replacing (u_n) by (t - u_n) if needed).

   As is left-continuous, and, as g is left-continuous and non-decreasing, lim_n→∞ g(t - u_n) g(t - u). Then, lim_n→∞ F(u_n) F(u). As a result, F reaches its minimum on [0, t].

2. 2) The previous proof is modified as follows: consider a sequence (u_n) converging to u defined previously. Without loss of generality, (u_n) is either increasing or decreasing. If (u_n) is increasing, then and if (u_n) is decreasing, then . As g is continuous, then lim_n→∞ g(t - u_n) = g(t - u). Therefore, in any case, lim_n→∞ F(u_n) F(u-), and there exist sequences where F(u-) is reached ((u_n) = (u - 1/n), for example), hence the result.

□

PROPOSITION 3.11 (Continuity of the convolution).–Let be two non-decreasing functions. If and g are left-continuous, then, so is * g.

PROOF.– For all s ∈ , define . The left-continuity of F_s directly follows from that of g, and for all . The latter equality is because is non-decreasing. Note that from Lemma 3.10, this is a minimum, and we denote one value by u_t such that (if u_t is not unique, it can be chosen arbitrarily).

Fix t ∈ and (t_n) a non-decreasing sequence converging to t. To prove the left-continuity of at t, we need to show that converges to , with .

As in the previous proof, we can extract from (u_n) a converging and increasing sequence (by exchanging the roles of and g if needed), and then assume without loss of generality that (u_n) is increasing, and denote its limit by u. We have where g₊ is either g(t - u) or g(t - u+), depending on how t_n - u_n is converging.

On the other hand, from Lemma 2.3, is non-decreasing, so , and finally .

□

3.3.1. Concave functions

We deal in this section with the concave functions, and we mainly state that concave functions are almost a sub-class of sub-additive functions defined in Chapter 2. Let us first recall the definition of a concave function:

DEFINITION 3.4 (Concave function).– A function is concave if and only if

[3.12]

Graphically, the arc drawn between two points of a concave function is below the function, as depicted in Figure 3.7. The interested reader may refer to [ROC 97] for a more complete reference to concave functions. Concave functions of are also continuous on {0}.

The next proposition states some useful properties of concave functions regarding the (min,plus) operators.

PROPOSITION 3.12 (Properties of concave functions).– Let , g be two concave functions. Then:

1. 1) + g is concave;
2. 2) ∧ g is concave;
3. 3) if is sub-additive;
4. 4) . In particular, if ;
5. 5) if , then .

We can deduce from these properties that the set of concave functions is a sub-dioid of (the zero and unit elements are concave).

These properties have a huge practical impact on computational aspects of network calculus. First, the computation of the convolution can be reduced to the computation of the minimum, which is usually a simpler operation to perform.

Note that sub-additive functions that are not concave do exist. For example, we can check that the function is sub-additive as , but is not continuous on (0, +∞), hence it is not concave.

Based on these properties, the class of concave piecewise linear functions will be presented in section 4.2.

1. PROOF.– 1) ,
   

   so + g is concave.

2. 2) ,
   

   Similarly, . Therefore,

   

   and ∧ g is concave.

3. 3) If , then for all t ∈ and all . Now, for all s > 0, set and , we can write
   

   which proves that is sub-additive.

4. 4) First assume that (0) = g(0) = 0. We know that ∀t ∈ and , and qg(t) g(qt). Then, , and we can write, using p = s/t and q = (t – s)/t,
   

   with equality when or . Therefore, .

   In the general case, we have

   

   and the result with and can be applied.

5. 5) By Corollary 2.1, . But, f is concave and , so is also concave, hence sub-additive, and . Thus, by Lemma 2.6, .

□

3.3.2. Convex functions

The class of convex functions has different properties regarding the (min,plus) dioid. Indeed, convex functions are not stable by the minimum, hence they do not form a sub-dioid. However, an equivalent of the Fourier transform (the Legendre–Fenchel transform) can be defined, and the convolution corresponds to the addition in the space of the transforms, which will translate into efficient algorithms in Chapter 4. This also enables us to prove the stability of the convex functions by the convolution.

Let us first recall the definition of a convex function.

DEFINITION 3.5 (Convex function).– A function is convex if and only if

In other words, f is convex if and only if is concave and the next proposition is a direct consequence of Proposition 3.12. Moreover, we note that the functions that are both convex and concave are exactly the linear functions (satisfying .

The two first points of the next proposition are deduced using the duality of (min,plus) and (max,plus) dioids and Proposition 3.12.

PROPOSITION 3.13 (Properties of convex functions).– Let f and g be two convex functions of . Then:

1. 1) is convex;
2. 2) is convex;
3. 3) is convex.

PROOF.– For all and all , with ,

□

We are now ready to define the Legendre–Fenchel transform [ROC 97]. As already mentioned, it can be roughly seen as the equivalent of the Fourier transform in the classical algebra. However, as is not a field, the space where this transform in an involution is not the whole space . We will see that there is a close relation with convex functions. This transform has already been used in the network calculus literature to efficiently compute performance bounds [FID 06a] or in the context of a formal series of the idempotent semi-ring [BUR 03, COH 89].

DEFINITION 3.6 (Legendre–Fenchel transform).– The Legendre–Fenchel transform of the space is the mapping defined by

We are now ready to define the Legendre–Fenchel transform [ROC 97]. As already mentioned, it can be roughly seen as the equivalent of the Fourier transform in the classical algebra. However, as is not a field, the space where this transform in an involution is not the whole space . We will see that there is a close relation with convex functions. This transform has already been used in the network calculus literature to efficiently compute performance bounds [FID 06a] or in the context of a formal series of the idempotent semi-ring [BUR 03, COH 89].

DEFINITION 3.6 (Legendre–Fenchel transform).– The Legendre–Fenchel transform of the space is the mapping defined by

The next proposition gives some examples of computations of Legendre–Fenchel transforms.

PROPOSITION 3.14 (Examples of Legendre–Fenchel transforms).–

1. 1) For all .
2. 2) For all .
3. 3) For all .

PROOF.– 1) For all . If , the supremum is reached for and ; if is not bounded and .

2) For all , since .

3) For all . Similar to the first case, the supremum is unbounded when , and the supremum is obtained for when , so that .

□

Note that it is also possible to deduce (3) from (1) and (2) using the third property of the next result: the convolution corresponds to the addition in the transform space.

PROPOSITION 3.15.–

1. 1) is convex and non-decreasing;
2. 2) ;
3. 3) ;
4. 4) if f is convex and non-decreasing, then .

PROOF.– 1) Let with . Then, , so is non-decreasing.

Let and . Then,

Thus, is convex.

2)

3)

4) Let f be a convex and non-decreasing function of . First, . Indeed, for ,

Fix and we obtain that .

Next, we need to show the equality. For this, let us introduce the concept of a supporting line. We say that f has a supporting line at of slope if , i.e. the affine function of slope α that meets f at x is below f. It should be obvious to an alert reader (if not, the reader can refer to [RoC 97] for the basic properties of convex functions) that a non-decreasing convex function has supporting lines at each point either f is differentiable at x and the slope is unique and equal to , or f is not differentiable and the possible slopes form an interval. This interval is where and are respectively the left and right derivatives of f at x. Moreover, f can be characterized as the infimum of all its supporting lines. Now, if f has a supporting line at x of slope , then has a supporting line at of slope x. Indeed, on the one hand, , as the minimum is reached for . On the other hand, for any (taking ). Thus, .

Now, if has a supporting line at of slope x, then has a supporting line at x of slope , and then and f has exactly the same set of supporting lines, so they are equal.

□

We can see from points 2) and 3) of this proposition that is a (non-injective) homomorphism. Therefore, the following equivalence relation is a congruence, i.e. an equivalence relation compatible with operations and of

[3.13]

Therefore, all functions that have the same Legendre–Fenchel transform belong to the same equivalence class modulo

[3.14]

Another consequence of the last point of this proposition is that is an involution over the sets of convex non-decreasing functions, and the convolution of two functions can be computed with the formula .

Note that, here, we only deal with non-decreasing functions. In fact, the result can hold in the more general framework of convex functions when the functions are defined on and not (hence the result about the stability of convex functions regarding the convolution could be stated without the non-decreasing property).