Směrování

Pojmem směrování (routing, routování) je označováno hledání cest v počítačových sítích. Jeho úkolem je dopravit datový paket určenému adresátovi, pokud možno co nejefektivnější cestou. Síťová infrastruktura mezi odesílatelem a adresátem paketu může být velmi složitá. Směrování se proto zpravidla nezabývá celou cestou paketu, ale řeší vždy jen jeden krok – komu data předat jako dalšímu. Ten pak rozhoduje, co s paketem udělat dál.

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.

Směrování je základním úkolem síťové (čili třetí) vrstvy Referenční model ISO/OSI. Jelikož hegemonem síťové vrstvy je IP, popíšeme zde směrování z jeho pohledu.

Základní směrování, směrovací tabulka

Z názvu by se zdálo, že směrování provádějí směrovače]. Ve skutečnosti zdaleka nejsou samy. Směruje každé zařízení zapojené do IP sítě. I koncové počítače, byť v jejich případě bývá směrování triviální.

Základní datovou strukturou pro směrování je směrovací tabulka (routing table). Představuje vlastně onu sadu ukazatelů, podle kterých se rozhoduje, co udělat s kterým paketem. Směrovací tabulka je složena ze záznamů obsahujících:

• cílovou adresu, které se dotyčný záznam týká. Může se jednat o adresu individuálního počítače, častěji však je cíl definován prefixem, tedy začátkem adresy. Prefix mívá podobu 147.230.0.0/16. Hodnota před lomítkem je adresa cíle, hodnota za lomítkem pak určuje počet významných bitů adresy. Uvedenému prefixu tedy vyhovuje každá adresa, která má v počátečních 16 bitech (čili prvních dvou bajtech) hodnotu 147.230.
• akci určující, co provést s datagramy, jejichž adresa vyhovuje prefixu. Akce mohou být dvou typů: doručit přímo adresátovi (pokud je dotyčný stroj s adresátem přímo spojen) nebo předat některému ze sousedů (jestliže je adresát vzdálen).

Směrovací rozhodnutí pak probíhá samostatně pro každý procházející datagram. Vezme se jeho cílová adresa a porovná se směrovací tabulkou následovně:

1. Z tabulky se vyberou všechny vyhovující záznamy (jejichž prefix vyhovuje cílové adrese datagramu).
2. Z vybraných záznamů se použije ten s nejdelším prefixem. Toto pravidlo vyjadřuje přirozený princip, že konkrétnější záznamy (jejichž prefix je delší, tedy přesnější) mají přednost před obecnějšími.

Směrovací algoritmy a protokoly

Zajímavou otázkou je, jak vznikne a jak je udržována směrovací tabulka. Tento proces mají obecně na starosti směrovací algoritmy. Když jsou pak pro určitý algoritmus definována přesná pravidla komunikace a formáty zpráv nesoucích směrovací informace, vznikne směrovací protokol (routing protocol). Směrovací algoritmy můžeme rozdělit do dvou základních skupin: na statické a dynamické. Často se také mluví o statickém a dynamickém směrování, které je důsledkem činnosti příslušných protokolů.

Statické směrování

Při statickém (též neadaptivním) směrování se směrovací tabulka nijak nemění. Je dána konfigurací počítače a případné změny je třeba v ní provést ručně. Tato varianta vypadá jako nepříliš atraktivní, ve skutečnosti ale drtivá většina zařízení v Internetu směruje staticky.

Patří sem například skoro všechny uživatelské počítače, které jsou zpravidla v natolik jednoduché síťové situaci, že cokoli složitějšího nemá smysl. Většinou se nacházejí v koncové podsíti, z níž vede jediná cesta ven přes odchozí směrovač. Jejich směrovací tabulka obsahuje dva záznamy: adresy ze stejné podsítě doručovat přímo, všechno ostatní předávat na odchozí směrovač. Tyto informace se nastaví manuálně či automaticky prostřednictvím DHCP a není třeba na nich nic měnit.

Dynamické směrování

Dynamické (adaptivní) směrování průběžně reaguje na změny v síťové topologii a přizpůsobuje jim směrovací tabulky. Podle způsobu, jakým si jednotlivá zařízení vyměňují informace o stavu sítě, lze dynamické algoritmy rozdělit do základních skupin (které se vzájemně prolínají a kombinují):

Centralizované

Zde všechny směrovače posílají informace o stavu okolní sítě do jednoho směrovacího centra. To sestaví mapu sítě, spočítá z ní směrovací tabulky a rozešle 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á kompletní mapu sítě, takže dokáže určit globálně optimální tabulky. Hlavním problémem centralizovaného přístupu je, že špatně škáluje – na linkách vedoucích do centra se kumulují zprávy o stavu sítě a odesílané tabulky. 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. Centralizované směrování se proto nedočkalo širšího uplatnění.

Izolované

Jsou postaveny na ryzím individualismu. 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ší. Pokud je možné síť nadimenzovat (například pro přepravu dat pro řízení jaderného reaktoru) nebo je třeba informaci co nejrychleji rozšířit po celé síti, může být záplavový algoritmus vhodným řešením. Proto jej používá například níže zmiňovaný protokol OSPF pro šíření informací o změnách v 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. O něco chytřejší je OSPF, kde jsou aktualizace označeny, takže směrovač pozná, že tuto zprávu již obdržel a její opakované kopie nadále nešíří.

Distribuované

Představují standardní přístup ke směrování v síti Internet. V nich se informace o změnách v síti 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 neuměrné velikosti směrovacích informací tím, že autonomní systém rozdělují do několika relativně samostatných oblastí (area). 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.

Směrovací protokoly

• RIP (Routing Information Protocol)
  • velmi jednoduchý
  • v malých sítí (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í (provideři)
  • autonomní systémy

Získávání MAC k IP adrese

• ARP (Address Resolution Protocol)
  • známe cílovou IP adresu, zjišťujeme MAC - abychom mohli IP paket umístit do rámce (Ethernet-linková vrstva) a odeslat
  • vytváří ARP tabulku, MAC<->IP
  • 1 MAC může mít více IP adres
  • vytváří dynamický záznam (dynamické záznamy mají omezenou životnost - sekundy až desítky minut)

• Proxy ARP
  • router se při ARP odpovědích vydává za PC které leží za ním
  • vytvoření 1 logické podsítě z více fyzických sítí

• RARP (Reverzní ARP)
  • známe svoji MAC, ale neznáme svoji IP adresu
  • pro konfiguraci bezdiskových stanic -> dnes DHCP (Dynamic Host Configuration Protocol)
  • umí předat jen IP -> omezené možnosti
  • v síti je server se statickou ARP tabulkou
  • následník BootP, zpětně nekompatibilní
  • dynamické konfigurace stanic pro TCP/IP
  • server přiděluje:
    • a) staticky - dle MAC přidělí IP
    • b) dynamicky - stanice dostanou volnou IP z definovaného rozsahu
  • stanice si „pronájem“ obnovují podle požadovaného serveru -> evidence aktivních stanic
  • stanice požádá pomocí broadcastu (se svojí MAC), server odpoví

Další algoritmy

Náhodné směrování

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).

Source routing

Způsob používaný 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ý.

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é).

Směrování v Internetu

Jelikož jsou rozměry Internetu obrovské, je směrování v něm realizováno hierarchicky. Celý Internet je rozdělen na tzv. autonomní systémy (Autonomous System, AS). Oficiální definice zní, že 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 používá interní směrovací protokol (Interior Gateway Protocol, IGP). Hlavním cílem těchto protokolů je pružnost a rychlá reakce na změny. Typickými představiteli jsou protokoly RIP a OSPF.

Předávání směrovacích informací mezi autonomními systémy řeší externí směrovací protokol (Exterior Gateway Protocol, EGP). Zde je hlavní prioritou stabilita směrovacího protokolu, proto je v porovnání s IGP podstatně konzervativnější. Prakticky jediným představitelem této skupiny je protokol BGP.