Collaborative Research: SING: Foundations of Next-Generation Routing

互联网的出现是计算机科学自诞生以来最深刻的焦点转移之一。传统上，计算机科学的研究主要集中在了解如何最好地设计、构建、分析和编程计算机。研究重点现在已经转移到如何最好地设计、构建、分析和运营网络以及在其上运行的分布式应用程序的问题上。要令人满意地回答这些问题，将需要开发一种类似于计算机科学研究人员已经开发的(单机)计算理论的网络计算理论(ToNC)。特别是，研究下一代网络中路由的理论基础将非常重要。这项工作将通过研究下一代路由系统的三个基本方面来补充正在进行的实验研究：(1)基于策略的域间路由(关注分布式算法机制、支付协议、解决方案概念和隐私)，(2)新的路由范例(关注不完全分布式、不需要一致状态或不使用拓扑相关寻址的协议的内在属性)，以及(3)路由协议复杂性的新度量(关注网络研究界最近提出的依赖复杂性概念)。PI在ToNC社区的形成中一直发挥着主导作用。牵头的PI是GENI科学理事会的联合主席，因此可以为GENI的社区参与铺平道路，这可能导致开发具有新功能和可证明特性的网络服务。

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.