A Graph-Theoretic Model of Routing Hierarchies

We present a graph-theoretic model of routing hierarchies that abstracts the generic properties of standard routing protocols such as PNNI and OSPF/BGP. These protocols are currently deployed in operational networks. Our model is based on purely topological constructs, without referring to protocol details. Through graph partitioning and refinements, a multi-level hierarchy of sibling and child clusters is obtained. By hiding the topology of a cluster from outside, this structure allows routing protocols to scale to support large networks. Without revealing intra-cluster details, a cluster cost graph is defined in terms of entry-to-exit transit costs. This graph is advertised to other clusters. Each node within a cluster combines the cost graphs from other clusters to construct a routing graph for routing traffic. The limited view of a routing graph may sometimes lead to suboptimal path selection. Additionally, routing between sibling clusters may have loops; protocol restrictions are needed for loop avoidance.