Expected Backoff
Given a uniform distribution of backoff times, the expected backoff time is the mean of the possibilities. That is, after c collisions, the number of backoff slots is in 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.
Read more about this topic: Exponential Backoff
Famous quotes containing the word expected:
“I believe that all women of working ages and physical capacity, regardless of income, should be expected to earn their livings either in or out of the home. Until this attitude prevails I believe the position of women will be uncertain and undignified, in spite of poetic rhapsodies to the contrary.”
—Mary Barnett Gilson (1877–?)