Network calculus is "a set of mathematical results which give insights into man-made systems such as concurrent programs, digital circuits and communication networks." 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:
data link capacity traffic shapers (leaky buckets) congestion control background traffic 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." Currently, there exists two branches in network calculus: one handling deterministic bounded, and one handling stochastic bounds.
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) sent 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.
A : R + → R + {\displaystyle A:\mathbb {R} ^{+}\rightarrow \mathbb {R} ^{+}}
∀ u , t ∈ R + : u < t ⟹ A ( u ) ≤ A ( t ) {\displaystyle \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.
b ( A , D , t ) := A ( t ) − D ( t ) {\displaystyle b(A,D,t):=A(t)-D(t)}
d ( A , D , t ) := inf { d ∈ R + s . t . D ( t + d ) ≥ A ( t ) } {\displaystyle d(A,D,t):=\inf \left\{d\in \mathbb {R} ^{+}~s.t.~D(t+d)\geq A(t)\right\}}
b ( A , D ) := sup t ≥ 0 { A ( t ) − D ( t ) } {\displaystyle b(A,D):=\sup _{t\geq 0}\left\{A(t)-D(t)\right\}}
d ( A , D ) := sup t ≥ 0 { inf { d ∈ R + s . t . D ( t + d ) ≥ A ( t ) } } {\displaystyle 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 Semiring Network calculus makes an intensive use on the min-plus semiring (sometimes called min-plus algebra). In filter theory and linear systems theory the convolution of two functions f {\displaystyle f} and g {\displaystyle g} is defined as
( f ∗ g ) ( t ) := ∫ 0 t f ( τ ) ⋅ g ( t − τ ) d τ {\displaystyle (f\ast g)(t):=\int _{0}^{t}f(\tau )\cdot g(t-\tau )d\tau }
… excerpt ends here. Continue reading the full article.
