10.14489/vkit.2020.03.pp.003-010

DOI: 10.14489/vkit.2020.03.pp.003-010

Щерба Е. В., Литвинов Г. А.
АЛГОРИТМ ПОИСКА ОПТИМАЛЬНОГО МАРШРУТА ДЛЯ ОБЕСПЕЧЕНИЯ КАЧЕСТВА ОБСЛУЖИВАНИЯ В ПЕРЕОГРАНИЧЕННЫХ СЛУЧАЯХ
(c. 3-10)

Аннотация. Предложены точный и эвристический алгоритм для задачи поиска маршрутов, удовлетворяющих максимально возможному количеству заданных аддитивных ограничений. Указанная задача является актуальной для обеспечения качества обслуживания в условиях множества накладываемых ограничений при маршрутизации пакетов в сетях с динамической топологией. Разработанные алгоритмы продемонстрированы на примерах, получены оценки их временной сложности. Показано, что эвристический алгоритм может быть использован на практике в целях нахождения оптимального маршрута при меньшем количестве вычислительных затрат.

Ключевые слова: многокритериальная маршрутизация; самоорганизующиеся сети; качество обслуживания; дискретная оптимизация.

Shcherba E. V., Litvinov G. A.
AN ALGORITHM FOR QOS-AWARE ROUTING IN THE OVER-CONSTRAINED CASE
(pp. 3-10)

Abstract. In recent years, а large number of researchers and designers of routing protocols for dynamically organized networks have focused on security and quality of service issues. The features of dynamically organized networks cause а significant increase in the number of criteria used to evaluate the quality of routes. Given the multiple constraints imposed simulta11eously on the routes in dynamically organized networks, the problem of packet routing with quality of service provision often becomes over-constrained. One of the possible solutions under these conditions is to find а route that satisfies the maximum possible number of constraints. In our previous works, we proposed and investigated the exact effective algorithm for solving this problem in the case of concave routing metrics. In this paper, we propose an algorithmic solution to this problem in the general case. The algorithm for solving the formulated problem proposed in this paper is а modification of the Dijkstraʼs algorithm, which ensures the storage of all non-dominated paths to the considered vertex. The theoretical evaluation of the time complexity of the proposed exact algorithm is also presented in the paper. It is shown that the proposed heuristic algorithm can be used in practice to find the optimal route with fewer computational costs. The proposed exact and heuristic algorithms are demonstrated bу examples.

Keywords: Multi-constrained routing; Self-organizing networks; Quality of service; Discrete optimization.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Е. В. Щерба, Г. А. Литвинов (Омский государственный технический университет, Омск, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

E. V. Shcherba, G. A. Litvinov (Omsk State Technical University, Omsk, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Корячко В. П., Перепелкин Д. А. Корпоративные сети: технологии, протоколы, алгоритмы. М.: Горячая линия – Телеком, 2011. 219 с.
2. Hanzo L., Tafazolli R. А Survey of QoS Routing Solutions for Mobile Ad Hoc Networks // IEEE Communications Surveys & Tutorials. 2007. V. 9, No. 2. Р. 50 – 70.
3. Щерба Е. В., Литвинов Г. А., Щерба М. В. Задача обеспечения качества обслуживания на базе протокола маршрутизации OLSR: подходы, алгоритмы, решения // Доклады ТУСУР. 2019. Т. 22, № 1. С. 55 – 65.
4. Щербина О. А. Удовлетворение ограничений и программирование в ограничениях // Интеллектуальные системы. 2011. Т. 15, № 1–4. С. 53 – 170.
5. Shcherba E. V., Litvinov G. A. On an Optimal Solution for Multiconstrained Routing Problem in the Overconstrained Case // Moscow Workshop on Electronic and Networking Technologies (МWENT–2018). Moscow, 2018. Р. 1 – 4.
6. Chen S., Nahrstedt К. On Finding Multiconstrained Paths // Proc. of the IEEE Intemational Conference on Communications (ICC). Atlanta, 1998. V. 2. Р. 874 – 879.
7. Щерба Е. В., Литвинов Г. А., Щерба М. В. Проблема обеспечения качества обслуживания при маршрутизации пакетов в динамически организуемых телекоммуникационных сетях для переограниченных случаев // Электронные средства и системы управления. Томск: ТУСУР, 2018. Т. I. С. 28 – 31.
8. Shcherba E. V., Litvinov G. A. Modeling the Optimal Path for QoS-aware Routing in the Over-Constrained Case // 2018 Dynamics of Systems, Mechanisms and Machines (Dynamics). Omsk, 2018. Р. 1 – 5.
9. Van Mieghem Р., Kuipers F. A. Concepts of Exact QoS Routing Algorithms // EEE/ACM Transactions on Networking. 2004. V. 12, No. 5. Р. 851 – 864.
10. Korkmaz Т., Кrunz М. Multiconstrained Optimal Path Selection // Proc. of the Conference on Computer Communications, 2001, IEEE Infocom. Alaska, 2001. V. 2. Р. 834 – 843.

Eng

1. Koryachko V. P., Perepelkin D. A. (2011). Corporate networks: technologies, protocols, algorithms. Moscow: Goryachaya liniya – Telekom. [in Russian language]
2. Hanzo L., Tafazolli R. (2007). А Survey of QoS Routing Solutions for Mobile Ad Hoc Networks. IEEE Communications Surveys & Tutorials, Vol. 9, (2), pp. 50 – 70.
3. Shcherba E. V., Litvinov G. A., Shcherba M. V. (2019). The task of ensuring quality of service based on the OLSR routing protocol: approaches, algorithms, solutions. Doklady TUSUR, Vol. 22, (1), pp. 55 – 65. [in Russian language]
4. Shcherbina O. A. (2011). Constraint Satisfaction and Constraint Programming. Intellektual'nye sistemy, Vol. 15, (1–4), pp. 53 – 170. [in Russian language]
5. Shcherba E. V., Litvinov G. A. (2018). On an Optimal Solution for Multiconstrained Routing Problem in the Overconstrained Case. Moscow Workshop on Electronic and Networking Technologies (МWENT–2018), pp. 1 – 4. Moscow.
6. Chen S., Nahrstedt К. (1998). On Finding Multiconstrained Paths. Proceedings of the IEEE Intemational Conference on Communications (ICC), Vol. 1, pp. 874 – 879. Atlanta.
7. Shcherba E. V., Litvinov G. A., Shcherba M. V. (2018). The problem of providing quality of service when routing packets in dynamically organized telecommunication networks for limited cases. Electronic tools and control systems, Vol. I, pp. 28 – 31. Tomsk: TUSUR. [in Russian language]
8. Shcherba E. V., Litvinov G. A. (2018). Modeling the Optimal Path for QoS-aware Routing in the Over-Constrained Case. 2018 Dynamics of Systems, Mechanisms and Machines (Dynamics), pp. 1 – 5. Omsk.
9. Van Mieghem Р., Kuipers F. A. (2004). Concepts of Exact QoS Routing Algorithms. EEE/ACM Transactions on Networking, Vol. 12, (5), pp. 851 – 864.
10. Korkmaz Т., Кrunz М. (2001). Multiconstrained Optimal Path Selection. Proceedings of the Conference on Computer Communications, IEEE Infocom, Vol. 2, pp. 834 – 843. Alaska.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

DOI: 10.14489/vkit.2020.03.pp.003-010

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

DOI: 10.14489/vkit.2020.03.pp.003-010

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.