Traditionally, networks are scaled to very large size through hierarchy: routing is performed on higher level aggregates and subsequently at finer granularity. The consequences are inefficiency in the form of inflated path lengths, and the use of location-dependent addresses which complicate management, mobility, and multihoming. Routing on location-independent "flat names" can solve these problems and is independently useful to support secure, self-certifying identifiers. But no previously proposed protocols exist for scalable, efficient routing directly on flat names. This project is developing distributed compact routing (DCR) protocols which route on flat names while guaranteeing scalability and efficiency for arbitrary networks. Building on recent theoretical advances in the area of compact routing, DCR addresses key challenges including autonomous distributed operation, congestion, and heterogeneity. The project is applying these techniques to Internet routing, mobile ad hoc networks, and content-centric networks. In addition, the project is studying recent systems-oriented proposals to scale Internet routing based on separating the "core" of the Internet from the edges, providing firm theoretical footing by determining when they can improve scalability with little loss of network efficiency. The results of this project will significantly improve scalability, mobility, and manageability in the Internet and other networks, bridging a gap between promising theoretical results and emerging practical needs. Results will be disseminated through publications and presentations, a public software release, and graduate and undergraduate courses.
This project explored provably-efficient network routing for giant networks, improving techniques for the Internet and leading to impact on computer science theory and real-time search in giant social networks. When we send a text message to a friend or search Google or start watching a movie, we are communicating with another computer and often many other computers that can be located anywhere in the world. Behind the scenes, the Internet figures out, within hundreds of milliseconds or less, where in the world this device is located and how to route messages there. How does the Internet find routes for messages through a network composed of many millions of network routers and billions of computers? Traditionally, network routing systems scale to large size with a technique called hierarchical routing: routing is performed on higher level aggregates (like ISPs) and subsequently at finer granularity. However, this leads to inefficiency in the form of inflated path lengths that slow Internet communications, and the use of location-dependent addresses which complicate network management, mobility, and multihoming (use of multiple Internet providers). This project began with the goal of developing efficient routing for large networks, with mathematical guarantees on near-optimal paths and system scalability. The project also led to exciting and initially-unexpected directions, ultimately producing research results in three areas. First, the project developed new algorithms and systems for scalable routing on location-independent names, similar to today's DNS names, with guaranteed near-optimal path length and minimal routing state. The design built on theoretical advances in the area of compact routing, and was the first to realize these guarantees in a dynamic distributed setting. Second, the project's work on practical scalable routing resulted in opening a new line of theory research. Past theoretical work had dealt with an understanding of the scalability of routing in worst-case networks. But essentially all real-world networks have a special structure called sparsity: each node in the network is connected to only a tiny fraction of the others. Routers, for example, typically have tens or hundreds of connections, not millions; Facebook users have hundreds of friends, not hundreds of millions. This project showed that in sparse graphs, the efficiency limits set by past theory work can be broken, realizing important gains. Third, these ideas led to an unexpected new application domain. Computing shortest paths is a fundamental primitive for several social network applications including socially-sensitive ranking, location-aware search, social auctions and social network privacy. Since these applications compute paths in response to a user query, the goal is to minimize latency while maintaining feasible memory requirements. This project showed that the novel scalable routing techniques above, coupled with new data structure and algorithmic mechanisms, allow computation of paths that are nearly always exact shortest paths, within microseconds per query. In addition to these research results, the project produced broader impact: professional development of several undergraduate and PhD researchers, a course module bringing fundamental routing theory to a computer networking audience, and a number of publications in both top computer networking venues and top computer science theory venues. The path-finding technology has been adopted by a social networking company.
