オーバーレイ配送網を用いた高品質ストリーミング機構の設計と実装

慶應義塾大学
政策・メディア研究科
後期博士課程 80649220
久松　剛

背景

近年，PPLive[1], KeyholeTV[2]などの様々なオーバレイコンテンツ配送技術を用いたリアルタイムストリーミングアプリケーションがインターネット上で広く利用されている．これらのアプリケーションは，各々のストリームデータ配信に対して独自にオーバレイ配送網を構築するため，IPマルチキャストのような，ルータに対するルーチング機能追加要件なども無く，サービスの展開が容易である．また，CDNのような中央サーバに依存したデータ配送を行わないため，サービス実現のために高性能なサーバを準備する必要もなく，ネットワーク構築に対するコストも軽減できる．その結果，個人によるコンテンツ発信が容易である．

一方，オーバレイコンテンツ配送では，IPマルチキャストのように配信データのコピーや転送をルータが行うのではなく，受信ノードにその役割を担わせるため，受信者側の計算機やネットワーク資源に負荷を与えてしまうという性質もある．また，配送ノードの突発的な網からの離脱などに対応するため，重複データを配送網に流して耐障害性を高める必要があり，網全体に対する負荷も高くなる傾向がある．

このため，既存のオーバレイコンテンツ配送の多くは，配信するストリーミング帯域を 1Mbps以下に制限して利用されているものが多い．しかし，この制約は，IPTVや次世代のリアルタイムストリーミングアプリケーションなど，将来に向けた高品質ストリーミングの実現に対する障壁となる．つまり，数万，あるいはそれ以上のノードへの同時配信を実現するため，および，MPEG2 や H.264などのエンコーディングフォーマットを利用する高品質ストリーミングを実現するためには，従来の制約に縛られない，より広帯域な伝送路を構築できる新しいオーバレイ配送技術とそれを利用するアプリケーションの実現が求められる．

ここでの課題を整理すると，広帯域と高応答性を要求するリアルタイムストリーミングの実現において，アプリケーションが構築するデータ配送網を最適化させ，重複データの配送を軽減しつつもデータ欠損時には迅速，かつ効率的にデータの再取得を実現するオーバレイコンテンツ配送技術を開発する必要がある．

既存技術

代表的なオーバーレイネットワークを用いたストリーミング形態を図に示す．基礎的な形態としてMesh型，及びTree型がある．Mesh型は複数の近隣ノードについてランダム接続を行うために冗長性は高いが，メッセージング量が多いため転送効率が低いという特徴がある[3]．Tree型は上位ノードとの単一の伝送経路を持つため，メッセージング量や経路の重複が少なく転送効率が高い反面，冗長性が低いという特徴がある[3]．これらの発展形としてMultiple-Tree型，及びHybrid型がある．Multiple-Tree型ではTree型のセッションを複数持ち，それぞれにデータを分散，あるいは重複転送することで耐故障性と冗長性を高めている．Hybrid型の一つであるmTreeboneではサービスの参加時間や転送能力より主だったノードを中心にTree網が構築され，それ以外のノードはMesh網を形成し，転送を行う[3]．同じくHybrid型のBullet[4][5]では，Multiple-Tree網で中心的な転送を行い，未到達データをMesh網で補完する形態である．

代表的なP2Pストリーミング形態

オーバレイコンテンツ配送に関する各方式についてシミュレーションや実ネットワーク上で動作させ, 比較検証した研究がいくつか存在する. これらの論文を踏まえ, 各方式の特性をまとめたものを以下に示す.

各オーバレイコンテンツ配送技術の特徴を述べている論文[6]では，Mesh型は構造が単純な一方でスタートアップ時間や伝送遅延時間といったオーバーヘッドが大きいことが挙げられている. 一方のTree型はスタートアップ時間が短い一方で，上位ノードの離脱に伴う網の再構築が不可避であるためにメンテナンスオーバーヘッドが大きく, 単一の伝送経路に依存するために帯域の利用効率が悪いことが指摘されている．

Tree型, Mesh型, Multiple-Tree型のオーバレイコンテンツ配送技術について, GridG[7]を用いたシミュレーションとPlanetLabを用いた検証を行っている論文[8]では，狭帯域環境下においてMultiple-Tree型が転送レート, end-to-endの伝送遅延時間の2点において有効であると述べている. 特にネットワークが不安定なシナリオを想定した場合, Tree型とMultiple-Tree型の複合利用が広帯域ストリーミングを実現することができるであろうとまとめている．

サービスされているストリーミングの転送帯域に注目する. 既存の論文において運用や実験の際に利用されたストリーミング転送帯域を表に示す. 既存のオーバーレイネットワークを用いたコンテンツ配信機構は300-450Kbps, 大きくとも1Mbps以下の狭帯域ストリーミングを想定したものが多い. しかしいずれの論文も1Mbps以下でサービスを展開する理由については述べられていない．既存技術を用いた広帯域ストリーミングの実証実験を行い，転送能力の検証と広帯域化を実現するための要素を発見する必要がある．

検証実験

本章では前述した既存のオーバレイコンテンツ配送技術において，高品質コンテンツ転送時の実証実験を行い，課題を明らかにする．はじめに実証実験環境について説明を行う．その後，各方式における実証実験結果について述べる．

既存アルゴリズムの動作には，オーバレイ構築ソフトウェアであるMACEDONがサポートしている非構造化オーバレイアルゴリズムより，代表的なストリーミング形態であるTree型(Overcast), Hybrid型(Bullet), Multiple-Tree型(SplitStream)を用いた．MACEDON単体ではエミュレータを持たないため, Modelnetを用いたエミュレーションを行う．

評価環境としてMacPro Dual 2.66GHz Quad-Core Intel Xeon上で動作するVMware12ノードを用いた．うち2台をエミュレータとし，10台をシミュレータとした．評価ネットワーク環境を表に示す．inetトポロジジェネレータを用いた5,000ノードから構成されるトポロジを作成した．

既存のオーバレイコンテンツ配信網において，1Mbpsから8Mbpsのストリーミングを行った際の平均転送帯域幅について検証を行った．

最も利用可能帯域幅が広いトポロジCにおけるストリーミング受信ノード数210，420の際の実験結果を図に示す．

ユーザー数210において，Hybrid型は約8Mbps，Multiple-Tree型は約5Mbpsを記録した．Multiple-Treeだけではなく，Multiple-TreeとMesh型を取り入れたHybrid型が優位であることが分かった．そのため，オーバーレイネットワークにおける高品質化にはMesh網などを用いた欠損データの補完が重要であると言える．

一方，ユーザー数420においてはHybrid型の平均受信帯域幅に大きく開きが見られ，そのためMultiple-Treeとの差異が見られない，あるいは下回るユーザーが存在した．このことより，ユーザー数が増加し，各ユーザーが利用することができるネットワーク帯域幅が減少した環境ではHybrid型よりもMultiple-Treeが優位であると言える．この理由としては欠損したデータを補完するためのメッセージングが増大し，利用可能なネットワーク帯域幅を圧迫してしまうことが挙げられる．

平均受信帯域幅

アプローチ

既存技術の実証実験より，帯域利用効率の高いMultiple-Tree型機構に注目する．Multiple-Tree型機構によるコンテンツ配信を中心に行い，データの受信状況に応じてコンテンツ配信網とは別に発見されたノードからのデータ再送を行う．データ再送要求を目的として接続されるノードを冗長ノードと呼ぶ．

実証実験より，重複データの原因であるセッション数と実効帯域との関係に着目した．このセッション数の制御をセッション数コントロールと呼ぶ．本提案手法ではネットワーク環境の指標としてチャンクの欠損数を用い，その欠損数に応じてセッション数を増減させるアルゴリズムを導入する．セッション数コントロールは，受信ノードが観測したチャンクの欠損数をトリガとして動作する．チャンクの欠損とは，伝送遅延時間の揺らぎやパケットロスなどにより，コンテンツの再生時間に対し間に合わなかったものを指す．チャンクの重複についてはチャンクが到達するまでの遅延時間が未知数であり，計算コストが高いために考慮しない．観測されたチャンクの欠損数は蓄積され，予め静的に指定された閾値との比較がなされる．閾値との比較により，一定期間連続したチャンクの欠損が観測される，あるいは欠損が回復し安定した通信が観測された場合に，セッション数の変更が発生する．

実証実験より，オーバーレイネットワークにおける高品質ストリーミングの実現には欠損チャンクの冗長ノードからの補完手法が必要である．冗長ノードを探索する上で，要求するチャンクを対象となるノードが保持している可能性に着目する．Tree型トポロジを血縁関係図に見立てた冗長ノード探索手法について述べる．多くの既存技術ではノード探索手法としてランダム，あるいは近傍性によるものを採用している．Tree型トポロジでは，上位ノードでデータ欠損が発生した場合，下位ノードに波及するという特徴がある．近傍性を基に接続を行った場合，近隣に存在するノードが，同一の上位ノードを参照している可能性が高い．そのため，近隣に位置するノードに対して再送要求を送信した場合，同一の上位ノードを参照している環境下では，該当するチャンクを保持していない可能性が高く，近隣ノードからの再送は効果が期待できない．一方，Bulletではランダムによるノード選択が行われている．そのため，近傍性を基にしたノード探索に比べ，チャンクを保持している可能性は高くなる．しかしこの手法ではノード間のRTTが未知数であるため，データを補完するために要する時間が大きくなり，再生に間に合わないケースが存在する可能性がある．本研究ではノード探索によって発見されたノードと自ノードの関係について，Tree網においてどのレベルで分岐されたものであるかを示す血縁距離というものを用いる．この際，上位で分岐すればするほど血縁距離が遠いと定義する．血縁距離が遠いほど自ノードが保持していないチャンクを保持している可能性が高く，接続に望ましいノードする．上位ノードに由来する固有のIDを持つ．接続が行われる際，上位ノードは下位ノードに対し固定桁数のノードIDを付与する．ノードIDは上位ノードのノードIDの末尾に固定桁数の任意の数値を連結した形で保存される．血縁距離の計算は，ノードIDが上位ノードの履歴を反映していることを利用した比較により実現する．

プロトタイプ評価

評価環境として検証実験と同様の環境を用いた．比較したアルゴリズムは検証実験で転送能力の高かったHybrid型 (Bullet)，Multiple-Tree型 (SplitStream) である．inetトポロジジェネレータに寄って生成された5,000ノードのうち，ストリーミングに参加するノードはそれぞれ280ノードとした．最もネットワーク資源に余裕のあるトポロジCにおける全受信ノードの平均転送帯域幅を表に示す．1Mbpsから4Mbpsのストリーミングに関して，既存研究のうち最も伝送能力が高いHybrid型(Bullet)と同等の結果であることが確認できた．特に8Mbpsのストリーミング実行時においては，他方式より1Mbps以上多く伝送が実現された．また，最大で6.6Mbpsを記録したノードが存在する他，最小値で比較した場合であっても他方式よりも高い転送帯域幅であることが確認された．

評価より，本研究で提案したセッション数コントロール手法と，チャンクの保持可能性に着目した冗長ノード選択手法についての有用性が確認された．セッション数コントロールアルゴリズムは暫定的なものであるため，今後のアルゴリズム検討によって伝送能力を拡大することができるものと考えられる．

成果

高品質ストリーミング実行時の既存オーバーレイ配信技術を用いた実証実験の結果として海外論文への投稿を行っている．またプロトタイプ設計と実装に関して論文誌への投稿を行っている．

まとめ

本研究によりオーバーレイネットワークを用いたリアルタイムストリーミングの高品質化要素発見を行った．その結果各ユーザーが利用するネットワーク帯域幅の有効利用が重要な要素であることが分かった．また高品質化を達成するためには欠損データを他ノードに問い合せることにより補完することが不可欠であることが分かった．これらを基にプロトタイプ設計とその実装を行った．プロトタイプ実装の評価より，既存技術に対する優位性を確認することができた．本研究の実現により個人によるコンテンツ配信の高品質化を実現することができる．

今後の展開

光ファイバの一般化が進む一方で，数多く存在するDSL，WiMAXやHSDPAの登場などによりユーザーの存在するインフラの多様化が起きている．その結果利用可能な帯域幅や特性もまた多様化している．本研究では広帯域ネットワークを想定した，高品質ストリーミングの実現に主眼を置いてきた．しかし高品質化が進むにつれ，こうしたネットワークの多様化の問題が大きくなってくる．そのため，ユーザーの帯域間格差を考慮したシステムが求められる．本研究のアルゴリズムを応用し，幅広いユーザー環境に対応したコンテンツ転送システムを実現することが求められる．

参考文献

[1]. S. Spoto, R. Gaeta, M. Grangetto, and M. Sereno, “Analysis of pplive through active and passive measurements,” IPDPS ’09: Proceedings of the 2009 IEEE International Symposium on Parallel& Distributed Processing, pp.1–7, Washington, DC, USA, IEEE Computer Society, 2009.

[2]. I. Cognitive Research Laboratories, “Keyholetv &　keyholevideo www page,” 2009.

[3]. F.Wangand, and J.LiuX.Xiong, “mtreebone: A hybrid tree/mesh overlay for application-layer live video multicast,” Proc. IEEE ICDCS 2007, p.49, June 2007.

[4]. K. Dejan, B. Ryan, K. Charles, V. Erik, A.J. W., S.A. C., and V. Amin, “Maintaining high bandwidth under dynamic network conditions,” ATEC ’05: Proceedings of the annual conference on USENIX Annual Technical Conference, pp.14–14, Berkeley, CA, USA, USENIX Association, 2005.

[5]. K. Dejan, S.A. C., V. Amin, B. Ryan, K. Charles, A.J. W., A. Jeannie, R. Adolfo, and V. Erik, “High-bandwidth data dissemination for large-scale distributed systems,” ACM Trans. Comput. Syst., vol.26, no.1, pp.1–61, 2008.

[6]. J.LiuB.Li, H.Zhang, and S.G.RAO, “Opportunities and challenges of peer-to-peer internet video broadcast,” Proceedings of the IEEE, vol.96, no.1, pp.11– 24, Jan. 2008.

[7]. D.Lu, and P.Dinda, “Gridg: Generating realistic computational grids,” ACM Sigmetrics Performance Evaluation Review, vol.30, no.4, pp.33–40, March 2003.

[8]. J. Seibert, D. Zage, S. Fahmy, and C. Nita-Rotaru, “Experimental comparison of peer-to-peer streaming overlays: An application perspective,” IEEE Conference on Local Computer Networks (LCN), pp.20–27, Washington, DC, USA, IEEE Computer Society, Oct. 2008.

[9]. X.ZhangB.Li, and T.P.YumJ.Liu, “Coolstreaming/ donet: A data-driven overlay network for efficient live media streaming,” IEEE INFOCOM 2005, pp.2102–2111, March 2005.

[10]. Li B., Qu Y., Keung Y., Xie S., Lin C., Liu J., and Zhang X., “Inside the new coolstreaming: Principles, measurements and performance implications,” INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, pp.1031–1039, 2008.

[11]. C.ZhangJin, D. Deng, S. Yang, Q. Yuan, and Z. YinH, “Anysee: Multicast-based peer-to-peer media streaming service system,” IEEE Asia-Pacific Conference on Communications, pp.274–278, Oct. 2005.

[12]. V. PaiV. Sambamurthy, A. E. MohrK.Kumar, and K. Tamilmani, “Chainsaw:eliminating trees from overlay multicast,” IPTPS 2005, pp.127–140, Feb. 2005.

[13]. N.Magharei, and Y.GuoR.Rejaie, “Mesh or multipletree: A comparative study of live p2p streaming approaches,” IEEE INFOCOM 2007, pp.1424–1432, May 2007.

[14]. J. Seibert, D. Zage, S. Fahmy, and C. Nita-Rotaru, “Experimental comparison of peer-to-peer streaming overlays: An application perspective,” IEEE Conference on Local Computer Networks (LCN), pp.20–27, Washington, DC, USA, IEEE Computer Society, Oct. 2008.

[15]. A. Sachin, S.J. Pal, M. Aditya, B. Pierpaolo, and G. Bernd, “Performance of p2p live video streaming systems on a controlled test-bed,” TridentCom ’08: Proceedings of the 4th International Conference on Testbeds and research infrastructures for the development of networks & communities, pp.1– 10, ICST, Brussels, Belgium, Belgium, ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2008.