Autour des graphes et du routage  

De l'Internet aux réseaux ad hoc, en passant par les réseaux de pair à pair, la façon dont les messages sont acheminés constitue le problème central des réseaux : c'est ce qu'on appelle le routage. Les graphes sont l'outil mathématique privilégié pour modéliser les réseaux et étudier ce problème.

Selon le réseau auquel on s'intéresse, le routage prend des aspects variés. Se frayer un chemin jusqu'à une destination donnée peut se décliner différemment suivant la manière dont cette destination est identifiée. Cependant, certaines techniques algorithmiques se retrouvent de façon récurrente.

Ainsi, pour diffuser un message dans un réseau sans en connaître la topologie, on utilise une technique qui s'appelle l'inondation. Elle apparaît comme une brique de base de nombreux protocoles de routage.

Par ailleurs, pour obtenir une certaine stabilité par rapport à la dynamique du réseau, un principe classique consiste à itérer un processus qui converge vers un point fixe. Un protocole célèbre obtient par exemple ses tables de routage comme point fixe d'itérations asynchrones de communications de vecteurs de distances.

Enfin, les réseaux les plus grands comme Internet ou les réseaux de pair à pair nécessitent une structuration qui permette de les appréhender sans les connaître dans leur globalité.

Cet exposé de Laurent Viennot a été enregistré le 14 décembre 2005, à l'INRIA Rocquencourt. Il reprend sa soutenance d'habilitation à diriger les recherches, qui s'est déroulée le 5 décembre 2005.

• la présentation de 50 mn en XML/SMIL : les transparents synchronisés avec la vidéo de l'orateur (haut débit).
• la présentation de 50 mn en XML/SMIL : les transparents synchronisés avec la voix de l'orateur, sans sa vidéo (modem).

La mise en forme en XML/SMIL a été réalisée par Pierre Jancène. Pour visionner ces documents, utiliser RealPlayer.

Pour en savoir plus sur ce sujet, nous vous proposons le document écrit téléchargeable en PDF (5,9 Mo).