Fast and flexible tool for the generation, maintenance and evaluation of hierarchical structures in diverse networks

The size and dynamics of modern network environments prohibit the application of protocols in large flat networks due to their inability to scale. Hierarchy has proven a successful scaling tool, dividing the network into multiple subsets (domains), allowing aggregation and abstraction of changing protocol control information (e.g., routing updates). Contrarily, if hierarchy is not applied then the overhead can effectively cripple network performance. There are numerous hierarchy formation approaches, which are mainly based on particular heuristics (e.g., creating a connected dominating set). These heuristics provide hierarchical structures that comply with some specific requirements, but when diverse requirements or conditions are imposed completely different heuristic must be designed and applied. We have built a more general hierarchy formation mechanism that provides a common and flexible framework for the generation and maintenance of hierarchies. The framework is suited to any input environment and can optimize any set of performance objectives. This framework has been implemented in the form of a software tool, which runs powerful hierarchy optimization algorithms, simulates robust distributed hierarchy maintenance algorithms and dynamic network environments, and provides powerful visualization of the hierarchy and performance. This tool can also assess the quality of the hierarchical structures with respect to the design objectives. The paper describes each of the functional components of the tool and their effectiveness in forming, maintaining, and evaluating structures that satisfy diverse hierarchy formation objectives.