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.
