SGER: Routing and Topology for a New Internet

新互联网的路由和拓扑摘要路由是互联网的基本功能。这个项目研究的是目前人们对互联网认识上的一个主要差距。这一差距是基于一个简单但重要的观察结果。由于各种原因，这一观察结果被当前大多数关于互联网路由的算法研究所忽视。研究人员检查了这一观察结果，并展示了它如何从根本上改变我们必须如何看待互联网。这一观察提出了一些新的问题，该项目用实验和分析工具对这些问题进行了攻击。随着互联网成为我们通信基础设施不可或缺的支柱，预计该项目的更广泛影响将是可观的。观察很简单：数据包不能在任意路径上进行路由。路由器目前被限制使用仅依赖于最终目的地(例如，OSPF)的确定性规则。当前关于网络拓扑和路由算法的许多研究假设任何路径都是可能的，并且必须从这个角度重新考虑，即，仅用诸如最短路径之类的子集来替换所有路径。该项目解决了如何布线以提高可靠性并在受到如此限制的情况下实现基础图的容量的具体问题。最后，使用最短路径分析网络容量/拥塞的工具也可以指导互联网新拓扑的设计：如何设计一个最短路径拥塞/容量与任意路径所达到的网络相当的网络？

Routing and Topology for a New InternetAbstractRouting is the basic function of the internet. This project studies a major gap in the current understanding of the Internet. This gap is based on a simple but important observation. For a variety of reasons this observation has been overlooked by most of the current algorithmic research on Internet routing. The investigators examine this observation and show how it changes, in a fundamental way, how we must look at the Internet. This observation raises a number of new questions that the project attacks both with experiments and with analytic tools. With the internet becoming the indispensable backbone of our communication infrastructure, the broader impact of the project is expected to be considerable.The observation is simple: packets cannot be routed on arbitrary paths. Routers are currently constrained to use deterministic rules that only depend on the final destination (e.g., OSPF). Much of the current research on network topologies and routing algorithms assumes that any path is possible and must be reconsidered in this light, i.e., replacing all paths with only a subset such as shortest paths. The project addresses the specific questions of how to route so as to improve reliability and achieve the capacity of the underlying graph while being so constrained. Finally, tools for analyzing the capacity/congestion of a network using shortest paths can guide the design of a new topology for the internet also: how to design a network where the shortest path congestion/capacity is comparable to that achieved by arbitrary paths?