CS331 · Annotated SlidesChapter 3 · Part 2 — Data Link Layer: Multiple Access Protocols
Chapter 3 · Part 2 · Annotated slides

Data Link Layer: Multiple Access Protocols

How many stations share one link: random access (CSMA and its three persistence methods, CSMA/CD), controlled access (reservation, polling, token passing) and channelization (FDMA, TDMA, CDMA). The favourite questions compare them: who is fair, who can collide, and who is stuck at R/M even when alone on the link.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up

Data-Link Layer

CS331: Computer Networks · Chapter 3, Part 2: Media Access Control
1
Exam weight Low
  1. Shared link → MAC sublayer → random access (CSMA family) → controlled access → channelization.
TipR = the channel rate, M = the number of stations. R/M is a fair equal share.

Chapter outline

  • Random access
  • Controlled access
  • Channelization
2
Exam weight Low
  1. Three families of multiple-access protocols.

Multiple Access

  • Broadcast (shared) link: multiple sending and receiving nodes connected to (or using) a single shared link①
  • Shared link examples: shared wire (cabled Ethernet), shared RF (802.11 WiFi), shared RF (satellite), shared radio (4G/5G)②
Shared wire, shared WiFi radio, satellite and cellular radio
3
Exam weight Low
  1. Broadcast link = many nodes, ONE medium. Everyone hears every transmission.

Seen again

↻ Ch 1 Part 1, slide 8 · Multipoint connections

Multiple Access

  • Problem: when two or more nodes transmit at the same time, their frames collide and the link bandwidth is wasted during the collision①
    • How do we coordinate the access of multiple sending/receiving nodes to the shared link?
  • Solution: a protocol to coordinate the transmission of the active nodes
  • These protocols are called Medium or Multiple Access Control (MAC) protocols and belong to a sublayer of the data link layer called MAC (Medium Access Control)②
4
Exam weight Medium
  1. Collision = two frames on the medium at once → both destroyed, bandwidth wasted.
  2. MAC protocols decide who sends when. They live in the MAC sublayer.

Data link layer: two sublayers

  • Data link control (LLC): responsible for error and flow control①
  • Multiple-access control (MAC): responsible for framing, MAC address and multiple access control②
Data link layer split into Logical Link Control above and Multiple-access Control (MAC) below
5
Exam weight High
  1. Upper sublayer LLC: error and flow control. Lower sublayer MAC: framing, MAC address, multiple access.
Exam trapIn these slides framing and MAC addresses are listed under the MAC sublayer, not LLC.
🎯 How this can come up · 2 questions
MCQ

Which data link sublayer is responsible for error and flow control?

MCQ

The MAC sublayer is responsible for:

Taxonomy of multiple-access protocols

Random access: CSMA/CD (wired LAN), CSMA/CA (wireless LAN). Controlled access: reservation, polling, token passing. Channelization: FDMA, TDMA, CDMA
6
Exam weight High
  1. Random: CSMA/CD (wired), CSMA/CA (wireless). Controlled: reservation, polling, token passing. Channelization: FDMA, TDMA, CDMA.
Memory trickRandom = free for all · Controlled = take turns · Channelization = split the channel.
🎯 How this can come up · 3 questions
MCQ

Token passing belongs to which family?

MCQ

CSMA/CA is used in:

MCQ

Which is a channelization protocol?

Random Access

Random access protocols:

  • No station is superior to another station and none is assigned control over another.①
  • A station with a frame to be transmitted can use the link directly, based on a procedure defined by the protocol, to decide whether or not to send.②
7
Exam weight Low
  1. Random access: no master, no turns. Each station decides for itself when to send, so collisions are possible.

Random Access – Carrier Sense Multiple Access (CSMA)

  • Based on the fact that in a LAN the propagation time is very small
  • If a frame is sent by a station, all stations know immediately, so they can wait before starting to send
    • A station with frames to send should sense the medium for another transmission (carrier) before it starts its own①
  • This can reduce the possibility of collision but it cannot eliminate it.②
    • A collision can only happen when more than one station begins transmitting within a short time (the propagation time period)③
Stations B and C both sense an idle medium and send; their frames collide partway
8
Exam weight High
  1. CSMA = listen before you talk.
  2. It reduces collisions but can’t eliminate them: a station far away may not hear a frame that already started.
  3. Collisions only happen within the propagation time window.
Exam trap“CSMA eliminates collisions” ✗. It only reduces them.
🎯 How this can come up · 2 questions
True / False

CSMA eliminates collisions completely.

MCQ

In CSMA, a station senses the medium:

Random Access – Carrier Sense Multiple Access (CSMA)

  • The vulnerable (unsafe) time for CSMA is the maximum propagation time
  • Maximum propagation delay (t_prop): the time it takes a bit of a frame to travel between the two most widely separated stations.①

Station A begins transmitting at t = 0; the farthest station B receives the first bit at t = t_prop②

Station A starts at t = 0; the farthest station receives the first bit at t = t_prop
9
Exam weight High
  1. Vulnerable time = max propagation delay between the two farthest stations.
🎯 How this can come up · 1 question
MCQ

The vulnerable time of CSMA equals:

Random Access – Carrier Sense Multiple Access (CSMA)

  • The longer the propagation delay, the worse the performance of the protocol.①
  • During this propagation period, a distant node might think the channel is still idle and start transmitting.
B senses at t1; C and D sense later before the frame reaches them; vulnerable time = propagation time
10
Exam weight Low
  1. Long cables = longer window where distant stations wrongly think the line is free.

Types of CSMA Protocols

Different CSMA protocols decide:

  • What should a station do when the medium is idle?
  • What should a station do when the medium is busy?
  1. Non-persistent CSMA
  2. 1-persistent CSMA
  3. p-persistent CSMA
11
Exam weight Low
  1. Three persistence methods: they differ in what to do when the line is BUSY and when it is IDLE.

Nonpersistent CSMA

A station with frames to send senses the medium:

  1. If the medium is idle, transmit; otherwise go to 2.
  2. If the medium is busy, (backoff) wait a random amount of time and repeat 1.①
  • Non-persistent stations are deferential (they respect others)②
  • Performance:
    • Random delays reduce the probability of collisions, because two stations with data will wait different amounts of time.
    • Bandwidth is wasted if the waiting time (backoff) is large, because the medium stays idle after a transmission ends even if stations have frames to send.③
Busy medium, then random waits; the channel sits idle (wasted time) before the station senses again
12
Exam weight High
  1. Non-persistent: busy → walk away for a random time, then check again.
  2. Fewer collisions, but the line can sit idle (wasted).
🎯 How this can come up · 1 question
MCQ

In non-persistent CSMA, if the medium is busy the station:

1-persistent CSMA

  • To avoid idle channel time, the 1-persistent protocol is used
  • A station wishing to transmit listens to the medium:
  1. If the medium is idle, transmit immediately;
  2. If the medium is busy, continuously listen until it becomes idle, then transmit immediately with probability 1 (100%)①
  • Performance
    • 1-persistent stations are selfish②
    • If two or more stations become ready at the same time, a collision is guaranteed③
A and B both wait for the channel to become idle and transmit immediately, so they collide
13
Exam weight High
  1. 1-persistent: busy → keep listening → the instant it’s idle, send (probability 1).
  2. No idle time, but if two stations were waiting, they BOTH send → guaranteed collision.
Memory trickNon-persistent = polite (walks away). 1-persistent = selfish (stares at the line).
🎯 How this can come up · 2 questions
MCQ

Which persistence method guarantees a collision when two stations wait for the same busy channel?

True / False

1-persistent CSMA sends with probability 1 as soon as the channel becomes idle.

P-persistent CSMA

  • Time is divided into slots; each slot typically equals the maximum propagation delay
  • A station wishing to transmit listens to the medium:
  1. If the medium is idle: transmit with probability p, OR wait one time slot with probability 1 – p, then repeat listening to the medium.①
  2. If the medium is busy, continuously listen until idle and repeat step 1.②
  • Performance:
    • Reduces the possibility of collisions, like non-persistent
    • Reduces channel idle time, like 1-persistent③
Continuous sensing while busy, then time slots; transmission when the probability outcome allows
14
Exam weight High
  1. p-persistent: idle → send with probability p, or wait one slot with probability 1 - p.
  2. Best of both: fewer collisions (like non-persistent) and less idle time (like 1-persistent).
  3. Slot = maximum propagation delay.
🎯 How this can come up · 2 questions
MCQ

In p-persistent CSMA, a time slot equals:

Written

Compare non-persistent, 1-persistent and p-persistent CSMA when the channel is busy and when it becomes idle.

Flow diagram for three persistence methods

Flow charts: 1-persistent senses until idle and sends; non-persistent waits randomly when busy; p-persistent draws R and sends if R ≤ p, else waits a slot
15
Exam weight Low
  1. p-persistent: draw a random R in [0, 1]; if R ≤ p send, otherwise wait a slot.

Persistent and non-persistent CSMA: throughput

Comparison of the channel utilization versus load for various random access protocols. Throughput: the fraction of the channel successfully carrying packets.

Throughput S versus load G: 0.01-persistent highest, then non-persistent, 0.1-persistent, 0.5-persistent, 1-persistent lowest
16
Exam weight Medium
  1. Under heavy load, 1-persistent does worst (collisions); small p and non-persistent do best.
🎯 How this can come up · 1 question
MCQ

Under heavy load, which CSMA variant has the lowest throughput on the graph?

CSMA/CD (Collision Detection)

  • CSMA (all previous methods) has an inefficiency:
    • If a collision occurs, the channel is unstable until the colliding packets have been fully transmitted①
  • CSMA/CD (Carrier Sense Multiple Access with Collision Detection) overcomes this as follows:
    • While transmitting, the sender is listening to the medium for collisions.
    • The sender stops transmission if a collision has occurred, reducing channel wastage.②

CSMA/CD is widely used in star topology if a hub is used③

17
Exam weight High
  1. Plain CSMA keeps sending the whole (already ruined) frame. CSMA/CD listens WHILE sending and stops as soon as it detects a collision.
  2. Used on shared Ethernet (bus or hub).

Seen again

↻ Ch 4, slide 6 · CSMA/CD in classic Ethernet
🎯 How this can come up · 1 question
MCQ

What does CSMA/CD add to CSMA?

How does a node detect a collision?

Transceiver: a node monitors the medium while transmitting. If the observed power is more than the transmitted power of its own signal, a collision has occurred.①

Transmitted signal vs. observed signal: the observed one has extra energy where the collision happens
18
Exam weight Low
  1. Detection = the energy on the wire is higher than what I am sending → someone else is sending too.

CSMA/CD Protocol

  • Use one of the CSMA persistence algorithms (non-persistent, 1-persistent, p-persistent) for transmission
  • If a collision is detected by a station during its transmission, it should:
    • Abort transmission, and
    • Transmit a jam signal (48 bits) to notify the other stations of the collision, so that they discard the transmitted frame, and to make sure the collision signal stays until it is detected by the furthest station①
    • After sending the jam signal, back off (wait) for a random amount of time, then
    • Reapply the CSMA persistence algorithm used②
19
Exam weight High
  1. On collision: ABORT → send a 48-bit JAM → random BACKOFF → try again with the same persistence method.
Memory trickCSMA/CD collision steps: “Abort, Jam, Back off, Retry.”
🎯 How this can come up · 2 questions
MCQ

After detecting a collision, a CSMA/CD station first:

MCQ

The jam signal in the slides is:

Performance of Random Access Protocols

  • Simple and easy to implement
  • Decentralized (no central device that can fail and bring down the entire system)
  • In low traffic, packet transfer has low delay
  • However, in heavier traffic, packet delay has no limit.①
  • In some cases, a station may never have a chance to transfer its packet (unfair protocol)
  • A node that has frames to transmit can transmit continuously at the full rate of the channel (R) if it is the only node with frames②
  • If M nodes want to transmit, many collisions can occur and the maximum average throughput for each node will not be R/M
    • (R/M = ideal average rate per node if the channel were divided equally with no overhead or collisions.)③
20
Exam weight High
  1. Random access: simple, decentralized, great at low load; UNFAIR and unbounded delay at high load.
  2. Alone on the link → full rate R. Busy link → each node gets less than R/M because of collisions.
🎯 How this can come up · 2 questions
True / False

Random access protocols are fair: every station is guaranteed a turn.

MCQ

A single active station using random access can send at:

Controlled access (scheduling)

  • Provides in-order access to the shared medium so that every station has a chance to transfer (fair protocol)①
  • A node is limited to throughput equal to R/M②
  • Eliminates collisions completely
  • Three methods for controlled access:
    • Reservation
    • Polling
    • Token passing③
21
Exam weight High
  1. Controlled access: stations take turns → fair, no collisions, but capped at R/M.
Exam trapRandom = can collide, unfair, R when alone. Controlled = never collides, fair, R/M.
🎯 How this can come up · 2 questions
MCQ

Which family eliminates collisions completely?

MCQ

The three controlled-access methods are:

1-Reservation access method

  • Stations take turns transmitting a single frame at a

full rate (R) bps①

  • Transmissions are organized into variable length cycles
  • Each cycle begins with a reservation frame that consists of N minislots, one minislot for each of the N stations②
  • When a station needs to send a data frame, it makes a

reservation in its own minislot.

  • By listening to the reservation interval, every station knows which stations will transfer frames, and in which order.
  • The stations that made reservations can send their data frames after the reservation frame.③ 22
A reservation frame of 5 minislots followed by data frames from the stations that reserved
22
Exam weight Medium
  1. Each cycle starts with a reservation frame of N minislots (one per station). A station sets its minislot to reserve a turn.
  2. Everyone hears the reservations, so everyone knows the order. Then the reserved data frames follow.
🎯 How this can come up · 1 question
MCQ

In the reservation method, a reservation frame contains:

2- Polling

  • Stations take turns accessing the medium
  • Two models: Centralized and distributed polling
  • Centralized polling
    • One device is assigned as primary station and the others as secondary stations①
    • All data exchanges are done through the primary
    • When the primary has a frame to send, it sends a select frame that includes the address of the intended secondary
    • When the primary is ready to receive data it sends a Poll frame for each device to ask if it has data to send or not. If yes, data will be transmitted otherwise NAK (Negative Acknowledgement) is sent.②
    • Polling can be done in order (Round-Robin) or based on predetermined order
  • Distributed polling
    • No primary and secondary
    • Stations have a known polling order list which is made based on some protocol
    • station with the highest priority will have the access right first, then it passes the access right to the next station (it will send a pulling message to the next station in the pulling list), which will passes the access right to the following next station, ... (Reservation and Token Passing are examples of Distributed Polling)③ 23
23
Exam weight High
  1. Centralized polling: a PRIMARY controls everything. SELECT = primary wants to send to a secondary. POLL = primary asks a secondary if it has data (data or NAK back).
  2. Distributed polling: no primary; stations follow a known order and pass the right to send along. Reservation and token passing are distributed polling.
Memory trickSELect = primary SEnds. POLL = primary coLLects.
🎯 How this can come up · 3 questions
MCQ

In centralized polling, the primary sends a ___ frame when it wants to send data to a secondary.

MCQ

A secondary with nothing to send answers a poll with:

True / False

Token passing is an example of distributed polling.

Select and poll functions in polling access method (Figure 12.19)

Select: primary sends SEL, secondary ACKs, data, ACK. Poll: primary sends Poll, secondary answers NAK or data, primary ACKs
24
Exam weight Low
  1. Left: primary → secondary uses SEL. Right: secondary → primary starts with a POLL.

Token-passing network

  • Implements a distributed polling system
  • A special frame called the token rotates around the ring.①
  • Any station that wants to send data has to wait for a free token to arrive.
  • The station makes the token busy by inserting its data into it and putting in the destination address.
  • The destination station receives the data and changes the token back to free.②
Stations A, B, C, D in a logical ring with the token travelling between them
25
Exam weight High
  1. Only the station holding the free token may send → no collisions.
🎯 How this can come up · 1 question
MCQ

In token passing, a station can send when it:

Token-passing procedure (Figure 13.13)

Wait for the token → capture it → send frames while time remains and there is data → release the token
26
Exam weight Low
  1. A station keeps the token only while it has data AND its allocated time hasn’t expired, then releases it.

Channelization

Channelization is a multiple-access method in which the available bandwidth of a link is shared in time, frequency, or through code, between different stations.①

  • Frequency-Division Multiple Access (FDMA)
  • Time-Division Multiple Access (TDMA)
  • Code-Division Multiple Access (CDMA)②
27
Exam weight Low
  1. Split the channel by frequency (FDMA), by time (TDMA) or by code (CDMA).

Frequency-division multiple access (FDMA) (Figure 12.21)

Four stations each send in their own frequency band of a common channel
28
Exam weight Low
  1. Each station has its own frequency band, all the time.

Channelization: FDMA

  • FDMA: Frequency Division Multiple Access
    • The transmission medium is divided into M separate frequency bands①
    • Each station transmits continuously on its assigned band at an average rate of R/M②
    • A node is limited to an average throughput of R/M even when it is the only node with frames to send③
29
Exam weight High
  1. FDMA: own band, send continuously, R/M even when alone (other bands sit empty).
🎯 How this can come up · 1 question
MCQ

In FDMA, a station that is the only one with data can send at:

Time-division multiple access (TDMA) (Figure 12.22)

Four stations each send in their own time slot of a common channel
30
Exam weight Low
  1. Each station has its own time slot on the whole bandwidth.

Channelization: TDMA

  • TDMA: Time Division Multiple Access
    • The entire bandwidth is a single channel whose capacity is shared in time between M stations①
    • A node must always wait for its turn until its slot arrives, even when it is the only node with frames③ to send②
    • A node is limited to an average throughput of R/M even when it is the only node with frames
31
Exam weight High
  1. TDMA: whole bandwidth, but only in your slot. Still R/M on average even when alone.
Exam trapFDMA, TDMA (and controlled access) cap a lone station at R/M; random access lets it use all of R.
🎯 How this can come up · 2 questions
True / False

In TDMA, a station that is the only one with frames can use every time slot.

Written

Compare FDMA and TDMA.

Channelization: CDMA

  • CDMA: Code Division Multiple Access
    • In CDMA, one channel carries all transmissions simultaneously①
    • Each station codes its data signal with a specific code before transmission
    • The receivers use these codes to recover the data of the desired station②
32
Exam weight High
  1. CDMA: everyone sends at the same time on the same frequency; codes separate them.
🎯 How this can come up · 1 question
MCQ

In which method do all stations send at the same time over the same channel, separated by codes?

Simple idea of communication with code (Figure 12.23)

Four stations send d·c; the common channel carries d1·c1 + d2·c2 + d3·c3 + d4·c4; each receiver extracts its own data
33
Exam weight Low
  1. Each station multiplies its data by its code; the channel carries the SUM; a receiver multiplies by the wanted code to pull its data out.

FDMA vs. TDMA vs. CDMA

FDMA slices frequency, TDMA slices time, CDMA slices by code
34
Exam weight Low
  1. FDMA = frequency slices. TDMA = time slices. CDMA = code slices (everyone uses all frequencies all the time).
Memory trickF = Frequency, T = Time, C = Code.