一种实用的互联网络RP_n(k)及其路由算法  

Interconnection network RP_n(k) and its routing algorithms

作　　者：邢长明[1] 杨林[2] 刘方爱[3] 

机构地区：[1]山东财政学院继续教育学院,济南250014 [2]山东商业职业技术学院国际交流学院,济南250103 [3]师范大学信息科学与工程学院,济南250014

出　　处：《计算机应用研究》2011年第6期2310-2312,2316,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60373063,90612003);山东省自然科学基金资助项目(Y2007G11);山东财政学院科研计划资助项目

摘　　要：基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。Based on these properties of Petersen graph and the simple scalable property of ring,presented a new interconnection network RPn（k） and analyzed the properties of the RPn（k）.RPn（k） not only has good regularity and extensibility,but also has shorter diameter,better grouping ability and smaller construction costs than the RP（k） network.Finally,discussed the routing algorithm of RPn（k） and proposed the point-to-point routing on the RPn（k） network.The performances of the algorithm is ＋2n routing time steps.When the number of nodes is same,the communication efficiency of the routing algorithm on RPn（k） is better than the routing algorithm on RP（k） network.

关 键 词：互联网络 RPn(k) 环 PETERSEN图 路由算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]