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.
