一类层次环网络的构造及路由算法

摘要：

讨论了一类层次环网络HRN的构造方法、拓扑性质和路由策略.重点讨论了HRN网络的一个子类,即RP(P,k1,k2)网络,分析了其拓扑性质,并和2D Torus,3D Torus,Hypercube和De Bruijn Graph等拓扑结构进行了分析比较.结果表明,RP(P,k1,k2)网络的拓扑结构简单,路由策略方便,是一种实用的互联网络.接着,讨论了RP(P,k1,k2)网络上的路由问题,给出了点点路由、Broadcast路由、All to-a¨路由和置换路由算法,前3个算法分别需要[k2/2]+[k1/2]+2,[k22/2]+[k1/2]+2,10×k1×k2-4个时间步,置换路由需要4+min{k2,k1}+(k2-1)×(k1-1)个路由时间步.最后,提出了两个参数,即最优节点分组和最优网络划分,用于评价互联网络的效率,并据此分析了RP(P,k1,k2),2D Torus和Hypercube网络的性能.

关键词：互联网络、路由算法、最优网络划分、最优节点分组、层次环网络

所属期刊栏目：25

分类号：TP302(计算技术、计算机技术)

资助基金：国家自然科学基金69933020;山东省自然科学基金

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1397-1404