article · Journal of the ACM · 1988
Stability of binary exponential backoff
Jonathan Goodman, Albert Greenberg, Neal Madras, Peter March
Cited by 173Open access
Abstract
Binary exponential backoff is a randomized protocol for regulating transmissions on a multiple-access broadcast channel. Ethernet, a local-area network, is built upon this protocol. The fundamental theoretical issue is stability: Does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? It is assumed n ≥ 2 stations share the channel, each having an infinite buffer where packets accumulate while the station attempts to transmit the first from the buffer. Here, it is established that binary exponential backoff is stable if the sum of the arrival rates is sufficiently small. Detailed results are obtained on which rates lead to stability when n = 2 stations share the channel. In passing, several other results are derived bearing on the efficiency of the conflict resolution process. Simulation results are reported that, in particular, indicate alternative retransmission protocols can significantly improve performance.
Cite this paper
Goodman, J., Greenberg, A., Madras, N., & March, P. (1988). Stability of binary exponential backoff. Journal of the ACM, 35(3), 579–602. https://doi.org/10.1145/44483.44488
Goodman, Jonathan, et al. “Stability of binary exponential backoff.” Journal of the ACM, vol. 35, no. 3, 1988, pp. 579–602, https://doi.org/10.1145/44483.44488.
Goodman, Jonathan, Albert Greenberg, Neal Madras, and Peter March. 1988. “Stability of binary exponential backoff.” Journal of the ACM 35 (3): 579–602. https://doi.org/10.1145/44483.44488.
Goodman, J. et al. (1988) ‘Stability of binary exponential backoff’, Journal of the ACM, 35(3), pp. 579–602. Available at: https://doi.org/10.1145/44483.44488.
@article{goodman1988stability,
title = {{Stability of binary exponential backoff}},
author = {Goodman, Jonathan and Greenberg, Albert and Madras, Neal and March, Peter},
journal = {Journal of the ACM},
volume = {35},
number = {3},
pages = {579--602},
year = {1988},
doi = {10.1145/44483.44488}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.