Smerovanie

Smerovanie je proces výberu cesty pre prevádzku v sieti medzi viacerými sieťami. Vo všeobecnosti sa smerovanie vykonáva v mnohých typoch sietí vrátane sietí s prepínaním ciest, ako je napríklad verejná telefónna sieť (PSTN), a počítačových sietí, ako je napríklad internet .

V sieťach s prepínaním paketov je smerovanie proces rozhodovania na vyššej úrovni, ktoré smeruje sieťové pakety z ich zdroja k ich cieľu cez medziľahlé uzly siete pomocou špecifických mechanizmov prepínania paketov. Prepínanie paketov je prechod sieťových paketov z jedného sieťového rozhrania na druhé. Medziľahlé uzly sú zvyčajne sieťové hardvérové zariadenia, ako sú napríklad smerovače, brány, firewally alebo prepínače . Bežné počítače, v prípade, že majú viacero sieťových kariet, môžu tiež vykonávať smerovanie, hoci nemajú špeciálne optimalizovaný hardvér pre túto úlohu.

Smerovací proces zvyčajne vykonáva svoje rozhodovanie, kam poslať dáta, na základe smerovacích tabuliek . Smerovacie tabuľky si uchovávajú záznam trás k rôznym cieľom v sieti. Smerovacie tabuľky môžu byť zadané administrátorom, pozorovaním sieťovej prevádzky alebo zostavené pomocou smerovacích protokolov. V dnešnej dobe môže samotné smerovacie tabuľky rozposlať sieťovým zariadeniam (tzv. whiteboxom) aj sieťový radič (controller), ktorý riadi tok dát v takzvanej softvérovo-definovanej sieti (SDN).

Smerovanie v užšom slova zmysle často odkazuje na IP smerovanie a je v kontraste s premostením (bridgovaním). IP smerovanie predpokladá, že sieťové adresy sú štruktúrované (majú hierarchiu) a že podobné adresy majú zariadenia v rámci siete. Štruktúrované adresy umožňujú, aby jeden záznam smerovacej tabuľky predstavoval cestu k skupine zariadení v sieti. Vo veľkých sieťach, štruktúrované adresovanie (smerovanie v užšom slova zmysle) prevyšuje neštruktúrované adresovanie (premostenie). Smerovanie sa stalo dominantnou formou dorozumievania zariadení na internete. Premostenie je stále široko používané v rámci miestnych počítačových sietí (LAN). Schémy smerovania sa líšia v tom, ako doručujú správy:

• Unicast doručuje správu konkrétnemu zariadeniu použitím one-to-one asociácie medzi odosielateľom a cieľom: každá cieľová adresa unikátne identifikuje jeden koncový bod prijímača.
• Broadcast doručuje správu všetkým zariadeniam v sieti použitím one-to-all asociácie; jeden paket od odosielateľa je smerovaný do všetkých možných zariadení v sieti pod broadcastovou adresou. Sieť automaticky replikuje paket podľa potreby aby sa dostal ku každému cieľu v broadcaste, ktorý je zvyčajne celá podsieť.
• Multicast doručuje správu skupine zariadení, ktoré preukázali záujem pre získanie správy pomocou one-to-many-of-many alebo many-to-many-of-many asociácie; pakety sú smerované súčasne v jednom prenose viacerým prijímateľom. Multicast sa líši od broadcastu tým, že posiela správu vybraným zariadeniam a nie nutne všetkým.
• Anycast doručuje správu hociktorému zariadeniu v skupine zariadení, zvyčajne k najbližšiemu od zdroja správy pomocou one-to-one-of-many asociácie, kde sú pakety smerované k hociktorému zariadeniu v skupine potenciálnych prijímateľov, ktoré sú definované rovnakou cieľovou adresou.

Unicast je dominantnou formou doručovania správ na internete. Tento článok sa zameriava na smerovacie algoritmy unicastu.

Distribúcia topológie

Pri statickom smerovaní môžu malé siete používať manuálne nakonfigurované smerovacie tabuľky. Väčšie siete majú zložité topológie, ktoré sa môžu rýchlo meniť, čo znemožňuje manuálnu konfiguráciu smerovacích tabuliek tak, aby odrážali skutočnosť. Napriek tomu väčšina verejnej komutovanej telefónnej siete (PSTN) používa vopred vypočítané smerovacie tabuľky so záložnými cestami, ak sa najpriamejšia cesta zablokuje (pozri smerovanie v PSTN ).

Dynamické smerovanie sa pokúša vyriešiť tento problém automatickým vytváraním smerovacích tabuliek na základe informácií prenášaných smerovacími protokolmi, čo umožňuje sieti konať takmer autonómne pri predchádzaní zlyhania a znefunkčnení siete. Dynamické smerovanie dominuje v lokálny počítačových sieťach. Príklady dynamických smerovacích protokolov a algoritmov zahŕňajú Routing Information Protocol (RIP), Open Shortest Path First (OSPF) a Enhanced Interior Gateway Routing Protocol (EIGRP).

Distance vector algoritmy

Distance vector alogirtmy používajú Bellman-Fordov algoritmus . Tento prístup priraďuje tzv. cenu (cost) každému z prepojení medzi každým uzlom v sieti. Uzly posielajú informácie z bodu A do bodu B cestou, ktorej výsledkom sú najnižšie náklady na cestu (t.j. súčet cien na prepojenia medzi použitými uzlami).

Keď sa uzol prvýkrát spustí, pozná iba svojich bezprostredných susedov a priamu cenu spojenú s ich dosiahnutím. (Táto informácia – zoznam destinácií, celková cena každého z nich a ďalší skok na odoslanie údajov, aby ste sa tam dostali – tvoria smerovaciu tabuľku alebo tabuľku vzdialeností . ) Každý uzol pravidelne posiela každému susednému uzlu svoje vlastné aktuálne hodnotenie celkových nákladov, aby sa dostal do všetkých destinácií, o ktorých vie. Susedné uzly skúmajú tieto informácie a porovnávajú ich s tým, čo už vedia; čokoľvek, čo predstavuje zlepšenie toho, čo už majú, vložia do vlastnej tabuľky. Postupom času všetky uzly v sieti objavia najlepší ďalší skok a celkové náklady pre všetky destinácie.

Keď sieťový uzol spadne, hociktoré uzly, ktoré ho použili ako ďalší skok, zahodia záznam a prenesú aktualizované informácie o smerovaní do všetkých susedných uzlov, ktoré následne proces zopakujú. Nakoniec všetky uzly v sieti dostanú aktualizácie a objavia nové cesty ku všetkým cieľom, ktoré nezahŕňajú klesajúci uzol.

Link-state algoritmus

Pri aplikácii algoritmov stavu spojenia je grafová mapa siete základným údajom používaným pre každý uzol. Na vytvorenie svojej mapy každý uzol zaplaví celú sieť informáciami o ostatných uzloch, ku ktorým sa môže pripojiť. Každý uzol potom nezávisle zostaví tieto informácie do mapy. Pomocou tejto mapy každý smerovač nezávisle určí najlepšiu cestu od seba ku každému inému uzlu pomocou štandardného algoritmu najkratších ciest, ako je Dijkstrov algoritmus . Výsledkom je stromový graf s koreňom v aktuálnom uzle, takže cesta cez strom od koreňa k akémukoľvek inému uzlu je najlacnejšia cesta k tomuto uzlu. Tento strom potom slúži na zostavenie smerovacej tabuľky, ktorá špecifikuje najlepší ďalší skok, ktorý sa má dostať z aktuálneho uzla do akéhokoľvek iného uzla.

Optimalizovaný algoritmus Link-state smerovania

Link-state algoritmus smerovania optimalizovaný pre mobilné siete ad hoc je optimalizovaný protokol OLSR (Link State Routing Protocol). OLSR je proaktívny; používa správy Hello a Topology Control (TC) na zisťovanie a šírenie informácií o stave spojenia prostredníctvom mobilnej ad hoc siete. Pomocou správ Hello každý uzol objaví 2-hop susedné informácie a zvolí sadu viacbodových prepínačov (MPR). MPR odlišujú OLSR od iných link-state protokolov.

Protokol path-vector

Distance-vector a link-state sú protokoly smerovania v rámci domény. Používajú sa vo vnútri autonómneho systému (vo vnútri siete patriacej jednej spoločnosti), ale nie medzi autonómnymi systémami. Obidva tieto smerovacie protokoly sa stávajú neovládateľné vo veľkých sieťach a nemožno ich použiť pri smerovaní medzi doménami . Distance-vector podlieha nestabilite, ak je v doméne viac ako niekoľko skokov. Link-state smerovanie vyžaduje značné zdroje na výpočet smerovacích tabuliek. To tiež vytvára hustú premávku v dôsledku záplav.

Path-vector smerovanie sa používa na smerovanie medzi doménami. Je to podobné ako distance vector smerovanie. Path-vector predpokladá, že jeden uzol (môže ich byť veľa) v každom autonómnom systéme koná v mene celého autonómneho systému. Tento uzol sa nazýva uzol hovorcu. Uzol hovorcu vytvorí smerovaciu tabuľku a inzeruje ju susedným hovorcovským uzlom v susedných autonómnych systémoch. Myšlienka je rovnaká ako pri distance vector s výnimkou toho, že iba uzly hovorcov v každom autonómnom systéme môžu navzájom komunikovať. Uzol hovorcu propaguje cestu, nie metriku, uzlov vo svojom autonómnom systéme alebo iných autonómnych systémoch.

Algoritmus path-vector je podobný algoritmu distance vector v tom zmysle, že každý hraničný smerovač propaguje destinácie, ktoré môže dosiahnuť, svojmu susednému smerovaču. Namiesto zverejňovaných sietí z hľadiska cieľa a vzdialenosti k tomuto cieľu sú však siete odosielané iným routrom ako cieľové adresy a popisy ciest na dosiahnutie týchto cieľov. Cesta, vyjadrená z hľadiska doteraz prejdených domén (alebo konfederácií), sa nesie v špeciálnom atribúte cesty, ktorý zaznamenáva postupnosť smerovacích domén, cez ktoré prešli informácie o dosiahnuteľnosti. Trasa je definovaná ako párovanie medzi cieľom a atribútmi cesty k tomuto cieľu, teda sa nazýva path-vector smerovanie; Smerovače dostanú vektor, ktorý obsahuje cesty k skupin cieľov.

Výber cesty

Výber cesty zahŕňa použitie metriky smerovania na viacero trás na výber (alebo predpovedanie) najlepšej trasy. Väčšina smerovacích algoritmov používa naraz iba jednu sieťovú cestu. Viaccestné smerovanie a špecificky rovnako nákladné viaccestné smerovacie techniky umožňujú použitie viacerých alternatívnych ciest.

V počítačových sieťach sa metrika počíta pomocou smerovacieho algoritmu a môže pokrývať informácie, ako je šírka pásma, oneskorenie siete, počet skokov, náklady na cestu, zaťaženie, maximálna prenosová jednotka, spoľahlivosť a náklady na komunikáciu. Smerovacia tabuľka ukladá len tie najlepšie možné trasy, zatiaľ čo databázy link-state alebo topologické databázy môžu uchovávať aj všetky ostatné informácie.

V prípade prekrývajúcich sa alebo rovnakých trás algoritmy pri rozhodovaní o tom, ktoré trasy sa majú nainštalovať do smerovacej tabuľky, zvažujú nasledujúce prvky podľa priority:

1. Dĺžka predpony : Vždy sa uprednostňuje zodpovedajúci záznam v tabuľke smerovania s dlhšou maskou podsiete, pretože presnejšie špecifikuje cieľ.
2. Metrika : Pri porovnávaní trás získaných prostredníctvom rovnakého smerovacieho protokolu sa uprednostňuje nižšia metrika. Metriky nemožno porovnávať medzi cestami získanými z rôznych smerovacích protokolov.
3. Administratívna vzdialenosť : Pri porovnávaní záznamov smerovacej tabuľky z rôznych zdrojov, ako sú rôzne smerovacie protokoly a statická konfigurácia, nižšia administratívna vzdialenosť označuje spoľahlivejší zdroj, a teda preferovanú cestu.

Pretože metrika smerovania je špecifická pre daný smerovací protokol, smerovače s viacerými protokolmi musia používať nejakú externú heuristiku na výber medzi cestami získanými z rôznych smerovacích protokolov. Smerovače Cisco napríklad pripisujú každej trase hodnotu známu ako administratívna vzdialenosť.

Miestny správca môže nastaviť trasy špecifické pre hostiteľa, ktoré poskytujú väčšiu kontrolu nad využívaním siete, umožňujú testovanie a celkovo lepšie zabezpečenie. To je užitočné pri ladení sieťových pripojení alebo smerovacích tabuliek.

V niektorých malých systémoch jediné centrálne zariadenie vopred rozhoduje o kompletnej ceste každého paketu. V niektorých iných malých systémoch, ktorékoľvek okrajové zariadenie vloží paket do siete, vopred rozhodne o kompletnej ceste tohto konkrétneho paketu. V oboch prípadoch potrebuje zariadenie na plánovanie trasy vedieť veľa informácií o tom, ktoré zariadenia sú pripojené k sieti a ako sú navzájom prepojené. Akonáhle má tieto informácie, môže použiť algoritmus, ako je vyhľadávací algoritmus A*, aby našiel najlepšiu cestu.

Vo vysokorýchlostných systémoch sa každú sekundu prenesie toľko paketov, že je nemožné, aby jediné zariadenie vypočítalo úplnú cestu pre každý jeden paket. Prvé vysokorýchlostné systémy sa s tým vysporiadali s prepínaním okruhov tak, že raz nastavili cestu pre prvý paket medzi nejakým zdrojom a nejakým cieľom; neskoršie pakety medzi tým istým zdrojom a tým istým cieľom pokračujú v rovnakej ceste bez prepočítavania až do roztrhnutia okruhu. Neskoršie vysokorýchlostné systémy zavádzajú pakety do siete bez toho, aby nejaké zariadenie kedy vypočítalo úplnú cestu pre pakety.

Vo veľkých systémoch je medzi zariadeniami toľko spojení a tieto spojenia sa menia tak často, že je nemožné, aby žiadne zariadenie vôbec vedelo, ako sú všetky zariadenia navzájom prepojené, nieto ešte vypočítať úplnú cestu cez nich. Takéto systémy vo všeobecnosti používajú smerovanie ďalšieho skoku .

Väčšina systémov používa deterministický dynamický smerovací algoritmus. Keď si zariadenie vyberie cestu k určitému konečnému cieľu, toto zariadenie si vždy zvolí rovnakú cestu k tomuto cieľu, až kým nedostane informácie, ktoré ho prinútia myslieť si, že iná cesta je lepšia.

Niekoľko smerovacích algoritmov nepoužíva deterministický algoritmus na nájdenie najlepšieho spojenia pre paket, ktorý sa má dostať z pôvodného zdroja do jeho konečného cieľa. Namiesto toho, aby sa predišlo preťaženiu horúcich miest v paketových systémoch, niekoľko algoritmov používa náhodný algoritmus – Valiantovu paradigmu – ktorý smeruje cestu k náhodne vybranému medzicieľu a odtiaľ do jeho skutočného konečného cieľa. V mnohých skorých telefónnych prepínačoch sa na výber začiatku cesty cez viacstupňovú prepínaciu štruktúru často používal randomizér.

V závislosti od aplikácie, pre ktorú sa vykonáva výber cesty, možno použiť rôzne metriky. Napríklad pri webových požiadavkách možno použiť cesty s minimálnou latenciou, aby sa minimalizoval čas načítania webovej stránky, alebo pri hromadných prenosoch údajov možno zvoliť najmenej využívanú cestu na vyváženie zaťaženia v sieti a zvýšenie priepustnosti. Obľúbeným cieľom výberu cesty je znížiť priemerné časy dokončenia prevádzkových tokov a celkovú spotrebu šírky pásma siete. Nedávno bola navrhnutá metrika výberu cesty, ktorá ako metrika výberu počíta celkový počet bajtov naplánovaných na okrajoch na cestu. Bola sprístupnená empirická analýza niekoľkých metrík výberu cesty vrátane tohto nového návrhu.

Viacerí agenti

V niektorých sieťach je smerovanie komplikované skutočnosťou, že žiadna entita nie je zodpovedná za výber ciest; namiesto toho je do výberu ciest alebo dokonca častí jednej cesty zapojených viacero entít. Komplikácie alebo neefektívnosť môžu nastať, ak si tieto subjekty zvolia cesty na optimalizáciu vlastných cieľov, ktoré môžu byť v rozpore s cieľmi ostatných účastníkov.

Klasickým príkladom je premávka v cestnom systéme, v ktorom si každý vodič vyberie cestu, ktorá minimalizuje čas jeho cesty. Pri takomto smerovaní môžu byť rovnovážne trasy pre všetkých vodičov dlhšie, než je optimálne. Najmä Braessov paradox ukazuje, že pridanie novej cesty môže všetkým vodičom predĺžiť cestovanie.

V modeli s jedným agentom, ktorý sa používa napríklad na smerovanie automaticky riadených vozidiel (AGV) na termináli, sa robia rezervácie pre každé vozidlo, aby sa zabránilo súčasnému používaniu rovnakej časti infraštruktúry. Tento prístup sa tiež označuje ako kontextové smerovanie.

Internet je rozdelený na autonómne systémy (AS), ako sú poskytovatelia internetových služieb (ISP), z ktorých každý riadi trasy zahŕňajúce jeho sieť. Smerovanie prebieha na viacerých úrovniach. Najprv sa cesty na úrovni AS vyberú prostredníctvom protokolu BGP, ktorý vytvorí sekvenciu AS, cez ktorú prechádzajú pakety. Každý AS môže mať viacero ciest, ktoré ponúkajú susedné AS, z ktorých si môže vybrať. Tieto rozhodnutia o smerovaní často korelujú s obchodnými vzťahmi s týmito susednými AS, ktoré nemusia súvisieť s kvalitou cesty alebo latenciou. Po druhé, keď už bola vybratá cesta na úrovni AS, často je na výber viacero zodpovedajúcich ciest na úrovni smerovača. Čiastočne je to spôsobené tým, že dvaja poskytovatelia internetových služieb môžu byť prepojení prostredníctvom viacerých pripojení. Pri výbere cesty na úrovni jedného smerovača je bežnou praxou, že každý ISP používa smerovanie hot-potato : posielanie prevádzky po ceste, ktorá minimalizuje vzdialenosť cez vlastnú sieť poskytovateľa internetových služieb – aj keď táto cesta predlžuje celkovú vzdialenosť k cieľu.

Uvažujme napríklad o dvoch ISP, A a B . Každý z nich má zastúpenie v New Yorku a je spojený rýchlym spojením s latenciou 5 – a každý má zastúpenie v Londýne prepojený 5 odkaz ms. Predpokladajme, že obaja ISP majú transatlantické spojenia, ktoré spájajú ich dve siete, ale spojenie A má latenciu 100 ms a B má latenciu 120 pani. Pri smerovaní správy zo zdroja v londýnskej sieti A do cieľa v newyorskej sieti B sa A môže rozhodnúť okamžite poslať správu B do Londýna. To šetrí A prácu pri odosielaní cez drahé transatlantické spojenie, ale spôsobuje, že správa má latenciu 125 ms, keď by druhá trasa bola 20 ms rýchlejšie.

Meracia štúdia internetových trás z roku 2003 zistila, že medzi pármi susedných ISP má viac ako 30 % ciest zvýšenú latenciu v dôsledku smerovania hot-potato, pričom 5 % ciest je oneskorených aspoň o 12 pani. Inflácia spôsobená výberom cesty na úrovni AS, hoci je značná, bola pripisovaná predovšetkým tomu, že BGP nemá mechanizmus na priamu optimalizáciu latencie, a nie egoistickým politikám smerovania. Bolo tiež navrhnuté, že ak by bol zavedený vhodný mechanizmus, poskytovatelia internetových služieb by boli ochotní spolupracovať na znížení latencie, a nepoužívať smerovanie hot-potato. Takýto mechanizmus neskôr publikovali tí istí autori, najskôr pre prípad dvoch ISP a potom pre globálny prípad.

Analytika trasy

Keďže internet a IP siete sa stali kritickými obchodnými nástrojmi, vzrástol záujem o techniky a metódy na monitorovanie smerovania sietí. Nesprávne smerovanie alebo problémy so smerovaním spôsobujú nežiaduce zníženie výkonu, prerušovanie alebo prestoje. Monitorovanie smerovania v sieti sa dosahuje pomocou nástrojov a techník na analýzu smerovania .

Centralizované smerovanie

V sieťach, kde je k dispozícii logicky centralizovaná kontrola nad stavom posielania, napríklad pomocou softvérovo definovanej siete, možno použiť smerovacie techniky, ktorých cieľom je optimalizovať globálne a celosieťové metriky výkonu. Toto využili veľké internetové spoločnosti, ktoré prevádzkujú mnoho dátových centier na rôznych geografických miestach pripojených pomocou súkromných optických prepojení, medzi ktoré patrí napríklad globálna WAN od Microsoftu, Facebook Express Backbone a B4 od Google.

Globálne metriky výkonu, ktoré je potrebné optimalizovať, zahŕňajú maximalizáciu využitia siete, minimalizáciu časov dokončenia toku prevádzky, maximalizáciu prevádzky doručenej pred konkrétnymi termínmi a skrátenie časov dokončenia tokov. Práca na neskoršej súkromnej sieti WAN pojednáva o modelovaní smerovania ako o probléme optimalizácie grafu tým, že sa celý rad zaradí do koncových bodov. Autori tiež navrhujú heuristiku na efektívne vyriešenie problému pri obetovaní zanedbateľného výkonu.