159
1 INTRODUCTION
The so-called network calculus as defined and
developed by the authors of publications cited in
References at the end of this paper is a theoretical
framework for analysis of performance guarantees in
communication networks. And performance is a key
criterion for any system. Further, system designers
tend to produce systems with the highest
performance at the lowest cost. Communication
systems share resources and are very hard to
forecasting.
The network calculus framework (Le Boudec J.-Y.
& Thiran P. 2012) offers an environment for
consideration of computer networks in terms of the
worst case analysis. This method is based on the so-
called min-plus algebra (Le Boudec J.-Y. & Thiran P.
2012). And in real-time systems, the worst case
analysis proves to be more useful than the
calculations that are based on averaging probabilistic
parameters characterizing queues. This concerns
mostly the cases where we want to know the
boundaries for the so-called Quality of Service (QoS)
parameters of a network in order to predict its critical
behavior. However, there are also cases where a more
sophisticated and detailed evaluation of a network is
needed. Then, the usual network calculus as
mentioned above, which is also called a deterministic
network calculus, must be evolved and widened.
This is done within a framework that is called a
stochastic network calculus (Jiang Y. 2006). And a
stochastic service curve plays a fundamental role in
it, similarly as a deterministic service curve in the
deterministic network calculus. This paper presents a
general model of the stochastic service curve for
communication networks in a new perspective.
The remainder of the paper is organized as
follows. Section 2 introduces the concept of a
stochastic service curve. In Section 3, we discuss a
method of evaluation of the available bandwidth in a
network through the service curve estimation. In the
next section, a new approach to modelling of
stochastic service curves for communication
networks is presented. Finally, Section 5 concludes
Consideration of a General Model of Stochastic Service
Curve for Communication Networks
K. Wasielewska
The State University of Applied Sciences in Elbląg, Elbląg, Poland
A. Borys
Gdynia Maritime University, Gdynia, Poland
ABSTRACT: In this paper, a general framework for modelling stochastic service curves for communication
networks is presented. It connects with each other two approaches to the traffic analysis and performance
evaluation of communication systems, namely, the one which is called a deterministic network calculus with its
stochastic counterpart. Thereby, it enables to treat any communication traffic in a consistent way. Further, as we
show here, it enables also achieving new results. Derivation of the above model is presented in details in this
paper. Finally, some hints are given how the method presented in this article could be applied in maritime
telecommunications area.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 13
Number 1
March 2019
DOI: 10.12716/1001.13.01.16
160
the paper as well as provides some hints on how the
method presented in this article could be applied in
maritime telecommunications area.
2 STOCHASTIC SERVICE CURVE
As already mentioned, a fundamental tool in the
network calculus framework is a service curve.
Further, note that in computer networks the traffic
service in a node (as well as on an end-to-end path) is
a stochastic process. The randomness of flows results
from the fact that nodes simultaneously support
different kinds of traffic derived from different
networks as well as from different nodes of a
network considered. From the reason of traffic
aggregation, nodes experience a cross traffic, which
depends on time and is transmitted at different
speeds. In addition, a technology (for example radio
communication), random actions and preferences of
users influence the randomness. And, see that a
stochastic service curve models very well the
phenomena mentioned above. Furthermore, it
describes the bounds for traffic streams in a system
and is able to take into account the events and
behavior described above.
A stochastic service curve can be defined as a non-
random function with an error function describing
the probability of violating performance boundaries
or as a random process.
In the literature, there are a few definitions of the
stochastic service curve. The definition of Cruz (Cruz
R. L. 1996), which describes the stochastic service
curve as a non-random function, is considered to be a
basic one.
DEF1: Definition of the stochastic service curve
after Cruz is the following. Let denote A(t) an arrival
function applied to a system and D(t) the related
departure function. And we assume that they
represent the corresponding random processes.
Further, we say that the system offers a stochastic
service curve S(t) if for
0t and 0k
,PDt A St k k
(1)
where
k
is called a deficit profile (or an error
function) that represents the probability of violating
restrictions imposed on the service. In the above
expression, the symbol
means the convolution
operator in the min-plus algebra,
Pevent stands
for the probability of an event indicated, t is a time
variable, and k denotes a modelling parameter of the
error function
k
mentioned above
It can be shown that all the other published
definitions of stochastic service curves for systems
governed by a single traffic stream (single-input
systems) - as non-random functions - can, in
principle, be derived from the Cruz’s definition given
above. They can be obtained through bigger or
smaller modifications of this definition. And then,
they are called differently as, for example, a statistical
or an effective service curve (Burchard A., Liebeherr
J., Patek S. D. 2002), (Burchard A. & Liebeherr J. &
Patek S. 2006). In these works, a probabilistic version
of the service curve (that is a stochastic one) is
defined as follows:
DEF2: A non-decreasing and non-negative
function
S is named an effective service curve with
the probability of violation
if for 0t we have
1,PDt A St
(2)
where an arrival curve
At and the related
departure curve
Dt in the time period
0, t are
the representatives of the corresponding random
processes.
The so-called leftover service curve (Fidler M. 2010)
is used in the traffic analysis and calculations, when a
traffic system possesses two or more inputs. That is in
cases of consideration of multi-input traffic systems.
The leftover service curve plays an important role
in many performance analyses of networks as shown,
for example, in (Fidler M. 2010) and other references
referred to as in this paper. However, it provides a
rather pessimistic estimation of the service available
to a stream in a system that is also crossed by some
other streams (that is such a one that experiences the
so-called cross traffic). Also, it is worth noting here
that there occur in the literature a few variants of this
curve (Ciucu F., Burchard A., Liebeherr J. 2005), (Li
C., Zhang S., Wang W. 2013), (Burchard A., Liebeherr
J., Patek S. D. 2002), (Li C., Burchard A., Liebeherr J.
2003), and (Burchard A., Liebeherr J., Patek S. D.
2006).
Let us now illustrate, in more detail, the concept
of the above curve exploiting an example. To this
end, we use Fig. 1 that shows two competing streams:
F
1 and F2, where a server named here S2 schedules the
aggregated traffic, while an another server named S
1
supports only the flow F
1. In order to calculate a rate
of the flow F
1 on the path of the connected nodes in
Fig. 1, we need to know how much service received
the F
1 flow on the S2 server.
S
1
S
2
F
1
F
2
Figure 1. The traffic flowing through a network of
interconnected n nodes (here n=2).
Finally at this point, we note that for the
calculations indicated above we can use one of the
theorems published in the literature that regard the
leftover service curve. For example, we can utilize a
theorem that was formulated and proved in (Xie J.
2011).
Note now that to make the leftover service curve a
more optimistic performance measure in analyses of
multi-input networks we can proceed similarly as in
the case just discussed of the usual service curve. We
can simply do this by expressing the leftover service
curve in terms of the probability theory applied along
the lines of DEF1 and DEF2.
Without going into details of partly troublesome
and sophisticated considerations related with the
161
notion, definition, and derivation of the
corresponding expressions describing the so-called
stochastic leftover service curve, presented in (Ciucu F.,
Burchard A, Liebeherr J. 2006) and (Ciucu F. 2007),
we say about, here, only what follows.
DEF3: Let the cross-traffic to a given traffic system
can be bounded by the so-called path envelope
denoted here as
c
Et with an overflow profile
k
. Then, this system offers a stochastic leftover
service curve
tc
St St Et
to its
through-traffic with
k
meaning the deficit profile
k
occurring in (1) that is applied to the through-
traffic of the system considered. Moreover, the
symbol
x t
in the expression above denotes
the operation of finding a maximum value in the set
(
)
{
}
,0xt for each time instant. Furthermore, with
regard to the topic of traffic envelopes, note that a
detailed material on this stuff is presented, for
example, in (Le Boudec J.-Y., Thiran P. 2012), (Fidler
M. 2010), and (Jiang Y. 2006).
Example definition of the stochastic service curve
assumed to be a random process can be found in
(Ciucu F. 2007). And for its formulation, we need to
define first a process that is called an almost surely
ordering of random varables.
DEF4: After (Ciucu F. 2007), we say that a random
variable X is almost surely smaller than a random
variable Y , and we write this as
X
Y a.s., if
0PX Y .
Second, we must use another definition of the
convolution operation in the definition of the
stochastic service curve. It is different from the
standard one that is used in the min-plus algebra, i.e.
different from the one which was denoted by
in
the considerations above. It can be defined as follows
(Ciucu F. 2007).
DEF5: Let us denote representatives of two
random doubly-indexed processes
12
,
B
tt and
12
,Gt t as
12
,bt t and
12
,gtt , respectively.
Then, their convolution, named an “indexed” one to
distinguish it from the previous one, is defined as
,in ,f ,
i
ust
bus g stbgut
(3)
for
0 ut
. Note also that because of the reasons
mentioned above the convolution symbol used in (3)
is slightly different than before, namely
i
.
And finally now, we are able to define the
stochastic service curve as a random process. It is called
also the statistical service curve with a.s. ordering and its
definition after (Ciucu F. 2007) is the following.
DEF6: A nonnegative, doubly-indexed random
process
12
,St st t can be regarded as a
service curve (in the sense of a random process),
when for an arrival process
At (which needs to
be re-indexed to
12
,
A
tut s ), the
corresponding departure process
Dt satisfies
. .
i
Dt A St as (4)
for all
0t and after applying 0u there.
It is also worth noting at the end of this section
that using the concept of the a.s. ordering the leftover
service curve as a random process can be also
formulated. This was done Fidler in (Fidler M. 2006).
3 AVAILABLE BANDWIDTH ESTIMATION
One of the key problems of ensuring high quality of
services provided in packet networks is the
estimation of bandwidth available between the
sender and the recipient. Formally, the available
bandwidth B on a route at time t means that unused
bandwidth, which can be utilized by an application
without any influence of the transmission quality of
flows occurring on this route. The available
bandwidth depends on time t. If there occur n nodes
on an end-to-end path, then the available bandwidth
B on this path at a time t is given by
1, ,
min ,
i
in
B
tBt
(5)
where
i
B
means an available bandwidth in the i-th
node.
Knowledge about available bandwidth on an end-
to-end path may be useful for the correct operation of
many network applications as, for example, VoIP,
Audio/Video, P2P, network games or services on
demand. Estimation of the available bandwidth can
be also very useful in the process of selecting a route
in overloaded networks or verifying the s-called
Service Level Agreements (SLAs). Transmission
conditions on an end-to-end path can change
dynamically and in an unpredictable way, so
estimating the available bandwidth a priori is not an
easy task. There are two classes of methods for
estimating the available bandwidth: active and
passive ones (Liebeherr J., Fidler M., Valaee S. 2010).
Active methods involve sending traffic samples and
analyzing their statistics after reaching the
destination. Among many tools available for this
purpose are, among others, the following ones: IGI,
Pathload, pathChirp - description of these methods
can be found in (Strauss J., Katabi D., Kaashoek F.
2003). However, all these methods just mentioned
require performing an installation on the both sides
of a tested path, which is not always possible. Passive
measurements, on the other hand, involve capturing
traffic in a working network and then analyzing it.
Although it is a fast and light-weight method while
conducting the analysis one should remember about
the changing network conditions and the influence of
buffers, control mechanisms, and cross flows on the
analyzed flow.
In (Liebeherr J., Fidler M., Valaee S. 2010), an
available bandwidth estimation method that utilizes
a service curve estimator
S
was conceived. And the
service curve estimator
S
derived in (Liebeherr J.,
Fidler M., Valaee S. 2010) is given by the following
formula:
,
PP
SD A
(6)
162
where
P
Dt means a traffic departure function
and
P
A
t
is a traffic arrival function. The latter is
understood a stream that comes from a traffic trace of
one or more flows. Both the functions describe a
cumulative traffic that is they are sums of bits in the
outgoing and incoming traffic, respectively, in the
time period
0, t
. Note also the use of the
superscript “P” in the symbols
P
Dt and
P
At
to indicate that these are network data probes.
Moreover, the symbol
in (6) stands for a
deconvolution operator that is defined in the sense of
the min-plus algebra as
0
supfgt ft g
(7)
for functions f and g. Liebeherr J., Fidler M., and
Valaee S. in their publication (Liebeherr J., Fidler M.,
Valaee S. 2010) shown that the estimator
S
given by
(6) can be viewed as the best possible estimate of an
actual service curve that can be obtained from the
available measurements of
P
A and
P
D .
4 GENERAL FRAMEWORK FOR STOCHASTIC
SERVICE CURVE MODELLING
The Internet environment is changing dynamically.
Because of this reason and also due to traffic
aggregation and multiplexing, any deterministic type
of estimation gives weak results. Furthermore, the
cross traffic is always present in real networks.
Therefore, because of the reasons mentioned above,
when we calculate a service curve for any node
and/or any traffic system working in a real
environment, it will be and should be considered as a
one understood in the sense of the stochastic leftover
service curve or a related one. And once again, we
remind here that just this type of the service curve
shows how much bandwidth actually is left for the
through traffic in a network.
Furthermore, the randomness of the service curve
follows clearly from what was said at the beginning
of this section. That is it must be considered as a
stochastic process. And, in this context, the definition
DEF6 referred to as above only supports this fact.
Novelty of our approach to modelling the
stochastic service curve, which we present in this
paper, relies, first of all, upon an assumption that a
service curve as a random process possesses
generally two parts. One of them is deterministic and
the second strictly stochastic.
Second, we treat here representatives of the
service curve random process as time series and
utilize widely tools that are available in the literature
for their analyses. Our observations of time series
related with service curves show that principally the
following components: (a) a deterministic trend, (b) a
strictly stochastic part, and (c) random disorders can
be recognized in them. In what follows, we present a
general model of the stochastic service curve which is
based on the above findings.
Suppose
s
St
and
b
St
are random
processes, and
d
St is a (deterministic) function.
Then, a stochastic service curve as a random process
I
St, which combines - through an addition
operation - the two processes mentioned above,
assumes the following form:
,
Idsb
St St St St
(8)
where
d
St stands for a deterministic part of the
service curve,
s
St means its stochastic part, and
b
St
represents a random errors, noise etc.
Note that it is also possible to model the stochastic
service curve in a multiplicative way, when the
processes
s
St and
b
St are multiplied with
each other. Then, the form of the “multiplicative”
stochastic service curve
II
St
assumes the
following form:
.
II d s b
St StSt St
(9)
Observe also that expressions (8) and (9) simplify
to
Idb
St St St (10)
and
,
II d b
S t S t const S t
(11)
respectively, in the absence of a strictly stochastic
component in a service curve. In (11), const means a
constant.
Further, note that in publications regarding time
series analyses the components
d
St and
s
St
occurring in formulas (8) and (9) are called a
deterministic trend and a stochastic trend,
respectively.
As well known, any stochastic process (in our case
a one-dimensional one) is characterized by giving the
corresponding probability distributions (which can
change with the passing of time). Equivalently, other
parameters as, for example, moments or the
characteristic function of a random variable (which in
our case is dependent upon time) can be provided.
However, this means of a stochastic process
characterization is oft too complicated from the
practical point of view, and therefore rather not used
in the network calculus.
Sometimes, however, it is enough to know only
one representative of a given stochastic process. That
is a one time series that characterizes its behavior. It
can, for example, be obtained by performing
measurements. In what follows, we describe how to
obtain such a time series for the stochastic service
curve
.
I
St Note however that this is not an
obvious task because in fact this series is hidden in
measured data. That what is available are measured
data regarding the input and output flows of bits to a
system (or node). And just to obtain the time series of
I
St, we need to carry out a processing these data.
To this end, we will use the Liebeherr, Fidler and
Valaee method (called here shortly the LFV method),
which was already mentioned and cited above
(Liebeherr J., Fidler M., Valaee S. 2010).
163
In the setting considered in this section, the input
and output traffic to a node or a system, which are
represented in (6) by the cumulative arrival
P
At
and departure
P
Dt functions, respectively, are
considered to be time series associated with
(representatives of) the stochastic processes
P
At
and
P
Dt
. And note that just this understanding
and interpretation allows us to apply (6) to obtain
from it a time series of
I
St. Then simply, (6)
describes a relation existing between the three time
series indicated above.
Now, in more detail, we calculate an estimator of
the time series of
I
St (being an representative of
the stochastic process
)
I
St using (6). That is the
following:
.
PP
I
St D At
(12)
The question how reliable is the estimator
I
St
given by (12) in evaluation of the available
and/or utilized bandwidth in a traffic node or a traffic
system is not trivial. This was noted and also
discussed in (Wasielewska K. 2014) and
(Wasielewska K, Borys A. 2019). Here, however, we
do not consider this topic.
It has been shown in (Liebeherr J., Fidler M.,
Valaee S. 2010) that for linear systems (that is for
those in which
PP
DAS
is satisfied) the
following relation:
St St
(13)
holds for each value of t. In (13),
S means the
system’s service curve. So, after applying this result
in our case, we get
II
St St
. (14)
It follows from (14) that
I
St
is a lower service
curve in the sense of a lower time series for a one of
the unknown time series which describe the system’s
service curve understood as a random process.
It can be shown (Liebeherr J., Fidler M., Valaee S.
2010) that when a traffic node or a traffic system
behaves nonlinearly, then determining of
P
P
SD A
gives only a lower bound for an
upper service curve
S defined by the following
relation:
DAS
. (15)
So, in this case, we will have
St St
(16)
satisfied for each value of t. And after applying the
latter result in our considerations regarding the
notion of a service curve represented by one of its
time series, we obtain
II
St St
. (17)
See that according to (17)
I
St
represents a
lower bound for a one of the unknown upper bound
time series which describe (indirectly) the system’s
service curve understood as a random process.
Let us now return to consideration of a traffic
system that behaves linearly. And, let
S mean the
difference between the system’s real service curve
and its estimator. That is
0.
II
St S t S t (18)
for each value of t. Further, note that then
e
St St can be considered as a systematic
error related to the approximation operation.
Therefore, we can write
.
IIe
St St St
(19)
And substituting (19) into (8) gives
.
Idsbe
St S t St St St
(20)
The components
b
St and
e
St are random,
therefore we rewrite (20) as
,
Idsbe
St St St S t
(21)
where
be b e
St St St . And this result
means that
I
St
is an estimator of
ds
St St
.
So, let us rewrite (21) as
.
Ids
St St St
(22)
Finally, (22) shows that after calculating the
service curve estimator
I
St
according to the
formula (12), one should separate, from each other,
the deterministic trend
d
St
from the stochastic
trend
s
St in the series obtained (that is in
).
I
St
In fact, they will form their estimates
d
St
and
s
St
, respectively.
Note now that we can proceed similarly in the
case of considering a nonlinear traffic system.
Therefore, the results and interpretations will be then
also similar. Only difference will regard the estimator
s
St
. Here, it will be interpreted as the estimator of
the stochastic part of the time series
I
St.
Observe further that we do not know whether a
traffic node or a traffic system which has a service
curve that is a random process behaves linearly or
nonlinearly. In other words, we do not know which
of the following three relations:
PP
I
Dt A St
,
PP
I
Dt A St
, and
PP
I
Dt A St actually holds for an actually
analyzed representative (time series) of the random
process
I
St, in a given moment t. And obviously,
the changes between these two working regimes of
the system analyzed, which are mentioned above,
will be random. That is we will have periods of time
in which the system will behave as a linear one and
also such ones in which it will behave nonlinearly.
We also emphasize here the fact that even the same
164
representative of the random process
I
St will
show the linear as well as the nonlinear behavior.
Of course, the behavior of all the representatives
of the random process
I
St will be similar. So, for
the same traffic node or a traffic system, they will
show different periods of linear and nonlinear
behavior. That is in the sense that their lengths and
times of occurrence will be random.
Note now that it follows from the above remarks
and the previous considerations that when we
calculate the estimators
I
St
using the formula (6),
we in fact do not know whether it is in the sense of
the estimator of the process
I
St or of the process
I
St. So, it follows from the above that the
estimator
I
St
for a given traffic system achieved
in our calculations will be partly more accurate and
partly less accurate. An obviously, we will not know
in which periods the former parts will occur and
where the latter ones. Simply because their
occurrences will be random.
Finally in this section, we would like to say that
the model presented here has been intensively
exploited and validated in (Wasielewska K. 2014).
There have been presented many results of
simulations which prove its usefulness.
5 CONCLUSIONS
A general novel framework for modelling stochastic
service curves for communication networks has been
proposed in this paper. It relies upon exploiting some
basic tools of the theory of stochastic processes as
well as the tools developed in the literature for
analysis of time series. All the definitions of
stochastic curves, which have been formulated and
discussed in the literature, and which are also
referred to as in this paper, can be derived along the
lines of our novel approach presented in this article.
We will continue the theme of this paper. Mainly
because of the fact that the methods of the stochastic
network calculus are very promising in solving many
traffic problems we are interested in as, for example,
those which occur in the areas of the so-called
advanced autonomous waterborne applications and
remotely controlled ships. In our view, they are also
very important for optimization of remote control
systems for vehicles.
REFERENCES
Burchard A., Liebeherr J., Patek S. 2006. A Min-Plus
Calculus for End-to-end Statistical Service Guarantees,
IEEE Transactions on Information Theory, 52(9): 4105-4114.
Jiang Y. 2006. A Basic Stochastic Network Calculus,
Proceedings of the ACM SIGCOMM, 36(4): 123-134.
Le Boudec J.-Y., Thiran P. 2012. Network Calculus: A
Theory of Deterministic Queuing Systems for the
Internet, Online Version of the Book Springer Verlag -
LNCS 2050.
Cruz R. L., 1996. Quality of service management in
Integrated Services networks, Proceedings of the 1st Semi-
Annual Research Review, Center of Wireless
Communication, UCSD.
Burchard A., Liebeherr J., Patek S. D. 2002. A Calculus for
End-to-end Statistical Service Guarantees, Technical
Report: University of Virginia, CS-2001-19 (2nd revised
version).
Xie J. 2011. A Temporal Network Calculus for Performance
Analysis of Computer Networks, Phd Thesis.
Ciucu F., Burchard A., Liebeherr J. 2005, A network service
curve approach for the stochastic analysis of networks,
Proceedings of ACM SIGMETRICS, 279-290.
Li C., Zhang S., Wang W. 2013. Network Calculus Based
Performance Analysis of ForCES SCTP TML in
Congestion Avoidance Stage, Information Technology
Journal, 12(4): 584-593.
Ciucu F. 2007. Scaling Properties in the Stochastic Network
Calculus. University of Virginia: Ph.D. Thesis.
Li C., Burchard A., Liebeherr J. 2003. A Network Calculus
with Effective Bandwidth", Technical Report: University
of Virginia, CS-2003-20.
Strauss J., Katabi D., Kaashoek F. 2003. A measurement
study of available bandwidth estimation tools, in
Proceedings of the 3rd ACM SIGCOMM conference on
Internet.
Liebeherr J., Fidler M., Valaee S. 2010. A system-theoretic
approach to bandwidth estimation, IEEE/ACM
Transactions on Networking, 18(4): 1040-1053.
Fidler M. 2010. A survey of deterministic and stochastic
service curve models in the network calculus, IEEE
Commun Surveys & Tutorials, 12(1): 59–86.
Ciucu F., Burchard A, Liebeherr J. 2006. Scaling properties
of statistical end-to-end bounds in the network calculus,
IEEE/ACM Trans. Networking, 14(6): 2300–2312.
Fidler M. 2006. An end-to-end probabilistic network
calculus with moment generating functions, in IEEE
14th International Workshop on Quality of Service (IWQoS),
261–270.
Wasielewska K. 2014. Wykorzystanie stochastycznego
rachunku sieciowego w analizie, projektowaniu i
serwisowaniu sieci komputerowych, in Polish, Phd
Thesis.
Wasielewska K, Borys A. 2019. Bandwidth estimation using
network calculus in practice, International Journal of
Electronics and Telecommunications (IJET), 65(1): 133-138.
