2
$\begingroup$

Four stations are trying to transmit frames through a single channel (only one frame per channel). After each frame is sent, they contend for the channel using Binary Exponential Backoff.

After $i$ collisions, each station waits (backs off) for a random number of slots chosen uniformly between 0 and $2^i - 1$: For the first collision, each sender will wait 0 or 1 slot times. After the second collision, the senders will wait anywhere from 0 to 3 slot times (inclusive). After the third collision, the senders will wait uniformly from 0 to 7 slot times (inclusive), and so forth. As the number of retransmission attempts increases, the contention window grows exponentially.

What is the probability of a collision on the i'th attempt?

1 Answers 1

3

A collision occurs if multiple stations choose the same slot. Equivalently, no collision occurs if they all choose a different slot. Assume that the four stations chose independently from one another. Let each number be represented by the uniformly distributed random variables $X_i, i=1\dots 4$.

The question is how you define the $i$'th event. I assume the question is asking for $1-P(X_1 \neq X_2 \neq X_3 \neq X_4)$ (meaning all different numbers). Defining $N=2^i$, this probability is equal to $1-\frac{N (N-1) (N-2) (N-3)}{N^4}$ since there are $N(N-1)(N-2)(N-3)$ ways of choosing four different numbers uniformly from a range of $N$. As a sanity check, if there were only two stations in the first collision, they would have to wait either 0 or 1 slot each. A collision would occur if they both chose 0 or both chose 1. This happens with probability 0.5 (2 out of the 4 possibilities). Our equation gives $1-\frac{2 \cdot 1}{2^2} = 0.5$

Corrections welcome.

  • 0
    Can u tell from where did n^4 (denominator) come from? Forgot my maths!2011-04-21
  • 0
    The number of stations: four.2011-04-21
  • 0
    Yes, I mean what does n^4 stand for here?2011-04-21
  • 0
    I defined $N=2^i$ as the range of the uniform random variables. Am I missing the question?2011-04-21
  • 0
    I could understand your description but couldn't quite understand the fraction N(N-1)(N-2)(N-2)/N^4 mathematically.2011-04-21
  • 0
    That's the probability of choosing four different numbers from a range of $N$. There are $N (N-1) (N-2) (N-3)$ ways of choosing four different numbers, each with a probability $1/N^4$.2011-04-21
  • 0
    Ok, got it now.. Thank you!2011-04-21