1 

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. 

Index Terms— Distributed system, resource allocation, elastic 

user, pricing, intelligent plane. 

I. INTRODUCTION

ince 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 

Author is with the National Institute of Standards and Technology, 100 

Bureau Drive, Stop 8920, Gaithersburg, MD 20899-8920 (phone: 301-975-

2235; fax: 301-590-0932; e-mail: marbukh@ nist.gov). 

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. 

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. 

Intelligent Plane as a Mapping Mechanism for 

User Level Performance Optimization: A Case 

of Reliable Services over Unreliable Network 

V. Marbukh, Senior Member, IEEE

S

User s

Congestion 

pricing of the 

network 

resources

Demand or

willingness to pay 

for network

resources

User 1 User S

Network
2 

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 TCP-type 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 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. 

II. 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. 

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
3 

A. 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 origindestination 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) 

B. Bandwidth Sharing and 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ˆ φ . 

μ s

s x

s x

~

∆s

time
4 

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]. 

C. Approximation for the 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 

 ∑∈

= 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 

Code Decode

Networ

Data Data 1r x

2r x

3r x μ s s x s x

~

min( , ) s s x μ
5 

 

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) 

III. NETWORK MANAGEMENT OBJECTIVE

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. 

A. 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 
6 

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

B. 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) 

IV. USERS RESPONDING TO BANDWIDTH PRICING

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) 

0

us

μ

0

s v

γ

1
7 

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. 

A. Uses Adjusting Bandwidth Requirements 

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) 
8 

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). 

B. Uses Adjusting Willingness to Pay for Bandwidth 

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 willingness-to-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). 

V. INTELLIGENT PLANE: QOS PRICING AND IMPLEMENTATION 

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. 

A. Users Adjusting QoS Requirements 

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) 
9 

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: 

∑ ∑∑ ∑ 















− − ls R r l∈r⊂

sr

s s

s

l

s

s s s

s

U f 1 ˆ :( , ) α

γ γ

μ μ γ (69) 

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 

 d d d M

~ ~ ~ 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 
10 

 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). 

B. Users Adjusting 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-
11 

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

of the proportional fairness may require more complicated 

pricing structure than (81). 

VI. EXAMPLES AND IMPLICATIONS

Subsection A looks at benefits of multi-path routing. 

Subsection B considers a case of feasible routes without 

overlapping links. 

A. 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 γ . 

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

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. 

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. 

To get feeling of equal cost multi-path routing consider a 

network shown on Figure 8. 

Fig. 8. Network topology 

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 . 

D

2γ

1 Dr 2 Dr 3 Dr

1

1

− θ r1

2

− θ r1

3

− θ r * 2 ˆs γ

~* Ds

1 2

4

5

3
12 

B. A Case of 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 . 

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. 

Fig. 9. Optimal route mixture, given route costs 

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 . Note that after some 

enhancements this model can be used to describe a situation of 

a soft handoff. 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 (μ,γ ). 

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

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 

service requirements (μ,γ ) become more demanding, lower 

capacity, and thus more expensive, routes are utilized. Upperright 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 . 

VII. 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) 

Implications of possibility that in non-steady regime some 

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 = 1 2

~ ~ c + c

2γ

μ

K c c

~ .. ~

1 + +

1 1

~ .. ~ + + K − c c

1

~c

A1

AK

A2
13 

π sr in (87) may be negative: π sr < 0, meaning that certain 

routes receive negative “payments” for offering their 

bandwidth. This situation may cause difficulties, especially if 

different routes represent different autonomous systems and 

payments are associated with real funds. Even if payments do 

not represent real funds and willingness to pay is simply a 

protocol parameter controlled by the user, an interesting 

question is whether a user can benefit by keeping the system 

from reaching an equilibrium. (c) 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]. (d) 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]. 

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, Karlsruhe, Germany, 

2003. 

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

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

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

greedy ASs competing to provide Internet services,” Forty-Second 

Annual Allerton Conference on Communication, Control, and 

Computing, Monticello, 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 Communications, Vol. 3, No. 2, March 2004, 

pp. 500-511. 

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

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

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

services,” Proc. Conf. on Info. Sciences and Systems, Princeton Univ., 

Mar. 17-19, 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 International 

Communications Conference (ICC 2004), Paris, France, 2004.