Algorithme distribué de routage compact en temps optimal

Cyril Gavoille (1) , Christian Glacet (1, 2) , Nicolas Hanusse (1, 2) , David Ilcinkas (2, 3)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
3 Combinatoire et Algorithmique

Nous présentons un algorithme distribué construisant des tables de routage de taille sous-linéaire en n, le nombre de nœuds du réseau. Le temps de convergence est proportionnel au diamètre, ce qui est optimal. Par rapport à BGP, la complexité du nombre de messages échangés est améliorée jusqu'à un facteur n^1/2, alors que la longueur des routes induites par les tables est allongée d'un facteur garanti constant. Notre algorithme est conçu pour un environnement statique synchrone ou asynchrone et produit un schéma name-independent.

Mots clés: compact routing; routage compact; distribué; optimal

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, David Ilcinkas. Algorithme distribué de routage compact en temps optimal. 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2013, Pornic, France. pp.117-120. ⟨hal-00818445v2⟩