Abstract: Peterson graph has good performance in parallel and distributed computation because of its characteristics such as short diameter and regularity. Based on ring structure, a new extension of Peterson graph was proposed, and a new interconnection network, the RPC(k) network was developed. Additionally, the properties of the RPC(k) network were investigated. It was proved that RPC(k) has lower-degree connectivity, smaller network diameter, simple topology and good extensibility. On the basis of these analysis, the conditions satisfying that the network diameter and grouping ability of RPC(k) are better than the diameter and grouping ability of 2-D Torus and RP(k) interconnection networks were presented. Finally, based on the RPC(k) network we designed a set of routing algorithms which are point to-point routing, permutation routing,one-to-all routing and all-to-all routing. Their communication efficiencies are「k/2」+5,k+9,「k/2」+5 and k+9 respectively. Especially as the k increasing, the efficiencies of these routing algorithms based on RPC(k) approximate to 1/3 of which based on RP(k) network.

Key words: Interconnection network, RPC(k) , Pctcrscn graph, Ring, Routing algorithm