Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T12:26:36.692Z Has data issue: false hasContentIssue false
  • English
  • Français

On fast simulation of the time to saturation of slotted ALOHA

Part of: Limit theorems

Published online by Cambridge University Press:  14 July 2016

V. Anantharam
V. Anantharam*
Affiliation:
Cornell University
*
∗Postal address: School of Electrical Engineering, Cornell University, Ithaca, NY 14853, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Cottrell et al. (1983) have indicated how ideas from the large deviations theory lead to fast simulation schemes that estimate the mean time taken by the slotted ALOHA protocol to saturate starting empty. Such fast simulation schemes are particularly useful when the attempt probability is small. The remaining time to saturation when the protocol has been operating for a time is more accurately described by the quasi-stationary exit time from the stable regime. The purpose of this article is to prove that the ratio of the quasi-stationary exit time to the exit time starting empty approaches 1 as the attempt probability becomes small.

Keywords

IMPORTANCE SAMPLINGLARGE DEVIATIONSMULTIPLE-ACCESSQUASI-STATIONARY DISTRIBUTION

MSC classification

Secondary: 60F10: Large deviations
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 3 , September 1992 , pp. 682 - 690
Copyright
Copyright © Applied Probability Trust 1992 

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

Research supported by NSF under NCR 8710840 and a PYI award, by IBM under a Faculty Development Award, and by BellCore Inc.

References

[1] IEEE Trans. Inf. Theory. Special issue on random access communications 31(2).Google Scholar
[2] Abramson, N. (1970) The ALOHA system - another alternative for computer communications. Proc. AFIPS Conf. Fall Joint Computer Conference 37, pp. 281–285.CrossRefGoogle Scholar
[3] Bertsekas, D. and Gallager, R. (1987) Data Networks. Prentice-Hall, Englewood Cliffs., NJ.Google Scholar
[4] Cottrell, M., Fort, J. C. and Malgouyres, G. (1983) Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Autom. Control. 28, 907–920.Google Scholar
[5] Darroch, J. and Seneta, E. (1965) On quasi-stationary distributions in absorbing discrete-time finite Markov chains. J. Appl. Prob. 2, 88–100.CrossRefGoogle Scholar
[6] Hajek, B. (1982) Hitting time and occupation time bounds implied by drift analysis, with applications. Adv. Appl. Prob. 14, 502–525.CrossRefGoogle Scholar
[7] Kielson, J. (1979) Markov Chain Models - Rarity and Exponentiality. Springer-Verlag, Berlin.CrossRefGoogle Scholar
[8] Neveu, J. (1975) Discrete Parameter Martingales. North-Holland, Amsterdam.Google Scholar
[9] Parekh, S., Schoute, F. and Walrand, J. (1987) Instability and geometric transience of the ALOHA protocol. Proc. 26th IEEE Conf. Decision and Control, Los Angeles, CA., pp. 1073–1077.CrossRefGoogle Scholar
[10] Parekh, S. and Walrand, J. (1989) A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Autom. Control 34, 54–66.Google Scholar
[11] Ross, S. (1983) Stochastic Processes. Wiley, New York.Google Scholar
[12] Schoute, F. (1982) Determination of stability of a Markov process by eigenvalue analysis applied to the access capacity enhancement ALOHA protocol. Philips Research Internal Report (cited in [9]).Google Scholar
[13] Walrand, J. (1988) An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
[14] Weiss, A. (1986) A new technique for analyzing large traffic systems. Adv. Appl. Prob. 18, 506–532.Google Scholar