Optimization algorithms for large self-structuring networks

As networks grow in scale and heterogeneity, hierarchical organization is inevitable. We present the case for optimal self-organization of network hierarchies. We provide a graph partitioning formulation relevant to networking but different from extant graph partitioning literature. In particular, we require that the resultant partitions be connected, a constraint that changes the character of the problem significantly. We devise a solution that consists of distinct phases for initial partitioning, refinement and post-processing, propose efficient heuristics for each phase, and evaluate them extensively on internetwork-like graphs through simulation. The results suggest that vertex trading techniques, in vogue for a number of decades in graph partitioning, are highly applicable, but multilevel techniques favored by conventional graph partitioning research may be of limited value for internetwork-like graphs. This solution can be implemented in practical networks to automatically generate Internet OSPF areas or ATM PNNI clusters.