Směrování

Směrování (anglicky routing, též routování) označuje v informatice určování cest datagramů v prostředí počítačových sítí. Směrování zajišťují nejen routery, ale i koncové stanice (při vysílání), a jeho úkolem je doručit datagram (resp. paket) adresátovi, pokud možno co nejefektivnější cestou. Směrování zajišťuje síťová vrstva modelu ISO/OSI a je využíváno v lokálních sítích LAN i na Internetu, kde jsou dnes směrovány zejména IP datagramy. Síťová infrastruktura mezi odesílatelem a adresátem paketu může být velmi složitá, a proto se směrování zpravidla nezabývá celou cestou paketu, ale řeší vždy jen jeden krok, tj. komu datagram předat jako dalšímu.

Směrovací proces lze zhruba přirovnat k cestě autem. Přijedete ke křižovatce, podíváte se na ukazatele a podle nich se rozhodnete, kam se dát. Řekněme, že jedete do Prahy, a Praha je značena vpravo. Zabočíte tedy doprava a neřešíte, jak budete postupovat na další křižovatce. Teprve když na ni dojedete, prohlédnete si zdejší sadu ukazatelů a provedete další rozhodnutí (např. pojedete rovně). A tak dále, dokud nedorazíte do cíle. Podobně každé směrující zařízení v sobě má sadu pravidel (ukazatelů směru), která říkají, kam se mají předávat pakety směřující k určeným cílům. Podle nich data předá některému ze sousedů a tam se rozhodovací proces bude opakovat podle zdejších pravidel. V každém uzlu sítě není možné z kapacitních důvodů uvádět pravidla pro dosažení všech cílů. Proto jsou pravidla při směrování zobecňována podobně, jako při cestě autem, kdy jsou na křižovatkách uvedeny vždy jen důležité cíle (buď v bezprostřední blízkosti nebo obecné dálkové cíle).

Směrovací tabulka (anglicky routing table) obsahuje informace, které jsou nutné při rozhodování o směrování. Je uložena, používána a může být i vytvářena v aktivních uzlech sítě (router, stanice apod.). Záznamy jsou ve směrovací tabulce rozděleny do řádků, přičemž každý obsahuje jednu směrovací informaci. Řádky jsou seřazeny od nejkonkrétnějších (nejdelší maska sítě) po nejobecnější (kratší maska sítě), přičemž posledním záznamem je generalizovaný odkaz (implicitní brána) na nejbližší router, kterým v případě sítí používajících TCP/IP „vede cesta do Internetu“ (implicitní brána, anglicky default gateway). Každý záznam (tj. řádek) ve směrovací tabulce obsahuje několik informací (ne nutně v uvedeném pořadí) - typicky bývají zaznamenány další údaje, které nejsou pro výklad nezbytně nutné, tabulka je pro IP sítě:

1. cíl – obsahuje číslo cílové podsítě, pro kterou je záznam v tabulce proveden ve formátu IP adresy (např. 10.0.0.0)
2. maska podsítě – maska ve spojení s číslem podsítě vymezuje rozsah IP adres, pro které je záznam platný (např. 255.255.255.0)
3. brána – IP adresa routeru, kterému má případně být IP datagram předán (není vyplněno v případě, že je podsíť přímo dosažitelná, tj. nachází se přímo za rozhraním, uvedeným v záznamu)
4. síťové rozhraní – skrze které síťové rozhraní je nutné IP datagram odeslat, pokud záznam odpovídá hledanému cíli

Pokud je po přijetí IP datagramu zjištěno, že není určen pro toto zařízení, měl by nutně být předán dále tak, že bude předán podle záznamů ve směrovací tabulce dalšímu cíli. V každém IP datagramu je uvedena IP adresa cíle, pro který je určen. Tato cílová IP adresa je porovnávána postupně se všemi záznamy ve směrovací tabulce. Tabulka je setříděna podle délky masky v jednotlivých záznamech od nejdelších (nejvíce jedniček zleva) po nejkratší (nejméně jedniček zleva), což vyjadřuje velikost cílových podsítí. Nejprve jsou tedy záznamy pro jednotlivé počítače nebo malé podsítě a teprve dále jsou záznamy pro postupně větší a větší podsítě. Postup porovnání s každým záznamem ve směrovací tabulce je následující:

1. je proveden logický součin cílové IP adresy a masky ze zkoumaného řádku tabulky
2. je-li výsledek roven cíli uvedenému ve zkoumaném záznamu, je nalezena shoda
3. není-li nalezena shoda, je zpracován další řádek tabulky
4. není-li již k dispozici další záznam v tabulce a shoda dosud nebyla nalezena, je ohlášena nedosažitelnost cílové sítě pro zkoumaný IP datagram

Podle vzniku záznamů ve směrovací tabulce hovoříme o statickém nebo dynamickém směrování.

Při statickém (též neadaptivním) směrování nejsou za běhu stanice záznamy ve směrovací tabulce nijak aktivně měněny. Může je do ní zapsat správce počítače (typicky podle údajů poskytnutých správcem příslušné počítačové sítě) nebo jsou do tabulky zapsány při startu počítače. Záznamy mohou být uchovány v konfiguračním souboru (v Microsoft Windows pak v registrech) nebo poskytovány například pomocí protokolu DHCP.

Statické směrování typicky používají koncové stanice nebo routery v malých počítačových sítích (LAN), protože záznamy není nutné v průběhu činnosti zařízení měnit a nebo proto, že jsou záznamy jednoduché.

Dynamické (adaptivní) směrování průběžně reaguje na změny v počítačové síti (přidávání nebo odebírání podsítí) a přizpůsobuje jim obsah směrovací tabulky. Podle způsobu, jakým si jednotlivá zařízení vyměňují informace o změnách v počítačové síti, lze dynamické směrování rozdělit do několika základních skupin (které se vzájemně prolínají a kombinují). Pro distribuci těchto informací mezi směrovači se používají různé směrovací protokoly (viz níže).

Centralizované

V centralizovaném směrování posílají všechny směrovače informace, které vědí o stavu okolní sítě do jednoho centra. Řídící centrum sestavuje mapu sítě, vypočítá směrovací tabulky a rozesílá je směrovačům. Z pohledu směrovače je tento přístup velmi jednoduchý (pošle hlášení a za chvíli dostane směrovací tabulku). Navíc centrum má k dispozici kompletní mapu sítě, takže dokáže globálně určit optimální tabulky. Hlavním problémem centralizovaného přístupu je špatná škálovatelnost, protože zatěžuje přenosové kapacity sítě režijním provozem tím více, čím větší je obsluhovaná síť. Velikost sítě, kterou lze takto směrovat, je proto omezená. Dílčí problém představuje i synchronizace tabulek – směrovače poblíž centra je dostávají dříve. Při příliš velké síti může dojít k nesouhlasu tabulek z důvodu časového prodlení při aktualizaci. Centralizované směrování se proto nedočkalo širšího uplatnění.

Distribuované

Distribuované směrování představuje standardní přístup ke směrování v síti Internet. Informace o změnách se předávají postupně mezi sousedními směrovači, až se rozšíří do celé sítě. Tento přístup je dostatečně pružný a robustní, aby zvládl i dost rozlehlé sítě. Skutečnost, že Internet stojí na distribuovaných algoritmech, je nejlepším vysvědčením životaschopnosti tohoto konceptu. Konkrétní přístupy a mechanismy se výrazně liší. Nejvýznamnějšími představiteli distribuovaných protokolů jsou: RIP, OSPF, BGP.

Hierarchické

Řeší problém rozlehlých sítí a neúměrné velikosti směrovacích informací tím, že autonomní systém rozdělují do několika relativně samostatných oblastí (autonomní systémy). Záplavové informace o změně v topologii sítě se šíří pouze v rámci oblasti. O výměnu souhrnných informací mezi oblastmi se starají hraniční směrovače (propojující jednotlivé oblasti mezi sebou). Jedna oblast tedy dostává o ostatních oblastech pouze souhrnné informace (s agregovanými prefixy). Tento způsob nabízí např. protokol OSPF.:

Dále vypsaná směrování nejsou široce používána, jsou uvedena pro ucelený přehled:

Izolované

Izolované směrování je založeno na individuálním přístupu. Nikdo nikomu neposílá žádné informace o stavu sítě, každý směrovač se rozhoduje zcela samostatně. Do této skupiny patří například záplavový algoritmus (též roztékání, flooding), kdy každý směrovač pošle paket do všech rozhraní kromě toho, z nějž dorazil. Tento algoritmus je velmi nehospodárný, na druhé straně ale zkouší všechny cesty, takže najde i tu nejlepší. Používá se v případech, kdy je možné síť naddimenzovat (například pro přepravu dat pro řízení jaderného reaktoru nebo ve vojenství) nebo je třeba informaci co nejrychleji rozšířit po celé síti. Největším problémem roztékání jsou cykly v síti, které způsobí, že paket se po čase vrátí znovu a znovu… Primitivním řešením tohoto problému je omezit životnost paketu. Záplavový algoritmus používá směrovací protokol OSPF pro šíření informací o změnách v síti.

Náhodné směrování

Náhodné směrování je zdánlivě nesmyslný způsob, avšak občas se používá v případě zahlcení směrovače, který nestíhá prohledávat routovací tabulku, a tak pakety, které by normálně zahodil, pošle náhodným směrem a má částečnou šanci se s paketem trefit do správné cesty (tudíž odesílatel nebude muset ztracený paket znovu po síti posílat, a tím fakticky zvyšovat zátěž sítě). V pozadí je myšlenka, že kromě náhodnosti paket narazí na router, který správnou cestu zná (nalezne ve své tabulce). Kromě šance na doručení jinak zahozeného paketu může takto zahlcený router přenést část své zátěže na okolní aktivní prvky.

Zdrojové směrování

Zdrojové směrování (anglicky source routing) je používán na linkové vrstvě např. v Token ringu. Odesílatel nejprve zašle do sítě záplavovou výzvu ke zjištění cesty k hledanému cíli. Pokud je příjemce dosažitelný, vrátí se mu odpověď v podobě výsledné trasy (seznamu routerů po cestě od odesílatele k příjemci). Výhodou tohoto způsobu je, že najde opravdu tu nejkratší cestu ze všech možných cest, avšak záplavový způsob je značně nešetrný k přenosovým kapacitám sítě.

Zpětné učení

Zpětné učení funguje podobně jako přehazování paketů na switchi na linkové vrstvě. Pokud router obdrží paket s příjemcem, o kterém neví, kde se nachází, pošle ho dál na všechna rozhraní (s výjimkou toho, odkud paket přišel). Avšak současně s každým procházejícím paketem si poznamenává, na jaké rozhraní přišel paket s daným odesílatelem. Tímto způsobem se učí topologii sítě (na kterém rozhraní jsou kteří hostitelé, tedy fakticky routovací tabulku).

Jelikož jsou rozměry Internetu obrovské, je v něm směrování realizováno hierarchicky. Celý Internet je rozdělen na autonomní systémy (anglicky Autonomous System, AS). Autonomní systém je část sítě s jednotnou směrovací politikou vůči zbytku Internetu. Typickým příkladem je síť jednoho poskytovatele Internetu a jeho připojených zákazníků. Uvnitř autonomního systému se typicky používá směrovací protokol IGP (anglicky Interior Gateway Protocol). Předávání směrovacích informací mezi autonomními systémy řeší směrovací protokol EGP (anglicky Exterior Gateway Protocol).

• RIP (Routing Information Protocol)
  • velmi jednoduchý
  • v malých sítích (max.15 skoků)
  • všechny routery broadcastují to, co znají (na počátku jen okolní sítě)
• OSPF (Open Shortest Path First)
  • ve velkých sítích (provideři)
  • autonomní systémy

• Směrovací tabulka

• Obrázky, zvuky či videa k tématu směrování na Wikimedia Commons