COMP3310/6331 – #19
Flow control and congestion
Dr Markus Buchhorn: markus.buchhorn@anu.edu.au
Where are we?
• Going back into the dark layers
Application Presentation
Session Transport
Network
Link (Ethernet, WiFi, …)
Physical (Cables, Space and Bits)
Messages
Segments
Packets Frames
Bits
2
Remember (TCP) Sliding Windows?
• Want reliability and throughput – and fill pipes! • Start with ARQ – stop-and-wait
– Single segment outstanding = problem on high bandwidth*delay networks
• Say one way delay=50ms so round-trip-time (RTT)=2d=100ms • Single segment per RTT = 10 packets/s
• Typical packet on Ethernet? Say 1000 bytes = ~10,000 bits -> 100kb/s or 10% of link • Even if bandwidth goes up, throughput doesn’t!
3
Sliding Windows
• Allow W segments to be ‘outstanding’ (unACKed) per RTT – Fill a pipeline with segments
• Set up a ‘window’ of W segments – per connection
• W=2*Bandwidth*delay
• At 100Mb/s, delay=50ms means W=10Mb
– and assuming same 10kb segments, W=1000 segments – 500 are on their way out there!
4
Sliding Window approach
Sender buffers up W segments until they are ACKed Seq# Available
Ack
ed
Un-Acked
Waiting
Window not full, so send a packet
Destination
Packet ACKed, so Window not full
Application
W=5
Acked
Un-Acked
Waiting
Available
Acked
Un-Acked
Waiting
5
If(lost) then: ARQ – “Go Back N”
• Receiver buffers just a single segment
• If it’s the next one in sequence, ACK it, everyone happy • If it’s not, drop it, I just don’t care
• Let sender retransmit what I’m actually waiting for
• Sender has a single timer. After timeout, resend • Really simple, but somewhat inefficient
1
2
3
4
5
6
ARQ – “Selective Repeat”
• Receiverbuffersmanysegments – Reduceretransmissions
• ACKwhathasbeenreceivedinorder
• AndalsoACKsegmentsthathaven’t – Anygapsindicatesmissingsegment!
– SelectiveACK(SACK)
• SenderhasatimerperunACKed-segment – Aseachtimerexpires,resendthatsegment
• Waymoreefficient,nowwidespread
ACK SACK
1
2
3
4
5
7
Very sender/network oriented
• Sender manages the transmission – UDP – send-and-forget, no control – TCP – Slows down waiting for ACKs – Optimised to keep network full
– What about the receiver application?
• Consider Receiver being swamped
– HD video streaming to small device – it needs to control the flow
8
Flow Control:
Sliding Windows on the Receiver side
• Transport layer:
– receives the segment from the network – and adds it to application buffer
• Application calls recv(N-bytes) to read from buffer – But what happens if the application is slow?
Receiver Window
Seq#
ACK
ACK
ready
ready
ready
9
Sliding Windows on the Receiver side
• More segments arrive, fill (TCP) buffer – and eventually application recv()s Seq#
Window
ACK
ACK
ready
ready
ready
ACK
ACK
ACK
ACK
ACK
ACK
ACK
ACK
ready
ready
10
Two windows to get through?
• TCP Sender Sliding Window (W) – Both sides know
• Receiver Sliding Window = Flow Control Window (WIN) – Number of “ACCEPTABLE” segments to be sent
Window
Flow-control Window
• Sender gets told WIN and uses lower of W and WIN as the ‘effective’ window 11
ACK
ACK
ready
ready
ready
A little simpler
• Sequence numbers identify where sender is up to • Acknowledgements where receiver is up to
• But receiver can also report buffer available
• Simple Flow Control
12
Congestion
• A traffic jam – something filled up and is holding up the rest – A dynamic condition
– Somewhere (unknown) along the (unknown) path
• Senders keep sending
– Makes it worse, for themselves, and everybody else – Congestion -> loss
• It is not the links that “cause” loss (by being congested) – They run at a specific clock, bits in/bits out.
– They set the limits
13
Routers/switches
• Too many inputs for the one output 100Mb/s
100Mb/s 100Mb/s
100Mb/s
14
OUT BUFFERS
IN BUFFERS
Router Buffers: Queues…
• FIFO (First in, First out) queues on every interface • Great for absorbing (short) bursts of traffic
– Data-rate in > data-rate out
• For a while… then queue overflows, and packets get dropped
• Largely driven by traffic patterns
– Multiple conversations randomly sending to the same path at the same time – Assuming similar bandwidth links in/out
15
Congestion Effects
Delay ms
realistic
collapse
New load Pkts/sec
Path capacity
“Goodput” Pkts/sec
ideal
collapse
ideal
New load Pkts/sec
16
Why???
• Rising load fills buffers – Delays go up
• Overflowing buffers drop packets – Loss rises
• What do the receivers do? – ASK FOR RETRANSMISSION
• What do the senders to? – RETRANSMIT
• Network fills with retransmitted packets, new packets are held back – Goodput goes to zero
17
Managing capacity
• Want to operate (just) below congestion damage – Use the network to nearly “capacity”
• Need to allocate total capacity:
• Efficiently: get as much as I can, without causing congestion and
• Fairly: everyone gets a reasonable share
18
Who handles that?
• To be effective, both Transport and Network layers have a role
• Network layer (IP) sees congestion – It’s happening in the routers’ buffers – And it could provide feedback
• Transport layer causes congestion! – But can’t see where.
– It can back off on transmissions
19
Isn’t it statistical multiplexing?
• Could allow all senders just to fight it out – eventually it’s even? – The very big and the very small
– Problem: in congestion everybody loses.
• This is hard:
– Different applications have different behaviours
• cat video vs security sensor
– Load is constantly changing
– Congestion may be happening in multiple, different, places – There is no central view
• Need to find solution(s) where:
– Senders adapt concurrently and continuously? – We can make it efficient and fair?
(time)
(space) (everyone’s blind)
20
Fairness and Efficiency
• What’s fair?
• Sometimes can’t have both…
AB
C
Fair…
AB
0.5
BC
0.5
AC
0.5
Total: 1.5
Efficient…
AB
1
BC
1
AC
0
Total: 2.0
21
“Equal per flow” fairness?
• AC uses twice the network of AB, BC – is that fair?
• Exact fairness is hard. Avoiding full starvation (AC=0) is more important
– Some starvation might be ok… AB
C
22
Network bottlenecks – unequal paths
• AC is choked by A-B link. BC is choked by B-C link • So now what’s fair?
C
A 1Mb/s B 100Mb/s
23
Max-Min Fairness
• Allocating bandwidth such that :
• “increasing the rate of one flow will decrease the rate of a smaller flow”
– “Maximising the minimum” – keep adding, and sharing what’s left. A
A 123B
B C
D
4
56
C D
24
Max-Min Fairness
• Start from zero. Increase bandwidth of A,B,C,D till something bottlenecks – R4-R5 fills at 1/3 each for B,C,D. Hold them down. What’s left to raise?
– A…cangoupto2/3,onR2-R3
A
A 123B
B C
D
4
56
C D
A=2/3, B=1/3 A=1/3, B=1/3
C=1/3, D=1/3
25
Max-Min Fairness
• SoA=2/3.B,C,D=1/3
• R2-R3 and R4-R5 are full. Other 3 have unused capacity.
A
A
1
A=2/3, B=1/3
23
B
B
C
C
4
56
C=1/3, D=1/3
D
D
26
And adapt over time
27
So how to adapt?
1. 2. 3.
Open/Closed loop
– Open: reserve a circuit ahead of time – Closed: adjust on feedback
Host or Network driven
– Host manages the allocation (use)
– Network policing is strong, but inflexible
And “allocate” bandwidth: Rate based or Window based – Tell application to send at a specific rate, or
– To watch window sizes
• TCP is Closed-Loop, Host-Driven, Window-Based
28
Two layers, working together
• Network layer (IP) provides feedback on allocation? – Actually, it indicates congestion
• Transport layer (TCP) modifies sender behaviour – TCP window sizes get adjusted
– Dynamically, in response
– This is a ‘control law’
• Additive Increase, Multiplicative Decrease (AIMD)
– Senders additively increase rate, while no congestion (gently, gently)
– Senders multiplicatively decrease rate when there is congestion (quickly, quickly!)
29
AIMD Sawtooth
• Slowly increase to probe the network – Multiple small steps that add to the rate
• Quickly decrease to avoid congestion collapse – Single(+) large percentage decrease
Sender rate Pkt/sec
Time
30
Nice features
• Converges to a fair and efficient allocation when all hosts run it – And everyone(*) does, with some parameter variations
– Doesn’t care about the topology
• Works effectively compared to other control laws
– Slow decrease=bad, fast increase=bad, both slow=bad, both fast=bad
• Just needs a single signal from the “network” (actually, receiver) – Path is congested, or not.
31
How does the network signal the sender?
Remember – multiple TCP implementations, by OS and date and …
Signal
Pros/Cons?
Packet loss
• Really obvious
• Don’t detect congestion till it happens
Packet delays
• Detect congestion earlier
• Detection is more inferred than actual
Router signal
Explicit Congestion Notification (ECN)
• Detect congestion earlier
• Needs the affected router and hosts to support it
32
Implementing AIMD
• What are the best numbers for increase/decrease?
• Several components in TCP contribute – let’s focus on a few. • Start with ACK clocking…
Segments…
ACKs…
33
ACK clocking process
• High-speed link, talking to low-speed (or congested) link
• Sender sends a burst of packets to destination (to router with big buffer) – Doesn’t know any better!
34
ACK clocking process
• Packets get buffered, and
• Low-speed link takes longer – packets get ‘longer’
35
ACK clocking process
• ACKs returned at rate of slowest link! • Sender learns to back off
36
ACK clocking process
• Sender matches ACK rate. Buffers can drain – congestion avoided
• Bursty traffic has become a smoother stream
• And we get a new measure – the ‘Congestion Window’ (CWND)
– Smaller than W (=2*B*delay). [and not related to Flow-control Window (WIN)]
37
Getting started
• On initial TCP connection, what is CWND?
– Guess? Too many variables (bandwidth, delay, congestion, …) – Pick something? Could be way under, or over.
• TCP Additive Increase (on start):
– Start with CWND of N bytes (~1 packet).
– Every round trip without loss, make CWND bigger by 1 packet
• Increase very gently, but it could be a long time to reach the ideal CWND – Whatever it currently is…
• Want an algorithm for TCP CWND growth to start a bit faster – and it’s called… 38
TCP Slow-Start…
• Instead of adding, double CWND every RTT (1,2,4,8,…)
• Start slow, but quickly reach high CWND
fixed
Slow Start
Additive Increase
Time
39
Slow-start overshoot
• Get to the right CWND more quickly
• But will still go (suddenly) over it
– Get packet loss/feedback
– Multiplicative decrease (big drop in CWND)
• So combine Slow-Start with Additive Increase:
– Initial connection, get MD’d down. Below right CWND, but still close? – Define a threshold: ss-thresh = 1⁄2 * CWND(@loss)
– Stop doubling, start adding
40
Combined behaviour…
• After the first overshoot… • Start with slow-start
• Move to A.I. phase
• Gets you there quicker
• Keeps you there longer – Within that good
Ssthresh/CWND band
– Trying to maximise performance, politely.
fixed
CWND
SSthresh
A.I.
Slow Start A.I. Time
41
Fast Retransmit
• Loss -> timeouts
• If timeout is too long, lose ACK clock
– Start all over again, with a CWND’s of packets out. – Slow start (CWND=1) then additive increase – ugh
• Recall ACKs (Seq#) are cumulative, sequential
ACK SACK
1
2
3
4
5
– If packet is lost, but later ones arrive, receiver sends a duplicate ACK
– “New data arrived, but it wasn’t the next segment” • Probably the next segment is lost
– Third duplicate ACK triggers a resend of Seq#+1 (lost?) segment: Fast Retransmit • Hopefully repairs the single-segment loss quickly
• And ACK Seq# catch up with what’s been sent before loss?
42
Fast Recovery
• Had loss, so still need to multiplicative-decrease the CWND
• Also have to wait for receiver to tell you where it’s Seq# is up to.
• Hang on:
– Additional (duplicate) ACKs are arriving = receiver got more segments • Probably the next one(s)!
• And they maintain the ACK clock
– Take a chance: advance the sliding window as if everything is ok (count ACKs) • MD the CWND (1⁄2 it!) and then continue sending (Fast Recovery)
– Somewhat slower, but hopefully little loss, and no re-start. • Receiver will sort things out and let you know (ACK)
43
TCP Reno
• Fairly common TCP codebase (1990s)
44
And beyond?
• TCP Reno
– Can repair one loss per RTT
– Multiple losses = timeout = (slow) start all over
• TCP NewReno
– Better ACK analysis
– Can repair multiple losses per RTT
• TCP SACK
– Far better!
– Receiver sends ACK ranges (set) – sender can retransmit without guessing
45
Can routers help?
• Explicit Congestion Notification
– Still being deployed (routers and hosts) – only standardised in 2001…
• TCP drives network to congestion, then backs off – Prefer to detect congestion (well) before it happens
• Really simple, with in-band signalling
1. Routernoticesqueuesgettingfull
2. Marks packets in queue (ECN “congestion looming” – IP header)
3. Forwardsontoreceiver
4. ReceivermarksTCPsegmentssentbacktoSender(ACKornormal)
5. Sendernotices,andbacksdown(MDofCWND)
6. Noadditionalpacketsneeded!
46
And more router help
• Haven’t yet discussed
– Quality of Service, Differentiated Services
– Traffic Shaping and Policing
– Fair queuing
– Rate and Delay guarantees
– Software Defined Networking
– And how they interact with routing and administrative domains
• And won’t!
• All “managing” packets randomly running through a network – Non-trivial…
47