Affordable Access

Quelques bornes sur les chemins dans les réseaux multicouches

Authors
  • Lamali, Mohamed
  • Fergani, Nasreddine
  • Cohen, Johanne
Publication Date
Jun 04, 2019
Source
HAL
Keywords
Language
French
License
Unknown
External links

Abstract

Les réseaux multicouches sont des réseaux où certains protocoles peuvent être encapsulés dans d'autres le long d'un chemin, induisant ainsi des tunnels parfois imbriqués. Les plus courts chemins faisables (i.e., qui respectent l'ordre des encapsulations et la continuité protocolaire) peuvent comporter des circuits. Dans cet article, nous donnons des bornes sur la longueur de tels chemins. Nous montrons qu'il existe des réseaux à n sommets où le chemin le plus court entre deux sommets spécifiés est superpolynomial en n. Nous montrons néanmoins que si un plus court chemin existe, sa longueur ne peut être plus qu'exponentielle en n². La version complète de cet article est [LFC18](https://hal.archives-ouvertes.fr/hal-01706362v2)

Report this publication

Statistics

Seen <100 times