Vers un routage compact distribué

Abstract

Dans cet article, nous proposons plusieurs schémas distribués de routage compact produisant des tables de routage d'au plus O(√n log n) entrées pour un réseau de n nœud, m arêtes et de diamètre D. La complexité de communication de ces algorithmes est de O(nm) et O(nm + n² * log n * min[(√n * log n), D]).