networking answer 3 questions must be original
smalling help
aqm-red_6.3.1_.pdf
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.1
Lecture 6 Active Queue Management (ST: Advances in Networks)
CS 6/75995 Summer 2014
H. Peyravi Department of Computer Science
Kent State University
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 1 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.2
§6.0.0 Contents Acronyms 1 Introduction
Introduction The Role of AQM
2 Traffic Engineering Traffic Engineering What is Congestion Congestion Control Implicit vs. Explicit feedback TCP Congestion Control
3 AQM AQM AQM Goals Random Early Detection (RED) How about non-responsive sources?
4 AQM Classifications Classification Based on Congestion Control Classification By Mechanisms
5 Bufferbloat in the Internet Bufferbloat in the Internet
6 Understanding Queues Understanding Queues
7 Controlled Delay Management Controlled Delay Management
8 CoDel Algorithm CoDel Algorithm
9 References
The contents of this lecture have been composed from various resources including those listed at the reference section.
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 2 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.3
§6.0.0 Glossaries ABR Available Bir Rate 10 AQM Active Queue Management 4–6, 15, 20, 29, 31, 35 ATM Asynchronous Transfer Mode 10 BDP Bandwidth × delay 30
CC Congestion Control 5, 6 CSFQ Core Stateless Fair Queuing 21
DiffServ Differentiated Services 4, 6 E2E End-to-End 16 ECN Explicit Congestion Notification 10
EWMA Exponentially Eeighted Moving Average 16, 18 FQ Fair Queuing 21
FRED Fair Random Early Detection 21 FWQ Weighted Fair Queuing 21 IETF Internet Engineering Task Force 29
IntServ Integrated Services 4 IP Internet Protocol 5, 6
MPLS Multiprotocol Label Switching 9 QoS Quality of Service 4, 6 RED Random Early Detection 5, 20, 21, 29, 35 SFQ Stochastic Fair Queuing 21 SLA Service Level Agreement 6 TCP Transport Control Protocol 5, 14
TD Tail-Drope 15 UDP User Data Protocol 21
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 3 / 39
Active Queue Management
Acronyms
Introduction Introduction
The Role of AQM
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.4
Introduction Introduction
§6.1.1 Introduction
å Reading list: [1], [3]
Since 1993, there has been a steady stream of research in Active Queue Management (AQM) 1
Issues I What are the major attributes of AQM schemes? I What are the design approaches taken by AQM schemes? • Heuristic techniques • Control-theoretic techniques • Deterministic optimization
I What is the role of AQM w.r.t. Quality of Service (QoS) provisioning in • Differentiated Services (DiffServ)? • Integrated Services (IntServ)? • Wireless domain?
• . . .
1 We used the words ”buffer” and ”queue” interchangeably
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 4 / 39
Active Queue Management
Acronyms
Introduction Introduction
The Role of AQM
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.5
Introduction The Role of AQM
§6.1.2 The Role of AQM I
The Role of AQM in Internet Protocol (IP) is to complement the work of end-system protocols such as the Transport Control Protocol (TCP) in Congestion Control (CC) so as to increase: I Network utilization I Limit packet loss I Limit delay The first proposal for AQM was Random Early Detection (RED) [2] in 1993. I Followed by a number of new/augmented/improved proposals • Some with rigorous analysis
K Some highlighted RED’s drawbacks
The design of RED and many of its variants were heuristic I As a result, parameter-tuning has been the main limitations Some researchers have used control theory techniques to overcome these limitations I Classical control I Modern control I Optimal control I Nonlinear control
Others use optimization techniques in the context of Congestion Control (CC)
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 5 / 39
Active Queue Management
Acronyms
Introduction Introduction
The Role of AQM
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.6
Introduction The Role of AQM
§6.1.2 The Role of AQM II
The focus has been shifted from CC to QoS provisioning Why? I Rapid deployment of data, voice, video and mobility • Supported by common IP, and • Growing heterogeneous set of communication technologies
I Diverse requirements of the different types of traffic flows
The role of AQM has become a mechanism to support DiffServ through I Traffic conditioning I Packet scheduling I Controlling • End-to-end delay • Delay variation (jitter) • Packet loss • Bandwidth
According to mutually agreed Service Level Agreements (SLAs).
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 6 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.7
Traffic Engineering Traffic Engineering
§6.2.1 Traffic Engineering
Measurement I To do reality check Experiment I To test implementation Issues
Analysis To bring fundamental understanding of the systems I May loose important facts because of simplification Simulation I Complementary to analysis • To test correctness • To explore complicate model
I May share similar model to analysis
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 7 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.8
Traffic Engineering What is Congestion
§6.2.2 What is Congestion
Question 6.1 (What is congestion?)
Answer: The aggregate demand for bandwidth exceeds the available capacity of a link
Question 6.2 (What are the consequences when congestion occurs?)
Answer: Performance degradation
Multiple packet losses
Low link utilization (low Throughput)
High queuing delay
Congestion collapse
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 8 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.9
Traffic Engineering Congestion Control
§6.2.3 Congestion Control
1 Open-loop control I No feed-back mechanisms I Mainly used in circuit switched network Generalized Multiprotocol Label
Switching (MPLS) 2 Closed-loop control
I Uses feedback information ⇒ global & local I Mainly used in packet switched network
a Implicit feedback control • End-to-end congestion control • Examples: TCP Tahoe, TCP Reno, TCP Vegas, etc.
b Explicit feedback control • Network-assisted congestion control • IBM SNA, DECbit, ATM ABR, ICMP source quench, RED, ECN
Two Basic Approaches
1 Congestion Control (Reactive) I Play after the network experienced congestion
2 Congestion Avoidance (Proactive) I Play before he network becomes congested
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 9 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.10
Traffic Engineering Implicit vs. Explicit feedback
§6.2.4 Implicit vs. Explicit feedback
1 Implicit feedback Congestion Control I Network drops packets when congestion occurs I Source infers congestion implicitly • It times out
K Duplicated Acks, etc. Û Duplicated Acks arrive when the time-out is shorter than RTT
I Example: end-to-end TCP congestion Control I It is a simple to implement but inaccurate ⇓ Why? • It is implemented only at the transport layer ( L4, e.g., TCP)
2 Explicit feedback Congestion Control I Router (L3) provides congestion indication explicitly to sources • Normally through packet marking
I Examples • DECbit • Explicit Congestion Notification (ECN) • Asynchronous Transfer Mode (ATM) Available Bir Rate (ABR)
I It provides more accurate information to sources ⇑ I It is more complicate to implement • Need cooperation between source and network • Need to change both source and network algorithms
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 10 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.11
Traffic Engineering TCP Congestion Control
§6.2.5 TCP Congestion Control I Slow Start
cwnd
W
1
4
2
RTTRTTRTT
time
h
Wh
W
/2
c
W +1c
Congestion Avoidance
Exponential growth
Slow Start has two phases 1 Exponential growth phase • Start with Wc = 1 • For each Ack, Wc := Wc + 1 segment • For each RTT, Wc := 2 × Wc ⇒ exponential growth • Until it reaches the threshold Wh , i.e., Wc ≥ Wh • Wc = Wc/2, then enters Congestion Avoidance phase
2 Congestion avoidance phase (linear growth) • For each successful ACK Wc := Wc + 1/Wc How? • For each RTT Wc := Wc + 1
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 11 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.12
Traffic Engineering TCP Congestion Control
§6.2.5 TCP Congestion Control II Does it do the job?
TCP Tahoe
Uses Slow Start + Fast Retransmission Reduces the time a sender waits before retransmitting a lost segment I Triple duplicate Acks are treated the same as a timeout How? • An indication of segment lost
I The sender retransmits the packet before waiting for its timeout Fast retransmit ⇒ an enhancement I Set Wh = Wc/2 I Set Wc = 1 segment and Slow Start
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 12 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.13
Traffic Engineering TCP Congestion Control
§6.2.5 TCP Congestion Control III TCP Reno
Uses Tahoe + Fast Recovery Upon receiving triple duplicate Acks, i.e. packet must have been lost and not received after 3 RTTTs I Sets Wc = Wc/2 I Retransmits the missing segments I Sets Wc = Wh + 3 Upon receiving next Ack, I Sets Wc = Wh
It allows the window size grow fast to keep the pipeline full
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 13 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering Traffic Engineering
What is Congestion
Congestion Control
Implicit vs. Explicit feedback
TCP Congestion Control
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.14
Traffic Engineering TCP Congestion Control
§6.2.5 TCP Congestion Control IV
Additive Increase/Multiplicative Decrease
Additive-increase/multiplicative-decrease (AIMD) algorithm is a feedback mechanism used in TCP I AIMD combines linear growth of the congestion window with an
exponential reduction when a congestion takes place
Multiple flows using AIMD congestion control will eventually converge to use equal amounts of a contended link
Let Wc(t) be the sending rate during time slot t, then
Wc(t + 1) = {
Wc(t) + a If congestion is not detected Wc(t)× d If congestion is detected
a > 0, 0 < b < 1 (1)
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 14 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.15
AQM AQM
§6.3.1 AQM
TCP performance degradation due I Multiple packet loss I Low link utilization I Congestion collapse The role of the router becomes important I Control congestion effectively inside the network How? I Allocate bandwidth fairly How?
One option is to use FIFO Tail-Drope (TD) queue management I Two problems with TD • Lock-out: a small number of flows monopolize the queue • Full-queue: the buffer is always full ⇒ high queuing delay
One possible solution is AQM I A group of FIFO based queue management mechanisms to support
end-to-end congestion control in the Internet
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 15 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.16
AQM Goals AQM Goals
§6.3.2 AQM Goals
Reducing the average queue length I That decreases the End-to-End (E2E) delay Reducing packet losses How? I More efficient resource allocation
Method
Drop some packets before buffer becomes full How? I Some random algorithms
Use Exponentially Eeighted Moving Average (EWMA) of the queue length as an congestion indicator Why?
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 16 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.17
AQM Goals Random Early Detection (RED)
§6.3.3 Random Early Detection (RED) I
TCP (Tahoe, Reno, Vegas) detect congestion after a buffer at an intermediate router is full RED provides a warning to sources ⇒ I It detects incipient congestion
Congestion measure ⇒ Average queue length
Q(t + 1) = [Q(t) + λ(t)−µ(t)]+
RED objectives
1 Congestion avoidance ⇒ proactive rather than reactive I Detect the onset of congestion, rather than react to it I Maintain the optimal region of high throughput and low delay
2 Avoid bias against bursty traffic I Probabilistic drop/mark
3 Preventing global synchronization or traffic oscillation
4 Bounded average queue length 5 Accommodating an equitable distribution of packet loss
I Fairness
6 Providing a lower delay or a lower jitter (delay variation)
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 17 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.18
AQM Goals Random Early Detection (RED)
§6.3.3 Random Early Detection (RED) II
1 Uses EWMA Why?
Q =
(1 − Wq)× Q + Wq × Q if Q 6= 0
(1 − Wq)m × Q otherwise, (2)
I Wq determines how rapidly Q w.r.t. Q, I m accounts for the periods when the queue has been empty • m estimates the number of packets that could have been transmitted during an
idle period.
2 Probabilistically drops/marks packets I Marking require ECN bit (RFC 2481)
It uses two thresholds Th and T` to control the growth of the queue
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 18 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.19
AQM Goals Random Early Detection (RED)
§6.3.3 Random Early Detection (RED) III
Q QmaxThTℓ
p
1
0
Pmax
If Q < T` accept the packet If Q ≥ Th mark/drop the packet If T` ≤ Q < Th mark/drop probabilistically with, Pa
(3)
Q is calculated at the packet arrival times I Rather than at a fixed time interval Why?
Within the region [T`, Th), the probability of packet discard depends on the proximity of Q to Th and it is bounded by Pmax When T` ≤ Q < Th, Pb increases linearly from zero to Pmax
Pb = Pmax × (Q − T`) (Th − T`)
(4)
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 19 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.20
AQM Goals Random Early Detection (RED)
§6.3.3 Random Early Detection (RED) IV
To mitigate any bias against bursty traffic, RED uses c, I The number of consecutive packets that have escaped discard, into the
probability of discard
As c increases, the probability of discard also increases I This avoids penalizing bursty traffic by spacing the discards quite evenly
rather than in a cluster
Pa modifies Pb by 11−c×Pb ,
Pa = Pb × 1
1 − c × Pb (5)
Performance I Desynchronization works well ⇑ I Very sensitive to parameter setting ⇓ I Fails to prevent buffer overflow as the number of sources increases ⇓
Over 100 AQM have been developed since RED ⇒ see [1]
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 20 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM AQM
AQM Goals
Random Early Detection (RED)
How about non-responsive sources?
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.21
AQM Goals How about non-responsive sources?
§6.3.4 How about non-responsive sources?
Generally, User Data Protocol (UDP) is non-responsive What routers want to do I Isolate non-responsive flows I Provide Quality of Service to all users Two ways to do that 1 Scheduling algorithms • Fair Queuing (FQ) • Weighted Fair Queuing (FWQ) • Core Stateless Fair Queuing (CSFQ) • Stochastic Fair Queuing (SFQ)
2 Queue management algorithms • RED • Fair Random Early Detection (FRED) • vdots
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 21 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications Classification Based on Congestion Control
Classification By Mechanisms
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.22
AQM Classifications Classification Based on Congestion Control
§6.4.1 Classification Based on Congestion Control
LocalGloba
Responsive Persistent (global)
Implicit feed−back (global)
Explicit
feed−back
Closed loop control
Source control Destination control
Open loop control
AQM Schemes
Open-loop flow/congestion control I No feedback mechanism between the receiver and the transmitter • Maximizing the utilization of network resources
I It has two controls • Controller • Regulator ⇒ alters the input variable in response to the signal from the controller
Closed-loop flow/congestion control I The network/node can report pending network congestion back to the
transmitter I It has some basic control elements • Sensor, controller, regulator, and transmitter
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 22 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications Classification Based on Congestion Control
Classification By Mechanisms
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.23
AQM Classifications Classification By Mechanisms
§6.4.2 Classification By Mechanisms I
Based on Congestion Indicator
Congestion Indicator
Queue-based
Enqueue events only ⇒ RED, GRED,CHOKEe,DRED
Enqueue & Dequeue events ⇒ FRED
Rate-based
Arrival rate ⇒ LUBA,SFED,RARED
Congestion window size ⇒ SHRED
Load-based
Flow count ⇒ GREEN, BLACK, SFED
Traffic composition ⇒ RED Worcester
Packet Loss
Loss volume ⇒ LRED
# of buffer over/under flow events ⇒ BLUE
Mixture {
⇒ Load/Delay controllers, Yellow
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 23 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications Classification Based on Congestion Control
Classification By Mechanisms
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.24
AQM Classifications Classification By Mechanisms
§6.4.2 Classification By Mechanisms II Based on Parameter Tuning
Parameter Tuning
Static {
⇒ RED, GRED
Dynamic
Network Load ⇒ GREEN
Bandwidth × Distance ⇒ - - -
Round-Trip-Time ⇒ GREEN
Link Capacity ⇒ GREEN
Mixture {
⇒ ARED, A-RIO, PSAND
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 24 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications Classification Based on Congestion Control
Classification By Mechanisms
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.25
AQM Classifications Classification By Mechanisms
§6.4.2 Classification By Mechanisms III Based on Flow Differentiation
Flow Differentiation
None {
⇒ RED, GRED
Flow aggregates
Two-class system: (Non)Responsive⇒ Stochastic Fair BLUE, RIO-C
Two-class system: Web vs. FTP⇒ SHRED
Multiple-class system⇒ RIO-DC, WRED,Rb-RIO, D-CBT, SFED
Individual flows
{ ⇒ FRED, BRED, BLACK
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 25 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications Classification Based on Congestion Control
Classification By Mechanisms
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.26
AQM Classifications Classification By Mechanisms
§6.4.2 Classification By Mechanisms IV Based on Control Function
Control Function
Heuristic
Equation-based ⇒ RED, GRED,Hyperbola RED, DSDRED
Non-equation-based ⇒ MRED
Control-Theoretic
Classic and Modern Control ⇒ PI, PD, GPC, PI-PD, PD-PD, ...
Fuzzy Control ⇒ Fuzzy control RED, Adaptive Fuzzy RED, ...
Optimization
Deterministic ⇒ REM, AVQ, SVB
Stochastic ⇒ - - - Neural Networks ⇒ Neural Network-based PID controller
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 26 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications Classification Based on Congestion Control
Classification By Mechanisms
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.27
AQM Classifications Classification By Mechanisms
§6.4.2 Classification By Mechanisms V
Based on Feedback Signal
Feedback Signal
Packet dropping
Random ⇒ RED, GRED, CHOKe, REM, SVB
Deterministic ⇒ AVQ
ECN Marking
Random ⇒ RED, REM, G
Deterministic ⇒ AVQ
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 27 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.28
Bufferbloat in the Internet Bufferbloat in the Internet
§6.5.1 Bufferbloat in the Internet I
Bufferbloat is the existence of excessively large and frequently full buffers inside the network [4], [3] Bufferbloat is due to 1 More available and cheap memory • Resulted in buffer proliferation
2 At the edge buffers become extremely oversized due to • Dynamically varying path characteristics • Link rates and path delays fall below nominal values
Unmanaged large buffers are more critical these days I Delay-sensitive applications are more prevalent I Streaming
Packet networks require buffers to absorb short-term arrival rate fluctuations Buffers tend to fill up and remain full at congested links I Results in excessive traffic delay and packet loss I Missing their intended function to absorb bursts
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 28 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.29
Bufferbloat in the Internet Bufferbloat in the Internet
§6.5.1 Bufferbloat in the Internet II Internet Engineering Task Force (IETF) urged deployment of AQM, specifically RED I But little guide has been available to set its configuration parameters I General reluctance to use it RED weaknesses resulted in more AQMs I Adding more configuration and complexity to the original RED Queue length is not a good predictor of congestion Why? I But research continued but deployment did not
Constant increase in link rate saved the Internet from disaster so far
Studies have shown edge queuing delays from 100’s ms to several seconds This results in harmful effects I Large, unmanaged buffers at the network edge
Correct buffer sizing is not an easy problem
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 29 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.30
Bufferbloat in the Internet Bufferbloat in the Internet
§6.5.1 Bufferbloat in the Internet III
Undersizing ⇒ Buffer < Bandwidth × delay (BDP) problems I Real links contain a complex mix of flow connection lengths and round-trip
times I Traffic patterns change significantly w.r.t buffer sizing requirements over
time • This makes it impossible to properly pick a static buffer size for most edge links
I It is important to distinguish between links at which TCP flows experience packet loss and those where they do not Why? • Packet loss is an important aspect of link quality • It also affects the required queue size • Links vary in bandwidth and individual connections vary in shaderound-trip
times How? K This makes it impossible to properly pick a static queue size for most edge
links
Oversizing ⇒ Buffer > BDP relevancy I A simple, robust algorithm that can manage buffer delay regardless of
buffer size and link bandwidth without a negative impact on utilization can make oversized buffers irrelevant [3] Why?
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 30 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.31
Understanding Queues Understanding Queues
§6.6.1 Understanding Queues I
Misconceptions about the cause and meaning of queues hamper developing an effective AQM Queues exist to absorb arrival fluctuations and packet bursts I Naturally exist in statistical multiplexing I Short-term between arrival and departure rates • Many scenarios in network or user behavior
An example: I Vertical direction is bandwidth (b/s) • Source 100 Mbps, Wc = 25 • Bollteneck 10 Mbps
I Horizontal direction is time(s) • Shorter in the queue • Longest in the Bollteneck
I After 1 RTT, the input is regulated • Same arrival/departure at bottleneck • The queue won’t grow ⇒ lock step • Different packet-time
K Packets are longer, but back-to-back in the bottleneck
(a) Initial setup
(b) After one round trip,each Ack becomes a packet
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 31 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.32
Understanding Queues Understanding Queues
§6.6.1 Understanding Queues II
Note that the steady-state queue size is not zero Why? I The distance in time between the sender and receiver is 10 bottleneck
packet times I We have 10 bottleneck packet time How? The standing queue has nothing to do with the senders rate I but rather with how much the senders window exceeds the pipe size I The standing queue resulting from a mismatch between the window and
pipe size, is the essence of bufferbloat
• It creates large delays but no improvement in throughput
The bufferbloat problem that makes the window to much the pipe size is hard to address Why? I Window size is chosen by the sender, queue manifest at bottleneck
gateways
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 32 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.33
Understanding Queues Understanding Queues
§6.6.1 Understanding Queues III Choosing window size is difficult to compute Why? I Bottleneck bandwidth and RTT change constantly How? • Connections come and go • Paths change due to re-routing • L1 and L2 bandwidth change due to physical conditions
The most promising approach is to detect the queue size and signal the source I Via TCP congestion control Reliable detection is difficult I The big queue is necessary for connections to get started Why?
Ack per packet or Ack per window?
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 33 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.34
Understanding Queues Understanding Queues
§6.6.1 Understanding Queues IV
While the queues are dong their job (shock absorber), the tail indicate they create excess delay How to distinguish between a good/bad queue? I Good queue ⇒ occupancy goes away after one RTT ⇒ no bufferbloat • Temporary increase in queue delay • High utilization
I Bad queue ⇒ occupancy persist for several RTT’s ⇒ bufferbloat • Low utilization • High buffer delay.
How to separate the two? Take the minimum queue length over a sliding time window that is longer than the nominal RTT I It keeps the pipe full with minimum delay
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 34 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management Controlled Delay Management
CoDel Algorithm
References
6.35
Controlled Delay Management Controlled Delay Management
§6.7.1 Controlled Delay Management I
RED is very sensitive to parameter setting ⇓ A modified version needed only one parameter; the queue output bandwidth I Or average departure rate Despite better performance, the issues remain the same I Almost anything worked for long-lived TCP I Nothing worked for bursty traffic
What kind of AQM do we need? 1 Parameterless ⇒ has no knobs to operate/adjust 2 Treats good queue and bad queue differently
I Keeps the delays low while permitting bursts of traffic 3 Controls delay, but insensitive to:
I RTT I Link rates, and I Traffic loads
4 Adapts to dynamically changing link rates with no negative impact on utilization
5 Simple and efficient I Spans across various link speeds • From home routers up to high-end commercial routers
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 35 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm CoDel Algorithm
References
6.36
CoDel Algorithm CoDel Algorithm
§6.8.1 CoDel Algorithm I A Controlled Delay Management with 3 major characteristics 1 Parameterless: It is not based on queue size, queue-size averages,
queue-size thresholds, rate measurements, RTT link utilization, drop rate or queue occupancy time
2 Uses local minimum delay ⇒ a more accurate and robust measure • A single variable determines how long the minimum has been above or below the
target value
3 It uses the actual delay experienced by each packet which is independent of link rate
CoDel timestamps each packet on ingress
It calculate the queuing latency upon packet departure Dq It compares min Dq’s during the interval with target delay D∗q ( 5 ms), sets d = 100 ms I If them minimum delay is less than the target delay, then • resets the count • forwards the packet
I Else if the drop time has expired, then • drops the packet, • increment the count, • schedule the next drop time as current time + d/sqrtcount
I Else forwards the packet
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 36 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm CoDel Algorithm
References
6.37
CoDel Algorithm CoDel Algorithm
§6.8.1 CoDel Algorithm II
Local min > target delay?
Current time >= Drop time
Dequeue next packet
Drop current packet
Increment count
Schedule next time to drop
= current time + interval/sqrt(count)
Yes
No
No
Yes
Reset count
Forward packet
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 37 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm CoDel Algorithm
References
6.38
CoDel Algorithm CoDel Algorithm
§6.8.1 CoDel Algorithm III
Algorithm 1: CoDel
Initialization: D∗q = 5(ms), // Packet delay target time d = 100(ms), // Drop interval Tc , // Current time Dt , // Drop time Ta , // Packet arrival time Dq = Tc − Ta , // Packet queuing delay Dm , // Minimum sojourn time seen in the current time interval Ti
repeat Dequeue next packet; Compute packet queuing delay Dq = Tc − Ta ; // local time - arrival time; Dm = min{Dq|Dq ∈ Dt}; // Find minimum packet delay during the interval; if Dm > D
∗ q then
if Tc ≥ Dt then Drop the packet; Dt = Tc + d/
√ n; // Reduce the drop interval;
n++; // Increment the count; end else
Forward the packet; end
end else
n = 1 // Reset the count; Forward the packet;
end until ;
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 38 / 39
Active Queue Management
Acronyms
Introduction
Traffic Engineering
AQM
AQM Classifications
Bufferbloat in the Internet
Understanding Queues
Controlled Delay Management
CoDel Algorithm
References
6.39
References
§6.9.0 References
[1] Richelle Adams. Active queue management: A survey. IEEE Communications Surveys and Tutorials, 15(3):1425–1476, 2013. [PDF].
[2] Sally Floyd and Van Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Netw., 1(4):397–413, 1993. [PDF].
[3] Kathleen Nichols and Van Jacobson. Controlling queue delay. Communications of the ACM, 55(7):42–50, July 2012. [PDF].
[4] Kathleen Nichols and Van Jacobson. Controlling queue delay. Queue, 10(5):20:20–20:34, May 2012. [PDF].
(CS 6/75995: ST: Advances in Networks) Active Queue Management Summer 2014 39 / 39
- Introduction
- Introduction
- The Role of AQM
- Traffic Engineering
- Traffic Engineering
- What is Congestion
- Congestion Control
- Implicit vs. Explicit feedback
- TCP Congestion Control
- AQM
- AQM
- AQM Goals
- Random Early Detection (RED)
- How about non-responsive sources?
- AQM Classifications
- Classification Based on Congestion Control
- Classification By Mechanisms
- Bufferbloat in the Internet
- Bufferbloat in the Internet
- Understanding Queues
- Understanding Queues
- Controlled Delay Management
- Controlled Delay Management
- CoDel Algorithm
- CoDel Algorithm
- References
