双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.

Topology and Routing Algorithms of Double-Loops Connected Petersen Graph Networks

Petersen graph has good performance in parallel and distributed computation because of its characteristics such as short diameter and regularity. On the basis of topology of double-loops, a new double-loops connected Petersen graph network DLCPG(k) is constructed. In addition, unicasting, broadcasting and a kind of fault-tolerant routing algorithms are designed respectively. It is proved that DLCPG(k) not only has good extensibility, short diameter and simple topology, but also has the following good characteristics for the networks with 10^k nodes: The diameter of DLCPG(k) is shorter than that of 2-dimensional Torus and RP(k) networks, and the grouping ability of DLCPG(k) overmatches that of 2-dimensional Torus and RP(k) networks at the same time. It is also proved that the communication efficiency of both the unicasting and broadcasting algorithms are better than the unicasting and broadcasting algorithms of RP(k) network conspicuously. Simulation results conclude that the new fault-tolerant routing algorithm is of good fault-tolerant ability.