(57)【要約】  ピアノードの処理キャパシティに関する情報をノード間で発信するための方法及びノードが提供される。発信するノードからそのピアノードに向けて２つのタイプの信号が送信される。発信するノードは、第１の信号のタイプを一定のレートで送信し、第２の信号のタイプを可変レートで送信する。ピアノードにおいて算出されるレートの比率は、発信するノードに利用可能な処理キャパシティを表す。シーケンス番号は、キャパシティの問題を検出する際ピアノードを支援するために第１及び第２のタイプの信号に追加されてもよい。【選択図】図２
2011507378.tif 000002
【特許請求の範囲】
【請求項１】
ノードの処理キャパシティに関する情報を取得する方法であって：
前記ノードから第１のレートで第１の信号を受信するステップと；
前記ノードから第２のレートで第２の信号を受信するステップと；
前記第２のレートと前記第１のレートとの間の比率を算出するステップと；
前記比率のプリセット値との比較に基づいて前記ノードの前記処理キャパシティを決定するステップと；
を含む方法。
【請求項２】
前記第１のレートは一定であり；及び
前記第２のレートは可変である；
請求項１に記載の方法。
【請求項３】
前記プリセット値は、前記ノードが通常の処理キャパシティを有する場合の前記第２及び第１のレートの間の比率に等しい、
請求項１に記載の方法。
【請求項４】
前記ノードの前記処理キャパシティを決定する前記ステップに基づいてルーティングテーブルを更新するステップと；
前記ノードの前記処理キャパシティが低い場合に、前記ノードに向けてメッセージを送信することを控えるステップと；
をさらに含む、請求項１に記載の方法。
【請求項５】
前記比率における変化を監視するステップと；
前記比率が変化する場合に、前記ノードの処理キャパシティの変化を検出するステップと；
をさらに含む、請求項１に記載の方法。
【請求項６】
前記第２のレートの減少は、前記処理キャパシティの低下を示す、
請求項５に記載の方法。
【請求項７】
連続する第１の信号の各々は、前回の第１の信号のシーケンス番号に基づいて算出されるシーケンス番号を含み；
最新の第１の信号の直後に受信される第２の信号は、前記最新の第１の信号のシーケンス番号に基づくシーケンス番号を含み；及び
次回の第１の信号の前に受信される連続する第２の信号の各々は、前回の第２の信号のシーケンス番号に基づくシーケンス番号を含む、
請求項１に記載の方法。
【請求項８】
連続する第１の信号の各々における前記シーケンス番号は、前記前回の第１の信号の前記シーケンス番号に前記プリセット値を加えたものに等しく；
前記最新の第１の信号の直後に受信される前記第２の信号における前記シーケンス番号は、前記最新の第１の信号の前記シーケンス番号に１を加えたものに等しく；及び
前記次回の第１の信号の前に受信される連続する第２の信号の各々における前記シーケンス番号は、前記前回の第２の信号の前記シーケンス番号に１を加えたものに等しい、
請求項７に記載の方法。
【請求項９】
前記最新の第１の信号の前記シーケンス番号に基づいて、又は前記前回の第２の信号の前記シーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号を算出するステップと；
前記期待されるシーケンス番号に等しくないシーケンス番号を含む前記次回の第２の信号を受信することにより、キャパシティの問題を検出するステップと；
をさらに含む、請求項７に記載の方法。
【請求項１０】
前記最新の第１の信号の前記シーケンス番号に基づいて、又は前記前回の第２の信号の前記シーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号を算出するステップ、をさらに含み；
前記第２のレートと前記第１のレートとの間の前記比率を算出することは、前記期待されるシーケンス番号に合致しないシーケンス番号を含む所与の第２の信号を無視することを含む、
請求項７に記載の方法。
【請求項１１】
ノードの処理キャパシティに関する情報を発信する方法であって：
前記ノードの通常の処理キャパシティを示すプリセット値以下である提供キャパシティ値を決定するステップと；
前記ノードから基本レートで周期的に第１の信号を送信するステップと；
前記ノードから前記提供キャパシティ値を示す第２のレートで周期的に第２の信号を送信するステップと；
を含む方法。
【請求項１２】
前記ノードは複数のインタフェースを含み；
周期的な第１の信号の各々は全てのインタフェース上を送信され；及び
周期的な第２の信号の各々は全てのインタフェース上を送信される、
請求項１１に記載の方法。
【請求項１３】
前記第２のレートは、前記基本レートに前記提供キャパシティ値を乗じたものに等しい、
請求項１１に記載の方法。
【請求項１４】
前記提供キャパシティ値は、周期的に決定される、
請求項１１に記載の方法。
【請求項１５】
前記提供キャパシティ値は、前記ノードの実際の処理キャパシティに従って設定される、
請求項１１に記載の方法。
【請求項１６】
前記提供キャパシティ値は、前記ノードの実際の処理キャパシティから負荷制限値（load  limiting  value）を引いたものに従って設定される、
請求項１１に記載の方法。
【請求項１７】
自身の処理キャパシティに関する情報を発信するためのノードであって：
プロセッサと；
前記プロセッサの負荷レベルを示すよう構成される負荷インジケータと；
ピアノードに向けて信号を送信するよう構成される１つ以上のインタフェースと；
前記プロセッサの前記負荷レベルを読み取り；
第１のレートで第１の信号を送信するよう前記１つ以上のインタフェースに要求し；
前記負荷レベルと前記ノードの処理キャパシティの最大量との比較に基づいて第２のレートを算出し；及び
前記第２のレートで第２の信号を送信するよう前記１つ以上のインタフェースに要求する；
よう構成される、制御ロジックと；
を含むノード。
【請求項１８】
前記第１のレートで前記制御ロジックのシーケンスを開始するよう構成されるクロック
をさらに含む、請求項１７に記載のノード。
【請求項１９】
前記負荷レベルと処理の前記最大量との比較に基づいて第２のレートを算出することは、前記負荷レベルが低い場合に前記第２のレートを最大値に設定することを含む、
請求項１７に記載のノード。
【請求項２０】
連続する第１の信号の各々は、前回の第１の信号のシーケンス番号に基づいて算出されるシーケンス番号を含み；
最新の第１の信号の直後に送信される第２の信号は、前記最新の第１の信号のシーケンス番号に基づくシーケンス番号を含み；及び
次回の第１の信号の前に送信される連続する第２の信号の各々は、前回の第２の信号のシーケンス番号に基づくシーケンス番号を含む、
請求項１７に記載のノード。
【請求項２１】
ピアノードの処理キャパシティに関する情報を取得するためのノードであって：
前記ピアノードから信号を受信するよう構成される１つ以上のインタフェースと；
前記１つ以上のインタフェースから第１の信号を複数回受信し；
前記第１の信号の第１のレートを決定し；
前記１つ以上のインタフェースから第２の信号を複数回受信し；
前記第２の信号の第２のレートを決定し；
前記第２及び第１のレートの間の比率を算出し；並びに
前記比率に基づく前記ピアノードの処理キャパシティをピアテーブルに記憶する；
よう構成される、制御ロジックと；
を含むノード。
【請求項２２】
クロックをさらに含み、並びに
前記制御ロジックは、前記クロックからのタイミング情報を使用して前記第１及び第２のレートを決定し、並びに前記第１及び第２のレートを前記ピアテーブルに記憶する；
請求項２１に記載のノード。
【請求項２３】
前記第１及び第２の信号は、シーケンス番号を含み；
前記制御ロジックは、最新の第１の信号のシーケンス番号に基づいて、又は前回の第２の信号のシーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号を計算するようさらに構成され；並びに
前記制御ロジックは、前記期待されるシーケンス番号を前記ピアテーブルに記憶するようさらに構成される；
請求項２１に記載のノード。
【請求項２４】
前記制御ロジックは、前記期待されるシーケンス番号に等しくないシーケンス番号を含む次回の第２の信号を受信することにより、キャパシティの問題を検出するようさらに構成される、
請求項２３に記載のノード。
【請求項２５】
前記第２及び第１のレートの間の比率を算出することは、前記期待されるシーケンス番号に合致しないシーケンス番号を含む所与の第２の信号を無視することを含む、
請求項２３に記載のノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算キャパシティに関するメトリック（metric）情報をノード間で交換するための方法及びノードに関する。
【背景技術】
【０００２】
計算ノード（computing  nodes）のネットワークにおいて、ノード間の通信は、予め定義されたルールに従って行われてもよく、又はネットワークの現在の状態に基づくメトリックに従って行われてもよい。ネットワーク、特にアドホックなネットワークにおけるノードの調整は、問題を孕み得る。例えば、複数のノードが全て同じ処理パワーを有しているわけではない場合、ノード間のリンクの既知の又は期待されるキャパシティのみに従ってルーティングすることは、効率的でない可能性がある。ネットワークには、可変レベルの柔軟性をもって設計されるものもあり、そのノードのうちのいくつかはメッセージ又は要求を送信する際にピアノード間における宛先を選択することができる。これらネットワークを効率的な手法で運用できるようにするために、ノードがそのような選択をすることを可能とする改良されたメトリックを提供することが必要となる。
【０００３】
２つのコプロセッサ上に負荷をバランシングする単純な手法は、単純に一方のプロセッサ上に一定のタスクを、もう一方のプロセッサ上に他のタスクを割り当てることである。例えば、パーソナルコンピュータ上の１つの中央処理装置（ＣＰＵ）は、もう一方のＣＰＵが入力データの計算を処理する傍ら、画像表示を処理し得る。このような所定の構成（pre-arranged）は、例えば出力を画像で表示できるようにする前に大量の入力データを処理する必要がある場合、非常に非効率的である。
【０００４】
処理負荷をバランシングする他の方法は、様々なプロセッサをスキャンすることにより、各プロセッサにおいて処理を待つタスクキューの長さを取得することである。この方法は、様々なプロセッサが同一の場所に配置されている場合のみ効果があり、例えばコプロセッサの場合、少なくともある部分スキャン処理の実行に供される１つの個別のプロセッサに依存し得る。
【０００５】
並行スケジューリングは、負荷をバランシングするための別のアプローチである。並行スケジューリングの方法において、全てのプロセッサは協同して仕事をスケジューリングする。並行スケジューリングは、コンパイル時間又は実行時間において全体的な負荷情報を使用することにより負荷をバランシングする。これらの方法は一般に、プロセッサの相対的な処理キャパシティを考慮した、様々なプロセッサへの予め決定されたタスクの割り当てに依存する。並行スケジューリングの方法は、ノードにかかる負荷の観点についての時間的に変化する要件のような、変化する条件にほとんど適応できない。
【０００６】
２つのノード間における最適な計算パスを見つけるためにルーティングプロトコルと共に通常使用されるメトリックは、最小ホップカウントと呼ばれる。２つのノード間における様々なパスが比較され、離散リンク、リピータ、ルータ、及び／又はゲートウェイの数がカウントされ、パス毎のホップの数を生じさせる。ホップの数が最小となる所与のパスが、２つのノードを接続するための最適なパスとして選択される。第１のノードが２つ以上のピアノードとの間で通信する選択肢を有する場合、ピアノードのうち最小数のホップを使用して到達され得る１つを選択してもよい。故に、最小ホップカウントを使用して２つのノード間における複数のパスのうちの１つを選択してもよく、又は複数のピアノードのうちの１つを選択してもよい。
【０００７】
ノードが異なる能力を有する環境において、ホップカウントのルーティングは適切ではないことが示されている。例えば“A  High-Throughput  Path  Metric  for  Multi-Hop  Wireless  Routing”（D.S.J.  De  Couto  et  al.,  M.I.T.  Computer  Science  and  Artificial  Intelligence  Laboratory,  International  Conference  on  Mobile  Computing  and  Networking,  San  Diego  CA,  September  2003）において、最小ホップカウントのルーティング技術は、ある環境において貧弱な性能を有することを著者は実証している。彼らは、２つのノード間に配置されるリンクの前方及び後方への配信比率（forward  and  reverse  delivery  ratio）を使用して算出される期待される送信カウントに基づいて、別のメトリックを提案している。その一方、“Comparison  of  Routing  Metrics  for  Static  Multi-Hop  Wireless  Networks”（R.Draves  et  al.,  Microsoft  Research,  Proceedings  of  the  2004  conference  on  Applications,  technologies,  architectures,  and  protocols  for  computer  communications,  Portland  OR,  August-September  2004）の他の著者は、メッセージの送信者が移動体である場合、ホップカウントのメトリックは他のリンク品質（link-quality）のメトリックよりも優れた性能を有することを主張している。
【０００８】
それにも関らず、ホップカウント又はより高度なメトリックにより最善のルーティングパスを決定する先行技術の方法は、ノードにはトラフィック処理能力が非常に高いものもあれば、非常に低いものもあり得るという事実を考慮に入れていない。ノードがネットワークのキャパシティを最適に使用できるように、その個々の処理キャパシティに関するメトリック情報をノード間において交換することに関する問題は、キャパシティの限界又はノード自身の現在の負荷を考慮に入れていないノード間の通信手段のみに基づくノードの調整によっては解決されない。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
通信するノードが、そのピアノードの現在の処理能力に関する正確で最新の情報を取得できるようにするための手段を有することは明らかに利点があるであろう。そのため、本発明の広範な目的は、１つのノードの処理キャパシティに関するメトリック情報をノード間において交換するための方法及びノードを提供することである。
【課題を解決するための手段】
【００１０】
本発明の第１の観点は、ノードの処理キャパシティに関する情報を取得する方法を対象とする。上記方法は、上記ノードから第１のレートで受信される第１の信号を含む。上記ノードから第２のレートで第２の信号も受信される。上記第２のレートと上記第１のレートとの間の比率が算出される。上記比率のプリセット値との比較に基づいて上記ノードの上記処理キャパシティが決定される。
【００１１】
本発明の第２の観点は、ノードの処理キャパシティに関する情報を取得する上記方法の変形を対象とする。連続する第１の信号の各々は、前回の第１の信号のシーケンス番号に基づいて算出されるシーケンス番号を含む。最新の第１の信号の直後に第２の信号が受信される場合、それは上記最新の第１の信号のシーケンス番号に基づくシーケンス番号を含む。その後、次回の第１の信号の前に受信される連続する第２の信号の各々は、前回の第２の信号のシーケンス番号に基づくシーケンス番号を含む。上記最新の第１の信号の、又は上記前回の第２の信号の上記シーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号が算出される。上記期待されるシーケンス番号に等しくないシーケンス番号を含む上記次回の第２の信号を受信することにより、生じ得るキャパシティの問題が検出される。
【００１２】
本発明の第３の観点は、ノードの処理キャパシティに関する情報を発信する方法を対象とする。上記方法は、提供キャパシティ値を決定するステップをもって開始される。上記提供キャパシティ値は、上記ノードの通常の処理キャパシティを示すプリセット値以下である。上記ノードは、基本レートで周期的に第１の信号を送信する。上記ノードは、上記提供キャパシティ値を示す第２のレートで周期的に第２の信号も送信する
【００１３】
本発明の第４の観点は、自身の処理キャパシティに関する情報を発信するためのノードを対象とする。上記ノードは、プロセッサと、上記プロセッサの負荷レベルを示す負荷インジケータとを含む。１つ以上のインタフェースは、ピアノードに向けて信号を送信するよう構成される。制御ロジックは、第１のレートで第１の信号を送信するよう上記１つ以上のインタフェースに要求する。上記制御ロジックは、上記プロセッサの上記負荷レベルを読み取り、及び上記負荷レベルの上記ノードの処理キャパシティの最大量との比較に基づいて第２のレートを算出する。上記制御ロジックは、上記第２のレートで第２の信号を送信するよう上記１つ以上のインタフェースに要求する。
【００１４】
本発明の第５の観点は、ピアノードの処理キャパシティに関する情報を取得するためのノードを対象とする。上記ノードは、上記ピアノードから信号を受信する１つ以上のインタフェースを含む。上記ノードは、制御ロジックも含む。上記制御ロジックは、上記１つ以上のインタフェースから第１の信号を複数回受信する。それは、上記第１の信号の第１のレートを決定する。上記制御ロジックはまた、上記１つ以上のインタフェースから第２の信号を複数回受信し、及び上記第２の信号の第２のレートを決定する。上記制御ロジックは、それから上記第２及び第１のレートの間の比率を算出し、並びに上記比率に基づく上記ピアノードの処理キャパシティをピアテーブルに記憶する
【図面の簡単な説明】
【００１５】
ここで本発明のより詳細な理解のため、さらなる目的及びその利点について、次の添付の図面と併せて、以下で説明する。
【００１６】
【図１】ノードの処理キャパシティに関する情報を発信（propagate）する一例となる方法を示す。
【図２】本発明の他の観点に従って、ピアノードにおいて対象ノード（node  of  interest）の処理キャパシティに関する情報を取得する一例となる方法を示す。
【図３】本発明の方法の追加的観点のステップを示す。
【図４】対象ノードの処理キャパシティを決定する処理においてより精度を上げるためのいくつかの例となる観点を示す。
【図５】本発明の観点に係る一例となるノードを示す。
【図６】本発明のいくつかの観点に係る一例となるピアテーブルを示す。
【発明を実施するための形態】
【００１７】
本発明の革新的な教示を、例となる様々な使用及び好適な実施形態の観点を特に参照して説明する。一方、この実施形態が本発明の革新的な教示の多くの有利な使用のうち数例しか提供していないことは、理解されるべきである。概して、本アプリケーションの本明細書における記述は、本発明の主張される様々な観点のいずれをも必ずしも限定しない。さらにいくつかの記述は、発明の特徴のいくつかに適用してもよく、他には適用しなくてもよい。図の説明において、同様の番号は本発明の同様の要素を表す。
【００１８】
本発明は、１つのノードの処理キャパシティに関するメトリック情報をノード間において交換するための方法及びノードを提供する。ノードのピアは、このメトリック情報を使用して、例えばネットワークの全体キャパシティをより良好に使用するよう、そのルーティングテーブルを調節することができる。対象処理ノードは、例えば１０秒毎といった定期的な間隔でＨＥＬＬＯメッセージをブロードキャストする。その後処理ノードは、例えば毎秒１回といったより高いレートでＡＬＩＶＥメッセージをブロードキャストする。ピアノードは、ＡＬＩＶＥ及びＨＥＬＬＯメッセージの間の比率を計算し、現在の例では１０：１となる。ＨＥＬＬＯメッセージは一定のレートで送信される。処理ノードが高い負荷若しくは輻輳を経験している場合、又は何らかの理由でノードにかかるトラフィックの負荷を削減することが望まれている場合、処理ノードはＡＬＩＶＥメッセージをいくらか遅れさせてもよい。処理ノードがダウンしている場合、又は処理ノード及びピアノードのインタフェースの間のパスがダウンしている場合、比率は無限大に近付く。
【００１９】
ピアノードは、比率を使用してそのルーティングテーブルを調節してもよく、それは例えば１より大きい比率を示す処理ノードに向けてのトラフィックの送信を削減し又は回避することによる。いかなる数のピアノードの間においても、ノードのいくつか又は全てを本発明の文脈において対象ノードと考えてもよく、いずれのピアも他のピアの処理キャパシティに関する情報を受信する必要があり得る。そのようなものとして、第１のノードは第２のノードから周期的なＨＥＬＬＯ及びＡＬＩＶＥメッセージを受信する一方、それはまた同時に自身の周期的なＨＥＬＬＯ及びＡＬＩＶＥメッセージを当該第２のノードに向けて送信し得る。
【００２０】
本発明の文脈において、プロセッサを含み、及びピア要素（peer  element）との間で通信するための手段を有する任意の計算要素（computing  element）をノードは含み得る。本発明を実装し得るノードの例は、コンピュータ内部のコプロセッサ、ルータ、サーバ、スイッチ等を含む。ピア要素は、例えば同一コンピュータ上の２つのコプロセッサであってもよいという点において互いに類似する要素であってもよく、又は例えばピアとしてのルータを有するサーバ若しくはピアとしての無線基地局を有するセルラ移動体の交換局を含むという点において互いに類似しない要素であってもよい。
【００２１】
ここで図面を参照すると、図１は、本発明のいくつかの観点に従って、ノードの処理キャパシティに関する情報を発信する一例となる方法を示している。シーケンス１００のステップは対象ノードにおいて実装されてもよく、当該ノードは例えば通常の又は名目の（nominal）処理キャパシティを有し、ピアノードからの代わりにいくつかの機能の処理を実行するという要求を処理してもよく、及びときどきその処理負荷が予め決定された限界に到達しつつあることを検出してもよい。ステップ１１０において、対象ノードは提供キャパシティ値（ＯＣ）を決定する。提供キャパシティ値は、対象ノードがピアノードに提供し得る処理の最大量を表すプリセット値を超えることはない。対象ノードは、様々なやり方で提供キャパシティを決定し得る。ある実施形態においては、プロセッサの負荷がプリセットの限界の範囲内にとどまる限り、提供キャパシティは名目上の値であるとされてよく、例えばプロセッサの負荷が７０パーセント未満であれば、名目の提供キャパシティが導かれ得る。またある実施形態においては、提供キャパシティはプロセッサの負荷の線形表現であってもよく、例えばプロセッサの負荷が１０パーセントであるときには提供キャパシティは９０パーセントとなり、又はプロセッサの負荷が６０パーセントであるときには提供キャパシティは４０パーセントとなる。提供キャパシティは、処理の要求で起こり得る急上昇からそのノードを保護するため、対象ノードの実際の処理キャパシティよりも低い値を表してもよい。実際の処理キャパシティと提供キャパシティとの間の非線形な関係を含む他の変化も、本発明から逸脱することなく使用されてもよい。
【００２２】
ステップ１２０において、対象ノードはノードの１つ以上のインタフェース上で第１の信号、例えばＨＥＬＬＯメッセージを送信する。ＨＥＬＬＯメッセージは、対象ノードのＩＤ（Identity）を好適に含むが、１つの対象ノードしかその処理キャパシティに関する情報を発信しない場合には当該ＩＤは省略されてもよい。ＨＥＬＬＯメッセージは、対象ノードの任意の数のピアノードに向けて送信され、対象ノードのハートビートとして使用される。以下に詳述されるように、シーケンス１００は、好適に一定のレートである第１のレート、又は基本レートでＨＥＬＬＯメッセージが確実に送信されるようにする手法で継続的に繰り返される。その後対象ノードは、ステップ１４０と１５０と１６０とを含むループ１３０において、複数の第２の信号、例えばＡＬＩＶＥメッセージを送信する。ＡＬＩＶＥメッセージも、対象ノードのＩＤを好適に含む。ステップ１５０においてＡＬＩＶＥメッセージは送信され、対象ノードの同じインタフェース上で全てのピアノードに向けても送信される。提供キャパシティがない場合（ＯＣは０に等しい）には、もちろんステップ１５０においてＡＬＩＶＥ信号は送信されない。ステップ１４０と１６０とにより制御されるループ１３０における繰り返しは、各ＨＥＬＬＯメッセージに続いてＡＬＩＶＥメッセージが確実にＯＣの回数（OC  times）送信されるようにする。その結果、ＡＬＩＶＥメッセージは、提供キャパシティ値の関数である第２のレートで送信される。例えば、ＡＬＩＶＥメッセージのレートは、提供キャパシティ値により乗じられる基本レートに等しくてもよい。ループ１３０が完了すると、シーケンス１００は代わりにステップ１１０又は１２０において継続してもよい。ある実施形態においては、毎回ＨＥＬＬＯメッセージを送信する前に一度、提供キャパシティ値がステップ１１０において決定され得る。またある実施形態においては、対象ノード又はピアノードのアプリケーションに応じて、より少ない頻度で提供キャパシティ値がステップ１１０において決定され得る。シーケンス１００と同等の、第２のレートが提供キャパシティと関連している他のシーケンスを使用して、第１及び第２のレートでＨＥＬＬＯ及びＡＬＩＶＥメッセージを送信してもよい。例えば、ＨＥＬＬＯメッセージを送信後、ＡＬＩＶＥメッセージの第１のインスタンスの前に、提供キャパシティが算出されてもよい。
【００２３】
ＨＥＬＬＯメッセージを送信する基本レートが一定となるように、シーケンス１００は一定のレートで好適に実行される。ピアノードが対象ノードの処理キャパシティをＨＥＬＬＯ及びＡＬＩＶＥメッセージのレートを比較することにより評価できるようにする手段として、ＡＬＩＶＥメッセージのレートは可変である。基本レートがいくらか変化する実施形態において、ピアノードは毎回のＨＥＬＬＯメッセージに続いて受信されるＡＬＩＶＥメッセージの数を比較することによりやはり対象ノードの処理キャパシティを評価し得る。一方、基本レートが実質的に一定である場合、ピアノードは長期間にわたるＡＬＩＶＥメッセージのレートをＨＥＬＬＯメッセージの固定された基本レートと比較することにより、対象ノードの処理キャパシティの算出結果（calculations）を有利に平均化してもよい。
【００２４】
ＨＥＬＬＯ及びＡＬＩＶＥメッセージの周期性は、それらメッセージを送信し及び受信する様々なノードによりサービス提供されるアプリケーションに従って、ノードの性質に従って、又はノードが接続されている手法に従って、決定され得る。例えば同一のイーサネットリンクに、又は処理ラック（processing  rack）内の同一のバックプレーン上で接続されることにより例えば対象ノードとそのピアノードとがＩＳＯレイヤ２レベルでリンクされる場合、ＨＥＬＬＯメッセージは例えば毎秒１回のレートで送信されてもよく、ＡＬＩＶＥメッセージは、処理キャパシティが名目的であるときには毎秒数回までのレートで送信されてもよい。ノードがＩＳＯレイヤ３レベルで接続される場合、並びにＨＥＬＬＯ及びＡＬＩＶＥメッセージがＩＰパケット又はＡＴＭフレームとして送信される必要がある場合、ＨＥＬＬＯメッセージのレートは数秒毎に１回であってもよく、一方ＡＬＩＶＥメッセージのレートは、処理キャパシティが名目的であるときには毎秒１回のオーダであってもよい。１ＧＨｚオーダの処理クロックのスピードを有する同一のパーソナルコンピュータの２つ以上のコプロセッサは、毎ミリ秒ほどのオーダでＨＥＬＬＯ及びＡＬＩＶＥメッセージを送信し得る。あるアプリケーションにおいては、メッセージが送信されるレートはさらにもっと高い又は低くてもよい。
【００２５】
図１が対象ノードの処理キャパシティに関する情報を発信する一例となる方法を示す一方、図２は、本発明の他の観点に従って、ピアノードにおいて対象ノードの処理キャパシティに関する情報を取得する一例となる方法を示している。シーケンス２００のステップは、例えば対象ノードのピアノードにおいて実装されてもよい。これらのステップは、ピアノードにおいて継続的な手法で好適に実行されるが、不定期間隔で、例えばピアノードが対象ノードの処理キャパシティを評価する必要があるときに実行されてもよい。ピアノードが次回のイベントが起こるのを待っているときに、ステップ２１０において方法が開始する。次回のイベントは、ステップ２１５において第１のタイプの信号を受信することであってもよく、当該第１の信号は、例えば対象ノードにより送信されるＨＥＬＬＯメッセージである。ステップ２２０においてピアノードは第１の信号の受信の時間を記憶する（note）。ステップ２２５において、ピアノードはさらに進むための十分なデータが受信されているか否かを判定する。第１の信号が１回しか受信されていない場合、又はシーケンス２００が再開されてから１回しか受信されていない場合、データは不十分であるとみなされ、次回のイベントが期待されるステップ２１０へ処理は戻る。そうではなく、ステップ２１５において第１の信号が既に少なくとも２回は受信されている場合、ステップ２２５においてデータは十分であるとみなされ、第１の信号の到着レートが算出される次のステップ２３０へ進む。第１の信号が既に複数のインスタンスにおいて受信されている場合、ピアノードは全てのこれらインスタンスをカバーする時間にわたって第１の到着レートを任意に平均化してもよく、又は単純に第１の信号の最後の２つのインスタンスに基づいて到着レートを考慮してもよい。第１の到着レートは、対象ノードの処理キャパシティを評価するための基礎として使用されることになるため、原則として一定で稀にしか変化しない。一方、対象ノード又は対象ノードとピアノードとの間の接続リンクが、ダウンしているか、再起動しているか、又はそうでなければそれらの通常の機能を担うことができない場合には、第１の到着レートは変化する可能性がある。ステップ２５５においてシーケンスは継続し、それについては以下で詳述される。
【００２６】
ステップ２１０においてピアノードが待っているときに起こる別の次回のイベントは、ステップ２３５において第２のタイプの信号を受信することであってもよく、当該第２の信号は、例えば対象ノードにより送信されるＡＬＩＶＥメッセージである。ステップ２４０においてピアノードは第２の信号の受信の時間を記憶する。ステップ２４５において、ピアノードはさらに進むための十分なデータが受信されているか否かを判定する。第２の信号が１回しか受信されていない場合、シーケンス２００が再開されてから１回しか受信されていない場合、又は設定可能な値よりも少ない数のインスタンスにおいてしか受信されていない場合、データは不十分であるとみなされ、次回のイベントが期待されるステップ２１０に処理は戻る。そうではなく、ステップ２３５において第２の信号が既に少なくとも２回受信されている場合、及び好適には第２の信号が設定可能な値に少なくとも等しい回数受信されている場合、ステップ２４５においてデータは十分であるとみなされ、第２の信号の到着レートが算出される次のステップ２５０へ進む。ピアノードは、そのような信号の数をカバーする時間にわたって第２の到着レートを好適に平均してもよい。好適な実施形態において、最後の第１の信号が受信されてからの期間にわたる第２の信号の到着レートが算出される。第２の到着レートは、対象ノードの現在の処理キャパシティの指標として使用されることになるため、変化してもよい。ステップ２５０における算出に続いて、ステップ２５５においてシーケンスは継続する。
【００２７】
ステップ２３０又はステップ２５０のいずれかに続き得るステップ２５５において、第１及び第２の信号の到着レートの比率が算出される。第２の信号は、第１の信号と比べてより高い到着レートを通常有していると期待されるため、好適な実施形態は通常の場合において、第２の到着レートを第１の到着レートで除して、１よりも大きい比率を取得する。当業者は、第１のレートの比率を第２のレートで除する別の実施形態が同等の結果をもたらすことを容易に観察するであろう。もちろん、ステップ２５５において、第１及び第２の到着レートのうちの１つしかステップ２３０及び２５０において算出されていない場合、結果として生じる比率はゼロ又は無限大であり得る。そのような結果は、シーケンス２００の文脈において非論理的ではなく、対象ノードの処理キャパシティに関する情報を取得する際に実際に使用され得る。ステップ２６０において、ステップ２５５において取得される比率がプリセット値と比較される。プリセット値は、ピアノードにおいて前もって設定され、対象ノードが通常の処理キャパシティのレベルである場合は第１及び第２の信号の到着レートの期待される比率に等しい。対象ノードの処理キャパシティは、比較から決定される。例えば、第１の信号の期待されるレートが毎１０秒に１回である場合、及び第２の信号の期待されるレートが毎秒１回である場合、プリセット値は１０に等しく、当該比率は第２の到着レートを第１の到着レートで除することにより取得される（比率が第１の到着レートを第２の到着レートで除することにより取得される実施形態においては、プリセット値は１０分の１（０．１）に等しくなる）。比率がプリセット値の１０よりも小さい場合、これは対象ノードが低い処理キャパシティを示すために第２の信号を送信する速度を落としていることを示す。比率がゼロである場合、対象ノードは使用可能な処理キャパシティを有していないとみなされる。
【００２８】
シーケンス２００がごく最近初期化されているとき、特別な場合が起こり得る。ステップ２３０において第１の到着レートが算出され、一方でステップ２４５において十分なデータが欠如していることにより第２の到着レートが算出できない場合、ステップ２５５においてゼロの比率が取得され得る。この場合ピアノードは、対象ノードが使用可能な処理キャパシティを有していないと好適にみなしてよい。対照的にステップ２５５において無限大の比率が取得されることは、第１の到着レートがまだ算出されていないことを示し得る。他の変形において、ステップ２２５及び２４５において十分なデータについて検証することなく、ステップ２３０及び２５０において第１及び第２の到着レートをそれぞれ算出することができる。所与のタイプの信号が１回しか受信されていない場合、この信号のタイプについての到着レートは極度に遅いとみなされ、またステップ２５５において極値の比率を生じさせるであろう。これらの場合のいずれにおいても、シーケンス２００の継続的な実行により、程なくステップ２２５及び２４５において十分なデータが利用可能となり、ステップ２６０において対象ノードの処理キャパシティを適切に決定できることを保証するであろう。
【００２９】
他の場合において、対象ノードに通信の問題があるためステップ２２５又は２４５若しくはその両方において十分なデータが取得されない可能性がある。これにより比率がゼロ又は無限大のいずれに等しくなるとしてもと、これはピアノードに対して対象ノードの処理キャパシティが利用可能でないことを示している。
【００３０】
図３は、本発明の方法の追加的観点のステップを示す。シーケンス３００は、図２のシーケンス２００と並行して実行されてもよい。特に、シーケンス３００は図２のステップ２６０に続いて開始してもよく、シーケンス２００の継続中の処理において対象ノードの処理キャパシティが再評価されるときはいつでも実行されてもよい。代わりにシーケンス３００は、不定期間隔で、第１及び第２の信号のレートよりも低いレートで周期的に、又はピアノードの特定の必要性に基づいて必要に応じて、実行されてもよい。
【００３１】
ステップ２６０において対象ノードの処理キャパシティが決定された後、ピアノードはさらなるアクションを取り得る。これらアクションのうちのいくつかは補完的であってもよく、ピアノードは、これらアクションのうちのいくつかを他のアクションとは独立してとってもよい。ピアノードは、比率における変化を監視することにより、対象ノードの処理キャパシティにおける変化を監視し得る。ステップ３１０において、ステップ２５５において取得される比率が、前もって記憶されている比率の値と比較される。ステップ３１５において、この比較の結果は３つの異なる値を有し得る。ステップ３１５における結果が比率の増加を示している場合、ピアノードはステップ３２０において、対象ノードの処理キャパシティが増加したことを記録（record）し、又は別の方法でメモリに記憶（take  note）する。ステップ３１５における結果が比率の減少を示している場合、ピアノードはステップ３２５において、ピアノードの処理キャパシティが減少したことを記録する。ステップ３１５における結果が比率が変化していないことを示している場合、特定のアクションは取られない。
【００３２】
ステップ３１０〜３２５が実行されるか否かに関わらず、ステップ３３０においてシーケンスは継続されてよく、ステップ２６０において決定された対象ノードの処理キャパシティは、予め決定された閾値と比較して評価される。処理キャパシティが閾値よりも低い場合、ステップ３３５においてピアノードはそのルーティングテーブルから対象ノードを削除してもよい。その結果、ピアノードは対象ノードに向けて信号、メッセージ又は要求を送信することを控えるであろう。もちろん、対象ノードのルーティングテーブルからの削除は、場合によってはトラフィック及びペイロードの交換にのみ適用可能であって、保守（maintenance）シグナリングには適用されなくてもよい。例えば、ピアノードは対象ノードに向けての自身の周期的なＨＥＬＬＯ及びＡＬＩＶＥ信号の送信を継続してもよい。その代わりに、ピアノードは、そのルーティングテーブルにおいて対象ノードに与えられるコストを、対象ノードに向けてより少ない数の信号、メッセージ又は要求が送信されることを保証するように、より高いコストに調整してもよい。ステップ３３０において、対象ノードの処理キャパシティが高く又は名目のレベルであるとみなされ得る。例えば、閾値を超える処理キャパシティのレベルは、高いとみなされ得る。代わりに、ステップ２５５において算出される比率がプリセット値に等しいとわかった場合にのみ、キャパシティは名目上の値であるとされてもよい。処理キャパシティを高い値又は名目上の値とするように決定するためのどのように精緻な基準を使用するとしても、ステップ３４０において、対象ノードは、ピアノードのルーティングテーブル内に追加され又は維持される。対象ノードの処理キャパシティが高いレベル又は名目のレベルにごく最近戻った場合、ノードはルーティングテーブルに追加される。その代わりに、処理キャパシティが高く又は名目上の値であるとされる場合、ルーティングテーブルにおいて対象ノードに与えられるコストは調整され得る。処理キャパシティがしばらくの間継続的に名目上の値である場合、ノードは既にルーティングテーブル内に存在しており、そこに維持され、ノードに与えられるコストは低い値に維持される。
【００３３】
図２のシーケンス２００に示されている方法は、対象ノードの処理キャパシティを決定する処理において精度を上げるための追加的観点を含み得る。第１及び第２の信号は、そのインスタンスの全てにおいて、シーケンス番号を伴って送信されてもよい。第１の信号が第１のインスタンスにおいて送信される場合、それは基本シーケンス番号を含む。第１のインスタンスにおいて送信される基本シーケンス番号の実際の値は、多くの実施形態において関連がない。それから第１の信号の次回のインスタンスは、式（１）に従ったシーケンス番号を伴う：
【００３４】
【数１】
2011507378.tif 000003
【００３５】
ここでＦ１は、第１の信号のシーケンス番号と前回の第１の信号のシーケンス番号との間の関係である。
【００３６】
最新の第１の信号の直後に送信される第２の信号の第１のインスタンスは、式（２）に従ったシーケンス番号を伴う：
【００３７】
【数２】
2011507378.tif 000004
【００３８】
ここでＦ２は、第２の信号のシーケンス番号と最新の第１の信号のシーケンス番号との間の関係である。
【００３９】
その後次回の第１の信号の前に送信される第２の信号の他のインスタンスは、式（３）に従ったシーケンス番号をそれぞれ伴う：
【００４０】
【数３】
2011507378.tif 000005
【００４１】
ここでＦ３は、第２の信号のシーケンス番号と前回の第２の信号のシーケンス番号との間の関係である。
【００４２】
これらの関数が一義的なシーケンスの計算を可能としている限り、及び対象ノードとピアノードとが同じ関数を使用している限り、第１及び第２の信号に伴われるシーケンス番号を計算するために、様々な関数Ｆ１、Ｆ２、及びＦ３の組が使用され得る。
【００４３】
関数Ｆ１、Ｆ２、及びＦ３を使用する単純な一例において、第１の信号の第１のインスタンスにおいて伴われる基本シーケンス番号は、ゼロに等しい。関数Ｆ１は、前回の第１の信号のシーケンス番号にプリセット値に等しい数を加算し、ここで例えばプリセット値は１０に等しい。関数Ｆ２は、最新の第１の信号のシーケンス番号に１を加算する。関数Ｆ３は、前回の第２の信号のシーケンス番号に１を加算する。この例において、第１の信号は第１のインスタンスにおいて、０に等しい基本シーケンス番号と共に送信される。一連の第２の信号は、それからＦ２を使用して算出される１に等しいシーケンス番号と共に、それからＦ３を使用して算出される２、３、・・・、１０に等しいシーケンス番号と共に送信される。それから第１の信号の次回のインスタンスは、Ｆ１を使用して算出される１０に等しいシーケンス番号を伴って送信される。
【００４４】
他の実施形態において、より複雑な関数が使用されてもよい。一例として、Ｆ２及びＦ３はシーケンス番号に作用する一方向性のハッシュ法の手続きを含んでもよく、一方Ｆ１は、同じ一方向性のハッシュ法をプリセット値に等しい回数シーケンス番号に作用させてもよい。
【００４５】
図４は、対象ノードの処理キャパシティを決定する処理においてより精度を上げるためのいくつかの例となる観点を示す。シーケンス４００及び４５０は、図２のシーケンス２００のステップのうちのいくつかと並行してピアノードにおいて動作し、シーケンス２００のオプションとしてのサブルーチンとみなされ得る。サブルーチン４００では、図２の前述の説明において示されているように、ステップ２１５においてピアノードにより第１の信号が受信される。第１の信号は、任意にシーケンス番号を含み得る。そうである場合、ステップ４１７において次回の第２の信号の期待されるシーケンス番号が、関数Ｆ２を使用して算出される。ステップ４１９において、サブルーチンは図２におけるステップ２１５に続くステップ、即ちステップ２２０に戻る。サブルーチン４５０では、図２に示されているように、ステップ２３５において第２の信号がピアノードにより受信される。第２の信号もシーケンス番号を含み得る。ステップ４５２において、第２の信号に含まれるシーケンス番号が期待されるシーケンス番号に合致するか否かがチェックされる。ある実施形態においては、受信されるシーケンス番号と期待されるシーケンス番号とが等しい場合に、合致しているとされる。またある実施形態においては、受信される信号の番号が期待される信号の番号以上である場合に、合致しているとされ得る。合致している場合には、ステップ４５４において次回の第２の信号に適用可能な別の期待される信号の番号が算出され、ステップ４５９においてサブルーチンは図２におけるステップ２３５に続くステップ、即ちステップ２４０に戻る。ステップ４５２において第２の信号に含まれるシーケンス番号が期待される信号の番号に合致しないとみなされた場合、ピアノードはこの第２の信号又は別の第２の信号が失われ若しくは遅延していることを検出する。ステップ４５６において、ピアノードは、キャパシティの問題が起こっていることを検出する。キャパシティの問題は、対象ノードにおける処理キャパシティの問題、又はピアノードと対象ノードとの間の通信リンク上の問題であり得る。ステップ４５８において、ピアノードは図２のさらなる処理において無視されるべき第２の信号にマークを付ける。それからサブルーチンは、ステップ４５９において図２のシーケンスに戻る。
【００４６】
ある実施形態においては、類似のロジックを使用して次回の第１の信号の期待されるシーケンス番号が算出され得る。同等の手法において、次回の第１の信号について期待されるシーケンス番号に合致しないシーケンス番号を含む次回の第１の信号を受信することは、対象ノードにおける問題又はピアノードと対象ノードとの間の通信リンク上における問題のいずれかを示すであろう。
【００４７】
図５は本発明のある観点に係る一例となるノードを示しており、ここで図５を参照しながら一例となるノードの構成を説明する。例となるノード５００は、自身の処理キャパシティに関する情報を発信することと、ピアノードの処理キャパシティに関する情報を取得することとの両方を可能とする特徴を含む。他の例となるノードは、これら特徴のいくつか、即ち処理キャパシティの情報の発信又は取得のいずれかのみを可能とすることを含み得ることは理解されるべきである。これら他の例となるノードは、それらが使用されるコンピューティングネットワークアーキテクチャの必要性に従って、例となるノード５００の特徴のサブセットを含んでもよい。
【００４８】
ノード５００は、メモリ５１０、プロセッサ５２０、プロセッサの負荷インジケータ５３０、クロック５４０、制御ロジック５５０、及び１つ以上のインタフェース５６０を含む。インタフェース５６０の各々は、１つの単独の装置として、又はシグナリング、メッセージ、及びデータを受信（入力）し及び送信（出力）するための異なる装置として実装されてもよい。ノードは、複数のピアノードに向けて接続されており；ピアノードに向けてノードを接続するための手段は、例えばあるピアノードに向けての接続はイーサネットリンク上にあってもよく、一方またあるピアノードに向けての接続は非同期転送モード（ＡＴＭ）リンク上にあってもよいというように、変わってもよい。そのためノード５００は、異なるタイプの複数のリンク上で接続するための複数のインタフェース５６０を含み得る。他の機能をさらに有し得るノードは、そのため当該技術分野において良く知られているようなより多くのコンポーネントを含んでもよい。ある実施形態においては、ノード５００は完全なシステム、例えばコンピュータである。またある実施形態においては、ノード５００は基本的に、例えばプロセッサ５２０、負荷インジケータ５３０、クロック５４０、及び制御ロジック５５０を含む単一の処理要素から成る。
【００４９】
メモリ５１０は、いくつかのその内容のために、例えばランダムアクセスメモリ（ＲＡＭ）を使用して実装されるテンポラリメモリであってもよい。いくつかの他の観点のために、それは好適に、電気的に消去することができ、再プログラミング可能であり、及び例えばフラッシュメモリ若しくはデータ記憶モジュールとして実装され得る、不揮発性メモリ又は持続性メモリである。メモリ５１０は、例えば図２のシーケンス２００におけるステップ２６０で使用されるノード５００において利用可能な処理の最大量を表すプリセット値、及び図３のシーケンス３００におけるステップ３３０において使用される予め決定された閾値を含むいくつかの定数５１２を記憶する。
【００５０】
メモリ５１０はまた、ピアノードのテーブル６００をこれらピアノードの処理キャパシティに関する情報を記憶するために記憶してもよい。図６は、本発明のいくつかの観点に係る一例となるピアテーブル６００を示す。テーブル６００は、複数の行６２０〜６２８を含み、これらはヘッダ行である第１の行６２０を除いて、テーブルを有するノードのピアに関する。テーブルは、ピアのリストにおけるノードの処理キャパシティに関する情報を取得し及び記憶するためにノードにより使用される。ピアテーブル６００は、複数の列６０２２〜６１６を含み、これらのうちのいくつかはオプションである。第１の列６０２は、ピアのＩＤ  Ｐｎを含む。第２の列は、第１の信号、例えばＨＥＬＬＯ信号を受信した最新のインスタンスの時間Ｔ１ｎを記憶する。第１の信号の新たなインスタンスが受信されるたびに、受信の時間を前回の受信の時間Ｔ１ｎと比較して、列６０６に記憶される第１の信号のレートＲ１ｎを計算する。列６０４において新たな受信の時間は前回の値を上書きする。もちろん、他の同等の実施形態を使用して第１の信号の受信のレートを追跡することもできる。ある実施形態においては、列６０６における第１の信号のレートは、単純に第１の信号の全ての受信で上書きされる。またある実施形態においては、列６０６の第１の信号のレートＲ１ｎは、時間にわたって平均されてもよい。またある実施形態においては、列６０６に記憶するためのより正確なレートＲ１ｎを計算するために、列６０４において毎行１つのＴ１ｎの値を記憶するのではなく、第１の信号の時間の値の配列を記憶することもできる。列６０８及び６１０は同様に、第２の信号、例えばＡＬＩＶＥ信号の受信の時間Ｔ２ｎ及びレートＲ２ｎをそれぞれ記憶する。列６１２において、２つの信号のレートの比率が各ピアについて記憶される。例となるピアテーブル６００において、比率は第２の信号のレートＲ２ｎを第１の信号のレートＲ１ｎで除することにより取得され、１０となる比率は名目のレートであることを示す。任意的な列６１４は、所与の列のピアについてのルーティングのコストを記憶する。コストは数値であり得、低いコストはピアへ向けてのルーティングが好適であることを示す。それは単純に高いか低いかの表示でもあり得る。コストは、ピアへ向かうルーティングが許可されるか否かを示す２値表示であってもよい。ある実施形態においては、ルーティングのコストは、ピアテーブル６００とは異なる別のルーティングテーブルにおいて記憶されてもよい。別の任意的な列６１６は、次回の第２の信号についての期待されるシーケンス番号（Ｅ−ＳＱＮ）Ｅｎを記憶する。ピアテーブル６００は、ノードのピアに関する追加的情報を維持するために他の列（図示しない）も含んでもよい。
【００５１】
ピアテーブル６００において、行６２２〜６２８上の例となるピアＰ１〜Ｐ４は、これらピアの処理キャパシティに関連する様々な状況を示している。行６２２上において、１０に等しい比率により示されるように、Ｐ１の処理キャパシティはその名目のレベルである。トラフィックはＰ１に向けてルーティングされてよく、ルーティングのコストは低い。行６２４上において、Ｐ２から第１の信号は少なくとも１回受信されたが、第２の信号はまだ受信されていない。Ｐ２について第２の信号のレートは算出されなくてもよく、従って比率はゼロに等しい。トラフィックはＰ２に向けてルーティングされ得ず、ルーティングのコストは高い。行６２６上において、Ｐ３から第２の信号しか受信されていない。最初の第２の信号のレートＲ１３は設定されていないため、第１の信号のレートについての空値でレートＲ２３を割った比率は無限大という結果を生じさせる。これもまたルーティングの問題を示しているため、ルーティングのコストは高い。行６２８上において、Ｐ４についての比率は７に等しく、これは名目の値である１０よりも小さい。Ｐ４の処理キャパシティはいくらか低下しており、そのため中程度のルーティングのコストが割り当てられる。
【００５２】
図６においてテーブルの形でピアテーブルの内容が表されているが、その内容がこれに限定されないことは留意されるべきである。ピアテーブルは、関連のデータベース、ハードコードされたコンポーネント、マイクロプロセッサ、プログラミングライブラリ等から構成され得る。
【００５３】
プロセッサ５２０は、ノード５２０において実装される特徴に係るタスクを実行する。負荷インジケータ５３０は、プロセッサ５２０上の負荷レベルを継続的に反映する。クロック５４０は、制御ロジック５５０におけるシーケンスを周期的に開始する。各シーケンスの始めに、制御ロジック５５０は負荷インジケータ５３０からプロセッサの負荷を読み取る。制御ロジック５５０は、メモリ５１０における定数５１２からプリセット値を読み取る。制御ロック５５０は、第１の信号、例えばＨＥＬＬＯメッセージをシーケンス毎に１回送信するよう１つ以上のインタフェース５６０に要求する。制御ロジック５５０は、第１の信号に含めるためのシーケンス番号を任意に生成してもよく、１回のシーケンスの間に送信される第１の信号の１つのインスタンスのシーケンス番号は、先行するシーケンスにおける第１の信号のシーケンス番号に基づいて好適に生成される。それから制御ロジック５５０は、プロセッサの負荷及びプリセット値からシーケンスの間に送信されるべき第２の信号、例えばＡＬＩＶＥメッセージの数Ｎを決定する。プロセッサの負荷が低い場合、数Ｎはプリセット値に等しく設定される。プロセッサの負荷が高いとみなされるべきか低いとみなされるべきかの判定は、メモリ５１０に記憶されているいくつかの定数５１２に依存し得る。制御ロジック５５０は、ＡＬＩＶＥメッセージに含まれるべきシーケンス番号を算出してもよく、連続するシーケンス番号の各々は、前回送信された信号のシーケンス番号に基づいて好適に算出される。制御ロジック５５０は、決定された数Ｎの第２の信号を、第１の信号のレートのＮ倍に相当するレートで送信するよう１つ以上のインタフェース５６０に要求する。
【００５４】
インタフェース５６０のうちの１つは、現在自身の処理キャパシティに関する情報を発信している対象のピアノードＰｎから一連の第１及び第２の信号を受信し得る。当該インタフェースは、制御ロジック５５０に情報を提供する。制御ロジック５５０は、クロック５４０からタイミング情報を読み取ることにより第１又は第２の信号の受信の時間を読み取り、及びピアテーブル６００においてピアノードのＩＤ  Ｐｎを含む行上に、第１の信号の時間Ｔ１ｎ又は第２の信号の時間Ｔ２ｎを記憶する。第１又は第２の信号が十分な回数受信されている限り、プロセッサは信号のレートＲ１ｎとＲ２ｎとを算出し、及びピアノードＰｎについてそれらを記憶する。両方のレートがピアノードＰｎについて算出されると、制御ロジック５５０はピアノードＰｎの処理キャパシティを示す比率を計算し、及びテーブルにおいて列６１２にそれを記憶する。制御ロジック５５０は、ピアノードＰｎについてのルーティングのコストの値を任意的に記憶してもよい。第１及び第２の信号は、シーケンス番号を含んでもよい。制御ロジック５５０は、ピアノードＰｎから受信される次回の第２の信号に適用可能な期待されるシーケンス番号（Ｅ−ＳＱＮ）を計算し、及びそれをＥｎとして記憶する。次回の第２の信号がピアノードＰｎから受信される際、当該次回の第２の信号に含まれるシーケンス番号がＥｎに適合しない場合、制御ロジック５５０は当該第２の信号を無視してもよい。
【００５５】
本発明の方法及びノードの好適な実施形態のいくつかの観点が添付の図面において示され、及び前述の詳細な説明において説明されているが、本発明は開示される実施形態に限定されず、次の特許請求の範囲により説明され及び定義される本発明の精神から逸脱することなく多数の再構成、変更、及び置換が可能であることは理解されるであろう。
【図１】
2011507378.tif 000006
【図２】
2011507378.tif 000007
【図３】
2011507378.tif 000008
【図４】
2011507378.tif 000009
【図５】
2011507378.tif 000010
【図６】
2011507378.tif 000011
【手続補正書】
【提出日】平成21年10月13日(2009.10.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノードの処理キャパシティに関する情報を取得する方法であって：
前記ノードから第１のレートで第１の信号を受信するステップと；
前記ノードから第２のレートで第２の信号を受信するステップと；
前記第２のレートと前記第１のレートとの間の比率を算出するステップと；
前記比率のプリセット値との比較に基づいて前記ノードの前記処理キャパシティを決定するステップと；
を含む方法。
【請求項２】
前記第１のレートは一定であり；及び
前記第２のレートは可変である；
請求項１に記載の方法。
【請求項３】
前記プリセット値は、前記ノードが通常の処理キャパシティを有する場合の前記第２及び第１のレートの間の比率に等しい、
請求項１に記載の方法。
【請求項４】
前記ノードの前記処理キャパシティを決定する前記ステップに基づいてルーティングテーブルを更新するステップと；
前記ノードの前記処理キャパシティが低い場合に、前記ノードに向けてメッセージを送信することを控えるステップと；
をさらに含む、請求項１に記載の方法。
【請求項５】
前記比率における変化を監視するステップと；
前記比率が変化する場合に、前記ノードの処理キャパシティの変化を検出するステップと；
をさらに含む、請求項１に記載の方法。
【請求項６】
前記第２のレートの減少は、前記処理キャパシティの低下を示す、
請求項５に記載の方法。
【請求項７】
連続する第１の信号の各々は、前回の第１の信号のシーケンス番号に基づいて算出されるシーケンス番号を含み；
最新の第１の信号の直後に受信される第２の信号は、前記最新の第１の信号のシーケンス番号に基づくシーケンス番号を含み；及び
次回の第１の信号の前に受信される連続する第２の信号の各々は、前回の第２の信号のシーケンス番号に基づくシーケンス番号を含む、
請求項１に記載の方法。
【請求項８】
連続する第１の信号の各々における前記シーケンス番号は、前記前回の第１の信号の前記シーケンス番号に前記プリセット値を加えたものに等しく；
前記最新の第１の信号の直後に受信される前記第２の信号における前記シーケンス番号は、前記最新の第１の信号の前記シーケンス番号に１を加えたものに等しく；及び
前記次回の第１の信号の前に受信される連続する第２の信号の各々における前記シーケンス番号は、前記前回の第２の信号の前記シーケンス番号に１を加えたものに等しい、
請求項７に記載の方法。
【請求項９】
前記最新の第１の信号の前記シーケンス番号に基づいて、又は前記前回の第２の信号の前記シーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号を算出するステップと；
前記期待されるシーケンス番号に等しくないシーケンス番号を含む前記次回の第２の信号を受信することにより、キャパシティの問題を検出するステップと；
をさらに含む、請求項７に記載の方法。
【請求項１０】
前記最新の第１の信号の前記シーケンス番号に基づいて、又は前記前回の第２の信号の前記シーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号を算出するステップ、をさらに含み；
前記第２のレートと前記第１のレートとの間の前記比率を算出することは、前記期待されるシーケンス番号に合致しないシーケンス番号を含む所与の第２の信号を無視することを含む、
請求項７に記載の方法。
【請求項１１】
ノードの処理キャパシティに関する情報を発信する方法であって：
前記ノードの実際の処理キャパシティであり、及び前記ノードの通常の処理キャパシティを示すプリセット値以下である提供キャパシティ値を決定するステップと；
前記ノードから基本レートで周期的に第１の信号を送信するステップと；
前記ノードから前記提供キャパシティ値を示す第２のレートで周期的に第２の信号を送信するステップと；
を含む方法。
【請求項１２】
前記ノードは複数のインタフェースを含み；
周期的な第１の信号の各々は全てのインタフェース上を送信され；及び
周期的な第２の信号の各々は全てのインタフェース上を送信される、
請求項１１に記載の方法。
【請求項１３】
前記第２のレートは、前記基本レートに前記提供キャパシティ値を乗じたものに等しい、
請求項１１に記載の方法。
【請求項１４】
前記提供キャパシティ値は、周期的に決定される、
請求項１１に記載の方法。
【請求項１５】
前記提供キャパシティ値は、前記ノードの実際の処理キャパシティに従って設定される、
請求項１１に記載の方法。
【請求項１６】
前記提供キャパシティ値は、前記ノードの実際の処理キャパシティから負荷制限値（load  limiting  value）を引いたものに従って設定される、
請求項１１に記載の方法。
【請求項１７】
自身の処理キャパシティに関する情報を発信するためのノードであって：
プロセッサと；
前記プロセッサの負荷レベルを示すよう構成される負荷インジケータと；
ピアノードに向けて信号を送信するよう構成される１つ以上のインタフェースと；
前記プロセッサの前記負荷レベルを読み取り、並びにそこから前記ノードの実際の処理キャパシティであり、及び前記ノードの通常の処理キャパシティを示すプリセット値以下である提供キャパシティを決定し；
第１のレートで第１の信号を送信するよう前記１つ以上のインタフェースに要求し；
前記負荷レベルと前記ノードの処理キャパシティの最大量との比較に基づいて第２のレートを算出し；並びに
前記第２のレートで第２の信号を送信するよう前記１つ以上のインタフェースに要求する；
よう構成される、制御ロジックと；
を含むノード。
【請求項１８】
前記第１のレートで前記制御ロジックのシーケンスを開始するよう構成されるクロック
をさらに含む、請求項１７に記載のノード。
【請求項１９】
前記負荷レベルと処理の前記最大量との比較に基づいて第２のレートを算出することは、前記負荷レベルが低い場合に前記第２のレートを最大値に設定することを含む、
請求項１７に記載のノード。
【請求項２０】
連続する第１の信号の各々は、前回の第１の信号のシーケンス番号に基づいて算出されるシーケンス番号を含み；
最新の第１の信号の直後に送信される第２の信号は、前記最新の第１の信号のシーケンス番号に基づくシーケンス番号を含み；及び
次回の第１の信号の前に送信される連続する第２の信号の各々は、前回の第２の信号のシーケンス番号に基づくシーケンス番号を含む、
請求項１７に記載のノード。
【請求項２１】
ピアノードの処理キャパシティに関する情報を取得するためのノードであって：
前記ピアノードから信号を受信するよう構成される１つ以上のインタフェースと；
前記１つ以上のインタフェースから第１の信号を複数回受信し；
前記第１の信号の第１のレートを決定し；
前記１つ以上のインタフェースから第２の信号を複数回受信し；
前記第２の信号の第２のレートを決定し；
前記第２及び第１のレートの間の比率を算出し；並びに
前記比率に基づく前記ピアノードの処理キャパシティをピアテーブルに記憶する；
よう構成される、制御ロジックと；
を含むノード。
【請求項２２】
クロックをさらに含み、並びに
前記制御ロジックは、前記クロックからのタイミング情報を使用して前記第１及び第２のレートを決定し、並びに前記第１及び第２のレートを前記ピアテーブルに記憶する；
請求項２１に記載のノード。
【請求項２３】
前記第１及び第２の信号は、シーケンス番号を含み；
前記制御ロジックは、最新の第１の信号のシーケンス番号に基づいて、又は前回の第２の信号のシーケンス番号に基づいて、次回の第２の信号の期待されるシーケンス番号を計算するようさらに構成され；並びに
前記制御ロジックは、前記期待されるシーケンス番号を前記ピアテーブルに記憶するようさらに構成される；
請求項２１に記載のノード。
【請求項２４】
前記制御ロジックは、前記期待されるシーケンス番号に等しくないシーケンス番号を含む次回の第２の信号を受信することにより、キャパシティの問題を検出するようさらに構成される、
請求項２３に記載のノード。
【請求項２５】
前記第２及び第１のレートの間の比率を算出することは、前記期待されるシーケンス番号に合致しないシーケンス番号を含む所与の第２の信号を無視することを含む、
請求項２３に記載のノード。
【国際調査報告】
2011507378.tif 000012
2011507378.tif 000013