Page 27 - 2577

затримок і посилає його копію всім сусіднім вузлам, включаючи й вузол 1. Вузол 1 очищує
свою поточну таблицю маршрутів і будує нову. Необхідно знайти оновлену таблицю для
вузла 1 (табл.2.5).
Знайдемо d , тобто k  , а j  . Множину A утворюють сусідні вузли з вузлом 1 –
2
1
12
A  2 3 4; ;  . Отже,
d  min d  l  min d  l ;d  l ;d  l  min 0 4 ; 2  2 ; 5  1  2 .
12 2 i 1i 22 12 32 13 42 14
 i  3;2  4 ;  i  3;2  4 ;  i  3;2  4 ;
2
Оскільки останній вираз мінімізує перший член, коли i  , то s  . Отримані
2
12
1
значення d і s заносимо у табл. 2.4. Тепер знайдемо d - k  , j  .
3
12 12 13
d  min d  l  min d  l ;d  l ;d  l  min 3 0 ; 2  2 ; 5  1  3 .
13 3 i 1i 23 12 33 13 43 14
 i  3;2  4 ;  i  3;2  4 ;  i  3;2  4 ;
Мінімальне значення виразу, що знаходиться у квадратних дужках досягнуто при
значенні i  , тобто s  .
4
4
13

Таблиця 2.5 – Розподілений алгоритм маршрутизації для вузла 1
Таблиця маршрутів вузла 1 перед Вектори Таблиця маршрутів вузла 1 після
обновленням затримок, які обновлення
передаються на Наступ-
Затримка Наступний вузол 1 Затримка ний
Вузол Вузол
d ij вузол s ki=i сусідніми d ij вузол
призна- вузлами призначенн s ki=i
чення і я і
D S D D D D S
1 1 2 3 4 1 1
1 0 - 3 7 5 1 0 -
2 2 2 0 4 2 2 2 2
3 5 3 3 0 2 3 3 4
4 1 4 2 2 0 4 1 4
5 6 3 3 1 1 5 2 4
6 10 3 5 3 3 6 4 4

Аналогічно знайдемо значення d , d , d і s , s , s :
14 15 16 14 15 16
d  min d  l  min d  l ;d  l ;d  l  min 2 2 ; 2  0 ; 5  1  1 ,
14 4 i 1i 24 12 34 13 44 14
 i  3;2  4 ;  i  3;2  4 ;  i  3;2  4 ;
s  4 ;
14
4
d  min d  l  min d  l ;d  l ;d  l  min 3 1 ; 2  1 ; 5  1  2 , s  ;
15 5 i 1i 25 12 35 13 45 14 15
 i  3;2  4 ;  i  3;2  4 ;  i  3;2  4 ;
d  min d  l  min d  l ;d  l ;d  l  min 5 3 ; 2  3 ; 5  1  4 ,
16 6 i 1i 26 12 36 13 46 14
 i  3;2  4 ;  i  3;2  4 ;  i  3;2  4 ;
s  4.
16
Відмітимо, що оцінка затримки каналу – довжина черги у цьому каналі. Таким
чином, при побудові нової таблиці маршрутів отримуємо канали з коротшими чергами. Це
приводить до вирівнювання навантаження на вихідних каналах.
Розподілений адаптивний алгоритм маршрутизації має такі недоліки:
- алгоритм не враховує швидкість передачі по лінії, а лише довжину черги. Тому
канали з високою пропускною здатністю не отримували пріоритет, який вони
повинні були б мати;
- довжина черги не є адекватною мірою затримки, оскільки від прибуття пакета на
вузол до його розміщення у поточній черзі протікає деякий непостійний час
зв’язаний з обробкою пакета.
- алгоритм не достатньо ефективний. Зокрема, він повільно реагує на зміну
навантаження у мережі.

24