计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (35): 123-125.

• 网络、通信与安全 • 上一篇    下一篇

交叉立方体网络上的一种双向搜索路由算法

王 敏1,高太平1,2,刘桂枝1,3,刘宏英1,4   

  1. 1.山西大学 计算机与信息技术学院,太原 030006
    2.山西大学 计算智能与中文信息处理省部共建教育部重点实验室,太原 030006
    3.山西大同大学 物理与电子科学学院,山西 大同 037009
    4.山西大同大学 数学与计算机科学学院,山西 大同 037009
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-12-11 发布日期:2007-12-11
  • 通讯作者: 王 敏

Bidirectional seeking routing algorithm in crossing cube

WANG Min1,GAO Tai-ping1,2,LIU Gui-zhi1,3,LIU Hong-ying1,4   

  1. 1.School of Computer & Information Technology,Shanxi University,Taiyuan 030006,China
    2.Key Lab. of MoE for Computation Intelligence & Chinese Inf. Pro.,School of Com. & Inf. Tech.,Shanxi University,Taiyuan 030006,China
    3.School of Physics and Electronic Science,Shanxi Datong University,Datong,Shanxi 037009,China
    4.School of Mathematics and Computer Science,Shanxi Datong University,Datong,Shanxi 037009,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-12-11 Published:2007-12-11
  • Contact: WANG Min

摘要: 交叉立方体是近年提出的一种互联网络。虽然直径大约是超立方体直径的一半,但由于节点连接方式比超立方体复杂,所以在交叉立方体中利用节点编码研究路由算法比在超立方体中复杂的多。针对交叉立方体互联网络节点编码的特点,在理论分析的基础上采用双向搜索的方法,给出了一个基于交叉立方体节点编码的多项式路由算法,证明了在交叉立方体上采用该算法求得的任意两节点间的路长不超过该交叉立方体的直径。

关键词: 交叉立方体, 编码, 双向搜索, 路由算法

Abstract: Crossing cube which has been proposed recently is a kind of interconnection networks.Although its diameter is about half of hypercube’s,researching routing algorithm by vertices’ labels is much more complicated in crossing cube than that in hypercube since vertices of crossing cube link complicatedly.In this paper,considering labels’ characteristics of vertices in crossing cubes,we give a polynomial routing algorithm of crossing cube adopting bidirectional seeking method by theoretic analysis,and prove that length of path obtained by this algorithm is not more than crossing cube’s diameter.

Key words: crossing cube, label, bidirectional seeking, routing algorithm