Truncated binary exponential backoff: Difference between revisions

Revision as of 01:48, 22 September 2010

Latest revision as of 09:09, 29 April 2018

(8 intermediate revisions by one other user not shown)

Line 1:

{{Merge|#REDIRECT [[Exponential backoff|date=November#Binary 2009}}exponential backoff / truncated exponential backoff]]

{{R to section}}

In a variety of [[computer networks]], '''binary exponential backoff''' or '''truncated binary exponential backoff''' refers to an [[algorithm]] used to space out repeated [[retransmission (data networks)|retransmissions]] of the same block of [[data]].

Examples are the retransmission of [[data frame|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 <math>2^c-1</math> 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 ([[Interval (mathematics)|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 [[exponential growth|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<ref name="IEEE_802_3">{{cite web|title=IEEE Standard 802.3-2008|url=http://standards.ieee.org/getieee802/download/802.3-2008_section1.pdf|publisher=IEEE|accessdate=22 September 2010}}</ref>), then the maximum delay is 1023 slot times.

Given a [[uniform distribution (discrete)|uniform distribution]] of backoff times, the [[expected value|expected]] backoff time is the mean of the possibilities. That is, after ''n'' collisions, the number of backoff slots is in <math>[0, 1, ..., N]</math> where <math>N = 2^c-1</math> and the expected backoff time (in slots) is <math>\frac{1}{N+1}\sum_{i=0}^{N} i</math>.

For example, the expected backoff time for the 3rd (''c = 3'') collision, one could first calculate the maximum backoff time, ''N'':

:<math>N = 2^c - 1</math>

:<math>N = 2^3 - 1 = 8 - 1</math>

:<math>N = 7</math>

... and then calculate the mean of the backoff time possibilities:

:<math>\operatorname{E}(c) = \frac{1}{N+1}\sum_{i=0}^{N} i</math>

:<math>\operatorname{E}(3) = \frac{1}{7+1}\sum_{i=0}^{7} i = \frac{1}{8}(0 + 1 + 2 + 3 + 4 + 5 + 6 + 7) = \frac{28}{8}</math>

:<math>\operatorname{E}(3) = 3.5</math>

... 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 ''a''₀, ''a''₁, ''a''₂, ... ''a''_m is simply the mean of ''a''₀ and ''a''_m or (''a''₀ + ''a''_m) / 2.

When applied to the above problem of finding the expected backoff time, the formula becomes simply:

:<math>\operatorname{E}(c) = \frac{2^c - 1}{2}</math>

Because these delays cause other stations who 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.{{citeneeded}}

==See also==

*[[Exponential backoff]]

==References==

{{reflist}}

*{{FS1037C}}

[[Category:Networking algorithms]]

[[Category:Ethernet]]

{{comp-sci-stub}}

[[de:Binary Exponential Backoff]]

[[fr:Binary Exponential Backoff]]

[[it:Algoritmo di backoff esponenziale binario]]