Методика розрахунку надійності комп'ютерних мереж

Для аналізу структурної надійності мереж зручно використовувати матрично-топологічні методи. В їхній основі лежить подання мережі за допомогою графа мережі (рис.1). Комп'ютерну мережу можна представити як сукупність множини X={x1,x2, ...,x} вузлів і множини U={uij } з'єднуючі вузли xi і xj ребер.

рис.1 Граф мережі

Будемо використовувати наступні основні поняття і визначення. Множина всіх вузлів графа G, суміжних з деяким вузлом xi, називається оточенням вузла xi і позначається N(xi). Ступінь вузла графа дорівнює числу ребер, інцидентних даному вузлу. Будемо позначати ступінь вузла х через deg(x). Послідовність, вузлів і ребер x1, u1, x2, u2…,xl, ul, xl+1називається маршрутом, що з'єднує вузли xl і xl+1, або (xl, xl+1)-маршрутом. Очевидно, що маршрут можна задати послідовністю x1, x2, …,xl+1 його вузлів, а також послідовністю u1, u2, …, ul ребер. Сама непересічна впорядкована послідовність ребер з вузла xs у вузол xt називається шляхом. Число ребер, що утворюють шлях називається рангом шляху. Між будь-якими двома вузлами мережі можна побудувати, як правило, множину шляхів. Шляхи називаються незалежними, якщо в них немає загальних ребер. Якщо між будь-якими двома вузлами існує не менш k незалежних шляхів, то мережа називається k-зв'язковою. Перетином мережі будемо називати мінімальну сукупність ребер, видалення яких розділить мережу на дві підмережі. Кількість ребер перетину називається рангом перетину. Перетини називаються незалежними, якщо вони не містять ті самі ребра. Нехай P1l – деякий шлях виду x1, x2, …,xl у графі G, xi і xj – вхідні в нього вузли, i < j. Очевидно, що частина xi, xi+1,…,xj шляхи P1l, що починається у вузлі xi і закінчується в xj, сама є шляхом графа G. Цей шлях будемо називати (xi, xj) – фрагментом шляху P1l.

Через відсутність прийнятної моделі механізму втрат в мережі і властивій складності розрахунку мережної надійності використовуються часові моделі з дискретною ймовірністю. Тут ми розглянемо найбільш популярну модель. В ній передбачається, що мережні компоненти (вузли і ребра мовою графів) можуть приймати лише два стани: працює або не працює. Стан мережного компонента - випадкова величина, що не залежить від стану інших компонентів (в загальному випадку це може бути і не так). Постановка задачі обчислення надійності: для кожного компонента мережі задана ймовірність того, що він перебуває в робочому стані, і потрібно обчислити міру надійності мережі.

В цьому випадку як показник надійності мережі в цілому можна використовувати ймовірність настання складної події, що полягає у встановленні зв'язків між всіма вузлами із заданої множини, і розраховувати його як відношення суми зважених коефіцієнтів важливості ймовірностей з'єднань пари вузлів.

де H0 – показник надійності всієї мережі, Кi – коефіцієнт важливості i-го з'єднання вузлів (0 Ki 1), Hi – показник надійності i-го з'єднання вузлів.

При проектуванні реальних мереж звичайно відсутня необхідність точного розрахунку надійності мережі. Проектувальникам необхідно лише переконатися в тім, що надійність мережі, з одного боку, не нижче заданої та, з іншого боку, не має економічно необґрунтованого запасу. Інакше кажучи, на практиці досить гарантувати, що дійсне значення надійності H0 перебуває в деяких межах Нтin < Н0 < Нтах. Оцінка надійності мережі із заданою кінцевою точністю дозволить скоротити трудомісткість розрахунків в тим більшій мірі, чим нижче необхідна точність оцінки. Існує методика розрахунку оцінок надійності, причому нижня оцінка Hμ розраховується по сукупності всіх шляхів між вузлами, верхня ж Hσ – по сукупності перетинів. При розрахунку надійності по сукупності шляхів додавання кожного наступного шляху приводить до збільшення надійності, а при розрахунку по сукупності перетинів додавання кожного наступного перетину приводить до зменшення структурної надійності, що створює передумови для двосторонньої оцінки структурної надійності з гарантованою точністю по обмежених наборах шляхів і перетинів. Ця властивість дозволяє регулювати трудомісткість оцінок надійності залежно від заданої точності.

Дійсно, для вирішення задачі досить послідовно переглядати шляхи μ, поки не виконається умова Hμ(m) ≥ Hmin і потім переглядати перетини σ, поки не виконається умова Hσ(r) ≤ Hmax. Тут m, r – число шляхів і перетинів відповідно. Якщо для деякого т виявиться, що Hμ(m) > Hmax, то можна припинити розрахунки і прийняти рішення, що в мережі закладена зайва надмірність, а якщо для деякого r виявиться, що Hσ(r) < Hmin , то це значить, що вимоги до надійності мережі не виконуються. Кількість потребуючого перегляду шляхів т і перетинів r звичайно набагато менше загального числа шляхів n і загального числа перетинів k графа, чим і досягається скорочення трудомісткості оцінки. Одночасно гарантується, що значення показника надійності мережі лежить в заданих межах Hμ(m) < H0 < Hσ(r) .

В такий спосіб для виконання розрахунків необхідний список всіх можливих шляхів і перетинів між заданими вузлами xa і xb. З літератури відомо, що шукана надійність з'єднання Нab залежить від надійності кожного шляху і варіантів їхніх перетинів по загальних ребрах. Якщо враховувати тільки незалежні шляхи, то трудомісткість обчислень значно скорочується. Аналогічна ситуація з незалежними перетинами. Нехай надійність j-го ребра i-го шляху - . Тоді надійність i-го шляху буде дорівнювати:

де mi -ранг шляху.

Якщо всі шляхи незалежні, то ймовірність зв’язності вузлів xa і xb по множині незалежних шляхів можна визначити як

де n – кількість незалежних шляхів між xa і xb.

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

Міркуючи аналогічно, неважко встановити, що для збільшення точності верхньої оцінки ймовірності зв’язаності вузлів по множині незалежних перетинів потрібно максимізувати число незалежних перетинів при мінімізації їхніх рангів. Проблема мережної надійності досліджується досить давно. В цей час ясно, що точного рішення навіть для мереж обмеженого розміру ця задача не має. Але можна вже сьогодні, якщо потрібно, зробити оцінку надійності зверху і знизу. Треба, втім, мати на увазі, що навіть це вимагає досить складних розрахунків.