Loop-Free Link-Traﬃc in Optimal Routing for Multi-Class
Networks∗
Hisao Kameda†, Jie Li† and Eitan Altman‡

Abstract
Individually and overall optimal routing problems are considered for networks with nodes interconnected by a generally conﬁgured manner and with multiple classes of users. The two problems
are formulated along with the discussions on mutual equivalence between both problems, on theexistence and uniqueness of solutions, and on the relation between the formulations with path andlink ﬂow patterns. We show that a link-traﬃc loop-free property holds within each class for bothindividually and overall optimal routing in a wide range of networks, and show the condition thatcharacterizes the category of networks for which the property holds.
Keywords: communications network, transportation network, overall optimization, Wardrop
equilibrium, existence and uniqueness, path ﬂow pattern, link ﬂow pattern

1 Introduction
We have two typical approaches for optimal routing in networks. (1) One arises in a context of minimizing the overall cost (overall mean delay) of all users (e.g., packets) from its arrival (origin) node of eachuser to its destination node through a number of links over the entire network. The optimal routing policy
with this framework is called the overall optimal routing policy. (2) A second approach is a distributed
one in which one seeks for a set of routing strategies for all users such that no user can decrease its cost
(expected delay) by deviating from its strategy unilaterally. This could be viewed as a result of leaving
each user the decision on which path to route. This approach is called the individually optimal routing
or selﬁsh routing [19, 20]. The situation where each user has unilaterally minimized its cost is called a
Wardrop equilibrium [17, 22] or a Nash equilibrium where no user has any incentive to make a unilateraldecision to change its route.
In computer and communication networks, most work has focused on overall optimal routing (e.g.,[2, 7, 8]). For networks in general, however, minimizing the cost of each user from its arrival (origin) node to its destination node is a major concern of the user. Thus, individually optimal routing
has attracted increasing attention of researchers and practitioners also in computer and communication
networks, and some research results have been obtained on it [1, 3, 16, 19, 20].
In most studies on optimal routing problems for communication networks in the literature (e.g.,[2, 7, 8, 9, 3, 16]), the link cost is modeled as a simple function dependent only on the link ﬂow itself.
We call it the traditional link-cost model. In this paper, however, the cost on a link of a network is
modeled by a function of the ﬂows of all links of the entire network. We call it a general link-cost model.
For example, we can consider a wireless communication network, where, when a link connecting two∗

A preliminary version of this paper was presented at IEEE CDC’04.
Hisao Kameda and Jie Li are with the Graduate School of Systems and Information Engineering, University of Tsukuba,
Tsukuba Science City, Ibaraki 305-8573, Japan. Email: {kameda,lijie}@osdp.cs.tsukuba.ac.jp.
‡
Eitan Altman is with INRIA, BP93, 06902 Sophia Antipolis Cedex, France. Email: Eitan.Altman@sophia.inria.fr.
†

1

nodes has more ﬂow and, thus, uses more power, links neighboring the link may have less capacity. This
paper studies both the individually and overall optimal routing problems in general link-cost models ofgenerally conﬁgured networks with multiple classes of users. We call a network with multi-class users
a multi-class network. We note, however, that, in these optimization problems, the cost to be optimized
depends only on the link ﬂow pattern while the instrument (the set of decision variables) is the path ﬂow
pattern.
In this paper, we discuss individually and overall optimal routing problems on which Dafermos has
obtained some basic results [6, 4, 5]. Our treatment is, however, more general than hers in the following
points: (1) Our model allows each user of a class to enter any origin and leave any destination bothavailable to the class with/without ﬁxing the arrival rate at each origin and the departure rate at each
destination. (2) The link-traﬃc loop-free property is discussed. (3) The relation between the case where
the instrument is the path ﬂow pattern and the case where it is the link ﬂow pattern is discussed. In
particular, we note that, by deﬁnition, a path ﬂow pattern determines a unique link ﬂow pattern whereas
it may not be sure whether for a link ﬂow pattern there exists a path ﬂow pattern that induces it, i.e.,
whether a given link ﬂow pattern is realizable.
We conﬁrm that, for the individually optimal routing problem under our assumptions, there is an
overall optimal routing problem associated to it, and that both have the same solution. We discuss theexistence and uniqueness of the solutions to the overall and individually optimal routing. Furthermore,
we show that the link-traﬃc loop-free property holds for each class, for the individually and overall
optimal routing in general link-cost models of multi-class networks. We pay much attention to therelation between the cases where the sets of the control variables are, respectively, the path and link
ﬂow patterns. We show the condition that characterizes the category of networks where the link-traﬃcloop-free property holds for each class. Some examples are discussed. In contrast, note that, evenin the networks where the link-traﬃc loop-free property holds for each class in overall and individually
optimal routing, it does not always hold in noncooperative optimal routing by a ﬁnite (but plural) numberof decision makers, where the decision makers strive to optimize unilaterally the cost of the users under
its control. Such counter-examples are given in [12, 13] (with the deﬁnition of class in those papers
changed to be the same as the one in this paper). Note, in passing, that overall optimal routing may have
only one decision maker and that individually optimal routing has inﬁnitely many inﬁnitesimal decision
makers.
The rest of this paper is organized as follows. In the next section, we provide the problem formulation. The relation between the individually and overall optimal routing for multi-class networks isprovided in Subsection 2.3. Subsection 2.4 discusses the existence and uniqueness of individually andoverall optimal routing for multi-class networks. Section 3 discusses the link-traﬃc loop-free property
for the individually and overall optimal routing for multi-class networks. Some examples are shown in
Section 4. Section 5 concludes the paper.

2 Problem Formulation and Solutions
Consider a network consisting of n nodes numbered, 1, 2, . . . , n, interconnected in an arbitrary fashion bylinks. N and L, respectively, denote the sets of nodes and links. There are multi-class users in the network.
C denotes the set of user classes. Each class may have a distinct set of links available to the class. We
assume that users do not change their classes during their trips from origins and destinations. We calllinks available to class-k users ‘class-k links.’ Lk denotes the set of ‘class-k links.’ Then, L = ∪k∈C Lk . Bya path for a class, say class k, connecting an ordered pair ω = (o, d), we mean a sequence of class-k links(v1 , v2 ), (v2 , v3 ), . . . , (vn0 −1 , vn0 ) that any class-k user can pass through where v1 , v2 , . . . , vn0 are distinct
nodes, v1 = o, and vn0 = d. Then, the path is denoted by (o, v2 , . . . , vn0 −1 , d). We call node o an origin,2the node d a destination and the pair ω = (o, d) an origin-destination pair (or o-d pair for abbreviation).
Each class may have a distinct set of origins and of destinations.
If vi is the same as node v j for some i and j such that j < i, we say that the path has a loop or cycle.
We note, however, that in the optimal solutions such a loop within a path never exists. Therefore, a link
appears in a path for a class at most once. On the other hand, although each path has no loop, the network
may have a loop as to link ﬂows as discussed in Section 3. We have the following assumptions.
A1 (1) If there exists a possible series of link connections for a class between an o-d pair, there must
exist a path for the class between the o-d pair. (2) If there exists a path for a class between an o-dpair, all possible series of link connections for the class between the o-d pair are also paths of theclass between the o-d pair.
A2 The rates of arrivals at each origin and of departures at each destination are given for each class.
Remark 1 As seen later in Sections 3 and 4, Assumption A1 presents the condition that characterizes
the category of networks that have the link-traﬃc loop-free property within each class for overall andindividually optimal routing. Even under the assumptions A1 and A2, we can model the situation where
there are particular combinations of origins and destinations such that users arriving at an origin should
depart the network only from the destination corresponding to the origin.
In Assumption A2, it may look unnatural that the rate of the departure at each destination is given
even though each user can leave the network at any available destination. We see below, however, thatthe assumption A2 is most general. Consider a network, named M, where each class-k user can leave
the network at any available destination without ﬁxing the class-k departure rate at each destination. We
imagine another network, named M0 , where one class-k ‘ﬁnal’ destination is added to the network M
and that each of the class-k destinations in M is connected to the class-k ﬁnal destination via a class-k
zero-cost link in the network M0 for every class k. (Later in this section, we will describe zero-cost links
along with the deﬁnition of link-cost functions, Gkij .) Then, the imagined network M0 can be regarded
as the one with multiple-origins and one common destination for class k as shown in Section 4.1.1 andsatisﬁes Assumptions A1 and A2. The optimal solutions of the networks M and M0 should be identical.
In a similar way, we can consider a network where each class-k user can enter the network at any
origin without ﬁxing the class-k arrival rate at each origin but with the departure rate at each class-k
destination being ﬁxed. We can also consider a network where each class-k user can enter at any origin
and leave from any destination without ﬁxing the arrival and departure rates at any origin and destination
for class k and with ﬁxing the total arrival and departure rates for the class k, respectively. The former
network is equivalent to the network where one ‘initial’ origin is added and connected to each origin via
a zero-cost link for class-k. The latter network is equivalent to the network where one initial origin andone ﬁnal destination are added for class-k.
We therefore see that the assumption A2 is most general and covers all three kinds of networks eachof which is equivalent to the corresponding one of the three networks mentioned above, respectively. For simplicity, we assume that a node cannot be both an origin and a destination at the same time
for the same class. The sets of all origin and destination nodes for class k are denoted by Ok and Dk ,respectively. The sets of all possible paths which originate from an o ∈ Ok and which are destined fora d ∈ Dk , for class k, are denoted by Pko− and Pk−d , respectively. The set of all paths in the network
for class k is denoted by Pk , each element of which must appear in a Pko− and in a Pk−d , i.e., Pk =k∪o∈Ok Pko− = ∪d∈Dk Pk−d ). For every origin o ∈ Ok and for every destination d ∈ Dk , respectively, let ro−k (k ∈ C) be the nonnegative external class-k user traﬃc demands that originates at node o for all
and r−ddestinations d ∈ Dk , and that is destined for node d from all origins o ∈ Ok .

3

k which ﬂows through path p. Similarly for a path
For a path p ∈ Pko− , ykp denotes the part of ro−kp ∈ P−d . y p is called the class-k path ﬂow through the path p. We have the following relations.
∑kykp = ro−, o ∈ Ok ,(1)
p∈Pko−∑kykp = r−d, d ∈ Dk ,(2)

ykp ≥ 0, p ∈ Pk , k ∈ C.

(3)

p∈Pk−d

∑
k
k
k
k
k = ∑
Naturally, o∈Ok ro−d∈Dk r−d . Denote the path ﬂow pattern by y = [y ], where y = [y p ]. By afeasible path ﬂow pattern, we mean y which satisﬁes relations (1), (2), and (3). Denote by FS y the setof feasible path ﬂow patterns. Clearly, FS y is convex, closed, and bounded.
Denote by xikj the class-k user ﬂow rate, also called the class-k ﬂow, through link (i, j). Let x = [xk ]where xk = [xikj ]. Furthermore, let x = [xi j ] where xi j = [xikj ]. We call x the link ﬂow pattern. Since alink appears in a path at most once, a class-k link ﬂow is expressed by class-k path ﬂows as follows.
∑pxikj =(4)
δi j ykp , (i, j) ∈ Lk , k ∈ C,
p∈Pk

where
{
p

δi j =

1, if link (i, j) is contained in path p,0, otherwise.

If link (i, j) is included in path p, we also express it as (i, j) ∈ p. From (4), we notice that a path ﬂow
pattern y induces a unique link ﬂow pattern x, while it is possible that more than one path ﬂow patterny induces the same link ﬂow pattern x. Moreover, for given x, it may not be sure whether there exists apath ﬂow pattern y that induces x.
Let Gkij be the class-k link cost of sending a class-k user from node i to node j through link (i, j).
Gkij is a function of all link ﬂows x. We assume that, for most of the link costs, Gkij (x) is a positive anddiﬀerentiable function that is convex in x and, in particular, that Gkij (x) is strictly convex in xikj . We also
consider the possible existence of zero-cost links the ﬂows of which do not inﬂuence other link costs,
00that is, for some i0 , j0 , k0 , Gki0 j0 (x) = 0 for all x, and xik0 j0 does not aﬀect any other Gkij . x s denotes thevector that consists of the elements xikj such that each corresponding Gkij (x) is strictly convex in xikj , and0x−s denotes the vector that consists of the elements xik0 j0 each of which is the ﬂow through the class-k0
zero-cost link (i0 , j0 ).
Dkp (x) denotes the class-k cost of a path p. Then,∑p
Dkp (x) =δi jGkij (x), p ∈ Pk , k ∈ C.
(5)(i, j)∈Lk

2.1 Overall Optimal Routing for Multi-Class Networks
By using (4) and (5), the overall cost of users over all classes is expressed as
D(x) =

1∑ ∑ k k
1∑∑ k ky p D p (x) =xi jGi j (x),
R k∈C
R k∈C
k
k
p∈P

(i, j)∈L

4

∑ ∑
∑
k =∑
k
where R = k∈C o∈Ok ro−k∈C d∈Dk r−d .
Thus, considering (4), the overall optimal routing problem is expressed as follows.
min D(x(y)) subject to y ∈ FS y .

(6)y

We have assumed that Gkij (x) is convex in x and, in particular, strictly convex in xikj , for all i, ( j , i), k.
We also assume that D(x) is convex in x and strictly convex in x s . Then, we see that D(x) is convex in y,which can be easily shown as follows: Indeed, the relation (4) can be regarded as a linear transformation:y → x and we denote this by x = x(y). Then, αD(x(y1 )) + (1 − α)D(x(y2 )) ≥ D(αx(y1 ) + (1 − α)x(y2 )) =D(x(αy1 + (1 − α)y2 )), where the inequality follows from the convexity of D(·) and the equality follows
from the transformation linearity. Thus, we see that D(x(y)) is convex in y.
Deﬁne gi j (x) as follows.
gkij (x) = R

∂
D(x).
∂xikj

(7)

Consider the following Lagrangian function:
∑[ ∑
∑
∑
∑
]
k
k
L(y, φ) = RD(x) +φko− (ro−−ykp ) +
φk−d (r−d−ykp ) ,k∈C o∈Okp∈Pko−d∈Dkp∈Pk−dwhere φko− and φk−d are Lagrange multipliers. Then, the path ﬂow pattern y that satisﬁes the following
relation derived from the Kuhn-Tucker condition is a solution for overall optimal routing if such a ﬂow
pattern y exists,∑
gkij (x) = βko,d , for y p > 0,(i, j)∈p∑

gkij (x) ≥ βko,d , for y p = 0,(8)(i, j)∈pp ∈ Pk , o ∈ Ok , d ∈ Dk , k ∈ C, y ∈ FS y ,where βko,d = φko− + φk−d . We recall that Pk = ∪o∈Ok Pko− = ∪d∈Dk Pk−d ).

2.2 Individually Optimal Routing for Multi-Class Networks
Informally, we deﬁne the individually optimal routing to be such that each individual user routes itself so
as to minimize its own cost from the arrival at its origin node to the departure from its destination node,
given the expected link cost of each link. In the equilibrium that the routing policy results in, every userof all classes may feel that its own cost is minimized and has no incentive to make a unilateral decision
to change its route. In other words, the link ﬂow pattern x of individually optimal routing is a Wardrop
equilibrium [22]. or a Nash equilibrium point in the sense of noncooperative game [15]. Thus, we deﬁne
the equilibrium condition of the individually optimal routing as follows.
Deﬁnition I: A path ﬂow pattern y is said to satisfy the equilibrium condition of the individually optimalrouting if and only if the following relation holds.
∑
Dkp (x) =Gkij (x) = Ako,d , for y p > 0,(i, j)∈p

Dkp (x) =∑Gkij (x) ≥ Ako,d , for y p = 0,(i, j)∈pp ∈ P , o ∈ Ok , d ∈ Dk , k ∈ C, y ∈ FS y .
k

5

(9)

We recall that Pk = ∪o∈Ok Pko− = ∪d∈Dk Pk−d ). We call the path ﬂow pattern y the solution of theindividually optimal routing if it satisﬁes the above equilibrium condition. It is a Wardrop equilibrium[22].
Remark 2 The above deﬁnition I and the assumptions A1 and A2 imply the situation where it only holds
that, for each combination of the origin and the destination, the paths used have equal costs that are notless than those of the unused paths. But, this situation may not reﬂect the freedom of each user of a class
to choose one destination among those available to the class. In order that truly individual decisions may
be realized, we may use the framework mentioned in the last paragraph of Remark 1. 

2.3 Relation between Individually and Overall Optimal Routing for Multi-Class Networks
We construct a new overall cost function D̂(x) for the same network as that of (6), such that
Gkij (x) = R∂D̂(x), (i, j) ∈ Lk , k ∈ C.
k
∂xi j

(10)

According to the line of research by Dafermos, et al. [4, 5, 17], we consider whether and under what
condition such a function D̂(x) exists. Since link-cost function Gkij (x) ((i, j) ∈ Lk , k ∈ C) is diﬀerentiable,k0 ((i, j) ∈ Lk , (l, m) ∈ Lk0 , k, k0 ∈ C) exists. Then, we assume that the matrix of partial derivatives∂Gkij /∂xlm0[ ∂Gk ]
∂Gkij
∂Gklm
ij
, is symmetric (i.e.,=
for all (i, j) ∈ Lk , (l, m) ∈of link-cost functions, Λ(x) =
k0
k0
∂xlm
∂xlm
∂xikj
0
Lk , k, k0 ∈ C). Moreover, we consider a submatrix, Λ s (x), of Λ(x) that contains the ((i jk), (i0 j0 k0 ))-th0elements such that both xikj and xik0 j0 are in x s . We note that the elements of Λ(x) that are not in Λ s (x)are all zero. We assume that Λ s (x) is positive deﬁnite. Then, D̂(x) is strictly convex in x s , Λ(x) is semipositive deﬁnite, and D̂(x) is convex in x. In the traditional link-cost models, Λ(x) is also symmetric andsemi-positive-deﬁnite (see, e.g., [1, 19]). Denote by (x−(i jk) , xi0kj ) the vector with the component xikj of x
replaced by xi0kj . If Λ(x) is symmetric, the following satisﬁes (10).
D̂(x) =

R∑{∑ ∑ ∫ xikj

1}
Gkij (x−(i jk) , xi0kj )dxi0kj .

(11)Gkij ((x−(i jk) , xi0kj ))dxi0kj , (i, j) ∈ Lk , k ∈ C.

(12)kk∈C |L | k∈C (i, j)∈Lk

0

We deﬁneĜkij (x)

=

k ∑

xi j

∫ xk

1
k∈C

ij

|Lk |

0

Then, we regard Ĝkij as a new class-k link cost on link (i, j). Thus,
D̂(x) =

1∑ ∑ k k
xi jĜi j (x).
R k∈Ck(i, j)∈L000

We recall that, for xik0 j0 ∈ x−s , Ĝki0 j0 = 0 and xik0 j0 would not inﬂuence other Ĝkij (i0 , i or j0 , j). Thus, wehave the following overall optimization problem, considering (4).
min D̂(x(y)) subject to (4) and y ∈ FS y .
y

6

(13)

We call the overall optimization problem (13) an associate problem to the individually optimal routing problem. We note that it is another overall optimal routing problem. Consider the following Lagrangian function:
∑
∑[ ∑
∑
∑
]
k
k
φ̂k−d (r−d−L̂(y, φ) = RD̂(x) +φ̂ko− (ro−−ykp ) +ykp ) ,k∈C o∈Okp∈Pko−d∈Dkp∈Pk−dwhere φ̂ko− and φ̂k−d are Lagrange multipliers. Then, the path ﬂow pattern y that satisﬁes the following relation derived from the Kuhn-Tucker condition as to the above Lagrangian function is an overall optimal
solution to the associate problem if such a ﬂow pattern y exists.
∑
Gkij (x) = Ako,d , for y p > 0,(i, j)∈p∑

Gkij (x) ≥ Ako,d , for y p = 0,(14)(i, j)∈pp ∈ Pk , o ∈ Ok , d ∈ Dk , k ∈ C, y ∈ FS y ,where Ako,d = φ̂ko− + φ̂k−d . We see that the above is equivalent to the condition (9) describing the solutionof the corresponding individually optimal routing problem. Then, we have the following lemma.
Lemma 1 A path ﬂow pattern y is a solution to associate problem (13) if and only if it satisﬁes theequilibrium condition (9).
On the other hand, if we regard gkij (x) as a new class-k link cost on link (i, j), then we have theequilibrium condition (8) of individual optimization that is an associate condition to the overall optimalrouting problem for multi-class networks with Gkij (x) being the class-k cost on link (i, j).
Corollary 1 A path ﬂow pattern y satisﬁes the associate condition (8) if and only if it is a solution to theoverall optimization problem (6).

2.4 Existence and UniquenessIn this section, we study the existence and uniqueness of the solutions to individually and overall optimalrouting problems for multi-class networks. We ﬁrst discuss the existence and uniqueness of the solutions
to the overall optimal routing problem. Then, by noting that the individually optimal routing problem
can be transformed into its associate overall optimal routing problem (13), we investigate the existence
and uniqueness of the solution to the associate problem (13) and, then, to the individually optimal routing
problem (9).
Denote the set of feasible link ﬂow patterns by FS x . That is,
FS x = {x | There exists y such that x and y satisfy (4) and y ∈ FS y }.
Clearly, the set {(x, y) | (x, y) satisﬁes (4) and y ∈ FS y } is convex, closed, and bounded, Then, by notingthat the orthogonal projection of a convex set onto a subspace is another convex set (see, e.g., [18]), theset FS x is convex in x and a closed and bounded hyperplane (see, e.g., [18]). Note that D(x) in (6) is
continuous in x and, thus, in y, and that the feasible set FS y is closed and bounded. Then, there exists asolution of path ﬂow patterns y to (6), according to the Weierstrass theorem (e.g., [10, 11]). Since D(x)is continuous and convex in x and strictly convex in x s , we have the following.

7

Theorem 1 For the overall optimal routing problem for multi-class networks (6), an optimal path ﬂow
pattern y exists and, in particular, the resulting x s is unique.
The uniqueness of x s is shown by contradiction as follows. Suppose that x s is not unique and thatboth x1 = (x1s , x1−s ) and x2 = (x2s , x2−s ) give the minimum Dmin of D(x), for x1s , x2s . Then, from theconvexity of the feasible region of x, αx1 + (1 − α)x2 , for some α (0 < α < 1), is also in the feasible
region, andD(αx1 + (1 − α)x2 ) = D(αx1s + (1 − α)x2s , αx1−s + (1 − α)x2−s )< αD(x1s , αx1−s + (1 − α)x2−s ) + (1 − α)D(x2s , αx1−s + (1 − α)x2−s )= αDmin + (1 − α)Dmin = Dmin ,where the inequality follows from the strict convexity of D(x) in x s and the second-last equality follows
from the meaning of x−s . The above relation contradicts the assumption that Dmin is the minimum of
D(x), and we see that the x that minimizes D(x) has a unique x s .
For the individually optimal routing problem, we note that D̂(x) in (13) is continuous in x and, thus,
in y, and that FS y is closed and bounded. Then, similarly as above, there exists a solution of y to (13)according to the Weierstrass theorem (e.g., [10, 11]). With Lemma 1 and by noting that D̂(x) is convex
in x and strictly convex in x s , we have the existence and uniqueness of a solution to individually optimalrouting as follows.
Theorem 2 For the individually optimal routing problem, there exists a solution y to (13) and thus thatsatisﬁes (9), and, in particular, the resulting x s is unique.
For the overall (respectively, individually) optimal routing problem, consider the following optimization problem that involves only the link ﬂow pattern x and does not involve the path ﬂow pattern y (withD(x) to be replaced by D̂(x) for the individually optimal routing problem).
min D(x) subject to x ∈ FS x .
x(15)

Similarly as above, we see that there exists a solution of x to (15) (respectively, to the problem with D(x)being replaced by D̂(x)), according to the Weierstrass theorem (e.g., [10, 11]). The optimization problem(15) (respectively, the one with D(x) being replaced by D̂(x)) is another nonlinear convex optimization
problem, but, clearly, (15) (respectively, the one with D(x) being replaced by D̂(x)) gives the solution xthat is the same as the link ﬂow pattern x that the solutions y to (6) (respectively, (13), thus (9)) result in.

3 Link-Traﬃc Loop-Free Property
In this section, we show a property that holds for the individually/overall optimal routing for multi-classnetworks, called the link-traﬃc loop-free property. The link-traﬃc loop-free property is such that there
exists no loop that consists of a sequence of links (v1 , v2 ), (v2 , v3 ), . . . , (vn0 −1 , vn0 ) where v1 , v2 , . . . , vn0
are distinct nodes while v1 = vn0 such that class-k link ﬂow xvk1 ,v2 > 0, xvk2 ,v3 > 0, xvkn0 −1 ,vn0 > 0 (k ∈ C)
(Figure 1). Although it is evident that no path has a loop, it is not clear whether there exists no loop forlink ﬂows of each class. For example, if Assumption A1 does not hold, as shown by the example given
later, there may exist loops for link ﬂows in the network.
From relations (1), (2), and (4), we have the following ﬂow-balance relation.
∑
∑
k
k
ri−
(if i ∈ Ok ) +xlik = r−i(if i ∈ Dk ) +xilk , i = 1, 2, . . . , n − 1, k ∈ C,
(16)
l∈Vik

l∈Vik

8

xikj
j

i

Figure 1: Link-traﬃc loop-free property in individually/overall optimal routing
where Vik is the set of immediately neighboring nodes of node i for class k, i.e., Vik = { j|(i, j) ∈Lk , or ( j, i) ∈ Lk }. The constraint with respect to i = n can be derived by summing up both sidesof the above constraints for i = 1, 2, . . . , n − 1. Deﬁne FS I as follows:
FS I = {x | x satisﬁes (16) and x ≥ 0}.
Note that the set of FS I is convex, closed, and bounded. Note, furthermore, that FS I includes but may
not be identical to FS x .
We have the associate problem for the individually optimal routing (and the overall optimal routing
problem) with the following new constraint (with D̂(x) and Ĝkij (x), respectively, to be replaced by D(x)and Gkij (x) for the overall optimal routing problem).
min D̂(x) subject to x ∈ FS I.

(17)

x

The necessary and suﬃcient condition that a solution to the above individually/overall-optimal routing problem satisﬁes is given as follows.
Lemma 2 The link ﬂow pattern x is an optimal solution to the individually (and overall) optimal routing
problem with constraint x ∈ FS I (17) if and only if x satisﬁes the following set of relations (with Gkij (x)to be replaced by gkij (x) for the overall optimal routing problem).
αki − Gkij (x) = αkj , for xikj > 0, (i, j) ∈ Lk , k ∈ C,(18)

αki − Gkij (x) ≤ αkj , for xikj = 0, (i, j) ∈ Lk , k ∈ C,

(19)

subject to x ∈ FS I, where αki (i ∈ N, k ∈ C) are Lagrange multipliers.
PROOF: We show the case of individual optimization. The case of overall optimization is shown in asimilar way. To obtain an optimal solution to problem (17), we form the Lagrangian function as follows,
H(x, α) = RD̂(x) +

n−1
∑∑

∑
∑ ]
[ k
k
αki ri−(if i ∈ Ok ) +xlik − r−i(if i ∈ Dk ) −xilk ,k∈C i=1

l∈Vi

(20)

l∈Vi

where αki are Lagrange multipliers.
Since function D̂(x) is continuous and convex in x (and strictly convex in x s ) and FS I is convex,
closed, and bounded, there exists a solution (that has a unique x s ) to problem (17) similarly as Theorem
92. Thus, the link ﬂow pattern x that satisﬁes the following Kuhn-Tucker condition is an optimal solution(that has a unique x s ) to problem (17) (see, e.g., [10]).
∂H= Gkij (x) + αkj − αki ≥ 0,
∂xikj
xikj

∂H
= xikj (Gkij (x) + αkj − αki ) = 0,k∂xi jxikj ≥ 0, (i, j) ∈ Lk , k ∈ C,kri−
(if i ∈ Ok ) +∑kxlik = r−i(if i ∈ Dk ) +

l∈Vi

∑

xilk , i = 1, 2, . . . , n − 1, k ∈ C.

l∈Vi

Rearranging the above relations, we have,
αki − Gkij (x) = αkj , for xikj > 0,
αki − Gkij (x) ≤ αkj , for xikj = 0,(i, j) ∈ Lk , k ∈ C, x ∈ FS I.
The above set of relations is equivalent to the set of relations (18), (19) and x ∈ FS I, and it is thenecessary and suﬃcient condition for a link ﬂow pattern x to be a solution to the individually optimalrouting problem (17). With Lemma 2, we proceed to have the link-traﬃc loop-free property in the individually/overall
optimal routing for problem (17).
Lemma 3 The class-k link traﬃc in a solution to the individually (and overall) optimal routing problem
with constraint x ∈ FS I (17) is loop free for all k ∈ C. That is, there exists no class-k link traﬃc suchthat xvk1 v2 > 0, xvk2 v3 > 0, . . . , xvkm−1 vm > 0, xvkm v1 > 0 (for all k ∈ C), where v1 , v2 , . . . , vm are distinct nodes
in the solution to the individually (and overall) optimal routing problem and where at least one of thelinks involved is not a zero-cost link.
PROOF: We show the case of individual optimization. It is proved by contradiction. Assume that there
exists class-k link traﬃc in the solution to individually optimal routing problem (17) for multi-class users
such as xvk1 v2 > 0, xvk2 v3 > 0, . . . xvkm−1 vm > 0, xvkm v1 > 0 (k ∈ C), where v1 , v2 , . . . , vm are distinct nodes.
According to Lemma 2, in the solution, we have
αkv1 − Gkv1 v2 (x) = αkv2 ,..
.
αkvm − Gkvm v1 (x)

=

(21)

αkv1 .

Then, we haveGkv1 v2 (x) + Gkv2 v3 (x) + · · · + Gkvm v1 (x) = 0,(22)which contradicts the fact that Gkij (x) > 0 if xikj > 0 for at least one of (non-zero-cost) links involved.
The case of overall optimization is shown in a similar way as above by replacing Gkij (x) by gkij (x). 
Since the constraint x ∈ FS I of the optimization problems may be weaker than the set of constraints
x ∈ FS x , there may be the possibility that a link ﬂow solution x (x ∈ FS I) may not be realized by any
path ﬂow pattern. In the following, however, we conﬁrm that there exists a path ﬂow pattern y that results
in any loop-free link-ﬂow pattern x such that x ∈ FS I.
10ika
originonode iyko... ixikj
yko... i jnode jFigure 2: Assigning ﬂows to paths on the basis of link ﬂows
Proposition 1 There exists a path ﬂow pattern y satisfying the constraint y ∈ FS y that results in a linktraﬃc loop-free ﬂow pattern x satisfying the constraint x ∈ FS I. That is, for networks with a link-traﬃcloop-free ﬂow pattern, FS I = FS x .
PROOF: Consider an arbitrary loop-free link-ﬂow pattern x that satisﬁes the constraint x ∈ FS I. We
show how to make a path ﬂow pattern y (∈ FS y ) that results in the loop-free link-ﬂow pattern x (∈ FS I).
We consider the following for each class. Consider a path (o, v1 , v2 , . . . , vi , vi+1 , . . . , d) where o is an
origin node, d is a destination node, and v1 , v2 , . . . , vi , vi+1 , . . . are called ‘intermediate nodes.’ Then, wecall the sequence (o, v1 , v2 , . . . , vi ) an intermediate path at node vi of path (o, v1 , v2 , . . . , vi , vi+1 , . . . , d).
Naturally, there may be multiple intermediate paths at each node including those coming from diﬀerent
origins. Furthermore, we also say that the sequence (o, v1 , v2 , . . . , vi ) is the intermediate path at node vithat is included in the intermediate path (o, v1 , v2 , . . . , vi , . . . , v j ) longer than it, for i < j and v j , d.
We can assign a path ﬂow pattern y such that the constraint x ∈ FS I is satisﬁed, as follows. We notethat the ﬂow through each intermediate path must be the sum of the ﬂows of the paths that go though theintermediate path for each class. The allotment of the ﬂow to an intermediate path of node vi+1 is done by
splitting the ﬂow to the intermediate paths of node vi , in a way proportional to the link ﬂow xvki ,vi+1 on thelink (vi , vi+1 ), say, for class k (in the case where node vi is neither an origin nor a destination for the class,and other cases are also treated in a formal manner below). In that sense, we obtain a proportionally fair
allotment.
More precisely, given a link-traﬃc loop-free ﬂow pattern, the path ﬂow pattern for class k, k ∈ C, canbe obtained as follows: Since the used links has the loop-free property, a ‘partial order’ relation amongclass-k nodes holds, that is, from the origins down to the destinations. Therefore, there must exist at least
one origin that receives no class-k ﬂows from any nodes but only sends class-k ﬂows to other nodes. We
call it a pure origin for class k. Similarly, there must exist at least one destination that sends no class-k
ﬂows to any nodes but only receives class-k ﬂows from other nodes. We call it a pure destination forclass k. Denote by ika the set of nodes that may receive class-k ﬂow directly from node i (Fig. 2).
(i) The case where node i is a pure origin o. A node j directly connected to a pure origin o ( j ∈ oka )has the class-k link ﬂow xok j . There must be only one class-k intermediate path from the origin at a nodej ∈ oka , that passes through one class-k link to the node j from the origin, and, thus, the allotment ofclass-k ﬂow to the class-k intermediate path is straightforward. Clearly, this allotment is relevant to (4)and (1) but does not violate them since x ∈ FS I must hold.
(ii) The case where node i is neither an origin nor a destination: Each of the class-k intermediate paths at

11

xikj
k
node j, j ∈ ia , that go through node i, will be allotted the ratio ∑of the ﬂow of the correspondingkl∈ika xilclass-k intermediate path at node i. For example, if the class-k intermediate path (o, . . . , i) included in aclass-k intermediate path (o, . . . , i, j) has the ﬂow yko... i , the class-k intermediate path (o, . . . , i, j) is to be
allotted the ﬂow
xikj
yko... i j = yko... i ∑.
kl∈ika xil
Clearly, this allotment is relevant to (4) and (1) but does not violate them since x ∈ FS I must hold.
k : Each(iii) The case where the node i is not a pure origin but an origin that has the external arrival rate ri−
kof the class-k intermediate paths at node j, j ∈ ia , that go through node i, will be allotted the ratio
∑
k
k
xikj
l∈ika xil − ri−∑∑kkl∈ika xill∈ika xilof the ﬂow of the corresponding class-k intermediate path at node i. In addition, a new set of intermediate
paths starting at node i is added to the group of node- j intermediate paths, and each is allotted the ﬂow
xikj
k
ri− ∑
. Clearly, this allotment is relevant to (4) and (1) but does not violate them since x ∈ FS I
kl∈ika xil
must hold.
k :(iv) The case where the node i is not a pure destination but a destination that has the departure rate r−ikEach of the class-k intermediate paths at node j, j ∈ ia , that go through node i, will be allotted the ratio∑kxikjl∈ika xil∑∑kkkl∈ika xil + r−i l∈ika xilof the ﬂow of the corresponding class-k intermediate path at node i. In addition, we have a set of completekr−ipaths ending at node i, and each is allotted the ratio ∑of the ﬂow of the correspondingkkl∈ika xil + r−i
intermediate path of node i. Clearly, this allotment is relevant to (4) and (2) but does not violate themsince x ∈ FS I must hold.
(v) The case where node i is a pure destination for class k. All the class-k paths that reach this nodeterminate at this node, and no further path-ﬂow allotment for class k is needed anymore. Clearly, we see
that, at this node, class-k path ﬂow allotment so far is relevant to (4) and (2) but does not violate themsince x ∈ FS I must hold.
We therefore see that, at every step of the above ﬁve allotments in cases (i), (ii), (iii), (iv), and (v), the setof constraints (4) and y ∈ FS y is satisﬁed.
Therefore, for an arbitrary x (∈ FS I) with the loop-free property, starting from nodes that directly
receives class-k ﬂows only from origins that receive no class-k ﬂows from other nodes, we can proceed
the steps of allotting the amount of class-k ﬂows to intermediate paths, and ﬁnally we can complete theassignment y of class-k path ﬂows, for all k ∈ C, that result in the above-mentioned x (∈ FS I).
We note that the above obtained y satisﬁes both the constraints (4) and y ∈ FS y and, thus, that theabove mentioned x satisﬁes the constraint x ∈ FS x .
Since FS I includes FS x , then, for networks with a link-traﬃc loop-free ﬂow pattern, FS I = FS x . 
From the above Proposition 1 and Lemma 3, we can conﬁrm the following.

12

xikj > 0jixkji = 0
Figure 3: One-way traﬃc property in individually and overall optimal routing
Lemma 4 For the solution x with the link-traﬃc loop-free property for the individually/overall optimalrouting with constraint x ∈ FS I (17) there exists a y that satisﬁes both the set of constraints (4) andy ∈ FS y , i.e., FS I = FS x .
We, therefore, see that the solution x with the link-traﬃc loop-free property for the individually/overall
optimal routing with constraint x ∈ FS I (17) is also the solution for the individually (and overall) optimalrouting problem (6,13,17), since its solution exists as discussed in Section 2.4.
Then, we have the following theorem.
Theorem 3 (Link-traﬃc loop-free property) The class-k link traﬃc in a solution to the individually(and overall) optimal routing problem (6,13,17) for a multi-class network is loop free for all k ∈ C. Thatis, there exists no class-k link traﬃc such that xvk1 v2 > 0, xvk2 v3 > 0, . . . , xvkm−1 vm > 0, xvkm v1 > 0 (for allk ∈ C), where v1 , v2 , . . . , vm are distinct nodes in the solution to the individually (and overall) optimalrouting problem and where at least one of the links involved is not a zero-cost link.
Now consider the case where two nodes are connected by two links. We have following result.
Corollary 2 (One-way traﬃc property) For any optimal solution x to an individually/overall optimalrouting problem (6,13,17) for multi-class networks, the following relations hold true,
xikj = 0, if xkji > 0,(23)

where either (i, j) or ( j, i) is not a zero-cost link for class k, for (i, j), ( j, i) ∈ Lk , k ∈ C.
PROOF: It is a direct result from Theorem 3. 
The property shown in the corollary 2 is called the one-way traﬃc property for the individually/overall
optimal routing in multi-class networks. The physical meaning is clear. It shows that the traﬃc from thenode i to node j, xikj , and the user ﬂow rate from the node j to node i, xkji cannot be positive both at thesame time as shown in Figure 3.

4 Examples
4.1 The Cases where Assumption A1 and A2 hold naturally
As to many networks, we can naturally assume the assumption A1. As we noted before, however,Assumption A2 looks somewhat awkward. In the following two cases, however, the assumption A2
holds naturally.
13

k
r2n

2
destination
k
r1n

n

1

k
r2n
k
r1n

Figure 4: A network with one common destination and multiple originskr12

2
origin
k
r12

n

1

k
r1n

k
r1n

Figure 5: A network with one common origin and multiple destinations
4.1.1 Multi-class routing in networks with a common destination
Consider the individually/overall optimal routing problem for a multi-class network with one common
destination and multiple origins for a class (we call it the problem with a common destination for thesake of brevity). as shown in Figure 4. Note that the problems of load balancing in distributed computer
systems [14, 21] are equivalent to the routing problems in the networks with one common destinationand multiple origins. Clearly, the assumption A2 holds naturally for the networks. The two link-traﬃcloop-free properties, Theorem 3 and Corollary 2 shown in the above section hold for the networks underindividually and overall optimal routing.
In contrast, consider a case of noncooperative optimal routing with a ﬁnite (but plural) number ofplayers for this model, i.e., users are divided into groups each of which is controlled by a decision makerthat strives to optimize unilaterally the cost for its group only. Link-traﬃc loops have been found in theabove-mentioned load-balancing problems (shown in [12, 13] if the deﬁnition of class given in thosepapers is changed to be the same as the one given in this paper).
4.1.2 Multi-class routing in networks with a common origin
We proceed to consider another network where there are multiple destinations but only one common
origin (we call it the network with a common origin for the sake of brevity) as shown in Figure 5. The
two link-traﬃc loop-free properties, Theorem 3 and Corollary 2 shown in the above section hold for the14

x23 = y1234 = r14 /2 > 0

r14

2

4

1

3

r14

x32 = y1324 = r14 /2 > 0

Figure 6: A network with one origin and one destination that satisﬁes Assumption A1(1) but does notsatisfy A1(2)networks for individually and overall optimal routing. Clearly, the assumption A2 holds naturally for the
networks also.

4.2 Examples where Assumption A1 Does Not HoldIn this section, we examine two examples wherein either (1) or (2) in the assumption A1 is violated
whereas the assumption A2 holds. We see that in both examples the link-traﬃc loop-free property does
not hold. Therefore, we see that Assumption A1 is the condition that characterizes the category of
networks for which the link-traﬃc loop-free property holds in individually and overall optimal routing
in multi-class networks.
4.2.1 An example where (1) holds but (2) does not hold in the assumption A1
Consider a single-class network consisting of four nodes 1, 2, 3, and 4 (|C| = 1) and a single pairof origin 1 and destination 4, shown in Figure 6. Nodes 2 and 3 are connected by links (2,3) and(3,2). We consider the case where we have only two paths (1,2,3,4) and (1,3,2,4) connecting the O-D
pair (1,4), but (1,2,4) and (1,3,4) are not paths connecting the O-D pair (1,4), which violates (2) in theassumption A1. We assume that the cost of each link depends only on the ﬂow of the link and that
G12 (x) = G13 (x), G23 (x) = G32 (x) > 0, and G24 (x) = G34 (x) where x denotes the ﬂow through eachlink. Let the arrival rate at the origin be r14 > 0. Then, the optimal path ﬂows of the two paths are
identical, and x23 = y1234 = r14 /2 = y1324 = x32 > 0, which means that the network has a link-traﬃcloop. On the other hand, if (2) in the assumption A1 is to hold, then paths (1,2,4) and (1,3,4) need to be
additionally available. Then, in optimal routing, only paths (1,2,4) and (1,3,4) are used, and the network
has no link-traﬃc loop.
4.2.2 An example where (2) holds but (1) does not hold in the assumption A1
Consider a single-class network consisting of four nodes 1, 2, 3, and 4 (|C| = 1) shown in Figure 7.
We consider the case where we have two distinct O-D pairs 1-3 and 4-2. That is, (1,2,3) and (4,3,2)
are only paths. On the other hand, there exists no path connecting each of O-D pairs 1-2 and 4-3,
respectively, even though O-D pairs 1-2 and 4-3 have links (1,2) and (4,3) connecting the origin and thedestination, which violates (1) in the assumption A1. Let the arrival rates at origins be such that r13 > 0
and r42 > 0. Thus, there are two origin nodes (i.e., nodes 1 and 4) and two destination nodes (i.e., nodes
3 and 2) in the network. It is clear that we have only one solution such that x23 = y123 = r12 > 0 and
x32 = y432 = r42 > 0, which is the optimal solution to individually/overall optimal routing problem under15

x23 = y123 = r13 > 0
r13

1

3

2
r42

r13
4

r42

x32 = y432 = r42 > 0

Figure 7: A network with two origins and two destinations that satisﬁes Assumption A1(2) but does notsatisfy A1(1)the set of constraints (4) and y ∈ FS y . In this example, it is clear that we have a link-traﬃc loop, i.e.,
x23 > 0 and x32 > 0. On the other hand, if (1) in the assumption A1 holds, both of (1,2) and (4,3) canbe paths, and the solution under the constraint x ∈ FS x is such that x23 = r13 − r42 ≥ 0 and x32 = 0
if r13 ≥ r42 (under Assumption A2), which shows the freedom of link-traﬃc loops that holds under
Assumption A1.

5 Conclusion
In this paper, we have studied both individually and overall optimal routing problems for multi-classnetworks with generalized link-cost functions and network conﬁgurations. We have seen that there isan associate overall optimal routing problem to each individually optimal routing problem for multiclass networks with the same solution under some condition. We have discussed the existence anduniqueness of the solutions to overall and individually optimal routing. Furthermore, we have shown thatthe link-traﬃc loop-free property holds for the individually and overall optimal routing in a wide rangeof networks. While doing so, we have discussed the relation between the formulations with path and link
ﬂow patterns. We have shown the condition that characterizes the category of multi-class networks thathave the link-traﬃc loop-free property for overall and individually optimal routing.

References[1] E. Altman and H. Kameda. Equilibria for multiclass routing in multi-agent networks. In A.S.
Nowak and K. Szajowski, editors, Advances in Dynamic Games: Annals of International Society
of Dynamic Games Vol. 7, pages 343–367, Boston, 2005. Birkhäuser. (An extended version of
the paper that appeared in Proc. 40th IEEE Conference on Decision and Control (IEEE CDC’01),
Orlando, U.S.A., pp. 604–609, Dec. 2001).
[2] D. Bertsekas and R. Gallager. Data Networks, 2nd Ed. Prentice-Hall, Englewood Cliﬀs, 1992.
[3] J. E. Cohen and C. Jeﬀries. Congestion resulting from increased capacity in single-server queueing
networks. IEEE/ACM Trans. Networking, 5(2):305–310, April 1997.
[4] S. C. Dafermos. An extended traﬃc assignment model with applications to two-way traﬃc. Transportation Science, 5:366–389, 1971.
[5] S. C. Dafermos. The traﬃc assignment problem for multi-class user transportation networks. Transportation Science, 6:73–87, 1972.
[6] S. C. Dafermos and F. T. Sparrow. The traﬃc assignment problem for a general network. J.
Research of National Bureau of Standards-B, 73B(2):91–118, 1969.
16

[7] L. Fratta, M. Gerla, and L. Kleinrock. The ﬂow deviation method: An approach to store-andforward communication network design. Networks, 3:97–133, 1973.
[8] R. G. Gallager. A minimum delay routing algorithm using distributed computation. IEEE Trans.
Communications, COM-25(1):73–85, Jan. 1977.
[9] P. Gupta and P. R. Kumar. A system and traﬃc dependent adaptive routing algorithm for Ad Hoc
networks. In Proceedings of the 36th IEEE Conference on Decision and Control, pages 2375–2380,
San Diego, California, Dec. 1997.
[10] M. D. Intriligator. Mathematical Optimization and Economic Theory. Prentice-Hall, 1971.
[11] M. W. Jeter. Mathematical Programming: An Introduction to Optimization. Marcel Dekker, New
York, 1986.
[12] H. Kameda, E. Altman, T. Kozawa, and Y. Hosokawa. Braess-like paradoxes in distributed computer systems. IEEE Trans. Automatic Control, 45(9):1687–1691, 2000.
[13] H. Kameda and O. Pourtallier. Paradoxes in distributed decisions on optimal load balancing for
networks of homogeneous computers. J. ACM, 49(3):407–433, 2002.
[14] J. Li and H. Kameda. Load balancing problems for multiclass jobs in distributed/parallel computer
systems. IEEE Trans. Comput., 47(3):322–332, 1998.
[15] R. B. Myerson. Game Theory: Analysis of Conﬂict. Harvard University Press, Cambridge, Massachusetts, 1991.
[16] A. Orda, R. Rom, and N. Shimkin. Competitive routing in multiuser communication networks.
IEEE/ACM Trans. Networking, 1:614–627, 1993.
[17] M. Patriksson. The Traﬃc Assignment Problem – Models and Methods. VSP, Utrecht, 1994.
[18] R. T. Rockafellar. Convex Analysis. Princeton Univ. Press, 1970.
[19] T. Roughgarden. Designing networks for selﬁsh users is hard. In Proceedings of the 42nd AnnualIEEE Symposium on Foundation of Computer Science, pages 472–481, 2001. (to appear in a special
issue of Journal of Computer and System Sciences).
[20] T. Roughgarden and É. Tardos. How bad is selﬁsh routing? J. ACM, 49(2):236–259, 2002.
[21] A. N. Tantawi and D. Towsley. Optimal static load balancing in distributed computer systems. J.
ACM, 32(2):445–465, April 1985.
[22] J. G. Wardrop. Some theoretic aspects of road traﬃc research. Proc. Inst. Civ. Eng., Part 2, 1:325–
378, 1952.

17