Node-to-Set Disjoint-path Routing in Metacube

The metacube interconnection network introduced a few years ago has some very interesting properties: it has a short diameter similar to the hypercube, and its degree is much lower than that of a hypercube of the same size. In this paper, we describe an efficient algorithm for finding disjoint paths between one source node and at most m+k target nodes in a metacube MC(k, m) excluding MC(*, 1), MC(2, 2), MC(3, 2) and MC(3, 3). We show that we can find m+k disjoint paths between the source node and the m+k targets of length at most metacube diameter plus (k + 4) with time complexity of order of metacube degree times its diameter.