Головна

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

  1. А) Основні алгоритмічні конструкції. Базові алгоритми.
  2. алгоритми
  3. Алгоритми вибору маршрутів для мобільних хостів.
  4. Алгоритми заміщення сторінок
  5. Алгоритми і структура нечітких регуляторів
  6. Алгоритми обробки одновимірних числових масивів

Протоколи цього виду служать для збору інформації про топологію міжмережевих з'єднань. Завдання маршрутизації (підбору оптимального маршруту) вирішується на основі аналізу таблиць маршрутизації, розміщених у всіх маршрутизаторах і кінцевих вузлах мережі. Для автоматичної побудови таблиць маршрутизації маршрутизатори обмінюються інформацією про топологію складовою мережі відповідно до спеціального службовим протоколом. Протоколи цього типу називаються протоколами маршрутизації (або маршрутизуючого протоколами). Протоколи маршрутизації (наприклад, RIP, OSPF, NLSP) слід відрізняти від власне мережевих протоколів (наприклад, IP, IPX). І ті й інші виконують функції мережевого рівня моделі OSI - беруть участь в доставці пакетів адресату через різнорідну складену мережу. Але в той час як перші збирають і передають по мережі чисто службову інформацію, другі призначені для передачі призначених для користувача даних, як це роблять протоколи канального рівня. Протоколи маршрутизації використовують мережеві протоколи як транспортний засіб. При обміні маршрутної інформацією пакети протоколу маршрутизації поміщаються в поле даних пакетів мережевого рівня або навіть транспортного рівня, тому з точки зору вкладеності пакетів протоколи маршрутизації формально варто було б віднести до більш високого рівня, ніж мережевий. За допомогою протоколів маршрутизації маршрутизатори складають карту зв'язків мережі тій чи іншій мірі подробиці. На підставі цієї інформації для кожного номера мережі приймається рішення про те, якому наступному маршрутизатору треба передавати пакети, що направляються в цю мережу, щоб маршрут виявився раціональним. Результати цих рішень заносяться в таблицю маршрутизації. При зміні конфігурації мережі деякі записи в таблиці стають недійсними. У таких випадках пакети, відправлені за помилковими маршрутами, можуть зациклюватися і губитися. Від того, наскільки швидко протокол маршрутизації приводить у відповідність вміст таблиці реальному стану мережі, залежить якість роботи всієї мережі. Протоколи маршрутизації можуть бути побудовані на основі різних алгоритмів, що відрізняються способами побудови таблиць маршрутизації, способами вибору найкращого маршруту і іншими особливостями своєї роботи. алгоритми:

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

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

19. Методи доступу: СДПС, ССДПС, СДПН, естафетний доступ.

1.Вільний доступ з перевіркою зіткнень (СДПС). Цей спосіб найбільш широко застосовується в магістральних структурах. Система захоплює канал і починає передачу в будь-який момент часу. Оскільки централізоване управління відсутня, дві і більше системи можуть вести передачу пакетів одночасно. В цьому випадку відбувається зіткнення - інтерференція пакетів, переданих одночасно, в результаті чого всі передані пакети спотворюються. Зіткнення виявляються шляхом прийому кожної системою переданого нею пакета (рис. 6.8). При цьому біти, що передаються в канал, порівнюються з битами, прийнятими з каналу. Якщо реєструється розбіжність переданого і прийнятого біта, це свідчить про зіткнення пакетів в каналі. При виявленні зіткнення система припиняє передачу пакета і повторює передачу через деякий час. Для того щоб зменшити ймовірність повторних зіткнень, кожна система починає повторну передачу через випадковий проміжок часу з досить великим середнім значенням t. Затримка передачі формується як випадкова величина, рівномірно розподілена в інтервалі, де Тmax - максимальна затримка повторної передачі.

Через сутички реальна пропускна здатність моноканала виявляється менше номінальної пропускної здатності фізичного каналу. З метою спрощення математичних виразів пропускні спроможності оцінюють числом пакетів, переданих за час Т, достатню для передачі одного пакета з фізичного каналу. Час передачі одного, пакета з фізичного каналу Т називають вікном ,. Вікно T = L [V, де L - довжина пакета (точніше, кадру), біт, і V - пропускна здатність фізичного каналу, біт / с. З урахуванням сказаного пропускна здатність моноканала S характеризується середнім числом пакетів, переданих в одному вікні. Очевидно, що .

Пропускна здатність моноканала при СДПС оцінюється наступним чином. Зіткнення виключаються, якщо протягом періоду 2Т, званого періодом уразливості, передається тільки один пакет (рис. 6,9). Якщо протягом періоду уразливості передаватиметься ще один пакет, який починається або в першому вікні, або в другому, відбувається зіткнення. Для найбільш простий оцінки припустимо, що потік запитів на передачу створюється нескінченним числом систем, що працюють незалежно один від одного і в результаті цього породжують пуассоновский потік запитів з сумарною інтенсивністю G запитів на одне вікно. Імовірність передачі пакета без зіткнення визначається ймовірністю надходження в період уразливості тільки одного пакета і дорівнює. Отже, тільки g-я частина пакетів буде передана без спотворень і інтенсивність потоку неспотворених пакетів.

Значення S характеризує пропускну здатність моноканала, залежність якої від інтенсивності потоку запитів G представлена ??на рис. 6.10 кривої СДПС. Максимум пропускної здатності досягається при G = 0,5 запитів на вікно і становить

пакету на одне вікно.

Таким чином, СДПС дозволяє використовувати для передачі даних не більше 18,4% пропускної здатності каналу.

При кінцевому числі систем М пропускна здатність моноканала:

2. синхронний вільний доступ з перевіркою зіткнень.

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

3. Вільний доступ з перевіркою несучої.

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

Якщо канал вільний, станція починає передачу пакетів; якщо канал зайнятий, передача відкладається і система чекає деякий час (t = Т / 2) потім знову слухає моноканал і т. д. В результаті такого способу передачі, ймовірність зіткнення істотно нижче і збільшується ступінь пропускної здатності фізичного каналу.

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

4. естафетний доступ.

СА підключені до каналу пов'язані один з одним кільцевої зв'язком, по якій між адаптерами передається естафета в якості якої виступає сигнал, що дозволяє доступ до каналу зв'язку. Естафета передається в наступний адаптер по закінченню передачі пакета попереднього. Якщо ж пакета на передачу немає, то естафета передається наступному адаптера негайно.

При естафетному доступі майже повністю використовується пропускна здатність фізичного каналу. Час доставки не перевищує N * T, де N - число активних систем ЛЗ, T - час передачі кадру. У такій мережі всі системи знаходяться в однакових умови і отримують дозвіл на передачу кадрів в моноканал з частотою не нижче 1 / N * T. Як естафети використовується спеціальний маркер, який передається від однієї СА до іншого по кільцю.



КВИТОК № 8 | Технологія Token Ring. Технологія FDDI.

Технологія 100VG-AnyLAN. | Стільникові системи зв'язку. Принцип роботи GSM мереж. | Принцип роботи CDMA мереж. | Кодування. Цифрове і логічне кодування. | Аналогові канали передачі даних. Способи модуляції. Модеми. | Цифрові канали передачі даних і технології xDSL. | Стандарт Fast Ethernet. Технологія Gigabit Ethernet і 10Gigabit Ethernet. | Технологія WiMAX. Стандарт UWB. | Стандарт ZigBee. | Мережева трансляція адрес (NAT). |

© um.co.ua - учбові матеріали та реферати