Optimalno permutacijsko usmerjanje v heksagonalnih omrežjih
Maja Rotovnik1, Jurij Silc2, Janez Zerovnik3 1
1	Inštitut za matematiko, fiziko in mehaniko, Jadranska ulica 19, SI-1000 Ljubljana, Slovenija
2	Institut "Jošef Stefan ", Odsek za računalniške sisteme, Jamova cesta 39, SI-1000 Ljubljana, Slovenija
3	Univerza v Ljubljani, Fakulteta za strojništvo, Aškerčeva cesta 6, SI-1000 Ljubljana, Slovenija E-pošta: mrotovnik@yahoo.com, jurij.silc@ijs.si, janez.zerovnik@imfm. uni-lj.si
Povzetek. V sestavku najprej vpeljemo komunikacijska omrežja in usmerjanje podatkov v njih, v nadaljevanju pa se osredotočimo na permutacijsko usmerjanje. Osrednji del sestavka je problem optimalnega permutacijskega usmerjanja na trikotniških mrežah. Predstavljen je optimalni permutacijski usmerjevalni algoritem, ki za usmerjanje vseh permutacij potrebuje lmax korakov, kjer je lmax najdaljša izmed vseh najkrajših poti sporocil.
Ključne besede: teorija grafov, heksagonalno omrežje, permutacijsko usmerjanje, trikotniške mreže
Optimal Permutation Routing on Hexagonal Networks
Extended abstract. At the beginning of the paper we introduce communication networks and data routing in networks. Later we focus on permutation routing, where each base station is the origin of at most one package and at the same time is the destination of no more than one package. The main part of the paper represents the problem of optimal permutation routing in triangular meshes with full-duplex edges.
We describe an optimal permutation routing algorithm for full-duplex triangular meshes. The basic idea of the algorithm is that a saturated package should not wait any longer because it has already waited as long as it could, otherwise the algorithm becomes suboptimal. Packet p is saturated if the number of waiting steps of the packet is lmax — lp, where lmax is the maximum length over the shortest paths of all packets and lp is the length of the shortest path of packet p.
The algorithm routes every permutation in the lmax routing steps and is optimal, because lmax is a lower bound of every permutation routing algorithm in triangular meshes.
Key words: graph theory, hexagonal network, permutation routing, triangular mesh
1 Uvod
Teorija grafov je ena najbolj proučevanih in uporabnih matematičnih smeri v zadnjih nekaj desetletjih. Aplikacije, ki jih lahko predstavimo z grafi, najdemo na vec različnih področjih, kot so operacijske raziskave, druZboslovje, kemija, računalniške mreze in predvsem komunikacijska omrezja (KO). KO je sestavljeno iz baznih postaj (BP) in povezav, po katerih lahko pošiljamo med njimi sporočila. KO lahko predstavimo z grafom, kjer so BP vozlišča grafa, fizične povezave med BP pa
so povezave grafa. Osnovna naloga KO je omogočanje izmenjave podatkov med BP. Način izbire poti, po katerih se bodo podatki premikali, imenujemo usmerjanje in je bistvenega pomena za uspesšno delovanje KO, saj lahko slaba izbira vodi do neučšinkovitega in počšasnega omrezja. (Če usmerjanje povezuje vse (urejene) pare voz-lisč, ga imenujemo popolno usmerjanje, sičer ga imenujemo delno usmerjanje. Literature na tu obravnavano temo je veliko, tu omenimo samo pogosto čitirano knjigo [3] in zapis v slovenskem jeziku [7].
Uspešno usmerjanje je odvisno od izbire topologije KO, tipa povezav, usmerjevalnega problema itd. [1]. Topologija KO je način, kako predstavimo KO s pomočjo grafov in kako so BP povezane v določene tipe grafov. Topologija je torej fizična povezanost KO. Od njene izbire so odvisne številne lastnosti, kot so premer, stopnja voz-lisč, razširljivost, odpornost na napake itd. Od dobrega KO pričakujemo, da bo imel majhen premer pri nizki stopnji vozlišč, da bo dobro razširljiv in bo čim bolj odporen na napake. Idealnega KO, ki bi imel vse te lastnosti, ni, saj z zmanjševanjem stopnje vozlišč večamo premer. Topologijo izberemo torej glede na pomembnost teh lastnosti v KO. Najbolj znane topologije so mreze. Povezave med vozlisščši KO so lahko neusmerjene, usmerjene ali hkratno dvosmerne. Glede na vrsto povezav, ki so v posameznem KO, ločimo različne modele usmerjanja: neusmerjen model, ki omogoča pretok podatkov po povezavi v obe smeri, vendar le v eno smer hkrati, usmerjen model, ki omogočša pretok podatkov po povezavi le v eno, in to vedno isto smer, ter hkratni dvosmerni model, ki omogoča prenos podatkov v obe smeri, vendar le en podatek v eno smer hkrati. Usmerjevalni model KO
določa način izmenjave sporočil. Poznamo več tipov usmerjevalnih modelov, kot npr. preklapljanje povezav, usmerjanje z vodili in paketno usmerjanje. Najpogosteje je uporabljeno paketno usmerjanje, kjer se sporočilo, ki ga Želimo poslati, preoblikuje v enega ali več paketov. Vsak paket pozna svoj cilj, kije enak cilju prvotnega sporočila. Ko paketi prispejo na čilj, se ponovno združijo v prvotno sporočilo. Usmerjanje poteka v več zaporednih korakih, ki jih imenujemo usmerjevalni koraki. V vsakem koraku se lahko paket premakne iz vozlišča, v katerem je, v eno izmed sosednjih vozlišč.
2 Splošni usmerjevalni problem
Usmerjevalni problem, kjer je sštevilo paketov določšeno pred začetkom usmerjanja in imajo vsi paketi ze pred začetkom usmerjanja določene čilje, imenujemo splošni usmerjevalni problem ali (N, p, k i , k2) -usmerjevalni problem, kjer je N število paketov, ki so na začetku usmerjanja v p vozliščih in pred začetkom usmerjanja, ni v nobenem vozlišču več kot ki in na konču več kot k2 paketov. Splošni usmerjevalni problem zajema več problemov, ki jih delimo v tri razrede.
Problemi vec vozlišč - isto sporošilo so usmerjevalni problemi, pri katerih večš vozlisščš oddaja ali sprejema isto sporočilo, torej gre za usmerjevalne probleme eden-večin veš-eden.
Izotonišni problemi so usmerjevalni problemi, pri katerih se razdalja med čelosštevilskimi reprezentačijami izvorov in čiljev paketov bodisi ohranja bodisi spreminja z natančno določenimi metričnimi pravili.
Permutačijski problemi so usmerjevalni problemi, pri katerihje podana permutačija n mnoziče vozlišč omrezja. V začetku usmerjanja je v vsakem vozlisču v omrezja natanko en paket, kije namenjen v vozlišče n(v). Gre torej za (n, n, 1,1) - usmerjevalni problem na omrezju z n vozlisči. Delni permutacijski usmerjevalni problem se od permutačijskega razlikuje po tem, da je v omrezšju manj kot n paketov, preslikava n pa je injektivna. V skrajnem primeru, ko je v omrezju le en paket, govorimo o osnovnem usmerjevalnem problemu. Preslikava n je v tem primeru transpozičija.
Naloga usmerjevalnega algoritma je resšitev usmerjevalnega problema. Algoritem za vsak podatek v omrezju določši pot, po kateri bo ta potoval po omrezšju od začšetka do čilja. Pri tem mora upoštevati vse omejitve, ki jih narekujeta topologija omrezšja in usmerjevalni problem. Preprečšiti mora trk, to je situačijo, v kateri zšeli večš sporočšil hkrati dostopati do iste povezave.
Usmerjevalne algoritme delimo na statične in di-namišne. Statični algoritmi določijo parametre potovanja paketov ze pred začetkom usmerjanja, medtem ko dinamični algoritmi pot paketov določajo sproti. Ker je rešitev danega usmerjevalnega problema lahko več, mora usmerjevalni algoritem izbrati najboljšo rešitev glede na
kriterij kakovosti.
Kakovost usmerjevalnih algoritmov lahko očenjujemo z več vidikov, odvisno od namena, načina uporabe in razpolozljivih virov. Pogost način očenjevanja je glede na prostorsko zahtevnost. Včšasih nas zanima tudi, ali je algoritem vodil pakete po najkrajših poteh in ali je vse pakete sploh dostavil. Največškrat pa algoritme očenjujemo po najdragočenejšem viru - času. Časovno zahtevnost usmerjevalnega algoritma merimo v sštevilu usmerjevalnih korakov, ki jih algoritem potrebuje, da dostavi vse pakete do čilja.
3 Optimalno permutacijsko usmerjanje na trikotniSkih mrežah
Ravninske mreze spadajo med najbolj proučevane topologije KO. Znano je, da obstajajo le tri porazdelitve ravnine v pravilne večkotnike: trikotniška porazdelitev ravnine, kvadratna porazdelitev ravnine ter porazdelitev ravnine na sšestkotnike, iz katerih dobimo trikotnisške, kvadratne in heksagonalne mrezše.
Porazdelitev ravnine na sšestkotnike je zelo primerna pri uporabi brezzičnih in mobilnih omrezij, saj imajo čeliče optimalni premer glede na območšno razmerje. Čš e čentre sosednjih čelič med sabo povezšemo, dobimo trikotnisko mrezo. Torej so heksagonalna omrezja končni podgrafi trikotniške mreze (slika 1, levo).
O
Slika 1. Heksagonalno omrežje in trikotniška mreža (levo); dvosmerna povezava (desno)
Figure 1. Hexagonal network and triangular mesh (left); a full-duplex edge (right)
V nadaljevanju bomo obravnavali optimalni permutacijski usmerjevalni algoritem za primer, ko je vsaka povezava grafa hkrati dvosmerna (slika 1, desno). Kadar to ne velja, lahko iž algoritma za dvosmerne povezave konstruiramo 2-aproksimacijo s pomočjo sodih in lihih korakov, kot je razlozeno npr. v [2].
3.1 Problem usmerjanja
V neskončni trikotniški mrezi imamo podano končno podmnozico vozlišč V in permutacijo n : V ^ V. Vsako vozlišce v iz mnozice V zeli poslati sporocilo vo-zlišcu n(v) iz V, torej imamo |V| sporocil, kijih zelimo dostaviti.
Po vsaki povezavi grafa lahko potuje v eno smer hkrati le en paket, ki v vsakem koraku algoritma bodisi počaka v vozlišču bodisi se pomakne v sosednje vozlišče. V istem vozlišču je dovoljeno čakanje več paketov hkrati, zato potrebujemo čakalne vrste. Ker je največja izhodna stopnja vozlišč grafa šest, potrebujemo v vsakem vozlišču šest vrst.
Naš čilj je minimizirati število korakov, kijih potrebujemo, da vsi paketi prispejo do svojih čiljev.
Vsakemu vozlišču mreze določimo koordinatni naslov na način, ki so ga vpeljali v [6] (slika 2). Koordinatni sistem ima tri osi x,y,z s kotom med njimi 120. Naj bodo i, j, k enotski vektorji na teh treh oseh. Ti vektorji so linearno odvisni, saj med njimi velja zveza i + j + k = 0. Vsako vozlišče grafa lahko zapišemo kot linearno kombinačijo teh vektorjev, zal pa zapis ni enoličen.
w
\ jpSwSj
Slika 2. Koordinatni sistem Figure 2. Coordinating system
Definicija 3.1 Naj bo G trikotniska mreža. Poljubno vozlišče grafa določimo za izhodišče in mu dodelimo koordinate (0,0,0). Za vsako drugo vozlišče A v grafu G obstaja vec poti od izhodišča do vozlišča A, različnih dolžin, ki so sestavljene iz a enot vektorja i, b enot vektorja j in c enot vektorja k, za neka cela števila a, b, c. Zato lahko vse te poti zapišemo kot (a, b, c) = ai + bj + ck in tak zapis vsake izmed teh poti imenujemo koordinatni naslov vozlisšcša A.
Ker med izhodiščem in vozliščem A obstaja vec poti, obstaja tudi več koordinatnih naslovov vozlišča A. Naj bo tudi (a', b',c') koordinatni naslov vozlisča A. Potem velja (a, b, c) = (a', b', c') ^ ai + bj + ck = a'i + b'j + c'k. Ce velja (a,b,c) = (a',b',c'), potem obstaja tako čelo stevilo d, da velja a' = a + d, b' = b + d, c! = c + d. Ob zdruzitvi teh dveh dejstev vidimo, da če je (a, b, c) koordinatni naslov vozlišča A, potem so vsi koordinatni naslovi vozlisča A oblike (a + d,b + d,c + d) za vsako čelo število d.
Definicija 3.2 Koordinatni naslov vozlišča A je oblike najkrajsše poti, cše obstaja pot od izhodisšcša do vozlisšcša A, ki je sestavljena iz a enot vektorja i, b enot vektorja j, c enot vektorja k in ima med vsemi najkrajšo dolšino.
Med dvema vozliščema je lahko več najkrajših poti, vendar se izkazše, da imajo vse enako vektorsko reprezentačijo.
Izrek 3.3 [6] Koordinatni naslov vozlišča A = (a,b,c) je oblike najkrajše poti natanko tedaj, ko velja:
1.	Vsaj ena komponenta je ničelna (abc = 0).
2.	Komponente so paroma različno predznašene (ab < 0, ac < 0, bc < 0).
Dokaz. Dokaz s protislovjem.
Najprej predpostavimo, da ne velja prva točka, torej abc = 0. Potem sta vsaj dve izmed sštevil a,b,c enako predznačeni. Brez izgube za splošnost lahko predpostavimo a > 0, b > 0 (druge moznosti obravnavamo analogno). Ker velja i + j + k = 0, je ai + bj + ck = ai + bj + ck - (i + j + k) = (a - 1)i +(b - 1)j + (c - 1)k. Torej je (a - 1, b - 1, c - 1) tudi koordinatni naslov vo-zlisščša A. Dolzšina poti, ki ustreza koordinatnemu naslovu (a, b, c), je enaka |a| + |b| + |c|, dolzina poti, ki ustreza koordinatnemu naslovu (a - 1, b - 1, c - 1), pa je enaka |a - 1| + |b - 1| + |c - 1|. Ker velja a > 0 in b > 0, je |a - 1| + |b - 1| + |c - 1| < |a - 1| + |b - 1| + |c| + 1 = |a| - 1 + |b| - 1 + |c| + 1 < |a| + |b| + |c|. Torej je dolzina poti, ki ustreza koordinatam (a - 1, b - 1, c - 1), krajsša od najkrajše poti (a, b, c). Prišli smo v protislovje s tem, daje (a, b, c) oblike najkrajse poti. Torej je abc = 0 in je vsaj ena komponenta ničšelna.
Zdaj predpostavimo, da ne velja druga točka, torej da komponente niso paroma različšno predznačšene. Brez izgube za splosšnost lahko predpostavimo ab > 0 (druge mozšnosti obravnavamo analogno). Potem po prvi točški velja, daje c = 0. Iz tega sledi, daje bodisi a > 0 in b > 0, bodisi a < 0 in b < 0. Potem je ai+bj+ck = ai+bj = ai + bj - (i + k + j) = (a - 1)i + (b - 1)j - k. Dolzina poti, ki ustreza (a-1,b-1, -1), je |a— 11+ |b-1| + |-1|. Kerje |a| + |b| + |c| = |a| + |b| = |a-1| + 1 + |b-1| + 1 > |a - 1| + |b - 1| + | - 1|, dobimo pot, krajšo od najkrajše. Protislovje. Zato velja ab < 0, ac < 0, bc < 0.
Zdaj moramo pokazati, da je, če veljata pogoja, koordinatni naslov (a, b, c) oblike najkrajše poti. Brez izgube za splošnost lahko predpostavimo c = 0, a > 0, b < 0 (vse druge mozšnosti obravnavamo analogno). Vsi mogočši koordinatni naslovi za vozlisščše A so oblike (a + d,b + d,c + d), za vsako čelo število d. Zdaj ločimo dve moznosti:
1.	d> 0: |a + d| + |b + d| + |c + d| = |a| + |d| + |b + d| + |d| > |a| + |d| + |b|-|d| + |d| = |a| + |b| + |d| >
|a| + |b|
2.	d < 0: |a + d| + |b + d| + |c + d| = |a + d| + |b| + |d| + |d| > |a|-|d| + |b| + |d| + |d| = |a| + |b| + |d| >
|a| + |b|
Vidimo, daje (a, b, c) res oblike najkrajše poti.	□
Posledica 3.4 [6] Koordinatni naslov, podan v obliki naj-krajsše poti, je enolicšen.
Dokaz. Ce je koordinatni naslov vozlišča A = (a, b, 0) podan v obliki najkrajše poti, potem so vsi koordinatni naslovi za A oblike (a + d, b + d, d) za vsako celo število d. (Če je d = 0, je |a + d| + |b + d| + |d| > |a| + |b|, torej mora biti d = 0 in je zapis res enoličen.	□
Na začetku permutacijskega usmerjanja vsak paket pozna svoje izvorno in ciljno vozlišče. Naj bo S izvorno vozlišče paketa in D njegovo ciljno vozlišče. Izračunamo lahko relativni naslov D — S, kije dolzina najkrajše poti med S in D.
Posledica 3.5 [6] Ceje D — S = (a, b, c) oblike najkrajše poti je dolšina najkrajše poti med S in D enaka |a| + |b| + |c|.
Izrek 3.6 [6] (je je D — S = ai + bj + ck, potem je |D — S| = min{|a—c| + |b—c|, |a—b| + |b—c|, |a—b| + |a—c|}.
Dokaz. Ker so a, b, c cela števila, je eno izmed njih vedno med drugima dvema, torej je eno število mediana vseh treh.
1.	c je mediana števil a, b, c. Potem je (a, b, c) = (a — c, b — c, 0), kije oblike najkrajše poti, zato je |D — S| = |a — c| + |b — c|.
2.	a je mediana sštevil a, b, c. Potem je (a, b, c)
Zakasnitev je dovoljena, če je lp + < lmax. Sicer je zakasnitev prepovedana. Paket p je nasičen na koncu i-tega koraka, ceje = lmax — lp.
Ideja optimalnega permutacijskega usmerjevalnega algoritma, ki ga bomo predstavili, je, da nasicšen paket ne sme več čakati, sicer algoritem ne bo več optimalen.
Na sliki 3 je prikazan mogoči paketni model. Vsak paket v tem paketnem modelu ima dve sškatli, eno dolzšine
lp, drugo pa dolzine lm
—l
v
Slika 3. Model paketa Fig. 3: Model of a package
V vsakem koraku algoritma ima paket dve mozšnosti. (Če se premakne v sosednje vozlišče, se zapolni pravokot-(0, a — b, a — c), kije oblike najkrajše poti, zato je nik v škatli dolzine lp, sicer se zapolni pravokotnik v
|D — S| = |a — b| + |a — c|.
3. b je mediana sštevil a, b, c. Potem je (a, b, c) = (a — b, 0, b — c), kije oblike najkrajše poti, zato je |D — S| = |a — b| + |b — c|.
(še vse troje zdruzšimo, res dobimo |D — S| = min{|a — c| + |b — c|, |a — b| + |b — c|, |a — b| + |a — c|}. □
3.2 Optimalni permutacijski usmerjevalni algoritem
Definicija 3.7 Naj bo p paket, podan s koordinatnim naslovom oblike najkrajše poti. Naj bo lp dolšina najkrajše poti paketa p, lmax pa naj bo najdaljša med najkrajšimi potmi vseh paketov. Potem je lp = |a| + |b| + |c|
in lm.i
maxp(lp).
Lema 3.8 Stevilo korakov kateregakoli permutacijskega usmerjevalnega algoritma je najmanj lmax.
Dokaz. lmax je najdaljša izmed najkrajših poti. Ker se paket v enem koraku lahko premakne kvečjemu za eno
škatli dolzine lmax — lp. Ce je polna prva škatla, je paket na cilju. (Ce se zapolni druga škatla, je paket nasičen in ne sme več čakati. Model, kije prikazan na sliki 3, rabi zgolj za analitične namene. V resnici paket ne potrebuje vseh informacij, na vsakem koraku potrebuje le vrednosti lp in .
Predpostavimo še, da ima omrezje globalno uro in da so vsa vozlišča sinhronizirana. Paketi se premikajo le ob diskretnih urnih ciklih, druge naloge so narejene v vmesnem času.
V nadaljevanju bomo podrobneje predstavili optimalni permutacijski algoritem A in podrobneje opisali pomembnejše postopke. Predpostavimo lahko, da je število vozlisc grafa končno, torej neko naravno stevilo n. Cea je vozlišč neskončno, dobimo neskončno zanko. Algoritem A
V vsakem vozlišču u omrezja naredi: begin
PREDPROCESIRANJE; i = 0;
while i < lm
do
enoto, potrebujemo vsaj lmax korakov.
□
Definicija 3.9 Pravimo, da paketa p in p' trkneta, ce sta hkrati v isti izhodni vrsti istega vozlišča. Ce hkrati trkne vec paketov, se kvečjemu eden izmed njih pomakne naprej.
Definicija 3.10 Stevilu korakov, kijih paket p šaka do istega koraka permutacijskega usmerjevalnega algoritma, pravimo cšas cšakanja paketa p ali krajsše, zakasnitev paketa p. Oznašimo jo s .
//* Faza sprejemanja: za vsak paket v vozlišču u
POSODOBI_PAKET; //* Faza pošiljanja: za vsak paket v vozlišču u
DOLOČI_IZHODNO_POVEZAVO; za vsako vrsto UREDI_VRSTO; pošlji prvi paket; i = i +1
endwhile end
3.2.1	Postopek PREDPROCESIRANJE
Pred začšetkom usmerjanja je v vsakem vozlisščšu en paket, ki pozna svoje čiljno vozlišče D. Zato lahko vsako izvorno vozlišče S izračuna koordinatni naslov paketa D — S = (a, b, c). Po izreku 3.6 je dovolj preveriti, kateri izmed koordinatnih naslovov (0, b — a, c — a), (a — b, 0, c — b), (a — c, b — c, 0) ima neničelni koordinati različno predznačeni. Nato izračunamo dolzino najkrajše poti med S in D, kije lp = |a| + |b| + |c|. Vsakemu paketu se doda se glava, ki nosi informačije o D — S, lp in števču .
(Časovna zahtevnost predpročesiranja je O(1), če je treba določiti fiksno stevilo naslovov, sičer pa O (log n), kjer je n največja velikost števila, ki je potrebno za določitev naslovov vozlišč.
3.2.2	Postopek POSODOBI_PAKET
Posodobitev koordinatnega naslova na vsakem koraku algoritma pripomore k večji robustnosti. Preveriti moramo, ali je paket ze v čiljnem vozlišču ali ne. Vsako vozlišče ima sšest vhodnih povezav, ki jih lahko brez izgube za splošnost označimo, kot je prikazano na sliki 4 levo.
Slika 4. Vhodne povezave (levo); izhodne povezave (desno) Figure 4. Input edges (left); output edges (right)
Postopek POSODOBI_PAKET izračuna razliko med starim naslovom in vhodno povezavo in to razliko priredi kot novi naslov. (Če je razlika enaka (0,0,0), je paket ze v čiljnem vozlišču, sičer se ni.
3.2.3 Procedura DOLOČI_IZHODNO_POVEZAVO
S pomočjo pročedure DOLOČI_IZHODNO_POVEZAVO se odločšimo, po kateri se bo paket premaknil. Vsako vo-zlisščše ima sšest izhodnih povezav, ki jih lahko brez izgube za splosšnost označšimo, kot je prikazano na sliki 4 desno.
Vseh |V | koordinatnih naslovov lahko razdelimo v 12 disjunktnih razredov glede na predznake koordinat: (+, 0, 0), (—, 0, 0), (0, +, 0), (0, —, 0), (0,0, +), (0, 0, —), (+, —, 0), (+, 0, —), (—, +, 0), ( —, 0, +), (0, +, —) in (0, —, +).
Postopek DOLOČI_IZHODNO_POVEZAVO doloci, v katero smer se bo paket premaknil v naslednjem koraku: begin
if koordinatni naslov ima le eno nenicelno komponento then
izhodna_povezava = povezava, ki ustreza nenicelni komponenti;
else
izhodna_povezava = povezava, ki ustreza negativni komponenti; endif end
3.2.4 Postopek UREDI_VRSTO
Vsako vrsto uredimo po padajočem številu preostalih korakov. Torej paket, ki ima se največ preostalih korakov, ima prioriteto 1, naslednji ima prioriteto 2 itd. Ta ureditev je optimalna, kot bomo pokazali v nadaljevanju.
Zaradi optimalnosti je pomembno, kako uredimo vrsto. Druga mozšnost bi bila, da pakete razvrstimo po dolzini njihove poti lp in potem v primeru enakosti po sštevilu preostalih korakov. Vendar druga mozšnost vodi do neoptimalnega algoritma. (Primer je dan v [5], glej tudi [6].)
Lema 3.11 [5] Paket lahko čaka le pred zadnjo smerjo.
Dokaz. Denimo, da dva paketa trkneta, ko imata še dve neničelni komponenti. Po postopku DOLOČI_IZHODNO_POVEZAVO mora biti smer, v kateri potujeta paketa ista, zato bi morala imeti isto izvorno voz-lisče. Protislovje s tem, da ima vsak paket v permutačij-skem usmerjanju različno izvorno vozlišče.
Paketi, ki imajo le eno neničšelno komponento, lahko trknejo le pred smerjo, ki ustreza tej komponenti. Torej paketi res čakajo le pred zadnjo smerjo.	□
Lema 3.12 [5] Paketa v dani vrsti ne moreta imeti istega čtevila preostalih korakov.
Dokaz. (Če sta paketa p in p' v isti vrsti, morata biti pred svojo zadnjo smerjo. Če bi imela isto stevilo preostalih korakov, bi imela isto čiljno vozlišče. Protislovje s tem, da ima vsak paket v permutačijskem usmerjanju različšno čiljno vozlisče.	□
3.3 Dokaz optimalnosti algoritma
Lema 3.13 [5] Naslednji razvrstitvi paketov sta ekvivalentni.
1.	Razvrstitev paketov v vrsto po padajočem številu preostalih korakov
2.	Razvrstitev paketov v vrsto po naraščajočem številu dovoljene zakasnitve
Dokaz. Število preostalih korakov paketa p po i-tem koraku algoritma je lp — (i — wp) = lp — i + wp. Preostalo Število dovoljene zakasnitve paketa p po i-tem koraku algoritma pa je lmax — lp — wp. Števili se poleg predznaka razlikujeta le v konstantah i in lmax, torej je razvrstitev res ekvivalentna.	□
Trditev 3.14 [5] Algoritem A ne povzroči dodatne zakasnitve paketov.
Dokaz. Z indukcijo po številu korakov bomo pokazali, da ni dodatne zakasnitve po i-tih korakih.
Baza indukcije, i = 1. Po prvem koraku so nasičeni le paketi z dolzino lmax. Ker so vsi paketi na začetku usmerjanja v različnih vozliščih, po prvem koraku ne moreta biti dva v isti vrsti istega vozlišča. Zato imajo vsi paketi z dolzino poti lmax največjo prioriteto glede na število preostalih korakov in zato noben ne čaka.
Korak indukčije. Zdaj predpostavimo, da po i — 1 korakih ni bilo dodatne zakasnitve in dokazimo, da je ni niti po i-tem koraku. Zadošča pokazati, da je v vsaki čšakalni vrsti le en nasičšen paket. Predpostavimo nasprotno. Denimo, da sta p in p' oba nasičena paketa v isti vrsti. Potem po definičiji nasičenosti velja lp + wp = lp' + wp' = lmax. Število preostalih korakov paketa p je lp — (i — wp) = lmax — i, stevilo preostalih korakov paketa p' pa je lp' — (i — wp') = lmax — i. Torej imata p in p' pred zadnjo smerjo še isto število korakov in zato isto čiljno vozlišče. Protislovje, saj v permutačijskem usmerjanju dva paketa ne moreta imeti istega čiljnega vozlišča. □
Izrek 3.15 [5] Algoritem A je optimalni permutacijski algoritem za trikotnisčke mrezče z dvosmernimi povezavami.
Dokaz. Zaradi trditve 3.14 vsi paketi dosezejo čilje v največ lmax korakih, torej je dosezena spodnja meja. □
Definicija 3.16 Usmerjevalni algoritem je pozabljiv, ce je pot vsakega paketa p odvisna le od njegovega izvornega in ciljnega vozlišča, Čepravje cas čakanja v vmesnih vo-zliččih odvisen od drugih poti.
Definicija 3.17 Naj bo Puv pot med vozliščema u in v. Pozabljiv algoritem Puv : u, v G V je translacijsko invarianten, ceje P(u+w)(v+w) = Puv+w za Vu, v,w G V.
Posledica 3.18 [4] Algoritem A je pozabljiv, translacijsko invarianten in optimalen.
Dokaz. Pozabljiv je očitno, saj algoritem potrebuje za pot vsakega paketa le izvorno in čiljno vozlišče. Ker je za usmerjanje pomembna le razlika D — S med izvornim vozlisčem S in čiljnim vozliščem D, je algoritem translačijsko invarianten.	□
4	Sklep
Obravnavali smo problem optimalnega permutacijskega usmerjanja in optimalne permutacijske usmerjevalne algoritme na trikotnih mrežah. Algoritem za trikotne mreže usmeri vsako permutacijo v lmax korakih, kjer lmax označuje najdaljšo med vsemi najkrajšimi potmi paketov.
5	Literatura
[1]	T. Dobravec, Usmerjevalni algoritmi v omrežjih s topologijo krožnih grafov, doktorska dizertacija, Univerza v Ljubljani, Fakulteta za racunalništvo in informatiko, 2004.
[2]	T. Dobravec, J. Zerovnik, B. Robic, Permutation Routing in Double-Loop Networks: Design and Empirical Evaluation, Journal of Systems Architecture, 48(13-14):387-402, 2003.
[3]	T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes, Morgan-Kaufman, San Mateo, California, 1992.
[4]	M. Rotovnik, Optimalno permutacijsko usmerjanje, Diplomska naloga, Univerza v Mariboru, Fakulteta za naravoslovje in matematiko, Maribor, 2008.
[5]	I. Sau Walls, J. Zerovnik, An Optimal Permutation Routing Algorithm for Full-Duplex Hexagonal Mesh Networks, Discrete Mathematics and Theoretical Computer Science, 10(3):49-62, 2008.
[6]	I. Stojmenovic, Honeycomb networks: topological properties and communication algorithms, IEEE Transactions on Parallel and Distributed Systems, 8(10):1036-1042, 1997.
[7]	J. Zerovnik, Usmerjanje sporocil v grafih, Obzornik za matematiko in fiziko, 51(6):161-170, 2004.
Maja Rotovnik je univerzitetna diplomirana matematicarka in je zaposlena kot mlada raziskovalka na Inštitutu za matematiko, fiziko in mehaniko v Ljubljani.
Jurij ¿Sile je višji znanstveni sodelavec na Odseku za računalniške sisteme na Institutu "Jozef Stefan" v Ljubljani in docent za napredno procesorsko arhitekturo na Mednarodni podiplomski šoli Jozefa Stefana v Ljubljani. Raziskovalno se ukvarja z racšunalnisškimi sistemi in strukturami ter meta-hevristicšnim optimiziranjem.
Janez Žerovnik je redni profesor za matematiko na Univerzi v Ljubljani, do leta 2008 pa je bil redni profesor za diskretno in racšunalnisško matematiko in redni profesor za racšunalnisštvo na Univerzi v Mariboru. Dopolnilno je zaposlen kot raziskovalec na Inštitutu za matematiko, fiziko in mehaniko v Ljubljani. Raziskovalno dela predvsem na podrocju diskretne optimizacije in teorije grafov z aplikacijami.