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