Open Shortest Path First

Open Shortest Path First (OSPF) je hierarchický interní směrovací protokol, fungující na bázi link-state, tzn. každý směrovač zná strukturu celé sítě (v případě OSPF přesněji celé oblasti). OSPF je nejpoužívanějším směrovacím protokolem pro směrování uvnitř autonomních systémů. Část sítě, v níž působí OSPF, se nazývá OSPF doména.

OSPF je tzv. beztřídní (classless) směrovací protokol, pracuje v sítích s různě dlouhými maskami podsítě (Variable-Length Subnet Mask, VLSM). Nepodporuje automatickou sumarizaci (sumarizaci na hranicích třídních sítí, tuto sumarizaci je v případě potřeby nutno konfigurovat manuálním zásahem). V případě IPv4 se OSPF zprávy vkládají přímo do IP paketu, přičemž hodnota v poli "Protocol" IP záhlaví je 89^[1]. U směrovačů firmy Cisco je administrativní vzdálenost protokolu OSPF implicitně 110.

Princip funkce

Činnost OSPF je rozdělena do tří částí – správa sousedských relací, šíření směrovacích informací a určování nejkratších (optimálních) cest.

Říká se, že ve zkonvergovaném stavu mají všechny routery patřící do jedné oblasti o této oblasti totožné informace. Zastřešujícím pojmem pro tyto údaje je link-state databáze (LSDB).

Správa sousedských relací

Jedna sousedská relace vždy existuje mezi dvěma směrovači. Sousedství není důležité ani tak pro sdílení informací o síti, jako spíše pro jejich nashromáždění. Ve zkonvergované plně funkční síti existují dva typy sousedství: dvojcestné (2-way) a úplné (full). První jmenovaný slouží jenom ke směrování, s druhým je navíc spojena výměna směrovacích informací.

Vznik sousedství probíhá tak, že dva jednu L2 topologii sdílející směrovače přijmou takzvané hello pakety; ty každý směrovač na každé rozhraní určené ke směrování (nikoli tzv. pasivní rozhraní) pravidelně zasílá. Hello paket je relativně velmi krátký, čili ani jeho časté zasílání nemá významný vliv na propustnost sítě, a je adresován právě všem těm zařízením, která jsou uzly dané L2 topologie (není směrován); jeho cílovou adresou je multicast 224.0.0.5 (01:00:5E:00:00:05). Implicitní interval zasílání hello paketů (tzv. hello interval) je 10 s.

K zániku sousedství dochází, jakmile od známého souseda není hello paket přijat po dobu tzv. dead timeru. Výchozí hodnota tohoto časovače je 40 s.

Alternativně lze sousedy definovat staticky. V takovém uspořádání se nadále zasílají hello pakety, nicméně tyto jsou unicastové. Obvykle se k této konfiguraci nepřistupuje z důvodu úspory režijního síťového provozu, nýbrž k efektivnější práci nad L2 topologiemi, které nepodporují broadcasting ani multicasting (tzv. non-broadcast multiaccess sítě, NBMA), např. Frame Relay. Na routerech firmy Cisco je v takovém uspořádání implicitní hello interval 30 s, dead interval 120 s.

Pro zformování sousedské relace je zapotřebí, aby oběma participujícím routerům byl shodně nakonfigurován hello interval, dead interval, číslo podsítě (IP adresa rozhraní po aplikaci masky podsítě binárním součinem), maska podsítě a ID oblasti.

Šíření směrovacích informací

K informování ostatních směrovačů o změnách v topologii dochází vždy, když k nějaké takové změně dojde. Změnou topologie se rozumí události vzniku nebo zániku sousedské relace. Směrovače v oblasti změny se dozvídají detailní informace, routery v jiných oblastech pouze případnou změnu metriky nebo směru (tj. IP adresa routeru následujícího v cestě užitečného IP paketu), nebo změnu ve výčtu dosažitelných sítí.

V L2 topologiích, v nichž může být více uzlů (v kontextu OSPF směrovačů) (tzv. multiaccess networks), typicky Ethernetu, OSPF používá koncept DR/BDR (Designated Router, Backup Designated Router). Jde o adresaci problému zbytečného opakovaného vytížení L2 topologie a směrovačů samotných (směrovače, jež nejsou DR ani BDR, se přijatou zprávou přestanou zabývat v rané fázi jejího zpracování). DR a BDR na rozdíl od takto nekvalifikovaných sousedů slyší na multicastové adrese 224.0.0.6 (01:00:5E:00:00:06). Pro výběr DR a BDR se používá primárně nakonfigurovaná priorita routeru, sekundárně ID routeru (RID), mající tvar IP adresy, jež je buď stanoveno správcem sítě, nebo automaticky vybráno z adres rozhraní směrovače. Směrovač, který není DR ani BDR, se v terminologii OSPF označuje jako DROther. Rozdělení rolí v tomto konceptu je pro každou L2 topologii individuální, tzn. vlastnost DR, popř. BDR, se neváže k routeru, ale k jeho rozhraní (jeden router v jedné L2 topologii může být DR, ve druhé BDR a ve třetí DROther).

Jednotlivé části LSDB mají své identifikátory, autory a časovače. Za autora je považován směrovač, jenž části dal vzniknout, a na něj se ostatní směrovače obracejí, když potřebují znát aktuální podobu příslušného fragmentu databáze (tj. v okamžiku, kdy se dozví, že se tento fragment změnil). Nedochází-li ke změnám v topologii, jež by se odrazily ve změně konkrétního fragmentu, informací, že tento fragment je stále platný, jeho autor zaplavuje celou OSPF doménu každých 30 min (zasílá jeho identifikátor); jedná se opatření pro eliminaci vlivu potenciální nesprávné implementace OSPF výrobcem zařízení nebo případné chyby ve standardu OSPF. Autor fragmentu je vyjádřen ID routeru.

Určování nejkratších cest

Pro stanovení nejkratších cest (cest s nejnižší metrikou), což je finální produkt každého dynamického směrovacího protokolu, v protokolu OSPF slouží Dijkstrův algoritmus, zvaný též Shortest Path First. Tento dal, ve spolupráci s faktem, že OSPF je otevřený standard, definovaný RFC, protokolu OSPF jeho název.

Výpočet se provádí znovu po každé změně v topologii a je jednou ze stinných stránek OSPF jako síťového řešení, neboť vzhledem k nárokům jiných intraautonomních dynamických směrovacích protokolů, především těch z rodiny distance-vector, je velmi náročný. Právě za účelem omezení požadavků na hardware se OSPF domény dělí do oblastí – jednotlivá změna v topologii poté k vytěžujícím výpočtům donutí jen v předmětné topologii účinkující směrovače.

Cesta, jejíž cíl je dosažitelný, aniž by paket musel projít jinou OSPF oblastí nebo částí autonomního systému pod správou jiného protokolu, se nazývá intraoblastní cesta (intra-area route). Cestě, která není intraoblastní cestou a jejíž cíl je dosažitelný bez toho, aby datagram musel projít částí autonomního systému pod správou jiného protokolu, se říká interoblastní (interarea route). Cesta, která není intraoblastní ani interoblastní, je externí (external route).

Oblasti

Existence koncepce oblastí v OSPF je důvodem, proč je tento protokol vydáván za hierarchický. Jak už bylo vysvětleno výše, oblasti slouží k zefektivnění fungování celé topologie. Oblasti jsou úskalím OSPF – obecně se má za to, že návrh oblastí je nejošemetnější částí konfigurace. Z důvodu výkonnosti je však rozdělení rozsáhlých OSPF domén na oblasti prakticky nevyhnutelné.

Hranice oblastí tvoří směrovače (nikoli linky, resp. L2 topologie). Z tohoto důvodu je ve víceoblastní OSPF doméně nutné, aby nejméně jeden směrovač byl členem alespoň dvou oblastí. Směrovač, který se účastní výhradně jedné oblasti, se označuje jako vnitřní směrovač (internal router). Naproti tomu směrovač tvořící rozhraní mezi oblastmi je znám jako hraniční směrovač (Area Border Router, ABR); jelikož takový router je z titulu své role povinen udržovat více LSDB, v principu musí být lépe hardwarově vybaven.

Oblasti jsou číslovány celými čísly od 0, a právě oblast 0 má zvláštní význam. Říká se jí páteřní oblast (backbone area) a v návrhu OSPF domény slouží jako referenční. I když v praxi není vyloučen opak, řečí standardu je použití oblasti 0 povinné. Pro router, který je členem výlučně oblasti 0, se používá termín páteřní směrovač (backbone router).

Případný směrovač představující spojení mezi OSPF doménou a částí autonomního systému, jíž vládne jiný dynamický směrovací protokol, popř. statické směrování, je nazýván jako hraniční směrovač autonomního systému (Autonomous System Border Router, ASBR) (zde se autonomním systémem nerozumí autonomní systém Internetu, nýbrž OSPF doména; pro tu se rovněž používá termín autonomní systém). Na hraničních směrovačích (ABR i ASBR) lze definovat pravidla pro manuální sumarizaci (více cílových sítí se vyjádří jedním záznamem).

Metrika

Jak je to u dynamických směrovacích protokolů obvyklé, metrika cesty je ovlivněna cenou všech L2 topologií na trase. Jako ukazatel kvality těchto článků trasy (nejčastěji linky, tedy přímého spojení dvou směrovačů) v OSPF slouží výhradně nominální přenosová rychlost (bandwidth), resp. její převrácená hodnota (metrika je obecně tím lepší, čím je nižší, a kvalita části trasy je přenosové rychlosti úměrná přímo). I když celá trasa je tak propustná, jak propustná je její nejméně propustná část, metrika cesty v OSPF není určena cenou formálně nejpomalejšího úseku (tzv. úzkého hrdla), nýbrž součtem cen jednotlivých úseků.

Cena úseku se počítá z rychlosti v Mb·s⁻¹, a aby číselné operace s metrikou mohly být realizovány celočíselnými datovými typy, převrácená hodnota rychlosti v Mb·s⁻¹ se (ještě před výpočtem podílu) násobí tzv. referenční nominální přenosovou rychlostí (reference bandwidth), jež byla prvotně stanovena na 100 Mb·s⁻¹, ale kvůli technologickému pokroku se používá vyšší hodnota; pro správnou funkci směrování tato konstanta musí být na všech směrovačích v OSPF doméně nastavena na touž hodnotu. Výsledek se zaokrouhlí na celé číslo dolů, a vyjde-li by 0, nahradí se 1. Na směrovačích firmy Cisco je cenu L2 topologie možné nastavit explicitně.

Ukázky cen nejznámějších typů L2 topologií při výchozí ref. bandwidth a ref. bandwidth 10 Gb·s⁻¹
Linka nebo technologie	Nomin. rychlost [Mb·s⁻¹]	Ref. bandwidth 100 Mb·s⁻¹	Ref. bandwidth 10 Gb·s⁻¹
DS0	64 kb·s⁻¹	1 562	156 250
DS1 (T1)	1 544 kb·s⁻¹	64	6 476
DS3 (T3)	44 736 kb·s⁻¹	2	223
E1, J1 (Y1)	2 048 kb·s⁻¹	48	4 882
E3	34 064 kb·s⁻¹	2	293
Ethernet	10 Mb·s⁻¹	10	1 000
FastEthernet	100 Mb·s⁻¹	1	100
GigabitEthernet	1 Gb·s⁻¹	1	10
10GbE	10 Gb·s⁻¹	1	1
Token ring 4 Mb·s⁻¹	4 Mb·s⁻¹	25	2 500
Token ring 16 Mb·s⁻¹	16 Mb·s⁻¹	6	625

Odkazy

Reference

↑ https://www.ietf.org/rfc/rfc1700.txt

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Open Shortest Path First na Wikimedia Commons
OSPF – dynamické routování (seriál)
RFC 2328 – OSPF Version 2

[1] ttps://www.ietf.org/rfc/rfc1700.txt

[1]