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??