Editing Exponential backoff (section)

==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.