Ignasi Sau ; Janez Žerovnik - An optimal permutation routing algorithm on full-duplex hexagonal networks

dmtcs:443 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 3 - https://doi.org/10.46298/dmtcs.443
An optimal permutation routing algorithm on full-duplex hexagonal networks

Authors: Ignasi Sau ORCID-iD; Janez Žerovnik

    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.


    Volume: Vol. 10 no. 3
    Section: Distributed Computing and Networking
    Published on: January 1, 2008
    Imported on: March 26, 2015
    Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 262 times.
    This article's PDF has been downloaded 356 times.