Research Initiation: Dynamic-Routing and Topology-Design Algorithms for Large Communications Networks

该项目的目标是开发算法，为大型通信网络设计中的动态路由和网络拓扑问题提供良好的解决方案。动态路由的研究将使用西格尔的动态网络模型，并将强调动态路由通常不被考虑的方面。这些方面包括一个新的“最坏情况”成本函数，通过限制网络拓扑将路由问题减少为纯粹的调度问题，并考虑具有低时间复杂性的次优路由算法。首席研究员将分析评估启发式设计算法，以解决有能力最小生成树问题以及其他本地访问网络拓扑设计问题。他将专注于推导设计算法的概率属性，这将为设计问题和设计算法良好运行的条件提供有价值的见解。

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.