Node-to-Set Disjoint Paths Routing in Metacube

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


metacube, hierarchical hypercube, interconnection network, polynomial algorithm, disjoint-path 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