Overview
Rate Control Protocol (RCP) is a new congestion control algorithm designed for fast download times (i.e. aka user response times, or flow-completion times). Whereas other modifications to TCP (e.g. STCP, Fast TCP, XCP) are designed to work for specialized applications that use long-lived flows (scientific applications and supercomputer centers), RCP is designed for the typical flows of typical users in the Internet today. For example, a mid-size flow in the Internet today contains 1000 packets and TCP typically makes them last 10x longer than need-be (XCP is even worse). RCP makes flows finish close to the minimum possible, leading to a perceptible improvement for web users, distributed computing, and distributed file-systems. We believe RCP is the only congestion control algorithm to do this.
The main properties of RCP are:
- Typical Internet flows will see 10 times faster download times than TCP and 30 times faster than XCP. Winners are the greater than 90% of sessions that never leave slow-start today.
- Efficiently uses high bandwidth-delay product networks such as the long haul optical links
- Provably stable network independent of link-capacities, round-trip times and number of flows
- Flows are easy to police, to ensure they adhere to congestion control (not generally possible with other schemes)
- Network operators can give preference (or weighted preference) to some flows/aggregates.
RCP has two components: (1) End-host congestion control layer that sits between IP and TCP/UDP. During introduction, the end-host could adapt by testing for RCP at each end and along the path, falling back to TCP if need-be. (2) Each router maintains a single fair-share rate per link. Each packet carries the rate of the bottleneck link. For each packet, the router compares the two values. If the router's fair-share rate is smaller, it overwrites the value in the packet. This way, the source learns the fair-share rate of bottleneck link. It is simple, requires a very minor change to switches/routers, requires no per-flow state or per-packet computation.
Papers and Technical Reports
-
"Why Flow-Completion Time is the Right Metric for Congestion Control"
[.pdf]
Nandita Dukkipati and Nick McKeown
ACM SIGCOMM Computer Communication Review Volume 36, Issue 1 (January 2006)
Extended version is available as High Performance Networking Group Technical Report TR05-HPNG-112102 [.pdf]
-
"Processor Sharing Flows in the Internet"
[.pdf]
Nandita Dukkipati, Masayoshi Kobayashi, Rui Zhang-Shen and Nick McKeown
Thirteenth International Workshop on Quality of Service (IWQoS), Passau, Germany, June 2005.
-
"Processor Sharing Flows in the Internet"
[.pdf].
Nandita Dukkipati and Nick McKeown
High Performance Networking Group Technical Report TR04-HPNG-061604, June 2004
-
"Performance Analysis of the Rate Control Protocol"
[Abstract]
Ashvin Lakshmikantha, Nandita Dukkipati, R. Srikant, Nick McKeown and C.L. Beck
This work is under submission. Meanwhile, if you are interested in reading the technical report, please email Ashvin Lakshmikantha.
- "RCP-AC: Congestion Control to make flows complete quickly in any environment" (Extended Abstract)[.pdf]
Nandita Dukkipati, Nick McKeown and Alexander G. Fraser
High-Speed Networking Workshop: The Terabits Challenge (In Conjunction with IEEE Infocom 2006), Barcelona, Spain, April 2006.
- This paper is on a design principle of Networking systems/algorithms. RCP is one of the examples illustrating the application of this principle.
"Typical versus Worst Case Design in Networking" [.pdf]
Nandita Dukkipati, Yashar Ganjali and Rui Zhang-Shen
Fourth Workshop on Hot Topics in Networks (HotNets-IV), College Park, Maryland, November 2005.
- "Stability Analysis of Explicit Congestion Control Protocols"[.pdf]
Hamsa Balakrishnan, Nandita Dukkipati, Nick McKeown and Claire Tomlin
Stanford University Department of Aeronautics and Astronautics Report: SUDAAR 776, September 2005
Selected Talks
-
"A Clean Slate Design of Internet's Congestion Control Algorithm"
[.pdf]
Caltech Lunch Bunch Seminar, 8 November 2005
-
"A Clean Slate Design of Internet's Congestion Control Algorithm"
[.pdf]
Hamilton Institute Workshop on Congestion Control, 27-28 September 2005
-
"A Clean Slate Design of Internet's Congestion Control Algorithm"
[.pdf]
At MIT and University of Massachusetts, Amherst, April 2005.
Also given at ICSI, Berkeley, July 2005 and at Berkeley Systems Lunch, October 2005
-
"Congestion Control for 100x100: Why TCP is a poor choice and how to redesign it from scratch"
[.pdf]
100x100 project retreat , Carnegie Mellon University, Pittsburgh, December 2004
Implementation
-
We have a RCP implementation in ns-2.28. Download RCP files rcp-v1.tar.gz (also includes sample .tcl files for RCP, TCP and XCP used in RCP papers).
-
Glen Gibb (EE, Stanford) is implementing the RCP router module in hardware on NetFPGA.
-
We have the RCP end-host implementation in the Virtual Network System (VNS) and are working on a Linux implementation.
Work in Progress
- Bounding the worst-case convergence time in RCP
The question we are interested in is: when there is a sudden increase in the network load -- for example the load has increased by five times within a round-trip time -- how quickly does RCP converge? Preliminary simulations suggest the convergence can be very quick depending on how the parameters are chosen: Worst-case convergence time.
People
Faculty: Nick McKeown
Graduate Student: Nandita Dukkipati
RCP has benefited immensely from the wonderful collaborations with:
Funding
This research is funded in part by NSF under ITR award ANI-0331653. RCP is part of the 100x100 Clean Slate Design Project.
Questions?
Please first check the Frequently Asked Questions. If you don't find what you are looking for, then Nandita Dukkipati will be quite happy to answer them for you.
