双环Petersen 图互联网络及路由算法 - CiteSeerX.PDF

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@ Journal of Software, Vol.17, No.5, May 2006, pp .1115− 1123 http://www.j DOI: 10. 1360/jos171115 Tel/Fax : +86-10 © 2006 by Journal of Software. All rights reserved. ∗ 双环Petersen 图互联网络及路由算法 + 王 雷 , 林亚平, 夏 巍 (湖南大学 软件学院,湖南 长沙 410082) Topology and Routing Algorithms of Double-Loops Connected Petersen Graph Networks + WANG Lei , LIN Ya-Ping, XIA Wei (College of Software, Hu ’nan University, Changsha 410082, China) + Corresponding author: Phn: +86-731-8822333, E-mail: wanglei_hn@, Wang L, Lin YP, Xia W. Topology and routing algorithms of double-loops connected petersen graph network. Journal of Software, 2006,17(5):1115−1123. /1000-9825/17/1115.htm Abstract: 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 10k 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