## Abstract

We discuss control strategies for communication networks such as the Internet. We advocate the goal of welfare maximization as a paradigm for network resource allocation. We explore the application of this paradigm to the case of parallel network paths. We show that welfare maximization requires active balancing across paths by data sources, and potentially requires implementation of novel transport protocols. However, the only requirement from the underlying ‘network layer’ is to expose the marginal congestion cost of network paths to the ‘transport layer’. We further illustrate the versatility of the corresponding layered architecture by describing transport protocols with the following properties: they achieve welfare maximization when each communication may use an arbitrary collection of paths; available in an overlay; and are combined in series and parallel. We conclude by commenting on incentives, pricing and open problems.

## 1. Introduction

The Internet has grown from a small network connecting a few nodes to be the dominant global communications network. The current Internet is an example of a fast packet network, and we shall take it as both an exemplar and a motivation for describing problems of controlling communication networks. In particular, we address problems of control in such a network, where the objective is to provide some form of service differentiation or quality of service (QoS) to different users or applications in the face of limited resources, and we want to optimize the performance in some sense.

The problem is a topical one since the current Internet essentially provides a ‘best-effort’ service to all users, with no clear mechanism for providing any form of end-to-end service differentiation. This is the subject of much current debate and research within the Internet community, often centred around clean-slate approaches or next generation architectures. This is because the Internet has failed to evolve architecturally. For instance, the current transmission control protocol/Internet protocol (TCP/IP) protocol suite, comprising the core protocols of the Internet, has changed a little over the last two decades. The reasons for this are many and varied, and include strong standards with a commitment to backward compatibility, and diverse ownership. These, coupled with an absence of a link between quality and price militates against any incentive or reward structure for unilateral innovation or evolution (e.g. Laskowski & Chuang 2006), which makes creating new end-to-end forms of differentiation difficult.

When there is excess demand, and limited resource, some form of control is needed. Different applications react differently to being given reduced resources or starved of resources. For example, a real-time media stream may be unable to decode meaningful content for the user to view, whereas a file transfer will be delayed. Our approach is general, and the resources could include wired or wireless network capacity, buffering in a switch or even processing capacity. However, we shall use capacity or bandwidth as a motivating example, with the rate that an application receives, the primary performance indicator. Other measures, such as latency or delay, are important from an application's perspective, but there are good reasons to see within-network queuing delay decreasing as network's evolve, leaving latency solely determined by path length and physics. Indeed, Kelly (2000) provides scaling regimes where queuing delays decrease, and others (such as Enachescu *et al*. 2006) have argued that buffers in the networks should be ‘small’.

In this paper, we focus on the performance of the so-called ‘elastic-traffic’. We first advocate welfare maximization as an objective for network control, §2. Our main argument is that it maximizes the so-called *schedulable region*, characterizing the load that the network can carry. Interestingly, for single-path data transfers, the current Internet TCP protocol achieves a particular type of welfare maximization.

We then address how to achieve this objective when multiple network paths connecting a data source to its destination can be used for individual data transfers (§3). We show that coordination of flow control along such multiple paths is required. We also explain why and how the current Internet transport protocol needs to be modified to allow suitable coordination.

We then discuss path sampling techniques for achieving welfare maximization at a macroscopic level, while ensuring that individual data transfers proceed along a small number of paths (§3*c*). We further introduce flow control protocols that combine network paths not only in parallel but also in series (§4). Finally, we comment on the architectural aspects of our proposals and related charging issues (§5).

## 2. Modelling and control of the Internet

TCP is the dominant transport protocol in the current Internet, and implements congestion control using a window-based flow control. Several authors (Mathis *et al*. 1997; Padhye *et al*. 2000) have proposed models for the rate that TCP allocates to a particular connection, say of class *s*. They express the achieved rate as a function of both the packet loss probability *p*_{s} along the corresponding network path, and the round-trip time (RTT) delay *T*_{s} along the same network path. The so-called *square-root formula* states that TCP Reno, when in congestion avoidance mode, gives a rate *x*_{s} equal to , when expressed in suitable units.

As Kunnyur & Srikant (2000) observe, this can be interpreted as saying that TCP implicitly solves a utility maximization problem, where the objective is to maximize the net utility (utility minus cost), with incurred cost the path loss rate *p*_{s}*x*_{s} and with utility function(2.1)The maximum is achieved when , which does indeed recover the square-root formula for *x*_{s}. In other words, the predominant flow control protocol in the current Internet can be thought of as implementing a utility maximization. See Kelly (2000) for a more complete discussion.

We now describe a general framework for bandwidth allocations in a data network proposed by Kelly *et al*. (1998). We classify data flows into different types *s*∈. Let *n*_{s} denote the number of data flows of type *s*, and let *x*_{s} denote the data rate assigned to each type *s* flow, for all *s*∈. Then, the vector of the desired data rates is chosen to maximize the welfare function(2.2)where *U*_{s} is a strictly concave, non-decreasing utility function and *Γ* is a convex, non-decreasing cost function, representing the overall network cost of having aggregate bandwidth *n*_{s}*x*_{s} for each flow type *s*∈. These are reasonable assumptions: concave utility captures the elastic nature of data traffic, while convex costs reflect congestion or capacity costs. This framework can be related to flow control in the current Internet, where flow types are associated with a pair of IP source and destination addresses.

For simplicity, we shall assume that the welfare function has one finite local maximum. Since welfare is a strictly concave function, this must be its unique global maximum. For the ease of exposition, we also assume that the functions *U*_{s}, *s*∈ and *Γ* are differentiable.

It is possible to design simple, decentralized rate adaptation schemes for send rates *x*_{s}, under which welfare increases over time and converges to the unique welfare maximizing allocation vector. Indeed, one such scheme that has these properties is the continuous rate adaptation algorithmwhereis the so-called marginal cost for bandwidth of type *s*, and *κ*_{s} is some positive gain parameter (see Srikant (2003) and Voice (2006) for a detailed treatment).

As a specific example of network cost, let *Γ* be the sum of costs specific to links within the networkwhere the cost of link *ℓ* is some (convex, increasing) function of the aggregate rate through that link , and where means that link *ℓ* is part of path *s*. Under these assumptions, the marginal cost *p*_{s} is the sum of the link prices . One specific link cost function of interest consists in setting to be packet loss probability in a single server queue with capacity *C* and finite buffer size *B* (the so-called M/M/1/B queuing system), an approximate model for current drop-tail routers.

We now argue that utility maximization is the natural framework for addressing questions of fairness and design for rate control algorithms.

Firstly, this objective is achievable in practice: we saw that TCP performs such a maximization. It can be modified to mimic the behaviour of the previous dynamical systems to capture different utility functions (e.g. *scalable TCP* in Kelly 2003); the packet loss signal to which TCP reacts could be replaced by some measure of the path marginal cost, to capture different cost functions.

Secondly, if the utility functions *U*_{s} capture accurately the utility of data rates for type *s* flows, and the function *Γ* which determines the marginal costs or ‘prices’ *p*_{s} reflects accurately the network costs, then the above framework is in line with the microeconomic theory, with its corresponding emphasis on welfare maximization.

The previous argument applies to a scenario where data sources are long-lived, and the collection of active flows is essentially static. This stands in sharp contrast with the current usage of the Internet. There, data transfers have a limited duration, which typically depends on the achieved transmission rate for transfers of files that have an intrinsic volume.

We now describe the models of control and the network performance in a dynamic setting. Such models are important for addressing performance, and have a validity independent of utility maximization.

We assume that for each type *s*, there are *n*_{s} file transfers. Type *s* file transfers are created at the instants of a rate *ν*_{s} Poisson process, and the corresponding file size is exponentially distributed with parameter *μ*_{s}. Once initiated, transfers take place (there is no admission control or rejection policy) and obtain a welfare maximizing rate allocation *x*_{s} such that the vector maximizes (2.2). This corresponds to the best-effort service model paradigm, as implemented in the current Internet: data transfers are always accepted and proceed at the maximal rate that the standard transport protocol will enable.

To analyse the performance, we consider deterministic evolution equations, which correspond to the mean drift of the variables of interest in the original stochastic model for *n*_{s}. Such deterministic evolutions can be interpreted as accurate approximations of the original dynamics under some ‘law of large numbers’ scaling, where both arrival rates and network capacities are large, and *n*_{s} are the rescaled quantities. Specifically, we consider the following differential equation:(2.3)We let denote the set of rate vectors ** z** for which

*Γ*(

*z*) is finite, and then introduce the following stability condition:(2.4)(2.5)where denotes the

*s*th partial derivative of

*Γ*, and

**is the vector of loads**

*ρ**ρ*

_{s}for each file transfer type

*s*, defined as . The conditions are natural extensions of the more familiar load constraints. For example, in the special case where is a single resource having capacity

*C*, with

*Γ*the penalty function if

*z*≤

*C*, and +∞ otherwise, then the conditions are equivalent to .

The following result is a consequence of a more general result proved in Key & Massoulié (2006), where real-time (fixed-duration) traffic is mixed with file transfers.

*Under the conditions* (*2.4*) *and* (*2.5*), *the differential equations* (*2.3*) *have a unique invariant point* *characterized by*(2.6)

Moreover, it is possible to show that all trajectories of the differential equations (2.3) converge to the equilibrium point.

In the case where the cost function *Γ* is constant on its domain , this result implies that the original stochastic system is ergodic, and hence file transfer times remain finite, whenever the vector of loads ** ρ** lies in the interior of . In other words, the schedulable region of the network coincides with . This is the largest possible region, and thus welfare maximizing rate assignments lead to a maximal schedulable region (e.g. Massoulié (2007) for more details).

## 3. Multipath routing and congestion control

Multipath routing, where a flow can choose or use several paths rather than one, provides performance and reliability benefits over single-path routing. Reliability is improved since failures are less likely to disconnect a sender from a receiver when multiple paths exist between them. Performance is improved since higher data rates can potentially be achieved over several paths than over a single path. Multipath routing can also alleviate limitations of current architectures, where routing choices are dictated by network providers rather than end-users.

In this section, we investigate how to achieve the full benefits of multipath routing.

### (a) Uncoordinated parallel routing

For uncoordinated parallel routing, we assume that each flow makes use of the underlying transport layer for each of its available paths, and that the transport layer assigns a rate according to some utility maximization principle, independently among paths used by the flow. This models traffic sources using several parallel standard TCP connections available for data transfer, and corresponds to the simplest implementation of multipath transfers within the current Internet architecture.

Let us assume that the transport layer solves(3.1)over *x*_{r}≥0, where *s* denotes a type of flow; (*s*) denotes the collection of paths that type *s* flows can use; and *N*_{s} is the total number of type *s* flows. Without loss of generality, we assume that the path sets (*s*) are disjoint. The utility on each path may represent a TCP controller in which case the utility functions depend on specific characteristics of the path, namely the corresponding RTT.

Such uncoordinated multipath transfers can be inefficient. To illustrate this, we focus on the performance with dynamic arrivals of file transfer requests, for a particular topology, shown in figure 1. Specifically, there are three types of flows, corresponding to all possible source–destination pairs (such as A–B). We denote the type of flow corresponding to a particular source–destination pair with the letter of the opposite vertex, e.g. type C flows correspond to the source–destination pair A–B. Flows between a pair of nodes can use both the direct one-hop route and the two-hop route (e.g. routes A–B and A–C–B for type C flows). We further assume sharp capacity constraints and unit capacity links, hence the cost *Γ* is zero unless some capacity constraint is violated, in which case it is infinite.

Consider the case of symmetric loads, where *ν*_{i}≡*ν* denotes the arrival rate of type *i* flow transfer requests, *μ*_{i}≡*μ* is the parameter of the assumed exponential distribution for the volume of such transfers and *ρ*_{i}≔*ν*_{i}/*μ*_{i} is the load contributed by such flows. The fluid dynamics corresponding to this process are given by(3.2)If we assume that the utility functions associated with each path all coincide with (a plausible model of TCP allocations if *α*=2 and RTTs are all equal), then it is possible to show that there is a solution of the fluid equations which converges to *n*=0 provided *ρ*<*ρ*^{*} where(3.3)

A more detailed treatment of this example can be found in Key & Massoulié (2006), where the following is proved.

*For the triangle network with symmetric offered loads ρ and path utility functions* , *the solution* ** n**(

*t*)

*to the system of differential equations*(

*3.2*)

*diverges to infinity whenever*

*ρ*>

*ρ*

^{*}.

*In particular, when α*=2,

*the system is unstable provided*.

*Conversely, the solution* ** n**(

*t*)

*decreases to zero in time at most*

*for a suitable constant*

*θ*>0

*whenever*

*ρ*<

*ρ*

^{*}.

It is possible to show that *ρ*^{*} is indeed the exact capacity of the triangle network under symmetric loads.

Let us anticipate on the discussion of coordinated multipath control. As will be discussed in §3*c*, if we consider a suitably *coordinated* control, then the corresponding trajectories converge to zero, under the following condition:(3.4)Consequently, the original stochastic system is ergodic under these conditions, which are essentially optimal. In particular, for symmetric loads this condition becomes *ρ*<1.

In other words, the schedulable region is smaller than that for coordinated routing, and indeed approximately 30% less traffic can be treated when uncoordinated routing is used instead of a coordinated controller.

### (b) Path bias and suboptimal coordination

The previous example showed that some form of coordination between paths is needed to reap the full benefits of multipath routing. One simple form of coordination is the following: for any flow of traffic offered access to several paths, choose the path for which the achieved transfer rate is largest. This could be implemented at the application layer, on top of the TCP transport layer for each path, by ‘feeding’ paths on the basis of their achieved rates.

We now show that this kind of adaptation is suboptimal when the underlying transport layer introduces biases between distinct paths. Specifically, we assume that the rate allocated by the transport layer to each path is the result of some utility maximization, where the utility function relative to path *r* is given by the utility function *U*_{r}(*x*) defined in (2.1), reflecting the behaviour of TCP Reno.

We consider the hexagonal network of figure 2, which has long fat links, each having RTT *T* and capacity *C*, and short, thin links with capacity *c* and RTT *τ* where *c*<*C* and *T*>*τ*. Assume that type *a* users transfer data to *a*′, and can either use a ‘long-fat’ path via *c*′, *b*′, comprising two long links and one short link (*l*–*s*–*l*), or a ‘short-thin’ route via *b*, *c*, which has two short links and one long route (*s*–*l*–*s*). Similarly, assume type *b* and *c* users transfer data to *b*′ and *c*′ respectively, and can each have a similar choice of short-thin or long-fat links.

We shall suppose that there are *N*′ users of each type, who can use *n*_{p} parallel connections, and let denote the total number of connections users of each type make. Now let each user independently and selfishly seek to use the set of paths that maximize their rate. In other words, they are able to choose the path sets (*s*) and the number of connections per paths subject to the constraint, , and they seek the routes that maximize the achieved throughput .

We now show that inefficient equilibria can exist, when using the TCP utility functions described above. Consider the case when all connections are via short–long–short links (*s*–*l*–*s*), having an RTT of *T*+2*τ*. Then, there will be 2*N* connections on each short link, and *N* on each long link. To fully use each thin link, each connection will receive a rate of *c*/(2*N*); for this to happen, the Lagrange multipliers *p* must satisfyNow, on the *l*–*s*–*l* route, with RTT 2*T*+*τ*, the path Lagrange multiplier is *p*, rather than 2*p*, and the rate per connection isThis path will not be chosen, and hence *s*–*l*–*s* is indeed a Nash equilibrium providedBut in this case, the throughput is *half* of what it would be if all connections were *l*–*s*–*l*.

As shown in Key *et al*. (2006), if the RTT bias is removed so that utility functions *U*_{r} are independent of path RTT, then the Nash equilibrium is efficient and solves the global social welfare problem (equations (3.5) and (3.6)) that we now introduce.

### (c) Multipath routing and coordinated congestion control

With joint multipath routing and coordinated congestion control, for fixed numbers *N*_{s} of users of type *s*, the optimal rates for class *s* users solve the welfare maximization problem(3.5)

(3.6)Now there is a single utility per *user* *s* and is the allocation a user receives aggregated across paths. This coordinated problem is strong Lagrangian, hence has a unique optimum and its solution characterized by the Kuhn–Tucker conditions(3.7)and, as a consequence, the allocation for user *s* only puts a non-zero allocation on paths *r* whose price *p*_{r} is equal to the minimum price across possible routes. There may be only one or several such lowest cost paths. In other words, for a user *s* there is a critical value price *p*_{s} such that the prices on any path *s* uses equal *p*_{s}, and on possible paths *r* that *s* can use but does not (i.e. allocates zero to these paths), the prices must be higher than *p*_{s}.

Theorem 2.1 still applies, hence with dynamic arrivals, such coordinated controllers ensure that the schedulable region is maximized. Moreover (see Massoulié & Key 2006), the equilibrium cost of network operation is also minimized, independently of which utility functions are used for each traffic class.

The distributed rate control algorithms can be constructed for all of the above optimization problems, e.g. Kelly & Voice (2005) and Han *et al*. (2006).

### (d) Path selection and randomization

We now assume that there is a large set of possible paths that a particular source–destination pair could use, but that each end-user uses only a small number of paths at any moment in time, while choosing to alter these paths over time as better ones become available. This models the practical limitations of opening a large number of potential connections, imposed by the cost of keeping state and the difficulty of assessing path quality on a large number of paths.

Assume that class *s* users can use concurrent paths from a collection *c*, where *c*⊂(*s*), and denote by (*s*) the family of all such path collections that are allowed. For definiteness, think of (*s*) as the collection of all subsets of (*s*) of size *b*. Denote by *N*_{c} the number of users with associated set of connections equal to *c*. When the number of class *s* users equals *N*_{s}, we have the relation(3.8)The allocation to a class *s* user is then given as the solution to the optimization(3.9)over *x*_{c,r}≥0 where *N*** x** can be written as the vector of aggregate loads (

*X*

_{r}) where .

Now assume that a user has some current route set *c*, and is offered a new route set *c*′, at some fixed rate *λ*_{cc′}, where this rate is on a fast time-scale compared with the time-scale of arrivals and departures. The new route set is accepted provided the *net benefit* the user receives from the new route set is higher than that of the current route set. The users of type *s* can explore the entire space provided that for all *s*, for any *r*∈(*s*) and any set *c*∈(*s*), there is some *c*′ such that *r*∈*c*′ and *λ*_{cc′}>0.

We denote by the aggregate data rate obtained by users streaming along routes *r*∈*c*, where *x*_{c,r} is the sending rate along route *r*. We assume the following form of rate adaptation (see Kelly *et al*. 1998):(3.10)where the term *μ*_{c,r} is non-negative, satisfies and is meant to ensure non-negativity of *x*_{c,r}, while *κ*_{c,r} is a positive gain parameter.

The net benefit per unit time for type *s* users streaming along routes *r* in some set *c*, denoted by *B*_{c} is given byUsers swap from set *c* to *c*′ when the set is offered provided . For any strictly concave, continuously differentiable function *U*, this is equivalent to choosing path sets *c* with higher *rate*, *x*_{c}.

When there is a large population of users, we can model the evolution of users by deterministic mean-field equations(3.11)for some continuous Lipschitz function that is equal to 0 on _{−} and positive on (0,∞).

We can then show that rate adaptation scheme and route selection policy do indeed maximize the welfare, in that they maximize (3.9), and moreover solve the global optimization problem (3.5) and (3.6). We shall assume that utility functions *U*_{s} and the penalty function *Γ* are continuously differentiable on their domain, the former are strictly concave increasing, the latter convex increasing and that as *x*→∞. We have the following (Key *et al*. 2007).

*Any absolutely continuous solution* *to the system of ordinary differential equations (ODEs) defined by* (*3.10*) *and* (*3.11*) *converges to the set of maximizers of the welfare function*(3.12)*under the constraints* (*3.8*). *The corresponding equilibrium rates* (*x*_{r}) *are solutions of the coordinated welfare maximization problem* (*3.5*) *and* (*3.6*).

This is a powerful result, which says that path reselection provides global allocations that coincide with the optimal allocations that would arise if users had simultaneous access to the full route set (*s*). Reselection can be interpreted as a repacking algorithm that operates on a time-scale dictated by *λ*. Of course, there are practical issues that need to be addressed in directly implementing these ideas; care needs to be taken in deciding how long to try alternate paths before assessing the throughput (quality) and in allowing for statistical effects in such sampling. For flows that are ‘short’, there may be a little benefit in repeated resampling.

What happens for parallel or uncoordinated controllers? It turns out that the same results apply *provided* there is no RTT bias in the controllers. Unlike current TCP, this is another argument for removing the current RTT bias in TCP. If parallel controllers use a fixed number of paths *b*, for example, *b*=2, then to give equivalence with the coordinated controller we need to replace the utility function *U*_{s}(*x*) for the coordinated controller by .

Note that several peer-to-peer (P2P) applications such as BitTorrent effectively implement receiver-driven multipaths. Transfers take place using TCP, where throughput depends on the RTT; hence, this is an example of a multipath uncoordinated congestion controller, which uses a greedy path selection algorithm to find best paths.

## 4. Combinations of paths in series and parallel

We have just seen that suitably designed congestion controllers can combine paths in parallel and maximize utility. We now show how to achieve such a maximization when multiple paths can be used in series as well as in parallel. For instance, a source node S could send data to a destination node D via a relay node R by combining the IP paths S–R and R–D in series. Considering the two paths separately rather than as one combined S–R–D path corresponds to breaking or splitting the flow at R. This is an appropriate model when R is a node in an overlay network or is a middle-box or proxy.

The use of proxies is particularly appropriate for wireless networks, where there is an incentive to break the TCP control loop into parts to achieve better throughput, and proxies are used in practice in mobile networks. Split TCP breaks a TCP connection into two or more ‘legs’ in series, and has been widely studied (e.g. Balakrishnan *et al*. 1995; Kopartyi *et al*. 2002).

We now discuss flow controllers that seek to maximize the overall welfare for source–destination flows by exploiting arbitrary network paths, generalizing the notion of coordinated controllers.

Assume that each flow *f*, with source *s*(*f*) and destination *d*(*f*), can use a collection of paths , where each path *p* is identified by its source and destination. A path *π* with source node and destination node is also denoted (*ij*).

We denote by the rate sent for flow *f* along path (*ij*), and by the amount of data buffered at *i* for flow *f*, with the convention thatIn this context, a natural utility maximization problem is the following:(4.1)

(4.2)

(4.3)

(4.4)

(4.5)The penultimate constraint specifies that the path rates satisfy flow conservation at intermediate, relay nodes, in other words they define a *flow* from *s*(*f*) to *d*(*f*).

Now consider the following rate adaptation scheme for rates : for each path , we set(4.6)where *ϕ* is some continuous, strictly increasing function, such that . In the above, is a positive gain parameter and *p*_{ij} denotes the marginal cost of sending along path (*ij*), that is(4.7)where ** y** is the vector of path rates and

*Γ*is the network cost function.

Note that the adaptation rule (4.6) could require some to remain positive, while there is no data to forward from node *i* to node *j* at that a particular time. This can be addressed in two different ways. One could send dummy packets instead of actual data packets, while still using path (*ij*) at rate . However, we prefer to follow an alternative approach and send at rate , where(4.8)where the adjustment variable is such that(4.9)Therefore, the vector ** y** of path rates used in the definition of marginal costs in (4.7) is given by(4.10)Finally, for each

*i*, we have(4.11)One technical point has been overlooked in the above description. The quantities should remain non-negative, a property that is not guaranteed for solutions of the ODEs (4.6)–(4.11). This can be addressed by adding to the r.h.s. of (4.6) a time-dependent, non-negative term such that if .

We now verify that the stationary points of (4.6)–(4.11) are solutions of (4.1)–(4.3). First, setting , , to zero gives(4.12)Setting to zero yields(4.13)By (4.12), nodes *i* at which are such that . In view of (4.13), at such nodes *i*, it holds that either or for all outgoing paths .

Note that necessarily, the equilibrium quantities define a flow from *s*(*f*) to *d*(*f*). By (4.13), at paths (*ij*), , at which , and hence is positive, it holds that . Thus, at each concatenation of paths (*s*(*f*)*i*_{1}), (*i*_{1}*i*_{2}), …, (*i*_{m}*d*(*f*)) along which all corresponding rates are positive, by the previous argument it holds thatFurthermore, by the second part of (4.13), any concatenation of paths along which some rate equals zero is such thatThese last two properties coincide with the Kuhn–Tucker optimality condition for the welfare maximization problem (4.1) and (4.2). Therefore, any equilibrium state for (4.6)–(4.11) provides a solution to this maximization problem.

We believe that a stronger result holds, namely that the above dynamical system converges asymptotically to solutions of this maximization problem. Lyapunov function techniques described in Voice (2006), in the work of Srikant (2003) and in Georgiadis *et al*. (2006), could plausibly be adopted to the present framework.

The algorithm (4.6) is a type of back-pressure algorithm, where transformed delays are used to summarize or communicate downstream prices. The function *ϕ* allows scaling of the data queues, although the choice of *ϕ* has implications for the stability and the choice of gain parameter in the presence of a delayed feedback. In practice, the data queues could be implemented at the application layer of a node, or be thought of as virtual queues, used to summarize downstream prices that may be signalled out of band to upstream nodes.

## 5. Architecture, pricing and incentives

In this section, we briefly discuss some of the practical aspects surrounding our ideas.

To implement multipath in the current Internet, some alternative paths need to be provided to the end-users. If the end-user is an edge gateway, or a node in a commercial network, then there may already be two paths to different Internet service providers (ISPs) or different AS's (autonomous systems), perhaps provided for resilience. For a domestic subscriber, there is typically only one path to the Internet, and without source routing, the path to a destination is specified by the user's ISPs and transit ISPs. Yet the *status quo* is changing: the advent of wireless mesh networks and the emergence of wireless for last-hop access facilitates multihoming, with different access points to the Internet, while there may be incentives for ISPs to offer alternate routes. The advent of IPv6 allows different addresses to be used for different interfaces for the same host, and both multipath and addressing are currently under discussion in the IETF.

At the present time, path choice is determined by the ISPs along a path. The current pricing structure makes the link between pricing and quality unclear: ISPs essentially charge for connectivity (to domestic customers) or on the basis of 95 percentile charging for large customers connected by large fibre-optic pipes, with little relation to quality. However, if ISPs could charge users that are not their direct customers for carrying transit traffic, then there is the potential to create a market where ISPs advertise paths or themselves to end-users, and receive income for carrying transit traffic. Moreover, the effects of competition lay the foundations for linking price with quality delivered and received. In terms of architecture, this could be done via ‘stepping-stone’ routers, described in Key *et al*. (2007), which could be advertised by a type of domain name system service; the user could then choose which stepping-stone router to user. If advertised by an ISP, then the ISP would forward the traffic to the destination and the ISP might choose to advertise a set of such routers.

The question of how to recover costs or charge end-users is vexed, and does not directly fit into the current charging models for the Internet. However, related schemes such as these occur in the telephony world: calling cards and other schemes allow indirect choice, through implicit choice of backbone or international carrier.

Congestion pricing is attractive economically and theoretically, and for fast-packet networks can create a version of the ‘smart-market’, first proposed by MacKie-Mason & Varian (1995), and discussed in Gibbens & Kelly (1999). Prices that reflect the congestion price of the resources used are fed back to users who have an incentive to behave rationally and react to such prices, while network providers have an incentive to upgrade resources to match user demand.

However, this assumes price signals can be fed back to the users, perhaps via an intelligent packet marking scheme. Intelligent packet marking has been advocated as a means of more intelligently signalling congestion than the current practice of discarding packets. The simplest scheme would convey such information via a single bit, such as the explicit congestion notification bit (Floyd & Fall 1999), yet even this has not been adopted in the Internet, owing to issues of backward compatibility and needing both hosts and end-systems to behave correctly when the bit has been set. Briscoe *et al*. (2005) have proposed using an edge-based deployment of congestion notification, which may enable partial deployment in managed networks. However, the lack of progress on implementing such a price-neutral mechanism illustrates some of the technical barriers to implementing congestion pricing, let alone philosophical or economic barriers.

One of the areas currently under discussion in Next Generation Internet is charging and economics. Users appear to have a strong preference for predictable charges, such as flat rate charging, despite the fact that most users would benefit from more flexible pricing schemes (typically the majority of traffic is created by a minority of users, reflecting quoted 80–20% behaviour, symptomatic of the heavy tailed traffic nature of Internet traffic). The challenge is whether more usage-, quality- or congestion-based charging is desirable, and whether it can be combined with simple tariffs. This is a contentious issue where strong differences of opinion exist. It is interesting to note that the mobile phone market in the UK provides examples of stratified pricing, where different flat rates are linked to usage.

## 6. Concluding remarks

We have shown that a utility maximization framework is a natural one for addressing questions of resource allocation for elastic traffic, when combined with stochastic demand. In this framework, path ‘prices’ reflect congestion costs along a path. In the current Internet, such prices are signalled via packet drops, and the use of a single, dominant transport protocol, TCP, owes more to social pressure from peer groups and standards bodies than any incentive compatible behaviour on the part of users. The lack of evolution of the Internet has also meant that route choice is determined by network providers, with the end-users having a little say in the matter.

However, the current situation can be exploited to advantage by smart algorithms at the edge or end-nodes, when using overlay functionality or when an evolution of the current structure allows stepping-stone routers without recourse to overlays. In particular, we have used the example of combined multipath routing and congestion control at the end-nodes to show such smart solutions produce versatile utility-maximizing allocations, which have nice properties of maximizing the schedulable region, and minimizing network cost. In fact, some current P2P applications already implement variants of these controllers. Such controllers can work with current TCP; however, the RTT bias inherent in TCP can lead to network inefficiencies.

The use of flexible routing combined with smart congestion controllers can overcome many of the current architectural limitations of the current Internet. The one application type that is not completely accommodated in this framework is real-time streaming or real-time applications in general. Firstly, the suitability of utility maximizing allocations for real-time flows is not as clear as for elastic traffic, although one possible integration is described in Key *et al*. (2004). Secondly, it is not possible to give a hard QoS guarantees over a best-effort network. Thirdly, it is not easy to justify implementing rate-adaptive real-time streaming, since there is a little incentive for an application to limit its rate. At the time of writing, the volume of real-time traffic is small, when compared with data traffic, and some argue that this fact if coupled with a degree of over-provisioning in the network is sufficient to provide soft guarantees that are acceptable in practice.

An alternative scenario to the current *status quo* is one where some form of pricing is used to relate path prices to real prices, via congestion prices. This brings advantages in terms of controllability and incentive compatibility, and allows for the QoS differentiation for real-time traffic. Whether the hurdles of accounting, billing and diverse ownership can be overcome, or are worth overcoming, is a moot point. We have suggested a possible evolution path that may allow some intermediate form of pricing linked to quality to be introduced, provided transit ISPs can charge end-hosts for transit traffic.

## 7. Uncited references

## Acknowledgments

We gladly acknowledge the contributions of Alan Bain, Frank Kelly and Don Towsley to several of the ideas in this paper.

## Footnotes

One contribution of 16 to a Discussion Meeting Issue ‘Networks: modelling and control’.

This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

- Copyright © 2008 The Royal Society