Електронний посібник

Лабораторная работа №4

Тема: Вивчення принципу ІР-адресації в комп'ютерних мережах та принципів маршрутизації

Мета роботи: вивчити принципи ІР-адресації, вивчити алгоритми маршрутизації, ознайомитися з методом визначення найкоротшого шляху в розподілених обчислювальних мережах на прикладі алгоритму Дейкстри.

Зміст звіту: тема, мета, покрокове здобуття найкоротшого шляху від вузла А до всіх останніх вузлів у вигляді графів і таблиці (завдання 1), граф мережі і таблиця маршрутизації (завдання 2), відповіді на контрольні питання.

Теоретичні відомості

Алгоритми маршрутизації

Розподіл каналів і потоків інформації на лінії зв'язку проводиться з врахуванням вартості шляху. Для оцінки вартості шляху використовуються різні критерії:

-число транзитних ділянок між взаємодіючими вузлами комутації (ВК);

-число зв'язків (ланок);

Найкоротшим шляхом передачі інформації називається шлях, для якої критерій вартості дороги має найменше значення в порівнянні з його значенням для інших можливих доріг.

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

Узагальнюючи, можна сказати, що всі алгоритми маршрутизації можна розбити на два класи: централізовані і децентралізовані.

Централізований алгоритм маршрутизації знаходить дорогу з найменшою вартістю від відправника до одержувача за допомогою повної інформації про мережу. Таким чином, як вхідні дані алгоритм використовує інформацію про те, який вузол з яким сполучений безпосередньо лінією зв'язку, і про вартість всіх ліній. Перш ніж почати самі обчислення, даний алгоритм повинен якимсь чином отримати цю інформацію. Самі обчислення можуть виводитися на якому-небудь одному комп'ютері (централізований глобальний алгоритм маршрутизації) або тиражуватися в різних місцях. Проте ключовою особливістю тут є те, що глобальний алгоритм володіє повною інформацією про топологію мережі і вартості ліній. На практиці алгоритми, що володіють глобальною інформацією про стан мережі, часто називають алгоритмами, заснованими на станах ліній, оскільки алгоритм повинен знати вартість кожної лінії в мережі. Ми вивчимо глобальний алгоритм, заснований на станах ліній, на прикладі алгоритму Дейкстри. На практиці він застосуються в протоколі ОSРF.

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

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

Третій спосіб класифікації алгоритмів маршрутизації визначається по тому, чи чутливий алгоритм до перевантаження. У чутливому до перевантаження алгоритмі вартості ліній динамічно змінюються, відображаючи поточний рівень перевантаження у відповідній лінії. Якщо з тимчасово переобтяженою лінією асоціюється висока вартість, алгоритм маршрутизації прагнутиме вибирати маршрути в обхід переобтяженої лінії. Перші алгоритми мережі АRРАnet були чутливими до перевантаження, проте спроби використання чутливих до перевантаження алгоритмів натрапили на ряд проблем Сьогодні в Інтернеті застосовуються алгоритми, нечутливі до перевантаження (такі як RІР, ОSРF і ВGР), оскільки вартість лінії, як правило, не відображає її поточного (або недавнього) рівня перевантаження.

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

У Інтернеті, як правило, використовуються лише два типи алгоритмів маршрутизації: динамічний глобальний алгоритм, заснований на станах ліній, і динамічний децентралізований дистанційно-векторний алгоритм.

Для вистежування змін в топології зв'язків мережі, змін в існуючих маршрутах і синхронізації таблиць маршрутизації серед маршрутизаторів і вузлів мережі використовуються протоколи обміну маршрутною інформацією. При цьому ці протоколи можуть ґрунтуватися на дистанційно-векторних алгоритмах, прикладом використання яких є протокол RІР, що мас реалізації для роботи в різних стеках протоколів, таких, як ТСР/ІР або ІРХ/SРХ, або на алгоритмах стану зв'язків, наприклад як протоколи IS-IS стека ОSІ, NLSР стека ІРХ/SРХ, ОSРF стека ТСР/ІР.

Вибір найкоротшого шляху

Ідея полягає в побудові графа підмережі, в якому кожен вузол відповідатиме маршрутизатору, а кожна дуга - лінії зв'язку (часто званою просто зв'язком). При виборі маршруту між двома маршрутизаторами алгоритм просто знаходить найкоротший шлях між ними на графі.

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

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

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

Аби показати, як працює цей алгоритм, розглянемо зважений ненаправлений граф (рис. З, а), де вагові коефіцієнти відповідають, наприклад, відстаням. Ми хочемо знайти найкоротший шлях А до D. Спершу ми чорним кружком позначаємо вузол А як постійний. Потім ми досліджуємо всі сусідні з ним вузли, вказуючи біля них відстань до вузла А. Якщо відшукується коротший шлях до якого-небудь вузла, то разом з вказівкою відстані у відмітці міняється і вузол, через який пройшов коротший шлях. Таким чином, пізніше можна відновити весь шлях. Розглянувши всі сусідні з А вузли, ми позначаємо найближчий вузол як постійний, як показано на рис. 3, б. Цей вузол стає новим робочим вузлом.

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

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

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

Тепер розглянемо випадок, коли вузол 2 все ще помічений як тимчасовий. В цьому випадку відмітка вузла Z або більше або рівна позначки вузла Е, або менше її. У першому випадку шлях АХYZЕ не може бути коротше, ніж шлях АВЕ Якщо ж відмітка вузла Z менше позначки вузла Е, то тоді вузол 2 повинен був стати постійним раніше вузла Е, і вузол Е перевірявся б з вузла Z.

Заливка

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

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

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

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

Алгоритми маршрутизації по вектору відстаней

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

Алгоритм маршрутизації по вектору відстаней інколи називають по іменах його творців розподіленим алгоритмом Беллмана-Форда і алгоритмом Форда-Фулкерсона. Цей алгоритм спочатку застосовувався в мережі АRРАNЕТ і в Інтернеті був відомий під назвою RIP. Найпоширенішим протоколом обміну маршрутною інформацією, заснованим на алгоритмі дистанційно-векторного типа, є протокол RIP - протокол маршрутної інформації. Як метрики різні реалізації протоколу RIP використовують широкий спектр показників, таких, як пропускна спроможність, затримки, надійність каналів зв'язку, проте найбільш поширеного в протоколах даного типа є метрика, що враховує кількість хопів. КІР застосовується в порівняно невеликих і відносно однорідних мережах, де відстань між двома будь-якими вузлами не повинна перевищувати 15 хопів.

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

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

Передбачимо, що як одиниця виміру використовується час затримки, і цей параметр відносно кожного з сусідів відомий маршрутизатору. Через кожні Т мілісекунди всі маршрутизатори посилають своїм сусідам список з приблизними затримками для кожного одержувача. Вони, зрозуміло, також отримують подібний список від всіх своїх сусідів. Припустимо, одна з таких таблиць прийшла від сусіда X, і в ній вказується, що час поширення від маршрутизатора X до маршрутизатора i рівне Xt. Якщо маршрутизатор знає, що час пересилки до маршрутизатора X рівне mn, тоді затримка при передачі пакету маршрутизатору i через маршрутизатор X складе Хt + т. Виконавши такі розрахунки для всіх своїх сусідів, маршрутизатор може вибрати найкращі шляхи і помістити відповідні записи в нову таблицю. Зверніть увагу на те, що стара таблиця в розрахунках не використовується.

Процес оновлення таблиці проілюстрований на рис. 1. Зліва показана підмережа (рис. 1, а). Перші чотири стовпці на рис. 1, б показують вектори затримок, отримані маршрутизатором J від своїх сусідів. Маршрутизатор A вважає, що час пересилки від нього до маршрутизатора В рівне 12 мс, 25 мс -до маршрутазатора С, 40 мс - до D і так далі. Передбачимо, що маршрутизатор J виміряв або оцінив затримки до своїх сусідів A, I, H, K як 8,10,12 і 6 мс відповідно.


Рисунок 1 Підмережа (а); отримані від А до К вектори і нова таблиця маршрутів для J (б)


Тепер розглянемо, як J розраховує свій новий маршрут до маршрутизатора G. Він знає, що затримка до А складає 8 мс, а А думає, що від нього до G дані дійдуть за 18 мс. Таким чином, J знає, що якщо він стане відправляти пакети для G через А, те затримка складе 26 мс. Аналогічно він обчислює значення затримок для маршрутів від нього до G, що проходять через останніх його сусідів (I, H і К), і отримує відповідно 41 (31+10), 18 (6 + 12) і 37 (31 + 6). Кращим значенням є 18, тому саме воно поміщається в таблицю в запис для одержувача G. Разом з числом 18 туди ж поміщається позначення лінії, по якій проходить найкоротший маршрут до G, тобто Н. Данини метод повторюється для всіх останніх адресатів, і нова таблиця, показана у вигляді правого стовпця на рисунку.


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

Маршрутизація з врахуванням стану ліній

Маршрутизація на основі векторів відстаней використовувалася в мережі АRРАNЕТ аж до 1979 року, коли її змінив алгоритм маршрутизації з врахуванням стану ліній. Відмовитися від колишнього алгоритму довелося по двох причинах. По-перше, старий алгоритм при виборі шляху не враховував пропускну спроможність ліній. Поки всі лінії мали пропускну спроможність 56 Кбіт/с, в обліку пропускної спроможності не було необхідності. Проте стали зявлятися лінії із швидкістю 230 Кбіт/с, а потім і 1,544 Мбіт/с, і не брати до уваги пропускну спроможність стало неможливо. Звичайно, можна було ввести пропускну спроможність як множник для одиниці виміру, але була ще і інша проблема, що полягала в тому, що алгоритм дуже довго приходив до стійкого стану (проблема рахунку до незкінченості).

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

У основі алгоритму лежить проста ідея, її можна викласти в п'яти вимогах до маршрутизатора. Кожен маршрутизатор повинен:

  1. Виявляти своїх сусідів і визнавати їх мережеві адреси.

  2. Вимірювати затримку або вартість зв'язку з кожним зі своїх сусідів.

  3. Створювати пакет, що містить всю зібрану інформацію.

  4. Посилати цей пакет всім маршрутизаторам.

  5. Обчислювати найкоротший шлях до всіх маршрутизаторів.

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

Протокол ОSРF («найди найкоротший шлях першим») є прикладом протоколу, заснованого на використанні алгоритму стану зв'язків.

ОSРF використовується для внутрішньої маршрутизації в мережах будь-якої складності. Метрика ОSРF є оцінкою якості зв'язку, звичайно це пропускна спроможність даної мережі. Причому метрика маршруту складає суму метрик всіх хопів маршруту.

Для визначення найбільш оптимального маршруту кожен маршрутизатор збирає інформацію про топологію мережі.

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

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

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

Після обміну інформацією про бази даних маршрутизатори можуть визначити, записів про які зв'язки їм не вистачає. Ці записи запрошуються у маршрутизатора-сусіда за допомогою спеціального повідомлення «запит про стан зв'язків». У відповідь маршрутизатор-сусід посилає повідомлення «оновлення стану зв'язків».


Завдання:

1. Визначити найкоротшу дорогу від вузла А до всіх вузлів по алгоритму Дейкстри. У таблиці 1 представлені вартості доріг між вузлами мережі, представленої на рис.2.


Таблиця 1 - Варіанти завдань

№варианта

АВ

АD

АС

ВС

ВD

СD

СЕ

СF

DЕ

EF

1

11

2

13

5

4

10

5

_8

14

1

2

20

12

8

5

6

16

5

10

12

4

3

1

3

8

4

2

7

5

6

9

1

4

4

8

12

13

9

2

7

6

11

10

5

12

3

9

4

2

9

13

4

9

5

6

2

5

9

4

11

15

7

2

9

11

7

5

9

7

13

15

4

8

6

10

1

8

6

4

10

5

8

12

14

11

4

3

9

2

5

9

2

10

15

8

7

10

1

10

6

8

12

5

2

1

3

7

9

1

11

5

12

5

13

2

1

8

9

4

10

12

5

9

2

6

8

10

2

9

11

1

13

8

5

9

2

1

7

6

10

2

13

14

8

2

5

2

2

1

5

13

4

1

15

2

5

10

2

9

3

9

8

2

2

16

4

1

3

5

11

8

13

6

2

8

17

2

6

9

2

14

2

8

4

4

1

18

9

12

2

15

5

1

1

10

2

5

19

5

9

2

8

11

2

9

5

4

3

20

8

2

15

4

3

9

4

10

6

_5_

21

3

5

9

6

8

2

1

1

5

9

22

9

2

8

1

2

1

1

5

7

3

23

5

7

9

12

5

3

4

8

9

7

24

5

9

11

10

3

9

9

4

1

2

25

4

9

2

1

3

5

10

6

4

7

26

8

9

12

4

5

7

6

3

2

4













Рисунок 2 - Абстрактна модель мережі


Алгоритм Дейкстри

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

c(i,j) — стоимость линии от узла i до узла j. Если узлы і и j не соединенs напрямую, тогда c(i,j) = ∞. Чтобы упростить нашу систему обозначений й примеры, мы будем предполагать, что c(i,j) = c(j,i). Однако следует отметить, что данный алгоритм будет работать й в случае, когда стоимости c(i,j) и c(j,i) не равны.

D(v) — стоимость пути от узла-источника до узла-адресата v, у которого на данный момент (на текущей итерации алгоритма) стоимость минимальна.

р(v) — предыдущий узел (соседний с узлом v) на текущем пути с наименьшей стоимостью от источника до узла v.

N — множество узлов, для которых на данной итерации известньы пути с наименьшей стоимостью.

Алгоритм работает следующим образом:

  1. Все узлы, кроме стартового, маркируются парой значений, состоящей из стоимости до данного узла (первоначально "∞") и именем узла подхода (первоначально "-"). Узел подхода - зто ближайший (слева) соседний узел, к которому осуществляется непосредственный подход через маркируемый узел.

  2. Начиная со стартового, выбирается узел с самой низкой совокупной стоимостью. Данный узел считается „установленным".

  3. Соседние с установленным узлы маркируются совокупной стоимостью от стартового узла и именем узла подхода.

  4. Если узел уже маркирован, то его метка заменяется на новую, совокупная стоимость которой меньше, чем существующая совокупная стоимость.

  5. Маркировка продолжается до тех пор, пока все узлы не будут установлены.

В качестве примера рассмотрим сеть, показанную на рис. З,а, и найдем пути с минимальной стоимостью от узла А до всех возможных адресатов. В табл. 2 показаны поэтапные результаты работы алгоритма. В каждой строке таблицы приведены значення переменных алгоритма в конце очередной итерации.




Рисунок 3 - Шаги вычисления кратчайшего пуга от А к В. Стрелка указывает на установленный узел

  1. Каждый узел, кроме стартового, первоначально маркируется как (∞,-).

  2. Начиная с узла А, зафиксируйте его, перемаркируйте соседние (справа) узлы В и G с учетом их стоимости (рис.3,б, строка 1 табл.2).

  3. Теперь самой малой стоимостью обладает узел В, поэтому повторите с зтим узлом все действия пункта 2 (рис.3,в, строка 2 табл.2).

  4. Теперь узел Е имеет самую малую стоимость, поэтому он й используется. Новая стоимость для узла G меньше, чем существующая, поэтому старая метка (6,А) заменяется новой (5,E) (рис.2,г, строка 3 табл.2).

  5. Повторите предыдущую процедуру для узла G. В результате узел Н получает метку (9,G) (рис.3,д, строка 4 табл.2).

  6. Узел F имеет меньшую стоимость, позтому он выбирается. Стоимость до С через F равна существующей метке, поэтому она не меняется. Новая стоимость для узла Н меньше, чем существующая, поэтому старая метка (9,G) заменяется на новую (8, F) (рис.3,е, строка 5 табл.2).

  7. Повторите процедуру для узла Н. В результате метка узла D примет знаменне (10,Н) (строка 6 табл.2).

  8. Узел С имеет меньшую стоимость, он выбирается. Новая стоимость для узла D (12,С) больше предыдущей, поэтому не меняется (строка 7 табл.2).

  9. Все узлы установлены. Самый короткий путь от А к D имеет совокупную стоимость 10. Начиная от узла D в обратном порядке мы получаем найкратчайший путь: D->Н->F->Е->В-> А.

Таблица 2 - Результат работы алгоритма для сети с рис.2

Шаг

N

D(В),р(В)

D(Е),р(Е)

D(G),р(G)

D(С),р(С)

D(F),р(F)

D(Н),р(Н)

D(D),p(D)

1

А

2,А

,-

6,А

,-

,-

,-

,-

2

АВ


4,В

6,А

9, B

,-

,-

,-

3

АВЕ



5,E

9,В

6,Е

,-

,-

4

АВЕG




9,В

6,Е

9,G

,-

5

АВЕF




9, B


8,F

,-

6

АВЕFН




9,В



10,Н

7

АВС







10,Н

8

АВЕFHD









Завдання 2

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

1) Для варіантів 1,4,7,10,13,16,19,22,25. Визначити таблицю маршрутизації маршрутизатора, пов'язаного з вузлом В.

А

В (10)

D(5)

Е(20)


В

А (10)

С(20)

Е(10)

F(10)

С

В (20)

F(20)



D

А (5)

Е (10)



Е

А (20)

В (10)

D(10)

F(10)

F

В (10)

С(20)

Е (10)


2) Для варіантів 2,5,8,11,14,17,20,23,26. Визначити таблицю маршрутизації маршрутизатора, пов'язаного з вузлом С

А

С(7)

D(5)



В

А (7)

С(12)

Е(10)

F(3)

С

В (12)

F(15)

А(7)


D

А (5)

Е (10)



Е


В (Ю)

D(10)

F(10)

F

В(3)

С(15)

Е (10)


3) Для варіантів 3,6,9,12,15,18,21,24. Визначити таблицю маршрутизації маршрутизатора, пов'язаного з вузлом D

А


D(5)

F(10)


В

А (7)

С(20)

Е(10)


С

В(20)

F(6)

D(9)


D

А (5)

Е (10)

С(9)


Е


В (Ю)

D(10)

F(10)

F


С(6)

Е (10)

А(10)



 

Адреса призначення

Мережева адреса наступного маршрутизатора

Мережева адреса вихідного порту

Відстані до мережі призначення

А

-

ІР11

-

В

-

IP12

-

С

ІР22(R2)

ІР12

13

D

ІР61(R6)

ІР11

6

ІРс

ІР31(R3)

ІР11

15

Маршрут за умовчанням (до мереж Е та F)

ІР61(R6)

ІР11

-

Приклад:


Контрольні питання:

  1. Що таке маршрут пересилки?

  2. Які 2 основні завдання маршрутизації?

  3. Що таке алгоритм маршрутизації? Назвіть відомі вам алгоритми. Які використовуються в Інтернеті?

  4. Що таке таблиця маршрутизації, яка інформація в ній може міститися. Як і ким вона заповнюється?

  5. На основі яких критеріїв може відбувається вибір маршруту?

  6. Які протоколи використовуються для відстежування змін в топології зв'язків мережі, змін в існуючих маршрутах і синхронізації таблиць маршрутизації серед маршрутизаторів і вузлів мережі? На основі яких алгоритмів вони працюють?

  7. В чому суть алгоритму по вектору відстаней (як працює)?

  8. В чому суть алгоритму з врахуванням стану ліній (як працює)?

  9. Чим відрізняються централізовані та децентралізовані алгоритми маршрутизації, статичні і динамічні?