Network calculus

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

• 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.

Traffic envelopes

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 conform to an envelope respectively arrival curve E(t) if for all t it holds that

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

Thus, E(t) places an upper constraint on flow A(t), i.e. an envelope E(t) specifies an upper bound on the number of bits of flow A(t) seen in any interval of length t starting at an arbitrary τ. The above equation can be rephrased for all t as

$A(t) \le \inf_{0 \leq \tau \leq t} \{ A(\tau) + E(t-\tau) \} = (A \otimes E)(t).$

Service curves

In order to provide performance guarantees to traffic flows it may be necessary to implement reservations in the network. Service curves provide a means of expressing resource allocations.

Let A(t) be a flow arriving at the ingress of a system, e.g. a link, a scheduler, a traffic shaper, or a whole network, and D(t) be the flow departing at the egress. The system is said to provide a service curve S(t), if for all t it holds that

$D(t) \ge \inf_{0 \le \tau \le t} \{A(\tau) + S(t-\tau) \} = (A \otimes S)(t).$

Min-plus algebra

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

$(f \ast g) (t) := \sum_{\tau} f(\tau) \cdot g(t-\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.

Concatenation

Consider two systems with service curve S₁(t) and S₂(t) in series. Let A(t) be the arrival function at system 1 and D(t) the departure function of system 2. By iterative application of the definition of service curves we have

$D(t) \geq ((A \otimes S_1) \otimes S_2)(t)$.

By associativity of the min-plus convolution it follows that

$D(t) \geq (A \otimes (S_1 \otimes S_2))(t)$

i.e. the tandem of systems S₁(t) and S₂(t) is equivalent to a single, lumped system S_e2e(t) where

$S_{e2e}(t) = (S_1 \otimes S_2)(t)$.

Performance bounds

The virtual backlog is defined as the vertical deviation of A(t) and D(t)

$B(t) = A(t) - D(t), \forall t \ge 0.$

Using the concepts of traffic envelopes and service curves the maximum backlog is bounded by

$B_{\max} \le \sup_{\tau \ge 0} \{E(\tau) - S(\tau) \} = (E \oslash S)(0).$

The delay W(t) is defined as the horizontal deviation of A(t) and D(t)

$W(t) = \inf \{w : A(t) - D(t+w) \le 0\} , \forall t \ge 0.$

Using the concepts of traffic envelopes and service curves the maximum delay is bounded by

$W_{\max} \le \inf \{w : \sup_{\tau \ge w} \{ E(\tau-w) - S(\tau) \} \le 0 \} = \inf \{w : (E \oslash S)(-w) \le 0 \}.$

References

Books that cover Network Calculus

• C.-S. Chang: Performance Guarantees in Communications Networks, Springer, 2000.
• J.-Y. Le Boudec and P. Thiran: Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, Springer, LNCS, 2001.
• A. Kumar, D. Manjunath, and J. Kuri: Communication Networking: An Analytical Approach, Elsevier, 2004.
• Y. Jiang and Y. Liu: Stochastic Network Calculus, Springer, 2008.

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

• R. T. Rockafellar: Convex analysis, Princeton University Press, 1972.
• F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley, 1992.

Some related research papers

• R. L. Cruz: A Calculus for Network Delay. Part I: Network Elements in Isolation and Part II: Network Analysis, IEEE Transactions on Information Theory, 37(1):114-141, Jan. 1991.
• O. Yaron and M. Sidi: Performance and Stability of Communication Networks via Robust Exponential Bounds, IEEE/ACM Transactions on Networking, 1(3):372-385, Jun. 1993.
• C.-S. Chang: Stability, Queue Length and Delay of Deterministic and Stochastic Queueing Networks, IEEE Transactions on Automatic Control, 39(5):913-931, May 1994.
• D. E. Wrege, E. W. Knightly, H. Zhang, and J. Liebeherr: Deterministic delay bounds for VBR video in packet-switching networks: Fundamental limits and practical tradeoffs, IEEE/ACM Transactions on Networking, 4(3):352-362, Jun. 1996.
• R. L. Cruz: SCED+: Efficient Management of Quality of Service Guarantees, IEEE INFOCOM, pp. 625-634, Mar. 1998.
• J.-Y. Le Boudec: Application of Network Calculus to Guaranteed Service Networks, IEEE Transactions on Information Theory, 44(3):1087-1096, May 1998.
• C.-S. Chang: On Deterministic Traffic Regulation and Service Guarantees: A Systematic Approach by Filtering, IEEE Transactions on Information Theory, 44(3):1097-1110, May 1998.
• R. Agrawal, R. L. Cruz, C. Okino, and R. Rajan: Performance Bounds for Flow Control Protocols, IEEE/ACM Transactions on Networking, 7(3):310-323, Jun. 1999.
• D. Starobinski and M. Sidi: Stochastically Bounded Burstiness for Communication Networks, IEEE Transactions on Information Theory, 46(1):206-212, Jan. 2000.
• A. Charny and J.-Y. Le Boudec: Delay Bounds in a Network with Aggregate Scheduling, QoFIS, pp. 1-13, Sep. 2000.
• R.-R. Boorstyn, A. Burchard, J. Liebeherr, and C. Oottamakorn: Statistical Service Assurances for Traffic Scheduling Algorithms, IEEE Journal on Selected Areas in Communications, 18(12):2651-2664, Dec. 2000.
• J.-Y. Le Boudec: Some properties of variable length packet shapers, IEEE/ACM Transactions on Networking, 10(3):329-337, Jun. 2002.
• Q. Yin, Y. Jiang, S. Jiang, and P. Y. Kong: Analysis of Generalized Stochastically Bounded Bursty Traffic for Communication Networks, IEEE LCN, pp. 141-149, Nov. 2002.
• C.-S. Chang, R. L. Cruz, J.-Y. Le Boudec, and P. Thiran: A Min, + System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees, IEEE/ACM Transactions on Networking, 10(6):805-817, Dec. 2002.
• D. Starobinski, M. Karpovsky, and L. Zakrevski: Application of Network Calculus to General Topologies using Turn-Prohibition, IEEE/ACM Transactions on Networking, 11(3):411-421, Jun. 2003.
• C. Li, A. Burchard, and J. Liebeherr: A Network Calculus with Effective Bandwidth, University of Virginia, Technical Report CS-2003-20, Nov. 2003.
• F. Ciucu, A. Burchard, and J. Liebeherr: A Network Service Curve Approach for the Stochastic Analysis of Networks, IEEE/ACM Transactions on Networking, 52(6):2300–2312, Jun. 2006.
• M. Fidler and S. Recker: Conjugate network calculus: A dual approach applying the Legendre transform, Computer Networks, 50(8):1026-1039, Jun. 2006.
• M. Fidler: An End-to-End Probabilistic Network Calculus with Moment Generating Functions, IEEE IWQoS, Jun. 2006.
• A. Burchard, J. Liebeherr, and S. D. Patek: A Min-Plus Calculus for End-to-end Statistical Service Guarantees, IEEE Transactions on Information Theory, 52(9):4105–4114, Sep. 2006.
• Eitan Altman, Kostya Avrachenkov, and Chadi Barakat: TCP network calculus: The case of large bandwidth-delay product, In proceedings of IEEE INFOCOM, NY, June 2002.
• Kym Watson, Juergen Jasperneite: Determining End-to-End Delays using Network Calculus, in 5th IFAC International Conference on Fieldbus Systems and their Applications (FeT´2003) S.: 255-260, Aveiro, Portugal, Jul 2003