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

研究启动：大型通信网络的动态路由和拓扑设计算法

• 批准号: 8809410
• 负责人: Galen Sasaki
• 金额: $ 6万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-09-01 至 1991-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8809410&HistoricalAwards=false
• 关键词: Research; Initiation; Dynamic; Routing; Topology

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.

这个项目的目标是开发算法， 为动态路由和网络拓扑提供良好的解决方案 大型通信网络设计中的问题。 的 动态路由研究将采用Segall的动态网络模型 并将强调动态路由中不重要的方面 通常认为。 这些方面包括新的"最坏情况" 成本泛函，将路由问题简化为纯粹的 调度问题通过限制网络的拓扑结构， 并考虑具有低时间的次优路由算法， 复杂性 主要研究者将分析评估启发式 最小生成树的设计算法 问题以及其他本地接入网络拓扑设计 问题 他将专注于推导的概率属性， 设计算法，这应该提供有价值的见解， 设计问题和设计条件 算法表现良好。