Topology and Routing Algorithms of 2-D Torus/Double -Loops Connected Petersen Graph Network
Lin Ya · Chinese Journal of Computers · 2004
A new extension of Petersen graph based on double-loops structure is proposed at first, and on the basis of which, an innovative 2-D double-loops connected Petersen graph interconnection network DCP(k) is constructed. Additionally, the characteristics of 2-D Torus connected Petersen graph interconnection network TCP(k) are analyzed, and on the basis of which, the conditions satisfying that the network diameter and grouping ability of TCP(k) are better than the diameter and grouping ability of 2-D Torus interconnection networks are presented. It is proved that DCP(k) and TCP(k) interconnection networks are both of simple topology, good extensibility and good connection degree etc, and especially, for the interconnection networks with 10×k nodes, DCP(k) and TCP(k) interconnection networks have both smaller network diameters and better grouping abilities than RP(k) and 2-D Torus interconnection networks. Finally, unicasting and broadcasting routing algorithms are designed for DCP(k) and TCP(k) interconnection networks respectively, it is proved that the communication efficiency of these two kinds of routing algorithms are better than those corresponding routing algorithms of RP(k) interconnection network, and in addition, the communication efficiency of unicasting and broadcasting routing algorithms of DCP(k) are better than those corresponding routing algorithms of TCP(k) interconnection network simultaneously.