Data Communication · Lecture 13

Multiple Access

Many stations, one medium: ALOHA, CSMA/CD, CSMA/CA, controlled access and channelization

Md Mahbub E Noor · Assistant Professor, Department of CSE, University of Barishal

Course: Data Communication · 2nd Year, 2nd Semester

Sharing a medium: today's goals

Classify multiple-access protocols into three families
Compute ALOHA vulnerable time and throughput
Explain CSMA persistence, CSMA/CD and the minimum frame size
Explain CSMA/CA, RTS/CTS, NAV and the hidden-station problem
Describe reservation, polling, token passing, FDMA, TDMA and CDMA

Lecture 12 gave us

reliable delivery between two nodes on one link.

Today

rules for many stations sharing one link: who may send, and what happens when two send at once.

Reading: Forouzan (5th ed.), Chapter 12

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

2 / 37

Three families of multiple-access protocols

Random access

No station is in charge; anyone may send, collisions are possible

· ALOHA (pure, slotted)

· CSMA

· CSMA/CD (wired Ethernet)

· CSMA/CA (Wi-Fi)

Controlled access

Stations take turns; a station sends only when authorised

· Reservation

· Polling

· Token passing

Channelization

The channel is split in frequency, time or code

· FDMA

· TDMA

· CDMA

Why needed: on a broadcast link every station hears every frame. If two transmit at once, their signals add and both frames are destroyed: a collision. The MAC sublayer decides who may send.

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

3 / 37

Pure ALOHA: send whenever you like

The first random-access method (University of Hawaii, 1970, radio)
A station sends a frame as soon as it has one
Any overlap of two frames destroys both: a collision
The receiver ACKs good frames; no ACK within 2 × T_p → collision assumed
Wait a random backoff time, then resend

Stn A

Stn B

Stn C

Stn D

time (one box = one frame time T_fr)

success

collision

This run

9 frames sent

3 survive

No ACK in time?

time-out = 2 × T_p

back off, resend

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

4 / 37

Binary exponential backoff (Example 12.1)

After the K-th collision, pick a random integer R from 0 to 2^K − 1
Wait T_B = R × T_p (or R × T_fr), then try again
Each failure doubles the range: crowded channel → longer waits
Give up after K_max attempts (usually 15)
Used again in CSMA/CD and CSMA/CA

After attempt K	R chosen from	T_B = R × T_p (T_p = 2 ms)
1	0, 1	0 or 2 ms
2	0, 1, 2, 3	0, 2, 4 or 6 ms
3	0 … 7	0 … 14 ms
K	0 … 2^K − 1	up to (2^K − 1) × 2 ms

Ex. 12.1: T_p

600 km / (3 × 10⁸ m/s)

2 ms

K = 2

R ∈ {0, 1, 2, 3}

T_B = 0, 2, 4, 6 ms

The range doubles after every collision, so a repeat collision becomes less and less likely.

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

5 / 37

Try it: back off and try again

Interactive

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

6 / 37

Pure ALOHA: vulnerable time (Example 12.2)

Vulnerable time: the period in which another start causes a collision
A frame started up to T_fr before B's hits B's beginning
A frame started up to T_fr after B's start hits B's end
Pure ALOHA vulnerable time = 2 × T_fr
Ex. 12.2: 200-bit frames at 200 kbps → 2 ms window

B's frame

A ends late

C starts early

t − T_fr

t + T_fr

vulnerable 2 T_fr

Ex. 12.2: T_fr

200 bits / 200 kbps

1 ms

Vulnerable time

2 × 1 ms

2 ms

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

7 / 37

Slotted ALOHA: start only at slot boundaries

Divide time into slots of length T_fr
A station may start sending only at the beginning of a slot
Frames either collide completely or not at all
Vulnerable time is halved: T_fr
Price: stations must be synchronised; a frame may wait up to one slot

Stn A

Stn B

Stn C

Stn D

time (one box = one frame time T_fr) · grid = slots

success

collision

Same 9 frames, slotted

each start moved to the next slot

7 survive

Vulnerable time

only frames in the same slot collide

1 × T_fr

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

8 / 37

ALOHA throughput

G: frames generated (new + resent) per frame time
S: frames that succeed per frame time (fraction of capacity)
Pure: S = G e^−2G, best 18.4% at G = ½
Slotted: S = G e^−G, best 36.8% at G = 1
Too much load and S falls: collisions waste the channel

18.4% at G = 0.5

36.8% at G = 1

G →

10%

20%

30%

40%

S (throughput)

Pure: max 1/(2e)

S = G e^−2G

18.4%

Slotted: max 1/e

S = G e^−G

36.8%

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

9 / 37

Examples 12.3 and 12.4: how many frames survive?

200-bit frames on a shared 200 kbps channel → T_fr = 1 ms, so G = (frames per second) × 1 ms

Offered load	Pure ALOHA: S = G e^−2G	Slotted ALOHA: S = G e^−G
1,000 frames/s · G = 1	13.5% → 135 frames/s	36.8% → 368 frames/s
500 frames/s · G = ½	18.4% → 92	30.3% → 152 (book: 151)
250 frames/s · G = ¼	15.2% → 38	19.5% → 49

Textbook typo (Example 12.4): it writes 1000 × 0.0368 = 368 and 500 × 0.0303 = 151. The factors are 0.368 and 0.303 (500 × 0.3033 = 151.6 ≈ 152).

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

10 / 37

Try it: ALOHA throughput

Interactive

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

11 / 37

Checkpoint 1 · 3 minutes

Check your understanding

Q1

Pure ALOHA, 1 Mbps channel, 1,000-bit frames. What is the vulnerable time?

Q2

Slotted ALOHA on the same channel; all stations together send 500 frames per second. How many survive per second?

Q3

In one sentence: why does slotting double ALOHA's best throughput?

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

12 / 37

CSMA: listen before you talk

Carrier sense: check the medium first; send only if it is idle
Fewer collisions, but not zero: signals take time to travel
C senses an idle cable because B's first bits have not reached it yet
Vulnerable time = T_p, the end-to-end propagation time
Much shorter than ALOHA's 2 T_fr on a LAN

B starts (t₁)

C starts (t₂)

B's signal reaches C (too late)

where bands overlap: collision

time ↓

Vulnerable time

end-to-end propagation

T_p

2 km cable, 2 × 10⁸ m/s

2,000 / (2 × 10⁸)

T_p = 10 µs

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

13 / 37

Persistence: what to do when the channel is busy

1-persistent: wait for idle, then send immediately (traditional Ethernet)
Non-persistent: if busy, go away for a random time
p-persistent: when idle, send with probability p; otherwise wait a slot
Slot ≥ maximum propagation time
Small p: fewer collisions, more waiting

Method	Channel idle	Channel busy	Trade-off
1-persistent	send at once	keep sensing; send the moment it is idle	many collisions (all waiters jump in)
Non-persistent	send at once	wait a random time, sense again	fewer collisions, idle gaps
p-persistent	send with probability p; else wait a slot	keep sensing until idle	balance; needs time slots

p = 0.2: send in 1st slot

probability p

20%

Still waiting after 3 slots

(1 − p)³ = 0.8³

51.2%

Average wait

1 / p

5 slots

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

14 / 37

Try it: 1-, non- and p-persistent

Interactive

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

15 / 37

CSMA/CD: collision detection

Keep listening while sending; compare what you hear with what you send
Collision detected → stop at once and send a short jam signal
Then binary exponential backoff and try again
No ACK needed for collisions: silence while sending means success
Used by classic (shared, half-duplex) Ethernet

A starts t₁

C starts t₂

C detects t₃

A detects t₄

collision

time ↓

sense (persistence)

send + listen

collision? jam

backoff, retry

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

16 / 37

Minimum frame size (Example 12.5)

A station must still be sending when news of a collision arrives
Worst case: the other end starts just before our first bit arrives
The collision news needs another T_p to come back: 2 T_p in total
So T_fr ≥ 2 T_p: short frames must be padded
10× the rate → 10× shorter cable for the same frame size

T_fr ≥ 2 × T_p

L_min = R × 2T_p

Ex. 12.5: 2 T_p

2 × 25.6 µs

51.2 µs

Minimum frame

10 Mbps × 51.2 µs

512 bits = 64 B

Rate, 64-byte frame	T_fr	Max T_p	Max cable (2 × 10⁸ m/s)
10 Mbps	51.2 µs	25.6 µs	5.12 km*
100 Mbps	5.12 µs	2.56 µs	512 m
1 Gbps	0.512 µs	0.256 µs	51.2 m

* T_p in Ex. 12.5 includes repeater and device delays, so real 10 Mbps networks were limited to 2.5 km.

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

17 / 37

Try it: catch the collision in time

Interactive

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

18 / 37

Checkpoint 2 · 3 minutes

Check your understanding

Q1

CSMA/CD at 100 Mbps; maximum propagation time (with device delays) is 10 µs. What is the minimum frame size?

Q2

Ethernet slot time is 51.2 µs. After the 3rd collision, what range does R come from, and what is the longest wait?

Q3

Why can't a Wi-Fi station simply use CSMA/CD?

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

19 / 37

CSMA/CA: collision avoidance for wireless

A radio cannot listen while it sends: no collision detection
So avoid collisions before they happen
Sense idle → wait an IFS → wait a random slot count → send
A paused backoff timer gives priority to the station that has waited longest
Every frame is acknowledged; no ACK → assume a collision, back off

busy

IFS

contention window: R slots

send

Tool	How it avoids collisions
IFS (interframe space)	wait a little even when idle: a distant station's signal may still be on its way; a shorter IFS = higher priority
Contention window	wait a random number of slots (binary exponential); the timer pauses while the channel is busy
ACK + timer	no collision detection, so the receiver must confirm every frame

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

20 / 37

The 802.11 handshake: RTS, CTS and NAV

A waits DIFS, then sends a short RTS (request to send) with the duration it needs
B waits SIFS, answers CTS (clear to send)
A sends the data; B sends the ACK
Every other station that hears RTS or CTS sets its NAV timer and stays quiet
If RTS frames collide, no CTS comes: back off and retry

RTS

CTS

Data

ACK

DIFS

SIFS

A (source)

B (destination)

C (other)

NAV

hears CTS

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

21 / 37

The hidden-station problem

Radio range is limited: A reaches B, C reaches B, but A and C cannot hear each other
A senses idle and sends to B; C also senses idle and sends to B
Collision at B: neither sender can hear it
Fix: B's CTS is heard by everyone in B's range, including C
C sets its NAV and waits until A's transfer ends

A's range

C's range

B hears both

Problem	What happens	RTS/CTS helps?
Hidden station	A and C both send to B; neither hears the other; collision at B	yes: C hears B's CTS
Exposed station	C hears B talking to someone else and keeps quiet though it could send	only partly

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

22 / 37

Try it: hidden stations and RTS/CTS

Interactive

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

23 / 37

Controlled access: take turns

Stations agree who may send: no collisions
Reservation: N minislots per interval, one per station; set yours to book a turn
Polling: a primary station controls the link (poll and select)
Token passing: only the station holding the token sends
Cost: coordination overhead and, for polling, one point of failure

Reservation (Fig. 12.18 idea)

Data 1

Data 3

Data 4

Data 1

Interval 1: minislots 1, 3, 4 set → those stations send · interval 2: only station 1 · then nobody

Polling

A primary asks each secondary in turn: poll (have you data?) or select (are you ready to receive?)

Token passing

A special frame, the token, circulates on a logical ring; only its holder may send

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

24 / 37

Token passing

Stations form a logical ring: each has a predecessor and a successor
Hold the token → send (for a limited time) → pass it on
No token, no sending: no collisions
Token management: limit holding time, detect a lost token, set priorities
The ring may be logical: bus, star or (dual) physical ring

token

Physical layout	Note
Ring	one broken link stops all
Dual ring	spare ring (FDDI)
Bus ring	token bus: next address in token
Star ring	hub bypasses failures (IBM Token Ring)

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

25 / 37

Channelization: FDMA and TDMA

FDMA: each station gets its own frequency band (with guard bands)
TDMA: each station gets its own time slot in a shared band
TDMA needs synchronisation: preamble bits and guard times
Unlike FDM/TDM (Lecture 9) there is no central multiplexer
Each station shapes its own signal; they mix on the common channel

FDMA

time →

own band all the time; guard bands between

TDMA

time →

whole band, own time slot; guard times

Example: GSM uses both

124 carriers × 8 time slots

992 channels

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

26 / 37

CDMA: everyone at once, different codes

All stations send at the same time over the whole band
Each station has a code: a sequence of N chips (+1 / −1)
Codes are orthogonal: inner product 0 with any other code
The receiver multiplies the channel by the sender's code and divides by N
Everyone else's data cancels out

Rule	Example (N = 4)
Bit 1 → +1, bit 0 → −1, silent → 0	data d_i ∈ {+1, −1, 0}
Send d_i × c_i (each chip × data)	−1 × [+1 −1 +1 −1] = [−1 +1 −1 +1]
Channel = sum of all stations	add chip by chip
Same code: c · c = N	[+1 +1 −1 −1] · [+1 +1 −1 −1] = 4
Different codes: c_i · c_j = 0	[+1 +1 −1 −1] · [+1 +1 +1 +1] = 0
Decode: (channel · c_i) / N	gives d_i: +1, −1 or 0

Analogy: in one room, pairs talk in different languages; each listener filters out everything not in its own language.

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

27 / 37

CDMA worked example (Forouzan Fig. 12.26)

Stations 1 and 2 send 0, station 4 sends 1, station 3 is silent
Each multiplies its data (−1, −1, 0, +1) by its code
Channel = chip-by-chip sum = [−1 −1 −3 +1]
Station 3 decodes station 2: inner product −4, ÷ 4 = −1 → bit 0
Only the sum travels; each code pulls out its own station

Stn	Data	Code c	d × c
1	bit 0 → −1	[+1 +1 +1 +1]	[−1 −1 −1 −1]
2	bit 0 → −1	[+1 −1 +1 −1]	[−1 +1 −1 +1]
3	silent → 0	[+1 +1 −1 −1]	[0 0 0 0]
4	bit 1 → +1	[+1 −1 −1 +1]	[+1 −1 −1 +1]
	channel		[−1 −1 −3 +1]

Station 3 listens to station 2

[−1 −1 −3 +1] · [+1 −1 +1 −1] = −1 +1 −3 −1

-4 / 4 = −1 → bit 0

Textbook typos: Fig. 12.26 labels C₂ as [+1 +1 +1 −1] and d₂·c₂ as [−1 −1 −1 +1]; correct: [+1 −1 +1 −1] and [−1 +1 −1 +1]. The text then says “→ bit 1”: −1 means bit 0.

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

28 / 37

CDMA practice: decode every station

Stations 1 and 2 send 1, station 3 sends 0, station 4 is silent
Channel = [+1 −1 +3 +1]
Inner product with each code, then divide by 4
Results: +1, +1, −1, 0 → bits 1, 1, 0 and silence
Try your own data in the lab (tab 4)

Stn	Data	Code c	d × c
1	bit 1 → +1	[+1 +1 +1 +1]	[+1 +1 +1 +1]
2	bit 1 → +1	[+1 −1 +1 −1]	[+1 −1 +1 −1]
3	bit 0 → −1	[+1 +1 −1 −1]	[−1 −1 +1 +1]
4	silent → 0	[+1 −1 −1 +1]	[0 0 0 0]
	channel		[+1 −1 +3 +1]

Stn	channel · code	Sum	÷ 4	Result
1	+1×+1 −1×+1 +3×+1 +1×+1	+4	+1	bit 1
2	+1×+1 −1×−1 +3×+1 +1×−1	+4	+1	bit 1
3	+1×+1 −1×+1 +3×−1 +1×−1	−4	−1	bit 0
4	+1×+1 −1×−1 +3×−1 +1×+1	0	0	silent

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

29 / 37

Making orthogonal codes: Walsh tables

Start with W₁ = [+1]
Build W_2N from four copies of W_N, the last one complemented
Each row is one station's code
N must be a power of 2: round the number of stations up
Any two different rows are orthogonal

W₁

W₂

−1

W₄

−1

W_2N = [ W_N W_N ; W_N −W_N ]

copy, copy, copy, complement

Ex. 12.6: two stations

[+1 +1] and [+1 −1]

rows of W₂

Ex. 12.7: 90 stations

2^m ≥ 90 → m = 7

N = 128

W₈ (blue +1, orange −1)

−1

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

30 / 37

Try it: share one channel with codes

Interactive

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

31 / 37

Multiple-access methods compared

Method	Family	Collisions	Efficiency	Where used
Pure ALOHA	random	yes	18.4%	first radio LAN
Slotted ALOHA	random	yes	36.8%	random-access requests (satellite, cellular)
CSMA/CD	random	detected, aborted	high on short LANs	classic shared Ethernet
CSMA/CA	random	avoided (IFS, backoff, RTS/CTS)	good	Wi-Fi (802.11)
Reservation / polling / token	controlled	none	high, with overhead	token ring, FDDI, Bluetooth polling
FDMA / TDMA / CDMA	channelization	none	fixed share	1G / 2G (GSM) / 3G cellular

Random access suits bursty traffic and many idle stations; controlled access and channelization suit steady traffic and guaranteed delay.

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

32 / 37

Try it yourself: Multiple Access Lab

1 · ALOHA: throughput curves, random runs and Examples 12.3/12.4
2 · CSMA/CD: draw a collision in space and time; minimum frame
3 · Backoff: roll R until two stations separate; p-persistent
4 · CDMA: Walsh codes, the channel sum and decoding

Scan to open the lab on your phone

Open the lab ↗

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

33 / 37

See it in action: sharing one medium

Watch pure ALOHA frames collide, then slotted ALOHA
See a CSMA/CD collision travel along a cable
See RTS/CTS save a hidden station
Watch CDMA codes add up and come apart
When a “Pause & predict” card appears, answer before the video moves on

Click the video to play or pause · Press → for full screen

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

34 / 37

Checkpoint 3 · 3 minutes

Check your understanding

Q1

CDMA with W₄: station 1 sends 1, station 2 is silent, station 3 sends 1, station 4 sends 0. What is on the channel? Decode station 3.

Q2

How many chips per bit does a CDMA network of 20 stations need?

Q3

In a token ring, the station holding the token crashes. What goes wrong, and what fixes it?

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

36 / 37

Key takeaways

Three families: random access, controlled access, channelization
ALOHA: vulnerable 2T_fr (pure) or T_fr (slotted); S_max 18.4% and 36.8%
CSMA/CD: listen while sending; minimum frame T_fr ≥ 2T_p
CSMA/CA: IFS, contention window, ACK; RTS/CTS and NAV for hidden stations
FDMA, TDMA, CDMA: share frequency, time or orthogonal codes

Next lecture

Lecture 14 · Wireless Communication Basics

Radio propagation, antennas, path loss and fading, Wi-Fi and cellular concepts: where CSMA/CA and channelization are used.

Reading: Forouzan, Chapters 15 and 16 · Practise in the Multiple Access Lab

Md Mahbub E Noor

Lecture 13: Multiple Access

University of Barishal

37 / 37