Dynamické smerovanie

Tomáš Babiak, xbabiak@fi.muni.cz

Obsah

1 Smerovanie
2 Distance Vector smerovanie
- 2.1 RIP
- 2.2 BGP
3 Link State smerovanie
- 3.1 OSPF
4 Bird
5 Použité zdroje

1 Smerovanie

Cieľom smerovania je výber najlepšej cesty poľa rôznych kritérií (napríklad priepustnosť, oneskorenie, cena).
Smerovač (router) sa na základe položiek v smerovacej tabuľke rozhodne, na ktoré sieťové rozhranie má prijatý paket poslať.
Exitujú dva prístupy smerovania: statické a dynamické. Pri statickom smerovaní sa smerovacia tabuľka vyplní ručne. Nevýhodou je, že každú zmenu v sieti treba ručne uplatniť na smerovači. Pri dynamickom smerovaní si smerovače navzájom vymieňajú informácie o svojom okolí a dynamicky upravujú svoje smerovacie tabuľky podľa aktuálneho stavu siete.

Smerovanie sa uplatňuje buď vo vnútri autonómneho systému, na to sa používajú Interior gateway protocols (IGP), alebo medzi autonómnymi systémami, to sú Exterior gateway protocols (EGP).

Dva prístupy k smerovaniu:
- Distance Vektor (DV) - berie sa v úvahu počet prechodov k cieľu
- Link state (LS) - na základe dostupnosti susedov

2 Distance Vector smerovanie

Predpokladom je, že na začiatku pozná každý smerovač iba cestu a cenu k svojim susedom. Cieľom je, aby bola v každom smerovači smerovacia tabuľka pre každý cieľ.

Funguje to tak, že každý smerovač udržuje Distance Vector (dvojica <Cieľ, Cena>) ku všetkým cieľom. Na začiatku pozná iba cenu k susedom, zvyšok je nastavený na nekonečno. Smerovač periodicky zasiela kópiu svojich DV susedom. Po prijatí DV zvýši smerovač cenu o cenu cesty k susedovi (od suseda) a porovná so svojimi DV. Pokiaľ je táto cena lepšia ako tá súčasná, tak smerovač aktualizuje vlastný DV a svoju smerovaciu tabuľku. Pri výpadku hrany (cesty k susedovi) vzrastie cena na nekonečno a postupne sa smerovač dozvie inú (za predpokladu, že iná cesta existuje).
Aby sa predišlo zacykleniu, tak smerovač nikdy neoznamuje cestu naspäť uzlu, od ktorého sa ju dozvedel

2.1 RIP

Routing Information Protokol je starý protokol vyvinutý firmou Xerox, ktorý je definovaný v RFC 1058. Ide o DV protokol typu IGP, ktorý používa počet uzlov a nekonečná (nedostupná) cesta má hodnotu 16. Smerovače zasielajú informácie každých 30 sekúnd s využitím UDP na porte 520.
Existuje aj RIP 2 (RFC 2453). Oproti pôvodne verzie pridáva napríklad podporu autentizácie a distribúcie sieťovej masky.

Výhodou RIP je jeho jednoduchosť. Nevýhodou je obmedzenie na veľkosť siete a pomalá stabilizácia pri výpade linky a nie práve najvhodnejšia metrika.

2.2 BGP

Border Gateway Protocol tvorí základ smerovania na Internete. Zabezpečuje smerovanie medzi autonómnymi systémami a vyvinul sa z protokolu EGP. Súčasná 4-tá verzia protokolu je definovaná v RFC 4271.
Používa sa Path Vector smerovanie, ktoré je podobné ako DV smerovanie, ale namiesto koncových uzlov sa posielajú celé cesty, čo zjednodušuje detekciu cyklov. BGP tiež umožňuje definovať pravidlá smerovania, takzvané politiky. (Napríklad, či sa daný autonómny systém dá použiť ako tranzitný a podobne.) Na rozosielanie informácií používa protokol TCP, konkrétne port 179 pre naviazanie spojenia.
Výhodou tiež je, že smerovacie informácie nie sú vymieňané periodicky, ale iba v prípade zmeny.

3 Link State smerovanie

Rovnaké predpoklady a cieľ ako u DV, ale iná idea. V tomto prípade sa šíri iba topológia siete a cesty si smerovače spočítajú samy.
Každý smerovač udržuje databázu stavu spojov (LS - Links State) a periodicky zasiela LS pakety (LSP - Link State Packet), v ktorých sa popisuje stav rozhraní smerovača a jeho susedov (teda stav pripojených sieti). Súhrn všetkých LSP tvorí topologickú mapu siete. Vďaka tomu si každý smerovač zostaví strom, ktorý zobrazuje aké uzly sú pripojené k akým ďalším uzlom. Každý smerovač (uzol) si nezávisle spočíta cesty do všetkých dostupných sietí. Používa sa na to Dijkstrův algoritmus najkratšej cesty.
Hlavnými výhodami oproti DV je zabránenie cyklov a schopnosť rýchlej konvergencie. Najväčšou nevýhodou je zložitejšia implementácia a udržovanie kompletnej mapy siete v každom uzle.

3.1 OSPF

Open Shortest Path First verzia 2 je definovaný v RFC 2328, verzia pre IPv6 v RFC 2740. OSPF nepoužíva TCP a ani UDP ale IP protokol 89.
Využíva hierarchické smerovanie, kedy môže byť sieť vrámci jedného autonómneho systému rozdelená to menších sietí, tzv. oblastí (area). Topológia danej oblasti ostáva skrytá ostatným oblastiam a tak umožňuje robiť zmeny topológie v každej oblasti nezávisle na ostatných. Práve jedna oblasť tvorí tzv. OSPF (backbone), ku ktorej musia byť pripojené všetky ostatné oblasti. Každá oblasť používa individuálnu kópiu algoritmu pre výpočet najkratších ciest, preto má svoju topologickú databázu, ktorá je vo všetkých smerovačoch oblasti totožná. Hraničné oblasti majú toľko databáz, koľko oblastí prepojujú. Vďaka tomu smerovanie OSPF prebieha v dvoch stupňoch: vnútri oblasti a medzi oblasťami.
Smerovanie pomocou OSPF je založené na jednej bezrozmerovej metrike, ktorá je obecne označovaná ako cena (najlepšia cesta s najnižšou súhrnnou cenou). Cena spojov v zloženej ceste zodpovedá priepustnosti spojov, nákladom na spoje a podobne.
OSPF reaguje rýchlo na topologické zmeny siete.

4 Bird

BIRD je akronym pre Bird Internet Routing Daemon. Ide o dynamický smerovač, ktorý bol ako študentský projekt vyvinutý na Matematicko-fyzikálnej fakulte Univerzity Karlovej. Navrhnutý a testovaný bol na pod Linuxom 2.0 až 2.4 a potom bol portovaný pre FreeBSD a NetBSD. Môže byť voľne distribuovaný podľa pravidiel GNU GPL. Pracuje nad IPv4 aj IPv6 a podporuje BGPv4, RIPv2, OSPFv2 (iba IPv4), virtuálny protokol pre výmenu smerovacích informácií medzi rozdielnymi smerovacími tabuľkami a statické smerovanie.

Konfiguračný súbor sa väčšinou nachádza v /etc/bird.conf. Konfigurácia má globálne nastavenia, čo je napríklad nastavenie logovania, rôznych filtrov, funkcií, ID smerovača a rôzne protokolové inštancie. V každej protokolovej inštancii je možné potom nastaviť konkrétne nastavenia pre daný protokol.
Príklad jednoduchého konfiguračného súboru. Aktivuje synchronizáciu smerovacích tabuliek kernelom OS, každých 10 sekúnd skenuje, či nie je nové sieťové rozhranie, spustí RIP na všetkých nájdených sieťových rozhraniach. Definuje logovania do systémového logu a jednoduchý filter, ktorý akceptuje všetko.

log syslog { debug, trace, info, remote, warning, error, auth, fatal, bug };
filter okay { accept; }
protocol kernel {
        persist;                # Don't remove routes on BIRD shutdown
        scan time 20;           # Scan kernel routing table every 20 seconds
        export all;             # Default is export none
}

protocol device {
        scan time 10;           # Scan interfaces every 10 seconds
}

protocol rip {
        export all;
        import all;
}

Príklad konfigurácie protokolu OSPF:

protocol ospf MyOSPF {
    rfc1583compat yes;
    area 0.0.0.0 {
        stub no;
        tick 1;
        interface "eth*" {
            hello 9;
            retransmit 6;
            cost 10;
            transit delay 5;
            dead count 5;
            wait 50;
            type broadcast;
            authentication simple;
            password "pass";
        };
        interface "arc0" {
            type nonbroadcast;
            poll 14;
            neighbors {
                10.1.1.2 eligible;
                10.1.1.4;
            };
            strict nonbroadcast yes;
        };
    };
    area 20 {
        stub 1;
        interface "ppp1" {
            hello 8;
            authentication none;
        };
    };
}