具有大量错误结点的超立方体网络中的高效路由算法的设计与讨论

Designing Efficient Routing Algorithms on Hypercube Networks with A Large Number of Faulty Nodes

该文提出了容错超立方体网络的一个很自然的新概念 :局部连通性 ;讨论了两种类型的局部连通性 :局部k-维子立方体连通性和局部子立方体连通性 .一个局部连通的超立方体网络可容许大量错误结点且能确保超立方体网络是全局连通的 ;给出了满足局部连通性条件的超立方体网络中的几个高效的容错路由算法 .文中的容错路由算法是分布式的和基于局部信息的 。

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 k1, there is an h-dimensional subcube H h containing H k (thus hk) 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.