Концепція автономної системи

Вказані вище складнощі щодо обміну інформацією зі системою ядра про досяжність мереж виникають тому, що бралися до уваги тільки аспекти архітектури раутінгу і не розглядалося адміністрування мережею. Складні топології, подібні до показаних на рис., виникають тоді, коли вузол належить окремій організації, яка має локальні мережі під своїм адміністративним управлінням (корпоративна мережа). Адміністративний орган може гарантувати, що внутрішні маршрути є узгодженими і життєздатними. Крім того, адміністративний орган може виділити один раутер, який інформуватиме зовнішнє середовище про досяжність мереж. Наприклад, раутер R3 на рис може оголошувати досяжність мереж 2, 3 і 4, приймаючи, що система ядра завжди знає про мережу 1, яка під’єднана безпосередньо до раутера ядра R1.

З точки зору раутінгу група мереж і раутерів, керованих окремим адміністративним органом, називають автономною системою. Раутери всередині автономної системи можуть використовувати власні механізми для дослідження, створення і перевірки узгодженості маршрутів. Відзначимо, що згідно з цим означенням раутери ядра формують автономну систему. Концептуально ідея автономної системи є природнім узагальненням архітектури, зображеної на рис. 3.51, де локальні мережі слід замінити автономними системами. Рис. ілюструє цю ідею. Кожна автономна система містить багато локальних мереж і раутерів, підпорядкованих одному адміністративному органу.

Рис. 3.51. Архітектура загальної мережі з автономними системами як вузлами магістралі.

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

Щоб автоматизні алгоритми могли розрізняти автономні системи, кожній автономній системі надається унікальний номер – ідентифікатор автономної системи. Це здійснює той сам центральний орган, який має повноваження для виділення IP-адрес. Коли два раутери обмінюються інформацією про досяжність мереж, то повідомлення переносять ідентифікатор автономної системи, яку репрезентує раутер.

Алгоритми раутінгу

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

Алгоритми раутінгу часто мають одну або більше з таких проектних цілей:

оптимальність;

простота і малі власні витрати;

стійкість до помилок і стабільність;

швидка збіжність;

гнучкість.

Оптимальність. Оптимальність відноситься до здатності алгоритму виділити “найкращий” маршрут. Найкращий маршрут залежить від метрик і ваг метрик, які вживаються при обчисленнях. Наприклад, один алгоритм раутінгу використовує кількість стрибків і затримку, однак однак робить вагу затримки більш вагомою при розрахунках. Звичайно, алгоритм раутінгу повинен чітко визначити свій алгоритм обчислення метрики.

Простота. Алгоритми раутінгу проектуються максимально простими, наскільки це можливо. Іншими словами, алгоритми раутінгу повинні пропонувати сввою функціональну ефективність з мінімальними власними витратами у програмному забезпеченні та використанні. Ефективність звичайно важлива, колт використання програмного забезпечення для алгоритмів раутінгу повинне виконуватися на комп’ютері з обмеженими фізичними ресурсами.

Стійкість до помилок і стабільність. Алгоритми раутінгу повинні бути стійкими до помилок. Іншими словами, вони повинні коректно діяти при наявності непередбачених обставин, таких як відмови обладнання, перевантаження і некоректні впровадження. Оскільки раутери розташовані у вузлових точках мережі, слід передбачити розв’язання проблем, що виникають при їх відмові. Кращі алгоритми раутінгу – це часто ті, які мають здатність протистояти випробуванням часу і залишаються стабільними при різноманітних умовах в мережі.

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

Рис. 3.52показує маршрутну петлю. У цьому випадку пакет поступає до раутера 1 в момент t ₁. Нехай таблиця раутінгу раутера R1 у деякий момент змодифікована і вказує, що оптимальний маршрут до призначення прямує через раутер R2 як раутер наступного стрибка. Тоді раутер R1 скеровує пакет до раутера R2. Якщо таблиця раутера R2 ще не змодифікована, тобто наявна повільна збіжність процесу модицікації таблиць раутінгу, то R2 вважає, що оптимальним наступним стрибком є раутер R1 і висилає пакет до нього. Таким чином, пакет буде циркулювати між раутерами R1 і R2, доки таблиця раутінгу раутера R2 не буде змодифікована або доки пакет не буде перекомутований між раутерами R1 і R2 максимально прийнятну кількість разів.

Рис. 3.52. Повільна збіжність і маршрутні петлі.

Гнучкість. Алгоритми раутінгу також повинні бути гнучкими. Іншими словами, алгоритми раутінгу повинні швидко і точно адаптуватися до різних обставин в мережі. Наприклад, приймемо, що у мережевому сегменті виявилася несправність. Більшість алгоритмів раутінгу при появі такої проблеми швидко виявляють наступний найкращий шлях для всіх маршрутів, які звичайно використовують цей сегмент. Алгоритми раутінгу можуть бути запрограмовані для пристосування до змін у ширині смуги мережі, розміру черги раутера, затримки в мережі та до інших змінних.

Типи алгоритмів раутінгу

Алгоритми раутінгу можна класифікувати за типами. Наприклад, алгоритми можуть бути:

статичними або динамічними;

одношляховими або багатошляховими;

плоскими або ієрархічними;

орієнтованими на інтелектуальну станцію або на інтелектуальний раутер;

внутрішньодоменними або міждоменними;

типу “зв’язок-стан” або “вектор-відстань”.

Статичні або динамічні алгоритми раутінгу. Статичні алгоритми раутінгу найбільш жорсткі з усіх. Відображення таблиць раутінгу здійснює мережевий адміністратор перед початком раутінгу. Таблиці може змінювати тільки мережевий адміністратор. Алгоритми, які використовують статичний раутінг, прості для проектування і добре працюють в середовищах, де мережевий трафік відносно прогнозований і будова мережі відносно проста. Оскільки системи із статичним раутінгом не можуть реагувати на зміни в мережі, вони в загальному вважаються непридатними у сьогоднішніх великих, постійно змінни мережах. Переважна більшість алгоритмів раутінгу, які застосовувалися у 90-х роках, є динамічними.

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

Алгоритми динамічного раутінгу можуть використовувати статичні маршрути. Наприклад, раутер останнього звертання (раутер, до якого висилаються всі незмаршрутизовані пакети) може бути призначеним. Цей раутер діє як склад для всіх незмаршрутизованих пакетів, забезпечуючи, що всі повідомлення будуть нарешті обслужені певним чином.

Одношляхові або багатошляхові алгоритми раутінгу. Окремі складні протоколи раутінгу підтримують багато шляхів до того самого призначення. Ці багатошляхові алгоритми дозволяють мультиплексування трафіку через багато ліній, чого не роблять одношляхові алгоритми. Переваги багатошляхових алгоритмів очевидні; вони можуть забезпечити суттєво кращу пропускну здатність і надійність.

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

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

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

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

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

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

Алгоритм “зв’язок-стан” чи “вектор-відстань”. Алгоритми типу “зв’язок-стан” (відомі також під назвою алгоритмів з пріорітетом найкоротшого шляху) висилають інформацію про маршрути до всіх вузлів в об’єднанні мереж. Однак кожен раутер висилає лише частину таблиці маршрутизації, яка описує стан його власних зв’язків. Алгоритми типу “вектор-відстань” (відомі також під назвою алгоритмів Беллмана-Форда) звертаються до кожного раутера за висиланням цілих таблиць або частин їх таблиць раутінгу, але тільки для своїх сусідів. По суті, алгоритми типу “зв’язок-стан” висилають малі модифікації всюди, тоді як алгоритми типу “вектор-відстань” висилають великі модифікації тільки до сусідніх раутерів.

Внаслідок більшої швидкості збіжності алгоритми типу “зв’язок-стан” є досить мало схильні до утворення петель раутінгу, ніж алгоритми з векторною відстанню. З другого боку, алгоритми типу “зв’язок-стан” більш вимогливі до потужності центрального процесора і пам’яті. Через це алгоритми “зв’язок-стан” дорожчі для впровадження та підтримки. Незалежно від цих відмінностей, обидва типи алгоритмів добре працюють у більшості ситуацій.

Термін “вектор-відстань” відноситься до класу алгоритмів, які використовують раутери (шлюзи у термінології TCP/IP) для модифікації раутінгової інформації. Кожен раутер розпочинає роботу із множиною маршрутів для тих мереж або підмереж, до який він безпосередньо під'єднаний, і, можливо, із певними додатковими маршрутами до інших мереж або станцій, якщо мережева топологія така, що протокол раутінгу нездатний коректно створити бажаний раутінг. Цей список міститься у таблиці раутінгу, де кожен вхід ідентифікує мережу-призначення або станцію і вказує “відстань” до цієї мережі (станції). Відстань називають метрикою і вона звичайно вимірюється у “стрибках”.

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

відомий коротший шлях до призначення;

список призначень не містить раутера B;

якщо відстань до призначення, завжди маршрутованого від B до A, змінена.

Цей вид алгоритму простий для впровадження, але має ряд недоліків:

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

Кожен раутер висилає копію цілої своєї таблиці раутінгу до кожного сусіда через регулярні інтервали часу. Деякі раутери можуть використовувати довші інтервали, щоб уникнути перевантаження мережі, однак це викликає проблеми, пов’язані з тим, як добре мережа відповідає на зміни в топології.

Алгоритми “вектор-відстань” вживають лічильник стрибків як метрику, не враховуючи швидкість зв’язків або їх надійність. Такі алгоритми використають шлях із лічильником стрибків 2, який проходить через дві низькошвидкісні лінії, замість того, щоб використати шлях із лічильником стрибків 3, який проходить через три високошвидкісні мережі.

Найбільш складним завданням для алгоритмів “вектор-відстань” є запобігання нестабільності. Для цього вживають різні розв’язання.

Оголошення стану зв’язку є іншим прикладом повідомлень, які пересилаються між раутерами. Оголошення стану зв’язку інформують інші раутери про стан зв’язків висилача. Інформація про зв’язок може також використовуватися для побудови повної картини топології мережі. Як тільки мережева топологія стає зрозумілою, раутери можуть визначати оптимальні маршрути до мережевих призначень.

Першою альтернативою до схем “ вектор-відстань ” є клас протоколів, відомих як “ зв’язок-стан, першим найкоротший шлях ” (Link State, Shortest Path First).

Важливими властивостями цих протоколів раутінгу є такі:

множина фізичних мереж ділиться на певну кількість областей (area);

всі раутери всередині області мають ідентичні бази даних;

кожна база даних раутера описує повну топологію (тобто описує, які раутери під’єднані до яких мереж) в домені раутінгу; топологія області представлена базою даних, яку називають базою даних станів зв’язку (Link State Database), яка описує всі зв’язки які має кожен раутер в області;

кожен раутер використовує свою базу даних для виведення множини оптимальних шляхів до всіх призначень, з яких він будує свою таблицю раутінгу; алгоритм для визначення оптимальних шляхів називають алгоритмом “ першим найкоротший шлях ” (Shortest Path First).

У загальному випадку протокол стан-зв’язок працює таким чином. Кожен раутер періодично висилає опис своїх сполучень (стан своїз зв’язків) до своїх сусідів (раутери є сусідами, якщо вони сполучені із тою самою мережею). Цей опис, який називають оголошенням станів зв’язку (Link State Advertisement - LSA), включає сконфігуровану вартість сполучення. LSA поширюється в домені раутінгу. Кожен раутер у домені обслуговує ідентичну зсинхронізовану копію бази даних, складену із цієї інформації про стан зв’язків. Ця база даних описує як топологію домену раутінгу і маршрути до мереж поза доменом, так і маршрути до мереж в інших автономних системах (доменах). Кожен раутер виконує алгоритм у своїй топологічній базі даних, отримуючи дерево найкоротших шляхів. Це дерево найкоротших шляхів містить найкоротший шлях до кожного раутера і до мережі, досяжної для цього раутера. Значення вартості до призначення і наступний стрибок для пересилання данограми отримуються із дерева найкоротших шляхів і вживаються для побудови таблиці раутінгу раутера.

Протоколи “стан-зв’язок”, порівняно із протоколами “вектор-відстань”, висилають модифікації тоді, коли вони є новими, і можуть висилати регулярні модифікації у спосіб, визначений сусідніми раутерами, до яких зв’язок активний. Більш важливо, що інформація, якою обмінюються, є стан зв’язків раутера, а не вміст таблиці раутінгу. Це значить, що алгоритми “стан-зв’язок” використовують менше мережевих ресурсів, ніж їх відповідники “вектор-відстань”, особливо коли раутінг складний або автономна система велика. Вони, однак, вимагають значних обсягів обчислень. У результаті користувачі отримують швидші відповіді на події в мережі, швидшу збіжність маршрутів і доступ до більш сучасних мережевих послуг.

Метрики

Таблиці раутінгу містять інформацію, вживану комутаційним програмним забезпеченням для вибору найкращого шляху. Однак як будуються таблиці раутінгу? Яку особливу інформацію вони містять? Як алгоритми раутінгу визначають переваги одного маршруту перед іншими?

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

довжина шляху;

надійність;

затримка;

ширина смуги;

завантаженість;

вартість комунікації.

Довжина шляху. Це найбільш поширена метрика раутінгу. Окремі протоколи раутінгу дозволяють мережевому адміністратору приписувати довільну вартість кожному мережевому зв’язку. У цьому випадку довжина шляху дорівнює сумі вартостей, пов’язаних із проходженням кожного зв’язку. Інші протоколи раутінгу визначають лічильник стрибків як метрику, яка визначає кількість переходів через пристрої для об’єднання мереж (такі як раутери), які повинен здійснити пакет на маршруті від джерела до призначення.

Надійність у сенсі алгоритмів раутінгу відноситься до надійності (звичайно описаної через коефіцієнт помилкових бітів) кожного мережевого зв’язку. Окремі мережеві зв’язки можуть відмовляти частіше за інші. При відмові певні мережеві зв’язки можуть бути відновлені простіше або швидше від інших. Будь-який коефіцієнт надійності може бути врахований при призначенні коефіцієнтів надійності. Коефіцієнти надійності звичайно приписують мережевим зв’язкам мережеві адміністратори. Звичайно це довільні числові значення.

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

Ширина смуги відноситься до наявної ємності зв’язку щодо трафіку. Якщо інші фактори еквівалентні, то 10-мегабітний зв’язок через Ethernet переважає 64-кілобітну виділену лінію. Хоч ширина смуги є мірою максимальної пропускної здатності зв’язку, однак маршрути через зв’язок із більшою шириною смуги не обов’язково кращі від маршрутів через повільніші зв’язки. Якщо, наприклад, швидший зв’язок більш зайнятий,то реальний час, потрібний для пересилання пакету до призначення, може бути більший, ніж при пересиланні через повільніший зв’язок.

Завантаженість стосується до ступеня зайнятості мережевих ресурсів (таких, як раутери). Завантаженість може бути обчислена для різних шляхів включно з використанням центральних процесорів і обробкою кількості пакетів за секунду. Неперервний моніторінг таких параметрів сам може інтенсивно споживати ресурси.

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