# GATE2004-54

7.8k views

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

edited
17

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

2

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
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...

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

=(1/4)*(6/16)
0

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 ?

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.
1
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

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

1
4.8k views
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)$
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}}$
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$
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}$