sosednjih vozlišč. Ko je ažuriranje končano, vozlišče spet neposredno preide v stanje poslušanja.
5.4 Dinamičnost navideznega omrežja v predlaganih
vozlišča in lahko se zgodi, da bo njena življenjska doba (število skokov) že pri koncu, tako da tudi poplava ne bo zajela dovolj vozlišč za iskanje odgovora. Veliko takih poizvedb bo ostalo neodgovorjenih.
Ob tej priložnosti bi bilo možno seveda podaljšati preostalo življenjsko dobo poizvedbe in tako omogočiti poplavo popolne velikosti. Pomislek proti tej izvedbi pa je, da bi takšna "oddaljena" poplava ignorirala morebitne odgovore, ki so blizu izvora poizvedbe, in našla takšne, ki se nahajajo več skokov stran. Slika 5-6 predstavlja opisani različici poplave. Očitno je ta rešitev sicer izvedljiva, vendar pa je precej okorna in zato lahko poskusimo najti učinkovitejšo.
nedostopno vozlišče
območje poplave
po podaljšanju življenjske dobe poizvedbe
nedostopno vozlišče
območje poplave
Slika 5-6: Primerjava območja poplave pri nespremenjeni življenjski dobi poizvedbe in pri podaljšani življenjski dobi poizvedbe; oboje v primeru, ko eno od vozlišč na poti do
rezultata postane nedostopno.
5.4.1.2 Izvorno vozlišče
Poplavo lahko sproži izvorno vozlišče, če ne dobi odgovora v pričakovanem času.
Težava pa je v tem, da izvorno vozlišče poizvedbo vdrugo sicer lahko pošlje vsem svojim sosedom, vendar je možno, da so tudi sosedje že prej posredovali odgovor nanjo in jo bodo zato posredovali naprej samo po poti, za katero smo ravnokar ugotovili, da ni uporabna. Zato bi bilo potrebno uvesti novo protokolarno sporočilo: poizvedba z obveznim poplavljanjem, ki bi jo poplavila vsa vozlišča, tudi tista, ki so že
"skonfigurirana" za iskano vsebino. To bi med drugim prineslo težave glede zagotavljanja združljivosti z vozlišči, ki delujejo po osnovnem protokolu in ne poznajo
novega tipa sporočila. Potrebno bi bilo tudi zagotoviti preprečevanje možnosti zlorabe, saj bi lahko dovolj spretni in preveč neučakani uporabniki (ali razvijalci aplikacij) za vse poizvedbe že takoj zahtevali poplavljanje, kar bi seveda pomenilo korak nazaj glede agregirane obremenitve navideznega omrežja.
5.4.1.3 Uporabnik
Poplavo bi seveda lahko sprožil tudi uporabnik, ki dovolj dolgo ne bi dobil odgovora.
Seveda je tu možnost zlorab še večja, poleg tega pa nalogo, ki bi jo lahko opravil sistem sam, a tem prelagamo na uporabnika. Uporabnika načeloma ne zanimajo detajli iskanja, kot na primer ali je bil odgovor najden s pomočjo poplave ali ne, zato to možnost lahko kar takoj izločimo.
5.4.1.4 Vsa vmesna vozlišča
Poplavo lahko sprožijo vsa vozlišča od izvora do vozlišča, ki je ugotovilo, da naslednji sosed ni več dostopen. Vozlišča so nekoč pred tem že videla odgovor na trenutno poizvedbo in si ga tudi zapomnila. Zapomnila so si tudi čas, ki je minil od trenutka takratnega posredovanja poizvedbe do sprejema odgovora. Zdaj lahko domnevajo, da mora odgovor prispeti po preteku podobnega časovnega intervala (upošteva naj se še nek smiseln, okoliščinam ustrezen varnostni faktor). Če po preteku tega časa odgovora ni, vsako vmesno vozlišče na poti od izvora poizvedbe sproži poplavo, če le poizvedbe ni poplavilo že prvič. Vozlišča, ki so poizvedbo poplavila že prej, odgovora še niso videla in zato ne morejo oceniti tega časovnega intervala, poleg tega pa s ponovno poplavo k rešitvi ne bi prinesla nič novega.
Dobra lastnost zadnjega načina je, da je časovno in glede števila prenosov poizvedbe popolnoma primerljiv s poplavo, ki jo sproži izvorno vozlišče, vendar ne zahteva uvedbe novega protokolarnega sporočila. Res pa zahteva več administracije in več virov na vsakem sodelujočem vozlišču. Največja prednost tega načina pa je bistveno boljši odzivni čas kot pri poplavi, ki jo zahteva izvorno vozlišče. Prepričajmo se.
nedostopno vozlišče
območje poplave
pri obveznem poplavljanju od izvora
nedostopno vozlišče
območje poplave pri poplavljanju na vseh vmesnih vozliščih
Slika 5-7: Primerjava poplave s strani izvornega vozlišča in poplave s strani vseh vmesnih vozlišč; oboje po odpovedi enega od vozlišč na poti do odgovora. Območji se
prostorsko prekrivata (zajameta ista vozlišča), lahko pa pride do časovnih razlik.
Denimo, da izvorno vozlišče domneva, da je vozlišče odgovora oddaljeno največ t skokov in zato mora odgovor dobiti v času 2t skokov. Če odgovora v tem času ne dobi, sproži poplavo, med katero se najde alternativen odgovor, oddaljen s skokov. Skupen čas, ki poteče od prvotne poizvedbe do sprejetja odgovora, je torej 2t + 2s:
s t
Tizvor =2 +2 (5.1)
Če pa imajo tak mehanizem časovne kontrole vgrajena tudi vsa vmesna vozlišča, velja za vozlišče, ki je od izvornega oddaljeno en skok, naslednji razmislek: vozlišče pričakuje odgovor v času (t - 1) skokov. Če ga v tem času ne dobi, sproži poplavo, ki po (s – 1) skokih doseže vozlišče odgovora, odgovor pa se vrne po 2(t – 1) + 2(s – 1) skokih, nakar je potreben še en skok, da odgovor posredujemo do izvornega vozlišča. Upoštevati moramo tudi prvi skok, ki ga je opravila poizvedba, da je prišla do tega vozlišča, in tako je skupno število skokov, potrebnih, da odgovor doseže izvorno vozlišče, naslednje:
2 2 2 1 ) 1 ( 2 ) 1 ( 2
1+ − + − + = + −
= t s t s
Tenskok (5.2)
Če je vmesno vozlišče od izvornega odmaknjeno dva skoka, po enakem razmisleku ugotovimo, da se na izvorno vozlišče vrne odgovor po 2t + 2s – 4 skokih, če pa je vmesno vozlišče odmaknjeno od izvornega n skokov, odgovor doseže izvorno vozlišče po 2t + 2s – 2n skokih.
V splošnem primeru poplavo sprožijo vsa vmesna vozlišča, ki je niso sprožila že ob sprejemu poizvedbe. Izvorno vozlišče najprej doseže najbližji odgovor, torej velja
n s t n n s n t n
Tvsavozl. = +2( − )+2( − )+ =2 +2 −2 . (5.3) Zaradi naštetih razlogov smo se pri izvedbi simulacije odločili za poplavo s strani vseh vmesnih vozlišč.
Opozorimo naj še, da pri poplavi s strani vseh vmesnih vozlišč ni število prenosov sporočil nič večje kot pri obvezni poplavi, saj še vedno velja, da vozlišča pomnijo GUID – identifikator poizvedbe, in ko sprejmejo isto poizvedbo drugič, je ne posredujejo naprej.
5.4.2 Vzdrževanje usmerjevalnih metapodatkov
Yang v študiji [36] empirično ugotavlja, da povprečen uporabnik v času svoje življenjske dobe oziroma ene seanse v sistemu enak z enakim generira približno povprečno deset poizvedb. Tudi če imamo v sistemu mnogo uporabnikov, lahko predpostavimo, da na vsakih deset generiranih poizvedb (ne glede na to, kdo jih je generiral), eden od njih zapusti sistem.
Vozlišča si pri obeh predlaganih načinih usmerjanja lokalno shranjujejo metapodatke, ki jih potrebujejo za učinkovitejše usmerjanje. Zaradi dinamične narave sistema moramo prav tako kot zgoraj tudi tu upoštevati, da povprečna življenjska doba vozlišča v sistemu ni neomejena. Zato smo implementirali tudi akcijo praznjenja skladišča metapodatkov:
vsa vozlišča periodično brišejo lokalne metapodatke, ki so starejši kot je neka vnaprej določena omejitev, odvisna od povprečne življenjske dobe vozlišča.