Network calculus

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:

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 S1(t) and S2(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 S1(t) and S2(t) is equivalent to a single, lumped system Se2e(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

Wikimedia Foundation. 2010.

Look at other dictionaries:

• π-calculus — In theoretical computer science, the π calculus (or pi calculus) is a process calculus originally developed by Robin Milner, Joachim Parrow and David Walker as a continuation of work on the process calculus CCS (Calculus of Communicating Systems) …   Wikipedia

• Pi-calculus — In theoretical computer science, the pi calculus is a process calculus originally developed by Robin Milner, Joachim Parrow and David Walker as a continuation of work on the process calculus CCS (Calculus of Communicating Systems). The aim of the …   Wikipedia

• Neural network — For other uses, see Neural network (disambiguation). Simplified view of a feedforward artificial neural network The term neural network was traditionally used to refer to a network or circuit of biological neurons.[1] The modern usage of the term …   Wikipedia

• Region Connection Calculus — The region connection calculus (RCC) serves for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidian space, or in a topological space) by their possible relations to each other. RCC8 consists of 8 basic …   Wikipedia

• Ambient calculus — In computer science, the ambient calculus is a process calculus devised by Luca Cardelli and Andrew D. Gordon in 1998, and used to describe and theorise about concurrent systems that include mobility. Here mobility means both computation carried… …   Wikipedia

• Frege's propositional calculus — In mathematical logic Frege s propositional calculus was the first axiomatization of propositional calculus. It was invented by Gottlob Frege, who also invented predicate calculus, in 1879 as part of his second order predicate calculus (although… …   Wikipedia

• Artificial Neural Network — Réseau de neurones Pour les articles homonymes, voir Réseau. Vue simplifiée d un réseau artificiel de neurones Un réseau de neurones artificiel est un modèle de c …   Wikipédia en Français

• Neuronal network — Réseau de neurones Pour les articles homonymes, voir Réseau. Neurosciences …   Wikipédia en Français

• List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

• Artificial intelligence — AI redirects here. For other uses, see Ai. For other uses, see Artificial intelligence (disambiguation). TOPIO, a humanoid robot, played table tennis at Tokyo International Robot Exhibition (IREX) 2009.[1] Artificial intelligence ( …   Wikipedia