Department of Computer Sciences

The University of Texas at Austin

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
1974 dissertation,
page 210 (also my
1975 paper
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 *K _{m}* where

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 *K _{m} *
chosen to be 2

**Selected publications**

- L. Kleinrock and Simon S. Lam, Packet-Switching
in a Slotted Satellite Channel, National Computer Conference, New York,
NY, June 1973; in
*AFIPS Conference Proceedings*, Vol. 42, 1973, pp. 703-710. - L. Kleinrock and Simon S. Lam, On
Stability of Packet Switching in a Random Multi-Access Broadcast Channel,
*Proceedings Subconf. on Computer Nets*, Seventh Hawaii International Conference on System Sciences, Honolulu, January 1974. - Simon S. Lam and L. Kleinrock, Dynamic
Control Schemes for a Packet Switched Multi-Access Broadcast Channel,
National Computer Conference, Anaheim, CA, May 1975,
*AFIPS Conference Proceedings*, Vol. 44, AFIPS Press, 1975. - Leonard Kleinrock and Simon S. Lam, Packet-Switching
in a Multi-Access Broadcast Channel: Performance Evaluation,
*IEEE Trans. on Commun.*, Vol. COM-23, April 1975. - Simon S. Lam and Leonard Kleinrock, Packet-Switching
in a Multi-Access Broadcast Channel: Dynamic Control Procedures,
*IEEE Trans. on Commun.*, Vol. COM-23, September 1975. - Simon S. Lam, A
Carrier Sense Multiple Access Protocol for Local Networks,
*Computer Networks*, Vol. 4, No. 1, January 1980. (This paper presents a closed-form delay formula for CSMA/CD, which was used by researchers during the 1980s for performance comparisons of different local area network schemes.) - Simon S. Lam,
Multiple
Access Protocols, chapter in
*Computer Communications, Vol. 1: Principles*, W. Chou (ed.), Prentice-Hall, 1982.