ptum-efficient-shielding-of-large-scale-network-through-pruned-tree-cut-mapping.pdf原版完整文件.docx

《ptum-efficient-shielding-of-large-scale-network-through-pruned-tree-cut-mapping.pdf原版完整文件.docx》由会员分享，可在线阅读，更多相关《ptum-efficient-shielding-of-large-scale-network-through-pruned-tree-cut-mapping.pdf原版完整文件.docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Contents lists available at ScienceDirectReliability Engineering and System Safetyjournal homepage: Reliability Engineering and System Safety 232 (2023) 109082PTUM: Efficient shielding of large-scale network through pruned tree-cut mappingWei Wei, Yuting Liu, Weidong Yang Key Laboratory of Grain Inf

2、ormation Processing and Control (Henan University of Technology), Ministry of Education, Zhengzhou 450001, China Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, Zhengzhou 450001, ChinaA R T I C L E I N F OA B S T R A C TKeywords:Network robustness P

3、runed tree-cut mapping ShieldingLarge-scale network ConnectivityAs one realistic way to improve the robustness of network, the protection of critical links will help build resilient link structure to defend against random link failure, especially in sparse network where few simultaneous broken links

4、 can divide it into disconnected parts. There are several ways to select the set of links to shield, where selecting links by graph cuts is a practical one. However, due to the computational complexity of cut enumeration, the existing algorithms cannot handle large-scale networks in acceptable time.

5、 Fortunately, between the pruned trees and cuts, we found an efficient mapping schema to enumerate small cuts, which can help select the candidate links quickly in large-scale sparse network, and the link set will be further refined to find the set with minimal shielding cost. The experimental resul

6、ts show that compared with the existing optimal algorithm, the acceleration ratio of 5 orders of magnitude can be obtained easily with little excess cost, and the shielding solution can protect more than 99.9% vulnerable node pairs. Furthermore, the time can be reduced to tens of seconds by parallel

7、ization for the ready-to-parallelize algorithm.1. IntroductionThe failure of communication network can severely affect their availability, and thus can severely affect the performance of services and applications built upon the network. Network robustness can be regarded as its ability to cope with

8、the various types of failures that can occur in the network, such as intended attacks or natural disasters. It is important to improve the network robustness to prevent these types of attacks and disasters from disconnecting the network. Significant research has been conducted in these areas, the st

9、udy can help produce useful tools in the characterization and utilization of complex inter- connected systems such as infrastructure, communication and social networks, while the gaps in the surveying literature still exist 1.There are already plenty of metrics used for network robustness as- sessme

10、nt 2, while some indirect metrics can affect robustness in spe- cific scenarios, such as the inter-network assortativity 3. A straight- forward way to enhance robustness is through improving these metrics, where the widely optimized metric is R 2. The largest component of a network, known as the lar

11、gest connected component (LCC), is a useful indicator of the network status. By iteratively deleting the highest- degree nodes, the average ratio of LCC size among all the iterations can be defined as the metric R. 4 developed a deep learning policy that aims to improve the resilience of the Interne

12、t of Things (IoT) network topology. It was implemented by adopting a R-improving reinforcement method that can be used to prevent cyber-attacks. 5 proposed a This paper was supported by the National Natural and Science Foundation of China (62172141, 62006071, 61772173, 61973104, 61803146), Natural s

13、cience project of Zhengzhou science and Technology Bureau (21ZZXTCX20), Henan Excellent Young Scientists Fund (212300410036), the Key Laboratory of Grain Information Processing and Control (Henan University of Technology), the Ministry of Education (KFJJ2022002), Backbone Teacher Training Program of

14、 Henan University of Technology (2012012), Young Backbone Teacher Training Program of Henan Higher Education (2018GGJS066, 2019GGJS089), Plan For Scientific Innovation Talent of Henan University of Technology (2018RCJH07, 2018QNJH26), Doctor Foundation of Henan University of Technology (2017025), Na

15、tural Science Foundation of the Henan Province (152102210068), National Key Research and Development Program of China (2017YFD0401001), Program for Science and Technology Innovation Talents in Universities of Henan Province (19HASTIT027, 21HASTIT029), the Innovative Funds Plans of Henan University o

16、f Technology (2020ZKCJ06), the Cultivation Program of Young Backbone Teachers in Henan University of Technology (21420080). Correspondence to: College of Information Science and Engineering, Henan University of Technology, No.100, Lianhua Street, New and High-tech Zone, Zhengzhou, 450001, China.E-ma

17、il addresses: weiwei_ise (W. Wei), yuting (Y. Liu), yangweidong (W. Yang).https:/doi.org/10.1016/j.ress.2022.109082Received 26 July 2022; Received in revised form 7 December 2022; Accepted 28 December 2022Available online 30 December 20220951-8320/ 2022 Elsevier Ltd. All rights reserved.W. Wei et al

18、.Reliability Engineering and System Safety 232 (2023) 10908214novel method that can be used to predict the robustness of a sys- tem against various attacks, the proposed robust optimization method considers the multiple factors that affect system performance. Despite the advantages of single metric-

19、based algorithms in optimizing the robustness of networks, they may not handle complex attack scenarios effectively, where the improvement of robustness needs to be applied to multiple targets. Accordingly, a new approach to evaluate robustness using complex networks was developed 6, which combined

20、a vector- guided multi-objective algorithm with a network property parameter. The proposed algorithm for analyzing network data was validated against a state-of-the-art method, and the results indicated that the algorithm significantly improved computational efficiency.There is also research to opti

21、mize the robustness for specific types of networks in given scenarios. 7 proposed framework for robustness enhancement of cyberphysical systems in different failure scenarios. The key node protection strategy and weak interdependency adjust- ment strategies can help alleviate or even mitigate the im

22、pacts of different kinds of failures, and the network robustness can be improved significantly. 8 proposed to improve the robustness of large networks by exploiting the communities in complex representations. The pro- posed method would allow them to perform comprehensive analysis of networks with t

23、housands of nodes. Urban transportation systems were tested using the community-based framework, and the results demon- strated the scalability and efficiency of the method. An integrated framework was proposed in 9 to assess network robustness. It is found in the framework that failures can be more

24、 quickly introduced by the betweenness-based attacks. The robustness enhancement strategies under different failures were proposed and analyzed accordingly. The robustness measurement and enhancement were also investigated in the two-layer maintenance support service network 10. Based on the propose

25、d robustness measurement, two strategies were proposed along with the way to select optimal one. The numerical results were provided to validate the effectiveness. The ability to withstand per- turbations in scale-free networks can be captured by the cascading failure model, accordingly 11 presented

26、 the model to calculate and evaluate the failure size and the robustness of a network when a fraction of its nodes is affected by a single perturbation. To verify the effectiveness of the model, they performed extensive numerical simula- tions, and the theoretical results were consistent with simula

27、tions. The goal of the study in 12 was to investigate the relationship between the knowledge network and the potential for high value inventions. They hypothesized that a robust knowledge network is associated with the likelihood of getting valuable inventions. They then tested this hypothesis using

28、 the patent citation network and found that the network robustness could be used to estimate the technical value of an invention.To avoid the complexity of optimizing network metrics, one of the most common approaches is to deploy redundant links or nodes to maintain the connectivity of the network

29、in case of failure. Although in failure the capacity of the protected network may decrease significantly between most node pairs, the connectivity will remain intact to support the upper-level applications. The commonly used algorithm for this problem schema is the graph augmentation work, which is

30、about how to increase the network connectivity using the links with minimal costs 13. For example, 14 presented a fast and efficient solution to graph argumentation, which considered both the node-weighted version and the degree-constrained version of the problem. By adding a certain number of links

31、, the converse problem of increasing maximal connectivity can be solved efficiently.In the situations where pre-deployed redundancy is not feasible, another realistic strategy is to protect critical links. The existing work focused on protecting communication networks, such as identifying and enhanc

32、ing the most valuable cables in communication networks. 15 tackled the issue of deploying cables when it passes through error- prone areas. To improve the reliability of cables that connect two sites, they proposed a multi-objective algorithm that can minimize the totalnumber of repairs and the cost

33、 as a whole. They also investigated how to protect the cable from getting damaged by optimally shielding them. The goal of 16 was to find a way to update selected links with minimal cost in a set of nodes. A heuristic algorithm was proposed to utilize integer linear programming and the greedy strate

34、gy. The results can be further improved by a post-processing procedure. More problem scenarios with different objectives were investigated. For example, the existing work also considered the likelihood of capsizing of the cable laying vehicle 17, and the trunk-and-branch tree topology 18.Instead of

35、just protecting the paths between limited number of ends, to improve the robustness of the whole network, it is necessary to protect the communications between large percentage of node pairs or all node pairs. However, due to the high time complexity, most of the existing methods usually focused on

36、limited node pairs, so the point-to-point optimization is not feasible if there are large number of node pairs. There are only limited studies on all-pairs oriented shielding 19. Due to the complexity of the proposed techniques, it can only be performed on small networks with limited nodes. To addre

37、ss the problem, we present a method that aims to provide a simple and cost-effective way to guarantee the connectivity of large- scale networks. Through a pruned tree-cut mapping, the algorithm examines the various candidate links and then selects the near-optimal ones to maintain the networks conne

38、ctivity. Compared with the op- timal algorithm in small-scale networks, the proposed algorithm can obtain an acceleration effect of 5 orders of magnitude with little excess cost. While in large-scale networks, the single thread version of the algorithm can generate the protection plan protecting mor

39、e than 99.9% vulnerable node pairs. Furthermore, due to the independence of the preprocessing pass, the total solving time can be significantly reduced further by implementing the multi-pass algorithm in parallel.The methodological novel contributions are a fast high-precisionalgorithm for the probl

40、em of improving the general robustness metrics (i.e., connectivity) in large-scale network, and the efficient way to val- idate its precision. Since the problem is highly related to the reliability of complex networked systems, the results have a discernable relation- ship to the solution of such pr

41、oblems, where the existing high-precision approximation algorithm can only handle small scale network with at most hundreds of nodes, and the degree or cost-related heuristics can only obtain low-robustness results under the same budget. Due to its efficiency and high precision, it has the potential

42、 to be integrated and applied to dynamic reliability scenarios.2. Model and algorithmThe core conception used in our algorithm is cut 20:Definition 1. In an undirected graph 𝐺 with the set of nodes 𝑉 and links 𝐸, given two sets of nodes 𝑋 and 𝑌 with 𝑋&

43、#119884; = and 𝑋𝑌 = 𝑉 . The link set 𝐸𝑋, 𝑌 is a cut of 𝐺 if it contains all the links with one end in 𝑋 and the other end in 𝑌 .The connectivity can also be defined based on cut, where the size of a cut is the number of links in

44、 a cut.Definition 2. The connectivity of a network can be defined as the minimal cut size of all the cuts in the network.The paper is about the problem related to the expected connectivity𝐾 of a graph with an undirected structure and a per-link cost. That is, how to find and shield a set of

45、links with minimal cost, so the graph is protected from getting separated into two or more unconnected parts when any 𝐾 1 unshielded links are removed, i.e., increasing the connectivity to 𝐾. Note that shielding a link means it cannot be broken and thus cannot be used as cut link, i.

46、e., shielding a link in a cut means removing all the other links in the cut cannot disconnect the graph. For the problem it has:Lemma 1. Given any 𝐾 1, for a connected graph with connectivity of less than 𝐾, it is NP-hard to shield the minimum cost set of links to increases its conne

47、ctivity to 𝐾.Proof. Denote the set of all the cuts with size less than 𝐾 in the given graph as 𝐾 . There is no cut belonging to 𝐾 in a connected graph with connectivity of 𝐾. In a graph 𝐺 with connectivity of 𝐾 𝐾, there must be at least

48、 one cut with value 𝐾 and the values of all the cuts in 𝐾 of𝐺 must be no less than 𝐾. Since one shielded link will eliminate the corresponding cut, to improve the connectivity from 𝐾 to 𝐾, it means all the cuts in 𝐾 of 𝐺 must be elimina

49、ted, i.e., at least one link of eachcut in 𝐾 should be shielded.Denote the links of all the cuts in 𝐾 as 𝜙𝐾 . By assigning each cut a unique identify (ID), denote 𝑈 as the complete set of all the IDs of cuts in 𝐾 , each link 𝑒 has a subset 

50、9880;𝑒 𝑈 that consisting of the IDs of all the cuts containing 𝑒. Denote 𝑆 as the set of 𝑈𝑒 of all the links in 𝜙𝐾 , the problem in the paper is clearly a set covering problem (SCP) finding the optimal subset of 𝑆 that covers all the IDs in 𝑈 . It is a NP-hard problem since the SCP problem i