Propojování sítí a směrování

Důvody propojování / rozdělování sítí

Prvky pro propojování sítí

LAN - rozbočovač (hub), most/přepínač (bridge/switch)


WAN - směrovač (router)



Směrování
 - zasílání paketů nejkratší cestou sítí skok po skoku k cíli.
 - zahrnuje problém hledání této nejkratší cesty

Most (bridge)


Dnes aplikovány spíše přepínače
(transparentní most implementovaný hardwarově).


Samoučící (transparentní) most (self-learning bridge)

"Plug-and-Play" zařízení, pro stanice je jeho přítomnost v síti transparentní.

Zdrojové směrování (source routing)


Zdroj cestu získá tak, že před vysláním datového rámce cíli pošle "průzkumný rámec". Ten se šíří v síti všemi cestami a postupně do sebe sbírá seznam segmentů, kterými již prošel. Pro zamezení cirkulace se průzkumný rámec neodesílá se do segmentů sítě, jejichž identifikátor již v seznamu je.  Cíl, který průzkumný rámec přijal, seznam segmentů otočí a pošle zpět zdroji (po již známé cestě). Zdroj může získat zpět několik odpovědí s možnými alternativními cestami k cíli, ty si uloží do cache. Pro zaslání datového rámce k cílové stanici volí jednu ze získaných cest, seznam segmentů na cestě k cíli vloží do hlavičky odesílaného datového rámce.

Problém cirkulace rámců v prostředí se smyčkami
(samoučící mosty)



V případě třech paralelních mostů počet rámců dokonce exponenciálně narůstá.

Řešení: Spanning Tree

Princip funkce:
  1. volba kořenu stromu  (root bridge)
  2. vytvoření stromu nejkratších (nejlevnějších) cest z každého mostu ke kořeni

Směrovač (router)




Obsah směrovacích tabulek buď definován staticky nebo zjišťován dynamicky komunikací s okolními směrovači s využitím směrovacího protokolu. Poznámky:

Směrování



Hledání cesty sítí


Směrovací algoritmus

Poznámka:
Tvorba (úprava) směrovacích tabulek pomocí směrovacího protokolu a směrování podle těchto tabulek může probíhat současně (a obvykle tomu tak je).


Požadované vlastnosti směrovacího algoritmu (a směrovacího protokolu):

některé v protikladu, rozhoduje se, které upřednostnit

Směrovací tabulka

Formát záznamu:

< cílová adresa, výstupní rozhraní / adresa next_hop, metrika >

Implicitní cesta (default route)

Neadaptivní a adaptivní směrování

Neadaptivní směrování - statické
Adaptivní směrování - mění se podle:


Dělení přístupů ke směrování
(centralizované, distribuované, izolované)

Dělení podle informace, která je pro směrování k dispozici, resp. podle toho, zda je algoritmus výpočtu směrovacích tabulek distribuovaný nebo centralizovaný.

Centralizované směrování

Dnes prakticky nepoužívané.

Distribuované směrování

Používá se v mnoha variantách v Internetu

Izolované směrování

- založeno pouze a jedině na lokálně dostupné informaci (délky front na jednotlivých rozhraních, informace získaná z procházejících paketů - např. směr, kterým leží zdroj příchozího paketu)

Použití pouze pro speciální účely.

Směrování statické vs. dynamické

Statické směrování

Dynamické směrování

V praxi často používána kombinace statického a dynamického směrování, staticky nakonfigurované cesty mají obvykle přednost.

Hierarchické směrování


Dělení směrovacích algoritmů

Metody DVA - Distance Vector Algorithms

Reprezentant:

 protokol RIP (Routing Information Protocol)

Problém počítání do nekonečna a jeho řešení

Položka směrovací tabulky se vzdáleností do A: 
nahození linky A-B

A B-C-D-E
  - - - -
  1 - - -
  1 2 - -
  1 2 3 -
  1 2 3 4

výpadek linky do A

AxB-C-D-E
  1 2 3 4   C oznámí B, že přes něj je A za 2 přeskoky, B přičte vzdálenost C-B
  3 2 3 4   B oznámí C, že přes něj je A za 3 přeskoky; C měl v tabulce cestu
            do A přes B za 3 přeskoky, ale B inzeruje jinak, čili přepíše
            (s přičtením vzdálenosti C-B)
=> počítání do nekonečna
Podstata problému:
Směrovač, který se dozví od souseda o cestě k nějakému cíli, neví, že tato cesta vede přes tento směrovač samotný.

Řešení 1:
Split horizon - směrovač neposílá informace o síti do toho rozhraní, které sám používá pro dosažení této sítě.

Řešení 2:
Nekonečno číselně nahradíme průměrem sítě + 1, položky směrovací tabulky s metrikou nekonečno se nepoužijí. Např. RIP definuje nekonečno jako 16 skoků.
Funguje i pro směrovací smyčky přes více směrovačů.

Další možná vylepšení

Triggered update
- po výpadku/náběhu přilehlé linky směrovače nebo změně směrovací tabulky po příchodu update od souseda se nečeká na periodu časovače, ale nová směrovací tabulka se sousedům zašle ihned.

Poisson reverse
- jako split horizon, ale cesta do sítě se na rozhraní používaném pro dosažení této sítě nejen neposílá, ale posílá s metrikou nekonečno.

Hold down
- po ztrátě nejlepší cesty do sítě po dobu časového intervalu (holddown) nepřijímáme cesty do téže sítě od jiných směrovačů. Mohlo by totiž jít o falešné cesty využívající linek, jejichž výpadku (o němž my už víme) si nabízející směrovače dosud nepovšimly.


Metody LSA - Link State Algorithms

Záznamy topologické databáze

Reprezentant:
 - protokol OSPF (Open Shortest Path First)
 - dnes jeden z nejpoužívanějších směrovacích protokolů

Poznámky:

Algoritmy teorie grafů používané pro směrování

Směrovací protokoly v prostředí TCP/IP

Vnitřní (uvnitř autonomního systému):

Otevřené standardy:
Firemní (proprietární)
Vnější (mezi autonomními systémy):
BGP (Border Gateway Protocol) - tzv. path vector