The emergence of the Internet is one of the most profound shifts in focus in Computer Science since its inception. Traditionally, Computer-Science research has focused primarily on understanding how best to design, build, analyze, and program computers. Research focus has now shifted to the question of how best to design, build, analyze, and operate networks and the distributed applications that run on top of them. Satisfactorily answering these questions will require the development of a Theory of Networked Computation (ToNC) that is analogous to the Theory of (single-machine) Computation that Computer-Science researchers have already developed. In particular, it will be important to investigate the theoretical foundations of routing in next-generation networks. This work will complement ongoing experimental research by examining three foundational aspects of next-generation routing systems: (1) Policy-based, interdomain routing (focusing on distributed algorithmic mechanisms, payment protocols, solution concepts, and privacy), (2) New routing paradigms (focusing on the intrinsic properties of protocols that are not fully distributed, do not require consistent state, or do not use topology-dependent addressing), and (3) New measures of the complexity of routing protocols (focusing on the notion of dependency complexity recently put forth in the networking-research community). The PIs have consistently played a leading role in ToNC-community formation. The lead PI is the co-chair of the GENI Scientific Council and is thus positioned to pave the way for ToNC-community participation in GENI, which could result in the development of network services with novel functionality and provable properties.
The emergence of the Internet is one of the most profound shifts in focus in Computer Science since its inception. Traditionally, Computer-Science research has focused primarily on understanding how best to design, build, analyze, and program computers. Research focus has now shifted to the question of how best to design, build, analyze, and operate networks and the distributed applications that run on top of them. Satisfactorily answering these questions will require the development of a Theory of Networked Computation that is analogous to the Theory of (single-machine) Computation that Computer-Science researchers have already developed. This project focuses on the algorithmic and programming-language foundations of routing in next-generation networks. Yale PhD student Andreas Voellmy, in collaboration with Vijay Ramachandran, and Paul Hudak, developed the programming language Nettle, which allows network operators to specify network routing policies at a high-level, and a compiler from Nettle to configurations for XORP, an open-source, extensible routing platform. The Internet is designed to ``route around failures,'' and thus the key to increasing availability lies in improving its ability to do so. The traditional way to route around failures is to have the routing system detect the failure and then compute an alternative set of paths. However, this approach involves substantial ``convergence time'' after each failure; the route recomputations cause substantial delay, and these delays will only increase as networks get larger. A more promising approach is to precompute these alternate paths, providing multiple paths to each destination that can be used in two ways. Yale Professor Joan Feigenbaum, in collaboration with Michael Schapira and Scott Shenker, put forth a new approach called "Multiple Paths Without Packet Marking'' (MPWPM) that may be able to handle load balancing as well as failures. Professor Feigenbaum also worked closely with Ellen Zegura of Georgia Tech and John Byers of Boston University on formulating the part of the agenda for NSF's program in Network Science and Engineering (NetSE) that deals with the overlap of theory and networking. Finally, Feigenbaum co-taught a course with Yale Economics Professor Dirk Bergemann entitled "Economics and Computation," in which routing and network formation is one of the main themes.
