NeTS: Small: New Directions in Routing and Traffic Engineering

路由可以说是网络最基本的方面，因为它回答了一个基本问题：如何在路由器或交换机中放置适当的状态，以便数据包可以从源传输到目的地？有大量关于路由的文献，涵盖了许多主题（域内和域间，有线和无线，融合和策略振荡等），并且路由器供应商多年来一直在磨练其路由实现。 在所有这些学术和商业工作之后，人们可能会认为关于路由的重要性不会有什么新的东西，并且所有当前的工作都将涉及对算法和实现的小的、渐进的改进。然而，有两个相互冲突的趋势正在改变路由的使用环境，这需要新一轮的路由研究：可靠性要求：由于网络越来越多地用于关键服务（医院、金融机构等），对网络的可靠性期望正变得更加严格即，“五个九”的可靠性）。 路由负责引导流量绕过故障（即，故障恢复）和避免热点（即，网络规模：网络规模正在快速增长，一种新的网络类型--拥有数十万台主机和数百万台虚拟机的网络中心--正在以前所未有的速度突破扩展极限。 在所有路由算法中，由于它们本质上是分布式一致性算法，因此收敛时间（用于响应故障和热点）和/或路由开销（就路由消息的数量和大小而言）随着大小而增加。这两个发展的结果是，路由算法被要求在更困难的任务上做得更好（在可靠性方面）（因为网络规模和复杂性的增加）。因此，无论是商业界还是学术界都开始了新一轮的路由研究。这些努力首先产生了几种ad hoc重路由方法（如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.