説明

全地球的にアドレス可能なオブジェクト及び関連するビジネスモデルの経路設定及び索引付けを行うためのシステム、方法及びプログラミング

【課題】方法、装置、及び機械読取可能なメモリに記録されたプログラミングを地球規模のネットワーク上のオブジェクトの索引の検索及び取得のために提供する。
【解決手段】本発明によるシステムは、経路設定層に分散型索引を組み込み、高速検索を可能にする。本方法は、参加しているノード、オブジェクト及び関連するメタデータの完全に分散化した動的な挿入、照合、取得、及び削除を提供する。ノードは、ネットワークに動的に加わり又離れることができる。このインフラは、出版、検索、ダウンロード、及びストリーミングのためのコンテンツネットワークに適用し得る。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、全地球的にアドレス可能なオブジェクト及び関連するビジネスモデルの経路設定及び索引付けのためのシステム、方法及びプログラミングに関する。
【背景技術】
【0002】
コンピュータ処理用ハードウェア能力の継続的な増大と相俟って、インターネットアクセスの急速な採用により、ネットワークサービスにおいて新しい膨大な機会が創造されてきている。しかしながら、ネットワークの状態は、クライアントーサーバモデルに大きく依存しており、ウェブが導入された8年前のインターネットのそれに今でも極めて似通っている。
【0003】
過去8年間、PCの接続性及び能力の傾向によれば、驚異的な数のPCがインターネットに接続され、膨大な量のCPU、ディスク、及び帯域幅資源が生成されてきた。しかしながら、これらPCのほとんどが、決してそれらの全能力を用いていない。極めて多くのマシンが今でも、そうする能力が新たに見出されたにも拘らず、決してサーバとして機能せず、クライアントとしてのみ機能している。
【0004】
クライアントーサーバモデルは、数多くの問題を抱えている。サーバは、維持に経費がかかり、ハードウェア、帯域幅、及び運用コストに経費が必要である。インターネット上のトラフィックは、予測不能である。即ち、いわゆる“スラッシュドット(Slashdot)効果”において、サイト上のコンテンツは、急激に人気を博すことがあり、クライアント要求にそれ以上応じられない程、サイトのサーバが氾濫することがある。同様に、集中型サイトでは、そのサイトのネットワークへの接続が氾濫することによってサイトをダウンさせ得る悪質なトラフィックというサービス拒否(DoS)攻勢を被ることがある。更に、幾つかのネットワークサービス、特に、大きな規模で映像又は音声を提供するなどの帯域幅集中サービスは、要求帯域幅が任意の単一のサイトの容量を超過するため、集中型モデルでは全く不可能である。
【0005】
最近、幾つかの分散型のピアツーピア技術、特に、フリーネット(フリーネット)及びグヌーテラ(Gnutella)が、ユーザのPCの総能力を利用して、ネットワークサービスを運用し、また、コンテンツのサービス提供コストを低減するために生み出されている。しかしながら、フリーネットは、比較的遅く、また、グヌーテラから任意のコンテンツを実際にダウンロードすることは、かなり困難である。このことは、プロトコルが数千ホストを超えてスケール変更せず、従って、ネットワーク上のアクセス可能なコンテンツの量が制限されるためである。
【0006】
オブジェクト照合のO(logn)時間(ここで、nは、ネットワークに参加しているノードの数であり、各時間ステップは、ピアマシンが他のピアマシンと交信相手することから成る)を提案する幾つかの研究プロジェクトは、様々な開発段階にあり、バークレイでのオーシャンストア(OceanStore)及びMITでのコード(Chord)が含まれる。しかしながら、1000ホスト程度と小さいネットワークの場合でさえ、lognは、10ホップであり、このことは、0.5分を上回る照合時間を提案する。更に、これらのシステムは、明らかに信頼性のためではなく、スケール変更可能性のために設計され、また、それらの信頼性は、信頼性の低いマシン上で動作するという現実世界の条件下では、テストされていない。
【発明の概要】
【発明が解決しようとする課題】
【0007】
本特許出願の該当譲受人であるスカイリス(Skyris)ネットワーク社は、スケール変更可能で耐故障性であることによって、分散型ネットワークサービスのニーズを満足する分散型索引付けのための新しくもっと効率的なアルゴリズムを開発した。この明細書において、我々は、いわゆる“トランスペアレントな索引付け”と我々が呼ぶ新しい経路設定及び検索方式を提案する。この方式では、検索索引は、大きくスケール変更可能であり耐故障性でランダム化された分散型経路設定層に組み込まれる。この経路設定及び索引付け層は、分散型ディレクトリサービスとして、即ち、これらの特性を共有し、信頼性が高く効率的で負荷のバランスが取れたネットワークサービスを構築するプラットフォームとして機能する。
【0008】
我々の待ち行列時間ベースのシミュレーションにより、スカイリス(SKYRIS)は、何十億台のサーバのネットワーク上で効率的に動作し得ることが分かる。更に、スカイリスネットワークは、わずかな待ち時間を許容することで、任意の分布のホットスポット(人気コンテンツの小規模部分)、即ち、突然人気が出たコンテンツを扱うことができ、また、トランスペアレントに扱うことが可能である。
【課題を解決するための手段】
【0009】
以下の設計目標は、スカイリスにとって主要なものであり、また、我々の研究の方向を決定したものである。
【0010】
スケール変更可能な記憶及び検索:スケール変更可能性は、スカイリスの最も重要な特徴の1つである。当初から、スカイリスプロジェクトは、潜在的に何十億台ものピアマシンの地球規模のシステムに合わせてスケール変更するように設計されている。
【0011】
効率的な取得:我々の目標は、スカイリスをウェブより高速でないにしろ、ウェブと同じように高速にすることである。新しいドメインのウェブ上で照合を行う場合、IPアドレスをユーザに提供する前に、幾つかの階層的交信相手を行い得るDNSシステムを最初にチェックする。目的は、幾つかのホップ内においてスカイリスシステムを同様に維持することであり、この場合、ホップは、1つのピアマシンから次のピアマシンに渡されるメッセージから成る。規模がより大きいファイルの場合、多数のソースから同時に取得するなどの他の方法があり、これによって、システムスループットが増大する。
【0012】
信頼性及び耐故障性:マシンが警告無しでクラッシュした場合、スカイリス上のクライアントは、依然として、ミラー化されたドキュメントを迅速に取得できる。マシンは、回復した場合、問題を生じることなく、シームレスにネットワークに復帰できる。耐故障性は、分散型ピアツーピアネットワークの場合、主要な問題であることに留意されたい。このようなネットワークは、サーバより極めて信頼性の低いユーザのPC上で動作し、また、更に、ユーザは、バックグラウンドにプログラムを置き去りにするよりもむしろそれをもっと頻繁に開いたり閉じたりしたいと願うことがある。
【0013】
負荷均衡化:ネットワーク全体は、驚異的な容量を有するが、個々のマシンは、能力が不足している。スカイリスは、マシンの過負荷を回避するために、システム全体に渡って均等に負荷(基本的には帯域幅)を分散しなければならない。スカイリスは、スケール変更が可能であり、また、耐故障性の双方である最初のシステムを実現し得たという点で独特であり、更に、たまたまプラットフォームが効率的であり、また、負荷が幾つかの追加的な努力で均衡な状態にし得るという点において、独特である。
【図面の簡単な説明】
【0014】
【図1】本発明の種々の側面の1つを示す概略図。
【図2】本発明の種々の側面の1つを示す概略図。
【図3】本発明の種々の側面の1つを示す概略図。
【図4】本発明の種々の側面の1つを示す概略図。
【図5】本発明の種々の側面の1つを示す概略図。
【図6】本発明の種々の側面の1つを示す概略図。
【図7】本発明の種々の側面の1つを示す概略図。
【図8】本発明の種々の側面の1つを擬似コード形式で示す図。
【図9】本発明の種々の側面の1つを擬似コード形式で示す図。
【図10】本発明の種々の側面の1つを擬似コード形式で示す図。
【図11】本発明の種々の側面の1つを擬似コード形式で示す図。
【図12】本発明の種々の側面の1つを擬似コード形式で示す図。
【図13】本発明の種々の側面の1つを擬似コード形式で示す図。
【図14】本発明の種々の側面の1つを擬似コード形式で示す図。
【図15】本発明の種々の側面の1つを擬似コード形式で示す図。
【図16】本発明の種々の側面の1つを擬似コード形式で示す図。
【図17】本発明の種々の側面の1つを擬似コード形式で示す図。
【図18】本発明の種々の側面の1つを擬似コード形式で示す図。
【図19】本発明の種々の側面の1つを擬似コード形式で示す図。
【図20】本発明の種々の側面の1つを擬似コード形式で示す図。
【図21】本発明の種々の側面の1つを擬似コード形式で示す図。
【図22】本発明の種々の側面の1つを擬似コード形式で示す図。
【図23】本発明の種々の側面の1つを擬似コード形式で示す図。
【図24】本発明の種々の側面の1つを擬似コード形式で示す図。
【図25】本発明の種々の側面の1つを擬似コード形式で示す図。
【図26】本発明の種々の側面の1つを擬似コード形式で示す図。
【図27】本発明の種々の側面の1つを擬似コード形式で示す図。
【図28】本発明の種々の側面の1つを擬似コード形式で示す図。
【図29】本発明の種々の側面の1つを擬似コード形式で示す図。
【図30】本発明の種々の側面の1つを擬似コード形式で示す図。
【図31】本発明の種々の側面の1つを擬似コード形式で示す図。
【図32】本発明の種々の側面の1つを擬似コード形式で示す図。
【発明を実施するための形態】
【0015】
これら及び本発明の他の側面は、添付の図面と共に好適な実施形態の以下の説明を読むと、更に明らかになるであろう。
【0016】
我々は、新しい経路設定及び索引付けフレームワークと、局所的な情報のみを用いて何十億台ものPCに対して耐故障性でスケール変更可能な具体的な方式と、を提示する。他のシステムも当社のものと同様にスケール変更しない。オーシャンストアは、プラクストン(Plaxton)のアルゴリズムに基づくが、スケール変更可能性を試みたものとして有名である。また、MITのコードプロジェクトが有名であり、これは、nをそのシステムにおけるノードとすると、O(logn)照合時間でスケール変更するが、これは、大規模なネットワークに対してスケール変更するのに充分な程耐故障性であるように、また、そう見えるように特に設計されてはいない。
【0017】
本経路設定及び索引付け方式は、スカイリスプロジェクトの中核の権能付与部である。ホットスポット管理の新しい関連した方法と共に、我々の経路設定及び索引付け方式によって、スカイリスネットワークの特性を用いて、キーワード検索並びに分散型情報取得及び配信を含み、数多くの有用で効率的でスケール変更可能な、また耐故障性のサービスの構築が可能である。
【0018】
システムの中核は、幾つかの別個の層から成る:
・経路設定(テーブル及びプロトコル)
・索引付け(テーブル及びプロトコル)
・ホットスポット管理
【0019】
プラットフォームへのインターフェイスは、単純であり、従って、コンテンツの検索及び記憶等の追加の層は、この中央フレームワーク上に簡単に構築し得る。
【0020】
経路設定
図1は、スカイリスネットワーク100の極めて概略的な図を提供する。
このネットワークでは、複数のノード102が、図1に示すインターネット104等のネットワークを介して接続される。幾つかの実施形態において、スカイリスネットワークは、中央サーバノート106を有し得る。他の実施形態では、各々、このような中央サーバ無しで動作し得る。
【0021】
図1に示すように、スカイリスネットワークは、数多くの異なるタイプのコンピュータ処理装置で用い得る。現時点では、スカイリスネットワークにおいてノードとして機能する能力を有し得る最も普通のタイプのコンピュータ処理装置は、傾向的に、図1に示すコンピュータ1等のデスクトップコンピュータ、ラップトップコンピュータ、及び他のより大型のコンピュータである。しかしながら、より小型の電子装置の能力が大きくなるにつれて、将来、スカイリスネットワークは、携帯タブレットコンピュータ102C、携帯情報端末コンピュータ102D、携帯電話102Eに搭載されたコンピュータ、及び、図1に示す腕時計コンピュータ102Fのような着用可能なコンピュータ等の更により小さい装置のコンピュータ等、より小型のコンピュータで使用可能になるであろう。
【0022】
スカイリスネットワークのノードは、ケーブルモデム又は現在普通の形態のセル方式通信等、比較的遅い接続でネットワークに接続し得る。しかしながら、ネットワークが、ケーブルモデム、DSL、無線LAN、又は高速無線接続等のより高速の接続を有する場合、ノードは、ネットワークからより良いサービスを受信し、また、ネットワークに対して価値が高まるであろう。
【0023】
図1において、ノード102Aは、概略ブロック図に表される。この図は、ノートが、中央プロセッサ110;ランダムアクセスメモリ112;CPUとメモリを接続するバス114、及び表示装置118を駆動するための映像インターフェイス116を有することを示す。このコンピュータは、キーボード122やマウス124等、ユーザ入力装置とインターフェイスを取るためのI/Oインターフェイス120も含む。また、ノード102Aが、スカイリスネットワークの他のノード102と通信を行えるようにするためのネットワークインターフェイス126も含まれる。
【0024】
また、ノード102Aは、ハードディスク、フロッピー(登録商標)ディスク、CDROM、又は大型固体メモリ等の大容量記憶装置も含む。この大容量記憶装置は、オペレーティングシステム130のプログラミング命令、ブラウザプログラム132、及びプラグイン134の形態でスカイリスプログラミングを記憶する。
【0025】
幾つかの実施形態では、スカイリスプログラムは、独立のアプリケーションとして動作するであろうが、多くの実施形態では、プラグとして動作し、また、これによって、ユーザは、ブラウザプログラム132によって生成されたブラウザインターフェイス内から、スカイリスネットワークを用いて、コンテンツにアクセスし得るであろう。
【0026】
スカイリスネットワークは、何百万台、恐らく、何十億台のPC及び他のタイプのコンピュータに対してスケール変更するように設計される。
【0027】
しかし、各ホストは、固定された記憶容量、はるかにより小さいメモリ能力、及び様々なネットワーク帯域幅を有し、モデムと同じように遅い可能性がある。我々は、任意のサーバが、任意の他のサーバを見つけて、それと通信を行い得ることを望む。従って、ネットワークの土台の1つは、小さい規模と可変ネットワークオーバーヘッドを有する経路設定アルゴリズムでなければならない。
【0028】
更に、我々は、(クラッシュ、リブート、ネットワークからの切断、スカイリスプログラムのシャットダウン、故障するネットワークへの接続など)、これらのマシンが頻繁に故障すると予想するため、我々は、情報を複製しなければならない。我々の手法は、管理可能なサイズの局所的な“区域”、即ち、ノードグループを作成して、各区域が、一斉送信を介して(通常、マルチキャストにより)、その区域のマシン用の局所的な索引及び交信相手情報を事前に複製するようにすることである。従って、ノードは、頻繁に消えるが、ネットワークが反応する機会を与えられる前に区域の全ノードが消え失せることは決してあり得ない程、区域は充分大きい。(本明細書の他の部分及び後続の請求項では、我々は、このような区域を“論理ノード”とも呼ぶ)。
【0029】
更に、我々は、新しいサーバが我々のネットワークに加わることを予想する。従って、我々の経路設定システムは、耐故障性(ノード削除可能)であるだけでなく、その場で、新しいマシンをネットワークに負荷し得ることも必要である。
【0030】
我々は、個々のマシン上で動作しないが、我々の“区域”で動作する既存の離散的な経路設定ネットワークに基づき、この問題を解決する新しい経路設定アルゴリズムを開発する。区域サイズが大きくなり過ぎる場合、我々は、区域を2つに分割する。区域サイズが小さくなり過ぎる場合、我々は、2つの区域を1つに併合する。
【0031】
我々は、スカイリスフレームワークに合わせて、2つの古典的なネットワークモデルを一般化した。それらは、ハイパーキューブモデル、及びサイズ2のデ・ブルジン(deBruijn)ネットワークである。ハイパーキューブの利点は、多数のリンクを犠牲にしたスループット効率及びより単純な区域管理である。デ・ブルジンの利点は、極めて少数のリンクであるが、スループット効率は減少し、また、耐故障性は小さくなる。
【0032】
留意されたいことは、区域概念の場合、これは動的な分割を含むが、他のネットワークモデルを用いることも同様に可能であること、また、ネットワークモデルのための2つの主な要件は、充分な局所性があること(隣接区域は、互いに近接すること)、及び、ネットワークを記述するパラメータの系統の柔軟性が充分なことである。第2の条件では、経路設定モデルは、サイズnのネットワークが与えられると、kが小さい場合(上例ではk=2)、サイズnkの同様な経路設定モデルに拡張し得ることが必要である。ハイパーキューブは、局所性及び分割の容易さの双方に対して最良のネットワークモデルであるが、デ・ブルジンモデルは、適合し得る他の古典的なネットワークモデルの一例である。この場合、困難さの度合いはより大きく、区域分割には、例えば、マシンの交信相手の半分を再割当てする必要があるが、交信相手の数は、より小さい。
【0033】
また留意に値することは、希望があれば、区域の概念は、例えば確率的に、隣接区域がある程度オーバーラップするように、あるいは、例えばマシンの帯域幅等に基づき、各マシンが複数の区域に割り当てられるように変更し得るということであり、この概念には、様々な簡単な変形例が存在する。これらを共に結ぶ糸は、それらは、例えば、距離関数を通して、幾つかの近隣ホストの集まりにおいて情報を複製するマシンの局所性の何らかの概念を保持していることである。情報を受信するホストの組は、接続速度又はマシンの有用性により変わりことがあり、また、情報により変わり得る。実際、人気コンテンツの‘ホットスポット’を扱うために、我々は、コンテンツの人気の度合いに基づき、その情報をより大きな区域に複製する。
【0034】
我々は、交信相手をキャッシュ処理するための専用の方式と共に、一般化したハイパーキューブアルゴリズムを用いるつもりであるが、この方式は、ハイパーキューブ(耐故障性)、デ・ブルジン(リンク数少)、及びランダム化されたモデル(ネットワークのスケール変更可能)の最良の側面を組み合わせる。次に、我々は、一般化したハイパーキューブ経路設定アルゴリズムについて説明する。
【0035】
ランダム化されたハイパーキューブモデル
我々のランダム化されたハイパーキューブモデルでは、各nサーバは、区間[0、1)において、SHA1ハッシュ関数を用いて、固有の160ビットのハッシュキーを取得する。(SHA1は、その衝突抵抗の暗号特性のために選択された。希望があれば、代わりに、ビット数が少ないものであっても、異なるハッシュ関数を用いることは簡単である。システムは、衝突耐性である必要があり、従って、これが発生する確率が小さいように、ビットの数は、システムのオブジェクト数のlogの少なくとも2倍であるべきである。また、既存のファイルに整合するファイルを作成できないように、即ち、与えられたyに対して、h(x)=h(y)となるようなxを生成することが簡単でないように、暗号化耐性であるべきである。十億のオブジェクトの場合、これは、約少なくとも60ビットである。1兆の場合、80ビットである。従って、160は、必要以上である。このハッシュキー(ノードID)は、区間中のサーバ“位置”を記述する。各サーバには、交信相手のリストが割り当てられ(交信相手は、そのサーバが存在を認識するサーバである)、これによって、サーバは直接通信を行う。
【0036】
図2は、ハイパーキューブ200の9つの次元を示す。コンピュータネットワークトポロジの当業者は認識されるように、ハイパーキューブは、各ノード201が、ハイパーキューブの多数の各次元に沿って、他のノードに接続されたネットワーク化トポロジである。
【0037】
9つの次元を示す図2において、各ノード201は、9つの他のノードに接続され、それら9つの各ノードへの接続は、異なる次元に沿う。
【0038】
図2において、この図に示す9つの各次元を202に示す。3つを超える次元を2次元の紙面上に表現するのは困難であることから、次元0、1、及び2に関連する接続を、次元34及び5の接続より大きいノード間の間隔を有するように示し、また、これらの次元は、次元6、7、及び8に存在する交信相手間の間隔より大きい間隔を有するものとして示す。
【0039】
図2において、次元の分離がより簡単にできるようにするために、我々は、3つの最も小さい次元6、7、及び8によって定義されるキューブを比較的小さいものとして描き、中間次元3、4、及び5によって形成されたその図に示すキューブのキューブは、より大きく、また、最も大きい3つの次元0、1、及び2が、それより大きいキューブのキューブを定義する。
【0040】
図3は、図2のハイパーキューブの入り乱れていない図を提供する。図において、ハイパーキューブの各ノード201をその各次元に沿って接続するほとんどのラインを除去してあるため、個々のノード201は、見易くなり、また、より小さいキューブ304から成る中間サイズのキューブ304で構成されるキューブ306としてのハイパーキューブの表現を見ることができる。
【0041】
図4は、図3に示すハイパーキューブを表す同じ方法を用いるが、異なる点は、それが、このハイパーキューブの3つの異なる図を提供し、その次元の異なる部分集合を表すことである。点線400内に囲まれた図4の部分は、ハイパーキューブの最初の9つの次元を示す図3に示す部分に対応する。点線402内に示す図4の部分は、点線円400内の個々のノード201に見えるものの破断図である。この破断図は、ハイパーキューブのための次の9つの次元9乃至17を示す。図3及び図4に示す各小さい矩形302の各個々の角部は、実際には、ハイパーキューブ表現のより小さい次元によって定義されるキューブの階層に対応することを認識されたい。このより高次元のハイパーキューブにおける各実際のノードは、ハイパーキューブの全ての次元によって、他の任意のノード(このノードは、その与えられた次元によって表現されるビットの値だけそれから変わる)に接続されることを認識されたい。
【0042】
スカイリスネットワークの本実施形態において用いられる160ビットハッシュ値は、一兆掛ける一兆掛ける一兆を超える可能な値を表すのに充分な程大きい2進数を表す。従って、与えられたスカイリスネットワークが、多数のノードを有する場合でさえ、このような大きい2進数値によって定義し得る極めて小さい割合の可能な値だけが、実際に、それらに関連付けられたノードを有する。このため、160ビットハッシュ値が、ハイパーキューブとして表される場合、そのハイパーキューブは、ほとんど空である。このことは、図4によって示されるが、図4では、十億のノード等、大きい組のノードによって形成されるハイパーキューブは、ハッシュアドレス空間の9つの最上位ビットのみを見た場合、満杯に見える。これは、その図に示す階層型の立体表現において、点線400によって囲まれた図の部分に示す最も小さいキューブ302の1つの各角部は、このような各角部が全アドレス空間の1/512を表すことから、それらに関連する何らかの値を有する傾向があるためである。また、各角部では、幾つかのノードが総アドレス空間のその部分に入ることがほぼ確かなためである。
【0043】
最も小さい各矩形408の各角部が、ハッシュアドレス空間の1/262144を表す点線402によって囲まれた図4の部分に示すアドレス空間をもっと綿密に調べると、また、従って、約百万ノードのネットワークにおいてさえ、このような角部によって表現されたアドレス空間の部分は、図示するように点線404によって囲まれたハイパーキューブ空間の部分は、完全に満たされていないという事実によって示されるように、常に1つ又は複数の関連するノードを有するとは限らない。
【0044】
点線404によって囲まれた図4の部分は、図示するように、点線402によって囲まれたハイパーキューブ空間の図内において、円406によって囲まれたハイパーキューブ空間のその部分の破断図を示す。図示するように、点線404によって囲まれたハイパーキューブ空間の部分は、全ての可能なハッシュ値によって表現された160次元の空間の内、18番目乃至26番目の次元を表す。図4に示す例では、ハイパーキューブ空間のこの部分は、密度が低く、極めて希薄にまた不規則に見える。
【0045】
x及びyを2つのノードIDとし、また、SHA1を用いると仮定する。x=x・・・x159とし、この式で、xは、xのi番目のビットを表す。同様に、y=y・・・Y159とする。距離関数d(x,y)=2−f(x,y)について考えるが、この式で、
【0046】
【数1】

とすると、f(x,y)は、f(x,x)=0及びf(x,y)=k+1であるように定義する。直感的に、f(x,y)は、x及びyが異なる場合、第1上位ビットの位置である。
【0047】
基本的なハイパーキューブモデルでは、0<=i<lognの各iに対して、ノードIDがxであるサーバXを仮定すると、Xには、d(x,y)=2−iのノードIDがyである1つのランダムな交信相手Yが与えられる。
【0048】
従って、Xが、ノードIdが、次式のように制約されるlognの交信相手を有する(“−”は、制約がないことを示す)。
【0049】
【数2】

上式において、k=logn、
【0050】
【数3】

は、bの補数を示す。
【0051】
言い換えると、ランダム化されたハイパーキューブモデルでは、各ノードは、検索空間の他の半分、その半分の他の半分、その4分の一の他の半分等々において交信相手を有する。このことについて、図5に示すが、図5は、図3に示すハイパーキューブ表現と同じである。与えるノードXが、図5に示す位置500を有する場合、交信相手
【0052】
【数4】

は、点線502によって囲まれた図5の部分の或るランダムな位置にあり、交信相手
【0053】
【数5】

は、点線504によって囲まれた或るランダムな位置にあり、交信相手
【0054】
【数6】

は、点線506によって囲まれた或るランダムな位置にあり、この順序での次の交信相手は、点線508によって囲まれた或るランダムな位置にあり、その後の交信相手は、点線510内に位置し、更に、その後の交信相手は、点線512内に位置する。
【0055】
図6は、スカイリスネットワークのほとんどの実施形態でのハッシュアドレス空間の用途を表現し得る他の方法を示す。この表現では、2進数小数点は、160ビットハッシュ値の前に置かれ、そのビットは、0と、数1から一兆分の一の一兆分の一の一兆分の一未満だけ変化する数の範囲にある値を表す。
【0056】
図6において、この範囲の部分602は、拡張された形態で示す。アドレス空間の範囲のこの部分は、アドレス空間の約1/32768に対応する。それは、0.1000000000000010と0.1000000000000000との間のアドレス範囲の部分に対応する。そこでは、個々のノードは、小さい円604によって表される。この一部の範囲全体におけるノード分布は、かなりの量の統計的なばらつきを含むことが分かる。
【0057】
図6において、区域に対応するアドレス範囲の部分は、点線606によって示される。更に詳細に後述するように、与えられた区域に対応するハッシュアドレス空間の部分は、変化して、各区域は、ハッシュ値アドレス空間の異なる一部の部分におけるノード密度の統計的なばらつきにも拘らず、相対的に一定な密度を維持し得る。このことは、2つの区域606Aが、その図に示す他の区域におけるよりも更に小さいアドレス空間の部分を網羅するという事実によって図6に示す。図示するように、これは、アドレスの空間それらの部分が、より高い密度のノードを有するためである。
【0058】
従って、ノードは、指数関数的に増加する密度で一組の直接交信相手を、それに近づくにつれて、有する。従って、拡張されるであろう基本的なハイパーキューブモデルは、極めて、コードプロジェクトの経路設定モデルに匹敵し、「ノード当たり交信相手がlognで照合時間O(logn)」という同じ結果を実現する。しかしながら、この点で、我々は、区域を用いているため、既に耐故障性であり、コード及び他のスケール変更可能なシステムは、そうではない。
【0059】
更に、各局所的な区域(或る小さいmに対して、同じ最初のmビットを共有する約n/2ノードの組)は、それ内の全ノードを追跡する。従って、一旦、検索者が局所的な区域のノードと交信すると、そのノードは、最終的な送信先を知り、それを直接転送し得る。もちろん、区域の各ノードは、同じ索引情報のコピーを維持するため、ほとんどの検索は、所望のノードアドレス又はハッシュ値と同じ区域内の任意のノードに到達するより更に検索を進める必要はない。
【0060】
このモデルは、サーバが、任意の与えられたハッシュ値に最も近いノードを、そのノードに対してその最も近い交信相手へそのメッセージを受け渡すことによって見つけ得るという特性を有する。xが、y及びd(x,y)=2−iを見つけようと試みる場合、xは、d(z,y)≦2−(i+1)である交信相手zを有する。確率2−jでf(z,y)=i+j、従って、E[f(z,y)]=i+1.5を得る。従って、シーク時間は、せいぜいlog(n−m+1)であり、平均シーク時間は、[log(n−m+1)]/2である。
【0061】
ハイパーキューブネットワークの様々な他の経路設定プロトコルが存在し、また、我々のランダム化された区域ネットワークにそのまま適合し得ることにも留意されたい。これらのプロトコルによって、より良い負荷均衡化が高コストで可能である。
【0062】
しかしながら、この基本モデルは、幾つかの問題を有する。検索所要時間O(logn)は、ユーザが待つのをいとわない時間をすぐに超過する。更に、経路設定テーブルは、依然として、やや脆弱であり、従って、我々は、ノード又はリンクが消滅した時、ネットワークが分断することを防止しなければならない。区域経路設定は、極めて堅固であるが、この段階のハイパーキューブは、信頼性が低い。
【0063】
従って、我々は、次の解法を提案する。この解法は、平均(logn)/(d+1)の検索時間、及び最大(logn)/dを実現するが、これらの式において、dは、約7の定数であり、経路設定テーブルは、2d−1lognの交信相手を含むように拡張されている。各クライアントは、dレベルの交信相手の索引を構築するが、ここで、d番目のレベルの交信相手は、(直接交信による接続系統によって定義される)そのノードへの長さdの経路を有する交信相手である。しかしながら、このことを全接続で行うことは、極端に無駄が多い。従って、我々は、或る交信相手のみを交換する。即ち、d(x,y)=2−iであれば、yは、xにその最も近いレベルの交信相手を与え、この場合、d(x,z)=2−i、2−i−d≦d(y,z)≦2−i−1、d(z,z)≧2−i−dである。
【0064】
言い換えると、yは、それが正当な権限を持ったその交信相手zの間隔で見え、それを長さ2−i−d+1の間隔に分割し、また、1つの交信相手を各間隔からxに受け渡すが、xは、2レベル離れた交信相手である。これを継続的に繰り返し、次のようになる。即ち、x=x・・・x159は、b・・・bd−2の全2d−1の値に対して、次の交信相手を有し、
【0065】
【数7】

合計約2d−1lognの交信相手となる。
【0066】
図7は、図6で用いたのと同じように直線的にハッシュアドレス空間を表す。それは、ノード700を示し、また、直接交信相手702A乃至702Dを有する。実際、それは、それに更に近い他の直接交信相手を含むが、図7にそれらを描くのは、それらがノード700に近いため困難である。図7に示す直接交信相手702a乃至702D等の各直接交信相手は、対応するリストの間接交信相手704をノード700に供給する。各直接交信相手によって返された間接交信相手は、直接交信相手がランダムに選択されたハッシュアドレス空間の一部内にある。また、間接交信相手が、最上位ビット直後にあるD−1ビットの組用の全ての値を有し、これによって、直接交信相手は、交信相手が供給されつつあるノード700と最初に異なることから、与えられた直接交信相手によって供給される間接交信相手は、それらの対応する直接交信相手に関連するアドレス空間の一部範囲において、実質的に均一に分散される。
【0067】
この図では、数字800によって示されるビット行は、ノードyによって一組の交信相手が供給されるノードxのビットパターンとして定義される。行802は、ノードyのアドレス値のビットを示す。図から分かるように、yのアドレスの最初の2ビットは、xのアドレスと同じであるが、yの3番目のビット、x2バーは、xの内、x2である反転した他の3番目のビットである。図8に示すように、ノードxは、yがxと異なる分の第1ビットまでy自体が有するのと同じビットをそれらのハッシュアドレスに有する一組の間接交信相手をノードyから望む。本例では、それは、yから一組の64のこのような交信相手を望み、これらは、ビットd1乃至d6に対する全ての可能な値を有する。
【0068】
図8は、与えられた直接交信相手によって返されるその組の間接交信相手の性質を更に詳細に示す。
【0069】
図8において、テーブル804は、一部のyの交信相手リストを示すが、これは、その直接及び間接交信相手双方のリストである。このテーブルでは、値b0乃至b6は、それらが占有するハッシュアドレス空間の上位ビットに対する一組の全ての可能な値を表す。図8において行R3乃至R8を調べることによって分かるように、yが完全に編成された交信相手リストを有する場合、それは、それがxの要求を満たす必要がある全ての交信相手を含むべきである。行R4は、バーx3‘よりむしろx3’を有するものを除いて、xによってシークされる全ての交信相手を有する。R5は、バーx4‘よりむしろx4’を有するものを除いて、R−4に含まれない要求された交信相手の全てを有する。R−6は、バーx5‘よりもむしろx5’を有するものを除いて、R4及びR5に含まれない要求された交信相手全てを有する。R7は、バーx6‘よりもむしろx6’を有するものを除いて、R4乃至R−6に含まれない要求された交信相手全てを有する。R8は、バーx7‘よりもむしろx7’を有するものを除いて、R4乃至R7に含まれない要求された交信相手全てを有する。ほとんどの場合、直接交信相手は、それが、ノード要求側交信相手にそれが必要とする全ての交信相手を供給し得る行R4乃至R8等の充分な行を有する。
【0070】
このグラフでは、ノードXは、レベルiにおいて、
【0071】
【数8】

の交信相手を有することが分かる。いずれのノードも故障しない場合、経路長は、(logn)/dによって束縛され、平均経路は、長さ(logn)/(d+l)を有し、また、交信相手を維持するために送られたホスト当たりのネットワークトラフィック量は、O(logn)である。
【0072】
従って、我々が交信相手をキャッシュ処理する方法は、それを以前の経路設定メカニズムと区別する数多くのすばらしい特性を有する。特に、それは、局所性を保持し、また強化する。それは、最新の経路設定テーブルを維持する(ノードは、そのd番目のレベルの交信相手が、少し前生きていたことを知るが、これは、不活性化後、交信相手が連続的な層で置換されるためである)。また、その性能の恩恵は、高く、一定割合の更なる動作を要求する。更に、(送られたビット数として計数される)帯域幅が大きくなるが、ノードは依然としてそれらの直接送信相手と、様々な時間間隔で交信して更なる情報を交換するだけであるため、メッセージの数は、同じである。このことによって、単純なping/ack方式は、この方式がより良い情報を送るだけでなく、それを同じ数のメッセージで、恐らく同じ数のパケットで、また、従って、同じ量のネットワークトラフィックでさえ送ることから、無駄が多いことが分かる。
【0073】
一旦このネットワークが構築されると、維持するのは比較的簡単である。ノードが故障した場合、それを直接又は間接交信相手として用いるノードは、ネットワークの残りの部分に達するのに充分な他の交信相手を有する。ノードが付加された場合、それは、その交信相手のリストを構築するための適切に配置されたノードを見つけ得る。実際、我々の待ち行列時間ベースのシミュレーションによって、このことが確証されている。
【0074】
では、ノードが一度に1つずつ到着する一方で、オンラインアルゴリズムを用いて、このネットワークを如何にして構築し始めるかという疑問が残る。
【0075】
まず、我々のハードウェア上で動作する可能性のあるオラクル(oracle)又はホストキャッシュとして単一ノードを指定する(しかしながら、更に詳細に後述するように、これは任意の既知のノードであってよい)。オラクルは、ネットワーク上に登録された現サーバ全ての基数検索木又は他の最適化されたデータ構造を維持し、最も近いノード問い合わせに応える。新しいノードがネットワークに付加される度に、ノードは、オラクルにそのノードID及び所望される交信相手の位置のリストを送る。次に、オラクルは、ノードを検索木に挿入し、最整合のノードIDを送り返す。
【0076】
しかしながら、これらの交信相手が所定の位置に残された場合、構築されるネットワークは、上述したランダム化されたネットワークと同じではない。従って、我々は、ノードに新しい交信相手を頻繁に付加するように要求する。このことを行う1つの方法は、ホストキャッシュに依拠する。即ち、j番目のノードが挿入されると、オラクルも更新された交信相手のリストをノード
【0077】
【数9】

に送る。このように、各ノードは、更新された交信相手のリストを、ほぼネットワークのサイズが2倍になる度に得る。オラクルは、このプロセスを、そのノード記憶装置が交信相手で満杯になるまで、繰り返す。この段階で、オラクルは、ランダムにノード交信相手情報の削減を開始し、それを到着する最新のノードのそれで置き換え始め、また、ネットワークの検索を実行して、連続的にどのノードが依然生きているかを見つける。この時点で、ネットワークは、そのサイズがそれほど急激に2倍にならないため、もっと安定する。こうして、我々は、交信相手を更新するという重荷をノード自体に置くことができる。各ノードは、時々検索して、それらの交信相手を更新することができる。このようにして、我々は、ほとんどノードが存在しない初めの状態でも、理想的なグラフに近い接続されたネットワークを維持する。
【0078】
索引付け
索引を維持したり、それにアクセスしたりすることは、現分散型ネットワークの困難な側面である。索引は、利用可能性を高くし、待ち時間を短くし得る形態のものでなければならない。更に、索引は、利用可能性を高くでき、負荷均衡化されなければならない。
【0079】
索引が全ノードに氾濫することは、単純な可能性である。USENETは、その最も純粋な形態でこのことを行い、他方、サマリキャッシュ(Summary_Cache)及びオーシャンストアは、ブルーム(Bloom)フィルタを用いる。ブルームフィルタは、索引を構築するための記憶要件を削減するが、一定の割合分だけである。即ち、それらは、依然としてO(n)空間を要求するが、ここで、nは、索引中の項目数である。
【0080】
氾濫の他の形態は、マルチキャストであり、これは、各サーバが、何らかの少ない一定回数だけ、たとえ一回でも完璧な信頼性で、各情報を受信するように最適化し得る。
【0081】
また、他の氾濫による解決法も存在する。グヌーテラは、恐らく、索引を構築しないが、代わりに全てのノードへの検索を氾濫させる最良の既知のネットワークである。ある意味では、グヌーテラは、索引を氾濫させ、また、検索を局所的に維持するUSENETの双対である。
【0082】
スカイリスモデルは、非常に単純である。即ち、我々は、索引を既存の経路設定インフラ内に組み込む。我々は、局所的な情報のみを用いて、高い利用可能性、短い待ち時間、及び負荷均衡化を可能にする経路設定インフラを既に有しており、従って、同じシステムを用いて索引付けを行うのは自然なことである。従って、我々は、全地球的に知られたドキュメントから区域への1対1のマップを作成する。我々は、ドキュメントの160−ビットSHA1固有ID(UID)の最初のlognビットによって与えられる区域を取り上げることによって、このことをなし得る。
【0083】
経路設定に関するアクセス問題を解くと、我々には、維持の問題が残される。今となっては、我々は、経路設定プロトコルを用いて、どの区域がファイルを索引付けするか決定し得るので、我々は、区域に索引を構築させる。区域は、小さいため、索引のこの部分は、小さく、我々には、より単純で既知の問題が残る。
【0084】
ノード挿入
新しいノードは、到着すると、ネットワーク中の与えられた区域に挿入されねばならない。1つの可能な戦略は、全ての可能な区域を調べ、どれが最も空いているかを決定し、そして、ノードをその区域に挿入することである。しかしながら、この戦略は、明らかに経費がかかり過ぎる。区域は、厳密に均衡化される必要がなく、充分近ければ充分良い可能性があることに留意されたい。天秤の他端は、ランダムハッシングであり、これは、情報を必要としないが、負荷の局所的な偏差をもたらす。
【0085】
我々の方法は、大抵dは2に等しいが、最良のdの照合を用いることである。我々は、そのノード用に生成された公開キーのSHA1ハッシュと、ノードのIPアドレスとに基づき、新しいノード用の2つのハッシュ値を生成する。次に、我々は、ハッシュ値によって参照される両区域のポーリングを行い、どちらが最も容量が低いかを決定し、そして、その区域に参加する。それらが双方共等しい場合、我々は、2つのいずれかをランダムに選択し得る。
【0086】
(区域が単純なランダムハッシングにおいてより更に良く均衡化されている)この構成の良い特性を保持するために、我々は、区域N1においてノードが消滅する度に、選択して、ランダムに他の区域N2を選択し、また、N2がN1より大きな能力を有する場合、N2のノードをN1に再度割り当て得る。
【0087】
接続性マネージャ
我々のシステムは、グヌーテラ及びフリーネットが行うのと同じ方法で接続性の原理にアプローチする。各サーバは、経路設定構成によって定義される可変数の交信相手を有し得る。時々(例えば、c=10秒等、固定された時間区間で)、一方のホストが他方のホストにピン(ping)を発し、他方のホストが応答する。接続は、単方向又は双方向のいずれでもよい。従って、我々は、グラフを考慮し得るが、この場合、各サーバは、ノードであり、端部は、接続部を表す。
【0088】
各サーバは、少なくともdレベルのキャッシュ処理を行うため、各サーバは、グラフ距離d内における全てのサーバを知り、また、それは、距離i<dにある全てのサーバが、ic秒内では、生きていたことを知る。
【0089】
サーバの第1レベル交信相手が故障した場合、サーバは、新しい第1レベル交信相手に切り替わらなければならず、また、その木の交信相手の中で、この交信相手を超えた全ての2d−1交信相手を切り替えなければならない。dが大き過ぎる場合、このことは、時間の浪費である。従って、我々は、dが約7であると推定する。
【0090】
更に、大幅に異なる帯域幅(例えば、モデム速度及び広帯域)が存在する場合、広帯域ユーザのdが大きく、モデムのdが小さいことは有用である。このことによって、広帯域ユーザが有する交信相手の数を増やす必要があり、例えば、d=nの広帯域ユーザは、通常、d=n−1のモデムユーザを処理し得るが、交信相手がd=n−2のモデムユーザである場合、広帯域ユーザは、要求された情報の半分しか得ることができず、従って、他のモデムユーザを必要とする。広帯域ユーザのトラフィックは、交信相手のレベルのその後の各減少に対して2倍に増える。このことは、更に、広帯域ユーザがそれらの交信相手として他の広帯域ユーザを選択するように距離関数を偏らせることによって、矯正し得る。このモデルが与えられると、モデム(又は無線)ユーザは、それらのdを大幅に低減し、それら自身をネットワーク端に限定し得る。
【0091】
更に、ノードは、僅かにdレベルを越えて、冗長バックアップ第1レベル交信相手を保持する。更に、ノードの交信相手が故障した場合、ノードの第2又は第3レベル交信相手は、(我々がネットワーク分断又は何らかの同様な互いに関係するイベントを有さない場合)必ずしも同様に故障しているとは限らない。従って、ノードは、その古い交信相手を徐々に段階的に撤廃し、新しい交信相手を段階的に導入することによって、大きいdをトレードオフし得る。
【0092】
我々は、ノードが、その古い交信相手を全て一掃することを意図するものではなく、むしろ、それらをディスクに保存することを意図する。このことの主な理由は、ネットワーク分断を回避することである。即ち、スカイリスネットワーク経路設定及び索引付けは、耐故障性であり、大部分のノードが突然消失した場合でさえ生き残り、従って、ネットワーク分断が生じた場合、スカイリスシステムもまた分断されるであろう。このことから、敵対するネットワークリンクが再度活性化された場合、それら2つの分離したネットワークは、再結合しなければならない。区域は、小さい管理可能なネットワークであるため、このことは、ベクトル時間(標準の分散型システム方法)を用いて達成でき、また、ブルームフィルタを用いて索引を併合することによって加速し得る。
【0093】
ホットスポット管理
スカイリスシステムが人気のあるコンテンツの問題に対応しない場合、小数のホストが全てのトラフィックにサービスを提供するという窮地に立たされる。
【0094】
ホットスポット問題に対する我々の最大の攻勢は、索引付けをダウンロードから分離することである。従って、1つの区域は、ファイルの索引付けを担当し、また、そのファイルをダウンロードする区域は、そのファイルを他の区域と共有することを担当する。従って、区域が2進数ファイルを記憶する代わりに、我々は、それらのファイルを有するホストのリストをそれらに記憶させる。このことによって、提供されるバイトよりもむしろ、要求の量に比例する数に重荷が低減される。
【0095】
しかしながら、チェックされない状態で残された場合、或るコンテンツは、人気があるため、依然としてその索引は過負荷を受ける。スラッシュドット効果は、人気のあるニュースサイトスラッシュドットが、より下位のウェブサーバ上の記事へリンクする時生じるが、このような振舞いの最初の良く知られたドキュメント化インスタンスの1つであった。
【0096】
従って、我々は、数多くの氾濫式ネットワークからアイデアを拝借し、要求元ノードにより近く情報を運ぶ方法を設計する。全てのノードは、全てのノードに近いため、一般的に、このことは問題ではない。しかしながら、この場合、情報を“より近くに”運ぶということには、区域のサイズが大きくなるという副作用がある。従って、我々は、グラフの交信相手を逆にして、幾つかの近隣の区域も含むように情報を索引付けするノードの組を大きくできる。即ち、我々は、我々の利点として、経路設定方式における仲介ノードを用いる。メンバがc個の区域からそれらのm2内部リンクに短いリストを事前に一斉送信でき、その結果、区域は拡張してそのニーズにサービスを提供する。
【0097】
多キーワード検索層
我々は、単一キーワード検索を有するため、2キーワード検索の明らかな方法は、双方の区域と交信し、双方のリストを要求し、それらを併合することである。我々がリストを(UID又は人気のいずれかによって)ソートし得る場合、併合には、リストのサイズにおいて、O(n)時間がかかる。他の素朴な方法は、ワード対を含むリストを記憶することである。しかしながら、これには、O(n)の記憶空間が必要であるが、我々には、この空間がない。従って、我々は、共通のワード対に対する結果をキャッシュ処理すべきであるが、ほとんどの多キーワード検索は、新しいことが分かる場合がある。
【0098】
しかしながら、我々の帯域幅不足環境では、我々は、より良い解決法を有さなければならない。例えば、キーワード“旅行”及び“ナップスタ”が各々百万ヒットを有し、また、それらの共通部分がとても小さい場合、各UIDが20バイト長であると、トップ1000のヒットに対する単一の検索は、未ソートリストの場合、20メガバイトのネットワークトラフィックを要するか、あるいは、ソートされたリストの場合、恐らく約1メガバイトを要する。これは、単一の検索のために転送するには、途方もなく大きな量である。
【0099】
これを解決するために、我々は、幾つかの最も効率的な氾濫式ネットワークから1つの方法を拝借し、また、ブルームフィルタを用いる。各ホストは、その索引のための可変サイズのブルームフィルタを保持し(これは、ディスクから再計算するのは経費がかかるためである)、併合するために、そのリストの代わりに、そのブルームフィルタのみを送る。第2のホストは、ブルームフィルタ上で論理ANDを用い、そして、そのリスト全体を見て、ブルームフィルタにあるトップの合致結果を見つける。最後に、ブルームフィルタは、まことしやかで見せかけのヒットを生じるため、第2サーバは、トップ1000(1+ε)の合致結果を第1ホストに送り返し、そして、第1ホストは、そのリストと付き合わせて、それらをダブルチェックする。これには、トップ1000のヒットに対して20キロバイトのデータが必要である。我々が、許された検索結果の数を減らすと、その数が減少する。我々は、ブルームフィルタサイズが、約n乃至2nバイトのオーダであり、リスト送信時、約90パーセントが節約されると予想する。従って、2キーワード検索のために用いる総ネットワーク帯域幅は、恐らく200キロバイトに低減される。これは、依然として、我々が望むより大きいが、数メガバイトよりもずっと良い。
【0100】
シミュレーション
我々は、耐故障性を測定するための更にもっと複雑なシミュレータと同様、スケール変更可能性のための単純なシミュレータを構築した。耐故障性シミュレータは、実際に、局所的な索引付けを除く、全経路設定プロトコルを実現する。それは、ネットワーク又は一連のイベントをシミュレートする標準の方法である待ち行列時間に基づくが、このシミュレータは、時間毎に記憶される地球規模のイベント優先順位行列を含む。新しいイベントは、近い将来の或る時点で発生するようにこの行列に置かれ、そして、各イベントが処理された後、早送りのタイミングを次のイベント時間に瞬時に合わせる。
【0101】
2区域でdレベルのキャッシュ処理を有するネットワークの場合、検索を行うためのホップ(1つのマシンから次のマシンへのメッセージ)の最大数は、
【0102】
【数10】

であり、平均は、約(logn)/(d+1)であることが理論的に分かることを思い起こされたい。コードは、d=1であるが同様な結果を実現し、また、その区域の不足によって、時間が約3つの更なるホップ分だけ増え、他方、フリーネット及びオーシャンストアは、一定の割合分悪くなることに留意されたい。従って、d=7に設定できると、我々には、約5倍の平均速度アップが与えられるが、これは、この設定値では極めて有意であり、極端な遅さと程良く速いシステム間の差である。
【0103】
スケール変更可能性のシミュレーションによって、理論に極めてよく一致する結果が明らかになり、また、他のO(logn)システムに対するスカイリスの利点が分かる。サイズ64(6400万のマシン)の百万区域の場合、スカイリスは、2.9ホップでその索引にメッセージを経路設定でき、他方、(ノードの信頼性が極めて高くない状態ではいずれにしてもこのような大規模なネットワーク上に存在し得ない)コードは、13.5ホップを要し、また、他のプロジェクトは不調である。64、000のホストのより小さいネットワークの場合でさえ、スカイリスの経路設定は、1.9ホップを要し、他方、コードは、8.5を要し、また、オーシャンストア及びフリーネットは、16ホップ近くを要する。
【0104】
耐故障性シミュレーションによって、ネットワークの耐故障性は、高いことが分かる。ネットワークの3つの特性によって、その耐故障性が高くなる。即ち、1番目に、各マシンは、その1次交信相手が故障した場合、最後の拠り所にする数多くの2次交信相手を有する。2番目に、これらの交信相手に関する情報は、可能な限り効率的な方法に近い方法で、極めて頻繁に伝えられる。最後に、全てのマシンが、経路設定構成において全てのマシンへの短い経路を有するため、ぶれの報いが小さい。
【0105】
アプリケーション
スカイリスの技術は、初めて、ユーザの装置上で動作する大規模な信頼性の高いネットワークサービスのためのプラットフォームの構築が可能である。このプラットフォームは、数多くのアプリケーションに用い得る信頼性の高い索引の有用な基本的運用を提供するが、これらアプリケーションの多くは、索引が分散型の性質であるため新しい。アプリケーションには、次のものが含まれる。
【0106】
分散型コンテンツ分布:スカイリスのプラットフォームによって、初めて、PCやノート型コンピュータ等のユーザ装置、又は、PDAや携帯電話等の無線装置の能力を用いて、大規模に信頼性の高いコンテンツ配信が可能である。スカイリスの歳入モデルは、帯域幅当たり又は単位モデル当たりでのコンテンツプロバイダへの課金が含まれる。従量料金制のような或るダウンロードを求める消費者への課金も可能である。
【0107】
ファイル共有:ファイル共有は、小グループの人々又は世界による映像、音声、及び他のドキュメントの共有を含む。それは、単純な形態のコンテンツ配信であり、この場合、コンテンツは、静的である。スカイリスは、キーワード検索でファイル共有をサポートする。
【0108】
分散型コンピュータ処理:スカイリスの分散型索引は、信頼性の高いハッシュテーブルとして機能し得るが、これは、分散型コンピュータ処理環境においてタスクをスケジュール化するのに有用な場合がある。
【0109】
分散型情報管理:分散型情報管理には、共同作業者間での対話及びドキュメントの共有のためのアプリケーションが含まれる。既存の解決法では、索引が、制限されたスケール変更可能性を有することから、スケール変更可能性が制限されてきた。しかしながら、スカイリスの分散型索引は、情報管理のためのスケール変更可能な分散型プラットフォームを提供し得る。
【0110】
分散型データベース:スカイリスの信頼性の高い区域によって、大規模な分散型データベースを構築し得る。データベースの主要な機能は、トランザクションにある。しかしながら、スカイリスのアーキテクチャは、2段階処理を用いたデータベースによる使用に適合でき、区域は、ハッシュ関数によるオブジェクトを担当する。
【0111】
コンテンツの階層構造:インターネット上のほとんどのコンテンツは、単一のドキュメントでなく、むしろ階層構造であり、これらは、通常、ファイルシステムのフォルダによってモデル化される。スカイリスシステムは、分散して階層構造に対応するように構成し得る。稚拙な方法は、単一の場所からのコンテンツに対応するために、階層における全てのコンテンツにルートのハッシュで印を付けることである。もっとスケール変更可能な方法は、オブジェクトの親のハッシュ値をオブジェクトに含むことである。
【0112】
セキュリティ:我々は、セキュアなハッシュを用いていることから、ユーザがダウンロードするコンテンツが索引のハッシュと合致することを確信するために、このハッシュに依拠することは簡単である。我々は、更に、例えば、64キロバイトの小さいサイズのブロックを分割し、そして、それらのハッシュを分割して、異なるホストから異なるブロックが送信された際、エラーに対して柔軟性のあるセキュアなハッシュを実現し得る。従って、問題は、索引付けされたデータを信頼し得るかどうかということになる。この問題を解決するために、我々は、公開キーインフラを用いることができ、そして、信頼できる第3者としてスカイリスを用い得る。システムは、公開キーでコンテンツの署名を行い、そして、暗号化されたコンテンツのハッシュで挿入し得る。
【0113】
ハイブリッドネットワーク:この分散型のインフラを構築した状態で、単一の集中型エンティティとして機能するもしくは何らかの単純なフェイルオーバ(failover)メカニズムで機能する又はそれら自体のスカイリス分散型のネットワークの動作さえ行うネットワークに幾つかの数のサーバを挿入するのは、簡単である。これらのサーバは、追加の能力を提供するために、地理的な位置特定サービスを提供するために、又は、コンテンツの索引等の他のサービスを動作させるために用い得る。任意のネットワーク化された資源は、ある程度信頼性が欠如しているが、それらは、通常のクライアントマシンより信頼性が高いと仮定し得る。
【0114】
コンピュータ処理資源:スカイリスのネットワークは、ユーザのPC上で走るプログラムから成ることから、たんぱく質フォールディング、又は従来スーパーコンピュータ上で走らせていた他の大きい並列コンピュータ処理等、コンピュータ処理的に集中するプロジェクトをネットワークに統合することが可能である。スカイリスの索引によって、コンピュータ処理的に集中するプログラムに利用可能な信頼性の高い分散型ハッシュテーブルプリミティブが可能になる。このようなプリミティブによって、コンピュータ処理ジョブのために、より良いジョブスケジューリング又は負荷均衡化が可能になる。
【0115】
トラフィック管理:分散型の地理的な又はネットワーク位置特定サービスは、ネットワーク上で構築したり、又は、様々な中央サーバからアクセスしたりできる。このサービスは、帯域幅を節約するために、どのクライアントからダウンロードするか選択する際、用い得る。
【0116】
ユーザの動機付け:もっと価値が付加されたタスクの場合、このような方式は、例えば、高価な品物の買い物の際のキャッシュバックのために実現し得るが、アプリケーションを動作中のユーザからスカイリスによって受信される価値は、現時点では、ユーザに対する直接支払いを検討するには小さ過ぎる。分散型システムに参加することに対してユーザに酬いる他のもっと効率的な方法には、ユーザによってリストから選択される宝くじやチャリティへの寄付が含まれる。チャリティへ寄付したり、あるいは、宝くじをひく団体もまた用い得る。
【0117】
結論
新しいアルゴリズムに基づくスカイリスの核心レベルのインフラは、全地球的にスケール変更可能であり、また、耐故障性が高いという両方である。これらの2つの特性は、他の分散型ネットワークには存在しない。これらのネットワークでは、ドメイン内経路設定プロトコルBGP等、スケール変更可能であるが耐故障性でない特性、又は、小規模でBGPより良好な経路設定を実現し得るMITでのRONプロジェクト等、耐故障性であるがスケール変更可能でない特性のいずれかを選択しなければならない。
【0118】
スカイリスのスケール変更可能性及び耐故障性によって、インフラは、従来不可能であった新しいアプリケーション、即ち、柔軟性のあるプリミティブに基づき、信頼性の低いデスクトップマシン上で動作する信頼性の高いネットワークサービス、分散型ディレクトリサービスを生成し得る。
【0119】
擬似コード実施形態
図9は、図1に示すスカイリスソフトウェア134と共に記憶されたデータ構造900を示す。
【0120】
このデータには、直接交信相手904のリスト、間接交信相手912のリスト、及び共有交信相手リスト918を含む交信相手リスト902が含まれる。直接交信相手リストは、UID、即ち、現ノードの各直接交信相手用のハッシュアドレス値、並びにそのネットワーク、即ち、IPアドレス908、及びその交信相手状態履歴910に関する情報を記憶する。交信相手状態履歴910は、最新の過去においてノードと交信するために何回試行がなされたかに関する情報を提供し、与えられた直接交信相手と交信しようとする試行が或る回数を超えて失敗した場合、現ノードは、その与えられた直接交信相手を新しい直接交信相手で置き換える必要があることを知る。
【0121】
間接交信相手リストは、各間接交信相手に対して、そのUID914及びそのネットワークアドレス916を含む。
【0122】
共有交信相手リストは、現ノードが直接交信相手である他のノードのリストであり、また、それには、このような他の各ノードに対して、他のノードが、図8に関して述べたようなプロセスで現ノードによって与えられた全ての現ノードの交信相手のリストが含まれる。後述するように、共有交信相手リストを用いると、ノードは、他のノードに対して、それが該他のノードに提供した任意の交信相手に関する更新情報を提供し得る。
【0123】
図9に示す共有区域データ922は、共通の区域に属する全てのノードによって共有されるデータを示す。このデータが複数のノードによって共有されるという事実によって、このような情報は、ノードが比較的高いレートで区域から出たり入ったりしても、欠落しないことを保証する傾向がある冗長性が提供される。
【0124】
共有区域データは、区域アドレスマスク924を含み、これには、現ノードの区域の全メンバによって共有される最上位ビットの組が含まれる。現ノードが、与えられたハッシュアドレスに関する要求を受信すると、また、そのハッシュアドレスの最上位ビットが、現ノードのアドレスマスクと合致すると、現ノードは、通常、要求に直接応答する。このことは、それが、その区域の全ての他のノードと同様、そのハッシュアドレスに関する全情報のコピーを有すべきためである。
【0125】
共有区域データは、未確認情報リスト926も含む。928に示すように、これは、現ノードを含む、区域の全ノードのUIDすなわちハッシュアドレスのリストであり、また、それは、このような各ハッシュアドレスと共に、そのノードから生じた最新の全未確認情報のリストを含む。933−934に示すように、それは、このような各未確認情報に対して、その発生時間及び未確認情報のコンテンツを示すタイムスタンプを含む。このような未確認情報は、区域のノードによって共通に索引付けされる全ての情報、並びに区域の運用に関係する他の通信情報を伝達するために用いられる。
【0126】
共有区域データは、ファイル等のデータオブジェクトを索引付けするために用い得る複数の各キーワードのためのキーワード登録リスト936を含む。このような各キーワード登録項目に対して、関連するファイル938のリストが記憶される。このリストには、各ファイルに対して、ファイルのハッシュ値940、ファイルの名前942、ファイルのサイズ944、(それがテキストファイル、音声ファイル、又は映像ファイルのいずれであるか等の)ファイルのタイプ946、他の記述的なテキストベースのメタデータ948、ファイル950のコピーを記憶するノード数、及びファイル952に関連する他のキーワードのリストが含まれる。また、キーワード登録項目は、キーワードに関連するファイルの順序良く並べられたリストであって、954で示すように、ファイルを記憶したノードの番号毎に順序良く並べられたリストを記憶する。このことは、ネットワークにそれらが記憶される回数毎に示すように、キーワード登録項目によってどのファイルが最も人気があるか決定するのを支援するために用いられ、また、それらのファイルに索引付けするキーワードに選択の優先権を与えるために用いられる。
【0127】
共有区域データには、ファイル登録リスト956も含まれる。このリストは、1つ又は複数の各ファイル登録項目に対して、ハッシュ値958、ハッシュ値チャンクのリスト960、ファイルに関連するキーワードのリスト962、及びファイルを記憶しているノードのリスト964を含む。リスト964には、ファイルのコピーを記憶している各ノードに対して、ノードのIPアドレス966、そのノードのポート番号968、そのノード用のインターネット接続速度970、そのノードのネットワーク位置972が記憶される。ネットワーク位置972は、与えられた要求側ノードへのダウンロードに対して、どのコピーが最も適切であるか決定するように、ノード対の近接性を判断するために用いられる。ファイルのコピーを記憶している各ノードに対して、登録項目は、ノードがファイヤウォールの背後にあるかどうかの指標も含み、そうであれば、その中継交信相手情報974及び登録項目有効期日976も含む。登録項目有効期日976は、そのファイルの与えられたコピーの登録項目が、ファイルを記憶しているノードのリストから除去される時間であるが、これは、そのコピーがその位置で依然として利用可能であることを示すそのノードから更新メッセージが受信されない場合である。
【0128】
図9において978に示すように、与えられたノードが、共有ネットワークデータに関して上述したファイル964を記憶しているノードのリストにおいて参照されるタイプの与えられたファイルのコピーを記憶する場合、そのノードは、ファイルコピー登録項目のリスト980にそのコピーの登録項目を有する。このような各ファイルコピー登録項目は、ファイルのハッシュ値982、一組の各チャンクのハッシュ値のリスト、即ち、好適な実施形態では、各々約128キロバイト長であるファイルの下位部分、ファイル自体の実際のコンテンツ986、及び、ファイルに関連するキーワードのリスト988を含む。ファイルコピー登録項目は、ファイルに関連する他のテキストベースのメタデータ、及び、共有ネットワークデータのファイル登録項目における上述した登録項目有効期日976に対応する索引更新時間も含む。まず、与えられたノードにファイルが記憶され、ファイルがそのノード上で連続的に利用可能な時間が長くなるにつれてその更新時間が長くなる場合、この索引更新時間は、好適には、より短い時間の期間に設定される。図9に示す連続更新数994は、ファイルコピーが、現ノードからネットワークに連続的に利用可能な更新期間の数を示し、また、それは、索引更新時間をどれくらいの長さに設定すべきか決定する際に用いられる。上述したように、任意の関連するファイルコピーのための登録項目が、上述したそれらファイルのコピー964を記憶しているノードのリストから除去されるのを防止するように、各ノードは、索引更新時間毎に、その各ファイルに関連する登録項目有効期日976を更新すべきである。
【0129】
図10は、ノードが、スカイリスネットワークに如何にして参入するかを示し、初めてそれに参入する場合、又はネットワークを去った後それに再度参入する場合を示す。
【0130】
最初に、機能1002は、ネットワークにおける既知のノードとの交信を確立する。通常、既知のノードは、ネットワークに参入しようと試みているノードに与えられたノードリストに含まれる1つ又は複数のノードである。例えば、通常、ノードは、スカイリスソフトウェアをダウンロードした後、ネットワークに参入し、また通常、このようなソフトウェアには、機能1002のために呼び出し得る複数の既知のノードのリストが含まれる。幾つかの実施形態において、既知のノードは、システムに関連する1つ又は複数の中央サーバの1つであり、また、任意の与えられた時間において、少なくとも1つ又は2つのこのような既知のサーバが利用可能なほど充分に信頼性の高い中央サーバの1つである。他の実施形態において、新しいノードには、動的にURLをIPアドレスにマッピングするために提供されるサービスである動的名前分析を用いることによって、実際の現ノードにマッピングされるネットワーク名が与えられる。このサービスは、様々なサービスプロバイダから有料でインターネット上で利用可能である。
【0131】
一旦、現ノードが、スカイリスネットワークにおける既知のノードとの交信を確立すると、機能1004は、複数の新しいネットワークハッシュアドレスを生成する。そして、機能1006は、このような新しい各ハッシュアドレスに対応するハッシュアドレス空間の部分を処理する区域のノードに対して、図11に関して後述するタイプのハッシュアドレス検索を機能10008に実行させる。
【0132】
機能1008によって実行されるハッシュアドレス検索は、各ノードに問い合わせるが、このノードは、そのノードの区域に関連する区域マスクのための潜在的な新しいハッシュアドレスの1つの区域に存在するものである。一旦このようなマスクが各潜在的なハッシュアドレスと共に返されると、機能1010は、その区域マスクにおいて最少の上位ビットを有する検索によって返された区域を選択する。通常、このことは、最小分布密度を有するアドレス空間の領域の区域に対応する。一旦この選択が行われると、機能1012は、選択された区域に対応するハッシュアドレスに現ノードを割り当てる。次に、機能1014は、機能1008の検索により選択された区域において交信されたノードから、図9に関して上述した共有区域データ922の完全なコピーをダウンロードする。これが一旦行われると、機能1016は、図12及び13に関して後述するように、ノードの新しいハッシュアドレス用の交信相手リストを作成する。
【0133】
図11は、ノードが、機能1008に関して上述したタイプのハッシュアドレス検索を如何にして実行するかについて述べる。
【0134】
図11に示すハッシュアドレス検索1100は、検索を実行するノードに関連する区域アドレスマスクが、検索されるハッシュアドレスの上位ビットと合致するかどうか調べて確認することによって、開始する。そうであれば、機能1102は、機能1104に、現ノードのUID及び区域マスク及びネットワークアドレスでの検索から戻らせる。このことが行われるのは、現ノードのアドレスマスクが検索されるハッシュアドレスの上位ビットと合致する場合、それは、ハッシュアドレスの検索を処理するのに必要な全ての共有区域情報のコピーを有すべきためである。
【0135】
1102の調査が満たされない場合、機能1106は、現ノードの交信相手リストを、機能1108によって実行される繰り返しのために、現交信相手リストにする。
【0136】
機能1108は、その繰り返しの1つが、検索アドレスの上位ビットに合致する区域マスク、その合致する区域マスクを有するノードのUID、及びそのノードのIPアドレスを含む他のノードから応答を得るまで繰り返しループを実行する。
【0137】
機能1108のループは、機能1110乃至1120を実行させる。機能1110は、検索要求がループ1108の繰り返しによって以前送られていない一組の1つ又は複数の交信相手が現交信相手リストにあるかどうか調べて確認する。1つ又は複数のこのようなまだ試されていない交信相手がある場合、機能1112は、検索されるアドレスに最大数の最上位ビットが合致するUID値を有するこのようなまだ試されていない交信相手のその1つに、ハッシュアドレスを検索するように検索要求を送る。
【0138】
ノードが、タイムアウト期間内に検索要求に対する応答を取得しない場合、機能1114及び1116は、繰り返しループ1108の最初で再び開始し、これによって、機能1112は、検索によって用いられている現交信相手リストの他の登録項目に検索要求を送る。
【0139】
機能1112によって送られた検索要求に応答して、返信が受信され、また、その返信が、合致する区域マスクを含まないが新しい交信相手リストを含む場合、機能1118及び1120は、新しい交信相手リストと現交信相手リストを併合する。検索要求が機能1112によって送られたノードが、現ノードより、検索されるハッシュアドレスに対してより近い場合、機能1120によって、検索の現交信相手リストに併合される交信相手リストは、検索の現交信相手リストに以前あったものより、検索されるハッシュアドレスにより近い一組の交信相手を含む可能性がある。
【0140】
通常、nがスカイリスネットワークのノード数に等しいとすると、機能1108の繰り返しループを通るlog(n)の繰り返しよりかなり少ない繰り返しの後、返信は、検索アドレスに合致する区域マスク並びにその合致するマスクを返すノードのUID及びIPアドレスを含む機能1112によって送られた検索要求の1つに応答して受信される。
【0141】
図12は、新しいノード用の交信相手リストを作成するために用いられる交信相手リスト作成機能1200について述べる。
【0142】
この機能には、0からkまでの範囲に渡る索引iの各可能な値に対して実行されるループ1202が含まれる。幾つかの実施形態において、kは、区域におけるノード数のlogである。この擬似コードに示すもの等の他の実施形態において、kは、交信相手リストが作成されつつあるノードの区域マスクの長さに等しい。
【0143】
ループ1202の各繰り返しに対して、機能1204は、機能1206乃至1210を実行することによって、新しいUID、即ち、ハッシュアドレス値を作成する。機能1206は、交信相手リストが作成されつつある現ノードから最初のi−1上位ビットをコピーする。次に、機能1208は、現ノードのUIDのi番目の最上位ビットを反転する。次に、機能1210は、作成される新しいハッシュ値においてi番目のビットより上位でない全ビットに対してランダム値を選択する。
【0144】
一旦この新しいUID値が作成されると、機能1212は、図13に示す新しい直接交信相手作成機能1300を呼び出す。
【0145】
図13に示すように、新しい直接交信相手作成機能は、機能1302乃至1320から構成される。1302における機能は、新しい直接交信相手作成機能が呼び出されたUIDに対して、図11に関して上述したタイプのハッシュアドレス検索を実行する。図11に関して上述したように、この機能は、検索されているUIDを処理する区域におけるノードを見つけるために検索を行う。一旦ハッシュアドレス検索がこのようなノードに関する情報を返すと、機能1304は、機能1302の検索によって返されたノードを、現ノード用のi番目の直接交信相手として作成するが、ここで、iは、最上位ビットの数に等しく、これによって、返された交信相手は、現ノードの新しいUIDと異なる。
【0146】
機能1306乃至1312は、新しい直接交信相手のためのUID、IPアドレス、及び初期的には空である交信相手状態履歴登録項目を記憶する。このことは、図9において各直接交信相手に対して記憶されるものとして示した情報906乃至910に対応する。
【0147】
一旦i番目の交信相手の登録項目が、現ノードのデータ構造において、それ用に作成されると、機能1314は、交信相手要求をi番目の交信相手に送って、i番目の交信相手と同じ最上位ビットからi番目のビットまでを有し、また、i番目のビットを含み、更に、d−1最上位ビットの全ての可能な組合せを有する間接交信相手を要求する。このことは、図8に関して上述した交信相手要求のタイプに対応する。直接交信相手が、要求された間接交信相手を返す場合、機能1316乃至1320は、このような各間接交信相手のUID及びIPアドレスを、現ノードデータ構造において、図9に関して上述した間接交信相手リスト912に記憶させる。
【0148】
図14は、図13に関して上述した機能1314を実行する際、ノードによって送られたタイプの交信相手要求を受信する時ノードが実行する交信相手要求応答機能1400である。
【0149】
交信相手要求応答機能が実行される時、機能1402は、全てのノード交信相手のリストを見つけるが、これら交信相手は、要求において識別された同じ最上位ビット乃至i番目のビットを有し、また、d−1の次の最上位ビットの全ての可能な組合せを有する。このことは、図8に関して上述した交信相手のリストと同様である。一旦このリストが作成されると、機能1404は、この交信相手のリストを要求元ノードに送る。次に、機能1404によって要求元ノードに送られた各交信相手ノードに対して、機能1406が実行される。要求元ノードに送られたこのような各交信相手ノードに対して、機能1406は、要求元ノードの下にあるノードの共有交信相手リストへの登録を機能1408に行わせて、それに送られた交信相手を記録する。図15及び16に関して後述するように、共有交信相手リスト登録項目は、その交信相手リストの交信相手がもはや有効でないことをそれが知った時、それが更新しなければならない他のノードがどれかについて、ノードが知ることができるように用いられる。
【0150】
図15は、直接交信相手状態更新機能1500について述べる。この機能は、機能1502を含むが、これは、現ノードの直接交信相手毎に、ループ1504をn秒ごとに実行する。1つの現実施形態において、nは、5秒に等しい。
【0151】
現ノードの直接交信相手毎に、機能1504は、機能1506乃至1526を実行させる。機能1506は、ループ1504の現繰り返しの現直接交信相手との通信を試みる。機能1506の試みに応答して通信が確立されない場合、機能1508は、機能1510乃至1526を実行させる。機能1510は、交信相手との通信が失敗したことを記録する。次に、機能1512は、これがn番目の連続した試みであって、その交信相手と試みた通信が失敗した試みであるかどうか調べて確認する。そうであれば、ノードは、もはや有効な直接交信相手でないと判断し、機能1514乃至1526を実行させる。本発明の他の実施形態において、直接交信相手がもはや有効でないといつ考えるべきかについて厳密に判断するために、異なる基準を用い得ることを認識されたい。
【0152】
機能1514乃至1518は、新しい直接交信相手によって用いられる新しいUIDを作成して、機能1512が無効であると判断したものを置き換える。この新しいUIDには、置換される直接交信相手と同じ最上位ビットから現ノードのUIDと異なる最初の最上位ビットまでが、それを含んで、含まれる。新しいUIDの残りのビットは、ランダムに選択される。
【0153】
一旦この新しいUIDが、作成されると、機能1520は、新しいUIDに対して、図13に関して上述した新しい直接交信相手作成機能1300を呼び出す。
【0154】
一旦、機能1300が、新しいUIDの最上位ビットと合致する区域マスクを有する区域の与えられたノードから新しい直接交信相手を見つけると、その与えられたノードを、失敗したことを機能1512が見つけた直接交信相手を置き換える新しい直接交信相手にする。また、機能1300は、ハッシュアドレス空間の新しい直接交信相手の部分に関連した対応する組の間接交信相手を取得する。機能1300は、この新しい直接交信相手及びその対応する間接交信相手に現ノード交信相手リストに登録させる。
【0155】
一旦このことが行われると、機能1522は、図9に関して上述した現ノードの共有交信相手リスト918において置換された交信相手用の登録項目を有する他の各ノードに対して、ループを実行する。置換される直接交信相手又はその関連する間接交信相手の1つを現ノードが以前送ったこのような各ノードに対して、機能1524は、交信相手変更メッセージを、置換される交信相手が置き換えられたことを示す他のそのノードに送り、UID及びIPアドレスによってそれを置き換えることになっている交信相手を識別する。機能1526は、次に、共有交信相手リストを更新して、新しい置換交信相手が、その置換に関してちょうど通知された他のそのノードに送られたことを反映する。
【0156】
図16は、ノードが、図15の機能1524に関して上述したタイプの交信相手変更メッセージを受信する時実行する交信相手変更メッセージ応答機能1600を示す。
【0157】
ノードが、このような交信相手変更メッセージ機能1602を受信する場合、それは、メッセージに示された置換された交信相手を、図9に関して上述したノードの交信相手リスト902におけるメッセージに示された新しい置換交信相手で置き換える。
【0158】
次に、機能1604は、現ノードの共有交信相手リストにおける置換された交信相手に関連する他の各ノード用のループを実行する。このような各ノードに対して、機能1606は、他のそのノードに交信相手変更メッセージを送り、置換された交信相手及びそれを置き換えようとしている交信相手のUID及びIPアドレスを示す。次に、機能1608は、現ノードの共有交信相手リストを更新して、それが、他のそのノードに新しい置き換え用の交信相手を送ったことを示す。
【0159】
図12乃至16から分かることは、スカイリスネットワークにおける動作によって、ノードが、比較的規模が大きい組の交信相手を創り出し得るということであり、ここで、これら更新相手の組は、大量のコンピュータ処理又は通信を必要とせずに、与えられたハッシュアドレス値を扱うことができるノードをもっと迅速に検索して見つけるために用い得る。これは、ノードが、通常、大多数のその交信相手を、単に他のノードからそれらをコピーすることによって取得し、また、他のノードによってそれに与えられた1つ又は複数のノードが故障していると分かった時、その交信相手リストを更新する情報を他のノードによって与えられるためである。これによって、システムは、壮大なアドレス空間を極めて迅速に検索できるようになり、しかも、そのことを可能にする多数の交信相手を維持するのに必要な通信及びコンピュータ処理のオーバーヘッドが比較的少ない。ネットワークが適切に及び効率的に交信相手の変更に関する情報を、それらに関して知る必要があるノードのみに中継するという事実によって、システムは、ほとんどのノードが比較的高い頻度で出たり入ったりするネットワークにおいてさえ、効率的に動作できる。
【0160】
図17及び18は、未確認情報通信に関するが、これは、スカイリスネットワークの、与えられた区域のノード間において情報を通信するための極めて効率的なメカニズム、即ち、論理ノードである。
【0161】
図17は、未確認情報作成機能1700を示す。与えられたノードの共有区域データに変更がある場合、機能1702は、機能1704乃至l708を実行させる。図25及び26に関して後述するように、このような変更は、通常、新しい情報が、与えられたノードにおいて索引付けされる時発生する。
【0162】
機能1704は、ノードの共有区域データにおける変更を詳述する新しい未確認情報を作成する。機能1706は、与えられたノードのUID、及びこの新しい未確認情報が作成された時間に対応するタイムスタンプで未確認情報にラベル付けする。次に、機能1708は、与えられたノード自体のUID下にある与えられたノードの未確認情報リストにこの未確認情報を配置する。
【0163】
図18は、未確認情報伝達機能1800について述べるが、これは、与えられた区域のノード間において未確認情報を通信するために用いられる。
【0164】
機能1802は、n秒毎にループを実行するが、これは、1つの実施形態では、5秒である。このループは、現ノードの未確認情報リストにおける各ノードに対して、内側ループ1804を形成する段階から構成される。このような各ノードに対して、機能1806乃至1830が、実行される。
【0165】
機能1806は、ループ1804の繰り返しにおいて、現ノードに関連する各未確認情報に対して、ループを実行するが、ループ1804では、その未確認情報が、与えられた時刻表より古いかどうかが調べて確認され、そうであれば、それは、機能1808にそれを削除させる。このことは、古い未確認情報をノードの未確認情報リストから除去して、そのリストが時間と共に無駄に大きくなるのを防止するように行われる。
【0166】
次に、機能1810は、ループ1804の現繰り返しの現ノードが、機能1800を実行している現ノードであるかどうか、また、現ノードの未確認情報リストにおいてそのUIDに関連する何らかの未確認情報であって、第2時刻表より新しい未確認情報があるかどうか調べて確認する。現ノードのUIDリストに現ノードに関連するこのような比較的最新の未確認情報がない場合、未確認情報伝達によって、現ノードが区域の一部として今でも機能していることを他のノードが通知されるように、機能1812は、現タイムスタンプを有する現ノードの未確認情報リストに“まだここにある”未確認情報を付加する。
【0167】
次に、機能1814は、ループ1804の現ノードが他のノードであり、また、他のそのノードは、第3時刻表より新しい現ノードの未確認情報リストにそのUIDに関連する未確認情報を有さないかどうか調べて確認する。これらの条件が合致した場合、これは、現ノードが、その他のノードは、現区域にもはや参加しておらず、また従って、機能1816が現ノードの未確認情報リストから他のそのノードを削除することを示すほど充分に長い期間の間、他のそのノードについて何も聞いていないことを意味する。
【0168】
一旦ループ1804の動作が完了すると、機能1818は、現ノードの未確認情報リストからランダムに抽出された他のノードとの通信を試みる。通信がランダムに抽出されたノードと実現されると、機能1820は、機能1822乃至1827を実行させる。
【0169】
機能1822は、通信の各側のノードUIDが、他方のノードの区域マスクと合致するかどうか調べて確認する。一方側の区域マスクが他方を含む場合、即ち、より小さい数の上位ビットを有する場合、より小さい数の上位ビットのノードは、他のノードのより長い区域マスクと合致するノードUIDと一致する未確認情報のみを交換する。より長い区域マスクのノードは、その未確認情報リストにあるノードUIDに関する全ての未確認情報をより短い区域マスクのノードに送る。これは、全てのこのようなノードのUIDは、他方のノードのより短い区域マスクに対応するハッシュアドレス空間の部分内に入るためである。通信中のノードの区域マスクにおけるいずれかのビットが、互いに競合する場合、いずれのノードも他のノードと如何なる未確認情報も通信しない。
【0170】
図19は、区域分割機能1900を示す。この機能は、現ノードの未確認情報リストにリスト化された区域数が上限区域数を超過するかどうか調べて確認する調査1902を含む。本発明の本実施形態において、ノードは、それらの区域を約32と64ノードとの間の密度範囲に保持しようと試みる。このような場合、上限区域数は、64である。機能1902の調査が満たされた場合、機能1904乃至1908が、実行される。
【0171】
機能1903は、現ノードの区域マスクの長さを1ビットだけ増やす。機能1904は、未確認情報を現ノードのUID下にあるノードの未確認情報リストに付加して、現ノードが、その区域マスクの長さを1ビットだけ拡張したことを示す。
【0172】
上述したように、未確認情報伝達によって、この未確認情報は、現ノードの区域にある他のノードに送り出される。現ノードが、その区域の密度が上限区域数を超過したことを検出するための最初のノードの1つである場合、その以前の区域におけるほとんどの他のノードは、機能1903の結果として、現ノードが有するものより短いアドレスマスクを有する。図18の未確認情報伝達機能に関して上述したように、より短い区域マスクを有するこのような他のノードは、現ノードから未確認情報を受信する。これは、その新しい区域マスクに対応するアドレス空間のその部分は、それらのより短いアドレスマスクによって表現されるアドレス空間の部分内に入るためである。このことによって、このような他のノードは、現ノードは、その区域を分割すると決めたというメッセージを受信する。しかし、現ノードの新しいより長いアドレスマスクと合致しないUIDを有するあらゆるこのようなノードは、もはや未確認情報を現ノードに送らない。これは、それが、それらの現区域のそれらの半分にもはや関心がないことをそれらが通知されたことによる。
【0173】
ノードが、機能1903によって示されるように、その区域の長さを増やす場合、マスク機能1906は、現ノードが全交信相手リストを含むかどうか調べて確認するが、この全交信相手リストには、直接交信相手と、対応する組の間接交信相手とが含まれ、後者においては、現ノードのアドレスと異なる第1最上位ビットが、現ノードのアドレスマスクにちょうど付加された新しいビットの位置に対応する。
【0174】
機能1906の調査によって、現ノードがこのような交信相手登録項目を有していないことが分かった場合、機能1908は、図13に関して上述した、新しい直接交信相手作成機能1300を呼び出し、このような直接交信相手及び対応する組の間接交信相手を作成する。
【0175】
図19に示さないが、機能1902に関して上述したように、ノードが、その区域は上限区域数を超過することを検出するが、更に、区域を分割すると、2つの半分の内一方は、下限区域数未満のアドレスを有するようになることを見つけた場合、それは、現区域のメンバにその他の半分におけるその区域に再参入させるメッセージを生成することによって応答するが、この応答は、区域をあまりにも大きくさせる一方でその半分の一方をあまりにも小さくさせる密度不均衡を補正するように行われる。
【0176】
図20は、区域分割未確認情報応答機能2000について述べる。機能2002によって示されるように、現ノードが、他のノードのUIDに関連する未確認情報を受信し、他のそのノードは、現ノードのUIDともはや合致しないようにその区域マスクを変更したことを示す場合、機能2004乃至2008が実行される。これらの機能は、他のノードの登録項目の指標を現ノードの未確認情報リストに配置し、他のノードは、他のノード変更を示す未確認情報に関連するタイムスタンプの時点で現ノードのネットワークを去ったことを示す。また、未確認情報通信は、新しい又は未確認情報が、他のそのノードから受信され、現ノードのUIDと合致する区域マスクをそれが有すると告げるまで、現ノードから他のそのノードへ行われるべきであることを示す。
【0177】
図21は、区域併合機能2100について述べる。ノードの未確認情報リストにおける区域数が下限区域数未満である場合、機能2102は、ループ2104を実行させる。ループ2104は、現ノードの区域マスクにおける区域マスクの1つ下位のビットによって定義されるハッシュ空間の一部の他の半分における1つ又は複数のランダムに抽出された各ハッシュアドレスに対して実行される。
【0178】
機能2106は、このようなランダムに抽出された各ハッシュアドレスに対して、ハッシュアドレス検索を実行する。機能2108は、ハッシュアドレス検索によって見つけられたノードが、現ノードより長い区域マスクを有するかどうか調べて確認する。そうである場合、機能21が実行される。
【0179】
機能2110は、検索によって返された他のノードにメッセージを送るべきかどうかを確率的に決定し、現ノードの区域マスクに対応するUIDでネットワークに再度参入するようにそれに要請する。このようなメッセージは、1/nの確率で送られるが、ここで、nは、ノード区域のサイズである。このようなメッセージを送るべきか否かに関するこのような確率的な決定は、極めて短い時間の間にこのようなメッセージを受信することから、多数のノードの全てにその可能性を提示するように用いられる。これは、このことによって、区域が過小密度でこのようなメッセージを受信することがあり得るためである。
【0180】
機能2208の調査が満たされない場合、組み合わせられるべき区域は、単に、それらのそれぞれの区域マスクを1ビットだけ短くすることによって組み合わせることができ、従って、機能2213は、機能2214乃至2222を実行させる。
【0181】
機能2216は、未確認情報通信を介して、現ノードの区域のノードに併合要求を送る。これによって、この未確認情報を受信する全てのノードは、自ら図22の併合要求応答機能を実行する。次に、機能2218は、現ノードにその区域マスクの長さを1ビットだけ短くさせる。機能2220は、現ノードの交信相手リストから、最初に最下位ビットだけ現ノードのハッシュアドレスと異なる直接交信相手、及びその関連する間接交信相手全てを削除する。次に、機能2220は、新しい区域の他の半分からのノードとのその次の未確認情報通信を現ノードに実行させ、こうして、現ノードは、併合が現ノードの半分によってではなく、新しく形成された区域の他の半分によって索引付けされるまで、全ての共有区域データを最後まで受信する。
【0182】
図23は、新しいファイルネットワーク登録機能2300を示す。この機能は、ノードによって実行されるが、これは、それが知る限り、以前ネットワークに参入したことがないファイルをスカイリスネットワークにそれが入れようとする場合に実行される。
【0183】
新しいファイルネットワーク登録機能は、参入されるファイルを1つ又は複数のチャンクに分割してしまう機能2302を含むが、各チャンクは、せいぜい与えられたサイズを有する。本発明の1つの実施形態において、ファイルチャンクは、128kBに制限される。次に、機能2304は、各チャンクにハッシュを実行する。次に、機能2306は、与えられたファイルに関連するチャンクのハッシュにファイルハッシュ値を設定する。
【0184】
このことが行われた後、機能2308は、ファイル関連付けられる1つ又は複数のキーワードのリストを見つける。異なる機能を用いて、異なるタイプのファイル用のキーワードを取得し得る。例えば、数多くの非テキストファイルは、それらのキーワードの根拠を大部分ファイルのタイトルに置いている。メタデータを含むファイルのキーワードは、このようなメタデータによって定義されることが多い。純粋なテキストファイルは、一般的に、ファイルで発生するよりテキストファイルにおいて相対的に極めて高い頻度で発生するファイル中における文字言語に対応するキーワードによって定義し得る。
【0185】
機能2308によって見つけられたこのような各キーワードに対して、機能2310及び2312は、その対応するハッシュ値を見つける。次に、機能2314は、図24に示すコピーファイルネットワーク登録機能2400を呼び出して、ファイルのネットワークへの登録を完成する。
【0186】
図24に示すように、コピーされたファイルネットワーク登録機能には、図24の機能が実行されているファイルに関連するハッシュ値に対するハッシュアドレス検索を形成する機能2402が含まれる。
【0187】
ハッシュアドレスが、ファイルハッシュ値に対応するハッシュアドレス空間の部分を処理するノードのアドレスを返す場合、機能2404は、現ノードIPアドレス2412と共に、そのノードにファイルに対するファイル索引挿入要求を送る。現ノードIPアドレス2412は、ハッシュアドレス検索によって返されたノードにキーワードハッシュ値に対するキーワード索引挿入要求を送るが、この要求は、現ノードIPアドレスと、現ファイルのファイル登録項目に含まれる他の情報と、を含む。次に、機能2406は、ファイル索引挿入要求に応答して返された現ファイルを記憶しているノードの数を記憶する。
【0188】
次に、機能2408は、現ファイルの各キーワードに対してループを実行する。このループには、キーワードのハッシュ値に対してハッシュアドレス検索を実行する機能2410が含まれ、機能2412は、ハッシュアドレス検索によって返されたノードにキーワードのハッシュ値に対するキーワード索引挿入要求を送る。この要求には、現ノードのIPアドレスと、ファイル索引挿入要求によって返された現ファイルを記憶しているノードの数を含むループ2408の現キーワードに関連するキーワード登録項目に対する情報と、が含まれる。
【0189】
次に、機能2414は、コピーされたファイルネットワーク登録機能が実行されているファイルのハッシュ値と共に現ノード上に、数字2416乃至2424によって示す情報の項目を記憶させる。これには、現ファイルの関連チャンクのハッシュ値のリスト、ファイル自体のデータ、ファイル及びそれらのハッシュ値に関連するキーワードのリスト、ゼロに設定された索引更新番号、及び初期的には短い更新長で設定された索引更新時間が含まれる。この更新長は時間を示し、この時間毎に、現ノードは、現ノード上に記憶されたファイルのコピーに対してネットワークによって作成される索引付けされたファイル登録項目を更新しなければならない。
【0190】
図25は、ファイル索引挿入要求応答機能2500を示す。これは、図24に関して上述した機能2404によって送られるタイプのファイル索引挿入要求を受信するノードによって実行される機能である。
【0191】
ノードがこのようなファイル索引挿入要求を受信すると、機能2502は、現ノード上に要求されたファイルに対する何らかのファイル登録項目があるかどうか調べて確認する。ない場合、機能2504及び2506が実行される。機能2504は、要求生成ノードに関する情報を含むファイルに対するファイル登録項目を作成する。このことは、図9に関して上述したファイル登録データ956に対応する。機能2506は、新しいファイル登録項目を含む現タイムスタンプを有するノード自体のUID下にあるノードの未確認情報リストに未確認情報を配置する。このことは、図17に関して上述した未確認情報作成に対応する。
【0192】
機能2502の調査が、応答される要求のファイルに対するファイル登録項目が既に存在することを見つけた場合、機能2508は、機能2510及び2512を実行させる。機能2510は、現ファイルに対するファイルコピー登録項目のリストに新しいファイルコピー登録項目を付加して、応答されている要求が送られたノードに対するネットワーク位置情報を示す。次に、機能2512は、現タイムスタンプが新しいファイルコピー登録項目情報を含む状態で、ノード自体のUID下にあるリストの現ノードに未確認情報を配置する。また、このことは、図17に関して上述したタイプの未確認情報作成に対応する。
【0193】
ファイル索引挿入応答要求の仕事が終わると、機能2514は、要求元ノードに情報を返し、要求に対応するファイルに対するファイルコピー登録項目の数を示す。
【0194】
図26は、キーワード索引挿入要求応答について述べる。このことは、ある程度図25において説明した応答機能と同様であるが、例外は、それが、ファイル索引情報よりもむしろキーワード索引情報を挿入するという要求に対するノードの応答について記述することである。
【0195】
ノードが、図24に関して上述した機能2412によって生成されるタイプのキーワード索引挿入要求を受信すると、機能2602は、現ノード上の要求に関連するキーワードに対して既に何らかのキーワード登録項目があるかどうか調べて確認する。ない場合、機能2604は、現キーワードに対して図9に関して上述したキーワード登録リスト936に関して上述したタイプのキーワード登録項目を作成する。
【0196】
一方、現キーワードに対する登録項目が既に存在する場合、機能2606は、キーワード要求に伴うファイルを記憶しているノードの数が、要求された最小の数を超えるかどうか調べて確認する。本実施形態において、キーワード登録項目のみが、そのキーワードに関連する5000の最も頻繁に記憶されるファイルに関する情報を記憶する。他の実施形態において、異なる要件を用いて、どのファイルが与えられたキーワードと共に索引付けされかを決定し得る。
【0197】
機能2606の調査が合格すると、機能2608乃至2616が実行される。機能2608は、そのキーワードに対する現ノード上のキーワード登録項目における現キーワードに関連するファイルに対する何らかの関連ファイル登録項目があるかどうか調べて確認する。そうであれば、機能2610は、関連するファイルのリストの現キーワード登録項目に現要求に関連するファイルに対する新しい関連ファイル登録項目を作成する。
【0198】
機能2608の調査が、要求されたファイルに対する関連ファイル登録項目が現キーワードのキーワード登録項目にあることを見つけた場合、機能2612は、機能2614及び2616を実行させる。機能2614は、ファイルを記憶しているノードの数を現キーワード索引挿入要求に含まれた数に置き換え、機能2616は、図9に示す記憶数954毎に順序良く並べられたファイルのリストにおけるファイルの位置を再度並べる。これは、与えられたファイルに関連するコピーの数が、現キーワードに関連する任意のファイルに対するトップ5000の最大数のコピー内に入るかどうか決定するために調査2606によって用いられるリストである。
【0199】
キーワード索引挿入要求応答機能が完了する前に、機能2618は、現タイムスタンプが、キーワード索引挿入要求に対する応答に起因したキーワード登録項目へのあらゆる変更を含んだ状態で、ノード自体のUID下にある現ノードの未確認情報リストに未確認情報を配置する。また、このことは、図17に関して上述したタイプの未確認情報作成に対応する。
【0200】
図27乃至29は、ネットワークによって用いられて、ネットワーク分散型索引によって索引付けされる情報が現在有効である機会を増やす機能を示す。
【0201】
図27は、ファイル期限切れ応答機能2700を示す。この機能には、ファイルのコピーを記憶しているノードのリストのノード記憶ファイル登録項目に対する有効期日が満了したかどうか調べて確認するための調査2702が含まれる。そうであれば、機能2704乃至2714が実行される。機能2704は、図9に示すリスト964と共に上述したタイプのノード記憶ファイル登録項目を削除する。次に、機能2706は、ファイルを記憶しているノードのリストが、削除によって空になったかどうか調べて確認する。そうであれば、機能2708乃至2714を実行する。機能2708は、ファイル登録項目に関連する各キーワードに対するループを形成する。このループは、キーワードのハッシュに対するハッシュアドレス検索を実行する機能2710と、キーワード検索によって返されたノードにメッセージを送り、そのノード上のキーワード関連登録項目の関連するファイルリストからファイルを除去するようにそれに通知する機能2712とから構成される。次に、機能2704は、関連するファイル登録項目を削除することによって機能2706により検出される状況に応答する。
【0202】
図28は、与えられたファイルのコピーを記憶している個々のノードによって実行されるファイル索引更新機能2800を示す。ファイルの与えられたコピーと共に記憶された図9に示す値992によって示されるファイル索引更新時間が、x時間より前に満了した場合、機能2802は、ネットワーク分散型索引付け方式に最も近く再参入されるようにファイルに対して実行される図24に関して上述したタイプのファイルネットワーク登録項目へのコピーを機能2804に実行させる。
【0203】
通常、機能2802の調査に用いられる時間xは、ファイルのコピーを記憶しているノードによって記憶される索引更新時間と、ファイルコピーの位置を索引付けするノードによって記憶される関連有効期日との間に通常存在するわずかな時間差に対応する。従って、機能2802の調査が満たされない場合、ファイル索引更新時間は、まだ満了していない。この場合、機能2806は、ファイル索引更新時間が満了しつつあるかどうか調べて確認しなければならない。そうであれば、機能2808及び2810が実行される。機能2808は、ノードに索引更新メッセージを送り、連続更新数でファイルコピーを索引付けして、そのノードに対して、新しく拡張された有効期日がどの程度に予め設定されるべきかを示す。機能2810は、図9に示すファイルの対応する連続更新数994をインクレメントし、こうして、ノードには、次の有効期日拡張が設定される際、現ファイルのコピーを連続して維持したことに対する評価が与えられることになる。
【0204】
図29は、図28で機能2808に関して上述したタイプの任意の索引更新メッセージを受信するノードによって実行されるファイル索引更新メッセージ応答機能2900を示す。
【0205】
このような索引更新メッセージが、更新メッセージに関連するファイルに対するファイル登録項目のファイルコピーを記憶しているノードのリストにリスト化されたノード受信された場合、機能2902及び2904は、更新メッセージに関連する連続更新数の関数として、ファイルのノードのコピーに対する新しい有効期日を設定する。上述したように、新しい有効期日が設定された未来への時間の長さは、連続更新数の関数である。連続更新数が極めて小さい場合、新しい有効期日は、未来へ数分だけ設定される。連続更新数が大きくなるにつれて、新しい有効期日は、幾つかの実施形態では、12又は24時間という長い時間の期間だけ未来へ拡張される。
【0206】
上記説明及び図面は、説明及び例示のためだけに与えられること、また、本発明は、追加された新規事項の解釈によってそのように限定されない限り、それらに限定されるものではないことを理解されたい。本開示内容を目の当たりにする当業者は、本発明の範囲から逸脱することなく、本内容に修正及び変更を成し得る。
【0207】
本出願の発明は、オペレーティングシステム、コンピュータハードウェア、又はコンピュータネットワークのいずれか1つタイプでの用途に限定されるものではなく、従って、本発明の他の実施形態は、異なるソフトウェア及びハードウェアシステムを用い得る。
【0208】
更に、以下の新規事項に述べたプログラムの働きは、実質的に全てのプログラムの働きと同様に、実質的に異なる構成及び順序を用いて、数多くの異なるプログラミング及びデータ構造によって実行し得ることを理解されたい。これは、プログラミングは、如何に複雑な与えられたアイデアも、当業者によって理解されると、実質的に無限の方法で記述し得る極端に柔軟性のある技術であることによる。従って、新規事項は、添付図に記述した厳密な機能及び/又は機能の順序に限定することを意図しない。このことが特に真実である理由は、上記明細書に述べた擬似コードは、大幅に簡素化されており、不必要な詳細事項で当業者に重荷を負わせることなく、本発明を実現するために当業者が知る必要があることをより効率的に伝えるようにしたためである。このような簡素化の観点において、上述した擬似コードの構造は、慣れたプログラマが、本発明を実現する際用いるであろう実際のコードの構造と大幅に異なることが多い。更に、明細書のソフトウェアで実行されるように示したプログラム化した働きの多くは、他の実施形態では、ハードウェアで実行し得る。
【0209】
上述した本発明の多くの実施形態において、本発明の様々な側面が、共に生じるように示したが、これらは、本発明のそれらの側面の他の実施形態においては、別々に起こり得る。
【符号の説明】
【0210】
100・・・スカイリスネットワーク
102A・・・ノード
102B・・・デスクトップコンピュータ
102C・・・携帯タブレットコンピュータ
102D・・・携帯情報端末コンピュータ
102E・・・携帯電話
102F・・・腕時計コンピュータ
114・・・バス
118・・・表示装置
122・・・キーボード
124・・・マウス

【特許請求の範囲】
【請求項1】
各ノードが索引アドレス空間及び別のネットワークアドレス空間にアドレスを有する分散型索引付けネットワークにおけるノードであって、前記ノードには、
プログラム命令及びデータ構造を記憶するための機械読取可能なメモリと、
前記メモリに記憶されたプログラム命令を実行するための1つ又は複数のプロセッサと、が含まれ、
前記メモリに記憶されたプログラム命令には、
索引アドレス空間の一部をノードと関連付ける段階と、
複数の各交信相手用の索引空間及びネットワークアドレスを記憶する交信相手リストを維持する段階であって、各交信相手は、前記索引付けネットワークの他のノードである前記段階と、
少数の前記交信相手リストを直接交信相手として処理し、また、前記交信相手の残りを間接交信相手として処理する段階と、
その直接交信相手が依然としてネットワークのメンバかどうか判断するために、最小頻度で各直接交信相手との通信を試みる段階と、
与えられた直接交信相手が、もはやネットワークのメンバとして機能していないという判断に応答する段階であって、その与えられた交信相手を置き換える新しい直接交信相手を見つけて、置換交信相手の索引及びネットワークアドレスのノードの交信相手リストにおける置換された直接交信相手を置き換えることによって前記応答する段階と、が含まれ、
ノードは、このような検索要求を送りつける次のノードとして、与えられたアドレスに最も近いその交信相手リスト上のアドレスを用いることによって、そのアドレスが直接又は間接アドレスかどうかに拘らず、ノードに関連する索引アドレス空間の一部に入らない与えられた索引アドレスに対する検索要求に応答するノード。
【請求項2】
請求項1に記載のノードであって、
前記ノードは、ノードの直接交信相手の内関連する1つからノードの各間接交信相手の索引アドレス及びネットワークアドレスを学習し、
前記ノードは、間接交信相手の索引及びネットワークアドレスをそれが学習した直接交信相手と同じ直接交信相手から、与えられた間接交信相手の状態の変化について学習するノード。
【請求項3】
請求項2に記載のノードであって、
前記プログラム命令には、ノードの交信相手の一部を要求元ノードに送り、ノードが前記一部の交信相手を他の要求元ノードに送ったという記録を記憶することによって、一組の交信相手用の他のノードからの要求に応答するための命令が含まれ、
要求に応答する前記ノードは、与えられた直接交信相手がネットワークのメンバとしてもはや機能していないと判断し、また、与えられた直接交信相手を交信相手要求に応答してノードが以前送った任意の他のノードに、与えられた交信相手は置き換えられたというメッセージを、置換交信相手の索引アドレス及びネットワークアドレスを含み、送る段階が含まれるノード。
【請求項4】
請求項3に記載のノードであって、
前記プログラム命令には、他のノードからのメッセージに応答するための命令が含まれ、前記他のノードによってノードに供給された与えられた間接交信相手が、与えられた索引及びネットワークアドレスを有する新しい間接交信相手によって置き換えられたことを、
ノードの交信相手リストの与えられた間接交信相手を置換ノードの索引及びネットワークアドレスで置き換える段階と、
置換された間接交信相手を交信相手要求に応答してノードが以前送った任意の他のノードに、以前通信された交信相手が置き換えられたことを示すメッセージを、置換交信相手の索引アドレス及びネットワークアドレスを含み、送る段階と、によって示すノード。
【請求項5】
請求項4に記載のノードであって、
前記ノードは、その間接交信相手が依然としてネットワークのメンバであるかどうか判断するために、それが直接交信相手と通信を行う最小頻度の10分の1より大きい頻度で間接交信相手と直接通信せず、また、直接交信相手との通信を介して、このような間接交信相手の状態の変化について学習するノード。
【請求項6】
各ノードが索引アドレス空間及び独立のネットワークアドレス空間にアドレスを有する分散型索引付けネットワークであって、前記ネットワークは、複数のノードを含み、各ノードには、
プログラム命令及びデータ構造を記憶するための機械読取可能なメモリと、
前記メモリに記憶されたプログラム命令を実行するための1つ又は複数のプロセッサと、が含まれ、前記メモリに記憶されたプログラム命令には、
索引アドレス空間の一部をノードと関連付ける段階と、
ノードの関連する一部の索引アドレス空間内で関連する索引アドレス値を有する索引付けされた情報を前記ノード上に記憶する段階と、
もしあれば、その索引値と共にノード上に記憶された情報にアクセスすることによって、与えられた索引値に関連する情報に対する要求に応答する段階と、が含まれ、
複数の各ノードに関連する索引アドレス空間の一部の全て又は部分がオーバーラップし、こうして、前記複数のノードの各ノードは、同様な組の索引アドレス値に対して、索引付けされた情報を記憶するネットワーク。
【請求項7】
請求項6に記載のノードであって、前記ノードは、プログラム命令を含み、前記プログラム命令は、
与えられた索引値で索引付けされる新しい情報の登録に応答する段階であって、検索を実行して、前記与えられた索引付けされた値を含む索引空間の一部に関連するノードを見つけることによって前記応答する段階と、
与えられた索引値と共に、検索によって見つけられたノード上に新しい情報を記憶する段階と、
索引空間の与えられた部分に関連するノード間において、1つのこのようなノード上の前記与えられた索引空間部分内に入る索引値の下で索引付けされた情報を通信する段階と、
前記索引値と共にこのような情報のコピーを記憶することによって、与えられたノード上で、このような通信に応答する段階と、が含まれるノード。
【請求項8】
請求項6に記載のノードであって、前記ノードは、プログラム命令を含み、前記プログラム命令は、
索引アドレス空間の与えられた部分を索引付けするノードの数をノードが決定できるようにする段階と、
索引アドレス空間の前記与えられた部分を索引付けするノードの数が、与えられた下限値より小さいという判断に応答する段階であって、索引空間の前記与えられた部分を現在索引付けしていない1つ又は複数の他のノードにメッセージを送り、前記他のノードが前記与えられた索引空間部分の索引付けを開始するように要求することによって前記応答する段階と、
索引アドレス空間の前記要求された部分を含むように索引アドレス空間の部分を与えられたノードに変えることによって、このような要求に応答する段階と、が含まれるノード。
【請求項9】
各ノードが索引アドレス空間及び別のネットワークアドレス空間にアドレスを有する分散型索引付けネットワークにおけるノードであって、前記ノードには、
プログラム命令及びデータ構造を記憶するための機械読取可能なメモリと、
前記メモリに記憶されたプログラム命令を実行するための1つ又は複数のプロセッサと、が含まれ、前記メモリに記憶されたプログラム命令には、
索引アドレス空間の一部をノードと関連付ける段階と、
ノードの関連する一部の索引アドレス空間内で関連する索引アドレス値を有する索引付けされた情報を前記ノード上に記憶する段階と、
もしあれば、与えられた索引値と共にノード上に記憶された情報にアクセスすることによって、与えられた索引値に関連する情報に対する要求に応答する段階と、
そのノードを含み、論理ノードを形成し、同じ一部の索引アドレス空間に全て関連付けられ実質的に同じ索引付けされた情報を記憶するノードから構成される一組のネットワークのノードを定義する段階と、
何らかの新しい情報を取得するために前記論理ノードの他のノードと通信する段階であって、前記情報は、ノード上にはまだ記憶されていないがこのような他のノードが記憶したものであり、また、論理ノードの関連する一部の索引アドレス空間内に関連する索引アドレス値を有する前記段階と、
前記新しい情報のコピーをノード上に記憶する段階であって、ノードが、ネットワークに充分長く留まる場合、与えられた期間の時間に渡り、論理ノードの他のノードによって記憶された実質的に全てのこのような情報のコピーを得るように前記記憶する段階と、が含まれるノード。
【請求項10】
請求項9に記載のノードであって、
前記メモリは、ノードの論理ノードにおけるノード数の推定値を形成するための命令を記憶し、
前記メモリは、
このような推定値に応答する段階であって、1つ又は複数の機能を実行して、論理ノードを、論理ノードに関連する索引アドレス空間の一部の別の部分に各々関連する複数の新しい別の論理ノードに分割することによって、論理ノードにおけるノード数が或るサイズを超えていることを示す前記応答する段階と、
このような推定値に応答する段階であって、1つ又は複数の機能を実行して、ノードの現論理ノードを第2の異なる現論理ノードと併合し、ノードの現論理ノード及び第2の現論理ノードの双方に関連する索引アドレス空間の一部を含む索引アドレス空間の関連する一部を有する1つの新しい論理ノードを形成することによって、論理ノードにおけるノード数が或るサイズ未満であることを示す前記応答する段階と、の内少なくとも1つのための命令を記憶するノード。
【請求項11】
請求項10に記載のノードであって、ノードのメモリは、分割及び併合する前記両機能を実行するための命令を記憶するノード。
【請求項12】
請求項11に記載のノードであって、
前記プログラム命令は、一組のアドレスビットによって表現し得る一組の可能な値によって、索引アドレス空間を表し、
与えられた論理ノードを形成するノードは、前記一連のアドレスビットの与えられた一連の最上位ビットに対して、全て共通の組のビット値を共有し、
論理ノードの前記分割及び//又は併合は、ノードの論理ノードのノードによって共有される索引アドレス空間の一連の最上位ビットの長さを変更する段階を伴うノード。
【請求項13】
請求項9に記載のノードであって、前記メモリは、命令を記憶し、前記命令には、
ノードの論理ノードにおけるノード数の推定値を形成する段階と、
このような推定値に応答する段階であって、ノードの論理ノードに関連する一部の索引アドレス空間内に入る値にそれらの索引アドレス値を変えることによりノードの論理ノードに参加するようにネットワークの他のノードに要求することによって、論理ノードのノード数が或るサイズ未満であることを示す前記応答する段階と、が含まれるノード。
【請求項14】
請求項9に記載のノードであって、前記論理ノードの他のノードと前記通信する段階は、その論理ノードの異なるノードと或る最小頻度で通信する段階を含み、ここで、このような各通信において、少なくとも1つの与えられた側は、通信において他の側によって記憶された情報更新のリストを受信し、このような各更新は、それが発生したノードを示し、また、更新発生の相対的な時間の指標を受信し、与えられた側がまだそのコピーを有さない何らかの更新を他の側から取得し、また、それら更新のコピーを記憶するノード。
【請求項15】
請求項9に記載のノードであって、前記命令は、命令を含み、前記命令には、
ノードが、分散型索引付けネットワークに参入しようとしている時、ノードに対する潜在的な索引アドレス値として用いるための少なくとも2つの索引アドレス値を取得する段階であって、前記潜在的な各索引アドレス値について、
その潜在的なアドレス値を含む索引アドレス空間の一部に関連する論理ノードに属する他のノードに対する検索をネットワーク上で実行する段階と、
その関連する論理ノードの密度に関して、このような他の各ノードに問い合わせる段階と、が含まれる前記取得する段階と、
最も小さい密度の関連する論理ノードを有するその1つの潜在的な索引アドレス値をノードの新しい索引アドレス値として選択する段階と、
次に、ノードの新しい索引アドレス値に関連する論理ノードの他のノードとの前記通信を開始する段階と、が含まれるノード。
【請求項16】
請求項9に記載のノードであって、
前記プログラム命令は、一組の索引アドレスビットによって表現し得る一組の可能な値によって、索引アドレス空間を表し、
与えられた論理ノードを形成するノードは、全て、共通の一部の前記索引アドレスビットに対する共通の組のビット値を共有するノード。
【請求項17】
請求項16に記載のノードであって、前記共有ビットは、前記索引アドレスビットにおける一連の最上位ビットであるノード。
【請求項18】
各ノードが索引アドレス空間及び別のネットワークアドレス空間にアドレスを有する分散型索引付けネットワークにおけるノードであって、前記ノードには、
プログラム命令及びデータ構造を記憶するための機械読取可能なメモリと、
前記メモリに記憶されたプログラム命令を実行するための1つ又は複数のプロセッサと、が含まれ、前記メモリに記憶されたプログラム命令には、索引アドレス空間の一部をノードと関連付ける段階と、ノードの関連する一部の索引アドレス空間に対応する索引値を有する1つ又は複数の各キーワードに対するキーワード登録項目を前記ノード上に記憶する段階であって、与えられたキーワードに関連するこのような各キーワード登録項目は、与えられたキーワードに関連する1つ又は複数のオブジェクトに関する情報を記憶する前記段階と、対応するキーワード登録項目をノードが記憶するキーワード索引値に関連する情報に対する要求に、そのキーワード登録項目のノード上に記憶された情報にアクセスすることによって、応答する段階と、が含まれるノード。
【請求項19】
請求項18に記載のノードであって、キーワードに関連する前記索引値は、キーワードのハッシュであるノード。
【請求項20】
請求項20に記載のノードであって、与えられたキーワードに関連するキーワード登録項目は、与えられたキーワードに関連する1つ又は複数のファイルのリストを含むノード。
【請求項21】
請求項20に記載のノードであって、キーワード登録項目は、1つ又は複数のファイルの前記リストの各ファイルに関連する索引値を含み、前記メモリは、また、ノードに関連する一部の索引アドレス空間内にある索引値を有する1つ又は複数の各ファイルに対するファイル登録項目を前記ノード上に記憶するためのプログラム命令を記憶するノード。
【請求項22】
請求項21に記載のノードであって、前記各ファイル登録項目は、前記ネットワークの1つ又は複数の異なるノード上に記憶された登録項目関連ファイルの全て又は一部の一組の1つ又は複数のコピーに関する情報、及びこのような各コピーが記憶されるノードのネットワークアドレスを含むノード。
【請求項23】
各ノードが索引アドレス空間及び別のネットワークアドレス空間にアドレスを有する分散型索引付けネットワークにおけるノードであって、前記ノードには、
プログラム命令及びデータ構造を記憶するための機械読取可能なメモリと、
前記メモリに記憶されたプログラム命令を実行するための1つ又は複数のプロセッサであって、前記メモリに記憶されたプログラム命令には、
索引アドレス空間の一部をノードと関連付ける段階と、
ノードの関連する一部の索引アドレス空間に対応する索引を有する1つ又は複数の各ファイルに対するファイル登録項目を前記ノード上に記憶する段階であって、このような各ファイル登録項目は、その関連するファイルに関する情報と、前記ネットワークの1つ又は複数の異なるノード上にコピーを記憶し得る登録項目の関連するファイルの全て又は一部の一組の1つ又は複数の各コピーに関する情報とを、このような各コピーが記憶されるノードのネットワークアドレスを含み、記憶する前記段階と、
与えられた索引値を有するファイルに関連する情報に対する要求を受信する段階であって、これには、このような要求を生成したノードのネットワーク位置の指標を含む前記段階と、が含まれる前記1つ又は複数のプロセッサと、
要求されたファイルの索引値が、ノードに関連する一部の索引アドレス空間内に入る場合、要求されたファイルの登録項目にリスト化された全て又は一部のファイルの一組の1つ又は複数のコピーに関する情報を、それらコピーを記憶しているノードのネットワークアドレスを含み、要求を送ったノードに送ることによって、このような索引によるファイル要求に応答する段階と、が含まれ、
どのファイルコピーが情報を要求元ノードに送るかに関する前記選択する段階には、要求元ノードのネットワーク位置が与えられると、与えられたファイルコピーが記憶されるネットワーク位置の見かけの適切さの関数として、前記選択を行う段階が含まれるノード。
【請求項24】
直接交信相手に関して、交信相手リストは、その交信相手状態履歴に関する情報を記憶し、交信相手状態履歴は、与えられた直接交信相手に対して過去に交信した試みの回数に関する情報を提供することにより、与えられた直接交信相手に対する交信の試みが或る回数を超えて失敗する場合、現ノードは、与えられた直接交信相手を新しい直接交信相手に置き換える必要があると判断することを特徴とする請求項1〜23の何れか1項に記載のノードまたはネットワーク。
【請求項25】
共有区域データは、区域のノードから生じる全ての最新の未確認情報からなるリストである未確認情報リストを含み、未確認情報は、区域のノードによって共通に索引付けされるべき情報を伝達し、未確認情報リストは、未確認情報ごとに、その発生時間を示すタイムスタンプを含むことを特徴とする請求項1〜24の何れか1項に記載のノードまたはネットワーク。
【請求項26】
登録項目は、ファイルのコピーを記憶するノードごとに、ノードがファイヤウォールの背後にあるか否かの指標も含み、そうであれば、その中継交信相手情報を含むことを特徴とする請求項1〜25の何れか1項に記載のノード。
【請求項27】
登録項目は、ファイルのコピーを記憶するノードごとに、登録項目有効期日を含み、有効期日は、コピーがその位置で依然として利用可能であることを示すそのノードから更新メッセージが受信されるまで、ファイルの与えられたコピーの登録項目がファイルを格納するノードのリストから除去されることを特徴とする請求項1〜26の何れか1項に記載のノード。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate


【公開番号】特開2011−150702(P2011−150702A)
【公開日】平成23年8月4日(2011.8.4)
【国際特許分類】
【出願番号】特願2011−24048(P2011−24048)
【出願日】平成23年2月7日(2011.2.7)
【分割の表示】特願2004−538472(P2004−538472)の分割
【原出願日】平成15年9月18日(2003.9.18)
【出願人】(506016691)スカイプ・リミテッド (16)
【氏名又は名称原語表記】SKYPE LIMITED
【Fターム(参考)】