An optimal permutation routing algorithm on full-duplex hexagonal networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2008

An optimal permutation routing algorithm on full-duplex hexagonal networks

Résumé

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.
Fichier principal
Vignette du fichier
960-3471-3-PB.pdf (102.44 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00972334 , version 1 (03-04-2014)

Identifiants

Citer

Ignasi Sau, 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⟩
461 Consultations
978 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More