A Multi-path Hybrid Routing Algorithm in Network Routing

The shortest path tree construction is essential in network routing, and the Dijkstra algorithm, which is a static routing algorithm, is widely used. When some links in a network have new weights, dynamic routing algorithms are more efficient than static routing algorithms. This is because the dynamic routing algorithms reduce redundancy by re-computing only the affected sections of the network with the changed links. However, the dynamic routing algorithms are not efficient in some situations and can increase computation time to create the shortest path tree. Therefore, hybrid routing algorithms, which reduce the total execution time of shortest path tree computation using the advantages of both static and dynamic routing algorithms, have been suggested recently. In this paper, a multi-path hybrid routing algorithm is presented that uses multi-path information to create the shortest path tree when some links have new weights. Comparisons with other routing algorithms, such as Dijkstra, Dynamic Dijkstra, and Hybrid Shortest Path Tree (HSPT), demonstrate that the multi-path hybrid routing algorithm provides better performance as the execution time decreases.