Комп’ютерні мережі - Лекції з КС - ЛК
Тема 4. Засоби побудови об'єднаних мереж.
Маршрутизатор.Призначення, сфера застосування, функції, приклад з'єднання.Відмінність між мостами і маршрутизаторами.протоколи, що маршрутизуються. Вибір маршруту. Алгоритми маршрутизації, протоколи RIP та OSPF. Типи маршрутизаторів.
Забезпечує вибір найкоротшого шляху між джерелом та приймачем;
Забезпечує фільтрацію широкомовних повідомлень для локальної мережі;
Забезпечує фільтрацію спотворених пакетів;
Здійснюють вибір раціонального маршруту в мережах із замкнутими контурами.
Для визначення найкоротших маршрутів маршрутизатор підтримує таблицю маршрутизації, яка містить таку інформацію:
Способи зв'язку з іншими мережами;
Можливі шляхи між маршрутизаторами;
Вартість передачі цими шляхами
Не вносять жодних обмежень до топології мережі;
Легко вирішують проблеми з петлями, що виникають в мережах.
Вимагають набагато більше зусиль щодо адміністрування, порівняно з мостами;
Параметри кожного маршрутизатора повинні бути узгоджені з іншими маршрутизаторами в мережі.
Для побудови об'єднаної мережі доцільно використовувати мости, якщо виконується правило 80/20, тобто. 80% трафіку є локальним кожної подсети і 20% трафіку є глобальним, тобто. зовнішнім, для кожної підмережі. Це правило виконується, якщо сервер розташовується в одному сегменті зі своїми користувачами. Якщо ж побудувати таким чином мережу не вдається, то доцільно використовувати маршрутизатори.
Зазвичай маршрутизатори використовують для великомасштабних мереж, які використовують підмережі. Для зв'язку підмереж використовуються різнітипи ліній (Т1, модемний зв'язок та ін.).
Маршрутизатор, який прийняв пакет, призначений для віддаленої підмережі, передає його маршрутизатору, який обслуговує мережу призначення, тобто. маршрутизатор передає пакет іншому маршрутизатору, а чи не віддаленому комп'ютеру. Отже, для того щоб передати повідомлення від відправника, що знаходиться в одній мережі, одержувачу, що знаходиться в іншій мережі, потрібно здійснити деяку кількість переходів між мережами, щоразу вибираючи відповідний маршрут. Таким чином, маршрут є послідовністю маршрутизаторів, через які проходить пакет.
Таблиця маршрутизації для мережі A має вигляд:
Довжина колії (транзитні ділянки)
Маршрут вибирається на підставі наявної цих пристроїв інформації про поточну конфігурацію мережі, а також на підставі вказаного критерію вибору маршруту. Зазвичай критерієм виступає затримка проходження маршруту окремим пакетом або середня пропускна спроможність маршруту для послідовності пакетів. Часто також використовується дуже простий критерій, що враховує лише кількість пройдених маршруті проміжних маршрутизаторів (хопів). Для вибору оптимального маршруту проходження пакета маршрутизатор аналізує спеціальну інформаційну структуру – таблицю маршрутизації. Зазвичай, маршрутизатори автоматично створюють таблиці маршрутизації, обмінюючись службовою інформацією.
Маршрутизатори ділять на пристрої верхнього, середнього та нижнього класів.
Високопродуктивні маршрутизатори верхнього класу служать об'єднання мереж підприємства. Вони підтримують безліч протоколів та інтерфейсів, причому не тільки стандартних, але часом і дуже екзотичних. Пристрої даного типу можуть мати до 50 локальних портів абоглобальних мереж.
За допомогою маршрутизаторів середнього класу формуються менші мережні об'єднання масштабу підприємства. Стандартна конфігурація включає два-три порти локальних мереж та від чотирьох до восьми портів глобальної мережі. Такі маршрутизатори підтримують найпоширеніші протоколи маршрутизації та транспортні протоколи.
Маршрутизатор нижнього класу призначаються для локальних мереж підрозділів; вони пов'язують невеликі офіси мережею підприємства. Типова конфігурація: один порт локальної мережі та два порти глобальної мережі, розраховані на низькошвидкісні виділені лінії або комутовані з'єднання. Тим не менш, подібні маршрутизатори мають великий попит у адміністраторів, яким необхідно розширити наявні міжмережові об'єднання.
Маршрутизатори бувають двох основних типів:
У статичних маршрутизаторах таблиця маршрутизації задається вручну і змінюється у процесі роботи мережі. У динамічних маршрутизаторах таблиці маршрутизації задається автоматично у процесі обміну.
Відмінності між мостами та маршрутизаторами.
Мости передають широкомовні пакети через усі порти. Маршрутизатори фільтрують широкомовні пакети локальної мережі та фільтрують некоректні пакети.
Міст розпізнає тільки єдиний шлях між підмережами, і цей шлях є остовим (сполучним) деревом. Маршрутизатор має інформацію про всілякі шляхи між кожною парою джерело-одержувач і на основі цієї інформації обирає найкоротший шлях.
Процес маршрутизації можна представити двома ієрархічно пов'язаними компонентами:
Алгоритми маршрутизації повинні мати низку властивостей. До них відносяться:
Оптимальність при виборі маршруту;
Живість істабільність;
Оптимальність під час виборів маршруту одна із головних якостей алгоритму. Вона характеризує здатність алгоритму маршрутизації вибирати найкращий маршрут. У цьому оптимальність маршруту залежить від низки показників та його значимості.
Алгоритми маршрутизації розробляються якнайпростішими, тобто. з найнижчим використанням ресурсів носія.
Алгоритми повинні мати живучість, тобто. вибирати альтернативні маршрути при втраті зв'язку, функціонувати в умовах високих навантажень та при некоректних побудовах мережевої топології.
Алгоритми маршрутизації повинні мати властивості збіжності.Східність– це процес угоди між усіма маршрутизаторами щодо вибору оптимального маршруту. Якщо певна подія в мережі призводить до зміни маршрутів, маршрутизатори розсилають повідомлення про оновлення маршрутизації, які проходять по всій мережі. Після отримання маршрутизаторів відбувається перепризначення оптимальних маршрутів. Угода всіх маршрутизаторів має бути вироблена швидко, інакше можуть з'явитися активні петлі, і може статися вихід мережі з ладу.
Алгоритми маршрутизації повинні швидко та правильно враховувати зміни стану мережі, наприклад, відмова вузла, сегмента мережі.
При виборі маршруту маршрутизатори використовують алгоритми маршрутизації, які, зазвичай, є алгоритмами вибору найкоротших шляхів.
Існують дві основні групи алгоритмів маршрутизації:
Дистанційно-векторні алгоритми маршрутизації;
Алгоритми маршрутизації з урахуванням стану каналів зв'язку.
Робота маршрутизатора відповідно до дистанційно-векторного протоколу нагадує роботу моста, оскільки точної топологічної картини мережі такий маршрутизатор немає.
Найпопулярнішим алгоритмом цієї групи є алгоритм Беллмана-Форда. Цей алгоритм реалізовано протоколі маршрутизації RIP. Протокол RIP призначений для малих та середніх мереж. Як довжина шляху використовується кількість транзитних ділянок і тому протокол не враховує завантаженість мережі та пріоритети трафіку.
Протокол RIP не застосовується у великих мережах, тому що:
Існує обмеження на максимальну довжину колії (трохи більше 15 транзитних ділянок);
Обмін маршрутними таблицями регулярно створює додаткове навантаження в мережі.
В алгоритмахдругої групимаршрутизатори обмінюються вартістю локальних зв'язків d, причому обмін здійснюється не на регулярній основі, а у разі, коли змінюється вартість локального каналу. Ці алгоритми значно складніші, ніж алгоритми першої групи. У цих алгоритмах кожен маршрутизатор зберігає складну базу даних топології всієї мережі. Протоколи стану каналу важкі реалізації і потребують значному обсязі пам'яті для зберігання інформації про стан каналів.
Приклад алгоритму цієї групи є алгоритм Дейкстра. Цей алгоритм реалізовано протоколі маршрутизації OSPF. Алгоритм OSPF ефективно працює у великих мережах, що містять понад 100 маршрутизаторів. Цей протокол враховує мережеве навантаження та пріоритети потоків. Крім того, протокол дозволяє вибрати кілька найкоротших шляхів між кожною парою джерело – одержувач і рівномірно розподілити навантаження цими шляхами.
Алгоритми вибору найкоротшого шляху.
Ці алгоритми дозволяють визначити найкоротший шлях між кожною парою джерело-одержувач. Вартість шляху дорівнює сумі вартості ліній цього шляху. Довжина або вартість кожної лінії може вимірюватися або числом пакетів, що очікуютьпередачі, або середня затримка пакета в лінії. У найпростішому випадку довжина колії може вимірюватися кількістю транзитних ділянок.
Ідея алгоритму в тому, щоб спочатку знайти найкоротші шляхи, що містять не більше однієї дуги. Потім знайти найкоротші шляхи, що містять не більше двох дуг, потім трьох дуг і т.д. Таким чином, алгоритм ітерує числом дуг (чи числом транзитних ділянок).
Формальний запис алгоритму Беллмана-Фордаверсії Амає вигляд:
де h - Число дуг шляху;
N – кількість вузлів (маршрутизаторів) мережі;
Di h - Довжина найкоротшого шляху від 1-го вузла до i вузла, за умови, що шлях включає не більше h дуг;
dji - Довжина лінії між двома суміжними j i вузлами (відстань від j вузла до i вузла).
Версія Аалгоритм Беллмана-Форда підходить для централізованих обчислень.
Алгоритм працює не регламентовано, виконуючи іноді ітерацію. При цьому використовуються останні оцінки Dj, отримані від сусідів j
Формальний запис алгоритму Беллмана-Фордаверсії Вмає вигляд:
де N (i) – безліч сусідів-вузлів i-вузла, з'єднаних з i-вузлом, що походить від i-вузла лінією;
Di h - Довжина найкоротшого шляху від i-вузла до 1-го вузла, за умови, що шлях включає не більше h дуг;
Dij - Відстань від i вузла до j вузла.
Алгоритм Беллмана-Фордаверсіїдобре підходить для розподілених обчислень. У маршрутизаторах він реалізується в асинхронному вигляді:
Алгоритм асинхронному вигляді (*) виконується в маршрутизаторах не регламентовано, тобто. час від часу. Таким чином, алгоритм може розпочинати роботу з будь-яких початкових умов. У будь-якому випадку, алгоритм зводиться дознаходження найкоротших шляхів.
За Дейкстре, топологія мережі представляється як неорієнтованого графа із зазначеними кожному за ребра значеннями показників. Цим показником, наприклад, може бути відстань між двома сусідніми вузлами. У процесі алгоритму відбувається оцінка міток, присвоєних кожному вузлу графа. За меншим значенням мітки визначається оптимальний шлях між вузлами. Через війну сукупної оцінки шляхів між вузлами графа визначається загальний оптимальний маршрут.
Нехай потрібно визначити найкоротші шляхи від одного вузла до інших вузлів. Ідея алгоритму у цьому, щоб шукати шляху порядку зростання довжини шляху, тобто. алгоритм ітерує довжиною шляху.
Спочатку визначається найкоротший з найкоротших шляхів, цей шлях з'єднує перший вузол з найближчим сусіднім вузлом. Наступний найкоротший шлях - це шлях з 1-ої дуги до наступного найближчого вузла, або шлях з 2-х дуг, але обов'язково проходить через вузол, обраний на першому кроці і т.д.
На k - кроці ми маємо безліч P з k-вузлів найближчих до 1-го вузла. Тоді на (k+1) кроці шлях до наступного найближчого вузла повинен проходити вузлами з безлічі P і вартість цього шляху визначається як
де Di - Довжина найкоротшого шляху від 1-го вузла до i-вузла;
dij - вартість зв'язку між суміжними ij вузлами.
Формальний запис алгоритму Дейкстра має вигляд:
Пошук наступного найближчого вузла. Знайти вузол i
Покласти P=P
Після цього здійснюється перехід до пункту 2.
Отже, протоколи маршрутизації можуть бути побудовані на основі різних алгоритмів, що відрізняються способамипобудови таблиць маршрутизації, способами вибору найкращого маршруту та іншими особливостями своєї роботи.