Exponential backoff

Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. It is often used in network congestion avoidance to help determine the correct sending rate.

An example of an exponential backoff algorithm

This example is from the Ethernet protocol^[1], where a sending host is able to know when a collision has occurred (that is, another host has tried to transmit), when it is sending a frame. If both hosts attempted to retransmit as soon as a collision occurred, there would be yet another collision - and the pattern would continue forever. The hosts must choose a random value within an acceptable range to ensure that this situation doesn't happen. An exponential backoff algorithm is therefore used. The figure 51.2μs has been given here as an example. However, 51.2μs could be replaced by any positive value, in practise.

1. When a collision first occurs, send a `Jamming signal' to prevent further data being sent.
2. Resend a frame after either 0 seconds or 51.2μs, chosen at random.
3. If that fails, resend the frame after either 0s, 51.2μs or 102.4μs
4. If that still doesn't work, resend the frame after k * 51.2μs, where k is a random number between 0 and 2³ − 1
5. After the n^th failed attempt, resend the frame after k * 51.2μs, where k is a random number between 0 and 2ⁿ − 1

See also

• Control theory
• Truncated binary exponential backoff

 This computer science-related article is a stub. You can help Wikipedia by expanding it.