单向k-元n-立方体网络

摘要

单向k-元n-立方体是指具有单向边的k-元n-立方体互连网络拓扑。当网络包含的顶点数目较大时，比起传统的双向k-元n-立方体，单向 k-元n-立方体对通信硬件复杂性的要求更低一些。提出了k-元n-立方体的一个定向，使得定向后的单向k-元n-立方体UQkn有一些良好的性质。证明了UQkn是正则的，极大弧连通的，具有迭代结构的且UQkn的直径是小的。此外，提出了一个简单的多项式时间路由算法。%Unidirectional k -ary n-cubes are k -ary n-cube interconnection topologies with unidirectional edges. While accommodating large number of vertices, unidirectional k -ary n -cubes require less complicated communication hard-ware than conventional bidirectional k -ary n-cubes. In this paper, it proposes an assignment of orientations to the edges of the k -ary n-cube and derives attractive properties for the resulting unidirectional k -ary n-cube UQkn . It shows that UQkn is regular, maximally arc-connected and recursively structured. The diameter of the UQkn is small. Moreover, it pro-vides a simple and polynomial-time routing algorithm.