Maximum flows characteristics of a multiuser communication network under a change in the capacity of cuts

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

doi:10.31857/S0002338825040086

Maximum flows characteristics of a multiuser communication network under a change in the capacity of cuts

Authors: Malashenko Y.Е.¹, Nazarova I.A.¹
Affiliations:
1. Federal Research Center “Computer Science and Control” of the RAS
Issue: No 4 (2025)
Pages: 122–131
Section: SYSTEM ANALYSIS AND OPERATIONS RESEARCH
URL: https://jdigitaldiagnostics.com/0002-3388/article/view/689640
DOI: https://doi.org/10.31857/S0002338825040086
EDN: https://elibrary.ru/BPBGRV
ID: 689640

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription or Fee Access

Abstract
Full Text
About the authors
References
Supplementary files
Statistics

Abstract

The maximum indicators of the functionality of a multiuser communication system are investigated under a change in the capacity of network edges. Based on the transmission routes of the maximum flows of the same type, the minimum cuts of the network are determined. The influence of changes in the capacity of the cut edges on the maximum allowable internodal flows under monopoly control modes is studied. The maximum values of the internodal flows correspond to the corners of the set of allowable flows satisfying the constraints of the model. A convex combination of vectors corresponding to the corners is used to estimate the relative changes in network characteristics during deformation of the set of feasible flows. Multi-criteria guaranteed estimates of the maximum feasible deviations from the reference indicators of the network functioning are formulated. Summary diagrams for networks with various structural features are provided.

Keywords

multicommodity flow model of network, guaranteed damage estimates, dominant minimum cut edges

Full Text

About the authors

Yu. Е. Malashenko

Federal Research Center “Computer Science and Control” of the RAS

Email: irina-nazar@yandex.ru
Russian Federation, Moscow

I. A. Nazarova

Federal Research Center “Computer Science and Control” of the RAS

Author for correspondence.
Email: irina-nazar@yandex.ru
Russian Federation, Moscow

References

Пехтерев С.В., Макаренко С.И., Ковальский А.А. Описательная модель системы спутниковой связи Starlink // Системы управления, связи и безопасности. 2022. № 4. С. 190-255.
Малашенко Ю.Е., Назарова И.А. Сравнительный анализ показателей функционирования сети при повреждении узлов // Информатика и ее применения. 2024. Т. 18. Вып. 3. С. 52–60.
Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
Данскин Дж.М. Теория максимина и ее приложение к задачам распределения вооружения. М.: Сов. радио, 1970.
Йенсен П., Барнес Д. Потоковое программирование. М.: Радио и связь, 1984.
Лотов А.В., Поспелова И. И. Многокритериальные задачи принятия решений. М.: Макс Пресс, 2008.
Ogryczak W., Luss H., Pioro M., Nace D., Tomaszewski A. Fair Optimization and Networks: a survey // J. Appl. Math. 2014. V. 25. P. 1–25.
Фрэнк Г., Фриш М. Сети, связь и потоки. М.: Связь, 1978.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л. и др. Алгоритмы: построение и анализ. 2-е изд. М.: Вильямс, 2010.