A stack-vector routing protocol for automatic tunneling - Graphes, Algorithmes et Combinatoire Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

A stack-vector routing protocol for automatic tunneling

Résumé

In a network, a tunnel is a part of a path where a protocol is encapsulated in another one. A tunnel starts with an encapsulation and ends with the corresponding decapsulation. Several tunnels can be nested at some stage, forming a protocol stack. Tunneling is very important nowadays and it is involved in several tasks: IPv4/IPv6 transition, VPNs, security (IPsec, onion routing), etc. However, tunnel establishment is mainly performed manually or by script, which present obvious scalability issues. Some works attempt to automate a part of the process (e.g., TSP, ISATAP, etc.). However, the determination of the tunnel(s) endpoints is not fully automated, especially in the case of an arbitrary number of nested tunnels. The lack of routing protocols performing automatic tunneling is due to the unavailability of path computation algorithms taking into account encapsulations and decapsulations. There is a polynomial centralized algorithm to perform the task. However, to the best of our knowledge, no fully distributed path computation algorithm is known. Here, we propose the first fully distributed algorithm for path computation with automatic tunneling, i.e., taking into account encapsulation, decapsulation and conversion of protocols. Our algorithm is a generalization of the distributed Bellman-Ford algorithm, where the distance vector is replaced by a protocol stack vector. This allows to know how to route a packet with some protocol stack. We prove that the messages size of our algorithm is polynomial, even if the shortest path can be of exponential length. We also prove that the algorithm converges after a polynomial number of steps in a synchronized setting. We adapt our algorithm into a proto-protocol for routing with automatic tunneling and we show its efficiency through simulations.
Fichier principal
Vignette du fichier
infocom_distributed (1).pdf (367.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01987354 , version 1 (23-01-2019)

Identifiants

Citer

Mohamed Lamine Lamali, Simon Lassourreuille, Stephan Kunne, Johanne Cohen. A stack-vector routing protocol for automatic tunneling. IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, Apr 2019, Paris, France. pp.1675-1683, ⟨10.1109/INFOCOM.2019.8737536⟩. ⟨hal-01987354⟩
185 Consultations
103 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More