More Web Proxy on the site http://driver.im/

article

Free access

Stability of binary exponential backoff

Authors:

Jonathan Goodman,

Albert G. Greenberg,

Peter MarchAuthors Info & Claims

Journal of the ACM (JACM), Volume 35, Issue 3

Pages 579 - 602

https://doi.org/10.1145/44483.44488

Published: 01 June 1988 Publication History

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.

References

[1]

ALDOUS, D. Ultimate instability of exponential back-off protocol for acknowledgement-based transmission control of random access communication channels. IEEE Trans. Inf. Theory IT-33, 2 (Nov. 1987), 219-233.

[2]

CAPETANAKIS, J. I. Tree algorithms for packet broadcast channels. IEEE Trans. Inf. Theory IT-25, 5 (Sept. 1979), 505-515.

[3]

COTTRELL, M., FORT, J.-C., AND MALGOUYRES, G. Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Automatic Cont. AC-28, 9 (1983), 907-920.

[4]

FAYOLLE, G., GELEMBE, E., AND LABETOULLE, J. Stability and optimal control of a packet switching broadcast channel. J. ACM 24 (July 1977), 375-386.

[5]

FLAJOLET, P. Approximate counting: A detailed analysis. BIT 25 (1985), 113-134.

[6]

GALLAGER, R.G. A perspective on multiaccess channels. IEEE Trans. Inf. Theory IT-31, 2 (Mar. 1985), 124-142.

[7]

GOODMAN, J., GREENBERG, A., MADRAS, N., AND MARCH, P. On the stability of the Ethernet. In Proceedings of the 17th Annual A CM Symposium on Theory of Computing (Providence, R.I., May). ACM, New York, 1985, pp. 379-387.

[8]

GREENBERG, A. G., FLAJOLET, P., AND LADNER, R.E. Estimating the multiplicities of conflicts to speed their resolution in multiple access channels. J. ACM 34, 2 (Apr. 1987), 289-326.

[9]

HAJEK, B., AND VAN I.A:)ON, T. Decentralized dynamic control of a multiaccess broadcast channel. IEEE Trans. Automatic Cont. AC-27, 3 (June 1982), 559-569.

[10]

HASTAD, J., LEIGHTON, T., AND ROGOFF, B. Analysis of backoff protocols for multiple access channels. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York City, N.Y., May). ACM, New York, 1987, pp. 241-253.

[11]

HAYES, J. F. An adaptive technique for local distribution. IEEE Trans. Commun. COM-29, 6 (June 1978), 1178-1186.

[12]

KARLIN, S. h First Course in Stochastic Processes, 1st ed. Academic Press, Orlando, Fla., 1966.

[13]

KELLY, F.P. Stochastic models of computer communication systems. J. Roy. Stat. Soc., Ser. B 47, 3 (1985), 379-395.

[14]

KUMAR, e. R. S., AND MERAKOS, L. Distributed control of broadcast channels with acknowledgement feedback: Stability and performance. In Proceedings of the IEEE Control and Decision Conference (Las Vegas, Nev., Dec.). IEEE, New York, 1984.

[15]

LAM, S. A carrier sense multiple access protocol for local networks. Comput. Netw. 4 (Feb. 1980), 21-32.

[16]

MATHYS, P., AND FLAJOLET, P. Q-ary collision resolution algorithms in random-access systems with free or blocked channel access. IEEE Trans. Inf. Theory IT-31, 2 (March 1985), 217-243.

[17]

METCALFE, R. M., AND BOGGS, D.R. Ethernet: Distributed packet switching for local computer networks. Commun. ACM 19, 7 (July 1976), 395-404.

[18]

MIKHAILOV, V.A. Methods of random multiple access. Candidate English thesis. Moscow institute of Physics and Technology, Moscow, USSR, 1979.

[19]

RIVEST, R. L. Network control by Bayesian broadcast. Tech. Rep. TM-287, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., Sept. 1985.

[20]

ROSENKRANTZ, W. Approximate Counting: A martingale approach. Stochastics 27, 1987, 111-120.

[21]

ROSENKRANTZ, W. A., AND TOWSLEY, n. On the instability of the slotted ALOHA multiaccess algorithm. IEEE Trans. Automatic Cont. AC-28, 10 (1984), 994-996.

[22]

SHENKER, S. Some conjectures on the behavior of acknowledgment based transmission control of random access communication channels. In Proceedings of the Sigmetrics "87 Conference on Measurement and Modelling of Computer Systems (Banff, Alberta, Canada). ACM, New York, 1987.

[23]

SHOCH, J. R., AND HUPP, J.A. Measured performance of an Ethernet local network. Commun. ACM 23, 12 (Dec. 1980), 711-721.

[24]

SZPANKOWSKI, W., AND REGO, V. Instability conditions arising in analysis of some multiaccess protocols. Tech. Rep. CSD-TR-577. Purdue Univ., Lafayette, Ind., Feb. 1986.

[25]

TANNENBAUM, A.S. Computer Networks. Prentice Hall, Englewood Cliffs, N.J., 1981.

[26]

TSYBAKOV, B. S., AND MIKHAILOV, V.A. Free synchronous packet access in a broadcast channel with feedback. Probl. Inf. Transm. 14, 4 (April 1979), 259-280 (translated from Russian original in ProbL Peredachi Inf. 14, 4 (Oct.-Dec. 1978), 32-59).

[27]

TSYBAKOV, B. S., AND MIKHAILOV, V.A. Ergodicity of a slotted Aloha system. ProbL Inf. Transm. 15, 4 (April 1980) (translated from Russian original in ProbL Peredachi Inf. 15, 4 (Oct.-Dec. 1979), 72-87).

[28]

TSYBAKOV, B. S., AND VVENDENSKAYA, N.D. Random multiple-access stack algorithm. ProbL Inf. Transm. I6, 3 (Jan. 1982), 230-243 (translated from Russian original in Probl. Peredachi Inf. 16, 3 (July-Sept. 1980), 80-94).

[29]

WEISS, A., AND GREENBERG, A.G. An analysis of aloha systems via large deviations, preprint (June 1986).

Cited By

Goldberg LLapinskas J(2025)Instability of backoff protocols with arbitrary arrival ratesJournal of Computer and System Sciences10.1016/j.jcss.2025.103638(103638)Online publication date: Mar-2025
https://doi.org/10.1016/j.jcss.2025.103638
Bender MFineman JGilbert SKuszmaul JYoung MKuznetsov PGelles ROlivetti D(2024)Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention ResolutionProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662807(231-242)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662807
Wang SJiang ZLi XMa J(2024)K-Backup: Load- and TCAM-Aware Multi-Backup Fast Failure Recovery in SDNsIEEE/ACM Transactions on Networking10.1109/TNET.2024.338609132:4(3347-3360)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3386091
Show More Cited By

Recommendations

Fast backoff counter reduction algorithm to enhance the binary negative-exponential backoff algorithm in heterogeneous condition
ICUIMC '08: Proceedings of the 2nd international conference on Ubiquitous information management and communication

BNEB has better collision resolution performance than the conventional DCF with BEB when BNEB stations only contend with themselves. BNEB stations use larger contention window size than DCF stations when they attempt first transmission of a frame or ...
Performance analysis of binary exponential backoff and improved backoff for WPAN
Special issue on advances in quality and performance assessment for future wireless communication services

The IEEE 802.15.3 medium access control (MAC) is proposed, especially, for wireless personal area network (WPAN) short and high data rates applications, to coordinate the access to the wireless medium among the competing devices. A concept of a ...
Enhanced binary exponential backoff algorithm for fair channel access in the ieee 802.11 medium access control protocol

The medium access control protocol determines system throughput in wireless mobile ad hoc networks following the ieee 802.11 standard. Under this standard, asynchronous data transmissions have a defined distributed coordination function that allows ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 35, Issue 3

July 1988

280 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/44483

Issue’s Table of Contents

Copyright © 1988 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Published in JACM Volume 35, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
1,780
Total Downloads

Downloads (Last 12 months)162
Downloads (Last 6 weeks)21

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Goldberg LLapinskas J(2025)Instability of backoff protocols with arbitrary arrival ratesJournal of Computer and System Sciences10.1016/j.jcss.2025.103638(103638)Online publication date: Mar-2025
https://doi.org/10.1016/j.jcss.2025.103638
Bender MFineman JGilbert SKuszmaul JYoung MKuznetsov PGelles ROlivetti D(2024)Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention ResolutionProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662807(231-242)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662807
Wang SJiang ZLi XMa J(2024)K-Backup: Load- and TCAM-Aware Multi-Backup Fast Failure Recovery in SDNsIEEE/ACM Transactions on Networking10.1109/TNET.2024.338609132:4(3347-3360)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3386091
O’Brien MWilliams JChen SPitt AArkin RKottege N(2023)Dynamic task allocation approaches for coordinated exploration of Subterranean environmentsAutonomous Robots10.1007/s10514-023-10142-447:8(1559-1577)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s10514-023-10142-4
Zhai JJin YChen WZheng WZhai JJin YChen WZheng W(2023)Production-Run Noise DetectionPerformance Analysis of Parallel Applications for HPC10.1007/978-981-99-4366-1_8(199-224)Online publication date: 19-Jun-2023
https://doi.org/10.1007/978-981-99-4366-1_8
Zheng LZhai JTang XWang HYu TJin YSong SChen WLee JAgrawal KSpear M(2022)VaproProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508411(150-162)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508411
Jiang YZheng CAgrawal KLee I(2022)Robust and Optimal Contention Resolution without Collision DetectionProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538592(107-118)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538592
Bender MGilbert SKuhn FKuszmaul JMédard MAgrawal KLee I(2022)Contention Resolution for Coded Radio NetworksProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538573(119-130)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538573
Jadoon MPastore ANavarro MPerez-Cruz F(2022)Deep Reinforcement Learning for Random Access in Machine-Type Communication2022 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC51071.2022.9771953(2553-2558)Online publication date: 10-Apr-2022
https://dl.acm.org/doi/10.1109/WCNC51071.2022.9771953
Zhai JZheng LZhang FTang XWang HYu TJin YSong SChen W(2022)Detecting Performance Variance for Parallel Applications Without Source CodeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.318179933:12(4239-4255)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TPDS.2022.3181799
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents