A heuristic method for hierarchical partitioning of link-state Internet routing domain

Abstract

Hierarchical routing mechanisms based on hierarchical partitioning of Internet routing domain, so-called AS(Autonomous System), have been proposed to cope with scalability problems. For ISPs (Internet Service Providers) running link-state routing protocol, it is critical to secure Internet connection to reduce the routing control overhead (for example, synchronizing routing database over routers, etc.) by hierarchically partitioning the AS. However, there are few literatures addressing hierarchical partitioning schemes for link-state Internet routing protocols such as OSPF. Link-state routing protocols require an additional constraint of contiguity for each resulting partitioned area: topological constraint. Also, a subnetwork constituting a AS should not be separated into different partitioned areas. Our goal is to devlop a HC(Hierachical Configuration) method under these constraints by determining the backbone boundary. To achieve this goal, we first devise a conceptual and graphic models of a AS. Then, we formulate the HC issue upon the graph as a combinatorial problem with new additional constraints. The objective is to minimize the backbone size which is crucial to overall stable operation. Finally, we present a heuristic solution method and experiment results.