Journal of Applied Mathematics and Physics, 2014, 2, 987-995
Published Online October 2014 in SciRes. http://www.scirp.org/journal/jamp
http://dx.doi.org/10.4236/jamp.2014.211112
How to cite this paper: Klehmet, U. and Berndt, R. (2014) Alternative Approaches of Convolution within Network Calculus.
Journal of Applied Mathematics and Physics, 2, 987-995. http://dx.doi.org/10.4236/jamp.2014.211112
Alternative Approaches of Convolution
within Network Calculus
Ulrich Klehmet, Rüdiger Berndt
Computer Networks and Communication Systems Friedrich-Alexand er-Universität, Erlangen, German y
Email: ulrich.klehmet@cs.fau.de, ruediger.berndt@cs.fau.de
Received Ju ly 2014
Abstract
Network Calculus is a powerful mathematical theory for the performance evaluation of communi-
cation systems; among others it allows to determine worst-case performance measures. This is
why it is often used to appoint Quality of Service guarantees in packet-switched systems like the
internet. The main mathematical operation within this deterministic queuing theory is the min-
plus convolution of two functions. For example the convolution of the arrival and service curve of
a system which reflects the datas departure. Considering Quality of Service measures and per-
formance evaluation, the convolution operation plays a considerable important role, similar to
classical system theory. Up to the present day, in many cases it is not practical and simple to per-
form this operation. In this article we describe approaches to simplify the min-plus convolution
and, accordingly, facilitate the corresponding calculations.
Keywords
Network Calculus, Min-Plus Convolution, Algebraic Laws, Convex Analysis
1. Introduction
Timeliness plays an important role regarding systems with real time requirements. This Quality of Service (QoS)
requirement can be found in many kinds of embedded systems which permanently exchange data with their en-
vironment; like safety-critical automotive systems or real time networks. Since knowledge of mean values is not
sufficient, analytical performance evaluation of such systems cannot be based on stochastic modeling as applied
in traditional queuing theory. For these systems worst-case performance parameters like maximum delay of ser-
vice times are required. In order to specify guarantees of performance figuresin terms of bounding values
which are valid in any casea mathematical tool Network Calculus (NC) as a novel system theory for determi-
nistic queuing theory has been developed [1].
The development of this theory has been started by Cruz [2] [3] on the
( )
,
σρ
traffic description and his
calculus for network delay. Further steps towards NC were taken by the work of Parekh and Gallagher [4] to
determine the service curve of Generalized Processor Sharing (GPS) schedulers. The NC framework has been
successfully applied for the analysis and dimensioning in various domains, including industrial automation net-
works [5] or automotive communications bus systems [6].
This article is structured as follows, in Section 2 we describe the basic modeling elements of NC theory. The
U. Klehmet, R. Berndt
988
subsequent Section 3 demonstrates the difficulties of convolution calculation and describes possible solution
approaches. Finally, Section 4 draws a conclusion and indicates future steps.
2. Basic Modeling Elements of Network Calculus
The most important modeling elements of NC are the arrival curve (denoted by
α
in the figure s) and the ser-
vice curve (denoted by
β
in the figures) together with the min-plus convolution. The arrival and the service
curve are the basis for the computation of maximum deterministic boundary values like backlog and delay
bounds [1].
Definition 1 (Arrival curve) Let
( )
t
α
be a non-negative, non-decreasing function. Flow
F
with input
( )
xt
at time t is constrained by or has arrival curve
( )
t
α
iff
( )()()
xtxst s
α
− ≤−
for all
0ts≥≥
. Flow
F
is also called
α
-smooth.
Example 1 A commonly used arrival curve is the token bucket constraint:
(1)
Figure 1 shows an arrival curve which represents an upper limit for a given traffic flow
( )
xt
with an aver-
age rate
r
and an instantaneous burst
b
. Therefore:
( )()()
,rb
xtxst s
α
−≤ −
.
For
:t ts∆=−
and
0
t
∆→
:
( )()
{}
{ }
0
lim lim
ts t
xtxsrt bb
→ ∆→
−≤⋅∆ +=
(2)
Next the convolution operation, which plays the most important role in Network Calculus will be defined.
Definition 2 (Min-plus convolution) Let
( )
ft
and
( )
gt
be non-negative, non-decreasing functions that
are 0 for
0t
. A third function, called min -plus convolution is defined as
()( )()()
{ }
0
inf
st
fgtf sgts
≤≤
⊗ =+−
(3)
On this basis we can characterize the arrival curve
( )
t
α
with respect to a given
( )
xt
as:
( )()()
xt xt
α
≤⊗
In other words, arrival curves describe an upper bound to the input stream of a system. Considering the sys-
tem’s output, we might be interested in service guarantees: like a minimum of output
( )
yt
, i.e. the amount of
data that leaves the system. The following definition deals with this problem.
Definition 3 (Service curve) Let a system
S
with input flow
( )
xt
and output flow
( )
yt
be given. The
system provides a (minimu m ) service curve
( )
t
β
to the flow, iff
( )
t
β
is a non-negative, non-decreasing
function with
( )
00
β
=
and if
( )
yt
is lower bounded by the convolution of
( )
xt
and
( )
t
β
, i.e.:
Figure 1. Token bucket arrival curve.
U. Klehmet, R. Berndt
989
( )()( )
yt xt
β
≥⊗
(4)
Figure 2 shows
()( )()()
{ }
0
inf
st
xtxst s
ββ
≤≤
⊗ =+−
as lower bound of output
( )
yt
and input
( )
xt
.
Such service curves are functions of the time and describe the service of network elements like routers or sche-
dulers in an abstract manner [7].
Example 2 A commonly used service curve of practical applications is the rate-latency function:
( )( )
[ ]
{ }
,:max 0,
RT
tt RtTRtT
ββ
+
==⋅− =⋅−
(5)
This function reflects a service element which offers a minimum service of rate
R
after a worst-case latency
of
T
. Since we want to analyze the worst-case performance, it is possible to abstractly model the complex in-
ternal behavior of the node by just describing the worst-case service using this curve. This is very important in
practical utilization.
In Figure 4, the (green) line depicts the rate-latency service curve with rate
R
and latency
T
.
Consider a system with input flow
( )
xt
, arrival curve
( )
t
α
, output flow
( )
yt
and service curve
( )
t
β
.
According to [1] the following three bounds can be derrived:
Backlog Bound
v
:
( )()( )()()
{ }
0
sup
s
vtxt ytss
αβ
=−≤ −
Delay Bound
d
in case of FIFO service:
( )()
{}
{ }
0
inf :
sup
s
d ss
ταβτ
≤ ≤+
Output Bound
( )
t
α
:
( )()()
{ }
0
:sup
s
tts s
α αβαβ
= =+−
Rema rk:
The complete backlog
( )( )( )
vtxt yt= −
at time
t
within a system is also called unfinished work or buffer
( )
t
. The expression
( )()
{ }
inf :ss
ταβ τ
≤+
is called virtual delay: the minimal time distance which is ne-
cessary for input
x
for being served to output. Thus, the backlog and delay bound are the maximal vertical and
horizontal deviation between arrival and service curve. Figure 3 depicts
d
and
v
for a given arrival- and
service curve.
Example 3 Let a system with a token bucket-smooth input and rate-latency service be given, thus:
( )()()
,rb
xtxst s
α
−≤ −
and
Figure 2. Convolution as a lower output bound.
U. Klehmet, R. Berndt
990
( )()()
{ }
,
inf
s tRT
ytxst s
β
≥ +−
.
Based on the three bounds above we can calculate the delay bound as
b
dTR
≤+
, the output bound as
( )()
trt Tb
α
= ++
, and the backlog bound as
vb rT= +
. Figure 4 shows these results.
3. Difficulties of the Convolution Operation
Within the Network Calculus (NC) the o ry, the convolution operation of so-called min-plus algebra is considered
the most essential operation. This is because—based on the arrival- and service curveit computes the depar-
ture of a network element, therefore it is the main instrument of analytical performance evaluation. For example
in [1], this operation is carried out by handusing pure analytical calculation.
Take Example 3 for which
,,rb RT
αβ
as the lower bound for output
,,
:
rb RT
yy
αβ
≥⊗
needs to be com-
puted.
3.1. Analytical Computation of Convolution Operator
a)
0:tT≤≤
Figure 3. Backlog and delay bound.
Figure 4. Example for the bounds.
U. Klehmet, R. Berndt
991
( )
( )()
[ ]
{ }
( )
{ }
( )
,, ,,,
infinf000 0
rb RTrbrbrb
st st
tts RsTts
αβ ααα
+
≤≤
⊗= −+−= −+=+=
b)
:tT>
( )
( )
( )
[ ]
{ }
( )
[ ]
{ }
( )
[ ]
{ }
( )
[ ]
{ }
( )
{ }
() ()
{ }
( )
{ }
( )
{ }
( )
{ }
{ }
( )
{ }
( )
{ }
( )
{ }
( )
{ }
( )
{ }
( )
{ }
,,
,
, ,,
inf
inf inf inf
inf0 inf0
inf
rb RT
rb
st
rbrb rb
sTT stst
sTT st
Tst
t
tsRs T
tsRs TtsRs TtsRs T
b rt sb rt sRsTRtT
brtT brtRTRrsRtT
brtT brtTRtT
brtT RtT
αβ
α
α αα
+
+ ++
≤≤≤ =
≤ <<
<<
++
=−+ −
=−+ −∧−+ −∧−+ −
=+ −+∧+ −+−∧+−
= +−∧+−+−∧−
=+−∧+−∧ −
=+−∧− .
(6)
Here
{ }
min ,A BAB∧=
and convolution
( )
,,rb RT
αβ
with result (6) is depicted in Figure 5.
For the following convolution of two rate-latency service curves (concatenation) a similarly complex calcula-
tion is requir e d .
( )
112212 12
,,
min ,,
RT RTRRT T
ββ ββ
+
=⊗=
(7)
As we can see from above, this analytical approach is cumbersome and error-prone. But, similar to convolu-
tion of classical systems theory, the convolution
is of great importance for NC theory. This is why we are
looking for other more elegant methods to computation.
Next, two alternative approaches called Use of algebraic laws and Use of convex analysis will be introduced.
3.2. Use of Algebraic Laws
In the following, the NC-relevant functions
Φ
are defined as non-negat i ve , non-decreasing, and passing
through the ori gin:
( )
( )
( )
{ }
1 010
:0 ,00fftftttfΦ=≥≥∀≥=
(8)
Among others, the following algebraic properties for the set of functions
Φ
can be found in literature [1]
Figure 5. Convolution of
,,rb RT
αβ
.
U. Klehmet, R. Berndt
992
Rule 1 (Commutativity of
):
f gg f⊗=⊗
Rule 2 (Associativity of
):
()( )
f ghfgh⊗⊗=⊗⊗
Rule 3 (Distributivity of
and
):
()() ()
h fghfhg⊗∧=⊗∧⊗
Rule 4 (Addition of a constant):
( )( )
0gKfK gfK⊗+=+⊗∀≥
Rule 5 (Concave functions passing through the origin):
{ }
min ,f gfg⊗=
Rule 6 (Shifting of f to right):
( )()()
T
ftftT
δ
+
⊗=−
with
( )
0
Tt
δ
=
for
tT
and
otherwise.
Now, we only apply these algebraic rules to compute the convolution
.
We consider Example 3 in an even more general form:
( )
,,rb RT
K
αβ
⊗+
with any constant
K
; let
r
rt
λ
= ⋅
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
{ }
,,
Rule1 Rule6Rule4
,, ,,
Rule2Rule5 Rule3
,, ,
Rule6 Rule4 Rule6
,, ,,
rb RT
RTrbT RrbTRrb
T RrbT RrbTRTrb
RTTrRTT rRTrT
K
KK K
KKK
KbKbKb
KbrtTR
αβ
βαδλ αδλ α
δλαδλαδλδα
βδ λβδλββ
+
⊗+
= +⊗=+⊗⊗=+ ⊗⊗
=+⊗⊗ =+⊗∧ =+⊗∧⊗

= +∧⊗+= +∧⊗+= +∧+

=++ −∧
( )
{ }
.tT
+
(9)
Or take the concatenation example:
112 2
,,RT RT
ββ β
= ⊗
:
( )()
( )
( )
( )
( )
( )
( )
()( )( )
( )
( )
{}( )( )
( )
( )
{} ()
( )
( )
1 212
12 12 12
Rule6 Rule2
1 1221212
Rule5 Rule6
12121 2min ,,
min,min,.
T TTT
TT RRT T
R tTRtTRttRttRtRttt
RR tttRRtTT
βδ δδδ
δδ β
++
+
=−⊗−=⊗ ⊗⊗=⊗⊗ ⊗
=⊗⊗=−+ =
(10)
3.3. Use of Convex Analysis
The next approach is based on the theory of convex analysis [8]. Similar considerations related to NC theory can
be found at [9]. However, we go another way considering “incompleteconvex functions. In Rockafellars book
[8] all necessary preconditions for the following definition and proofs of the next theorems can be found.
Definition 4 (Conjugate function) Let
f
be any closed convex function on n
R
.
( )( )
{ }
: sup,dom
t
fsstf ttf
= −∈
is called the conjugate of
f
or Fenchel-tran sfo rm , with
, n
st R
,⋅⋅
the inner product in
n
R
.
Theorem 1 (Conjugate f**) The conjugate
f
∗∗
of
f
is
f
:
( )()
{ }
sup ,dom
s
ftstfssf
∗∗∗ ∗
= −∈
.
Theorem 2 (Convolution) Let
1
,,
n
ff
be proper convex functions on
n
R
. Then:
( )
11nn
fff f
∗∗
⊗⊗= ++
.
Rema rk:
In case of the convex NC functions of
Φ
:
1n
RR
. From Theorem 1 and 2 we get
( )
( )
11nn
ffff
∗∗
⊗⊗ =++
.
Example:
Again the aim is the concatenation
112 2
,,RT RT
ββ β
= ⊗
with
( )
( )
,
: 1,2
0:
ii
ii i
RT i
RtTt Ti
ttT
β
− ≥=
=<
(11)
U. Klehmet, R. Berndt
993
First of all, the conjugate of the rate-latency function
,RT
β
i.e.
,RT
β
needs to be determined. From defini-
tion 4 we know that
()( )
{ }
( )
{ }
supdom sup
tt
sstttstR tT
β ββ
= −∈= −−
(12)
So, we get:
Case 0:s<
( )
s
β
= ∞
Case 0:s=
( )
0s
β
=
( )
: 0
and for Case 0::
Tss R
ss sR
β
<≤
>=
∞>
( )( )
,
: 0
Altogether:: 0
:
RT
s
ssTss R
sR
ββ
∗∗
∞<
= =≤≤
∞>
(13)
Determination of
( )
t
β
∗∗
as conjugate of
( )
s
β
with
doms
β
:
( )()
{ }
{( )
,
: 0
supsup: 0
:
s sRT
s
tstsstTss Rt
sR
ββ β
∗∗ ∗
∞<
=−=−≤≤ =
∞>
(14)
This certainly confirms Theorem 1.
Applying Theorem 2:
( )
12 12
ββ ββ
∗∗
⊗=+
and by applying Theorem 1:
( )()
12 12
ββ ββ
∗∗
⊗=⊗
; here
( )
12
ββ
∗∗
+
.
For the concatenation
112 2
,,RT RT
ββ
we obtain
(let
11
1,RT
ββ
=
and
22
2,RT
ββ
=
,
21
0TT>>
,
21
0RR>>
)
()()( )()()
1 2121122121
12 1
: 0: 0: 0
: 0: 0: 0
: : :
ss s
sssTs sRTs sRTTs sR
sR sRsR
βββ β
∗∗
∞< ∞<∞<
 
 
⊗=+=≤≤ =≤≤=+≤≤
 
 
∞> ∞>∞>
 
(15)
( )
( ){()
1 2121
1
: 0
sup: 0
:
s
s
tstTT ssR
sR
ββ
∗∗
∞<
⇒ +=−+≤≤
∞>
(16)
But this is the same structure as in expression for
( )
t
β
∗∗
and therefore
()
()
( )
11 212 1 2
12, min ,,
RT TRRT T
t
βββ β
∗∗
++
+==
holds. Figure 6 depicts this operation.
Figure 6. Concatenation of two rate-latency functions.
U. Klehmet, R. Berndt
994
In conclusion, the use of convex analysis seems to be a further approach to determine the min-plus convolu-
tion operation—at least in the context of convex functions like the set of piecewise linear functions where
,RT
β
belongs.
Question:
How to deal with non-convex functions
f∈Φ
. Take Example 3 with input
,rb
x
α
=
and service curve
,RT
β
. The min-plus convolution realizes a guaranteed lower bound for the output:
( )
( )
( )
,,rb RT
yt t
αβ
≥⊗
.
( )
,
: 0
But function 0: 0
rb
rt bt
tt
α
+>
==
is not convex because the
relation in:
( )
( )
( )
( )
( )
,0 1,0,1
11
rbrb rb
ttt t
αλλλ αλα
−+ ≤−+
for
01
0, t tR= ∈
and
01
λ
<<
is not fulfilled. Therefore Theorem 1 and 2 are not readily applicable.
However, in contrast to [9] other ways are possible. Here the following one is suggested: making functions
convex by redefining their values at certain points, e.g. where unnatural discontinuities appear (e.g.
0t=
). For
examp le, we change
( )
,rb t
α
to
( )
,rb t
α
such that
( )
,rb
t
α
is convex and still reflects the arrival curve feature
well:
( )
,
for 0
rb
trtbt
α
=+≥
(17)
Now,
,
rb
α
is convex and the principles of convex analysis are applicable. Although
,rb
α
∉Φ
(since
( )
,
00
rb
α
) it represents the important burst feature
( )
:0t ts∆=−→
of the arrival curve
,rb
α
(of formula
2):
( )()
{ }
{}( )( )
00,0,
limlimlim lim
tstt rbt rb
xtxsrtbttb
αα
→∆→∆→ ∆→
−≤⋅∆+= ∆=∆=
.
Since
,,rb rb
αα
the convolution of
( )
{ }
,,
rb RT
brt T
αβ
+
⊗ =+−
differs from
( )
{ }
( )
{ }
,,rb RT
brtTRtT
αβ
++
⊗ =+−∧−
.
The expression
( )
{ }
brt T+
+−
is identical in both formulas. When considering rate-latency functions (c.f.
Example 2) where an incoming input is served with minimal rate
R
after a maximal delay
T
, the output
y
is lower bounded not only by
( )
{ }
brt T
+
+−
but by
( )( )
{ }
min ,brtT RtT
++
+− −
Of course, in the long run
for
t→∞
the term
( )
{ }
brt T
+
+−
is the dominant one, as you can see in Figure 5.
4. Conclusions
The most important operation within the Network calculus is the min-plus convolution. But the calculation of
this fundamental operation still is complex and error-prone. For this reason we introduced other computation
approaches to perform the convolution: here called Use of algebraic laws and Use of convex analysis. In order to
apply the convex analysis we transform non-convex into convex functions (e.g. keeping the token-b ucket arrival
curve property) which is different, for example, from the approach of [9].
This article reflects work in progress and the presented examples ought to demonstrate these techniques. In
future work we will continue to investigate the procedures of subsection 3.2 and 3.3 to answer the following
questions: Can we extend the principles to some classes of non-convex functions or even to mixed classes of
convex and non-convex functions? Which kinds of applications are suited considering algebraic laws and con-
vex analysis? Are there even cases where a combination of both methods is beneficial? To all of these, we want
to find answers in future work.
References
[1] Le Boudec, J.-Y. and Thiran, P. (2001) Network Calculus. Springer Verlag LNCS 2050.
U. Klehmet, R. Berndt
995
[2] Cruz, R. (1991) A Calculus for Network Delay, Part I: Network Elements in Isolation. IEEE Transactions on Informa-
tion Theory, 37, 114-131.
[3] Cruz, R. (19 91 ) A Calculus for Network Delay, Part Ii: Network Analysis. IEEE Transactions on Information Theory,
37, 132-141.
[4] P arekh, A. K. and Gallager, R. G. (1993) A Generalized Processor Sharing Approach to Flow Control in Integrated Ser-
vice Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1, 344-357.
http://dx.doi.org/10.1109/90.234856
[5] Kersch bau m, S., Hielsch er, K., Kleh met, U. and German, R. (2012) Network Calculus: Application to an Industrial
Automation Network. In: MMB and DFT 2012 Workshop Proceedings (16 th GI/ITG Conference), Kaiserslau tern,
March 2012.
[6] Herp el, T., Hi elscher , K. , Kleh met , U. and German, R. (2009) Stochastic and Deterministic Performance Evaluation of
Automotive CAN Co mmunicati on. Computer Networks, 53, 1171-1185.
http://dx.doi.org/10.1016/j.comnet.2009.02.008
[7] Fidler, M. (2010 ) A Survey of Deterministic and Stochastic Service Curve Models in the Network Calculus. IEEE
Communications Surveys & Tutorials, 12, 59-86.
[8] Ro ckafellar, R .T. (1970) Convex Analysis. Princeton University Press.
[9] P and it, K., Schmitt, J., Kirchner , C. and Steinmetz, R. (2004) Optimal Allocation of Service Curves by Exploiting
Properties of the Min-Plus Con volu ti on. Technical Report.