Exponential backoff
Encyclopedia
Exponential backoff is an algorithm
that uses feedback
to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate.
used to space out repeated retransmissions
of the same block of data
, often as part of network congestion avoidance.
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 network. 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
and the number of attempts to retransmit.
After c collisions, a random number of slot times between 0 and 2c - 1 is chosen. For 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.
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. Because of this possibility, after 16 attempts at transmission, the process is aborted.
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 has been given here as an example. However, 51.2μs could be replaced by any positive value, in practice.
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:
... obtaining 3.5 as the expected number of back off slots after 3 collisions.
The above derivation is largely unnecessary when you realize that the mean of consecutive integers is equal to the mean of the largest and smallest numbers in the set. That is, the mean of a set A of consecutive integers a0, a1, a2, ... am is simply the mean of a0 and am or (a0 + am) / 2.
When applied to the above problem of finding the expected backoff time, the formula becomes simply:
... or otherwise interpreted as half of the maximum backoff time.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that uses feedback
Feedback
Feedback describes the situation when output from an event or phenomenon in the past will influence an occurrence or occurrences of the same Feedback describes the situation when output from (or information about the result of) an event or phenomenon in the past will influence an occurrence or...
to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate.
Binary exponential backoff / truncated exponential backoff
In a variety of computer networks, binary exponential backoff or truncated binary exponential backoff refers to an algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used to space out repeated retransmissions
Retransmission (data networks)
Retransmission, essentially identical with Automatic repeat request , is the resending of packets which have been either damaged or lost. It is a term that refers to one of the basic mechanisms used by protocols operating over a packet switched computer network to provide reliable communication...
of the same block of data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
, often as part of network congestion avoidance.
Examples are the retransmission of frames
Data frame
In computer networking and telecommunication, a frame is a digital data transmission unit or data packet that includes frame synchronization, i.e. a sequence of bits or symbols making it possible for the receiver to detect the beginning and end of the packet in the stream of symbols or bits...
in carrier sense multiple access with collision avoidance
Carrier sense multiple access with collision avoidance
Carrier sense multiple access with collision avoidance , in computer networking, is a wireless network multiple access method in which:*a carrier sensing scheme is used....
(CSMA/CA) and carrier sense multiple access with collision detection
Carrier sense multiple access with collision detection
Carrier sense multiple access with collision detection is a Media Access Control method in which:*a carrier sensing scheme is used....
(CSMA/CD) networks, where this algorithm is part of the channel access
Media Access Control
The media access control data communication protocol sub-layer, also known as the medium access control, is a sublayer of the data link layer specified in the seven-layer OSI model , and in the four-layer TCP/IP model...
method used to send data on these network. In Ethernet
Ethernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
networks, the algorithm is commonly used to schedule retransmissions after collisions. The retransmission is delayed by an amount of time
Time
Time is a part of the measuring system used to sequence events, to compare the durations of events and the intervals between them, and to quantify rates of change such as the motions of objects....
derived from the slot time
Slot time
Slot time is a concept in computer networking. It is twice the time it takes for an electronic pulse to travel the length ofthe maximum theoretical distance between two nodes...
and the number of attempts to retransmit.
After c collisions, a random number of slot times between 0 and 2c - 1 is chosen. For 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
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
). 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
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
.
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
IEEE 802.3
IEEE 802.3 is a working group and a collection of IEEE standards produced by the working group defining the physical layer and data link layer's media access control of wired Ethernet. This is generally a local area network technology with some wide area network applications...
CSMA/CD standard), then the maximum delay is 1023 slot times.
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. Because of this possibility, after 16 attempts at transmission, the process is aborted.
An example of an exponential backoff algorithm
This example is from the EthernetEthernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
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 has been given here as an example. 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 being sent.
- Resend a frame after either 0 seconds or 51.2μs, chosen at random.
- If that fails, resend the frame after either 0s, 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 number 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 number between 0 and 2c − 1.
Expected backoff
Given a uniform distribution of backoff times, the expectedExpected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
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:
... obtaining 3.5 as the expected number of back off slots after 3 collisions.
The above derivation is largely unnecessary when you realize that the mean of consecutive integers is equal to the mean of the largest and smallest numbers in the set. That is, the mean of a set A of consecutive integers a0, a1, a2, ... am is simply the mean of a0 and am or (a0 + am) / 2.
When applied to the above problem of finding the expected backoff time, the formula becomes simply:
... or otherwise interpreted as half of the maximum backoff time.