Network calculus

Network calculus is "a set of mathematical results which give insights into man-made systems such as concurrent programs, digital circuits and communication networks."[1] Network calculus gives a theoretical framework for analysing performance guarantees in computer networks. As traffic flows through a network it is subject to constraints imposed by the system components, for example:

These constraints can be expressed and analysed with network calculus methods. Constraint curves can be combined using convolution under min-plus algebra. Network calculus can also be used to express traffic arrival and departure functions as well as service curves.

The calculus uses "alternate algebras ... to transform complex non-linear network systems into analytically tractable linear systems."[2]

Currently, there exists two branches in network calculus: one handling deterministic bounded, and one handling stochastic bounds .[3] This article is only about deterministic network calculus.

System modelling

Modelling flow and server

In network calculus, a flow is modelled as cumulative functions A, where A(t) represents the amount of data (number of bits for example) send by the flow in the interval [0,t). Such functions are non-negative and non-decreasing. The time domain is often the set of non negative reals.

Arrival and departure curve at ingress and egress of a server.

A: \mathbb R^+ \rightarrow \mathbb R^+

\forall u,t \in \mathbb R^+: u < t \implies A(u) \leq A(t)

A server can be a link, a scheduler, a traffic shaper, or a whole network. It is simply modelled as a relation between some arrival cumulative curve A and some departure cumulative curve D. It is required that A ≥ D, to model the fact that the departure of some data can not occur before its arrival.

Modelling backlog and delay

Given some arrival and departure curve A and D, the backlog at any instant t, denoted b(A,D,t) can be defined as the difference between A and D. The delay at t, d(A,D,t) is defined as the minimal amount of time such that the departure function reached the arrival function. When considering the whole flows, the supremum of these values is used.

Horizontal and vertical deviation between arrival and departure cumulative curves

b(A,D,t) := A(t) - D(t)

d(A,D,t) := \inf\left\{ d \in \mathbb R^+ ~s.t.~ D(t+d) \geq A(t) \right\}

b(A,D) := \sup_{t \geq 0}\left\{ A(t) - D(t) \right\}

d(A,D) := \sup_{t \geq 0}\left\{ \inf\left\{ d \in \mathbb R^+ ~s.t.~ D(t+d) \geq A(t) \right\} \right\}

In general, the flows are not exactly known, and only some constraints on flows and servers are known (like the maximal number of packet sent on some period, the maximal size of packets, the minimal link bandwidth). The aim of network calculus is to compute upper bounds on delay and backlog, based on these constraints. To do so, network calculus uses the min-plus algebra.

Min-plus algebra

In filter theory and linear systems theory the convolution of two functions f and g is defined as

(f \ast g) (t) := \int_{0}^{\tau} f(\tau) \cdot g(t-\tau) d\tau

In min-plus algebra the sum is replaced by the minimum respectively infimum operator and the product is replaced by the sum. So the min-plus convolution of two functions f and g becomes

(f \otimes g) (t) := \inf_{0 \leq \tau \leq t}\left\{f(\tau) + g(t-\tau)\right\}

e.g. see the definition of service curves. Convolution and min-plus convolution share many algebraic properties. In particular both are commutative and associative.

A so-called min-plus de-convolution operation is defined as

(f \oslash g) (t) := \sup_{\tau \ge 0}\left\{f(t+\tau) - g(\tau)\right\}

e.g. as used in the definition of traffic envelopes.

The vertical and horizontal deviations can be expressed in terms of min-plus operators.

b(f,g) = (f \oslash g)(0)

d(f,g) = \inf \{w : (f \oslash g)(-w) \le 0 \}

Traffic envelopes

Cumulative curves are real behaviours, unknown at design time. What is known is some constraint. Network calculus uses the notion of traffic envelope, also known as arrival curves.

A cumulative function A is said to conform to an envelope (or arrival curve) E, iff for all t it holds that

E(t) \ge \sup_{\tau \ge 0} \{A(t+\tau) - A(\tau) \} = (A \oslash A)(t).

Two equivalent definitions can be given

\forall \tau,t \in \mathbb R^+: A(\tau+t)-A(\tau) \leq E(t)

 

 

 

 

(1)

A \leq A \otimes E

Thus, E places an upper constraint on flow A. Such function E can be seen as an envelope that specifies an upper bound on the number of bits of flow seen in any interval of length t starting at an arbitrary τ, cf. eq. (1).

Service curves

In order to provide performance guarantees to traffic flows it is necessary to specify some minimal performance of the server (depending on reservations in the network, or scheduling policy, etc.). Service curves provide a means of expressing resource availability. Several kinds of service curves exists, like weakly strict, variable capacity node, etc. See [4] [5] for an overview.

Minimal service

Let A be an arrival flow, arriving at the ingress of a server, and D be the flow departing at the egress. The system is said to provide a simple minimal service curve S to the pair (A,B), if for all t it holds that D(t) \ge (A \otimes S)(t).

Strict minimal service

Let A be an arrival flow, arriving at the ingress of a server, and D be the flow departing at the egress. A backlog period is an interval I such that, on any t ∈ I, A(t)>D(t).

The system is said to provide a strict minimal service curve S to the pair (A,B) iff, \forall s,t \in \mathbb R^+, such that s \leq t, if (s,t] is a backlog period, then D(t)-D(s) \geq S(t-s).

If a server offers a strict minimal service of curve S, it also offers a simple minimal service of curve S.

Basic results: Performance bounds and envelope propagation

From traffic envelope and service curves, some bounds on the delay and backlog, and an envelope on the departure flow can be computed.

Let A be an arrival flow, arriving at the ingress of a server, and D be the flow departing at the egress. If the flow as a traffic envelope E, and the server provides a minimal service of curve S, then the backlog and delay can be bounded:

b(A,D) \leq b(E,S)

d(A,D) \leq d(E,S)

Moreover, the departure curve has envelope E' = E \oslash S.

Moreover, these bounds are tight i.e. given some E, and S, one may build an arrival and departure such that b(A,D) = b(E,S) and v(A,D)=v(E,S).

Concatenation / PBOO

Consider a sequence of two servers, when the output of the first one is the input of the second one. This sequence can be seen as a new server, built as the concatenation of the two other ones.

Then, if the first (resp. second) server offers a simple minimal service S_1 (resp. S_2), then, the concatenation of both offers a simple minimal service S_{e2e} = S_1 \otimes S_2.

Sequence of two servers

The proof does iterative application of the definition of service curves X \ge A \otimes S_1, D \ge X \otimes S_2 and some properties of convolution, isotonicity (D \geq ( X \otimes S_2) \otimes S_1), and associativity (D \geq X \otimes (S_2 \otimes S_1)).

The interest of this result is that the end-to-end delay bound is not greater than the sum of local delays: d(E,S_2 \otimes S_1) \leq d(E,S_1) + d(E \oslash S_1, S_2).

This result is known as Pay burst only once (PBOO).

Tools

There are several tools based on network calculus.

References

  1. ↑ Le Boudec, Jean-Yves; Thiran, Patrick (2001). Goos, Gerhard; Hartmanis, Juris; van Leeuwen, Jan, eds. "Network Calculus: A Theory of Deterministic Queuing Systems for the Internet". Lecture Notes in Computer Science 2050. doi:10.1007/3-540-45318-0. ISBN 978-3-540-42184-9.
  2. ↑ Jiang, Yuming; Liu, Yong (2009). "Stochastic Network Calculus". doi:10.1007/978-1-84800-127-5. ISBN 978-1-84800-126-8.
  3. ↑ Fidler, M. (2010). "Survey of deterministic and stochastic service curve models in the network calculus". IEEE Communications Surveys & Tutorials 12: 59. doi:10.1109/SURV.2010.020110.00019.
  4. 1 2 Bouillard, Anne; Jouhet, Laurent; Thierry, Eric (2009). Service curves in Network Calculus: dos and don'ts (Technical report). INRIA. RR-7094.
  5. ↑ Bouillard, Anne; Jouhet, Laurent; Thierry, Éric. Comparison of Different Classes of Service Curves in Network Calculuswith (PDF). 10th International Workshop on Discrete Event Systems (WODES 2010). Technische Universität Berlin.
  6. ↑ Bondorf, Steffen; Schmitt, Jens B. (2014). The DiscoDNC v2 – A Comprehensive Tool for Deterministic Network Calculus (PDF). 8th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2014).
  7. ↑ Boyer, Marc; Migge, Jörn; Fumey, Marc (2011). PEGASE, A Robust and Efficient Tool for Worst Case Network Traversal Time (PDF). SAE 2011 AeroTech Congress & Exhibition.
  8. ↑ Mifdaoui, Ahlem; Ayed, H. (2010). WOPANets: A tool for WOrst case Performance Analysis of embedded Networks. 15th IEEE International Workshop on Computer Aided Modeling, Analysis and Design of Communication Links and Networks (CAMAD).
  9. ↑ Schmidt,, Mark; Veith, Sebastian; Menth, Michael; Kehrer, Stephan (2014). DelayLyzer: A Tool for Analyzing Delay Bounds in Industrial Ethernet Networks. 17th Int. GI/ITG Conf. on Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault Tolerance (MMB & DFT 2014). doi:10.1007/978-3-319-05359-2_19.

Books, Surveys, and Tutorials on Network Calculus

Related books on the max-plus algebra or on convex minimization

Deterministic network calculus

Network topologies, feed-forward networks

Measurement-based system identification

Stochastic network calculus

Wireless network calculus

This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.