Page 25 - 2577
P. 25
• рівень навантаження у мережі буде вищий за оптимальний, але менший ніж при
лавинній маршрутизації.
Адаптивна маршрутизація враховує зміну умов, які впливають на маршрутизацію:
відмова вузлів або їх перевантаження. Стратегії адаптивної маршрутизації можна
класифікувати за джерелом інформації, яким може бути локальний вузол сусідні вузли або
всі вузли мережі. Прикладом адаптивної локальної маршрутизації є стратегія, коли вузол
направляє черговий пакет у канал з найкоротшою чергою Q . У результаті відбувається
вирівнювання навантаження у мережі. Але в цьому випадку деякі канали можуть передавати
пакети у зворотному (неправильному) напрямку з метою уникнення цього явища кожному
каналу присвоюють певний пріоритет B для кожного i -го вузла: тоді для кожного вхідного
i
пакету вузол буде вибирати канал з найменшою сумою Q B . Нижче подано приклад
i
адаптивної маршрутизації.
Приклад 2.2. На рис. 2.5 показаний стан вузла 4 мережі, поданої на рис. 2.4 у деякий
момент часу. На цей вузол прибуло певне число пакетів і на кожному вихідному каналі
утворились черги пакетів, які очікують відправки. Нехай пакет, який перший у черзі і який
прибув з вузла 1 необхідно направити до вузла 5. Кожний із чотирьох вузлів має свій
пріоритет. Визначити вихідний канал, до якого буде направлено вказаний пакет.
Рисунок 2.5 – Приклад локальної адаптивної маршрутизації
Обчислимо величини Q B . Результати обчислень занесемо у табл. 2.3.
i
Таблиця 2.4 – Визначення пріоритетів вузла 4
Наступний Кількість Пріоритет, Q B
i
вузол пакетів у черзі, Q B
i
1 2 9 11
2 3 6 9
3 1 3 4
4 5 0 5
Знайдемо мінімальне значення величини Q B за формулою
i
Q B min Q B .
i min i
i
Із таблиці 2.4 видно, що BQ 4, тобто вузол 4 направить наступний пакет до
i min
вузла 6 через вузол 2.
Адаптивні схеми, які використовують лише локальну інформацію, застосовують
порівняно рідко. Частіше використовують стратегії, які засновані на використанні інформації
від сусідніх вузлів чи від усіх вузлів. Обі ці стратегії користуються інформацією про
22
