Exponential Backoff - An Example of An Exponential Backoff Algorithm

An Example of An Exponential Backoff Algorithm

This example is from the Ethernet protocol, 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 is used as an example here but it is the slot time for a 10 Mbit/s Ethernet line (see Slot time). However, 51.2μs could be replaced by any positive value, in practice.

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, 102.4μs, or 153.6μ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 23 − 1.
5. In general, after the cth failed attempt, resend the frame after k · 51.2μs, where k is a random number between 0 and 2c − 1.