Sujet : Recherche d'informations par agents mobiles et diffusion

 

Responsables : Nicolas Hanusse, Cyril Gavoille

 

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. 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