1 Uvod
Teorija grafov je ena najbolj proučevanih in uporabnih
matematičnih smeri v zadnjih nekaj desetletjih. Ap-
likacije, ki jih lahko predstavimo z grafi, najdemo na
več različnih področjih, kot so operacijske raziskave,
družboslovje, kemija, računalniške mreže in predvsem
komunikacijska omrežja (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
Prejet 6. avgust, 2008
Odobren 20. oktober, 2008
so povezave grafa. Osnovna naloga KO je omogočanje
izmenjave podatkov med BP. Način izbire poti, po ka-
terih se bodo podatki premikali, imenujemo usmerjanje
in je bistvenega pomena za uspešno delovanje KO, saj
lahko slaba izbira vodi do neučinkovitega in počasnega
omrežja. Če usmerjanje povezuje vse (urejene) pare voz-
lišč, ga imenujemo popolno usmerjanje, sicer ga imenu-
jemo delno usmerjanje. Literature na tu obravnavano
temo je veliko, tu omenimo samo pogosto citirano 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-
lišč, 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 last-
nosti, ni, saj z zmanjševanjem stopnje vozlišč večamo pre-
mer. Topologijo izberemo torej glede na pomembnost
teh lastnosti v KO. Najbolj znane topologije so mreže.
Povezave med vozlišči KO so lahko neusmerjene, usmer-
jene ali hkratno dvosmerne. Glede na vrsto povezav, ki
so v posameznem KO, ločimo različne modele usmer-
janja: neusmerjen model, ki omogoča pretok podatkov po
povezavi v obe smeri, vendar le v eno smer hkrati, us-
merjen 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
20 Rotovnik, Šilc, Žerovnik
določa način izmenjave sporočil. Poznamo več tipov us-
merjevalnih modelov, kot npr. preklapljanje povezav, us-
merjanje 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, ki je enak cilju prvotnega sporočila.
Ko paketi prispejo na cilj, 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 število paketov določeno
pred začetkom usmerjanja in imajo vsi paketi že pred
začetkom usmerjanja določene cilje, imenujemo splošni
usmerjevalni problem ali (N, p, k1, k2)-usmerjevalni
problem, kjer je N število paketov, ki so na začetku us-
merjanja v p vozliščih in pred začetkom usmerjanja, ni v
nobenem vozlišču več kot k1 in na koncu več kot k2 pake-
tov. Splošni usmerjevalni problem zajema več problemov,
ki jih delimo v tri razrede.
Problemi več vozlišč – isto sporočilo so usmerjevalni
problemi, pri katerih več vozlišč oddaja ali sprejema isto
sporočilo, torej gre za usmerjevalne probleme eden-več in
več-eden.
Izotonični problemi so usmerjevalni problemi, pri ka-
terih se razdalja med celoštevilskimi reprezentacijami
izvorov in ciljev paketov bodisi ohranja bodisi spreminja
z natančno določenimi metričnimi pravili.
Permutacijski problemi so usmerjevalni problemi, pri
katerih je podana permutacija Π množice vozlišč omrežja.
V začetku usmerjanja je v vsakem vozlišču v omrežja
natanko en paket, ki je namenjen v vozlišče Π(v). Gre
torej za (n, n, 1, 1) - usmerjevalni problem na omrežju z n
vozlišči. Delni permutacijski usmerjevalni problem se od
permutacijskega razlikuje po tem, da je v omrežju manj
kot n paketov, preslikava Π pa je injektivna. V skraj-
nem primeru, ko je v omrežju le en paket, govorimo o
osnovnem usmerjevalnem problemu. Preslikava Π je v
tem primeru transpozicija.
Naloga usmerjevalnega algoritma je rešitev usmerje-
valnega problema. Algoritem za vsak podatek v omrežju
določi pot, po kateri bo ta potoval po omrežju od začetka
do cilja. Pri tem mora upoštevati vse omejitve, ki jih
narekujeta topologija omrežja in usmerjevalni problem.
Preprečiti mora trk, to je situacijo, v kateri ž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 že pred začetkom usmerjanja, medtem ko di-
namič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 ocenjujemo
z več vidikov, odvisno od namena, načina uporabe in
razpoložljivih virov. Pogost način ocenjevanja 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
ocenjujemo po najdragocenejšem viru – času. Časovno
zahtevnost usmerjevalnega algoritma merimo v številu
usmerjevalnih korakov, ki jih algoritem potrebuje, da
dostavi vse pakete do cilja.
3 Optimalno permutacijsko usmerjanje na
trikotniških mrežah
Ravninske mreže 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 šestkotnike, iz katerih dobimo trikotniške,
kvadratne in heksagonalne mreže.
Porazdelitev ravnine na šestkotnike je zelo primerna
pri uporabi brezžičnih in mobilnih omrežij, saj imajo
celice optimalni premer glede na območno razmerje.
Če centre sosednjih celic med sabo povežemo, dobimo
trikotniško mrežo. Torej so heksagonalna omrežja končni
podgrafi trikotniške mreže (slika 1, levo).
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 per-
mutacijski usmerjevalni algoritem za primer, ko je vsaka
povezava grafa hkrati dvosmerna (slika 1, desno). Kadar
to ne velja, lahko iz algoritma za dvosmerne povezave
konstruiramo 2-aproksimacijo s pomočjo sodih in lihih
korakov, kot je razloženo npr. v [2].
3.1 Problem usmerjanja
V neskončni trikotniški mreži imamo podano končno
podmnožico vozlišč V in permutacijo Π : V → V .
Vsako vozlišče v iz množice V želi poslati sporočilo vo-
zlišču Π(v) iz V , torej imamo |V | sporočil, ki jih želimo
dostaviti.
Optimalno permutacijsko usmerjanje v heksagonalnih omrežjih 21
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 is-
tem vozlišču je dovoljeno čakanje več paketov hkrati, zato
potrebujemo čakalne vrste. Ker je največja izhodna stop-
nja vozlišč grafa šest, potrebujemo v vsakem vozlišču šest
vrst.
Naš cilj je minimizirati število korakov, ki jih potre-
bujemo, da vsi paketi prispejo do svojih ciljev.
Vsakemu vozlišču mreže 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
kombinacijo teh vektorjev, žal pa zapis ni enoličen.
Slika 2. Koordinatni sistem Figure 2. Coordinating system
Definicija 3.1 Naj bo G trikotniška mreža. Poljubno vo-
zlišče grafa določimo za izhodišče in mu dodelimo koor-
dinate (0, 0, 0). Za vsako drugo vozlišče A v grafu G ob-
staja več 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
vozlišča A.
Ker med izhodiščem in vozliščem A obstaja več poti,
obstaja tudi več koordinatnih naslovov vozlišča A. Naj bo
tudi (a′, b′, c′) koordinatni naslov vozlišča A. Potem velja
(a, b, c) = (a′, b′, c′) ⇔ ai + bj + ck = a′i + b′j + c′k.
Če velja (a, b, c) = (a′, b′, c′), potem obstaja tako celo
število d, da velja a′ = a + d, b′ = b + d, c′ = c + d.
Ob združitvi teh dveh dejstev vidimo, da če je (a, b, c)
koordinatni naslov vozlišča A, potem so vsi koordinatni
naslovi vozlišča A oblike (a + d, b + d, c + d) za vsako
celo število d.
Definicija 3.2 Koordinatni naslov vozlišča A je oblike
najkrajše poti, če obstaja pot od izhodišča do vozlišč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 izkaže, da imajo vse enako vektorsko
reprezentacijo.
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 6= 0. Potem sta vsaj dve izmed števil a,b,c
enako predznačeni. Brez izgube za splošnost lahko pred-
postavimo a > 0, b > 0 (druge možnosti 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-
zlišča A. Dolžina poti, ki ustreza koordinatnemu naslovu
(a, b, c), je enaka |a| + |b| + |c|, dolžina 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 dolžina
poti, ki ustreza koordinatam (a − 1, b − 1, c − 1), krajša
od najkrajše poti (a, b, c). Prišli smo v protislovje s tem,
da je (a, b, c) oblike najkrajše 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 splošnost lahko predpostavimo ab > 0 (druge
možnosti obravnavamo analogno). Potem po prvi točki
velja, da je c = 0. Iz tega sledi, da je 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. Dolžina
poti, ki ustreza (a−1, b−1,−1), je |a−1|+|b−1|+|−1|.
Ker je |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 možnosti obravnavamo analogno).
Vsi mogoči koordinatni naslovi za vozlišče A so oblike
(a + d, b + d, c + d), za vsako celo število d. Zdaj ločimo
dve možnosti:
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, da je (a, b, c) res oblike najkrajše poti. �
Posledica 3.4 [6] Koordinatni naslov, podan v obliki naj-
krajše poti, je enoličen.
22 Rotovnik, Šilc, Žerovnik
Dokaz. Če 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 6= 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, ki je dolžina najkrajše poti
med S in D.
Posledica 3.5 [6] Če je 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] Če 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), ki je oblike najkrajše poti, zato je |D −
S| = |a − c| + |b − c|.
2. a je mediana števil a, b, c. Potem je (a, b, c) =
(0, a − b, a − c), ki je oblike najkrajše poti, zato je
|D − S| = |a − b| + |a − c|.
3. b je mediana števil a, b, c. Potem je (a, b, c) = (a −
b, 0, b − c), ki je oblike najkrajše poti, zato je |D −
S| = |a − b| + |b − c|.
Če vse troje združ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 naj-
krajše poti paketa p, lmax pa naj bo najdaljša med na-
jkrajšimi potmi vseh paketov. Potem je lp = |a|+ |b|+ |c|
in lmax = maxp(lp).
Lema 3.8 Število 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
enoto, potrebujemo vsaj lmax korakov. �
Definicija 3.9 Pravimo, da paketa p in p′ trkneta, če sta
hkrati v isti izhodni vrsti istega vozlišča. Če hkrati trkne
več paketov, se kvečjemu eden izmed njih pomakne naprej.
Definicija 3.10 Številu korakov, ki jih paket p čaka do i-
tega koraka permutacijskega usmerjevalnega algoritma,
pravimo čas čakanja paketa p ali krajše, zakasnitev
paketa p. Označimo jo s wip.
Zakasnitev wip je dovoljena, če je lp + w
i
p ≤ lmax.
Sicer je zakasnitev prepovedana. Paket p je nasičen na
koncu i-tega koraka, če je wip = lmax − lp.
Ideja optimalnega permutacijskega usmerjevalnega al-
goritma, ki ga bomo predstavili, je, da nasič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 škatli, eno dolžine
lp, drugo pa dolžine lmax − lp.
Slika 3. Model paketa Fig. 3: Model of a package
V vsakem koraku algoritma ima paket dve možnosti.
Če se premakne v sosednje vozlišče, se zapolni pravokot-
nik v škatli dolžine lp, sicer se zapolni pravokotnik v
škatli dolžine lmax − lp. Če je polna prva škatla, je paket
na cilju. Če se zapolni druga škatla, je paket nasičen in
ne sme več čakati. Model, ki je 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 w
i
p.
Predpostavimo še, da ima omrežje globalno uro in da
so vsa vozlišča sinhronizirana. Paketi se premikajo le ob
diskretnih urnih ciklih, druge naloge so narejene v vmes-
nem času.
V nadaljevanju bomo podrobneje predstavili opti-
malni permutacijski algoritem A in podrobneje opisali
pomembnejše postopke. Predpostavimo lahko, da je
število vozlišč grafa končno, torej neko naravno število
n. Čea je vozlišč neskončno, dobimo neskončno zanko.
Algoritem A
V vsakem vozlišču u omrežja naredi:
begin
PREDPROCESIRANJE;
i = 0;
while i < lmax do
//* 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
Optimalno permutacijsko usmerjanje v heksagonalnih omrežjih 23
endwhile
end
3.2.1 Postopek PREDPROCESIRANJE
Pred začetkom usmerjanja je v vsakem vozlišču en paket,
ki pozna svoje ciljno 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, ka-
teri izmed koordinatnih naslovov (0, b − a, c − a), (a −
b, 0, c − b), (a − c, b − c, 0) ima neničelni koordinati ra-
zlično predznačeni. Nato izračunamo dolžino najkrajše
poti med S in D, ki je lp = |a| + |b| + |c|. Vsakemu
paketu se doda še glava, ki nosi informacije o D − S, lp
in števcu wip.
Časovna zahtevnost predprocesiranja je O(1), če je
treba določiti fiksno število naslovov, sicer 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 al-
goritma pripomore k večji robustnosti. Preveriti moramo,
ali je paket že v ciljnem vozlišču ali ne. Vsako vozlišče
ima š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 že
v ciljnem vozlišču, sicer še ni.
3.2.3 Procedura DOLOČI IZHODNO POVEZAVO
S pomočjo procedure DOLOČI IZHODNO POVEZAVO se
odločimo, po kateri se bo paket premaknil. Vsako vo-
zlišče ima šest izhodnih povezav, ki jih lahko brez izgube
za splošnost označimo, kot je prikazano na sliki 4 desno.
Vseh |V | koordinatnih naslovov lahko razdelimo v
12 disjunktnih razredov glede na predznake koordi-
nat: (+, 0, 0), (−, 0, 0), (0,+, 0), (0,−, 0), (0, 0,+),
(0, 0,−), (+,−, 0), (+, 0,−), (−,+, 0), (−, 0,+),
(0,+,−) in (0,−,+).
Postopek DOLOČI IZHODNO POVEZAVO določi, v
katero smer se bo paket premaknil v naslednjem koraku:
begin
if koordinatni naslov ima le eno neničelno komponento
then
izhodna povezava =
povezava, ki ustreza neničelni 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 ko-
rakov. Torej paket, ki ima še 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 možnost bi bila, da pakete razvrstimo po
dolžini njihove poti lp in potem v primeru enakosti po
številu preostalih korakov. Vendar druga mož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-
lišče. Protislovje s tem, da ima vsak paket v permutacij-
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 število preostalih
korakov, bi imela isto ciljno vozlišče. Protislovje s tem,
da ima vsak paket v permutacijskem usmerjanju različno
ciljno vozlišče. �
3.3 Dokaz optimalnosti algoritma
Lema 3.13 [5] Naslednji razvrstitvi paketov sta ekviva-
lentni.
1. Razvrstitev paketov v vrsto po padajočem številu pre-
ostalih korakov
2. Razvrstitev paketov v vrsto po naraščajočem številu
dovoljene zakasnitve
Dokaz. Število preostalih korakov paketa p po i-tem ko-
raku algoritma je lp − (i − w
i
p) = lp − i + w
i
p. Preostalo
število dovoljene zakasnitve paketa p po i-tem koraku al-
goritma pa je lmax − lp − w
i
p. Š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 zakas-
nitve 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 dolžino lmax. Ker so vsi paketi na začetku us-
merjanja v različnih vozliščih, po prvem koraku ne moreta
biti dva v isti vrsti istega vozlišča. Zato imajo vsi paketi z
dolžino poti lmax največjo prioriteto glede na število pre-
ostalih korakov in zato noben ne čaka.
Korak indukcije. Zdaj predpostavimo, da po i − 1
korakih ni bilo dodatne zakasnitve in dokažimo, 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 definiciji nasičenosti velja lp + w
i
p =
lp′ + w
i
p′
= lmax. Število preostalih korakov paketa p
je lp − (i − w
i
p) = lmax − i, število preostalih korakov
paketa p′ pa je lp′ −(i−w
i
p′
) = lmax− i. Torej imata p in
p′ pred zadnjo smerjo še isto število korakov in zato isto
ciljno vozlišče. Protislovje, saj v permutacijskem usmer-
janju dva paketa ne moreta imeti istega ciljnega vozlišča.
�
Izrek 3.15 [5] Algoritem A je optimalni permutacijski al-
goritem za trikotniške mreže z dvosmernimi povezavami.
Dokaz. Zaradi trditve 3.14 vsi paketi dosežejo cilje v
največ lmax korakih, torej je dosežena spodnja meja. �
Definicija 3.16 Usmerjevalni algoritem je pozabljiv, če
je pot vsakega paketa p odvisna le od njegovega izvornega
in ciljnega vozlišča, čeprav je čas č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 ∈ V je translacijsko in-
varianten, če je P(u+w)(v+w) = Puv+w za ∀u, v, w ∈ V .
Posledica 3.18 [4] Algoritem A je pozabljiv, trans-
lacijsko invarianten in optimalen.
Dokaz. Pozabljiv je očitno, saj algoritem potrebuje za
pot vsakega paketa le izvorno in ciljno vozlišče. Ker
je za usmerjanje pomembna le razlika D − S med
izvornim vozliščem S in ciljnim vozliščem D, je algo-
ritem translacijsko invarianten. �
4 Sklep
Obravnavali smo problem optimalnega permutacijskega
usmerjanja in optimalne permutacijske usmerjevalne al-
goritme 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 računalništvo in informatiko,
2004.
[2] T. Dobravec, J. Žerovnik, B. Robič, Permutation Routing
in Double-Loop Networks: Design and Empirical Evalua-
tion, 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 nar-
avoslovje in matematiko, Maribor, 2008.
[5] I. Sau Walls, J. Žerovnik, An Optimal Permutation Rout-
ing Algorithm for Full-Duplex Hexagonal Mesh Net-
works, Discrete Mathematics and Theoretical Computer
Science, 10(3):49–62, 2008.
[6] I. Stojmenović, Honeycomb networks: topological prop-
erties and communication algorithms, IEEE Transactions
on Parallel and Distributed Systems, 8(10):1036–1042,
1997.
[7] J. Žerovnik, Usmerjanje sporočil v grafih, Obzornik za
matematiko in fiziko, 51(6):161-170, 2004.
Maja Rotovnik je univerzitetna diplomirana matematičarka in
je zaposlena kot mlada raziskovalka na Inštitutu za matematiko,
fiziko in mehaniko v Ljubljani.
Jurij Šilc je višji znanstveni sodelavec na Odseku za
računalniške sisteme na Institutu “Jožef Stefan” v Ljubljani
in docent za napredno procesorsko arhitekturo na Mednaro-
dni podiplomski šoli Jožefa Stefana v Ljubljani. Raziskovalno
se ukvarja z računalniškimi sistemi in strukturami ter meta-
hevrističnim optimiziranjem.
Janez Žerovnik je redni profesor za matematiko na Univerzi
v Ljubljani, do leta 2008 pa je bil redni profesor za diskretno
in računalniško matematiko in redni profesor za računalništvo
na Univerzi v Mariboru. Dopolnilno je zaposlen kot razisko-
valec na Inštitutu za matematiko, fiziko in mehaniko v Ljubljani.
Raziskovalno dela predvsem na področju diskretne optimizacije
in teorije grafov z aplikacijami.