Vérification de tables de routage par utilisation d'un ensemble représentatif d'en-têtes - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1, 2) , (1) , (1, 3) , (4, 3) , (3, 4) , (1, 2, 3)
1
2
3
4

Abstract

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.
Fichier principal
Vignette du fichier
verification.pdf (146.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01148595 , version 1 (04-05-2015)

Identifiers

  • HAL Id : hal-01148595 , version 1

Cite

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⟩
206 View
166 Download

Share

Gmail Facebook Twitter LinkedIn More