JAIST Repository
https://dspace.jaist.ac.jp/Title

SFネットワーク構造がパケット輸送に与える影響についてAuthor(s)遠藤,友基; 林,幸雄

Citation

情報処理学会研究報告 : 数理モデル化と問題解決研
究報告, 2004(18): 15‑18

Issue Date

2004‑03

Type

Journal Article

Text version

publisher

URL

http://hdl.handle.net/10119/3413

Rights社団法人 情報処理学会, 遠藤友基／林幸雄, 情報処理学会研究報告 : 数理モデル化と問題解決研究報告,2004(18), 2004, 15‑18. ここに掲載した著作物の利用に関する注意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 The copyrightof this material is retained by the Information
Processing Society of Japan (IPSJ). This material
is published on this web site with the agreementof the author (s) and the IPSJ. Please becomplied with Copyright Law of Japan and the Codeof Ethics of the IPSJ if any users wish toreproduce, make derivative work, distribute or
make available to the public any part or whole
thereof. All Rights Reserved, Copyright (C)Information Processing Society of Japan.

Description

Japan Advanced Institute of Science and Technology

社団法人 情報処理学会 研究報告
IPSJ SIG Technical Report

2004−MPS−48

2004／3／1

SF ネットワーク構造がパケット輸送に与える影響について
遠藤友基†

林幸雄†

近年の研究により, インターネットのルーターネットワークにはスケールフリー性という構造的特徴があることが明らかになっている. コンピュータネットワークをモデルとしたパケット輸送のシミュレーションは数多く行われているが, 実際のインターネットの基本機能を実現し, かつスケールフリー性を考慮した大規模ネットワークでの試みは行われていない. 本研究では現実のトポロジ情報を用い,スケールフリー性がパケット輸送にどのような影響を与えるかをシミュレーションにより検証した. その結果, スケールフリー性がネットワークの渋滞現象に大きな影響を与えていることが明らかになった.

Dynamic properties of packet transportation in Scale-Free network models
Yuuki Endou† and Yukio Hayashi†
Recent studies in physics and computer science have shown that many complex networks
in nature and social relationships have a common structure called scale-free(SF) networks.
The topology with a power law degree distribution appears in router network on the Internet. Although many simulations of packet transpotation in many types of network model arestudied, both of the routing function on the Internet and the SF structure are not considered in large networks. We investigate the dynamic property of packet transportation in SF
network models whose topological structures are extracted from real data. Our results showthat ”betweenness centrality”, which was used in social networks, is very important factor for
packet transpotation and network congestion.てきている.

1. は じ め に本研究ではインターネットのルーター構造はべき乗計算機性能の劇的な向上と情報ネットワークの整備則に従うという Faloutsos2) たちの測定結果を踏まえ,が進むに従って, インターネットは必要不可欠な情報インターネットシミュレーションモデルを構築する.

インフラとして, その地位を確固たるものとしている.

そして大規模ネットワークでもシミュレーション可能

しかし, 流通されるデータ量やホスト数の増大によっなパケット通信を行うシミュレータを製作し, スケーて, トポロジの変化や輻輳といったより広域的なネッルフリーの特性をもつ実データのトポロジ情報をもとトワークの状況に応じた経路制御が求められている.にしたモデルにおいて, ネットワーク中のパケット分中でもネットワークの渋滞を引き起こす輻輳現象の解布の状態を分析する. この結果から, ネットワークのト明は重要な課題である. この問題はネットワークのトポロジがパケット輸送に大きな影響を与えていることポロジとダイナミックスという大きく 2 つの枠組みにを明らかにする.

分けて考えることができる. これまで, トポロジは格子モデルやランダムグラフなどが, ダイナミックスでは2. パケット通信シミュレータ

パケットの独立なポアソン到着による待ち行列解析が一般的だった. しかし近年の研究により, トポロジでパケットシミュレータは現在も様々なものが利用さはスケールフリー性という普遍的性質が, ダイナミッれている 3) . しかし大規模な場合において, 様々なトポクスでは従来の待ち行列理論では説明できない相互作ロジ情報を扱うには適していない. そのために独自でパ用的輻輳の相転移現象がみられることが指摘されておケット通信シミュレータを製作した. 本研究では, ルー

り 1) , こうした新たな知見に基づく研究が盛んになっター間の距離などのリンク情報も加味できる OSPF の† 北陸先端科学技術大学院大学 知識科学研究科
School of Knowledge Science, Japan Advanced Institute of Science and Technology

メカニズムをより一般化したものを用いた. 製作したシミュレータの概要は図 1 のようになっている. ホス
ト PC とルーターを表すノードはそれぞれにルーティ−15−(5)図 1 離散事象のパケット通信シミュレータの概要

図 2 ISP 間の接続地図 (出典：Internet Mapping Project5) )ングテーブルとクロックを持っており, マクロなシス

ケールフリー性に注目している. そこで今回対象に選テム時計を参照しながらパケット送受信の動作を決めんだネットワークモデルは入手可能な実データの中で,ている. また送信されるパケットは送信先, 送信元, 発スケールフリーの構造的特徴を持つ電力網 9) と AS10)

送時間, パケット生存時間の情報を保持し, 送受信間でのネットワークデータである. 表 1 にネットワークモ

パケット消滅における TCP の再送機能も実現できるデルの各種データを, 表 2 にシミュレータの各種設定ようになっている.

パラメータを示す.

3. スケールフリーネットワークについて

表１. 計算ネットワークの各種データ
参照データ
総辺数
全ノード数
合計次数
平均次数
平均経路長
assortativity
次数分布べき指数
平均結合相関べき指数

Faloutsos たちの実測により, インターネットにおけるノード間の接続関係はべき乗則に従うということが分かっている 2) . このべき乗則はノードをルーターとみなしたトポロジだけでなく, AS(Autonomous Sys-tem) をノードとみなしたとき（以下, 図 2 参照）や電力網
6594
4941
13188
2.6691018.98919
0.01128
3.95353
0.04236

AS125726474
25144
3.88384
3.70500-0.05714
2.496140.51906

WWW(World Wide Web) の接続関係に対しても同様の性質が成り立っている 4) . こうしたべき乗則のネッ

表２. シミュレータの各種パラメータ（単位はシステム時間）

トワークは観察するスケールを変えても同じ構造が現

ルーター処理時間
再送要求発生間隔
Queue の上限
ダメージノードからの回復する規定長平均伝送率
リンクコスト
確認メッセージ伝送時間
リクエスト上限
パケット生存時間
終了時間
平均要求パケット数
平均リクエスト発生間隔れることから, スケールフリーネットワークと呼ばれており, 理論解析やシミュレーションによる実験が盛んに行われている.
一方, パケット輸送に関して, SF ネットワーク構造に着目したモデルの研究は近年特に活発になっている.

Tadić らはノード数 N = 1000 のサイズのネットワー
クを使い, パケットの伝送時間や拡散速度の分布にはべき乗則に従う性質があることを示した 6) . また, これらの性質がネットワークサイズにも依存しないことも

0.001
1050400.005
全て 10.005
100
10100020（ポアソン乱数）
1.0, 0.5,0.1, 0.05（ポアソン過程）

5. 輻輳現象とトポロジの影響示している 7) . だが, 彼らの関心はトポロジの性質に特化しているところがあり, インターネットの基本的な本節ではトポロジの性質によって, ネットワークのパケット伝送機能は満たしていない. また, Kim らは輻輳状態が大きく異なってくることについて述べる.
まずは図 3 に, 平均リクエスト間隔の異なる状況で各ノードを通過するパケットのフロー量に着目し, これがべき乗分布に従うことを示している 8) .の総 Queue 長の時間変化を示す. ここに示す総 Queue長とは, ネットワーク中のすべてのノードに入ってい4. シミュレーションモデル

る Queue の総和のことである. 平均リクエスト間隔を本研究では現実のネットワークトポロジ特性, 特にス小さくしていくと, 総 Queue 長が大きくなり, ネット−16−図 4 総 Queue 長とリンク総量の時間平均(a) 平均リクエスト間隔 0.5（非輻輳時）(b) 平均リクエスト間隔 0.05（輻輳時）
図 3 総 Queue 長の時間変化

図 5 active なノードとリンクの時間平均ワークが輻輳してくる現象が図 3 から分かる.

が分かる. これは電力網のトポロジがパケットの負荷を

図 4 は平均リクエスト間隔と変化させたとき, ネッ広く分散させていることを示しているのに対し, AS のトワーク中における総 Queue 長とリンクに流れていトポロジは限られたノードやリンクが集中して使われたパケット総量の時間平均はどのように変わっていくていることを表している. これらの結果と表 1 のデータかを示したグラフである. 電力網, AS のトポロジともと照らし合わせると, 電力網のトポロジに対して, ASノードに溜まる総 Queue 長はほぼ同様の変化を見せのトポロジは平均経路長が短いために総 Queue 長やるのに比べ, リンクを流れるのパケット総量は電力網リンクのパケット総量が小さくなり，平均結合相関ののトポロジほうが AS のトポロジに比べて大きくなっべきの傾きが大きことからホスト間の結合がより強くていることが分かる. 特に平均リクエスト間隔が 0.05なるため, 負荷が集中するものと考えられる.の輻輳時では, 電力網で, 全ノードの総 Queue 長：リンクの総パケット数がほぼ 2:1 なのに対し,AS は 7:1とノードの負担が大きくなっている.

6. Betweenness との関係
社会的ネットワークで研究されてきた”betweenness

これを稼動しているノード, リンクの数で示したのcenterality（以下, betweenness）”という指標がパケッが図 5 である. これを見ると, 相対的に電力網のトポロト輸送の問題でも重要となる 8) . betweenness とは各ジが AS のトポロジに比べて大きく推移していることノード間の最短パスを考えたとき, あるノードを経由−17−

図 6 betweenness と平均 Queue 長との関係（電力網）

図 7 betweenness と平均 Queue 長との関係（AS）する割合を数値化したものである. 我々のシミュレー

ワークモデルを用い, より詳細な定量的性質を検討しションにおいても, そうした betweenness がパケットていく必要がある.

輸送に大きな影響を与えることが分かった.
図 6 と図 7 は各ノードの平均 Queue 長が between-ness とどのように関係してくるかを示したものである. 本来の betweenness は各ノード間において定義されるものだが, ここではホスト間の通信に限定して算出している. この状況でも, betweenness の値が高いノードほど平均 Queue 長が長くなることが分かり, それはべき乗の傾きをもっている. このとき, どちらの結果も betweenness の値を b とすると, bγ（γ = 1.55）に比例する直線にのる. この結果からもパケット輸送を考える上で, 各ノードの betweenness が大きなノードほど, 通信では重要なコネクタの役割を果たしていると考えられる.

7. 結 び に本論文で得られた結果を以下にまとめる.

• ネットワークのつながり方を示す平均経路長や平均結合相関は, 前者の値が大きいほど総 Queue 長やリンクのパケット総量が大きくなり, 後者の値が大きいほどノードとリンクに負荷が集中する傾向にある（表 1, 図 4, 図 5）.

• 単一ノードで見たときに betweenness はパケット輸送に大きく関係してくる量であり, betweennessが高いノードほど平均 Queue 長が長くなり, それはべき乗の傾きをもつ（図 6, 図 7）.

betweenness はネットワークのトポロジによって大きく変わってくる. 従って, この betweenness が高いノードの分布状態が, 渋滞現象において重要なファクターになることが予想される. 今後は種々のネット−18−

参 考 文 献1) 高安美佐子, インターネットの交通流にみられる自己組織化,” 数理科学, 1 月号, 1999.
2) M.Faloutsos, P.Faloutsos, C.Faloutsos, ”On
Power-Law Relationships of the InternetTopology,” ACM SIGCOMM, 29(4), 251-262,1999.
3) http://www.cs.bu.edu/BRITE/
4) A.L.Barabási, 青木薫 訳, 「新ネットワーク思考」, NHK 出版 , 2002.
5) G.Caldarelli, R.Marchetti, L.Pietronero, ”The
fractal properties of Internet,” Europhysics
Letters, 52, 386-391, 2000.
6) B.Tadić, S.Thurner, G.J.Rodgers, ”Trafiic
on complex networks: Toward understanding global statistical properties from microscopic density fluctuations,” arxiv;condmat/0401094, 2004.
7) B.Tadić, S.Thurner, ”Infomation Super-Diffusion
on Structured Networks,” arxiv;cond-mat/0307670,
2003.
8) K.I.Goh, B.Kahng, D.Kim, ”Universal Behavior of Load Distribution in Scale-Free Networks, ” Phys. Rev. Lett. 87(27), 278701, 2001.
9) D.J.Watts, S.H.Strogatz, ”Collective dyanamics of small-world networks,” Nature, 393, 440,
1998.
10) Adilson E.Motter, Ying-Cheng Lai, ”Cascadebased attacks on complex networks,” Phys.
Rev. E 66, 065102, 2002.