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

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

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.