Congestion Control in TCP
Overview of RENO TCP Reacting to Congestion AIMD and alternatives
• How fast should a sender transmit data? – Not too fast, not too slow, just right …
Copyright By PowCoder代写 加微信 powcoder
• Should not be faster than the sender’s share – Bandwidth allocation
• Should not be faster than the network can process – Congestion control
• Congestion control abd bandwidth allocation are
separate ideas, but frequently combined
How much bandwidth should each flow from a source to a How much allocation should each flow from a
Bandwidth Allocation
Bandwidth allocation
Destination 1
Destination 2
destination receive when they compete for resources?
source to a destination receive?
◆ What is a fair allocation? – What is “fair”?
CSE 123 – Lecture 11: Congestion Control
Statistical Multiplexing
• Bigger the buffer, lower the packet loss – But should we just plan to have big buffers?
• If buffer never goes empty, the outgoing line is busy 100% of time
Congestion
Congestion
1.5-Mbps T1 link
Packets dropped here
Destination
Buffer intended to absorb bursts when input rate > output But if sending rate is persistently > drain rate, queue builds
Buffer’s goal to absorb bursts when input rate > output
But if sending rate is persistently > drain rate, queue
Dropped packets represent wasted work; goodput < throughput
builds, eventually drops
Dropped packets represent wasted work
CSE 123 – Lecture 11: Congestion Control
10-Mbps Ethernet
Hosts send packets as fast as advertised window allowe When packets dropped, hosts retransmit causing more
Goodput = useful bits delivered per unit time Excludes header overhead, retransmissions, etc.
Congestion Collapse
When increase network load produces descrease in useful work
- Sender sends faster than bottleneck link
- Packets dropped
- Sender transmits, adding to congestion
In 1986, the NSF backbone dropped from 32 Kbps to 40 bps CS 640 6
How to mitigate?
• Increase network resources – More buffers?
– Increase link speed?
• Reduce network load – Send data slower
– How much slower?
– When to slow down?
Detecting Congestion
• Explicit congestion signaling
– Source quench: ICMP message from router to sender
– DECBit/Explicit Congestion Notification (ECN):
• Router marks packet based on queue occupancy (for packets encountering “congestion” on the way)
• Receiver conveys such info back to the sender
• Implicit congestion signaling (used by TCP)
– Packet loss
• Assume congestion is a primary source of packet loss
– Packet delay
• RTT increases as packets queue
Throttling options
• Window-based (TCP)
– Constrain number of outstanding packets allowed in network – Increase window to send faster; decrease to send slower
– Pro: Cheap to implement, good failure properties
– Con: Creates traffic bursts (requires bigger buffers)
• Rate-based (many streaming media protocols)
– Two parameters (period, packets)
– Allow sending of x packets in period y
– Pro: smooth traffic
– Con: fine-grained per-connection timers, what if receiver fails?
Basic TCP algorithm
• Window-based congestion control
– Unified congestion control and flow control mechanism
– AWnd: advertised flow control window from receiver
– CWnd: congestion control window
• Estimate of how much outstanding data network can deliver in a
round-trip time
– Sender can only send MIN(AWnd,CWnd) at any time
• Idea: decrease CWnd when congestion is encountered; increase CWnd otherwise
– Question: how much to adjust?
TCP Congestion Control
• The source estimates how much capacity is available in the network, so that it knows how many packets it can safely have in transit.
– Once a given source has this many packets in transit, it uses the arrival of an ACK as a signal that one of its packets has left the network, and that it is therefore safe to insert a new packet into the network without adding to the level of congestion.
– By using ACKs to pace the transmission of packets, TCP is said to be self-clocking.
TCP Congestion Control
• In more detail
– assumes best-effort network (FIFO or FQ routers) each source determines network capacity for itself
– uses implicit feedback
– ACKs pace transmission (self-clocking)
• Challenge
– determining the available capacity in the first place – adjusting to changes in the available capacity
Congestion Control Overview
• Objective: adjust to changes in the available capacity
• New state variable per connection: CWnd
– limits how much data source has in transit
MaxWnd = MIN(CWnd,AWnd)
EffWnd = MaxWnd - (LastByteSent -
LastByteAcked)
– increase CongestionWindow when congestion goes down
– decrease CongestionWindow when congestion goes up
TCP RENO Overview
• SlowStartphase
• Congestion avoidance phase
– Additive Increase/ Multiplicative Decrease (AIMD) – Fast Retransmit/Fast Recovery
Slow Start
• Objective: determine the available capacity in the first
– Additive increase is too slow
• One additional packet per RTT
– begin with CWnd = 1 MSS
– double CWnd each RTT (increment by 1 MSS for each ACK)
– This is exponential increase to probe for available bandwidth
• If loss “detected” set SSThresh = CWnd/2, and exit current Slow Start
Destination
Slow Start contd.
• Exponential growth, but slower than all at once
– when first starting connection
– when connection goes dead waiting for timeout
1.0 2.0 3.0
6.0 7.0 8.0 9.0
• Problem: lose up to half a CongestionWindow’s worth of data
How to detect loss?
• One way is by a Timeout – SetCWnd=1
• SSThresh and CWnd always >= 1 MSS
• As long as CWnd < SSThresh, do Slow Start, else do
Congestion Avoidance
• There is another way (coming up soon)
Congestion Avoidance
• Algorithm
– increment CWnd by one packet per RTT
Destination
In practice: increment a little for each ACK
(linear increase)
– CWnd always >= 1 MSS
Increment = 1/CWnd
CWnd += Increment
(MSS = max segment size = size of a single packet)
Basic MechaOnviesrmviesw
18 16 14 12 10
Slow Start + Congestion Avoidance
Congestion avoidance
Slow start
round-trip times
CSE 123 – Lecture 11: Congestion Control
We can detect losses sooner
• Fastre-transmit
– Timeouts are slow
– When packet is lost, receiver is still receiving ACKs
– Use 3 duplicate ACKs to indicate a loss
Fast Retransmit Example
Fast recovery (increase cwnd by 1)
Fast retransmit
CSE 123 – Lecture 11: Congestion Control
Ack 3 Ack 4
Ack 4 Ack 4 Ack 4
Fast recovery
• Goal: avoid stalling after loss
• If there are still ACKs coming in, then no need for slow start
• If a packet has made it through -> we can send another one
• Divide cwnd by 2 after fast retransmit
• Increment cwnd by 1 MSS for each additional
duplicate ACK
• Once you get new ACK, move to congestion
More Sophistication
18 16 14 12 10
Slow Start + Congestion Avoidance + Fast Retransmit + Fast Recovery
Fast recovery
round-trip times
CSE 123 – Lecture 11: Congestion Control
What is TCP’s sending rate?
Destination
• Roughly WindowSize / RTT
• Sender can roughly send one WindowSize worth of data before and no more, until the first acks come back
Additive Increase Multiplicative Decrease (AIMD)
• The new congestion avoidance phase – Which is where we will mostly be
– If an ACK is received: CWnd = CWnd + 1/CWnd • Adding 1 MSS per RTT (CWnd = CWnd + 1 every RTT)
– If a packet is lost (3 dup acks): CWnd = CWnd/2 • Halving on each loss
• Trace: sawtooth behavior
AIMD (cont)
3.0 4.0 5.0 Time (seconds)
6.0 7.0 8.0
Fast Retransmit and Fast Recovery
• Problem:coarse-grain TCP timeouts lead to idle periods
• Fastretransmit:use3 duplicate ACKs to trigger retransmission
• Fast recovery: start at SSTHRESH and do additive increase after fast retransmit
Packet 1 Packet 2
Packet 3 Packet 4
Packet 5 Packet 6
Retransmit packet 3
ACK 1 ACK 2
ACK 2 ACK 2
Fast Retransmit Results
5.0 6.0 7.0
• This is a graph of fast retransmit only – Avoids some of the timeout losses
• Fast recovery
– skip the slow start phase in this graph at 3.8 and 5.5 sec
– go directly to half the last successful CongestionWindow (ssthresh)
• TCPSlowStart:
– On each new ack:
• CW = CW + 1 (MSS)
• TCP Congestion Avoidance
– On each new ack:
• CW = CW + 1/CW (in MSS)
– On triple dupack
• SSThresh = CW/2
• CW = CW + 3 (MSS)
– On timeout
• CW = 1 (MSS)
In summary
– On each additional dupack • CW = CW + 1 (MSS)
– On new ack
• CW=SSThresh
More on TCP Congestion Control
TCP Congestion Control
• Very simple mechanisms in network – FIFO scheduling with shared buffer pool – Feedback through packet drops
• End-host TCP interprets drops as signs of congestion and slows downàreduces size of congestion window
• But then, periodically probes – or increases congestion window
– To check whether more bandwidth has become available 30
Congestion Control Objectives
• Simplerouterbehavior
• Distributed-ness
• Efficiency: Sxi(t) close to system capacity
• Fairness:equal(orpropotional)allocation
– Metric = (Sxi)2/n(Sxi2)
• Convergence:controlsystemmustbestable
Linear Control
• Many different possibilities for reaction to congestion and probing
– Examine simple linear controls
• Window(t + 1) = a + b Window(t)
• Different ai/bi for increase and ad/bd for decrease
• Various reaction to signals possible – Increase/decrease additively
– Increased/decrease multiplicatively
– Which of the four combinations is optimal?
• Consider two end hosts vying for network bandwidth
Four alternatives
• AdditiveIncreaseAdditiveDecrease(AIAD)
• AdditiveIncreaseMultiplicativeDecrease (AIMD)
• MultiplicativeIncreaseAdditiveDecrease (MIAD)
• MultiplicativeIncreaseMultiplicativeDecrease (MIMD)
• So why pick AIMD?
Additive Increase/Decrease
• Both X1 and X2 increase/ decrease by the same amount over time
– Additive increase improves fairness and additive decrease reduces fairness
Fairness Line
Allocation T0
Efficiency Line
User 1’s Allocation x1
Multiplicative Increase/Decrease
• Both X1 and X2 increase by the same factor over time
– Extension from origin – constant fairness
Fairness Line
User 2’s Allocation
User 1’s Allocation x1
Efficiency Line
Convergence to Efficiency
User 2’s Allocation x2
Fairness Line
Efficiency Line
User 1’s Allocation x1
Distributed Convergence to Efficiency
Fairness Line
User 2’s Allocation x2
Efficiency Line
User 1’s Allocation x1
Convergence to Fairness
User 2’s Allocation x2
Fairness Line
Efficiency Line
User 1’s Allocation x1
Convergence to Efficiency & Fairness
• Intersection of valid regions
• For decrease: a=0 & b < 1
Fairness Line
User 2’s Allocation x2
Efficiency Line
User 1’s Allocation x1
What is the Right Choice?
• Constraintslimit us to AIMD
– Can have multiplicative term in increase (MAIMD)
– AIMD moves towards optimal point
Fairness Line
User 2’s Allocation x2
Efficiency Line
User 1’s Allocation x1
Exponentially Weighted Moving Average
Smoothing of data
Smoothing of data
• Simple moving average
Smoothing of data
• Weighted moving average
Smoothing data
• Exponentially Weighted Moving Average (EWMA)
Smoothing data
• Exponentially Weighted Moving Average (EWMA)
Accelerometer
1425154905000. 001425154910000. 001425154915000. 001425154920000. 001425154925000. 001425154930000. 001425154935000. 001425154940000. 001425154945000. 001425 -2
Alpha = 0.8
Alpha = 0.5
Congestion avoidance
• Howdoesthesourcedeterminewhetherornotthe network is congested?
• Answer:apacketlossisdetected
– Either through a timeout
• timeoutsignalsthatapacketwaslost
• packets are seldom lost due to transmission error • lostpacketimpliescongestion
• RTO calculation is critical
– Or through duplicate acks (triple)
Alpha = 0.2
Alpha = 0.1
S eri e s1 S eri e s2 S eri e s3
1425154918000.00 1425154920000.00 1425154922000.00 1425154924000.00 1425154926000.00 1425154928000.00 1425154930000.00
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com