Назвіть основні алгоритми маршрутизації.

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

Існують способи просування пакетів, які не вимагають таблиць маршрутизації. Простим способом передачі пакетів по мережі є «лавинна» маршрутизація, кожен маршрутизатор передає пакет іншим маршрутизаторам. Також є маршрутизація від джерела. Відправник поміщає в пакет інформацію про те, які проміжні маршрутизатори повинні брати участь у передачі пакету до мережі призначення. На основі цієї інформації кожен маршрутизатор зчитує адресу наступного маршрутизатора, і передає йому пакет для подальшої обробки.

Існує статична маршрутизація, у якій записи вводяться в пам’ять кожного маршрутизатора вручну адміністратором мережі та при зміні стану мережі адміністраторові необхідно терміново відбити ці зміни у відповідних таблицях маршрутизації; та адаптивної (динамічної) маршрутизаціїю, де всі зміни конфігурації мережі автоматично відображаються в таблицях маршрутизації завдяки протоколам маршрутизації. Такими протоколами є: протокол RIP, протокол IS-IS, протокол OSPF, BGPv4, HSRP, EIGRP.

Протокол RIP (Routing Information Protocol - протокол маршрутної інформації) є внутрішнім протоколом маршрутизації дистанційно-векторного типу. Цей протокол найчастіше використовується в невеликих мережах.

Процес побудови таблиці маршрутизації за допомогою протоколу RIP відбувається в загальному в 5 етапів. Етап 1 - створення мінімальної таблиці. Дана складова мережа включає вісім 1Р-мереж, пов’язаних чотирма маршрутизаторами з ідентифікаторами: Rl, R2, R3 і R4. Етап 2 - розсилка мінімальної таблиці сусідам. Після ініціалізації кожен маршрутизатор починає посилати своїм сусідам повідомлення протоколу IP в яких міститься його мінімальна таблиця. IP-повідомлення передаються в дейтаграмах протоколу і включають два параметри для кожної мережі: її IP-адресу та відстань до неї від передавального повідомлення маршрутизатора. Етап 3 - отримання IP-повідомлень і обробка отриманої інформації Етап 4 - розсилка нової таблиці сусідам. Кожен маршрутизатор відсилає нове RIP-повідомлення всім своїм сусідам. У цьому повідомленні він поміщає дані про всіх відомих йому мережах: як безпосередньо підключених, так і віддалених, про які маршрутизатор дізнався з RIP-повідомлень. Етап 5 - отримання RIP-повідомлень від сусідів і обробка отриманої інформації. Етап 5 повторює етап 3 - маршрутизатори приймають RIP-повідомлення, обробляють міститься в них і на її підставі коректують свої таблиці маршрутизації.

Протокол OSPF (Open Shortest Path First - вибір найкоротшого шляху першим) розбиває процедуру побудови таблиці маршрутизації на два етапи, до першого відноситься побудова та підтримка бази даних про стан зв’язків мережі, до другого - знаходження оптимальних маршрутів і генерація таблиці маршрутизації. Побудова та підтримка бази даних про стан зв’язків мережі. Зв’язки мережі можуть бути представлені у вигляді графа, в якому вершинами графа є маршрутизатори і підмережі, а ребрами - зв’язки між ними. Кожен маршрутизатор обмінюється зі своїми сусідами тією інформацією про графа мережі, яку він має до даного моменту. Маршрутизатори не модифікують інформацію, як це відбувається в дистанційно-векторних протоколах, а передають її в незмінному вигляді.

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

BGP (англ. Border Gateway Protocol, протокол граничного шлюзу) - основний протокол динамічної маршрутизації в Інтернеті. Протокол BGP призначено обміну інформацією про досяжності підмереж між автономними системами, тобто групами маршрутизаторів під єдиним технічним управлінням, використовують протокол внутрідоменной маршрутизації для визначення маршрутів всередині себе і протокол междоменной маршрутизації для визначення маршрутів доставки пакетів в інші АС. Передана інформація включає в себе список АС, до яких є доступ через дану систему. Вибір найкращих маршрутів здійснює виходячи з правил, прийнятих в мережі. BGP підтримує безкласову адресацію і використовує підсумовування маршрутів для зменшення таблиць маршрутизації. BGP, поряд з DNS, є одним з головних механізмів, що забезпечують функціонування Інтернету. BGP є протоколом прикладного рівня і функціонує поверх протоколу транспортного рівня TCP (порт 179). Після установки з’єднання передається інформація про всі маршрутах, призначених для експорту. Надалі передається тільки інформація про зміни в таблицях маршрутизації. При закритті з’єднання видаляються всі маршрути, інформація про яких передана протилежною стороною.

Протокол маршрутизації IS-IS (Intermediate System - to - Intermediate System) використовує той же принцип маршрутизації за станом каналів, що і протокол OSPF. Але якщо OSPF є розробкою IETF, то протокол IS-IS був створений ISO (International Standard Organization). Якраз в термінології ISO маршрутизатори називаються "проміжними системами" (Intermediate System, IS), а хости - "кінцевими системами" (End System, ES). Існує також протокол ES-IS, за допомогою якого маршрутизатори дізнаються про підключені до них хостах, а хости - про маршрутизатори. Протокол IS-IS поділяє мережу на області, щоб не поширювати інформацію про маршрути серед всіх маршрутизаторів мережі, забезпечуючи розумні розміри їх таблиць маршрутизації, а тим самим - швидку збіжність пошуку маршруту. Назване перевагу протоколу IS-IS - в той же час і його суттєвий недолік. Цей недолік пов’язаний з лавинної розсилкою пакетів, спричиненої раптовою зміною стану каналів. Принципи маршрутизації IS-IS дуже схожі на використовувані в протоколі OSPF. Для синхронізації баз даних маршрутизації IS-IS використовує пакети CSNP (Complete Sequence Number Packet) і PSNP (Partial Sequence Number Packet), за своїм призначенням приблизно аналогічні пакетам DD (Database Description) і LSR (Link State Request) протоколу OSPF. Протокол IS-IS підтримує і дворівневу ієрархічну систему мереж (периферійні області та магістральна область 0).

HSRP (Hot Standby Router Protocol, Hot Standby Redundancy Protocol) - протокол сімейства FHRP (First Hop Redundancy Protocol). Основне завдання даного протоколу полягає в тому, щоб домогтися 100% доступності та відмовостійкості першого хосту від відправника.

Це досягається шляхом використання у двох або більше маршрутизаторів або маршрутизирующих комутаторів третього рівня однієї IP адреси і MAC адреси так званого віртуального маршрутизатора. Така група називається HSRP групою. HSRP протокол реалізований поверх стека протоколів TCP/IP, для доставки службової інформації використовується протокол UDP. У свою чергу, дані пакети відправляються на IP адреса групового розсилання (multicast) 224.0.0.2

Шляхом проведення виборів HSRP група вибирає один активний роутер, що відповідає за форвардного пакетів, призначених віртуальному роутера. Вибори проводяться на підставі пріоритету роутера. Пріоритет може бути призначений адміністратором, що дозволяє йому впливати на процес вибору. Якщо адміністратор не визначив пріоритет, використовується значення за замовчуванням, рівне 100. Якщо жодному з роутерів в групі не був призначений пріоритет, то пріоритети всіх роутерів збігаються, активним у цьому випадку стане роутер з найбільшим IP адресою. Потім вибирається резервний роутер. Обмінюються повідомленнями тільки активний і резервний роутери.

Протокол EIGRP (Enhanced Interior Gateway Routing Protocol)-був представлений в 1994 році, як вдосконалена версія протоколу маршрутизації IGRP (Interior Gateway Routing Protocol), ці два протоколи розроблені компанією Cisco. На відміну від протоколу IGRP, який використовує класову маршрутизацію, протокол EIGRP підтримує безкласову маршрутизацію CIDR (classless interdomain routing) і маски змінної довжини VLSM (variable-length subnet mask). Від IGRP відрізняється більш швидкої конвергенцією, підвищеної масштабованість і більш ефективною обробкою петель маршрутизації. Протокол EIGRP є дистанційно-векторного протоколу маршрутизації, хоча його ще називають гібридним, він поєднує в собі кращі риси дистанційно-векторних алгоритмів і алгоритмів станом каналу.