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

Résumé : 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.
Type de document :
Communication dans un congrès
ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01148595
Contributeur : Fabien Mathieu <>
Soumis le : lundi 4 mai 2015 - 20:59:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : lundi 14 septembre 2015 - 18:46:22

Fichier

verification.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01148595, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

260

Téléchargements de fichiers

158