Distributed Systems Lab
 分散システム学研究室

このページについて

2016年度から2019年度までの4年間,科学研究費補助金の支援を受けてまとまった研究を行いました. 研究種目は基盤研究(B)で,研究課題名は 「P2P型ビデオストリーミング基盤のための理論的性能保証手法の研究」です. オフィシャルな情報については こちら をご参照ください.助成期間中,備品の購入や出張旅費などについて気にすることなく研究に専念できたので,大変助かりました. どうもありがとうございました. 最終成果報告書の原稿はここからご覧いただけますが,このページでは,1) この研究で何をしたかったのか,2) どういうアプローチを取ったのか,3) 具体的な成果は何か, 4) 今後の方向性はどうなのか,などについてわかりやすく説明したいと思います. 想定する読者のレベルは情報系の学部生です.

背景(何がしたかったのか)

申請当時,ビデオストリーミングサービスが急速に普及し始めていました. Amazonプライム・ビデオとNetflixが日本国内でVoD(Video on Demand)サービスを開始したのがちょうど2015年の秋です. それまでもYouTubeやUstreamなどは普通に使われていましたし (2011年の東日本大震災のときには,一時的にではありますが,YouTubeやUstreamを使ってニュース番組のリアルタイムなネット配信がなされていました), 論文レベルでは,BitTorrentをベースにしたBiToSなどのVoDや アプリケーションレベルマルチキャストのような配信手法も存在していました. 一般にP2Pはクライアント/サーバ型と対比的に説明されることが多く,サーバ型に比べて信頼性や安定性などの点で問題があるものの, 参加ノードのリソースを有効に利用することで,サーバの容量不足などを解決する決定打になると考えられていました. ただし私には,それらの立ち位置が少しupper bound寄りになっているのではないかという気がしていました. すなわち,この方法を使えばこのくらいの性能が出るというポジティブな主張に終始しており,それが理論的な限界性能にどのくらい近いのか(つまりlower boundに関する議論)は, あまり考慮されていなかったように思います. そもそもビデオストリーミングの性能のlower boundをどのように評価すべきなのかすら,当時の私にはよくわかりませんでした. そこでこの点を明らかにし,きちんと理解したいと思ったのがそもそもの動機です. 基盤研究の審査では研究業績が重視されていたため 課題と業績をうまく結びつける必要があったのですが, 私の業績に「ビデオストリーミングの理論的な性能保証」という補助線を入れるとすっきりと説明できたという経緯もあります.

アプローチは?

基本的に,グラフ理論に関する知識や,アルゴリズムの設計・解析を通して身につけた手法を使いました. これまでに取り組んできた研究で得られた結果(正確には,時間をかけて正しい証明を導き出す力)は役に立っていると思います. 導き出された理論的な結果を裏付けるため,評価用のテストベッドを構築し, その上で実験を重ねていくことも当初から想定していました (ただし我々を取り巻く環境はここ数年で大きく変わり,研究室内にオンプレミスサーバを用意して実験するよりも AWSやGCPなどをうまく使った方が,結果的に網羅的で多様な検証ができるようになりました),

研究成果

マルチツリー型ビデオ配信

ビデオストリームには動画品質に応じたビットレートがあり(例えば4K動画の場合,68Mbps以上が推奨値とされる), 各ノードのアップロード容量も一定値に制限されています(フレッツ光などでは回線ごとに1Gbpsまで). したがってビデオストリームをP2P技術を使って普通に配信した場合, 各ノードが持つことのできる子ノードの数(出次数)が制限されることになり, 指定された視聴ノード集合にビデオを配信するためには, 次数制約付き全域木(もしくは次数制約付きシュタイナ木)を構成することになるだろうなということはすぐにわかります (WebRTCなどには環境に合わせたビットレートの自動調整機能があるため, 次数制約は実際にはそれほど強くない). また評価のメトリックとしては,視聴ノードまでの転送回数,すなわち配信木の深さを考えるのが適切だと考えました. なぜならばP2Pに特徴的な性質はノードによる転送であり, 転送回数の増加はそれだけでビデオの質の低下につながる可能性を生むからです.
ただしそれだけだと発展性がないので,ここではSplitstreamというシステムで提案された, 与えられたビデオストリームを複数のサブストリームに分割して配信するというモデルを考えることにしました (各ノードの容量制約の範囲内で,サブストリームごと独立に全域木を構成する問題を考えることになる. サブストリームへの分割は,Multiple Description Codingなどを使えば なんとか実現できそうだし...). このモデルのもとで最初に考えたのは次のような問題です: a個のサブストリームに分割されたビデオストリームをn台のノードに配信したいとする. 各ノードのアップロード容量が均一であると仮定したとき, 各サブストリームを高々1回の転送ですべてのノードに配信するのに必要十分なアップロード容量を aとnの関数で表現せよ. 結果はここで発表されています. 新規性のある結果として,aとnの組み合わせによっては,a個のサブストリームを同時に送信できるだけの容量では足りなくて, 一定の追加分が必要十分であることが明らかになりました. サーバ型からP2P型に1ホップ分踏み出す際に, 配信性能を保つためには何が必要なのかが少し分かった気がしました.

議論の一般化とモデルの拡張

本研究課題では,上記の結果を出発点として様々な拡張を行いました. 拡張の方向としては,

  1. 配信時に許容される転送回数を1回から複数回に増やした場合,
  2. サーバのアップロード容量をクラウドCDNなどを使って増強できると仮定した場合,
  3. 単一のストリームだけでなく,いろんなビットレートのビデオストリームを同時並行的に配信する場合
などを考えました. また上記のようなマルチツリー型配信モデル以外にも,ストリーム配信をチャンク単位の転送として捉え, 与えられたチャンク列を最短時間でブロードキャストする問題や, 外的要因によってリンクの容量が一時的に減少する状況, 視聴要求が一気に到着するフラッシュクラウドと呼ばれる状況についても考えています. かなり細かい話になるので,詳細に興味のある人は こちら をご覧ください(説明文はP2P video streamingボタンを押した先にあります). また最終年度は,当初の計画通り少し実装寄りにシフトして,クラウドゲームやアドホックネットワーク上のビデオ配信など, 通常のビデオ配信から派生するいくつかの状況について具体的に検討を行いました.
DBLPなどでも参照できますが,本研究課題に関連する 発表論文を以下にまとめておきます(数的には問題ないし,質的にも十分面白い結果たちだと思う). 国際会議論文のいくつかは,拡張版をジャーナルに投稿中です.

発表論文のリスト(本研究課題に関連するもの)

ジャーナル論文

  1. Shogo Inoue, Satoshi Fujita: Collaborative Illustrator with Android Tablets Communicating through WebRTC. IEICE Transactions on Information and Systems, 103-D(12): ***-*** (2020).
  2. Tsuyoshi Yoshihara, Satoshi Fujita: Towards Fog-Assisted Virtual Reality MMOG with Ultra Low Latency. International Journal of Computer Networks & Communications (IJCNC), **(**): ***-*** (2020).
  3. Hironori Ando, Satoshi Fujita: Tight Bounds on the Upload Capacity to Enable Two-Hop Delivery in Peer-to-Peer Video Streaming Systems. International Journal of Foundations of Computer Science, 31(3): 341-354 (2020).
  4. Satoshi Fujita: Cloud-Assisted Peer-to-Peer Video Streaming with Minimum Latency. IEICE Transactions on Information and Systems, 102-D(2): 239-246 (2019). OPEN ACCESS
  5. Satoshi Fujita: Flash Crowd Absorber for P2P Video Streaming. IEICE Transactions on Information and Systems, 102-D(2): 261-268 (2019). OPEN ACCESS
  6. Satoshi Fujita: Multi-Tree-Based Peer-to-Peer Video Streaming with a Guaranteed Latency. IEICE Transactions on Information and Systems, 102-D(9): 1707-1714 (2019). OPEN ACCESS
  7. Satoshi Fujita: Peer-to-Peer Video Streaming of Non-Uniform Bitrate with Guaranteed Delivery Hops. IEICE Transactions on Information and Systems, 102-D(11): 2176-2183 (2019). OPEN ACCESS
  8. Satoshi Fujita: Resilient Tree-Based Video Streaming with a Guaranteed Latency. Journal of Interconnection Networks 19(4): 1950009:1-1950009:20 (2019).OPEN ACCESS
  9. Satoshi Fujita: Three-Tier Delaunay Network as a Topology for Peer-to-Peer Overlay. Journal of Interconnection Networks 19(4): 1950010:1-1950010:16 (2019).OPEN ACCESS
  10. Naoki Takeuchi, Satoshi Fujita: Semi-Deterministic Construction of Scale-Free Networks with Designated Parameters. Journal of Interconnection Networks 18(1): 1850001:1-1850001:18 (2018).OPEN ACCESS
  11. Satoshi Fujita: Broadcasting a Stream of Chunks in Heterogeneous Networks with a Short Maximum Broadcast Time. Journal of Interconnection Networks 18(2-3): 1850007:1-1850007:16 (2018).OPEN ACCESS
  12. Bahaa Aldeen Alghazawy, Satoshi Fujita: Low Cost Cloud-Assisted Peer to Peer Live Streaming. KSII Transactions on Internet and Information Systems, 10(4): 1732-1750 (2016). OPEN ACCESS
国際会議(拡張版がジャーナル論文になったものを除く)
  1. Masayuki Kawakami, Satoshi Fujita: Live Streaming over Wi-Fi Direct Multi-Groups. CANDAR Workshops 2019: 221-227.
  2. Yuta Yamada, Satoshi Fujita: Load Balancing in P2P Video Streaming Systems with Service Differentiation. CANDAR Workshops 2018: 539-543.
  3. Takuya Shoji, Satoshi Fujita: Tight Lower Bounds on the Maximum Number of Hops in P2P Video Streaming through Multiple Spanning Trees. CANDAR 2017: 30-37.
  4. Satoshi Fujita: Reliability Calculation of P2P Streaming Systems with Bottleneck Links. IPDPS Workshops 2017: 1238-1244.
  5. Shuji Jinbo, Bahaa Aldeen Alghazawy, Satoshi Fujita: Batch-based flash crowd relaxation in cloud-assisted P2P live streaming. SNPD 2017: 95-100.
  6. Martin Thodi, Satoshi Fujita: Collaborative Development Environment in Peer-to-Peer Networks. CANDAR 2016: 586-589.

今後の展望

本研究課題の実施を通して,マルチツリー型配信におけるノードのアップロード容量と転送ホップ数の関係については, ほぼ調べ尽くすことができたと考えています. ただしモデルとしては少し単純化されすぎているところもあり(前述のように,現実にはビットレートは固定されないことが多いです), 実システムに適用するのはこのままでは難しいかもしれません. そうは言ってもP2P-assisted CDNという枠組み自体は,ホットなトピックの一つですし(中国のLiveSkyやAkamaiのNetSessionなどはすでにそうです), 日本国内でもテレビ放送のネット同時配信がもうすぐ始まるので, 今後ピア支援型配信は当たり前のように使われるはずで, そのような配信における転送回数の抑制が問題になったときなどに, 本研究課題の成果は生きてくると考えています.自身の次の課題としては, クラウドゲームにおける低遅延化の問題や XRアプリのための情報共有プラットフォームに興味を持っています. すなわち,ビデオ配信のように与えられたビデオを一方向に配信するのでなく, ユーザとのインタラクションによって動的に生成されるビデオストリームを 低遅延で配信する問題へとシフトしていくつもりです (まずは実証的にアプローチし,課題を特定した上で再びモデル上の議論に戻ってくる予定).

↑ PAGE TOP