Page 28 - 2577

Роботу алгоритму можна покращити, якщо мірою затримки використовувати не
довжину черги, а величину, яка обчислюється за виразом:
[затримка]=[час відправлення]+[час передачі]+[час на затримку розповсюдження] –
[час прибуття].
Обчислення затримки відбувається у такий спосіб. На вузлі кожний вхідний пакет
дістає відмітку про час прибуття. Коли пакет передається, записується час відправлення.
Якщо повертається позитивне підтвердження, обчислюється затримка для поточного пакета.
Отже, вузол повинен знати швидкість передачі даних у каналі і час розповсюдження. За
певний час (у мережі ARPANET цей час складає 10 с) вузол обчислює середній час затримки.
Якщо у затримці виявляються суттєві змін, то інформація передається іншим вузлам з
використанням лавинної маршрутизації. Так що кожний вузол вміщує дані оцінки затримки
у кожному каналі мережі. Коли прибуває нова інформація, то вузол перебудовує свою
маршрутну таблицю, використовуючи алгоритм Дейкстри.

2.2.2 Оптимальні алгоритми маршрутизації орієнтовані на трафік

Постановка задачі
Розглянемо модель мережі передачі даних (МПД), яка складається із N вузлів
комунікації і М ліній зв`язку. Зробимо такі допущення:
- всі лінії зв`язку абсолютно надійні;
- у лініях зв`язку відсутні шуми;
- вузли комунікації мають нескінченну ємність;
- пакети у вузлах комунікації обновлюються миттєво;
- довжини всіх повідомлень незалежні і розподілені за показниковим законом
P  t 1  e  t  ; де μ– інтенсивність поступлення повідомлень; 1 - середня

довжина повідомлення в байтах;
- трафік, який поступає в мережу, складається із повідомлень, які мають
однаковий пріоритет, і утворюють пуасоновський потік
k
 u ij  u
(  uP  e ij , k  ;0 k  x t u  x ; k - кількість повідомлень, які поступили
u
k!
за інтервал часу u ) зі середнім значенням  [повідомлень/с]; де x - кількість
ij t
повідомлень, що поступили на момент часу t. Величина  означає інтенсивність
ij
потоку від вузла і до вузла j;
2
- кожна лінія зв'язку складається із єдиного дуплексного каналу зв`язку з
пропускною здатністю d (біт /с) ((k,l) – лінія зв`язку між вузлами k і l); якщо
kl
лінія зв`язку між вузлами k і l відсутня, то d =0.
kl
Позначимо через  повний зовнішній трафік. Очевидно, що
N N
   ij
 . (2.1)
 i 1  j 1
 ji,
Долю потоку  , яка проходить лінією (k,l), позначимо через x kl  . Природно, що
ij
0  x  , ji  1. (2.2)
kl
Тоді величина потоку  в лінії (k,l), яка зумовлена потоком  , буде дорівнювати
ij
kl
(рис. 2.6)

2
дуплексний зв`язок – двосторонній зв’зок між 2 пунктами, при якому в кожному із них передача і
прийом повідомлень можуть вестись одночасно.

25