仮想バックボーンを利用するALMにおける 常時接続ピアの評価指標に関する検討 芝浦工業大学大学院 工学研究科 杉野博徳 森野博章 三好匠 研究の背景・目的 –はじめに放送型の一対多通信を行うサービスが増加してきている ex.ストリーミング配信，IPTV マルチキャストの利用による効率化 ex. IPマルチキャスト，Flexcast，ALM (OLM) 各マルチキャストの相違点はパケットの複製・中継を役割を担うノード IPマルチキャスト Flexcast ALM ルータ スプリッタ ユーザ端末 ネットワークに専用の 設定やノードが必要 アプリケーションの インストール ALMは導入の容易さなどの面で有利である 研究の背景・目的 –ALMの問題ALMは基本的に論理網で配信ツリーを構築を行う 配信元 C しかし，物理網を考慮せずに 例のような配信ツリーを構築すると 論 理 網 A B D 冗長なTraffic 転送遅延の増大 1 ルータ 配信元 9 物 理 網 2 10 3 A 配信ツリーの例 8 7 C 6 11 4 12 D 今後，ユーザが増加するに従い深 刻な問題となる 5 B データ到達までのHop数が大きく転送遅延が大きい 問題解決へのアプローチ –従来方式MST(Minimum Spanning Tree) •物理Hop数の総和を最小する SPT(Shortest Path Tree) 1 2 11 D MST 3 •新規参加ピア-配信ピア間のHop数が 最小にするように配信ツリーを構築 A 5 4 10 6 B 8 7 9 C 図はA,B,C,Dの順番でピアが参加 欠点・課題点 MST D SPT •配信ピアからのHop数の増加 SPT •冗長なTrafficの発生 共通 •ピアの参加順が影響する A B C 問題解決へのアプローチ –提案方式 VBT(Virtual-Backbone-based Tree) 予め仮想的なバックボーン(Virtual Backbone)を構築しておく Virtual Backbone (仮想バックボーン) 配信元 バックボーンを利用する効果 •近傍に接続先となるピアが存在 •経路集約 Trafficの削減とHop数の低減 バックボーン構築ピアの選択指針 •ネットワークに常時接続し接続を 受け付けられるピア •各ALM参加ピアからアクセスしや すい位置に存在しているピア 仮想バックボーンを利用した例 Virtual Backboneの構築(1) ALMに参加するピアの分類 前提として、ALMに参加するピアには次の3種類があると 仮定する 長期視聴・常時接続ピア 長期間サービスを利用するユーザピア ネットワークには常時接続 短期視聴・常時接続ピア 短期間サービスを利用するユーザピア ネットワークには常時接続 短期視聴・非常時接続ピア 短期間のみサービスを利用するユーザピア ネットワークには一時的に接続 今回のポイント サービスを利用していなく ても，ネットワークに常時 接続しているピアを配信 ツリーに組み込む！！ Virtual Backboneの構築(2) Step1. バックボーン構築ピア(BP)の選択 常時接続ピアに対して重み付けする 常時接続ピア 重み付けの定義式 WR = i HOPPi→S HOPPi→R + HOPR→S R Hop R->S HopP ->R i WN =WR /N 重みの大きいピア(X-1)個と配信ピア をBPとして選択する S HopP ->S i Pi Step2. スタイナー木の作成 Step.1で選択したピアによりスタイナー木を構築 重み付けの例 配信ピア 配信ツリーの構築 -ピアの新規参加- •ピアの新規参加 Virtual Backbone BP Step1. 最寄りのBPの発見 参加済みピア R Step2. 接続先ピアの決定 HopP->R 接続先判定式 HOPPi→BP R= HOPPi→R + HOPR→BP Hop R->BP BP BP 最短経路 Hop P->BP 新規参加ピア P R > RT (閾値) となる参加済みピアが， 存在する 参加済みピアを接続先ピアにする 存在しない BPを接続先ピアにする Step3. 接続を行う 接続先ピアの子ピアが接続上限数に達していた場合 子ピアに対して接続動作を行う BP 性能評価 -評価指標評価指標 •ピア-配信ピア間の平均物理Hop数 転送遅延への影響 Hop数が少なければ参加ピアへデー タが到達する時間が短くなる •延べ利用物理リンク数 ネットワーク全体での帯域の消費 リンク数が少なければネットワークに かかる負荷が少なく効率的といえる B 3 論理リンク A-> B, B->C 4 2 5 1 C 延べ物理リンク数=5 A 性能評価 -ネットワークモデルネットワークトポロジ Abilene ピア数 203 常時接続ピア数 20 ピア新規参加時の閾値RT 0.6 各ピアの最大接続数 3 視聴間隔 負の指数分布(平均=10[min]) 離脱から次の視聴までの 間隔 シミュレーション時間 負の指数分布(平均=10[min]) 1000[min] 性能評価 -トポロジー(1) - 全てのピアが常時接続ピアと仮定した際の各ピアの重みの様子 配信ピア 0.4 <= WN < 0.5 0.5 <= WN < 0.6 0.6 <= WN 配信ピアに近い位置のピ アのWRの値が大きい ハブノードに接続されてい る影響 評価結果(1) -BPの選択数の変化常時接続ピアはランダム配置 Hop 平配 均信 ピ ア 数 参 加 ピ ア 間 の 25 750 平均Hop数 延べ物理リンク数 20 延 べ 600 物 理 450 リ ン ク 300 数 - 約 3 割 低 減 15 10 5 150 0 0 VBT (BP=3) VBT VBT VBT SPT (BP=7) (BP=15) (BP=21) MST 平均Hop数の低減の効果が大きい、ただしBP数には最適値が存在し， 大きすぎる場合は性能低下 評価結果(2) -WNによるBPの選択WN=(WR/総ピア数)を利用してBPを選択(上限15とする) Hop 平配 均信 ピ ア 数 参 加 ピ ア 間 の 25 平均Hop数 延べ物理リンク数 20 750 600 - 15 450 10 300 5 150 0 VBT VBT VBT (0.4<=WN<0.5) (0.5<=WN<0.6) (0.6<=WN) SPT MST VBT(0.6<P)の場合，BPは7個しか選択されていない 0 延 べ 物 理 リ ン ク 数 性能評価 -トポロジー(2) - コアネットワークがリング型の時の各ピアの重みの様子 配信ピア 0.4 <= WN < 0.5 0.5 <= WN < 0.6 0.6 <= WN コアネットワーク 評価結果(3) -BPの選択数の変化常時接続ピアはランダム配置 Hop 平配 均信 ピ ア 数 参 加 ピ ア 間 の 40 35 30 800 平均Hop数 700 延べ物理リンク数 約2割低減 600 - 25 500 20 400 15 300 10 200 5 100 0 0 SPT VBT VBT VBT VBT (BP=3) (BP=7) (BP=15) (BP=21) MST 延べ物理リンク数低減の効果が大きい 延 べ 物 理 リ ン ク 数 評価結果(4) -WNによるBPの選択WN=(WR/総ピア数)を利用してBPを選択(上限15とする) Hop 平配 均信 ピ ア 数 参 加 ピ ア 間 の 40 800 平均Hop数 35 700 延べ物理リンク数 600 25 500 20 400 15 300 10 200 5 100 0 0 - 30 VBT VBT VBT (0.4<=WN<0.5)(0.5<=WN<0.6)(0.6<=WN) SPT MST (0.5<=WN<0.6) のピアをBPとすれば十分な性能が出る 延 べ 物 理 リ ン ク 数 本発表のまとめ Virtual Backboneを利用した配信ツリー構築方式の提案 比較方式と比べ トポロジー(1) トポロジー(2) 平均Hop数が約3割低減 延べ物理リンク数が約2割低減 コアネットワークがツリーなら平均Hop数、リング型なら延べ物理リ ンク数に効果があるといえる バックボーン構築ピア(BP) •選択する数の最適値が存在する •0.5 < WN < 0.6のピアから選択できれば十分な性能が得られる 今後の課題 •ネットワーク規模を拡大させて評価 •VBTのツリー構築においてスタイナー木以外の検討 評価結果(3) -BPの分散と集中BP同士の位置関係による性能への影響 ここではBP同士が少なくとも4Hop以上離れている場合， BPの位置は分散しているとする ：ピア ：ルータ 近傍とする 分散とする また， 0.5<WN<0.6 と 0.6<WNの時は重み付けの仕方からピア が集中 しているので， 0.4<WN<0.5 の重みのピアからBPを選択 する 評価結果(3) -BP同士の位置関係による影響Hop 平配 均信 ピ ア 数 参 加 ピ ア 間 の 25 平均Hop数 750 延べ物理リンク数 600 15 450 10 300 5 150 0 0 - 20 VBT(近傍) VBT(分散) SPT MST 延 べ 物 理 リ ン ク 数 平均Hop数の低減には近傍配置，延べ物理リンク数の低減には分散配置がよい
© Copyright 2024 ExpyDoc
