Page 31 - 2577
P. 31
l,1 i
N N
x i, ( j) x i, ( j) 0 l , i, j (2.14)
kl lk
k 1 k 1 l , 1 j.
0 x kl , (i ) j , 1 i , j ,k ,l , 1 . N (2.15)
Вихідні дані для розв'язку задачі вибору оптимального маршруту:
Для розв'язку сформованої задачі (2.11)-(2.15) необхідно мати такі вихідні дані:
- топологічну структуру мережі;
- матрицю вхідних потоків f
kl
N
- пропускну здатність ліній зв'язку – матриця D d kl 1 ;
1
- середню довжину повідомлень - , байт.
Задача (2.11) – (2.15) називається задачею вибору оптимальних потоків і
визначення оптимальних маршрутів в мережі передачі даних за критерієм середньої
затримки.
Класифікація задач оптимальної маршрутизації
Обмеження (2.15) допускає, що для передачі повідомлень із вузла і у вузол j може
бути використано більше, ніж один маршрут, тобто задача (2.11) – (2.15) зумовлює
альтернативну процедуру вибору маршрутів.
Якщо умову (2.15) заміни на умову
x kl , (i ) j ,,1,0 i j ,k ,l , 1 N , (2.15а)
то задача (2.11) – (2.14) вкупі з (2.15а) буде визначати фіксовану маршрутизацію.
Частковим випадком альтернативної маршрутизації (дейтаграмної) є маршрутизація з
обмеженням на число вхідних ліній К, які використовуються для передачі даних із кожного
вузла до вузла – адресата. Тому маршрутизацію називають К - шляховою . Для опису такої
задачі вводять додаткове обмеження. Введемо додаткову змінну
N i, ( j)
x
, 1 якщо kl 0
(
kl j) i 1 (2.16)
N
, 0 якщо x i, ( j) ,0 j, k, l N.,1
kl
i 1
(
Іншими словами, змінна kl ) j 1, якщо лінія (k, l) використовується для передачі
потока у вузол–адресат j хоча б від одного вузла-джерела і дорівнює нулю в протилежному
випадку.
Тоді обмеження на число вихідних ліній К, які використовуються для передачі даних
із кожного вузла k вузлу-адресату j (рис 2.7) можна записати в наступному вигляді:
N
kl ( ) j K , k , j , 1 N . (2.17)
l 1
Таким чином, задача (2.11) – (2.17) описує К – шляхову маршрутизацію. Слід
відмітити, якщо в (2.17) покласти К=1, то прийдемо до обмеження (2.15а), що є цілком
природним.
28
