Алгоритм дифузного поновлення DUAL

Перед тим як почати читання цієї статті, радимо ознайомитися з матеріалом про розрахунок шляху за алгоритмом Bellman - ford.

Алгоритм дифузного поновлення (Diffusing Update Algorithm -DUAL) - один з двох обговорюваних тут алгоритмів, спочатку призначених для реалізації в розподіленої мережі. Він унікальний тим, що також видаляє інформацію про досяжності і топології, що міститься в кінцевому автоматі алгоритму. Інші обговорювані тут алгоритми залишають видалення інформації на розсуд реалізації протоколу, а не розглядають цей аспект роботи алгоритму всередині самого алгоритму.

До 1993 року Bellman-Ford і Dijkstra були реалізовані як розподілені алгоритми в декількох протоколах маршрутизації. Досвід, отриманий в результаті цих ранніх реалізацій і розгортання, привів до "другої хвилі" досліджень і роздумів про проблему маршрутизації в мережах з комутацією пакетів, що призвело до появи вектора шляху і DUAL.

Оскільки DUAL розроблений як розподілений алгоритм, найкраще описати його роботу в мережі. Для цієї мети використовуються малюнки 8 і 9. Щоб пояснити DUAL, в цьому прикладі буде простежуватися потік A, який вивчає три пункти призначення, а потім обробляються зміни в стані доступності для цих же пунктів призначення. У першому прикладі буде розглянуто випадок, коли є альтернативний шлях, але немає downstream neighbor, другий розгляне випадок, коли є альтернативний шлях і downstream neighbor.

На малюнку 8 вивчення D з точки зору A:

1. A дізнається два шляхи до D:

1. A не впізнає шлях через B, тому що B використовує A в якості свого наступника:
2. A порівнює доступні шляхи і вибирає найкоротший шлях без петель:
3. A перевіряє залишилися шляху, щоб визначити, чи є які-небудь з них downstream neighbors:

A знає це, тому що C оголошує маршрут до D зі своєю локальною метрикою, що дорівнює 3.

A зберігає локальну метрику C в своїй таблиці топології.

Отже, A знає локальну вартість в C і локальну вартість в A.

1. 3 (вартість в C) = 3 (вартість в A), тому цей маршрут може бути петлею, отже, C не задовольняє умові здійсненності. C не позначене як downstream neighbors.

Downstream neighbors в DUAL називаються можливими наступниками. Припустимо, що канал [A, H] не працює. DUAL не покладається на періодичні оновлення, тому A не може просто чекати іншого поновлення з достовірною інформацією. Швидше A повинен активно слідувати альтернативним шляхом. Таким чином, це дифузний процес виявлення альтернативного шляху. Якщо канал [A, H] не працює, враховуючи тільки D:

1. A перевіряє свою локальну таблицю на предмет можливих наступників (Downstream neighbors).
2. Можливих наступників немає, тому A повинен знайти альтернативний шлях без петель до D (якщо він існує).
3. A відправляє запит кожному сусідові, щоб визначити, чи є який-небудь альтернативний шлях без петель до D.
4. В C:
5. В B:
6. A отримує ці відповіді:

На малюнку 9 пункт призначення (D) був переміщений з H на E. Це буде використовуватися у другому прикладі.

У цьому прикладі є можливий наступник (downstream neighbor).

Вивчення D з точки зору A:

1. A дізнається два шляхи до D:
2. A не впізнає ніякого шляху через B:
3. A порівнює доступні шляхи і вибирає найкоротший шлях без петель:
4. A перевіряє залишилися шляху, щоб визначити, чи є які-небудь з них downstream neighbors:

Якщо канал [A, C] не працює, просто розглядаючи A:

1. A перевірить свою таблицю локальної топології на предмет можливого наступника.
2. Можливий наступник існує через H.
3. A перемикає свою локальну таблицю на H як кращий шлях.
4. A відправляє оновлення своїх сусідів, відзначаючи, що його вартість досягнення D змінилася з 3 до 4.

Як ви можете бачити, обробка, коли існує можливий наступник, набагато швидше і простіше, ніж без нього. У мережах, де було розгорнуто протокол маршрутизації з використанням DUAL (зокрема, EIGRP), однією з основних цілей проектування буде обмеження обсягу будь-яких запитів, що генеруються в разі відсутності можливого наступника. Область запиту є основним визначальним фактором того, як швидко завершується подвійний алгоритм і, отже, як швидко сходиться мережу.

На малюнку 10 показаний базовий закінчений автомат DUAL.

Речі, що входять в route gets worse (погіршення маршруту), можуть являти собою:

• Відмова підключеного каналу або сусіда
• Отримання поновлення для маршруту з більш високою метрикою
• Отримання запиту від поточного наступника
• Отримання нового маршруту від сусіда
• Виявлено новий сусід, а також маршрути, за якими він може дістатися
• Отримання всіх запитів, відправлених сусідам, коли маршрут погіршується