Godfrey Tan, John Guttag
10 min
This 2005 paper by Godfrey Tan and John Guttag from MIT tackles a critical performance issue in 802.11 wireless LANs (WLANs), especially 802.11b networks. In these networks, devices transmit at varying data rates (1, 2, 5.5, or 11 Mbps) due to fluctuating indoor channel conditions like signal strength and bit error rates. The standard MAC protocol, Distributed Coordination Function (DCF), aims for 'fairness' by giving each node equal transmission opportunities—but this backfires in multi-rate scenarios, slashing aggregate throughput. The authors propose time-based fairness as a superior alternative and introduce the Time-based Regulator (TBR), an AP-side algorithm that enforces it without changing client hardware.
Why it matters: As WLANs grew congested in the early 2000s, rate diversity became rampant (e.g., workshop traces showed bytes split across rates). Legacy fairness hurt fast nodes, discouraging upgrades to faster standards like 802.11g. This work shows how redefining fairness boosts efficiency while protecting slow nodes.
DCF, the core 802.11 access method, uses CSMA/CA to grant contending nodes roughly equal chances to transmit a packet, regardless of rate. With similar packet sizes and rates, this yields throughput-based fairness—equal bandwidth per node, which feels intuitive.
But rate diversity breaks it:
Intuition: Imagine a highway where slow trucks get equal 'turns' to enter as sports cars. Cars idle behind trucks, wasting capacity. DCF prioritizes equal slots over equal time, inefficient when speeds vary.
The fix: Allocate equal channel occupancy time to each node, not equal attempts.
Benefits:
TBR runs on the Access Point (AP), regulating downlink traffic (common bottleneck) compatibly with any MAC, including DCF.
Experiments on real 802.11b hardware confirm TBR achieves time-based fairness, restoring fast-node throughputs without harming slow ones. Aggregate gains are significant in congested, diverse-rate settings.
This challenges 'fairness' assumptions in shared media. Time-based > throughput-based for efficiency in heterogeneous systems. Influences later WiFi (e.g., 802.11n/ac airtime fairness modes). Fluid models aid analysis of queueing with variable service rates. Core lesson: Fairness notions must align with resource (time vs. bits) for optimal performance.
The performance seen by individual clients on a wireless local area network (WLAN) is heavily influenced by the manner in which wireless channel capacity is allocated. The popular MAC protocol DCF (Distributed Coordination Function) used in 802.11 networks provides equal long-term transmission opportunities to competing nodes when all nodes experience similar channel conditions. When similar-sized packets are also used, DCF leads to equal achieved throughputs (throughput-based fairness) among contending nodes. Because of varying indoor channel conditions, the 802.11 standard supports multiple data transmission rates to exploit the trade-off between data rate and bit error rate. This leads to considerable rate diversity, particularly when the network is congested. Under such conditions, throughput-based fairness can lead to drastically reduced aggregate throughput. In this paper, we argue the advantages of time-based fairness, in which each competing node receives an equal share of the wireless channel occupancy time. We demonstrate that this notion of fairness can lead to significant improvements in aggregate performance while still guaranteeing that no node receives worse channel access than it would in a single-rate WLAN. We also describe our algorithm, TBR (Time-based Regulator), which runs on the AP and works with any MAC protocol to provide time-based fairness by regulating packets. Through experiments, we show that our practical and backward compatible implementation of TBR in conjunction with an existing implementation of DCF achieves time-based fairness.
Sam: Exactly. In their model, total throughput is the sum of each device's share of time multiplied by its own max speed when alone. With equal time fractions, fast devices multiply their high speed by that share, boosting the network total significantly. The paper tests this in fluid models where data streams endlessly, and task models with fixed data jobs, where average completion time drops under time fairness.
Alex: So no one finishes worse off, but the group gets done faster on average.
Sam: Yes, their experiments match this: in a slow-fast pair, time fairness doubles aggregate throughput over rate fairness while the slow device's speed stays as if alone.
Alex: So in a four-node example, the total throughput jumps under time fairness because the fast ones pull their weight without the slow ones dragging the average down.
Sam: Precisely. They first figure each device's baseline throughput—the max speed it hits when no one else competes. Then, under equal time shares, every device gets one over n of the channel, where n is the number of devices, so its actual speed becomes that baseline divided by n. Slow devices end up with low speeds matching what they'd get alone in a crowd of slows, while fast ones lift the network total.
Alex: How do they prove that equal time actually happens without changing the whole WiFi standard?
Sam: Their regulator estimates airtime per packet from size, rate, and overheads like back-offs, deducting tokens accordingly to cap each at one-nth. Tests with Cisco cards confirm it: three nodes at high speeds all hit near-equal shares. Real traces from an MIT workshop and office setups reveal rate diversity is common, validating the need.
Alex: So the math holds in practice, and slow nodes don't suffer more than baseline.
Sam: Yes, the one-megabit node gets its solo baseline over four under time fairness, same as if all matched it—total rises notably. This baseline property ensures no one loses out, just the group gains. The paper suggests it's a practical fix for congested older WiFi networks.
Alex: Okay, so for older office WiFi, this TBR seems deployable at the router without big changes. How does it actually track and deduct that channel time in real time?
Sam: It runs as software above the MAC layer, triggered by key events. When a device joins, it sets up a bucket of tokens—think of tokens as seconds of allowed airtime—and starts refilling them steadily at an equal rate for everyone. Packets wait in per-device queues until the MAC asks for one.
Alex: Right, so the refill is fair from the start—like equal drips into each bucket.
Sam: When the MAC is ready, it picks a queue with tokens left, sends the oldest packet in round-robin order, and after transmission subtracts the exact airtime used from that device's tokens. Airtime includes the packet send, reply acknowledgment, tiny delays, and retries—estimated for uplink if needed. Slow packets deduct fewer tokens since they take less time at their low speed.
Alex: So retries count against the sender's share too, keeping it honest.
Sam: Exactly. For most traffic like TCP, the router paces everything without client changes. To avoid wasting airtime if some devices can't use their full share, it periodically shifts excess tokens to busy ones using max-min fairness—maximizing the lowest share first.
Alex: Does that dynamic shift risk short-term unfairness, like one device bursting too much?
Sam: The bucket caps bursts, and round-robin smooths turns, but yes, adjusting rates every few seconds can vary flows briefly, possibly needing bigger buffers. Their tests show it holds long-term equal shares even in mixes.
Alex: So the token logic enforces time fairness practically, boosting total speed where traces show congestion from rate mixes. That's a solid mechanism.
Alex: But how did they actually build and test this TBR in a real setup—did it work as planned on actual hardware?
Sam: They built a proof-of-concept in the HostAP driver on a Linux PC acting as the access point, using hardware like D-Link cards that many older WiFi cards supported. Nodes were identified by their unique MAC addresses, like digital fingerprints. They set up separate queues per device, keeping total memory use the same as a normal router. One note: it doesn't yet factor in exact retransmissions for airtime estimates, which could cause minor imbalances.
Alex: Okay, so it's plug-and-play on existing gear with simple queue tweaks—no huge hardware overhaul.
Sam: Their tests used a Linux laptop as the access point with handhelds sending large packets over TCP. In same-speed pairs, TBR kept total throughput close to what equal shares predict. For mixed speeds, normal WiFi dropped total downlink notably, but TBR hit about twice that, matching their time-fairness math.
Alex: That lines up with the baseline logic we discussed. Any catches for real networks, like short bursts?
Sam: The paper notes TBR shines for long flows, like file transfers. For hotspots with quick bursts, responsiveness depends on tuning token rates and bucket sizes—larger buckets smooth long-term fairness but can cause short bursts. Overall, tests confirm it holds high channel use amid varying traffic.
Alex: So a practical step for congested older WiFi, with room to refine for bursts. Solid evidence from hardware runs.
Alex: Those hardware results sound promising. Does the paper tie that back to real-world gains?
Sam: Yes, it confirms TBR matches normal WiFi when speeds align, with negligible overhead. In mixed cases, it shows downlink gains of about 100 percent or more, closely tracking their models. This affirms long-term equal channel time across directions.
Alex: Right, so it delivers without punishing anyone below baseline. What about varying traffic demands, like one node bottlenecked?
Sam: Table four tests that: TBR's rate adjustments shift unused tokens effectively, yielding throughputs nearly identical to standard—no disruption. It handles demand differences smoothly.
Alex: Makes sense for steady flows. But the paper mentions relying on estimates for retries—does that cause issues?
Sam: That's a key limitation: without firmware access, TBR estimates retransmissions rather than tracking them exactly, slightly biasing toward low-rate nodes and trimming total throughput a bit below ideal models. It's less ideal for very short flows too, where quick adjustments lag. Still, experiments show it holds up well overall.
Alex: So practical for offices with file transfers, but tune for web bursts. Ties into mixed setups nicely.
Sam: Precisely. Traces confirm rate diversity is routine, and without time fairness, fast devices throttle to match slow ones, stalling upgrades. TBR unlocks full potential in mixed deployments, boosting aggregate throughput substantially while preserving baselines— a meaningful step for enterprise WiFi.
Alex: That's a clear, deployable fix grounded in real tests and traces. Thanks for walking through this work on time-based fairness in multi-rate networks, Sam.
Sam: My pleasure, Alex.
Sam: Thanks for listening to ResearchPod.