2013年6月3日月曜日

P2P探訪 Raider 楽観的チョーク解除ではぶられる確率

ひとつだけランダムにChokeを解除する機能が備わっています。Chokeがされ続けて1ピースもダウンロードが開始されない状況が長く発生するのかどうか検証しました。

[Choke]

Torrentでは、一度にアップロードするPeerを制限しています。だいたい、4つくらいです。4つの内1つはランダムに切り替わります。4つの内3つは戦略的に切り替えます。つまり、転送速度に時間がかからないPeerや、以前にデータをダウンロードさせてもらったPeerに優先的にデータをアップロードするのに使用します。

低回線でひとつもデータの断片を持たない場合、ランダムに切り替わるものだけが頼りになります。長時間データがアップロードされない状況に陥ることはないのでしょうか?検証しました。


[楽観的Chokeであふれる確率]

このランダムに割り振られるアップロードするPeerを選ぶことを楽観的チョーク解除と呼ぶことにします。Chokeがデータをアップロードしない。Unchokeがデータわアップロードする。という意味です。

Peerが4つある場合

以下のような組み合わせが考えられます。○がunchokeされる。 ×がchokeされる。
○○○○ 
×○○○,○×○○
○○×○,○○○× 
××○○,×○×○
×○○×,○××○
○×○×,○○×× 
○×××,×○××
××○×,×××○
×××× 

また、○となる確率は1/4、×となる確率は3/4ですから、

4つすべてのPeerからダウンロードできる確率は(1/256)3つからダウンロードできる確率は(12/256)、2つのPeerからダウンロードできる確率は(54/256)、1つからダウンロードできる確率は、(108/256)、どのPeerからもダウンロードできない確率は(81/256)となります。

同様にどのPeerからもダウンロードできない確率、

Peerが 4の場合は、 (3**4)/(4**4) = 0.31

Peerが 5の場合は、 (4**5)/(5**5) = 0.32

Peerが50の場合は、(49**50)/(50**50) = 0.36

Peerが1000000の場合は = 0.36

といった感じになります。また、30秒ごとに切り替わりますから、Peerが50であった場合、30秒後もはぶられる確率は、0.12、60秒後もはぶられる確率は、0.04となります。

Seederが存在している限り、ダウンロードがまったまできなくなる状況が続くことはなさそうです。


[PS]

簡単な2項分布の問題でした。2項分布つにいては、Googleしてください。

書き間違えてた。書き直した。

思ったよりもChokeが長く続く可能性があるのに驚いた。何か間違えているかな?

初期状態では、どれが戦略的に優先すべきPeerが不明なわけだから、(46**50)/(50**50)=0.015となる。また、((x-4)/x)**xは0.020くらいに収束する。つまり、Peer数が増えても状況はかわらない。

....ミスッた。別の記事で書き直します。



2013年6月1日土曜日

P2P探訪 Raider JavaFXでHtmlServerを立ててMediaPlayerを再生する

「へちまたん」にTorrentでダウンロード中の動画を再生する機能を追加することにしました。

動画再生にはJavaFXのMediaPlayerを使用することにしました。しかし、JavaFXのMediaPlayerは、ファイルとアドレスしか指定できません。ダウンロード中のデータをJavaFXのMediaPlauerに渡すにはどうすればよいのでしょうか?

「へちまたん」で回答を紹介します。


[回答]

「へちまたん」は、HtmlServerの機能をもたせることで解決しました。

1. 動画ファイルをダウンロードする。

2. ダウンロード中の動画ファイルをMediaPlayerに渡すサーバーを立ち上げる。

3. 動画再生側(MediaPlayer)は「へちまたん」が立ち上げたサーバーにデータを取得しにいく。

といった感じです。

[必要な実装]

基本、GETリクエストを受けとたらそのデータを返すだけです。しかし、終盤の映像だけ再生したいといったことがある場合、これだけではうまくいきまん。

Rangeリクエストに対応する必要があります。

[Rangeリクエスト]

Rangeリクエストはダウンロードするデータの位置を指定する事ができます。

例えば、200MBの「どかまぎ列伝」というデータがあったとしましょう。20分くらい動画とします。ユーザーはこの動画すでに見たことがあるのです。しかし、終盤のシーンは見逃してしまいましたとします。理由は色々あると思いますが、とりあえず見逃したのです。なので、15分くらいの動画再生を飛ばしたいはずです。もしも、通常通り動画をサーバーからデータを読み込むと、0Bから読み込みを開始します。途中からとかできません。0Bから読み込み始めます。

この場合、1秒間1MB読み取れる、恵まれた環境の人でも、150秒です。2分以上待たされることになります。そんな問題を解決するのが、Rangeリクエストです。

Rangeリクエストは位置を指定してダウンロードできます。15分後のデータからくださいといったことが可能になるわけです。

[位置を指定してダウンロード]

動画を再生する側は簡単です。Getリクエストのヘッダーに欲しいデータの位置を指定するだけです。300MBのデータの10MBから最後までデータが欲しい場合は、「Range: bytes=10000000-」とヘッダーを追加します。これは、JavaFXのMediaPlayerの中で勝手にやってくれます。

サーバー側は、「Accept-Ranges: bytes」「Content-Range: bytes 10000000-300000000/300000001」とヘッダーを追加して、指定された位置のデータを返すだけでよいです。

といった感じで、特別難しい処理が必要ではないです。HttpのGetリクエストに追加するヘッダーが変わる事ぐらいしか特別なことはしていません。

マルチパートでレスポンスを返すといった、ちょっと複雑なケースもあります。しかし、動画の配信で呼ばれることは、ほぼほぼないでしょう。より詳しい情報はrfc2616を参照してください。

[Hetimatanのコード]

つくりかけですが..

https://github.com/kyorohiro/Hetimatan/blob/master/Hetimatan/src/net/hetimatan/net/http/SimpleHttpServer.java