Exponential Backoff - Expected Backoff

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 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:

... or otherwise interpreted as half of the maximum backoff time.