Керування перевантаженням комп’ютерної мережі © Кучеров Д.П. Навчально-науковий інститут Комп’ютерних інформаційних технологій Національного авіаційного університету, Київ, Україна d_kucherov@ukr.net Анотація У роботі розглядається комп’ютерна мережа, що функціонує в умовах перевантажень та збоїв. Встановлено типові причини на наслідки перевантаження комп’ютерних мереж. Відзначається, що універсальним показником мережі є її перепускна здатність, що дозволяє розглядати проблему перевантаження відносно її перепускної здатності. Проаналізовано також відомі способи підвищення перепускної здатності мережі на основі керування чергами, методами передбачення та за рахунок механізму зворотного зв’язку, який введений для мереж Ethernet специфікацією IEEE 802.3x, а також способи керування перевантаженням, що використовуються в мобільних мережах. На підставі виконаного аналізу здійснено висновок про доцільність реконфігурації мережі в умовах перевантаження. Проблема підвищення перепускної здатності мережі ставиться на основі вимірювання навантаження мережі. Відповідно до обраної постановки завдання стає необхідність визначення перепускної здатності згідно з використовуваними на практиці алгоритмами маршрутизації. Завдання керування перевантаженням комп’ютерної мережі вирішується за протоколами маршрутизації OSPF, IS-IS, RIP в IP-мережах. В рамках цієї задачі розглядається керуванням перевантаженням мережі за рахунок резервування частки перепускної здатності, що використовується в реальних маршрутизаторах. В статті розглядається можливість відтворення перепускної здатності комп’ютерної мережі, формування трафіку в різних умовах мережевих підключень в умовах перевантаження мережі, що приводить до її реконфігурації. На основі типового уявлення про роботу мережі визначається конфігурація з меншим навантаженням, встановлюються відношення між падінням трафіку та його відновленням завдяки резервуванню. Встановлюються умови функціонування мережі в умовах перевантажень, які приводять до реконфігурації початкової топології, адекватність якої аналізується за схемою «загибель-розмноження». Поступове перевантаження вузлів у задачі подано ланцюгом Маркова, отримання показників перевантаження здійснюється на основі рівнянь Колмогорова. Встановлюються також умови відновлення перепускної здатності за рахунок компенсації перепускної здатності. Отримано числові показники щодо функціонування мережі за рахунок реконфігурації мережі. Ключові слова: комп’ютерна мережа, перевантаження, реконфігурація, схема «загибель- розмноження» 1 Вступ Перевантаження мережі є однією з основних проблем, з якою періодично стикаються користувачі комп’ютерних мереж. Ця проблема викликає зниження перепускної здатності мережі, збільшення часу проходження пакетів або їх втрату. Саме це явище призводить до припинення дії деяких мережевих служб, таких як VoIP, інтерактивні додатки, чат, доступ до віддалених ресурсів та інших. Останнім часом, коли спостерігається експоненціальне зростання мереж, ця проблема при їх експлуатації стає найбільш загостреною. Одним з чинників перевантаження вважається надлишкова буферизація каналу передавання [1]. Буфер необхідний при передачі даних по лінії зв’язку, якщо у відправника та отримувача різний темп оброблення. При цьому в буфері затримується передавання пакетів на час приймання та первинного оброблення отримувачем. Наповнення буферу приводить до втрат переданих пакетів. Це явище може спостерігатися в маршрутизаторах, бездротових точках доступу, мостах, шлюзах, пристроях супутникового зв’язку. Виключення перевантаження вирішується декількома способами. Запобігти перевантаженню буфера можна досягти завдяки керуванню чергами та методами передбачення. Методи керування перевантаженням контролюють перевантаження після того, коли воно виникає, в той час, як методи передбачення усувають перевантаження шляхом контролю інтенсивності передавання даних у мережі, що дозволяє передбачити перевантаження та запобігти його в типових "вузьких місцях" мережі. Основним засобом мережевих операційних систем із запобігання перевантажень в Cisco є застосування алгоритмів зваженого випадкового раннього виявлення (WRED) [2]. В дуплексному режимі контролю портів комутатора можлива реалізація механізму зворотного зв’язку, який введений для мереж Ethernet специфікацією IEEE 802.3x. Механізм реалізується введенням підрівня керування рівнем MAC, на якому вводиться параметр часу зупинки передачі кадрів іншим вузлам. Час вимірюється в 512 бітовими інтервалами конкретної реалізації Ethernet, діапазон можливих варіантів зупинки знаходиться в інтервалі 0 – 65535. Після завершення часу зупинки передача відновлюється. Перевантаження може бути виключеним, якщо вводиться резервування перепускної здатності на підставі двійкових методів. При цьому користувачу додатками QoS надається частина перепускної здатності 69 каналу, інша частина резервується іншим користувачам, що здійснюється за рахунок використання логічного з’єднання. Але це відбувається на рівні обладнання, яке вводить пріоритети певним користувацьким додаткам, наприклад, таким як відеоконференція. Таким чином, все мереже обладнання, що є в каналі передачі, повинне підтримувати цю технологію, але це не завжди виконується. В мобільних мережах типовим рішенням завдання перевантаження вважається реконфігурація мережі. В статті проводиться аналіз можливості відтворення перепускної здатності комп’ютерної мережі, формування трафіку в різних умовах мережевих підключень, визначається конфігурація з меншим навантаженням, встановлюються відношення між падінням трафіку та його відновленням завдяки резервуванню. 2 Аналіз останніх досліджень та публікацій Комп’ютерна мережа зазвичай діє в умовах різної швидкості передачі даних. Ця проблема зустрічається не тільки в мережах Ethernet, а й в мобільних мережах. Наявність великої кількості агентів мобільної мережі приводить до її перевантаження, що в значної ступені вирішується шляхом рішення завдання маршрутизації за умови зміни топології мережі. Оскільки, єдиного ефективного алгоритму маршрутизації для комп’ютерних мереж не існує, тому в [3] для динамічного розподілу трафіку пропонується вирішувати завдання маршрутизації на основі існуючої системи агентів визначенні суміжних агентів. Питання перевантаження мобільної мережи в умовах перешкод навмисного і ненавмисного походження вирішується авторами роботи [4]. Ефективна мережа мобільного зв’язку створюється за допомогою реконфігурації діаграм напрямленості антен базових станцій. Висуваються вимоги до топології з кращою завадозахищеністю стільникового зв’язку. В одній з останніх робіт з цього напрямку [5] пропонується методика побудови оптимізаційних моделей комп’ютерної мережі, які призначені для виконання завдань шляхом розміщення вузлів мережевої структури за допомогою середовища електронних таблиць. Вузли мережі поділяються на сервери та прив’язані до них клієнти. Конфігурація графу такої мережі створюється шляхом рішення максимінної задачі на основі нелінійної оптимізації. Метод слідкуючого вікна при управлінні потоком даних в локальній мережі, утвореної мобільними агентами запропоновано авторами [6]. Аналіз наведених підходів показує ефективність застосування адаптивного вікна спостереження на основі ARQ – механізму керування потоком даних. Встановлені властивості механізму керування дозволяють визначити оптимальний розмір вікна спостереження та пакетів для передачі даних по мережі. Методологія оцінки якості реконфігурованої топології мереж WATM на основі показників надійності їх функціонування подана в [7, 8]. Розроблений автором статті підхід базується на по-кроковому моніторингу порогів безвідмовленості та відновлюваності комп’ютерної мережі. Черговий крок задається відношенням приросту коефіцієнта готовності до приросту витрат на його підтримку. В роботі [8] розглядається пропускна здатність мультисенсорної системи, яка побудована на мережевому принципі дії. Адекватність реконфігурації мережі в умовах природних та штучних перешкод аналізується за схемою «загибель-розмноження». Метою статті є оцінка показників відновлюваності трафіку комп’ютерної мережі, яка діє в умовах перевантажень за рахунок умов штучних та природних завад, що приводить до зміни конфігурації системи. 3 Постановка проблеми Будемо розглядати комп’ютерну мережу, вузли якої здатні обробляти інформацію та обмінюватися даними, крім того дозволяється зміна конфігурації системи. За способом управління мережа відповідає архітектурі «клієнт-сервер». Мережа має певну топологію, яка описується зваженим графом G = (V, E), в якому V – вузли, число вузлів V(G) = N, а E – зважені дуги, число дуг G(E) = M. Кожній дузі графу (i, j) ставиться у відповідність число wij > 0, яке зветься вагою дуги (i, j), i = 1..N, j = 1..M. В разі, коли (i, j)  G, wij = . Шлях від вузла s до вузла f довжиною l називають впорядковану послідовність (Es, …, Ef)l = (Es, Ei), …, (Ei+q, Ei+q+1), …, (El, Ef). Зваженою довжиною шляху від s до f називають число L( s, f )   wi , j . (1)  j , j 1( E s ,..., E f ) Введемо множину усіх припустимих шляхів sf, тоді найкоротший шлях визначається виразом   Lsf min  wi , j . (2) ( E s ,..., E f ) sf  j , j 1( E s ,...,E f ) Ставиться завдання визначити можливість щодо визначення найкоротшого шляху в комп’ютерній мережі в умовах впливу природних чи штучних перешкод на систему (1). 70 4 Задача маршрутизації Передача даних в мережі відбувається за правилами, що регламентуються застосовуваними протоколами, згідно яких встановлюється адреса, розмір і структура пакету, що передавається, швидкість передачі даних. Адреса може бути індивідуальною, коли повідомлення посилається тільки одному агенту, груповою, коли повідомлення розсилається кожному агенту в групі, або деякій підгрупі агентів. Такий спосіб адресації подібний до адресації в комп’ютерних мережах. Передача даних відбувається від адреси джерела до адреси приймача. Якщо кількість вузлів значна, тоді виникає необхідність передавати інформацію через транзитні вузли. Але при цьому стає необхідність прокладання маршруту щодо забезпечення мінімуму часу на доставку інформації, що досягається мінімумом транзитних вузлів або наявністю каналів з високою пропускною здатністю та надійністю ліній зв’язку. Зрозуміло, що невелике збільшення кількості транзитних вузлів, що мають велику пропускну здатність, є переважним над мінімальною кількістю вузлів з невеликою пропускною здатністю з точки зору часу передачі інформації. Надійні канали зв’язку характеризуються мінімальними втратами інформації, що передавається. Через вузол може проходити декілька підпотоків, їх відрізняють за адресом пункту призначення. Зрозуміло, щоб визначити маршрут, який би забезпечив рівний час потоків різного обсягу даних, необхідно враховувати швидкість передачі, яку мають окремі лінії, та надавати можливість проведення розпаралелювання підпотоків та їх збірку. Переключення вузлів для передачі підпотоків здійснюється мультиплексуванням вільних каналів. Дана задача складається у визначенні маршруту проходження інформації кінцевому агенту. Розрізнюють статичні та динамічні маршрути. Статичний маршрут задається одноразово або за певним розкладом та не змінюється в межах певного часу. Динамічні маршрути обчислюються відповідними алгоритмами в залежності від топології та стану інформаційної мережі. До них відносяться алгоритми пошуку найкоротшої відстані в ширину, Дейкстри, Беллмана-Форда [9, 12]. 4.1 Пошук в ширину Проводиться обхід кожної вершини Vi  V графа G, запам’ятовується кількість пройдених дуг Ei  E, Мінімальна відстань L(s, f) між точками s та f відповідає найменшій кількості дуг, що з’єднують вершини s і f N L( s, f )  min  Ei (3) ( E s ,..., E f ) sf i 1 Приклад застосування алгоритму наведений на рис.1. Рис. 1. Комп’ютерна мережа, що складається з 9 вузлів. Найкоротший маршрут передачі інформації між вершинами 1-9 за алгоритмом (2) відповідно до рис. 1 складає L(1, 9)=3. Оцінкою продуктивності графа виступає часова складність O(), що визначається кількістю операцій за алгоритмом (2). За цим алгоритмом усі вузли та ребра скануються одноразово, тому часова складність визначається їх кількістю, а саме O(M+N). 4.2 Алгоритм Дейкстри Цей алгоритм є процедурою пошуку найкоротшого шляху на зваженому орієнтованому графі. Алгоритм використовується протоколами маршрутизації OSPF та IS-IS в IP-мережах [13, 14]. Ребра графа мають вагу (i, j) таку, що 0, якщо i  j , тобто та сама вершина ,  wij   w  0, якщо | i  j | 2 тобто сусідні вершини, (4)  , якщо інакше. 71 Довжина шляху на кожному кроці k від вершини s визначається правилом Lk  min[ L(k ), L(V )  wij ] для V  G, L(s)=0. (5) V Правило (4) не дозволяє робити проходи по дугам графа G з великою вагою. Таким чином, множина вершин в графі G являє собою впорядковану послідовність зв’язаних між собою вузлів, яка містить найкоротший шлях від вершини s до k. Цей шлях показаний на рис. 2 стрілками. Рис. 2. Структура зваженого графа. В кожний розрахунковий момент часу на маршрутизатор i поступає сумарний потік інформації, призначений для передавання кожному маршрутизатору j. Цей потік визначає таблицю маршрутизації, яку можна визначити матрицею P(t) розмірності NN з нульовою головною діагоналлю P (t )   сij (t ), k  K , (6) i, j де K – множина потоків інформації, яка зв’язана з відповідними IP-адресами, а сij – пропускна здатність. Компанія Cisco в маршрутизаторах визначає ваги дуг за формулою 108 wij  , (7) сij (t ) Оскільки алгоритм є ітераційним, то число ітерацій визначається кількістю вершин графа, тому часова складність алгоритму O(N). В межах кожної ітерації, відбувається нове проходження з врахуванням нової (j+1) вершини. При цьому вершини з найбільшою вагою вивільняються, а довжина шляху з новими вершинами поновлюється, кращий результат запам’ятовується. Це те ж оцінюється кількістю вершин. Загальна продуктивність алгоритму оцінюється величиною O(N2). Таким чином, алгоритм Дейкстри є ресурсоємним, але завдяки знанням топології мережі і шляху до потрібної вершини, маршрутизатор завжди знаходить альтернативний шлях до потрібного вузла мережі у випадку виникнення проблем у будь-якому вузлу визначеного шляху. Резервування перепускної здатності повинно враховувати навантаження мережі. Для контролю маршрутизатор доповнюється засобами вимірювання навантаження, які будуть створювати аналогічно (6) матрицю навантажень Х=|xij|. Тоді алгоритм з резервуванням трафіку може бути записаний як сij  , якщо сij  xij , сij (t )   (8) cij, якщо інакше, де  - частка, що компенсує перевантаження. 4.3 Алгоритм Беллмана-Форда За суттю цей алгоритм нагадує попередній (Дейкстри). На відміну від алгоритму Дейкстри цей алгоритм не відкидає ребр з великою вагою та ітераційно розраховує довжину усі шляхи в графі, запам’ятовуючи мінімальний шлях, використовується протоколом маршрутизації RIP. Кількість ітерацій, як і алгоритмі Дейкстри визначається кількістю вершин, а кількість розрахунків в межах ітерації кількістю ребр, то часова складність алгоритму оцінюється величиною O(VE). Результат цього алгоритму для графа рис.2 співпадає з алгоритмом Дейкстри. При однакових розмірах графа алгоритм Дейкстри є менш ресурсоємним ніж Беллмана-Форда, а значить більш швидкий. Зменшення ресурсоємності можна досягти зменшенням кількості ребр, тобто переходом до розрідженого графу. 72 5 Зміна структури системи Під реконфігурацією інформаційної системи будемо розуміти зміну будови системи, яка стосується розміру чи її топології. Особливістю реконфігурації є перебудова структури та топології системи з метою виключення перевантажень та збоїв в роботі системи. Вважається, що мережа виконує свої функції, поки між вузлами здійснюється обмін інформації. Приклад реконфігурованої системи показаний на рис.3. Рис. 3. Зміна будови інформаційної системи в результаті втрати зв’язку. Таким чином, внаслідок перевантажень чи збоїв топологія локальної повнозв’язної мережі змінюється до «шина». Відповідно до загального уявлення про комп’ютерну мережу (1) вона є системою з обмеженою кількістю можливих станів. Тому її поведінку можна промоделювати за допомогою математичного апарату аналізу марківських ланцюгів. Будемо вважати, що в процесі роботи комп’ютерна мережа, яка складається з кінцевої множини елементів N, обмінюється інформацією між всіма елементами за протоколами OSPF або RIP, що відповідає умовам нормального функціонування системи. Початковий стан мережі позначимо S1. Якщо за якимись не випадковими причинами починають виходити з ладу елементи мережі чи може пропадати обмін інформацією, то відбувається перехід системи до іншого стану. Будемо вважати, що елементи системи не перевантажуються одночасно, а по одному, тому здійснюються послідовні переходи зі стану S1 у стани S2, S3, …, Si через певні інтервали часу t, i означає номер стану. Послідовний набір станів комп’ютерної мережі та переходів між ними утворює ланцюг Маркова. Оскільки ланцюг послідовний, то функціонування системи можна подати у вигляді схеми «загибель-розмноження» [15]. Нехай комп’ютерна мережа складається з n вузлів, тому відповідно до підходу за схемою «загибель- розмноження» введемо стани Si , i=1..n+1, де S1 – стан мережі, що відповідає функціонуванню всіх вузлів без перевантажень. За умови впливу зовнішніх і внутрішніх факторів погіршується перепускна здатність каналів в мережі з фіксованою інтенсивністю . При цьому здійснюється перехід в стани, коли вузли поступово втрачають пакети, послідовно один за другим. Таким чином, здійснюється перехід в стан S2, коли не працює 1 вузол, та так далі, а відповідно Sn+q – комп’ютерна мережа перестала виконувати завдання у зв’язку з виходом з ладу (n – q)-вузлів. Система також може вживати заходи щодо нарощування перепускної здатності, що відбувається з інтенсивністю  > . При цьому з інтенсивністю  відбуваються послідовні переходи зі станів Si у стани Si-1. Знайдемо ймовірності pi знаходження комп’ютерної мережі в кожному з кінцевих станів Si та проаналізуємо їх. Ймовірності знаходження системи у фінальних станах знаходяться за формулами [15] 1 i  i  k  k   n    pi  p0 k 1 , i  0, p0  1   k 1  . (8) i i k  i 1   k     k 1  k 1  Розглянемо цю задачу для випадку n = 5,  = 0,5, 1 = 0,8, 2=1,6, 3=2,4. Результати розрахунку за формулами (8) наведені на рис.4. Аналіз рисунку показує, що чим більше , тим краще система справляється с пакетами, більше ймовірність знаходження її у стані з мінімальними затримками та менше ймовірність знаходження у стані з найбільшими затримками. Рис. 4. Деградація комп’ютерної мережі в умовах інтенсивних навантажень. 73 Як видно з рисунку, якщо  > (2..5) , то система стає більш стійкою до навантажень різних типів. 6 Висновки На підставі проведеного аналізу протоколів та алгоритмів маршрутизації встановлено, що ефективність комп’ютерної мережі визначається можливістю її функціонування в умовах перевантажень та збоїв, що є наслідком надлишкової буферизації системи. Одним з ефективних способів зменшення впливу перевантажень на мережу є резервування перепускної здатності каналів та компенсація її частки в каналах, які піддаються найбільшому впливу. Відповідно до проведеного аналізу мережі за схемою «загибель-розмноження» встановлена, що дія система функціонує, якщо відношення інтенсивності перевантажень до інтенсивності приросту перепускної здатності не перевищує значення 0,2…0,5. Подальші дослідження функціонування комп’ютерної мережі планується зосередити на аналізі її динамічних властивостей. Література 1. Gettys J. Bufferbloat: Dark Buffers in the Internet / J. Gettys // Internet Computing. – IEEE Computer Society, 2011. – Vol. 15.  № 3. – P. 96-95. 2. Руководство по технологиям объединенных сетей / Пер. с англ. – М.: ИД «Вильямc», 2005. – 1040 с. 3. Давиденко И.Н. Способ определения местоположения агентов домена в мобильных сетях / И.Н. Давиденко, И.А. Жуков // Проблеми інформатизації та управління. – №1 (23). – 2008. – С. 61-64. 4. Ластовченко М.М. Метод анализа эффективности реконфигурации топологии беспроводных мультисерверных сетей повышенной помехозащищенности / М.М. Ластовченко, Е.Е. Зубарева, В.О. Саченко // УСиМ.  №6. – 2009. – С. 79-86. 5. Кузьмичов А.І. Оптимізаційні моделі мережевих структур / А.І. Кузьмичов, Є.О. Додонов // Реєстрація, зберігання і обробка даних. – Т.19. - № 2. – 2017. – С. 24 – 35. 6. Kucherov D.P. Control System Objects with Multiple Stream of Information / D.P. Kucherov, A. N. Kozub // Proceedings 2015 IEEE 3rd International Conference “Actual Problems of Unmanned Aerial Vehicles Developments (APUAVD)”, October 13-15, 2015. – P. 290-293. 7. Горбунов И. Э. Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи / И. Э. Горбунов // Математичні машини і системи.  №2. – 2006. – С. 48-59. 8. Кучеров Д.П. Реконфігурація мультисенсорної системи за умови впливу дестабілізуючих факторів / Д.П. Кучеров // Сенсорна електроніка і мікросистемні технології. – T.13.  №2. - 2016. – С. 101-112. 9. Столлингс В. Современные компьютерные сети / В. Столлингс. – СПб.: Питер, 2003. – 783 с. 10. Олифер В.Г. Компьютерные сети: принципы, технологии, протоколы / В.Г. Олифер, Н.А. Олифер. – СПб.: Питер, 2006. – 958 с. 11. Таненбаум Э. Компьютерные сети / Э. Таненбаум, Д. Уэзеролл. – СПб.: Питер, 2012. – С. 960. 12. Кормен Т. Алгоритмы. Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – М.: ИД «Вильямс», 2005. – 1296 с. 13. Кузнецов Н.А. Алгоритм Дейкстры с улучшенной робастностью для управления маршрутизацией в IP-сетях / Н.А. Кузнецов, В.Н. Фетисов // Автоматика и телемеханика. - № 8. – 2008. – С. 80-85. 14. Fortz B. Optimizing OSPF / IS-IS weights in a changing world / B. Fortz, M. Throup // IEEE Journal on selected areas in communications, June, 2002. – P. 1-31. - [електронний ресурс]. – Режим доступу: DOI: 10.1109/JSAC.2002.1003042 15. Вентцель Е.С. Исследование операций: задачи, принципы, методология / Е.С. Вентцель. – М.: Наука, 1988. – 208 с. Control of Computer Network Overload © Dmytro P. Kucherov Educational-Scientific Institute of Computer Information Technologies of National Aviation University, Kyiv, Ukraine d_kucherov@ukr.net Abstract The paper considers a computer network operating in conditions of overload and failure. The typical reasons for the consequences of overloading of computer networks are established. It is noted that the universal indicator of the 74 network is its traffic capacity, which allows us to consider the problem of overload in relation to its throughput. We analyze are known ways to increase the throughput of the network based on queue control, prediction methods, and through the feedback mechanism introduced for Ethernet networks by the IEEE 802.3x specification, as well as methods for controlling overloads used in mobile networks. On the basis of the performed analysis, the conclusion was made on the expediency of reconfiguring the network under overload conditions. The problem of increasing the throughput of the network is based on the measurement of network load. According to the chosen task setting, it becomes necessary to determine the throughput in accordance with the routing algorithms used in practice. The task of controlling the overload of a computer network is determined by the routing protocols OSPF, IS-IS, RIP in IP networks. Within this framework, the network overload control is considered by reserving the part of traffic capacity as its share used in real routers. In this article examines the possibility of reproducing throughput of the computer network, the formation of traffic in various conditions of network connections in conditions of network overload, which leads to its reconfiguration. Based on a typical representation of the network's work, a configuration with a lower load is determined, and the relationship between traffic fall and its restoration through the reservation is established. The conditions of operation of the network in conditions of overloads are determined, which lead to the reconfiguration of the initial topology, the adequacy of which is analyzed according to the scheme "death-reproduction". Gradual overload of nodes in the task is given by the Markov chain that allow to obtain overload indicators is carried out on the basis of Kolmogorov equations. The conditions for restoration of traffic capacity due to overload compensation are also established. Numerical value of indicators for network operation are obtained due to network reconfiguration. Keywords: computer network, overload, reconfiguration, "death-reproduction" scheme 75