Question

Let A and B be two stations attempting to transmit on an Ethernet. Each has a steady queue of frames ready to send; A’s frames will be numbered ?1, ?2 and so on, and B’s similarly. Let ? = 51.2 ???? be the exponential backoff base unit. Suppose A and B simultaneously attempt to send frame 1, collide, and happen to choose backoff times of 0 × ? and 1 × ?, respectively. As a result, Station A transmits ?1 while Station B waits. At the end of this transmission, B will attempt to retransmit ?1 while A will attempt to transmit ?2. These first attempts will collide, but now A backs off for either 0 × ? or 1 × ? (with equal probability), while B backs off for time equal to one of 0 × ?, 1 × ?, 2 × ? and 3× ? (with equal probability).

(a) Give the probability that A wins this second backoff race immediately after his first collision.

(b) Suppose A wins this second backoff race. A transmits ?2 and when it is finished, A and B collide again as A tries to transmit ?3 and B tries once more to transmit ?1. Give the probability that A

wins this third backoff race immediately after the first collision.

(c) What is the probability that A wins all the ? backoff races. (? is a given constant)

(d) Assume that there are 3 stations sharing the Ethernet. Will the chance for A to win all the backoff

races decrease or increase? Why?

Answer 1

(a) Give the probability that A wins this second back-off race immediately after his first collision.
Answer:------------
For the second back-off race,
A picks k_A(2) to be either 0 or 1 with equal probability,so 1/2 for each.
B picks k_B(2) from (0, 1, 2, 3) with probability 1/4 for each choice.
A wins the second backoff race if k_A(2) < k_B(2).
P[A wins] = P[k_A(2) < k_B(2)]
= P[k_A(2) = 0] × P[k_B(2) > 0] + P[k_A(2) = 1] × P[k_B(2) > 1]
= 1/2 × 3/4 + 1/2 × 2/4
= 3/8 + 2/8
= 5/8

(b) Suppose A wins this second back-off race. A transmits ?2 and when it is finished, A and B collide again as A tries to transmit ?3 and B tries once more to transmit ?1. Give the probability that A wins this third back-off race immediately after the first collision.
Answer:------------
In this case, again A picks k_A(3) to be either 0 or 1 with probability 1/2 each,
while B picks k_B(3) from (0, 1, 2, 3, 4, 5, 6, 7), each with probability 1/8:
P[A wins] = P[k_A(3) < k_B(3)]
= P[k_A(3) = 0] × P[k_B(3) > 0] + P[k_A(3) = 1] × P[k_B(3) > 1]
= 1/2 × 7/8 + 1/2 × 6/8
= 7/16 + 6/16
= 13/16