HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

A stack-vector routing protocol for automatic tunneling

Abstract : 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.
Complete list of metadata

Contributor : Mohamed Lamine Lamali Connect in order to contact the contributor
Submitted on : Wednesday, January 23, 2019 - 12:49:36 PM
Last modification on : Tuesday, January 4, 2022 - 6:16:45 AM
Long-term archiving on: : Wednesday, April 24, 2019 - 1:03:19 PM


infocom_distributed (1).pdf
Files produced by the author(s)


  • HAL Id : hal-01987354, version 1
  • ARXIV : 1901.08326


Mohamed Lamine Lamali, Simon Lassourreuille, Stephan Kunne, Johanne Cohen. A stack-vector routing protocol for automatic tunneling. IEEE INFOCOM 2019, Apr 2019, Paris, France. ⟨hal-01987354⟩



Record views


Files downloads