Dynamic Routing and Congestion Control Through Random

Assignment of Routes

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

May 22, 2008

Abstract

We introduce an algorithm for maximizing utility

through congestion control and random allocation of

routes to users. The allocation is defined by a probability

distribution whose degree of randomness as measured

by its entropy, is controlled. We seek to use the entropy

to modulate between the two extremes of path specification; minimum cost path selection on one end and

equiprobable path allocation on the other. We explore

the trade-off between stability and utility in two sample

topologies.

Keywords:Cross-Layer,TCP/IP algorithms,

1 INTRODUCTION

Recent progress in the development of protocols that maximize utility through joint congestion control and routing

has uncovered a number of interesting questions regarding the algorithms that represent these protocols. Building on earlier work (see [3] and [2] for references) Kelly

and co-workers examined the stability of global optimization algorithms that represent TCP/AQM protocols with

routing. In [2] a fluid flow model of a multipath route

allocation policy was analyzed. Here a number of routes

connecting a source and destination may be available and

the goal is to assign traffic and bandwidth rates along

routes so that network utility is maximized. If one assumes there is no time delay associated with communication between source and link (resource) layers, global

stability of equilbria of the model in [3] was proved and

the global stability of equilibria associated with a more

constrained optimization model were proved in [2].

Single path problems are on the other end of the spectrum of path specification. Here multiple paths linking

source and destination are available as in the multipath

case, but only a single path is selected, for example a

path with minimum cost. Wang et al [6] obtained sufficient conditions for the existence of a solution to a single

path utility maximization problem. One of their main

results states that when there is no duality gap, optimal

solutions of the utility maximization problem are equilibrium points of their TCP/AQM-IP algorithm (see [1] for

a discussion of this point). Here the congestion prices are

used as link costs. However the existence of an equilibrium is not guaranteed. Indeed when a duality gap exists,

there is no equilibrium, moreover if it does exist it may be

unstable. They propose adding a static component to the

link cost in order to stabilize it. Wang et al also establish

that there is no duality gap for the multipath problem.

Since the utility of the optimal solutions of the latter are

an upper bound to the single path utility equilibrium we

can ask the following question. Can the requirement for

a single path of minimum cost be relaxed so that one can

achieve stability and larger utility on the one hand and

yet not be so relaxed as the multipath problem where (implicitly) one would have to identify all the paths joining

a source and destination with equal and minimum cost?

This paper presents a model that attempts to address this

question.

In what follows we present an optimization problem

for congestion control and route allocation where users

are randomly assigned routes according to a probability

distribution whose degree of randomness is controlled by

a fixed parameter hs, the entropy of the distribution for

a source s. The case hs = 0 corresponds to the single

1
path allocation problem while the maximum value hs =

log(# of routes for s) corresponds to the problem of

allocation among equiprobable routes.

2 MODEL

The optimization problem that our protocol seeks to solve

is:

max

xˆ≥0

max

βˆ≥0

X

s

Us(xs) (1)

X

s

X

r∈Rs(l)

βsrxs ≤ cl (2)

∀s βsr ≥ 0,

X

r∈Rs

βsr = 1 (3)

−

X

r∈Rs

βsr log βsr ≤ hs (4)

where s is the index of the source-destination pair, Us is

the corresponding utility function, ˆx = {xs} is the vector of source rates, and βˆ = {βsr} is the matrix whose

rows are the route probability distributions for source s.

The constraints (2) require 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. Finally, (3) is the usual requirement for probability distributions and (4) places an upper bound on the

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

s. Small values of hs mean 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 [4] 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 [4] and [6], the dual variables are link costs changing in response to congestion.

The route allocation distributions follow dynamics that

minimize the average route cost and this plays a role in

the onset of instability when hs is small. In [5] where the

idea of random route allocation was first proposed, the

authors introduced an adaptive algorithm involving nonconstant 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. We find similar results

in our algorithm.

3 Summary of Results

We give a brief summary of some results for the first

sample topology, a network consisting of a single sourcedestination pair of nodes connected by two links. In

this situation each link is also a route. Given capacities

c1 > c2 where c1 and c2 are the capacities of link 1 and link

2 respectively, suppose for some hs we have c1

c2

=

β

(hs)

1

β

(hs)

2

.

Here β

(hs)

1 and β

(hs)

2

, the proportion of traffic allocated

to links 1 and 2 respectively define a probability distribution with entropy hs. Note that when hs < log(2)

is fixed, there are two such distributions.There exists a

steady state (x

∗

s, p∗

1, p∗

2, β(hs)

1

, β(hs)

2

). Here x

∗

s is the source

rate, {p

∗

i } are the link costs for i = 1, 2. We give sufficient

conditions for this steady state to be an optimal solution

of (1)-(4) and sufficient conditions for its stability. For

fixed values of c1, c2, we computed the time averaged utility and found the maximum to occur near hs for which

the above mentioned steady state exists. For smaller values of hs we see instability of our algorithm in the sense of

sustained periodic behavior, which could be an analogue

of the route flapping phenomenon observed in single path

allocation protocols and mentioned in [2],[5] and [6].

References

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

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

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

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

[5] V. Marbukh, S. Klink ”Decentralized Control

of Large Scale Networks as a Game with Local

Interactions:Cross Layer TCP/IP Optimization”

ValueTools07.

[6] J.Wang, L. Li, S.H. Low, J.C.Doyle ”CrossLayer Optimization in TCP/IP networks” IEEE

Transactions on Networking, Vol. 13, No. 3, pp. 568-

582, 2005.

2