Page 21 - 2577

Фіксована маршрутизація. При фіксованій маршрутизації для кожної пари вузлів:
відправлення і призначення у мережі вибирається один постійний маршрут. Для цього
використовується один із алгоритмів мінімальної вартості (Дейкстри, Беллмана-Форда). При
цьому маршрути є незмінними або, у крайньому випадку, змінюються при зміні топології
мережі.
Для визначення маршруту складається матриця, яка зберігається, наприклад, у центрі
керування мережею. Для користування таблицею необхідно лише знати, який вузол у
маршруті буде першим.
Допустимо, що маршрут найменшої вартості із вузла X в вузолY починається з каналу
X-А. Вартість частини маршруту, що залишилася (від А до Y) позначимо як R . Визначимо
1
R як маршрут мінімальної вартості від А до Y. Якщо R  R , то вибирається R ; у
2 1 2 2
протилежному випадку, коли R  R , то маршрут R не є маршрутом мінімальної вартості і
2
2
1
R  R .
1 2
Розглянемо конкретний приклад (рис. 2.4). Нехай задано матриця маршрутів (табл.
2.1), використовуючи її необхідно знайти шлях між вузлами 1 і 5.

Таблиця 2.1 – Маршрутна таблиця

Від вузла 4 5 6
1
2
3
Вузол
До вузла 1 - 1 5 2 4 5
2
2
4
-
5
5
2
3
4 4 3 - 5 3 5
4
-
5
4
4
5
5 4 4 5 5 - 5
6 4 4 5 5 6 -

Із табл. 2.1 визначимо, що маршрут від вузла 1 до вузла 6 починається у вузлі
3. Маршрут від вузла 4 до 6 проходить через вузол 5 і, на кінець, до вузла 5. Отже, маршрут
від вузла 1 до вузла 6 буде таким 1 – 4 – 5 – 5.
При фіксованій маршрутизації для дейтаграм і для віртуальних каналів застосовується
одна і та же стратегія.
Переваги:
- простота;
- надійно працює у мережі зі стабільним навантаженням.
Недоліки:
- мала гнучкість;
- не реагує на перевантаження та відмови.
Алгоритми фіксованої маршрутизації або алгоритм Дейкстри можна
сформулювати наступним чином:
- знайти найкоротший шлях від заданого (початкового) вузла до всіх інших вузлів;
- побудувати шляхи в порядку збільшення їх довжин.
Алгоритм виконується поетапно. На k - ому етапі визначаються найкоротші
шляхи до k вузлів найближчих (що мають найменшу вартість шляху) до початкового вузла.
Ці вузли утворюють множину T . На k  кроці додають новий вузол, що не входить у
1
множину T і має найкоротший шлях до початкового вузла. При додаванні нового вузла
визначають найкоротший шлях до нього від початкового вузла.
Формальний опис цього алгоритму подано нижче. Нехай задано такі
параметри:
N - множина вузлів мережі;

18