Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T10:15:28.288Z Has data issue: false hasContentIssue false
  • English
  • Français

Cell loss asymptotics for buffers fed with a large number of independent stationary sources

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

Published online by Cambridge University Press:  14 July 2016

Nikolay Likhanov  and
Ravi R. Mazumdar
Nikolay Likhanov*
Affiliation:
Institute for Problems of Information Transmission
Ravi R. Mazumdar*
Affiliation:
University of Essex
*
∗Postal address: Institute for Problems of Information Transmission, 19 Bolshoi Karetnyi, GSP-4, Moscow 101447, Russia.
∗∗Postal address: Department of Mathematics, University of Essex, Colchester CO4 3SQ, UK. Email address: [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we derive asymptotically exact expressions for buffer overflow probabilities and cell loss probabilities for a finite buffer which is fed by a large number of independent and stationary sources. The technique is based on scaling, measure change and local limit theorems and extends the recent results of Courcoubetis and Weber on buffer overflow asymptotics. We discuss the cases when the buffers are of the same order as the transmission bandwidth as well as the case of small buffers. Moreover we show that the results hold for a wide variety of traffic sources including ON/OFF sources with heavy-tailed distributed ON periods, which are typical candidates for so-called ‘self-similar’ inputs, showing that the asymptotic cell loss probability behaves in much the same manner for such sources as for the Markovian type of sources, which has important implications for statistical multiplexing. Numerical validation of the results against simulations are also reported.

Keywords

ATMfinite bufferscell loss asymptoticsBahadur–Rao theoremrate functionsheavy-tailed distributions

MSC classification

Primary: 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Secondary: 60F10: Large deviations 60K25: Queueing theory 90B22: Queues and service
Type
Research Papers
Information
Journal of Applied Probability , Volume 36 , Issue 1 , March 1999 , pp. 86 - 96
Copyright
Copyright © Applied Probability Trust 1999 

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

References

Anantharam, V. (1995). On the sojourn time of sessions at an ATM buffer with long-range dependent input traffic. In Proc. 34th. IEEE CDC, IEEE Control Systems Society, New York.Google Scholar
Bahadur, R. R., and Ranga Rao, R. (1960). On deviations of the sample mean. Ann. Math. Statist. 31, 1015–1027.CrossRefGoogle Scholar
Botvich, A., and Duffield, N. G. (1995). Large deviations, economies of scale and the shape of the loss curve in large multiplexers. Queueing Systems 20, 293–320.CrossRefGoogle 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
Courcoubetis, C., and Weber, R. (1996). Buffer overflow asymptotics for a switch handling many traffic sources. J. Appl. Prob. 33, 886–903.Google Scholar
Duffield, N. G., and O'Connell, N. (1995). Large deviations and overflow probabilities for the general single-server queue with applications. Math. Proc. Camb. Phil. Soc. 118, 363–374.Google Scholar
Ganesh, A., and Anantharam, V. (1994). Correctness within a constant of an optimal buffer allocation rule of thumb. IEEE Trans. Inf. Theory 40, 871–882.Google Scholar
Guibert, A. (1994). Overflow probability upperbound in fluid queues with general on/off sources. J. Appl. Prob. 31, 1134–1139.Google Scholar
Kelly, F. P. (1991). Effective bandwidths at multi-class queues. Queueing Systems 19, 5–16.Google Scholar
Kesidis, G., Walrand, J., and Chang, C. S. (1993). Effective bandwidths for multi-class Markov fluids and other ATM sources. IEEE/ACM Trans. Networking 1, 424–428.CrossRefGoogle Scholar
Konstantopoulos, T., and Lin, S.-J. (1996). High variability vs long-range dependence for network performance. Proc. 35th. IEEE CDC. IEEE Control Systems Society, New York, pp. 1354–1359.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
Likhanov, N., Tsybakov, B., and Georganas, N. D. (1995). Analysis of an ATM buffer with self-similar (‘fractal’) input traffic. Proc. IEEE INFOCOM'95. IEEE Computer Society, New York, pp. 985–992.Google Scholar
Likhanov, N., Mazumdar, R. R. and Théberge, F. (1996). Calculation of cell loss probabilities in large unbuffered multiservice systems. Proc. IEEE ICC '96. IEEE Communications Society, New York.Google Scholar
Norros, I. (1994). A storage model with self-similar input. Queueing Systems 16, 387–396.Google Scholar
Petrov, V. V. (1975). Sums of Independent Random Variables. Springer, Berlin.Google Scholar
Schwartz, A., and Weiss, A. (1995). Large deviations for performance analysis: queues, communications and computing. Chapman and Hall, UK.Google Scholar
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
Taqqu, M. S., and Levy, J. (1986). Using renewal processes to generate long-range dependence and high variability. In Dependence in Probability and Statistics, ed. Eberlein, E. and Taqqu, M. S. Birkhäuser, Boston, pp. 73–89.CrossRefGoogle Scholar