- Алгоритм вектора відстані є динамічним алгоритмом.
- В основному використовується в ARPANET і RIP.
- Кожен маршрутизатор підтримує таблицю відстаней, відому як Вектор .
Три ключі до розуміння роботи алгоритму дистанційної векторної маршрутизації:
Алгоритм дистанційної векторної маршрутизації
Нехай 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) = ∞ 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.
- Алгоритм маршрутизації з вектором відстані спрощує процес маршрутизації, припускаючи, що вартість кожного посилання дорівнює одній одиниці. Таким чином, ефективність передачі може бути виміряна кількістю посилань для досягнення пункту призначення.
- У векторній маршрутизації відстані вартість базується на кількості переходів.
На наведеному вище малюнку ми бачимо, що маршрутизатор надсилає знання безпосереднім сусідам. Сусіди додають ці знання до своїх і надсилають оновлену таблицю своїм сусідам. Таким чином маршрутизатори отримують власну інформацію плюс нову інформацію про сусідів.
Таблиця маршрутизації
Відбувається два процеси:
- Створення таблиці
- Оновлення таблиці
Створення таблиці
Спочатку для кожного маршрутизатора створюється таблиця маршрутизації, яка містить принаймні три типи інформації, наприклад ідентифікатор мережі, вартість і наступний стрибок.
- На наведеному вище малюнку показано оригінальні таблиці маршрутизації всіх маршрутизаторів. У таблиці маршрутизації перший стовпець представляє ідентифікатор мережі, другий стовпець представляє вартість посилання, а третій стовпець порожній.
- Ці таблиці маршрутизації надсилаються всім сусідам.
Наприклад:
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 отримує таблицю маршрутизації від B, він використовує її інформацію для оновлення таблиці.
- Таблиця маршрутизації B показує, як пакети можуть переміщатися до мереж 1 і 4.
- B є сусідом маршрутизатора A, пакети від A до B можуть досягати за один стрибок. Таким чином, 1 додається до всіх витрат, наведених у таблиці B, і сума буде вартістю підключення до певної мережі.
- Після коригування A об’єднує цю таблицю зі своєю власною таблицею, щоб створити об’єднану таблицю.
- Об’єднана таблиця може містити повторювані дані. На наведеному вище малюнку об’єднана таблиця маршрутизатора A містить повторювані дані, тому в ній зберігаються лише ті дані, які мають найнижчу вартість. Наприклад, A може надсилати дані в мережу 1 двома способами. Перший, який не використовує наступний маршрутизатор, тому він коштує один стрибок. Другий вимагає двох стрибків (від A до B, потім від B до мережі 1). Перший варіант має найменшу вартість, тому його зберігають, а другий відмовляються.
- Процес створення таблиці маршрутизації триває для всіх маршрутизаторів. Кожен маршрутизатор отримує інформацію від сусідів і оновлює таблицю маршрутизації.
Остаточні таблиці маршрутизації всіх маршрутизаторів наведено нижче: