Алгоритми маршрутизації в мережах

1. Вступ

В наш час комп’ютерні мережі перебувають в стані розвитку й набувають широкого розповсюдження. Лише комп’ютерна мережа Internet в даний час розрахована на 4.294.967.296 комп’ютерів, які матимуть IP адреси. До цього числа слід додати чиленні локальні та корпоративні мережі. Всі ці комп’ютери були з’єднані з метою обміну інформацією і власники комп’ютерів жадають швидкої передачі великої кількості інформації на значні відстані.

Вимоги користувачів мережі задовольняються покращенням якісті каналів передачі даних на заміну телефонним дротам прийшлі оптично-волоконні лінії, канали передачі даних за допомогою супутникового зв’язку тощо. Але значну роль при такій кількості з’єднаних в мережу комп’ютерів відіграє якість протоколів, за допомогою яких здійснюється передача даних

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

Враховуючи, що 4-байтну адресацію в мережі Internet буде замінено 8-байтною, тобто максимальна кількість комп’ютерів під’єднаних до мережі зросте у 4.294.967.296 разів, слід зазначити, що найбільшу роль відіграватиме покращення саме механізму маршрутизації пакетів даних між серверами мережі Internet.

Маршрутизація – це задача знаходження шляху між комп’ютером, що відсилає дані та комп’ютером-одержувачем, але в зв’язаній моделі IP ця задача в основному зводиться до пошуку шляхів до шлюзів між мережами. Поки пакети даних знаходяться на окремій мережі або підмережі проблеми маршрутизації вирішуються за технологією, специфічною для інтерфейсу цієї мережі. IP маршрутизація починається, коли потрібно передати дані між різними мережами з різними інтерфейсами. Якщо мережі отримувача та відправника безпосередньо зв’язані, то дані мають пройти через шлюз, що з’єднує мережі. Якщо ці мережі не зв’язані шлюзом, дані мають пройти через мережі, що знаходяться між відправником і одержувачем та шлюзами що їх з’єднують.Як тільки дані доходять до шлюзу на мережі отримувача, технологія маршрутизації цієї мережі спрямовує дані до отримувача.

Для знаходження маршруту до комп’ютера-отримувача система зберігає таблиці маршрутизації, які використовуються протоколами мережного рівня для вибору потрібного мережного інтерфейсу. Маршрутизаційна інформація зберігається у вигляді двох таблиць: перша – для маршрутів до хостів, друга – для маршрутів до мереж. Такий підхід дозволяє використовувати універсальні механізми визначення маршрутів як для мереж із розподіленим середовищем передачі даних , так і для мереж типу point-to-point. Визначаючи маршрут, модуль мережного протоколу (IP) спочатку переглядає таблиці для хостів, а потім для мереж. Якщо пошук не дає результату, то використовується маршрут по замовчуванню.

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

пункту призначення.

В таблиці 1 наведено приклад таблиці типу пункт призначення/наступний об’єкт для пересилання пакетів.

Мережа призначенняНаступний об’єкт

57вершина С

24вершина В

26вершина В

18вершина А

20вершина С