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.


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:

    Publication date :

    2015-07-10


    Remarks:

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


    Type of media :

    Paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    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

    Free access

    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