Vérification de tables de routage par utilisation d'un ensemble représentatif d'en-têtes

Yacine Boufkhad (1, 2) , Ricardo de La Paz (1) , Leonardo Linguaglossa (1, 3) , Fabien Mathieu (4, 3) , Diego Perino (3, 4) , Laurent Viennot (1, 2, 3)

1 GANG - Networks, Graphs and Algorithms
2 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
3 LINCS - Laboratory of Information, Network and Communication Sciences
4 Alcatel-Lucent Bell Labs France [Nozay]

Vérifier des tables de routage consiste à tester la validité des tables de l'ensemble des routeurs d'un réseau donné. Par exemple, il peut s'agir de tester l'absence de boucle ou de trou noir. Dans cet article, nous proposons une approche en deux étapes : construire un ensemble représentatif d'en-têtes de paquets, puis tester les propriétés désirées sur ces en-têtes. Toute la difficulté est de construire un ensemble relativement petit tout en garantissant qu'un paquet avec un en-tête arbitraire va se comporter exactement comme au moins l'un des en-têtes de l'ensemble représentatif. À partir d'un modèle très général inspiré du paradigme Software Defined Networking (SDN), nous montrons que le problème de la détection de boucles peut se résoudre en temps polynomial en la taille d'un ensemble représentatif. Nous montrons aussi qu'une condition naturelle sur les règles de routage, inspirée des travaux de Boutier et Chroboczek sur le routage par source et destination, permet de construire un ensemble représentatif dont la taille est au plus le nombre de règles de routage plus un. Par comparaison, sans cette condition naturelle, la taille de l'ensemble représentatif peut dans le pire des cas être exponentielle en la taille des en-têtes.

Mots clés: SDN; techniques de vérification et test; tables de routage

Domaines: Réseaux et télécommunications [cs.NI]

Yacine Boufkhad, Ricardo de La Paz, Leonardo Linguaglossa, Fabien Mathieu, Diego Perino, et al.. Vérification de tables de routage par utilisation d'un ensemble représentatif d'en-têtes. ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France. ⟨hal-01148595⟩