Analysis and synthesis of communication network structures by state enumeration method

K. A. Batenkov

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 18 (2022) no. 3, pp. 300-315

Résumé

One 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.

Détail

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

Bibliographie

[1] Zuev K. M., Wu S., Beck J. L., “General network reliability problem and its efficient solution by Subset Simulation”, Probabilistic Engineering Mechanics, 40 (2015), 25–35 | DOI

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

[3] Teruggia R., Reliability analysis of probabilistic networks, PhD thesis, Univ. of Turin, School of Doctorate in Science and High Technology, Turin, 2010, 214 pp.

[4] Dudnik B. Ya., Ovcharenko V. F., The reliability and survivability of communication systems, Radio i svyaz' Publ, M., 1984, 216 pp. (In Russian)

[5] Stability of the public communication network. Requirements and verification methods, Standardinform Publ., M., 2009, 16 pp. (In Russian)

[6] Oboskalov V. P., Structural reliability of electric power systems, Ural Federal University Press, Ekaterinburg, 2012, 194 pp. (In Russian)

[7] Batenkov K. A., “Numerical characteristics of the structures of communication networks”, Proceedings of SPIIRAS, 2017, no. 4, 5–28 (In Russian)

[8] Filin B. P., Methods of analysis of structural reliability of communication networks, Radio i svyaz' Publ, M., 1988, 208 pp. (In Russian)

[9] Batenkov K. A., “General approaches to the analysis and synthesis of structures of communication networks”, Modern problems of telecommunications, Siberian State University of Telecommunications and Informatics Press, Novosibirsk, 2017, 19–23 (In Russian)

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

[11] 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), 481–485

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

[13] Tutte W. T., Graph theory, Addison-Wesley Publishing Company, Addison, 1984, 423 pp. | MR | Zbl

[14] Yagan O., Makowski A. M., “Zero-one laws for connectivity in random key graphs”, IEEE Trans. Inf. Theory, 58:5 (2012), 2983–2999 | DOI | MR | Zbl

[15] Batenkov K. A., “To the question of assessing the reliability of bipolar and multipolar networks”, Modern problems of radioelectronics, Siberian Federal University Press, Krasnoyarsk, 2017, 604–608 (In Russian)

[16] Zhao J., Yagan O., Gligor V., “Connectivity in secure wireless sensor networks under transmission constraints”, Allerton Conference on Communication, Control, and Computing, 2014, 1–18 | MR

[17] Nusez A., Lacasa L., Valero E., Gumez J. P., Luque B., “Detecting series periodicity with horizontal visibility graphs”, Intern. J. Bifurc. Chaos, 22 (2012), 1–10 | MR

[18] 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, 46–56 | DOI | Zbl

[19] Batenkov K. A., Network stability, Akademy of Federal Guard Service of Russian Federation Press, Oryol, 2017, 277 pp. (In Russian)

[20] Brown J. I., Tufts J., “On the roots of domination polynomials”, Graphs Combin., 30 (2014), 527–547 | DOI | MR | Zbl

[21] Cox D., On network reliability, PhD thesis, Dalhousie University, Halifax, Nova Scotia, 2013, 209 pp.

[22] Batenkov K. A., “On the analysis of survivability of communication networks based on probabilistic approach”, Science week of SPbSPU (Institut fisiki, nanotekhnologii i telekommunikatsii), St Petersburg Polytechnical Institute Press, St Petersburg, 2016, 6–8 (In Russian)

[23] Huh J., “H-vectors of matroids and logarithmic concavity”, Adv. Math., 270 (2015), 49–59 | DOI | MR | Zbl

[24] Harris D. G., Srinivasan A., “Improved bounds and algorithms for graph cuts and network reliability”, Proceedings of the 25$^{\rm th}$ Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press, ACM-SIAM, 2014, 259–278 | MR | Zbl

[25] Karger D. R., “A fast and simple unbiased estimator for network (un)reliability”, Proceedings of the 48$^{\rm th}$ annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, New Brunswick, New Jersey, 2016, 635–644 | MR

[26] Batenkov K. A., “Features of an estimation of quality of functioning of communication networks”, 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 Politekhnical University Press, Tomsk, 2016, 30–31 (In Russian)

[27] Mishra K., Trivedi K., Some R., “Uncertainty analysis of the remote exploration and experimentation system”, Journal of Spacecraft and Rockets, 2012, 1032–1042 | DOI

[28] Ghosh R., Longo F., Frattini F., Russo S., Trivedi K., “Scalable analytics for IaaS cloud availability”, IEEE Trans. on Cloud Computing, 2014, 57–70 | DOI

[29] Karpov A. G., Klemeshev V. A., Kuranov D. Yu., “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, 16:1 (2020), 41–49 (In Russian) | DOI | MR