Multiple Access Overview

Imagine you're managing a popular shared workspace with 100 desks and 200 people who need to work there throughout the day. How do you allocate the desks?

Option 1: Static Allocation "Each of you gets a desk for half the day. Person 1-100: 9 AM-2 PM. Person 101-200: 2 PM-7 PM." Simple, predictable, but wasteful when people don't show up during their slot.

Option 2: Dynamic Allocation "Desks are first-come-first-served. When you need one, check in. When you leave, check out." More efficient on average, but no guarantees—you might arrive when all desks are taken.

Option 3: Demand-Based Allocation "Request a desk when you need it. Based on your needs and current availability, you'll be assigned a time slot." Balances efficiency and predictability, but requires coordination overhead.

Channel allocation in networking follows the same principles. How should a shared communication channel's capacity be divided among competing users? This fundamental question underlies every MAC protocol design.

This page explores channel allocation from theoretical foundations to practical implementation, preparing you to understand why different protocols make different allocation choices.

Before diving into solutions, let's precisely define what we're trying to solve.

Problem Statement

Given:

• A communication channel with total capacity C bits/second
• N stations (users) that need to transmit data
• Traffic patterns: each station generates data at some rate, possibly variable over time
• Performance requirements: throughput, delay, fairness, reliability

Find:

• An allocation strategy that determines which station can use the channel at any given time
• A mechanism to implement that strategy

Constraints:

• Only one station can effectively transmit at a time (for bus/wireless) OR capacity is limited (for channelization)
• Stations have only local information (in distributed systems)
• Physical propagation delays affect coordination
• Implementation must be practical with reasonable cost and complexity

Why Allocation is Difficult

The channel allocation problem is challenging because of several competing factors:

Allocation Dimensions

Channel capacity can be divided along several independent dimensions:

Frequency (FDMA): Different stations use different frequency bands. Total bandwidth is partitioned.

Time (TDMA): Different stations transmit in different time slots. Frame duration is partitioned.

Code (CDMA): Different stations use different spreading codes. Code space is partitioned.

Space (SDMA): Different stations in different locations can use the same frequency/time (via directional antennas or spatial isolation).

Combinations: Modern systems like LTE/5G combine multiple dimensions (OFDMA uses both frequency and time).

The Fundamental Tradeoff

There's a fundamental tension in channel allocation:

Static (pre-determined) allocation:

• Pro: Guaranteed capacity, no contention
• Pro: Simple implementation
• Con: Wasted capacity when assigned station is idle
• Con: Inflexible to demand changes

Dynamic (demand-based) allocation:

• Pro: Efficient use of capacity (statistical multiplexing)
• Pro: Adapts to changing demand
• Con: No guarantees (contention possible)
• Con: Coordination overhead

The art of MAC protocol design is finding the right position on this spectrum for the target application.

Static allocation (also called fixed allocation) pre-assigns channel capacity to stations before communication begins. Each station knows exactly when and how it can transmit, regardless of actual demand.

Traditional Static FDMA

In classic FDMA (Frequency Division Multiple Access), the frequency spectrum is permanently divided:

Total Spectrum: 900-960 MHz (60 MHz)
Stations: 60
Allocation: Each station gets 1 MHz band

Station 1: 900-901 MHz (always available to Station 1)
Station 2: 901-902 MHz (always available to Station 2)
...
Station 60: 959-960 MHz (always available to Station 60)

Characteristics:

• Zero contention: You own your band
• Permanent allocation: Doesn't change with traffic
• Wasted if idle: Your unused band can't help others
• Guard bands: Some spectrum lost to separation (typically 10-20%)

Traditional Static TDMA

In classic TDMA (Time Division Multiple Access), time is permanently divided:

Frame Duration: 10 ms
Stations: 10
Allocation: Each station gets 1 ms slot per frame

Station 1: Slots 0-1 ms, 10-11 ms, 20-21 ms, ...
Station 2: Slots 1-2 ms, 11-12 ms, 21-22 ms, ...
...

Characteristics:

• Deterministic access: Know exactly when your slot comes
• Requires synchronization: All stations must agree on slot timing
• Wasted if idle: Empty slots represent lost capacity
• Guard times: Some time lost to slot boundaries

Mathematical Analysis of Static TDM

Consider a network with N stations sharing a channel of capacity C. With static TDM, each station gets C/N capacity.

Parameters:

• λ = arrival rate (frames per second per station)
• μ = service rate = C/N (bits per second per station)
• L = average frame length (bits)
• ρ = utilization per station = λL/μ = λLN/C

Mean delay (M/M/1 queue model):

T_static = 1/(μ - λ) = L/(C/N - λL) = NL/(C - NλL)

Example:

• C = 100 Mbps, N = 10 stations, L = 10,000 bits, λ = 500 frames/sec/station
• Each station capacity: 10 Mbps
• Traffic per station: 500 × 10,000 = 5 Mbps
• Utilization: 5/10 = 50%
• T_static = 1/(1000 - 500) = 2 ms

The Key Insight: Inefficiency Under Variable Load

Static allocation assumes all N stations need capacity continuously. In reality:

When Station A is busy and Station B is idle:

• Station A wants more than its share
• Station B's allocation is wasted
• Total throughput is limited by A's fixed allocation

The M stations active problem: If only M < N stations have data at any time, static allocation gives each only C/N, but they could share C/M if allocation were dynamic.

Static: Each active station gets C/N
Dynamic: Each active station gets C/M (M ≤ N)
Multiplexing gain: N/M

For bursty traffic where typically M << N, this multiplexing gain is substantial—often 10x or more.

This inefficiency drove the development of dynamic allocation methods.

Dynamic allocation assigns channel capacity based on current demand. Stations receive capacity only when they need it, allowing the channel to be shared more efficiently.

Types of Dynamic Allocation

1. Contention-Based (Random Access) Stations compete for the channel when they have data. No pre-allocation; access determined by contention protocol.

• Examples: ALOHA, CSMA, CSMA/CD, CSMA/CA
• Advantage: Maximum flexibility, minimal overhead when idle
• Disadvantage: Collisions waste capacity, no guarantees

2. Demand-Assigned (Reservation) Stations request capacity when needed; a scheduler grants access.

• Examples: Reservation ALOHA, DAMA (Demand-Assigned Multiple Access)
• Advantage: Combines dynamic efficiency with scheduled access
• Disadvantage: Reservation overhead, request delay

3. Centrally Scheduled A central controller monitors demand and assigns capacity.

• Examples: Polling, LTE scheduler, Wi-Fi PCF
• Advantage: Optimal global decisions, QoS enforcement
• Disadvantage: Single point of failure, requires controller knowledge

Statistical Multiplexing Gain

The mathematical advantage of dynamic allocation comes from statistical multiplexing:

Scenario:

• 100 users, each needing 1 Mbps when active
• Each user is active 10% of the time
• Average aggregate demand: 100 × 1 × 0.1 = 10 Mbps

Static allocation: Need 100 Mbps capacity (1 Mbps × 100 users) Utilization: 10/100 = 10%

Dynamic allocation: Need ~15-20 Mbps capacity (10 Mbps average + safety margin for variance) Utilization: ~50-67%

Multiplexing gain: 100/15 to 100/20 = 5x to 6.7x

The more bursty the traffic (lower duty cycle), the greater the multiplexing gain.

Mathematical Analysis: Queuing Theory Perspective

Dynamic allocation can be modeled as a shared queue versus N separate queues.

N Separate Queues (Static Allocation):

• Each queue has service rate μ = C/N
• Mean delay: Σ(1/(μ - λ_i))/N

Single Shared Queue (Ideal Dynamic):

• One queue with service rate μ = C
• Mean delay: 1/(C - Σλ_i)

Result (for identical stations):

T_static / T_dynamic = N × (1 - ρ) / (1 - ρ/N)

Where ρ = total traffic / capacity

For ρ = 0.5 and N = 10: T_static / T_dynamic ≈ 5.3

Dynamic allocation provides 5.3x better delay performance!

Dynamic TDMA Variants

Demand-Assigned TDMA: Slots are not permanently assigned. Instead:

1. Stations send reservation requests during contention slots
2. Controller collects requests and builds schedule
3. Schedule specifies which station transmits in each slot
4. Stations with no data get no slots (capacity available to others)

Used in satellite systems (DAMA) and some industrial networks.

Packet Reservation Multiple Access (PRMA): Hybrid for voice applications:

1. Voice user contends for a slot when starting to talk
2. Once acquired, slot repeats automatically (implicit reservation)
3. Slot released when speech pause detected
4. Other users can contend for released slots

Combines efficiency of dynamic access with regularity needed for voice.

Dynamic Frequency Allocation

Cognitive Radio / Dynamic Spectrum Access: Modern approach where stations:

1. Sense spectrum to find unused frequencies
2. Dynamically use available frequencies
3. Vacate if primary users appear
4. Coordinate to avoid interfering with each other

This moves allocation from static spectrum licensing to dynamic spectrum sharing—a frontier research area.

Beyond efficiency, a critical concern in channel allocation is fairness: ensuring that all stations receive reasonable access to the shared resource.

Defining Fairness

Fairness can be defined in multiple ways:

1. Equal Opportunity Fairness All stations have the same probability of successful transmission attempts.

• Achieved by: Random access with identical backoff distributions
• Limitation: Doesn't guarantee equal throughput

2. Equal Throughput Fairness All stations achieve the same long-term throughput.

• Achieved by: Round-robin scheduling, equal TDMA slots
• Limitation: Ignores different needs; wastes slots for idle stations

3. Proportional Fairness Throughput proportional to some weight (priority, subscription level).

• Achieved by: Weighted fair queueing, priority scheduling
• Common in: Cellular networks, QoS systems

4. Max-Min Fairness Maximize the minimum throughput across all stations.

• Achieved by: Complex scheduling algorithms
• Optimal for: Situations where all stations have equal priority

Jain's Fairness Index

The most commonly used fairness metric in networking is Jain's Fairness Index:

J(x₁, x₂, ..., xₙ) = (Σxᵢ)² / (n × Σxᵢ²)

Where xᵢ is the throughput (or other resource measure) for station i.

Properties:

• Range: [1/n, 1]
• J = 1: All stations have equal throughput (perfectly fair)
• J = 1/n: One station gets all throughput (maximally unfair)
• Population-independent: Same formula works for any n

Example:

• 4 stations with throughput: [10, 10, 10, 10] Mbps

• J = (40)² / (4 × 400) = 1600/1600 = 1.0 (perfect)

• 4 stations with throughput: [40, 0, 0, 0] Mbps

• J = (40)² / (4 × 1600) = 1600/6400 = 0.25 = 1/4 (worst case)

Fairness in Random Access

CSMA/CD Fairness: Binary exponential backoff creates some unfairness:

• Station that just transmitted has backoff = 0 or 1
• Station that collided has larger backoff window
• Recent winners are more likely to win again

This "capture effect" can cause temporary unfairness, but long-term averages tend to equalize.

CSMA/CA Fairness: Wi-Fi's access mechanism can be unfair:

• Stations closer to the AP have lower error rates, faster backoff completion
• Hidden terminals cause repeated collisions for specific station pairs
• 802.11ax (Wi-Fi 6) introduces mechanisms to improve fairness

Fairness in Controlled Access

Token Ring: Intrinsically fair—each station holds the token for the same maximum time (Token Holding Time). Every station gets exactly one opportunity per token rotation.

Polling: Fairness depends on poll order and frequency. Equal polling = equal opportunity.

Fairness in Channelization

Equal TDMA/FDMA: Perfectly fair by allocation—each station gets equal slice.

Weighted allocation: Fairness relative to weights. If Station A has weight 2 and Station B has weight 1, A getting 2× B's bandwidth is "proportionally fair."

Modern networks must support diverse applications with vastly different requirements. Quality of Service (QoS) mechanisms ensure that each application's needs are met through intelligent channel allocation.

Traffic Categories and Requirements

Different applications have different sensitivities:

Real-Time Interactive (Voice, Video Conferencing):

• Latency: Critical (< 150ms end-to-end)
• Jitter: Critical (< 30ms variation)
• Packet loss: Moderate tolerance (1-3%)
• Bandwidth: Moderate, constant

Streaming Media (Video, Music):

• Latency: Moderate (buffering possible)
• Jitter: Moderate (buffering smooths)
• Packet loss: Low tolerance (< 1%)
• Bandwidth: High, relatively constant

Interactive Data (Web, Gaming):

• Latency: Important (< 200ms round-trip)
• Jitter: Less important
• Packet loss: Zero tolerance (TCP retransmits)
• Bandwidth: Bursty, variable

Bulk Transfer (Downloads, Backup):

• Latency: Not important
• Jitter: Not important
• Packet loss: Zero tolerance
• Bandwidth: As much as available

QoS-Aware Allocation Mechanisms

Priority Queuing: Traffic is classified into priority levels. High-priority traffic is always served before low-priority traffic.

Priority 1 (Highest): Voice
Priority 2: Video
Priority 3: Interactive data
Priority 4 (Lowest): Bulk transfers

Risk: Starvation—low priority may never get service under heavy load.

Weighted Fair Queuing (WFQ): Each traffic class gets a weight. Capacity is divided proportionally.

Voice: Weight 4 (gets 4 units of service per round)
Video: Weight 3 (gets 3 units per round)
Data: Weight 2 (gets 2 units per round)
Best-effort: Weight 1 (gets 1 unit per round)

Advantage: Prevents starvation while providing differentiated service.

Token Bucket Shaping: Limit burst size while allowing average rate:

• Bucket holds tokens that refill at average rate r
• To transmit, frame must claim tokens equal to its size
• Bucket capacity b limits maximum burst
• Result: Average rate r, burst tolerance b, excess traffic delayed/dropped

Admission Control: Before accepting a new flow (voice call, video stream), check if network can support it:

• If yes: Accept and reserve resources
• If no: Reject (busy signal, buffering warning)

Prevents overcommitment that would degrade all flows.

QoS in Different MAC Technologies

Ethernet (IEEE 802.1p):

• 3-bit Priority Code Point (PCP) in VLAN tag
• 8 priority levels (0-7)
• Switch queues traffic by priority
• Higher priority transmitted first

Wi-Fi (IEEE 802.11e/WMM):

• Four Access Categories: Voice > Video > Best Effort > Background
• Different CSMA parameters per category:
  • Voice: Smaller contention window, shorter inter-frame gaps
  • Background: Larger window, longer gaps
• Results in probabilistic priority during contention

Cellular (LTE/5G):

• QoS Class Identifier (QCI) defines treatment
• Guaranteed Bit Rate (GBR) vs. Non-GBR bearers
• Scheduler enforces QoS based on traffic type

DOCSIS (Cable):

• Service Flow IDs define QoS parameters
• Scheduler allocates upstream slots to meet guarantees
• Unsolicited Grant Service for constant bit rate

Modern networks employ sophisticated allocation strategies that combine elements from static and dynamic approaches. Let's examine how real systems solve the allocation problem.

LTE/5G Cellular: Dynamic Scheduling

Cellular networks use fully dynamic scheduling with centralized control:

Resource Blocks:

• Time-frequency resources divided into Resource Blocks (RBs)
• Each RB: ~180 kHz × 0.5 ms (LTE) or variable (5G NR)
• Scheduling decisions made every Transmission Time Interval (TTI)

Scheduler Inputs:

• Buffer status reports from user devices
• Channel quality indicators (CQI) per device
• QoS requirements per bearer
• Fairness constraints

Scheduler Output:

• Which devices get which RBs this TTI
• Modulation and coding scheme for each

Scheduling Algorithms:

• Round Robin: Simple, fair, ignores channel quality
• Max C/I: Maximum throughput, unfair to edge users
• Proportional Fair: Balance throughput and fairness
• M-LWDF: Delay-aware for real-time traffic

Wi-Fi 6 (802.11ax): OFDMA

Wi-Fi 6 introduced multi-user OFDMA for finer-grained allocation:

Before (802.11ac): Entire channel (20/40/80/160 MHz) allocated to one user per transmission.

After (802.11ax): Channel divided into Resource Units (RUs). Multiple users can be scheduled simultaneously in different RUs.

20 MHz channel divisions:
- 1 × 242-tone RU (full channel, one user)
- 2 × 106-tone RUs (two users simultaneously)
- 4 × 52-tone RUs (four users simultaneously)
- 9 × 26-tone RUs (nine users simultaneously)

Benefits:

• Efficient for small packets (IoT, voice)
• Reduces contention overhead
• Access point schedules based on traffic needs

Satellite Systems: Demand-Assigned TDMA

Satellite systems face unique challenges (long delays, expensive bandwidth) that drive sophisticated allocation:

DVB-RCS2 Return Link:

1. Terminal sends capacity request (traffic backlog, QoS needs)
2. Network Control Center builds Terminal Burst Time Plan (TBTP)
3. TBTP tells each terminal exactly when to transmit in upcoming frames
4. Allocation adapts to demand every superframe (~45-135 ms)

Efficiency mechanisms:

• Contention slots for request messages (small, tolerable collision cost)
• Multiple capacity request modes (per-frame or periodic)
• Rate adaptation based on link conditions (ACM)

Data Center Networks: Credit-Based Allocation

Data center fabrics use different approaches:

Priority Flow Control (PFC):

• Switch buffer fills → send PAUSE to upstream
• Upstream stops transmitting indicated priority classes
• Prevents buffer overflow, enables lossless Ethernet

Explicit Congestion Notification (ECN):

• Switch marks packets when buffer passes threshold
• Receiver echoes mark to sender
• Sender reduces transmission rate

RDMA over Converged Ethernet (RoCE):

• Applications bypass kernel, write directly to NIC
• Requires lossless network (PFC/ECN)
• Allocation via flow control, not MAC contention

We've completed our exploration of channel allocation—the theoretical and practical frameworks for sharing network capacity. Let's consolidate the key insights:

Module Complete: Foundation Established

With this page, you've completed Module 1: Multiple Access Overview. You now possess a comprehensive understanding of:

1. The shared channel problem — Why multiple access control is necessary
2. The MAC sublayer — Its position, responsibilities, and implementation
3. Collision concepts — Physical nature, detection, avoidance, and impact
4. MAC protocol categories — Random access, controlled access, channelization
5. Channel allocation — Static vs. dynamic, fairness, QoS, modern strategies

This foundation prepares you to study specific MAC protocols in depth. The subsequent modules in this chapter will cover:

• ALOHA Protocols — The foundational random access family
• CSMA Protocols — Carrier sensing and its variants
• CSMA/CD — Ethernet's collision detection approach
• Controlled Access — Polling and token passing
• Channelization — FDMA, TDMA, CDMA in detail

Each protocol will make intuitive sense because you understand the category it belongs to, the problem it solves, and the tradeoffs it makes.