Efficient message routing in P_r^Σ-network

The P_r^∑-network is a high performance interconnection network constructed by the recursive expansion method on the basis of the Petersen graph. As its cost (degree×diameter), a main performance measure for static interconnection networks, is very low in comparison with other known networks of the same size, P_r^∑ becomes an attractive configuration for high performance interconnection networks. This paper describes how message routing in a P_r^∑ network can be efficiently carried out. We first show a node addressing scheme for the network, and then present a simple and efficient routing algorithm for message routing in the network. Our algorithm realizes point-to-point message routing without the need of maintaining a routing table at each node, and has a time complexity of O(log n_r) for a P_r^∑-network containing n_r nodes, where n_r = 10^r+1 and r≥0.