=Paper=
{{Paper
|id=Vol-1950/paper12
|storemode=property
|title=Can we break the Internet?: A Robustness Analysis of the Internet Exchange Points (IXP) Network Graph.
|pdfUrl=https://ceur-ws.org/Vol-1950/paper12.pdf
|volume=Vol-1950
|authors=Alexandra Ibarra,Javier Bustos
}}
==Can we break the Internet?: A Robustness Analysis of the Internet Exchange Points (IXP) Network Graph.==
https://ceur-ws.org/Vol-1950/paper12.pdf
Can we break the Internet?: A Robustness Analysis of the
Internet Exchange Points (IXP) Network Graph.
Alexandra Ibarra Javier Bustos-Jiménez
NIC Labs, Universidad de Chile, Chile NIC Labs, Universidad de Chile, Chile
ale@niclabs.cl jbustos@niclabs.cl
precision, and having limited CPU resources,
the best strategy is to select the nodes with
Abstract higher degree.
Internet peering is the contract between
1 Introduction
two autonomous systems (AS) that agree to
exchange traffic and traffic routes through Internet peering is the contract between two
a physical link, it is a multi-tier hierarchy autonomous systems (AS) that agree to exchange
where the first tier (of about 10-20 nodes) traffic and traffic routes through a physical link.
are connected with a clique of peering links, The authors of [DD10] state that “The core of the
second tier are customers of the first, and Internet is a multi-tier hierarchy of Transit Providers
residential and small business access are in (TPs). About 10-20 tier-1 TPs, present in many
the third tier. Therefore, it is natural to think geographical regions, are connected with a clique of
that the peering exchange network (IXP) peering links. Regional (tier-2) ISPs are customers
can be seen as the backbone of the Internet of tier-1 TPs. Residential and small business access
itself. Then, it is very important to study and (tier-3) providers are typically customers of tier-2
analyze its robustness. TPs”. Therefore, it is natural to think that the peering
network exchange network (IXP) can be seen as the
In this work we will study IXP network
backbone of the Internet itself.
robustness under targeted attacks. Choosing
the “right” node to disconnect under a greedy Since their correct functioning requires that the
strategy, we will compare how much damage network is properly connected, it is of great
is produced by that node disconnection importance to study their ability to resist failures
and we will compare how fast we can (either unintentional or targeted attacks). This ability
decouple the IXP network using the following is called robustness.
strategies: selecting the node with the higher We consider that an “adversary” should plan a
degree, with higher betweenness centrality, greedy strategy aiming to maximize the damage with
the higher degree in a 2-core network, and the minimum number of strikes. Thus, in this article
node with higher collective influence. we discuss the performance of attacks based on
the node betweenness centrality metric [BMSBJ12]
Our work shows that the best algorithm over the Internet Backbone (the network formed
for limited “strikes” in a targeted attack is by Internet exchange points, IXP), also comparing
selecting the node by higher betweenness. the targeted attack performance against the optimal
However, if a quick attack as important as network decoupling algorithm MinSum [BDSZ16].
The authors declare that there is no conflict of interest regarding
The article is organized as follows: next section
the publication of this paper. Copyright c by the paper’s authors. presents related work, followed by the methodology
Copying permitted for private and academic purposes. for collecting data and creating the IXP network
1
(Section 3), and the analysis of IXP network as a
graph (Section 4). Conclusions are presented in
Section 5.
2 Related work
The idea to consider an IXP-based network as “the
Internet backbone” is not new; It has previously
been used as part of the “internet core” to study the
inter-AS traffic patterns and an evolution of provider
peering strategies [LIJM+ 11], to optimize the content
delivery from Google via direct paths [CSR+ 15] and
the Internet Backbone Market [BFBS05].
To study the robustness of a network, its evolution
against failure must be analyzed. On real–world
situations, networks may confront random failures as
well as targeted attacks. For the latter, two main
categories of attacking strategies have been defined:
simultaneous and sequential attacks [HKYH02a].
Simultaneous attacks choose a set of nodes and Figure 1: IXP Peering Graph
remove them all at once while sequential attacks nodes are sorted by degree at the first iteration and
choose a node to remove and given the impact of in the latter betweenness centrality are recalculated
this removal it chooses another node, proceeding after each disconnection. It is widely accepted to use
iteratively. those metric, because it reflects the importance of an
On [Est06] it was found that targeted attack node in the network [IKSW13]. Also, attack strategies
can be more effective when they are directed to are compared by means of the Unique Robustness
bottlenecks rather than hubs. On [BRSBJ15] authors Measure (R-index) [SMA+ 11], defined as:
present partial values of R-index while nodes are
disconnected, showing the importance of a well 1 X
N
chosen robustness metric for performing the attacks. R= s(Q), (1)
N
For a better understanding of network attacks and Q=1
strategies, see [HKYH02b, MR06, RW10, SSYS10].
where N is the number of nodes in the network and
3 Building the Internet backbone graph s(Q) is the fraction of nodes in the largest connected
component after disconnecting nodes using a given
From peeringdb.com we collected the strategy. The higher the R-index, the better in terms
autonomous systems (AS) from every Internet of robustness.
Exchange Point (IXP) and defined them as graph In order to use more modern metrics, we compared
nodes, where there is an edge between any pair of the performance of both previous metrics against
nodes if and only if there is a physical connection CoreHD [ZZZ16] and Collective Influence (CI)
(e.g.: fiber) between them. Figure 1 shows the [MMB+ 16] algorithms. CoreHD is based on the idea
resulting Graph, which has 786 nodes and 20, 422 that, in a power-law network, there is a high number of
edges. nodes with degree 1 that will not contribute a network
dismantling, thus first the 2-Core (nodes with degree
4 Network Analysis ≥ 2 ) is built and then the node with higher degree is
In our targeted attack, we start testing a sequential removed.
attack on our IXP network with two well known Collective Influence is based on the idea of
metrics: degree and betweenness centrality. At each finding the minimal set of maximal influencers
strike, the next node to disconnect was the one with in a network aiming to remove such set, more
the highest metric value. Notice that in the former the precisely: “the most influential nodes in a complex
2
network form the minimal set whose removal would 5 Conclusions and Future Work
dismantle the network in many disconnected and
In this work we have presented how robust the Internet
non-extensive components” [MMB+ 16]. Following
backbone (the peering AS network) would be if an
the recommendations of [BDSZ16] at each iteration
adversary can choose wisely which AS node link
the node with highest CI2 value (calculating CI for
will aisle (or if it is DDoS-ed, or if a very unlucky
each node using a radius of 2) is removed.
accident happens). Following the recommendations,
the chosen one would be the node with a higher metric
value such as degree, betweenness, or collective
influence.
Our work has shown that the best algorithm for
limited “strikes” in a targeted attack is selecting the
node with higher betweenness. However, if a quick
attack is important as precision, and having limited
CPU resources, the best strategy is to select the nodes
with the higher degree.
As future work we plan to apply similar studies to
other Internet infrastructures, such as country-based
fiber interconnection, submarine Internet cables,
Figure 2: Largest component size. In the plot x-axis etc. Also, we plan to improve the metrics for
is the iteration, and R-index is the area below curves. robustness reflecting both the infrastructure and the
user perception.
Plot in Figure 2 gave an idea for the best algorithm
References
having limited “strikes” in the targeted attack, that
is, selecting the node with higher betweenness. 20% [BDSZ16] Alfredo Braunstein, Luca Dall’Asta,
of “Internet” is disconnected after removing 10% Guilhem Semerjian, and Lenka
of the nodes and around half of the “Internet” is Zdeborová. Network dismantling.
disconnected after removing just a 20% of the nodes. Proceedings of the National Academy
However, if a quick attack is important as precision, of Sciences, 113(44):12368–12373,
and having limited CPU resources (such as, only one 2016.
desktop computer for strategy chosen), it seems that
choosing the nodes with higher degree is the best [BFBS05] Paolo Buccirossi, Laura Ferrari Bravo,
strategy (Figure 3). and Paolo Siciliani. Competition in
the internet backbone market. World
Competition, 28(2):233–252, 2005.
[BMSBJ12] Nicolás Ignacio Bersano-Méndez,
Satu Elisa Schaeffer, and Javier
Bustos-Jiménez. Metrics and models
for social networks. In Computational
Social Networks, pages 115–142.
Springer, 2012.
[BRSBJ15] I. Bachmann, P. Reyes, A. Silva, and
J. Bustos-Jimenez. Miuz: measuring
Figure 3: Largest component size. X-axis is in the impact of disconnecting a node. In
seconds since the beginning of the algorithm, and 2015 34th International Conference of
Y-axis is the larger connected component size. the Chilean Computer Science Society
(SCCC), pages 1–6, Nov 2015.
3
[CSR+ 15] Yi-Ching Chiu, Brandon Schlinker, percolation in massively large social
Abhishek Balaji Radhakrishnan, Ethan media. Scientific reports, 6, 2016.
Katz-Bassett, and Ramesh Govindan.
Are we one hop away from a better [MR06] Wojciech Molisz and Jacek Rak.
internet? In Proceedings of Internet End-to-end service survivability under
Measurement Conference, pages attacks on networks. Journal of
523–529. ACM, 2015. Telecommunications and Information
Technology, pages 19–26, 2006.
[DD10] Amogh Dhamdhere and Constantine
[RW10] Jacek Rak and Krzysztof Walkowiak.
Dovrolis. The internet is flat: Modeling
Survivability of anycast and unicast
the transition from a transit hierarchy
flows under attacks on networks.
to a peering mesh. In Proceedings
In International Congress on Ultra
of Co-NEXT, pages 21:1–21:12, New
Modern Telecommunications and
York, NY, USA, 2010. ACM.
Control Systems, pages 497–503. IEEE,
[Est06] Ernesto Estrada. Network robustness 2010.
to targeted attacks. the interplay of [SMA+ 11] Christian M Schneider, André A
expansibility and degree distribution. Moreira, José S Andrade, Shlomo
The European Physical Journal Havlin, and Hans J Herrmann.
B-Condensed Matter and Complex Mitigation of malicious attacks
Systems, 52(4):563–574, 2006. on networks. Proceedings of the
National Academy of Sciences,
[HKYH02a] Petter Holme, Beom Jun Kim,
108(10):3838–3841, 2011.
Chang No Yoon, and Seung Kee
Han. Attack vulnerability of complex [SSYS10] Ali Sydney, Caterina Scoglio, Mina
networks. Physical Review E, Youssef, and Phillip Schumm.
65(5):056109, 2002. Characterising the robustness of
complex networks. International
[HKYH02b] Petter Holme, Beom Jun Kim, Journal of Internet Technology and
Chang No Yoon, and Seung Kee Secured Transactions, 2(3-4):291–320,
Han. Attack vulnerability of complex 2010.
networks. Physical Review E,
65(5):056109, 2002. [ZZZ16] Lenka Zdeborová, Pan Zhang, and
Hai-Jun Zhou. Fast and simple
[IKSW13] Swami Iyer, Timothy Killingback, Bala decycling and dismantling of networks.
Sundaram, and Zhen Wang. Attack Scientific reports, 6, 2016.
robustness and centrality of complex
networks. PloS one, 8(4):e59613, 2013.
[LIJM+ 11] Craig Labovitz, Scott Iekel-Johnson,
Danny McPherson, Jon Oberheide, and
Farnam Jahanian. Internet inter-domain
traffic. ACM SIGCOMM Computer
Communication Review, 41(4):75–86,
2011.
[MMB+ 16] Flaviano Morone, Byungjoon Min,
Lin Bo, Romain Mari, and Hernán A
Makse. Collective influence algorithm
to find influencers via optimal
4