(57)【要約】【課題】大きなデータセットのイレーザ(erasure)符号化された複製を、地理的に分散されたレプリカ・セット上にわたって提供するデータ複製技術を提供する。【解決手段】マルチキャスト・ツリーを使用して、データセットを保存し、転送し、イレーザ符号化する。データのイレーザ符号化は、ソース、中間ノード及び宛先ノードを含むマルチキャスト・ツリー内の種々の位置で実行することができる。一実施態様において、システムは、オリジナル・データセットを保存するソース・ノード、複数の中間ノード、および一意レプリカ・フラグメントを保存する複数のリーフ（葉）ノードを有する。それらのノードは、マルチキャスト・ツリーとして構成され、そのマルチキャスト・ツリーの複数のレベルにおいて分散イレーザ符号化を実行することによって、オリジナル・データを一意レプリカ・フラグメントに変換する。【選択図】図４
2007202146.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク・ノードのマルチキャスト・ツリーを用いて、オリジナル・データを、複数の一意レプリカ・フラグメントを有するレプリカ・セットへ変換する分散方法であって、
少なくとも１つの第１のレベルの中間符号化データ・ブロックを生成するために、少なくとも１つの第１のレベルのネットワーク・ノードにおいて、前記オリジナル・データの少なくとも一部を符号化することによって第１のレベルの符号化を行うことと、
複数のさらなる符号化レベル（ｎ）の各々に対して、少なくとも１つの第ｎのレベルの中間符号化データ・ブロックを生成するために、前記マルチキャスト・ツリー内の少なくとも１つの第ｎのレベルのネットワーク・ノードにおいて、少なくとも１つの（ｎ−１）レベルの中間符号化データ・ブロックの第ｎのレベルの符号化を行うことと、
を有する方法。
【請求項２】
最終の符号化レベルにおいて、少なくとも１つの一意レプリカ・フラグメントを生成するために、少なくとも１つの（ｎ−１）レベルの中間符号化データ・ブロックの最終レベルの符号化を行うことをさらに有する、請求項１に記載の方法。
【請求項３】
前記少なくとも１つの一意レプリカ・フラグメントを前記マルチキャスト・ツリーのリーフ・ノードに保存するステップをさらに有する、請求項２に記載の方法。
【請求項４】
前記リーフ・ノードが最終レベルの符号化を行う、請求項３に記載の方法。
【請求項５】
一意レプリカ・フラグメントは、前記一意レプリカ・フラグメントを前記オリジナル・データの一部分に復号するためのキーを有する、請求項１に記載の方法。
【請求項６】
前記マルチキャスト・ツリーを演算するステップをさらに有する、請求項１に記載の方法。
【請求項７】
前記符号化のステップはイレーザ符号化を有する、請求項１に記載の方法。
【請求項８】
複数の一意レプリカ・フラグメントを有するレプリカ・データセットへオリジナル・データを変換する方法であって、
少なくとも１つの第１のレベルの中間符号化データ・ブロックを生成するために、少なくとも１つのネットワーク・ノードにおいて、前記オリジナル・データの少なくとも一部を符号化することによって第１のレベルの符号化を行うことと、
前記少なくとも１つの第１のレベルの中間符号化データ・ブロックを少なくとも１つの他のネットワーク・ノードへ送信することと、
前記少なくとも１つの他のネットワーク・ノードにおいて、前記少なくとも１つの第１のレベルの中間符号化データ・ブロックの第２のレベルの符号化を行うことと、
を有する方法。
【請求項９】
前記第２のレベルの符号化を行うステップは、前記一意レプリカ・フラグメントの少なくとも１つを生成する、請求項８に記載の方法。
【請求項１０】
一意レプリカ・フラグメントは、前記一意レプリカ・フラグメントを前記オリジナル・データの一部分に復号するためのキーを有する、請求項９に記載の方法。
【請求項１１】
前記第２のレベルの符号化を行うステップが少なくとも１つの第２のレベルの中間符号化データ・ブロックを生成する請求項８に記載の方法であって、
前記少なくとも１つの第２のレベルの中間符号化データ・ブロックを少なくとも１つの他のネットワーク・ノードへ送信することと、
前記少なくとも１つの第２のレベルの中間符号化データ・ブロックの第３のレベルの符号化を行うことと、
を有する請求項８に記載の方法。
【請求項１２】
前記第３のレベルの符号化を行うステップが、前記一意レプリカ・フラグメントの少なくとも１つを生成する、請求項１１に記載の方法。
【請求項１３】
前記符号化のステップはイレーザ符号化を有する、請求項８に記載の方法。
【請求項１４】
オリジナル・データを、複数の一意レプリカ・フラグメントを有するレプリカ・データセットへ変換するシステムであって、
前記オリジナル・データセットを格納するソース・ノードと、
前記一意レプリカ・フラグメントを格納するための複数のリーフ・ノードと、
複数の中間ノードと、
を有し、
前記ソース・ノードと複数のリーフ・ノードと複数の中間ノードとは、論理的に、マルチキャスト・ツリーとして構成され、
前記ノードは、前記マルチキャスト・ツリーの複数のレベルにおいて分散イレーザ符号化を行うことによって、前記オリジナル・データを前記一意レプリカ・フラグメントへ変換するように構成されている、システム。
【請求項１５】
前記リーフ・ノードの少なくとも１つが、中間符号化データ・ブロックを受信し、かつ一意レプリカ・フラグメントを生成するために、前記中間符号化データ・ブロックをさらにイレーザ符号化するように構成されている、請求項１４に記載のシステム。
【請求項１６】
前記中間ノードの少なくとも１つが、中間符号化データ・ブロックを受信し、かつ前記中間符号化データ・ブロックをさらにイレーザ符号化するように構成されている、請求項１４に記載のシステム。
【請求項１７】
前記一意レプリカ・フラグメントは、前記一意レプリカ・フラグメントを前記オリジナル・データの一部分に復号するためのキーを有する、請求項１４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してデータ複製（データ・レプリケーション；data replication）に関し、特に、マルチキャスト・ツリー(multicast tree)を用いた分散(distributed)データ複製に関する。
【背景技術】
【０００２】
電子データの周期的なバックアップとアーカイブは、多くのコンピュータ・システムの重要な役目である。多くの企業にとって、それら企業のコンピュータ・システム・データの使用可能性(availability)と正確度は、企業の継続的な運営にとって決定的に重要である。そのようなものとして、周期的に、重要なデータをバックアップし、アーカイブするために多くのシステムが配備されている。メイン・コンピュータ・システムの所在位置においてデータを単にバックアップするだけでは、災害復旧の仕組みとして不十分であることが今までに明らかになってきている。もし、災害（例えば、火災、洪水等）が、メイン・コンピュータ・システムが所在している場所を襲うならば、全てのバックアップ媒体（例えば、テープ、ディスク等）がオリジナルのデータとともに破壊される公算が大きい。この問題を認識して、多くの企業では、現在、オフサイト（現地外、off-site）バックアップ技術を用い、それによって、重要データはオフサイト・コンピュータ・システムにバックアップされ、その結果、重要データを地理的に遠い位置に所在する媒体上に蓄積することができる。それ以上の保護を与えるために、少なくとも１つのバックアップ・サイトに障害が生じた場合であってもオリジナル・データを回復することができるように、データは、しばしば、複数のバックアップ・サイトに複製される。オフサイト・バックアップでは、一般に、複製されたデータがネットワークを経てバックアップ・サイトに送信される必要がある。
【０００３】
データセットのサイズが大きくなると、複製と保管が問題になる。大きなデータセットの複製に関して２つの主要な問題がある。第１に、同一のデータの複数のコピーがネットワークを介して送信されるので、複製（レプリケーション）は、ソース（送信元）においてバンド幅におけるボトルネック（隘路）を発生させる。この問題は、図１に図示されている。図１は、従来技術のデータ複製技術を示している。この従来技術においては、バックアップされるべきのオリジナル・データセット（参照番号１１６によって表されている）のソースであるソース・ノード１０２が、ネットワーク１１２を経由して、４つのレプリカ・ノード１０４，１０６，１０８，１１０にデータをバックアップする。オリジナル・データセット１１６をレプリカ・ノード１０４，１０６，１０８，１１０の各々で複製するために、ソースは、ネットワーク１１２を経由して、オリジナル・データセット１１６をレプリカ・ノードの各々に送信する。もし、オリジナル・データセットが大きいならば、例えば４テラバイトならば、ソースは合計で１６テラバイトの送信のために、レプリカ・ノードの各々に４テラバイトを別々に４回送信しなければならない。１６テラバイトの送信をソース１０２からすることは、参照番号１１４によって表されているように、ソースのネットワークとの接続部に重大なバンド幅ボトルネックを発生させる。図１に示されている複製技術に関する他の１つの問題は、レプリカ・ノード１０４，１０６，１０８，１１０の各々がバックアップ・データセットの４テラバイト全部を保存しなければならないことである。
【０００４】
図１に図示されている問題に対する１つの公知の解は、図２に示されているように、マルチキャスト・ツリーとして論理的に組織化されたネットワーク・ノードを用いることである。図２は、バックアップ対象のオリジナル・データセット（参照番号２１６によって表されている）のソースであるソース・ノード２０２と、４つのレプリカ・ノード２０４，２０６，２０８，２１０を示している。この解決手法においては、中間ノード２１２，２１４を用いてバックアップ・データ２１６をレプリカ・ノード２０４，２０６，２０８，２１０に運ぶマルチキャスト技術を用いることによって、ボトルネック（図１の符号１１４）は低減する。ここで、ソース・ノード２０２は、複製されたデータ２１６を中間ノード２１２，２１４へ送信する。中間ノード２１２は、次に、複製されたデータ２１６をレプリカ・ノード２０４，２０６へ送信する。中間ノード２１４は、複製されたデータ２１６をレプリカ・ノード２０８，２１０へ送信する。この場合、ソース・ノード２０２は、今や２個のレプリカ・データセット、合計８テラバイトを送信すればよいだけであるから、ソース・ノード２０２におけるバンド幅の要件は、５０％だけ低減されている。図２に示されているマルチキャスト技術は、ソース２０２上のフォワード（転送）負荷を低減するが、レプリカ・ノード２０４，２０６，２０８、２１０の各々はそれでもなおバックアップ・データセットの全４テラバイトを保存しなければならないので、レプリカ・ノードにおける保存要件の問題は軽減されない。
【０００５】
レプリカ・ノードの保存要件に対する１つの解決手法は、イレーザ符号（erasure code；消失符号）の使用である。イレーザ符号は、厳密に複製することのオーバーヘッドを伴うことなく、冗長性を与える。イレーザ符号は、オリジナル・データセットをｎ個のブロックに分割し、それらをｌ個の符号化フラグメントに符号化する。ただし、ｌ＞ｎである。符号化率ｒは、ｒ＝ｌ／ｍ＜１と定義される。イレーザ符号の重要な性質は、どのｌ個の符号化フラグメントからもオリジナルのデータセットを再生することができることである。イレーザ符号化の使用の利点は、レプリカ・ノードの各々が、オリジナルのデータセットよりもかなり小さいサイズをもつｍ個の符号化フラグメントのうちの１つを蓄積するだけでよいということである。イレーザ符号化はこの技術分野においては周知であって、イレーザ符号化のさらに詳細な記述は、John BYers, Michael Luby, Michael Mitzenmacher and Ashu Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data," Proceedings of ACM SIGCOMM '98, Vancouver, Canada, pp. 56-67, Sept. 1998（非特許文献１）に記載されている。この文献は、引用をもって本明細書に挿入されたものとする。
【０００６】
ネットワークを経由してオリジナル・データをバックアップするために、イレーザ符号化をこのように使用することは、図３に示されている。図３は、従来技術のデータ複製技術を示している。その技術においては、バックアップ対象のオリジナル・データセット（参照番号３１６によって表されている）のソースであるソース・ノード３０２が、ネットワーク３１２を経由して４つのレプリカ・ノード３０４，３０６，３０８，３１０に対し、イレーザ符号化を用いてデータをバックアップする。この場合には、ソース・ノード３１６は、複製されたデータを送信するのに先立って、イレーザ符号化を実行し、４つのイレーザ符号化されたフラグメント３１８，３２０，３２２，３２４を発生する。ソースは、４つのイレーザ符号化フラグメントを、ネットワーク３１２を経由してレプリカ・ノードの各々に送信する。イレーザ符号の１つの特徴は、ｎ個の符号化フラグメントを合わせた全体でのサイズは、オリジナル・データセットのサイズより大きいことである。したがって、図１を用いて説明したバンド幅ボトルネックの問題は、この場合には、符号化フラグメントの総体でのサイズの理由によって、むしろ悪化する。ソース３０２からの符号化フラグメントの送信は、参照番号３１４によって表されているように、ソースがネットワークに接続する位置で、著しいバンド幅ボトルネックを生じさせる。
【０００７】
図２に示されているマルチキャスト技術は、図１に示されているバンド幅ボトルネック問題を軽減するが、不幸なことに、図３に示されているバンド幅ボトルネック問題を軽減するために用いることはできない。その理由は、各々のイレーザ符号化フラグメント３１８，３２０，３２２，３２４は、一意(unique)であって、かつ、他の全てのフラグメントとは一次独立でなければならないからである。図２のマルチキャスト技術においては、中間ノード２１２，２１４の各々は、同一のデータ（複製されたデータ２１６）をレプリカ・ノードに転送するが、イレーザ符号化を使用するときにはそうでない。図３に示されているようにイレーザ符号化フラグメント３１８，３２０，３２２，３２４の各々は、一意であり、したがって図２のマルチキャスト技術は、イレーザ符号化に基づくデータ複製技術に関して用いることができない。したがって、現存する技術は、イレーザ符号化されたデータセットの全体を生成するために、単一のノード（すなわち、ソース）に依拠し、複数のユニキャスト(unicast)を用いてそれをレプリカ・ノードに配布する。
【非特許文献１】John BYers, Michael Luby, Michael Mitzenmacher and Ashu Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data（バルクデータの高信頼性分散のデジタル・ファウンテン手法）," Proceedings of ACM SIGCOMM '98, Vancouver, Canada, pp. 56-67, １９９８年９月
【非特許文献２】K. Fu, M. F. Kaashoek, and D. Mazieres, "Fast and Secure Distributed Read-Only File System（高速かつセキュアな分散された読出し専用ファイルシステム）," ACM Trans. Comput. Syst., 20(1): 1-24, 2002
【非特許文献３】R.Koetter and M. Medard, "An algebraic approach to network coding（ネットワーク符号化の代数学的方法）," IEEE/ACM Trans. Networking, vol. 11, pp. 782-795, ２００３年１０月
【非特許文献４】Castro et al., "SplitStream: High-Bandwidth Multicast in Cooperative Environments（スプリット・ストリーム：協力環境における高帯域マルチキャスト）," Proceedings of the 19th ACM Symposium on Operating Systems Principles, pp. 298-313, ２００３年１０月
【非特許文献５】V. N. Padmanabhan et al, "Distributing Streaming Media Content Using Coorperative Networking（協力ネットワーキングを用いた分散ストリーミング・メディア・コンテンツ）," Proceedings of the 12th International Workshop on NOSSDAV, pp. 177-186, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述した問題を解決する、改良されたデータ複製技術が必要である。
【０００９】
したがって本発明の目的は、前述の問題を解決する改良されたデータ複製技術を提供することにある。
【課題を解決するための手段】
【００１０】
本発明は、地理的に分散したレプリカ・セット上にわたり大きなデータセットのイレーザ符号化された複製を供給することによる、改良されたデータ複製技術を提供する。本発明は、マルチキャスト・ツリーを使用して、データセットを保存し、転送し、イレーザ符号化する。データのイレーザ符号化は、ソース、中間ノード及び宛先（デスティネーション）ノードを含むマルチキャスト・ツリー内の種々の位置で行うことができる。マルチキャスト・ツリーのノード上にわたってイレーザ符号化を分散することによって、本発明は上述の従来技術の問題の多くを解決する。
【００１１】
本発明の実施態様によると、システムは、オリジナル・データを複数の一意レプリカ・フラグメントを有するレプリカ・セットへ変換する。システムは、オリジナル・データセットを格納するソース・ノードと、複数の中間ノードと、一意レプリカ・フラグメントを格納する複数のリーフ（葉）・ノードとを有する。これらのノードは、マルチキャスト・ツリーとして構成され、そのマルチキャスト・ツリーの複数のレベルにおいて分散イレーザ符号化を実行することによって、オリジナル・データを一意レプリカ・フラグメントに変換する。
【００１２】
一実施態様においては、オリジナル・データは、複数の一意レプリカ・フラグメントを有するレプリカ・データセットへ変換される。第１のレベルの符号化は、中間の符号化されたデータを生成するために、少なくとも１つのネットワーク・ノードにおいてオリジナル・データを符号化することによって実行される。中間符号化データは、他のネットワーク・ノードへ送信され、当該他のネットワーク・ノードは、次に、その中間符号化データの第２のレベルの符号化を実行する。第２のレベルの符号化では、一意レプリカ・フラグメントを生成してもよいし、あるいは、さらなる符号化のためのさらなる中間符号化データを生成してもよい。一実施態様においては、データの符号化とレプリカ・フラグメントの格納とを実行するネットワーク・ノードが、マルチキャスト・ツリーとして体系づけられる。
【００１３】
他の一実施態様においては、オリジナル・データを、複数の一意レプリカ・フラグメントを有するレプリカ・セットに変換するために、ネットワーク・ノードのマルチキャスト・ツリーが使用される。第１のレベルの符号化は、少なくとも１つの第１のレベルの中間符号化データ・ブロックを生成するために、少なくとも１つの第１のレベルのネットワーク・ノードにおいてオリジナル・データを符号化することによって実行される。次に、複数のさらなる符号化レベル（ｎ）の各々に対して、少なくとも１つの第ｎのレベルの中間符号化データ・ブロックを生成するために、マルチキャスト・ツリー内の少なくとも１つの第ｎのレベルのネットワーク・ノードにおいて、少なくとも１つの（ｎ−１）レベルの中間符号化データ・ブロックの第ｎのレベルの符号化を実行する。最終の符号化レベルにおいて、少なくとも１つの一意レプリカ・フラグメントを生成するために、少なくとも１つの（ｎ−１）レベルの中間符号化データ・ブロックに対する最終レベルの符号化が実行される。その一意レプリカ・フラグメントは、マルチキャスト・ツリーのリーフ・ノードに格納することができる。
【００１４】
利点のある実施態様において、前述の符号化はイレーザ符号化である。
【００１５】
本発明のこれらと他の利点は、次の詳細な説明及び添付の図面を参照することによって、当業者に明らかであろう。
【発明を実施するための最良の形態】
【００１６】
図４は、分散ネットワーク・ノードのマルチキャスト・ツリーを用いて、オリジナル・データを、多数の一意レプリカ・フラグメントからなるレプリカ・データセットに変換する、本発明の原理の概要を示している。
【００１７】
ソース・ノード４０２は、複製されレプリカ・ノード４０４，４０６，４０８，４１０において保存されるべきオリジナル・データ４１６を保持している。ソース・ノード４０２は、オリジナル・データ４１６の一部を中間ノード４１２，４１４に送信する。中間ノードの各々は、オリジナル・データの、当該ノードでの受信部分を符号化することによって第１のレベルのイレーザ符号化を行い、第１のレベルの中間のイレーザ符号化されたデータ・ブロックを生成する。さらに詳しく言えば、中間ノード４１２は、オリジナル・データの、当該ノードの部分をイレーザ符号化して中間イレーザ符号化データ・ブロック４１８を生成する。中間ノード４１４は、オリジナル・データの、当該ノードの部分をイレーザ符号化して中間イレーザ符号化データ・ブロック４２０を生成する。中間ノード４１２は、中間イレーザ符号化データ・ブロック４１８をレプリカ・ノード４０４，４０６へ送信し、中間ノード４１４は、中間イレーザ符号化データ・ブロック４２０をレプリカ・ノード４０８，４１０へ送信する。レプリカ・ノード４０４，４０６，４０８，４１０の各々は、当該レプリカ・ノードが受信した中間イレーザ符号化データ・ブロックをさらにイレーザ符号化して一意レプリカ・フラグメントを生成し、その一意レプリカ・フラグメントは、次に、当該レプリカ・ノードに保存される。さらに詳細に記すと、レプリカ・ノード４０４は、中間イレーザ符号化データ・ブロック４１８をさらにイレーザ符号化して、レプリカ・フラグメント４２２を生成する。レプリカ・ノード４０６は、中間イレーザ符号化データ・ブロック４１８をさらにイレーザ符号化して、レプリカ・フラグメント４２４を生成する。レプリカ・ノード４０８は、中間イレーザ符号化データ・ブロック４２０をさらにイレーザ符号化して、レプリカ・フラグメント４２６を生成する。レプリカ・ノード４１０は、中間イレーザ符号化データ・ブロック４２０をさらにイレーザ符号化して、レプリカ・フラグメント４２８を生成する。イレーザ符号化の原理にしたがって、いくつかのレプリカ・セット・フラグメント４２２，４２４，４２６，４２８を、オリジナルのデータセット４１６を再構築するために使用することができる。
【００１８】
図４から分かるように、本発明の原理によるシステムは、従来技術の問題を解決する。第１に、ネットワーク・ノードの転送負荷を低減するためにマルチキャスト転送（フォワーディング）が用いられるので、従来技術のバンド幅のボトルネック問題が解決される。例えば、４つのレプリカ・ノード４０４，４０６，４０８，４１０が存在するとしても、ソース・ノード４０２は、オリジナル・データの部分を中間ノード４１２，４１４に送るだけである。第２に、レプリカ・ノードの各々はレプリカ・セット・フラグメントを保存するだけであるので、従来技術の保存スペースの問題は解決される。そして、レプリカ・ノードごとにオリジナル・データセット全体を保存しなくてもよくなる。このように、イレーザ符号化タスクをマルチキャスト・ツリー内のノード間に分散させることによって、本発明は、オリジナル・データを一意レプリカ・フラグメントのレプリカ・セットに変換するための改良された技術を提供する。
【００１９】
図４は、本発明を説明するために用いられる簡略ネットワーク図であって、本発明には図４に示されたものとは異なる種々の別の実施形態が可能であることを認識すべきである。例えば、イレーザ符号化の２つのレベルだけが示されているが、追加のレベルのイレーザ符号化をマルチキャスト・ツリー内で実施することができる。さらに、マルチキャスト・ツリーは平衡（バランス）していなくてもよい。例えば、レプリカ・ノード４０４に保存されるレプリカ・フラグメント４２２は２レベルのイレーザ符号化の結果であり、一方、レプリカ・ノード４１０に保存されるレプリカ・フラグメント４２８は３以上のレベルのイレーザ符号化の結果であってもよい。また、図４は、ソース・ノード４０２がオリジナル・データセットの複数部分を中間ノード４１２，４１４へ送信していることを示しているが、別の実施形態においては、ソース・ノード４０２それ自身が第１のレベルのイレーザ符号化を実行し、したがって中間イレーザ符号化データ・ブロックを中間ノード４１２，４１４へ送信してもよい。さらに図４は、レプリカ・ノードが最終レベルのイレーザ符号化を実行してレプリカ・フラグメントを生成することを示しているが、そのような最終レベルのイレーザ符号化を中間ノードで実行し、保存用レプリカ・ノード自体がイレーザ符号化を行うことなくレプリカ・フラグメントを保存用レプリカ・ノードへ伝送してもよい。さらに、マルチキャスト・ツリー内のノードのうちのあるものがイレーザ符号化を行わないようにすることができる。マルチキャスト・ツリー内の全てのノードは、少なくとも、保存及び転送機能を備えていて、そして、イレーザ符号化機能を追加的に備えることができる。１つの重要な特徴は、イレーザ符号化をマルチキャスト・ツリー内のどこででも、すなわち、ソース、中間ノードまたはレプリカ・リーフ・ノードにおいて実施することができるということである。
【００２０】
本発明の原理にしたがって分散ネットワーク・ノードのマルチキャスト・ツリーを用いてオリジナル・データをレプリカ・データセットに変換するために、図４に一般的に示されているシステムに対して種々の組み合わせと選択肢を適用することができることは、当業者にとって本明細書の記述から明らかであろう。
【００２１】
前掲の記述及び本明細書における以下の記述によって、本発明の種々の実施形態の機能的な説明が与えられる。本明細書で記述されるネットワーク・ノードとコンピュータの機能は、例えば、周知のコンピュータ・プロセッサ、メモリ装置、記憶装置、コンピュータ・ソフトウエア及びその他の要素を用いて実現することができることを、当業者は認識するであろう。そのようなコンピュータの上位レベルでのブロック図が図５に示されている。コンピュータ５０２は、コンピュータ５０２の全動作を規定するコンピュータ・プログラム命令を実行することによってコンピュータ５０２のそのような動作を制御するプロセッサ５０４を含んでいる。コンピュータ・プログラム命令は、記憶装置５１２（すなわち磁気ディスク）に格納され、コンピュータ・プログラム命令の実行が要求されるときにメモリ５１０にロードされることができる。したがってコンピュータの動作は、メモリ５１０及び／または記憶装置５１２に格納されているコンピュータ・プログラム命令によって規定され、コンピュータの機能は、プロセッサ５０４がコンピュータ・プログラム命令を実行することによって制御されるであろう。コンピュータ５０２は、また、ネットワークを経由して他のノードと通信をするための少なくとも１つのネットワーク・インターフェース５０６を含んでいる。コンピュータ５０２は、また、当該コンピュータ５０２とユーザとの対話を可能にする装置（例えば、ディスプレイ、キーボード、マウス、スピーカ、ボタン等）を表わす入出力部（Ｉ／Ｏ）５０８を含んでいる。当業者は、実際のコンピュータの実装には、他の要素も含まれていることと、図５は、そのようなコンピュータの要素のいくつかの、説明のための上位階層での表示であることを了承するであろう。
【００２２】
ここで、図６乃至図１２を用いて本発明の実施形態を説明する。図６は、クライアント・ノード６０２がアプリケーション６０４を実行する様子を示している。アプリケーション６０４は、クライアント・ノード６０２上で実行される任意のタイプのアプリケーションであってよい。本明細書の「背景技術」の欄に記載したように、アプリケーションは、離れた場所にあるノードに対し保存用のデータを複製することを望んでいるとする。アプリケーション６０４は、離れたノード上に複製され保存されることをそのアプリケーション６０４が望んでいるあるオリジナル・データ６０６を、既に識別していると仮定する。図６に示されている実施形態において、複製システムへのリンクは、クライアント・ノード６０２上で実行するデーモン６０８を介している。アプリケーション６０４のようなアプリケーションは、デーモン６０８を介して複製システムと相互作用をする。例えばこの相互作用は、アプリケーション・プログラミング・インターフェース（ＡＰＩ）を介することができる。一実施形態においては、アプリケーション６０４は、データが複製されるべきことを、下記のＡＰＩコールを用いて指示する：
create_object(objname, buf, len, &objmeta)
ただし、
objnameは、オブジェクト（対象）を識別するためにアプリケーションによって与えられた名称であり、
bufは、オリジナル・データが位置付けられているクライアント６０２内の記憶場所へのポインタであり、
lensは、保存されるデータについての、bufから開始する長さであり、
&objmetaは、以下にさらに詳細に説明するように、デーモンによって生成されたオブジェクト・メタデータのメモリ・アドレスである。
【００２３】
したがって、アプリケーション６０４がデータを複製することを望むときには、アプリケーション６０４は、図６において参照番号６１０で表されているように、前述のＡＰＩコールをデーモン６０８に送る。デーモンは、そのＡＰＩコール６１０を受信すると、次のようにオブジェクト・メタデータ６１２を生成する。
【００２４】
objnameは、例えばK. Fu, M. F. Kaashoek, and D. Mazieres, "Fast and Secure Distributed Read-Only File System," ACM Trans. Comput. Syst., 20(1): 1-24, 2002（非特許文献２）に記載されているような、コリジョン（衝突）防止機能付き暗号ハッシュを用いてOBJECT-ID  ６１４を生成するために使用される。OBJECT-ID  ６１４は、メタデータを識別するために複製システムによって用いられる一意の識別子である。次にデーモン６０８は、オリジナル・データ６０６を固定サイズのデータのブロックに分割し、各々のそのようなブロックに識別子を割り当てる。ブロックのサイズは、（ブロック・サイズとともに線型に増加する）符号化オーバーヘッドと、ネットワークのバンド幅の使用量との間のトレードオフ（妥協）である。適切なブロック・サイズは、実装の仕方が異なるとともに異なる。本実施形態においては、ブロック・サイズは２０４８バイトと仮定する。ブロック識別子は、ブロックの内容をハッシュ演算することによって割り当てることができる。図６に示されている例に対してデータの４つのブロックを仮定すると、４つの識別子が以下のように表される。
【００２５】
【表１】
2007202146.tif 000003
【００２６】
これらのブロック識別子は、参照番号６２２において示されているように、メタデータ６１２内に保存される。識別子を割り当ててデータセット・ブロックを同定した後、デーモン６０８は、最終のレプリカ・データセット（すなわちレプリカ・フラグメント）が保存されるレプリカ・ノードを指定する。図６の例では、レプリカ・フラグメントを保存する３つのレプリカ・ノード６１６，６１８，６２０があると仮定する。デーモン６０８は、どのデータ・ブロックがどのレプリカ・ノードに保存されるかを選択し、参照番号６２４として示されているように、メタデータ６１２内に識別符号を保存する。図６に示されているように、BLOCKID01によって識別されるブロックに関連するレプリカ・フラグメントは、レプリカ・ノード０（ノード−０）及びレプリカ・ノード２（ノード−２）で保存され、BLOCKID02によって識別されるブロックに関連するレプリカ・フラグメントは、レプリカ・ノード０及びレプリカ・ノード１（ノード−１）で保存され、BLOCKID03によって識別されるブロックに関連するレプリカ・フラグメントは、レプリカ・ノード１及びレプリカ・ノード２で保存され、BLOCKID04によって識別されるブロックに関連するレプリカ・フラグメントは、レプリカ・ノード０及びレプリカ・ノード２で保存されることになる。
【００２７】
レプリカ・ノードセット内のノード数は、複製アプリケーションの使用可能性及び性能要件に基づいて定められる。例えば、大企業のためのバックアップを行うデータ・センターは高い障害回復力を必要とするであろうが、その高い障害回復力は、大きなレプリカ・ノードセットを必要とするであろう。
【００２８】
この点で、対象メタデータ６１２は完成し、各データ・ブロックは少なくとも１つのレプリカ・ノードに割り当てられる。次に、デーモン６０８は、データの各ブロックを、それが割り当てられているレプリカ・ノードに対して、マルチキャスト・ツリー６２６を経由して送信する。図６には、データ・ブロックの、それぞれのレプリカ・ノードへの、この送信が示されている。例えば図６は、識別子<BLOCKID01>とこの識別子<BLOCKID01>に関連する実際のデータとを有するデータ６２８が、ノード−０  ６１６に送信されることを示している。識別子<BLOCKID01>とこの識別子<BLOCKID01>に関連する実際のデータとを有するデータ６３０が、ノード−２  ６２０へ送信されることが示されている。識別子<BLOCKID02>とこの識別子<BLOCKID02>に関連する実際のデータとを有するデータ６３２が、ノード−０  ６１６へ送信されることを示されている。識別子<BLOCKID02>とこの識別子<BLOCKID02>に関連する実際のデータとを有するデータ６３４が、ノード−１  ６１８へ送信されることが示されている。図６は、同様に、<BLOCKID03>及び<BLOCKID04>に対する識別子とその識別子に関連するデータが、それらのそれぞれのレプリカ・ノードに送信されることを示している。
【００２９】
データがマルチキャスト・ツリーをトラバース（ツリー構造の要素をたどる操作）するにしたがって、図４を用いて前述したように、データは、ツリー中の種々のノードにおいて分散された態様で、イレーザ符号化される。前述したように、最初のレベルの符号化は、マルチキャスト・ツリー６２６内で起きてもよいし、または、デーモン６０８内で起きてもよいことを理解すべきである。さらに、最終レベルの符号化は、マルチキャスト・ツリー６２６内の中間ノードで起きてもよいし、または、レプリカ（リーフ）ノード６１６，６１８，６２０で起きてもよい。図６には明示的には表されていないが、クライアント６０２とレプリカ・ノード６１６，６１８，６２０は、論理的にはマルチキャスト・ツリー６２６の要素である。マルチキャスト符号化についてのさらなる詳細は、図１１を用いて後述する。
【００３０】
イレーザ符号化の結果は、レプリカ・ノードの各々に格納されたレプリカ・フラグメントである。フラグメントは、オリジナル・データの一定サイズの塊（チャンク）のイレーザ符号化された表現である。レプリカ・ノードでは、レプリカ・フラグメントは、ブロック識別子によって索引付けられて（インデックスされて）保存される。イレーザ符号化されたデータのほかに、各フラグメントは、（さらに詳細に後述されるように）データを符号化するために使用される符号化キーを含んでいる。これによって各フラグメントは自己完結され(self-contained)、データのブロック全体は、必要なフラグメントの検索(retrieval)のときに復号（デコード）される。図６には、保存されているフラグメントが示されている。例えばフラグメント６３６は、ブロック識別子<BLOCKID01>で索引付けられて示されている。フラグメント６３６は、キーと符号化されたデータとを含んでいる。フラグメント６３６は、ノード−０  ６１６に保存されて示されている。その他のフラグメントも同様に図６に示されている。
【００３１】
全てのフラグメントがそれぞれのレプリカ・ノードに保存された後に、デーモン６０８は、オブジェクト・メタデータ６２２の、メモリ内の位置をアプリケーション６０４に返す。これは、アドレス&objmetaを指定して行われたＡＰＩコールからの復帰の結果である。この段階では、オリジナル・データ６０６は、レプリカ・ノードに保存された複数の一意レプリカ・フラグメントを有するレプリカ・データセットにバックアップされている。
【００３２】
データの検索は、レプリカ・データセットがレプリカ・ノードに保存された後、任意のときにアプリケーション６０４によって実施することができる。例えば、クライアント・ノード６０２でのオリジナル・データ６０６の喪失につながる事象の結果として、アプリケーション６０４は、レプリカ・ノードに保存されている複製されたデータの検索を要求する。１つの実施形態においては、データ検索はブロックごとに行われ、アプリケーション６０４は、以下のＡＰＩコールを用いて、検索すべきデータ・ブロックを指定することができる：
read_block(BlockID, &buf, &&len)
ただし、
BlockIDは、検索されるべき特定のブロックの識別子であり；
&bufは、そのブロックが保存されるべきメモリ・ロケーションを示すポインタを格納しているメモリ内のアドレスであり；
&lenは、当該データ・ブロックの長さを格納しているメモリ内のアドレスである。
したがって、アプリケーション６０４がデータ・ブロックを検索することを望むときには、アプリケーション６０４は、前述のＡＰＩコールをデーモン６０８に送る。その要求に記述されているBlockIDに基づいて、デーモン６０８は、オブジェクト・メタデータ６１２にアクセスすることによって、当該ブロックの符号化されたバージョンが保存されているレプリカ・ノードを判定する。デーモンは、次に、識別されたブロックに関連するフラグメントを当該レプリカ・ノードから検索し、そのフラグメントを復号してオリジナルのデータ・ブロックを再構築する。回復されたデータ・ブロックは、メモリ中に保存され、デーモン６０８は、&bufによって識別されるメモリ・ロケーション内に、ブロックが格納されたメモリ・ロケーションに対するポインタを返す。デーモン６０８は、当該データ・ブロックの長さを保存しているメモリのアドレスを&len内に返す。このようにして、アプリケーション６０４は、オリジナル・データ６０６の全体を再構築することができる。なお、前述の実施形態は、アプリケーション６０４がブロックごとに実施する手法を用いてオリジナル・データ６０６を再構築する技術を記述している。別の実施形態においては、オリジナル・データセットの全体は、単一のＡＰＩコールを用いて回復することができる。この場合には、アプリケーションは、OBJECT-IDをデーモン６０８に出力し、デーモン６０８は、関連するデータ・ブロックの全てを、自動的に検索する。
【００３３】
アプリケーション６０４がレプリカ・データセットをレプリカ・ノードに保存する必要がもはやなくなったとき、アプリケーション６０４は、保存されているレプリカ・データセットを破壊することを指示を伴う適切なコマンドをデーモン６０８に送信することができる。１つの実施形態においては、アプリケーション６０４は、以下のＡＰＩコールを用いて、レプリカ・データセットを破壊すべきことを指示することができる：
destroy_object (objmeta)
ただし、objmetaは、対象のメタデータのメモリ・アドレスである。
この命令を受信すると、デーモン６０８はメタデータ６２２にアクセスし、符号化フラグメントが保存されているレプリカ・ノードに対し適切な適切なコマンドを送信して、そのレプリカ・ノードに対し、フラグメントを破壊することを指示する。
【００３４】
本発明の一実施形態に基づく、マルチキャスト・ツリーを用いたイレーザ符号化のさらに詳細な説明を以下に記述する。最初に、図７乃至図１０を用いて、マルチキャスト・ツリーを生成する技術を記述する。次に、図１１を用いて、マルチキャスト・ツリー内でイレーザ符号化を行う技術を記述する。
【００３５】
前述したように、create_object(objname, buf, len, &objmeta)命令をデーモン６０８が受け取り次第、マルチキャスト・ツリー６２６が定義されなければならない。最適化されたツリーは、所定の中間ノードへの及びその所定の中間ノードからの情報の流れ量が着信(incoming)及び発信(outgoing)ノード容量に最適に整合する場合に、生成することができる。分散プロセスにおいて協動するように用意されたノードの集合Ｖがあると仮定する。各ノードｖ∈Ｖは、ｖへの着信（ｂin(ｖ)）及び発信（ｂout(ｖ)）アクセスに対する負荷容量(capacity budget)を定めている。これらの容量は、全ての着信および発信容量のうちの最小値（ｂmin）を用いて、容量単位の整数倍へ写像（マップ）される。ノードｖに対しては、着信容量Ｉ(ｖ)は、
【００３６】
【数１】
2007202146.tif 000004
【００３７】
であって、発信容量Ｏ(ｖj)は、
【００３８】
【数２】
2007202146.tif 000005
【００３９】
である。各単位容量は、単位時間当たりｕ＝ｌ／ｍシンボルの伝送に対応する。次数（degree：ノードにおける最大着信シンボルと最大発信シンボルとの和）情報を用いると、目標は、各辺（edge：ノードとノードとを結ぶ直線）上のシンボル数を当該辺の容量内に保つ分散ツリー（分散木）を構成することである。
【００４０】
図７乃至図１０のフローチャートを用いて、マルチキャスト・ツリーの生成を説明する。ステップ７０２は、初期化ステップを示す。ツリー中の各ノードに対して、ｖに端を発するサブツリーにおける宛先の数を表す値ｔvは維持されるものとする。ソース・ノードｓに対して、値ｔsは常にｍ（宛先の総数）である。全ての宛先ｄ∈Ｄに対するｔdの値は、常に１である。初期時には、ソースｓは、ｍ個の全ての宛先へ直接接続される。もし、Ｏ(ｓ)≧１ならば、ソースは宛先を直接サポートすることができ、ツリー中に中間ノードは必要でない。そうでなければ、ソースにかかる負荷を軽減するために、中間ノードを加える必要がある。過負荷のノードを識別することを容易にするために、Ｏ(ｓ)−Ｒo(ｓ)をＤと定義する。ただしＲo(ｖ)は、ｖから送信されるシンボル数である。ツリー構成アルゴリズムは、もしＤが負ならば（すなわち、ｓが過負荷ならば）、Ｄを最小にすることを目指す。
【００４１】
Ｄが負であるとする。そのことは、ソースが過負荷であることを示している。ｓからいくらかの負荷を取り除くことができるノードｖ∈Ｖを見つけることが必要である。この場合には２つの重要な問題がある。すなわち、１）Ｖの中のどのノードがその目的のために選択されるか、２）そのノードは当該ソースのどの子ノード（チルドレン：children）を引き継ぐか、という問題である。ステップ７０４において、Ｖ＝Φ（すなわち、使用可能ノードの集合が空集合である）であり、かつ、Ｄ＜０（すなわち、ソースが過負荷である）であるか、否かが決定される。もし、そうであるならば（「はい」）、アルゴリズムは終了する。ステップ７０４における判断が否（「いいえ」）ならば、アルゴリズムは、ステップ７０６において、（関数Select-Nodeを用いて）ソースの最大数のチルドレンを引き継ぐことができるノードｖiを選択する。このノードは、シンボルの最大数（ソースのチルドレンｉの全てに対するｔiの値を用いて決定される）の流れをサポートすることができる着信及び発信容量の両方を有するノードである。図８を用いて、Select-Node関数をさらに詳細な記述する。ステップ７０６においてｖiが選択されると、次に、ステップ７０８において、ステップ７０６において選択されたノードｖiが使用可能のノードの集合Ｖから除外され、Ｄが前述のように再計算されて、ｉが１だけインクリメントされる。ソースの負荷がその受け入れ限度以下に低減してしまうまで、または、さらなる中間ノードが残らなくなるまで、アルゴリズムは、判断のステップ７０４に制御を渡す。
【００４２】
Select-Node関数（ステップ７０６）の詳細が、図８のフローチャートに示されている。Select-Node関数の入力の際して、ステップ８０２において、子ノード（Ｃ）の候補集合が、入力頂点(input vertex)Ｖの全ての子ノードの集合(Children)として初期化される。ステップ８０４において、その集合は、カバレッジ（ｔc）をキーとして、カバレッジの減少する順序でソート(SORT)される。任意の周知のソート手順を使用することができる。ステップ８０６，８１４，８１６は、インデックスＪを用いて集合Ｃの全域にわたって反復するループを形成する（｜Ｃ｜は集合Ｃのサイズである）。したがって、Ｃ内の各要素に対して、このノード（Ｊ）の全て子ノードのカバレッジの和（ｔj）が計算される。図１０を用いてこの計算を以下にさらに詳細に議論する。ステップ８１６において、各ノードＪに対するカバレッジ（Ｚj）が、ステップ８１４で計算された和とシンボルの最大数（ｎ）とのうちの小さい方に割り当てられる。ステップ８０６における反復条件が満たされなくなると、制御はステップ８０８に渡され、ステップ８０８において、選択されるべき頂点のインデックスを計算する関数が呼び出される。図９のフローチャートを用いてこの関数を説明する。選択されたノードに対する新しいカバレッジ値ｔv*は、ステップ８１０において更新される。関数NumChildによって返される頂点は、ステップ８１２において、呼び出し側プログラムに返される。
【００４３】
関数NumChild（ステップ８０８）の詳細が図９のフローチャートに示されている。関数NumChildの目標は、最大容量（頂点がサポートすることができる着信及び発信シンボルの数）をもつ頂点のインデックスを求めることである。最大容量を有する頂点のインデックス（ＭＡＸ）と反復のインデックスｊとはステップ９０２で初期化される。ｊは頂点の集合（Ｖ）の全域にわたるループを生成する。ループ条件はステップ９０４で検査され、ステップ９１０で継続される。もし、ループが完了していなければ、制御はステップ９０６に移り、ステップ９０６において、容量(Capacity)は、ノード（ｊ）における着信シンボルと送信シンボルとのうちの小さい方に初期化される。もし、所望のカバレッジＺj（ステップ８１６で計算された）が考察対象のノード（ｊ）（ステップ９０８において検査された）の容量以下ならば、このノードが候補であるとして、制御はステップ９１４に渡される。ステップ９１４において、容量は現在の最大値と比較される。もし、その容量の方が現在の最大値よりも大きいならば、ステップ９１６において、最大容量ノードのインデックス（ＭＡＸ）はｊに設定される。ループはステップ９１２で終了し、このステップ９１２において、最大容量ノードのインデックスが返される。
【００４４】
図１０は、ステップ８１４からの、考慮対象のノード（ｊ）の全ての子ノードのカバレッジ値の和を計算するために実行されるステップのフローチャートを示している。ステップ１００２において、ＫとＳＵＭはゼロに初期化される。ステップ１００４において、Ｋ≦Ｊか否かが判定される。もし、Ｋ≦Ｊならば、ステップ１００６において、ｔkがＳＵＭの値に加算され、Ｋが１だけインクリメントされ、制御がステップ１００４に渡される。ステップ１００４の判断が否のときには、ステップ１００８において、ＳＵＭの値が返される。
【００４５】
図１１を用いて、前述のアルゴリズムにしたがって定義されたマルチキャスト・ツリーを用いた、イレーザ符号化のためのアルゴリズムを次に述べる。一般に、生成されたイレーザ符号化データに対して、所与のブロックがｎ個の等サイズのフラグメントに分割され、次にそのフラグメントがｌ個のフラグメントに符号化される。ただしｌ＞ｎである。ステップ１１０２に表されているように、ｘ1，ｘ2，…，ｘi，…ｘnは、ｎ個のオリジナル・フラグメントのｊ番目のバイトを表す入力シンボル(InputSymbols)であるとする。ステップ１１０４に示されるように、ランダムな係数が、所与の代数体サイズ（本実施形態では２16）に対して生成される。ステップ１１０６において、符号化された出力シンボル(OutputSymbols)ｙ1，…，ｙiが、大きな有限体上で入力シンボルｘiの線形結合をとることによって構成される。入力シンボル数に対する出力シンボル数の比ｒは、イレーザ符号の伸縮係数(stretch factor)（ｒ＝ｌ／ｍ）と呼ばれる。もしｒ＞１ならば、オリジナル・データを再構築するために、任意のｎ個のシンボルを選択することができる。障害が存在する場合であってもデータが使用可能であるために、ｌ個のシンボルに対応するｌ個のフラグメントをｍ個のシステム上に均一に分散する。目標は、ｋ個の障害が存在する場合に、任意のｎ個のフラグメントの検索(retrieval)を可能にすることである。もし、ｋ×（ｌ／ｍ）＞ｎならば、レプリカ・セットから選択されるｋ個のノードからオリジナル・データ・ブロックを高い確率で再生することができることを証明することができる。
【００４６】
オリジナル・データの線形変換は、ｙ＝ｇ1ｘ1＋ｇ2ｘ2＋…＋ｇnｘn、すなわち、
ｙ＝ＧＸT          (1)
のように表すことができる。ただし、Ｇは符号化係数ベクトルであり、ＸTはベクトルＸ＝［ｘ1 ｘ2 … ｘn］の転置ベクトルである。オリジナル・シンボルｘiを再構築するために、もし、（ｙiｓ）で表される前述の式が一次独立ならば、少なくともｎ個の符号化されたシンボル（ｙiｓ）が必要である。このことは、出力シンボルが、再構築のために相異なっていなければならないということをも意味している。
【００４７】
前述のように、本発明の一実施形態によると、イレーザ符号化されたデータ・フラグメントは、マルチキャスト・ツリー上にわたって分散される。マルチキャスト・ツリーを用いる分散の目標は、各ノードにおけるレートまたは転送負荷をできるだけ低くすることであって、その場合には、ツリー中の各中間ノードが符号化処理に関与する。各ノードはｊ個の入力シンボルｘi，…，ｘjの集合を受け取り、各発信辺（発信エッジ）に沿って、ｈ個の一次独立な出力シンボルｙ1，…，ｙhを生成する。一次独立性は、十分なサイズ（２16）の有限体内にある符号化係数をランダムに選択してｙを生成することによって、非常に高い確率（１−２-16）で保証される。この技術は、R.Koetter and M. Medard, "An algebraic approach to network coding," IEEE/ACM Trans. Networking, vol. 11, pp. 782-795, Oct. 2003（非特許文献３）に記載されている。
【００４８】
出力符号化シンボルの完全な集合をソースで生成する代わりに、本発明の原理による符号化は、段階的に符号化する。この場合には、各中間ノードは、その中間ノードが受信した情報に基づいて、必要に応じて、追加のシンボルを生成する。図１２に示されている例は、ｎ＝４，ｌ＝１０として、この手法を示している。図１２に示されるように、宛先（リーフ）ノード１２０６，１２１０，１２１２，１２１４，１２１６でのｌ＝１０の出力シンボルを生成するために、ソース・ノード１２０２とともに中間ノード１２０４，１２０８の両者が部分的符号化を行うマルチキャスト・ツリーが使用されている。
【００４９】
ソースから宛先（ツリーのリーフ）への経路中の中間ノードによる符号化の結果、オリジナル・シンボルの変換が反復される。したがって、式(1)によって与えられるように、宛先における出力シンボルは、
ｙ＝ＧnＧn-1…Ｇ1ＸT        (2)
ｙ＝ＧfＸT                  (3)
になる。
復号するために、多項式Ｇf（すなわちキー）は、システム中で生成された各フラグメントとともに含まれている。これらのキーは、図６を用いて前述されている。
【００５０】
ｋという冗長係数を用いてデータのブロックを複製することを考えよう。分散Ｔのために使用されるマルチキャスト・ツリーについて、ソースＳはツリーのルートを表し、Ｖは中間ノードの集合であり、宛先ノードの集合Ｄはリーフ・ノードである。各中間ノードｖ∈Ｖに対するカバレッジｔ(ｖ)を、ｖによってカバーされるリーフ・ノードの数と定義する。データ転送の最後に、各宛先ノードは、そのノードに対するｌ／ｍシンボルの割り当て分を受信しなければならない。したがって任意の中間ノードは、その子ノードの各々のに対して充分なシンボルを転送しなければならない。その上、一次独立性の仮定から、もし、あるノードの子ノードの数が冗長係数よりも大きいならば、そのノードはオリジナル・データを再構築することができなければならないということが要求される。したがって、システム内の各ノードによって受信される入力シンボルの数ｉｎ(ｖ)は、次式で与えられる。
【００５１】
【数３】
2007202146.tif 000006
【００５２】
ただし、ｋは符号化の冗長係数である。
【００５３】
リーフ・ノードから出発してツリーをルートに向かって遡りながら、式(4)は、マルチキャスト・ツリーの各辺を流れるシンボルの数を定めるために適用される。
【００５４】
当業者には理解されることであるが、本発明の原理に基づくシステムの実際の実装を設計するにあたっては、種々の実装設計上の論点が生ずるであろう。例えば、そのような設計上の論点の１つは、障害とデッド・ロックとに関連する。デッド・ロックの回避のための、及びノード障害を処理するための種々の公知技術を、本発明の原理にしたがうシステムに関連して使用することができる。例えば、Castro et al., "SplitStream: High-Bandwidth Multicast in Cooperative Environments," Proceedings of the 19th ACM Symposium on Operating Systems Principles, pp. 298-313, Oct. 2003（非特許文献４）に記載されている技術を使用することができる。SplitStream技術は、適切なタイムアウトや再送信を使用して障害を処理することの負担をなくす。
【００５５】
他の１つの設計上の論点は、レプリカ再構築に関する。前述のように、符号化されたフラグメントは、匿名（送信源の固有情報が消去された情報）である。このことの主な理由は２つある。第１に、フラグメントの数は、アプリケーションによって選択された冗長度に依存する。したがって、多数のフラグメントが各ブロック用に存在することができ、それが、ＤＨＴサイズと経路（ルーティング）テーブルの大きな増加を導く。第２に、フラグメントは、ＤＨＴに対する複数回の更新をすることなく、レプリカを新たに具現して再構築することができる。障害後にレプリカを再構築するために、新しいレプリカは、健全なノードから必要な数のフラグメントを検索し、前述のように新たな一次独立のフラグメントを構築する。データの検索を完了させることによって、データ検索に新しいレプリカを参加させることができる。その存在を他のレプリカに通信するために、ブロックの内容は更新され、新しいレプリカを、今や、レプリカ集合にシームレスに統合することができる。
【００５６】
他の１つの設計上の論点は、ブロック検索の性能に関する。保存された符号化データを読むことは、ＤＨＴの少なくとも２回の参照(lookup)を含み、その１回は、オブジェクト・メタデータを見出すためのものであり、他の１回は、レプリカ集合内のノードのリストを取得するためのものである。それらの参照は、メタデータのキャッシュと楽観的（オプティミスティック）ブロック検索との組み合わせを用いることによって軽減される。対象にアクセスする複数のノードの高度の空間的局在性を期待することができる。すなわち、データを保存したノードは、高い蓋然性で、再度、そのデータを検索しそうである。このキャッシュ内のヒットによって、全てのＤＨＴ参照が除かれ、そして、その場合には性能は従来型のクライアント−サーバ・システムの性能に近づく。ヒットミスがあった場合はクライアントは全参照を行わなければならない。
【００５７】
他の１つの設計上の論点は、資源の利用を最適化することに関する。従来型のピア・ツー・ピア・システムは、転送するノードにおいて付加的なＣＰＵサイクルを必要としない。このことによって、各ノードのハンド幅だけがデータの転送に参加するための資源上の制約になる。しかし、本発明に基づくシステムは、転送のためばかりでなく、イレーザ符号化のためにも中間ノードを使用するので、ＣＰＵオーバーヘッドを生じる。フラグメントは匿名であって独立であるので、転送するノードは、ＣＰＵサイクルを利用できるときに、日和見的にデータを符号化することができる。そうでなければ、データは単に転送され、宛先（レプリカ）が、受信データに対応する一次独立のフラグメントを生成しなければならない。これは、許容できる問題解決手法ではあるが、イレーザ符号化を行うために充分な資源をもつ転送ツリーをもたらすツリー構造における制約条件として、ＣＰＵの使用可能性を用いることができる。
【００５８】
他の１つの設計上の論点は、一般化されたネットワーク符号化に関する。前述の実施形態では、単一のツリーを用いたイレーザ符号化データの分散を利用した。さらに高速のデータ分散を提供するために、別の実施形態においては複数のツリーを用い、その場合に各ツリーは、オリジナル・データの部分またはセグメントを独立に分散するようにすることができる。さらに一般化された手法は、例えば、V. N. Padmanabhan et al, "Distributing Streaming Media Content Using Coorperative Networking," Proceedings of the 12th International Workshop on NOSSDAV, pp. 177-186, 2002（非特許文献５）に記載されている手法と同様な方法を用いて、参加ノードを用いて有向非巡回グラフ（ＤＡＧ：Directed Acyclic Graph）を形成することである。中間ノードにおける符号化を用いる一般的なＤＡＧに基づく手法は、次の２つの利点をもつ。(i)転送負荷の、関与するノード間における最適分散、(ii)ソースとレプリカ集合との間の複数の経路を用い基礎をなすネットワーク内での、利用可能なバンド幅の資源の有効活用。
【００５９】
前述の詳細な説明は、全ての側面において説明と例示のためのものであって、限定的なものではないと理解されるべきである。したがって、本明細書に開示されている発明の範囲は、詳細な説明から定められるべきではなく、特許請求の範囲から、特許法によって許される全範囲にしたがって解釈されるように定められるべきである。本明細書で示され、記述されている実施形態は、単に本発明の原理を説明するだけであること、および、種々の変更が本発明の範囲と精神から逸脱することなく当業者によって実施されることができることを理解するべきである。当業者は、本発明の範囲と精神から逸脱することなく、他の種々の特徴の組み合わせを実施することができるであろう。
【図面の簡単な説明】
【００６０】
【図１】従来技術のデータ複製技術を示す図である。
【図２】マルチキャスト・ツリーとして論理的に体系化された従来技術のネットワーク・ノードを示す図である。
【図３】ネットワーク上でオリジナル・データをバックアップするためのイレーザ符号化の従来技術を示す図である。
【図４】オリジナル・データを、多数の一意レプリカ・フラグメントを有するレプリカ・データセットに変換するための、分散ネットワーク・ノードのマルチキャスト・ツリーの使用を説明する図である。
【図５】ネットワーク・ノードを実現するために使用することができるコンピュータの、上位レベルでのブロック図である。
【図６】本発明の実施の一形態を図示するブロック図である。
【図７】マルチキャスト・ツリーを生成する技術を示すフローチャートである。
【図８】マルチキャスト・ツリーを生成する技術を示すフローチャートである。
【図９】マルチキャスト・ツリーを生成する技術を示すフローチャートである。
【図１０】マルチキャスト・ツリーを生成する技術を示すフローチャートである。
【図１１】マルチキャスト・ツリー内でイレーザ符号化を実行する技術を示すフローチャートである。
【図１２】マルチキャスト・ツリーにおけるイレーザ符号化を説明する図である。
【符号の説明】
【００６１】
４０２，１２０２    ソース・ノード
４０４，４０６，４０８，４１０，６１６，６１８，６２０    レプリカ・ノード
４１２，４１４，１２０４，１２０８    中間ノード
４１６，６０６    オリジナル・データ
４１８，４２０    中間イレーザ符号化データ・ブロック
４２２，４２４，４２６    レプリカ・フラグメント
５０２    コンピュータ
５０４    プロセッサ
５０８    入出力部
５１０    メモリ
５１２    記憶装置
６０２    クライアント・ノード
６０４    アプリケーション
６０８    デーモン
６１２    オブジェクト・メタデータ
６２６    マルチキャスト・ツリー
６３６    フラグメント
１２０６，１２１０，１２１２，１２１４，１２１６    宛先（リーフ）ノード
【図１】
2007202146.tif 000007
【図２】
2007202146.tif 000008
【図３】
2007202146.tif 000009
【図４】
2007202146.tif 000010
【図５】
2007202146.tif 000011
【図６】
2007202146.tif 000012
【図７】
2007202146.tif 000013
【図８】
2007202146.tif 000014
【図９】
2007202146.tif 000015
【図１０】
2007202146.tif 000016
【図１１】
2007202146.tif 000017
【図１２】
2007202146.tif 000018