Hoop Conjecture

2014-01-20T20:29:18Z

128.101.152.70:

'''Network calculus''' is "a set of mathematical results which give insights into man-made systems such as [[concurrent program]]s, [[digital circuit]]s and [[communication network]]s."<ref name="leboudec">{{cite doi|10.1007/3-540-45318-0}}</ref> Network calculus gives a theoretical framework for analysing performance guarantees in [[computer network]]s. As traffic flows through a network it is subject to [[Constraint (mathematics)|constraints]] imposed by the system components, for example:
* [[data link|link]] capacity
* traffic shapers ([[leaky bucket]]s)
* [[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."<ref>{{cite doi|10.1007/978-1-84800-127-5}}</ref>

==Min-plus algebra==
In filter theory respectively linear systems theory the [[convolution]] of two functions <math>f</math> and <math>g</math> is defined as

<math>
(f \ast g) (t) := \sum_{\tau} f(\tau) \cdot g(t-\tau).
</math>

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 <math>f</math> and <math>g</math> becomes

<math>
(f \otimes g) (t) := \inf_{0 \leq \tau \leq t}\left\{f(\tau) + g(t-\tau)\right\}
</math>

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

<math>
(f \oslash g) (t) := \sup_{\tau \ge 0}\left\{f(t+\tau) - g(\tau)\right\}
</math>

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

==Traffic envelopes==
Traffic flows in networks are described as cumulative functions. For example, <math>A(t)</math>
is the number of bits in the interval <math>[0,t)</math>. <math>A(t)</math> is said to conform to an envelope arrival curve <math>E(t)</math>, if for all <math>t</math> it holds that

<math>
E(t) \ge \sup_{\tau \ge 0} \{A(t+\tau) - A(\tau) \} = (A \oslash A)(t).
</math>

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

<math>
A(t) \le \inf_{0 \leq \tau \leq t} \{ A(\tau) + E(t-\tau) \} = (A \otimes E)(t).
</math>

==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 <math>A(t)</math> be a flow arriving at the ingress of a system, e.g. a link, a scheduler, a traffic shaper, or a whole network, and <math>D(t)</math> be the flow departing at the egress. The system is said to provide a service curve <math>S(t)</math>, if for all <math>t</math> it holds that

<math>
D(t) \ge \inf_{0 \le \tau \le t} \{A(\tau) + S(t-\tau) \} = (A \otimes S)(t).
</math>

==Concatenation==
Consider two systems with service curve <math>S_1(t)</math> and <math>S_2(t)</math> in series. Let <math>A(t)</math> be the arrival function at system 1 and <math>D(t)</math> the departure function of system 2. By iterative application of the definition of service curves we have

<math>D(t) \geq ((A \otimes S_1) \otimes S_2)(t)</math>.

By associativity of the min-plus convolution it follows that

<math>D(t) \geq (A \otimes (S_1 \otimes S_2))(t)</math>

i.e. the tandem of systems <math>S_1(t)</math> and <math>S_2(t)</math> is equivalent to a single, lumped system <math>S_{e2e}(t)</math> where

<math>S_{e2e}(t) = (S_1 \otimes S_2)(t)</math>.

==Performance bounds==
The virtual backlog is defined as the vertical deviation of <math>A(t)</math> and <math>D(t)</math>

<math>
B(t) = A(t) - D(t), \forall t \ge 0.
</math>

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

<math>
B_{\max} \le \sup_{\tau \ge 0} \{E(\tau) - S(\tau) \} = (E \oslash S)(0).
</math>

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

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

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

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

==References==

{{Reflist}}

Books that cover Network Calculus
* C.-S. Chang: ''Performance Guarantees in Communications Networks'', Springer, 2000.
* J.-Y. Le Boudec and P. Thiran: ''[http://ica1www.epfl.ch/PS_files/NetCal.htm 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: {{doi-inline|10.1109/18.61109|A Calculus for Network Delay. Part I: Network Elements in Isolation}} and {{doi-inline|10.1109/18.61110|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

[[Category:Network performance]]
[[Category:Computer network analysis]]

formulasearchengine - User contributions [en]

Hoop Conjecture