Efficient message routing in P_r^Σ-network

The P_r^Σ-network is a high performance interconnection network constructred 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 = 10^{r + 1} nodes, where r ≥ 0.