logo

Atstumo vektorinio maršruto parinkimo algoritmas

    Atstumo vektoriaus algoritmas yra pasikartojantis, asinchroninis ir paskirstytas.
      Paskirstyta:Jis paskirstomas taip, kad kiekvienas mazgas gauna informaciją iš vieno ar kelių tiesiogiai prijungtų kaimynų, atlieka skaičiavimus ir paskirsto rezultatą atgal savo kaimynams.Pakartotinis:Jis kartojasi tuo, kad jo procesas tęsiasi tol, kol nebelieka informacijos, kuria galėtų keistis kaimynai.Asinchroninis:Nereikalaujama, kad visi jo mazgai veiktų užrakinimo žingsnyje vienas su kitu.
  • 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ą:

    Žinios apie visą tinklą:Kiekvienas maršrutizatorius dalijasi savo žiniomis visame tinkle. Maršrutizatorius siunčia surinktas žinias apie tinklą savo kaimynams.Maršrutas tik kaimynams:Maršrutizatorius siunčia savo žinias apie tinklą tik tiems maršrutizatoriams, kurie turi tiesiogines nuorodas. Maršrutizatorius per prievadus siunčia viską, ką turi apie tinklą. Informaciją gauna maršrutizatorius ir naudoja ją savo maršruto lentelės atnaujinimui.Dalijimasis informacija reguliariais intervalais:Per 30 sekundžių maršrutizatorius nusiunčia informaciją kaimyniniams maršrutizatoriams.

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) = &#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> 

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

Atstumo vektorinio maršruto parinkimo algoritmas
  • 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.
Atstumo vektorinio maršruto parinkimo algoritmas

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.

Atstumo vektorinio maršruto parinkimo algoritmas
    NET ID:Tinklo ID apibrėžia galutinę paketo paskirties vietą.Kaina:Kaina – tai apynių, kurių pakelis turi nuvežti, skaičius.Kitas šuolis:Tai maršrutizatorius, kuriam turi būti pristatytas paketas.
Atstumo vektorinio maršruto parinkimo algoritmas
  • 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 &amp; E. B sends its routing table to A &amp; C. C sends its routing table to B &amp; D. D sends its routing table to E &amp; C. E sends its routing table to A &amp; 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ą.
Atstumo vektorinio maršruto parinkimo algoritmas
  • Sureguliavęs A sujungia šią lentelę su savo lentele, kad sukurtų kombinuotą lentelę.
Atstumo vektorinio maršruto parinkimo algoritmas
  • 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.
Atstumo vektorinio maršruto parinkimo algoritmas
  • 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:

Atstumo vektorinio maršruto parinkimo algoritmas