Informatics and Applications
2023, Volume 17, Issue 3, pp 33-38
MULTIUSER NETWORK LOAD ANALYSIS BY SPLITTING FLOWS ALONG THE SHORTEST ROUTES
- Yu. E. Malashenko
- I. A. Nazarova
Abstract
In computational experiments on a multicommodity network model, two ways of transmitting flows of different types along shortest routes are investigated. In the first case, the transmitted internodal flows are equal in magnitude. In the other - a nondiscriminatory distribution is defined in which all pairs of nodes are distributed the same resources. The total load of the network edges resulting from the simultaneous transmission of all internodal flows is considered to be given. The proposed method allows one to obtain guaranteed estimates of the specific resource costs of the network and the maximum feasible load of the edges while transmitting split internodal flows along the shortest routes found. The results of a comparative analysis of the equalization distribution of flows and resources in networks with different structural features are given. The algorithmic scheme has a polynomial estimate of the required number of operations.
[+] References (11)
- Malashenko, Y. E., and I. A. Nazarova. 2022. Estimate of resource distribution with the shortest paths in the multi-user network. J. Comput. Sys. Sc. Int. 61(4):599-610. doi: 10.1134/S106423072204013X.
- Malashenko, Y. E., and I. A. Nazarova. 2022. Analysis of the load distribution and internodal flows under different routing strategies in a multiuser network. J. Comput. Sys. Sc. Int. 61(6): 970-980. doi: 10.1134/ S1064230722060132.
- Malashenko, Y. E., and I. A. Nazarova. 2023. Quantitative analysis of flow distributions in a multi-user telecommunication network. J. Comput. Sys. Sc. Int. 62(2): 324-335.
- Salimifard, K., and S. Bigharaz. 2020. The multicommodity network flow problem: State of the art classification, applications, and solution methods. Operational Research 22(1):1-47. doi: 10.1007/s12351-020-00564-8.
- Luss, H. 2012. Equitable resource allocation: Models, algorithms, and applications. Hoboken, NJ: John Wiley & Sons. 376 p.
- Balakrishnan, A., G. Li, and P. Mirchandani. 2017. Optimal network design with end-to-end service requirements. Oper. Res. 65(3):729-750. doi: 10.1287/opre.2016.1579.
- Caramia, M., and A. Sgalambro. 2010. A fast heuristic algorithm for the maximum concurrent k-splittable flow problem. Optim. Lett. 4(1):37-55. doi: 10.1007/s11590- 009-0147-4.
- Kabadurmus, O., and A. E. Smith. 2016. Multicommodity k-splittable survivable network design problems with relays. Telecommun. Syst. 62(1):123-133. doi: 10.1007/ s11235-015-0067-9.
- Bialon, P. 2017. A randomized rounding approach to a k-splittable multicommodity flow problem with lower path flow bounds affording solution quality guarantees. Telecommun. Syst. 64(3):525-542. doi: 10.1007/s11235- 016-0190-2.
- Melchiori, A., and A. Sgalambro. 2020. A branch and price algorithm to solve the quickest multicommodity k-splittable flow problem. Eur. J. Oper. Res. 282(3):846- 857. doi: 10.1016/j.ejor.2019.10.016.
- Cormen, T. H., C. E. Leiserson, R. L. Rivest, and C. Stein. 2001. Introduction to algorithms. 2nd ed. Cambridge, Lon-don: The MIT Press. 1180 p.
[+] About this article
Title
MULTIUSER NETWORK LOAD ANALYSIS BY SPLITTING FLOWS ALONG THE SHORTEST ROUTES
Journal
Informatics and Applications
2023, Volume 17, Issue 3, pp 33-38
Cover Date
2023-10-10
DOI
10.14357/19922264230305
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
multicommodity flow model; distribution of internodal flows and loads; network peak load
Authors
Yu. E. Malashenko  and I. A. Nazarova
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|