=Paper=
{{Paper
|id=Vol-1950/paper5
|storemode=property
|title=Modelling the Internet as Spatially Constrained Interdependent Networks
|pdfUrl=https://ceur-ws.org/Vol-1950/paper5.pdf
|volume=Vol-1950
|authors=Ivana Bachmann,Javier Bustos
|dblpUrl=https://dblp.org/rec/conf/ssn/BachmannB17
}}
==Modelling the Internet as Spatially Constrained Interdependent Networks==
https://ceur-ws.org/Vol-1950/paper5.pdf
Modelling the Internet as
Spatially Constrained Interdependent Networks
Ivana Bachmann Javier Bustos-Jiménez
NIC Labs, Universidad de Chile, Chile NIC Labs, Universidad de Chile, Chile
ivana@niclabs.cl jbustos@niclabs.cl
connected to the Internet in case of failure. However,
to understand the Internet robustness we must also
Abstract understand the underlying structures that compose it.
On the one hand, there is the physical Internet net-
The modern world has made the Internet a work comprised by cables, antennas, routers, etc. On
need for the people. More than ever before we the other hand there is the logic Internet network com-
have Internet dependent systems and devices. prised by autonomous systems (AS) [AS] which are
Thus, it is important to maintain the infras- connected through the BGP protocol [BGP]. These
tructure of the Internet working properly. In networks interact with each other allowing for the In-
order to do this first it is necessary to under- ternet to properly function. In this work we will focus
stand and model the behaviour of the compo- on these two layers.
nents of the Internet network. In this paper The area of interdependent networks studies systems
we characterize the interactions between the composed of two or more interacting networks, with
Internet’s physical and logical layers, and rec- behaviours produced by such interactions that are not
ommend a mixture of existing models from usually present on single networks. The study of the
the literature to model this specific case. We robustness of interdependent networks is a problem
study two cases of simulated Internet struc- that has been explored in the last decade, leading
tures and find that an Internet physical layer to the development of several frameworks to tackle
embedded in a long and narrow space with it. Among these frameworks we can find the “one to
Chile-like proportions of with and length is one” model presented by Buldyrev et al. [BPP+ 10],
more fragile to random attacks than an Inter- where they consider two interacting networks where
net physical layer embedded in a square space. each node depends on exactly one node in the other
network with mutual dependency, this means that if
1 Introduction a node fails then necessarily its interdependent neigh-
In our modern world communication networks are of bour will fail.
extreme importance and the Internet is no exception. We can also find “many to many” kind of models,
From communicating with friends to coordinating and where each node may be interconnected to 0 or more
transmitting crucial messages, the Internet is, nowa- nodes in the other network [NST13, Qiu13, DTD+ 14,
days, a big part of day to day activities in our society. RHB+ 14, CD15]. In these models dependencies may
Thus, we must be able to understand how the Internet be directed or undirected. Different many to many
works and react under conditions that may affect the models have different rules for how many node’s inter-
Internet functionality. In particular we must under- dependencies have to fail for the node to fail.
stand what would happen in case of a random failure Other models focus more on specific characteristics of
or, even worse, a targeted attack. the system that want to be represented. Examples
In order to understand what would happen to the In- of this are the works presented in [PM13, MKT14,
ternet under different failure scenarios it is necessary HLGT16] where the main purpose of the model is to
to study its robustness. Here, we consider that Inter- represent a power grid network coupled with their con-
net robustness refers to the ability of keep the users trol network, or the work of Li et al. [LBB+ 12] where
main feature of the model is to represent spatially con-
Copyright c by the paper’s authors. Copying permitted for strained networks.
private and academic purposes.
In order to measure the robustness of interdepen-
dent networks different indexes and metrics are used.
Some of these include the size of the giant mutually
connected component [LBB+ 12, KLCB14, ZXZX16,
WKVM16], the percolation threshold [BPP+ 10, Figure 1: Continental Chilean geography. The width
DBBH13, LCB16], the time delay of information trans- (E-W) to length (N-S) proportion of Chile is 1:25.
mission [ZPC11], etc.
between each pair of nodes, thus, the links of the net-
In this work we characterized the Internet as an in-
work are undirected links. Additionally, this network
terdependent network comprised by the physical In-
has characteristics specific to its physical nature such
ternet network and the logic Internet network. Here,
as distances and failure probability given their geo-
each layer is characterized as well as the interactions
graphic location, for example, due to natural catastro-
between them (section 2). Using this characterization,
phes.
in section 3, we provide a model and metric selected
from the existing literature that can be used to study
2.2 logical network
the Internet robustness considering a user based per-
spective of the robustness. Finally, in section 4 we The logical network is the one that maps communica-
simulate Internet interdependent systems and study tion routes among the ASs. An AS is a subnetwork
two kinds of physical spaces: a long and narrow space that autonomously manages the routing within itself.
with a width to length proportion of 1:25, in order On the logical network each AS represents a node while
to emulate the Chilean geography, and a square space each connection given by the BGP between nodes rep-
with a width to length ratio of 1:1. Our finding sug- resent a link. In this network the information flow is
gests that a long and narrow geography increases the bidirectional, hence the links in this network are undi-
vulnerability of the Internet interdependent system. rected. Additionally, in order for a node to have access
to the Internet service it must be connected through
at least one path to a Internet Service Provider (ISP),
2 Characterizing the Internet
and to an International gateway to have access to the
as an interdependent system worldwide network.
The Internet can be seen as the emerging interdepen-
dent network formed by the physical network which 2.3 Interdependencies
contains antennas, routers, cables, etc. and the logi- The physical and the logical network interact with each
cal network which contains ASs connected according other, i.e., they are interdependent networks. These
to the BGP routing protocol. These networks depend interactions are mutual.
on each other as each AS must be allocated on at least On the one hand, we have that each ASs node in the
one working node of the physical network to stay func- logical network may be allocated in one or more nodes
tional, and at least one AS must be running and an- in the physical network. If a node in the physical net-
swering on a physical node in order for it to maintain work doesn’t have a path to an ISP or gateway coun-
the communication with other nodes. terpart node (logical networks), then it will not have
In this section we characterize the Internet as an inter- access to Internet service. As for the dependence, if
dependent network, the physical network and the logi- all the physical nodes where a logic node is allocated
cal network are characterized in subsection 2.1 and 2.2 fail, then the logic node will also fail, as none of its
respectively, and the inter-dependencies between them physical systems is able to communicate.
are described in subsection 2.3. On the other hand, we have that a physical node may
route a set of ASs. Hence, if all the logic nodes allo-
2.1 Physical network cated in it fail, then the physical node won’t be able to
answer to any other node within the physical network,
The physical network is the one responsible of transfer- so we consider that it failed too.
ring and distributing the information through physical This way the dependencies between networks are es-
means such as cables, optical fibers, routers, and an- tablished as “many to many” in a bidirectional fash-
tennas. Here, processing and redistributing informa- ion, with the condition that if all of the interdependent
tion equipment such as servers, routers, or antennas nodes of a particular node fail, then it fails.
correspond to the nodes of the network. While the
physical means that connect the nodes, such as cables,
fibers, or electromagnetic signals in the case of anten-
3 The model
nas, correspond to the links of the network. Given the characterization of the interdependent sys-
In this network the information flow is bidirectional tem we selected from the literature a model and set of
metrics. The objective was to select a framework to u and v, each of radius d(v, u), where d(v, u) is the eu-
study the robustness of interdependent networks with- clidean distance between node u and v. This way, the
out mayor modifications. In order to do so we referred adapted relative neighbourhood model creates a net-
to the work presented in [Bac17] where 57 papers pre- work where 2 nodes are connected if in the direction
senting or using frameworks to study the robustness where they face each other the space is empty. This
on interdependent networks were reviewed. model captures a physical Internet network built with
In order to select a proper framework we considered finite resources, where longer links have a higher cost
the consumer-provider nature of the logic and the relative to shorter links.
physical network. We also took into account the met- Finally, the logical network was modeled as a net-
ric’s ability to measure the users’ access to the Inter- work with Power-law degree distribution using λ = 2.7
net. [FFF99] as it has been widely used to model BGP net-
Given the consumer-provider nature of the system as works.
well as its “many to many” inter-dependencies, we de-
termined that among the papers considered in [Bac17] 3.1 Cascading process
the work presented by Parandehgheibi et al. [PM13]
was the best option to analyze the case of the Internet In the figure 2 (extracted from [PM13]) there is an
network. example of a cascading failure process. In this ex-
The model presented in the work of Parandehgheibi ample unidirectional dependencies are considered be-
et al. consists of two networks, the Power grid net- tween the networks. Blue links represent support links
work, and the Control and Communication network from the CCN to the Power Grid while orange links
(CCN). Each network has provider nodes and con- represent support links from the Power Grid to the
sumer nodes. The latter nodes must have a path to CCN. On step 1 S4 fails, leaving R3 without support
a provider in order to function properly. Thus, the from the Power Grid. Then, on step 2 node R3 fails.
power grid provider has generator nodes G, and sub- With the failure of R3, R2 has no longer a path that
station nodes S, while the CCN network has router connects it to the control center C, also S1 and S3
nodes R, and control centers C (see figure 2). loose their support from the CCN network. Thus, in
The inter-dependencies establish support-dependence step 3 R2, S1, and S3 fail. With the failure of S1, the
relations. This relations may be unidirectional or bidi- node S2 has no longer a path to the generator node
rectional. In the unidirectional case if a node in one of G, and the node R1 looses all support from the power
the networks gives support to a node in the other net- grid. Hence, in step 4 R1 and S2 fail and the system
work, this support is not necessarily reciprocal, while reaches a total failure state.
in the bidirectional case it is reciprocal.
A consumer node will stay functional if there is a path 3.2 Robustness metrics
from it to the a provider node and if it has at least The metric used in [PM13] is the minimum total
one of their support nodes in the other network still failure removals of nodes (Node-MTFR). This met-
working. ric indicates the minimum amount of nodes to be
The bidirectional inter-dependencies version of this removed to cause total failure. In order to cause
model can be directly applied over the Internet inter- total failure, all the interdependent nodes must fail
dependent system given the characterization that we according to [PM13]. This characteristic allows us
previously established (see section 2). The providers to measure when all the users (ASs nodes) will stop
in the logical network are the nodes containing ISPs having access to the Internet as each AS is dependent
or International gateways. In the physical network on at least one physical node. Thus, this metric
the providers are the nodes where the logical network is useful to measure the robustness given our user
providers are allocated. oriented approach of it.
As for the physical network, its model was based on the We also used the fractional size of the largest
relative neighbourhood model presented in [WKVM16] connected component in the logical network G,
for interdependent networks, which describes the con- to measure the amount of users with Internet ac-
ditions to inter-connect a pair of nodes where each cess, and the node-MTFR metric presented in [PM13].
belong to a different physically embedded network.
We have adapted this model to build a single physical
layer. In our adaptation, given a finite 2-dimensional
space with a certain shape and a number of nodes Np , 4 Results
each node is randomly allocated in the space. Two We studied the robustness of 14 simulated interdepen-
nodes u and v get to be connected if there is no other dent systems modelled according to the model pre-
node in the intersection area of the circles centered at sented in section 3.
Two scenarios for the physical space shape were repre- size of the largest connected component of the logical
sented, the first one representing a square space with network G of the system with its physical network em-
a 1:1 width to length ratio, and the second one repre- bedded in a long and narrow space presents a faster de-
senting a long and narrow space such as Chile’s geog- cay in comparison to the interdependent system with
raphy (see figure 1) with a 1:25 width to length ratio. its physical network embedded in a square space. We
In both cases, the logical network was simulated with can see this result on figure 4(b), where (1 − p) is the
300 nodes, and the physical network with 2000 nodes, fraction of nodes removed at random over the whole
following the Chilean proportions of nodes in both net- interdependent system. This means that less nodes
works. have to be removed to cause the same damage to the
We found that G presents a continuous decay under system.
random attacks over the whole network, meaning that We also observed that the node-MTFR of both sys-
no abrupt collapse is observed on the logical network tems remain really close to the total amount of nodes
under random attacks. Also, on average, the fractional in the logical network (see table 1), which is less than
the average amount of nodes that must be removed
under random attacks to cause the same damage.
Figure 3: Results for long and narrow physical space
averages on the left, and square space averages on the
right.
Table 1: Average node-MTFR by space type
Space type mean node-MTFR
Long and narrow 299.9
Square 299.25
4.1 Square physical space
For the square physical space 4 interdependent sys-
tems were simulated. Each system was randomly at-
tacked to study their robustness, and for each system
the node-MTFR was calculated. In figure 4(a) we show
the average results obtained over 100 iterations of the
random attacks. In table 1 we show the average node-
MTFR for these simulated interdependent networks.
Similar to the case of a long and narrow physical
space it can be seen that node-MTFR is able to cause
total failure by removing about 13% of the system’s
nodes (299 nodes out of 2300, see Table 1), while under
random attacks 30% of the nodes must be removed for
Figure 2: Cascading process as presented in [PM13]. G to be under 0.01.
lated physical and logical networks. It was also pro-
posed a modified version of the relative neighborhood
model presented in [WKVM16] to simulate physical
networks. Using this modified relative neighborhood
model we randomly attacked 2 types of systems. One
with its physical network embedded in a square space,
and another with its physical network embedded in
a long and narrow space following the proportions of
Chile. We found that the narrow and long space phys-
ical networks results in a more fragile interdependent
system structure from the user’s point of view. This
suggests that studying the particular scenarios of coun-
(a)
tries with geographies similar to the Chilean one may
be of special concern when studying Internet robust-
ness. Finally, we observed that node-MTFR may be
a more accurate measure of Internet infrastructure ro-
bustness than random attack as less nodes are required
to cause total failure in comparison to random attacks.
As future work remains to study the effect on the
robustness of randomly attacking each network sep-
arately, as well as studying different coupling pat-
terns of the interacting networks, different amount of
providers, and space configurations for the Internet
physical network. It is of special interest for the case
of the Chilean Internet to analyze the effect of physi-
(b)
cal networks that contain areas where nodes can’t be
placed on. This areas could be used to represent ge-
Figure 4: Green lines show each simulation results.
ographic features such as islands or mountains which
Blue line shows average of all simulations. In (a) Re-
are prevalent on the Chilean geography.
sults for square physical space. In (b) Results for long
and narrow physical space.
Acknowledgement
4.2 Long and narrow physical space
The long and narrow physical space follows the This work was partially funded by CONICYT Doctor-
Chilean country width to length proportion of 1:25. ado Nacional 21170165.
An image of the country can be seen in figure 1. For
the physical space 10 interdependent systems were References
simulated. Each system was randomly attacked to
study their robustness, and for each system the node- [AS] Autonomous system. https://tools.
MTFR was calculated. In figure 4(b) we show the ietf.org/html/rfc1930. Accessed: 03-
average results obtained over 100 iterations of the ran- 07-2017.
dom attacks, and in table 1 the average node-MTFR
value obtained for each pair of networks is simulated. [Bac17] Ivana Bachmann. Framework de estu-
We can observe that under random attacks about 29% dio multi-capa para resiliencia de Inter-
of nodes must be removed of the interdependent sys- net chileno. Master’s thesis, Universidad
tem in order to reach values of G inferior to 0.01, while de Chile, Santiago, Chile, 2017.
node-MTFR can cause total failure by removing only
13% of the nodes in the system. [BGP] Border gateway protocol. https://
tools.ietf.org/html/rfc4271. Ac-
cessed: 03-07-2017.
5 Conclusions
In this work we characterized the Internet as the in- [BPP+ 10] Sergey V Buldyrev, Roni Parshani, Ger-
terdependent system comprised by the Internet logical ald Paul, H Eugene Stanley, and Shlomo
network and the Internet physical network. We found Havlin. Catastrophic cascade of fail-
a model and a metric suitable for studying the Internet ures in interdependent networks. Nature,
from the literature ‘as is’, and we used it over simu- 464(7291):1025–1028, 2010.
[CD15] Srinjoy Chattopadhyay and Huaiyu Dai. [MKT14] Yuki Matsui, Hideharu Kojima, and Tat-
Towards optimal link patterns for robust- suhiro Tsuchiya. Modeling the interac-
ness of interdependent networks against tion of power line and scada networks.
cascading failures. In 2015 IEEE Global In 2014 IEEE 15th International Sym-
Communications Conference (GLOBE- posium on High-Assurance Systems En-
COM), pages 1–6. IEEE, 2015. gineering, pages 261–262. IEEE, 2014.
[DBBH13] Michael M Danziger, Amir Bashan, [NST13] Duy T Nguyen, Yilin Shen, and My T
Yehiel Berezin, and Shlomo Havlin. In- Thai. Detecting critical nodes in interde-
terdependent spatially embedded net- pendent power networks for vulnerability
works: dynamics at percolation thresh- assessment. Smart Grid, IEEE Transac-
old. In Signal-Image Technology & tions on, 4(1):151–159, 2013.
Internet-Based Systems (SITIS), 2013 [PM13] Marzieh Parandehgheibi and Eytan
International Conference on, pages 619– Modiano. Robustness of interdependent
625. IEEE, 2013. networks: The case of communication
networks and the power grid. In Global
[DTD+ 14] Gaogao Dong, Lixin Tian, Ruijin Du,
Communications Conference (GLOBE-
Min Fu, and H Eugene Stanley. Analysis
COM), 2013 IEEE, pages 2164–2169.
of percolation behaviors of clustered net-
IEEE, 2013.
works with partial support–dependence
relations. Physica A: Statistical Mechan- [Qiu13] Yuzhuo Qiu. The effect of clustering-
ics and its Applications, 394:370–378, based and degree-based weighting on ro-
2014. bustness in symmetrically coupled het-
erogeneous interdependent networks. In
[FFF99] Michalis Faloutsos, Petros Faloutsos, and 2013 IEEE International Conference on
Christos Faloutsos. On power-law rela- Systems, Man, and Cybernetics, pages
tionships of the internet topology. In 3984–3988. IEEE, 2013.
ACM SIGCOMM computer communica-
tion review, volume 29, pages 251–262. [RHB+ 14] Saulo DS Reis, Yanqing Hu, Andrés
ACM, 1999. Babino, José S Andrade Jr, Santiago
Canals, Mariano Sigman, and Hernán A
[HLGT16] Yuqi Han, Zhi Li, Chuangxin Guo, and Makse. Avoiding catastrophic failure in
Yuezhong Tang. Improved percolation correlated networks of networks. Nature
theory incorporating power flow analy- Physics, 10(10):762–767, 2014.
sis to model cascading failures in cyber-
physical power system. In Power and En- [WKVM16] Xiangrong Wang, Robert E Kooij, and
ergy Society General Meeting (PESGM), Piet Van Mieghem. Modeling region-
2016, pages 1–5. IEEE, 2016. based interconnection for interdepen-
dent networks. Physical Review E,
[KLCB14] Yosef Kornbluth, Steven Lowinger, 94(4):042315, 2016.
Gabriel Cwilich, and Sergey V Buldyrev. [ZPC11] Xian Zhang, Chris Phillips, and Xiuzhong
Cascading failures in networks with Chen. An overlay mapping model for
proximate dependent nodes. Physical achieving enhanced qos and resilience
Review E, 89(3):032808, 2014. performance. In Ultra Modern Telecom-
munications and Control Systems and
[LBB+ 12] Wei Li, Amir Bashan, Sergey V Buldyrev,
Workshops (ICUMT), 2011 3rd Interna-
H Eugene Stanley, and Shlomo Havlin.
tional Congress on, pages 1–7. IEEE,
Cascading failures in interdependent lat-
2011.
tice networks: The critical role of the
length of dependency links. Physical re- [ZXZX16] Xue-Jun Zhang, Guo-Qiang Xu, Yan-Bo
view letters, 108(22):228702, 2012. Zhu, and Yong-Xiang Xia. Cascade-
robustness optimization of coupling
[LCB16] Steven Lowinger, Gabriel A Cwilich, and preference in interconnected networks.
Sergey V Buldyrev. Interdependent lat- Chaos, Solitons & Fractals, 92:123–129,
tice networks in high dimensions. Physi- 2016.
cal Review E, 94(5):052306, 2016.