Optimal routing is essential for efficient operations of computer networks over a large geographical area. If there is a sudden large disturbance to the network, severe congestion can occur, and as a result, the best existing optimal routing algorithm may take a large number of iterations to steer the routing to a reasonable delay level. The aggregation based gradient projection algorithm studied in this project has demonstrated speed-up ratios over the existing best routing algorithm ranging from infinity to 3300% - 700%. This kind of speed-up result is worthy of further investigation for possible eventual implementation in large real networks. The idea of exploiting hierarchical aggregation and disaggregation-decomposition (HAD) is the cornerstone of the project. Fast computation usually comes from imitating how nature solves its own difficult computation problems.. For example, several lines of anatomical and physiological evidence suggest that information processing in the cortex is fundamentally hierarchical in nature. Intimately related to the concept of hierarchy are the concepts of good organization, aggregation (or summarized computation, an almost necessary mechanism for solving large problems) disaggregation (for accurate solution, details are needed), and decomposition (the classical idea of divide-and-conquer). The HAD algorithm is the result of integrating the related concepts into a generic computational system. The project aims to develop the HAD based algorithms for both conventional packet switching and ATM networks, to simulate the developed algorithms in a realistic network environment and to exploit the speed advantage to the fullest extent, and to establish the theoretical speed-up complexity for the HAD algorithm. This project is a joint project with Wei K. Tsai of the University of California, Irvine.
