Slidy z prednášky
YouTube

1.  Princípy smerovacích algoritmov

Nastavenie smerovacej tabuľky môže byť buď statické alebo dynamické. Pri statickom smerovaní nastavuje smerovaciu tabuľku administrátor ručne. Nevýhoda tohto prístupu môže byť pri výpadkoch niektorých routrov v sieti, lebo ak by aj existovala alternatívna fungujúca cesta k cieľu, smerovanie by mohlo datagram poslať rovno smerom k nefunkčnému zariadeniu. Pri dynamickom smerovaní sa o nastavenie smerovacej tabuľky stará smerovací algoritmus niektorého z možných smerovacích protokolov.

Smerovacie algoritmy slúžia na zistenie aktuálne optimálnej cesty k všetkým dostupným sieťam a modifikáciu smerovacích tabuliek routrov tak, aby datagramy po svojej aktuálne optimálnej ceste k cieľu naozaj putovali.

Keďže routrov je na svete veľa, majú aj veľa správcov. Každý zo správcov má na starosti obvykle viacero sietí a routrov, ktoré tieto siete prepájajú. Takáto množina sietí sa nazýva autonómny systém (skrátene AS). Je na správcovi autonómneho systému, aby zvolil vhodný smerovací protokol vo svojom autonómnom systéme, ktorý sa bude starať o nastavovanie smerovacích tabuliek.

Stanica, vysielajúca datagram, je obvykle napojená k jedinému routru – predvolenej bráne, rovnako aj prijímajúca stanica. To znamená, že na koncových úsekoch cesty je smer putovania datagramu jednoznačný – priamo medzi stanicou a predvolenou bránou. V modeli siete budeme teda uvažovať iba routre (bez staníc), ktoré sú navzájom poprepájané pavučinou spojení. Na routre a spojenia medzi nimi sa môžeme pozerať ako na graf, kde routre sú vrcholy a spojenia sú hrany. Jednotlivé hrany môžu byť ohodnotené. Táto cena hrán môže byť interpretovaná ako čas potrebný na prenos datagramu medzi routrami, alebo aj ako miera zahltenia spojenia.

Uvažujme nasledujúci 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čovať ako c(v1, v2), kde v1 a v2 sú vrcholy, napríklad cena c(w, z) = 5. Cena cesty (v1, v2, v3, …, vn,) = c(v1, v2) + c(v2, v3) + … + c(vn-1, vn).

Rozoznávame dva hlavné typy smerovacích algoritmov, ktoré sú základom pre konkrétne smerovacie protokoly vo vnútri autonómnych systémov. Prvým typom je LSA: link state algorithm, ktorý na svoj beh potrebuje poznať celú topológiu siete a ceny všetkých hrán. Ak tieto informácie má, vypočíta optimálne cesty ku všetkým routrom autonómneho systému. Druhý typ je DVA: distance vector algorithm. DVA nepotrebuje poznať celú topológiu siete, len ceny hrán fyzicky spojených s routrom, na ktorom tento algoritmus beží. Tiež je závislý na informáciách od svojich susedov, ktoré si spolu vymieňajú. DVA je iteratívny algoritmus, ktorý postupne konverguje k aktuálne optimálnym smerom pre jednotlivé cieľové routre.

1.1  LSA: link state algorithm

LSA je typ algoritmov, ktoré na svoj beh potrebujú poznať celú topológiu siete a ceny všetkých hrán. Táto informácia je obvykle šírená broadcastovými alebo multicastovými správami od všetkých routrov, pričom každý z routrov rozosiela správu o jeho lokálnych spojoch.

V reálnych protokoloch sa využíva Dijkstrov algoritmus, ktorý počíta najkratšie cesty z jedného uzla k všetkým ostatným. Keďže všetky uzly vedia celú topológiu, každý si vypočíta najkratšie cesty od seba k ostatným uzlom.

Dijkstrov algoritmus bol dôkladne preberaný v predmete PAZ1b, no v krátkosti si ho pripomenieme. Označíme D(v) ako aktuálne najmenšiu cenu cesty zo štartovacieho uzla do uzla v, ďalej označme p(v) ako predchodcu uzla v na aktuálne najkratšej ceste zo štartovacieho uzla a nakoniec označme N ako množinu uzlov, ku ktorým už poznáme definitívne najkratšiu cestu.

Inicializácia: N = {u}, kde u je štartovací uzol Pre všetkých susedov v uzla u nastav D(v) = c(u, v) a p(v) = u Pre všetky ostatné uzly w, ktoré nie sú susedom u nastav D(w)=∞ Výpočet: Pokiaľ N neobsahuje všetky uzly opakuj vezmi uzol w taký, že jeho D(w) je najmenšie zo všetkých uzlov, ktoré nie sú v N pridaj w do N vezmi každý uzol v, ktorý je susedom uzla w a ktorý zároveň nie je v N nastav D(v) = min{D(v), D(w) + c(w, v)} ak sa D(v) v predchádzajúcom kroku zmenilo, nastav p(v)=w

Ukážme si príklad použitia Dijkstrovho algoritmu. Predpokladajme, že chceme spustiť Dijkstrov algoritmus na vyššie znázornenom grafe v uzle u.

  1. inicializácia
    • N={u}
    • D(u)=0, D(v)=2, D(w)=5, D(x)=1, D(y)=∞, D(z)=∞
    • p(u)=u, p(v)=u, p(w)=u, p(x)=u, p(y)=?, p(z)=?
  2. Spomedzi vrcholov v, w, x, y, z, ktoré nie sú v N, si vyberieme uzol x, lebo má najmenšiu hodnotu vzdialenosti D(x). Vrchol x vložíme do N a prepočítame vzdialenosti pre všetkých susedov vrcholu x, ktorí nie sú v N, teda vrcholov v,w a y.
    • N={u,x}
    • D(u)=0, D(v)=2, D(w)=4, D(x)=1, D(y)=2, D(z)=∞
    • p(u)=u, p(v)=u, p(w)=x, p(x)=u, p(y)=x, p(z)=?
  3. Spomedzi vrcholov v, w, y, z ktoré nie sú v N, si vyberieme uzol y, lebo má najmenšiu hodnotu vzdialenosti D(y) (mohli by sme vybrať aj v). Vrchol y vložíme do N a prepočítame vzdialenosti pre všetkých susedov vrcholu y, ktorí nie sú v N, teda vrcholov w a z.
    • N={u,x,y}
    • D(u)=0, D(v)=2, D(w)=3, D(x)=1, D(y)=2, D(z)=4
    • p(u)=u, p(v)=u, p(w)=y, p(x)=u, p(y)=x, p(z)=y
  4. Spomedzi vrcholov v, w, z ktoré nie sú v N, si vyberieme uzol v, lebo má najmenšiu hodnotu vzdialenosti D(v). Vrchol v vložíme do N a prepočítame vzdialenosti pre všetkých susedov vrcholu v, ktorí nie sú v N, teda vrcholu w.
    • N={u,x,y,v}
    • D(u)=0, D(v)=2, D(w)=3, D(x)=1, D(y)=2, D(z)=4
    • p(u)=u, p(v)=u, p(w)=y, p(x)=u, p(y)=x, p(z)=y
  5. Spomedzi vrcholov w, z ktoré nie sú v N, si vyberieme uzol w, lebo má najmenšiu hodnotu vzdialenosti D(w). Vrchol w vložíme do N a prepočítame vzdialenosti pre všetkých susedov vrcholu w, ktorí nie sú v N, teda vrcholu z.
    • N={u,x,y,v,w}
    • D(u)=0, D(v)=2, D(w)=3, D(x)=1, D(y)=2, D(z)=4
    • p(u)=u, p(v)=u, p(w)=y, p(x)=u, p(y)=x, p(z)=y
  6. Už iba vložíme uzol z do N a môžeme skončiť.

Nakoniec pomocou údajov o predchodcoch uzlov vieme zrekonštruovať najkratšie cesty do všetkých uzlov v grafe. Z každej cesty si vezmeme iba prvý krok (v našom prípade buď do uzla v alebo do uzla x) a ten zapracujeme do smerovacej tabuľky.

cieľový router (cieľ) susedný router na najkratšej ceste k cieľovému (brána)
v v
w x
x x
y x
z x

Samozrejme do reálnej smerovacej tabuľky sa namiesto cieľových routrov zapíšu adresy sietí, ku ktorým majú tieto routre priamy prístup a namiesto „mena“ routra sa použije IP adresa rozhrania, ktoré je napojené na spoj s uzlom u.

Pri použití LSA môže v niektorých prípadoch dochádzať k osciláciám. Predstavme si situáciu, že za cenu hrany budeme považovať množstvo prenášaných dát za nejaký čas. Uvažujme jednoduchý graf so 4 vrcholmi. Vrcholy z a x vysielajú k vrcholu w konštantne 1 MB dát za sekundu a vrchol y vysiela k vrcholu w e MB dát za sekundu. Predpokladajme, že žiadna iná komunikácia v tomto grafe neprebieha.

Ako môžeme vidieť na obrázku a, na začiatku boli smerovacie tabuľky uzlov nastavené tak, že datagramy zo z a x boli smerované priamymi spojmi k w a uzol y smeroval dáta pre w cez vrchol x. Keďže samotné posielanie dát zmenilo ceny hrán, je potrebné prepočítať smerovacie tabuľky. Pri prepočte zistia vrcholy x a y, že lacnejšia cesta k w je cez vrchol z a začnú smerovať datagramy týmto smerom. To ale opäť zmení ceny hrán a opäť sa začnú prepočítavať smerovacie tabuľky a vrcholy x, y aj z začnú smerovať datagramy opačným smerom a tak ďalej.

1.2  DVA: distance vector algorithm

DVA je algoritmus, ktorý pre každý uzol vychádza iba z cien susedných hrán a z informácií od svojich susedov. Každý vrchol si uchováva vektor podľa neho najlacnejších vzdialeností k všetkým vrcholom grafu a vektory vzdialeností svojich susedov, ktoré mu poslali.

DVA je založený na Bellman-Fordovej rovnici, ktorá vyjadruje vzťah medzi cenou najlacnejšej cesty z uzla x do uzla y a cenami ciest od susedov vrcholu x do vrcholu y. Označme dx(y) ako cenu najlacnejšej cesty z uzla x do uzla y. Potom Bellman-Fordova rovnica hovorí, že:

dx(y) = minv {c(x,v) + dv(y) }, cez všetky vrcholy v susedov vrcholu x.

V algoritme DVA budeme používať označenie Dx(y) ako očakávanú najmenšiu cenu cesty z vrcholu x do vrcholu y. Každý vrchol si uchováva vektor vzdialeností ku všetkým vrcholom grafu, tento vektor označme Dx = [Dx(y): kde y je vrchol grafu]. Každý vrchol tiež pozná ceny s ním susediacich hrán a vektory vzdialeností svojich susedov.

Inicializácia v uzle u: Du(u)=0. Pre všetkých susedov v uzla u nastav Du(v) = c(u, v) a v ich vektoroch vzdialeností nastav vzdialenosti ku všetkým vrcholom na ∞ (lebo ich reálne vektory zatiaľ nemáme) Pre všetky ostatné uzly w, ktoré nie sú susedom u nastav Du(w)=∞ Pošli svoj vektor vzdialeností všetkým svojim susedom Ak príde vektor vzdialeností od niektorého suseda w, alebo ak sa zmenia ceny susedných hrán: Pre každý vrchol y nastav Du(y) = minv{c(u,v) + Dv(y) } Ak sa niekde zmenila hodnota z pôvodného vlastného vektora vzdialeností, pošli všetkým svojim susedom nový vektor vzdialenosti

Príklad výpočtu DVA na troch uzloch je znázornený na nasledujúcom obrázku. Na začiatku (ľavý stĺpec) sa všetky vrcholy a teda aj ich vektory vzdialeností inicializujú. Takáto inicializácia vo všetkých uzloch naraz je síce nepravdepodobná, ale pre účely vysvetlenia algoritmu si to môžeme dovoliť predpokladať.

Po inicializácii pošlú všetky vrcholy svojim susedom svoje vektory vzdialeností. Vezmime si ako príklad vrchol x, ktorému prišli vektory Dy a Dz. Tieto vektory si uloží a ide prepočítať vlastný vektor podľa Bellman-Fordovej rovnice. Prepočítame Dx(y) a Dx(z):

Dx(y) = min {c(x,y) + Dy(y) ,c(x,z) + Dz(y)} = min{2+0, 7+1} = 2
Dx(z) = min {c(x,y) + Dy(z) ,c(x,z) + Dz(z)} = min{2+1, 7+0} = 3

Keďže sa nám zmenila hodnota Dx(z), zmenil sa aj celý vektor a musíme ho poslať svojim susedom. Okrem toho si vrchol x zapíše do smerovacej tabuľky, že datagramy pre vrcholy y aj z má posielať cez vrchol y. Podobne sa zmenil aj vektor vzdialeností vrcholu z. Vektor vrcholu y sa nezmenil, takže ten svoj už vektor neposiela. V ďalšej fáze si opäť všetky tri vrcholy prepočítajú svoje vektory vzdialeností, a keďže žiadnemu sa jeho vektor nezmení, žiadne ďalšie vektory sa neposielajú a systém ostane stabilný.

Pri zmene ceny niektorej hrany na to zareagujú susedné routre a prepočítajú svoje vektory vzdialeností. Ak dôjde k zmene vektora, zasielajú ho svojim susedom, tí si prepočítajú svoje vektory a tak sa táto informácia môže šíriť ďalej. Predstavme si situáciu na nasledujúcom obrázku.

Prvý prípad vykresľuje situáciu, keď sa cena hrany (x,y) zmení zo 4 na 1. V tomto prípade si vrcholy x a y prepočítajú svoje vektory vzdialeností. Všimnime si, ako sa zmení vektor vrcholu y. Pôvodný vektor (4,0,1) sa zmení na (1,0,1). Tento vektor pošle susedom. Čo sa stane vo vrchole z? Pôvodný vektor vrcholu z (5,1,0) sa zmení na (2,1,0). Tento vektor pošle svojim susedom, ale u nich sa už po prepočítaní vektory vzdialeností nezmenia a systém sa stabilizuje.

V druhom prípade sa zmení cena hrany (x,y) zmení zo 4 na 60. Čo sa stane? Na začiatku má vrchol y vektor vzdialeností (4,0,1) a z má vektor (5,1,0). Po zmene ceny hrany si y prepočíta svoj vektor podľa Bellman-Fordovej rovnice (min{60+0, 1+5} = 6, 0, 1) a pošle ho susedom. Vrchol z si následne prepočíta svoj vektor (min{50+0, 1+6} = 7, 0, 1) a pošle ho susedom. Vrchol y si následne prepočíta svoj vektor (min{60+0, 1+7} = 8, 0, 1) a tak ďalej. Takéto posielanie sa vykoná celkovo 44 krát, kým dôjde k stabilizácii. Hovoríme o takzvanom count to infinity probléme, teda o „počítaní do nekonečna“. Tomuto problému sa v stromových sieťach dá vyhnúť technikou „poisoned reverse“, kde sa pri odhalení počítania do nekonečna môže jeden z uzlov rozhodnúť zmeniť hodnotu vo svojom vektore jedenkrát na nekonečno a potom opäť hlásiť reálne hodnoty vektora, lebo ako sme videli pri znižovaní cien, sa zmeny prejavia rýchlo. „Poisoned reverse“ však stráca svoju silu v sieťach s cyklami, kde je veľmi náročné odhaliť stav počítania do nekonečna.

Výber toho, či použiť protokol založený na LSA alebo na DVA je na administrátorovi siete. Oba prístupy majú svoje výhody aj nevýhody. LSA vyžaduje pri každej zmene výmenu všetkých informácii v sieti broadcastovými alebo multicastovými správami od všetkých routrov. DVA posiela správy iba medzi susedmi, ale zato možno aj niekoľko, či až veľmi veľakrát (count to infinity problém). LSA na druhej strane môže spôsobiť oscilácie. Dijkstrov algoritmus vyžaduje čas O(e log(n)), kde n je počet vrcholov a e je počet hrán. DVA prepočíta vektor v čase O(n), ale urobí to potenciálne aj veľakrát, kým sa stabilizuje.

2.  Smerovacie protokoly vnútri autonómnych systémov

Smerovací protokol vnútri autonómnych systémov má za úlohu nastaviť, ako budú smerované datagramy medzi jednotlivými sieťami v rámci tohto autonómneho systému. Najznámejšie takéto smerovacie protokoly sú RIP a OSPF. Príbuzný protokol k OSPF je IS-IS protokol (RFC 1142). My sa bližšie pozrieme na prvé dva.

Smerovacie protokoly pre autonómne systémy sa niekedy nazývajú aj Interior Gateway Protocols (IGP).

2.1  RIP: Routing information protocol

verzia 1 : RFC 1058, verzia 2: RFC 2453

RIP je aplikačný protokol, ktorý pracuje veľmi podobne ako teoretický model DVA. V DVA sme pre jednoduchosť ako cenu uvádzali cenu hrany medzi dvoma routrami. V RIP (aj v OSPF) sa uvažujú ceny od routra k jednotlivým sieťam a podsieťam. RIP ako cenu cesty od niektorého routra k cieľovej sieti považuje počet routrov (hop-ov), ktoré sa na tejto ceste nachádzajú vrátane samotného routra. To znamená, že cena cesty k sieti priamo napojenej na daný router je rovná jednej. Maximálna cena cesty pre RIP je určená na 15 hop-ov, tým pádom by sa RIP vo väčších AS nemal používať. Všetky siete vo vzdialenosti viac ako 15 hopov sú vo vzdialenosti nekonečno (zapisuje sa číslom 16).

V DVA routre zasielajú svoje vektory vzdialeností, ak sa zmení cena lokálnych spojení. V RIP sa ceny lokálnych spojení (teda počet hop-ov) menia iba pri odpojení/pripojení. Namiesto tohto mechanizmu sa v RIP posielajú vektory vzdialeností (RIP informácie) každých 30 sekúnd, aj keď sa nič nezmenilo. Tieto vektory majú povolených maximálne 25 cieľových sietí z vnútra AS. Ak router nedostane od svojho suseda žiadne RIP informácie po dobu 180 sekúnd, je tento sused považovaný za nedostupného. RIP poskytuje aj možnosť vyžiadať si RIP informácie od suseda cez RIP požiadavku.

Keďže cena cesty sa ráta ako počet routrov na tejto ceste, môžeme povedať, že vzdialenosť susedných routrov je vždy 1. Predpokladajme, že router A má v svojom vektore vzdialeností cenu k sieti X 10 hopov cez router B. Ak od routra C príde routru A RIP informácia, že router C má vzdialenosť k sieti X iba 5 hopov, tak router A si môže zmeniť svoju vzdialenosť k sieti X na 5+1=6 hopov cez router C.

Protokol RIP sa rozšíril v roku 1982 ako súčasť BSD Unixu. Na komunikáciu používa UDP protokol a port 520. Ide teda o aplikačný protokol (používaný programom routed) na riadenie smerovacej tabuľky v sieťovej vrstve.

2.2  OSPF: Open shortest path first

verzia 2: RFC 2328

OSPF je mladší protokol ako RIP a má oproti nemu aj mnoho vylepšení. OSPF je založený na LSA algoritme, teda na kompletnej informácii o topológii siete, cene všetkých hrán a na Dijkstrovom algoritme, ktorý pre každý uzol vytvára strom najkratších ciest k jednotlivým sieťam (nie k routrom ako v teoretickom modeli).

Ceny jednotlivých hrán sú nastavované sieťovým administrátorom, nie riadené protokolom. Administrátor si však môže vybrať, či nastaví ceny hrán na 1 alebo inú konštantu, alebo sa budú vypočítavať na základe prevádzky či aktuálnej priepustnosti spojení.

Informácia o topológii siete sa získava broadcastovými správami aspoň raz za 30 minút. Správy OSPF protokolu sú prenášané priamo v tele IP datagramov.

OSPF pridáva oproti protokolu RIP ďalšiu funkcionalitu.

  • Umožňuje autentifikáciu OSPF správ. To znamená, že iba správy od routrov spravovaných administrátorom daného AS sú akceptované a žiaden útočník vo vnútri AS nemôže ovplyvňovať smerovací algoritmus.
  • Ak existuje viac ciest s rovnakou cenou, OSPF nevyžaduje vybratie iba jednej z nich ako v originálnom Dijkstrovom algoritme. Tým pádom sa môže prevádzka rozdeliť rovnomerne na obe cesty.
  • Integrovaná podpora pre multicastové smerovanie v rozšírení MOSPF (RFC 1584), ktorá pridáva multicastové informácie do existujúcich broadcastových informácií o cenách hrán.
  • Podpora pre hierarchické smerovanie vo vnútri AS je asi najdôležitejším prínosom tohto protokolu. O hierarchickom smerovaní viac v ďalšej kapitole. Pri hierarchickom smerovaní sa routre môžu organizovať do autonómnych oblastí. V každej oblasti beží nezávislé klasické OSPF smerovanie. Jednotlivé oblasti sú prepojené cez hraničné routre oblastí, ktoré tvoria chrbticovú oblasť. Aby to nebolo jednoduché, chrbticová oblasť môže obsahovať aj routre, ktoré nie sú súčasťou žiadnej z autonómnych oblastí. Chrbticová oblasť je tiež jediná, ktorá obsahuje aj brány na komunikáciu s inými autonómnymi systémami.

3.  Hierarchické smerovanie

Ani jeden z algoritmov LSA a DVA nie je vhodný na globálne použitie pre celý internet. Keďže na svete sú milióny routrov, každý z nich by si musel uchovávať a počítať vzdialenosti ku všetkým ostatným. Tento systém by sa nikdy neustálil a výmenné správy by zahltili internet tak, že by už možno ani neostalo prenosové pásmo pre reálnu komunikáciu koncových zariadení.

Podobne ako napríklad pri DNS má aj hierarchické smerovanie veľa výhod oproti centralizovanému riešeniu. Je to hlavne nezávislosť administrácie lokálnych skupín sietí a routrov.

Routre v tom istom AS komunikujú spoločným smerovacím protokolom vnútri-AS (napr. RIP alebo OSPF). Každý AS môže používať vo vnútri ľubovoľný smerovací protokol. Každý AS komunikuje s ostatnými AS cez routre na hranici AS, ktoré nazývame brány, alebo gateway routre, ktoré sú napojené na jeden alebo viac routrov iných AS. Jednotlivé AS medzi sebou komunikujú nejakým smerovacím protokolom medzi-AS. Správy protokolu medzi-AS však prichádzajú aj na routre vo vnútri AS. Smerovacie tabuľky routrov tak môžu byť ovplyvňované ako smerovacím protokolom vnútri-AS tak aj medzi-AS.

Majme nasledovné 3 autonómne systémy.

Predpokladajme, že k routru 1d príde datagram, určený pre sieť mimo AS1. Router 1d vie, že na to, aby datagram odišiel, musí ho nasmerovať ku bráne, ale ku ktorej? V AS1 sú dve brány 1c a 1b. Cestu k nim vieme zistiť na základe nejakého smerovacieho protokolu vnútri-AS. Na určenie toho, cez ktorý z týchto dvoch routrov má datagram odoslať, už slúži smerovací protokol medzi-AS.

Protokol medzi-AS musí distribuovať informácie, na základe ktorých vie každý AS, ktoré adresy sú dostupné cez ktoré susedné AS, a teda aj cez ktoré brány. Táto dostupnosť sa musí premietnuť do všetkých routrov v AS.

Predpokladajme, že AS1 sa naučí cez medzi-AS protokol, že sieť X je dostupná cez AS3 (t.j. cez bránu 1c), ale nie cez AS2 (t.j. cez bránu 1b). Medzi-AS protokol o tom informuje všetky routre vo vnútri AS1. Keď router 1d zistí, že X je dostupná cez bránu 1c, použije znalosti získané z protokolu vnútri-AS. Zistí, cez aké rozhranie posiela datagramy smerom k 1c a zapíše si, že aj datagramy pre sieť X majú ísť cez toto rozhranie.

Teraz predpokladajme, že AS1 sa naučilo cez medzi-AS protokol, že sieť X je dostupná cez AS2 aj cez AS3. To, či bude datagramy pre sieť X posielať cez 1b alebo 1c, je už úloha pre protokol vnútri-AS. Cez takzvané smerovanie horúceho zemiaku (hot potato routing), musí protokol vnútri-AS pre každý router zistiť cenu ciest ku 1b a 1c, vybrať tú lacnejšiu a doplniť riadok v smerovacích tabuľkách routrov vo vnútri AS pre cieľovú sieť X.

4.  Smerovací protokol medzi autonómnymi systémami: BGP

BGP: Border gateway protocol, verzia 4, RFC 4271, RFC 1772, RFC 1773

BGP je medzi-AS smerovací protokol, ktorý je v súčasnosti de facto štandardom v dnešnom internete. BGP poskytuje každému AS:

  • získanie informácií o dostupnosti sietí od susedných AS,
  • prenos týchto informácií ku všetkým routrom vnútri AS,
  • zistenie „dobrých“ ciest k sieťam na základe informácií o dostupnosti siete a politiky riadenia AS,
  • zasielanie informácií o dostupnosti svojich sietí zvyšku internetu – táto vlastnosť je kľúčová, inak by vznikali izolované skupiny sietí, ktoré by o sebe navzájom nevedeli.

BGP je veľmi zložitý protokol. Keďže však ide o dôležitý protokol, ktorý spája celý internet, pozrieme sa aspoň na kľúčové súčasti protokolu a ich funkciu.

BGP správy sú prenášané cez TCP spojenia na porte 179. Tieto spojenia obvykle zodpovedajú fyzickým spojeniam, špeciálne to platí pre spojenia brán medzi rôznymi AS. Cez tieto spojenia sa susedné AS informujú o dostupnosti sietí. Keď niektorý AS informuje o dostupnosti siete, vyjadruje tým aj prísľub, že ak dostane datagramy určené pre túto sieť, tak ich aj k tejto sieti nasmeruje. Ak sa napríklad AS1 naučí, že sieť X je dostupná cez AS2, tak môže všetky datagramy pre sieť X posielať cez AS2. Ak sa brána v AS1 dozvie informáciu o dostupnosti siete X, tak cez BGP spojenia vnútri AS1 môže túto informáciu odovzdať všetkým routrom vnútri AS1. Keď sa routre v AS1 dozvedia túto správu, prispôsobia si svoje smerovacie tabuľky aj za pomoci informácií od smerovacieho protokolu vnútri-AS. Jednotlivé AS si medzi sebou vymieňajú v BGP správach celé zoznamy dostupných sietí.

AS1 sa tiež môže rozhodnúť, že povie AS3, že sieť X je dostupná cez AS1. Toto rozhodnutie je často riešené v politike smerovania, ktorá je často riadená vzťahmi provider-zákazník alebo dohodami medzi jednotlivými providermi medzi sebou. Napríklad ak AS1 je zákazníkom AS2 a AS3, tak nemá záujem na tom, aby pre nich smeroval cudziu komunikáciu cez seba.

Každý AS má svoje jedinečné číslo zvané ASN: autonomous system number (RFC 1930), ktoré je prideľované organizáciou IANA (niektoré AS ani nemusia mať svoje číslo, ak neposkytujú smerovanie cudzích sietí iným AS).

V BGP správach okrem zoznamov dostupných sietí sú aj ďalšie atribúty. Dva z najdôležitejších sú AS-PATH a NEXT-HOP. AS-PATH obsahuje postupnosť čísiel ASN, cez ktoré budú smerované datagramy pre danú sieť. Keď stanica preposiela informáciu o dostupnosti pre iné AS, pridá svoje ASN na koniec AS-PATH. Táto informácia sa používa na zabránenie cyklickým smerovaniam, ale aj na výber vhodnejšej cesty v prípade viacerých možností smerovania k danej sieti.

NEXT-HOP je atribút, ktorý obsahuje IP adresu rozhrania brány, cez ktoré je potrebné smerovať datagramy pre cieľovú sieť X. Napríklad, v prípade, že BGP správa prichádza z brány 2a z AS2 do brány 1b v AS1. NEXT-HOP obsahuje IP adresu rozhrania brány 2a, na ktoré je napojená brána 1b. Brána 1b, na základe importnej politiky, môže informovať o dostupnosti siete X všetky routre vo vnútri AS1 cez vnútorné BGP správy. V tom prípade bude NEXT-HOP obsahovať niektorú IP adresu rozhrania brány 1b vo vnútri AS1. Túto adresu použijú vnútorné routre v AS1 na určenie rozhrania, cez ktoré majú posielať datagramy pre sieť X cez 1b.

Ak sa AS naučí viac smerov k rovnakej sieti, môže sa rozhodnúť pre vylúčenie jedného zo smerov. Môže na to použiť politiku smerovania, ktorá je ovplyvňovaná administrátorskými, ale často aj manažérskymi rozhodnutiami (napríklad, ak AS je napojený na viacerých providerov, a nie všetci požadujú rovnakú cenu za prenesené dáta, alebo môže ísť o vyhranenie niektorých spojení iba pre (manažérsky) prioritné služby). Ak politika smerovania neurčí, ktorý zo smerov má byť vylúčený, môže byť niektorý smer vylúčený na základe dĺžky AS-PATH. Ak si chceme zachovať obe spojenia, môžeme nechať výber cesty na smerovací protokol vnútri-AS (hot potato routing). Ak stále ostanú dve alternatívne cesty s rovnakou cenou, dajú sa použiť aj ďalšie BGP identifikátory na výber optimálnej cesty. Kritériá na výber ciest môžu byť aj veľmi komplikované, ale tomu sa už venovať nebudeme.

5.  Unicast, broadcast, multicast a anycast.

Táto kapitolka slúži iba na vysvetlenie štyroch smerovacích schém:

  • Unicast je taká smerovacia schéma, pri ktorej datagramy vychádzajúce od zdroja dát smerujú vždy k jedinej presne určenej cieľovej stanici. Unicast smerovanie je vyžadované napríklad protokolom TCP, kedy musí komunikácia prebiehať vždy len medzi dvojicou staníc.
  • Anycast je smerovacia schéma, pri ktorej je viac potenciálnych príjemcov správy, ale správa je doručená iba jednému z nich, obvykle najbližšiemu. Anycast sa využíva napríklad pri komunikácii s koreňovými DNS servermi prípadne aj niektorými TLD DNS servermi. Ako vieme, existuje iba 13 IPv4 adries koreňových DNS serverov, ale reálne je každá z týchto IPv4 adries použitá pre viaceré stanice. Požiadavka na koreňový DNS server teda môže prísť na ľubovoľný (jeden) z týchto serverov.
  • Broadcast je smerovacia schéma, ktorá zaručuje doručenie odoslanej správy všetkým uzlom, či podsieťam. Broadcast sa používa napríklad pri protokole OSPF, ktorý pred samotným spustením Dijkstrovho algoritmu potrebuje rozoslať od každého routra ku každému routru informáciu o lokálnych cenách spojov (hrán). Pojem broadcast sa používa aj na označenie správy vo vnútri siete určenej pre všetky stanice v sieti. Na tomto princípe funguje napríklad protokol DHCP alebo ARP (bude vysvetlený pri spojovej vrstve). Na aplikačnej vrstve funguje na princípe broadcastu napríklad peer-to-peer protokol Gnutella.
  • Multicast je smerovacia schéma, ktorá rozosiela správy každému, kto je prihlásený v danej multicastovej skupine. Multicast je veľmi podobný broadcastu, pretože zabezpečuje, aby rozosielané správy prijímali všetky stanice a routre, ktoré ich prijímať chcú, ale na rozdiel od broadcastu zabezpečuje aj to, aby stanice, a ak to nebráni prvej podmienke aj routre, neprijímali rozosielané správy, ak si to neprajú. Multicast používajú hlavne rádiá a televízie na streamované vysielanie cez internet. Je však veľmi užitočný aj napríklad pre videokonferencie, gridové výpočty, sieťové hry alebo rozosielanie aktualizácií programov.

6.  Broadcastové smerovanie

V súvislosti s broadcastom sa používa pojem broadcastová doména, ktorá určuje množinu sietí a routrov, v ktorej sa majú šíriť broadcastové správy. Ak si vezmeme napríklad protokol OSPF, tak broadcastovú doménu tvoria všetky routre v AS.

Pri broadcastovom smerovaní je cieľom to, aby vyslanú správu dostali všetky uzly (stanice a/alebo routre) v broadcastovej doméne. Broadcastové správy sa nikdy nešíria pre celý internet, ale vždy len v rámci AS alebo v rámci siete. Broadcastové smerovanie sa realizuje buď pre celý AS alebo jeho časť.

Broadcast by sa dal realizovať aj tak, že každému uzlu v broadcastovej doméne pošleme kópiu správy priamo zo zdroja. Ak máme N uzlov, tak vyšleme N správ. Toto riešenie je síce jednoduché, ale neefektívne. Lepšie je, ak zdrojový uzol vyšle do každého spoja iba jednu správu a tá sa rozmnoží až po ceste tak, aby každý uzol dostal svoju kópiu a zároveň, aby žiaden uzol nemusel správu vysielať viackrát tým istým spojením.

Hlavným problémom broadcastového smerovania je teda zistenie, kedy je potrebné vytvárať kópie broadcastových správ a do ktorých spojov ich zasielať. Popíšeme si 3 prístupy k spôsobu broadcastového smerovania: nekontrolované zaplavenie, kontrolované zaplavenie a spanning tree (kostra grafu).

6.1  Nekontrolované zaplavenie

Tento prístup používa jednoduché pravidlo. Ak na router príde broadcastová správa, router vytvorí kópiu tejto správy a rozošle túto správu do všetkých rozhraní okrem toho, odkiaľ správa prišla. Tento prístup môže fungovať úplne bezchybne pokiaľ sa v grafe tvorenom routrami a spojmi nevyskytuje cyklus. Vezmime si vyššie nakreslený obrázok. Ak router R1 vyšle správu, dostane ju R2 a rozošle ju k R3 a R4. R3 dostal správu od R2 takže ju pošle na všetky ostatné rozhrania, teda k routru R4, ten ju prepošle opäť k R2, ktorá ju zas prepošle k R1 a R3. Takáto situácia vyústi k nekonečnému cykleniu dvoch správ, jednej v smere a druhé proti smeru hodinových ručičiek. Ak však máme v grafe viac cyklov, dochádza k nekontrolovanému množeniu broadcastových správ. Takému javu hovoríme broadcastová búrka, ktorá vedie k úplnému zahlteniu všetkých routrov v broadcastovej doméne.

6.2  Kontrolované zaplavenie

Kľúčom k zabráneniu nekonečných rozosielaní pri kontrolovanom zaplavovaní je zistenie routra, že danú správu už raz rozosielal a nebude to robiť opäť.

Jedným riešením je, že každý pôvodný odosielateľ správy pribalí k správe aj jedinečné číslo broadcastovej správy. Každý uzol si potom musí pamätať všetky čísla správ, ktoré už rozosielal a v prípade, že už áno, tak ich druhýkrát nerozošle. Tento prístup využíva Gnutella.

Druhý prístup ku kontrolovanému zaplaveniu je reverse path forwarding (RPF). Idea RPF je jednoduchá. Pokiaľ príde na nejaký uzol broadcastová správa, tak ju rozpošle cez všetky rozhrania okrem prijímajúceho iba vtedy, ak táto správa prišla cez rozhranie, ktoré je súčasťou najkratšej unicastovej cesty k zdrojovému uzlu. V opačnom prípade je správa zahodená. Využíva teda smerovaciu tabuľku určenú pre unicastové smerovanie. Toto využitie je tak trochu obrátené, lebo smerovacia tabuľka nastavuje smerovanie odchádzajúcich správ a pri RPF filtrujeme prichádzajúce broadcastové správy. Na nasledujúcom obrázku môžeme vidieť, ako sa bude šíriť broadcastová správa z uzla A do celého grafu pri použití RPF. Hrubou čiarou sú naznačené spoje, ktoré sú na najkratšej ceste od jednotlivých uzlov k uzlu A. Šípky s obdĺžničkom označujú správy, ktoré budú prijímajúcim routrom zahodené.

6.3  Spanning tree (kostra grafu)

Aj keď predchádzajúce techniky zabraňujú broadcastovým búrkam, predsa len sa stáva, že niektoré uzly dostanú viac kópií tej istej správy. Riešením aj tohto nedostatku je práve smerovacia schéma spanning tree.

Pri spanning tree sa ešte pred odoslaním prvej broadcastovej správy musí vyrobiť strom rozosielania obsahujúci všetky uzly. Hrany tohto stromu tvoria vybrané spojenia medzi uzlami. Ak je už strom rozosielania hotový, broadcastové správy sa šíria iba pozdĺž hrán tohto stromu. Keďže ide o strom, neexistujú v ňom cykly a každý uzol dostane vždy iba jednu kópiu broadcastovej správy.

Samozrejme je ideálne, ak tento strom bude minimálny. Určite si spomínate na minimálnu kostru grafu, ktorá sa preberala v predmete PAZ1b. Kruskalov algoritmus, ktorý sa na PAZ1b preberá, však vyžaduje úplnú znalosť topológie siete. Metóda spanning tree negeneruje vždy minimálny strom. Pred vytvorením stromu sa uzly musia dohodnúť, ktorý z uzlov grafu bude centrálny uzol (nazývaný aj rendezvous point). Potom všetky uzly pošlú pripájaciu unicastovú správu smerom k centrálnemu uzlu. Ako správa prechádza jednotlivými routrami na ceste k centrálnemu uzlu, routre si zaznačujú, že hrany, po ktorých prešla, sú súčasťou stromu. Ak takáto správa dôjde na uzol, ktorý už je súčasťou stromu, správa sa zahadzuje, lebo by aj tak šla iba po tých spojeniach, ktoré už sú súčasťou stromu. Tým pádom aj na vytvorenie stromu je potrebné poslať iba toľko správ, koľko je hrán vo výslednom strome, a teda toľko správ, ako pri šírení už bežnej broadcastovej správy.

7.  Multicastové smerovanie

Multicastové smerovanie má za úlohu dopraviť správy medzi všetkými členmi danej multicastovej skupiny. Multicastová skupina je identifikovaná špeciálnou IP adresou, ktorá nie je pridelená žiadnej stanici. V protokole IPv4 sme hovorili o triedach IPv4 adries. IPv4 adresy triedy D sú práve IPv4 adresy multicastových skupín. V protokole IPv6 je multicastové adresovanie možné aj v rámci siete či autonómneho systému (IPv6 nemá podporu pre broadcastové správy).

Pred tým ako sa pustíme do multicastového smerovania, musíme spomenúť protokol IGMP: Internet group management protocol (RFC 3376). Tento protokol slúži iba na komunikáciu medzi stanicou a jej predvolenou bránou. Má za úlohu umožniť stanici prihlásiť sa k nejakej multicastovej skupine. Protokol IGMP umožňuje bráne informovať všetky lokálne siete o ponúkaných multicastových skupinách, ku ktorým sa v prípade záujmu môžu stanice pripojiť. Tieto skupiny sa brána dozvie buď od multicastového smerovacieho protokolu, alebo jednoducho preto, že aj iná stanica v niektorej z jej sietí je členom danej multicastovej skupiny.

Stanica si môže vybrať z ponúkaných skupín, alebo požiadať o členstvo v nejakej z týchto skupín tiež cez protokol IGMP. Stanica môže tiež požiadať o členstvo aj v inej multicastovej skupine, ktorá nebola ponúkaná (používateľ si ju mohol nájsť napríklad cez nejakú webovú stránku). Ak stanica požiada o členstvo v skupine, je už na bráne, aby pomocou multicastového smerovacieho protokolu zabezpečila, že bude prijímať správy pre túto multicastovú skupinu, aby ich mohla posielať tejto stanici.

IGMP vyžaduje, aby brána raz za čas informovala o možnosti byť členom multicastovej skupiny aj stanici, ktorá už je členom. Ak táto stanica neodpovie opätovnou požiadavkou o členstvo v skupine, je z tejto skupiny automaticky vylúčená.

Multicastový smerovací protokol musí zabezpečiť, aby každý člen multicastovej skupiny dostával spoločné správy. Prístupy na spôsob distribúcie týchto správ sme už spomínali pri broadcastovom smerovaní: RPF (tu nazývaný „source based tree“ teda strom založený na zdroji) a spanning tree (tu nazývaný „group-shared tree“ teda zdieľaný strom skupiny). Prvý prístup je používaný v protokole DVMRP = distance-vector multicast routing protocol(RFC 1075) a v protokole PIM-DM = protocol independent multicast routing protocol – dense mode (RFC 3973). Druhý prístup sa používa v protokole PIM-SM = PIM – sparse mode (RFC 4601,RFC 3569,RFC 4607).

Pri RPF prístupe je ťažké určiť, do ktorého spojenia treba skopírovať multicastovú správu, aby tieto správy neboli zbytočne rozosielané uzlom, ktoré nechcú a nemusia byť súčasťou multicastového rozosielacieho stromu. Vykoná sa teda to, že sa broadcastovým spôsobom rozpošle informácia o možnosti prijímania správ danej multicastovej skupiny. Koncové routre, ktoré nemajú pripojených žiadnych členov danej multicastovej skupiny, pošlú orezávaciu správu, že o dané dáta nemajú záujem. V prípade vnútorného routra, ktorý rozosielal informáciu o skupine ďalším susedom, môže odoslať orezávaciu správu, iba ak od všetkých týchto susedov prídu orezávacie správy. Orezávacie správy sa posielajú vždy tým routrom, ktoré danému routru poslali správu o možnosti pripojenia k multicastovej skupine. Ak router orezávaciu správu nepošle, po čase začne dostávať správy tejto multicastovej skupiny, ktoré musí ďalej posielať všetkým neorezaným routrom a prihláseným staniciam v niektorej zo svojich lokálnych sietí.

Ak sa používa prístup založený na spanning tree, všetci účastníci sa pripájajú k stromu rozosielania cez unicastovú pripájaciu správu na centrálny uzol. Žiadne orezávanie sa robiť nemusí, lebo routre, ktoré nie sú súčasťou spanning tree žiadne informácie o tejto skupine nedostávajú (nevedia, že existuje). Špeciálnym prípadom kedy sa spanning tree vyplatí je, ak je v skupine vždy len jeden zdroj vysielania. V tom prípade je odosielateľ automaticky zvolený za centrálny uzol a správy putujú po optimálnych cestách.

Multicast má podporu aj pre celý internet cez protokol MSDP = Multicast source discovery protocol (RFC 3618, RFC 4611). Opäť ide o hierarchický typ smerovania, ktoré funguje ako multicastový variant BGP protokolu.

8.  Úlohy a diskusia

  • V grafe na obrázku 4.27 (na ktorom sme robili príklad pre Dijkstrov algoritmus) predpokladajte, že je nastavené routovanie algoritmom DVA a všetky vrcholy už sú v stabilnom stave.
    • Napíšte ako vyzerajú vektory vzdialeností jednotlivých uzlov.
    • Predpokladajme, že sa zmení cena hrany (z,w) z 5 na 1. Ako sa v prvej fáze zmenia vektory vzdialeností na vrcholoch w a z, ako sa v druhej fáze zmenia vektory vo všetkých vrcholoch? Koľko celkovo správ si budú musieť vymeniť všetky vrcholy dohromady, pokiaľ sa opäť dosiahne stabilný stav? Bude potrebných menej správ ako počet správ, ktorý by potrebovali vrcholy na prepočítanie ciest algoritmom LSA?
  • Predstavte si, že chcete vytvoriť vlastný program na telekonferenciu fungujúcu celosvetovo. Aký multicastový protokol by ste použili? Skúste zistiť aké organizácie by ste museli kontaktovať, aby tento multicast naozaj fungoval celosvetovo. Čo by vám tieto organizácie museli poskytnúť?

9.  Čo sme nespomenuli

  • VPN (Virtual private network) je spôsob, ktorým sa pomocou aplikačných protokolov dosiahne, že počítače ktoré sú fyzicky v iných sieťach, hoc aj veľmi ďaleko od seba, sú v rovnakej virtuálnej sieti. V operačnom systéme sa vytvorí nové virtuálne rozhranie s novou IP adresou, ktorá prislúcha buď reálnej vzdialenej sieti (ak VPN server simuluje switch), alebo virtuálnej privátnej sieti (ak VPN server prevádzkuje samostatnú virtuálnu sieť, často zapojenú do vzdialenej fyzickej siete cez NAT, ktorý na serveri realizuje prepojenie virtuálnej siete a fyzickej siete).
  • TOR (The Onion Router) je anonymizačná sieť, ktorá opäť pomocou aplikačného šifrovacieho protokolu zabezpečuje anonymitu iniciátorov spojenia vytvorením spojení s cieľom cez reťaz anonymizačných serverov. Môžete si o tom pozrieť napr. toto video.

10.  Otestujte sa

zdroje:

  • James F. Kurose, Keith W. Ross: Computer Networking: A Top-Down Approach, 4th edition. Pearson Education, Inc., ISBN: 0-321-51325-8, 878 pages, 2008