The goal of this project is to develop algorithms that will produce good solutions for dynamic routing and network-topology problems in the design of large communication networks. The study of dynamic routing will use Segall's dynamic network model and will emphasize aspects of dynamic routing that are not usually considered. These aspects include a new "worst-case" cost functional, reducing the routing problem to a purely scheduling problem by restricting the topology of the network, and considering suboptimal routing algorithms that have low time- complexities. The principal investigator will analytically evaluate heuristic design algorithms for the Capacitated Minimal Spanning Tree Problem as well as other local-access-network topology design problems. He will focus on deriving probabilistic properties of design algorithms, which should provide valuable insights into the design problems and conditions under which the design algorithms perform well.
