A framework for performance characterization and enhancement of the OSPF routing protocol

Open Shortest Path First (OSPF) is a popular Interior Gateway Protocol widely used inside large IP routing domains. Recent studies have shown that the time consumed by local SPF computations must be controlled to achieve millisecond convergence time. This paper presents the authors' experience in measuring and improving the performance of the OSPF routing protocol software. First, we propose a reusable performance characterization framework for routing performance study, which allowed us to perform reproducible experiments in a controlled environment with different network topologies and workloads. Then we present relative performance of several low-level optimizations suggested to optimize route computation code and data structures. Finally, we present the performance benefit of algorithm-level optimization using Incremental Shortest Path First algorithm (ISPF). We are able to achieve substantial gains in performance by using ISPF, more than what is possible by employing techniques for code optimization and using efficient data structures to implement Dijkstra's SPF (DSPF) algorithm.