k-pairwise disjoint paths routing in perfect hierarchical hypercubes

Hierarchical hypercubes (HHC), also known as cube-connected cubes, have been introduced in the literature as an interconnection network for massively parallel systems. Effectively, they can connect a large number of nodes while retaining a small diameter and a low degree compared to a hypercube of the same size. Especially (2 ^m +m)-dimensional hierarchical hypercubes (\(\mathit {HHC}_{2^{m}+m}\)), called perfect HHCs, are popular as they are symmetrical, which is a critical property when designing routing algorithms. In this paper, we describe an algorithm finding, in an \(\mathit{HHC}_{2^{m}+m}\), mutually node-disjoint paths connecting k=⌈(m+1)/2⌉ pairs of distinct nodes. This problem is known as the k-pairwise disjoint-path routing problem and is one of the important routing problems when dealing with interconnection networks. In an \(\mathit{HHC}_{2^{m}+m}\), our algorithm finds paths of lengths at most 2 ^m+1+m(2 ^m+1+1)+4 in O(2^5m ) time, where 2 ^m+1 is the diameter of an \(\mathit{HHC}_{2^{m}+m}\). Also, we have shown through an experiment that, in practice, the lengths of the generated paths are significantly lower than the worst-case theoretical estimations.