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

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

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.