Node-to-Set Disjoint Paths Routing in Metacube

A. Bossard, K. Kaneko, and S. Peng (Japan)


metacube, hierarchical hypercube, interconnection network, polynomial algorithm, disjointpath routing


The metacube interconnection network targeting large par allel computers has been introduced a few years ago. Keep ing its diameter short, similar to that of the hypercube, this network has a degree much lower than that of a hy percube of the same size. For example, with only 6 links per node, the corresponding metacube is able to connect more than one hundred of millions of nodes. We in troduce in this paper a routing algorithm for finding in a metacube MC(k, m) disjoint paths between one source node and a maximum of m + k destination nodes. We show that for any source node s, and any destination nodes D = {d1, . . . , dn}, n ≤ m + k, we can find n dis joint paths from s to di (1 ≤ i ≤ n) of maximal length (m2k + n)(k + 1) + k + 4 in O(nm2k (log n + k)) time complexity.

Important Links:

Go Back