Transcript FAST v3 - Stanford University

TCP Congestion Control
Evolution
Steven Low
Caltech
netlab.CALTECH.edu
Summary
 First 25 years of Internet
 Networks are several orders of
magnitude smaller in size, speed, and
heterogeneity
 Applications are much simpler
 Last 14 years of Internet
 Networks are much bigger, faster, and
heterogeneous
 Applications are much more diverse and
demanding
TCP congestion control gradually becomes unsuitable
for more and more applications in more and more networks
Summary
 Both networks and applications are
evolving much faster in last 14 years
than previous 25
 Our control mechanisms have shown
remarkable robustness, but also
essentially frozen in the last 20 years
 TCP congestion control is gradually
being stressed more and more
 Time to change is now
 … though there may not be an
internet-wide train wreck
 But why wait for train wreck to change?
Outline
 Where we were
 Network growth
 Application growth
 Control mechanism growth
 Where we are
 Need to change TCP congestion
control
Internet milestones
1969
1974
1983
1988
TCP/IP
ARPANet
TCP
1991 1993 1996
HTTP
Tahoe
1999
2003 2006
Napster
Mosaic
Backbone speed:
50-56kbps, ARPANet
T1
NSFNet
T3, NSFNet
OC12
MCI
Network is exploding
OC48
vBNS
OC192
Abilene
Internet at birth (1969)
1 October, SDS
Routers
December, DEC
1 November, IBM
2 September, SDS
Source: http://www.computerhistory.org/exhibits/internet_history/full_size_images/1969_4-node_map.gif
Internet at 31
Internet growth
In comparison: car
If car technology has been advancing as
fast:
 US$ 5 /car [US$ 25,000 /car]
 100 km / lt [8 km / lt]
Subscribers in millions
The Wireless Internet
DoCoMo’s i-mode
• E-mail
• Internet
• Doubles
every half
year
• More than
20 million
subscribers
by early
2000s
(Courtesy: D. Rutledge)
Wireless Mesh Network
• Rooftop routers with 0.5-W
transmitters
(Courtesy: D. Rutledge)
• 2Mb/s channels and up to 1-mile
Application milestones
1971 1973
1969 1972
1988
Internet
Talk
Radio
ARPANet
Network
Mail
Telnet
1993 1995
Tahoe
Internet
Phone
Whitehouse
online
1990
2004 2005
Napster
music
iTunes
video
AT&T
VoIP
YouTube
File
Transfer
Simple applications
Diverse & demanding applications
Network Mail (1971)
First Internet (ARPANet) application
The first network email was sent by Ray Tomlinson between these two
computers at BBN that are connected by the ARPANet.
First ARPANet applications
 First Network Mail: SNDMSG, Ray
Tomlinson, 1971
 Replaced by SMTP: RFC 821, J. Postel, Aug
1982
 Telnet: RFC 318, Jon Postel, April 1972
 Started RFC 137, T. C. O’Sullivan, April 1971
 FTP: RFC 454, A. McKenzie, Feb 1973
 Started in July 1972, RFC 354, Abhay
Bhushan
Internet applications today
Telephony
Music
TV & home theatre
Finding your way
Games
Mail
Library at your finger tip
Network centric warfare
Software As A Service
Control milestones
1969
1973
1983
1988
TCP/IP
ARPANet
TCP
Tahoe
Flow control:
Prevent overwhelming receiver
+ Congestion control:
Prevent overwhelming network
Going forward: provide/facilitate new application requirements
2006
TCP (1974)
 Cerf and Kahn, Trans. Communications (1974)
 RFC 793, TCP (1981)
 ARPANet cutover to TCP/IP (Jan 1, 1983)
 Window control: ack-clocking, timeout,
retransmission
 For correct delivery of packet sequence over
unreliable networks
 To prevent overwhelming receiver (through Advertised
Window in TCP header)
“We envision [HOST retransmission capability] will occasionally be
invoked to allow HOST accommodation to infrequent overdemands
for limited buffer resources, and otherwise not used much.”
-- Cerf and Kahn, 1974
TCP (1974)
Key control mechanism
 Receiver specified max amount of data it
can receive (Advertised Window)
 Sender maintains no more than that
amount of outstanding packets
 Ack-clocking adapts to (mild) congestion
Congestion collapse
 October 1986, Internet had its first congestion
collapse
 Link LBL to UC Berkeley
 400 yards, 3 hops, 32 Kbps
 throughput dropped to 40 bps
 factor of ~1000 drop!
 1988, Van Jacobson proposed TCP congestion
control
throughput
load
Networks in late 1986
 5,089 hosts on Internet (Nov 1986)
 Backbone speed: 50 – 56 kbps
 Control mechanism focused only on receiver
congestion, not network congestion
 Large number of hosts sharing a slow (and
small) network
 Network became the bottleneck, as opposed to
receivers
 But TCP flow control only prevents overwhelming
receivers
Jacobson introduced mechanism to
deal with network congestion in 1988
Tahoe and its variants (1988)
 Jacobson, Sigcomm 1988
 + Avoid overwhelming network
 + Window control mechanisms
 Dynamically adjust sender window based on
congestion (as well as receiver window)
 Loss-based AIMD
 Fast Retransmit/Fast Recovery
 New timeout calculation that incorporates
variance in RTT samples
“… important considering that TCP spans a range from 800 Mbps
Cray channels to 1200 bps packet radio links”
-- Jacobson, 1988
Outline
 Where we were
 Where we are
 Need to change TCP congestion
control
Summary
 First 25 years of Internet
 Network is several orders of magnitude
smaller in size, speed, and heterogeneity
 Applications are simple
 Last 14 years of Internet
 Networks are much bigger, faster, and
heterogeneous
 Applications are much more diverse and
demanding
 Both network and applications are
evolving much faster in last 14 years
than previous 25
What is inadequate
 New applications demand new
requirements that stretch TCP
 FTP or Telnet vs video streaming
 New networks stretch TCP
 New wireless challenges
 Solutions to some wireless issues
need more than transport layer
mechanisms
What is inadequate
 Wireless networks: 5 demos
 Video delivery: 4
 Large BDP: 2
 Short messages: 1
 Content upload: 1
TCP congestion control becomes unsuitable for more
and more applications in more and more networks
Real-world evidence
Throuput: LA  Tokyo
Throuput: San Fran  MIT
20000
FTP throughput (kbps)
18000
1.8x
3.8x
6.3x
17.6x 21.8x
28.1x
32.5x
16000
14000
Alter avg:
233Mbps
12000
10000
8000
6000
4000
2000
0
50x delays are common over DSL speed
Alternative
TCP
File size (MB)
links
0.1
0.5
1
5
10
20
60
Reno avg:
35Mbps
Another example
TCP
thruput: 1Mbps
Alternative
thruput: 120Mbps
Heavy packet loss in Sprint network:
Alternative increased throughput by 120x !
San Francisco  New York
June 3, 2007
Why is evolving TCP important
 Pockets of industry are
experiencing increasing pain
 They will not wait for research or
standards communities
 MS and Linux are already
deploying new TCP’s
The pain will only intensity …
… because of powerful industry trends
Trend 1

Exploding need to deliver large content

Video, software, games, business info
Trend 1: Online content is exploding
 CAGR 2005 – 2011: 36%
 Google worldwide:
46PB/month
 Library of Congress: 0.136PB
Trend 1: Video is exploding
Jan 2007
Trend 1: Multi-year growth
 Only ~10% of digital content is currently online
Jan 2007
Trend 2

Exploding need to deliver large content


Video, software, games, business info
Infrastructure growth to support delivery need
Trend 2: Broadband penetration

Global broadband penetration is accelerating


11 million new subscribers/month globally
83% of US home Internet access is broadband by June 2007
Source: Deutsche Bank, Jan 2007
Trend 3

Exploding need to deliver large content



Video, software, games, business info
Infrastructure growth to support delivery need
Centralize IT to reduce costs of management, space,
power, cooling

Exacerbated by virtualization of infrastructure and
personalization of content
Trend 3: Centralization

Power & cooling cost is escalating, fueling centralization


CAGR (2005-10): power & cooling 11.2%, new server spend 2.7%
In 2005, 1,000 servers cost $3.8M to power & cool in 4yrs; 2%
increase in electricity cost raises cost by $200K
Worldwide Expense
(US: $4.5B in 2006; EPA)
Source: IDC Sept 2006
Trend 3: Centralization
Content Volume & Global Transfer Increasing

Exploding need to deliver large content



Infrastructure growth to support delivery need
Centralize IT to reduce costs of management, space,
power, cooling


Video, software, games, business info
Exacerbated by virtualization of infrastructure and
personalization of content
Implication


More large contents over longer distance
Served from centralized data centers
“You could only get that sustained rate if you are delivering within
100 miles, due to the way current Internet protocols work.”
Tom Leighton, MIT/Akamai, Oct 2007
http://sramanamitra.com/2007/10/21/speeding-up-the-internet-algorithms-guru-and-akamai-founder-tom-leighton-part-5/
Solution Approaches
 Protocol problems degrade performance of
long-distance transfers
 Current approach: reduce distance
 Alternative approach: fix protocol problems
Content Delivery Networks (CDNs)
Protocol limitations inherent in Internet give rise to Content Delivery Networks
CDNs circumvent protocol problems by placing servers all around the world
Alternative Solution
Distance is no longer a constraint in IT infrastructure design