Designing Efficient Routing Algorithms on Hypercube Networks with A Large Number of Faulty Nodes
Wang Guo · Chinese Journal of Computers · 2001
Routing has been a popular topic in the study of computer networks. With the continuous increasing in network size, routing in large size networks with faults has become unavoidable. We introduce a new and natural concept of fault tolerance for hypercube networks: local-connectivity. Two kinds of local-connectivity have been defined in this paper. The first kind of local-connectivity is local k-subcube-connectivity, in which each k-dimensional subcube H k contains less than 2 k-1 faulty nodes and the non-faulty nodes in H k make a connected graph. The second kind of local-connectivity is local subcube-connectivity, in which if for every k-dimensional subcube H k of H n, where k1, there is an h-dimensional subcube H h containing H k (thus hk) such that H h is locally h-subcube connected. We show that a locally connected hypercube network may contain a large number of faulty nodes, and prove that a locally connected hypercube network is also globally connected. We develop two efficient routing algorithms on locally connected hypercube networks: for a locally k-subcube-connected n-dimensional hypercube network H n, our first routing algorithm constructs a path of non-faulty nodes from a given source node to a given destination node in time O(n2k); for a locally subcube-connected n-dimensional hypercube network H n, our second routing algorithm constructs a path of non-faulty nodes from a given source node to a given destination node in time O(n2 k min), where k min is the smallest integer such that the n-dimensional hypercube H n is locally k min-subcube-connected (where the value k min is not necessarily known to our algorithm)/ Our routing algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms. Our new concept of local-connectivity is easily extendable to other hierarchical networks. Finally, other network problems, such as network emulation and network broadcasting, should also be interesting under our new concept of local-connectivity.