Deprecated: Implicit conversion from float-string "1527769894.130" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1527769894.130" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1527769894.130" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1527769894.130" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1527769894.130" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1710498940.264" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1710498940.264" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1710498940.264" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1710498940.264" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1710498940.264" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1527506281.923" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1527506281.923" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1527506281.923" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1527506281.923" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1527506281.923" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1608352038.661" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1608352038.661" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1608352038.661" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1608352038.661" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1608352038.661" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1608394673.217" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1608394673.217" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1608394673.217" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1608394673.217" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1608394673.217" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1608400926.021" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1608400926.021" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1608400926.021" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1608400926.021" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1608400926.021" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1606554015.555" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1606554015.555" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1606554015.555" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1606554015.555" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1606554015.555" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1606725427.030" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1606725427.030" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1606725427.030" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1606725427.030" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1606725427.030" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594
Computer Networks: GATE CSE 2004 | Question: 54
edited by
16,725 views
38 votes
38 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$
edited by

3 Answers

Best answer
49 votes
49 votes

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

Answer(B)

Answer:

Related questions

9.5k
views
4 answers
31 votes
Kathleen asked Sep 18, 2014
9,525 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 t...
7.4k
views
6 answers
26 votes
Kathleen asked Sep 18, 2014
7,365 views
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 b...
8.9k
views
4 answers
35 votes
Kathleen asked Sep 18, 2014
8,881 views
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 $1...
19.0k
views
8 answers
55 votes
go_editor asked Apr 24, 2016
18,992 views
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 ...