Collaborative Research: SING: Foundations of Next-Generation Routing

互联网的出现是计算机科学自诞生以来最深刻的转变之一。传统上，计算机科学研究主要集中在理解如何最好地设计、构建、分析和编程计算机。现在，研究的焦点已经转移到如何最好地设计、构建、分析和操作网络以及在其上运行的分布式应用程序。要圆满地回答这些问题，就需要发展一种网络计算理论（ToNC），它类似于计算机科学研究人员已经开发的（单机）计算理论。特别是，研究下一代网络中路由的理论基础将是重要的。这项工作将通过检查下一代路由系统的三个基本方面来补充正在进行的实验研究：(1)基于策略的域间路由（关注分布式算法机制、支付协议、解决方案概念和隐私），(2)新的路由范式（关注非完全分布式、不需要一致状态或不使用拓扑相关寻址的协议的内在属性），以及(3)路由协议复杂性的新度量（关注网络研究社区最近提出的依赖复杂性的概念）。PIs一直在tonc社区的形成中发挥主导作用。首席PI是GENI科学委员会的联合主席，因此他的定位是为tonc社区参与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.