Novel Topological Framework for Adaptive Routing

We identify that a major contributing factor to the shortcomings of current routing protocols is their mathematical treatment of graphs used to represent networks. Typically, routing protocols decimate the rich connectivity present in a network into a small number of distinct trees for every source, which are then translated into routing table entries. We propose a new routing paradigm that introduces a novel concept of neighbourhood, embodying path diversity. This framework summarises rather than decimates paths throughout the network, preserving and exploiting all of the network´s potentially rich intrinsic path diversity. Central to our abstraction are two intimately connected and complementary path diversity units: simple cycles, and cycle adjacencies. A recursive network abstraction procedure is presented, together with an associated generic recursive routing protocol family that offers many desirable features. A simple instance of such a protocol is compared against existing wired and wireless routing protocols through simulations for a highly-stressed network with unstable links, illustrating the potential advantages of the proposed approach.