NeTS: Small: Diverse and Resilient Beyond Paths

随着互联网应用的进步及其对带宽的永无止境的需求，今天的网络在规模和复杂性方面都迅速增长。不断增长的规模和复杂性也极大地增加了失败的可能性。在当今的大型数据中心中，情况尤其如此。因此，设计具有高容量和内置弹性的网络是当务之急。路由是网络的核心，因为它决定是否转发数据包以及将数据包转发到何处。因此，它在确保网络弹性方面至关重要。支撑当今大部分网络基础设施的IP/MPLS(网际协议/多协议标签交换)网络中的传统路由协议主要是基于路径的和反应性的。还提出了各种IP/MPLS(主动式)快速重路由机制；但它们中的大多数只能处理单个链路故障。多个链路故障的组合特性使得大多数现有的基于路径的快速重路由方法无效；并且随着链路/节点故障数量的增加，其复杂性迅速增加。为了获得高的网络容量、可用性和可靠性，需要新的范式转换方法来发展未来多样化和有弹性的路由系统。除了路径之外，该项目倡导一种新的路由范例--称为预订单路由--它绕过了传统的基于路径的路由方案的限制，有效地利用具有丰富拓扑的网络中固有的拓扑多样性进行多样化和弹性的路由，同时满足应用或流的服务质量要求(例如，带宽和延迟)。与传统的基于路径的路由不同，在所提出的经由预序的路由范例下，没有明确指定用于路由或转发的路径；相反，可以使用包含在路由预序中的任何连接节点序列，从而规避了路径的刚性和脆弱性限制，同时也避免了路径枚举所带来的“组合诅咒”挑战。因此，在设计上，通过预订单进行路由具有内置的弹性和负载平衡功能。更广泛的影响：如果成功，本研究项目中提出的改变范式的新路由框架将提供互联网服务和关键物理基础设施所需的高度多样性和弹性。所有这些都将为用户、服务提供商和整个社会带来重大好处。PI将积极地让本科生--特别是女学生和代表性不足的少数族裔--参与研究项目，例如，通过NSF REU补助金以及高级设计课程和PI所在机构的本科生研究机会计划(UROP)。主计处将利用软件定义网络(SDN)平台在公共领域发布通过预购实现的路由，以供广泛分发和采用，并参与其他外联活动。

With advances in Internet applications and their insatiable demands for bandwidth, today's networks have grown rapidly both in scale and complexity. The growing scale and complexity also drastically increase the probability of failures. This is particularly the case in today's huge data centers. It is thus imperative that networks be designed with high capacity and with built-in resiliency. Routing is central to networking, as it determines whether and where packets are to be forwarded. It is therefore essential in ensuring network resiliency. Conventional routing protocols in IP/MPLS (Internet Protocol/Multiple Protocol Label Switching) networks that underpin much of today's networking infrastructure are primarily path-based and reactive. Various IP/MPLS (proactive) fast rerouting mechanisms have also been proposed; but most of them can only handle a single link failure. The combinatorial nature of multiple link failures renders most existing path-based fast rerouting approaches ineffectual; and their complexity grows rapidly, as the number of link/node failures increases. In order to achieve high network capacity, availability and reliability, new paradigm-shifting approaches are needed for the development of future diverse and resilient routing systems. Going beyond paths, this project advocates a novel routing paradigm -- dubbed routing via preorders -- which circumvents the limitations of conventional path-based routing schemes to effectively take advantage of topological diversity inherent in a network with rich topology for diverse and resilient routing, while at the same time meeting the quality-of-service requirements (e.g., bandwidth and latency) of applications or flows. Unlike conventional path-based routing, under the proposed routing via preorders paradigm no paths are explicitly specified for routing or forwarding; instead any sequence of connected nodes contained in the routing preorder can be used, thereby circumventing the rigidity and fragility limitations of paths while also avoiding the "combinatorial curse" challenge posed by path enumeration. Hence by design, routing via preorders has built-in resiliency and load-balancing capabilities. Broader Impact: If successful, the paradigm-shifting new routing framework advanced in this research project will provide the high diversity and resiliency demanded by the Internet services and critical physical infrastructures. All of these will bring significant benefits to users, service providers and society at large. The PI will actively involve undergraduate students -- especially female students and underrepresented minorities in the research project, e.g., via NSF REU grants as well as senior design courses and the Undergraduate Research Opportunity Program (UROP) at the PI's institution. The PI will release the implementation of routing via preorders using the software-defined networking (SDN) platform in public domains for wide distribution and adoption, and engage in other outreach activities.