Směrování: Porovnání verzí

Z Wiki UnArt Slavičín
Skočit na navigaciSkočit na vyhledávání
(Nová stránka: Pojmem '''směrování''' ({{cizojazyčně|en|routing}}, routování) je označováno hledání cest v počítačových sítích. Jeho úkolem je dopravit da...)
 
 
(Není zobrazeno 18 mezilehlých verzí od stejného uživatele.)
Řádek 1: Řádek 1:
Pojmem '''směrování''' ({{cizojazyčně|en|routing}}, routování) je označováno hledání cest v [[Počítačová síť|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.
Pojmem '''směrování''' (routing, routování) je označováno hledání cest v [http://cs.wikipedia.org/wiki/Po%C4%8D%C3%ADta%C4%8Dov%C3%A1_s%C3%AD%C5%A5 počítačových sítích]. Jeho úkolem je dopravit datový [http://cs.wikipedia.org/wiki/Paket paket] určenému adresátovi, pokud možno co nejefektivnější cestou. Síťová [http://cs.wikipedia.org/wiki/Infrastruktura 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ě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|referenčního modelu OSI]]. Jelikož hegemonem [[Síťová vrstva|síťové vrstvy]] je [[Internet Protocol|protokol IP]], popíšeme zde směrování z jeho pohledu.
Směrování je základním úkolem síťové (čili třetí) vrstvy [http://cs.wikipedia.org/wiki/Referen%C4%8Dn%C3%AD_model_ISO/OSI Referenční model ISO/OSI]. Jelikož hegemonem [http://cs.wikipedia.org/wiki/S%C3%AD%C5%A5ov%C3%A1_vrstva síťové vrstvy] je [http://cs.wikipedia.org/wiki/Internet_Protocolprotokol IP], popíšeme zde směrování z jeho pohledu.


== Základní směrování, směrovací tabulka ==
== Základní směrování, směrovací tabulka ==
Z názvu by se zdálo, že směrování provádějí [[Router|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 názvu by se zdálo, že směrování provádějí [http://cs.wikipedia.org/wiki/Router 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:
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:
Řádek 25: Řádek 25:
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.
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.
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 [http://cs.wikipedia.org/wiki/DHCP DHCP] a není třeba na nich nic měnit.


=== Dynamické směrování ===
=== Dynamické směrování ===
Řádek 33: Řádek 33:
;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í.
;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šíří.
;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 [http://cs.wikipedia.org/wiki/OSPF 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]].
;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: [http://cs.wikipedia.org/wiki/RIP RIP], [http://cs.wikipedia.org/wiki/OSPF OSPF], [http://cs.wikipedia.org/wiki/BGP 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]].
;Hierarchické: Řeší problém rozlehlých sítí a neuměrné velikosti směrovacích informací tím, že [http://cs.wikipedia.org/wiki/Autonomn%C3%AD_syst%C3%A9m 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 [http://cs.wikipedia.org/wiki/OSPF OSPF].


=== Směrovací protokoly ===
=== Směrovací protokoly ===
Řádek 78: Řádek 78:
;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).
;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 ring]]u. 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ý.
;Source routing: Způsob používaný na linkové vrstvě např. v [http://cs.wikipedia.org/wiki/token_ring Token ring]u. 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 [[switch]]i na [[linková vrstva|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é).
;Zpětné učení: Funguje podobně jako přehazování paketů na [http://cs.wikipedia.org/wiki/switch switch]]i na [http://cs.wikipedia.org/wiki/Linkov%C3%A1_vrstva 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 ==
== 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ém]]y (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ů.
Jelikož jsou rozměry Internetu obrovské, je směrování v něm realizováno hierarchicky. Celý Internet je rozdělen na tzv. '''[http://cs.wikipedia.org/wiki/Autonomn%C3%AD_syst%C3%A9m autonomní systém] (Autonomous System, AS)'''. Oficiální definice zní, že [http://cs.wikipedia.org/wiki/Autonomn%C3%AD_syst%C3%A9m 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]].
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 [http://cs.wikipedia.org/wiki/RIP RIP] a [http://cs.wikipedia.org/wiki/OSPF 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]].
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 [http://cs.wikipedia.org/wiki/BGP BGP].
 
[[Kategorie:Internet]]
 
[[af:Roetering]]
[[ar:التسيير (علم الشبكات)]]
[[bg:Маршрутизация]]
[[de:Routing]]
[[el:Δρομολόγηση]]
[[en:Routing]]
[[es:Encaminamiento]]
[[eu:Bideratze-algoritmo]]
[[fa:مسیریابی (رایانه)]]
[[fi:Reititys]]
[[fr:Routage]]
[[ga:Ródú]]
[[he:ניתוב]]
[[id:Routing]]
[[it:Instradamento]]
[[ja:ルーティング]]
[[mk:Рутирање]]
[[pdc:Routing]]
[[pl:Trasowanie (informatyka)]]
[[pt:Encaminhamento]]
[[ro:Rutare]]
[[ru:Маршрутизация]]
[[sv:Routing]]
[[tr:Routing]]
[[uk:Маршрутизація]]
[[vi:Định tuyến]]
[[wuu:路由]]
[[zh:路由]]

Aktuální verze z 6. 1. 2009, 10:13

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 switch]i 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ém (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.