Technologie internetu (8.): Směrování v malém

V tomto dílu seriálu probereme dva významné reprezentanty vnitřních směrovacích protokolů. Říká se jim tak proto, že se používají pro výměnu informací mezi směrovači v rámci jednoho autonomního systému (AS). V ideálním případě by měl každý AS používat jediný vnitřní směrovací protokol.

V praxi to ale vypadá jinak, protože autonomní systémy mívají určitou vnitřní hierarchii: Typickým správcem AS je velký telekomunikační operátor, jehož nákladná páteř se směrovači zvučných jmen propojuje sítě řady „maloobchodních“ poskytovatelů připojení. Drobní ISP pak často provozují vlastní směrovací protokol, který lépe odpovídá jejich erudici a použitým směrovačům, jimiž nezřídka bývají obyčejná PC s Linuxem.

Moderní směrovače i směrovací programy pro PC (Quagga, BIRD, XORP a další) proto umožňují provozovat více směrovacích protokolů zároveň. Každý protokol si v takovém případě udržuje vlastní směrovací tabulku a na správci počítače pak je, aby vhodným způsobem zkonfiguroval filtry jak pro přenos informací mezi protokoly, tak i pro import do hlavní směrovací tabulky, podle níž se směrují datagramy. Jak vím z vlastní zkušenosti, tato část konfigurace směrovačů bývá velmi ošemetná a nezkušený správce může právě zde napáchat nejvíce škody. Proto je nutno s těmito takzvanými redistribucemi zacházet opatrně a vše dopředu pořádně vyzkoušet.

RIP

Routing Information Protocol (RIP) je mezi směrovacími protokoly skutečným veteránem. Mnozí by proto jeho zkratku raději interpretovali podle vzoru anglosaských náhrobků: Rest In Peace. RIP má ale i dnes své místo především v sítích s malým počtem směrovačů, kde vynikne jeho hlavní přednost – jednoduchá, či spíše nulová konfigurace. Pro IPv6 až donedávna zůstával v podstatě jediným použitelným vnitřním protokolem.

Přímé předchůdce RIPu najdeme ještě v době předinternetové. Jeho algoritmus se prakticky shoduje s tím, který byl používán v Arpanetu roku 1969, a podobné algoritmy byly v 70. letech navrženy i pro jiné sítě, které nepoužívaly IP. Nejdůležitější okamžik v historii RIPu nastal v srpnu 1983 v souvislosti s vydáním operačního systému 4.2BSD Unix. Ten totiž obsahoval směrovacího démona routed, který pak byl po dlouhá léta neformálním standardem pro směrování uvnitř autonomních systémů vznikajícího internetu.

Jak funguje RIP Činnost směrovače RIP verze 2 je založena na následujících principech: ● Směrovač poslouchá zprávy od svých sousedů a upravuje podle nich svou směrovací tabulku tak, aby každému cílovému prefixu mohl přiřadit následníka (next hop), přes něhož vede nejkratší známá cesta. ● Každých 30 vteřin odešle svou aktuální směrovací tabulku všem svým sousedům. ● Dostane-li od některého souseda žádost, pošle pouze jemu svou směrovací tabulku. Takové žádosti vysílají směrovače například po zapnutí, aby se rychleji inicializovaly. ● Zaznamená-li směrovač v síti změnu, odešle všem sousedům vyvolanou aktualizaci (triggered update). Do ní jsou zařazeny jen ty části směrovací tabulky, které tato změna ovlivní. ● Všechny směrovací informace mají omezenou platnost. Pokud se údaj o dostupnosti určité sítě neobnoví během šesti vysílacích period (tj. 180 sekund), směrovač jej musí označit za neplatný (přiřadí mu „nekonečnou“ metriku 16).

RIP verze 2 (viz RFC 1723) přinesl mimo jiné nezbytnou podporu pro beztřídní směrování (CIDR). Na druhé verzi RIPu je založena jeho varianta pro IPv6, označovaná také jako RIPng (next generation) a definovaná v RFC 2080.

RIP používá známý Bellmanův-Fordův algoritmus, který umožňuje nalézt nejkratší cestu mezi dvěma zadanými uzly v libovolném grafu. V našem případě jsou uzly směrovače a hrany spoje mezi nimi. Vzdálenost mezi uzly (metrika) může být dána buď jednoduše počtem „hopů“ anebo jako součet délek, které jsou hranám administrativně přiděleny.

Směrovač, který používá RIP, si udržuje vlastní tabulku, v níž pro každý známý síťový prefix zaznamenává délku nejkratší cesty k této síti a také next hop, tedy následníka, přes něhož tato nejkratší cesta vede. Zjistí-li časem z informací od sousedů, že existuje jiná, kratší cesta, zapíše její délku a následníka do tabulky místo starých údajů. Další podrobnosti o fungování RIPu jsou uvedeny v rámečku.

Hlavní nedostatek RIPu vyplývá z faktu, že se směrovací informace šíří mezi sousedícími směrovači v dávkách, mezi nimiž jsou poměrně značné časové prodlevy (obvykle 30 vteřin). Některé změny topologie se proto ke vzdáleným směrovačům šíří poměrně pomalu, což může vést ke vzniku směrovacích smyček. Druhým zásadním problémem je, že přípustné cesty v síti mohou mít metriku nejvýše 15. Metrika 16 a více je považována za „nekonečnou“, a příslušná cesta tudíž za nepoužitelnou. Toto omezení připomínající počítání Hotentotů (jedna-dva-moc) je kompromisem, vynuceným touhou po dosažení rozumné rychlosti konvergence. Z téhož důvodu také není možné podstatněji zkracovat periodu výměny informací mezi sousedy.

OSPF

Zřejmě nejpoužívanějším vnitřním směrovacím protokolem je OSPF (Open Shortest Path First). V porovnání s RIPem se jedná o podstatně důmyslnější protokol, který může efektivně fungovat i pro obrovské sítě. S tím jde ovšem ruku v ruce relativní složitost konfigurace. OSPF patří mezi protokoly založené na stavu linek (link-state protocols). To znamená, že všechny směrovače mají stále přesnou představu o topologii celé sítě. Pokud v ní dojde kdekoli ke změně stavu linky (funguje-nefunguje), všechny směrovače se to prakticky okamžitě dozvědí a upraví podle aktuálního stavu své datové struktury popisující topologii sítě.

Konkrétněji: každý směrovač si udržuje strom nejkratších cest, v němž je sám kořenem a ze kterého může získat aktuální nejkratší cestu do kteréhokoli místa sítě. Dostane-li směrovač oznámení o změně stavu nějaké linky, musí svůj strom nejkratších cest přepočítat.

Běžně používané implementace k tomu používají algoritmus kombinatorické optimalizace, jehož autorem je jeden z velikánů informatiky – Edsger Dijkstra. Tento algoritmus je velmi obecný a nemá taková omezení jako algoritmus RIPu. Speciálně nekonečno je pro něj opravdu nekonečné, takže lze pomocí administrativně nastavených délek hran vyjádřit poměrně podrobné představy o preferencích jednotlivých spojů a cest v síti.

Zaměření seriálu nám neumožňuje věnovat se všem detailům a finesám OSPF, zkusme však alespoň pomocí analogie vysvětlit základní rozdíl mezi RIPem a OSPF. Představme si silniční síť, která propojuje určitý počet obcí. Naším úkolem je udržovat aktuální stav ukazatelů směru na všech křižovatkách i s ohledem na všechna možná přechodná dopravní omezení. Metoda podobná RIPu by spočívala v tom, že na každé křižovatce bude skupina poslů, kteří zjistí, do jakých obcí vedou z křižovatky přímé cesty, a pak se každou hodinu vydají do všech směrů na sousední křižovatky, kde se na základě jejich informací upraví ukazatele a poslové z této křižovatky vyrazí, až přijde jejich čas, předat vědomosti dále. OSPF naproti tomu odpovídá daleko profesionálnějšímu postupu, který by mohl vypadat třeba tak, že se na každé křižovatce umístí mapa a změny aktuální dopravní situace se okamžitě hlásí na všechna místa (řekněme mobilním telefonem), která si podle toho upraví svou mapu.

OSPF umožňuje v případě potřeby zavést dvoustupňovou hierarchii, v níž se celá síť rozdělí na vhodný počet podsítí zvaných oblasti (areas). Jedna z nich je speciální: nazývá se páteřní oblast a veškerá vzájemná komunikace mezi ostatními oblastmi musí vést přes ni. Detailní informace o topologii každé z nepáteřních oblastí zůstávají uvnitř této oblasti a do páteře se šíří jen vhodně sumarizované informace. Toto uspořádání je zejména vhodné pro velké sítě s distribuovanou správou.

IPv4 internet dnes používá verzi 2 protokolu OSPF (viz RFC 2328). Pro IPv6 pak slouží verze 3, která je popsaná v RFC 2740.