A class of adaptive routing and link assignment algorithms for large-scale networks with dynamic topology

The authors present novel algorithms for adaptive routing and link assignment, which can be used in a large-scale network (1000-10000 nodes) with dynamic topology and stress. Special attention was given to performance (delay, throughput, and survivability) and implementation cost issues as the size of the network grows. These costs are controlled by a logical partitioning of the network into areas. The proposed class of algorithms addresses the following key issues: maintenance of up-to-date routing information in the presence of dynamics, robustness to failures that can partition areas, optimization of routing algorithm performance through multiple path routing, and optimization of network topology for performance metrics of delay, link performance, and connectivity