1

Approche Agent Mobile pour la réparation de charge dans les réseaux hétérogènes
L. SAOUDI


Résumé — Notre travail consiste à coupler l’approche agents mobiles au système de répartition de charge sur un réseau de stations de travail dynamique et hétérogène. La plate forme de répartition de charge conçue est semicentralisée : la collecte d’information est centralisée tandis que la redistribution de charge est distribuée, cette stratégie nous a permit de gagner l’autonomie de décision d’équilibrage et le temps de collecte d’information avec un réseau moins chargé. Pour assurer l’équité de répartition de charge sur une plate forme hétérogène, nous avons ajusté un algorithme d’estimation de charge, afin de trouver des charges comparables sur des plates formes hétérogènes. Notre plate forme se compose de quatre agents :  Agent de collecte d’information : responsable de collecte d’information de charge de toutes les stations du réseau.  Agent d’état: responsable du contrôle local de la charge d'une station.  Agent d’équilibrage : responsable de la redistribution de charge.  Agent de découverte : il inspecte et cherche à découvrir l’état réel du système. Un prototype de plate forme est implémentée sous la plate forme d’agents mobiles AGLET, qui va exploiter la machine virtuelle Java JikesRVM pour supporter la mobilité forte, et expérimenté par une application académique de multiplication parallèle de matrices de grand volume. Mots Clés—agent mobile, calcul distribué, Estimation de charge, répartition de charge.

peuvent se communiquer entre eux et avec des agents mobiles pour former ce qu’on appelle système multi agents. Notre travail consiste à coupler l’approche agent mobile au système de répartition de charge via une stratégie semicentralisée dans un réseau de stations de travail. Ce papier est divisé comme suit : La première section donne une vision générale sur la répartition de charge, la deuxième section décrit l’approche agent mobile pour la répartition de charge, puis nous présentons dans la troisième section notre plate forme de répartition de charge. notre mécanisme de calcul de charge comparable est présenté dans la quatrième section.la dernière section est l’étape d’expérimentation, elle présente l’environnement d’expérimentation ainsi que les résultats obtenus.

II. REPARTITION DE CHARGE A. Définition La répartition de charge consiste à répartir de façon équitable l'ensemble du travail sur les noeuds du système (stations de travail).Lorsqu’un processeur est surchargé, le système cherche à exporter ou migrer un des processus de la station surchargée vers des autres moins chargées. L’objectif est de réduire le temps d’exécution et optimiser l’exploitation des ressources. B. Stratégies de Répartition de charge Différentes taxonomies de stratégies d’équilibrage ont été proposées. Elles permettent de classer les différents algorithmes en fonction de divers aspects [8]. : Quand : Quand est ce que l’équilibreur de charge commence à travailler : avant l’exécution (indépendant de l’état actuel du système) ; ou pendant l’exécution de l’application (dépends de l’état actuel du système) ; dans ce cas on distingue deux stratégies : statique et dynamique. C’est le critère le plus important de la classification Où : ce critère appliqué sur les stratégies dynamiques, Où se trouve l’équilibreur de charge ; sur un seul poste centrale (centralisé) ou bien dupliqué sur tous les postes (distribué). On parle donc sur les stratégies centralisées ou distribuées.

I. INTRODUCTION a répartition de charge constitue un domaine de recherche en plein essor dans les systèmes distribués, elle cherche à répartir la charge des stations surchargées vers les stations moins chargées, afin de minimiser le temps d’exécution et maximiser l’utilisation des ressources de système. L’agent mobile vient comme une nouvelle approche de répartition de charge, grâce à sa facilité de migration sans prendre en considération l’hétérogénéité du réseau. L’efficacité des agents mobiles repose essentiellement sur sa légèreté, pour cette raison il est préférable de localiser des fonctionnalités complexes dans des agents stationnaires, qui

L

2

Quelle : sur quelle information se base l’équilibrage de charge: les informations de toutes les stations du réseau (stratégie locale) ou d’un groupe de station du réseau (stratégie globale). Qui : qui initier l’équilibrage c’est le poste le moins chargé ou bien le poste le plus chargé. Comment : Comment se fait l’équilibrage : d’une manière optimale c.à.d. toutes les stations ont la même charge ou sous optimale c.à.d. juste pour répartir les tâches sur les stations sous chargées. C. Modules de repartition de charge La répartition de charge soulève des questions concernant : - la représentation et la quantification de la charge. - la diffusion entre machines les informations de la charge. - le choix des machines susceptibles de participer à la redistribution de la charge. - la charge à transférer entre les machines et le moyen de transfert. Les réponses à ces questions se trouvent dans les différents modules d’équilibrage de charge[11]: Module de collecte d’information de la charge : Ce composant doit gérer, les informations locales de la charge, et l'acquisition des informations distantes. Module de transfert : Le composant de transfert permet à un nœud d'évaluer son état et de transférer des entités comme émetteur. Beaucoup de stratégies sont basées sur des seuils ou des transferts relatifs. Module de sélection : Lorsque le composant de transfert a décidé d'être émetteur, le composant de sélection doit élire une entité à transférer [4]. Module de localisation : Il a pour responsabilité de trouver un partenaire (émetteur ou receveur) pour le transfert [4]. Module de négociation Les composants précédents ne sont pas isolés, ils interagissent avec les composants des autres stations. Les échanges de messages se font à partir du composant de négociation.

le réseau, cet objectif est atteint par la localisation des fonctionnalités complexes dans des agents stationnaires, qui peuvent se communiquer entre eux et avec les agents mobiles par un simple mécanisme de passage de message. Les agents mobiles résultats sont de poids léger, d’où l’idée de coupler le système multi agents et agent mobile pour construire un système de répartition de charge basé sur l’approche agent. Les agents mobiles possèdent trois caractéristiques clés, lui permettre de supporter facilement la répartition de charge dynamique pour les applications distribuées ou parallèles: * ils peuvent se déplacer d’une plate forme à une autre. * ils peuvent se déplacer entre des plates formes hétérogènes. *ils portent le code d’application pour l ‘exécuter sur une machine distante au lieu d’exiger une préinstallation de ce code sur la machine de destination [5]. C'est bien pour ces raisons que la répartition de charge est un domaine de développement considérable pour la technologie d’agents mobiles.

IV. PLATE FORME DE REPARTITION DE CHARGE A. Vue générale du système Notre plate forme est conçue pour la répartition de charge des applications de calcul distribué basée sur le système multi agents, qui s’exécutent sur des stations hétérogènes. La stratégie de notre plate forme est semi centralisée, comme tout système d’équilibrage passe par deux étapes essentielles : Collecte d’informations de charge sur le système puis redistribution de la charge, nous proposons de centraliser la phase de collecte d’information et de distribuer la phase de répartition de charge. Collecte des informations centralisée : Le choix de centralisation de la collecte d’informations est très bénéfique en terme de : 1/ éviter le problème de diffusion d’information « all to all » si on adopte la stratégie distribuée, donc on a une diffusion d’information « all to one », c.à.d réduire le trafic réseau. 2/minimiser le temps de collecte d’informations, et cela par interrogation et l’attente de réponse d’un seul nœud au lieu de plusieurs. 3/faciliter d’extensibilité aux autres grappes (clusters) : comme les informations de chaque cluster sont regroupées dans un seul poste ceci facilite l’échange d’information entre les clusters. Répartition de charge distribuée : L’opération de répartition de charge peut être réalisée sur n’importe quel nœud appartenant au système et veut répartir sa charge. Cette stratégie permet de : 1/ donner aux différentes stations l’initiative de répartir la charge de leurs applications indépendamment, cela donne une transparence à notre système et libère l’utilisateur de toutes contraintes d’emplacement et surtout pour les utilisateurs nomades.

III. APPROCHE AGENT MOBILE POUR LA REPARTITION DE
CHARGE

L’agent mobile est un point d’intérêt pour les systèmes distribués. Cet intérêt est dû grâce à sa facilité de migration sans prendre en considération l’hétérogénéité du réseau. De plus ils servent à diminuer le trafic du réseau [2]; pour ces raisons et d’autres l’agent mobile vient comme une nouvelle approche de répartition de charge Une approche possible de conception d’un système de répartition de charge basé agent est de donner à l’agent mobile toutes les fonctionnalités (de calcul, de contrôle, de négociation, de sécurité…). Un des objectifs de conception d’un système de répartition de charge basé agent, est de minimiser le code à déplacer dans

3 2/éviter les problèmes d’étranglement du serveur dans le cas ou plusieurs stations veulent répartir sa charge sur le système. Notre plate forme se compose de deux types d’agents : A. Agents mobiles : il y a deux agents dans ce type : - Agent de travail : cet agent ne fait pas partie de notre plate forme mais de l’application à équilibré; pour commencer l’exécution il faut tout d’abord s’enregistrer chez l’agent d‘équilibrage qui décide où doit être l’exécuter. - Agent de découverte: cet agent est activé régulièrement par l’agent central d’information ; Ce dernier lui donne une liste des nœuds enregistrés dans son buffer, ensuite l’agent de découverte se déplace d’un nœud à un autre pour consulter l’état réel de ces derniers, dés qu’il termine l’ensemble des nœuds de la liste, il retourne avec un rapport à l’agent central. B. Agents stationnaires : avec trois agents : - agent central de collecte d’informations : cet agent est une base de référence pour tous les agents d’état, il joue le rôle de tableau noir où chaque agent d’état doit enregistrer ses propres informations structurées dans ce tableau et les modifie en cas de changement. L’agent central doit répondre aux demandes des agents d’équilibrage par offre d’une liste des stations disponibles qui possèdent une charge inférieure à un seuil Min calculé par l’agent central. - agent d’état : cet agent est dupliqué sur toutes les stations du système, son but est de calculer et contrôler régulièrement la charge de la station et informer l’agent central sur la charge de sa station s'il y a un changement significatif ; et déclencher l’agent d’équilibrage dans le cas où il y aurait une surcharge. - agent d’équilibrage : c’est le cerveau de notre système, il a pour mission de sélectionner les agents de travail à migrer et localiser les machines destinataire de migration. B. Coopération entre les agents : Les flèches pointées : sont les flèches qui représentent l’étape d’initialisation du système : (1) : envoie d’état de la charge station : les stations clientes doivent exécuter l’agent d’état pour pouvoir communiquer avec l’agent de collecte d’information central. Au démarrage, cet agent doit calculer la charge de sa station puis l’envoyer à l’agent central d’information avec l’adresse de sa station pour remplir la table de charge de l’agent central. (2) : déclenchement de l’agent de découverte : Cet agent est déclenché par l’agent central d’information d’une manière régulière dans le temps pour découvrir l’état réel du système afin d'assurer le bon fonctionnement de ce dernier

2
Agent de Découverte

Station centrale
Agent de collecte d'information

2 . 1
Agent d'état Agent d’Equilibrage

2 . 2 . 4 3

1
Agent d'état

4 4 5 4

Agent d’Equilibrage Agent de travai1 y.1 Agent de travail y.2

3 3

8 4

Agent de travai1 x.l Agent de travail x.2

Agent de travail i

7 4 6 4

Station .x
Agent de travail x.i

. . Station yde Agent travail y.n

Fig. 1: Coopération entre les agents de la plate forme (2.1) : visiter les stations du système : l’agent de découverte doit visiter les stations trouvées dans son itinéraire, l’une après l’autre, pour extraire leurs informations techniques et leurs états. (2.2) : retour à l’agent de collecte d’information central : dés qu’il termine son itinéraire, l’agent de découverte doit retourner à l’agent central. Les flèches continues : sont les flèches qui représentent l’étape de répartition de la charge : (3) : déclencher l’équilibrage : Si la charge de la station dépasse un seuil Max (donné par l’utilisateur) l’agent d’état envoie un message d’équilibrage à l’agent d’équilibrage. (4) : demande de la liste des stations candidates : l’agent d’équilibrage envoie une requête à l’agent central pour récupérer la liste des stations prometteuses d’équilibrage calculée par l’agent de collecte d’information central. (5) : récupérer la liste des stations candidates : après les calculs, la liste est envoyée à l’agent d’équilibrage puisque celui-ci l’a demandé. (6) : choix de l’agent et de la station de migration : l’agent d’équilibrage doit sélectionner l’agent et localiser la station de migration.

4 (7) : demande d’enregistrement : l’agent de travail demande l’enregistrement à l’agent d’équilibrage de la station distante. (8) : enregistrement : l’agent d’équilibrage ajoute l’agent de travail dans sa table.

Plate forme d’exécution

P III /Intel 651MHZ Me

P III /Intel 651MHZ Windows 2000pro

Pentium4 2.30GHz WindowsXP

PIII 9 94MHZ WindowsXP

Intel Xeon 3.06GHZ X4 Linux REdHat 9

Nombre de threads

V. ALGORITHME D’ESTIMATION DE CHARGE COMPARABLE Le calcul de la charge est réalisé par l’agent d’état, dans notre cas, en se limitant à la charge du processeur. Notre algorithme se base sur l’algorithme proposé par l’équipe ADAJ[ 1], mais avec quelques modifications. Le mécanisme de calcul de charge s’appuie sur un thread java qui calcule le temps moyen passé en attente du CPU. Ce thread est lancé dans chacune des JVM (JavaVirtual Machine ) appartenant à la plateforme d’exécution. L’algorithme d’estimation de la charge est basé sur un thread java, le voici: EstimationCharge(temps_du_sommeil,nbre_de_iteration, tampon) { t1=System.nanoTime() ; //lire le temps de la machine for(int i=0 ; i< nbre_de_iteration ,i++){ yield () ; } t2 =System.nanoTime () ; //lire le temps de la machine temps_en_attente_total=t2-t1;//calculer le temps total temps_en_attente= temps_en_attente_total/ nbre_de_iteration ; //calcul du temps moyen sleep(temps de sommeil) //Entrer en sommeil pour temps_du_sommeil et rendre le CPU Mais cet algorithme ne prends pas en considération la puissance du processeur (vitesse du CPU),et l’hétérogénéité des systèmes d’exploitation(technique d’allocation de processeur), il est conçu pour calculer le temps d’attente d’un processus dans la file d’attente des processus prêts. Notre proposition pour améliorer cet algorithme est de l’accompagner avec un outil d’ajustement, ce dernier sert à calculer des charges comparables pour des plates formes hétérogènes à partir les charges estimées par l’algorithme précédent et sous les mêmes conditions : portabilité, efficacité et simplicité. Le mécanisme de calcul du taux est le suivant : On lance pour chaque station du réseau un thread chargeur et un thread estimateur en même temps, puis on calcule le temps d’exécution du thread chargeur, gardant en même temps la charge de la station, la charge est estimée par le thread estimateur. taux=temps d’exécution /charge À cet effet la charge à comparer à un instant t est : Charge comparable(t)=charge(t)*taux. Nous avons testé cet algorithme sur différent type de CPU et de systèmes d’exploitation. Comme le montre ce tableau :

Charge initiale Charge(t) TempsExéc(t) taux Charge initiale Charge (t) TempsExéc(t) taux Charge initiale Charge (t) TempsExéc(t) taux Charge initiale Charge (t) TempsExéc(t) taux

0 11MS 7375 6.70 0MS 22MS 14774 6.71 0MS 33MS 22166 6.71 0MS 44MS 29521MS 6.70

0MS 60 MS 7480 1.24 0MS 119MS 14723 MS 1.23 0 MS 178 MS 22149 MS 1.24 0 MS 236 MS 29297 MS 1.24

0 MS 19MS 2250 MS 1.18 0MS 38 MS 4544MS 1.19 MS 0 MS 58 MS 6882 MS 1.18 0 MS 78 MS 9251MS 1.18

0 MS 93MS 5142 MS 0.55 0MS 182 MS 9976 MS 0.54 0 MS 268 MS 14808 MS 0.55 300 MS 351MS 19423MS 0.55

0MS 5MS 1633MS 3.26 0MS 5MS 1689MS 3.37 0MS 5MS 1707MS 3.41 0MS 5MS 3412MS 6.82

Table1: Résultats d’expérimentation

Notre plate forme s’implémente autour du langage java couplé avec la plate forme d’agents mobiles AGLETS. Le réseau sur lequel a été testée notre plate forme est composé de 6 stations de travail :

1 chargeur 2 chargeurs 3 chargeurs 4 chargeurs

Discussion :
Les résultats d’expérimentation de notre algorithme montrent qu’il donne des résultats conformes à notre hypothèse en terme de: A. augmentation de temps de réponse avec l’augmentation de nombre de threads . B. variation de la charge en fonction de système d’exploitation . C. variation de la charge en fonction de la machine . D. Obtention des charges comparables via le taux d’exécution. D’après l’expérimentation, on peut dire que notre algorithme donne des résultats qui reflètent la charge de la machine et peut aussi refléter la charge d’un système hétérogène.

VI. EXPÉRIMENTATION

5
Modèle Pentium4 Pentium4 CPU 1.7 GHZ 2.8 GHZ RA M 256 MO 256 MO SE windows2000 Pro Windows XP Nbre de machines 2 4

VII. CONCLUSION Dans ce travail, nous avons conçu et implanté un prototype d’une plate forme de répartition de charge à base d’Agent Mobile pour les réseaux hétérogènes. Dans lequel nous essayons à répondre aux questions suivantes : Comment exploiter l’approche agent pour la répartition de charge? Comment obtenir des charges comparables dans un environnement hétérogène? La plate forme est testée sous une machine Virtuelle Java standard, il reste à la tester sous JikesRVM pour l’enrichir avec la migration forte des aglets.

Notre application testée est de type académique illustre le problème de multiplication des matrices de grand volume. Le test se déroule comme suit : 1 : Le programme génère deux matrices : Les mêmes matrices sont testées pour calculer les résultats de la multiplication dans les deux versions (phase 2 et 3) 2 : Version 1 : Le programme va découper la première matrice en sous matrices, puis les dispatcher sur les stations existantes, après les calculs, il collecte les résultats obtenus dans une seule matrice et indique le temps d’exécution de cette opération. 3 : Version 2 : Le programme va découper la première matrice en un nombre saisi par l’utilisateur, pour notre cas ce nombre est égal au nombre de stations dans la première version, afin de pouvoir comparer le temps d’exécution de deux versions sous les mêmes conditions. Après la réception de la liste des stations prometteuses d’équilibrage, l’agent d’équilibrage va dispatcher les AGLETS porteuses les sous matrices, entre les stations concernées par l’équilibrage, sur lesquelles elles s’exécutent ; après les calculs, l’agent original de la multiplication indique le temps d’exécution. Après l’expérimentation nous avons constaté un gain de performance en terme de temps d’exécution dans la deuxième versions du programme (multiplication avec équilibrage de charge), malgré que les deux versions sont exécutées sous les mêmes conditions ( les mêmes stations de travail et le même nombre d’AGLETS porteuses des sous matrices). Résultats : Nous avons obtenu les résultats suivants :
Stations Charge Station1 27MS Station 2 30MS Station 3 25MS Station4 79MS Station5 100MS

REFERENCES [ 1] : A.BOUCHI. : proposition d’un mécanisme d’observation dynamique de l’exécution d’applications Java distribuées.thèse de PHD .Université des Sciences et Technollogies de Lille .2003. [2] :L.Danny : Mobile objects and mobile agents the future of distributed computing 1999. [3]. Durfee E.H, Lesser V.R, et Corkill,D.D. Trends in Cooperative Distributed Problem Solving: IEEE Transactions on Knowledge and Data Engineering, March 1989, KDE-1(1), pages 63-83. [4] : Eric Piel : equilibrage de charge pour systemes asymétriques temps réel multi processeurs.mémoire DEA, laboratoire d’informatique fondamentale Lille France. 2004. [5] :J. Gomoluch, M. Schroeder, Information Agents on the Move: A Survey on Load-balancing with Mobile Agents, Software Focus, 2 (2001), pp. 31-36. [6]: L. Jiming, J.Xialong, W.Yuanshi: Agent based load balancing on homogeneous mini-grids. IEEE transactions on parallel and distributed system vol 16 N-6 June 2005. [7]: Cristophe LAN : répartition de charge dynamique à l’initiative des processus, thèse de doctorat, 1999, université de franche comité. [8]: Z.Mohammed L.Wei, P.Srinivasan: customized dynamic load balancing for a network of workstations, 1995, university of Rochester. [9]: Paraskevas Evirpidou, George Samaras, Christoforos Panayiotou, Evagellia Pitoura PACMAN metacomputer, parallel computing with java mobile agent université de Cyprus 2000. [10] : S. Rouvrais : utilisation des agents mobiles pour la construction de service distribute , thèse de doctorat ,Université Rennes1 , Juillet2002. [ 11] : F. SPIES : Conception et évaluation de stratégies de répartition de charge Dynamique dans les systèmes distribués ; thèse PHD décembre1994.
.

Temps de calcul sans répartition de charge : 59 Secondes et 844 Milliseconde. Temps de calcul avec répartition de charge : 43 Secondes et 797 Millisecondes. D'après l’expérimentation nous pouvons déduire que le nombre de stations n’est pas un facteur majeur pour gagner le temps d’exécution d’application parallèle, par rapport à l’introduction d’un mécanisme d’équilibrage de charge dans cet environnement; il faut bien exploiter nos ressources avant de les augmenter.