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

  1. $0.5$
  2. $0.625$
  3. $0.75$
  4. $1.0$
in Computer Networks
edited by

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

3 Answers

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$

edited by
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...
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.
Very Well explained Answer Thank You Arjun Sir
why can't we do like this :


The probability of A winning the collision in the 2nd pass given that it has already won it in the 1st 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 1st 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 ?

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
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.
Yes you are correct. I assumed probability of A winning in both rounds, for that it will 0.15625. Otherwise we have to check for all the possibilities and you are absolutely correct
1 vote

My solution is hit and lit

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 2nd 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$



Related questions

18 votes
4 answers
A point is randomly selected with uniform probability in the $X-Y$ plane within the rectangle with corners at $(0,0), (1,0), (1,2)$ and $(0,2).$ If $p$ is the length of the position vector of the point, the expected value of $p^{2}$ is $\left(\dfrac{2}{3}\right)$ $\quad 1$ $\left(\dfrac{4}{3}\right)$ $\left(\dfrac{5}{3}\right)$
asked Sep 19, 2014 in Probability Kathleen 4.8k views
17 votes
6 answers
Two $n$ bit binary strings, $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to $d$ is $\dfrac{^{n}C_{d}}{2^{n}}$ $\dfrac{^{n}C_{d}}{2^{d}}$ $\dfrac{d}{2^{n}}$ $\dfrac{1}{2^{d}}$
asked Sep 19, 2014 in Probability Kathleen 3.5k views
24 votes
3 answers
An examination paper has $150$ multiple choice questions of one mark each, with each question having four choices. Each incorrect answer fetches $-0.25$ marks. Suppose $1000$ students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is $0$ $2550$ $7525$ $9375$
asked Sep 19, 2014 in Probability Kathleen 4.2k views
45 votes
7 answers
Consider three IP networks $A, B$ and $C$. Host $H_A$ in network $A$ sends messages each containing $180$ $bytes$ of application data to a host $H_C$ in network $C$. The TCP layer prefixes $20$ byte header to the message. This passes through an intermediate network $B$. The maximum packet ... other overheads. $325.5$ $\text{Kbps}$ $354.5$ $\text{Kbps}$ $409.6$ $\text{Kbps}$ $512.0$ $\text{Kbps}$
asked Apr 24, 2016 in Computer Networks jothee 9.6k views