Fair Stateless Aggregate Traffic Marking using Active Queue Management Techniques

Abhimanyu Das, Debojyoti Dutta, Ahmed Helmy

Abstract

In heterogeneous networks such as today's Internet, the differentiated services architecture promises to provide QoS guarantees through scalable service differentiation. Traffic marking is an important component of this framework. In this paper, we propose two new aggregate markers that are stateless, scalable and fair. We leverage stateless Active Queue Management (AQM) algorithms to enable fair and efficient token distribution among individual flows of an aggregate. The first marker, Probabilistic Aggregate Marker (PAM), uses the Token Bucket burst size to probabilistically mark incoming packets to ensure TCP-friendly and proportionally fair marking. The second marker, Stateless Aggregate Fair Marker (F-SAM) approximates fair queueing techniques to isolate flows while marking packets of the aggregate. It distributes tokens evenly among the flows without maintaining per-flow state. Our simulation results show that our marking strategies show upto 30% improvement over other commonly used markers while marking flow aggregates. These improvements are in terms of better average throughput and fairness indices, in scenarios containing heterogeneous traffic consisting of TCP (both long lived elephants and short lived mice) and misbehaving UDP flows. As a bonus, F-SAM helps the mice to win the war against elephants.

Introduction

The Differentiated Services (Diffserv) architecture maintains scalability by grouping traffic into large aggregates at the network edge, allowing core routers to remain stateless. However, traditional traffic marking tools, such as Token Buckets, are "flow-blind." This lack of granularity leads to significant unfairness within the aggregate. Specifically, long-lived "elephant" flows often starve short-lived "mice" (like web requests), and non-responsive UDP "bullies" can monopolize high-priority "In-Profile" tokens at the expense of well-behaved TCP traffic. Existing solutions to this "tragedy of the commons" typically require per-flow state management, which fails to scale at high speeds.

Proposed Marking Strategies

This paper introduces two novel markers that repurpose Active Queue Management (AQM) logic for edge marking. By viewing a Token Bucket’s burst size as a virtual queue and the token arrival rate as link bandwidth, established AQM algorithms can be applied to decide packet priority.

Probabilistic Aggregate Marker (PAM)

PAM is inspired by the Random Early Detection (RED) algorithm. Rather than waiting for a token bucket to empty before marking packets as "OUT" (low priority), PAM maintains an exponentially weighted moving average (EWMA) of the bucket size. As the bucket depletes, the probability of marking a packet as "OUT" increases linearly. This probabilistic approach smooths out bursts and ensures that high-volume flows are statistically more likely to be penalized, promoting proportional fairness.

Stateless Aggregate Fair Marker (F-SAM)

F-SAM adapts Core Stateless Fair Queueing (CSFQ) to the marking context. It utilizes a max-min fairness criterion where ingress nodes estimate a flow's rate and embed it in the packet header. The F-SAM marker at the egress uses this information to calculate a "fair share" rate. Packets from flows exceeding this share are probabilistically marked as "OUT." This provides robust flow isolation without requiring the marker to maintain a per-flow state table.

Experimental Evaluation

The markers were evaluated using the ns-2 network simulator across several synthetic traffic scenarios designed to stress-test fairness and throughput:

  • Mixes of long-lived bulk TCP flows.
  • Heterogeneous traffic consisting of "elephants" (long TCP) and "mice" (short HTTP-like TCP).
  • Scenarios featuring "misbehaving" UDP flows sending at high constant bit rates (CBR) alongside elastic TCP flows.

Key Results and Insights

Simulation results demonstrate that both PAM and F-SAM significantly outperform standard markers like Token Buckets (TB) and Time Sliding Window Three Colour Markers (TSW2CM).

Throughput and Fairness

In heterogeneous environments, the proposed markers achieved up to a 30% improvement in average throughput. F-SAM, in particular, showed exceptional resilience against UDP bullies. By effectively penalizing non-responsive flows, it maintained a much higher fairness index compared to standard methods.

Fairness Index comparison in the presence of a misbehaving UDP flow.

Protecting "Mice" from "Elephants"

A notable benefit of F-SAM is its inherent protection of short-lived flows. Because rate estimation (EWMA) requires time to ramp up, "mice" flows initially appear to have a lower rate than they actually do. This gives them a temporary priority, allowing them to complete transfers before being throttled by the fair-share calculation.

Per-flow throughput comparison showing F-SAM's superior performance in heterogeneous traffic.

Conclusion and Future Work

PAM and F-SAM demonstrate that per-flow fairness can be achieved in a stateless manner at the network edge. While F-SAM provides stronger isolation, PAM offers a simpler implementation based on well-understood RED principles. Future work includes addressing rate estimation lag in complex network paths and exploring auto-tuning mechanisms, such as PI controllers, for PAM’s thresholds. Additionally, extending F-SAM to support Weighted Fair Queueing (WFQ) within aggregates remains a promising research direction.

Summary updated

Abstract

In heterogeneous networks such as today's Internet, the differentiated services architecture promises to provide QoS guarantees through scalable service differentiation. Traffic marking is an important component of this framework. In this paper, we propose two new aggregate markers that are stateless, scalable and fair. We leverage stateless Active Queue Management (AQM) algorithms to enable fair and efficient token distribution among individual flows of an aggregate. The first marker, Probabilistic Aggregate Marker (PAM), uses the Token Bucket burst size to probabilistically mark incoming packets to ensure TCP-friendly and proportionally fair marking. The second marker, Stateless Aggregate Fair Marker (F-SAM) approximates fair queueing techniques to isolate flows while marking packets of the aggregate. It distributes tokens evenly among the flows without maintaining per-flow state. Our simulation results show that our marking strategies show upto 30% improvement over other commonly used markers while marking flow aggregates. These improvements are in terms of better average throughput and fairness indices, in scenarios containing heterogeneous traffic consisting of TCP (both long lived elephants and short lived mice) and misbehaving UDP flows. As a bonus, F-SAM helps the mice to win the war against elephants.
BibTeX
@inproceedings{das2002fair,
  author = {Abhimanyu Das and Debojyoti Dutta and Ahmed Helmy},
  title = {{Fair Stateless Aggregate Traffic Marking using Active Queue Management Techniques}},
  booktitle = {MMNS},
  year = {2002},
  url = {https://openreview.net/forum?id=xM3M1My53Tq},
}
Figure