Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-16T09:21:06.458Z Has data issue: false hasContentIssue false
  • English
  • Français

Weak convergence of high-speed network traffic models

Part of: Operations research and management science Special processes

Published online by Cambridge University Press:  14 July 2016

Sidney Resnick  and
Eric van den Berg
Sidney Resnick*
Affiliation:
Cornell University
Eric van den Berg*
Affiliation:
Telecordia Technologies
*
∗Postal address: School of Operations Research and Industrial Engineering, Cornell University, 206 Rhodes Hall, Ithaca, NY 14853-3801, USA. Email address: sid@orie.cornell.edu
∗∗Postal address: Telecordia Technologies, 445 South Street, Room 16338B, Movistown, NJ 07960, USA. Email address: evdb@research.telecordia.com
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a network traffic model consisting of an infinite number of sources linked to a server. Sources initiate transmissions to the server at Poisson time points. The duration of each transmission has a heavy-tailed distribution. We show that suitable scalings of the traffic process converge to a totally skewed stable Lévy motion in Skorohod space, equipped with the Skorohod M1 topology. This allows us to prove a heavy-traffic theorem for a single-server fluid model.

Keywords

Fractional Brownian motionPoisson processLévy stable motionhigh speed networkM1 Topology

MSC classification

Primary: 90B15: Network models, stochastic 90B18: Communication networks
Secondary: 90B22: Queues and service 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 2 , June 2000 , pp. 575 - 597
Copyright
Copyright © by the Applied Probability Trust 2000 

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 research was partly supported by NSF Grant DMS-97-04982 at Cornell University. S. Resnick was also partially supported by NSA grant MDA904-98-1-0041 at Cornell. Portions of this work were completed at the University of North Carolina, Chapel Hill, and the hospitality of the Department of Statistics is gratefully acknowledged.

References

Astrauskas, A. (1983). Limit theorems for sums of linearly generated random variables. Lithuanian Math. J. 23, 127–134. Transl. from Litovskii Matematicheskii Sbornik (Lieutuvos Matematikos Rinkinys).CrossRefGoogle Scholar
Avram, F., and Taqqu, M. S. (1989). Probability bounds for M-Skorohod oscillations. Stoch. Proc. Appl. 33, 63–72.Google Scholar
Avram, F., and Taqqu, M. S. (1992). Weak convergence of sums of moving averages in the α-stable domain of attraction. Ann. Prob. 20, 483–503.Google Scholar
Bingham, N. H., Goldie, C. M., and Teugels, J. L. (1987). Regular Variation. Cambridge University Press.Google Scholar
Boxma, O., and Cohen, J. W. (1997). Heavy traffic analysis for the GI/G/1 queue with heavy tailed distributions. Tech. Rept, Centrum voor Wiskunde en Informatica. PNA-R9710, ISSN 1386-3711. Available at http://www.cwi.nl/static/publications/reports/PNA-1997.html.Google Scholar
Brichet, F., Roberts, J., Simonian, A., and Veitch, D. (1996). Heavy traffic analysis of a storage model with long range dependent on/off sources. Queueing Systems 23, 197–215.Google Scholar
Cohen, J. W., Resnick, S., and Samorodnitsky, G. (1998). Sample correlations of infinite variance time series models: an empirical and theoretical study. J. Appl. Math. Stoch. Anal. 11, 255–282.Google Scholar
Cohen, J. W. (1997). Heavy-traffic limit theorems for the heavy-tailed GI/G/1 queue. Tech. Rept, Centrum voor Wiskunde en Informatica. PNA-R9719, ISSN 1386-3711. Available at http://www.cwi.nl/static/publications/reports/PNA-1997.html.Google Scholar
Cohen, J. W. (1998). Heavy-traffic theory for the heavy-tailed M/G/1 queue and ν-stable Lévy noise traffic. Tech. Rept, Centrum voor Wiskunde en Informatica. PNA-R9805, ISSN 1386-3711. Available at http://www.cwi.nl/static/publications/reports/PNA-1998.html.Google Scholar
Cohen, J. W. (1998). The ν-stable Lévy motion in heavy-traffic analysis of queueing models with heavy tailed distributions. Tech. Rept, Centrum voor Wiskunde en Informatica. PNA-R9808, ISSN 1386-3711. Available at http://www.cwi.nl/static/publications/reports/PNA-1998.html.Google Scholar
Davis, R. A., and Mikosch, T. (1997). The sample a.c.f. of heavy tailed stationary processes with applications to ARCH. Ann. Statist. 26, 2049–2080.Google Scholar
de Haan, L. (1970). On Regular Variation and its Application to the Weak Convergence of Sample Extremes. Mathematisch Centrum Amsterdam.Google Scholar
Feigin, P., and Resnick, S. (1996). Pitfalls of fitting autoregressive models for heavy-tailed time series. Available at http://www.orie.cornell.edu/trlist/trlist.html at TR1163.ps.Z; to appear: Extremes 1, 391–422.Google Scholar
Feller, W. (1971). An Introduction to Probability Theory and its Applications, Vol. 2, 2nd edn. Wiley, New York.Google Scholar
Garrett, M. W., and Willinger, W. (1994). Analysis, modeling and generation of self similar v.b.r. video traffic. In Proc. ACM SigComm 94, London, pp. 269–280.CrossRefGoogle Scholar
Geluk, J. L., and de Haan, L. (1987). Regular Variation, Extensions and Tauberian Theorems. CWI Tract., Vol. 40. Stichting Mathematisch Centrum Centrum voor Wiskunde en Informatica, Amsterdam.Google Scholar
Heath, D., Resnick, S., and Samorodnitsky, G. (1997). Patterns of buffer overflow in a class of queues with long memory in the input stream. Ann. Appl. Prob. 7, 1021–1057.CrossRefGoogle Scholar
Heath, D., Resnick, S., and Samorodnitsky, G. (1998). Heavy tails and long range dependence in on/off processes and associated fluid models. Math. Operat. Res. 23, 145–165.Google Scholar
Jelenković, P. R., and Lazar, A. A. (1996). A network multiplexer with multiple time scale and subexponential arrivals. In Stochastic Networks (Lecture Notes in Statistics 117), eds Glasserman, P., Sigman, K. and Yao, D. D. Springer, New York, pp. 215–235.Google Scholar
Jelenković, P. R., and Lazar, A. A. (1997). Asymptotic results for multiplexing subexponential on–off sources. Tech. Rept, Columbia University.Google Scholar
Konstantopoulos, T., and Lin, S.-J. (1998). Macroscopic models for long-range dependent network traffic. Queueing Systems Theory Appl. 28, 215–243.Google Scholar
Leland, W. E., Taqqu, M. S., Willinger, W., and Wilson, D. V. (1994). On the self-similar nature of Ethernet traffic (extended version). IEEE/ACM Trans. Networking 2, 1–15.Google Scholar
Parulekar, M., and Makowski, A. M. (1996). Tail probabilities for a multiplexer with a self-similar traffic. Proc. 15th Ann. IEEE INFOCOM. IEEE, New York, pp. 1452–1459.Google Scholar
Resnick, S. I. (1987). Extreme Values, Regular Variation and Point Processes. Springer, New York.Google Scholar
Resnick, S. (1997). Heavy tail modeling and teletraffic data. Ann. Statist. 25, 1805–1869.Google Scholar
Resnick, S. (1998). Why non-linearities can ruin the heavy tailed modeler's day. In A Practical Guide to Heavy Tails: Statistical Techniques for Analysing Heavy Tailed Distributions. Birkhäuser, Boston.Google Scholar
Resnick, S., and Samorodnitsky, G. (1998). A heavy traffic limit theorem for workload processes with heavy tailed service requirements. Tech. Rept 1221, available at www.orie.cornell.edu/trlist/trlist.html.Google Scholar
Resnick, S. and van den Berg, E. (1998). A test for nonlinearity of time series with infinite variance. Tech. Rept. 1222, available at www.orie.cornell.edu/trlist/trlist.html.Google Scholar
Resnick, S., Samorodnitsky, G., and Xue, F. (1998). Growth rates of sample covariances of stationary symmetric α-stable processes associated with null recurrent Markov chains. To appear in Stoch. Proc. Appl. Tech. Rept. TR1220; available at www.orie.cornell.edu/trlist/trlist.html.Google Scholar
Resnick, S., Samorodnitsky, G., and Xue, F. (1998). How misleading can sample a.c.f.'s of stable m.a.'s be? (very!). Tech. Rept 1209; available at www.orie.cornell.edu/trlist/trlist.html; to appear: Ann. Appl. Prob. 9, 797–817.Google Scholar
Samorodnitsky, G., and Taqqu, M. S. (1994). Stable Non-Gaussian Random Processes. Chapman and Hall, New York.Google Scholar
Skorohod, A. V. (1956). Limit theorems for stochastic processes. Theor. Prob. Appl. 1, 261–290.Google Scholar
Taqqu, M., Willinger, W., and Sherman, R. (1997). Proof of a fundamental result in self-similar traffic modeling. Comput. Commun. Rev. 27.Google Scholar
Whitt, W. (1999). Limits for cumulative input processes to queues. Preprint, AT&T Labs.Google Scholar
Whitt, W. (1999). On the Skorohod m topologies. Preprint, AT&T Labs.Google Scholar
Whitt, W. (1999). The reflection map is Lipschitz with appropriate Skorohod m metrics. Preprint, AT&T Labs.Google Scholar
Willinger, W., and Paxson, V. (1998). Where mathematics meets the internet. Not. Amer. Math. Soc. 45, 961–970.Google Scholar
Willinger, W., Taqqu, M. S., Leland, M., and Wilson, D. (1995). Self-similarity in high-speed packet traffic: analysis and modelling of ethernet traffic measurements. Statist. Sci. 10, 67–85.Google Scholar
Willinger, W., Taqqu, M. S., Leland, M., and Wilson, D. (1995). Self-similarity through high variability: statistical analysis of ethernet LAN traffic at the source level. Comput. Commun. Rev. 25, 100–113. (Proc. ACM/SIGCOMM'95, Cambridge, MA).Google Scholar
Willinger, W., Taqqu, M. S., Leland, M., and Wilson, D. (1996). Self-similarity through high variability: statistical analysis of ethernet LAN traffic at the source level (extended version). IEEE/ACM Trans. Networking, 5, 71–86.Google Scholar