March 24th, 2008
Fixing the unfairness of TCP congestion control
Bob Briscoe (Chief researcher at the BT Network Research Centre) is on a mission to tackle one of the biggest problems facing the Internet. He wants the world to know that TCP (Transmission Control Protocol) congestion control is fundamentally broken and he has a proposal for the IETF to fix the root cause of the problem.
The Internet faced its first congestion crisis in 1986 when too much network traffic caused a series of Internet meltdowns when everything slowed to a crawl. Today’s problem is more subtle and lesser known since the network still appears to be working correctly and fairly. But underneath that facade and illusion of fairness, a very small percentage of users hog most of the Internet’s capacity suffocating all other users and applications.
Â
Solving the first Internet meltdown crisis
In October of 1986, the Internet began to experience a serious of “congestion collapses”. So many computers were piling their traffic on to the network at the same time that the network came to a grinding halt and no one got any meaningful throughput. By mid 1987, computer scientist Van Jacobson who is one of the prime contributors to the TCP/IP stack created a client-side patch for TCP that saved the day. Every computer on the Internet - roughly 30,000 in those days - was quickly patched by their system administrators.
Jacobson’s TCP stack patch worked by causing a computer to cut the flow rate of its TCP stream in half as soon as it detects any packet loss. Packets are lost whenever the routers relaying them receive more packets than they can forward and the router begins to randomly drop packets across the board. But whenever a computer sees an acknowledgement that its packet arrived successfully, it quickly and continually increases its flow rate with every acknowledgement until it experiences another packet drop at which time it cuts its throughput in half again. This became known as the AIMD (Additive Increase Multiplicative Decrease) algorithm where the sending computer is constantly probing for the maximum allowable bandwidth by repeatedly increasing throughput until it crosses a line and gets knocked down.
Jacobson’s AIMD algorithm also allowed a new TCP stream to open up and quickly rise to equilibrium where it attains the same flow rate as all other TCP streams. Conversely when a TCP stream ended transmission, the extra bandwidth freed up would be evenly distributed amongst the remaining streams. Van Jacobson’s patch was so successful that it became a part of the TCP standards and it hasn’t fundamentally changed for over 20 years and according to Bob Briscoe, Jacobson’s algorithm is the “fifth most cited academic paper in all of computer science”.
Under Jacobson’s algorithm which sought out to balance the flow rate (throughput) of each TCP stream, the system was more or less fair to everyone who wanted to use the network so long as everyone used an equal number of TCP streams. Since people typically used one TCP stream at a time and people had limited usage on those time-sharing computers in the 1980s, Jacobson’s algorithm was adequate for the problems of that era. While it was possible for someone to open two FTP downloads or uploads at a time and get double the total throughput than anyone else, this wasn’t a big problem when applications and operating systems were mostly limited to text and computers were limited to academic and large corporate institutions. But as time went on and as the number of applications and users grew, it was only a matter of time before the fairness of the system would be exploited.
<Next page - Exploiting Jacobson’s TCP algorithm>
George Ou is Technical Director of ZDNet. See his full profile and disclosure of his industry affiliations.
