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.
Virtual
Sender
File
replicas
a We use the term “user” as a convenient shorthand for a user, or the software
or algorithm a user or end-system employs.
The original version of this paper was published in the
Proceedings of IEEE Infocom 2007, May 2007 by IEEE.