Sujet : Recherche d'informations par agents mobiles

Responsable : Nicolas Hanusse
Téléphone : 05 4000 2604
e-mail : hanusse@labri.fr
Site Web : http://www.labri.fr/~hanusse
Equipe : Combinatoire et Algorithmique

Présentation du sujet :

Un agent mobile est un programme circulant dans des réseaux et ayant la capacité de s'exécuter quand il arrive à un noeud du réseau. Ici, le terme "réseau" est pris au sens large car il peut inclure aussi bien des réseaux de type Internet, ad hoc, graphe du Web, réseau pair à pair. Les applications sont multiples: mise-à-jour automatique de données (table routage, paramétrages divers, ...) , recherche et collecte d'informations, appels automatiques de numéros de téléphones, apprentissage d'un "plan" d'un environnement/terrain (avec ou sans
obstacles), ...

Nous nous intéressons aux agents mobiles de recherche. Dans un environnement centralisé, un agent va interroger un annuaire ou des tables dont il connait la localisation. C'est plus ou moins la démarche que fait un utilisateur lorsqu'il interroge un moteur de recherche sur le WEB. Cette approche pose plusieurs problèmes:
- certains noeuds doivent contenir énormément d'informations.
- le temps de mise-à-jour des annuaires ou tables lors de changement peut être extrêmement important. Par exemple, Google met environ 2 mois à reparcourir toutes les pages qu'il indexe.

En résumé, cette approche est très gourmande en espace mémoire et en
temps de mise-à-jour. D'autre part, le caractère dynamique de certains réseaux rende l'accés à une information existante non encore indéxé très difficile.

Dans ce sujet, nous proposons une approche distribué: les noeuds contiennent des indications partielles pour trouver des informations (pensez aux panneaux de signalisation aux intersections de route). Ce type de méthode est particulièrement adapté à des réseaux dynamiques ou pair à pair (Gnutella) dans lesquels tous les noeuds possèdent un même rôle contrairement à l'approche centralisée.

L'objectif de ce mémoire est de concevoir, étudier et expérimenter des algorithmes menant à des informations avec différentes contraintes:
- le réseau peut être défaillant. Il est intéressant de construire des
algorithmes auto-stabilisant.
- la quantité de mémoire aux noeuds ou des agents peut être borné.
- ...

Après une phase de conception et d'analyse théorique, les algorithmes devront être validés sur des données réelles ou sur des simulations.L'étudiant devra être intéressé par l'algorithmique distribué, les réseaux et la modélisation par des graphes.

Mot-clés : réseau, algorithmique distribué, graphes, agents mobiles

Références :
[1] "Searching with Mobile Agents in Networks with Liars", Hanusse, Kranakis,
Krizanc, Actes de EUROPAR 1999, a paraître dans Discrete Applied Math.

[2] "Memoryless Search Algorithms in Networks with faulty Advice", Hanusse,
Kavvadias, Kranakis, Krizanc, Actes de TCS 2002

[3] "Computing Science: Graph Theory in Practice: Part II.", Hayes, American Scientist, Vol. 88, No. 2, March-April 2000, pages
104-109. [Applications of mathematical graph theory to very large structures,
especially the World Wide Web.]

[4] "Gnutella 0.6", T. Klingberg et R. Manfredi
"http://rfc-gnutella.sourceforge.net/

[5] "Mapping the gnutella network: properties of large-scale
peet-to-peer systems and implications for system design". ACM SIGCOMM 2001

Commentaires :
Ce sujet est proposé dans le cadre du projet MOBICOOP avec Sebastien Tixeuil du LRI.