An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges

In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an n-dimensional bijective connection network, denoted by X(n), is extremely low when n becomes sufficient large. Then, we give an O(n) algorithm to find a fault-free path of length at most n + 3inverted right perpendicularlog(2) vertical bar F vertical bar inverted left perpendicular + 1 between any two different nodes in X(n) if each node of X(n) has at least one fault-free incident edge and the number of faulty edges is not more than 2n - 3. In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Mobius cubes, etc., all the results are appropriate for these cubes. (C) 2011 Elsevier B.V. All rights reserved.