> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/networking/index/cs-268-adv-network/congestion-control.md).
# 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??