Постановка задачі синтезу багатозв’язної мережі

Розглянуті вище мережеві топології (дерево, зірка, кільце) є базовими, їх оптимальний синтез здійснюється на першому етапі проектування телекомунікаційних мереж. На другому етапі в базову мережу додаються лінії зв’язку для виконання певних обмежень (наприклад, для збільшення надійності або зменшення кількості транзитних вузлів, тощо). Отримані мережі є багатозв’язними (кількість маршрутів між будь-якою парою вузлів перевищує 2). Додаються, як правило, дуги мінімальної вартості, що не увійшли в базову мережу.

Крім визначення топології, при проектуванні телекомунікаційної мережі слід висунути вимоги до її обладнання, для чого треба визначити необхідну пропускну здатність каналів зв’язку. Це здійснюється через розрахунок матриці міжвузлових трафіків мережі. Основою для такого розрахунку є матрицяінформаційних тяжінь – потреб у зв’язку для будь-якої пари вузлів.

Отже задача синтезу багатозв’язної мережі може бути сформульована наступним чином:

для множини вузлів, що задана матрицею відстаней та матрицеюінформаційних тяжінь, побудувати телекомунікаційну мережу, що забезпечує необхідний трафік та відповідає висунутим умовам та обмеженням.

Розглянемо послідовність дій для синтезу багатозв’язної мережі з обмеженням на число транзитних вузлів між будь-якою парою вузлів мережі (на кількість “переприйомів”).