Resource Distribution and Balancing Flows in a Multiuser Network

Yu. E. Malashenko; Малашенко Ю. Е.; I. A. Nazarova; Назарова И. А.

doi:10.31857/S0002338823050128

Resource Distribution and Balancing Flows in a Multiuser Network

作者: Malashenko Y.¹, Nazarova I.¹
隶属关系:
1. Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
期: 编号 5 (2023)
页面: 91-102
栏目: СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
URL: https://journals.rcsi.science/0002-3388/article/view/140345
DOI: https://doi.org/10.31857/S0002338823050128
EDN: https://elibrary.ru/NYWDTB
ID: 140345

如何引用文章

全文:

开放存取

##reader.subscriptionAccessGranted##
受限制的访问

订阅存取

详细
作者简介
参考
补充文件
统计

详细

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.

作者简介

Yu. Malashenko

Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia

Email: irina-nazar@yandex.ru
Россия, Москва

I. Nazarova

Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia

编辑信件的主要联系方式.
Email: irina-nazar@yandex.ru
Россия, Москва

参考

Малашенко Ю.Е., Назарова И.А. Анализ распределения предельных нагрузок в многопользовательской сети // Информатика и ее применения. 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.