Based on Petersen graph, a new interconnection network, the RP(k) network, is developed and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus network. Especially when the number of nodes in an optimal node group is between 6 and 100, the diameter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Furthermore based on the RP(k) network we design 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] + 2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.