Network calculus

From Wikipedia, the free encyclopedia

Network calculus is 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:

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 curves as well as service curves.

1 Arrival and departure curves
2 Service curves
3 Min-plus algebra
4 References

[edit] Arrival and departure curves

Traffic flows in networks are described as cumulative functions. For example, $A (t)$ is the number of bits in the interval $[0, t)$ . $A (t)$ is said to be f-upper constrained if, for all $s < t$ :

$A(t) \le A(s) + f(t-s)$

Thus $f$ places some constraint on flow $A$ .

[edit] Service curves

In order to provide performance guarantees to traffic flows is it necessary to implement reservations in the network.

Service curves provide a means of expressing resource reservations. Is $A (t)$ is a flow arriving at the ingress of the network and $B (t)$ is flow departing at the egress, the maximum delay is bounded by $T$ , if the following inequality is met:

$B(t) \ge A(s-T)$

[edit] Min-plus algebra

In filter theory the convolution of two signals $h$ and $x$ is given by;

$(h \otimes x) (t) = \int_{-\infty}^{\infty} h(s) x(t-s) ds$

In min-plus algebra the sum is replaced by the minimum operator and the product is replaced by the sum. So the convolution of two wide-sense increasing functions $f$ and $g$ is:

$(f \otimes g) (t) = \textrm{min}(f(s) + g(t-s))$