Vektorové směrování vzdálenosti

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. července 2014; kontroly vyžadují 9 úprav .

Distance vector routing ( Distance Vector Routing, DVR ) - routing , jehož protokoly jsou založeny na algoritmu vzdálenostního vektoru [1] . Algoritmy vektoru vzdálenosti patří do třídy adaptivních (neboli dynamických) algoritmů směrování.

Tento algoritmus byl poprvé popsán Fordem a Fulkersonem v „Flows in Networks“. Jejich práce byla zase založena na Bellmanově rovnici z jeho knihy Dynamické programování.

Algoritmy směrování vektorů vzdálenosti se také nazývají Bellman-Fordovy algoritmy .

Algoritmus vektoru vzdálenosti

Algoritmus dostal své jméno díky tomu, že ani na konci algoritmu, ani v jeho průběhu nemá ani jeden vrchol topologickou informaci o žádné trase. Každá objevená cesta je reprezentována pouze cílovým uzlem, cenou cesty a dalším vrcholem na cestě k cílovému uzlu a reprezentace cesty neobsahuje žádné mezilehlé uzly ani hrany. Cena cesty je vzdálenost a cílový vrchol a další vrchol jsou vektor . [jeden]

Problém, který řeší algoritmus vektoru vzdálenosti, je problém hledání nejkratších cest mezi vrcholy grafu . Graf je matematická abstrakce, ve které jsou vrcholy spojeny hranami. Každá hrana má určité náklady na její použití. Cesta mezi dvěma vrcholy je sada mezilehlých hran a vrcholů spojujících dva původní vrcholy. Náklady na cestu jsou definovány jako součet nákladů hran, které ji tvoří. Nejkratší cesta mezi dvěma vrcholy je cesta s nejnižšími náklady.

Pravidla
  • Na začátku algoritmu zná každý vrchol pouze cesty k sousedním vrcholům.
  • Jak algoritmus běží, sousední vrcholy se vzájemně informují o vrcholech, které mají k dispozici. Každá deklarace se skládá z cílového uzlu a nákladů na nejkratší cestu známou informujícímu uzlu.
  • Zpočátku každý vrchol hlásí pouze sousední vrcholy s cenou nejkratších cest rovnající se ceně hran.
  • Po obdržení deklarace uzel vypočítá náklady na cestu k deklarovanému uzlu přes deklarující uzel jako součet nákladů na hranu vedoucí k deklaračnímu uzlu a nákladů na cestu obsaženou v deklaraci. Poté uzel zkontroluje, zda již ví o cestě k deklarovanému cílovému uzlu.
  • Pokud to neví nebo pokud jsou náklady na známou cestu vyšší než vypočítané náklady na novou cestu, uzel si pamatuje novou cestu k cílovému uzlu.
  • Pokud nová cesta nahradí existující cestu, ta se zahodí.
  • Pokud jsou náklady na existující cestu nižší nebo rovné ceně nové cesty, bude nová cesta vyřazena.
  • Po zapamatování nové cesty musí vrchol oznámit cílový vrchol a cenu nové cesty k sousedním vrcholům.
Provoz routeru

V algoritmech vektoru vzdálenosti každý směrovač periodicky vysílá po síti vektor , jehož součástí jsou vzdálenosti (měřené v jedné nebo jiné metrice ) od tohoto směrovače do všech sítí, které jsou mu známy. Pakety směrovacího protokolu se běžně označují jako reklamy na dálku, protože je používá směrovač, aby ostatním směrovačům oznámil, co ví o své konfiguraci sítě.

Poté, co router přijme od nějakého souseda vektor vzdáleností (vzdáleností) k sítím známým, zvětší složky vektoru o vzdálenost od sebe k tomuto sousedu. Vektor navíc doplňuje informacemi o dalších jemu známých sítích, o kterých se dozvěděl přímo (pokud jsou připojeny k jeho portům) nebo z podobných oznámení jiných routerů. Router odešle aktualizovanou hodnotu vektoru svým sousedům. Nakonec se každý router dozví prostřednictvím sousedních routerů informace o všech sítích dostupných ve složené síti ao vzdálenostech k nim. [2]

Poté vybere z několika alternativních tras do každé sítě tu cestu, která má nejmenší hodnotu metriky . Router, který odeslal informace o této trase, je ve směrovací tabulce označen jako další skok.

Výhody a nevýhody

Algoritmy vektorů vzdálenosti fungují dobře pouze v malých sítích. Ve velkých sítích pravidelně ucpávají komunikační linky silným provozem, kromě toho změny konfigurace nemohou být tímto typem algoritmu vždy správně zpracovány, protože routery nemají přesnou představu o topologii připojení v síti, ale pouze mají nepřímou informaci - vektor vzdálenosti.

Distance vector protocols

Protokol RIPv1

Protokol vzdálenostních vektorů RIPv1 (Routing Information Protocol) je prvním dynamickým směrovacím protokolem a je dnes velmi běžně používaný.

Tento protokol se používá jako interní směrovací protokol v malých sítích a je podporován zařízeními všech výrobců. [3]

Základní parametry
  • RIP - vzdálený vektorový protokol.
  • Administrativní vzdálenost - 120.
  • Metrikou je počet skoků.
  • Maximální počet chmelů je 15.
  • Metrika nedosažitelné trasy je 16.
  • Distribuce aktualizací směrovacích informací - vysílání každých 30 sekund.
  • Čekací čítač konvergence (Časovač přidržení) - 180 sec.
  • Maska podsítě – použije se výchozí maska, určená třídou sítě, neodesílá se v aktualizaci.

Protokol RIPv2

Protokol vzdálenosti RIPv2 je modifikací protokolu RIPv1 .

Tento protokol se používá jako interní směrovací protokol v malých sítích a je podporován zařízeními všech výrobců. [3]

Základní parametry
  • RIPv2 je vzdálený vektorový protokol.
  • Administrativní vzdálenost - 120.
  • Metrikou je počet skoků.
  • Maximální počet chmelů je 15.
  • Metrika nedosažitelné trasy je 16.
  • Distribuce aktualizací směrovacích informací - pomocí multicastové adresy 224.0.0.9 každých 30 sekund.
  • Čekací čítač konvergence (Časovač přidržení) - 180 sec.
  • Podpora spuštěných aktualizací. Maska podsítě – používá masku s proměnnou délkou odeslanou v aktualizaci.

Srovnání RIPv1 a RIPv2

Srovnání RIPv1 a RIPv2
Směrovací protokol RIPv1 RIPv2
Adresování Třída Beztřídní
Maska s variabilní délkou Ne Ano
Odeslání masky v aktualizacích Ne Ano
Typ adresy Přenos Multicast
Popis RFC 1058 RFC 1721, 1722, 2435
Podpora sumarizace tras Ne Ano
Podpora autentizace Ne Ano

Protokol IGRP

Stejně jako u RIP směrovač IGRP pravidelně distribuuje obsah své tabulky svým sousedům prostřednictvím vysílání. Na rozdíl od RIP však směrovač IGRP začíná již vytvořenou směrovací tabulkou pro podsítě, které jsou k němu připojeny. Tato tabulka je dále rozšířena o informace z nejbližších sousedních routerů. Zprávy o změně protokolu IGRP neobsahují informace o masce podsítě. Místo jednoduchého počtu zásahů RIP se používají různé typy metrických informací, konkrétně [4] :

Zpoždění Popisuje (v desítkách mikrosekund) čas k dosažení cíle, když není síť bez zátěže.
Šířka pásma Rovná se 10 000 000 děleno nejmenší šířkou pásma na dané trase (měřeno v kb/s). Například nejnižší šířka pásma 10 kb/s odpovídá metrice 1 000 000 kb/s.
Zatížení Měřeno jako podíl šířky pásma na dané trase, která se aktuálně používá. Kódováno čísly od 0 do 255 (255 odpovídá zatížení 100 %).
Spolehlivost Část datagramu, která dorazila bez poškození. Kódováno čísly od 0 do 255 (255 odpovídá 100% bez poškození datagramů).
Počet skoků Určuje počet zásahů do cílů.
Cesta MTU (cesta MTU) Největší hodnota maximální přenosové jednotky (MTU) pro datagramy, které lze odeslat přes jakýkoli odkaz ve veřejné cestě.

Protokol EIGRP

Distance Vector Routing Protocol EIGRP je vylepšení IGRP vyvinuté společností Cisco. EIGRP kombinuje principy protokolů pro směrování vektorů vzdálenosti pomocí vektoru vzdálenosti s přesnější metrikou k určení nejlepších cest do cílové sítě a principy protokolů stavu spojení, které využívají spouštěné aktualizace k šíření změn ve směrovacích informacích. Pro tuto kombinaci provozních principů se tento protokol někdy nazývá hybridní protokol.

Protokol EIGRP používá pro podporu směrování následující nástroje :

  • Neighbor table - obsahuje seznam sousedních routerů, který zajišťuje obousměrnou komunikaci mezi přímo připojenými routery.
  • Tabulka topologie – obsahuje položky tras pro všechny cílové sítě, o kterých router ví.
  • DUAL (difuzní aktualizační algoritmus) je algoritmus difuzní aktualizace používaný k výpočtu tras.
  • Směrovací tabulka - obsahuje nejlepší trasy v cílové síti, vybrané z topologické tabulky.
  • Následník – Nejlepší nalezená trasa (primární) pro dosažení cílové sítě. Zapisuje se do směrovací tabulky .
  • Možná úspěšná (Feasible následník) - záložní cesta. Záložní trasy jsou vybírány současně s nejlepší. Tyto cesty jsou uloženy v topologické tabulce. Může existovat více redundantních cest do cílové sítě.

Viz také

Literatura

  1. M.V. DIBROV.  Směrovače. - Krasnojarsk, 2008. - 389 s.
  2. Goldovský Ya.M. , Zhelenkov B.V., Tsyganova N.A. Směrování v počítačových sítích: Učebnice. - M.: RUT (MIIT), 2017. - 114 s.
  3. Zolotarev S.P.. "Algoritmy směrování vektorů vzdálenosti" Vologda Readings, no. 69, 2008, str. 43-48.
  4. Sidney Faith.  TCP/IP architektura, protokoly, implementace (včetně IP verze 6 a IP Security). - Laurie, 2000. - ISBN 5-85582-072-6 .

Poznámky

  1. ↑ 1 2 M.V. DIBROV. Směrovače. - Krasnojarsk, 2008. - 389 s.
  2. ↑ Zolotarev, S.P. Algoritmy směrování vzdálenostních vektorů  (ruština)  // Vologda Readings. - 2008. - č. 69 . - S. 43-48 . Archivováno z originálu 12. prosince 2020.
  3. ↑ 1 2 Goldovský Ya.M. , Zhelenkov B.V., Tsyganova N.A. Směrování v počítačových sítích. — M.: RUT (MIIT), 2017. — 114 s.
  4. ↑ Sidney Faith. TCP/IP architektura, protokoly, implementace (včetně IP verze 6 a IP Security). - Laurie, 2000. - ISBN 5-85582-072-6 .