# Optimal Routing for Multiclass Networks

Authors: Hisao Kameda; Jie Li; Eitan Altman
Journal: Advances in Operations Research
 (2011)

---

## Abstract

Overall optimal routing is considered along with individually optimal routing for networks with
nodes interconnected in a generally configured manner and with multiple classes of users. The two
problems are formulated, and we discuss the mutual equivalence between the problems, the existence
and uniqueness of solutions, and the relation between the formulations with path and link flow patterns.
We show that a link-traffic loop-free property holds within each class for both individually and
overall optimal routing for a wide range of networks, and we show the condition that characterizes the
category of networks for which the property holds.


---

## Body

## 1. Introduction

There are two typical approaches for optimal routing in networks. (1) One arises in the context of minimizing the overall cost (overall mean delay) of all users (e.g., packets) from the arrival (origin) node of each user to its destination node through a number of links over the entire network. The optimal routing policy with this framework is called theoverall optimal routing policy. (2) A second approach is a distributed one in which one seeks 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 the result of allowing each user the decision on which path to route. This approach is called the individually optimal routing. The situation where each user has unilaterally minimized its cost is called a Wardrop equilibrium [1, 2] or a Nash equilibrium where no user has any incentive to make a unilateral decision to change its route.In computer and communication networks, most work has focused on overall optimal routing (e.g., [3–5]). 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 in computer and communication networks, and some research results have been obtained [6–9].In most studies on optimal routing problems for communication networks in the literature (e.g., [3–5, 7, 8, 10]), the link cost is modeled as a simple function dependent only on the link flow itself. We call this the traditional link-cost model. In this paper, however, the cost on a link of a network is modeled by a function of the flows of all links in the entire network. We call this a general link-cost model. For example, in a wireless communication network, where, when a link connecting two nodes has more flow and, thus, uses more power, neighboring links may have less capacity. This paper studies optimal routing problems in general link-cost models for generally configured networks with multiple classes of users. We call a network with multiple-class users a multiclass network. We note, however, that, in these optimization problems, the cost to be optimized depends only on the link flow pattern while the instrument (the set of decision variables) is the path flow pattern.In this paper, we discuss individually and overall optimal routing problems on which Dafermos has obtained some basic results [11–13]. 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 both available to the class with/without fixing the arrival rate at each origin and the departure rate at each destination. (2) The link-traffic loop-free property is discussed. (3) The relation between the case where the instrument is the path flow pattern and the case where it is the link flow pattern is discussed. In particular, we note that, by definition, a path flow pattern determines a unique link flow pattern whereas it may not be sure whether for a link flow pattern there exists a path flow pattern that induces it, that is, whether a given link flow pattern is realizable.We confirm the necessary and sufficient condition that, for an individually optimal routing problem under our assumptions, there exists an overall optimal routing problem associated to it, and that both have the same solution. We discuss the existence and uniqueness of the solutions to the overall and individually optimal routing. Furthermore, we show that the link-traffic loop-free property holds for each class, for the individually and overall optimal routing in general link-cost models of  multiclass networks. We pay much attention to the relation between the cases where the sets of the control variables are, respectively, the path and link flow patterns. We show the condition that characterizes the category of networks where the link-traffic loop-free property holds for each class. Some examples are discussed. In contrast, note that, even in the networks where the link-traffic loop-free property holds for each class in overall and individually optimal routing, it does not always hold in noncooperative optimal routing by a finite (but plural) number of decision makers, where the decision makers strive to optimize unilaterally the cost of the users under its control. Such counter-examples are given in [14, 15] (with the definition 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 infinitely many infinitesimal 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  multiclass networks is provided in Section2.3. Section 2.4 discusses the existence and uniqueness of individually and overall optimal routing for  multiclass networks. Section 3 discusses the link-traffic loop-free property for the individually and overall optimal routing for  multiclass networks. Some examples are shown in Section 4. Section 5 concludes the paper.


## 2. Problem Formulation and Solutions

Consider a network consisting ofn nodes numbered, 1,2,…,n, interconnected in an arbitrary fashion by links. N and L, respectively, denote the sets of nodes and links. There are  multiclass 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 (commodities) do not change their classes during their trips from origins and destinations. Thus, the users (commodities) of different classes can be different. We call links available to class-k users “class-k links.” Lk denotes the set of “class-k links.” Then, L=∪k∈CLk. By a 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),…,(vn′-1,vn′) that any class-k user can pass through where v1,v2,…,vn′ are distinct nodes, v1=o, and vn′=d. Then, the path is denoted by (o,v2,…,vn′-1,d). We call node o an origin, the node d adestination, 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.Ifvi is the same as node vj 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 flows 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 ano-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-d pair, all possible series of link connections for the class between the o-d pair are also paths of the class 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 2.1.
As seen later in Sections3 and 4, assumption (A1) presents the condition that characterizes the category of networks that have the link-traffic loop-free property within each class for overall and individually 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, that the assumption (A2) is most general. Consider a network, namedℳ, where each class-k user can leave the network at any available destination without fixing the class-k departure rate at each destination. We imagine another network, named ℳ′, where one class-k “final” destination is added to the network ℳ and that each of the class-k destinations in ℳ is connected to the class-k final destination via a class-kzero-cost link in the network ℳ′ for every class k (later in this section, we will describe zero-cost links along with the definition of link-cost functions, Gijk). Then, the imagined network ℳ′ can be regarded as the one with multiple-origins and one common destination for class k as shown in Section 4.1.1 and satisfies assumptions (A1) and (A2). The optimal solutions of the networks ℳ and ℳ′ 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 fixing the class-k arrival rate at each origin but with the departure rate at each class-k destination being fixed. We can also consider a network where each class-k user can enter at any origin and leave from any destination without fixing the arrival and departure rates at any origin and destination for class k and with fixing 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 and one final destination are added for class-k.
We therefore see that assumption (A2) is most general and covers all three kinds of networks each of 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 classk are denoted by 𝒪k and 𝒟k, respectively. The sets of all possible paths which originate from an o∈𝒪k and which are destined for a d∈𝒟k, for class k, are denoted by 𝒫o-k and 𝒫-dk, respectively. The set of all paths in the network for class k is denoted by 𝒫k, each element of which must appear in a 𝒫o-k and in a 𝒫-dk, that is, 𝒫k=∪o∈𝒪k𝒫o-k=∪d∈𝒟k𝒫-dk. For every origin o∈𝒪k and for every destination d∈𝒟k, respectively, let ro-k and r-dk (k∈C) be the nonnegative external class-k user traffic demands that originate at node o for all destinations d∈𝒟k, and that is destined for node d from all origins o∈𝒪k.For a pathp∈𝒫o-k, ypk denotes the part of ro-k which flows through path p. Similarly for a path p∈𝒫-dk, ypk is called the class-k  path flow through the path p. We have the following relations:(2.1)∑p∈Po-kypk=ro-k,o∈Ok,(2.2)∑p∈P-dkypk=r-dk,d∈Dk,(2.3)ypk≥0,p∈Pk,k∈C.
Naturally, ∑o∈𝒪kro-k=∑d∈𝒟kr-dk. Denote the path flow pattern by y=[yk], where yk=[ypk]. By a feasible path flow pattern, we mean y which satisfies relations (2.1), (2.2), and (2.3). Denote by FSy the set of feasible path flow patterns. Clearly, FSy is convex, closed, and bounded.Denote byxijk the class-k user flow rate, also called the class-kflow, through link (i,j). Let x=[xk] where xk=[xijk]. Furthermore, let x=[xij] where xij=[xijk]. We call x the link flow pattern. Since a link appears in a path at most once, a class-k link flow is expressed by class-k path flows as follows:(2.4)xijk=∑p∈Pkδijpypk,(i,j)∈Lk,k∈C,
where (2.5)δijp={1,iflink(i,j)iscontainedinpathp,0,otherwise.
If link (i,j) is included in path p, we also express it as (i,j)∈p. From (2.4), we notice that a path flow pattern y induces a unique link flow pattern x, while it is possible that more than one path flow pattern y induces the same link flow pattern x. Moreover, for given x, it may not be sure whether there exists a path flow pattern y that induces x.LetGijk be the class-k link cost of sending a class-k user from node i to node j through link (i,j). Gijk is a function of all link flows x. We assume that, for most of the link costs, Gijk(x) is a positive and differentiable function that is convex in x and, in particular, that Gijk(x) is strictly convex in xijk for all i,(j≠i),k. We also consider the possible existence of zero-cost links the flows of which do not influence other link costs, that is, for some i′,j′,k′, Gi′j′k′(x)=0 for all x, and xi′j′k′ does not affect any other Gijk. xs denotes the vector that consists of the elements xijk such that each corresponding Gijk(x) is strictly convex in xijk, and x-s denotes the vector that consists of the elements xi′j′k′ each of which is the flow through the class-k′ zero-cost link (i′,j′). Denote by Lsk and by L-sk, respectively, the sets of class-k links with nonzero cost and with zero cost. Then we assume that Gijk(x) is strictly convex in xs for all i,(j≠i),k.Dpk(x) denotes the class-k cost of a path p. Then,(2.6)Dpk(x)=∑(i,j)∈LkδijpGijk(x),p∈Pk,k∈C.


### 2.1. Overall Optimal Routing for Multiclass Networks

By using (2.4) and (2.6), the overall cost of users over all classes is expressed as (2.7)D(x)=1R∑k∈C∑p∈PkypkDpk(x)=1R∑k∈C∑(i,j)∈LkxijkGijk(x),
where R=∑k∈C∑o∈𝒪kro-k=∑k∈C∑d∈𝒟kr-dk.Thus, considering (2.4), the overall optimal routing problem is expressed as follows:(2.8)min⁡yD(x(y))subjecttoy∈FSy.
We have assumed that Gijk(x) is convex in x and, in particular, strictly convex in xs, for all i,(j≠i),k. Then, we can see that D(x) is convex in x and strictly convex in xs (by noting that ∑k∈C∑(i,j)∈Lk{αx(1)i,jk+(1-α)x(2)i,jk}Gi,jk(αx(1)+(1-α)x(2))=∑k∈C∑(i,j)∈Lsk{αx(1)i,jk+(1-α)x(2)i,jk}Gi,jk(αx(1)s+(1-α)x(2)s)<α∑k∈C∑(i,j)∈Lskx(1)i,jkGi,jk(x(1)s)+(1-α)∑k∈C∑(i,j)∈Lskx(2)i,jkGi,jk(x(2)s)+α(1-α)∑k∈C∑(i,j)∈Lsk(x(1)i,jk-x(2)i,jk)[Gi,jk(x(2)s)-Gi,jk(x(1)s)]<α∑k∈C∑(i,j)∈Lskx(1)i,jkGi,jk(x(1)s)+(1-α)∑k∈C∑(i,j)∈Lskx(2)i,jkGi,jk(x(2)s)=α∑k∈C∑(i,j)∈Lkx(1)i,jkGi,jk(x(1))+(1-α)∑k∈C∑(i,j)∈Lkx(2)i,jkGi,jk(x(2)) for 0<α<1 and for x(1)s≠0 or x(2)s≠0.) Then, we see that D(x) is convex in y, which can be easily shown as follows: Indeed, the relation (2.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.Consider the following Lagrangian function:(2.9)L(y,ϕ)=RD(x)+∑k∈C[∑o∈Okϕo-k(ro-k-∑p∈Po-kypk)+∑d∈Dkϕ-dk(r-dk-∑p∈P-dkypk)],
where ϕo-k and ϕ-dk are Lagrange multipliers. Define gij(x) as follows:(2.10)gijk(x)=R∂∂xijkD(x).
Then, the path flow pattern y that satisfies the following relation derived from the Kuhn-Tucker condition is a solution for overall optimal routing if such a flow pattern y exists,(2.11)∑(i,j)∈pgijk(x)=βo,dk,foryp>0,∑(i,j)∈pgijk(x)≥βo,dk,foryp=0,p∈Pk,o∈Ok,d∈Dk,k∈C,y∈FSy,
where βo,dk=ϕo-k+ϕ-dk. We recall that 𝒫k=∪o∈𝒪k𝒫o-k=∪d∈𝒟k𝒫-dk.


### 2.2. Individually Optimal Routing for Multiclass Networks

Informally, we define 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 user of 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 flow patternx of individually optimal routing is a Wardrop equilibrium [2], or a Nash equilibrium point in the sense of noncooperative game [16]. Thus, we define the equilibrium condition of the individually optimal routing as follows.Definition 2.2.
A path flow patterny is said to satisfy the equilibrium condition of the individually optimal routing if and only if the following relation holds:
(2.12)Dpk(x)=∑(i,j)∈pGijk(x)=Ao,dk,foryp>0,Dpk(x)=∑(i,j)∈pGijk(x)≥Ao,dk,foryp=0,p∈Pk,o∈Ok,d∈Dk,k∈C,y∈FSy.We recall that𝒫k=∪o∈𝒪k𝒫o-k=∪d∈𝒟k𝒫-dk. We call the path flow pattern y the solution of the individually optimal routing if it satisfies the above equilibrium condition. It is a Wardrop equilibrium [2].Remark 2.3.
The above definition 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 not less than those of the unused paths. But, this situation may not reflect 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 Remark2.1.


### 2.3. Relation between Individually and Overall Optimal Routing for Multiclass Networks

We note that link-cost functionGijk(x)((i,j)∈Lk,k∈C) is differentiable, that is, ∂Gijk/∂xlmk′((i,j)∈Lk,(l,m)∈Lk′,k,k′∈C) exists. In order to obtain an optimization problem that gives the same solution as the equilibrium condition (2.12) of the individually optimal routing, we consider the following function D̂(x) as described as follows. From Patriksson [1, page 75, Theorem 3.4], the necessary and sufficient condition that we can construct a new overall cost function D̂(x) for the same network as that of (2.8), such that(2.13)Gijk(x)=R∂D̂(x)∂xijk,(i,j)∈Lk,k∈C,
is that the matrix of partial derivatives of link-cost functions, Λ(x)=[∂Gijk/∂xlmk′], is symmetric (i.e., ∂Gijk/∂xlmk′=∂Glmk′/∂xijk for all (i,j)∈Lk,(l,m)∈Lk′,k,k′∈C).Moreover, we consider a submatrix,Λs(x), of Λ(x) that contains the ((ijk),(i′j′k′))th elements such that both xijk and xi′j′k′ are in xs. We note that the elements of Λ(x) that are not in Λs(x) are all zero. We assume that Λs(x) is positive definite. Then, if the above symmetry condition holds, D̂(x) is strictly convex in xs, Λ(x) is semipositive definite, and D̂(x) is convex in x. In the traditional link-cost models, Λ(x) is also symmetric and semipositive definite (see, e.g., [6, 9]). Denote by (x-(ijk),xij′k) the vector with the component xijk of x replaced by xij′k. If Λ(x) is symmetric, the following satisfies (2.13):(2.14)D̂(x)=1R∑k∈C|Lk|{∑k∈C∑(i,j)∈Lk∫0xijkGijk(x-(ijk),xij′k)dxij′k}.D̂ corresponds to what is often called a potential in game theory [17]. We define(2.15)Ĝijk(x)=1xijk∑k∈C|Lk|∫0xijkGijk(x-(ijk),xij′k)dxij′k,(i,j)∈Lk,k∈C.
Then, we regard Ĝijk as a new class-k link cost on link (i,j). Thus, (2.16)D̂(x)=1R∑k∈C∑(i,j)∈LkxijkĜijk(x).
We recall that, for xi′j′k′∈x-s, Ĝi′j′k′=0 and xi′j′k′ would not influence other Ĝijk(i′≠i or j′≠j). Thus, considering (2.4), as an optimization problem that gives the same solution as the equilibrium condition (2.12) of the individually optimal routing problem, we have the following overall optimization problem:(2.17)min⁡yD̂(x(y))subjectto(2.4)andy∈FSy.We call the overall optimization problem (2.17) an associate problem to the individually optimal routing problem. We note that it is another overall optimal routing problem. Consider the following Lagrangian function(2.18)L̂(y,ϕ)=RD̂(x)+∑k∈C[∑o∈Okϕ̂o-k(ro-k-∑p∈Po-kypk)+∑d∈Dkϕ̂-dk(r-dk-∑p∈P-dkypk)],
where ϕ̂o-k and ϕ̂-dk are Lagrange multipliers. Then, the path flow pattern y that satisfies 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 flow pattern y exists;(2.19)∑(i,j)∈pGijk(x)=Ao,dk,foryp>0,∑(i,j)∈pGijk(x)≥Ao,dk,foryp=0,p∈Pk,o∈Ok,d∈Dk,k∈C,y∈FSy,
where Ao,dk=ϕ̂o-k+ϕ̂-dk. We see that the above is equivalent to the condition (2.12) describing the solution of the corresponding individually optimal routing problem. Then, we have the following lemma.Lemma 2.4.
A path flow patterny is a solution to associate problem (2.17) if and only if it satisfies the equilibrium condition (2.12).On the other hand, if we regardgijk(x) as a new class-k link cost on link (i,j), then we have the equilibrium condition (2.11) for the individual optimization that is an associate condition to the overall optimal routing problem for  multiclass networks with Gijk(x) being the class-k cost on link (i,j).Corollary 2.5.
A path flow patterny satisfies the associate condition (2.11) if and only if it is a solution to the overall optimization problem (2.8).


### 2.4. Existence and Uniqueness

In this section, we study the existence and uniqueness of the solutions to overall and individually optimal routing problems for  multiclass networks. We first 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 (2.17) as long as the symmetry condition given in Section 2.3 holds, we investigate the existence and uniqueness of the solution to the associate problem (2.17) and, then, to the individually optimal routing problem (2.12).Denote the set of feasible link flow patterns byFSx. That is,(2.20)FSx={x∣Thereexistsysuchthatxandysatisfy(2.4)andy∈FSy}.
Clearly, the set {(x,y)∣(x,y)satisfies(2.4)andy∈FSy} is convex, closed, and bounded. Then, by noting that the orthogonal projection of a convex set onto a subspace is another convex set (see, e.g., [18]), the set FSx is convex in x and a closed and bounded hyperplane (see, e.g., [18]). Note that D(x) in (2.8) is continuous in x and, thus, in y, and that the feasible set FSy is closed and bounded. Then, there exists a solution of path flow patterns y to (2.8), according to the Weierstrass theorem (e.g., [19, 20]). Since D(x) is continuous and convex in x and strictly convex in xs, we have the following.Theorem 2.6.
For the overall optimal routing problem for  multiclass networks (2.8), an optimal path flow pattern y exists and, in particular, the resulting xs is unique.The uniqueness ofxs is shown by contradiction as follows. Suppose that xs is not unique and that both x1=(xs1,x-s1) and x2=(xs2,x-s2) give the minimum Dmin of D(x), for xs1≠xs2. Then, from the convexity of the feasible region of x, αx1+(1-α)x2, for some α (0<α<1), is also in the feasible region, and (2.21)D(αx1+(1-α)x2)=D(αxs1+(1-α)xs2,αx-s1+(1-α)x-s2)<αD(xs1,αx-s1+(1-α)x-s2)+(1-α)D(xs2,αx-s1+(1-α)x-s2)=αDmin⁡+(1-α)Dmin⁡=Dmin⁡,
where the inequality follows from the strict convexity of D(x) in xs 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 xs.For the individually optimal routing problem, we note thatD̂(x) in (2.17) is continuous in x and, thus, in y, and that FSy is closed and bounded. Then, similarly as above, there exists a solution of y to (2.17) according to the Weierstrass theorem (e.g., [19, 20]). With Lemma 2.4 and by noting that D̂(x) is convex in x and strictly convex in xs, we have the existence and uniqueness of a solution to individually optimal routing as follows.Theorem 2.7.
For the individually optimal routing problem, there exists a solutiony to (2.17) and thus that satisfies (2.12), and, in particular, the resulting xs is unique.For the overall optimal routing problem, consider the following optimization problem that involves only the link flow patternx and does not involve the path flow pattern y:(2.22)min⁡xD(x)subjecttox∈FSx.
Similarly as above, we see that there exists a solution of x to (2.22) according to the Weierstrass theorem (e.g., [19, 20]). The optimization problem (2.22) is a nonlinear convex optimization problem, but, clearly, (2.22) gives the solution x that is the same as the link flow pattern x that the solutions y to (2.8), thus (2.11) results in.For the individually optimal routing problem, consider the following optimization problem that involves only the link flow patternx and does not involve the path flow pattern y:(2.23)min⁡xD̂(x)subjecttox∈FSx.
Similarly as above, we see that there exists a solution of x to (2.23), according to the Weierstrass theorem (e.g., [19, 20]). The optimization problem (2.23) is another nonlinear convex optimization problem, but, clearly, (2.23) gives the solution x that is the same as the link flow pattern x that the solutions y to (2.17), thus (2.19) (i.e., (2.12)) results in.


## 2.1. Overall Optimal Routing for Multiclass Networks

By using (2.4) and (2.6), the overall cost of users over all classes is expressed as (2.7)D(x)=1R∑k∈C∑p∈PkypkDpk(x)=1R∑k∈C∑(i,j)∈LkxijkGijk(x),
where R=∑k∈C∑o∈𝒪kro-k=∑k∈C∑d∈𝒟kr-dk.Thus, considering (2.4), the overall optimal routing problem is expressed as follows:(2.8)min⁡yD(x(y))subjecttoy∈FSy.
We have assumed that Gijk(x) is convex in x and, in particular, strictly convex in xs, for all i,(j≠i),k. Then, we can see that D(x) is convex in x and strictly convex in xs (by noting that ∑k∈C∑(i,j)∈Lk{αx(1)i,jk+(1-α)x(2)i,jk}Gi,jk(αx(1)+(1-α)x(2))=∑k∈C∑(i,j)∈Lsk{αx(1)i,jk+(1-α)x(2)i,jk}Gi,jk(αx(1)s+(1-α)x(2)s)<α∑k∈C∑(i,j)∈Lskx(1)i,jkGi,jk(x(1)s)+(1-α)∑k∈C∑(i,j)∈Lskx(2)i,jkGi,jk(x(2)s)+α(1-α)∑k∈C∑(i,j)∈Lsk(x(1)i,jk-x(2)i,jk)[Gi,jk(x(2)s)-Gi,jk(x(1)s)]<α∑k∈C∑(i,j)∈Lskx(1)i,jkGi,jk(x(1)s)+(1-α)∑k∈C∑(i,j)∈Lskx(2)i,jkGi,jk(x(2)s)=α∑k∈C∑(i,j)∈Lkx(1)i,jkGi,jk(x(1))+(1-α)∑k∈C∑(i,j)∈Lkx(2)i,jkGi,jk(x(2)) for 0<α<1 and for x(1)s≠0 or x(2)s≠0.) Then, we see that D(x) is convex in y, which can be easily shown as follows: Indeed, the relation (2.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.Consider the following Lagrangian function:(2.9)L(y,ϕ)=RD(x)+∑k∈C[∑o∈Okϕo-k(ro-k-∑p∈Po-kypk)+∑d∈Dkϕ-dk(r-dk-∑p∈P-dkypk)],
where ϕo-k and ϕ-dk are Lagrange multipliers. Define gij(x) as follows:(2.10)gijk(x)=R∂∂xijkD(x).
Then, the path flow pattern y that satisfies the following relation derived from the Kuhn-Tucker condition is a solution for overall optimal routing if such a flow pattern y exists,(2.11)∑(i,j)∈pgijk(x)=βo,dk,foryp>0,∑(i,j)∈pgijk(x)≥βo,dk,foryp=0,p∈Pk,o∈Ok,d∈Dk,k∈C,y∈FSy,
where βo,dk=ϕo-k+ϕ-dk. We recall that 𝒫k=∪o∈𝒪k𝒫o-k=∪d∈𝒟k𝒫-dk.


## 2.2. Individually Optimal Routing for Multiclass Networks

Informally, we define 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 user of 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 flow patternx of individually optimal routing is a Wardrop equilibrium [2], or a Nash equilibrium point in the sense of noncooperative game [16]. Thus, we define the equilibrium condition of the individually optimal routing as follows.Definition 2.2.
A path flow patterny is said to satisfy the equilibrium condition of the individually optimal routing if and only if the following relation holds:
(2.12)Dpk(x)=∑(i,j)∈pGijk(x)=Ao,dk,foryp>0,Dpk(x)=∑(i,j)∈pGijk(x)≥Ao,dk,foryp=0,p∈Pk,o∈Ok,d∈Dk,k∈C,y∈FSy.We recall that𝒫k=∪o∈𝒪k𝒫o-k=∪d∈𝒟k𝒫-dk. We call the path flow pattern y the solution of the individually optimal routing if it satisfies the above equilibrium condition. It is a Wardrop equilibrium [2].Remark 2.3.
The above definition 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 not less than those of the unused paths. But, this situation may not reflect 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 Remark2.1.


## 2.3. Relation between Individually and Overall Optimal Routing for Multiclass Networks

We note that link-cost functionGijk(x)((i,j)∈Lk,k∈C) is differentiable, that is, ∂Gijk/∂xlmk′((i,j)∈Lk,(l,m)∈Lk′,k,k′∈C) exists. In order to obtain an optimization problem that gives the same solution as the equilibrium condition (2.12) of the individually optimal routing, we consider the following function D̂(x) as described as follows. From Patriksson [1, page 75, Theorem 3.4], the necessary and sufficient condition that we can construct a new overall cost function D̂(x) for the same network as that of (2.8), such that(2.13)Gijk(x)=R∂D̂(x)∂xijk,(i,j)∈Lk,k∈C,
is that the matrix of partial derivatives of link-cost functions, Λ(x)=[∂Gijk/∂xlmk′], is symmetric (i.e., ∂Gijk/∂xlmk′=∂Glmk′/∂xijk for all (i,j)∈Lk,(l,m)∈Lk′,k,k′∈C).Moreover, we consider a submatrix,Λs(x), of Λ(x) that contains the ((ijk),(i′j′k′))th elements such that both xijk and xi′j′k′ are in xs. We note that the elements of Λ(x) that are not in Λs(x) are all zero. We assume that Λs(x) is positive definite. Then, if the above symmetry condition holds, D̂(x) is strictly convex in xs, Λ(x) is semipositive definite, and D̂(x) is convex in x. In the traditional link-cost models, Λ(x) is also symmetric and semipositive definite (see, e.g., [6, 9]). Denote by (x-(ijk),xij′k) the vector with the component xijk of x replaced by xij′k. If Λ(x) is symmetric, the following satisfies (2.13):(2.14)D̂(x)=1R∑k∈C|Lk|{∑k∈C∑(i,j)∈Lk∫0xijkGijk(x-(ijk),xij′k)dxij′k}.D̂ corresponds to what is often called a potential in game theory [17]. We define(2.15)Ĝijk(x)=1xijk∑k∈C|Lk|∫0xijkGijk(x-(ijk),xij′k)dxij′k,(i,j)∈Lk,k∈C.
Then, we regard Ĝijk as a new class-k link cost on link (i,j). Thus, (2.16)D̂(x)=1R∑k∈C∑(i,j)∈LkxijkĜijk(x).
We recall that, for xi′j′k′∈x-s, Ĝi′j′k′=0 and xi′j′k′ would not influence other Ĝijk(i′≠i or j′≠j). Thus, considering (2.4), as an optimization problem that gives the same solution as the equilibrium condition (2.12) of the individually optimal routing problem, we have the following overall optimization problem:(2.17)min⁡yD̂(x(y))subjectto(2.4)andy∈FSy.We call the overall optimization problem (2.17) an associate problem to the individually optimal routing problem. We note that it is another overall optimal routing problem. Consider the following Lagrangian function(2.18)L̂(y,ϕ)=RD̂(x)+∑k∈C[∑o∈Okϕ̂o-k(ro-k-∑p∈Po-kypk)+∑d∈Dkϕ̂-dk(r-dk-∑p∈P-dkypk)],
where ϕ̂o-k and ϕ̂-dk are Lagrange multipliers. Then, the path flow pattern y that satisfies 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 flow pattern y exists;(2.19)∑(i,j)∈pGijk(x)=Ao,dk,foryp>0,∑(i,j)∈pGijk(x)≥Ao,dk,foryp=0,p∈Pk,o∈Ok,d∈Dk,k∈C,y∈FSy,
where Ao,dk=ϕ̂o-k+ϕ̂-dk. We see that the above is equivalent to the condition (2.12) describing the solution of the corresponding individually optimal routing problem. Then, we have the following lemma.Lemma 2.4.
A path flow patterny is a solution to associate problem (2.17) if and only if it satisfies the equilibrium condition (2.12).On the other hand, if we regardgijk(x) as a new class-k link cost on link (i,j), then we have the equilibrium condition (2.11) for the individual optimization that is an associate condition to the overall optimal routing problem for  multiclass networks with Gijk(x) being the class-k cost on link (i,j).Corollary 2.5.
A path flow patterny satisfies the associate condition (2.11) if and only if it is a solution to the overall optimization problem (2.8).


## 2.4. Existence and Uniqueness

In this section, we study the existence and uniqueness of the solutions to overall and individually optimal routing problems for  multiclass networks. We first 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 (2.17) as long as the symmetry condition given in Section 2.3 holds, we investigate the existence and uniqueness of the solution to the associate problem (2.17) and, then, to the individually optimal routing problem (2.12).Denote the set of feasible link flow patterns byFSx. That is,(2.20)FSx={x∣Thereexistsysuchthatxandysatisfy(2.4)andy∈FSy}.
Clearly, the set {(x,y)∣(x,y)satisfies(2.4)andy∈FSy} is convex, closed, and bounded. Then, by noting that the orthogonal projection of a convex set onto a subspace is another convex set (see, e.g., [18]), the set FSx is convex in x and a closed and bounded hyperplane (see, e.g., [18]). Note that D(x) in (2.8) is continuous in x and, thus, in y, and that the feasible set FSy is closed and bounded. Then, there exists a solution of path flow patterns y to (2.8), according to the Weierstrass theorem (e.g., [19, 20]). Since D(x) is continuous and convex in x and strictly convex in xs, we have the following.Theorem 2.6.
For the overall optimal routing problem for  multiclass networks (2.8), an optimal path flow pattern y exists and, in particular, the resulting xs is unique.The uniqueness ofxs is shown by contradiction as follows. Suppose that xs is not unique and that both x1=(xs1,x-s1) and x2=(xs2,x-s2) give the minimum Dmin of D(x), for xs1≠xs2. Then, from the convexity of the feasible region of x, αx1+(1-α)x2, for some α (0<α<1), is also in the feasible region, and (2.21)D(αx1+(1-α)x2)=D(αxs1+(1-α)xs2,αx-s1+(1-α)x-s2)<αD(xs1,αx-s1+(1-α)x-s2)+(1-α)D(xs2,αx-s1+(1-α)x-s2)=αDmin⁡+(1-α)Dmin⁡=Dmin⁡,
where the inequality follows from the strict convexity of D(x) in xs 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 xs.For the individually optimal routing problem, we note thatD̂(x) in (2.17) is continuous in x and, thus, in y, and that FSy is closed and bounded. Then, similarly as above, there exists a solution of y to (2.17) according to the Weierstrass theorem (e.g., [19, 20]). With Lemma 2.4 and by noting that D̂(x) is convex in x and strictly convex in xs, we have the existence and uniqueness of a solution to individually optimal routing as follows.Theorem 2.7.
For the individually optimal routing problem, there exists a solutiony to (2.17) and thus that satisfies (2.12), and, in particular, the resulting xs is unique.For the overall optimal routing problem, consider the following optimization problem that involves only the link flow patternx and does not involve the path flow pattern y:(2.22)min⁡xD(x)subjecttox∈FSx.
Similarly as above, we see that there exists a solution of x to (2.22) according to the Weierstrass theorem (e.g., [19, 20]). The optimization problem (2.22) is a nonlinear convex optimization problem, but, clearly, (2.22) gives the solution x that is the same as the link flow pattern x that the solutions y to (2.8), thus (2.11) results in.For the individually optimal routing problem, consider the following optimization problem that involves only the link flow patternx and does not involve the path flow pattern y:(2.23)min⁡xD̂(x)subjecttox∈FSx.
Similarly as above, we see that there exists a solution of x to (2.23), according to the Weierstrass theorem (e.g., [19, 20]). The optimization problem (2.23) is another nonlinear convex optimization problem, but, clearly, (2.23) gives the solution x that is the same as the link flow pattern x that the solutions y to (2.17), thus (2.19) (i.e., (2.12)) results in.


## 3. Link-Traffic Loop-Free Property

In this section, we show a property that holds for the overall/individually optimal routing for  multiclass networks, called thelink-traffic loop-free property. The link-traffic loop-free property is such that there exists no loop that consists of a sequence of links (v1,v2),(v2,v3),…,(vn′-1,vn′) where v1,v2,…,vn′ are distinct nodes while v1=vn′ such that class-k link flow xv1,v2k>0,xv2,v3k>0,xvn′-1,vn′k>0(k∈C) (Figure 1). Although it is evident that no path has a loop, it is not clear whether there exists no loop for link flows of each class. For example, if assumption (A1) does not hold, as shown by the example given later, there may exist loops for link flows in the network.Figure 1
Link-traffic loop-free property in overall/individually optimal routing.From relations (2.1), (2.2), and (2.4), we have the following flow-balance relation:(3.1)ri-k(ifi∈Ok)+∑l∈Vikxlik=r-ik(ifi∈Dk)+∑l∈Vikxilk,i=1,2,…,n-1,k∈C,
where Vik is the set of immediately neighboring nodes of node i for class k, that is, Vik={j∣(i,j)∈Lk,or(j,i)∈Lk}. The constraint with respect to i=n can be derived by summing up both sides of the above constraints for i=1,2,…,n-1. Define FSI as follows: (3.2)FSI={x∣xsatisfies(3.1)andx≥0}.
Note that the set of FSI is convex, closed, and bounded. Note, furthermore, that FSI includes but may not be identical to FSx.We have the overall optimal routing problem (and the associate problem for the individually optimal routing) with the following new constraint (withD(x) and Gijk(x), resp., to be replaced by D̂(x) and Ĝijk(x) for the associate problem for the individually optimal routing):(3.3)min⁡xD(x)subjecttox∈FSI.The necessary and sufficient condition that a solution to the above overall/individually optimal routing problem satisfies is given as follows.Lemma 3.1.
The link flow patternx is an optimal solution to the overall (and individually) optimal routing problem with constraint x∈FSI (3.3) if and only if x satisfies the following set of relations (with gijk(x) to be replaced by Gijk(x) for the individually optimal routing problem):
(3.4)αik-gijk(x)=αjk,forxijk>0,(i,j)∈Lk,k∈C,αik-gijk(x)≤αjk,forxijk=0,(i,j)∈Lk,k∈C,
subject to x∈FSI, where αik(i∈N,k∈C) are Lagrange multipliers.Proof.
We show the case of overall optimization. The case of individual optimization is shown in a similar way. To obtain an optimal solution to problem (3.3), we form the Lagrangian function as follows:
(3.5)H(x,α)=RD(x)+∑k∈C∑i=1n-1αik[ri-k(ifi∈Ok)+∑l∈Vixlik-r-ik(ifi∈Dk)-∑l∈Vixilk],
where αik are Lagrange multipliers.
Since functionD(x) is continuous and convex in x (and strictly convex in xs) and FSI is convex, closed, and bounded, there exists a solution (that has a unique xs) to problem (3.3) similarly as Theorem 2.6. Thus, the link flow pattern x that satisfies the following Kuhn-Tucker condition is an optimal solution (that has a unique xs) to problem (3.3) (see, e.g., [19]):
(3.6)∂H∂xijk=gijk(x)+αjk-αik≥0,xijk∂H∂xijk=xijk(gijk(x)+αjk-αik)=0,xijk≥0,(i,j)∈Lk,k∈C,ri-k(ifi∈Ok)+∑l∈Vixlik=r-ik(ifi∈Dk)+∑l∈Vixilk,i=1,2,…,n-1,k∈C.
Rearranging the above relations, we have,
(3.7)αik-gijk(x)=αjk,forxijk>0,αik-gijk(x)≤αjk,forxijk=0,(i,j)∈Lk,k∈C,x∈FSI.
The above set of relations is equivalent to the set of relations (3.4) and x∈FSI, and it is the necessary and sufficient condition for a link flow pattern x to be a solution to the overall optimal routing problem (3.3).With Lemma3.1, we proceed to have the link-traffic loop-free property in the overall/individually optimal routing for problem (3.3).Lemma 3.2.
The class-k link traffic in a solution to the overall (and individually) optimal routing problem with constraint x∈FSI (3.3) is loop-free for all k∈C. That is, there exists no class-k link traffic such that xv1v2k>0, xv2v3k>0,…,xvm-1vmk>0, xvmv1k>0 (for all k∈C), where v1,v2,…,vm are distinct nodes in the solution to the overall (and individually) optimal routing problem and where at least one of the links involved is not a zero-cost link.Proof.
We show the case of overall optimization. It is proved by contradiction. Assume that there exists class-k link traffic in the solution to overall optimal routing problem (3.3) for  multiclass users such as xv1v2k>0, xv2v3k>0,…,xvm-1vmk>0, xvmv1k>0  (k∈C), where v1,v2,…,vm are distinct nodes. According to Lemma 3.1, in the solution, we have
(3.8)αv1k-gv1v2k(x)=αv2k,⋮αvmk-gvmv1k(x)=αv1k.
Then, we have
(3.9)gv1v2k(x)+gv2v3k(x)+⋯+gvmv1k(x)=0,
which contradicts the fact that gijk(x)>0 if xijk>0 for at least one of (nonzero-cost) links involved.
The case of individual optimization is shown in a similar way as above by replacinggijk(x) by Gijk(x).Since the constraintx∈FSI of the optimization problems may be weaker than the set of constraints x∈FSx, there may be the possibility that a link flow solution x(x∈FSI) may not be realized by any path flow pattern. In the following, however, we confirm that there exists a path flow pattern y that results in any loop-free link-flow pattern x such that x∈FSI.Proposition 3.3.
There exists a path flow patterny satisfying the constraint y∈FSy that results in a link-traffic loop-free flow pattern x satisfying the constraint x∈FSI. That is, for networks with a link-traffic loop-free flow pattern, FSI=FSx.Proof.
Consider an arbitrary loop-free link-flow patternx that satisfies the constraint x∈FSI. We show how to make a path flow pattern y(∈FSy) that results in the loop-free link-flow pattern x(∈FSI).
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, we call 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 different origins. Furthermore, we also say that the sequence (o,v1,v2,…,vi) is the intermediate path at node vi that is included in the intermediate path (o,v1,v2,…,vi,…,vj) longer than it, for i<j and vj≠d.
We can assign a path flow patterny such that the constraint x∈FSI is satisfied, as follows. We note that the flow through each intermediate path must be the sum of the flows of the paths that go though the intermediate path for each class. The allotment of the flow to an intermediate path of node vi+1 is done by splitting the flow to the intermediate paths of node vi, in a way proportional to the link flow xvi,vi+1k on the link (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-traffic loop-free flow pattern, the path flow pattern for classk, k∈C, can be obtained as follows. Since the used links have the loop-free property, a “partial-order” relation among class-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 flows from any nodes but only sends class-k flows 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 flows to any nodes but only receives class-k flows from other nodes. We call it a pure destination for class k. Denote by iak the set of nodes that may receive class-k flow directly from node i (Figure 2). (i)
The case where nodei is a pure origin o. A node j directly connected to a pure origin o (j∈oak) has the class-k link flow xojk. There must be only one class-k intermediate path from the origin at a node j∈oak, that passes through one class-k link to the node j from the origin, and, thus, the allotment of class-k flow to the class-k intermediate path is straightforward. Clearly, this allotment is relevant to (2.4) and (2.1) but does not violate them since x∈FSI must hold.(ii)
The case where nodei is neither an origin nor a destination: each of the class-k intermediate paths at node j, j∈iak, that go through node i, will be allotted the ratio xijk/∑l∈iakxilk of the flow of the corresponding class-k intermediate path at node i. For example, if the class-k intermediate path (o,…,i) included in a class-k intermediate path (o,…,i,j) has the flow yo⋯ik, the class-k intermediate path (o,…,i,j) is to be allotted the flow
(3.10)yo⋯ijk=yo⋯ikxijk∑l∈iakxilk.
Clearly, this allotment is relevant to (2.4) and (2.1) but does not violate them since x∈FSI must hold.(iii)
The case where the nodei is not a pure origin but an origin that has the external arrival rate ri-k: each of the class-k intermediate paths at node j, j∈iak, that go through node i, will be allotted the ratio
(3.11)∑l∈iakxilk-ri-k∑l∈iakxilkxijk∑l∈iakxilk
of the flow 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 flow ri-k((xijk)/(∑l∈iakxilk)). Clearly, this allotment is relevant to (2.4) and (2.1) but does not violate them since x∈FSI must hold.(iv)
The case where the nodei is not a pure destination but a destination that has the departure rate r-ik: each of the class-k intermediate paths at node j, j∈iak, that go through node i, will be allotted the ratio
(3.12)∑l∈iakxilk∑l∈iakxilk+r-ikxijk∑l∈iakxilk
of the flow of the corresponding class-k intermediate path at node i. In addition, we have a set of complete paths ending at node i, and each is allotted the ratio r-ik/(∑l∈iakxilk+r-ik) of the flow of the corresponding intermediate path of node i. Clearly, this allotment is relevant to (2.4) and (2.2) but does not violate them since x∈FSI must hold.(v)
The case where nodei is a pure destination for class k. All the class-k paths that reach this node terminate at this node, and no further path-flow allotment for class k is needed anymore. Clearly, we see that, at this node, class-k path flow allotment so far is relevant to (2.4) and (2.2) but does not violate them since x∈FSI must hold.
We therefore see that, at every step of the above five allotments in cases (i), (ii), (iii), (iv), and (v), the set of constraints (2.4) and y∈FSy is satisfied.
Therefore, for an arbitraryx (∈FSI) with the loop-free property, starting from nodes that directly receives class-k flows only from origins that receive no class-k flows from other nodes, we can proceed the steps of allotting the amount of class-k flows to intermediate paths, and finally we can complete the assignment y of class-k path flows, for all k∈C, that result in the above-mentioned x (∈FSI).
We note that the above-obtainedy satisfies both the constraints (2.4) and y∈FSy and, thus, that the above-mentioned x satisfies the constraint x∈FSx.
SinceFSI includes FSx, then, for networks with a link-traffic loop-free flow pattern, FSI=FSx.Figure 2
Assigning flows to paths on the basis of link flows.From the above Proposition and Lemma3.2, we can confirm the following.Lemma 3.4.
For the solutionx with the link-traffic loop-free property for the overall/individually optimal routing with constraint x∈FSI (3.3) there exists a y that satisfies both the set of constraints (2.4) and y∈FSy, that is, FSI=FSx.We, therefore, see that the solutionx with the link-traffic loop-free property for the overall/individually optimal routing with constraint x∈FSI (3.3) is also the solution for the overall (and individually) optimal routing problem ((2.8), (2.17), (3.3)), since its solution exists as discussed in Section 2.4.Then, we have the following theorem.Theorem 3.5 (Link-traffic loop-free property).
The class-k link traffic in a solution to the overall (and individually) optimal routing problem ((2.8), (2.17), (3.3)) for a  multiclass network is loop-free for all k∈C. That is, there exists no class-k link traffic such that xv1v2k>0, xv2v3k>0,…,xvm-1vmk>0, xvmv1k>0 (for all k∈C), where v1,v2,…,vm are distinct nodes in the solution to the overall (and individually) optimal routing 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 the following result.Corollary 3.6 (One-way traffic property).
For any optimal solutionx to an overall/individually optimal routing problem ((2.8), (2.17), (3.3)) for  multiclass networks, the following relations hold true:
(3.13)xijk=0,ifxjik>0,
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 Theorem3.5.The property shown in Corollary3.6 is called the one-way traffic property for the overall/individually optimal routing in  multiclass networks. The physical meaning is clear. It shows that the traffic from the node i to node j, xijk, and the user flow rate from the node j to node i, xjik cannot be positive both at the same time as shown in Figure 3.Figure 3
One-way traffic property in overall and individually optimal routing.Recall the definitions on the networks given at the beginning of Section2. Since we assume that the users (commodities) do not change their classes during flowing through their path, we can partition classes into disjoint subsets. Consider that each subset of classes is associated either with a decision maker (or an atomic player) or with infinitely many decision makers (nonatomic users). Consider a case where an equilibrium exists where all of atomic users and nonatomic users achieve their own cost minimization unilaterally. In such an equilibrium, we can see that each class has no link loop, by applying Theorem 3.5 to each atomic user or to the collection of nonatomic users with the behaviors of other users being given.


## 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.


#### 4.1.1. Multiclass Routing in Networks with a Common Destination

Consider the overall/individually optimal routing problem for a  multiclass network with one common destination and multiple origins for a class (we call it the problem with a common destination for the sake of brevity) as shown in Figure4. Note that the problems of load balancing in distributed computer systems [21, 22] are equivalent to the routing problems in the networks with one common destination and multiple origins. Clearly, the assumption (A2) holds naturally for the networks. The two link-traffic loop-free properties, Theorem 3.5 and Corollary 3.6 shown in the above section hold for the networks under overall and individually optimal routing.Figure 4
A network with one common destination and multiple origins.In contrast, consider a case of noncooperative optimal routing with a finite (but plural) number of players for this model, that is, users are divided into groups each of which is controlled by a decision maker that strives to optimize unilaterally the cost for its group only. Link-traffic loops have been found in the above-mentioned load-balancing problems (shown in [14, 15] if the definition of class given in those papers is changed to be the same as the one given in this paper).


#### 4.1.2. Multiclass 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 Figure5. The two link-traffic loop-free properties, Theorem 3.5 and Corollary 3.6 shown in the above section, hold for the networks for overall and individually optimal routing. Clearly, the assumption (A2) holds naturally for the networks also.Figure 5
A network with one common origin and multiple destinations.


### 4.2. Examples Where Assumption (A1) Does Not Hold

In 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-traffic 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-traffic loop-free property holds in overall and individually optimal routing in  multiclass 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 pair of 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, in the one-class network, there exist only two paths (1,2,3,4) and (1,3,2,4) connecting the O-D pair (1,4) of the one class, but (1,2,4) and (1,3,4) are not paths connecting the O-D pair (1,4), which violates (2) in the assumption (A1). We assume that the cost of each link depends only on the flow of the link and that G12(x)=G13(x), G23(x)=G32(x)>0, and G24(x)=G34(x) where x denotes the flow through each link. Let the arrival rate at the origin be r14>0. Then, the optimal path flows of the two paths are identical, and x23=y1234=r14/2=y1324=x32>0, which means that the network has a link-traffic loop for the one class.Figure 6
A network with one origin and one destination that satisfies assumption (A1)(1) but does not satisfy (A1)(2).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 for the one class. Then, in optimal routing, only paths (1,2,4) and (1,3,4) are used, and the network has no link-traffic 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, in the network, there exist only two distinct O-D pairs 1-3 and 4-2 (two O-D pairs for one class) and where only (1,2,3) and (4,3,2) are possible paths. On the other hand, there exists no path connecting 1 (as an origin) and 2 (as the corresponding destination) for the one class although link (1,2) exists, and there exists no path connecting 4 (as an origin) and 3 (as the corresponding destination) for the one class although link (4,3) exits. That is, O-D pairs neither of 1-2 nor 4-3 works as an origin -destination pair, which violates (1) in the assumption (A1). Thus the commodity that enters the network at the origin 1 can get out of the network only at the destination 3 but not at 2, and the commodity that enters the network at the origin 4 can get out of the network only at the destination 2 but not at 3. 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 overall/individually optimal routing problem under the set of constraints (2.4) and y∈FSy. In this example, it is clear that we have a link-traffic loop for the one class, that is, x23>0 and x32>0.Figure 7
A network with two origins and two destinations that satisfies assumption (A1)(2) but does not satisfy (A1)(1).On the other hand, if (1) in the assumption (A1) holds, both of (1,2) and (4,3) can be paths for the one class, and the solution under the constraintx∈FSx is such that x23=r13-r42≥0 and x32=0 if r13≥r42 (under assumption (A2)), which shows the freedom of link-traffic loops that holds under assumption (A1).So far, we consider overall optimization (in which only one decision maker, or a player, is involved) and individual optimization (in which infinitely many decision makers, or infinitely many players, are involved) are involved. In this section, we mention an extension of the above-mentioned loop-free property.


## 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.


### 4.1.1. Multiclass Routing in Networks with a Common Destination

Consider the overall/individually optimal routing problem for a  multiclass network with one common destination and multiple origins for a class (we call it the problem with a common destination for the sake of brevity) as shown in Figure4. Note that the problems of load balancing in distributed computer systems [21, 22] are equivalent to the routing problems in the networks with one common destination and multiple origins. Clearly, the assumption (A2) holds naturally for the networks. The two link-traffic loop-free properties, Theorem 3.5 and Corollary 3.6 shown in the above section hold for the networks under overall and individually optimal routing.Figure 4
A network with one common destination and multiple origins.In contrast, consider a case of noncooperative optimal routing with a finite (but plural) number of players for this model, that is, users are divided into groups each of which is controlled by a decision maker that strives to optimize unilaterally the cost for its group only. Link-traffic loops have been found in the above-mentioned load-balancing problems (shown in [14, 15] if the definition of class given in those papers is changed to be the same as the one given in this paper).


### 4.1.2. Multiclass 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 Figure5. The two link-traffic loop-free properties, Theorem 3.5 and Corollary 3.6 shown in the above section, hold for the networks for overall and individually optimal routing. Clearly, the assumption (A2) holds naturally for the networks also.Figure 5
A network with one common origin and multiple destinations.


## 4.1.1. Multiclass Routing in Networks with a Common Destination

Consider the overall/individually optimal routing problem for a  multiclass network with one common destination and multiple origins for a class (we call it the problem with a common destination for the sake of brevity) as shown in Figure4. Note that the problems of load balancing in distributed computer systems [21, 22] are equivalent to the routing problems in the networks with one common destination and multiple origins. Clearly, the assumption (A2) holds naturally for the networks. The two link-traffic loop-free properties, Theorem 3.5 and Corollary 3.6 shown in the above section hold for the networks under overall and individually optimal routing.Figure 4
A network with one common destination and multiple origins.In contrast, consider a case of noncooperative optimal routing with a finite (but plural) number of players for this model, that is, users are divided into groups each of which is controlled by a decision maker that strives to optimize unilaterally the cost for its group only. Link-traffic loops have been found in the above-mentioned load-balancing problems (shown in [14, 15] if the definition of class given in those papers is changed to be the same as the one given in this paper).


## 4.1.2. Multiclass 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 Figure5. The two link-traffic loop-free properties, Theorem 3.5 and Corollary 3.6 shown in the above section, hold for the networks for overall and individually optimal routing. Clearly, the assumption (A2) holds naturally for the networks also.Figure 5
A network with one common origin and multiple destinations.


## 4.2. Examples Where Assumption (A1) Does Not Hold

In 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-traffic 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-traffic loop-free property holds in overall and individually optimal routing in  multiclass 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 pair of 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, in the one-class network, there exist only two paths (1,2,3,4) and (1,3,2,4) connecting the O-D pair (1,4) of the one class, but (1,2,4) and (1,3,4) are not paths connecting the O-D pair (1,4), which violates (2) in the assumption (A1). We assume that the cost of each link depends only on the flow of the link and that G12(x)=G13(x), G23(x)=G32(x)>0, and G24(x)=G34(x) where x denotes the flow through each link. Let the arrival rate at the origin be r14>0. Then, the optimal path flows of the two paths are identical, and x23=y1234=r14/2=y1324=x32>0, which means that the network has a link-traffic loop for the one class.Figure 6
A network with one origin and one destination that satisfies assumption (A1)(1) but does not satisfy (A1)(2).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 for the one class. Then, in optimal routing, only paths (1,2,4) and (1,3,4) are used, and the network has no link-traffic 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, in the network, there exist only two distinct O-D pairs 1-3 and 4-2 (two O-D pairs for one class) and where only (1,2,3) and (4,3,2) are possible paths. On the other hand, there exists no path connecting 1 (as an origin) and 2 (as the corresponding destination) for the one class although link (1,2) exists, and there exists no path connecting 4 (as an origin) and 3 (as the corresponding destination) for the one class although link (4,3) exits. That is, O-D pairs neither of 1-2 nor 4-3 works as an origin -destination pair, which violates (1) in the assumption (A1). Thus the commodity that enters the network at the origin 1 can get out of the network only at the destination 3 but not at 2, and the commodity that enters the network at the origin 4 can get out of the network only at the destination 2 but not at 3. 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 overall/individually optimal routing problem under the set of constraints (2.4) and y∈FSy. In this example, it is clear that we have a link-traffic loop for the one class, that is, x23>0 and x32>0.Figure 7
A network with two origins and two destinations that satisfies assumption (A1)(2) but does not satisfy (A1)(1).On the other hand, if (1) in the assumption (A1) holds, both of (1,2) and (4,3) can be paths for the one class, and the solution under the constraintx∈FSx is such that x23=r13-r42≥0 and x32=0 if r13≥r42 (under assumption (A2)), which shows the freedom of link-traffic loops that holds under assumption (A1).So far, we consider overall optimization (in which only one decision maker, or a player, is involved) and individual optimization (in which infinitely many decision makers, or infinitely many players, are involved) are involved. In this section, we mention an extension of the above-mentioned loop-free property.


## 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 pair of 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, in the one-class network, there exist only two paths (1,2,3,4) and (1,3,2,4) connecting the O-D pair (1,4) of the one class, but (1,2,4) and (1,3,4) are not paths connecting the O-D pair (1,4), which violates (2) in the assumption (A1). We assume that the cost of each link depends only on the flow of the link and that G12(x)=G13(x), G23(x)=G32(x)>0, and G24(x)=G34(x) where x denotes the flow through each link. Let the arrival rate at the origin be r14>0. Then, the optimal path flows of the two paths are identical, and x23=y1234=r14/2=y1324=x32>0, which means that the network has a link-traffic loop for the one class.Figure 6
A network with one origin and one destination that satisfies assumption (A1)(1) but does not satisfy (A1)(2).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 for the one class. Then, in optimal routing, only paths (1,2,4) and (1,3,4) are used, and the network has no link-traffic 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, in the network, there exist only two distinct O-D pairs 1-3 and 4-2 (two O-D pairs for one class) and where only (1,2,3) and (4,3,2) are possible paths. On the other hand, there exists no path connecting 1 (as an origin) and 2 (as the corresponding destination) for the one class although link (1,2) exists, and there exists no path connecting 4 (as an origin) and 3 (as the corresponding destination) for the one class although link (4,3) exits. That is, O-D pairs neither of 1-2 nor 4-3 works as an origin -destination pair, which violates (1) in the assumption (A1). Thus the commodity that enters the network at the origin 1 can get out of the network only at the destination 3 but not at 2, and the commodity that enters the network at the origin 4 can get out of the network only at the destination 2 but not at 3. 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 overall/individually optimal routing problem under the set of constraints (2.4) and y∈FSy. In this example, it is clear that we have a link-traffic loop for the one class, that is, x23>0 and x32>0.Figure 7
A network with two origins and two destinations that satisfies assumption (A1)(2) but does not satisfy (A1)(1).On the other hand, if (1) in the assumption (A1) holds, both of (1,2) and (4,3) can be paths for the one class, and the solution under the constraintx∈FSx is such that x23=r13-r42≥0 and x32=0 if r13≥r42 (under assumption (A2)), which shows the freedom of link-traffic loops that holds under assumption (A1).So far, we consider overall optimization (in which only one decision maker, or a player, is involved) and individual optimization (in which infinitely many decision makers, or infinitely many players, are involved) are involved. In this section, we mention an extension of the above-mentioned loop-free property.


## 5. Conclusion

In this paper, we have studied both overall and individually optimal routing problems for  multiclass networks with generalized link-cost functions and network configurations. We have seen that there is an 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 and uniqueness of the solutions to overall and individually optimal routing. Furthermore, we have shown that the link-traffic loop-free property holds for the overall and individually optimal routing in a wide range of networks. While doing so, we have discussed the relation between the formulations with path and link flow patterns. We have shown the condition that characterizes the category of  multiclass networks that have the link-traffic loop-free property for overall and individually optimal routing.



---

*Source: 645954-2011-07-06.xml*