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 for full-duplex hexagonal networks, using the addressing scheme described by Nocetti et al. Furthermore, we prove that this algorithm is oblivious and translation invariant. ; Zahtevnost permutacijskega usmerjanja je standarden test za primernost topologije za komunikacijsko omrežje. V članku je pokazano, da je mogoče na heksagonalnih mrežah vsako permutacijsko usmerjanje opraviti v optimalnem številu komunikacijskih korakov, to je v številu korakov, ki so potrebni za najdaljšo med najkrajšimi potmi, ki so potrebne za prenos informacijskih paketov. Dokaz je konstruktiven, uporabljeni algoritem pa porazdeljen, saj ne potrebuje nobene globalne informacije. Vsako vozlišče potrebuje samo podatek o svoji lokaciji, vsak od paketov pa s seboj nosi naslov cilja.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    An optimal permutation routing algorithm on full-duplex hexagonal networks ; Optimalni algoritem za permutacijsko usmerjanje na heksagonalnih mrežah


    Beteiligte:

    Erscheinungsdatum :

    2015-07-10


    Anmerkungen:

    Discrete Mathematics and Theoretical Computer Science, vol. 10, no. 3, pp. 49-62, 2008. ; ISSN: 1365-8050


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629




    Optimal control with disturbance estimation ; Optimální řízení s odhadem poruchy

    Dušek, František / Honc, Daniel / Kizhakke Illom, Rahul Sharma | BASE | 2017

    Freier Zugriff

    Optimalni temperaturni intervali na besnastavov relsov pat

    Lepoev, Milcho / Atanasov, Svetomir | IuD Bahn | 2011


    Delay-Minimized Routing for Full-Duplex Vehicular Ad-Hoc Networks

    Zhou, Momiao / Xu, Wei / Ding, Zhizhong et al. | IEEE | 2022


    Optimal Full-Duplex Jamming for Safeguarding Two-Hop Relay Networks

    Li, Qiang / Ren, Pinyi / Du, Qinghe et al. | IEEE | 2019