ツリー型 P2P システムにおける 3 種の再接続法の遅延時間評価
2009SE078 石黒 裕貴

2010SE146 中山 遼祐

2010SE230 竹内 秀幸

指導教員： 河野 浩之

はじめに

1

近年，インターネットの高速化，普及によりコンテンツは多様化し，P2P を利用したサービスが次々と登場している．
これら，P2P を用いられるネットワークは物理的な接続を表す物理ネットワークと，論理的な接続を表す論理ネットワークの 2 層から構成されている．
また，P2P ではネットワーク上で自由な接続を行えるた
め，ノード同士の接続の仕方によってそのシステムの性能が大きく変化してしまう．実際の P2P ネットワークではピアの離脱が発生し，結果としてトポロジの再構築が必要となる場合がある．
そこで，本研究ではツリー型のネットワークトポロジに

図 1 オーバーレイ･ネットワーク

おいてピアが参加，離脱した時の再接続の際，先行研究

また，P2P ネットワークにおいてツリー型のネットワークト[1]で使用されたピア選択法を用いることで，よりスケーラポロジがある．

ビリティに優れたネットワークの再構築を行う．そこで現れツリー型とはネットワークの中心となるルートノードからる遅延時間の変化を比較し評価する．

枝分かれするように下位層へ繋がっていくトポロジである．

本論文の構成は以下の通りである．2 章では P2P ネット

末端のノードが故障しても他のノード間の通信には影響

ワークの形態，離脱，先行研究との比較について述べる．

は受けないが，上位層のノードが故障するとそのノードよ

3 章では提案された動的トポロジ法を述べる．4 章ではパり下位層のノードが影響を受ける．

ラメータ設定，シミュレーション実験，離脱･再構築のシナリオについて述べる．5 章にて遅延時間の評価，比較について述べる．6 章ではまとめを述べる．

2.3

離脱と遅延P2P ネットワークでピアがネットワークから外れることが離脱である．丸で囲んだピアの離脱から接続の切れたピP2P ネットワーク

2アの再接続までの流れを図 2 に示す．

本章では，2.1 節で P2P の概要を，2.2 節で P2P のネットワーク形態，2.3 節でピアの離脱と遅延，2.4 節でツリー型の遅延時間の変化を述べる．

2.1

P2P の概要

P2P とはネットワークに接続されたコンピュータ同士が端末装置として対等の立場，機能で直接接続し，データ手順 2

手順 1を送受信する通信方式である．従来のクライアント･サーバ型と比べて，特定の端末にアクセスの集中がないため負荷分散ができ，スケーラビリティに優れているというメリットがある．

2.2

ネットワーク形態

P2P ネットワークにおいて，すでに存在する下層ネットワ

手順 3
図 2 ピアの離脱と再構築

ークの物理構造の上位にあたる層において，仮想的に手順 1．P2P ネットワークが形成されている．

形成されたネットワークをオーバーレイ･ネットワークという．

手順 2．丸で囲んだノードが何らかの影響で離脱．

オーバーレイ･ネットワーク下位層を隠蔽して汎用性高め

手順 3．離脱の影響で通信が切れたノードを別の経路るとともに，下位層に新しい機能を追加する技術を指す．
その形態を図 1 に示す．

から接続．

１つ選択する(ノード k と表す)そしてノード k を からツリー型における遅延時間の変化

2.4

先行研究[1]では，ツリー型のネットワークトポロジにお取り除く．
(4) (手続きの終了)：ノード i とノード k を接続し手続きを終いて動的トポロジ構築法を用いた離脱耐性評価が行わ了する．

れた．提案された論理ホップ最小化法，物理ホップ最小供給可能なノードを化法，ランダムピア選択法の 3 つのピア選択法を用いて全てシミュレーションを行い評価した結果，論理ホップ最少化の要素とする法は有用性が高いことが示された．しかし，トポロジの再構築後の遅延時間については比較されていない．
本研究では先行研究[1]において提案された 3 つのピのうち論理ホップ数

ア選択法をツリー型のトポロジに適応させて，それぞれが最小なノードを の要再構築後の遅延時間の変化がどう現れるかシミュレーシ素とし, から取り除くョンを行い，評価していく．のうちランダムに 1

動的トポロジ構築法

3つ選択したノードを と先行研究[1]において 3 つのピア選択法が提案された．

し, から取り除く

ピア選択法とは，目的に合わせて優先的に選択するピアを変更した様々な提案のことである．
ノード i とノード k を接本章では 3.1 節で論理ホップ最小化法，3.2 節で物理ホップ最小化法，3.3 節でランダムピア選択法の 3 つのピ続する

ア選択法について順に説明する．

論理ホップ最小化法

3.1

手続きを終了する

各ピア選択法について以下のことを定義し，3.1，3.2，3.3 で用いる．

図 3 論理ホップ最小化法のフローチャート･配信の起点となるノードをルートノード．
･ネットワーク上にあるノードの集合を S．

物理ホップ最小化法

3.2･供給可能なノードを j，接続要求を行うノードを i とする．

論理ネットワーク上で自由にノード接続を行えることが･論理ネットワーク上でルートノードからのホップ数を論理P2P の利点として挙げられるが，物理ネットワークを考慮ホップと呼び， とする．

しないピア選択では伝送に無駄が発生している場合があ･供給を行うノードをノード k．

る．これによりネットワーク間のトラフィックの増加が起こり，論理ホップ数に差がある複数のピアを供給ピアにして遅延や動画品質の劣化を引き起こす原因にもなる．そこしまうと，論理ホップの大きい親ピアに合わせて子ピアので，遅延時間の小さいピア同士を接続することで，ネット論理ホップが決定されるため，接続できるピアの総数をワーク間のトラフィックを低減させることを目的とする物理減らしてしまう問題が発生する．そこで論理ホップ数の極ホップ最小化法が提案された．また，物理ホップ最小化

力小さいピアから順番に供給ピアを選択していくことで，法のアルゴリズムを以下に示す．

ネットワークに参加可能なピア数を増加させることを目的

論理ホップ最小化法のアルゴリズムに記述中の(2)にとする論理ホップ最小化法を提案する．また対象となるおける“論理ホップ数”を“ノード i からの遅延時間”に変更

論理ホップ数のピアが複数存在する場合は，そのうちかする．

らランダムにピアを選択する．論理ホップ最小化法のアルゴリズムを以下に示す．また，そのフローチャートを図 3に示す．
(1) ( の作成)：j(て≧1，かつをみたすピア)を全に含まれるノードのうち，論理ホップ数が最小のノードをの要素とし，そのようなノードをから取り除く．
(3) (ピアの選択)：

ランダムピア選択法

接続ピアを供給可能なものの中からランダムに選択しの要素とする．

(2) ( の作成)：3.3ていく方式である．ランダムピア選択法のアルゴリズムを以下に示す．
(1) ( の作成)：供給可能なノード j(を満たすピア)を全て(2) (ピアの選択)：に含まれるノードのうち，ランダムに≧１，かつの要素とする．に含まれるノードのうち，ランダムに１つ選択する(ノード k と表す)そして選択したノード k をから取り除く．

が接続要求を出すことになるのでそれぞれの手法を使用(3) (手続きの終了)：ノード i とノード k を接続し手続きを終了する．

し，論理ネットワーク上に接続していく．また，観測するデータとは別にケンブリッジ大学‐ハーバード大学間で送受信を行うデータが存在する．

ピア離脱後の遅延時間評価

4

本研究ではネットワークシミュレータである NS-2 を用いてネットワーク構築を行い，シミュレーションを行った．
本章では，4.1 節ではパラメータ設定，4.2 節ではシミュレーション実験，4.3 節で離脱・再構築のシナリオについて述べる．

4.1

パラメータ設定

シミュレーション実験を行うにあたり，使用するパラメータの項目を表 1 に示す．
表 1 実装するパラメータ要求数(Ni)

1ピアの最大供給可能数(Mi)2

ルータ

20ピアの数40

配信元

1最大論理ホップ数(H)7ピアの離脱回数

8ピアの参加回数4

図 4 南山大学内の物理ネットワーク

要求数を 1 にすることで接続するピアが論理ネットワー
ク上でのリンク数を 1 にする．ピアの最大供給可能数を 2にすることで供給できるピアに接続できるピアを制限している．ルータ数 20，ピアの数 40 にすることで物理ネットワーク上ではノード数が 60，論理ネットワーク上ではノード数が 40 とする．配信元を 1 にすることでツリー型のトポロジにする．最大論理ホップ数を 7 にすることでネットワークが広がり過ぎないように設定する．またピアの離脱回数を8，ピアの参加回数を 4 に設定する．

4.2

図 5 南山大学内の論理ネットワーク

シミュレーション実験

ピアが存在する場所はケンブリッジ大学，南山大学，ハーバード大学にあると仮定し，ケンブリッジ大学‐南山大学間を 280ms，南山大学‐ハーバード大学間を 230msとリンク間の遅延を大きくしてある．使用する物理ネットワークのうち南山大学内の物理ネットワークを図 4 に示す．

4.3

離脱・再構築のシナリオ本研究ではシミュレーション開始から 1 秒毎にランダムにピアを参加，離脱させていく．
パケットを流すことや止めることでピアの参加，離脱をまた，使用する論理ネットワークのうち南山大学内の論行う．また離脱したピアの下位層に位置するピアは離脱

理ネットワークを図 5 に示す．配信元である南山大学から，した時間に再接続をする．シミュレーション時間は 12 秒とケンブリッジ大学，ハーバード大学へとデータを送信し，し，離脱するピアはランダムに選択する．

その様子を観測する．論理ネットワーク上に元から参加し接続を行うピアは 3 種の接続法によって接続ピアを決ているピア数を 36 とし，シミュレーション開始から１秒ごと定する．また，どのピアが供給可能であるか接続要求をに離脱と参加を繰り返し合計 12 回行った．8 つのピアを離脱させることで離脱したピアの下位層に位置するピア行うピアは把握しているものとする．

表 2 最下層ピアの平均遅延時間
参加，離脱前物理ホップ最小化法

論理ホップ最小化法

ランダムピア選択法

3 秒後

1.02541[ms]1.07753[ms]1.12419[ms]1.199852[ms]

6 秒後

1.02541[ms]0.9982[ms]1.07776[ms]1.06924[ms]9 秒後

1.02541[ms]0.86894[ms]1.17346[ms]1.58247[ms]12 秒後

1.02541[ms]0.72175[ms]1.17829[ms]1.476429[ms]離脱後の再構築のシナリオプログラムの一部を以下にンク間の遅延が大きなリンクを伝送路として使用するピア

示す．

を選択した場合，伝送に無駄がある場合があった．一方，$ns at 1.0 “$ftp 56 stop” //離脱ピアの ftp の停止

物理ホップ最小化法ではリンク間の遅延を最優先に考慮$ns at 1.0 “$ftp 15 stop”

し接続を行うため，参加，離脱を繰り返すごとに最下層ピ

set tcp64 [new Agent/TCP] //再接続ピアの tcp の設定

アの平均遅延時間が減少していく傾向が見られた．

$ns attach-agent $n26 $tcp64
set sink64 [new Agent/TCPSink]$ns attach-agent $n58 $sink64$ns connect $tcp64 $sink64
set ftp66 [new Application/FTP] //ftp の設定$ftp66 attach-agent $tcp66$ns at 1.0 “$ftp 64 start” //ftp のスタート

遅延時間の評価，比較5

本章では 5.1 節で遅延評価，5.2 節で各手法ごとの遅延時間を比較する．
図 6 最下層ピアの平均遅延時間

5.1遅延評価

以下ではピアが離脱した場合についてピア選択法によまとめ

6る再接続が離脱する前後の伝送遅延の変化に与える影本研究では，スケーラビリティに優れたトポロジ構築の響を観測する．シミュレーションより得たトレースファイルために，ピアの参加，離脱の際の接続法について3種類の解析を行い，リンク間の平均遅延時間を算出する．のピア選択法を使用し遅延時間を比較評価した．

sをパケット受信時間，tをパケット送信時間，nを送受信回数として平均遅延時間を式で表すと次式になる．
平均遅延時間．

結果，物理ホップ最小化法が最も平均遅延時間を小さくすることが出来た．しかし，ピアが離脱･参加を繰り返しトポロジの再構築を行うことによって末端のピアまでの(1)論理ホップ数にばらつきができ，効率の悪いトポロジになることがある．そこで定期的にピア間の接続をリセットし，5.2

比較つなぎ直しトポロジの整理を行う必要がある．また，論理論理ホップ最小化法，物理ホップ最小化法，ランダムホップ最小化法と物理ホップ最小化法を組み合わせ，各ピア選択法を使用し，各手法ごとに3秒ずつ最下層ピア

手法の利点を取り入れた接続法を提案することを検討しの平均遅延時間の値を算出した．その値を表2，また縦ていきたい．

軸を遅延時間(ms)，横軸を経過時間(s)としグラフ化したものを図6に示す図6は黒を参加，離脱前，赤を物理ホッ

参考文献

プ最小化法，青を論理ホップ最小化法，黄色をランダム[1]

ピア選択法の順に並んでいる．
比較の結果，物理ホップ最小化法が最も平均遅延時

電子情報通信学会，NS2010-58，pp.61-62，間を小さくすることができた．論理ホップ最小化法は参加，離脱が繰り返し行われても，ホップ数に偏りのないトポロ

石井智之，井家敦，“スケーラビリティを考慮した
P2P ストリーミングにおける動的トポロジ構築法，”(2010)．

[2]

Eyuphan B. and Boleslaw K．S．，“Constructing

ジを形成することができた．しかし今回のようにリンク間のLimited Scale-Free Topologies Over Peer-to-Peer

遅延に大きな差がある場合，物理網を考慮しないため伝Networks”，Parallel and Systems，pp.2-3，(2013)．

送に無駄がある場合があった．ランダムピア選択法は，リ