P2P環境におけるアプリケーションレベルマルチキャスト

概要

　近年、マルチメディアコンテンツのストリーミング等の需要が高まっている。これ らのアプリケーションでは、マルチキャスト通信を用いることによって、ネットワー ク資源の消費を少なくすることができる。 また、マルチキャスト通信では全クライアントがサーバへ接続する必要が無いため、 サーバの負荷も小さくなる。
　これまでに、Application Level Multicast(ALM)に関する多くの研究が報告されて いるが、本研究では分散ハッシュを用いたALMであるScribe[1]の改良を行う。
　Scribeにおいて、帯域の制限によって発生するpushdown操作は、マルチキャスト通 信の性能を大きく左右する。本研究では、ノードの性能がヘテロである環境を想定し、 Scribeでの従来のpushdownよりもネットワーク資源の消費が少なく、効率 の良い新しいpushdownを提案する。

Scribe/Pastry

　本研究で対象としたScribe[1]は，分散ハッシュの1つであるPastry[2]を 用いてマルチキャスト木を構築する．
　 　Pastry上の各ノードは，ID空間的に遠いノードは大まかな情報，近いノードは詳し い情報を持つルーティングテーブルを維持し、Pastryでの検索はこのルーティング テーブルを用いて行なう．
　図1に示すように，Pastryでは目的のIDに少しずつIDが近づいていく形式で検索経路 が選ばれる．Scribeでは，Pastryの検索経路を利用し，検索経路の次の中継ノードに join要求を出すことでマルチキャスト木を構築する(図2)．
plaxton2.jpeg(15422 byte) multicast-tree.jpeg(15023 byte)
図1：Pastryでの検索経路例 図2：Scribeでのマルチキャスト木例

pushdown

　一般的にノードの上り帯域には制限があるため，各ノードがマルチキャス ト木上で保持することが可能な子ノード数には限界がある．この、保持することが 可能な最大の子ノード数をDegreeと呼ぶ．
　Scribeでは，マルチキャスト木の構築時にDegree以上のjoin要求を受けた場合， pushdownを行うことにより，子ノード数をDegree以下に抑える．
　Scribeでの既存のpushdown手法としてBharambeら[3]によって，以下の2種類 のpushdownが提案されている。
Preempt ID pushdown
マルチキャスト木のIDであるmulticast keyと一致するプレフィックスが多 いIDを持つノードが優先される
Preempt Degree pushdown
Degreeが多いノードが優先される
　論文[3]では、ノードの性能がヘテロな環境において，Preempt Degree pushdown が，高さの低いマルチキャスト木を構築可能と報告されている．
　しかし，Preempt Degree pushdownではDegreeのみしか考慮していないため，親ノー ドから離れているノードであっても，Degreeが大きければpushdown時に優先される． その結果，親子ノード間の距離が大きいマルチキャスト木が構築され，ネットワー ク資源の大量消費が問題となる。

提案手法

　本研究では，pushdown時にノードと親子ノード間のリンクの両方を評価することで ネットワーク資源の消費を減少させるHybrid pushdown及び，Hybrid pushdownにおけ るパラメータを動的に変更するDynamic Hybrid pushdownを提案する．
　　Hybrid pushdownでは，ノードとリンクの両方を評価するために以下の評価式を用 いてpushdownを行う．
valuation-plan.gif(3872 byte)

　Hybrid pushdownの時，親ノードは上記の式を用いてpushdownノードとリダイレクト先ノー ドを選択する．
pushdownノード
自分の子ノードとjoin要求をしてきたノードの中か ら評価値が最も小さいノードを選択．
リダイレクト先ノード
残りのノードの中から評価値で重み付けした確率に 従ってランダムに選択．
　上記の式によってDegreeとHopの両方を評価することにより，ネットワーク資源の消費 を減少させることが期待できる． また，評価値で重み付けした確率に従ってランダムにリダイレクト先を選択するこ とにより，評価値の高いノードほど多くの子孫ノードを持つことになる．その結果， Degreeを重視した評価値を用いた場合は木の高さが低くなり，Hopを重視した評価 値を用いた場合はネットワーク効率が良いマルチキャスト木を構築することが可能 となる．
　Dynamic Hybrid pushdownでは，子ノードの平均Degreeから動的にパラメータを変 更することで，Hybrid pushdownより効率的なマルチキャスト木の構築を行う．
　Dynamic Hybrid pushdownでは、子ノードの平均Degreeが小さい場合は，Degreeを 重視するパラメータにすることで少ないDegreeを有効に使い，高さの低い木を構築する． 反対に，子ノードの平均Degreeがある程度以上に大きい場合は，どの子ノードを pushdownノードとして選択しても木の高さは低くなる．そこで，子ノードの平均 Degreeが大きい場合は，Hopを重視したパラメータにすることで，木の高さを低く し保ったままネットワーク資源の消費を低減させることが可能となる．

実験

　提案手法の有効性を計算機シミュレーションによって評価する．評価方法として Median Depth，Average Link stress，Relative Delay Penalty(RDP)の3種類を用 いた．
　ネットワークシミュレータとしてns-2，ネットワークモデルとしてGT-ITMを用い， Scribeに参加するノードが512台，ルータが64台の計576台で実験を行った．

実験結果

Median Depthの結果
node576-dhp-depth.jpeg(62895 byte)
図5：Median Depthの結果

　Degreeを評価したパラメータのHybrid pushdown及び、Dynamic Hybrid pushdownは、 Preempt Degree pushdownと同じ程度に低い木を構築できていることが確認できる。


Average Link stressの結果
node576-dhp-linkstress.jpeg(70023 byte)
図6：Average Link stressの結果

　Preempt Degree pushdownが最も悪いLink stressとなっている。全体的には、Hopを評価するpushdownほど良い結果となり、 ネットワークの利用効率が良くなっていることが確認できる


。
Relative Delay Penalty(RDP)の結果
node576-dhp-rdp.jpeg(66590 byte)
図7：Relative Delay Penalty(RDP)の結果

　Hybrid pushdownはPreempt Degree pushdownよりも良いRDPの値となっており、遠回りな経路が少ないことが確認できる。そして、 Dynamic Hybrid pushdownはHybrid pushdownよりもさらに良いRDPの値になっていることが確認できる。

　Hybrid pushdownは、全ての評価方法において既存のpushdownであるPreempt Degree pushdownよりも良い結果となった。 また、パラメータを動的に変化させることで、Dynamic Hybrid pushdownはさらに良い結果となった。

参考文献

[1] M. Castro, P. Druschel, A. Kermarrec, and A. Rowstron, SCRIBE: A large-scale and decentralized application-level multicast infrastructure, IEEE Journal on Selected Areas in Communications Vol.20 No.8, pp.1489-1499, Oct. 2002.
[2] A. Rowstron, and P. Druschel, Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), pp.329-350, Nov. 2001.
[3] A. R. Bharambe, S. G. Rao, V. N. Padmanabhan, S. Seshan, and H. Zhang, The Impact of Heterogeneous Bandwidth Constraints on DHT-Based Multicast Protocols, Proceedings of 4th International Workshop on P2P Systems(IPTPS) 2005, Feb. 2005.