Framework for performance engineering of OSPF software

The performance of the Open Shortest Path first (OSPF) routing protocol software is presented, which includes measuring its performance, analysing the results, proposing solutions for improvement and evaluating their effect. First, a reusable framework for evaluating the performance of routing software is proposed, which allows to perform reproducible experiments in a controlled environment with different network topologies. Then, performance bottlenecks are identified and the relative performance of several low-level optimisations suggested to improve the route computation code and data structures is discussed. In addition, the design and implementation of an algorithm-level optimisation is presented, using the Incremental Shortest Path First (ISPF) algorithm, and its performance benefits are then presented. Substantial gains in performance are achieved by using ISPF, more than what is possible by employing techniques for code optimisation and by using efficient data structures to implement Dijkstra's SPF algorithm. Finally, the effect of topological change on the size of the affected subtree is investigated, and it is found that most of the time a topological change affects a small number of nodes in an OSPF area, causing a small number of route updates in the routing table and consequently, a smaller execution time for ISPF.