Buffers and Protocols

Geoff Huston
APNIC Labs

The Evolution of Speed
1980’s– TCP rates of Kilobits per second
1990’s– TCP rates of Megabits per second
2000’s– TCP rates of Gigabits per second
2010’s– TCP rates of Gigabits per second

GM

K
80’s

90’s

00’s

10’s
2

The Evolution of Speed
1980’s– TCP rates of Kilobits per second
1990’s– TCP rates of Megabits per second
2000’s– TCP rates of Gigabits per second?
2010’s– TCP rates of Gigabits per second

GM

K80’s

90’s

00’s

10’s
3

Today• Optical transmission speeds are now edging into Terrabit
capacity• But peak TCP session speeds are not keeping up• Its likely that network buffers play a role here
• How?

opticaltransport

TTCP speedGMK
80’s

90’s

00’s

10’s

4

TCP
• The Transmission Control Protocol is an end-to-end
protocol that creates a reliable stream protocol from theunderlying IP datagram device• TCP operates as an adaptive rate control protocol thatattempts to operate efficiently and fairly

TCP Design Objectives
To maintain an average flow which is Efficient and FairEfficient:– Minimise packet loss
– Minimise packet re-ordering– Do not leave unused path bandwidth on the table!
Fair:– Do not crowd out other TCP sessions– Over time, take an average 1/N of the path capacity when there are
N other TCP sessions sharing the same pathIt’s a Flow Control process• Think of this as a multiflow fluid dynamics
problem• Each flow has to gently
exert pressure on theother flows to signal
them to provide a fairshare of the network,and be responsive tothe pressure from allother flows

TCP Control
TCP is an ACK Pacing protocol

Data sending rate is matched to theACK arrival rate

TCP Control• Ideally TCP would send packets at a fair share ofavailable network capacity. But the TCP sender has noidea what “available network capacity” means.
• So TCP uses ‘rate adaptation’ to probe into network,
increasing the sending rate until it is ‘too fast’• Packet drop is the conventional signal of ‘too fast”

TCP Control
ACK pacing protocols relate to a past network state, not necessarily thecurrent network state– The ACK signal shows the rate of data that left the network at thereceiver that occurred at ½ RTT back in time
– If there is data loss in the forward path, the ACK signal of that loss isalready at least ½ RTT old!
TCP should react quickly to ‘bad’ news
– If there is no data loss, that is also old news
TCP should react conservatively to ‘good’ news

“Classic TCP” – TCP Reno
• Additive Increase Multiplicative Decrease (AIMD)– While there is no packet loss, increase the sending rate by one
segment (MSS) each RTT interval– If there is packet loss decrease the sending rate by 50% over thenext RTT Interval, and halve the sender’s window• Start Up– Each RTT interval, double the sending rate
– We call this “slow start” – probably because its anything but slow!!!

TCP Reno and Buffers – the Theory

Queue formation

Queue drain

TCP and Buffers – the Theory• When a sender receives a low signal it repairs the loss andhalves its sending window• This will cause the sender to pause for the amount of time todrain halve the outstanding data in the network• Ideally this exactly matches the amount of time taken for thequeue to drain• At the time the queue is drained the sender resumes its sending(at half the rate) and the buffer has fully drained• For this to work, the queue size should equal the delay
bandwidth product of the link it drives

TCP and Buffers – the Theory• When a sender receives a low signal it repairs the loss andhalves its sending windowflow• This will cause the sender to pause for the amount of timetoelgsi naddrain halve the outstanding data in the network
nue aqueelgnia s• Ideally this exactly matches otheamountof time taken for thefoniqueue to drain n assumpt
ith aws
ork the queue is drained the sender resumes its sending• AtthewtimesihAll t(at half the rate) and the buffer has fully drained• For this to work, the queue size should equal the delay
bandwidth product of the link it drives

TCP and Buffers• The rule of thumb for buffer size isSize = (BW ∙ RTT)
“High Performance TCP in ANSNET”
Villamizar & Song, 1994

15

TCP and Buffers
Too Big: The queue never drains, so the buffer adds delay tothe connection
Sending Rate / Sender Window

Queue too big
Packet Loss

Congestion
Avoidance

AddeddelayCongestion
Avoidance

Sender’s window recovery interval(1xRTT)Time

Link Capacity

TCP and Buffers

Sending Rate / Sender Window

Too Small: The queue drains and the sender operates below
bottleneck speed – so the link is under-used
Packet Loss

Congestion
Avoidance

Queue too small
Idle
capacity

Link Capacity
Congestion
Avoidance

Sender’s window recovery interval(1xRTT)
TimeRefinements to RENO• There have been many efforts to alter RENO’s flow control algorithm• In a loss-based AIMD control system the essential parameters are themanner of rate increase and the manner of loss-based decrease– For example:
MulTCP behaves as it it were N simultaneous TCP sessions: i.e.
increase by N segments each RTT and rate drop by 1/N upon
packet loss
• What about varying the manner of rate increase away from AI?

Enter CUBIC• CUBIC is designed to be useful for high speed sessions while still
being ‘fair’ to other sessions and also efficient even at lower speeds• Rather than probe in a linear manner for the sending rate that triggers
packet loss, CUBIC uses a non-linear (cubic) search algorithm

CUBIC and Queue formation

Total Queue Capacity(Onset of Packet Loss)

Network Buffers Fill

Link Capacity Capacity(Onset of Queuing)
Network Buffers DrainCUBIC assessment• Can react quickly to available capacity in the network• Tends to sit for extended periods in the phase of queueformation• Can react efficiently to long fat pipes and rapidly scale up
the sending rate
• Operates in a manner that tends to exacerbate ‘buffer bloat’
conditions

From 1 to N – Scaling Switching• This finding of buffer size relates to a single flow through asingle bottleneck resource• What happens to buffers with more flows and fastertransmission system?

22

Flow Mixing• If 2 flows use a single buffer and they resonate precisely
then the buffer still needs to be delay-bandwidth size
• If they are precisely out of phase the common buffer
requirement is halved

23

Smaller Buffers?
• If 2 flows use a single buffer and they resonate precisely then the buffer stillneeds to be delay-bandwidth size
• If they are precisely out of phase the common buffer requirement is halved• What about the case of N de-synchronised flows?

Size = (BW ∙ RTT) / √N
Assuming that the component flows manage to achieve a fair outcome ofobtaining 1/N of the resource in a non-synchronised manner, then the peakbuffer resource is inversely proportionate to the square root of N(“Sizing Router Buffers”, Appenzeller, McKeown, Keslassy, SIGCOM’04)

24

The Role of Buffers• Buffers in a network serve two essential roles:– smooth sender burstiness– Multiplexing N inputs to 1 output

Sender Pacing• Distribute cwnd data across the entire RTT interval• Remove burst adaptation pressure on network buffers

Tiny Buffers?
• If all senders ‘paced’ their sending to avoid bursting, andwere sensitive to the formation of standing queues then wewould likely have a residual multiplexing requirement forbuffers where:

B >= O(log W)
where W is the average flow window size27

Why is this important?
• Because memory speed is not scaling at the same rate astransmission or switching• Further capacity and speed improvements in the network
mandate reduced memory demands within the switch

Switching Chip Design TradeOffs• On Chip memory is fast, but limited to between ~16M to ~64M
• A chip design can include an interface to external memory banks
but the memory interface/controller also takes up chip space andthe external memory is slower• Between 20% to 60% of switch chip real estate is devoted tomemory / memory control• Small memory buffers in switch design allows for larger switch
fabric implementations on the chip29

Switch Design30

Flow States• There are three ‘states’ of flow management:– Under-Utilised – where the flow rate is below the link capacity and no queues
form– Over-Utilised – where the flow rate is greater that the link capacity and queues
form– Saturated – where the queue is filled and packet loss occurs• Loss-based control systems probe upward to the Saturated point, and back off
quickly to what they guess is the Under-Utilised state in order to the let the queues
drain• But the optimal operational point for any flow is at the point of state change fromUnder to Over-utilised, not at the Saturated point

RTT and Delivery Rate with Queuing

Under-Utilised

Over-Utilised

Saturated

How to detect the onset ofqueuing?
• By getting the network say when queues are formingICMP Source Quench Redux!

• Switch generates an ICMP message (similar to ICMP PTB)• ICMP payload allows sender to identify TCP session

ICMP Issues• IMCP messages are unverified– DOS attack vector• ICMP messages are often filtered– A sender cannot rely upon the message• Anycast can add subtle complications here!

Explicit Congestion Notification

Explicit Congestion Notification• Sparse signal (single bit)
• Both hosts and routers need to be ECN aware• IP level marking requires end host protocol surgery at bothends:•

Receivers need to reflect ECN bits•

Senders need to pass IP ECN up to the TCP session

ECN Issues• It would be good if…
– everyone did it!
• But they don’t all do it, which means that hosts cannot relyon ECN as the only means of congestion control• What’s the value of partial adoption of ECN?

High Precision Congestion Control• Eliminate all the guesswork out of the problem by having
each switch attach the time, local queue length and link
bandwidth to the IP packet!

How to detect the onset ofqueuing?
• By getting the network say when queues are formingOR• By detecting the onset of queue-based delays in themeasured RTT

Flow Control Revisited• Current flow control systems make small continual adjustments every
RTT interval and a massive adjustment at irregular intervals– As the flow rate increases the CA adjustments of 1 segment per RTT
become too small– Rate halving is a massive responseOR• We could use a system that only made periodic adjustments every n
RTT intervals– And set the adjustment to be proportionate to the current flow rate
41

BBR Design Principles• Pace the sending packets to avoid the need for network buffer rate
adaptation• Probe the path capacity only intermittently (every 8th RTT)
• Probe the path capacity by increasing the sending rate by 25% for
an RTT interval and then drop the rate to drain the queue:– If the RTT of the probe interval equals the RTT of the previous
state then there is available path bandwidth that could be utilised– If the RTT of the probe rises then the path is likely to be at theonset of queuing and no further path bandwidth is available• Do not alter the path bandwidth estimate in response to packet loss

Idealised BBR profile

sending rate

network queues

BBR Politeness?
• BBR will probably not constantly
pull back when simultaneous
loss-based protocols exertpressure on the path’s queues• BBR tries to make minimal
demands on the queue size, anddoes not rely on a large dynamic
range of queue occupancy
during a flow

Pulling it back together…
Where are we in networking today?
– A diverse mix of e-2-e TCP control protocols
CUBIC, NewRENO, LEDBAT, Fast, BBR– A mix of traffic models
Buffer-filling streamers, flash bursts, bulk data
– A mix of active queue disciplines
RED, WRED, CODEL, FQ, none
– A mix of media
Wire line, mobile, WiFi
– A mix of buffer size deployments– Sporadic ECN marking

Protocol Darwinism?
What “wins” in this diverse environment?
– Efficiency is perhaps more critical than fairness as a “survivalfitness” strategy– I suspect that protocols that make minimal assumptions about thenetwork will be more robust than those that require certain network
characteristics to operate efficiently– Protocols that operate with regular feedback mechanisms appear to
be more robust than irregular “shock” treatment protocols

What is all this telling us?
• The Internet still contains a large set of important unsolved problems• And some of our cherished assumptions about network design may bemistaken• Moving large data sets over very high speed networks requires anentirely different approach to what we are doing today• BBR seems to be a step in an interesting direction, particularly for very
high speed networking• We actually don’t know much about fine-grained behaviour of large
scale high capacity switching systems.
• It’s clear that more research and more testing at scale would help here!
47

That’s it!
Questions?