Journal Article

Set-to-Set Disjoint Paths Routing in Hierarchical Cubic Networks

Antoine Bossard and Keiichi Kaneko

in The Computer Journal

Published on behalf of British Computer Society

Volume 57, issue 2, pages 332-337
Published in print February 2014 | ISSN: 0010-4620
Published online January 2013 | e-ISSN: 1460-2067 | DOI:
Set-to-Set Disjoint Paths Routing in Hierarchical Cubic Networks

Show Summary Details


Due to its simplicity, the hypercube topology is popular as interconnection network of parallel systems. However, due to physical restrictions of the number of links per node, this topology is no more satisfactory in the context of modern supercomputing. Effectively, today massively parallel systems, such as the Fujitsu K computer, connect hundreds of thousands of nodes (705 024 nodes for the K, connected according to a six-dimensional torus network). Focusing on degree reduction, a variation of the hypercube topology called hierarchical cubic networks (HCNs) was described. An HCN contains almost half of the number of edges of an hypercube of the same size, and additionally, its diameter is also smaller. We describe in this paper a set-to-set disjoint paths routing algorithm in an HCN (n), finding between two disjoint sets of nodes at most n+1 mutually node-disjoint paths of lengths at most 6n+3 in O(n2log n) time.

Keywords: interconnection network; algorithm; parallel processing; hypercube; hierarchical cubic network

Journal Article.  0 words. 

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.