Метод адаптивного балансування навантаження в кластерних системах військового призначення на основі рівноваги Неша

Автор(и)

  • В. Фесьоха Військовий інститут телекомунікацій та інформатизації імені Героїв Крут, Україна
  • Є. Нерознак Військовий інститут Телекомунікацій та інформатизації імені Героїв Крут, Україна
  • О. Сова Військовий інститут Телекомунікацій та інформатизації імені Героїв Крут, Україна
  • О. Нестеров Військовий інститут телекомунікацій та інформатизації імені Героїв Крут, Україна

DOI:

https://doi.org/10.33099/2304-2745/2022-3-76/101-110

Ключові слова:

Балансування навантаження; кластер; теорія ігор; рівновага Неша; імовірнісний розподіл; знаходження оптимуму.

Анотація

В умовах постійного зростання попиту на інформатизацію усіх сфер життєдіяльності суспільства залишається відкритим питання надійного та стабільного функціонування інформаційних систем/сервісів (ІС), що надають послуги користувачам у режимі реального часу.У даному контексті особливої уваги заслуговує стабільне (неперервне) функціонування ІС критичної інфраструктури держави, зокрема ІС військового призначення.

Одним з можливих вирішень завдань даного класу є концепція теорії математичних моделей прийняття оптимальних рішень в умовах конфлікту – рівновага Неша. Це така множина стратегій або дій у грі з двома чи більше гравцями, згідно з якими кожен учасник реалізує оптимальну стратегію, передбачаючи дії суперників, при якій жоден із учасників не може збільшити виграш, змінивши вибір стратегії в односторонньому порядку, коли інші учасники не змінюють свого вибору.

Метою статтіє удосконалення методу адаптивного балансування навантаження кластерної системи військового призначення на основі рівноваги Неша для досягнення стійкої рівноваги оптимального використання серверних ресурсів із максимальною конвергенцією до соціального оптимуму.

Запропоновано підхід, який дозволяє вирішити описану у статті проблематику:

пошук рівноваги у змішаних стратегіях завжди має рішення;

кількість гравців обмежено біматричною грою, що дозволяє знаходити рівновагу Неша за досить короткий час;

метод ефективно адаптується до динаміки значень усіх розглянутих впливових на процес балансування навантаження факторів;

виведення з ладу одного із серверів не призводить до втрати завдань у цілому, які йому було делеговано, втрачається лише їх частина (можливо відновити за контрольною сумою).

Отримані результати відповідають актуальним вимогам до функціонування ІС критичної інфраструктури держави, зокрема ІС військового призначення у контексті їх стабільності (неперервності) та надійності.

Біографії авторів

В. Фесьоха, Військовий інститут телекомунікацій та інформатизації імені Героїв Крут

доктор філософії

Є. Нерознак, Військовий інститут Телекомунікацій та інформатизації імені Героїв Крут

Y. Neroznak

О. Сова, Військовий інститут Телекомунікацій та інформатизації імені Героїв Крут

доктор технічних наук, старший науковий співробітник

О. Нестеров, Військовий інститут телекомунікацій та інформатизації імені Героїв Крут

доктор філософії

Посилання

Сервіс публічної транснаціональної корпорації Google. Google Trends. URL: https://trends.google.com.ua/trends/explore?date=today%205-y (дата звернення: 08.09.2022).

Про національну безпеку України : Закон України від 21.06.2018 р. № 2469-VIII // Відомості Верховної Ради. 2018. № 31. Ст. 241.

Фесьоха В., Фесьоха Н. Модель нечіткої автентифікації користувачів інформаційних систем органів військового управління на основі поведінковоії біометрії // Захист інформації (НАУ). 2021. Т. 23, № 2. С. 116–123.

Convergence Time to Nash Equilibria. Eyal Even-Dar, Alex Kesselman, and Yishay Mansour School of Computer Science, Tel-Aviv University. 2003.

Comparing Nash equilibria to Optimal Solutions in the Load Balancing Game with randomized strategies. CS 684 Algorithmic Game Theory Scribe: Mateo Restrepo Instructor: Eva Tardos February 23, 2004.

Congestion Games with Player-Specific Payoff Functions. Igal Milchtaich, Department of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel Received October 9, 1993.

Strong price of anarchy. Nir Andelman, Michal Feldman, Yishay Mansour. Games and Economic Behavior 65 (2009) 289–317.

Strong Price of Anarchy for Machine Load Balancing. Amos Fiat, Haim Kaplan, Meital Levy, and Svetlana Olonetsky. International Colloquium on Automata, Languages, and Programming ICALP 2007: Automata, Languages and Programming.Tel Aviv University. Р. 583–594.

Chen B., Li S., Zhang Y. Strong stability of Nash equilibria in load balancing games // Sci. China Math. 2014. Vol. 57. Р. 1361–1374. URL: https://doi.org/10.1007/s11425-014-4814-2 (дата звернення: 08.09.2022).

Baruch Awerbuch, Yossl Azar, Yossl Richter, Dekel Tsur. Tradeoffs in worst-case equilibria // Theoretical Computer Science. 2006. Vol. 361. Р. 200–209. URL: https://doi.org/10.1016/ j.tcs.2006.05.010 (дата звернення: 09.09.2022).

Vöcking B. (2007). Selfish Load Balancing. In N. Nisan, T. Roughgarden, E. Tardos, & V. Vazirani (Eds.) // Algorithmic Game Theory P. 517–542. URL: https://doi.org/10.1017/CBO9780511800481.022 (дата звернення: 09.09.2022).

Christodoulou G., Koutsoupias E., Nanavati A. Coordination Mech-anisms. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 2004. P. 345–357.

Christodoulou G., Koutsoupias E., Nanavati A. (2004). Coordination Mechanisms. In: Díaz J., Karhumäki J., Lepistö A., Sannella D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. URL: https://doi.org/10.1007/978-3-540-27836-8_31 (дата звернення: 09.09.2022).

Satish Penmatsa, Anthony T. Chronopoulos. Game-theoretic static load balancing for distributed systems // Journal of Parallel and Distributed Computing. Vol. 71, Issue 4. 2011. P. 537–555. URL: https://doi.org/10.1016/j.jpdc.2010.11.016 (дата звернення: 10.09.2022).

Ігнатенко О. П., Одобеску В. Я. Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель // Проблеми програмування. 2018. № 2–3. С. 75–82.

Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр. Санкт-Петербург : БХВ-Петербург, 2012. 432 с.

Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters // Communications of the ACM. January 2008. Vol. 51, Issue 1. P. 107–113. URL: https://doi.org/10.1145/ 1327452.1327492 (дата звернення: 10.09.2022).

Laemmel R. Google’s MapReduce Programming Model – Revisited. Data Programmability Team. Microsoft Corp. Redmond, WA, USA. URL: http://web.archive.org/web/20160304084223/http://userpages.unikoblenz.de/~laemmel/MapReduce/pape.pdf (дата звернення: 10.09.2022).

Диксит А., Скит С., Рейли-младший Д. Стратегические игры. Доступный учебник по теории игр / пер. с англ. Н. Яцюк ; науч. ред. А. Минько. Москва : Манн, Иванов и Фербер, 2017. 880 с.

Nash J. F. Equilibrium Points in N-Person Games // Proceedings of the National Academy of Scienses of the USA. 1950. Vol. 36. Р. 48–49.

Кремлев А. Г. Основные понятия теории игр : учебное пособие. Екатеринбург : Урал. ун-т, 2016. 144 с.

##submission.downloads##

Опубліковано

2023-03-14

Номер

Розділ

ЗАБЕЗПЕЧЕННЯ ДІЯЛЬНОСТІ ЗБРОЙНИХ СИЛ