Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 79 ยท Data Link Layer

Medium Access Control

Learn how stations share one channel: ALOHA, slotted ALOHA, CSMA, CSMA/CD with backoff, CSMA/CA and token passing, with efficiency formulas and live Python.

When many stations share one channel (a radio band, a coax cable, a hub) and two of them talk at once, their signals overlap and both transmissions are garbage. That overlap is a collision. Someone has to decide who may transmit and when. The rules that settle this are called medium access control (MAC), and they live in the lower half of the data link layer.

There are three families of answers. Channel partitioning gives each station a fixed share of time, frequency or code, as in the TDM and FDM schemes from Multiplexing and Physical Devices. It never collides but wastes capacity when stations are idle. Random access lets stations transmit when they want and recovers from collisions. Controlled access takes turns, using a token or polling. This lesson focuses on random access, the family behind classic Ethernet and Wi-Fi, and ends with token passing.

ALOHA

ALOHA was built in the early 1970s to connect the Hawaiian islands by radio, and it is the simplest idea imaginable: transmit whenever you have a frame. If the frame is acknowledged, great. If not, assume a collision, wait a random time and try again. The random wait is essential; if two colliding stations waited the same fixed time they would collide forever.

A frame is vulnerable for a long period. With frame time T, any other frame that starts in the window from T before to T after the start of yours overlaps with it, so the vulnerable time is 2T. If the network offers on average G frames per frame time (including retransmissions), the chance that nobody else starts in a 2T window is e-2G, and the throughput is

S = G ยท e-2G, with a maximum of 1 / (2e) โ‰ˆ 18.4% at G = 0.5.

Past that point, more traffic means more collisions and less useful throughput.

Slotted ALOHA

Divide time into slots one frame long and make stations start only at slot boundaries. Two frames now either collide completely or not at all. The vulnerable time halves to T, so

S = G ยท e-G, with a maximum of 1 / e โ‰ˆ 36.8% at G = 1.

The cost is that stations need a common clock to know where the slots are.

Python ALOHA throughput: simulation against theory

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulated columns land very close to the formulas, and you can see the shape: throughput rises, peaks and then falls as load grows. The simulation treats the offered load as a stream of random frame starts, which is the standard model behind these formulas.

CSMA: listen before you talk

ALOHA ignores what everyone else is doing. CSMA (Carrier Sense Multiple Access) adds the obvious improvement: listen first. If the channel is busy, wait. Collisions are still possible, because two stations can both hear silence and start within the signal's propagation time, before either one's signal has reached the other. The longer the cable relative to the frame, the worse it gets. Variants differ in what a station does when it finds the channel busy:

  • 1-persistent: keep listening and transmit the instant the channel goes idle. Best utilization when load is low, but two waiting stations will certainly collide.
  • Non-persistent: if busy, wait a random time and then listen again. Fewer collisions, more idle gaps.
  • p-persistent (slotted channels): when idle, transmit with probability p, otherwise defer one slot.

CSMA/CD: detect the collision

On a wired medium, a station can listen while it transmits. CSMA/CD (collision detection) uses that: if the signal on the wire differs from what the station is sending, a collision is happening. The station stops at once, sends a short jam signal so everyone notices, and backs off. Aborting early saves the time of a whole wasted frame. Classic shared Ethernet used exactly this.

flowchart TD
    A["Frame ready"] --> B{"Channel idle?"}
    B -- "no" --> B
    B -- "yes" --> C["Transmit and listen"]
    C --> D{"Collision?"}
    D -- "no" --> E["Done"]
    D -- "yes" --> F["Send jam signal"]
    F --> G["Wait random backoff"]
    G --> B

CSMA/CD in one loop: sense, send, watch for collisions, jam, back off, try again.

Binary exponential backoff

After the n-th collision of a frame, a station picks a random number k from 0 to 2n - 1 and waits k slot times. (Ethernet caps the exponent at 10 and gives up after 16 attempts.) The range doubles with every collision, so the more crowded the channel, the further stations spread out. Two stations that collide have a 50% chance of picking different numbers on the first retry.

Why Ethernet has a minimum frame size

To detect a collision the sender must still be transmitting when the evidence comes back. In the worst case the other end of the cable is Tp away, and the collision signal needs another Tp to return, so the frame must last at least 2ยทTp. Ethernet fixed the slot time at 51.2 ยตs, which at 10 Mbit/s is 512 bits, or 64 bytes. Shorter frames are padded. We return to this in Ethernet and Frames.

The efficiency of CSMA/CD, ignoring details, is roughly 1 / (1 + 6.44a), where a = Tp / Tt as in Flow Control and ARQ. Efficiency is high when frames are long and cables are short.

Python Backoff rounds and CSMA/CD efficiency

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

About half of all collisions are settled on the very next try, and the odds fall off fast with each doubling. The efficiency lines show that long cables and short frames are a bad pair: with 512-bit frames over 2,500 m, efficiency drops below 40%, but with full-size frames it is above 90%.

CSMA/CA: avoid the collision

Radio cannot do collision detection. A transmitter's own signal is billions of times stronger than the signal arriving from a far station, so it cannot hear a collision while it sends. Wireless also has the hidden terminal problem: two stations may both reach the access point but not each other, so neither hears the other's transmission. CSMA/CA (collision avoidance), used by Wi-Fi, therefore tries not to collide in the first place:

  1. Sense the channel. When it has been idle for a short interframe space (DIFS), pick a random backoff counter.
  2. Count the counter down only while the channel stays idle; pause it during other stations' transmissions.
  3. When it reaches zero, transmit the frame.
  4. The receiver answers with an ACK. No ACK means a collision (or other loss) and the contention window is doubled before the next attempt.

For hidden terminals, a station can first send a short RTS (request to send), and the access point replies with a CTS (clear to send) that everyone nearby hears and obeys by staying quiet. The extra handshake costs time, so it is used mainly for long frames. Wi-Fi and 802.11 covers the details.

Controlled access: tokens and polling

Instead of competing, stations can take turns.

  • Token passing: a small special frame, the token, circulates around a logical ring. Only the holder may transmit, for a limited time, then passes the token on. Token Ring (IEEE 802.5) and FDDI worked this way. There are no collisions and the worst-case wait is bounded, which suits real-time systems, but a lost token or a failed station needs recovery logic.
  • Polling: a controller asks each station in turn whether it has anything to send. Bluetooth and some industrial buses use this.

At light load, random access has lower delay because you transmit immediately; at heavy load, controlled access wins because it never wastes time on collisions.

Method Collisions Good when Examples
Pure ALOHA Frequent Very light load Early radio networks
Slotted ALOHA Fewer Light load, shared clock Satellite and RFID reservation
CSMA/CD Detected, then retried Wired shared cable Classic Ethernet
CSMA/CA Avoided, ACK to confirm Radio Wi-Fi
Token passing None Heavy, real-time load Token Ring, FDDI

Modern wired Ethernet has retired CSMA/CD almost completely. Switches give every device its own full-duplex link, so there is nothing to collide with, as explained in Switches, Bridges and MAC Learning.

Limits of the random-access methods

The methods above are simple and need no central control, but each one pays a price.

  • Pure ALOHA transmits whenever a station has data, with no coordination, so any two overlapping frames collide. The vulnerable time is two frame times and the best efficiency is about 18 percent. Collisions get worse as load grows, and delay is unpredictable.
  • Slotted ALOHA doubles the best efficiency to about 37 percent by letting stations start only at slot boundaries, but it needs synchronized clocks, and a frame that arrives mid-slot must wait, which adds delay.
  • CSMA persistence modes decide what to do when the channel is busy. 1-persistent: keep listening and send the moment it is free (fast, but if two stations are waiting they always collide). Non-persistent: wait a random time and listen again (fewer collisions, more idle time). p-persistent (slotted channels): when the channel is free, send with probability p, otherwise wait for the next slot, a compromise between the two.
  • CSMA/CD has limits too. The network length and speed are tied by the minimum frame size, so it does not scale to long, fast links. Under heavy load collisions and backoff waste bandwidth, an unlucky station may wait a long time (and gives up after 16 attempts), and a station that deliberately ignores the rules can degrade a shared segment. Switched full-duplex Ethernet removed collisions altogether, which is why CSMA/CD is now mostly history.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is the maximum throughput of slotted ALOHA twice that of pure ALOHA?

    In slotted ALOHA, frames can only start at slot boundaries, so they either collide completely or not at all. The window in which another frame can interfere is T instead of 2T, which moves the peak from 18.4% to 36.8%.
  2. 2. A station sensing a collision in CSMA/CD does what?

    Stopping early saves channel time; the jam signal makes sure all stations notice, and the random backoff prevents the same stations from colliding again at once.
  3. 3. After the third collision of a frame, binary exponential backoff picks the wait from which range of slots?

    After the n-th collision the range is 0 to 2^n - 1. For n = 3 that is 0 to 7.
  4. 4. Why does Wi-Fi use collision avoidance rather than collision detection?

    A transmitter's own signal drowns out everything else, so it cannot detect a collision. Stations that cannot hear each other also cause collisions the sender will never notice, which is why Wi-Fi uses backoff, ACKs and optional RTS/CTS.

Summary

  • MAC rules decide who may use a shared channel; the families are channel partitioning, random access and controlled access.
  • Pure ALOHA peaks at about 18.4% throughput (S = Gยทe-2G); slotted ALOHA at about 36.8% (S = Gยทe-G).
  • CSMA listens before sending; CSMA/CD also detects collisions, jams and backs off exponentially, which needs a minimum frame time of 2ยทTp (64 bytes in Ethernet).
  • CSMA/CA avoids collisions with random backoff, ACKs and optional RTS/CTS, because radios cannot detect collisions.
  • Token passing and polling take turns, avoiding collisions and giving bounded delay.

Next: Ethernet and Frames