Truncated binary exponential backoff: Difference between revisions

Revision as of 00:45, 22 September 2010

Latest revision as of 09:09, 29 April 2018

(15 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 i collisions, a random number of slot times between 0 and <math>2^i-1</math> is chosen. For the first collision, each sender might wait 0 or 1 slot times. After the second collision, the senders might wait 0, 1, 2, or 3 slot times, and so forth. As the number of retransmission attempts increases, the number of possibilities for delay increases.

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, then the maximum delay is 1023 slot times.

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.

==See also==

*[[Exponential backoff]]

==References==

*{{FS1037C}}

[[Category:Networking algorithms]]

[[Category:Ethernet]]

{{comp-sci-stub}}

[[de:Binary Exponential Backoff]]

[[fr:Binary Exponential Backoff]]

[[it:Algoritmo di backoff esponenziale binario]]