article

Performance analysis of exponential backoff

Authors:

Byung-Jae Kwak,

Leonard E. MillerAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 13, Issue 2

Pages 343 - 355

https://doi.org/10.1109/TNET.2005.845533

Published: 01 April 2005 Publication History

Abstract

New analytical results are given for the performance of the exponential backoff (EB) algorithm. Most available studies on EB focus on the stability of the algorithm and little attention has been paid to the performance analysis of EB. In this paper, we analyze EB and obtain saturation throughput and medium access delay of a packet for a given number of nodes N. The analysis considers the general case of EB with backoff factor r; binary exponential backoff (BEB) algorithm is the special case with r = 2. We also derive the analytical performance of EB with maximum retry limit M(EB-M), a practical version of EB. The accuracy of the analysis is checked against simulation results.

References

[1]

{1} R. M. Metcalfe and D. R. Boggs, "Ethernet: distributed packet switching for local computer networks," Commun. ACM, vol. 19, no. 7, pp. 395-404, Jul. 1976.]]

[2]

{2} P802.11, IEEE Standard for Wireless Lan Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Nov. 1997.]]

[3]

{3} D. J. Aldous, "Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels," IEEE Trans. Inform. Theory, vol. 33, no. 2, pp. 219-223, Mar. 1987.]]

[4]

{4} J. Goodman, A. G. Greenberg, N. Madras, and P. March, "Stability of binary exponential backoff," J. ACM, vol. 35, no. 3, pp. 579-602, 1988.]]

[5]

{5} J. R. Shoch and J. A. Hupp, "Measured performance of an ethernet local network," Commun. ACM, vol. 23, no. 12, pp. 711-721, Dec. 1980.]]

[6]

{6} J. Håstad, T. Leighton, and B. Rogoff, "Analysis of backoff protocols for multiple access channels," SIAM J. Comput., vol. 25, no. 4, pp. 740-744, 1996.]]

[7]

{7} D. R. Boggs, J. C. Mogul, and C. A. Kent, "Measured capacity of an ethernet: myths and reality," in Proc. ACM Symp. Commun. Architecture and Protocols (SIGCOMM 88), 1988, pp. 222-234.]]

[8]

{8} K. K. Ramakrishnan and H. Yang, "The ethernet capture effect: analysis and solution," in Proc. 19th Conf. Local Computer Networks, 1994, pp. 228-240.]]

[9]

{9} D. G. Jeong and W. S. Jeon, "Performance of an exponential backoff scheme for slotted-ALOHA protocol in local wireless environment," IEEE Trans. Veh. Technol., vol. 44, no. 3, pp. 470-479, Aug. 1995.]]

[10]

{10} K. Sakakibara, H. Muta, and Y. Yuba, "The effect of limiting the number of retransmission trials on the stability of slotted ALOHA systems," IEEE Trans. Veh. Technol., vol. 49, no. 4, pp. 1449-1453, Jul. 2000.]]

[11]

{11} K. Sakakibara, T. Seto, D. Yoshimura, and J. Yamakita, "On the stability of slotted ALOHA systems with exponential backoff and retransmission cutoff in slow-frequency-hopping channels," in Proc. 4th Int. Symp. Wireless Personal Multimedia Communications, Aalborg, Denmark, Sep. 2001.]]

[12]

{12} G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination function," J. Select. Areas Commun., vol. 18, no. 3, pp. 535-547, Mar. 2000.]]

[13]

{13} F. P. Kelly and I. M. MacPhee, "The number of packets transmitted by collision detect random access schemes," Ann. Probabil., vol. 15, pp. 1557-1568, 1987.]]

[14]

{14} H. Al-Ammal, L. A. Goldberg, and P. MacKenzie, "Binary exponential backoff is stable for high arrival rates," in Proc. 17th Int. Symp. Theoretical Aspects of Computer Science, Lille, France, Feb. 2000.]]

[15]

{15} H. Al-Ammal, "An improved stability bound for binary exponential backoff," Theory Comput. Syst., vol. 30, pp. 229-244, 2001.]]

[16]

{16} L. A. Goldberg and P. D. MacKenzie, "Analysis of practical backoff protocols for contention resolution with multiple servers," J. Comput. Syst. Sci., vol. 58, no. 1, pp. 232-258, 1999.]]

[17]

{17} H. Wu, Y. Pang, K. Long, S. Cheng, and J. Ma, "Performance of reliable transport protocol over IEEE 802.11 wireless lan: analysis and enhancement," in Proc. IEEE INFOCOM, vol. 2, Jun. 2002, pp. 599-607.]]

[18]

{18} P802.3, Carrier Sense Multiple Access With Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications, Mar. 1991.]]

Cited By

Zhao XDai L(2024)Connection-Based Aloha: Modeling, Optimization, and Effects of Connection EstablishmentIEEE Transactions on Wireless Communications10.1109/TWC.2023.328490723:2(1008-1023)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TWC.2023.3284907
Wu SDai HXu LLiu LXiao FXu J(2023)Comprehensive Cost Optimization for Charger Deployment in Multi-hop Wireless ChargingIEEE Transactions on Mobile Computing10.1109/TMC.2022.316211222:8(4563-4577)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3162112
Nikolay KMikhail P(2023)Probabilistic Modeling of the Behavior of a Computing Node in the Absence of Tasks on the Project ServerSupercomputing10.1007/978-3-031-49435-2_5(62-76)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49435-2_5
Show More Cited By

Index Terms

Performance analysis of exponential backoff
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

An Adaptive Backoff Algorithm Based on Channel Utilization for IEEE 802.11

Though the binary exponential backoff (BEB) is a popular algorithm of collision avoidance in the IEEE 802.11 MAC protocol due to simple implementation, it causes the short-term unfair problem. Another popular algorithm is the history based adaptive ...
A smart exponential-threshold-linear backoff mechanism for IEEE 802.11 WLANs

Based on the standardized IEEE 802.11 Distributed Coordination Function (DCF) protocol, this paper proposes a new backoff mechanism, called Smart Exponential-Threshold-Linear (SETL) Backoff Mechanism, to enhance the system performance of contention-...
Enhancing the performance of ieee 802.11 wlan using multi rate backoff algorithm
WMuNeP '07: Proceedings of the 3rd ACM workshop on Wireless multimedia networking and performance modeling

In the IEEE 802.11 Wireless Local Area Networks (WLANs), after each collision on the shared channel, network nodes sending collided packets.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 13, Issue 2

April 2005

238 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2005

Published in TON Volume 13, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

77
Total Citations
View Citations
1,214
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao XDai L(2024)Connection-Based Aloha: Modeling, Optimization, and Effects of Connection EstablishmentIEEE Transactions on Wireless Communications10.1109/TWC.2023.328490723:2(1008-1023)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TWC.2023.3284907
Wu SDai HXu LLiu LXiao FXu J(2023)Comprehensive Cost Optimization for Charger Deployment in Multi-hop Wireless ChargingIEEE Transactions on Mobile Computing10.1109/TMC.2022.316211222:8(4563-4577)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3162112
Nikolay KMikhail P(2023)Probabilistic Modeling of the Behavior of a Computing Node in the Absence of Tasks on the Project ServerSupercomputing10.1007/978-3-031-49435-2_5(62-76)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49435-2_5
Chen JManivannan MAbduljabbar MPericàs M(2022)ERASE: Energy Efficient Task Mapping and Resource Management for Work Stealing RuntimesACM Transactions on Architecture and Code Optimization10.1145/351042219:2(1-29)Online publication date: 7-Mar-2022
https://dl.acm.org/doi/10.1145/3510422
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
Eroğlu AOnur E(2022)Revisiting Slotted ALOHA: Density Adaptation in FANETsWireless Personal Communications: An International Journal10.1007/s11277-021-09428-6124:2(1711-1740)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s11277-021-09428-6
Yamada HOkita MIno F(2022)Accelerating Imbalanced Many-to-Many Communication with Systematic Delay InsertionParallel and Distributed Computing, Applications and Technologies10.1007/978-3-031-29927-8_33(426-437)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-29927-8_33
Liu JDong WZhou QLi D(2021)FauceProceedings of the VLDB Endowment10.14778/3476249.347625414:11(1950-1963)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476254
Kadota IModiano E(2021)Age of Information in Random Access Networks with Stochastic ArrivalsIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488897(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488897
Anderton WChakraborty TYoung M(2021)Windowed backoff algorithms for WiFi: theory and performance under batched arrivalsDistributed Computing10.1007/s00446-021-00403-934:5(367-393)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00446-021-00403-9
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents