Semiring Algebraic Structure for Metarouting with Automatic Tunneling

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.