Resilient Recursive Routing in Communication Networks
Summary
After a brief review of conventional approaches to shortest path routing an alternative algorithm that abstracts a network graph into a logical tree is introduced. The algorithm is based on the decomposition of a graph into its minimum cycle basis (a basis of the cycle vector space of a graph having least overall weight or length). A procedure that abstracts the cycles and their adjacencies into logical nodes and links correspondingly is introduced. These logical nodes and links form the next level logical graph. The procedure is repeated recursively, until a loop-free logical graph is derived. This iterative abstraction is called a logical network abstraction procedure and can be used to analyze network graphs for resiliency, as well as become the basis of a new routing methodology. Both these aspects of the logical network abstraction procedure are discussed in some detail.
