Truncated binary exponential backoff: Difference between revisions

Revision as of 01:48, 22 September 2010

Revision as of 01:49, 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 ''n'' collisions, the number of backoff slots is in <math>[0, 1, ..., ''N'']</math> where <math>''N'' = 2^<super>''c-1''</mathsuper>-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 3rd (''c = 3'') collision, one could first calculate the maximum backoff time, ''N'':