(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 performed.

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 initial questions.

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.