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

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

• zvětšení rozsahu:
  - překonání fyzikálních omezení rozsahu jedné lokální sítě
  - propojení původně nezávislých sítí, i geograficky vzdálených
  
• oddělení provozu
  - bezpečnost (odposlouchávání, úmyslné rušení)
  - snížení zátěže sítě (kolize) i stanic (broadcasty)
  - lepší odolnost proti poruchám (izolace poruch)
  

Prvky pro propojování sítí

Most (bridge)

• na 2. vrstvě OSI RM, v lokální síti
• zpravidla stejný formát rámce na všech rozhraních (alternativou je tzv. překladový most (translating bridge))
• mosty transparentní (samoučící) / zdrojové směrování
• možnost konverze média, kódování, ...
• parametry: forwarding rate a filtering rate

Half bridge - dva mosty připojené vždy z jedné strany k LAN a vzájemně propojené sériovou linkou - obvykle pro propojení sítí na větší vzdálenost

Dnes aplikovány spíše přepínače (srov. s transparentním mostem).

Problém cirkulace rámců v prostředí se smyčkami

Neustálá konstrukce spanning tree (normalizováno v 802.1d), linky tvořící smyčky blokovány, při výpadku se aktivují. Pojmy: Root bridge, root port, blocking/forwarding stav portu, metriky linek

Ukázka problému v případě existence smyček

Směrovač (router)

• na 3. vrstvě OSI RM, vzájemné propojení i různých lokálních sítí
• směruje konkrétní síťový protokol(y)
• na každém rozhraní (interface) musí být nakonfigurovaná adresa (příp. více adres, příp. subnet maska, co podporuje příslušný protokol)
• určování výstupního rozhraní a adresy dalšího skoku na základě směrovací tabulky, přepočítávání checksum, snižování TTL, fragmentace, ...
• 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ích protokolů
• může současně fungovat jako jednoduchý firewall - filtrace
• pro neznámé protokoly často funguje jako most

Brána (gateway)

• na 4.-6. vrstvě OSI RM, propojování velmi rozdílných sítí, které využívají obecně zcela různé protokoly
• terminologická nejednoznačnost, v prostředí TCP/IP se gateway říkalo směrovači (někdy také IMP - Internet Message Processor)

Směrování

• ve spojově orientovaných sítích nebo u virtuálního spojení při vytváření spojení (nastavování spojovacího pole, budování přepínacích tabulek)
• v sítích s přepínáním paketů (obvykle obecně polygonálních) při přenosu každého jednotlivého paketu = > každý paket může jít jinou cestou = > bezpečnost proti výpadku, problémy duplikace, změny pořadí

Fáze tvorby směrovacích tabulek a směrování podle nich (mohou se prolínat)

Směrovací algoritmus

část software 3. vrstvy OSI rozhodující, kterým rozhraním se má příchozí paket odeslat (ať už jde o paket datový v sítích s přepínáním paketů nebo paket zřizující spojení ve spojově orientovaných sítích).

Požadované vlastnosti směrovacího algoritmu:

• jednoduchost
• robustnost
• stabilita
• férovost
• optimalita

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

Směrovací tabulka

< destination addr, výstupní rozhraní, next_hop_addr, metrika >

Jako cílová adresa může být uvedena síť, subsíť nebo i jednotlivý host, použije se cesta, která se shoduje s adresou cíle v paketu na co největší počet míst = > nutnost projít vždy celou tabulku = > časově náročný proces

Default route - pro sítě připojené jediným rozhraním k intersíti, veškeré pakety, pro něž neexistuje položka ve směrovacích tabulkách, se posílají zadaným rozhraním na určený následující router

Neadaptivní a adaptivní směrování

Adaptivní směrování - založeno na měření a odhadech okamžitého provozu a topologie sítě

Směrování centralizované vs. distribuované

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í

• v síti existuje centrální prvek RCC (Routing Control Center), který shromažďuje informace od všech směrovačů, kombinuje z nich topologii sítě, počítá směrovací tabulky pro všechny směrovače a předává jim je
• jednotlivé směrovače posílají periodicky do RCC stavové informace (seznam "živých" sousedů, délky front na jednotlivých interface, celková zpracovávaná zátěž, ...)
• problém s distribucí tabulek od RCC do jednotlivých směrovačů - distribuce postupná, směrování v době distribuce nekonzistentní (staré a nové verze tabulek současně)

V datových sítích používané velmi málo

Distribuované směrování

• každý směrovač zná "vzdálenost" ke všem sousedům (je-li metrikou počet přeskoků,je to 1)
• každý směrovač si vyměňuje své informace o směrování s jinými směrovači (prostřednictvím sousedů)

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)

• Horký brambor - paket se vkládá do nejkratší výstupní fronty (cílem je se jej co nejrychleji zbavit)
• Backward learning - do paketů se vkládá identifikace zdrojového směrovače a počítadlo, při průchodu každým směrovačem se počítadlo zvýší - směrovač z příchozího paketu zjistí, jak daleko je přes dané rozhraní ke zdrojovému směrovači
• Záplavové směrování (flooding) - paket se vyšle na všechny linky mimo té, ze které přišel, v paketu počítadlo přeskoků a likvidace paketu při dosažení limitu jako opatření proti zahlcení
  • vždy vybírá nejkratší cestu (resp. všechny nejkratší cesty paralelně)
  • použití pro spolehlivé a rychlé rozšíření informace v síti s neznámou a příp. proměnnou topologií - vojenské aplikace
  • používá se jako "normál" pro srovnání ostatních algoritmů

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

Statické směrování

• tabulky v jednotlivých směrovačích konfigurovány "ručně" - pracnější
• odpadá režije směrovacích protokolů (zabraná šířka pásma,čas na zpracování)
• bezpečnější (omezení možnosti generování falešných směrovacích informací, odposlouchání topologie sítě)
• při výpadku linky nutný ruční zásah (nebo více alternativních řádků směrovací tabulky pro jeden cíl = > možnost zálohování linek, vyvažování provozu mezi více linkami)
• použitelné, pokud se topologie a charakter zátěže přiliš nemění

Dynamické směrování

• automaticky reagují na poměry v síti (topologie, zátěž, ...)
• nutnost provozu směrovacích protokolů
• užitečné při častých změnách (příp. i obecně neznámé) topologie sítě (typicky v Internetu)

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í

rozdělení sítě do hierarchicky organizovaných celků, směrovače v jenotlivých celcích znají jen topologii svého celku a cestu do vyššího celku (nikoli jeho vnitřní strukturu)
= > omezení rozsahu směrovacích tabulek (agregováním záznamů)

Metodiky směrování

rozdělení podle použité metriky, způsobu šíření směrovací informace (broadcast, multicast, výměna mezi sousedy, designated routery pro LAN), reakce na náběhy a výpadky linek

Metody DVA - Distance Vector Algorithms

• metrikou je počet "přeskoků" (hops) na cestě mezi zdrojem a cílem
• nezohledňuje parametry jednotlivých linek
• směrovače neznají topologii sítě, pouze rozhraní, přes která se budou posílat pakety do jednotlivých sítí a vzdálenosti k těmto sítím (distanční vektory)
• obvykle periodické zasílání směrovací tabulky směrovače sousedům, ty došlé informace kombinují se svou lokální tabulkou za účelem nalezení nejkratších cest do jednotlivých sítí
• horší konvergence při změnách topologie
• z došlých směrovacích tabulek sousedů (vzdáleností sousedů od jednotlivých cílů) a vzdálenosti k jednotlivým sousedům a výběrem nejlepší cesty se počítá lokální směrovací tabulka

Problémy a jejich řešení: triggered update, poisson reverse, hold down,...

Reprezentant: protokol RIP (Routing Information Protocol)

Problém: "optimistické", rychle se učí dobré cesty, ale špatně zapomíná při výpadcích

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

Nekonečno číselně nahradíme průměrem sítě + 1, položky směrovací tabulky s metrikou nekonečno se nepoužijí.

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ý

Žádný směrovač nikdy nemá metriku horší, než o 1 větší než minimum z metrik sousedů => pomalé šíření špatných zpráv (nemožnost rychle rozšířit metriku s hodnotou "nekonečno")

Pokud směrovač detekuje výpadek linky, měl by si z ní nasimulovat "poslání" paketu se všemi položkami s metrikou nekonečno a zareagovat na něj.

Metody LSA - Link State Algorithms

• směrování na základě znalosti stavu jednotlivých linek sítě (suma stavů linek na cestě je metrikou)
• směrovače znají topologii celé sítě (graf) a ohodnocení jednotlivých linek (hran)-udržují v topologické databázi. Počítá se nejkratší cesta (Dijkstrův alg.)
• hrany mohou být ohodnoceny obecně více metrikami (např. rychlost, spolehlivost, cena, ...) = > možnost směrovat každý typ provozu jinou cestou
• každý směrovač sleduje stav a funkčnost linek připojených k němu, při změně okamžitě šíří informaci = > rychlá konvergence. Šíří se pouze změny (do celé sítě)
• v ustáleném stavu se nepoužívá periodické rozesílání směrovacích tabulek, směrovač může získat topologii sítě od jiného směrovače na vyžádání (po zabezpečeném protokolu)

reprezentant: protokol OSPF (Open Shortest Path First)

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

• Dijkstra - pro zvolený uzel hranově ohodnoceného grafu nalezne strom nejkratších cest do ostatních uzlů
• Floyd - vychází z matice cen grafu, počítá matici vzdáleností uzlů grafu a úplné směrovací tabulky pro jednotlivé uzly
• Ford-Fulkerson - určení nejkratších vzdáleností ze všech uzlů do jednoho společného uzlu

Příklad: směrovací protokol RIP