Analysis of Backoff Protocols for Multiple Access Channels
Authors:
- Johan HåstadJHJohan Håstad
- Tom LeightonTLTom Leighton
- Brian RogoffBRBrian Rogoff
- 1 August 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 25 (4) , 740-774
Abstract
In this paper, we analyze the stochastic behavior of backoff protocols for multiple access channels such as the Ethernet. In particular, we prove that binary exponential backoff is unstable if the arrival rate of new messages at each station is $\tfrac{\lambda }{N}$ for any $\lambda > \frac{1}{2}$ and the number of stations N is sufficiently large. For small N, we prove that $\lambda \geqslant \lambda _0 + \frac{1}{{4N - 2}}$` implies instability, where $\lambda _0 \approx .567$. More importantly, we also prove that any superlinear polynomial backoff protocol (e.g., quadratic backoff) is stable for any set of arrival rates that sum to less than one and any number of stations. The results significantly extend the previous work in the area and provide the first examples of acknowledgment-based protocols known to be stable for a nonnegligible overall arrival rate distributed over an arbitrarily large number of stations. The results also disprove a popular assumption that exponential backoff is the best choice among acknowledgment-based protocols for systems with large overall arrival rates. Finally, we prove that any linear or sublinear backoff protocol is unstable if the arrival rate at each station is $\frac{\lambda }{N}$ for any fixed $\lambda $ and sufficiently large N.
Keywords
This publication has 12 references indexed in Scilit:
- Markov Chains and Stochastic Stability1993
- Some Theorems on Instability with Applications to Multiaccess ProtocolsOperations Research, 1988
- Stability Conditions for Multidimensional Queueing Systems with Computer ApplicationsOperations Research, 1988
- Analysis of a multiaccess control schemeIEEE Transactions on Automatic Control, 1987
- Network control by Bayesian broadcastIEEE Transactions on Information Theory, 1987
- Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channelsIEEE Transactions on Information Theory, 1987
- Decentralized dynamic control of a multiaccess broadcast channelIEEE Transactions on Automatic Control, 1982
- Network ProtocolsACM Computing Surveys, 1981
- Measured performance of an Ethernet local networkCommunications of the ACM, 1980
- Technical Note—A Last Word on L = λWOperations Research, 1974