×

Large-scale behaviour of packet-switched networks: theoretical analysis framework. (English) Zbl 1145.68336

Summary: We present a possible way to study large-size packet-switched networks capable of accounting for interactions between adjacent queues. The interaction between queues arises, because of the influence of the routing protocol on each switching decision, and the stochastic nature of packet lengths and inter-arrival times.Both the methodology and the analysis tools are adaptations of methods of statistical mechanics. The justification for their use lies in recent experimental evidence indicating that aggregate, core-network IP traffic, exhibits quasi-Markovian properties when the network is heavily loaded.In this paper, we present a general methodology and introduce approximations that greatly simplify the analysis. These approximations, are owing to the quasi-Markovian nature of the traffic and the large size of the network.

MSC:

68M10 Network design and communication in computer systems
68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
82B99 Equilibrium statistical mechanics
90B10 Deterministic network models in operations research
90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cao, J., Cleveland, W.S., Lin, D. & Sun, D.X. 2002 Internet traffic tends to poisson and independent as the load increases. <i>Nonlinear estimation and classification</i> (eds. Holmes, C. Denison, D. Hansen, M. Yu, B. & Mallick, B.), New York: Springer-Verlag
[2] Carmichael, H.J. 1999 Statistical methods in quantum optics I: master equations and Fokker–Planck equations. New York: Springer-Verlag. · Zbl 0918.60095
[3] Delcoigne, F. & Fayolle, G. 1999 Thermodynamical limit and propagation of chaos in polling systems. <i>Markov Process. Relat. Fields</i> <b>5</b>, 89–124. · Zbl 0920.60072
[4] Fayolle, G., Fortelle, A., Lasgouttes, J., Massoulie, L. & Roberts, J. 2001 Best-effort networks: modeling and performance analysis via large networks asymptotics. <i>Proc. IEEE INFOCOM</i>, 2001.
[5] Gardiner, C.W. 1994 Handbook of stochastic methods. Berlin: Springer-Verlag.
[6] Gnedenko, B.V. 1963 The theory of probability. 2nd edn. New York: Chelsea. · Zbl 0121.25101
[7] Graham, C. & Méléard, S. 1994 Chaos hypothesis for a system interacting through shared resources. <i>Probab. Theor. Relat. Fields</i> <b>100</b>, 157–173.
[8] Kelly, F. 1991 Loss networks. <i>Ann. Appl. Probab.</i> <b>1</b>, 319–378.
[9] Kramers, H.A. 1940 <i>Physica</i> <b>7</b>, 284.
[10] McQuillan, J.M., Richer, I. & Rosen, E.C. 1980 The new routing algorithm for the ARPANET. <i>IEEE Trans. Commun.</i> <b>28</b>, 5.
[11] Moyal, J.E. 1949 <i>J. R. Stat. Soc.</i> <b>11</b>, 151–210.
[12] Risken, H. 1989 The Fokker–Planck equation: methods of solution and applications. 2nd edn. Berlin: Springer-Verlag. · Zbl 0665.60084
[13] Schwartz, M. 1987 Telecommunication networks, protocols, modeling and analysis. Reading: Addison-Wesley.
[14] Stepanenko, A.S., Constantinou, C.C., Arvanitis, T.N. & Baughan, K. 2001 Statistical properties of core network internet traffic. <i>Electron. Lett.</i> <b>38</b>, 350–351.
[15] Stepanenko, A. S. Constantinou, C. C. Arvanitis, T. N. & Baughan, K. 2002 On a theory of interacting queues. In <i>Lecture notes in Computer Science (LNCS2345)</i>, pp. 769–777. Berlin: Springer-Verlag. · Zbl 1046.68914
[16] Stratonovich, R.L. 1989 Noise in nonlinear dynamical systems. <i>Theory of continuous Fokker–Planck systems</i> (eds. Moss, F. & McCli, P.V.E.), vol. 1. Cambridge: Cambridge University Press
[17] Vvedenskaya, N.D., Dobrushin, R.L. & Karpelevich, F.I. 1996 A queueing system with a choice of the shorter of two queues–an asymptotic approach. <i>Problems Inform. Transmission</i> <b>32</b>, 15–27. · Zbl 0898.60095
[18] Zinn-Justin, J. 1993 Quantum field theory and critical phenomena. 2nd edn. Oxford: Clarendon Press. · Zbl 0865.00014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.