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

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

A picks k_A(2)to be either 0 or 1 with equal probability in second backoff race,1/2 for each.from(0,1,2,3)with probability 1/4 for each choice,B Picks K_b(2). IN second backoff race ,A WinS if k_B(2)>K_a(2)

P[A wins] =P[k_B(2)>K_A(2)]

=P[k_A(2)= 1]×P[kB(2)>1]+P[k_A(2) = 0]×P[k_B(2)>0]

=12×24+12×34=58

2)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.

With probability of 1/2 each ,A picks k_A(3) to be either 0 or 1.with probability of 1/8 EACH,B picks k_B(3) from(0,1,2,3,4,5,6,7):

P[A wins] =P[kB(3)>KA(3)]

=P[kA(3) =1]×P[kB(3)>1]+P[kA(3) = 0]×P[kB(3)>0]

=12×68+12×78=1316

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

We assume that B will retry 16 times (the typical value), after which it gives up.

Further more, when choosing k between 0 and 2ⁿ−1 in the exponential backoff, n is capped at 10.

The probability that A wins all 13 remaining backoff races is:

P[A wins remaining races] = ¹⁶∏_i=4P[A wins i|A wins i−1]

Let k_A(i) be the k value A picks for I th backoff race.

Given that A wins that race, (k_A(i)<k_B(i)), the probability of A winning backoff race #(i+ 1)is 1 if k_A(i) + 1< k_B(i).

Otherwise (in case k_A(i) + 1≥k_B(i)), A and B collide when A is done with theith frame,and the probability becomes P[k_A(i+ 1)< k_B(i+ 1)].

P[A wins i+ 1|A wins i] =P[k_A(i) + 1< k_B(i)]·1

+P[k_A(i) + 1≥k_B(i)]·P[k_A(i+ 1)< k_B(i+ 1)]

≥P[k_A(i) + 1< k_B(i)]·P[k_A(i+ 1)< k_B(i+ 1)]

+P[k_A(i) + 1≥k_B(i)]·P[k_A(i+ 1)< k_B(i+ 1)]

= (P[k_A(i) + 1< k_B(i)] +P[k_A(i) + 1≥k_B(i)])

×P[k_A(i+ 1)< k_B(i+ 1)]

=P[k_A(i+ 1)< k_B(i+ 1)]

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?

Sol: Suppose for two stations A and B.

We assume B will retry for 16 times ,after which it gives up.

But for Station A,Probability for A wins 16 races decreases to ≈ 0.82

From above Assumption

For Three stations A,B and C.

For Station A,chance to win all the backoff Races Decreases