Моделі та методи аналізу та маршрутизації фракталоподібного трафіку у комп’ютерних мережах

Abstract

Дрєєва Г. М. Моделі та методи аналізу та маршрутизації фракталоподібного трафіку у комп’ютерних мережах. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 123 Комп’ютерна інженерія. – Черкаський державний технологічний університет, Черкаси, 2023. Актуальність дослідження зумовлена постійним збільшенням навантаження на сучасні комп’ютерні мережі внаслідок все зростаючої їх ролі у всіх сферах діяльності людини та необхідністю забезпечення високої якості надання послуг користувачам навіть при пікових навантаженнях на мережу. Адже повністю усунути ймовірність пікових навантажень на комп’ютерні мережі, як і на будь-які системи масового обслуговування, за рахунок постійного їх масштабування не є можливим – тож необхідно боротися з наслідками перевантажень, коли вони трапляються. Одним зі шляхів підвищення якості обслуговування у комп’ютерних мережах є зменшення кількості втрачених IP-пакетів. Втрата мережевих пакетів при пікових навантаженнях на комп’ютерну мережу відбувається внаслідок того, що черги маршрутизаторів переповнюються, і вони відкидають пакети, які не можуть помістити у чергу. На різні протоколи транспортного рівня втрата пакетів може впливати по-різному, зокрема, при використанні протоколу UDP буде падати якість та надійність передачі даних, а при використанні протоколу TCP буде знижуватися швидкість передачі даних при невеликих значеннях втрат пакетів, а при великих втратах пакетів буде знижуватися і швидкість, і якість роботи мережі. Тому важливою науково-практичною задачею, яка вирішується у цій роботі, є підвищення якості обслуговування у комп’ютерних мережах під час високої інтенсивності мережевого трафіку та пікових навантаженнях на маршрутизатори шляхом зменшення кількості втрачених мережевих пакетів. Як показало проведене дослідження методів маршрутизації трафіку, прогнозування завантаженості мережевих пристроїв з метою перенаправлення трафіку на менш завантажені за прогнозами пристрої є перспективним способом зменшення кількості втрачених IP-пакетів під час пікових навантажень на мережу. Для прогнозування можна використовувати будь-які методи прогнозування часових рядів, питання тільки в тому наскільки якісно вони будуть прогнозувати стан каналу зв’язку для комп’ютерних мереж із різними типами трафіку. А оскільки мережевий трафік має свої певні властивості та особливості й може бути різних типів та з різними варіаціями властивостей, то було досліджено можливість та ефективність застосування різних методів прогнозування часових рядів для прогнозування завантаженості маршрутизаторів. Методи прогнозування часових рядів можна загалом приблизно розділити на такі категорії: – Класичні статистичні методи, наприклад, ковзні середні, експоненційне згладжування, ARIMA, SARIMA. – Машинне навчання, наприклад, лінійна регресія, випадковий ліс, нейронні мережі та глибоке навчання тощо. – Фрактальний аналіз, наприклад, R/S-аналіз. Проведене дослідження показало, що реальний комп’ютерний трафік має фрактальні властивості, а також може бути персистентним або антиперсистентним залежно від типу мереж та інформації, що у них передається. Зокрема, у гетерогенних комп’ютерних мережах спостерігається персистентний трафік, а у мобільних та домашніх Wi-Fi мережах, в наномережах датчиків та Інтернеті речей IoT спостерігається антипесистентний трафік. Це можна використати при розробці методів прогнозування завантаженості мережевих пристроїв, використовуючи для прогнозування часових рядів трафіку фрактальний аналіз. Оскільки використання фрактальних часових рядів для математичного опису мережевого трафіку дозволяє моделювати такі його властивості, як наявність трендів, персистентність та антиперсистентість, які притаманні реальному трафіку та дозволяють робити моделі більш реалістичними, то для вирішення обраної науково-практичної задачі було вирішено використовувати переважно фрактальний аналіз та синтез трафіку. На основі проведеного дослідження можливих шляхів вирішення наявної науково-практичної задачі було наступним чином сформульовано мету дисертаційної роботи: зменшення ймовірності втрати IP-пакетів при високій інтенсивності трафіку за рахунок розробки і застосування моделей та методів фрактального аналізу й адаптивної маршрутизації трафіку. Проведено дослідження та порівняльний аналіз моделей та методів роботи комп’ютерних мереж, а також методів аналізу, моделювання, прогнозування та маршрутизації мережевого трафіку. Удосконалено математичну модель мережевого фракталоподібного трафіку, яка відрізняється від відомих представленням трафіку на рівні “пакет є” – “пакета немає” на вході маршрутизатора та запропонованими ланцюгами Маркова, які описують ймовірності станів генератора трафіку як стохастичного скінченного автомата, що дало змогу одержати рівняння для імітаційного моделювання фрактального та мультифрактального трафіків. На основі запропонованої математичної моделі розроблено метод генерації мережевого фрактального трафіку, який відрізняється від відомих можливістю налаштовувати фрактальну розмірність та інтенсивність трафіку перед його генерацією, а отже, моделювати різні типи трафіку. Вперше розроблено метод аналізу мережевого фракталоподібного трафіку, який відрізняється від відомих використанням нової міри визначення фрактальної розмірності бінарного трафіку, що дозволило зв’язати аналітично його статистичні та фрактальні властивості, підвищити точність визначення фрактальної розмірності та зменшити кількість арифметичних операцій при фрактальному аналізі. Набув подальшого розвитку метод програмного імітаційного моделювання комп’ютерної мережі на основі теорії складних мереж, який відрізняється від відомих використанням запропонованого методу генерації мережевого фрактального трафіку та параметризацією характеристик моделі, зокрема таких як кількість маршрутизаторів, густина зв’язків між ними, довжина їх черг, пропускна здатність, інтенсивність та фрактальна розмірність трафіку, максимальна кількість вихідних пакетів з одного пристрою в одиницю часу, що дозволило моделювати комп’ютерні мережі різної архітектури для тестування якості роботи алгоритмів маршрутизації. Удосконалено метод адаптивної маршрутизації трафіку, який відрізняється від відомих використанням додаткової метрики для визначення найкоротших шляхів передачі мережевих пакетів, представленої прогнозованою ймовірністю втрати мережевих пакетів маршрутизатором, яка визначається запропонованим новим методом на основі вимірюваних значень фрактальної розмірності та інтенсивності вхідного трафіку, що дозволило підвищити якість обслуговування у комп’ютерній мережі під час пікових навантажень за рахунок зменшення кількості втрачених IP-пакетів. Проведена оцінка якості та ефективності запропонованих методів і моделей шляхом проведення експериментів на програмній імітаційній моделі. Практична цінність роботи полягає у такому: Розроблено алгоритми моделювання структури комп’ютерної мережі та генерації фрактального мережевого трафіку, що дають можливість моделювати комп’ютерні мережі різної архітектури для тестування якості роботи алгоритмів маршрутизації. Розроблено алгоритми для аналізу фрактальних властивостей трафіку та алгоритми для прогнозування ймовірності втрати мережевих пакетів маршрутизатором на основі статистичних та фрактальних властивостей вхідного трафіку, що дають змогу удосконалювати алгоритми маршрутизації. Запропонований метод аналізу мережевого фракталоподібного трафіку з більшою точністю та однозначністю результатів визначає фрактальну розмірність трафіку незалежно від довжини досліджуваного ряду, на відміну від відомого методу на основі R/S-аналізу, а також має меншу кількість арифметичних операцій. Зокрема, запропонований метод дає менший відсоток відхилення від середнього значення показника Херста, а саме 1,8% , на відміну від 2,5% для R/S-аналізу. Розроблено алгоритм адаптивної маршрутизації трафіку з застосуванням додаткової метрики для визначення найкоротших шляхів передачі мережевих пакетів, представленої прогнозованою ймовірністю втрати мережевого пакету маршрутизатором, яка визначається новим методом на основі вимірюваних значень фрактальної розмірності та інтенсивності вхідного трафіку. Запропонований удосконалений метод адаптивної маршрутизації дає змогу зменшувати кількість втрачених мережевих пакетів під час високої інтенсивності трафіку, зокрема, при інтенсивності 0,8 в середньому на 23% для персистентного трафіку, на 17% –для випадкового трафіку та на 1,5% – для антиперсистентного трафіку; конкретні значення покращень залежать від параметрів мережі. Практичне значення отриманих результатів підтверджено відповідними актами впровадження. Результати дисертаційних досліджень впроваджені і використовуються у діяльності Інтернет сервіс провайдера ТОВ «Імперіал-Нет», а також використано у навчальному процесі Центральноукраїнського національного технічного університету. Models and methods of analysis and routing of fractal-like traffic in computer networks. – Qualifying scientific work on the rights of the manuscript. Dissertation for the degree of Doctor of Philosophy (PhD) in the specialty 123 “Computer Engineering”. – Cherkasy State Technological University, Cherkasy, 2023. The relevance of the research is determined by the constant increase in the load on modern computer networks due to their ever-growing role in all spheres of human activities and the need to ensure high quality of service to users even during peak network loads. After all, it is not possible to completely eliminate the likelihood of peak loads on computer networks, as well as on any mass service systems, due to their constant scaling – therefore, it is necessary to deal with the consequences of overloads when they occur. One way to improve the quality of service in computer networks is to reduce the number of lost IP-packets. The loss of network packets during peak loads on a computer network occurs as a result of router queues becoming full, and then they discard packets that cannot fit into the queue. Different transport layer protocols can be affected differently by packet loss, for example, when using the UDP protocol, the quality and reliability of data transmission will decrease, and when using the TCP protocol, the data transmission speed will decrease at low levels of packet loss, while at high levels of packet loss, both the speed and quality of network performance will decrease. Therefore, an important scientific and practical task, which is solved in this work, is to improve the quality of service in computer networks during high network traffic intensity and peak loads on routers by reducing the number of lost network packets. As the study of traffic routing methods has shown, prediction of the load on network devices with the aim of redirecting traffic to devices that are less loaded according to forecasts is a promising way to reduce the number of lost IP-packets during peak network loads. Any time series forecasting methods can be used for prediction; the question is only how accurately they will predict the state of the communication channel for computer networks with different types of traffic. Since network traffic has its own specific properties and characteristics and can be of different types with various property variations, the possibility and effectiveness of applying different time series forecasting methods for predicting router load have been investigated. Methods of forecasting time series can be roughly divided into the following categories: – Classical statistical models, for example, moving averages, exponential smoothing, ARIMA, SARIMA. – Machine learning, for example, linear regression, random forest, neural networks, and deep learning, etc. – Fractal analysis, for example, R/S analysis. The conducted research has shown that real computer traffic has fractal properties and can be either persistent or anti-persistent, depending on the type of networks and the information being transmitted in them. In particular, persistent traffic is observed in heterogeneous computer networks, while anti-persistent traffic is observed in mobile and home Wi-Fi networks, in nanonetworks of sensors, and in the Internet of Things (IoT). This can be utilized in the development of methods for forecasting the load on network devices, using fractal analysis for forecasting time series of traffic. Since the use of fractal time series for the mathematical description of network traffic allows to model its properties, such as the availability of trends, persistence, and anti-persistence, which are inherent to real traffic and make models more realistic, it has been decided to predominantly use fractal analysis and synthesis of traffic to solve the chosen scientific and practical task. Based on the conducted research of possible ways to solve the existing scientific and practical problem, the goal of the dissertation work is formulated as follows: the reduction of the probability of IP-packet loss during high traffic intensity by developing and applying models and methods of fractal analysis and adaptive traffic routing. A study and comparative analysis of models and methods of computer networks operation, as well as methods of analysis, modeling, forecasting, and routing of network traffic, have been conducted. An improved mathematical model of network fractal-like traffic, which differs from known models by representing traffic at the "packet is present" – "packet is absent" level at the router input and the proposed Markov chains, which describe the probabilities of states of the traffic generator as a stochastic finite automaton, has been developed. This allows to obtain the equations for simulation modeling of fractal and multifractal traffic. Based on the proposed mathematical model, a method of generating network fractal traffic, which differs from known methods by the ability to adjust the fractal dimension and traffic intensity before its generation, thus modeling different types of traffic, has been developed. For the first time, a method of analyzing network fractal-like traffic, which differs from known methods by using a new measure for defining the fractal dimension of binary traffic, has been developed. This allows to analytically link its statistical and fractal properties, increase the accuracy of determining the fractal dimension, and reduce the number of arithmetic operations during fractal analysis. A method of software simulation modeling of a computer network based on the theory of complex networks, which differs from known ones by using the proposed method of generating network fractal traffic and by parameterizing the characteristics of the model, in particular, such as the number of routers, the density of connections between them, the length of their queues, bandwidth, intensity and fractal dimension of traffic, the maximum number of outgoing packets from one device per unit of time, has been further developed, which makes it possible to simulate computer networks of various architectures for testing the quality of work of routing algorithms. A method of adaptive traffic routing, which differs from known methods by using an additional metric to determine the shortest paths for transmitting network packets, represented by the predicted probability of network packet loss by the router, which is determined by proposed new method based on the measured values of fractal dimension and intensity of incoming traffic, has been improved. This allows to improve the quality of service in the computer network during peak loads by reducing the number of lost IP-packets. The quality and effectiveness of the proposed methods and models have been assessed through experiments conducted on the software simulation model. The practical value of the work lies in the following: The algorithms for modeling the structure of a computer network and generating fractal network traffic, which allow to simulate computer systems of different architecture to test the quality of routing algorithms, are developed. The algorithms for analyzing fractal properties of traffic and algorithms for predicting the probability of loss of network packets by a router based on statistical and fractal properties of incoming traffic, which allow to improve routing algorithms, are developed. The proposed method for analyzing network fractal-like traffic determines the fractal dimension of traffic with greater accuracy and unambiguity of results, regardless of the length of the studied series, unlike the known method based on R/S-analysis, and also has fewer arithmetic operations. In particular, the proposed method has a smaller percentage deviation from the average value of the Hurst exponent: namely, 1.8% compared to 2.5% for R/S-analysis. The adaptive traffic routing algorithm using an additional metric for determining the shortest paths for network packet transmission, represented by the predicted probability of loss of a network packet by a router, which is determined by a new method based on measured values of fractal dimension and intensity of incoming traffic, is developed. The proposed improved adaptive routing method allows to reduce the number of lost network packets during high traffic intensity, in particular, at an intensity of 0.8 on average by 23% for persistent traffic, by 17% for random traffic, and by 1.5% for anti-persistent traffic, with specific improvement values depending on network parameters. The practical significance of the obtained results is confirmed by the corresponding implementation acts. The results of the dissertation research have been implemented and are used in the activities of the Internet service provider LLC "Imperial-Net" and have also been used in the educational process at the Central Ukrainian National Technical University.