Evènement pour le groupe Algorithmique Distribuée


Date 2016-10-10  14:00-15:00
TitreCalcul de chemins dans les réseaux multicouches : une approche par la théorie des langages 
RésuméLes réseaux multicouches sont des réseaux où plusieurs protocoles coexistent sur différentes couches. Néanmoins, plusieurs architectures réseaux définissent des fonctions de conversion, encapsulation et désencapsulation de protocoles pour pallier cette hétérogénéité. Les algorithmes classiques de calcul de chemins dans les graphes ne peuvent être appliqués dans ce contexte car ils ne prennent pas en compte ces (dés)encapsulations. De plus, les plus courts chemins dans ce type de réseaux ont des caractéristiques non triviales : ils peuvent comporter des boucles et n’ont pas de sous-structure optimale. Après avoir constaté que les séquences de protocoles associées à un chemin dans un réseau multicouche forment un langage à contexte libre, nous proposons un nouveau modèle de réseau basé sur les automates à pile, ainsi que des algorithmes issus de la théorie des langages pour calculer le(s) plus court(s) chemin(s) dans ce type de réseaux. Nous montrons également que sous contrainte de bande passante, le calcul de chemins devient NP-complet, même dans un réseau symétrique et avec seulement deux protocoles. 
Lieu178 
Orateur Lamine Lamali 



Aucun document lié à cet événement.

Retour
Retour à l'index