Network Calculus

---

Network Calculus can be viewd as the system theory that applies to communication systems. The main difference with traditional system theory is that here we consider another algebra, where the operators are changed as follows: addition becomes computation of the minimum, multiplication becomes addition - minn-plus algebra. This approach is based on the fundamental work of Cruz and research of Le Boudec and Thiran.
Assume we have a network node with input flow x(t) and output flow y(t) and serve this flow according to some envelope. The functions of the input and output flow are cumulative and wide-sense increasing. These parameters are connected by the equation: Main terms in network calculus are: backlog, virtual delay, arrival curve, service curve.

Definitions:

• backlog - this is the amount of bits in the system including the served ones. If teh system is single buffer this is equal to buffer size

• virtual delay - this is the delay of a given bit if all bits arrived before it are served before it.

• arrival curve - let us have a wide-sense increasing function alpha, that is defined for all t. We say that x(t) if bounded by alpha if for all s <= t:

• service curve - let us have a system with x - input flow and y - output flow. We say that the system offers service curve beta to the flow if and only if, for all t there is t0 that 0<= t0 <=t and:

The simplest form of the arrival curve is alpha=R.t. The most popular arrival curve is TSPEC (e.g. traffic specification). It is defined with the quadruple {M, p, b, r}, with M - maximum frame size, p - peak rate, b - burstiness, r - long term average rate. This is a combination of two leaky buckets - alpha = min( p.t+M; r.t+b ). Another interesting arrival curve is that of periodic flow with contsant size packets. Its arrival cuvre is: , which can be modified to: .
The simplest service cuvre is specified by GPS (generalized processor sharing) and is beta = R.t. Another interesting service curve is the guaranteed delay - it is represented with the impulse delta function. The most interesting service curve is the RSPEC, defined by the equation:

Some Theorems

Concatenation of nodes

Assume a flow traverses two systems in sequence. Assume that system 1 offers beta1 and system 2 - beta2 service curves to thw flow. Then the concatenation of the two systems offers a service curve of to the flow.

Backlog Bound

Assume a flow, constrained by arrival curve alpha, traverses a system that offers a service curve beta. The backlog x(t) - y(t) for all t satisfies:

Delay Bound

Assume a flow traverses two systems in sequence. Assume that system 1 offers beta1 and system 2 - beta2 service curves to thw flow. The virtual delay d(t) for all t satisfies:

Output Flow

Assume a flow traverses two systems in sequence. Assume that system 1 offers beta1 and system 2 - beta2 service curves to thw flow. The output flow is constraned by the curve taht satisfies the following:

FIFO Split

Consider a service node serving two packet flows in FIFO order. Assume that the node offers to the aggregate flow a service curve beta and suppose that the second flow is constrained by an arrival curve alpha2. Lets define the family of functions: The most often chosen function from this family is when

Non preemptive priority node

Consider a service node serving two packet flows in non preemptive priority mode - F1(low priority) and F2 (high priority). ssume that the node offers to the aggregate flow a service curve beta and suppose that the second flow is constrained by an arrival curve alpha2. Let Lmax is the maximum sized frame in F2. Then the node offers to the high priority flow a service curve: and to the low priority:

• for GPS and PGPS refer to the work of Parekh and Galahar, and for WFQ and WRR to the work of Georges, Divoux and Rondeau

Example

Calculations of the delay and backlog bounds for 4 flows (one periodic and 3 – TSPEC) traversing through FIFO or Strict Priority multiplexer.

The first flow is periodic and is constrained by the arrival curve : The other three flows are TSPEC and are constrained by the arrival curves :
The service curves offered to each flow by the FIFO multiplexer are calculated by the equations: And for the Strict priority the calculations are: The results for Strict priority depends on the priority of the flows. It is assumed that the flow with lower id has higher priority. The bounds for the virtual delay and for the backlog are calculated with the equations: This equations are not general and are adjusted knowing the form of the curves - figure bellow:

Results

We choose the following parameters for the switch and four flows: Using the above pesumptions, parameters and calculation we obtain the following results:
There are some tools that help making the calculations, using Java - DISCO or MatLab - CyNC

• CopyLeft: DSNET V-Lab