Computer Networking › Section F · The link layer and LANs › Topic F.3
Multiple access links and protocols
When many nodes share one channel, two transmissions at once ruin each other. A multiple access protocol is the set of rules that decides who may speak, trading fairness, efficiency and simplicity.
The shared-channel problem
On a broadcast link every node hears every transmission, and when two frames overlap in time at a receiver they collide and both are lost. A multiple access protocol is distributed: nodes follow common rules, with no referee. For a channel of rate \(R\) bit/s, a good protocol gives a lone active node the full rate \(R\), gives each of \(M\) active nodes about \(R/M\) on average, needs no central controller or synchronised clocks, and stays simple. The designs fall into three families: channel partitioning, random access and taking turns.
Channel partitioning
Time-division multiple access (TDMA) gives each node a fixed slot in a repeating cycle. Frequency-division multiple access (FDMA) gives each node its own frequency band. Code-division multiple access (CDMA) gives each node its own code. None can collide, and each node's share is guaranteed. The weakness is waste. With 4 nodes sharing 100 Mbit/s, each owns 25 Mbit/s, and a node with a large file to send stays at 25 Mbit/s even when the other three are silent, while their slots go unused.
Slotted ALOHA
Random access protocols let a node transmit at full rate whenever it has a frame and repair collisions afterwards. In slotted ALOHA, time is cut into slots exactly one frame long, all nodes are synchronised, and a node only starts at a slot boundary. If it has a frame, it transmits in the next slot. After a collision it retransmits in each later slot with probability \(p\), independently. Assume \(N\) nodes always have frames waiting, each transmitting with probability \(p\). A slot succeeds only if exactly one does:
This peaks at \(p = 1/N\), and as \(N\) grows it approaches \(1/e \approx 0.368\).
Worked example: slotted ALOHA
Ten nodes each transmit in a slot with probability \(p = 0.1\). 1. Success needs exactly one transmitter: \(10 \times 0.1 \times 0.9^9 \approx 0.387\). 2. A slot is idle when nobody transmits: \(0.9^{10} \approx 0.349\). 3. Everything else is a collision: \(1 - 0.387 - 0.349 \approx 0.264\). 4. On a 100 Mbit/s channel, about 38.7 Mbit/s of frames get through, and the rest of the capacity is lost to idle slots and collisions. A computer simulation of 200,000 slots gives a success rate close to 0.39, agreeing with the formula. Trying \(p = 0.3\) with the same ten nodes gives only 0.121: transmitting more eagerly makes things worse.
Pure ALOHA
ALOHA, developed at the University of Hawaii around 1970 to link computers over radio, needs no slots or synchronisation: a node transmits the moment a frame arrives. The price is a longer window of vulnerability. A frame collides with any other frame that starts during its own transmission, or during the frame time just before it, so the dangerous period is two frame times instead of one. The best efficiency drops to \(1/(2e) \approx 0.184\), half the slotted figure. Hearing the channel before speaking was the next improvement.
Carrier sensing and CSMA/CD
Carrier sense multiple access (CSMA) adds courtesy: listen first and stay quiet if the channel is busy. Collisions still occur, because a signal takes time to travel, so two nodes can both find the channel idle and start. With collision detection (CSMA/CD), a node keeps listening while it sends. If it hears interference it stops at once, which saves wasting a whole frame, sends a short jam signal so that everyone notices, and waits a random time. Classic shared Ethernet worked this way; the Computer Science topic Network fundamentals gives the first look, and radio cannot do it, as the topic Wireless LANs: 802.11 explains.
Binary exponential backoff
After the \(n\)th collision on a frame, an Ethernet node picks \(K\) at random from \(\{0, 1, \ldots, 2^m - 1\}\), where \(m = \min(n, 10)\), and waits \(K\) slot times before sensing again. A slot time is 512 bit times, which is 51.2 µs at 10 Mbit/s. The node gives up after 16 attempts. Doubling the range adapts to the load: few contenders resolve quickly, while many contenders quickly spread out. The 512-bit slot matches the minimum Ethernet frame of 64 bytes, long enough that the sender is still transmitting when news of a collision comes back.
Worked example: backoff in numbers
Two stations collide on their first attempt. 1. Each picks \(K\) from \(\{0, 1\}\), so they pick the same value, and collide again, with probability \(1/2\). 2. After a second collision the range is \(\{0, \ldots, 3\}\), and a repeat has probability \(1/4\). 3. After a third it is \(\{0, \ldots, 7\}\), and a repeat has probability \(1/8\). 4. Colliding on all of the next three attempts has probability \(\tfrac12 \times \tfrac14 \times \tfrac18 = 1/64\). 5. After a fourth collision \(K \le 15\), so the longest wait is \(15 \times 51.2 = 768\) µs. From the tenth collision on, \(K \le 1023\), at most about 52 ms.
Taking turns
Taking-turns protocols avoid both waste and collisions. In polling, one controlling node invites each of the others to send in turn, as the central device does in Bluetooth, at the cost of polling overhead, added delay, and a single point of failure. In token passing, a small token frame circulates, and only the holder may send, as in the old Token Ring network; a lost token or a failed node needs recovery. Cable internet (DOCSIS) mixes ideas: a headend grants upstream time slots, and modems ask for them in contention slots using random access with binary exponential backoff. Modern switched Ethernet needs none of this, as Switched LANs: MAC addresses, ARP, switches, and VLANs shows.
Common mistakes to avoid
First, treating ALOHA's 37% as a limit for every random-access protocol; it is the best case for slotted ALOHA with many nodes. Second, forgetting that carrier sensing does not remove collisions, because of propagation delay. Third, taking the backoff range as 1 to \(2^n\) slots instead of 0 to \(2^n - 1\); zero is allowed, meaning retry at once. Fourth, saying channel partitioning is wasteful always; it wastes capacity only when some nodes have nothing to send. Fifth, claiming that switched full-duplex Ethernet still uses CSMA/CD in practice.
Key takeaways
Shared links need multiple access protocols. TDMA, FDMA and CDMA partition the channel fairly but waste idle shares. Slotted ALOHA succeeds with probability \(Np(1-p)^{N-1}\), at best about 37%, and pure ALOHA about 18%. CSMA/CD listens before and during transmission, then backs off exponentially: the range is 0 to \(2^m - 1\) slots with \(m = \min(n, 10)\). Polling and token passing take turns, and DOCSIS combines scheduled slots with random-access requests.
Flashcards
Flashcard
Two overlapping transmissions that destroy each other
Test your understanding
Question 1 of 5
In slotted ALOHA, five nodes each transmit in a slot with probability 0.2. What is the probability that a given slot carries a successful frame?
Question 2 of 5
Why is the best efficiency of pure ALOHA only about half that of slotted ALOHA?
Question 3 of 5
On 10 Mbit/s Ethernet a slot time is 51.2 µs. After a station's fourth collision on the same frame, what is the longest it can wait before sensing again?
Question 4 of 5
Five nodes share a 100 Mbit/s channel using TDMA. Only one node has data to send. What rate can it achieve?
Question 5 of 5
Why can two nodes that use carrier sensing still collide?
