On the Efficiency of Hierarchical Network Design

V. Pasias, D.A. Karras (Greece), and R.C. Papademetriou (UK)


Hierarchical Network Design Algorithm, Integer Linear Programming (ILP), Heuristic Algorithms, routing, capacity planning, survivability.


This paper presents a novel heuristic algorithm for the design of survivable hierarchical networks called Hierarchical Network Design Algorithm (HNDA). HNDA addresses all necessary stages for the design of hierarchical networks, including the design of access and transit subnetworks(s) as well as the topology optimisation of the designed subnetworks(s). Network survivability is also supported with the establishment of one or more node/link disjoint backup protection paths. HNDA is capable of designing medium and large-scale networks at polynomial time. HNDA were compared with an analogous composite optimisation model through a series of tests. The results indicate that as regards design costs the performance of HNDA was very close to this of the equivalent optimisation model. The solution times for HNDA were essentially smaller especially when the number of the candidate access and/or transit switches became large.

Important Links:

Go Back