Enhancements and optimizations of OSPF routing protocol for fast convergence

It is important for OSPF to have quick convergence time to provide good service to real time applications. In this thesis, we provide a survey of recent efforts on achieving fast OSPF convergence. In addition, we also propose some schemes to achieve faster OSPF convergence by scheduling the routing table calculations more efficiently. OSPF routers typically schedule routing table calculation which is one of the major steps in the convergence process using hold time based schemes. The schemes are used to limit the number of routing table calculations that will be performed during the convergence period. We modify the exponential back-off hold time scheme to improve its performance when small value is used for the initial hold time parameter in comparison to inter-LSA arrival time where an LSA (link-state advertisement) is a control message that describes a topology change. In the hold time based schemes, it is difficult to find values optimum for any topology change scenarios. Thus, we also propose a scheme called LSA Correlation that uses a different approach than the hold time based schemes.;The LSA Correlation scheme schedules routing table calculation upon identification of a topology change instead of upon hold timer expiration in the hold time based schemes. A topology change is identified by the scheme through correlating the content of individual LSAs that are received at a router due to topology change(s). We develop analytical and simulation models for the hold time and LSA Correlation schemes to evaluate their performance. The performance of the schemes was evaluated in cases of isolated and large scale topology change scenarios. The analysis on the analytical and simulation models have shown that the modified exponential hold time scheme require less routing table calculations with small initial hold time values. The analysis also shows that the LSA Correlation scheme requires less routing table calculations and has smaller convergence delays compared to the hold time based schemes where convergence delay refers to the time between receipt of the first LSA and the time when final routing table calculation is performed.