New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2

This paper proposes a parallel shortest path-searching algorithm and implements it on a newly structured parallel reconfigurable processor, DAPDNA-2 (IPFlex Inc). Routing determines the shortest paths from the source to the ultimate destination through intermediate nodes. In open shortest path first (OSPF), Dijkstra´s shortest path algorithm, which is the conventional one, finds the shortest paths from the source on a program counter-based processor. The calculation time for Dijkstra´s algorithm is O(N²) when the number of nodes is N. When the network scale is large, calculation time required by Dijkstra´s algorithm increases rapidly. It´s very difficult to compute Dijkstra´s algorithm in parallel because of the need for previous calculation results, so Dijkstra´s algorithm is unsuitable for parallel processors. Our proposed scheme finds the shortest paths using a simultaneous multi-path search method. In contrast with Dijkstra´s algorithm, several nodes can be determined at one time. Moreover, we partition the network into different groups (network groups) and find the all-node pair´s shortest path in each group using a pipeline operation. Networks can be abstracted, and the shortest paths in very large networks can be found easily. The proposed scheme can decrease calculation time from O(N²) to O(N) using a pipeline operation on DAPDNA-2. Our simulations show that the proposed algorithm uses 99.6% less calculation time than Dijkstra´s algorithm. The proposed algorithm can be applied to the very large Internet network designs of the future.