Other examples of adverse events include collisions of network traffic, an error response from a service, or an explicit request to reduce the rate (i.e. back off).
The value of c is incremented each time an adverse event is observed, leading to an exponential rise in delay and, therefore, an inversely proportionate rate.
The time period that must elapse before attempting to increase the rate again may, itself, be determined by an exponential backoff algorithm.
The mechanism by which rate reduction is practically achieved in a system may be more complex than a simple time delay.
Exponential backoff is commonly utilised as part of rate limiting mechanisms in computer systems such as web services, to help enforce fair distribution of access to resources and prevent network congestion.
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.
A 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 and the exponential backoff algorithm sets the range of delay values that are possible.
In a binary exponential backoff algorithm (i.e. one where b = 2), after c collisions, each retransmission is delayed by a random number of slot times between 0 and 2c − 1.
Using the same Poisson process and steady state assumptions as Abramson, Larry Roberts showed that the maximum throughput rate is 1/e = 0.368 in theory.
Simulation results by Abramson, his colleagues, and others showed that an ALOHA channel, slotted or not, is unstable and would sometimes go into congestion collapse.
In 1971, 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.
This model retained the assumptions of Poisson arrivals and steady state and was not intended for understanding statistical behaviour and congestion collapse.
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.
[8] 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.
[13] 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 m denote the number of previous collisions incurred by a packet at a user as the feedback information in its control loop.
Without a limit on 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.
Limiting 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 i = 10 in a truncated binary exponential backoff algorithm, (as it is in the IEEE 802.3 CSMA/CD standard[14]), then the maximum delay is 1023 slot times, i.e. 210 − 1.
Selecting an appropriate backoff limit for a system involves striking a balance between collision probability and latency.