BPA - A Parallel Shortest Path Algorithm for Cluster-Router

X. Zhang, J. Wu, N. Zhang, and Y. Zhao (PRC)


cluster router, shortest path, shortest path tree, parallel algorithm, complexity


To keep up with the pace of fast development of Internet, cluster architecture has been proposed for next generation core routers. In a cluster router, parallel computation is expected. Computing shortest path tree (SPT) is a fundamental problem implementing OSPF, which is one of the most popular routing protocols. This paper presents a parallel algorithm BPA (Branching Parallel Algorithm) for computing SPT, analyzes the performance of BPA, and finally validates the BPA performance by experiments

Important Links:

Go Back