Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-15T06:12:17.142Z Has data issue: false hasContentIssue false
  • English
  • Français

Analysis of a phase transition phenomenon in packet networks

Part of:Operations research and management scienceSpecial processesLimit theorems

Published online by Cambridge University Press:  01 July 2016

Michel Mandjes and
Jeong-Han Kim
Michel Mandjes*
Affiliation:
Bell Laboratories, Lucent Technologies
Jeong-Han Kim*
Affiliation:
Microsoft Research
*
∗ Current address: CWI, PO Box 94079, 1090 GB Amsterdam, The Netherlands. Email address: michel@cwi.nl
∗∗ Postal address: 1 Microsoft Way, Redmond, WA 98052, USA.
Get accessRights & Permissions [Opens in a new window]

Abstract

The multiplexing of variable bit rate traffic streams in a packet network gives rise to two types of queueing. On a small time-scale, the rates at which the sources send is more or less constant, but there is queueing due to simultaneous packet arrivals (packet-level effect). On a somewhat larger time-scale, queueing is the result of a relatively high number of sources sending at a rate that is higher than their average rate (burst-level effect). This paper explores these effects. In particular, we give asymptotics of the overflow probability in the combined packet/burst scale model. It is shown that there is a specific size of the buffer (i.e. the ‘critical buffer size’) below which packet-scale effects are dominant, and above which burst-scale effects essentially determine the performance—strikingly, there is a sharp demarcation: theso-called ‘phase transition’. The results are asymptotic in the number of sources n. We scale buffer space B and link rate C by n, to nb and nc, respectively; then we let n grow large. Applying large deviations theory we show that in this regime the overflow probability decays exponentially in the number of sources n. For small buffers the corresponding decay rate can be calculated explicitly, for large buffers we derive an asymptote (linear in b). The results for small and large buffers give rise to an approximation for the decay rate (with general b), as well as for the critical buffer size. A numerical example (multiplexing of voice streams) confirms the accuracy of these approximations.

Keywords

queueing theorylarge deviations asymptoticsbuffer overflowpacket and burst scalephase transitionATM multiplexersIP routers

MSC classification

Primary:60K25: Queueing theory
Secondary:60F10: Large deviations90B18: Communication networks

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 33 , Issue 1 , March 2001, pp. 260 - 280
Copyright
Copyright © Applied Probability Trust 2001 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

[1] Anick, D., Mitra, D. and Sondhi, M. (1982). Stochastic theory of a data-handling system with multiple sources. Bell Syst. Tech. J. 61, 1871–1894.CrossRefGoogle Scholar
[2] Botvich, D. and Duffield, N. (1995). Large deviations, the shape of the loss curve, and economies of scale in large multiplexers. Queueing Systems 20, 293–320.Google Scholar
[3] Courcoubetis, C., Siris, V. and Weber, R. (1997). Investigation of cell scale and burst scale effects on the cell loss probability using large deviations. In Proc. 13th UK Workshop Perf. Eng. of Comput. and Telecommunication Systems, Ilkley, UK.Google Scholar
[4] Courcoubetis, C. and Weber, R. (1996). Buffer overflow asymptotics for a buffer handling many traffic sources. J. Appl. Prob. 33, 886–903.CrossRefGoogle Scholar
[5] Dembo, A. and Zeitouni, O. (1993). Large Deviations Techniques and Applications. Jones and Bartlett, Boston.Google Scholar
[6] Dron, L., Ramamurthy, G. and Sengupta, B. (1991). Delay analysis of continuous bit rate traffic over an ATM network. IEEE J. Sel. Areas Commun. 9, 402–407.Google Scholar
[7] Duffield, N. (1998). Conditioned asymptotics for tail probabilities in large multiplexers. Performance Evaluation 31, 281–300.CrossRefGoogle Scholar
[8] Eckberg, A. (1979). The single-server queue with periodic arrival process and deterministic service time. IEEE Trans. Commun. 27, 556–562.Google Scholar
[9] Gibbens, R. and Kelly, F. (1999). Distributed connection acceptance control for a connectionless network. In Proceedings ITC 16: Teletraffic Engineering in a Competitive World, eds Key, P. and Smith, D.. Elsevier, Amsterdam, pp. 941–952.Google Scholar
[10] Heffes, H. and Lucantoni, D. (1986). A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE J. Sel. Areas Commun. 4, 856–868.CrossRefGoogle Scholar
[11] Hui, J. (1988). Resource allocation for broadband networks. IEEE J. Sel. Areas Commun. 6, 1598–1608.Google Scholar
[12] Kelly, F. (1996). Notes on effective bandwidths. In Stochastic Networks: Theory and Applications, eds Kelly, F., Zachary, S., and I. Ziedins. Oxford University Press, pp. 141–168.CrossRefGoogle Scholar
[13] Kelly, F. (2000). Models for a self-managed Internet. Phil. Trans. R. Soc. A 358, 2335–2348.Google Scholar
[14] Likhanov, N. and Mazumdar, R. (1999). Cell loss asymptotics in buffers fed with a large number of independent stationary sources. J. Appl. Prob. 36, 86–96.Google Scholar
[15] Mandjes, M. and Boots, N.-K. (2000). The shape of the loss curve, and the impact of long-range dependence on network performance. Submitted.Google Scholar
[16] Mandjes, M. and Borst, S. (2000). Overflow behavior in queues with many long-tailed inputs. Adv. Appl. Prob. 32, 1150–1167.Google Scholar
[17] Mandjes, M. and Kim, J.-H. (1999). Large deviations for small buffers: an insensitivity result. To appear in Queueing Systems.Google Scholar
[18] Mandjes, M. and Ridder, A. (1999). Optimal trajectory to overflow in a queue fed by a large number of sources. Queueing Systems 31, 137–170.Google Scholar
[19] Norros, I., Roberts, J., Simonian, A. and Virtamo, J. (1991). The superposition of variable bit rate sources in an ATM multiplexer. IEEE J. Sel. Areas Commun. 9, 378–387.Google Scholar
[20] Roberts, J. (ed.) (1992). Performance Evaluation and Design of Multiservice Networks: Final Report (Euraton Publications EUR 14152). Commission of the European Communities, Luxembourg.Google Scholar
[21] Schoute, F. (1988). Simple decision rules for acceptance of mixed traffic streams. In Teletraffic Science for New Cost-Effective Systems, Networks and Services (Proc. 12th Int. Teletraffic Congress, Turin), ed. Bonatti, M.. North-Holland, Amsterdam, pp. 1–7.Google Scholar
[22] Schwartz, M. (1996). Broadband Integrated Networks. Prentice Hall, Upper Saddle River, NJ.Google Scholar
[23] Shwartz, A. and Weiss, A. (1995). Large deviations for performance analysis, queues, communication, and computing. Chapman and Hall, New York.Google Scholar
[24] Simonian, A. and Guibert, J. (1995). Large deviations approximation for fluid queues fed by a large number of on/off sources. IEEE J. Sel. Areas Commun. 13, 1017–1027.Google Scholar
[25] Sriram, K. and Whitt, W. (1986). Characterizing superposition arrival processes in packet multiplexers for voice and data. IEEE J. Sel. Areas Commun. 4, 833–846.CrossRefGoogle Scholar
[26] Weiss, A. (1986). A new technique of analyzing large traffic systems. Adv. Appl. Prob. 18, 506–532.CrossRefGoogle Scholar
[27] Wischik, D. (1999). Sample path large deviations for queues with many inputs. To appear in Ann. Appl. Prob. Google Scholar