----->>>>i think it helps...

28 votes

$A$ and $B$ are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both $A$ and $B$ attempt to transmit a frame, collide, and $A$ wins the first backoff race. At the end of this successful transmission by $A$, both $A$ and $B$ attempt to transmit and collide. The probability that $A$ wins the second backoff race is:

- $0.5$
- $0.625$
- $0.75$
- $1.0$

35 votes

Best answer

Exponential back-off algorithm is in use here. Here, when a collision occurs:

- each sender sends a jam signal and waits (back-offs) $k \times 51.2 \mu s$, where $51.2$ is the fixed slot time and $k$ is chosen randomly from $0$ to $2^N-1$ where $N$ is the current transmission number and $1\leq N\le 10.$ For $11\leq N \leq 15, k$ is chosen randomly from $0$ to $1023.$ For $N=16,$ the sender gives up.

For this question $N=1$ for $A$ as this is $A's$ first re-transmission and $N = 2$ for $B$ as this is its second re-transmission. So, possible values of $k$ for $A$ are $\{0,1\}$ and that for $B$ are $\{0,1,2,3\},$ giving $8$ possible combinations of values. Here, $A$ wins the back-off if its $k$ value is lower than that of $B$ as this directly corresponds to the waiting time. This happens for the $k$ value pairs $\{(0,1), (0,2), (0,3), (1,2), (1,3)\}$ which is $5$ out of $8$. So, probability of $A$ winning the second back-off race is $\frac{5}{8} = 0.625.$

Correct Answer: $B$

0

K value should have one more pair i.e. (2,3)...if so the answer should be 5/16...because total 16 pairs can be possible out of which number of favourable pairs are 5...

Please clear my doubt...

Please clear my doubt...

0

Here, possible value of k for A is {0,1} .so we can't have the pair (2,3).

N is nothing but re-transmission serial number.

Since A is trying to retransmit for the first time => N=1 for A giving k values as 0 and 1.

B is trying to retransmit for the second time => N=2 for B giving k values as 0,1,2 and 3.

N is nothing but re-transmission serial number.

Since A is trying to retransmit for the first time => N=1 for A giving k values as 0 and 1.

B is trying to retransmit for the second time => N=2 for B giving k values as 0,1,2 and 3.

0

The probability of A winning the collision in the 2^{nd} pass given that it has already won it in the 1^{st} pass is $\frac{5}{8}= 0.625$ which is as calculated (and the options matched). This is the case when we are considering the conditional probability, under the condition that $A$ has already won in the 1^{st} pass. But how to understand whether or not the question is demanding conditional probability ?

If we do not consider the required probability to be conditional, then probability would be something like this,

$$\text{P( A wins in the 2nd pass)}$$

$$= \text{P( A wins in the 1st pass)} \times \text{P(A wins in the second pass | A wins in the 1st pass)}$$ $$= \frac{1}{4}*\frac{5}{8}= 0.15625$$

Though $0.15625$ is not given in option, but what if both $0.625$ and $0.15625$ are given in options ?

1

The question has already mentioned that A has won the first back-off race. So this event has already happened. If it had not mentioned that A has already won round 1, then 0.15625 would have been the answer

0

I do not think so, that if A is not stated to have won the 1st round, then the answer shall be 0.15625 if we do not consider condition probability. Because, in such a situation, A might have won the 1st round and then it is supposed to win 2nd round as well or it has failed the 1st round, but it is supposed to win the 2nd round.

This is what I feel, I might be wrong.

This is what I feel, I might be wrong.

0 votes

For access control Ethernet(802.3) uses CSMA/CD. In CSMS/CD collision is resolved by binary backoff algorithm which says if a collision occurs then the stations which involved in collision have to wait

$wait = k * Time$

here K is a number chosen from ($0 - 2^n-1$) n is collision number

as A has Successfully Transmit 1 packet and B has undergone first collision

when A and B collide again for B second collision happened as for A new packets ! collision occurred

A can wait between (0 or 1) before retransmission

B can wait between (0-3) before retransmission (as it is has 2^{nd} collision)

wait by A | wait by B | Winner(who can transmit |

0 | 0 | Collision |

0 | 1 | A |

0 | 2 | A |

0 | 3 | A |

1 | 0 | B |

1 | 1 | Collision |

1 | 2 | A |

1 | 3 | A |

among 8 possibilities A wins 5 times

$prob = 5/8=0.625$

Answer(B)