Network Calculus and Dioid Algebra

Introduction

In this section, we use dioid algebra to re-expose Network Calculus. The idea is to rewrite the expressions that appear in Network Calculus as linear equations in dioid algebra.

To be adequate to deal with Network Calculus, a dioid has to be able to represent not just regulation and service curves, but also constraints related to performance bounds, e.g., delay and backlog constraints. It must as well be able to represent multiplexing and demultiplexing of traffic flows.

Next, we present the dioid commonly used in the Network Calculus literature and show that there are other dioids that are not just suitable to Network Calculus, but in fact the obtained expressions in these new dioids are simpler than the expressions in the literature.

Review

From section Network Calculus, a minimum system for the NC is formed by a filter that limit burstness of input flows and a network that can offer some guarantee of service (Figure 1). The first part is associated with regulation curves; the second part, with service curves.

basicNCSystem
Figure 1

Define F the set of non-decreasing positive real functions equal to zero for t < 0, i.e.,

F = {x ∈ R+: x(t1) ≥ x(t2), if t1t2, and x(t) = 0, ∀t < 0}

Given x,σ,β ∈ F with x(0) = σ(0) = β(0) = 0, we say that σ and β are, respectively, a regulation and a service curve for x if, t ∈ R+:

x(t) ≤   inf {x(s) + σ(t-s)};
0 ≤ s ≤ t
y(t) ≥   inf {x(s) + β(t-s)}.
0 ≤ s ≤ t

In this section, we use the following convention for ordering:
- When comparing entire functions in F, ≤ and ≥ denote order in a given dioid;
- When comparing points of functions in F or numbers in general, ≤ and ≥ denote order in the conventional sense.

The convolution approach

The structure F = (F,min,+), where sum means “min” and product means “+”, is a dioid. Regulation and service curves can be expressed in terms of convolutions in dioid F.

Consider the convolution between functions x and h given by

(x * h)(t) = ∫ t 0 x(s) · h(t-s) ds.

As integrals represent sums, if we exchange sum by infimum and product by sum, the above expression changes to

(1) (x * h)(t) =   inf {x(s) + h(t-s)}.
0 ≤ s ≤ t

For this reason, the expression in (1) is commonly called “min-plus convolution” in the Network Calculus literature.

From the definitions of regulation and service curves and (1), σ,β F are, respectively, a regulation and a service curve for a flow x if x(0) = σ(0) = β(0) = 0 and t ∈ R+,

x(t) ≤ (x * σ)(t),
y(t) ≥ (x * β)(t).

The Product Approach

The NC literature always represent regulation and service curves in terms of convolutions in F. Here, a different approach is presented. Consider set C defined as:

C = {x ∈ R+ ∪ {+∞}: x(t1) ≥ x(t2), if t1t2, and x(t) = x(0), ∀t < 0}.

Notice that in C functions can assume value +∞. Define the following operations in C:

(ab)(t) =
(a b)(t) =
 min {a(t), b(t)},
 inf {a(t) + b(t-s)}.
s ∈R

The structure C = (C,⊕,⊗) with and ⊗ as above is also a dioid. In C, regulation and service curves can be defined, respectively, as functions of the products and . In this case,

x ≥ (x σ) or   x = x,
y ≤ (x β) or = y.

Notice the inversion in the inequality, due to the definition of sum in dioid C.
Remember: In C, ab ⇔ ∀t: a(t) ≤ b(t).

The reason to redefine the product in this “convolution” way is the simplicity of the expressions obtained and the added possibility to explore the properties of residuations of this product.

Dioid C

The structure C is a complete commutative dioid. In C, t:

ε(t) =
e(t) =
(ab)(t) =
T(t) =
+∞;
{
+∞,
0,
if t > 0;
if t ≤ 0;
max {a(t), b(t)};
0.

The residuations of the product are defined as

(a \ y)(t) = (y / a)(t) =
{
 sup {y(t+s) - a(s)}+,
s ≥ 0
 sup {y(s) - a(s)}+,
s ≥ 0
if t ≥ 0,

if t < 0.

The above expression for t ≥ 0 is very similar to the expression presented in the NC literature as the “min-plus deconvolution”. The min-plus deconvolution is used in the determination of some performance bounds as presented in section Network Calculus.

The “min-plus deconvolution” in the NC literature can lead to results that are not in F [1], i.e, that are outside of the chosen dioid. This inconvenient is satisfactorily overcome by the residuations in C.

Special Elements and Mappings in C

There are some elements and mappings in C that are particularly interesting to represent performance constraints. They are presented next.

Vertical displacement functions: Given B ∈ R+∞ = R+ ∪ {+∞}, define λB C as λB(t) = B, if t ≤ 0, and λB(t) = +∞, if t > 0.

Function λB satisfies the following equality, t: (x λB)(t) = x(t) + B .

Delay functions: Given D ∈ R+∞, define δD C as δD(t) = 0, if tD, and δD(t) = +∞, otherwise.

Function δD satisfies the following equality, t: (x δD)(t) = x(t - D).

Functions of the type λB are useful to represent backlog constraints and functions of the type δD are useful to represent delay constraints. Finally, mappings F and G below are useful to represent multiplexing and demultiplexing of traffic flows, respectively.

Mappings F and G : Given a,b C, define ∀t:

(F{a, b})(t) = a(t) + b(t);
(G{a, b})(t) =
{
 inf [a(s) - b(s)]+,
st
 inf [a(s) - b(s)]+,
s ≥ 0
if t ≥ 0,

if t < 0.

Dioid C

Sections Further Definitions and Dioid of Power Series are necessary to understand dioid C’. Alternatively, you can go directly to section Basic Network Constraints.

In the following, we define a dioid of formal power series for treating Network Calculus problems. Dioids of formal power series are very useful to make finite representations of infinite functions. Moreover, there are tools for manipulating these series already implemented, e.g., see [2]-[3].

Consider a discrete time model, where a discrete function x(t) : Z → R+∞ denotes the quantity of data that passes through a given point of a network during the interval (0,t].

Given dioid R = (R+∞,min,+) (Example 2), any function x(t) : Z → R+∞ can be associated to an element of dioid R[[δ]], by the following way:

x =
x(tt.
t ∈Z

In dioid R[[δ]], from section Dioids of Formal Power Series we have:

fg:
f g:
(fg)(t) =
(f g)(t) =
 min {f(t), g(t)},
 min {f(s) + g(t-s)}.
s ∈Z

Moreover,

a \ y = y / a:
(a \ y)(t) = (y / a)(t) =
 max {y(t+s) - a(s)}+,
s ∈Z

Example: Consider a,b R[[δ]] defined as a = 5δ2 ⊕ 7δ7 and b = 2δ. The following equations are satisfied:

ab = 2δ ⊕ 5δ2 ⊕ 7δ7
a b = (5 2)δ2+1 ⊕ (7 2)δ7+1 = 7δ3 ⊕ 9δ8 = b a
b \ a = (2 \ 5)δ2-1 ⊕ (2 \ 7)δ7-1 = 3δ ⊕ 5δ6 = a / b

From dioid R[[δ]], it is possible to define dioid R[[δ]]/δ-1. In this new dioid, aR[[δ]]/δ-1 : a = a-1)* .

The elements of R[[δ]]/δ-1 are classes of power series, whose representative elements (i.e., the greatest element of each class) have non-decreasing coefficients in t. In R[[δ]]/δ-1:

ε =

t ∈Z
(+∞)δt,
e =

t ≤ 0
t

t > 0
(+∞)δt,
(+∞)δt = (δ-1)*.

Now, consider the subset C’ of R[[δ]]/δ-1 whose elements satisfy the condition x(t) = x(0), ∀t < 0. C’ is a subdioid of R[[δ]]/δ-1.

Special Elements and Mappings in C

Similar to dioid C, we can define vertical displacement functions, delay functions and mappings to represent multiplexing and demultiplexing in dioid C’.

Vertical displacement functions: Given B ∈ R+∞, define λB C’ as follows: λB = B = B-1)*.

Function λB satisfies the following equality:

(x λB)(t) =

t ∈N
[x(t) + Bt.

Delay functions: Given D ∈ R+∞, define δD C’ as δD(t) = δD.

Function δD satisfies the following equality:

x δD =

t ∈N
x(tt+D.

Mappings F and G : Given a,b C’, define:

F{a, b}:
G{a, b}:
(F{a, b})(t) = a(t) + b(t);
(G{a, b})(t) = [a(s) - b(s)]+.

Basic Network Constraints in C and C

To be adequate to deal with Network Calculus, a dioid has to be able to represent not just regulation and service curves, but also delay and backlog constraints, as well as multiplexing and demultiplexing of traffic flows. These constraints can express performance specifications or physical limitations of systems.

Next, we describe five types of constraints: flux constraints, coupling constraints, regulation constraints, service constraints and backlog constraints. This set of constraints covers a large set of Network Calculus problems and can be expanded as needed.

Flux constraint: Guarantees that the quantity of data that leaves a system, y, is never greater than the one that enters in it, x. In C and C’ this constraint can be equally written as:

y = y ⊕ x.

Coupling constraint: Allows the modeling of systems whose output traffic is the multiplexing of its input traffics. Let xk, k = 1,…,M, be the input flows and y be the output flow. In C and C’:

y = F{x1,…,xM} = Fk=1,…,M{xk}

Backlog constraint: Represents limitations on buffer capacity. An element has maximum backlog capacity B > 0, if t: x(t) - y(t) ≤ B. In C and C’, this inequality can be written as:

x = xB

Regulation constraint: Shapes the input traffic, limiting its burstness. In C, the output y of the regulator is given by:

y = y.

Service constraint: Represents (or is related to) the minimum quantity of data served by a network element. In C and C’:

= y.

Delay constraints are not included in the set of basic constraints, because they are a particular case of a service constraint, when β is of the type δD.

A system has maximum virtual delay limited by D when, t: x(t) ≤ y(t+D). Equivalently, s:
x(s-D) ≤ y(s). This inequality can be written in C and C’ as: x δD = x δDy. Therefore, delay constraints can be represented by service constraints where β = δD.

Performance Bounds in C and C

Consider a network with input flow x (limited by a regulation curve σ) and output flow y. The network offers a service curve β between x and y.

As presented in section Network Calculus, it is possible to obtain bounds for the maximum delay and backlog between the input flow x and the output flow y, respectively D and W, and a regulation curve σy for y. We have

D = inf {d ≥ 0: σ(t) ≤ β(t+d), ∀t};
W = sup {σ(s) - β(s)};
s ≥ 0
  σy = sup {σ(t+s) - β(s)}.
s ≥ 0

In C and C’, these equations can be rewritten as

δD = inf {δd: σ*δdβ};
W = (β \ σ*)(0);
  σy = β \ σ*.

The infimum that appears in the first equation is an infimum in dioids C or C’.

Bibliography

  1. J.-Y. Le Boudec and P. Thiran.(2003, June) Network Calculus- A theory of deterministic queueing systems for the Internet. (pdf)- Last access: November 22nd, 2012.)


  2. S. Gaubert, “Théorie des Systèmes Linéaires dans les dioïdes,” 1992. PhD Thesis. L'École Nationale Supérieure des Mines de Paris, Paris 1992.


  3. L. Hardouin. “Data processing tools to handle periodic series in dioid,” http://www.istia.univ-angers.fr/~hardouin/outils.html (Last access: November 22nd, 2012).


Back to top ↑

Last update: 2012-11-22

© 2009-2012 · Mabia Cavalcante