Metarouting allows for the modeling of routing protocols using an algebraic structure called routing algebra. Routing protocols requiring design or validation can easily be modeled using this approach. To date, however, existing research on routing algebras has mainly focused on applying this approach to routing protocols that are generally used in networks which have a single addressing and forwarding protocol. The basic algebraic structures used in such contexts are semirings, Sobrinho’s algebras and algebras of endomorphisms. In this paper, we propose the modification of these existing routing algebras to deal with networks that contain multiple forwarding protocols where tunnels are omnipresent. To achieve this, we define new algebraic structures derived from the three aforementioned ones, in order to model the generalized routing problem with automatic tunneling entitled valid paths algebra. All of our routing algebras are defined as semi-direct products of two structures, the well-known shortest paths algebra and the proposed valid paths algebra. These new algebras are isotonic and non-monotonic with a partial order. We propose a fixed point for those new algebras and we prove the iterative convergence to the optimal solution of the valid shortest paths problem.

Most current routing protocols are based on path computation algorithms in graphs (e.g., Dijkstra, Bellman-Ford, etc.). These algorithms have been studied for a long time and are very well understood, both in a centralized and distributed context, as long as they are applied to a network having a single communication protocol. The problem becomes more complex in the multi-protocol case, where there is a possibility of encapsulation of some network protocols into others, therefore inducing nested tunnels. The classic algorithms cited above no longer work in this case because they cannot manage the protocol encapsulations and the corresponding protocol stacks. In this work, we propose a highly parallelizable algorithm that takes into account protocol encapsulations as well as protocol conversions in order to compute shortest paths in a multi-protocol network. To achieve this computation efficiently, we study the transitive closure between subpaths (i.e., the concatenation of two subpaths to obtain a longer one) in the case where each subpath induces a protocol stack, and thus tunnels. Leveraging on Software-Defined Networks with a controller having a highly parallel architecture enables us to compute the routing tables of all nodes in a very efficient way. Experimentation results on both random and realistic topologies show that our algorithm outperforms the previous solutions proposed in the literature.

Metarouting models routing protocols in the form of an algebraic structure called routing algebra. It aims to help designing or validating routing protocols. Most research work on routing algebras have been applied to routing protocols used in networks having a single addressing and forwarding protocol. In this context, some of the basic algebraic structures used are semirings. In this paper, we define a new algebraic structure for dealing with networks containing multiple forwarding protocols, which may induce many (and possibly nested) tunnels. We widely generalize the semiring structure for modeling the routing problem with automatic tunneling. We define a new model of routing algebra with tunneling. It is defined as a semi-direct product of two structures, the well-know shortest paths algebra and a new proposed valid paths algebra. We show that it has a fixed point and we prove the iterative convergence to the optimal solution of the valid shortest paths problem.