(57)【要約】  配布されるファイルのサイズに従って符号化するために用いられるフラグメント数を変更させる適応耐消去コード（ＥＲＣ）を用いる適応符号化ストレージシステムが開示される。適応ＥＲＣは、Ｐ２Ｐストレージの効率性及び信頼性を大いに改善することができる。Ｐ２Ｐストレージアプリケーションに対する多くの手順を実施することができる。１つの実施形態では、小容量の動的データファイルは、より信頼できるピアまたはサーバに迂回され、一方、大容量の静的ファイルは、信頼できないピアのストレージ能力を利用して記憶される。同様に、バランスのとれた貢献及び利益のために、ピアは、Ｐ２Ｐネットワークに記憶されるコンテンツの量と同じコンテンツの量をホストすることになっている。結果として、信頼できないピアは、より少ないデータを配布することが許され、より信頼性のあるピアは、より多くのデータを配布されることが許される。同様に、より小容量のファイルは、より高い配布コストが割り当てられ、より大容量ファイルは、より低い配布コストが割り当てられる。
2009527856.tif 000002
【特許請求の範囲】
【請求項１】
分散ネットワーク内で記憶されるべきファイルを符号化するコンピュータ実行プロセスであって、
異なる耐消去符号化（ＥＲＣ）フラグメント数に対応する最適ファイルサイズを算出し、前記フラグメント数の各々は、ファイルサイズの対応する範囲に対する最適フラグメント数であるプロセスアクション（９０２）と、
所定のファイルサイズのファイルを入力するプロセスアクション（９０４）と、
前記ファイルサイズが、最小ＥＲＣフラグメント数の２に対する前記ファイルサイズの前記範囲より小さい場合、耐消去符号化を用いずに前記ファイルを符号化するプロセスアクション（９０６、９０８）と、
前記入力ファイルの前記ファイルサイズがファイルサイズの範囲に対応する場合、耐消去符号化及び前記入力ファイルの前記ファイルサイズの範囲に対応する最適フラグメント数を符号化するプロセスアクション（９０６、９１０）と
を含むことを特徴とするコンピュータ実行プロセス。
【請求項２】
分散ネットワークにおいて１つ以上のピアに前記符号化されたファイルを送出するプロセスアクションを更に含むことを特徴とする請求項１記載のコンピュータ実行プロセス。
【請求項３】
前記符号化されたファイルは、ピア信頼性及びファイルコンテンツの所望の信頼性に従って記憶されるピアの数を算出するプロセスアクションを更に含むことを特徴とする請求項１記載のコンピュータ実行プロセス。
【請求項４】
異なる耐消去符号化(ＥＲＣ) フラグメント数に対応する最適ファイルサイズの範囲を算出するプロセスアクションは、
特定のＥＲＣフラグメント数に適している最適のファイルサイズとして異なるフラグメント数同士の間の境界を決定するプロセスアクションを含むことを特徴とする請求項１記載のコンピュータ実行プロセス。
【請求項５】
前記ファイルが符号化するために分割されたフラグメント数に等しいかそれより大きい前記符号化されたファイルの一組のファイルフラグメントを得るプロセスアクションと、
前記ファイルが耐消去符号化されていた場合に、耐消去復号化を用いて前記符号化されたファイルフラグメントを復号して、前記符号化されたファイルの復号化バージョンを得るプロセスアクションと、
前記ファイルが耐消去符号化されていなかった場合に、耐消去復号化を用いずに前記符号化されたファイルフラグメントを復号して、前記符号化されたファイルの復号化バージョンを得るプロセスアクションと、
をさらに含むことを特徴とする請求項１記載のコンピュータ実行プロセス。
【請求項６】
前記ファイルを符号化する際に用いられる前記耐消去符号化は、リードソロモン符号化であることを特徴とする請求項１記載のコンピュータ実行プロセス。
【請求項７】
前記ファイルサイズが約１０ＫＢ未満である場合、耐消去符号化が用いられず、
前記ファイルサイズが約１０ＫＢから３３ＫＢである場合、最適フラグメント数は２であり、
前記ファイルサイズが約３３ＫＢから１００ＫＢである場合、最適フラグメント数は４であり、
前記ファイルサイズが約１００ＫＢから３１０ＫＢである場合、最適フラグメント数は８であり、
前記ファイルサイズが約３１０ＫＢから９５０ＫＢである場合、最適フラグメント数は１６であり、
前記ファイルサイズが約９５０ＫＢから２.９ＭＢである場合、最適フラグメント数は３２であり、
前記ファイルサイズが約２．９ＭＢから８.９ＭＢである場合、最適フラグメント数は６４であり、
前記ファイルサイズが約８．９ＭＢから２６ＭＢである場合、最適フラグメント数は１２８であり、
前記ファイルサイズが約２６ＭＢより大きい場合、最適フラグメント数は２５６であることを特徴とする請求項６記載のコンピュータ実行プロセス。
【請求項８】
請求項１に記載の前記プロセスを実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
【請求項９】
ピアツーピアネットワークのストレージの信頼性及び効率性を改善するシステムであって、
汎用コンピュータデバイスと、
前記汎用コンピュータにより実行可能なプログラムモジュールから成るコンピュータプログラムと、
を含み、
前記コンピュータデバイスは、前記コンピュータプログラムの前記プログラムモジュールにより方向付けられ、前記コンピュータプログラムの前記プログラムモジュールは、
前記最適フラグメント数を判断して耐消去符号化を用いて所定のサイズのファイルを符号化するプログラムモジュール（１０１０）と、
耐消去符号化を用いて前記ファイルを符号化するための前記最適フラグメント数が１である場合、耐消去符号化を用いてファイルを符号化しないプログラムモジュール(１０１０)と、
前記載的フラグメント数が１より大きい場合、前記ファイルを前記最適フラグメント数に分解し、更に耐消去符号化を用いて前記ファイルを符号化するプログラムモジュール（１０１０）と、
であることを特徴とするシステム。
【請求項１０】
前記符号化されたファイルフラグメントが記憶される前記ピアの数を、ピア信頼性及びファイルコンテンツの所望の信頼性に従って算出するプログラムモジュールを更に含むことを特徴とする請求項９記載のシステム。
【請求項１１】
耐消去符号化を用いて符号化されたファイルをネットワーク上の１つ以上のピアに配布するプログラムモジュールを更に含むことを特徴とする請求項１０記載のシステム。
【請求項１２】
前記ファイルを配布する前記プログラムモジュールは、
前記分散ネットワーク内の各々のピアの信頼性を判断するサブモジュールと、
前記ファイルの前記サイズを判断するサブモジュールと、
ファイルサイズによって判断されるような適当な信頼性を有する１つ以上のピアを用いて前記ファイルを配布するサブモジュールと、
を含むことを特徴とする請求項１１記載のシステム。
【請求項１３】
前記ファイルを配布する前記プログラムモジュールは、
前記ファイルが大容量である場合、その信頼性が所定の閾値を下回るピアを用いて前記大容量ファイルを配布するサブモジュールと、
前記ファイルが大容量でない場合、その信頼性が所定の閾値を上回るピアを用いて前記ファイルを配布するサブモジュールと、
を含むことを特徴とする請求項１２記載のシステム。
【請求項１４】
前記ファイルを配布する前記プログラムモジュールは、
前記分散ネットワーク内の各々のピアの前記信頼性を判断するサブモジュールと、
前記ファイルが静的であるか否かを判断するサブモジュールと、
前記ファイルが静的である場合に、その信頼性が所定の閾値を下回るピアを用いてファイルを配布するサブモジュールと、
前記ファイルが静的でない場合に、その信頼性が所定の閾値を上回るピアを用いてファイルを配布するサブモジュールと、
を含むことを特徴とする請求項１１記載のシステム。
【請求項１５】
前記ファイルを配布する前記プログラムモジュールは、
前記分散ネットワーク内の各々のピアの前記信頼性を判断するサブモジュールと、
前記ファイルの変更を監視するサブモジュールと、
最初に、前記ファイルをより信頼性のあるピアに配布するサブモジュールと、
前記ファイルが変化しないことが観察される場合、より低い信頼性のピアに前記ファイルを再配布するサブモジュールと、
を含むことを特徴とする請求項１１記載のシステム。
【請求項１６】
サーバを用いて前記分散ネットワークの効率性を改善するプログラムモジュールを更に含み、前記プログラムモジュールは更に、
前記分散ネットワーク内の全ての動的ファイルを前記サーバにバックアップするサブモジュールと、
周期的に、前記分散ネットワーク内のピア及び前記サーバにチェックさせて前記サーバにバックアップされた前記動的ファイルが変わったか否かを見るサブモジュールと、
前記動的ファイルが変化しなかった場合、これらのファイルを静的であると指定して、大容量ファイルにそれらをまとめるサブモジュールと、
耐消去符号化を用いて前記大容量ファイルを前記分散ネットワークに配布するサブモジュールと、
を含むことを特徴とする請求項９記載のシステム。
【請求項１７】
前記最適フラグメント数を判断し、耐消去符号化を用いて所定のサイズのファイルを符号化するプログラムモジュールは、
各々の利用可能な耐消去符号化フラグメント数に対する最適ファイルサイズの範囲を判断し、前記フラグメント数の各々は、前記対応する範囲に対する前記最適フラグメント数であるサブモジュールと、
入力ファイルの前記サイズが該当するファイルサイズ範囲について判断するサブモジュールと、
前記入力ファイルの前記サイズが該当する前記最適ファイルサイズの範囲に対応する前記最適フラグメント数を用いるサブモジュールと、
を含むことを特徴とする請求項９記載のシステム。
【請求項１８】
分散ネットワークに記憶されている符号化されたファイルを復号するコンピュータ実行プロセスであって、
前記ファイルを符号化するために用いられた前記フラグメント数に等しいかまたはそれより大きい符号化されたファイルの一組のフラグメントを検索し、前記ファイルは、所定のファイルサイズに対する最適フラグメント数を用いて耐消去符号化されているプロセスアクションと、
耐消去復号化を用いて前記符号化されたフラグメントを復号して前記符号化されたファイルの復号化バージョンを得るプロセスアクションと、
を含むことを特徴とするコンピュータ実行プロセス。
【請求項１９】
前記符号化されたフラグメントのうちの少なくともいくつかは、前記分散ネットワーク内の１つ以上のピアのストレージ媒体から検索されることを特徴とする請求項１８記載のコンピュータ実行プロセス。
【請求項２０】
前記符号化されたフラグメントのうちの少なくともいくつかは、前記分散ネットワーク上のサーバのストレージ媒体から検索されることを特徴とする請求項１８記載のコンピュータ実行プロセス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ピアツーピア（Ｐ２Ｐ）でデータ配信を行うシステムに関する。
【背景技術】
【０００２】
ピアツーピア（Ｐ２Ｐ）アプリケーションでは、ピアがＰ２Ｐサービスに参加すると、ネットワーク帯域幅及び／またはハードドライブディスクストレージリソースを自身とともにもたらす。Ｐ２Ｐシステムの需要が増大するにつれて、システムの容量も同様に増大する。このことは、クライアントサーバシステムとは著しい対照を成している。クライアントサーバシステムでは、サーバの容量が固定されており、クライアントサーバシステムのプロバイダにより代価が払われる。結果的に、Ｐ２Ｐシステムは、実行するのに経済的であり、拡張可能であるのでクライアントサーバシステムより優れている。
【０００３】
Ｐ２Ｐシステムでは、ピアは、帯域幅だけでなく、他のピアに役立つストレージスペースにも寄与する。ピアにより提供される集合的なストレージスペースは、分散型のストレージクラウドを形成する。データは、クラウドに記憶され、かつクラウドから検索される。Ｐ２Ｐストレージは、多くのアプリケーションに用いることができる。ひとつは分散型のバックアップである。ピアは、Ｐ２Ｐクラウドにそれ自体のデータをバックアップすることができる。ピアの障害時に、データをクラウドから復元することができる。別のＰ２Ｐアプリケーションには、分散型のデータアクセスがある。クライアントは多数のデータ保有ピアから同時に検索することができるので、Ｐ２Ｐ検索は、単一のソースからデータを検索することと比べてより高いスループットを有することができる。別のアプリケーションには、オンデマンドの映画視聴がある。メディアサーバは、動画ファイルをＰ２Ｐクラウドに先んじて散布することができる。クライアントが映画を見ているときに、それはＰ２Ｐクラウド及びサーバの両方から映画をストリームさせることができ、よって、サーバの負荷を減らし、ネットワークバックボーン上のトラフィックを減らして、ストリーミング映画の品質を改善する。
【０００４】
Ｐ２Ｐネットワークのピアはサーバのように動作することができるにもかかわらず、ピアは、１つの重要な態様、即ち信頼性において商用ウェブ／データベースサーバと異なっている。ピアは、通常、その予備のハードディスクスペース及び使用されていない帯域幅でＰ２Ｐアプリケーションをサポートする普通のコンピュータなので、標準的なサーバよりずっと信頼性が低い。ユーザは、時々ピアコンピュータまたはＰ２Ｐアプリケーションをオフにすることを選択することができる。強い要請として、例えば大容量ファイルのアップロード／ダウンロードなどが、Ｐ２Ｐアクティビティのために必要な帯域幅からピアを求めるかもしれない。ピアコンピュータは、ソフトウェア／ハードウェアをアップグレードもしくはパッチする必要性のために、またはウイルス攻撃のためにオフラインであってもよい。コンピュータハードウェア及びピアのネットワークリンクはまた、本質的に、標準的なサーバコンピュータ及び信頼性があるよう設計されたその商用ネットワークリンクより、はるかに信頼性がない。商用サーバ／サーバクラスタは、「シックスナイン」信頼性（アクセス失敗率１０-6を有し、その割合で、年に約３０秒のダウンタイムが認められる）があるように設計されるが、良い消費者ピアは「ツーナイン」信頼性（アクセス失敗率１０-2または毎日約１５分のダウンタイム）だけを有するかもしれず、ピアがたった５０％の信頼性（半分の確率でダウン）またはわずか１０％の信頼性（９０％の確率でダウン）であることも珍しくない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
Ｐ２Ｐバックアップ及びデータ検索などの大部分のＰ２Ｐアプリケーションは、サーバの信頼性レベル（「シックスナイン」信頼性）と同じＰ２Ｐストレージに対する信頼性レベルを維持しなければならない。課題は、ピアの最小限の帯域幅及びストレージリソースを用いて信頼性ある効率的なＰ２Ｐストアをどのように構築するかという点にある。
【課題を解決するための手段】
【０００６】
ピアツーピア（Ｐ２Ｐ）ネットワークにおいてデータを効率的にかつ確実に記憶する適応符号化ストレージシステム及びその方法が示される。適応符号化ストレージシステム及びその方法は、記憶されて配布されるファイルサイズに基づいて、耐消去符号化（ＥＲＣ、erasure resilient coding）用のフラグメント数、即ち、ＥＲＣフラグメント数を調整する。
【０００７】
適応符号化ストレージシステムの多くの実施形態は、Ｐ２Ｐネットワークの効率性及び信頼性を改善する手順を用いる。例えば、１つの実施形態では、サーバコンポーネントのサポートが利用できる場合、小容量の動的データは、より信頼性のあるピアまたはサーバにさえも迂回させられる。また、別の実施形態では、バランスのとれたＰ２Ｐネットワークについて、信頼性がなくて、より小容量のファイルを配布しているピアは、より小容量のデータを配布することができる。
【０００８】
背景技術のセクションで説明した既存のピアツーピアストレージ及び配布システムにおける前述の限界は、本発明による適応符号化ストレージシステムの特定の実施によって解決することができるが、このシステム及びプロセスは、前述の不利な点のいずれかまたは全てを解決する実施に決して限定されない、ということが注目される。むしろ、本システム及びプロセスは、続く説明から明らかになるより広範なアプリケーションを有する。
【０００９】
この概要は、単純化した形式で、概念の選択を導入するために提供され、概念は、詳細な説明で更に後述されるということも注目されるべきである。この概要は、請求された要旨の重要な特徴または基本的特徴を識別することを意図しておらず、また請求された要旨の範囲を決定する際の補助として用いられることも意図していない。
【００１０】
適応符号化ストレージシステムの特定の特徴、態様及び利点は、以下の説明、添付の請求の範囲、及び添付の図面に関してよりよくよく理解されるだろう。
【発明を実施するための最良の形態】
【００１１】
本適応符号化ストレージシステムの好適実施形態の以下の説明では、本明細書の一部を成し、適応符号化ストレージシステムを実施し得る特定の実施例形態が例として示されている添付の図面が参照される。他の実施形態が利用されてもよく、本適応符号化ストレージシステムの範囲から逸脱することなく構造上の変更が成されてもよい、ということが理解される。
【００１２】
１.０  例示的な動作環境：
図１は、本発明を実施することができる適当なコンピュータシステム環境１００の一例を示している。コンピュータシステム環境１００は、適当なコンピュータ環境の単に一例であって、本発明の使用または機能性の範囲に関していかなる限定をも示唆することを意図したものではない。コンピュータ環境１００は、例示的な動作環境１００において示したコンポーネントのうちのいずれか１つまたはコンポーネントの組み合わせに関連するいかなる依存性または必要条件を有していると解釈されてはならない。
【００１３】
本発明は、多くの他の汎用または専用のコンピュータシステム環境またはコンピュータシステム構成で動作することができる。本発明に好適な周知のコンピュータシステム、環境、及び／または構成の例は、パーソナルコンピュータ、サーバコンピュータ、携帯用、ラップトップもしくはモバイルコンピュータまたは携帯電話及びＰＤＡなどの通信デバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な消費者エレクトロニクス、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む配布コンピューティング環境などを含むが、これらに限定されるものではない。
【００１４】
マイクロホン配列１９８のコンポーネントを含むハードウェアモジュールと組み合わせてコンピュータにより実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的なコンテキストで、本発明を記述することができる。通常、プログラムモジュールは、特定のタスクを実行するかまたは特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。本発明はまた、通信ネットワークを介してリンクされているリモート処理装置によりタスクが実行される、分散コンピューティング環境において実施されてもよい。分散コンピューティング環境では、プログラムモジュールは、メモリストレージデバイスを含んでいるローカルコンピュータ記憶媒体及びリモートコンピュータ記憶媒体にあってもよい。図１を参照すると、本発明を実施する例示的なシステムは、コンピュータ１１０の形式で汎用コンピュータデバイスを含む。
【００１５】
コンピュータ１１０のコンポーネントは、処理装置１２０、システムメモリ１３０、及び、システムメモリを含む様々なシステムコンポーネントを処理装置１２０に接続するシステムバス１２１を含むことができるが、これらに限定されるものではない。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、及び、様々なバスアーキテクチャのうちのいずれかを用いるローカルバスを含む数種類のバス構造のうちのいずれであってもよい。一例として、そしてこの例に限らないが、かかるアーキテクチャは、ＩＳＡ（業界標準アーキテクチャ）バス、ＭＣＡ（マイクロチャネルアーキテクチャ）バス、ＥＩＳＡ（エンハンスドＩＳＡ）バス、ＶＥＳＡ（ビデオ電子装置規格化協会）ローカルバス、及びメザニンバスとしても公知のＰＣＩ（周辺部品相互接続）バスを含む。
【００１６】
コンピュータ１１０は、通常様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０がアクセスすることができるいかなる利用可能な媒体であってもよく、揮発性媒体及び不揮発性媒体、着脱自在媒体及び固定媒体、の両方を含む。この例に限らないが一例として、コンピュータ可読媒体は、コンピュータ記憶媒体及び通信媒体を含み得る。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータなどの情報を記憶する任意の方法または技術で実施される揮発性及び不揮発性で着脱自在及び固定の媒体を含む。
【００１７】
コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置もしくは他の磁気記憶装置、または所望の情報を記憶するために用いることができかつコンピュータ１１０がアクセスすることができる他の任意の媒体、を含むが、これらに限定されるものではない。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを、搬送波または他の搬送メカニズムなどの変調されたデータ信号に含み、更に任意の情報交付媒体も含む。用語「変調されたデータ信号」は、信号に情報を符号化するような方法でその特性のうちの１つ以上が設定または変更されている信号を意味する。この例に限らないが一例として、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体及び、音響、ＲＦ、赤外線、及びその他の無線媒体などの無線媒体を含む。上記のいずれの組合せも、コンピュータ可読媒体の範囲内に含まれるものとする。
【００１８】
システムメモリ１３０は、リードオンリーメモリ（ＲＯＭ）１３１及びランダムアクセスメモリ（ＲＡＭ）１３２などの、揮発性メモリ及び／または不揮発性メモリの形式のコンピュータ記憶媒体を含む。起動中など、コンピュータ１１０内の要素同士の間で情報を転送するのを助ける基本ルーチンを含んでいる基本入出力システム１３３（ＢＩＯＳ）は、通常、ＲＯＭ１３１に記憶されている。通常、ＲＡＭ１３２は、処理装置１２０により、直ちにアクセス可能でありかつ／またはそのとき動作中であるデータ及び／またはプログラムモジュールを含む。この例に限らないが一例として、図１は、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、及びプログラムデータ１３７を示す。
【００１９】
コンピュータ１１０は、また、他の着脱自在／固定式、揮発性／不揮発性コンピュータ記憶媒体を含んでいてもよい。一例にすぎないが、図１は、固定式不揮発性磁気媒体から読み取り、またはそこに書き込むハードディスクドライブ１４１、固定式不揮発性磁気ディスク１５２から読み取り、またはそこに書き込む磁気ディスクドライブ１５１、及びＣＤ  ＲＯＭ又は他の光学式媒体などの着脱自在不揮発性光ディスク１５６から読み取り、またはそこに書き込む光ディスクドライブ１５５を示している。例示的な動作環境において用いることができる着脱自在／固定式、揮発性／不揮発性コンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどを含むが、これらに限定されるものではない。ハードディスクドライブ１４１は、通常、インタフェース１４０などの固定式のメモリインタフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１及び光ディスクドライブ１５５は、インタフェース１４０などの着脱自在のメモリインタフェースを介してシステムバス１２１に接続されている。
【００２０】
上記で検討し更に図１に示した、ドライブ及びそれらの関連するコンピュータ記憶媒体は、コンピュータ可読命令示、データ構造、プログラムモジュール、及びコンピュータ１１０のための他のデータを提供する。図１では、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、及びプログラムデータ１４７を記憶するように示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、及びプログラムデータ１３７と同じまたは異なっていてもよいことに注意すべきである。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、及びプログラムデータ１４７には、最低限それらが異なったコピーであることを示すために、本明細書では異なる番号を与えている。ユーザは、キーボード１６２及び、マウス、トラックボールまたはタッチパッドと一般に称されるポインティングデバイス１６１などの入力装置を介してコンピュータ１１０へ命令及び情報を入力することができる。
【００２１】
他の入力装置（図示せず）は、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナ、ラジオ受信機、及び、テレビ受信機または放送ビデオ受信機等を含んでいてもよい。これらの、及び他の入力装置は、しばしばシステムバス１２１に接続されている有線または無線のユーザ入力インタフェース１６０を介して処理装置１２０に接続されるが、他の従来のインタフェース及びバス構造により接続されてもよい。他の従来のインタフェース及びバス構造には、例えば、パラレルポート、ゲームポート、ＵＳＢ（汎用シリアルバス）、ＩＥＥＥ １３９４インタフェース、ブルートゥース（登録商標）無線インタフェース、ＩＥＥＥ ８０２.１１無線インタフェース等がある。更に、コンピュータ１１０はまた、マイクロホンまたはマイクロホン配列１９８などのスピーチまたは音声入力装置及び、パラレル、シリアル、ＵＳＢ、ＩＥＥＥ １３９４、ブルートゥース（登録商標）等の従来の有線インタフェースまたは無線インタフェースを含むオーディオインタフェース１９９を介して接続された他の音声出力装置またはスピーカ１９７を含んでいてもよい。
【００２２】
モニタ１９１または他の種類のディスプレイ装置も、ビデオインタフェース１９０などのインタフェースを介してシステムバス１２１に接続している。モニタに加えて、コンピュータはまた、出力周辺インタフェース１９５を介して接続できるプリンタ１９６のような他の周辺出力装置を含んでいてもよい。
【００２３】
コンピュータ１１０は、リモートコンピュータ１８０などの１つ以上のリモートコンピュータへの論理接続を用いてネットワーク化された環境において動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般のネットワークノードであってもよく、概してコンピュータ１１０と関連して上記で説明した要素の多数または全てを含むが、図１にはメモリストレージデバイス１８１だけを示している。図１に示した論理接続は、ローカルエリアネットワーク(ＬＡＮ)１７１及び広域ネットワーク（ＷＡＮ）１７３を含むが、同様に他のネットワークを含んでいてもよい。かかるネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、及びインターネットにおいて一般的である。
【００２４】
ＬＡＮネットワーク環境において用いられる場合、コンピュータ１１０は、ネットワークインタフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境において用いられる場合、コンピュータ１１０は、通常、モデム１７２、またはインターネットなどのＷＡＮ１７３にわたって通信を確立する他の手段を含む。内臓でもまたは外付けでもよいモデム１７２は、ユーザ入力インタフェース１６０または他の適当なメカニズムを介してシステムバス１２１に接続することができる。ネットワーク化された環境では、コンピュータ１１０と関連して示したプログラムモジュールまたはその一部は、リモートメモリストレージデバイスに記憶することができる。この例に限らないが一例として、図１は、リモートアプリケーションプログラム１８５がメモリデバイス１８１に存在しているように示している。図示したネットワーク接続は例示的であって、コンピュータ同士の間の通信リンクを確立する他の手段が用いられてもよいということは理解されるだろう。
【００２５】
一般に、適応符号化ストレージシステムは、図２で示したネットワークなどのＰ２Ｐネットワークで動作する。特定のデータストリーミングセッションに対して、「サーバ」２００は、データまたはストリーミング媒体を最初に発するＰ２Ｐネットワークのノードとして定義される。「クライアント」（または受信器）２１０は、そのときデータを要求しているノードとして定義される。そして、「サービングピア（serving peer）」２２０は、データの完全なコピーまたは部分的なコピーをクライアントに提供するノードとして定義される。
【００２６】
一般に、サーバ２００、クライアント２１０、及びサービングピア２２０は全て、インターネットなどのネットワークに接続されたエンドユーザノードである。サーバ２００は常にデータを供給することができるので、サーバノードもサービングピア２２０として動作する。サーバノード２００はまた、例えば、利用可能なサービングピアのリストを維持すること、デジタル著作権管理(ＤＲＭ)機能を実行することなどの、サービングピア２２０が実行することができない管理機能を実行することができる。更に、従来のＰ２Ｐスキームと同様に、本明細書で説明している適応符号化ストレージシステムは、ピアノード２２０が更に展開するにつれて、効率性が高まって利益を得る。特に、ピアノード２２０の数が増加するにつれて、データサーバ２００の負荷は減少し、それにより動作するのにより安価になり、一方、各々のクライアントノード２１０は、特定のデータ転送セッションの間非常に良いデータ品質を受信することができる。
【００２７】
更に、特定のノードの役割が変化してもよいということが明らかでなければならない。例えば、特定のノードは、１つの特定のデータ転送においてクライアント２１０として動作することができるが、別のセッションではサービングピア２２０として動作する。更に、特定のノードは、クライアントノード２１０及びサーバ２００またはサービングピア２２０として同時に動作して、１つ以上の他のサービングピアから他のデータを受信しながら１つ以上のデータファイルまたはこれらのファイルの一部を同時に送信することができる。
【００２８】
データ送信の間、クライアント２１０は、最初に、所望のデータのいくつかまたは全てを保持する多数のすぐ近くのピア２２０の位置を確認し、次に多数のピア（サーバ２００を含んでもよい）からデータを受信する。従って、各々のサービングピア２２０は、クライアント２１０のダウンロード要求の一部を果たすことにより全体のアップロード負荷を減少させてサーバを補助するように動作する。その結果、クライアント２１０は、多くのクライアントが存在する場合に特に、多くの場合にもっと良いデータ品質を受信することができる。なんとなれば、サーバ２００を補助する多数のサービングピア２２０がある場合に利用可能な極めて大きいサービング中の帯域幅があるからである。
【００２９】
例示的な動作環境が検討されてきたので、この説明セクションの残りの部分を、適応符号化ストレージシステム及びその方法を具体化しているプログラムモジュールの説明に当てる。
【００３０】
２.０  信頼性のある効率的なピアツーピアストレージ
適応符号化ストレージシステムは、適応耐消去符号化（ＥＲＣ）スキームを提供する。適応耐消去符号化（ＥＲＣ）スキームは、ＥＲＣ符号化を用いるべきか否かを適応的に判断し、最適な信頼性及び効率性のために所定のファイルサイズに対してＥＲＣ符号化に用いられるべき最適フラグメント数を用いる。ファイルのＥＲＣ符号化に用いられるフラグメント数は、この検討のために「ＥＲＣフラグメント数」と称される。以下のパラグラフは、用いられるＥＲＣフラグメント数を検討するだけでなく、ピアツーピア（Ｐ２Ｐ）ストレージの効率性及び信頼性を検討し、更にＰ２ＰネットワークにおけるＥＲＣの使用方法を提供する。次に、適応符号化ストレージシステム及びそのプロセスの様々な実施形態を検討する。
【００３１】
２.１  Ｐ２Ｐストレージの信頼性：データの冗長性
信頼性のない部分を有するシステムに信頼性をもたらす特別の解決法は、冗長性を用いることである。ネットワーク上の各々の個別のピアが信頼性ｐを有していて、所望の信頼性ｐ0を実現する場合、ｎ個のピアに情報を単に複製してもよい。
【００３２】
【数１】
2009527856.tif 000003
【００３３】
ここで、ｎは、情報を保持しているピアの数である。検索時に、クライアントは、情報記憶ピアに一つずつコンタクトすることができる。情報記憶ピアのうちの１つがオンライン状態である限り、情報を確実に検索することができる。
【００３４】
信頼性を実現するとはいえ、単純な複製戦略は効率的ではない。図３は、「シックスナイン」信頼性を実現するのに必要な情報記憶ピアの数を示している。５０％のピア信頼性については、２０のピアに対して情報を複製して記憶することが必要である。このことは、情報を配布して記憶する、２０倍多い帯域幅及びストレージスペースに至らしめる。明らかに、効率性が情報の信頼性と引き替えに犠牲にされている。
【００３５】
２.２  Ｐ２Ｐにおける耐消去符号化
同じ信頼性をなお維持しながら効率性を改善するために、ＥＲＣは役に立つツールであり得る。ＥＲＣは、オリジナルのファイルをｋ個のオリジナルのフラグメント｛ｘi｝，ｉ＝０，・・・，ｋ−１に分割し、その各々は、ガロア体ＧＦ（ｑ）にわたるベクトルである。ここで、ｑは、フィールドの順番である。仮に、６４ＫＢ長のファイルを符号化するとしたら、ｑ＝２16及びｋ＝１６が用いられる場合、各々のフラグメントは、４ＫＢであって、２Ｋワードから成っていて、各々のワードはＧＦ(２16)の要素である。ＥＲＣは、次に符号化フラグメントをオリジナルのフラグメントから生成する。ＥＲＣ符号化フラグメントは、次の演算により生成される。
【００３６】
【数２】
2009527856.tif 000004
【００３７】
ここで、ｃjは符号化フラグメントであり、Ｇiは、ｋ次元生成作用素ベクトルであり、方程式(２)は、ＧＦ(ｑ)にすべてがかかるマトリックス乗算である。復号化時に、ピアは、ｍ個の符号化フラグメントを集め、ここで、ｍはｋと等しいかまたは若干大きい数であり、ｋ個のオリジナルフラグメントを復号することを試みる。このことは、次の方程式を解くことに相当する。
【００３８】
【数３】
2009527856.tif 000005
【００３９】
生成ベクトルにより生成されるマトリックスが最大階数ｋを有する場合、オリジナルのメッセージを回収することができる。
【００４０】
多くの利用可能なＥＲＣがある。特に興味深いものは、リードソロモン(ＲＳ)符号である。ＲＳ符号は、構造化生成作用素ベクトル（structured generator vectors）を用い、ＭＤＳ（maximum distance separable）である。その結果、任意のｋ個の特徴的な符号化フラグメントも、オリジナルのフラグメントを復号することが可能である。ＲＳ符号の他の利点は、符号化フラグメントを生成作用素ベクトルのインデックスｉにより容易に識別して管理することが可能で、それにより、複製ＲＳ符号の検出を容易にするということである。ＥＲＣについての以下の説明では、ＲＳ符号を用いることが仮定されている。しかしながら、適応符号化ストレージシステムは、従来の任意のＥＲＣ数で実施することができる。
【００４１】
２.３  ＥＲＣ：フラグメント数
Ｐ２ＰストレージにおいてＥＲＣを用いることにより、データファイルは、より多くのピアに配布されるが、各々のピアは、オリジナルのファイルの１／ｋサイズである１つの符号化フラグメントを記憶することが必要なだけである。それは、同じレベルの信頼性を実現するのに必要な帯域幅及びストレージスペースにおける全体的な減少をもたらして、効率性を改善する。仮にｎ1を、符号化フラグメントが特定の所望の信頼性レベルを実現するために配布されることが必要であるピアの数であるとする。ＲＳ符号は、ＭＤＳ符号なので、ｋ個の特徴的な符号化フラグメントを保持するｋ個のピアは、オリジナルファイルを回復するのに十分であり得る。利用可能なぴったりｍ個のピアがあるという蓋然性を、２項分布を介して算出することができる。
【００４２】
【数４】
2009527856.tif 000006
【００４３】
よって、ｐ、ｐ0及びｋからｎ1を以下で算出することができる。
【００４４】
【数５】
2009527856.tif 000007
【００４５】
複製率ｒは、以下で定義される。
【００４６】
【数６】
2009527856.tif 000008
【００４７】
複製率ｒは、Ｐ２Ｐクラウドに配布されて記憶されることが必要なファイルのｒ個のコピーとして、効率性についての良い指標である。
【００４８】
図４には、異なるＥＲＣフラグメント数ｋに対して「シックスナイン」信頼性を実現するための所望の複製率を示している。ＥＲＣの使用は、必要な複製率を大いに減じるということがわかる。非ＥＲＣ（ｋ＝１）をＥＲＣフラグメント数であるｋ＝２５６と比較すると、所望の複製率は、１０％のピア信頼性に対してｒ＝１３２からｒ＝１３．１まで、５０％のピア信頼性に対してｒ＝２０からｒ＝２．５ｒまで、更に、９９％のピア信頼性に対してｒ＝３からｒ＝１．０５まで減少する。ＥＲＣは、信頼性を犠牲にすることなく、効率性を改善することができる。
【００４９】
より大なるＥＲＣフラグメント数により、複製率が更に低下することがわかる。５０％のピア信頼性については、ｋ＝８から１６、３２、６４、１２８及び２５６へと進むことにより、ｒ＝５.７５から４.３７５、３.５３、３.０２、２.６８及び２.４８まで複製率の低下をもたらす。対応する効率性の向上は、それぞれ２４％、１９％、１５％、１１％、及び８％である。このことは、より高い効率性のために大なるＥＲＣフラグメント数を用いなければならないということを示唆するようにみえる。
【００５０】
しかしながら、より大なるＥＲＣフラグメント数は、符号化フラグメントを記憶して検索するためにより多くのピアを必要とするということを示唆する。図５に示すように、「シックスナイン」信頼性を実現する符号化フラグメントを保持するために必要とするピアの数が示される。再び、５０％のピア信頼性については、ｋ＝８から１６、３２、６４、１２８、及び２５６へと進むことにより、ｎ1＝４６から７０、１１３、１９３、３４３及び６３０まで情報記憶ピアの数を増加させる。各々ｋを２倍にすると、情報を記憶するのに必要とされる５２％、６１％、７１％、７８％、及び８４％多くのピアという結果になる。ｋを２倍にすることはまた、情報検索の間、コンタクトをとるべきピアの数を少なくとも２倍にすることを必要とする。
【００５１】
大部分の実際的なＰ２Ｐネットワークでは、ピア同士の間の接続を確立することは、些細でない量のオーバーヘッドを必要とする。オーバーヘッドの一部は、適切なピアアイデンティティの検索及び適当なルーティングパスの発見（例えば、分散ハッシュテーブル（ＤＨＴ））によるものであるかもしれない。オーバーヘッドの別の一部は、一方または両方のピアがネットワークアドレス翻訳（ＮＡＴ)の背後にある場合に、例えばＳＴＵＮ（ＮＡＴを介したＵＤＰの単純な横断）などの、特定のＮＡＴアルゴリズムを呼び出す必要のためにある。２つのピアの間の接続を確立するための平均オーバーヘッドをoverheadであると仮定すると（この例では１６ＫＢに設定されている）、サイズｓのファイルを記憶するのに必要な全体のネットワーク帯域幅は、以下であると算出することができる。
【００５２】
【数７】
2009527856.tif 000009
【００５３】
方程式(７)について、より大なるＥＲＣフラグメント数が必ずしも最も良い効率性をもたらすとは限らないということがわかる。その代わりに、小容量のファイルに対して、小なるＥＲＣフラグメント数または非ＥＲＣすら用いなければならない。異なるファイルサイズ及びＥＲＣフラグメント数に対して、方程式(７)で必要とされる全体の帯域幅が算出され、図６に示したカーブが描かれる。異なるＥＲＣフラグメント数同士の間の境界は、特定のＥＲＣフラグメント数に適している最適ファイルサイズの範囲である。例えば、図６の一番下の分布曲線は、非ＥＲＣが用いられるべきファイルサイズの下側の境界を、そして、ｋ＝２のフラグメント数が用いられるべきファイルサイズの上側の境界を示している。興味深いことに、ファイルサイズの境界は、ピアの利用可能性に対して相対的に集中的であるということがわかる。それは、最適ＥＲＣフラグメントのパラメータの選択を大いに単純化する。一般に、約１０ＫＢ未満ファイルに対して、ＥＲＣは用いられるべきではない。フラグメント数ｋ＝２、４、８、１６、３２、１２８及び２５６を有するＥＲＣに対して、最も適したファイルサイズの範囲は、それぞれ、約１０-３３ＫＢ、３３-１００ＫＢ、１００-３１０ＫＢ、３１０-９５０ＫＢ、９５０ＫＢ‐２.９ＭＢ、２．９ＭＢ‐８．９ＭＢ、８.９-２６ＭＢ、＞２６ＭＢである。
【００５４】
２.４  適応ＥＲＣスキーム
適応符号化ストレージシステム及びその方法は、適当なＥＲＣフラグメント数を適応的に選択して、Ｐ２Ｐネットワークに効率的にコンテンツを記憶することを確実にする。図６に構築したファイル境界分布曲線を用いて、システムの一実施形態は、非ＥＲＣ及び、異なるファイルサイズに対するｋ＝２、４、８、１６、３２、６４、１２８、２５６を有するＥＲＣ、を用いることを適応的に選択する。適応ＥＲＣアプローチが固定パラメータＥＲＣと比較され、ネットワーク帯域幅使用の差が、ピア信頼性がそれぞれ５０％及び９９％の図７及び図８に示されている。ｋ＝１（非ＥＲＣ）、８、３２及び２５６といった固定ＥＲＣフラグメント数を用いて比較すると、適応ＥＲＣ方法は、５０％のピア信頼性について６１％、２６％、２５％及び５０％の平均で、さらに、９９％のピア信頼性について５０％、１８％、２９％及び５７％の平均で効率性を改善している。効率性の改善は重要である。
【００５５】
最も一般的な意味で、適応符号化ストレージ方法の一実施形態を図９に示している。プロセスアクション９０２に示すように、適応符号化ストレージシステムは、異なるフラグメント数に対する最適ファイルサイズの境界を算出する。符号化されるべき所定のファイルサイズのファイルが入力される（プロセスアクション９０４）。プロセスアクション９０６に示すように、入力ファイルのサイズが非消去コーディング（ｋ＝１）と一致しないか否かに関してチェックをする。入力ファイルサイズがＥＲＣと一致しない場合、ファイルはＥＲＣを用いずに符号化される（プロセスアクション９０８）。ファイルサイズがＥＲＣファイルサイズの範囲と一致する場合、ファイルは、ＥＲＣ符号化及び入力ファイルのファイルサイズに対応するフラグメント数を用いて符号化される。フラグメント数はそのサイズのファイルに対する最適フラグメント数である（方法アクション９１０）。
【００５６】
本明細書において説明される適応ＥＲＣプロセスの主なアプリケーションは、Ｐ２Ｐバックアップまたは復元においてのものである。ピアは、ネットワーク内の他のピアにファイルをバックアップし、次に、例えばファイルが消失した場合に（例えば、ファイルがコンピュータクラッシュにおいて消失した場合など）、ネットワーク内のピアからファイルを検索することによりこれらのファイルを復元することができる。概して、図１０は、適応符号化ストレージ技術をＰ２Ｐシステムで用いることができる方法を示している例示的な動作フローチャートを示している。図１０の破線または点線によって表される任意及びボックス同士の間の相互接続は、本明細書で説明される適応符号化ストレージシステムの代替実施形態を示し、後述するように、これらの代替実施形態のいずれかまたはすべては、この文書の全体にわたって説明されている他の代替実施形態と組み合わせて用いることができるということに、留意する必要がある。
【００５７】
特に、図１０で示すように、ネットワークのピアにデータをバックアップすることを所望するときなどのデータ転送動作の前に、サーバ２００またはピア２２０は、記憶用の他のピアに転送されるべきデータを符号化する（符号１０００）。適応符号化ストレージシステムは、例えば、ＭＰＥＧ１／２／４、ＷＭＡ、ＷＭＶ等の従来の任意の多数のコーデックで動作することができる。更に、符号化プロセスの間（符号１０００）、サーバ２００またはピア２２０も、データのヘッダ、及びデータ構造を含むコンパニオンファイルの両方を生成する。
【００５８】
上記のように、一つの実施形態では、一旦データが符号化されると（符号１０００）、符号化されたデータパケットは、固定サイズの多数のデータユニットへ分割される（符号１００５）。更に、符号化されたデータのように、データヘッダ及びデータ構造も、符号化されたデータパケットを分割するために用いられるときに、同じ固定サイズの多数のデータユニットへ分割される（符号１００５）。この情報を固定長データユニットへ分割すること（符号１００５）は、データ転送動作の前にピアがメモリブロックを事前割り当てすることを可能にし、それによって、データ転送プロセスの間、コンピュータ的に高価なメモリ割り当て動作を避ける。更に、より小さいデータユニットを使用することにより、各々のピアにより割かれる帯域幅の正確な量以上のデータを記憶しているクライアントまたはピアによる微調整を可能にして、データ転送動作の間、クライアントデータユニットの要求を満足させる。
【００５９】
符号化されたデータ、データヘッダ及びデータ構造をより小さいデータユニットへ分割すること（符号１００５）に加えて、耐消去符号化が用いられる場合、追加のコーディングレイヤは、サービングピアが本質的に信頼性の低い典型的なＰ２Ｐ環境においてさらなる冗長性を提供するために用いられる。特に、上記したように、一つの実施形態では、耐消去符号化がデータファイルに適当であると判断されると、データユニットは、多数のデータブロックに更に分割され、耐消去符号化プロセスは、ファイルを符号化するために用いられる（符号１０１０）。
【００６０】
かかるコーディングの使用（符号１０１０）は、ピアのうちの１つ以上が、ピアのうちの必要なデータを含んでいるものを識別するというクライアントへの要求を単純化すると共に、特定のデータユニットを再構成するのに必要なデータブロックを有するということを確実にする。更に、一つの実施形態では、各々のサービングピア２２０によって用いられる耐消去符号化キーは、サーバ２００によって自動的に各々のピアに割り当てられる。しかしながら、別の実施形態では、各々のサービングピア２２０は、耐消去符号化キーをただ無作為に選択する。次に、各々のピア２２０が最初にクライアントによって接続されるときに、これらのキーはクライアント２１０によって検索される。
【００６１】
一旦、データファイルが最初に符号化され（符号１０００）、データユニットへ分割され（符号１００５）、場合により更に消去符号化される（符号１０１０）と、得られるデータユニットまたはデータブロックは、次に、様々なピア２２０へ配布される（符号１０１５）。この配布（符号１０１５）は、多数のピアに全体または一部として符号化されたデータのブロックまたはパケットが単に提供される、という意味において検討することができる。多数のピアでは、データを検索することを所望するクライアントによって呼び出されると、更にデータを転送するためにキャッシュされるかまたは記憶される。
【００６２】
一旦、データがサービングピア２２０に配布される（符号１０１５）と、クライアント２１０は、クライアントがこのデータをストレージから検索することを所望する場合には、これらのピアへのデータ要求を開始する準備ができている。更に、上記したように、サーバ２００はまた、データをクライアント２１０へ転送するためにピア２２０として動作することができる。
【００６３】
この点で、クライアント２１０は、利用可能なサービングピア２２０のリストを最初に検索することによりデータ転送セッションから開始する。このリストは、サーバ２００から、ピア２２０のうちの１つから、または潜在的なサービングピアを識別する従来の配布ハッシュテーブル（ＤＨＴ）より、直接検索される。一旦、クライアントがピアのリストを検索する（符号１０１０）と、次にクライアントは、各々のサービングピア２２０に接続し、各々のピアから利用可能なファイルのリストを検索する（符号１０２５）。一旦、クライアント２１０が各々のピア２２０の利用可能なファイルのリストを検索すると、次に、クライアントは、クライアントとそれらのピアとの間のネットワーク接続を介してピアの１つ以上から転送されるべきデータのデータヘッダ及びデータ構造を検索する（符号１０３５）。
【００６４】
データヘッダは、一般に、データのチャネル数、各々のチャネルの特性及び特徴（音声サンプリングレート、ビデオ解像度／フレームレート）、使用するコーデック、媒体の著者／著作権所有者、その他などの、データを記述している全体的な情報を含む。従って、データ転送セッションの開始時におけるデータヘッダの検索は、クライアント２２０が必要なツールをセットアップするかまたは初期化することを可能にし（符号１０４０）、データ転送セッションの間、それらのパケットを受信する前に続けて受信したパケットを復号する（符号１０６５）。
【００６５】
更に、特定のデータのデータ構造を検索した（符号１０３５）後に、クライアントは、データ構造を分析し、データ転送プロセスの間に要求することを必要とする転送データのデータユニットのデータユニットＩＤを算出する（符号１０４５）。次に、クライアント２１０は、ピア２２０のうちの１つ以上に、一つずつ、それらのデータユニットを要求する（符号１０５０）。
【００６６】
最後に、一旦、特定のデータパケットを構成しているデータユニットの全てがクライアント２１０の要請に従って回復されると（符号１０５０）、それらのデータパケットは、オリジナルのデータパケットへ再組立てされる（符号１０５５）。再組立てされたデータパケットは、次に復号されて（符号１０６０）、クライアント２１０で復元される（符号１０６５）。
【００６７】
３.０  Ｐ２Ｐストレージ：ポリシー及び設計戦略
Ｐ２Ｐネットワークに記憶されるファイルサイズに基づいてＥＲＣフラグメント数を調整することに加えて、効率性も改善することができる。本明細書で説明された適応符号化ストレージシステムの様々な実施形態は、下記に説明されるように、特定の戦略を用いることにより記憶効率を改善するように設計されている。これらの戦略は、適応符号化ストレージシステムと連動して用いるかまたは任意のＰ２Ｐネットワークで用いることができる。
【００６８】
３.１  Ｐ２Ｐストレージコスト
このセッションでは、ファイルをＰ２Ｐネットワークに記憶することが、「シックスナイン」信頼性を持つサーバにファイルを直接記憶することと比較される。Ｐ２Ｐ解決法はサーバ帯域幅及びコストを低減するが、ファイルをＰ２Ｐストレージに配布するためにより多くの帯域幅を費やすことをピアに要求するということがわかる。ネットワーク帯域幅の全体的な使用は、Ｐ２Ｐ解決法では増加する。クライアントのアップロード帯域幅の増加は、Ｐ２Ｐストレージのコストであると考えられる。異なるピア信頼性及びファイルサイズに対するこのコストは、表１に示されている。
【００６９】
【表１】
2009527856.tif 000010
【００７０】
ピア信頼性が高くかつファイルサイズが大きい場合、Ｐ２Ｐストレージを用いるコストは小さいということがわかる。例えば、９９％の信頼性があるピアに１００ＭＢのファイルを記憶することは、９％のコストを負うだけである。しかしながら、ピア信頼性が低くかつファイルサイズが小さい場合、コストは重大であり得る。
【００７１】
３．２  Ｐ２Ｐストレージポリシー
表１から、Ｐ２Ｐストレージクラウドを用いる以下のポリシーを導くことができる。
【００７２】
ａ）大容量ファイルを記憶するには信頼できないピアを用い、かつ小容量ファイルを記憶するには信頼性のあるピアを用いなければならない。信頼できないピアに大容量ファイルを割り当て、信頼性のあるピアにより小さいファイルを割り当てる場合、Ｐ２Ｐシステムに対するコストはより小さくなる。
【００７３】
ｂ）静的ファイルを記憶するには信頼できないピアを用い、動的ファイルを記憶するには信頼性のあるピアを用いなければならない。静的であるとして変化しないそれらのファイルを呼び出し、動的であるとして常に変わるそれらのファイルを呼び出す。多数の小容量の静的ファイルを、大容量の静的ファイルにまとめて、Ｐ２Ｐストレージクラウドに記憶することができる。単一のファイルの変更により、組み合わされたファイル全体が更新されることが必要となるので、同じ戦略は動的ファイルに対して効果的でない。
【００７４】
このポリシーの必然的帰結は、アプリケーションの状態、ピア状態情報等を記憶するためにＰ２Ｐネットワークが用いられる場合、ネットワークの最も信頼性のあるピアに情報を迂回させなければならないということである。アプリケーションの状態を含むファイルが高信頼性のピア（本質的に、高信頼性のピアは、拡張Ｐ２Ｐネットワークのコアを構成するサブネットワークを形成する）にだけ配置されるということが制限される場合、この複製率及び状態ファイルを更新するコストを大いに低減して、効率性を改善する。
【００７５】
ｃ）信頼できないピアにはより少なく配布されることが許されなければならず、信頼性のあるピアにはより多く配布することが許されなければならない。
【００７６】
ｄ）より小容量のファイルはより高い配布コストが割り当てられ、より大容量のファイルはより低い配布コストが割り当てられなければならない。
【００７７】
ポリシーｃ）及びｄ）は、Ｐ２Ｐバックアップアプリケーション及びＰ２Ｐ検索アプリケーションについてである。ここで、ピアはコンテンツをＰ２Ｐストレージクラウドに配布し、他のピアのためにコンテンツを記憶することができる。バランスのよいＰ２Ｐストレージネットワークによって、各々のピアにその貢献と利益とのバランスをとらせなければならない。前の作業において、帯域幅がＰ２Ｐ記憶アプリケーションの主要な資源であるということが指摘された。ピアの貢献を、ピアが他のピアのために受信して記憶する符号化フラグメントの量であるとする。ピアの利益を、ピアがＰ２Ｐクラウドに配布するコンテンツ量であるとする。低い信頼性がより冗長なデータ記憶装置をもたらすということを考慮すると、信頼できないピアを罰してそれらがより少なく配布されることを可能にし、信頼性のあるピアに報いてそれらがより多く配布されることを可能にしなければならない。かかるポリシーがＰ２Ｐアプリケーションをオンラインに保持することをユーザに奨励して、Ｐ２Ｐネットワークの全体の信頼性を改善しかつ必要な複製率を減少させるので、かかるポリシーはＰ２Ｐ経済において明確な利益を有することができる。
【００７８】
また、高い配布コストをそれに割り当てることにより小容量のファイルの配布を罰して、ピアが比例的により多く貢献することを要求することができる。そして、低い配布コストをそれに割り当てることにより大容量ファイルの配布に報いて、ピアに比例的により少なく貢献させる。当然の結果として、Ｐ２Ｐバックアップアプリケーションは、バックアップ頻度を最小にするように設計されていなければならない。その変化の直後にファイルを直ちに更新する代わりに、多数の変化を大容量ファイルにまとめて、例えば毎晩夜中にＰ２Ｐストレージクラウドに、一度だけそれを更新することが考えられる。
【００７９】
上記のポリシーに沿って設計された適応符号化ストレージシステム及びその方法の一実施形態を、図１１に示している。プロセスアクション１１０２に示すように、分散ネットワークまたはＰ２Ｐネットワークの各々のピアの信頼性が判断される。配布されるべきまたは記憶されるべきファイルが入力される（プロセスアクション１１０４）。ファイルのサイズが判断され（プロセスアクション１１０６）、配布コストが、方程式(７)の期待される記憶帯域幅に基づいてファイルに割り当てられる（プロセスアクション１１０８）。ファイルが大容量ファイルである場合、より高い配布コストを割り当てることができる。ファイルが小容量である場合、ファイルはより低い配布コストに割り当てることができる。ファイルのサイズに基づいて、適応符号化ストレージシステムは、適当な信頼性でピアを選択してファイルを記憶する（プロセスアクション１１１０）。即ち、その信頼性が所定の閾値未満であるピアは、大容量ファイルを記憶して配布するために用いられ、その信頼性が所定の閾値を上回るピアは、小容量ファイルを記憶して配布するために用いられる。
【００８０】
上記のポリシーに沿って設計された適応符号化ストレージシステム及びその方法の他の実施形態を、図１２に示している。プロセスアクション１２０２に示すように、分散ネットワークまたはＰ２Ｐネットワークの各々のピアの信頼性が判断される。配布されるべきまたは記憶されるべきファイルが入力される（プロセスアクション１２０４）。ファイルを、ファイルが静的または動的かを判断するために以前に記憶された同一のファイルと比較する（プロセスアクション１２０６）。ファイルが蓄積された最初の時、ファイルは動的であると仮定される。ファイルに対する頻繁な変化が観察される場合、ファイルは動的であると指定されたままである。ファイルが長期間変わらないことが観察される場合、ファイルは静的であると指定される。動的ファイルは、非常に信頼性のあるピアに記憶される（プロセスアクション１２１０）。（このように、最初は、ファイルはサーバまたは非常に信頼性のあるピアに記憶される。）一旦、ファイルが変化せず、ファイルが静的になっているということがわかると、これらの静的ファイルは再配布されて、より低い信頼性のピアに記憶される。
【００８１】
図１１及び１２に示した実施形態は、分散ネットワークまたはピアツーピアネットワークの全体的な効率性及び信頼性を高めるために、単独でまたは組合せて用いることができるということに注目すべきである。
【００８２】
３.３  サーバコンポーネントのサポートを有するＰ２Ｐストレージ
サーバコンポーネントがＰ２Ｐネットワークを補完するために用いられる場合、大容量で静的なファイルに対してＰ２Ｐストレージを用い、小容量で動的なファイルに対してサーバを用いることができる。大部分のサーバ資源を消費するのは大容量ファイルであるので、Ｐ２Ｐストレージはうまくサーバを補完する。
【００８３】
図１３に示すように、適応符号化ストレージシステム及びその方法の一実施形態は、サーバサポートを有するＰ２Ｐバックアップを用いる。図１３に示したように、ネットワーク内の動的ファイルは、サーバにバックアップされる（プロセスアクション１３０２）。クライアント及び／またはサーバは、次に、それ以上変化せず、静的ファイルに変わりつつある動的ファイルを自動的に検出する（プロセスアクション１３０４、１３０６）。これらの検出された静的ファイルは、次に、プロセスアクション１３０８に示すように、大容量ファイルにまとめられて、さらに、Ｐ２ＰストレージクラウドへＥＲＣを用いて配布される（プロセスアクション１３１０）。このことは、Ｐ２Ｐクラウドに記憶されるファイルのサイズを効果的に増やす。大きいフラグメント数のＥＲＣと組み合わされると、このことは効率性を改善することができる。
【００８４】
図１３に示した実施形態は、単独でまたは、図１１及び１２に示した実施形態と組み合わせて用いられて、分散ネットワークまたはピアツーピアネットワークの全体の効率性及び信頼性を高めることができる。この実施形態は、また、耐消去符号化を用いても、そして、それを用いずとも、使用することができるということが強調されなければならない。
【００８５】
上述した代替実施形態のいずれかまたは全てが、所望の任意の組み合わせで用いられて、追加の複合型の実施形態を生成することができるということに注意する必要がある。要旨が構造上の特徴及び／または方法論的行為に固有の言語で説明されてきたが、添付の請求の範囲において画定される要旨は、上記した特定の特徴または作用に必ずしも限定されないということが理解されるべきである。むしろ、上記した特定の特徴及び作用は、請求項を実施する実例形式として開示されている。
【図面の簡単な説明】
【００８６】
【図１】本明細書で説明されているように、適応符号化ストレージシステム及びその方法を実行する例示的なシステムを構成している汎用コンピュータデバイスを表す一般的なシステム図である。
【図２】本明細書で説明されているように、適応符号化ストレージシステム及びその方法で用いることができる例示的なピアツーピア（Ｐ２Ｐ）ネットワークを示す図である。
【図３】所望の１０-6の信頼性を実現する情報記憶ピアの数を示すグラフである。
【図４】ピア信頼性及び所望の複製率を示すグラフである。
【図５】耐消去符号化を用いて所望する１０-6の信頼性を実現するために必要な情報記憶ピアの数を示すグラフである。
【図６】Ｐ２Ｐネットワーク内の情報ストレージに対するＥＲＣフラグメント数及び関連する適したファイルサイズを示すグラフである。
【図７】（ピア信頼性＝５０％での）適応ＥＲＣ及び固定ＥＲＣを有するＰ２Ｐ構成内のピア同士の間の帯域幅使用量を示すグラフである。
【図８】（ピア信頼性＝９９％での）適応ＥＲＣ及び固定ＥＲＣを有するＰ２Ｐ構成内のピア同士の間の帯域幅使用量を示すグラフである。
【図９】適応符号化ストレージプロセスの一実施形態を示す図である。
【図１０】適応符号化ストレージ技術がＰ２Ｐネットワークにおいて用いられる方法を示す例示的な動作のフローチャートである。
【図１１】Ｐ２Ｐネットワークのストレージ効率性を最適化する手順を実行する適応符号化ストレージシステム及びそのプロセスの実施形態を示す図である。
【図１２】Ｐ２Ｐシステムのストレージ効率性を最適化する手順を実行する適応符号化ストレージシステム及びその方法の別の実施形態を示す図である。
【図１３】サーバのサポートがあるＰ２Ｐバックアップを用いる適応符号化ストレージシステム及びその方法の実施形態を示す図である。
【図１】
2009527856.tif 000011
【図２】
2009527856.tif 000012
【図３】
2009527856.tif 000013
【図４】
2009527856.tif 000014
【図５】
2009527856.tif 000015
【図６】
2009527856.tif 000016
【図７】
2009527856.tif 000017
【図８】
2009527856.tif 000018
【図９】
2009527856.tif 000019
【図１０】
2009527856.tif 000020
【図１１】
2009527856.tif 000021
【図１２】
2009527856.tif 000022
【図１３】
2009527856.tif 000023
【国際調査報告】
2009527856.tif 000024
2009527856.tif 000025