A Model of Joint Congestion Control and Routing Through

Random Assignment of Paths

Fern Y. HUNT

Information Technology Laboratory

National Institute of Standards and Technology

Gaithersburg, Maryland 20899, USA

Vladimir MARBUKH

Information Technology Laboratory

National Institute of Standards and Technology

Gaithersburg, Maryland 20899, USA

February 16, 2010

Abstract

We investigate the trade-o between utility and path diversity in a model of congestion control where

there can be multiple routes between two locations in a network. The model contains a random route

allocation scheme for each source s where the degree of randomness and therefore path diversity is controlled by hs, the entropy of the route distribution. After deriving the model from a network utility

maximization problem we analyze it in detail for two sample topologies. We conclude that, starting

from an allocation with maximum robustness and path diversity, one can always increase the utility

by decreasing hs. However it can only decrease until a critical value of the entropy is reached. The

value depends on the topology and link capacities of the network and can be explicity computed for our

examples.

Keywords:TCP/IP protocols, multipath routing,discrete dynamics, Morse theory

1 INTRODUCTION

In recent years, network protocols have been interpreted as algorithms that solve a convex optimization problem. In

this set-up overall congestion control is formulated as a network utility maximization problem (NUM) that is solved

in a distributed fashion by the various network layers. The network topology and the capacity of its links introduces

constraints on the optimal solution. Then algorithms solve the problem by computing and modifying the primal and

dual variables based on ecient communication between users, link and router layers of the network. Since the work

of Kelly et al [7] congestion control protocols have been seen as regulating user network transmission rates so that

the objective function i.e., the aggregate utility, is maximized subject to capacity constraints ([8], [3]). The utility

function incorporates ecient utilization and fair allocation of resources among users. Signicantly, such functions

have been identied for existing protocols such as TCP and BGP (Border Gateway Protocols) through a process of

"reverse engineering", thus opening up opportunities for analysis and improvement of existing protocols as well as

the development of new ones.

The paradigm just described has been extended to the problem of characterizing protocols that jointly control

congestion and routing ([12],[3], [4], [5],[6]). Aside from the obvious improvement in the utilization of network

resources that could be gained by such an approach, there are obvious benets in this time of cybersecurity concerns

about adequate network robustness against route disruptions. However implicit in such a protocol is a tradeo

between robustness through path diversity on the one hand and network performance or utility on the other. Single

1
path routing based on e.g. the OSPF (Open Shortest Path First) protocol can lead to route apping instability and

reduced utility. However splitting trac equally across all paths regardless of cost would also imply reduced utility.

The best tradeo if it exists would have to navigate between these extremes. Thus the design of stable, implementable

algorithms that achieve maximum aggregate utility remains a challenge.

Our purpose is to propose a generalized NUM optimization problem for joint congestion control and routing

where we can examine the behavior of the time averaged utility as a function of entropy, a model parameter that

can be interpreted as a measure of path diversity. This paper is not presenting an algorithm to be implemented on

a real network but is rather, a theoretical study of issues that must be addressed by any algorithm that is based on

the NUM problem we discuss. Our model contains a routing scheme based on random allocation where the degree

of randomness is controlled. The randomness of any route or path allocation for a class of network users s, can be

measured in terms of the entropy hs of the probability distribution dened by the allocation.

Treating hs as a parameter, we nd that as we increase hs from 0, the model equations fail to converge to an

equilibrium until the entropy reaches a critical value (see Section 5.1 for TwoLinks and Section 6.1 for Diamond).

Stable equilibria exist for values of hs greater or equal to the critical value and we show that the corresponding

equilibrium pair (x

∗

s, β∗s ) are solutions of the optimization problem.

We also calculate the time averaged aggregate utility for a range of values hs for each topology (see Figure 8,

Figure 9). These graphs show how the utility decreases as the entropy increases and they illustrate the fact that one

can always increase the utility for a route allocation that has entropy greater than the critical value by changing the

allocation so that the entropy decreases. This automatically decreases the mean route cost. A protocol based on

the model we presented does not allow one to decrease the entropy below the critical value. We conjecture that the

behavior of the model for entropy values less than the critical value corresponds to the unstable behavior seen in the

single path TCP/IP protocols as discussed in reference [12].

We now turn to a description of the organization of the paper. The NUM optimization problem is presented in

the next section and is followed by a description of the model and the notation used in Section 3. The model is an

algorithm for solving the NUM optimization problem and is derived following the work of [8], [12] in Section 4. Then

the model is specialized to the TwoLinks topology (see (29)) in Section 5, and there follows a detailed description of

the model behavior in 5.1-5.3. Readers who want to skip the details and see the results and conclusions can go to the

beginning of sections 5 and 6. The model equations for the Diamond topology (equations (38)-(42)) can be found in

Section 6. A summary of the model behavior for this topology can be found at the beginning while details can be

found in the subsections 6.1-6.3. A discussion of how the aggregate utility varies as a function of the parameter hs

for these two topologies can be found in Section 7. The conclusion can be found in Section 8. Finally the last section,

Section 9 is an appendix, containing proofs of some results needed in the detailed subsections of 5 and 6.

2 OPTIMIZATION PROBLEM

Consider a planar network to be a graph with nodes representing physical nodes in the network and edges representing

links. The link capacities are dened by the vector c = (c1, c2, · · · , cL). A user who requires bandwidth to transmit

from one node to another in the network (or a single TCP session between those two nodes) is indexed by s, the

index of the source-destination pair. For each s , the utility function is a twice dierentiable strictly concave function

Us : [ms, Ms] → R. Here ms and Ms are lower and upper bounds respectively on the bandwidth rate xs. Us(xs)

measures the degree of user satisfaction, network fairness and eciency for the part of the network dened by s. Users

in a source-destination class s are assigned a path by edge routers using a probability distribution with a minimum

degree of randomization as specied by hs. The distribution is constrained so that the trac on any link does not

exceed the link capacity.

The optimization problem that our protocol seeks to solve is:

max

β≥0,x∈X x≥0

X

s

Us(xs) (1)

X

s

X

r∈Rs(l)

βsrxs ≤ cl (2)

∀s

X

r∈Rs

βsr = 1, βsr ≥ 0 (3)

−

X

r∈Rs

βsr log βsr ≥ hs (4)

x = {xs : s = 1, 2, · · · S} is the vector of source rates with each xs ∈ [ms, Ms] where ms ≥ 0. In this paper we will

take ms = 0 for all s and Us(xs) = ws(1 − αs)x

1−αs

s with αs = 2. The form for U is commonly used in the literature

[3]. The elements β = {βsr} comprise a matrix whose rows are the route probability distributions for source s. The

2
constraints (2) require that all routes r in Rs(l), the set of routes of source s that use link l, be assigned bandwidth

rates βsrxs so that the total link load does not exceed the capacity cl. Finally if Rs is the set of all paths joining the

source-destination pair s, then (3) is the usual requirement for probability distributions and (4) places an lower bound

on the degree of randomness for the distribution {βsr} for source s. Small values of hs indicate that the problem is

closer to the single path case and as hs increases we are closer to the equiprobable case- a version of the multipath

problem. Following the approach of [8] we developed an algorithm based on a gradient projection iteration method

for the dual optimization problem. We will discuss the convergence of this algorithm and its stability as a function of

hs for two sample topologies. As in [8] and [12], the dual variables are link costs changing in response to congestion.

The route allocation distributions follow dynamics that minimize the average route cost.

In [9] where the idea of random route allocation was rst proposed, the authors introduced an adaptive algorithm

involving non-constant values of hs. Through simulations they demonstrated the trade-o between stability and

utility. They found that the maximum utility occurs near the boundary between stability and instability.

3 DESCRIPTION OF MODEL

To describe the results of this paper, the model equations are presented next. They are based on a gradient projection

algorithm for solving the dual form of a NUM problem and they are derived in Section 4. The utility funcion

Us : [ms, Ms] → R where 0 < ms < Ms, is a strictly concave, twice continuously dierentiable function.

We will as usual represent a computer network as a planar graph with nodes representing locations in the network.

In the literature, the total amount of bandwidth to send information from one part of the network to another is

controlled by an agent called a source. There are several routes a source can take to its destination and we assume

each route is dened by a set of uni-directional links indexed by l = 1, · · ·L. These links are represented in the graph

as weighted edges, where an edge weight is the link capacity. Sources are indexed by s, and trac is assigned to route

r ∈ R(s) with probability βrs where R(s) is the set of all routes used by source s. If p

(k)

l

is the link cost at time k

and cl is the capacity of the lth link then the equations of the model are

p

(k+1)

l =



p

(k)

l − h







cl −

X

s

xs(k)

X

r∈Rs(l)

β

(k)

sr











+

l = 1, · · ·L (5)

β

(k)

sr = exp(−γs(k)dr(k))/Zs(k) (6)

where dr(k) = P

l∈r

p

(k)

l

is the cost of route r at time k, h is a step size , [a]

+ = a if a > 0 and is 0 otherwise.

Zs(k) = P

r∈R(s)

exp(−γ

(k)

s dr(k)) is the normalization factor for the route distribution and, the variable γ

(k)

s is the

solution of the implicit equation,

γ

(k)

s Ds(k) + log(Zs(k)) = hs, Ds(k) = X

r∈R(s)

β

(k)

sr dr(k) (7)

The model equations are completed by a relation between the bandwidth rate xs(k) and Ds(k), the mean route cost

at time k for positive constants w and M.

xs(k) = min 

w

Ds(k)

1/2

, M!(8)

Equations (6) and (7) force the route distribution β

(k)

sr to be the unique distribution of entropy hs with the smallest

mean route cost at each time step k. Recall that for any probability distribution βs = {βsr}r∈R(s) the entropy of the

distribution is

H(βs) = −





X

r∈R(s)

βsr log βsr



 . (9)

Thus the condition on the route distributions is H(βs) = hs. This constant entropy requirement will constrain the

set of values {pl | l = 1 · · ·L} for which a bounded γ

(k)

s exists. The precise set depends on the network topology and

capacity of the links. In this paper we present a detailed discussion of two very simple sample networks where these

regions can be determined.

3
4 DERIVATION OF THE MODEL

The problem (1)-(4) is not convex in (x, β) but through an invertible change a variables (x, β) 7→ (x, y) it can be

transformed to one. The new problem is:

max

x,y

X

s

Us(xs) (10)

X

s

X

r∈Rs(l)

ysr ≤ cl (11)

xs =

X

r∈Rs

ysr, ysr ≥ 0 (12)

−

X

r∈Rs

ysr

xs

log ysr

xs

≥ hs (13)

This is a convex program because the functions in (10)-(13) are clearly concave. If we assume the conditions

X

s

0

ms

0 < cl

hold for each l, where the summation is over all source-destination pairs s

0

that use link l, and note that a β = {βsr :

r ∈ Rs, s = 1 · · · S} can always be found so that ysr = xs ∗ βsr and

−

X

r∈Rs

βsr log(βsr) ≥ hs

then there is a Slater point([11]) and the Slater constraint qualication is satised. We note here that xs ∈ [ms, Ms]

can be chosen independently of β. Thus (10)-(13) is superconsistent and Lagrange multipliers exist. The Lagrangian

for the problem is:

L(x, yλ, p) = X

s

[Us(xs) −

X

r∈Rs

 X

l∈r

pl

!

ysr − λ

1

s

 X

r∈Rs

ysr log( ysr

xs

) + hsxs

!

(14)

−λ

2

s

 

xs −

X

r∈Rs

ysr!+

XNL

l=1

plcl

where {pl, l = 1 · · · NL} are the Lagrange multipliers for (11) and λ = [λ

1

s, λ2s : s = 1, · · · S] are Lagrange multipliers

for constraints (13) and (12). To obtain solutions x, y we consider the problem;

max

x,y

L(x, y, λ, p) = max

x

max

y

L(x, y, λ, p)

where maximization is rst performed in y with x and p held xed. The problem maxy L(x, y, λ, p) is equivalent to

the constrained problem

max

y

X

s

Us(xs) −

X

r∈Rs

(

X

l∈r

pl)ysr (15)

xs =

X

r∈Rs

ysr, ysr ≥ 0

−

X

r∈Rs

ysr

xs

log( ysr

xs

) ≥ hs

Problem (15) has a Slater point so it too is superconsistent. A solution y

∗

to (15) exists if and only if there is a λ

∗

that satises the Karush-Kuhn-Tucker conditions ([11] p.182,183). Reintroducing βsr =

ysr

xs

where βsr is independent

of xs, we obtain the following form of the optimal solution of (15) for each xed xs and p.

βsr =

exp(−γ ∗ dr)

Zs

(16)

where

Zs =

X

r∈Rs

exp(−γ ∗ dr), dr =

X

l∈r

pl

4
and γ =

1

λ2

s

is the solution of the implicit equation,

γ ∗ Ds + log Zs(γ) = hs , Ds =

X

r∈Rs

βsrdr (17)

Recognizing that (15) is equivalent to the problem of minimizing P

r∈Rs

ysrdr = xsDs subject to the constraints, we

see that the optimal solution can be obtained by setting γ equal to the unique positive root of (17). Indeed there

are in general two roots of this equation when hs < log |Rs| and the positive root provides the smallest value of Ds.

Given γ > 0, call any βsr subject to (16) and (17), β

∗

sr. Then we have y

∗

sr = xsβ

∗

sr. The {y

∗

sr : r = 1, · · · Rs} are

unique since for each s, (17) has a unique positive solution. Set

L(x, p) = max

y

L(x, y, λ, p) = L(x, y

∗

(x, p), λ∗(x, p), p)

where y

∗

(x, p) and λ

∗

(x, p) are the optimal solution and Lagrange multipliers of (15) for xed x and p. Using the

KKT conditions L can be written as,

L(x, p) = X

s

[Us(xs) − xs

X

r∈Rs

(

X

l∈r

pl)β

∗

sr] +XNL

l=1

plcl (18)

L is strictly concave on the product interval X =

Q

s

[ms, Ms] and therefore maxx L(x, p) exists for a unique x.

Moreover L is convex in p. To see this note that

− Λs(p) = −

X

r∈Rs

(

X

l∈r

pl)β

∗

sr ≥ − X

r∈Rs

(

X

l∈r

pl)βr (19)

and is the supremum over all vectors β; β :

P

r∈Rs

βr = 1, −

P

r∈Rs

βr log βr ≥ hs. Thus L(x, p) is the supremum of

set of convex functions over an innite (convex) set (p. 81 Boyd and Vandenberghe). Applying the same reasoning

to L we can conclude that Q(p) = maxx L(x, p) = maxx maxy L(x, y, λ, p) is convex in p. The remainder of this

derivation follows the work of [8] and [12]. First the dual problem for p is formulated as:

min

p:pl≥0

Q(p) (20)

If {β

∗

sr}s,r is dierentiable in p and λ, then Danskin's theorem [1] applied to L implies the dierentiability of Q. Indeed

the unique maximizing x ̄ and y = xβˆ∗ are dierentiable in p and λ. At x ̄, either x ̄s(p) = Ms or U

0

s(  ̄xs)(p)) = Λs(p). If

x ̄s(p) < Ms, then a condition introduced in [8], U

00 (xs) ≥ δs > 0 for all xs ∈ (0, Ms], together with the dierentiability

of Λs with respect to p and λ, imply that x ̄s is dierentiable(see Appendix) and thus L( ̄x, y∗, λ, p) is dierentiable.

We conjecture that Λs is dierentiable at p if p lies in a convex subset of RL. The exact nature of the subset depends

on the existence of a nite positive root of (17). We have determined the region for sample problems discussed in

this paper. In general however we do not expect Q to be everywhere dierentiable. These considerations lead to the

following subgradient algorithm for solving (20).

p

k+1 = [pk − hgk

]

+

(21)

If xs(p) < Ms, for all s, where g is a subgradient of Q. When it is dierentiable g

k = 5Q(pk

). Our interest lies in

understanding the dynamics of the latter equation when this condition is satised at least initially and the boundary

of X can only be approached from the interior thus for the rest of our discussion we assume that for each k:

ASSUMPTION For all s , x ̄s(p

k

) < Ms.

Under this assumption, (21) can be written as

p

k+1

l =



p

k

l − h







cl −

X

s

x

k

s

X

r∈Rs(l)

β

k

sr(

X

l

0 ∈r

p

k

l

0 )











+

l = 1 · · · NL (22)

Equations (22) is supplemented by the relations coming from the optimality conditions.

β

k

sr =

exp −γ

k

s (

P

l∈r

pl)



Z(γ

k

s )

(23)

x

k

s = min(

w

E[d]

 1

α

M) , E[d] = X

r∈Rs

β

k

sr(

X

l

0 ∈r

p

k

l

0 ) (24)

where γ

k

s is the solution of (17) using β

k

sr , and Z(γ

k

s ) is dened analogously to Z(s). Equation (17) eectively insures

that at each time step k the route distribution nβ

(k)

sr : r ∈ Rs

o

has entropy hs for every s.

5
5 TWO LINKS TOPOLOGY

A network consisting of a single source-destination pair of nodes connected by two links is depicted in Figure 1. In

this section we describe the dynamics of equations (22) particular to this case as seen in equation (29). We nd the

values of the entropy hs where the iterations converge and these can be used to express the solution of the original

optimization problem. As hs is varied it will be convenient from a conceptual as well as mathematical point of view

to express the variation in entropy in terms of the route allocation distribution.

In Section 5.1, we discuss the existence of stable equilibria for (29) at an intrinsic (critical) entropy value with

route probabilities,

β

∗

1 =

c1

c1 + c2

, β∗

2 =

c2

c1 + c2

(25)

where c1 and c2 are the link capacities and without loss of generality we assume c1 > c2. The corresponding critical

value of the entropy is therefore

hT (c) = −



c1

c1 + c2

log c1

c1 + c2

+

c2

c1 + c2

log c2

c1 + c2



(26)

(27)

Each initial point in a region H in the p1, p2 plane, converges along a straight line orbit to a point on the line of

constant mean cost x ̄∗ (see the line L1 Figure 2). Although there are innitely many such points in the plane there

is a unique equilibrium bandwidth rate xs∗ =

 w

x ̄∗

1/2

. These equilibria are neutrally stable.

There is a corresponding equilibrium route allocation as well. In the latter part of our discussion here and Theorem

9.1 in the Appendix we show that there are just two probability distributions with a given entropy hs < log 2. It is

shown that within the quadrant sector {p = (p1, p2,) : p1 < p2 }, the route probabilities β

(k)

1 > β(k)2 are constant

and equal to the values in (25) for k ≥ 1. Thus the optimal route probabilities are reached in a single step although

of course the solution of the implicit equation varies and depends on p. The reverse inequality holds in the other

quadrant sector. The particular choice of solution depends on the sector the intiial values of p are in. The proof

that the equilibrium values (xs∗, β∗) are solutions of the optimization problem for h small enough is omitted here

but follows along the same lines as the proof of Theorem 1 in reference [8] and page 214 of [1], because orbits of

(29) remain in a single sector so the route probabilities are constants. Therefore the equations take the same form as

those discussed in [8]. We note that it is also at this point that the lower bound on U

00

is needed.

If hs 6= hT (c), then the route probabilities in analogy with equation (25) are:

β

(hs)

1 =

c1 + μc2

(1 + μ)c2 + c1

β

(hs)

2 =

c2

(1 + μ)c2 + c1

(28)

where μ 6= 0. If μ = 0 then hs = hT (c), while μ < 0 implies that hs > hT (c). The dynamics of the iterations

for these values are discussed in Section 5.2. There it is proved, that if initial points start in H, iterates converge

to a asymptotically stable equilibrium point on the p2 axis. Figure 3 shows some of these orbits. This equilibrium

corresponds to a solution of the optimization problem but here the utility, i.e. U(x

∗

s) is smaller than the value obtained

at hT (c). The discussion of TwoLinks ends in Section 5.3 where we treat the case μ > 0. Here hs < hT (c). The

algorithm does not converge but instead orbits approach the line p1 = p2 and the solution of the implicit equation

becomes unbounded.

We now introduce the equations for the TwoLink topology and establish some preliminary facts needed for their

analysis in the later subsections. We are interested in identifying sucient conditions for the existence of equilibria

for our algorithm in the region where the dual function Q is dierentiable. In this topology note that a nite

solution of (17) fails to exist if hs < log 2 but p1 = p2. Therefore we will restrict our investigation of (22) to the set

{p = hp1 , p2i : p1 < p2}. We will denote by xs the bandwidth rate with the single source in this network. In this

setting equations (22) become:

p

k+1

1 =

h

p

k

1 − h

n

c1 − β

k

1 xs(k)

oi+

(29)

p

k+1

2 =

h

p

k

2 − h

n

c2 − β

k

2 xs(k)

oi+

Here β

(k)

1

is the probability of being assigned to route 1 at the kth step and β

(k)

2 = 1 − β

(k)

1

. Now the entropy of a

two point distribution is dened as

H(β) = − (β log(β) + (1 − β) log(1 − β))

6
Figure 1:

The equation H(β) = hs, for some xed hs < log 2, is satised by exactly two distributions βˆ = {β

(hs)

, 1 − β

(hs)

} or

{1 − β

(hs)

, β(hs)}. Since the left hand side of (17) can be interpreted as H(

ˆβk), where βˆ(k) = {β

(k)

1

, β(k)

2 }, this means

there are only two possible values of β

(k)

1

(β

(k)

2

respectively).The optimality conditions require that the positive root

be selected, so we conclude that β

(k)

1 ≡ β

(hs) where β(hs) > (1 − β(hs)

) if p

(0)

1 < p(0)2 and the reverse inequality when

p

(0)

1 > p(0)

2

(see Theorem 9.1 in the Appendix).

In what follows the sets Wi = {pi|pi − h{ci − βixs} > 0} will be mentioned frequently.

5.1 Route Distribution dened by Link Capacities

Given capacities c1 > c2 where c1 and c2 are the capacities of link 1 and link 2 respectively suppose,

c1

c2

=

β

(hs)

1

β

(hs)

2

= λ > 1. (30)

Here β

(hs)

1 and β

(hs)

2

, the proportion of trac allocated to links 1 and 2 respectively dene a probability distribution

with entropy hs = hT (c) given by (27). The entropy and thus the possible path allocation probabilities are determined

by the capacities of the links and are therefore intrinsic to the network. The ratio in (30) is greater than 1 so we

make the choice of assigning the smaller initial price to link 1, i.e. p

(0)

1 < p(0)

2

. We also make the realistic assumption

that M > c1

β

(hs)

1

. There exists a family of steady states (equilibrium values) (xs∗, p∗

1, p∗2, β(hs)

1

, β(hs)

2

). Here xs∗ =

c2

β2

is the unique equilibrium source rate, where p

∗

i are the link costs for i = 1, 2 such that β

(hs)

1 p

∗

1 + β

(hs)

2 p

∗

2 = x ̄∗, where

xs∗ =

 w

x ̄∗

1/2

. The equilibrium values of pi are not unique as we will see. To simplify notation in what follows we

write β

(hs)

i = βi i = 1, 2.

The dynamics of (29) are most conveniently described by dividing the (p1, p2) plane into 3 regions. Let L0 be

the line perpendicular to the line L1 : x ̄ = x ̄∗ at the point (0, p ̃2). It is clear that p ̃2 =

x ̄∗

β2

. Similarly let L2 be the

line perpendicular to L1 at the point of intersection of the lines L1 and {p : p1 = p2}. We will begin with the region

bounded above by L0, and below by L2 and on the left by the p2 axis. Denoting this region by R we assume that

initial value p

0 = (p

(0)

1

, p

(0)

2

) is in H = R ∩ W1 ∩ W2 ∩ {p : p2 > p1}. As long as p

(k)

2 > p(k)1

, β

(k)

i = βi i = 1, 2 (see the

discussion at the end of the introductory part Section 5). Equations (29) and (30) imply that p

(k)

2 − p

(k)

1

increases so

this inequality holds while p

(k)

i ∈ Wi. The orbit of p proceeds in a direction parallel to L0, i.e. perpendicular to L1.

To see this let, ∆p equal the vector < h(β1xs(k)−c1), h(β2xs(k)−c2) >. Then the dot product with < −β2, β1 >

is ∆p· < − β2, β1 >= 0. If p1 leaves W1, (p2 cannot leave W2 because p2 > β2x ̄

∗

), then the orbit will move to the

p2 axis and p

(k)

2 → p ̃2 as k → ∞. If p1 remains in W1 we will show that p

(k) will exponentially converge to a point

on the line L1. From (29) we derive the following equation for the evolution of x ̄ for p

(k)

i ∈ Wi i = 1, 2 k ≥ 1.

x ̄

k+1 = T( ̄x(k)

) =  ̄x

k + hβ(hs)

2

(1 + λ

2

)



xs(k)β

(hs)

2 − c2



(31)

First suppose that xs(0) < xs∗, (x ̄

0 > x ̄∗

). Equation (31) shows that x ̄ decreases as long as xs(k) ≤ xs∗and is xed

when xs(k) = xs∗(x ̄

(k) =  ̄x∗

). Moreover, an application of the the Mean Value theorem shows the the map T is a

7
uniform contraction in within the interval, [ ̄x

∗

, x ̄

(k)

] and the approach to x ̄

∗

is exponential. In fact we have,

x ̄

(k+1) − x ̄∗ = ( ̄x(k) − x ̄∗

) −

hβ2

2

2w

(

w

ξ

)

3/2

( ̄x

(k) − x ̄∗

) (32)

where ξ ∈ [ ̄x

∗

, x ̄

(k)

]. Thus p

(k)

converges to a point pˆ on L1 that is the intersection of L1, with the line perpendicular

to it and passing through through p

(0). It is clear then, that the equilibrium values are not unique. However the

equilibrium value of the bandwidth xs∗and therefore the equilibrium mean cost x ̄

∗

is unique. If xs(0) > xs∗, then

x ̄ increases and eventually reaches an interval where T is a contraction i.e. (32) holds with ξ ∈ [ ̄x

(k)

, x ̄

∗

]. Since

p

(0) ∈ W1 ∩ W2 the orbit remains in this set because p

(k)

1 and p

(k)

2 are both increasing while c2 − β2 ∗ xs(k) decreases

with k. As in the previous case, p

(k)

exponentially approaches a point on L1. It is not hard to show by local stability

analysis that the limiting point is neutrally stable along the L1 direction (with eigenvalue 1) and is stable along the

L0 direction, with eigenvalue less than 1 in absolute value.

Let us now consider the cases where p

(0) ∈ W1 ∩ W2 is located outside of H. If the initial point is above (and to

the left of) L0, then the orbit of p lies along a straight line perpendicular to L1 and approaches a point on the p2

axis. At some time k, p

(k)

1 ∈/ W1, then p

(k+1)

1 = 0. Since xs(m) ≤ xs∗

, for m ≥ k, then p

(m)

1 = 0 for m ≥ k + 1 and the

orbit is conned to the p2 axis. p

(m)

2 → p ̃2 as m → ∞. If p

(0) is located to the right of the line L2 but still satises,

p

(0)

2 > p(0)

1

, then the orbit moves in a direction perpendicular to L1. As in previous cases however, it will reach the

p1 = p2 before it reaches L1 so that the orbit fails to converge to an equilibrium.

Figure 2: (p1, p2) plane when hs = hT (c)

5.2 Route Distribution with Less Weight on the Larger Link (increased hs)

We now consider the choice of parameters

c1

c2

= λ , β

hs

1

β

hs

2

= λ + μ.

The parameter μ expresses the degree to which the route allocation distribution's entropy diers from what we can

call an intrinsic entropy dened in (27). In this instance λ is xed by the intrinsic capacities of the links but the

controller can vary trac allocation by varying μ. The rst case we consider, μ < 0 , decreases the portion of trac

assigned to link 1. As β1 decreases while maintaining the inequality β1 > β2, we have hs > hT (c) and the entropy

increases. It approaches the distribution that assigns 1/2 to each i.e. hs = log 2. We assume that p

(0)

i ∈ Wi, i = 1, 2.

If p

(k)

i ∈ Wi 1 ≤ k ≤ K i = 1, 2 ,where K, is an arbitrary but xed positive integer, the right hand sides of of the

two equations in (29) can be used to show the following:

Lemma 5.1 If p

(0)

1 < p(0)2 and xs(0) ∈

h

c2

βhs

2

,

c1

βhs

1

i

, then p

(k)

1 < p(k)2 and xs(k) ∈

h

c2

βhs

2

,

c1

βhs

1

i

for 1 ≤ k ≤ K.

8
Proof: We use mathematical induction on 0 ≤ l ≤ K − 1. The induction hypothesis is that p

(l)

1 < p(l)2 and

xs(l) ∈

h

c2

βhs

2

,

c1

βhs

1

i

with β

(l)

i = β

(hs)

i

, i = 1, 2. Equation (29) then implies that p

(l+1)

1 < p(l+1)2

. Using the argument

in the appendix, we then see that β

(l+1)

i = β

(hs)

i

, i = 1, 2. To show that xs(l+1) ∈

h

c2

βhs

2

,

c1

βhs

1

i

we rewrite (29),

simplifying the notation for βi by dropping the hs superscript. Note that the right hand sides of (29) can be

rewritten as [p

(l)

1 − h{c1 − β

(l)

1 xs∗ + β

(l)

1

(xs∗ − xs(l))}]

+ and [p

(l)

2 − h{c2 − β

(l)

2 xs∗ + β

(l)

2

(xs∗ − xs(l))}]

+ respectively.

Here xs∗ = θ

c2

β2

where θ =

1+λ(λ+μ)

1+(λ+μ)

2 . Therefore after some algebra the equations for p

(l+1) are:

p

(l+1)

1 = p

(l)

1 +

hμc2

1 + (λ + μ)

2)

+ hβ(l)

1

(xs

(l) − xs∗

) (33)

p

(l+1)

2 = p

(l)

2 −

hμ(λ + μ)c2

1 + (λ + μ)

2 + hβ(l)

2

(xs

(l) − xs∗

)

The fact that βi = β

(l)

i = β

(l+1)

i

i = 1, 2 is then used to derive an equation for the mean value x ̄

(l+1)

,

x ̄

(l+1) =

h

x ̄

(l) + h(β2

1 + β

2

2 )(xs

(l) − xs∗

)

i

(34)

If xs(l) ≥ xs∗, then (34) shows that x ̄

(l+1) ≥ x ̄(l)

and thus xs(l+1) ≤ xs(l). It is clear then that xs(l+1) ≤

c1

β1

. To see

that xs(l+1) ≥

c2

β2

for h small enough, suppose the contrary, xs(l+1) <

c2

β2

. We would then have

xs

(l) − xs(l+1) > xs(l) −

c2

β2

≥ xs

∗ −

c2

β2

.

We compute the last dierence as xs∗ −

c2

β2

=

−μ(λ+μ)

1+(λ+μ)

2

c2

β2

. However the dierentiability and in particular the

continuity of U

0

shows that xs(l+1) − xs(l)can be made much smaller than this (it is O(h) ) for h small enough).

Indeed we have

|xs

(l+1) − xs(l)

| ≤ C max

x ̄∗

1≤x≤x ̄∗

2

 w

4x3

1/2

h

where x ̄∗

i =



βiw

ci

1/2

for i = 1, 2 and C = maxi=1,2 |

ci

βi

− xs∗|. Thus the contradiction. A similar argument can be

made when xsl < xs∗. ✷

If p

(k)

1

remains in W1 for a suciently long interval then xs(k) will be close enough to xs∗so the (xs(k) − xs∗)

terms in the equations of (33) can be neglected. Note also that in this situation p

(k)

2

is always in W2. We then have

p

(k)

1 decreasing until it leaves W1 and thereafter p

(k)

1 = 0. Meanwhile p

(k)

2

increases as the orbit moves along the p2

axis until p2 → p

∗

2, where β2p

∗

2 = x ̄∗

2

. This conclusion still holds true if p

(k)

1

leaves W1 at some time we can assume

to be k = K + 1. Using the fact that p

(l)

i ∈ Wi 0 ≤ l ≤ K we can show that xs(k) ∈

h

c2

β2

,

c1

β1

i

. This means that the

orbit lands on the p2 axis on the next step k = K + 2 and p

(k)

2

continues to increase and approach p

∗

2.

5.3 Distribution with More Weight on the Larger Link (decreased hs)

We now discuss the case μ > 0, where hs < hT (c) . First note that for any μ the equation for p

(k)

1

can be rewritten

as,

p

(k+1)

1 =

h

p

(k)

1 − h((λ + μ)β2{x

∗

1 − xs(k)}

i+

, x

∗

1 =

λ

λ + μ

c2/β2 (35)

We have x

∗

1 < xs∗ < c2/β2 since xs∗ = θ

c2

β2

and θ < 1. As before, we rst assume that p

(0)

i ∈ Wi. If xs(0) ∈ [x

∗

1,

c2

β2

]

then p

(k)

1

increases and since p

(k)

2 > p(k)1

, it follows that p

(k)

i ∈ Wi i = 1, 2 for all k ≥ 0 and xs will approach xs∗

.

Rewriting (29) to reveal the behaviour of p

(k) near xs∗

, we have,

p

(k+1)

1 = p

(k)

1 + h



μ

(λ + μ)

2 + 1

+ β1(xs(k) − xs

∗

)



(36)

p

(k+1)

2 = p

(k)

2 − h



μ(λ + μ)c2

(λ + μ)

2 + 1

+ β2(xs(k) − xs

∗

)



. (37)

Therefore it follows that p

(k)

1

increases and p

(k)

2 decreases in this situation so that p

(k)

2 − p

(k)

1 → 0 as k → ∞. This

means that γ(k) → ∞, where γ(k) is the solution of (17) at the kth step and the iterations fail to converge.

9
Figure 3: (p1, p2) plane when hs > hT (c)

If xs(0) < x∗

1, then p

(k)

1 and p

(k)

2 decrease. The dot product ∆p · h−β2, β1i = −hμβ2c2 shows that when p

(0)

i ∈ Wi

then p

(k)

i ∈ Wi because in this region, the increment ∆p is pointing away from the p2 (p1 = 0) axis. At xs(k) = x

∗

1,

p

(k)

1

remains xed but p

(k)

2 decreases, i.e. ∆p is pointing downward. xs(k) increases until it enters the interval [x

∗

1,

c2

β2

],

and approaches xs∗. Therefore p2 decreases and p1 increases. Consequently p

(k)

2 −p

(k)

1 → 0 as in the previous case. If

xs(0) >

c2

β2

then p2 and p1 both increase. Thus, x ̄

(k)

increases and xs(k) decreases and eventually enters the interval

[ ̄x

∗

1,

c2

β2

]. Suppose therefore that this is the case. If for some k, p

(k)

1 = 0 then , since p

(k)

2 decreases and p

(k)

1

increases,

either p

(k)

2 → p

∗

2 while p

(m)

1

remains 0 for m ≥ k or p

(m)

1 becomes positive and is therefore in W1. In the latter case

we can use the previous arguments for the case p

(k)

i ∈ Wi that show that p

(k)

2 − p

(k)

1 → 0.

Our nal case for the parameter choice μ > 0 is to suppose that xs(0) >

c2

β2

. Clearly xs will decrease until it

enters the interval [x

∗

1,

c2

β2

]. Previous arguments can then be used to determine the fate of p

(k)

i

, i = 1, 2. We in

fact see the divergence of γ

(k)

in our numerical computations. The cases discussed in this section correspond to the

selection of a distribution that allocates a larger fraction of trac to link 1 than the allocation dened by (30)and

the corresponding critical entropy in equation(27). Thus hT (c) denes the outer limit of how far one can decrease

entropy in order to increase utility.

6 DIAMOND TOPOLOGY

We turn our discussion now to another simple topology (see Figure 5 ) with 5 links attached to a single source

destination pair. As seen in the gure there are 3 routes, using the links indicated in the gure.

Inspection of the gure leads to the system:

p

(k+1)

1 =

h

p

(k)

1 − h{c1 − (β

(k)

1 + β

(k)

3

)xs(k)}

i+

(38)

p

(k+1)

2 =

h

p

(k)

2 − h{c2 − β

(k)

2 xs(k)}

i+

(39)

p

(k+1)

3 =

h

p

(k)

3 − h{c3 − β

(k)

1 xs(k)}

i+

(40)

p

(k+1)

4 =

h

p

(k)

4 − h{c4 − (β

(k)

2 + β

(k)

3

)xs(k)}

i+

(41)

p

(k+1)

5 =

h

p

(k)

5 − h{c5 − β

(k)

3 xs(k)}

i+

(42)

10
Figure 4: (p1, p2) plane when hs < hT (c)

where, as in Section 5, the bandwidth rate xs(k) = min(

w

E[d(k)]

 1

2

, M) , with E[d

(k)

] = P

r=1,2,3

β

k

r d

(k)

r =

P

r=1,2,3

β

(k)

r

P

l

0 ∈r

p

k

l

0



. The route probabilities are updated according to the following equations:

β

(k+1)

i =

exp −γ

(k)

d

(k)

i



Z(k)

i = 1, 2, 3 (43)

where Z(k) = P3

i=1 exp 

−γ

(k)

d

(k)

i



and

d

(k)

1 = p

(k)

1 + p

(k)

3

, d(k)

2 = p

(k)

2 + p

(k)

4

, d(k)

3 = p

(k)

1 + p

(k)

5 + p

(k)

4

. (44)

As was the case with the twolinks topology, we will examine the dynamics for a special choice of capacities. Here,

led by the search for strictly interior equilibria of (38)-(42), we take

c2 = c3, c1 = c3 + c5, c4 = c2 + c5. (45)

The Subsections 6.1-6.3 contain discussions of the dynamics (38)-(42) for values of the route distribution entropy hs

in relation to the critical entropy for this topology,

hD(c) = −



c2

c2 + c3 + c5

log c2

c2 + c3 + c5

+

c3

c2 + c3 + c5

log c3

c2 + c3 + c5

+

c5

c2 + c3 + c5

log c5

c2 + c3 + c5



. (46)

Equation (47) expresses the corresponding route distribution. In Section 6.1, (see Figure 6), we prove the existence

of a set of equilibria in (d1, d2, d3) space that correspond to solutions of the optimization problem. Propositions

6.2 and 6.3 show that these values lie on the line x ̄∗ =

P3

i=1 βid

∗

i

, with βi, the optimal route distribution given by

(47). The equilibrium bandwidth rate is unique and can be expressed in terms of the equilibrium route costs by

xs∗ =

w

x ̄∗

1/2

. These solutions are neutrally stable and do not persist when hs is perturbed. New unique and stable

equilibria for (38)-(42) arise when hs is increased. Note however that the value of the aggregate utility will be less

than the value achieved at hD(c). In sections 6.2 we study the dynamics of the iterations when hs > hD(c). Changes

in hs are reected in changes in the route allocation distribution as seen in equation (53), where ν < 1. In Section

6.3, hs < hD(c) and ν > 1. It is shown there that the iterations fail to converge and in fact the line d1 = d3 is

approached.

The proofs that the equilibrium values of subsections 6.1 and 6.2 are solutions of the original optimization

problem again rely on the proof of Theorem 1 in reference [8] . The arguments below show that the route allocation

distributions (β

(k)

1

, β(k)

2

, β(k)

3

), are constant for k ≥ 1 when hs ≥ hD(c). Thus the proofs of our statements closely

follow those in [8] and [1] therefore they are omitted.

We now choose initial conditions for p

(0)

i

, i = 1 · · · , 5, that greatly simplify the dynamics as seen in the following

result.

11
Figure 5: DIAMOND NETWORK

Lemma 6.1 Suppose the capacities in (38)-(42) satisfy (45). Further suppose the initial conditions

p

(0)

2 = p

(0)

3

, p

(0)

1 = p

(0)

3 + p

(0)

5

, p

(0)

4 = p

(0)

2 + p

(0)

5

hold, with p

(0)

i ∈ Wi, i = 1, ...5. Then

p

(k)

2 = p

(k)

3

, p

(k)

1 = p

(k)

4

, k ≥ 1

and β

(k)

1 = β

(k)

2

for k ≥ 1.

Proof of Lemma: The proof is by induction. Suppose the conclusions of the lemma hold for some k. We then

have d

(k)

1 = d

(k)

2 by (44). Now at stage k ,γ

(k) must satisfy the implicit equation(17) with dr = d

(k)

r r = 1, 2, 3. Since

β1 and β2 satisfy (43), we must have β

(k+1)

1 = β

(k+1)

2

. The other conclusions follow from the right hand sides of

(38)-(42). ✷

Remark: If p

(k)

i ∈ Wi for i = 2, 3, 5, then p

(k+1)

1 = p

(k+1)

3 + p

(k+1)

5 and p

(k+1)

4 = p

(k+1)

2 + p

(k+1)

5

. When p

(k)

i ∈/ Wi for

some i = 2, 3, 5 we cannot claim these equations are valid. Nevertheless it is always true that p

(k+1)

1 = p

(k+1)

4

.

As a corollary of Lemma 6.1 we can show that β

(k)

i

i = 1, 2, 3 is constant in k and therefore the dynamics

of (38)-(42) are greatly simplied. To see this let us call the simplex of probability distributions on the three

routes S =

n

βˆ = (β1, β2, β3) | βi ≥ 0 i = 1, 2, 3 , β1 + β2 + β3 = 1 o

. For a xed hs ≥ log(2), the subset dened

by C =

n

βˆ = (β1, β2, β3) ∈ S | H(βˆ) ≥ hs

o

is a closed convex region enclosed by a smooth simple closed curve

as boundary. It is the constraint region of the optimization problem (3)-(4). Its boundary is the level curve ` = n

βˆ ∈ S | H(βˆ) = hs

o

. When hs < log(2), the level curve breaks up into 3 pieces at the points where some βi = 0

(see Figure 10 ). When 0 < hs < log 3 there are precisely two points in C with distribution hs that satisfy β1 = β2.

Each point corresponds to one of the conditions β1 > β3 or β1 < β3. It is not hard to show that in the region

where d

(k)

3 ≥ d

(k)

1 = d

(k)

2

, we have β

(k)

1 = β

(k)

2 ≥ β

(k)

3

so that over any time interval where this inequality is satised,

β

(k)

j

j = 1, 2, 3 is constant. When hs < log 2, β1 = β2 > β3 occurs when β3 = 0. Therefore the corresponding value

of hs must therefore be log 2 which is infeasible.

Corollary 1 Assume the hypotheses of Lemma 6.1 hold and let hs be given with hs > log(2). Further suppose that

d

(l)

3 > d(1) for 1 ≤ l ≤ k. Then βˆ(l) = βˆ(hs) where βˆ(hs)

is the distribution with entropy hs satisfying β

(hs)

1 = β

(hs)

2 ≥

β

(hs)

3

. The latter inequality is strict when hs < log(3).

Remark: The dual function Q in (20) is dierentiable in the region {p | d3 > d1 }.

12
Figure 6: (d1, d3) plane for hs = hD(c)

6.1 Diamond Route Distribution Using Link Capacities

We assume a value of hs for which

βˆ(hs) =



c3

c2 + c3 + c5

,

c2

c2 + c3 + c5

,

c5

c2 + c3 + c5



(47)

As was true with the twolinks topology, the values of xs for which ∆p

(k)

i = 0 when p

(k)

i ∈ Wi i = 1 · · · 5, will play an

important role in dening the dynamical behaviour of the link and route costs. Here Wi = { pi ≥ 0 | pi − h∆pi > 0 }

where ∆i is the part of the expression on the right hand side of (38)-(42) inside the curly brackets. Since the entropy

in (47) is expressed in terms of link capacities that satisfy (45) it is not hard to show that xs

(∗)

i = xs(∗) = c2 +c3 +c5

where xs(∗)as in Section 5.1, is the equilibrium bandwidth rate. Equations for the route costs can be obtained from

(38)-(42) when p

(k)

i ∈ Wi.

d

(k+1)

1 = d

(k)

1 − h [C1 − xs(k)b1] (48)

d

(k+1)

3 = d

(k)

3 − h [C3 − xs(k)b3] (49)

where C1 = c1 + c3, b1 = β1 + β2 + β3 = 1, while C3 = c1 + c4 + c5, and b3 = β1 + β2 + 3β3 with βi = β

(hs)

i

. Recall

that Lemma 6.1 implies that d

(k)

1 = d

(k)

2

so the equation for d2 is unecessary. We assume that initial values of pi

begin in Wi. When (48)- (49) are valid it can be seen that for ∆d

(k)

i = d

(k+1)

i − d

(k)

i

i = 1, 2, 3, the dot product

< b3, −b1 > · < ∆d

(k)

1

, ∆d

(k)

3 > is,

b3∆d

(k)

1 − b1∆d

(k)

3 = 2(1 − ν)(c2 + c3) (50)

where in the present case ν = 1 (see equation (47) and (53)). Let x ̄

∗ be the mean route cost corresponding to

xs∗ =



w

x ̄

(∗)

1/2

and let ld be the line in the d1, d3 plane given by ld : β1d1 + β2d2 + β3d3 =  ̄x

∗

(see Figure 6) It

intersects the d3 axis at the point (0,

x ̄

∗

β3

). Let l0 be the line through this point, parallel to the vector < −b3, b1 >

and given by the equation,

l0 : b1d3 − b3d1 = b1

x ̄

∗

β3

(51)

Finally, if P is the intersection of ld with the line d1 = d3, let l1 be the line passing through P and parallel to l0. We

call A the region in the d1, d3 plane bounded above by l0 and below by l1. Propositions 6.2 describes the dynamics

of (48)-(49) when p

(k)

i ∈ Wi i = 1 · · · 5 for all k ≥ 1 and Proposition 6.3, discusses equations (38)- (42) when at some

time k and for some i, p

(k)

i ∈/ Wi.

13
Proposition 6.2 Assume ν = 1 and suppose p

(0) is chosen so that (d

(0)

1

, d(0)

3

) lies in A ∩ {(d1, d3)|d3 ≥ d1}. Further

suppose that p

(k)

i ∈ Wi for all k ≥ 0 and the hypotheses of Lemma 6.1 are satised. Then the orbit d

(k) = (d

(k)

1

, d(k)

3

)

moves along a straight line through d

(0) parallel to l0 , and converges to a point d∗ = (d∗

1, d∗

3) on ld. We have

β1d

∗

1 + β2d

∗

2 + β3d

∗

3 =  ̄x

∗ with d∗

i > 0.

Proof: Since p

(k)

i ∈ Wi, k ≥ 0, we can compute the dot product < −b3, b1 > · < ∆d

(k)

1

, ∆d

(k)

3 >= 0 for all k, by

equation (50) where ∆d

(k)

i = d

(k+1)

i −d

(k+1)

i

i = 1, 2, 3. Therefore iterates proceed in a direction parallel to < b1, b3 >

, i.e. parallel to the line l0. Since p

(k)

i ∈ Wi, we can write down the following equation for x ̄

(k+1), the mean route

cost at time k + 1 ,

x ̄

(k+1) = Tx ̄(k) =  ̄x(k) − h(β1b1 + β2b2 + β3b3)(xs

∗ − xs(k)) (52)

where xs∗ = c2 + c3 + c5 and xs(k) = ( w

x ̄

(k)

)

1

2 . As in Section 5.1 we can see that T is a uniform contraction when

d

(k) ∈ A so that x ̄(k) → x ̄∗

, where xs∗ = ( w

x ̄∗ )

1

2 . When d

(k)

is above the line ld, d

(k)

1 and d

(k)

3 decrease and approach

the line from above. Conversely when d

(k)

is below the line, the d

(k)

1

, and d

(k)

2 both increase so the approach is from

below. ✷

Remarks: Note that d

(k)

1 < d(k)3

for all k ≥ 1 in this situation so we can legitimately treat the β

(k)

j

j = 1, 2, 3 as

constant.

If (d

(0)

1

, d(0)

3

) is below the line l1, the orbit will reach the line d1 = d3 before it reaches ld and hence γ(k) will diverge

to ∞.

The fate of orbits beginning at points in the region A ∩ {(d1, d3)|d3 ≥ d1} where for some k p(k)

i ∈/ Wi , is the

same as that of orbits that begin above the line l0 because in both cases, the orbits approach the d3 axis. The next

proposition discusses the latter situation. Here some of the link prices will converge to zero, an indication the trac

on those links have reached their capacity.

Proposition 6.3 If p

(0) is chosen as in the previous proposition but (d

(0)

1

, d(0)

3

) is above the line l0, then d

(k)

approaches the d3 axis. Moreover:

1. if for some k, p

(k)

1 ∈/ W1, and p

(l)

3 ∈ W3 l ≥ 0 , then p

(k)

converges to p

∗ = (0, p∗

2, p∗2, 0, p∗5), with β1p

∗

2 + β2p

∗

2 +

β3p

∗

5 =  ̄x

∗

.

2. if for some k p(k)

3 ∈/ W3, and p

(l)

1 ∈ W1 , l ≥ 0 , then p

(k)

converges to p

∗ = (p∗

1, 0, 0, p∗1, p∗5) where β1p

∗

1 +

β2p

∗

1 + β3(2p

∗

1 + p

∗

5) =  ̄x

∗

.

3. if for some k p(k)

i ∈/ Wi i = 1, 3, then p

(k)

converges to p

∗ = (0, 0, 0, 0, p∗

5) where β3p

∗

5 =  ̄x

∗

.

Proof: The proof that the orbit d

(k)

, k ≥ 0 proceeds along a straight line parallel to l0 is also valid for this case.

Therefore the orbit must approach the d3 axis. We can also assume that h is small enough so that any point above

the line l0 has a d3 value large enough so that either p1 ∈ W1 or p3 ∈ W3 or p

(k)

5 ∈ W5. Since d

(k)

1 = p

(k)

1 + p

(k)

3

, there

is some k, where either p

(k−1)

1 ∈/ W1 and/or p

(k−1)

3 ∈/ W3.

(i) If p

(k−1)

1 ∈/ W1 we must have p

(k)

1 = p

(k)

4 = 0. From (38)-(42), one can therefore see that p

(l)

1 = 0 l ≥ k as long as

xs(l) ≤ xs∗, l ≥ k. During this time we can restrict our attention to the equations for p2 (= p3) and p5. Here

we assume that p

(k)

2 ∈ W2. The mean route cost at time k, x ̄

(k) = β1p

(k)

2 +β2p

(k)

2 +β3p

(k)

5

, continues to decrease

and converges to x ̄

∗

. We have x ̄

(l) ≥ x ̄∗

so xs(l) ≤ xs∗for all l ≥ k. Meanwhile, p

(k)

2

, p

(k)

5

converge to values

p

∗

2 , p∗

5 for which x ̄ =  ̄x

∗ while p∗

1 = p

∗

4 = 0. Note that p

(l+1)

2 −p

(l+1)

5 = p

(l)

2 −p

(l)

5 +h(β

(hs)

3 −β

(hs)

2

)(xs∗ −xs(k)).

Therefore if p

(k)

5 > p(k)2

, the inequality remains true for l ≥ k and d

(l)

3 ≥ d

(l)

1

.

(ii) If p

(k−1)

3 ∈/ W3 , we will also assume in analogy with (i) that p

(k)

1 ∈ W1. Since p

(k)

2 = p

(k)

3 = 0, and p

(k)

1 = p

(k)

4

,

a system for p1 and p5 remains. Arguing as before it can be seen that since x ̄

(l) ≥ x ̄∗

, for l ≥ k , then

p

(l)

1 = 0 l ≥ k. The mean route cost at time k, x ̄

(k) = (1 + β3)p

(k)

1 + (β2 + β3)p

(k)

5

, decreases and p

(k)

1

, p

(k)

5

converge to p

∗

1, p∗5 where x ̄

∗ = (1 + β3)p∗

1 + (β2 + β3)p

∗

5. The remaining limiting pi values are p

∗

2 = p

∗

3 = 0. In

this case we also have d

(l)

3 ≥ d

(l)

1

, for l ≥ k.

(iii) If both p

(k−1)

3 ∈/ W3 and p

(k−1)

1 ∈/ W1 hold, then we can repeat the reasoning in (i) and (ii) and conclude that the

system reduces to the evolution of just p5 . In this case p

(k)

5

converges to p

∗

5 where β3p

∗

5 =  ̄x

∗

. The remaining

limiting values are p

∗

i = 0 i = 1 · · · 4. As in the previous cases, d

(l)

3 > d(l)1

for l ≥ k. ✷

14
Proposition 6.2 shows that there are inntely many equilibrium points with d

∗ > 0 for the system (38)-(42) with

each point depending on the initial condition d

0

. However the equilibrium value xs∗is unique. In the d-plane,

linearization about any such point shows that each has a neutrally stable direction (eigenvalue 1) along the direction

of ld, and an asymptotically stable direction parallel to l0 and so these points are neutrally stable. Thus it is not

surprising that they do not persist when a parameter,in particular the entropy hs , is changed. The equilibrium

points in the p plane discussed in Proposition 5.3 are more dicult to analyze because the right hand side of the

system fails to be dierentiable when any pi ∈/ Wi. Nevertheless linearization of the reduced system discussed in (i)

and (ii) in the proof of Proposition 6.3 shows the equilibrium points there are neutrally stable and the equilibrium

point in (iii) is asymptotically stable. A complete proof would have to show that the stability demonstrated in the

reduced system is also valid in the entire p plane. The fact that, in each of these cases, the plane for the reduced

system is invariant under (38)-(42) leads us to conjecture that this extension can be made.

In the next section we will discuss the eect of perturbing the route allocation away from the distribution dened

by the critical entropy. Under such a perturbation the neutrally stable points will disappear but the asymptotically

stable point in Proposition 6.3 (iii) with a single positive price for link 5 will persist.

6.2 Diamond Route Distribution with increased hs

In our discussion of the behavior of (38)-(42) for perturbed entropy values, it is useful to introduce a parameter ν

that decreases (increases) the weight on links 2 and 3 as the perturbed entropy increases (decreases). Since we will

continue the assumptions on the capacity values displayed in equation (45), β

(hs)

1 = β

(hs)

2 will still hold. Therefore,

it is assumed that the entropy is the value hs for which the route allocation distribution is,

βˆ(hs) =



νc3

c2 + c3 + c5

,

νc2

c2 + c3 + c5

,

c5 + (1 − ν)(c2 + c3)

c2 + c3 + c5



, (53)

where ν < 1. The entropy of the distribution with β

(hs)

1 = β

(hs)

2 = β, is H = 2β log(2)+hβ where hβ = −2β log(2β)−

(1−2β) log(1−2β). It is not hard to show that if β > 1/4, decreasing β increases H and vice versa. Since we conne

our analysis to the region d1 ≥ d3 (see the discussion at the beginning of Section 6), we must consider a distribution

where β1 = β2 ≥ β3. This implies that β ≥ 1/3.

The case ν < 1 corresponds to an entropy value hs larger than the critical entropy where ν = 1. Here in

contrast to Section 6.1, the values of xs for which ∆p

(k)

i = 0 in (38)-(42) are not all equal and so any orbit for

which p

(k)

i ∈ Wi, k ≥ 0 as in Proposition 6.2 will not become a stationary point once d

(k)

reaches the line ld . The

equilibrium value x ̄

∗

satises:

xs∗ = (w/x ̄

∗

)

1/2

, where xs∗ = (c2 + c3 + c5)



1 −

(1−θ)β3b3

β1b1+β2b2+β3b3



and

θ = (c2 + c3 + 3c5) / (c2 + c3 + 3c5 + 2(1 − ν)(c2 + c3))

The neutrally stable points discussed in that proposition no longer exist. The same situation also holds for the

neutrally stable points discussed in parts 1 and 2 of Proposition 6.3. However, as the next proposition shows, for

each ν < 1, there is a unique equilibrium bandwidth rate and a corresponding unique equilibrium to which orbits of

(38)-(42) converge.

In what follows we let B

0

be the region in the d1, d3 plane bounded above by the line l0 , below by the line l1

and on the left by d3 axis. The lines l0 and l1 are described just as they are in Section 6.1. We then dene

B = B

0

∩ {(d1, d3) | d1 ≥ d3}.

Proposition 6.4 Let hs be the entropy dened by the distribution in (53) and suppose the initial values of {p

(0)

i

i =

1 · · · 5} satisfy the hypotheses in Lemma 6.1. Then p

(k) = (p

(k)

1

, p

(k)

2

, p

(k)

3

, p

(k)

4

, p

(k)

5

) → (0, 0, 0, 0, p∗

5)

Proof: Since p

(0)

i ∈ Wi i = 1, · · · 5, the initial dynamics of the route cost vector d

(k)

is governed by the equations

in (48)-(49). First suppose, d

(0) ∈ B. The mean route cost, x ̄(k) = β1d

(k)

1 + β2d

(k)

2 + β3d

(k)

3 becomes stationary (i.e.

∆ ̄x

(k) = 0) when xs(k) = xs∗

. We can repeat the arguments in the derivation of (32) from (31) to this situation to

show that the mapping T, dened by

x ̄

(k+1) = Tx ̄(k) =  ̄x(k) − h ̄b{xs∗ − xs(k)} (54)

where  ̄b = β1b1 +β2b2 +β3b3, is a global contraction in B with a xed point at x ̄

∗

. Consequently orbits in the d plane

starting in B will converge to the line ld. Once the orbit approaches the line, it remains there and moves toward the

d3 axis i.e. d1 decreases while d3 increases. This is because,

xs

∗

3 < xs∗ < xs∗1 (55)

15
where xs∗

1 = C1/b1 = c2 + c3 + c5 and xs∗

3 = (c2 + c3 + c5)θ are values for which ∆d

(k)

i = 0, for i = 1, 3. If d

(0) lies

above the line l0, then x ̄

(k) decreases since xs(k) < xs∗

. It is clear therefore that regardless of where the orbit starts,

d1 will eventually become small enough so that p

(k−1)

1 ∈/ W1 or p

(k−1)

3 ∈/ W3 for some k for the rst time.

We examine the case when p

(k−1)

3 ∈/ W3 rst. It follows that p

(k)

3 = 0. We will show that p

(k+1)

3 = 0 and that the

subset {p|p3 = 0} is invariant under the iteration of (38)-(42). By Lemma 6.1, p

(k)

2 = 0, and p

(k)

1 = p

(k)

4

, so we will

focus on p1 and p5 . If p

(k)

i ∈ Wi i = 1, 5, then an equation for x ̄

(k+1) can be obtained. The value let us call it xsp∗

1,5,for

which ∆ ̄x

(k+1) = 0 is xsp∗

1,5 = u ∗ xsp∗

1 + (1 − u) ∗ xsp∗

5 where u =

(1+β3)(β1+β3)

(1+β3)(β2+β3)+β2

3

. Here, xsp∗

1 = (c3 + c5)/(β1 + β3)

and xsp∗

5 = c5/β3 are xs values for which ∆p

(k)

i = 0, i = 1, · · · , 5. The inequality xsp∗

5 < xsp∗

1,5 < xsp∗

1 < xsp∗

3

holds. It can also be shown that the mapping x ̄

(k+1) = Tx ̄(k)

is a contraction in the p1, p5 plane with a xed point x ̄

∗

1,5

corresponding to xsp∗

1,5. Now p

(k−1)

3 ∈/ W3, implies that xs(k −1) ≤ xsp∗

3 = (c2 +c3 +c5)/ν and if xs(k −1) > xsp∗

1,5,

then xs will decrease and xs(k) < xs(k − 1). If xs(k − 1) < xsp∗

1,5 then xs(k) > xs(k − 1) but since h is small

xs(k) < xsp∗

3. Moreover, the distance between xs(k) and xsp∗

1,5 decreases because of the contraction property in

the iteration of x ̄

(k)

. Thus p

(k+1)

3 = 0. Even though, subsequent iteration of p1 and p5 leads to increasing xs when

xs(k) < xsp∗

1,5 the corresponding value of xs will approach but cannot exceed xsp∗

1,5. Thus p3 remains 0. Eventually

(p

(k)

1

, p

(k)

5

) converges to the line xsp∗

1,5 = β1p1 + β3p5 and remains on the line as p

(k)

1 → 0, and p

(k)

5 → p

∗

5, where

xs∗ = xsp∗

5.

If p

(k−1)

1 ∈/ W1 and p

(k−1)

3 ∈/ W3, then since xsp∗

1 > xsp∗

5, xs(k) > xsp∗

1 implies that x ̄

(k) = β3p

(k)

5 will increase and

thus xs decreases and eventually, xs(l) < xsp∗

1 for some l ≥ k. If p

l)

1 = 0, it remains 0 and the orbit remains on the p5

axis and converges to p

∗

5. If p

(l)

1 ∈ W1 for some l then we are back in case discussed in the previous paragraph. In all

these cases the orbits eventually converge to the point (0, 0, 0, 0, p∗

5) where x ̄

∗ = β3p∗

5 with corresponding xs∗ = c5/β3.

Finally we turn to the case where the equations for d lose validity because for some k, p

(k−1)

1 ∈/ W1 but

p

(k−1)

i ∈ Wi i = 3, 5. We are supposing that up to this point, p

(l)

i ∈ Wi l = 0, 1 · · · k − 2, i = 1, 3, 5. From

the Remark following Lemma 6.1, we have p

(k−1)

1 = p

(k−1)

3 + p

(k−1)

5

. But p

(k−1)

3 > h{c3 − β1xs(k − 1)} and

p

(k−1)

5 > h{c5 − β3xs(k − 1)} so it must be that p

(k−1)

1 > h{c1 − (β1 + β3)xs(k − 1)}. Thus p

(k−1)

1 ∈ W1 a contradiction. Consequently this case cannot occur. ✷.

Remark: Since orbits that begin below the line l1 blow up we will not discuss these here.

6.3 Diamond Route Distribution with decreased hS

Using the notation introduced in Section 6.2 we consider ν > 1. This has the eect of increasing the weight on links 2

and 3 with a compensating decrease of weight on link 5. The discussion in Section 6.2 shows that the corresponding

entropy hs is decreased. In contrast with the previous case, the algorithm fails to converge and in fact the root γ(k)

of (17) diverges as k → ∞. This section details a proof of this fact. For a particular sub-case (see Case 1a) we assume

that 2c2 > c5.

We assume initial values of p, such that p

(0)

i ∈ Wi i = 1, · · · , 5. The subsequent dynamics at least intially can

therefore be described by equations (48)-(49) Let the xs values for which ∆d

(k)

j = 0 j = 1, 2, 3 be denoted by xs∗

j

.

The relation (55) is now,

xs

∗

1 < xs∗ < xs∗

3 (56)

Let τ1 be the line in the d plane given by x ̄ =  ̄x

∗

1, where x ̄

∗

1 is the mean cost corresponding to xs∗1. The line τ3 is

dened analogously. The line τd :  ̄x =  ̄x

∗

lies between τ1 and τ3 so we will dene C to be the region bounded by

these lines , the d3 axis , and the line {(d1, d3)|d3 = d1}. If d

(0) is an initial point whose corresponding xs value is

xs(0) < xs∗

1, then d1 and d3 will decrease. On the other hand if the corresponding xs value satises xs(0) > xs∗3,

then d1, and d3 will increase (see Figure 7). Orbits either enter the region C or they intersect or approach the d1

or d3 axes. We describe the fate of orbits that enter C. The behavior of x ̄

(k)

is governed by (54). The contraction

property of T implies that d

(k)

approaches the line τd and once the orbit reaches the line it moves along it. By (56)

see that d1 increases and d3 decreases so it is clear that d

(k)

approaches the line d1 = d3. Thus γ

k must diverge.

Suppose now that an orbit's initial position is located above the line l0 (see equation (51) and Figure 7). In this

situation, at least initially xs(k) ≤ xs∗

1 < xs∗3, therefore d1 and d3 are decreasing and orbits approach the d3 axis.

We have d

(0)

3 ≥ δ where (0, δ) is the intersection of l0 with the d3 axis. Thus the equation (48) will cease to be valid

for some k for the rst time. Since d

k−1

1 = p

(k−1)

1 + p

(k−1)

3

, we can suppose either p

(k−1)

1 ∈/ W1 or p

(k−1)

3 ∈/ W3. One

can verify after some algebra, an inequality that will be used in the arguments that appear below. Recall that xsp∗

i

is the value of xs for which ∆p

(k)

i = p

(k+1)

i − p

(k)

i = 0, when p

(k)

i ∈ Wi. For ν > 1, xsp∗

3 = xsp∗2 < xsp∗1 < xsp∗5.

16
Figure 7: (d1, d3) plane for hs < hD(c)

Case 1: First assume that p

(k−1)

1 ∈/ W1 and thus p

(k)

1 = 0.

Case 1a If p

(k)

2 = p

(k)

3 ∈ W2 and p

(k)

5 ∈ W5, an equation for x ̄

(k+1) can be obtained in terms of p

(k+1)

2 and p

(k+1)

5 of

the form x ̄

(k+1) = Tx ̄(k)

analogous to (32). T is a contraction with a xed point x ̄

∗

2,5 such that xs∗2,5 =



w

x ̄

∗

2,5

1/2

, and

xs∗

2,5 = (1 − f)xsp2 + fxsp5 with f =

β

2

3

(β2

3+(1−β3)β2)

. Now suppose xs∗

2,5 < xsp∗1. Then x ̄

(k) = β1p

(k)

3 + β2p

(k)

2 + β3p

(k)

5

will move closer to the value of x ̄ corresponding to xs∗

2,5. Thus xs(k + 1) < xsp1 and therefore p

(k+1)

1 = 0. We could

repeat this argument so that by induction this implies then that p

(l)

1 = 0 l ≥ k. Now d

(l)

3 ≥ d

(l)

1 and p

(l)

1 = 0 = p

(l)

4

,

therefore p

(l) ≥ p

(l)

2

In the p2, p5 plane, xs(k) → xs∗

2,5 and since xsp∗2 < xs∗2,5 < xsp∗1 < xsp∗5, we must have p5 decreasing and

p2 increasing. Thus (p

(k)

2

, p

(k)

5

) approaches the line p2 = p5 as k → ∞. This means that we approach the line

d1 = d2 = d3. The following sucient condition for xs∗

2,5 < xsp1 is derived in the Appendix and is satised when

κ =

c2

c5

> 1/2 and ν > 1.



1

κ + 1 + (1 − ν)κ

−

f

1 + 2(1 − ν)κ



> 0 (57)

(58)

The preceeding reasoning assumed p

(k)

2 ∈ W2. The convergence of (p

(l)

2

, p

(l)

5

) to the line x ̄ = xs∗

2,5 and the fact that

xs∗

2,5 > xsp2 shows that p

(l)

2 ∈ W2 for l ≥ k.

Case 1b: Suppose p

(k)

3 ∈/ W3. Then xs(k) ≤ xsp∗

3 and since xsp∗3 < xsp∗1 < xsp∗5, both d

(k)

1 and d

(k)

3 decrease.

Therefore even though p

(k+1)

3

is 0, xs(k) increases. xs continues to increase until xs(l) ≥ xsp∗

3, for some l ≥ k. If

xs(l) = xsp∗

3 then note that p

(l)

5 decreases, and hence x ̄

(l) decreases. Therefore xs will continue to increase and p3

eventually becomes positive and we are back in the previous case where p

(k)

3 = p

(k)

2 ∈ W2. If we have p

(k)

5 ∈/ W5, then

p

(k)

1 = 0 implies that d

(k+1)

1 = p

(k+1)

3 ≥ d

(k+1)

3 = p

(k+1)

5 = 0. So we have crossed the line d1 = d3 causing γ to diverge.

Case 2: Finally let us consider the case when for the rst time , p

(k−1)

3 ∈/ W3. Then xs(k −1) ≤ xsp∗

3 < xsp∗1 < xsp∗5

so d1 and d3 decrease, causing xs(k) to increase. This increase continues until xs(l) ≥ xsp3, for some l ≥ k.

Case 2a: If p

(k)

1 ∈ W1, then xs continues to increase and eventually, p

(l)

3 ∈ W3 for some l ≥ k and is increasing.One

can check that xsp∗

3 = xs∗1 < xsp∗1 < xsp∗5. If xs(l) ≤ xsp1, then (d

(l)

1

, d(l)

3

) ∈ C and we can apply the results of the

discussion of orbits in that region to this case. If xs(l) > xsp1 and p

(k)

5 ∈ W5 then, equations (48)-(49) can be used

17
to show that (d

(l)

1

, d(l)

3

) is either in or will eventually enter C. If p

(k)

5 ∈/ W5 then d

(k+1)

1 = d

(k+1)

3

, i.e. we are at the

boundary of the feasible region so γ

(k+1) = ∞.

Case 2b Note that xsp∗

3 < xs∗2,5 < xsp∗1 . If p

(k)

1 ∈/ W1 then xs increases until for some l ≥ k, p

(l)

3 > 0. As

in Case 1a, the dynamics of d

(l)

1

, d(l)

3 are determined by p

(l)

3 = p

(l)

2 and p

(l)

5 as long as xs(l) < xsp∗

1 with l > k. We

can repeat the arguments of Case 1a to show that in fact xs(k) → xs∗

2,5.

7 UTILITY-ENTROPY TRADEOFF

Figure 8: Twolinks Utility vs. entropy

Figure 9: DIAMOND Utility vs. entropy

The route distribution entropy hs is a measure of the degree of path diversity of an allocation scheme that uses

that distribution.The tradeo between path diversity and utility is not well understood in general but our approach

allows us to frame the issue in relation to a reference entropy that denes an intrinsic allocation dened by the link

capacities and topology of a given network. Using the critical entropy value as a reference, the eect of decreasing or

increasing path diversity beyond this allocation can be assessed. This is illustrated in our examples by plotting the

utility as a function of hs. In each case, this was done by computing the average utility over a nite time interval for

18
each hs for a range of values that contained the critical entropy value. Figure 8 shows the computation for TwoLinks

and Figure 9 shows the corresponding computation for Diamond. For values of hs less than the critical value, a time

interval was chosen so that orbits were still within the feasible region. Increasing the entropy from hs = 0, the value

for a single path allocation scheme, the iterations did not converge until a critical entropy value was reached.

Inspection of the curves shows that a network using an allocation with larger entropy can increase utility by

decreasing the entropy (that is, increasing the fraction on less expensive links) up until the critical value is reached.

The diering topologies of TwoLinks and Diamond aect what happens when the allocation entropy is less than the

critical value. In TwoLinks the utility cannot be increased by decreasing the entropy. In Diamond, the utility is

increased until the value hs = log 2. Note in contrast to [9] the utility does not reach a maximum at the critical

entropy value. We could not stably iterate equations (38) -(42) for values hs < log 2. We nd that the iterations

fail to converge for any hs < hD(c). A possible reason for this comes from a visualization of the route allocation

distributions for 3 routes (Figure 10). As discussed in Section 4, each β = (β1, β2, β3), such that βi ≥ 0 i = 1, 2, 3 ,

β1 +β2 +β3 = 1, can be associated with a point in the equilateral triangle with altitude height 1. The transformation

from the simplex in 3-space to this triangle is smooth and invertible. The region dened by the constraints of the

optimization problem i.e. inequalities (11)-(13) is convex and bounded by the level curve for hs. Level curves for

various values of hs are mapped to the curves in the triangle. When hs = log 2, the curve is tangent to the boundary

of the triangle and therefore the level curve is tangent to the boundary of the simplex. The points of tangency are

singular points for the entropy function (i.e. points where the derivative of hs as a function of β fail to exist). Once

hs < log 2, the curve becomes disconnected. It is interesting to note that the source of the trouble comes from

the implicit equation. Indeed there are two solutions of the implicit equation for each hs and when hs < log 2, the

values of γ(k) oscillate between these values introducing sustained oscillations into the system that resemble the route

apping phenomenon discussed in [12] and other work. For such hs note that we are eectively operating with only

two of the three links, so that the Diamond topology is equivalent at this stage to the Twolinks topology.

8 CONCLUSION

In this paper, we presented a convex network optimization problem for simultaneously controlling congestion and

route allocation. The set of possible route allocations that can be used by a source s is constrained by placing a

lower bound on the route distribution entropy hs. As a rst step towards understanding the issues involved in any

protocol based on this model we derived a dual iteration scheme and analyzed the dynamics for two simple topologies.

Sucient conditions insuring that the equilibria of the iteration scheme are solutions of the optimization problem

are given. We also discuss the limits of the algorithm. Specically in our examples we identify parameter values hs

where the iterates eventually leave the region of feasibility. For such parameter values some other approach-using

subgradient methods may prove useful.

Another key issue here is the trade-o between network utility and hs, a parameter that measures path diversity.

After making mild assumptions about the capacity of the links in each example we found a critical value of the

entropy. The average utility can always be increased if the system has an allocation with route distribution entropy

hs that is larger than the critical value. Figure 8 shows how the average utility for the TwoLinks topology plateaus

so that its maximum value is achieved at or near the value at the critical entropy hT (c) similar to the results of the

simulation in [9]. However Figure 9 shows that the average utility for the Diamond topology continues to increase

for hs < hD(c). A natural lower bound of log 2 is reached, corresponding to the point where one of the 3 routes is

eliminated and the topology is eectively equivalent to TwoLinks. What we can therefore say in this case is that the

utility value at hD(c) is the largest practicably achievable one given a protocol based on dual iteration.

In summary, we see that one cannot increase the utility by choosing a path distribution with entropy less than

the reference entropy without producing infeasible solutions. For each of the examples, the link capacities and the

topology introduce inherent limits to how closely the route allocation can approach the single path specication

scheme.

9 APPENDIX

9.1 Constant β

(k)

in TwoLinks

In this section we will show that

Theorem 9.1 Let c1

c2

= λ and β

(hs)

1

βhs

2

= λ + μ with λ > 1 and λ + μ ≥ 0. Then

β

(k)

i ≡ β

(hs)

i

i = 1, 2, k ≥ 0 (59)

where H(β

(hs)

) = −(β

(hs)

1

log β

(hs)

1 + β

(hs)

2

log β

(hs)

2

) = hs.

19
Proof: For simplicity we will drop the hs notation from β

(hs)

i

i = 1, 2. Given an entropy value hs < log 2 there are

exactly two associated probability distributions, either {β, 1 − β} or {1 − β, β}. If we dene the ratio ρ =

β1

β2

, then

the distributions can be expressed as either {

ρ

1+ρ

,

1

1+ρ

} or {

1

1+ρ

,

ρ

1+ρ

}. If p

(k)

1 < p(k)2

then the choice of a positive

root of (17) implies that β

(k)

1 =

ρ

1+ρ where ρ < 1. If on the other hand, p

(k)

1 > p(k)2

then β

(k)

1 =

1

1+ρ

. ✷

Note that the condition hs < log 2, rules out the possibility that p

(k)

1 = p

(k)

2

for any nite k since the solution

of (17) would then be ∞. These facts lead to the observation that β

(k)

i

, i = 1, 2 remains constant in k if and only if

p

(k)

2 − p

(k)

1 does not change sign. In fact a change in sign leads to a jump discontinuity in the value of βi, i = 1, 2 .

9.2 Diamond route distributions and their entropy

There are 3 routes in the diamond topology. Using planar geometry one can show that every distribution in the simplex

of distributions on 3 routes S =

n

βˆ = (β1, β2, β3) | βi ≥ 0 i = 1, 2, 3 β1 + β2 + β3 = 1 o, can be represented by a

point in an equiliateral triangle with an atltitude of height 1. This result is known as Viviani's theorem. If we

position the leftmost vertex of the base of the triangle at the origin (as shown in Figure 10), then the distribution

(β1, β2, β3) ∈ S corresponds to coordinates (x, y) in the triangle through Ψ : R2 → S given by,

β1 = y , β2 =

√

3x − y

2

, β3 = 1 −

 

y +

p

(3)x

2

!

(60)

The entropy function H(β1, β2, β3) , denes a function of x, y through (60) and h(x, y) = H(Ψ(x, y)). The distribution

with β1 = β2 = β3 = 1/3, is the image of (1/

p

(3), 1/3). A simple computation shows that the latter is a non-singular

critical point of h. Hence nearby level curves are nearly ellipses and other level curves for smaller values of hs that

do not touch another critical point must have the same topological type and so they are simple closed curves [10].

Since Ψ is ane and H is convex, h = H ◦ Ψ is convex and therefore quasi-convex. The region enclosed by a level of

h is therefore convex. At log 2, the level curve has several critical points that are the images of the intersection of

the black curve in Figure 10 with the sides of the triangle. The topological type of the level curve therefore changes.

9.3 Sucent condition that x

∗

2,5 < xsp∗1

We present a proof of the inequality (58) that appeared in Section 6.3.

Lemma 9.2 Let xsp∗

1 be the value of xs for which ∆p

(k)

1 = 0 in equation (38). Further let, xs∗

2,5 be the value of xs

for which ∆ ̄x

(k) = 0 restricted to the (p2, p5) plane. Then xs∗

2,5 < xsp∗1 if and only if inequality (58) is satised .

Proof:

We have,

xsp1 =

c3 + c5

c3 + c5 + (1 − ν)(c2 + c3)

, xsp2 = xsp3 =

c2 + c3 + c5

ν

(61)

xs

∗

2,5 = (1 − f)xsp2 + fxsp5 (62)

f =

β

2

3

β

2

3 + (1 − β3)β2

(63)

=

(c5 + 2(1 − ν)c2)

2

[2(νc2)

2 + (c5 + 2(1 − ν)c2)2]

(64)

Writing xs∗

2,5 − xsp1 = (xsp2 − xsp1) − (xsp2 − xs∗

2,5), after some algebra it can be seen that

xs

∗

2,5 − xsp1 =



1 − ν

ν

  1

c3 + c5 + (1 − ν)c3

−

f

c5 + (1 − ν)(c2 + c3)



(c2 + c3 + c5) (65)

The expression in the square brackets of equation (65) is the left hand side of inequality (58). Setting κ =

c2

c5

=

c3

c5

it can be seen that choosing κ > 1/2 is sucient when f is rewritten in terms of κ and the inequality is veried by

calculation. ✷

20
Figure 10: Diamond route allocations

References

[1] D.P. Bertsekas, J. N.Tsitsiklis "Parallel and Distributed Computation: Numerical Methods", Prentice

Hall, Englewood Clis, N. J. 1989

[2] S.Boyd, L. Vandenberghe "Convex Optimization", Cambridge University Press, Cambridge UK, 2004

[3] M.Chiang, S.H. Low, A.R. Calderbank, J.C. Doyle "Layering as optimization decomposition: A

mathematical theory of network architectures", Proceedings of the IEEE, Vol. 95, no. 1, pp. 252-312, 2007

[4] J. He, M. Bresler, M. Chiang, J. Rexford "Towards Robust Multi-Layer Trac Engineering: Optimization of Congestion Control and Routing" IEEE Journal on Selected Areas in Communications, Vol. 25, No. 5,

pp.868-880, 2007

[5] F.P.Kelly, T. Voice "Stability of end-to-end algorithms for joint routing and rate control" Computer

Communication Review, Vol. 35, No. 2, pp. 5-12, 2005

[6] X. Lin, N. Shroff, R. Srikant "On the Connection-Level Stability of Congestion-Controlled Communication

Networks", IEEE Trnasactions on Information Theory, Vol. 54, No. 5, 2008

[7] F.P. Kelly, A.K.Maulloo, D.K.H. Tan "Rate control in communication networks: shadow prices, proportaion fairness and stability." Journal of the Operational Research Society, Vol. 49, pp. 237-252, 1998.

21
[8] S.H. Low, D. E. Lapsley "Optimization Flow Control I: Basic Algorithm and Convergence" IEEE/ACM

Transactions on Networking Vol. 7, No. 6, pp.861-874, 1999

available at http://netlab.caltech.edu/pub.

[9] V. Marbukh, S. Klink "Decentralized Control of Large Scale Networks as a Game with Local Interactions:Cross Layer TCP/IP Optimization" ValueTools07

[10] Y. Matsumoto "An Introduction to Morse Theory" Translations of Mathematical Monographs, Vol. 208,

American Mathematical Society, 2002

[11] A. Peressini, F.Sullivan, J.Uhl "The Mathematics of Nonlinear Programming", Springer Verlag, New York,

N.Y. , 1988

[12] J.Wang, L. Li, S.H. Low, J.C.Doyle "Cross-Layer Optimization in TCP/IP networks" IEEE Transactions

on Networking, Vol. 13, No. 3, pp. 568-582, 2005

22