文章基本信息

标题：Disjoint-Path Routing on Hierarchical Dual-Nets
其他标题：Disjoint-Path Routing on Hierarchical Dual-Nets
本地全文：下载
作者：Jun Arai ; Yamin Li
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2014
卷号：4
期号：2
页码：260-278
语种：English
出版社：International Journal of Networking and Computing
摘要：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.
关键词：Interconnection network; routing algorithm; disjoint paths