Page 47 - 2577

інформації. Вибір топологічної структури здійснюється у відповідності з критерієм мінімуму
сумарної річної оренди каналів зв’язку при наявності обмежень на час затримки і надійність
передачі інформації. Вимога надійності враховується шляхом введення обмежень на
зв’язаність мережі (кількість незалежних маршрутів із вузла – джерела у вузол – адресат) і
кількість переприймань у маршруті (кількість проміжних вузлів комутації або концентрації).
Допускається кількість переприймань не більше двох і використовується принцип
двозв’язаності. У відповідності з цим принципом кожна пара джерело – адресат зв’язана
щонайменше двома шляхами, що не мають загальних вузлів. Це дозволяє, при виході вузла
або каналу з ладу, мережі зберігати працездатність.
Вихідні дані для топологічного проектування інформаційної мережі базуються на:
- техніко-економічних характеристиках вузлів комутації і концентрації інформації,
каналів і апаратури передачі даних;
- вимогах часу затримки надійності і достовірності;
- матриці потоків повідомлень від джерела до адресата;
- об’ємах інформаційних і службових повідомлень, що передаються мережею;
- залежності вартості оренди від довжини та пропускної здатності каналів.

3.3 Проектування топологічної структури мережі за критеріями вартості та
надійності

Розглянемо задачу, яка розв’язується на стадії проектування в умовах, коли відсутня
детальна інформація про мережеві протоколи, матриці інтенсивності вхідних потоків і т.д.
Нехай мережа подана у вигляді графа G 0(V,E 0) , де N  V – число вершин і M  E
0 0
– число ребер графа G 0. Розглянемо каркасний граф G(V,E) графа G 0, в якому N  V ,

M  E . Позначимо: D(G) – діаметр графа G, а D(G – e) і D(G – v) – діаметри графа G – е,
отриманого із графа G шляхом вилучення ребра е, і графа G – v, отриманого із графа G
шляхом вилучення довільної вершини. Всім ребрам графа G поставлені у відповідність
невід’ємні ваги, які дорівнюють вартості оренди каналів між парою вузлів комутації. Тоді під
вартістю графа G будемо розуміти суму ваг ребер, що входять до G. Цю суму позначимо
через С(G). Позначимо через Х множину всіх каркасних підграфів графа G 0.
Тоді задача синтезу топологічної структури комп’ютерної мережі полягає у
знаходженні такого підграфа G, що:

C  G  min C  G (3.1)
G X
при наступних умовах
D   dG  (3.2)
1
D G  e  d , для будь-якого ребра e E , (3.3)
2
V
D G v  d 2 , для будь-якої вершини x . (3.4)
Умови (3.2) – (3.4) обмежують максимальну довжину шляху між двома вузлами
(обмеження (3.2)); те саме, але при вилученні одної з вершин або одного із ребер (обмеження
(3.3) і (3.4)).
Алгоритм розв’язку задачі базується на розв’язку допоміжної задачі – отримання
нижньої межі вартості мережі.
Суть цієї допоміжної задачі в тому, що умови (3.2) – (3.4) не враховуються, а умова
двозв’язаності графа замінюється необхідною умовою
deg v V   2G  .
Вводиться нова умова, яка накладає обмеження на кількість ребер
 deg   v  2M .
v V G  
Таким чином, необхідно розв’язати таку допоміжну задачу:
44