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

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

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

Об авторах

Ю. Е. Малашенко

ФИЦ ИУ РАН

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

И. А. Назарова

ФИЦ ИУ РАН

Автор, ответственный за переписку.
Email: irina-nazar@yandex.ru
Россия, Москва

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

  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.

Дополнительные файлы


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