Távolságvektoros útválasztás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. július 14-én felülvizsgált verziótól ; az ellenőrzések 9 szerkesztést igényelnek .

Distance vector routing ( Distance Vector Routing, DVR ) - útválasztás , melynek protokolljai a távolságvektor algoritmuson alapulnak [1] . A távolságvektor-algoritmusok az adaptív (vagy dinamikus) útválasztási algoritmusok osztályába tartoznak.

Ezt az algoritmust először Ford és Fulkerson írta le a "Flows in Networks" című könyvében. Munkájuk Bellman Dinamikus programozás című könyvének egyenletén alapult .

A távolságvektor-útválasztó algoritmusokat Bellman–Ford algoritmusoknak is nevezik .

Távolságvektor algoritmus

Az algoritmus nevét arról kapta, hogy sem az algoritmus végén, sem alatta egyetlen csúcsnak sincs topológiai információja egyetlen útvonalról sem. Minden egyes felfedezett útvonalat csak a célcsomópont, az útvonal költsége és a célcsomóponthoz vezető útvonal következő csúcsa reprezentál, és az útvonalábrázolás nem tartalmaz közbenső csomópontokat vagy éleket. Az út költsége a távolság, a célcsúcs és a következő csúcs pedig egy vektor . [egy]

A távolságvektor-algoritmus által megoldott probléma a gráf csúcsai közötti legrövidebb utak megtalálása . A gráf egy matematikai absztrakció, amelyben a csúcsokat élek kötik össze. Minden élnek némi költsége van a használatáért. A két csúcs közötti út a két eredeti csúcsot összekötő közbenső élek és csúcsok halmaza. Egy útvonal költsége az azt alkotó élek költségeinek összege. A két csúcs közötti legrövidebb út a legalacsonyabb költséggel járó út.

Szabályok
  • Az algoritmus elején minden csúcs csak a szomszédos csúcsokhoz vezető útvonalat ismeri.
  • Az algoritmus futása során a szomszédos csúcsok tájékoztatják egymást a számukra elérhető csúcsokról. Minden deklaráció a cél csomópontból és az informáló csomópont által ismert legrövidebb út költségéből áll.
  • Kezdetben minden csúcs csak a szomszédos csúcsokat jelenti, amelyekben a legrövidebb utak költsége megegyezik az élek költségével.
  • A deklaráció vételekor a csomópont kiszámítja a deklarált csomóponthoz vezető út költségét a deklaráló csomóponton keresztül, a deklaráló csomóponthoz vezető él költségének és a deklarációban szereplő útvonal költségének összegeként. Ezt követően a csomópont ellenőrzi, hogy tudja-e már a deklarált célcsomópont elérési útját.
  • Ha nem tudja, vagy ha az ismert útvonal költsége nagyobb, mint az új útvonal számított költsége, a csomópont megjegyzi a célcsomóponthoz vezető új útvonalat.
  • Ha az új elérési út egy meglévőt helyettesít, az utóbbit el kell vetni.
  • Ha a meglévő útvonal költsége kisebb vagy egyenlő, mint az új elérési út költsége, akkor az új útvonal el lesz vetve.
  • Az új útvonal memorizálása után a csúcsnak be kell jelentenie a célcsúcsot és az új útvonal költségét a szomszédos csúcsokhoz.
Router működése

A távolság-vektor algoritmusokban minden útválasztó periodikusan és egy vektort sugároz a hálózaton keresztül , amelynek összetevői a távolságok (egy vagy másik metrikában mérve ) ettől az útválasztótól az összes általa ismert hálózatig. Az útválasztási protokoll - csomagokat általában távhirdetéseknek nevezik, mivel ezeket az útválasztó arra használja, hogy közölje más útválasztókkal, hogy mit tud a hálózati konfigurációjáról.

Miután valamelyik szomszédtól megkapta az általa ismert hálózatokhoz való távolságok (távolságok) vektorát , az útválasztó megnöveli a vektor összetevőit a saját és a szomszéd közötti távolsággal. Ezenkívül a vektort kiegészíti más, általa ismert hálózatokkal kapcsolatos információkkal, amelyekről közvetlenül (ha az ő portjaihoz csatlakoznak) vagy más útválasztók hasonló bejelentéseiből értesült. A router elküldi a vektor frissített értékét a szomszédjainak. Végül minden útválasztó megtanulja a szomszédos útválasztókon keresztül információkat az összetett hálózatban elérhető összes hálózatról és a távolságokról. [2]

Ezután minden hálózathoz több alternatív útvonal közül kiválasztja azt az útvonalat, amelynél a legkisebb a metrika értéke . Az erről az útvonalról információt küldő útválasztó a következő ugrásként van megjelölve az útválasztási táblázatban.

Előnyök és hátrányok

A távolságvektor-algoritmusok csak kis hálózatokban működnek jól. A nagy hálózatokban időszakonként eltömítik a nagy forgalommal járó kommunikációs vonalakat, emellett a konfigurációs változásokat nem mindig lehet megfelelően feldolgozni az ilyen típusú algoritmusokkal, mivel az útválasztóknak nincs pontos elképzelésük a hálózatban lévő kapcsolatok topológiájáról , hanem csak közvetett információval rendelkeznek - a távolságvektor.

Távolságvektor protokollok

RIPv1 protokoll

A RIPv1 távolságvektor protokoll (Routing Information Protocol) az első dinamikus útválasztási protokoll, és ma nagyon gyakran használják.

Ezt a protokollt belső útválasztási protokollként használják kis hálózatokban, és minden gyártó berendezése támogatja. [3]

Alapparaméterek
  • RIP - távoli vektor protokoll.
  • Adminisztratív távolság - 120.
  • A mérőszám az ugrások száma.
  • Az ugrások maximális száma 15.
  • Az elérhetetlen útvonal mérőszáma 16.
  • Útválasztási információk frissítéseinek terjesztése - 30 másodpercenként sugározzák.
  • Konvergencia várakozási számláló (Hold-Down Timer) - 180 mp.
  • Alhálózati maszk – az alapértelmezett maszkot használják, a hálózati osztály határozza meg, nem küldi el a frissítés.

RIPv2 protokoll

A RIPv2 távolságvektor protokoll a RIPv1 protokoll egy módosítása .

Ezt a protokollt belső útválasztási protokollként használják kis hálózatokban, és minden gyártó berendezése támogatja. [3]

Alapparaméterek
  • A RIPv2 egy távoli vektorprotokoll.
  • Adminisztratív távolság - 120.
  • A mérőszám az ugrások száma.
  • Az ugrások maximális száma 15.
  • Az elérhetetlen útvonal mérőszáma 16.
  • Útválasztási információ frissítések terjesztése - a 224.0.0.9 multicast cím használatával 30 másodpercenként.
  • Konvergencia várakozási számláló (Hold-Down Timer) - 180 mp.
  • Az aktivált frissítések támogatása. Alhálózati maszk – a frissítésben elküldött változó hosszúságú maszkot használ.

A RIPv1 és a RIPv2 összehasonlítása

A RIPv1 és a RIPv2 összehasonlítása
Útválasztási protokoll RIPv1 RIPv2
Megszólítás Osztály Osztály nélküli
Változtatható hosszúságú maszk támogatás Nem Igen
Maszk küldése a frissítésekben Nem Igen
Cím típusa Adás Multicast
Leírás RFC 1058 RFCs 1721, 1722, 2435
Útvonal-összegzés támogatása Nem Igen
Hitelesítési támogatás Nem Igen

IGRP protokoll

A RIP -hez hasonlóan az IGRP router is rendszeresen szétosztja a táblája tartalmát a szomszédjai között adások útján. A RIP-től eltérően azonban az IGRP útválasztó egy már kialakított útválasztási táblázattal indul a hozzá kapcsolódó alhálózatokhoz. Ez a táblázat tovább bővül a legközelebbi szomszédos útválasztók információival. Az IGRP protokoll módosítási üzenetei nem tartalmaznak alhálózati maszk információt. Egy egyszerű RIP találatszám helyett különféle típusú metrikus információkat használnak, nevezetesen [4] :

Késleltetés Leírja (tíz mikroszekundumban) a cél eléréséhez szükséges időt, amikor nincs terhelés a hálózaton.
Sávszélesség 10 000 000 osztva az adott útvonal legkisebb sávszélességével (Kbps-ban mérve). Például a legalacsonyabb 10 Kb/s sávszélesség 1 000 000 Kb/s mérőszámnak felel meg.
Betöltés Egy adott útvonalon jelenleg használatban lévő sávszélesség arányaként mérve. 0-tól 255-ig terjedő számokkal kódolva (255 100%-os terhelésnek felel meg).
Megbízhatóság A datagram azon része, amely sérülés nélkül megérkezett. 0-tól 255-ig terjedő számokkal kódolva (a 255 azt jelenti, hogy a datagramok 100%-ban nem sérültek meg).
Komlószám Meghatározza a célhelyekre érkező találatok számát.
MTU útvonal (MTU útvonal) A legnagyobb átviteli egység (MTU) legnagyobb értéke a nyilvános elérési út bármely hivatkozásán keresztül elküldhető datagramokhoz.

EIGRP protokoll

Distance Vector Routing Protocol Az EIGRP a Cisco által kifejlesztett IGRP továbbfejlesztése. Az EIGRP egyesíti a távolságvektoros útválasztási protokollok elveit, pontosabb metrikával rendelkező távolságvektort használva a célhálózathoz vezető legjobb útvonalak meghatározásához, valamint a kapcsolatállapot-protokollok alapelveit, triggerelt frissítéseket használva az útválasztási információk változásainak terjesztésére. A működési elvek ezen kombinációja esetén ezt a protokollt néha hibrid protokollnak is nevezik.

Az EIGRP protokoll a következő eszközöket használja az útválasztás támogatására :

  • Neighbor table - a szomszédos útválasztók listáját tartalmazza, amely kétirányú kommunikációt biztosít a közvetlenül csatlakoztatott útválasztók között.
  • Topológia táblázat – tartalmazza az útvonalbejegyzéseket az összes célhálózathoz, amelyről az útválasztó tud.
  • A DUAL (diffusing update algoritmus) az útvonalak kiszámítására használt diffúziós frissítési algoritmus.
  • Routing table - a célhálózat legjobb útvonalait tartalmazza, a topológiai táblázatból kiválasztva.
  • Utód – A megtalált legjobb (elsődleges) útvonal a célhálózat eléréséhez. Bekerül az útválasztási táblázatba .
  • Lehetséges sikeres (Megvalósítható utód) - tartalék útvonal. A tartalék útvonalak kiválasztása a legjobbakkal egy időben történik. Ezeket az útvonalakat a topológiai táblázat tárolja. Több redundáns útvonal is lehet a célhálózathoz.

Lásd még

Irodalom

  1. M.V. DIBROV.  Routerek. - Krasznojarszk, 2008. - 389 p.
  2. Goldovsky Ya.M. , Zhelenkov B.V., Tsyganova N.A. Útválasztás számítógépes hálózatokban: Tankönyv. - M.: RUT (MIIT), 2017. - 114 p.
  3. Zolotarev S.P.. "Távolságvektor-útválasztó algoritmusok" Vologda Readings, no. 69, 2008, pp. 43-48.
  4. Sidney Faith.  TCP/IP architektúra, protokollok, megvalósítás (beleértve a 6-os IP-verziót és az IP-biztonságot). - Laurie, 2000. - ISBN 5-85582-072-6 .

Jegyzetek

  1. ↑ 1 2 M.V. DIBROV. Routerek. - Krasznojarszk, 2008. - 389 p.
  2. ↑ Zolotarev, S. P. Távolságvektoros útválasztási algoritmusok  (orosz)  // Vologdai olvasmányok. - 2008. - 69. sz . - S. 43-48 . Az eredetiből archiválva : 2020. december 12.
  3. ↑ 1 2 Goldovsky Ya.M. , Zhelenkov B.V., Tsyganova N.A. Útválasztás számítógépes hálózatokban. — M.: RUT (MIIT), 2017. — 114 p.
  4. ↑ Sidney Faith. TCP/IP architektúra, protokollok, megvalósítás (beleértve a 6-os IP-verziót és az IP-biztonságot). - Laurie, 2000. - ISBN 5-85582-072-6 .