Abstract: 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 hardware 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 provides a simple and polynomial-time routing algorithm.

Key words: interconnection networks, [k]-ary [n]-cubes, distributed routing, connectivity

摘要： 单向[k]-元[n]-立方体是指具有单向边的[k]-元[n]-立方体互连网络拓扑。当网络包含的顶点数目较大时，比起传统的双向[k]-元[n]-立方体，单向?[k]-元[n]-立方体对通信硬件复杂性的要求更低一些。提出了[k]-元[n]-立方体的一个定向，使得定向后的单向[k]-元[n]-立方体[UQkn]有一些良好的性质。证明了[UQkn]是正则的，极大弧连通的，具有迭代结构的且[UQkn]的直径是小的。此外，提出了一个简单的多项式时间路由算法。

关键词: 互连网络, [k]-元[n]-立方体, 分布式路由, 连通性