Dinil Sebastien Soudan

Mon Divakaran

Eitan Altman

Pascale Vicat-Blanc

Primet

Equilibrium in size-based scheduling systems

Keywords:

Size-based scheduling is advocated to improve response times of small flows. While researchers continue to explore different ways of giving preferential treatment to small flows without causing starvation to other flows, little focus has been paid to the study of stability of systems that deploy size-based scheduling mechanisms. The question on stability arises from the fact that, users of such a system can exploit the scheduling mechanism to their advantage and split large flows into multiple small flows. Consequently, a large flow in the disguise of small flows, may get the advantage aimed for small flows. As the number of misbehaving users can grow to a large number, an operator would like to learn about the system stability before deploying size-based scheduling mechanism, to ensure that it won't lead to an unstable system. In this paper, we analyse the criteria for the existence of equilibria and reveal the constraints that must be satisfied for the stability of equilibrium points. Our study exposes that, in a two-player game, where the operator strives for a stable system, and users of large flows behave to improve delay, size-based scheduling doesn't achieve the goal of improving response time of small flows.

Résumé

L'ordonancement basé sur la taille est préconisé pour améliorer le temp de réponse des petits flux. Alors que les chercheurs continuent d'explorer differentes manières de donner de la préference au petits flux sans causer de famine aux autres flux, peu d'interet a été consacré à l'étude de la stabilité des systémes utilisant ces mécanismes d'ordonancement. La question de la stabilité apparait lorsque l'on concidère que les utilisateurs d'un tel système peuvent exploiter de tels mécanismes afin d'en tirer un meilleur profit en divisant leurs grands flux en plusieurs petits. De ce fait, un grand flux déguisé en petits flux profite des avantages accordés à ces derniers. Comme le nombre d'utilisateur détournant le mécanisme peut devenir conséquent, un opérateur est en droit de se questionner sur la stabilité du système avant de le déployer. Ce afin de garantir la stabilité. Dans ce papier, nous analysons les critères d'existences des equilibres et montrons les contraintes qui doit être satisfaites pour que ces équilibres soient stables. Notre étude montres que dans le jeux entre l'opérateur qui veut deployer un système stable et l'utilisateur qui agit de maniére égoïste afin de minimiser son délai, les mécanismes d'ordonancement basés sur la taille échouent dans leur but premier de minimiser les délais des petits flux.

Mots-clés: equilibre, size-based scheduling

Introduction

Scheduling based on flow size (or flow age) has been gaining importance in the recent times. Researchers have proposed different ways of scheduling based on size, ranging from SRPT (Shortest Remaining Processing Time) to LAS (Least Attained Service) to MLPS (Multi-level Processor Sharing) scheduling mechanisms [START_REF] Kleinrock | Queueing Systems[END_REF][START_REF] Avrachenkov | Differentiation Between Short and Long TCP Flows: Predictability of the Response Time[END_REF][START_REF] Sun | DRR-SFF: A Practical Scheduling Algorithm to Improve the Performance of Short Flows[END_REF]. These scheduling strategies differ from the general model for flow scheduling in the Internet. The queues in the Internet nodes, though are served in an FCFS order at packet level, can be modeled using an M/G/1-PS (processor sharing) queue at flow level. The motivation to deviate from this norm, and schedule flows based on size, is to give better completion time to small flows. Strictly speaking, the aim has been to improve the conditional mean response time of small flows, at negligible cost to large flows. LAS, for example, always gives highest priority to the flow that has attained the least service. More details on size-based scheduling policies and the advantages they bring, can be found in [START_REF] Nuyens | The foreground-background queue: A survey[END_REF] and [START_REF] Avrachenkov | Differentiation Between Short and Long TCP Flows: Predictability of the Response Time[END_REF]. Note that, researchers use age-based scheduling to refer to the scheduling schemes that are blind, in the sense that, they do not have information about the size of the flow when it arrives, and hence uses its age (the number of bytes/packets already scheduled) to make scheduling decision. Whereas, in this paper, we use the broader phrase size-based scheduling to include all the policies that use age or size to make scheduling decisions.

A user (an end-user or an application) sends a file as a single flow across the Internet. We take this as a normal behaviour. If size-based scheduling is deployed by an operator, there is a clear motivation for one or more users to deviate from the normal behaviour. Indeed, there is an incentive in splitting a flow (possibly large, but more precisely, one that is not small) into multiple small flows to exploit the advantage (say, priority in scheduling) given to small flows to improve the response time. If a considerable number of users deviate from the normal behaviour, then the operator's aim of giving shorter response time to small flows might well be deceived. More importantly, an operator would like to know if such user manipulations would lead to an unstable system behaviour. This poses an important problem in the context of size-based scheduling systems which, to the best of our knowledge, has not been addressed yet. This is the problem we address in this work. In the scenario where users do not misbehave, the stability issue (for network of queues) has been addressed in [START_REF] Brown | Stability of networks with age-based scheduling[END_REF] recently.

The focus of this work is to study the equilibria in size-based scheduling system where users misbehave. We believe this would lead to better understanding of the implication of deploying a sizebased scheduling mechanism. More description of the problem is given in Section 2. The model is elaborated in Section 3. The existence of equilibria are studied for two kinds of system behaviours: one in which the service rates are fixed, is studied in Section 4; and the other in which the service rates are varying, is studied in Sections 5 and 6. We summarize our analysis as a game between the operator and users, in Section 7.

Problem statement and assumptions

We study the problem that arises when an operator deploys a size-based scheduling mechanism. Though there are different ways of scheduling based on size, our focus is on size-based scheduling using two queues. Here, flows are classified based on their sizes. Small flows are sent to one queue, and large flows to another 1 . Each queue is assigned a specific service rate, such that the total service rate equals the line capacity. The aim of operator in setting such a mechanism is to give to reduce the average response times of small flows.

To formulate the objective of the operator, we assume Poisson flow arrivals. Arrivals and service rates are in units of small flow. λ x and λ y are the arrival rates for small and large flows respectively. Each large is F times a small flow. The service rates at small and large queues are φ x and φ y respectively, such that if C denotes the line capacity, φ x + φ y = C. Each queue is served using the PS discipline; hence it is an M/G/1 -P S queue.

We study the existence of equilibria under the scenario where users cheat by splitting a large flow into multiple small flows to improve their delay. This is explored in two cases: (i) where the service rates assigned are static, (ii) where the operators exhibits control by dynamically changing the service rates. In the latter case, we explore the existence of interesting equilibria, and state the conditions required for stability, under the assumption that the incentive for players to migrate is to minimize the delay the flow will incur. Note that, by 'players', we consider only the users who migrate. The fluid model used in this work is inspired by the one used in [START_REF] Altman | Bandwidth allocation for guaranteed versus best effort service categories[END_REF], where the authors analyse dynamic bandwidth resource allocation and migration between guaranteed performance and best effort traffic classes.

The two-queues model is depicted in Fig. 1. The queue for small flows is called small queue and is referred to as Q x . The other queue is called the large queue which is denoted by Q y . The number of flows at Q x is represented by x. At the large queue, this number (in number of small flows) is denoted by y. We assume infinite queues. The service rates, φ x and φ y , are also in number of small flows. They are both assumed to take non-zero values.

The system parameters φ x and φ y are set by the operator. System state is modeled using averaged queue sizes: x and y. Depending on the measured delay values, a user might decide to split a large flow into multiple small flows. Therefore, a fraction of the flows arriving at the large queue might be migrated to the small queue. This migration function, which is a result of aggregate user behaviour, is represented as m(x, y). It is linear in λ y F as a result of the integration of individual user that send dλ y each: mdλ y = λ y m. We take m to be a non-negative and continuous function of x and y. m represents the fraction of λ y which goes to

Q x . 0 ≤ m(x, y) ≤ 1 (1)
For every large flow that migrates, it adds an overhead of η (e.g. connection establishment cost, slow-start cost). The rate equations can now be written as:

dx dt = λ x -φ x + λ y F m(x, y)(1 + η), x > 0 (2)
dy dt = λ y F -φ y -λ y F m(x, y), y > 0 (3)
The rate equations are different at the borders. For x = 0,

dx dt x=0 = [λ x -φ x + λ y F m(x, y)(1 + η)] + (4)
and for y = 0,

dy dt y=0 = [λ y F -φ y -λ y F m(x, y)] + . ( 5
)
4 System analysis for static service rates

This section details the analysis of a system where the service rates at both the queues are fixed.

Proposition 4.1. An interior point (x, y) is an equilibrium iff φ x -λ x = λ y F -φ y and m is such that m(x, y) = φx-λx λyF and 0 ≤ m(x, y) ≤ 1.
Proof of Prop. 4.1. Let (x, y) be an interior point. It is an equilibrium if and only if :

   dx dt = 0 dy dt = 0 0 ≤ m(x, y) ≤ 1 ⇐⇒      m(x, y) = φx-λx λyF (1+η) m(x, y) = λyF -φy λyF 0 ≤ m(x, y) ≤ 1 Remark 4.2.
Existence of interior equilibrium does not only depend on m function but also on the arrival rates and service rates. Meaning that they can only exist in very specific cases.

Proposition 4.3. (0, 0) is an equilibrium point if and only if: 4) and ( 5), we obtain that (0, 0) is an equilibrium point if and only if:

     m(0, 0) ≤ φx-λx λyF (1+η) λyF -φy λyF ≤ m(0, 0) 0 ≤ m(0, 0) ≤ 1 Proof of Prop. 4.3. Using equations (
     dx dt x=0 = 0 dy dt y=0 = 0 0 ≤ m(0, 0) ≤ 1 ⇐⇒    λx-φx 1+η + λ y F m(0, 0) ≤ 0 λ y F -φ y -λ y F m(0, 0) ≤ 0 0 ≤ m(0, 0) ≤ 1 ⇐⇒      m(0, 0) ≤ φx-λx λyF (1+η) λyF -φy λyF ≤ m(0, 0) 0 ≤ m(0, 0) ≤ 1
     m(0, y) ≤ φx-λx λyF (1+η) m(0, y) = λyF -φy λyF 0 ≤ m(0, y) ≤ 1
Proof of Prop. 4.4. Using equations ( 4) and ( 3), we obtain that (0, y) is an equilibrium point if and only if:

   dx dt x=0 = 0 dy dt = 0 0 ≤ m(0, y) ≤ 1 ⇐⇒    λx-φx 1+η + λ y F m(0, y) ≤ 0 λ y F -φ y -λ y F m(0, y) = 0 0 ≤ m(0, y) ≤ 1 ⇐⇒      m(0, y) ≤ φx-λx λyF (1+η) m(0, y) = λyF -φy λyF 0 ≤ m(0, y) ≤ 1
Proposition 4.5. (x, 0) with x > 0 is an equilibrium point if and only if:

     m(x, 0) = φx-λx λyF (1+η) λyF -φy λyF ≤ m(x, 0) 0 ≤ m(x, 0) ≤ 1
Proof of Prop. 4.5. Using equations ( 2) and ( 5), we obtain that (x, 0) is an equilibrium point if and only if:

     dx dt = 0 dy dt y=0 = 0 0 ≤ m(0, y) ≤ 1 ⇐⇒    λx-φx 1+η + λ y F m(x, 0) = 0 λ y F -φ y -λ y F m(x, 0) ≤ 0 0 ≤ m(x, 0) ≤ 1 ⇐⇒      m(x, 0) = φx-λx λyF (1+η) λyF -φy λyF ≤ m(x, 0) 0 ≤ m(x, 0) ≤ 1

Discussion

The aim of a network operator in deploying such a scheduling mechanism is to give shorter delays to small flows, at negligible cost to large flows. With this in mind, we can now evaluate which among the equilibrium points are interesting and useful (from the perspective of a network operator).

To start with, let us consider the equilibrium point (0, 0). The inequalities of Prop. 4.3 give the shaded region of Fig. 2, where one m can exist to make (0, 0) an equilibrium. This region is dominated by the line λ x + λ y F = C, which defines the region where a single queue system would have empty queue equilibrium. Thus, this equilibrium (in the two queue system) is not of great interest for the network operator. The lines (x, 0) and (0, y) constitute the remaining border point equilibria. (x, 0) is the set of those points where there is queueing in the small queue, but not at the large queue. For this reason, these are not desirable equilibria from operator's point of view. Similarly existence of (0, y) means, there is nothing queueing at Q x . So, there is incentive for users to migrate to Q x . Hence (0, y) will not be stable.

As seen in previous section, interior point equilibrium are only possible in limiting cases where the surplus rate at the large queue is exactly equal to the surplus of service of x, with the additional constraint that m transfers exactly this. This situation is too constrained to happen in a real scenario. To introduce more flexibility, the operator can control the service rate. But this requires the use of some observable parameters of the system. In this system, the only observable parameters are x and y as arrival rates λ x and λ y are not separable at the queues.

Control on φ x using parameter x

In this section we study the system when operator controls the service rates using a single parameter. Let f be the control function, and x be the control parameter. In the remaining of this section we use the following definition for φ x (x) and φ y (x). Definition 5.1. φ x (x) and φ y (x)

φ x (x) = f (x) φ y (x) = C -f (x)
C being the maximum link capacity (or service rate), let:

0 < f (x) < C (6)
so that the service rate at any queue doesn't vanish.

Delay condition

We introduce the delay condition which is satisfied at equilibrium, as the users have no incentive to migrate once the delays at both queues are equal. Let us look the delay a large flow will incur Q x , if it is split into F small flows. For a service rate of φ x at Q x , each small flow gets φx x+F of service. Hence the time to transfer a large flow through Q x is T x = x+F F φx (1 + η). On the other hand, if the arriving large flow decides to queue at Q y , the delay experienced will be T y = y+1 φy . At equilibrium, T x = T y ; thus,

(x + F )(1 + η) F φ x = y + 1 φ y (7)

Analysis of equilibrium

For equilibrium to exist, the equations ( 2) and ( 3) should be equated to zero.

Proposition 5.2. If η is zero, no equilibrium will exist unless C = λ x + λ y F .

Proof of Prop. 5.2. From the combination (2) + (3) at equilibrium, when η is 0, we get C = λ x + λ y F .

In the remaining, η is taken to be strictly positive.

Using equations ( 2) and (3) at equilibrium, gives the constraints (8) on f for the existence of such an equilibrium point.

f (x e ) = (1 + η)(C -λ y F ) -λ x η (8)
There can be multiple such points x e or no depending on f . Proposition 5.3. For a given set of parameters (λ x , λ y , C, η, f, m) with η > 0, the system has inner equilibrium points (x e , y e ) where:

x e ∈ f -1 ( (1 + η)(C -λ y F ) -λ x η ) (9)
and:

y e = C -f (x e ) F f (x e ) (x e + F )(1 + η) -1 iff:          λ x + λ y F ≤ C λ x + λ y F (1 + η) > C f -1 ( (1+η)(C-λyF )-λx η ) = ∅ m(x e , y e ) = C-(λx+λyF ) ηλyF (10)
Proof of Prop. 5.3. From the combination, (2) + (1 + η)(3), at equilibrium, we obtain Eq. ( 8). The system has equilibriums iff there is point x e satisfying this equation, meaning f -1 (

(1+η)(C-λyF )-λx η
) is not empty (η = 0). From Eq. ( 7), we get corresponding y e . Then from Eq. (2) at equilibrium, we have m as defined in Eq. (10).

Due to constraint (1) on m, and constraint (6) on f , we have the existence of this equilibrium iff:

λ x + λ y F ≤ C C < λ x + λ y F (1 + η) (11)
Second inequality is strict because of Eq. ( 6).

Fig. 3 shows the region of arrival rates where equilibrium can exist, dashed-line is excluded from this.

Corollary 5.4. If f is strictly monotonic. For every 2-tuple of (λ x , λ y ) satisfying the line equation:

(1 + η)(C -λ y F ) -λ x = k (for a constant k),
there is maximum of one equilibrium point.

Proof. Corollary 5.4 If f is strictly monotonic, there is utmost one pre-image by f -1 . As potential equilibria are determined by Eq. (9) (and y e which only depends on x e ), all points of the line of arrival rates:

(1 + η)(Cλ y F )λ x = k have the same potential equilibrium. Since m(x e , y e ) has to satisfy Eq. ( 10), which gives a different line in λ x and λ y , there is at most one equilibrium point (the intersection). From the above, it can be observed that, for a monotonic f , there exists utmost one equilibrium point for the whole line of arrival rates. This gives only a few equilibrium points for a wide range of arrival rates. A non-monotonic f will give more equilibrium points. But still, it is not feasible to obtain equilibrium points for all values of (λ x , λ y ) satisfying the line of arrival rates, as it would require an infinite queue or an infinite variability of f . Hence, we conclude that control using a function of x alone, is not of any use to the operator.

λ x λ y F C C C (1+η)
6 Control on φ x using parameters x and y

As seen in previous section, using only one parameter is not enough to stabilize the system as the control space is too small. We thus use a control function with two parameters: x and y. Definition 6.1. φ x (x, y) and φ y (x, y) φ x (x, y) = g(x, y) φ y (x, y) = Cg(x, y)

Similar to what have been done with f , if C is the maximum link capacity (or service rate), let:

0 < g(x, y) < C (12)
Note that, definition of delay equation at equilibrium as given in [START_REF] Sastry | Nonlinear Systems. Analysis, Stability and Control[END_REF] remains the same and so we directly proceed to the analysis of potential equilibria.

Analysis of equilibrium

For equilibrium to exist, the equations ( 2) and ( 3) should be equated to zero. Prop. 5.2 still holds in this case as φ x φ y also sum to C; therefore from equations ( 2) and ( 3) we can prove the same. Hence η is also taken strictly positive here.

Similarly to what have been done for Prop.5.3, at equilibrium, using Eq. ( 2) and ( 3), we obtain the following constraint on g:

g(x e , y e ) = (1 + η)(C -λ y F ) -λ x η (13)
Proposition 6.2. For a given set of parameters (λ x , λ y , C, η, g, m) with η > 0, the system has inner equilibrium points (x e , y e ) iff:

               g(x e , y e ) = (1+η)(C-λyF )-λx η m(x e , y e ) = C-(λx+λyF ) ηλyF (x+F )(1+η) F φx = y+1 φy λ x + λ y F ≤ C λ x + λ y F (1 + η) > C (14)
Proof of Prop. 6.2. Same as Prop. 5.3 except that (8) has been replaced by (13).

Note that the region of arrival rates where equilibrium points can exist is the same.

We define an equivalent load Γ:

Definition 6.3. Γ(λ x , λ y ) = λx 1+η + λ y F . Definition 6.4. D(Γ) is the set of (x, y) satisfying: y = a(Γ)x + b(Γ) ( 15
)
where

a(Γ) = (1 + η)Γ -C F (C -Γ) and b(Γ) = (2 + η)Γ -2C C -Γ Proposition 6.5.
For a given setting of arrival rates (λ x , λ y ) satisfying

Γ(λ x , λ y ) = k (16)
and the two inequalities of Prop. 6.2, equilibria (x e , y e ) under this load are on D(k). Besides, for all the equilibrium points in D(k), g satisfies (13) and is constant:

g(x e , y e ) = 1 + η η (C -Γ) (17)
Proof of Prop. 6.5. Let (λ x , λ y ) be a setting of arrival rates satisfying Eq. ( 16) and the two inequalities of Prop. 6.2. We first show that D(k) contains all the potential equilibrium points. By replacing g using Eq. ( 13) in the delay equation [START_REF] Sastry | Nonlinear Systems. Analysis, Stability and Control[END_REF], we obtain Eq. ( 15).

All equilibrium points of arrival settings satisfying ( 16) have the same value of g as Eq. ( 13) holds and gives Eq. ( 17) which is constant in Γ(λ x , λ y ).

Fig. 4 shows Γ-lines in the λ x λ y -plane and their corresponding D(Γ)-lines in the xy-plane. On each such line in the xy-plane, g is constant and thus gradient is orthogonal. From Eq. ( 17), we also know ∂g ∂Γ is negative which justifies the orientation of gradient on the figure. Proposition 6.6. For any (λ x , λ y ) verifying the two inequalities of Prop. 6.2, D(Γ(λ x , λ y )) for does not intersect in first quadrant.

Proof of Prop. 6.6. For Γ(λ x , λ y ) = Γ satisfying the two inequalities of Prop. 6.2, satisfy:

(1+η)Γ > C and C ≥ λ x + λ y F > Γ.
Under this, da dΓ and db dΓ are strictly positive and a is strictly positive. Thus, D(Γ(λ x , λ y )) do not intersect in the first quadrant. This basically means g is 'feasible'. As a corollary of Prop. 6.6, we give: Corollary 6.7. g can exist in the sense that there are no incompatible constraints resulting from Prop. 6.2.

Proof of Corollary 6.7. Prop. 6.5 gives the value g must have on D(Γ) in order to have equilibria on it and according to Prop. 6.6 these lines do not intersect in the first quadrant where g can be defined. It proves there is no incompatibility in the definition of g. Proposition 6.8. lim

Γ→C - a(Γ) = +∞ ; lim Γ→ C 1+η + a(Γ) = 0 lim Γ→C - b(Γ) = +∞ ; lim Γ→ C 1+η + b(Γ) = -1
Proof of Prop. 6.8. Trivial.

In particular, this last proposition implies that g can be defined in the whole first quadrant using Eq. ( 13) and lines D(Γ).

As of now, we demonstrated that it is feasible to define g so that point of D(Γ) can be equilibria for (λ x , λ y ) on Γ line. Next, we study the stability of the potential equilibria in order to define the additional constraints on m. The only constraint on m coming from existence of equilibrium (Prop. 6.2) is that m(x e , y e ) =

C-(λx+λyF ) ηλyF

. The point where this will hold is not specified and depends on m. Defining m will thus define a mapping of arrival rates (λ x , λ y ) to the actual equilibrium point.

Stability of the equilibria and definition of m

As demonstrated in the previous section, g that doesn't prevent existence of equilibrium is feasible.

We now like to have the constraints that m has to satisfy. We already know from the previous section the range m must cover, but we don't know where they have to be located in xy-plane. In order to get more constraints on m, we study the conditions for stable equilibriums. To do so we rely on Hartman Grobman theorem and the study of the stability of the linearized system. Proposition 6.9. For an equilibrium point (x e , y e ) as defined by Prop. Inequalities of the proposition are obtained using combination of equations ( 21) and ( 22). Proposition 6.2 and 6.9 give sufficient conditions on m to define stable equilibria. Next, we prove that there exists m which stabilizes the system for any arrival setting. Proposition 6.10. There exists an m satisfying the constraints of propositions 6.2 and 6.9 which stabilizes the system for any arrival rates in the shaded region of the Fig. 4. Proof of Prop. 6.10. We prove this by exhibiting one such m. Let m be such that

m(x, y) = e -xy
The m satisfies the constraints of Eq. ( 18) for any λ y in (0, C) as ∂m ∂x = -ye -xy and ∂m ∂y = -xe -xy , are both strictly negative on the interior. Besides, as m ranges from 1 to 0, from the borders (y = 0 and x = 0) to infinity, thus by continuity, there exists an equilibrium point (x e , y e ) where m(x e , y e ) = C-(λx+λyF ) ηλyF for any arrival rates as all D(Γ)-lines enter the first quadrant by one its borders.

Note that if m is strictly monotonic, there is only one equilibrium point for any arrival rate setting in the equilibrium existence region (refer Fig. 3) located at the intersection of the level set of g and m. In addition, it is not possible to apply this for all setting of arrival rates in order to get equilibria for all of them, unless queue are infinite. Proposition 6.11. If queues are finite, some setting of arrival rates can't have equilibrium.

Proof of Prop. 6.11. As a(Γ) tends to 0 when Γ tends to C/1 + η + , and b(Γ) tends to -1, intersection of y = 0 and D(Γ) tends to infinity. Hence, for any x max , it is possible to find Γ close enough to C/1 + η so that equilibrium which have to be on D(Γ) (due to Prop. 6.5) would have to be after x max .

Using limits of a(Γ) and b(Γ) when Γ tends to C, it is possible to pursue the same reasoning and prove that for some settings of arrival rates, there can't be equilibrium under finite queue for large flows.

Thus we see that, the system can attain stability depending on the decision of users, and the control function used by operator.

Game

We summarize our results in the form of a game with two players: operator and user (with a large flow to send). Here, we make the fair assumption that T x < T y . The operator can take one of the two actions:

• AFP: Assume fair play, and not use a g.

• AUP: Assume unfair play, and use a g.

From the users, we consider a collective behaviour.

• UC: Users cheat,

• UR: Users rightful Under AUP, T x = T y . We use preferential ordering of payoffs for both players. That is (a o , a u ) ≺ p (a ′ o , a ′ u ), if player p prefers second strategy over the first. The letter o is used to refer to operator, and u to refer to users.

• (AFP, UR) ≺ u (AFP, UC): Users prefer to cheat when the operator does nothing to stop them from cheating, as this would give them shorter response time in the small queue (when T x < T y ).

• (AUP, UR) ≺ u (AUP, UC): Users also prefer to cheat when the operators are aware and are setting service rates dynamically to achieve stability, as this would ensure a finite queue; hence a finite delay. Observe that, if the don't cheat (and stay in Q y ), there is no equilibrium (from Prop. 6.2); hence the queue will build up without bound.

Therefore, it can be drawn that UC strictly dominates UR under any action of the operator (AFP or AUP). Hence, the action UR can be eliminated [START_REF] Osborne | A Course in Game Theory[END_REF]. So, what lefts to be analysed is the preference of operator under this user action (UR). We see, (AFP, UC) ≺ o (AUP, UC), as there is no equilibrium for general arrival rates (from Prop. 6.2, and if T x remains less than T y , migration will create additional load due to η) leading to overflow.

From the above analysis, (AUP, UC) is a Nash equilibrium in the two-players game. That is, assuming operators and users are rational, users will tend to cheat, and operators will look to stabilize the system to maintain finite queues (when the system is operating near to saturation, depending on η).

Note that if the operator's setting of service rates is such that T x > T y , then migrating to small queue is no more an incentive for large flows. This doesn't preclude operator from favoring small flows as x φx < y φy can still hold. In such a scenario, it can be seen that (AFP, UR) will be a Nash equilibrium. This situation can happen if η is large enough and φy φx can be maintained such that: Second constraint will not be satisfied if operator want to favor small flows too much, say, as in the priority based scheduling proposed in [START_REF] Avrachenkov | Differentiation Between Short and Long TCP Flows: Predictability of the Response Time[END_REF]; meaning that it will be of interest for users to cheat.

Conclusions

Starting from the setting of static service rates, and moving to dynamic service rate settings, we analysed the existence of equilibria. For the existence of equilibria that is of interest to the operator, it is necessary to have control over the service rate as a function of the queue lengths. Even then, not all the stable equilibrium points are of interest to the operator, as they give the same delay to small and large flows. Therefore, if a large number of users cheat, the operator has no visible incentive in deploying a size-based scheduling system.

The focus of our study revolved around saturation (of the line capacity) as we assumed that there is some cost η incurred due to migration. In the future, we plan to analyse the system in overload. Similarly, it would be interesting to understand what happens if the operator deploys a mechanism to detect and shift some of the disguised large flows from the small queue to the large queue.

Figure 1 :

 1 Figure 1: Two-queues model.

Proposition 4 . 4 .

 44 (0, y) with y > 0 is an equilibrium point if and only if:

Figure 2 :

 2 Figure 2: Existence region of equilibrium (0, 0) under static service rate.

Figure 3 :

 3 Figure 3: Interior equilibrium existence region under φ x (x) = f (x).

Figure 4 :

 4 Figure 4: Interior equilibrium existence region and mapping of Γ(λ x , λ y ) lines to D(Γ), level sets and gradient field of g(x, y).

  To analyse of the equilibrium point (x e , y e ), we take the Jacobian J of the rate equations (2) and (3) at this point. The partial derivatives ∂g ∂x and ∂g ∂y at (x e , y e ) are obtained from the delay equation, Eq. (7).The equilibrium point (x e , y e ) is asymptotically stable if the eigenvalues of the J at (x e , y e ) have strictly negative real parts[START_REF] Sastry | Nonlinear Systems. Analysis, Stability and Control[END_REF] Ch. 2 & 5]. Characteristic polynomial of J is:From this and equations (19) and (20), real parts of the roots are strictly negative iff:

		(1 + η)	∂m ∂x	-	∂m ∂y		<	(1 + η)C(1 + x e + y e + F ) λ y (F (2 + y e + η) + x e (1 + η)) 2	(21)
	and					∂m ∂x	+	y e + 1 x e + F	∂m ∂y	< 0	(22)
									6.2 if the following equations
	hold:	    	∂m ∂x	+	y e + 1 x e + F	∂m ∂x ∂y ∂m	(1+ye)C λy(F (2+η+ye)+xe(1+η)) 2 < 0 <	(18)
	then (x e , y e ) is asymptotically stable.
	Proof of Prop. 6.9. ∂g ∂x	(x e , y e ) =	(1 + η)(y e + 1)F C (F y e + x e (1 + η) + F (2 + η)) 2	(19)
			∂g ∂y	(x e , y e ) = -	(1 + η)(x e + F )F C (F y e + x e (1 + η) + F (2 + η)) 2	(20)
									λ 2 +
			(λ y F ( ∂m ∂y -(1 + η) ∂m ∂x ) + ∂g ∂x -∂g ∂y ) λ + η(λ y F ( ∂m ∂x ∂g ∂y -∂m ∂y ∂g ∂x ))

A flow is called small if its size is less than a threshold, θ. In practice, θ bytes of every large flow also go to the small queue. But, we ignore this to keep the model simple. Besides, this affects neither the analysis nor the results given here.

Acknowledgement

This work was done in the framework of the INRIA and Alcatel-Lucent Bell Labs Joint Research Lab on Self Organized Networks.


Patrick Le Meur

On maximal diagonalizable Lie subalgebras of the first Hochschild cohomology

Let A be a basic connected finite dimensional algebra over an algebraically closed field, with ordinary quiver without oriented cycles. Given a presentation of A by quiver and admissible relations, Assem and de la Peña have constructed an embedding of the space of additive characters of the fundamental group of the presentation into the first Hochschild cohomology group of A. We compare the embeddings given by the different presentations of A. In some situations, we characterise the images of these embeddings in terms of (maximal) diagonalizable subalgebras of the first Hochschild cohomology group (endowed with its Lie algebra structure).

Introduction

Let A be a finite dimensional algebra over an algebraically closed field k. The representation theory of A deals with the study of (right) A-modules. So we assume that A is basic and connected and it admits presentations A ≃ kQ/I by its (unique) ordinary quiver Q and an ideal I of admissible relations. In the eighties, Martinez-Villa and de la Peña introduced the fundamental group π1(Q, I) of (Q, I) ( [START_REF] Martínez-Villa | The universal cover of a quiver with relations[END_REF]). Like in topology, this group is defined using an equivalence relation ∼I (called the homotopy relation) on the set of unoriented paths in Q. This group is part of the so-called covering techniques initiated in [START_REF] Bongartz | Covering spaces in representation theory[END_REF][START_REF] Ch | Algebren, Darstellungsköcher Ueberlagerungen und zurück[END_REF]. In particular, it has led to the definition of simple connectedness and strong simple connectedness for an algebra ( [START_REF] Assem | On some classes of simply connected algebras[END_REF][START_REF] Skowroński | Simply connected algebras and Hochschild cohomologies[END_REF]). Also, it has proved to be a very useful tool in representation theory. For example, it is proved in [START_REF] Skowroński | Selfinjective algebras of polynomial growth[END_REF] that any domestic self-injective algebra admitting a Galois covering by a strongly simply connected locally bounded k-category is of quasitilted type. Note that in general, different presentations A ≃ kQ/I and A ≃ kQ/J may lead to non-isomorphic groups π1(Q, I) and π1(Q, J).

The fundamental group π1(Q, I) behaves much like the fundamental group of a topological space. For example, given a presentation ν : kQ ։ A (with kernel I), Assem and de la Peña have defined an injective group homomorphism θν : Hom(π1(Q, I), k + ) ֒→ HH 1 (A). Here HH 1 (A) is the first Hochschild cohomology group Ext 1 A op ⊗A (A, A) ( [START_REF] Hochschild | On the cohomology groups of an associative algebra[END_REF]). This result is to be compared with the classical isomorphism Hom(π1(X), Z) ∼ -→ H 1 (X; Z) relating the singular cohomology to the fundamental group of a path connected topological space X. It is known from [START_REF] Gerstenhaber | The cohomology structure of an associative ring[END_REF] that HH 1 (A) has a structure of Lie algebra, isomorphic to the Lie algebra of derivations of A (with the commutator as Lie bracket) factored out by the ideal of inner derivations. With this presentation of HH 1 (A), the derivations that lie in the image of θν, have been characterized in terms of diagonalizable derivations ( [START_REF] Farkas | Diagonalizable derivations of finite dimensional algebras[END_REF], see also [START_REF] De La Peña | On the first Hochschild cohomology group of an algebra[END_REF]).

The aim of this text is to characterise maximal diagonalisable Lie subalgebras of HH 1 (A) using the subspaces Im(θν) associated to the different presentations ν of A. Recall that, given a Lie algebra, the maximal diagonalizable (for the adjoint representation) subalgebras are related to Cartan subalgebras.

On the one hand, one can define a diagonalizability for elements in HH 1 (A) using the above notion of diagonalizable derivations. Also one can define the diagonalizability of a subset of HH 1 (A) (as the simultaneous diagonalizability of its elements). It appears that Im(θν) is diagonalizable, and that any diagonalizable subset of HH 1 (A) is contained in Im(θν ) for some presentation ν : kQ ։ A.

On the other hand, given two presentations ν : kQ ։ A and µ : kQ ։ A with kernel I and J respectively, it is not easy to compare the groups π1(Q, I) and π1(Q, J) (and therefore θν and θµ). In some cases, this is possible, however. For example, assume that (α, u) is a bypass in Q (that is, α is an arrow and u is an oriented path which is parallel to α and distinct from α), that τ ∈ k, and that J = ϕα,u,τ (I). Here ϕα,u,τ : kQ ∼ -→ kQ is the automorphism, called a transvection, which maps α to α + τ u, and which fixes any other arrow ( [START_REF] Meur | The fundamental group of a triangular algebra without double bypasses[END_REF]). In such a situation, if α ∼I u (or α ∼J u), then there is a natural surjective group homomorphism π1(Q, J) ։ π1(Q, I) (or π1(Q, I) ։ π1(Q, J), respectively); if α ∼I u and α ∼J u then π1(Q, I) equals π1(Q, J) and the natural homomorphisms are the identity maps; and if α ∼I u and α ∼J u, then I = J and π1(Q, I) = π1(Q, J). In each of these cases, we shall see that there is a simple relation between θν and θµ.

In order to formulate our main result, we use the quiver Γ of the homotopy relations of the presentations of A ( [START_REF] Meur | The fundamental group of a triangular algebra without double bypasses[END_REF]). Its set of vertices is the set of the homotopy relations ∼ Ker(ν) associated to all the presentations ν : kQ ։ A. Also, there is an arrow ∼I →∼J if there exists a transvection ϕα,u,τ such that J = ϕα,u,τ (I) and such that the natural surjective group homomorphism is a non isomorphism π1(Q, I) ։ π1(Q, J). The quiver Γ has been introduced in order to find conditions under which an algebra admits a universal Galois covering. This existence is related to the existence of a unique source (that is, a vertex which is the target of no arrow). Actually, under one of the two following conditions, Γ does have a unique source [START_REF] Meur | The universal cover of an algebra without double bypass[END_REF]Prop. 2.11] and [START_REF] Meur | The universal cover of a monomial algebra without multiple arrows[END_REF]Cor. 4.4]):

(H1) Q has no double bypass and k has characteristic zero (a double bypass is a 4-tuple (α, u, β, v) where (α, u) and (β, v) are bypasses such that the arrow β appears in the path u).

(H2) A is monomial (that is, A ≃ kQ/I0 with I0 an ideal generated by a set of paths) and Q has no multiple arrows.

Using these results, we prove the main theorem of the text.

Theorem 1. Assume that at least one the two hypotheses (H1) or (H2) is satisfied. Then:

(i) The maximal diagonalizable subalgebras of HH 1 (A) are exactly the subalgebras of the form Im(θν ) where ν : kQ ։ A is a presentation such that ∼ Ker(ν) is the unique source of Γ.

(ii) If G, G ′ are two such subalgebras of HH 1 (A), then there exists an algebra automorphism ψ :

A ∼ -→ A inducing a Lie algebra automorphism ψ * : HH 1 (A) ∼ -→ HH 1 (A) such that G ′ = ψ * (G).
Note that the Lie algebra HH 1 (A) has already been studied (see [START_REF] Guil-Asensio | The group of outer automorphisms and the Picard group of an algebra[END_REF][START_REF] Strametz | The Lie algebra structure on the first Hochschild cohomology group of a monomial algebra[END_REF], for instance). The text is organised as follows. In Section 1 we recall all the definitions we will need and prove some useful lemmas. In Section 2, we introduce the notion of diagonalizability in HH 1 (A). In particular, we will prove that a subset of HH 1 (A) is diagonalizable is and only if it is contained in Im(θν) for some presentation ν : kQ ։ A. In Section 3 we compare the Lie algebra homomorphisms θν for different presentations ν of A, using the quiver Γ. Finally, in Section 4 we prove Theorem 1.

This text is part of the author's thesis ( [START_REF] Meur | Revêtements galoisiens et groupe fondamental des algèbres de dimension finie[END_REF]) made at Universitï¿ 1 2 Montpellier II under the supervision of Claude Cibils.

Preliminaries

Terminology and notations for quivers

Let Q be a quiver. We write Q0 and Q1 for the set of vertices and of arrows, respectively. We read (oriented) paths from the right to the left, that is, we view a path u as a morphism and the concatenation vu of two paths u and v such that the source of v equals the target of u as a composition of morphisms. Given x ∈ Q0, the trivial path (of length 0, with source and target equal to x) is denoted by ex. Two paths are called parallel if they have the same source and the same target. An oriented cycle in Q is a non trivial path whose source and target are equal. If α ∈ Q1 we consider its formal inverse α -1 with source and target equal to the target and the source of α, respectively. Hence, we get the double quiver

Q such that Q 0 = Q0 and Q 1 = Q1 ∪ {α -1 | α ∈ Q1}. Then, a walk in Q is exactly an oriented path in Q. Given a walk γ = α εn n . . . α ε 1 1 (with αi ∈ Q1, εi ∈ {±1}), its inverse γ -1 is by definition α -ε 1 1 . . . α -εn n .

Presentations by quiver and admissible relations

Let Q be a quiver. Its path algebra kQ is the k-algebra whose basis as a k-vector space is the set of paths in Q (including the trivial paths), and whose product is bilinearly induced by the concatenation of paths (if u, v are two paths such that the source of v is different from the target of u, then we set vu = 0). The unit of kQ is

P x∈Q 0 ex and kQ is finite dimensional if and only if Q is finite (that is
Q0 and Q1 are finite) and has no oriented cycles. We let kQ + be the ideal of kQ generated by the arrows.

An admissible ideal of kQ is an ideal I such that (kQ + ) N ⊆ I ⊆ (kQ + ) 2 for some N 2. In such a case, the elements of I are called relations and, following [START_REF] Martínez-Villa | The universal cover of a quiver with relations[END_REF], a minimal relation of I is a relation s P i=1 tiui = 0 such that t1, . . . , ts ∈ k * and u1, . . . , us are pairwise distinct paths in Q, and such that there is no non empty proper subset S ⊂ {1, . . . , s} satisfying P i∈S tiui ∈ I. In such a case, u1, . . . , us are necessarily parallel. Note that I is generated by its minimal relations. Recall (see [START_REF] Auslander | Representation theory of artin algebras[END_REF]) that any finite dimensional k-algebra A is Morita equivalent to a basic one. If A is basic, then there exists a unique quiver Q, the ordinary quiver of A, and a surjective k-algebra homomorphism ν : kQ ։ A whose kernel is an admissible ideal of kQ. Also, {ν(ex) | x ∈ Q0} is a complete set of primitive orthogonal idempotents of A. The homomorphism ν is called a presentation (by quiver and admissible relations). We have A ≃ kQ/Ker(ν) and A is connected if and only if Q is connected.

Presentation of HH 1 (A)

Let A be a basic finite dimensional k-algebra and let {e1, . . . , en} be a complete set of primitive orthogonal idempotents. A unitary derivation ( [START_REF] De La Peña | On the first Hochschild cohomology group of an algebra[END_REF]) is a k-linear map d : A → A such that d(ab) = ad(b) + d(a)b for any a, b ∈ A and such that d(ei) = 0 for every i. Let Der0(A) be set of unitary derivations. It is a Lie algebra for the commutator. In the sequel, all derivations will be unitary. So we shall call them derivations. Let E :=

{ n P i=1 tiei | t1, . . . , tn ∈ k}. Then E is a semi-simple subalgebra of A and A = E ⊕ r where r is the radical of A. Let Int0(A) := {δe : A → A, a ∈ A → ea -ae | e ∈ E},
this is an ideal of Der0(A). Throughout this text, we shall use the following presentation proved in [START_REF] De La Peña | On the first Hochschild cohomology group of an algebra[END_REF]:

Theorem 1. ([7]) HH 1 (A) ≃ Der0(A)/Int0(A) as Lie algebras.
In the following lemma, we collect some useful properties on derivations.

Lemma 1.1. Let d ∈ Der0(A), then d(ejAei) ⊆ ejAei. Assume that the ordinary quiver Q of A has no oriented cycles, then d(r) ⊆ r and d(r 2 ) ⊆ r 2 .
Proof: Since d is unitary and since Q has no oriented cycles, we have

d(r) ⊆ r. So, d(r 2 ) ⊆ r 2 . If ψ : A ∼ -→ A is a k-algebra automorphism such that ψ(ei) = ei for every i, then the map d → ψ • d • ψ -1 induces a Lie algebra automorphism of HH 1 (A), denoted by ψ * : HH 1 (A) ∼ -→ HH 1 (A).

Fundamental groups of presentations

Let (Q, I) be a bound quiver (that is, Q is a finite quiver and I is an admissible ideal of kQ). The homotopy relation ∼I was defined in [START_REF] Martínez-Villa | The universal cover of a quiver with relations[END_REF] as the equivalence class on the set of walks in Q generated by the following properties:

(1) αα -1 ∼I ey and α -1 α ∼I ex for any arrow α with source x and target y,

(2) wvu ∼I wv ′ u if w, v, v ′ , u are walks such that the concatenations wvu and wv ′ u are well defined and such that v ∼I v ′ ,

(3) u ∼I v if u and v are paths in a same minimal relation (with a non zero scalar).

Note that if r1, . . . , rt are minimal relations generating the ideal I, then the condition (3) above may be replaced by the following one ( [START_REF] Bardzell | H 1 and representation of finite dimensional algebras[END_REF]):

(3 ′ ) u ∼I v if u and v are paths in Q appearing in ri (with a non zero scalar) for some i ∈ {1, . . . , t}.

The ∼I -equivalence class of a walk γ is be denoted by [γ]I . Let x0 ∈ Q0, following [START_REF] Martínez-Villa | The universal cover of a quiver with relations[END_REF], the set of ∼Iequivalence classes of walks with source and target x0 is denoted by π1(Q, I, x0). The concatenation of walks endows this set with a group structure whose unit is [ex 0 ]I . This group is called the fundamental group of (Q, I) at x0. If Q is connected, then the isomorphism class of π1(Q, I, x0) does not depend on the choice x0. In such a case, we write π1(Q, I) for π1(Q, I, x0). If A is a basic connected finite dimensional k-algebra and if ν : kQ ։ A is a presentation, the group π1(Q, Ker(ν)) is called the fundamental group of the presentation ν. The following example shows that two presentations of A may have non isomorphic fundamental groups. Proof: We use a non multiplicative version of Grï¿ 1 2 bner bases ( [START_REF] Adams | An introduction to Gröbner bases[END_REF], see also [START_REF] Farkas | Synergy in the theories of Gröebner bases and path algebras[END_REF]). Fix an arbitrary total order u1 < . . . < uN on the set of paths in Q and let (u * 1 , . . . , u * N ) be the basis of Hom k (kQ, k) dual to (u1, . . . , uN ). Following [15, Sect. 1], the Grï¿ 1 2 bner basis of I is the unique basis (r1, . . . , rt) defined by the three following properties:

(i) rj ∈ ui j + Span(ui ; i < ij) for some ij , for every j, (ii) u * i j (r j ′ ) = 0 unless j = j ′ , (iii) i1 < . . . < it.

It follows from these properties that:

(iv) r = t P j=1 u * i j (r)rj for any r ∈ I.

Recall from [15, Sect. 1] that r1, . . . , rt are minimal relations of I so that ≡I is generated by the property (3 ′ ) defining ∼I . So we only need to prove that that d(rj) ∈ k.rj for any j. We proceed by induction on j ∈ {1, . . . , t}. By assumption on d and thanks to (i), we have d(r1) ∈ I ∩ Span(ui ; i i1). Hence, (iii) and (iv) imply that d(r1) ∈ k.r1. Let j ∈ {1, . . . , d -1} and assume that d(r1) ∈ k.r1, . . . , d(rj) ∈ k.rj . By assumption on d and thanks to (i) and (ii), we have d(rj+1) ∈ I ∩ Span(ui ; i ij+1) and u * i l (d(rj+1)) = 0 if l j. So, (iii) and (iv) imply that d(rj+1) ∈ k.rj+1. This finishes the induction and proves the lemma.

Comparison of fundamental groups

Let A be a basic connected finite dimensional k-algebra with ordinary quiver Q without oriented cycles. We defined the transvections in the introduction. A dilatation ( [START_REF] Meur | The fundamental group of a triangular algebra without double bypasses[END_REF]) is an automorphism D : kQ ∼ -→ kQ such that D(ei) = ei for any i and such that D(α) ∈ k.α for any α ∈ Q1. The following proposition will be useful in the sequel, it was proved in [START_REF] Meur | The universal cover of an algebra without double bypass[END_REF]: [START_REF] Meur | The universal cover of an algebra without double bypass[END_REF]Prop. 2.5]) Let I be an admissible ideal of kQ, let ϕ be an automorphism of kQ and let J = ϕ(I). If ϕ is a dilatation, then ∼I and ∼J coincide. Assume that ϕ = ϕα,u,τ :

Proposition 1.4. ([
-If α ∼I u and α ∼J u then ∼I and ∼J coincide.

-If α ∼I u and α ∼J u then ∼J is generated by ∼I and α ∼J u.

-If α ∼I u and α ∼J u then I = J and ∼I and ∼J coincide.

In particular, if α ∼J u, then the identity map on the set of walks in Q induces a surjective group homomorphism π1(Q, I) ։ π1(Q, J).

Here generated means: generated as an equivalence relation on the set of walks in Q, and satisfying the conditions (1) and (2) in the definition of the homotopy relation. If I, J are admissible ideals such that there exists ϕα,u,τ satisfying J = ϕα,u,τ (I), α ∼I u and α ∼J u, then we say that ∼J is a direct successor of ∼I . Proposition 1.4 allows one to define a quiver Γ associated to A as follows ([13, Def. 4.1]):

-Γ0 = {∼I | I is an admissible ideal of kQ such that A ≃ kQ/I}, -there is an arrow ∼→∼ ′ if ∼J is a direct successor of ∼I .

Example 1.5. Let A be as in Example 1.2, then J = ϕ α,cb,1 (I) and Γ is equal to ∼I →∼J .

The quiver Γ is finite, connected and has not oriented cycles ([13, Rem. 3, Prop. 4.2]). Moreover, if Γ has a unique source ∼I 0 (that is, a vertex with no arrow ending at it) then the fundamental group of any admissible presentation of A is a quotient of π1(Q, I0). It was proved in [START_REF] Meur | The universal cover of an algebra without double bypass[END_REF] and [START_REF] Meur | The universal cover of a monomial algebra without multiple arrows[END_REF] that Γ has a unique source under one of the hypotheses (H1) or (H2) presented in the introduction. Moreover, the hypotheses (H1) and (H2) both ensure the following proposition which will be particularly useful to prove Theorem 1.

Proposition 1.6. ( [START_REF] Meur | The universal cover of an algebra without double bypass[END_REF]Lem. 4.3] and [START_REF] Meur | The universal cover of a monomial algebra without multiple arrows[END_REF]Prop. 4.3]) Assume that at least one of the two hypotheses (H1) or (H2) is satisfied. Let ∼I 0 , ∼I ∈ Γ, where ∼I 0 is the unique source of Γ. Then there exist a dilatation D and a sequence of transvections ϕα 1 ,u 1 ,τ 1 , . . . , ϕα l ,u l ,τ l such that:

-I = Dϕα l ,u l ,τ l . . . ϕα 1 ,u 1 ,τ 1 (I0).
-If we set Ii := ϕα i ,u i ,τ i . . . ϕα 1 ,u 1 ,τ 1 (I0), then αi ∼I i ui for every i.

If ∼I =∼I 0 , then ∼I 0 , ∼I 1 , . . . , ∼I l , ∼I coincide.

Comparison of the fundamental groups and the Hochschild cohomology

Let A be a basic connected finite dimensional k-algebra . Assume that the ordinary quiver Q of A has no oriented cycles. Let x0 ∈ Q0 and fix a maximal tree T of Q, that is, a subquiver of Q such that T0 = Q0 and such that the underlying graph of T is a tree. With these data, Assem and de la Peña have defined an injective homomorphism of abelian groups θν : Hom(π1(Q, Ker(ν)), k + ) ֒→ HH 1 (A) associated to any admissible presentation ν : kQ ։ A ( [START_REF] Assem | The fundamental groups of a triangular algebra[END_REF]). We recall the definition of θν and refer the reader to [START_REF] Assem | The fundamental groups of a triangular algebra[END_REF] for more details. For any x ∈ Q0 there exists a unique walk γx in T with source x0, with target x and of minimal length for these properties. Let ν : kQ ։ A be an admissible presentation and let f ∈ Hom(π1(Q, Ker(ν)), k + ) be a group homomorphism. Then, f defines a derivation e f : A → A as follows: e f (ν(u)) = f ([γ -1 y uγx]∼ Ker(ν) ) ν(u) for any path u with source x and target y. The following proposition was proved in [START_REF] Assem | The fundamental groups of a triangular algebra[END_REF]: Proposition 1.7. ( [START_REF] Assem | The fundamental groups of a triangular algebra[END_REF]) The map f → e f induces an injective map of abelian groups:

θν : Hom(π1(Q, Ker(ν)), k + ) ֒→ HH 1 (A) .
Note that θν is not surjective in general. Indeed, if A is the path algebra of the Kronecker quiver, then Ker(ν) = 0, dim k Im(θν) = 1, and dim k HH 1 (A) = 3. Note also that despite its definition, the homomorphism θν does not depend on the choice of T . Indeed, let T ′ be another maximal tree, thus defining the walk γ ′

x of minimal length in T ′ with source x0 and target x, for every vertex x. Given a group homormorphism f : π1(Q, Ker(ν)) → k + there is a new derivation f : A → A (instead of e f ) obtained by applying the previous construction to

T ′ (instead of to T ), that is f (ν(u)) = f ([γ ′-1 y uγ ′ x ] Ker(ν) )ν(u) for every path u in Q from x to y. Now let e = P x∈Q 0 f ([γ ′-1 x γx] Ker(ν) ) ex ∈ A.
It is easily checked that fe f is the inner derivation associated to e. In particular, e f and f have equal images in HH 1 (A). So the construction of θν does not depend on the choice of the maximal tree T .

The product in k endows Hom(π1(Q, Ker(ν)), k + ) with a commutative k-algebra structure. So it is also an abelian Lie algebra for the commutator. The following lemma proves that θν preserves this structure. The proof is just a direct computation, so we omit it.

Lemma 1.8. θν : Hom(π1(Q, Ker(ν)), k + ) ֒→ HH 1 (A) is a Lie algebra homomorphism. In particular, Im(θν) is an abelian Lie subalgebra of HH 1 (A).

Throughout this text, A will be a basic connected finite dimensional k-algebra with ordinary quiver Q without oriented cycles (Q0 = {1, . . . , n}). We fix a complete set {e1, . . . , en} of primitive orthogonal idempotents of A. So A = E ⊕ r, where E = k.e1 ⊕ . . . ⊕ k.en and r is the radical of A. Without loss of generality, we assume that any presentation ν : kQ ։ A is such that ν(ei) = ei. Finally, in order to use the Lie algebra homomorphisms θν , we fix a maximal tree T in Q.

Diagonalizability in HH 1 (A)

The aim of this section is to prove some useful properties on the subspaces Im(θν) in terms of diagonalizability in HH 1 (A). Note that diagonalizability was introduced for derivations of A in [START_REF] Farkas | Diagonalizable derivations of finite dimensional algebras[END_REF]. For short, a basis of A is a basis B of the k-vector space A such that: B ⊆ S i,j ej Aei, such that {e1, . . . , en} ⊆ B, and such that B\{e1, . . . , en} ⊆ r. Note the following link between bases and presentations of A:

-If ν : kQ ։ A is a presentation of A, then there exists a basis B such that ν(α) ∈ B for any α ∈ Q1 and such that any element of B is of the form ν(u) with u a path in Q. We say that this basis B is adapted to ν.

-If B is a basis of A, then there exists a presentation ν : kQ ։ A such that ν(α) ∈ B for any α ∈ Q1. We say that the presentation ν is adapted to B.

The property of being diagonalizable (as a linear map) is stable under the sum with an inner derivation as the following lemma shows. The proof is immediate.

Lemma 2.1. Let u : A → A be a linear map, let e ∈ E and let B be a basis of A. Then u is diagonal with respect to the basis B if and only if the same holds for u + δe.

The preceding lemma justifies the following definition.

Definition 2.2. Let f ∈ HH 1 (A) and let d be a derivation representing f . Then f is called diagonalizable (and diagonal with respect to a basis B of A) if and only if d is diagonalizable (and diagonal with respect to B, respectively). The subset D ⊆ HH 1 (A) is called diagonalizable if and only if any there exists a basis B of A such that any f ∈ D is diagonal with respect to B.

The following proposition gives a criterion for a subset D ⊂ HH 1 (A) to be diagonalizable.

Proposition 2.3. Let D ⊆ HH 1 (A). Then, D is diagonalizable if and only if every element of D is diagonalizable and [f, f ′ ] = 0 for any f, f ′ ∈ D.
Proof: Clearly, if D is diagonalizable, then so is every element of D and [f, f ′ ] = 0 for every f, f ′ ∈ D. We prove the converse. For each f ∈ D, let d f be a derivation representing f . So d f is diagonal with respect to some basis and it suffices to prove that this basis may be assumed to be the same for all f ∈ D. Note that d f induces a diagonalizable linear map d f : ej rei → ejrei, for every i, j (see Lemma 1.1). Also, for every f, f ′ ∈ D, there exist scalars t

(f,f ′ ) i ∈ k, for i ∈ {1, . . . , n}, such that [d f , d f ′ ] is the inner derivation δ e (f,f ′ ) , where e (f,f ′ ) = n P i=1 t (f,f ′ ) i ei. Now, let i, j ∈ {1, . . . , n}. Then, given f, f ′ ∈ D, we have two diagonalizable maps d f , d f ′ : ejrei → ej rei whose commutator is equal to (t (f,f ′ ) j -t (f,f ′ ) i
)Ide j re i . So this commutator must be zero. This shows that there exists a basis Bi,j of ejrei for which d f : ejrei → ejrei has a diagonal matrix. So any f ∈ D is diagonal with respect to the basis B = {e1, . . . , en}∪ S i,j

Bi,j which does not depend on f . This proves that D is diagonalizable.

Our main example of diagonalizable subspace of HH 1 (A) is Im(θν):

Proposition 2.4. Let ν : kQ ։ A be a presentation. Then, Im(θν) is diagonalizable.

Proof: Let B be a basis of A adapted to ν and let I = Ker(ν). Then θν (f ) is diagonal with respect to B, for every f ∈ Hom(π1(Q, I), k + ).

In this section, we aim at proving that any diagonalizable subset of HH 1 (A) is contained in Im(θν ) for some presentation ν. It was proved in [START_REF] Farkas | Diagonalizable derivations of finite dimensional algebras[END_REF] that any diagonalizable derivation (with suitable technical conditions) defines an element of HH 1 (A) lying in Im(θν) for some ν. We will use the following similar result.

Lemma 2.5. Let f ∈ HH 1 (A) be diagonalizable. Let B be a basis with respect to which f is diagonal. Let ν : kQ ։ A be a presentation adapted to B. Then f ∈ Im(θν ).

Proof: Let I = Ker(ν) and let d : A → A be a derivation representing f . We set r := ν(r), for any r ∈ kQ. Let α ∈ Q1. By assumption on B, there exists tα ∈ k such that d(α) = tαα. Let tu := tα 1 + . . . + tα n , for any path u = αn . . . α1 (with αi ∈ Q1). So d(u) = tuu, because d is a derivation. More generally, if γ = α εn n . . . α ε 1 1 is a walk in Q (with αi ∈ Q1), let us set tγ := n P i=1 (-1) ε i tα i , with the convention that tγ = 0 if γ is trivial. We now to prove that the map γ → tγ defines a group homomorphism g : π1(Q, I) → k + , [γ]I → tγ and that f = θν(g).

First, we prove that the group homomorphism g : π1(Q, I) → k + is well defined. By definition of the scalar tγ, we have: (i) te x = 0 for any x ∈ Q0 and t γ ′ γ = t γ ′ + tγ for any walks γ, γ ′ such that the walk γ ′ γ is defined.

(ii) t α -1 α = te x and t αα -1 = te y for any arrow x α -→ y ∈ Q1.

(iii) twvu = t wv ′ u for any walks w, v, v ′ , u such that tv = t v ′ , and such that the walks wvu, wv ′ u are defined.

In order to prove that g is well defined, it only remains to prove that tu = tv whenever u, v are paths in Q appearing in the same minimal relation of I (with non zero scalars). For this purpose, let From (ii), (iii) and (iv) we deduce that we have a well defined map g : π1(Q, I) → k, [γ]I → tγ. Moreover, (i) proves that g is a group homomorphism. Now we prove that f = θν(g). For any path u with source x and target y, we have g([γ -1 y uγx]I ) = tu -tγ y + tγ x . Hence, θν(g) ∈ HH 1 (A) is represented by the derivation e g : A → A such that e g(u) = (tu -tγ y + tγ x )u for any path u with source x and target y. Let us set e := P

x∈Q 0 tγ x ex ∈ E.
Therefore, e g + δe = d. This proves that f = θν(g).

Now we can state the main result of this section. It is a direct consequence of Proposition 2.4 and of Lemma 2.5. Proposition 2.6. Let D ⊆ HH 1 (A). Then D is diagonalizable if and only if there exists a presentation ν : kQ ։ A such that D ⊆ Im(θν).

Remark that Lemma 2.5 also gives a sufficient condition for θν to be an isomorphism. Recall that A is called constricted if and only if dim eyAex = 1 for any arrow x → y (this implies that Q has no multiple arrows). In [START_REF] Bardzell | H 1 and representation of finite dimensional algebras[END_REF] it was proved that for such an algebra, two different presentations have the same fundamental group. Proposition 2.7. Assume that A is constricted. Let ν : kQ ։ A be any presentation of A. Then θν : Hom(π1(Q, I), k + ) → HH 1 (A) is an isomorphism. In particular, HH 1 (A) is an abelian Lie algebra.

Proof: Since θν is one-to-one, we only need to prove that it is onto. Let B be a basis of A adapted to ν, let f ∈ HH 1 (A) and let d : A → A be a derivation representing f . Let x α -→ y be an arrow. Then eyAex = k.ν(α) so that there exists tα ∈ k such that d(ν(α)) = tαν(α). Let u = αn . . . α1 be any path in Q (with αi ∈ Q1). Since d is a derivation, we have d(ν(u)) = (tα 1 + . . . + tα n )ν(u). As a consequence, d is diagonal with respect to B. Moreover, ν is adapted to B. So Lemma 2.5 proves that f ∈ Im(θν ). This proves that θν is an isomorphism. So HH 1 (A) is abelian.

3 Comparison of Im(θ ν ) and Im(θ µ ) for different presentations µ and ν of A If two presentations ν and µ of A are related by a transvection or a dilatation, then there is a simple relation between the associated fundamental groups (see Proposition 1.4). In this section, we compare θν and θµ. We first compare θν and θµ when µ = ν • D with D a dilatation. Recall that if J = D(I) with D a dilatation, then ∼I and ∼J coincide, so that π1(Q, I) = π1(Q, J). Therefore, d1(ν(α)) = d2(µ(α)) because D is a dilatation and because ∼I and ∼J coincide. This implies that d1 = d2 and θν (f ) = θµ(f ).

The following example shows that Proposition 3.1 does not necessarily hold true if ν and µ are two presentations of A such that ∼ Ker(ν) and ∼ Ker(µ) coincide. Example 3.2. Assume that char(k) = 2 and let A = kQ/I where Q is the quiver: It is easy to verify that d2 -d1 is not an inner derivation. Hence, θν = θµ. Now we compare θν and θµ when µ = ν • ϕα,u,τ and when the identity map on the set of walks in Q induces a surjective group homomorphism π1(Q, Ker(ν)) ։ π1(Q, Ker(µ)).

Example 1 . 2 .' a 7 7 2 c/

 122 Let A = kQ/I where Q is the quiver: 1 b ' / 3 and I =< ca >. Set x0 = 1.Then π1(Q, I) ≃ Z is generated by [b -1 a]I . On the other hand, A ≃ kQ/J where J =< ca -cb >, and π1(Q, J) is the trivial group.In the sequel we shall use the following technical lemma. Lemma 1.3. Let (Q, I) be a bound quiver where Q has no oriented cycles and let d : kQ → kQ be a linear map such that d(I) ⊆ I, and d(u) = tuu for some tu ∈ k, for any path u. Let ≡I be the equivalence relation on the set of paths in Q generated by the condition (3) defining ∼I . Then, the following implication holds for any paths u, v: u ≡I v implies tu = tv .

  d ′ : kQ → kQ be the linear map such that d ′ (u) = tuu for any path u in k. Thus, d • ν = ν • d ′ . In particular, d ′ (I) ⊆ I. So we may apply Lemma 1.3 to d ′ and deduce that: (iv) tu = tv if u, v are paths in Q lying in the support of a same minimal relation of I.

Proposition 3 . 1 .

 31 Let ν : kQ ։ A be a presentation, let D : kQ ∼ -→ kQ be a dilatation. Let µ := ν • D : kQ ։ A. Let I = Ker(µ) and J = Ker(ν), so that J = D(I). Then θµ = θν .Proof: Let f ∈ Hom(π1(Q, I), k + ). Then, θν (f ) and θµ(f ) are represented by the derivations d1 and d2 respectively, such that for any arrow x α -→ y:d1(ν(α)) = f ([γ -1 y αγx]J ) ν(α) d2(µ(α)) = f ([γ -1y αγx]I ) µ(α) .

5 andI

 5 =< da, f ecb, f ea + dcb >. Let T be the maximal tree such that T1 = {b, c, e, f }. Let ν : kQ ։ A = kQ/I be the natural projection. Let ψ := ϕ a,cb,1 ϕ d,f e,1 . Thus,I = ψ(I). Let µ := ν •ψ : kQ ։ A so that Ker(µ) = Ker(ν) = I. Observe that π1(Q, I) is the infinite cyclic group with generator [b -1 c -1 a]I . So let f : π1(Q, I) → k + be the unique group homomorphism such that f ([b -1 c -1 a]I ) = 1.Then θν(f ) is represented by the following derivation:d1 : A -→ A ν(x) -→ ν(x) if x ∈ {a, d} ν(x) -→ 0 if x ∈ {b, c, e, f } . On the other hand, θµ(f ) is represented by the derivation: d2 : A -→ A ν(a) -→ ν(a) + ν(cb) ν(d) -→ ν(d) + ν(f e) ν(x) -→ 0 if x ∈ {b, c, e, f } .

Proposition 3 . 3 .

 33 Let ν : kQ ։ A be a presentation, let ϕα,u,τ : kQ ∼ -→ kQ be a transvection and let µ := ν • ϕα,u,τ : kQ ։ A. Set I = Ker(ν) and J = Ker(µ), so that I = ϕα,u,τ (J). Suppose that α ∼J u and let p : π1(Q, I) ։ π1(Q, J) be the quotient map (seeProposition 1.4). Then, the following diagram commutes:Hom(π1(Q, J), k + ) θµ ' ' p * HH 1 (A) Hom(π1(Q, I), k + )where p * : Hom(π1(Q, J), k + ) ֒→ Hom(π1(Q, I), k + ) is the embedding induced by p. In particular, Im(θµ) ⊆ Im(θν).

Proof: Recall that p is the map [γ]I → [γ]J . Let f ∈ Hom(π1(Q, J), k + ). So p * (f ) is the composition π1(Q, I) p -→ π1(Q, J) f -→ k. We know that θµ(f ) and θν(p * (f )) are represented by the derivations d1 and d2 respectively, such that for any arrow x Let us prove that d1 and d2 coincide on ν(Q1). Let x a -→ y be an arrow. If a = α, then µ(a) = ν(a) and the above characterizations of d1 and d2 imply that d1(ν(a)) = d1(µ(a)) = d1(ν(a)). Now assume that a = α so that: ν(a) = µ(a) -τ µ(u) and [γ -1

y aγx]J = [γ -1 y uγx]J (recall that a = α ∼J u). Thus:

.

Hence, d1 and d2 are two derivations of A and they coincide on ν(Q1). So d1 = d2 and θµ(f

The following example shows that Proposition 3.3 does not necessarily hold true if ν is a presentation of A and ψ : kQ → kQ is an automorphism such that the identity map on the walks in Q induces a surjective group homomorphism π1(Q, Ker(ν)) ։ π1(Q, Ker(ν • ψ)). Example 3.4. Let A = kQ/I where char(k) = 2, where Q is the quiver of Example 3.2 and where I =< da, f ea + dcb >. Let ν : kQ ։ A be the natural projection with kernel I, let ψ := ϕ d,ef,1 ϕ a,cb,1 and let

a]J . Note also that ∼ Ker(ν) is weaker that ∼ Ker(µ) so that the identity map on the set of walks in Q induces a surjective group homomorphism p : π1(Q, Ker(ν)) ։ π1(Q, Ker(µ)). Let T be the maximal tree such that

On the one hand, θµ(f ) ∈ HH 1 (A) is represented by the derivation:

On the other hand, θν (p * (f )) ∈ HH 1 (A) is represented by the derivation:

One checks easily that d2 -d1 is not inner so that θµ(f ) = θν (p * (f )). Moreover, Im(θν) and Im(θµ) are one dimensional (because char(k) = 2, π1(Q, Ker(ν)) ≃ Z and π1(Q, Ker(µ)) ≃ Z/2Z) and d1, d2 are not inner. Hence Im(θµ) ⊆ Im(θν).

Actually, Proposition 3.3 does not work here because the automorphism ψ : (kQ, J) → (kQ, I) maps arrows to linear combination of paths which are not homotopic for ∼I . For example,

Finally, we compare θν and θµ when µ = ν • ψ with ψ : kQ ∼ -→ kQ an automorphism such that Ker(ν) = Ker(µ).

.

In particular, Im(θµ) is equal to the image of Im(θν) under the Lie algebra automorphism ψ * : HH 1 (A)

Proof: Since ψ fixes the idempotents e1, . . . , en, we know that ψ * is well defined. Let f ∈ Hom(π1(Q, I), k + ). So θν(f ) and θµ(f ) are represented by the derivations d1 and d2 respectively, such that for any arrow x α -→ y:

In order to prove that ψ * (θν(f )) = θµ(f ) it suffices to prove that ψ • d1 = d2 • ψ. Let x α -→ y be an arrow. Then:

On the other hand:

Hence, ψ • d1 and d2 • ψ are derivations of A which coincide on ν(Q1). So ψ * (θν (f )) = θµ(f ) for any f ∈ Hom(π1(Q, I, k + )).

Proof of Theorem 1

In this section, we prove Theorem 1. We begin with the following useful lemma. We keep the notations αi, ui, τi, Ii of that proposition. Let ψ := ϕ -1 Dϕα l ,u l ,τ l . . . ϕα 1 ,u 1 ,τ 1 . Thus, ψ(I0) = I0 and ν ′ := ν • ψ : kQ ։ A is a presentation with kernel I0. Thanks to Proposition 3.5 from which we keep the notations, we know that:

Let us show that Im(θµ) ⊆ Im(θ ν ′ ). By construction, we have

For simplicity, we use the following notations: µ0 := ν ′ and µi := ν ′ ϕ -1 α 1 ,u 1 ,τ 1 . . . ϕ -1 α i ,u i ,τ i for i ∈ {1, . . . , l}. Note that Ii = Ker(µi). Since αi ∼I i ui and µi = µi-1 • ϕα i ,u i ,-τ i , Proposition 3.3 implies that:

Moreover, µ = µmD -1 where D -1 is a dilatation. Hence, (1), (2) and Proposition 3.1 imply that:

Now assume that ∼I is the unique source of Γ. Then Proposition 1.6 imply that the homotopy relations ∼I 0 , ∼I 1 , . . . , ∼I l , ∼I coincide. Therefore, for any i ∈ {1, . . . , l}, we have µi-1 = µi • ϕα i ,u i ,τ i , and αi ∼I i-1 ui. So Proposition 3.3, implies that Im(θµ i-1 ) ⊆ Im(θµ i ). This proves that all the inclusions in (2) are equalities, and so is the inclusion in (3). Now we can prove Theorem 1. Proof of Theorem 1: (i) Let G be a maximal diagonalizable subalgebra of HH 1 (A). Thanks to Proposition 2.6, there exists a presentation µ : kQ ։ A such that G ⊆ Im(θµ). On the other hand, Lemma 4.1, implies that there exists a presentation ν : kQ ։ A such that ∼ Ker(ν) is the unique source of Γ and such that Im(θµ) ⊆ Im(θν ). Hence, G ⊆ Im(θν) where Im(θν) is a diagonalizable subalgebra of HH 1 (A), thanks to Proposition 2.4. The maximality of G forces G = Im(θν).

Conversely, let µ : kQ ։ A be a presentation such that ∼ Ker(µ) is the unique source of Γ. Hence, Im(θµ) is diagonalizable (thanks to Proposition 2.4) so there exists a maximal diagonalizable subalgebra G of HH 1 (A) containing Im(θµ). Thanks to the above description, we know that G = Im(θν ) where ν : kQ ։ A is a presentation such that ∼ Ker(ν) is the unique source of Γ. Moreover, Lemma 4.1 gives a k-algebra automorphism ψ : A ∼ -→ A such that Im(θµ) = ψ⋆(Im(θν)). Since ψ * is a Lie algebra automorphism of HH 1 (A), the maximality of G = Im(θν) implies that Im(θµ) is maximal.

(ii) is a consequence of (i) and of Lemma 4.1.