Roman Pletka, Marcel Waldvogel and

Soenke Mannal (University of Stuttgart)

PURPLE:	Predictive Active Queue Management
Utilizing Congestion Information

Overview

The goals of AQM

AQM based on queue level occupancy

Rate-based AQM

Per-flow AQM

Explicit congestion notification (ECN) RFC 3168

Measurements from real Internet backbones

The Purple algorithm

The macro-managed part

The micro-managed part

Simulation results

The single-bottleneck case

The multi-bottleneck case

Conclusion and outlook

End-to-end Packet delivery Requirements

AQM Goals for End-to-end Packet Delivery:

Low packet loss rates.

Short end-to-end delays.

High TCP goodput.

Absorb traffic bursts [Villamizar:94] (bandwidth–delay product of buffer space in routers).

Stable queuing delays.

4 Packets / connection in Flight [Morris 97].

Non Goals:

Queues stabilized at a certain length.

Exact per-flow fairness.

Keeping per-flow state information.

United Colors of AQM

RED

[Floyd 93]

PURPLE

Tail Drop

A-RED

[Floyd 01]

S-RED

[Feng 99]

F-RED

[Lin 97]

BLUE
[Feng 99]

Time

BAT
[Bowen 01]

Green 1
[Feng 02]

Green 2
[Wydrowsky 02]

non lin.

RED
[Plasser 02]

Kantawala

&Turner

D-RED

[Aweya 01]

Flow-based

Based on intrinsic TCP properties

Rate-based

Heuristics

PI Controller

[Hollot 01]

Explicit Congestion Notification (ECN)

Explicit congestion notification (ECN) standardized in [RFC3168], first discussed in context of the DECbit in [Ramakrishnan 90].

ECN enables to indicate congestion without dropping packets and causing a later retransmit or time-out. Done at routers by simply setting a mark in the packet header when a packet would have been dropped but there is still space in the queue.

ECN does not require routes to be symmetric.

The concept has the potential to significantly improve latency and goodput, but current AQM mechanisms such as RED [Floyd 93] often need to revert to packet loss.

Improvements in throughput and goodput when using ECN have been reported in RFC2884.

Although ECN is not widely deployed yet today but can be expected to be widespread in the future:
Today: 2.3% of ECN-enabled traffic found in an OC-12c Packet-over-Sonet link connecting the Merit premises in East Lansing to the Internet2/Abilene.

Purple: The Static Model…

TCP steady state equation from [Mathis 97] of a single TCP connection n:

From a single connection to a bundle:

a system constant

Maximum segment size

Round trip time

Probability of a “packet loss”

cn

Sn

Rn

pn

Static Model:

Scaling the bandwidth of a single TCP connection by a factor :

Scaling the bundle:

Purple: …and its Dynamics

Splitting the drop probability:

Control rule:

Router k

Router 1

Router K

Ratio of packets

with CE set

Ratio of packets

with CWR set

Obtained from

pk and p<k, recorded from

the preceding RTT

Source

Receiver

Assumption:

k is the main bottleneck and

drop probabilities are small.

=> summing is a good approximation.

RTT estimation

Maintain a distribution of measured RTTs (array of 32 values)

Estimation:

Add an exact-match packet filter when CE bit is set.

Measure time until a packet with CWR arrives for this classifier.

Ignore shortest and longest values measured.

This can be smartly achieved on network processors.

Purple: Microscopic Drop Probability Updates

Enhancement to short term queue variations by using a fine-grained microscopic part and taking into account the average queue length.

Link capacity

queuing delay parameter

Average queue occupancy

Total queue capacity

L



q

Q

Purple: Putting it all together

At packet arrival:

Background task:

if ecn_enabled(pkt) then

measure_ce_probability();

measure_cwr_probability();

if rand() ≤ pk then

set_ce(pkt);

start_rtt_est(pkt);

end if

end if

if Queue full then

drop(pkt);

return;

end if

enqueue(pkt);

ewma(q);

ewma(X);

remove_expired_rtt_entries(rtt_max);

  L / X’ ;

p’k  p/2 – p<k – p>k ;

if t > --rtt_cntr then

update p<k from history;

update p>k from history;

update RTT estimate R;

p  p/2 ;

rtt_cntr  floor(R/t);

end if

The Single-Bottleneck Case

Router

TCP Source

TCP Sink

Purple Queue

Source 1

Source n

100 Mbps / 2 ms

100 Mbps

10-20 ms

Sink n

100 Mbps

10-20 ms

Sink 1

Simulation Parameters:

thmin =10 packets

thmax = 600 packets

pmax = 0.02

wq = 0.002

 All AQM schemes are ECN enabled.

Rate and Goodput Comparison

Rate

Goodput

80

10

10

10

80

80

80

10

10

10

80

80

Results with the micro-managed part disabled.

Not enough sources for

good parameter estimation!

Comparison of Mark and Drop Rates

Goodput and Delay Comparison

Results with the micro-managed part and shorter queues.

10 Sources

100 Sources

10 Sources

100 Sources

Average Queue Length and Local Drop Rate

RED

PURPLE

ARED

- 100 TCP Sources

Queue Length (kB)

Drop Probability

Simulation Time [s]

0

160

100

0

100

0

100

0

100

0

100

0

100

0

160

0

160

0

0.14

0

1

0

1

0

Simulation Time [s]

Simulation Time [s]

Simulation Time [s]

Simulation Time [s]

Simulation Time [s]

Source 1:1

Purple

Router

TCP Source

TCP Sink

Purple Queue

The Multi-Bottleneck Case

Source 1:n

100 Mbps

Source 2:1

Source 2:n

Source 3:1

Source 3:n

Sink 2:1

Sink 2:n

Sink 3:1

Sink 3:n

Sink 1:n

Sink 1:1

10 ms

100 Mbps

20 ms

100 Mbps

10 ms

100 Mbps

1 ms

100 Mbps

1 ms

100 Mbps

10-20 ms

100 Mbps

10-20 ms

100 Mbps

10-20 ms

100 Mbps

10-20 ms

100 Mbps

10-20 ms

100 Mbps

10-20 ms

The Multi-Bottleneck Case

Conclusion

Purple is an AQM scheme designed for ECN-enabled TCP/IP networks.

Improved TCP goodput by taking into account the steady state properties of TCP.

Purple maintains low buffer usage even with a high number of TCP connections and therefore improves the end-to-end delay.

Significant less packet drops than other well-known AQM algorithms.

Faster convergences of AQM parameters lead to more stable drop probabilities lead to less tail drops.

Outlook

Possibility to maintain per-incoming interface RTT estimates.

Provides new means for TCP bandwidth estimation and its characteristics (short-lived vs. long-term sessions).

Marcel Waldvogel

2003-10-31T15:35:23