Research Initiation Award: Compact Schemes for Message Routing in Dynamic Networks

研究启动奖：动态网络中消息路由的紧凑方案

• 批准号: 8808574
• 负责人: Ravi Janardan
• 金额: $ 3.55万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-08-01 至 1991-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8808574&HistoricalAwards=false
• 关键词: Research; Initiation; Award; Compact; Schemes

This research focuses on the problem of succinctly storing shortest, or near-shortest, path routing information in a distributed network which experiences changes in topology and edge costs. The emphasis is on both identifying such routing schemes and efficient algorithms for constructing them. Three interrelated problems are investigated: 1. Design of compact routing schemes that incrementally adapt to changes by computing a small amount of additional information, which is then used to restore good routings. 2. Design of compact schemes that route messages along two or more node-disjoint paths of low total cost, thus making the routings resilient to faults. 3. Investigation of an interval property of graphs that allows very succinct encoding of shortest paths. This finds application in the updating of routing information when edge costs change. The techniques used will be based, in part, on naming nodes appropriately and on interesting properties of distances in graphs. Thus, in addition to yielding space-efficient routing schemes, this research will also provide new insights into the succinct encoding of information within node names and on the structure of shortest paths.

本研究的重点是问题的简洁存储最短，或 一种分布式网络中的近最短路径路由信息，该分布式网络 经历拓扑和边缘成本的变化。重点是两者 识别这样的路由方案和有效算法， 建造它们。 研究了三个相互关联的问题： 1. 设计紧凑的路由方案，逐步适应 通过计算少量的附加信息来改变， 然后用于恢复良好的路由。 2. 设计紧凑的方案，将消息沿着两个或多个 节点不相交路径的总成本低，从而使路由 对错误有弹性。 3. 研究了图的区间性质， 最短路径的简洁编码。 这适用于 当边成本改变时更新路由信息。 所使用的技术将部分基于命名节点 适当地和有趣的性质的距离图。 因此，除了产生空间高效的路由方案之外， 研究还将提供新的见解的简洁编码 节点名称中的信息和最短路径的结构。