Algoritmus vektoru vzdálenosti je iterativní, asynchronní a distribuovaný.
Distribuováno:Je distribuován tak, že každý uzel přijímá informace od jednoho nebo více svých přímo připojených sousedů, provádí výpočet a poté distribuuje výsledek zpět svým sousedům.Iterativní:Je iterativní v tom, že jeho proces pokračuje, dokud nejsou k dispozici žádné další informace pro výměnu mezi sousedy.Asynchronní:Nevyžaduje, aby všechny jeho uzly vzájemně fungovaly v zamykacím kroku.
• Algoritmus vektoru vzdálenosti je dynamický algoritmus.
• Používá se hlavně v ARPANET a RIP.
• Každý router udržuje tabulku vzdáleností známou jako Vektor .

Tři klíče k pochopení fungování algoritmu vzdáleného vektorového směrování:

Znalosti o celé síti:Každý router sdílí své znalosti prostřednictvím celé sítě. Směrovač posílá své shromážděné poznatky o síti svým sousedům.Směrování pouze k sousedům:Směrovač posílá své znalosti o síti pouze těm směrovačům, které mají přímé spojení. Router posílá cokoli o síti přes porty. Informace přijímá router a používá je k aktualizaci své vlastní směrovací tabulky.Sdílení informací v pravidelných intervalech:Do 30 sekund router odešle informaci sousedním routerům.

Algoritmus vektorového směrování vzdálenosti

Nechat d_X(y) jsou náklady na cestu s nejnižšími náklady z uzlu x do uzlu y. Nejnižší náklady souvisí s Bellman-Fordovou rovnicí,

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

Kde minv je rovnice pro všech x sousedů. Po cestě z x do v, pokud vezmeme v úvahu nejlevnější cestu z v do y, cena cesty bude c(x,v)+d_v(y). Nejmenší cena od x do y je minimum c(x,v)+d_v(y) převzal všechny sousedy.

S algoritmem Distance Vector Routing obsahuje uzel x následující informace o směrování:

• Pro každého souseda v je cena c(x,v) cena cesty od x k přímo připojenému sousedovi v.
• Vektor vzdálenosti x, tj. D_X= [D_X(y) : y v N ], obsahující jeho náklady na všechna místa určení, y, v N.
• Vektor vzdálenosti každého z jeho sousedů, tj. D_v= [D_v(y) : y v N ] pro každého souseda v z x.

Směrování vektoru vzdálenosti je asynchronní algoritmus, ve kterém uzel x posílá kopii svého vektoru vzdálenosti všem svým sousedům. Když uzel x přijme nový vektor vzdálenosti od jednoho ze svých sousedních vektorů, v, uloží vektor vzdálenosti v a použije Bellman-Fordovu rovnici k aktualizaci vlastního vektoru vzdálenosti. Rovnice je uvedena níže:

co je mac os

 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

Uzel x aktualizoval svou vlastní tabulku vektorů vzdáleností pomocí výše uvedené rovnice a posílá svou aktualizovanou tabulku všem svým sousedům, aby mohli aktualizovat své vlastní vektory vzdáleností.

Algoritmus

 At each node x, <p> <strong>Initialization</strong> </p> for all destinations y in N: D<sub>x</sub>(y) = c(x,y) // If y is not a neighbor then c(x,y) = &#x221E; for each neighbor w D<sub>w</sub>(y) = ? for all destination y in N. for each neighbor w send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to w <strong>loop</strong> <strong>wait</strong> (until I receive any distance vector from some neighbor w) for each y in N: D<sub>x</sub>(y) = minv{c(x,v)+D<sub>v</sub>(y)} If D<sub>x</sub>(y) is changed for any destination y Send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to all neighbors <strong>forever</strong> 

Poznámka: Ve vektorovém algoritmu vzdálenosti uzel x aktualizuje svou tabulku, když buď uvidí jakoukoli změnu nákladů v jednom přímo propojeném uzlu, nebo obdrží jakoukoli aktualizaci vektoru od nějakého souseda.

Pojďme to pochopit na příkladu:

Sdílení informací

• Na obrázku výše každý cloud představuje síť a číslo uvnitř cloudu představuje ID sítě.
• Všechny sítě LAN jsou propojeny směrovači a jsou znázorněny v rámečcích označených jako A, B, C, D, E, F.
• Algoritmus vektorového směrování vzdálenosti zjednodušuje proces směrování tím, že předpokládá, že cena každého spoje je jedna jednotka. Efektivitu přenosu lze tedy měřit počtem spojů k dosažení cíle.
• U vektorového směrování vzdálenosti je cena založena na počtu skoků.

Na výše uvedeném obrázku vidíme, že router posílá znalosti k bezprostředním sousedům. Sousedé přidají tyto znalosti ke svým vlastním znalostem a pošlou aktualizovanou tabulku svým vlastním sousedům. Tímto způsobem routery získávají své vlastní informace a nové informace o sousedech.

Směrovací tabulka

Probíhají dva procesy:

• Vytvoření tabulky
• Aktualizace tabulky

Vytvoření tabulky

Na začátku je pro každý směrovač vytvořena směrovací tabulka, která obsahuje alespoň tři typy informací, jako je ID sítě, cena a další skok.

NET ID:ID sítě definuje konečný cíl paketu.Náklady:Cena je počet skoků, které musí paket vykonat, aby se tam dostal.Další skok:Je to router, na který musí být paket doručen.

• Na obrázku výše jsou zobrazeny původní směrovací tabulky všech směrovačů. Ve směrovací tabulce představuje první sloupec ID sítě, druhý sloupec představuje cenu spojení a třetí sloupec je prázdný.
• Tyto směrovací tabulky se odesílají všem sousedům.

Například:

 A sends its routing table to B, F & E. B sends its routing table to A & C. C sends its routing table to B & D. D sends its routing table to E & C. E sends its routing table to A & D. F sends its routing table to A. 

Aktualizace tabulky

• Když A obdrží směrovací tabulku od B, použije její informace k aktualizaci tabulky.
• Směrovací tabulka B ukazuje, jak se pakety mohou přesunout do sítí 1 a 4.
• B je sousedem s routerem A, pakety z A do B mohou dosáhnout jedním skokem. Ke všem nákladům uvedeným v tabulce B se tedy přičte 1 a součet bude cenou za dosažení konkrétní sítě.

• Po úpravě pak A zkombinuje tuto tabulku s vlastní tabulkou a vytvoří kombinovanou tabulku.

• Kombinovaná tabulka může obsahovat některá duplicitní data. Na obrázku výše obsahuje kombinovaná tabulka routeru A duplicitní data, takže uchovává pouze ta data, která mají nejnižší cenu. Například A může odeslat data do sítě 1 dvěma způsoby. První, který nepoužívá žádný další router, takže stojí jeden skok. Druhý vyžaduje dva skoky (A do B, pak B do sítě 1). První možnost má nejnižší náklady, proto je ponechána a druhá možnost se upouští.

• Proces vytváření směrovací tabulky pokračuje pro všechny směrovače. Každý router přijímá informace od sousedů a aktualizuje směrovací tabulku.

Konečné směrovací tabulky všech směrovačů jsou uvedeny níže: