Autour des graphes et du routage

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.

Une mise en forme en XML/SMIL a été réalisée par Pierre Jancène. Pour visionner ce document, RealPlayer était utilisé à l’origine, les évolutions logicielles ne permettent malheureusement plus de le lire.

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

Il reste possible d’accéder à la vidéo, au format Real, lisible avec RealPlayer ou VLC.

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