Page 24 - 2577

Таблиця 2.3 – Вибір маршруту мінімальної вартості за допомогою алгоритму
1
Беллмана-Форда для рис. 2.4 (s  )

h L h  2 Шлях L h  3 Шлях

0  -  -
1 2 1 – 2 5 1 – 3
2 2 1 – 2 4 1 – 4 – 3
3 2 1 – 2 3 1 – 4 – 5 – 3
4 2 1 – 2 3 1 – 4 – 5 – 3

продовження табл. 2.3
L  4 Шлях L  5 Шлях L  6 Шлях
h h h
 -  -  -
1 1 – 4  -  -
1 1 – 4 2 1 – 4 – 5 10 1 – 3 – 6
1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 - 6
1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 - 6

Така схема маршрутизації спричиняє лавоподібне зростання кількості пакетів у
мережі. Щоб запобігти цьому явищу, використовують такі процедури.
1. Запам’ятовування на кожному вузлі ідентифікаторів вже ретрансльованих пакетів.
Коли будуть надходити копії повторних пакетів, то вони будуть анульовані.
1. Включення у кожний пакет лічильника переходів. Цьому лічильнику присвоюється
певний порядковий номер, наприклад діаметр мережі ( довжина найдовшого маршруту з
мінімальним числом переходів). Кожного разу, коли вузол передає пакет, це значення
зменшується на одиницю. Коли воно досягне нуля пакет буде анулюваний.
Переваги:
- висока живучість, що дозволяє застосовувати такі мережі, наприклад, у воєнній
справі.
Недоліки:
*
- великий обсяг трафіка, який прямо пропорційний зв’язності мережі .
На практиці частіше застосовується варіант даного алгоритму під назвою
вибіркова заливка. У цьому алгоритмі вузли посилають пакети не по всіх лініях, а тільки по
тих, які йдуть приблизно в потрібному напрямку. Навряд чи є сенс посилати пакет, що
прямує на захід, по лінії, що йде на схід, якщо тільки топологія мережі не є лабіринтом і
маршрутизатор не знає про це.
Стохастична маршрутизація. При стохастичній апроксимації кожний вузол для
ретрансляції пакетів вибирає випадковим чином тільки один вихідний канал крім того, по
якому прибув цей пакет. Ймовірність вибору каналу визначається виразом
R
P i  i ,
 R j

j
де R - швидкість передачі даних по i - тому каналу.
i
Як і лавинна, випадкова маршрутизація не використовує інформацію про мережу.
Оскільки вибір маршруту відбувається випадково, то фактично вибраний маршрут, як
правило, не буде мати ні мінімального числа переходів, ні мінімальної вартості.
Недолік:

*
Мережа (граф) є зв’язними тоді і тільки тоді, коли між двома її вузлами (вершинами) існує простий шлях.
21