A Parallel Routing Algorithm on Circulant Networks Employing the Hamiltonian Circuit Latin Square

Abstract. Double-loop and 2-circulant networks are widely used in the design and implementation of local area networks and parallel processing architectures. In this paper, we investigate the routing of a message on circulant networks, that is a key to the performance of this network. We would like to transmit 2k packets from a source node to a destination node simultaneously along paths on G(n; ±s1,±s2,...,±s k ), where the i th packet will traverse along the i th path (1 ≤ i ≤ 2k). In oder for all packets to arrive at the destination node quickly and securely, the i th path must be node-disjoint from all other paths. For construction of these paths, employing the Hamiltonian Circuit Latin Square(HCLS) we present O(n 2 ) parallel routing algorithm on circulant networks