The article deals with optimum two-phase planning of secure routs in large scale computer networks. Uncertainty of future needs is covered by extensive statistical modeling, which resulted in identification of statistical dependences and phenomena allowing for optimization of creation. To describe secure paths in random matrices the author uses programmable percolation apparatus. Tolerance of the created secure routes to failures in certain secure paths is demonstrated here. Large scale (complex) networks are characterized by the large number of nodes, paths connecting them and mixed topology. There are a number of crucial research tasks pertaining to such networks, for example, analysis of dimensions and number of various-object clusters appearing in the networks; analysis of paths connecting nodes and clusters; analysis of nodes, removal of which may cause disintegration of the network into unlinked parts and etc. The main task of the security strategy being a generalized long-term activity plan aimed at assuring security of large scale networks is effective use of limited resources. In this case problem solving done in a responsive planning way basing on minimum aggregate expenditures allows succeeding. Papers [10, 14, 17] tackle the issue of using the classical percolation theory for the applied research networks. However, the authors never address methods to study large scale networks based on programmable percolation theory explicated in [5, 6, 7, 8].
A large scale network is considered here. Paths among certain nodes are secure. Resource scarcity makes it impossible to build all possible secure routes at once. One may make a secure route each time it is necessary, though it is time-consuming and costly, if compared to other routes incorporating available secure paths (or passing through clusters of such secure paths) provided the latter are abundant. In this case, to create the required route it is necessary to introduce few secure paths covering inter-cluster gaps.
Uncertainty in realization of the given secure route may be determined by statistical analysis based on a large number of random routes.
Thus, the network under consideration has a random number of securely connected nodes making up a somewhat stochastic secure basis. Now it is possible to build a completely secure route via any nodes of the network introducing additional secure segments where they are missing or necessary. As these additional secure segments are formed emergently, they require thorough positioning. Besides they are more expensive than secure paths from stochastic basis.
It is required to define probability of a secure path in the stochastic basis (in terms of the percolation theory – concentration of the open black cells) which minimizes overheads of building secure routs in the network.
In the classic percolation theory [
With the programmable percolation [
Image Processing, Geoinformation Technology and Information Security / Ya. Mostovoy, V.Berdnikov that programmable percolation allows having concentration of objects (secure paths) more than twice as little as the stochastic percolation threshold. As well the concentration of objects is in the neighborhood of concentration typical to average maximal number of clusters appearing ( = 0.25).
As far as targets of research are large scale networks and statistical phenomena of secure-path clusters, and the goal of research is long-term planning of optimal-cost secure routes in large scale networks, our theoretical considerations are verified by a computer experiment - the only possible way of application investigation.
The computer experiment for long-term planning of secure routs in large scale networks consisted of a number of consecutive stages, repeated for each of randomly filled matrices (SPNM) being models of operation environment.
Each time the following steps were made for each value of secure routs concentration: - the matrix was randomly filled with objects in conformity with the predetermined probability law and concentration value; - the resultant clusters and objects were identified and analyzed; - measures of cluster distribution (average values, scatter and etc.), cluster size, inter-cluster gaps and etc. were calculated;
- gaps between stochastically-formed clusters were analyzed; shortest artificial percolation paths were formed; average length of the above mentioned path was measured and average number of additionally inserted secure segments covering intercluster gaps was calculated per totality of randomly-filled matrices.
In order to identify clusters and estimate their characteristics we used the Hoshen-Kopelman algorithm [
Classic percolation theory considers a randomly-filled matrix to be a model of environment in direct geometrical interpretation. Such an approach does not suit for analysis of network security, because network topology cannot be rendered by a two-dimensional array. It is necessary to migrate from network topology to that of the secure paths inter nodes matrix (SPNM). Such a matrix might ignite research of network security and availability of through paths using methods of the percolation theory.
Example of such a transmission is demonstrated below in Figures 1 and 2.
Black lines are data connections (paths) between network nodes. Yellow lines are secure connection (secure paths) between the nodes.
5 1 2 3
4 6
7
SPNM is filled according to the following rule: end-node names of interest are recorded in the vertical direction, startnode names of interest are recorded in the horizontal direction (in Figure 2 they are blue). Note that nodes in the vertical and horizontal directions are not repeated. The suggested research tool SPNM strict squareness is unimportant. Casual randomization of lines and columns is possible. SPNM filling algorithm is the following:
1.1. If node is missing in the table, record the node name in the horizontal direction. 1.2. Record nodes, which are connected with the node in the network in vertical direction.
1.3. Mark SPNM cells correspondingly: black if there is secure connection between the node and other nodes from the table. 2. End of the loop.
Adjoining black cells make up a cluster. The point is that information can be securely transferred via this segment of the network. In the given example (see Fig.2) there are two clusters: the «1-2, 1-8» cluster and the «3-4» cluster.
If certain inter-cluster gaps in the SPNM are filled with secure connections (marked red), then a through non-stochastic but programmed percolation route is created in the SPMN. It means that all the nodes recorded in the vertical direction are available for secure connection with the nodes recorded in the horizontal direction.
Thus, secure interconnection of all the nodes recorded in the vertical direction is rendered on the SPNM as a programmable percolation vertical route (see Fig.3): route in the given direction we used an adaptation of Dijkstra's algorithm. All programmable percolation routes are the subject of statistical modeling.
For statistical analysis we used different-size SPNM filled with the help of the random number generator.
Example of an SPNM randomly filled with secure paths (black cells) is given in Figure 4. Concentration of the black cells differs. SPNM size here is 50 × 50. Possible shortest routes of the programmable percolation in the bottom-top direction across the SPNM are plotted in red. Note greater tortuousness of the programmable percolation route across the matrix with = 0.6 concentration.
a) b)
Concentration is a relative fraction of black nodes during random and homogeneous filling of the matrix. It makes
black cells [
= 0.6.
Statistical modeling using square randomly filled matrices allows detection and analysis of cluster statistical phenomena
The first peculiarity is presence of the stochastic percolation threshold in the shape of matrix dissection by the open
The second peculiarity is such concentration of objects when average number of clusters is maximum [
= 0.25 (see Fig. 5).
The third statistical peculiarity is maximum average length of the shortest route through the stochastically formed clusters in the percolation direction. This value appears when the population of objects and route tortuousness grows. Average length of the programmable percolation ( ) shortest route grows up to the stochastic percolation threshold, and upon reaching it starts decreasing. The more tortuous is the percolation route (i.e. the longer it is), the more passing clusters it incorporates.
During statistical modeling we considered several thousands of different size matrices. The cells of those matrices were randomly filled with provision for equal probability of objects distribution in the cells. In order to identify all the clusters in the received random
matrices we used the Hoshen-Kopelman algorithm [
Dependence of the average number of clusters in the matrix from the probability of the object in the cell is given in
Image Processing, Geoinformation Technology and Information Security / Ya. Mostovoy, V.Berdnikov grows. Further growth of concentration results in merging of the clusters. Their average number decreases while their size grows.
On several physical grounds we established that the number of clusters appeared in the matrix with the certain concentration depended on the matrix area size 2, while length of routes depended on the linear dimension of the matrix . Consequently, it is possible to save numerical results of statistical modeling from influence of the matrix size by dividing them by or 2 correspondingly. Numerical computations verify the above said (see Fig.5).
KK(K) kk(K)
We may decrease the appropriate concentration and consequently number of objects necessary for percolation, if we replace classical stochastic percolation with the suggested programmable percolation and apply the two-phase approach.
Taking into account different value of type I objects randomly distributed to form a stochastic basis (black cells) and type II objects inserted in certain places of the coverage area to get the shortest programmable percolation route (red cells), we are able to come at a such concentration of the stochastic basis when total cost of the created programmable percolation route is minimal.
Having said this it can be believed that each of the objects from the stochastic basis scattered in the operating environment is cheaper than an additional object inserted into a certain place of the same operating environment.
Figure 6 demonstrates processed results of two-phase operations computer experiment: average number of the inserted objects necessary for programmable percolation with various concentrations of objects in the stochastic basis and for differentsize matrices. Figure 6a: in vertical direction is given the average number of the objects inserted in 50×50 matrix (dotted line) and 100×100 matrix. Figure 6b: the dependences are normalized according to the matrix size (whereupon the graphs coincided).
Stochastic percolation cluster is formed at concentration = 0.6 and the shortest percolation route passes through it.
That is why in this case the average number of the added cells tends to zero. At this concentration tortuousness and length of the
percolation route are maximal. Further growth of the concentration makes the shortest percolation route more straight and its
length decreases (Fig. 6c) [
80 DK (K) 60 dk(K) 40 0 20 means absence of gaps to be covered (absence of the reds). Therefore, wealth of gaps in the route results in greater cost of each 0 ∗ ( ) ∗ ⁄ ( )2
. With account of this equation, the cumulative costs formula (1) shall be and inversely proportional to relative tortuousness of the route ( ) ⁄ as maximal tortuousness Р = × × 2 + 0 ∗ ( )2 ∗ 2 ⁄ ( )2
Let us analyze relative cost of a two-phase operation. For this we divide the left-hand side and the right-hand side of the obtained equation (2) by Р
п = ∗ п ∗ 2 – cost of a purely stochastic one-phase operation. Ротн = Р ⁄ Р п = 1.7 + 1.7 ∗ ( ( 0 ∗ ( )2) ⁄ ( ∗ ( )) ) = 1.7 ( + ∗ ( ) 2 ⁄ ( )2) , where =
0⁄ is ratio of the additional object cost to the stochastic basis object cost. Figure 7 demonstrates two-phase operation relative cost variation versus stochastic basis
obtained with the above equation taking into consideration ( ) and ( ) variations (see Fig. 5) for
Pотн 0,6 1,2
1 0,8 0,4 0,2 0 0 20 40 60 80
100
K (2) (3) one. Al the upsurges seen on the plot are within statistical error. Then, we let a new percolation route start from the preceding point in the same direction and on the same conditions of optimality bypassing the fault. Probability that the new percolation route reverts to the former one is demonstrated in Figure 8; optimal concentration of the stochastic basis
= 0.25 was estimated in advance. The plot obtained in the cause of the experiment did not depend on the matrix size. The plot was normalized according to the following rule: = ⁄ , where is coordinate position of the failure in SPNM in the vertical direction, is the SPNM height. It is safe to say that the route is invariable up to = 0.85, i.e. a new percolation route is likely to revert to the former p 1,5 0,5 1 0 0 0,2 0,4 0,8 1
1,2 0,6 Ln denoting a failure. different sizes is the same. Variation of the green cells number versus concentration is given in Figure 9. Actually, the plot for matrices of 0 20 40
K 60 80 100
Note that all the deviations of the plot are within statistical error.
Based on the findings it follows that the number of the green cells independent from the matrix size, but depends on the concentration. Therefore, the fault phenomenon is of purely local nature.
Besides, we studied programmable percolation, i.e. making routes from the given point to the target point. This problem matrix size we shall normalize to the length of the guiding axis in the following way: (4) 2,5 1,5 LG
1 0,5
0 -0,5 100x100 50x50 10, plot a). The results agreed. Hence, the average number of objects (red cells) added to the percolation route would be the same irrespective to the direction of a percolation route. -0,2
Note that graph 10a was plotted by averaging the number of the red cells in the situation of the percolation failure, whereas graph 10b was plotted by averaging the number of the red cells for programmable percolation between target points A and B. 8. Conclusion
1. In case of limited resources cost-effective planning of secure routes shall be two-phased: firstly is created a stochastic basis of secure though rather low-concentrated paths, and secondly are built secure routes via clusters of the stochastic basis with minimal insertion of secure paths in between the gaps of the clusters.
2. Concentration of secure paths in the stochastic basis shall be 0.25. At such concentration of secure nodes the number of the generated clusters is maximal. In this case any secure route built between the given nodes of the network has minimal average total cost.
3. Subsequent to the results of the percolation route stability analysis it was found that the fault phenomenon was of purely local nature and bypass routes were likely to revert to the original percolation route.
4. When the optimal concentration of secure paths is 0.25 , the average number of additionally inserted secure paths to bypass the failed one is not more than 2.