Hoop Conjecture

Network calculus is "a set of mathematical results which give insights into man-made systems such as concurrent programs, digital circuits and communication networks." Network calculus gives 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.

The calculus uses "alternate algebras ... to transform complex non-linear network systems into analytically tractable linear systems."

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 \geq 0}\left\{f(t+\tau )-g(\tau )\right\}$

e.g. as used in the definition of traffic envelopes.

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 arrival curve $E(t)$, if for all $t$ it holds that

$E(t)\geq \sup _{\tau \geq 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 $\tau$. The above equation can be rephrased for all $t$ as

$A(t)\leq \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)\geq \inf _{0\leq \tau \leq t}\{A(\tau )+S(t-\tau )\}=(A\otimes S)(t).$

Concatenation

Consider two systems with service curve $S_{1}(t)$ and $S_{2}(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_{1}(t)$ and $S_{2}(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\geq 0.$

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

$B_{\max }\leq \sup _{\tau \geq 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)\leq 0\},\forall t\geq 0.$

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

$W_{\max }\leq \inf\{w:\sup _{\tau \geq w}\{E(\tau -w)-S(\tau )\}\leq 0\}=\inf\{w:(E\oslash S)(-w)\leq 0\}.$

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

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.
• V. N. Kolokol'tsov, Victor P. Maslov: Idempotent Analysis and Its Applications, Springer, 1997. ISBN 0792345096.

Some related research papers

• R. L. Cruz: Template:Doi-inline and Template:Doi-inline, 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