Page 74 - 2577

4.7.5 Динамічні алгоритми маршрутизації

Динамічна маршрутизація представлена алгоритмами мінімальної завантаженості
буферів та з урахуванням стану лінії. Суть динамічних алгоритмів полягає в тому, що для
обчислення нових найкоротших шляхів використовуються динамічні параметри, такі як
трафік. Обчислення нових шляхів відбувається через встановлені користувачем проміжки
часу. Алгоритм базується на мінімальній зайнятості буферів, має дві модифікації, перша з
них полягає в тому, що матриця суміжності формується з чисел від 1 до 100, які відповідають
процентному відношенню наповненості буфера, і друга, що можна задавати кількість
діапазонів на які розбивається дане процентне співвідношення. Для прикладу нехай ми
задали число 4, тоді 1-му діапазону відповідатиме процентне співвідношення 1-24, 2-му – 25-
49, 3-му – 50-74 і 4-му – 75-100. У цьому випадку коливання завантаження в межах одного із
діапазонів не викликає значних змін таблиці маршрутизації. В даних алгоритмах відсутня
інформація про кількість видалених дублікатів та кількість пакетів, видалених через
вичерпану ретрансляційну можливість. Натомість дані алгоритми будують найоптимальніші
шляхи, що мало б гарантувати найшвидшу доставку повідомлень адресату. Експеримент
проводиться на графі комп’ютерної мережі, зображеної на рисунку 4.15. Всі налаштування
вузлів та ліній передачі даних залишаються незмінними, якщо не оговорюється інше.
Зменшено паузу на відсилання пакетів вузлів-генераторів до 75 мсек, та зменшено діапазон
випадкових значень на генерування самих пакетів також до 75 мсек, кожен вузол-генератор
генерує по 200 пакетів з метою збільшення трафіка. Встановлення даних значень при
проведенні статичних експериментів привело б до значного перевантаження мережі та
втрати пакетів, все це свідчить про неефективність їх застосування.
Статистичні дані, представлені у таблиці 4.6 дають нам право говорити пре те, що
даний алгоритм забезпечує надійну передачу інформації від джерела до пункта призначення.
Ця надійність забезпечується порівняно частою необхідністю оновлення таблиць
маршрутизації. При збільшенні інтервалу оновлення спостерігаються втрати пакетів. Це
зумовлено тим, що пакети приходять швидше, ніж вузлу вдається їх обробити, а наступне
оновлення таблиць маршрутизації відбувається із запізненням, що не забезпечує жваві
реакції на ситуацію, яка склалася.

Таблиця 4.6 – Алгоритм, побудований на основі завантаженості буфера

Інтервал оновлення, сек.
Вузол Відкинуті, Пік, Відкинуті, Пік, Відкинуті, Пік,
5 10 15

пакети % пакети % пакети %
0 0 0 0 1 0 0
1 0 0 0 1 0 0
2 0 0 0 1 0 0
3 0 18 0 19 0 2
4 0 0 0 0 0 0
5 0 0 0 0 0 0
6 0 0 0 2 0 1
7 0 2 0 1 0 1
8 0 1 0 2 0 1
9 0 44 0 68 12 100
10 0 38 0 75 0 58
11 0 0 0 0 0 0
12 0 1 0 2 0 1

71