Efficient message routing in PrΣ-network

Hong Shen

Research output: Contribution to journalArticlepeer-review


The PrΣ-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, PrΣ becomes an attractive configuration for high performance interconnection networks. This paper describes how message routing in a PrΣ 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 nr) for a PrΣ-network containing nr = 10r + 1 nodes, where r ≥ 0.

Original languageEnglish
Pages (from-to)57-64
Number of pages8
JournalMicroprocessing and Microprogramming
Issue number1
Publication statusPublished - Jan 1994
Externally publishedYes


  • Algorithm
  • Cost
  • Interconnection network
  • Message routing
  • Performance
  • Recursive expansion
  • Time complexity


Dive into the research topics of 'Efficient message routing in PrΣ-network'. Together they form a unique fingerprint.

Cite this