# 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??
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://sliu583.gitbook.io/blog/networking/index/cs-268-adv-network/congestion-control.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.