Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

Fault-free cycles in folded hypercubes with more faulty elements

Let FFv (respectively, FFe) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional folded hypercube FQn. In this paper, we show that FQn−FFv−FFe contains a fault-free cycle with length at least n²−2|FFv| if |FFe|+|FFv|?2n−4 and |FFe|?n−1, where n?3. Our result improves the previously known result of [S.-Y. Hsieh, A note on cycle embedding in folded hypercubes with faulty elements, Information Processing Letters (2008), in press, doi:10.1016/j.ipl.2008.04.003] where |FFe|+|FFv|?n−1 and n?4.     

Node-disjoint paths in hierarchical hypercube networks

The hierarchical hypercube network is suitable for massively parallel systems. One of its appealing properties is the low number of connections per processor, which can facilitate the VLSI design and fabrication. Other alluring features include symmetry and logarithmic diameter, which can derive easy and fast algorithms for communication. In this paper, a maximal number of node-disjoint paths are constructed between every two distinct nodes of the hierarchical hypercube network. Their maximal length is not greater than max{2^m+1+2m+1,2^m+1+m+4}, where 2^m+1 is the diameter. The effectiveness of node-disjoint paths is further verified by experiments.     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=²n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given.     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.     

Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u ₁, u ₂, …, u _k (1≤k<n) in the n-cube Q _n , where (u ₁, u ₂), (u ₃, u ₄), …, (u _2m?1, u _2m ) (m≤? k\2 ?) are edges of the same dimension, (ii) any k positive integers a ₁, a ₂, …, a _k such that a ₁, a ₂, …, a _2m are odd and a _2m+1, …, a _k are even, with a ₁+a ₂+···+a _k =2 ⁿ , and (iii) k subsets W ₁, W ₂, …, W _k of V(Q _n ) with |W _i |≤n?k and if a _i =1, then u _i ¬∈W _i , for 1≤i≤k, we show that there exist k vertex-disjoint paths P ₍₁₎, P ₍₂₎, …, P _(k) in Q _n where P _(i) contains a _i vertices, its origin is u _i , and its terminus is in V(Q _n )/ W _i , for 1≤i≤k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, ?asopis pro P?stování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].     

An effective routing algorithm in incomplete hypercubes

An incomplete hypercube appears interesting and practical because of its relaxed restriction on the system size and possession of salient properties of complete hypercubes. The performance of incomplete hypercubes can be improved considerably by reducing communication time, which can be achieved by forwarding messages through two parallel paths between a pair of nodes. This paper presents a simple and effective two-parallel-paths routing algorithm for incomplete hypercubes which takes advantage of the flexibility provided by incomplete hypercubes, and yet prevents traffic congestion and deadlock. Simulation results indicate that the mean latency for sending large sized messages is reduced and the degree of reduction becomes larger when the system load grows. This significant reduction in latency could translate to a respectable performance improvement. This algorithm can also tolerate one fault in the system by sending duplicate copies of messages through two parallel paths with little increase in the mean latency under light-traffic load.     

Longest fault-free paths in hypercubes with vertex faults

The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ? n − 2, the n-cube contains a fault-free path with length at least 2ⁿ − 2f − 1 (or 2ⁿ − 2f − 2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n − 1 faulty vertices. Hence, our result is optimal.     

A further result on fault-free cycles in faulty folded hypercubes

Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let FFv (respectively, FFe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube FQn. Fu has showed that FQn−FFv−FFe for n?3 contains a fault-free cycle of length at least n²−2|FFv| if |FFv|+|FFe|?2n−4 and |FFe|?n−1. In this paper, we further consider the constraints |FFv|+|FFe|?2n−4 and |FFe|?n that were not covered by Fu's result. We obtain the same lower bound of the longest fault-free cycle length, n²−2|FFv|, under the constraints that (1) |FFv|+|FFe|?2n−4 and (2) every node in FQn is incident to at least two fault-free links.     

Long paths in hypercubes with a quadratic number of faults

A path between distinct vertices u and v of the n-dimensional hypercube Q_n avoiding a given set of f faulty vertices is called long if its length is at least 2ⁿ-2f-2. We present a function (n)=Θ(n²) such that if f(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q_n. Moreover, the bound provided by (n) is asymptotically optimal. Furthermore, we show that assuming f(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.     

Node-disjoint paths in incomplete WK-recursive networks

The incomplete WK-recursive networks have been recently proposed to relieve the restriction on the sizes of the WK-recursive networks. In this paper, a maximal set of node-disjoint paths is constructed between arbitrary two nodes of an incomplete WK-recursive network. The effectiveness of the constructed paths is verified by both theoretic analysis and extensive experiments. A tight upper bound on the maximal length is suggested. On the other hand, experimental results show that for arbitrary two nodes, the expected maximal length is not greater than twice their distance and about equal to the diameter. When the two nodes are the farthest pair, the maximal length is not greater than twice the diameter and the expected maximal length is not greater than 1.5 times the diameter.     

Long paths in hypercubes with conditional node-faults

Let F be a set of f?2n-5 faulty nodes in an n-cube Q_n such that every node of Q_n still has at least two fault-free neighbors. Then we show that Q_n-F contains a path of length at least 2ⁿ-2f-1 (respectively, 2ⁿ-2f-2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2ⁿ-2f-1 (or 2ⁿ-2f-2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n-2 faulty nodes are considered.     

Long paths and cycles in hypercubes with faulty vertices

A fault-free path in the n-dimensional hypercube Q_n with f faulty vertices is said to be long if it has length at least 2ⁿ-2f-2. Similarly, a fault-free cycle in Q_n is long if it has length at least 2ⁿ-2f. If all faulty vertices are from the same bipartite class of Q_n, such length is the best possible. We show that for every set of at most 2n-4 faulty vertices in Q_n and every two fault-free vertices u and v satisfying a simple necessary condition on neighbors of u and v, there exists a long fault-free path between u and v. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n²/10+n/2+1 faulty vertices in Q_n where n?15 that Q_n has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal.     

Pancyclicity and bipancyclicity of conditional faulty folded hypercubes

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network’s topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ_n is an attractive variant of an n-dimensional hypercube Q_n that is obtained by establishing some extra edges between the vertices of Q_n. FQ_n for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ_n. For any FQ_n (n ? 2) with at most 2n − 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2ⁿ; and when n ? 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2ⁿ − 1. The result is optimal with respect to the number of faulty edges tolerated.     

Hamiltonian paths and cycles passing through a prescribed path in hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. In this paper, the following result is obtained: The n-dimensional hypercube Qn with n?3 is (2n−3)-path bipancyclic but is not (2n−2)-path bipancyclic, moreover, a path P of length k with 2?k?2n−3 lies in a cycle of length 2k−2 if and only if P contains two edges of the same dimension. In order to prove the above result we first show that any path of length at most 2n−1 is a subpath of a Hamiltonian path in Qn with n?2, moreover, the upper bound 2n−1 is sharp when n?4.     

Embedding paths of variable lengths into hypercubes with conditional link-faults

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q_n, in which every node is still incident to at least two fault-free links. Then we show that Q_n-F has a path of any odd (resp. even) length in the range from the distance to 2ⁿ-1 (resp. 2ⁿ-2) between two arbitrary nodes even if |F|=2n-5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.