Disjoint-Path Routing on Hierarchical Dual-Nets

Abstract

The hierarchical dual-net (HDN) was introduced as a topology of interconnection networks for extremely large parallel computers. The HDN is constructed based on a symmetric product graph (base network). A ${k}$-level hierarchical dual-net, HDN(${B,k,S}$), contains ${(2N_0)^{2^k}/(2\times \prod_{i=1}^{k}s_i)}$ nodes, where ${S=\{G'_1,G'_2,\ldots,G'_k\}}$, ${G'_i}$ is a super-node and ${s_i = |G'_i|}$ is the number of nodes in the super-node at the level ${i}$ for ${1 \leq i \leq k}$, and ${N_0}$ is the number of nodes in the base network ${B}$. The node degree of HDN(${B,k,S}$) is ${d_0+k}$, where ${d_0}$ is the node degree of the base network. The HDN is node and edge symmetric and can contain huge number of nodes with small node-degree and short diameter. Disjoint-path routing is a fundamental and critical issue for the performance of an interconnection network. In this paper, we propose an efficient algorithm for finding disjoint-paths on an HDN and give the performance simulation results.