The efficient and fair allocation of distributed resources is a longstanding problem in network research. Today, almost all operating systems use TCP congestion control [27] to manage remote network resources. TCP assumes no network support beyond that packets are dropped when the network is overloaded; it uses these packet losses as a signal to control its sending rate. Provided that all endpoints use a compatible algorithm, persistent congestion can be averted while still achieving good throughput and fair allocation of the shared resource.
However, it has long been understood that TCP is far from optimal in many circumstances. TCP managed networks perform poorly for moderate sized flows on idle links [12,28], interactive applications [21], applications demanding minimally variable response times [13], high bandwidth-delay paths [32], and wireless networks [5]. In each case, the response in the cited papers has been to propose explicit network support. Clearly, network-based resource allocation can be designed to perform optimally. Thus, the research debate has largely focused on the appropriate knobs to place in the network, and specifically, the tradeoff between simplicity and optimality in network support for resource management.
We take a radically different approach. Our goal is to demonstrate that cooperating endpoints, without any special support from the network, can achieve near optimal resource allocation in all likely conditions. Our motivation is partly intellectual - what are the algorithmic limits to endpoint resource allocation? Our motivation is also partly practical - it is much easier to deploy an endpoint solution than to modify every router in the Internet. Since TCP congestion control was first introduced in 1988, three substantial changes to its algorithm have been introduced and widely adopted [38]; by contrast, to date no router-based changes to congestion management have achieved equally widespread use.
Our approach is simple: we directly emulate network-based control. Our algorithm, called the Probe Control Protocol (PCP), sends a short sequence of probe packets at a specific rate to detect whether the network can currently support the test rate, given its current traffic load. If so, the endpoint sends at that rate; if not, e.g., if other hosts are already using the bandwidth, the endpoint tries a new probe at a slower rate. A key element is that we use rate pacing (instead of TCP-like ack clocking) for all traffic; this allows probes to be short and precise. These short probes are ``low impact'' compared to the TCP approach of sending at the target rate for the full round trip time. Thus, endpoints can be aggressive with respect to testing for available bandwidth, without causing packet loss for existing flows. For example, a new arrival can use history to safely guess the currently available bandwidth. Since most links are idle most of the time, this often allow endpoints to jump (almost) immediately to full utilization of the link.
We have implemented PCP as a user-level process on Linux. Initial tests on the RON testbed show that PCP can outperform TCP by an average of a factor of two for 200KB transfers over the wide area, without having any measurable impact on competing TCP traffic. We supplement these results with simulation experiments, where we show that PCP achieves our goals of near optimal response time, near zero packet loss rates, and small router queues, across a wide variety of operating environments; we further show that it has better fairness properties than TCP. A Linux kernel implementation is also currently in progress. Interested readers can obtain the source codes for the implementations and the simulation harness at https://www.cs.washington.edu/homes/arvind/pcp.
A practical limitation of our work is that, like TCP, we provide no means to counter misbehaving hosts; network based enforcement such as fair queueing [14] is still the only known means to do so. We show that PCP, unlike TCP, benefits from fair queueing, thus making it the first system to do well for both FIFO and fair-queued routers. Any future network is likely to have a mixture of FIFO and fair-queued routers, making an endpoint solution compatible with all a necessity for network evolution. In our view, TCP's poor performance over fair-queuing routers is a barrier to further deployment of router enforcement. By contrast, PCP can be seen as a stepping stone for more robust isolation mechanisms inside the network, thereby improving the overall predictability of network performance.
The rest of this paper presents our approach in more detail. Section 2 outlines the goals of our work, arguing that TCP is sub-optimal in many common network conditions found today. Section 3 describes the design of the PCP algorithm. We evaluate our approach in Section 4, discuss related work in Section 5, and summarize our results in Section 6.