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 , 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.49--62
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972334
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:13:33
Dernière modification le : jeudi 3 avril 2014 - 16:43:33
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:40:33

Fichier

960-3471-3-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de
la notice

326

Téléchargements du document

340