Truncated binary exponential backoff: Difference between revisions

Revision as of 01:50, 22 September 2010

Revision as of 01:51, 22 September 2010

Line 9:

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 ''nc'' collisions, the number of backoff slots is in [0, 1, ..., ''N''] where ''N'' = 2^''c'' - 1 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 third (''c'' = 3) collision, one could first calculate the maximum backoff time, ''N'':