同じラベルに整合する多数のノードを識別するコンピュータネットワーク
ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索動作（32）を実行し、第１の検索手段によって識別されたアドレスに応答して、同じラベルに整合する別のノードのアドレスを識別する第２の検索動作（35）を実行することによって、コンピュータネットワークのノードを検出する。所与のラベルに整合する各ノードは、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をもち、照会メッセージに応答して、リストのアドレスを含むメッセージを戻す。第２の検索動作は、第１の検索手段によって識別されたアドレスに照会メッセージを送り、応答を受信すると、前の照会メッセージへの応答に含まれているアドレスへ別の照会メッセージを反復的に送ることを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータネットワーク、限定はしないが、とくに、ピア ツウ ピア システムのような、とりわけ、中央の記憶または制御を使用しない、分散形システムに関連する情報検索に関する。
【発明の開示】
【課題を解決するための手段】
【０００２】
本発明の１つの態様にしたがうと、ノードを含むコンピュータネットワークであって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索手段と、
−第１の検索手段によって識別されたアドレスを受信し、それに応答して、同じラベルに整合する別のノードのアドレスを識別するように動作可能であるように接続された第２の検索手段とをもち、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索手段が、第１の検索手段によって識別されたアドレスに照会メッセージを送り、応答を受信すると、その照会メッセージへの応答か、または場合によっては、次の照会メッセージへの応答に含まれるアドレスへ照会メッセージを反復的に送るように動作可能なコンピュータネットワークを与える。
【０００３】
別の態様では、本発明は、ノードを含むコンピュータネットワークを動作する方法であって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索動作を行うことと、
−第１の検索手段によって識別されたアドレスに応答して、同じラベルに整合する別のノードのアドレスを識別する第２の検索動作を行うこととを含み、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索動作が、第１の検索手段によって識別されたアドレスに照会メッセージを送り、応答を受信すると、その照会メッセージへの応答か、または場合によっては、後の照会メッセージへの応答に含まれるアドレスへ照会メッセージを反復的に送るように動作可能な方法を与える。
【０００４】
本発明の他の好ましい特徴は、特許請求項に定められている。
ここで、本発明のいくつかの実施形態を、例示的に、添付の図面を参照して記載する。
【発明を実施するための最良の形態】
【０００５】
ノード
この記述では、処理、記憶、および通信能力をもつコンピューティングノードを参照する。コンピューティングノードは、コンピュータまたは他の装置（ここで、各コンピュータは、多数の独立プログラムまたは処理をその上で実行させることに注意すべきである）であるか、またはそのようなプログラムまたは処理である。また、多数の記憶されたデータ項目が、１つのプログラムまたは処理によってサービスされても、このような項目は、別個のノードとしてみなされる。
【０００６】
この記述は、各コンピューティングノードを、例えば、インターネットプロトコル（internet protocol, IP）ネットワークのような遠隔通信ネットワークである、幾つかの通信インフラストラクチャに接続して、メッセージをそれに送ることができることを仮定している。したがって、各コンピューティングノードは、通信インフラストラクチャ内のノードも構成している。
【０００７】
仮想ネットワークに属している仮想ノードも参照する。コンピューティングノードは、それと関係付けられた（恐らくは、異なる仮想ネットワークに属している）２つ以上の仮想ノードをもつことができるので、区別は重要である。その名前が示唆するように、仮想ノードは、物理的な認識において存在せず、むしろ、その存在は、やがて明らかになるように、仮想ノード間のリンク、したがって、それが属している仮想ネットワークを定めている、記憶されたデータによって設定されたものである。
【０００８】
必然的に、仮想ノードは、コンピューティングノードと関係付けられなければならず、それにより、処理、記憶、および通信能力を得る。仮想ノードによるメッセージの送信、受信、および処理に対する参照は、仮想ノードの代わりに、コンピューティングノードによる、このような送信、受信、または処理を指す。
【０００９】
例は、図１に示されている。コンピュータは、通常の構成要素、例えば、プロセッサ１、メモリ２、ディスプレイ３、キーボード４、およびネットワーク10を介して通信するための通信インターフェイス５をもつ。
メモリ２は、オペレーティングシステムおよび他のプログラム（図示されていない）、並びに図示されているテキストファイル20のようなデータファイルを含む。これは、テキストファイル20に対応するラベル21aと、自分自身のアドレス21bとを含む記憶装置21も含む。さらに加えて、これは、アドレスリスト22および支援プログラム23をもち、これらは共に、仮想ネットワークのノードの、コンピュータ上における、存在を定めている。このノードは、アドレス24をもつ。アドレスリスト25および支援プログラム26も示されており、これらは共に、別の仮想ネットワークのノードの、コンピュータ上における、存在を定めている。このノードは、アドレス27をもつ。リスト22、25に記憶されているアドレスは、同じ仮想ネットワーク内の他のノードのアドレスである。
【００１０】
ルックアップシステム
ここで、本発明の応用のたった１つの可能な例である、記載されているルックアップシステムを記載する。このシステムは、ユーザが、コメントをウエブページと関係付けることを可能にする。ユーザは、このページをいつ訪問しても、他のユーザが行ったコメントを見る機会をもっている。コメントは、（例えば、テキストファイルのような）コメントを与えたユーザのコンピュータ上に記憶される。
【００１１】
ウエブページを見ているユーザ（または、むしろ、ユーザのコンピュータ）は、ウエブページのユニバーサルリソースロケータ（universal resource locator, URL）をもち、ユーザがコメントを検索するのを可能にする機構が必要である。
【００１２】
テキストファイルは、コメントを与えたユーザのコンピュータ上に記憶され、国際特許出願第WO 03/034669号[代理人参照番号第A30044号]に記載されているタイプの仮想ネットワークのノードと関係付けられるものか、または、他のウエブページに関するコメントを含む他のテキストファイル、および恐らくは、他の関係のないファイルであってもよい。この仮想ネットワーク（この記述に関連して、一次仮想ネットワーク、または、単に、一次ネットワークと呼ばれる）では、ノードを識別するラベルをもっているならば、そのアドレスを知らなくても、そのノードへメッセージを送ることができる。このタイプのネットワークは、（各ノードに１つの）固有のラベルで機能することができるが、この例では、ラベルは固有ではなく、むしろ、特定のウエブページに関するコメントを含むテキストファイルと関係付けられた全ノードが、同じラベルをもつ。このラベルは、ウエブページのＵＲＬのハッシュ関数である。この仮想ネットワークは、１つのみのノードに到達する検索機構を与える。
【００１３】
テキストファイルは、第２の仮想ネットワークのノードとも関係付けられている。これ（二次仮想ネットワーク）は、１つの特定のウエブページに関するコメントを含むテキストファイルと関係付けられたノードのみを含む。
しかしながら、我々の上述の国際特許出願にしたがって一次ネットワークを使用することが好ましいが、必須ではないことに注意すべきである。実際に、仮想ネットワークを使用することは、全く必須ではなく、その代わりに、ラベルを受信し、それに対応する１つのノードのアドレスを戻す別の一次検索機構を使用してもよい。
【００１４】
コメントを書き込むコンピュータは、図１に示されており、
・一次ネットワーク内に、ラベル21aおよびネットワークアドレス24をもつノードを生成しなければならず、
・二次ネットワーク内に、ネットワークアドレス27をもつノードを生成しなければならない。
【００１５】
先ず、アドレスリスト22がブートストラップリンクを含むことを除いて、アドレスリスト22、25は空である。リスト22が一次ネットワークのいくつかの他のノードのラベルおよびアドレスを含むことと、リスト25が二次ネットワークのいくつかの他のノードのアドレスを含むことを保証するネットワークの自己組織化について別途記載する。さしあたり、これらのラベルおよびアドレスが存在すると仮定して、システムを記載する。
【００１６】
アドレスに関するいくつかの用語は、この点において、順番である。テキストファイル20によって形成されるノード、一次仮想ネットワークのノード、および二次仮想ネットワークのノードは、概念上１つの識別をもつ一方で、自分自身のアドレスをもっている。通信ネットワーク10内の別個のアドレスを各ノードに割り当てることができるが、実際には、これはとくに便利ではない。好ましい実行では、各ノードは、３つの部分から成るアドレスをもつ。すなわち、
・コンピューティングノードの“位置を特定する”インターネットアドレス。例えば、130.146.209.15；
・コンピューティングノードにおける特定の通信ポートの位置を特定するポート番号。ポートは、インターネットアドレスの標準部分である。これらは、例えば、異なる独立のアプリケーションプログラムがメッセージを個別に送受信するのを可能にする。すなわち、各々は、自分自身のポートにおいてメッセージを受信し、他のアプリケーションプログラムに向けられたメッセージを受信しないか、またはそれによって“混乱”させられない。インターネットアドレスとポート番号とを合わせて、（ＴＣＰ／ＩＰのような、使用されている通信プロトコルの一部であるので）ネットワークアドレスと考えることができる。全ての一次および二次ノードのネットワークアドレスは、同じであってもよいが、必ずしも、そうでなくてもよい。例えば、一次ノードへの全メッセージは、二次メッセージが受信されるのと、異なるポートにおいて受信される（これは、このようなメッセージを区別する１つのやり方である）；
・メッセージが向けられた特定のノードの位置を特定するノード識別子（整数値）。例えば、一次ネットワーク上の全てのメッセージが、専用のポートにおいて受信されるとき、各ノードと関係付けられた局所的に固有の識別子が依然として存在する。したがって、多数のノードがあるとき、メッセージが向けられたノードは明らかである。このノード識別子は、アプリケーション別のアドレス拡張部である（標準のインターネットプロトコルの一部ではない）。これは、単に、送られるメッセージ内に含まれている。それを受信する処理は、これを“知り”、このノードの識別子を調べて、メッセージが送られるべきノードを判断する。
【００１７】
両者のノードは同じネットワークアドレスをもつことが可能であるが、必ずしも、そうでなくてもよい。各ノードは、自分自身のポートをもたず（その理由の１つは、使用可能なポートの数が、ある程度制限されるためである）、２つのポート（したがって、２つの異なるネットワークアドレス）、すなわち、一次ネットワークのために１つのポート、二次ネットワークのために１つのポートをもっていてもよい。一般に、多数の二次ネットワークがあり、その全てが同じポートを使用してもよい。
【００１８】
次の記述において、ノードのアドレスの参照は、そのノードの完全なアドレスを指していることを強調しておく。
とくに魅力的なアプローチでは、テキストファイル、一次ノード、二次ノードの全てが同じノード識別子（およびＩＰアドレス）をもち、ポート番号のみが異なるものを与える。このようなアドレス指定プロトコルは、処理の一部を簡潔にする機会を与え、１つのノードのアドレスをもっていて、それと関係付けられた別のノードのアドレスを必要とするとき、別のノードのアドレスは、ルックアップする必要があるのではなく、むしろ、１つのノードのアドレスから推測される。しかしながら、次の記述では、このような簡潔化を行わず、これらの処理をアドレスプロトコルで行なう。
【００１９】
ウエブページを見ているコンピュータは、
・同じハッシュ関数をＵＲＬに適用して、ラベルを得て、
・一次仮想ネットワーク上で（ラベルを含む）照会を送って、１つのノードのアドレスを得て、
・検出されたアドレスを使用して、二次仮想ネットワーク上で照会を送り、二次仮想ネットワーク上の、より多くの（または、全ての）他の全ノードのアドレスを得て、
・これらのアドレスを使用して、表示するためのコメントを検索することによって、
関係付けられたコメントを検索する。
【００２０】
検索コンピュータは、仮想ネットワークのノードを必ずしも含む必要はなく、検索処理を実行するソフトウエアをロードされ、かつ仮想ネットワークのノードがあるコンピュータと通信できるように通信インターフェイスをもつ従来のコンピュータであってもよいことに注意すべきである。この処理は、図１Ａのフローチャートに示されており、次に記載するように、処理を進める。
【００２１】
ステップ３０：ユーザがＵＲＬを入力した（または、ハイパーリンクを呼出した）後で、コンピュータは、対応するウエブページを検索する。このステップは全く従来通りである。
ステップ３１：ハッシュ関数をＵＲＬに適用して、ラベルを得る。我々の以前の国際特許出願に記載されているように、これにはＳＨＡ−１アルゴリズムを使用することができる。
【００２２】
ステップ３２：検索コンピュータのこのラベルおよびネットワークアドレスを含む‘検出’メッセージを、一次ネットワークのノードへ送る。明らかに、コンピュータは、少なくとも1つのこのようなアドレスを保持していなければならない。
ステップ３３：検索コンピュータは、一次ネットワークから‘検出済み’メッセージを受信する。このメッセージは、検出したノードのラベルおよびアドレス、並びに二次ネットワークの関係付けられたノードのアドレスおよびコメントを含む。検出済みメッセージが適正な時間内に受信されないときは、処理を中止するタイムアウト機構が含まれることもある。
【００２３】
ステップ３４：この例では、一次ネットワークは、検出メッセージに含まれているラベルに最も近いラベルをもつノードのラベルとアドレスとを常に戻すように構成されている。したがって、戻されるラベルが、求めているラベルと同じかどうかを調べる検査が行われ、同じでないときは、処理は終了する。“最近（nearest）”の意味の説明について下記を参照すべきである。
【００２４】
ステップ３５：ラベルが整合すると仮定すると、検索コンピュータは、（別途詳しく記載する）処理を実行して、検出済みメッセージによって戻されたアドレスを使用して、二次ネットワークを使用して、別のアドレスを検索する。
ステップ３６：次に、これらのアドレスを使用して、“書込み（posting）”コンピュータから、コメントを含むテキストファイルを検索する。
【００２５】
二次仮想ネットワーク
このネットワークの目的は、ノードのグループを１つの仮想ネットワークへ自己組織化し、その後、これを使用して、グループの一部である全ノードを発見できるようにすることである。主な要件は、結果のネットワークが全ノードを含むことである。別の要件は、ネットワークを生成し、維持するのに必要なシステムロードが、全ノード全体で等しく分散されることである。これは、最も“公平” であるだけでなく（異なるユーザが、資源を分散形アプリケーションに与えるときに重要である）、オーバーロードからシステムを保護するのも助ける。
【００２６】
したがって、ネットワークは、次の特性をもつ。すなわち、
・各ノードによって維持されるリンクの数が、好ましくは、同じである；
・全リンクが双方向である。その結果、ノードへのリンクの数も、各ノードにおいて同じである。これは、ノードが受信し、処理しなければならないメッセージの数に影響を与えるので、重要である；
・これは“フラットな”構造である。ノードは、自分自身を階層的に配置しない。その結果、システムのロードは、全ノード全体で等しく分散される。
各ノードの構造
各ノードは、自分に関係付けられた次に示すデータをもつ：
・他のノードへのいくつかのリンク。各リンクは、単に、別のノードのアドレスである。“確認済み”または“未確認”の状態が、各リンクと関係付けられている。各ノードは、単に最大数のリンクを維持することができ、最大数のリンクは、システム全体のパラメータＬによって与えられる。Ｌの典型的な値は、例えば、６である。このパラメータが、全ノードにおいて同じであることは必須ではないが、それらを違うものにすることによって得られる恩恵はない；
・スペアリンク、または、約言して、スペアのリスト。各スペアは、単に、別のノードのアドレスである。スペアを自己組織化処理によって使用して、仮想ネットワークを構築する。ノードは、ノードについて、それが、ノードに既にリンクしているか、または最大数のリンクを既にもっているために、リンクとして加えることができないことを知らされると、他のノードをスペアとして加える。ノードが維持することができるスペアの数も制限され、システム全体のパラメータＳによって与えられる。Ｓの典型的な値は、例えば、３である。スペアリンクのリストは、通常、必須ではないが、追加の機構を与える際に、非常に有益であり、これによって、局所的に収容できないリンクを、仮想ネットワーク内の他の地点に伝搬することができる。しかしながら、到来する通知メッセージが、二次ネットワークの同じノード（または、非常に少数のノードの中の１つ）に常に到達する場合は、システムにおいて、スペアリンク（または、同様の伝搬機構）を使用することは必要である。
【００２７】
メッセージ
ネットワークへ自己組織化し、何れのノードが所与のネットワークの一部であるかを発見するために、ノードはメッセージを相互に送る。次のタイプのメッセージは、二次ネットワークによって使用される：
・リンク追加（AddLink）メッセージ：
・送信側のアドレス、および、
・受信側のアドレスを含む。
【００２８】
これは、一方のノード（送信側）によって別のノード（受信側）へ送られ、相互リンクを要求する。
・リンク変更（ChangeLink）メッセージ：
・送信側のアドレス、
・受信側のアドレス、および、
・対象のアドレスを含む。
これは、１つのノード（Ｘ）によって別のノード（Ｙ）へ送られ、Ｙに、そのリンクの１つ（Ｚ）を自分自身（Ｘ）へのリンクに変更することを要求する。プロトコルは、Ｘが同様のメッセージをＺへ送って、Ｚに、Ｙへのリンクを自分自身（Ｘ）へのリンクと交換することを要求する。したがって、事実上、Ｘは、ＹとＺとの間の現在のリンクの中に自分自身を挿入することを要求する。
・リンク追加済み（LinkAdded）メッセージ：
・送信側のアドレス、および、
・受信側のアドレスを含む。
【００２９】
これは、ノードに、送信側がそのノードへのリンクをちょうど加えたことを通知するのに使用される。
・リンクエラー（LinkError）メッセージ：
・送信側のアドレス、
・受信側のアドレス、
・対象のアドレス、および、
・エラーコードを含む。
【００３０】
これは、ノードに、そのリンクの１つに問題があると考えられることを通知するのに使用される。例えば、対象のノードが応答しない、またはリンクが相互でないといったことである。これは、エラーのタイプを示すエラーコードを含む。
・リンク（Links）メッセージ：
・送信側のアドレス、
・受信側のアドレス、
・全リンクのアドレス、および
・基準値を含み、
・リンクメッセージは、送信側ノードからのいくつかの他のデータも含むことができる。ウエブページのコメントの例において、これは、関係付けられたコメントのアドレスである。
【００３１】
これは、送信側ノードの全ての現在のリンクを含む。これは、常に、リンク照会メッセージに応答して送られる。参照を使用して、応答される特定の照会を区別することができる。
・リンク照会（LinksQuery）メッセージ：
・送信側のアドレス、
・受信側のアドレス、および、
・基準値を含む。
【００３２】
これは、ノードに、応答に（その現在のリンクを含む）リンクメッセージを送ることを要求するのに使用される。
・通知（Notify）メッセージ：
・送信側のアドレス、
・受信側のアドレス、
・対象のアドレス、および、
・通知レベルを含む。
【００３３】
これは、ノードに、ネットワーク内の別のノードについて通知するのに使用される。通知レベルは、通知メッセージの伝搬を制御して、制限するのに使用される。ここに記載されているように、送信側のアドレスは、使用されないが、デバッグのため、または希望であれば、肯定応答を送るのに役立つ。
【００３４】
二次ネットワークの構築
このシステムは、グループのノードを１つの仮想ネットワークへ自己組織化し、１つのノードのアドレスをもつと、グループ内の他のノードのアドレスを検出することができるようにする。このセクションは、同じ二次ネットワークに属すべきノードが発見されたときに、新しいリンクがどのように生成されるかを記載している。ここで、２つの部分を区別することができる。
【００３５】
同じ二次ネットワークに属すべきノードの対の発見。ノードを同じネットワークにグループ化するための基準は、アプリケーション別である。ウエブページの注釈の例において、同じＵＲＬに関するコメントを表わす全ノードは、二次ネットワーク内で一緒にグループ化されるべきである。一緒にグループ化されるべきノードをどのように発見するかも、アプリケーション別である。簡潔に例を与える。
【００３６】
ノードの発見の結果として、二次ネットワークを更新／拡張する。同じ二次ネットワークに属すべき１対のノードが発見されると、その結果として、システムは１つ以上の新しいリンクを構築する。新しいリンクは、１対のノードの間に必ずしもあるわけではないが、例えば、これらの２つのノードがリンクするノード間にある。新しいリンクがどのように生成されるかは別途詳しく記載する。
【００３７】
最初の通知メッセージ
二次ネットワークの組織化は、グループの既存のメンバーと新しいメンバーとを識別する、到来する‘通知’メッセージの存在を予め想定する（しかしながら、早い段階では、何れかのノードがまだグループの一部分でない可能性があり、一方で、自己組織化処理の後の方では、両者のノードは既にグループの一部である）。二次ネットワークに、それに属すべきノードについて通知するかは、システムの別の部分次第である。それを行うことができる種々の方法がある。ここで、二次ネットワークを、我々の以前の国際特許出願に記載されているタイプの一次ネットワークと共に使用して、これがどのように行われるかについての例を与える。ウエブページの注釈の例において、各コメントは、対応するウエブページのＵＲＬに基づくラベルのもとで、一次ネットワーク内のノードとして、自分自身を公開している。このようにして、一次ネットワークを使用して、所与のＵＲＬがあるときは、このコメントをルックアップすることができる。所与のＵＲＬの全てのコメントを示すために、各コメントは、それと関係付けられた二次ネットワークのノードももつ。同じＵＲＬに関するコメントに対応するノードは、そのＵＲＬに特定の二次ネットワークへ自己組織化する。このようにして、一次ネットワークを使用して、ＵＲＬに関する１つのコメントを検出すると、二次ネットワークを使用して、同じＵＲＬに関する別のコメントを検出することができる。
【００３８】
したがって、この場合に、一緒にグループ化されるべき二次ネットワークの各ノードは、一次ネットワークにおいて、同じラベルのもとで公開される。一次ネットワークにおいて、ノードが‘プッシュ’更新を定期的に実行して、ノードが、同じラベルのもとで公開されている別のノードに気付くときは必ず、必要な通知メッセージが生成される変更を含めて、リンクを構築し、維持する機構を、別途記載する。
【００３９】
通知メッセージの処理
ノードが、まだリンクしていないノードについての通知メッセージを受信すると、次の１つが行われる。
受信ノードは、最大数の許可されたリンクを既にもっているときは、それを（既にスペアとしてもっていないときは）スペアとして加える。これを行なうときに、ノードが、スペアの最大数を越えると、１つのスペアを取り除く。取り除いたスペアに通知メッセージを送ることもある。通知メッセージを送るかどうかは、通知レベルの値に依存する。通知レベルを下げるたびに、メッセージを永久に伝搬するのを防ぐ。
【００４０】
そうではなくて、対象ノードが、最大数のリンクをまだもっていないときは、受信ノードは、両ノード間の相互リンクを生成することを試みる。これは、図２の（ａ）および（ｂ）に示されている。ここで、Ｌ＝３であり、ノード１はノード２についての通知メッセージを受信する。両ノードは、リンクを２つだけもっているので、ノード１とノード２との間にリンクが生成される。
そうではなくて、対象ノードが、リンクの最大数を既にもっているときは、両ノード間に相互リンクを簡単に生成することができない。したがって、受信ノードが既存のリンクに自分自身を挿入するのを試みることが行われる。これは、図２の（ｃ）および（ｄ）に示されている。ここでは、ノード２とノード３との間のリンクが切断されるが、２つの新しいリンク、すなわち、ノード１とノード２との間のリンクと、ノード１とノード３との間のリンクとによって置換される。したがって、リンクの総数が１つ増加する。ノード２およびノード３が最大数のリンクを既にもっていても、これは行われる。しかしながら、ノード１は、これを成功させるために、２つの新しいリンクを生成できることが必要である。この処理は、図３ないし９のフローチャートにおいてさらに詳しく記載する。
【００４１】
図３は、ノードが、到来する通知メッセージをどのように処理するかを示している。ここでは、新しいリンクを生成すべきかどうか、および生成するときは、どのように（新しいリンクを加えることによって、または既存のリンクを２つのリンクへ変えることによって）生成するかを決定する。新しいリンクが生成されないときは、スペアの組を更新して、別の通知メッセージを送ってもよい。
【００４２】
ステップ300において、通知メッセージが受信される。通知メッセージは、それ（送信側）へ送ったノードのアドレス、対象ノードのアドレス、および伝搬制限値、すなわち通知レベルを含む。受信ノードは、最初に、それが新しいリンクを設定する余地をもっているかどうかを検査し（301）、もっているときは、それが対象ノードへのリンクを既にもっているかどうかを検査する（302）。もっていないときは、受信ノードは、対象ノードとのリンクを設定することを試みる。
【００４３】
ステップ303において、受信ノードは、リンク照会メッセージを対象ノードへ送り、ステップ304において、応答を待つ。応答、すなわち、リンクメッセージが受信されると、受信ノードは、（それが、途中で、他のメッセージを受信し、処理し、その結果として、リンクを生成した場合は）それが新しいリンクを設定する余地を依然としてもっているかどうかを再び検査する（305）。そうであるときは、次に、受信ノードは、受信したリンクメッセージを調べて、対象ノードが新しいリンクを設定する余地をもっているかどうかを検査する（306）。対象ノードがもっているときは、次に、ステップ307および308において、受信ノードは、（“未確認”と示されている）対象ノードのアドレスを、自分のリンクリストへ加え、リンク追加メッセージを対象ノードへ送る。
【００４４】
しかしながら、ステップ306において、対象ノードが別のリンクを受け入れることができないと判断されると、受信ノードは、図２を参照して既に記載したように、自分自身を既存のリンクへ挿入することを試みる。第１のステップ（309）では、受信ノードが２つのリンクのための余地をもっているかどうかを検査し、もっていないときは、処理は終了する。しかしながら、もっているときは、受信ノードは、受信したリンクメッセージ内のリンクリストから無作為にリンク（しかし、受信ノードがリンクを既にもっているノードではない）、すなわち、対象ノードと、ここでは、他のノードと呼ばれる別のノードとの間のリンクを選択する。次に、受信ノードは：
（未確認の）対象ノードのアドレスをリンクリスト追加し（311）；
（未確認の）その他のノードのアドレスをリンクのリストに追加し（312）；
他ノードのアドレスを含むリンク変更メッセージを対象ノードへ送り（313）；
対象ノードのアドレスを含むリンク変更メッセージを他のノードへ送る（314）ことによって、自分自身をこのリンク内へ挿入することを試みる。
【００４５】
しかしながら、ステップ301において、受信ノードがリンクを追加する余地をもっていないと判断されるか、またはステップ302において、受信ノードが対象ノードへのリンクを既にもっていると判断されるときは、処理は、受信ノードがリンクをスペアリンクのリストに追加するかどうかを調べる。ステップ315において、対象ノードがスペアリスト内に既にあることが検出されたときは、処理は終了する。316において、リンクをスペアリストに追加する余地があるかどうかを検査し、あるときは、317において、これを適切に追加する。ないときは、ステップ318において、スペアリンクの中の既存の１つを無作為に選択し、ステップ319において、取り除き、ステップ317において、これを対象ノードへのリンクと置換する。さらに加えて、ステップ320において、可変の通知レベルがデクレメントされ、（ステップ321において）それが依然としてゼロ以外であるときは、ステップ322において、通知レベルのこの新しい値をもつ元の通知メッセージを、無作為に選択された既存のリンクによって指示された（置換と呼ばれる）ノードへ送る。
【００４６】
この処理の効果は、リンクの全ての組を既にもっているノードＡが、自分に対象ノードＢへのリンクを要求する通知メッセージを受信するとき、Ｂのアドレスがスペアリンクとして記録されることである。このリンクは、Ａのスペアリンクリストがいっぱいになるまで、休止状態を維持する。次に、Ａが、自分にノードＣへのリンクを要求する、後の通知メッセージを受信し、ステップ318において、ノードＢへのスペアリンクが選択されると、ステップ322において生成された新しい通知メッセージは、事実上、ノードＢからノードＣへのリンクを生成するためのノードＢへの要求である。
【００４７】
フローチャート上には示されていないが、リンクが未確認であり、かつ受信ノードが、所定の時間期間内で、（図６を参照して別途記載されるように、リンク追加済みメッセージによって）確認を受信しないときは、未確認のリンクを削除する機構も与えられる。受信ノードは、依然として“未確認”状態のリンクをもっているとき、リンク照会メッセージに応答して、これらの未確認リンクを（もちろん、確認済みのリンクも）戻し、他のノードが、それがリンクの設定を試みていることを確認できるようにすることに注意すべきである。
【００４８】
図３では、ステップ305および309が“ノー”であるときは、処理の終了に導かれるが、希望であれば、これらを、ステップ315において始まる、効率が僅かに向上した“スペアリンク”処理へルート設定してもよい。
ステップ309ないし314では、ノードは対象ノードのリンクの1つを効率的に切断し、それらの間に自分自身を挿入する。フローチャートに示されていない別の可能なオプションでは、ノードが、（もちろん、それが少なくとも1つのリンクをもっていると仮定して）自分自身のリンクの１つを切断し、それらの間に対象ノードを挿入する。このオプションは、実行されるときは、ステップ301から‘ノー’で出た後で、直ちに試みられる。第１に、受信ノードは、対象ノードがＬ−１よりも少ないリンクをもつかどうかを検査して、（他のノードへの）自分自身のリンクの１つを無作為に選択して、これを、対象リンクへの未確認のリンクと置換して、リンク追加メッセージを対象ノードへ送る必要がある。対象ノードと他のノードとの間に双方向リンクを設定するために、それは、次に、（ａ）未確認リンクとして他のノードをリンクリストへ無条件で追加することを対象ノードに要求する特別のリンク追加メッセージを対象ノードへ送り、（ｂ）受信ノードを古いリンクとして取り除き、対象ノードを新しいリンクとして追加するために指定する特別のリンク変更メッセージを、他のノードへ送る。このオプションは、ステップ309ないし314に加えて、またはこれらに代わって含むことができる。
【００４９】
受信ノードが自分自身のリンクの１つを切断する別のオプションでは、（最初に、対象ノードがＬ−１よりも少ないリンクをもつことを確かめた）受信ノードが、自分自身を対象ノードとして指定した通知メッセージを、対象ノードに送る。これは、同じ結果をもつが、僅かに大きいメッセージングオーバーヘッドを含む。
【００５０】
図４は、ノードが、到来するリンク変更メッセージをどのように処理するかを示している。これらのメッセージは、通知メッセージを受信したノードＸが、既存のリンクを２つの新しいものに変えたいときに（図２参照）送られる。受信ノードＹは、400において、対象ノードとしてノードＺをもつ通知メッセージ、すなわち、ノードＹに、ノードＺへの既存のリンクを、ノードＸへのリンクと置換することを求める通知メッセージを受信する。それがＸへのリンクを既にもっているときは（401）終了し、一方で、ノードＹがノードＺへのリンクを実際はもっていないときは（402）、ノードＹはエラーメッセージを送信側Ｘへ送る（403）。
【００５１】
全てが適切であるならば、ノードＹはリンク照会メッセージを送信側Ｘへ送って（404）、応答して、送信側Ｘからのリンクメッセージを待ち（405）、送信側Ｘが、対象リンクを変える前に生成すべきであった２つの新しいリンクを実際に生成したかどうかを検査する。これらの検査（406、407）がイエスであるときは、受信ノードは、Ｚへのリンクを取り除き（408）、Ｘを確認済みリンクとして追加し（409）、リンク追加済みメッセージを送信側Ｘへ戻す（410）。
【００５２】
図５は、ノードが、到来するリンク追加メッセージをどのように処理するかを示している。これらのメッセージは、ノードが、ノードとの新しいリンクを生成したいときに（図１参照）送られる。501において、メッセージを受信し、ステップ502において、ノードは、それが別のリンクのための余地をもっているかどうかを検査し、もっていないときは、503において、エラーメッセージを戻す。そうでなければ、それは、リンク照会メッセージを送信側へ送り（504）、送信ノードからの応答のリンクメッセージを待ち（505）、506において、送信ノードが受信ノードへのリンクを実際に生成したかを検査する。ノーであるときは、リンクを追加するのを断って、終了するが、イエスであるときは、送信側ノードを確認済みリンクとして追加し（507）、確認によってリンク追加済みメッセージを送信側へ戻す（508）。
【００５３】
図６は、ノードが、到来するリンク追加済みメッセージをどのように処理するかを示している。これらのメッセージは、リンク変更またはリンク追加メッセージに応答して、別のノードが、受信ノードへのリンクを受け入れたときに送られる。600において、リンクが受け入れたことを示すリンク追加済みメッセージが受信されると、ステップ601において、その状態が“確認済み”に変更される。次に、リンクは、それが（リンク変更メッセージに応答して）新しいリンクに変更されるか、リンクが切断されるまで、維持される。
【００５４】
図７は、ノードが、到来するリンクエラーメッセージをどのように処理するかを示している。これらのメッセージは、（リンク変更メッセージまたはリンク追加メッセージによって）受信側ノードが相互リンクを要求した後で、ノードが受信側ノードへのリンクを生成できないときか、またはリンクが切断されていると考えられるときに（他方の端部のノードがメッセージに応答しないか、またはリンクが相互でないとき）、送られる。切断されたリンクは、自己組織化処理によってではなく、（別途記載するように）クライアントが二次ネットワークを横切るときに検出される。
【００５５】
ステップ700においてメッセージを受信した後で、メッセージが、受信側ノードが未確認リンクをもつノードに関するものであるかどうかが判断される（701）。そうであって、かつ、それが、要求されたリンクを生成することに失敗したことを示すエラーコードを保持しているときは（702）、703において、リンクは取り除かれる。しかしながら、メッセージが、受信ノードが未確認のリンクをもつノードに関するものでないときは、受信ノードは、リンク照会メッセージを対象ノードへ送り（704）、応答のリンクメッセージを待ち（705）、706において応答を検査し、対象ノードが自分自身へのリンクをもっているかどうかを検査し、もっていないときは、ステップ703において、対象ノードへのリンクを取り除く。
【００５６】
図８は、ノードが、到来するリンク照会メッセージをどのように処理するかを示している。これらのメッセージは、別のノードが受信ノードのリンクを知りたいときに送られ、800において、受信ノードは、それを受信すると、801において、リンクメッセージで応答する。
【００５７】
図９は、ノードが、到来するリンクメッセージをどのように処理するかを示している。それがどのように処理されるかは、、対応するリンク照会メッセージが送られた理由に完全に依存する。これは、とくに、図３、４、５、および７に示されているように、異なる理由で行われる。したがって、リンク照会メッセージが送られるとき、それは、局所的に固有である基準を与えられ、メッセージハンドラがその基準と関係付けられる。次に、リンクメッセージを受信すると（900）、適切なメッセージハンドラが識別され、ステップ902において、メッセージが適切なメッセージハンドラへ送られ、ノードはメッセージを正しいやり方で処理する。
【００５８】
もちろん、例えば、受信ノードが遮断されていたために、リンク照会に応答して、リンクメッセージがそれまで受信されないということも起こり得る。したがって、所与の期間の後で、リンクメッセージが受信されなかったときは、対応するメッセージハンドラが取り除かれる。これは、ここに記載されているフローチャートの何れにも明示的に示されていないが、リンク照会の時間が切れると、動作はそれ以上行われず、単に、フローチャート全体が“終了した”ことを意味する。
【００５９】
ノードを検索
二次ネットワークの１つのノードのアドレスが与えられると、ネットワーク内の他の、潜在的に全ての、ノードを発見することができる。このやり方は、非常に簡単である。既知のノードに、その全リンクを要求するリンク照会メッセージを送る。ノードは、自分がリンクしている全ノードのアドレスを含むリンクメッセージで応答する。したがって、これらのノードの各々に接触して、リンクを要求し、全リンクのアドレスを得ることができる。このやり方を続けることによって、ネットワークを横切って、それが含む全ノードを次第に発見する。
【００６０】
図１０は、処理をより詳しく示している。これは、図１Ａに示されている検索ステップ35において使用されている処理であることが分かるであろう。接触することに成功した全ての既知のノードのアドレスは、“確認済み”リスト内に置かれる。同時にデータが検索される。“ウエブページコメント”の例の場合に、データの関連項目は、コメントのアドレスであり、これも、ノードアドレスと一緒に、確認済みリスト内へ入れられる。次に確認済みリストは、図１Ａのコメント“検索”ステップ（36）に必要なアドレスを与える。他方で、“確認済み”リストは、まだ接触していない既知のノードのリストを含む。最終的に、“既知”のリストは、全ての既知のノードのアドレスを含む。それは、“確認済み”および“未確認”リスト内の全てのアドレス、および接触したが、応答されていないノードのアドレスも含む。既知のリストは、それに入れられた各アドレスごとに、源アドレスを入れるための追加のフィールドももっている。源アドレスは、誤った報告のために、現在のポインタが指示しているアドレスが得られた、そのリストからのノードのアドレスである。
【００６１】
検索処理が行われる場所は、それがノードであっても、または他の場所であっても、重要ではない。ステップ1000において、ノードのアドレスを検索する要求は、開始アドレス、すなわち、問題の仮想ネットワークに属していると判断された１つのノードのアドレスと共に受信される。ステップ1002において、現在の、アドレスポインタは、最初に、このアドレスに設定され、一方で、源の、第２のアドレスポインタは、最初は、ナルである（1003）。
【００６２】
ステップ1004および1005において、リンク照会メッセージを現在のアドレスポインタによって与えられるアドレスへ送り、応答を待つ。リンクメッセージが受信されると、現在のアドレスは、その横にリンクメッセージからのコメントアドレスと共に、確認済みリストに追加される（ステップ1006）。
【００６３】
ステップ1007において、サブプロセスに入り、リンクメッセージに含まれている各アドレスごとに行なう。アドレスが既に既知のリスト内にあるときは（1008）、処理は、次のアドレスへ進む。さもなければ、アドレスを既知のリストおよび未確認リストへ加える（ステップ1009、1010）。さらに加えて（1011）、現在のアドレスを、アドレスの源が加えられているように、既知のリストへ入れる。
【００６４】
このサブプロセスが完了すると、（未確認リストが空でなければ、なお、この場合は、プロセスはステップ1012において終了する）、ステップ1013において、アドレスは、未確認リストから無作為に選択される。このアドレスは、新しい現在のアドレスになり、未確認リストから削除される。次のステップ（1014）では、既知のリスト内の現在のアドレスをルックアップして、それと関係付けられる源のアドレスを検索し、これを源のアドレスポインタに入れる。無作為の選択は、一定ではない。例えば、現在のアドレスを未確認リスト内で“最も古い”ノードとして選択してもよく、またはリストを別の基準（例えば、ノードのアドレス）によって分類し、現在のアドレスが、常にこのリスト内の“第１”のノードであるようにしてもよい。しかしながら、現在のアドレスの無作為の選択には利点がある。これは、（とくに、全てのノードが常に検索されるわけではないときは）システムにおける負荷を分散し、さらに加えて、ネットワークのリンクの試験を分散し、切断されたリンクがより迅速に発見される。
【００６５】
次に処理をステップ1004から再び続け、未確認リストが空である、すなわち、別の新しいアドレスを検出することができなくなるまで、反復する。
検索処理の副次的効果は、これが、切断されたリンクを発見することである。例えば、ノードが応答しない、またはリンクが相互でないとき、発見される。リンクが相互でないことは、ノードＡがノードＢにリンクしているが、ノードＢが、そのリンクテーブル内にノードＡをもっていない場合である。切断されたリンクが発見されると、リンクの“源”であるノードは、リンクエラーメッセージによって通知される。既に図７で示したように、源ノードは、（エラー報告の精度を確認するために）リンク自体を検査することができ、その結果としてリンクを取り除いてもよい。応答しないノードは、ステップ1005において、設定されたタイムアウト期間内にリンクメッセージを受信しないことによって認識され、ステップ1015において、現在のアドレスおよび“応答無し”のエラーコードを含むエラーメッセージが源へ送られ、制御はステップ1012へ戻る。ステップ1016において、リンクの相互性がないことが、試験によって認識され、現在のアドレスについての受信されたリンクメッセージが、源のアドレスを含んでいるかどうかを判断し、含んでいないときは、現在のアドレスおよび“相互ではない”エラーコードを含むエラーメッセージが、源のアドレスへ送るが（ステップ1017）、（図７の処理にしたがって）源ノードは改善措置を取る責務があるので、検索処理は、これまで通りに継続する。ステップ1016における試験は、源のアドレスがナルであるときは、省かれる。
【００６６】
多数の確認済みノードが、リンクメッセージに応答しないノードにリンクしても、最初にリンクを与えたノード（源ノード）のみが、“応答無し”だったことを通知されることに注意すべきである。この理由の１つは、これが、フローチャートをより理解し易くするからである。しかしながら、別の実際的な恩恵があることを示すことができる。ノードが、一時的にオーバーロードしたために、（時間内に）応答しない場合がある。この場合に、多数のノードがそれにリンク照会メッセージを同時に送って、（図７のように）エラーがあるかどうかを試験することが望ましくないことがある。何れにしても、希望であれば、このようなリンクが発見されたときに、ノード検索アルゴリズムを更新して、切断されたリンクによって影響を受ける全ての既知のノードに通知するのが、直接的である。
【００６７】
図１０では、全ての既知のノードに接触するまで、ノード検索を終了しない。実際には、処理をより早く終了することが望ましいことがある。例えば、ユーザが、ファイルをダウンロードする場所を探しているとき、例えば、１０００個の全てのダウンロードアドレスの代わりに、１０個の潜在的なダウンロードアドレスを選択することをユーザに提案することで十分であることがある。
【００６８】
図１０のアルゴリズムは、全体的に直列に示されている。一度に、１つのみのノードに接触する。前のリンク照会メッセージに対する応答を受信した（または、タイムアウトした）後でのみ、別のリンク照会メッセージが送られる。しかしながら、実際には、多数のリンク照会メッセージを並列に発行することによって、検索を高速化することが好ましい。ボックス1000において、多数の検索要求が、図１０の処理の多数の例によって、同時に処理される場合もある。
【００６９】
考察
自己組織化の成功
二次仮想ネットワークの目的は、いくつかの接続されないネットワークとは対照的に、１つのネットワークへ一緒にグループ化されるべき全てのノードを自己組織化することである。これに当てはまるかどうかは、主として、最初の通知メッセージがどのように生成されるかに依存する。例えば、全てを一緒にグループ化すべき１２個のノードのグループがあるが、このグループの中の５つのノードのみが、この５つのノードを含むこのグループ内の他のノードについての通知を受信し、他の７つのノードの何れも、これらの５つのノードの何れについても通知されないときは、ノードは、１つのネットワークへ自己組織化することはできない。その代りに、それらは、２つの別個のネットワーク、すなわち、５つのノードをもつものと、７つのノードをもつものへ配置する。しかしながら、最初の通知が、ノードが１つのネットワークへ自己組織化することができないというものでない限り、自己組織化処理は、ノードが１つのネットワークへ自己組織化しない可能性は非常に低い。自己組織化が1つのネットワークを生成する確率の計算は、複雑であり、最初の通知が生成される機構に依存する。しかしながら、幾つかの異なる最初の通知機構で経験したシミュレーションにおいて、これまでは、ノードが、1つのネットワークに自己組織化することに失敗したことはない。
【００７０】
悪質なノードのロバスト性
これまでは、全てのノードがプロトコルにしたがうと仮定されていた。しかしながら、規則にしたがって動作しない悪質なノードがあることがある。これらは、他のノードによって維持されているリンクを切断することを試みるか、または自分への多過ぎるリンクを設定しすることを試みるか、あるいはこの両者を行う。全体的なシステムは、このような悪用に対して可能な限りロバストであることが望ましい。
【００７１】
これまで記載してきたシステムは、悪質なノードに対して、既に相当にロバストである。その理由は、各ノードが、リンク照会メッセージ−リンクメッセージの交換を用いて、自分自身のリンクを変更する前に、他の関連するノードによって維持されているリンクを常に検査しているからである。例えば、ノードは、リンク追加メッセージを受信するとき（図３参照）、最初に、送信ノードを自分自身のリンクとして加える前に、送信ノードが実際に自分にリンクしたかを検査する。
【００７２】
しかしながら、システムは、依然として、相対的欠点をもつ。現状では、ノードは、リンクメッセージに応答するとき、容易に“嘘をつく”ことができる。ノードは、しばしば、受信ノードが自分にリンクしたかを検査するリンク照会メッセージを送る。これを知ると、受信ノードは、自分が、リンクメッセージの送信側をリンクとして常に含んでいるように変更された偽のリンクメッセージで応答することができる。これは、ノードが、自分にリンクしている許容数のＬ個よりも相当に多いノードをもつことを可能にする。その結果、これは、システム内の“好適な”リンクの総数を相当に低減する。
【００７３】
都合のよいことに、この欠点に対処する方法がある。これは、ノードが、プロキシノードを介してリンク照会を送るときに達成することができる。ノードが照会を送りたいときは、いつも、これらのプロキシが無作為に選択される。各ノードは、例えば、自分が現在プロキシとしてリンクしているノードを使用することができる。したがって、ノード（Ａ）が別のノード（Ｂ）のリンクを知りたいとき、ノードＢにはノードＡが分からない。その理由は、ノードＢが受信するリンク照会メッセージは、プロキシノード（Ｃ）からであり、かつノードＢがノードＣから受信するメッセージは、ノードＡを全く参照していないからである。したがって、ノードＢが、全システムにとって重要な影響を与える偽のメッセージを送るための好適な方法はない。
【００７４】
もちろん、悪質なプロキシの影響について問題がある。明らかに悪質なプロキシは有害な影響をもつ（プロトコルに従わないノードが、性能にある程度影響を与えるのは、避けられない）が、この影響は制限される。この理由は、悪質なプロキシは、送るように要求されたリンク照会を悪質に処理できるだけであり、これらの要求は全ノードにおいてほぼ均等に分散されるからである。他方で、プロキシが使用されないときは、悪質なノードは、非常にアクティブであることによって、大きな破壊を生じることがある。これらのノードが多くの疑似のリンク追加メッセージを送り、次に送る多くのリンクメッセージを偽造するとき、全システムに与える影響は、相当により大きい。
【００７５】
一次仮想ネットワーク
一次ネットワークは、上述の国際特許出願に詳しく記載されている。ここでは、基本的な検索および自己組織化機構を、二次ネットワークの自己組織化を駆動するための通知メッセージの生成を可能にする変更と共に、記載する。
最初に、この機構によって使用される仮想座標空間の概念を説明する必要がある。各ノードがラベルをもつことは、既に記載した。ラベルは、仮想空間における座標へ変換される。空間は、一次元、二次元、またはより高い次元であってもよい。精密な変換機構は、あまり重要ではない。一次元空間では、二値であると考えられるラベルを、座標として直接に使用することができる。二次元以上の次元では、一連のビットであると考えられるラベルを２つ以上の等しいグループへ分割し、二値であると考えられる各グループが座標の１つを形成するという方法が好ましい。各座標（または、一次元空間における座標）は、範囲［１，０］に位置するように基準化される。
【００７６】
この仮想空間内の２つのラベル間の距離は、２つの座標の組の間のユークリッド距離である（しかしながら、希望であれば、市街区距離（しばしばマンハッタン距離と呼ばれる）のような他の距離を使用してもよい）。
【００７７】
【数１】
既に記載したように、この点において、各ノードは、他のノードへのリンクを表わす多数のエントリを含むリスト22（図１）をもっている。各エントリは、このような別のノードのラベルおよびアドレスを含んでいる。最初に、このリストは空であり、したがって、ノードは、ブートストラップリンク、すなわち、幾つかのリンク（一般的に、４つ）の第２の、同様の、リストをもち、最初に、ネットワークの他のノードに接触することができる。リスト22内のリンク（短距離リンクと呼ばれる）に加えて、ノードは、階層的に配置された追加のこのようなリスト、または長距離のリンクのリスト、あるいはこの両者ももつ。これらは我々の以前の国際特許出願に記載されているが、オプションであるので、ここには記載しない。
【００７８】
メッセージ
最初に、使用するメッセージを示す（一次仮想ネットワークにおいて使用されるメッセージは、二次仮想ネットワークにおいて使用されるメッセージとは、異なり、完全に独立していることに注意すべきである）。
検出メッセージ（FIND message）は、ノードのルックアップを開始し、満たし、“プル”更新を支援するのに使用される。これらは、
・目標ノードのラベル、および、
・照会を開始したノードのアドレス、
を含む。
【００７９】
検出済みメッセージ(FOUND message)は、照会の結果を戻すのに使用される、これらは、
・目標ノードのラベル、
・検出されたノードのラベル、
・検出されたノードのアドレス、
・検出されたノードと関係付けられる二次ネットワークのノードのアドレス、および、
・アプリケーション別データ−この場合は、検出されたノードと関係付けられるコメントノードのアドレス、
を含む。
【００８０】
プッシュメッセージ(PUSH message)は、ノードのラベルを他のノードへ広告する。これらは、
・対象ノードのラベル、
・対象ノードのアドレス、および、
・目標ノードに到達するための、ホップ ツウ ゴー（hop to go）の数
を含む。
【００８１】
通知メッセージ(NOTIFY message)は、プッシュ更新を伝搬するのに使用される。これらは、
・対象ノードのラベル、および、
・対象ノードのアドレス、
を含む。
検索
図１１は、各ノードが、到来する検出メッセージをどのように処理するかを示している。原則的に、受信ノードは、検出メッセージ内で識別される目標ノードに対して、自分自身よりも近いノードをルックアップし、成功であるときは、検出メッセージ上で送る。成功でないときは、受信ノードは、自分自身のアドレスおよびラベルを戻す。受信ノードは、次に示すステップを実行することにより、これを行う：
ステップ1100：ノードは、目標ノードのラベルおよび開始ノードのアドレスを含む検出メッセージを受信する；
ステップ1105：ノードは、目標ノードのラベルを、ラベル空間の座標へ変換し、自分が記録した全てのリンク（ノード）の中で、ラベル空間内で目標ノードに最も近いものを計算する。該当するノードは、最近ノードとして示される；
ステップ1110：ノードは、自分自身の座標と目標のノードの座標との間の距離を、最近ノードの座標と目標のノードの座標との間の距離と比較する；
ステップ1115：自分自身の座標と目標のノードの座標との間の距離が（等しいか、または）より短いときは、ノードは、ネットワーク10を介して、開始ノードへ、自分自身のラベルとアドレスとを含む検出済みメッセージを送る；
ステップ1120：最近ノードの座標と目標ノードの座標との間の距離が、より短いときは、ノードは、検出メッセージを最近ノードへ送る；
ステップ1115において戻されるノードのアドレスは、目標ラベルをもつノードのアドレスか、またはラベル空間内で目標ラベルに近いノードのアドレスである。戻されたラベルが目標のラベルに整合しないときは、目標のノードが存在しないか、または仮想ネットワークが十分に自己組織化されていないかの何れかを意味する。
【００８２】
プッシュ
各ノードは、プッシュ更新を自発的に開始する。例えば、各ノードは、プッシュ更新処理を定期的に始めてもよい。プッシュ更新において、ノードは、自分自身のラベルおよびアドレスをもつプッシュメッセージを、無作為に並んでいて、その列の長さに制限が設定されたノードを経由して送る。列の中の最後のノードは、通知メッセージを開始ノードへ送る。図１２、１３、および１４は、この処理の種々の部分を示している。
【００８３】
図１２は、ノードが、次のステップを使用して、プッシュ更新をどのように開始するかを示している：
ステップ1200：ノードは、ブートストラップリンクの中から無作為にリンクを選択し、選択されたリンクによって識別されるノードのアドレスを、次のメッセージのための転送アドレスとして入力する；
ステップ1205：ノードは、移動のためのホップのフィールドにおける小さい正の乱数を、プッシュメッセージに入力する；
ステップ1210：ノードは、自分自身のラベルおよびアドレスを、対象ノードのものとしてプッシュメッセージに入力し、ネットワーク10を使用して、プッシュメッセージを転送アドレスのノードへ送る。
【００８４】
図１３および１４は、短距離リンクがどのように更新されるかを示している。プッシュメッセージを通知メッセージと一緒に使用して、短距離リンクを更新する。この更新には２つの段階がある。第１の段階では、各ノードは、受信したメッセージ内の移動のためのホップの値が“０”になるまで、プッシュメッセージを無作為に送る。移動のためのホップの値が“０”であるときは、受信ノードは、通知メッセージを送ることによって、プッシュ更新の第２の段階を始める。第２の段階では、通知メッセージをノードへ連続的に送り、そのラベルは、仮想空間内の対象ノードに次第により近くなる。より近いラベルをもつノードを検出できないときは、必要であれば、最後に検出されたノードへのリンクを更新する。これが常に当てはまるのは、例えば、ノードが、設定された短距離リンクをまだもっていないために、所与の対象ノードを検出できないときである。最後に検出されたノードは、追加の通知メッセージを、リンクの組を潜在的に更新したノードへも送る。
【００８５】
図１３を参照すると、到来するプッシュメッセージを取扱うプッシュ更新の第１の段階は、次のステップを含む：
ステップ1300：ノードはプッシュメッセージを受信する。プッシュメッセージは、対象ノードとして、開始ノードのラベルおよびアドレスを含み、移動のためのホップのフィールドの値をもつ；
ステップ1305：受信ノードは、ブートストラップリンクの中から無作為にリンクを選択し、次のメッセージのための転送アドレスとして、選択されたリンクによって識別されるノードのアドレスを入力する；
ステップ1310および1315：受信ノードは、ホップ ツウ ゴーのフィールドの値を１低減し、ホップ ツウ ゴーの低減値が、依然としてゼロよりも大きいかどうかを検査する；
ステップ1320：低減値が、依然としてゼロよりも大きいときは、ノードは、プッシュメッセージを、自分が入力した転送アドレスへ送る；
ステップ1325：値がゼロであるときは、ノードは、その代りに、対象ノードとして、（受信したプッシュメッセージ内に与えられている）開始ノードのラベルおよびアドレスを、通知メッセージに入力し、通知メッセージを、自分が入力した転送アドレスへ送る。
【００８６】
図１４を参照すると、プッシュ更新を取扱う、すなわち通知メッセージを取扱う、第２の段階は、次に示すステップを含む：
ステップ1400：ノードは、対象ノードとしてのノードのラベルおよびアドレスを含む通知メッセージを受信する；
ステップ1401：受信ノードは、通知メッセージの対象ノードが、受信ノードと同じラベルをもつかどうかを検査する；
ステップ1402：そうであるときは、受信ノードは、通知メッセージの対象ノードが、受信ノードと同じアドレスをもつかどうかを検査する。この場合は、受信ノードは、それ以上の動作を行わない。
【００８７】
しかしながら、通知メッセージの対象ノードが、受信ノードとラベルは同じであるが、アドレスは異なるノードであるときは、２つのイベントが行われる。第１に（ステップ1403）、受信ノードは、到来する通知メッセージの対象ノードへ、短距離リンクの受信ノード自身のリストからの無作為に選択されたノードを、対象ノードとして指定する通知メッセージを送る。第２に、ステップ1404は、二次ネットワークによる動作のために通知メッセージを生成する。しかしながら、受信ノードは、このようなメッセージを直接に生成できない。概して、通信ネットワーク上で、異なる仮想ネットワーク間でメッセージを送るのを避けるのが好ましいが、主な問題は、受信ノードが、二次ネットワークの自分自身のノードのアドレスだけでなく、対象ノードと関係付けられる二次ノードのノードのアドレスも必要とすることである。受信ノードは、このアドレスをもっていない。したがって、２段階の処理が使用される。
【００８８】
第１に、受信ノードは、特定の相互通知（CrossNotify）メッセージを、到来する通知メッセージにおいて対象ノードとして指定された一次ネットワークのノードへ送る。このメッセージは：
・受信ノード（すなわち、到来する（一次ネットワークの）メッセージを受信したノード）のアドレスに設定された、送信側アドレスと；
・到来する通知メッセージに含まれているアドレスに設定された、受信側（または宛先）アドレスと；
・受信ノードと関係付けられた二次ネットワークのノードのアドレスに設定された、対象アドレスとを含む。
【００８９】
最初の２つのアドレスは、一次ネットワーク上のノードのアドレスであり、第３のアドレスは、二次ネットワーク上のノードのアドレスであることに注意すべきである。
第２に、相互通知メッセージを受信する一次ネットワークのノードは、事実上（in effect）、それを、二次ネットワークの関係付けられたノードへ送る。必要であれば、二次ネットワーク上で使用するフォーマットへメッセージを再フォーマットし、（一次ネットワークの）受信側アドレスを、二次ネットワークの関係付けられたノードのアドレスと置換する。次に、メッセージは、ちょうど図３に示されているように処理される。“事実上”という理由は、実際には、相互通知メッセージを受信する一次ネットワークのノードが、二次ネットワークの関係付けられたノードへ、単に、相互通知メッセージの対象フィールドにおいて指定されているアドレスを含んでいる簡単な局所的なメッセージを送ることが好ましいからである。その場合には、図３の処理は、通知レベルを適切な値に設定するステップを含むように変更される。
【００９０】
この処理は、図１５を参照して、例示的に示される。図１５では、ボックスはノードを表わし、矢印はメッセージを表わす。図１４のステップ1400において、一次ネットワークのノードＰ１は、対象ノードとして一次ネットワークのノードＰ２のラベルＬＰ２およびアドレスＡＰ２を含む通知メッセージを受信すると仮定する。ノードＰ１において、対象ノードは、Ｐ１とラベルは同じである（すなわち、ＬＰ１＝ＬＰ２）が、アドレスは異なる（ＡＰ１≠ＡＰ２）ことが分かる（図１４のステップ1401、1402）。ノードＰ１は、二次ネットワークのノードＳ１のアドレスＡＳ１を知り、（図１４のステップ1404において）送信側アドレスＡＰ１、受信側アドレスＡＰ２、および対象アドレスＡＳ１をもつ相互通知メッセージを生成する。このメッセージは、一次ネットワークのノードＰ２において受信され、Ｐ２は、アドレスＡＳ１をもつ局所的な通知メッセージを、二次ネットワークの関係付けられたノードＳ２へ送る。その代わりに、二次ネットワークのノードＳ２は、局所的通知（LocalNotify）メッセージを受信すると、図３のプロセスにしたがってリンク自体を生成する代わりに、（図１５において点線によって示されている）（二次ネットワークの）別の通知メッセージを生成し、これを、対象として自分自身を指定しているノードＳ１へ送る。次に、通知メッセージは、ノードＳ１において、図３の処理を使用して処理される。このオプションは、追加のメッセージを含むが、図３の処理が実行されるとき、通知メッセージは、実際には、メッセージの対象フィールドのアドレスであるノードによって送られ、したがって、対象ノードは、本質的に、依然として存在していると確認される。
【００９１】
ここで図１４に戻って、ステップ1405：受信ノードは、対象ノードのラベルを座標へ変換し、受信ノードが記録した短距離リンクの座標を計算し、仮想空間内の対象ノードの座標に最も近い座標をもつノードのラベルへ導く。該当するノードは、最近ノードを示している：
ステップ1415：受信ノードは、自分自身の座標と対象ノードの座標との間の距離を、最近ノードの座標と対象ノードの座標との間の距離と比較する；
ステップ1415において、受信ノードと対象ノードとの間の距離が、同じか、またはより短いことが検出されると、受信ノードは、対象ノードのラベルおよびアドレスを、自分自身の短距離リンクの組内のリンクとして追加し（ステップ1420：この処理は、図１６を参照して、別途詳しく記載する）、受信ノードのラベルおよびアドレスを含む通知メッセージを対象ノードへ送り（ステップ1430）、対象ノードのラベルおよびアドレスを含む通知メッセージを最近ノードへ送る（ステップ1435）；
ステップ1415において、最近ノードと対象ノードとの間の距離が、より長いことが検出されると、受信ノードは、ステップ1435へ戻り、対象ノードのラベルおよびアドレスを含む通知メッセージを最近ノードへ送る。
【００９２】
図１６は、ノードが短距離リンクを更新するときに、どのように動作するかをより詳しく示している。これは、新しいリンクを短距離リンクへ加え、このリンクによって取り替えられる全短距離リンクを取り除く。
図１６を参照すると、ノードは、例えば、図１４のステップ1420の結果として、新しいリンクを短距離リンクのリストへ加えることが必要である。
【００９３】
ステップ1600：更新ノード（すなわち、短距離リンクの組への更新を実行するノード）は、新しいリンクのノードのラベルおよびアドレスをもつ；
ステップ1605：更新ノードは、更新ノードよりも、新しいノードにより近いノードに関係する全ての既存のリンクを識別する。これらの識別されたリンクは取り替えられる。これらのリンクを識別するために、更新ノードは、各既存のリンクごとに、新しいノードの座標と、既存のリンクにおいて特定されているノードの座標との間の距離を計算する。更新ノードは、これらの距離の各々を、自分自身の座標と、各既存のリンクにおいて特定されているノードの座標との間の距離と比較する；
ステップ1610：新しいノードに関係する距離が、更新ノードに関係する距離よりも短い全リンクを、短距離リンクから取り除く；
ステップ1620：更新ノードは、新しいノードのリンクを短距離リンクへ加える。
【図面の簡単な説明】
【００９４】
【図１】本発明の１つの実施形態において使用されているコンピュータのブロック図。
【図１Ａ】一次および二次仮想ネットワークを使用するデータ検索動作を示すフローチャート。
【図２】コンピュータネットワークのノード間のリンクの管理を示す模式図。
【図３】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図４】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図５】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図６】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図７】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図８】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図９】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１０】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１１】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１２】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１３】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１４】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１５】図１４に示されている処理中のメッセージの流れを示す模式図。
【図１６】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【符号の説明】
【００９５】
２・・・メモリ、３・・・ディスプレイ、４・・・キーボード、５・・・通信インターフェイス。
【技術分野】
【０００１】
本発明は、コンピュータネットワーク、限定はしないが、とくに、ピア ツウ ピア システムのような、とりわけ、中央の記憶または制御を使用しない、分散形システムに関連する情報検索に関する。
【発明の開示】
【課題を解決するための手段】
【０００２】
本発明の１つの態様にしたがうと、ノードを含むコンピュータネットワークであって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索手段と、
−第１の検索手段によって識別されたアドレスを受信し、それに応答して、同じラベルに整合する別のノードのアドレスを識別するように動作可能であるように接続された第２の検索手段とをもち、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索手段が、第１の検索手段によって識別されたアドレスに照会メッセージを送り、応答を受信すると、その照会メッセージへの応答か、または場合によっては、次の照会メッセージへの応答に含まれるアドレスへ照会メッセージを反復的に送るように動作可能なコンピュータネットワークを与える。
【０００３】
別の態様では、本発明は、ノードを含むコンピュータネットワークを動作する方法であって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索動作を行うことと、
−第１の検索手段によって識別されたアドレスに応答して、同じラベルに整合する別のノードのアドレスを識別する第２の検索動作を行うこととを含み、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索動作が、第１の検索手段によって識別されたアドレスに照会メッセージを送り、応答を受信すると、その照会メッセージへの応答か、または場合によっては、後の照会メッセージへの応答に含まれるアドレスへ照会メッセージを反復的に送るように動作可能な方法を与える。
【０００４】
本発明の他の好ましい特徴は、特許請求項に定められている。
ここで、本発明のいくつかの実施形態を、例示的に、添付の図面を参照して記載する。
【発明を実施するための最良の形態】
【０００５】
ノード
この記述では、処理、記憶、および通信能力をもつコンピューティングノードを参照する。コンピューティングノードは、コンピュータまたは他の装置（ここで、各コンピュータは、多数の独立プログラムまたは処理をその上で実行させることに注意すべきである）であるか、またはそのようなプログラムまたは処理である。また、多数の記憶されたデータ項目が、１つのプログラムまたは処理によってサービスされても、このような項目は、別個のノードとしてみなされる。
【０００６】
この記述は、各コンピューティングノードを、例えば、インターネットプロトコル（internet protocol, IP）ネットワークのような遠隔通信ネットワークである、幾つかの通信インフラストラクチャに接続して、メッセージをそれに送ることができることを仮定している。したがって、各コンピューティングノードは、通信インフラストラクチャ内のノードも構成している。
【０００７】
仮想ネットワークに属している仮想ノードも参照する。コンピューティングノードは、それと関係付けられた（恐らくは、異なる仮想ネットワークに属している）２つ以上の仮想ノードをもつことができるので、区別は重要である。その名前が示唆するように、仮想ノードは、物理的な認識において存在せず、むしろ、その存在は、やがて明らかになるように、仮想ノード間のリンク、したがって、それが属している仮想ネットワークを定めている、記憶されたデータによって設定されたものである。
【０００８】
必然的に、仮想ノードは、コンピューティングノードと関係付けられなければならず、それにより、処理、記憶、および通信能力を得る。仮想ノードによるメッセージの送信、受信、および処理に対する参照は、仮想ノードの代わりに、コンピューティングノードによる、このような送信、受信、または処理を指す。
【０００９】
例は、図１に示されている。コンピュータは、通常の構成要素、例えば、プロセッサ１、メモリ２、ディスプレイ３、キーボード４、およびネットワーク10を介して通信するための通信インターフェイス５をもつ。
メモリ２は、オペレーティングシステムおよび他のプログラム（図示されていない）、並びに図示されているテキストファイル20のようなデータファイルを含む。これは、テキストファイル20に対応するラベル21aと、自分自身のアドレス21bとを含む記憶装置21も含む。さらに加えて、これは、アドレスリスト22および支援プログラム23をもち、これらは共に、仮想ネットワークのノードの、コンピュータ上における、存在を定めている。このノードは、アドレス24をもつ。アドレスリスト25および支援プログラム26も示されており、これらは共に、別の仮想ネットワークのノードの、コンピュータ上における、存在を定めている。このノードは、アドレス27をもつ。リスト22、25に記憶されているアドレスは、同じ仮想ネットワーク内の他のノードのアドレスである。
【００１０】
ルックアップシステム
ここで、本発明の応用のたった１つの可能な例である、記載されているルックアップシステムを記載する。このシステムは、ユーザが、コメントをウエブページと関係付けることを可能にする。ユーザは、このページをいつ訪問しても、他のユーザが行ったコメントを見る機会をもっている。コメントは、（例えば、テキストファイルのような）コメントを与えたユーザのコンピュータ上に記憶される。
【００１１】
ウエブページを見ているユーザ（または、むしろ、ユーザのコンピュータ）は、ウエブページのユニバーサルリソースロケータ（universal resource locator, URL）をもち、ユーザがコメントを検索するのを可能にする機構が必要である。
【００１２】
テキストファイルは、コメントを与えたユーザのコンピュータ上に記憶され、国際特許出願第WO 03/034669号[代理人参照番号第A30044号]に記載されているタイプの仮想ネットワークのノードと関係付けられるものか、または、他のウエブページに関するコメントを含む他のテキストファイル、および恐らくは、他の関係のないファイルであってもよい。この仮想ネットワーク（この記述に関連して、一次仮想ネットワーク、または、単に、一次ネットワークと呼ばれる）では、ノードを識別するラベルをもっているならば、そのアドレスを知らなくても、そのノードへメッセージを送ることができる。このタイプのネットワークは、（各ノードに１つの）固有のラベルで機能することができるが、この例では、ラベルは固有ではなく、むしろ、特定のウエブページに関するコメントを含むテキストファイルと関係付けられた全ノードが、同じラベルをもつ。このラベルは、ウエブページのＵＲＬのハッシュ関数である。この仮想ネットワークは、１つのみのノードに到達する検索機構を与える。
【００１３】
テキストファイルは、第２の仮想ネットワークのノードとも関係付けられている。これ（二次仮想ネットワーク）は、１つの特定のウエブページに関するコメントを含むテキストファイルと関係付けられたノードのみを含む。
しかしながら、我々の上述の国際特許出願にしたがって一次ネットワークを使用することが好ましいが、必須ではないことに注意すべきである。実際に、仮想ネットワークを使用することは、全く必須ではなく、その代わりに、ラベルを受信し、それに対応する１つのノードのアドレスを戻す別の一次検索機構を使用してもよい。
【００１４】
コメントを書き込むコンピュータは、図１に示されており、
・一次ネットワーク内に、ラベル21aおよびネットワークアドレス24をもつノードを生成しなければならず、
・二次ネットワーク内に、ネットワークアドレス27をもつノードを生成しなければならない。
【００１５】
先ず、アドレスリスト22がブートストラップリンクを含むことを除いて、アドレスリスト22、25は空である。リスト22が一次ネットワークのいくつかの他のノードのラベルおよびアドレスを含むことと、リスト25が二次ネットワークのいくつかの他のノードのアドレスを含むことを保証するネットワークの自己組織化について別途記載する。さしあたり、これらのラベルおよびアドレスが存在すると仮定して、システムを記載する。
【００１６】
アドレスに関するいくつかの用語は、この点において、順番である。テキストファイル20によって形成されるノード、一次仮想ネットワークのノード、および二次仮想ネットワークのノードは、概念上１つの識別をもつ一方で、自分自身のアドレスをもっている。通信ネットワーク10内の別個のアドレスを各ノードに割り当てることができるが、実際には、これはとくに便利ではない。好ましい実行では、各ノードは、３つの部分から成るアドレスをもつ。すなわち、
・コンピューティングノードの“位置を特定する”インターネットアドレス。例えば、130.146.209.15；
・コンピューティングノードにおける特定の通信ポートの位置を特定するポート番号。ポートは、インターネットアドレスの標準部分である。これらは、例えば、異なる独立のアプリケーションプログラムがメッセージを個別に送受信するのを可能にする。すなわち、各々は、自分自身のポートにおいてメッセージを受信し、他のアプリケーションプログラムに向けられたメッセージを受信しないか、またはそれによって“混乱”させられない。インターネットアドレスとポート番号とを合わせて、（ＴＣＰ／ＩＰのような、使用されている通信プロトコルの一部であるので）ネットワークアドレスと考えることができる。全ての一次および二次ノードのネットワークアドレスは、同じであってもよいが、必ずしも、そうでなくてもよい。例えば、一次ノードへの全メッセージは、二次メッセージが受信されるのと、異なるポートにおいて受信される（これは、このようなメッセージを区別する１つのやり方である）；
・メッセージが向けられた特定のノードの位置を特定するノード識別子（整数値）。例えば、一次ネットワーク上の全てのメッセージが、専用のポートにおいて受信されるとき、各ノードと関係付けられた局所的に固有の識別子が依然として存在する。したがって、多数のノードがあるとき、メッセージが向けられたノードは明らかである。このノード識別子は、アプリケーション別のアドレス拡張部である（標準のインターネットプロトコルの一部ではない）。これは、単に、送られるメッセージ内に含まれている。それを受信する処理は、これを“知り”、このノードの識別子を調べて、メッセージが送られるべきノードを判断する。
【００１７】
両者のノードは同じネットワークアドレスをもつことが可能であるが、必ずしも、そうでなくてもよい。各ノードは、自分自身のポートをもたず（その理由の１つは、使用可能なポートの数が、ある程度制限されるためである）、２つのポート（したがって、２つの異なるネットワークアドレス）、すなわち、一次ネットワークのために１つのポート、二次ネットワークのために１つのポートをもっていてもよい。一般に、多数の二次ネットワークがあり、その全てが同じポートを使用してもよい。
【００１８】
次の記述において、ノードのアドレスの参照は、そのノードの完全なアドレスを指していることを強調しておく。
とくに魅力的なアプローチでは、テキストファイル、一次ノード、二次ノードの全てが同じノード識別子（およびＩＰアドレス）をもち、ポート番号のみが異なるものを与える。このようなアドレス指定プロトコルは、処理の一部を簡潔にする機会を与え、１つのノードのアドレスをもっていて、それと関係付けられた別のノードのアドレスを必要とするとき、別のノードのアドレスは、ルックアップする必要があるのではなく、むしろ、１つのノードのアドレスから推測される。しかしながら、次の記述では、このような簡潔化を行わず、これらの処理をアドレスプロトコルで行なう。
【００１９】
ウエブページを見ているコンピュータは、
・同じハッシュ関数をＵＲＬに適用して、ラベルを得て、
・一次仮想ネットワーク上で（ラベルを含む）照会を送って、１つのノードのアドレスを得て、
・検出されたアドレスを使用して、二次仮想ネットワーク上で照会を送り、二次仮想ネットワーク上の、より多くの（または、全ての）他の全ノードのアドレスを得て、
・これらのアドレスを使用して、表示するためのコメントを検索することによって、
関係付けられたコメントを検索する。
【００２０】
検索コンピュータは、仮想ネットワークのノードを必ずしも含む必要はなく、検索処理を実行するソフトウエアをロードされ、かつ仮想ネットワークのノードがあるコンピュータと通信できるように通信インターフェイスをもつ従来のコンピュータであってもよいことに注意すべきである。この処理は、図１Ａのフローチャートに示されており、次に記載するように、処理を進める。
【００２１】
ステップ３０：ユーザがＵＲＬを入力した（または、ハイパーリンクを呼出した）後で、コンピュータは、対応するウエブページを検索する。このステップは全く従来通りである。
ステップ３１：ハッシュ関数をＵＲＬに適用して、ラベルを得る。我々の以前の国際特許出願に記載されているように、これにはＳＨＡ−１アルゴリズムを使用することができる。
【００２２】
ステップ３２：検索コンピュータのこのラベルおよびネットワークアドレスを含む‘検出’メッセージを、一次ネットワークのノードへ送る。明らかに、コンピュータは、少なくとも1つのこのようなアドレスを保持していなければならない。
ステップ３３：検索コンピュータは、一次ネットワークから‘検出済み’メッセージを受信する。このメッセージは、検出したノードのラベルおよびアドレス、並びに二次ネットワークの関係付けられたノードのアドレスおよびコメントを含む。検出済みメッセージが適正な時間内に受信されないときは、処理を中止するタイムアウト機構が含まれることもある。
【００２３】
ステップ３４：この例では、一次ネットワークは、検出メッセージに含まれているラベルに最も近いラベルをもつノードのラベルとアドレスとを常に戻すように構成されている。したがって、戻されるラベルが、求めているラベルと同じかどうかを調べる検査が行われ、同じでないときは、処理は終了する。“最近（nearest）”の意味の説明について下記を参照すべきである。
【００２４】
ステップ３５：ラベルが整合すると仮定すると、検索コンピュータは、（別途詳しく記載する）処理を実行して、検出済みメッセージによって戻されたアドレスを使用して、二次ネットワークを使用して、別のアドレスを検索する。
ステップ３６：次に、これらのアドレスを使用して、“書込み（posting）”コンピュータから、コメントを含むテキストファイルを検索する。
【００２５】
二次仮想ネットワーク
このネットワークの目的は、ノードのグループを１つの仮想ネットワークへ自己組織化し、その後、これを使用して、グループの一部である全ノードを発見できるようにすることである。主な要件は、結果のネットワークが全ノードを含むことである。別の要件は、ネットワークを生成し、維持するのに必要なシステムロードが、全ノード全体で等しく分散されることである。これは、最も“公平” であるだけでなく（異なるユーザが、資源を分散形アプリケーションに与えるときに重要である）、オーバーロードからシステムを保護するのも助ける。
【００２６】
したがって、ネットワークは、次の特性をもつ。すなわち、
・各ノードによって維持されるリンクの数が、好ましくは、同じである；
・全リンクが双方向である。その結果、ノードへのリンクの数も、各ノードにおいて同じである。これは、ノードが受信し、処理しなければならないメッセージの数に影響を与えるので、重要である；
・これは“フラットな”構造である。ノードは、自分自身を階層的に配置しない。その結果、システムのロードは、全ノード全体で等しく分散される。
各ノードの構造
各ノードは、自分に関係付けられた次に示すデータをもつ：
・他のノードへのいくつかのリンク。各リンクは、単に、別のノードのアドレスである。“確認済み”または“未確認”の状態が、各リンクと関係付けられている。各ノードは、単に最大数のリンクを維持することができ、最大数のリンクは、システム全体のパラメータＬによって与えられる。Ｌの典型的な値は、例えば、６である。このパラメータが、全ノードにおいて同じであることは必須ではないが、それらを違うものにすることによって得られる恩恵はない；
・スペアリンク、または、約言して、スペアのリスト。各スペアは、単に、別のノードのアドレスである。スペアを自己組織化処理によって使用して、仮想ネットワークを構築する。ノードは、ノードについて、それが、ノードに既にリンクしているか、または最大数のリンクを既にもっているために、リンクとして加えることができないことを知らされると、他のノードをスペアとして加える。ノードが維持することができるスペアの数も制限され、システム全体のパラメータＳによって与えられる。Ｓの典型的な値は、例えば、３である。スペアリンクのリストは、通常、必須ではないが、追加の機構を与える際に、非常に有益であり、これによって、局所的に収容できないリンクを、仮想ネットワーク内の他の地点に伝搬することができる。しかしながら、到来する通知メッセージが、二次ネットワークの同じノード（または、非常に少数のノードの中の１つ）に常に到達する場合は、システムにおいて、スペアリンク（または、同様の伝搬機構）を使用することは必要である。
【００２７】
メッセージ
ネットワークへ自己組織化し、何れのノードが所与のネットワークの一部であるかを発見するために、ノードはメッセージを相互に送る。次のタイプのメッセージは、二次ネットワークによって使用される：
・リンク追加（AddLink）メッセージ：
・送信側のアドレス、および、
・受信側のアドレスを含む。
【００２８】
これは、一方のノード（送信側）によって別のノード（受信側）へ送られ、相互リンクを要求する。
・リンク変更（ChangeLink）メッセージ：
・送信側のアドレス、
・受信側のアドレス、および、
・対象のアドレスを含む。
これは、１つのノード（Ｘ）によって別のノード（Ｙ）へ送られ、Ｙに、そのリンクの１つ（Ｚ）を自分自身（Ｘ）へのリンクに変更することを要求する。プロトコルは、Ｘが同様のメッセージをＺへ送って、Ｚに、Ｙへのリンクを自分自身（Ｘ）へのリンクと交換することを要求する。したがって、事実上、Ｘは、ＹとＺとの間の現在のリンクの中に自分自身を挿入することを要求する。
・リンク追加済み（LinkAdded）メッセージ：
・送信側のアドレス、および、
・受信側のアドレスを含む。
【００２９】
これは、ノードに、送信側がそのノードへのリンクをちょうど加えたことを通知するのに使用される。
・リンクエラー（LinkError）メッセージ：
・送信側のアドレス、
・受信側のアドレス、
・対象のアドレス、および、
・エラーコードを含む。
【００３０】
これは、ノードに、そのリンクの１つに問題があると考えられることを通知するのに使用される。例えば、対象のノードが応答しない、またはリンクが相互でないといったことである。これは、エラーのタイプを示すエラーコードを含む。
・リンク（Links）メッセージ：
・送信側のアドレス、
・受信側のアドレス、
・全リンクのアドレス、および
・基準値を含み、
・リンクメッセージは、送信側ノードからのいくつかの他のデータも含むことができる。ウエブページのコメントの例において、これは、関係付けられたコメントのアドレスである。
【００３１】
これは、送信側ノードの全ての現在のリンクを含む。これは、常に、リンク照会メッセージに応答して送られる。参照を使用して、応答される特定の照会を区別することができる。
・リンク照会（LinksQuery）メッセージ：
・送信側のアドレス、
・受信側のアドレス、および、
・基準値を含む。
【００３２】
これは、ノードに、応答に（その現在のリンクを含む）リンクメッセージを送ることを要求するのに使用される。
・通知（Notify）メッセージ：
・送信側のアドレス、
・受信側のアドレス、
・対象のアドレス、および、
・通知レベルを含む。
【００３３】
これは、ノードに、ネットワーク内の別のノードについて通知するのに使用される。通知レベルは、通知メッセージの伝搬を制御して、制限するのに使用される。ここに記載されているように、送信側のアドレスは、使用されないが、デバッグのため、または希望であれば、肯定応答を送るのに役立つ。
【００３４】
二次ネットワークの構築
このシステムは、グループのノードを１つの仮想ネットワークへ自己組織化し、１つのノードのアドレスをもつと、グループ内の他のノードのアドレスを検出することができるようにする。このセクションは、同じ二次ネットワークに属すべきノードが発見されたときに、新しいリンクがどのように生成されるかを記載している。ここで、２つの部分を区別することができる。
【００３５】
同じ二次ネットワークに属すべきノードの対の発見。ノードを同じネットワークにグループ化するための基準は、アプリケーション別である。ウエブページの注釈の例において、同じＵＲＬに関するコメントを表わす全ノードは、二次ネットワーク内で一緒にグループ化されるべきである。一緒にグループ化されるべきノードをどのように発見するかも、アプリケーション別である。簡潔に例を与える。
【００３６】
ノードの発見の結果として、二次ネットワークを更新／拡張する。同じ二次ネットワークに属すべき１対のノードが発見されると、その結果として、システムは１つ以上の新しいリンクを構築する。新しいリンクは、１対のノードの間に必ずしもあるわけではないが、例えば、これらの２つのノードがリンクするノード間にある。新しいリンクがどのように生成されるかは別途詳しく記載する。
【００３７】
最初の通知メッセージ
二次ネットワークの組織化は、グループの既存のメンバーと新しいメンバーとを識別する、到来する‘通知’メッセージの存在を予め想定する（しかしながら、早い段階では、何れかのノードがまだグループの一部分でない可能性があり、一方で、自己組織化処理の後の方では、両者のノードは既にグループの一部である）。二次ネットワークに、それに属すべきノードについて通知するかは、システムの別の部分次第である。それを行うことができる種々の方法がある。ここで、二次ネットワークを、我々の以前の国際特許出願に記載されているタイプの一次ネットワークと共に使用して、これがどのように行われるかについての例を与える。ウエブページの注釈の例において、各コメントは、対応するウエブページのＵＲＬに基づくラベルのもとで、一次ネットワーク内のノードとして、自分自身を公開している。このようにして、一次ネットワークを使用して、所与のＵＲＬがあるときは、このコメントをルックアップすることができる。所与のＵＲＬの全てのコメントを示すために、各コメントは、それと関係付けられた二次ネットワークのノードももつ。同じＵＲＬに関するコメントに対応するノードは、そのＵＲＬに特定の二次ネットワークへ自己組織化する。このようにして、一次ネットワークを使用して、ＵＲＬに関する１つのコメントを検出すると、二次ネットワークを使用して、同じＵＲＬに関する別のコメントを検出することができる。
【００３８】
したがって、この場合に、一緒にグループ化されるべき二次ネットワークの各ノードは、一次ネットワークにおいて、同じラベルのもとで公開される。一次ネットワークにおいて、ノードが‘プッシュ’更新を定期的に実行して、ノードが、同じラベルのもとで公開されている別のノードに気付くときは必ず、必要な通知メッセージが生成される変更を含めて、リンクを構築し、維持する機構を、別途記載する。
【００３９】
通知メッセージの処理
ノードが、まだリンクしていないノードについての通知メッセージを受信すると、次の１つが行われる。
受信ノードは、最大数の許可されたリンクを既にもっているときは、それを（既にスペアとしてもっていないときは）スペアとして加える。これを行なうときに、ノードが、スペアの最大数を越えると、１つのスペアを取り除く。取り除いたスペアに通知メッセージを送ることもある。通知メッセージを送るかどうかは、通知レベルの値に依存する。通知レベルを下げるたびに、メッセージを永久に伝搬するのを防ぐ。
【００４０】
そうではなくて、対象ノードが、最大数のリンクをまだもっていないときは、受信ノードは、両ノード間の相互リンクを生成することを試みる。これは、図２の（ａ）および（ｂ）に示されている。ここで、Ｌ＝３であり、ノード１はノード２についての通知メッセージを受信する。両ノードは、リンクを２つだけもっているので、ノード１とノード２との間にリンクが生成される。
そうではなくて、対象ノードが、リンクの最大数を既にもっているときは、両ノード間に相互リンクを簡単に生成することができない。したがって、受信ノードが既存のリンクに自分自身を挿入するのを試みることが行われる。これは、図２の（ｃ）および（ｄ）に示されている。ここでは、ノード２とノード３との間のリンクが切断されるが、２つの新しいリンク、すなわち、ノード１とノード２との間のリンクと、ノード１とノード３との間のリンクとによって置換される。したがって、リンクの総数が１つ増加する。ノード２およびノード３が最大数のリンクを既にもっていても、これは行われる。しかしながら、ノード１は、これを成功させるために、２つの新しいリンクを生成できることが必要である。この処理は、図３ないし９のフローチャートにおいてさらに詳しく記載する。
【００４１】
図３は、ノードが、到来する通知メッセージをどのように処理するかを示している。ここでは、新しいリンクを生成すべきかどうか、および生成するときは、どのように（新しいリンクを加えることによって、または既存のリンクを２つのリンクへ変えることによって）生成するかを決定する。新しいリンクが生成されないときは、スペアの組を更新して、別の通知メッセージを送ってもよい。
【００４２】
ステップ300において、通知メッセージが受信される。通知メッセージは、それ（送信側）へ送ったノードのアドレス、対象ノードのアドレス、および伝搬制限値、すなわち通知レベルを含む。受信ノードは、最初に、それが新しいリンクを設定する余地をもっているかどうかを検査し（301）、もっているときは、それが対象ノードへのリンクを既にもっているかどうかを検査する（302）。もっていないときは、受信ノードは、対象ノードとのリンクを設定することを試みる。
【００４３】
ステップ303において、受信ノードは、リンク照会メッセージを対象ノードへ送り、ステップ304において、応答を待つ。応答、すなわち、リンクメッセージが受信されると、受信ノードは、（それが、途中で、他のメッセージを受信し、処理し、その結果として、リンクを生成した場合は）それが新しいリンクを設定する余地を依然としてもっているかどうかを再び検査する（305）。そうであるときは、次に、受信ノードは、受信したリンクメッセージを調べて、対象ノードが新しいリンクを設定する余地をもっているかどうかを検査する（306）。対象ノードがもっているときは、次に、ステップ307および308において、受信ノードは、（“未確認”と示されている）対象ノードのアドレスを、自分のリンクリストへ加え、リンク追加メッセージを対象ノードへ送る。
【００４４】
しかしながら、ステップ306において、対象ノードが別のリンクを受け入れることができないと判断されると、受信ノードは、図２を参照して既に記載したように、自分自身を既存のリンクへ挿入することを試みる。第１のステップ（309）では、受信ノードが２つのリンクのための余地をもっているかどうかを検査し、もっていないときは、処理は終了する。しかしながら、もっているときは、受信ノードは、受信したリンクメッセージ内のリンクリストから無作為にリンク（しかし、受信ノードがリンクを既にもっているノードではない）、すなわち、対象ノードと、ここでは、他のノードと呼ばれる別のノードとの間のリンクを選択する。次に、受信ノードは：
（未確認の）対象ノードのアドレスをリンクリスト追加し（311）；
（未確認の）その他のノードのアドレスをリンクのリストに追加し（312）；
他ノードのアドレスを含むリンク変更メッセージを対象ノードへ送り（313）；
対象ノードのアドレスを含むリンク変更メッセージを他のノードへ送る（314）ことによって、自分自身をこのリンク内へ挿入することを試みる。
【００４５】
しかしながら、ステップ301において、受信ノードがリンクを追加する余地をもっていないと判断されるか、またはステップ302において、受信ノードが対象ノードへのリンクを既にもっていると判断されるときは、処理は、受信ノードがリンクをスペアリンクのリストに追加するかどうかを調べる。ステップ315において、対象ノードがスペアリスト内に既にあることが検出されたときは、処理は終了する。316において、リンクをスペアリストに追加する余地があるかどうかを検査し、あるときは、317において、これを適切に追加する。ないときは、ステップ318において、スペアリンクの中の既存の１つを無作為に選択し、ステップ319において、取り除き、ステップ317において、これを対象ノードへのリンクと置換する。さらに加えて、ステップ320において、可変の通知レベルがデクレメントされ、（ステップ321において）それが依然としてゼロ以外であるときは、ステップ322において、通知レベルのこの新しい値をもつ元の通知メッセージを、無作為に選択された既存のリンクによって指示された（置換と呼ばれる）ノードへ送る。
【００４６】
この処理の効果は、リンクの全ての組を既にもっているノードＡが、自分に対象ノードＢへのリンクを要求する通知メッセージを受信するとき、Ｂのアドレスがスペアリンクとして記録されることである。このリンクは、Ａのスペアリンクリストがいっぱいになるまで、休止状態を維持する。次に、Ａが、自分にノードＣへのリンクを要求する、後の通知メッセージを受信し、ステップ318において、ノードＢへのスペアリンクが選択されると、ステップ322において生成された新しい通知メッセージは、事実上、ノードＢからノードＣへのリンクを生成するためのノードＢへの要求である。
【００４７】
フローチャート上には示されていないが、リンクが未確認であり、かつ受信ノードが、所定の時間期間内で、（図６を参照して別途記載されるように、リンク追加済みメッセージによって）確認を受信しないときは、未確認のリンクを削除する機構も与えられる。受信ノードは、依然として“未確認”状態のリンクをもっているとき、リンク照会メッセージに応答して、これらの未確認リンクを（もちろん、確認済みのリンクも）戻し、他のノードが、それがリンクの設定を試みていることを確認できるようにすることに注意すべきである。
【００４８】
図３では、ステップ305および309が“ノー”であるときは、処理の終了に導かれるが、希望であれば、これらを、ステップ315において始まる、効率が僅かに向上した“スペアリンク”処理へルート設定してもよい。
ステップ309ないし314では、ノードは対象ノードのリンクの1つを効率的に切断し、それらの間に自分自身を挿入する。フローチャートに示されていない別の可能なオプションでは、ノードが、（もちろん、それが少なくとも1つのリンクをもっていると仮定して）自分自身のリンクの１つを切断し、それらの間に対象ノードを挿入する。このオプションは、実行されるときは、ステップ301から‘ノー’で出た後で、直ちに試みられる。第１に、受信ノードは、対象ノードがＬ−１よりも少ないリンクをもつかどうかを検査して、（他のノードへの）自分自身のリンクの１つを無作為に選択して、これを、対象リンクへの未確認のリンクと置換して、リンク追加メッセージを対象ノードへ送る必要がある。対象ノードと他のノードとの間に双方向リンクを設定するために、それは、次に、（ａ）未確認リンクとして他のノードをリンクリストへ無条件で追加することを対象ノードに要求する特別のリンク追加メッセージを対象ノードへ送り、（ｂ）受信ノードを古いリンクとして取り除き、対象ノードを新しいリンクとして追加するために指定する特別のリンク変更メッセージを、他のノードへ送る。このオプションは、ステップ309ないし314に加えて、またはこれらに代わって含むことができる。
【００４９】
受信ノードが自分自身のリンクの１つを切断する別のオプションでは、（最初に、対象ノードがＬ−１よりも少ないリンクをもつことを確かめた）受信ノードが、自分自身を対象ノードとして指定した通知メッセージを、対象ノードに送る。これは、同じ結果をもつが、僅かに大きいメッセージングオーバーヘッドを含む。
【００５０】
図４は、ノードが、到来するリンク変更メッセージをどのように処理するかを示している。これらのメッセージは、通知メッセージを受信したノードＸが、既存のリンクを２つの新しいものに変えたいときに（図２参照）送られる。受信ノードＹは、400において、対象ノードとしてノードＺをもつ通知メッセージ、すなわち、ノードＹに、ノードＺへの既存のリンクを、ノードＸへのリンクと置換することを求める通知メッセージを受信する。それがＸへのリンクを既にもっているときは（401）終了し、一方で、ノードＹがノードＺへのリンクを実際はもっていないときは（402）、ノードＹはエラーメッセージを送信側Ｘへ送る（403）。
【００５１】
全てが適切であるならば、ノードＹはリンク照会メッセージを送信側Ｘへ送って（404）、応答して、送信側Ｘからのリンクメッセージを待ち（405）、送信側Ｘが、対象リンクを変える前に生成すべきであった２つの新しいリンクを実際に生成したかどうかを検査する。これらの検査（406、407）がイエスであるときは、受信ノードは、Ｚへのリンクを取り除き（408）、Ｘを確認済みリンクとして追加し（409）、リンク追加済みメッセージを送信側Ｘへ戻す（410）。
【００５２】
図５は、ノードが、到来するリンク追加メッセージをどのように処理するかを示している。これらのメッセージは、ノードが、ノードとの新しいリンクを生成したいときに（図１参照）送られる。501において、メッセージを受信し、ステップ502において、ノードは、それが別のリンクのための余地をもっているかどうかを検査し、もっていないときは、503において、エラーメッセージを戻す。そうでなければ、それは、リンク照会メッセージを送信側へ送り（504）、送信ノードからの応答のリンクメッセージを待ち（505）、506において、送信ノードが受信ノードへのリンクを実際に生成したかを検査する。ノーであるときは、リンクを追加するのを断って、終了するが、イエスであるときは、送信側ノードを確認済みリンクとして追加し（507）、確認によってリンク追加済みメッセージを送信側へ戻す（508）。
【００５３】
図６は、ノードが、到来するリンク追加済みメッセージをどのように処理するかを示している。これらのメッセージは、リンク変更またはリンク追加メッセージに応答して、別のノードが、受信ノードへのリンクを受け入れたときに送られる。600において、リンクが受け入れたことを示すリンク追加済みメッセージが受信されると、ステップ601において、その状態が“確認済み”に変更される。次に、リンクは、それが（リンク変更メッセージに応答して）新しいリンクに変更されるか、リンクが切断されるまで、維持される。
【００５４】
図７は、ノードが、到来するリンクエラーメッセージをどのように処理するかを示している。これらのメッセージは、（リンク変更メッセージまたはリンク追加メッセージによって）受信側ノードが相互リンクを要求した後で、ノードが受信側ノードへのリンクを生成できないときか、またはリンクが切断されていると考えられるときに（他方の端部のノードがメッセージに応答しないか、またはリンクが相互でないとき）、送られる。切断されたリンクは、自己組織化処理によってではなく、（別途記載するように）クライアントが二次ネットワークを横切るときに検出される。
【００５５】
ステップ700においてメッセージを受信した後で、メッセージが、受信側ノードが未確認リンクをもつノードに関するものであるかどうかが判断される（701）。そうであって、かつ、それが、要求されたリンクを生成することに失敗したことを示すエラーコードを保持しているときは（702）、703において、リンクは取り除かれる。しかしながら、メッセージが、受信ノードが未確認のリンクをもつノードに関するものでないときは、受信ノードは、リンク照会メッセージを対象ノードへ送り（704）、応答のリンクメッセージを待ち（705）、706において応答を検査し、対象ノードが自分自身へのリンクをもっているかどうかを検査し、もっていないときは、ステップ703において、対象ノードへのリンクを取り除く。
【００５６】
図８は、ノードが、到来するリンク照会メッセージをどのように処理するかを示している。これらのメッセージは、別のノードが受信ノードのリンクを知りたいときに送られ、800において、受信ノードは、それを受信すると、801において、リンクメッセージで応答する。
【００５７】
図９は、ノードが、到来するリンクメッセージをどのように処理するかを示している。それがどのように処理されるかは、、対応するリンク照会メッセージが送られた理由に完全に依存する。これは、とくに、図３、４、５、および７に示されているように、異なる理由で行われる。したがって、リンク照会メッセージが送られるとき、それは、局所的に固有である基準を与えられ、メッセージハンドラがその基準と関係付けられる。次に、リンクメッセージを受信すると（900）、適切なメッセージハンドラが識別され、ステップ902において、メッセージが適切なメッセージハンドラへ送られ、ノードはメッセージを正しいやり方で処理する。
【００５８】
もちろん、例えば、受信ノードが遮断されていたために、リンク照会に応答して、リンクメッセージがそれまで受信されないということも起こり得る。したがって、所与の期間の後で、リンクメッセージが受信されなかったときは、対応するメッセージハンドラが取り除かれる。これは、ここに記載されているフローチャートの何れにも明示的に示されていないが、リンク照会の時間が切れると、動作はそれ以上行われず、単に、フローチャート全体が“終了した”ことを意味する。
【００５９】
ノードを検索
二次ネットワークの１つのノードのアドレスが与えられると、ネットワーク内の他の、潜在的に全ての、ノードを発見することができる。このやり方は、非常に簡単である。既知のノードに、その全リンクを要求するリンク照会メッセージを送る。ノードは、自分がリンクしている全ノードのアドレスを含むリンクメッセージで応答する。したがって、これらのノードの各々に接触して、リンクを要求し、全リンクのアドレスを得ることができる。このやり方を続けることによって、ネットワークを横切って、それが含む全ノードを次第に発見する。
【００６０】
図１０は、処理をより詳しく示している。これは、図１Ａに示されている検索ステップ35において使用されている処理であることが分かるであろう。接触することに成功した全ての既知のノードのアドレスは、“確認済み”リスト内に置かれる。同時にデータが検索される。“ウエブページコメント”の例の場合に、データの関連項目は、コメントのアドレスであり、これも、ノードアドレスと一緒に、確認済みリスト内へ入れられる。次に確認済みリストは、図１Ａのコメント“検索”ステップ（36）に必要なアドレスを与える。他方で、“確認済み”リストは、まだ接触していない既知のノードのリストを含む。最終的に、“既知”のリストは、全ての既知のノードのアドレスを含む。それは、“確認済み”および“未確認”リスト内の全てのアドレス、および接触したが、応答されていないノードのアドレスも含む。既知のリストは、それに入れられた各アドレスごとに、源アドレスを入れるための追加のフィールドももっている。源アドレスは、誤った報告のために、現在のポインタが指示しているアドレスが得られた、そのリストからのノードのアドレスである。
【００６１】
検索処理が行われる場所は、それがノードであっても、または他の場所であっても、重要ではない。ステップ1000において、ノードのアドレスを検索する要求は、開始アドレス、すなわち、問題の仮想ネットワークに属していると判断された１つのノードのアドレスと共に受信される。ステップ1002において、現在の、アドレスポインタは、最初に、このアドレスに設定され、一方で、源の、第２のアドレスポインタは、最初は、ナルである（1003）。
【００６２】
ステップ1004および1005において、リンク照会メッセージを現在のアドレスポインタによって与えられるアドレスへ送り、応答を待つ。リンクメッセージが受信されると、現在のアドレスは、その横にリンクメッセージからのコメントアドレスと共に、確認済みリストに追加される（ステップ1006）。
【００６３】
ステップ1007において、サブプロセスに入り、リンクメッセージに含まれている各アドレスごとに行なう。アドレスが既に既知のリスト内にあるときは（1008）、処理は、次のアドレスへ進む。さもなければ、アドレスを既知のリストおよび未確認リストへ加える（ステップ1009、1010）。さらに加えて（1011）、現在のアドレスを、アドレスの源が加えられているように、既知のリストへ入れる。
【００６４】
このサブプロセスが完了すると、（未確認リストが空でなければ、なお、この場合は、プロセスはステップ1012において終了する）、ステップ1013において、アドレスは、未確認リストから無作為に選択される。このアドレスは、新しい現在のアドレスになり、未確認リストから削除される。次のステップ（1014）では、既知のリスト内の現在のアドレスをルックアップして、それと関係付けられる源のアドレスを検索し、これを源のアドレスポインタに入れる。無作為の選択は、一定ではない。例えば、現在のアドレスを未確認リスト内で“最も古い”ノードとして選択してもよく、またはリストを別の基準（例えば、ノードのアドレス）によって分類し、現在のアドレスが、常にこのリスト内の“第１”のノードであるようにしてもよい。しかしながら、現在のアドレスの無作為の選択には利点がある。これは、（とくに、全てのノードが常に検索されるわけではないときは）システムにおける負荷を分散し、さらに加えて、ネットワークのリンクの試験を分散し、切断されたリンクがより迅速に発見される。
【００６５】
次に処理をステップ1004から再び続け、未確認リストが空である、すなわち、別の新しいアドレスを検出することができなくなるまで、反復する。
検索処理の副次的効果は、これが、切断されたリンクを発見することである。例えば、ノードが応答しない、またはリンクが相互でないとき、発見される。リンクが相互でないことは、ノードＡがノードＢにリンクしているが、ノードＢが、そのリンクテーブル内にノードＡをもっていない場合である。切断されたリンクが発見されると、リンクの“源”であるノードは、リンクエラーメッセージによって通知される。既に図７で示したように、源ノードは、（エラー報告の精度を確認するために）リンク自体を検査することができ、その結果としてリンクを取り除いてもよい。応答しないノードは、ステップ1005において、設定されたタイムアウト期間内にリンクメッセージを受信しないことによって認識され、ステップ1015において、現在のアドレスおよび“応答無し”のエラーコードを含むエラーメッセージが源へ送られ、制御はステップ1012へ戻る。ステップ1016において、リンクの相互性がないことが、試験によって認識され、現在のアドレスについての受信されたリンクメッセージが、源のアドレスを含んでいるかどうかを判断し、含んでいないときは、現在のアドレスおよび“相互ではない”エラーコードを含むエラーメッセージが、源のアドレスへ送るが（ステップ1017）、（図７の処理にしたがって）源ノードは改善措置を取る責務があるので、検索処理は、これまで通りに継続する。ステップ1016における試験は、源のアドレスがナルであるときは、省かれる。
【００６６】
多数の確認済みノードが、リンクメッセージに応答しないノードにリンクしても、最初にリンクを与えたノード（源ノード）のみが、“応答無し”だったことを通知されることに注意すべきである。この理由の１つは、これが、フローチャートをより理解し易くするからである。しかしながら、別の実際的な恩恵があることを示すことができる。ノードが、一時的にオーバーロードしたために、（時間内に）応答しない場合がある。この場合に、多数のノードがそれにリンク照会メッセージを同時に送って、（図７のように）エラーがあるかどうかを試験することが望ましくないことがある。何れにしても、希望であれば、このようなリンクが発見されたときに、ノード検索アルゴリズムを更新して、切断されたリンクによって影響を受ける全ての既知のノードに通知するのが、直接的である。
【００６７】
図１０では、全ての既知のノードに接触するまで、ノード検索を終了しない。実際には、処理をより早く終了することが望ましいことがある。例えば、ユーザが、ファイルをダウンロードする場所を探しているとき、例えば、１０００個の全てのダウンロードアドレスの代わりに、１０個の潜在的なダウンロードアドレスを選択することをユーザに提案することで十分であることがある。
【００６８】
図１０のアルゴリズムは、全体的に直列に示されている。一度に、１つのみのノードに接触する。前のリンク照会メッセージに対する応答を受信した（または、タイムアウトした）後でのみ、別のリンク照会メッセージが送られる。しかしながら、実際には、多数のリンク照会メッセージを並列に発行することによって、検索を高速化することが好ましい。ボックス1000において、多数の検索要求が、図１０の処理の多数の例によって、同時に処理される場合もある。
【００６９】
考察
自己組織化の成功
二次仮想ネットワークの目的は、いくつかの接続されないネットワークとは対照的に、１つのネットワークへ一緒にグループ化されるべき全てのノードを自己組織化することである。これに当てはまるかどうかは、主として、最初の通知メッセージがどのように生成されるかに依存する。例えば、全てを一緒にグループ化すべき１２個のノードのグループがあるが、このグループの中の５つのノードのみが、この５つのノードを含むこのグループ内の他のノードについての通知を受信し、他の７つのノードの何れも、これらの５つのノードの何れについても通知されないときは、ノードは、１つのネットワークへ自己組織化することはできない。その代りに、それらは、２つの別個のネットワーク、すなわち、５つのノードをもつものと、７つのノードをもつものへ配置する。しかしながら、最初の通知が、ノードが１つのネットワークへ自己組織化することができないというものでない限り、自己組織化処理は、ノードが１つのネットワークへ自己組織化しない可能性は非常に低い。自己組織化が1つのネットワークを生成する確率の計算は、複雑であり、最初の通知が生成される機構に依存する。しかしながら、幾つかの異なる最初の通知機構で経験したシミュレーションにおいて、これまでは、ノードが、1つのネットワークに自己組織化することに失敗したことはない。
【００７０】
悪質なノードのロバスト性
これまでは、全てのノードがプロトコルにしたがうと仮定されていた。しかしながら、規則にしたがって動作しない悪質なノードがあることがある。これらは、他のノードによって維持されているリンクを切断することを試みるか、または自分への多過ぎるリンクを設定しすることを試みるか、あるいはこの両者を行う。全体的なシステムは、このような悪用に対して可能な限りロバストであることが望ましい。
【００７１】
これまで記載してきたシステムは、悪質なノードに対して、既に相当にロバストである。その理由は、各ノードが、リンク照会メッセージ−リンクメッセージの交換を用いて、自分自身のリンクを変更する前に、他の関連するノードによって維持されているリンクを常に検査しているからである。例えば、ノードは、リンク追加メッセージを受信するとき（図３参照）、最初に、送信ノードを自分自身のリンクとして加える前に、送信ノードが実際に自分にリンクしたかを検査する。
【００７２】
しかしながら、システムは、依然として、相対的欠点をもつ。現状では、ノードは、リンクメッセージに応答するとき、容易に“嘘をつく”ことができる。ノードは、しばしば、受信ノードが自分にリンクしたかを検査するリンク照会メッセージを送る。これを知ると、受信ノードは、自分が、リンクメッセージの送信側をリンクとして常に含んでいるように変更された偽のリンクメッセージで応答することができる。これは、ノードが、自分にリンクしている許容数のＬ個よりも相当に多いノードをもつことを可能にする。その結果、これは、システム内の“好適な”リンクの総数を相当に低減する。
【００７３】
都合のよいことに、この欠点に対処する方法がある。これは、ノードが、プロキシノードを介してリンク照会を送るときに達成することができる。ノードが照会を送りたいときは、いつも、これらのプロキシが無作為に選択される。各ノードは、例えば、自分が現在プロキシとしてリンクしているノードを使用することができる。したがって、ノード（Ａ）が別のノード（Ｂ）のリンクを知りたいとき、ノードＢにはノードＡが分からない。その理由は、ノードＢが受信するリンク照会メッセージは、プロキシノード（Ｃ）からであり、かつノードＢがノードＣから受信するメッセージは、ノードＡを全く参照していないからである。したがって、ノードＢが、全システムにとって重要な影響を与える偽のメッセージを送るための好適な方法はない。
【００７４】
もちろん、悪質なプロキシの影響について問題がある。明らかに悪質なプロキシは有害な影響をもつ（プロトコルに従わないノードが、性能にある程度影響を与えるのは、避けられない）が、この影響は制限される。この理由は、悪質なプロキシは、送るように要求されたリンク照会を悪質に処理できるだけであり、これらの要求は全ノードにおいてほぼ均等に分散されるからである。他方で、プロキシが使用されないときは、悪質なノードは、非常にアクティブであることによって、大きな破壊を生じることがある。これらのノードが多くの疑似のリンク追加メッセージを送り、次に送る多くのリンクメッセージを偽造するとき、全システムに与える影響は、相当により大きい。
【００７５】
一次仮想ネットワーク
一次ネットワークは、上述の国際特許出願に詳しく記載されている。ここでは、基本的な検索および自己組織化機構を、二次ネットワークの自己組織化を駆動するための通知メッセージの生成を可能にする変更と共に、記載する。
最初に、この機構によって使用される仮想座標空間の概念を説明する必要がある。各ノードがラベルをもつことは、既に記載した。ラベルは、仮想空間における座標へ変換される。空間は、一次元、二次元、またはより高い次元であってもよい。精密な変換機構は、あまり重要ではない。一次元空間では、二値であると考えられるラベルを、座標として直接に使用することができる。二次元以上の次元では、一連のビットであると考えられるラベルを２つ以上の等しいグループへ分割し、二値であると考えられる各グループが座標の１つを形成するという方法が好ましい。各座標（または、一次元空間における座標）は、範囲［１，０］に位置するように基準化される。
【００７６】
この仮想空間内の２つのラベル間の距離は、２つの座標の組の間のユークリッド距離である（しかしながら、希望であれば、市街区距離（しばしばマンハッタン距離と呼ばれる）のような他の距離を使用してもよい）。
【００７７】
【数１】
既に記載したように、この点において、各ノードは、他のノードへのリンクを表わす多数のエントリを含むリスト22（図１）をもっている。各エントリは、このような別のノードのラベルおよびアドレスを含んでいる。最初に、このリストは空であり、したがって、ノードは、ブートストラップリンク、すなわち、幾つかのリンク（一般的に、４つ）の第２の、同様の、リストをもち、最初に、ネットワークの他のノードに接触することができる。リスト22内のリンク（短距離リンクと呼ばれる）に加えて、ノードは、階層的に配置された追加のこのようなリスト、または長距離のリンクのリスト、あるいはこの両者ももつ。これらは我々の以前の国際特許出願に記載されているが、オプションであるので、ここには記載しない。
【００７８】
メッセージ
最初に、使用するメッセージを示す（一次仮想ネットワークにおいて使用されるメッセージは、二次仮想ネットワークにおいて使用されるメッセージとは、異なり、完全に独立していることに注意すべきである）。
検出メッセージ（FIND message）は、ノードのルックアップを開始し、満たし、“プル”更新を支援するのに使用される。これらは、
・目標ノードのラベル、および、
・照会を開始したノードのアドレス、
を含む。
【００７９】
検出済みメッセージ(FOUND message)は、照会の結果を戻すのに使用される、これらは、
・目標ノードのラベル、
・検出されたノードのラベル、
・検出されたノードのアドレス、
・検出されたノードと関係付けられる二次ネットワークのノードのアドレス、および、
・アプリケーション別データ−この場合は、検出されたノードと関係付けられるコメントノードのアドレス、
を含む。
【００８０】
プッシュメッセージ(PUSH message)は、ノードのラベルを他のノードへ広告する。これらは、
・対象ノードのラベル、
・対象ノードのアドレス、および、
・目標ノードに到達するための、ホップ ツウ ゴー（hop to go）の数
を含む。
【００８１】
通知メッセージ(NOTIFY message)は、プッシュ更新を伝搬するのに使用される。これらは、
・対象ノードのラベル、および、
・対象ノードのアドレス、
を含む。
検索
図１１は、各ノードが、到来する検出メッセージをどのように処理するかを示している。原則的に、受信ノードは、検出メッセージ内で識別される目標ノードに対して、自分自身よりも近いノードをルックアップし、成功であるときは、検出メッセージ上で送る。成功でないときは、受信ノードは、自分自身のアドレスおよびラベルを戻す。受信ノードは、次に示すステップを実行することにより、これを行う：
ステップ1100：ノードは、目標ノードのラベルおよび開始ノードのアドレスを含む検出メッセージを受信する；
ステップ1105：ノードは、目標ノードのラベルを、ラベル空間の座標へ変換し、自分が記録した全てのリンク（ノード）の中で、ラベル空間内で目標ノードに最も近いものを計算する。該当するノードは、最近ノードとして示される；
ステップ1110：ノードは、自分自身の座標と目標のノードの座標との間の距離を、最近ノードの座標と目標のノードの座標との間の距離と比較する；
ステップ1115：自分自身の座標と目標のノードの座標との間の距離が（等しいか、または）より短いときは、ノードは、ネットワーク10を介して、開始ノードへ、自分自身のラベルとアドレスとを含む検出済みメッセージを送る；
ステップ1120：最近ノードの座標と目標ノードの座標との間の距離が、より短いときは、ノードは、検出メッセージを最近ノードへ送る；
ステップ1115において戻されるノードのアドレスは、目標ラベルをもつノードのアドレスか、またはラベル空間内で目標ラベルに近いノードのアドレスである。戻されたラベルが目標のラベルに整合しないときは、目標のノードが存在しないか、または仮想ネットワークが十分に自己組織化されていないかの何れかを意味する。
【００８２】
プッシュ
各ノードは、プッシュ更新を自発的に開始する。例えば、各ノードは、プッシュ更新処理を定期的に始めてもよい。プッシュ更新において、ノードは、自分自身のラベルおよびアドレスをもつプッシュメッセージを、無作為に並んでいて、その列の長さに制限が設定されたノードを経由して送る。列の中の最後のノードは、通知メッセージを開始ノードへ送る。図１２、１３、および１４は、この処理の種々の部分を示している。
【００８３】
図１２は、ノードが、次のステップを使用して、プッシュ更新をどのように開始するかを示している：
ステップ1200：ノードは、ブートストラップリンクの中から無作為にリンクを選択し、選択されたリンクによって識別されるノードのアドレスを、次のメッセージのための転送アドレスとして入力する；
ステップ1205：ノードは、移動のためのホップのフィールドにおける小さい正の乱数を、プッシュメッセージに入力する；
ステップ1210：ノードは、自分自身のラベルおよびアドレスを、対象ノードのものとしてプッシュメッセージに入力し、ネットワーク10を使用して、プッシュメッセージを転送アドレスのノードへ送る。
【００８４】
図１３および１４は、短距離リンクがどのように更新されるかを示している。プッシュメッセージを通知メッセージと一緒に使用して、短距離リンクを更新する。この更新には２つの段階がある。第１の段階では、各ノードは、受信したメッセージ内の移動のためのホップの値が“０”になるまで、プッシュメッセージを無作為に送る。移動のためのホップの値が“０”であるときは、受信ノードは、通知メッセージを送ることによって、プッシュ更新の第２の段階を始める。第２の段階では、通知メッセージをノードへ連続的に送り、そのラベルは、仮想空間内の対象ノードに次第により近くなる。より近いラベルをもつノードを検出できないときは、必要であれば、最後に検出されたノードへのリンクを更新する。これが常に当てはまるのは、例えば、ノードが、設定された短距離リンクをまだもっていないために、所与の対象ノードを検出できないときである。最後に検出されたノードは、追加の通知メッセージを、リンクの組を潜在的に更新したノードへも送る。
【００８５】
図１３を参照すると、到来するプッシュメッセージを取扱うプッシュ更新の第１の段階は、次のステップを含む：
ステップ1300：ノードはプッシュメッセージを受信する。プッシュメッセージは、対象ノードとして、開始ノードのラベルおよびアドレスを含み、移動のためのホップのフィールドの値をもつ；
ステップ1305：受信ノードは、ブートストラップリンクの中から無作為にリンクを選択し、次のメッセージのための転送アドレスとして、選択されたリンクによって識別されるノードのアドレスを入力する；
ステップ1310および1315：受信ノードは、ホップ ツウ ゴーのフィールドの値を１低減し、ホップ ツウ ゴーの低減値が、依然としてゼロよりも大きいかどうかを検査する；
ステップ1320：低減値が、依然としてゼロよりも大きいときは、ノードは、プッシュメッセージを、自分が入力した転送アドレスへ送る；
ステップ1325：値がゼロであるときは、ノードは、その代りに、対象ノードとして、（受信したプッシュメッセージ内に与えられている）開始ノードのラベルおよびアドレスを、通知メッセージに入力し、通知メッセージを、自分が入力した転送アドレスへ送る。
【００８６】
図１４を参照すると、プッシュ更新を取扱う、すなわち通知メッセージを取扱う、第２の段階は、次に示すステップを含む：
ステップ1400：ノードは、対象ノードとしてのノードのラベルおよびアドレスを含む通知メッセージを受信する；
ステップ1401：受信ノードは、通知メッセージの対象ノードが、受信ノードと同じラベルをもつかどうかを検査する；
ステップ1402：そうであるときは、受信ノードは、通知メッセージの対象ノードが、受信ノードと同じアドレスをもつかどうかを検査する。この場合は、受信ノードは、それ以上の動作を行わない。
【００８７】
しかしながら、通知メッセージの対象ノードが、受信ノードとラベルは同じであるが、アドレスは異なるノードであるときは、２つのイベントが行われる。第１に（ステップ1403）、受信ノードは、到来する通知メッセージの対象ノードへ、短距離リンクの受信ノード自身のリストからの無作為に選択されたノードを、対象ノードとして指定する通知メッセージを送る。第２に、ステップ1404は、二次ネットワークによる動作のために通知メッセージを生成する。しかしながら、受信ノードは、このようなメッセージを直接に生成できない。概して、通信ネットワーク上で、異なる仮想ネットワーク間でメッセージを送るのを避けるのが好ましいが、主な問題は、受信ノードが、二次ネットワークの自分自身のノードのアドレスだけでなく、対象ノードと関係付けられる二次ノードのノードのアドレスも必要とすることである。受信ノードは、このアドレスをもっていない。したがって、２段階の処理が使用される。
【００８８】
第１に、受信ノードは、特定の相互通知（CrossNotify）メッセージを、到来する通知メッセージにおいて対象ノードとして指定された一次ネットワークのノードへ送る。このメッセージは：
・受信ノード（すなわち、到来する（一次ネットワークの）メッセージを受信したノード）のアドレスに設定された、送信側アドレスと；
・到来する通知メッセージに含まれているアドレスに設定された、受信側（または宛先）アドレスと；
・受信ノードと関係付けられた二次ネットワークのノードのアドレスに設定された、対象アドレスとを含む。
【００８９】
最初の２つのアドレスは、一次ネットワーク上のノードのアドレスであり、第３のアドレスは、二次ネットワーク上のノードのアドレスであることに注意すべきである。
第２に、相互通知メッセージを受信する一次ネットワークのノードは、事実上（in effect）、それを、二次ネットワークの関係付けられたノードへ送る。必要であれば、二次ネットワーク上で使用するフォーマットへメッセージを再フォーマットし、（一次ネットワークの）受信側アドレスを、二次ネットワークの関係付けられたノードのアドレスと置換する。次に、メッセージは、ちょうど図３に示されているように処理される。“事実上”という理由は、実際には、相互通知メッセージを受信する一次ネットワークのノードが、二次ネットワークの関係付けられたノードへ、単に、相互通知メッセージの対象フィールドにおいて指定されているアドレスを含んでいる簡単な局所的なメッセージを送ることが好ましいからである。その場合には、図３の処理は、通知レベルを適切な値に設定するステップを含むように変更される。
【００９０】
この処理は、図１５を参照して、例示的に示される。図１５では、ボックスはノードを表わし、矢印はメッセージを表わす。図１４のステップ1400において、一次ネットワークのノードＰ１は、対象ノードとして一次ネットワークのノードＰ２のラベルＬＰ２およびアドレスＡＰ２を含む通知メッセージを受信すると仮定する。ノードＰ１において、対象ノードは、Ｐ１とラベルは同じである（すなわち、ＬＰ１＝ＬＰ２）が、アドレスは異なる（ＡＰ１≠ＡＰ２）ことが分かる（図１４のステップ1401、1402）。ノードＰ１は、二次ネットワークのノードＳ１のアドレスＡＳ１を知り、（図１４のステップ1404において）送信側アドレスＡＰ１、受信側アドレスＡＰ２、および対象アドレスＡＳ１をもつ相互通知メッセージを生成する。このメッセージは、一次ネットワークのノードＰ２において受信され、Ｐ２は、アドレスＡＳ１をもつ局所的な通知メッセージを、二次ネットワークの関係付けられたノードＳ２へ送る。その代わりに、二次ネットワークのノードＳ２は、局所的通知（LocalNotify）メッセージを受信すると、図３のプロセスにしたがってリンク自体を生成する代わりに、（図１５において点線によって示されている）（二次ネットワークの）別の通知メッセージを生成し、これを、対象として自分自身を指定しているノードＳ１へ送る。次に、通知メッセージは、ノードＳ１において、図３の処理を使用して処理される。このオプションは、追加のメッセージを含むが、図３の処理が実行されるとき、通知メッセージは、実際には、メッセージの対象フィールドのアドレスであるノードによって送られ、したがって、対象ノードは、本質的に、依然として存在していると確認される。
【００９１】
ここで図１４に戻って、ステップ1405：受信ノードは、対象ノードのラベルを座標へ変換し、受信ノードが記録した短距離リンクの座標を計算し、仮想空間内の対象ノードの座標に最も近い座標をもつノードのラベルへ導く。該当するノードは、最近ノードを示している：
ステップ1415：受信ノードは、自分自身の座標と対象ノードの座標との間の距離を、最近ノードの座標と対象ノードの座標との間の距離と比較する；
ステップ1415において、受信ノードと対象ノードとの間の距離が、同じか、またはより短いことが検出されると、受信ノードは、対象ノードのラベルおよびアドレスを、自分自身の短距離リンクの組内のリンクとして追加し（ステップ1420：この処理は、図１６を参照して、別途詳しく記載する）、受信ノードのラベルおよびアドレスを含む通知メッセージを対象ノードへ送り（ステップ1430）、対象ノードのラベルおよびアドレスを含む通知メッセージを最近ノードへ送る（ステップ1435）；
ステップ1415において、最近ノードと対象ノードとの間の距離が、より長いことが検出されると、受信ノードは、ステップ1435へ戻り、対象ノードのラベルおよびアドレスを含む通知メッセージを最近ノードへ送る。
【００９２】
図１６は、ノードが短距離リンクを更新するときに、どのように動作するかをより詳しく示している。これは、新しいリンクを短距離リンクへ加え、このリンクによって取り替えられる全短距離リンクを取り除く。
図１６を参照すると、ノードは、例えば、図１４のステップ1420の結果として、新しいリンクを短距離リンクのリストへ加えることが必要である。
【００９３】
ステップ1600：更新ノード（すなわち、短距離リンクの組への更新を実行するノード）は、新しいリンクのノードのラベルおよびアドレスをもつ；
ステップ1605：更新ノードは、更新ノードよりも、新しいノードにより近いノードに関係する全ての既存のリンクを識別する。これらの識別されたリンクは取り替えられる。これらのリンクを識別するために、更新ノードは、各既存のリンクごとに、新しいノードの座標と、既存のリンクにおいて特定されているノードの座標との間の距離を計算する。更新ノードは、これらの距離の各々を、自分自身の座標と、各既存のリンクにおいて特定されているノードの座標との間の距離と比較する；
ステップ1610：新しいノードに関係する距離が、更新ノードに関係する距離よりも短い全リンクを、短距離リンクから取り除く；
ステップ1620：更新ノードは、新しいノードのリンクを短距離リンクへ加える。
【図面の簡単な説明】
【００９４】
【図１】本発明の１つの実施形態において使用されているコンピュータのブロック図。
【図１Ａ】一次および二次仮想ネットワークを使用するデータ検索動作を示すフローチャート。
【図２】コンピュータネットワークのノード間のリンクの管理を示す模式図。
【図３】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図４】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図５】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図６】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図７】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図８】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図９】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１０】二次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１１】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１２】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１３】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１４】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【図１５】図１４に示されている処理中のメッセージの流れを示す模式図。
【図１６】一次仮想ネットワークのノードの動作の態様を示すフローチャート。
【符号の説明】
【００９５】
２・・・メモリ、３・・・ディスプレイ、４・・・キーボード、５・・・通信インターフェイス。
【特許請求の範囲】
【請求項１】
ノードを含むコンピュータネットワークであって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索手段と、
−第１の検索手段によって識別されたアドレスを受信し、それに応答して、同じラベルに整合する別のノードのアドレスを識別するように動作可能であるように接続された第２の検索手段とをもち、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索手段が、第１の検索手段によって識別されたアドレスへ照会メッセージを送り、応答を受信すると、その照会メッセージへの応答か、または場合によっては、後の照会メッセージへの応答に含まれているアドレスへ照会メッセージを反復的に送るように動作可能なコンピュータネットワーク。
【請求項２】
第１の検索手段が、仮想ノードの一次ネットワークによって形成され、各ノードが、二次ネットワークの他のノードへのリンクのリストによって定められており、リスト内の各エントリが、各他のノードのラベルおよびアドレスを含み、各ノードが、ラベルを含む要求メッセージの受信に応答して、ネットワーク内で要求メッセージを伝搬する手段と、それを受信するノードのラベルに整合するラベルを含む要求メッセージの受信に応答して、応答メッセージを生成する手段とを含む請求項１記載のコンピュータネットワーク。
【請求項３】
第２の検索手段が、仮想ノードの二次ネットワークによって形成され、各ノードが、一次ネットワークへの他のノードのリンクのリストによって定められており、リスト内の各エントリが、各他のノードのアドレスを含み、各ノードが、要求メッセージの受信に応答して、リストのアドレスを含む応答メッセージを生成する手段を含む請求項１または２記載のコンピュータネットワーク。
【請求項４】
一次ネットワークのノードによって生成される応答メッセージが、応答メッセージを生成するノードと関係付けられた二次ネットワークのノードのアドレスを含む請求項２に従属するときに請求項３記載のコンピュータネットワーク。
【請求項５】
一次ネットワークの各ノードが、各々が一次ネットワークの開始ノードのラベルおよびアドレスを含む探索メッセージを開始し、伝搬するように動作可能な手段を含み、
各ノードが、受信ノードのラベルに整合するラベルと、受信ノードのアドレスに整合しないアドレスとを含む探索メッセージを受信すると、二次ネットワークへのリンクの追加のために通知メッセージを生成するように動作可能であり、前記通知メッセージが、探索メッセージを開始するノードを識別し、受信ノードと関係付けられた二次ネットワークのノードのアドレスを含む請求項２に従属するときに請求項３記載か、または請求項４記載のコンピュータネットワーク。
【請求項６】
通知メッセージが、宛先として、開始ノードのアドレスを含み、開始ノードが、それを受信すると、開始ノードと関係付けられた二次ネットワークのノードへ、それと、通知メッセージに含まれているアドレスをもつノードとの間のリンクの追加を要求するメッセージを送るように動作可能である請求項５記載のコンピュータネットワーク。
【請求項７】
二次ネットワークの各ノードが、次の動作を行うようにプログラムされた処理手段を含み、動作が、
メッセージを受信することと、
リストの内容に関する情報を要求するメッセージに応答することと、
受信した要求にしたがって、リストからアドレスを取り除き、別のアドレスをリストへ挿入することと、
ノードと第２のノードとの間のリンクを要求するメッセージの受信に応答して、
（Ａ）リストの内容に関する情報を要求する、第２のノードへのメッセージを生成することと、
（Ｂ）第１のノードと第２のノードとの両者が、所定数よりも少ないアドレス数をリスト内にもっているかどうかを判断することと、
（Ｃ）この状態が満たされたときは、そのリスト内へ第２のノードのアドレスを挿入し、第２のノードにノードのアドレスをそのリストに追加するように要求する、第２のノードへのメッセージを生成することと、
（Ｄ）この状態が満たされないときは、ノードが、所定数よりも少なくとも２つ少ないアドレス数をリスト内に含んでいるかどうかを判断し、そうであるときは、
（ａ）第２のノードのリストから、第３のノードのアドレスを選択することと、
（ｂ）第２のノードのアドレスを第１のノードのリストへ挿入し、第３のノードのアドレスを第１のノードのリストへ挿入することと、
（ｃ）第２のノードのリストから、第３のノードのアドレスを取り除き、ノードのアドレスを挿入することを要求する、第２のノードへのメッセージを生成することと、
（ｄ）第３のノードのリストから第２のノードのアドレスを取り除き、ノードのアドレスを挿入することを要求する、第３のノードへのメッセージを生成することとを含む請求項１ないし６の何れか１項記載のコンピュータネットワーク。
【請求項８】
ノードを含むコンピュータネットワークを動作する方法であって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索動作を行うことと、
−第１の検索手段によって識別されたアドレスに応答して、同じラベルに整合する別のノードのアドレスを識別する第２の検索動作を行うこととを含み、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索動作が、第１の検索手段によって識別されるアドレスに照会メッセージを送ることと、応答を受信すると、その照会メッセージへの応答か、または場合によっては、次の照会メッセージへの応答に含まれているアドレスに照会メッセージを反復的に送ることとを含む方法。
【請求項９】
第１の検索動作が、仮想ノードの一次ネットワークを使用し、各ノードが、一次ネットワークの他のノードへのリンクのリストによって定められていて、リスト内の各エントリが、各他のノードのラベルおよびアドレスを含む方法であって、
−ラベルを含む要求メッセージを受信するステップと、
−ネットワーク内で要求メッセージを伝搬するステップと、
−それを受信するノードのラベルに整合するラベルを含む要求メッセージのノードに到達すると、応答メッセージを生成するステップとを含む請求項８記載の方法。
【請求項１０】
第２の検索動作が、仮想ノードの二次ネットワークを使用し、各ノードが、二次ネットワークの他のノードへのリンクのリストによって定められていて、リスト内の各エントリが、各他のノードのアドレスを含む方法であって、要求メッセージがノードに到達すると、そのノードのリストのアドレスを含む応答メッセージを生成することを含む請求項８または９記載の方法。
【請求項１１】
一次ネットワークのノードによって生成される応答メッセージが、応答メッセージを生成するノードと関係付けられた二次ネットワークのノードのアドレスを含む請求項９に従属するとき請求項１０記載の方法。
【請求項１２】
一次ネットワークの各ノードが、各々が、一次ネットワークの開始ノードのラベルおよびアドレスを含んでいる探索メッセージを開始し、伝搬するように動作可能な手段を含む方法であって、
受信ノードのラベルに整合するラベルと、受信ノードのアドレスに整合しないアドレスとを含む探索メッセージのノードに到達すると、二次ネットワークへのリンクの追加のための通知メッセージを生成することを含み、前記通知メッセージが、探索メッセージを開始するノードを識別し、受信ノードと関係付けられた二次ネットワークのノードのアドレス含む請求項９に依存するときに請求項１０記載の、または請求項１記載の方法。
【請求項１３】
通知メッセージが、宛先として、開始ノードのアドレスを含み、開始ノードが、それを受信すると、開始ノードと関係付けられた二次ネットワークのノードへ、それと、通知メッセージに含まれるアドレスをもつノードとの間のリンクの追加を要求するメッセージを送る請求項１２記載の方法。
【請求項１４】
（ｉ）二次仮想ネットワークの第１のノードと第２のノードとの間のリンクを要求する通知メッセージを受信することと、
（ｉｉ）第１のノードおよび第２のノードの両者が、各場合において、所定数よりも少ないアドレス数をそのリスト内にもっているかどうかを判断することと、
（ｉｉｉ）この条件が満たされるときは、第１のノードのアドレスを第２のノードのリスト内へ挿入し、第２のノードのアドレスを第１のノードのリスト内へ挿入することと、
（ｉｖ）この条件が満たされないときは、第１のノードが、所定数よりも少なくとも２つ少ないアドレス数をそのリスト内にもっているかどうかを判断し、そうであるときは、
（ａ）第２のノードのリストから、第３のノードのアドレスを選択し、
（ｂ）第２のノードのリストから、第３のノードのアドレスを取り除き、
（ｃ）第３のノードのリストから、第２のノードのアドレスを取り除き、
（ｄ）第２のノードのアドレスを第１のノードのリストへ挿入し、第３のノードのアドレスを第１のノードのリストへ挿入し、
（ｅ）第１のノードのアドレスを第２のノードのリストへ挿入し、第１のノードのアドレスを第３のノードのリストへ挿入することとをさらに含む請求項１０ないし１３の何れか１項記載の方法。
【請求項１５】
リンクを要求するメッセージが、第１のノードにおいて受信され、ステップ（ｉｉｉ）において、
第２のノードのアドレスが、それが未確認であることを示すマーカを付された第１のノードのリスト内へ挿入され、
第１のノードから第２のノードへ送られるメッセージが、第２のノードに、第２のノードのリンクへ第１のノードのアドレスを追加することを要求し、
第２のノードにおいて、アドレスが追加され、確認のメッセージが、第１のノードへ送られ、
第１のノードにおいて、肯定応答のメッセージを受信すると、“未確認”のマーカが取り除かれる請求項１４記載の方法。
【請求項１６】
ノードが指定されたノードのアドレスをそのリストに加えるように要求するメッセージを受信すると、ノードが、先ず、指定されたノードのリストのコピーを要求するメッセージを指定されたノードへ送り、最初に、ノードが、要求を受信したノードのアドレスを含むリストを、指定されたノードから受信するときのみ、前記要求にしたがう請求項１５記載の方法。
【請求項１７】
リンクを要求するメッセージが、第１のノードにおいて受信され、
第１のノードが、第２のノードのリストのコピーの要求を、第２のノードへ送り、
第２のノードが、第１のノードへ要求されたコピーを送り、
リストから第３のノードのアドレスを選択するステップ（ｉｖ）の（ａ）が、第１のノードにおいて行われ、
ステップ（ｉｖ）の（ａ）および（ｂ）では、
第１のノードが、第２のノードのアドレスと第３のノードのアドレスとを、第１のノードのリストに、各場合に、それが未確認であることを示すマーカを付して、追加し、
第１のノードが、第２のノードがそのリストから第３のノードのアドレスを取り除き、それを第１のノードのアドレスと置換することを要求するメッセージを、第２のノードへ送り、
第１のノードが、第３のノードがそのリストから第２のノードのアドレスを取り除き、それを第１のノードのアドレスと置換することを要求するメッセージを、第３のノードへ送り、
第２のノードが、このようなメッセージを受信すると、そのリストから第３のノードのアドレスを取り除き、それを第１のノードのアドレスと置換し、確認のメッセージを第１のノードへ送り、
第３のノードが、このようなメッセージを受信すると、そのリストから第２のノードのアドレスを取り除き、それを第１のノードのアドレスと置換し、確認のメッセージを第１のノードへ送り、
第１のノードが、第２のノードまたは第３のノードから確認のメッセージを受信すると、そのリストから各“未確認”マーカを取り除くことが行われる請求項１４ないし１６の何れか１項記載の方法。
【請求項１８】
ノードが、そのリストから、別のノードのアドレスを取り除き、それを、指定されたアドレスのノードと置換することを要求するメッセージを受信すると、ノードが、最初に、指定されたノードのリストのコピーを要求するメッセージを、指定されたノードへ送り、次に、ノードが、指定されたノードから、要求を受信したノードのアドレスを含むリストを受信するときのみ、前記要求にしたがう請求項１７記載の方法。
【請求項１９】
指定されたノードへのリスト要求メッセージと、そのようなメッセージへの応答とが、リスト要求メッセージを送るノードのアドレスが、指定されたノードへ伝えられないように、中間ノードを介して送られる請求項１６ないし１８の何れか１項記載の方法。
【請求項２０】
各ノードが少なくとも１つのスペアリンクを記憶する手段をさらに含み、
第１のノードが、所定数と同数のアドレス数を、そのリスト内にもつときに、第１のノードと第２のノードとの間のリンクを要求するメッセージを受信する場合に、第２のノードのアドレスを、前記スペアリンクの記憶装置へ挿入することと、
第１のノードと別のノードとの間のリンクを要求する後のメッセージを受信すると、そのメッセージを、第１のノードのスペアリンク記憶手段から検索したアドレスへ送ることとを含む請求項１４ないし１９の何れか１項記載の方法。
【請求項１】
ノードを含むコンピュータネットワークであって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索手段と、
−第１の検索手段によって識別されたアドレスを受信し、それに応答して、同じラベルに整合する別のノードのアドレスを識別するように動作可能であるように接続された第２の検索手段とをもち、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索手段が、第１の検索手段によって識別されたアドレスへ照会メッセージを送り、応答を受信すると、その照会メッセージへの応答か、または場合によっては、後の照会メッセージへの応答に含まれているアドレスへ照会メッセージを反復的に送るように動作可能なコンピュータネットワーク。
【請求項２】
第１の検索手段が、仮想ノードの一次ネットワークによって形成され、各ノードが、二次ネットワークの他のノードへのリンクのリストによって定められており、リスト内の各エントリが、各他のノードのラベルおよびアドレスを含み、各ノードが、ラベルを含む要求メッセージの受信に応答して、ネットワーク内で要求メッセージを伝搬する手段と、それを受信するノードのラベルに整合するラベルを含む要求メッセージの受信に応答して、応答メッセージを生成する手段とを含む請求項１記載のコンピュータネットワーク。
【請求項３】
第２の検索手段が、仮想ノードの二次ネットワークによって形成され、各ノードが、一次ネットワークへの他のノードのリンクのリストによって定められており、リスト内の各エントリが、各他のノードのアドレスを含み、各ノードが、要求メッセージの受信に応答して、リストのアドレスを含む応答メッセージを生成する手段を含む請求項１または２記載のコンピュータネットワーク。
【請求項４】
一次ネットワークのノードによって生成される応答メッセージが、応答メッセージを生成するノードと関係付けられた二次ネットワークのノードのアドレスを含む請求項２に従属するときに請求項３記載のコンピュータネットワーク。
【請求項５】
一次ネットワークの各ノードが、各々が一次ネットワークの開始ノードのラベルおよびアドレスを含む探索メッセージを開始し、伝搬するように動作可能な手段を含み、
各ノードが、受信ノードのラベルに整合するラベルと、受信ノードのアドレスに整合しないアドレスとを含む探索メッセージを受信すると、二次ネットワークへのリンクの追加のために通知メッセージを生成するように動作可能であり、前記通知メッセージが、探索メッセージを開始するノードを識別し、受信ノードと関係付けられた二次ネットワークのノードのアドレスを含む請求項２に従属するときに請求項３記載か、または請求項４記載のコンピュータネットワーク。
【請求項６】
通知メッセージが、宛先として、開始ノードのアドレスを含み、開始ノードが、それを受信すると、開始ノードと関係付けられた二次ネットワークのノードへ、それと、通知メッセージに含まれているアドレスをもつノードとの間のリンクの追加を要求するメッセージを送るように動作可能である請求項５記載のコンピュータネットワーク。
【請求項７】
二次ネットワークの各ノードが、次の動作を行うようにプログラムされた処理手段を含み、動作が、
メッセージを受信することと、
リストの内容に関する情報を要求するメッセージに応答することと、
受信した要求にしたがって、リストからアドレスを取り除き、別のアドレスをリストへ挿入することと、
ノードと第２のノードとの間のリンクを要求するメッセージの受信に応答して、
（Ａ）リストの内容に関する情報を要求する、第２のノードへのメッセージを生成することと、
（Ｂ）第１のノードと第２のノードとの両者が、所定数よりも少ないアドレス数をリスト内にもっているかどうかを判断することと、
（Ｃ）この状態が満たされたときは、そのリスト内へ第２のノードのアドレスを挿入し、第２のノードにノードのアドレスをそのリストに追加するように要求する、第２のノードへのメッセージを生成することと、
（Ｄ）この状態が満たされないときは、ノードが、所定数よりも少なくとも２つ少ないアドレス数をリスト内に含んでいるかどうかを判断し、そうであるときは、
（ａ）第２のノードのリストから、第３のノードのアドレスを選択することと、
（ｂ）第２のノードのアドレスを第１のノードのリストへ挿入し、第３のノードのアドレスを第１のノードのリストへ挿入することと、
（ｃ）第２のノードのリストから、第３のノードのアドレスを取り除き、ノードのアドレスを挿入することを要求する、第２のノードへのメッセージを生成することと、
（ｄ）第３のノードのリストから第２のノードのアドレスを取り除き、ノードのアドレスを挿入することを要求する、第３のノードへのメッセージを生成することとを含む請求項１ないし６の何れか１項記載のコンピュータネットワーク。
【請求項８】
ノードを含むコンピュータネットワークを動作する方法であって、
−ラベルの入力に応答して、そのラベルに整合するノードのアドレスを識別する第１の検索動作を行うことと、
−第１の検索手段によって識別されたアドレスに応答して、同じラベルに整合する別のノードのアドレスを識別する第２の検索動作を行うこととを含み、
所与のラベルに整合する各ノードが、同じラベルに整合する他のノードのアドレスを含むデータ記憶領域をそれと関係付けて、照会メッセージに応答して、リストのアドレスを含むメッセージを戻し、
第２の検索動作が、第１の検索手段によって識別されるアドレスに照会メッセージを送ることと、応答を受信すると、その照会メッセージへの応答か、または場合によっては、次の照会メッセージへの応答に含まれているアドレスに照会メッセージを反復的に送ることとを含む方法。
【請求項９】
第１の検索動作が、仮想ノードの一次ネットワークを使用し、各ノードが、一次ネットワークの他のノードへのリンクのリストによって定められていて、リスト内の各エントリが、各他のノードのラベルおよびアドレスを含む方法であって、
−ラベルを含む要求メッセージを受信するステップと、
−ネットワーク内で要求メッセージを伝搬するステップと、
−それを受信するノードのラベルに整合するラベルを含む要求メッセージのノードに到達すると、応答メッセージを生成するステップとを含む請求項８記載の方法。
【請求項１０】
第２の検索動作が、仮想ノードの二次ネットワークを使用し、各ノードが、二次ネットワークの他のノードへのリンクのリストによって定められていて、リスト内の各エントリが、各他のノードのアドレスを含む方法であって、要求メッセージがノードに到達すると、そのノードのリストのアドレスを含む応答メッセージを生成することを含む請求項８または９記載の方法。
【請求項１１】
一次ネットワークのノードによって生成される応答メッセージが、応答メッセージを生成するノードと関係付けられた二次ネットワークのノードのアドレスを含む請求項９に従属するとき請求項１０記載の方法。
【請求項１２】
一次ネットワークの各ノードが、各々が、一次ネットワークの開始ノードのラベルおよびアドレスを含んでいる探索メッセージを開始し、伝搬するように動作可能な手段を含む方法であって、
受信ノードのラベルに整合するラベルと、受信ノードのアドレスに整合しないアドレスとを含む探索メッセージのノードに到達すると、二次ネットワークへのリンクの追加のための通知メッセージを生成することを含み、前記通知メッセージが、探索メッセージを開始するノードを識別し、受信ノードと関係付けられた二次ネットワークのノードのアドレス含む請求項９に依存するときに請求項１０記載の、または請求項１記載の方法。
【請求項１３】
通知メッセージが、宛先として、開始ノードのアドレスを含み、開始ノードが、それを受信すると、開始ノードと関係付けられた二次ネットワークのノードへ、それと、通知メッセージに含まれるアドレスをもつノードとの間のリンクの追加を要求するメッセージを送る請求項１２記載の方法。
【請求項１４】
（ｉ）二次仮想ネットワークの第１のノードと第２のノードとの間のリンクを要求する通知メッセージを受信することと、
（ｉｉ）第１のノードおよび第２のノードの両者が、各場合において、所定数よりも少ないアドレス数をそのリスト内にもっているかどうかを判断することと、
（ｉｉｉ）この条件が満たされるときは、第１のノードのアドレスを第２のノードのリスト内へ挿入し、第２のノードのアドレスを第１のノードのリスト内へ挿入することと、
（ｉｖ）この条件が満たされないときは、第１のノードが、所定数よりも少なくとも２つ少ないアドレス数をそのリスト内にもっているかどうかを判断し、そうであるときは、
（ａ）第２のノードのリストから、第３のノードのアドレスを選択し、
（ｂ）第２のノードのリストから、第３のノードのアドレスを取り除き、
（ｃ）第３のノードのリストから、第２のノードのアドレスを取り除き、
（ｄ）第２のノードのアドレスを第１のノードのリストへ挿入し、第３のノードのアドレスを第１のノードのリストへ挿入し、
（ｅ）第１のノードのアドレスを第２のノードのリストへ挿入し、第１のノードのアドレスを第３のノードのリストへ挿入することとをさらに含む請求項１０ないし１３の何れか１項記載の方法。
【請求項１５】
リンクを要求するメッセージが、第１のノードにおいて受信され、ステップ（ｉｉｉ）において、
第２のノードのアドレスが、それが未確認であることを示すマーカを付された第１のノードのリスト内へ挿入され、
第１のノードから第２のノードへ送られるメッセージが、第２のノードに、第２のノードのリンクへ第１のノードのアドレスを追加することを要求し、
第２のノードにおいて、アドレスが追加され、確認のメッセージが、第１のノードへ送られ、
第１のノードにおいて、肯定応答のメッセージを受信すると、“未確認”のマーカが取り除かれる請求項１４記載の方法。
【請求項１６】
ノードが指定されたノードのアドレスをそのリストに加えるように要求するメッセージを受信すると、ノードが、先ず、指定されたノードのリストのコピーを要求するメッセージを指定されたノードへ送り、最初に、ノードが、要求を受信したノードのアドレスを含むリストを、指定されたノードから受信するときのみ、前記要求にしたがう請求項１５記載の方法。
【請求項１７】
リンクを要求するメッセージが、第１のノードにおいて受信され、
第１のノードが、第２のノードのリストのコピーの要求を、第２のノードへ送り、
第２のノードが、第１のノードへ要求されたコピーを送り、
リストから第３のノードのアドレスを選択するステップ（ｉｖ）の（ａ）が、第１のノードにおいて行われ、
ステップ（ｉｖ）の（ａ）および（ｂ）では、
第１のノードが、第２のノードのアドレスと第３のノードのアドレスとを、第１のノードのリストに、各場合に、それが未確認であることを示すマーカを付して、追加し、
第１のノードが、第２のノードがそのリストから第３のノードのアドレスを取り除き、それを第１のノードのアドレスと置換することを要求するメッセージを、第２のノードへ送り、
第１のノードが、第３のノードがそのリストから第２のノードのアドレスを取り除き、それを第１のノードのアドレスと置換することを要求するメッセージを、第３のノードへ送り、
第２のノードが、このようなメッセージを受信すると、そのリストから第３のノードのアドレスを取り除き、それを第１のノードのアドレスと置換し、確認のメッセージを第１のノードへ送り、
第３のノードが、このようなメッセージを受信すると、そのリストから第２のノードのアドレスを取り除き、それを第１のノードのアドレスと置換し、確認のメッセージを第１のノードへ送り、
第１のノードが、第２のノードまたは第３のノードから確認のメッセージを受信すると、そのリストから各“未確認”マーカを取り除くことが行われる請求項１４ないし１６の何れか１項記載の方法。
【請求項１８】
ノードが、そのリストから、別のノードのアドレスを取り除き、それを、指定されたアドレスのノードと置換することを要求するメッセージを受信すると、ノードが、最初に、指定されたノードのリストのコピーを要求するメッセージを、指定されたノードへ送り、次に、ノードが、指定されたノードから、要求を受信したノードのアドレスを含むリストを受信するときのみ、前記要求にしたがう請求項１７記載の方法。
【請求項１９】
指定されたノードへのリスト要求メッセージと、そのようなメッセージへの応答とが、リスト要求メッセージを送るノードのアドレスが、指定されたノードへ伝えられないように、中間ノードを介して送られる請求項１６ないし１８の何れか１項記載の方法。
【請求項２０】
各ノードが少なくとも１つのスペアリンクを記憶する手段をさらに含み、
第１のノードが、所定数と同数のアドレス数を、そのリスト内にもつときに、第１のノードと第２のノードとの間のリンクを要求するメッセージを受信する場合に、第２のノードのアドレスを、前記スペアリンクの記憶装置へ挿入することと、
第１のノードと別のノードとの間のリンクを要求する後のメッセージを受信すると、そのメッセージを、第１のノードのスペアリンク記憶手段から検索したアドレスへ送ることとを含む請求項１４ないし１９の何れか１項記載の方法。
【図１】
【図１Ａ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１Ａ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公表番号】特表２００７−５０７０３１（Ｐ２００７−５０７０３１Ａ）
【公表日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願番号】特願２００６−５２７４５６（Ｐ２００６−５２７４５６）
【出願日】平成１６年９月１３日（２００４．９．１３）
【国際出願番号】ＰＣＴ／ＧＢ２００４／００３９４１
【国際公開番号】ＷＯ２００５／０３２１０４
【国際公開日】平成１７年４月７日（２００５．４．７）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【公表日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願日】平成１６年９月１３日（２００４．９．１３）
【国際出願番号】ＰＣＴ／ＧＢ２００４／００３９４１
【国際公開番号】ＷＯ２００５／０３２１０４
【国際公開日】平成１７年４月７日（２００５．４．７）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
[ Back to top ]