ラベル torrent の投稿を表示しています。 すべての投稿を表示
ラベル torrent の投稿を表示しています。 すべての投稿を表示

2013年7月17日水曜日

P2P探訪 Raider トラッカーにアクセスしてみる

TorrentクローンをJava で作成しています。
そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。
そこで、学習したしことを、epub形式でまとめています。http://p.booklog.jp/users/kyorohiro


やる気スイッチが入らないので、書きかけの物をさらします。



-----------------

トラッカーにアクセスしてみる

TorrentからTrackerサーバーのアドレスを取得するできました。これでTrackerへ接続する準備ができました。さっそくTrackerにアクセスしてみましょう。

TrackerはHttpサーバーです。 「ピアID」と「Info辞書のHash」と「ポート番号」を渡すと、ピアの一覧を返してくれます。 Httpサーバーなので、「ピアID」と「Info辞書のHash」を持つURLさえ生成すれば、ブラウザからもアクセスできます。
まずは、 URLを生成して、Trackerからピアのリストを取得してみましょう。

ピアIDを準備する

Trackerへアクセスする際に、peer_idが要求されます。 peer_idは20バイトのユニーク値を持つバイト配列です。
このidは、クライアントを識別するのも活用できます。 詳しくは、http://www.bittorrent.org/beps/bep_0020.html を参照してみてください。 

例えば、以下のような感じでかける。
public static String createPeerId() {
byte[] peerId = new byte[20]; 
Random random = new Random(System.currentTimeMillis());
random.nextBytes(peerId);
System.arraycopy("-KY-".getBytes(), 0, peerId, 0, 8);
PercentEncoder encoder = new PercentEncoder();
return encoder.encode(peerId);
}
※ せっかく20バイトもデータがあのに、System.currentTimeMillis()でほぼ一意決まってしまう。スジが良くないです。 

Info辞書のHashを準備する

Trackerでは管理しているデータをユニークなID(SHA1のハッシュ)で管理しています。 Trackerは複数のTorrentファイルを管理していることがほとんどです。 なので、TrackerはこのユニークなIDをもらい、どのピアのリストを欲しがっているか判断するのです。

なので、Trackerからピア一覧をもらう場合は、このユニークなIDを用意する必要があります。 しかし、このIDはTorrentファイルには記載されていません。 Torrentファイルから生成する必要があります。
TorrentファイルのInfo辞書のSHA1を求めてください。 それがTrackerが必要としているユニークなIDです。


例えば、以下のような感じでかける。SHA1ハッシュは既存のAPIを使用すると良いでしょう。

Reader reader = <Info辞書の部分>
byte[] temp = ....
MessageDigest md = MessageDigest.getInstance("SHA");
do {
int len = reader.read(temp);
if (len < 0) {
break;
}
md.update(temp, 0, len);
} while (true);
digestLen = md.digest(buffer, 0, 20);


その他イロイロ準備する

上記のほかにも、「Port番号」、「状態」、「ダウンロードしたバイト数」、「アップロードしたバイト数」を渡す必要があります。
- 「Port番号」
他のピアからの通信の待ち受けしているポート番号です。 

- 「状態」
Trackerに状態を通知します。 「started」、 「stopped」、 「completed」の3つがあります。
既にデータを保持している場合は、「completed」、持っていない場合は、「started」、 ネットワークから抜ける場合は、「stopped」を設定します。

アドレスを生成してみよう

HttpサーバーへリクエストするURLは使用できる文字が制限されています。しかし、今回生成した値は、限りなくランダムに近い20バイトの配列です。 このため、そのままURLに使用することはできません。 
このような場合、 Percent Encoding をしたものをURLとして使用することになっています。
Percent Encoding
URLとして使用できない文字を、 「%xx」の形式にします。xxは16進数です。
例えば、以下のような感じでかけます。

private static final char[] sEncodeMap = {
'0','1','2','3','4','5','6',
'7','8','9','A','B','C','D','E','F'};
public  String encode(byte[] input, int start, int end) {
StringBuilder mBuilder = new StringBuilder();
for(int i=start;i<end;i++) {
byte atom = input[i];
mBuilder.append(''%');
mBuilder.append(sEncodeMap[(0xF0&atom)>>4]);
mBuilder.append(sEncodeMap[atom&0xF]);
}
return mBuilder.toString()
}


URLを作る
準備した値をつなげてURLを生成しましょう。
http://xxx.xxx.xx:6969/announce?info_hash=<生成した文字列>&peer_id=<ピアID>&port=6881&uploaded=0&downloaded=0&event=started

生成したURLをブラウザに入力すれば、Trackerからピアのリストをもらえます、

P2P探訪 Raider Torrentファイルを読み込んでみる(metafile)


TorrentクローンをJava で作成しています。
そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。
そこで、学習したしことを、epub形式でまとめています。http://p.booklog.jp/users/kyorohiro


やる気スイッチが入らないので、書きかけの物をさらします。





-------

Torrentファイルを読み込んでみる

すでにBencodingのパーサー作成済みなので、Torrentファイルの中身を解析することができるようになったと思います。
本ページでは、Torrentファイルに記載されている情報について説明します。

.Torrentはメタファイル 

Torrentファイルのデータの中身は、metainfo file structure と呼ばれています。 「メタ」というのは、データを要約したものです。
例えば、文書であれば、 「著作名」、「題名」、「ISBN番号」といったものがあげられます。 カメラで写真を撮ると、デシタルデータの場合JPEGという方式で画像されたりします。この時、 「撮影日時」、「撮影機器」、「解像度」、「GPS情報」などが記録されます。


では、Torrentでは、どのような情報が登録されているでしょうか?

MetaInfoの構造

ファイルがひとつの時
{
   announce:<benstring>, 
   info:{
     length:<beninteger>,
     name:<benstring>,
     piece length:<beninteger>,
     pieces:<benstring>
   }
}

ファイルが複数の場合
{
   announce:<benstring>, 
   info:{
    files: [
            { length:<beninteger>, path:[<benstring>,<benstring>]},
            { length:<beninteger>, path:[<benstring>,<benstring>]},
            ..
     ]
     name:<benstring>,
     piece length:<beninteger>,
     pieces:<benstring>
   }

ファイル名を記録できる

ファイル名を記録できます。 図xxxの name でファイル名を表現します。 lengthでファイルサイズを表します。
例えば、 「dokamagi,mp4」という20MBのデータをを記録したい場合、以下のように記述できます。
info:{
  name:"dokamagi,mp4"
  length:20971529
 }
}

TorrentはひとつのMetaInfoに複数のファイルを含めることもできます。この場合、name と pathを用いてファイル名を表現します。

例えば、「data/manga/bb.zip」「data/movie/dokamagi.mp4」というデータを記録した場合は、以下のように記述できます。

info:{
  files[
    {length:20971529, movie, dokamagi.mp4}
    {length:2097152, manga, bb.mp4}
  ]
  name:"data"
  length:20971529
 }
}

Trackerのアドレスを記録できる

Trackerのアドレスが記録できます。 announce でアドレスを記述します。
例えば、「http://127.0.0.1:8080/announce」をTrackerのアドレスとして記録した場合は、
{
announce:"http://127.0.0.1:8080/announce"
}


データの分割情報を知ることができる

Torrentは、データを分割してダウンロード、アップロードします。  MetaFileには、データを分割するサイズ、そのSHA1ハッシュ値が記述されています。 分割するサイズは「piece length 」で記述します。 SHA1ハッシュは、「pieces」で記述します。
例えば、32kのデータを、16kbに分割する場合は
{
   announce:<benstring>, 
   info:{
     piece length:16384,
     pieces:<40バイトのデータ>
   }
}

piecesは、分割したデータごとにSHA1ハッシュをとります。上記の例では、データが2分割されるため、20×2の40バイトとなっています。

P2P探訪 Raider Torrentファイルを読み込んでみる(bencoding)

TorrentクローンをJava で作成しています。
そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。
そこで、学習したしことを、epub形式でまとめています。http://p.booklog.jp/users/kyorohiro


やる気スイッチが入らないので、書きかけの物をさらします。

-------------------------------------------------------------------

ダウンロードの始まり

データをダウンロードは、「へちまたん.torrent」といった、torrentを拡張子に持つファイルを取得することから始まります。

通常、インターネットを通じてWWWから取得することになると思います。
OSのイメージであれば配布しているサイトで手に入るかもしれません。 オープンソースアニメや著作権きれのデータなど、それ専用のデータを野止めているサイトを探すと良いでしょう。「オープンソース アニメ Torrent」、「著作権切れ Torrent」といったキーワードで検索してみてください。Googleで検索すれば簡単に見つかると思います。

このページでは、実際にTorrentファイルを読み込み。どのような情報が記載されているか調べてみましょう。

Bencode/Bencoding で書かれている

Torrentファイルはbencoding という形式で書かれています。  Torrentファイルを読み込むためには、bencodingを解釈できるようにならなくてなりません。 まずは、Bencodingを読み込んでみましょう。

String/Integer/List/Dictionaryを扱える

 bencodingは、 String/辞書/リスト の4つのデータ型を扱うことができます。
 そして、以下のようなフォーマットで書かれています。

  beninteger   : "i" [0-9]* "e"
  benstring    : [0-9]* ":" <bytes array/string> 
     # bytes array/string length is prev [0-9]*.
  bendiction   : "d" dictelements "e" 
  benlist      : "l" listelements "e"
  benobject    : beninteger | benstring | beniction | benlist
  listelements : benobject (benobject)*
  dictelements : benstring benobject (benstring benobject)*


ひとつひとつ見ていきましょう。
文字列
まずは文字列です。 この本ではbencodingでの文字列をbenstiringと呼ぶことにはます。 例えば、「torrent」という文字列は、こbenstringでは、「7:torrent」と書きます。  
また、benstringは  文字列だけでなく、バイト配列としても使われます。<20バイトの配列> は、「20:<20バイトの配列>」とあらわす事ができるのです。

整数
実数です。この本ではbencodingでの整数はbenintegerと呼ぶことにはます。例えば、「1024}という数字は、benintegerでは、[i1024e」と書くことができます。

リスト
リストとは、bencodingで扱えるデータ構造のひとつです。 0個以上のデータを順序ありでデータを保持できます。つまり、 文字、整数、リスト、辞書、を保持することができます。

この本ではbencodingでのリストはbenlistと呼ぶことにはます。
例えば、「512という数字と、"test"という文字列」は、benlistでは、[li512e4:teste」と書くことができます。                                                                                                                                           
辞書
辞書とはbencodingで扱えるデータ構造のひとつです。辞書データは文字列とデータを紐付けで管理することができます。
例えば RPGゲームで主人公のパラメータとして、名前、性別、レベル、得意な魔法、とか設定されているとします。辞書型は、主人公辞書は、"レベル"とキーを渡せば、主人公のレベルが返ります。 女の主人公ならば、"性別"とキーを渡せば、女性と返ります。

辞書です。この本ではbencodingでのリストはbendictと呼ぶことにはます。
例えば、bencodingで 「"レベル" 13」 「"magic" "halito"」 を持つ辞書は、bendictでは、[d5:levelei13e5:magic6:halitoe」と書くことができます。

パースしやすい構造になっている

bencodingはパースし易いつくりになっています。
先頭1文字で、どのデータ構造でできているかが判断できるようになっているからです。

例えば、 integerならば'i'、 stringならば's'、リストならば'l'、辞書ならば、'd' といった感じです。
なので、bencodingのdecoderは、以下のようなシナリオで実現できます。
1. 一文字読み込む。
2. どのデータか判別する。
3. データ形式に応じて読み込む。
4. 1に戻る。



今後の表記について

今後 bencodingでデーター構造を表はする場合は、以下の表記をしようします。
リスト
  「li512e4:teste」は、 「[ 512, test] 」と表記します。
辞書
  「d5:levelei13e5:magic6:halitoe」は「{level:13, magic:halito}」と表記します。

P2P探訪 Raider お互いの位置を知る

TorrentクローンをJava で作成しています。
そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。
そこで、学習したしことを、epub形式でまとめています。http://p.booklog.jp/users/kyorohiro


やる気スイッチが入らないので、書きかけの物をさらします。

-------------------------------------------------------------------

お互いの位置を知る

P2Pにてデータをダウンロードする場合、自分が欲しいデータを持っているコンピュータを探すことからはじまります。
これは、従来のシステムから考えると特殊なことです。たとえば、皆さんが日常で使用しているインターネットの世界では、欲しいデータの在り処はアドレスとい形で提供されています。Googleで検索したいならば、www.google.com、Youtubeで動画をみたいならば、www.youtube.com、ニコニコ動画で生放送をみたいならば、live.nicovideo.jp といったアドレスをブラウザに入力すると、欲しい情報を手に入れることができるでしょう。

しかし、P2Pではデータを持っているのは、インターネット上に名前を振られた、GoogleやYoutubeのようなホスト名を持つコンピュータではありません。今、皆さんがブラウザを起動しているようなコンピュータになります。
なので、GoogleやYoutubeにアクセスするように、皆さんのコンピュータにアクセスするためのアドレスを知る必要があります。

また、これはP2Pでのファイル共有としては重要な機能です。お互いのアドレスを知ることができれば、ほぼほぼデータ交換をに必要な作業は完了したと言っても良いでしょう。欲しいデータがあるコンピュータを知ることができたならば、後はデータ配信するようにお願いすれば良いのです。


Torrentでのお互いの位置を知る方法は2つある

では、Torrentではお互いの位置をどのようにして知るのでしょうか?Torrentでは2つの方法が提供されています。

Httpサーバーから教えてもらう方法

ひとつは、「GoogleやYoutubeのようなホスト名を持つコンピュータ」から教えてもらう方法。 このコンピュータのことをTrackerと呼びます。
P2Pといえる部分はTorrentクライアント同士がデータを転送する部分になります。 それだけではなく、TrackerはGoogleやYoutubeといったた通常のWWWのコンピュータと同じルールで動作しています。 
なので、ブラウザーからTrackerにアクセスすることも可能です。 ブラウザからTrackerにアクセスすると、データを配信してくれるTorrentクライアントの一覧を取得できます。 ためしに、以下の手順でURLを生成してTrackerにアクセスしてみてください。  TrackerはTorrentの一覧を返してくれます。
1. 
2. 
3. 
4. 
5. 

Torrentクライアント同で情報を交換しあう

 もうひとつは、「知り合いのTorrentクライアントから教えてもらう方法」です。 Mainline DHT と呼ばれていて、Kademliaベースの分散ハッシュテーブルが使用されています。 「Kademlia」については別の章で説明します。

当初TorrentはDHTをサポートしていませんでした。 このため、TorrentはTracker化が潰れてしまうとデータを配信したTorrentクライアントは存在するのに、データを配信できなません。 いかに、転送効率をあげようとも、Trackerが落ちてしまうという弱点を持っていたのです。
しかし、今では、DHTがサポートされ、Trackerが存在していなくとも、データの配信を可能にしました。


友達の友達は友達!!
DHTは「知り合いの知り合いを6人たどれば、世界中の誰とでもつながる」と同じ仕組みでできています。 例え、自分がメッセージを届けたい人のメールアドレスをしらなくても、 あなたの友人は知っているかも知れません。
友人にメッセージを届けたい人にメールアドレスを教えてもらうと良いでしょう。

もしも、 あなたの友人が「メッセージを届けたい人のメールアドレス」を知らなくても、その友人の友人は知っているかも知れません。現実世界では、「六次の隔たり」と呼ばれていて、6人もたどれば、世界中の誰とでもつながっているそうです。

DHTをサポートするTorrentクライアントは、 Torrentクライアントのリスト持っています。 もしも、特定のデータを持つTorrentクライアントを聞かれたら、自分のリストからもっともそのことを知っていそうなTorrentクライアントを紹介します。
これによって、少ない回数でおめあてのデータを持つクライアントを発見することでできるのです。

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


2013年5月19日日曜日

P2P探訪 Raider やる気スイッチ 「はじめに」

Raiderのメタファで、Torrentクローンを作成しています。 Java で作成しています。
そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。
そこで、学習したしことを、epub形式でまとめることにしました。
https://github.com/kyorohiro/Raider/tree/master/Raider/doc/torrent/matome.epub
だが、やる気スイッチが入らない。なので、そこそこまとまった書きかけのものをさらすことにした。 そうすれば、やる気スイッチが入るかもしれない。
↓書き直します。たぶん、ひとかけらも残りませんが..。はじめにの章の部分

この文書について


Bittorrentのクローンを作成しています。その時に調査した結果をまとめたのこの文章です。
少しでも興味を持たれたかた。この文書を通して少しでもTorrentの理解の助けになれば幸いです。


ちまたでは、Torrentは違法なファイル共有アプリという認識が強いように思います。Twitterの検索機能で、Torrentと検索して見てください。Torrentに関するネガティブなイメージな。違法な利用を助長するようなツイートを発見することができるでしょう。
GooleでTorrentと検索してみてください。「アメリカ合衆国のデジタル ミレニアム著作権法に基づいたクレームに応じ、このページから 1 件の検索結果を除外しました。」といった文言が表示されます。また、Twiiterで検索した結果と同じように違法な利用を助長するようなサイトを発見することができるでしょう。

しかし、こういったネガティブなイメージはTorrentの一面でしかありません。まっとうな使われ方も大くされており。
例えば、大規模なネットワークシステムのデプロイといったことが上げられます。デプロイというのは、ユーザーへサービスを提供するために準備作業の事をいいます。
Googleであれば、データを即座に検索できるようにサーバーを立ち上げる。Youtubeならば、動画を再生できるようにする。Twitterならば、ツイートを送信だとか表示できるようにするといった事です。
大手のネットワークサービスでは、数千代、数万台のコンピュータが動作しております。 これらのコンピュータに変更を加える必要が出てきた場合には、修正するためのデータを数千代、数万台のコンピュータに配信する必要がでてきます。
こういった、データの配信にTorrent技術は使用されています。

例えば、OSのイメージの配信に使用されています。OSというWindowsやMacなどメーカーがCDやDVDといった記憶媒体を通して配布されている事をイメージするかも知れません。
しかし、独自にOSをパッケージングする事は、大手のメーカがする仕事というわれではありません。今では、個人が趣味でOSをパッケージングして配信する事も可能です。可能なだけでは、ありきたりな行為になりつつあります。
個人で配信する場合、当然ながら数千台、数万台のサーバーを用意する事はできません。また、CDやDVDの記憶媒体を大量に配る事にしても限界があります。
そういった、個人がデータを配布するのに、Torrentの技術が使用されています。


また、Torrentを学ぶことは、P2Pの記述を学ぶうえで最適な題材ではないかと考えられます。
まず、Torrentはもっとも普及した通信方法であります。それだけではなく、最新の技術を取り入れ進化し続けている技術でもあります。
Torrentを学習すると、ネットワークアプリ作成のノウハウ、分散ハッシュテーブル、 ゲーム理論を応用した柔軟なネットワーク等など、基本から応用まで、扱う事になります。
なによりも、多くのアプリや仕様がオープンに公開されており、P2Pを実例をもって学ぶことができるのです。

Torrent以外でメジャーなP2Pアプリはありました。しかし、Torrentほどおっぴろげなものはないでしょう。日本で流行したWinnyのソースは公開されていません。Winnyについて知りたければハックする必要があります。海外で流行したWinmxもそうです。
Torrentはその仕様が公開されています。どのような通信プロトコルで通信されているかが文書化されています。おおくの実装例、オープンソースとして公開されています。公開されているだけではありません。さまざまなプログラム言語で書かれています。Python Ruby Java JavaScript C++ 等などありとあらゆる言語で書かれています。
もしも、煮詰まったとき等は、これらの実装を読む事で保管する事も可能でしょう。あなたの得意な言語で読む事でできるのです。

Torrentのアングラな面は一面に過ぎないすぎないこと。優れた技術は多くの実用的なプロダクトで利用されていること。また、TorrentがP2Pの教材として優れておいることを理解しいただけけば幸いです。


2013年5月17日金曜日

P2P探訪 Raider やる気スイッチ 「トレントって何」

Raiderのメタファで、Torrentクローンを作成しています。 Java で作成しています。
そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。
そこで、学習したしことを、epub形式でまとめることにしました。
https://github.com/kyorohiro/Raider/tree/master/Raider/doc/torrent/matome.epub
だが、やる気スイッチが入らない。なので、そこそこまとまった書きかけのものをさらすことにした。 そうすれば、やる気スイッチが入るかもしれない。
↓書き直します。たぶん、ひとかけらも残りませんが..

トレントっ何

Torrentは効率良くデータを配信するするためプロトコルです。とても効率良く配信ができるため、様々な分野で利用されています。

個人では多くのユーザーにデータを届けたい場合非常にコストがかかります。これは、今までのインターネットのデータ配信をする方法では不可能でした。不可能だったことがP2Pテクノロジーによって可能になったのです。

P2Pテクノロジー

データの配信はとてもコストが高い

インターネット上でデータを配信するためには、サーバーとデータを通信する必要があります。ここでいうサーバーというのは、URLにヒモづくコンピュータという認識でよいです。
例えば、Googleで検索する場合は、http://www.google.com、 Youtubeで動画を見るには、http://www.youtube.com といったアドレスにIEやFirefoxやChromeといったブラウザからアクセスしていますね。
そういった、ブラウザからアクセスした先にはコンピュータがあり、あなたに期待に答えるように、検索結果や、動画の配信をしてくれます。

このデータを配信するサーバーはとてもコストがかかります。コストというのはお金だとか、時間だとかです。

例えば、ニコ生配信とかで、2000人くらいのユーザーが見に来るような場合、2000×50KB=100MB必要となります。 ご家庭にある通信回線は10MB程度ですから。100MBという値は、すでに個人で配信できる量ではなくなります。

また、これらを配信するサーバーを運営している方々は、こういったコストを負担してサービスを提供しているのです。

低コストでデータの配信が可能な優れもの

Torrentはこれらのコストをきわめて最小化することできます。あなたが、こういったサービスを自ら提供することも容易になりました。このサーバーにコストがかかる問題の解決策として、Torrentでは、データをダウンロードするユーザーも、データ配信に加わることにしたのです。

例えば、30分のアニメを200MBのデータとして配信する場合、1分間に2MB、1秒間に51KBのデータを配信する必要があります。
サーバー側が10MBの通信回線を持っていて、2.5MBを配信に使用する場合、同時にに50人くらい配信できます。これが限界です。

しかし、50人が2.5MBを配信に使用してくれれば、2.5×50MBつまり150MBの配信が可能になります。
150MBだと、3000人程度に配信が可能です。
また。この3000人が、2.5MB配信にまわしてくれれば、2.5×3000MB=7500MBの配信が可能になります。これは、15万人に配信が可能です。

といった感じで、データを受け取る側が増えれば増えるほど、配信可能なデータ数が増えるのがわかってもらえたでしょうか。これによって、サーバーを運営する側だけがコストを払わなくても良くなったのです。


2013年2月10日日曜日

P2P探訪 Raider その1-1 Bencoding

前回の記事を書き直しました。説明不足を補います。

 課題1 Torrent File に記載されている情報を読み込みたい。
BitTorrent のプロトコルを学習するに当たって、実際に、Torrentクライアントを実装することにしました。
まず最初に、TorrentFileに記載されている情報を読み取ることから始めたいと思います。

Torrentファイルは、bencode というルールで、記述されています。
そこで、
1. Bencodingを扱えるようにする。
2. Bittorrentファイルを読み込めるようにする。
の順に問題を解決していくことにしました。

というわけで、この記事ではBencodingについて説明します。

Bencoding
bencodingは integer, string(byte array), list, diction のデータ型を持ちます。
なので、この4つデータ型のデコードとエンコードができるようになれば、
bencodingを扱えるようになったことになります、

具体的に、以下のようなルールでエンコードされいます。
  beninteger   : "i" [0-9]* "e"
  benstring    : [0-9]* ":" <bytes array/string> 
     # bytes array/string length is prev [0-9]*.
  bendiction   : "d" dictelements "e" 
  benlist      : "l" listelements "e"
  benobject    : beninteger | benstring | beniction | benlist
  listelements : benobject (benobject)*
  dictelements : benstring benobject (benstring benobject)*

といった感じです。
例えば、
  Integerで、1を表したい場合は、"i1e"
  Stringでabcを表したい場合は、"3:abc"
  上記を含むListを表したい場合は、"li1e3:abce"
  といった感じで表せます。


また、bencodingは簡単にパースできるように工夫されています。
簡単といえるのは、先頭1文字で、どのデータ構造でできているかが判断できるようになっているからです。

なので、bencodingのdecoderは、以下のようなシナリオで実現できます。
1. 一文字読み込む。
2. どのデータか判別する。
例えば、 'i' ならば、integer、's'ならば、stringといった感じです。
3. データ形式に応じて読み込む。
4. 1に戻る。


RaiderでのParse方法
Bittorrent のbencodingのencode/decode方法はとてもシンプルです。
Bittorrentのbencodingに関する部分のコードをチックすると良いでしょう。ですが、Radierでは LLライクな独自の方法を採用しました。
特に理由はありません。仕様から空で考えたら、別の実装になってしまいました。

パースの仕組みについて、簡単に解説します。 LLでは文法とJava Method が一対一で対応付けることができます。
なので、対応付け方法がわかれば、機械的な作業になります。
※ なので普通は、antlrだとか javaccとか、yaccとか bisonとか ツールを使って実現したりします。


例えば、以下のような文法の場合
   benstring    : "i" [0-9]* "e"
   beninteger   : "i" [0-9]* "e"
   benobject    : beninteger | benstring

以下のような感じで一対一の対応で書けます。
 static void benstring(reader) throws xxException {
    try {
       reader.mark(); 
       if(check(string grammer)) {
       } else {
          reader.backtoMark(); // パースに失敗した時に、ポインターの位置を元に戻す。
          throw xxException;
       }
    } finally {
      reader.releasemark();
    }
 }

 static void beninteger(reader) throws xxException  {
    try {
       reader.mark();
       if(check(integer grammer)) {
       } else {
          reader.backtoMark(); // パースに失敗した時に、ポインターの位置を元に戻す。
          throw xxException;
       }
    } finally {
      reader.releasemark();
    }
 }
 static void benobject(reader) throws xxException {
     try {benstring()}catch(xxException e){}
     try {beninteger()}catch(xxException e){throw e;}
 }



[reference]
- 成果物、bencoding
  https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/bencode

- Torrent spec
  http://en.wikipedia.org/wiki/Torrent_file
  http://www.bittorrent.org/beps/bep_0003.html
  http://sourceforge.net/projects/bittorrent/
  
- LL Parser
  http://pragprog.com/book/tpdsl/language-implementation-patterns
  

mbedtls dart の 開発を始めた web wasm ffi io flutter

C言語 で開発した機能を、Dart をターゲットとして、Web でも サーバーでも、そして Flutter  でも使えるようにしたい。 そこで、mbedtls の 暗号化の部分を Dart 向けのPackageを作りながら、 実現方法を試行錯誤する事にした。 dart...