NeTS-NBD: Fast Convergence to Topology Changes in Link State Routing Protocols

NeTS-NBD：链路状态路由协议中拓扑变化的快速收敛

• 批准号: 0520064
• 负责人: Mukul Goyal
• 金额: $ 13万
• 依托单位: University of Wisconsin-Milwaukee
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0520064&HistoricalAwards=false
• 关键词: NeTS; NBD; Fast; Convergence; Topology

Link state routing protocols such as OSPF and IS-IS, using shortest path first (SPF) forwarding, are the most widely deployed Interior Gateway Protocols in the Internet today. These protocols can achieve fast convergence to a topology change by flooding the Link State Advertisements (LSAs) declaring the change throughout the network. Each router in the network updates its routing table by doing an SPF calculation on receiving a new LSA. In order to reduce the processing load on the routers, the protocol implementations typically limit the frequency of SPF calculations thereby delaying the router's convergence to the topology change(s). Fast convergence to the topology changes is an absolute necessity in the future networks but limiting the processing load on the routers is also important for routing stability. In this proposal, we present a simple and elegant solution, called LSA Correlation, that can help achieve fast convergence to a topology change with at most two SPF calculations per change. A topology change results in the generation of several new LSAs. The simple idea is to correlate the new LSAs to identify the topology change. Once the topology change has been identified, an SPF calculation can immediately be performed. Thus, there is no need for limiting the SPF calculations for isolated topology changes and any artificial delays in the convergence process are removed.Intellectual Merit: Both fast convergence to topology changes and routing stability are important requirements of modern networks but so far have been viewed to be at odds with each other. The proposed scheme, LSA Correlation, meets both requirements in a simple and elegant manner. LSA Correlation is simple to implement and has low time complexity. Most of the correlation processing may already be happening in the protocol implementations. Moreover, LSA Correlation is easy to deploy and can work in cooperation with other schemes to speed up the failure recovery in IP networks. Topology change identification with LSA Correlation allows large-scale topology changes to be handled differently than isolated topology changes. While fast convergence is desirable for isolated changes, it is important to limit the SPF calculations during large-scale topology changes. Finally, the subevents used in the correlation process can also be used to detect pathological situations like link flaps. The proposal also involves a comprehensive experimental evaluation of the convergence performance and processing requirements of different traditional ways to limit the SPF calculations and the proposed LSA Correlation scheme. Multiple evaluation methods (testbed experiments for smaller topologies and simulations for big topologies) will help avoid errors while real network topologies and a wide range of topology change scenarios will create realistic situations for the experiments.Broader Impacts: The current design, implementations and deployment practices of OSPF protocol leave a lot to be desired when viewed in context of modern requirements. The dilemma between fast convergence and routing stability, rigid hub-and-spoke architecture for OSPF areas, apparent lack of scalability to very large networks, ad hoc assignment of link weights and lack of clear understanding about the relationship between the network topology and routing protocol performance are some of the factors that need careful consideration. The proposed work represents a small yet important step in overhauling the protocol for the next generation Internet. In a different context, funding of this proposal will go a long way in supporting the fledgling research in computer networks at University of Wisconsin - Milwaukee.

使用最短路径优先（SPF）转发的链路状态路由协议（如OSPF和IS-IS）是当今Internet中部署最广泛的内部网关协议。这些协议可以通过在整个网络中泛洪声明拓扑变化的链路状态通告（LSA）来实现对拓扑变化的快速收敛。网络中的每台路由器在收到新的LSA时都会进行SPF计算，从而更新其路由表。为了减少路由器上的处理负载，协议实现通常限制SPF计算的频率，从而延迟路由器对拓扑变化的收敛。在未来的网络中，快速收敛到拓扑变化是绝对必要的，但限制路由器上的处理负载对于路由稳定性也很重要。在这个提案中，我们提出了一个简单而优雅的解决方案，称为LSA相关性，可以帮助实现快速收敛到拓扑变化，每次变化最多两次SPF计算。拓扑更改会导致生成多个新的LSA。简单的想法是关联新的LSA以识别拓扑变化。一旦识别出拓扑变化，就可以立即执行SPF计算。因此，没有必要限制SPF计算孤立的拓扑结构的变化和收敛过程中的任何人为的延迟被删除。智力优点：快速收敛到拓扑结构的变化和路由的稳定性是现代网络的重要要求，但到目前为止，已被视为不一致。所提出的方案，LSA相关，满足这两个要求，在一个简单而优雅的方式。LSA相关性实现简单，时间复杂度低。大多数相关处理可能已经在协议实现中发生。此外，LSA相关性易于部署，并可以与其他方案合作，以加快IP网络中的故障恢复。通过LSA相关性进行拓扑更改识别，可以以不同于孤立拓扑更改的方式处理大规模拓扑更改。虽然快速收敛对于孤立的更改是理想的，但在大规模拓扑更改期间限制SPF计算也很重要。最后，在相关过程中使用的子事件也可以用于检测病理情况，如链接皮瓣。该提案还涉及对不同传统方法的收敛性能和处理要求的综合实验评估，以限制SPF计算和所提出的LSA相关方案。多种评估方法（小拓扑和模拟大拓扑的试验台实验）将有助于避免错误，而真实的网络拓扑和广泛的拓扑变化的情况下，将创建现实的情况下experiments.Broader的影响：当前的设计，实施和部署的OSPF协议的做法留下了很多需要在现代的要求的上下文中查看。快速收敛和路由稳定性之间的困境，刚性的轴辐式结构的OSPF区域，明显缺乏可扩展性非常大的网络，ad hoc分配的链路权重和缺乏清晰的理解网络拓扑结构和路由协议性能之间的关系是一些需要仔细考虑的因素。这项拟议中的工作代表了为下一代互联网彻底改革协议的一个小而重要的步骤。在不同的背景下，这项提案的资金将大大有助于支持威斯康星州-密尔沃基大学的计算机网络研究。