Проблеми маршрутизації у мережах
За наявності прямої лінії зв'язку між двома комп'ютерами зазвичай немає питань у тому, яким саме шляхом має бути доставлена інформація. Але, як вже згадувалося, одна з відмінностей взаємодії віддалених процесів від взаємодії процесів локальних полягає у використанні в більшості випадків процесів-посередників, розташованих на обчислювальних комплексах, що не є комплексами відправника і одержувача. У складних топологічних схемах організації мереж інформація між двома комп'ютерами може передаватися різними шляхами. Виникає питання: як організувати роботу операційних систем на комплексі-учасниках зв'язку (це можуть бути кінцеві або проміжні комплекси) для визначення маршруту передачі даних? За якою з кількох ліній зв'язку (або через якийсь мережевий адаптер) потрібно відправити пакет інформації? Якіпротоколимаршрутизації можливі? Існує два принципово різних підходи до вирішення цієї проблеми:маршрутизація від джерела передачі данихтаоднокрокова маршрутизація.
Маршрутизація від джерела передачілегко реалізується на проміжних компонентах мережі, але вимагає повного знання маршрутів на кінцевих компонентах. Вона досить рідко використовується в сучасних мережевих системах, і далі ми її не розглядатимемо.
По-друге, якщо для багатьох одержувачів в якості чергового вузла маршруту використовується один і той же компонент мережі, а інші маршрути вибираються для обмеженого числа одержувачів, то в таблицю явно заносяться тільки записи для цього невеликої кількості одержувачів, а для маршруту, що веде до Більшість всієї мережі, робиться один запис – маршрутизація за умовчанням (default). Приклад простийтаблиці маршрутизаціїдля деякого комплексупевної абстрактної мережі наведено нижче:
За способами формування та використаннятаблиць маршрутизаціїалгоритмиоднокрокової маршрутизаціїможна розділити на три класи:
алгоритмифіксованої маршрутизації;
алгоритмипростий маршрутизації;
алгоритмидинамічної маршрутизації.
При фіксованій маршрутизації таблиця, як правило, створюється в процесі завантаження операційної системи. Усі записи у ній є статичними. Лінія зв'язку, яка буде використовуватися для доставки інформації від даного вузла до деякого вузла A мережі, вибирається раз і назавжди. Зазвичай лінії вибирають те щоб мінімізувати повний час доставки даних. Перевагою цієї стратегії є простота реалізації. Основний недолік полягає в тому, що при відмові обраної лінії зв'язку дані не будуть доставлені, навіть якщо існує інший фізичний шлях для їх передачі.
Найбільш гнучкими єалгоритмидинамічноїабоадаптивної маршрутизації, які вміють оновлювати вміст таблиць маршрутів на основі обробки спеціальних повідомлень, що надходять від інших компонентів мережі, що займаються маршрутизацією, що задовольняють певномупротоколу. Такіалгоритмиприйнято ділити на два підкласи:алгоритми дистанційно-векторнітаалгоритми стану зв'язків.
Векторно-дистанційніпротоколизабезпечують досить розумну маршрутизацію пакетів, але не здатні запобігти виникненню маршрутних петель при збоях у роботі мережі. Тому векторно-дистанційна машрутизація може бути ефективна лише щодо невеликих мережах. Для великих мереж застосовуютьсяалгоритми стану зв'язків, на кожномумаршрутизаторібудуючі графи мережі, як вузли якого виступають її компоненти, а як ребер, що мають вартість, існуючі між ними лінії зв'язку.Маршрутизаториперіодично обмінюються графами і вносять до них зміни. Вибір маршруту пов'язаний із пошуком оптимального за вартістю шляху за таким графом.
Детальний описпротоколівдинамічної маршрутизаціїможна знайти в [Оліфер, 2002], [Таненбаум, 2003].