Unicast in hypercubes with large number of faulty nodes

摘要

Unicast in computer/communication networks is a one-to-one communication between a source node s and a destination node t. We propose three algorithms which find a nonfaulty routing path between s and t for unicast in the hypercube with a large number of faulty nodes. Given the n-dimensional hypercube H/sub n/ and a set F of faulty nodes, node u/spl epsiv/ H/sub n/ is called k-safe if u has at least k nonfaulty neighbors. The H/sub n/ is called k-safe if every node of H/sub n/ is k-safe. It has been known that for 0/spl les/k/spl les/2, a k-safe H/sub n/ is connected if |F|/spl les/2/sup k/(n-k)-1. Our first algorithm finds a nonfaulty path of length at most d(s,t)+4 in O(n) time for unicast between 1-safe s and t in the H/sub n/ with |F|/spl les/2n-3, where d(s,t) is the distance between s and t. The second algorithm finds a nonfaulty path of length at most d(s,t)+6 in O(n) time for unicast in the 2-safe H/sub n/ with |F|/spl les/4n-9. The third algorithm finds a nonfaulty path of length at most d(s,t)+O(k/sup 2/) in time O(|F|+n) for unicast in the k-safe H/sub n/ with |F|/spl les/2/sup k/(n-k)-1 (0/spl les/k/spl les/2). The time complexities of the algorithms are optimal. We show that in the worst case, the length of the nonfaulty path between s and t in a k-safe H/sub n/ with |F|/spl les/2/sup k/(n-k)-1 is at least d(s,t)+2(k+1) for 0/spl les/k/spl les/2. This implies that the path lengths found by the algorithms for unicast in the 1-safe and 2-safe hypercubes are optimal.