Email this article Resource Distribution and Balancing Flows in a Multiuser Network
- Authors: Malashenko Y.E.1, Nazarova I.A.1
-
Affiliations:
- Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
- Issue: No 5 (2023)
- Pages: 91-102
- Section: СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
- URL: https://journals.rcsi.science/0002-3388/article/view/140345
- DOI: https://doi.org/10.31857/S0002338823050128
- EDN: https://elibrary.ru/NYWDTB
- ID: 140345
Cite item
Open Access
Access granted
Subscription Access
Abstract
Balancing strategies for control flows and resources are studied in computational experiments on a mathematical model of a multiuser network. An algorithmic scheme for sequentially solving a chain of lexicographically ordered problems of finding nondiscriminating the maximin distributions of flows is proposed. A procedure for step-by-step equalizing the splitting of internodal flows along all the existing shortest paths is developed. At each iteration, a part of the available resource is distributed equally among all pairs of correspondent nodes for which there is a possibility of flow transmission. The results obtained in the course of the experiments make it possible to trace the dynamics of changes in the capacity of the edges, up to reaching the maximum network load. Bottlenecks in various networks are analyzed and compared with a monotonic increase in the flows. Special diagrams are given.
About the authors
Yu. E. Malashenko
Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
Email: irina-nazar@yandex.ru
Россия, Москва
I. A. Nazarova
Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
Author for correspondence.
Email: irina-nazar@yandex.ru
Россия, Москва
References
- Малашенко Ю.Е., Назарова И.А. Анализ распределения предельных нагрузок в многопользовательской сети // Информатика и ее применения. 2021. Т. 15. Вып. 4. С. 19–24.
- Малашенко Ю.Е., Назарова И.А. Оценки распределения ресурсов в многопользовательской сети при равных межузловых нагрузках // Информатика и ее применения. 2023. Т. 17. Вып. 1. С. 21–26.
- Малашенко Ю.Е., Назарова И.А. Анализ загрузки многопользовательской сети при расщеплении потоков по кратчайшим маршрутам // Информатика и ее применения. 2023. Т. 17. Вып. 3. С. 19–24.
- Salimifard K., Bigharaz S. The Multicommodity Network Flow Problem: State of the Art Classification, Applications, and Solution Methods // J. Oper. Res. Int. 2020. V. 22. Iss. 2. P. 1–47.
- Luss H. Equitable Resource Allocation: Models, Algorithms, and Applications. Hoboken: John Wiley & Sons, 2012.
- Balakrishnan A., Li G., Mirchandani P. Optimal Network Design with End-to-End Service Requirements // Oper. Res. 2017. V. 65. Iss. 3. P. 729–750.
- Bialon P. A Randomized Rounding Approach to a k-Splittable Multicommodity Flow Problem with Lower Path Flow Bounds Affording Solution Quality Guarantees // Telecommun. Syst. 2017. V. 64. Iss. 3. P. 525–542.
- Caramia M., Sgalambro A. A Fast Heuristic Algorithm for the Maximum Concurrent k-splittable Flow Problem // Optim. Lett. 2010. V. 4. Iss. 1. P. 37–55.
- Melchiori A., Sgalambro A. A Branch and Price Algorithm to Solve the Quickest Multicommodity k-Splittable Flow Problem // European J. Oper. Res. 2020. V. 282. Iss. 3. P. 846–857.
- Kabadurmus O., Smith A.E. Multicommodity k-Splittable Survivable Network Design Problems with Relays // Telecommun. Syst. 2016. V. 62. Iss. 1. P. 123–133.
- Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л. и др. Алгоритмы: построение и анализ. М.: Вильямс, 2005.
Supplementary files
