NeTS: Small: New Directions in Routing and Traffic Engineering

路由可以说是网络中最基本的方面，因为它回答了一个基本问题：如何在路由器或交换机中设置适当的状态，以便数据包能够从源传输到目的地？有大量关于路由的文献，涵盖了许多主题（域内和域间，有线和无线，收敛和策略振荡等），路由器供应商已经打磨了他们的路由实现多年。在所有这些学术和商业工作之后，人们可能会期望在路由方面没有什么重要的新内容，所有当前的工作都将涉及对算法和实现的小而渐进的改进。然而，有两种相互冲突的趋势正在改变路由使用的背景，这需要新一轮的路由研究：可靠性要求：由于网络越来越多地用于关键服务（医院、金融机构等），对网络的可靠性期望变得更加严格，即可靠性的“五个九”。路由负责引导流量绕过故障（即故障恢复）并避免热点（即负载分配），因此所需的可靠性提高必须来自改进路由协议中嵌入的故障恢复和负载分配机制。网络规模：网络正以快速的速度增长，一种新的网络——数据中心，它可以拥有数十万台主机和数百万台虚拟机——正在前所未有地推动扩展限制。在所有路由算法中，因为它们本质上是分布式一致性算法，收敛时间（用于响应故障和热点）和/或路由开销（就路由消息的数量和大小而言）随着大小而增加。这两个发展的结果是，路由算法被要求在更困难的任务上做得更好（就可靠性而言）（因为网络规模和复杂性的增加）。因此，商业界和学术界都开始了新一轮的路由研究。这些努力首先产生了几种临时路由方法（如MPLS快速路由和ECMP），然后集中精力开发多路径路由方法（如路径拼接和各种其他方法）。然而，所有这些开发都是在传统路由方法的基础上进行改进的，传统路由方法构建了从源到目的地的单一路径。这些机制显著提高了网络的可靠性，但它们并没有告诉我们如何将更有效的故障恢复和负载分配纳入路由算法的核心基础。最近，我们（和其他人一起）提出了一种新的路由范式，它将路由的基本输出从路径更改为有向无环图（DAG）。这种新方法在这里被称为沿dag路由（RAD），它自动为本地故障恢复和负载分配提供多条路径。这允许RAD在没有任何全局路由重新计算以响应故障或热点的情况下，保证连通性（只要图是连接的）并提供最佳负载分配（在简单的单目的地流量模型中）。该项目从设计、仿真、实现和理论等多个角度研究了RAD方法。我们的目标是将这种新的路由范式建立在坚实的科学基础上。更广泛的影响：商业和政府迫切需要提高可靠性和易于管理的路由算法。这个提议的项目将产生基于商业路由硬件（使用OpenFlow接口）的新路由和流量工程方法的原型，可用于在商业环境中测试这些想法。这可能会对数据中心网络的实现方式产生重大影响，并更普遍地提高网络可靠性。在这方面，已经与路由器供应商进行了有希望的初步讨论。

Routing is arguably the most fundamental aspect of networking, since it answers the basic question: how do you place the appropriate state in routers or switches so that packets can travel from source to destination? There is a huge literature on routing, covering many topics (intradomain and interdomain, wireline and wireless, convergence and policy oscillations, etc.), and the router vendors have been honing their routing implementations for many years. After all this academic and commercial work, one might expect that there would be little new of fundamental importance to say about routing, and that all current work would involve small, incremental improvements to algorithms and implementations.However, there are two conflicting trends that are changing the context in which routing is being used, and which necessitate a new round of routing research:Reliability requirements: Because networks are being increasingly used for critical services (hospitals, financial institutions, etc.), the reliability expectations for networks are becoming more stringent i.e., 'five nines' of reliability). Routing is responsible for directing traffic around failures (i.e., failure recovery) and avoiding hotspots (i.e., load distribution), so the required increases in reliability must come from improving the failure recovery and load distribution mechanisms embedded in routing protocols.Network size: Networks are growing at a rapid pace, and a new class of networks - datacenters, which can have hundreds of thousands of hosts and millions of VMs - are pushing the scaling limits as never before. In all routing algorithms, because they are essentially distributed consistency algorithms, the convergence times (for responding to failures and hotspots) and/or the routing overhead (in terms of the number and size of routing messages) increase with size. The upshot of these two developments is that routing algorithms are being asked to do a better job (in terms of reliability) on a harder task (because of the increases in network size and complexity). As a result, both the commercial world and the academic community have embarked on a new round of routing research. These efforts first produced several ad hoc rerouting methods (such as MPLS Fast Reroute and ECMP) and then concentrated on developing multipath routing methods (such as Path Splicing and a variety of other approaches). However, all of these developments are retrofitted on top of the traditional approach to routing, which builds a single path from the source to the destination. These mechanisms significantly improve the reliability of networking, but they do not tell us how to incorporate more effective failure recovery and load distribution into the core foundation of routing algorithms.More recently, we (along with others) have proposed a new routing paradigm, one that changes the basic output of routing from a path to a directed acyclic graph (DAG). This new approach, which here will be called Routing Along DAGs (RAD), automatically provides multiple paths for local failure recovery and load distribution. This allows RAD to, without any global route recomputations in response to failures or hotspots, guarantee connectivity (as long as the graph is connected) and provide optimal load distribution (in a simple single-destination traffic model). This project is investigating the RAD approach from many angles: design, simulation, implementation, and theory. The goal is to have a put this new routing paradigm on a firm scientific footing.Broader Impacts: There is a pressing commercial and governmental need for increased reliability and easy-to-manage routing algorithms. This proposed project will produce prototypes of new routing and traffic engineering approaches built on commercial routing hardware (using the OpenFlow interface) that could be used to test these ideas in commercial settings. This could have a significant impact on how datacenter networking is done, and more generally improve network reliability. Promising preliminary discussions have already been held with router vendors in this regard.