Monitoring distributed computing systems on the basis of the determined shortest paths and shortest hamiltonian cycles in a graph

Authors

  • Сергей Владимирович Листровой Ukrainian State University of Railway Transport Pl. Feuerbach, 7, Kharkov, Ukraine, 61050, Ukraine https://orcid.org/0000-0001-7568-4521
  • Сергей Владимирович Минухин Simon Kuznets Kharkiv National University of Economics Lenin av., 9-a, Kharkov, Ukraine, 61166, Ukraine https://orcid.org/0000-0002-9314-3750
  • Елена Сергеевна Листровая Kharkiv national aerospace University named after M. E. Zhukovsky, Chkalov St. 17, Kharkov, Ukraine, 61070, Ukraine

DOI:

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

Keywords:

distributed computing system (DCS), monitoring, agent, remote access, delay, graph

Abstract

The tasks of monitoring the Distributed Computing System (DCS) are associated with optimization of the order (sequence) of surveying the monitored objects, such as resources (clusters and cluster nodes), carried out tasks (downloads), communication channels, and database servers. The problems are solved due to the use of plug-ins that include programs to initialize the startup and operation of remote services (agents), while the latter provide control over the DCS performance. Since the size of each of the transmitted commands to initialize the remote services of the monitored objects is several kilobytes and there are thousands of the DCS-controlled nodes, the volume of the transmitted information reaches 4–5 Mbytes. The amount of the transmitted results of assessing the state of the monitored objects in the DCS, which can be about 412 per one object, and the volume of each object – about 4 Kbytes – largely affect the bandwidth of communication channels.

This accounts for the necessity to optimize the survey time for the monitored objects via minimizing the time for control over the DCS objects in real time. The problem is solved due to the method implemented in two stages: finding the shortest path and the shortest Hamiltonian cycle in a random graph describing the topology of the DCS communication channels. The proposed DCS-monitoring methods allow optimizing the survey time for the monitored objects in polynomial time and consequent improving the quality of performance and the quality of service provided to the DCS users in real time.

Author Biographies

Сергей Владимирович Листровой, Ukrainian State University of Railway Transport Pl. Feuerbach, 7, Kharkov, Ukraine, 61050

Professor

Department of specialization computer systems 

Сергей Владимирович Минухин, Simon Kuznets Kharkiv National University of Economics Lenin av., 9-a, Kharkov, Ukraine, 61166

Candidate of technical Sciences,Professor

Department of Information Systems

Елена Сергеевна Листровая, Kharkiv national aerospace University named after M. E. Zhukovsky, Chkalov St. 17, Kharkov, Ukraine, 61070

Candidate of technical Sciences,associate ProfessorDepartment of Economics and marketing

References

  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.

Downloads

Published

2015-12-22

How to Cite

Листровой, С. В., Минухин, С. В., & Листровая, Е. С. (2015). Monitoring distributed computing systems on the basis of the determined shortest paths and shortest hamiltonian cycles in a graph. Eastern-European Journal of Enterprise Technologies, 6(4(78), 32–45. https://doi.org/10.15587/1729-4061.2015.56247

Issue

Vol. 6 No. 4(78) (2015): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

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

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.