Multiple Access Protocols

A broadcast channel is a shared medium — a coaxial cable, a radio spectrum band, a fiber tap — where a signal transmitted by one node is received (in principle) by all other nodes attached to it. This differs fundamentally from point-to-point links, where each sender has a private wire to its receiver. Because point-to-point links avoid the access problem entirely, multiple access protocols exist specifically to arbitrate broadcast channels: Ethernet hubs (historically), Wi-Fi, cable access networks (DOCSIS), and satellite uplinks. A multiple access protocol is a distributed algorithm that determines how nodes share the channel. The protocol must solve the problem without the assumption of a global clock synchronizing every bit, and typically without a central arbiter, since broadcast channels connect physically dispersed nodes. Multiple access protocols are judged on several axes: when only one node has data, it should get the full channel rate R; when M nodes have data, each should get a fair share R/M (at least in symmetric settings); the protocol should be decentralized (no single point of failure) and simple to implement in hardware. The three canonical families differ in when they resolve contention. Channel partitioning resolves contention in advance, by construction — each node is statically assigned a slice of time, frequency, or code, so collisions are structurally impossible. Random access resolves contention after the fact — nodes transmit greedily, a collision occurs when two or more transmissions overlap in time on the channel, and the protocol detects (or infers) collisions and drives a retransmission scheme. Taking-turns protocols resolve contention through explicit coordination — a token or a polling message that grants transmission rights to one node at a time, cycling through all nodes.

1. Channel partitioning: TDMA, FDMA, CDMA

Time Division Multiple Access (TDMA) divides time into fixed-length slots, grouped into repeating frames of N slots for N nodes. Node i transmits only in slot i of every frame; if it has nothing to send, the slot is wasted (transmitted as idle). Throughput per node is exactly R/N whenever that node has data, deterministically, with zero collisions.

Frequency Division Multiple Access (FDMA) divides the channel's frequency spectrum into N non-overlapping bands, each of bandwidth R/N, permanently assigned to one node. This is the classical approach in analog cellular systems and cable television.

Code Division Multiple Access (CDMA) assigns each node a unique orthogonal spreading code; all nodes transmit simultaneously over the full bandwidth, and receivers decode using the sender's code, exploiting the orthogonality to reject the "noise" from other senders' encoded signals. CDMA underlies 3G cellular and some satellite systems, trading complex signal-processing hardware for the elimination of both time-slicing and frequency-slicing waste. All three share a mathematical signature: with N active nodes, each gets exactly R/N — a perfectly fair, perfectly deterministic allocation. The cost is rigidity: an idle node's dedicated slot, band, or code capacity cannot be reassigned instantaneously to a busy node.

2. Random access: ALOHA family

Pure ALOHA (Abramson, 1970s, University of Hawaii) is maximally simple: a node with a frame transmits immediately, in full, with no coordination whatsoever. If the frame collides with any other transmission (any temporal overlap), both are lost. After a collision, each colliding sender waits a random backoff time before retransmitting, to avoid perpetually re-colliding in lockstep. ``` ALOHA_send(frame): transmit(frame) # send immediately, full-length wait_for_ack_or_timeout() if collision_or_timeout: backoff = random_uniform(0, T_max) # randomized retransmission delay wait(backoff) ALOHA_send(frame) # retry else: done() # success ```

Slotted ALOHA improves on this by dividing time into slots equal to one frame's transmission time, and requiring all nodes to be slot-synchronized (a modest coordination assumption). A node with a frame waits for the start of the next slot, then transmits the entire frame within that slot. ``` Slotted_ALOHA_send(frame): wait_for_next_slot_boundary() transmit(frame) # fills exactly one slot if collision_detected_in_this_slot: with probability p: retransmit_next_slot() else: wait_one_more_slot_and_retry_with_prob_p() else: done() ``` Slotting halves the "vulnerable window" during which a collision can occur (explained in Complexity & Correctness below), doubling maximum throughput.

3. Random access: CSMA and CSMA/CD

Carrier Sense Multiple Access (CSMA) adds a simple courtesy rule absent from ALOHA: listen before you talk. A node senses the channel; if it is idle, the node transmits; if busy, the node defers. Because of propagation delay, two distant nodes can both sense "idle" and transmit almost simultaneously, still colliding — CSMA reduces but does not eliminate collisions.

CSMA with Collision Detection (CSMA/CD) — the protocol underlying classic (bus/hub) Ethernet — adds two more rules: listen while talking (detect a collision by observing garbled or excessive-current signal on the wire), and abort immediately upon detecting one, instead of wasting the rest of the frame's transmission time. ``` CSMA_CD_send(frame): loop: while channel_is_busy(): wait() # persistent carrier sense transmit(frame) while transmitting: if collision_detected(): send_jam_signal() # ensure all parties notice abort_transmission() n = n + 1 # collision counter k = min(n, 10) r = random_integer(0, 2^k - 1) # binary exponential backoff wait(r 512_bit_times) continue loop # retry from the top return SUCCESS ``` The <strong>binary exponential backoff</strong> scheme is the crucial ingredient: after the n*-th consecutive collision on a frame, the sender picks a random wait r uniformly from {0, 1, …, 2^min(n,10) − 1} slot times (512 bit-times in classic Ethernet), then retries. As collisions repeat, the contention window doubles, spreading out competing senders and making convergence to a collision-free transmission increasingly likely.

4. Taking-turns protocols: polling and token passing

Polling designates one node as a "master" that cycles through the others, asking each in turn "do you have data?" Only the polled node may transmit, briefly, before control returns to the master. This eliminates collisions and idle-slot waste but introduces polling overhead (the round-trip cost of each poll) and a single point of failure (the master).

Token passing removes the central master: a special control frame, the token, circulates node-to-node around a logical (or physical) ring. Only the node currently holding the token may transmit; it then passes the token onward. Token Ring and FDDI are the classical examples. ``` Token_ring_node(my_id, ring_order): loop: token = wait_for_token() if have_data_to_send(): transmit(frame) wait_for_frame_to_circulate_back() pass_token(next_node_in(ring_order)) ```

Channel partitioning is trivially correct: because slots, frequencies, or codes are disjoint by construction, no two nodes ever transmit in the same slice, so collisions are structurally impossible. This is an invariant enforced by the static allocation itself, not by any runtime detection. The efficiency cost is equally structural: with N nodes and only M < N active, the N − M idle nodes' allocations go completely unused, so throughput can fall to M·R/N even though demand could in principle saturate the channel. Time complexity per transmission is O(1) (no contention resolution needed); the "cost" instead shows up as wasted capacity, which we quantify below for TDMA: if nodes are active independently with probability q, a node's average wait for its own slot is (N−1)/2 slots regardless of load — a fixed latency floor even when the channel is otherwise empty.

Pure ALOHA's throughput is derivable exactly using a Poisson traffic model. Let frames be generated by all nodes combined according to a Poisson process with aggregate rate G frames per frame-transmission-time (this rate G includes original arrivals plus retransmissions — it is the offered load). A given frame, transmitted at time t, collides if any other frame starts anywhere in the interval (t − 1, t + 1) frame-times — a vulnerable period of length 2 frame-times, because a frame starting up to one frame-time before t is still transmitting when t's frame begins, and a frame starting up to one frame-time after t begins overlaps it too. The probability that zero other frames arrive in an interval of length τ frame-times, under a Poisson process of rate G, is: ``` P(0 arrivals in τ) = e^(−Gτ) ``` For pure ALOHA, τ = 2, so the probability a given frame survives without collision is e^(−2G). Throughput (successful frames per frame-time) is offered load times survival probability: ``` S = G · e^(−2G) ``` Maximizing over G: differentiate, set dS/dG = 0: ``` dS/dG = e^(−2G) − 2G·e^(−2G) = e^(−2G)(1 − 2G) = 0 ⟹ G = 1/2 ``` Substituting back: ``` S_max = (1/2) · e^(−1) = 1/(2e) ≈ 0.184 ``` So pure ALOHA's maximum achievable throughput is about 18.4% of channel capacity, even with an ideal choice of offered load — a striking, non-obvious result showing that greedy uncoordinated access wastes over 80% of capacity at best.

Slotted ALOHA halves the vulnerable period to exactly 1 frame-time, because two frames can only collide if they start in the same slot (arrivals are aligned to slot boundaries). Setting τ = 1: ``` S = G · e^(−G) dS/dG = e^(−G)(1 − G) = 0 ⟹ G = 1 S_max = 1 · e^(−1) = 1/e ≈ 0.368 ```

Slotted ALOHA doubles pure ALOHA's peak efficiency to about 36.8% — the single most quoted result in multiple access theory, and a clean illustration of how a small amount of coordination (slot synchronization) buys a large efficiency gain.

CSMA/CD's efficiency depends on the ratio of propagation delay to transmission time. Let d_prop be the maximum one-way propagation delay across the network and d_trans the time to transmit a full frame. The vulnerable period for a collision to occur despite carrier sensing is bounded by d_prop (a distant node may sense idle just before a transmission's leading edge arrives). A standard approximation for CSMA/CD efficiency under N persistently-backlogged senders is: ``` efficiency ≈ 1 / (1 + 5 · (d_prop / d_trans)) ``` This shows why classic Ethernet enforces a minimum frame size of 64 bytes: it must guarantee d_trans ≥ 2·d_prop (round-trip propagation) so that a sender is still transmitting when a collision signal could return, guaranteeing every collision is detected during transmission rather than after a node believes it has already succeeded. Correctness here means: no node ever finishes transmitting a frame and considers it successful when in fact a collision occurred — the minimum frame size closes this gap given the network's maximum physical extent.

Binary exponential backoff's correctness argument is a stability/fairness one, not a strict optimality proof: as repeated collisions occur, doubling the contention window exponentially reduces the probability that the same k competing senders pick overlapping backoff slots again, so the expected number of retries to reach a successful transmission is bounded, and the scheme adapts automatically to the (unknown, possibly changing) number of contending nodes — heavier contention is met with proportionally larger randomization range, which is precisely the self-tuning behavior a static backoff constant cannot achieve.

Taking-turns protocols guarantee both no collisions (like partitioning) and full utilization when only one node is active (like random access, but deterministically), at the cost of O(N) latency per round in polling (each of N nodes must be asked even if only one has data) and vulnerability to failure of the token or the master — a lost token requires a timeout-based regeneration protocol, an engineering complication absent from the collision-based schemes.

Consider a small Ethernet segment with N = 4 hosts (A, B, C, D) sharing one CSMA/CD bus, offered load causing repeated contention. Frame transmission time is 10 time units; propagation delay is negligible (small LAN) so we focus on the collision/backoff mechanics rather than the vulnerable-window derivation above.

This trace illustrates three properties proven above: (1) the first collision is essentially certain when all nodes start with data simultaneously (an adversarial but realistic "burst" scenario e.g. after a network partition heals); (2) binary exponential backoff spreads contenders across an exponentially growing window, so D succeeds after only 2 rounds while B and C need more rounds because they happened to draw the same value; (3) the protocol is self-correcting — no central authority decided that D should go first, yet the randomized backoff converged to a collision-free schedule within a small, bounded number of rounds with high probability.

Contrast with slotted ALOHA on the same scenario: with p = 1/4 (retransmission probability tuned for N = 4 to approximate the optimal G = 1), each node, once holding a frame, retransmits in each slot independently with probability p. The expected number of slots until a specific frame succeeds (given no new arrivals) is 1/p = 4 slots on average — comparable in order of magnitude to CSMA/CD's backoff rounds above, but ALOHA burns full slots on every collision (no carrier sensing to detect a doomed transmission early), whereas CSMA/CD's jam-and-abort mechanism wastes only a fraction of a slot per collision, which is precisely why Ethernet outperforms ALOHA in practice despite both being random-access protocols.

Classic (hub-based) Ethernet used CSMA/CD directly on a shared coaxial or twisted-pair bus; understanding its collision dynamics explains historical Ethernet's minimum frame size and the reason modern switched Ethernet, which gives each link a dedicated collision domain, eliminated the need for CSMA/CD almost entirely (a preview of Ethernet and the Frame Format). Wi-Fi (IEEE 802.11) uses CSMA/CA (Collision Avoidance) rather than CSMA/CD, because a wireless transmitter cannot reliably listen for collisions on its own outgoing signal (its own transmission drowns out any incoming interference at the antenna) — it instead uses random backoff before transmitting and optional RTS/CTS handshakes, directly descended from the ALOHA/CSMA lineage developed here. Cable modem networks (DOCSIS) combine TDMA-style time slots for upstream transmission with contention-based "request" slots resembling slotted ALOHA. Cellular networks use CDMA (3G) or scheduled OFDMA resource blocks (4G/5G, an evolved form of channel partitioning) for the data channel, paired with a random-access channel (based on slotted ALOHA) purely for a device's initial connection request. Token-based industrial networks (e.g., some fieldbus protocols in factory automation) still favor taking-turns designs where bounded worst-case latency matters more than peak throughput. Understanding these three families — and the throughput math behind them — is the foundation for reasoning about capacity, fairness, and latency in every shared-medium network layered above the physical layer, directly connecting to Delay, Loss, and Throughput in Packet Networks when analyzing real link performance.

Ask the tutor: How does the CSMA/CD efficiency formula change if propagation delay is comparable to or larger than transmission time, and why does this make CSMA/CD impractical for long-distance or satellite links?