Binary Exponential Backoff

Contention Window doubles with every retransmission in BEB. Source: Yazid et al. 2014, fig. 2.
Contention Window doubles with every retransmission in BEB. Source: Yazid et al. 2014, fig. 2.

When multiple entities attempt to gain access to a shared resource, only one of them will succeed. Those who fail wait till the resource becomes available and then retry. But if everyone were to retry at the same time, quite possibly none of them will succeed. Moreover, new packets are arriving in addition to those waiting for retries.

Binary Exponential Backoff (BEB) is an algorithm to determine how long entities should backoff before they retry. With every unsuccessful attempt, the maximum backoff interval is doubled. BEB prevents congestion and reduces the probability of entities requesting access at the same time, thereby improving system efficiency and capacity utilization.

BEB was initially proposed for computer networking where multiple computers share a single medium or channel. It's most famously used in Ethernet and Wi-Fi networking standards.

Discussion

  • Where is binary exponential backoff useful?

    BEB is most useful in distributed systems without centralized control or systems that lack predetermined resource allocation. In such systems, multiple entities attempt to access a shared resource. Because there's no centralized control, whoever manages to grab the resource before anyone else will be allowed to use it. Others have to wait for their turn.

    The problem is that when the resource becomes available, everyone else will attempt to grab it. This results in delays. Entities spend time trying to resolve the confusion. Resource utilization is therefore not optimal. The problem gets worse when many entities (dozens or hundreds) are involved.

    BEB is an algorithm that mitigates this problem. BEB is therefore useful in probabilistic systems. It's not useful in deterministic systems where the resource is allocated by a controller, each entity knows its turn and will use the resource at specific times and durations as allocated.

  • Could you explain how BEB works?
    Illustrating collision and backoff. Source: Park 2018, pp. 6.
    Illustrating collision and backoff. Source: Park 2018, pp. 6.

    Consider Wi-Fi as an example. Two Wi-Fi stations Sue and Mira want to send data to Arnold. When the stations access the channel at the same time, we say that it's a collision. Stations whose packets have just collided will initiate a backoff procedure. Every station maintains a number called Contention Window (CW). The station will choose a random value within this window. This value, which is really the number of idle transmission slots that the station has to wait, is called the Backoff Period. During this period, these stations (Sue and Mira) cannot transmit.

    The essence of BEB is that the backoff period is randomly selected within the CW. Each station will potentially have a different waiting time. They can't transmit until the backoff period has passed. Moreover, when another station gains access, backoff timer is paused. It's resumed only when the channel becomes idle again as determined by Distributed Interframe Space (DIFS).

    With every collision, the station will double its CW. This is why the prefix "binary exponential" is used. It's common to have minimum and maximum values for CW.

  • Could you share some facts or details about BEB?
    Some problems with BEB. Source: Ho et al. 2001, slide 23.
    Some problems with BEB. Source: Ho et al. 2001, slide 23.

    BEB doesn't eliminate collisions. By staggering the channel access due to random backoff, it reduces the probability of collision. It's possible that two nodes that collide may backoff the same amount and collide again when they retry. Collision can also happen with nodes that collided long ago and whose backoff just completed.

    It may be argued that randomizing the backoff with every retry is enough to lower the collision probability. Why do we need to double the contention window (CW)? This is because new packets are getting generated and need to be transmitted in addition to collided packets. If CW is not increased, we'll have network congestion with more nodes vying for the channel within the same time. However, doubling the CW is not optimal when network load is low.

    Often minimum CW is non-zero, so that retrying nodes backoff at least some amount before retrying. Likewise, there's a maximum CW so that nodes are not starved due to long backoff periods.

  • What are some well-known applications of BEB?
    Backoff times between TCP retransmissions double with each attempt. Source: Ye 2017.
    Backoff times between TCP retransmissions double with each attempt. Source: Ye 2017.

    Medium Access Control (MAC) layer of networking protocols use BEB. For example, both Ethernet and Wi-Fi use Truncated BEB to set the contention window. Actual backoff is selected randomly within the contention window. Due to this randomization, the term Randomized Exponential Backoff is sometimes used.

    Transmission Control Protocol (TCP) is a protocol that guarantees packet delivery by acknowledging correctly received packets. If acknowledgements are not received, the sender will retransmit the packet. Immediate retransmission can potentially congest the network. Hence, the sender uses BEB before retransmitting.

    In a mobile ad hoc network, routes are discovered when required. It's possible for an attacker to flood the network with Route Request (RREQ) packets. One defence against this is BEB. RREQ packets that are seen too soon (not obeying BEB backoffs) are dropped.

    In network applications, when a request fails due to contention, BEB with jitter is used for retries. Examples include access to AWS DynamoDB, or Google Cloud Storage.

    In general, BEB and its variants are used in wired/wireless networks, transactional memory, lock acquisition, email retransmission, congestion control and many cloud computing scenarios.

  • What metrics are useful to measure the performance and stability of BEB?

    The following metrics are commonly used:

    • Throughput: This is the number of packets per second successfully sent over the channel. Algorithm is considered stable if the throughput does not collapse as the offered load goes to infinity. Offered load can be defined as number of nodes waiting to transmit or total packet arrival rate relative to channel capacity.
    • Delay: Nodes that experience a collision, backoff and retry later. Delay increases as the channel experiences more packet collisions. Algorithm is considered stable if the delay is bounded.
    • Call Count: This is the average number of retries needed to achieve a successful transmission.

    Other metrics useful during analysis include probability of collision \(p_c\) and probability that a node will transmit in an arbitrary time slot \(p_t\). Sometimes BEB is generalized to exponential backoff, with a backoff factor \(r\). With BEB, \(r\) is set to 2. It's been shown that the optimum backoff factor that maximizes asymptotic throughput is \(1/(1-e^{-1})\).

  • What's the Capture Effect that occurs with BEB?

    Capture Effect points to a lack of fairness for channel access. Nodes that experience collisions will be in their backoff procedures. New nodes entering the system have a higher chance to capture the channel. These new nodes can therefore transmit long sequences of packets while others are waiting for their backoffs to end. Even if old and new nodes collide, newer nodes will have shorter backoff and will therefore gain access more quickly.

    Capture effect has been studied for the Ethernet scenario. It was found that the effect is severe for small number of nodes and improves as more nodes contend for the channel. One proposed solution is to use Capture Avoidance Binary Exponential Backoff (CABEB).

    Capture effect is different from starvation effect. With starvation, some nodes have little chance to transmit while most are able to transmit. With capture effect, a few nodes occupy the channel most of the time.

  • What are some variations of BEB?
    Adding jitter reduces repeat collisions. Source: Brooker 2015.
    Adding jitter reduces repeat collisions. Source: Brooker 2015.

    By definition, BEB simply doubles the backoff with every collision. So two nodes that collide with their first attempt will most likely collide again since their retries coincide. For this reason, an element of randomness is added to the backoff. This could be termed as jitter.

    Alternatively, nodes could select a random slot within the contention window as standardized in Ethernet or Wi-Fi. In a modified BEB, each successive slot will be selected with a probability of \(1/2^i\) after \(i\) collisions. This means that next retry can potentially happen after \(2^i\) slots.

    With Truncated BEB, a maximum backoff time is defined so that nodes that experience lots of collisions don't end up waiting longer and longer. However, there may be limit to the maximum number of retries. In Wi-Fi, CW is in the range [23, 1023].

    Other variations include continuously listening to the channel and modifying the backoff; tuning the CW based on slot utilization and collision count; increasing the CW with every alternate collision.

Milestones

1970

Norman Abramson proposes the use of a shared broadcast channel for the ALOHA system. This system would use radio communications to connect computers of the University of Hawaii spread across the islands of Hawaii. The system comes into operation in June 1971. The design of ALOHA didn't define any backoff since it was assumed that both new and retransmitted packets arrive according to a Poisson process.

1973
Simulation results show that throughput depends on K. Source: Lam 1973, fig. 1.
Simulation results show that throughput depends on K. Source: Lam 1973, fig. 1.

Leonard Kleinrock and Simon S. Lam propose the first backoff algorithm for multiple access in slotted ALOHA. A uniform random retransmission delay over K slots is proposed. Channel throughput increases with K but when K goes to infinity channel throughput approaches 1/e. In July, Lam shows that with fixed K backoff, slotted ALOHA is unstable. This suggests that K has to be adaptive.

1975

Simon S. Lam and Leonard Kleinrock propose an adaptive backoff algorithm called Heuristic RCP (Retransmission Control Procedure). The idea is to adapt K based on the number of collisions (m) a packet has experienced. If K increases steeply with respect to m, channel saturation won't happen. Binary exponential backoff is a special case of Heuristic RCP where \(K=2^m\).

2005
High priority traffic is given smaller interframe spacing and contention window. Source: Cisco 2017, fig. 2-8.
High priority traffic is given smaller interframe spacing and contention window. Source: Cisco 2017, fig. 2-8.

IEEE publishes IEEE 802.11e, an amendment to the 802.11 standard. This specifies Quality of Service (QoS) enhancements at the MAC layer. It proposes a feature named Enhanced Distributed Channel Access (EDCA). Traffic is categorized by type into an Access Category (AC). Each AC has its own interframe spacing, and minimum and maximum values for the contention window. This is the way traffic is prioritized towards channel access.

References

  1. Abramson, Norman. 1985. "Development of the ALOHANET." IEEE Trans. on Info Theory, vol. 31, no. 2, pp. 119-123, March. Accessed 2018-12-19.
  2. Ang Eu, Zhi and Winston Seah. 2006. "Mitigating Route Request Flooding Attacks in Mobile Ad Hoc Networks." Information Networking, Advances in Data Communications and Wireless Networks: International Conference, ICOIN 2006, Sendai, Japan, January 16-19, Revised Selected Papers, pp. 327-336. Accessed 2019-01-13.
  3. Bender, Michael A., Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. 2015. "How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness." arXiv, Cornell University, July 12. Accessed 2018-12-19.
  4. Brooker, Marc. 2015. "Exponential Backoff And Jitter." Blog, Amazon Web Services, March 04. Accessed 2018-12-19.
  5. Choi, Nakjung, Yongho Seok, Yanghee Choi, Sungmann Kim, and Hanwook Jung. 2005. "P-DCF: enhanced backoff scheme for the IEEE 802.11 DCF." IEEE 61st Vehicular Technology Conference, Stockholm, vol. 3, pp. 2067-2070. Accessed 2018-12-19.
  6. Cisco. 2017. "WLAN Quality of Service." Chapter 2 in: Voice over Wireless LAN 4.1 Design Guide, Cisco, November 23. Accessed 2020-07-24.
  7. Google Cloud Docs. 2018. "Truncated Exponential Backoff." Google Cloud, October 23. Accessed 2018-12-19.
  8. Ho, Jin-Meng, Sid Schrum, Khaled Turki, Donald P. Shaver, and Matthew B. Shoemake. 2001. "Presentation for Proposed Enhanced Contention Access." IEEE doc. 802.11-01/137, March. Accessed 2018-12-19.
  9. Khan, Pervez, Niamat Ullah, Farman Ali, Sana Ullah, Youn-Sik Hong, Ki-Young Lee, and Hoon Kim. 2017. "Performance Analysis of Different Backoff Algorithms for WBAN-Based Emerging Sensor Networks." Sensors, vol. 17, no. 3, March. Accessed 2018-12-19.
  10. Kwak, Byung-Jae, Nah-Oak Song, and Leonard E. Miller. 2005. "Performance Analysis of Exponential Backoff." IEEE/ACM Trans. on Networking, vol. 13, no. 2, pp. 343-355, April. Accessed 2018-12-19.
  11. Lam, Simon S. 1973. "Some Satellite Simulation Results." ARPANET Satellite System Note 48 (NIC 17655), July 09. Accessed 2019-01-12.
  12. Lam, Simon S. 2018. "Adaptive Backoff Algorithms for Multiple Access: A History." Networking Research Laboratory, Department of Computer Sciences, The University of Texas at Austin. Accessed 2018-12-19.
  13. Lee, Youngho, Byeongung Kim, Jeongbae Yun, Seonhwan Hwang, Gihyuk Seong, Kyuchang Lee, and Kijun Han. 2012. "A Traffic Adaptive Backoff Approach for Wireless Networks." CENTRIC 2012 : The Fifth International Conference on Advances in Human-oriented and Personalized Mechanisms, Technologies, and Services, Lisbon, Portugal, November 18-23. Accessed 2018-12-19.
  14. Park, Kihong. 2018. "IEEE 802.11 MAC." Wireless, CS536, Purdue University. Accessed 2018-12-19.
  15. Ramakrishnan, K.K. and Henry Yang. 1994. "The Ethernet capture effect: analysis and solution." IEEE Proceedings of 19th Conference on Local Computer Networks, October 2-5, Minneapolis, USA. Accessed 2019-01-13.
  16. Song, Nah-Oak, Byung-Jae Kwak, and Leonard E. Miller. 2003. "On the Stability of Exponential Backoff." J Res Natl Inst Stand Technology, Jul-Aug, vol. 108, no. 4, pp. 289–297. Accessed 2019-01-12.
  17. Wikipedia. 2020. "IEEE 802.11e-2005." Wikipedia, January 19. Accessed 2020-07-24.
  18. Yazid, Mohand, Louiza Bouallouche-Medjkoune, and Aissani, Djamil. 2014. "Modeling and Performance Study of the Packet Fragmentation in an IEEE 802.11e-EDCA Network over Fading Channel." IJMTA (International Journal Multimedia Tools and Applications) Springer Ed. 74, via ResearchGate. Accessed 2018-12-19.
  19. Ye, Chen. 2017. "The points of TCP retransmission you must know (1)." Chen's Blog, May 05. Accessed 2018-12-19.

Further Reading

  1. Brooker, Marc. 2015. "Exponential Backoff And Jitter." Blog, Amazon Web Services, March 04. Accessed 2018-12-19.
  2. Goodman, Jonathan, Albert Greenberg, Neal Madras, and Peter March. 1988. "Stability of binary exponential backoff." J. ACM, vol. 35, no. 3, pp. 579-602, via ResearchGate. Accessed 2018-12-19.
  3. Kwak, Byung-Jae, Nah-Oak Song, and Leonard E. Miller. 2005. "Performance Analysis of Exponential Backoff." IEEE/ACM Trans. on Networking, vol. 13, no. 2, pp. 343-355, April. Accessed 2018-12-19.
  4. Ahmad, Ibrahim Sayed, Ali Kalakech, and Seifedine Kadry. 2013. "Minimizing Mobiles Communication Time Using Modified Binary Exponential Backoff Algorithm." International Journal of Computer Networks & Communications (IJCNC), vol.5, no.6, November, pp. 85-102, via ResearchGate. Accessed 2018-12-19.
  5. Rettig, Daniel. 1998. "Collision Reduction Algorithm for an Ethernet Backoff Protocol." US Patent No. 5717889, filed 1995-06-30. Accessed 2018-12-19.

Article Stats

Author-wise Stats for Article Edits

Author
No. of Edits
No. of Chats
DevCoins
3
0
3287
3
1
268
1674
Words
11
Likes
38K
Hits

Cite As

Devopedia. 2020. "Binary Exponential Backoff." Version 6, July 24. Accessed 2024-06-25. https://devopedia.org/binary-exponential-backoff
Contributed by
2 authors


Last updated on
2020-07-24 07:07:22
  • Multiple Access Protocols
  • Carrier Sense Multiple Access
  • Collision Probability
  • Backoff Algorithms for Wireless Sensor Networks