SGER: Routing and Topology for a New Internet

SGER：新互联网的路由和拓扑

• 批准号: 0731704
• 负责人: Richard Lipton
• 金额: $ 4.5万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0731704&HistoricalAwards=false
• 关键词: SGER; Routing; Topology; New; Internet

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?

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