(57)【要約】【課題】  ノードが階層に編成されている分散データ複製において複製オーバヘッドと整合性レベルを最適にトレードオフするための方法およびシステムを提供することにある。【解決手段】  ルート・ノードは、他のすべてのノードに複製する必要がある元のデータを有し、複製コピーは満足しなければならない鮮度しきい値を有する。データは、階層内の定期的な更新により伝搬される。各ノードは、その子ノードに定期的にデータを送信する。鮮度しきい値を考慮して、アルゴリズムおよびその分散プロトコルにより、鮮度しきい値がすべてのノードについて満足され、全体的な複製オーバヘッドが最小限になるように、階層の各リンクについて最適更新期間を決定することができる。このシステムおよび方法は、複製オーバレイ支援リソース発見システムなど、複製データが整合性要件を有する、いかなるシナリオでも使用することができる。【選択図】  図１
2009545072.tif 000002
【特許請求の範囲】
【請求項１】
階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するための方法において、
前記ノードのネットワーク階層内の任意の所与のノードに保管された任意のデータについて鮮度しきい値を定義するステップと、
任意の所与のノードに保管されたすべてのデータについて前記鮮度しきい値が満足され、データの更新に関連するオーバヘッドが最小限になるように、各ノードに保管されたデータについて前記ネットワーク階層内の前記ノード間の複数のリンクのそれぞれによる更新期間を決定するステップと、
前記ノードに保管されたデータを前記決定された更新期間に応じて更新するステップと、
を含む、方法。
【請求項２】
前記複数のノードが、ツリー階層に配置されたサーバを含む、請求項１に記載の方法。
【請求項３】
前記複数のノードがツリー階層に配置される、請求項１に記載の方法。
【請求項４】
前記更新期間を決定する前記ステップが、
その現行データ更新期間と、その親ノードから１つまたは複数のリーフ・ノードへのすべてのデータ更新期間の合計とを前記ノードの階層内の各ノードから親ノードに伝達するステップであって、前記現行データ更新期間が、所与のノードの親ノードがそのノードにデータ更新を送信しなければならない期間を含むステップと、
前記鮮度しきい値が前記ノードの階層内のすべてのリーフ・ノードで満足されるように前記伝達された現行データ更新期間と更新期間合計を調整するステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記更新期間を決定する前記ステップが、
前記ノードの階層内の各ノードで状態データを維持するステップであって、所与のノードの前記状態データが、
前記ノードに関連し、その親ノードがデータ更新を送信しなければならない期間を表す現行データ更新期間と、
その親ノードから前記ノードの任意の子孫リーフ・ノードへの前記データ更新期間の合計と、
を含む、ステップと、
非リーフ・ノードの各子ノードに関連するスケール・ファクタを各非リーフ・ノードで維持するステップと、
をさらに含む、請求項３に記載の方法。
【請求項６】
各ノードで維持された前記状態データを前記ノードの階層を介してルート・ノードに上に伝達するステップをさらに含む、請求項５に記載の方法。
【請求項７】
前記状態データを前記階層を介して伝達する前記ステップが、
前記状態データで伝達された前記データ更新期間のすべての合計が等しい場合に、前記伝達された状態データ内の前記データ更新期間を使用する受信側ノードに関するデータ更新期間を、前記伝達された状態データをその子ノードから受信する前記ノードの階層内の各ノードで計算するステップ
をさらに含む、請求項６に記載の方法。
【請求項８】
前記状態データを前記階層を介して伝達する前記ステップが、
所与のノードで、前記状態データで伝達された前記データ更新期間の前記合計のすべてが等しいわけではないと判断するステップと、
前記所与のノードの任意の子ノードを選択するステップと、
前記任意の子ノードに関連する前記データ更新期間の前記合計を使用して、他のすべての子ノードに関するスケール・ファクタを計算するステップと、
前記計算されたスケール・ファクタを使用して、前記所与のノードのすべての子に関する更新された状態データを計算するステップと、
前記更新された状態データを前記所与のノードから前記ノードの階層を介して上に伝達するステップと、
をさらに含む、請求項６に記載の方法。
【請求項９】
ルート・ノードのすべての子ノードから前記ルート・ノードで状態データを受信するステップと、
前記鮮度しきい値が前記ルート・ノードのすべてのリーフ・ノードで達成されることを保証するために、前記ルート・ノードで受信された前記状態データに対する調整を行うステップと、
をさらに含む、請求項６に記載の方法。
【請求項１０】
調整を行う前記ステップが、前記定義された鮮度しきい値に等しくなるように各リーフ・ノードにおける合計更新期間を調整するステップをさらに含む、請求項９に記載の方法。
【請求項１１】
調整を行う前記ステップが、
各リーフ・ノードに関連する前記合計更新期間を共通同等値に調整するステップと、
前記共通同等値を前記鮮度しきい値と比較するステップと、
前記共通同等値に対する前記鮮度しきい値の比率としてスケール・ファクタを求めるステップと、
前記スケール・ファクタを使用して、各リーフ・ノードで現行更新期間を調整するステップと、
をさらに含む、請求項９に記載の方法。
【請求項１２】
前記スケール・ファクタを前記ルート・ノードの各子ノードに伝達するステップと、
前記スケール・ファクタを使用して、各子に関する現行更新期間を調整するステップと、
をさらに含む、請求項１１に記載の方法。
【請求項１３】
コンピュータによって読み取られたときに、階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するための方法を前記コンピュータに実行させるコンピュータ可読コードを含むコンピュータ可読媒体において、前記方法が、
前記ノードのネットワーク階層内の任意の所与のノードに保管された任意のデータについて鮮度しきい値を定義するステップと、
任意の所与のノードに保管されたすべてのデータについて前記鮮度しきい値が満足され、データの更新に関連するオーバヘッドが最小限になるように、各ノードに保管されたデータについて前記ネットワーク階層内の前記ノード間の複数のリンクのそれぞれによる更新期間を決定するステップと、
前記ノードに保管されたデータを前記決定された更新期間に応じて更新するステップと、
を含む、コンピュータ可読媒体。
【請求項１４】
前記複数のノードがツリー階層に配置される、請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記更新期間を決定する前記ステップが、
その現行データ更新期間と、その親ノードから１つまたは複数のリーフ・ノードへのすべてのデータ更新期間の合計とを前記ノードの階層内の各ノードから親ノードに伝達するステップであって、前記現行データ更新期間が、所与のノードの親ノードがそのノードにデータ更新を送信しなければならない期間を含むステップと、
前記鮮度しきい値が前記ノードの階層内のすべてのリーフ・ノードで満足されるように前記伝達された現行データ更新期間と更新期間合計を調整するステップと、
をさらに含む、請求項１４に記載のコンピュータ可読媒体。
【請求項１６】
前記更新期間を決定する前記ステップが、
前記ノードの階層内の各ノードで状態データを維持するステップであって、所与のノードの前記状態データが、
前記ノードに関連し、その親ノードがデータ更新を送信しなければならない期間を表す現行データ更新期間と、
その親ノードから前記ノードの任意の子孫リーフ・ノードへの前記データ更新期間の合計と、
を含む、ステップと、
非リーフ・ノードの各子ノードに関連するスケール・ファクタを各非リーフ・ノードで維持するステップと、
をさらに含む、請求項１５に記載のコンピュータ可読媒体。
【請求項１７】
各ノードで維持された前記状態データを前記ノードの階層を介してルート・ノードに上に伝達するステップをさらに含む、請求項１６に記載のコンピュータ可読媒体。
【請求項１８】
前記状態データを前記階層を介して伝達する前記ステップが、
前記状態データで伝達された前記データ更新期間のすべての合計が等しい場合に、前記伝達された状態データ内の前記データ更新期間を使用する受信側ノードに関するデータ更新期間を、前記伝達された状態データをその子ノードから受信する前記ノードの階層内の各ノードで計算するステップ
をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
前記状態データを前記階層を介して伝達する前記ステップが、
所与のノードで、前記状態データで伝達された前記データ更新期間の前記合計のすべてが等しいわけではないと判断するステップと、
前記所与のノードの任意の子ノードを選択するステップと、
前記任意の子ノードに関連する前記データ更新期間の前記合計を使用して、他のすべての子ノードに関するスケール・ファクタを計算するステップと、
前記計算されたスケール・ファクタを使用して、前記所与のノードのすべての子に関する更新された状態データを計算するステップと、
前記更新された状態データを前記所与のノードから前記ノードの階層を介して上に伝達するステップと、
をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【請求項２０】
前記方法が、
ルート・ノードのすべての子ノードから前記ルート・ノードで状態データを受信するステップと、
前記鮮度しきい値が前記ルート・ノードのすべてのリーフ・ノードで達成されることを保証するために、前記ルート・ノードで受信された前記状態データに対する調整を行うステップであって、
各リーフ・ノードに関連する前記合計更新期間を共通同等値に調整するステップと、
前記共通同等値を前記鮮度しきい値と比較するステップと、
前記共通同等値に対する前記鮮度しきい値の比率としてスケール・ファクタを求めるステップと、
前記スケール・ファクタを使用して、各リーフ・ノードで現行更新期間を調整するステップと、
前記スケール・ファクタを前記ルート・ノードの各子ノードに伝達するステップと、
前記スケール・ファクタを使用して、各子に関する現行更新期間を調整するステップと、
によって調整を行うステップと、
をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報技術システムの管理および監督の分野に関し、特に、情報技術システム内の分散データ複製のための整合性維持に関する。
【背景技術】
【０００２】
データ複製は、データ可用性および全体的なシステム・パフォーマンスを改善するために、複数の位置で元のデータのコピーを保管するために広く使用される技法である。データ複製は、とりわけ、コンテント・デリバリ・ネットワーク（content delivery network）、ピアツーピア保管および交換、アプリケーションレベルのマルチキャスト、および分散データ・バックアップを含む、様々な情報技術システムで使用される。
【０００３】
多くのこのようなシステムでは、１つのノードに位置する元のデータを他のノードの集合に複製する必要がある。これらのすべてのノードは通常、ツリー階層に編成され、元のデータを有するノードは階層のルートになる。データは、階層の各リンクにより定期的に複製される。たとえば、ルート・ノードは、その子ノードにそのデータを定期的に送信し、その子のそれぞれはその親から受信したデータをその子に定期的に送信する。このようにして、データは階層内のすべてのノードの全体にわたってリフレッシュされる。
【０００４】
データ複製が使用され、データ整合性を維持する必要がある情報技術システムの１つはリソース発見システムである。ネットワーク・コンピューティング・システムなどのコンピューティング・システムでアプリケーションまたはサービスを実行するためには、このコンピューティング・システム内のリソースおよびこのコンピューティング・システムの外部にあるリソースも、これらのアプリケーション間に割り振る必要がある。このようなリソースとしては、たとえば、中央演算処理装置（ＣＰＵ）リソースなどのコンピューティング・ハードウェア・リソース、たとえば、物理マシン内のハード・ディスク・サイズ、メモリ・サイズなどの記憶容量、データ・コレクタまたはデータ・センサを含む。使用可能なリソースは静的リソースおよび動的リソースのいずれにもなり得る。たとえば、所与のマシンのメモリ・サイズまたはネットワーク・アダプタ速度は通常、固定されているが、使用可能なメモリまたは帯域幅は時間の経過につれて頻繁に変化する。
【０００５】
様々な同時発生リソース要求間でリソースを割り振るためには、使用可能なリソースのリポジトリを作成し、維持する必要がある。このリポジトリの作成および維持は、割り振りに使用可能なリソースを発見することを含む。リソース発見は、所与のリソース要求の指定の要件に従ってリモート・リソースの場所を突き止めることができ、様々なアプリケーションのために多くの分散コンピューティング・システムで広く使用される。たとえば、グリッド・コンピューティングでは、アプリケーションを実行するために必要なＣＰＵおよびメモリ・リソースを所有するマシンまたはノードが発見または識別され、その後、これらの識別されたマシンにそのアプリケーションが配備される。
【０００６】
様々なリソース発見のための手法が提案されている。これらの提案された手法としては、１９８８年発行のP. MockapetrisおよびK. J. Dunlapによる「Development of the Domain Name System」（Proceedingsof SIGCOMM'88, Stanford, Californiaの１２３〜１３３ページ）に記載されたドメイン・ネーム・システム（ＤＮＳ：domain name system）、１９９７年１２月発行のM. Wahl、T. Howes、およびS. Killeによる「RFC 2251 - Lightweight Directory Access Protocol (v3)」、２００１年１月発行のＩＴＵ−Ｔによる「Recommendation X.500」、および１９９６年発行のD.W.Chadwickによる「Understanding X.500 - The Directory」に記載された軽量ディレクトリ・アクセス・プロトコル（ＬＤＡＰ／Ｘ．５００）、ならびにSun Microsystemsによる「Java Naming andDirectory Interface -- JNDI Documentation」（http://java.sun.com/products/jndi/docs.html）に記載されたＪａｖａ命名ディレクトリ・インターフェース（ＪＮＤＩ：java naming and directory interface）を含む。これらのシステムはいずれも、リソースを発見するためのディレクトリ・サービスを提供するが、上記のこれまでのリソース発見の試みは、ほとんどの場合、静的リソース、すなわち、たとえばホスト名とインターネット・プロトコル（ＩＰ）アドレスのマッピングなど、極めてゆっくり変化するリソースのために手配されていた。これらのシステムを使用して、たとえば、数十分以下の規模で頻繁に変化する動的リソースのサポートは、非常に限られている。加えて、これらのシステムでは、使用可能なリソースの空間（space）または領域（universe）は、委任された方法で管理される定義済みツリー階層にグローバルに編成されるものと想定する。すなわち、各組織は、このような階層について合意し、ツリーの一部分を「所有」する。
【０００７】
しかし、リソースのグローバル編成および管理は存在する可能性はない。加えて、グローバル編成によって、リソースの割り振りに複雑さと制約がもたらされる。たとえば、新しいタイプのリソースを今後追加する予定である場合、リソース階層を事前定義することは難しい可能性がある。管理上および信頼上の理由により、自律システムは、リソースをどのように編成すべきかについて種々の認識を有する可能性がある。すでに種々のリソース発見サービスを使用しているシステムは、共通タスクのために共同作業する必要があるが、個々のレガシー・リソース発見サービスを変更することは非常に困難なことである。
【０００８】
スケーラブル広域リソース発見ツール（ＳＷＯＲＤ：scalable wide-area resource discovery tool）の１つは、２００４年１２月発行のDavid Oppenheimer、Jeannie Albrecht、David Patterson、およびAmin Vahdatによる「Distributed Resource Discovery on PlanetLab with SWORD」（First Workshop on Real, Large Distributed Systems (WORLDS '04)）に記載されている。このリソース発見サービスは、２００２年７月発行のLarry Peterson、Tom Anderson、David Culler、およびTimothy Roscoeによる「A Blueprint for Introducing Disruptive Technology into the Internet」に記載されているようにＰｌａｎｅｔＬａｂのために作成されたものである。ＳＷＯＲＤによって使用されるリソース発見ツールでは、分散ハッシュ・テーブル（ＤＨＴ：distributed hash table）ベースのピアツーピア・ネットワークを使用して、動的リソースに関する多次元範囲照会（multi-dimensional range query）をサポートする。ピアツーピア・ネットワークを使用する場合の不利点の１つは、システムの管理が難しいことである。ピアツーピア・ネットワークは個別ノードの高い自律性を可能にするように配置されており、システム内の特に集中化した制御および管理を容易にすることが極めて難しくなっている。加えて、ＳＷＯＲＤ内のリソース発見ツールでは、それぞれの個別自律システムがその完全なリソース・レコードをピアツーピア・ネットワークにエクスポートする必要がある。これは、信頼性の課題のために問題になる可能性がある。個別自律システムは、外界にそのオリジナル・レコードを快く公開しない可能性がある。
【０００９】
使用可能なリソースのリポジトリの作成および維持は、オーバヘッド、すなわち、システム・リソースを消費する。維持する量が増えるほど、システム・オーバヘッドについて発生するコストが増加する。このような維持としては、システム・リソースに関する最新かつ正確な情報を反映する信頼できる整合データを提供することを含む。しかし、頻繁な更新はより多くのシステム・リソースを消費する。使用可能なシステム・リソースのリソースを維持するための現在の方法は、最新のデータを求める希望と、システム・オーバヘッドを最小限にしようという希望とをバランスを取るものではない。したがって、システム・オーバヘッドの消費量を最適化しながら、受け入れられるレベルの鮮度をリポジトリで提供するように、様々なリソース要求間でこれらのリソースを割り振るためにリソースのリポジトリの作成および維持を可能にするシステムおよび方法が必要である。
【非特許文献１】１９８８年発行のP. MockapetrisおよびK. J. Dunlapによる「Development of the DomainName System」（Proceedings of SIGCOMM'88, Stanford,Californiaの１２３〜１３３ページ）
【非特許文献２】１９９７年１２月発行のM. Wahl、T. Howes、およびS. Killeによる「RFC 2251 - Lightweight Directory Access Protocol (v3)」
【非特許文献３】２００１年１月発行のＩＴＵ−Ｔによる「RecommendationX.500」
【非特許文献４】１９９６年発行のD.W. Chadwickによる「Understanding X.500 - The Directory」
【非特許文献５】Sun Microsystemsによる「Java Naming and Directory Interface -- JNDI Documentation」
【非特許文献６】２００４年１２月発行のDavidOppenheimer、Jeannie Albrecht、DavidPatterson、およびAmin Vahdatによる「DistributedResource Discovery on PlanetLab with SWORD」（FirstWorkshop on Real, Large Distributed Systems (WORLDS '04)）
【非特許文献７】２００２年７月発行のLarry Peterson、Tom Anderson、David Culler、およびTimothy Roscoeによる「A Blueprint forIntroducing Disruptive Technology into the Internet」
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明によるシステムおよび方法は、複製階層内のデータ階層の整合性維持のために使用されるオーバヘッドの量を最適化する。元のデータは動的なものにすることができ、連続的に変化する可能性があるので、複製データ・コピーについて特定のレベルの整合性を保証することが望ましい。整合性レベルと複製オーバヘッドとのトレードオフが存在する。一般に、各リンクによる更新の頻度が高くなるほど、整合性が改善される。しかし、データ更新の頻度が高まると、消費するオーバヘッドが多くなる。所望の整合性レベルの場合、本発明による模範的なシステムおよび方法は、所望の整合性レベルが満足され、複製オーバヘッドが最小限になるように、階層内の複数のリンクのうちのそれぞれによる最適更新頻度を決定する。
【課題を解決するための手段】
【００１１】
本発明の諸実施形態は、コンテント・デリバリ・ネットワーク、ピアツーピア・データ交換、およびアプリケーションレベルのマルチキャストを含むがこれらに限定されない様々なタイプの情報技術システムで使用することができる。本明細書に示されている諸例は、連合リソース発見システム（federated resource discovery system）に関する最適複製オーバヘッドを決定するための本発明の使用を例示しているが、本発明はこのようなタイプのシステムでの適用に限定されない。
【００１２】
本発明の模範的な諸実施形態によるシステムおよび方法は、ノードがツリー階層に編成されている分散アプリケーションにおいて複製オーバヘッドと整合性レベルを最適にトレードオフする。階層のルート・ノードは、複数の他のノードに複製する必要がある元のデータを有する。この複製は、階層内の各リンクによる定期的な更新メッセージを介して実行される。すべてのノードは、その親から受信したデータをその子に定期的に送信する。このようにして、階層内のすべての他のノードにデータが複製される。
【００１３】
元のデータは時間の経過につれて変化するので、階層の全体にわたって分散されるデータの複製コピーは、元のデータと比較して所定のレベルの整合性を必要とする。所与の起点ノードから複製ノードのツリー・トポロジへの整合性の要件は、定式化し、公式化することができる。この公式化によって表される最適化問題は、所与の整合性要件を満足しながら、全体的なメッセージ・オーバヘッドが最小限になるように、階層のすべてのリンクによる最適更新期間を計算するためのアルゴリズムを使用して解くことができる。このアルゴリズムは、階層内で実行することができる分散実装例を有し、各ノードで一定の状態およびメッセージ・オーバヘッドを使用して、全体的な複製オーバヘッドを最小限にすることができる。
【００１４】
本発明によるシステムおよび方法は、階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するための方法を含む。ノードはサーバを含み、適切な階層はツリー階層を含む。鮮度しきい値（freshness threshold）は、ノードのネットワーク階層内の任意の所与のノードに保管された任意かつすべてのデータについて定義される。次に、任意の所与のノードに保管されたすべてのデータについて鮮度しきい値が満足され、データの更新に関連するオーバヘッドが最小限になるように、各ノードに保管されたデータについてネットワーク階層内のノード間の複数のリンクのそれぞれによる更新期間が決定される。ノードに保管されたデータは、決定された更新期間に応じて更新される。
【００１５】
更新期間を決定するために、現行データ更新期間と、その親ノードから１つまたは複数のリーフ・ノードへのすべてのデータ更新期間の合計が、ノードの階層内の各ノードから親ノードに伝達される。現行データ更新期間は、所与のノードの親ノードがそのノードにデータ更新を送信しなければならない期間を含む。伝達された現行データ更新期間と更新期間合計は、鮮度しきい値がノードの階層内のすべてのリーフ・ノードで満足されるように調整される。加えて、更新期間の決定は、ノードの階層内の各ノードで状態データを維持することも含む。所与のノードの状態データは、そのノードに関連し、その親ノードがデータ更新を送信しなければならない期間を表す現行データ更新期間と、その親ノードからそのノードの任意の子孫リーフ・ノードへのデータ更新期間の合計とを含む。非リーフ・ノードの各子ノードに関連するスケール・ファクタは、各非リーフ・ノードで維持される。
【００１６】
一実施形態では、各ノードで維持された状態データは、ノードの階層を介してルート・ノードに上に伝達される。状態データを階層を介して上に伝達するために、状態データで伝達されたデータ更新期間のすべての合計が等しい場合に、伝達された状態データ内のデータ更新期間を使用する受信側ノードに関するデータ更新期間が、伝達された状態データをその子ノードから受信するノードの階層内の各ノードで計算される。代わって、所与のノードで、状態データで伝達されたデータ更新期間の合計のすべてが等しいわけではないと判断された場合、所与のノードの任意の子ノードが選択され、その任意の子ノードに関連するデータ更新期間の合計を使用して、他のすべての子ノードに関するスケール・ファクタを計算する。計算されたスケール・ファクタを使用して所与のノードのすべての子に関する更新された状態データを計算し、更新された状態データは、所与のノードからノードの階層を介して上に伝達される。
【００１７】
状態データはルート・ノードのすべての子ノードからそのルート・ノードで受信され、鮮度しきい値がルート・ノードのすべてのリーフ・ノードで達成されることを保証するために、ルート・ノードで受信された状態データに対する調整が行われる。状態データに対する調整としては、定義された鮮度しきい値に等しくなるように各リーフ・ノードにおける合計更新期間（summation update period）を調整することを含む。加えて、各リーフ・ノードに関連する合計更新期間は共通同等値（common equal value）に調整され、この共通同等値は鮮度しきい値と比較される。スケール・ファクタは、共通同等値に対する鮮度しきい値の比率として求められ、現行更新期間はそのスケール・ファクタを使用して各リーフ・ノードで調整される。そのスケール・ファクタはルート・ノードの各子ノードに伝達され、各子に関する現行更新期間はそのスケール・ファクタを使用して調整される。
【発明を実施するための最良の形態】
【００１８】
最初に図１を参照すると、本発明によりシステム・オーバヘッドを最小限にしながら、所望のレベルのデータ整合性を維持するように、階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するために、模範的な実施形態とともに使用するためのシステム１０の模範的な一実施形態が例示されている。例示されている通り、システム１０は本発明の模範的な諸実施形態による連合リソース発見システムである。この連合リソース発見システムは、最適オーバヘッドとともに整合性レベルを維持するための方法を適用できる模範的な情報技術システムの１つである。しかし、最適オーバヘッドとともに整合性レベルを維持するための方法の適用は、連合リソース発見システムに限定されず、様々な情報技術システムおよび関連階層に適用することができる。
【００１９】
最初に本発明の模範的な諸実施形態による連合リソース発見システムの編成および使用の考察から始めるが、この連合リソース発見システムは、所定の階層に応じて配置された複数の専用サーバ１２（Ｄサーバ）を含む。専用サーバは、この階層により相互に通信状態にあり、ファイルまたはデータを交換することができる。適切なサーバは、当技術分野で既知であって入手可能であり、コマンドを処理し、データを保管し、他のサーバと通信できる任意のタイプのプロセッサまたは処理装置を含む。適切な階層としては、ツリー階層およびピラミッド階層を含むが、これらに限定されない。好ましくは、サーバは、ツリー階層に配置され、複数のリーフ・ノードＤサーバ２０と、複数の中間ノードＤサーバ１６と、ルート・ノードＤサーバ１４とを含む。すべてのＤサーバは、単一の位置に、たとえば、専用サーバ・ファームの一部として位置することができる。代わって、サーバは、様々な位置に分散され、１つまたは複数のネットワークの全域で通信状態にある。たとえば、各Ｄサーバは、個別ドメインまたは組織に位置することができる。サーバは、厳密にその階層専用になる場合もあれば、階層外で他のサービスまたは機能を提供する多目的サーバになる場合もある。
【００２０】
システムは、特定のドメインまたは組織に関連し、Ｏサーバ２２という複数のリソース発見サーバも含む。各Ｏサーバを１つの個別ドメインに関連付けるか、あるいは２つ以上のＯサーバを共通ドメインに関連付けることができる。適切なタイプのＯサーバはＤサーバの場合と同じである。一実施形態では、すべてのＯサーバは、個別のものであり、Ｄサーバとは別個のものである。代わって、少なくとも１つのＯサーバと１つのＤサーバは共通サーバである。一般に、Ｏサーバは、複数サーバが広く分散したシステムとして配置される。各Ｏサーバは１つまたは複数のネットワークの全域でＤサーバのうちの少なくとも１つと通信状態にある。たとえば、分散Ｏサーバは、インターネットなどの広域ネットワーク１８の全域でＤサーバと通信状態にある。加えて、他のグループのＯサーバも、１つまたは複数のローカル・エリア・ネットワーク２４、たとえば、所与のドメインまたはインターネット・サービス・プロバイダに関連するローカル・エリア・ネットワークを介してＤサーバと通信することができる。本明細書で使用する様々なサーバ間の通信は、各サーバが任意の他のサーバとの間でデータを送受信できるという点で双方向通信である。各ＯサーバはＤサーバのうちのいずれか１つと通信することができるが、好ましくは、各Ｏサーバは、ツリー階層内のリーフ・ノードを表すＤサーバの１つによって識別され、そのＤサーバにより伝達される。したがって、Ｏサーバはツリー階層内のそのＤサーバの子ノードになる。
【００２１】
各Ｏサーバは、単一サーバになる場合もあれば、所与のドメインまたは組織内の分散サービスである場合もある。各Ｏサーバは、その組織内のリソースを発見し、保管されたリソース・データを更新し、所望のレベルの細分性に応じてリソース・データを要約し、他のサーバにリソース・データを伝達し、他のサーバからリソース・データを受信することができる。所与の組織内に含まれるリソースは、その組織の特定のフォーマットまたは独自所有のフォーマットに応じて編成され、そのフォーマットでこれらのリソースを記述するデータまたは属性はＯサーバ内で入手され維持される。そのリソースを記述するために使用される属性に関する特定のフォーマットまたは固有フォーマットとしては、特定のタイプのリソースを命名するために使用される規則を含む。属性フォーマットの変形は、たとえば、メモリ対ＲＡＭのように完全に同じリソースを記述するために異なる名前を使用すること、ならびに同じ基本機能を有する異なるリソースを使用することから発生する。たとえば、ある組織はその１次記憶ソースとしてＲＡＭを使用する可能性があり、他の組織はその１次記憶ソースとしてフラッシュ・メモリを使用する可能性がある。どちらもそれぞれの組織に対して同じ基本機能を提供するが、そのリソースを記述するために異なる属性を有することになる。
【００２２】
各Ｏサーバは、階層構造内に含まれる分散専用サーバであるＤサーバのうちの１つまたは複数と通信状態にあって、それとデータを交換することができるので、各ＯサーバはＤサーバのうちの１つに対し、その組織の特定のフォーマットまたはプロトコルに応じてそのＯサーバに保管されたリソース属性データをエクスポートする。このＤサーバはＯサーバにとって親Ｄサーバである。したがって、様々な組織はユニバーサル・フォーマットに応じてフォーマットする必要がない。
【００２３】
任意の所与のリソースの識別、位置、および諸機能を含む、そのリソースの記述は、そのリソースに関連し、リソース属性データで表される複数の属性を使用して提供される。これらの属性は定性または定量記述子の形を取ることができる。一実施形態では、とりわけ、実数または整数、カテゴリ・データ、および数値間隔などの定量数値形式で属性が提供される。所与のリソースに関連する各属性は、それが関連付けられるリソースの次元と見なすことができる。データまたは属性の量が大きいほど、相互に関係する次元数（dimensionality）が大きくなるか高くなる。次元数が大きいほど、関連データを保管するために必要な記憶空間が大きくなる。しかし、リソースが位置する組織に関連するＯサーバを除いて、すべてのリソースに関する次元数全体を階層内のすべてのサーバで維持する必要はない。実際に、任意の所与のＤサーバでは、そのＤサーバからの照会を、そのリソースに関する属性データのすべてを含むＯサーバの方向に経路指定するために十分な量の情報だけが必要である。したがって、任意の所与のＤサーバは、任意の所与のリソースに関する属性の要約または集約表現だけを必要とする。
【００２４】
図２を参照すると、本発明によるリソース発見および割り振りで使用するためのＤサーバ２６のツリー階層の模範的な一実施形態が図２に例示されている。このツリー階層リソース発見システムは、ルートＤサーバ１４と、中間ノードＤサーバ１６と、リーフ・ノードＤサーバ２０とを含む、複数の個別Ｄサーバを含む。各リーフ・ノードＤサーバ２０は、１つまたは複数のＯサーバからそれに伝達されたリソース属性データを含む。これらのリソース属性データとしては、数の範囲などの定量データ２６と、コンポーネントのリストまたは集合などの定性データ２８とを含む。
【００２５】
任意の所与のＤサーバにおけるリソース属性データの保管を改善するために、集約関数（aggregation function）を使用して、そのリソースに関連し、そのＤサーバに伝達されたリソース属性データの要約または集約が作成される。一般に、集約関数は、元のデータより粗い細分性、たとえば、低い次元数の要約されたデータを生成する。低い次元数は、属性の数を削減するか、あるいは、所与の属性に関連するデータまたは情報の量を削減することによって達成される。一実施形態では、集約は、所与の属性に関連するデータの量を減少させることを含む。したがって、所与の属性の場合、集約関数はその属性に関連するデータを有するすべてのリソースを使用して適用され、集約は所与の属性に関する集約を伴う。たとえば、受け入れられる数値の範囲を使用して記述され、その範囲に関する上限および下限の形を有する属性の場合、集約関数は、その属性に関連する各リソースに関連する上限および下限を使用して適用され、所与のＤサーバに伝達される。各リソースは、その属性について上限および下限を有する。所与の集合のリソースの場合、そのリソースのすべてについて受け入れられる範囲の数値のすべては、そのリソースのすべてに関連する最小下限とそのリソースのすべてに関連する最大上限によって定義された範囲内に収まることになる。したがって、集約された属性は全体的な最小下限と全体的な最大上限とを含む。各リソースに関する個別の属性はＤサーバで維持されない。集約属性のみが全体的な上限および下限を含む。この集約属性は、Ｄサーバの階層を介して上に、そして最終的にルートＤサーバに伝達される。集約された属性を受信する階層内のＤサーバは、その属性の点でそれより下のリソースについてより粗いかまたは広いビューを入手する。そのＤサーバは任意のリソースに関連する範囲を把握していない可能性があるが、Ｄサーバは、その子ノードに関連する任意のリソースがその集約された属性の上限と下限の範囲内に収まる上限と下限をその属性について有することを把握するであろう。所与のＤサーバ、たとえば、中間Ｄサーバのうちの１つが集約された属性データをその子から受信すると、そのＤサーバは各次元に沿ってそのデータをさらに集約する。この場合も、定量または数値属性について、Ｄサーバは、すべての下限のうちのより小さいものと、すべての上限のうちの最大のものとを取り、その結果、新しい下限と上限を入手する。このようにさらに集約された属性はそのＤサーバの親に伝達される。このプロセスは、階層内のルート・サーバに到達するまで、ＤサーバからＤサーバへと繰り返される。
【００２６】
カテゴリ属性２８の場合、その属性に含まれるメンバまたはカテゴリを表すために集合またはリストが使用される。たとえば、その属性は、所与のリソースがサポートできる通信プロトコルのタイプのＩＤにすることができ、その属性は、サポートされる通信プロトコルのＩＤを含む集合によって表される。集約は、リソースに関連し、Ｏサーバまたは子Ｄサーバから受信したすべての属性集合の組み合わせまたは和集合を取ることを含む。すべての集合の和集合を表す属性集合は階層を介して上に伝達され、各レベルでさらに集約または結合される。図２に示されている通り、最下部のリーフ・ノードＤサーバ２０から最上部のルートＤサーバ１４までの各サーバで集約が繰り返される。ルートＤサーバは、すべての使用可能なリソースの属性に関するすべてのカテゴリのＩＤを含む上位集合（superset）を維持する。ルートＤサーバは、所与のコンピューティング・システムで実行されるアプリケーションなど、１つまたは複数のリソース要求への割り振りのために発見され使用可能なすべてのリソースの属性データを受信し集約する。上記の例では下限および上限ならびにセット和集合（set union）集約関数が使用されているが、集約関数がデータ・サイズを縮小し、使用可能なリソースにサーチを向けるのを支援する限り、その他の形式の集約関数も使用することができる。
【００２７】
一実施形態では、集約関数は、たとえば、番地、市区町村、郡、州などの位置属性とともに使用するのに適している。たとえば、リーフ・ノード・レベルＤサーバのレベルでは、位置属性は、たとえば、ビデオ・カメラなどの所与のリソースが位置する市区町村ブロック・サイズの長方形を記述するかまたは境界線で囲むために十分な量の情報を含む。図２に例示されている通り、各リーフ・ノードＤサーバにおける位置の集合は位置の集合｛Ｌ｝で示され、これは正確な番地または正確なマップ・グリッドと同じくらいの細部を示すことができるであろう。位置属性は集約され、中間Ｄサーバ１６に伝達されるので、位置情報に提供される細部の量は、たとえば、市区町村名｛Ｃ｝および州名｛Ｓ｝など、減少した特異性によって示される。市区町村名集合は、その子からその中間Ｄサーバに伝達されるすべての位置属性集合に含まれる市区町村のすべてを含む。ルートＤサーバ・レベルでは、位置属性は、すべてのリソースが所与の州内に位置することを指定するだけであろう。
【００２８】
一般に、集約のプロセスは、矢印Ａの方向によって示されるように、階層を介して上に属性データを伝達する際に使用される。複製は、矢印Ｂによって示されるように、階層を介してリーフ・ノードＤサーバまたは中間Ｄサーバまで集約されたデータを下に伝達するために使用される。また、複製は、階層の構造全体を通してより多くの情報を伝達し、照会に対する応答をより効率的なものにするために使用される。一実施形態では、所与のＤサーバの兄弟およびそのＤサーバの祖先の兄弟の要約されたデータが定期的に階層内の上から下にそのＤサーバから受信側Ｄサーバに送信され、受信側Ｄサーバによってキャッシュされる。たとえば、図２の拡張リスト３０に例示されている通り、所与のリーフ・ノードＤサーバＤ1は、それ自体の集約されたリソース属性データと、その兄弟であるリーフ・ノードＤサーバＤ2、その親である中間ＤサーバＣ1、その親の兄弟である中間ＤサーバＣ2、その祖父母である中間ＤサーバＢ1、その祖父母の兄弟である中間ＤサーバＢ2およびＢ3、ならびにルートＤサーバＡの複製され集約されたリソース・データとを含む。したがって、処理のためにリソース割り振り照会をルートＤサーバに伝達する必要なしに、そのリソース割り振り照会をそのリーフ・ノードで受信し処理できるように、Ｄサーバの階層に提示されたリソース割り振りデータのすべてに関する十分な情報が階層内の単一リーフ・ノードで維持される。すなわち、リーフ・ノードはすべての使用可能なまたは識別されたリソースについて十分に詳細なピクチャを有する。
【００２９】
したがって、各サーバは、その要約され集約されたデータを階層を介して上に転送し、階層内の上流に位置するサーバの集約されたデータを階層を介して下にリーフ・ノードに向かって伝搬する。たとえば、Ｄサーバ・ノードＢ1は、ルートＤサーバＡからＤサーバＢ2およびＢ3の集約された属性データを受信し、この集約された属性データをＤサーバＣ1およびＣ2の両方に転送する。ＤサーバＣ1およびＣ2は、集約された属性データを受信すると、リーフ・レベル・サーバに向かって階層内の下方伝搬を続行する。
【００３０】
複製を使用して、階層内の様々なＤサーバ間でリソース情報を伝達すると、各Ｄサーバは、少なくとも一部分の要約または集約コピーと、潜在的にグローバル・リソースの集合全体を含み、リソース発見および照会時間を加速する。一般に、所与のＤサーバが任意の特定のリソースについて有する細部の量は、Ｄサーバとリソースとの間の距離、たとえば、中間ノードＤサーバおよびＯサーバの数に比例する。Ｄサーバとリソースとの間の距離がより短い場合、より高度な特異性または細部がそのリソースに関するＤサーバに維持される。この距離が拡大するにつれて、Ｄサーバは依然としてそのリソースに関する情報を維持することになるが、細分性はかなり粗くなる。たとえば、Ｄサーバ・ノードＤ1は市区町村ブロック・レベルの特異性でＤサーバ・ノードＤ2で保管されたカメラ・レコードの位置を把握しているが、Ｄサーバ・ノードＤ1は州レベルの特異性でＤサーバ・ノードＢ2およびＢ3に関するカメラ・レコードの位置だけを把握している。特異性のレベルを低減し、距離につれて細分性を増加すると、全体的な保管およびメッセージ・オーバヘッドが極めて大きいものにならないことが保証される。一実施形態では、ｎ個のサーバを含む階層内のノード度（node degree）がｋである場合、保管の複雑さ（storagecomplexity）は各サーバで約ｋ  ｌｏｇ  ｎである。
【００３１】
また、複製により、ルートＤサーバだけでなく、階層内の任意のＤサーバに照会を送信することができる。図３を参照すると、Ｄサーバの所与の階層を使用してリソース照会の処理を例示する模範的な一実施形態が示されている。クライアント３４は階層内のＤサーバのうちの１つａ１に照会３６を提示する。このＤサーバａ１は、それ自体の要約されたデータと、それに伝達された任意の複製データとを含む、そのＤサーバに保管された要約または集約データをサーチする。このサーチに基づいて、Ｄサーバａ１は、その兄弟Ｄサーバｃ１およびその伯父Ｄサーバｂ２が照会によって要求されたリソースに関する情報を含むと判断する。Ｄサーバａ１はその兄弟および伯父Ｄサーバｃ１およびｂ２に照会３８、４０を転送する。次に、これらのＤサーバｃ１およびｂ２はそのＤサーバの子のデータをサーチし、関連リソース情報を所有するその子Ｄサーバに照会４６、４８を転送する。Ｏサーバのうちの１つまたは複数に照会４２、４４、５０を経路指定するために、その後の子においてリソース属性データをサーチするプロセスが繰り返される。Ｏサーバはツリー階層内のリーフ・ノードＤサーバの子ノードである。各Ｏサーバは、その照会に応答して、詳細なリソース・レコードを求めてそれ自体のデータベースをサーチし、その結果５２、５４、５６をクライアントに返す。例示されている通り、初期照会３４はルートＤサーバ１４に提示または転送されていないが、中間ノードＤサーバに提示されている。そのポイントから照会が処理され、その照会に応答するリソースを含む、ドメインまたはコンピュータ・システムであるＯサーバに転送されている。
【００３２】
応答時間を減少させることに加えて、複製により、たとえば、ルートＤサーバを含むＤサーバのうちの１つまたは複数の障害に直面したときに、階層システムの頑強性または弾力性が改善される。ルートＤサーバ１４が故障またはクラッシュした場合、階層に提示された照会は依然として、残っている使用可能なＤサーバによって処理し応答することができる。一実施形態では、階層内の各Ｄサーバは、その子サーバおよび親サーバとの各通信リンクに沿って周期的な「ハートビート（heart-beat）」メッセージを維持する。これらのハートビート・メッセージは、通信リンクおよびサーバの可用性をテストする。たとえば、親Ｄサーバに関連するサーバまたは通信リンクがアクセス不能であることを所与のハートビート・メッセージが示す場合、Ｄサーバはその新しい親として伯父Ｄサーバを選択する。この選択は、ランダムにまたは１つまたは複数の所定の選択基準に応じて行うことができる。親Ｄサーバが階層システムのルートＤサーバである場合、子のうちの１つが新しいルートとして選ばれる。新しいルートＤサーバの選択に適した方法としては、各子Ｄサーバに対する現行負荷およびその組み合わせを考慮して、最小ＩＰアドレスを有する子Ｄサーバを選択することを含むが、これに限定されない。一般に、すべての照会を単一ルートＤサーバに提示または転送する必要性を除去すると、関連のボトルネックが緩和され、階層全体にわたって計算負荷が分散され、照会応答時間が短縮される。
【００３３】
複製された要約は、他のどのサーバがリソース・データを要求したかを発見するために使用されるので、複製された要約が時間通りに更新されることは重要なことである。複製された要約は、好ましくは、現在使用不能なリソースまたは最近追加されたリソースを含む使用可能なリソースの現行状態を正確に表す。そうではない場合、期限切れの要約により、間違ったサーバに照会が転送されることになる。一実施形態では、要約されたデータは軟質状態（soft-state）である。たとえば、各Ｄサーバは、要約されたデータの各次元ごとに存続時間（ＴＴＬ：time-to-live）値を維持する。一般に、データは、新しいデータが子または親から受信されると、定期的にリフレッシュされる。リフレッシュ済みデータが規定のＴＴＬ値に従って受信される限り、要約されたデータが現行かつ信頼できるものとして維持される。しかし、リソースが除去されるかまたは子Ｄサーバがオフラインになると、リフレッシュ済みデータはＴＴＬ値によって設定された制約の範囲内で受信されなくなる。したがって、これらに関連する要約データがＴＴＬ値に応じて期限切れになると、このデータは所与のＤサーバから除去される。したがって、期限切れのデータ、階層トポロジに対する変更、および使用可能なリソースの変化は、照会に応じたリソース発見を妨害したり、損なうことはない。
【００３４】
一般に、複製のプロセスは、記憶域、プロセッサ、および通信リソースが消費されるときにオーバヘッドを被る。したがって、本発明による模範的な諸実施形態は、複製データにおいて所望の更新レベルを保持しながら、全体的なシステム・パフォーマンスおよびリソース割り振りに対するこのオーバヘッドの影響を最小限にするための方法およびシステムも含む。一実施形態では、各リンクについて最適更新期間を設定する分散アルゴリズムが使用される。
【００３５】
喪失に加えて、階層トポロジおよび使用可能なリソースの集合に対する追加および訂正も考慮される。たとえば、所与のＤサーバは、前の親Ｄサーバの喪失ならびに新しい親Ｄサーバとのその後の再接続に続いて、再フォーマットされた階層トポロジを再結合することになる。新しい親Ｄサーバと接続すると、子Ｄサーバはその集約または要約されたデータを新しい親に転送する。
【００３６】
一実施形態では、データ複製は最後のリーフＤサーバ・ノードまで貫徹されるが、Ｏサーバはどのデータの複製にも関係していない。Ｏサーバは、Ｄサーバによって理解できる適切な形式、たとえば、要約または集約形式で、そのデータをエクスポートするだけである。Ｏサーバ・データをＤサーバに転送するために、定期的または自動化された方法を含む様々な方法が使用される。データの転送は、ＯサーバによってまたはＤサーバからの照会に応答して開始することができる。一実施形態では、ＤサーバまたはＯサーバに統合されるかまたはいずれかのサーバとは分離して動作し、システム管理者、たとえば、ラッパ・デーモン（wrapper daemon）の直接制御の範囲外のバックグラウンドで自動的に実行されるルーチンを使用して、ＯサーバからＤサーバにデータ更新を転送する。一実施形態では、このルーチンが定期的に所与のＯサーバに照会し、所望の要約されたデータを抽出し、抽出されたデータを親Ｄサーバに転送する。単に検索を行って転送することに加えて、このルーチンは、Ｏサーバのサーチによって返された結果をクライアントによって理解される共通フォーマットに再フォーマットすることもできる。
【００３７】
Ｄサーバの階層は、多種多様な組織またはドメインに含まれるリソースの割り振りをモニターし管理するために任意の特定の属性フォーマットを使用することに限定されない。加えて、分散コンピューティング・システムには、リソース識別のためのユニバーサルまたは標準化された属性フォーマットが課せられていない。各コンピューティング・システムは、それ自体の属性フォーマットを決定し、使用する。したがって、各タイプのリソースに使用されるスキーマ、すなわち、属性のリストは、異なる組織について完全に同じである必要はない。様々な受信属性が異なる場合でも、リーフ・レベルのＤサーバは、様々なＯサーバから受信した所与のタイプのリソースに関する属性を、階層内の複数のＤサーバ間で使用される１つまたは複数の共通属性にマッピングすることができる。一実施形態では、Ｄサーバのうちの１つまたは複数、たとえば、リーフ・ノードＤサーバは、階層内のリソース属性データに使用する予定の所定の共通属性フォーマットをＯサーバに伝達する。伝達された共通属性は、各Ｏサーバがそのリソースに関するリソース・データ属性を共通属性にマッピングできるようにするために十分な量の情報を含む。このマップは、リソース属性データとともにＤサーバに伝達される。したがって、各自律組織は、リソース発見システムを選択する際の自由度が増しており、階層システムは、より多様なレガシー自律システムを組み込むことができる。個別コンピューティング・システムには、いかなる外部属性フォーマットまたは階層も課せられない。
【００３８】
本発明による分散システム内の連合リソース発見のための方法の模範的な一実施形態では、複数の分散コンピューティング・システム内に配置された複数のリソースに関連するリソース属性データがこれらの分散コンピューティング・システムから定義済み階層に応じて配置された複数の専用サーバのうちの１つまたは複数に伝達される。一般に、リソース属性データは、複数の分散コンピューティング・システム内に配置された関連リソースの識別および割り振りを容易にするために、分散コンピューティング・システムに含まれるリソースに関する十分な量のデータを含む。このリソースは、クライアント、たとえば、コンピューティング・システム内または階層内のサーバのうちの１つで実行されるアプリケーションからのリソース要求照会に応じて識別され割り振られる。コンピューティング・リソースの任意の配置またはネットワーク配置を含む適切なコンピューティング・システムとしては、情報技術（ＩＴ：information technology）コンピューティング・システムを含むが、これに限定されない。
【００３９】
一実施形態では、リソース属性データをＤサーバに伝達するために、Ｄサーバを使用する各コンピューティング・システムからリソース・データが積極的に入手される。代わって、複数のコンピューティング・システム内に配置されたＯサーバは、そのＯサーバが位置するコンピューティング・システム内に含まれるリソースに関するリソース属性データを入手する。一実施形態では、各コンピューティング・システムは、リソース属性データを入手するために使用される２つ以上のＯサーバを含む。好ましくは、各コンピューティング・システムは、リソース属性データの取得および伝達のために１つのＯサーバを含む。リソース属性データは、階層内の任意のＤサーバに伝達することができる。好ましくは、リーフ階層の場合、リソース属性データはその階層内に含まれるリーフ・ノードＤサーバのうちの１つに伝達される。一実施形態では、適切なリーフ・ノードＤサーバは各Ｏサーバごとに識別され、Ｏサーバは関連リーフ・ノードＤサーバにリソース属性データを伝達する。
【００４０】
各Ｏサーバまたはリソース発見サーバは、そのコンピューティング・システム内に含まれるリソースに関するリソース属性データを、そのコンピューティング・システム用の固有属性フォーマットで入手する。複数のコンピューティング・システムの場合、複数の固有属性フォーマットが可能であり、各フォーマットが独特のものである可能性がある。これらの固有フォーマットにより、特定のリソースに割り当てられた名前およびコンピューティング・システム内の所与の機能に使用されるリソースのタイプを含むがこれらに限定されない、リソースを説明し記述する方法が様々になる。各コンピューティング・システム用の各固有属性フォーマットは、分散コンピューティング・システムのうちの１つによって決定され、それに関連付けられる。様々なコンピューティング・システムに対して１つの汎用またはユニバーサル属性フォーマットが課せられるわけではない。その代わりに、伝達されたリソース属性データがＤサーバ・レベルで複数の固有属性フォーマットから共通属性フォーマットにマッピングされる。この共通属性フォーマットは、複数の専用サーバのうちの少なくとも１つによって提供される。共通フォーマットと固有フォーマットとのマッピングはＤサーバ・レベルまたはＯサーバ・レベルで実行することができる。一実施形態では、共通属性フォーマットがＯサーバのそれぞれに伝達され、リソース属性データをＤサーバに伝達する際にＯサーバは伝達されたリソース属性データを複数の固有フォーマットからＤサーバによって提供された共通属性フォーマットにマッピングする。したがって、リソース属性データとともに両方のマッピング情報がＤサーバに伝達される。
【００４１】
分散コンピューティング・システム内で現在使用可能なリソースのすべてに関するリソース属性データを階層内のＤサーバに伝達すると、十分な量のリソース属性データが専用サーバの階層内の任意の所与の専用サーバに維持される。したがって、リソース照会は任意のＤサーバに提示し、そのＤサーバによって処理することができ、これらのＤサーバはこれらの照会を専用サーバの階層を介して適切な分散コンピューティング・システムまたはその照会に適したリソースを含むコンピューティング・システム内の適切なＯサーバに経路指定することができる。各Ｄサーバにおける所望の量のリソース属性データの維持は、集約および複製を使用して実施される。一実施形態では、リソース属性データは、複数のコンピューティング・システムからそのリソース属性データが伝達される各Ｄサーバで集約される。これらの集約されたリソース属性データは、１つまたは複数の中間Ｄサーバを介して階層のルートＤサーバに伝達される。リーフ・ノードＤサーバでリソース属性データを集約することに加えて、リソース属性データは、そのデータが階層を介して上に伝達されたときに、中間専用サーバのそれぞれでさらに集約される。
【００４２】
一実施形態では、階層内の各専用サーバに維持されたリソース属性データは、階層内の１つまたは複数の追加専用サーバ、たとえば、階層内の兄弟および祖先で複製される。任意の所与のリソースの状況および可用性、すなわち、そのリソースに関連するリソース属性データは時間の経過につれて変化するので、Ｄサーバに維持されたリソース属性データは定期的に更新される。たとえば、存続時間値は、専用サーバに伝達された各リソース属性データについて識別される。これは、更新を受信しなければならないかまたはそのデータが期限切れになる規定の条件または期間である。識別された存続時間値に従って更新が受信されない場合、リソース属性データは専用サーバから削除される。
【００４３】
本発明による整合性保証のための模範的な諸実施形態は、ネットワーク階層を介してリンクされた複数のノードに保管されたデータ、たとえば、要約またはデータ集約を更新するための方法を含む。リソースの動的属性、たとえば、データ・レートおよび使用可能帯域幅と、これらの動的リソースを含む、生成された要約は、時間の経過につれて連続的に変化する。集約された要約はノードまたはサーバの階層の全体にわたって複製され、サーチをガイドするために使用されるので、その要約は、好ましくは、リソースの現行状態を反映するために十分迅速に更新される。複数のノードに保管されたデータを更新するための方法は、複製された要約と元の要約との間の所与のレベルの整合性を保証する。
【００４４】
ノードの階層全体にわたる要約の伝搬は、階層内の各リンクに沿って定期的に行われる。これらのリンクは、階層内の２つのノード間の接続または経路（path）であり、階層内のブランチまたはトランクを表すものと見なすことができる。階層を介して要約が伝搬されるたびに、通信オーバヘッドなどのオーバヘッドが発生する。伝搬頻度が高くなる、すなわち、更新頻度が高くなると、消費するオーバヘッドが多くなるが、更新頻度が低くなると、現行要約とこれらの要約の伝搬コピーとの整合性に悪影響を及ぼす。したがって、整合性レベルと複製オーバヘッドとの間のトレードオフが存在する。要約がリンクに沿って複製される頻度が高くなるほど、整合性はさらに向上する。しかし、これは複製オーバヘッドの増加という犠牲を払って達成される。本発明によるシステムおよび方法は、整合性とオーバヘッドの消費との間のこのバランスを最適化する。
【００４５】
鮮度という概念は、整合性を定量化するために使用される。本明細書で使用される複製された要約の鮮度とは、元の要約の生成以降の経過時間（elapsed time）または遅れ時間（lag time）である。このような測定基準（metric）は、複製コピーがどのくらい新鮮であるまたは時代遅れであるかを表し、元の要約から複製された要約が入手されて以来、元の要約の値について発生した可能性のある変化がどのくらい大きいかまたは重大であるかも反映することができる。これは、任意の所与のノードに保管された任意のデータまたは複製された要約に関する鮮度しきい値、すなわち、データがリフレッシュされる前の最大使用期間として表すこともできる。たとえば、元のノードまたはサーバＡおよび複製サーバＢの場合、Ａで維持されるデータ要約は、ＲXX（τ）という自己相関関数を含む定常ランダム・プロセスＸ（ｔ）を使用して表すことができる。Ｂにおけるこのデータ要約のレプリカは、Ｘ′（ｔ）として示され、Ｘ（ｔ−δ）であり、ここでδは経過時間である。これらの２つのランダム・プロセス間の差の平均値は以下の式で表すことができる。
【数１】
2009545072.tif 000003
したがって、複製された要約と元の要約との値の差は、経過時間δの関数である。この経過時間は値の差に変換することができ、逆もまた同様であり、この値の差に関する制限または要件は、ノードの階層を介して伝達または複製された、所与の複製された要約または任意のその他のタイプのデータの鮮度、遅れ時間、または最大期間を指定することによって達成される。
【００４６】
図４を参照すると、ネットワーク階層１００に配置された複数のノードが例示されている。ツリー階層として例示されているが、本発明による方法は、本明細書に記載された他のタイプの階層で使用することもできる。各階層は、少なくとも１つのルート・ノード１１０と、１つまたは複数の中間ノード１２０と、１つまたは複数のリーフ・ノード１３０とを含む。このネットワーク階層内では、様々なサーバまたはノードが要約を作成し、たとえば、上述の通り、所与のノードの親、兄弟、およびその兄弟の子孫に、階層を介してその要約を伝搬する、例示されている通り、たとえば、ノードＤ１４０の要約は、その親ノードＥ１５０、その兄弟ノードＣ１６０、リーフ・ノードであるその兄弟の子孫ノードＡおよびＢ１７０に伝搬され複製される。ノードの任意の所与のネットワーク階層内の各ノードごとに、そのノードが次のレベルでその親を有し、その兄弟およびそれらの子孫をさらに下のレベルに有するルートである、複製ツリーが存在する（図５）。各ノードごとに１つの複製ツリーを識別することができ、同じネットワーク階層内に複数のこのような複製ツリーが存在する。
【００４７】
所与のノードをルートとするこのツリーは、その親と、その兄弟と、その兄弟の子孫とを含む、ｎ個のノードの集合Ｖを含む。各ノードνi∈Ｖごとに、Ｔ（νi）は、νiという親ノードが更新されたデータまたはその現在の元の要約をノードνiに送信する期間を示す。実質的に同じサイズを有する更新メッセージの場合、このリンク、すなわち、親ノードとνiとの間のリンクにおける複製オーバヘッドは、１／Ｔ（νi）によって示される。ノードνiに関する最大経過時間は、δ（νi）によって示され、ノードνiのすべての祖先の更新期間の合計である。これは、次のホップの子（hopchild）νの更新期間Ｔ（ν）後にそれぞれの祖先が次のホップの子νを更新するときに発生する。たとえば（図４）、δ（Ａ）＝Ｔ（Ｃ）＋Ｔ（Ｅ）＋Ｔ（Ａ）になる。
【００４８】
本発明の一実施形態によれば、ネットワーク階層内の任意の所与のノードに保管された任意のデータ、たとえば、複製された要約に関するターゲット鮮度限界または最大期間が定義される。この最大期間の場合、各ノードに保管されたデータに関するネットワーク階層内のノード間の複数のリンクのそれぞれによる複製期間または更新期間Ｔ（νi）は、任意の所与のノードに保管されたすべてのデータについて鮮度限界が満足され、データの更新、すなわち、複製に関連する全体的なオーバヘッドが最小限になるように決定される。その後、データは、決定された更新期間に応じて更新される。これは、以下のように最適整合性保証問題について数学的に表すことができ、以下の式のようになるように各ノードνiごとにＴ（νi）を選択する。
【数２】
2009545072.tif 000004
【００４９】
一般に、この最適化問題は、線形制約を含む非線形凸型目的関数（non-linearconvex objective function）を有し、閉形解（closed-form solution）を持たない可能性がある。しかし、いくつかの制約を観察することにより、閉形解構造を導出することができる。第１の制約はリーフ・ノード制約であり、任意のリーフ・ノードｗの場合、遅れ時間限界は厳格であり、すなわち、δ（ｗ）＝Ｃである。これは、矛盾（contradiction）により証明することができる。たとえば、最適解χにおいて、遅れ時間限界はリーフ・ノードｗで厳格ではなく、δ（ｗ）＜Ｃであると想定する。また、ε＝Ｃ−δ（ｗ）＞０とする。Ｔ（ｗ）の値はＴ（ｗ）＋εに増加させることができる。依然として制約のすべてが満足されているが、オブジェクト関数はより小さくなる。したがって、χは最適ではない。
【００５０】
第２の制約は共通祖先制約であり、共通祖先ｕを共用する２つのリーフ・ノードｗ1およびｗ2の場合、ｕからｗ1への経路に沿った更新期間の合計がｕからｗ2の場合と同じになることを示している。これは以下の通りである。このリーフ・ノード制約により、δ（ｗ1）＝δ（ｗ2）＝Ｃが得られる。ｕからｗ1への経路に沿った更新期間の合計はδ（ｗ1）−δ（ｕ）＝Ｃ−δ（ｕ）であり、ｕからｗ2への経路についても同じことが当てはまる。
【００５１】
リーフ・ノード制約を使用すると、不等式制約を等式制約に変更することにより、元の最適化問題が書き直され、すなわち、∀リーフ・ノードｗ，δ（ｗ）＝Ｃになる。どの非リーフ・ノードｕについても、δ（ｕ）はそのリーフ子孫のものより厳密に小さいので、非リーフ・ノードはこの制約から除外される。最適化問題を解くために標準的なラグランジュの方法が適用され、以下の解構造が得られ、これは親子制約になる。親子制約は、任意の非リーフ・ノードｕおよびその子集合Ｃｈｉｌｄ（ｕ）について、
【数３】
2009545072.tif 000005
であるときに、最小合計複製または更新オーバヘッドが達成されることを示している。
【００５２】
これらの３つの制約に基づいて、単純かつ軽量の分散アルゴリズムを使用して最適解を実装する。一実施形態では、このアルゴリズムの実装例は以下の擬似コードに例示されている。
【数４】
2009545072.tif 000006
【００５３】
このアルゴリズムでは、任意の所与のノードは、いくつかのタイプの状態データを保管または維持する。状態データとしては、所与のノードに関連する現行更新期間であって、所与のノードの親ノードが所与のノードにデータ更新の要約を送信しなければならない期間を表すｔと、所与のノードの親ノードから、所与のノードの任意の子リーフ子孫である所与のノードの任意の子リーフ・ノードへの経路に沿った複製期間またはデータ更新期間の合計であるｓを含む（ｓはすべてのリーフ子孫について同じである）。状態データは、スケール・ファクタαも含み、所与のノードの各子ノードごとに１つのスケール・ファクタが維持される。リーフ・ノードにはいずれの子ノードもないので、リーフ・ノードを除くすべてのノードでスケール・ファクタが維持される。一実施形態では、すべてのノードがその状態データを１という値に初期設定する。
【００５４】
保管データを更新するための方法の模範的な諸実施形態は、２つのオーバラップ・フェーズで機能する。第１のフェーズは、すべてのノードに保管された現行状態データをノードの階層を介してルート・ノードにボトムアップ式に報告することである。たとえば、各ノードは、リーフ・ノードから始めて、その現行のｔおよびｓをその親ノードに転送または報告する。非リーフ・ノードである所与のノードがその子ノードのうちの少なくとも１つおよび好ましくはすべてからｔ値を受信した後、そのノードは、共通祖先制約によって要求される通り、状態データで伝達されたｓ値のすべてが同じであるかどうかを判断する。する。すべてのｓ値が同じである場合、所与のノードは、状態データで伝達されたデータ更新期間と組み合わせて親子制約を使用して、その受信側ノードに関するｔを計算する。たとえば（図４）、ノードＣ１６０はそのｔc１６５を以下のように計算する。
【数５】
2009545072.tif 000007
【００５５】
ｓ値が異なり、等しくないと判断された場合、所与のノードは等しくなるようにｓ値を調整する。一実施形態では、所与のノードは、ｓ0というｓ値を有する任意の子ノードを選ぶ。次に、所与のノードは、任意の子ノード、すなわち、ｓ0に関連するデータ更新期間の合計を使用して、所与のノードの他のすべての子ノードのスケール・ファクタを計算する。このスケール・ファクタは、αi＝ｓ0／ｓiとして表される。次に、所与のノードは、この計算されたスケール・ファクタを使用して、所与のノードのすべての子について更新された状態データを計算し、すなわち、ｔi＝ｔiαi，ｓi＝ｓiαi＝ｓ0になる。
【００５６】
等しくなるようにすべてのｓ値を調整した後、所与のノードは親子制約を使用して、それ自体のｓおよびそれ自体のｓをｔ＋ｓ0として計算する。次に、所与のノードは、その状態データ｛ｔ，ｓ｝をその親ノードに再通知または伝達する。たとえば、ノードＥは、ノードＣから｛０．７，１．７｝を、ノードＤから｛１，１｝を受信する。ｓ値は等しくないので、ノードＥはノードＤの状態データを｛１．７，１．７｝にスケーリングし、それ自体のｔEを
【数６】
2009545072.tif 000008
として計算する。ノードＥはその親ノードＦに｛０．６５，２．３５｝を送信する。
【００５７】
最終的に、ルート・ノードＦはそのすべての子から状態データ報告を受信し、ルート・ノードは、すべてのリーフ・ノードが正確に遅れ時間限界Ｃの定義済み最大期間を有するように状態データ内の値を調整する。一実施形態では、ルート・ノードは、必要であればすべての子ノード間で等しくなるようにｓを調整した後でｓの値をＣと比較し、ルート・スケール・ファクタＣ／ｓを求める。次に、ルート・ノードは、各子ノードのｔをｔαとして更新する。たとえば、最大データ期間Ｃ＝１０の場合、ルート・ノードＦはα＝１０／２．３５≒４．２６を計算する。したがって、ルート・ノードはｔEを０．６５×４．２６＝２．７７に更新し、これはルート・ノードがその子ノードＥを更新しなければならない期間である。
【００５８】
最下部、すなわち、リーフ・ノードから、最上部、すなわち、ルート・ノードまで状態データを報告し、ルート・ノードで任意のスケーリング・ファクタを適用して、第２のフェーズが実行される。第２のフェーズはトップダウン・フェーズであり、ルート・ノードから始めて、対応するスケール・ファクタが各子に送信される。その親からスケール・ファクタを受信した後、ノードは、スケール・ファクタに、その子ノードの調整済みのｔ値を掛けて、最終データ更新期間を求める。たとえば、ノードＥは、親ノードＦから４．２６を受信し、ｔC＝４．２６×０．７＝２．９８およびｔD＝４．２６×１．７＝７．２４を更新する。これらは、ノードＥがその子ノードＣおよびＤにデータ更新を送信しなければならないデータ更新期間である。ノードが非リーフ・ノードである場合、そのノードは、その親ノードから受信したスケーリング・ファクタをそれに掛けることにより、その子ノードのスケール・ファクタαも更新する。次に、そのノードは、更新されたスケーリング・ファクタを適切な子ノードに送信する。たとえば。ノードＥは、４．２６に古いα、すなわち、ＣおよびＤの場合の１および１．７を掛けて、４．２６および７．２４を求める。次に、ノードは、これらの値をＣおよびＤにそれぞれ送信する。最終的に、すべての非リーフ・ノードはスケーリング・ファクタを受信し、それぞれの子ノードに対する更新期間を入手する。たとえば、ノードＣは、それが４．２６×１＝４．２６でノードＡおよびＢを更新しなければならないことを把握する。
【００５９】
本発明の模範的な諸実施形態による分散アルゴリズムは、非常に少量のオーバヘッドを使用する。たとえば、各ノードまたはサーバではＯ（ｋ）状態のみが発生し、ｋは所与のノードの子ノードの数であり、各リンクに沿ってＯ（１）メッセージ・オーバヘッドが発生し、各リンクにより１つのボトムアップ・メッセージと１つのトップダウン・メッセージが送信される。
【００６０】
実施例
本発明によるシステムおよび方法のパフォーマンスの模範的な評価は、照会応答時間およびメッセージ・オーバヘッドという２つの測定基準を使用して実行された。応答時間とは、クライアントが照会を送信してから、クライアントがすべての突き合わせレコードを受信するまでの時間である。メッセージ・オーバヘッドとは、すべての制御メッセージの合計サイズである。
【００６１】
リソース発見サービスおよびリゾルバは、Ｊａｖａを使用して実装された。図６に例示されている通り、サーバ２００は、その子の要約２０２，複製された要約２０４、直接接続リソースの要約２０６、そのブランチ要約２０８という４通りのタイプの要約を維持する。要求２１０および応答２１２という２通りのタイプのメッセージを使用して、リソースを発見する。クライアントは、リソースを発見するためにリゾルバ２１４に連絡するかまたはリゾルバ２１４を呼び出す。リゾルバから要求を受信した後、サーバは、接続リソースの要約をチェックし、何らかの一致が見つかった場合に詳細なレコードを求めて接続リソース２１６にさらに照会する。サーバは、その子の要約および複製された要約もチェックする。この一致は、クライアントに戻される応答メッセージ内の参照（referral）として含まれることになる。
【００６２】
ループを回避するために、リゾルバ２１４は、それが照会したサーバに関する「訪問済み（visited）」２１８と、それがまだ照会しなければならない参照されたサーバ（referredserver）に関する「訪問予定（to visit）」２２０という２つのキューを各クライアント要求ごとに維持する。リゾルバは、参照されたサーバがすでにキュー内にあるかどうかをチェックする。参照されたサーバは、それがいずれのキューにもない場合にのみ「訪問予定」キューに追加され、リゾルバがそのサーバに照会した後で「訪問済み」キューに移動される。リゾルバは複数の参照を受信することができるので、リゾルバはマルチスレッドになり、「訪問予定」キュー内のそれぞれのサーバについて１つのスレッドを起動する。
【００６３】
リソース発見は、それぞれがＸｅｏｎ  ３．４ＧＨｚ  ＣＰＵおよび６ＧＢメモリを有する５台のＳｕＳｅ  ９  ＳＰ２  Ｌｉｎｕｘマシンからなるテスト・ベッドで実行される。ＤＢ２データベースを使用して、接続リソースをエミュレートする。各リソース・レコードは、整数、ダブル（double）、タイムスタンプ、文字列、カテゴリ・タイプを含む、１２０通りの属性を有する。数値、タイムスタンプ、および文字列（辞書順を使用）タイプについて下限および上限ならびにヒストグラム要約方法が実装され、カテゴリ・タイプについてはセット和集合が実装される。各データベースは、たとえば、市区町村および州の位置ならびに人の名前など、ランダムに生成されたデータと実際のデータの両方を使用して、データが読み込まれる。各データベースは２００Ｋのレコードを有し、サーバはＪａｖａデータベース接続（ＪＤＢＣ：Java Database Connectivity）インターフェースを使用して、詳細なリソース・レコードを求めてデータベースに照会するかまたは要約を生成することができる。ベンチマークのために、リソース発見は、すべてのレコードが１つの中央データベースに保管される集中手法と比較される。
【００６４】
リゾルバの負荷は多次元照会の集合である。照会は、それぞれの選択性、すなわち、その照会を満足するリソース・レコードのパーセンテージに基づいてグループ化される。０．０１％、０．０３％、０．１％、０．３％、１％、および３％という６つの選択性グループがあり、それぞれ２０個の照会を有する。
【００６５】
全応答時間は、リゾルバとリソース発見サーバとの間のすべての要求−応答交換ラウンドの合計である。リゾルバはマルチスレッドであるので、クライアントは階層内の複数のブランチを並行してサーチすることができる。したがって、全応答時間は最長サーチ・パスによって決定される。最悪の場合、最長パスは、ルート・サーバまたは任意のエントリ・ポイント・サーバから始まり、最深ダウン・リーフ・サーバで終わり、これらのサーバが付き合わせレコードを有するものと想定する。このようなパスの長さ、したがって、要求−応答交換ラウンドは、Ｏ（ｌｏｇ  Ｎ）であり、ここでＮは階層内のサーバの総数である。実際は、これらのサーバはいずれの突き合わせレコードも持たない可能性があり、サーチはこのような深さに到達するかなり前に停止する可能性がある。したがって、平均応答時間はより少なくなる。
【００６６】
リソース発見応答時間（マルチスレッド・リゾルバと単一スレッド・リゾルバの両方）は集中リゾルバと比較される。このセットアップは必ずリソース発見の最悪の場合であり、すなわち、すべてのサーバが照会される。インデックスなしのリソース所有者と、インデックスありのリソース所有者という２つのシナリオについて実験が行われた。各リソース所有者に応じて、インデックス・サポートなしの単純なディレクトリ・サービス実装例を使用する場合もある。
【００６７】
図７を参照すると、マルチスレッド・バージョン２２２は、単一スレッド２２４に比較して５０％〜７０％、集中リゾルバ２２６に比較して２０％〜５０％、応答時間を削減する。適切なインデックスがなくても、リソース・レコードを走査し、突き合わせレコードを送信する個別ディレクトリ・サービスに大部分の時間が費やされるので、本発明によるリソース発見は集中リゾルバより性能が優れている。マルチスレッド・リゾルバにより、複数のディレクトリ・サービスはそれぞれのレコードを同時に走査し送信することができ、１つのディレクトリ・サービスですべてのレコードを実行するより早く完了する。
【００６８】
図８に示されている通り、リゾルバ２２８とサーバ２３０との間の要求−応答交換中の詳細な時間内訳が例示されている。ソケットのオープン２３２、ＪＤＢＣドライバのロード２３４、および要約のチェック２３６という３つの部分は他の部分に比較してかなり小さい。したがって、これらの部分は、各ステップの平均時間を照会選択性の関数として示す図９のグラフには含まれていない。これは、主要部分が照会実行２３８と応答送信時間２４０であることを確認する。
【００６９】
リソース所有者がインデックス・サポート付きのディレクトリ・サービスを使用する場合、応答時間比較が図１０に示されている。この場合、マルチスレッド・バージョン２４２は依然として単一スレッド２４４より５０％〜７０％性能が優れているが、集中リゾルバ２４６は選択性が低いときにより高速になる。しかし、選択性が増加するにつれて、より多くのレコードが送信され、リソース発見のパフォーマンスはこの場合も比較可能なものになる。リソース発見は、選択性が０．３％であるときに応答時間を倍増し、１％の場合にほぼ同じに接近し、選択性が３％になると、この場合も中央リポジトリより２５％性能が優れている。上記の比較により、本発明によるリソース発見のパフォーマンスは中央リポジトリに匹敵すると結論づける。
【００７０】
メッセージ・オーバヘッドに関しては、リソース発見は、ボトムアップおよびトップダウン整合性制御メッセージを含む、制御メッセージを使用する。これらの制御メッセージは、いくつかの状態データ変数のみを含み、一定のサイズのものである。要求メッセージは照会を含み、この照会は数量詞を含み、リソース・レコード内の属性の総数によって制限され、一定のサイズでもある。応答メッセージは、返される参照またはレコードの数に比例したサイズを有する。
【００７１】
残りのメッセージは複製メッセージである。本発明によるリソース発見の複製オーバヘッドが中央リポジトリのものと比較される。Ｎ個のレコードが存在し、そのそれぞれがｎ個の数値属性とｃ個のカテゴリ属性を有するものと想定する。数値属性は、下限／上限または要約に関するヒストグラムを使用し、そのいずれも一定のサイズである。このような要約のサイズがｓ1であり、数値のサイズがｓ2であると想定し、各カテゴリ属性については、セット和集合を使用し、各値のサイズがｓ3であり、Ｎ個のレコード内にｋ個の別個の値が存在するものと想定する。したがって、Ｎ個のすべてのレコードに関する要約はＳsummary＝ｎｓ1＋ｃｋｓ3になり、元のデータ・サイズはＳorigin＝Ｎ（ｎｓ2＋ｃｓ3）になる。
【００７２】
レコード内の属性を考慮すると、ｎ、ｃは一定であるので、ＳsummaryはＯ（１）になる。ＳoriginはＯ（Ｎ）になり、これは複製されたレコードの総数に比例して増加する。したがって、リソース発見は、リソース・レコードの数にかかわらず複製オーバヘッドを一定に保持することができ、中央リポジトリは線形オーバヘッドを有する。
【００７３】
整合性制御に関しては、本発明によるリソース発見は、所与の限界内に整合性を保持する能力を有する。図１１は、９個のリソース発見サーバ２４８と１２個の個別リソース所有者２５０からなるでも・セットアップを示している。所有者Ｄ４  ２５２のリソースの動的属性であるｄａｔａ＿ｒａｔｅの要約の上限は、１秒ずつ増加することができる。ターゲット鮮度限界は２５０秒に設定され、他の６つのサーバの複製された要約の上限が追跡される。図１２は、元の上限とその複製コピーの変化を時間の関数として示している。示されている通り、６つのすべての複製コピーの遅れ時間は必ず、２５０という定義済み限界２５４の範囲内になる。
【００７４】
本発明によるリソース発見システムでは、おそらく複数のルート・サーバを有するツリー階層にサーバを配置している。しかし、これらのリソース発見システムは、親の選択がより柔軟な、より一般的なモデルに拡張することができる。たとえば、各サーバまたはノードは複数の親を同時に選択することができる。したがって、サーバ２６０は、ブランチ２６４を相互に共用できるツリー２６２を形成する（図１３）。この階層配置は、より柔軟なコラボレーション・シナリオをサポートする。あるリソース所有者２６５は複数のグループに参加している可能性があり、そのそれぞれはグループに関する目的のために共同作業する必要がある。各グループはそれ自体のサーバ・ツリー構造を形成することができる。したがって、この所有者のための接続ポイント・サーバは、種々のツリーを結合し、対応するツリー内の各グループに意図されたリソース要約のみを伝搬することができる。
【００７５】
リソース所有者間のコラボレーションは様々な形を取ることができ、本発明によるリソース発見は多種多様な形式をサポートすることができる。リソース所有者は、他のすべての当事者に同等のサービスを提供することができる。この場合、単純にそのリソースをエクスポートし、誰でもそれをサーチして使用できるようにする。また、所有者は、ユーザ同士を差別化し、指定の当事者のみに特定のリソースを提供することもできる。リソース発見サーバは、ユーザＩＤに基づいて要約をサーチするように拡張することができる。また、リソース所有者は、そのリソースの種々のビューを複数の接続ポイントにエクスポートすることもでき、これらの接続ポイントはそれぞれのユーザのみから照会を受け入れる。
【００７６】
本発明によるオーバレイ構造により、サーバはその兄弟、その祖先、および祖先の兄弟から要約を複製することができる。リソース所有者は、その要約伝搬の範囲を制限する必要がある場合もあれば、その要約をさらに伝搬しないよう接続ポイントに指示する場合もあれば、伝搬された要約において下限／上限などの最も粗い形式を使用するよう接続ポイントに要求する場合もある。
【００７７】
本発明の模範的な諸実施形態による方法およびシステムは、完全にハードウェアの一実施形態、完全にソフトウェアの一実施形態、またはハードウェアとソフトウェアの両方の要素を含む一実施形態の形を取ることができる。好ましい一実施形態では、本発明は、ファームウェア、常駐ソフトウェア、およびマイクロコードを含むがこれらに限定されないソフトウェアで実装される。加えて、模範的な方法およびシステムは、コンピュータ、論理処理装置、または任意の命令実行システムによりあるいはそれに関連して使用するためのプログラム・コードを提供するコンピュータ使用可能媒体またはコンピュータ可読媒体からアクセス可能なコンピュータ・プログラム（computer program product）の形を取ることができる。この説明のために、コンピュータ使用可能媒体またはコンピュータ可読媒体は、命令実行システム、装置、またはデバイスによりあるいはそれに関連して使用するためのプログラムを収容、保管、伝達、伝搬、または伝送可能な任意の装置にすることができる。適切なコンピュータ使用可能媒体またはコンピュータ可読媒体は、電子、磁気、光、電磁、赤外線、または半導体システム（あるいは装置またはデバイス）もしくは伝搬媒体を含むが、これらに限定されない。コンピュータ可読媒体の例としては、半導体またはソリッド・ステート・メモリ、磁気テープ、取り外し可能コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、剛性磁気ディスク、および光ディスクを含む。光ディスクの現在の例としては、コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、書き換え可能コンパクト・ディスク（ＣＤ−Ｒ／Ｗ）、およびＤＶＤを含む。
【００７８】
プログラム・コードの保管または実行あるいはその両方に適したデータ処理システムは、システム・バスを介して記憶素子に直接または間接的に結合された少なくとも１つのプロセッサを含むが、これに限定されない。記憶素子としては、プログラム・コードの実際の実行中に使用されるローカル・メモリと、大容量記憶装置と、実行中に大容量記憶装置からコードを検索しなければならない回数を削減するために少なくとも何らかのプログラム・コードの一時記憶を提供するキャッシュ・メモリとを含む。キーボード、ディスプレイ、およびポインティング・デバイスを含むがこれらに限定されない入出力またはＩ／Ｏ装置は、直接あるいは介在する入出力コントローラを介してシステムに結合することができる。また、本発明による方法およびシステムの模範的な諸実施形態は、データ処理システムが介在する私設網または公衆網を介してその他のデータ処理システムあるいはリモート・プリンタまたは記憶装置に結合された状態になれるようにするためにシステムに結合されたネットワーク・アダプタも含む。現在使用可能な適切なタイプのネットワーク・アダプタは、モデム、ケーブル・モデム、ＤＳＬモデム、イーサネット・カード、およびそれらの組み合わせを含むが、これらの限定されない。
【００７９】
一実施形態では、本発明は、マシンまたはコンピュータによって読み取られたときに、本発明の模範的な諸実施形態による分散情報技術システム内の連合リソース発見のための方法または階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するための方法をマシンまたはコンピュータに実行させるマシン実行可能コードまたはコンピュータ実行可能コードを含むマシン可読媒体またはコンピュータ可読媒体、ならびにそのコンピュータ実行可能コードそのものを対象とする。マシン可読コードまたはコンピュータ可読コードは、マシンまたはコンピュータによって読み取り、実行することができる任意のタイプのコードまたは言語にすることができ、機械語、アセンブラ言語、高水準言語、オブジェクト指向言語、およびスクリプト言語を含む、当技術分野で既知であって入手可能な任意の適切な言語または構文で表現することができる。コンピュータ実行可能コードは、本発明によるシステムによって使用されるコンピュータ・ネットワーク内に配置され、それと通信状態にあり、それによってアクセス可能なデータベースを含む、任意の適切な記憶媒体またはデータベースに保管することができ、本発明の提示を制御するために使用される制御システムを含む、当技術分野で既知であって入手可能な任意の適切なハードウェア・プラットフォーム上で実行することができる。
【００８０】
本明細書に開示されている本発明の例示的な諸実施形態が本発明の諸目的を果たすことは明らかであるが、当業者であれば多数の変更例およびその他の実施形態を考案できることは認識されている。さらに、任意の実施形態による特徴（複数も可）または要素（複数も可）あるいはその両方は、単独でまたは他の実施形態（複数も可）と組み合わせて使用することができ、本発明による方法のステップまたは要素は任意の適切な順序で実行または遂行することができる。したがって、特許請求の範囲は本発明の精神および範囲の範囲内になると思われるこのような変更例および実施形態のすべてを包含するためのものであることが理解されるであろう。
【図面の簡単な説明】
【００８１】
【図１】本発明を使用できる専用サーバ階層および分散コンピューティング・システムの一実施形態の概略表現である。
【図２】本発明を使用できる専用サーバ階層の一実施形態の概略表現である。
【図３】本発明による照会処理の一実施形態を例示する概略表現である。
【図４】複製および整合性保証で使用するためのノードの複製ツリー階層の一実施形態の概略表現である。
【図５】ルート・ノードとして配置されたツリー階層からのノードの一実施形態の概略表現である。
【図６】本発明とともに使用するためのリソース発見サーバの一実施形態の概略表現である。
【図７】インデックスが使用不能であるときの照会選択性の関数として全応答時間を例示するグラフである。
【図８】本発明による要求および応答照会交換の時間内訳の一実施形態の概略表現である。
【図９】インデックスが維持されているときの照会選択性の関数として応答時間の主要部分を例示するグラフである。
【図１０】応答時間対選択性を例示するグラフである。
【図１１】ツリー階層による要約の複製の概略表現である。
【図１２】複製された要約により元の要約の変化を追跡することを例示するグラフである。
【図１３】本発明とともに使用するためのノードのネットワーク階層の他の実施形態の概略表現である。
【図１】
2009545072.tif 000009
【図２】
2009545072.tif 000010
【図３】
2009545072.tif 000011
【図４】
2009545072.tif 000012
【図５】
2009545072.tif 000013
【図６】
2009545072.tif 000014
【図７】
2009545072.tif 000015
【図８】
2009545072.tif 000016
【図９】
2009545072.tif 000017
【図１０】
2009545072.tif 000018
【図１１】
2009545072.tif 000019
【図１２】
2009545072.tif 000020
【図１３】
2009545072.tif 000021
【手続補正書】
【提出日】平成21年6月16日(2009.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するための方法において、
前記ノードのネットワーク階層内の任意の所与のノードに保管された任意のデータについて鮮度しきい値を定義するステップと、
任意の所与のノードに保管されたすべてのデータについて前記鮮度しきい値が満足され、データの更新に関連するオーバヘッドが最小限になるように、各ノードに保管されたデータについて前記ネットワーク階層内の前記ノード間の複数のリンクのそれぞれによる更新期間を決定するステップと、
前記ノードに保管されたデータを前記決定された更新期間に応じて更新するステップと、
を含む、方法。
【請求項２】
前記複数のノードが、ツリー階層に配置されたサーバを含む、請求項１に記載の方法。
【請求項３】
前記複数のノードがツリー階層に配置される、請求項１に記載の方法。
【請求項４】
前記更新期間を決定する前記ステップが、
その現行データ更新期間と、その親ノードから１つまたは複数のリーフ・ノードへのすべてのデータ更新期間の合計とを前記ノードの階層内の各ノードから親ノードに伝達するステップであって、前記現行データ更新期間が、所与のノードの親ノードがそのノードにデータ更新を送信しなければならない期間を含むステップと、
前記鮮度しきい値が前記ノードの階層内のすべてのリーフ・ノードで満足されるように前記伝達された現行データ更新期間と更新期間合計を調整するステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記更新期間を決定する前記ステップが、
前記ノードの階層内の各ノードで状態データを維持するステップであって、所与のノードの前記状態データが、
前記ノードに関連し、その親ノードがデータ更新を送信しなければならない期間を表す現行データ更新期間と、
その親ノードから前記ノードの任意の子孫リーフ・ノードへの前記データ更新期間の合計と、
を含む、ステップと、
非リーフ・ノードの各子ノードに関連するスケール・ファクタを各非リーフ・ノードで維持するステップと、
をさらに含む、請求項３に記載の方法。
【請求項６】
各ノードで維持された前記状態データを前記ノードの階層を介してルート・ノードに上に伝達するステップをさらに含む、請求項５に記載の方法。
【請求項７】
前記状態データを前記階層を介して伝達する前記ステップが、
前記状態データで伝達された前記データ更新期間のすべての合計が等しい場合に、前記伝達された状態データ内の前記データ更新期間を使用する受信側ノードに関するデータ更新期間を、前記伝達された状態データをその子ノードから受信する前記ノードの階層内の各ノードで計算するステップ
をさらに含む、請求項６に記載の方法。
【請求項８】
前記状態データを前記階層を介して伝達する前記ステップが、
所与のノードで、前記状態データで伝達された前記データ更新期間の前記合計のすべてが等しいわけではないと判断するステップと、
前記所与のノードの任意の子ノードを選択するステップと、
前記任意の子ノードに関連する前記データ更新期間の前記合計を使用して、他のすべての子ノードに関するスケール・ファクタを計算するステップと、
前記計算されたスケール・ファクタを使用して、前記所与のノードのすべての子に関する更新された状態データを計算するステップと、
前記更新された状態データを前記所与のノードから前記ノードの階層を介して上に伝達するステップと、
をさらに含む、請求項６に記載の方法。
【請求項９】
ルート・ノードのすべての子ノードから前記ルート・ノードで状態データを受信するステップと、
前記鮮度しきい値が前記ルート・ノードのすべてのリーフ・ノードで達成されることを保証するために、前記ルート・ノードで受信された前記状態データに対する調整を行うステップと、
をさらに含む、請求項６に記載の方法。
【請求項１０】
調整を行う前記ステップが、前記定義された鮮度しきい値に等しくなるように各リーフ・ノードにおける合計更新期間を調整するステップをさらに含む、請求項９に記載の方法。
【請求項１１】
調整を行う前記ステップが、
各リーフ・ノードに関連する前記合計更新期間を共通同等値に調整するステップと、
前記共通同等値を前記鮮度しきい値と比較するステップと、
前記共通同等値に対する前記鮮度しきい値の比率としてスケール・ファクタを求めるステップと、
前記スケール・ファクタを使用して、各リーフ・ノードで現行更新期間を調整するステップと、
をさらに含む、請求項９に記載の方法。
【請求項１２】
前記スケール・ファクタを前記ルート・ノードの各子ノードに伝達するステップと、
前記スケール・ファクタを使用して、各子に関する現行更新期間を調整するステップと、
をさらに含む、請求項１１に記載の方法。
【請求項１３】
コンピュータによって読み取られたときに、階層に編成され、ネットワークを介してリンクされた複数のノードに保管された複製データを更新するための方法を前記コンピュータに実行させるコンピュータ可読コードを含むコンピュータ可読媒体において、前記方法が、
前記ノードのネットワーク階層内の任意の所与のノードに保管された任意のデータについて鮮度しきい値を定義するステップと、
任意の所与のノードに保管されたすべてのデータについて前記鮮度しきい値が満足され、データの更新に関連するオーバヘッドが最小限になるように、各ノードに保管されたデータについて前記ネットワーク階層内の前記ノード間の複数のリンクのそれぞれによる更新期間を決定するステップと、
前記ノードに保管されたデータを前記決定された更新期間に応じて更新するステップと、
を含む、コンピュータ可読媒体。
【請求項１４】
前記複数のノードがツリー階層に配置される、請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記更新期間を決定する前記ステップが、
その現行データ更新期間と、その親ノードから１つまたは複数のリーフ・ノードへのすべてのデータ更新期間の合計とを前記ノードの階層内の各ノードから親ノードに伝達するステップであって、前記現行データ更新期間が、所与のノードの親ノードがそのノードにデータ更新を送信しなければならない期間を含むステップと、
前記鮮度しきい値が前記ノードの階層内のすべてのリーフ・ノードで満足されるように前記伝達された現行データ更新期間と更新期間合計を調整するステップと、
をさらに含む、請求項１４に記載のコンピュータ可読媒体。
【請求項１６】
前記更新期間を決定する前記ステップが、
前記ノードの階層内の各ノードで状態データを維持するステップであって、所与のノードの前記状態データが、
前記ノードに関連し、その親ノードがデータ更新を送信しなければならない期間を表す現行データ更新期間と、
その親ノードから前記ノードの任意の子孫リーフ・ノードへの前記データ更新期間の合計と、
を含む、ステップと、
非リーフ・ノードの各子ノードに関連するスケール・ファクタを各非リーフ・ノードで維持するステップと、
をさらに含む、請求項１５に記載のコンピュータ可読媒体。
【請求項１７】
各ノードで維持された前記状態データを前記ノードの階層を介してルート・ノードに上に伝達するステップをさらに含む、請求項１６に記載のコンピュータ可読媒体。
【請求項１８】
前記状態データを前記階層を介して伝達する前記ステップが、
前記状態データで伝達された前記データ更新期間のすべての合計が等しい場合に、前記伝達された状態データ内の前記データ更新期間を使用する受信側ノードに関するデータ更新期間を、前記伝達された状態データをその子ノードから受信する前記ノードの階層内の各ノードで計算するステップ
をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
前記状態データを前記階層を介して伝達する前記ステップが、
所与のノードで、前記状態データで伝達された前記データ更新期間の前記合計のすべてが等しいわけではないと判断するステップと、
前記所与のノードの任意の子ノードを選択するステップと、
前記任意の子ノードに関連する前記データ更新期間の前記合計を使用して、他のすべての子ノードに関するスケール・ファクタを計算するステップと、
前記計算されたスケール・ファクタを使用して、前記所与のノードのすべての子に関する更新された状態データを計算するステップと、
前記更新された状態データを前記所与のノードから前記ノードの階層を介して上に伝達するステップと、
をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【請求項２０】
前記方法が、
ルート・ノードのすべての子ノードから前記ルート・ノードで状態データを受信するステップと、
前記鮮度しきい値が前記ルート・ノードのすべてのリーフ・ノードで達成されることを保証するために、前記ルート・ノードで受信された前記状態データに対する調整を行うステップであって、
各リーフ・ノードに関連する前記合計更新期間を共通同等値に調整するステップと、
前記共通同等値を前記鮮度しきい値と比較するステップと、
前記共通同等値に対する前記鮮度しきい値の比率としてスケール・ファクタを求めるステップと、
前記スケール・ファクタを使用して、各リーフ・ノードで現行更新期間を調整するステップと、
前記スケール・ファクタを前記ルート・ノードの各子ノードに伝達するステップと、
前記スケール・ファクタを使用して、各子に関する現行更新期間を調整するステップと、
によって調整を行うステップと、
をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【国際調査報告】
2009545072.tif 000022