Implementation and performance evaluation of a multi-path incremental shortest path algorithm in quagga routing software

Abstract — In this paper a multi-path incremental shortest path algorithm has been proposed allowing a quick reconfiguration of a routing table when a network topological change occurs. After evaluating the algorithm complexity, we have implemented it in Quagga, one of the most popular open source routing software. In order to evaluate the algorithm performance, we have realized a test-bed allowing the shortest path computation time to be calculated for any network. The results obtained show that the algorithm allows the shortest path computation time to be reduced of about the 97 % with respect to the case in which the classical Dijkstra’s algorithm is adopted