Communications - January 2011

Path Selection and Multipath
Congestion Control

abstract

In this paper, we investigate the benefits that accrue from the use of multiple paths by a session coupled with rate control over those paths. In particular, we study data transfers under two classes of multipath control, coordinated control where the rates over the paths are determined as a function of all paths, and uncoordinated control where the rates are determined independently over each path. We show that coordinated control exhibits desirable load balancing properties; for a homogeneous static random paths scenario, we show that the worst-case throughput performance of uncoordinated control behaves as if each user has but a single path (scaling like log(log(N))/ log(N) where N is the system size, measured in number of resources), whereas coordinated control yields a worst-case throughput allocation bounded away from zero. We then allow users to change their set of paths and introduce the notion of a Nash equilibrium. We show that both coordinated and uncoordinated control lead to Nash equilibria corresponding to desirable welfare maximizing states, provided in the latter case, the rate controllers over each path do not exhibit any round-trip time (RTT) bias (unlike TCP Reno). Finally, we show in the case of coordinated control that more paths are better, leading to greater welfare states and throughput capacity, and that simple path reselection polices that shift to paths with higher net benefit can achieve these states.

1. intRoDuction

Multipath routing has received attention recently. 2, 5, 6, 14, 21 Furthermore, combining multipath routing with rate control is implicitly used by several peer-to-peer (P2P) applications. Most relevant to us is Bit Torrent, 4 which maintains a number of, typically four, active connections to other peers with an additional path periodically chosen at random together with a mechanism that retains the best paths (as measured by throughput).

The basic setting of multipath coupled with rate control
is as follows. A source and destination pair in a network is
given a set of possibly overlapping paths connecting them.
The pair then chooses a subset to use and the rates at which
to transfer data over those paths. This scenario is illustrated
in Figure 1a. Note that the P2P example described above
falls into this formulation once one includes a fictitious
source feeding data through peers to the intended receiver,
as shown in Figure 1b. Some natural questions arise:
• How many paths are required? And does it suffice, as
with the above P2P application, to use a subset of the
paths? Opening multitudinous TCP connections has
negative systems performance implications, hence
there are incentives to keep the number of connections
small.

The motivating application scenario is of data transfers over a network, where the transfers are long enough to allow performance benefits for multipath routing, although our results apply more generally to situations where there are alternative resources that can help service a demand, and where the demand is serviced using some form of rate control. We assume that demand is fixed, and each usera attempts to optimize its performance by choosing appropriate paths (resources), where the rate control algorithm is fixed. More precisely, we assume that the rate control is implicitly characterized by a utility maximization problem, 20 where a particular rate control algorithm

Sender (a) (b)

Receiver

figure 1. (a) a canonical multipath example. (b) a Bittorrent example where a receiving peer receives data from four peers. a virtual sender has been included to show the relationship to canonical multipath.