Optimal Routing in 2-jump Circulant Networks

Borut Robi<=c ?

University of Cambridge Computer Laboratory

Systems Research Group

New Museums Site, Pembroke Street, Cambridge CB2 3QG, UK

May 1996

Abstract

An algorithm for routing a message along the shortest path between a pair of processors in 2-jump circulant (undirected double fixed step) networks is given. The algorithm requires ?(d) time for preprocessing, and ` = O(d) routing steps, where ` is the distance between the processors and d is the diameter of the network.

?Supported by the Partridge Visiting Fellowship and the Slovenian Science Foundation. On leave from Jo<=zef Stefan Institute and Faculty of Computer and Information Science, University Ljubljana, Slovenia.