Fast hierarchical aggregation and decomposition (HAD) algorithms for optimal routing in high-speed data networks

In this research, new distributed algorithms are developed to solve optimal routing problems (ORPs) for large data networks with multiple commodities. We first discuss our new routing algorithm, which utilizes our computation localization scheme, for the networks with general topologies. The algorithm is shown to be much faster than other existing algorithms for general network topologies.; We then develop our new hierarchical aggregation/decomposition (HAD) algorithms, which can further speedup the computations for hierarchical network topologies including hierarchically clustered and hierarchically structured network topologies. Our algorithms prove to be faster, more scalable than other existing HAD based algorithms and much easier to implement.; In high-speed networks, such as ATM networks, packets could be lost while being routed to their destinations. Minimization of packet loss probabilities becomes a major concern. The ORP minimizing average network packet loss probabilities is more complicated since the ORP is a non-convex problem and the ordinary gradient projection algorithm cannot be directly used to obtain optimal routing. To solve the packet loss ORP, we developed an HAD based two-stage algorithm. The algorithm can effectively avoid the traps of local minimum caused by the non-convexity of the problem and thus, can find the true optimal solution of the ORP with high computation speed.; The implementations of our algorithms are simulated using OPNET simulation tool. OPNET is a leading networking simulation tool and is developed by MIL3, Inc. The simulation results are consistent to our theoretical analyses.