(57)【特許請求の範囲】
【請求項１】
ピアツーピアオーバーレイネットワークのサイズを決定するための方法において、
プロセッサにおいて、第１のノードが前記オーバーレイネットワークを離れていることを推測することと、
送信機において、サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信することと、
前記プロセッサにおいて、よく知られているストリングをハッシングして、前記サイズカウンタ値を導出することを含む、前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定することとを含む方法。
【請求項２】
前記推測することは、前記第１のノードとの通信が失敗したことを決定することを含む請求項１記載の方法。
【請求項３】
前記推測することは、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信することを含む請求項１記載の方法。
【請求項４】
前記プロセッサにおいて、第２のノードが前記オーバーレイネットワークに加わっていることを決定することと、
前記送信機において、前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信することとをさらに含む請求項１記載の方法。
【請求項５】
前記プロセッサにおいて、第３のノードが前記オーバーレイネットワークを離れていることを決定することと、
前記送信機において、前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信することとをさらに含む請求項１記載の方法。
【請求項６】
ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
第１のノードが前記オーバーレイネットワークを離れていることを推測するように構成されているプロセッサと、
前記プロセッサに結合されており、サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するように構成されている送信機とを具備し、
前記プロセッサは、よく知られているストリングをハッシングして、前記サイズカウンタ値を導出することにより、前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定するように構成されている装置。
【請求項７】
前記プロセッサは、前記第１のノードとの通信が失敗したことを決定することにより、推測するように構成されている請求項６記載の装置。
【請求項８】
前記プロセッサは、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信することにより、推測するように構成されている請求項６記載の装置。
【請求項９】
前記プロセッサは、第２のノードが前記オーバーレイネットワークに加わっていることを決定するように構成され、
前記送信機は、前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信するように構成されている請求項６記載の装置。
【請求項１０】
前記プロセッサは、第３のノードが前記オーバーレイネットワークを離れていることを決定するように構成され、
前記送信機は、前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するように構成されている請求項６記載の装置。
【請求項１１】
ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
第１のノードが前記オーバーレイネットワークを離れていることを推測する手段と、
サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信する手段と、
よく知られているストリングをハッシングして、前記サイズカウンタ値を導出する手段を備える、前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定する手段とを具備する装置。
【請求項１２】
前記推測する手段は、前記第１のノードとの通信が失敗したことを決定する手段を備える請求項１１記載の装置。
【請求項１３】
前記推測する手段は、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信する手段を備える請求項１１記載の装置。
【請求項１４】
第２のノードが前記オーバーレイネットワークに加わっていることを決定する手段と、
前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信する手段とをさらに具備する請求項１１記載の装置。
【請求項１５】
第３のノードが前記オーバーレイネットワークを離れていることを決定する手段と、
前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信する手段とをさらに具備する請求項１１記載の装置。
【請求項１６】
ピアツーピアオーバーレイネットワークのサイズを決定するためのコンピュータ読取可能記憶媒体において、
第１のノードが前記オーバーレイネットワークを離れていることを推測するための、プロセッサにより実行可能なコードと、
サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するための、前記プロセッサにより実行可能なコードと、
よく知られているストリングをハッシングして、前記サイズカウンタ値を導出することにより、前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定するための、前記プロセッサにより実行可能なコードとを含むコンピュータ読取可能記憶媒体。
【請求項１７】
前記コードは、前記プロセッサに、前記第１のノードとの通信が失敗したことを決定させることにより推測させるように構成されている請求項１６記載のコンピュータ読取可能記憶媒体。
【請求項１８】
前記コードは、前記プロセッサに、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信させることにより推測させるように構成されている請求項１６記載のコンピュータ読取可能記憶媒体。
【請求項１９】
前記コードは、
前記プロセッサに、第２のノードが前記オーバーレイネットワークに加わっていることを決定させるように構成され、
前記プロセッサに、前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信させるように構成されている請求項１６記載のコンピュータ読取可能記憶媒体。
【請求項２０】
前記コードは、
前記プロセッサに、第３のノードが前記オーバーレイネットワークを離れていることを決定させるように構成され、
前記プロセッサに、前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信させるように構成されている請求項１６記載のコンピュータ読取可能記憶媒体。
【請求項２１】
ピアツーピアオーバーレイネットワークのサイズを決定するための方法において、
プロセッサにおいて、オーバーレイネットワークの第１のノードに関係するノードのセットを識別することと、
トランシーバにおいて、前記ノードのセットのそれぞれのノードに関係するセグメント長を取得することと、
前記プロセッサにおいて、前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定することとを含む方法。
【請求項２２】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項２１記載の方法。
【請求項２３】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項２１記載の方法。
【請求項２４】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項２１記載の方法。
【請求項２５】
前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記セグメント長の少なくとも一部分を取得することを含む請求項２１記載の方法。
【請求項２６】
前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得することを含む請求項２１記載の方法。
【請求項２７】
前記オーバーレイネットワークのサイズを決定することは、前記第１のノードのサイズ推定を規定し、
トランシーバにおいて、前記第１のノードに関係する前記サイズ推定と、前記ノードのセットのそれぞれのノードに関係する追加のサイズ推定の少なくとも一部分とを取得することと、
プロセッサにおいて、前記追加のサイズ推定の少なくとも一部分および前記サイズ推定を平均することにより、前記オーバーレイネットワークの更新されたサイズを決定することとをさらに含む請求項２１記載の方法。
【請求項２８】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項２７記載の方法。
【請求項２９】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項２７記載の方法。
【請求項３０】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項２７記載の方法。
【請求項３１】
前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記追加のサイズ推定の少なくとも一部分を取得することを含む請求項２７記載の方法。
【請求項３２】
前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記追加のサイズ推定の少なくとも一部分を取得することを含む請求項２７記載の方法。
【請求項３３】
ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別するように構成されているプロセッサと、
前記プロセッサに結合されており、前記ノードのセットのそれぞれのノードに関係するセグメント長を取得するように構成されているトランシーバとを具備し、
前記プロセッサは、前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定するようにさらに構成されている装置。
【請求項３４】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項３３記載の装置。
【請求項３５】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項３３記載の装置。
【請求項３６】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項３３記載の装置。
【請求項３７】
前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記セグメント長の少なくとも一部分を取得するように構成されている請求項３３記載の装置。
【請求項３８】
前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得するように構成されている請求項３３記載の装置。
【請求項３９】
前記オーバーレイネットワークのサイズは、前記第１のノードのサイズ推定を規定し、
前記プロセッサは、前記第１のノードに関係する前記サイズ推定を取得するようにさらに構成され、
前記トランシーバは、前記ノードのセットのそれぞれのノードに関係する追加のサイズ推定の少なくとも一部分を取得するようにさらに構成され、
前記プロセッサは、前記追加のサイズ推定の少なくとも一部分および前記サイズ推定を平均することにより、前記オーバーレイネットワークの更新されたサイズを決定するようにさらに構成されている請求項３３記載の装置。
【請求項４０】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項３９記載の装置。
【請求項４１】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項３９記載の装置。
【請求項４２】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項３９記載の装置。
【請求項４３】
前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記追加のサイズ推定の少なくとも一部分を取得するように構成されている請求項３９記載の装置。
【請求項４４】
前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記追加のサイズ推定の少なくとも一部分を取得するように構成されている請求項３９記載の装置。
【請求項４５】
ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別する手段と、
前記ノードのセットのそれぞれのノードに関係するセグメント長を取得する手段と、
前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定する手段とを具備する装置。
【請求項４６】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項４５記載の装置。
【請求項４７】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項４５記載の装置。
【請求項４８】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項４５記載の装置。
【請求項４９】
前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記セグメント長の少なくとも一部分を取得する手段を備える請求項４５記載の装置。
【請求項５０】
前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得する手段を備える請求項４５記載の装置。
【請求項５１】
前記オーバーレイネットワークのサイズは、前記第１のノードのサイズ推定を規定し、
前記第１のノードに関係する前記サイズ推定と、前記ノードのセットのそれぞれのノードに関係する追加のサイズ推定の少なくとも一部分とを取得する手段と、
前記追加のサイズ推定の少なくとも一部分および前記サイズ推定を平均することにより、前記オーバーレイネットワークの更新されたサイズを決定する手段とをさらに具備する請求項４５記載の装置。
【請求項５２】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項５１記載の装置。
【請求項５３】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項５１記載の装置。
【請求項５４】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項５１記載の装置。
【請求項５５】
前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記追加のサイズ推定の少なくとも一部分を取得する手段を備える請求項５１記載の装置。
【請求項５６】
前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記追加のサイズ推定の少なくとも一部分を取得する手段を備える請求項５１記載の装置。
【請求項５７】
ピアツーピアオーバーレイネットワークのサイズを決定するためのコンピュータ読取可能記憶媒体において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別するための、プロセッサにより実行可能なコードと、
前記ノードのセットのそれぞれのノードに関係するセグメント長を取得するための、前記プロセッサにより実行可能なコードと、
前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定するための、前記プロセッサにより実行可能なコードとを含むコンピュータ読取可能記憶媒体。
【請求項５８】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項５７記載のコンピュータ読取可能記憶媒体。
【請求項５９】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項５７記載のコンピュータ読取可能記憶媒体。
【請求項６０】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項５７記載のコンピュータ読取可能記憶媒体。
【請求項６１】
前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせさせて、前記セグメント長の少なくとも一部分を取得させるように構成されている請求項５７記載のコンピュータ読取可能記憶媒体。
【請求項６２】
前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得させるように構成されている請求項５７記載のコンピュータ読取可能記憶媒体。
【請求項６３】
前記オーバーレイネットワークのサイズを決定することは、前記第１のノードのサイズ推定を規定し、
前記第１のノードに関係する前記サイズ推定を取得するための、前記プロセッサにより実行可能なコードと、
前記ノードのセットのそれぞれのノードに関係する追加のサイズ推定の少なくとも一部分を取得するための、前記プロセッサにより実行可能なコードと、
前記追加のサイズ推定の少なくとも一部分および前記サイズ推定を平均することにより、前記オーバーレイネットワークの更新されたサイズを決定するための、前記プロセッサにより実行可能なコードとを含む請求項５７記載のコンピュータ読取可能記憶媒体。
【請求項６４】
前記ノードのセットは、前記第１のノードに関係するフィンガーを含む請求項６３記載のコンピュータ読取可能記憶媒体。
【請求項６５】
前記ノードのセットは、前記第１のノードに関係する隣接ノードを含む請求項６３記載のコンピュータ読取可能記憶媒体。
【請求項６６】
前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む請求項６３記載のコンピュータ読取可能記憶媒体。
【請求項６７】
前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせさせて、前記追加のサイズ推定の少なくとも一部分を取得させるように構成されている請求項６３記載のコンピュータ読取可能記憶媒体。
【請求項６８】
前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記追加のサイズ推定の少なくとも一部分を取得させるように構成されている請求項６３記載のコンピュータ読取可能記憶媒体。
【発明の詳細な説明】
【米国特許法第１１９条の下での優先権主張】
【０００１】
本特許出願は、双方が、本発明の譲受人に譲渡され、ここでの参照によりここに明確に組み込まれている、“ピアツーピアオーバーレイネットワークのサイズ推定のための方法および装置”と題し、２００９年２月２６日に出願された仮出願第６１／１５５，８６８号、および、“オーバーレイルーティング安定化およびサイズ推定に対する、適応自己同調可能アプローチのための方法および装置”と題し、２００９年６月９日に出願された仮出願第６１／１８５，５３５号に対して優先権を主張する。
【分野】
【０００２】
本出願は、一般的に、オーバーレイネットワークの動作に関連し、さらに詳細には、ピアツーピアオーバーレイネットワーク中の拡張オーバーレイ状態維持のための方法および装置に関連している。
【背景】
【０００３】
サーバベースのインフラストラクチャなしで、メンバーノードがサービスを取得するネットワークは、“ピアツーピア”オーバーレイネットワークとして呼ばれる。ピアツーピアオーバーレイでは、ピアノードは、互いに協働して、サービスを提供し、ネットワークを維持する。ピアツーピアオーバーレイネットワークは、インターネットプロトコル（ＩＰ）を利用するネットワークのような基礎となるネットワークのトップ上に築くことができる。
【０００４】
ピアツーピアオーバーレイネットワークでは、それぞれのノードは、オーバーレイ中に参加している１個以上のピアの知識を有する。オーバーレイネットワーク上で発信元ノードから宛先ノードにデータをルーティングするための、シンプルだが非効率的なアプローチは、宛先ノードに到達するまで、次のホップへ、または、後継ノード（すなわち、識別スペース中の発信元ノードの論理的に隣のノード）へデータを継続的にパスすることである。しかしながら、このアプローチは、オーバーレイネットワークのサイズ、および、ホップの数が増加するにつれて、過大な待ち時間を招く。それゆえ、ルーティング最適化のために、それぞれのノードは、それ自身から、１個のノード、２個のノード、４個のノード、または、２(m-1)個までのノード分離れているフィンガーのリストを維持する。ここで、ｍは、それぞれのノード識別子に割り当てられたビットの数である。これは、ノードＯ（ｎ）からノードＯ（ｌｏｇ（ｎ））にデータをルーティングするために必要とされるホップの数を最小化するのを助ける。ここで、ｎは、平均的なケースに対するノードの数である。
【０００５】
しかしながら、ノードは、いつでも来たり行ったりし、結果として、オーバーレイネットワークコンフィギュレーションが変化し、この変化は、特定のノードに知られているフィンガーに影響するかもしれない。この可変性を補うために、それぞれのノードは、そのノードが知るフィンガーを再計算するフィンガー安定化アルゴリズムを再ランする。フィンガー安定化アルゴリズムの結果は、フィンガーテーブルに記憶させる。残念ながら、それぞれのノードは、それ自身のフィンガーテーブルを維持していることから、それぞれのノードがそのフィンガー安定化アルゴリズムをランさせる必要がある頻度を決定することは問題になるかもしれない。例えば、ノードがそのフィンガー安定化アルゴリズムを十分頻繁にランしない場合、そのフィンガーテーブルは古くなり、結果として、非効率的で遅れたパケットルーティングが生じるかもしれない。ノードがそのフィンガー安定化アルゴリズムを頻繁にランしすぎる場合、これは、結果として、オーバーレイ帯域幅を無駄にすること、および／または、オーバーレイネットワーク上の他のノード上に負担をかけることになるかもしれない。例えば、安定化アルゴリズムをランするには、電力を必要とし、安定化アルゴリズムの過大な実行は、バッテリーで動作するノードにおける電力を無駄にするかもしれない。
【０００６】
さらに、構造化ピアツーピアオーバーレイネットワークは、本質的に広く分散されていることから、参加するノードは、完全なルーティングテーブルを有しておらず、したがって、それらが動作しているオーバーレイネットワークのサイズを知らない。しかしながら、オーバーレイネットワークのサイズの知識は、オーバーレイをマージするとき、負荷バランシングを実施するとき、または、ストラテジーをキャッシングするときとともに、ルーティングプロトコル特殊化のような、いくつかの目的に対して有用であることがある。
【０００７】
残念ながら、従来のシステムは、正確なオーバーレイネットワークサイズを提供することに失敗することがある。例えば、ノードは、それらの隣接するものに進んで知らせることなく、オーバーレイを離れるかもしれず、結果として、オーバーレイネットワークサイズは、正確に維持されないかもしれない。
【０００８】
それゆえ、ノードが、フィンガー安定化アルゴリズムを適応的にスケジューリングし、オーバーレイネットワークのサイズを決定できるようにして、上述した問題を克服するように動作する、シンプルでコスト効率のよいメカニズムを有することが望ましいだろう。
【概要】
【０００９】
１つ以上の態様では、ノードが、フィンガー安定化アルゴリズムの実行間の時間間隔を決定できるようにし、それによって、アルゴリズムの実行を適応的にスケジューリングするように適応的に動作する、方法および装置を備える適応スケジューリング（ＡＳ）システムを提供する。システムはまた、ノードが、その上にこれらが参加するオーバーレイネットワークのサイズを決定でき、それによって、マージング、負荷バランシング、およびキャッシングのようなネットワーク機能を促進するように動作する。
【００１０】
ある態様では、ピアツーピアオーバーレイネットワークのサイズを決定するための方法を提供する。方法は、第１のノードがオーバーレイネットワークを離れていることを推測することと、サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信することとを含む。
【００１１】
ある態様では、ピアツーピアオーバーレイネットワークのサイズを決定するための装置を提供する。装置は、第１のノードがオーバーレイネットワークを離れていることを推測するように構成されているプロセッサと、プロセッサに結合されており、サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するように構成されている送信機とを具備する。
【００１２】
ある態様では、ピアツーピアオーバーレイネットワークのサイズを決定するための方法を提供する。方法は、オーバーレイネットワークの第１のノードに関係するノードのセットを識別することと、ノードのセットのそれぞれのノードに関係するセグメント長を取得することと、ノードのセット中のノードの総数を、セグメント長の合計で割ることにより、オーバーレイネットワークのサイズを決定することとを含む。
【００１３】
ある態様では、ピアツーピアオーバーレイネットワークのサイズを決定するための装置を提供する。装置は、オーバーレイネットワークの第１のノードに関係するノードのセットを識別するように構成されているプロセッサと、プロセッサに結合されており、ノードのセットのそれぞれのノードに関係するセグメント長を取得するように構成されているトランシーバとを具備し、プロセッサは、ノードのセット中のノードの総数を、セグメント長の合計で割ることにより、オーバーレイネットワークのサイズを決定するように構成されている。
【００１４】
ある態様では、ピアツーピアオーバーレイネットワークのサイズを決定するための方法を提供する。方法は、オーバーレイネットワークの第１のノードに関係するノードのセットを識別することと、第１のノードに関係するサイズ推定と、ノードのセットのそれぞれのノードに関係するサイズ推定とを取得することと、サイズ推定を平均することにより、オーバーレイネットワークのサイズを決定することとを含む。
【００１５】
ある態様は、ピアツーピアオーバーレイネットワークのサイズを決定するための装置を提供する。装置は、オーバーレイネットワークの第１のノードに関係するノードのセットを識別し、第１のノードに関係するサイズ推定を取得するように構成されているプロセッサと、プロセッサに結合されており、ノードのセットのそれぞれのノードに関係するサイズ推定を取得するように構成されているトランシーバとを具備し、プロセッサは、サイズ推定を平均することにより、オーバーレイネットワークのサイズを決定するように構成されている。
【００１６】
これから述べる図面の簡単な説明、説明、および特許請求の範囲を参照した後、他の態様が明らかになるだろう。
【図面の簡単な説明】
【００１７】
ここに記述した前述の態様は、付随する図面を参照する際の下記の記述への参照により、さらに容易に明らかになるだろう。
【図１】図１は、ＡＳシステムの動作を図示するネットワークを示している。
【図２】図２は、ＡＳシステムにしたがって構築された例示的なＡＳ装置を示している。
【図３】図３は、ＡＳシステムにしたがって、フィンガー安定化アルゴリズムを適応的にスケジューリングするための例示的な方法を示している。
【図４】図４は、ＡＳシステムにしたがって構築された例示的なＡＳ装置を示している。
【図５】図５は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定するための第１の方法を示している。
【図６】図６は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定するための第２の方法を示している。
【図７】図７は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定するための第１の改善方法を示している。
【図８】図８は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定するための第２の改善方法を示している。
【図９】図９は、ＡＳシステムにしたがって構築された例示的なＡＳ装置を示している。
【図１０】図１０は、ＡＳシステムにしたがって構築された例示的なＡＳ装置を示している。
【図１１】図１１は、ＡＳシステムにしたがって構築された例示的なＡＳ装置を示している。
【説明】
【００１８】
下記の説明は、フィンガー安定化アルゴリズムの実行を適応的にスケジューリングし、オーバーレイネットワークのサイズを決定する、ＡＳシステムの態様およびインプリメンテーションを記述している。
【００１９】
図１は、ＡＳシステムの動作を図示するネットワーク１００を示している。ネットワーク１００は、インターネットプロトコルネットワークのような何らかのタイプのネットワークを含む基礎となるネットワーク１０２を備える。基礎となるネットワーク１０２を、単一のエンティティとして示しているが、基礎となるネットワークは、ＷＡＮ、ＬＡＮ、ワイヤレスネットワーク、および／または他の何らかのタイプのネットワークのような、任意の数のネットワークまたは任意のタイプのネットワークを含んでいてもよい。
【００２０】
ピアツーピアオーバーレイネットワーク１０４は、基礎となるネットワーク１０２のノードのサブセットを備え、基礎となるネットワーク１０２のサービスを利用して、それらのノードが通信できるようにするように動作する。ピアツーピアオーバーレイネットワーク１０４では、ノードは、通信リンク１０６により接続され、円形ルーティングパスを形成する。通信リンク１０６は、基礎となるネットワーク１０２により提供される安全なトンネルであってもよい。ピアツーピアオーバーレイネットワーク１０４は、基礎となるネットワーク１０２のものとは異なる、許可および対話のセットとともに動作する。ピアツーピアオーバーレイネットワーク１０４は、何らかのルーティングパターンを可能にする何らかのトポロジーまたはアーキテクチャを有するかもしれず、この何らかのルーティングパターンは、図１中に示されているルーティングに限定されないことにも留意すべきである。
【００２１】
ピアツーピアオーバーレイネットワーク１０４中のノードのそれぞれは、ノード識別子を確立する。説明の簡略化および簡潔のために、ピアツーピアオーバーレイネットワーク１０４のノードのノード識別子は、（１、４、７、１０、１３、１６、１９、および２２）である。実際には、オーバーレイネットワークは、非常に大多数のノードを備え、より多くのノード識別子を利用することに留意すべきである。動作中に、トラフィックは、ピアツーピアオーバーレイネットワーク１０４の回りをいずれの方向にも流れることができる。
【００２２】
トラフィックルーティングを促進するために、ネットワーク１０４のそれぞれのノードは、オーバーレイネットワーク１０４全体に及ぶルーティングフィンガーを識別するフィンガーテーブルを計算して維持する。例えば、それぞれのノードは、フィンガー安定化アルゴリズムをランして、オーバーレイネットワークの現在のコンフィギュレーションに基づいてルーティングフィンガーを識別する。したがって、ノードがオーバーレイに加わるおよび離れるとき、フィンガー安定化アルゴリズムは、それぞれのノードに関係するルーティングフィンガーを識別するだろう。例えば、ノード４においてランしているフィンガー安定化アルゴリズムは、ノード１３に対するフィンガー１０８と、ノード１９に対するフィンガー１１０とを識別している。フィンガーの使用は、オーバーレイネットワーク１０４にわたって、より効率的なパケットルーティングを提供する。例えば、ノード１６にルーティングされることになっている、ノード４におけるパケットは、第１のホップ中で、フィンガー１０８をわたってルーティングすることができ、その後、ルーティングパス１１４により図示されているように、第２のホップ中で、ノード１６にルーティングすることができる。
【００２３】
オーバーレイネットワーク１０４のノードのそれぞれにおいて、ＡＳ装置を提供する。簡略化のために、オーバーレイネットワーク１０４のノード４においてＡＳ装置１１２を示している。しかしながら、類似したＡＳ装置が、オーバーレイネットワーク１０４のそれぞれのノードに位置していてもよい。ＡＳ装置１１２は、ノード４において実施するフィンガー安定化アルゴリズムの実行を適応的にスケジューリングするように動作する。ＡＳ装置１１２は、何らかのタイプのフィンガー安定化アルゴリズムとの使用に適しており、その動作の簡単な説明を下記に提供する。
【００２４】
ＡＳ装置１１２は、フィンガー安定化アルゴリズムの実行間の初期の時間間隔またはベースの時間間隔（すなわちｔ秒）で開始する。安定化アルゴリズムをランするとき、ノード４は、Ｎ個のフィンガーを発見する。ＡＳ装置１１２は、ｔ秒間、時間間隔を測定して、フィンガー安定化アルゴリズムを再度実行するようにノード４をトリガする。２個のフィンガー結果の間の差分（すなわち、決定されたフィンガーの、数および／またはタイプ）が、第１の基準を満たす場合には、ＡＳ装置１１２は、フィンガー安定化アルゴリズムの実行間の時間間隔を増加させるように動作する。例えば、１つのインプリメンテーションでは、時間間隔を、２倍だけ増加させる。しかしながら、差分が第２の基準を満たす場合には、ＡＳ装置１１２は、フィンガー安定化アルゴリズムの実行間の時間間隔を減少させるように動作する。例えば、１つのインプリメンテーションでは、時間間隔を、１／２に減少させる。第１および第２の基準は、任意の適切な性能目標を満たすように規定することができる。例えば、２個のフィンガー結果の間に差分がない場合に、第１の基準を満たしてもよい。２個のフィンガー結果の間に何らかの差分が見つかる場合に、第２の基準を満たしてもよい。したがって、特定のノードのフィンガーテーブル中の変化に関する条件の何らかのセットをテストするために、第１および第２の基準を規定することも可能である。
【００２５】
それゆえ、この適応自己同調可能アプローチを通して、ＡＳ装置１１２は、それぞれのノードが、フィンガー安定化アルゴリズムの実行間の安定状態間隔に、独立的、かつ、適応的に、達することができるようにする。さらに、システムは、それぞれのノードが、オーバーレイのサイズを独立的に近似できるようにする。例えば、特定のノードが、時間ｔにおいて、オーバーレイネットワーク中にＮ個のフィンガーを識別した場合には、その時間において、オーバーレイネットワーク中に多くて２N個のノードがある。したがって、特定のノードが、３個の一意的なフィンガーを識別した場合に、ノードは、オーバーレイネットワークのサイズを８（２3）個のノードに近似する。しかしながら、この近似は、時間とともに変化することになり、オーバーレイネットワークの近似サイズ範囲をノードに提供するように機能する。
【００２６】
ＡＳシステムは、フィンガー安定化アルゴリズムをスケジューリングするために、ノード間の関連、または、システムのグローバルな知識を必要とせず、このことは、ピアツーピア分散アプリケーションに対して有益である。ＡＳ装置１１２の動作のさらに詳細な説明を下記に提供する。
【００２７】
図２は、ＡＳシステムにしたがって構築された例示的なＡＳ装置２００を示している。例えば、ＡＳ装置２００は、図１中に示したＡＳ装置１１２としての使用に適している。ＡＳ装置２００は、データバス２１０を使用して通信するようにすべて結合されている、プロセッサ２０２と、メモリ２０４と、タイマー２０６と、トランシーバ２０８とを備えている。ＡＳ装置２００は、１つのインプリメンテーションに過ぎないことと、他のインプリメンテーションも可能性があることに留意すべきである。
【００２８】
ピアツーピアオーバーレイネットワーク上で、ＡＳ装置２００が、データまたは他の情報を複数のノードと通信できるようにするように動作する、ハードウェア、および／または、ハードウェア実行ソフトウェアを、トランシーバ２０８は備えている。トランシーバ２０８は、フィンガー安定化アルゴリズムまたはネットワークサイズ推定を実施する目的として、ピアツーピアオーバーレイネットワークのノードとの１つ以上の通信リンク２１２を確立するように動作可能である。例えば、通信リンク２１２は、基礎となるＩＰネットワークのサービスを利用して形成される安全なトンネルであってもよい。
【００２９】
メモリ２０４は、ＡＳシステムの動作中に情報の記憶および取出ができるようにするように動作可能な何らかの適切な記憶デバイスを含んでいる。メモリ２０４は、オーバーレイネットワークパラメータ１１４を記憶するように動作する。オーバーレイネットワークパラメータ１１４は、ノード識別子、基礎となるネットワーク識別子、サービス識別子、および他の何らかのパラメータを含む、オーバーレイネットワークについての情報、あるいは、オーバーレイの動作または使用に関連する情報を含む。オーバーレイネットワークパラメータ１１４はまた、ＡＳシステムの動作の間に使用する、第１および第２のセットの基準を含む。例えば、基準のセットを、プロセッサ２０２によりメモリ２０４中に記憶させる。プロセッサ２０２はまた、基準のセットの更新、変更、または、他の修正をするように動作可能である。フィンガー安定化アルゴリズム２１８の実行間の時間間隔をいつ増加または減少させるかを決定するために、ＡＳシステムの動作中に基準のセットを使用する。
【００３０】
メモリ２０４はまた、ピアツーピアオーバーレイネットワークの１つ以上のノードに関係するフィンガー情報を含むフィンガーデータベース２１６を記憶するように動作可能である。フィンガーデータベース２１６は、ノードに対して利用可能なフィンガーの数およびタイプについての情報を記憶させるために使用する。例えば、フィンガーデータベース２１６は、フィンガーの数と、フィンガーのタイプと、フィンガーエンドノードのような情報、および、オーバーレイネットワークのフィンガーに関連する他の何らかの情報を含む。フィンガーデータベース２１６中の情報を、プロセッサ２０２によるフィンガー安定化アルゴリズム２１８の実行から決定する。
【００３１】
タイマー２０６は、プロセッサ２０２から受信した時間パラメータに基づいて、時間間隔を測定するように動作する、ハードウェア、および／または、ハードウェア実行ソフトウェアを含む。例えば、時間パラメータは、カウンタを初期化するために使用するカウントダウン値を含む。カウントダウン値は、タイマー２０６により測定されることになる特定の時間間隔に対応する。したがって、プロセッサ２０２は、タイマー２０６を設定して、任意の望ましい時間間隔を測定してもよい。時間間隔を測定したとき、タイマー２０６は、プロセッサ２０２に対してタイマー満了を示す。例えば、タイマー２０６は特定の時間間隔を測定し、その終わりにおいて、プロセッサ２０２は、その終わりを知らされて、その後フィンガー安定化アルゴリズム２１８を実行するように動作する。フィンガー安定化アルゴリズム２１８は、特定のノードに関係するフィンガーについての情報を決定するように動作する。
【００３２】
プロセッサ２０２は、少なくとも１つの、ＣＰＵ、プロセッサ、ゲートアレイ、ハードウェア論理、メモリエレメント、および／またはハードウェア実行ソフトウェアを含む。プロセッサ２０２は、オーバーレイネットワーク中の特定のノードに対して利用可能なフィンガーを決定するように動作する。例えば、プロセッサ２０２は、フィンガー安定化アルゴリズム２１８を実行し、決定したフィンガーについての情報をフィンガーデータベース２１６中に記憶させる。プロセッサ２０２はまた、フィンガー安定化アルゴリズムにより決定したフィンガー決定を比較して、フィンガー安定化アルゴリズムを実施する前に、時間間隔を増加させるか、または、減少させるかを決定するように動作する。プロセッサ２０２は、タイマー２０６を制御して、この時間間隔を測定する。プロセッサ２０２はまた、オーバーレイサイズ推定のための１つ以上の方法を実施するように動作する。
【００３３】
適応時間間隔決定
ＡＳシステムの動作中に、タイマー２０６は時間間隔を測定するように動作し、その後、プロセッサ２０２はフィンガー安定化アルゴリズム２１８を実行する。例えば、タイマー２０６は、時間間隔が終了したまたは満期になったことを、プロセッサ２０２にシグナリングする。プロセッサ２０２は、オーバーレイネットワークパラメータ２１４を利用して、フィンガー安定化アルゴリズム２１８を実行するために使用する情報を決定するように動作する。結果として生じるフィンガー決定を、フィンガーデータベース２１６中に記憶させる。
【００３４】
プロセッサ２０２は、その後、フィンガー安定化アルゴリズムの次の実行の前に、測定することになる時間間隔を決定する。プロセッサ２０２は、フィンガー安定化アルゴリズムの２個のフィンガー結果を比較することにより、次の時間間隔を決定する。例えば、プロセッサ２０２は、２個の最も最近のフィンガー決定を比較してもよいし、平均されたフィンガー結果を比較してもよいし、比較する何らかの特定のフィンガー結果を選択してもよい。２個のフィンガー結果の間の差分が、第１のセットの基準（すなわち、同じ数、タイプ、エンドノード等）を満たす場合には、プロセッサ２０２は、時間パラメータを増加させ、これに対応して、時間間隔（ＴＩ）を増加させる。例えば、１つのインプリメンテーションでは、時間間隔を、下記のように、選択された最大ＴＩmaxまで増加させ、このことは、アルゴリズムが、１／ＴＩmaxの最低頻度において実施されることを保証する。  
ＴＩnew＝ＴＩold＊２
【００３５】
２個のフィンガー結果の間の差分が第２のセットの基準を満たす場合には、プロセッサ２０２は、時間パラメータを減少させ、これに対応して、時間間隔（ＴＩ）を減少させる。例えば、１つのインプリメンテーションでは、時間間隔を、下記のように、選択された最低ＴＩminまでダウンして減少させ、このことは、アルゴリズムが、１／ＴＩminの最高頻度において実施されることを保証する。  
ＴＩnew＝ＴＩold／２
【００３６】
いったん新しい時間パラメータを決定すると、プロセッサ２０２は、時間パラメータをタイマー２０６に提供し、新しい時間間隔を測定できるようにする。時間間隔の終わりにおいて、プロセッサ２０２は、フィンガー安定化アルゴリズムを再び実行する。上記で提供した、時間間隔を増加させるおよび減少させるための技術は、１つのインプリメンテーションに過ぎないことと、他の技術を使用してもよいこととに留意すべきである。例えば、時間間隔は、上述したものよりも速い、もしくは、上述したものよりも遅いレートに、増加させてもよく、および／または、減少させてもよい。実質的には、時間間隔を増加および／または減少させるための何からの技術を使用してもよい。
【００３７】
プロセッサ２０２は、第１および第２のセットの基準を規定する何らかのセットのパラメータを発生させて、ＡＳシステムの選択された性能を得てもよいことにも留意すべきである。例えば、２個のフィンガー決定の間に差分がない場合に、または、２個のフィンガー決定の間に小さい差分がある場合のみに、これらの基準を満たすように、第１のセットの基準を規定してもよい。さらに、２個のフィンガー決定の間に何らかの差分がある場合に、または、２個のフィンガー決定の間に非常に多くの差分がある場合のみに、これらの基準を満たすように、第２のセットの基準を規定してもよい。したがって、何らかのフィンガーダイナミック（すなわち、変化がない、小さい変化、大きい変化、特定の変化等）を実質的に検出し、検出したフィンガーダイナミックに基づいて、フィンガー安定化アルゴリズムの実行間の時間間隔を調節するために、基準のセットは、プロセッサ２０２によって設定することができる。
【００３８】
１つのインプリメンテーションでは、ＡＳシステムは、１つ以上のプログラム命令（“命令”）、あるいは、コンピュータ読取可能媒体上に記憶されている、または、コンピュータ読取可能媒体上に具現化されている“コード”のセットを有する、コンピュータプログラムプロダクトを含む。少なくとも１つのプロセッサ、例えば、プロセッサ２０２によりコードが実行されるとき、これらの実行は、ＡＳ装置２００に、ここで記述するＡＳシステムの機能を提供させる。例えば、コンピュータ読取可能媒体は、フロッピー（登録商標）ディスク、ＣＤＲＯＭ、メモリカード、ＦＬＡＳＨメモリデバイス、ＲＡＭ、ＲＯＭ、あるいは、ＡＳ装置２００にインターフェースする他の何らかのタイプのメモリデバイスまたはコンピュータ読取可能媒体を含む。別の態様では、外部デバイスまたは通信ネットワークリソースから、ＡＳ装置２００中にコードのセットをダウンロードしてもよい。コードのセットは、実行されるとき、ここで記述するような、ＡＳシステムの態様を提供するように動作する。
【００３９】
図３は、ＡＳシステムにしたがって、フィンガー安定化アルゴリズムを適応的にスケジューリングするための例示的な方法３００を示している。明確にするために、図２中に示したＡＳ装置２００を参照して、方法３００を下記に記述する。１つのインプリメンテーションでは、プロセッサ２０２は、ＡＳ装置２００を制御するための１つ以上のセットのコードを実行して、下記に記述している機能を実施する。
【００４０】
ブロック３０２において、オーバーレイネットワークパラメータのデータベースを維持する。１つのインプリメンテーションでは、プロセッサ２０２は、パラメータデータベース２１４をメモリ２０４中に維持する。例えば、パラメータデータベース２１４は、これらには限定されないが、ＩＰアドレス、ノード識別子、および／または、ピアツーピアオーバーレイネットワーク上で動作する１つ以上のノードに関連する他の何らかパラメータを含む。
【００４１】
ブロック３０４において、フィンガー安定化アルゴリズムを実施する。１つのインプリメンテーションでは、プロセッサ２０２は、安定化アルゴリズム２１８を実行し、トランシーバ２０８および通信リンク２１２を使用してオーバーレイネットワークの他のノードと通信して、オーバーレイネットワークのフィンガーを決定する。プロセッサ２０２は、オーバーレイネットワークに関係するフィンガーを決定するための何らかの適切な安定化アルゴリズムを実施する。
【００４２】
ブロック３０６において、フィンガー安定化アルゴリズムの結果を、メモリ中に記憶させる。例えば、プロセッサ２０２は、フィンガー安定化アルゴリズムの結果を、フィンガーデータベース２１６の一部として、メモリ２０４中に記憶させる。
【００４３】
ブロック３０８において、時間間隔を初期化する。例えば、プロセッサ２０２は、タイマー２０６が初期時間間隔を測定できるように、初期時間パラメータをタイマー２０６中に入力する。
【００４４】
ブロック３１０において、方法は、現在の時間間隔が測定されるのを待つ。例えば、タイマー２０６は、現在の時間間隔を測定して、時間間隔が満期になったとき、プロセッサ２０２に表示を提供する。
【００４５】
ブロック３１２において、フィンガー安定化アルゴリズムを実施する。１つのインプリメンテーションでは、タイマー２０６満期に応答して、プロセッサ２０２は、安定化アルゴリズム２１８を実行し、トランシーバ２０８および通信リンク２１２を使用してオーバーレイネットワークの他のノードと通信して、オーバーレイネットワークのフィンガーを決定する。プロセッサ２０２は、オーバーレイネットワークに関係するフィンガーを決定するための何らかの適切な安定化アルゴリズムを実施する。
【００４６】
ブロック３１４において、フィンガー安定化アルゴリズムの結果を、メモリ中に記憶させる。例えば、プロセッサ２０２は、フィンガー安定化アルゴリズムの結果を、フィンガーデータベース２１６の一部として、メモリ２０４中に記憶させる。
【００４７】
ブロック３１６において、２つのフィンガー決定の間の差分が第１のセットの基準を満たすか否かに関して、決定を行う。例えば、プロセッサ２０２は、フィンガーデータベース２１６から、現在のフィンガー結果および以前のフィンガー結果を取り出して、それらを比較し、それらの間の差分が第１のセットの基準を満たすか否かを決定する。例えば、第１および第２のフィンガー決定の間に差分がない場合に、または、第１および第２のフィンガー決定の間に小さい差分がある場合のみに、第１のセットの基準を満たしてもよい。第１のセットの基準を満たす場合、方法はブロック３１８に進む。第１のセットの基準を満たさない場合、方法はブロック３２０に進む。
【００４８】
ブロック３１８において、現在の時間間隔を増加させる。例えば、プロセッサ２０２は、２倍だけ時間間隔を増加させ、タイマー２０６が、更新された時間間隔を測定できるように、新たな時間パラメータをタイマー２０６中に入力する。その後、方法は、ブロック３１０に進み、タイマー２０６の満期を待つ。プロセッサ２０２は、何らかの適切な技術またはアルゴリズムを利用して、時間間隔を増加させることができることに留意すべきである。
【００４９】
ブロック３２０において、２個のフィンガー決定の間の差分が第２のセットの基準を満たすか否かに関して、決定を行う。例えば、プロセッサ２０２は、フィンガーデータベース２１６から、現在のフィンガー結果および以前のフィンガー結果を取り出して、それらを比較し、それらの間の差分が第２のセットの基準を満たすか否かを決定する。例えば、第１および第２のフィンガー決定の間に差分がある場合に、または、第１および第２のフィンガー決定の間に大きい差分がある場合のみに、第２のセットの基準を満たしてもよい。第２のセットの基準を満たす場合、方法はブロック３２２に進む。第２のセットの基準を満たさない場合、方法はブロック３１０に進み、時間間隔を変更しない。
【００５０】
ブロック３２２において、時間間隔を減少させる。例えば、プロセッサ２０２は、１／２に時間間隔を減少させ、タイマー２０６が、更新された時間間隔を測定できるように、新たな時間パラメータをタイマー２０６中に入力する。その後、方法は、ブロック３１０に進み、タイマー２０６の満期を待つ。プロセッサ２０２は、何らかの適切な技術またはアルゴリズムを利用して、現在の時間間隔を減少させることができることに留意すべきである。１つのインプリメンテーションでは、時間間隔は、時間間隔を増加させるレートよりも速いレートにおいて、減少させる。
【００５１】
それゆえ、方法３００は、オーバーレイネットワークに関係するフィンガーがいつ変化したかを決定し、ＡＳシステムにしたがって、フィンガー安定化アルゴリズムの実行間の時間間隔を適応的に調節するために、ノードにおいて動作可能である。方法３００は１つのインプリメンテーションに過ぎないことと、方法３００の動作は、再構成することができ、または、そうでなければ、さまざまなインプリメンテーションの範囲内で修正できることとに留意すべきである。したがって、他のインプリメンテーションは可能性がある。
【００５２】
図４は、ＡＳシステムにしたがって構築された例示的なＡＳ装置４００を示している。例えば、ＡＳ装置４００は、図２中で示したＡＳ装置２００としての使用に適している。ある態様では、ここで記述したようなＡＳシステムの態様を提供するように構成されている１つ以上のモジュールを備える少なくとも１つの集積回路により、ＡＳ装置４００は実現される。例えば、１つのインプリメンテーションでは、それぞれのモジュールは、ハードウェア、および／または、ハードウェア実行ソフトウェアを備える。
【００５３】
ＡＳ装置４００は、ノードに関係する第１および第２のフィンガーを比較する手段（４０２）を含む第１のモジュールを備える。この第１のモジュールは、ある態様ではプロセッサ２０２を含む。ＡＳ装置４００はまた、第１および第２のフィンガー決定の間の差分が第１の基準を満たす場合に、フィンガー安定化アルゴリズムの実行間の時間間隔を増加させる手段（４０４）を含む第２のモジュールを備える。この第２のモジュールは、ある態様ではタイマー２０６を含む。ＡＳ装置４００はまた、第１および第２のフィンガー決定の間の差分が第２の基準を満たす場合に、フィンガー安定化アルゴリズムの実行間の時間間隔を減少させる手段（４０６）を含む第３のモジュールを備える。この第３のモジュールは、ある態様ではタイマー２０６を含む。
【００５４】
オーバーレイサイズ決定
ＡＳシステムはまた、オーバーレイネットワークサイズ推定を決定するように動作する。１つのインプリメンテーションでは、ＡＳ装置２００は、ピアツーピアオーバーレイネットワークのサイズ推定のための２つの方法を実施するように動作する。第１の方法では、中心カウンタを利用し、ノードダイナミックの推論と中心カウンタを組み合わせて、オーバーレイネットワークのサイズを推定する。第２の方法では、ピア間のピギーバック通信とともに、１つ以上のヒューリスティックを使用して、オーバーレイネットワークのサイズを推定する分散推定プロセスを実施する。
【００５５】
サイズ決定―方法１
図５は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定するための第１の方法５００を示している。サイズ決定の第１の方法５００は、関係するデータキーを任意のデータアイテムが有する、オーバーレイネットワークの分散ハッシュテーブルのインプリメンテーションに基づいている。数値キーに対して衝突耐性のあるハッシュ関数を使用して、データキーストリングをハッシングすることより、データキーを取得する。ノードはまた、同じキースペース中のノード識別子を受信する。それのノードキーが、数値距離でデータアイテムのキー（数値キー）に最も近いノードにおいて、データアイテムを記憶する。
【００５６】
明確にするために、図２中に示したＡＳ装置２００を参照して、方法５００を下記に記述する。１つのインプリメンテーションでは、プロセッサ２０２は、ＡＳ装置２００を制御するための１つ以上のセットのコードを実行して、下記に記述する機能を実施する。
【００５７】
ブロック５０２において、オーバーレイサイズカウンタが維持され、オーバーレイネットワークの現在のサイズを示す。オーバーレイサイズカウンタは、オーバーレイネットワーク中に参加している任意のノードによりアクセスできる。オーバーレイサイズカウンタの説明、および、オーバーレイサイズカウンタをどのように維持し、更新するのかを下記に提供する。
【００５８】
ブロック５０４において、加わるノードが検出されるか否かに関して、決定を行う。１つのインプリメンテーションでは、オーバーレイネットワークに加わる何らかのノードは、最も近い隣接しているものに追加される。この最も近い隣接しているものは、数値キースペース中の後継点である。すなわち、この最も近い隣接しているものは、そのノードキーが、時計回り方向において、加わるノードのキーに最も近い。例えば、図１中に示したＡＳ装置１１２を備えるノード４は、時計回り方向において、加わるノードに最も近いと仮定する。したがって、ノード４は、加わるノードに対する“ジョインアナウンサー”として指定される。
【００５９】
ジョインアナウンサーは、ノードの到着をアナウンスすることと、オーバーレイサイズカウンタをインクリメントさせることを担当している。異なる加わるノードに対して、ジョインアナウンサーが異なっていてもよいことに留意すべきである。１つのインプリメンテーションでは、オーバーレイネットワークに加わりたいことを示している加わるノードからの通信を受信することにより、加わるノードが検出されるか否かに関して、プロセッサ２０２は決定を行う。加わるノードが検出された場合、方法はブロック５０６に進む。加わるノードが検出されなかった場合、方法はブロック５０８に進む。
【００６０】
ブロック５０６において、オーバーレイサイズカウンタをインクリメントさせるために、メッセージを送る。オーバーレイサイズカウンタは、分散ハッシュテーブル中に維持されている。以前に同意された一意的なカウンタ変数を表す“オーバーレイサイズ”のような、よく知られているストリングをハッシングすることにより取得するデータキーにおいて記憶されることになるメッセージを、ジョインアナウンサーが送るときに、オーバーレイサイズカウンタがインクリメントされる。ジョインアナウンサーは、インクリメントを規定するメッセージをこのオーバーレイサイズカウンタのキーに送る。これらのメッセージに基づいて、カウンタを記憶するノード上で、すなわち、そのノードキーが、カウンタキー、例えば、ストリング“オーバーレイサイズ”のハッシュに最も近いノード上で、オーバーレイサイズカウンタをインクリメントさせる。１つのインプリメンテーションでは、プロセッサ２０２は、トランシーバ２０８を制御して、オーバーレイサイズカウンタをインクリメントさせるメッセージを送信する。
【００６１】
ブロック５０８において、離れるノードが検出されるか否かに関して、決定を行う。１つのインプリメンテーションでは、オーバーレイを離れる何らかのノードは、数値キースペース中でその隣接しているものに、進んでリーブメッセージを送る。それのノードキーが、時計回り方向において、離れるノードのキーに最も近いノードは、離れるノードに対する“リーブアナウンサー”として指定される。例えば、図１中に示したＡＳ装置１１２を備えるノード４が、時計回り方向において、離れるノードに最も近いと仮定する。したがって、ノード４は、リーブアナウンサーとして指定され、オーバーレイサイズカウンタをデクリメントさせることを担当する。１つのインプリメンテーションでは、オーバーレイネットワークを離れたいことを示す離れるノードからの通信を受信することにより、離れるノードが検出されるか否かに関して、プロセッサ２０２は決定を行う。離れるノードが検出された場合、方法はブロック５１０に進む。離れるノードが検出されなかった場合、方法はブロック５１２に進む。
【００６２】
ブロック５１０において、オーバーレイサイズカウンタをデクリメントさせるために、メッセージを送る。オーバーレイサイズカウンタは、分散ハッシュテーブル中に維持されている。以前に同意された一意的なカウンタ変数を表す“オーバーレイサイズ”のような、よく知られているストリングをハッシングすることにより取得するデータキーにおいて記憶されることになるメッセージを、リーブアナウンサーが送るときに、オーバーレイサイズカウンタがデクリメントされる。リーブアナウンサーは、デクリメントを規定するメッセージをこのオーバーレイサイズカウンタのキーに送る。これらのメッセージに基づいて、カウンタを記憶するノード上で、すなわち、そのノードキーが、カウンタキー、例えば、ストリング“オーバーレイサイズ”のハッシュに最も近いノード上で、オーバーレイサイズカウンタをデクリメントさせる。１つのインプリメンテーションでは、プロセッサ２０２は、トランシーバ２０８を制御して、オーバーレイサイズカウンタをデクリメントさせるメッセージを送信する。
【００６３】
ブロック５１２において、離れるノードが推測できるか否かに関して、決定を行う。ノードは、いつもオーバーレイネットワークに進んで加わるが、オーバーレイを進んで離れはしないかもしれないので、リーブアナウンサーは、ノードがオーバーレイを離れるときを推論により決定するように動作する。１つのインプリメンテーションでは、リーブアナウンサーは、ノードがオーバーレイを離れたと推測するとき、オーバーレイサイズカウンタを更新する。例えば、何らかの特定のノードに対するリーブアナウンサーは、その特定のノードに対する接続を維持して、リングのルーティング完全性を維持する必要がある。リーブアナウンサーは、接続の失敗または他の表示により、その特定のノードが離れたことを推測し、続いて、オーバーレイサイズカウンタを更新することができる。例えば、図１中に示したＡＳ装置１１２を備えるノード４は、特定のノードに対する接続を維持し、リングのルーティング完全性を維持することを仮定する。１つのインプリメンテーションでは、トランシーバ２０８は、特定のノードに関係する接続の失敗を検出する。したがって、ノード４は、リーブアナウンサーとして指定され、プロセッサ２０２は、進んだものでない離脱が起こったとしても、特定のノードがオーバーレイを離れたことを推測し、オーバーレイサイズカウンタを更新するように動作する。
【００６４】
１つのインプリメンテーションでは、接続の失敗を検出することにより、または、ノードがオーバーレイネットワークを離れたと示している第三者通信を受信することにより、ノードがオーバーレイを離れたことを推測するか否かに関して、プロセッサ２０２は決定を行う。第三者通信は、オーバーレイネットワーク中の別のノードから発信されてもよい。離れるノードが推測された場合、方法はブロック５１４に進む。離れるノードが推測されなかった場合、方法はブロック５１６に進む。
【００６５】
ブロック５１４において、オーバーレイサイズカウンタをデクリメントさせるために、メッセージを送る。オーバーレイサイズカウンタは、分散ハッシュテーブル中に維持されている。以前に同意された一意的なカウンタ変数を表す“オーバーレイサイズ”のような、よく知られているストリングをハッシングすることにより取得されるデータキーにおいて記憶されることになるメッセージを、リーブアナウンサーが送るときに、オーバーレイサイズカウンタがデクリメントされる。リーブアナウンサーは、デクリメントを規定するメッセージをこのオーバーレイサイズカウンタのキーに送る。これらのメッセージに基づいて、カウンタを記憶するノード上で、すなわち、そのノードキーが、カウンタキー、例えば、ストリング“オーバーレイサイズ”のハッシュに最も近いノード上で、オーバーレイサイズカウンタをデクリメントさせる。１つのインプリメンテーションでは、プロセッサ２０２は、トランシーバ２０８を制御して、オーバーレイサイズカウンタをデクリメントさせるメッセージを送信する。
【００６６】
ブロック５１６において、現在のネットワークサイズを決定するために、オーバーレイネットワークサイズカウンタに問い合わせる。オーバーレイサイズカウンタの現在の値を取り出すために、“オーバーレイサイズ”のような、よく知られているストリングをハッシングすることによる同じカウンタキーに問い合わせることにより、ノードは、ネットワークサイズについて知ることができる。オーバーレイサイズカウンタの現在の値は、オーバーレイネットワークサイズの現在の推定である。
【００６７】
ＡＳ装置２００を備える何らかのノードにおいて、上記の動作を実施できることに留意すべきである。したがって、ジョインアナウンサーまたはリーブアナウンサーとしてアクトする何らかのノードにより、オーバーレイサイズカウンタをインクリメントまたはデクリメントさせる分散方法で、動作を実施する。それゆえ、ＡＳシステムのインプリメンテーションは、進んだものでない離脱のケースにおいて、オーバーレイサイズカウンタを正確に更新できるように、ノードが離れていることを推測するように動作する。方法５００は１つのインプリメンテーションに過ぎないことと、方法５００の動作は、再構成することができ、または、そうでなければ、さまざまなインプリメンテーションの範囲内で修正できることとにも留意すべきである。したがって、他のインプリメンテーションも可能性がある。
【００６８】
サイズ決定―方法２
サイズ決定の第２の方法は、上記の方法５００中のような加わることと離れることとを示す何らかの特有なメッセージを送り出すことを必要とせず、分散ハッシュテーブル中に維持されるよく知られている同意されたカウンタでもない。第２の方法は、さらなる精度のために適用できる２つの改善を含む推定技術を利用する。
【００６９】
図６は、ＡＳシステムにしたがってオーバーレイネットワークサイズを決定するための第２の方法６００を示している。方法６００では、Ｓは、何らかのセットのｋ個のノードにより管理されるセグメント長（数値ＩＤスペースの長さ）の合計を示す。そして、オーバーレイサイズの推定Ｅ、すなわち、オーバーレイ中のノードの数は、ｋ／Ｓから決定できる。
【００７０】
明確にするために、図２中に示したＡＳ装置２００を参照して、方法６００を下記に記述する。１つのインプリメンテーションでは、プロセッサ２０２は、ＡＳ装置２００を制御するための１つ以上のセットのコードを実行して、下記に記述する機能を実施する。オーバーレイネットワーク中のノードにおいてＡＳ装置が位置していることと、ＡＳ装置２００は、下記の機能を実施して、オーバーレイネットワークのサイズを決定することとを仮定する。
【００７１】
ブロック６０２において、オーバーレイネットワーク中で、ノードのセットを識別する。セットは、オーバーレイネットワーク中のノードのうちのいくつかまたはすべてを含んでいてもよい。例えば、ノードは、フィンガーを、隣接するものを、または、ＡＳ装置を備えるノードと通信中であるノードを含んでいてもよい。１つのインプリメンテーションでは、プロセッサ２０２は、セットの一部であるノードを識別するように動作する。
【００７２】
ブロック６０４において、ノードのセットに関係するセグメント長を取得する。１つのインプリメンテーションでは、これらの関係するセグメント長を取得するために、ノードのセットに問い合わせる。セグメント長は、所定のノードとその時計回りの後継点との間のＩＤスペースの一部である。セグメント長が減少するにつれて、ネットワーク中のノードの数がより多くなる。
【００７３】
オーバーレイネットワーク中のすべてのノードをサンプリングして、それらの関係するセグメント長を導出することは実用的ではないかもしれないので、１つのインプリメンテーションでは、ＡＳ装置を備えるノードが、そのノードが既にルーティング関係を維持するノードに、それらのセグメント長を尋ねる。例えば、ＡＳ装置は、セット中のノードのそれぞれに対して、それらが管理するセグメント長について問い合わせることが可能である。別のインプリメンテーションでは、セグメント長情報は、ＡＳ装置を備えるノードと、そのそれぞれのフィンガーまたは隣接するものとの間の通常のメッセージのトップ上にピギーバックされている。したがって、プロセッサ２０２は、トランシーバ２０８を制御して、通常通信のトップ上に情報をピギーバックさせることにより、ノードのセットから、セグメント情報のうちのいくつかまたはすべてを取得する。
【００７４】
ブロック６０６において、それらのセグメント長の合計で割ったセット中のノードの数に基づいて、オーバーレイネットワークのサイズを決定する。例えば、ＩＤスペースの長さは、０と１との間になるように区分されていると仮定する。オーバーレイネットワーク中に１つのノードのみがある場合には、Ｅ＝１／１＝１であり、このケースにおいて正しい推定である。２つのノードと、これらが、第１のノードが０．３を所有し、第２のノードが０．７を所有するように、ＩＤスペースを区分することを考える。そのとき、Ｅ＝２／（０．３＋０．７）＝２である。１つのインプリメンテーションでは、プロセッサ２０２は、セット中のノードの総数を、それらの関係するセグメント長の合計で割ることにより、オーバーレイネットワークの推定されるサイズを決定するように動作する。
【００７５】
それゆえ、方法６００は、ノードの識別されたセットと、それらの関係するセグメント長とに基づいて、オーバーレイネットワークのサイズを決定するように動作する。方法６００は１つのインプリメンテーションに過ぎないことと、方法６００の動作は、再構成することができ、または、そうでなければ、さまざまなインプリメンテーションの範囲内で修正できることとに留意すべきである。したがって、他のインプリメンテーションも可能性がある。
【００７６】
方法２に対する改善
図７は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定する第１の改善方法７００を示している。例えば、方法７００では、１つ以上ノードからの推定を平均することにより、より正確なおよび／またはよりロバーストなオーバーレイサイズ推定を決定するように動作する。明確にするために、図２中に示されたＡＳ装置２００を参照して、方法７００を下記に記述する。１つのインプリメンテーションでは、プロセッサ２０２は、ＡＳ装置２００を制御するための１つ以上のセットのコードを実行して、下記に記述する機能を実施する。ＡＳ装置２００は、オーバーレイネットワーク中のノードにおいて位置していることと、ＡＳ装置２００は、下記の機能を実施して、オーバーレイネットワークのサイズを決定することとを仮定する。
【００７７】
ブロック７０２において、第１のノードにおいて、サイズ推定を決定する。１つのインプリメンテーションでは、サイズ推定は、方法６００により決定する。例えば、ＡＳ装置２００は、第１のノードにおいて、方法６００を実施して、オーバーレイネットワークのサイズ推定を決定するように動作する。
【００７８】
ブロック７０４において、他のノードからのサイズ推定を取得する。例えば、ＡＳ装置を備える第１のノードは、他のノードからサイズ推定を取得するように動作する。１つのインプリメンテーションでは、フィンガーから、隣接するものから、および、第１のノードと通信中である他のノードから、サイズ推定を取得する。例えば、プロセッサ２０２は、トランシーバ２０８を制御して、他のノードにそれらのそれぞれのサイズ推定を問い合わせることにより、他のノードからのサイズ推定を取得するように動作する。
【００７９】
ブロック７０６において、取得したサイズ推定に基づいて、オーバーレイサイズを決定する。１つのインプリメンテーションでは、第１のノードは、第１のノードがそのフィンガーから、隣接するものから、または他のノードから知ったすべてのオーバーレイサイズ推定の平均を取ることにより、そのサイズ推定をさらに改善することができる。したがって、最終サイズ推定Ｅ＝（Ｅ０＋Ｅ１＋Ｅ２＋...＋Ｅｎ）／ｎである。ここで、Ｅ１からＥｎは、ｎ個の他のノードから取得したサイズ推定であり、Ｅ０は、第１のノードのサイズ推定である。１つのインプリメンテーションでは、プロセッサ２０２は、サイズ推定を平均して、より正確な平均されたサイズ推定を取得するように動作する。
【００８０】
それゆえ、方法７００は、より正確な平均されたサイズ推定を取得するために、１つ以上のノードからのサイズ推定を平均することにより、第１の方法６００を改善するように動作する。方法７００は１つのインプリメンテーションに過ぎないことと、方法７００の動作は、再構成することができ、または、そうでなければ、さまざまなインプリメンテーションの範囲内で修正できることとに留意すべきである。したがって、他のインプリメンテーションも可能性がある。
【００８１】
図８は、ＡＳシステムにしたがって、オーバーレイネットワークサイズを決定するための第２の改善方法８００を示している。例えば、方法８００は、オーバーレイネットワーク中の何らかのノードからの推定を平均することにより、より正確なおよび／またはロバーストなオーバーレイサイズ推定を決定するように動作する。明確にするために、図２中に示したＡＳ装置２００を参照して、方法８００を下記に記述する。１つのインプリメンテーションでは、プロセッサ２０２は、ＡＳ装置２００を制御するための１つ以上のセットのコードを実行して、下記に記述する機能を実施する。ＡＳ装置２００は、オーバーレイネットワーク中の第１のノードにおいて位置していることと、ＡＳ装置２００は、下記の機能を実施して、オーバーレイネットワークのサイズを決定することとを仮定する。
【００８２】
ブロック８０２において、第１のノードにおいて、サイズ推定を決定する。１つのインプリメンテーションでは、サイズ推定は、方法６００により決定する。例えば、ＡＳ装置２００は、第１のノードにおいて、方法６００を実施して、オーバーレイネットワークのサイズ推定を決定するように動作する。
【００８３】
ブロック８０４において、他のノードからのサイズ推定を取得する。例えば、上記の方法７００を使用して、他のノードからサイズ推定のサンプリングがＩＤスペース中で均一でない可能性がある。これに取り組むために、何らかのノードとの何らかのパケット交換上にサイズ推定情報をピギーバックさせる。これは、そのノードから個々のサイズ推定が取得されるノードの数を増加させることから、ネットワークのサイズ推定のよりロバーストなビューを提供する。ノードの隣接するもののみからのこれらの推定を取得するよりむしろ、この改善は、特定のノードを通してパケットをルーティングする何らかのノードからこの情報を得ることを可能にし、または、ルーティングから離れて特定のノードとのトランザクションを行うことを可能にする。したがって、第１のノードは、フィンガーから、隣接しているものから、および、第１のノードと対話する他の何らかのノードからサイズ推定を取得することができる。１つのインプリメンテーションでは、プロセッサ２０２は、トランシーバ２０８を制御して、第１のノードとの何らかのパケット交換上にピギーバックされたサイズ推定を取得するように動作する。
【００８４】
ブロック８０６において、取得したサイズ推定に基づいて、オーバーレイサイズを決定する。１つのインプリメンテーションでは、第１のノードは、そのフィンガーから、隣接するものから、または、第１のノードと通信中である他の何らかのノードから第１のノードが知ったすべてのオーバーレイサイズ推定の平均を取ることにより、そのサイズ推定をさらに改善できる。したがって、最終サイズ推定Ｅ＝（Ｅ０＋Ｅ１＋Ｅ２＋...＋Ｅｎ）／ｎである。ここで、Ｅ１からＥｎは、ｎ個の他のノードから取得したサイズ推定であり、Ｅ０は、第１のノードのサイズ推定である。１つのインプリメンテーションでは、プロセッサ２０２は、サイズ推定を平均して、より正確なサイズ推定を取得するように動作する。
【００８５】
それゆえ、方法８００は、何らかのパケット送信上にピギーバックされていて取得したサイズ推定を提供して、よりロバーストな平均を提供することにより、第１の方法６００を改善するように動作する。方法８００は１つのインプリメンテーションに過ぎないことと、方法８００の動作は、再構成することができ、または、そうでなければ、さまざまなインプリメンテーションの範囲内で修正できることとに留意すべきである。したがって、他のインプリメンテーションも可能性がある。
【００８６】
図９は、ＡＳシステムにしたがって構築された例示的なＡＳ装置９００を示している。例えば、ＡＳ装置９００は、図２中に示したＡＳ装置２００としての使用に適している。ある態様では、ここで記述したようなＡＳシステムの態様を提供するように構成されている１つ以上のモジュールを備える少なくとも１つの集積回路により、ＡＳ装置９００を実現する。例えば、１つのインプリメンテーションでは、それぞれのモジュールは、ハードウェア、および／または、ハードウェア実行ソフトウェアを備える。
【００８７】
ＡＳ装置９００は、第１のノードがオーバーレイネットワークを離れていることを推測する手段（９０２）を含む第１のモジュールを備える。この第１のノードは、ある態様ではプロセッサ２０２を含む。ＡＳ装置９００はまた、サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信する手段（９０４）を含む第２のモジュールを備える。この第２のモジュールは、ある態様ではトランシーバ２０８を含む。
【００８８】
図１０は、ＡＳシステムにしたがって構築された例示的なＡＳ装置１０００を示している。例えば、ＡＳ装置１０００は、図２中で示したＡＳ装置２００としての使用に適している。ある態様では、ここで記述したようなＡＳシステムの態様を提供するように構成されている１つ以上のモジュールを備える少なくとも１つの集積回路により、ＡＳ装置１０００を実現する。例えば、１つのインプリメンテーションでは、それぞれのモジュールは、ハードウェア、および／または、ハードウェア実行ソフトウェアを備える。
【００８９】
ＡＳ装置１０００は、オーバーレイの第１のノードに関係するノードのセットを識別する手段（１００２）を含む第１のモジュールを備える。この第１のモジュールは、ある態様ではプロセッサ２０２を含む。ＡＳ装置１０００はまた、ノードのセットのそれぞれのノードに関係するセグメント長を取得する手段（１００４）を含む第２のモジュールを備える。この第２のモジュールは、ある態様ではトランシーバ２０８を含む。ＡＳ装置１０００はまた、ノードのセット中のノードの総数を、セグメント長の合計で割ることにより、オーバーレイネットワークのサイズを決定する手段（１００６）を含む第３のモジュールを備える。この第３のモジュールは、ある態様ではプロセッサ２０２を含む。
【００９０】
図１１は、ＡＳシステムにしたがって構築された例示的なＡＳ装置１１００を示している。例えば、ＡＳ装置１１００は、図２中で示したＡＳ装置２００としての使用に適している。ある態様では、ここで記述したようなＡＳシステムの態様を提供するように構成されている１つ以上のモジュールを備える少なくとも１つの集積回路により、ＡＳ装置１１００を実現する。例えば、１つのインプリメンテーションでは、それぞれのモジュールは、ハードウェア、および／または、ハードウェア実行ソフトウェアを備える。
【００９１】
ＡＳ装置１１００は、オーバーレイネットワークの第１のノードに関係するノードのセットを識別する手段（１１０２）を含む第１のモジュールを備える。この第１のモジュールは、ある態様ではプロセッサ２０２を含む。ＡＳ装置１１００はまた、第１のノードに関係するサイズ推定と、ノードのセットのそれぞれのノードに関係するサイズ推定とを取得する手段（１１０４）を含む第２のモジュールを備える。この第２のモジュールは、ある態様ではトランシーバ２０８を含む。ＡＳ装置１１００はまた、サイズ推定を平均することにより、オーバーレイネットワークのサイズを決定する手段（１１０６）を含む第３のモジュールを備える。この第３のモジュールは、ある態様ではプロセッサ２０２を含む。
【００９２】
ここに開示した態様と関連して説明したさまざまな例示的な論理、論理ブロック、モジュールおよび回路は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、現場プログラム可能ゲートアレイ（ＦＰＧＡ）または他のプログラム可能論理デバイス、ディスクリートゲートまたはトランジスタ論理、ディスクリートハードウェアコンポーネント、あるいは、ここに記述した機能を実行するように設計されているこれらの任意の組み合わせたものにより、実現または実行してもよい。汎用プロセッサはマイクロプロセッサであってもよいが、代替実施形態では、プロセッサは、任意の従来のプロセッサ、制御装置、マイクロ制御装置、または状態機械であってもよい。プロセッサはまた、例えば、ＤＳＰおよびマイクロプロセッサを組み合わせたものや、複数のマイクロプロセッサや、ＤＳＰコアを伴う１つ以上のマイクロプロセッサや、任意のその他のこのようなコンフィギュレーションのような、コンピューティングデバイスを組み合わせたものとして実現してもよい。
【００９３】
ここに開示した態様と関連して記述した方法またはアルゴリズムのステップは、ハードウェアで、プロセッサにより実行されるソフトウェアモジュールで、あるいは、双方を組み合わせたもので直接的に具現化してもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーブバルディスク、ＣＤ−ＲＯＭ、または、技術的に知られている他の何らかの形態の記憶媒体に存在していてもよい。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるようにプロセッサに結合されていてもよい。代替実施形態では、記憶媒体は、プロセッサと一体化されていてもよい。プロセッサおよび記憶媒体は、ＡＳＩＣに存在していてもよい。ＡＳＩＣは、ワイヤレス通信デバイスに存在していてもよい。代替実施形態では、プロセッサおよび記憶媒体は、ディスクリートコンポーネントとしてワイヤレス通信デバイスに存在していてもよい。
【００９４】
開示した態様の記述は、当業者が本発明を製作または使用できるように提供した。これらの態様に対するさまざま改良は当業者に容易に明らかになり、ここに規定した一般的な原理は、例えば、インスタントメッセージングサービス中、または、任意の一般的なワイヤレスデータ通信アプリケーション中で、本開示の精神または範囲から逸脱することなく、他の態様に適用してもよい。したがって、本開示は、ここで示した態様に限定されることを意図しているものではなく、ここで開示した原理および新しい特徴と一致した最も広い範囲に一致させるべきである。 “例示的な”という用語は、“例として、インスタンスとして、あるいは例証として機能すること”を意味するように、ここでは排他的に使用している。“例示的な”としてここで記述した何らかの態様は、必ずしも、他の態様より好ましい、または、効果的であるとして解釈すべきではない。
【００９５】
したがって、適応スケジューリングシステムの態様をここに図示し、記述してきたが、それらの精神または不可欠な特性から逸脱することなく、態様に対してさまざまな変更を行うことができることを正しく認識するだろう。それゆえ、ここでの開示および記述は、これには限定されないが、下記の特許請求の範囲において述べる本発明の範囲を例示するものであることを意図している。
以下に、本願出願時の特許請求の範囲に記載された発明を付記する。
［１］ピアツーピアオーバーレイネットワークのサイズを決定するための方法において、
第１のノードが前記オーバーレイネットワークを離れていることを推測することと、
サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信することとを含む方法。
［２］前記推測することは、前記第１のノードとの通信が失敗したことを決定することを含む［１］記載の方法。
［３］前記推測することは、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信することを含む［１］記載の方法。
［４］第２のノードが前記オーバーレイネットワークに加わっていることを決定することと、
前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信することとをさらに含む［１］記載の方法。
［５］第３のノードが前記オーバーレイネットワークを離れていることを決定することと、
前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信することとをさらに含む［１］記載の方法。
［６］前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定することをさらに含む［１］記載の方法。
［７］前記サイズカウンタ値を問い合わせることは、よく知られているストリングをハッシングして、前記サイズカウンタ値を導出することを含む［６］記載の方法。
［８］ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
第１のノードが前記オーバーレイネットワークを離れていることを推測するように構成されているプロセッサと、
前記プロセッサに結合されており、サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するように構成されている送信機とを具備する装置。
［９］前記プロセッサは、前記第１のノードとの通信が失敗したことを決定することにより、推測するように構成されている［８］記載の装置。
［１０］前記プロセッサは、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信することにより、推測するように構成されている［８］記載の装置。
［１１］前記プロセッサは、第２のノードが前記オーバーレイネットワークに加わっていることを決定するように構成され、
前記送信機は、前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信するように構成されている［８］記載の装置。
［１２］前記プロセッサは、第３のノードが前記オーバーレイネットワークを離れていることを決定するように構成され、
前記送信機は、前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するように構成されている［８］記載の装置。
［１３］前記プロセッサは、前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定するように構成されている［８］記載の装置。
［１４］前記プロセッサは、よく知られているストリングをハッシングして、前記サイズカウンタ値を導出することにより、前記サイズカウンタ値を問い合わせるように構成されている［１３］記載の装置。
［１５］ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
第１のノードが前記オーバーレイネットワークを離れていることを推測する手段と、
サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信する手段とを具備する装置。
［１６］前記推測する手段は、前記第１のノードとの通信が失敗したことを決定する手段を備える［１５］記載の装置。
［１７］前記推測する手段は、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信する手段を備える［１５］記載の装置。
［１８］第２のノードが前記オーバーレイネットワークに加わっていることを決定する手段と、
前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信する手段とをさらに具備する［１５］記載の装置。
［１９］第３のノードが前記オーバーレイネットワークを離れていることを決定する手段と、
前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信する手段とをさらに具備する［１５］記載の装置。
［２０］前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定する手段をさらに具備する［１５］記載の装置。
［２１］前記サイズカウンタ値を問い合わせる手段は、よく知られているストリングをハッシングして、前記サイズカウンタ値を導出する手段を備える［２０］記載の装置。
［２２］ピアツーピアオーバーレイネットワークのサイズを決定するためのコンピュータプログラムプロダクトにおいて、
第１のノードが前記オーバーレイネットワークを離れていることを推測するための、プロセッサにより実行可能なコードと、
サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信するための、前記プロセッサにより実行可能なコードとを具現化するコンピュータ読取可能媒体を含むコンピュータプログラムプロダクト。
［２３］前記コードは、前記プロセッサに、前記第１のノードとの通信が失敗したことを決定させることにより推測させるように構成されている［２２］記載のコンピュータ読取可能媒体。
［２４］前記コードは、前記プロセッサに、前記第１のノードが前記オーバーレイネットワークを離れているという表示を第三者から受信させることにより推測させるように構成されている［２２］記載のコンピュータ読取可能媒体。
［２５］前記コードは、
前記プロセッサに、第２のノードが前記オーバーレイネットワークに加わっていることを決定させるように構成され、
前記プロセッサに、前記サイズカウンタ値をインクリメントさせるインクリメントメッセージを送信させるように構成されている［２２］記載のコンピュータ読取可能媒体。
［２６］前記コードは、
前記プロセッサに、第３のノードが前記オーバーレイネットワークを離れていることを決定させるように構成され、
前記プロセッサに、前記サイズカウンタ値をデクリメントさせるデクリメントメッセージを送信させるように構成されている［２２］記載のコンピュータ読取可能媒体。
［２７］前記コードは、前記プロセッサに、前記サイズカウンタ値を問い合わせて、前記オーバーレイネットワークのサイズを決定させるように構成されている［２２］記載のコンピュータ読取可能媒体。
［２８］前記コードは、前記プロセッサに、よく知られているストリングをハッシングさせて、前記サイズカウンタ値を導出させることにより、前記サイズカウンタ値を問い合わせさせるように構成されている［２７］記載のコンピュータ読取可能媒体。
［２９］ピアツーピアオーバーレイネットワークのサイズを決定するための方法において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別することと、
前記ノードのセットのそれぞれのノードに関係するセグメント長を取得することと、
前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定することとを含む方法。
［３０］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［２９］記載の方法。
［３１］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［２９］記載の方法。
［３２］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［２９］記載の方法。
［３３］前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記セグメント長の少なくとも一部分を取得することを含む［２９］記載の方法。
［３４］前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得することを含む［２９］記載の方法。
［３５］ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別するように構成されているプロセッサと、
前記プロセッサに結合されており、前記ノードのセットのそれぞれのノードに関係するセグメント長を取得するように構成されているトランシーバと、
前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定するように構成されている前記プロセッサとを具備する装置。
［３６］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［３５］記載の装置。
［３７］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［３５］記載の装置。
［３８］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［３５］記載の装置。
［３９］前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記セグメント長の少なくとも一部分を取得するように構成されている［３５］記載の装置。
［４０］前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得するように構成されている［３５］記載の装置。
［４１］ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別する手段と、
前記ノードのセットのそれぞれのノードに関係するセグメント長を取得する手段と、
前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定する手段とを具備する装置。
［４２］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［４１］記載の装置。
［４３］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［４１］記載の装置。
［４４］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［４１］記載の装置。
［４５］前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記セグメント長の少なくとも一部分を取得する手段を備える［４１］記載の装置。
［４６］前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得する手段を備える［４１］記載の装置。
［４７］ピアツーピアオーバーレイネットワークのサイズを決定するためのコンピュータプログラムプロダクトにおいて、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別するためのプロセッサにより実行可能なコードと、
前記ノードのセットのそれぞれのノードに関係するセグメント長を取得するための前記プロセッサにより実行可能なコードと、
前記ノードのセット中のノードの総数を、前記セグメント長の合計で割ることにより、前記オーバーレイネットワークのサイズを決定するための、前記プロセッサにより実行可能なコードとを具現化するコンピュータ読取可能媒体を含むコンピュータプログラムプロダクト。
［４８］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［４７］記載のコンピュータ読取可能媒体。
［４９］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［４７］記載のコンピュータ読取可能媒体。
［５０］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［４７］記載のコンピュータ読取可能媒体。
［５１］前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせさせて、前記セグメント長の少なくとも一部分を取得させるように構成されている［４７］記載のコンピュータ読取可能媒体。
［５２］前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記セグメント長の少なくとも一部分を取得させるように構成されている［４７］記載のコンピュータ読取可能媒体。
［５３］ピアツーピアオーバーレイネットワークのサイズを決定するための方法において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別することと、
前記第１のノードに関係するサイズ推定と、前記ノードのセットのそれぞれのノードに関係するサイズ推定とを取得することと、
前記サイズ推定を平均することにより、前記オーバーレイネットワークのサイズを決定することとを含む方法。
［５４］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［５３］記載の方法。
［５５］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［５３］記載の方法。
［５６］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［５３］記載の方法。
［５７］前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記サイズ推定の少なくとも一部分を取得することを含む［５３］記載の方法。
［５８］前記取得することは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記サイズ推定の少なくとも一部分を取得することを含む［５３］記載の方法。
［５９］ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別し、前記第１のノードに関係するサイズ推定を取得するように構成されているプロセッサと、
前記プロセッサに結合されており、前記ノードのセットのそれぞれのノードに関係するサイズ推定を取得するように構成されているトランシーバと、
前記サイズ推定を平均することにより、前記オーバーレイネットワークのサイズを決定するように構成されている前記プロセッサとを具備する装置。
［６０］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［５９］記載の装置。
［６１］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［５９］記載の装置。
［６２］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［５９］記載の装置。
［６３］前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記サイズ推定の少なくとも一部分を取得するように構成されている［５９］記載の装置。
［６４］前記トランシーバは、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記サイズ推定の少なくとも一部分を取得するように構成されている［５９］記載の装置。
［６５］ピアツーピアオーバーレイネットワークのサイズを決定するための装置において、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別する手段と、
前記第１のノードに関係するサイズ推定と、前記ノードのセットのそれぞれのノードに関係するサイズ推定とを取得する手段と、
前記サイズ推定を平均することにより、前記オーバーレイネットワークのサイズを決定する手段とを具備する装置。
［６６］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［６５］記載の装置。
［６７］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［６５］記載の装置。
［６８］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［６５］記載の装置。
［６９］前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせて、前記サイズ推定の少なくとも一部分を取得する手段を備える［６５］記載の装置。
［７０］前記取得する手段は、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記サイズ推定の少なくとも一部分を取得する手段を備える［６５］記載の装置。
［７１］ピアツーピアオーバーレイネットワークのサイズを決定するためのコンピュータプログラムプロダクトにおいて、
オーバーレイネットワークの第１のノードに関係するノードのセットを識別するための、プロセッサにより実行可能なコードと、
前記第１のノードに関係するサイズ推定を取得するための、前記プロセッサにより実行可能なコードと、
前記ノードのセットのそれぞれのノードに関係するサイズ推定を取得するための、前記プロセッサにより実行可能なコードと、
前記サイズ推定を平均することにより、前記オーバーレイネットワークのサイズを決定するための、前記プロセッサにより実行可能なコードとを具現化するコンピュータ読取可能媒体を含むコンピュータプログラムプロダクト。
［７２］前記ノードのセットは、前記第１のノードに関係するフィンガーを含む［７１］記載のコンピュータ読取可能媒体。
［７３］前記ノードのセットは、前記第１のノードに関係する隣接しているものを含む［７１］記載のコンピュータ読取可能媒体。
［７４］前記ノードのセットは、前記第１のノードと通信中の１つ以上のノードを含む［７１］記載のコンピュータ読取可能媒体。
［７５］前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分に問い合わせさせて、前記サイズ推定の少なくとも一部分を取得させるように構成されている［７１］記載のコンピュータ読取可能媒体。
［７６］前記コードは、前記プロセッサに、それぞれ、前記ノードのセットの少なくとも一部分とのピギーバック通信中に、前記サイズ推定の少なくとも一部分を取得させるように構成されている［７１］記載のコンピュータ読取可能媒体。
【図１】
0005307255.tif 000002
【図２】
0005307255.tif 000003
【図３】
0005307255.tif 000004
【図４】
0005307255.tif 000005
【図５】
0005307255.tif 000006
【図６】
0005307255.tif 000007
【図７】
0005307255.tif 000008
【図８】
0005307255.tif 000009
【図９】
0005307255.tif 000010
【図１０】
0005307255.tif 000011
【図１１】
0005307255.tif 000012