NeTS: Small: New Directions in Routing and Traffic Engineering

NeTS：小型：路由和流量工程的新方向

• 批准号: 1117161
• 负责人: Scott Shenker
• 金额: $ 30万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117161&HistoricalAwards=false
• 关键词: NeTS; Small; New; Directions; Routing

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.

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