Binary exponential backoff; probability of winning

1. Minimum frame size for CSMA/CD?
   Stuck? Peek at 2.3.3 CSMA and its persistence variants; CSMA/CD; minimum frame size = 2·Tp·B

   • CSMA: sense before sending; collisions still possible within T_p.
   • 1-persistent / non-persistent / p-persistent: what to do when busy.
   • CSMA/CD: listen while sending; on collision jam, stop, back off.
   • L_min = 2·T_p·B; d_max = L_min·v/(2B); i.e. T_t ≥ 2T_p.
   • CSMA/CA (Foundation): wireless avoids collisions instead of detecting them.

   Read lesson 2.3.3

2. Slotted ALOHA maximum throughput?
   Stuck? Peek at 2.3.2 Pure and slotted ALOHA: vulnerable time, throughput, maximum efficiency

   • T = frame time; G = attempts per T.
   • Pure: vulnerable 2T, S = G·e⁻²ᴳ, max 1/(2e) ≈ 0.184 at G = 0.5.
   • Slotted: vulnerable T, S = G·e⁻ᴳ, max 1/e ≈ 0.368 at G = 1.
   • Finite N: P(success) = N·p·(1 − p)ᴺ⁻¹.

   Read lesson 2.3.2

3. Expected tries until success with probability p each?
   Stuck? Peek at 0.2.4 Exponents, logarithms and basic probability

   • 2ᵃ·2ᵇ = 2ᵃ⁺ᵇ; 2¹⁰ ≈ 10³ (estimates only).
   • log₂ x = power of 2 giving x; bits for N values = ⌈log₂ N⌉.
   • P(none) = (1−p)ⁿ · P(≥ 1) = 1 − (1−p)ⁿ · P(exactly 1) = n·p·(1−p)ⁿ⁻¹.
   • (1 − 1/n)ⁿ → 1/e ≈ 0.368; 1/(2e) ≈ 0.184.
   • 1 + 2 + … + 2ᵏ⁻¹ = 2ᵏ − 1; expected tries = 1/p.

   Read lesson 0.2.4

Two people bump into each other in a doorway. If both step back and step forward again at the same moment, they bump again. The fix: each picks a random pause — and if they keep bumping, they pick from longer and longer pauses. That is binary exponential backoff, the retry rule of CSMA/CD.

After their first collision, A and B each choose a wait of 0 or 1 slot at random. What is the probability they collide again?

1/2: both choose 0 or both choose 1. A wins (picks a smaller wait) with probability 1/4, B wins with 1/4.

The rule

Slot time = 512 bit times in classic 10 Mbps shared LANs (51.2 µs), the same as the minimum frame time from Lesson 2.3.3.

Why exponential?

Each collision hints that many stations are competing. Doubling the range spreads their retries out quickly, so the chance of another clash drops — at the cost of longer waits under heavy load.

Probability of winning

"Winning" = choosing a strictly smaller K than every rival. For two stations with ranges of size a and b, count the (K_A, K_B) pairs with K_A < K_B and divide by a·b.

A classic twist (the capture effect): if A won the previous round and now collides with B again, A's counter restarts at its first collision (range 2) while B is at its second (range 4) — so A is more likely to win again.

Putting it together

• Each collision doubles the random backoff range (cap 1024, give up at 16).
• Winning means drawing a strictly smaller K; count the pairs.
• Recent winners restart small, so they tend to win again (capture).

• After the n-th collision the range is {0, …, 2ⁿ − 1} — it includes 0 and has 2ⁿ values.
• The range stops growing after 10 collisions but attempts continue until 16.
• A station that just succeeded restarts its own counter; its rival keeps its larger range (capture effect).

"Bump once: pick from 2. Bump again: pick from 4." Double the doorway dance each time.

Random access works well under light load but wastes slots in collisions under heavy load. Next (2.3.5): the third family — stations take turns in an orderly way, so collisions never happen.

1. NAT

   After the 4th collision, from how many values is K chosen?

   Write your answer before opening the key.

2. NAT

   Two stations both at their 2nd collision. Probability they collide again (3 decimals)?

   Write your answer before opening the key.

3. NAT

   Both stations at their 2nd collision. Probability that A wins (3 decimals)?

   Write your answer before opening the key.

4. MCQ

   After the 13th collision a station chooses K from:

   1. {0, …, 8191}
   2. {0, …, 1023}
   3. {0, …, 12}
   4. it gives up
5. MSQ

   Which are true of binary exponential backoff?

   1. The range doubles after each collision up to a cap.
   2. K is always at least 1.
   3. Under heavy load average waits grow.
   4. Slot time equals the minimum frame time.

• After the n-th collision: K uniform in {0, …, 2^min(n,10) − 1}; wait K × slot; abort after 16.
• Slot = 512 bit times (51.2 µs at 10 Mbps).
• P(A wins) = #{K_A < K_B} / (a·b); both at range 2: win 1/4, tie 1/2.
• Capture: A at range 2 vs B at range 4 → A wins 5/8.

• binary exponential backoff
• slot time (512 bit times)
• backoff range 0..2ⁿ − 1, cap at 10, abort at 16
• probability of winning
• capture effect

1. Range after the n-th collision?
   Reveal answer

   {0, …, 2^min(n,10) − 1}.
2. Both at the first collision: P(collide again)?
   Reveal answer

   1/2.
3. A at range 2, B at range 4: P(A wins)?
   Reveal answer

   5/8.

• Two stations, ranges a and b: P(A wins) = #{K_A < K_B} / (a·b); P(tie) = min(a,b)/(a·b). — uniform independent choices, ties = another collision.
• Range after n collisions = 2^min(n,10); give up after 16 attempts. — classic binary exponential backoff.