Editing Exponential backoff (section)

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