НОУ ІНТУІТ, Лекція, Мережі та мережеві операційні системи

Проблеми маршрутизації у мережах

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

Маршрутизація від джерела передачі легко реалізується на проміжних компонентах мережі, але вимагає повного знання маршрутів на кінцевих компонентах. Вона досить рідко використовується в сучасних мережевих системах, і далі ми її не розглядатимемо.

По-друге, якщо для багатьох одержувачів в якості чергового вузла маршруту використовується один і той же компонент мережі, а інші маршрути вибираються для обмеженого числа одержувачів, то в таблицю явно заносяться тільки записи для цього невеликої кількості одержувачів, а для маршруту, що веде до Більшість всієї мережі, робиться один запис – маршрутизація за умовчанням ( default ). Приклад простийтаблиці маршрутизації для деякого комплексу абстрактної мережі наведено нижче:

За способами формування та використання таблиць маршрутизації алгоритми однокрокової маршрутизації можна розділити на три класи:

алгоритми фіксованої маршрутизації;
алгоритми простої маршрутизації;
алгоритми динамічної маршрутизації.

При фіксованій маршрутизації таблиця зазвичай створюється в процесі завантаження операційної системи. Усі записи у ній є статичними. Лінія зв'язку, яка буде використовуватися для доставки інформації від даного вузла до деякого вузла A мережі, вибирається раз і назавжди. Зазвичай лінії вибирають те щоб мінімізувати повний час доставки даних. Перевагою цієї стратегії є простота реалізації. Основний недолік полягає в тому, що при відмові обраної лінії зв'язку дані не будуть доставлені, навіть якщо існує інший фізичний шлях для їх передачі.

Найбільш гнучкими є алгоритми динамічної абоадаптивної маршрутизації, які вміють оновлювати вміст таблиць маршрутів на основі обробки спеціальних повідомлень, що надходять від інших компонентів мережі, що займаються маршрутизацією, що задовольняють певному протоколу. Такі алгоритми прийнято ділити на два підкласи: алгоритми дистанційно-векторні та алгоритми стану зв'язків.

Векторно-дистанційні протоколи забезпечують досить розумну маршрутизацію пакетів, але не здатні запобігти виникненню маршрутних петель при збоях у роботі мережі. Тому векторно-дистанційна маршрутизація може бути ефективна лише щодо невеликих мережах. Для великих мереж застосовуються алгоритми стану зв'язків, що на кожному маршрутизаторі будують графи мережі,як вузли якого виступають її компоненти, а як ребер, що мають вартість, існуючі між ними лінії зв'язку. Маршрутизатори періодично обмінюються графами та вносять до них зміни. Вибір маршруту пов'язаний із пошуком оптимального за вартістю шляху за таким графом.

Детальний опис протоколів динамічної маршрутизації можна знайти в [Оліфер, 2002], [Таненбаум, 2003].