Netchange
var Neigh»            : set of nodes :          (* The neighbors of u *)
Du                  : array of 0.. N ;       (* Du[v) estimates dfu, v) *)
Nbu                : array of nodes :      {* Nbu\v\ is preferred neighbor for v *
ndiau              : array of 0.. N ;       (* ndisv\w. v] estimates d(w, v) *)
Initialization:
begin forall it' £ Nciyh,,, v € V do ndisu[<t>. v] := N : forall v G V do
begin DUU>\ ■- N : Nb„{»\ := udej end : Dtl(it]:=0; Nb„[u\ := local ■ forall w fc A'c-ítrň,, do sond {mydist, u, 0) to í/j end
Procedure Recompute (v): begin if v = u
then begin Du[v] := 0 ; Nbu[v] := local end else begin (* Estimate distance to v *)
ři:- I + min{wfe((|«!. ľ] : tv € Neighu} ; if d < JV then begin Du[v]:=d;
Nbu[v] := w with 1 + ndisu[w, v] = d end else begin Du[v] := ,V ; /Vft,,^] := udef end end ; if í*«'r] has changed then forall x 6 JVei^ do send {mydist. u, Dw [■(.>]) to x end
Processing it ( mydist. r. d) message from neighbor «■: { A (mydist. ľ. d) irt at the head u f QN.ľ } begin receive (mydist. c ŕ/) from w : ndisu[w, v] := d : Recompute (v) end
Upon failure of channel aw:
begin receive ( fail, u>) : Neighu := Neigh,, \ {w} :
forall u S V do Recompute (v) end
Upon repair of channel utw:
begin receive {repair, w} : Neighu := Neigh,, U {u1} ; forall r £ V do
begin ndis„[w, v\ := N ;
send (mydist, (.£>„ [e]) tow end etui
korektnosť
lexikograficky klesá hodnota [ř0, ř-|,..., tN]
kde tj je počet správ (mydist, /)+ počet dvojíc u, v kde Du[v] = i
□        \3
packet routing
•  synchrónny režim
» vrcholy majú pakety (uložené v bufferoch)
•  v jednom kroku pojednej linke ide max. jeden paket
•  algoritmus = odchádzajúce linky + priorita bufferov
•  celkový čas
initial        j^—k configuration   H3j
packet routing na mriežke v N x v N
Každý vrchol má 1 paket, do každého smeruje 1 paket (permutation routing)
algoritmus
Najprv riadok, potom stĺpec. Prednosť má ten s najdlhšou cestou.
analýza: stačí 2vÄŽ - 2 krokov
a po \//V - 1 krokoch je každý v správnom stĺpci (nebrzdia sa)
• routovanie v stĺpci ide v VN - 1 krokoch
a pre každé / platí: po N — 1 krokoch sú koncové pakety na koncových miestach • dôvod: zdržujú sa iba navzájom
veľkosť buffra v najhoršom prípade: 2/3\//V - 3
□        \3
veľkosť buffra: priemerný prípad I
setting
Každý vrchol má jeden paket s náhodným cieľom
max. veľkosť buffra m počet zahnutí vo vrchole
psf, že aspoň r zahne < O M=     < (f)r
V^A í   1   Y
slog N
prer=l^,jepsřo(/V-
□        rJ         -         =
veľkosť buffra: priemerný prípad II
wide-channel: nepredbiehajú sa
očakávaný počet paketov na hrane (J, j) >-> (/ + 1 ,j) je
2/(\//V - /)A      A N        - ¥
chceme ukázať, že s veľkou psťou ich neprejde príliš viac
J
Černovov odhad
Majme n nezávislých Bernoulihho náh. prem. X-\,... ,Xn, pričom PryX^ = 1] < P^. Potom
Pr[X>ßP\<e('-ls-hß)ßP
kdeX = £X,,P = £P,
E{exx*	< 1 + Pk{ex -E[exx] < ep<	1) 9A-	<ep* 1)	ex-	-1)
P[exx >	A„Pl      E[exx]	<	eP(ex-	-1)	-XßP
□       s>        -        =
veľkosť buffra: priemerný prípad II
Majme n nezávislých Bernoulihho náh. prem. X-\,.. .,Xn, pričom Pr[Xk = 1] < P^. Potom
Pr[X>ßP]<e^-y>nß)ßP
kdeX = £X,,P = £P,
psf, že vo wch prejde aspoň «A/2 paketov cez hranu e počas ŕ + 1, ŕ + 2,..., ŕ -
je najviac e(<*-i-<*ina)A/2
očakávaný počet paketov na hrane (/,/) i-^ (/ + 1 ,y) je
2/(V/V - /)A      A N        - ¥
chceme ukázať, že s veľkou psťou ich neprejde príliš viac
n = 2iA, Pi
k -     N
VŇ-i    D -  2i(VŇ-i)A
L,P
N
ß--
aN 4/(v/W-/)
□        \3
veľkosť buffra: priemerný prípad II
ak je paket vo vzd. d od hrany e v čase T, a p prejde cez e v čase T + d + S, potom v každom kroku [T + d, T + d + 6] prejde paket cez e
dôsledok
ak paket prejde cez e v čase T vo wch, a prejde cez e v čase T + S v št. , tak v každom kroku [T, T + 6] prejde paket
ak počas [T + 1, T + A] prejde cez e x paketov v št., tak pre nejaké f prejde x + f paketov cez e v čase [T + 1 = f, T + A] vo wch.
psf, že cez e prejde viac ako «A/2 paketov počas konkrétneho okna A krokov je najviac 0(e(a-,-dn°)A/2)
dôsledok
s psfou 1 - O(jy) neprejde po e viac ako clog N paketov v posebe idúcich krokoch, kdec=2F^T <9-
dynamické routovanie
model
V každom kroku sa v každom vrchole s psfou A narodí paket s náhodným cieľom.
stabilita
Pre A > 4/\//Vje systém nestabilný
Ak je A < 0.99-^j, tak psf zdržania konkrétneho paketu o A krokov je e~°<A). W.h.p. stačí buffer 0(1 + J§|^).
n         \3           -           =          ■=      -00*0
hierarchické routovanie
cieľ: minimalizovať počet rozhodnutí
s-klastre:
•  každý je súvislý, pokrývajú všetky vrcholy
•  každý obsahuje aspoň s vrcholov a má polomer najviac 2s kostra spájajúca centrá klastrov: m listov =► m - 2 vetvení
po / klastrovaniach s parametrom s: m, listov, max. m, - 2 vetvení => m,-+i = m,(2/s)
rrif + ŕs rozhodnutí
sř»2/V1/f
□        g         -         =         ^      -00*0
cvičenia
mriežka -/ň x -/ň, prednosť má hocikto; ukážte, že v najhoršom prípade treba viac ako 2^/n krokov, ale stačí 0(^/n)
mriežka y/n x \fň, v každom vrchole správa do náhodného. Ukážte, že w.h.p. do žiadnoho vrchola nesmeruje viac ako 3 log nj log log n správ.
majme cestu z n procesorov, každý chce routovať práve dva pakety (červený a modrý), pričom červené aj zelené tvoria permutáciu, ukážte, že stačí n krokov