Measuring the Utility/Path Diversity Trade off in Multipath

Protocols

Fern Y. Hunt

National Institute of Standards and Technology

Mail Stop 8910

Gaithersburg, Maryland 20899

fern.hunt@nist.gov

Vladimir Marbukh

National Institute of Standards and Technology

Mail Stop 8910

Gaithersburg, Maryland 20899

vladimir.marbukh@nist.gov

ABSTRACT

We derive a model of congestion control where the trade-off

between utility and path diversity can be investigated. In

a network where there can be multiple routes between locations, each source s is assigned a route according to an allocation scheme where the degree of randomness and therefore

path diversity is controlled by hs, the entropy of the distribution defined by the allocation. Model equations are derived

from a network utility maximization problem and the results

of the analysis of two networks with a single source destination are presented. We conclude for each such network

there is a critical value of hs for which stable equilibrium

solutions of the model equations exist and using the results

of [9] it can be shown that they are also solutions of the

original optimization problem. Treating hs as a parameter,

the trade-off is discussed in terms of the behavior of the time

averaged utility as a function of hs.

Categories and Subject Descriptors

C.2 [Network Protocols]: [Routing Protocols]

Keywords:TCP/IP protocols, multipath routing, discrete

dynamics,

1. INTRODUCTION

In recent years, network protocols have been interpreted

as algorithms that solve a convex optimization problem ( see

e.g. [13], [8]). 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 efficient communication between users, link and router layers of the network.

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are

not made or distributed for profit or commercial advantage and that copies

bear this notice and the full citation on the first page. To copy otherwise, to

republish, to post on servers or to redistribute to lists, requires prior specific

permission and/or a fee.

VALUETOOLS October 20-22,2009, Pisa, Italy

Copyright 2009 ICST 978-963-9799-70-7/00/0004 ...$5.00.

Since the work of Kelly et al [8] congestion control protocols

have been seen as regulating user network transmission rates

so that the objective function that is, the aggregate utility,

is maximized subject to capacity constraints ([9], [3]). The

utility function incorporates efficient utilization and fair allocation of resources among users. Significantly such functions

have been identified 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 ([13], [3], [4], [6],[7]). Aside from the

obvious improvement in the utilization of network resources

that could be gained by such an approach, there are benefits

in this time of cybersecurity concerns to building adequate

network robustness against route disruptions. However implicit in such a protocol is a tradeoff between robustness

through path diversity on the one hand and network performance or utility on the other. Single path routing based

on e.g. the OSPF (Open Shortest Path First) protocol can

lead to route flapping instability and reduced utility. However splitting traffic equally across all paths regardless of

cost would also imply reduced utility. The best tradeoff 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 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 solves the NUM problem we discuss. Our model contains a routing scheme that

allocates users according to a fixed vector whose components

sum to one. The degree of path diversity of the route or path

allocation for a class of network users s, can be measured

in terms of the entropy hs of the probability distribution

defined by the allocation. We discuss two example networks

with a single source and destination.

Treating hs as a parameter, we find 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

4 for TwoLinks and Section 5 for Diamond). Stable equi-
libria 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 3, Figure 5).

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 to

one with a smaller entropy. 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 discussed in reference [13].

We now turn to a description of the organization of the paper. The NUM optimization problem for a general network

is presented in the next section, is followed by a description

of the model of the dynamics of the protocol in time. This

can be found in Section 3. The relationship between the

NUM problem, the dual optimization problem and the resulting model equations is not the main focus of this paper

so we defer discussion of these points until the end of the paper in the appendix. There following the work in references

[9], [13] it is shown that the model equations (6)-(9) implement a solution of the NUM optimization problem stated

in equations (1)-(4). They are specialized to the TwoLinks

topology (see equations in (10)) and the Diamond topology

(equations (15)-(19)). A discussion of how the aggregate

utility varies as a function of the parameter hs for these two

topologies can be found in Section 4.1 and 5.1 respectively

and finally the conclusion can be found in Section 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 defined 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 network

operator assigns a bandwidth rate xs and uses a twice differentiable strictly concave utility function Us : [ms, Ms] → R.

Here ms and Ms are lower and upper bounds respectively

on the bandwidth rate. Us(xs) measures the degree of user

satisfaction, network fairness and efficiency for the part of

the network defined by s. Users in a source-destination class

s are assigned a path by edge routers so that the fraction of

users allocated to path or route r is βsr with 0 < βsr ≤ 1.

We can regard βs = {βsr}r∈Rs as a probability distribution

because the fractions sum to 1. Here Rs is the set of all

paths available to s. The distribution is constrained so that

the traffic on any link does not exceed the link capacity.

The optimization problem that our protocol seeks to solve

is therefore:

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 and Rs(l) is the set of

routes used by source s that require link l. 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 matrix β = {βsr}s,r is a set of probability

distributions that define path allocations for each source s.

The constraints in (2) state that all routes that use link l

i.e. routes r in Rs(l) of source s be assigned bandwidth rates

βsrxs so that the total link load does not exceed the capacity

cl. Equation (3) is the usual requirement for probability

distributions and equation (4) places a lower bound on the

degree of randomness for the distribution {βsr} for source s.

Indeed recall that for any allocation βs, the entropy of the

associated probability distribution is:

H(βs) = −

 X

r∈Rs

βsr log βsr!. (5)

Thus equation (4) is just H(βs) ≥ hs. By putting a lower

bound on the entropy we exclude allocations that place a

majority of traffic on too few paths. The remaining path allocations have a greater degree of diversity, insuring some robustness in the system depending on the values of hs. Small

values of hs indicate that the problem is closer to the single

path case since allocations that use fewer paths are admissible but as hs increases we are closer to the equiprobable

case (a version of the multi-path problem) and the resulting

set of feasible allocations reduces to those that have a higher

degree of path diversity and higher average path cost.

In [10] where the idea of random route allocation was

first proposed, the authors introduced an adaptive algorithm

involving non-constant values of hs. Through simulations

they demonstrated the trade-off 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. As is customarily the case in a constrained optimization problem, dual variables- in our case

the link costs, play an integral role in the solution of equations (1)-(4). The solution of the dual problem (if it exists)

can be used to find the solution of NUM. To solve the dual

problem, a projection gradient procedure is employed and

as in previous works, (see references [9], [13]), the dynamics

of the link costs {pl, l = 1, 2, · · · , L} and route allocations

at each iteration step is a model of the behavior of the protocol at each time step. Under appropriate conditions on

Us and the initial link costs (see reference [5]) the iterations

converge to an optimal cost vector p

∗

corresponding to the

optimal values of x

∗

and β

∗

of equations (1)-(4).
Figure 1:

If pl(k) 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

(6)

β

(k)

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

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 =

X

r∈R(s)

β

(k)

sr dr(k) (8)

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 ws and M.

xs(k) = min 

ws

Ds(k)

1/2

, M!(9)

Equations 7 and 8 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. 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 the simple

sample networks we discuss these regions can be determined.

4. TWO LINKS TOPOLOGY

A network consisting of a single source-destination pair of

nodes connected by two links is depicted in Figure 1. The

equations 6 become:

p

(k+1)

1 =

h

p

(k)

1 − h{c1 − β

k

1 xs(k)}

i+

,

(10)

p

(k+1)

2 =

h

p

(k)

1 − h{c2 − β

k

2 xs(k)}

i+

Each link is a path or route so di = pi i = 1, 2.

Assuming c1 > c2, and initial link prices p

(0)

1 < p(0)2

, there

is a critical entropy hT (c) < log 2 given by,

hT (c) = −



c1

c1 + c2

log c1

c1 + c2

+

c2

c1 + c2

log c2

c1 + c2



(11)

with a corresponding critical route distribution,

β

∗

1 =

c1

c1 + c2

, β∗

2 =

c2

c1 + c2

(12)

We say that p

(k)

i ∈ Wi if p

k

i −h{ci−β

(k)

i xs(k)} > 0. Figure 2

shows the behavior of iterates of equations in 10. If R is the

region bounded by the lines L0, the p2 axis, the line L2 and

the line { p |p1 = p2 }, then H = R∩W1∩W2. Lines L0 and

L2 are perpendicular to the line  ̄x

∗ = β∗

1 p1 + β

∗

2 p2. If J =

{p | p = (p1, p2)| p1 < p2, p1 > 0, p2 > 0 }, then it can

be shown ([5]) that iterates of a point p

(0) beginning in the

region H ⊂ J remain in H and converge to an equilibrium

point on the line of points with constant average p value  ̄x

∗

(see Figure 2). We claim in fact that if p

(k−1)

1 < p(k−1)

2

,

the allocations at time k ≥ 1 satisfy, β

(k) = (β

(k)

1

, β(k)

2

) =

β

∗ = (β∗

1 , β∗2 ). To see this note that the implicit equation

(8) forces the entropy of β

k)

to be hT (c). There are only

are only two distributions with that entropy value and the

conditions p

(k−1)

1 < p(k−1)

2

imply that β

(k)

1 > β(k)

2

. Since β

∗

is the unique distribution satisfying the latter condition the

claim is proved. Each equilibrium point (p

∗

1, p∗2) corresponds

to the unique solution (xs∗, β∗) of the optimization problem

when h is sufficiently small with,

x

∗

s =

ws

x ̄

∗

 1

2

(13)

x ̄s

∗ = β∗

1 p

∗

1 + β

∗

2 p

∗

2 (14)

The proof of optimality follows along the same lines as the

proof of Theorem 1 in [9] and uses [1] p. 214.

Orbits starting outside of H either converge to the intersection of the p2 axis with the  ̄x

∗

line or they approach the

line p1 = p2 and fail to converge (see [5]).

In the case where hs < hT (c) we can also conclude that

the route allocation distribution is constant while the iterates are in the region J . This is proved using the same

reasoning as in the case hs = hT (c). Here a point beginning

in J will remain there and converge to a unique point (0, p∗

2)

on the p2 axis. Thus the larger link 1, is saturated, while

link 2 reaches some positive equilibrium price. However the

equilibrium bandwidth xs∗ will be smaller than the value

achieved at hT (c). When hs < hT (c), orbits leave J and

move towards the line {(p1, p2) : p1 = p2 } as k → ∞.

Meanwhile, the solution of the implicit equation γ

k) → ∞

and the corresponding entropy approaches log 2. Thus the

orbit leaves the feasible region and fails to converge.
Figure 2: Iterates of Equation 10 (in brown and

green) for hs = hT (c)

Figure 3: hs-ref is the critical entropy hT (c).

4.1 Utility/ Entropy tradeoff for TwoLinks

For general multipath models the tradeoff between path

diversity and utility is not well understood but introducing

the entropy hs as a measure of path diversity, directly into

our model equations allows us to address the question of

tradeoff in terms of a study of the utility as a function of hs.

For the TwoLinks (and the Diamond) topology the utility

was computed at each time step over a finite time interval.

This was done for each hs over a range of values where the

minimum hs was less than critical value hT (c) and the maximum hs was greater. An example of such a computation can

be seen in Figure 3. As hs increases from 0 the average utility steadily increases and plateaus near the average utility

value at hT (c) and then decreases for increasing hs > hT (c).

Thus (approximately) this graph mirrors the simulations by

Marbukh and Klink [10] of a stochastic model where hs is

adjusted adaptively. Here N is the number of iterations

performed at each hs, and M is the number of hs values.

5. DIAMOND TOPOLOGY

We turn our discussion now to another simple topology

(see Figure 4 ) with 5 links attached to a single source destination pair. As seen in the figure there are 3 routes, using

the links indicated in the figure.

Figure 4: DIAMOND NETWORK

Inspection of the figure leads to the system:

p

(k+1)

1 =

h

p

(k)

1 − h{c1 − (β

(k)

1 + β

(k)

3

)xs(k)}

i+

(15)

p

(k+1)

2 =

h

p

(k)

2 − h{c2 − β

(k)

2 xs(k)}

i+

(16)

p

(k+1)

3 =

h

p

(k)

3 − h{c3 − β

(k)

1 xs(k)}

i+

(17)

p

(k+1)

4 =

h

p

(k)

4 − h{c4 − (β

(k)

2 + β

(k)

3

)xs(k)}

i+

(18)

p

(k+1)

5 =

h

p

(k)

5 − h{c5 − β

(k)

3 xs(k)}

i+

(19)

where as in the previous section, the bandwidth rate is

xs(k) = min(

ws

E[d(k)]

 1

2

, M) , with E[d

(k)

] = P3

r=1 β

k

r d

(k)

r =

P3

r=1 β

(k)

r

P

l

0 ∈r

p

k

l

0



. The route probabilities are defined

by the following equations:

β

(k)

i =

exp 

−γ

(k)

d

(k)

i



Z(k)

i = 1, 2, 3 (20)

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

.

(21)

Here led by the search for strictly interior equilibria of equations (15)-(19) we take

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

As motivation we can think of link 1 and 3 as an input/

output pair while links 2 and 4 are a corresponding input/output pair.

There are only two distributions β = (β1, β2, β3), with

given entropy hs < log 3 , satisfying the condition β1 =
β2. The choices correspond to the inequalities, β1 > β3

or β1 < β3. Furthermore, if we choose initial link prices

p

(0)

l

l = 1...5 that are compatible with equation (22) then

β

(k)

1 = β

(k)

2 k ≥ 1.

Given 1 ≤ i ≤ 5, for any k ≥ 0 we will say that p

(k)

i ∈ Wi if

p

(k+1)

i > 0.

Lemma 1. Suppose the capacities in equations (15)-(19)

satisfy equation (22). 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. The proof is by induction on k.

The conclusion of the lemma thus implies that with appropriate choice of initial link prices there are at most two possible distributions β with a given entropy hs and one can show

that if d

(k)

3 ≥ d

(k)

1 = d

(k)

2

then there is just one. Therefore

as long as iterates remain in the region { p : d1 < d3 },

(β

(k)

1

, β(k)

2

, β(k)

3

) is constant after one time step. In reference

[5] we describe the analytical and computational study of

equations (15)-(19) and find that the algorithm converges

for values hs ≥ hD(c) where hD(c) is

hD(c) = −[

c2

c2 + c3 + c5

log c2

c2 + c3 + c5

+ (23)

c3

c2 + c3 + c5

log c3

c2 + c3 + c5

+

c5

c2 + c3 + c5

log c5

c2 + c3 + c5

]

Using arguments similar to those used for TwoLinks at the

critical value hT (c), we can show at hs = hD(c) there exist

a family of equilibria in the d1, d3 plane that lie along the

line { (d1, d2, d3) : d1 = d2 x ̄

∗ = β∗

1 d1 + β

∗

2 d2 + β

∗

3 d3}.

These points correspond to a unique (x

∗

s, β∗

) solution of the

optimization problem where β

∗

is the route distribution corresponding to the critical entropy hD(c),

β

∗ =



c2

c2 + c3 + c5

,

c3

c2 + c3 + c5

,

c5

c2 + c3 + c5



The proof of optimality as in the TwoLinks case uses the

fact that iterates stay within a region where the route distribution is constant.

Values of hs > hD(c) corresponding to route distributions

β =



νc2

c2 + c3 + c5

,

νc3

c2 + c3 + c5

,

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

c2 + c3 + c5



(24)

for ν < 1 were analyzed and computations were done. We

show that under the hypotheses of Lemma 1 iterates of the

algorithm converge to a unique equilibrium where p

∗

i = 0 1 ≤

i ≤ 4, and p

∗

5 > 0 when hs is the entropy of the distribution

in equation 24. The algorithm fails to converge if ν > 1,

a situation where hs < hD(c). Here orbits approach the

line in the (d1, d3) plane d1 = d3 as k → ∞. Since we

have d

(k)

1 = d

(k)

2

for all k ≥ 1 by Lemma 1, the iterates

Figure 5: DIAMOND Utility vs. entropy

leave the region of feasibility. Thus we see that hD(c) marks

the boundary between convergence and divergence of this

algorithm.

5.1 Utility/Entropy tradeoff for Diamond topology

The variation of utility as a function of hs in the Diamond

topology is illustrated in Figure 5. The average utility over

a finite time interval (defined by the number of iterations N)

was computed for a given value of hs. Again the minimum hs

was less than hD(c) while the maximum value was greater.

Although the average utility decreases for hs ≥ hD(c), the

maximum is not achieved at the critical value. It continues

to increase until the value log 2 is reached. A plot of β3,

the fraction of traffic allocated to route 3 as a function of

hs shows that β3 decreases as hs decreases until β3 = 0 at

log 2. We find this to be the case even when link 5 is not

an obvious bottleneck e.g. when c5 > c2 = c3. Thus the

route with the cross link 5 is eliminated and the network is

reduced effectively to TwoLinks. Numerically we find that

we cannot even iterate long enough to calculate the average

utility when hs < log 2.

6. CONCLUSION

We presented a network utility maximization problem that

is equivalent to a convex optimization problem that incorporates a measure of path diversity in the assignment of paths

to users transmitting between two locations in the network.

Within the framework of our model it is possible to examine the tradeoffs between utility maximization that could be

offered by single path routing on the one hand and robustness on the other, by introducing an entropy parameter hs

directly into the optimization problem (and thus the model

equations). One can then study the utility as a function

of hs. In this paper, the proposed method is demonstrated

for two example topologies TwoLinks and Diamond. Thinking of hs = 0 as representing a single path scheme while

hs = log(number of routes) represents the most robust

multipath scheme, we see that our results suggest that the

degree to which a network can approach single path routing is limited by the link capacities and its topology. In

each case, there is a critical value hs, hT (c) in the case of

TwoLinks and hD(c) for Diamond, so that model equations
diverged for hs less than the critical value. On the other

hand we presented sufficient conditions for the model equations to converge to equilibria that correspond to solutions

of the optimization problem. The extension of this methodology to more complex networks is needed as well as the consideration of other approaches e.g. subgradient algorithms.

It is possible that the problem of divergence could be addressed in this way.

APPENDIX

A. DERIVATION OF THE MODEL

The NUM problem in equations (1)-(4) is not convex in

(x, β) but through a change a variables (x, β) 7→ (x, y) it can

be transformed to one. The new problem is:

max

x,y

X

s

Us(xs) (25)

X

s

X

r∈Rs(l)

ysr ≤ cl (26)

xs =

X

r∈Rs

ysr, ysr ≥ 0 (27)

−

X

r∈Rs

ysr

xs

log ysr

xs

≥ hs (28)

This is a convex program because the functions in equations

( 25)-(28) are clearly concave. If we assume the conditions

X

s

0

ms

0 < cl

hold for each l, where the summation is over all sourcedestination pairs s

0

that use link l, then there is a Slater

point ([12]) and the Slater constraint qualification is satisfied. Thus the problem in equations ( 25)-(28) 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)−λ

2

s(xs−

X

r∈Rs

ysr)]+XL

l=1

plcl

where λ = [λ

1

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

constraints in equations (27) and (28). To obtain solutions

x, y we consider the solutions of the problem;

max

x,y

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

x

max

y

L(x, y, λ, p)

where maximization is first performed in y with x and p

held fixed. 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 (29)

xs =

X

r∈Rs

ysr, ysr ≥ 0

−

X

r∈Rs

ysr

xs

log( ysr

xs

) ≥ hs

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

∗

to (29) exists if and only if there

is a λ

∗

that satisfies the KKT conditions ([12] p.182,183).

Reintroducing βsr =

ysr

xs

where βsr is independent of xs, we

obtain the following form of the optimal solution of (29) for

each fixed xs and p.

βsr =

exp(−γ ∗ dr)

Zs

(30)

where

Zs =

X

r∈Rs

exp(−γ ∗ dr), dr =

X

l∈r

pl

and γ =

1

λ2

s

is the solution of the implicit equation,

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

X

r∈Rs

βsrdr (31)

Recognizing that equations (29) 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 equation

(31). 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 (30) and (31), β

∗

sr. Then we have y

∗

sr = xsβ

∗

sr. The

{y

∗

sr : r = 1, · · · Rs} are unique since for each s, (31) 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 equation (29) for fixed x and p. It can

be shown that 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 (32)

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 infinite (convex) set (p.

81 [2]). Applying the same reasoning to L we can conclude

that the dual function

Q(p) = max

x

L(x, p) = max

x

max

y

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

is convex in p. The remainder of this derivation follows the

work in references [9] and [13]. First the dual problem for p

is formulated as:

min

p:pl≥0

Q(p) (34)

If Λ is differentiable at p, Danskin’s theorem [1] applied to

L implies the differentiability of Q. Indeed the unique maximizing  ̄x and y = xβˆ∗ are differentiable in p and λ.This

can be seen in the case of βˆ by using the necessary optimality condition ∂L

∂βsr

= 0. At  ̄x, either  ̄xs(p) = Ms or

U

0

s(  ̄xs)(p)) = Λs(p). If  ̄xs(p) < Ms, then a condition introduced in [9], U

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

with the differentiability of Λs with respect to p and λ, imply that  ̄xs is differentiable and thus L( ̄x, y∗

, λ, p) is differentiable. The condition that Λ be differentiable at p holds

we conjecture for values of p that lie in a convex subset.

The exact nature of the subset depends on the existence of

a finite positive root of equation (31). We have determined

the region for sample problems discussed in this paper. In

general however we do not expect Q to be everywhere differentiable. However when it is differentiable our interest lies
in understanding the dynamics of the following equation for

solving the optimization problem in equation (34):

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





+

(35)

l = 1 · · · NL

The equations (35) are supplemented by the relations coming from the optimality conditions.

β

(k)

sr =

exp −γ

(k)

s (

P

l∈r

pl)



Z(γ

(k)

s )

(36)

x

(k)

s = min(

ws

E[d]

 1

α

, M) , E[d] = X

r∈Rs

β

(k)

sr (

X

l

0 ∈r

p

(k)

l

0 )

(37)

where γ

(k)

s is the solution of equation (31) using β

(k)

sr and

Z(γ

(k)

s ) is defined analogously to Z(s). Equation (31) effectively insures that at each time step k the route distribution

n

β

(k)

sr : r ∈ Rs

o

has entropy hs for every s.

B. REFERENCES

[1] D.P. Bertsekas, J. N.Tsitsiklis ”Parallel and

Distributed Computation: Numerical Methods”,

Prentice Hall, Englewood Cliffs, 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 Traffic Engineering:

Optimization of Congestion Control and Routing”

IEEE Journal on Selected Areas in Communications,

Vol. 25, No. 5, pp.868-880, 2007.

[5] F.Hunt, V. Marbukh ”A Model of Joint Congestion

Control Through Random Assignment of Paths”,

NIST Internal Report, 2009.

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

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

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

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

[10] V. Marbukh, S. Klink ”Decentralized Control of

Large Scale Networks as a Game with Local

Interactions:Cross Layer TCP/IP Optimization”

ValueTools07 .

[11] Y. Matsumoto ”An Introduction to Morse Theory”

Translations of Mathematical Monographs, Vol. 208,

American Mathematical Society, 2002.

[12] A. Peressini, F.Sullivan, J.Uhl ”The Mathematics

of Nonlinear Programming”, Springer Verlag, New

York, N.Y. , 1988.

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