Node-to-set disjoint paths routing in a metacube
Antoine Bossard, Keiichi Kaneko, Shietung Peng · International Journal of High Performance Computing and Networking · 2015
The metacube interconnection network was designed for large parallel computers in 2002. Compared with a hypercube of the same size, a metacube has a degree significantly lower while retaining a similar diameter. For example, a metacube having only six links per node has the capacity to connect 237 nodes. We describe in this paper a routing algorithm in a metacube MC(k, m) selecting n (n ≤ k + m) disjoint paths between one source node and n destination nodes. We show that for any source node s, and any set of destination nodes D = {d1, d2, ..., dn}, we can select n disjoint paths from s to di (1 ≤ i ≤ n) of maximum length (k + 1)(m2k + n) + k + 4 in O(nm2k(log n + k)) time. Additionally, we performed an empirical evaluation of the proposed algorithm and observed that its average time complexity and average maximum path length are significantly better than the theoretical worst-case estimations.