14.2 Random Access Protocols

Random Access Protocols

Random access protocols let multiple devices share a single communication channel without any central coordinator telling them when to transmit. They're the foundation of technologies like Ethernet and Wi-Fi. The core challenge: when devices transmit independently, collisions happen. These protocols differ in how they prevent, detect, and recover from those collisions.

Principles of Random Access

In a random access scheme, each device decides on its own when to send data. No one is in charge of scheduling. This creates a few fundamental problems:

• Collisions occur when two or more devices transmit at the same time, corrupting both frames.
• Fairness becomes tricky since there's no guarantee every device gets equal access.
• Scalability degrades as more devices join the channel, increasing collision likelihood.

The goal of every random access protocol is to maximize throughput (successful use of the channel) while keeping delay low and collisions rare. Different protocols make different tradeoffs among these goals.

Operation of ALOHA Protocols

Pure ALOHA

Pure ALOHA is the simplest random access protocol. A device transmits whenever it has data ready. That's it.

1. A device with a frame to send transmits immediately.
2. It waits for an acknowledgment from the receiver.
3. If no acknowledgment arrives (meaning a collision likely occurred), the device waits a random backoff time and retransmits.

The vulnerability window is the problem. A frame of duration $t$ can collide with any other frame that starts transmitting within $2t$ of its own start time (the frame before it could overlap the tail, and the frame after it could overlap the head). This wide window is why Pure ALOHA's throughput is so low.

• Strengths: Dead simple to implement, no synchronization needed, low delay when traffic is light.
• Weaknesses: High collision probability under load, poor throughput when many devices are active.

Slotted ALOHA

Slotted ALOHA improves on Pure ALOHA by dividing time into fixed-length slots, each exactly one frame long. Devices can only begin transmitting at the start of a slot.

1. A device with a frame to send waits until the next slot boundary.
2. It transmits the frame at the start of that slot.
3. If a collision occurs (another device chose the same slot), the device waits a random number of slots before retransmitting.

By forcing transmissions to align, the vulnerability window shrinks from $2t$ to just $t$. A collision only happens when two devices pick the same slot, not when their frames partially overlap.

• Strengths: Doubles the maximum throughput compared to Pure ALOHA.
• Weaknesses: Requires all devices to be synchronized to slot boundaries, which adds complexity. Collisions still happen when multiple devices choose the same slot.

Performance Metrics

Throughput is the key metric. It measures the fraction of channel capacity used for successful (collision-free) transmissions.

• Pure ALOHA peaks at $S = \frac{1}{2e} \approx 0.184$, meaning only about 18.4% of the channel carries successful data at best.
• Slotted ALOHA peaks at $S = \frac{1}{e} \approx 0.368$, roughly 36.8% of channel capacity.

Both maxima occur at a specific offered load ($G = 0.5$ for Pure ALOHA, $G = 1.0$ for Slotted ALOHA). Beyond that optimal load, throughput actually decreases because collisions dominate and retransmissions create even more traffic, a feedback loop that can cause instability.

Collision probability rises with the number of active devices and the traffic load. The retransmission strategy matters too: a poorly chosen backoff algorithm can make congestion worse instead of better.

Comparison of Random Access Protocols

CSMA: Carrier Sense Multiple Access

CSMA protocols add a "listen before you talk" step that ALOHA lacks entirely. A device senses the channel before transmitting. If the channel is busy, it defers.

• CSMA/CD (Collision Detection) is used in wired networks like Ethernet. Devices listen while transmitting. If they detect a collision in progress, they abort immediately and back off, saving time that would otherwise be wasted finishing a corrupted frame.
• CSMA/CA (Collision Avoidance) is used in wireless networks like Wi-Fi. Wireless devices can't easily detect collisions during transmission, so CSMA/CA tries to prevent them using mechanisms like RTS/CTS (Request to Send / Clear to Send) handshakes and random backoff before transmitting.

CSMA protocols achieve significantly higher throughput than ALOHA variants because sensing the channel eliminates many collisions before they happen. However, they introduce their own problems:

• The hidden terminal problem occurs when two devices can't hear each other but both transmit to the same receiver, causing a collision the sender can't detect.
• The exposed terminal problem occurs when a device unnecessarily defers because it hears a nearby transmission that wouldn't actually cause a collision at the intended receiver.
• Carrier sensing adds overhead and doesn't eliminate collisions entirely, especially when propagation delay is significant (a device might sense the channel as idle while another device's signal is still traveling toward it).