1
ˇ ´ ´I (ROUTING) SMEROV AN V kompletn´ım grafu nenast´av´a probl´em. Kaˇzd´ y uzel je soused se zbytkem vrchol˚ u a m˚ uˇze s nimi kdykoliv komunikovat. Probl´em nast´av´a u ostatn´ıch graf˚ u:
Krit´eria dobr´eho smˇerov´an´ı: a) Corectnost - spr´avn´ y paket mus´ı b´ yt doruˇcen spr´avn´emu adres´atovi b) Sloˇ zitost - algoritmus mus´ı pouˇz´ı co nejm´ıˇ n smˇerovac´ıch tabulek, zpr´av, ˇcasu atd. c) Efektivnost - vˇsechny pakety by mˇeli b´ yt pos´ılan´e po co nejkratˇs´ıch cest´ach. Pokud je toto splnˇeno, algoritmus se naz´ yv´a optim´aln´ı. d) Robustnost - V pˇr´ıpadˇe topologick´e zmˇeny s´ıtˇe, by mˇel algoritmus tyto zmˇeny zaznamenat a zmˇenit smˇerov´an´ı. e) Adoptivnost - M˚ uˇzeme zkoumat zat´ıˇzenost cesty(hrany) a poˇzadujeme rovnomˇern´e zat´ıˇzen´ı cest(hran). ´ ern´e cesty maj´ı zajiˇstˇen u f ) Spravedlnost - Umˇ ´ mˇern´ y ˇcas pˇrenosu. Nem˚ uˇzeme poˇzadovat, aby po kratˇs´ı cestˇe putoval paket d´ele neˇz po delˇs´ı cestˇe.
Smˇ erov´ an´ı pomoc´ı smˇ erovac´ıch tabulek Pˇredpokl´ad´ame, ˇze m´ame vrchol u a pole table u, kter´e obsahuje urˇcit´e informace. Z´ akladn´ı algoritmus: receive hm, di ; if d = u then OK else send hm, di to table u [d];
2 Sestrojen´ı smˇ erovac´ı tabulky:
index 1 2 3 4 5 6 7
1 1 1 3 1 4* 5
2 3 4 5 2 3 3* 5 - 3 3 1 2 4 1* 3 3 5 1 4* 4 4 4 4 4* 5 5* 5* 5
6 7 3 5 3 1 4 1* 6 5* 4* 7 7 6 -
Naˇse smˇerovac´ı tabulka m´a vlastnost nejkratˇs´ıch cest. Pokud poˇzadujeme jinou vlastnost dostaneme i jinou tabulku. ∗ - existuje v´ıce moˇznost´ı
Kolik bit˚ u je potˇreba na uchov´an´ı cel´e smˇerovac´ı tabulky? Θ(n2 log n) pro n vrchol˚ u Celkov´ y poˇcet u ´ daj˚ u v tabulce: Θ(n2 )
Vˇ eta : Optim´aln´ı smˇerovac´ı sch´ema pro dan´ y graf vyˇzaduje Θ(n2 log n) bit˚ u, kter´e jsou uchov´avan´e ve smˇerovac´ı tabulce. N´ ahodn´ y graf - definuje se podle teorie pravdˇepodobnosti nebo pomoc´ı Kolmogorovsk´e sloˇzitosti. Mˇejme n pr´azdn´ ych vrchol˚ u. Postupnˇe pˇrid´av´ame hrany. V nˇejak´em okamˇziku tento proces zastav´ıme. Tedy po q - kroc´ıch budeme m´ıt q hran. n Poˇcet vˇsech vrchol˚ u, kter´e se takto daj´ı vygenerovat je 2( 2 ) . Pokud n´ahodnˇe vybereme z t´eto mnoˇziny nˇekter´e grafy, tyto grafy maj´ı urˇcit´e vlastnosti.
ˇ ık´ame, ˇze t´emˇeˇr vˇsechny grafy maj´ı vlastnost Q, pokud plat´ı, ˇze Definice : R´
3 limn→∞ P [G m´a vlastnost Q] = 1. G je graf, kter´ y je prvkem nˇejak´eho pravdˇepodobnostn´ıho prostoru. Pˇr´ıklady vlastnost´ı: 1. T´emeˇr vˇsechny grafy jsou souvisl´e 2. T´emˇeˇr vˇsechny grafy maj´ı pr˚ umˇer 2 3. T´emˇeˇr vˇsechny grafy nejsou plan´arn´ı Graf je reprezentov´an bin´arn´ım ˇretˇezcem, tedy nad abecedou {0,1} d´elky
n 2
.
Kaˇzd´ y graf je reprezentov´an bin´arn´ım ˇretˇezcem. Pokud n´ahodnˇe vygenerujeme n´ahodn´ y bin´arn´ı ˇretˇezec dostaneme i n´ahodn´ y graf. Kolmogorovsk´ y n´ahodn´ y graf je reprezentov´an nestlaˇciteln´ ym(m´alo stlaˇciteln´ ym) ˇretˇezcem. M´alo stlaˇciteln´ y ˇretˇezec je n´ahodnˇe generovan´ y ˇretˇezec, tedy ˇretˇezec bez ˇcasto se opakuj´ıc´ıch stejn´ ych podˇretˇezc˚ u. Vˇ eta : (Horn´ı odhad pro rozsah smˇerovac´ıch tabulek v Kolmogorovsk´ych n´ ahodn´ych grafech) Smˇerovaˇc pro optim´aln´ı smˇerovac´ı sch´ema na Kolmogorovsk´ ych O( log n ) ∗ n´ahodn´ ych grafech ˇra´du n, potˇrebuje uchov´avat nanejv´ yˇs 6n bit˚ u smˇerovac´ı informace. ∗ maxim´alnˇe o tolik je ˇretˇezec stlaˇciteln´ y. 2 Celkovˇe smˇerovac´ı tabulka vyˇzaduje 6n bit˚ u. Vˇ eta : (Doln´ı odhad) Kaˇzd´ y smˇerovaˇc pro optim´aln´ı smˇerovac´ı sch´ema na Kolmogorovsk´ ych o(n) - n´ahodn´ ych grafech potˇrebuje uchov´avat alespoˇ n n/2 - o(n) bit˚ u smˇerovac´ı informace. Celkov´e pamˇet’ov´e n´aroky vyˇzaduj´ı n2 /2 - o(n2 ) bit˚ u informace.
4 NETCHANGE ALGORITMUS Popis algoritmu Tajibnapis Netchange algoritmus je d´an jako algoritmus 4.8 a 4.9. Postupy algoritmu budou nejdˇr´ıve podloˇzeny neform´aln´ım popisem operac´ı algoritmu, a n´aslednˇe bude form´alnˇe dok´az´ana spr´avnost algoritmu. V´ ybˇer souseda, kter´emu budou doruˇceny bal´ıky pro urˇcen´ı v , je zaloˇzen na odhadech vzd´alenosti kaˇzd´eho uzlu k v . Preferovan´ y soused je vˇzdy sousedem s nejniˇzˇs´ım odhadem t´eto vzd´alenosti. var N eighu Du N bu ndisu
: set of nodes ; : array of 0..N ; : array of nodes ; : array of 0..N ;
(* soused´e u *) (* Du [v] odhaduje d(u, v) *) (* N bu [v] je soused preferovan´ y pˇred v *) (* ndisu [w, v] odhaduje d(w, v) *)
Inicializace: begin forall w ∈ N eighu , v ∈ V do ndisu [w, v] := N ; forall v ∈ V do begin Du [v] := N ; N bu [v] := udef end ; Du [u] := 0 ; N bu [u] := local ; forall w ∈ N eighu do send hmydist, u, 0i to w end Postup n´ahrady(v): begin if v = u then begin Du [v] := 0 ; N bu [v] := local end else begin (* Odhadnout vzd´alenost k v *) d := 1 + min{ndisu [w, v] : w ∈ N eighu } ; if d < N then begin Du [v] := d ; N bu [v] := w with 1 + ndisu [w, v] = d end else begin Du [v] := N ; N bu [v] := udef end end ; if Du [v] se zmˇen´ı then forall x ∈ N eighu do send hmydist, v , Du [v ]i to x end ˇ ast prvn´ı, pro uzel u). Algoritmus 4.8 NETCHANGE ALGORITMUS (C´
Uzel prov´ad´ı odhad Du [v] of d(u, v) a odhaduje ndisu [w, v] of d(w, v) pro kaˇzd´eho souseda w of u. Odhad Du [v] je vypoˇc´ıt´an z odhad˚ u ndisu [w, v], a odhady
5 ndisu [w, v] obdrˇz´ıme pˇres komunikaci se sousedy. V´ ypoˇcet odhad˚ u Du [v] pokraˇcuje n´asledovnˇe. Jestliˇze u = v potom d(u, v) = 0 takˇze Du [v] je v tomto pˇr´ıpadˇe nastaven na 0. Jestliˇze u 6= v, nejkratˇs´ı cesta z u do v (pokud takov´a cesta existuje ) se skl´ad´a z pr˚ uchodu od u k sousedovi, slouˇcen´emu s nejkratˇs´ı cestou od tohoto souseda k v a tedy d(u, v) = 1 + min w ∈ N eighu d(w, v). Z pˇredch´azej´ıc´ı rovnice, uzel u 6= v odhaduje d(u, v) aplikov´an´ım t´eto definice na odhadovan´e hodnoty d(w, v), nalezen´ ych v tabulk´ach jako ndisu [w, v]. Kdyˇz existuje N uzl˚ u, minim´alnˇe se mˇen´ıc´ı cesta m´a d´elku nejv´ yˇse N − 1. Uzel m˚ uˇze tuˇsit, ˇze neexistuje ˇza´dn´a cesta, pokud je vypoˇc´ıtan´a vzd´alenost N a v´ıc; hodnota N je uˇzita v tabulce. Algoritmus vyˇzaduje uzel, aby mˇel odhad vzd´alenosti sv´ ych soused˚ u k v. Ty jsou obdrˇreny od tˇechto uzl˚ u, protoˇze je pˇren´aˇsej´ı ve zpr´av´ach typu hmydist, ..i. Pokud uzel u poˇc´ıt´a hodnotu d jako odhad sv´e vzd´alenosti k v(Du [v] = d), je posl´ana tato informace vˇsem soused˚ um ve zpr´avˇe hmydist, v, di. Po obdrˇzen´ı zpr´avy hmydist, v, di od souseda w, u pˇridˇeluje ndisu [w, v] hodnotu d.Jako v´ ysledek zmˇeny v ndisu [w, v] se odhad d(u, v) m˚ uˇze zmˇenit a proto je odhad nahrazen pokaˇzd´e, kdyˇz se tabulka zmˇen´ı. Pokud se odhad opravdu zmˇen´ı k d’ je samozˇrejmˇe pˇrenesen k soused˚ um, 0 kteˇr´ı uˇz´ıvaj´ı zpr´avy hmydist, v, d i. Zpracov´an´ı zpr´avy hmydist, v , d i od souseda w: { hmydist, v , d i stoj´ı v ˇcele Qwv } begin receive hmydist, v , d i from w ndisu [w, v] := d ; Recompute(v) end Pˇri v´ ypadku pr˚ uchodu uw: begin receive hfail, w i ; N eighu := N eighu \{w} ; forall v ∈ V do Recompute (v) end Pˇri oparavˇe pr˚ uchodu uw: begin receive hrepair, w i ; N eighu := N eighu ∪ {w} ; forall v ∈ V do begin ndisu [w, v] := N ; send hmydist, v , Du [v ]i to w end end ˇ ast 2, pro uzel u). Algoritmus 4.9 NETCHANGE ALGORITMUS (C´
6 Algoritmus reaguje na na v´ ypadky a opravy pr˚ uchod˚ u t´ım, ˇze pozmˇen´ı m´ıstn´ı tabulky a poˇsle zpr´avu hmydist, ..i pokud se odhady vzd´alenosti zmˇen´ı. Pˇredpokl´ad´ame, ˇze ozn´amen´ı o tom, ˇze uzly se dost´avaj´ı nad pr˚ uchodem nahoru a dol˚ u, je ve formˇe zpr´av hf ail, .i a hrepair, .i. Pr˚ uchod mezi uzly u1 a u2 je modelov´an dvˇemi ˇradami Qu1 ,u2 pro zpr´avy od u1 k u2 a Qu2 ,u1 pro zpr´avy od u2 k u1 . Kdyˇz pr˚ uchod vypadne, jsou tyto ˇrady pˇrestˇehov´any z konfigurace a uzly na obou konc´ıch pr˚ uchodu obdrˇz´ı zpr´avu hf ail, .i. Jestliˇze pr˚ uchod mezi u1 a u2 vypadne, u1 obdrˇz´ı zpr´avu hf ail, u2 i a u2 z´ısk´a zpr´avu hf ail, u1 i. Kdyˇz je pr˚ uchod opravov´an (nebo je k s´ıti pˇrid´an nov´ y) jsou ke konfiguraci pˇrid´any dvˇe pr´azdn´e ˇrady a dva uzly spojen´e pr˚ uchodem obdrˇz´ı zpr´avu hf ail, .i. Jestliˇze pr˚ uchod mezi u1 a u2 nastane, u1 obdrˇz´ı hrepair, u2 i a u2 obdrˇz´ı hrepair, u1 i. Reakce algoritmu na v´ ypadky a opravy je n´asledu´ıc´ı. Kdyˇz vypadne pr˚ uchod mezi u a w, w se pˇrem´ıst´ı z N eighu a naopak. Odhad vzd´alenosti pro kaˇzd´e urˇcen´ı je nahrazen, a samozˇrejmˇe, posl´an vˇsem zb´ yvaj´ıc´ım soused˚ um, pokud byl zmˇenˇen. Je to tento pˇr´ıpad, pokud pˇredt´ım vedla nejlepˇs´ı cesta pˇres vypaden´ y pr˚ uchod a neexistuje ˇza´dn´ y jin´ y soused w’ s ndisu [w 0 , v] = ndisu [w, v]. Kdyˇz je pr˚ uchod opravov´an (nebo je pˇrid´an nov´ y), w se pˇrid´a k N eigh u , ale u nem´a dosud ˇza´dn´ y odhad vzd´alenosti d(w, v) (a naopak). Nov´ y soused w je ihned informov´an o Du [v] pro vˇsechna urˇcen´ı v (posl´an´ım zpr´avy hmydist, v, Du [v]i). Dokud u neobdrˇz´ı podobn´e zpr´avy z w, u pouˇz´ıv´a N jako odhad pro d(w, v), tzn., nastavuje ndisu [w, v] na N . Vˇ eta : Pokud po konˇcn´em kroku topologick´ ych zmˇen, topologie s´ıtˇe z˚ ust´av´a konstantn´ı(nemˇenn´a) algorimus NETCHANGE dos´ahne stabiln´ı konfiguraci po koneˇcn´em poˇctu krok˚ u.
7
Probl´ em dohody na nespolehliv´ ych s´ıt´ıch V s´ıt´ıch budeme uvaˇzovat 2 typy chyb: a) CRASH b) BYZANTINE FAILURE (Byzantsk´e chyby) ad a) Budeme uvaˇzovat, ˇze chybn´ y je procesor. Zastav´ı svou aktivitu a bude se chovat jako nepˇr´ıtomn´ y v dan´e s´ıti. ad b) Bude se chovat libovolnˇe. M˚ uˇze se jevit jako protihr´aˇc, nepˇr´ıtel. Je dan´ y jeden gener´al a nˇekolik d˚ ustojn´ık˚ u. Vˇsichni si m˚ uˇzou pos´ılat zpr´avy mezi sebou. Komunikaˇcn´ı s´ıt´ı je kompletn´ı graf. Gener´al nebo d˚ ustojn´ıci m˚ uˇzou b´ yt loaj´aln´ı nebo byzantinˇst´ı (crash nebo pos´ılaj´ı zpr´avy, aby ˇskodili loaj´aln´ım d˚ ustojn´ık˚ um). C´ılem je, aby se v koneˇcn´em ˇcase loaj´aln´ı shodli na stejn´e hodnotˇe. Pouˇz´ıvaj´ı se dva algoritmy podle typu zpr´av: a) podepsan´e zpr´avy b) anonymn´ı zpr´avy Mˇejme kompletn´ı graf Kn , p0 necht’ je gener´al p1 , . . , pn−1 - jsou d˚ ustojn´ıci. Vˇ eta : Existuje algoritmus odoln´ y v˚ uˇci t byzantsk´ ym chyb´am, kter´ y pouˇz´ıv´a podepsan´e zpr´avy a ˇreˇs´ı u ´ lohu o shodˇe. Pˇriˇcemˇz mus´ı platit, ˇze t ≤ n − 2. ALGORITMUS SM(t ) Pozn. Vi = ∅ ∀i → mnoˇzina zpr´av, kter´e si pamatuje i -t´ y procesor v ∈ {0,1} → zpr´ava m : p → zpr´ava m z podpisem p 1. Gener´al v0 poˇsle zpr´avu v : 0 vˇsen d˚ ustojn´ık˚ um. 2. Pro ∀i if (pi pˇrijme zpr´avu v : 0) then vi = {v}; send v : 0 : i to ostatn´ım d˚ ustojn´ık˚ um if (pi pˇrijme zpr´avu v : 0 : j1 ..jk ) then vi = {v} ∪ Vi ; if (k < t) then send v : 0 : j1 : .. : jk : i to ostatn´ım d˚ ustojn´ık˚ um r˚ uzn´ ym od 3. if (Vi obsahuje jedinou hodnotu) then pak tuto hodnotu vrat’ na v´ ystup else vrat’ NIL Algoritmus je synchronn´ı a k oznaˇcuje poˇcet kol. Vˇ eta : Algoritmus konˇc´ı v´ ypoˇcet po t + 1 kolech a pouˇz´ıv´a (n − 1)(n − 2)..(n − t − 1) zpr´av.
j1 ..jk
