社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

サービスネットワーク連携のための高信頼化ネットワーク基盤構築手法
荒川

伸一†

荻野

長生††

北原

武††

長谷川

剛††† 村田正幸†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5†† 株式会社 KDDI 総合研究所 〒 356-8502 埼玉県ふじみ野市大原 2-1-15††† 大阪大学サイバーメディアセンター 〒 560–0043 大阪府豊中市待兼山町 1-32
E-mail: †arakawa@ist.osaka-u.ac.jp
あらまし

情報通信技術が社会に深く浸透し、あらゆる機器や人が情報ネットワークを構成する時代が到来しつつある。特に近年は、ネットワーク仮想化技術の進展を背景に、いくつかの（マイクロ）サービスネットワークを連携させ、新たなサービスを創発するネットワークシステムが注目されている。本稿では、複数のサービスネットワークがネットワークを介して相互に接続される “Network of Networks” に着目し、トポロジー構造およびトラヒックフローの振る舞いの観点から相互に接続されたネットワークの性質を明らかにする。固有ベクトル中心性にもとづいてノードを Central ノードと Periphery ノードに分類し、これらのノードの接続組み合わせによる４つの相互接続ネットワー
クを生成し、ノード故障発生時のスループット性能の変化を調べた。その結果、ネットワークのコアとなるノード近隣の固有値ベクトル中心性が低い Periphery ノード同士を接続することで、高い信頼性と効率性が得られることが明らかとなった。

On the Strategy of Making Reliable Inter-Connected Network
for Cooperative Service Networks
Shin’ichi ARAKAWA† , Nagao OGINO†† , Takeshi KITAHARA†† ,Go HASEGAWA††† , and Masayuki MURATA†† Graduate School of Information Science and Technology, Osaka University Yamadaoka 1–5, Suita, Osaka,
565–0871 Japan†† KDDI Research, Inc. 2-1-15 Ohara, Fujimino-shi, Saitama, 356-8502, Japan††† Cyber Media Center, Osaka University 1-32 Machikaneyama, Toyonaka, Osaka, 560-0043 Japan
E-mail: †arakawa@ist.osaka-u.ac.jp
Abstract In recent years, developing a new service by collaborating two or more (micro-)services has attracted
much attention. Such the trends of service development lead to increase the importance on understanding inter-networking of service systems. In this paper, we investigate characteristics of inter-connected networks from both
topological and traﬃc-flow perspectives. Based on the eigenvalue centrality and location of nodes, four strategies
for connecting two networks are developed and examined for constructing inter-connected networks. The results
showed that high reliability and eﬃciency are achieved by connecting periphery nodes, which have low eigenvalue
centrality, around core nodes.
Key words Inter-connected networks, Network of networks, Resilience, Network design, Eigenvector centrality

1. Introduction

two or more (micro-)services has attracted much attention. One ofexamples is a concept of API economy where Internet services con-

Many people enjoy Internet services such as SNS or cloud ser-nect and collaborate each other through web APIs. Such the trends

vices and expect new Internet services to further improve our Inter-of service development lead to increase the importance on under-

net life. In recent years, developing a new service by collaborating

standing inter-networking of services, a. k. a, network of networks.
—1—

Several studies investigate topological characteristics of interconnected networks. Refs. [1, 2] evaluate the reliability of inter-

local network ‫ܣ‬connected networks by changing structure for connecting two networks. They introduce two metrics, inter degree-degree coefficient(IDDC) and inter-clustering coefficient (ICC), to characterize thestructure for connecting two networks. IDDC represents the similarity of degree of two nodes that form an inter-connected link,

local network ‫ܤ‬while ICC represents the clustering coefficient among nodes thatform inter-connected links. Using the random network and scale-Inter-connected node

free network, they show that the reliability of inter-connected net-

Inter-connected links

work improves with high values of IDDC and ICC. Brummit etal. [3] showed that too many inter-connected links increase the risk

Figure 1: Illustration of an inter-connected networkof large-scale failures because inter-connected links help to propagate impact of failures from one network to another network.
In the case of interconnections between communication networks, these evaluations are not sufficient because they do not consider about traffic flow. Their evaluations are only based on topological metrics. However, in communication networks, traffic flow
is important because the quality of communication is dependent on
not only connectivity but also on the traffic concentration of somenodes. The difference of connecting structure between networks isdependent on which nodes are connected. Therefore, it needs toconsider about the amount of traffic flow on links and which nodes
are connected for making an inter-connected network.
In this paper, we investigate the characteristics of inter-connected
networks from both topological and traffic perspectives. Although
the actual application of a network of networks should suppose multiple networks, we investigate the simplest scenario where two networks are connected via inter-connected links (Figure 1). Moreover,
we assume that there is a cooperative relationship between two network operators, and thus some information such as topological information to decide the inter-connected nodes is available. Then,we will provide an approach to generate an inter-connected networkand evaluate the reliability of generated inter-connected networks
before and after failures. For generating the inter-connected networks, nodes are first classified into Central nodes and Peripheral
nodes based on their roles of nodes in the network. Next, we prepare some connection strategies to construct inter-connected networks with different inter-connected structure such as CC (Central
node connects to Central node) or CP (Central node connects to
Peripheral node). With the inter-connected networks with different
connection strategies, we evaluate the reliability from the viewpointof not only topological metrics but also traffic-flow metrics.
This paper is organized as follows. Section 3 shows our strategies for making inter-connected networks. In Section 4, we evaluate
performance of inter-connected networks and its reliability against
node failures. Finally, Section 5 concludes this paper.

2. Construction of Inter-connected Networks
It is important to consider the connecting structure among net-

works for designing reliable and efficient networks. In this section,
we discuss what properties of nodes are suitable for deciding interconnecting nodes when two networks cooperatively connects eachother for the common goal of constructing a reliable and efficientinter-connected network. Here, reliable represents that a network
can keep the connectivity among nodes as much as possible evenwhen failures occur, and efficient represents that a network can communicate with high throughput. We first explain a basic strategy andsome premise on making an inter-connected network. Then, we define the properties of nodes to use and explain connecting strategies
to construct inter-connected networks.
2. 1 Basic Strategy for Communication Networks
When constructing an inter-connected network by connecting
communication networks under the number of inter-connecting
links is not limited, resilience of the inter-connected network between networks is the highest when all nodes have inter-connecting
links. That is, it is more difficult to separate an inter-connected
network into two networks when failures occur. However, it is notrealistic because of a lot of operational cost. Owing to this, under the number of inter-connecting links is limited, we construct aninter-connected network to enhance the reliability.
A problem is what properties of nodes to make inter-connecting
links. The properties represent the role or importance of nodes. Oneof approaches is to attach inter-connecting links to nodes in the core
part of networks as we can easily imagine. Nodes in the core part of
networks are the placed at the center of networks and play an important role in networks. Another approach may use nodes around periphery nodes. In this paper, we investigate which is better whether
core or periphery nodes for inter-connected nodes.
To classify nodes into core and periphery, what criteria should beused? In our study, we use eigenvector centrality as criteria. Eigenvector Centrality indicates the importance of a node’s neighbors,and can be high because a node has either numerous or importantneighbors. In the communication networks, eigenvector centrality
can be regarded as the amount of traffic through nodes. Intuitively, it
is natural that the amount of traffic traversing a node increases when—2—

its neighbors also process so much traffic. Hence, using eigenvector centrality of nodes, we can suppose how much traffic is pro-in network B•

PP: Peripheral node in network A connects to Peripheral

cessed on each node, i.e. the importance of each node in networks.

node in network B

Thereby, nodes with high eigenvector centrality can be regarded as

When choosing inter-connecting nodes, we consider following twocore nodes and nodes with low eigenvector centrality can be re-intentions. One is that each node in network A and B with closer

garded as periphery nodes, such as placed on the edge of networks.

distance are connected. This is because it is known that the costs of

Although the study focusing on an inter-connected network of Web

constructing links are dependent on their length [5]. For example, inpages [4] also use eigenvector centrality as criteria to classify nodes,

CC, a Central node in the east (in the case of U.S.A) of network A

their goal of the inter-connection is to enhance eigenvector central-connects a Central node in the east of network B. As a result, we canity of networks (the sum of eigenvector centrality of each node in

get inter-connected networks with different connecting structure be-

network). Because in communication networks regarding eigenvec-

tween networks. The other intention is that inter-connecting nodes

tor centrality as traffic, enhancing eigenvector centrality of only ashould be selected so as not to concentrate on one place. Whenpart of nodes means enhancing loads of them, as for our study, weinter-connecting nodes are concentrate on one place or city/state, allconstruct an inter-connected network to enhance reliability and ef-

inter-connecting nodes might be failed simultaneously when large-

ficiency, not to enhance eigenvector centrality.

scale disasters occur. For example, considering the topography in

In our current approach, the topological information of two net-

the United States, it is better to pick nodes from New York, Chicago

works is required to calculate eigenvector centrlaity. However, in an

and San Francisco than to pick nodes from only New York. There-

actual scenario, the topological information may not be disclosed

fore, we use the information of the module structure of network in

as Internet’s ASes are. It may be hard to know the information toorder to distinguish the location of nodes. Based on the information

calculate eigenvector centrality of another network. However, un-of module structure and eigenvector centrality of nodes, Central andder cooperative relationship, the essential information required for

Peripheral nodes are defined as follows.

inter-connection can be shared. In this paper, we assume that the•Centralinformation to calculate eigenvector centrality is available and use

We pick nodes with links between modules as the candidate of Cen-

topological information in the evaluation.

tral. We calculate eigenvector centrality for adjacency matrix of a

2. 2 Criteria of Central and Peripheral Nodes

local network. In each module, a node with the highest eigenvector

In this section, we explain criteria of Central and Peripheral

centrality is defined as Central node.

nodes. For reference [4], the nodes are classified into Central nodes•

Peripheral

and Peripheral nodes based on eigenvector centrality of nodes.

We calculate eigenvector centrality with adjacency matrix of each

Eigenvector centrality is calculated as the first eigenvector ⃗x ofmodule, which means the regarding each module as network. In

the adjacency matrix M . Centrality of node i is the ith factor ofeach module, a node with the highest eigenvector centrality is de-⃗x = {v1 , v2 , ..., vN }T (N is the number of nodes). Eigenvector

fined as Peripheral node. Peripheral nodes can be chosen as theCentrality indicates the importance of a node’s neighbors, and cansame nodes as Central but we allow that.

be high because a node has either numerous or important neigh-Assuming that the number of inter-connecting links equals to thebors. In the communication networks, eigenvector centrality can benumber of modules at first of evaluation. It is the situation that theregarded as the amount of traffic through nodes. Intuitively, it isplace of inter-connecting nodes is well distributed. However, it isnatural that the amount of traffic traversing a node increases when

better that the number of inter-connecting links is few as much as

its neighbors also process so much traffic. Hence, we can regard

possible. Therefore, we regard the number of inter-connecting links

nodes with higher eigenvector centrality as more important nodes.

as a parameter, and consider decreasing the number in evaluation.

Based on the eigenvector centrality, we classify nodes into Central
and Peripheral. The definition is explained in Section 2. 3.
2. 3 Making Reliable and Efficient Inter-connected Networks
For construcging an inter-connected network from network A andB, we consider four connecting strategies based on the role of interconnecting nodes as follows.
•

CC: Central node in network A connects to Central node in

network B•

CP: Central node in network A connects to Peripheral nodein network B•

PC: Peripheral node in network A connects to Central node

3. Evaluation
3. 1 Local Networks
We consider an inter-connected network by connecting network
A and B. As for network A and B, we use an ISP topology, whichhas 523 nodes and 1304 links, as shown in Figure 2.
Since all nodes have the properties of states based on its location
information, we regard one state as one module. However, there
are some exceptions because of the size of states. In the ISP topology, 82 nodes belong to California while only one node belongs to
Kentucky. Since small-scale states (with a few nodes) are a part oflarge-scale states (with many nodes) generally, it is not suitable for
—3—

6.55

Average hop length

6.5
6.45
6.4
6.35
6.3
6.25
6.2
CC

CP (PC)PP

Connec!ng strategy

Figure 3: Average hop length

Figure 2: ISP topology
12using such nodes as inter-connecting nodes, under the purpose ofstates are not regarded as modules. 12 states remain after excluding small-scale states, where the number of nodes in states is lessthan 11. To the contrary, there is a so large-scale state. The num-

10

Average flow rate

obtaining distributed inter-connecting nodes. Thereby, small-scale

8
CC
6
CP
4

PC
PP

ber of nodes in California is about 1.5 times larger than that of in

2

New York, which is the second largest state. In addition, the area0
1

of California is large and its domain expands from north to south
widely. To select inter-connecting nodes adequately, we divide California into two states heuristically. Consequently, we can obtain 13

2

3

4

5

6

7

8

9

Hop length

Figure 4: Average flow rate of intra-communication before failures

states. In this figure, nodes are colored by module structure. The
same colored nodes are in the same module and non-colored nodes
are in small-scale modules. We choose inter-connectingnodes fromeach state.

connected links.
Figure 3 shows average hop length d of inter-communication. In
the figure, X-axis shows each connecting strategy and Y-axis shows

3. 2 Link Capacity

average hop length d. We can see that d is the shortest in CC net-

An inter-connected network has two classes of links: internal

work and is the longest in PP network. Figure 4 shows the average

links and inter-connected links. The link capacity of internal links

flow rate of intra-communication. The flow rate of each node pairwithin network A is set based on the amount of traffic through its

is calculated such that the link capacity is fully utilized. Here, welink when all node pairs in network A communicate. The link ca-

focus on node pairs in network A as intra-communication. In thesepacity of inter-connecting link i is based on the amount of traffic

figures, X-axis shows the hop length of node pairs and Y-axis shows

Si through its link when all node pairs in inter-connected network

the average flow rate per hop length of node pairs. We can see that,

communicate. Then, the capacity of inter-connecting link i is de-in CC and CP network which use Central nodes in network A as

fined asinter-connecting nodes, the average flow rate of long-range commu-Sici =∗ Ctotal ,(1)
NA ∗ NB
where Ctotal is the total capacity of inter-connecting links and NA

nication becomes low. However, in PC and PP network where Pe-(and NB ) is the number of nodes in network A (and B).
3. 3 Characteristics of Inter-connected Networks
In this section, we evaluate the characteristics of inter-connected
networks. Based on the strategies CC, PP, CP and PP, we generated four inter-connected networks. We set the number of interconnecting links to 13, which equals to the number of modules,
and the sum of link capacity of inter-connecting links Ctotal to thenumber of node pairs whose minimum hop path passes through theinter-connected links. Thus, Ctotal is set to NA × NB . Hereafter,
we call inter-communication as the communication between nodepairs across the inter-connected links and intra-communication as
the communication between node pairs that do not use the inter-ripheral nodes in network A are used as inter-connecting nodes, theaverage flow rate is still large even in long-range communication.
Next, we show the average flow rate of inter-communication. Figure 5 shows the average flow rate of node pairs in the same moduleand Figure 6 shows the average flow rate of node pairs whose nodes
belongs to the different module. In these figures, X-axis shows individual connecting structure. We can see that it achieves higher flowrate of node pairs in the same module by using Peripheral nodes
regardless of network A or B.
Hereafter, we show the characteristics of inter-connected networks after a node failure. Note that, because we use the same
topology for network A and B, we assume that the node in network B in the same place of failed node in network A is also failed—4—

1.0E+05

The number of node pairs decreasing
flow rate

Average ﬂow rate of node pairs in thesame module

16
14
12
10
8
6
4
2
0
CC

CP

PC

PP

9.0E+048.0E+04
7.0E+04
CC
CP
PC
PP

6.0E+04
5.0E+04
4.0E+04
3.0E+04
1

Connec"ng strategy

10

100

1000

rank of node betweenness centrality of broken nodes

Figure 5: Average flow rate of node pairs in the same module

Figure 8: The number of node pairs of intra-communication decreasing flow rate when nodes other than inter-connecting nodes failAverage ﬂow rate of node pairs in thediﬀerent module

0.4
0.35
0.3

rate between before and after failures. As for intra-communication,

0.25

we show the results when nodes other than inter-connecting nodes

0.2

break in Figure 8. In this figure, X-axis shows the rank of node be-

0.15

tweenness centrality of failed nodes and Y-axis shows the number of

0.1

node pairs decreasing flow rate by failures. This represents that the

0.05

smaller values are better. We can see that the values can be kept low

0
CC

CP

PC

PP

for PC network, so it is revealed that PC network is the most reliable.

Connec#ng strategy

However, it is too simple to use PC strategy for constructing interFigure 6: Average flow rate of node pairs in the different moduleconnected networks. This is because, this results represent flow rate

Increasing rate of average hop lengthof node pairs in only network A. From a viewpoint of network B,
1.1

PC strategy equals to CP strategy. We can see that the values are

1.08

larger in CP network. When network A wants to use PC strategy,

1.06

does network B agree with such unfair connection? The answer is
No. Therefore, we pick up the results of CC and PP network and1.04
average

1.02

worst

1

show them in Figure 9. We can see that the values in CC network aremostly larger than the values in PP network. The discussion about
CP and PC strategy is also applied to intra-communication. There-

0.98
0.96
CC

CP

PC

PP

Connec!ng strategy

fore, in the following evaluation, we show the result in CC and PP
network. As for inter-communication, we show the results whennodes other than inter-connecting nodes break in Figure 10. The

Figure 7: Increasing rate of hop length after a single failure in average and worst casedefinition of X-axis and Y-axis are the same as Figure 9. We cansee that the values in CC network are larger than the values in PP
network. In other words, CC network is affected by failures moreat the same time. Figure 7 shows the changes of average hop lengththan PP network. For these results, when we compare CC and PP

of inter-communication after a single node failure. Here, the aver-

network, PP network is more reliable than CC network.

age hop length is calculated as an average of average hop length of
all patterns of a single node failure. In the figure, the average hop

4. Conclusion

length is normalized by an average hop length before the failure oc-

In this paper, we investigated characteristics of inter-connected

curs. Blue bar represents the average of average hop length of all

networks from both topological and traffic-flow perspectives. We

pattern of a single node failure. Red bar represents the worst casefirst discussed that eigenvalue centrality and location of nodes are

scenario, i.e., the average hop length is maximally increase. We canimportant for making inter-connected networks more reliable andsee that CC network receive the worst influence from failures com-efficient. Folllowing the discussion, nodes in the network werepared to other connecting strategy. In addition, PP network can keep

classified into Central nodes and Peripheral nodes based on their

the increasing rate low even in the worst case. Thus, it is revealed

eigenvector centrality of nodes. Then, we examined four connect-that PP network is not affected largely by failures.

ing strategies CC, CP, PC, and PP to construct inter-connected net-

Finally, we show the changes of flow rate after a node failure.

works with different inter-connected structure. We evaluated the

For all pattern of a single failure, we focus on fluctuation of flow

reliability and efficiency from the viewpoint of not only topolog—5—

The number of node pairs decreasing
flow rate

1.0E+05
9.0E+048.0E+04
7.0E+04CCPP

6.0E+04
5.0E+04
4.0E+04
3.0E+04
1

10

100

1000

rank of node betweenness centrality of broken nodes

Figure 9: The number of node pairs of intra-communication decreasing flow rate when nodes other than inter-connecting nodes fail(CC, PP)The number of node pairs decreasing
flow rate

2.0E+05
1.8E+05
1.6E+05
1.4E+05
1.2E+05
1.0E+05
CCPP

8.0E+04
6.0E+04
4.0E+04
2.0E+04
0.0E+00
1

10

100

1000

rank of node betweenness centrality of broken nodes

Figure 10: The number of node pairs of inter-communication decreasing flow rate when nodes other than inter-connecting nodes failical metrics but also traffic flow when failures occur. The results
showed that high reliability and efficiency are achieved by using
periphery nodes around core nodes as inter-connecting nodes. Our
future work is to consider the interdependency between two service
networks and investigate good connecting strategies for the interdependent networks.
References[1] R. Parshani, C. Rozenblat, D. Ietri, C. Ducruet, and S. Havlin, “Intersimilarity between coupled networks,” Europhysics Letters, vol. 92,
p. 68002, Jan. 2011.
[2] J. Gao, S. V. Buldyrev, H. E. Stanley, and S. Havlin, “Networks
formed from interdependent networks,” Nature Physics, vol. 8,
pp. 40–48, Dec. 2011.
[3] C. D. Brummitt, R. M. D’Souza, and E. A. Leicht, “Suppressing cascades of load in interdependent networks,” Proceedings of the National Academy of Sciences, vol. 109, pp. 681–689, Mar. 2012.
[4] J. Aguirre, D. Papo, and J. M. Buldú, “Successful strategies for competing networks,” Nature Physics, vol. 9, pp. 230–234, Feb. 2013.
[5] X. Ma, S. Kim, and K. Harfoush, “Towards realistic physical topology models for Internet backbone networks,” in Proceedings of 6thInternational Symposium on High-Capacity Optical Networks andEnabling Technologies, pp. 36–42, Dec. 2009.

—6—