Amar Prakash Azad

Eitan Altman
email: eitan.altman@sophia.inria.fr

R El-Azouzi

Routing Games : From Egoism to Altruism

Keywords: Routing game, Altruism, Nash equilibrium, Performance analysis, Cooperation

The paper studies the routing in the network shared by several users. Each user seeks to optimize either its own performance or some combination between its own performance and that of other users, by controlling the routing of its given flow demand. We parameterize the degree of cooperation which allows to cover the fully non-cooperative behavior, the fully cooperative behavior, and even more, the fully altruistic behavior, all these as special cases of the parameter's choice. A large part of the work consists in exploring the impact of the degree of cooperation on the equilibrium. Our first finding is to identify multiple Nash equilibria with cooperative behavior that do not occur in the non-cooperative case under the same conditions (cost, demand and topology). We then identify Braess like paradox (in which adding capacity or adding a link to a network results in worse performance to all users) in presence of user's cooperation. We identify another type of paradox in cooperation scenario: when a given user increases its degree of cooperation while other users keep unchanged their degree of cooperation, this may lead to an improvement in performance of that given user. We then pursue the exploration and carry it on to the setting of Mixed equilibrium (i.e. some users are non atomic-they have infinitesimally small demand, and other have finite fixed demand). We finally obtain some theoretical results that show that for low degree of cooperation the equilibrium is unique, confirming the results of our numerical study.

I. INTRODUCTION

Non-cooperative routing has long been studied both in the framework of road-traffic as well as in the framework of telecommunication networks. Such frameworks allow to model the flow configuration that results in networks in which routing decisions are made in a non-cooperative and distributed manner between the users. In the case of a finite (not very large) number of agents, the resulting flow configuration corresponds to the so called Nash equilibrium [START_REF] Basar | Dynamic Noncooperative Game Theory[END_REF] defined as a situation in which no agent has an incentive to deviate unilaterally. The Nash equilibrium has been extensively used in telecommunications, see e.g. [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], [START_REF] Kameda | A case where a paradox like Braess's occurs in the Nash equilibrium but does not occur in the Wardrop equilibrium -a situation of load balancing in distributed computer systems[END_REF]. The authors in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] studied a routing games in which each user has a given amount of flow to ship and has several paths through which he may split that flow. Such a routing game may be handled by models similar to [START_REF] Park | Quality of service provision in noncooperative networks with diverse user requirements[END_REF] in the special case of a topology of parallel links. This type of topology is studied in detail in the first part of [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] as well as in [START_REF] Altman | Equilibria for multiclass routing problems in multi-agent networks[END_REF]. However, the model of [START_REF] Park | Quality of service provision in noncooperative networks with diverse user requirements[END_REF] does not extend directly to other topologies. Indeed, in more general topologies, the delay over a path depends on how much traffic is sent by other users on any other path that shares common links. Routing games with general topologies have been studied, for example, in the second part of [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], as well as in [START_REF] Altman | Equilibria for multiclass routing problems in multi-agent networks[END_REF]. A related model was studied thirty years ago by Rosenthal in [START_REF] Rosenthal | A class of games possessing pure strategy nash equilibria[END_REF], yet in a discrete setting. It is shown that in such a model there always exists a pure strategy Nash equilibrium. He introduces a kind of discrete potential function for computing the equilibrium. Nevertheless if a player has more than 1 unit to ship such an equilibrium doesn't always exist.

In this work, we embark on experimental investigation of the impact of cooperation in the context of routing games. In particular we consider parallel links and load balancing network topology for investigation, originally presented in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] and [START_REF] Kameda | Braess-like Paradoxes in Distributed Computer Systems[END_REF] in the context of selfish users. The experimentation is mainly aimed at exploring some strange behaviors which appears in presence of user's partial cooperation (Cooperation in Degree), which is further strengthened with some theoretical results.

Firstly, we identify loss of uniqueness of Nash equilibria. We show by a simple example of parallel links and load balancing network that there may exist several such equilibria. Moreover, even the uniqueness of link utilization at equilibria may fail even in the case of simple topology. A similar example of parallel links, in absence of the cooperation between users there would be a single equilibrium [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. Beyond Nash equilibrium we investigate further in the setting of Mixed users i.e. where there are two types of users, Group user and Individual users. Group users seek Nash equilibrium while the Individual users seek equilibrium with Wardrop conditions. Strengthening our earlier finding, we observe loss of uniqueness with partial cooperation against the unique solutions shown in [START_REF] Boulogne | Mixed Equilibrium for Multiclass Routing Games[END_REF] for selfish users. However in the latter section (Sec. V), we show theoretically that there exist uniqueness of Nash equilibrium under some conditions in the presence of cooperation between users.

Secondly, we identify paradoxical behavior in presence of such cooperation. One of the observed paradox here is a kind of Braess paradox, a well studied paradox in routing context. Braess paradox has attracted attention of many researchers in context of routing games especially related to upgrading the system, see [START_REF] Bean | Braess' paradox in a loss network[END_REF]- [START_REF] Kameda | Braess-like Paradoxes in Distributed Computer Systems[END_REF]. The famous Braess paradox tell us that increasing resources to the system leads to degraded performance in some cases. Such paradox is originally shown to exist in many scenarios, e.g. Braess network in [START_REF] Kameda | How harmful the paradox can be in Braess/Cohen-Kelly-Jeffries networks[END_REF], Load balancing network in [START_REF] Kameda | Braess-like Paradoxes in Distributed Computer Systems[END_REF]. Although such paradoxes are found even in the case of selfish users earlier, their existence even in case of such partial cooperation is highlighted here. We show that as the link capacity increases the overall cost of a user increases i.e. addition of resources in the system can tentatively lead to degraded performance. Even more, we also identify another kind of paradox related to degree of Cooperation: When a user increases its degree of cooperation while other users keep their degree of cooperation unchanged, leads to performance improvement of that user. We also observe similar behavior even when other user also increase their degree of cooperation. Altruism is talked in the context of economics in [START_REF]Handbook of the Economics of Giving, Altruism and Reciprocity[END_REF] as follows: "Motivationally, altruism is the desire to enhance the welfare of others at a net welfare loss to oneself". One may pose the question of whether there is any sense in analyzing altruism in networking context. is there any reason to expect an ISP to take routing decision so as to maximize the utility of other users? We believe that altruistic behaviour can be rewarding for the ISP as it can attract demand. Already in [START_REF] Korilis | Architecting Non cooperative Networks[END_REF] it was shown that if some small amount of flow is controlled by network manager and the latter routes it in some altruistic way then this can enable the manager to impose an efficient equilibrium (One that coincides with the global optimum).

The paper is structured as follows: in section II, we present the system model, define our framework of cooperative user and, formulate the problem. Further in section III we detail the numerical investigation and summarize the findings. Based on one of the findings, we depict more examples identifying Braess paradox in the setting of Nash game in subsection III-C. In section IV, mixed equilibrium is illustrated. In section V, we develop theoretical results to show the conditions where uniqueness can be established in presence of users cooperation. In section VI we summarize the study of impact of cooperation.

II. SYSTEM MODEL

We consider a network (V, L), where V is a finite set of nodes and L ⊆ V × V is a set of directed links. For simplicity of notation and without loss of generality, we assume that at most one link exists between each pair of nodes (in each direction). For any link l = (u, v) ∈ L ,define S(l) = u and D(l) = v. Considering a node v ∈ V, let In(v) = {l : D(l) = v} denote the set of its in-going links, and Out(v) = {l : S(l) = v} the set of its out-going links.

A set I = {1, 2, ..., I} of users share the network (V, L), where each source node acts as a user in our frame work. We shall assume that all users ship flow from source node s to a common destination d. Each user i has a throughput demand that is some process with average rate r i . User i splits its demand r i among the paths connecting the source to the destination, so as to optimize some individual performance objective. Let f i l denote the expected flow that user i sends on link l. The user flow configuration f i = (f i l ) l∈L is called a routing strategy of user i. The set of strategies of user i that satisfy the user's demand and preserve its flow at all nodes is called the strategy space of user i and is denoted by F i , that is:

F i = {f i ∈ R |L| ; l∈Out(v) f i l = l∈In(v) f i l + r i v , v ∈ V},
where r i s = r i , r i d = -r i and r i v = 0 for v = s, d. The system flow configuration f = (f 1 , ..., f I ) is called a routing strategy profile and takes values in the product strategy space

F = ⊗ i∈I F i .
The objective of each user i is to find an admissible routing strategy f i ∈ F i so as to minimize some performance objective, or cost function, J i , that depends upon f i but also upon the routing strategies of other users. Hence J i (f ) is the cost of user i under routing strategy profile f .

A. Nash equilibrium

Each user in this frame work minimizes his own cost functions which leads to the concept of Nash equilibrium. The minimization problem here depends on the routing decision of other users, i.e., their routing strategy

f -i = (f 1 , ..., f i-1 , f i+1 , ...f I ), Definition 2.1: A vector f i , i = 1, 2, .
.., I is called a Nash equilibrium if for each user i, f i minimizes the cost function given that other users' routing decisions are f j , j = i. In other words,

J i ( f 1 , f 2 , ..., f I ) = min f i ∈F i J i ( f 1 , f 2 , ..., f i , ..., f I ), i = 1, 2, ..., I, (1)
where F i is the routing strategy space of user i. Nash equilibrium has been discussed in the context of non-cooperative game with selfish users quite often in recent studies.

In this paper we study a new aspect of cooperative routing games where some users cooperate with the system taking into account the performance of other users. We define this degree of Cooperation as follows :

Definition 2.2: Let -→ α i = (α i 1 , .., α i |I| )
be the degree of Cooperation for user i. The new operating cost function Ĵi of user i with Degree of Cooperation, is a convex combination of the cost of user from set I,

Ĵi (f ) = k∈I α i k J k (f ); k α i k = 1, i = 1, ...|I|
where Ĵi (f) is a function of system flow configuration f with cooperation. Based on the degree of Cooperation vector, we can view the following properties for user i,

• Non cooperative user : if α i k = 0, for all k = i. • Altruistic user : User i is fully cooperative with all users and does not care for his benefits, i.e.,

α i i = 0. • Equally cooperative -if α i j = 1
|P| , user i is equally cooperative with each user j, where j ∈ P, P ⊆ I. Note that Ĵi (f ) is the new effective cost function with degree of Cooperation, where it takes into account the cost of other users. Although a user cooperating with the system, it attempts to minimize its own operating cost function in the game setting. Hence such frame work can be classified under non-cooperative games and the thus we can benefit to apply the methods of non-cooperative games to obtain various quantities e.g. Nash equilibria.

III. NUMERICAL INVESTIGATION OF THE ROLE OF

COOPERATION

In this section we detail some numerical examples to study the routing game in the presence of cooperation between some users. In these examples, we use two types of cost functions : linear function which is often used in the transportation network and M/M/1 function which is used in the queuing networks. We consider two network topologies : parallel links [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] and load balancing networks [START_REF] Kameda | A case where a paradox like Braess's occurs in the Nash equilibrium but does not occur in the Wardrop equilibrium -a situation of load balancing in distributed computer systems[END_REF] which are defined below Load Balancing Network: A simple load balancing topology of network G consists of 3 nodes is depicted in Fig. 1(a). This topology has been widely studied in context of queuing networks. The nodes are numbered 1, 2, 3 and communication links among them are numbered as l 1 , l 2 , l 3 , l 4 . Node 1, 2 acts as source node and node 3 acts as destination node. Link l 1 , l 2 are directed links for nodes 1, 3 and nodes 2, 3 where as, link l 3 , l 4 are directed link for nodes 1, 2 and nodes 2, 1. Cost function of user i is the sum of cost of each link J i = l∈{1,...4} f i l T l (f l ) , where T l (f l ) is the link cost function. The cost of each user i with cooperation can be defined as below, Parallel Links Network: A simple parallel links topology of network G consists of 2 nodes is depicted in Fig. 1(b) which is originally discuses in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. The nodes are numbered 1, 2 and communication links between them are numbered as l 1 , l 2 . Node 1 acts as source node and node 2 acts as destination node. Cost function of user i is the sum of cost of each link J i = l∈{1,2} f i l T l (f l ) , where T l (f l ) is the link cost function. The cost of each user i with cooperation can be defined as below,

Ĵi = l∈{1,...4} k∈{1,2} α i k f k l T l (f l ) (2)
Ĵi = l∈{1,2} k∈{1,2} α i k f k l T l (f l ) (3)
For each network topology, we consider both the cost functions for investigation. Linear Cost Function: Linear link cost function is defined as, T l (f li ) = a i f li + g i for link i = 1, 2, where as, T l (f lj ) = cf lj + d for link j = 3, 4.

M/M/1 Delay Cost Function: The link cost function can be defined as, T l (f li ) =

1 Cl i -fl i
, where C li and f li denote the total capacity and total flow of the link l i . Note that this cost represents the average expected delay in a M/M/1 queue with exponentially distributed inter arrival times and service times under various regimes such as the FIFO (First In First Out) regime in which customers are served in the order of arrivals, the PS (Processor sharing) regime and the LIFO (Last In First Out) regime. This same cost describes in fact the expected average delays in other settings as well such as the M/G/1 queue (exponentially distributed inter arrival times and general independent service times) under the PS or the LIFO regime.

A. Numerical Examples

We consider two users share a network. We distinguish two cases. An asymmetric case in which the user 1 is cooperative with α 1 1 > 0 and user 2 is noncooperative, i.e., α 2 2 = 0. The second case is symmetric case in which both users are cooperative with the same degree of cooperation α, i.e. α = α 1 1 = α 2 2 . We compute the Nash equilibrium at sufficiently many points of degree of Cooperation α in the interval [0,1] and plot the corresponding user cost and user flow. Here user flow signifies the fraction of demand flowing in the corresponding user destination link. Since we consider only two links, the fraction of demand flow in one route complements that of the other route. Hence we plot the fraction of demand corresponding to the user i.e. f 1 l1 for user 1 and f 2 l2 for user 2. In sequel we describe five experiments as follows:

Experiment 1) Load balancing network with linear link cost: In Fig. 2(a)-2(b), we plot the cost and the flow obtained at Nash equilibrium versus α in the range [0, 1]. We use the following parameters, a 1 = a 2 = 1, g 1 = g 2 = 0, c 1 = c 2 = 0.1, d 1 = d 2 = 0.2. Note that the plot of user 1 and 2 overlap in the figure in symmetrical case. This is due to the same degree of Cooperation.

Experiment 2) Parallel links with linear link cost: In Fig. 3(a),3(b), we plot te cost function and the flow for both users obtained at Nash equilibrium for α in the range of [0, 1]. We use the following parameters,

a 1 = 4, a 2 = 2, g 1 = 1, g 2 = 1, r 1 = 1.2, r 2 = 1.
Experiment 3) Load balancing network with M/M/1 link cost: Consider the parameters for the link cost functions as, C l1 = 4.1, C l2 = 4.1, C l3 = 5, C l4 = 5, r 1 = 1, r 2 = 1. In Fig. 4(a),4(b), we plot cost and flow obtained at Nash equilibrium for 0 ≤ α ≤ 1.

Experiment 4) Parallel links with M/M/1 link cost: In Fig. 5(a),5(b), we plot the cost function and the flow for both users obtained at Nash equilibrium versus α. We use the following parameter, C l1 = 0.001, C l2 = 0.001, r 1 = 1, r 2 = 1.

Experiment 5) Load balancing network with linear link cost: We vary the link cost for l 3 and l 4 by varying the parameter c. More precisely, we increase c from 0 to

α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.
range of cooperation. In Fig. 345, we obtain multiple Nash equilibria as above for some range of cooperation. In Fig. 3(a),3(b), 5(a),5(b) although α 1 = α 2 , due to other parameter being non-symmetrical, we do not observe a symmetrical plot for "J 1 , J 2 -Symmetrical". Uniqueness of Nash equilibrium is shown in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], for a similar situation as in Fig. 2(a),2(b) for selfish user, but we observe loss of uniqueness when users have some cooperation.

C. Braess like paradox

We also observe a Braess kind of paradox which is related to performance when additional resource is added to the system. To understand this, consider the topology of experiment 1, i.e., the load balancing network topology. Consider a configuration where initially link l 3 and l 4 has very high cost (i.e. effectively doesn't exist) and latter the link cost is reduced to a low value e.g. c = 0 and d = 0.5. This can be interpreted as an additional resources added to the system. Observe

C l 1 = 4.1, C l 2 = 4.1, C l 3 = 5, C l 4 = 5, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.
than for the initial configuration the cost of user 1 is J 1 = 1 and cost of user 2 is J 2 = 1 in experiment 1. However in the latter configuration which is depicted in Fig. 2(a), we observe the cost of user 1 and 2 is greater that 1 at Nash equilibria. This explains degradation of performance when resources are increased. A very clearer observation can be made in Fig. 6 where the link cost for link l 3 and l 4 is parameterized. Due to multiple Nash equilibria we see two curves. The lower curve corresponds to Nash solutions where flow for each user choose direct link to destination while the upper curve correspond to mixed strategy solution where a fraction of flow for each user choose direct link path. Notice that user cost is improving as the link cost is increasing for the upper curve. Such paradox is widely studied as Braess paradox in many literature. Above we identified the existence of Braess paradox in load balancing network. Now we identify the Braess paradox in parallel links topology. Consider the parameters as follows, the scenario when initially the link l 3 , l 4 does not exist, while latter they are added in the system. In other words, the initially the capacity C 3 = 0, C 4 = 0, and latter it is C 3 = 10, C 4 = 10. Note that when C 3 = 0, C 4 = 0, flow at Nash equilibrium is trivially f l1 = 1, f l2 = 1. In the following, we consider two scenarios of degree of cooperation :

C l1 = 4.1 C l2 = 4.1 r 1 = 2 r 2 = 1. Consider
• Only one user is Cooperative : The degree of Cooperation taken in this case is α 1 = 0.93, α 2 = 0.

On increasing the capacity C 3 , C 4 from 0 → 10, the cost functions at Nash equilibrium are obtained as J 1 = 0.952 → 2.06, J 2 = 0.3225 → 0.909 and the flows are f l1 = 2 → 0, f l2 = 1 → 0.0951.

We also obtain another Nash equilibrium where the cost functions and the flow doesn't change from initial state. Note that increasing the capacity in the network degrades the performance at the first Nash equilibrium.

• Both users are Cooperative : We repeat the above experiment with the degree of Cooperation α 1 = 0.9, α 2 = 0.9. The cost functions at Nash equilibrium are obtained as J 1 = 0.952 → 1.247, J 2 = 0.3225 → 0.430. We again obtain another Nash equilibrium where the cost functions and the flow doesn't change from initial state. Note that again increasing the capacity in the network degrades the performance at the first Nash equilibrium.

D. Paradox in cooperation

In Fig. 2(a), we observe that J 1 has higher cost than J 2 . This is intuitive because user 2 is selfish user while user 1 has a varying degree of Cooperation. In particular remark that α 1 ↓ 0, J 1 ↑ J 2 . But this is not true for the whole range of Cooperation. Observe in Fig. (3.a) a non intuitive behavior for some small range of α 1 (approximately α 1 ∈ (0.87, 1). Notice that when the degree of cooperation α 1 increases (i.e. increase in its altruism) while other user be pure selfish (α 2 = 0), leads to improved cost of user 1. This is a paradoxical behavior, we call it paradox in cooperation. This paradox also exist in case of symmetrical cooperation (see J 1 -Symmetrical, J 2 -Symmetrical ) in the range of α approximately (0, 0.4). Notice that such paradox is still observed in Fig. 34. Remark that such paradox exist only when there are multiple equilibria.

IV. MIXED EQUILIBRIUM

The concept of mixed-equilibrium (M.E.) has been introduced by Harker [START_REF] Harker | Multiple equilibrium behaviors on networks[END_REF] (and further applied in [START_REF] Wie | A differential game approach to the dynamic mixed behavior traffic network equilibrium problem[END_REF] to a dynamic equilibrium and in [START_REF] Boulogne | Mixed Equilibrium for Multiclass Routing Games[END_REF] to a specific load balancing problem). Harker has established the existence of the M.E., characterized it through variational inequalities, and gave conditions for its uniqueness. We discuss here the behavior of mixed equilibrium in presence of partial cooperation. Consider the network (V, L) shared by two types of users: (i) group users (denoted by N )

The following result establishes the uniqueness of Nash Equilibrium in case of positive flow.

Theorem 5.1: Consider the cost function of type 5.2. Let f and f be two Nash equilibria such that there exists a set of links L 1 such that {f i l > 0 and f i l > 0, i ∈ I} for l ∈ L 1 , and {f i l = f i l = 0, i ∈ I} for l ∈ L 1 . Then f = f . Refer [START_REF] Amar Prakash Azad | Routing Games : From Egoism to Altruism[END_REF] for proof.

B. Uniqueness of NEP in general topology

It is a hard to characterize system behavior for general network with user's partial cooperation. For selfish users, it is shown that there exist uniqueness for Nash equilibrium point(NEP) under Diagonal Strict Convexity in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF].

We consider a special case of cooperation where a user cooperates equally with all other users i.e.

Ĵi (f) = (1 -α i )J i (f) + α i k J k (f)
Consider the cost function of type 5.2. The cost function of each user on link l can be thus given by Ĵi l (f ) = ((1α i )f l + (1 -2α i )f -i l )T l (f l ) (4) Theorem 5.2: Consider the cost function of type 5.2. Let f and f be two Nash equilibria such that there exists a set of links L 1 such that {f i l > 0 and f i l , i ∈ I} for l ∈ L 1 , and {f i l = f i l = 0, i ∈ I} for l ∈ L 1 . Then f = f . Refer [START_REF] Amar Prakash Azad | Routing Games : From Egoism to Altruism[END_REF] for detailed proof.

VI. CONCLUDING REMARKS

This paper is aimed at exploring user performance in routing games where a finite number of users take into account not only their performance but also other's user's performance. We have parameterized the degree of Cooperation to capture the user behavior from altruistic to ego-centric regime. We notice some strange behaviors. Firstly we show the existence of multiple Nash equilibria by a simple example of parallel links and load balancing networks in contrast to the unique Nash equilibrium in case of selfish users. Moreover, we then explored the mixed user scenario, which is composed of a finite number of Group type user seeking Nash equilibrium and infinitely many Individual type users satisfying Wardrop condition. We illustrate loss of uniqueness of equilibrium even in mixed users scenario in presence of partial cooperation by an example for parallel links network. However it is known to have unique equilibrium in presence of only finitely many selfish users in similar settings.

Secondly we identify two kinds of paradoxical behavior. We identify situation where well known Braess paradox occurs in our setting of cooperation. We show using an example of parallel links network with M/M/1 link cost that addition of system resources indeed degrades the performance of all users in presence of some cooperation, while it is well known that this is not true for this setting with only selfish users.

We also identify another type of paradox, paradox in cooperation: i.e. when a given user increases its degree of cooperation while other users keep unchanged their degree of cooperation, this may lead to an improvement in performance of that given user. In extreme sense a user can benefit itself by adopting altruistic nature instead of selfishness.

  Fig. 1. Network Topology

Fig. 2 .Fig. 3 .

 23 Fig. 2. Topology : Load balancing, Cost function : Linear, Parameters : a1 = a2 = 1, g1 = g2 = 0, c1 = c2 = 0.1, d1 = d2 = 0.2., Cooperation : { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

Fig. 4 .

 4 Fig. 4. Topology : Load balancing, Cost function : M/M/1 Delay, Parameters : C l 1 = 4.1, C l 2 = 4.1, C l 3 = 5, C l 4 = 5, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Topology : Parallel links, Cost function : M/M/1 Delay, Parameters : C l 1 = 0.001, C l 2 = 0.001, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

1000 in the steps of 20 and compute Nash equilibrium at each point. In Fig. 6, we plot the cost of each user with the increasing link cost of the link l 3 and l 4 . Note high link cost signifies that link doesn't exit.

We analyze the results obtained from the experimentation done above. We will be using α = α 1 here for simplicity as we have fixed α 2 = 1 for asymmetrical case and α = α 1 = α 2 for symmetrical case. The important behavior can be summarized under following two headings.

B. Non uniqueness of Nash equilibrium

In Fig. 2 we observe that there exist multiple Nash equilibria for both symmetrical case and asymmetrical case. Note that multiple Nash equilibria is constrained to some range of cooperation(α). However there also exist some range of cooperation where unique solution exist. We observe that there exist three Nash equilibrium for some range of cooperation, two Nash equilibrium at one point and, unique Nash equilibrium for some : these users have to route a large amount of jobs; (ii) individual users; these users have a single job to route through the network form a given source to a given destination. There are infinitely many individual users. For simplicity, we assume that all individual users have a common source s and common destination d. Let P be the set of possible paths which go from s to d.

Cost function

is the cost function of path p for each individual user. The aim of each user is to minimize its cost, i.e., for i ∈ N , min f i J i (f ) and for individual user, min p∈P F i p (f ). Let f p be the amount of individual users that choose path p.

Definition 4.1:

A. Mixed equilibrium in parallel links

In the following proposition, we provide some closed form of Mixed equilibrium in parallel links.

Proposition 1: Consider parallel links network topology (Fig. 1(b)) and M/M/1 delay link cost function. Consider that a Group type user and Individual type users are operating in this network. The mixed equilibrium strategy (f 1 * l1 , f 2 * l2 ) can be given exactly as follows, 1) When Both link is used at Wardrop equilibrium:

where

2) When only one link ( 1) is used at Wardrop equilibrium:

the unique (if there exists) root of the quadratic equation

T h e c o e f fi c i e n t s of the quadratic equation are

3) When only one link (2) is used by Wardrop user:

2 , r 1 ) and M 3 is the unique root(if there exist) of the quadratic equation

Refer technical report [START_REF] Amar Prakash Azad | Routing Games : From Egoism to Altruism[END_REF] for detailed proof.

Corollary 1: Consider the symmetric parallel links, i.e., (C 1 = C 2 = C, r 1 = r 2 = r) network with M/M/1 delay link cost function. In a mixed user setting the mixed equilibrium strategy (( [START_REF] Amar Prakash Azad | Routing Games : From Egoism to Altruism[END_REF] for detailed proof.

In Fig. [START_REF] Kameda | A case where a paradox like Braess's occurs in the Nash equilibrium but does not occur in the Wardrop equilibrium -a situation of load balancing in distributed computer systems[END_REF], we depict the mixed equilibrium strategy(flow) for the varying degree of cooperation(α).

Observe the loss of uniqueness of mixed equilibrium in presence of partial cooperation. It is known to have unique equilibrium in the network setting with finitely many selfish users [START_REF] Boulogne | Mixed Equilibrium for Multiclass Routing Games[END_REF]. Remark that we have already shown in the previous section that there exist multiple Nash equilibria in presence of partial cooperation. Due to space limitation we illustrate this behavior with only parallel links topology and M/M/1 cost function. However we identify a similar remark from other configuration also.

V. EXISTENCE AND UNIQUENESS OF EQUILIBRIUM

Having noted the existence of multiple Nash equilibrium in sec.III-A using various examples, we here establish the conditions under which unique nash equilibrium exist. Uniqueness of Nash equilibrium is shown in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] in case of non-cooperative games for parallel links topology. Under some condition, uniqueness is shown for general topology also. In this section we follow the similar structure to establish the uniqueness for parallel links topology in case of our setting of user cooperation.

We follow some assumptions on the cost function J i same as in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF].

Assumption 5.1: : G1:

Note the inclusion of +∞ in the range of Ĵi l , which is useful to incorporate implicitly and compactly and additional constraints such as link capacities. Also note that the assumption G3 is stronger than in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF].

Function that comply with these general assumptions, we call type G function. For selfish user operating on parallel links NEP is shown to exist in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] with the function which comply with the type G function.

We shall mainly consider cost functions that comply with the following assumptions: Assumption 5.2: : B1:

Functions that comply with these assumptions are referred to as type-B functions.

Remark 5.1: In Assumption B1, T l (f l ) is the cost per unit of flow (for example mean delay) on the link l, for the total utilization, f l = i∈I f i l , of that link. Note that if T l (f l ) is the average delay on link l, it depends only on the total flow on that link. The average delay should be interpreted as a general congestion cost per unit of flow, which encapsulates the dependence of the quality of service provided by a finite capacity resource on the total load f l offered to it.

A special kind of type-B cost function is that which corresponds to an M/M/1 link model. In other words, suppose that C1:

Where C l is the capacity of the link l. Function that comply with these requirements are referred to as type-C functions. Such delay functions are broadly used in modeling the behavior of the links in computer communication networks [START_REF] Bertsekas | Data Networks[END_REF], [START_REF] Kleinrock | Queueing Systems[END_REF].

A. Parallel links network topology

In this section we study the special case where the users from set I shares a set of parallel communication links L = {1, 2....L} interconnecting a common source node to a common destination node. In [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], uniqueness of Nash equilibrium is shown for the selfish users (when user do not cooperate in managing the communication link) in parallel links, where the cost functions (J i (f )) of users are assumed to hold assumption 5.2. However this is not true when the users have cooperation in degree as defined in sec.(2.2). We observe that assumption 5.2 is not sufficient to guarantee unique Nash equilibrium in our setting. It is a harder problem to characterize system behavior for general degree of cooperation. Hence we consider a special case of cooperation where a user cooperative with similar cooperation with all other users i.e.

Consider the cost function of type 5.2. The cost function of each user on link l is given by Ĵi l (f ) = ((1

T l (f l ) Existence problem in the case of Nash equilibrium for the cost function Ĵi l (f) can be directly studied as in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. Note that in case of α i < 0.5 for all i ∈ I, the uniqueness of Nash equilibrium is guaranteed from E. Orda et al. [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. Note that when α i < 0.5, the function K i l (f -i l , f l ) is strictly increasing function in f -i l and f l . Uniqueness of Nash equilibrium can be also observed in case of All-positive flow in each link. By All-positive flow we mean, if there is a positive flow of at least one user on a link then all user have strictly positive flow on that link.


ZAMM . Z. angew. Math. Mech. 77 (1997) 7, 519-526 DELL'ISOLA, F., WOZNIAK, C.

On Continuum Modelling the Interphase Layers in Certain Two-Phase Elastic Solids

I n this paper we propose a continuum model of a moving transition layer smoothly separating two different solid phases of a certain elastic material continuum and we investigate some necessary conditions to its existence and propagation.

A n application of this model to the analysis of waue propagation in micro-damaged media with open-and closed-micro cracked phases is shown. MSC (1991): 73K99, 73D99

Introduction

In the literature great interest is paid to the study of propagation of discontinuity surfaces in continuous media. Such surfaces are introduced as models of a large variety of phenomena (cf. for instance [lo]) including various kind of phase transitions. When these phenomena need more detailed description the modelization is improved endowing the discontinuity surfaces with more sophisticated structure, i.e. introducing suitable surface fields and postulating for them some balance equations. Such an approach (for a more careful discussion see [START_REF] Dell'isola | Deduction of thermodynamic balance laws for bidimensional nonmaterial directed continua mod-7 WOZNIAK, Cz.: Refined macro-dynamics of periodic structures[END_REF], [ll], [START_REF] Dell'isola | On the derivation of thermomechanical balance equations for continuous systems with nonmaterial 13 TRUESDELL, C. : Rational continuum mechanics[END_REF]) sometimes leads to some models which are questionable from both the logical and physical point of view. On the other hand the passage from one phase to the other may be not always abrupt. In this case the interface has to be regarded as a region to be modeled as a three-dimensional interphase layer (see [START_REF] Dell'isola | Deduction of thermodynamic balance laws for bidimensional nonmaterial directed continua mod-7 WOZNIAK, Cz.: Refined macro-dynamics of periodic structures[END_REF] and also the review paper [START_REF] Rubinstein | On mathematical models for solid-liquid zones in a two-phase monocomponent system and in binary alloys[END_REF] on mushy regions arising in phase transitions) in which we can assume to deal with a certain mixture of both phases. This circumstance occurs also in some particular cases of solid-solid phase transitions described for instance in [9]. Hence the question arises about the description of the properties of the material constituting the interphase layer and about the conditions under which this layer can exist and propagate.

In this paper we propose a continuum model of a moving transition layer smoothly separating two different solid phases of a certain elastic material continuum and we investigate some necessary conditions to its existence and propagation. The term phase means here state of a considered continuum, characterized by a given constitutive equation. The differences in material behaviour in different states of the solid body do not arise only because of structural phase transitions (e.g. martensitic transformations, described on the micro-level by discrete models in [l-31) but can be also caused by the existence of different strain energy functions related to appropriate different classes of local deformations. Such a situation occurs, for example, if we consider a damaged medium in which micro-cracks are in different regions (phases) all open, all closed or partly open and partly closed (cf. [START_REF] Wozniak | Laminated media with interface defects[END_REF]): this last possibility characterizing the interfacial region, in which a phase transition takes place.

The basic idea of our approach is that the phase transition occurs in a certain thin non-material (or following the terminology of TRUESDELL [13] non-substantial) mowing layer (the interphase layer), separating different phases of the body, in which the strain energy function on a macro-level is not well defined. The main hypothesis is that the interphase layeron a micro-levelis constituted by an arrangement of two different phases forming a definite banded quasi-periodic microstructure. After scaling this microstructure down we arrive at the macro-model of the interphase layer representing a certain fine mixture of both phases. To this end we adapt the micro-macro modelling procedure proposed in [START_REF] Wozniak | A nonstandard method of modelling of thermoelastic periodic composites[END_REF] for composite materials (the similarity between composite material structure and fine phase mixtures was already noted in [START_REF] Ball | Fine phase mixtures as minimizers of energy[END_REF] ) . Hence on the macro-level the interphase layer is modelled as a shell-like region of the medium, moving independently of the body motion. By means of an averaging procedure of this region over its thickness (cf. [START_REF] Dell'isola | Deduction of thermodynamic balance laws for bidimensional nonmaterial directed continua mod-7 WOZNIAK, Cz.: Refined macro-dynamics of periodic structures[END_REF]) this model in special cases can be simplified obtaining as model for the interface a discontinuity surface, eventually endowed with material properties.

Intending to postpone the modelling of more complex phenomena, in this paper we will restrict ourselves to describe those in which purely mechanical notions are needed (e.g. diffusion less solid-solid phase transformations): non-mechanical notions as temperature or entropy are excluded from the present analysis. i) the material behaviour of the interphase layer depends not only on the material properties of both phases but also on the propagation speed of the layer, ii) not every propagation speed of the interphase layer is possible, iii) when the interphase layer does not propagate then the material properties of the interphase layer are similar to the The main results of this contribution can be stated as follows: macro-properties of a micro-layered two component medium (cf. [7], [START_REF] Bakhvalov | Processes averaging in periodic media[END_REF]-[IS]).

Basic assumptions

We will assume that a continuum description of the motion of the considered body B is possible, so that it is possible to establish in which phase a substantial particle of B presents itself.

Motion

Let 3 be placed in the reference position BR C E where E is the set of places, whose tangent vector space is TE. In the time interval I := [to, tf] a motion p maps BR x I into E. Therefore V t E I , p ( . , t ) : B R + E .

(2.1)

We will use the following notation: pt := p ( . , t) , f t := V p t E Lin (TE) ,

Bt := ~( B R , t ) ,
where Lin (TE) is the set of invertible linear transformations mapping TE into TE. When this will not lead to misunderstanding we will skip the index t in the introduced notations.

Strain energy

We will assume that two strain energy functions WL(X, .) and W,(X, .) defined in disjoined subsets @+, @of Lin (TE), respectively, are assigned to every substantial point X in BR describing the behaviour of the two possible phases (denoted by + and -) for the considered continuum.

We will assume that at the micro-level almost every material point X, X E BR, is present only in one of these two phases. This means that either Vpt(X) E @+ or Vpt(X) E @-(but not both) holds throughout the body except possibly at some points, lines or surfaces in BR.

However in certain regions the sets of the substantial points which present themselves in the phase + orcan have a very complicated structure, being, for instance, composed by many disjoined connected parts whose length dimensions can be neglected on the macro-level. We will refrain from the detailed description of all phenomena occurring during the change of phase. Therefore we will pass to a macro-description of phase change and we will introduce the concept of a certain ideal mixture of both phases constituting what will be called a non-substantial interphase layer occupying respectively in the referential and spatial descriptions the regions PR(t) and q. To be more precise we will assume that :

i) The region BR and consequently spatial region Bt can beon a macro-level and at every time instant tpartitioned into three mutually disjoint subregions (which in general are non-substantial) @(t) and Bi(t) such that

In these regions the considered elastic material is present in different phases: the interphase layer occupies the region PR(t) separating the regions B;(t) occupied by the phases + andrespectively.

ii) Some macro-descriptors can be defined in PR(t) which allow the description of some of the more relevant interfacial phenomena in terms of fields smoothly varying from one phase to the other.

Transition layer assumptions

We will assume, rephrasing [START_REF] Dell'isola | Deduction of thermodynamic balance laws for bidimensional nonmaterial directed continua mod-7 WOZNIAK, Cz.: Refined macro-dynamics of periodic structures[END_REF], that:

2.3.1)

The interfacial region PR(t) can be obtained by shifting along the normal a given surface &. As a consequence of this assumption we can define a scalar vector field c(X, t) and a unit normal field n(X, t) in PR(t) mapping every X E PR(t) into the unique 8' and normal (to Zt) vector corresponding to it. We remark that, if c, is the field of the normal speed of the surface Zt, then the following equality holds

x -(X, t) = C,(X, t ) . 2% 2.3.
2) The boundary of PR(t) can be partitioned as follows: @(t) = 2; u 2; , where Z : and 2; are the respectively &-shifted and (-&)-shifted surfaces from Zt representing the surfaces dividing + andphases, respectively, from the interphase (transition) layer.

2. [START_REF] Wozniak | Laminated media with interface defects[END_REF] Assumption on the microstructure inside the interphase layer

2.4.1) F-micro-layers

In PR(t) coexist the two phases + and -. More precisely we will assume thaton a micro-levelthe interfacial region is constituted by thin micro-layers of constant thickness E each of which is partitioned into two sub layers of varying thickness (denoted respectively E+ and E -) filled with phase + andrespectively. These micro layers and sub layers are assumed to be obtained translating Zt along the normal. We will assume that 6t E = -with n > l , n and hence in our description of the microstructure of the interphase layer all terms of an order higher than E will be neglected.

2.4.2) Some auxiliary definitions

For the time being assume t, 0, and E fixed. When not causing misunderstanding we will simply use the symbol 6 for the introduced thickness &(8).

Let E + ( . ) , c ( . ) be linear functions defined on the interval [-6, 61

E

We remark that the choice of '63 and "83 can be made in order to assure the continuity of hE at points separating the intervals Ii. It is easy to see that neglecting terms of an order F we have that

The function hE will be called micro-shape function andas will be explained belowplays an important r6le in the modelling of the interphase layer.

In the sequel we shall also use the functions u+, udefined in [-6, 61 and given by which for O3 = 03 represent the percentage of the + andphase inside the layer descibed by the interval I, included in [-6, 61.

2.4.3) Kinematic assumptions

The motion p of the body B inside the transition layer can be represented as the sum of a macroscopic part (i.e.

independent of F )

V t E I , P ( . , ~) : B R + E , and of a superimposed small disturbance DE

V t E I , DE(-, t) : BR --+ T(E)
caused by the micro-inhomogeneity of the transition layer which has the following form: DE(X, t) := hE(X, t) Q(X, t) . VX E @(t), In this last equation Q, which we will call descriptor of interfacial layer micro-structure, models the micro-state of the considered substantial particle and hE is a suitable micro-shape function constant on every 03-shifted surface from &.

Fine phase mixture hypothesis

The macro-model of the interphase layer will be obtainedafter using the kinematic assumption 2.4.3) -by means of the limiting passage E -+ 0 in all relations describing the mechanical behaviour of the media constituting the interphase layer.

We will call the macro-model of the interphase layer obtained using the hypotheses introduced in this section interfacial fane phase mixtures. It has to be emphasized that, due to the properties of function hE, in this model all relevant quantities smoothly vary in the passage from one phase to the other.

The validity of the above formulated modelling hypotheses needs to be tested by means of the comparison of the subsequent theoretical predictions with experimental evidence. We are aware of the fact that they restrict the scope of applicability of our model, which could be improved in some particular instances introducing more sophisticated microshape functions and/or more descriptors of micro-structure.

Evolution equations

As we have stated before, we assume in this section that all quantities infinitesimal of order equal or greater than E are negligible.

This hypothesis restricts our treatment to interfaces for which the hypothesis of fine phase mixture holds.

Consequently E+ and E -are negligible. This is not the case for the relative thicknesses G* and for the strain modulators p* which remain constant when E tends to zero.

The model resulting after this limit passage will introduce for the interfacial region PR(t) a microstructured continuum with the internal variable Q. Every substantial macro-particle of this continuum contains both phases + and -, in the proportion controlled by the macro-fields G*. The state of every macro-particle is determined by its macro-strain tensor F and by the vector Q.

The evolution equations for macro-displacements and for Q are obtained postulating the principle of stationary action for motions belonging to the class specified by the hypotheses of the previous section and neglecting in the expression of the action all quantities infinitesimal together with E .

The action functional

We start expressing micro-deformation tensor f and the velocity field v in the referential description in terms of macro-deformation tensor F := VP, the descriptor Q, the macro-velocity field V := P and the propagating speed of the interfacial layer. Using the Hypotheses of subsection 2.4 and recalling that F and V are the derivatives with respect X and time t of the function P, we obtain (quantities infinitesimal with E are neglected) where the symbol { } means that the equality holds respectively in the + orphases.

the region PR(t) :

We can now introduce the action functional d for the interphase layer occupying in the reference configuration

tf d = ( X -."P) d t , to (3.3)
the kinetic energy X and the potential 9 being definedon a micro-levelas follows (dVR and dAR are respectively the volume and surface elements in the reference configuration) :

where the strain energy WR is a function of the material point X and the strain f , it is equal to Wi(X, .) or to W,(X, .) if x belongs respectively to phase + or -, @R is the mass density in the referential description and t R are the external contact forces applied on the boundary of the interfacial transition layer, which we assume are independent of the micro-structure of the layer.

Once the hypothesis of fine phase mixture is used neglecting all terms infinitesimal with E , with simple algebra one obtains the following expression for the action functional

(3.5)
where c, is defined in eq. (2.4), ~( 6 ~) := 0+(03) 0 -( 0 3 ) , we have assumed that the referential mass densities & of phase + andare equal, and we have used the following denotations:

@R = @ ; = &?g ; (WR) (X, F, Q) := o+(X) W&(X, f + ( F , (2)) + a-(x) Wi(X, f -( F , (2)).

(3.6) (3.7)

The evolution equations for macro-placement P and the descriptor Q inside PR(t) are obtained assuming that the first variation of the action d determined by equation (3.5) is vanishing.

1) Equation of motion dV dt

DivSR -eR -= 0 in @R(t) and SRN = tR on a&(t),

( 3 4
where the vector field N is the unit normal to a@R(t) and the (Piola-Kirchhoff) macro-stress-tensor SR is determined by the macro-constitutive relation

2) Propagation condition

+ pRtyc:Q = 0 in &(t) . aQ (3.

10)

We remark that equations (3.8)-(3.10) describe the behaviour of the interfacial continuum if the motion of the interfacial region PR(t) is known a priori. The equations governing the motion of this region has to be found modelling its specific physical nature, as is done, in the particular instance treated there, in sect.

It has to be emphasized that: in the proposed macro-model the properties of the continuum constituting the interphase layer can be easily determined once the constitutive properties of phases + andand the micro-structure functions ai are known; since c, is the relative velocity of the interfacial layer with respect to the referential space then the condition (3.10) is Galilean invariant; equations (3.10) is an algebraic relation among Q, F, and c: . The definition of average strain energy implies that using it one can express Q in terms of F and ci and therefore that the strain energy can be regarded as a function (WR) of the macro-strain F and the speed c,. On the other hand the physically admissible domain for a strain energy function is included in the set of independent variables for which the energy is positive: in particular this implies that some restrictions have to be expected on possible speeds c,. In the next section we find, in the case of transition layer in linear elastic solids, an explicit form of such a restriction. When we deal with a substantial layer the the speed c, is vanishing. The equations (3.8)-(3.10) reduces to those found in [START_REF] Wozniak | A nonstandard method of modelling of thermoelastic periodic composites[END_REF] where some macro-models of micro-laminated materials are considered.

An application

In this section we want to apply the model developed up to now to the study of the propagation of a particular interfacial layer.

More precisely we consider the micro-cracked material investigated in [START_REF] Wozniak | Laminated media with interface defects[END_REF]: the considered solid body is assumed damaged because of the presence of planar micro-cracks (parallel to the laminae interfaces) whose planes are characterized by a regular field n of unit vectors.

We assume that the region BR can be partitioned into three regions: i.e. the region in which the micro-cracks are open (phase +), that in which the micro-cracks are closed (phase -), and the interphase layer in which the microcracks are partly closed and partly open.

In the interphase layer a macro-strain F and one macro-descriptor Q, following the procedure showed in the previous section, are introduced.

In the considered instance the partitioning at the macro-level can be determined by means of the phase defining function and thresholds y : (X, F) E BR x Lin (TE) ++ yx(F) = n(X) . FTFn(X) -1 ;

( y -, y+) E R+ x R+ . we are in the part of the body where phase transitionon a macro-leveloccurs: i.e. in the part of the body where the knowledge of the strain F and the normal n is not sufficient to establish whether the micro-cracks are closed or open. For the points in HR(t) the knowledge of the values of y does not allow the unique determination of the strain energy which in this sense is not well-defined (cf. [START_REF] Wozniak | Laminated media with interface defects[END_REF]) at the macro-level until more the detailed description of the structure of the interfacial layer allowed by the introduction of the vector field Q is added to our model. Indeed the average strain energy (WR) is not only a function of macro-strain F but also a function of the macro-descriptor Q. We will limit ourselves to the case of a linear elastic micro-cracked material in which the vector field n is constant and to the study of interphase layers propagation in the direction of n.

Therefore we will restrict our consideration to uniaxial strain states. In this case the strain energy functions W i and W i (respectively the strain energy in the medium with open cracks and with closed cracks) and the sets of admissible local deformations are given, in terms of the infinitesimal strain e, by @+ := {e/n. en 2 e+} , @-:= {e/n. en 5 -e-}, Wh(e) = E + ( n . en)', WR(e) = $ E-(n. en)', where: the positive constants e+, which we can call strain thresholds, play the rhle, in the case of linear elasticity, of the phase defining thresholds;

the constants E* are positive and verify the relationship E-> Ef , (4.2) which is simply physically interpreted recalling that once the cracks are open the stiffness of the material is lower than in the case of closed cracks.

In the model discussed in [START_REF] Wozniak | Laminated media with interface defects[END_REF] one can assume that the traction Y required to open (close) all micro-cracks is

given by Y = E+e+ = E-e-.

In the sequel we will study the propagation of a disturbance of displacement in the direction of n. In other words we will study the propagation of a longitudinal plane wave of displacements, opening (or closing) the micro-cracks, in which the phase change occurs inside a thick layer whose micro-structure verifies the hypotheses listed in the previous section. i) U is the component of macro-displacement along n, U,, its derivative in the direction of n, ii) we introduce only one micro-shape function and one vectorial macro-descriptor, iii) Q is the component of the macro-descriptor vector along n, iv) the interface layer is the union of planes orthogonal to n, v) S is the normal stress n . SRn.

(3.7) is recalled

We will use the following denotation and hypotheses:

The average strain energy for the considered continuum and displacement fields is easily evaluated once equation Therefore we obtain, using (3.9), the following expression for the normal stress S in terms of Q and Utn: so that S can be expressed in terms of Ufn and c? as follows:

E

  such that &+(-6) = E -( 6 ) = 0 ; w3 E [-6,6], &+(6) = &-(-d) = E . Obviously we have that t+(e3) + &-(03) = E Also we define on [-6, 61 the functions & + ( 0 3 ) ; p-(e3) :=-. & -( 0 3 ) p+(e3) := -F We partition the interval [-6, 61 into the n disjoined intervals, of constant length E , Ii := (83 -F C ( @ ) , 03 + &+(@)). We can now define the function h" : [-6, 61 + lR as the real-valued continuous function which i) in every subinterval (03 -~-( 0 ; ) , 83) (83,(33 + ~' ( 8 : ) ) of Ii (i = 1,. . . , n) is linear with angular coefficients respectively -p+('83) and p-("83) (for some '83 and "83 in Ii) 3 + (33 &-(oil& ( i ) ii) when O3 = 0; it attains the values

  B; :=pt(B;l(t)), @ ~( t ) : = { ~ E BR/YX(VP(X,t)) E ( b -, y + ) ) > @:=pt(PR(t)). The physical interpretation of the function yx and the constants ( y -, y+) is very easy: in the + phase micro-cracks are open, in the -phase micro-cracks are closed, and in order to open or to close micro-cracks the stress needs a component along n which respectively corresponds to the thresholds y+ and y-. In points X in which

  with y := (T+G-and whereE := E'G' + E-r-; S = E U f n + v[E] Q , [El := E--E+ ; E := E'u-+ E-u'.

  while the propagation condition (3.10) becomes EQ + [El U,, -QRczQ = 0 . Equation (4.7) allows to express Q in terms of Urn and cz (4.7)

  Referring to[START_REF] Dell'isola | Deduction of thermodynamic balance laws for bidimensional nonmaterial directed continua mod-7 WOZNIAK, Cz.: Refined macro-dynamics of periodic structures[END_REF] for more details, for seek of self containment, we recall that this means that if the surface Zt has parametric

representation r"(8, t), 8 = (@, 8') = Zi' there exists a surface scalar field dt, such that

vx E &(t) g! (8, o')/x = r"(8, t) + 03n(8, t) ; (2.3)

where n represents the normal vector field to Zt and O3 E [-dt(8), dt

[START_REF] Rubinstein | On mathematical models for solid-liquid zones in a two-phase monocomponent system and in binary alloys[END_REF]

]. The set obtained fixing in (2.3) 8' and letting 8 vary we will call 03-shifted surface from &.

We will call interphase longitudinal modulus the quantity (4.10) which depends on the coordinate O3 inside the interfacial layer because in it the fields (see equation (4.5)) o* appear. dition implies the following restrictions on the propagation speed c, (recall condition 4.2):

The interphase longitudinal modulus must be positive everywhere inside the interphase layer. This physical con-eR$ < E+ or eRc: > E-.

The field U has to be found solving the hyperbolic equation which is implied by (3.8), (4.11) (4.12)

where the expression (4.9) for S has to be substituted.

To (4.11) some boundary conditions must be added, together with some free-moving boundary conditions determining the position of & and the scalar &. In particular we must assume that the following conditions must hold on the surfaces 2: and .

X; , which in the considered case are planar, together with -Zt :

where ((t) represents the distance of Zlt from a reference plane.

Moreover the displacements and normal stresses will be assumed to be continuous on 2: and 2;. Concerning condition (4.10) we remark that i) interphase longitudinal modulus reduces to the effective modulus found in [START_REF] Wozniak | Laminated media with interface defects[END_REF] when c, is vanishing; ii) when the speed c, tends to infinity the interphase longitudinal modulus tends to E;

iii) when llcnll tends to Jyor to /$ respectively from lower or from higher values then respectively on 2; and on Z : the interphase loigitudinal modulus vanishes.

The free moving boundary problem (4.12)-(4.14) seems to be interesting enough to deserve an accurate mathematical analysis. In particular it will be interesting to determine the set of initial conditions for which condition (4.11) is verified for all subsequent time instant and to examine under which condition the interphase layer initially present disappears in a finite time, or when it does not disappear, eventually growing indefinitely.

Conclusions

In this paper we prove that for the family of interphase layer whose structure is described by the hypotheses listed in sect. 3, i) the material behaviour of the medium filling the interphase layer depends not only on the material properties of both phases but also on the propagation speed of the layer, ii) if one assumes that the interphase longitudinal modulus has to be always positive not every propagation speed of the interphase layer is possible, iii) when the interphase layer does not propagate in the referential description then the material properties of the substantial particles belonging to it are similar to the effective properties of a micro-laminated two component medium Moreover we particularize the general model introduced in sect. 3 to study the one dimensional propagation in We find a free moving boundary problem for the boundaries delineating the interphase layer and the field of (Cf. [ 141 -[IS]). the direction of the layering of an interphase layer in the microcracked solid studied in 141. longitudinal displacements which seems to deserve mathematical interest.


Marco Aldinucci

Françoise André

Jérémy Buisson

Sonia Campa

Massimo Coppola

Marco Danelutto

Corrado Zoccolo

Parallel program/component adaptivity management

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Grid computing platforms require to handle dynamic behaviour of computing resources within complex parallel applications. We introduce a formalization of adaptive behaviour that separates the abstract model of the application from the implementation design. We exemplify the abstract adaptation schema on two applications, and we show how two quite different approaches to adaptivity, the ASSIST environment and the AFPAC framework, easily map to this common schema.

An Abstract Schema for Adaptation

With the advent of more and more complex and dynamic distributed architectures, such as Computational Grids, growing attention has to be paid to the effects of dynamicity on running programs. Even assuming a perfect initial mapping of an application over the computing resources, choices made can be impaired by many factors: load of the used machines and network available bandwidth may vary, nodes can disappear due to network problems, user requirements may change.

To properly handle all these situations, as well as the implicitly dynamic behaviour of several algorithms, adaptivity management code has to be built into the parallel/distributed application. In so doing, a tradeoff must be settled between the complexity of adding dynamicityhandling code to the application and the gain in efficiency we obtain.

The need to handle adaptivity has been already addressed in several projects (AppLeS [START_REF] Berman | Application-level scheduling on distributed heterogeneous networks[END_REF], GrADS [START_REF] Vadhiyar | Self adaptability in grid computing[END_REF], PCL [START_REF] Ensink | Program control language: a programming language for adaptive distributed applications[END_REF], ProActive [START_REF] Baude | On hierarchical, parallel and distributed components for Grid programming[END_REF]). These works focus on several aspects of reconfiguration, e.g. adaptation techniques (GrADS, PCL, ProActive), strategies to decide reconfigurations (GrADS), and how to modify the application configuration to optimize the running application (AppLes, GrADS, PCL). In these projects concrete problems posed by adaptivity have been faced, but little investigation has been done on common abstractions and methodology [START_REF] Mcilhagga | Towards a design methodology for adaptive applications[END_REF]. In this work we discuss, at a very high level of abstraction, a general model of the activities we need to perform to handle adaptivity in parallel and distributed programs.

Our model is abstract with respect to the implemented adaptation techniques, monitoring infrastructure and reconfiguration strategy; in this way we can uncover the common aspects that have to be addressed when developing a programming framework for reconfigurable applications, and we show that it can be applied to two concrete examples: ASSIST [START_REF] Aldinucci | Dynamic reconfiguration of grid-aware applications in ASSIST[END_REF] and AFPAC [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF].

The abstract model of dynamicity management we propose is shown in Fig. 1, where highlevel actions rely on lower-level actions and mechanisms. The model is based on the separation of application-oriented abstractions and implementation mechanisms, and is also deliberately specified in minimal way, in order not to introduce details that may constrain possible implementations. As an example, the schema does not impose a strict time ordering among its leaves. In order to validate the proposed abstraction, we exemplify its application in two distinct, significant case studies: message-passing SPMD programs, and component-based, high-level parallel programs. In both cases, adaptive behaviour is derived by specializing the abstract model introduced here. We get significant results on the performance side, thus showing that the model maps to worthwhile and effective implementations [START_REF] Aldinucci | Dynamic reconfiguration of grid-aware applications in ASSIST[END_REF].

The work is structured as follows. Sec. 2 introduces the abstract model. The various phases required by the general schema are detailed with examples in Sec. 3.1 and Sec. 3.2 with respect to two example applications. Sec. 4 explains how the schema is mapped in the AFPAC framework, where self-adapting code is obtained by semi automated restructuring of existing code. Sec. 5 describes how the same schema is employed in the ASSIST programming environment, exploiting explicit program structure to automatically generate autonomic dynamicity-handling code.

Adaptivity

The process of adapting the behaviour of a parallel/distributed application to the dynamic features of the target architecture is built of two distinct phases: a decision phase, and a commit phase, as outlined in Fig. 1. The outcome of the decide phase is an abstract adaptation strategy that the commit phase has to implement. We separate the decisions on the strategy to be used to adapt the application behaviour from the way this strategy is actually performed. The decide phase thus represents an abstraction related to the application structure and behaviour, while commit phase concerns the abstraction of the run-time support needed to adapt. Both phases are split into different items. The decide phase is composed of:

• trigger -It is essentially an interface towards the external world, assessing the need to perform corrective actions. Triggering events can result from various monitoring activities of the platform, from the user requesting a dynamic change at run-time, or from the application itself reacting to some kind of algorithm-related load unbalance. • policy -It is the part of the decision process where it is chosen how to deal with the triggering event. The aim of the adaptation policy is to find out what behavioural changes are needed, if any, based on the knowledge of the application structure and of its issues. Policies can also differ in the objectives they pursue, e.g. increasing performance, accuracy, fault tolerance, and thus in the triggering events they choose to react to. Basic examples of policy are "increase parallelism degree if the application is too slow", or "reduce parallelism to save resources". Choosing when to re-balance the load of different parts of the application by redistributing data is a more significant and less obvious policy. In order to provide the decide phase with a policy, we must identify in the code a pattern of parallel computation, and evaluate possible strategies to improve/adapt the pattern features to the current target architecture. This will result either in specifying a user-defined policy or picking one from a library of policies for common computation patterns. Ideally, the adaptation policy should depend on the chosen pattern and not on its implementation details.

In the commit phase, the decision previously taken is implemented. In order to do that, some assessed plan of execution has to be adopted.

• plan -It states how the decision can be actually implemented, i.e. what list of steps has to be performed to come to the new configuration of the running application, and according to which control flow (total or partial order). • execute -Once the detailed plan has been devised, the execute phase takes it in charge relying on two kinds of functionalities of the support code the different mechanisms provided by the underlying target architecture, and a timing functionality to activate the elementary steps in the plan, taking into account their control flow and the needed synchronizations among processes/threads in the application. The actual adapting action depends on both the way the application has been implemented (e.g. message passing or shared memory) and the mechanisms provided by the target architecture to interact with the running application (e.g. adding and removing processes to the application, moving data between processing nodes and so on).

The general schema does not constrain the adaptation handling code to a specific form. It can either consist in library calls, or be template-generated, it can result from instrumenting the application or as a side effect of using explicit code structures/library primitives in writing the application. The approaches clearly differ in the degree of user intervention required to achieve dynamicity.

Examples of the abstract decomposition

In order to better explain the abstract adaptation model, we instantiate the model in two different applications, and discuss the meaning that actions and phases in the model assume.

Task farming

We exemplify the abstract adaptation schema on a task-parallel computation organized around a centralized task scheduler, continuously dispatching works to be performed to the set of available processing elements. For this kind of pattern, both a performance model and a balancing policy are well known, and several different implementation are feasible (e.g. multithreaded on SMP machines, or processes in a cluster and/or on the Grid). At steady state, maximum efficiency is achieved when the overall service time of the set of processing elements is slightly less than the service time of the dispatcher element.

Triggers are activated, for instance, when (1) the average interarrival time of task incoming is much lower/higher than the service time of the system, (2) on explicit user request to satisfy a new performance contract/level of performance, (3) when built-in monitoring reports increased load on some of the processing elements, even before service time increases too much.

Assuming we care first for computation performance and then resource utilization, the adaptation policy would be like that in Fig. 2. Applying this policy, the decide phase will eventually determine the increase/decrease of a certain magnitude in the allocated computing power, independently of the kind of computing resources.

This decision is passed to the commit phase, where we must produce a detailed plan to implement it (finding/choosing resources, devising a mapping of application processes where appropriate).

Assuming we want to increase the parallelism degree, we will often come up with a simple plan like that in Fig. 3. The given plan is the most usual one, but some steps can be skipped depending on the implementation. For example, a multithreaded program executing on a SMP architecture does not require the code to be installed (step 2). The order may also be different, e.g. swapping steps 3 and 4. Actions listed in the plan exploit mechanisms provided by the implementation, for instance to either fork new threads, or stage and run new processes or even ask for a larger processing time share (on a multiprogrammed system with QoS control at the system level). The list of steps in the plan is also customized w.r.t. application implementation.

As an example, whenever computing resources are homogeneous, step 1 is quite simple, while it will require a specific effort to select the best execution plan on heterogeneous resources.

Once the detailed plan has been devised, it has to be executed and its actions have to be orchestrated, choosing proper timing in order that they do not to interfere with each other and with the ongoing computation.

Abstract timing depends on the implementation of the mechanisms, and on the precedence relationship that may be given in the plan. In the given example, steps 1 and 2 can be executed in sequence, but without internal constraint on timing. Step 3 requires a form of synchronization with the scheduler to update its data, or to suspend all the computing elements, depending on actual implementation of the scheduler/worker synchronization. For the same reason, execution of step 4 also may/may not require a restart/update of the monitoring subsystem to take into account the new resources.

Fast fourier transform

The fast fourier transform can be implemented as a parallel SPMD code which distributes the matrix by lines. It alternates local computation and global matrix transposition steps. A performance model is known that predicts the optimal number of processors for such an application, depending on their power and the cost of communications. The code can thus be made adaptive, by spawning processes when new processors become available. Similarly, when some allocated processors are reclaimed by the operating system, concerned processes have to be safely terminated first. Thanks to the abstract model for dynamic adaptation, such a behavior can be easily designed.

The policy is composed of the following two statements: when the trigger notifies of available processors, and if the optimal number of processors is not overflowed, then the application decides to start new processes; when the trigger notifies that some used processors are reclaimed, some of the processes will be stopped. Given this decision, the commit phase produces a plan. The plans for the two kinds of adaptation are given on Fig. 4 and5.

This example shows that the implementation mechanisms may depend on several aspects of the application. For example, redistributing a matrix is strongly dependent on the application and its implementation. On the other hand, preparation of the environment may require for example starting daemons (when using LAM-MPI communications), but it is not strictly related to the application code.

1. prepare the environment for the newly recruited processors (start daemons, stage-in files, etc.) 2. spawn processes to be executed by the new processors 3. fix connections between processes such that the new ones can communicate with the others 4. redistribute the matrix in order to balance the load amongst the whole set of processes 1. redistribute the matrix in such a way that the terminating processes do not hold any part of the matrix anymore 2. fix connections between processes in order to exclude the processes that are terminating 3. effectively terminate the concerned processes 4. clean everything that has been previously installed specifically for the application The mechanisms also impose various constraints on the timing phase of the abstract model, depending on their implementation. This is the case for action 2 of the plan for spawning processes which creates the processes. For an MPI application this action can be implemented either the standard way, with the MPI_Comm_spawn, or in an ad-hoc way if the developer requires finer control over process creation. The former approach requires synchronization of already running processes, whereas the latter may not.

AFPAC: A generic framework for developers to manage adaptation

The AFPAC framework [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF] focuses at present on adaptability of parallel components. Its approach consists in defining the modifications that should be applied to an existing component in order to make it able to adapt itself. Its concrete architecture (Fig. 6) can be seen as a specialization of the abstract model of Fig. 1 as follows. Indeed, policy, planner and actions entities implement respectively the policy, plan and mechanisms phases of the abstract model; the timing phase of the abstract model is split over both the executor for handling the control flow and the coordinator for the synchronization with the application. AFPAC does not make appear explicitly the trigger phase as it is considered as an interface, whereas the service entity, modelling the application, has no counter-part in the abstract model. As shown in Fig. 6, the decider glues the policy to the external probes in the same way that the decide phase aggregates the trigger and policy phases in the abstract model. The same kind of matching applies between the executor entity and the execute phase. In the case of a parallel component, the service is implemented by a parallel algorithm. At runtime, it contains several execution threads distributed over a collection of processes.

The AFPAC framework does not impose any constraint on communications between threads.

At the current state, the AFPAC framework includes two coordinators. The first one executes sequential actions and does not impose any synchronization constraint with the service. It is somewhat an empty coordinator. The other coordinator aims at executing parallel actions in the context of the execution threads of the service. To do so, it requires to suspend the execution threads at a state from which such actions are allowed to be executed. Such a state is called an adaptation point. In the case of parallel codes, adaptation points must be related in order to build a global state that satisfies some consistency model. For example, in the case of SPMD codes, such a consistency model may state that all threads should execute the action from the same adaptation point. This problem has been further discussed in [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF]; an algorithm has been proposed in [START_REF] Buisson | Enforcing consistency during the adaptation of a parallel component[END_REF] for implementing such a coordinator that looks for adaptation points in the future of the execution of the service. It is especially suitable for SPMD codes such as the ones using MPI (e.g. the fast fourier transform example given in Sec.3.2).

The AFPAC framework gives full control over dynamic adaptation to the developer. Consequently, the developer is responsible for designing and implementing the policy, plan template and action entities. In the same way, he/she has to place manually adaptation points within the source code of the service as additional statements. Nevertheless, extra preparation of the component (such as generation of annotations required by the coordinator) is done automatically thanks to aspect-oriented programming. Thanks to this semi-automated modification and to the separation of concerns, AFPAC can be used to make adaptable existing legacy codes at a low development cost.

ASSIST: Managing dynamicity using language and compilation approaches

ASSIST applications are described by means of a coordination language, which can express arbitrary graphs of (possibly) parallel modules, interconnected by typed streams of data. A parallel module (parmod ) coordinates a set of concurrent activities which are performed by Virtual Processes (VPs). VPs execute a set of sequential activities on their input data and internal state, activities which are selected on item arrival from the input streams. The sequential functions can be programmed using standard sequential languages (C, C++, Fortran).

Overall, a parmod may behave in a data-parallel (e.g. SPMD/for-all/apply-to-all) or taskparallel way (e.g. farm, pipeline), and it can nondeterministically accept from one or more input streams a number of input items, which may be decomposed in parts and used as function parameters to activate VPs. A parmod may also exploit a distributed shared state, which survives between VP activations related to different stream items. More details on the ASSIST environment can be found in [START_REF] Vanneschi | The programming model of ASSIST, an environment for parallel and distributed portable applications[END_REF][START_REF] Aldinucci | ASSIST as a research framework for high-performance Grid programming environments[END_REF].

An ASSIST module (or a graph of modules) can be declared as a component, which is characterized by provide and use ports (both one-way and RPC-like), and by Non-Functional ports. Among the non-functional interfaces there are those related to QoS control. At any moment during an ASSIST application run, components can be assigned a new QoS contract, e.g. specifying a performance requirement. In order to fulfill the contracts, the component framework continuously adapts component configurations, in terms of parallelism degree, and process mapping [START_REF] Aldinucci | Dynamic reconfiguration of grid-aware applications in ASSIST[END_REF]. The adaptation mechanism relies on automatic user code instrumentation, and on a hierarchy of Application Managers [START_REF] Aldinucci | Components for high performance Grid programming in Grid[END_REF].

Each component has a Component Adaptation Manager (CAM) entity coordinating its adaptation. An Application Manager (AM), possibly distributed, enforces QoS of the application in the whole, by coordinating and leveraging on CAMs. As sketched in Fig. 7, ASSIST implements the abstract adaptation schema by organizing its leaves, left to right (compare with Fig. 1) in an autonomic control loop. CAM managed entities are processes within a component, while the AM applies the abstract model to application components. In the following we describe the CAM case.

The trigger functionality has to (1) collect a stream of monitoring data from the running program, as a feedback to the autonomic behaviour of AMs, and (2) to react to QoS contract changes when they trigger the need for adaptation.

The policy phase in Fig. 7 evaluates a component performance model over the monitoring data, to find out the amount/allocation of resources that can match the assigned QoS contract. In the case the QoS contract is broken, the decide phase will set a target for the commit phase, e.g. the additional amount of required computing power. The ASSIST compiler synthesizes the performance model from static information on the parallel pattern exploited by the component. Application programmers can also override standard performance models with custom ones.

The plan phase in Fig. 7 reconveys component performance within its contractually specified values by exploiting the set of actions available as mechanisms. Plan templates are instantiated as partially ordered sets of actions, which are performed according to the schedule provided by timing. ASSIST implements two layers of adaptation mechanisms: parallelism degree management (add or remove resource to/from computation), and computation (VP) remapping, with associated data migration and global state consolidation.

The timing functionality, not shown in Fig. 7, involves a distributed agreement among a set of VPs on the point where the reconfiguration must happen. In ASSIST the migration process can be performed in so-called reconf-safe points [START_REF] Aldinucci | Dynamic reconfiguration of grid-aware applications in ASSIST[END_REF], i.e. points in the application code where the distributed computation and state are known to be consistent, and can be efficiently synchronized. Placement and use of reconf-safe points are automated, so that different mechanisms available to the execute phase (reconfiguration commands in Fig. 7) automatically get the appropriate kind of synchronization.

The execute functionality thus exploits support code built within the VPs, and coordinates it with services provided by the component framework to interface to Grid middleware (e.g. for resource recruiting).

Observe that all the code needed to perform the timing and execute phases is automatically generated by the ASSIST compiler, that instruments the application code in a fully transparent manner for the application developer. ASSIST reconf-safe points are designed to exploit synchronization points already needed to ensure the correctness of the parallel application code. Moreover, the ASSIST high-level structured nature enables the compiler to automatically select the optimal implementation of mechanisms for each application and reconf-safe point. For instance, no state migration code is inserted for stateless computations, and depending on the parallelism pattern (e.g. stream versus data parallel), VPs involved in the synchronisation can be a subset of those within the component being reconfigured.

In this way ASSIST adaptive components run with no overhead with respect to non-adaptive versions of the same code, when no configuration change is performed [START_REF] Aldinucci | Dynamic reconfiguration of grid-aware applications in ASSIST[END_REF].

Conclusions

We have described a general model to provide adaptive behaviour in Grid-oriented componentbased applications. The general schema we have shown is independent of implementation choices, such as the responsibility for inserting the adaptatation code (either left to the programmer, as it happens in the AFPAC framework, or performed by exploiting knowledge of the high level program structure, as it happens in the ASSIST context). The model also encompasses user-driven as well as autonomic adaptation.

The abstract model helps in separating application and run-time programming concerns of adaptation, exposing adaptive behaviour as an aspect of application programming, formalizing the concerns to be addressed, and encouraging an abstract view of the run-time mechanisms for dynamic reconfiguration.

This formalization gives the basis for defining a methodology. The given case studies provide with valuable clues about how to solve different concerns, and how to identify common parts of the adaptation that can be generalized in support frameworks. The model can be thus also usefully applied within other programming frameworks, like GrADS, which do not enforce a strong separation of adaptivity issues into design and implementation.

We expect that such a methodology will lead to more portable and understandable adaptive applications and components, and it will also promote layered software architectures for adaptation, simplifying implementation of both the programming framework and the applications.

  Parallel program/component adaptivity management M. Aldinucci a , F. André b , J. Buisson b , S. Campa c , M. Coppola a , M. Danelutto c , C. Zoccolo c a Inst. of Information Science and Technologies (ISTI -CNR), V. Moruzzi 1, 56124 Pisa, Italy b University of Rennes I, Avenue du General Leclerc, 35042 Rennes, France c Dept. of Computer Science, University of Pisa, Largo B. Pontecorvo 3, 56127 Pisa, Italy

Figure 1 :

 1 Figure 1: Abstract schema of an adaptation manager.

Figure 3 .

 3 Figure 3. Plan for increasing resources.

Figure 4 .

 4 Figure 4. Plan for spawning processes.

Figure 5 .

 5 Figure 5. Plan for removing processes.

Figure 6 :

 6 Figure 6: AFPAC Framework.

Figure 7 :

 7 Figure 7: ASSIST framework.

  • when steady state is reached, no configuration change is needed • if the set of processing elements is slower than the dispatcher, new processing elements should be added to support the computation and reach the steady state • if the processing elements are much faster than the dispatcher, reduce their number to increase efficiency Figure2. A simple farm adaptive policy 1. find a set of available processing elements {P i } 2. install code to be executed at the chosen {P i } (i.e. application code, code that interacts with the task scheduler and for dinamicity handling) 3. register with the scheduler all the {P i } for task dispatching 4. inform the monitoring system that new processing element have joined the execution

Acknowledgments. This research work is carried out under the FP6 Network of Excellence CoreGRID funded by the European Commission (Contract IST-2002-004265), and it was partially supported by the Italian MIUR FIRB project Grid.it (n. RBNE01KNFP) on Highperformance Grid platforms and tools.