An optimal permutation routing algorithm on full-duplex hexagonal networks

Ignasi Sau 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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00972334
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, April 3, 2014 - 4:13:33 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Thursday, July 3, 2014 - 4:40:33 PM

File

960-3471-3-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00972334, version 1

Collections

Citation

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

Share

Metrics

Record views

707

Files downloads

702