Аnalysis and synthesis of communication network structures by state enumeration шethod

Authors

  • Kirill A. Batenkov Academy of Federal Guard Service of Russian Federation, 35, Priborostoitelnaya uh, Oryol, 302015, Russian Federation https://orcid.org/0000-0001-6083-1242

DOI:

https://doi.org/10.21638/11701/spbu10.2022.301

Abstract

Оne of the methods of analysis and synthesis of communication network structures is considered, based on the simplest approach to calculating the probability of connectivity - the method of iterating over the states of the network edges. Despite its significant drawback, which consists in the considerable complexity of the calculations carried out, it turns out to be quite in demand both at the stage of debugging new analysis methods and when performing the procedure of sequential synthesis of network structures. The proposed method of sequential synthesis can be presented in the form of stages, at each of which one or more edges (network elements) are added. An increase in the number of edges used leads to an increase in the number of variations of the connectivity functions of a graph with an added edge, and hence to an increase in the complexity of operations for calculating conditional probabilities. At the same time, such a complication makes it possible to more accurately solve the synthesis problem, since not in all situations the sequential addition of edges is equivalent to sorting through all possible alternatives. Both the described method of analyzing the structures of communication networks based on the enumeration of states and the synthesis method differ in the essential simplicity of the implementation of the processes of the calculations carried out. It is this circumstance that allows us to use these methods as reference. The accuracy of the calculations depends solely on the capabilities of hardware and software systems and is in no way limited directly by the method of sorting states. As a result, the calculation of the probability of connectivity with precision accuracy, which is typical for situations of comparative analysis of communication networks with the availability and survivability coefficients of individual network elements close to the threshold values, also turns out to be feasible on the basis of the methods considered.

Keywords:

network, graph structure, connectivity probability, coefficient of readiness, coefficient of operational readiness, complete state enumeration method

Downloads

Download data is not yet available.
 

References

Литература

Zuev К. М., Wu S., Beck J. L. General network reliability problem and its efficient solution by Subset Simulation // Probabilistic Engineering Mechanics. 2015. Vol. 40. P. 25-35.

Mussel C., Hopfensitz M., Kestler H. A. Boolnet package vignette. 2019. https://cran.r-project.org/web/packages/BoolNet/vignettes/BoolNet_package_vignette.Snw.pdf (дата обращения: 21.08.2021 г.).

Teruggia R. Reliability analysis of probabilistic networks: PhD thesis. Turin: Univ. of Turin, School of Doctorate in Science and High Technology, 2010. 214 p.

Дудник Б. Я., Овчаренко В. Ф. Надежность и живучесть систем связи / под ред. Б. Я. Дудника. М.: Радио и связь. 1984. 216 с.

ГОСТ Р 53111-2008. Устойчивость функционирования сети связи общего пользования. Требования и методы проверки. М.: Стандартинформ, 2009. 16 с.

Обоскалов В. П. Структурная надежность электроэнергетических систем: учеб. пособие. Екатеринбург: Урал. федерал. ун-т, 2012. 194 с.

Батенков К. А. Числовые характеристики структур сетей связи // Труды СПИИРАН. 2017. № 4. С. 5-28.

Филин Б. П. Методы анализа структурной надежности сетей связи. М.: Радио и связь, 1988. 208 с.

Батенков К. А. Общие подходы к анализу и синтезу структур сетей связи // Современные проблемы телекоммуникаций: Материалы Рос. науч.-технич. конференции. Новосибирск: Сиб. гос. ун-т телекоммуникаций и информатики, 2017. С. 19-23.

Половко А. М., Гуров С. В. Основы теории надежности. СПб.: БХВ-Петербург, 2006. 704 с.

Nozaki Т., Nakano Т., Wadayama Т. Analysis of breakdown probability of wireless sensor networks with unreliable relay nodes // 2017 IEEE Intern. Symposium Inf. Theory. Aachen, Germany, 2017. P. 481-485.

Takabe S., Nakano T., Wadayama T. Fault tolerance of random graphs with respect to connectivity: phase transition in logarithmic average degree // arXiv: 1712.07807, 2017.

Tutte W. T. Graph theory. Addison: Addison-Wesley Publishing Company, 1984. 423 p.

Yagan O., Makowski A. M. Zero-one laws for connectivity in random key graphs // IEEE Trans. Inf. Theory. 2012. Vol. 58. N 5. P. 2983-2999.

Батенков К. А. К вопросу оценки надежности двухполюсных и многополюсных сетей связи // Современные проблемы радиоэлектроники: сб. науч, трудов. Красноярск: Сиб. федерал. ун-т, 2017. С. 604-608.

Zhao J., Yagan О., Gligor V. Connectivity in secure wireless sensor networks under transmission constraints // Allerton Conference on Communication, Control, and Computing. 2014. P. 1-18.

Nucez A., Lacasa L., Valero E., Gymez J. P., Luque B. Detecting series periodicity with horizontal visibility graphs // Intern. J. Bifurc. Chaos. 2012. N 22. P. 1-10.

Zhang H. C., Xu D. L., Lu C., Qi E. R., Tian C., Wu Y. S. Connection effect on amplitude death stability of multi-module floating airport // Ocean Eng. 2017. P. 46-56.

Батенков К. А. Устойчивость сетей связи. Орел: Академия Федеральной службы охраны Российской Федерации, 2017. 277 с.

Brown J. I., Tufts J. On the roots of domination polynomials // Graphs Combin. 2014. N 30. P. 527-547.

Cox D. On network reliability: PhD thesis. Halifax, Nova Scotia: Dalhousie University, 2013. 209 p.

Батенков К. А. Об анализе живучести сетей связи на основе вероятностного подхода // Неделя науки СПбПУ: Материалы науч. конференции с международ. участием. Институт физики, нанотехнологий и телекоммуникаций. СПб.: Изд-во C.-Петерб. политехнич. ун-та, 2016. С. 6-8.

Huh J. H-vectors of matroids and logarithmic concavity // Adv. Math. 2015. N 270. P. 49-59.

Harris D. G., Srinivasan A. Improved bounds and algorithms for graph cuts and network reliability // Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM: ACM Press, 2014. P. 259-278.

Karger D. R. A fast and simple unbiased estimator for network (un)reliability // Proceedings of the 48th annual IEEE Symposium on Foundations of Computer Science. New Brunswick, New Jersey: IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, 2016. P. 635-644.

Батенков К. А. Особенности оценки качества функционирования сетей связи // Ресурсоэффективные системы в управлении и контроле: взгляд в будущее: сб. науч. трудов V Международ. конференции школьников, студентов, аспирантов, молодых ученых. В 3-х т. Т. 1. Томск: Изд-во Томск, политехнич. у-та, 2016. С. 30-31.

Mishra К., Trivedi К., Some R. Uncertainty analysis of the remote exploration and experimentation system // Journal of Spacecraft and Rockets, 2012. P. 1032-1042.

Ghosh R., Longo F., Frattini F., Russo S., Trivedi K. Scalable analytics for laaS cloud availability // IEEE Trans. on Cloud Computing. 2014. P. 57-70.

Карпов А. Г., Клемешев В. А., Куранов Д. Ю. Определение работоспособности системы, структура которой задана графом // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. Вып. 1. С. 41-49. https://doi.org/10.21638/11702/spbu10.2020.104


References

Zuev К. M., Wu S., Beck J. L. General network reliability problem and its efficient solution by Subset Simulation. Probabilistic Engineering Mechanics, 2015, vol. 40, pp. 25-35.

Mussel C., Hopfensitz M., Kestler H. A. Boolnet package vignette, 2019. https://cran.r-project.org/web/packages/BoolNet/vignettes/BoolNet_package_vignette.Snw.pdf (accessed: August 21, 2021).

Teruggia R. Reliability analysis of probabilistic networks. PhD thesis. Turin, Univ. of Turin, School of Doctorate in Science and High Technology Publ., 2010, 214 p.

Dudnik B. Ya., Ovcharenko V. F. Nadezhnost’ i zhivuchest’ sistem svyazi [The reliability and survivability of communication systems]. Moscow, Radio i svyaz’ Publ., 1984, 216 p. (In Russian)

GOST R 53111-2008. Ustojchivost’ funkcionirovaniya seti svyazi obshchego pol’zovaniya. Trebo-vaniya i metody proverki [Stability of the public communication network. Requirements and verification methods]. Moscow, Standardinform Publ., 2009, 16 p. (In Russian)

Oboskalov V. P. Strukturnaya nadezhnost’ elektroenergeticheskih sistem [Structural reliability of electric power systems]. Ekaterinburg, Ural Federal University Press, 2012, 194 p. (In Russian)

Batenkov K. A. Chislovve harakteristiki struktur setej svyazi [Numerical characteristics of the structures of communication networks]. Trudy SPIIRAN [Proceedings of SPIIRAS], 2017, no. 4, pp. 5-28. (In Russian)

Filin В. P. Metody analiza strukturnoj nadezhnosti setej svyazi [Methods of analysis of structural reliability of communication networks]. Moscow, Radio i svyaz’ Publ., 1988, 208 p. (In Russian)

Batenkov K. A. Obshchie podhody к analizu i sintezu struktur setej svyazi [General approaches to the analysis and synthesis of structures of communication networks]. Sovremennye problemy telekommu-nikaciy. Materials of Russian scientific-technical conference [Modern problems of telecommunications]. Novosibirsk, Siberian State University of Telecommunications and Informatics Press, 2017, pp. 19-23. (In Russian)

Polovko A. M., Gurov S. V. Osnovy teorii nadezhnosti [Fundamentals of reliability theory]. St Petersburg, BHV-Petersburg Publ., 2006, 704 p. (In Russian)

Nozaki T., Nakano T., Wadayama T. Analysis of breakdown probability of wireless sensor networks with unreliable relay nodes. 2017 IEEE Intern. Symposium Inf. Theory. Aachen, Germany, 2017, pp. 481-485.

Takabe S., Nakano T., Wadayama T. Fault tolerance of random graphs with respect to connectivity: phase transition in logarithmic average degree. arXiv: 1712.07807, 2017.

Tutte W. T. Graph theory. Addison, Addison-Wesley Publ,, 1984, 423 p.

Yagan O., Makowski A. M. Zero-one laws for connectivity in random key graphs. IEEE Trans. Inf. Theory, 2012, vol. 58, no. 5, pp. 2983-2999.

Batenkov К. A. К voprosu ocenki nadezhnosti dvuhpolyusnyh i mnogopolyusnyh setej svyazi [To the question of assessing the reliability of bipolar and multipolar networks]. Sovremennye problemy radioehlektroniki. Sbornik nauch. trudov [Modern problems of radioelectronics]. Krasnoyarsk, Siberian Federal University Press, 2017, pp. 604-608. (In Russian)

Zhao J., Yagan O., Gligor V. Connectivity in secure wireless sensor networks under transmission constraints. Allerton Conference on Communication, Control, and Computing, 2014, pp. 1-18.

Nucez A., Lacasa L., Valero E., Gymez J. P., Luque B. Detecting series periodicity with horizontal visibility graphs. Intern. J. Bifurc. Chaos, 2012, no. 22, pp. 1-10.

Zhang H. C., Xu D. L., Lu C., Qi E. R., Tian C., Wu Y. S. Connection effect on amplitude death stability of multi-module floating airport. Ocean Eng., 2017, pp. 46-56.

Batenkov K. A. Ustojchivost’ setej svyazi [Network stability]. Oryol, Akademy of Federal Guard Service of Russian Federation Press, 2017, 277 p. (In Russian)

Brown J. L, Tufts J. On the roots of domination polynomials. Graphs Combin., 2014, no. 30, pp. 527-547.

Cox D. On network reliability. PhD thesis. Halifax, Nova Scotia, Dalhousie University Press, 2013, 209 p.

Batenkov K. A. Ob analize zhivuchesti setej svyazi na osnove veroyatnostnogo podhoda [On the analysis of survivability of communication networks based on probabilistic approach]. Nedelya nauki SPbPU [Science week of SPbSPU]. Institut fisiki, nanotekhnologii i telekommunikatsii, St Petersburg, St Petersburg Polytechnical Institute Press, 2016, pp. 6-8. (In Russian)

Huh J. H-vectors of matroids and logarithmic concavity. Adv. Math., 2015, no. 270, pp. 49-59.

Harris D. G., Srinivasan A. Improved bounds and algorithms for graph cuts and network reliability. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, ACM Press, 2014, pp. 259-278.

Karger D. R. A fast and simple unbiased estimator for network (un)reliability. Proceedings of the th annual IEEE Symposium on Foundations of Computer Science. New Brunswick, New Jersey, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing Publ., 2016, pp. 635-644.

Batenkov K. A. Osobennosti ocenki kachestva funkcionirovaniya setej svyazi [Features of an estimation of quality of functioning of communication networks]. Resursoehffektivnye sistemy v upravlenii i kontrole: vzglyad v budushchee [Resource-efficient system management and control: a look into the future]. Sbornik nauch. trudov of V conference schools, students, postgradient students and young scientists. Tomsk, Tomsk Politekhnical University Press, 2016, pp. 30-31. (In Russian)

Mishra K., Trivedi K., Some R. Uncertainty analysis of the remote exploration and experimentation system. Journal of Spacecraft and Rockets, 2012, pp. 1032-1042.

Ghosh R., Longo F., Frattini F., Russo S., Trivedi K. Scalable analytics for laaS cloud availability. IEEE Trans. on Cloud Computing, 2014, pp. 57-70.

Karpov A. G., Klemeshev V. A., Kuranov D. Yu. Opredelenie rabotosposobnosti sistemy, struktura kotoroi zadana grafom [Determining the ability to work of the system, the structure of which is given using graph]. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2020, vol. 16, iss. 1, pp. 41-49. https://doi.org/10.21638/11702/spbu10.2020.104 (In Russian)

Downloads

Published

2022-09-29

How to Cite

Batenkov, K. A. (2022). Аnalysis and synthesis of communication network structures by state enumeration шethod. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 18(3), 300–315. https://doi.org/10.21638/11701/spbu10.2022.301

Issue

Vol. 18 No. 3 (2022)

Section

Applied Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.