Roman Pletka, Andreas Kind, Marcel Waldvogel

and Soenke Mannal (University of Stuttgart)

Closed-Loop Congestion Control for Mixed Responsive and Non-Responsive Traffic

Overview

The goals of AQM

AQM based on queue level occupancy

Rate-based AQM

Per-flow AQM

The BAT AQM algorithm

Problems in fair bandwidth allocation of responsive and
non-responsive traffic

The Closed-Loop Congestion Control (CLCC) algorithm

Simulation results

Conclusion and outlook

End-to-end Packet delivery Requirements

AQM Goods for End-to-end Packet Delivery:

Low packet loss rates.

Short end-to-end delays.

High TCP goodput (not only throughput).

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

[Pletka 03]

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]

But…

but…

None of the traditional AQM schemes are capable to efficiently separate and hence fairly allocate bandwidth for responsive and non-responsive traffic.

In addition, most existing AQM schemes require extensive tuning in order to provide lose bandwidth guarantees.

The BAT AQM Algorithm

Open-loop control scheme:

Configurable with meaningful parameters (e.g., maximum and minimum bandwidth guarantees instead of queuing thresholds).

BAT approximates max-min fairness [Bertsekas87].

Reference

Input

Controller

Control

Input

Process

Output

Per-flow aggregate transmit probabilities Ti (e.g., DiffServ codepoints).

Based on two-level AIMD control to adapt the transmit probabilities:

fi,min	min b\w guarantee

fi,max	max b\w guarantee

B	excess b\w signal

Ci	increase constant

Di	decrease constant

Oi	offered load

w	scaling constant

fi,max

fi,min

Rate

Time

Fairness index of BAT with 2 CBR Flows

Two competing UDP flows with equal fmax = 100Mbps and varying minimum bandwidth guarantees fmin:

fmin

Flow 1

[Mbps]

fmin Flow 2 [Mbps]

high fairness

low fairness

The Simulation Topology

TCP

Source 1

TCP

Source n

100 Mbps

100 Mbps

UDP

Source

UDP

Sink

TCP

Sink 1

TCP

Sink n

BAT

BAT

1500

1500

500

500

1500

1500

500

500

Packet Size [Bytes]

100

200

100

200

100

200

100

200

UDP Rate [Mbit/s]

2 – 20

2 – 20

2 – 20

2 – 20

2 – 198

2 – 198

2 – 198

2 – 198

0 – 4

5 – 9

10 – 14

15 – 19

20 – 24

25 – 29

30 – 34

35 – 39

RTT [ms]

Simulation

Each simulation set consists of 5 different bandwidth allocations (90, 60, 45, 30, 25% UDP traffic).

Motivation: Difficulties in bandwidth allocation

Difficulties in presence of responsive and non-responsive traffic:

Traditional AQM (RED):
Decreasing TCP bandwidth share when UDP traffic increases [Floyd97].

BAT:
Using a correction factor for DUDP as a function of the desired bandwidth allocation.

Key idea:	It is sufficient to control only one parameter, namely DUDP in BAT based on the UDP/TCP ratio rref.

The CLCC algorithm

based on Closed-loop control:

Reference

Input

Controller

Control

Input

Process

Output

Σ

+

_

Sensor

derived from a PID Controller:

Discrete time notation:

The proportional part does not improve the results



and

(pure integral feedback controller)

Control error:

Control rule:

y(t)	control input

xd(t)	control error

Kr, TN, TV system parameters

The CLCC algorithm (detailed view)

- Offered UDP rate OUDP

- Serviced TCP and UDP rate fTCP, fUDP (measured & averaged)

- Desired UDP/TCP ratio rref

Input Interface

OUDP < fUDP,ref

Recovery from

Preemption ?

Control Preemption

D = 0.9 · D

Recovery

UDP

k

k-1

UDP

D = D

UDP

k

recovery

UDP

Error Signal Feedback

x = (r - r ) / r

d,k

ref

k

ref

D = D + β·D · x

UDP

k

k-1

UDP

k-1

UDP

d,k

Signal Limiter

D ≤ D ≤ D

UDP

k

min

max

0.5

0.33

0.05

Output Interface

D

UDP

k

new

Yes

No

Yes

No

CLCC on a IBM PowerNP 4GS3 Network Processor

UDP offered

rate

TCP offered

rate

Data Plane

AQM Scheme

AQM Algorithm

CLCC Algorithm

evaluate new AQM parameters

dt ~ 1s

Control Plane

NP APIs

Routing

Resource

Manager

CLCC

max/min

b/w

values

Error

Signal

Feedback

Control

Preemption

Recovery

Signal

Limiter

Serviced UDP

rate

Serviced TCP

rate

Packet

Processing

Transmit

Probability

Table

max/min values

DUDP

D0

serviced

rates

Network Processor

Control Processor

- adapts transmit

probabilities

every 4ms

- Layer 2-4
processing

Packet

Scheduler

rref

Simulation Results (using ns-2)

Set of 100 greedy TCP connections, 2 - 200ms RTTs.

One CBR UDP flow at 90Mbps.

Bandwidth allocation:
fUDP,min= 0 Mbps, fTCP,min= 40Mpbs, fUDP,max= fTCP,max= 100Mbps  rref= 30/70  0.42

BAT without additional controller

Using the CLCC algorithm with BAT

Simulation Results (cont.)

Set of 100 greedy TCP connections.

One bouncing UDP flow between 50 and 120Mbps.

Bandwidth allocation:
fUDP,min= 0 Mbps, fTCP,min= 40Mpbs, fUDP,max= fTCP,max= 100Mbps
 rref= 30/70  0.42

UDP and TCP rates

UDP/TCP ratio and fairness index

Conclusion

CLCC is a robust solution for fair bandwidth allocation of responsive and non-responsive traffic even in presence of bursty traffic conditions.

First AQM system that is able to automatically control under disparate creativeness without having to include an expensive fair queuing system.

CLCC maintains low queuing delays when used on top of BAT.

CLCC requires no tuning of parameters.

Simulations have been verified in an implementation based on a IBM PowerNP 4GS3 network processor.

Outlook

Analysis of CLCC on top of other AQM algorithms.

Short-lived TCP connections.

Closed-Loop Congestion Control for Mixed Responsive and Non-Responsive Traffic

IBM Presentation System

W.Bux

2003-07-24T09:49:04

Marcel Waldvogel