NeTS: Small: Diverse and Resilient Beyond Paths

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