再生頻度に応じたファイル配置と P2P システムのジッタ性能評価
2010SE193 澁谷 有紀

2010SE196 清水 里美

指導教員： 河野 浩之

1

はじめに

Skype や Winny，Napster などの P2P 型を採用するメリットは従来のサーバー・クライアント型に比べて特定の端末に負荷がかからないため高スケーラビリティであり，サーバーが落ちても通信可能なため障害耐性がある．また，低コストを実現し匿名性もある．
しかし，P2P 型ストリーミングシステムを利用するにあたって，再生途切れによるユーザの待ち時間が発生したり遅延の揺れが発生したりなどの問題が挙げられる．この問題が頻繁に起こることによりユーザはストレスを感じるた
め，途中で再生を中断してしまう可能性があり，P2P ストリーミングの品質低下に繋がる．
そこで，本研究では動画の再生頻度に応じた P2P ストリーミングシステムの QoS (Quality of Service) について評価する．これまで P2P ストリーミングの品質を向上するため，様々な研究が成されたが再生頻度を考慮した研究はまだ行われていない．そのため本研究では人気動画，不人気動画をどのピアに置くかによって効率よく動画を再生しジッタを減らすのかを考慮する．ここで動画の人気度は Zipf 分布に従い動画を選択することとする．通信はUDP で行う．
第 2 章ではこれまで行われていた P2P ストリーミングシステムについての研究を著者，技術と共に紹介する．第 3章では P2P ストリーミングを行う際，効率よく動画を再生するためにジッタを減らす手法を提案する．その際，動画の人気評価をするための Zipf 分布について説明する．第 4章では NS2 による実験のパラメータやプログラムを説明する．第 5 章では実験の結果とその考察を行う．第 6 章ではこれまでのまとめを示す．

2

P2P ストリーミングシステム

本章では 2.1 節で P2P システムの特徴やトポロジーの種類などを説明し，2.2 節では関連研究として不人気動
画視聴ピアの帯域を有効に活用する PEC (Popularity

デックスサーバーはどのピアがどんな情報を持っているのか集中管理しているため，データの所在検索に適している．スーパーノード型は Skype が使用している形態で，3 つの処理能力の高いノードと下部の一般のノードに別れている．そして一般ノードは検索情報などを保持しない
ためデータの検索は処理能力の高いノードが行う．

2.2

PEC

これより，動画を円滑に再生するための手法 PEC について説明する．PEC は再生頻度が少ない不人気動画に対して送信帯域を有効活用した手法である．図 1 の矢印
はセグメント送信を表しており，FIFO (First In First Out)
方式ではよく再生される人気動画に対して不人気動画の送信帯域が有効活用されない．不人気動画を再生した場合には人気動画がキャッシュから溢れてしまい，再生頻度が少ない不人気動画がキャッシュに残ってしまうた
め，効率が悪い．人気動画を視聴しているピア A，B，Cは人気動画のセグメントを持っているため a，b，c，d のように他ピアに送信出来る．ただし e は他ピアに送信出来ない．図 1 に示す PEC は不人気動画を視聴している D のピアもキャッシュに人気動画を持つため配信サーバーの負担を低減することに成功している．A，B，C の人気動画を視聴しているピアだけでなく不人気動画を視聴している D も送信出来るため，a，b，c，d，e のようにそれぞれ他ピアに人気動画のセグメントを送信することができ，効率が良い．また，表 1 に先行研究の技術とその内容を示す.
表 1 先行研究の技術
技術名

技術内容

再生途切れ
時間短縮方式

次に再生する動画を予測し，それを予めバッファリングすることで再生開始までの待ち時間を減らす[2]．

V-Chaining方式

VoD システムでピア間の遅れを評価し，遅れの中で平均の遅れを最小にし評価する．最小のジッタの中で最適経

Based Efficient Caching) を説明する[2]．

路を選ぶ[1]．

2.1

P2P システム

ここでは P2P 型の通信をする際に用いられるネットワー
クトポロジーについてピュア型，ハイブリッド型，スーパーノ ー ド 型 を そ れ ぞ れ 説 明 す る ． ピ ュ ア 型 は Winny ，Gnutella などに使用されている形態で，検索・転送を P2Pで行い，検索は隣接ピアを経由する．中心のピアはいな
い．ハイブリッド型は Napster が使用している形態で，インBIS 方式

P2P ストリーミング環境で再生途切れを短縮するため，ピースの希少性やピースの緊急性を考慮[3]．

レアレストファスト方式

希少なピースを優先的に受信する[3]．BitTorrent に使われている．

のため，不人気動画はできるだけそれぞれのピアからホップ数の少ない中心にある IP ネットワーク配置する．これによって，たとえ不人気動画が再生された場合でも最小限のジッタにおさえることができる．

3.2

ジッタ

ジッタとは信号の時間的なズレや揺らぎであり，パケットの伝送時間が一定しない状況を表す．図 3 にパケットジッタの図を示す．図 3 より，上部のパケットの送信時間を，， ， また，受信側の到着時間をそれぞれ
図1

3

PEC におけるセグメント送信者の例

提案内容

本章では 3.1 節でネットワークトポロジーの提案，3.2 節
ではジッタの説明をし，また 3.3 節では動画の人気度の指標である Zipf 分布について説明する．

3.1

再生頻度によるファイル配置提案

図2，，とおき，パケットの送信間隔と受信間隔は任意の自然数 nを用いて式(1)，(2)のように表す．
(1)(2)
送信間隔は一定であるため，式(1)は常に一定の値をとるが，下部の受信側のパケットの到着間隔はそれぞれ異なるため，式(2)の値は一定ではない．この受信間隔と送信間隔の差がジッタである．よってジッタは式(3)で表される．
(3)
このジッタはネットワークの輻輳や不適切なキューイングなどの原因となり，ノイズや音とび，音質・画質の劣化などを発生させる．

動画の人気度に応じたネットワークの提案

本研究では再生頻度を考慮した P2P ストリーミングシス
テムのジッタ評価を行う．図 2 に提案内容のネットワーク図を示す．なお，IP ネットワークのトポロジーはピュア型とする．
図 2 より，シミュレーションにおけるネットワークは上層部に仮想的なオーバーレイ・ネットワーク，下に IP ネットワークが存在している．仮想的なオーバーレイ・ネットワークにおいてホップ数が同じピア間の場合でも，IP ネットワーク層ではホップ数が大きく異なってしまう場合がある．つまり，仮想的なオーバーレイ・ネットワークで同じホップ数でも，ジッタが異なってくるということがいえる．
そこで，本研究では物理回線での IP ネットワーク層におけるホップ数を考慮することでジッタを減らしていくことを考える．図 2 のように各 IP ネットワークには再生される確率の高い人気動画をそれぞれに配置し，ホップ数を減らすことで効率のよい動画再生をできるようにする．逆に，再生される確率の低い不人気動画については配置する数を少なくする．しかし，これでは不人気動画を再生した場合，急激にジッタが増加してしまうことが考えられる．そ

図3

3.3

パケットジッタ再生頻度に成り立つ Zipf 則

Zipf 分布とは，出現頻度が k 番目に大きい要素が全体に占める割合が 1/k に比例するという経験則である．このZipf 分布のグラフについて，縦軸を頻度，横軸を順位とし，
図 4 に示す．この法則は自然現象や社会現象などで成立することが確認されており，Web のリンク数や単語の使用回数，都市の大きさ，企業の規模，図書館での書籍の人気度などを表すのに利用されている．これらは，順位に対し値が反比例しているため，順位の高いわずかな要素が極度に高い値を示し，大多数の要素が極めて低い値を示す．つまり，Web のリンク数を例にとると，誰もがリンクするサイトはごくわずかで，多くのサイトは誰にもリンクされないということがいえる．
本研究では動画の再生回数が Zipf 分布に従うものとする．Web のリンク数と同様に誰もが再生する動画はごくわずかで，多くの動画はほとんど再生されないことがいえ

Step0:シミュレーターの宣言と出力ファイルの設定るため，提案内容の動画の人気度を考慮したネットワークは，従来よりも効率のよい配信が可能になることが予測される．

Step1:Node と Link の設置
Step2:Agent の設置
Step3:Application の設置
Step4:シミュレーションのタイムスケジュールを設定
Step5:設定終了を宣言

0.30.25
頻度0.2

表 2 シミュレーターの比較

0.15

シミュレーター

特徴0.1

p2psim・DHT を評価することが目的のシミュ
レーター
・ネットワークへのノードの参加・離脱を制御することができる

peersim・数百万のノード規模のネットワークを評価することができる
・実装された DHT のアルゴリズムなど

0.05
0
10 20 30 40 50 60 70 80 90 100
順位
図4

Zipf 分布のグラフはなく，個別に用意する必要がある

1/ k s(4)

・各種通信システムを評価するためのシミュレーター

ただし N は全要素の数，k は順位を示し，s は常に s=1とする．

・ネットワークが極めて詳細なため，大規模性を主張したい P2P システムには不向き

NS2f ( k ; s, N )  N

1 / nsn 1

4

P2P ストリーミングのシミュレーション

本章では各シミュレーターの特徴と，それを用いた実験結果を示す．そして実験のために適切なパラメータを設定し，プログラムの紹介を行う．実験は既存の再生頻度を考慮していない手法と，本研究の提案手法を比較し，結果を示す．ジッタの定義を式(3)とし，再生頻度に関しては式(4)に従うこととする．

4.1

シミュレーターの選択

表 2 よりそれぞれのシミュレーターの比較を行い，NS2(Network Simulator Version2) を使って実験を行う[4]．
NS2 は P2P ストリーミングシステムの評価を行うにあたって代表的なものであり，本研究では大規模性を主張していないため，NS2 が最適なシミュレーターだと考える．また，メジャーなシミュレーターであり，フリーソフトで簡単に手に入れられるのが特徴である．

4.2

パラメータ設定と NS2 のプログラム

これより表 3 のパラメータを用いて実験を行う．それぞれの帯域幅については，バックグラウンドに様々な通信が行われていることを考慮し，小さな値を設定する．また，通信方式は UDP で行っているため，ジッタの評価ができる程度のパケットが到着するように，それぞれのキューサイズを表 3 の値に設定する．
次に NS2 でプログラムを組むためのシナリオファイル作成の手順を以下のように考える．

MACEDON
Mace・DHT 等のオーバーレイ・ネットワー
ク開発を容易にするフレームワーク・共通の基盤を用いることで，複数の実装を比較評価が可能

表 3 シミュレーションパラメータ
パラメータ値

ピア数

20

ルータ数

1LAN 数3

ソースノードとルータ間の帯域幅

1Mbps

ルータ間の帯域幅

2Mbps

ソースノードとルータ間の3500pkt

キューサイズルータ間のキューサイズ

4000pkt

ルータ間の転送遅延30~300ms

ソースノードとルータ間の転送遅延

30ms

動画の長さ

300sec

動画のパケットサイズ

1000pkt

シミュレーション時間

1200secNS2 によるシミュレーション結果

5

これより NS2 によるシミュレーション結果を示す．5.1 節
では NAM の出力結果を示し，5.2 節では提案手法のファイル配置で不人気動画を視聴した際のジッタとそうでないもののファイル配置で不人気動画を視聴した際のジッタを比較する．

5.1

NAM の出力結果

本節では NAM の出力結果を図 5 に示す．LAN1，LAN2，LAN3 はそれぞれヨーロッパ，日本，アメリカを想定し，転送遅延は LAN1，AN2 間が 300ms，LAN2，LAN3 間は 200ms とする．リンクの長さは遅延時間に影響するため，それぞれの LAN の間は Link の長さが長くなっていることが分かる．

本節ではそれぞれのジッタをグラフに表す．図 6，7 にはn0 が不人気動画を視聴した際のジッタを示す．図 6 は不人気動画ファイルをネットワークの端に配置した際のジッタであり，図 7 には我々の提案手法でファイル配置を行った際のジッタを示す．
実験結果より，人気動画はどちらのシステムもそれぞれのピアに配置してあるため，n0 が人気動画を視聴した場合近くのピアから動画を送信でき，どちらも揺れの最大は0.00832 秒となった．一方，図 6，7 の場合，n0 が不人気動画を視聴しているため二つのグラフが大きく違っていることが分かる．不人気動画をネットワークの端に配置してあるシステムでは揺れの最大は 0.0216 秒となり，ジッタは約 2.6 倍に増加したが，それに比べて我々の提案手法で実行した場合は，人気動画を視聴した際と変わらず小さかった．よって我々の提案手法は P2P ストリーミングのQoS が向上していることが分かる．

6

まとめ

本研究では P2P ストリーミングを行う際に発生するジッタを減らすために再生頻度に応じたファイル配置を提案した．NS2 を用いて，再生頻度を考慮したファイル配置の

図5

5.2

NAM の出力結果

ジッタ性能評価システムと，再生頻度を考慮せずに不人気動画のファイルをネットワークの端に置いたシステムとのジッタの比較を行った．その結果，n0 が不人気動画視聴の際，前者の方がジッタは少なかった．人気動画を視聴した際はそれぞれのピアからのホップ数が少ないため，ジッタは両者ともあまり変わらなかった．我々の提案手法は，不人気動
画ファイルをネットワークの端に配置したシステムよりも，ジッタを最大で約 38.5%改善できた．よって不人気動画はそれぞれのピアからできるだけホップ数が少ない場所に設置した方が効率の良いファイル配置だといえる．

参考文献

図 6 ネットワークの端から通信した際のジッタ[1] Hareesh K.. and Manjaiah D.H., “Quality of Servicein Peer to Peer Video on demand System Using V
Chaining Mechanism, ” International Journal ofComputer and Information Technology, Vol.02,
No.01, pp.1-9 (2013).
[2] 池田匡視, 岡崎直宣, 朴美娘, “P2P を用いたビデ
オストリーミング配信システムの効率化に関する検討,” マルチメディア, 分散, 協調とモバイル(DICOMO2011)シンポジウム, pp.99-106 (2011).
[3] 坂下卓, 義久智樹, 原隆浩, 西尾章治郎, “P2P ス
トリーミング環境における再生途切れ時間短縮方式,”
情報処理学会論文誌, Vol.52, No.3, pp.1045-1054(2011).
[4] 銭飛, “NS2 によるネットワークシミュレーション,” 森
北出版株式会社(2006).

図7

提案手法のシステムで生じたジッタ