様式 C-19
科学研究費補助金研究成果報告書
平成
21 年
6月
9 日現在
研究種目:若手研究(B)
研究期間:
2007~2008
課題番号: 19700076
研究課題名(和文) インターネット上の組織の相対的なトラフィック量推定に関する研究
研究課題名(英文)
Modeling of Traffic Demand of Node in Large-scale Network
研究代表者
福田健介(FUKUDA KENSUKE)
国立情報学研究所・アーキテクチャ科学研究系・准教授
研究者番号:90435503
研究成果の概要:
本研究課題では,インターネット上のノード(組織や個人)の生成するトラフィック量が
どのような分布で特徴付けられるかを,複数のインターネットトラフィックデータから解
析した.その結果,ノードのトラフィックは既存の指数分布モデルとは異なり,裾の広い
対数正規分布でモデル化する必要があることが明らかになった.また,
そのような分布が,
トラフィック量の指数的増加により説明可能であることを明らかにした.
交付額
(金額単位:円)
2007 年度
2008 年度
年度
年度
年度
総 計
直接経費
2,000,000
1,200,000
3,200,000
間接経費
0
360,000
合
計
2,000,000
1,560,000
360,000
3,560,000
研究分野:総合領域
科研費の分科・細目:情報学 計算機システム・ネットワーク
キーワード:情報ネットワーク,インターネットトラフィック
1.
研究開始当初の背景
負荷分散,輻輳制御,P2P,経路制御等の,
インターネット上で使用される各種プロト
コルの性能を大規模ネットワークで評価を
行うためには,一般にトポロジやネットワー
クの負荷を何かしらのモデルを仮定するこ
とが一般的である.しかしながらインターネ
ットはネットワークのネットワークと呼ば
れることからもわかるように,その瞬間瞬間
のトポロジや負荷のスナップショットを取
ることが原理的に不可能である.近年,ネッ
トワークトポロジの研究において,インター
ネットトポロジは,従来仮定されてきたラン
ダムグラフよりも,多様性・頑強性の高いス
ケールフリーネットワークやスモールワー
ルドネットワークとして特徴付けられるこ
とがわかってきた.これらのモデルの示唆す
る点としては,ネットワークトポロジの統計
性の違いが上位サービスの性能に大きな影
響を及ぼすことが挙げられる.しかしながら
ネットワークトポロジの統計的性質が明ら
かになったとしても,ネットワークトポロジ
上のノードにおいて,各ノードが送受信する
トラフィック量に関する知見がなければ,各
種シミュレーションにおいて,正しいシミュ
レーション結果が得られるとは言い難い.例
えば下図のようなネットワークトポロジを
考えてみると,各ノードのトラフィックがほ
ぼ一様(もしくは指数的)であるか,大きな偏
りがあるかを知ることが直感的にも理解で
きる.
netflow にて収集).データ収集期間は,2004
年,2005 年,2006 年,2007 年のそれぞれ 1
週間である.
(3) 国内設置の/18 サイズのダークネットへ
到着したトラフィック(tcpdump にて収集).
ダークネットは経路広報されているものの
実際にはホストの存在していないネットワ
ークであり,到着するパケットは全て異常な
ものである.
4.研究成果
(1) ノードレベルトラフィックの解析
2.
研究の目的
本研究では,背景で述べた,「ネットワーク
トポロジ中の各ノードのトラフィック需給」
について着目した.すなわち,(1) ネットワ
ーク上のノードが果たして,均一なトラフィ
ック需給を持つのか,もし偏りがあるとすれ
ば,それは,正規分布のような裾の短い分布
となるのか,もしくは,さらに裾の広い分布
として特徴付けられるのかを明らかにする
ことである.(2) 同様に,ノードごとのトラ
フィック需給の分布が明らかになった場合
に,その時間発展を予測可能な単純な物理モ
デルを明らかにすることを目的とする.
3.
図 1 は SINET の組織レベルでのトラフィック
量を累積グラフで表現したものであり,この
グラフは各ノードの入出力トラフィックが
どのような偏りを持つかを表している.注目
すべき点は水平軸方向が対数スケールにな
っていることである(なおトラフィック量は
規格化してある).すなわち,ノードレベル
トラフィックは,非常に幅の広い分布となっ
ており,既存の一様モデルや指数モデルとは
大きく異なっている.このような幅の広い分
布はいくつか知られているが,本研究では,
ベキ分布,ならびに対数正規分布によるフィ
ッティングを行った.図を見ればわかるよう
に,トラフィック量は,ネットワークトポロ
ジの統計的性質として現れるベキ分布より
も,対数正規分布によるフィッティングの方
が当てはまりが良い.つまり,トラフィック
の場合,大多数のノードが少量のトラフィッ
クで特徴付けられ,少数のノードが多量のト
ラフィックで特徴付けられるモデルとは異
なることを意味している.
研究の方法
インターネット上のネットワークトポロジ
を考える際には,複数のレベルの抽象化が考
えられる.一つは広域経路制御の単位である
AS レベル,もう一つは AS 内のノードレベル
である.本課題では,主として AS 内のノー
ドレベルトラフィック分布を同定するため
に,3 種類のトラフィックデータを収集・解
析した.
(1) 学術情報ネットワーク(SINET)の加入機
関単位(大学,短大,高専,研究機関等)の年
間トラフィック量(SNMP にて収集)
(2) 国内 ISP 1 社の加入者(ユーザ)ごとの 1
日当たりの使用トラフィック量(sampled
次に ISP で得られた各加入者単位でのトラ
フィック使用量をプロットしたものを図 2 に
示す.この図より加入者単位のトラフィック
分布もまた,上り下り共に裾の広い対称的な
分布となることがわかる.しかしながら図を
見ると,
2005 年のデータには 2 つの山があり,
2008 年のデータではその山の差があまりは
っきりしなくなっていることが読み取れる.
つまり,2005 年のユーザのトラフィック分布
は,2 つのタイプのユーザから構成されてい
ると言える.前者のピークは従来のサーバ・
クライアント型のサービス(web, mail 等)を
主として利用していることから,既存の大多
数のユーザはこのタイプ(CS タイプ)に分類
される.それに対して後者のピークは主とし
て P2P サービスを利用している少数のユーザ
に相当する(P2P タイプ).P2P タイプのユー
ザはユーザ数で見るとたかだか 4-5%にすぎ
ないが,水平軸が対数表示であることからも
わかるように,使用トラフィック量の約 75%
に対応するとの結果を得ている.同様に,
2005 年および 2008 年の二つの図を比較して
みると CS タイプのピークは右方向にシフト
しているものの分布の形自体には変化がな
いことが読み取れる.これは,トラフィック
の成長モデルが時間発展に対して,同一の関
数形で表現可能であることを意味している.
それに対して,P2P タイプのピークは 2008 年
ではピークが顕著ではなくなっている.これ
は,ユーザ数の減少というよりは,CS タイプ
の裾が右方向にシフトしているため,ピーク
がわかりにくくなっているものと考えられ
る.また,図中の右側に相当する大量のトラ
フィックには,アクセスリンクによるボトル
ネックが存在する.そのため現状の技術では,
これ以上大量のトラフィックをユーザが生
成することは原理的にないため,将来の観測
では,この分布にある種の歪みが生じること
になると予想できる.実際,P2P タイプの最
頻値はほとんど変化がない.
併せてダークネットに到着したパケット
の送信元アドレスに基づいて AS レベルで集
約したパケット数の分布を調査した.その結
果,分布は,裾の長い分布となるものの,そ
の関数形は対数正規分布よりもベキ分布に
近いとの結果が得られた.これは,ウィルス
等に感染しているホスト数が,AS 内のホスト
数に比例していると考えれば,AS 内のホスト
数に関係した指数となると言える.しかしな
がら,感染ホストがパケットを送信するタイ
ミングに大きな偏りがあるため,分布が対数
正規分布からずれたものになっていると考
えられる.ダークネットに関するさらなる解
析は今後の主要な課題である.
(2) トラフィック生成モデル
上記解析結果より,AS 内ノードレベルトラ
フィックは対数正規分布で表現可能である
ことが明らかとなった.本稿では,そのよう
なトラフィック量の分布を生成する単純な
モデルを導入する.これは,multiplicative
growth model として経済学では良く知られて
いるモデルである(経済学では,所得の分布
や会社の規模の分布を説明するモデルとな
っている).
初期状態ではノード i(ノード数 n)は一様
乱数で振られた初期トラフィック量 p_i(0)
を持つ.これらのノードが時間発展の度に,
一様乱数で割り当てられた成長率 b_i(t)(>
1)を持つとすると,1 ステップ後のトラフィ
ック量は,p_i(1) = p_i(0)*b_i(0)と表すこ
とができる.すなわち時間ステップ k では,
p_i(k) = Π(b_i(k))*p_i(0)となる.両辺の
対数を取ると,log(p_i(k)) = Σlog(b_i(k))
+ log(p_i(0)である.このようなトラフィッ
クを持つノードが n 個存在する状況を考えて
みると,この対数を取ったものの分布は正規
分布となる.よって,オリジナルの分布は対
数正規分布である.
このモデルの前提はトラフィックの成長
が指数的であることだけであるが,我々の観
測では,2 種類のノードレベルトラフィック
ではその成長は指数的であることが確認さ
れており(b ≒ 1.3),このモデルの前提条件
は満たされていることがわかった.
実際にシミュレーションでトラフィック
の分布を調べた結果を図 4 に示す.シミュレ
ーションパラメータは,トラフィックの初期
値:1〜1000 の乱数,ノード数:1000,増加
率 1.0〜2.0 とした.図中の 3 つのプロット
は下記の 3 つのシナリオに対応する.(1) 20
回の指数的増加モデルの反復,(2) 40 回の指
数的増加モデルの反復,(3) 20 回の指数的増
加モデルの反復の後,20 回の加算的増加モデ
ル(p_i(t) = p_i(t-1) + a_i(t-1))の反復.
実験結果を見ると,シナリオ 1 でまず実際
のトラフィック分布で現れるのと同じよう
な裾の長い釣り鐘状の分布が現れることが
わかる.これは,トラフィック成長の反復が
比較的少なくてもトラフィック量は対数正
規分布に近いものが得られることを表して
いる.また,シナリオ 2 では,時間発展とと
もに,分布の最頻値が右方向へシフトしてい
くことがわかる.これは,加入者レベルトラ
フィックの時間発展で得られた結果と似た
ものとなっている.最後にシナリオ 3 である
が,これは,将来的にトラフィック量の成長
が緩やかになりほぼ加算的になった場合の
想定シナリオである.この結果は,分布の左
側部分のトラフィックの少ない部分には多
少の違いがあるが,おおむねシナリオ 1 の結
果とほとんど同じであることがわかる.つま
り,将来的にトラフィックの成長が止まった
としても,インターネットトラフィックの分
布が一度対数正規分布になったとすると,他
の分布に変化する可能性が少ないことを表
している.
以上のシミュレーション結果より,現在,
および近未来のトラフィック量分布を必要
とするシミュレーションでは,その分布を対
数正規分布で表現することに妥当性を与え
るものであると結論づけられる.
現在のインターネットトラフィックを生
成している主要なアプリケーションは,P2P
アプリケーションによるものである(我々の
調査ではバックボーントラフィックの 80%程
度が P2P と推定).それに対して,ビデオス
トリームや google map に代表されるような
広帯域のネットワークを必要とするアプリ
ケーションの需要が高まっていることも指
摘されている.ISP 加入者トラフィックのデ
ータにせよ,学術加入機関のトラフィックに
しせよ,多数を占めるライトユーザは,P2P
トラフィックの生成には関与していないが,
今後はこれらの広帯域利用アプリケーショ
ンの普及とともに,徐々にではあるが,トラ
フィックを生成するノードへと変化してい
くと予想されるため,シナリオ 3 で示した楽
観的な状況になる見込みは今のところ低い
と思われる.
5.主な発表論文等
(研究代表者、研究分担者及び連携研究者に
は下線)
〔雑誌論文〕(計 1 件)
① 福田 健介,佐藤 進也,明石 修,廣津 登
志夫,栗原 聡,菅原 俊治,ネットワー
クトポロジの次数情報に着目したサー
バ・クライアント負荷分散方式の提案と
評価,コンピュータソフトウエア,vol.24,
pp.78-87, 2007. 査読有
〔学会発表〕(計 3 件)
① 福田 健介,廣津 登志夫,明石 修,菅原
俊治,異常パケットトレースアドレス局
所性に関する解析,情報処理学会全国大
会,2007 年 3 月 14 日, 査読無
② Kensuke Fukuda, Towards Modeling of
Traffic Demand of Node in Large Scale
Network,
Proc.
IEEE
ICC2009,
pp.214-218, 北京,2008. 査読有
③ Kenjiro Cho, Kensuke Fukuda, Hiroshi
Esaki, Akira Kato. Observing Slow
Crustal Movement in Residential User
Traffic, Proc. ACM CoNEXT2008, p.12,
マドリッド,2008, 査読有
〔図書〕
(計 1 件)
①福田 健介, P2P 教科書,インプレス社,
pp.280-297, 2007
〔その他〕
ホームページ等
http://www.fukuda-lab.org/
6.研究組織
(1)研究代表者
福田 健介(FUKUDA KENSUKE)
国立情報学研究所・アーキテクチャ科学研
究系・准教授
研究者番号:90435503
ダウンロード

様式 C-19 科学研究費補助金研究成果報告書