Fault-tolerant Routing in Metacube

A new interconnection network with low-degree for very large parallel computers called metacube (MC) has been introduced recently. The MC network has short diameter similar to that of the hypercube. However, the degree of an MC network is much lower than that of a hypercube of the same size. More than one hundred of millions of nodes can be connected by an MC network with up to 6 links per node. The MC network has 2-level cube structure. An MC(k,m) network that connects 2 m2k +k nodes with m + k links per node has two parameters, k and m, where k is the dimension of the high-level cubes (classes) and m is the dimension of the low-level cubes (clusters). In this paper, we give an efficient algorithm for fault-tolerant routing in MC networks. The fault-tolerant routing problem in MC(k,m) is solved through a special structure in an MC network, called multi-channel cube. In order to construct k disjoint paths for each node pair in a multi-channel cube, an innovative technique, called signature, is introduced. 1