Моделі і методи забезпечення QoS шляхом обслуговування черг у мовах пікових навантажень

Abstract

Дисертаційна робота присвячена вирішенню актуальної науково-прикладної задачі, пов'язаної з розробкою та подальшим удосконалення моделей та методів управління чергами при пікових навантаженнях для підвищення якості обслуговування комп’ютерних мереж. Метою дисертаційної роботи є розробка математичних моделей вузлів мереж і моделей трафіка з гарантованою доставкою пакетів на базі математичного апарата марківських систем масового обслуговування та теорії черг для розв’язання задач аналізу комп’ютерних мереж та управління чергами у вузлах мереж за сукупністю критеріїв, які покращують показники QoS (затримка пакета, втрати пакетів). Об’єкт дослідження – процеси управління чергами в комп’ютерних мережах при пікових навантаженнях. Предмет дослідження – моделі та методи управління чергами в комп’ютерних мережах при пікових навантаженнях. У вступі обґрунтовано актуальність підвищення якості обслуговування в комп’ютерних мережах, представлено зв’язок роботи з науковими програмами, планами і темами, наведено наукову новизну, представлено практичне значення отриманих результатів, надано інформацію щодо особистого внеску здобувача, представлено перелік публікацій за темою дисертації. У першому розділі виконано постановку науково-технічної проблеми якості обслуговування в комп’ютерних мережах. Проведено аналіз принципів побудови та функціонування сучасних комп’ютерних мереж. Досліджено основні мережеві протоколи та механізми забезпечення якості обслуговування, виділено перспективні напрямки дослідження. Вказано на доцільність удосконалення існуючих та розробку нових моделей та методів управління чергами, особливо за умови пікових навантажень. Обґрунтовано вибір моделей та методів для подальшого дослідження. Сформульовано завдання дисертаційного дослідження. У другому розділі побудовано математичні моделі вузлів комп’ютерної мережі з неоднорідним вхідним потоком пакетів без пріоритетів, багатоканального вузла мережі з неоднорідним вхідним потоком пакетів з абсолютним пріоритетом, багатоканальним потоком пакетів із відносним пріоритетом, вузла мережі з повторною передачею пакетів. Розроблено наближену технологію оцінки якості обслуговування багатоканальних вузлів маршрутизації з відмовами та неоднорідним вхідним трафіком з пріоритетами. Отримані співвідношення для показників QoS дають можливість оцінити якість обслуговування UDP та TCP трафіків у вузлах мереж, врахувати їх відмінності та оптимізувати ресурси мережі. Показано, що врахування TCP трафіка, на відміну від стандартних моделей, які враховуються тільки UDP трафік, погіршує показники довжини черги при піковому навантаженні, а граф має ступінчасту форму, що відрізняє його від кривої, яку побудовано аналітично з використанням класичних формул СМО. У третьому розділі запропоновано комплексну математичну модель управління потоками пакетів. Розглянуто сценарій управління вузлом мережі, де доступно чотири черги, кожна здатна обслуговувати один із шістнадцяти потоків пакетів, кожен із них з власним набором характеристик якості обслуговування. Одним із ключових аспектів цієї системи є належний порядок приоритизації, який сприятиме ефективному розподілу ресурсів між потоками відповідно їх вимог до якості обслуговування. Визначено оптимальну стратегію для кожної черги у розподілі потоків пакетів. Для вирішення задачі застосовано техніку управління потоками, зокрема, використання вартісної функції для оптимізації, а також методи адаптивного керування розміром черг та розподілу навантаження. Виконано програмну симуляцію мережі вузла мережі з чергами із пріоритетами та управлінням потоками пакетів. Проведено аналіз шляхів передачі даних у мережі з урахуванням поточного навантаження та пріоритетів повідомлень. У четвертому розділі удосконалено методи формування трафіку вузла мережі, що гарантує показники якості обслуговування. Метод управління дисципліною обслуговування, запропонований у роботі, забезпечує мінімізацію максимальної ймовірності того, що довжина черги з урахуванням ваги відповідного потоку буде не нижчою за критичну. Розроблено метод управління ресурсом з урахуванням рівності середніх довжин черг. Запропоновано технологію визначення розподілу ресурсу процесора, оптимального, у розумінні рівності середніх тривалостей, очікування початку обслуговування. Протестовано розроблені методи управління обслуговуванням черг пакетів у вузлах мереж за сукупністю критеріїв, за допомогою симулятора OMNeT++. У висновках наведено основні результати наукової роботи щодо вирішення поставлених наукових задач дослідження. За результатами дослідження отримано такі наукові резульатти: 1. Вперше запропоновано вартісно-вагову модель управління обслуговуванням потоків пакетів за рахунок розподілу їх по чергам вузла мережі, яка враховує суперпозицію показників якості обслуговування QoS (Quality of Service) мережі, внутрішніх параметрів заголовку пакету та додаткових показників провайдерів Інтернет, кожному з яких задається вага. Використання запропонованої моделі із 11 показниками мережевих пакетів дозволило знизити затримку пакету при онлайн управлінняі рухомим об’єктом на 15.7% при загальному навантаженні на мережу 90% і більше. 2. Удосконалено марківські моделі обслуговування мережевого трафіку, шляхом врахування особливостей протоколу управління передачею TCP (Transmission Control Protocol) щодо гарантування доставки пакета та повторної передачі втрачених пакетів, що дозволило покращити точність розрахунку показників якості обслуговування QoS (Quality of Service), а саме: втрати пакетів на 3.83% та затримку пакетів на 4.63% при піковому навантаженні 90% від пропускної здатності. 3. Отримали подальший розвиток методи управління обслуговуванням черг, які, на відміну від відомих, встановлюють раціональний розподіл ресурсу системи передачі пакетів за критеріями: середня довжина черг з урахуванням пріоритетів - знижує ймовірність відкидання пакетів алгоритмом RED по всіх потоках; середня тривалість очікування початку обслуговування - покращує пропускну здатність вузла мережі; ймовірність того, що довжина максимальної з черг не перевищить критичну - збалансовує відкидання пакетів алгоритмом RED між усіма потоками, знижує коливання черг; середня кількість черг, довжина яких не менше критичної - збалансовує відгук для всіх користувачів. Дослідження, результати яких викладені в дисертаційній роботі, виконані на кафедрі «Системи інформації ім. В.О. Кравця» НТУ «Харківський політехнічний інститут» відповідно до завдань держбюджетної теми МОН України: Міжнародний проект за програмою ERASMUS+ (Project Number: 598236-EPP-1-2018-1-LT-EPPKA2-CBHE-SP) за темою «dComFra – Digital competence framework for Ukrainian teachers and other citizens» (термін виконання 2018-2021рр), в яких здобувач був виконавцем окремих етапів. За результатами дослідження підтверджено практичну та теоретичну цінність розроблених моделей та методів, надано практичні рекомендації, щодо застосування розроблених моделей та методів та розглянуто перспективи їх подальшого розвитку. The dissertation is devoted to the solution of an actual scientific and applied problem related to the development and further improvement of models and methods of queue management at peak loads to improve the quality of computer network service. The purpose of the dissertation is to develop mathematical models of network nodes and traffic models with guaranteed delivery of packets based on the mathematical apparatus of mass service Markov systems and queuing theory for solving the problems of computer network analysis and queue management in network nodes according to a set of criteria that improve indicators QoS (packet delay, packet loss). The object of research is queue management processes in computer networks at peak loads. The subject of research is models and methods of queue management in computer networks at peak loads. The introduction substantiates the relevance of improving the quality of service in computer networks, presents the connection of work with scientific programs, plans and topics, presents scientific novelty, presents the practical significance of the obtained results, provides information on the personal contribution of the recipient, presents a list of publications on the topic of the dissertation. In the first chapter, the scientific and technical problem of the quality of service in computer networks is formulated. An analysis of the principles of construction and functioning of modern computer networks has been carried out. The main network protocols and mechanisms for ensuring the quality of service have been studied, promising areas of research have been highlighted. The expediency of improving existing and developing new models and methods of queue management, especially under conditions of peak loads, is indicated. The choice of models and methods for further research is justified. The task of the dissertation research is formulated. In the second chapter, mathematical models of computer network nodes with a heterogeneous incoming flow of packets without priorities, a multi-channel network node with a heterogeneous incoming flow of packets with absolute priority, a multi-channel flow of packets with relative priority, and a network node with retransmission of packets are built. An approximate technology for evaluating the quality of service of multi-channel routing nodes with failures and heterogeneous incoming traffic with priorities has been developed. The obtained ratios for QoS indicators make it possible to evaluate the quality of service of UDP and TCP traffic in network nodes, take into account their differences and optimize network resources. It is shown that taking into account TCP traffic, unlike standard models that take into account only UDP traffic, worsens the indicators of the queue length at peak load, and the graph has a stepped shape, which distinguishes it from the curve that is built analytically using classical SMO formulas. In the third section, a complex mathematical model of packet flow management is proposed. A network node control scenario is considered where four queues are available, each capable of serving one of sixteen packet streams, each with its own set of QoS characteristics. One of the key aspects of this system is proper prioritization, which will facilitate the efficient allocation of resources between streams according to their quality of service requirements. The optimal strategy for each queue in the distribution of packet flows is determined. To solve the problem, the technique of flow management is applied, in particular, the use of a cost function for optimization, as well as methods of adaptive control of the size of queues and load distribution. A software simulation of the network of a network node with priority queues and packet flow management was performed. An analysis of data transmission paths in the network was carried out, taking into account the current load and message priorities. In the fourth chapter, the methods of network node traffic formation, which guarantees service quality indicators, are improved. The service discipline management method proposed in the work ensures the minimization of the maximum probability that the queue length, taking into account the weight of the corresponding flow, will not be lower than the critical one. A resource management method was developed taking into account the equality of average queue lengths. The technology for determining the distribution of the processor resource, which is optimal in the sense of the equality of the average durations, waiting for the start of service, is proposed. The developed methods of managing the service of packet queues in network nodes were tested according to a set of criteria, using the OMNeT++ simulator. The main results of the scientific work regarding the solution of the set scientific problems of the research are presented in the conclusions. According to the results of the research, the following scientific results were obtained: 1. For the first time, a value-weight model of packet flow service management by distributing them among network node queues is proposed, which takes into account the superposition of network QoS (Quality of Service) indicators, internal parameters of the packet header, and additional indicators of Internet providers, each of which is assigned a weight . The use of the proposed model with 11 indicators of network packets made it possible to reduce the packet delay during online control of a moving object by 15.7% with a total network load of 90% or more. 2. The Markov models of network traffic maintenance have been improved by taking into account the features of the TCP (Transmission Control Protocol) transmission control protocol in terms of guaranteeing packet delivery and retransmission of lost packets, which made it possible to improve the accuracy of calculating QoS (Quality of Service) indicators, namely: losses packets by 3.83% and packet delay by 4.63% at a peak load of 90% of the bandwidth. 3. Queue maintenance management methods have been further developed, which, unlike the known ones, establish a rational distribution of the resource of the packet transmission system according to the following criteria: the average length of queues taking into account priorities - reduces the probability of discarding packets by the RED algorithm on all streams; the average waiting time for the start of service - improves the bandwidth of the network node; the probability that the length of the maximum of the queues will not exceed the critical length - balances the rejection of packets by the RED algorithm between all flows, reduces queue fluctuations; the average number of queues, the length of which is not less than critical - balances the response for all users. The research, the results of which are presented in the dissertation, was carried out at the department "Information Systems named after V.O. Kravets" of NTU "Kharkiv Polytechnic Institute" in accordance with the tasks of the state budget topic of the Ministry of Education and Culture of Ukraine: International project under the ERASMUS+ program (Project Number: 598236-EPP-1-2018-1-LT-EPPKA2-CBHE-SP) on the topic "dComFra – Digital competence framework for Ukrainian teachers and other citizens" (implementation period 2018-2021), in which the applicant was the executor of individual stages. Based on the results of the study, the practical and theoretical value of the developed models and methods was confirmed, practical recommendations were given regarding the application of the developed models and methods, and the prospects for their further development were considered.