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

Автор(и)

  • Сергей Владимирович Листровой Український державний університет залізничного транспорту Пл. Фейєрбаха, 7, м. Харків, Україна, 61050, Україна https://orcid.org/0000-0001-7568-4521
  • Сергей Владимирович Минухин Харківський національний економічний університет імені Семена Кузнеця Пр. Леніна, 9-а, м. Харків, Україна, 61166, Україна https://orcid.org/0000-0002-9314-3750
  • Елена Сергеевна Листровая Національний аерокосмічний університет ім. М. Є. Жуковського, вул. Чкалова, 17, м. Харків, Україна, 61070, Україна

DOI:

https://doi.org/10.15587/1729-4061.2015.56247

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

розподілена обчислювальна система, моніторинг, агент, віддалений доступ, затримка, граф

Анотація

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

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

Сергей Владимирович Листровой, Український державний університет залізничного транспорту Пл. Фейєрбаха, 7, м. Харків, Україна, 61050

Доктор технічних наук, професор

Кафедра спеціалізованих комп’ютерних систем

Сергей Владимирович Минухин, Харківський національний економічний університет імені Семена Кузнеця Пр. Леніна, 9-а, м. Харків, Україна, 61166

Кандидат технічних наук, професор

Кафедра інформаційних систем

Елена Сергеевна Листровая, Національний аерокосмічний університет ім. М. Є. Жуковського, вул. Чкалова, 17, м. Харків, Україна, 61070

Кандидат технічних наук,доцентКафедра економіки і маркетингу

Посилання

  1. Nagios – The Industry Standard in IT Infrastructure Monitoring. Available at: http://www.nagios.org
  2. Icinga. Open Source Monitoring Available at: https://www.icinga.org
  3. Mynukhyn S. V. (2015). Informacyonnye tekhnologhii realyzacii dvukhurovnevoj modeli planyrovanyja paketov zadanyj v raspredelennoj vychyslyteljnoj systeme na osnove reshenyja zadachy o naimenjshem pokrytii. Systemy upravlinnja, navighaciji ta zv'jazku, 1 (33), 111–115.
  4. Ponomarenko, V. S., Lystrovoj, S. V., Mynukhyn, S. V. et al. (2008). Metody i modeli planirovanyja resursov v GRID-systemakh. Kharkov: INZhEK, 408.
  5. Kofman, A., Anry-Labroder, A. (1977). Metody i modeli issledovanyja operacyj. Celochyslennoe proghrammyrovanye. Moscow: Mir, 236.
  6. Vaghner, Gh. (1973). Osnovy issledovanyja operacij. Moscow: Myr, 2, 489.
  7. Richard, B. (1962). Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM, 9, 61–63. doi: 10.1145/321105.321111
  8. Held, M., Karp, Richard, M. (1971). The Traveling-Salesman Problem and Minimum Spanning Trees. Mathematical Programming, 1, 6–25. doi: 10.1007/bf01584070
  9. Gurevich, Y., Shelah, S. (1987). Expected computation time for Hamiltonian path problem. SIAM Journal on Computing, 16, 486–502. doi: 10.1137/0216034
  10. Bjorklund, A., Husfeldt, T. (2008). Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings. Algorithmica, 52, 226–249. doi: 10.1007/s00453-007-9149-8
  11. Koivisto, M., Parviainen, P. (2010). A space-time tradeoff for permutation problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10. Austin, 484–492. doi: 10.1137/1.9781611973075.41
  12. Kohn, S., Gottlieb, A., Kohn, M. (1977). A generating function approach to the traveling salesman problem. In Proceedings of the 1977 annual conference, ACM ’77. New York, USA, 294–300. doi: 10.1145/800179.810218
  13. Karp, R. M. (1982). Dynamic Programming Meets the Principle of Inclusion and Exclusion. Operations Research Letters, 1 (2), 49–51. doi: 10.1016/0167-6377(82)90044-x
  14. Bax, E., Franklin, J. (1996). A Finite-Difference Sieve to Count Paths and Cycles by Length. Information Processing Letters, 60, 171–176. doi: 10.1016/s0020-0190(96)00159-7
  15. Bj¨orklund, A. (2010). Determinant Sums for Undirected Hamiltonicity. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, FOCS’10. Washington, DC, 173–182. doi: 10.1109/FOCS.2010.24
  16. Woeginger, G., J. (2008). Open Problems Around Exact Algorithms. Discrete Appl. Math., 156, 397–405. doi: 10.1016/j.dam.2007.03.023
  17. Eppstein, D. (2003). The traveling salesman problem for cubic graphs. Algorithms and Data Structures. Lecture Notes in Computer Science, 2748, 307–318. doi: 10.1007/978-3-540-45078-8_27
  18. Iwama, K., Nakashima, T. (2007). An improved exact algorithm for cubic graph TSP. Computing and Combinatorics. Lecture Notes in Computer Science, 4598, 108–117. doi: 10.1007/978-3-540-73545-8_13
  20. Gebauer, H. (2011). Finding and enumerating hamilton cycles in 4-regular graphs. Theoretical Computer Science, 412 (35), 4579–4591. doi: 10.1016/j.tcs.2011.04.038
  21. Mohyla, I. A., Lobach, I. I., Yakymets', O. A. (2014). Influence of parameters of the ant colony algorithm on the traveling salesman problem solution. Eastern-European Journal of Enterprise Technologies, 4 (4 (70)), 18–23. doi: 10.15587/1729-4061.2014.26290
  22. Boronikhina, E. A., Sibiryakova, V. A. (2014). Sravnenie metodov resheniya zadachi kommivoyazhera. Informatsyonnye tekhnolohii i matematicheskoe modelirovanie I74 (ITMM–2014). Tomsk: izd-vo Tom. un-ta, 3, 18–21.
  24. Kureychyk, V. M., Martynov, A. V. (2014). Ob alhoritmakh resheniya zadachi kommivoyazhera s vremennymi ohranicheniyami. Informatika, vycheslitel'naya tekhnika i ynzhenernoe obrazovanie, 1 (16), 1−13.
  25. Chastykova, V. A., Vlasov, K. A. (2013). Razrabotka i sravnitel'nyi analiz evristicheskikh alhoritmov dlya poiska naimen'sheho hamil'tonova tsikla v polnom hrafe. Fundamental'nye issledovaniya, 10, 63–67.
  26. Li, Y. A New Exact Algorithm for Traveling Salesman Problem with Time Complexity Interval (O(n4), O(n3*2n)). Available at: http://arxiv.org/abs/1412.2437
  27. Seraya, O. V. (2013). Analiz metodov resheniya transportnykh zadach so sluchainymi stoimostyami perevozok. Informatsionno-upravlyayushchie sistemy na zheleznodorozhnom transporte, 4, 42–45.
  28. Listrovoy, S. V., Gul, Yu. (1999). Method of Minimum Covering Problem Solution on the Basis of Rank Approach. Engineering Simulation, 17, 73–89.
  29. Listrovoy, S. V., Golubnichiy, D. Yu., Listrovaya, E. S. (1999). Solution method on the basis of rank approach for integer linear problems with boolean variables. Engineering Simulation, 16, 707–725.

##submission.downloads##

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

2015-12-22

Як цитувати

Листровой, С. В., Минухин, С. В., & Листровая, Е. С. (2015). Розробка методу моніторингу розподіленої обчислювальної системи на основі визначення найкоротших шляхів і найкоротших гамільтонових циклів у графі. Eastern-European Journal of Enterprise Technologies, 6(4(78), 32–45. https://doi.org/10.15587/1729-4061.2015.56247

Номер

Том 6 № 4(78) (2015): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2015 Сергей Владимирович Листровой, Сергей Владимирович Минухин, Елена Сергеевна Листровая

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.