Beyond CHOKe: Stateless Fair Queueing

Rade Stanojevic, Robert ShortenNet-coop 2007 · DOI

TL;DR

This paper introduces MLC(l), a novel stateless Active Queue Management (AQM) scheme that aims to achieve max-min fair resource allocation in TCP networks without requiring per-flow state in routers. By analyzing a Markov chain model and conducting simulations, the authors demonstrate that increasing the parameter 'l' in MLC(l) brings the network's resource allocation arbitrarily close to max-min fairness.

What Problem Does This Paper Address?

Ensuring fair resource allocation in the internet, particularly for TCP traffic, is a long-standing challenge. The goal is often to achieve "max-min fairness," where resources are distributed such that the minimum allocated bandwidth is maximized, and then the next minimum is maximized, and so on. A key difficulty is that routers typically lack per-flow state information, making it hard to differentiate between flows and allocate resources fairly, especially when flows have different characteristics like varying Round-Trip Times (RTTs). Existing solutions often require changes to end-to-end protocols or complex router state management. This paper tackles the problem of achieving max-min fairness using a stateless AQM scheme, meaning routers don't need to track individual flows.

Methods

The core contribution is the Multi-Level Comparison with index l (MLC(l)) scheme. MLC(l) is a stateless AQM that operates by comparing an arriving packet with a randomly selected set of 'l' packets already in the queue. If all 'l' packets belong to the same flow, the arriving packet is dropped. This mechanism is designed to implicitly penalize flows that are currently using a larger proportion of the link's bandwidth.

The authors also employ:

  • Markov Chain Analysis: A mathematical model is used to analyze the behavior of MLC(l) under various network conditions and to prove its convergence properties.
  • Power-Drop AQM Framework: MLC(l) is presented as a specific instance of a broader class of "power-drop" AQMs, where the drop probability is proportional to the flow's current throughput raised to a power related to the index 'l'.
  • ns2 Simulations: Packet-level simulations are used to validate the analytical findings and compare MLC(l) with existing AQM schemes like RED.

Datasets

Not discussed in the paper. The experiments utilize simulated network traffic generated by TCP flows within the ns2 simulator.

Key Insights and Ideas

  • Statelessness is Achievable for Fairness: The most significant insight is that it's possible to approximate max-min fairness using a stateless AQM. This is crucial for scalability in high-speed networks where maintaining per-flow state is prohibitive.
  • The Power of Multi-Level Comparison: The MLC(l) scheme's effectiveness hinges on the parameter 'l'. Increasing 'l' allows the scheme to more accurately infer and penalize aggressive flows, leading to better fairness.
  • RTT Unfairness Mitigation: The paper shows that traditional AQMs like RED exhibit RTT unfairness (favoring low-RTT flows). MLC(l), especially with higher 'l', demonstrably reduces this bias.
  • Convergence to Max-Min Fairness: The analytical results provide strong theoretical backing that as 'l' increases, the resource allocation achieved by MLC(l) converges to the ideal max-min fair allocation.

Key Results

  • Analytical Convergence: The Markov chain analysis proves that for an arbitrary network topology and set of TCP users, increasing 'l' in MLC(l) leads to resource allocation arbitrarily close to max-min fairness.
  • Simulation Validation:
    • In a single bottleneck scenario with 100 flows, MLC(2) shows fairness proportional to 1/RTT^(2/3), a significant improvement over RED's 1/RTT fairness.
  • In a more complex multi-bottleneck topology, MLC(17) achieved a Jain's fairness index of 0.997, very close to the ideal max-min fairness, while DropTail and RED achieved indices of 0.345 and 0.731, respectively.
  • Power-Drop Characterization: MLC(l) is formally shown to be a power-drop AQM, with the drop probability related to the flow's throughput and the index 'l'.

Limitations and Future Work

  • Assumptions: The analysis often relies on assumptions of low loss probability and neglecting variations in round-trip times.
  • Parameter Tuning: While the paper discusses controlling the hM parameter (related to l) using a MIMD scheme, the optimal tuning of parameters like ∆0 and γ for real-world deployment is an area for further exploration.
  • Unresponsive Flows: The paper notes that MLC is designed to improve TCP fairness and "neglects effects of unresponsive flows." Handling such flows might require additional mechanisms.
  • Future Work: The authors suggest that further research could explore similar interesting features shared with other schemes like XCP, particularly regarding shuffling parameters. The potential for MLC to enforce fairness without end-to-end protocol changes is highlighted as a key advantage.

Summary updated

BibTeX
@inproceedings{stanojevic2007beyond,
  author = {Rade Stanojevic and Robert Shorten},
  title = {{Beyond CHOKe: Stateless Fair Queueing}},
  booktitle = {Net-coop},
  year = {2007},
  doi = {10.1007/978-3-540-72709-5\_5},
}
Figure