Microsoft PowerPoint _junki.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint _junki.pptx"

こうしろうひめい
5 years ago
Views:

1 地理情報を考慮した P2P ストリーミング Optimized P2P Streaming with Geographical Information 後藤研究室修士 2 年 5109B021 9 大村淳己関連発表大村淳己, 高田和也, 後藤滋樹, Location Based Clusteringを用いたP2P ストリーミング, 電子情報通信学会技術研究報告, vol. 110, no. 373, IN , 124 pp.37 42, 2011 年 1 月. 1

2 1. 研究背景 2. 研究目的 3. 提案内容 Location Based Clustering 目次ピース選択アルゴリズム Earliest First 4. 実験 1 2 クラスタリング実験ピース選択アルゴリズム改造実験 3 クラスタ内ダウンロード実験 5. まとめ 2

3 研究背景高画質動画の数が増し, ユーザの動画に対する需要も高まっている. 限られたリソースの中で如何にして安定した配信が行えるかが長年の技術的な課題となっている. 従来のクライアントサーバモデルの配信ではスケーラビリティに限界があり, 加えて非常にコストが高い. 3

4 目的研究目的 1 地理情報に基づいた P2P ネットワークを構成することでトランジットコストを減らす. 2 ストリーミングシステムに適したアルゴリズムをBitTorrentに適用することにより,P2Pを利用したストリーミングシステムを実現し, 実ネットワークであるPlanetLab 上で評価する. 成果物 BitTorrentを利用したロケーションベースの高画質ストリーミングシステム. 4

5 提案内容 Location Based Clustering ピアの地理情報 ( 緯度経度 ) を用いてクラスタリングを行い, P2P 通信をそれぞれのクラスタ内に閉じる. ピア間通信におけるトランジットコスト減少. 近接ピア選択による通信速度の向上. Intelligent Tracker Leecher Original Seeder Normal Seeder C1 C2 CN 5

6 BitTorrent 2001 年に開発された大容量コンテンツ配信向けソフトウェア及びプロトコル. 最も普及している P2Pの一つ. トラッカーから受け取ったピアリストから接続先を決め, ピースと呼ばれる小さな単位で相互通信する. 用語トラッカーピアやピアの持つファイル情報の管理リーチャダウンロード中のピアシーダダウンロードが完了したピア Tracker BitTorrent Network 6

7 既存 BitTorrentシステム通常のトラッカー通常のトラッカーは単純なピア情報の管理を行うだけ. Request ピア情報登録処理 Normal Tracker User P2Pピア DB ピアリスト渡し処理 xx.xx.xxx.xxx xx.xxx.xx.xxx xx.x.xxx.xxx 7

8 提案 BitTorrentシステムインテリジェントトラッカート Request ピア情報登録処理地理情報取得処理クラスタリング処理 Intelligent Tracker User P2Pピア DB クラスタリング結果 DB xx.xx.xxx.xxx xx.xxx.xx.xxx xx.x.xxx.xxx ピアリスト渡し処理 8

9 提案内容ピース選択アルゴリズムの改造 BitTorrentのピース選択アルゴリズムをストリーミング配信に適した形のEarliest First に変更する. 既存手法採用手法 Rarest First Earliest First ピースの取得が再生と無関係ピースの取得が再生と相関関係ユーザの待ち時間大ユーザの待ち時間小 9

10 実験一覧実験 1: クラスタリング実験クラスタリング手法の概要とその評価を行う. 実験 2: ピース選択アルゴリズム改造実験ピース選択アルゴリズムを実際に動かし評価する. 実験 3: クラスタ内ダウンロード実験実験 1,2 で得られた結果を元に,PlanetLab 上で評価を行う. 10

11 PlanetLab PlanetLabはインターネット上に展開する大規模テストベッド.2010 年 11 月の時点で世界 519 拠点 1138 ノードが稼働中. 問題点一部地域にノードが集まっている. 生ネットワークゆえにノードが不安定. 大学機関のネットワーク経由がほとんど. PlanetLab ノードの分布図 PlanetLab ノードの参加国 4% 4% 29% 21% 42% US EU JP PL その他 11

12 目的実験 1 : クラスタリング実験ノードの地理情報に基づいたクラスタリング手法について検いて検討する. 今回利用したPlanetLabノード数は618. 実験内容ノード数増減時のクラスタ数の変化について 12

13 実験 1-1 : ノード数増減時のクラスタ数の変化についてオリジナルシーダのみ *(n=30, k=4), 全ノード参加時 (n=618, k=15) を結んだ線形関数を利用する. PAM (Partition around medoids) をクラスタリングアルゴリズムとして採用. クラスタタ数参加ノード数に応じたクラスタ数の変化参加ノード * コンテンツ配布者側が用意するシーダ 13

14 実験 2: ピース選択アルゴリズム改造実験比較手法既存手法全ピースに Rarest First 適用.(( 通常の BT アルゴリズム ) 提案手法 (1) 最初の 100ピースを Earliest First, 残りのピースは Rarest First. 提案手法 (2) 全ピースに Earliest First 適用. 14

15 目的実験 2: ピース選択アルゴリズム改造実験ピース選択アルゴリズムを改造し,PlanetLab 上でダウンロード実験を行い, ストリーミング配信に適していることを示す. 実験内容 CentOS 5.5 x86_64 LiveCD (694.4M) をストリーミングコンテンツと見立ててダウンロード.1ピース256KB,2Mbps 配信とすると1ピースの再生時間は1 秒, 計 50 分弱の動画となる. CentOSを選んだ理由はシーダが豊富で効率的に実験できるため. 評価項目ダウンロード速度の比較累計待ち時間の比較パラメタ値コンテンツサイズ 694.4M CentOS 5.5 x86_64 LiveCD 配信ビットレート 2Mbps ピースサイズ 256KB 15

4500 4000 3500 実験 2 1: ピース選択アルゴリズム改造実験ダウンロード速度の比較ダウウンロード速速度 (KB/s) 3000 2500 2000 1500 1000 提案手法

16 実験 2 1: ピース選択アルゴリズム改造実験ダウンロード速度の比較ダウウンロード速速度 (KB/s) 提案手法 (2) がもっとも低速 => しかし再生に間に合っているなら問題ない 500 2Mbps 経過時間 (sec) 16

実験 2 1: ピース選択アルゴリズム改造実験経過時間と待ち時間の関係取得ピースが動画再生と無関係のためバッ waiting

バッファ時間に初期ピースをダウンロードでき再生開始時の初期バッファリング時間 try :

100 50 0 提案手法 (1) よりさらに削減できている buffer=10sec, try=3 buffer=30sec,

17 実験 2 1: ピース選択アルゴリズム改造実験経過時間と待ち時間の関係取得ピースが動画再生と無関係のためバッ waiting time : ファによらず待ち時間は改善していないコンテンツを再生してからの待ち時間,buffer 時間は含まない buffer : バッファ時間に初期ピースをダウンロードでき再生開始時の初期バッファリング時間 try : るため待ち時間を大幅に削減できている再生ピースが存在しない時の再検索回数累計計待ち時間 (sec) 提案手法 (1) よりさらに削減できている buffer=10sec, try=3 buffer=30sec, try= 経過時間 (sec) 経過時間 (sec) 17

18 実験内容実験 3: クラスタ内ダウンロード実験概要 3 1: 全ノード参加時 ( ノード数 618, クラスタ数 15) アジア地区 (class 15) 評価項目アメリカ東海岸地区 (class 3) 南米地区 (class 2) 各クラスタの平均通信速度各クラスタの累計待ち時間の分布 18

19 実験 3 1: クラスタ内ダウンロード実験アジア地区 (class 15) 有効ノード数 17 19

20 実験 3-1: クラスタ内ダウンロード実験アメリカ東海岸地区 (class 3) 有効ノード数 39 20

21 実験 3-1: クラスタ内ダウンロード実験南米地区 (class 2) 有効ノード数 10 21

実験 3 1: クラスタ内ダウンロード実験各クラスタの平均通信速度 RF: Rarest First 既存手法 3000 2500 EF: Eariest First 提案手法 EF では通信速度が低下 2000

22 実験 3 1: クラスタ内ダウンロード実験各クラスタの平均通信速度 RF: Rarest First 既存手法 EF: Eariest First 提案手法 EF では通信速度が低下 2000 ピース番号を考慮する必要がないRFの方が通信速度が 1500 よいことが分かった地区のネットワーク状況 500 に大きく依存 2Mbps 0 Downは配信ビットレートを大 RF EF RF EF RF EF 幅に上回っている. アジア地区米東海岸地区南米地区 C2 C15 C3 22

23 実験 3 1: クラスタ内ダウンロード実験各クラスタの累計待ち時間の分布 RF: Rarest First 既存手法 EF: Eariest First 提案手法 buffer = 10sec buffer = 30sec 各クラスタにおいて提案手法 EF の累計待ち時間を少なく抑えることができた. C15: アジア,C2: 東アメリカ海岸,C3: 南米 23

24 まとめ 1 地理情報を利用したノードのクラスタリングを行うことにより, 通信局所性を高め, 地理的に狭い範囲で通信を行うことができた. 2 ストリーミングに適したピース選択アルゴリズムを採用したス選択アルゴリズムを採用したことにより, ユーザの再生時の累計待ち時間を減少させユーザビリティを向上させることを PlanetLab 上の評価で確認した. 課題インテリジェントトラッカーの負荷状況の考慮. オリジナルシーダの運用方法. VoDオリジナルサーバとのハイブリッドシステム. 24

25 ご清聴ありがとうございました 25

!!!!!! Agenda 2012/2/6

Loca%on Based P2P Loca%on Based P2P Clustering with Seeders 5110B074-7 2012/2/6 !!!!!! Agenda 2012/2/6 - IP2009 20145 4.3 [1] P2P P2P [1] 2010 Cisco Visual Networking Index Forecast 2012/2/6 P2P (BitTorrent)!