- A távolságvektor algoritmus egy dinamikus algoritmus.
- Főleg ARPANET-ben és RIP-ben használják.
- Minden útválasztó egy távolságtáblázatot tart fenn, amely ún Vektor .
Három kulcs a távolságvektor útválasztási algoritmus működésének megértéséhez:
Távolságvektor Routing Algorithm
Legyen dx(y) az x csomóponttól az y csomópontig tartó legkisebb költségű út költsége. A legkevesebb költséget a Bellman-Ford egyenlet kapcsolja össze,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} Ahol a minv az összes x szomszédra felvett egyenlet. Az x-ből v-be való utazás után, ha figyelembe vesszük a v-től y-ig tartó legkisebb költségű utat, az útköltség c(x,v)+d lesz.ban ben(y). A legkisebb költség x-től y-ig a c(x,v)+d minimumaban ben(y) átvette az összes szomszédot.
A Distance Vector Routing algoritmussal az x csomópont a következő útválasztási információkat tartalmazza:
- Minden v szomszédnál a c(x,v) költség az x-től a közvetlenül kapcsolódó szomszédig, v.
- Az x távolságvektor, azaz Dx= [Dx(y) : y N-ben ], amely tartalmazza az összes rendeltetési helyre vonatkozó költségét, y-ban N-ben.
- Minden szomszédjának távolságvektora, azaz Dban ben= [Dban ben(y) : y N-ben ] x minden v szomszédjára.
A távolságvektor-útválasztás egy aszinkron algoritmus, amelyben az x csomópont elküldi távolságvektorának másolatát minden szomszédjának. Amikor az x csomópont megkapja az új távolságvektort az egyik szomszédos vektorától, v, elmenti v távolságvektorát, és a Bellman-Ford egyenlet segítségével frissíti saját távolságvektorát. Az egyenlet az alábbiakban látható:
panda iterrows
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N Az x csomópont a fenti egyenlet segítségével frissítette a saját távolságvektor-táblázatát, és elküldi frissített táblázatát minden szomszédjának, hogy azok frissíthessék saját távolságvektoraikat.
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) = ∞ 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> Megjegyzés: A távolságvektor-algoritmusban az x csomópont frissíti a tábláját, ha költségváltozást észlel egy közvetlenül kapcsolódó csomópontban, vagy ha vektorfrissítést kap valamelyik szomszédtól.
Értsük meg egy példán keresztül:
Információk megosztása
- A fenti ábrán minden felhő a hálózatot jelöli, a felhőben lévő szám pedig a hálózati azonosítót.
- Az összes LAN-t router köti össze, és az A, B, C, D, E, F feliratú dobozokban jelennek meg.
- A távolságvektoros útválasztási algoritmus leegyszerűsíti az útválasztási folyamatot, feltételezve, hogy minden kapcsolat költsége egy egység. Ezért az átvitel hatékonysága a cél eléréséhez szükséges linkek számával mérhető.
- A távolságvektoros útválasztásnál a költség az ugrásszámon alapul.
A fenti ábrán azt látjuk, hogy a router elküldi a tudást a közvetlen szomszédoknak. A szomszédok ezt a tudást hozzáadják saját tudásukhoz, és elküldik a frissített táblázatot saját szomszédjaiknak. Ily módon az útválasztók saját információkat kapnak, valamint a szomszédokról szóló új információkat.
Útválasztási táblázat
Két folyamat megy végbe:
- A táblázat létrehozása
- A táblázat frissítése
A táblázat létrehozása
Kezdetben minden útválasztóhoz létrejön az útválasztási táblázat, amely legalább háromféle információt tartalmaz, például a hálózati azonosítót, a költséget és a következő ugrást.
- A fenti ábrán az összes útválasztó eredeti útválasztási táblázata látható. Az útválasztási táblázatban az első oszlop a hálózati azonosítót, a második oszlop a kapcsolat költségét, a harmadik oszlop pedig üres.
- Ezeket az útválasztó táblákat elküldik az összes szomszédnak.
Például:
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.
A táblázat frissítése
- Amikor A egy útválasztó táblát kap B-től, akkor annak információit használja a tábla frissítéséhez.
- A B útválasztási táblázata megmutatja, hogy a csomagok hogyan mozoghatnak az 1-es és 4-es hálózatba.
- A B az A router szomszédja, az A-ból B-be érkezõ csomagok egy ugrással elérhetik. Tehát 1-et adunk a B táblázatban megadott összes költséghez, és az összeg egy adott hálózat elérésének költsége lesz.
- A beállítás után A ezt a táblázatot a saját táblázatával kombinálja egy kombinált táblázat létrehozásához.
- A kombinált táblázat ismétlődő adatokat tartalmazhat. A fenti ábrán az A router kombinált táblázata tartalmazza a duplikált adatokat, így csak azokat az adatokat tartja meg, amelyeknek a költsége a legalacsonyabb. Például A kétféleképpen küldheti el az adatokat az 1-es hálózatnak. Az első, amely nem használ következő útválasztót, tehát egy ugrásba kerül. A másodikhoz két ugrás szükséges (A-ból B-be, majd B-ből az 1-es hálózatba). Az első lehetőség a legalacsonyabb költséggel jár, ezért megtartják, a másodikat pedig elvetik.
- Az útválasztási tábla létrehozása minden útválasztónál folytatódik. Minden útválasztó megkapja az információkat a szomszédoktól, és frissíti az útválasztási táblázatot.
Az összes útválasztó végleges útválasztási táblázata az alábbiakban található:
