仮想ネットワーク
仮想ネットワークは、それぞれのノードが他のこのようなノードへのリンクを表す所定数（Ｌ）のアドレスまで記憶するためのリストを備えた複数のノードを有する。これらのリンクは、第１のノードと第２のノードの間のリンクを要求するメッセージを受信すること（３００）と、前記第１のノードと第２のノードの両方が、それぞれのケースで、前記所定数未満であるそのリストの中に多くのアドレスを有しているかどうかを判断すること（３０１、３０５）と、この条件が満たされる場合に、第１ノードのアドレスを第２のノードのリストの中に挿入（３０８）し、第２のノードのアドレスを第１のノードのリストの中に挿入すること（３０７）と、この条件が満たされないときに、第１のノードが、前記所定数より少なくとも２少ないそのリストの中に多くのアドレスを有するかどうかを判断すること（３０９）と、有する場合に（ａ）第３のノードのアドレスを第２のノードのリストから選択すること（３１０）と、（ｂ）第３のノードのアドレスを第２のノードのリストから削除すること（３１３）と、（ｃ）第２のノードのアドレスを第３のノードのリストから削除すること（３１４）と、（ｄ）第１のノードのリストの中に第２のノードのアドレスを挿入すること（３１１）と、第１のノードのリストの中に第３のノードのアドレスを挿入すること（３１２）と、（ｅ）第２のノードのリストの中に第１のノードのアドレスを挿入し（３１３）、第３のノードのリストの中に第１のノードのアドレスを挿入すること（３１４）とによって管理される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は仮想ネットワークに関し、特に集中記憶装置または制御装置を備えないものなど、ピアツーピアシステムなどの分散型システムに関するが、それに限定されない。
【発明の開示】
【課題を解決するための手段】
【０００２】
本発明のある態様によれば、各ノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを有する複数のノードを有する仮想ネットワークを操作する方法が提供され、
（ｉ）第１のノードと第２のノードの間のリンクを要求するメッセージを受信することと、
（ｉｉ）第１のノードと第２のノードの両方が、それぞれのケースでそのリスト内に所定数未満であるいくつかのアドレスを有するかどうかを判断することと、
（ｉｉｉ）この条件が満たされる場合には、第１のノードのアドレスを第２のノードのリストに挿入し、第２のノードのアドレスを第１のノードのリストの中に挿入することと、
（ｉｖ）この条件が満たされない場合には、第１のノードがそのリストの中に前記所定数より少なくとも２少ないいくつかのアドレスを有するかどうかを判断し、そうである場合には、
（ａ）第３のノードのアドレスを第２のノードのリストから選択することと、
（ｂ）第３のノードのアドレスを第２のノードのリストから削除することと、
（ｃ）第２のノードのアドレスを第３のノードのリストから削除することと、
（ｄ）第２のノードのアドレスを第１のノードのリストに挿入し、第３のノードのアドレスを第１のノードのリストに挿入することと、
（ｅ）第１のノードのアドレスを第２のノードのリストに挿入し、第１のノードのアドレスを第３のノードのリストに挿入することと、
を含む。
【０００３】
別の態様では、本発明は仮想ネットワークのノードを提供し、前記ノードは他のこのようなノードの所定数のアドレスまでを記憶するためのリストを含む記憶手段と、以下の動作、つまり
メッセージを受信することと、
リストの内容についての情報を要求するメッセージに応えることと、
リストからアドレスを削除するために受信した要求に従うことと、
リストへのアドレスの挿入を要求するメッセージに従うことと、
ノードと第２のノード間のリンクを要求するメッセージの受信に応えて、
（Ａ）そのリストの内容についての情報を要求する第２のノードに対するメッセージを作成することと、
（Ｂ）第１のノードと第２のノードの両方が、それぞれのケースで、そのリストに所定数未満であるいくつかのアドレスを有するかどうかを判断することと、
（Ｃ）この条件が満たされる場合、第２のノードのアドレスをそのリストに挿入し、そのリストにノードのアドレスを追加するように第２のノードに要求するメッセージを第２のノードに対して作成することと、
（Ｄ）この条件が満たされない場合には、ノードがそのリストに、所定数より少なくとも２少ないいくつかのアドレスを有するかどうかを判断することと、そうである場合に、
（ａ）第３のノードのアドレスを第２のノードのリストから選択することと、
（ｂ）第２のノードのアドレスを第１のノードのリストに挿入し、第３のノードのアドレスを第１のノードのリストに挿入することと、
（ｃ）第２のノードのリストからの第３のノードアドレスの削除、及びノードのアドレスの挿入を要求するメッセージを第２のノードに作成することと、
（ｄ）第３のノードのリストからの第２のノードのアドレスの削除、及びノードのアドレスの挿入を要求するメッセージを第３のノードに作成することと、
を実行するようにプログラミングされる処理手段によって定められる。
【０００４】
本発明の他の好ましい態様は請求項に定められる。
【０００５】
本発明のいくつかの実施形態は、以下、添付図面を参照して一例として説明する。
【発明を実施するための最良の形態】
【０００６】
（ノード）
本説明中、処理機能、記憶機能及び通信機能を有するコンピューティングノードについて言及する。コンピューティングノードは、１台のコンピュータでも、他のデバイスでもよく、あるいは−単一のコンピュータがその上で実行するいくつかの独立したプログラムまたはプロセスを有することができることに注意すると−このようなプログラムまたはプロセスであってよい。記憶されるデータの項目は、いくつかのこのような項目は単一のプログラムまたはプロセスによってサービスを受けてよいが、別個のノードとして見なされてもよい。
【０００７】
本説明は、各コンピューティングノードが、メッセージがそれに送信できるようなＩＰ（インターネットプロトコル）ネットワークのような電気通信網など、なんらかの通信インフラストラクチャに接続されていることを前提とする。したがって、各コンピューティングノードは通信インフラストラクチャ内のノードも構成する。
【０００８】
また、仮想ネットワークに属する仮想ノードに対しても述べる。コンピューティングノードはそれに関連付けられる（おそらくは異なる仮想ネットワークに属する）２つまたは３つの仮想ノードを有することができるため、区別は重要である。その名が暗示するように、仮想ノードはいかなる物理的な意味でも存在しない。むしろやがて明らかになるように、その存在は、仮想ノードの間のリンクを定義し、したがってそれが属する仮想ネットワークも定義する記憶されているデータにより確立される。
【０００９】
必然的に、仮想ノードは、それに処理機能、記憶機能、及び通信機能を与えるコンピューティングノードと関連付けられなければならない。つまり仮想ノードによるメッセージの送信、受信及び処理に対する参照は、仮想ノードの代わりにコンピューティングノードによるこのような送信、受信または処理を参照する。
【００１０】
例は図１に図示されている。コンピュータは、ネットワーク１０を介する通信のために通常の構成要素、すなわちプロセッサ１、メモリ２、ディスプレイ３、キーボード４及び通信インタフェース５を有する。
【００１１】
メモリ２は、オペレーティングシステムと他のプログラム（図示せず）、及び図示されているテキストファイル２０などのデータファイルを格納している。それは、テキストファイル２０とそれ自体のアドレス２１ｂに対応するラベル２１ａを含む２１も有する。さらに、それはアドレスリスト２２、及びコンピュータ上で仮想ネットワークのノードの存在をともに定義するサポートプログラム２３を有する。このノードにはアドレス２４が付いている。別の仮想ネットワークのノードの、コンピュータ上での存在をともに定義するアドレスリスト２５及びサポートプログラム２６も図示されている。このノードにはアドレス２７が付いている。リスト２２、２５に記憶されているアドレスは、同じ仮想ネットワーク内の他のノードのアドレスである。
【００１２】
（ルックアップシステム）
これは本発明の応用例の考えられる１つの例でしかありえないが、ここで分散型ルックアップシステムを説明する。このシステムによってユーザはコメントをウェブページと関連付けることができる。ユーザはこのページをビジットするたびに、他のユーザが行ったコメントを見る機会もある。コメントは、（例えばテキストファイルとして）コメントを寄せたユーザのコンピュータに記憶されている。
【００１３】
ウェブページ（またはむしろ、自分のコンピュータ）を見ているユーザは、ウェブページのユニバーサルリソースロケータ（ＵＲＬ）を有し、必要とされているのはユーザがコメントを取り出すことができる機構である。この例では、前記機構は以下のとおりである。
【００１４】
他のウェブページについてのコメントを含む他のテキストファイル、及びおそらく他の関連していないファイルもそうである可能性があるように、テキストファイルはコメントを寄せたユーザのコンピュータに記憶され、我々の国際特許出願ＷＯ第０３／０３４６６９号［代理人参照第Ａ３００４４号］に説明される方の仮想ネットワークのノードと関連付けられている。（本説明の文脈では一次仮想ネットワーク、または単に一次ネットワークと呼ばれる）この仮想ネットワークは、それを特定するラベルを有するのであればそのアドレスを知らなくてもノードにメッセージを送信できるようにするのに役立つ。その種のネットワークは一意のラベル（ノードあたり１つ）で機能できるが、この例ではラベルは一意ではない。むしろ、ある特定のウェブページについてのコメントを含むテキストファイルに関連付けられるすべてのノードが同じラベルを有する。このラベルはウェブページのＵＲＬのハッシュ関数である。この仮想ネットワークは、ただ１つのノードに到達する取り出し機構を提供する。
【００１５】
テキストファイルは、第２の仮想ネットワークのノードとも関連付けられる。これ（二次仮想ネットワーク）は前記１つの特定のウェブページについてのコメントを含むテキストファイルと関連付けられているノードだけを含む。
【００１６】
しかしながら、我々の前述された国際特許出願による一次ネットワークの使用が好ましいが、それが必須ではないことに注意する。事実上、仮想ネットワークを使用することはまったく必須ではない。ラベルを受信し、それに対応する１つのノードのアドレスを返す別の一次取り出し機構が代わりに使用できるであろう。
【００１７】
コメントをポストするコンピュータは図１に図示されるとおりであり、
・一次ネットワーク内でノードを作成しなければならない。このノードはラベル２１ａ及びネットワークアドレス２４を有している。
【００１８】
・二次ネットワーク内でノードを作成しなければならない。このノードにはネットワークアドレス２７が付いている。
【００１９】
当初、アドレスリスト２２、２５は、リスト２２がブートストラップリンクを含んでいるのを除き、空である。リスト２２が一次ネットワークのいくつかの他のノードのラベルとアドレスを含み、リスト２５が二次ネットワークのいくつかの他のノードのアドレスを含むことを確実にするためのネットワークの自己組織化については、後述する。まず当分は、システムはこれらのラベルとアドレスが存在しているという仮定に基づいて説明する。
【００２０】
この時点でアドレスについて少し説明することが必要である。テキストファイル２０によって形成されるノード、一次仮想ネットワークのノード、及び二次仮想ネットワークのノードは、概念上はただ１つのアイデンティティを有しているが、独自のアドレスを有している。実際問題としてはこれは特に便利ではないが、それぞれのノードに通信網１０内の異なるアドレスを割り当てることが可能であろう。我々の好ましいインプリメンテーションでは、各ノードは以下の３つの部分から構成されるアドレスを有する。
【００２１】
・コンピューティングノードの場所を指定するインターネットアドレス。例えば、１３０．１４６．２０９．１５
・コンピューティングノードにおけるある特定の通信ポートの場所を指定するポート番号。ポートはインターネットアドレスの標準的な部分である。例えば、それらは異なる独立したアプリケーションプログラムがメッセージを独立して送信、受信できるようにする。つまり、それぞれが専用のポートでメッセージを受信し、他のアプリケーションプログラム向けのメッセージは受信しない、あるいは他のアプリケーションプログラム向けのメッセージによって「混乱」しないであろう。ポート番号とともにインターネットアドレスは、（使用されるＴＣＰ／ＩＰなどの通信プロトコルの一部であるため）ネットワークアドレスと見なすことができる。すべての一次ノード及び二次ノードのためのネットワークアドレスは同じである場合があるが、必ずしもそうである必要はない。例えば、一次ノードのための全メッセージは、（このようなメッセージを区別する１つの方法である）二次メッセージがそこで受信されるそれとは別のポートで受信されてよい。
【００２２】
・メッセージが向けられる特定のノードの場所を指定するノード識別子（整数値）。例えば一次ネットワークでのすべてのメッセージが専用ポートで受信される場合も、各ノードと関連付けられた局所的に一意の識別子がある。したがって、複数のノードがあるときに、メッセージがどのノード向けであるのかが明確である。このノード識別子はアプリケーションに特殊なアドレス拡張子（それは標準インターネットプロトコルの一部ではない）である。それは送信されるメッセージに含まれるだけである。それを受信するプロセスはこれを「知って」おり、メッセージがどのノードに転送される必要があるのかを判断するためにこのノード識別子を調べる。
【００２３】
両方のノードが同じネットワークアドレスを有することはありえるが、必ずしもそうである必要はない。（部分的には使用可能なポートの数が制限されることがあるため）すべてのノードが専用のポートを有するわけではないが、２つのポート（したがって、２つの異なるネットワークアドレス）を有することもある。つまり、１つは一次ネットワーク用、１つは二次ネットワーク用である。通常、すべて同じポートを使用できるであろういくつかの二次ネットワークがある。
【００２４】
以下では、ノードのアドレスに対する参照がそのノードの完全なアドレスを指すことが強調されなければならない。
【００２５】
特に魅力的な手法は、テキストファイル及び一次ノードと二次ノードがすべて同じノード識別子（及びＩＰアドレス）を有し、ポート番号だけが異なっていることを提供することである。このようなアドレス指定プロトコルは、あるノードのアドレスを有し、それに関連付けられる別のノードのアドレスを必要とする場合に、後者のノードのアドレスが、調べられなければならないよりはむしろ、前者のアドレスから推定される可能性があるという点で、処理のいくらかを簡略化するための機会を与える可能性がある。しかしながら、以下の説明では、このような簡略化は行われておらず、その結果これらのプロセスは任意のアドレスプロトコルを扱うであろう。
【００２６】
ウェブページを見るコンピュータは、
・ラベルを取得するために同じハッシュ関数をＵＲＬに適用することによって
・あるノードのアドレスを取得するために一次仮想ネットワーク上で（ラベルを含む）照会を送信することによって、
・見つけられたアドレスを使用して、二次仮想ネットワーク上の多くの（あるいはすべての）他のノードのアドレスも取得するために二次仮想ネットワーク上で照会を送信することによって、
・表示するためのコメントを取り出すためにこれらのアドレスを使用することによって
関連付けられたコメントを取り出す。
【００２７】
取り出すコンピュータが必ずしも仮想ネットワークのノードを含まなくてもよいことに注意する。つまり、それは、取り出しプロセスを実現するためのソフトウェアをロードされ、それが仮想ネットワークのノードが常駐するコンピュータと通信できるように通信インタフェースをロードされた従来のコンピュータである場合がある。このプロセスは図１Ａのフローチャートに示され、以下のように進行する。
【００２８】
ステップ３０：ユーザがＵＲＬを入力する（あるいはハイパーリンクを呼び出す）のに続き、コンピュータは対応するウェブページを取り出す。このステップはまったく従来的である。
【００２９】
ステップ３１：ラベルを取得するためにハッシュ関数がＵＲＬに適用される。我々の以前の国際特許出願に説明されるように、これはＳＨＡ−１アルゴリズムを使用できる。
【００３０】
ステップ３２：このラベルと取り出し側コンピュータのネットワークアドレスを含む「Ｆｉｎｄ」メッセージが一次ネットワークに送信される。コンピュータが少なくとも１つのこのようなアドレスを所有していることが必要なのは明白である。
【００３１】
ステップ３３：取り出し側コンピュータが一次コンピュータから「Ｆｏｕｎｄ」メッセージを受信する。このメッセージは二次ネットワークの関連付けられたノードのアドレス及びコメントのアドレスだけではなく、発見されたノードのラベルとアドレスも含む。「Ｆｏｕｎｄ」メッセージが妥当な時間内に受信されない場合にプロセスを打ち切るためのタイムアウト機構を含むことができる。
【００３２】
ステップ３４：この例では、一次ネットワークは常に、それが「Ｆｉｎｄ」メッセージに含まれるラベルに最も近いラベルを含むノードのアドレスを返すように配置される。したがって、返されるラベルが要求されたラベルと同じであるかどうかを確かめるためにチェックが実行され、同じではない場合、プロセスは終了する。「最も近い」の意味の説明については以下を参照されたい。
【００３３】
ステップ３５：ラベルが一致すると仮定し、取り出し側コンピュータは、それがそれにより二次ネットワークを使用して追加のアドレスを取り出すために発見（Ｆｏｕｎｄ）メッセージによって返されるアドレスを使用する（詳しく後述される）プロセスを実行する。
【００３４】
ステップ３６：次にこれらのアドレスはコメントを含むテキストファイルを「ポスト側」コンピュータから取り出すために使用される（ｕｓｅｓ）。
【００３５】
（二次仮想ネットワーク）
このネットワークの目的は、ノードのグループを、グループの一部であるすべてのノードを発見するためにその後使用できる単一の仮想ネットワークに自己組織化することである。主要な要件は、結果としてネットワークがすべてのノードを含んでいることである。別の要件は、ネットワークを作成、維持するために必要とされるシステム負荷がすべてのノード全体で等しく拡散されることである。これは、さまざまなユーザが自分のリソースを１つの分散型アプリケーションに寄与するときに重要である、最も「公平」であるだけではなく、システムを過負荷から保護するのに役立つ。
【００３６】
したがって、ネットワークには以下の特性がある。
【００３７】
・各ノードによって維持されるリンクの数は好ましくは同じである。
【００３８】
・すべてのリンクは双方向である。その結果ノードへのリンク数も各ノードについて同じである。これはノードが受信し、処理しなければならないメッセージ数に影響を及ぼすため重要である。
【００３９】
・それは「平坦な」構造を有している。ノードは自らを階層的に配列しない。その結果システム負荷はすべてのノード全体で等しく拡散される。
【００４０】
（各ノードの構造）
各ノードは、それに関連付けられる以下のデータを有する。
【００４１】
・他のノードに対する複数のリンク。各リンクは別のノードのアドレスにすぎない。核リンクに関連付けられているのは、「確認済み」または「未確認」である場合があるステータスである。各ノードは、システム全体のパラメータＬによって指定される最大数のリンクを維持できるにすぎない。Ｌの典型的な値は、例えば６である。このパラメータがすべてのノードについて同じであることは必須ではないが、それらが異なるようにすることにより獲得される利点はない。
【００４２】
・スペアリンク、つまり手短に言えばスペアのリスト。各スペアは別のノードのアドレスにすぎない。スペアは仮想ネットワークを構築するために自己組織化プロセスによって使用される。ノードは、それがすでにノードにリンクしているため、またはそれがすでに最大数のリンクを有しているためのどちらかの理由により、それがリンクとして追加できない前記ノードについて通知されると他のノードをスペアとして追加する。ノードが維持できるスペアの数も制限され、システム全体のパラメータＳによって指定される。Ｓの典型的な値は、例えば３である。スペアリンクのリストは概して必須ではないが、それにより局所的に収容できないリンクを仮想ネットワークのなんらかの他のポイントに伝搬できる追加の機構を提供する上で非常に貴重である。しかしながら、スペアリンク（または類似した伝搬機構）を使用することは、入信するＮｏｔｉｆｙメッセージがつねに二次ネットワークの同じノード（または非常に少ない数のノードの内の１つ）に到着するシステムでは必要である。
【００４３】
（メッセージ）
ネットワークに自己組織化するため、及びどのノードが特定のネットワークの一部であるのかを発見するために、ノードは互いにメッセージを送信する。以下に示すタイプのメッセージが二次ネットワークによって使用される。
【００４４】
・以下を含むＡｄｄＬｉｎｋメッセージ
・送信者のアドレス
・受信者のアドレス
メッセージは相互リンクを要求するためにノード（送信者）によって別のノード（受信者）に送信される。
【００４５】
・以下を含むＣｈａｎｇｅＬｉｎｋメッセージ
・送信者のアドレス
・受信者のアドレス
・主題のアドレス
メッセージは、それがそのリンク（Ｚ）の内の１つをそれ自体（Ｘ）のリンクに変更することを要求するためにノード（Ｘ）によって別のノード（Ｙ）に送信される。プロトコルは、Ｘが、それにＹに対するそのリンクをそれ自体（Ｘ）に対するリンクで変更するように要求する、類似したメッセージをＺに送信するになている。したがって、事実上Ｘは現在ＸとＺの間にあるリンクにそれ自体を挿入することを要求すｒ。
【００４６】
・以下を含むＬｉｎｋＡｄｄｅｄメッセージ
・送信者のアドレス
・受信者のアドレス
メッセージは、送信者がそれに対するリンクをちょうど追加したところであることをノードに通知するために使用される。
【００４７】
・以下を含むＬｉｎｋＥｒｒｏｒメッセージ
・送信者のアドレス
・受信者のアドレス
・主題のアドレス
・エラーコード
メッセージはノードに、そのリンクの内の１つに問題があると考えられることを知らせるために使用される。例えば、主題ノードが応答しない可能性がある、あるいはリンクが相互的でない可能性がある。メッセージはエラーのタイプを示すためにエラーコードを含む。
【００４８】
・以下を含むＬｉｎｋｓメッセージ
・送信者のアドレス
・受信者のアドレス
・すべてのリンクのアドレス
・基準値
・Ｌｉｎｋｓメッセージは送信者ノードからのなんらかの他のデータも含む。ウェブページコメント例では、これは関連コメントのアドレスである。
【００４９】
メッセージは送信側ノードのすべてのカレントリンクを含む。それはつねにＬｉｎｋｓＱｕｅｒｙメッセージに応えて送信される。参照は、応答される前記特定の照会を区別するために使用できる。
【００５０】
・以下を含むＬｉｎｋｓＱｕｅｒｙメッセージ
・送信者のアドレス
・受信者のアドレス
・基準値
メッセージは、ノードにＬｉｎｋｓメッセージを（そのカレントリンクを含む）返事として送信するように要求するために使用される。
【００５１】
・以下を含むＮｏｔｉｆｙメッセージ
・送信者のアドレス
・受信者のアドレス
・主題のアドレス
・通知レベル
メッセージは、ノードにネットワーク内の別のノードを通知するために使用される。通知レベルはＮｏｔｉｆｙメッセージの伝搬を制御、制限するために使用される。ここで説明されるように、送信者アドレスは使用されないが、デバッグのために、あるいは肯定応答を送信することが所望される場合に有効である。
【００５２】
（二次ネットワークの構築）
システムはグループノードに単一の仮想ネットワークへ自己組織化させ、その結果１つのノードのアドレスを有すると、グループ内の他者のアドレスを発見できる。本項では、同じ二次ネットワークに所属するはずであるノードが発見されると、新しいリンクがどのようにして作成されるのかを説明する。ここでは２つの部分が区別できる。
【００５３】
同じ二次ネットワークに所属するはずであるノードの組の発見。複数のノードを同じネットワークの中にグループ化するための基準が何であるのかは、アプリケーション特有である。ウェブページ注釈例では、同じＵＲＬについてのコメントを表すすべてのノードは二次ネットワーク内で一緒にグループ化されなければならない。一緒にグループ化されなければならないノードがどのようにして発見されるのかもアプリケーション特有である。例を簡単に示す。
【００５４】
二次ネットワークをノード発見の結果として更新する／拡張すること。同じ二次ネットワークに所属しなければならない１組のノードが発見されると、システムは結果として１つまたは複数の新しいリンクを構築してよい。新しいリンクは必ずしもノードの前記組の間にはないが、例えばこれらの２つのノードのリンク先であるノードの間にあってよい。どのようにして新しいリンクが作成されるのかの詳細は後述する。
【００５５】
（Ｉｎｉｔｉａｌ Ｎｏｔｉｆｙ（初期通知）メッセージ）
二次ネットワークの組織化は、例えばグループの既存のメンバーと新しいメンバーを特定できる入信「通知」メッセージの存在を前提としている（早い段階ではどちらのノードもまだグループの一部ではないが、後に自己組織化プロセスの間に両方のノードともすでにグループの一部である可能性がある）。それに属さなければならないノードの二次ネットワークに通知するのはシステムの別の部分しだいである。それを行うことができるさまざまな方法がある。ここで、我々は、二次ネットワークが我々の以前の国際特許出願に説明される型の一次ネットワークと組み合わせて使用されるときに、これがどのようにして行われるのかの例を示す。ウェブページ注釈例では、各コメントは対応するウェブページのＵＲＬに基づくラベルの下で一次ネットワーク内のノードとして自らを公表する。このようにして、一次ネットワークは、ＵＲＬが存在する場合に特定のＵＲＬついてのコメントをルックアップするのに使用できる。特定のＵＲＬについてのすべてのコメントを示すために、各コメントはそれに関連付けられる二次ネットワークのノードも有する。同じＵＲＬについてのコメントに相当するノードはそのＵＲＬに特定的な二次ネットワークに自己組織化する。このようにして、いったん一次ネットワークがＵＲＬについての単一のコメントを見つけるのに使用されると、二次ネットワークは前記同じＵＲＬについての他のコメントを診付けるために使用できる。
【００５６】
したがって、このケースでは、ともにグループ化されなければならない二次ネットワークのノードはそれぞれ一次ネットワークの同じラベルの下で公表される。ノードが同じラベルの下で公表された別のノードを認識すると必ず、必要とされるＮｏｔｉｆｙメッセージが作成されるような改善策を含む、一次ネットワーク内で、ノードがリンクを構築し、維持するために周期的に「Ｐｕｓｈ（プッシュ）」更新を実行する機構について、以下に説明する。
【００５７】
（通知メッセージの取り扱い）
ノードが、それがまだリンクしていないノードについてＮｏｔｉｆｙメッセージを受信すると、以下の１つが起こる。
【００５８】
受信側ノードがすでに最大数の許容リンクを有する場合、それ（受信側ノード）は（それがすでにそれ（リンク）をスペアとして有していない限り）代わりにそれをスペアとして追加する。これを行う際に、前記ノードがその最大スペア数を超えると、それは１つのスペアを削除する。次に、それ（前記ノード）はそれが削除した前記スペアにＮｏｔｉｆｙメッセージも転送する。それがこれを行うかどうかは、通知レベルの値次第である。通知レベルは、メッセージが際限なく伝搬するのを妨ぐために毎回減少する。
【００５９】
それ以外の場合、主題ノードがまだ最大数のリンクを有していない場合、受信側ノードは両方のノードの間に相互リンクを作成しようと試みる。これは図２のａとｂに描かれている。ここでは、Ｌ＝３であり、ノード１はノード２についてのＮｏｔｉｆｙメッセージを受信した。両方のノードとも２つのリンクしか有していなかったため、ノード１とノード２の間にリンクが作成される。
【００６０】
それ以外の場合、主題ノードがすでに最大数のリンクを有している場合は、単に両方のノード間に相互リンクを作成することは可能ではない。したがって、何が起こるかというと（ｗｈａｔ ｈａｐｐｅｎｓ）、受信側ノードが既存のリンクにそれ自体を挿入しようと試みる。これは図２のｃとｄに描かれている。ここでノード２とノード３の間のリンクは破壊されるが、それは２つの新しいリンク、つまりノード１とノード２の間のリンクとノード１とノード３の間のリンクによって置き換えられる。したがってリンクの総数は１だけ増加する。それは、たとえノード２とノード３がすでに最大数のリンクを有していたとしてもうまく行く。しかしながら、これが成功するためにはノード１が２つの新しいリンクを作成できることが必要であった。このプロセスは図３から図９のフローチャートにさらに詳細に説明される。
【００６１】
図３は、ノードが入信Ｎｏｔｉｆｙメッセージをどのように処理するのかを示す。ここでは、新しいリンクを作成する必要があるかどうかが決定され、そうである場合にはどのように（新しいリンクを追加することによって、あるいは既存のリンクを２つのリンクに変更することによって）作成されるべきかが決定される。新しいリンクが作成される場合、スペアの集合は更新され、Ｎｏｔｉｆｙメッセージが送信されてよい。
【００６２】
ステップ３００では、それを送信したノード（送信者）のアドレス、主題ノードのアドレス、及び伝搬制限値であるｎｏｔｉｆｙｌｅｖｅｌを含むＮｏｔｉｆｙメッセージが受信される。受信側ノードは最初に、それが新しいリンクをセットアップする空間を有するかどうかをチェックし（３０１）、空間がある場合には、それがすでに主題ノードへのアクセスを有しているかどうかをチェックする（３０２）。有していない場合、それ（受信側ノード）は主題とリンクをセットアップしようと試みる。
【００６３】
ステップ３０３では、それ（受信側ノード）は主題ノードにＬｉｎｋｓＱｕｅｒｙメッセージを送信し、ステップ３０４で応答を待つ。いったん応答−Ｌｉｎｋメッセージ−が受信されると、それ（「受信側ノード」または「前記ノード」）は、（それがその間にも他のメッセージを受信、処理し、その結果としてリンクを作成した場合）それが依然として新しいリンクをセットアップするための空間を有しているかどうかを再びチェックする（３０５）。空間がある場合、それは次に主題ノードが新しいリンクをセットアップするための空間を有するかどうかをチェックするために受信されたＬｉｎｋｓメッセージを調べる（３０６）。それが有する場合、ステップ３０７と３０８で、受信側ノードは主題ノードのアドレスを（「未確認」とマークされているが）そのリンクのリストに追加し、ＡｄｄＬｉｎｋメッセージを主題ノードに送信する。
【００６４】
しかしながら、ステップ３０６で、主題ノードが追加リンクを受け入れることができないと判断されると、受信側ノードは、図２を参照して前述されたように、それ自体を既存のリンクの中に挿入しようと試みる。第１のステップ（３０９）は、受信側ノードが２つのリンク分の空間を有するかどうかをチェックすることである。ない場合には、プロセスは終了する。しかしながら、ある場合には、受信側ノードは受信されたＬｉｎｋｓメッセージの中のリンクのリストから無作為に（受信側ノードがすでにリンクを有しているノードではない）リンク、すなわち主題ノードと、ここでは他と呼ばれる別のノードの間のリンクを選択する。それから、受信側ノードは、
３１１ 主題ノード（未確認）のアドレスをそのリンクのリストに追加する
３１２ 他のノード（未確認）のアドレスをそのリンクのリストに追加する
３１３ 他のアドレスを含むＣｈａｎｇｅＬｉｎｋメッセージを主題ノードに送信する
３１４ 主題のアドレスを含むＣｈａｎｇｅＬｉｎｋメッセージを他のノードに送信する
ことによって、それ自体をこのリンクに挿入しようと試みる。
【００６５】
しかしながら、ステップ３０１で、受信側ノードがリンクを追加するための空間を持たないと判断されると、あるいはステップ３０２で、それが主題ノードに対してすでにリンクを有していると判断されると、プロセスは受信側ノードがそのスペアリンクのリストにリンクを追加する必要があるかどうかを調べる。ステップ３１５では、主題ノードがすでにスペアリストにあると判明するとプロセスが終了する。ステップ３１６では、スペアリストにリンクを追加するための空間があるかどうかがチェックされ、ある場合には、これは３１７で正式に追加される。ない場合には、ステップ３１８でスペアリンクの内の既存のリンクが無作為に選択され、それがステップ３１７で主題へのリンクによって置換できるようにステップ３１９で削除される。また、変数ｎｏｔｉｆｙｌｅｖｅｌは３２０で減分され、（ステップ３２１）それがゼロ以外のままであると、ステップ３２２で元のＮｏｔｉｆｙメッセージが−ｎｏｔｉｆｙｌｅｖｅｌのこの新しい値とともに−無作為に選択された既存のリンクによって指される（置換と呼ばれる）ノードに転送される。
【００６６】
このプロセスの効果は、すでにリンクの完全な集合を有するノードＡがそれに主題ノードＢにリンクするように依頼するＮｏｔｉｆｙメッセージを受信すると、Ｂのアドレスがスペアリンクとして記録されるという点である。このリンクは、Ａのスペアリンクのリストがいっぱいになるまで休眠したままである。次に、ＡがそれにノードＣにリンクするように依頼する、後のＮｏｔｉｆｙメッセージを受信し、ノードＢへのスペアリンクがステップ３１８で選択されると、ステップ３２２で作成される新しいＮｏｔｉｆｙメッセージは、事実上、それ自体からノードＣへのリンクを作成するというノードＢに対する要求である。
【００６７】
リンクが未確認であり、受信側ノードが一定の期間内に（図６を参照して後述されるように、ＬｉｎｋＡｄｄｅｄメッセージを介して）確認を受信しないとき、未確認のリンクが削除される機構も提供されるが、フローチャートには図示されていない。受信側ノードが、依然として「未確認」ステータスを有するリンクを有するときには、それはＬｉｎｋｓＱｕｅｒｙメッセージに応えて（言うまでもなく確認済みのリンクだけではなく）これらの未確認リンクも返し、他のノードが、それがリンクをセットアップしようと試みていることを確認できるようにする。
【００６８】
図３では、ステップ３０５と３０９で「ノー」に出ると、プロセスは終了する。しかしながら所望される場合、それらはステップ３１５で始まる、効率がわずかに改善されて「スペアリンク」プロセスに送ることができる。
【００６９】
ステップ３０９から３１４では、ノードは事実上、主題のリンクの１つを破壊し、それ自体を間に挿入する。フローチャートに図示されていない別の考えられるオプションは、ノードが（言うまでもなくそれがすでに１つのリンクを有していると仮定し）独自のリンクの内の１つを破壊し、主題を間に挿入することであろう。このオプションは、実現される場合、ステップ３０１で「ノー」に出た直後に試されるであろう。最初に、受信側ノードは、主題がＬ−１個より少ないリンクを有していたかどうかを確かめ、無作為に（ノード他に対する）独自のリンクの内の１つを選択し、これを主題に対する未確認リンクで置換し、主題にＡｄｄＬｉｎｋメッセージを送信する必要があるであろう。次に、主題と他の間に双方向リンクを設立するために、それは、（ａ）主題に無条件で他を未確認リンクとしてそのリンクのリストに追加することを要求する特別のＡｄｄＬｉｎｋメッセージを主題に送信し、（ｂ）受信側ノードが旧リンクとして削除され、主題を追加される新規リンクとして指定する特別なＣｈａｎｇｅＬｉｎｋメッセージを他に送信するであろう。このオプションは、ステップ３０９から３１４と同様に、あるいはステップ３０９から３１４の代わりに含まれるであろう。
【００７０】
受信側ノードが独自のリンクの内の１つを破壊するための別のオプションは、（最初に、主題がＬ−１個より少ないリンクを有していたと検証した）それ（受信側ノード）が主題に、それ自体を主題として指定するＮｏｔｉｆｙメッセージを送信することであろう。これは同じ結果をもたらすが、わずかに大きなメッセージングオーバヘッドを必要とするであろう。
【００７１】
図４は、ノードが入信ＣｈａｎｇｅＬｉｎｋメッセージをどのように処理するのかを示している。これらのメッセージは、Ｎｏｔｉｆｙメッセージを受信したノードＸが既存のリンクを２つの新しいリンクに変更することを希望するときに送信される（図２を参照されたい）。受信側ノードＹは、４００でノードＺをｓｕｂｊｅｃｔとするＮｏｔｉｆｙ、つまりノードＹにその既存のノードＺリンクを、ノードＸに置換するように求めるメッセージを受信する。それ（ノードＹ）が事実上ノードＺへのリンクを所有していない（４０２）場合は、それはｓｅｎｄｅｒＸにエラーメッセージを送信する４０３が、それがすでにＸへのリンクを有する場合は、それは追加の処置を講じない（４０１）。
【００７２】
すべてがうまくいくと仮定して、それはｓｅｎｄｅｒＸにＬｉｎｋＱｕｅｒｙメッセージを送信し（４０４）、後者（送信者）が、それが主題リンクを変更する前に作成しなければならなかった２つの新しいリンクを実際に作成したかどうかチェックするために、送信側ノードＸからの応答としてＬｉｎｋｓメッセージを待機する（４０５）。これらのチェック（４０６、４０７）が無事に終了すると、受信側ノードはＺへのリンクを削除し（４０８）、確認されたリンクとしてＸを追加し（４０９）、ＬｉｎｋＡｄｄｅｄメッセージをｓｅｎｄｅｒＸに返す（４１０）。
【００７３】
図５は、ノードが入信ＡｄｄＬｉｎｋメッセージをどのようにして処理するのかを示している。これらのメッセージは、ノードがノードとの新しいリンクの作成を希望するときに送信される（図１を参照されたい）。メッセージは５０１で受信され、ノードはステップ５０２で、それが別のリンクのための空間を有するかどうかをチェックし、ない場合には５０３でエラーメッセージを返す。ある場合には、それはＬｉｎｋｓＱｕｅｒｙメッセージをｓｅｎｄｅｒに送信し（５０４）、送信側ノードからの応答としてＬｉｎｋｓメッセージを待機し（５０５）、その結果それは５０６で後者（送信者）が実際に受信側ノードへのリンクを作成したことをチェックできる。ノーである場合、それはリンクを追加するのを拒否し、終了するが、そうであるならば、それは次にｓｅｎｄｅｒを確認されたリンクとして追加し（５０７）、確認する目的でＬｉｎｋＡｄｄｅｄメッセージをｓｅｎｄｅｒに返す（５０８）。
【００７４】
図６は、ノードが入信ＬｉｎｋＡｄｄｅｄメッセージをどのように処理するのかを示す。これらのメッセージは、ＣｈａｎｇｅＬｉｎｋメッセージまたはＡｄｄＬｉｎｋメッセージのどちらかに応えて、別のノードが受信側ノードへのリンクを受け入れると送信される。リンクが受け入れられたことを示すＬｉｎｋＡｄｄｅｄメッセージが６００で受信されると、そのステータスはステップ６０１で「確認済み」に変更される。それからリンクは、それが（ＣｈａｎｇｅＬｉｎｋメッセージに応えて）新しいリンクのために変更されるのか、あるいはリンクが破壊されるかのどちらかまで維持される。
【００７５】
図７は、ノードが入信ＬｉｎｋＥｒｒｏｒメッセージをどのようにして処理するのかを示す。これらのメッセージは、ノードが受信側ノードへのリンクを、後者が（ＣｈａｎｇｅＬｉｎｋメッセージまたはＡｄｄＬｉｎｋメッセージを手段として）相互リンクを要求した後に作成できなかったとき、あるいはリンクが壊れていると考えられる（他端でのノードがメッセージに応答していない可能性がある、あるいはリンクが相互的ではない可能性がある）ときのどちらかに送信される。壊れたリンクは自己組織化プロセスによってではなく、（後述されるように）クライアントが二次ネットワークを横断するときに検出される。
【００７６】
７００でのメッセージの受信に続き、メッセージが、受信側ノードが未確認リンクを有するノードについてであるかどうかが判断される（７０１）。そうである場合、及びそれが要求されたリンクを作成できなかったことを示すエラーコードを伝搬する（７０２）場合、リンクは７０３で削除される。しかしながら、メッセージが、受信側ノードが未確認リンクを有するノードについてではない場合、受信側ノードはｓｕｂｊｅｃｔにＬｉｎｋＱｕｅｒｙメッセージを送信し（７０４）、応答としてＬｉｎｋｓメッセージを待機し（７０５）、主題がそれ自体にリンクを有するかどうかをチェックするために７０６で応答をチェックし、有さない場合にはステップ７０３で主題ノードに対するそのリンクを削除する。
【００７７】
図８は、ノードが入信ＬｉｎｋｓＱｕｅｒｙメッセージをどのように処理するのかを示す。これらのメッセージは、別のノードが受信側ノードのリンクを知ることを希望するときに送信され、したがって後者（受信側ノード）は８００でその受信時に８０１でＬｉｎｋｓメッセージで応答する。
【００７８】
図９は、ノードが入信Ｌｉｎｋｓメッセージをどのようにして処理するのかを示す。それがどのように処理されるのかは、なぜ対応するＬｉｎｋｓＱｕｅｒｙメッセージが送信されたのかに完全に左右される。これは、とりわけ図３、図４、図５及び図７に示されるようにさまざまな理由から起こる。したがって、何が起こるかというと（ｗｈａｔ ｈａｐｐｅｎｓ）、ＬｉｎｋｓＱｕｅｒｙメッセージが送信されると、それは局所的に一意である基準を与えられ、メッセージハンドラが前記基準に関連付けられる。それから、Ｌｉｎｋｓメッセージが受信されると（９００）、適切なメッセージハンドラが特定され、メッセージは、ステップ９０２でメッセージがただちに処理されるように適切なメッセージハンドラに送られる。
【００７９】
言うまでもなく、例えば受信側ノードが停止していたために、ＬｉｎｋｓＱｕｅｒｙに応えてＬｉｎｋｓメッセージがいままで送信されていない場合がある。したがって、一定の期間後にＬｉｎｋｓメッセージが受信されない場合は、対応するメッセージハンドラは削除される。これはここに説明されるフローチャートのいずれにおいても明示的に示されていないが、それは単にリンク照会が時間切れになると、追加の処置は講じられず、フローチャート全体が「完了した」ことを意味する。
【００８０】
（ノードの取り出し）
二次ネットワークの単一のノードのアドレスを考慮すると、ネットワークの他の、潜在的にはすべてのノードを発見することが可能である。これを行うことができる方法は非常に簡単である。既知のノードにすべてのリンクを要求するためにＬｉｎｋｓＱｕｅｒｒｙメッセージを送信する。ノードは、それがリンクするノードのすべてのアドレスを含むＬｉｎｋｓメッセージで応答する。それから、これらのノードのそれぞれに順々に連絡し、それらのリンクを要求し、このようにしてそれらすべてのリンクのアドレスを得ることができる。このように続けることで、ネットワークを横断し、それが含むすべてのノードを徐々に発見する。
【００８１】
図１０は、プロセスを詳細に示している。これが図１Ａに示されている取り出しステップ３５で使用されるプロセスであることが理解されるであろう。無事に連絡されたすべての既知のノードのアドレスは「確認済み」リストに入れられる。データは同時に取り出されてよい。「ウェブページコメント」例のケースでは、データの関連する項目はコメントのアドレスであり、これもノードアドレスと同時にｃｏｎｆｉｒｍｅｄ（確認済み）リストに入れられる。ｃｏｎｆｉｒｍｅｄ（確認済み）リストは、図１Ａのコメント「取り出し」ステップ（３６）に必要とされるアドレスを提供する。他方、「未確認」リストはまだ連絡を受けていない既知のノードのアドレスを含む。最後に「既知」のリストはすべての既知のノードのアドレスを含んでいる。それは「確認済み」リストと「未確認」リストの中のすべてのアドレスを含んでいるが、連絡されたノード及び応答していないノードのアドレスも含む。ｋｎｏｗｎ（既知の）リストは、それに入れられたアドレスごとに、ソースａｄｄｒｅｓｓ（アドレス）を含む追加フィールド−つまり、エラー報告のために、そのリストからｃｕｒｒｅｎｔ（カレント）ポインタが指すアドレスが取得されたノードのアドレスを有する。
【００８２】
どこで取り出しプロセスが発生するのかは重要ではない。それはノードあるいは他のどこかである可能性がある。ステップ１０００では、ノードアドレスを取り出す要求がｓｔａｒｔ（開始）アドレス、つまり対象とする仮想ネットワークに属すると判断された１つのノードのアドレスとともに受信される。ステップ１００２では、第２のアドレスポインタ、ｓｏｕｒｃｅ（ソース）は当初ヌルである（１００３）が、アドレスポインタｃｕｒｒｅｎｔ（カレント）は当初このアドレスに設定される。
【００８３】
ステップ１００４と１００５では、ＬｉｎｋｓＱｕｅｒｙメッセージは、ｃｕｒｒｅｎｔ（カレント）によって指定されるアドレスに送信され、応答が待機される。Ｌｉｎｋｓメッセージが受信されると、それと並行して、ｃｕｒｒｅｎｔ（カレント）は、Ｌｉｎｋｓメッセージからのコメントアドレスとともにｃｏｎｆｉｒｍｅｄ（確認済み）リストに追加される（ステップ１００６）。
【００８４】
ステップ１００７では、Ｌｉｎｋｓメッセージに含まれるアドレスのそれぞれについて実行されるサブプロセスが入力される。アドレスがすでに既知のリスト内にあると（１００８）、プロセスは次のアドレスに移動する（ｓｔｅｐｓ ｏｎ ｔｏ）。それ以外の場合、アドレスはｋｎｏｗｎ（既知の）リストに、及びｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストに追加される（ステップ１００９、１０１０）。また（１０１１）、ｃｕｒｒｅｎｔ（カレント）のアドレスは追加されたアドレスのソースであるとしてｋｎｏｗｎ（既知の）リストに入力される。
【００８５】
いったんこのサブプロセスが完了すると、（その場合プロセスがステップ１０１２で終了する、ｕｎｃｏｆｉｒｍｅｄ（未確認）リストが空でない限り）ステップ１０１３でｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストから無作為にアドレスが選択される。このアドレスが新しいｃｕｒｒｅｎｔ（カレント）アドレスになり、ｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストから削除される。次のステップ（１０１４）は、それに関連付けられるソースアドレスを取り出すためにｋｎｏｗｎ（既知の）リストの中でｃｕｒｒｅｎｔ（カレント）をルックアップし、これをｓｏｕｒｃｅ（ソース）ポインタに入れることである。無作為選択は必須ではない。例えば、カレントは未確認リスト内の「最も旧い」ノードとして選ぶことができるであろう、あるいはリストは別の基準（例えばノードのアドレス）でソートされ、ｃｕｒｒｅｎｔ（カレント）はつねにこのリストの「最初の」ノードとなることができるであろう。しかしながら、ｃｕｒｒｅｎｔ（カレント）の無作為選択にはその利点がある。それは（特にすべてのノードがつねに取り出されるわけではない場合に）システム内で負荷を拡散し、壊れたリンクがより迅速に発見されるようにネットワークのリンクの試験も拡散する。
【００８６】
それから、プロセスはステップ１００４から再び続行し、ｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストが空になる−つまり、追加の新しいアドレスが見つからなくなる−まで反復する。
【００８７】
取り出しプロセスの思わぬ結果は、それが壊れたリンクを発見することである。例えば、ノードが応答していない、あるいはリンクが相互的ではない場合がある。後者は、ノードＡがノードＢにリンクするが、ノードＢがそのリンクテーブルにノードＡを入れていないケースである。壊れたリンクが発見されると、前記リンクの「ソース」であるノードはＬｉｎｋＥｒｒｏｒメッセージを手段として通知される。図７がすでに示していたように、ソースノードは、次に（エラーレポートの精度を確認するために）リンク自体をチェックすることができ、結果としてリンクを削除する場合がある。応答していないノードは、設定されたタイムアウト期間内にＬｉｎｋｓメッセージを受信できないことによってステップ１００５で認識され、ステップ１０１５では、ｃｕｒｒｅｎｔ（カレント）のアドレスと「応答なし」エラーコードを含むエラーメッセージがｓｏｕｒｃｅ（ソース）に送信され、その結果制御はステップ１０１２に戻る。リンクの相互性の欠如（ｎｏｎ−ｍｕｔｕａｌｉｔｙ）は、ｃｕｒｒｅｎｔ（カレント）について受信されたＬｉｎｋｓメッセージがｓｏｕｒｃｅ（ソース）のアドレスを含んでいるかどうかを判断するためにステップ１０１６での試験によって認識される。含んでいない場合、ｃｕｒｒｅｎｔ（カレント）のアドレス及び「非相互的」エラーコードを含むエラーメッセージがｓｏｕｒｃｅ（ソース）に送信される（ステップ１０１７）が、（図７のプロセスに従って）救済処置を講じるのはソースノードの責任であるため、取り出しプロセスは以前のように続行する。ステップ１１０６での試験は、ｓｏｕｒｃｅ（ソース）がヌルである場合には省略される。
【００８８】
複数の確認済みノードが、Ｌｉｎｋｓメッセージに応答しないノードにリンクするとしても、最初にリンクに貢献したノード（ソースノード）だけが、「応答なし」であったことを通知されることに注意されたい。これは、部分的には、その方がフローチャートを理解しやすいためである。しかしながら、別の実際的な利点があると主張することができる。ノードは、それが一時的にオーバロードされているために（時間内に）応答しない可能性がある。この場合、（図７でのように）エラーがあるかどうかを試験するために、複数のノードにＬｉｎｋｓＱｕｅｒｙメッセージを同時に送信してほしくない場合がある。いずれにせよ、所望される場合、壊れたリンクにより影響を受けるすべての既知のノードに、このようなリンクが発見されると通知するようにノード取り出しアルゴリズムを更新することは分かりやすい。
【００８９】
図１０では、ノード取り出しは、すべての既知のノードが連絡を受けるまで停止しない。実際には、プロセスを早期に終了することを希望する場合がある。例えば、ユーザがファイルをそこからダウンロードする場所を探している場合、例えばすべて、１０００の代わりに１０の可能性のあるダウンロードアドレスの選択肢をユーザに提供することで十分である可能性がある。
【００９０】
図１０のアルゴリズムは完全にシリアルとして示されている。一度に１つのノードだけが連絡される。別のＬｉｎｋｓＱｕｅｒｙメッセージは、過去のメッセージに対する応答が受信された（あるいはそれが時間切れになった）後にのみ送信される。しかしながら、実際には、我々は複数のＬｉｎｋｓＱｕｅｒｙメッセージを同時に発行することにより取り出しを加速することを好む。ボックス１０００では、複数の取り出し要求が図１０のプロセスの複数のインスタンスによって同時に処理される場合がある。
【００９１】
（説明）
（自己組織化の成功）
二次仮想ネットワークの目的とは、複数の接続されていないネットワークとは対照的に単一のネットワークの中にともにグループ化されなければならないすべてのノードを自己組織化することである。これが当てはまるかどうかは、初期のＮｏｔｉｆｙメッセージがどのように作成されるのかに負うところが大きい。例えば、すべてともにグループ化されなければならない１２のノードのグループがあるが、このグループの内、５つのノードだけが５つのこのグループ内の他のノードについて通知を受信し、他の７つのノードのどれもこれらの５つのノードのどれかについて通知されない場合、ノードが単一のネットワークに自己組織化することは不可能である。代わりに、それらは、５つのノードの１つと７つのノードの１つという２つの別々のネットワークに配置される（ａｒｒａｎｇｅ ｉｎｔｏ）。しかしながら、初期通知が、ノードが単一のネットワークに自己組織化することが不可能でないようであれば、自己組織化のプロセスは、ノードが単一のネットワークに自己組織化しない可能性がきわめて低いほどである。自己組織化の結果単一ネットワークが生じる確率の計算は複雑であり、初期通知を作成する機構に左右される。しかしながら、我々はシミュレーションで複数の異なる初期通知機構を経験し、これまでノードが単一のネットワークに自己組織化することができなかったことはない。
【００９２】
（悪意のあるノードに対するロバスト性）
これまで、すべてのノードはプロトコルに従うと仮定されてきた。しかしながら、ルールに従って行動しない悪意のあるノードがいる可能性がある。それらは、他のノードによって維持されているリンクを破壊しようとする、及び／あるいはそれら自体に多すぎるリンクを取得しようとする。全体的なシステムがこのような悪用に対し可能な限りロバストであることが望ましい。
【００９３】
これまで説明されてきたシステムは悪意のあるノードに対してすでにかなりロバストである。それは、各ノードが、自身のリンクを変更する前に、つねにＬｉｎｋｓＱｕｅｒｙ−Ｌｉｎｋｓメッセージ交換を用いて他の関連性のあるノードによって維持されるリンクをチェックするためである。例えば、ノードがＡｄｄＬｉｎｋメッセージを受信するとき（図３を参照されたい）、それは、自身のリンクとして送信者を追加する前に、最初に、送信側ノードが実際にそれにリンクしたかどうかをチェックする。
【００９４】
しかしながら、システムには依然として相対的な弱さがある。現状では、ノードは、それらがＬｉｎｋｓメッセージで応答するときに容易に「ウソをつく」ことができる。多くの場合、ノードは受信側ノードがそれにリンクしていることをチェックするためにＬｉｎｋｓＱｕｅｒｙメッセージを送信する。受信側ノードは、このことを知っているので、それがつねにリンクとしてＬｉｎｋｓメッセージの送信者を含むように修正された捏造Ｌｉｎｋｓメッセージで応答できる。これにより、ノードはそれにリンクするＬ個のノードという許容数よりはるかに多いノードを有することができる。結果として、これはシステム内の「よい」リンクの総数を削減するであろう。
【００９５】
幸いなことに、この弱さに対処する方法がある。これは、ノードがプロキシノードを通してそれらのＬｉｎｋｓＱｕｅｒｙを送信する場合に行うことができる。これらのプロキシは、ノードが照会を送信することを希望するたびに無作為に選ばれる。各ノードは、例えば、それが現在リンクしているノードをプロキシとして使用できる。このようにして、別のノード（Ｂ）のリンクを知ることを希望するノード（Ａ）は、それ（ノードＢ）が受信するＬｉｎｋｓＱｕｅｒｙメッセージがプロキシノード（Ｃ）からであり、ノードＢがノードＣから受信するメッセージはまったくノードＡを参照しないため、ノードＢにとっては未知である。したがって、ノードＢが全体的なシステムに重大な影響を及ぼす捏造メッセージを送信する手っ取り早い方法はない。
【００９６】
言うまでもなく、悪意のあるプロキシの影響はどのようなものであるかに関する疑問がある。明らかに悪意のあるプロキシは有害な影響を及ぼすが（プロトコルに従わないノードがパフォーマンスにある程度影響を与えるのは避けられない）、この影響は限られている。その理由は、それらが不当に処理できるのは、それらが転送するように依頼されるＬｉｎｋｓＱｕｅｒｙだけであり、これらの要求はすべてのノード全体でだいたい均一に拡散されるためである。他方、プロキシが使用されないときには、悪意のあるノードは非常にアクティブであることによる大混乱を引き起こすことがある。これらのノードが多くの偽のＡｄｄＬｉｎｋメッセージを送信し、それらが実質的に送信する多くのＬｉｎｋｓメッセージを捏造すると、全体的なシステムに及ぼされる影響ははるかに大きくなる。
【００９７】
（一次仮想ネットワーク）
一次ネットワークは、我々の前述された国際特許出願に詳しく説明されている。ここでは、二次ネットワークの自己組織化を促進するＮｏｔｉｆｙメッセージの作成を可能にする改善策とともに、基本的な取り出し機構と自己組織化機構が説明される。
【００９８】
最初に、この機構によって使用される仮想座標空間の概念を説明することが必要である。各ノードがラベルを有することはすでに言及された。ラベルは仮想空間で座標に変換される。空間は一次元、二次元またはさらに高い次元である場合がある。正確な変換機構はあまり重大ではない。つまり一次元空間の場合、バイナリ数と見なされるラベルは座標として直接的に使用できる。二次元及び三次元以上の場合、好ましい方法では、ビットの文字列として見なされるラベルが２つまたは３つ以上の等しいグループに区分され、バイナリ数と見なされる各グループが座標の１つを形成する。各座標（つまり、一次元空間での前記座標）は範囲［０，１］にあるように拡大縮小される。
【００９９】
所望される場合、（多くの場合マンハッタン距離と呼ばれる）都市ブロック距離のような他の距離が使用できるであろうが、この仮想空間の２つのラベルの間の距離が、２つの座標集合の間のユークリッド距離である。座標空間は、ｘ1とｘ2の間のｘ方向の距離が
Ｍｉｎ｛（１−｜ｘ1−ｘ2｜），｜ｘ1−ｘ2｜｝
となるように重なり（ｗｒａｐｓ）、したがって点（ｘ1，ｙ1）と（ｘ2，ｙ2）の間の二次元のユークリッド距離は、
【数１】
【０１００】
である。
【０１０１】
我々は、この点で各ノードが、多くのエントリが他のノードへのリンクを表すリスト２２（図１）を有することも思い出す。各エントリは、このような別のノードのラベルとアドレスから構成される。当初、このリストは空であるため、ノードは、ブートストラップリンク−すなわちそれがネットワークの他のノードに最初に連絡できるように２、３のリンク（通常は４つ）−の第２の類似したリストを有する。ノードは（短距離リンクと呼ばれる）リスト２２の中のリンクだけではなく、階層的に配列された追加のこのようなリスト、及び／または長距離リンクのリストも有する場合がある。これらは、我々の初期の国際特許出願に説明されているが、それらは付加的であるため、ここでは説明されない。
【０１０２】
（メッセージ）
最初に、以下のメッセージが使用される（一次仮想ネットワークで使用されるメッセージが二次仮想ネットワークで使用されるメッセージとは異なり、二次仮想ネットワークで使用されるメッセージから完全に独立していることに注意する）。
【０１０３】
ＦＩＮＤメッセージは、ノードルックアップを起動し、実行するため、及び「ＰＵＬＬ（プル）」更新をサポートするために使用される。それらは、
・ターゲットノードのラベル
・照会を開始したノードのアドレス
を含む。
【０１０４】
ＦＯＵＮＤメッセージは照会の結果を返すために使用される。それらは、
・ターゲットノードのラベル
・発見されたノードのラベル
・発見されたノードのアドレス
・発見されたノードと関連付けられる二次ネットワークのノードのアドレス
・アプリケーション特有データ−このケースでは、発見されたノードと関連付けられるコメントノードのアドレス
ＰＵＳＨ（プッシュ）メッセージは、ノードのラベルを他のノードに宣伝する。それらは、
・主題ノードのラベル
・主題ノードのアドレス
・ターゲットノードに到達するためのｈｏｐｓ ｔｏ ｇｏ（移動ホップ）数
ＮＯＴＩＦＹメッセージはプッシュ−更新を伝搬するために使用される。それらは、
・主題ノードのラベル
・主題ノードのアドレス
を含む。
【０１０５】
（取り出し）
図１１は、各ノードが入信Ｆｉｎｄメッセージをどのようにして処理するのかを示している。原則的には、受信側ノードはそれ自体よりＦｉｎｄメッセージで特定されたターゲットノードにより近いノードを探し、成功した場合はＦｉｎｄメッセージを次へ回す。成功しない場合、それは独自のアドレスとラベルを返す。それは、以下のステップを実行することによってこれを行う。
【０１０６】
ステップ１１００：ノードは、ターゲットノードのラベルと開始側ノードのアドレスを含むＦｉｎｄメッセージを受信する。
【０１０７】
ステップ１１０５：ノードはターゲットノードのラベルをラベル空間の座標に変換し、それが記録しているすべてのリンク（ノード）の内で、どれがラベル空間内のターゲットノードに最も近いのかを計算する。当該ノードはｎｅａｒｅｓｔノードと指定される。
【０１０８】
ステップ１１１０：ノードは自身の座標とターゲットノードの座標の間の距離を、ｎｅａｒｅｓｔノードの座標とターゲットノードの座標の間の距離に比較する。
【０１０９】
ステップ１１１５：自身の座標とターゲットノードの座標の間の距離が少ない（あるいは等しい）場合、ノードは開始側ノードにネットワーク１０を介して、自身のラベルとアドレスを含んだＦｏｕｎｄメッセージを送信する。
【０１１０】
ステップ１１２０：ｎｅａｒｅｓｔノードの座標とターゲットノードの座標の間の距離が少ない場合、ノードはＦｉｎｄメッセージをｎｅａｒｅｓｔノードに転送する。
【０１１１】
ステップ１１１５で返されるノードのアドレスはターゲットラベルが付いたノードのアドレス、またはラベル空間内でそれに近いもののどちらかである。返されるラベルがターゲットラベルに一致しないときは、それはターゲットノードが存在していない、または仮想ネットワークが十分に自己組織化されていないかのどちらかを意味する。
【０１１２】
（プッシュ）
各ノードはＰｕｓｈ（プッシュ）更新を自発的に開始する。例えば、各ノードは定期的にＰｕｓｈ（プッシュ）更新プロセスを開始する可能性がある。Ｐｕｓｈ（プッシュ）更新では、ノードはノードの無作為系列（ｒａｎｄｏｍ ｓｅｒｉｅｓ）を通して自身のラベルとアドレスとともにＰｕｓｈ（プッシュ）メッセージを送出し、系列の長さに制限を設定する。系列の中の最後のノードは開始側ノードに向かってＮｏｔｉｆｙメッセージを送り返す。図１２、図１３、及び図１４はこのプロセスの多用な部分を示している。
【０１１３】
図１２は、以下のステップを使用してノードがどのようにしてＰｕｓｈ（プッシュ）更新を開始するのかを示す。
【０１１４】
ステップ１２００：ノードはそのブートストラップリンクの中から無作為にリンクを選択し、選択されたリンクによって特定されるノードのアドレスを次のメッセージのｆｏｒｗａｒｄ（転送）アドレスとして入力する。
【０１１５】
ステップ１２０５：ノードはＰｕｓｈ（プッシュ）メッセージのフィールドｈｏｐｓ ｔｏ ｇｏ（移動ホップ）に小さい正の乱数を入力する。
【０１１６】
ステップ１２１０：ノードは自身のラベルとアドレスをＰｕｓｈ（プッシュ）メッセージの中のｓｕｂｊｅｃｔノードのラベルとアドレスとして入力し、ネットワーク１０を使用して、Ｐｕｓｈ（プッシュ）メッセージをｆｏｒｗａｒｄ（転送）アドレスにあるノードに送信する。
【０１１７】
図１３及び図１４は、短距離リンクがどのようにして更新されるのかを示している。Ｐｕｓｈ（プッシュ）メッセージは、短距離リンクを更新するためにＮｏｔｉｆｙメッセージとともに使用される。この更新には２つの段階がある。第１の段階では、各ノードは、受信されるようなメッセージの移動ホップ（ｈｏｐｓ ｔｏ ｇｏ）の値が「０」になるまでＰｕｓｈ（プッシュ）メッセージを無作為に転送する。移動ホップ（ｈｏｐｓ ｔｏ ｇｏ）の値が「０」である場合、受信側ノードはＮｏｔｉｆｙメッセージを送信することによってＰｕｓｈ（プッシュ）更新の第２段階を開始する。第２段階では、Ｎｏｔｉｆｙメッセージは、そのラベルが漸次的に仮想空間の主題に近くなるノードに連続して転送される。より近いラベルをもつノードが発見されない場合、必要に応じ、最後に発見されたノードのリンクが更新される。これは、例えば、それがまだ確立されていない短距離リンクを有していないためなど、それ以外の場合それが特定の主題ノードを発見できないときにつねに当てはまる。また最後に発見されたノードは、潜在的にそのリンク集合も改善できるであろうノードに追加のＮｏｔｉｆｙメッセージを送信する。
【０１１８】
図１３のＰｕｓｈ（プッシュ）更新の第１の段階を参照すると、入信Ｐｕｓｈ（プッシュ）メッセージを処理するには以下のステップが必要となる。
【０１１９】
ステップ１３００：ノードはＰｕｓｈ（プッシュ）メッセージを受信する。Ｐｕｓｈ（プッシュ）メッセージは、開始側ノードのラベルとアドレスをｓｕｂｊｅｃｔノードとして含み、フィールドｈｏｐｓ ｔｏ ｇｏ（移動ホップ）に値を有する。
【０１２０】
ステップ１３０５：受信側ノードはそのブートストラップリンクの中からリンクを無作為に選択し、選択されたリンクによって特定されるノードのアドレスを次のメッセージのｆｏｒｗａｒｄ（転送）アドレスとして入力する。
【０１２１】
ステップ１３１０と１３１５：受信側ノードはフィールドｈｏｐｓ ｔｏ ｇｏ（移動ホップ）の値を１だけ減少させ、ｈｏｐｓ ｔｏ ｇｏ（移動ホップ）の減少した値が依然としてゼロより大きいかどうかをチェックする。
【０１２２】
ステップ１３２０：減少した値が依然としてゼロより大きい場合、ノードはＰｕｓｈ（プッシュ）メッセージをそれが入力したｆｏｒｗａｒｄ（転送）アドレスに転送する。
【０１２３】
ステップ１３２５：値がゼロである場合、ノードは、代わりに、（受信されたＰｕｓｈ（プッシュ）メッセージに指定される）開始側ノードのラベルとアドレスをＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔ（主題ノード）として入力し、それが入力したｆｏｒｗａｒｄ（転送）アドレスにＮｏｔｉｆｙメッセージを送信する。
【０１２４】
図１４を参照すると、Ｐｕｓｈ（プッシュ）更新を処理し、Ｎｏｔｉｆｙメッセージを処理する第２の段階は以下のステップを伴なう。
【０１２５】
ステップ１４００：ノードは、ｓｕｂｊｅｃｔノードとしてノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを受信する。
【０１２６】
ステップ１４０１：受信側ノードは、Ｎｏｔｉｆｙメッセージのｓｕｂｊｅｃｔが受信側ノードと同じラベルを有するかどうかをチェックする。
【０１２７】
ステップ１４０２：そうである場合は、受信側ノードはＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔが受信側ノードと同じアドレスを有するかどうかをチェックする。その場合、それは追加の処置を講じない。
【０１２８】
しかしながらＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔが受信側ノードと同じラベルの付いているが、受信側ノードとは異なるアドレスのノードである場合、２つのイベントが発生する。第１に（ステップ１４０３）受信側ノードは入信Ｎｏｔｉｆｙ（通信）メッセージの主題ノードに、主題として受信側ノードの自身の短距離リンクのリストから無作為に選ばれたノードを指定するＮｏｔｉｆｙメッセージを送信する。第２に、ステップ１４０４は、二次ネットワークによる動作のためにＮｏｔｉｆｙ（通知）メッセージを作成させる。しかしながら、受信側ノードはこのようなメッセージを直接的に作成することはできない。一般的には、通信網上での異なる仮想ネットワーク間でメッセージを送信するのを回避することが好まれるが、主要な問題は受信側ノードが二次ネットワークのそれ自体のノードのアドレスだけではなく、ｓｕｂｊｅｃｔノードに関連する二次ノードのノードアドレスも必要とするという点である。受信側ノードはこのアドレスを持っていない。したがって、２段階プロセスが使用される。
【０１２９】
第１に、受信側ノードは、入信Ｎｏｔｉｆｙメッセージの中の主題として指定される特別な一次ネットワークのノードにＣｒｏｓｓＮｏｔｉｆｙメッセージを送信する。このメッセージは以下のものを含む。
【０１３０】
・受信側ノード（つまり、入信（一次ネットワーク）メッセージを受信したノード）のアドレスに設定されたｓｅｎｄｅｒアドレス
・入信Ｎｏｔｉｆｙメッセージに含まれるアドレスに設定されたｒｅｃｅｉｖｅｒ（つまり宛て先）アドレス
・受信側ノードと関連付けられる二次ネットワークのノードのアドレスに設定されるｓｕｂｊｅｃｔアドレス
最初の２つのアドレスが一次ネットワーク上のノードのアドレスであり、第３のアドレスが二次ネットワーク上のノードのアドレスであることに注意する。
【０１３１】
第２に、ＣｒｏｓｓＮｏｔｉｆｙメッセージを受信する一次ネットワークのノードは、実質的には、それを二次ネットワークの関連するノードに転送する。必要ならば、転送側ノードはメッセージを二次ネットワークで使用されているフォーマットにフォーマットし直し、（一次ネットワーク）ｒｅｃｅｉｖｅｒアドレスを二次ネットワークの関連するノードのアドレスで置換できるであろう。メッセージは、それから、まさに図３に示されているように処理されるであろう。我々が「実質的には」という理由は、実際には、ＣｒｏｓｓＮｏｔｉｆｙメッセージを受信する一次ネットワークのノードだけが二次ネットワークのその関連するノードに、ＣｒｏｓｓＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔフィールドに指定されるアドレスを含む簡略で局所的なメッセージを送信することが好まれるからである。その場合、図３のプロセスは、ｎｏｔｉｆｙｌｅｖｅｌを適切な値に設定するステップを含むように修正されるであろう。
【０１３２】
このプロセスは、ボックスがノードを表し、矢印がメッセージを表す図１５を参照して例によって図解される。一次ネットワークのノードＰ１が、図１４のステップ１４００で、一次ネットワークのノードＰ２のラベルＬP2とアドレスＡP2をｓｕｂｊｅｃｔとして含むＮｏｔｉｆｙ（通知メッセージ）を受信すると仮定する。ノードＰ１では、主題ノードがＰ１と同じラベルを有する（つまりＬP1＝ＬP2）が、別のアドレス（ＡP1≠ＡP2）を有することが認識される（図１４のステップ１４０１、１４０２）。ノードＰ１は、その二次ネットワークノードＳ１のアドレスＡS1を知っており、（図１４のステップ１４０４で）送信者アドレスＡP1、受信者アドレスＡP2、及び主題アドレスＡS1でＣｒｏｓｓＮｏｔｉｆｙメッセージを作成する。このメッセージは一次ネットワークのノードＰ２で受信され、これは、アドレスＡS1で局所通知メッセージを二次ネットワークの関連するノードＳ２に送信する。代わりに、二次ネットワークのノードＳ２は、ＬｏｃａｌＮｏｔｉｆｙメッセージの受信時に、図３のプロセスに従ってそれ自体リンクを作成する代わりに、それがノードＳ１に送信し、それ自体を主題として指定する（図１２の点線によって示される）（二次ネットワークの）追加のＮｏｔｉｆｙメッセージを作成できるであろう。Ｎｏｔｉｆｙメッセージは、それから、図３のプロセスを使用するノードＳ１で処理される。このオプションは追加のメッセージを必要とするが、図３のプロセスが実行されるようになると、Ｎｏｔｉｆｙメッセージが、そのアドレスがメッセージのｓｕｂｊｅｃｔフィールド内にあるノードによって実際に送信され、ｓｕｂｊｅｃｔノードがこのようにして依然として存在しているとして本質的に確認されるという利点を有する。
【０１３３】
いま図１４ステップ、１４０５に戻ると受信側ノードはｓｕｂｊｅｃｔノードのラベルを座標に変換し、それが記録した短距離リンクの内のどれが、その座標が仮想空間内のｓｕｂｊｅｃｔノードの座標にもっとも近いノードラベルにつながるのかを計算する。当該ノードはｎｅａｒｅｓｔノードと指定される。
【０１３４】
ステップ１４１５：受信側ノードは自身の座標とｓｕｂｊｅｃｔノードの座標の間の距離を、ｎｅａｒｅｓｔノードの座標とｓｕｂｊｅｃｔノードの座標の間の距離と比較する。
【０１３５】
ステップ１４１５では、受信側ノードとｓｕｂｊｅｃｔノードの間の距離が同じまたは少ないことが判明すると、受信側ノードはｓｕｂｊｅｃｔノードのラベルとアドレスを自身の短距離リンク集合（（ステップ１４２０）。このプロセスは、図１６を参照してさらに説明される）の中のリンクとして追加し、ｓｕｂｊｅｃｔノードに受信側ノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを送信し（ステップ（１４３０）、ｎｅａｒｅｓｔノードに、ｓｕｂｊｅｃｔのノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを送信する（ステップ１４３５）。
【０１３６】
ステップ１４１５で、最も近いノードとｓｕｂｊｅｃｔノードの間の距離がより大きいと判明すると、受信側ノードは、それがｎｅａｒｅｓｔノードにｓｕｂｊｅｃｔノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを送信するという点でステップ１４３５に戻る。
【０１３７】
図１６は、ノードが、その短距離リンクを更新するときにどのように動作するのかを詳細に示している。それは新しいリンクをその短距離リンクに追加し、このリンクに代わられるすべての短距離リンクを削除する。
【０１３８】
図１６を参照すると、例えば図１４のステップ１４２０の結果として、ノードは新しいリンクをその短距離リンクに追加する必要がある。
【０１３９】
ステップ１６００：更新ノード（すなわち、その短距離リンク集合に対して更新を行うノード）は、新しいリンクのためのノードのアドレスを有する。
【０１４０】
ステップ１６００：更新ノードは、更新ノードに対してより新しいノードにさらに近いノードに関するすべての既存のリンクを特定する。これらの特定されたリンクは入れ替えられなければならない。これらのリンクを特定するために更新ノードは、各既存のリンクに、新しいノードの座標とその既存のリンクで指定されるノードの座標の間の距離を計算する。それは、これらの距離のそれぞれを自身の座標とそれぞれの既存のリストに指定されるノードの座標の間の距離と比較する。
【０１４１】
ステップ１６１０：新しいノードに関する距離が更新ノードに関する距離より短いすべてのリンクは短距離リンクから削除される。
【０１４２】
ステップ１６２０：更新ノードは、その短距離リンクに新しいノードのためのリンクを追加する。
【図面の簡単な説明】
【０１４３】
【図１】本発明のある実施形態で使用されるコンピュータのブロック図である。
【図１Ａ】一次仮想ネットワークと二次仮想ネットワークを使用するデータ検索動作を示すフローチャートである。
【図２】コンピュータネットワークのノード間のリンクの管理の概略図である。
【図３】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図４】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図５】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図６】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図７】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図８】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図９】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１０】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１１】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１２】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１３】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１４】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１５】図１４に描かれているプロセスの間のメッセージの流れを描く概略図である。
【図１６】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【技術分野】
【０００１】
本発明は仮想ネットワークに関し、特に集中記憶装置または制御装置を備えないものなど、ピアツーピアシステムなどの分散型システムに関するが、それに限定されない。
【発明の開示】
【課題を解決するための手段】
【０００２】
本発明のある態様によれば、各ノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを有する複数のノードを有する仮想ネットワークを操作する方法が提供され、
（ｉ）第１のノードと第２のノードの間のリンクを要求するメッセージを受信することと、
（ｉｉ）第１のノードと第２のノードの両方が、それぞれのケースでそのリスト内に所定数未満であるいくつかのアドレスを有するかどうかを判断することと、
（ｉｉｉ）この条件が満たされる場合には、第１のノードのアドレスを第２のノードのリストに挿入し、第２のノードのアドレスを第１のノードのリストの中に挿入することと、
（ｉｖ）この条件が満たされない場合には、第１のノードがそのリストの中に前記所定数より少なくとも２少ないいくつかのアドレスを有するかどうかを判断し、そうである場合には、
（ａ）第３のノードのアドレスを第２のノードのリストから選択することと、
（ｂ）第３のノードのアドレスを第２のノードのリストから削除することと、
（ｃ）第２のノードのアドレスを第３のノードのリストから削除することと、
（ｄ）第２のノードのアドレスを第１のノードのリストに挿入し、第３のノードのアドレスを第１のノードのリストに挿入することと、
（ｅ）第１のノードのアドレスを第２のノードのリストに挿入し、第１のノードのアドレスを第３のノードのリストに挿入することと、
を含む。
【０００３】
別の態様では、本発明は仮想ネットワークのノードを提供し、前記ノードは他のこのようなノードの所定数のアドレスまでを記憶するためのリストを含む記憶手段と、以下の動作、つまり
メッセージを受信することと、
リストの内容についての情報を要求するメッセージに応えることと、
リストからアドレスを削除するために受信した要求に従うことと、
リストへのアドレスの挿入を要求するメッセージに従うことと、
ノードと第２のノード間のリンクを要求するメッセージの受信に応えて、
（Ａ）そのリストの内容についての情報を要求する第２のノードに対するメッセージを作成することと、
（Ｂ）第１のノードと第２のノードの両方が、それぞれのケースで、そのリストに所定数未満であるいくつかのアドレスを有するかどうかを判断することと、
（Ｃ）この条件が満たされる場合、第２のノードのアドレスをそのリストに挿入し、そのリストにノードのアドレスを追加するように第２のノードに要求するメッセージを第２のノードに対して作成することと、
（Ｄ）この条件が満たされない場合には、ノードがそのリストに、所定数より少なくとも２少ないいくつかのアドレスを有するかどうかを判断することと、そうである場合に、
（ａ）第３のノードのアドレスを第２のノードのリストから選択することと、
（ｂ）第２のノードのアドレスを第１のノードのリストに挿入し、第３のノードのアドレスを第１のノードのリストに挿入することと、
（ｃ）第２のノードのリストからの第３のノードアドレスの削除、及びノードのアドレスの挿入を要求するメッセージを第２のノードに作成することと、
（ｄ）第３のノードのリストからの第２のノードのアドレスの削除、及びノードのアドレスの挿入を要求するメッセージを第３のノードに作成することと、
を実行するようにプログラミングされる処理手段によって定められる。
【０００４】
本発明の他の好ましい態様は請求項に定められる。
【０００５】
本発明のいくつかの実施形態は、以下、添付図面を参照して一例として説明する。
【発明を実施するための最良の形態】
【０００６】
（ノード）
本説明中、処理機能、記憶機能及び通信機能を有するコンピューティングノードについて言及する。コンピューティングノードは、１台のコンピュータでも、他のデバイスでもよく、あるいは−単一のコンピュータがその上で実行するいくつかの独立したプログラムまたはプロセスを有することができることに注意すると−このようなプログラムまたはプロセスであってよい。記憶されるデータの項目は、いくつかのこのような項目は単一のプログラムまたはプロセスによってサービスを受けてよいが、別個のノードとして見なされてもよい。
【０００７】
本説明は、各コンピューティングノードが、メッセージがそれに送信できるようなＩＰ（インターネットプロトコル）ネットワークのような電気通信網など、なんらかの通信インフラストラクチャに接続されていることを前提とする。したがって、各コンピューティングノードは通信インフラストラクチャ内のノードも構成する。
【０００８】
また、仮想ネットワークに属する仮想ノードに対しても述べる。コンピューティングノードはそれに関連付けられる（おそらくは異なる仮想ネットワークに属する）２つまたは３つの仮想ノードを有することができるため、区別は重要である。その名が暗示するように、仮想ノードはいかなる物理的な意味でも存在しない。むしろやがて明らかになるように、その存在は、仮想ノードの間のリンクを定義し、したがってそれが属する仮想ネットワークも定義する記憶されているデータにより確立される。
【０００９】
必然的に、仮想ノードは、それに処理機能、記憶機能、及び通信機能を与えるコンピューティングノードと関連付けられなければならない。つまり仮想ノードによるメッセージの送信、受信及び処理に対する参照は、仮想ノードの代わりにコンピューティングノードによるこのような送信、受信または処理を参照する。
【００１０】
例は図１に図示されている。コンピュータは、ネットワーク１０を介する通信のために通常の構成要素、すなわちプロセッサ１、メモリ２、ディスプレイ３、キーボード４及び通信インタフェース５を有する。
【００１１】
メモリ２は、オペレーティングシステムと他のプログラム（図示せず）、及び図示されているテキストファイル２０などのデータファイルを格納している。それは、テキストファイル２０とそれ自体のアドレス２１ｂに対応するラベル２１ａを含む２１も有する。さらに、それはアドレスリスト２２、及びコンピュータ上で仮想ネットワークのノードの存在をともに定義するサポートプログラム２３を有する。このノードにはアドレス２４が付いている。別の仮想ネットワークのノードの、コンピュータ上での存在をともに定義するアドレスリスト２５及びサポートプログラム２６も図示されている。このノードにはアドレス２７が付いている。リスト２２、２５に記憶されているアドレスは、同じ仮想ネットワーク内の他のノードのアドレスである。
【００１２】
（ルックアップシステム）
これは本発明の応用例の考えられる１つの例でしかありえないが、ここで分散型ルックアップシステムを説明する。このシステムによってユーザはコメントをウェブページと関連付けることができる。ユーザはこのページをビジットするたびに、他のユーザが行ったコメントを見る機会もある。コメントは、（例えばテキストファイルとして）コメントを寄せたユーザのコンピュータに記憶されている。
【００１３】
ウェブページ（またはむしろ、自分のコンピュータ）を見ているユーザは、ウェブページのユニバーサルリソースロケータ（ＵＲＬ）を有し、必要とされているのはユーザがコメントを取り出すことができる機構である。この例では、前記機構は以下のとおりである。
【００１４】
他のウェブページについてのコメントを含む他のテキストファイル、及びおそらく他の関連していないファイルもそうである可能性があるように、テキストファイルはコメントを寄せたユーザのコンピュータに記憶され、我々の国際特許出願ＷＯ第０３／０３４６６９号［代理人参照第Ａ３００４４号］に説明される方の仮想ネットワークのノードと関連付けられている。（本説明の文脈では一次仮想ネットワーク、または単に一次ネットワークと呼ばれる）この仮想ネットワークは、それを特定するラベルを有するのであればそのアドレスを知らなくてもノードにメッセージを送信できるようにするのに役立つ。その種のネットワークは一意のラベル（ノードあたり１つ）で機能できるが、この例ではラベルは一意ではない。むしろ、ある特定のウェブページについてのコメントを含むテキストファイルに関連付けられるすべてのノードが同じラベルを有する。このラベルはウェブページのＵＲＬのハッシュ関数である。この仮想ネットワークは、ただ１つのノードに到達する取り出し機構を提供する。
【００１５】
テキストファイルは、第２の仮想ネットワークのノードとも関連付けられる。これ（二次仮想ネットワーク）は前記１つの特定のウェブページについてのコメントを含むテキストファイルと関連付けられているノードだけを含む。
【００１６】
しかしながら、我々の前述された国際特許出願による一次ネットワークの使用が好ましいが、それが必須ではないことに注意する。事実上、仮想ネットワークを使用することはまったく必須ではない。ラベルを受信し、それに対応する１つのノードのアドレスを返す別の一次取り出し機構が代わりに使用できるであろう。
【００１７】
コメントをポストするコンピュータは図１に図示されるとおりであり、
・一次ネットワーク内でノードを作成しなければならない。このノードはラベル２１ａ及びネットワークアドレス２４を有している。
【００１８】
・二次ネットワーク内でノードを作成しなければならない。このノードにはネットワークアドレス２７が付いている。
【００１９】
当初、アドレスリスト２２、２５は、リスト２２がブートストラップリンクを含んでいるのを除き、空である。リスト２２が一次ネットワークのいくつかの他のノードのラベルとアドレスを含み、リスト２５が二次ネットワークのいくつかの他のノードのアドレスを含むことを確実にするためのネットワークの自己組織化については、後述する。まず当分は、システムはこれらのラベルとアドレスが存在しているという仮定に基づいて説明する。
【００２０】
この時点でアドレスについて少し説明することが必要である。テキストファイル２０によって形成されるノード、一次仮想ネットワークのノード、及び二次仮想ネットワークのノードは、概念上はただ１つのアイデンティティを有しているが、独自のアドレスを有している。実際問題としてはこれは特に便利ではないが、それぞれのノードに通信網１０内の異なるアドレスを割り当てることが可能であろう。我々の好ましいインプリメンテーションでは、各ノードは以下の３つの部分から構成されるアドレスを有する。
【００２１】
・コンピューティングノードの場所を指定するインターネットアドレス。例えば、１３０．１４６．２０９．１５
・コンピューティングノードにおけるある特定の通信ポートの場所を指定するポート番号。ポートはインターネットアドレスの標準的な部分である。例えば、それらは異なる独立したアプリケーションプログラムがメッセージを独立して送信、受信できるようにする。つまり、それぞれが専用のポートでメッセージを受信し、他のアプリケーションプログラム向けのメッセージは受信しない、あるいは他のアプリケーションプログラム向けのメッセージによって「混乱」しないであろう。ポート番号とともにインターネットアドレスは、（使用されるＴＣＰ／ＩＰなどの通信プロトコルの一部であるため）ネットワークアドレスと見なすことができる。すべての一次ノード及び二次ノードのためのネットワークアドレスは同じである場合があるが、必ずしもそうである必要はない。例えば、一次ノードのための全メッセージは、（このようなメッセージを区別する１つの方法である）二次メッセージがそこで受信されるそれとは別のポートで受信されてよい。
【００２２】
・メッセージが向けられる特定のノードの場所を指定するノード識別子（整数値）。例えば一次ネットワークでのすべてのメッセージが専用ポートで受信される場合も、各ノードと関連付けられた局所的に一意の識別子がある。したがって、複数のノードがあるときに、メッセージがどのノード向けであるのかが明確である。このノード識別子はアプリケーションに特殊なアドレス拡張子（それは標準インターネットプロトコルの一部ではない）である。それは送信されるメッセージに含まれるだけである。それを受信するプロセスはこれを「知って」おり、メッセージがどのノードに転送される必要があるのかを判断するためにこのノード識別子を調べる。
【００２３】
両方のノードが同じネットワークアドレスを有することはありえるが、必ずしもそうである必要はない。（部分的には使用可能なポートの数が制限されることがあるため）すべてのノードが専用のポートを有するわけではないが、２つのポート（したがって、２つの異なるネットワークアドレス）を有することもある。つまり、１つは一次ネットワーク用、１つは二次ネットワーク用である。通常、すべて同じポートを使用できるであろういくつかの二次ネットワークがある。
【００２４】
以下では、ノードのアドレスに対する参照がそのノードの完全なアドレスを指すことが強調されなければならない。
【００２５】
特に魅力的な手法は、テキストファイル及び一次ノードと二次ノードがすべて同じノード識別子（及びＩＰアドレス）を有し、ポート番号だけが異なっていることを提供することである。このようなアドレス指定プロトコルは、あるノードのアドレスを有し、それに関連付けられる別のノードのアドレスを必要とする場合に、後者のノードのアドレスが、調べられなければならないよりはむしろ、前者のアドレスから推定される可能性があるという点で、処理のいくらかを簡略化するための機会を与える可能性がある。しかしながら、以下の説明では、このような簡略化は行われておらず、その結果これらのプロセスは任意のアドレスプロトコルを扱うであろう。
【００２６】
ウェブページを見るコンピュータは、
・ラベルを取得するために同じハッシュ関数をＵＲＬに適用することによって
・あるノードのアドレスを取得するために一次仮想ネットワーク上で（ラベルを含む）照会を送信することによって、
・見つけられたアドレスを使用して、二次仮想ネットワーク上の多くの（あるいはすべての）他のノードのアドレスも取得するために二次仮想ネットワーク上で照会を送信することによって、
・表示するためのコメントを取り出すためにこれらのアドレスを使用することによって
関連付けられたコメントを取り出す。
【００２７】
取り出すコンピュータが必ずしも仮想ネットワークのノードを含まなくてもよいことに注意する。つまり、それは、取り出しプロセスを実現するためのソフトウェアをロードされ、それが仮想ネットワークのノードが常駐するコンピュータと通信できるように通信インタフェースをロードされた従来のコンピュータである場合がある。このプロセスは図１Ａのフローチャートに示され、以下のように進行する。
【００２８】
ステップ３０：ユーザがＵＲＬを入力する（あるいはハイパーリンクを呼び出す）のに続き、コンピュータは対応するウェブページを取り出す。このステップはまったく従来的である。
【００２９】
ステップ３１：ラベルを取得するためにハッシュ関数がＵＲＬに適用される。我々の以前の国際特許出願に説明されるように、これはＳＨＡ−１アルゴリズムを使用できる。
【００３０】
ステップ３２：このラベルと取り出し側コンピュータのネットワークアドレスを含む「Ｆｉｎｄ」メッセージが一次ネットワークに送信される。コンピュータが少なくとも１つのこのようなアドレスを所有していることが必要なのは明白である。
【００３１】
ステップ３３：取り出し側コンピュータが一次コンピュータから「Ｆｏｕｎｄ」メッセージを受信する。このメッセージは二次ネットワークの関連付けられたノードのアドレス及びコメントのアドレスだけではなく、発見されたノードのラベルとアドレスも含む。「Ｆｏｕｎｄ」メッセージが妥当な時間内に受信されない場合にプロセスを打ち切るためのタイムアウト機構を含むことができる。
【００３２】
ステップ３４：この例では、一次ネットワークは常に、それが「Ｆｉｎｄ」メッセージに含まれるラベルに最も近いラベルを含むノードのアドレスを返すように配置される。したがって、返されるラベルが要求されたラベルと同じであるかどうかを確かめるためにチェックが実行され、同じではない場合、プロセスは終了する。「最も近い」の意味の説明については以下を参照されたい。
【００３３】
ステップ３５：ラベルが一致すると仮定し、取り出し側コンピュータは、それがそれにより二次ネットワークを使用して追加のアドレスを取り出すために発見（Ｆｏｕｎｄ）メッセージによって返されるアドレスを使用する（詳しく後述される）プロセスを実行する。
【００３４】
ステップ３６：次にこれらのアドレスはコメントを含むテキストファイルを「ポスト側」コンピュータから取り出すために使用される（ｕｓｅｓ）。
【００３５】
（二次仮想ネットワーク）
このネットワークの目的は、ノードのグループを、グループの一部であるすべてのノードを発見するためにその後使用できる単一の仮想ネットワークに自己組織化することである。主要な要件は、結果としてネットワークがすべてのノードを含んでいることである。別の要件は、ネットワークを作成、維持するために必要とされるシステム負荷がすべてのノード全体で等しく拡散されることである。これは、さまざまなユーザが自分のリソースを１つの分散型アプリケーションに寄与するときに重要である、最も「公平」であるだけではなく、システムを過負荷から保護するのに役立つ。
【００３６】
したがって、ネットワークには以下の特性がある。
【００３７】
・各ノードによって維持されるリンクの数は好ましくは同じである。
【００３８】
・すべてのリンクは双方向である。その結果ノードへのリンク数も各ノードについて同じである。これはノードが受信し、処理しなければならないメッセージ数に影響を及ぼすため重要である。
【００３９】
・それは「平坦な」構造を有している。ノードは自らを階層的に配列しない。その結果システム負荷はすべてのノード全体で等しく拡散される。
【００４０】
（各ノードの構造）
各ノードは、それに関連付けられる以下のデータを有する。
【００４１】
・他のノードに対する複数のリンク。各リンクは別のノードのアドレスにすぎない。核リンクに関連付けられているのは、「確認済み」または「未確認」である場合があるステータスである。各ノードは、システム全体のパラメータＬによって指定される最大数のリンクを維持できるにすぎない。Ｌの典型的な値は、例えば６である。このパラメータがすべてのノードについて同じであることは必須ではないが、それらが異なるようにすることにより獲得される利点はない。
【００４２】
・スペアリンク、つまり手短に言えばスペアのリスト。各スペアは別のノードのアドレスにすぎない。スペアは仮想ネットワークを構築するために自己組織化プロセスによって使用される。ノードは、それがすでにノードにリンクしているため、またはそれがすでに最大数のリンクを有しているためのどちらかの理由により、それがリンクとして追加できない前記ノードについて通知されると他のノードをスペアとして追加する。ノードが維持できるスペアの数も制限され、システム全体のパラメータＳによって指定される。Ｓの典型的な値は、例えば３である。スペアリンクのリストは概して必須ではないが、それにより局所的に収容できないリンクを仮想ネットワークのなんらかの他のポイントに伝搬できる追加の機構を提供する上で非常に貴重である。しかしながら、スペアリンク（または類似した伝搬機構）を使用することは、入信するＮｏｔｉｆｙメッセージがつねに二次ネットワークの同じノード（または非常に少ない数のノードの内の１つ）に到着するシステムでは必要である。
【００４３】
（メッセージ）
ネットワークに自己組織化するため、及びどのノードが特定のネットワークの一部であるのかを発見するために、ノードは互いにメッセージを送信する。以下に示すタイプのメッセージが二次ネットワークによって使用される。
【００４４】
・以下を含むＡｄｄＬｉｎｋメッセージ
・送信者のアドレス
・受信者のアドレス
メッセージは相互リンクを要求するためにノード（送信者）によって別のノード（受信者）に送信される。
【００４５】
・以下を含むＣｈａｎｇｅＬｉｎｋメッセージ
・送信者のアドレス
・受信者のアドレス
・主題のアドレス
メッセージは、それがそのリンク（Ｚ）の内の１つをそれ自体（Ｘ）のリンクに変更することを要求するためにノード（Ｘ）によって別のノード（Ｙ）に送信される。プロトコルは、Ｘが、それにＹに対するそのリンクをそれ自体（Ｘ）に対するリンクで変更するように要求する、類似したメッセージをＺに送信するになている。したがって、事実上Ｘは現在ＸとＺの間にあるリンクにそれ自体を挿入することを要求すｒ。
【００４６】
・以下を含むＬｉｎｋＡｄｄｅｄメッセージ
・送信者のアドレス
・受信者のアドレス
メッセージは、送信者がそれに対するリンクをちょうど追加したところであることをノードに通知するために使用される。
【００４７】
・以下を含むＬｉｎｋＥｒｒｏｒメッセージ
・送信者のアドレス
・受信者のアドレス
・主題のアドレス
・エラーコード
メッセージはノードに、そのリンクの内の１つに問題があると考えられることを知らせるために使用される。例えば、主題ノードが応答しない可能性がある、あるいはリンクが相互的でない可能性がある。メッセージはエラーのタイプを示すためにエラーコードを含む。
【００４８】
・以下を含むＬｉｎｋｓメッセージ
・送信者のアドレス
・受信者のアドレス
・すべてのリンクのアドレス
・基準値
・Ｌｉｎｋｓメッセージは送信者ノードからのなんらかの他のデータも含む。ウェブページコメント例では、これは関連コメントのアドレスである。
【００４９】
メッセージは送信側ノードのすべてのカレントリンクを含む。それはつねにＬｉｎｋｓＱｕｅｒｙメッセージに応えて送信される。参照は、応答される前記特定の照会を区別するために使用できる。
【００５０】
・以下を含むＬｉｎｋｓＱｕｅｒｙメッセージ
・送信者のアドレス
・受信者のアドレス
・基準値
メッセージは、ノードにＬｉｎｋｓメッセージを（そのカレントリンクを含む）返事として送信するように要求するために使用される。
【００５１】
・以下を含むＮｏｔｉｆｙメッセージ
・送信者のアドレス
・受信者のアドレス
・主題のアドレス
・通知レベル
メッセージは、ノードにネットワーク内の別のノードを通知するために使用される。通知レベルはＮｏｔｉｆｙメッセージの伝搬を制御、制限するために使用される。ここで説明されるように、送信者アドレスは使用されないが、デバッグのために、あるいは肯定応答を送信することが所望される場合に有効である。
【００５２】
（二次ネットワークの構築）
システムはグループノードに単一の仮想ネットワークへ自己組織化させ、その結果１つのノードのアドレスを有すると、グループ内の他者のアドレスを発見できる。本項では、同じ二次ネットワークに所属するはずであるノードが発見されると、新しいリンクがどのようにして作成されるのかを説明する。ここでは２つの部分が区別できる。
【００５３】
同じ二次ネットワークに所属するはずであるノードの組の発見。複数のノードを同じネットワークの中にグループ化するための基準が何であるのかは、アプリケーション特有である。ウェブページ注釈例では、同じＵＲＬについてのコメントを表すすべてのノードは二次ネットワーク内で一緒にグループ化されなければならない。一緒にグループ化されなければならないノードがどのようにして発見されるのかもアプリケーション特有である。例を簡単に示す。
【００５４】
二次ネットワークをノード発見の結果として更新する／拡張すること。同じ二次ネットワークに所属しなければならない１組のノードが発見されると、システムは結果として１つまたは複数の新しいリンクを構築してよい。新しいリンクは必ずしもノードの前記組の間にはないが、例えばこれらの２つのノードのリンク先であるノードの間にあってよい。どのようにして新しいリンクが作成されるのかの詳細は後述する。
【００５５】
（Ｉｎｉｔｉａｌ Ｎｏｔｉｆｙ（初期通知）メッセージ）
二次ネットワークの組織化は、例えばグループの既存のメンバーと新しいメンバーを特定できる入信「通知」メッセージの存在を前提としている（早い段階ではどちらのノードもまだグループの一部ではないが、後に自己組織化プロセスの間に両方のノードともすでにグループの一部である可能性がある）。それに属さなければならないノードの二次ネットワークに通知するのはシステムの別の部分しだいである。それを行うことができるさまざまな方法がある。ここで、我々は、二次ネットワークが我々の以前の国際特許出願に説明される型の一次ネットワークと組み合わせて使用されるときに、これがどのようにして行われるのかの例を示す。ウェブページ注釈例では、各コメントは対応するウェブページのＵＲＬに基づくラベルの下で一次ネットワーク内のノードとして自らを公表する。このようにして、一次ネットワークは、ＵＲＬが存在する場合に特定のＵＲＬついてのコメントをルックアップするのに使用できる。特定のＵＲＬについてのすべてのコメントを示すために、各コメントはそれに関連付けられる二次ネットワークのノードも有する。同じＵＲＬについてのコメントに相当するノードはそのＵＲＬに特定的な二次ネットワークに自己組織化する。このようにして、いったん一次ネットワークがＵＲＬについての単一のコメントを見つけるのに使用されると、二次ネットワークは前記同じＵＲＬについての他のコメントを診付けるために使用できる。
【００５６】
したがって、このケースでは、ともにグループ化されなければならない二次ネットワークのノードはそれぞれ一次ネットワークの同じラベルの下で公表される。ノードが同じラベルの下で公表された別のノードを認識すると必ず、必要とされるＮｏｔｉｆｙメッセージが作成されるような改善策を含む、一次ネットワーク内で、ノードがリンクを構築し、維持するために周期的に「Ｐｕｓｈ（プッシュ）」更新を実行する機構について、以下に説明する。
【００５７】
（通知メッセージの取り扱い）
ノードが、それがまだリンクしていないノードについてＮｏｔｉｆｙメッセージを受信すると、以下の１つが起こる。
【００５８】
受信側ノードがすでに最大数の許容リンクを有する場合、それ（受信側ノード）は（それがすでにそれ（リンク）をスペアとして有していない限り）代わりにそれをスペアとして追加する。これを行う際に、前記ノードがその最大スペア数を超えると、それは１つのスペアを削除する。次に、それ（前記ノード）はそれが削除した前記スペアにＮｏｔｉｆｙメッセージも転送する。それがこれを行うかどうかは、通知レベルの値次第である。通知レベルは、メッセージが際限なく伝搬するのを妨ぐために毎回減少する。
【００５９】
それ以外の場合、主題ノードがまだ最大数のリンクを有していない場合、受信側ノードは両方のノードの間に相互リンクを作成しようと試みる。これは図２のａとｂに描かれている。ここでは、Ｌ＝３であり、ノード１はノード２についてのＮｏｔｉｆｙメッセージを受信した。両方のノードとも２つのリンクしか有していなかったため、ノード１とノード２の間にリンクが作成される。
【００６０】
それ以外の場合、主題ノードがすでに最大数のリンクを有している場合は、単に両方のノード間に相互リンクを作成することは可能ではない。したがって、何が起こるかというと（ｗｈａｔ ｈａｐｐｅｎｓ）、受信側ノードが既存のリンクにそれ自体を挿入しようと試みる。これは図２のｃとｄに描かれている。ここでノード２とノード３の間のリンクは破壊されるが、それは２つの新しいリンク、つまりノード１とノード２の間のリンクとノード１とノード３の間のリンクによって置き換えられる。したがってリンクの総数は１だけ増加する。それは、たとえノード２とノード３がすでに最大数のリンクを有していたとしてもうまく行く。しかしながら、これが成功するためにはノード１が２つの新しいリンクを作成できることが必要であった。このプロセスは図３から図９のフローチャートにさらに詳細に説明される。
【００６１】
図３は、ノードが入信Ｎｏｔｉｆｙメッセージをどのように処理するのかを示す。ここでは、新しいリンクを作成する必要があるかどうかが決定され、そうである場合にはどのように（新しいリンクを追加することによって、あるいは既存のリンクを２つのリンクに変更することによって）作成されるべきかが決定される。新しいリンクが作成される場合、スペアの集合は更新され、Ｎｏｔｉｆｙメッセージが送信されてよい。
【００６２】
ステップ３００では、それを送信したノード（送信者）のアドレス、主題ノードのアドレス、及び伝搬制限値であるｎｏｔｉｆｙｌｅｖｅｌを含むＮｏｔｉｆｙメッセージが受信される。受信側ノードは最初に、それが新しいリンクをセットアップする空間を有するかどうかをチェックし（３０１）、空間がある場合には、それがすでに主題ノードへのアクセスを有しているかどうかをチェックする（３０２）。有していない場合、それ（受信側ノード）は主題とリンクをセットアップしようと試みる。
【００６３】
ステップ３０３では、それ（受信側ノード）は主題ノードにＬｉｎｋｓＱｕｅｒｙメッセージを送信し、ステップ３０４で応答を待つ。いったん応答−Ｌｉｎｋメッセージ−が受信されると、それ（「受信側ノード」または「前記ノード」）は、（それがその間にも他のメッセージを受信、処理し、その結果としてリンクを作成した場合）それが依然として新しいリンクをセットアップするための空間を有しているかどうかを再びチェックする（３０５）。空間がある場合、それは次に主題ノードが新しいリンクをセットアップするための空間を有するかどうかをチェックするために受信されたＬｉｎｋｓメッセージを調べる（３０６）。それが有する場合、ステップ３０７と３０８で、受信側ノードは主題ノードのアドレスを（「未確認」とマークされているが）そのリンクのリストに追加し、ＡｄｄＬｉｎｋメッセージを主題ノードに送信する。
【００６４】
しかしながら、ステップ３０６で、主題ノードが追加リンクを受け入れることができないと判断されると、受信側ノードは、図２を参照して前述されたように、それ自体を既存のリンクの中に挿入しようと試みる。第１のステップ（３０９）は、受信側ノードが２つのリンク分の空間を有するかどうかをチェックすることである。ない場合には、プロセスは終了する。しかしながら、ある場合には、受信側ノードは受信されたＬｉｎｋｓメッセージの中のリンクのリストから無作為に（受信側ノードがすでにリンクを有しているノードではない）リンク、すなわち主題ノードと、ここでは他と呼ばれる別のノードの間のリンクを選択する。それから、受信側ノードは、
３１１ 主題ノード（未確認）のアドレスをそのリンクのリストに追加する
３１２ 他のノード（未確認）のアドレスをそのリンクのリストに追加する
３１３ 他のアドレスを含むＣｈａｎｇｅＬｉｎｋメッセージを主題ノードに送信する
３１４ 主題のアドレスを含むＣｈａｎｇｅＬｉｎｋメッセージを他のノードに送信する
ことによって、それ自体をこのリンクに挿入しようと試みる。
【００６５】
しかしながら、ステップ３０１で、受信側ノードがリンクを追加するための空間を持たないと判断されると、あるいはステップ３０２で、それが主題ノードに対してすでにリンクを有していると判断されると、プロセスは受信側ノードがそのスペアリンクのリストにリンクを追加する必要があるかどうかを調べる。ステップ３１５では、主題ノードがすでにスペアリストにあると判明するとプロセスが終了する。ステップ３１６では、スペアリストにリンクを追加するための空間があるかどうかがチェックされ、ある場合には、これは３１７で正式に追加される。ない場合には、ステップ３１８でスペアリンクの内の既存のリンクが無作為に選択され、それがステップ３１７で主題へのリンクによって置換できるようにステップ３１９で削除される。また、変数ｎｏｔｉｆｙｌｅｖｅｌは３２０で減分され、（ステップ３２１）それがゼロ以外のままであると、ステップ３２２で元のＮｏｔｉｆｙメッセージが−ｎｏｔｉｆｙｌｅｖｅｌのこの新しい値とともに−無作為に選択された既存のリンクによって指される（置換と呼ばれる）ノードに転送される。
【００６６】
このプロセスの効果は、すでにリンクの完全な集合を有するノードＡがそれに主題ノードＢにリンクするように依頼するＮｏｔｉｆｙメッセージを受信すると、Ｂのアドレスがスペアリンクとして記録されるという点である。このリンクは、Ａのスペアリンクのリストがいっぱいになるまで休眠したままである。次に、ＡがそれにノードＣにリンクするように依頼する、後のＮｏｔｉｆｙメッセージを受信し、ノードＢへのスペアリンクがステップ３１８で選択されると、ステップ３２２で作成される新しいＮｏｔｉｆｙメッセージは、事実上、それ自体からノードＣへのリンクを作成するというノードＢに対する要求である。
【００６７】
リンクが未確認であり、受信側ノードが一定の期間内に（図６を参照して後述されるように、ＬｉｎｋＡｄｄｅｄメッセージを介して）確認を受信しないとき、未確認のリンクが削除される機構も提供されるが、フローチャートには図示されていない。受信側ノードが、依然として「未確認」ステータスを有するリンクを有するときには、それはＬｉｎｋｓＱｕｅｒｙメッセージに応えて（言うまでもなく確認済みのリンクだけではなく）これらの未確認リンクも返し、他のノードが、それがリンクをセットアップしようと試みていることを確認できるようにする。
【００６８】
図３では、ステップ３０５と３０９で「ノー」に出ると、プロセスは終了する。しかしながら所望される場合、それらはステップ３１５で始まる、効率がわずかに改善されて「スペアリンク」プロセスに送ることができる。
【００６９】
ステップ３０９から３１４では、ノードは事実上、主題のリンクの１つを破壊し、それ自体を間に挿入する。フローチャートに図示されていない別の考えられるオプションは、ノードが（言うまでもなくそれがすでに１つのリンクを有していると仮定し）独自のリンクの内の１つを破壊し、主題を間に挿入することであろう。このオプションは、実現される場合、ステップ３０１で「ノー」に出た直後に試されるであろう。最初に、受信側ノードは、主題がＬ−１個より少ないリンクを有していたかどうかを確かめ、無作為に（ノード他に対する）独自のリンクの内の１つを選択し、これを主題に対する未確認リンクで置換し、主題にＡｄｄＬｉｎｋメッセージを送信する必要があるであろう。次に、主題と他の間に双方向リンクを設立するために、それは、（ａ）主題に無条件で他を未確認リンクとしてそのリンクのリストに追加することを要求する特別のＡｄｄＬｉｎｋメッセージを主題に送信し、（ｂ）受信側ノードが旧リンクとして削除され、主題を追加される新規リンクとして指定する特別なＣｈａｎｇｅＬｉｎｋメッセージを他に送信するであろう。このオプションは、ステップ３０９から３１４と同様に、あるいはステップ３０９から３１４の代わりに含まれるであろう。
【００７０】
受信側ノードが独自のリンクの内の１つを破壊するための別のオプションは、（最初に、主題がＬ−１個より少ないリンクを有していたと検証した）それ（受信側ノード）が主題に、それ自体を主題として指定するＮｏｔｉｆｙメッセージを送信することであろう。これは同じ結果をもたらすが、わずかに大きなメッセージングオーバヘッドを必要とするであろう。
【００７１】
図４は、ノードが入信ＣｈａｎｇｅＬｉｎｋメッセージをどのように処理するのかを示している。これらのメッセージは、Ｎｏｔｉｆｙメッセージを受信したノードＸが既存のリンクを２つの新しいリンクに変更することを希望するときに送信される（図２を参照されたい）。受信側ノードＹは、４００でノードＺをｓｕｂｊｅｃｔとするＮｏｔｉｆｙ、つまりノードＹにその既存のノードＺリンクを、ノードＸに置換するように求めるメッセージを受信する。それ（ノードＹ）が事実上ノードＺへのリンクを所有していない（４０２）場合は、それはｓｅｎｄｅｒＸにエラーメッセージを送信する４０３が、それがすでにＸへのリンクを有する場合は、それは追加の処置を講じない（４０１）。
【００７２】
すべてがうまくいくと仮定して、それはｓｅｎｄｅｒＸにＬｉｎｋＱｕｅｒｙメッセージを送信し（４０４）、後者（送信者）が、それが主題リンクを変更する前に作成しなければならなかった２つの新しいリンクを実際に作成したかどうかチェックするために、送信側ノードＸからの応答としてＬｉｎｋｓメッセージを待機する（４０５）。これらのチェック（４０６、４０７）が無事に終了すると、受信側ノードはＺへのリンクを削除し（４０８）、確認されたリンクとしてＸを追加し（４０９）、ＬｉｎｋＡｄｄｅｄメッセージをｓｅｎｄｅｒＸに返す（４１０）。
【００７３】
図５は、ノードが入信ＡｄｄＬｉｎｋメッセージをどのようにして処理するのかを示している。これらのメッセージは、ノードがノードとの新しいリンクの作成を希望するときに送信される（図１を参照されたい）。メッセージは５０１で受信され、ノードはステップ５０２で、それが別のリンクのための空間を有するかどうかをチェックし、ない場合には５０３でエラーメッセージを返す。ある場合には、それはＬｉｎｋｓＱｕｅｒｙメッセージをｓｅｎｄｅｒに送信し（５０４）、送信側ノードからの応答としてＬｉｎｋｓメッセージを待機し（５０５）、その結果それは５０６で後者（送信者）が実際に受信側ノードへのリンクを作成したことをチェックできる。ノーである場合、それはリンクを追加するのを拒否し、終了するが、そうであるならば、それは次にｓｅｎｄｅｒを確認されたリンクとして追加し（５０７）、確認する目的でＬｉｎｋＡｄｄｅｄメッセージをｓｅｎｄｅｒに返す（５０８）。
【００７４】
図６は、ノードが入信ＬｉｎｋＡｄｄｅｄメッセージをどのように処理するのかを示す。これらのメッセージは、ＣｈａｎｇｅＬｉｎｋメッセージまたはＡｄｄＬｉｎｋメッセージのどちらかに応えて、別のノードが受信側ノードへのリンクを受け入れると送信される。リンクが受け入れられたことを示すＬｉｎｋＡｄｄｅｄメッセージが６００で受信されると、そのステータスはステップ６０１で「確認済み」に変更される。それからリンクは、それが（ＣｈａｎｇｅＬｉｎｋメッセージに応えて）新しいリンクのために変更されるのか、あるいはリンクが破壊されるかのどちらかまで維持される。
【００７５】
図７は、ノードが入信ＬｉｎｋＥｒｒｏｒメッセージをどのようにして処理するのかを示す。これらのメッセージは、ノードが受信側ノードへのリンクを、後者が（ＣｈａｎｇｅＬｉｎｋメッセージまたはＡｄｄＬｉｎｋメッセージを手段として）相互リンクを要求した後に作成できなかったとき、あるいはリンクが壊れていると考えられる（他端でのノードがメッセージに応答していない可能性がある、あるいはリンクが相互的ではない可能性がある）ときのどちらかに送信される。壊れたリンクは自己組織化プロセスによってではなく、（後述されるように）クライアントが二次ネットワークを横断するときに検出される。
【００７６】
７００でのメッセージの受信に続き、メッセージが、受信側ノードが未確認リンクを有するノードについてであるかどうかが判断される（７０１）。そうである場合、及びそれが要求されたリンクを作成できなかったことを示すエラーコードを伝搬する（７０２）場合、リンクは７０３で削除される。しかしながら、メッセージが、受信側ノードが未確認リンクを有するノードについてではない場合、受信側ノードはｓｕｂｊｅｃｔにＬｉｎｋＱｕｅｒｙメッセージを送信し（７０４）、応答としてＬｉｎｋｓメッセージを待機し（７０５）、主題がそれ自体にリンクを有するかどうかをチェックするために７０６で応答をチェックし、有さない場合にはステップ７０３で主題ノードに対するそのリンクを削除する。
【００７７】
図８は、ノードが入信ＬｉｎｋｓＱｕｅｒｙメッセージをどのように処理するのかを示す。これらのメッセージは、別のノードが受信側ノードのリンクを知ることを希望するときに送信され、したがって後者（受信側ノード）は８００でその受信時に８０１でＬｉｎｋｓメッセージで応答する。
【００７８】
図９は、ノードが入信Ｌｉｎｋｓメッセージをどのようにして処理するのかを示す。それがどのように処理されるのかは、なぜ対応するＬｉｎｋｓＱｕｅｒｙメッセージが送信されたのかに完全に左右される。これは、とりわけ図３、図４、図５及び図７に示されるようにさまざまな理由から起こる。したがって、何が起こるかというと（ｗｈａｔ ｈａｐｐｅｎｓ）、ＬｉｎｋｓＱｕｅｒｙメッセージが送信されると、それは局所的に一意である基準を与えられ、メッセージハンドラが前記基準に関連付けられる。それから、Ｌｉｎｋｓメッセージが受信されると（９００）、適切なメッセージハンドラが特定され、メッセージは、ステップ９０２でメッセージがただちに処理されるように適切なメッセージハンドラに送られる。
【００７９】
言うまでもなく、例えば受信側ノードが停止していたために、ＬｉｎｋｓＱｕｅｒｙに応えてＬｉｎｋｓメッセージがいままで送信されていない場合がある。したがって、一定の期間後にＬｉｎｋｓメッセージが受信されない場合は、対応するメッセージハンドラは削除される。これはここに説明されるフローチャートのいずれにおいても明示的に示されていないが、それは単にリンク照会が時間切れになると、追加の処置は講じられず、フローチャート全体が「完了した」ことを意味する。
【００８０】
（ノードの取り出し）
二次ネットワークの単一のノードのアドレスを考慮すると、ネットワークの他の、潜在的にはすべてのノードを発見することが可能である。これを行うことができる方法は非常に簡単である。既知のノードにすべてのリンクを要求するためにＬｉｎｋｓＱｕｅｒｒｙメッセージを送信する。ノードは、それがリンクするノードのすべてのアドレスを含むＬｉｎｋｓメッセージで応答する。それから、これらのノードのそれぞれに順々に連絡し、それらのリンクを要求し、このようにしてそれらすべてのリンクのアドレスを得ることができる。このように続けることで、ネットワークを横断し、それが含むすべてのノードを徐々に発見する。
【００８１】
図１０は、プロセスを詳細に示している。これが図１Ａに示されている取り出しステップ３５で使用されるプロセスであることが理解されるであろう。無事に連絡されたすべての既知のノードのアドレスは「確認済み」リストに入れられる。データは同時に取り出されてよい。「ウェブページコメント」例のケースでは、データの関連する項目はコメントのアドレスであり、これもノードアドレスと同時にｃｏｎｆｉｒｍｅｄ（確認済み）リストに入れられる。ｃｏｎｆｉｒｍｅｄ（確認済み）リストは、図１Ａのコメント「取り出し」ステップ（３６）に必要とされるアドレスを提供する。他方、「未確認」リストはまだ連絡を受けていない既知のノードのアドレスを含む。最後に「既知」のリストはすべての既知のノードのアドレスを含んでいる。それは「確認済み」リストと「未確認」リストの中のすべてのアドレスを含んでいるが、連絡されたノード及び応答していないノードのアドレスも含む。ｋｎｏｗｎ（既知の）リストは、それに入れられたアドレスごとに、ソースａｄｄｒｅｓｓ（アドレス）を含む追加フィールド−つまり、エラー報告のために、そのリストからｃｕｒｒｅｎｔ（カレント）ポインタが指すアドレスが取得されたノードのアドレスを有する。
【００８２】
どこで取り出しプロセスが発生するのかは重要ではない。それはノードあるいは他のどこかである可能性がある。ステップ１０００では、ノードアドレスを取り出す要求がｓｔａｒｔ（開始）アドレス、つまり対象とする仮想ネットワークに属すると判断された１つのノードのアドレスとともに受信される。ステップ１００２では、第２のアドレスポインタ、ｓｏｕｒｃｅ（ソース）は当初ヌルである（１００３）が、アドレスポインタｃｕｒｒｅｎｔ（カレント）は当初このアドレスに設定される。
【００８３】
ステップ１００４と１００５では、ＬｉｎｋｓＱｕｅｒｙメッセージは、ｃｕｒｒｅｎｔ（カレント）によって指定されるアドレスに送信され、応答が待機される。Ｌｉｎｋｓメッセージが受信されると、それと並行して、ｃｕｒｒｅｎｔ（カレント）は、Ｌｉｎｋｓメッセージからのコメントアドレスとともにｃｏｎｆｉｒｍｅｄ（確認済み）リストに追加される（ステップ１００６）。
【００８４】
ステップ１００７では、Ｌｉｎｋｓメッセージに含まれるアドレスのそれぞれについて実行されるサブプロセスが入力される。アドレスがすでに既知のリスト内にあると（１００８）、プロセスは次のアドレスに移動する（ｓｔｅｐｓ ｏｎ ｔｏ）。それ以外の場合、アドレスはｋｎｏｗｎ（既知の）リストに、及びｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストに追加される（ステップ１００９、１０１０）。また（１０１１）、ｃｕｒｒｅｎｔ（カレント）のアドレスは追加されたアドレスのソースであるとしてｋｎｏｗｎ（既知の）リストに入力される。
【００８５】
いったんこのサブプロセスが完了すると、（その場合プロセスがステップ１０１２で終了する、ｕｎｃｏｆｉｒｍｅｄ（未確認）リストが空でない限り）ステップ１０１３でｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストから無作為にアドレスが選択される。このアドレスが新しいｃｕｒｒｅｎｔ（カレント）アドレスになり、ｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストから削除される。次のステップ（１０１４）は、それに関連付けられるソースアドレスを取り出すためにｋｎｏｗｎ（既知の）リストの中でｃｕｒｒｅｎｔ（カレント）をルックアップし、これをｓｏｕｒｃｅ（ソース）ポインタに入れることである。無作為選択は必須ではない。例えば、カレントは未確認リスト内の「最も旧い」ノードとして選ぶことができるであろう、あるいはリストは別の基準（例えばノードのアドレス）でソートされ、ｃｕｒｒｅｎｔ（カレント）はつねにこのリストの「最初の」ノードとなることができるであろう。しかしながら、ｃｕｒｒｅｎｔ（カレント）の無作為選択にはその利点がある。それは（特にすべてのノードがつねに取り出されるわけではない場合に）システム内で負荷を拡散し、壊れたリンクがより迅速に発見されるようにネットワークのリンクの試験も拡散する。
【００８６】
それから、プロセスはステップ１００４から再び続行し、ｕｎｃｏｎｆｉｒｍｅｄ（未確認）リストが空になる−つまり、追加の新しいアドレスが見つからなくなる−まで反復する。
【００８７】
取り出しプロセスの思わぬ結果は、それが壊れたリンクを発見することである。例えば、ノードが応答していない、あるいはリンクが相互的ではない場合がある。後者は、ノードＡがノードＢにリンクするが、ノードＢがそのリンクテーブルにノードＡを入れていないケースである。壊れたリンクが発見されると、前記リンクの「ソース」であるノードはＬｉｎｋＥｒｒｏｒメッセージを手段として通知される。図７がすでに示していたように、ソースノードは、次に（エラーレポートの精度を確認するために）リンク自体をチェックすることができ、結果としてリンクを削除する場合がある。応答していないノードは、設定されたタイムアウト期間内にＬｉｎｋｓメッセージを受信できないことによってステップ１００５で認識され、ステップ１０１５では、ｃｕｒｒｅｎｔ（カレント）のアドレスと「応答なし」エラーコードを含むエラーメッセージがｓｏｕｒｃｅ（ソース）に送信され、その結果制御はステップ１０１２に戻る。リンクの相互性の欠如（ｎｏｎ−ｍｕｔｕａｌｉｔｙ）は、ｃｕｒｒｅｎｔ（カレント）について受信されたＬｉｎｋｓメッセージがｓｏｕｒｃｅ（ソース）のアドレスを含んでいるかどうかを判断するためにステップ１０１６での試験によって認識される。含んでいない場合、ｃｕｒｒｅｎｔ（カレント）のアドレス及び「非相互的」エラーコードを含むエラーメッセージがｓｏｕｒｃｅ（ソース）に送信される（ステップ１０１７）が、（図７のプロセスに従って）救済処置を講じるのはソースノードの責任であるため、取り出しプロセスは以前のように続行する。ステップ１１０６での試験は、ｓｏｕｒｃｅ（ソース）がヌルである場合には省略される。
【００８８】
複数の確認済みノードが、Ｌｉｎｋｓメッセージに応答しないノードにリンクするとしても、最初にリンクに貢献したノード（ソースノード）だけが、「応答なし」であったことを通知されることに注意されたい。これは、部分的には、その方がフローチャートを理解しやすいためである。しかしながら、別の実際的な利点があると主張することができる。ノードは、それが一時的にオーバロードされているために（時間内に）応答しない可能性がある。この場合、（図７でのように）エラーがあるかどうかを試験するために、複数のノードにＬｉｎｋｓＱｕｅｒｙメッセージを同時に送信してほしくない場合がある。いずれにせよ、所望される場合、壊れたリンクにより影響を受けるすべての既知のノードに、このようなリンクが発見されると通知するようにノード取り出しアルゴリズムを更新することは分かりやすい。
【００８９】
図１０では、ノード取り出しは、すべての既知のノードが連絡を受けるまで停止しない。実際には、プロセスを早期に終了することを希望する場合がある。例えば、ユーザがファイルをそこからダウンロードする場所を探している場合、例えばすべて、１０００の代わりに１０の可能性のあるダウンロードアドレスの選択肢をユーザに提供することで十分である可能性がある。
【００９０】
図１０のアルゴリズムは完全にシリアルとして示されている。一度に１つのノードだけが連絡される。別のＬｉｎｋｓＱｕｅｒｙメッセージは、過去のメッセージに対する応答が受信された（あるいはそれが時間切れになった）後にのみ送信される。しかしながら、実際には、我々は複数のＬｉｎｋｓＱｕｅｒｙメッセージを同時に発行することにより取り出しを加速することを好む。ボックス１０００では、複数の取り出し要求が図１０のプロセスの複数のインスタンスによって同時に処理される場合がある。
【００９１】
（説明）
（自己組織化の成功）
二次仮想ネットワークの目的とは、複数の接続されていないネットワークとは対照的に単一のネットワークの中にともにグループ化されなければならないすべてのノードを自己組織化することである。これが当てはまるかどうかは、初期のＮｏｔｉｆｙメッセージがどのように作成されるのかに負うところが大きい。例えば、すべてともにグループ化されなければならない１２のノードのグループがあるが、このグループの内、５つのノードだけが５つのこのグループ内の他のノードについて通知を受信し、他の７つのノードのどれもこれらの５つのノードのどれかについて通知されない場合、ノードが単一のネットワークに自己組織化することは不可能である。代わりに、それらは、５つのノードの１つと７つのノードの１つという２つの別々のネットワークに配置される（ａｒｒａｎｇｅ ｉｎｔｏ）。しかしながら、初期通知が、ノードが単一のネットワークに自己組織化することが不可能でないようであれば、自己組織化のプロセスは、ノードが単一のネットワークに自己組織化しない可能性がきわめて低いほどである。自己組織化の結果単一ネットワークが生じる確率の計算は複雑であり、初期通知を作成する機構に左右される。しかしながら、我々はシミュレーションで複数の異なる初期通知機構を経験し、これまでノードが単一のネットワークに自己組織化することができなかったことはない。
【００９２】
（悪意のあるノードに対するロバスト性）
これまで、すべてのノードはプロトコルに従うと仮定されてきた。しかしながら、ルールに従って行動しない悪意のあるノードがいる可能性がある。それらは、他のノードによって維持されているリンクを破壊しようとする、及び／あるいはそれら自体に多すぎるリンクを取得しようとする。全体的なシステムがこのような悪用に対し可能な限りロバストであることが望ましい。
【００９３】
これまで説明されてきたシステムは悪意のあるノードに対してすでにかなりロバストである。それは、各ノードが、自身のリンクを変更する前に、つねにＬｉｎｋｓＱｕｅｒｙ−Ｌｉｎｋｓメッセージ交換を用いて他の関連性のあるノードによって維持されるリンクをチェックするためである。例えば、ノードがＡｄｄＬｉｎｋメッセージを受信するとき（図３を参照されたい）、それは、自身のリンクとして送信者を追加する前に、最初に、送信側ノードが実際にそれにリンクしたかどうかをチェックする。
【００９４】
しかしながら、システムには依然として相対的な弱さがある。現状では、ノードは、それらがＬｉｎｋｓメッセージで応答するときに容易に「ウソをつく」ことができる。多くの場合、ノードは受信側ノードがそれにリンクしていることをチェックするためにＬｉｎｋｓＱｕｅｒｙメッセージを送信する。受信側ノードは、このことを知っているので、それがつねにリンクとしてＬｉｎｋｓメッセージの送信者を含むように修正された捏造Ｌｉｎｋｓメッセージで応答できる。これにより、ノードはそれにリンクするＬ個のノードという許容数よりはるかに多いノードを有することができる。結果として、これはシステム内の「よい」リンクの総数を削減するであろう。
【００９５】
幸いなことに、この弱さに対処する方法がある。これは、ノードがプロキシノードを通してそれらのＬｉｎｋｓＱｕｅｒｙを送信する場合に行うことができる。これらのプロキシは、ノードが照会を送信することを希望するたびに無作為に選ばれる。各ノードは、例えば、それが現在リンクしているノードをプロキシとして使用できる。このようにして、別のノード（Ｂ）のリンクを知ることを希望するノード（Ａ）は、それ（ノードＢ）が受信するＬｉｎｋｓＱｕｅｒｙメッセージがプロキシノード（Ｃ）からであり、ノードＢがノードＣから受信するメッセージはまったくノードＡを参照しないため、ノードＢにとっては未知である。したがって、ノードＢが全体的なシステムに重大な影響を及ぼす捏造メッセージを送信する手っ取り早い方法はない。
【００９６】
言うまでもなく、悪意のあるプロキシの影響はどのようなものであるかに関する疑問がある。明らかに悪意のあるプロキシは有害な影響を及ぼすが（プロトコルに従わないノードがパフォーマンスにある程度影響を与えるのは避けられない）、この影響は限られている。その理由は、それらが不当に処理できるのは、それらが転送するように依頼されるＬｉｎｋｓＱｕｅｒｙだけであり、これらの要求はすべてのノード全体でだいたい均一に拡散されるためである。他方、プロキシが使用されないときには、悪意のあるノードは非常にアクティブであることによる大混乱を引き起こすことがある。これらのノードが多くの偽のＡｄｄＬｉｎｋメッセージを送信し、それらが実質的に送信する多くのＬｉｎｋｓメッセージを捏造すると、全体的なシステムに及ぼされる影響ははるかに大きくなる。
【００９７】
（一次仮想ネットワーク）
一次ネットワークは、我々の前述された国際特許出願に詳しく説明されている。ここでは、二次ネットワークの自己組織化を促進するＮｏｔｉｆｙメッセージの作成を可能にする改善策とともに、基本的な取り出し機構と自己組織化機構が説明される。
【００９８】
最初に、この機構によって使用される仮想座標空間の概念を説明することが必要である。各ノードがラベルを有することはすでに言及された。ラベルは仮想空間で座標に変換される。空間は一次元、二次元またはさらに高い次元である場合がある。正確な変換機構はあまり重大ではない。つまり一次元空間の場合、バイナリ数と見なされるラベルは座標として直接的に使用できる。二次元及び三次元以上の場合、好ましい方法では、ビットの文字列として見なされるラベルが２つまたは３つ以上の等しいグループに区分され、バイナリ数と見なされる各グループが座標の１つを形成する。各座標（つまり、一次元空間での前記座標）は範囲［０，１］にあるように拡大縮小される。
【００９９】
所望される場合、（多くの場合マンハッタン距離と呼ばれる）都市ブロック距離のような他の距離が使用できるであろうが、この仮想空間の２つのラベルの間の距離が、２つの座標集合の間のユークリッド距離である。座標空間は、ｘ1とｘ2の間のｘ方向の距離が
Ｍｉｎ｛（１−｜ｘ1−ｘ2｜），｜ｘ1−ｘ2｜｝
となるように重なり（ｗｒａｐｓ）、したがって点（ｘ1，ｙ1）と（ｘ2，ｙ2）の間の二次元のユークリッド距離は、
【数１】
【０１００】
である。
【０１０１】
我々は、この点で各ノードが、多くのエントリが他のノードへのリンクを表すリスト２２（図１）を有することも思い出す。各エントリは、このような別のノードのラベルとアドレスから構成される。当初、このリストは空であるため、ノードは、ブートストラップリンク−すなわちそれがネットワークの他のノードに最初に連絡できるように２、３のリンク（通常は４つ）−の第２の類似したリストを有する。ノードは（短距離リンクと呼ばれる）リスト２２の中のリンクだけではなく、階層的に配列された追加のこのようなリスト、及び／または長距離リンクのリストも有する場合がある。これらは、我々の初期の国際特許出願に説明されているが、それらは付加的であるため、ここでは説明されない。
【０１０２】
（メッセージ）
最初に、以下のメッセージが使用される（一次仮想ネットワークで使用されるメッセージが二次仮想ネットワークで使用されるメッセージとは異なり、二次仮想ネットワークで使用されるメッセージから完全に独立していることに注意する）。
【０１０３】
ＦＩＮＤメッセージは、ノードルックアップを起動し、実行するため、及び「ＰＵＬＬ（プル）」更新をサポートするために使用される。それらは、
・ターゲットノードのラベル
・照会を開始したノードのアドレス
を含む。
【０１０４】
ＦＯＵＮＤメッセージは照会の結果を返すために使用される。それらは、
・ターゲットノードのラベル
・発見されたノードのラベル
・発見されたノードのアドレス
・発見されたノードと関連付けられる二次ネットワークのノードのアドレス
・アプリケーション特有データ−このケースでは、発見されたノードと関連付けられるコメントノードのアドレス
ＰＵＳＨ（プッシュ）メッセージは、ノードのラベルを他のノードに宣伝する。それらは、
・主題ノードのラベル
・主題ノードのアドレス
・ターゲットノードに到達するためのｈｏｐｓ ｔｏ ｇｏ（移動ホップ）数
ＮＯＴＩＦＹメッセージはプッシュ−更新を伝搬するために使用される。それらは、
・主題ノードのラベル
・主題ノードのアドレス
を含む。
【０１０５】
（取り出し）
図１１は、各ノードが入信Ｆｉｎｄメッセージをどのようにして処理するのかを示している。原則的には、受信側ノードはそれ自体よりＦｉｎｄメッセージで特定されたターゲットノードにより近いノードを探し、成功した場合はＦｉｎｄメッセージを次へ回す。成功しない場合、それは独自のアドレスとラベルを返す。それは、以下のステップを実行することによってこれを行う。
【０１０６】
ステップ１１００：ノードは、ターゲットノードのラベルと開始側ノードのアドレスを含むＦｉｎｄメッセージを受信する。
【０１０７】
ステップ１１０５：ノードはターゲットノードのラベルをラベル空間の座標に変換し、それが記録しているすべてのリンク（ノード）の内で、どれがラベル空間内のターゲットノードに最も近いのかを計算する。当該ノードはｎｅａｒｅｓｔノードと指定される。
【０１０８】
ステップ１１１０：ノードは自身の座標とターゲットノードの座標の間の距離を、ｎｅａｒｅｓｔノードの座標とターゲットノードの座標の間の距離に比較する。
【０１０９】
ステップ１１１５：自身の座標とターゲットノードの座標の間の距離が少ない（あるいは等しい）場合、ノードは開始側ノードにネットワーク１０を介して、自身のラベルとアドレスを含んだＦｏｕｎｄメッセージを送信する。
【０１１０】
ステップ１１２０：ｎｅａｒｅｓｔノードの座標とターゲットノードの座標の間の距離が少ない場合、ノードはＦｉｎｄメッセージをｎｅａｒｅｓｔノードに転送する。
【０１１１】
ステップ１１１５で返されるノードのアドレスはターゲットラベルが付いたノードのアドレス、またはラベル空間内でそれに近いもののどちらかである。返されるラベルがターゲットラベルに一致しないときは、それはターゲットノードが存在していない、または仮想ネットワークが十分に自己組織化されていないかのどちらかを意味する。
【０１１２】
（プッシュ）
各ノードはＰｕｓｈ（プッシュ）更新を自発的に開始する。例えば、各ノードは定期的にＰｕｓｈ（プッシュ）更新プロセスを開始する可能性がある。Ｐｕｓｈ（プッシュ）更新では、ノードはノードの無作為系列（ｒａｎｄｏｍ ｓｅｒｉｅｓ）を通して自身のラベルとアドレスとともにＰｕｓｈ（プッシュ）メッセージを送出し、系列の長さに制限を設定する。系列の中の最後のノードは開始側ノードに向かってＮｏｔｉｆｙメッセージを送り返す。図１２、図１３、及び図１４はこのプロセスの多用な部分を示している。
【０１１３】
図１２は、以下のステップを使用してノードがどのようにしてＰｕｓｈ（プッシュ）更新を開始するのかを示す。
【０１１４】
ステップ１２００：ノードはそのブートストラップリンクの中から無作為にリンクを選択し、選択されたリンクによって特定されるノードのアドレスを次のメッセージのｆｏｒｗａｒｄ（転送）アドレスとして入力する。
【０１１５】
ステップ１２０５：ノードはＰｕｓｈ（プッシュ）メッセージのフィールドｈｏｐｓ ｔｏ ｇｏ（移動ホップ）に小さい正の乱数を入力する。
【０１１６】
ステップ１２１０：ノードは自身のラベルとアドレスをＰｕｓｈ（プッシュ）メッセージの中のｓｕｂｊｅｃｔノードのラベルとアドレスとして入力し、ネットワーク１０を使用して、Ｐｕｓｈ（プッシュ）メッセージをｆｏｒｗａｒｄ（転送）アドレスにあるノードに送信する。
【０１１７】
図１３及び図１４は、短距離リンクがどのようにして更新されるのかを示している。Ｐｕｓｈ（プッシュ）メッセージは、短距離リンクを更新するためにＮｏｔｉｆｙメッセージとともに使用される。この更新には２つの段階がある。第１の段階では、各ノードは、受信されるようなメッセージの移動ホップ（ｈｏｐｓ ｔｏ ｇｏ）の値が「０」になるまでＰｕｓｈ（プッシュ）メッセージを無作為に転送する。移動ホップ（ｈｏｐｓ ｔｏ ｇｏ）の値が「０」である場合、受信側ノードはＮｏｔｉｆｙメッセージを送信することによってＰｕｓｈ（プッシュ）更新の第２段階を開始する。第２段階では、Ｎｏｔｉｆｙメッセージは、そのラベルが漸次的に仮想空間の主題に近くなるノードに連続して転送される。より近いラベルをもつノードが発見されない場合、必要に応じ、最後に発見されたノードのリンクが更新される。これは、例えば、それがまだ確立されていない短距離リンクを有していないためなど、それ以外の場合それが特定の主題ノードを発見できないときにつねに当てはまる。また最後に発見されたノードは、潜在的にそのリンク集合も改善できるであろうノードに追加のＮｏｔｉｆｙメッセージを送信する。
【０１１８】
図１３のＰｕｓｈ（プッシュ）更新の第１の段階を参照すると、入信Ｐｕｓｈ（プッシュ）メッセージを処理するには以下のステップが必要となる。
【０１１９】
ステップ１３００：ノードはＰｕｓｈ（プッシュ）メッセージを受信する。Ｐｕｓｈ（プッシュ）メッセージは、開始側ノードのラベルとアドレスをｓｕｂｊｅｃｔノードとして含み、フィールドｈｏｐｓ ｔｏ ｇｏ（移動ホップ）に値を有する。
【０１２０】
ステップ１３０５：受信側ノードはそのブートストラップリンクの中からリンクを無作為に選択し、選択されたリンクによって特定されるノードのアドレスを次のメッセージのｆｏｒｗａｒｄ（転送）アドレスとして入力する。
【０１２１】
ステップ１３１０と１３１５：受信側ノードはフィールドｈｏｐｓ ｔｏ ｇｏ（移動ホップ）の値を１だけ減少させ、ｈｏｐｓ ｔｏ ｇｏ（移動ホップ）の減少した値が依然としてゼロより大きいかどうかをチェックする。
【０１２２】
ステップ１３２０：減少した値が依然としてゼロより大きい場合、ノードはＰｕｓｈ（プッシュ）メッセージをそれが入力したｆｏｒｗａｒｄ（転送）アドレスに転送する。
【０１２３】
ステップ１３２５：値がゼロである場合、ノードは、代わりに、（受信されたＰｕｓｈ（プッシュ）メッセージに指定される）開始側ノードのラベルとアドレスをＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔ（主題ノード）として入力し、それが入力したｆｏｒｗａｒｄ（転送）アドレスにＮｏｔｉｆｙメッセージを送信する。
【０１２４】
図１４を参照すると、Ｐｕｓｈ（プッシュ）更新を処理し、Ｎｏｔｉｆｙメッセージを処理する第２の段階は以下のステップを伴なう。
【０１２５】
ステップ１４００：ノードは、ｓｕｂｊｅｃｔノードとしてノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを受信する。
【０１２６】
ステップ１４０１：受信側ノードは、Ｎｏｔｉｆｙメッセージのｓｕｂｊｅｃｔが受信側ノードと同じラベルを有するかどうかをチェックする。
【０１２７】
ステップ１４０２：そうである場合は、受信側ノードはＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔが受信側ノードと同じアドレスを有するかどうかをチェックする。その場合、それは追加の処置を講じない。
【０１２８】
しかしながらＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔが受信側ノードと同じラベルの付いているが、受信側ノードとは異なるアドレスのノードである場合、２つのイベントが発生する。第１に（ステップ１４０３）受信側ノードは入信Ｎｏｔｉｆｙ（通信）メッセージの主題ノードに、主題として受信側ノードの自身の短距離リンクのリストから無作為に選ばれたノードを指定するＮｏｔｉｆｙメッセージを送信する。第２に、ステップ１４０４は、二次ネットワークによる動作のためにＮｏｔｉｆｙ（通知）メッセージを作成させる。しかしながら、受信側ノードはこのようなメッセージを直接的に作成することはできない。一般的には、通信網上での異なる仮想ネットワーク間でメッセージを送信するのを回避することが好まれるが、主要な問題は受信側ノードが二次ネットワークのそれ自体のノードのアドレスだけではなく、ｓｕｂｊｅｃｔノードに関連する二次ノードのノードアドレスも必要とするという点である。受信側ノードはこのアドレスを持っていない。したがって、２段階プロセスが使用される。
【０１２９】
第１に、受信側ノードは、入信Ｎｏｔｉｆｙメッセージの中の主題として指定される特別な一次ネットワークのノードにＣｒｏｓｓＮｏｔｉｆｙメッセージを送信する。このメッセージは以下のものを含む。
【０１３０】
・受信側ノード（つまり、入信（一次ネットワーク）メッセージを受信したノード）のアドレスに設定されたｓｅｎｄｅｒアドレス
・入信Ｎｏｔｉｆｙメッセージに含まれるアドレスに設定されたｒｅｃｅｉｖｅｒ（つまり宛て先）アドレス
・受信側ノードと関連付けられる二次ネットワークのノードのアドレスに設定されるｓｕｂｊｅｃｔアドレス
最初の２つのアドレスが一次ネットワーク上のノードのアドレスであり、第３のアドレスが二次ネットワーク上のノードのアドレスであることに注意する。
【０１３１】
第２に、ＣｒｏｓｓＮｏｔｉｆｙメッセージを受信する一次ネットワークのノードは、実質的には、それを二次ネットワークの関連するノードに転送する。必要ならば、転送側ノードはメッセージを二次ネットワークで使用されているフォーマットにフォーマットし直し、（一次ネットワーク）ｒｅｃｅｉｖｅｒアドレスを二次ネットワークの関連するノードのアドレスで置換できるであろう。メッセージは、それから、まさに図３に示されているように処理されるであろう。我々が「実質的には」という理由は、実際には、ＣｒｏｓｓＮｏｔｉｆｙメッセージを受信する一次ネットワークのノードだけが二次ネットワークのその関連するノードに、ＣｒｏｓｓＮｏｔｉｆｙメッセージのｓｕｂｊｅｃｔフィールドに指定されるアドレスを含む簡略で局所的なメッセージを送信することが好まれるからである。その場合、図３のプロセスは、ｎｏｔｉｆｙｌｅｖｅｌを適切な値に設定するステップを含むように修正されるであろう。
【０１３２】
このプロセスは、ボックスがノードを表し、矢印がメッセージを表す図１５を参照して例によって図解される。一次ネットワークのノードＰ１が、図１４のステップ１４００で、一次ネットワークのノードＰ２のラベルＬP2とアドレスＡP2をｓｕｂｊｅｃｔとして含むＮｏｔｉｆｙ（通知メッセージ）を受信すると仮定する。ノードＰ１では、主題ノードがＰ１と同じラベルを有する（つまりＬP1＝ＬP2）が、別のアドレス（ＡP1≠ＡP2）を有することが認識される（図１４のステップ１４０１、１４０２）。ノードＰ１は、その二次ネットワークノードＳ１のアドレスＡS1を知っており、（図１４のステップ１４０４で）送信者アドレスＡP1、受信者アドレスＡP2、及び主題アドレスＡS1でＣｒｏｓｓＮｏｔｉｆｙメッセージを作成する。このメッセージは一次ネットワークのノードＰ２で受信され、これは、アドレスＡS1で局所通知メッセージを二次ネットワークの関連するノードＳ２に送信する。代わりに、二次ネットワークのノードＳ２は、ＬｏｃａｌＮｏｔｉｆｙメッセージの受信時に、図３のプロセスに従ってそれ自体リンクを作成する代わりに、それがノードＳ１に送信し、それ自体を主題として指定する（図１２の点線によって示される）（二次ネットワークの）追加のＮｏｔｉｆｙメッセージを作成できるであろう。Ｎｏｔｉｆｙメッセージは、それから、図３のプロセスを使用するノードＳ１で処理される。このオプションは追加のメッセージを必要とするが、図３のプロセスが実行されるようになると、Ｎｏｔｉｆｙメッセージが、そのアドレスがメッセージのｓｕｂｊｅｃｔフィールド内にあるノードによって実際に送信され、ｓｕｂｊｅｃｔノードがこのようにして依然として存在しているとして本質的に確認されるという利点を有する。
【０１３３】
いま図１４ステップ、１４０５に戻ると受信側ノードはｓｕｂｊｅｃｔノードのラベルを座標に変換し、それが記録した短距離リンクの内のどれが、その座標が仮想空間内のｓｕｂｊｅｃｔノードの座標にもっとも近いノードラベルにつながるのかを計算する。当該ノードはｎｅａｒｅｓｔノードと指定される。
【０１３４】
ステップ１４１５：受信側ノードは自身の座標とｓｕｂｊｅｃｔノードの座標の間の距離を、ｎｅａｒｅｓｔノードの座標とｓｕｂｊｅｃｔノードの座標の間の距離と比較する。
【０１３５】
ステップ１４１５では、受信側ノードとｓｕｂｊｅｃｔノードの間の距離が同じまたは少ないことが判明すると、受信側ノードはｓｕｂｊｅｃｔノードのラベルとアドレスを自身の短距離リンク集合（（ステップ１４２０）。このプロセスは、図１６を参照してさらに説明される）の中のリンクとして追加し、ｓｕｂｊｅｃｔノードに受信側ノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを送信し（ステップ（１４３０）、ｎｅａｒｅｓｔノードに、ｓｕｂｊｅｃｔのノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを送信する（ステップ１４３５）。
【０１３６】
ステップ１４１５で、最も近いノードとｓｕｂｊｅｃｔノードの間の距離がより大きいと判明すると、受信側ノードは、それがｎｅａｒｅｓｔノードにｓｕｂｊｅｃｔノードのラベルとアドレスを含むＮｏｔｉｆｙメッセージを送信するという点でステップ１４３５に戻る。
【０１３７】
図１６は、ノードが、その短距離リンクを更新するときにどのように動作するのかを詳細に示している。それは新しいリンクをその短距離リンクに追加し、このリンクに代わられるすべての短距離リンクを削除する。
【０１３８】
図１６を参照すると、例えば図１４のステップ１４２０の結果として、ノードは新しいリンクをその短距離リンクに追加する必要がある。
【０１３９】
ステップ１６００：更新ノード（すなわち、その短距離リンク集合に対して更新を行うノード）は、新しいリンクのためのノードのアドレスを有する。
【０１４０】
ステップ１６００：更新ノードは、更新ノードに対してより新しいノードにさらに近いノードに関するすべての既存のリンクを特定する。これらの特定されたリンクは入れ替えられなければならない。これらのリンクを特定するために更新ノードは、各既存のリンクに、新しいノードの座標とその既存のリンクで指定されるノードの座標の間の距離を計算する。それは、これらの距離のそれぞれを自身の座標とそれぞれの既存のリストに指定されるノードの座標の間の距離と比較する。
【０１４１】
ステップ１６１０：新しいノードに関する距離が更新ノードに関する距離より短いすべてのリンクは短距離リンクから削除される。
【０１４２】
ステップ１６２０：更新ノードは、その短距離リンクに新しいノードのためのリンクを追加する。
【図面の簡単な説明】
【０１４３】
【図１】本発明のある実施形態で使用されるコンピュータのブロック図である。
【図１Ａ】一次仮想ネットワークと二次仮想ネットワークを使用するデータ検索動作を示すフローチャートである。
【図２】コンピュータネットワークのノード間のリンクの管理の概略図である。
【図３】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図４】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図５】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図６】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図７】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図８】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図９】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１０】二次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１１】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１２】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１３】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１４】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【図１５】図１４に描かれているプロセスの間のメッセージの流れを描く概略図である。
【図１６】一次仮想ネットワークのノードの動作の態様を示すフローチャートである。
【特許請求の範囲】
【請求項１】
それぞれのノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを有する、複数のノードを有する仮想ネットワークを操作する方法であって、
（ｉ）第１のノードと第２のノードの間のリンクを要求するメッセージを受信することと、
（ｉｉ）前記第１のノードと第２のノードの両方がそれぞれのケースで、前記所定数未満であるいくつかのアドレスをそのリストの中に有するかどうかを判断することと、
（ｉｉｉ）この条件が満たされた場合に、前記第１のノードの前記アドレスを前記第２のノードの前記リストに挿入し、前記第２のノードの前記アドレスを前記第１のノードの前記リストに挿入することと、
（ｉｖ）この条件が満たされない場合に、前記第１のノードが、前記所定数より少なくとも２少ないいくつかのアドレスをそのリストに有するかどうかを判断し、そうである場合、
（ａ）第３のノードのアドレスを前記第２のノードの前記リストから選択することと、
（ｂ）前記第２のリストの前記リストから前記第３のノードの前記アドレスを削除することと、
（ｃ）前記第３のノードの前記リストから前記第２のノードの前記アドレスを削除することと、
（ｄ）前記第２のノードの前記アドレスを前記第１のノードの前記リストに挿入し、前記第３のノードの前期アドレスを前記第１のノードの前記リストに挿入することと、
（ｅ）前記第１のノードの前記アドレスを前記第２のノードの前記リストに挿入し、前記第１のノードの前記アドレスを前記第３のノードの前記リストに挿入することと、
を含む、方法。
【請求項２】
リンクを要求する前記メッセージが前記第１のノードで受信され、ステップ（ｉｉｉ）で、
前記第２のノードの前記アドレスが、それが未確認であることを示すマーカが付随する前記第１のノードの前記リストに挿入され、
前記第２のノードに前記第１のノードの前記アドレスを前記第２のノードの前記リンクに追加するように要求するメッセージが前記第１のノードから前記第２のノードに送信され、
前記第２のノードで、前記アドレスがこのように追加され、確認のメッセージが前記第１のノードに送信され、
前記第１のノードで、肯定応答の前記メッセージの受信時に、前記「未確認」マーカが削除される、
請求項１に記載の方法。
【請求項３】
ノードが、それがそのリストに指定されたノードのアドレスを追加するように要求するメッセージの受信時に、最初に前記指定されたノードに、前記指定されたノードの前記リストのコピーを要求するメッセージを送信し、次にそれが前記指定されたノードから、前記要求を受信する前記ノードの前記アドレスを含むリストを受信する場合にだけ前記追加要求に従う、請求項２に記載の方法。
【請求項４】
リンクを要求する前記メッセージが前記第１のノードで受信され、
前記第１のノードは前記第２のノードに前記第２のノードの前記リストのコピーに対する要求を送信し、
前記第２のノードは前記第１のノードに前記要求されたコピーを送信し、
第３のノードの前記アドレスを前記リストから選択するステップ（ｉｖ）（ａ）が前記第１のノードで実行され、
ステップ（ｉｖ）の（ａ）および（ｂ）が、
前記第１のノードが前記第２のノードの前記アドレス及び前記第３のノードの前記アドレスを前記第１のノードの前記リストに追加し、それぞれのケースでそれが未確認であることを示すマーカが付随し、
前記第１のノードが前記第２のノードに、それがそのリストから前記第３のノードの前記リストを削除し、それを前記第１のノードの前記アドレスで置き換えることを要求するメッセージを送信し、
前記第１のノードが前記第３のノードに、それがそのリストから前記第２のノードの前記アドレスを削除し、それを前記第１のノードの前記アドレスで置き換えることを要求するメッセージを送信し、
前記第２のノードは、このようなメッセージの受信時にそのリストから前記第３のノードの前記アドレスを削除し、それを前記第１のノードの前記アドレスで置き換え、前記第１のノードに確認のメッセージを送信し、
前記第３のノードは、このようなメッセージの受信時にそのリストから前記第２のノードの前記アドレスを削除し、それを前記第１のノードの前記アドレスで置き換え、前記第１のノードに確認のメッセージを送信し、
前記第１のノードが前記第２のノードまたは前記第３のノードから前記確認のメッセージを受信すると、それぞれの「未確認」マーカをそのリストから削除する、
という点で実行される、請求項１から３のいずれか１項に記載の方法。
【請求項５】
ノードが、それが別のノードの前記アドレスをそのリストから削除し、それを指定されたノードのアドレスで置き換えることを要求するメッセージの受信時に、最初に前記指定されたノードに、前記指定されたノードの前記リストのコピーを要求するメッセージを送信し、それが、前記要求を受信する前記ノードの前記アドレスを含むリストを前記指定されたノードから受信する場合にだけ前記要求に従う、請求項４に記載の方法。
【請求項６】
前記指定されたノードに対する前記リスト要求メッセージと、このようなメッセージに対する応答が、前記リスト要求メッセージを送信する前記ノードの前記アドレスが前記指定されたノードに伝達されないように中間ノードを介して送信される、請求項３または５に記載の方法。
【請求項７】
各ノードが、少なくとも１つのスペアリンクを記憶するための手段も有し、
第１のノードと第２のノードの間のリンクを、前記第１のノードがそのリストの中に前記所定数に等しいいくつかのアドレスを有するときに要求するメッセージの受信時に、前記スペアリンク記憶装置に前記第２のノードのアドレスを挿入することと、
前記第１のノードと別のノードの間のリンクを要求する後のメッセージの受信時に、前記第１のノードの前記スペアリンク記憶手段から取り出される前記アドレスまたは１つのアドレスにそのメッセージを転送することと、
を含む、請求項１から６のいずれか１項に記載の方法。
【請求項８】
各ノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを含む記憶手段と、処理手段とを有する複数のノードを有する仮想ネットワークであって、前記処理手段が、請求項１から７のいずれか１項に記載の方法を実行するために動作中配列される仮想ネットワーク。
【請求項９】
仮想ネットワークのノードであって、前記ノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを含む記憶手段と、
メッセージを受信する、
前記リストの内容についての情報を要求するメッセージに応える、
前記リストからアドレスを削除するために受信された要求に従う、
前記リストへのアドレスの挿入を要求するメッセージに従う、
動作を実行するようにプログラミングされる処理手段によって定義され、
前記ノードと第２のノードの間にリンクを要求するメッセージの受信に応えて、
（Ａ）そのリストの前記コンテンツについての情報を要求する第２のノードに対するメッセージを作成する、
（Ｂ）前記第１のノードと第２のノードの両方が、それぞれのケースで、前記所定数未満であるいくつかのアドレスをそのリストの中に有するかどうかを判断する、
（Ｃ）この条件が満たされる場合に、前記第２のノードの前記アドレスをそのリストに挿入し、前記第２のノードに前記ノードの前記アドレスをそのリストに追加するように要求する前記第２のノードに対するメッセージを作成する、
（Ｄ）この条件が満たされない場合に、前記ノードが前記所定数より少なくとも２少ないいくつかのアドレスをそのリストの中に有するかどうかを判断し、そうである場合には、
（ａ）第３のノードの前記アドレスを前記第２のノードの前記リストから選択し、
（ｂ）前記第２のノードの前記アドレスを前記第１のノードの前記リストに挿入し、前記第３のノードの前記アドレスを前記第１のノードの前記リストに挿入し、
（ｃ）前記第２のノードの前記リストからの前記第３のノードの前記アドレスの前記削除及び前記ノードの前記アドレスの挿入を要求する、前記第２のノードに対するメッセージを作成し、
（ｄ）前記第３のノードの前記リストからの前記第２のノードの前記アドレスの前記削除及び前記ノードの前記アドレスの挿入を要求する、前記第３のノードに対するメッセージを作成するノード。
【請求項１】
それぞれのノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを有する、複数のノードを有する仮想ネットワークを操作する方法であって、
（ｉ）第１のノードと第２のノードの間のリンクを要求するメッセージを受信することと、
（ｉｉ）前記第１のノードと第２のノードの両方がそれぞれのケースで、前記所定数未満であるいくつかのアドレスをそのリストの中に有するかどうかを判断することと、
（ｉｉｉ）この条件が満たされた場合に、前記第１のノードの前記アドレスを前記第２のノードの前記リストに挿入し、前記第２のノードの前記アドレスを前記第１のノードの前記リストに挿入することと、
（ｉｖ）この条件が満たされない場合に、前記第１のノードが、前記所定数より少なくとも２少ないいくつかのアドレスをそのリストに有するかどうかを判断し、そうである場合、
（ａ）第３のノードのアドレスを前記第２のノードの前記リストから選択することと、
（ｂ）前記第２のリストの前記リストから前記第３のノードの前記アドレスを削除することと、
（ｃ）前記第３のノードの前記リストから前記第２のノードの前記アドレスを削除することと、
（ｄ）前記第２のノードの前記アドレスを前記第１のノードの前記リストに挿入し、前記第３のノードの前期アドレスを前記第１のノードの前記リストに挿入することと、
（ｅ）前記第１のノードの前記アドレスを前記第２のノードの前記リストに挿入し、前記第１のノードの前記アドレスを前記第３のノードの前記リストに挿入することと、
を含む、方法。
【請求項２】
リンクを要求する前記メッセージが前記第１のノードで受信され、ステップ（ｉｉｉ）で、
前記第２のノードの前記アドレスが、それが未確認であることを示すマーカが付随する前記第１のノードの前記リストに挿入され、
前記第２のノードに前記第１のノードの前記アドレスを前記第２のノードの前記リンクに追加するように要求するメッセージが前記第１のノードから前記第２のノードに送信され、
前記第２のノードで、前記アドレスがこのように追加され、確認のメッセージが前記第１のノードに送信され、
前記第１のノードで、肯定応答の前記メッセージの受信時に、前記「未確認」マーカが削除される、
請求項１に記載の方法。
【請求項３】
ノードが、それがそのリストに指定されたノードのアドレスを追加するように要求するメッセージの受信時に、最初に前記指定されたノードに、前記指定されたノードの前記リストのコピーを要求するメッセージを送信し、次にそれが前記指定されたノードから、前記要求を受信する前記ノードの前記アドレスを含むリストを受信する場合にだけ前記追加要求に従う、請求項２に記載の方法。
【請求項４】
リンクを要求する前記メッセージが前記第１のノードで受信され、
前記第１のノードは前記第２のノードに前記第２のノードの前記リストのコピーに対する要求を送信し、
前記第２のノードは前記第１のノードに前記要求されたコピーを送信し、
第３のノードの前記アドレスを前記リストから選択するステップ（ｉｖ）（ａ）が前記第１のノードで実行され、
ステップ（ｉｖ）の（ａ）および（ｂ）が、
前記第１のノードが前記第２のノードの前記アドレス及び前記第３のノードの前記アドレスを前記第１のノードの前記リストに追加し、それぞれのケースでそれが未確認であることを示すマーカが付随し、
前記第１のノードが前記第２のノードに、それがそのリストから前記第３のノードの前記リストを削除し、それを前記第１のノードの前記アドレスで置き換えることを要求するメッセージを送信し、
前記第１のノードが前記第３のノードに、それがそのリストから前記第２のノードの前記アドレスを削除し、それを前記第１のノードの前記アドレスで置き換えることを要求するメッセージを送信し、
前記第２のノードは、このようなメッセージの受信時にそのリストから前記第３のノードの前記アドレスを削除し、それを前記第１のノードの前記アドレスで置き換え、前記第１のノードに確認のメッセージを送信し、
前記第３のノードは、このようなメッセージの受信時にそのリストから前記第２のノードの前記アドレスを削除し、それを前記第１のノードの前記アドレスで置き換え、前記第１のノードに確認のメッセージを送信し、
前記第１のノードが前記第２のノードまたは前記第３のノードから前記確認のメッセージを受信すると、それぞれの「未確認」マーカをそのリストから削除する、
という点で実行される、請求項１から３のいずれか１項に記載の方法。
【請求項５】
ノードが、それが別のノードの前記アドレスをそのリストから削除し、それを指定されたノードのアドレスで置き換えることを要求するメッセージの受信時に、最初に前記指定されたノードに、前記指定されたノードの前記リストのコピーを要求するメッセージを送信し、それが、前記要求を受信する前記ノードの前記アドレスを含むリストを前記指定されたノードから受信する場合にだけ前記要求に従う、請求項４に記載の方法。
【請求項６】
前記指定されたノードに対する前記リスト要求メッセージと、このようなメッセージに対する応答が、前記リスト要求メッセージを送信する前記ノードの前記アドレスが前記指定されたノードに伝達されないように中間ノードを介して送信される、請求項３または５に記載の方法。
【請求項７】
各ノードが、少なくとも１つのスペアリンクを記憶するための手段も有し、
第１のノードと第２のノードの間のリンクを、前記第１のノードがそのリストの中に前記所定数に等しいいくつかのアドレスを有するときに要求するメッセージの受信時に、前記スペアリンク記憶装置に前記第２のノードのアドレスを挿入することと、
前記第１のノードと別のノードの間のリンクを要求する後のメッセージの受信時に、前記第１のノードの前記スペアリンク記憶手段から取り出される前記アドレスまたは１つのアドレスにそのメッセージを転送することと、
を含む、請求項１から６のいずれか１項に記載の方法。
【請求項８】
各ノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを含む記憶手段と、処理手段とを有する複数のノードを有する仮想ネットワークであって、前記処理手段が、請求項１から７のいずれか１項に記載の方法を実行するために動作中配列される仮想ネットワーク。
【請求項９】
仮想ネットワークのノードであって、前記ノードが他のこのようなノードの所定数のアドレスまでを記憶するためのリストを含む記憶手段と、
メッセージを受信する、
前記リストの内容についての情報を要求するメッセージに応える、
前記リストからアドレスを削除するために受信された要求に従う、
前記リストへのアドレスの挿入を要求するメッセージに従う、
動作を実行するようにプログラミングされる処理手段によって定義され、
前記ノードと第２のノードの間にリンクを要求するメッセージの受信に応えて、
（Ａ）そのリストの前記コンテンツについての情報を要求する第２のノードに対するメッセージを作成する、
（Ｂ）前記第１のノードと第２のノードの両方が、それぞれのケースで、前記所定数未満であるいくつかのアドレスをそのリストの中に有するかどうかを判断する、
（Ｃ）この条件が満たされる場合に、前記第２のノードの前記アドレスをそのリストに挿入し、前記第２のノードに前記ノードの前記アドレスをそのリストに追加するように要求する前記第２のノードに対するメッセージを作成する、
（Ｄ）この条件が満たされない場合に、前記ノードが前記所定数より少なくとも２少ないいくつかのアドレスをそのリストの中に有するかどうかを判断し、そうである場合には、
（ａ）第３のノードの前記アドレスを前記第２のノードの前記リストから選択し、
（ｂ）前記第２のノードの前記アドレスを前記第１のノードの前記リストに挿入し、前記第３のノードの前記アドレスを前記第１のノードの前記リストに挿入し、
（ｃ）前記第２のノードの前記リストからの前記第３のノードの前記アドレスの前記削除及び前記ノードの前記アドレスの挿入を要求する、前記第２のノードに対するメッセージを作成し、
（ｄ）前記第３のノードの前記リストからの前記第２のノードの前記アドレスの前記削除及び前記ノードの前記アドレスの挿入を要求する、前記第３のノードに対するメッセージを作成するノード。
【図１】
【図１Ａ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１Ａ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公表番号】特表２００７−５０７１４２（Ｐ２００７−５０７１４２Ａ）
【公表日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願番号】特願２００６−５２７４６２（Ｐ２００６−５２７４６２）
【出願日】平成１６年９月１７日（２００４．９．１７）
【国際出願番号】ＰＣＴ／ＧＢ２００４／００４００３
【国際公開番号】ＷＯ２００５／０３２０６９
【国際公開日】平成１７年４月７日（２００５．４．７）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【Ｆターム（参考）】
【公表日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願日】平成１６年９月１７日（２００４．９．１７）
【国際出願番号】ＰＣＴ／ＧＢ２００４／００４００３
【国際公開番号】ＷＯ２００５／０３２０６９
【国際公開日】平成１７年４月７日（２００５．４．７）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【Ｆターム（参考）】
[ Back to top ]