The embedding of rings and meshes into RP(k) networks

摘要

This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and the ring with 10 K nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9 K nodes can be embedded into the RP-1 (k) network. After that, we discuss the embedding of a 2-D mesh, M,(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP{k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequence-column-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to [a/10]+2 and the congestion is equal to max{[a/10]+1, 6} when a >10. As a special case, the four parameters are also equal to 1 when a is equal to 10.