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

点击翻译按钮获取中文摘要

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.