Protokol směrování vektoru vzdálenosti - Distance-vector routing protocol

A protokol směrování vektoru vzdálenosti v datové sítě určuje nejlepší trasu pro datové pakety na základě vzdálenosti. Protokoly pro směrování vektoru vzdálenosti měří vzdálenost podle počtu směrovače paket musí projít, jeden router se počítá jako jeden hop. Některé protokoly vzdálenosti-vektor také berou v úvahu latence sítě a další faktory, které ovlivňují provoz na dané trase. K určení nejlepší trasy v síti si směrovače, na kterých je implementován protokol vzdálenosti a vektoru, vyměňují informace navzájem, obvykle směrovací tabulky plus počty hopů pro cílové sítě a případně další dopravní informace. Protokoly pro směrování vektoru vzdálenosti také vyžadují, aby směrovač informoval své sousedy o topologie sítě se pravidelně mění.

Protokoly pro směrování vektoru vzdálenosti používají Algoritmus Bellman-Ford vypočítat nejlepší trasu. Další způsob výpočtu nejlepší trasy v síti je založen na nákladech na spojení a je implementován prostřednictvím směrovací protokoly stavu spojení.

Termín vzdálenost vektor odkazuje na skutečnost, že protokol manipuluje vektory (pole ) vzdáleností k dalším uzlům v síti. Algoritmus vektoru vzdálenosti byl původní ARPANET směrovací algoritmus a byl implementován v širším měřítku v místní sítě s Směrovací informační protokol (RIP).

Metodologie

Směrovače, které používají protokol vzdálenost-vektor, určují vzdálenost mezi sebou a cílem. Nejlepší cesta pro internetový protokol balíčky které nesou data přes a datová síť se měří jako počet směrovače (hop), paket musí projít, aby se dostal do své cílové sítě. Některé protokoly vektoru vzdálenosti navíc zohledňují další dopravní informace, například latence sítě. Aby byla zajištěna nejlepší cesta, směrovače si pravidelně vyměňují informace se sousedními směrovači, obvykle jejich směrovací tabulka, počet hopů pro cílovou síť a případně další informace týkající se provozu. Směrovače, které implementují protokol vzdálenosti a vektoru, se spoléhají čistě na informace poskytované jinými směrovači a nehodnotí topologie sítě.[1]

Protokoly vektoru vzdálenosti aktualizují směrovací tabulky směrovačů a určují cestu, na kterou bude paket odesílán Další skok což je výstupní rozhraní routeru a IP adresa rozhraní přijímajícího routeru. Vzdálenost je měřítkem nákladů na dosažení určitého uzlu. Nejlevnější trasa mezi libovolnými dvěma uzly je trasa s minimální vzdáleností.

Aktualizace se provádějí pravidelně v protokolu vektoru vzdálenosti, kde se celá nebo část směrovací tabulky směrovače odesílá všem jeho sousedům, kteří jsou nakonfigurováni pro použití stejného směrovacího protokolu vzdálenost-vektor. Jakmile má směrovač tyto informace, je schopen upravit svou vlastní směrovací tabulku tak, aby odrážela změny, a poté o změnách informovat své sousedy. Tento proces byl popsán jako „směrování podle pověsti“, protože směrovače spoléhají na informace, které dostávají od jiných směrovačů, a nemohou určit, zda jsou tyto informace skutečně platné a pravdivé. Existuje řada funkcí, které mohou pomoci s nestabilitou a nepřesnými informacemi o směrování.

Vývoj směrování vzdálenost-vektor

Nejstarší směrovací protokol a nejstarší protokol vektoru vzdálenosti je verze 1 protokolu Směrovací informační protokol (RIPv1). RIPv1 byl formálně standardizován v roce 1988.[2] Stanovuje nejkratší cestu napříč sítí čistě na základě chmele, což je počet směrovačů, které je třeba předat, aby se dosáhlo cílové sítě. RIP je protokol vnitřní brány, takže jej lze použít v místní sítě (LAN) na vnitřních nebo hraničních směrovačích. Směrovače s implementací RIPv1 si do roku vyměňují své směrovací tabulky se sousedními směrovači vysílání paket RIPv1 každých 30 sekund do všech připojených sítí. RIPv1 není vhodný pro velké sítě, protože omezuje počet směrování na 15. Tento limit směrování byl zaveden, aby se zabránilo směrování smyček, ale také znamená, že sítě, které jsou připojeny přes více než 15 směrovačů, jsou nedosažitelné.[3]

Protokol vektoru vzdálenosti navržený pro použití v rozsáhlé sítě (WAN) je Protokol hraniční brány (BGP). BGP je protokol vnější brány a proto implementováno na hraničních a externích směrovačích na internetu Internet. Vyměňuje informace mezi směrovači prostřednictvím a protokol kontroly přenosu Relace (TCP). Směrovače s implementací BGP určují nejkratší cestu v síti na základě řady jiných faktorů než chmele. Správce BGP může také nakonfigurovat tak, aby byly preferovány nebo vyloučeny určité trasy. BGP používá poskytovatelé internetových služeb (ISP) a telekomunikační společnosti.[4]

Mezi protokoly vektoru vzdálenosti, které byly popsány jako hybrid, protože používá metody směrování spojené s směrovací protokoly stavu spojení, je vlastnický Vylepšený vnitřní směrovací protokol brány (EIGRP). Byl vyvinut společností Cisco v 80. letech a byl navržen tak, aby nabízel lepší konvergenci a způsoboval menší síťový provoz mezi směrovači než směrovací protokol stavu spojení Nejprve otevřete nejkratší cestu (OSPF).[5]

Dalším příkladem směrovacího protokolu vzdálenost-vektor je Babel.

Problém počítání do nekonečna

The Algoritmus Bellman-Ford nezabrání směrovací smyčky z dění a trpí problém počítání do nekonečna. Jádro problému počítání do nekonečna spočívá v tom, že pokud A řekne B, že má někde cestu, neexistuje způsob, jak by B vědělo, zda má cesta B jako součást. Chcete-li jasně vidět problém, představte si podsíť připojenou jako A – B – C – D – E – F a nechte metriku mezi směrovači „počet skoků“. Nyní předpokládejme, že A je offline. V procesu aktualizace vektorů si B všimne, že trasa do A, která byla vzdálenost 1, je dole - B neobdrží aktualizaci vektoru od A. Problém je v tom, že B také dostane aktualizaci z C a C stále není vědom toho, že A je dole - takže říká B, že A jsou jen dva skoky z C (C do B do A). Protože B neví, že cesta z C do A prochází sama sebou (B), aktualizuje svoji tabulku novou hodnotou „B na A = 2 + 1“. Později B přepošle aktualizaci na C a vzhledem k tomu, že A je dosažitelné přes B (z pohledu C), C se rozhodne aktualizovat svoji tabulku na „C na A = 3 + 1“. To se pomalu šíří sítí, dokud nedosáhne nekonečna (v takovém případě se algoritmus sám opraví kvůli relaxační vlastnosti Bellman-Ford).

Řešení a řešení

RIP používá dělený horizont s technikou reverzního jedu ke snížení šance na vytvoření smyček a využívá maximální počet chmele k řešení problému „počítat do nekonečna“. Tato opatření zabraňují vytváření směrovacích smyček v některých, ale ne ve všech případech.[6] Přidání a držet čas (odmítnutí aktualizací trasy na několik minut po stažení trasy) zabrání tvorbě smyčky prakticky ve všech případech, ale způsobí výrazné prodloužení doby konvergence.

V poslední době byla vyvinuta řada vektorových protokolů vzdálenosti bez smyčky - pozoruhodné příklady jsou EIGRP, DSDV a Babel. Tito se ve všech případech vyhýbají vytváření smyček, ale trpí zvýšenou složitostí a jejich nasazení bylo zpomaleno úspěchem směrovací protokoly stavu spojení jako OSPF.

Příklad

V této síti máme 4 směrovače A, B, C a D:

Networkabcd.svg

Označíme aktuální čas (nebo iteraci) v algoritmu pomocí T a začneme (v čase 0 nebo T = 0) vytvořením matic vzdálenosti pro každý router k jeho bezprostředním sousedům. Když vytváříme směrovací tabulky níže, je nejkratší cesta zvýrazněna zeleně a nová nejkratší cesta je zvýrazněna žlutě. Šedé sloupce označují uzly, které nejsou sousedy aktuálního uzlu, a proto se v jeho tabulce nepovažují za platný směr. Červená označuje neplatné položky v tabulce, protože odkazují na vzdálenosti od uzlu k sobě nebo přes sebe.

T = 0
od A.přes Apřes Bpřes Cpřes D
do A
do B.3
do C.23
do D.
od B.přes Apřes Bpřes Cpřes D
do A3
do B.
do C.2
do D.
od C.přes Apřes Bpřes Cpřes D
do A23
do B.2
do C.
do D.5
od D.přes Apřes Bpřes Cpřes D
do A
do B.
do C.5
do D.
V tomto okamžiku mají všechny směrovače (A, B, C, D) pro své DV nové „nejkratší cesty“ (seznam vzdáleností, které od nich vedou k jinému směrovači přes souseda). Každý vysílá tento nový DV všem svým sousedům: A do B a C, B do C a A, C do A, B a D a D do C. Jakmile každý z těchto sousedů obdrží tyto informace, nyní přepočítají nejkratší cesta.

Například: A přijme DV z C, které řekne A, že existuje cesta přes C do D, se vzdáleností (nebo cenou) 5. Jelikož aktuální „nejkratší cesta“ k C je 23, pak A ví, že má cesta k D, která stojí 23 + 5 = 28. Protože neexistují žádné další kratší cesty, o kterých A ví, dá to jako svůj aktuální odhad nejkratší cesty ze sebe (A) do D, přes C.

T = 1
od A.přes Apřes Bpřes Cpřes D
do A
do B.325
do C.523
do D.28
od B.přes Apřes Bpřes Cpřes D
do A325
do B.
do C.262
do D.7
od C.přes Apřes Bpřes Cpřes D
do A235
do B.262
do C.
do D.5
od D.přes Apřes Bpřes Cpřes D
do A28
do B.7
do C.5
do D.
Všechny směrovače opět získaly v poslední iteraci (při T = 1) nové „nejkratší cesty“, takže všechny vysílají své DV ke svým sousedům; To vyzve každého souseda, aby znovu vypočítal své nejkratší vzdálenosti.

Například: A přijme DV z B, které řekne A, že existuje cesta přes B do D, se vzdáleností (nebo cenou) 7. Jelikož aktuální „nejkratší cesta“ k B je 3, pak A ví, že má cesta k D, která stojí 7 + 3 = 10. Tato cesta k D délky 10 (přes B) je kratší než stávající „nejkratší cesta“ k D délky 28 (přes C), takže se stává novou „nejkratší cestou“ k D.

T = 2
od A.přes Apřes Bpřes Cpřes D
do A
do B.325
do C.523
do D.1028
od B.přes Apřes Bpřes Cpřes D
do A37
do B.
do C.82
do D.317
od C.přes Apřes Bpřes Cpřes D
do A23533
do B.26212
do C.
do D.5195
od D.přes Apřes Bpřes Cpřes D
do A10
do B.7
do C.5
do D.
Tentokrát mají pro své DV nové nejkratší cesty pouze směrovače A a D. Vysílají tedy své nové DV svým sousedům: A vysílá do B a C a D vysílá do C. To způsobí, že každý ze sousedů přijímajících nové DV přepočítá své nejkratší cesty. Protože však informace z DV neposkytují žádné kratší cesty, než které již mají ve svých směrovacích tabulkách, nejsou ve směrovacích tabulkách žádné změny.
T = 3
od A.přes Apřes Bpřes Cpřes D
do A
do B.325
do C.523
do D.1028
od B.přes Apřes Bpřes Cpřes D
do A37
do B.
do C.82
do D.137
od C.přes Apřes Bpřes Cpřes D
do A23515
do B.26212
do C.
do D.3395
od D.přes Apřes Bpřes Cpřes D
do A10
do B.7
do C.5
do D.
Žádný ze směrovačů nemá žádné nové nejkratší cesty k vysílání. Proto žádný ze směrovačů dostávat jakékoli nové informace, které by mohly změnit jejich směrovací tabulky. Algoritmus se zastaví.

Reference

  1. ^ Tamara Dean (2009). Průvodce sítí + Network +. Cengage Learning. str.274. ISBN  9781423902454.
  2. ^ Hedrick, C. L. „Routing Information Protocol“. tools.ietf.org. RFC  1058. Citováno 2019-04-16.
  3. ^ Tamara Dean (2009). Průvodce sítí + Network +. Cengage Learning. str.274. ISBN  9781423902454.
  4. ^ Tamara Dean (2009). Průvodce sítí + Network +. Cengage Learning. str.274 –275. ISBN  9781423902454.
  5. ^ Tamara Dean (2009). Průvodce sítí + Network +. Cengage Learning. str.275. ISBN  9781423902454.
  6. ^ RFC  1058, Oddíl 2.2.2

Další čtení