Analysis of critical damage in the communication network. III: Analysis of internode flows (Q2239212)

The paper presents an interesting approach to analyzing critical damage in communication networks. As the critical damage, the authors accepted a subset of edges, removing which at least for one pair of nodes breaks all possible connection paths. For each pair of source-destination vertices, two criteria are used to estimate the decrease in the flow for each damage from the given set. At the first step, all destructive actions are determined at which the maximal possible flow for some selected pair of nodes become zero (the first criterion). At the next step, for such a pair, all damages are found at which the maximal flow was below the permissible level but greater than zero (the second criterion). Finally, based on the data obtained, diagrams of the maximal permissible flows between each pair of vertices are formed for all critical damage from the given set. In this paper, the authors consider and analyze three types of damage: destruction of the minimal cut separating the source-destination pair in an intact network, destruction of the minimal cut in a network with unit capacities, and destruction of all edges incident to a vertex. The computational experiments are carried out for all possible combinations of source-destination pairs of vertices, considering the transmission direction. The results of the consequences of destructive influences on network systems with various structural features are further analyzed -- the authors analyze two network models, so-called core, and ring networks. The capacities of edges are chosen at random from the segment [900, 999] and are equal for coinciding edges in both networks. In this study, the authors continue their earlier study of the flow method of the a priori analysis of the structural invulnerability of a network in the case of a certain type of failure. The choice as the structural damage of cuts that are minimal in terms of throughput and the number of edges, as well as separating a certain vertex from the network, is determined by the logic of the study. The search for the most vulnerable source-destination pairs for the indicated damage is carried out according to two criteria (the zeroing of the flow and the flow falling below a predetermined level), which makes it possible to estimate in advance how the structure retains the standard performance of the network system after destruction. When carrying out the computational experiment, the methods of flow programming with a polynomial estimate of the computational complexity are used. As presented by the authors, the proposed calculation scheme is relatively simple and amenable to parallelization. Therefore, when investigating the vulnerability of large networks, even clusters of personal computers with various operating systems could be used. For Part I and II see [the authors, J. Comput. Syst. Sci. Int. 59, No. 5, 745--754 (2020; Zbl 1459.94006); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upravl. 2020, No. 5, 106--115 (2020); J. Comput. Syst. Sci. Int. 59, No. 6, 918--927 (2020; Zbl 1459.94005); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upravl. 2020, No. 6, 109--119 (2020)].