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

The Gateway to Computer Science Excellence

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

+20 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$ 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,341 answers

198,451 comments

105,210 users