GATE CSE 2004 | Question: 54

Question

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

• A. $0.5$
• B. $0.625$
• C. $0.75$
• D. $1.0$

Comments

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

---

https://gateoverflow.in/30257/csma-cd

---

Prerequisite knowledge

https://www.geeksforgeeks.org/back-off-algorithm-csmacd/

---

here who win first the probability of first wining station increases..

and collision probability is decreases exponentially...

thst's why it is also called Binary exponential backoff algorithm.(Binary because only applicable for 2 station only)

Answer 1

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$

Comments

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

Answer 2

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)

Answer 3

My solution is hit and lit