logo

Алгоритм дистанційної векторної маршрутизації

    Алгоритм вектора відстані є ітераційним, асинхронним і розподіленим.
      Розповсюджується:Він розподілений таким чином, що кожен вузол отримує інформацію від одного або кількох своїх безпосередньо підключених сусідів, виконує обчислення, а потім розподіляє результат назад своїм сусідам.Ітеративний:Він є ітеративним, оскільки його процес продовжується до тих пір, поки не стане доступною інформація для обміну між сусідами.Асинхронний:Він не вимагає, щоб усі його вузли працювали на етапі блокування один з одним.
  • Алгоритм вектора відстані є динамічним алгоритмом.
  • В основному використовується в ARPANET і RIP.
  • Кожен маршрутизатор підтримує таблицю відстаней, відому як Вектор .

Три ключі до розуміння роботи алгоритму дистанційної векторної маршрутизації:

    Знання про всю мережу:Кожен маршрутизатор ділиться своїми знаннями через всю мережу. Маршрутизатор надсилає зібрані відомості про мережу своїм сусідам.Маршрутизація лише до сусідів:Маршрутизатор надсилає інформацію про мережу лише тим маршрутизаторам, які мають пряме з’єднання. Маршрутизатор надсилає все, що має про мережу, через порти. Інформацію отримує маршрутизатор і використовує її для оновлення власної таблиці маршрутизації.Регулярний обмін інформацією:Протягом 30 секунд маршрутизатор надсилає інформацію сусіднім маршрутизаторам.

Алгоритм дистанційної векторної маршрутизації

Нехай dх(y) буде вартістю шляху з найменшою вартістю від вузла x до вузла y. Найменші витрати пов'язані рівнянням Беллмана-Форда,

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

Де minv — це рівняння, прийняте для всіх x сусідів. Після подорожі від x до v, якщо ми розглянемо шлях з найменшою вартістю від v до y, вартість шляху буде c(x,v)+dв(у). Найменша вартість від x до y є мінімумом c(x,v)+dв(y) охоплені всіма сусідами.

За допомогою алгоритму дистанційної векторної маршрутизації вузол x містить таку інформацію про маршрутизацію:

  • Для кожного сусіда v вартість c(x,v) є вартістю шляху від x до безпосередньо підключеного сусіда v.
  • Вектор відстані x, тобто Dх= [ Dх(y) : y у N ], що містить його вартість до всіх пунктів призначення, y, у N.
  • Вектор відстані кожного з його сусідів, тобто Dв= [ Dв(y) : y в N ] для кожного сусіда v з x.

Маршрутизація вектора відстані — це асинхронний алгоритм, у якому вузол x надсилає копію свого вектора відстані всім своїм сусідам. Коли вузол x отримує новий вектор відстані від одного зі своїх сусідніх векторів v, він зберігає вектор відстані v і використовує рівняння Беллмана-Форда для оновлення свого власного вектора відстані. Рівняння наведено нижче:

метод java
 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

Вузол x оновив власну таблицю векторів відстані за допомогою наведеного вище рівняння та надсилає свою оновлену таблицю всім своїм сусідам, щоб вони могли оновити власні вектори відстані.

Алгоритм

 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> 

Примітка. У векторному алгоритмі відстані вузол x оновлює свою таблицю, коли бачить будь-яку зміну вартості в одному безпосередньо пов’язаному вузлі або отримує будь-яке оновлення вектора від сусіда.

Розберемося на прикладі:

Обмін інформацією

Алгоритм дистанційної векторної маршрутизації
  • На наведеному вище малюнку кожна хмара представляє мережу, а число всередині хмари представляє ідентифікатор мережі.
  • Усі локальні мережі з’єднані маршрутизаторами, і вони представлені в полях, позначених як A, B, C, D, E, F.
  • Алгоритм маршрутизації з вектором відстані спрощує процес маршрутизації, припускаючи, що вартість кожного посилання дорівнює одній одиниці. Таким чином, ефективність передачі може бути виміряна кількістю посилань для досягнення пункту призначення.
  • У векторній маршрутизації відстані вартість базується на кількості переходів.
Алгоритм дистанційної векторної маршрутизації

На наведеному вище малюнку ми бачимо, що маршрутизатор надсилає знання безпосереднім сусідам. Сусіди додають ці знання до своїх і надсилають оновлену таблицю своїм сусідам. Таким чином маршрутизатори отримують власну інформацію плюс нову інформацію про сусідів.

Таблиця маршрутизації

Відбувається два процеси:

  • Створення таблиці
  • Оновлення таблиці

Створення таблиці

Спочатку для кожного маршрутизатора створюється таблиця маршрутизації, яка містить принаймні три типи інформації, наприклад ідентифікатор мережі, вартість і наступний стрибок.

Алгоритм дистанційної векторної маршрутизації
    NET ID:Ідентифікатор мережі визначає кінцеве призначення пакета.Вартість:Вартість — це кількість переходів, яку має пройти пакет, щоб потрапити туди.Наступний крок:Це маршрутизатор, до якого повинен бути доставлений пакет.
Алгоритм дистанційної векторної маршрутизації
  • На наведеному вище малюнку показано оригінальні таблиці маршрутизації всіх маршрутизаторів. У таблиці маршрутизації перший стовпець представляє ідентифікатор мережі, другий стовпець представляє вартість посилання, а третій стовпець порожній.
  • Ці таблиці маршрутизації надсилаються всім сусідам.

Наприклад:

 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. 

Оновлення таблиці

  • Коли A отримує таблицю маршрутизації від B, він використовує її інформацію для оновлення таблиці.
  • Таблиця маршрутизації B показує, як пакети можуть переміщатися до мереж 1 і 4.
  • B є сусідом маршрутизатора A, пакети від A до B можуть досягати за один стрибок. Таким чином, 1 додається до всіх витрат, наведених у таблиці B, і сума буде вартістю підключення до певної мережі.
Алгоритм дистанційної векторної маршрутизації
  • Після коригування A об’єднує цю таблицю зі своєю власною таблицею, щоб створити об’єднану таблицю.
Алгоритм дистанційної векторної маршрутизації
  • Об’єднана таблиця може містити повторювані дані. На наведеному вище малюнку об’єднана таблиця маршрутизатора A містить повторювані дані, тому в ній зберігаються лише ті дані, які мають найнижчу вартість. Наприклад, A може надсилати дані в мережу 1 двома способами. Перший, який не використовує наступний маршрутизатор, тому він коштує один стрибок. Другий вимагає двох стрибків (від A до B, потім від B до мережі 1). Перший варіант має найменшу вартість, тому його зберігають, а другий відмовляються.
Алгоритм дистанційної векторної маршрутизації
  • Процес створення таблиці маршрутизації триває для всіх маршрутизаторів. Кожен маршрутизатор отримує інформацію від сусідів і оновлює таблицю маршрутизації.

Остаточні таблиці маршрутизації всіх маршрутизаторів наведено нижче:

Алгоритм дистанційної векторної маршрутизації