- 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.
Contents
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
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
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
Min-plus algebra
In filter theory respectively linear systems theory the convolution of two functions f and g is defined as
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
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
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
.
By associativity of the min-plus convolution it follows that
i.e. the tandem of systems S1(t) and S2(t) is equivalent to a single, lumped system Se2e(t) where
.
Performance bounds
The virtual backlog is defined as the vertical deviation of A(t) and D(t)
Using the concepts of traffic envelopes and service curves the maximum backlog is bounded by
The delay W(t) is defined as the horizontal deviation of A(t) and D(t)
Using the concepts of traffic envelopes and service curves the maximum delay is bounded by
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
Categories:- Network performance
- Computer network analysis
Wikimedia Foundation. 2010.