Decentralized Control of Large-Scale Networks as a Game 

with Local Interactions: Cross-layer TCP/IP Optimization 

Vladimir Marbukh 

National Institute of Standards and Technology 

100 Bureau Drive, Stop 8920, 

Gaithersburg, MD 20899-8920, USA 

Tel: 1 301 975 2235 

E-mail: marbukh@nist.gov

Stephan Klink 

National Institute of Standards and Technology 

100 Bureau Drive 

Gaithersburg, MD 20899-8920, USA 

Tel: 1 301 975 2235 

E-mail: klink@gmx.net

ABSTRACT

Developing optimized distributed protocols for large-scale 

networks is a challenging problem due to scalability and stability 

concerns. Scalability concerns can be naturally addressed by 

interpreting distributed protocols as a non-cooperative game of 

local protocol components attempting to maximize their 

individual utilities. One of the difficulties in implementing this 

approach is developing adaptive algorithms capable of learning of 

the expected utilities and adjusting the corresponding control 

actions for the purpose of approaching the solution to the 

corresponding game, and thus optimization of the global system 

performance. It is known that the best response by each 

component to its expected utility may result in unstable behavior 

and deterioration of the overall performance. On an example of 

cross-layer optimization of a TCP/IP network, this paper 

discusses the possibility of avoiding these undesirable effects by 

allowing the control actions occasionally deviate from their best 

response values. Using simulations, the paper suggests that (a) 

sufficient level of randomness in route selection improves the 

network performance by eliminating the route flapping instability, 

(b) the optimal level of randomness keeps the network within the 

stability region in close proximity to the border of this region, and 

(c) it may be possible to optimize the network performance by 

adjusting the level of randomness. 

Categories and Subject Descriptors

C.4 [Performance of Systems]: – modeling techniques, 

performance attributes, reliability, availability, and serviceability. 

General Terms

Algorithms, Management, Performance, Design, Reliability, 

Theory. 

Keywords

Distributed protocols, optimization, learning algorithms, game 

theory, TCP/IP, OSPF, randomized routing, routing stability. 

1. INTRODUCTION 

Recent technological advances made implementation of 

complicated adaptive network management algorithms 

technologically feasible [1]. Adaptive network management 

algorithms extract essential information from real-time or near 

real-time measurements and produce the appropriate responses. 

Developing optimized distributed protocols for large-scale, selfmanaged systems is a challenging problem due to scalability and 

stability concerns. Scalability concern can be naturally addressed 

by interpreting distributed protocols as a non-cooperative game 

where each component is modeled as a player attempting to 

maximize its own utility [2]. Success of this game theoretic 

approach, however, requires solving two major problems. The 

first problem is identifying of the “optimal” individual utilities 

through resource pricing so that (hopefully unique) Nash 

equilibrium in this game optimizes the overall network 

performance. Since typically such “optimal” individual utilities 

are themselves solution to some global optimization problem, the 

second problem is developing adaptive algorithms capable of 

learning of the expected utilities and adjusting the corresponding 

control actions for the purpose of approaching the solution to the 

corresponding game, and thus optimization of the global system 

performance. Distributed, adaptive algorithms attempt to 

approach the global optimum by learning evolution, when each 

player makes its decisions based on the history of its own 

decisions and responses by other players [2]. Typically, if this 

evolutionary process converges, the corresponding steady state 

also represents the Nash solution to the corresponding game and 

thus optimizes the overall steady-state performance. The 

convergence, however, is not guaranteed even in a rather 

exception case of a pure Nash equilibrium in the corresponding 

game, let alone a common case of a mixed Nash equilibrium. 

A classical networking example of such instability is route 

flapping in a situation of equal cost multipath [3]. It is known [4] 

that under certain conditions the necessary and sufficient 

condition for the routing algorithm to achieve optimal load 

balancing is to select minimum cost route, where the link costs 

are increasing and convex functions of the link loads. However, 

adaptive version of this routing, which estimates the average link 

loads, and then routes the entire flow on the minimum cost path, 

increases load on the minimum cost route until flow admission 

strategy takes over or at least two feasible routes have 

approximately the same cost. After that the routing decisions 

become very sensitive to the route costs causing route flapping 

instability, which significantly increases the amount of signaling 

traffic and may cause deterioration in the network performance 

[5]. Conventional approach to ensuring convergence to the 

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, or republish, to post on servers or to redistribute to lists, 

requires prior specific permission and/or a fee. 

Valuetools’07, October 23–25, 2007, Nantes, France. 

Copyright 2007 ICST 978-963-9799-00-4 
optimum is switching only a small (infinitesimal) portion of 

traffic on the minimum cost route [6]. Except for MPLS, 

currently existing routing algorithms, such as Open Shortest Path 

First (OSPF) and its Traffic Engineering (TE) extensions require 

flow level granularity in load balancing, i.e., all packets of the 

same flow are to be routed on the same minimum cost path to 

avoid out of order arrivals [3]. 

Practical protocol implementations usually offer some 

phenomenological mechanisms for alleviating instability 

problems. For example, OSPF routing protocol assumes uniform 

traffic split among multiple equal minimum cost routes in order to 

achieve better load balancing and allows minimum period of 30 

seconds for the link cost updates [3]. New technological 

advances allow for more flexibility in tuning the protocols to 

specific conditions. Taking advantage of these emerging 

capabilities requires better understanding of various trade-offs 

involved in protocol design, including stability/performance 

trade-off. Possibility of stabilization of a minimum cost routing 

by adding the load independent component to link costs has been 

discussed in [5], [7]-[8]. The main conclusion is that stability 

generally requires the relative weight on the dynamic (load 

sensitive) component of the link cost to be sufficiently small. 

Increase of the dynamic component improves the network 

performance until the performance peaks and then deteriorates. 

Deterioration in the network performance occurs close to the 

point of loosing stability. 

Recently, IP community expressed interest in relaxing OSPF 

requirement to split load equally among feasible routes of 

minimum cost in a situation of equal cost multi-path [9]-[10]. 

Paper [9] has demonstrated that any (including optimal) routing 

can be viewed as a minimum cost routing based on some link 

costs assuming, however, the ability to split traffic arbitrarily 

among multiple feasible minimum cost routes. Paper [9] has 

argued that technologically such ability may be achieved in IP 

network running OSPF or IS-IS protocols by manipulating the set 

of next hops for route prefixes. Due to inherent uncertainties in 

the external demands and network conditions, e.g., due to link 

failures, it is natural to attempt to determine the set of optimal, 

i.e., minimum cost, routes and the optimal load split among these 

routes adaptively, based on the on-line measurements. This paper 

is a preliminary attempt to identify approach to this problem in a 

context of cross-layer optimization of a TCP/IP network. The 

paper proposes a scheme allowing flows to be routed on “almost” 

minimum cost paths. The load split among “almost” minimum 

cost routes is optimized by sending more flows with the same 

source-destination on the paths with lower estimated costs. 

The proposed scheme allowing routing decisions occasionally 

deviate from their optimal (minimum estimated cost) route 

selection has natural interpretation as a learning or evolutionary 

algorithm. One may expect that adding “noise” to the system 

dynamics may stabilize the system in some neighborhood of the 

optimal state, trading steady-state performance under quasistationary conditions for robustness under unexpectedly changing 

conditions. The question we are most interested in this paper is 

stabilization and optimization of the network by such 

randomization. Note the difference between this view and view 

accepted in genetic algorithms, where algorithm mutation is 

basically a discovery mechanism. 

The paper considers a TCP/IP network where TCP-AQM 

flow control mechanism is assumed to maximize the aggregate 

utility [5]. We assume that a single route is selected for each 

arriving flow, and that TCP-AQM instantaneously maximizes the 

aggregate utility. These assumptions reflect flow level 

granularity in load allocation and much faster TCP-AQM 

convergence then a flow arrival/departure process. Section 2 

abstracts TCP operations as an aggregate utility maximization 

problem for a given set of flows. Section 3 characterizes the 

optimal flow level granularity routing and introduces a noncooperative game * G with a Nash equilibrium representing the 

optimal routing. Learning algorithm attempting to approach this 

equilibrium by the best responses to the expected utility 

represents the minimum cost routing and may exhibit route 

flapping instability causing sharp deterioration in the network 

performance. Section 4 describes a minimum average cost 

routing representing the stochastic fictitious play in the 

corresponding game * G . Section 5 describes a model for the 

network dynamics with the minimum average cost routing and 

random number of flows in progress due to random flow 

arrivals/departures. Section 6 reports simulation results indicating 

that (a) sufficient level of randomness improves the network 

performance by eliminating the route flapping instability, (b) the 

optimal level of randomness keeps the network within the 

stability region in close proximity to the border of this region, and 

(7) it may be possible to adaptively optimize the level of 

randomness. Finally, conclusion summarizes the results and 

outlines direction for future research. 

2. MODEL 

A network is comprised of a set of nodes n ∈ N connected by 

bi-directional links l ∈ L with finite capacities l c . Traffic with 

source-destination s ∈ S can be routed over feasible acyclic 

paths Rs r ∈ . We assume that there are M s = dim Ks

users Ks k ∈ generating demand with source-destination s . 

Each user Ks k ∈ has utility function u (x) s of transmitting at 

a rate x ≥ 0 , where functions u (x) s are strictly increasing and 

continuous. 

It is known [11], [5], that TCP-AQM results in the bandwidth 

allocation maximizing the aggregate utility. Note that for TCP 

utility functions u (x) s are typically strictly concave. Assuming 

that user Ks k ∈ traffic can be arbitrarily split among feasible 

routes Rs r ∈ , the aggregate utility maximization problem is as 

follows: 

 ∑∑ ∑ ∈ ∈ ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

s K k R r

s kr X Y s s

u x ,max (1) 

subject to the capacity constraints. 

 l l y ≤ c (2) 

and flow non-negativity constraints 

 xkr ≥ 0 (3) 

where kr x is the user Ks k ∈ rate on a feasible route Rs r ∈ , 

and 
 ∑∑∑ ∈ ∈

= s K k R r

l kr

s s

y x (4) 

is the total link l load. 

 Sometimes it is more convenient (and also relevant [11]) to 

replace capacity constraints (2) with penalty function in the 

optimized criterion. Consider the following optimization problem 

 W

X ,Y

max (5) 

subject to constraints (3)-(4), where the social welfare is 

 ∑∑ ∑ −∑ ( ) ⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ = ∈ ∈ l

l l

s K k R r

s kr W u x f y

s s

 (6) 

and penalty functions l f are monotonously increasing and 

convex: 

 d ( y) = df ( y) dy > 0 l

def

l , (7) 

 ( ) ( ) 0 2 2 d′ y = d fl y dy >

def

l , (8) 

∀y ∈[0,∞). 

In this paper we assume that the entire user Ks k ∈ flow 

 ∑

∈

= Rs r

kr

def

k x x (9) 

is routed on a single path sk r . It is straightforward to modify 

optimization problems (1)-(4) and (5)-(6) to account for this 

requirement by adding the corresponding integer constraints 

 

⎩

⎨

⎧

≠

= =

sk

k sk

kr if r r

x if r r

x

0 (10) 

Further in the paper we always assume that numbers of users with 

the same source-destinations are large: 

 M s >> 1, ∀s ∈ S (11) 

In this practically important case solution to the corresponding 

discrete optimization problem can be approximated based on the 

solution to the following continuous optimization problem: 

max (12) : ⎪⎭

⎪

⎬

⎫

⎪⎩

⎪

⎨

⎧

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛ −⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

∑ ∑ ∑∑ ∑ ∈ ls R r l∈r⊆

l s sr

s R r

s s sr Z s s

M u z f M z

subject to constraints zsr ≥ 0 . If solution to optimization 

problem (12) is known: ( ) sr Z = z , the optimal flow-level 

granularity routing algorithm allocates 

 M sr ≈ α srM s (13) 

users s ∈ S on a route Rs r ∈ , where 

 ∑′∈

= ′

Rs r

sr sr sr α z z (14) 

In a case when user utilities u (x) s are concave, optimization 

problems (1)-(4) and (3)-(6) are convex and thus they have unique 

optimal solution * X and no other locally optimal solution exists. 

3. MINIMUM COST ROUTING 

A necessary condition for a vector ( ) sr Z = z to be a solution 

to optimization problem (12) can be characterized in terms of the 

link costs (7) as follows [5]-[6]. A set of path flows is optimal if 

the flows are positive on feasible paths of minimum cost, where 

the cost of a path is a sum of the costs of the path’s links: 

 ∑

∈

=

l r

dr dl (15) 

and the link costs (7) are calculated at the point ( ) sr Z = z . 

These necessary conditions are also sufficient if utilities u (x) s

are concave and thus optimization problem (12) is convex. The 

characterization of the optimal load allocation in terms of the 

minimum cost routing implies that at the optimum the paths along 

which the load with the same source-destination s ∈ S is split 

must have the same cost, which is the minimum cost over all 

feasible paths with the same source-destination s (a situation of 

equal cost multi-path). 

Given route costs r d , consider individual optimization 

problem for a user Ks k ∈

 ( , ; ) ~ maxmax

0

U r x d s r R x ∈ s ≥ (16) 

where the individual net utility is 

 s s r U (r, x;d) = u (x) − xd ~ (17) 

Optimization problem (16)-(17) can be rewritten as follows: 

 { r} r R s x

u x x d ≥ ∈ smax ( ) − min

0

 (18) 

with internal optimization having a form of a minimum cost 

routing: 

 r r R

d ∈ smin (19) 

In absence of the equal cost multi-path situation solving 

individual optimization problem (16)-(17) by each user 

k ∈ Ks , s ∈ S independently from each other results in the 

optimal load allocation if the link cost dl are “right”. This 

simple observation suggests possibility of a distributed algorithm 

for optimization of the overall network performance. However, 

achieving this goal requires first, identifying the “right” link costs, 

an, second, dealing with equal cost multi-path situation when 

minimum cost route selection (19) is indifferent between two or 

more minimum cost routes. 

Solving these problems requires accounting for the 

“interactions” among different users (flows) due to dependency of 

the actual route costs in each user individual net utility (17) not 

only on the routing and flow control decisions made by this user, 

but also on the routing and flow control decisions made by other 

users. Accounting for these interdependencies naturally leads to 

the following game theoretic interpretation of the optimal load 

allocation problem. Consider a non-cooperative game G of all 

users Ks k ∈ , s ∈ S . User k attempts to select its route 

k Rs r ∈ and rate ∈[0,∞) k x in order to maximize its utility 

 ( , ; , ) ( ) ( , ) s k k k k s k k r k k U r x r x u x x d r x − − = − k − − (20) 
where vector k r− includes routes and vector k x− includes rates 

for all users except user k . Note that expression (20) assumes 

(11). Solution to the user optimization problem 

 maxmax ( , ; , )

0 s k k k k r R x

U r x r x k s k

− − ∈ ≥

 (21) 

depends on the decisions by other users. Note that this game 

theoretic formulation assumes that instantaneous information on 

the link costs is available to the users and users can 

instantaneously react to this information by adjusting their routes 

and transmission rates. In practical applications, the frequency of 

link cost updates is upper bounded, e.g., for OSPF routing 

protocol the shortest period between link costs updates is 30 

seconds [3]. Section 5 accounts for finite frequency of link cost 

updates in the dynamic model of route selection. 

Due to much faster TCP-AQM convergence than frequency 

of routing updates we assume that given routes for all users, rates 

*

k k x = x maximize the criterion (6). This can be justified when 

user utility functions u (x) s are typically strictly concave and 

thus game G in rates ( ) k x for given routes ( ) k r have unique 

pure equilibrium ( )

*

k x , where k s Ks x = z , k ∈ * * and ( )

*

s z

is the unique solution to the following optimization problem 

⎪⎭

⎪

⎬

⎫

⎪⎩

⎪

⎨

⎧

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

∑ −∑∑ ∑∈ ⊆ ≥ ls R r l r

l s s sr

s

s s s x s s

M u z f M z : 0max ( ) α (22) 

for given portions of flows routed on different feasible paths 

 ∑ ∑ ∑ ∈ ∈ ∈

=

s Rs s r K k

k

k K

sr k α δ (r ,r) δ (r ,r) (23) 

where δ (i, j) = 1 if i = j and δ (i, j) = 0 otherwise. 

Under this assumption routing and flow control game G

simplifies into routing game * G where each user Ks k ∈

selects its route k r in an attempt to minimize the route cost: 

 min ( ) *

r k r R

d r k s

− ∈ (24) 

where the route costs are calculated assuming that user rates have 

already reached the optimum *

k k x = x − : 

 ( ) ( , ) * *

r k r k k d r d r x − = − − (25) 

Importance of the game * G follows from the following two 

observations: (a) minimum cost routing (19) can be viewed as the 

best user response in the game * G , where r r d d

~ = are the 

observed route costs, (b) there is a close relation between Nash 

equilibrium strategies in the game * G and solution to 

optimization problem (12). It can be shown that each local 

maximum in (12) corresponds to Nash equilibrium in the game 

* G , where user Ks k ∈ selects strategy k Rs r ∈ with 

probability α sr , given by (14). A local solution to (12), which 

sends entire traffic with the same source-destination s on a 

single feasible route s Rs r ∈* , corresponds to pure equilibrium 

strategy *

k s r = r for users Ks k ∈ in the game * G . Solution 

to (12), which splits traffic with the same source-destination s

among feasible routes Rs r ∈ , corresponds to mixed strategy for 

users Ks k ∈ in the game * G : select route Rs r ∈ with 

probability α sr , given by (14). 

4. MINIMUM AVERAGE COST ROUTING 

The following minimum average cost routing reduces sensitivity 

of the routing decisions to the instantaneous link utilization by 

randomizing routing decisions. Given the observed route costs 

dr dr

~ = , each user s selects a route Rs r ∈ with probability 

β sr , where distribution ( , ) s sr Rs β = β r ∈ minimizes the 

average route cost 

 ∑

∈

=

k s r R

s sr r D β d

β

min (26) 

subject to conditions sr sr Rs ∑ β = 1, β ≥ 0, r ∈ and 

the following condition 

 s

r R

sr sr h

k

− ∑ ≥ ∈β log β (27) 

requiring a certain level of randomness in the route selection 

measured by the entropy of this selection hs . 

It is known [12] that solution to (26)-(27) is as follows 

 

⎩

⎨

⎧

∉

∈ =

−

s

s

A d

sr if r R

e if r R s r

0

γ

β (28) 

where 

 ∑

∈

− = −

s

r

r R

d

s A e γ log (29) 

and s γ = γ is the unique solution to equation 

 − As + Ds = hs γ (30) 

The average route cost (24) can be expressed as follows 

 D dA γ dγ s s = ( ) (31) 

It is easy to verify that a case hs = 0 or, equivalently, 

γ s = ∞ , corresponds to the minimum cost routing selection, 

and that a case log(dim ) hs = Rs or, equivalently γ s = 0 , 

corresponds to the equal flow split among dim Rs feasible 

routes Rs r ∈ . Figure 1 sketches the probability β1 of route 

1r selection as a function of the difference in the route costs 

2 1 d − d in a case of two feasible routes: { , } Rs = d1 d2 . 

Note, that procedure (28)-(30) can be easily generalized to 

include routing only over a subset of “almost” minimum cost 
feasible routes Rs Rs r ∈ ⊆* , e.g., routes having “sufficiently” 

low cost. 

Fig. 1. Probability of route 1r selection 

 (0 ) = γ 0 < γ 1 < γ 2 < γ ∞ = ∞ . 

A minimum average cost route selection with positive entropy 

h > 0, or equivalently finite parameter γ < ∞, reduces the 

overall system performance measured by the criterion (6), 

comparatively to a case of the minimum cost routing with 

h = 0, or equivalently γ = ∞ , assuming that this minimum 

cost routing is stable. For small entropy h > 0, or equivalently 

large parameter γ < ∞, this loss in performance can be 

estimated as follows: 

 − ≈ ∑ ( ) − s

s s s

opt W W a D D min (32) 

where the average and the minimum route costs for a user 

Ks k ∈ are respectively Ds and 

 sr r R

Ds d ∈ s= min min (33) 

and as > 0 are some constants. Expression (32) suggests 

minimum cost route selection (19), for which min Ds = Ds . 

However, minimum cost routing may result in unstable 

behavior, which typically leads to deterioration on the network 

performance and undesirable transient effects. Stability 

requirements impose low limit on the average cost of a selected 

route (see Section 6 of the paper). Figure 2 sketches selection of 

the optimal operating point ( ) Ds subject to the stability 

constraints in a case of two source-destinations S = {1,2}. The 

shape of the stability region can be obtained by stability analysis 

of the presented in the next section network dynamic equations. 

In this paper we only conjecture that this stability region is 

convex in the average route costs. 

Fig. 2. Optimal operating point 

5. DYNAMICS AND LEARNING 

Consider the following model of TCP/IP operation. Link costs 

are updated and routing decisions are made at moments 

t = i , i = 0,1,2,.. i τ . Flows arriving during time interval 

[ , ) ∈ i i+1 t t t are routed based on the link costs at the moment 

i t = t , while “fast” TCP-AQM flow control keeps the 

transmission rates of all flows at the optimal levels all time. 

Thus, the number of flows Ks k ∈ routed on a path Rs r ∈ at 

step i +1 is 

⎩

⎨

⎧

∉

∈

+ =

−

s

s

A i d i

s

sr if r R

M i e if r R

M i s r

0

( ) ( 1)

( ) γ ( )

 (34) 

where the total number of flows Ks k ∈ in the system at step i

is M (i) s , constant 

 ∑

∈

− = −

s

r

r R

d i

s A i e ( ) ( ) log γ , (35) 

(i) s γ = γ is the unique solution to equation 

 A ( ) d h (i) s

r R

s sr r

s

− + ∑ = ∈γ γ β , (36) 

route r cost is 

 ∑

∈

=

l r

r l d (i) d (i), (37) 

link l cost is 

 [ ] ( ) ( ) ( ) l l y y i l

d i df y dy = = , (38) 

link l load at step i is 

 ∑ ∑

∈

= s R r

l sr r

s

y (i) M (i)x (i) , (39) 

and the rate of a flow Ks k ∈ is 

 ( ) argmax{ } ( ) ( )

0

x i u x xd i s r x r = − ≥

 (40) 

Note that in a case of file transfer, with Poisson flow arrivals 

and exponentially distributed file sizes, vector 

0 γ 0 =

γ ∞ = ∞

1 γ 2 γ

0 γ 0 =

γ ∞ = ∞

1 γ 2 γ

β1

2 1 0 d − d

1 2

1

Stability region

D 1

D 2

min D 1

min D 2

opt D 1

opt D 2
( ) M sr (i) :r ∈ Rs ,s ∈ S forms a Markov chain for 

i = 0,1,2,.. A case of a fixed set of flows can be obtained by 

assuming the total number of flows Ks k ∈ in the system is 

fixed M s (i) = M s , s ∈ S . In a case of a large numbers of 

flows in progress (11), zero order approximation of evolution of 

Markov chain ( ) M sr (i) :r ∈ Rs ,s ∈ S is described by a 

closed system of deterministic “averaged” equations for the 

vector of averages ( ) E[M sr (i)]:r ∈ Rs ,s ∈ S . In a case 

when optimization problem (12) has a solution, which does not 

split demand with the same source-destination among multiple 

feasible routes, this optimum is an equilibrium for the averaged 

system. As it has been shown in [5], even in this case, the 

equilibrium may be unstable for the minimum cost routing (34)-

(40) with h (i) ≡ 0 s , or equivalently, γ s (i) ≡ ∞ , 

s ∈ S, i = 0,1,2,... This “route flapping instability” is 

typical in a general case when optimization problem (12) has a 

solution, which splits demand with the same source-destination 

among multiple feasible routes. The instability can be prevented 

by reducing sensitivity of the link costs to the link utilization. 

Paper [5] has considered such a reduction by adding a static 

component to the link costs in a case when optimization problem 

(12) has a solution, which does not split demand with the same 

source-destination among multiple feasible routes. 

We propose reducing sensitivity of the link costs to the link 

utilization with minimum average cost routing (34)-(36) by 

controlling entropies h (i) s , or equivalently, parameters (i) s γ , 

for s ∈ S, i = 0,1,2,.. in a general case when optimization 

problem (12) has a solution, which splits demand with the same 

source-destination among multiple feasible routes. Game 

theoretic interpretation offers important insights into this problem. 

A minimum average cost routing (34)-(36) represents a smooth 

(logistic) fictitious play [2] in the game * G allowing one to 

leverage relevant results on the learning in games for distributed 

protocol optimization. For example, known results [2] obtained 

by application of stochastic approximation to learning algorithms 

suggest that randomized routing (34)-(36) with large γ s → ∞

and link costs averaged over a large number of link cost update 

cycles results in load allocation close to the optimal. 

Note, that the game theoretic interpretation of the minimum 

average cost routing algorithm suggests other rationales for 

randomization of the routing decisions besides elimination 

instability, such as unavoidable uncertainties in the operating 

environment, such as link failures, and “protection” against 

malicious attempts to manipulate the link cost values by an 

adversary/adversaries [2], [13]-[14]. Also note that the minimum 

average cost routing can be interpreted as an evolutionary 

algorithm, where attempt to minimize the route cost by each user 

Ks k ∈ represents selection while randomization of the routing 

decisions represents mutations. The optimal operating point on 

Fig. 2 represents the optimal level of mutations. 

6. SIMULATION RESULTS 

This section presents simulation results indicating benefits of 

randomization of the routing decisions and possibility of adaptive 

optimization by adjusting the level of the randomness based on 

observed network stability/instability. We uses the latest version 

(v.2.01) of the GLASS simulation tool [15]. We extended the tool 

so that it provided periodical link cost updates and added a 

module that calculated the link costs for each feasible route and 

made the minimum average cost routing decisions. In order to 

investigate the possibility of adaptation we also implemented a 

module capable of observing history of route costs for the last 

several link cost update periods. Note that the simulation has 

reflected only the “IP part” of the TCP/IP cross-layer 

optimization. GLASS simulation has assumed that each arriving 

flow occupied a fixed bandwidth. This assumption corresponds to 

a particular case of TCP/IP for rigid streaming applications with 

utility function closely approximated by a step-wise function. 

Figure 3 demonstrates existence of the optimal level of the 

randomness, represented by parameter ≈ 0.6 opt γ for a fully 

connected network with 12 nodes and a Poisson flow arrivals. 

Fig. 3. Fully connected network with 12 nodes: aggregate utility. 

Since simulation of one scenario (one set of parameters, including 

γ ) takes approximately 11 hours, we looked at one sourcedestination pair, approximately accounting for the effect of the 

remainder of the network by fixed background traffic. Running 

one scenario for this simplified network model takes 

approximately one hour. To reduce simulation time further we 

investigated a simple two-node, two-link network shown on 

Figure 4. 

Fig. 4. Two-node, two-link network fragment. 

This network qualitatively exhibits the same pattern of behavior 

shown on Figure 3 with ≈ 0.7 opt γ . 

Figure 5 shows evolution of the low capacity link cost for 

sufficiently high level of randomness in the route selection: 

70.0%

75.0%

80.0%

85.0%

90.0%

95.0%

100.0%

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

3

Gamma

Aggregate Utility

C1 =100

λ =120 C2 = 50
opt 0 ≤ γ << γ . This evolution exhibits stable routing 

behavior without periodic pattern indicative of a route flapping 

instability. Random fluctuations in the link cost result from 

random flow arrivals/departures. Note that we cut off the link 

costs at certain level, arbitrarily scaled as link cost d = 1. 

Fig. 5. Link costs: a case of stable routing (0 ) opt ≤ γ << γ

Figure 6 shows evolution of the low capacity link cost for 

sufficiently low level of randomness in the route selection: 

opt γ >> γ . This evolution demonstrates unstable (periodic) 

routing behavior combined with random fluctuations resulted 

from random flow arrivals/departures. 

Fig. 6. Link costs: a case of unstable routing ( ) opt γ >> γ

Figure 7 shows evolution of the low capacity link cost on the 

border between stability and instability regions: opt γ ≈ γ . 

Fig. 7. Link costs: stability/instability border region ( ) opt γ ≈ γ

Figure 7 demonstrates emergence of unstable (periodic) pattern in 

the routing behavior. 

Simulation results presented on Figures 5-7 suggest that the 

optimal operating point lies within the network stability region in 

close proximity to the border of this region as assumed in off-line 

selection of the optimal operating point is depicted on Figure 2. 

We attempted to use this observation for adaptive optimization of 

the minimum cost routing. Based on the last 10 link cost update 

periods, the adaptive version of the minimum average cost routing 

algorithm approximately determines if the routing behavior is 

stable (non-periodic) or unstable (periodic). In the former case 

adaptive algorithm increases parameter γ by 10 per cent. In the 

latter case adaptive algorithm reduces parameter γ by 50 per 

cent. Figure 8 shows the corresponding random walk performed 

by the parameter γ . 

Fig. 8. Random walk by parameter γ . 

Figure 9 demonstrates that the density of the probability 

distribution for this random walk is concentrated in the 

neighborhood of the optimal parameter ≈ 0.7 opt γ . Simulation 

has also revealed that the performance loss for a case of the 

adaptive parameter γ as compared to a case of preset optimal 

parameter opt γ = γ is only 2-3 per cent. This preliminary result 

may be viewed as an encouragement for future efforts in adaptive 

routing algorithms. 

Fig. 9. Probability density of random walk by parameter γ . 

-0.2

0

0.2

0.4

0.6

0.8

1

1.2

0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000

Time [s]

Linkcost

-0.2

0

0.2

0.4

0.6

0.8

1

1.2

0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000

Time [s]

LinkCost -0.2

0

0.2

0.4

0.6

0.8

1

1.2

0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000

Time [s]

LinkCost

0

0.5

1

1.5

2

2.5

3

0.0%

5.0%

10.0%

15.0%

20.0%

25.0%

0.0

0.2

0.4

0.6

0.81.0

1.2

1.4

1.6

1.8

2.0

2.2

2.4

2.6

2.8

3.0

Gamma
7. CONCLUSION 

Based on interpretation of cross-layer optimization of TCP/IP 

network as a learning algorithm, this paper has reported initial 

simulation results indicating that (a) sufficient level of 

randomness in route selection improves the network performance 

by eliminating the route flapping instability, (b) the optimal level 

of randomness keeps the network within the stability region in 

close proximity to the border of this region, and (c) it may be 

possible to optimize the routing algorithm performance by 

adaptively the level of randomness in the route selection. Current 

research investigates shape of the stability region and the optimal 

selection of the operating point conjectured in Figure 2. This 

research is based on stability analysis of the discrete dynamic 

system (34)-(40). Future efforts should be concentrated on online determination of the set of “almost” minimum cost routes and 

estimation of the entropy of the route selection, based on the 

historic observations. 

8. ACKNOWLEDGMENTS 

The first author appreciates useful and spirit uplifting discussions 

with M. Carson and A. Nakassis. 

9. REFERENCES 

[1] A.G. Ganek and T.A. Corbi, “The dawning of the autonomic 

computing era,” IBM Systems J., Vol. 42, No 1, 2003, pp.5-

18. 

[2] D. Fudenberg and D.K. Levine, The theory of learning in 

games, The MIT Press, 1999. 

[3] C. Huitema, Routing in the Internet, Prentice Hall, 2000. 

[4] D. Bertsekas and R. Gallager, Data Networks, Prentice-Hall, 

New Jersey, 1992. 

[5] J. Wang, L. Li, S.H. Low, and J.C. Doyle, “Cross-layer 

optimization in TCP/IP networks,” IEEE/ACM Trans. on 

Networking, to appear, available at http://netlab.caltech.edu/. 

[6] A. Elwalid, C. Jin, S. Low and J. Widjaja, “MATE: MPLS 

Adaptive Traffic Engineering,” in Proceedings of 

Infocom’2001, Anchorage, Alaska, April 2001. 

[7] D.P. Bertsekas, “Dynamic behavior of shortest path routing 

algorithm for communication networks,” IEEE Trans. On 

Automatic Control, pp. 60-74, Feb. 1982. 

[8] S.H. Low and P. Varaiya, “Dynamic behavior of a class of 

adaptive routing protocols (IGRP),” Proc. Of Infocom’93, 

pp. 610-616, March 1993. 

[9] Z. Wang, Y. Wang, and L. Zhang, “Internet traffic 

engineering without full mesh overlaying,” in Proceedings of 

Infocom’2001, Anchorage, Alaska, April 2001. 

[10]A. Sridharan, R. Guerin, and Cristophe Diot, “Achieving 

Near Optimal Traffic Engineering Solution for Current 

OSPF/IS-IS Networks,” in Proceedings of Infocom’2003.

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

for communication networks: shadow prices, proportional 

fairness and stability,” Journal of the Operational Research 

Society, pp. 237-252, vol. 409, 1998. 

[12]T.M. Cover and J.A. Thomas, Elements of Information 

Theory, Wiley, 1991. 

[13]V. Marbukh, “Network provisioning as a game against 

nature,” IEEE International Communications Conference 

(ICC 2003), Anchorage, AK, 2003. 

[14]V. Marbukh, “On Shortest random walks under adversarial 

uncertainty”, Fortieth Annual Allerton Conference on 

Communication, Control, and Computing, Monticello, 

Illinois, 2002. 

[15]O. Borchert and R. Rouil, “The GMPLS lightwave agile 

switching simulator – an overview,” 

http://www.antd.nist.gov/glass. 

.