Fair Stateless Aggregate Traffic Marking Using Active Queue Management Techniques

Abhimanyu Das, Debojyoti Dutta, Ahmed Helmy

Abstract

The differentiated services architecture promises to provide QoS guarantees through scalable service differentiation among multimedia and best-effort flows in the Internet. Traffic marking is an important component of this Diffserv framework. In this paper, we propose two new stateless, scalable and fair aggregate markers for TCP aggregates and UDP multimedia aggregates. We leverage stateless Active Queue Management (AQM) algorithms to design markers that ensure fair and efficient token distribution among individual flows of an aggregate. We present the Probabilistic Aggregate Marker (PAM), that uses the token bucket burst size to probabilistically mark incoming packets to achieve TCP-friendly and fair marking, and the Stateless Aggregate Fair Marker (F-SAM) that approximates fair queueing techniques to isolate flows while marking packets of the aggregate. Our simulation results show that our marking strategies show upto 30% improvement over other commonly used markers while marking flow aggregates. When applied to aggregate TCP flows consisting of long-lived flows (elephants) and short lived web flows(mice), our F-SAM marker prevents any bias against short flows and helps the mice to win the war against elephants.

Introduction

In the Differentiated Services (Diffserv) architecture, the network edge is responsible for "marking" packets—assigning them a priority level (IN or OUT)—based on a Service Level Agreement (SLA). A significant challenge in this framework is intra-aggregate fairness. Standard edge markers often treat traffic as a single aggregate blob. Consequently, a single high-rate "misbehaving" flow (such as a high-bandwidth UDP stream) can consume the majority of high-priority tokens, starving well-behaved TCP flows. While per-flow state tracking could address this, it is not scalable for modern backbone routers handling millions of flows. This research explores stateless methods to ensure fairness, particularly protecting short-lived TCP "mice" from long-lived "elephants."

Proposed Marking Schemes

The authors propose repurposing Active Queue Management (AQM) algorithms, typically used for packet dropping in core routers, for packet marking at the network edge.

Probabilistic Aggregate Marker (PAM)

PAM is inspired by the Random Early Detection (RED) algorithm. Instead of monitoring a physical queue, PAM tracks the "burst size" of a token bucket. As the bucket level decreases, PAM begins marking packets as low-priority (OUT) with an increasing probability. This probabilistic approach avoids the synchronization issues inherent in "hard" token bucket markers and ensures a more proportional distribution of tokens.

Stateless Aggregate Fair Marker (F-SAM)

F-SAM is based on Core Stateless Fair Queueing (CSFQ). In this scheme, ingress nodes estimate a flow's rate and encode it into the packet header. The F-SAM marker at the egress node calculates a "fair share" rate ($f$) for the aggregate. If a packet's incoming rate ($r$) exceeds this fair share, it is marked as OUT with a probability of $1 - f/r$. This effectively isolates flows without requiring the router to maintain per-flow state.

Experimental Setup

The performance of PAM and F-SAM was evaluated using the ns-2 network simulator. The simulation utilized a "dumbbell" topology (Figure 1) consisting of two edge nodes connected via a core link.

Simulation network topology featuring a dumbbell core and edge nodes.

The traffic models included a mix of bulk TCP flows (FTP), short-lived TCP flows (HTTP 1.0), and Constant Bit Rate (CBR) UDP flows. These were compared against standard benchmarks: the Token Bucket (TB) marker and the Time Sliding Window Three Colour Marker (TSW2CM).

Key Results and Discussion

The simulation results demonstrate significant improvements in fairness and throughput.

Protecting TCP Flows

A critical test involved competing TCP flows against a misbehaving UDP flow. As shown in Figure 2, standard Token Bucket markers allow the UDP flow to dominate the high-priority (IN) packet count. In contrast, F-SAM and PAM significantly increase the number of IN packets for TCP flows, leading to up to a 30% improvement in throughput.

Comparison of packet marking (IN vs OUT) for TCP flows and a misbehaving UDP flow across different markers.

The "Mice" vs. "Elephants"

F-SAM provides a unique advantage to short-lived "mice" flows. Because F-SAM uses an Exponentially Weighted Moving Average (EWMA) for rate estimation, short flows often conclude before their estimated rate reaches its actual peak. This lag causes the marker to perceive them as lower-rate flows, granting them a higher proportion of high-priority tokens relative to long-lived "elephant" flows.

Fairness and Predictability

Using Jain’s Fairness Index, F-SAM achieved near-perfect fairness (approaching 1.0) among UDP flows of varying rates, whereas the Token Bucket marker fell below 0.4. Furthermore, F-SAM reduced the variance in throughput among flows, making network performance more predictable.

Conclusion

This paper demonstrates that AQM techniques can be effectively adapted for stateless traffic marking at the network edge. PAM and F-SAM provide scalable solutions to the intra-aggregate fairness problem, protecting well-behaved TCP traffic from aggressive flows. While F-SAM requires header modifications, the resulting gains in fairness and the protection of short-lived web traffic offer a compelling case for its adoption in Diffserv architectures. Future work may explore other AQM techniques, such as CHOKe or PI controllers, to further refine these marking strategies.

Summary updated

Abstract

The differentiated services architecture promises to provide QoS guarantees through scalable service differentiation among multimedia and best-effort flows in the Internet. Traffic marking is an important component of this Diffserv framework. In this paper, we propose two new stateless, scalable and fair aggregate markers for TCP aggregates and UDP multimedia aggregates. We leverage stateless Active Queue Management (AQM) algorithms to design markers that ensure fair and efficient token distribution among individual flows of an aggregate. We present the Probabilistic Aggregate Marker (PAM), that uses the token bucket burst size to probabilistically mark incoming packets to achieve TCP-friendly and fair marking, and the Stateless Aggregate Fair Marker (F-SAM) that approximates fair queueing techniques to isolate flows while marking packets of the aggregate. Our simulation results show that our marking strategies show upto 30% improvement over other commonly used markers while marking flow aggregates. When applied to aggregate TCP flows consisting of long-lived flows (elephants) and short lived web flows(mice), our F-SAM marker prevents any bias against short flows and 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