Baackoff algorithm


#1

Assume that X and Y are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both X and Y attempt to transmit a frame, they wait to get the control of channel using binary exponential algorithm. The probability that both were successfully allowed to send the frame on fifth round of the algorithm (assuming every time both X and Y will collide in back-off race till 4th round) is ________.


#2

1st Round : Both A and B send and collision happens, so both decide to wait for backoff algorithm,i.e,

A can take values from (0,1) and B as well can take from (0,1) .

So, probability of collision in 1st Round is 1.

2nd Round : Both A and B transmit again by taking appropriate value .

Unfortunately, If A and B both take 0, then collision occurs and If A and B both take 1, then even collision occurs .

Hence, we summarize collision in table like :

00 - Yup !! There is a collision

01 - Nopes !! Either one wins the backoff race

10 - Nopes !! Either one wins the backoff race

11 - Yup !! There is a collision

Hence, probabilty of collision = 2 / 4 = 1 / 2 = Probabilty of no collision

PS : It is written that both collide in backoff race till 4th round, hence, A and B both might have taken either 00 or 11.

3rd Round : As it is clear from the question that both collide till 4th round. So, they must have collided in 2nd round.

Values now available for A and B to take are (0,1,2,3)

Hence, when the collision occurs :

00 - Yup !! There is a collision

11 - same

22 - same

33 - same

Probability of collision = 4 / 16 = 1/ 4 = 1/ 22

and Probability of no collision = 1 - 1/4 = 12/16

4th Round : Why are we coming to 4th round ? Because according to the question, A and B have collided in 3rd round which is possible only when Both of them took the value 00 or 11,22,33 and collide.

Now, they again want to transmit. This time they can take values from : (0,1,2,3,4,5,6,7)

Now, what is the probability of collision in this round = 8 / 64 = 1 / 8 = 1 / 23

and probability of no collision in this round = 7 / 8

5th Round : Why are we coming to 5th round ? Because collision occured till 4th round.

Question wants A and B both to send successfully in this round by either one winning a race ( Whosoever wins That does not matter here)

Hence, both A and B take now values from (0,1,2…15).

probability of collision in this round = 16 / 256 = 1 / 16 = 1 / 24

and probability of no collision in this round = 15 /16

Total probabilty that both are successful to transmit on 5th round =>

=> 1 * 1/2 * 1/4 * 1/8 * (1 - 1/16)

=> 0.0145


#3

thanks bro…