1 - 森野研究室

仮想バックボーンの導入による
P2P網の帯域利用効率化の検討
芝浦工業大学工学研究科
杉野博徳森野博章三好匠
研究の目的
Application Level Multicast(ALM)における配信ツ
リーを物理網を考慮して構築する
•ALMの配信ツリーは参加ピア同
士の論理リンクにより構築
D
配信ピア
C
論理網
B
A
図は，A,B,C,Dの順にピアが配信ツリーに
参加している例(各ピアの最大次数=3)
•論理リンクにより各ピアの中継
数の分散をする制御
D
配信ピ
ア
C
B
物理網
A
物理網を十分に考慮しているわ
けではないので，非効率な経路
を利用している可能性がある
研究の背景(1)
物理網を考慮した配信ツリーの構築
MST
ツリー構築の2つのアプローチ
•MST(Minimum Spanning Tree)
D
配信ピ
ア
C
•SPT(Shortest Path Tree)
B
MST(Minimum Spanning Tree)
A
物理網を考慮しないツリー
•物理Hop数の総和が最小になるよ
うに配信ツリーを構築
•配信ピアまでのHop数が大きくなる
可能性
例. ピアDの場合， 10Hop
D
配信ピ
ア
C
B
A
研究の背景(2)
物理網を考慮した配信ツリーの構築
SPT
SPT(Shortest Path Tree)
D
配信ピア
•新規参加ピア-配信ピア間のHop数が
最小にするように配信ツリーを構築
C
例. ピアDは，ピアA,B,Cのう
ちピアCと接続
•利用効率が落ちる可能性
例. 配信ピア->CとC->Dの通
信で同じ経路に同じデータ
が流れる
B
A
物理網を考慮しないツリー
D
配信ピ
ア
C
B
A
研究の背景(3)
SPT，MSTによる配信ツリー構築
•それぞれ長所，短所がある
•ピアの参加する順番に左右される
SPTの場合
MSTの場合
そこで，
配信ピア
配信ピア
DD
ピアはA,B,C,Dの順に参加
各ピアの最大次数=3
DD
配信ピア
配信ピア
SPT,MSTの特徴を生かせるように予め配信
C C
ツリーを構築したらどうか？
BB
AA
仮想バックボーンの導入
BB
AA
ピアBとピアAの参加順が逆だとよりよいツリーの構築が可能
ピアDとCの参加順が逆だとよりよいツリーの構築が可能
CC
仮想バックボーンの構築(1)
ALMに参加するピアの分類
前提として、ALMに参加するピアには次の3種類があると
仮定する
長期視聴・常時接続ピア
長期間サービスを利用するユーザピア
ネットワークには常時接続
短期視聴・常時接続ピア
短期間サービスを利用するユーザピア
ネットワークには常時接続
短期視聴・非常時接続ピア
短期間のみサービスを利用するユーザピア
ネットワークには一時的に接続
今回のポイント
サービスを利用していなく
ても，ネットワークに常時
接続しているピアを配信
ツリーに組み込む！！
仮想バックボーンの構築(2)
仮想バックボーンの構築
Step1. バックボーン構築ピアの選択
ピアに対して重み付けし，重みが大きい
ピアを選択
重み付け
•任意の2ピア間の最短経路を計算
図の場合，(A->B), (A->C), (B->A),
(B->C), (C->B), (C->A)
A
•ある最短経路上に存在するピアの重重み (0)
みを1増加(ただし，両端は除く)
Step2. 重みの大きいピアによりス
タイナー木を作成する
A -> C
C -> A
B
(2)
C
(0)
重みづけの例
仮想バックボーンの構築(3)
バックボーンツリーの例
()内の数値は重み
仮想バックボーンツリー
常時接続ピア
配信ピア
バックボーンを構
築するピア(BP)
(16)
(13)
(0)
(3)
(13)
(8)
(0)
配信ツリーの構築
•ピアの参加アルゴリズム
新規参加ピアの最寄りのBPを発見
接続先候補ピア=最寄りのBP
新規参加ピア-BP間の経路上に参加ピアは
存在するか？
Y
接続先候補ピア=経路上の参加ピア
接続先候補ピア=
接続先候補ピアの子ピア
N
接続先候補ピアと接続可能？
接続
Y
N
シミュレーションによる性能評価(1)
評価指標
•ピア-配信ピア間の平均物理Hop数
遅延への影響
•延べ利用物理リンク数
B
論理リンク
A-> B, B->C
3
4c
5 d
C
2
b
a 1
A
延べ物理リンク数=5
ネットワーク全体での帯域の消費
•平均リンク集中度
Link a,b,dの集中度=1
Link cの集中度=2
物理リンクがどれぐらいの論理リン平均Link集中度=1.25
クにより利用されているか
シミュレーションによる性能評価(2)
比較方式
iMST
•incremental MST
•新規参加ピアは，既存の配信ツリーに対して物理
Hop数の総和が最小になるように物理リンクを追加
SPT
•通常のSPT(Shortest Path Tree)によるアプローチ
•新規参加ピアは，配信ピアとの間の物理Hop数が
最小になるように物理リンクを追加
シミュレーションによる性能評価(3)
各方式におけるピアの分類
今回のシミュレーションでは，次のような仮定をしている
長期視聴・常時接続ピア
提案方式・・・存在しない
比較方式・・・存在しない
短期視聴・常時接続ピア
提案方式・・・BPとして選ばれるピアは全てこの分類
比較方式・・・存在しない
短期視聴・非常時接続ピア
提案方式・・・BP以外のピア
比較方式・・・全てのピアがこの分類
シミュレーションによる性能評価(4)
ネットワークモデル
ネットワークトポロジ
米国Abileneネットワーク
ピア数
367
ルータ数
126
各ピアの最大次数
3
視聴間隔
負の指数分布(平均=10[min])
離脱から次の視聴まで
の間隔
負の指数分布(平均=10[min])
シミュレーション時間
1000[min]
評価結果(1) 配信ピアまでの平均Hop数
average number of hops between the server and a peer
number of hops
60
50
40
30
20
10
0
iMST
SPT
Proposal Proposal Proposal
(BP=5) (BP=10) (BP=15)
仮想バックボーンにより，BPもしくはBPに近いピアと接続すれば配
信ピアまでのホップ数の低減ができたと考えられる
評価結果(2) 延べ物理リンク数
number of physical links
total number of used physical links
1200
1000
800
600
400
200
0
iMST
SPT
Proposal Proposal Proposal
(BP=5)
(BP=10) (BP=15)
各ピアとBPとの接続経路には最短経路を利用するため，物理リンク
数の低減があまり起こらなかったのではないかと考えられる
degree of concentration
評価結果(3) リンクの集中度
4
concentration of logical links
3.5
3
2.5
2
1.5
1
0.5
0
iMST
SPT
Proposal Proposal Proposal
(BP=5)
(BP=10) (BP=15)
延べ物理リンク数と同様の理由で集中度の低減
が起こってないのではないかと考えられる
評価結果のまとめ
•延べ利用物理リンク数
ProposalはiMSTとほぼ同じ結果
•ピア-配信ピア間の平均物理Hop数
ProposalにHop数の低減効果が見られた，
BPの数が多いほど効果が大きい
•平均リンク集中度
ProposalはSPTより小さく，iMSTより大きい結果
本発表のまとめ
物理網を考慮してALMの配信ツリーを構築する
ために仮想バックボーンの導入を検討した
今後の課題
•提案方式の性能と常時接続ピアの配置との関連性の評価
•バックボーンを構築するピアの最大次数を変化させた場
合の評価

Download Report