№ 132 · networks

How does Wi-Fi share one room?

Devices on one Wi-Fi channel all share it. The surprise is that under DCF, the fundamental access method in the 802.11 standard these sources describe, nobody hands out turns (an optional mode, PCF, lets the access point poll stations). Each device listens, waits a random amount of time, and transmits when its timer runs out. When two timers run out together, both packets are lost and both devices back off longer. The sources date from 2002 and 2010 and do not cover later Wi-Fi generations.

Listen first, then wait

Snoeren describes the method as carrier sense multiple access with collision avoidance, CSMA/CA. A station that senses the channel idle transmits its whole packet. If the channel is busy it defers. Wu, Cheng, Peng, Long and Ma give the details: a station may transmit once the medium has been idle for an interval called DIFS, the DCF inter-frame space. If the medium was busy, it waits for DIFS and then draws a random backoff.

Why it cannot just detect collisions

Snoeren notes that half-duplex radios cannot detect collisions. Wu and colleagues add that 802.11 does not use collision detection (CSMA/CD) because a station cannot listen to the channel while transmitting. So collisions are avoided rather than caught. The backoff timer counts down only while the channel is idle, freezes when the channel is busy, and resumes after another DIFS. A station transmits when the counter reaches zero.

Predict first

Two stations pick backoff timers and both count down. Station A's timer reaches zero first and it starts sending. What happens to station B's timer?

Check your answer

It freezes. Wu and colleagues state the counter is decreased while the channel is idle, frozen when busy, and resumed once the channel is idle again for more than DIFS.

The window that grows

The random draw is uniform over a range called the contention window, CW. After each unsuccessful transmission the window doubles, up to a maximum. Wu and colleagues give the values for the direct-sequence spread spectrum physical layer: CWmin is 31 and CWmax is 1023. Strictly it is CW+1 that doubles, so CW runs 31, 63, 127, 255, 511, 1023. Snoeren puts it plainly: a node that fails to receive a clear-to-send reply doubles its CW up to an upper bound, and a node that completes a transfer restores CW to its minimum. A wider window spreads the draws further apart, so retries collide less often.

The hidden terminal

Carrier sense only reaches as far as a radio can hear. Snoeren describes the hidden terminal problem: B can talk to both A and C, but A and C cannot hear each other. When A transmits to B, C senses nothing and may transmit too, and the two collide at B. The fix is a four-way exchange: request-to-send, clear-to-send, data, acknowledgement. A sends the request-to-send, B replies with clear-to-send, and any station that overhears the CTS stays quiet for the duration carried in the frame. Wu and colleagues note the cost: the extra frames add overhead for short data frames.

Interactive Press run a slot to let every station count down one slot, or send a packet to run until the next attempt. Change the number of stations to see how often attempts collide.

Each station draws a backoff counter uniformly from 0 to CW. Counters fall by one per slot while the channel is idle; the first to reach zero transmits. If two or more reach zero in the same slot, all their packets are lost, each of their windows doubles (up to CWmax), and new counters are drawn. A success resets the window to CWmin. The readout counts attempts, collisions and successes for the current number of stations.

What one paper proposed

Wu and colleagues argued that the standard's reset rule wastes work: the backoff can be seen as a search for the best window size, and resetting CW to its minimum after every success breaks that search. They proposed a more conservative scheme that halves the window on success, doubles it on failure, and keeps it when the retry limit is reached. Their model predicts higher throughput, and they report simulations agreeing, though the model slightly overestimates because broadcast routing packets reset the window. In 2002 this was a proposal, not the standard; these sources do not say whether it was adopted.

In short

One channel, many stations, and under DCF no scheduler. Each station listens, waits a random backoff that freezes while the channel is busy, and doubles its window after a failure. A request-to-send and clear-to-send exchange covers the stations that carrier sense cannot reach.

Where this comes from

  1. CSE 123 Lecture 16: QoS and 802.11 linked only, not reproduced
    Snoeren · 2010
    web.archive.org/web/20240728062206/cseweb.ucsd.edu/classes/fa10/cse123/lectures/123-fa10-l16.pdf
  2. IEEE 802.11 Distributed Coordination Function (DCF): Analysis and Enhancement linked only, not reproduced
    Wu, Cheng, Peng, Long, Ma · 2002
    www.cs.nccu.edu.tw/~ttsai/mobilecomm_ttsai/papers/0605wu.pdf