744-slide.ppt

Evaluation of Queue Management Algorithms Ningning Hu, Liu Ren, Jichuan Chang 30 April 2001

15744 Course

1

Motivation • Typical queuing discipline: DropTail • Active queue management: – RED (93’), BLUE (99’), … – FRED (97’), SFB (99’), CHOKe (2000’)

• Problem: How to compare them? – Metrics: Utilization, Fairness and Complexity – Method: simulation under common settings 15744 Course

2

Algorithms      

Drop Tail: drop when the queue is full RED: queue length, minth, maxth, avg FRED: per-active-flow accounting BLUE: loss rate, link utilization, freeze_time SFB: identify flows using N * L bins CHOKe: compare incoming packet with random selected packet in queue

15744 Course

3

Simulation Scenario source

destination 2Mbps

2Mbps UDP

UDP 1Mbps, 40ms router

TCP

router

TCP

• Topology: Dumb-bell • Metrics: throughput and queue size 15744 Course

4

TCP

Drop Tail

RED

BLUE

TCP

FRED

15744 Course

SFB 1. 2. 3.

# TCP Flow : # UDP Flow = 10 : 1 UDP sending rate = 2Mbps Buffer size = 150 packets

CHOKe

5

Performance Comparison 1

DropTail

0.8

RED

0.6

FRED

0.4

BLUE

0.2

SFB CHOKe

0 0.1

0.2

0.4

0.8

1

2

4

8

UDP Rate (Mbps)

Figure 1. UDP Thpt (Mbps) 150

DropTail RED FRED BLUE

100 50

SFB CHOKe

0 0.1

0.2

0.4

0.8

1

2

4

8

UDP Rate (Mbps)

Figure 2. UDP Queue Size (packet)

15744 Course

6

Conclusion Algorithm

Link Utilization

Fairness

Ease of Configuration

RED

Good

Unfair

Hard

BLUE

Good

Unfair

Hard

FRED

Good

Fair

Easy (adaptive)

SFB

Good

Fair

Easy (non-adaptive)

CHOKe

Good

Fair

Easy (adaptive)

Algorithm

Buffer size requirement

Per-flow State Information

Computational Overhead

RED

Large

No

Arrival

BLUE

Small

No

Freeze-time

FRED

Small

Yes

Arrival-departure

SFB

Large

No

Freeze-time

CHOKe

Small

No

Arrival

15744 Course

7

FRED

• RED + Per-active-flow accounting – protection of fragile flow – penalizing non-responsive flow – Flow type differentiation

• Key parameter: minq – 2 or 4

• Weak point: – Compute avgq per packet

New flow?

New state

N Calculate avg & maxq Non-adaptive? N minth
15744 Course

Y

N Drop Tail

Y Robust Fragile

8

Drop RED Accept

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

1TCP ,1UDP 10 TCP, 1UDP 10 TCP, 5 UDP

70

0.1

0.2

0.4 0.8 1 UDP rate (Mbps)

2

4

8

UDP Queue Size (packet)

UDP Thpt (Mbps)

FRED performance

1TCP,1UDP

60

10 TCP , 1UDP 10 TCP , 5 UDP

50 40 30 20 10 0 0.1

15744 Course

0.2

0.4 0.8 1 UDP rate (Mbps)

2

4

9

8

FRED characteristics • Easy to configure, adaptive • Buffer size requirement

Throughput (Mbps)

– Will degrade as DropTail with too many flows – “Two-packet-buffer” to keep fairness 1 0.75 TCP_ Thpt

0.5

UDP_ thpt

0.25 0 10

15744 Course

20

40

45

50

60

Buffer size (#Packet)

10

70

CHOKe CHOose and Keep for responsive flows CHOose and Kill for unresponsive flows Random rel="nofollow">maxth? minth Same FlowID?

maxth

15744 Course

11

UDP Throughput (Mbps)

CHOKe 1 0.8 0.6 0.4 0.2 0 0.1

0.2

0.4

0.8

1

2

4

8

UDP rate (Mbps) 1 TCP, 1 UDP

15744 Course

10 TCP, 1 UDP

10 TCP, 5 UDP

12

Parameters in CHOKe 0.7

UDPFlowThroughput (Mbps)

UDP Flow Throughput (Mbps)

0.25

0.2

0.15

0.1

0.05

0 1

2

5

10

Candidate Num ber

15744 Course

15

0.6 0.5 0.4 0.3 0.2

num = 1 num = 10

0.1

num = 5 num = 15

0 2

1.6

1

0.8

UDP rate (Mbps)

13

BLUE •Main Point: Uses packet loss and link idle events instead of average queue length : •Based on observation that RED is often forced into drop-tail mode •Adapt to how bursty and persistent congestion is by looking at loss/idle events

15744 Course

14

BLUE Algorithm Pm is Blue’s packet dropping probability: •Upon packet loss, if no update of pm in freeze_time then increase by d1 •Upon link idle, if no update of pm in freeze_time then decrease pm by d2 •d1 >> d2  •More critical to react quickly to increase in load

15744 Course

15

BLUE Characteristics

•More stable queue size and much better behavior with small buffers •Good property damaged by non-responsive flows.

15744 Course

16

Stochastic Fair Blue(SFB) •Objective: •Identify and penalize misbehaving flows

•Main Algorithm: Create L hashes with N bins each •Each bin keeps track of separate marking rate (p m) •Rate is updated using standard technique(as BLUE) •Flow uses minimum pm of all L bins it belongs to •Non-misbehaving flows hopefully belong to at least one bin without a bad flow

15744 Course

17

SFB Characteristics

•Could effectively detect non-responsive flows and rate-limit them •But not adaptive, the bandwidth share of non-responsive flows is controlled by a parameter(Boxtime) offered by the user. •Boxtime is the time interval no packets from non-responsive flows can be enqueued.

15744 Course

18

SFB: Unfairness of Non-responsive Flows

Our solution: Randomized Boxtime a little bit.

15744 Course

19

Rate-limit Non-responsive flows UDP packets Boxtime Queue

Time

15744 Course

20