Pure and slotted ALOHA: vulnerable time, throughput, maximum efficiency

1. TDMA with N stations: rate per station?
   Stuck? Peek at 2.3.1 The multiple access problem; collisions; channel partitioning

   • Collision: overlapping transmissions on a shared link; all involved frames lost.
   • MAC families: partitioning (TDMA/FDMA), random access (send freely, recover from collisions), taking turns (an orderly schedule).
   • TDMA/FDMA: R/N per station, no collisions, idle shares wasted, wait up to (N − 1) slots.

   Read lesson 2.3.1

2. d_min = 4: errors corrected?
   Stuck? Peek at 2.2.2 Hamming distance: detect d − 1, correct ⌊(d − 1)/2⌋

   • d(x, y) = number of 1s in x ⊕ y; d_min = smallest over codeword pairs.
   • Detect d_min − 1; correct ⌊(d_min − 1)/2⌋.
   • Detect s needs d ≥ s + 1; correct t needs d ≥ 2t + 1.
   • Hamming code: smallest r with 2ʳ ≥ m + r + 1.

   Read lesson 2.2.2

3. (1 − 1/n)ⁿ for large n, and 1/(2e)?
   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

The first wireless computer network linked islands in Hawaii in 1971. Its rule was almost no rule: send whenever you have a frame; if no confirmation comes back, wait a random time and send again. It was called ALOHA, and its numbers — 18.4 % and 36.8 % — are among the most asked facts in GATE networking.

Every frame takes time T to send. A frame starting at time 0 is safe only if no other frame overlaps it. During how long a window must nobody else start?

2T, from −T to +T. A frame that started up to T before ours is still on the channel when we start; one that starts before ours ends also overlaps. This 2T is the vulnerable time of pure ALOHA.

Pure ALOHA

Send a frame as soon as it is ready. If it collides, wait a random time and resend. Let T be the frame time (one frame's T_t).

Throughput S = G·e⁻²ᴳ

Let G = offered load = average number of frames (new + retransmitted) attempted per frame time T. Assuming attempts arrive at random (Poisson), the probability that no other attempt falls in a window of length 2T is e⁻²ᴳ. Throughput (successful frames per frame time):

Slotted ALOHA

Time is divided into slots of length T; a station may start only at a slot boundary. Two frames now collide only if they choose the same slot, so the vulnerable time halves to T.

With a finite number N of stations each sending in a slot with probability p, a slot succeeds with probability N·p·(1 − p)ᴺ⁻¹ (Lesson 0.2.4), maximised at p = 1/N and tending to 1/e.

Putting it together

• ALOHA sends blindly and retries after collisions.
• Pure: S = G·e⁻²ᴳ (max 18.4 %); slotted: S = G·e⁻ᴳ (max 36.8 %).
• Slots halve the vulnerable time from 2T to T.

• Pure ALOHA's vulnerable time is 2T, slotted's is T — not the other way round.
• G counts all attempts (including retransmissions) per frame time, not per second.
• Throughput in frames/s = S ÷ T = attempts/s × e⁻²ᴳ. Some books print "500 frames/s × 0.184 = 92" — that multiplies the attempt rate by S and mixes units; the correct value there is 0.184 / 1 ms = 184 frames/s.

"Slots halve the danger and double the best": 2T → T, 18.4 % → 36.8 %.

ALOHA transmits blind. Next (2.3.3): what if a station first listens and stays quiet while someone else is talking — and stops as soon as it hears a clash?

1. NAT

   Maximum throughput of slotted ALOHA (3 decimals)?

   Write your answer before opening the key.

2. NAT

   Frame time 2 ms; the stations attempt 250 frames/s. Pure ALOHA throughput in frames/s (nearest whole)?

   Write your answer before opening the key.

3. MCQ

   The vulnerable time of pure ALOHA with frame time T is:

   1. T/2
   2. T
   3. 2T
   4. 4T
4. NAT

   5 stations each send in a slot with probability 0.1. Probability a slot carries exactly one frame (4 decimals)?

   Write your answer before opening the key.

5. MSQ

   Which are true?

   1. Slotted ALOHA peaks at G = 1.
   2. Pure ALOHA peaks at G = 0.5.
   3. Raising G always raises throughput.
   4. Slotted ALOHA needs synchronised slot boundaries.

• 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)ᴺ⁻¹.

• pure ALOHA
• slotted ALOHA
• frame time T
• offered load G
• throughput S
• vulnerable time 2T / T
• max efficiency 18.4 % / 36.8 %

1. Pure ALOHA S and max?
   Reveal answer

   G·e⁻²ᴳ; 0.184 at G = 0.5.
2. Slotted ALOHA S and max?
   Reveal answer

   G·e⁻ᴳ; 0.368 at G = 1.
3. Vulnerable time pure vs slotted?
   Reveal answer

   2T vs T.

• G = (attempts per second) × T; frames/s delivered = S / T = (attempts/s) × e⁻²ᴳ (pure) or × e⁻ᴳ (slotted). — Poisson-style random attempts, frame time T.
• Max values: pure 0.184 at G = 0.5; slotted 0.368 at G = 1. — infinite-population ALOHA model.