SGER: Routing and Topology for a New Internet

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Routing and Topology for a New Internet Abstract Routing 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?