Směrování a směrovací algoritmy

Směrování

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

Směrovací algoritmus

• část software 3. vrstvy OSI RM rozhodující, kterým rozhraním se má odeslat příchozí paket nebo kudy zřídit požadovaný virtuální okruh
• rozhoduje na základě staticky konfigurovaných informací nebo informací od směrovacího protokolu
• implementován s použitím směrovací tabulky
  

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):

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

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

Směrovací tabulka

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

• jako cílová adresa může být uvedena síť, podsíť nebo i jednotlivý uzel
• v prostředí IP jsou adresy sítí různé délky
• 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

• pro sítě připojené jediným rozhraním k hierarchicky vyšší síti
• např. firma k Internetu, pobočka firmy k centrále
• veškeré pakety, pro jejichž cílovou adresu neexistuje položka ve směrovací tabulce, se posílají na na default route
  
• next-hop pro default route se konfiguruje na přilehlé rozhraní směrovače do vyšší hierarchické úrovně (typicky směrovač ISP)
• smyslem snížení počtu záznamů ve směrovací tabulce
  

Neadaptivní a adaptivní směrování

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

• okamžité topologie sítě
• okamžitého zatížení jednotlivých částí sítě (zde ale nebezpečí rozkmitání směrování)

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í

• v síti existuje centrální prvek RCC (Routing Control Center), který shromažďuje informace o okolí 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ě)

Dnes prakticky nepoužívané.

Distribuované směrování

• každý směrovač zná "vzdálenost" (ceny linek) ke všem svým sousedům a stav těchto linek (funkčnost, přenosovou rychlost, okamžitou zátěž, ...)
  
• každý směrovač si vyměňuje své informace o směrování s jinými směrovači (prostřednictvím sousedů)
  
• ze získaných informací si směrovač vytvoří směrovací tabulku

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é sítě 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é síti
  
• Záplavové směrování (flooding) - paket se vyšle na všechny linky mimo té, ze které přišel. V paketu je počítadlo přeskoků, 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žie 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
• použitelné, pokud se topologie příliš často nemění (od výpadků a modifikací sítě)
  

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)
• smyslem omezení rozsahu směrovacích tabulek (agregováním záznamů a implicitní cestou)

Dělení směrovacích algoritmů

• použitá metrika
• úroveň informovanosti o topologii sitě
• logika šíření směrovací informace (výměna mezi sousedy, záplava všem, ...)
• technická realizace zasílání směrovacích informací (broadcast/multicast, perioda)
• doba konvergence - reakce na náběhy a výpadky linek
  
  

Metody DVA - Distance Vector Algorithms

• 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 (tzv. distanční vektory)
• periodické zasílání směrovací tabulky sousedům
  
• na začátku směrovací tabulka obsahuje pouze přímo připojené sítě
  
• z došlých směrovacích tabulek sousedů (vzdáleností sousedů od jednotlivých sítí) a výběrem nejlepší cesty si směrovač postupně upravuje svou směrovací tabulku
• pokud cesta nebyla delší dobu sousedem inzerována, ze směrovací tabulky se odstraní
  
• metrikou je počet "přeskoků" (hop count) na cestě mezi zdrojem a cílem
• nezohledňuje parametry jednotlivých linek (přenosovou rychlost, zpoždění, okamžitou zátěž, ...)
• pomalá konvergence při změnách topologie, zátěž od broadcastu směrovacích tabulek
• příliš "optimistické" - směrovač se rychle učí dobré cesty, ale špatně zapomíná při výpadcích (čekání na timeout). Žá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".
• jednoduchá implementace, historicky starší
  

 protokol RIP (Routing Information Protocol)

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

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

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

• směrování na základě znalosti "stavu" jednotlivých linek sítě (funkčnost, cena)
  
• směrovače (uzly grafu) znají topologii celé sítě (graf) a ceny jednotlivých linek (ohodnocení hran). Tyto informace udržují v topologické databázi.
  
• všechny směrovače mají stejnou topologickou databázi
• každý směrovač počítá strom nejkratších cest ke všem ostatním směrovačům (a k nim připojeným sítím) pomocí Dijkstrova algoritmu.  
  
• každý směrovač sleduje stav a funkčnost linek připojených k němu, při změně okamžitě šíří informaci (o aktuálním stavu svého okolí) všem ostatním směrovačům. Ty si ji vloží do topologické databáze
• okamžitá reakce na změnu stavu linky (výpadek,náběh) = > rychlá konvergence
• šíří se pouze změny (ale do celé sítě) - žádné periodické rozesílání směrovacích tabulek

Záznamy topologické databáze

• ID směrovače
• seznam přilehlých linek, u každé vždy ID sousedního směrovače a cena linky

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

• nově nastartovaný směrovač může získat topologii sítě od souseda na vyžádání (po zabezpečeném protokolu)
• hrany mohou být ohodnoceny obecně více metrikami (např. rychlost, spolehlivost, cena, ...) = > možnost konstrukce alternativních stromů nejkratších cest a směrování každého typu provozu jinou cestou (podle preferencí zdrojové stanice). Toto však prakticky téměř nepoužíváno.

Dynamické propagování implicitní cesty (default)

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ů. V modifikované variantě základ protokolu OSPF.
  
• 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. V distribuované variantě základ protokolu RIP.

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

• RIP (Routing Information Protocol) - distance vector
  
• OSPF (Open Shortest Path First) - link state

• IGRP, EIGRP - Cisco
• NLSP - Novell