(e.g. TCP Reno) maps to a particular (user) utility function, 9
and users selfishly seek to choose paths in such a way as to
maximize their net utility. Within this optimization framework, a coordinated controller is modeled by a single utility function per user, whose argument is the aggregate rate
summed over paths, whereas an uncoordinated controller
has a utility function per path and the aggregation is over all
of the utility functions.
Key to the usefulness of multipath rate control is its ability in the hands of users operating independently of each
other to balance the load throughout the network. We illustrate this for a particular scenario, where the paths chosen
are fixed and static, but chosen at random from a set of size
N. We focus on the worst-case allocation, which is a measure
of the fairness of the scheme. In the uncoordinated case,
the worst-case allocation scales as log(log(N))/log(N) independent of the number b of paths chosen. In contrast, in the
coordinated case where each user can balance its load across
the b paths available to it, provided there are two or more, the
worst-case allocation is bounded away from zero. This demonstrates that
1. Coordinated control balances loads significantly better
than uncoordinated when paths are fixed.
2. Coordinated improves on greedy least-loaded resource
selection, as in Mitzenmacher, 16 where the least-loaded
selection of b resources scales as 1/log(log(N) ) for b > 1.
Effectively, coordinated control is able to shift the load
among the resources, and with each user independently
balancing loads over no more than two paths, able to utilize the resources as if global load balancing was being
This raises the question of how users should be assigned
a set of paths to use. One natural path selection mechanism
is to allow users to make their own choices. We study this
as a game between users and consider a natural notion of a
Nash equilibrium in this context, where users seek to selfishly
maximize their own net utilities. We find that when users use
coordinated controllers, the Nash equilibria coincide with
welfare-maximizing social optima. When we consider uncoordinated controllers, then the results depend on whether the
controllers exhibit RTT bias (like TCP) or not. When they do
not exhibit RTT bias, the Nash equilibria also coincide with
welfare-maximizing social optima. Otherwise they need not.
We show that increasing the number of paths available
to a source destination pair is desirable from a performance
perspective. However, the simultaneous use of a large number of paths may not be possible. We show that this does not
pose a problem as simple path selection policies that combine random path resampling with moving to paths with
higher net benefit lead to welfare maximizing equilibria and
also increase the throughput capacity of the network. In fact
such a policy does as well as if each user uses all of the available paths simultaneously.
In summary, we shall provide some partial answers to our
from the sets of paths and shift to paths with higher net
benefit, they can rely on a small number of paths and
do as well as if they were fully using all available paths.
• Coordinated control has better fairness properties
than uncoordinated in the static case. When combined
with path reselection, uncoordinated control only does
as well as a coordinated control if there is no RTT bias
in the controllers.
We conclude the paper with some thoughts on how multipath rate control might be deployed.
2. the muLtiPath fRame WoRk
The standard model of the network is as a capacitated graph
G = (V, E, C) where V represents a set of end-hosts or routers,
E is a set of communication links and each link has a capacity, say in bits per second, Cl, l ∈ E. In addition a large population of sessions perform data transfers over the network.
These sessions are partitioned into a set of session classes
S with Ns sessions in class s S. Associated with class s is a
source ss, a destination ds, and a set of one or more, possibly overlapping paths, R(s) between the source and destination that is made available to all class s sessions. Finally, we
associate an increasing, concave function with each session
class, Us(x), which is the utility that a class s session receives
when it sends data at rate x > 0 from source to destination.
Now, exactly how this utility is used and the meaning of
x depends on whether we are concerned with coordinated
or uncoordinated control. We will shortly describe each of
these in turn.
A discussion of how utility functions can be used to model
standard TCP Reno is given in Kunniyur and Srikant. 15 The
so-called weighted alpha-fair utility functions given by
were introduced in Mo and Walrand, 17 and are linked to different notions of fairness. For example, a = 1 corresponds to
(weighted) proportional fairness, 8 and lim a → ∞ to max–min
fairness. TCP’s behavior is well approximated by taking a = 2
and wr = 1/T 2r, where Tr is the round trip time for path r, in
the following sense: TCP achieves the maximum aggregate
utility, for given paths and link capacities, for the corresponding utility functions Ur.