Congestion Control
简单理解一下congestion control
Congestion control
Congestion: "too many sources sending too much data too fast for network to handle"
Manifestations
Long delays (queueing in router buffers)
Packet loss (buffer overflow at routers)
Different from flow control
One sender too fast for one receiver
Causes / costs of congestion: scenario 1
Simplest scenario
One router, infinite buffers
Input, output link capacity: R
Two flows
No retransmissions needed
Another scenario
One router, finite buffer
Sender retransmits lost, timed-out packet
Application-layer input
Transport-layer input includes retransmissions
Perfect knowledge: sender sends only when router buffers available
Or some perfect knowledge
Packets can be lost (dropped at router) due to full buffers
Sender knows when packet has dropped: only resends if packet known to be lost
Relasitic scenario: un-needed duplicates
Packets can be lost, dropped at router due to full buffers - requiring retransmissions
But sender times can time out prematurely, sending two copies, both of which are delivered
Costs of congestion
More work (retransmission) for given receiver throughput
Unneeded retransmissions: link carries multiple copies of the packet
Decreasing maximum achievable throughput
When packet dropped, any upstream transmission capacity and buffering used for that packet was wasted!
Insights
Throughput can never exceed capacity (link)
Delay increases as capacity approached
Loss / retransmission decreases effective throughput
Un-needed duplicates further decreases effective throughput
Upstream transmission capacity / buffering wasted for packets lost downstream (congestion collapse)
Apporaches towards congestion control
End-to-end congestion control
No explicit feedback from network
Congestion inferred from observed loss, delay (i.e. timeout, ACKs)
Approach taken by TCP
Network-assisted congestion control
Router provide direct feedback to sending / receiving hosts with flows passing through congested router
May indicate congestion level or explicitly set sending rates
TCP ECN, ATM, DECbit protocols
TCP Congestion control: AIMD
approach: senders can increase sending rate until packet loss (congestion) occurs, then decreasing sending rate on loss event
Additive increase: increase sending rate by 1 maximum segment size every RTT until loss detected
Multiplicative decrease: cut sending rate in half at each loss event
Cut in half on loss detected by triple duplicate ACK (TCP Reno)
Cut to 1 MSS (maximum segment size) when loss detected by timeout (tcp Tahoe)
AIMD: probing for bandwidth
A distributed, async algorithm - has been shown to
Optimize congested flow rates network wide
Have desirable stability properties
Implementation
Sender sequence number space
TCP sender limits transmission: LastByteSent - LastByteAcked <= cwnd
cwnd is dynamically adjusted in response to observed network congestion
TCP slow start
When connection begins, increase rate exponentially until first loss event
TCP from slow start to congestion avoidance
When should the exponential increase switch to linear?
When cwnd gets to 1/2 of its value before timeout
Implementation
Variable ssthresh
On loss event, ssthresh is set to 1/2 of cwnd just before loss event
TCP CUBIC
Is there a better way than AIMD to "probe" for usable bandwidth?
Insight / intuition
W_max: sending rate at which congestion loss was detected
Congestion state of bottleneck link probably (?) hasn't changed much
After cutting rate / window in half on loss, initially ramp to W_max faster, but then approach W_max more slowly
Operation
K: point in time when TCP window size will reach W_max
K itself is tunable
Increase W as a functino of the cube of the distance between current time and K
Larger increases when further away from K
Smaller increases when nearest K
Default in Linux, most popular for web services
TCP and the congested "bottleneck link"
TCP (classic, CUBIC) increase TCP's sending rate until packet loss occurs at some router's output: the bottleneck link
Understanding congestion: useful to focus on congested bottleneck link
Goal: keep the end-end pipe just full, but not fuller
Delay-based TCP congestion control
Keeping sender-to-receiver pipe "just full enough"
RTT_min - minimum observed RTT (uncongested path)
Uncongested throughput with congestion window cwnd is cwnd / RTT_min
BBR deployed on Google's (internal) backbone network
Explicit congestion notification (ECN)
TCP deployments often implement network-assisted congestion control
Two bits in IP header (ToS field) marked by network router to indicate congestion
policy to determine marking chosen by network operator
Congestion indication carried to destination
Destination sets ECE bits on ACK segment to notify sender of congestion
both IP (IP header ECN bit marking) and TCP (TCP header, C,E bit marking)
Fairness
Fairness goal: if K TCP sessions share the same bottleneck link of bandwidth R, each should have average rate of R / K
Is TCP fair?
Example: two competing TCP sessions
Additive increase gives slope of 1, as throughput increases
Multiplicative decrease decreases throughput proportionally
Fairness and UDP
Multimedia apps often do not use TCP
Do not want rate throttled by congestion control
Instead use UDP
Send audio / video at constant rate, tolerate packet loss
There is no "Internet police" policing use of congestion control
Fairness, parallel TCP connections
Application can open multiple parallel connections between two hosts
Web browsers do this, e.g., link of rate R with 9 existing connections
New app asks for 1 TCP, gets rate R / 10
New app asks for 11 TCP, gets rate R / 2
Is it fair??
Last updated
