Director: Simon S. Lam (more publications)
Adaptive Backoff Algorithms for Multiple Access: A History
The use of random access to share a broadcast channel was first proposed by Norman Abramson for the ALOHA System (AFIPS Conf. Proceedings, 1970). He carried out his analysis under the assumption that both new and retransmitted packets arrive according to a Poisson process. This assumption abstracted away the need for a backoff algorithm.
The first backoff algorithm for multiple access was proposed and investigated in our 1973 paper in National Computer Conference for the slotted ALOHA protocol. We proposed to delay the retransmission of a collided packet by a random time, chosen uniformly over K slots (K > 1) where K is a parameter. We showed that the channel throughput increases with K and, only in the limit as K goes to infinity, does the channel throughput approach the 1/e value predicted by analysis based upon the Poisson process assumption.
In ARPANET Satellite System Note 48 (NIC 17655), I presented simulation results to show that slotted ALOHA using a fixed K for backoff was unstable. In simulations, the channel throughput quickly collapsed to zero even though the rate of new packet arrivals was 0.35 which is less than 1/e. These observations led to several research contributions I made in 1973. First I developed a Markov Chain model that characterizes ALOHA instability. The equations and graphs of this model were reproduced in many textbooks, such as Schwartz (Addison-Wesley 1987), Kleinrock Vol. 2 (Wiley 1977), Rom & Sidi (Springer-Verlag 1990), and Bertsekas & Gallager (Prentice-Hall 1992).
During 1973, I also proposed several adaptive backoff algorithms and investigated
their effectiveness, including one called Heuristic RCP. In Chapter 6 of my
page 210 (also my
in National Computer Conference, page 150), I wrote about Algorithm 4 (Heuristic RCP) as follows:
For a backlogged packet with m previous collisions, the uniform retransmission
randomization interval is taken to be Km where Km is a monotone nondecreasing function in
When the channel traffic increases, the probability of channel collision
As a result, the "effective" value of K increases. If Km
is a steep enough
function of m, we see that channel saturation will be prevented.
I evaluated Heuristic RCP using analyses and simulations for several functions and came to the conclusion that it is simple to implement and is capable of preventing channel saturation under temporary overload conditions. Heuristic RCP was also described in our 1975 Transactions on Communications paper.
The binary exponential backoff algorithm used in Ethernet is a special
case of Heuristic RCP with the function Km
chosen to be 2m .