# 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.

Figure 1

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

*x*∈ R

^{+}:

*x*(

*t*

_{1}) ≥

*x*(

*t*

_{2}), if

*t*

_{1}≥

*t*

_{2}, 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

*of functions in F or*

**points***in general, ≤ and ≥ denote order in the conventional sense.*

**numbers**## 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

*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:

*x*∈ R

^{+}∪ {+∞}:

*x*(

*t*

_{1}) ≥

*x*(

*t*

_{2}), if

*t*

_{1}≥

*t*

_{2}, and

*x*(

*t*) =

*x*(0), ∀

*t*< 0}.

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

*a*⊕

*b*)(

*t*) =

(

*a*⊗

*b*)(

*t*) =

*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
*xσ*
and
*xβ*.
In this case,

*x*≥ (

*x*⊗

*σ*) or

*x*=

*x*⊕

*xσ*,

*y*≤ (

*x*⊗

*β*) or

*xβ*=

*xβ*⊕

*y*.

Notice the inversion in the inequality, due to
the definition of sum in dioid
**C**.

**Remember:** In **C**,
*a* ≥ *b*
⇔ ∀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*) =

(

*a*∧

*b*)(

*t*) =

T(

*t*) =

0,

*t*> 0;

if

*t*≤ 0;

*a*(

*t*),

*b*(

*t*)};

0.

The residuations of the product are defined as

*a*⊂⊃ \

*y*)(

*t*) = (

*y*⊂⊃ /

*a*)(

*t*) =

*y*(

*t*+

*s*) -

*a*(

*s*)}

^{+},

^{s ≥ 0}

sup {

*y*(

*s*) -

*a*(

*s*)}

^{+},

^{s ≥ 0}

*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

*t*≤

*D*, 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

*δ*are useful to represent delay constraints. Finally, mappings

_{D}*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*) =

*a*(

*s*) -

*b*(

*s*)]

^{+},

^{s ≥ t}

inf [

*a*(

*s*) -

*b*(

*s*)]

^{+},

^{s ≥ 0}

*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*(

*t*)δ

^{t}.

^{t ∈Z}

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

*f*⊕

*g*:

*f*⊗

*g*:

*f*⊕

*g*)(

*t*) =

(

*f*⊗

*g*)(

*t*) =

*f*(

*t*),

*g*(

*t*)},

min {

*f*(

*s*) +

*g*(

*t-s*)}.

^{s ∈Z}

Moreover,

*a*⊂⊃ \

*y*=

*y*⊂⊃ /

*a*:

*a*⊂⊃ \

*y*)(

*t*) = (

*y*⊂⊃ /

*a*)(

*t*) =

*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:

*a*⊕

*b*= 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,
∀*a* ∈
**R**[[δ]]/δ^{-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},

^{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*) +

*B*]δ

^{t}.

**Delay functions:** Given
*D* ∈ R_{+∞},
define
*δ _{D}* ∈

**C**’ as

*δ*(

_{D}*t*) = δ

^{D}.

Function
*δ _{D}*
satisfies the following equality:

*x*⊗

*δ*=

_{D}^{t ∈N}

*x*(

*t*)δ

^{t+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:

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

*y = F*{

*x*

_{1},…,

*x*

_{M}} =

*F*

_{k=1,…,M}{

*x*

_{k}}

**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*=

*x*⊕

*yλ*

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

*y*=

*y*⊕

*yσ*.

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

*xβ*=

*xβ*⊕

*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*

*δ*⊕

_{D}*y*. 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}

*σ*= sup {

_{y}*σ*(

*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

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.)

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.

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).

Last update: 2012-11-22

© 2009-2012 · Mabia Cavalcante