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.
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.
[3] 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).
The time domain is often the set of non negative reals.
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.
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.
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.
A so-called min-plus de-convolution operation is defined as
The vertical and horizontal deviations can be expressed in terms of min-plus operators.
Cumulative curves are real behaviours, unknown at design time.
Network calculus uses the notion of traffic envelope, also known as arrival curves.
A cumulative function A is said to conform to an envelope E (also called arrival curve and denoted α) , if for all t it holds that
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 d starting at an arbitrary t, cf.
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.
The system is said to provide a simple minimal service curve S to the pair (A,B), if for all t it holds that
The system is said to provide a strict minimal service curve S to the pair (A,B) iff,
If a server offers a strict minimal service of curve S, it also offers a simple minimal service of curve S. Depending on the authors, on the purpose of the paper, different notations or even names are used for the same notion.
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:
The proof does iterative application of the definition of service curves
[6] There exist several tools and library devoted to the min-plus algebra.
All these tools and library are based on the algorithms presented in.
It is organized every two years to bring together researchers with an interest in the theory of network calculus as well as those who want to apply existing results to new applications.
The workshop also serves to promote the network calculus theory to researchers with an interest in applied queueing models.
In 2018, International Workshop on Network Calculus and Applications (NetCal 2018) was held in Vienna, Austria as a part of the 30th International Teletraffic Congress (ITC 30).
