Title: Node-to-set disjoint paths routing in a metacube

Authors: Antoine Bossard; Keiichi Kaneko; Shietung Peng

Addresses: Advanced Institute of Industrial Technology, Tokyo Metropolitan University, Shinagawa, 140-0011, Japan ' Graduate School of Engineering, Tokyo University of Agriculture and Technology, Koganei, 184-8588, Japan ' Faculty of Computer and Information Science, Hosei University, Koganei, 184-8584, Japan

Abstract: 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 2³⁷ 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 = {d₁, d₂, ..., d_n}, we can select n disjoint paths from s to di (1 ≤ i ≤ n) of maximum length (k + 1)(m2^k + n) + k + 4 in O(nm2^k(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.

Keywords: metacube interconnection networks; metacubes; hierarchical hypercubes; disjoint paths; routing algorithms; time complexity; graphs; path length; parallel computing.

DOI: 10.1504/IJHPCN.2015.072778

International Journal of High Performance Computing and Networking, 2015 Vol.8 No.4, pp.315 - 323

Accepted: 24 Jun 2014
Published online: 03 Nov 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article