Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-05T22:43:38.319Z Has data issue: false hasContentIssue false
  • English
  • Français

Network decomposition in the many-sources regime

Part of: Special processes Operations research and management science Computer system organization Limit theorems

Published online by Cambridge University Press:  01 July 2016

Do Young Eun  and
Ness B. Shroff
Do Young Eun*
Affiliation:
Purdue University
Ness B. Shroff*
Affiliation:
Purdue University
*
∗ Current address: Department of Electrical and Computer Engineering, Box 7911, North Carolina State University, Raleigh, NC 27695-7911, USA. Email address: [email protected]
∗∗ Postal address: School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907-1285, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We derive results that show the impact of aggregation in a queueing network. Our model consists of a two-stage queueing system where the first (upstream) queue serves many flows, of which a certain subset arrive at the second (downstream) queue. The downstream queue experiences arbitrary interfering traffic. In this setup, we prove that, as the number of flows being aggregated in the upstream queue increases, the overflow probability of the downstream queue converges uniformly in the buffer level to the overflow probability of a single queueing system obtained by simply removing the upstream queue in the original two-stage queueing system. We also provide the speed of convergence and show that it is at least exponentially fast. We then extend our results to non-i.i.d. traffic arrivals.

Keywords

Aggregationqueueing networkmany-sources asymptoticspeed of convergence

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B18: Communication networks 60F10: Large deviations 68M20: Performance evaluation; queueing; scheduling
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 36 , Issue 3 , September 2004 , pp. 893 - 918
Copyright
Copyright © Applied Probability Trust 2004 

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.)

Footnotes

This work has been partly supported by NSF grant number ANI-0099137.

References

[1] Beran, J., Sherman, R., Taqqu, M. S. and Willinger, W. (1995). Long-range dependence in variable-bit-rate video traffic. IEEE Trans. Commun. 43, 1566–1579.CrossRefGoogle Scholar
[2] Botvich, D. 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.CrossRefGoogle Scholar
[3] Choe, J. and Shroff, N. B. (2000). Use of supremum distribution of Gaussian processes in queueing analysis with long-range dependence and self-similarity. Stoch. Models 16, 209–231.CrossRefGoogle 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. (1998). Large Deviations Techniques and Applications (Appl. Math. 38), 2nd edn. Springer, New York.Google Scholar
[6] Duffield, N. G. (1996). Economies of scale in queues with sources having power-law large deviation scaling. J. Appl. Prob. 33, 840–857.CrossRefGoogle Scholar
[7] Eun, D. Y. and Shroff, N. B. (2003). Simplification of network analysis in large-bandwidth systems. In Proc. IEEE INFOCOM 2003 (San Francisco, CA, April 2003), pp. 597–607.CrossRefGoogle Scholar
[8] Jackson, J. R. (1957). Networks of waiting lines. Operat. Res. 5, 518–521.CrossRefGoogle Scholar
[9] Kingman, J. F. C. (1969). Markov population processes. J. Appl. Prob. 6, 1–18.CrossRefGoogle Scholar
[10] Leland, W. E., Taqqu, M., Willinger, W. and Wilson, D. V. (1994). On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Trans. Networking 2, 1–15.CrossRefGoogle Scholar
[11] Likhanov, N. and Mazumdar, R. (1999). Cell loss asymptotics for buffers fed with a large number of independent stationary sources. J. Appl. Prob. 36, 86–96.CrossRefGoogle Scholar
[12] Mandjes, M. and Borst, S. (2000). Overflow behavior in queues with many long-tailed inputs. Adv. Appl. Prob. 32, 1150–1167.CrossRefGoogle Scholar
[13] Mandjes, M. and Kim, J. H. (2001). Large deviations for small buffers: an insensitivity result. Queueing Systems 37, 349–362.CrossRefGoogle Scholar
[14] Veciana, G. de, Courcoubetis, C. and Walrand, J. (1994). Decoupling bandwidths: decomposition approach to resource management in networks. In Proc. IEEE INFOCOM 2003 (Toronto, June 1994), pp. 466–473.CrossRefGoogle Scholar
[15] Wischik, D. (1999). The output of a switch, or, effective bandwidths for networks. Queueing Systems 32, 383–396.CrossRefGoogle Scholar
[16] Wischik, D. (2000). Sample path large deviations for queues with many inputs. Ann. Appl. Prob. 11, 379–404.Google Scholar