1 Introduction

There exist numerous systems wherein a number of independent users share and compete for resources on a network. Consider, for instance, a distributed computing system, such as a grid, composed of a network of servers on a local or wide-area network (Foster and Kesselman 1998), or a packet-switched computer network like the Internet (see, e.g., Keshav 1997; Stevens 1994; Chen et al. 1999). The network consists of nodes, i.e., computers (hosts) and routers, which are connected by links, namely, the communication lines. Each job, or packet, sent by a node, is associated with a unique pair of hosts: its origin and destination nodes. Jobs originating at a host flow through a path that consists of a series of interconnected routers to their destination host. Each router may keep routing information in some form, e.g., of a routing table. Such information tells each arriving job to which adjacent router the packet is to be forwarded. Alternatively, so-called ‘source routing’ arises when the path of each job is specified at the origin. Then, each job carries this information about its path while passing through the network.

In addition, there exist protocols that provide routing information at each router, so that every job, or packet, may be guided through a path of the shortest cost among the paths that connect the same pair of origin and destination nodes, given the cost of each link. Thus, such a routing protocol assigns to each link the cost that reflects the estimated communication delay through the link. The communication delay and availability of each link may vary from time to time, and so routers need to exchange packets to update routing information. So-called ‘dynamic routing protocols’ work in this way. Such exchange of packets, however, cannot be done too frequently. Otherwise, links would be flooded and performance would degrade. Thus, the information at each router is updated at some regular (but not too short) intervals, and the cost optimization process is not truly ‘dynamic’ but rather ‘quasi-static.’

Job and/or packet generation is regarded as a stochastic process. It is probable that such processes are stable, i.e., in a stochastic equilibrium, during a time period that contains a large number of update intervals. In quasi-static control, a shortest path routing that reflects communication delays as link costs may cause oscillations in the amount of jobs, or packets, that flow through each link, and thus, oscillations in the communication delay of each link or path. Such oscillations could be avoided by means of suitably forecasting the expected delay of each link for the next update interval, and/or by employing, if needed, an adequate mixing strategy of using more than one possible path, each used at a certain ratio or frequency. Thus, if suitably controlled, shortest path routing may bring about situations wherein each job, or packet, flows through one of the paths of the shortest cost (communication delay) among the paths that connect its origin and destination nodes. The resulting network flow must be very close to a Wardrop equilibrium (of nonatomic users).

On the other hand, source routing may provide situations quite close to a Nash equilibrium, as in the following example. Consider a situation where the information on the estimated delay of each link, and thus each path, is available at each origin. An autonomous system, e.g., a local-area computer network in a large enterprise, or a telephone network run by an Internet-service provider, may be connected to the network at an origin. Then, the manager or the administrator of the autonomous system would like to minimize the overall cost or mean delay of the jobs that are sent from the origin into the computer communication network. Again, such oscillations mentioned above could be avoided by means of suitably forecasting the expected delay of each link in the next update interval, and/or by employing, if needed, an adequate mixing strategy of using more than one possible path, each used at a certain ratio or frequency. Thus, if suitably controlled, source routing may bring about situations wherein the mean delay of the packets of an autonomous system is at a minimum, given the routing decisions on the packets of the other autonomous systems that are connected to the network. In such cases, the situation must be very close to a Nash equilibrium.

Nash and Wardrop equilibria are two related paradigms that describe a stable network flow as a function of its characteristics. While there are similarities between the two notions of network equilibrium, as we shall see in this paper, there are important differences as well. Wardrop equilibria have been discussed extensively in transportation science which continues to develop (Patriksson 2004; Shao et al. 2006).

The famous (original) Braess paradox shows that adding a connection (a link) to a network may sometimes degrade the cost for all users in a Wardrop equilibrium. If performance degrades coincidently for all users when a new connection is added to a system, it is called a paradox. The Braess paradox has attracted the attention of many researchers. A list of references on the Braess paradox is kept in Braess’ home page at http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/#paradox.

Only a few studies have provided an estimation of how harmful the paradox can be, i.e., the worst-case degree of coincident cost degradation for all users by adding connections to a noncooperative system (Kameda 2002; Roughgarden 2006a; Roughgarden and Tardos 2004). It has been shown that there exists a system in a Nash equilibrium for any size of the degree of the paradox. In contrast, there has not been found any system in Wardrop equilibrium for which the degree of coincident cost degradation can increase without bound if the number of nodes in the network is bounded. Moreover, we have not seen any estimation of how beneficial the addition of connections to a noncooperative network can be, i.e., the best-case degree of coincident cost improvement by adding connections to a noncooperative system.

This paper answers the following questions:

  1. i.

    For Wardrop and Nash networks (networks in a Wardrop or Nash equilibrium), is there a parameterization that leads to every level of coincident cost degradation up to a bound, and every value of coincident cost improvement, when adding new connections to a network?

  2. ii.

    What is the effect of adding connections to distributed computer systems?

Note, in passing, that each user of a network may have decisions on flow control, in addition to routing. In wireless networks, users may have power control. The concept of a Nash equilibrium is also discussed with a paradoxical behavior discovered (Inoie et al. 2006), both of which are not addressed in this paper.

As to the literature on the game theory and networks, see also Altman and Wynter (2004).

The next section introduces Nash and Wardrop networks. Section 3 presents the measure of coincident degradation (paradox) and improvement for all users by adding connections to systems. Section 4 answers question (i) above, while Section 5 discusses distributed computing systems and responds to question (ii).

Section 6 concludes and summarizes the contributions of the paper.

2 Nash and Wardrop networks

We discuss two types of noncooperative networks. In the first case, one can consider systems where the jobs, or packets, are classified into a small number of groups led by a user or decision maker, each of which optimizes its cost non-cooperatively. In this situation, the users are referred to as “atomic” (as some game-theorists say) in that each user’s decision has an impact on the costs experienced by the other users. The situation where, in such a scheme, every user has optimized his decision, given the decisions of other users, and furthermore, would not unilaterally deviate from this decision is called a Nash equilibrium, since it is, in this respect, “stable” (Haurie and Marcotte 1985; Kameda et al. 2000; Kameda and Pourtallier 2002). As mentioned above, in computer networking, some source routing protocols may bring about situations close to Nash equilibria.

In other types of noncooperative networks, each infinitesimal, i.e., non-atomic (as some game-theorists say), user makes its own routing decision so as to minimize its expected delay from its origin to its destination given the routing decisions of other users. In this setting, the number of such users is so high that the impact of any one such user is infinitesimally small on the cost experienced by all users. In this case as well, the situation where every infinitesimal user has optimized its decision, given the decisions of other users, and would not unilaterally deviate from that choice, is called an equilibrium. The name given to this form of equilibrium is Wardrop equilibrium, i.e., a Nash equilibrium with infinitesimal players (nonatomic users) (Haurie and Marcotte 1985; Patriksson 1994). As mentioned previously, in computer networking, some shortest path routing protocols may bring about situations close to Wardrop equilibria.

3 Degrees of coincident cost degradation (paradox) and improvement for all users by adding connections to systems

This paper uses a single scalar measure that quantifies Pareto superiority of a system state before adding connections to that after doing so, or the degree of paradoxes in Nash equilibria.

Pareto superiority is defined as follows. Consider a system consisting of n users (or players, decision makers), 1,2,...,n. User i has its cost C i (S), in the system state S.Footnote 1 Denote by S a and S b two different states of the system, and \(k_{i}\triangleq C_{i}(S^{a})/C_{i}(S^{b})\). Then, we say that S b is Pareto superior to S a iff k i  > 1 for some i and k j  ≥ 1 for all other j. In particular, we say that S b is strongly Pareto superior to S a iff k i  > 1 for all i. A state to which some other state is Pareto superior is Pareto inefficient. Thus, the Pareto superiority depends on the vector (k 1,k 2,...,k n ). It may, however, be convenient to express the degree of Pareto superiority, using a single scalar measure. It is required that the measure should clearly reflect Pareto superiority. If k min > 1, the state S b is (strongly) Pareto superior to S a. Thus, the measure k min may be used as a primary measure of Pareto superiority. In contrast, for example, a measure based on a certain average or on a product of all k i cannot satisfy the above requirement, but may be used as a secondary measure for tie-breaking in the case where k min = 1.

It would be anticipated that in a system state where each user has more freedom of choice than in another state, at least one user should enjoy higher utility than in the latter state. As the famous Braess paradox shows, however, it is not always the case for noncooperative systems. Thus, a Nash equilibrium of a system with less freedom may be strongly Pareto superior to that with more freedom, which is called paradox. We, therefore, use the measure of Pareto superiority defined above as the measure of the degree of the paradox, i.e., the coincident cost degradation for all users by adding connections. The measure of the degree of coincident cost improvement for all users by adding connections can be considered in a similar way. For example, if \(k_\text{min}\rightarrow 0\), we say that the degree of coincident cost improvement for all users by adding connections can increase without bound.

The price of anarchy The idea of a measure, the price of anarchy, was mentioned by Koutsoupias and Papadimitriou (1999), and its name ‘the price of anarchy’ appeared in Papadimitriou (2001). The term ‘anarchy’ is considered to mean the state of a Nash or Wardrop equilibrium which is reached by the situation where every player behaves selfishly to optimize its own cost or utility. The measure looks to show the degree how bad is the state of the worst-case Nash/Wardrop equilibrium against a best state. The proposer of the measure defines the best state to be the state with the optimal social cost. Then, the price of anarchy is equal to the ratio of the social cost of the worst-case Nash/Wardrop equilibrium to the minimum social cost. A number of results have been obtained based on this measure, many of which are described by Roughgarden (2005, 2006b). In fact, before the idea of the measure, price of anarchy, was proposed, anomalous behaviors of Wardrop and Nash equilibria compared with social optima, like those expressed in terms of the price of anarchy, had already been discovered and investigated in the context of load balancing in distributed computer systems that was identical to routing in networks of particular types (Zhang et al. 1992; Kameda et al. 1997a, b).

On the other hand, the measure of the Pareto inefficiency of a Nash equilibrium has to reflect the comparison with all the Pareto optima, and the state with the optimal social cost is only one Pareto optimum. Therefore, the price of anarchy cannot be a good measure of the Pareto inefficiency of a Nash equilibrium (Legrand and Touati 2007). Following the spirit of the price of anarchy, we may think of a measure which is the ratio of the social cost of state A to that of state B for comparing two states A and B. According to the discussion given above on the measure of Pareto superiority and paradoxes, we can see that the above-mentioned measure that has the spirit of the price of anarchy may serve only as a secondary measure and cannot serve as the primary measure of Pareto superiority and paradoxes. We note that the above-mentioned anomalous behavior of the Wardrop/Nash equilibrium necessarily occurs when the Braess paradox occurs, but not vice versa.

4 Coincident cost improvement for all users by adding connections to Wardrop and Nash systems

The present paper addresses the estimation of the best-case degrees of coincident cost improvement for all users by adding connections to Wardrop and Nash systems. In this section, we show that the degree of coincident cost improvement (benefits) by adding connections to both Wardrop and Nash systems can increase without bound.

4.1 Wardrop network

Wardrop networks considered here consist of one origin and one destination and some relay nodes, some pairs of which a one-way link connects. One of the simplest networks is the general Braess network (Fig. 1) discussed later. There are a number of paths each of which connects the origin and the destination through a different series of links. The cost of a path is the sum of the cost of each link in the path. Infinitely many infinitesimal users send their packets through the network. Each user chooses a path of the minimum cost. The choice of a single infinitesimal user has only a negligible impact on the cost of each link. The situation where no user can reduce his/her cost by unilaterally choosing another path is a Wardrop equilibrium, an infinitesimal-user version of a Nash equilibrium.

Fig. 1
figure 1

General Braess network. Left: The network before Link 5 is added. Right: The network after Link 5 is added

Full size image

It is assumed that the cost of each link is a non-decreasing function of the total flow, i.e., the rate of packets through the link. In a Wardrop equilibrium of the networks with only one pair of origin and destination, the costs of all users are identical. C o and C c, respectively, denote the costs of users of a Wardrop network before and after adding connections to the network. Define \(\displaystyle k={C_{\rm c}}/{C_{\rm o}}\). Then, k expresses the degree of cost change for all users by adding the connections. k min of Section 3 reduces to k here.

The Braess network consists of four nodes: one origin (Node 0), one destination (Node 3), and two relay nodes (Nodes 1 and 2): See Fig. 1. Before adding a link, the network has two paths, 0-1-3 (Path 1) and 0-2-3 (Path 2), each of which contains two links, Link 1 (from Node 0 to Node 1) and Link 2 (from Node 1 to Node 3) for the first path, and Link 3 (from Node 0 to Node 2) and Link 4 (from Node 2 to Node 3) for the second: See Fig. 1 left. After adding new link (Link 5), i.e., a one-way link connecting the two relay nodes 1 and 2, the network has three paths including the new, third, path 0-1-2-3 (Path 3): See Fig. 1 right. In the original Braess network, the cost of each link is a linear function of the amount of the flow through the link (Braess 1968).

This paper also considers general Braess networks, that have nonlinear link cost functions. As before, let f i denote the flow on Link i. The total demand in the network is denoted, as before, by d, and the path flows are denoted by x r for path r. The superscripts c and o indicate which flows are on the original, o, network, and which are on the network with an added link, c, i.e., \(x_r^c\) is the flow on Path r in the network having the additional link. Since the flow on the original network on all paths equals demand which in turn equals the flow on all three of the paths in the new network, we have that:

$$ x^o_1+x^o_2=x^c_1+x^c_2+x^c_3=d. $$
(1)

The cost on the four links are t i (f i ), for i = 1,2,3,4. For the original Braess network, t 2(f 2) = f 2 + 50, t 3(f 3) = f 3 + 50, t 1(f 1) = 10f 1, and t 4(f 4) = 10f 4, and for the new connection, t 5(f 5) = f 5 + 10. The demand on the network is d = 6. Solving for Wardrop equilibrium, using these values, one obtains C o = 83 and C c = 92, and thus k = C c/C o = 1.1084... (Braess 1968). Recall that k shows the degree of cost change by adding Link 5, and k ( > 1) gives the value of the coincident cost degradation. In the above case, it is about 11% degradation.

By general Cohen–Kelly networks, we mean a subset of general Braess networks for which the costs of Links 1 and 4, are, respectively, t 1(f 1) = α/(a − f 1) and t 4(f 4) = α/(a − f 4). By definition, 0 ≤ f i  < a, for i = 1,4. The costs on Links 2 and 3 are t 2 = t 3 = b, for some constant, b > 0, and t 5 = τ > 0, a different nonnegative constant.

Cohen and Kelly (1990) considered a network of this type for which α = 1, b = 2, τ = 1, and d = 2λ, for some arrival rate, λ. Note that the resulting network is symmetric. They showed that C o = 1/(a − λ) + 2 < 3 = C c (i.e.,  1 < k < 3/2), assuming that 2λ > a − 1 > λ > 0, which is a paradox. In the above case, the degree of degradation is bounded by the 50% above the original cost (Fig. 2).

Fig. 2
figure 2

General Cohen–Kelly network. Left: The network before Link 5 is added. Right: The network after Link 5 is added

Full size image

As a general result on the Braess networks, it has been shown that the degree, k, of coincident cost degradation is bounded by 2 for the general Braess networks for which costs on Links 1 and 4 are increasing and costs on Links 2, 3, and 5 are non-decreasing (Kameda 2002). Furthermore, as a general result on the Wardrop systems, it has been shown that k is bounded by \(\lfloor{n/2}\rfloor\) for networks that consist of n vertices and have link costs each of which is a non-decreasing function of the flow through the link (Roughgarden 2006a). Note, in passing, that the Braess paradox may also occur for networks with multiple origin-destination pairs (Cohen and Jeffries 1997; Kameda 2002).

Cohen–Kelly network Consider a Cohen–Kelly network with and b ≥ α/(a − d) + τ. Then, the following relations hold.

$$ C_{\mathrm{o}}=\frac{\alpha}{a-d/2}+b, \label{ttypeN2before} $$
(2)
$$ C_{\mathrm{c}}=\frac{2\alpha}{a-d}+\tau. \label{ttypeN2after} $$
(3)

We consider the case of τ = 0, in particular. Then, the above Cohen–Kelly networks are described by the values of parameters α, a, b, and d that satisfy 0 < d < a and 0 < α/(a − d) ≤ b.

Reduced Cohen–Kelly network A subset of general Cohen–Kelly networks with b = α/(a − d) + τ. Thus, the following relation holds for C c while C o is given by Eq. (2).

$$ C_{\mathrm{c}} =\frac{2\alpha}{a-d}+\tau=2b-\tau= \frac{\alpha}{a-d}+b. \label{ttypeN3after} $$
(4)

We also consider the case of τ = 0, in particular.

We show that there exist Wardrop systems such that any degree of k can be obtained, up to a bound.

Theorem 1

For every value of k , s.t. 0 < k < 2, there exist Wardrop systems for which the measure k is that value.

Proof

The outline of the proof is given as follows.

  1. Step 1.

    shows that k depends only on ρ ( = d/a) and Z ( = b(a − d)/α − 1), i.e., k = k(ρ,Z).

  2. Step 2.

    sees that k = k(ρ,0) monotonically increases in ρ with the range 1 < k < 2 and the domain 0 < ρ < 1. Thus, given k, s.t. 1 < k < 2, the corresponding value of ρ can be obtained and thus, with Z = 0, the corresponding combinations of values of α, a, d, and b, can be obtained, which describe model Cohen–Kelly networks that are also reduced Cohen–Kelly networks.

  3. Step 3.

    sees that, given ρ, s.t. 0 < ρ < 1, k = k(ρ,Z) monotonically decreases in Z with the range 0 < k ≤ 1 and the domain Z ρ  ≤ Z where Z ρ  = ρ/(2 − ρ) > 0. Thus, given k, s.t. 0 < k ≤ 1, the corresponding value of Z can be obtained and thus, with given ρ, the corresponding combinations of values of α, a, d, and b, can be obtained, which describe model Cohen–Kelly networks.

  4. Step 4.

    shows, by combining 2. and 3., that, for every value of k, s.t. 0 < k < 2, the corresponding combinations of values of α, a, d, and b, can be obtained, which describe model Cohen–Kelly networks. Therefore, for every value of k, s.t. 0 < k < 2, there exist model Cohen–Kelly networks that have the value of k.

The details of the proof are as follows.

  1. 1.

    Consider a Cohen–Kelly network. Then,

    $$\begin{array}{rcl} k&=&\frac{C_{\mathrm{c}}}{C_{\mathrm{o}}} =\frac{\displaystyle \frac{2\alpha}{ a-d}}{\displaystyle \frac{\alpha}{a-d/2}+\frac{\alpha}{a-d}+b-\frac{\alpha}{ a-d}} \\ &=&\frac{2}{Z+1+\displaystyle \frac{a-d}{a-d/2}} =\frac{2}{Z+3-\displaystyle \frac{2}{2-\rho}}, \end{array}$$

    where ρ = d/a, with 0 < ρ < 1, and Z = b(a − d)/α − 1, with Z ≥ 0.

  2. 2.

    Consider the combinations of values of α, a, d, and b such that Z = 0. Note that, with Z = 0, k is a continuous and strictly increasing function of ρ with the domain 0 < ρ < 1 and the range 1 < k < 2 . Therefore, for every value of k, s.t. 1 < k < 2, the corresponding value of ρ is found, and then, combinations of values of α, a, d, and b that satisfy ρ = d/a and Z = b(a − d)/α − 1 = 0 can be obtained, which describe Cohen–Kelly networks that are also reduced Cohen–Kelly networks. Thus, it is seen that, for every value of k, s.t. 1 < k < 2, there exist Cohen–Kelly networks which have that value of k. It is also seen that the worst-case value, 2, of the measure k of coincident cost degradation due to adding Link 5 is asymptotically reached in certain reduced Cohen–Kelly networks as ρ approaches 1.

  3. 3.

    Next, consider the case where a, d, and thus ρ are given. Recall that 0 < ρ < 1. Then, a value of Z, Z ρ  = ρ/(2 − ρ) > 0, gives that k = 1. Note that k is continuous and strictly decreasing in Z with the domain Z ≥ Z ρ and the range 0 < k ≤ 1. It is seen that, given a, d, and thus ρ, for every value of k, s.t. 0 < k ≤ 1, the corresponding value of Z ≥ Z ρ is found, and then, combinations of values of α and b that satisfy Z = b(a − d)/α − 1 can be obtained, which describe model Cohen–Kelly networks along with the values of a and d given at the beginning of 3). Thus, it is seen that, for every value of k, s.t. 0 < k ≤ 1, there exist Cohen–Kelly networks which have that value of k. That is, k can be nearly equal to 0, and then κ = log2 k can decrease without bound to − ∞.

  4. 4.

    Combining 2) and 3) above, it is seen, therefore, that for any value of k , s.t. 0 < k < 2, there exist Cohen–Kelly networks that have the value of k. Furthermore, from 2), it is seen that the worst-case value, k = 2, is asymptotically reached in certain reduced Cohen–Kelly networks as ρ approaches 1. □

This result is complementary to the result (Roughgarden 2006b) which shows that the degree of degradation can take on countably many values increasing as the size of the network, in terms of the number of nodes, increases. In our case, this result shows that, for a network of a fixed size, the degradation can also take on a continuum of values up to its bound.

Remark 1

In the above proof, it is seen, in 3), that the degree of coincident cost improvement can increase without bound (i.e., k ≃ 0) in some Cohen–Kelly networks, with b ≥ α/(a − d) or Z ≥ 0, as b → ∞ with α, a, and d fixed. On the other hand, in 2), in reduced Cohen–Kelly networks with τ = 0, the ratio of the paradox (k) approaches 2 as ρ→1, which means asymptotically infinite link costs.

Define the degree κ = log2 k. Thus, k = 2κ. Then, adding link 5 leads to the cost improvement of 2|κ| times if κ ≤ 0 (i.e., k ≤ 1), and leads to the cost degradation of 2|κ| times if κ ≥ 0 (i.e., k ≥ 1). Thus, unlimited large values of |κ| can be considered for κ < 0. That is, the cost improvement (− κ) occurs without bounds.

The above result shows that − ∞ < κ < 1 which is equivalent to 0 < k < 2.

Corollary 1

The degree of coincident cost improvement for all users by adding connections to Wardrop systems can increase without bound. □

4.2 Nash network

A situation in which a Nash equilibrium results on a network is as follows. For each OD pair, there is one decision maker, or an atomic player, that strives to minimize the cost for that OD pair. Before adding connections, each decision maker has no choice since there is only one available path. After adding connections, decision maker i chooses the proportion of its flow, d i , to forward to other nodes, i.e., the values of x ij , so as to minimize its own cost.

We then have the following result.

Theorem 2

For any value of 0 < k < 1, there exists a Nash system which achieves that value.

Proof

Consider the following Nash network with n = 3 nodes, 1, 2, and 3: packet arrival rates to origin nodes 1 and 2, respectively, are d 1 = d 2 = d > 0. Before adding connections, there are l = 2 links 1 and 2, and links 1 and 2, respectively, connect nodes 1 and 2 to node 3, the destination nodes. Denote the delay (cost) of passing through link i by D i . which is defined as follows:

$$\begin{array}{rcl} D_1(f_1)&= & \begin{cases} D, \mbox{ for }0\le f_1\le d, \\ \delta, \mbox{ for }f_1>d, \end{cases} \\ D_2(f_2)&=&D \mbox{~(constant)}. \end{array}$$
(5)

Consider adding connections, that is, links 12 and 21, respectively, for forwarding packets from nodes 1 to 2 and from nodes 2 to 1. Let the forwarding costs, G ij \((i\ne j)\), which is the cost of forwarding a job from node i to node j, be defined as follows:

$$ G_{12} = G_{21}=0. $$

(This system is topologically identical to the distributed systems [see Fig. 3 in the next section] with the number of nodes being 2.) Furthermore, let 0 < δ < D = Δ.

Fig. 3
figure 3

The model of a distributed system for n = 3

Full size image

We can easily show the degree of cost improvement for this case is k = k 1 = k 2, and any value of 0 < k < 1 is given by a suitable choice of δ and D.

D 1,D 2,G 12, and G 21 are nonincreasing. Then, clearly, \({\boldsymbol{x}^{*}} = ({x}_{11}^{*},{x}_{12}^{*}, {x}_{21}^{*},{x}_{22}^{*}) = (1,0,1,0) \) is a Nash equilibrium after adding connections, and

$$ C_1({\boldsymbol{x}^{*}})=\delta,{\quad}C_2({\boldsymbol{x}^{*}})=\delta. $$

Note, however, that, before adding connections,

$$ C_1({\boldsymbol{x}}^{*})=D,{\quad}C_2({\boldsymbol{x}}^{*})=D, $$

Therefore, k 1 = k 2 = δ/D < 1, and both users 1 and 2 have coincident cost improvements by adding connections, and the best-case degree can increase without bound as δ/D→0.

Thus, we have seen that there exist Nash networks that achieve any value of the degree of coincident cost improvement for all users by adding connections to the networks. □

Corollary 2

There exist Nash systems for which the degree of coincident cost improvement for all users increases without bound.

5 Distributed computing systems

This section discusses, in particular, models of distributed systems, like grids (Foster and Kesselman 1998). Load balancing of jobs among nodes in distributed systems can be modeled as a routing in some specific networks (Kim and Kameda 1990; Kameda et al. 1997a). It has been shown that the degree of the Braess-like coincident cost degradation can increase without bound in Nash equilibria (Kameda and Pourtallier 2002) on this type of network.

5.1 Assumptions

A network equivalent to a distributed system consists of n origins and one destination, with each origin being connected to the destination through one separate link, which is often called ‘node’. Routing in this network is equivalent to load balancing in a distributed computer system (Tantawi and Towsley 1985; Kim and Kameda 1990; Kameda et al. 1997a). Note that the load balancing policies considered here are static in nature.

Since there is a single destination, we denote the total flow of OD pair from source node i as d i . Before adding connections, there is only one path for each OD pair. Hence, initially, the network has only links from the origin nodes to the destination, and looks like a star. After adding connections (see Fig. 3), flow may be forwarded to other nodes. Let the flow from origin i to node j be d i x ij . Then, x ij is a fractional flow, so that 0 ≤ x ij  ≤ 1, i,j = 1,2,...,n and ∑  j = 1...n x ij  = 1. Denote by \(\boldsymbol{x}\) the vector (x 11,x 12,...,x 1n ,x 21,x 22,...,x nn ), i.e., the resulting strategy profile.

The resulting flow f i from node i to the destination, i = 1,2,..., n, is

$$ f_{i} = \sum_{j=1\ldots n}d_j{x_{ji}}. \label{defbeta} $$
(6)

Thus, given the entire strategy profile \(\boldsymbol{x}\), the cost \(C_{i}(\boldsymbol{x})\) for the flow associated with OD pair i is the sum of the costs on the direct, original, paths to the destination and the costs on the forwarding links. Note that the flow on the direct links may come from multiple sources once forwarding links are added. We have

$$ \label{defTik} C_{i}(\boldsymbol{x}) =\sum_{j=1\ldots n}x_{ij}C_{ij}(\boldsymbol{x}). $$
(7)

where

$$ \label{defTijk} C_{ii}(\boldsymbol{x}) = D_i(f_i), $$
(8)
$$ C_{ij}(\boldsymbol{x}) = D_j(f_j) + G_{ij}(\boldsymbol{x}), \mbox{ for } j \ne i. $$
(9)

The above definitions come from the following. In distributed computing systems, the delay experienced by a forwarded job can be further broken down into its two contributions: the job processing time on the node at which it is eventually processed, denoted D i , and the delay associated with the forwarding of the job from node i to another node, j, G ij .

To reflect real distributed computer systems, we assume that the job processing time on the node D i is increasing and convex in f i and that the delay associated with the forwarding of the job from node i to another node, j , G ij is non-decreasing and convex in \(\boldsymbol{x}\) .

(One origin and one destination networks are discussed by a number of people (Orda et al. 1993; Koutsoupias and Papadimitriou 1999)).

It is further assumed that, for all i,j,k, \(i\ne j\ne k\ne i\),

$$ \label{triangleineq} G_{ij}(\boldsymbol{x})<G_{ik}(\boldsymbol{x})+G_{kj}(\boldsymbol{x}). $$
(10)

The above inequality implies that a job forwarded from a node is not forwarded again to another node. That is, we consider distributed systems in which every two nodes are directly connected (Tantawi and Towsley 1985; Kameda et al. 1997a). For example, a distributed system in which each node is connected to an Ethernet LAN satisfies the condition (10).

5.2 Wardrop equilibrium in distributed systems

We consider an individual optimization scheme for the systems of this category. Each infinitesimal (nonatomic) user optimizes its own costs by choosing its path to the destination. The situation where each such user minimizes its costs, given the decisions of other users, is a Wardrop equilibrium or a Wardrop system. As stated previously, in Wardrop equilibrium, all used paths between an OD pair have equal cost, and this holds for every OD pair simultaneously.

The following result shows that there exists no paradox on distributed computing networks at Wardrop equilibrium.

Theorem 3

The costs of all users neither degrade nor improve coincidently by adding connections to any Wardrop distributed computing system.

Proof

The proof makes use of a decomposition of nodes similar to that of Kameda et al. (Zhang et al. 1992; Tantawi and Towsley 1985; Kameda et al. 1997a). After adding connections to the distributed computing Wardrop system, nodes are one of the following types:

  1. 1.

    idle (R d): The node forwards jobs and does not process any jobs. That is, f i  = 0.

  2. 2.

    active (R a): The node forwards jobs and does not receive any jobs. But, the node processes a part of the jobs that originate at that node. That is, d i  > f i  > 0.

  3. 3.

    neutral (N): The node processes jobs locally without forwarding or receiving jobs. That is, d i  = f i .

  4. 4.

    sink (S): The node receives jobs from other nodes but does not forward any jobs. That is, f i  > d i .

There does not exist such a node that both sends and receives jobs. Indeed, suppose that the converse is true, and there exists a node i that forwards jobs to node j and also receives jobs from node k. Then, it must hold that the node processing costs satisfy:

$$ D_i(f_i)\ge D_j(f_j)+G_{ij}(\boldsymbol{x}), $$
(11)
$$ D_k(f_k)\ge D_i(f_i)+G_{ki}(\boldsymbol{x})=C_{ki}. $$
(12)

Then, from Eq. (10), we have that \(C_{ki} \!=\!D_{i}(f_i)\!+\!G_{ki}(\boldsymbol{x})\! \ge\! D_{j}(f_j)\!+\!G_{ij}(\boldsymbol{x})+\) \(G_{ki}(\boldsymbol{x})> D_j(x_j)+G_{kj}(\boldsymbol{x})= C_{kj} \). That is, C ki  > C kj . So, x ki  = 0, and node i does not receive jobs from node k, hence a contradiction.

Now, denote by \(C^o_i\) and \(C^c_i\), respectively, the cost for origin i before and after adding connections to the network. Recall that D i is non-decreasing for all i. We have two cases to consider: coincident cost degradation, and coincident cost improvement.

  1. 1.

    (Cost degradation) Assume that adding connections to a system in question brings about coincident cost degradation to all OD pairs.

    Suppose that there exists an idle or active node i after adding connections, then \(C^o_i=D_i(d_i)\ge D_i(f_i)= C^c_i\). That is, OD pair i suffers no cost degradation. Thus, we see that there can exist neither idle nor active nodes.

    Then, since there exist neither idle nor active nodes, there must exist no sink node, but only neutral nodes. That is, no coincident cost degradation occurs for any OD pair from adding connections to the distributed computing system in Wardrop equilibrium.

  2. 2.

    (Cost Improvement) Assume now that adding connections to a network in question brings about coincident cost improvement to all OD pairs.

    Suppose that there exists a sink node i, then \(C^o_i=D_i(d_i)\le D_i(f_i)=C^c_i\), which implies no cost improvement for OD pair i. Thus, there exists no sink node.

    Then, since there exists no sink node after adding connections, then there must exist neither idle node nor active node, but again, only neutral nodes. That is, no coincident cost improvement occurs for any OD pair from adding connections to the distributed computing network in Wardrop equilibrium. □

5.3 Nash equilibrium in distributed systems

A situation in which a Nash equilibrium results on a distributed systems is as follows. There are n origin nodes with a single destination. One origin node and the destination node compose an OD pair. For each OD pair, there is one decision maker, or an atomic player, that strives to minimize the cost for that OD pair. Before adding connections, each decision maker has no choice since there is only one available path. After adding connections, decision maker i chooses the proportion of its flow, d i , to forward to other nodes, i.e., the values of x ij , so as to minimize its own cost. As is already shown (Kameda and Pourtallier 2002), if the system strives to keep in Nash equilibrium, there exist a homogeneous system (as described in details by the next subsection) with any size of degree of the paradox by adding connections the system. Due to the difficulty of solving Nash equilibria, there has not been obtained any further simple results on this model.

5.4 Coincident cost improvement in homogeneous distributed computing systems

Let us now consider a homogeneous distributed computing network of n origin nodes with a single destination. Each node has d units flow it wishes to process. Recall the notation given in Section 5.1. As before, x ij denotes the flow sent from origin i to node j, and when i = j, then the flow is sent from node i, to the destination, i.e., processed on node i. The cost on a link from node i to the single destination is D i , but since the network is homogeneous, D i  = D j  = D for all nodes i,j. The forwarding costs, G ij , will be referred to as before as G ( > 0).

It has been shown that, for homogeneous distributed computing systems, the degree of coincident cost degradation by adding connections can increase without bound in Nash equilibria (Kameda and Pourtallier 2002), as noted in the previous subsection. That is, for any value of k > 1, there exists a homogeneous Nash distributed computing system that has that value of degradation. However, we show next that under any static load balancing policy adding connections to homogeneous Nash distributed computing systems can bring no coincident cost improvement for all users.

Theorem 4

No static load balancing policy in homogeneous distributed systems can bring about coincident cost, or mean response time, improvement for all users by adding connections.

Proof

Note first that cost experienced by each node i before adding connections is equal to C i  = D(d). Now, assume on the contrary that there is forwarding of flows and that the resulting strategy profile is given by \(\boldsymbol{x}\ge\boldsymbol{0}\). Then, since the forwarding of jobs may cause non-zero communication costs, from Eq. (7), we have the cost of each OD pair k for all k as

$$ C_k(\boldsymbol{x})\geq x_{k1}D(f_{1})+x_{k2}D(f_{2})+\cdots+x_{kn}D(f_{n}). $$
(13)

Then, by summing up Eq. (13) for all k, we have

$$ \sum\limits_{k=1}^{n}dC_k(\boldsymbol{x})\geq \sum\limits_{k=1}^{n}f_kD(f_{k}). $$
(14)

If we show

$$ D(d) \leq \sum\limits_{k=1}^{n} \frac{f_{k}}{nd}D(f_{k}), $$
(15)

then, from Eq. (14), we have

$$ \sum\limits_{k=1}^{n}C_k(\boldsymbol{x})\ge nD(d). $$
(16)

Then, it cannot hold that \(C_k(\boldsymbol{x})< D(d)\) for all k coincidently, which means that it cannot hold that after adding connections all users enjoy cost (mean response time) improvement coincidently.

We shall show Eq. (15) as follows.

Let us now denote \(\alpha_{k}=\displaystyle\frac{f_{k}}{nd}\). Note that we have the following properties of the α k : 0≤ α k  ≤ 1, k = 1...n, and \( {\displaystyle\sum\limits_{k=1\ldots n}} \alpha_{k}=1\), since \( {\displaystyle\sum\limits_{k=1\ldots n}} f_{k}=nd\). Therefore, rewriting the inequality, we must prove that

$$ D(d)\leq {\displaystyle\sum\limits_{k=1}^{n}} \alpha_{k}D(f_{k}). $$

Observe that \( {\displaystyle\sum\limits_{k=1}^{n}} \alpha_{k}f_{k}= {\displaystyle\sum\limits_{k=1}^{n}} \displaystyle\frac{f_{k}}{nd}f_{k}= {\displaystyle\sum\limits_{k=1}^{n}} \displaystyle\frac{f_{k}^{2}}{nd}\) is strictly convex and quadratic in f k and takes its minimum at \(f_{i}^{\ast}=f_{j}^{\ast}\), for all i,j = 1...n. Thus, at the minimum, since \(f^{\ast}_i=f^{\ast}_j=f^{\ast}\) and \(\sum_{k=1}^n f^{\ast}=nf^{\ast}=nd\), we have that \(f_{k}^{\ast}=d\). So \(\alpha_{k}^{\ast}f_{k}^{\ast}={d}/{n}\) for all k = 1...n. Thus, we can bound the sum, \( {\displaystyle\sum\limits_{k=1}^{n}} \alpha_{k}f_{k}\), by the value d, i.e., 

$$ d\leq {\displaystyle\sum\limits_{k=1}^{n}} \alpha_{k}f_{k}. $$

Then, since D(·) is non-decreasing and convex, we have that

$$ D(d)\leq D\left({\displaystyle\sum\limits_{k=1}^{n}} \alpha_{k}f_{k}\right)\leq {\displaystyle\sum\limits_{k=1}^{n}} \alpha_{k}D(f_{k}), $$

which proves Eq. (15) and, thus, our result.

Remark 2

From the above, we see that under any static load balancing policy, not only noncooperatively but also cooperatively, it is impossible that all users benefit coincidently from adding connections to homogeneous distributed computing systems. □

6 Concluding remarks

The present paper has examined Wardrop and Nash systems. Recall that we have considered systems with fixed numbers of nodes. The results imply the following: For Wardrop systems, the degree of coincident cost improvement may increase without bound by adding connections in spite of the fact that no Wardrop system has been found for which the degree of coincident cost degradation can increase without bound. On the other hand, for Nash systems, the degrees of both coincident cost improvement and degradation can increase without bound.

In particular, we have seen that in Wardrop systems representing heterogeneous distributed computing systems, there is neither cost improvement nor cost degradation coincidently for all users by the addition of connections. On the other hand, while it has already been shown that Nash systems representing homogeneous distributed computing systems may experience cost degradation for all users when adding connections, we show here that homogeneous distributed systems, under any load balancing policies including cooperative and noncooperative ones, cannot experience cost improvement for all users coincidently by adding connections.