Page 26 - 2577

затримки і відмови на кожному доступному їм вузлі. На основі отриманої інформації вузол
оцінює ситуацію із затримками у всій мережі і застосовує алгоритм мінімальної вартості. У
випадку централізованої маршрутизації кожний вузол повідомляє про затримки у своїх
каналах центральному вузлу, який синтезує маршрути на базі цієї інформації і відсилає
відомості про маршрути назад на вузли.
Розподілений адаптивний алгоритм маршрутизації був розроблений для мережі
ARPANET, де як критерій ефективної оцінки затримки використовувався алгоритм
Беллмана-Форда. При цьому алгоритмі на кожному вузлі зберігається два вектори:
 d i1   s i1 
 d   s 
D   i2  ; S   i2  ,
i i
 ...   ... 
   
d
s
 iN   iN 
де D - вектор затримок для вузла i ;
i
d - поточна оцінка мінімальної затримки від вузла i до вузла j ( d  );
0
ij ii
N - число вузлів у мережі;
S - вектор наступних вузлів для вузла i ;
i
s - наступний вузол на поточному маршруті з мінімальною затримкою від вузла
ij
i до
вузла j .
Періодично кожний вузол передає свій вектор затримок кожному сусідньому вузлу.
На основі всіх отриманих векторів затримок вузол k модифікує обидва своїх вектори
наступним чином:
d  min d   l  ,
kj  ij ki 
i A
i
s  , при цьому значення i мінімізує вираз min d   l  .
ki  ij ki 
i A
де A - множина сусідніх вузлів для k ;
l - поточна оцінка затримки від k до i .
ki
Приклад 2.3. На рис. 2.6 показана комп'ютерна мережа, а у табл. 2.5 наведені
маршрути для вузла 1 у момент часу, який відповідає значенням вартостей на рис. 2.5.
Для кожного вузла призначення вказані затримки і наступний вузол на маршруті,
який здійснює цю затримку. У деякий момент часу вартості каналів набудуть нові значення,
як це показано у табл. 2.4.

Рисунок 2.6 – Комп'ютерна мережа до прикладу 2.4

Порівнюючи рис. 2.4 з рис. 2.6, видно, що в мережі відбулися зміни. Про ці зміни
вузол 1 повідомляє сусідні вузли 2, 3, 3. Кожний із цих вузлів модифікує свій вектор
23