[チュートリアル招待講演] 通信ネットワークの トポロジー - 村田研究室

社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
[チュートリアル招待講演] 通信ネットワークの
トポロジー構成のモデル化と性能評価への応用
荒川 伸一†
滝根 哲哉††
村田
正幸†
† 大阪大学 大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
†† 大阪大学 大学院工学研究科
E-mail: †{arakawa,[email protected], [email protected]
あらまし
経路制御や輻輳制御など、ネットワーク制御手法の評価には通信ネットワークの適切なモデル化が必要で
ある。インターネットトポロジーを観測した結果、ノードの次数分布がべき則に従うことが明らかになっているが、
次数分布がべき則のみが通信ネットワークの特性を決定するわけではない。本講演では、通信ネットワーク、特に ISP
内のルーターレベルトポロジーに着目し、その構造分析とモデル化に関する研究を紹介する。ルーターレベルトポロ
ジーと生物学や社会学の研究でしばしば用いられるスケールフリーネットワークを対比することで、通信ネットワー
クの構造的特徴を明らかにする。さらに、国内 ISP ネットワークを対象とした物理回線容量の計測結果をもとに、ルー
ターレベルトポロジーにおける回線容量分布の特性を説明し、その発生要因とモデル化手法を示す。
キーワード べき則、ルーターレベルトポロジー、BA モデル、回線容量、Zipf 則、フロー制御
[Tutorial Invited Lecture] Analyzing and Modeling Router-level Networks
and Its Application to Performance Evaluation
Shin’ichi ARAKAWA† , Tetuya TAKINE†† , and Masayuki MURATA†
† Graduate School of Information Science and Technology, Osaka University
1–5 Yamadaoka, Suita, Osaka 565–0871, Japan
†† Graduate School of Engineering, Osaka University, Osaka, Japan
E-mail: †{arakawa,[email protected], [email protected]
Abstract Modeling communication networks is vital for network researches. Recent measurement studies on the Internet
topology show that the degree distribution obeys the power-law distribution. However, only the degree distribution does not
determine the performance of network control methods. As previous studies have shown, one of important factors to characterize the performance of network control methods is a structure of topologies. However, other characteristics, which are even
more important, are link capacity because these characteristics are particular to communication networks. In this tutorial, we
introduce several research works that investigate and reveal the topological structure of router-level topologies, and then show
the structural dissimilarity between router-level topologies and well-known scale-free network. We further introduce the link
capacity characteristics of router-level topologies by using our own measurement data of ISP networks in Japan.
Key words Power-Law Networks, Router-level topology, BA model, Link Capacity, Zipf Law, Flow control
—1—
Advanced Network Architecture Research Lab.
Osaka University
4
はじめに
ASレベルのトポロジーの特徴
• 情報ネットワークのモデル化は何故必要か?
• 1999年のASマップ: 3037ノード
• AT&T, Sprint等の様々なISP間の接続
関係
• 科学的な興味
• 制御⼿法の性能評価
• 例: (何らかの)経路制御⼿法を提案 → 評価で⽤いるトポロジーは?
• 次数分布にべき則の性質が観察されて
⋅
いる: 次数が である確率が
• 既存の⽂献で扱われているトポロジーを使う(これは論⽂を書く上で必須)
• しかし、今のインターネットで効果を発揮するかはわからない
•
• 実網のデータを取得できる⽴場にある場合でも、ネットワーク規模拡⼤(ノード追加
、リンク追加)や回線容量増強時の検証が必要
• BA モデル
• 1. ノードを段階的に追加
• 2. 追加時に既存トポロジーの次数が⼤
きいノードに優先的に接続
• Non-linear attachment:
• 経路制御→トポロジー (AS-level or router-level)
• 輻輳制御→トポロジー+回線容量
•
7
ルーターレベルトポロジーの次数分布
/∑
T. Bu and D. Towsley, “On distinguishing between
Internet power law topology generators,” in
Proceedings of INFOCOM, pp. 1587–1596, June
2002.
BAモデルで⽣成したトポロジー: 1000ノード, 平
均次数2。縦軸は累積補分布
Advanced Network Architecture Research Lab.
Osaka University
8
国内ISPトポロジーの次数分布
• ASの1ノードが1 ISPに相当
• ISP内トポロジーの計測:[Sprint2004]
• AT&T 社: 523ノード, 1304リンク
• Sprint 社: 467ノード, 1292リンク
AT&Tトポロジ
http://research.lumeta.com/ches/map/gallery/index.html
• スケールフリーネットワーク:
• もちろん、研究対象によって必要とするモデル化の
粒度は異なる
Advanced Network Architecture Research Lab.
[Faloutsos99] M. Faloutsos, P. Faloutsos, and C.
Faloutsos, “On power-law relationships of the Internet
topology,” in Proceedings of SIGCOMM ʼ99, vol. 29, pp.
251–262, Oct. 1999.
• AS-levelトポロジーのモデル化
情報ネットワークの特徴抽出、ネットワーク成⻑を含む
トポロジー構成のモデル化が重要
Osaka University
5
Advanced Network Architecture Research Lab.
Osaka University
•
Tracerouteによる国内ISPトポロジーの計測
•
国内ISPにおいても次数分布にべき則が観察される
•
•
•
2006年6⽉~2006年12⽉
⼤阪⼤学を含む国内2拠点で調査
ISP A, ISP B, ISP Cの3つのISPのルーターレベルトポロジーを分析
国内ISP B
Sprintトポロジ
次数 の出現確率
⻘森
[Sprint2004] N. Sprint, R. Mahajan, D. Wetherall, and T.
Anderson, “Measuring ISP topologies with rocketfuel,”
IEEE/ACM Transactions on Networking, vol. 12, pp. 2–16,
Feb. 2004.
Osaka University
AT&Tトポロジの可視化
注) 州の粒度でのノード位置情報にもとづ
き、⼿でばらしている
Advanced Network Architecture Research Lab.
ノード次数
9
東京
Advanced Network Architecture Research Lab.
Osaka University
ルーターレベルトポロジーのモデル化
ISPトポロジーの構造的特徴:ルータ処理能⼒の制約 [Li04]
• 構造的特徴およびモデル化
• ルータのバックプレーンの処理制約
[Li04] L. Li, D. Alderson, W. Willinger, and J. Doyle, “A first–principles approach to
understanding the Internetʼs router–level topology,” in Proceedings of SIGCOMM, Aug. 2004.
• 次数分布がべき則となる複数のトポロジーを列挙
• リンク両端の2ノードの次数相関がスループット性能を決定付ける
• ルーターレベルトポロジーはスループット性能が⾼い
• 次数の⼤きいノードはアクセス回線収容に⽤いられる
• 次数の⼩さいノードはコアノードの⼤容量回線収容に⽤いられる
• ⼯学的な最適化がなされている:確率的なトポロジー⽣成⼿法の問題点を指摘
• D. Alderson and W. Willinger: “A contrasting look at self-organization in the Internet and
next-generation communication networks,” IEEE Communication Magazine, July 2005.
• Cisco 12416 ルータの場合
• バックプレーン処理能⼒:160Gbps
• 次数<= 16
• 1本のリンクの回線容量:10Gbps
• 次数 = 128
• 1本のリンクの回線容量:100 Mbps
• 次数が⼤→接続できるリンクの回線容量に制限
• 次数が⼩→⼤容量回線を接続
• ルーターレベルトポロジーの特徴
•
•
∑
, ∈
/
• 次数の⼤きいノードと次数の⼤きいノードがどの
程度連結されているか
• Assortative mixing: M. Newman, "Assortative
mixing in networks" Physical Review Letters,
2002.
Bandwidth per link (Gbps)
•
10
100
10
1
0.1
1
10
100
number of links
1000
Advanced Network Architecture Research Lab.
Osaka University
11
収容トラヒック量の⽐較
Osaka University
Advanced Network Architecture Research Lab.
12
ルーターレベルトポロジーの分析、⽣成⼿法 (1/3)
• 隣接する2ノードの次数相関がルーターレベルトポロジーの特
徴 [Li04]
• スループット性能が⾼くなるよう設計されている
↑ERトポロジ
• 3ノード間の次数相関がルーターレベルトポロジーの性質を決
定する [Machadevan2006]
↑BAトポロジ
• [Machadevan2006] P. Machadevan, D. Krioukov, K. Fall, and A. Vahdat, “Systematic
topology analysis and generation using degree correlation,” in Proceedings of SIGCOMM
2006, Aug. 2006.
• 平均クラスタ係数や最⼤固有値、平均ホップ⻑の類似性を議論
↑Sprintトポロジ
↑AT&Tトポロジ
Advanced Network Architecture Research Lab.
Osaka University
13
Osaka University
Advanced Network Architecture Research Lab.
ルーターレベルトポロジーの分析、⽣成⼿法 (2/3)
ルーターレベルトポロジーの分析、⽣成⼿法 (3/3)
• 元のトポロジとの類似度を表す指標
• d3-graph⽣成法
•
•
•
•
クラスd0:
クラスd1:
クラスd2:
クラスd3:
平均次数が等しい
次数分布が等しい
次数kのノードと次数kʼのノードの2ノードが連結される確率が等しい
次数k, kʼ, kʼʼのノード間の接続確率が元のグラフと等しい
14
• Step.1: d1-pseudo graphを⽣成 (下図の×を求める)
• Step.2: d2 targeted d1-preserved rewiring(⾚い曲線)
• Step.3: d3 targeted d2-preserved rewiring(⽔⾊の曲線) △を⽣成
• → Original Graph(△)の情報が必要。
• d3-randomizing
• オリジナルグラフを与え、d3の領域内(d3の性質を満たす状況)でのみ
rewiringする(⻩緑)
Osaka University
Advanced Network Architecture Research Lab.
15
Osaka University
dk-reserved rewiring
[Machadevan2006]の課題
• d2 reserved rewiring
• dK-randomizingの適⽤範
囲は広い
• 理論上は、クラスdNまで考
えることが可能
• d3 reserved rewiring
• ただし、現実的には クラスD3まで
。クラスD4以上 だと計算量がおい
つかない
Advanced Network Architecture Research Lab.
16
D3 reserved
Sprintトポロジでは
3ノード間の次数の関係
が故障耐性を決定づける
• D3で測れないルーターレベ
ルトポロジーの特性もある
• 例えば、故障耐性
• 故障耐性の特性決定付ける指標と
して局所連結性(モジュール性)
が挙げられる[Arakawa2010]
[Arakawa2010] S. Arakawa, T. Takine, M.
Murata, “A failure-tolerant structure in Routerlevel Internet topologies,” NS研究会 (2010/07)
AT&Tトポロジでは
3ノード間の次数の関係
のみでは故障耐性は定
まらない
Osaka University
Advanced Network Architecture Research Lab.
17
Modularity-reserved rewiring
ルーターレベルトポロジーの階層構造
• Modularity-reserved rewiring
• 階層構造のイメージ図
• 地域をモジュールと⾒⽴て、地域間のconnectivityが確保されている時
に、リンクをrewiring
• Modularity-reserved + d2-randomizationにより、故障耐性が保持さ
れる
19
Advanced Network Architecture Research Lab.
Osaka University
• ノードiのFunctionalityとしてHi, Ziを導⼊
: ノードiの次数
:ノードiから他ノード
へのホップ距離の和
・ISP: Provincial Hubの存在
・AT&T: Non-hub coreが存在
Provincial Hub
HubCore
Leaf (non-hub)
Non-hub core
S. Arakawa, T. Takine, M. Murata, “A failure-tolerant structure in
Router-level Internet topologies,” NS研究会 (2010/07)
Osaka University
Advanced Network Architecture Research Lab.
20
Advanced Network Architecture Research Lab.21
Osaka University
トポロジーの局所連結性
トポロジーの局所連結性(モジュール性)
•
ISP1〜ISP8: tracerouteによって観測されたISPトポロジ
•
•
Model1~4: 既存のモデル化⼿法により⽣成したトポロジ (Sprint社と同⼀ノード数、リンク数)
•
INET: 1997年11⽉のASトポロジ, トポロジ⽣成ツールINETで使⽤
ノードの役割を分類 [Guimera2005]
•
ネットワークをいくつかのモジュールに分割
•
Participation coefficient, P [0 ≤ P ≤ 1]
• ノードが、他のモジュールのノードと連結している割合
•
Within-module degree, W
• ⾃⾝が属するモジュールのノード次数分布における、ノードの次数(接続
リンク数)の偏差
Pi = 0
•
Pj = 1
2.58 (0.5%) を超えるとハブノード、それ以外は⾮ハブノード
BA
[Guimera2005] R. Guimera and L. A. N. Amaral,
“Functional cartography of complex metabolic networks,”
Nature, vol. 433, p. 895, 2005.
AT&T
Module 2
・・・
Module 1
・・・
Osaka University
Advanced Network Architecture Research Lab.
22
Connector hub
Osaka University
収容トラヒック量の⽐較(再)
↑ERトポロジ
↑BAトポロジ
Z=2.0, P =0.56(90-130Gbps)
回線容量のモデル化
Provincial
(40-50Gbps)
↑Sprintトポロジ
↑AT&Tトポロジ
23
Advanced Network Architecture Research Lab.
Osaka University
24
Advanced Network Architecture Research Lab.
Osaka University
情報ネットワーク特有の性質:回線容量
回線容量の計測結果(国内ISPネットワーク)
• IIJ社の基幹ルータのノード処理能
⼒分布[9] (21ノード,34×2リン
ク)
•
• 2003年の公開データから計算
• 傾き-2.6
国内ISPネットワーク (ISP A, ISP B)の回線容量を測定
•
観測期間: 2006年6⽉~2006年12⽉
•
3.8GHz PentiumIVのCPUタイマを使⽤
•
使⽤した計測ツール
• Traceroute (トポロジ観測)
• Pchar (回線容量測定)
•
⼤阪⼤学、国内ISP Dから計測
ISP A
Link capacity (Mbps)
• 回線容量分布を算出
• 上位40位程度まで、傾き-1.1のべき則
ISP B
100000
100000
10000
10000
y = 91598x‐1.031
1000
1000
100
100
10
10
1
1
1
10
100
1000
y = 83766x‐1.298
傾き-1
1
10000
10
Rank
100
1000 10000
Rank
25
[9] 丸⽥⼀, “べき指数を⽤いたインターネットバックボーンのネットワーク構造分析,” GLOCOM Review, vol. 8, no. 4, 2003.
Advanced Network Architecture Research Lab.
Osaka University
26
Advanced Network Architecture Research Lab.
Osaka University
27
回線容量分布がZipf則に従う理由
トポロジの構造と回線容量割当
• 単純に考えると、以下のルールでも回線
容量分布はZipfとなる
• フロー制御がもたらすダイナミクスを無視する場合、リンクを
経由するフロー数に応じた回線容量割当が最適
• 10Gbpsのuplink, 2.4G×4のdownlink
• 例えば、Betweenness Centrality (あるノード、またはリンクを経由する最短
経路数)に基づくノード性能・回線容量割当が有効 [Zhang09]
• ¼を4本、1/16を16本・・・とすればよい
• このようなシンプルなルールでもそれな
りに辻褄は合う(右下図)
フロー制御が働く環境下での回線容量増強
回線容量最⼤値 40Gbps×4本
“容量半分→本数を倍”のルールにより
⽣成した分布
2. 送信レート上昇
• ただし、分布に基づいて回線容量を割り
振る問題は残される
• 回線容量増強を考慮することができない
1. ボトルネックの
回線容量を増強
Destination
Source
3. 別リンクが新たにボトルネック
ノード次数vs. ノード容量:回線容量分布を与え、
edge betweeness centralityのランクと1対1に対応
Advanced Network Architecture Research Lab.
Osaka University
28
増強による回線容量分布の変化
回線容量均⼀な状態を初期状態とする
•
シミュレーションによりボトルネックリンクを探
し回線容量を増強
•
•
ボトルネックリンク:シミュレーション時にパケッ
ト棄却率が最⼤のリンク
•
使⽤するフロー制御は TCP
• ⽅針:
• 各リンクに重み
を定め、重みの⾼いリンクから順に増強
• 増強したリンクの重みを減少させ、周辺のリンクに重みを分配
• トポロジを階層化し下層と上層をつなぐリンクに優先的に重みを加算
• モジュール間リンクを持つノードとの距離に基づき階層を定義
• 他モジュールとの通信を担う上層のリンクが増強されるとモジュール内下層のノード
と他モジュール間のトラヒック量が増⼤すると想定
さらにシミュレーションを⾏いボトルネックを増
強(以降繰り返し)
1. 回線容量を増強
Rank
回線容量分布: 増強回数 100, 250, 450, 600回
⼀定量の増強
回線増強を繰り返していくと、回
線容量分布の傾きが‐1.0に近づく
2, 3. トラ
ヒック増⼤を
考慮し重みを
加算
ただし、⻑期間のシミュレーションが必要
Rank
AT&Tトポロジ(1331回増強、倍増)傾き-1
29
• 初期値を経由フロー数とする
Link Capacity
•
Advanced Network Architecture Research Lab.
Osaka University
回線容量割当⼿法 (1/2)
AT&Tトポロジ
回線増強を繰り返していくと、回線容
量分布の傾きが増⼤する傾向
Link Capacity
•
[Zhang09] G. Q. Zhang, S. Zhou, D. Wang, G. Yan, and G. Q. Zhang, “Enhancing network transmission
capacity by efficiently allocating node capability,” arXiv:0910.2285, Oct. 2009.
回線容量割当⼿法
増強による送受信トラヒック量の増⼤
Advanced Network Architecture Research Lab.
Osaka University
30
Osaka University
Advanced Network Architecture Research Lab.
回線容量割当⼿法 (2/2)
まとめ
• 増強⼿順:
• 通信ネットワークの接続関係のモデル化
1. 重み最⼤のリンクを増強し重みを
減少させる
2. 増強したリンクの両端と同じもしくは1階層下のノードと接続するリン
クに重みを分配
• 重みは
/ ずつ均等に分配( は対象となるリンク数)
1
/
• ルーターレベルトポロジーの構造的特徴
• 回線容量のモデル化
ずつ均等に分配( は対象となるリンク数)
回線容量割当結果
• スケールフリーネットワーク、BAモデル
• ルーター処理能⼒制約を考慮したモデル
• 次数相関
• 局所連結性(モジュール性)、階層性、冗⻑性
3. 重みが加算されたリンクからさらに1階層下のリンクに重みを分配
• 重みは
• 情報ネットワーク特有の性質である回線容量
• 回線容量におけるZipf則:公開データ、計測データ、計算機シミュレーションデ
ータのそれぞれで観察
• 回線容量割当⼿法ならびに性能評価への適⽤例
総回線容量とスループット
100,000セッションの
平均スループット (Kbps)
Link Capacity
Rank
Osaka University
31
回線容量の総和(初期状態を1)
Advanced Network Architecture Research Lab.
32
Osaka University
関連⽂献
関連⽂献
• Motif (Graph Mining)
•
Advanced Network Architecture Research Lab.
33
スケールフリーネットワーク上でのトラヒックダイナミクス
• SubGraphの出現頻度 (P.20)
•
• R. Milo et al., “Network motif: Simple Building Blocks of Complex Networks,”
Science Vol. 298, pp.824-827, 2002.
M. Woolf, D. Arrowsmith, R. Mondragon, J. Pitts, and S. Zhou, “Dynamical modelling of TCP
packet traffic on scale-free networks,” Institut Mittag-Leffler, vol.6, p.7, Oct. 2004.
•
• J.-P. Onnela, et al., ”Intensity and coherence of motifs in weighted complex
networks”, Physical Review E, 71, 065103(R) (2005).
W.-X. Wang, B.–H. Wang, C.–Y. Yin, Y.–B. Xie, and T. Zhou, “Traffic dynamics based on local
routing protocol on a scale-free network,” Physical Review E, vol. 73, p.026111, Feb. 2006.
•
C. Liu, Q. Zhang, Z. Zhang, “Emergence and disappearance of traffic congestion in weightevolving networks,” Simulation Modelling Practice and Theory, Vol. 17, pp. 1566–1574, Nov.
2009.
•
T. Hirayama, S. Arakawa, K. Arai, and M. Murata, “Effect of modularity structure on traffic
dynamics,” in Technical Committee on New Generation Network (NwGN2010-39), pp. 15–20,
Jan. 2011.
• Assortative mixing, or degree-degree correlation.
• 次数の⼤きいノードと次数の⼤きいノードがどの程度連結されているか?
• M. Newman, "Assortative mixing in networks" Physical Review Letters, 2002.
• Modularity
• モジュール分割の⼿法(P.21)
• M. Newman, “Modularity and community structure in networks,” PNAS, vol. 103,
pp. 8577–8582, Apr. 2006.
• *-centrality
• 様々な指標が検討されている (列挙しきれない。例えばP.27のbetweenness centrality)
• Luciano da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso, P. R. Villas Boas.
Characterization of complex networks: A survey of measurements. Advances in Physics,
Volume 56, pages 167 – 242, Issue 1 (2007)
•
“ネットワーク設計”を扱った⽂献(主に物理学の研究分野)
•
Y. Xia and D. Hill, “Optimal capacity distribution on complex networks,”Europhysics Letters,
vol. 89, p. 58004, Mar. 2010.
•
X. Ling, M.-B. Hu, W.-B. Du, R. Jiang, Y.-H. Wu, and Q.-S. Wu, “Bandwidth allocation strategy
for traffic systems of scale-free network,” Physics Letters A, pp. 4825–4830, Nov. 2010.
•
G.-Q. Zhang, S. Zhou, D. Wang, G. Yan, and G.-Q. Zhang, “Enhancing network transmission
capacity by efficiently allocating node capability,” Physica A, vol. 390, pp. 387–391, Jan.
2011.