Test by Bikram | Mock GATE | Test 3 | Question: 28

Question

Two $CSMA/CD$ stations are each trying to transmit large files of multiple frames. After each frame is sent, they contend for the channel using the binary exponential back-off algorithm.

The probability that the contention ends in round $3$ is _____  (up to 3 decimal points).

Comments

@Lucky and @Aakash

please see below answer, the difference is 1 ∗ (1/2) ∗ (1/2²) ∗ ...... ∗ (1/2^k−2) ∗ (1−1/2^k−1)

where you all use 1 ∗ (1/2) ∗ (1/2²) ∗ ...... ∗ (1/2^k) ∗ (1−1/2^k) 

Reference:

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

see page 97, https://www.cs.umd.edu/class/fall2012/cmsc417/Slides/Chapter_5_V6.01.pdf

this slide also support my used formula.

---

@Aakash das and @Lucky

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

---

@lucky and aakas

check these documents which support , my answer is correct and the formula i used also correct

P(one of station transmits data in kth round) =1∗(1/2)∗(1/2²)∗......∗(1/2^k−2)∗(1−1/2^k−1)

page 4 and 5 , qstn number 3 http://cesg.tamu.edu/~sshakkot/courses/ECEN424/Solution-3.pdf

qstn number 4, 5th page http://omikron.eit.lth.se/ETSN01/ETSN01/tutorials/Tutorial8.pdf

Answer 1

Collision always occurs in round 1.

So probability that successful transmission happens in round 1 = 0.

P_{(one of station transmits data in kth round)} = 1 ∗ (1/2) ∗ (1/2²) ∗ ...... ∗ (1/2^k−2) ∗ (1−1/2^k−1)

now, k= 3 so it becomes 1/ 2^3-2  * ( 1 - 1/ 2^3-1 ) 

= 1/ 2¹ * ( 1 - 1/ 4 ) 

= 0.5 * 0.75

= 0.375 

Comments

@harsh181996

see this answer, https://gateoverflow.in/30257/csma-cd , it is the general case of this particular problem.

---

Without using the formula:

A collision happens in round 1 with probability 1. In the next round too, collision happens, this time with a probability of 1/2. [This can be derived by writing all possible combinations and seeing which generates a collision.] Since now no more collisions are allowed, in the third round, we subtract the collision probability from 1 i.e 1-1/4.

Now, all of these are conditional probabilities, therefore the total probability can be given as 1*1/2*(1-1/4) which is 0.375.

---

@Gokulnath , I am not understanding why Round 1 Collision Probability is 1 ?

Why are we not considering case:

Round 1: A [0,1]                            B[0,1]                      Probability of collision = (1/2)

Round 2: A[0,1,2,3]                      B[0,1,2,3]                 Probability of collision = (1/4)

Round 3: A[0,1,2,3,4,5,6,7]          B[0,1,2,3,4,5,6,7]     Probability of collision = (1/8)

@Bikram Sir, I have gone through the links but it is not giving satisfactory idea !