Page 41 - 2577

N N
1     1   f
T      kl kl
 2 d     1  f
k  l1 1 kl kl kl
при умові виконання обмеження
f  d , k, l 1 , N .
kl kl
К19. Обчислити:
N N
1 f kl
T  :    .
new 2
 k  l1 1 d kl  f kl
К20. Якщо T T   , то перейти до К11.
old new
Інакше:

1) Включити найкоротший шлях  0 в множину  :  0   ;
0 i 0 j i 0 j 0 0 i 0 j 0 i 0 j
2)    k ,l 0 :   j 0 :   j 0 ;
0 i 0 j kl kl
3) покласти: T  T ;   1 :   2 ;
old new
4) якщо   1  g , то перейти до кроку 7; інакше до К9.

Контрольні питання та завдання

1. Дайте визначення алгоритму маршрутизації.
1. Яка різниця між дейтаграмною передачею і віртуальним з'єднанням?
2. Чи впливає вибір алгоритму маршрутизації на пропускну здатність каналу зв’язку?
3. Дайте класифікацію алгоритмів маршрутизації, які орієнтовані на топологію
мережі.
4. Які критерії ефективності покладені в основу алгоритмів маршрутизації,
орієнтованих на топологію мережі?
5. Використовуючи табл. 2.1, знайдіть маршрут для пакета, який відправлений із вузла
2 до вузла 4.
7. Для комп’ютерної мережі, яка показана на рис. 2.4, знайти оптимальний маршрут
для пакета від вузла 2 до вузла 5, використавши алгоритм Дейкстри.
8. Для комп’ютерної мережі, яка показана на рис. 2.4, знайти оптимальний маршрут
для пакета від вузла 2 до вузла 5, використавши алгоритм Беллмана-Форда.
9. Які переваги і недоліки притаманні лавинній маршрутизації?
10. Яким чином вибирається канал для чергового пакета в алгоритмі випадкової
маршрутизації?
11. Який канал буде обрано вузлом 3 (рис. 2.4) для відправки чергового пакета, якщо
на поточний момент часу його стан характеризується такою табл.:

Наступний Пріоритет Довжина
вузол черги
2 0 7
4 8 1
5 6 2
6 3 5

11. Як здійснює вибір маршруту розподілений адаптивний алгоритм?
12. Виведіть формулу для середнього часу перебування повідомлення в комп’ютерній
мережі.
13. Дайте класифікацію задач маршрутизації, орієнтованих на трафік мережі.
14. Яка відмінність між віртуальною і К-шляховою маршрутизаціями?

38