一种实用的互联网络RPn(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 [k/2]+ 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.%基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销.讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步.在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高.