edited by
3,782 views
13 votes
13 votes
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
edited by

2 Answers

Best answer
29 votes
29 votes

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/ 2

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 / 2

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 / 2

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

selected by
1 votes
1 votes

Lets take small example ...instead of fifth lets take at second round of collision..

so collision number for both X and Y is 2.

so X can choose from 0 to 3 values that is 22 and same as Y.

Now collision will occur when both the station will choose (0,0),(1,1),(2,2),(3,3) .

so probability of collision is =( 22 / 22 * 22) .

same way at fifth round of collision = ( 25 / 25 * 25

NO COLLISION =1-( 25 / 25 * 25 THIS SHOULD BE ANS..

Related questions

1 votes
1 votes
1 answer
2
Rajesh Raj asked Dec 15, 2016
922 views
For gigabit ethernet, the length of the cable, if length of the cable in standardethernet l (2000) to maintain same frame size is _______.
0 votes
0 votes
1 answer
3
thor asked Nov 28, 2016
436 views
Please explain question first :::For gigabit ethernet, the length of the cable, if length of the cable in standard ethernet l (2000) to maintain same frame size is ______...
0 votes
0 votes
1 answer
4