A new HAD algorithm for optimal routing of hierarchically structured data networks

In this paper a new algorithm based on aggregation/disaggregation and decomposition/composition (HAD) scheme is proposed to solve the optimal routing problems (ORP) for hierarchically structured networks. Our algorithm has two major differences with the existing HAD algorithms for hierarchically clustered networks: 1. Our algorithm works with networks which are more general than networks with clustered structure; 2. Our algorithm parallelizes the computations for different commodities so that it speeds up with a parallel time complexity of O(mlog² (n)), which is much less than O(Mlog²(n)) needed for the existing HAD algorithms, for an n-node network with M commodities. Here, m is a positive number usually much smaller than M and is a function of the patterns of all the commodities. The implementation of the algorithm for a 200-node network is simulated using the OPNET simulation package