Premium
An efficient shortest path routing on the hypercube with blocking/faulty nodes
Author(s) -
Arabpour Niasari Mehrdad,
Qiu Ke
Publication year - 2020
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.6124
Subject(s) - hypercube , shortest path problem , k shortest path routing , constrained shortest path first , computer science , node (physics) , path (computing) , routing (electronic design automation) , shortest path faster algorithm , blocking (statistics) , yen's algorithm , equal cost multi path routing , fault tolerance , longest path problem , floyd–warshall algorithm , algorithm , mathematics , mathematical optimization , link state routing protocol , theoretical computer science , distributed computing , parallel computing , dijkstra's algorithm , computer network , routing protocol , graph , structural engineering , engineering
Summary We investigate fault‐tolerant shortest path problem in the hypercube between two nodes where some nodes are faulty (or blocked) and thus cannot be used in routing. Previously, several similar problems were studied where proposed algorithms are distributed and local‐information‐based, that is, each node in the network knows only its neighbor's status (faulty or not) and they also look for optimal or near‐optimal paths. There have been studies that established some sufficient conditions for these paths to exist. Since these conditions are only sufficient, there could be shortest paths that will be missed by these conditions. We study the problem under the assumption that for two given nodes, a source node s , a target node t , only s requires to have a global information of the network in order to find a shortest path to t , should it exist. A shortest path is defined as the Hamming distance between s and t . This problem can be solved by trivial algorithms. The first is to try all possible paths. In an n ‐dimensional hypercube with 2 n vertices, this method would cost at least n! time. Another method is to perform a standard shortest path finding algorithm, which would require at least 2 n time. A routing algorithm has been previously developed which is efficient in certain situations. However, in the worst case, its running time could be exponential in the hypercube dimension. We propose an efficient algorithm with running time of O ( n 3 m 2 ) , polynomial in n , the hypercube dimension, and m , number of blocking nodes. We gain our efficiency by reducing the routing problem to a permutation problem which can be solved using inclusion‐exclusion principle. We finally use dynamic programming technique to optimally count the terms. With the proposed algorithm, not only can we find a shortest path, if such a path does exist, but we can also count all possible shortest paths.