Utility Maximization for Resolving Throughput/Reliability 

Trade-offs in an Unreliable Network with Multipath Routing 

Vladimir Marbukh 

National Institute of Standards and Technology 

100 Bureau Drive, Stop 8920, Gaithersburg, 

MD 20899-8920, USA 

Tel: 1 301 975 2235 

E-mail: marbukh@nist.gov 

ABSTRACT

This paper proposes a framework for balancing competing user 

(i.e., application) level requirements by resolving the 

corresponding trade-offs in a distributed system with limited 

resources. Assuming that each user’s preferences can be 

characterized by some utility function, the goal of balancing 

competing requirements for each user as well as across different 

users is to maximize the aggregate utility. The framework 

assumes a presence of Intelligent Plane, which isolates users from 

details of the network properties and mechanisms of 

implementation of the user level requirements. The Intelligent 

Plane performs the following tasks: (a) maps the user level 

requirements into the network resource requirements, (b) maps 

the resource congestion prices into prices of the user level 

requirements, and (c) maps the user willingness to pay for the 

user level requirements into payments for the specific sets of 

resources. Once payments for the specific sets of resources are 

identified, the resources are allocated to the users by a “TCPfriendly” algorithm. The paper discusses this framework for a 

particular case of balancing user requirements for throughput and 

survivability in an unreliable network, where survivability is 

achieved through redundancy, e.g., using multipath routing. 

Keywords

Distributed system, resource allocation, elastic user, multipath 

routing, throughput, reliability trade-offs, pricing, intelligent 

plane. 

1. INTRODUCTION 

Since network resources are shared by multiple users 

(i.e., applications) and performance of each user is 

typically characterized by multiple competing criteria, 

network management includes the following two major 

tasks: (a) making the best use of the allocated resources for 

each user by resolving the trade-offs among competing 

user criteria, and (b) sharing resources among different 

users. Framing the goal of network management as the 

aggregate utility maximization subject to the capacity 

constraints, where the aggregate utility is the sum of the 

individual user utilities, has been proposed in [1]. This 

framework is based on the concept of elastic users, capable 

of adjusting their behavior in response to congestion 

pricing signals. Papers [2]-[3] have developed a distributed 

scheme for aggregate utility maximization in a case when 

user utilities are expressed in terms of the link bandwidths. 

This scheme interprets Lagrange multipliers associated 

with capacity constraints as congestion costs of the 

corresponding resources. These costs are communicated to 

the elastic users, who adjust their resource requirements or 

willingness to pay for the resources by maximizing the 

individual net utilities. Figure 1 illustrates this scheme. 

Fig. 1. Users directly responding to resource pricing 

However, assumption [2]-[3] that user utilities are 

expressed in terms of the network resources may be too 

restrictive. Typically, users more naturally can express 

their preferences in terms of the user level requirements, 

such as rates and Quality of Service (QoS) parameters, 

rather than network level parameters, such as required 

bandwidth. Mapping user level requirements into network 

level resource requirements as well as mapping congestion 

resource pricing signals into pricing of the user level 

requirements depend on the specific network properties as 

well as specific implementation of the user level 

requirements. In the Internet with a dumb core and 

intelligent applications concentrated at the network edges 

this mapping can be performed by intelligent applications 

through probing. 

User s

Congestion pricing 

of the network 

resources

Demand or 

willingness to pay 

for network 

resources

User 1 User S

Network
Several recent proposals, starting with [4], argued in favor 

of relieving users from the burden of such probing by 

moving some intelligence to a separate “Intelligent Plane” 

(IntPlane). The IntPlane sits between the users and the 

network and hides the details of the network properties and 

user level requirements implementation mechanisms from 

the users. The advantages of such enhanced architecture 

include user convenience, possibility of optimization of the 

resource allocation and security considerations [4]. This 

paper proposes the functionality for the IntPlane as a 

mapping mechanism, which is shown on Figure 2. 

Fig. 2. Intelligent Plane as a mapping mechanism 

Each elastic user attempting to maximize its individual net 

utility informs the IntPlane on its relative marginal utilities 

and “willingness to pay” for the network resource. The 

IntPlane performs the following tasks: (a) given the amount 

of the network resources allocated to each user, the 

IntPlane optimizes the balance among competing user level 

requirements for each user, (b) maps user willingness to 

pay into payments for specific sets of the network 

resources, and (c) communicates to the user the aggregate 

congestion cost of the resources allocated to the user. Once 

the willingness to pay for the specific sets of resources is 

identified, the resources are allocated to users by a TCPtype algorithm. The “payments“ may either represent real 

funds, or be simply a parameter in the TCP-type protocol 

[5]. To ensure capability of this scheme to operate in a 

competitive (non-cooperative) environment, the resource 

allocation should be proportionally fair, meaning that 

resources are allocated to the users proportionally to the 

payments [2]-[3]. Proportional fairness ensures that both 

schemes, based on the direct user payments for the 

resources and user payments for the QoS, result in the same 

resource allocation and user payments [6]. 

This paper discusses possible implementation and 

benefits of the proposed enhanced architecture in a case of 

providing reliable services in an unreliable network. The 

reliability is achieved through redundancy by reserving 

extra bandwidth to protect against link capacity variability 

due to fading and mobility, and using multipath routing to 

protect against link failures. The packet level 

implementation of the redundancy scheme can be based on 

the route diversity coding [7]. Benefits of multipath 

routing for load balancing and protection against network 

element failures have been known for a long time [8]. 

However, research on load balancing, protection and 

restoration for wire-line and wireless networks has been 

mostly concentrated on evaluation of various performance 

and survivability metrics of certain multipath routing 

schemes [6]. While providing quantification of improving 

survivability with increase in redundancy through 

consuming more network resources, this research leaves 

aside the problem of balancing survivability and economic 

efficiency for each user as well as across different users. 

Conventional practical solutions, which offer users a 

limited set of choices with respect to survivability, attempt 

to resolve these trade-offs within a centralized framework 

by assigning the corresponding service classes. A price 

based market framework shifts choices regarding requested 

services, including survivability levels, to the users, 

assuming that users are aware of the available services and 

their prices [10]-[11]. 

The paper is organized as follows. Section II describes 

a model of the unreliable network and implementation of 

the reliable throughput. Section III introduces user utility 

of obtaining certain QoS and formulates the corresponding 

aggregate utility maximization framework. Section IV 

briefly extends decentralized aggregate utility 

maximization framework [2]-[3] to a case when each user 

is aware of mapping its QoS requirements into the 

requirements for the network resources. The 

decentralization is based on congestion pricing of the 

resources and elastic users responding to these pricing 

signals by maximizing their individual net utilities 

expressed in terms of the requested network resources. 

Section V develops a decentralized aggregate utility 

maximization framework assuming that users are unaware 

of the network properties and implementation of the user 

level requirements. The decentralization is based on 

proportionally fair pricing of the user level requirements 

and elastic users responding to these pricing signals by 

maximizing their individual net utilities expressed in terms 

of the user level parameters. The mapping between user 

User s

Pricing for user level 

(QoS) parameters 

Demand or 

willingness to pay 

for user level (QoS) 

parameters

User 1 User S

Intelligent Plane

Demand or willingness 

to pay for network 

resources

Congestion pricing of 

the network resources

Network
and network level parameters is done by the IntPlane. 

Section VI considers some examples and discusses the 

implication. Finally, conclusion briefly summarizes the 

proposed framework and proposes directions for future 

research. 

. 

2. MODEL 

Subsection A defines two user s ∈ S QoS 

parameters: the reliable throughput μ s and the 

corresponding reliability exponent s γ . Subsection B 

introduces a “fair” bandwidth sharing with controlled 

portions of link bandwidths allocated to different users. 

This bandwidth sharing allows for implementation of the 

reliable throughput by creating a “safety margin” for the 

fluctuating instantaneous user throughput. Subsection C 

describes an approximation for the reliability exponent 

used in the remainder of the paper. 

2.1 User level parameters 

Consider a network with link capacities l c being subject 

to variability due to fading, mobility, node and link 

reliability, etc. Each network user s ∈ S is uniquely 

identified by its origin-destination and user level Quality of 

Service (QoS) requirements. Presence of several users 

with the same origin-destination models different types of 

applications with the same origin-destination, e.g., voice 

and video. We assume that link capacity fluctuations occur 

on such fast timescale that they cannot be completely 

absorbed by the network management actions. Due to 

these fluctuations, link capacities l c are in effect random 

variables and thus it may be difficult or even impossible to 

guarantee a fixed bandwidth (throughput) to a user. 

Instead it may be more natural to view the instantaneous 

aggregate throughput s x for a user s ∈ S as a random 

variable. Due to possible large fluctuations in the 

instantaneous aggregate throughput s x users may prefer to 

characterize their requirements in terms of the pair 

( , ) s s μ γ of the “reliable” aggregate throughput μ s and 

the corresponding reliability exponent s γ quantifying the 

confidence level that the instantaneous throughput s x does 

not deteriorate below μ s , where 

 ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

≤

≤ = − } ~ {{ } log

s s

s s

s P x x

P x μ γ (1) 

and the average aggregate bandwidth reserved for user s

is s x

~ . Figure 3 illustrates that creating a “safety margin” 

s s s ∆ = x − μ ~ increases confidence that the instantaneous 

throughput s x would not deteriorate below μ s . 

Fig. 3. Reliable aggregate throughput 

Note that besides reserved average aggregate throughput 

s x

~ and reliable throughput μ s , reliability exponent s γ

also depends on: (a) probability distribution of the random 

link capacities l c , (b) mechanism for sharing of the 

instantaneous link bandwidth among different users, (c) 

implementation of the reliable throughput μ s , given 

resources allocated to user s , and (d) bandwidths reserved 

on specific routes. This paper assumes that random link 

capacities l c are jointly statistically independent for all 

links l ∈ L . Assumptions (b)-(d) are described in the next 

two subsections. 

This paper assumes that each user s instantaneous 

aggregate throughput s x can be approximated by a 

normally distributed random variable with average s x

~ and 

standard deviation σ s , and thus reliability exponent (1) is 

 ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − = − Φ

s

s s

s

x

σ

μ γ

~

log (2) 

where 

 ( ) ∫

−∞

Φ = −

ξ

η η

π

ξ exp 2 d 2 ( ) 2 (3) 

Note that approximation (2)-(3) neglects small probability 

event that the bandwidth is negative. In a case of high 

reliability requirements: γ s → ∞ , reliability exponent (2) 

can be asymptotically approximated as follows: 

 2

2 ) ~( 2

1 ~ s s

s

s x μ

σ

γ − (4) 

μ s

s x

s x

~

∆s

time
2.2 Reliable Throughput 

We assume that each user s is allocated a certain 

controlled portion φls of the link l bandwidth l c

~ , or 

equivalently, the average bandwidth ls l ls x c φ ~ ~ = , where 

average capacity of a link l is [ ] ~

l l c = E c , and 

= ∑ ≤ 1 ∈

Σ

s S

ls

def

φl φ . The instantaneous bandwidth allocated 

to a user s on a link l is a random variable 

( ) ls l ls l l ls x c c c x ~ ~ = φ = . In a case of small variability in 

the link capacities it is convenient to introduce “small” 

random variables l l l c c

~ ξ = 1− with zero averages 

E[ξ l ] = 0 , so that the instantaneous bandwidth allocated 

to a user s on a link l is 

 ls l ls x x

~ = (1−ξ ) (5) 

In a particular case of a link failure model, when 

operational link l has capacity l l c = cˆ and failed link has 

capacity cl = 0 it is convenient to introduce binary 

random variables δ l = 0 if link l is operational and 

δ l = 1 otherwise, so that the instantaneous link l

bandwidth is l l l c = (1−δ )cˆ , and ξ l = δ l − δ l , where 

[ ] δ l = E δ l . In this particular case the instantaneous 

bandwidth (5) is ls l ls x = (1−δ )xˆ , where ls l ls xˆ = cˆ φ . 

The rest of this subsection discusses implementation of 

the reliable throughput μ s , given the instantaneous link 

bandwidths sl x allocated to user s . Given vector 

X (x ,l L) s = sl ∈ , the maximum achievable user s

instantaneous aggregate throughput is ∑

∈

=

( ) * M s Xs l

s sl x x , 

where ( ) * M s X s is the corresponding min-cut. This paper 

assumes a suboptimal implementation of the reliable 

throughput, based on the route diversity coding [4] and 

shown on Figure 4. 

Fig. 4. Route diversity coding 

In this implementation, after adding redundant bits and 

coding, user s ∈ S data stream of rate μ s is transformed 

into stream of higher rate s s x ≥ μ ~ . This resulting stream 

is split into flows sr x

~ over feasible routes Rs r ∈ with the 

same origin-destination: 

 ∑

∈

= Rs r

s sr x x ~ ~ . (6) 

User s instantaneous throughput, i.e., rate of the user 

stream received at the destination, is 

 ∑

∈

= Rs r

s sr x x , (7) 

where the instantaneous throughput over route Rs r ∈ is 

 sr r sr x x

~ = (1−ξ ) (8) 

and the normalized variability of a route r capacity is 

characterized by random variable 

 ∏∈

= − − l r

r l ξ 1 (1 ξ ) . (9) 

The reliability exponent (1) quantifies the possibility of 

reconstructing user s data stream at the destination [4]. 

Note that formula (9) is based on the assumption that link 

capacities fluctuate at much faster time scale than time 

needed for a packet to reach its destination. In the opposite 

extreme case the normalized variability of a route r

capacity is characterized by random variable 

l r ξ r = 1− max(1−ξ l ), ∈ . Our analysis can be 

easily carried out for this case also. 

Calculation of the reliability exponent (1) is 

comparatively simple in a case when routes Rs r ∈ do not 

have overlapping links. In this case the aggregate 

instantaneous throughput (7) is a sum of jointly statistically 

independent random variables since ξ r are jointly 

statistically independent random variables for Rs r ∈ . 

When routes Rs r ∈ do have overlapping links, 

calculation of the reliability exponent (1) is generally a 

difficult problem [9]. 

2.3 Approximation for Reliability Exponent 

We approximate the reliability exponent (1) by the 

leading term in the asymptotic expansion (4): 

 ( )2

2

~

2

1 s s

s

s x μ

σ

γ = − , (10) 

where user s average aggregate throughput is 

 ∑

∈

= Rs r

s sr x x ~ ~ (11) 

the variance of the aggregate throughput is 

Code Decode

Network

Data Data 1r x

2r x

3r x μ s s x s x

~

min( , ) s s x μ
 ∑

∈

= Rs r r

s r r sr sr x x

1 2

1 2 1 2

,

2 2 ~ ~ σ θ (12) 

the “normalized correlation” between route Rs r1 ,r2 ∈

capacities is characterized by 

 ∑

∈

=

1I 2

1 2

2 2

l r r

θ r r θ l (13) 

and the normalized variance of the link l capacity is 

[ ] 2 2 θ l = E ξ l . Note that matrix ( ) Rs r r s r r ∈ Θ = 1 2 1 2 ,

2 θ is 

symmetric and positive: 2 2

1 2 2 1 θ r r = θ r r and 

( ) 2 2 2

1 2 1 2 0 min , ≤ θ r r ≤ θ r θ r , 1 2 ∀r ,r . Also note that 

expression (10) can be obtained from a Gaussian link 

model in a large deviation regime of high reliability [12]. 

For a particular model of link failures the normalized 

variance of the link l capacity is ( ) θ l = δ l 1− δ l

2 , where 

the probability of link l failure is ∈[0,1] δ l . 

 Reliability exponent (10) can be expressed as 

follows: 

 

1

,

2

2

1 2

1 2 1 2

1 1

2

1 −

∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = − ∑

Rs r r

r r sr sr

s

s θ α α

ω

γ (14) 

in terms of the user s redundancy factor, i.e., the number 

of bits transmitted per a bit of the “payload” [7], 

 ∑

∈

= Rs r

sr

s

def

s x

1 ~

μ

ω (15) 

and portions of load routed on feasible paths Rs r ∈ are 

 s s sr

def

sr x

~ ( )

−1 α = ω μ (16) 

where 

 ω s ≥ 1 (17) 

 ∑ = 1 ∈Rs r

α sr . (18) 

Given load allocation vector ( , ) s sr Rs α = α r ∈ , the 

upper limit on reliability exponent (14), achieved as 

ω s → ∞ , is 

 

1

,

2

1 2

1 2 1 2 2

1 ˆ

−

∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∑

Rs r r

s θ r r α srα sr γ (19) 

Given upper limit (19), the minimum redundancy (15) 

required to achieve reliability exponent γ for user s is 

 ( ) 1

1 ˆ −

= − s ω γ γ (20) 

If routes Rs r ∈ do not have overlapping links, formula 

(12) takes the following form 

 ∑( ) ∈

= Rs r

s r sr x

2 ~ 2

σ θ (21) 

and thus, formula (14) simplifies as follows: 

 

1

2 2

2

1 1

2

1 −

∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = − ∑

Rs r

r sr

s

s θ α

ω

γ (22) 

where we simplified notations as follows: 2 2 θ r = θ rr . 

Given redundancy factor ω s , one may attempt to 

maximize the reliability exponent (14): 

 s s sr

γ γ α 0

* max≥

= (23) 

subject to constraints (18). 

Theorem 1. Given redundancy factor ω s and network 

properties represented by matrix Θs , solution to 

optimization problem (22)-(23), (18) is 

 

1

,

2

2

*

1 2

1 2

1 1

2

1 −

∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = − ∑

Rs r r

r r

s

s t

ω

γ (24) 

and is achieved for load allocation 

 ∑′ ′∈

= ′ ′

Rs r r

sr r r r r t t

1 2

1 2 1 2

,

* 2 2 α (25) 

where symmetric and positive matrix ( ) Rs r r s r r T t ∈ = 1 2 1 2 ,

2 is the 

inverse to Θs : −1 Ts = Θs . 

Proof. The optimal load allocation is determined by 

solution to the following optimization problem: 

 ∑

∈ s s r r R

r r sr sr

1 2

1 2 1 2

,

2 min θ α α α

 (26) 

subject to constraints (18). The Lagrangian for (25), (18) is 

 ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∑ + − ∑ ∈ s ∈Rs r

sr

r r R

L θ r r α srα sr λ 1 α

1 2

1 2 1 2

,

2

and, due to convexity, the corresponding necessary and 

sufficient Kuhn-Tucker conditions form the following 

linear system [13]: 

 0 2 ∂ = ∑ − = ′∈

α θ ′α ′ λ

Rs r

L sr rr sr (27) 

where Lagrange multiplier λ is determined by (18). This 

ends the proof. 

The following statements directly follow from Theorem 

1. 

Corollary 1. Given the network properties represented 

by matrix Θs , the upper limit on the reliability exponent 

(10), achieved as redundancy factor ω s → ∞ , is 
 

1

,

* 2

1 2

1 2 2

1 ˆ

−

∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∑

Rs r r

s r r γ t (28) 

Corollary 2. If routes Rs r ∈ do not have overlapping 

links, the maximal reliability exponents (24) is 

 

1

2

2

* 1 1

2

1 −

∈

−

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = − ∑

Rs r

r

s

s θ

ω

γ (29) 

the optimal load allocation (25) is 

 ∑′∈

−

′

− = Rs r

sr r r

* 2 2 α θ θ (30) 

and the upper limit (28) is 

 

1

* 2

2

1 ˆ

−

∈

−

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∑

Rs r

s θ r γ (31) 

3. GOAL OF NETWORK MANAGEMENT 

Subsection A introduces individual user utility of 

obtaining service parameters ( , ) s s μ γ . Subsection B 

formulates the aggregate utility maximization framework 

[1] for a particular case of balancing competing 

requirements for reliable throughput and the corresponding 

reliability for each user as well as across different users. 

3.1 User Utilities 

Let h (x,μ) s be a function, monotonously increasing in 

both arguments 0 ≤ μ ≤ x < ∞ . Consider elastic user s

whose satisfaction of obtaining service with parameters 

(μ,γ ) is characterized by a utility function 

 (μ,γ ) (μ) (γ ) s s s U = u v , (32) 

where function (μ) us is a conditional average over the 

aggregate rate s x : 

 us μ = Ex [ ] h xs μ xs > μ s ( ) ( , ) , (33) 

and function (γ ) s v is monotonously increasing for 

0 ≤ γ < ∞ . Note that under large deviation regime of 

high reliability, conditional average in (32) can be 

approximated by the corresponding unconditional average. 

Figures 5 and 6 sketch typical utility functions (μ) us and 

(γ ) s v respectively. 

Definition (32)-(33) is quite flexible, covering a wide 

range of possibilities. Consider some particular cases. 

User s having “hard” requirements on the reliability 

parameter min

s s γ ≥ γ is characterized by utility function 

(32)-(33), where 

 ( ) ( ) min

s s v γ = χ γ −γ , 

(34) 

and step-wise function is χ(γ ) = 1 if γ > 0 , and 

χ(γ ) = 0 if γ ≤ 0 . 

Fig. 5. Typical user utility of the reliable throughput 

Fig. 6. Typical user utility of the reliability exponent 

User s , elastic with respect to the reliable throughput μ , 

is characterized by utility (32)-(33), where function 

( ,μ) (μ) s us h x ≡ does not depend on the actual random 

aggregate throughput x ∈[μ,∞) and depends only on the 

reliable aggregate throughput μ ∈[0,∞). A particular 

case (32)-(34) with 0 min γ s = describes an elastic user 

concerned with the average throughput: ( ) [ ] s s s U = u E x . 

A particular case of (32)-(34) with 0 min γ s = and function 

h (x, ) u (x) s μ ≡ s independent of the reliable throughput 

μ ∈[0,∞) describes an elastic user whose satisfaction is 

characterized by the average utility of the instantaneous 

aggregate throughput: [ ( )] s s s U = E u x . 

0

us

μ

0

s v

γ

1
3.2 Aggregate Utility Maximization Problem 

S. Shenker has proposed [1] aggregate utility 

maximization to be the objective of network management. 

In our particular case the aggregate utility maximization 

framework takes the following form: 

 ∑ ( ) s

Us s s max μ ,γ (35) 

over user level requirements ( , ) ( , ,s S) μ γ = μ s γ s ∈

and vector : , ) ~( ~ sr Rs X = x s ∈ S r ∈ subject to 

constraints (10), link capacity constraints 

 l l y c ~ ~ ≤ , 

(36) 

flow non-negativity constraints: 0 ~xsr ≥ and constraints 

on the reliable throughput ≤ s ≤ xs , s ∈ S ~ 0 μ , where 

the link l load is 

 ∑ ∑∈ ⊆

= s R r l r

l sr

s

y x :

~ ~ (37) 

Optimization problem (35) is equivalent to the following 

optimization problem 

 W

X

~ , ,

max

μ γ

 (38) 

subject to the same constraints except (37), where the 

“social welfare” is 

 = ∑ ( ) () −∑

l

l l

s

s s s W U f y

~ μ ,γ (39) 

and appropriately selected penalty functions f (y) l may 

quantify the congestion penalty in terms of delays or packet 

loss as link utilization approaches link capacities [3]. For 

packet networks it is often assumed [14] 

 ) ~ f ( y) y (c y l = l − . (40) 

A particular case of optimization problem (38)-(39), 

when each user s specifies its service requirements 

( , ) s s μ γ correspond to the following traffic engineering 

problem: 

 ∑ ∑∑ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

∈ ⊆ ≥ l sR r l r

l sr x s sr

f x : 0 ~

min ~ (41) 

subject to constraints 

x x x s S

s Rs r r

s r r sr sr

r R

sr ∀ ∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ ∑ ≥ + ∑ ⊆ ∈

, ~ ~ 2 ~

1 2

,

2

1 2

1 2 1 2 μ γ θ (42) 

4. USERS ALLOCATE BANDWIDTH 

This section assumes that each s ∈ S (a) is aware of the 

network properties quantified by matrix Θs , and (b) 

capable of finding the optimal balance ( , ) * *

s s μ γ between 

competing requirements for the reliable throughput μ s and the 

corresponding reliability exponent s γ by maximizing the 

individual utility, given allocated bandwidths 

, ) ~( ~

s sr Rs X = x r ∈ :

 { 2 ) ( )} ~ argmax (

0

* γ σ γ γ

γ s s s s s = u x − v ≥

 (43) 

 * * 2 ~ s s s s μ = x −σ γ (44) 

Once optimization (43)-(44) is performed and thus 

individual utilities with respect to the bandwidth 

 2 ) ( ) ~ ) ( ~

( ~ * *

s s s s s s s s U X = u x −σ γ v γ (45) 

are identified, the aggregate utility maximization problem 

(38)-(39)becomes 

 ( ) ⎪⎭

⎪

⎬

⎫

⎪⎩

⎪

⎨

⎧

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ ∑ −∑ ∑∑

l sR r l∈r⊂

l sr

s

s s X s

U X f x :

~ max ~ ~ ~ (46) 

Note that under hard constraints on the reliability (34) the 

optimal operating point (43)-(44) is 

 ( ) * * min min 2 , ~ ( , ) s s s s s s μ γ = x −σ γ γ Σ (47) 

and thus individual utility (45) is 

 2 ) ( ) ~ ) ( ~

( ~ min min

s s s s s s s s U X = u x −σ γ v γ (48) 

This section describes distributed algorithms to aggregate 

utility maximization (46), assuming that user s ∈ S utility 

function Us

~ is known only to this user. The algorithms are the 

straightforward extension of algorithms proposed in [2]-[3] for a 

case ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∑

∈Rs r

s s sr U U x ~ ~ ~ , and assume that elastic users 

respond to congestion price of the bandwidth. Subsection A 

describes algorithm based on users adjusting bandwidth 

requirements in response to bandwidth prices. Subsection B 

describes algorithms based on users adjusting their willingness to 

pay for bandwidth in response to rates charged for the bandwidth. 

4.1 Users Adjusting Bandwidth Requests 

Consider the following individual optimization problem 

for a user s attempting to maximize its individual net 

utility: 

⎭

⎬

⎫

⎩

⎨

⎧ − − ∑

∈ ≥ ≥ s sr r R

s s s s r sr x

u x v d x

~ 2 ) ( ) ~ maxmax (

0 0 ~ σ γ γγ

 (49) 

where the route r price is: 
 ∑

∈

= ′

l r

r l l d f y ) ~( (50) 

the link l price ) ~(l l f ′ y is a derivative of the congestion 

penalty function for this link ) ~(l l f y , and the link load l y

~

is given by (37). Solving individual optimization problem 

(49)-(50) by each user s ∈ S also maximizes the 

aggregate utility (46) if the link prices are “right”, meaning 

that derivatives ) ~(l l f ′ y are calculated at the optimal link 

l load y y l opt

l = l , ∀ ~ ~ . 

Kuhn-Tucker necessary conditions for a vector 

, ) ~( ~

s sr Rs X = x r ∈ to solve (49) are as follows [13]: 

 r s

s

r

r R

s rr sr if d u

u

d

x

s

≤ ′ ′ ∑ = − ′∈

′ ′

− 1 ~ 2 1 2 γσ θ (51) 

 xsr = 0 if dr > u′ ~ (52) 

where u′

s (μ) = dus (μ) dμ is the derivative of the user 

s utility at the point of this user reliable throughput 

μ = μ s and σ s is given by (12). If user utilities 

) ~( ~Us X s are concave, (51)-(52) are also the 

corresponding sufficient conditions [13]. In this case, user 

s optimal response to the pricing signals r d is requesting 

bandwidth vector , ) ~( ~

s sr Rs X = x r ∈ , which solves 

system (51)-(52) and thus maximizes its individual net 

utility (49)-(50). 

Generally, optima in (46) and (49) are achieved when 

some flows are zero: 0 ~xsr = for some r ∈ Rs , s ∈ S . 

In fact, this situation is typical in presence of “high cost”, 

e.g., highly congested or very “long” routes, when optimal 

solution is not to use these “expensive” routes. For 

example, conventional shortest path routing uses only one, 

“optimal” route. Given μ ≥ 0 , define a subset of feasible 

routes participating in user s ∈ S transmission: 

 ( ) { : ( ) , } s s r Rs R μ = r u′ μ > d r ∈ (53) 

Consider two routes , ( ) r1 r2 ∈ Rs μ , which do not have 

overlapping link with each other or with any other route 

(μ) Rs ∀r ∈ : riIr = ∅ , i = 1,2 . In this case we 

have from (51): 

 

sr s

sr s

r

r

sr

sr

d u

d u

x

x

− ′

− ′

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

=

2

1

1

2

2

1

1

1

~

~ 2

θ

θ

 (54) 

It follows from (54) that if two routes , ( ) r1 r2 ∈ Rs μ

have the same cost: 1 2 dr = dr , then the user transmission 

rate on these routes should be inversely proportional to the 

variances of the fluctuating bandwidths of the 

corresponding routes: 

 ( )2

1 2 2 1

~ ~ sr sr r r x x = θ θ (55) 

This conclusion that load allocation among several routes 

of the same cost should send more traffic on the better 

quality routes while preserving routing diversity is 

intuitively plausible. 

 In a case of hard reliability constraints (34) when 

feasible routes Rs r ∈ do not have overlapping links, the 

optimal flow vector , ) ~( ~

s sr Rs X = x r ∈ can be identified 

explicitly. Indeed, in this case Kuhn-Tucker equations (51) 

take the following form: 

 ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

′ = −

s

r

r

s

sr u

d

x max 0, 1

2

~ 2 γθ

σ

 (56) 

Summarizing (56) over Rs r ∈ we obtain: 

 ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

′ = ∑ − ∈ s

r

r R r

s

s u

d

x

s

max 0, 1 1

2

~ 2

γ θ

σ

 (57) 

Substituting (57) into (44) we obtain the following 

expression for σ s : 

 

⎥

⎥

⎦

⎤

⎢

⎢

⎣

⎡ − ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

′ = ∑ −

∈

γ

γ θ

μ σ

μ

2 1 1

2 ( )

2 * Rs r s r

r

s u

d

 (58) 

Substituting σ s into (56) we obtain the following 

expression for the flows , ( ) ~xsr r ∈ Rs μ : 

2

( )

2

1 1

1 2 1

~

s r

r

r R s

r

r

sr u

d

u

d

x

s

θ

γ θ

μ

μ

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

′ −

−⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

′ −

=

∑′∈

′

′

 (59) 

Substituting (59) into right-hand side of the following 

necessary condition for optimality in (49) 

 ∑

∈

′ = Rs r

s sr u x

1 ~

μ

 (60) 

we obtain a quadratic algebraic equation for the derivative 

us

′ , yielding the reliable throughput μ = μ s . After that, 

flows are determined by (59). 

4.2 Uses Adjusting Willingness to Pay 

Solving individual optimization problem (49) by each 

user results in a decentralized maximization of the 

aggregate utility assuming convexity and “right” link 

prices. Formula (50) can be used as a basis for finding the 

right prices by a distributed algorithm [2], when users 

declare their requirements for bandwidth ) ~( ~

s sr X = x , 

then “the network” informs users on the route costs (50), 
then users adjust their bandwidth requirements, etc. This 

subsection describes a distributed algorithm for finding the 

“right” prices, based on the user willingness-to-pay. This 

algorithm, being a straightforward extension of the 

corresponding algorithm [3], probably better fits into 

existing Internet architecture. 

Consider a situation when, given bandwidth vector 

, ) ~( ~

s sr Rs X = x r ∈ , each user s determines its 

willingness to pay wsr for bandwidth on each route 

Rs r ∈ by maximizing its individual net utility: 

 ⎪⎭

⎪

⎬

⎫

⎪⎩

⎪

⎨

⎧ −⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

∑ ∑ ∈ ∈ ≥ s s sr r R

sr

r R

s sr sr w

U (w p ) w ~ max

0

 (61) 

where psr is the rate charged by the network for a unit of 

bandwidth on route Rs r ∈ . After user s informs the 

network on the vector ( , ) sr Rs w r ∈ , the network, 

running Transmission Control Protocol – Active Queue 

Management (TCP-AQM) protocol [5], adjusts bandwidth 

vector , ) ~( ~

s sr Rs X = x r ∈ according to the following 

system of differential equations: 

 ( ) sr sr sr r x k w x d ~ ~ ~ = − & (62) 

Assuming that each user s monitors its rates r x

~ on 

routes Rs r ∈ and instantaneously adjusts parameters wsr

by solving optimization problem (61) the user willingnessto-pay is 

 

sr

s s

sr sr x

U X

w x ~

) ~

( ~ ~

∂

∂ = (63) 

Consider rate of change of the social welfare (39) with 

time: 

 ∑ ∑∈ ∂

∂ = s R r

sr

s sr

x

x

W W& ~& ~ (64) 

Substituting (62)-(63) into right-hand side of (64) we 

obtain 

0 ~ ~

~

~ ~ ~

~

2

≥ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − ∂

∂ =

= ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − ∂

∂ =

∑ ∑

∑ ∑

∈

∈

sr

s R r

r

sr

s

sr

s R r

r

sr

sr

r

sr

s

d x

x

U

d x

x

w d

x

U W

s

s

&

 (65) 

Thus social welfare (39) is a Lyapunov function for the 

dynamic system (62)-(63). Note that since social welfare 

(39) may have multiple local maxima for streaming 

applications [1], inequality (65) only implies that the 

bandwidth adjustment process (62)-(63) converges to the 

local maximum of the social welfare (39). 

 

5. QOS PRICING 

This section proposes algorithms for aggregate utility 

maximization (35) assuming that users are unaware of the 

network layer parameters. These algorithms assume 

presence of the IntPlane, which isolates users from the 

network properties and QoS implementation mechanisms. 

Subsection A considers implementation and pricing of the 

service parameters ( , ) s s μ γ by the IntPlane, given price 

of the bandwidth ( , ) r Rs d r ∈ . This setting may describe 

a case of “fat” links carrying traffic from a large number of 

users, so that the link costs can be considered fairly stable. 

Subsection B describes a cross-layer, distributed algorithm 

for aggregate utility maximization,. The algorithm is based 

on user willingness to pay for service parameters ( , ) s s μ γ

and results in proportionally fair pricing. Subsection B 

also demonstrates that under certain, rather restrictive, 

conditions this algorithm maximizes the aggregate utility. 

5.1 Users Requesting QoS 

Consider a user s ∈ S individual optimization problem 

 max{ } ( , ) ( ) , 0

μ γ μ γ

μ γ

Us − Ds ≥

 (66) 

where the price of a unit of reliable throughput for user s

is 

 

s

s

s

d D

1 γ γˆ

~

− = (67) 

the price of a unit of the average throughput for user s is 

 ∑

∈

= Rs rds drα sr

~ (68) 

the upper limit on the reliability exponent s γˆ is given by 

(19), cost of a route r is r d and vector 

( , ) s sr Rs α = α r ∈ characterizes implementation of user 

s requirements. 

Given implementation of all user level requirements 

( ,s S) α = α s ∈ , maximization individual net utility (66) 

by each user s ∈ S also maximizes the aggregate utility: 

(69)

1 ˆ ( , ) :

∑ ∑∑ ∑ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

− − ls R r l∈r⊂

sr

s s

s

l

s

s s s

s

U f α

γ γ

μ μ γ

over user level requirements ( , : s S) μ s γ s ∈ if the route 

costs are 
 ∑∑ ∑

∈ ⊂ ∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

− = ′

ls R r r l r

sr

s s

s

r l

s

d f 1 ˆ :α

γ γ

μ (70) 

The problem of joint maximization of the aggregate 

utility (69) over user level parameters ( , : s S) μ s γ s ∈

and implementation ( ,r R ,s S) α sr ∈ s ∈ can be 

decomposed into (a) maximization of individual net utility 

(66) by each user s ∈ S , and (b) minimization of the cost 

of implementation of user s ∈ S requirements by the 

IntPlane: 

∑ ∑ ∈

∈

≥ −

=

s

s

r r R

r sr

r r R

r r sr sr

Ds d α

γ θ α α α

1 2

1 2 1 2

,

0 2

*

1 2

1 min ~ (71) 

subject to constraints (18). 

Cost minimization (71) subject to constraint (18) can be 

carried out as follows. Consider optimization problem: 

 ∑

∈ ≥

=

s sr r r R

r r sr sr

1 2

1 2 1 2

,

2

0

min ~θ θ α α α (72) 

subject to constraints 

 d d

Rs r

r sr

~ ∑ ≤ ∈

α (73) 

and constraints (18). Note that this optimization problem 

intends to maximize the bound on the reliability exponent 

(19) subject to upper constraint on the average route cost, 

or, equivalently, to minimize the average route cost subject 

to lower bound on the reliability exponent (19). The 

Largangian for this optimization problem is [13]: 

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

+ − ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − −

= −

∑ ∑

∑

∈ ∈

∈

s s

s

r R

sr

r R

r sr

r r R

r r sr sr

d d

L

λ α λ α

θ α α

1 ~ 1 2

,

2

1 2

1 2 1 2

 (74) 

where the corresponding Largange multipliers are λ1 and 

λ2 . Optimization problem (72)-(73), (18) is convex and 

thus, the necessary and sufficient conditions for a vector 

( , ) s sr Rs α = α r ∈ to be a solution to this optimization 

problem are as follows [13]: 

0 0

0

2 1

2 1 2 1

2

= − ≤

∑ = − − > ′∈

′ ′

sr r

r r

r R

rr sr

if d

d if d

s

α λ λ

θ α λ λ λ λ

 (75) 

where Largange multipliers are λ1 and λ2 are determined 

from (18) and (73). 

It can be shown that , 0 λ1 λ2 ≥ , and thus the structure 

of the solution to (72)-(73), (18) is as follows. Without 

loss of generality, assume that all K = dim Rs routes 

Rs r ∈ are arranged in M mutually exclusive groups 

Gm ,m = 1,..,M so that all routes in the same group have 

the same cost m d

~ and cost increases as the group number 

increases: 

14 24 4 34

64 74 4 84

14 24 4 34

64 74 4 84

14243

64748

M

M

M

d

G

K K

d

G

K K

d

G

d d K d d d d

~ ~

1

~

1 .. .. ... .. 1

2

2

1 2

1

1

1

= =

+

=

= = < = = < < = = −

Routes within each group are numbered arbitrarily. To 

avoid trivialities we further in the paper assume that 

r Rs θ > 0, ∀r ∈ . Since solution to system (75) is 

 ∑=

= −

Km

j

i mij d j t

1

2 1

2 α max(0,λ λ ), (76) 

where matrix ( )Km

m mij i j

T t , 1

2

= = is inverse to the matrix 

( )Km

i j m ij , 1

2

= Θ = θ , at the optimum the load is spread over 

feasible routes from groups Gi ,i = 1,..,m and m is 

determined by conditions: 2 1 1 2 1

~ , ~

d m ≤ λ λ d m+ > λ λ . 

Substituting (76) into conditions (73) and (18) results in 

explicit, though elaborate, expressions for Lagrange 

multipliers λ1 and λ2 . Thus, the complexity of solving 

optimization problem (72)-(73), (18) lies in inverting 

matrices Θm ,m = 1,,.., M . 

Once solution )

~ α = α(d , )~

( ~ ~ θ = θ d to optimization 

problem (72)-(73), (18) is found, solution to optimization 

problem (71), (18) is ) ~

( opt opt α = α d , where opt d

~ and 

opt Ds , solve the following optimization problem: 

 

)

~

(

~ 1 2

~

min ~ ~

*

d

d D

d s

− γθ

= (77) 

subject to constraint 

 M d d d ~ ~ ~ 1 ≤ ≤ (78) 

It can be shown that (76)-(77) is a convex optimization 

problem, which can be solved by fixed points as follows: 

 λ γθ

γθ

1

~ 2 − 2 d = 

where λ1 is the Lagrange multiplier in (74). It is also 

possible to show existence of M constants 

 0 .. 1 0 1 2 1

def

M M

def

= η < η ≤ η ≤ ≤ η ≤ η + = (79) 
such that if ˆ [ , ) 1

*

s η m η m γ γ ∈ − then 

i K m 0, i 1,.., * α > = and i 0, i K m 1,..,K * α = = + . 

Once optimal load split is identified, the redundancy factor 

is given by (20) and the optimal reliable throughput is 

determined by solution to the corresponding individual 

optimization problem. 

In a case of a user s concerned only with the average 

throughput: γ s → 0, solution to (71)-(18) sends entire 

traffic on minimum cost routes G1 r ∈ . If there are 

several minimum cost routes: dim 2 G1 ≥ , a situation of 

minimum equal cost multipath arises. The optimal load 

split among minimum cost routes G1 r ∈ is 

 

otherwise

t t if k K

k

K

j

kj

K

i j

k ij

0

1,.., 1

1

2

1

1

, 1

2

1

1 1

=

= ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∑ ∑=

−

=

α

α

 (80) 

and the redundancy factor is ω = 1. In another extreme case of 

very reliability sensitive user s : ˆ 0 * γ → γ s − , the optimal 

load split among feasible routes Rs r ∈ is given by (25), and 

redundancy factor is given by (20). 

5.2 Users Willingness to Pay for QoS 

We assume that user s is charged for service (μ,γ ) a 

price proportional to the reliable throughput μ

 Ps = psμ (81) 

where rate ps is some increasing functions of the 

reliability exponent γ . Given service (μ,γ ) and price 

structure (81), user s (a) determines and communicates to 

the IntPlane its willingness to pay for the service w = ws , 

where 

 w { } Us ( ) w ps w w s = − ≥

argmax ,γ 0

 (82) 

and (b) estimates and communicates to the IntPlane the 

relative importance of its competing requirements for the 

reliable throughput μ and reliability exponent γ

quantified by its relative marginal utility 

 γ μ

μ γ ∂

∂

∂

∂ = s s

s

U U

g ( , ) (83) 

 Based on this information and being aware of the 

network properties quantified by matrix Θ , the IntPlane 

performs the following tasks: (a) maximizes user s utility 

(μ,γ ) Us , given bandwidth vector X s

~ , as follows: 

 { [ ] } Xs s gs s s s s μ& = k 1+ (μ ,γ ) ∂γ ∂μ ~ (84) 

where k > 0 is some constant, and (b) allocates portions 

 

sr

s

s

sr

sr x

x

~

~

∂

∂ = μ

μ

π (85) 

of user s payment (82) to “pay” for the route Rs r ∈

bandwidths, where the reliable throughput is 

 μ σ 2γ ~ s s s = x − . (86) 

Combining (85) with (86) we obtain 

 ( ) s

sr

sr sr r s

x

x

μ

π γ θ σ

~ ~ 1 2 2 −1 = − (87) 

It is easy to verify that 

 1 ~

1 ~ ≡ ∂

∂ ∑

∈Rs r sr

s

sr

s x

x μ

μ

 (88) 

and thus the proposed payment scheme is proportionally 

fair [2]-[3]. Once payments wsr = wsπ sr are identified, 

the flow vector ) ~( ~ sr X = x is adjusted by a “TCP-type” 

load allocation algorithm (62). 

Consider a particular situation, when (a) relaxation of the 

user level parameters (84) is much faster than relaxation of 

the allocated bandwidths (62), i.e., k k

~ >> and thus: 

 0 ~ ⎥ ≡

⎦

⎤ ⎢

⎣

⎡

∂

∂ ⎥ +

⎦

⎤ ⎢

⎣

⎡

∂

∂ ⎥

⎦

⎤ ⎢

⎣

⎡

∂

∂

s s s s

s

s X

s

s

Us U

γ μ γ γ

μ

μ

, (89) 

(b) each user s instantaneously adjusts and informs the 

IntPlane on its willingness to pay wr (82): 

 μ

μ ∂

∂ = s

s s

U

w (90) 

(c) the IntPlane instantaneously allocates each user s

payment (90) into payments wsr = ws

π sr for the 

bandwidths on specific routes Rs r ∈ . 

Consider rate of change of the social welfare (39) with 

time: 

 ∑ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

∂

∂

+

∂

∂ = s

s

s

s

s

W W W γ

γ

μ

μ & & & (91) 

Due to our assumptions 
 sr

s R r

r

sr

sr

r

sr

s

s

s d x

x

w d

x

U W

s

~ ∑ ∑ ~ ~ ∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − ∂

∂

∂

∂ = μ

μ

& (92) 

where 

 

sr

s

s

s

sr sr x

U

w x ~ ~

∂

∂

∂

∂ = μ

μ

 (93) 

Substituting (86) and (93) into (92) we obtain that the 

proposed adaptation algorithm increases the social welfare: 

 0 ~ ~

2

≥ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ − ∂

∂

∂

∂ = ∑ ∑∈

sr

s R r

r

sr

s

s

s d x

x

U W

s

μ

μ

& (94) 

and in a convex case maximizes the social welfare. 

Note that proportional fairness of this scheme is a result 

of property (88) of approximation (10). For more general 

trade-offs than (10) property (88) may not hold, and thus 

ensuring of the proportional fairness may require more 

complicated pricing structure than (81). 

6. EXAMPLES 

This Subsection A looks at benefits of multi-path routing. 

Subsection B considers a case of feasible routes without 

overlapping links. 

6.1 Benefits of Multi-path Routing 

In a case of a single-path routing, when user traffic must be 

routed on a single path, the optimal route and the 

corresponding price of a unit of the reliable throughput 

under approximation (10) are determined by solution to the 

following optimization problem 

 min ( ) ( ) * γ γ r r R r D D

s s ∈

= (95) 

where the price of a unit of the reliable throughput on a 

route r is 

 (γ ) (1 θ 2γ ) r r r D = d − (96) 

Figure 7 sketches the price of a unit of the reliable 

throughput on a fixed route (96), the price of optimal 

single-route implementation (95) (fat curve), and the price 

of optimal implementation using multipath routing (71) as 

functions of the reliability parameter γ . 

Figure 7 assumes a typical situation, when higher quality 

routes are more congested due to higher demand: 

1 2 3 dr < dr < dr , while 1 2 3 θ r > θ r > θ r . In a case of a 

single-path routing, when user reliability requirements for 

γ are low, the least congested, low quality route 1r should 

be used. As user reliability requirements increase, the user 

traffic should be carried on more congested, higher quality 

route 2r . As user reliability requirements keep increasing, 

the user traffic should be shifted to the most congested 

route 3r having the highest quality. Sufficiently high user 

reliability requirements cannot be met with a single-path 

routing. 

Fig. 7. Price of a unit of the reliable throughput 

Since, according to (95)-(96), maximal reliability 

exponent user s can achieve with a single path routing is 

 * 2 (1 2)max −

∈

= r r R s sγ θ ( , (97) 

it follows from (31) that this user can increase its reliability 

exponent with multi-path routing without overlapping links 

up to 

 min 1 2 2 > ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

Γ = ∈ ∈

−

∑ r r R r R

s r s s

θ θ (98) 

times. Gain (98) increases with increase in the routing 

diversity. Beneficial effect of multi-path routing on load 

balancing manifests itself in reduction of the average price 

of the unit of reliable throughput. Generally, this beneficial 

effect increases with increase in the user reliability 

requirements. Note that multi-path routing does not have 

beneficial effect for a user not concerned with reliability 

(γ = 0), since in this case optimal implementation is 

based on the minimum congestion cost routing. 

Fig. 8. Network topology 

D

2γ

1 Dr 2 Dr 3 Dr

1

1

− θ r1

2

− θ r1

3

− θ r * 2 ˆs γ

~* Ds

1 2

4

5

3
To get feeling of equal cost multi-path routing 

consider a network shown on Figure 8. The network has 

three feasible routes (1,2,3) r1 = , (1,4,2,3) r2 = , and 

(1,5,3) r3 = with the same congestion costs: 

d1 = d2 = d3 = d , and matrix 

 

⎟

⎟

⎟

⎠

⎞

⎜

⎜

⎜

⎝

⎛

Θ =

2

2 2

2 2

0 0

0

0

θ

χθ θ

θ χθ

 (99) 

where parameter χ ∈[0,1] characterizes overlapping 

between routes 1r and 2r . In this case the optimal load 

split (80) is as follows: 

χ

α α

+ = = 3

1

1 2 , χ

χ α

+

+ = 31

3 . 

If χ = 0 , i.e., equal cost routes 1r , 2r and 3r do not 

overlap, the optimal allocation splits load equally among 

these three routes: α1 = α 2 = α 3 = 1 3 . If χ = 1, i.e., 

matrix (99) describes a network with just two equal cost 

routes 1 2 r ≡ r ≡ r and 3r , the optimal loads allocation 

splits load equally among these two routes: 

α r = α 3 = 1 2 . 

6.2 Routes without Overlapping Links 

To illustrate our results, consider a case of K feasible routes 

without overlapping links: ( ) 2 2

2

2

1 , ,.., Θ = diag θ θ θ K , where 

without loss of generality we assume that θ1 ≥ θ 2 ≥ θ K , i.e., 

route 1r has lower quality than route j r if 1 ≤ i < j ≤ K . 

Fig. 9. Optimal route mixture, given route costs 

Figure 9 sketches the phase diagram, given the route costs dk , 

k = 1,2 and reliability exponent γ in a case of K = 2

feasible routes. This diagram shows three qualitatively 

different region with respect to the optimal route mixture 

( , ) α1 α 2 , where α k is the portion of the user traffic to be 

routed on path k r , given route relative congestion costs 

1 2 d d and user reliability requirements γ . In the region 

α1 = 1, α 2 = 0 entire user traffic should be sent over 

route 1r . In the region α1 = 0, α 2 = 1 entire user 

traffic should be sent over route 2r . In the region 

0 , 1 < α1 α 2 < user traffic should be split between routes 

1r and 2r . Also note that the part of Figure 9, where 

1 d1 d2 ≤ represents a typical situation when lower 

quality route is less congested.

It is instructive to analyze the optimal route mixture as 

user reliability requirements γ or relative route congestion 

cost 1 2 d d changes. Not reliability conscious user 

should use the minimum cost route. As user reliability 

requirements γ increase, multi-path routing becomes 

preferable until upper bound (28) is reached. Consider 

change in optimal connectivity as low quality route 1r

becomes more congested, i.e., as 1 2 d d increases from 

zero to infinity. In this case optimal connectivity for not 

reliability sensitive user should change from single route 1r

to multi-path routing 1U 2 r r , and eventually to single 

high quality, less congested route 2r . Connectivity for 

moderately reliability sensitive user should change from 

multi-path routing 1U 2 r r to single route 2r since low 

quality route 1r alone cannot provide required transmission 

reliability. Highly reliability sensitive user should be 

always connected over both routes: 1r and 2r , since 

neither route alone can guarantee required transmission 

reliability. Generalization to case of an arbitrary number of 

feasible routes without overlapping links is straightforward. 

Figures 10 sketches the phase diagram with respect to the 

optimal route mixture, given the average route capacities 

k c

~ , k = 1,..,K and service parameters (μ,γ ). Figure 

10 assumes a typical situation when lower quality routes 

have higher capacity: K c c

~ .. ~

1 > > . In the region 

( , : ,.., 0; .. 0} Ak = μ γ α1 α k > α k+1 = = α K = routes 

k r ,..,r 1 are utilized while routes k K r ,..,r +1 are not. As 

2γ

1

1

1

− θ 1

2

− θ * 2 ˆs γ

1

0

2

1

=

=

α

α

1 α1 = 0

0

2

1

>

>

α

α

1 2 d d

0

0

2

1

>

>

α

α

0 α 2 =
service requirements (μ,γ ) become more demanding, 

lower capacity, and thus more expensive, routes are 

utilized. Upper-right border of the region Ak also 

represents service requirements (μ,γ ) having the same 

congestion cost. In a case of penalty function (40), the link 

l cost is 2) ~ ~ ( ~ l l l l d = c c − y , where the average link 

load is l y

~ , and thus, the upper-right border of the region 

Ak represents service requirements (μ,γ ) resulting in 

the same average delay on route k+1 r : 1

~ = 1 k+ T c if 

k = 1,..,K −1, and T = ∞ if k = K . 

Fig. 10. Optimal route mixture, given route capacities. 

7. CONCLUSION 

This paper has proposed a framework for aggregate 

utility maximization in a distributed environment, where 

utilities are expressed in terms of application-level 

requirements. The framework assumes presence of the 

Intelligent Plane, which isolates users from the network 

layer. Numerous issues deserve further investigation, 

including the following: (a) Stability in presence of delays 

in feedback loops. (b) Property (88) ensures that pricing 

structure (81) results in proportionally fair resource 

allocation. Property (88) is a result of approximation (10) 

and may not hold in other situations, e.g., for a link failure 

model, when more sophisticated pricing schemes may be 

required to ensure proportional fairness [15]-[16]. (c) 

Possible generalization to a case when users are not only 

“buyers” but also “sellers” of the limited resources, such as 

in a case of a wireless multi-hop network, when 

intermediate nodes may expend their battery energy for 

relaying other users’ traffic [17]-[18]. 

8. ACKNOWLEDGMENTS 

Author appreciates illuminating comments by A. Nakassis. 

9. REFERENCES 

[1] S. Shenker, "Fundamental design issues for the future Internet," 

IEEE JSAC, 13 (1995) 1176-1188. 

[2] F.P. Kelly, “Charging and rate control for elastic traffic,” European 

Transactions on Telecommunications, Vol. 8, 1997, pp. 33-37. 

[3] F.P. Kelly, A.K. Maulloo, and D.H.K. Tan, “The rate control for 

communication networks: shadow prices, proportional fairness and 

stability,” Journal of the Operational Research Society, pp. 237-252, 

vol. 409, 1998. 

[4] D.D.. Clark, C. Partridge, J.C. Ramming, and J. Wroslawski, “A 

knowledge plane for the Internet,” ACM SIGCOMM, 2003. 

[5] S. H. Low, F. Paganini and J. C. Doyle, “Internet congestion 

control,” IEEE Control Systems Magazine, 22(1), Feb. 2002, 28-43. 

[6] V. Marbukh and R.E. Van Dyck, “On aggregate utility maximization 

by greedy ASs competing to provide Internet services,” FortySecond Annual Allerton Conference on Communication, Control, 

and Computing, Illinois, 2004. 

[7] A. Tsirigos and Z.J. Haas, “Analysis of multipath routing – part I: 

the effect on the packet delivery ratio,” IEEE Trans. On Wireless 

Communications, Vol. 3, No. 1, January 2004, pp. 138-146. 

[8] N.F. Maxemchuk, “Dispersity routing, Proc. IEEE ICC, San 

Francisco, CA, 1975. 

[9] A. Tsirigos and Z.J. Haas, “Analysis of multipath routing – part II: 

mitigation of the effects of frequently changing network topologies,” 

IEEE Trans. On Wireless Commun, Vol. 3, No. 2, 2004, 500-511. 

[10]J. MacKie-Mason, “What does economics have to do with 

survivability?” InfoSurv, June 1997. available at http://wwwpersonal.umich.edu/~jmm/presentations/darpa-econ-tutorial.pdf. 

[11] V. Marbukh, “Towards market approach to providing survivable 

services,” Conf. on Inf. Sciences and Syst. Princeton Univ., 2004. 

[12] F.P. Kelly, “Notes on effective bandwidth,” In "Stochastic Networks: 

Theory and Applications" (Editors F.P. Kelly, S. Zachary and I.B. 

Ziedins) Royal Statistical Society Lecture Notes Series, 4. Oxford 

University Press, 1996. 141-168. 

[13] S. Boyd and L. Vandenberge, Convex Optimization, Cambridge 

University Press, 2004. 

[14] D. Bertsekas and R. Gallger, Data Networks, Prentice-Hall, 1992. 

[15]C. Courcoubetis and R. Weber, Pricing Communication Networks, 

Wiley, 2003. 

[16] V. Marbukh, “A knowledge plane as a pricing mechanism for 

aggregate, user-centric utility maximization,” ACM Performance 

Evaluation Review, Volume 32, Issue 2, pp. 22-24, 2004 

[17]J. Crowcroft, R. Gibbens, F. Kelly and S. Ostring, “Modelling 

insentives for collaboration in mobile ad hoc networks,” 

Performance Evaluation, 57, pp. 427-439, 2004. 

[18] P. Marbach and Ying Qiu, " Cooperation in Wireless Ad Hoc 

Networks: A Market-Based Approach," available at 

http://www.cs.toronto.edu/~marbach/publ.html. 

[19] V. Marbukh, “On aggregate utility maximization based network 

management: challenges and possible approaches,” IEEE ICC 2004

1 2

~ ~ c + c

2γ

μ

K c c

~ .. ~

1 + +

1 1

~ .. ~ + + K − c c

1

~c

A1

AK

A2