二维环/双环互连Petersen图网络及其路由算法  

Topology and Routing Algorithms of 2-D Torus/Double -Loops Connected Petersen Graph Network

作　　者：王雷[1] 林亚平[1] 陈治平[1] 文学[1] 

机构地区：[1]湖南大学计算机与通信学院,长沙410082

出　　处：《计算机学报》2004年第9期1290-1296,共7页Chinese Journal of Computers

基　　金：湖南省自然科学基金 (0 3JJY30 98)资助

摘　　要：基于双环结构提出了一种Petersen图的新扩展方法 ,并在此基础上构造了一个 2维双环互连Petersen图网络DCP(k) .分析了 2维环互连Petersen图网络TCP(k)的特性 ,给出了TCP(k)优于 2 DTorus互联网络的直径及可分组性的条件 .证明了DCP(k)和TCP(k)具有良好的可扩性和连接度 ;而且对 10×k个节点组成的互联网络 ,DCP(k)和TCP(k)均具有比RP(k)及 2 DTorus互联网络更小的直径和更优越的可分组性 .最后 ,分别设计了DCP(k)和TCP(k)上的单播和广播路由算法 ,证明了其通信效率较RP(k)上的对应算法均分别有明显提高 ,且DCP(k)更优于TCP(k) .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.

关 键 词：环 双环 Peterson图 最优分组 路由算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]