|Look up backoff in Wiktionary, the free dictionary.|
Binary exponential backoff algorithm
In a variety of computer networks, binary exponential backoff or truncated binary exponential backoff refers to an algorithm used to space out repeated retransmissions of the same block of data, often to avoid network congestion.
Examples are the retransmission of frames in carrier sense multiple access with collision avoidance (CSMA/CA) and carrier sense multiple access with collision detection (CSMA/CD) networks, where this algorithm is part of the channel access method used to send data on these networks. In Ethernet networks, the algorithm is commonly used to schedule retransmissions after collisions. The retransmission is delayed by an amount of time derived from the slot time (for example, the time it takes to send 512 bits; i.e., 512 bit-times) and the number of attempts to retransmit.
After c collisions, a random number of slot times between 0 and 2c − 1 is chosen. After the first collision, each sender will wait 0 or 1 slot times. After the second collision, the senders will wait anywhere from 0 to 3 slot times (inclusive). After the third collision, the senders will wait anywhere from 0 to 7 slot times (inclusive), and so forth. As the number of retransmission attempts increases, the number of possibilities for delay increases exponentially.
The 'truncated' simply means that after a certain number of increases, the exponentiation stops; i.e. the retransmission timeout reaches a ceiling, and thereafter does not increase any further. For example, if the ceiling is set at i = 10 (as it is in the IEEE 802.3 CSMA/CD standard), then the maximum delay is 1023 slot times. This is useful because these delays cause other stations that are sending to collide as well. There is a possibility that, on a busy network, hundreds of people may be caught in a single collision set.
When collision avoidance is not a goal, a simpler version of exponential backoff can be used to just avoid network congestion. In this version of the algorithm, retransmission is delayed by predetermined (non-random) time. For example, in SIP protocol over unreliable transport (such as UDP) the client retransmits requests at an interval that starts at T1 seconds (usually, 500 ms, which is the estimate of the round-trip time) and doubles after every retransmission until it reaches T2 seconds (which defaults to 4 s). This results in retransmission intervals of 500 ms, 1 s, 2 s, 4 s, 4 s, 4 s, etc.
Example 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 re-transmit 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 value '51.2 μs' is used as an example here because 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.
- When a collision first occurs, send a "Jamming signal" to prevent further data from being sent.
- Resend a frame after either 0 seconds or 51.2 μs, chosen at random.
- If that fails, resend the frame after either 0 s, 51.2 μs, 102.4 μs, or 153.6 μs.
- If that still doesn't work, resend the frame after k · 51.2 μs, where k is a random integer between 0 and 23 − 1.
- In general, after the cth failed attempt, resend the frame after k · 51.2 μs, where k is a random integer between 0 and 2c − 1.
Given a uniform distribution of backoff times, the expected backoff time is the mean of the possibilities. That is, after c collisions, the number of backoff slots is in [0, 1, ..., N], where N = 2c − 1 and the expected backoff time (in slots) is
For example, the expected backoff time for the third (c = 3) collision, one could first calculate the maximum backoff time, N:
and then calculate the mean of the backoff time possibilities:
which is, for the example, E(3) = 3.5 slots.