{"id":342,"date":"2020-04-06T08:06:44","date_gmt":"2020-04-06T06:06:44","guid":{"rendered":"http:\/\/tech.sosthe.sk\/?p=342"},"modified":"2020-04-06T22:41:33","modified_gmt":"2020-04-06T20:41:33","slug":"4-4-principy-smerovacich-algoritmov","status":"publish","type":"post","link":"http:\/\/tech.sosthe.sk\/index.php\/2020\/04\/06\/4-4-principy-smerovacich-algoritmov\/","title":{"rendered":"4.9. Princ\u00edpy smerovac\u00edch algoritmov"},"content":{"rendered":"

Nastavenie smerovacej tabu\u013eky m\u00f4\u017ee by\u0165 bu\u010f statick\u00e9 alebo dynamick\u00e9. Pri statickom smerovan\u00ed nastavuje smerovaciu tabu\u013eku administr\u00e1tor ru\u010dne. Nev\u00fdhoda tohto pr\u00edstupu m\u00f4\u017ee by\u0165 pri v\u00fdpadkoch niektor\u00fdch routrov v sieti, lebo ak by aj existovala alternat\u00edvna funguj\u00faca cesta k cie\u013eu, smerovanie by mohlo datagram posla\u0165 rovno smerom k nefunk\u010dn\u00e9mu zariadeniu. Pri dynamickom smerovan\u00ed sa o nastavenie smerovacej tabu\u013eky star\u00e1 smerovac\u00ed algoritmus niektor\u00e9ho z mo\u017en\u00fdch smerovac\u00edch protokolov.<\/p>\n

Smerovacie algoritmy sl\u00fa\u017eia na zistenie aktu\u00e1lne optim\u00e1lnej cesty k v\u0161etk\u00fdm dostupn\u00fdm sie\u0165am a modifik\u00e1ciu smerovac\u00edch tabuliek routrov tak, aby datagramy po svojej aktu\u00e1lne optim\u00e1lnej ceste k cie\u013eu naozaj putovali.<\/p>\n

Ke\u010f\u017ee routrov je na svete ve\u013ea, maj\u00fa aj ve\u013ea spr\u00e1vcov. Ka\u017ed\u00fd zo spr\u00e1vcov m\u00e1 na starosti obvykle viacero siet\u00ed a routrov, ktor\u00e9 tieto siete prep\u00e1jaj\u00fa. Tak\u00e1to mno\u017eina siet\u00ed sa naz\u00fdva\u00a0auton\u00f3mny syst\u00e9m (skr\u00e1tene AS)<\/strong>. Je na spr\u00e1vcovi auton\u00f3mneho syst\u00e9mu, aby zvolil vhodn\u00fd smerovac\u00ed protokol vo svojom auton\u00f3mnom syst\u00e9me, ktor\u00fd sa bude stara\u0165 o nastavovanie smerovac\u00edch tabuliek.<\/p>\n

Stanica, vysielaj\u00faca datagram, je obvykle napojen\u00e1 k jedin\u00e9mu routru \u2013 predvolenej br\u00e1ne, rovnako aj prij\u00edmaj\u00faca stanica. To znamen\u00e1, \u017ee na koncov\u00fdch \u00fasekoch cesty je smer putovania datagramu jednozna\u010dn\u00fd \u2013 priamo medzi stanicou a predvolenou br\u00e1nou. V modeli siete budeme teda uva\u017eova\u0165 iba routre (bez stan\u00edc), ktor\u00e9 s\u00fa navz\u00e1jom poprep\u00e1jan\u00e9 pavu\u010dinou spojen\u00ed. Na routre a spojenia medzi nimi sa m\u00f4\u017eeme pozera\u0165 ako na graf, kde routre s\u00fa vrcholy a spojenia s\u00fa hrany. Jednotliv\u00e9 hrany m\u00f4\u017eu by\u0165 ohodnoten\u00e9. T\u00e1to cena hr\u00e1n m\u00f4\u017ee by\u0165 interpretovan\u00e1 ako \u010das potrebn\u00fd na prenos datagramu medzi routrami, alebo aj ako miera zahltenia spojenia.<\/p>\n

Uva\u017eujme nasleduj\u00faci graf G = (V,E), kde V = {u, v, w, x, y, z} a E = (u, v), (u, x), (u, w), (v, x), (v, w), (x, w), (x, y), (w, y), (w, z), (y, z). Cenu hrany budeme ozna\u010dova\u0165 ako c(v1<\/sub>, v2<\/sub>), kde v1<\/sub>\u00a0a v2<\/sub>\u00a0s\u00fa vrcholy, napr\u00edklad cena c(w, z) = 5. Cena cesty (v1<\/sub>, v2<\/sub>, v3<\/sub>, \u2026, vn<\/sub>,) = c(v1<\/sub>, v2<\/sub>) + c(v2<\/sub>, v3<\/sub>) + \u2026 + c(vn-1<\/sub>, vn<\/sub>).<\/p>\n

\"\"<\/p>\n

Rozozn\u00e1vame dva hlavn\u00e9 typy smerovac\u00edch algoritmov, ktor\u00e9 s\u00fa z\u00e1kladom pre konkr\u00e9tne smerovacie protokoly vo vn\u00fatri auton\u00f3mnych syst\u00e9mov. Prv\u00fdm typom je\u00a0LSA: link state algorithm<\/strong>, ktor\u00fd na svoj beh potrebuje pozna\u0165 cel\u00fa topol\u00f3giu siete a ceny v\u0161etk\u00fdch hr\u00e1n. Ak tieto inform\u00e1cie m\u00e1, vypo\u010d\u00edta optim\u00e1lne cesty ku v\u0161etk\u00fdm routrom auton\u00f3mneho syst\u00e9mu. Druh\u00fd typ je\u00a0DVA: distance vector algorithm<\/strong>. DVA nepotrebuje pozna\u0165 cel\u00fa topol\u00f3giu siete, len ceny hr\u00e1n fyzicky spojen\u00fdch s routrom, na ktorom tento algoritmus be\u017e\u00ed. Tie\u017e je z\u00e1visl\u00fd na inform\u00e1ci\u00e1ch od svojich susedov, ktor\u00e9 si spolu vymie\u0148aj\u00fa. DVA je iterat\u00edvny algoritmus, ktor\u00fd postupne konverguje k aktu\u00e1lne optim\u00e1lnym smerom pre jednotliv\u00e9 cie\u013eov\u00e9 routre.<\/p>\n

4.9.1\u2002 LSA: link state algorithm<\/h3>\n

LSA je typ algoritmov, ktor\u00e9 na svoj beh potrebuj\u00fa pozna\u0165 cel\u00fa topol\u00f3giu siete a ceny v\u0161etk\u00fdch hr\u00e1n. T\u00e1to inform\u00e1cia je obvykle \u0161\u00edren\u00e1 broadcastov\u00fdmi alebo multicastov\u00fdmi spr\u00e1vami od v\u0161etk\u00fdch routrov, pri\u010dom ka\u017ed\u00fd z routrov rozosiela spr\u00e1vu o jeho lok\u00e1lnych spojoch.<\/p>\n

V re\u00e1lnych protokoloch sa vyu\u017e\u00edva\u00a0Dijkstrov algoritmus<\/strong>, ktor\u00fd po\u010d\u00edta najkrat\u0161ie cesty z jedn\u00e9ho uzla k v\u0161etk\u00fdm ostatn\u00fdm. Ke\u010f\u017ee v\u0161etky uzly vedia cel\u00fa topol\u00f3giu, ka\u017ed\u00fd si vypo\u010d\u00edta najkrat\u0161ie cesty od seba k ostatn\u00fdm uzlom.<\/p>\n

Dijkstrov algoritmus bol d\u00f4kladne preberan\u00fd v predmete\u00a0PAZ1b<\/a>, no v kr\u00e1tkosti si ho pripomenieme. Ozna\u010d\u00edme\u00a0D(v)<\/strong>\u00a0ako aktu\u00e1lne najmen\u0161iu cenu cesty zo \u0161tartovacieho uzla do uzla\u00a0v<\/strong>, \u010falej ozna\u010dme\u00a0p(v)<\/strong>\u00a0ako predchodcu uzla\u00a0v<\/strong>\u00a0na aktu\u00e1lne najkrat\u0161ej ceste zo \u0161tartovacieho uzla a nakoniec ozna\u010dme\u00a0N<\/strong>\u00a0ako mno\u017einu uzlov, ku ktor\u00fdm u\u017e pozn\u00e1me definit\u00edvne najkrat\u0161iu cestu.<\/p>\n

\n\n\n\n
Inicializ\u00e1cia:\u00a0N<\/strong>\u00a0= {u<\/strong>}, kde\u00a0u<\/strong>\u00a0je \u0161tartovac\u00ed uzol Pre v\u0161etk\u00fdch susedov\u00a0v<\/strong>\u00a0uzla\u00a0u<\/strong>\u00a0nastav\u00a0D(v)<\/strong>\u00a0=\u00a0c(u, v)<\/strong>\u00a0a\u00a0p(v)<\/strong>\u00a0=\u00a0u<\/strong>\u00a0Pre v\u0161etky ostatn\u00e9 uzly\u00a0w<\/strong>, ktor\u00e9 nie s\u00fa susedom\u00a0u<\/strong>\u00a0nastav\u00a0D(w)<\/strong>=\u221e V\u00fdpo\u010det: Pokia\u013e\u00a0N<\/strong>\u00a0neobsahuje v\u0161etky uzly opakuj vezmi uzol\u00a0w<\/strong>\u00a0tak\u00fd, \u017ee jeho\u00a0D(w)<\/strong>\u00a0je najmen\u0161ie zo v\u0161etk\u00fdch uzlov, ktor\u00e9 nie s\u00fa v\u00a0N<\/strong>\u00a0pridaj\u00a0w<\/strong>\u00a0do\u00a0N<\/strong>\u00a0vezmi ka\u017ed\u00fd uzol\u00a0v<\/strong>, ktor\u00fd je susedom uzla\u00a0w<\/strong>\u00a0a ktor\u00fd z\u00e1rove\u0148 nie je v\u00a0N<\/strong>\u00a0nastav\u00a0D(v)<\/strong>\u00a0= min{D(v)<\/strong>,\u00a0D(w)<\/strong>\u00a0+\u00a0c(w, v)<\/strong>} ak sa\u00a0D(v)<\/strong>\u00a0v predch\u00e1dzaj\u00facom kroku zmenilo, nastav\u00a0p(v)=w<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

Uk\u00e1\u017eme si pr\u00edklad pou\u017eitia Dijkstrovho algoritmu. Predpokladajme, \u017ee chceme spusti\u0165 Dijkstrov algoritmus na vy\u0161\u0161ie zn\u00e1zornenom grafe v uzle\u00a0u<\/strong>.<\/p>\n

    \n
  1. inicializ\u00e1cia\n
      \n
    • N<\/strong>={u<\/strong>}<\/li>\n
    • D(u)<\/strong>=0,\u00a0D(v)<\/strong>=2,\u00a0D(w)<\/strong>=5,\u00a0D(x)<\/strong>=1,\u00a0D(y)<\/strong>=\u221e,\u00a0D(z)<\/strong>=\u221e<\/li>\n
    • p(u)<\/strong>=u<\/strong>,\u00a0p(v)<\/strong>=u<\/strong>,\u00a0p(w)<\/strong>=u<\/strong>,\u00a0p(x)<\/strong>=u<\/strong>,\u00a0p(y)<\/strong>=?,\u00a0p(z)<\/strong>=?<\/li>\n<\/ul>\n<\/li>\n
    • Spomedzi vrcholov\u00a0v<\/strong>,\u00a0w<\/strong>,\u00a0x<\/strong>,\u00a0y<\/strong>,\u00a0z<\/strong>, ktor\u00e9 nie s\u00fa v\u00a0N<\/strong>, si vyberieme uzol\u00a0x<\/strong>, lebo m\u00e1 najmen\u0161iu hodnotu vzdialenosti\u00a0D(x)<\/strong>. Vrchol\u00a0x<\/strong>\u00a0vlo\u017e\u00edme do\u00a0N<\/strong>\u00a0a prepo\u010d\u00edtame vzdialenosti pre v\u0161etk\u00fdch susedov vrchola\u00a0x<\/strong>, ktor\u00ed nie s\u00fa v\u00a0N<\/strong>, teda vrcholov\u00a0v<\/strong>,w<\/strong>\u00a0a\u00a0y<\/strong>.\n
        \n
      • N<\/strong>={u<\/strong>,x<\/strong>}<\/li>\n
      • D(u)<\/strong>=0,\u00a0D(v)<\/strong>=2,\u00a0D(w)<\/strong>=4,\u00a0D(x)<\/strong>=1,\u00a0D(y)<\/strong>=2,\u00a0D(z)<\/strong>=\u221e<\/li>\n
      • p(u)<\/strong>=u<\/strong>,\u00a0p(v)<\/strong>=u<\/strong>,\u00a0p(w)<\/strong>=x<\/strong>,\u00a0p(x)<\/strong>=u<\/strong>,\u00a0p(y)<\/strong>=x<\/strong>,\u00a0p(z)<\/strong>=?<\/li>\n<\/ul>\n<\/li>\n
      • Spomedzi vrcholov\u00a0v<\/strong>,\u00a0w<\/strong>,\u00a0y<\/strong>,\u00a0z<\/strong>\u00a0ktor\u00e9 nie s\u00fa v\u00a0N<\/strong>, si vyberieme uzol\u00a0y<\/strong>, lebo m\u00e1 najmen\u0161iu hodnotu vzdialenosti\u00a0D(y)<\/strong>\u00a0(mohli by sme vybra\u0165 aj\u00a0v<\/strong>). Vrchol\u00a0y<\/strong>\u00a0vlo\u017e\u00edme do\u00a0N<\/strong>\u00a0a prepo\u010d\u00edtame vzdialenosti pre v\u0161etk\u00fdch susedov vrchola\u00a0y<\/strong>, ktor\u00ed nie s\u00fa v\u00a0N<\/strong>, teda vrcholov\u00a0w<\/strong>\u00a0a\u00a0z<\/strong>.\n
          \n
        • N<\/strong>={u<\/strong>,x<\/strong>,y<\/strong>}<\/li>\n
        • D(u)<\/strong>=0,\u00a0D(v)<\/strong>=2,\u00a0D(w)<\/strong>=3,\u00a0D(x)<\/strong>=1,\u00a0D(y)<\/strong>=2,\u00a0D(z)<\/strong>=4<\/li>\n
        • p(u)<\/strong>=u<\/strong>,\u00a0p(v)<\/strong>=u<\/strong>,\u00a0p(w)<\/strong>=y<\/strong>,\u00a0p(x)<\/strong>=u<\/strong>,\u00a0p(y)<\/strong>=x<\/strong>,\u00a0p(z)<\/strong>=y<\/strong><\/li>\n<\/ul>\n<\/li>\n
        • Spomedzi vrcholov\u00a0v<\/strong>,\u00a0w<\/strong>,\u00a0z<\/strong>\u00a0ktor\u00e9 nie s\u00fa v\u00a0N<\/strong>, si vyberieme uzol\u00a0v<\/strong>, lebo m\u00e1 najmen\u0161iu hodnotu vzdialenosti\u00a0D(v)<\/strong>. Vrchol\u00a0v<\/strong>\u00a0vlo\u017e\u00edme do\u00a0N<\/strong>\u00a0a prepo\u010d\u00edtame vzdialenosti pre v\u0161etk\u00fdch susedov vrchola\u00a0v<\/strong>, ktor\u00ed nie s\u00fa v\u00a0N<\/strong>, teda vrchola\u00a0w<\/strong>.\n
            \n
          • N<\/strong>={u<\/strong>,x<\/strong>,y<\/strong>,v<\/strong>}<\/li>\n
          • D(u)<\/strong>=0,\u00a0D(v)<\/strong>=2,\u00a0D(w)<\/strong>=3,\u00a0D(x)<\/strong>=1,\u00a0D(y)<\/strong>=2,\u00a0D(z)<\/strong>=4<\/li>\n
          • p(u)<\/strong>=u<\/strong>,\u00a0p(v)<\/strong>=u<\/strong>,\u00a0p(w)<\/strong>=y<\/strong>,\u00a0p(x)<\/strong>=u<\/strong>,\u00a0p(y)<\/strong>=x<\/strong>,\u00a0p(z)<\/strong>=y<\/strong><\/li>\n<\/ul>\n<\/li>\n
          • Spomedzi vrcholov\u00a0w<\/strong>,\u00a0z<\/strong>\u00a0ktor\u00e9 nie s\u00fa v\u00a0N<\/strong>, si vyberieme uzol\u00a0w<\/strong>, lebo m\u00e1 najmen\u0161iu hodnotu vzdialenosti\u00a0D(w)<\/strong>. Vrchol\u00a0w<\/strong>\u00a0vlo\u017e\u00edme do\u00a0N<\/strong>\u00a0a prepo\u010d\u00edtame vzdialenosti pre v\u0161etk\u00fdch susedov vrchola\u00a0w<\/strong>, ktor\u00ed nie s\u00fa v\u00a0N<\/strong>, teda vrchola\u00a0z<\/strong>.\n
              \n
            • N<\/strong>={u<\/strong>,x<\/strong>,y<\/strong>,v<\/strong>,w<\/strong>}<\/li>\n
            • D(u)<\/strong>=0,\u00a0D(v)<\/strong>=2,\u00a0D(w)<\/strong>=3,\u00a0D(x)<\/strong>=1,\u00a0D(y)<\/strong>=2,\u00a0D(z)<\/strong>=4<\/li>\n
            • p(u)<\/strong>=u<\/strong>,\u00a0p(v)<\/strong>=u<\/strong>,\u00a0p(w)<\/strong>=y<\/strong>,\u00a0p(x)<\/strong>=u<\/strong>,\u00a0p(y)<\/strong>=x<\/strong>,\u00a0p(z)<\/strong>=y<\/strong><\/li>\n<\/ul>\n<\/li>\n
            • U\u017e iba vlo\u017e\u00edme uzol\u00a0z<\/strong>\u00a0do\u00a0N<\/strong>\u00a0a m\u00f4\u017eeme skon\u010di\u0165.<\/li>\n<\/ol>\n

              Nakoniec pomocou \u00fadajov o predchodcoch uzlov vieme zrekon\u0161truova\u0165 najkrat\u0161ie cesty do v\u0161etk\u00fdch uzlov v grafe. Z ka\u017edej cesty si vezmeme iba prv\u00fd krok (v na\u0161om pr\u00edpade bu\u010f do uzla\u00a0v<\/strong>\u00a0alebo do uzla\u00a0x<\/strong>) a ten zapracujeme do smerovacej tabu\u013eky.<\/p>\n

              \n\n\n\n\n\n\n\n\n
              cie\u013eov\u00fd router (cie\u013e)<\/td>\nsusedn\u00fd router na najkrat\u0161ej ceste k cie\u013eov\u00e9mu (br\u00e1na)<\/td>\n<\/tr>\n
              v<\/td>\nv<\/td>\n<\/tr>\n
              w<\/td>\nx<\/td>\n<\/tr>\n
              x<\/td>\nx<\/td>\n<\/tr>\n
              y<\/td>\nx<\/td>\n<\/tr>\n
              z<\/td>\nx<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

              Samozrejme do re\u00e1lnej smerovacej tabu\u013eky sa namiesto cie\u013eov\u00fdch routrov zap\u00ed\u0161u adresy siet\u00ed, ku ktor\u00fdm maj\u00fa tieto routre priamy pr\u00edstup a namiesto \u201emena\u201c routra sa pou\u017eije IP adresa rozhrania, ktor\u00e9 je napojen\u00e9 na spoj s uzlom\u00a0u<\/strong>.<\/p>\n

              Pri pou\u017eit\u00ed LSA m\u00f4\u017ee v niektor\u00fdm pr\u00edpadoch doch\u00e1dza\u0165 k oscil\u00e1ci\u00e1m. Predstavme si situ\u00e1ciu, \u017ee za cenu hrany budeme pova\u017eova\u0165 mno\u017estvo pren\u00e1\u0161an\u00fdch d\u00e1t za nejak\u00fd \u010das. Uva\u017eujme jednoduch\u00fd graf so 4 vrcholmi. Vrcholy\u00a0z<\/strong>\u00a0a\u00a0x<\/strong>\u00a0vysielaj\u00fa k vrcholu\u00a0w<\/strong>\u00a0kon\u0161tantne 1 MB d\u00e1t za sekundu a vrchol\u00a0y<\/strong>\u00a0vysiela k vrcholu\u00a0w<\/strong>\u00a0e MB d\u00e1t za sekundu. Predpokladajme, \u017ee \u017eiadna in\u00e1 komunik\u00e1cia v tomto grafe neprebieha.<\/p>\n

              \"\"<\/p>\n

              Ako m\u00f4\u017eeme vidie\u0165 na obr\u00e1zku\u00a0a<\/em>, na za\u010diatku boli smerovacie tabu\u013eky uzlov nastaven\u00e9 tak, \u017ee datagramy zo\u00a0z<\/strong>\u00a0a\u00a0x<\/strong>\u00a0boli smerovan\u00e9 priamymi spojmi k\u00a0w<\/strong>\u00a0a uzol\u00a0y<\/strong>\u00a0smeroval d\u00e1ta pre\u00a0w<\/strong>\u00a0cez vrchol\u00a0x<\/strong>. Ke\u010f\u017ee samotn\u00e9 posielanie d\u00e1t zmenilo ceny hr\u00e1n, je potrebn\u00e9 prepo\u010d\u00edta\u0165 smerovacie tabu\u013eky. Pri prepo\u010dte zistia vrcholy\u00a0x<\/strong>\u00a0a\u00a0y<\/strong>, \u017ee lacnej\u0161ia cesta k\u00a0w<\/strong>\u00a0je cez vrchol\u00a0z<\/strong>\u00a0a za\u010dn\u00fa smerova\u0165 datagramy t\u00fdmto smerom. To ale op\u00e4\u0165 zmen\u00ed ceny hr\u00e1n a op\u00e4\u0165 sa za\u010dn\u00fa prepo\u010d\u00edtava\u0165 smerovacie tabu\u013eky a vrcholy\u00a0x<\/strong>,\u00a0y<\/strong>\u00a0aj\u00a0z<\/strong>\u00a0za\u010dn\u00fa smerova\u0165 datagramy opa\u010dn\u00fdm smerom a tak \u010falej.<\/p>\n

              4.9.2\u2002 DVA: distance vector algorithm<\/h3>\n

              DVA je algoritmus, ktor\u00fd pre ka\u017ed\u00fd uzol vych\u00e1dza iba z cien susedn\u00fdch hr\u00e1n a z inform\u00e1ci\u00ed od svojich susedov. Ka\u017ed\u00fd vrchol si uchov\u00e1va vektor pod\u013ea neho najlacnej\u0161\u00edch vzdialenost\u00ed k v\u0161etk\u00fdm vrcholom grafu a vektory vzdialenost\u00ed svojich susedov, ktor\u00e9 mu poslali.<\/p>\n

              DVA je zalo\u017een\u00fd na Bellman-Fordovej rovnici, ktor\u00e1 vyjadruje vz\u0165ah medzi cenou najlacnej\u0161ej cesty z uzla\u00a0x<\/strong>\u00a0do uzla\u00a0y<\/strong>\u00a0a cenami ciest od susedov vrchola\u00a0x<\/strong>\u00a0do vrchola\u00a0y<\/strong>. Ozna\u010dme\u00a0dx<\/sub>(y)<\/strong>\u00a0ako cenu najlacnej\u0161ej cesty z uzla\u00a0x<\/strong>\u00a0do uzla\u00a0y<\/strong>. Potom Bellman-Fordova rovnica hovor\u00ed, \u017ee:<\/p>\n

              dx<\/sub>(y)<\/strong>\u00a0= minv<\/strong><\/sub>\u00a0{c(x,v)<\/strong>\u00a0+\u00a0dv<\/sub>(y)<\/strong>\u00a0}, cez v\u0161etky vrcholy\u00a0v<\/strong>\u00a0susedov vrchola\u00a0x<\/strong>.<\/p>\n

              V algoritme DVA budeme pou\u017e\u00edva\u0165 ozna\u010denie\u00a0Dx<\/sub>(y)<\/strong>\u00a0ako o\u010dak\u00e1van\u00fa najmen\u0161iu cenu cesty z vrchola\u00a0x<\/strong>\u00a0do vrchola\u00a0y<\/strong>. Ka\u017ed\u00fd vrchol si uchov\u00e1va vektor vzdialenost\u00ed ku v\u0161etk\u00fdm vrcholom grafu, tento vektor ozna\u010dme\u00a0Dx<\/sub><\/strong>\u00a0= [Dx<\/sub>(y)<\/strong>: kde\u00a0y<\/strong>\u00a0je vrchol grafu]. Ka\u017ed\u00fd vrchol tie\u017e pozn\u00e1 ceny s n\u00edm susediacich hr\u00e1n a vektory vzdialenost\u00ed svojich susedov.<\/p>\n

              \n\n\n\n
              Inicializ\u00e1cia v uzle\u00a0u<\/strong>: Du<\/strong><\/sub>(u<\/strong>)=0. Pre v\u0161etk\u00fdch susedov\u00a0v<\/strong>\u00a0uzla\u00a0u<\/strong>\u00a0nastav\u00a0Du<\/sub>(v)<\/strong>\u00a0=\u00a0c(u, v)<\/strong>\u00a0a v ich vektoroch vzdialenost\u00ed nastav vzdialenosti ku v\u0161etk\u00fdm vrcholom na \u221e (lebo ich re\u00e1lne vektory zatia\u013e nem\u00e1me) Pre v\u0161etky ostatn\u00e9 uzly\u00a0w<\/strong>, ktor\u00e9 nie s\u00fa susedom\u00a0u<\/strong>\u00a0nastav\u00a0Du<\/sub>(w)<\/strong>=\u221e Po\u0161li svoj vektor vzdialenost\u00ed v\u0161etk\u00fdm svojim susedom Ak pr\u00edde vektor vzdialenost\u00ed od niektor\u00e9ho suseda\u00a0w<\/strong>, alebo ak sa zmenia ceny susedn\u00fdch hr\u00e1n: Pre ka\u017ed\u00fd vrchol\u00a0y<\/strong>\u00a0nastav\u00a0Du<\/sub>(y)<\/strong>\u00a0= minv<\/strong><\/sub>{c(u,v)<\/strong>\u00a0+\u00a0Dv<\/sub>(y)<\/strong>\u00a0} Ak sa niekde zmenila hodnota z p\u00f4vodn\u00e9ho vlastn\u00e9ho vektora vzdialenost\u00ed, po\u0161li v\u0161etk\u00fdm svojim susedom nov\u00fd vektor vzdialenosti<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

              Pr\u00edklad v\u00fdpo\u010dtu DVA na troch uzloch je zn\u00e1zornen\u00fd na nasleduj\u00facom obr\u00e1zku. Na za\u010diatku (\u013eav\u00fd st\u013apec) sa v\u0161etky vrcholy a teda aj ich vektory vzdialenost\u00ed inicializuj\u00fa. Tak\u00e1to inicializ\u00e1cia vo v\u0161etk\u00fdch uzloch naraz je s\u00edce nepravdepodobn\u00e1, ale pre \u00fa\u010dely vysvetlenia algoritmu si to m\u00f4\u017eeme dovoli\u0165 predpoklada\u0165.<\/p>\n

              \"\"<\/p>\n

              Po inicializ\u00e1cii po\u0161l\u00fa v\u0161etky vrcholy svojim susedom svoje vektory vzdialenost\u00ed. Vezmime si ako pr\u00edklad vrchol\u00a0x<\/strong>, ktor\u00e9mu pri\u0161li vektory\u00a0Dy<\/sub><\/strong>\u00a0a\u00a0Dz<\/sub><\/strong>. Tieto vektory si ulo\u017e\u00ed a ide prepo\u010d\u00edta\u0165 vlastn\u00fd vektor pod\u013ea Bellman-Fordovej rovnice. Prepo\u010d\u00edtame\u00a0Dx<\/sub>(y)<\/strong>\u00a0a\u00a0Dx<\/sub>(z)<\/strong>:<\/p>\n

              Dx<\/sub>(y)<\/strong>\u00a0= min {c(x,y)<\/strong>\u00a0+\u00a0Dy<\/sub>(y)<\/strong>\u00a0,c(x,z)<\/strong>\u00a0+\u00a0Dz<\/sub>(y)<\/strong>} = min{2+0, 7+1} = 2
              \nDx<\/sub>(z)<\/strong>\u00a0= min {c(x,y)<\/strong>\u00a0+\u00a0Dy<\/sub>(z)<\/strong>\u00a0,c(x,z)<\/strong>\u00a0+\u00a0Dz<\/sub>(z)<\/strong>} = min{2+1, 7+0} = 3<\/p>\n

              Ke\u010f\u017ee sa n\u00e1m zmenila hodnota\u00a0Dx<\/sub>(z)<\/strong>, zmenil sa aj cel\u00fd vektor a mus\u00edme ho posla\u0165 svojim susedom. Okrem toho si vrchol\u00a0x<\/strong>\u00a0zap\u00ed\u0161e do smerovacej tabu\u013eky, \u017ee datagramy pre vrcholy\u00a0y<\/strong>\u00a0aj\u00a0z<\/strong>\u00a0m\u00e1 posiela\u0165 cez vrchol\u00a0y<\/strong>. Podobne sa zmenil aj vektor vzdialenost\u00ed vrchola\u00a0z<\/strong>. Vektor vrchola\u00a0y<\/strong>\u00a0sa nezmenil, tak\u017ee ten svoj u\u017e vektor neposiela. V \u010fal\u0161ej f\u00e1ze si op\u00e4\u0165 v\u0161etky tri vrcholy prepo\u010d\u00edtaj\u00fa svoje vektory vzdialenost\u00ed, a ke\u010f\u017ee \u017eiadnemu sa jeho vektor nezmen\u00ed, \u017eiadne \u010fal\u0161ie vektory sa neposielaj\u00fa a syst\u00e9m ostane stabiln\u00fd.<\/p>\n

              Pri zmene ceny niektorej hrany na to zareaguj\u00fa susedn\u00e9 routre a prepo\u010d\u00edtaj\u00fa svoje vektory vzdialenost\u00ed. Ak d\u00f4jde k zmene vektora, zasielaj\u00fa ho svojim susedom, t\u00ed si prepo\u010d\u00edtaj\u00fa svoje vektory a tak sa t\u00e1to inform\u00e1cia m\u00f4\u017ee \u0161\u00edri\u0165 \u010falej. Predstavme si situ\u00e1ciu na nasleduj\u00facom obr\u00e1zku.<\/p>\n

              \"\"<\/p>\n

              Prv\u00fd pr\u00edpad vykres\u013euje situ\u00e1ciu, ke\u010f sa cena hrany (x<\/strong>,y<\/strong>) zmen\u00ed zo 4 na 1. V tomto pr\u00edpade si vrcholy\u00a0x<\/strong>\u00a0a\u00a0y<\/strong>\u00a0prepo\u010d\u00edtaj\u00fa svoje vektory vzdialenost\u00ed. V\u0161imnime si, ako sa zmen\u00ed vektor vrchola\u00a0y<\/strong>. P\u00f4vodn\u00fd vektor (4,0,1) sa zmen\u00ed na (1,0,1). Tento vektor po\u0161le susedom. \u010co sa stane vo vrchole\u00a0z<\/strong>? P\u00f4vodn\u00fd vektor vrchola\u00a0z<\/strong>\u00a0(5,1,0) sa zmen\u00ed na (2,1,0). Tento vektor po\u0161le svojim susedom, ale u nich sa u\u017e po prepo\u010d\u00edtan\u00ed vektory vzdialenost\u00ed nezmenia a syst\u00e9m sa stabilizuje.<\/p>\n

              V druhom pr\u00edpade sa zmen\u00ed cena hrany (x<\/strong>,y<\/strong>) zmen\u00ed zo 4 na 60. \u010co sa stane? Na za\u010diatku m\u00e1 vrchol\u00a0y<\/strong>\u00a0vektor vzdialenost\u00ed (4,0,1) a\u00a0z<\/strong>\u00a0m\u00e1 vektor (5,1,0). Po zmene ceny hrany si\u00a0y<\/strong>\u00a0prepo\u010d\u00edta svoj vektor pod\u013ea Bellman-Fordovej rovnice (min{60+0, 1+5} = 6, 0, 1) a po\u0161le ho susedom. Vrchol\u00a0z<\/strong>\u00a0si n\u00e1sledne prepo\u010d\u00edta svoj vektor (min{50+0, 1+6} = 7, 0, 1) a po\u0161le ho susedom. Vrchol\u00a0y<\/strong>\u00a0si n\u00e1sledne prepo\u010d\u00edta svoj vektor (min{60+0, 1+7} = 8, 0, 1) a tak \u010falej. Tak\u00e9to posielanie sa vykon\u00e1 celkovo 44 kr\u00e1t, k\u00fdm d\u00f4jde k stabiliz\u00e1cii. Hovor\u00edme o takzvanom\u00a0count to infinity<\/strong>\u00a0probl\u00e9me, teda o \u201epo\u010d\u00edtan\u00ed do nekone\u010dna\u201c. Tomuto probl\u00e9mu sa v stromov\u00fdch sie\u0165ach d\u00e1 vyhn\u00fa\u0165 technikou \u201epoisoned reverse\u201c, kde sa pri odhalen\u00ed po\u010d\u00edtania do nekone\u010dna m\u00f4\u017ee jeden z uzlov rozhodn\u00fa\u0165 zmeni\u0165 hodnotu vo svojom vektore jedenkr\u00e1t na nekone\u010dno a potom op\u00e4\u0165 hl\u00e1si\u0165 re\u00e1lne hodnoty vektora, lebo ako sme videli pri zni\u017eovan\u00ed cien, sa zmeny prejavia r\u00fdchlo. \u201ePoisoned reverse\u201c v\u0161ak str\u00e1ca svoju silu v sie\u0165ach s cyklami, kde je ve\u013emi n\u00e1ro\u010dn\u00e9 odhali\u0165 stav po\u010d\u00edtania do nekone\u010dna.<\/p>\n

              V\u00fdber toho, \u010di pou\u017ei\u0165 protokol zalo\u017een\u00fd na LSA alebo na DVA je na administr\u00e1torovi siete. Oba pr\u00edstupy maj\u00fa svoje v\u00fdhody aj nev\u00fdhody. LSA vy\u017eaduje pri ka\u017edej zmene v\u00fdmenu v\u0161etk\u00fdch inform\u00e1cii v sieti broadcastov\u00fdmi alebo multicastov\u00fdmi spr\u00e1vami od v\u0161etk\u00fdch routrov. DVA posiela spr\u00e1vy iba medzi susedmi, ale zato mo\u017eno aj nieko\u013eko, \u010di a\u017e ve\u013emi ve\u013eakr\u00e1t (count to infinity probl\u00e9m). LSA na druhej strane m\u00f4\u017ee sp\u00f4sobi\u0165 oscil\u00e1cie. Dijkstrov algoritmus vy\u017eaduje \u010das O(e log(n)), kde n je po\u010det vrcholov a e je po\u010det hr\u00e1n. DVA prepo\u010d\u00edta vektor v \u010dase O(n), ale urob\u00ed to potenci\u00e1lne aj ve\u013eakr\u00e1t, k\u00fdm sa stabilizuje.<\/p>\n","protected":false},"excerpt":{"rendered":"

              Nastavenie smerovacej tabu\u013eky m\u00f4\u017ee by\u0165 bu\u010f statick\u00e9 alebo dynamick\u00e9. Pri statickom smerovan\u00ed nastavuje smerovaciu tabu\u013eku administr\u00e1tor ru\u010dne. Nev\u00fdhoda tohto pr\u00edstupu m\u00f4\u017ee by\u0165 pri v\u00fdpadkoch niektor\u00fdch…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"_links":{"self":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts\/342"}],"collection":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/comments?post=342"}],"version-history":[{"count":5,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts\/342\/revisions"}],"predecessor-version":[{"id":533,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts\/342\/revisions\/533"}],"wp:attachment":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/media?parent=342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/categories?post=342"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/tags?post=342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}