View source for Exponential backoff

{{Short description|Rate-seeking algorithm}}
{{Use dmy dates|date=January 2024}}
{{Use British English|date=December 2024}}
{{Wiktionary|backoff}}

'''Exponential backoff''' is an [[algorithm]] that uses [[feedback]] to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. These algorithms find usage in a wide range of systems and processes, with [[radio network]]s and [[computer network]]s being particularly notable.

==Exponential backoff algorithm==
An exponential backoff algorithm is a form of [[closed-loop control system]] that reduces the rate of a controlled process in response to adverse events. For example, if a smartphone app fails to connect to its server, it might try again 1 second later, then if it fails again, 2 seconds later, then 4, etc. Each time the pause is multiplied by a fixed amount (in this case 2). In this case, the adverse event is failing to connect to the server. Other examples of adverse events include [[collision (telecommunications)|collisions of network traffic]], an error response from a service, or an explicit request to reduce the rate (i.e. ''back off'').

The rate reduction can be modelled as an [[exponential function]]:

:<math>t = b^c</math>

or

:<math>f = \frac{1}{b^c}</math>

Here, {{math|''t''}} is the time delay applied between actions, {{math|''b''}} is the multiplicative factor or ''base'', {{math|''c''}} is the number of adverse events observed, and {{math|''f''}} is the frequency (or rate) of the process (i.e. number of actions per unit of time). The value of {{math|''c''}} is incremented each time an adverse event is observed, leading to an exponential rise in delay and, therefore, an inversely proportionate rate. An exponential backoff algorithm where {{math|1= ''b'' = 2}} is referred to as a ''binary'' exponential backoff algorithm.

When the rate has been reduced in response to an adverse event, it usually does not remain at that reduced level forever. If no adverse events are observed for some period of time, often referred to as the ''recovery time'' or ''cooling-off period'', the rate may be increased again. The time period that must elapse before attempting to increase the rate again may, itself, be determined by an exponential backoff algorithm. Typically, recovery of the rate occurs more slowly than reduction of the rate due to backoff and often requires careful tuning to avoid [[oscillation]] of the rate.<ref>{{harvnb|Tanenbaum|Wetherall|2010|chapter=5.3|page=395}}</ref> The exact recovery behaviour is implementation-specific and may be informed by any number of environmental factors.

The mechanism by which rate reduction is practically achieved in a system may be more complex than a simple time delay. In some cases, the value {{math|''t''}} may refer to an [[upper bound]] to the time delay, rather than a specific time delay value. The name ''exponential backoff'' refers to the [[exponential growth]] characteristic of the backoff, rather than an exact numeric relationship between adverse event counts and delay times.

==Rate limiting==
Exponential backoff is commonly utilised as part of [[rate limiting]] mechanisms in computer systems such as [[web service]]s, to help enforce fair distribution of access to resources and prevent [[network congestion]]. Each time a service informs a client that it is sending requests too frequently, the client reduces its rate by some predetermined factor, until the client's request rate reaches an acceptable equilibrium. The service may enforce rate limiting by refusing to respond to requests when the client is sending them too frequently so that misbehaving clients are not allowed to exceed their allotted resources.

A benefit of utilising an exponential backoff algorithm, over of a fixed rate limit, is that rate limits can be achieved dynamically without providing any prior information to the client. In the event that resources are unexpectedly constrained, e.g. due to heavy load or a service disruption, backoff requests and error responses from the service can automatically decrease the request rate from clients. This can help maintain some level of availability rather than overloading the service. In addition, [[quality of service]] can be prioritised to certain clients based on their individual importance, e.g. by reducing the backoff for emergency calls on a [[telephone network]] during periods of high load.

In a simple version of the algorithm, messages are delayed by predetermined (non-random) time. For example, in [[Session Initiation Protocol|SIP protocol]] over unreliable transport (such as [[User Datagram Protocol|UDP]]) the client retransmits requests at an interval that starts at T1 seconds (usually, {{val|500 |u=ms}}, which is the estimate of the [[round-trip time]]) and doubles after every retransmission until it reaches T2 seconds (which defaults to {{val|4|u=s}}). This results in retransmission intervals of {{val|500 |u=ms}}, {{val|1|u=s}}, {{val|2|u=s}}, {{val|4|u=s}}, {{val|4|u=s}}, {{val|4|u=s}}, etc.<ref name="sip">Rosenberg et al. [https://datatracker.ietf.org/doc/html/rfc3261 RFC3261 – SIP: Session Initiation Protocol]. The Internet Society. 2002.</ref>

==Collision avoidance==
Exponential backoff algorithms can be used to avoid network collisions. In a [[point-to-multipoint]] or [[multiplexed]] network, multiple senders communicate over a single shared channel. If two senders attempt to transmit a message at the same time, or ''talk over'' each other, a collision occurs and the messages are damaged or lost. Each sender can then back off before attempting to [[retransmission (data networks)|retransmit]] the same message again.

A [[Deterministic algorithm|deterministic]] exponential backoff algorithm is unsuitable for this use case since each sender would back off for the same time period, leading them to retransmit simultaneously and cause another collision. Instead, for purposes of collision avoidance, the time between retransmissions is [[Randomized algorithm|randomized]] and the exponential backoff algorithm sets the ''range'' of delay values that are possible. The time delay is usually measured in [[time-division multiplexing|slots]], which are fixed-length periods (or ''slices'') of time on the network. In a binary exponential backoff algorithm (i.e. one where {{math|1= ''b'' = 2}}), after {{mvar|c}} collisions, each retransmission is delayed by a random number of slot times between {{math|0}} and {{math|2<sup>''c''</sup> &minus; 1}}. After the first collision, each sender will wait 0 or 1 slot times. After the second collision, the senders will wait anywhere from 0 to 3 slot times ([[Interval (mathematics)|inclusive]]).  After the third collision, the senders will wait anywhere from 0 to 7 slot times (inclusive), and so forth. As the number of retransmission attempts increases, the number of possibilities for delay [[increases exponentially]]. This decreases the probability of a collision but increases the average latency.

Exponential backoff is utilised during retransmission of [[data frame|frames]] in [[carrier-sense multiple access with collision avoidance]] (CSMA/CA) and [[carrier-sense multiple access with collision detection]] (CSMA/CD) networks, where this algorithm is part of the [[Media access control|channel access]] method used to send data on these networks. In [[Ethernet]] networks, the algorithm is commonly used to schedule retransmissions after collisions. The retransmission is delayed by an amount of [[time]] derived from the [[slot time]] (for example, the time it takes to send 512 bits; i.e., 512 [[Bit time|bit-times]]) and the number of attempts to retransmit.

===Example===
This example is from the [[Ethernet]] protocol,<ref>{{cite book| title=Computer Networks: A Systems Approach |url=https://book.systemsapproach.org/ |last1=Peterson |first1=Larry L. |last2=Davie |first2=Bruce S. |chapter=Chapter 2: Direct Links | chapter-url=https://book.systemsapproach.org/direct/ethernet.html#transmitter-algorithm |page=120 |publisher=Morgan Kaufmann Publishers |edition=Sixth |year=2022 |isbn=978-0-12-818200-0 }}</ref> where a sending host is able to know when a collision has occurred (that is, another host has tried to transmit), when it is sending a frame. If both hosts attempted to re-transmit as soon as a collision occurred, there would be yet another collision &mdash; and the pattern would continue forever. The hosts must choose a random value within an acceptable range to ensure that this situation doesn't happen. An exponential backoff algorithm is therefore used. The value 51.2 μs is used as an example here because it is the [[slot time]] for a {{val|10 |u=Mbit|up=s}} Ethernet line. However, {{val|51.2 |u=μs}} could be replaced by any positive value, in practice.

# When a collision first occurs, send a ''jamming signal'' to prevent further data from being sent.
# Resend a frame after either 0 seconds or {{val|51.2 |u=μs}}, chosen at random.
# If that fails, resend the frame after either {{val|0 |u=s}}, {{val|51.2 |u=μs}}, {{val|102.4 |u=μs}}, or {{val|153.6 |u=μs}}.
# If that still fails, resend the frame after {{mvar|k}} · {{val|51.2 |u=μs}}, where {{mvar|k}} is a random integer between 0 and {{math|2<sup>3</sup> &minus; 1}}.
# For further failures, after the ''c''th failed attempt, resend the frame after {{mvar|k}} · {{val|51.2 |u=μs}}, where {{mvar|k}} is a random integer between 0 and {{math|2<sup>''c''</sup> &minus; 1}}.

==History and theory==
In a seminal paper published in AFIPS 1970,<ref name="abramson1">{{Cite conference |last=Abramson |first=Norman |year=1970 |title=The ALOHA System - Another Alternative for Computer Communications |url=https://www.clear.rice.edu/comp551/papers/Abramson-Aloha.pdf |conference=Proc. 1970 Fall Joint Computer Conference |publisher=AFIPS Press}}</ref>  [[Norman Abramson]] presented the idea of multiple “users,” on different islands, sharing a single radio channel (i.e., a single frequency) to access the main computer at the University of Hawaii without any time synchronization. Packet collisions at the receiver of the main computer are treated by senders after a timeout as detected errors.  Each sender not receiving a positive acknowledgement from the main computer would retransmit its “lost” packet.  Abramson assumed that the sequence of packets transmitted into the shared channel is a Poisson process at rate {{mvar|G}}, which is the sum of the rate {{mvar|S}} of new packet arrivals to senders and the rate of retransmitted packets into the channel.  Assuming steady state, he showed that the channel throughput rate is <math>S =Ge^{-2G}</math> with a maximum value of  1/(2{{mvar|e}}) = 0.184 in theory.

[[Lawrence Roberts (scientist)|Larry Roberts]] considered a time-slotted ALOHA channel with each time slot long enough for a packet transmission time. (A satellite channel using the [[Time-division multiple access|TDMA]] protocol is time slotted.) Using the same Poisson process and steady state assumptions as Abramson, Larry Roberts showed that the maximum throughput rate is 1/{{mvar|e}} = 0.368 in theory.<ref name="roberts1">{{Cite journal |last=Roberts |first=Lawrence G.|date=April 1975 |title=ALOHA Packet System With and Without Slots and Capture |journal=Computer Communications Review |volume=5 |issue=2|pages=28–42|doi=10.1145/1024916.1024920 }}</ref> Roberts was the program manager of the [[ARPANET]] research project. Inspired by the slotted ALOHA idea, Roberts initiated a new ARPANET Satellite System (ASS) project to include satellite links in the ARPANET.

Simulation results by Abramson, his colleagues, and others showed that an ALOHA channel, slotted or not, is unstable and would sometimes go into [[network congestion|congestion collapse]].  How much time until congestion collapse depended on the arrival rate of new packets as well other unknown factors. In 1971, [[Lawrence Roberts (scientist)|Larry Roberts]] asked Professor [[Leonard Kleinrock]] and his Ph.D. student, [[Simon Lam]], at [[UCLA]] to join the Satellite System project of [[ARPANET]].  Simon Lam would work on the stability, performance evaluation, and adaptive control of slotted ALOHA for his Ph.D. dissertation research. The first paper he co-authored with Kleinrock was [[ARPANET]] Satellite System (ASS) Note 12 disseminated to the ASS group in August 1972.<ref>{{cite Tech Report|last=Kleinrock|first=Leonard|author2=Simon S. Lam |date=August 1972|title=Analytic Results for the ARPANET Satellite System Model Including the Effects of the Retransmission Delay Distribution |url=https://www.cs.utexas.edu/users/lam/Vita/Bpapers/ASS_note_12.pdf|institution=ARPA Network Information Center, [[Stanford Research Institute]], Menlo Park, California| number=ASS Note 12 (NIC 11294) }}</ref> In this paper, a slot chosen randomly over an interval of {{mvar|K}}  slots was used for retransmission. A new result from the model is that increasing {{mvar|K}} increases channel throughput which converges to 1/{{mvar|e}} as {{mvar|K}} increases to infinity.  This model retained the assumptions of Poisson arrivals and steady state and was not intended for understanding statistical behaviour and congestion collapse.

===Stability and adaptive backoff===

To understand stability, Lam created a discrete-time [[Markov chain]] model for analyzing the statistical behaviour of slotted ALOHA in chapter 5 of his dissertation.<ref name="Lam74">{{cite thesis|last=Lam |first=Simon S. |date=March 1974 |title= Packet Switching in a Multi-Access Broadcast Channel with Application to Satellite Communication in a Computer Network, Ph.D. dissertation, 306 pages |url= https://www.cs.utexas.edu/users/lam/Vita/UCLA/| institution= UCLA-ENG-7429 (ARPA), UCLA School of Engineering and Applied Science }}</ref> The model has three parameters: {{var|N}}, {{var|s}}, and {{var|p}}.  {{var|N}} is the total number of users. At any time, each user may be idle or blocked.  Each user has at most one packet to transmit in the next time slot. An idle user generates a new packet with probability {{var|s}} and transmits it in the next time slot immediately. A blocked user transmits its backlogged packet with probability {{var|p}}, where 1/{{var|p}} = ({{var|K}}+1)/2 to keep the average retransmission interval the same. The throughput-delay results of the two retransmission methods were compared by extensive simulations and found to be essentially the same.<ref>Fig. 5-1 on page 100, Chapter 5, in Lam’s dissertation</ref>

Lam’s model provides mathematically rigorous answers to the stability questions of slotted ALOHA, as well as an efficient algorithm for computing the throughput-delay performance for any stable system. There are 3 key results, shown below, from Lam’s Markov chain model in Chapter 5 of his dissertation (also published jointly with Professor Len Kleinrock, in IEEE Transactions on Communications.<ref name="KL75">{{cite journal |last1=Kleinrock |first1=Leonard |last2=Lam S.|first2=Simon |date=April 1975 |title=Packet-Switching in a Multi-Access Broadcast Channel: Performance Evaluation|journal=IEEE Transactions on Communications|url=https://www.cs.utexas.edu/users/lam/Vita/Jpapers/KleinrockLam75.pdf |volume=COM-23|number=4|pages=410–423|doi=10.1109/TCOM.1975.1092814 |accessdate=16 February 2023}}</ref>)
#  Slotted ALOHA with Poisson arrivals (i.e., infinite {{var|N}}) is inherently unstable, because a stationary probability distribution does not exist. (Reaching steady state was a key assumption used in the models of Abramson and Roberts.)
#  For slotted ALOHA with a finite {{var|N}} and a finite {{var|K}}, the Markov chain model can be used to determine whether the system is stable or unstable for a given input rate ({{var|N}}×{{var|s}}) and, if it is stable, compute its average packet delay and channel throughput rate. 
# Increasing {{var|K}} increases the maximum number of users that can be accommodated by a stable slotted ALOHA channel.<ref>Fig. 5-9 on page 114 in Chapter 5 of Lam's dissertation, or Fig. 10 on page 418 in the 1975 Kleinrock-Lam paper.</ref>
====Corollary====
For a finite ({{var|N}}{{times}}{{var|s}}), an unstable channel for the current {{var|K}} value can be made stable by increasing {{var|K}} to a sufficiently large value, to be referred to as its {{var|K}}({{var|N}},{{var|s}}).<ref>Fig 5-10 on page 116 in Chapter 5 of Lam’s dissertation, or Figure 11 on page 418 in the 1975 Kleinrock-Lam paper.</ref>

===Heuristic RCP for adaptive backoff===
Lam used [[Markov decision process|Markov decision theory]] and developed optimal control policies for slotted ALOHA but these policies require all blocked users to know the current state (number of blocked users) of the Markov chain.  In 1973, Lam decided that instead of using a complex protocol for users to estimate the system state, he would create a simple algorithm for each user to use its own local information, i.e., the number of collisions its backlogged packet has encountered. {{refn|See Algorithm 4 on pages 901-902 in the Lam-Kleinrock paper<ref name="LK75">{{cite journal |last1=Lam |first1=Simon S.|last2=Kleinrock |first2=Leonard |date=September 1975|title=Packet-Switching in a Multi-Access Broadcast Channel: Dynamic Control Procedures|journal=IEEE Transactions on Communications |url=https://www.cs.utexas.edu/users/lam/Vita/Jpapers/LamKleinrock75.pdf |volume=COM-23|number=9|pages=891–904|doi=10.1109/TCOM.1975.1092917 |accessdate=16 July 2023}}</ref> or subsection 6.7.2, on pages 209-210 in Chapter 6 of Lam’s dissertation.}} Applying the above Corollary, Lam invented the following class of adaptive backoff algorithms (named Heuristic RCP).

A Heuristic RCP algorithm consists of the following steps: (1) Let {{var|m}} denote the number of previous collisions incurred by a packet at a user as the feedback information in its control loop. For a new packet, {{var|K}}(0) is initialized to 1. (2) The packet’s retransmission interval {{var|K}}({{var|m}}) increases as {{var|m}} increases (until the channel becomes stable as implied by the above Corollary). For implementation, with {{var|K}}(0)=1, as m increases, {{var|K}}({{var|m}}) can be increased by multiplication (or by addition).

====Observation====
Binary Exponential Backoff (BEB) used in Ethernet several years later is a special case of Heuristic RCP with <math>K(m) = 2^m</math>.

BEB is very easy to implement. It is however not optimal for many applications because BEB uses 2 as the only multiplier which provides no flexibility for optimization. In particular, for a system with a large number of users, BEB increases {{var|K}}({{var|m}}) too slowly.  On the other hand, for a system with a small number of users, a fairly small {{var|K}} is sufficient for the system to be stable, and backoff would not be necessary.
 
To illustrate an example of a multiplicative RCP that uses several multipliers, see the bottom row in Table 6.3 on page 214 in Chapter 6 of Lam’s dissertation, or bottom row in Table III on page 902 in the Lam-Kleinrock paper. In this example:
# A new packet is transmitted immediately, {{var|m}}=0, {{var|K}}(0)=1
# For a packet with 1 previous collision, {{var|K}}(1) = {{var|K}}(0){{times}}10 = 10     (The multiplier jumps up directly to {{var|K}}{{sup|*}} = 10 which was found to be the optimum {{var|K}} value at steady state for this particular system (slotted ALOHA for a satellite channel).
# For a packet with 2 previous collisions, {{var|K}}(2) = {{var|K}}(1){{times}}10 = 100   (one more collision, {{var|K}} jumps up 10 times).
# {{var|K}}(3) = {{var|K}}(2) × 2 = 200      
# {{var|K}}({{var|m}})={{var|K}}({{var|m}}&minus;1) for {{var|m}}≥4
For this example, {{var|K}}=200 is sufficient for a stable slotted ALOHA system with {{var|N}} equal to about 400, which follows from result 3 above Corollary. There is no need to increase {{var|K}} any further.

==Truncated exponential backoff==
The 'truncated' variant of the algorithm introduces a limit on {{math|''c''}}. This simply means that after a certain number of increases, the exponentiation stops. Without a limit on {{math|''c''}}, the delay between transmissions may become undesirably long if a sender repeatedly observes adverse events, e.g. due to a degradation in network service. In a randomized system this may occur by chance, leading to unpredictable latency; longer delays due to unbounded increases in {{math|''c''}} are exponentially less probable, but they are effectively inevitable on a busy network due to the [[law of truly large numbers]]. Limiting {{math|''c''}} helps to reduce the possibility of unexpectedly long transmission latencies and improve recovery times after a transient outage.

For example, if the ceiling is set at {{math|1= ''i'' = 10}} in a truncated binary exponential backoff algorithm, (as it is in the [[IEEE 802.3]] CSMA/CD standard<ref name="IEEE_802_3">{{Cite web|title=IEEE Standard 802.3-2015|url=https://standards.ieee.org/ieee/802.3/6003/|publisher=IEEE|access-date=20 March 2022}} (purchase)</ref>), then the maximum delay is 1023 slot times, i.e. {{math|2<sup>10</sup> &minus; 1}}.

Selecting an appropriate backoff limit for a system involves striking a balance between collision probability and latency. By increasing the ceiling there is an exponential reduction in probability of collision on each transmission attempt. At the same time, increasing the limit also exponentially increases the range of possible latency times for a transmission, leading to less deterministic performance and an increase in the average latency. The optimal limit value for a system is specific to both the implementation and environment.<ref>{{harvnb|Tanenbaum|Wetherall|2010|chapter=4.3|page=285}}</ref>

==Expected backoff==
Given a [[Discrete uniform distribution|uniform distribution]] of backoff times, the [[expected value|expected]] backoff time is the mean of the possibilities. After ''c'' collisions in a binary exponential backoff algorithm, the delay is randomly chosen from {{math|[0, 1, ..., ''N'']}} slots, where {{math|1=''N'' = 2<sup>''c''</sup> − 1}}, and the expected backoff time (in slots) is
:<math>\operatorname{E}(c) = \frac{1}{N+1}\sum_{i=0}^{N} i = \frac{1}{N+1}\frac{N(N+1)}{2} = \frac{N}{2}.</math>

For example, the expected backoff time for the third ({{math|1=''c'' = 3}}) collision, one could first calculate the maximum backoff time, ''N'':
:<math>N = 2^c - 1</math>
:<math>N = 2^3 - 1 = 8 - 1</math>
:<math>N = 7 ,</math>
and then calculate the mean of the backoff time possibilities:
:<math>\operatorname{E}(c) = \frac{1}{N+1}\sum_{i=0}^{N} i = \frac{1}{N+1}\frac{N(N+1)}{2} = \frac{N}{2} = \frac{2^c-1}{2}</math>.
which is, for the example, {{math|1= ''E''(3) = 3.5}} slots.

==See also==
* [[Control theory]]
* [[Markov chain]]
* [[Markov decision process]]

==References==
{{Reflist}}

===Bibliography===
*{{cite book |title=Computer Networks |edition=5th |first1=Andrew |last1=Tanenbaum |first2=David |last2=Wetherall |isbn=978-0132126953 |date=2010 |publisher=Pearson}}

{{FS1037C}}

{{DEFAULTSORT:Exponential Backoff}}
[[Category:Ethernet]]
[[Category:Network scheduling algorithms]]
[[Category:Scheduling algorithms]]