一种实用的互联网络拓扑结构rpc(k)及路由算法

pertersen图由于具有短直径和正则性等特性，在并行计算与分布式计算中具有良好的性能。基于环结构，提出了一种pertersen图的新扩展方法，构造了互联网络rpc(k)。分析了该互联网络的性质，它具有连接度小、网络直径短、拓扑结构简单以及易于扩展等特点。同时给出了rpc(k)优于二维torus以及rp(k)互联网络的直径和节点可分组性的条件。最后，分别设计了rpc(k)上的单播路由、置换路由、广播路由和多对多路由，它们的通信效率分别为「k/2」+5,k+9,「k/2」+5和k+9。特别是随着k的增大，rpc(k)网络路由算法的通信效率近似于rpc(k)网络上的对应算法通信效率的1/3倍。