Published on

05-Jan-2017View

212Download

0

Transcript

Robustness of Internet under targeted attack: A cascadingfailure perspective

Jianwei Wang n, Chen Jiang, Jianfei QianSchool of Business Administration, Northeastern University, Shenyang 110819, PR China

a r t i c l e i n f o

Article history:Received 1 May 2012Received in revised form27 April 2013Accepted 24 August 2013Available online 17 September 2013

Keywords:Cascading failureRobustnessAttackInternet

a b s t r a c t

In many networks, there exist some heterogeneous nodes, for example the hosts and the routers in theInternet, and the users and the supply-grid stations in the power grid. In the previous studies, however,few cascading models were constructed in the heterogeneous networks. Considering two types of nodes,we propose a new cascading edge model and investigate the cascading dynamic behaviors in theInternet. Compared with an extending BarabsiAlbert (BA) network with two types of nodes, we findthat the Internet displays the stronger robust level under two targeted attacks and propose someeffective methods to protect these networks. The cascading model in the Internet can be extensivelyapplied to other real-life networks, and may provide a new perspective to study the network safety.

& 2013 Elsevier Ltd. All rights reserved.

1. Introduction

In recent years, owing to the importance of the network safety inour daily life, the question of the robustness of complex networks hasattracted a large amount of interests from many researchers (Lin,2007; Bossardt et al., 2007; Wu et al., 2007a,b, 2011; Holme et al.,2002; Xia and Hill, 2008). In particular, there has been the extensiveeffort to study and understand the Internet robustness, which hasbeen one of the most central topics in the network safety. Animportant conclusion in this context is that the Internet displays thestronger robustness against random failure, but shows the exceptionalvulnerability against intentional attack (Albert et al., 2000). Since theearlier studies mainly focus on the static properties of a network(Cohen et al., 2000, 2001), recently cascading failures induced by theredistribution dynamics of the load on a network have been highlyconcerned and widely investigated. Cascading failures are common inreal-life systems and can occur not only in the Internet but also inmany other infrastructure networks. Typical examples include severalblackouts in some countries, e.g., the largest blackout in US historytook place on 14 August 2003 and the Western North Americanblackouts in July and August 1996, and the Internet collapse caused bythe submarine earthquake near Taiwan in December 2006.

A number of important aspects of cascading failures have beendiscussed in the literature and many valuable results have been found,including the robustness of interdependent networks (Vespignaniet al., 2010; Buldyrev et al., 2010; Parshani et al., 2010; Huang et al.,

2011; Shao et al., 2011), the cascading control and defense strategies(Wang and Rong, 2009a,b; Yang et al., 2009; Wang et al., 2010;Simonsen et al., 2008; Motter, 2004; Ash and Newth, 2007), themodels for describing the cascading phenomena (Crucitti et al., 2004;Wang and Chen, 2008; Wang and Xu, 2004; Wang and Rong, 2009c;Lehmann and Bernasconi, 2010; Goh et al., 2001; Sandro et al., 2008),and cascading failures triggered by intentional attacks (Motter and Lai,2002; Wang et al., 2008; Wang and Rong, 2008; Zhao et al., 2004,2005; Ricard et al., 2008). These studies not only construct cascadingmodels from single networks but also pay close attention to cascadingmodels from coupled networks. However, in all studies cited above, afew works explore cascading failures in the Internet with two types ofnodes, i.e., the routers and the hosts. Therefore, in the Internet, how toconstruct a cascading model with heterogeneous nodes and investi-gate its robustness against cascading failures is a significant topic.

To this end, the aim of this paper is to construct a new cascadingmodel and investigate the roles of different edges in the cascadingpropagation in the Internet. Considering two types of nodes, weconstruct a new cascading model and compare the effects of differentways of attacking edges in the Internet. We numerically find someinteresting and important results, such as, targeted attacks are notalways effective and the Internet is more robust than Barabasi andAlbert (1999) (BA) networks under targeted attacks. In addition, wecarefully analyze these results by the local topological structure of twokinds of networks. Our findings may be useful in further studies onhow to build attack-robust networks and increase the robustness ofreal-life networks against cascading failures.

The rest of this paper is organized as follows: in Section 2, wedescribe the cascading model in detail. In Section 3, we analyzethe robustness of the Internet under two targeted attacks. Finally,some summaries and conclusions are shown in Section 4.

Contents lists available at ScienceDirect

journal homepage: www.elsevier.com/locate/jnca

Journal of Network and Computer Applications

1084-8045/$ - see front matter & 2013 Elsevier Ltd. All rights reserved.http://dx.doi.org/10.1016/j.jnca.2013.08.007

n Corresponding author. Tel.: 86 024 83672631.E-mail address: jwwang@mail.neu.edu.cn (J. Wang).

Journal of Network and Computer Applications 40 (2014) 97104

www.sciencedirect.com/science/journal/10848045www.elsevier.com/locate/jncahttp://dx.doi.org/10.1016/j.jnca.2013.08.007http://dx.doi.org/10.1016/j.jnca.2013.08.007http://dx.doi.org/10.1016/j.jnca.2013.08.007http://crossmark.crossref.org/dialog/?doi=10.1016/j.jnca.2013.08.007&domain=pdfhttp://crossmark.crossref.org/dialog/?doi=10.1016/j.jnca.2013.08.007&domain=pdfhttp://crossmark.crossref.org/dialog/?doi=10.1016/j.jnca.2013.08.007&domain=pdfmailto:jwwang@mail.neu.edu.cnhttp://dx.doi.org/10.1016/j.jnca.2013.08.007

2. The model

In general, the Internet contains two types of nodes, the routersand the computers, which play different roles in the function. Thecomputers are the terminal users, while the cables between therouters can transport the load. We can simply use a two-layernetwork to represent the Internet (see Fig. 1), in which the routersand the computers lie in the top layer and the bottom layer,respectively. When the cable between two routers fails owing tosome reasons, the load on it will be redistributed to other cables,which may further lead to the malfunction of other cables andeventually trigger the larger cascading failures in the wholeInternet. According to the cascading evolving process mentionedabove, a cascading model should include three aspects: how todefine the initial load on an edge, how to assign the capacity of anedge, and how to redistribute the load on it after an edge fails.Therefore, considering the different roles of the routers and thecomputers in the cascading propagation and three aspects relatedwith cascading failures, we propose a new cascading model.

Next, we briefly introduce our cascading edge model. Firstly,we give a new method to assign the initial load on an edge. In theInternet, the load on the cable between two routers A and B isgenerally decided by the number of the routers and the computersconnected with A and B. Therefore, considering the effects of therouters in the R layer and the computers in the C layer on theinitial load on an edge, we assume the initial load Lij of edge ij to be

Lij f Rki;R-R; kj;R-Rf Cki;R-C ; kj;R-C 1where ki;R-R and ki;R-C is the degrees of node i connecting withthe routers in the R layer and the computers in the C layer,respectively, and is a tunable parameter, governing the strengthof the initial load on an edge. Two functions fR and fC represent theeffects of the routers and the computers connected with routersi and j on the initial load on edge ij, respectively. Our main aim isto investigate the robustness of the Internet under targeted attacks

against cascading failures. Therefore, we assume

f Rki;R-R; kj;R-R 1ki;R-Rkj;R-R 2

f Cki;R-C ; kj;R-C 2ki;R-Ckj;R-C 3

of which 1, 2, , and are tunable parameters. The definitions ofEqs. (1) and (2) are supported by empirical evidences of realnetworks (Wang and Rong, 2009b; Wang and Chen, 2008; Barratet al., 2004). Moreover, Holme et al. (2002) shows that thebetweenness of an edge has a positive correlation with theproduct form of node degrees at both ends of the edge. Specially,in a single network with one type of nodes, many cascadingmodels are constructed according to the rules above. In this sense,our assumption about the initial load on the edge is in accordancewith the previous models. By analyzing the definition of the initialload on an edge, we can see that the distribution of the initial loadis decided by parameters , 1, 2, , , and the network topologystructure. Therefore, we mainly focus on the correlation betweenthese parameters and the effects of targeted attacks.

Since the capacity of an edge in real-life networks is generallylimited by cost, it is natural to assume that the capacity Cij of edgeij is proportional to its initial load for simplicity:

Cij 1Lij 4

where 40 is a uniform capacity parameter (Fig. 2).Considering that the edge with the higher capacity has generally

the stronger capacity to handle the extra load, we assume topreferentially redistribute the load along those higher-capacityedges (Wang and Rong, 2008, 2009a,b; Wang and Chen, 2008).Thus, the load on a failed edge ij will be preferentially redistributedto its neighboring edges in the R layer (see Fig. 3 for illustration).The additional load Lim received by edge im is proportional to its

Fig. 1. The scheme demonstrates that the Internet with the routers and the computers can be represented by two layers networks.

J. Wang et al. / Journal of Network and Computer Applications 40 (2014) 9710498

capacity, i.e.,

Lim LijCim

aAi CiabAj Cjb5

where i and j are the sets of the neighboring nodes of nodes i andj, respectively. For edge im received the additional load Lim,if LimLim4Cim, then it will be broken and the load on it has tobe transferred to its neighboring edges. This load redistribution mayfurther lead to the cascading propagation in the entire network.

Here we focus on cascading failures triggered by attacking asingle edge. In a real-life network, an attack on a particular edge isdefined as an event that disables or removes this edge from thenetwork. We use seij, srnij , and scnij to denote the avalanche sizes ofedges, and nodes in the R layer and the C layer induced byremoving edge ij, respectively. It is evident that 0rseijrE1,0rsrnij rNr , and 0rscnij rNc , where E, Nr, and Nc represents thenumber of edges, and nodes in the R layer and the C layer in thenetwork, respectively. Therefore, without loss of generality, weadopt the normalized avalanche size S of edges and the normal-ized avalanche sizes SRN and SCN of nodes in the R layer and the Clayer to quantify the network robustness, i.e.,

S 1EA

ijAA

seijE1 6

SRN 1EA

ijAA

srnijNr

7

SCN 1EA

ijAA

scnijNc

8

where A and EA represent the set and the number of edges attacked,respectively.

3. The analysis of the robustness of the Internet

To better investigate the robustness of the Internet againstcascading failures and propose the effective protection strategies,we focus on two simple targeted attacks in our cascading model.The first one is to attack the edges with the highest load (HL). Theremoval rule is to select the edges in the descending order of theload and then to remove them one by one starting from the edgeswith the highest load (if some edges happen to have the sameload, we randomly choose one of them). The second one is toattack the edges with the lowest load (LL). The removal rule is toselect the edges in the ascending order of load and then to removethem one by one starting from the edges with the lowest load(if some edges happen to have the same load, we randomly chooseone of them). The LL is rarely applied to the real-life networks,because ones generally think that the HL is easier to lead to thecascading propagation on a global scale in the whole network.

As an example we consider the structure of the Internet at thelevel of autonomous systems with 22 963 nodes and 48 436 edges.The data are collected by Mark Newman on July 22, 2006(Network data from Mark Newman's, 2006). We use autonomoussystems as the routers in the R layer in our cascading model, andgenerate the computers in the C layer. For the node i in the R layer,we simply set ki;R-R ki;R-C , i.e., if the degree of node i in the Rlayer is ki;R-R, we will generate ki;R-R nodes as the computersin the C layer. The Internet by extending the computers consistsof 119 835 nodes and 145 208 edges. For simplicity, we set 1 2 1 in numerical simulations. To better compare theeffects of two targeted attacks in the Internet, we firstly calculatethe order of the initial load on edges when 0:1, and findthat the smallest value of the load in all edges consists of 138edges. Therefore, we choose 138 edges as the attacked objects inthe LL. While we only choose 10 edges in the HL, considering thedifferences among the edges with the highest load. In simulations,each curve is averaged over 10 realizations.

Firstly, we perform numerical simulations with 0:03rr0:75and 0:07rr0:85 in Fig. 4. We can observe that the curves of thefailed edges in the R layer display threshold-like behaviors, i.e.,a phase transition from normal state to collapse, which can beexplained by the role of the parameter . In many previous studieson cascading failures (Wang and Rong, 2008, 2009a,b,c; Wang andChen, 2008; Wang et al., 2008), quantifying the network robust-ness by this phase transition point has been widely applied.To better compare two attacks, we also adopt this phrase transi-tion point to quantify the robustness of the Internet againstcascading failures, i.e., the critical threshold c . Apparently, thebigger the value c , the more efficient the targeted attack. In Fig. 4,when 0:03rr0:15 and 0:07rr0:25, both the critical thresh-old c and the larger avalanche sizes in the comparison betweentwo attacks show that the LL is relatively easy to trigger cascadingfailures than the HL. This result means that protecting the edgeswith the lowest load is more important than protecting the oneswith the highest load. In other words, the vulnerability in theInternet is not originated from attacking the edges with thehighest load. According to the different cases of the load distribu-tion in the Internet, our finding has an important implication thatit can provide guidance in protecting some edges selected effec-tively to avoid cascading-failure-induced disasters. Additionally, inthe ranges of 0:20rr0:35 and 0:30rr0:45, we can see that

Fig. 2. The scheme demonstrates the correlation between the initial load Lij on anedge ij in the R layer and two kinds of different degrees of nodes i and j. The nodesin the R layer and in the C layer correspond to the routers and the computers,respectively.

Fig. 3. Illustration of the local...