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). RFC 3626 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:
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ľ. 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. 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.