GATE Overflow Test Series | Computer Networks | Test 1 | Question: 12

Question

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

• A. $5/8$
• B. $1/16$
• C. $1/8$
• D. $3/16$

Answer 1

At first backoff race both have $0 \ldots 2^{1}-1$ backoffs:
 
        $$\begin{array}{|c|c|c|}
             \hline
             A = 0,1 & B = 0,1 & \text{Win}\\
             \\\hline
             0 & 0 & \text{None}\\
             0 & 1 & \text{A}\\
             1 & 0 & \text{B}\\
             1 & 1 & \text{None}\\
             \\\hline
        \end{array}$$

   It is given that $B$ wins here.
   
For second backoff race:
   
        $\begin{array}{|c|c|c|}
            \hline
             B = 0,1 & A = 0,1,2,3 & \text{Win}\\
             \\\hline
             0 & 0 & \text{None}\\
             0 & 1 & \text{B}\\
             0 & 2 & \text{B}\\
             0 & 3 & \text{B}\\
             1 & 0 & \text{A}\\
             1 & 1 & \text{None}\\
             1 & 2 & \text{B}\\
             1 & 3 & \text{B}\\
             \\\hline
        \end{array}$

 So, $A$ can win the second backoff race with $\text{P(A wins)} = 1/8$.    

 Now, we can see how things started initially where both had equal opportunity and how it shifted towards the first winner. This shows the potential of capture effect.