1. На главную
  2. Электронные версии
  3. Известия РАН. Теория и системы управления
  4. № 5, 2023

Известия РАН. Теория и системы управления, 2023, № 5, стр. 91-102

УПРАВЛЕНИЕ РАСПРЕДЕЛЕНИЕМ РЕСУРСОВ ПРИ ВЫРАВНИВАНИИ НАГРУЗОК И МЕЖУЗЛОВЫХ ПОТОКОВ В МНОГОПОЛЬЗОВАТЕЛЬСКОЙ СЕТИ

Ю. Е. Малашенко a, И. А. Назарова a, *

a ФИЦ ИУ РАН
Москва, Россия

* E-mail: irina-nazar@yandex.ru

Поступила в редакцию 29.03.2023
После доработки 12.04.2023
Принята к публикации 05.06.2023

Аннотация

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

Список литературы

  1. Малашенко Ю.Е., Назарова И.А. Анализ распределения предельных нагрузок в многопользовательской сети // Информатика и ее применения. 2021. Т. 15. Вып. 4. С. 19–24.

  2. Малашенко Ю.Е., Назарова И.А. Оценки распределения ресурсов в многопользовательской сети при равных межузловых нагрузках // Информатика и ее применения. 2023. Т. 17. Вып. 1. С. 21–26.

  3. Малашенко Ю.Е., Назарова И.А. Анализ загрузки многопользовательской сети при расщеплении потоков по кратчайшим маршрутам // Информатика и ее применения. 2023. Т. 17. Вып. 3. С. 19–24.

  4. 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.

  5. Luss H. Equitable Resource Allocation: Models, Algorithms, and Applications. Hoboken: John Wiley & Sons, 2012.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. Kabadurmus O., Smith A.E. Multicommodity k-Splittable Survivable Network Design Problems with Relays // Telecommun. Syst. 2016. V. 62. Iss. 1. P. 123–133.

  11. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л. и др. Алгоритмы: построение и анализ. М.: Вильямс, 2005.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Известия РАН. Теория и системы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал