20.500.12556/DKUM-51751 An optimal permutation routing algorithm on full-duplex hexagonal networks Optimalni algoritem za permutacijsko usmerjanje na heksagonalnih mrežah 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. mathematics hexagonal networks permutation routing shortest path distributed algorithm communication networks oblivious algorithm matematika heksagonalne mreže permutacijsko usmerjanje najkrajše poti porazdeljen algoritem komunikacijsko omrežje pozabljiv algoritem true false true Angleški jezik Slovenski jezik Znanstveno delo 2015-07-10 15:05:41 2015-07-10 15:05:41 2022-05-30 03:07:13 2022-03-30 03:07:19 2008 0 0 str. 49-62 št. 3 Letn. 10 2008 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1365-8050 519.17 8089433 14899801 1365-8050 URN:SI:UM:DK:0UYRUQPC Discrete_Mathematics_&_Theoretical_Computer_Science_2008_Sau,_Zerovnik_An_optimal_permutation_routing_algorithm_for_full-duplex_hexagona.pdf Discrete_Mathematics_&_Theoretical_Computer_Science_2008_Sau,_Zerovnik_An_optimal_permutation_routing_algorithm_for_full-duplex_hexagona.pdf 1 C6DF6D1670CCF47A77E7FAAA80D19908 cf517b7f720437ad30ba82560372c0491797fd49e883083989c444d89a3bc418 63087e7c-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=113939 http://dmtcs.episciences.org/443 1 https://dk.um.si/Dokument.php?lang=slv&id=76311 Fakulteta za strojništvo 0 0 0