A Constant Time Shortest-Path Routing Algorithm for Pyramid Networks

H.-J. Hsieh, D.-R. Duh, and J.-S. Shiau (Taiwan)


Interconnection networks, pyramid networks, shortestpath, routing algorithm


For interconnection networks, designing shortest path routing algorithms is in general more difficult than designing simple routing algorithms. In this paper, we derive a shortest path routing algorithm for pyramid networks. The proposed algorithm takes O(1) time to determine a shortest path between any two nodes in a pyramid network. We also design a distributed routing algorithm such that an intermediate node takes O(1) time to confirm the next node along the shortest path without any centralized controller.

Important Links:

Go Back