Пошук оптимального маршруту

Для пошуку оптимального маршруту використовуються так звані алгоритми маршрутизації. Незалежно від того, окремо чи вибираються маршрути для кожного пакета або ж тільки один раз для з'єднання, бажано. Щоб алгоритм вибору маршруту володів певними властивостями - коректністю, простотою, надійністю, стійкістю, справедливістю і оптимальністю.
Існують загальні положення, що описують оптимальні маршрути, незалежно від топології або трафіку. Такий визначальною ідеєю є принцип оптимальності.Відповідно до цього принципу, якщо маршрутизатор B розташовується на оптимальний маршрут від маршрутизатора A до маршрутизатора C, то оптимальний маршрут від маршрутизатора B до маршрутизатора C співпаде з частиною першого маршруту. Прямим наслідком принципу оптимальності є можливість розгляду безлічі оптимальних маршрутів від всіх джерел до приймачів у вигляді дерева. Таке дерево називається вхідним деревом. Принцип оптимальності і вхідний дерево - це ті точки відліку, щодо яких можна вимірювати ефективність різних алгоритмів маршрутизації.
Найбільш поширені алгоритми пошуку оптимальних маршрутів:
1. Маршрутизація з урахуванням стану ліній.
2. Маршрутизація по вектору відстані.
3. Ієрархічна маршрутизація

39. Таблиці маршрутизації.

Щоб за адресою мережі призначення можна було б вибрати раціональний маршрутподальшого проходження пакету, кожен кінцевий вузол і маршрутизатор аналізуютьспеціальну інформаційну структуру, яка називається таблицею маршрутизації. Коли намаршрутизатор надходить новий пакет, номер мережі призначення, витягнутий з кадрунадійшов, послідовно порівнюється з номерами мереж з кожного рядка таблиці.Рядок із поєднаним номером мережі вказує, на який найближчий маршрутизатор сліднаправити пакет. Оскільки пакет може бути адресований в мережу складовою мережі, може здатися, що кожна таблиця маршрутизації повинна мати записи про всі мережах, що входять у складену мережу. Але при такому підході в разі великої мережі обсягтаблиць маршрутизації може виявитися занадто великим, що вплине на час їїперегляду, зажадає багато місця для її зберігання і т. п. Тому на практиці кількість записів в таблиці маршрутизації намагаються зменшити за рахунок використанняспеціального запису - «маршрутизатор за замовчуванням» (default).

40. Алгоритми маршрутизації та метрики.

Основна функція мережевого рівня полягає у виборі маршруту для пакетів від початкової до кінцевої точки. У більшості випадків пакетам доводитися проходити через кілька маршрутизаторів. Єдиним винятком є ​​широкомовні мережі. Алгоритми вибору маршрутів і використовувані ними структури даних є головною метою при проектуванні мережевого рівня.
Алгоритм маршрутизації реалізується тією частиною програмного забезпечення мережевого рівня, що відповідає за вибір вихідний лінії для відправки пакету, що прийшов. Якщо підмережа використовує дейтаграмним службу, вибір маршруту для кожного пакета повинен проводитися заново, так як оптимальний маршрут міг змінитися.
Деякі реалізації мережевих протоколів допускають наявність в таблиці маршрутизації відразу декількох рядків, які відповідають одному і тому ж адресою мережі призначення. У цьому випадку при виборі маршруту приймається до уваги стовпець "Відстань до мережі призначення». При цьому під відстанню розуміється будь-яка метрика, використовувана відповідно до заданого в мережевому пакеті критерієм. Відстань може вимірятися хопамі, часом проходження пакета по лінії зв'язку, будь-якої характеристикою надійності лінії зв'язку на даному маршруті або іншою величиною, що відбиває якість даного маршруту по відношенню до заданого критерію.

41. Внутрішні та зовнішні протоколи маршрутизації.

Маршрутизатори використовують протоколи маршрутизації для обміну маршрутною інформацією. Іншими словами, протоколи маршрутизації визначають, як
маршрутизуються протоколи передачі даних. двома родинами протоколів маршрутизації є протоколи внутрішніх шлюзів (Interior Gateway Protocol - IGP) і протоколи зовнішніх
шлюзів (Exterior Gateway Protocols - EGP). Класифікація всіх протоколів за цими
двох родин заснована на принципі їх роботи по відношенню до автономних
системам.
Автономною системою (Autonomous System - AS) називається мережу або група мереж, що перебувають під єдиним адміністративним контролем, як, наприклад, домен
Cisco.com. Автономна система складається з маршрутизаторів, які для зовнішнього світу (тобто для інших мереж) виглядають як єдина мережа. Агентство по виділенню
імен і унікальних параметрів протоколів Internet (Internt Assigned Numbers
Authority - IANA) виділяє номери автономних систем регіональним регістраторам. Такі
автономні системи описуються шестнадцатібітовим номером. При налаштуванні
таких протоколів маршрутизації, як BGP, потрібно вказати призначений уніКальний номер автономної системи.
Протоколи класу IGP маршрутизируют дані всередині автономних систем.
До класу IGP відносяться такі протоколи маршрутизації:
􀂄протоколи RIP і RIP V2;
􀂄IGRP;
􀂄EIGRP;
􀂄 OSPF;

42. Дистанційно –векторні протоколи.

Алгоритм дистанційно-Векторної маршрутизації визначає напрямок (вектор) і відстань (лічильник вузлів) для кожного з каналів зв'язку, що утворюють мережу.
При використанні цього алгоритму маршрутизатор періодично (наприклад, кожні 30 секунд) пересилає всю або частину своєї таблиці маршрутизації своїм сусідам. Періодичні поновлення розсилаються маршрутизатором, що використовують
дистанційно-векторний алгоритм, навіть якщо не відбулися ніякі зміни в
мережі. Отримавши таблицю маршрутизації від свого сусіда, маршрутизатор може провірити вже відомі маршрути і внести необхідні зміни на основі підлозілого оновлення. Такий процес іноді називають''маршрутизацією за чутками'',
оскільки подання маршрутизатора про структуру мережі базується на даних його
сусідів.
Дистанційно-Векторний алгоритм служить основою для наступних протоколів
􀂄 для протоколу маршрутної інформації (RIP)-одного з найбільш широко поширених протоколів IGP- типу, використовуючих як метрики лічильник вузлів;
􀂄 для протоколу маршрутизації внутрішнього шлюзу IGRP); корпорація Cisco розробила цей протокол для маршрутизаціі у великих гетерогенних мережах;
для вдосконаленого протоколу маршрутизації внутрішнього шлюзу
(EIGRP), що представляє поліпшену версію IGRP від ​​корпорації Cisco; цей протокол має виключно швидку конвергенцію, працює значно більше ефективно, ніж його попередник, і поєднує в собі всі переваги дистанційно- векторних алгоритмів і протоколів з урахуванням стану каналів.

43. Протоколи маршрутизації по стану каналів.

Маршрутизація на основі векторів відстаней використовувалася в мережі ARPANETаж до 1979 року, коли її змінив алгоритм маршрутизації з урахуванням стану ліній.Відмовитися від колишнього алгоритму довелося з двох причин. 1) Старий алгоритмпри виборі маршруту не враховував пропускну спроможність ліній. 2) Алгоритмзанадто довго приходив до стійкого стану (проблема рахунку до нескінченності).
В основі алгоритму маршрутизації з урахуванням стану ліній лежить проста ідея. Їїможна викласти у п'яти вимогах до маршрутизатора. Кожен маршрутизатор повинен:
1. Виявляти своїх сусідів і дізнаватися їх мережеві адреси.
2. Вимірювати затримку або вартість зв'язку з кожним зі своїх сусідів.
3. Створювати пакет, який містить всю зібрану інформацію.
4. Посилати цей пакет всім маршрутизаторам.
5. Обчислювати найкоротший шлях до всіх маршрутизаторам.
У результаті кожному маршрутизатору висилається повна топологія і всі вимірянізначення затримок. Після цього для виявлення найкоротшого шляху до кожногомаршрутизатора може застосовуватися алгоритм Дейкстри.

44. Механізм створення під мереж. Протокол OSPF.

Відкритий протокол пошуку найкоротшого шляху(OSPF)_використовує алгоритм маршрутизації за станом каналів. проблемна група
проектування Internet (IETF) розробила OSPF в 1988 році. Сама остання версія цього протоколу, OSPF версії 2, описана у специфікації RFC 2328. OSPF является протоколом IGP-типу, що означає, що він поширює маршрутну інформацію між маршрутизаторами, що знаходяться в єдиній автономній системі.
Протокол OSPF був розроблений для використання у великих мережах, в яких не можливе використання протоколу RIP.

45. Розбивання на під мережі класів А та В.

Процес розбиття на підмережі мереж класу А і В повністю аналогічний процедурі, виконуваної для мереж класу С, але все ж він трохи складніше,оскільки_використовується більша кількість бітів. Для використання у підмережах в мережі класу
А доступні 22 біта, у мережі класу В-24 бита.Запозичення 12-Ти бітів з вузлової частини адреси мережі класу В створює мережеву
маску 255.255.255.240, або в іншому позначенні- префікс / 28. Усі вісім бітів
третя октету були використані для створення маски, тому його значення дорівнює
255-Ти-максимальне значення восьми одиничних бітів. У четвертому октеті були використані тільки чотири біта, отже, його значення дорівнюватиме 240.
Слід пам'ятати, що маска підмережі являє собою суму запозичених бітів і фіксованих бітів мережевої частини адреси.
Запозичення 20-Ти бітів в адресі класу А для створення підмережі створює мережеву маску 255.255.255.240, або в іншому позначенні- префікс / 28. Усі вісім
бітів другого і третього октетів, а також 4 біта останнього октету в даному випадку
будуть рівні 1 і будуть належати масці підмережі.
У розглянутій ситуації на перший погляд може здатися, що маски для мереж класу А і В будуть абсолютно ідентичними. Тим не менш, не знаючи, для якої
мережі або, точніше, для мережі якого класу розрахована маска, неможливо сказати,
скільки насправді бітів було запозичено для створення підмережі.