- Atstumo vektoriaus algoritmas yra dinaminis algoritmas.
- Jis daugiausia naudojamas ARPANET ir RIP.
- Kiekvienas maršrutizatorius palaiko atstumo lentelę, žinomą kaip Vektorius .
Trys raktai, norint suprasti atstumo vektorinio maršruto parinkimo algoritmo veikimą:
Atstumo vektorinio maršruto parinkimo algoritmas
Tegul dxy) yra mažiausiai kainuojančio kelio nuo mazgo x iki mazgo y kaina. Mažiausios išlaidos yra susijusios su Bellman-Ford lygtimi,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)}
Kur minv yra lygtis, paimta visiems x kaimynams. Nuvažiavus nuo x iki v, jei atsižvelgsime į mažiausiai kainuojantį kelią nuo v iki y, kelio kaina bus c(x,v)+din(y). Mažiausia kaina nuo x iki y yra mažiausia c(x,v)+diny) perėmė visus kaimynus.
Naudojant Distance Vector Routing algoritmą, mazge x yra tokia maršruto informacija:
- Kiekvieno kaimyno v kaina c(x,v) yra kelio kaina nuo x iki tiesiogiai prijungto kaimyno v.
- Atstumo vektorius x, ty Dx= [Dx(y) : y N ], įskaitant išlaidas visoms paskirties vietoms, y N.
- Kiekvieno jo kaimyno atstumo vektorius, ty Din= [Din(y) : y iš N ] kiekvienam x kaimynui v.
Atstumo vektoriaus maršrutas yra asinchroninis algoritmas, kuriame mazgas x siunčia savo atstumo vektoriaus kopiją visiems savo kaimynams. Kai mazgas x gauna naują atstumo vektorių iš vieno iš gretimų vektorių v, jis išsaugo v atstumo vektorių ir naudoja Belmano-Fordo lygtį, kad atnaujintų savo atstumo vektorių. Lygtis pateikta žemiau:
kas yra const java
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N
Mazgas x atnaujino savo atstumo vektorių lentelę naudodamas aukščiau pateiktą lygtį ir siunčia atnaujintą lentelę visiems savo kaimynams, kad jie galėtų atnaujinti savo atstumo vektorius.
Algoritmas
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>
Pastaba: Atstumo vektoriaus algoritme mazgas x atnaujina savo lentelę, kai mato bet kokį kainos pasikeitimą viename tiesiogiai susietame mazge arba gauna bet kokį vektorių naujinį iš kurio nors kaimyno.
Supraskime per pavyzdį:
Dalijimasis informacija
- Aukščiau pateiktame paveikslėlyje kiekvienas debesis žymi tinklą, o debesies viduje esantis skaičius – tinklo ID.
- Visi LAN yra sujungti maršrutizatoriais ir yra pavaizduoti langeliuose, pažymėtuose kaip A, B, C, D, E, F.
- Atstumo vektoriaus maršruto parinkimo algoritmas supaprastina maršruto parinkimo procesą, darydamas prielaidą, kad kiekvienos nuorodos kaina yra vienas vienetas. Todėl perdavimo efektyvumą galima išmatuoti pagal nuorodų skaičių, skirtą pasiekti paskirties vietą.
- Atstumo vektorinio maršruto parinkimo atveju kaina yra pagrįsta šuoliu skaičiumi.
Aukščiau pateiktame paveikslėlyje matome, kad maršrutizatorius siunčia žinias artimiausiems kaimynams. Kaimynai prideda šias žinias prie savo žinių ir siunčia atnaujintą lentelę savo kaimynams. Tokiu būdu maršrutizatoriai gauna savo informaciją ir naują informaciją apie kaimynus.
Maršrutizavimo lentelė
Vyksta du procesai:
- Lentelės kūrimas
- Lentelės atnaujinimas
Lentelės kūrimas
Iš pradžių kiekvienam maršrutizatoriui sukuriama maršruto parinkimo lentelė, kurioje yra bent trijų tipų informacija, pvz., tinklo ID, kaina ir kitas šuolis.
- Aukščiau esančiame paveikslėlyje parodytos originalios visų maršrutizatorių maršruto parinkimo lentelės. Maršruto parinkimo lentelėje pirmasis stulpelis nurodo tinklo ID, antrasis stulpelis nurodo ryšio kainą, o trečias stulpelis yra tuščias.
- Šios maršruto lentelės siunčiamos visiems kaimynams.
Pavyzdžiui:
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.
Lentelės atnaujinimas
- Kai A gauna maršruto parinkimo lentelę iš B, ji naudoja jos informaciją atnaujindama lentelę.
- B maršruto parinkimo lentelė rodo, kaip paketai gali persikelti į 1 ir 4 tinklus.
- B yra A maršrutizatoriaus kaimynas, paketai nuo A iki B gali pasiekti vienu šuoliu. Taigi prie visų B lentelėje nurodytų išlaidų pridedamas 1, o suma bus kaštai pasiekti konkretų tinklą.
- Sureguliavęs A sujungia šią lentelę su savo lentele, kad sukurtų kombinuotą lentelę.
- Kombinuotoje lentelėje gali būti pasikartojančių duomenų. Aukščiau pateiktame paveikslėlyje kombinuotoje maršrutizatoriaus A lentelėje yra pasikartojantys duomenys, todėl joje saugomi tik tie duomenys, kurių kaina yra mažiausia. Pavyzdžiui, A gali siųsti duomenis į 1 tinklą dviem būdais. Pirmasis, kuris nenaudoja kito maršrutizatoriaus, todėl kainuoja vieną šuolį. Antrajam reikia dviejų apynių (A į B, tada B į tinklą 1). Pirmasis variantas turi mažiausią kainą, todėl jis paliekamas, o antrasis atmetamas.
- Maršruto lentelės kūrimo procesas tęsiamas visiems maršrutizatoriams. Kiekvienas maršrutizatorius gauna informaciją iš kaimynų ir atnaujina maršruto parinkimo lentelę.
Toliau pateikiamos galutinės visų maršrutizatorių maršruto parinkimo lentelės: