(57)【要約】  本発明は、適性に基づく経路指定のための方法、システム、およびコンピューター・プログラム生産物に及ぶ。本発明の実施形態は、経路指定表に収容されているルーティング・ノードが、オーバーレイ・ネットワークにおいてメッセージを転送し処理するためのしかるべき（または比較的高い）能力を有する可能性を著しく高める。このため、ノードがメッセージのために経路を決定する場合、選択したルーティング・ノードはいずれも適している（または、少なくとも現在利用可能なものでは最良である）ことの何らかの保証が得られる。更に、送出側ノードは、メッセージを送る際に、適性計量値が高い方のルーティング・ノードを優先することができる。高い方の適性計量値を優先することにより、メッセージがしかるべく転送され処理されることが、更に保証される。したがって、本発明の実施形態は、帯域幅を最適化し、効率的な経路指定能力が得られるように、メッセージを導出するために用いることができる。【選択図】      図１Ｂ
2010536259.tif 000002
【特許請求の範囲】
【請求項１】
コンピューター・システムにおいて、該コンピューター・システムは、オーバーレイ・ネットワーク（１００）の中にノード（１０１）として含まれ、前記オーバーレイ・ネットワーク（１００）は複数の他のノード（１２１）も含み、前記コンピューター・システムにおいて経路指定表を維持する方法であって、
前記オーバーレイ・ネットワーク（１００）内部の指定位置に存在する別のノード（１２１）についてのノード情報（１０７）を受信する行為であって、前記ノード情報（１０７）が当該別のノード（１２１）についての適性情報を含む、行為と、
1つ又は複数のノードを含む経路指定表（１０２）にアクセスする行為であって、前記経路指定表（１０２）の中にある各ノードが、前記コンピューター・システムが前記オーバーレイ・ネットワーク（１００）内にある宛先ノードにメッセージを配信するために、前記メッセージを送ることができるノードであり、前記経路指定表（１０２）の中にある各ノードは、前記オーバーレイ・ネットワーク（１００）内においてメッセージを転送し処理する当該ノードの能力を表す適性計量値を有する、行為と、
前記別のノードについて適性計量値（１０７）を計算する行為であって、前記適性計量値（１０７）は、前記オーバーレイ・ネットワーク（１００）内においてメッセージを転送し処理する前記別のノードの能力を表し、前記適性計量値（１０７）は、前記別のノードについての前記適性情報（１０７）に部分的に基づく、行為と、
前記別のノード（１２１）を前記経路指定表（１０２）に挿入する行為と、
前記経路指定表を複数の範囲（１９１、１９２、１９３）に分割する行為であって、各範囲が前記オーバーレイ・ネットワーク（１００）の一部に対応する、行為と、
前記経路指定表の中にある各ノードを、前記オーバーレイ・ネットワークにおける当該ノードの位置に基づいて、指定された範囲に割り当てる行為と、
最も多くのノードを含む範囲（１９４）を特定する行為と、
前記特定した範囲の中にあるノードの適性計量値に基づいて、前記特定した範囲内において、前記オーバーレイ・ネットワークにおいて最もメッセージを転送し処理することができないノードを特定する行為と、
前記特定したノードを前記経路指定表（１０２）から除去する行為と、
を備えている、方法。
【請求項２】
請求項１記載の方法において、別のノードについてのノード情報を受信する前記行為は、前記別のノードについてのノード表サイズを、前記別のノードの1つ又は複数のその他の特性と共に受信する行為を含む、方法。
【請求項３】
請求項１記載の方法において、経路指定表にアクセスする前記行為は、リング・トポロジにおいてメッセージを導出するために用いることができるノードを収容する経路指定表にアクセスする行為を含む、方法。
【請求項４】
請求項１記載の方法において、前記別のノードについての適性計量値を計算する前記行為は、前記別のノードの経路指定表のサイズに基づいて、適性計量値を計算する行為を含む、方法。
【請求項５】
請求項１記載の方法において、前記経路指定表を複数の範囲に分割する前記行為は、前記経路指定表を複数の範囲に分割する行為を含み、各範囲は、前記コンピューター・システムからの当該範囲の距離に応じて、前記オーバーレイ・ネットワークの指数的に小さくなる一部または指数的に大きくなる一部に対応し、範囲は前記コンピューターに近い程小さく、範囲はコンピューター・システムから遠い程大きくなる、方法。
【請求項６】
請求項１記載の方法において、前記特定した範囲において、前記オーバーレイ・ネットワーク内において最もメッセージを転送し処理することができないノードを特定する前記行為は、最も小さい経路指定表を有するノードを特定する行為を含む、方法。
【請求項７】
請求項１記載の方法において、前記特定したノードを前記経路指定表から除去する前記行為は、最も小さな経路指定表を有するノードを、前記コンピューター・システムの経路指定表から除去する行為を含む、方法。
【請求項８】
請求項１記載の方法であって、更に、
前記経路指定表にアクセスする前に、前記経路指定表をロックする行為と、
前記特定したノードを除去した後に、前記経路指定表のロックを解除する行為と、
を備えている、方法。
【請求項９】
請求項１記載の方法であって、更に、
前記特定したノードを除去した後に、前記経路指定表から１つのルーティング・ノードを選択する行為と、
前記選択したルーティング・ノードにメッセージを送る行為と、
を備えている、方法。
【請求項１０】
コンピューター・システムにおいて、該コンピューター・システムは、オーバーレイ・ネットワークの中にノード（１０１）として含まれ、前記オーバーレイ・ネットワークは複数の他のノードも含み、前記コンピューター・システムにおいて経路指定表（１０２）を維持する方法であって、
前記オーバーレイ・ネットワークの中にある別のノードからメッセージ（１１１）を受信する行為であって、前記メッセージ（１１１）が前記オーバーレイ・ネットワーク（１００）の中にある複数の更に別のノードについてのノード情報を含み、前記ノード情報が、前記複数の更に別のノードの各々についての適性情報を含む、行為と、
前記コンピューター・システムの経路指定表にアクセスする行為であって、前記コンピューター・システムの経路指定表（１０２）が、前記コンピューター・システムが前記オーバーレイ・ネットワーク（１００）内にある宛先ノードにメッセージを導出するために通信することができる複数のノードを含み、前記コンピューター・システムの経路指定表（１０２）の中にある前記複数のノードの各々が、前記オーバーレイ・ネットワークにおいてメッセージを転送し処理する能力を表す適性計量値を有する、行為と、
前記複数の更に別のノードの各々について、
前記更に別のノードについて適性計量値を計算する行為であって、前記適性計量値が、前記オーバーレイ・ネットワーク（１００）内において前記更に別のノードがメッセージを転送し処理する能力を表し、前記適性計量値は、少なくとも部分的に、前記更に別のノードについての適性情報に基づく、行為と、
前記更に別のノードを前記コンピューター・システムの経路指定表（１０２）に挿入する行為と、
を備えており、更に、
前記コンピューター・システムの経路指定表の中にあるノードの数が、指定された数（１６１）を超過したことを判断する行為と、
前記経路指定表を複数の範囲（１９１、１９２、１９３）に分割する行為であって、各範囲が前記オーバーレイ・ネットワーク（１００）の一部に対応する、行為と、
前記経路指定表の中にある各ノードを、前記オーバーレイ・ネットワーク（１００）における当該ノードの位置に基づいて、前記複数の範囲の１つに割り当てる行為と、
最も多いノードを含む範囲（１９４）を特定する行為と、
適性計量値に基づいて、前記特定した範囲におけるノードの間で、最もメッセージを転送し処理するのに適していないノードを、前記経路指定表（１０２）から除去する行為と、
を備えている、方法。
【請求項１１】
請求項１０記載の方法において、前記オーバーレイ・ネットワークの中にある別のノードからメッセージを受信する前記行為は、前記複数の更に別のノードの各々についてのノード表サイズを、前記複数の更に別のノードの各々の1つ又は複数のその他の特性と共に受信する行為を含む、方法。
【請求項１２】
請求項１０記載の方法において、前記更に別のノードについて適性計量値を計算する前記行為は、前記更に別のノードの経路指定表のサイズに基づいて、適性計量を計算する行為を含む、方法。
【請求項１３】
請求項１０記載の方法において、前記更に別のノードについて適性計量値を計算する前記行為は、前記更に別のノードの経路指定表のサイズのみに基づいて、適性計量を計算する行為を含む、方法。
【請求項１４】
請求項１０記載の方法において、前記コンピューター・システムの経路指定表の中にあるノードの数が、指定された数を超過したことを判断する前記行為は、経路指定表の方針を参照する行為を含む、方法。
【請求項１５】
請求項１０記載の方法であって、更に、前記特定した範囲におけるノードの間で、最もメッセージを転送し処理するのに適していないノードを除去した後に、
前記コンピューター・システムの経路指定表の中にあるノードの数が、前記指定された数をもはや超過しなくなるまで、
最も多くのノードを含む次の範囲を特定する行為と、
適性計量値に基づいて、前記次に特定した範囲の中にあるノードの間で、前記メッセージを転送し処理するのに最も適さないノードを、前記経路指定表から除去する行為と、
を繰り返す、方法。
【請求項１６】
請求項１０記載の方法であって、更に、
前記経路指定表にアクセスする前に、前記経路指定表をロックする行為と、
前記特定したノードを除去した後に、前記経路指定表のロックを解除する行為と、
を備えている、方法。
【請求項１７】
請求項１０記載の方法であって、更に、
前記特定したノードを除去した後に、前記経路指定から１つのルーティング・ノードを選択する行為と、
前記選択したルーティング・ノードにメッセージを送る行為と、
を備えている、方法。
【請求項１８】
請求項１０記載の方法において、前記オーバーレイ・ネットワークはリング・トポロジである、方法。
【請求項１９】
請求項１０記載の方法において、前記オーバーレイ・ネットワークは、インターネット上に重ねられたピア・ツー・ピア・ネットワークである、方法。
【請求項２０】
コンピューター・システムにおいて、コンピューター・システムは、二重にリンクされたリング・トポロジを有するオーバーレイ・ネットワークの中にノードとして含まれ、前記オーバーレイ・ネットワークは複数の他のノードも含み、前記コンピューター・システムにおいて経路指定表を維持する方法であって、
前記二重にリンクされたリング・トポロジの中にある別のノードからメッセージを受信する行為であって、前記メッセージが前記別のノードの経路指定表の中にある複数の更に別のノードについてのノード情報を含み、該ノード情報が、前記別のノードの経路指定表における更に別のノード毎に経路指定表のサイズを示す、行為と、
前記メッセージ受信に続くあらゆる経路決定を防止するために前記コンピューター・システムの経路指定表をロックする行為であって、前記コンピューター・システムの経路指定表の中にある各ノードは、前記コンピューター・システムが前記二重にリンクされたリング・トポロジ内にある宛先ノードにメッセージを配信するためにメッセージを送ることができるノードであり、前記コンピューター・システムの経路指定表の中にある前記複数のノードの各々は、前記ノードの対応する経路指定表のサイズの指示と共に格納されている、行為と、
前記複数の更に別のノードを前記コンピューター・システムの経路指定表に統合する行為と、
前記コンピューター・システムの経路指定表の中にあるノードの数が、指定された数を超過していると判断する行為と、
前記経路指定表を複数の範囲に分割する行為であって、各範囲が、二重にリンクされたリング・トポロジの一部に対応する、行為と、
前記経路指定表の中にある各ノードを、前記二重にリンクされているリング・トポロジにおける当該ノードの位置に基づいて、前記複数の範囲の１つに割り当てる行為と、
を備えており、更に、
前記コンピューター・システムの経路指定表の中にあるノードの数が、前記指定された数をもはや超過しなくなるまで、
最も多くのノードを含む範囲を特定する行為と、
前記特定された範囲の中で、指示された経路指定表のサイズが最も小さいノードを特定する行為と、
前記特定したノードを前記コンピューター・システムの経路指定表から除去する行為と、
前記コンピューター・システムの経路指定表の中にあるノードの数がもはや前記指定された数を超過しなくなった後に、前記経路決定において前記コンピューター・システムの経路指定表を再度用いることができるように、前記コンピューター・システムの経路指定表のロックを解除する行為と、
を繰り返す、方法。
【発明の詳細な説明】
【背景技術】
【０００１】
コンピューター・システムおよび関係する技術は、社会の多くの側面に影響を及ぼす。実際、コンピューター・システムが情報を処理することができるために、我々の生活および仕事が様変わりした。コンピューター・システムの出現以前では手作業で行っていた多数の作業（例えば、文書作成、予定管理、口座管理等）をコンピューター・システムが行うのは今では珍しいことではない。更に最近になって、コンピューター・システムが互いに結合され、更に他の電子デバイスにも結合されて、有線およびワイヤレスのコンピューター・ネットワークを形成し、これらを通じてコンピューター・システムおよびその他の電子デバイスが電子コンテンツを転送することが可能になっている。したがって、多くの計算作業の事項は、多数の異なるコンピューター・システムおよび／または多数の異なる計算コンポーネント間で分散されることになる。
【０００２】
オーバーレイ・ネットワークとは、今日の従来からのネットワーク（プライベート・ネットワークおよびインターネット双方）に跨り、これら基礎となるネットワークの細目を覆い隠す均一な視界(view)を提供する構造である。このようなオーバーレイ・ネットワーク上にあるノード間の通信は、意図する終点に到達するまで、具体的なアルゴリズムを用いて、ノード（コンピューター・システム）によってメッセージを導出することから成る。オーバーレイ・ネットワークを経由する経路指定は、今日では主に静的であり、本質的に適応性がない。
【０００３】
オーバーレイ・ネットワークに関与するノードは、経路指定に関する限りにおいて、性質という観点からは同質であるものとして扱われることが多い。つまり、全てのノードは同様の計算パワー、ネットワーク接続性、および知覚負荷(perceived load)を有するという、大まかな想定がある。この想定は、例えば、ノードが、負荷が一定となるように制御されたデーターセンター型環境にある場合のように、少なくとも一部の環境では有効である。しかしながら、多くのその他の環境では、この想定は有効ではない。例えば、インターネットまたはその他の分散型コンピューティング環境上にあるノードは、異質な可変構成負荷（varying configurations load）、および計算処理能力(capacity)を有する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
更に、インターネットおよびその他の分散型ネットワーク上にあるノード間のネットワーク・リンク容量は、ブロードバンドの速度からダイアルアップの速度までの差がある。例えば、地点Ａから地点Ｂに至るには潜在的に可能な２つの経路があると仮定する。一方の経路では、ダイアルアップによって接続されるノードを通過する必要があり、他方のルートでは、高速ブロードバンド接続によって接続されるノードを通過する必要がある。全てのノードが同様に扱われるとすると、確率論的に、最適ではない経路である、ダイアルアップによって接続されるノードを経由してメッセージが導出される可能性があり、メッセージ転送の効率に影響を及ぼす。これらの非効率性およびその他の非効率性は、規模が大きく（例えば、百万単位のノード）、効果的に利用することができる大容量マシンおよびリンクを有するオーバーレイ・ネットワークを用いることによって拡大される可能性がある。
【０００５】
オーバーレイ・ネットワークに伴う少なくとも１つの別の問題は、ノード間において実在情報(presence information)を更新するため（即ち、１つのノードが別のノードの存在に気がついたとき）に用いられるメカニズムである。実在情報を伝搬するための典型的なメカニズムは、ノードの実在情報で、オーバーレイまたはオーバーレイの少なくとも大部分を溢れさせる。実在情報は、オーバーレイの構成機器によって捕獲され、それらの経路指定表の一部として格納され、後続の経路決定に用いられる。しかしながら、オーバーレイ上に実在情報を溢れさせるのは、非常に費用がかかり、しかも多大なネットワーク容量を消費する。そして、この消費されるネットワーク容量は、実際のアプリケーション・メッセージには利用できなくなる。この問題は、例えば、数千個または数百万ものノードが実在情報を発行しているときというように、オーバーレイ・ネットワーク上のノード数が増大するに連れて、非常に悪化する潜在的可能性がある。
【０００６】
また、オーバーレイ・ネットワークに付随する他の問題もある。例えば、オーバーレイ・ネットワークを用いると、オーバーレイ上にある２つの任意のノード間において通信する際に効果的であることが多い。これを行うためには、ソース・ノードは宛先の終点アドレス（ＩＰアドレス／ＤＮＳ名）を必要とする。オーバーレイ・ネットワークは、オーバーレイ全域でメッセージの経路を決定するために、分散メカニズムを採用し、各ノードは、オーバーレイの中にある他のノードの位置について、部分的な知識しかない。メッセージは、宛先ノードに到達するまで、オーバーレイ全域にわたって、発信元から宛先に「より近い」ノードに受け渡され、ホップ(hop)
毎に数値的に宛先に近づいていく。ノード間における経路を考慮する際に「近接度」を唯一の素因として用いると、多くの場合、ノード間における経路の効率低下の原因になる可能性が高い。
【課題を解決するための手段】
【０００７】
本発明は、適性に基づく経路指定のための方法、システム、およびコンピューター・プログラム生産物に及ぶ。本発明の実施形態は、例えば、オーバーレイ・ネットワークの中にあるノードのような、コンピューター・システムに経路指定表を維持することを含む。コンピューター・システムは、オーバーレイ・ネットワーク内部の指定された位置に存在する別のノードについてのノード情報を受信する。このノード情報は、別のノードについての適性情報を含む。
【０００８】
コンピューター・システムは、1つ又は複数のノードを含む経路指定表にアクセスする。経路指定表における各ノードは、オーバーレイ・ネットワーク内部にある宛先ノードまでメッセージを配信するために、コンピューター・システムがメッセージを送ることができるノードであり。経路指定表にある各ノードは、適性計量値を有する。この値は、オーバーレイ・ネットワーク内部において当該ノードがメッセージを転送および処理する能力を表す。コンピューター・システムは、他のノードについて適性計量値を計算する。計算された適性計量値は、オーバーレイ・ネットワーク内部において他のノードがメッセージを転送および処理する能力を表す。適性計量値は、少なくとも部分的に、他のノードについての適性情報に基づく。
【０００９】
コンピューター・システムは、他のノードを経路指定表に挿入する。経路指定表は、複数の範囲に分割されている。各範囲は、オーバーレイ・ネットワークの一部に対応する。コンピューター・システムは、オーバーレイ・ネットワークにおけるノードの位置に基づいて、経路指定表における各ノードを指定範囲に割り当てる。
【００１０】
コンピューターは、最も多いノードを含む範囲を特定する。コンピューター・システムは、特定した範囲の中にあるノードの適性計量値に基づいて、オーバーレイ・ネットワーク内において、特定した範囲内でメッセージを最も転送および処理できないノードを特定する。コンピューター・システムは、この特定したノードを経路指定表から除去する。
【００１１】
実施形態の中には、オーバーレイ・ネットワークにおける複数のノードについてのノード情報を、オーバーレイ・ネットワークにおける他のノードからのメッセージにおいて受信する場合がある。適性計量は、複数のノードの各々について計算され、他のノードの各々は、コンピューター・システムの経路指定表に挿入される。経路指定表の中にあるノードの数が、指定数を超過していないか否か判断する。
【００１２】
経路指定表は、複数の範囲に分割され、各範囲はオーバーレイ・ネットワークの一部に対応する。経路指定表におけるノードの各々は、複数の範囲の１つに割り当てられる。最も多いノードがある範囲を特定する。特定した範囲におけるノードから、適性計量値に基づいて、メッセージを転送および処理するのに最も適さない(least fit)ノードを経路指定表から除去する。ノードが最も多い範囲の特定、および最も適さないノードのその範囲からの除去は、経路指定表の中にあるノードの数がもはや指定数を超過しなくなるまで、継続することができる。
【００１３】
この摘要は、詳細な説明において以下で更に説明する概念から選択したものを、簡略化した形態で紹介するために設けられている。この摘要は、特許請求する主題の主要な特徴や必須の特徴を特定することを意図するのではなく、特許請求する主題の範囲を判断する際に補助として用いることも意図していない。
【００１４】
本発明の更に別の特徴および利点は、以下に続く説明に明記されており、部分的にこの説明から自明であり、あるいは本発明の実施によって習得することもできる。本発明の特徴および利点は、添付した特許請求の範囲に特に指定した手段(instrument)および組み合わせによって実現し、獲得することができる。本発明のこれらおよびその他の特徴は、以下の説明および添付した特許請求の範囲から更に一層明らかとなろうし、あるいは以下に明記するように、本発明の実施によって習得することができる。
【図面の簡単な説明】
【００１５】
本発明の先に明記した利点および特徴ならびにその他の利点および特徴を得ることができる態様について説明するために、添付図面に例示する具体的な実施形態を参照して、先に端的に説明した本発明の一層特定的な説明を行う。これらの図面は本発明の典型的な実施形態のみを図示するのであり、したがってその範囲を限定するように解釈すべきでないことを理解した上で、添付図面の使用により、本発明について更に具体的にそして詳細に記載し説明する。
【図１Ａ】図１Ａは、適性に基づく経路指定を容易にするオーバーレイ・リング・ネットワーク・アーキテクチャの一例の図を示す。
【図１Ｂ】図１Ｂは、経路指定表を維持するオーバーレイ・リング・ネットワーク・アーキテクチャのノード例の図を示す。
【図１Ｃ】図１Ｃは、経路指定表を維持するオーバーレイ・リング・ネットワーク・アーキテクチャのノード例の別の図を示す。
【図１Ｄ】図１Ｄは、経路指定表を維持するオーバーレイ・リング・ネットワーク・アーキテクチャのノード例の別の図を示す。
【図２】図２は、経路指定表を維持する方法の一例のフロー・チャートを示す。
【図３】図３は、経路指定表を維持する方法の別の例のフロー・チャートを示す。
【発明を実施するための形態】
【００１６】
本発明は、適性の基づく経路指定のための方法、システム、およびコンピューター・プログラム生産物に及ぶ。本発明の実施形態は、例えば、オーバーレイ・ネットワークにおけるノードのような、コンピューター・システムにおいて経路指定表を維持することを含む。コンピューター・システムは、オーバーレイ・ネットワーク内において指定された位置に存在する別のノードについてのノード情報を受信する。このノード情報は、他のノードについての適性情報を含む。
【００１７】
コンピューター・システムは、1つ又は複数のノードを含む経路指定表にアクセスし、経路指定表における各ノードは、オーバーレイ・ネットワーク内部にある宛先ノードまでメッセージを配信するために、コンピューター・システムがメッセージを送ることができるノードである。経路指定表にある各ノードは、適性計量値を有する。この値は、オーバーレイ・ネットワーク内部において当該ノードがメッセージを転送および処理する能力を表す。コンピューター・システムは、他のノードについて適性計量値を計算する。計算された適性計量値は、オーバーレイ・ネットワーク内部において他のノードがメッセージを転送および処理する能力を表す。適性計量値は、少なくとも部分的に、他のノードについての適性情報に基づく。
【００１８】
コンピューター・システムは、他のノードを経路指定表に挿入する。経路指定表は、複数の範囲に分割されている。各範囲は、オーバーレイ・ネットワークの一部に対応する。コンピューター・システムは、オーバーレイ・ネットワークにおけるノードの位置に基づいて、経路指定表における各ノードを指定範囲に割り当てる。
【００１９】
コンピューターは、最も多いノードを含む範囲を特定する。コンピューター・システムは、特定した範囲の中にあるノードの適性計量値に基づいて、オーバーレイ・ネットワーク内において特定した範囲内でメッセージを最も転送および処理できないノードを特定する。コンピューター・システムは、この特定したノードを経路指定表から除去する。
【００２０】
実施形態の中には、オーバーレイ・ネットワークにおける複数のノードについてのノード情報を、オーバーレイ・ネットワークにおける他のノードからのメッセージにおいて受信する場合がある。適性計量は、複数のノードの各々について計算され、他のノードの各々は、コンピューター・システムの経路指定表に挿入される。経路指定表の中にあるノードの数が、指定数を超過していないか否か判断する。
【００２１】
経路指定表は、複数の範囲に分割され、各範囲はオーバーレイ・ネットワークの一部に対応する。経路指定表におけるノードの各々は、複数の範囲の１つに割り当てられる。最も多いノードがある範囲を特定する。特定した範囲におけるノードから、適性計量値に基づいて、メッセージを転送および処理するのに最も適さない(least fit)ノードを経路指定表から除去する。ノードが最も多い範囲の特定、および最も適さないノードのその範囲からの除去は、経路指定表の中にあるノードの数がもはや指定数を超過しなくなるまで、継続することができる。
【００２２】
本発明の実施形態は、以下で更に詳しく論ずるように、コンピューター・ハードウェアを含む特殊目的または汎用コンピューターを備えるまたは利用することができる。また、本発明の範囲に該当する実施形態は、コンピューター実行可能命令および／またはデーター構造を搬送または格納するための物理的またはその他のコンピューター読み取り可能媒体も含む。このようなコンピューター読み取り可能媒体は、汎用または特殊目的コンピューター・システムによってアクセスすることができるのであれば、入手できるいずれの媒体でも可能である。コンピューター実行可能命令を格納するコンピューター読み取り可能媒体は、物理的記憶媒体である。コンピューター実行可能命令を搬送するコンピューター読み取り可能媒体は、伝送媒体である。つまり、限定ではなく一例として、本発明の実施形態は、少なくとも２つの全く異なる種類のコンピューター読み取り可能媒体、即ち、物理的記憶媒体および伝送媒体を備えることができる。
【００２３】
物理的記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたはその他の光ディスク・ストレージ、磁気ディスク・ストレージまたはその他の磁気記憶デバイス、あるいは所望のプログラム・コード手段をコンピューター実行可能命令の形態で格納するために用いることができ、汎用または特殊目的コンピューターによってアクセスすることができるのであればその他のいずれの媒体も含む。
【００２４】
この説明およびそれに続く特許請求の範囲では、「物理的ネットワーク」とは、コンピューター・システムおよび／またはモジュールおよび／またはその他の電子デバイス間における電子データーの輸送を可能にする1つ又は複数のデーター・リンクとして定義する。
【００２５】
この説明および以下の特許請求の範囲においては、「オーバーレイ・ネットワーク」とは、別のネットワーク（例えば、物理的ネットワークまたはその他のオーバーレイ・ネットワーク）の上に構築されたコンピューター・ネットワークとして定義する。オーバーレイ・ネットワーク上にあるノードは、仮想リンクまたは論理リンクによって接続されているものと見なすことができ、その各々は、基礎ネットワークにおいて、恐らくは多くの物理的ネットワークおよび／またはデーター・リンクを通過する経路に対応する。例えば、多くのピア・ツー・ピア・ネットワークはオーバーレイ・ネットワークとなる。何故なら、これらはインターネットの上に張られているからである。オーバーレイ・ネットワークは、ＩＰアドレスによって指定されない宛先にメッセージを導出することを可能にするために構築することができる。例えば、分散したハッシュ表を用いて、予めＩＰアドレスがわかっていない、特定の論理アドレスを有するノードにメッセージを導出することができる。
【００２６】
ネットワークまたはその他の通信接続（有線接続、ワイヤレス、あるいは有線接続またはワイヤレスの組み合わせ）を通じてコンピューターに情報を転送または提供するとき、このコンピューターは接続を伝送媒体として適正に見なす。伝送媒体は、所望のプログラム・コード手段をコンピューター実行可能命令またはデーター構造の形態で格納するために用いることができ、汎用または特殊目的コンピューターによってアクセスすることができるネットワークおよび／またはデーター・リンクを含むことができる。前述したものの組み合わせも、コンピューター読み取り可能媒体の範囲内に含まれてしかるべきである。
【００２７】
更に、種々のコンピューター・システム・コンポーネントに到達したときに、コンピューター実行可能命令またはデーター構造の形態となっているプログラム・コード手段は、自動的に伝送媒体から物理的記憶媒体に（またはその逆に）転送することができることは言うまでもない。例えば、コンピューター実行可能命令またはデーター構造をネットワークまたはデーター・リンクを通じて受信すると、ネットワーク・インターフェース・モジュール（例えば、「ＮＩＣ」）の中にあるＲＡＭにバッファすることができ、次いで最終的にコンピューター・システムにおいてコンピューター・システムのＲＡＭおよび／または揮発性の低い物理的記憶媒体に転送することができる。つまり、物理的記憶媒体は、伝送媒体も利用する（または主に利用する場合もある）コンピューター・システム・コンポーネントに含むことができることは言うまでもない。
【００２８】
コンピューター実行可能命令は、例えば、命令およびデーターを含み、これらは、汎用コンピューター、特殊目的コンピューター、または特殊目的処理デバイスに、ある種の機能または機能の集合対を実行させる。コンピューター実行可能命令は、例えば、アセンブリ言語のような二進数の中間フォーマット命令、またはソース・コードとすることもできる。主題は、構造的特徴および／または方法論的行為に特定的な文言で記載しているが、添付する特許請求の範囲において定義する主題は、必ずしも前述の記載した特徴や行為に限定されるのではないことは言うまでもない。逆に、記載する特徴や行為は、特許請求の範囲を実施する形態例として開示するに過ぎない。
【００２９】
本発明は、多くの種類のコンピューター・システム構成を有するネットワークコンピューティング環境においても実施できることは当業者には認められよう。コンピューター・システム構成には、パーソナル・コンピューター、デスクトップ・コンピューター、ラップトップ・コンピューター、メッセージ・プロセッサ、ハンドヘルド・デバイス、マルチプロセッサ・システム、マイクロプロセッサ主体またはプログラマブル消費者用デバイス、ネットワークＰＣ、ミニコンピューター、メインフレーム・コンピューター、移動体電話機、ＰＤＡ、ページャ、ルータ、交換機等が含まれる。また、本発明は分散型システムにおいても実施することができ、この場合、ローカルおよびリモート・コンピューター・システムが、（有線接続データー・リンク、ワイヤレス・データー・リンク、または有線接続およびワイヤレス・データー・リンクの組み合わせのいずれかによって）ネットワークを通じてリンクされており、双方がタスクを実行する。分散型システム環境では、プログラム・モジュールは、ローカルおよびリモート双方のメモリー記憶デバイスに配置することもできる。
【００３０】
図１Ａは、適性に基づく経路指定を容易にするネットワーク・アーキテクチャ１００の図を示す。図１Ａに示すように、ネットワーク・アーキテクチャ１００はリング１５１を含む。リング１５１は、双方向に二重にリンクした２９、即ち５１２の位置のリストであり、これらの位置は、ノードによって専有され、二重リンク・リング・トポロジ（即ち、オーバーレイ・ネットワーク）を設けることができる。リング１５１は、ノード１０１、および経路指定表１０２においてＩＤ番号で掲示する他のノードを含む、複数のノードを含む。一般に、リング１５１は、種々の異なる基礎ネットワークおよび接続を通じて物理的に接続することができるノード間における論理的接続性を表す。例えば、ノードの各々は、システム・バスおよび／または例えば、ローカル・エリア・ネットワーク（「ＬＡＮ」）、ワイド・エリア・ネットワーク（「ＷＡＮ」）、更にはインターネットのような1つ又は複数の基礎ネットワーク（またはその一部）を通じて、互いに物理的に接続することができる。
【００３１】
リング１５１上のノードは、種々のオーバーレイ・プロトコルを用いて、互いに通信することができる。オーバーレイ・プロトコルは、基礎となる物理的ネットワークのプロトコルを構築すること、および／またはそれに基づくことができる。つまり、図示するノードの各々、およびその他の接続されているノードは、メッセージに関するデーターを作成し、メッセージ関係データー（例えば、インターネット・プロトコル（「ＩＰ」）データーグラム、および送信制御プロトコル（「ＴＣＰ」、ハイパーテキスト転送プロトコル（「ＨＴＴＰ」）、シンプル・メール転送プロトコル（「ＳＭＴＰ」）のようなＩＰデーターグラムを利用する、それよりも上位レイヤのプロトコル）を基礎ネットワークを通じて交換することができる。
【００３２】
ノード１０１は、複数のノード（以降「ルーティング・ノード」と呼ぶ）を格納する経路指定表１０２を維持する。ノード１０１は、経路指定表１０２の中にあるルーティング・ノードの各々と直接通信することができる。ノード１０１は、メッセージをルーティング・ノードに送り、ノード１０１よりもルーティング・ノードに近いノードに、メッセージを配信することができる。例えば、メッセージを、ＩＤ＝４０３を有するノードに配信するには、ノード１０１は、ＩＤ＝４０１を有するルーティング・ノードにこのメッセージを送ることができる。
【００３３】
ノード１０１は、経路指定表の方針１６１に応じて、経路指定表１０２を維持することができる。経路指定表の方針１６１は、経路指定表１０２に含めるべきルーティング・ノードの最大数を定めることができる。また、経路指定表の方針１６１は、経路指定表１０２の中にあるノードをどのようにしてある数の範囲に分割するかを示し、範囲当たりのルーティング・ノードの最大数を定めることができる。例えば、経路指定表の方針１６１は、経路指定表１０２を範囲１９１、１９２、１９３、１９４、１９５、１９６、１９７、および１９８に分割できることを示すことができる。
【００３４】
１つの範囲に含まれる範囲ＩＤを可変とし、ノード１０１に近い範囲程濃い密度でルーティング・ノードが位置付けられ、ノード１０１から遠い範囲程薄い密度でルーティング・ノードが位置付けられるようにすることができる。例えば、範囲１９２は、ノード１０１から＋３２ＩＤから＋６４ＩＤまでの範囲の４つのノードを含む。範囲１９４は、＋１２８から＋２４６までの範囲の４つのルーティング・ノードを含む。つまり、範囲１９２および１９４は双方共、４つのルーティング・ノードを含む。しかしながら、範囲１９２の方が濃い密度でノードが位置付けられている。何故なら、範囲１９２における４つのルーティング・ノードの方が、リング１５１上で短い距離にわたって広がっているからである。一方、範囲１９２における４つのルーティング・ノードは、リング１５１上において大きい距離にわたって広がっているので、範囲１９４の方が淡い密度でノードが位置付けられていることになる。
【００３５】
また、経路指定表の方針１６１は、近隣の隣接ノードについて範囲を定めることもできる。例えば、ノード１０１から＋１６から−１６ノードＩＤの範囲に入るノードを、隣接ノードとして自動的に経路指定表１０２に含めることができる。隣接ノードは、先行隣接ノードと後続隣接ノードとの間で分けることができる。例えば、経路指定表１０２は後続隣接ノード１８１および先行隣接ノード１８２を含み、各々ノード１０１に比較的近い（ノード１０１から１６ノードＩＤ以内）３つのノードを有する。
【００３６】
図１Ｂは、経路指定表１０２を維持するノード１０１の図を示す。これより図１Ｂを参照すると、ノード１０１は、適性計算モジュール１０３および経路指定表管理部１０４を含む。適性計算モジュール１０３は、ルーティング・ノードについての適性値を計算するように構成されている。適性計算モジュール１０３は、適性計算アルゴリズムを実装して、ルーティング・ノードについての適性値を計算することができる。一般に、適性値は、ルーティング・ノードのメッセージを処理し導出する能力を示す。
【００３７】
適性値は、種々の異なるタイプのデーターから計算することができ、これらのデーターには、少なくともある程度、ノードのメッセージを処理し導出する能力を示す。例えば、適性値は、ルーティング・ノードの経路指定表のサイズ、ノード１０１とルーティング・ノードとの間のレイテンシ、ルーティング・ノードが送るメッセージの数、およびルーティング・ノードが受信するメッセージの数の内1つ又は複数から計算することができる。適性値を計算するとき、異なるタイプのデーターには異なる重みを付けることができる。実施形態の中には、例えば、経路指定表のサイズのような、１つのタイプのデーターを用いて、適性値を計算する場合もある。
【００３８】
経路指定表管理部１０４は、経路指定表の方針１６１にしたがって、ノードを経路指定表１０２に入れる、およびノードを経路指定表１０２から除去するように構成されている。また、経路指定表管理部１０４は、ルーティング・ノード間において適性値を比較して、保持すべきルーティング・ノードおよび除去すべきルーティング・ノードを決定することもできる。
【００３９】
ノード１０１は、絶えずリング１５１上のノードと通信する。この通信の間に、ノードはそれらに関するノード情報およびリング１５１上にある他のノードに関するノード情報を含ませることができる。ノード情報は、他のノードの経路指定表のサイズ、ノード１０１とノードとの間のレイテンシ、ノードが送ったメッセージ数、およびノードが受信したメッセージ数を含むことができる。受信したノード情報に基づいて、適性計算モジュールは1つ又は複数のノードについて適性値を計算することができる。
【００４０】
経路指定表１０２には、ノードの一部を、それらの対応する適性値と共に保持することができる。例えば、範囲１９３内では、ノードＩＤ７６は適性＝１００を有し、ノードＩＤ９０は適性＝１０００を有し、ノードＩＤ９９は適性＝５０を有し、ノードＩＤ１１２は適性＝５０００を有する。経路指定表管理部１０４は、経路指定表１０２およびその種々の範囲を、指定されている最大値まで、ルーティング・ノードで満たすことができる。指定されている最大値に達した後、経路指定表管理部１０４は、適性計算モジュール１０３と相互動作して、経路指定表１０２のサイズおよびその種々の範囲を、指定されている最大値に維持することができる。
【００４１】
図２は、経路指定表を維持する方法２００のフロー・チャートを示す。方法２００について、図１Ａおよび図１Ｂにおけるコンポーネントおよびデーターに関して説明する。
【００４２】
方法２００は、オーバーレイ・ネットワーク内において指定された位置に存在する別のノードについてのノード情報を受信する行為を含む。ノード情報は、当該他のノードについての適性情報を含む（行為２０１）。例えば、ノード１０１はノード情報１０７を受信することができる。ノード情報１０７は、ノード１２１に関する特性を含む。例えば、ノード情報１０７は、ノード１２１が有する経路指定表のサイズが４５であることを示す。即ち、ノード１２１の経路指定表は４５個のルーティング・ノードを含む。
【００４３】
方法２００は、1つ又は複数のノードを含む経路指定表にアクセスする行為を含む。経路指定表における各ノードは、コンピューター・システムがメッセージをオーバーレイ・ネットワークの中にある宛先ノードに配信するためにそのメッセージを送ることができるノードである。経路指定表の中にある各ノードは、オーバーレイ・ネットワーク内においてそのノードがメッセージを転送し処理する能力を表す適性計量値を有する（行為２０２）。例えば、経路指定表管理部１０４は経路指定表１０２にアクセスすることができる。経路指定表１０２の中にある各ノードは、ノード１０１がメッセージを送りそのメッセージを（リング１５１上の）宛先ノードに配信することができるルーティング・ノードである。また、経路指定表１０２の中にある各ルーティング・ノードは、適性値を有する。例えば、範囲１９３内では、ノードＩＤ７６は適性＝１００を有し、ノードＩＤ９０は適性＝１０００を有し、ノードＩＤ９９は適性＝５５を有し、ノードＩＤ１１２は適性＝５０００を有する。
【００４４】
経路指定表１０２にアクセスする前に、経路指定表管理部１０４は経路指定表１０２をロックすることができる。経路指定表１０２をロックすると、経路指定表１０２に対する他のアクセスが妨げられる（例えば、経路決定）。つまり、ロックすることにより、経路指定表１０２を変更しているときに経路指定表１０２をアクセスすることによる経路指定の誤りの潜在的可能性を軽減する。
【００４５】
方法２００は、他のノードについての適性計量値を計算する行為を含む。適性計量値は、オーバーレイ・ネットワーク内においてメッセージを転送し処理する当該他のノードの能力を表す。適性計量値は、少なくとも部分的に、当該他のノードについての適性情報に基づく（行為２０３）。例えば、適性計算モジュール１０３は、少なくとも部分的にノード情報１０７に基づいて、ノード１２１についての適性値１０７を計算することができる。適性値１０７は、経路指定表のサイズを含む、ノード１２１の1つ又は複数の特性に基づいて計算することができる。適性計量値１０７は、リング１５１内においてメッセージを転送し処理するノード１２１の能力を示す。
【００４６】
方法２００は、他のノードを経路指定表に挿入する行為を含む（行為２０４）。例えば、経路指定表管理部１０４は、ノードＩＤ９７を経路指定表１０２に挿入することができる。方法２００は、経路指定表を複数の範囲に分割する行為を含み、各範囲はオーバーレイ・ネットワークの一部に対応する（行為２０５）。例えば、経路指定表管理部１０４は、経路指定表１０２を範囲１９１〜１９８に分割することができる。
【００４７】
方法２００は、オーバーレイ・ネットワークにおけるノードの位置に基づいて、経路指定表の中にある各ノードを、指定された範囲に割り当てる行為を含む（行為２０６）。例えば、経路指定表管理部は、リング１５１内におけるルーティング・ノードの位置に基づいて、経路指定表１０２の各ルーティング・ノードを、範囲１９１〜１９８から選択した指定範囲に割り当てることができる。図１に示すように、経路指定表１０２を分割し、ルーティング・ノードを範囲に割り当てることができる。加えて、図１Ｂに示すように、ノード１２１を範囲１９３に割り当てることができる。
【００４８】
方法２００は、最も多いノードを含む範囲を特定する行為を含む（行為２０７）。例えば、経路指定表管理部１０４は、範囲１９３が最も多いノードを含むことを特定することができる。範囲１９３は、５つのノードを含み、一方範囲１９２、および１９４〜１９７は４つのノードを含む（隣接ノードはこの特定から除外することができる）。
【００４９】
方法２００は、特定した範囲におけるノードの適性計量値に基づいて、特定した範囲内において、オーバーレイ・ネットワーク内において最もメッセージを転送および処理できないノードを特定する行為を含む（行為２０８）。例えば、経路指定表管理部１０４は、ノードＩＤ９９を、範囲１９３において最も低い計量値を有するものとして特定することができる。コンピューター・アーキテクチャ１００内部において、適性計量値が低い程、メッセージを転送し処理する能力が低いことを示すことができる。したがって、経路指定表管理部１０４は、ノードＩＤ９９を、リング１５１内において最もメッセージを転送し処理することができないルーティング・ノードとして特定することができる。（しかしながら、構成によっては、適性計量値が高い程、メッセージを転送し処理する能力が低いことを示すために用いることができ、あるいは適性計量値からメッセージング処理および転送能力を判断する何らかの他のメカニズムを用いることもできる。）
【００５０】
方法２００は、特定したノードを経路指定表から除去する行為を含む（行為２０９）。例えば、経路指定表管理部１０４は、ノードＩＤ９９を経路指定表１０２から除去することができる。続いて、ノードＩＤ９９を除去するために、経路指定表管理部１０４は経路指定表１０２のロックを解除することができる。経路指定表１０２のロックを解除すると、経路指定表１０２への他のアクセスが可能になる。つまり、ノード１０１は、あらゆる変更が完了した後に、経路指定表１０２を用いて、ルーティング・ノードを特定することができる。
【００５１】
実施形態の中には、ノードが、複数の他のノードについてのノード情報を含むメッセージを受信する場合もある。図１Ｃおよび図１Ｄは、複数のノードについてのノード情報を受信したときに、経路指定表を維持するノード１０１の別の図を示す。図３は、経路指定表を維持する方法３００のフロー・チャートを示す。方法３００について、図１Ｃおよび図１Ｄにおけるコンポーネントおよびデーターに関して説明する。
【００５２】
方法３００は、オーバーレイ・ネットワークにおける別のノードからメッセージを受信する行為を含み、このメッセージはオーバーレイ・ネットワークの中にある複数の更に別のノードについてのノード情報を含み、このノード情報は、これら複数の更に別のノードの各々について適性情報を含む（行為３０１）。例えば、ノード１０１は、リング１５１上にある別のノードからメッセージ１１１を受信することができる。メッセージ１１１は、リング１５１上にある複数の他のノードについてのノード情報を含み、これら複数のノードの各々についての適性情報を含む。例えば、メッセージ１１１は、ノードＩＤ４６、１４４、２４２、および４６０について経路指定表のサイズおよびその他の特性（例えば、送ったメッセージ数、受信したメッセージ数等）を含む。メッセージ１１１の内容は、他のノードの経路指定表またはその一部を表すことができる。
【００５３】
方法３００は、コンピューター・システムの経路指定表にアクセスする行為を含み、コンピューター・システムの経路指定表は、当該コンピューター・システムが通信してオーバーレイ・ネットワーク内部にある宛先ノードにメッセージを導出することができる複数のノードを含み、コンピューター・システムの経路指定表の中にある複数のノードの各々は、オーバーレイ・ネットワーク内においてメッセージを転送し処理する能力を表す適性計量値を有する（行為３０２）。例えば、経路指定表管理部１０４は経路指定表１０２にアクセスすることができる。経路指定表１０２における各ルーティング・ノードは、リング１５１内部において当該ルーティング・ノードがメッセージを転送し処理する能力を表す適性計量値を有する。
【００５４】
経路指定表１０２にアクセスする前に、経路指定表管理部１０４は経路指定表１０２をロックすることができる。経路指定表１０２をロックすると、経路指定表１０２に対する他のアクセスが妨げられる（例えば、経路決定）。つまり、ロックすることにより、経路指定表１０２を変更しているときに経路指定表１０２をアクセスすることによる経路指定の誤りの潜在的可能性を軽減する。
【００５５】
複数の更に別のノードの各々について、方法３００は、更に別のノードについての適性計量値を計算する行為を含む。適性計量値は、オーバーレイ・ネットワーク内においてメッセージを転送し処理する当該更に別のノードの能力を表す。適性計量値は、少なくとも部分的に、当該更に別のノードについての適性情報に基づく（行為３０３）。例えば、適性計算モジュール１０３はノードＩＤ４６、１４４、２４２、および４６０についてそれぞれ適性計量値４０、２００、２０００、および５００を計算することができる。適性値は、経路指定表のサイズおよび／またはメッセージ１１１において示されるその他の特性に基づいて計算することができる。
【００５６】
複数の更に別のノードの各々について、方法３００は、別のノードをコンピューター・システムの経路指定表に挿入する行為を含む（行為３０４）。例えば、経路指定表管理部１０４は、ノードＩＤ４６、１４４、２４２、および４６０を経路指定表１０２に挿入することができる。
【００５７】
方法３００は、コンピューター・システムの経路指定表の中にあるノードの数が指定数を超過していると判断する行為を含む（行為３０５）。例えば、経路指定表管理部１０４は経路指定表の方針１６１を参照して、経路指定表１０２に対する最大ルーティング・ノード数にアクセスすることができる。経路指定表管理部１０４は、ノードＩＤ４６、１４４、２４２、および４６０の挿入によって、経路指定表１０２の中にあるノードの数が最大ルーティング・ノード数を超過したと判断することができる。
【００５８】
方法３００は、経路指定表を複数の範囲に分割する行為を含み、各範囲はオーバーレイ・ネットワークの一部に対応する（行為３０６）。例えば、経路指定表管理部１０４は、経路指定表１０２を範囲１９１〜１９８に分割することができる。方法３００は、オーバーレイ・ネットワークにおけるノードの位置に基づいて、経路指定表の中にある各ノードを、複数の範囲の１つに割り当てる行為を含む（行為３０７）。例えば、経路指定表１０２の中にあるノードの各々を、それらのリング１５１における位置に基づいて、範囲１９１〜１９８の１つに割り当てることができる。ノードＩＤ４６を範囲１９３に割り当てることができ、ノードＩＤ１４４および２４２を範囲１９５に割り当てることができ、ノードＩＤ４６０を範囲１９７に割り当てることができる。
【００５９】
方法３００は、最も多いノードを含む範囲を特定する行為を含む（行為３０８）。例えば、経路指定表管理部は、範囲１９４が最も多い（６つの）ルーティング・ノードを含むことを特定することができる。方法３００は、適性計量値に基づいて、特定した範囲内において、これらのノードの間で最もメッセージを転送および処理できないノードを除去する行為を含む（行為３０９）。例えば、経路指定表管理部１０２は、ノードＩＤ１３５を経路指定表１０２から除去することができる。経路指定表管理部１０４は、ノードＩＤ１３５を、範囲１９３において最も低い計量値を有するものとして特定することができる。したがって、経路指定表管理部１０４は、ノードＩＤ１３５が、リング１５１内において最もメッセージを転送し処理することができないルーティング・ノードであると判断する。（しかしながら、前述のように、構成によっては、適性計量値が高い程、メッセージを転送し処理する能力が低いことを示すために用いることができ、あるいは適性計量値からメッセージング処理および転送能力を判断する何らかの他のメカニズムを用いることもできる。）
【００６０】
実施形態の中には、経路指定表１０２のノード数が指定数をもはや超過しなくなるまで、行為３０８および３０９を繰り返すことができる場合がある。例えば、１つのノードを除去した後、経路指定表管理部１０４は、経路指定表１０２の中にあるノードの数を、最大ルーティング・ノード数と突き合わせてチェックすることができる。経路指定表１０２の中にあるルーティング・ノードの数が最大ルーティング・ノード数を未だ超過している場合、行為３０８および３０９を繰り返すことができる。
【００６１】
例えば、ノード１３５を除去した後、経路指定表管理部１０４は、範囲１９２が５つのノードを含むと判断することができる。経路指定表管理部１０４は、適性計量値に基づいて、ノードＩＤ３７を、リング１５１内部において最もメッセージを転送し処理することができないルーティング・ノードとして特定することができる。したがって、経路指定表管理部１０４はノードＩＤ３７を経路指定表１０２から除去する。続いて同様のチェックを行うことができ、ノードＩＤ１４４（範囲１９３における）およびノードＩＤ４６３（範囲１９７における）が除去される結果となる。このように、経路指定表１０２は、最終的に、メッセージ１１１が受信される前のサイズに戻される。図１Ｄは、メッセージ１１１を処理した後において得られた経路指定表１０２の内容を示す。
【００６２】
経路指定表１０２の更新に続いて、経路指定表管理部１０４は経路指定表１０２のロックを解除することができる。経路指定表１０２のロックを解除すると、経路指定表１０２への他のアクセスが可能になる。つまり、ノード１０１は、あらゆる変更が完了した後に、経路指定表１０２を用いて、ルーティング・ノードを特定することができる。したがって、メッセージ１１１の処理に続いて、ノード１０１はリング１５１における宛先ノードに向けてメッセージを送ることができる。宛先ノードの位置に基づいて、ノード１０１は、宛先ノードにより近接したルーティング・ノードを（経路指定表１０２から）選択し、メッセージをこのより近接したルーティング・ノードに送ることができる。
【００６３】
本発明の実施形態は、経路指定表に収容されているルーティング・ノードが、オーバーレイ・ネットワークにおいてメッセージを転送し処理するためのしかるべき（または比較的高い）能力を有する可能性を著しく高める。このため、ノードがメッセージのために経路を決定する場合、選択したルーティング・ノードはいずれも適している（または、少なくとも現在利用可能なものでは最良である）ことの何らかの保証が得られる。更に、送出側ノードは、メッセージを送る際に、適性計量値が高い方のルーティング・ノードを優先することができる。高い方の適性計量値を優先することにより、メッセージがしかるべく転送され処理されることが、更に保証される。したがって、本発明の実施形態は、帯域幅を最適化し、効率的な経路指定能力が得られるように、メッセージを導出するために用いることができる。
【００６４】
本発明は、その主旨または本質的な特徴から逸脱せずに、他の具体的な形態においても具体化することができる。記載した実施形態は、あらゆる観点において、限定的ではなく例示的として見なすのみとする。したがって、本発明の範囲は、前述の説明ではなく、添付した特許請求の範囲によって示されるものとする。特許請求の範囲の均等の意味および範囲に該当するあらゆる変更は、特許請求の範囲に包含されるものとする。
【図１Ａ】
2010536259.tif 000003
【図１Ｂ】
2010536259.tif 000004
【図１Ｃ】
2010536259.tif 000005
【図１Ｄ】
2010536259.tif 000006
【図２】
2010536259.tif 000007
【図３】
2010536259.tif 000008
【国際調査報告】
2010536259.tif 000009
2010536259.tif 000010