计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (20): 1-4.

• 博士论坛 • 上一篇    下一篇

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

张国珍   

  1. 山西大学 数学科学学院,太原 030006
  • 出版日期:2015-10-15 发布日期:2015-10-30

Unidirectional [k]-ary [n]-cube networks

ZHANG Guozhen   

  1. School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China
  • Online:2015-10-15 Published:2015-10-30

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

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

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