Dovhenko protection of networks

Надійність комп'ютерних мереж

Перш ніж переходити до теоретичної частини, подивимося, що можна зробити для поліпшення надійності мережі з практичної точки зору. Звичайно, цьому сприятиме використання RAID-систем жорстких дисків, катастрофостійкої системи дублювання резервних копій дисків у віддалених вузлах, розміщених у різних будівлях, тощо. Але не слід знімати з рахунку дублювання базових серверів: DNS, NTP (якщо вони потрібні), поштових серверів, серверів баз даних та ін. Всередині локальної мережі підвищенню надійності може сприяти застосування протоколу STP, що може автоматично забезпечити обхід відмовившої ділянки LAN (якщо застосування динамічного протоколу внутрішньої маршрутизації неможливо або небажано, наприклад, з міркувань безпеки). У багатьох випадках украй важливо задублювати шлюз мережі, що веде в Інтернет, тому що його відмова залишить усіх користувачів мережі без зв'язку. Компанія CISCO і багато інших фірм розробили протоколи резервування маршрутизаторів. У цих протоколах два або більше пристроїв спільно використовують віртуальні IP й Мас-адреси, які зазначені в мережевому сегменті для шлюзу за замовчуванням. Для реалізації такої схеми існує три протоколи:

   * HSRP (Hot Standby Router Protocol - протокол гарячого резервування маршрутизаторів) компанії CISCO; 
   * IPSTB (IP Standby Protocol) компанії DEC;
   * VIRP (Virtual Router Redundancy Protocol) - протокол надлишкового віртуального маршрутизатора). 

Компанія CISCO підтримує тільки протокол HSRP. У цьому протоколі один з маршрутизаторів є основним (primary), а другий - резервним (standby). Після введення цього протоколу в дію всі запити і весь трафік шлюзу обслуговуються основним маршрутизатором. Дублюючий маршрутизатор залишається пасивним до виходу з ладу основного (рішення не найдешевше, якщо врахувати вартість маршрутизатора, навіть якщо дублюючий прилад простіше і дешевше основного).

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

Вихід з ладу робочої станції (термінальний вузол) створює проблеми її користувачеві, решта користувачів Інтернет, швидше за все, цього не помітять, але відмова сервера позначиться на роботі всіх його клієнтів, в тому числі і віддалених. Вихід же з ладу маршрутизатора (якщо це транзитний вузол) може вплинути на роботу цілого регіону. Звідси видно, що окремі вузли можуть по-різному впливати на роботу мережі в цілому. Навіть у класі серверів можна виділити групи різного впливу на рівень надійності. Наприклад, відмова сервера IN-ADDR.ARPA практично паралізує роботу всіх програм traceroute. Ще гірший вплив надасть вихід з ладу регіонального DNS-сервера. Саме з цієї причини такі сервери зазвичай дублюються (навіть у локальних мережах). Існують і інші сервери, які впливають на реалізацію певних мережевих функцій (поштові сервери, сервери баз даних в системах платежів, сервери центрів сертифікації та ін.) Очевидно, що вплив на надійність мережі може надавати не тільки устаткування або ОС, але і прикладні програми.Якщо користувач не може отримати доступ до певного мережного ресурсу, це дуже часто пов'язане не з відмовою обладнання або програми, а просто з перевантаженням однієї з ділянок мережі по дорозі до зазначеного ресурсу (некомпетентність користувача в даному аналізі не розглядається).

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

перш ніж писати і запускати програму розрахунку надійності мережі треба навчитися оцінювати: а чи вистачить наявних обчислювальних ресурсів для вирішення поставленого завдання в поточному тисячолітті. Для цього існує математичні методи оцінки складності алгоритмів [А. V. AHO, J. D. Ullman, "Foundation of Computer Science", Computer Science Press, 1992, або VV Leeuwen, "Algorithms and Complexity", The MIT Cambridge, Massachusetts, Elsevier Science Publishers, 1990]. Через складність прямих обчислень багато дослідників обмежуються лише оцінкою можливих меж надійності. На практиці, навіть використовують самі продуктивні обчислювальні системи, можна оцінити надійність мережі з обмеженим числом вузлів. Для великих мереж доступними є лише оцінки нижній або верхньої межі надійності.

За відправну точку приймемо мережу G = (V, E), в якій V - набір вузлів або вершин графа мережі, а Е - набір неорієнтованих ребер або набір орієнтованих дуг. Більшість досліджень з мережевої надійності присвячені де-термінальним заходам. Нехай є набір з К вузлів і вузол sєK (k =|K|). Задана мережа G, і всі дуги графа, що описує мережу, мають ймовірність надійності р. Тоді де-термінальна міра надійності визначається як (Pr - ймовірність):

Rel(G,s,K,p) = Pr [існує хоча б один працюючий шлях від s до кожного вузла з набору k]

Основною метою досліджень в галузі мережевої надійності є прагнення розробити методи для інженерів-проектувальників, що спрощують проектування мереж, які вимагають підвищеної надійності. В ідеалі, бажано сформувати моделі проектування мереж та алгоритми, які використовують в якості вхідних даних характеристики мережевих компонентів, а також критерії проектування, і видають на виході оптимальну структуру мережі. Так як точні вирази для надійності мережі дуже складні, в моделях для проектування мереж замість явних виразів надійності використовуються замінники. У цьому розділі ми розглядаємо проблему аналізу заходів мережевої надійності. Різні моделі дослідження застосовуються спільно з процедурами проектування мережі. Якщо значення заходів надійності виявиться незадовільним, то слід змінити вхідні параметри проектної моделі. В іншому випадку, проектувальник може вручну скоригувати схему мережі. Коли одним з вищезгаданих методів отримана чергова топологія мережі, обчислюється нове значення заходів мережевої надійності. Побудувавши, таким чином, ітераційний процес, ми доб'ємося відповідності між знов отриманим та бажаним значенням заходів мережевої надійності.

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

Області застосування

Мережі з комутацією пакетів, рівень опорної мережі

Перші мережі з комутацією пакетів були розроблені в 1960-х роках. Їх створили з метою поділити високошвидкісні канали між великою кількістю користувачів. Трафік, породжуваний одним користувачем, має багато сплесків і пауз. Трафік декількох користувачів можна динамічно рознести за часом і передавати по одному з'єднанню. ARPANET була першою великою мережею з комутацією пакетів. Велика частина досліджень в галузі мережевої надійності до і після 1970 велася саме для ARPANET. Надійність ARPANET в основному розглядалася з точки зору пов'язаності мережі. Вважалося, що мережа функціонує, якщо вона залишається пов'язаної, тобто поки кожен з користувачів специфікованого субнабора пов'язаний один з одним. Такий підхід був виправданий, тому що в ARPANET використовувалася динамічна маршрутизація, так що дані могли бути спрямовані в обхід вузлів які відмовили. Хоча існувала можливість транспортування даних за іншим маршрутом, в мережі могли виникнути перевантаження і затримки, викликані падінням загальної пропускної здатності мережі.

При порівнянні ARPANET з комерційними опорними мережами з комутацією пакетів, що використовуються в 1980-х роках, такими, як Telnet і Tymnet, ясно, що комерційні мережі є на богато компактнішими. Як наслідок, імовірність порушення зв'язаності в комерційних мережах багато менше, але, як правило, завантаження каналів там досить висока. Звідси напрошується висновок, що слід більш детально обчислювати параметри мережевої надійності і враховувати перевантаження і пропускну здатність мережі. Будемо вважати, що мережа працездатна, якщо вона пов'язана і параметри мережевої працездатності, якими можуть бути середні затримки, не перевищують заданих меж.

Сьогодні мережа ArpaNet може здатися топологічно досить простою, але навіть для такої мережі розрахунок надійності аж ніяк не просте завдання навіть при оцінці простоти зв'язності.

Для того щоб мінімізувати перебір, можна використовувати різні методи еквівалентного перетворення графа мережі, мiнiмiзуючи число вузлів або ребер при збереженні значення надійності.

Опорний рівень в мережах з комутацією каналів

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

Зв'язкові мережі

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

Локальні оптоволоконні мережі для передачі голосу

Оптичні кабелі - одне з останніх досягнень сучасної технології. Телекомунікаційні мережі всього світу переводяться на використання цієї техніки (дивись, наприклад, T. Flanagan, "Fiber Network Survivability" IEEE Communication Magazine 28 (1990) 46-53). Основною перевагою оптичного середовища передачі в порівнянні з передачею по мідних кабелях є істотне зростання пропускної спроможності та зниження рівня шумів. Саме з цієї причини багато телефонних мереж загального користування здійснюють швидкий перехід на оптику. Як, проте, виявилося, у проблематиці надійності мереж існують більш важливі проблеми, і саме їх потрібно вивчати. А саме: пропускна здатність оптоволоконних мереж надзвичайно висока, тому структура таких мереж, на відміну від звичайних, має більш розподілений характер. Старі мережі були більш розгалуженими і мали велике число зв'язків, питання мережевої надійності стояло не так гостро. При проектуванні сучасних мереж слід серйозно поставитися до проблеми мережевий надійності, тому що перебої в роботі навіть одного з оптичних каналів можуть викликати розрив мережі.

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

Архітектури перемикачів і комп'ютерів, стійкі до збоїв

Комп'ютерна система називається стійкою до збоїв, якщо при відмові одного з її компонентів вона продовжує функціонувати. У 1970-х роках такі комп'ютери використовувалися як перемикачі в опорних телекомунікаційних мережах. І сьогодні вони широко застосовуються у багатьох додатках. Пізніше були розроблені паралельні обчислювальні архітектури. З метою підвищення продуктивності паралельні ЕОМ збиралися з безлічі однотипних елементів. Однак паралельні архітектури мають також і підвищені характеристики надійності. Зазвичай такі відмовостійкі і паралельні комп'ютерні системи при аналізі надійності моделювались як мережі. Оскільки більша частина досліджень з оцінки мережевої надійності велася для мереж передачі даних, основний упор робився на алгоритми аналізу топології мереж. Стимулом робіт з мережевої надійності послужили комп'ютерні архітектури, в основі роботи яких лежать сильно структуровані мережі, поєднані з певними архітектурами ЕОМ. Зазвичай використовуються заходи, що базуються на пов'язаності мережі. Проте особливо у випадку паралельних ЕОМ з великою кількістю процесорів повинні розглядатися параметри надійності, які враховують міркування пропускної здатності.

Інші застосування

Існує велика різноманітність мережевих моделей, частина з них застосовується в інших галузях науки. У всіх аналізованих випадках мережа підтримує роботу багатьох користувачів, трафік кожного з них потрібно через мережу одним або кількома маршрутами. Зазвичай мається на увазі, що можна зробити більш точну оцінку надійності, якщо врахувати в розрахунках параметри маршрутизації. На завершення потрібно відзначити, що потрібно враховувати величини пропускної здатності. Одна з найбільш цікавих галузей застосування - міські мережі наземного транспорту. У цьому контексті інциденти, такі, як аварії на автомагістралях, викликають відмову мережевих вузлів або дуг. Хоча порушення зв'язаності в мережі міського транспорту відбуваються дуже рідко, все-таки цілком типово, коли відмова сайту або зв'язку викликає ситуацію значною перевантаження.

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

Причини виникнення збоїв

Механізми втрат і причини їх виникнення відносно добре вивчені в класичній теорії надійності. Наприклад, в електронних системах деградація вузлів відбувається, коли вони піддаються безперервному теплового впливу. У результаті такі вузли випадковим чином виходять з ладу. Аналіз надійності для подібних систем звичайно включає в себе вивчення цих випадкових процесів і параметри їх розподілів. При аналізі мережевої надійності частина механізмів, що викликають втрати, відомі також як і параметри їх функцій розподілу. Але залишається багато не менш важливих механізмів, про функції розподілу яких ми нічого не можемо сказати. Наприклад, існує багато публікацій про виникнення відмов у роботі оптоволоконних мереж, викликаних природними причинами, такими, як пожежі, або помилками оператора транзитної мережі, який спільно використовував канал. Таким чином, важко побудувати модель збоїв в каналі, що задовольняє реальній частоті збоїв. Зазвичай, прогноз частоти збоїв у мережі будується на основі історичного аналізу або результатів вимірювань. Більш докладний розгляд проблеми представлено в книзі MO Ball, C.J. Colbourn, J.S. Provan, "Network Reliability".

Складність аналізу мережевої надійності

Існує два важливих окремих випадків мір: 2-термінальна міра з |К|=2 і всетермінальная міра, де К = V. Ці заходи прийнято позначати Rel2(G,s,p)і RelА (G,s,p), відповідно (Rel - надійність). Наведемо результати, отримані для складності аналізу мережевої надійності в трьох частинних задачах: k-термінальної 2-термінальної і всетермінальної.

k терміналів

Набір шляхів з мінімальною потужністю для k-термінальної міри є дерево Штейнера з мінімальною потужністю. Відомо, що завдання розпізнавання є NP складною для орієнтованих і неорієнтованих мереж. Аналіз функціональної і раціональної надійності для задачі аналізу мають NP складність. Валіант [LGValiant, "The complexity the enumeration and reliability problems", SIAM, J. Computing, 8 (1979), 410-421] наводить альтернативне доказ, що полягає в демонстрації того, що обчислення

SN(K)=ΣFi=|(S:S відповідає субграфу, який містить шлях до кожного вузла в К)|, має складність NP. Тут K є набором терміналів.

2 термінала

Завдання розпізнавання мінімального набору шляхів і розрізів, поєднані з 2-термінальної мірою, є проблемами найкоротшого шляху і мінімального розрізу, відповідно. Відомі поліноміальні алгоритми для обох цих завдань. Валіант вперше показав, що завдання аналізу надійності в разі 2-термінальної міри мають складність NP. Його результатом служать гарною ілюстрацією методик, які використовуються в даній області.

Всетермінальная міра

Для орієнтованої всетермінальной міри проблеми з наборами шляхів і розрізів з мінімальною потужністю є завданням пошуку мінімального покриває дерева і мінімального s-орієнтованого розрізу, відповідно.

Обидві ці завдачі вирішуються за поліноміальний час. Завдання підрахунку мінімальних s-орієнтованих розрізів має складність NP. А це, у свою чергу, означає, що пов'язана з нею завдача надійності має складність NP. Для випадку неорієнтованому заходи задачі з розпізнавання і підрахунку мінімального набору шляхів і розрізів мають поліноміальну складність. Однак завдання обчислення загального члена в полінома надійності має складність NP, тому що завдача аналізу надійності для неорієнтованого випадку мають складність NP.

У світлі цих негативних результатів, більшість досліджень мали на меті аналіз структурованих мереж. Найширший клас мереж, для яких можна виконати обчислення за поліноміальний час, базується на послідовно-паралельних графах і певних узагальненнях. Прован (JSProvan, "The complexity of reliability computations in planar and acyclic graphs", SIAM, J. Computings 8 (1986), 694-702) показав, що неорієнтована 2-термінальна проблема надійності має складність NP в планарних нециклічних мережах, що мають ступеня вузлів не вище трьох.

Результати даного розділу вказують на те, що поліноміальні алгоритми для мережевої надійності існують тільки для маленького класу мереж. Завдяки цьому факту велике число досліджень присвячене вивченню обмежень мережевий надійності і підходів, заснованих на методі Монте-Карло.

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

Ребро або дуга, які не входять ні в один з мінімальних наборів шляхів, називається нерелевантні: працездатність таких нерелевантних ребер не впливає на роботу або відмову мережі. Найпростішим способом спрощує перетворення графа є видалення нерелевантних ребер. За визначенням, таке перетворення не змінює міру надійності. Щоб перетворення мало практичне застосування для мережі, час його ефективної реалізації має бути поліноміальним. Для все-, k-і 2-термінальних мір надійності петлі завжди є нерелевантними. А для k-і 2 - термінальних мір надійності нерелевантними є також усі кінцеві ребра, що не мають термінального закінчення. Такі ребра легко знаходити і видаляти. У разі орієнтованих задач надійності пошук нерелевантних дуг аж ніяк не просте завдання. Було показано, що задача знаходження нерелевантних дуг у випадку (s,t)-пов'язаності має складність NP, в той час як загальна неорієнтована завдання допускає ефективне рішення.

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