Skip to Main content Skip to Navigation
New interface
Journal articles

An optimal permutation routing algorithm on full-duplex hexagonal networks

Ignasi Sau Valls 1 Janez Žerovnik 2 
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm on full-duplex hexagonal networks, using the addressing scheme described by F.G. Nocetti, I. Stojmenovic and J. Zhang (IEEE TPDS 13(9): 962-971, 2002). Furthermore, we prove that this algorithm is oblivious and translation invariant.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, April 3, 2014 - 4:13:33 PM
Last modification on : Thursday, August 4, 2022 - 4:52:42 PM
Long-term archiving on: : Thursday, July 3, 2014 - 4:40:33 PM


Files produced by the author(s)




Ignasi Sau Valls, Janez Žerovnik. An optimal permutation routing algorithm on full-duplex hexagonal networks. Discrete Mathematics and Theoretical Computer Science, 2008, Vol. 10 no. 3 (3), pp.49--62. ⟨10.46298/dmtcs.443⟩. ⟨hal-00972334⟩



Record views


Files downloads