| | | | | |
|
 |
|
 |
 |
|
|
P2PにおけるPAR2の存在意義
大抵の人はPAR2は冗長化であり容量が増えるのでそれに伴い通信量が増えると考えがちです。しかし実際はP2P上ではそうではありません。確かに冗長化するために使用するP2Pネットワーク上のストレージの占める割合は元のキャッシュが1つずつであれば増えますが、元々多重拡散しているためストレージの消費が増えることはありませんし、何より通信量はほとんど増えません。加えて歯抜け防止に大いに効果を発揮します。
 PAR2とは
一般的な訂正符号（RAID-5で一般的に使用される訂正符号）とは違い、連続して発生する誤りを訂正する能力を持った誤り訂正の方法で、非常に高い訂正能力があります。
PAR2の訂正能力
n個のデータブロック(D1, D2, ...., Dn)と、m個のパリティブロック(P1, P2, ..., Pm)があるとします。この時、D1, D2, ..., Dn, P1, P2, ..., Pm の中からm個のブロックが消失しても、残りのn個のブロックより消失ブロックの内容を復元することができます。
PAR2の中身
一般的な訂正符号であるパリティを拡張した物であるのでPAR2とも呼ばれていますが、中身はReed-Solomon符号です。しかし訂正能力の高さの代わりに複雑な演算を使用するために復元に時間がかかり、また複雑であるためにプログラマーへの負担が大きくなります。プログラミング方法についてはPAR2の計算方法を参照ください。
PAR2の注意すべき点
現在のパソコンの処理能力は100MFLOPSほどあります。これは普通のデータ処理には問題が無いくらい十分速いですが、PAR2は分割数倍の時間がかかるという特徴があるので気をつける必要があります。たとえば128分割をすると1秒で1MBを処理することが厳しくなります。分割数に関しては今後のコンピュータの速度と比べながら調整する必要がありそうです。ImonyではPAR2を二重に組み、通信層では256分割、処理層では64分割を採用する予定です。
※パリティブロックの数は影響は復元時間に影響しません
P2Pに与える影響
ダウンロード成功率
DO-NOTHING(何もしない) 自分のみ持っている状態です
COPY(コピー) 自分を含めた4人にコピーした状態です
DIFFUSED(拡散) 256人に64種の断片を均等に拡散した状態です
PAR1(パリティ) DIFFUSEに加え4人に1種のパリティを拡散した状態です
PAR2(パリティ2) 256人に256種の断片及びパリティを拡散した状態です
※DIFFUSED,PAR1,PAR2は誰も完全キャッシュを持たない状態であり、また自分の存在を含めていません。
このグラフはこの状態での完全ダウンロード成功確率を表しています。
- PAR2は維持率32%でも99%取得可能
- 維持率32%の時、DIFFUSED,PAR1は成功率は30万分の1未満
- DIFFUSEDで成功する可能性が高いのは68%以上
- PAR2で成功する可能性が高いのは25%以上
- 等確率減少の場合でもPAR2はDIFFUSEDに比べ約3.6倍の寿命
- PAR1の導入でも効果はある
このグラフより以上のような結論を導くことができます。これよりPAR2の導入は大幅な効率向上が見込めるということと、PAR1の導入でもある程度の効率向上が見込めるということがわかりました。またP2Pにおいては再接続により減少確率は次第に減るので4倍以上の延命効果があるかもしれません。
計算式は以下のとおりになります。このグラフでは維持率を横軸にし、分割数を64、倍率を4で計算しています。最初に「消滅率 = 1 - 維持率」「ブロック消滅率 = 消滅率 ^ 倍率」「ブロック維持率 = 1 - ノード消滅率」を予め計算し以下を計算すると確率を求めることができます。
- [何もしない] = 維持率
- [コピー] = ブロック維持率
- [拡散] = ブロック維持率 ^ 分割数
- [パリティ] = [拡散] * (ブロック維持率 + ブロック消滅率 * (分割数 + 1))
- [パリティ2] = Σ[k = 分割数 ～ 分割数 * 倍率]維持率 ^ k * 消滅率 ^ (分割数 * 倍率 - k) * C(分割数 * 倍率, k)
歯抜け率
DIFFUSED(拡散) 256人に64種の断片を均等に拡散した状態です
PAR1(パリティ) DIFFUSEに加え4人に1種のパリティを拡散した状態です
PAR2(パリティ2) 256人に256種の断片及びパリティを拡散した状態です
※ここでは64断片中1断片～4断片(約6%)が見つからなかった状態を歯抜けとしています
このグラフはこの状態での64断片中60断片以上取得した状態で失敗確率を表しています。
- DIFFUSEDでは維持率57%時に最大82%の確率で歯抜け
- PAR1では維持率53%時に最大74%の確率で歯抜け
- PAR2では維持率24%時に最大72%の確率で歯抜け
このグラフより以上のような結論を導くことができます。これよりPAR2の導入は大幅な歯抜け防止効果が見込めるということと、PAR1の導入でもある程度の効果が見込めるということがわかりました。
計算式は以下のとおりになります。このグラフでは維持率を横軸にし、分割数を64、倍率を4、歯抜け判定数を60で計算しています。最初に「消滅率 = 1 - 維持率」「ブロック消滅率 = 消滅率 ^ 倍率」「ブロック維持率 = 1 - ノード消滅率」を予め計算し以下を計算すると確率を求めることができます。
- [拡散] = Σ[k = 歯抜け判定数 ～ 分割数 - 1]ブロック維持率 ^ k * ブロック消滅率 ^ (分割数 - k) * C(分割数, k)
- [パリティ] = Σ[k = 歯抜け判定数 ～ 分割数 - 1]ブロック維持率 ^ k * ブロック消滅率 ^ (分割数 + 1 - k) * C(分割数 + 1, k)
- [パリティ2] = Σ[k = 歯抜け判定数 ～ 分割数 - 1]維持率 ^ k * 消滅率 ^ (分割数 * 倍率 - k) * C(分割数 * 倍率, k)
PAR2に関してはMicrosoft Visual Basic 6.0での乱数によるダウンロード成功率計算プログラムでも確認できます。
これらグラフはMicrosoft Excel 2000とAdobe Photo Shop 5.0Jとを使い出力しています。
|
 |
コンテンツ
トップページ
Imonyについて
Imonyアンテナ
更新履歴
リンク集
≫P2P today
≫俺が新しいP2P作ろっか？
…P2P製作 本スレ
≫Download板
|
|
Copyright(C) 2004/04/01-2008/12/05 FlashBox.
All rights reserved. Programed by Imo.
Designed by Imo, N-Style, siv.
Time: 191.1ms -87
管理モード
|