Institut de la Francophonie pour Centre de Recherche Informatique de l'Informatique Montréal RAPPORT DE STAGE MODÉLISATION ET IMPLÉMENTATION D'UN SYSTÈME DISTRIBUÉ DE PAGES BLANCHES AU SEIN D’UNE PLATE- FORME MULTI-AGENT Réalisée par : NGUYEN Thi Truc Vien Promotion 7 - IFI Sous la responsabilité de : M. Arnaud DURY Chercheur au CRIM Montréal, décembre 2003 TIEU LUAN MOI download : skknchat@gmail.com TIEU LUAN MOI download : skknchat@gmail.com MODÉLISATION ET IMPLÉMENTATION D'UN SYSTÈME DISTRIBUÉ DE PAGES BLANCHES AU SEIN D’UNE PLATE- FORME MULTI-AGENT TIEU LUAN MOI download : skknchat@gmail.com MODÉLISATION ET IMPLÉMENTATION D'UN SYSTÈME DISTRIBUÉ DE PAGES BLANCHES AU SEIN D’UNE PLATE- FORME MULTI-AGENT Réalisée par : NGUYEN Thi Truc Vien Promotion 7 - IFI Sous la responsabilité de : M. Arnaud DURY Chercheur au CRIM Centre de Recherche Informatique de Montréal Décembre, 2003 TIEU LUAN MOI download : skknchat@gmail.com Table des matières Table des matières __________________________________________________________ 4 Remerciements _____________________________________________________________ 7 Résumé ___________________________________________________________________ 8 Abstract __________________________________________________________________ 9 Plan du rapport ___________________________________________________________ 10 Chapitre 1. Systèmes multi-agents et systèmes peer-to-peer ________________________ 11 I.
Principes de base____________________________________________________ 11 I.1 Introduction des systèmes multi-agents _______________________________ 11 I.2 Systèmes multi-agents : Principes généraux et applications _______________ 11 I.1 Qu’est-ce qu’un agent ? _____________________________________ 12 I.3 Système multi-agent ________________________________________ 13 I.3 Les plates-formes d'agents mobiles : Aglets, Jade, Voyager _______________ 14 I.4 Notre plate-forme multi-agent : Présentation de Guest _________________ 17 I.1 Qu’est-ce qu’un système peer-to-peer ? _____________________________ 18 I.2 Les services des systèmes P2P ____________________________________ 18 I. État de l'art _____________________________________________________ 21 TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent II.1 Les limitations des SMA disponibles : Aglet, Jade, Voyager, … ___________ 21 II.1 Rappel de service de Pages blanches (AMS – Agent Management System) 21 II.2 Problème de l'agent "PagesBlanches" ____________________________ 21 II.2 L’inconvénient des systèmes P2P : Gnutella, Chord _____________________ 22 III.1 Mes travaux ____________________________________________________ 23 III.2 But principal : Service de pages blanches + Peer-to-peer _________________ 23 III.1 Nouveau modèle de pages blanches ______________________________ 23 III.2 Peer-to-peer_________________________________________________ 23 Chapitre 3. Analyse du système_______________________________________________ 24 IV. Aperçu du système ________________________________________________ 24 IV.1 Principes de fonctionnement du Chord________________________________ 24 IV.2 Hachage consistant ___________________________________________ 25 IV.3 Localisation par hachage – Table d’index _________________________ 25 IV.4 Tolérance aux fautes – Listes de successeurs _______________________ 26 IV.5 Mise à l’échelle de la localisation des nœuds - Protocole de stabilisation 27 IV.2 Principes de fonctionnement du notre Système _________________________ 28 IV.3 Service de nomage _______________________________________________ 30 IV.4 Architecture du Système___________________________________________ 31 IV.5 L'organisation du code ____________________________________________ 36 IV.1 massip _____________________________________________________ 36 Table des matières 5 TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent IV.2 Techniques inspirées du Chord__________________________________ 38 V.1 Pas de migration et de mort ____________________________________ 39 V.2 Avec de migration – techniques du Chord pas encore implémentées ____ 39 V.3 Avec les techniques d'optimisation du Chord_______________________ 41 V.3 Évaluation globale _______________________________________________ 43 Chapitre 5.3 Développements dans l'avenir ______________________________________ 45 Annexes _________________________________________________________________ 46 Systèmes multi-agents : Principes généraux et applications_____________________ 46 whatis.com _____________________________________________________________ 51 Interface graphique du Système ___________________________________________ 52 Références _______________________________________________________________ 57 Table des matières 6 TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent Remerciements Ce travail de stage a pu voir le jour avec énormément d'aide et encouragement des personnes autour de moi.
Ce court remerciement ne sera pas suffisant pour récompenser leurs efforts mais tout de même. J’adresse tout d'abord mes grands remerciements à M. Arnaud Dury – chercheur du CRIM -- pour avoir dirigé ce stage avec passion et avec patience. Son aide précieuse m'a fait enfin arriver à la finition de ce travail.
Je souhaite remercier M. Thang Viet Pham – doctorant du CRIM -- pour son intérêt à mes travaux pendant la période de mon stage, ainsi pour ses conseils scientifiques et pratiques qu'il m'a prodigué au cours de cette recherche. Je tiens à exprimer mes remerciements, à M. Laurent Magnin – responsable de l’ancienne équipe GLIC (Génie logicielle et ingénierie de la connaissance) du CRIM et professeur associé à l’Université de Montréal -- qui m'a accueillie gentiment au sein de l'équipe GLIC qu’il a animé.
Sa gentillesse et sa sympathie ont accompagné la réalisation de la partie de ce travail. Je remercie sincèrement tous les membres du CRIM. Depuis le début de mon stage au sein de l'équipe, leurs aides et leurs encouragements m'ont permis d’avancer pendant cette période difficile. Je suis profondément reconnaissante à tous mes amis pour leur aide et leurs encouragements, notamment les étudiants vietnamiens à Montréal pour leurs collaborations.
Je tiens à remercier tous les membres de l'ancienne équipe GLIC que je ne les ai pas encore cités – Nicolas Besson, Kaddour Boukerche, El-Hachemi Alikacem, Nazim Bougherara -- pour leurs encouragements et gentillesse ! Je les remercie de m'avoir encouragé. Enfin, je tiens à adresser mes grands remerciements aux membres de ma famille pour la patience qu'ils m'ont montrée pendant cette longue période de travail. Remerciements 7 TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent Résumé Le thème des systèmes multi-agents (SMA) est actuellement un champ de recherche très actif. C’est une discipline qui s’intéresse aux comportements collectifs produits par les interactions de plusieurs entités autonomes et flexibles appelées agents, que ces interactions tournent autour de la coopération, de la concurrence ou de la coexistence entre ces agents.
Il existe plusieurs plate-formes d'agents mobiles : Jade, Aglet, Voyager,. Dans ces systèmes aujourd’hui, le fonctionnement des services de pages blanches et jaunes est centralisé. En raison de cela, il faut un serveur central qui sert à gérer les localisations des agents. À côté des SMA existent les systèmes peer-to-peer : un ensemble de clients informatique partageant leurs données ou leurs ressources à travers un réseau de communications où les ordinateurs sont à la fois clients et serveurs.
Cela donne des avantages : facilité de mise à l’échelle, robustesse, coopération, partage,. Il y a de nombreux exemples : Gnutella, Chord (partager des fichiers),. Mais, dans ces systèmes, le code reste toujours immobile, non migrant. Au sein des systèmes distribués, deux grandes tendances convergent.
D'un côté, nous voyons apparaître des environnements d'exécution de systèmes d'agents mobiles où il faut un serveur central pour gérer la communication entre agents. De l'autre côté, nous voyons apparaître des systèmes peer-to-peer où tout est égal. Nous proposons de développer un nouveau modèle de pages blanches pour les applications multi-agents. C’est une plate-forme multi-agents intégrant les concepts des systèmes distribués, des services d’infrastructure des plates-formes d’agents – à savoir les services de pages blanches et enrichis par les techniques du Chord – un protocole de peer-to-peer du MIT pour les applications sur Internet.
Notre rédaction a pour ambition de présenter les principes fondamentaux, problèmes, solution et techniques utilisées pour la réalisation du projet. Mots clés : systèmes multi-agents, systèmes peer-to-peer, service de pages blanches, techniques du Chord Résumé 8 TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent Abstract Multi-agent system is not a new subject. It is an active research field at present, a subject about collective behaviours generated by interactions of several autonomous, flexible entities called agents. These interactions turn around the cooperation, competition or coexistence among the agents.
There are several mobile agents platforms : Jade, Aglet, Voyager, … The problem is that, AMS – Agent Management System and DF – Directory Facilitator services of actual multi-agents platforms have been still centralized. Therefore, a central server is necessary for agent management. Besides multi-agents systems, there are peer-to-peer systems – a set of computer clients sharing their data and resources through a communication network where each one is both client and server. That provides many advantages : scalability, without centralized authority, robustness, cooperation, sharing, … There are various examples : Gnutella, Chord (file sharing), … But, the code of those systems is still immobile, without migration.
So, in the distributed systems world, the two tendencies tend to meet to each other. On one side, we see appearing mobile agent system execution environments, which need a central server for agent management. On the other side, we see appearing peer-to-peer systems where all is equal. Beyond the two ones, we propose to develop a new model of AMS for multi- agents applications.
That is a multi-agents platform integrated distributed systems concepts, infrastructure services of multi-agents platforms like AMS (white pages) services and enriched of Chord techniques – a peer-to-peer protocol of MIT for Internet applications. Our composition is for the purpose of presenting the fundamental principles, problems, solution and techniques used to carry out this project. Key words : multi-agents systems, peer-to-peer systems, AMS (white pages) service, and Chord techniques Abstract 9 TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent Plan du rapport Le chapitre 1, ″Systèmes multi-agents et systèmes peer-to-peer″ introduit les principes et quelques exemples d'applications des systèmes multi-agents, plate-formes d'agents mobiles et systèmes peer-to-peer. Le chapitre 2, ″État de l'art″ présente les problèmes, notre solution et le but principal de notre projet.
Le chapitre 3, ″Analyse″ détaille le système réalisé, techniques utilisées et l'architecture de notre système. Le chapitre 4, ″Résultats atteints″ fait des statistiques quantiques et évalue les résultats. Le chapitre 5, ″Conclusion″ présente les avantages, inconvénients du système et son développement en réalité au futur. Plan du rapport 10 TIEU LUAN MOI download : skknchat@gmail.
Systèmes multi-agents et systèmes peer- to-peer I. Principes de base I.1 Introduction des systèmes multi-agents L'informatique devient de plus en plus diffuse et distribuée. La décentralisation et donc, la coopération entre modules logiciels est un besoin. De plus, avec la croissance de la taille, de la complexité de nouvelles applications informatiques, la vision centralisée et assez statique atteint ses limites.
On est ainsi naturellement conduit à chercher une façon de donner plus d'autonomie et d'initiative aux différents modules logiciels. Le concept de système multi- agent propose un cadre de réponse à ces enjeux.2 Systèmes multi-agents : Principes généraux et applications I.1 Définition générale TIEU LUAN MOI download : skknchat@gmail.com Modélisation et implémentation d’un système distribué de pages blanches au sein d’une plate-forme multi-agent I.1 Qu’est-ce qu’un agent ? Dans la littérature spécialisée, on trouve une multitude de définitions des agents. Elles se ressemblent toutes sur les concepts généraux, mais diffèrent selon le type d’application pour lequel est conçu l’agent. Première définition due à Ferber [4] : Un agent est une entité autonome, réelle ou abstraite, qui est capable d’agir sur elle- même et sur son environnement, qui, dans un univers multi-agents, peut communiquer avec d’autres agents, et dont le comportement et la conséquence de ses observations, de ses connaissances et des interactions avec les autres agents.
Définition proposée par Jennings, Sycara et Wooldridge récemment [5] : Un agent est un système informatique, situé dans un environnement, et qui agit d’une façon autonome et flexible pour atteindre les objectifs pour lesquels il a été conçu. − situé : l’agent est capable d’agir sur son environnement à partir des entrées qu’il reçoit de ce même environnement (systèmes de contrôle de processus, systèmes embarqués, etc.) ; − autonome : l’agent est capable d’agir sans l’intervention d’un tiers (humain ou agent) et contrôle ses propres actions ainsi que son état interne ; − flexible : l’agent dans ce cas est : capable de répondre à temps : l’agent doit être capable de percevoir son environnement et d’élaborer une réponse dans les temps requis, proactif : l’agent doit exhiber un comportement proactif et opportuniste, tout en étant capable de prendre l’initiative au bon moment, social : l’agent doit être capable d’interagir avec les autres agents (logiciels et humains) quand la situation l’exige afin d’accomplir ses tâches ou aider ces agents à accomplir les leurs. Systèmes multi-agents et systèmes peer-to-peer 12 TIEU LUAN MOI download : skknchat@gmail.