Construction of a parallel and shortest routing algorithm on recursive circulant networks
Ilyong Chung · 2000
In this paper, we investigate the routing of a message in recursive circulant, that is a key to the performance of this network. On recursive circulant network, we would like to transmit m packets from a source node to a destination node simultaneously along m paths, where the ith packet will traverse along the ith path (0/spl les/i/spl les/m-1). In order for all packets to arrive at the destination node quickly and securely, these m paths must be node-disjoint and the sum of lengths of paths be the smallest. Employing the Hamiltonian circuit Latin square (HCLS), we present O(m2) parallel routing algorithm for constructing a set of m shortest and node-disjoint paths.