Multiple Access Overview

Imagine a crowded conference room where twenty people need to speak, but there's only one microphone. If everyone talks simultaneously, the result is unintelligible noise—nobody's message gets through. If everyone waits politely for others to finish, communication becomes inefficient, with long awkward silences. Somehow, the group must develop rules for sharing the microphone efficiently and fairly.

This is the shared channel problem—and it is the foundational challenge of Medium Access Control (MAC) in computer networks.

Every time you connect to Wi-Fi, plug into an Ethernet switch, or transmit data over a shared network, your device participates in a carefully orchestrated dance of coordination. The underlying communication channel—whether a copper cable, fiber optic strand, or wireless spectrum—is fundamentally a shared resource. Without sophisticated protocols governing access, network communication would collapse into chaos.

A communication channel is the physical or logical medium through which data signals travel between network devices. Understanding the nature of shared channels requires examining how they differ from dedicated point-to-point links and why sharing introduces complexity.

Point-to-Point vs. Shared Channels

In a point-to-point link, two devices have exclusive access to a dedicated communication path. Think of a direct telephone line between two offices—when you pick up the phone, you have the entire capacity of that line to yourself. There's no contention, no competition, and no need for complex coordination protocols.

In contrast, a shared channel (also called a broadcast channel or multiple access channel) connects multiple devices to the same communication medium. Every device physically attached to the channel can potentially transmit and receive signals. This is analogous to a party line telephone system, a public address system, or a group radio frequency.

Why Share Channels at All?

Given the complexity that shared channels introduce, why do networks use them? The answer lies in economics and practicality:

1. Cost Efficiency Dedicated point-to-point links between every pair of devices would require n(n-1)/2 connections for n devices. For 100 devices, that's 4,950 separate links. Shared channels dramatically reduce infrastructure costs by allowing all devices to use a common medium.

2. Physical Constraints Some transmission media inherently broadcast to all receivers. Wireless radio waves propagate in all directions—there's no practical way to create point-to-point links without extensive directional hardware. The electromagnetic spectrum is fundamentally shared.

3. Efficient Resource Utilization Most network devices don't transmit continuously. A workstation might only use the network 1-5% of the time. Dedicating a full channel to each device wastes 95-99% of that capacity. Shared channels allow statistical multiplexing, where many devices share bandwidth and the aggregate demand averages out.

4. Flexibility and Scalability Adding a new device to a shared channel is often as simple as physical connection. No new links need to be provisioned to every existing device. This dramatically simplifies network expansion.

When multiple devices share a communication channel, several critical problems emerge. Understanding these problems is essential before studying the solutions (MAC protocols).

The Simultaneous Transmission Problem

The most immediate issue is what happens when two or more devices attempt to transmit at the same time. On most shared media, the signals interfere with each other, corrupting both transmissions. Neither sender's data reaches its destination intact.

Consider what happens physically:

On electrical cables (Ethernet): Voltage levels representing binary data combine algebraically. A '1' from Station A (+5V) and a '1' from Station B (+5V) might combine to create +10V—a voltage that receivers cannot interpret correctly. The frame becomes corrupted.

On wireless networks (Wi-Fi): Radio signals at the same frequency overlap in the air. The electromagnetic waves combine through superposition, creating interference patterns that destroy the information content of both signals.

On optical fiber (shared segment): Light pulses from different sources can overlap temporally, making it impossible to distinguish individual transmissions.

In all cases, simultaneous transmission leads to data loss. The transmitted frames must be discarded, and the data must be retransmitted—wasting channel capacity and adding latency.

The Hidden Information Problem

A second fundamental challenge is that each device has incomplete information about the network state. Consider these scenarios:

No knowledge of other devices' intentions: Station A has no way of knowing that Station B is about to start transmitting. By the time A realizes B is active, it may have already begun sending its own frame.

Propagation delay blindness: Even if Station A can detect another station's transmission, propagation delay means that signal takes time to travel across the medium. Station A might start transmitting because the channel appears idle, unaware that Station C began transmitting moments earlier and the signal hasn't arrived yet.

Hidden terminals in wireless: In wireless networks, Station A might be able to hear Station B but not Station C. If Station C is transmitting to Station B, Station A cannot detect C's signal and might transmit simultaneously, causing a collision at B.

This incomplete information means that devices cannot simply "look before they leap"—the very act of checking the channel state takes time, during which the state may change.

The Fairness Problem

Beyond preventing collisions, shared channels raise questions of fairness:

• Should all devices receive equal access, or should some have priority?
• How do we prevent aggressive devices from monopolizing the channel?
• What happens when one device always has data to send while others transmit occasionally?

Starvation occurs when some devices are perpetually denied access while others transmit. A good MAC protocol must ensure reasonable access for all legitimate devices while still utilizing the channel efficiently.

The Efficiency Problem

Collisions directly waste channel capacity, but the overhead of collision avoidance also consumes resources:

• Time spent sensing the channel is time not spent transmitting
• Control messages (acknowledgments, tokens, etc.) consume bandwidth
• Backoff periods after collisions reduce effective throughput
• Complex protocols add processing overhead to every device

The ideal MAC protocol would achieve:close to 100% channel utilization while experiencing zero collisions and guaranteeing fair access to all devices. In practice, these goals conflict, and real protocols make tradeoffs.

The shared channel problem isn't an abstract theoretical concern—it affects every network technology in use today. Let's examine how it manifests in different contexts:

Classic Ethernet (10BASE5, 10BASE2)

The original Ethernet design from Xerox, DEC, and Intel used a shared coaxial cable—literally a single wire running through an entire office or building. Every workstation connected to this cable via transceivers ("taps").

The problem: Any workstation could transmit at any time. With dozens of machines on the same cable, collisions were inevitable. Early Ethernet networks with heavy traffic could experience collision rates exceeding 30%, meaning nearly a third of all transmission attempts failed.

The solution: CSMA/CD (Carrier Sense Multiple Access with Collision Detection), where devices listen before transmitting and detect collisions in progress. We'll study this protocol in detail later in this chapter.

Wireless LANs (Wi-Fi)

Wireless networks face an even more challenging version of the shared channel problem:

The medium cannot be "owned": Unlike cables that can be physically isolated, radio waves propagate freely through space. Any device within range of an access point shares the same frequency bands.

Collision detection is impossible: While Ethernet devices can detect collisions by monitoring voltage levels while transmitting, wireless devices cannot simultaneously transmit and receive on the same frequency. By the time a wireless device realizes a collision occurred, the entire frame has been transmitted and wasted.

Hidden and exposed terminal problems: Physical obstructions and distance create scenarios where devices cannot accurately sense each other's transmissions. This adds layers of complexity not present in wired networks.

Interference from non-network sources: Microwave ovens, Bluetooth devices, and competing Wi-Fi networks all share the same unlicensed spectrum, creating interference that appears similar to collisions.

Modern Switched Ethernet

Today's Ethernet networks largely eliminate the shared channel problem at the physical layer by using switches that create point-to-point links to each device. Each switch port is a separate collision domain.

However, the shared channel problem hasn't disappeared—it has moved:

• Wireless segments of enterprise networks still share channels
• Virtual LANs (VLANs) create logical shared domains
• Network congestion at switch uplinks creates queuing that resembles contention
• Software-defined networks abstract channel sharing to higher layers

Having built intuition through examples, let's now state the shared channel problem formally. This precise formulation will guide our study of MAC protocols.

System Model

Consider a system with the following characteristics:

1. Shared Broadcast Channel

• N stations (devices) share a single communication channel with capacity C bits/second
• When any station transmits, all other stations can potentially receive the signal
• The channel can carry at most one frame successfully at any instant

2. Station Behavior

• Each station generates frames according to some traffic pattern (random, bursty, constant)
• Stations have buffers to hold frames waiting for transmission
• Stations can sense the channel state (idle, busy, or collision)

3. Physical Constraints

• Propagation delay (τ): Signal takes time to travel between stations
• Transmission time (T): Sending a frame of L bits takes T = L/C seconds
• Detection delay: Receiving stations need time to detect valid frames

4. Collision Semantics

• If two or more frames overlap in time at any receiver, all are corrupted
• Corrupted frames must be retransmitted

The Multiple Access Problem

Given: A shared channel with N stations, each with frames to transmit.

Goal: Design a protocol that:

1. Maximizes throughput: Successful data transmission approaches channel capacity
2. Minimizes collisions: Overlapping transmissions are avoided or quickly resolved
3. Ensures fairness: All stations receive reasonable access over time
4. Bounds delay: Frames don't wait indefinitely for transmission
5. Scales gracefully: Performance degrades acceptably as N increases

Constraints:

• Stations have only local information (they generally cannot know the global state)
• Decisions must be made distributed (no central controller in random access protocols)
• Propagation delay creates uncertainty about current channel state
• Finite buffers mean dropped frames if waiting too long

The Impossibility of Perfection

An important theoretical result: No distributed algorithm can achieve both 100% channel utilization and zero collisions under realistic assumptions (finite propagation delay, independent station decisions).

This is because:

• Achieving zero collisions requires coordination before transmission
• Coordination requires communication, which consumes channel time
• The channel time spent coordinating cannot carry user data

Thus, MAC protocol design is fundamentally about managing tradeoffs: between throughput and delay, between simplicity and efficiency, between fairness and responsiveness.

The shared channel problem is as old as electrical communication itself, but its solutions in computer networking emerged from specific historical contexts.

The ALOHA Network (1971)

The first systematic study of shared channel access came from the University of Hawaii's ALOHANET project, led by Norman Abramson. The goal was to connect computers on different islands using a shared radio channel—there was no way to run cables across the Pacific Ocean.

The original ALOHA protocol was remarkably simple: transmit whenever you have data, and retransmit if no acknowledgment arrives. This simplicity came at a cost—maximum efficiency of only 18.4%. But ALOHANET demonstrated that useful communication was possible on shared channels with distributed random access.

Key insight: You don't need perfect coordination to communicate. If collisions are detected and frames retransmitted, the system eventually succeeds. The question is efficiency, not feasibility.

The Ethernet Revolution (1973-1980s)

Robert Metcalfe at Xerox PARC built on ALOHA's ideas but improved efficiency dramatically with carrier sensing—listening before transmitting. If the channel was busy, a station waited rather than transmitting into a collision.

This simple addition, combined with collision detection (possible on wired media), raised Ethernet's practical efficiency to 90%+ under moderate load. Ethernet became the dominant LAN technology and remains so today.

The Token Ring Alternative

IBM developed Token Ring as an alternative approach using coordinated access. Instead of random transmission with collision resolution, stations passed a special "token" message. Only the station holding the token could transmit.

Token Ring offered:

• Deterministic access: Bounded worst-case delay (important for time-sensitive applications)
• No collisions: The token ensured exclusive access
• Fair distribution: Every station got the token in rotation

However, Token Ring lost the market battle to Ethernet due to:

• Higher cost (more complex hardware)
• Single point of failure (broken ring affected all stations)
• Slower adaptation to higher speeds
• The "good enough" performance of Ethernet for most applications

Modern Wireless Challenges

When wireless LANs emerged in the 1990s, the shared channel problem returned with new complications. Wi-Fi's CSMA/CA protocol addressed wireless-specific challenges, but the fundamental issues remain. Every time you experience slow Wi-Fi in a crowded space, you're witnessing the shared channel problem in action.

Before diving into specific protocols, it's useful to understand that MAC protocols fall into distinct categories based on how they approach channel sharing. We'll study each category in detail throughout this chapter.

Random Access Protocols

Philosophy: Let stations transmit whenever they want. Handle collisions when they occur through detection and retransmission.

Characteristics:

• No central coordination required
• Simple to implement
• Efficient under light load (stations rarely collide)
• Degrades under heavy load (frequent collisions waste capacity)
• Non-deterministic delay (unpredictable wait times)

Examples: Pure ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA

Controlled Access Protocols

Philosophy: Explicitly coordinate access so only one station transmits at a time. Prevent collisions by design.

Characteristics:

• Requires coordination mechanism (token, polling, reservation)
• More complex implementation
• Efficient under heavy load (no collisions)
• May underperform under light load (waiting for permission)
• Deterministic delay (bounded worst-case)

Examples: Polling, Token Passing, Reservation protocols

Channelization Protocols

Philosophy: Divide the channel capacity among stations so each has a dedicated sub-channel.

Characteristics:

• No contention within sub-channels
• Requires knowledge of number of stations
• May waste capacity if station has no data (dedicated slot unused)
• Provides guaranteed bandwidth
• Well-suited for embedded and real-time systems

Examples: FDMA, TDMA, CDMA

We've established the conceptual foundation for understanding Medium Access Control. Let's consolidate the key insights before moving forward:

What's Next

With the shared channel problem clearly defined, we're ready to study how networks solve it. The next page examines the MAC sublayer—its position in the network stack, its responsibilities, and its interface with other layers. Understanding where MAC fits architecturally will help you appreciate how specific protocols integrate into real network implementations.

Subsequent pages will cover:

• Collision concepts in detail: detection, avoidance, and resolution
• MAC protocol categories: random access, controlled access, channelization
• Channel allocation strategies and their mathematical foundations