by **Alchemist** » Thu Nov 13, 2014 9:54 am

This question is based on Ethernet's exponential backoff algorithm.

After experiencing nth collision in a row for a frame, the adapter chooses a value for K at random from {0,1,2,....,2^m-1}

where m = min(n,10).

The adapter then waits K*512 bit times and then senses the channel whether it is busy or idle.

Note that if a frame is destroyed in the collision, then only it's collision counter increases.

So, backoff race is won by a frame for which this waiting time (K*512 bit times) is less.

After first collision,

n (for A) = 1

n (for B) = 1

both A and B chooses from a random number {0,1}, and given that A wins the race, i.e. A must have been chosen 0 and B have 1.

As A wins the race,

n (for A) = 0

n (for B) = 1

now.

After second collision,

n (for A) = 1

n (for B) = 2

Now, A chooses from a random number {0,1}, and B chooses from a random number {0,1,2,3}

Since waiting time for a frame is directly proportional to this random number (i.e. K*512 bit times), For A to win the race, value of K must be less than than that of K for B.

So, favorable cases :

0-1

0-2

0-3

1-2

1-3

Number of favorable cases = 5

and total number cases = 2*4 = 8

Probability of A to win = 5/8 = 0.625

_________________________________________

"Live Free or Die Hard"