(57)【要約】  メッセージルーティングの方法、システム、装置、及びバックアップリソースを選択する方法、システム。メッセージルーティングの方法は、各ノードビジーインデックスを予め設定された間隔ごとに更新し、分散ハッシュテーブルアルゴリズムとノードビジーインデックスとに従って受信メッセージノードを選択し、選択された受信メッセージノードにメッセージを送信することを含む。メッセージルーティングのシステムは、送信ノード装置とルーティングノード装置とを含む。バックアップリソースを選択する方法は、状態発行ノードがマルチキャストグループ内の他のノードにノードビジーインデックスをブロードキャストし、バックアップリソース選択ノードが受信したノードビジーインデックスに従ってエージェントノードを選択することを含む。バックアップリソースを選択するシステムは、状態発行ノード装置とバックアップリソース選択ノード装置とを含む。参照ルーティングテーブル内のノードビジーインデックスに従って本発明の一例示的実施形態では受信メッセージノードを選択し、ノード間に分散させられる負荷を調整して、ネットワークの輻輳を防止する。
2010538552.tif 000002
【特許請求の範囲】
【請求項１】
ノードのビジーレベルを所定の間隔で更新し、
分散ハッシュテーブル（ＤＨＴ）アルゴリズムと前記ノードのビジーレベルとに従ってパケット受信ノードを選択し、前記選択されたパケット受信ノードにパケットを送信する、
ことを含む、パケットルーティングの方法。
【請求項２】
前記ノードのビジーレベルを所定の間隔で更新するステップは、
ルーティングテーブル内のノードに前記所定の間隔で状態レベル問い合わせ要求を送信し、
前記状態レベル問い合わせ要求を受信したノードが、ノードのビジー状態を確認し、該ビジー状態に従ってノードのビジーレベルを決定し、該ビジーレベルを運ぶ状態レベル問い合わせ応答を返し、
前記状態レベル問い合わせ応答を受信すると、前記状態レベル問い合わせ応答内で運ばれた前記ビジーレベルに従ってノードに対応するビジーレベルを更新する、
ことを含む、請求項１に記載の方法。
【請求項３】
前記ノードのビジー状態を確認し、該ビジー状態に従ってノードのビジーレベルを決定するステップは、
前記状態レベル問い合わせ要求を受信したノードが、前記所定の間隔内にローカルノードによって受信されたパケットの数を確認し、前記ノードのビジーレベルを、前記パケットの数、中央処理ユニット（ＣＰＵ）の状態、メモリサイズ、ネットワーク帯域幅、及びノードの意向のうちの少なくとも１つに従って決定する、
ことを含む、請求項２に記載の方法。
【請求項４】
前記ビジーレベルは、全てのパケットの処理が可能なビジーレベル１と、ノードが管理しているキー範囲内のパケットのみの処理が可能なビジーレベル２と、パケットが全く処理できない状態レベル３とを含む、請求項２又は３に記載の方法。
【請求項５】
前記状態レベル問い合わせ要求を受信したノードのビジーレベルがビジーレベル２である場合、前記状態レベル問い合わせ応答は、前記状態レベル問い合わせ要求を受信したノードが管理しているキー範囲を運び、
前記状態レベル問い合わせ要求を受信したノードのビジーレベルがビジーレベル３である場合、前記状態レベル問い合わせ応答は、前記状態レベル問い合わせ要求を受信したノードが管理しているキー範囲と、ノードのプロキシノードのキーとを運ぶ、請求項４に記載の方法。
【請求項６】
前記ＤＨＴアルゴリズムと前記ノードのビジーレベルとに従ってパケット受信ノードを選択し、前記選択されたパケット受信ノードにパケットを送信するステップは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップノードを探索し、前記次ホップノードのビジーレベルを判定し、前記ビジーレベルが２又は３である場合、パケットの宛先が、前記次ホップノードが管理するキー範囲内であるか否かを確認し、前記宛先が前記範囲内である場合、前記次ホップノードがビジーレベル２にあるならば、前記次ホップノードに前記パケットを送信し、又は、前記次ホップノードがビジーレベル３にあるならば、前記次ホップノードのプロキシノードに前記パケットを送信する、
ことを含む、請求項５に記載の方法。
【請求項７】
前記状態レベル問い合わせ要求はキープアライブメッセージであり、前記状態レベル問い合わせ応答はキープアライブ応答である、請求項２に記載の方法。
【請求項８】
前記ノードのビジーレベルを所定の間隔で更新するステップは、
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を前記所定の間隔で測定し、
前記パケットの数を、予めネゴシエーションされた最高閾値及び／又は中間閾値と比較し、
比較結果に従って、ノードのビジーレベルを更新する、
ことを含む、請求項１に記載の方法。
【請求項９】
前記ＤＨＴアルゴリズムと前記ノードのビジーレベルとに従ってパケット受信ノードを選択し、前記選択されたパケット受信ノードにパケットを送信するステップは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップノードを探索し、前記ローカルノードによって前記次ホップノードに送信されたパケットの数を測定し、前記パケットの数が前記中間閾値以上である場合、前記パケットの宛先が前記次ホップノードが管理するキー範囲内であるか否かを確認し、前記宛先が前記範囲内である場合、前記パケットの数が前記中間閾値と前記最高閾値との間であるならば、前記次ホップノードに前記パケットを送信し、又は、パケットの前記数が前記最高閾値以上であるならば、前記次ホップノードのプロキシノードに前記パケットを送信する、
ことを含む、請求項５に記載の方法。
【請求項１０】
ノードが管理するキー範囲が変更された場合、前記ノードが前記変更されたキー範囲を上流ノードに通知することを更に含む、請求項８に記載の方法。
【請求項１１】
ノードのビジーレベルを所定の間隔で更新し、分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、ルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたルーティングノードにパケットを送信するように適合された、送信ノードと、
前記送信ノードからの前記パケットを受信し、前記ＤＨＴアルゴリズムと、ローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、前記ルーティングノードと、
を備える、パケットルーティングのシステム。
【請求項１２】
前記送信ノードは、
状態レベル問い合わせ要求をローカルルーティングテーブル内のノードに前記所定の間隔で送信するように適合された、メッセージ送信モジュールと、
状態レベル問い合わせ応答を受信し、前記ルーティングテーブル内の対応するノードのビジーレベルを、前記状態レベル問い合わせ応答内で運ばれる前記ビジーレベルに従って更新するように適合された、ビジーレベル更新モジュールと、
前記ＤＨＴアルゴリズムと、前記ビジーレベル更新モジュールによって更新された前記ルーティングテーブル内の前記ノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたパケット受信ルーティングノードに前記パケットを送信するように適合された、パケット送信モジュールと、
を備え、
前記ルーティングノードは、
前記送信ノードから前記状態レベル問い合わせ要求を受信すると、ローカルノードのビジー状態を確認するように適合された、ビジー状態確認モジュールと、
前記ビジー状態確認モジュールの確認結果に従ってビジーレベルを決定するように適合された、ビジーレベル決定モジュールと、
前記ビジーレベル決定モジュールによって決定されたビジーレベルを運ぶ前記状態レベル問い合わせ応答を前記送信ノードに返すように適合された、メッセージ応答モジュールと、
前記送信ノードからパケットを受信し、前記ＤＨＴアルゴリズムと前記ローカルに記憶された他のノードのビジーレベルとに従って、前記次ホップルーティングノードを選択するように適合された、パケット転送モジュールと、
を備える、請求項１１に記載のシステム。
【請求項１３】
前記送信ノードは、
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を前記所定の間隔で測定するように適合された、測定モジュールと、
前記測定モジュールによって測定された前記パケットの数と、予めネゴシエーションされた最高閾値及び／又は中間閾値とを比較するように適合された、比較モジュールと、
前記比較モジュールの比較結果に従ってノードのビジーレベルを更新するように適合された、ビジーレベル更新モジュールと、
前記ＤＨＴアルゴリズムと、前記ビジーレベル更新モジュールによって更新された前記ルーティングテーブル内の前記ノードのビジーレベルとに従って、前記パケット受信ルーティングノードを選択し、前記選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、
を備える、請求項１１に記載のシステム。
【請求項１４】
状態レベル問い合わせ要求をローカルルーティングテーブル内のノードに所定の間隔で送信するように適合された、メッセージ送信モジュールと、
状態レベル問い合わせ応答を受信し、前記ルーティングテーブル内の対応するノードのビジーレベルを、前記状態レベル問い合わせ応答内で運ばれるビジーレベルに従って更新するように適合された、ビジーレベル更新モジュールと、
分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、前記ビジーレベル更新モジュールによって更新された前記ルーティングテーブル内の前記ノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、
を備える、送信ノード。
【請求項１５】
前記パケット送信モジュールは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップルーティングノードを探索し、前記次ホップルーティングノードのビジーレベルを判定し、該ビジーレベルは、全てのパケットの処理が可能なビジーレベル１と、前記次ホップノードが管理しているキー範囲内のパケットのみの処理が可能なビジーレベル２と、パケットを全く処理できないビジーレベル３と、を含み、前記ビジーレベルが２又は３である場合、パケットの宛先が、前記次ホップルーティングノードが管理しているキー範囲内であるか否かを判定するように適合された、確認ユニットと、
前記宛先が前記次ホップルーティングノードが管理しているキー範囲内であると前記確認ユニットが判定した場合、前記次ホップルーティングノードがビジーレベル２にあるならば、前記次ホップノードにパケットを送信するように、又は、前記次ホップルーティングノードがビジーレベル３にあるならば、前記次ホップルーティングノードのプロキシノードにパケットを送信するように適合された、パケット送信ユニットと、
を備える、請求項１４に記載の送信ノード。
【請求項１６】
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を所定の間隔で測定するように適合された、測定モジュールと、
前記測定モジュールによって測定された前記パケットの数と、予めネゴシエーションされた最高閾値及び／又は中間閾値とを比較するように適合された、比較モジュールと、
前記比較モジュールの比較結果に従ってノードのビジーレベルを更新するように適合された、ビジーレベル更新モジュールと、
分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、前記ルーティングテーブル内の前記ノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、
を備える、送信ノード。
【請求項１７】
前記パケット送信モジュールは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップルーティングノードを探索し、前記ローカルノードによって前記次ホップノードに送信されたパケットの数を確認し、前記パケットの数が前記中間閾値以上である場合、パケットの宛先が前記次ホップルーティングノードが管理しているキー範囲内であるか否かを判定するように適合された、確認ユニットと、
前記宛先が前記次ホップルーティングノードが管理しているキー範囲内であると前記確認ユニットが判定した場合、前記パケットの数が前記中間閾値と前記最高閾値との間であるならば、前記次ホップルーティングノードにパケットを送信するように、又は、前記パケットの数が前記最高閾値以上であるならば、前記次ホップルーティングノードのプロキシノードにパケットを送信するように適合された、パケット送信ユニットと、
を備える、請求項１６に記載の送信ノード。
【請求項１８】
送信ノードから状態レベル問い合わせ要求を受信すると、ローカルノードのビジー状態を確認するように適合された、ビジー状態確認モジュールと、
前記ビジー状態確認モジュールの確認結果に従ってビジーレベルを決定するように適合された、ビジーレベル決定モジュールと、
前記ビジーレベル決定モジュールによって決定されたビジーレベルを運ぶ状態レベル問い合わせ応答を、前記送信ノードに返すように適合された、メッセージ応答モジュールと、
パケットを受信し、分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、ローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、パケット転送モジュールと、
を備える、ルーティングノード。
【請求項１９】
状態公告ノードによって、ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストし、
バックアップリソース選択ノードによって、受信したノードのビジーレベルに従ってプロキシノードを選択する、
ことを含む、バックアップリソースを選択する方法。
【請求項２０】
前記ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストするステップは、
前記状態公告ノードによって、前記ローカルノードの前記ビジーレベルを確認し、前記ローカルノードのビジーレベルを、前記マルチキャストグループ内の他のノードにブロードキャストする、
ことを含み、
前記受信したノードのビジーレベルに従ってプロキシノードを選択するステップは、
前記バックアップリソース選択ノードによって、前記状態公告ノードによってブロードキャストされた前記ビジーレベルを受信すると、前記バックアップリソース選択ノードによって、前記プロキシノードを必要としているか否かを判定し、必要としている場合、前記受信したノードのビジーレベルに従って前記プロキシノードを選択し、又は、必要としていない場合、前記ビジーレベルを別のノードに中継する、
ことを含む、請求項１９に記載の方法。
【請求項２１】
ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストするように適合された、状態公告ノードと、
受信した状態公告ノードによってブロードキャストされたビジーレベルに従ってプロキシノードを選択するように適合された、バックアップリソース選択ノードと、
を備える、バックアップリソースを選択するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信に関し、特に、パケットルーティングの方法、システム、及び装置と、バックアップリソースを選択する方法及びシステムとに関する。
【背景技術】
【０００２】
ピアツーピア（Ｐ２Ｐ）ネットワークは、参加者が、それらの参加者が所有する何らかのハードウェアリソース（例えば、処理能力、記憶能力、ネットワーク接続能力、プリンタ）を共有する、分散ネットワークである。共有リソースは、いかなる中間エンティティの必要もなしに、ネットワークによって提供されるサービス及びコンテンツを介して、他のピアノードによってアクセスされることが可能である。ネットワーク内の参加者は、リソース（サービス及びコンテンツ）の提供者と、リソース（サービス及びコンテンツ）の消費者との両方である。Ｐ２Ｐは、従来のクライアント／サーバ（Ｃ／Ｓ）モデルを打破して、ネットワーク内の全てのノードが同位となるようにする。ノードは、他のノードにサービスを提供するサーバと、他のノードによって提供されるサービスを受けるクライアントとの両方である。Ｐ２Ｐは、システム内のどのノードの能力も十分に活用して、相互サービスを提供し、その結果、ノードの利用率が増加し、ネットワーク、装置、及び情報サービスの性能が向上する。
【０００３】
構造化Ｐ２Ｐシステムでは、リソースのパブリケーションはネットワークトポロジと密接に関連し、リソースは、Ｐ２Ｐトポロジ内の論理アドレスに正確に従って、ネットワーク内に分散させられる。システム内では、どのノードも仮想論理アドレスを有し、全てのノードが、それらのノードのアドレスに従って、比較的安定した緊密なトポロジを構成する。構造化Ｐ２Ｐシステムでは、リソースに対するハッシュ操作によって生成される値は、キーによって示されるリソースマーク値である。キーの名前空間は、ノードの名前空間にマッピングされ、すなわち、１つのキーが１つのノードに対応する。リソースは、キーとノードとの間のマッピングに従って、構造化Ｐ２Ｐシステム内に分散させられ、従って、リソースは、対応するキーに従って見つけられることが可能である。
【０００４】
構造化Ｐ２Ｐシステムでは、各ノードが、分散ハッシュテーブル（ＤＨＴ）に従って計算された、キー空間の一部を記憶する。キー空間は、ＤＨＴアルゴリズムによって異なる。例えば、ｃｈｏｒｄ（コード）アルゴリズムによれば、ノードＡとノードＢとが隣接しており、ノードＡのＩＤがノードＢのＩＤよりも小さい場合、ノードＡによって管理されるキー空間は、ノードＡのＩＤからノードＢのＩＤまでの数空間（ｎｕｍｅｒａｌ  ｓｐａｃｅ）内のキーで構成される。
【０００５】
ＤＨＴアルゴリズムは、ｃｈｏｒｄ及びｐａｓｔｒｙ（ペストリー）を含み、構造化Ｐ２Ｐネットワーク内での、キーに基づくリソース探索を提供する。キーに従ってルートが見出され、キーに対応するリソースは、そのルートにおいて取得されるか、又は記憶されている。
【０００６】
構造化Ｐ２Ｐシステム内でパケットがルーティングされる場合、パケット内の（宛先ノードに関連する）キーに対応した経路が、キーと特定のアルゴリズムとに従って決定され、パケットが、段階的なアプローチ方法を使用して、複数の中間ノードによって宛先ノードにルーティングされる。
【０００７】
Ｐ２Ｐオーバレイネットワーク内のノード上のルーティングテーブルは、ＤＨＴアルゴリズムに従って計算され、検索される。ｃｈｏｒｄアルゴリズムを例に取ると、ノード上のルーティングテーブルは表１に示されている。
【０００８】
【表１】
2010538552.tif 000003
【０００９】
ｃｈｏｒｄアルゴリズムでは、ノードがパケットをルーティングしている場合、ノードは、そのルーティングテーブルから、パケット内のキーに従って、近接ノードＩＤを見出し、そのノードＩＤに対応するノードにパケットを転送する。規則によれば、キーがＸとＺとの間である場合、パケットは、ノードＩＤ  Ｙに対応するノードに転送される。パケットが宛先ノード（ノードＩＤがキーであるノード）に到達するまで、どのノードも、この規則に従ってパケットをルーティングする。
【００１０】
しかし、Ｐ２Ｐオーバレイシステムでは、各ノードの処理能力は様々であり、異なるキーを有するパケットは、異なるホップ数を経由してルーティングされる。結果として、Ｐ２Ｐオーバレイシステム内のいくつかのノードは、より多くのパケットを処理し、他のノードは、より少ないパケットを処理する（処理とは、パケットのキーが、ノードによって記憶されているキー空間内に入る場合に、ノードがパケットをルーティングすること、又は、ノードが宛先である場合に、ノードがパケットを終端させることを意味する）。多数のパケットを処理するノード、及び劣った処理能力のノードは、十分な能力を提供できない可能性があり、これにより、Ｐ２Ｐオーバレイシステム内の輻輳が発生し、結果として、後続のパケットは転送も処理もされなくなる。
【００１１】
Ｐ２Ｐオーバレイシステム内の輻輳を回避するために、従来技術では、経路選択方法を以下のように提供する。
【００１２】
（１）宛先ノードにパケットを送信する前に、送信ノード（ソースノード）は、宛先ノードに、輻輳検出パケットを送信する。
【００１３】
（２）中間ノードが輻輳検出パケットを受信した後で、輻輳が発生している場合、中間ノードは、輻輳検出パケットの明示的輻輳通知（ＥＣＮ）を１に設定して、輻輳検出パケットを宛先ノードに転送する。
【００１４】
（３）宛先ノードは、送信ノードに輻輳通知を送信し、この通知は、中間ノードの輻輳情報を運んで、経路が輻輳していることを送信ノードに通知する。
【００１５】
（４）輻輳通知を受信したら、送信ノードは、その経路の代わりに別の経路を選択する。
【００１６】
Ｐ２Ｐオーバレイシステム内のノードのルーティングテーブルにおいて、ノードは、ｋ個の利用可能なノードから次ホップを選択することができる。ｋ個のノードのうち、１つは、ＤＨＴを介して検索された近接ノードであり、その他のノードは全て、近接ノードに隣接している。輻輳通知が、近接ノードが輻輳していることを示す場合、送信ノードは、次ホップとして、その他のｋ−１個のノードから無作為に１つを選択する。
【発明の概要】
【発明が解決しようとする課題】
【００１７】
本発明を実施する間に、発明者は、送信ノードが宛先ノードにパケットを送信する場合、送信ノードは輻輳検出パケットを最初に送信しなければならず、これは伝送における遅延を発生させる、ということを見出した。更に、発明者は、上記の解決法におけるノードは、輻輳及び非輻輳の２つの状態しか有さず、かつ、Ｐ２Ｐオーバレイネットワークでは、ノード間のトポロジ的状態は不安定なため（これは、輻輳検出パケットが送信された後でも、ルーティングテーブルが動的に変化することを意味している）、ノードの変化によりオーバレイ経路は変化する可能性があり、従って、テスト結果は正確ではない、ということを見出した。
【００１８】
発明者は、既存のマルチキャスト解決法におけるバックアップリソースの選択では、選択されるバックアップリソースの実際の処理能力が十分に考慮されず、従って、選択されたバックアップリソースは十分な処理能力を提供できない可能性があり、これにより、情報の紛失がもたらされ、かつ、マルチキャストトラフィックの正常な移送に悪影響が及ぼされる、ということも見出した。
【課題を解決するための手段】
【００１９】
経路上の負荷をバランスさせるため、及びネットワークの輻輳を回避するために、本発明の実施形態は、パケットルーティングの方法、システム、及び装置を提供する。技術的解決策は、以下の通りである。
【００２０】
パケットルーティングの方法は、
ノードのビジーレベルを所定の間隔で更新し、
ＤＨＴアルゴリズムとノードのビジーレベルとに従って、パケット受信ノードを選択し、選択されたパケット受信ノードにパケットを送信する、ことを含む。
【００２１】
パケットルーティングのシステムは、
ノードのビジーレベルを所定の間隔で更新し、ＤＨＴアルゴリズムと送信ノードのルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、選択されたルーティングノードにパケットを送信するように適合された、送信ノードと、
送信ノードからのパケットを受信し、ＤＨＴアルゴリズムとローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、ルーティングノードと、を含む。
【００２２】
更に、送信ノードは、
状態レベル問い合わせ要求を、ローカルルーティングテーブル内のノードに、所定の間隔で送信するように適合された、メッセージ送信モジュールと、
状態レベル問い合わせ応答を受信し、ルーティングテーブル内の対応するノードのビジーレベルを、状態レベル問い合わせ応答内で運ばれるビジーレベルに従って更新するように適合された、ビジーレベル更新モジュールと、
ＤＨＴアルゴリズムとビジーレベル更新モジュールによって更新されたルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、を含む。
【００２３】
別の送信ノードは、
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を所定の間隔で測定するように適合された、測定モジュールと、
測定モジュールによって測定されたパケットの数と、予めネゴシエーションされた最高閾値及び／又は中間閾値とを比較するように適合された、比較モジュールと、
比較モジュールの比較結果に従って、ノードのビジーレベルを更新するように適合された、ビジーレベル更新モジュールと、
ＤＨＴアルゴリズムとルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、を含む。
【００２４】
ルーティングノードは、
送信ノードから状態レベル問い合わせ要求を受信すると、ローカルノードのビジー状態を確認するように適合された、ビジー状態確認モジュールと、
ビジー状態確認モジュールの確認結果に従って、ビジーレベルを決定するように適合された、ビジーレベル決定モジュールと、
ビジーレベル決定モジュールによって決定されたビジーレベルを運ぶ状態レベル問い合わせ応答を、送信ノードに返すように適合された、メッセージ応答モジュールと、
パケットを受信し、ＤＨＴアルゴリズムとローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、パケット転送モジュールと、を含む。
【００２５】
この技術的解決法は、次の利点を提供する。
【００２６】
パケット受信ノードが、そのルーティングテーブル内のノードのビジーレベルを参照して選択されるため、ノード間での負荷の分散がバランスさせられ、ネットワークの輻輳の発生が回避される。
【００２７】
マルチキャストグループ内の適切なバックアップリソースを選択する目的のために、本発明の実施形態は、バックアップリソースを選択する方法及びシステムを提供する。技術的解決法は、以下の通りである。
【００２８】
バックアップリソースを選択する方法は、
状態公告ノードによって、ローカルノードのビジーレベルを１つのマルチキャストグループ内の他のノードにブロードキャストし、
バックアップリソース選択ノードによって、受信したノードのビジーレベルに従ってプロキシノードを選択することを含む。
【００２９】
バックアップリソースを選択するシステムは、
ローカルノードのビジーレベルを１つのマルチキャストグループ内の他のノードにブロードキャストするように適合された、状態公告ノードと、
受信した状態公告ノードによってブロードキャストされたビジーレベルに従って、プロキシノードを選択するように適合された、バックアップリソース選択ノードと、を含む。
【００３０】
この技術的解決法は、次の利点を提供する。
【００３１】
他のノードのビジーレベルを参照して、ノードは適切なプロキシノードを選択することができ、従って、選択は、リソースバックアップのために適切である。
【図面の簡単な説明】
【００３２】
【図１】本発明の第１の実施形態による、パケットルーティングの方法のフローチャートを示す。
【図２】本発明の第１の実施形態による、ノードＡからノードＩまでのルートを比較している。
【図３】本発明の第２の実施形態による、パケットルーティングの方法のフローチャートを示す。
【図４】本発明の第３の実施形態による、パケットルーティングのシステムの概略図である。
【図５】本発明の第４の実施形態による、バックアップリソースを選択するシステムのネットワーキングを示す。
【図６】本発明の第５の実施形態による、バックアップリソースを選択するシステムを示す。
【発明を実施するための形態】
【００３３】
本発明の技術的解決法、目的、及び利点をより明確にするために、以下では、本発明の実施形態について添付の図面を参照して詳細に説明する。
【００３４】
本発明の実施形態では、１つのノードのビジーレベルが、複数のレベルに設定され、他のノードに通知される。送信ノードがパケットを送信する場合、送信ノードは、他のノードのビジーレベルに従って、ルートを選択する。これにより、ネットワーク内の輻輳が防止され、負荷バランシングがある程度達成される。
【００３５】
第１の実施形態
本発明の第１の実施形態は、パケットルーティングの方法を提供する。方法は、ノードのビジーレベルを、予め設定された間隔で更新し（ここで、複数のビジーレベルが規定されており）、分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、ノードのビジーレベルとに従って、パケット受信ノードを選択し、選択されたノードにパケットを送信することを含む。
【００３６】
ノードのビジーレベルは、ノードの処理能力に従って、予め設定される。必要に応じて、複数のビジーレベルが設定されてもよい。ノードは、一定期間内に受信するパケットの数を測定し、測定結果と、そのノードの中央処理ユニット（ＣＰＵ）の状態と、そのノードのメモリサイズと、ネットワーク帯域幅とに従って、そのノードのビジーレベルを決定してもよい。決定では、ノードの意向と、その他のハードウェア性能指標も参照されてもよい。受信パケットの数は動的なので、ノードのビジーレベルもまた動的である。
【００３７】
図１は、本発明の一実施形態による、パケットルーティングの方法のフローチャートを示す。パケットルーティングの方法は、以下のステップを含む。
【００３８】
ステップ１０１：送信ノードが、そのルーティングテーブル内のノードに、状態レベル問い合わせ要求を送信する。
【００３９】
状態レベル問い合わせ要求は、通常のキープアライブ（ＫｅｅｐＡｌｉｖｅ）メッセージであってもよく、又は、他のノードがオンラインであるかどうかと、それらのノードのビジーレベルとを確認するための、ユーザ定義のメッセージであってもよい。
【００４０】
ステップ１０２：送信ノードから状態レベル問い合わせ要求を受信すると、ノードは、その現在のビジーレベルを確認し、そのノードのビジーレベルを運ぶ状態レベル問い合わせ応答を、送信ノードに送信する。
【００４１】
この実施形態では、ノードの状態は、３つのビジーレベルに分類される。
【００４２】
ビジーレベル１：ノードはアイドルであり、全てのパケットを処理する（転送する、又は終端させる）ことができる。
【００４３】
ビジーレベル２：ノードはビジーであるが、非常にビジーではなく、宛先がそのノードのキー範囲内にあるパケットを処理することができる。
【００４４】
ビジーレベル３：ノードは非常にビジーであり、後続のパケットを処理することができず、そのノードに宛てられたパケットは、そのノードのプロキシノードによって処理される必要があり、そのノードに宛てられていないパケットはプロキシノードに転送されない。
【００４５】
ノードの現在のビジーレベルが１である場合、そのノードの状態レベル問い合わせ応答は、ビジーレベル１を運ぶ。ノードの現在のビジーレベルが２である場合、そのノードの状態レベル問い合わせ応答は、ビジーレベル２と、そのノードのキー空間とを運ぶ。ノードの現在のビジーレベルが３である場合、そのノードによって送信される状態レベル問い合わせ応答は、ビジーレベル３と、そのノードのキー空間と、そのノードのプロキシノードのキーとを運ぶ。
【００４６】
必要に応じて、４つのビジーレベルが設定されてもよい。
【００４７】
ビジーレベル１：ノードは非常にアイドルであり、他のノードのプロキシノードとして働くこと、及び全てのパケットを処理することができる。
【００４８】
ビジーレベル２：ノードはアイドルであり、全てのパケットを処理することができるが、他のノードのプロキシノードとして働くことはできない。
【００４９】
ビジーレベル３：ノードはビジーであるが、非常にビジーではなく、宛先がそのノードのキー範囲内にあるパケットを処理することができる。
【００５０】
ビジーレベル４：ノードは非常にビジーであり、後続のパケットを処理することができず、そのノードに宛てられたパケットは、そのノードのプロキシノードによって処理される必要があり、そのノードに宛てられていないパケットはプロキシノードに転送されない。
【００５１】
ノードの現在のビジーレベルが１である場合、そのノードの状態レベル問い合わせ応答は、ビジーレベル１を運ぶ。ノードの現在のビジーレベルが２である場合、そのノードの状態レベル問い合わせ応答は、ビジーレベル２を運ぶ。ノードの現在のビジーレベルが３である場合、そのノードの状態レベル問い合わせ応答は、ビジーレベル３と、そのノードのキー空間とを運ぶ。ノードの現在のビジーレベルが４である場合、そのノードによって送信される状態レベル問い合わせ応答は、ビジーレベル４と、そのノードのキー空間と、そのノードのプロキシノードのキーとを運ぶ。
【００５２】
ビジーレベルに対応する状態は相対的である。３つのビジーレベルを例に取ると、３つのビジーレベルは、ＣＰＵ占有率と、残りの帯域幅と、空きメモリサイズとを比較することによって測定されてもよい。例えば、１ＧＨｚのＣＰＵと、２５６ＭＢのメモリと、５００ｋｂｐｓの帯域幅とを有するノードの場合、ＣＰＵ占有率が５０％以下、及び／又は、空きメモリサイズが４０ＭＢ以上、及び／又は、空き帯域幅が２００ｋｂｐｓ以上である場合、ノードはビジーレベル１にある。ＣＰＵ占有率が５０％と７０％との間、及び／又は、空きメモリサイズが１０ＭＢと４０ＭＢとの間、及び／又は、空き帯域幅が５０ｋｂｐｓと２００ｋｂｐｓとの間である場合、ノードはビジーレベル２にある。ＣＰＵ占有率が７０％以上、及び／又は、空きメモリサイズが１０ＭＢ以下、及び／又は、空き帯域幅が５０ｋｂｐｓ以下である場合、ノードはビジーレベル３にある。ビジーレベルのその他の区分について、各レベルの測定値は同様である。ここでの数値は例示に過ぎず、その他の値及び具体的な基準が同様に採用されてもよい。
【００５３】
ステップ１０３：状態レベル問い合わせ応答をノードから受信すると、送信ノードは、ノードの現在のビジーレベルを記憶する。
【００５４】
ノードの現在のビジーレベルは、ルーティングテーブル内又はユーザ定義のテーブル内の、ノードに対応するルーティングエントリ内に記憶されてもよい。
【００５５】
ステップ１０４：送信ノードがパケットを送信することを望む場合、送信ノードは、ＤＨＴアルゴリズムとノードのビジーレベルとを参照し、所定のポリシーに従って、パケットを受信するノードを選択する。
【００５６】
所定のポリシーとは、各ビジーレベルに対応する予め設定された処理（例えば、ビジーレベル２のノードには、そのノードのキー範囲内のパケットのみを送信する）を意味する。
【００５７】
ステップ１０５：送信ノードは、選択された受信ノードにパケットを送信する。
【００５８】
送信ノードは、ルーティングテーブル内のノードのビジーレベルに従って、受信ノードを決定する。３つのビジーレベルを例に取ると、具体的な処理は以下の通りである。
【００５９】
（１）ビジーレベル１のノードについては、全てのパケットが、そのノードに送信されることが可能である。
【００６０】
（２）ビジーレベル２のノードについては、そのノードのキー空間内のノードに宛てられたパケットのみが、そのノードに送信される。
【００６１】
（３）ビジーレベル３のノードについては、そのノードのキー空間内のノードに宛てられたパケットが、そのノードのプロキシノードに転送される。
【００６２】
上記の方法において、ノードによって送信ノードに返される状態レベル問い合わせ応答は、ノードのビジーレベルを運ぶ。ノードの現在の状態が、ノードの処理限界に近づいた場合、ノードの現在の状態に従って送信ノードが後続のパケットのための適切な受信ノードを選択するのを助けるために、ノードは、特別なメッセージを送信して送信ノードに通知してもよい。
【００６３】
ノードの処理能力は、ノードのビジーレベルに更に影響を及ぼす場合がある。例えば、ノードの低いハードウェア性能のため、ノードの最もアイドルな状態は、ビジーレベル１に達さず、せいぜいビジーレベル２である可能性がある。
【００６４】
図２では、本発明の実施形態における、ノードＡからノードＩまでのルートを比較している。ノードのビジーレベルは、ルーティングテーブル内に記憶されていると仮定する。
【００６５】
（１）ノードＡ及びノードＦを例に取ると、全てのノードがアイドルである場合、ノードＡ上のルーティングテーブルは表２に示されており、ノードＦ上のルーティングテーブルは表３に示されている。
【００６６】
【表２】
2010538552.tif 000004
【表３】
2010538552.tif 000005
【００６７】
パケットは、図２の破線で示すように、ルートＡ→Ｃ→Ｅ→Ｆ→Ｉに沿って、ノードＡからノードＩまでルーティングされる。
【００６８】
（２）ルート上のいくつかのノードが輻輳している場合、例えば、ノードＣ、ノードＧ、及びノードＨがビジーレベル２であり、ノードＩがビジーレベル３であり、そして、ノードＩのプロキシノードがノードＧである場合、ノードＡ上のルーティングテーブルは表４に示されており、ノードＦ上のルーティングテーブルは表５に示されている。
【００６９】
【表４】
2010538552.tif 000006
【表５】
2010538552.tif 000007
【００７０】
この場合、ノードＡがノードＩにパケットを送信する際に、ノードＡは、ローカルルーティングテーブル内のノードのビジーレベルを確認する。ノードＣのビジーレベルが２であることをノードＡが見出した場合、ノードＡはノードＢにパケットを送信する。ノードＢは、そのローカルルーティングテーブル内の情報に従って、ノードＦにパケットを転送する。ノードＦは、そのローカルルーティングテーブルを確認して、ノードＩがビジーレベル３であることを見出し、ノードＩのプロキシノードＧにパケットを転送する。従って、ノードＡからノードＩまでのルートは、図２の実線で示すように、Ａ→Ｂ→Ｆ→Ｇである。
【００７１】
この実施形態では、ノード間で負荷をバランスさせるため、及びネットワークの輻輳の発生を回避するために、ノードが、そのルーティングテーブル内のノードのビジーレベルを参照して、パケット受信ノードを選択する。加えて、パケットの宛先が十分に考慮され、その結果、ノードによって処理されるパケットは、ベストエフォートのノードに送信される。
【００７２】
第２の実施形態
本発明の第２の実施形態は、パケットルーティングの別の方法を提供する。送信ノードは、所定の期間内に下流ノードに送信されるパケットの最高閾値及び中間閾値に関して、下流ノードと予めネゴシエーションする。ネゴシエーション中に、下流ノードは、そのプロキシノードを送信ノードに通知する。送信ノードは、ネゴシエーションされた最高閾値及び中間閾値と、対応するプロキシノードとを記録する。そのような情報は、ルーティングテーブル又は別のユーザ定義のテーブル内の対応するエントリ内に書き込まれてもよい。この実施形態では、説明を容易にするために、情報はルーティングテーブル内に記録される。図３は、本発明の実施形態におけるパケットルーティングの方法のフローチャートを示し、この方法は以下を含む。
【００７３】
ステップ２０１：下流ノードに送信されたパケットの数（ｔ）を、一定の間隔で計数する。
【００７４】
ステップ２０２：ＤＨＴアルゴリズムに従って、ルーティングテーブル内の次ホップノードを探索し、測定された、次ホップノードに送信されたパケットの数（ｔ）を、中間閾値ｘ及び最高閾値ｙと比較する。ｔがｙ以上である場合、処理はステップ２０３に進み、ｔがｘ未満である場合、処理はステップ２０４に進み、ｔがｘとｙとの間である場合、処理はステップ２０５に進む。
【００７５】
ステップ２０３：そのノードへのパケットのルーティングを停止し、別のノードを選択する。
【００７６】
ステップ２０４：そのノードへのパケットのルーティングを継続する。
【００７７】
ステップ２０５：そのノードに宛てられたパケットは、そのノードにルーティングし、その他のパケットの、そのノードへの転送は停止する。
【００７８】
この実施形態では、ノードのキー範囲が変更された場合、ノードはその上流ノードに、変更されたキー範囲を通知する。
【００７９】
図２に示すノードを引き続き例に取る。
【００８０】
（１）ノードＡによって測定された、ノードＢに送信されたパケットの数は、中間閾値ｘと最高閾値ｙとの間であり、別のノードに送信されたパケットの数は、ｘ未満である。ノードＡ及びノードＦを例に取ると、ノードＡ上のルーティングテーブルは表６に示されており、ノードＦ上のルーティングテーブルは表７に示されている。
【００８１】
【表６】
2010538552.tif 000008
【表７】
2010538552.tif 000009
【００８２】
パケットは、図２の破線で示すように、ルートＡ→Ｃ→Ｅ→Ｆ→Ｉに沿って、ノードＡからノードＩまでルーティングされる。
【００８３】
（２）いくつかのノードがより多くのパケットを転送している場合、例えば、測定された、ノードＣ、ノードＧ、及びノードＨに送信されたパケットの数がｘとｙとの間であり、ノードＩに送信されたパケットの数がｙを上回り、そして、ノードＩのプロキシノードがノードＧである場合、ノードＡ上のルーティングテーブルは表８に示されており、ノードＦ上のルーティングテーブルは表９に示されている。
【００８４】
【表８】
2010538552.tif 000010
【表９】
2010538552.tif 000011
【００８５】
この場合、ノードＡがノードＩにパケットを送信する際に、ノードＡは、一定期間内にローカルルーティングテーブル内のノードに送信されたパケットの数（ｔ）を測定し、ノードＣに送信されたパケットの数が、中間閾値と最高閾値との間であることを見出す。次に、ノードＡは、ノードＢにパケットを送信する。ノードＢは、そのローカルルーティングテーブル内の情報に従って、ノードＦにパケットを転送する。ノードＦは、そのローカルルーティングテーブルを確認して、ノードＩによって処理されたパケットの数が最高閾値を超過したことを見出し、ノードＩのプロキシノードＧにパケットを転送する。従って、ノードＡからノードＩまでのルートは、図２の実線で示すように、Ａ→Ｂ→Ｆ→Ｇである。
【００８６】
この実施形態では、ノード間で負荷をバランスさせるため、及びネットワークの輻輳の発生を回避するために、ノードが、そのルーティングテーブル内のノードのビジーレベルを参照して、パケット受信ノードを選択する。加えて、パケットの宛先が十分に考慮され、その結果、ノードによって処理されるパケットは、ベストエフォートのノードに送信される。
【００８７】
第３の実施形態
図４は、本発明の第３の実施形態による、パケットルーティングのシステムの概略図である。パケットルーティングのシステムは、
ノードのビジーレベルを所定の間隔で更新し、ＤＨＴアルゴリズムと送信ノードのルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ノードを選択し、選択されたルーティングノードにパケットを送信するように適合された、送信ノードと、
送信ノードからのパケットを受信し、ＤＨＴアルゴリズムとローカルに記憶された、他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、ルーティングノードと、を含む。
【００８８】
送信ノードは、
状態レベル問い合わせ要求をローカルルーティングテーブル内のノードに、所定の間隔で送信するように適合された、メッセージ送信モジュールと、
状態レベル問い合わせ応答を受信し、ルーティングテーブル内の対応するノードのビジーレベルを状態レベル問い合わせ応答内で運ばれるビジーレベルに従って更新するように適合された、ビジーレベル更新モジュールと、
ＤＨＴアルゴリズムとビジーレベル更新モジュールによって更新されたルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、を含む。
【００８９】
更に、パケット送信モジュールは、
ＤＨＴアルゴリズムに従って、ルーティングテーブル内の次ホップルーティングノードを探索し、次ホップルーティングノードのビジーレベルを判定し（ここで、ビジーレベルは、全てのパケットが処理されることが可能なビジーレベル１と、次ホップノードのキー範囲内のパケットのみが処理されることが可能なビジーレベル２と、どのパケットも処理されることができないビジーレベル３とを含み）、ビジーレベルが２又は３である場合、パケットの宛先が、次ホップルーティングノードが管理しているキー範囲内であるか否かを判定するように適合された、確認ユニットと、
宛先が次ホップノードが管理しているキー範囲内である場合、次ホップノードのビジーレベルが２であると確認ユニットが判定した場合に、次ホップノードにパケットを送信するか、又は、次ホップノードのビジーレベルが３である場合に、次ホップノードのプロキシノードにパケットを送信するか、又は、次ホップノードのビジーレベルが１である場合に、任意のパケットを次ホップノードに送信するように適合された、パケット送信ユニットと、を含む。
【００９０】
従って、ルーティングノードは、
送信ノードから状態レベル問い合わせ要求を受信すると、ローカルノードのビジー状態を確認するように適合された、ビジー状態確認モジュールと、
ビジー状態確認モジュールの確認結果に従って、ビジーレベルを決定するように適合された、ビジーレベル決定モジュールと、
ビジーレベル決定モジュールによって決定されたビジーレベルを運ぶ状態レベル問い合わせ応答を送信ノードに返すように適合された、メッセージ応答モジュールと、
送信ノードからパケットを受信し、ＤＨＴアルゴリズムとローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、パケット転送モジュールと、を含む。
【００９１】
あるいは、下流ノードのビジーレベルが、そのノードにローカルノードによって送信されたパケットの数によって測定される場合、送信ノードは、
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を一定の間隔で測定するように適合された、測定モジュールと、
測定モジュールによって測定されたパケットの数と、予めネゴシエーションされた最高閾値及び／又は中間閾値とを比較するように適合された、比較モジュールと、
比較モジュールの比較結果に従って、ノードのビジーレベルを更新するように適合された、ビジーレベル更新モジュールと、
ＤＨＴアルゴリズムとビジーレベル更新モジュールによって更新されたノードのビジーレベルとに従って、パケット受信ノードを選択し、選択されたパケット受信ノードにパケットを送信するように適合された、パケット送信モジュールと、を含む。
【００９２】
更に、パケット送信モジュールは、
ＤＨＴアルゴリズムに従って、ルーティングテーブル内の次ホップノードを探索し、ローカルノードによって次ホップノードに送信されたパケットの数を確認し、パケットの数が中間閾値以上である場合、パケットの宛先が、次ホップノードが管理しているキー範囲内であるか否かを判定するように適合された、確認ユニットと、
宛先が次ホップノードが管理しているキー範囲内である場合、パケットの数が中間閾値と最高閾値との間であると確認ユニットが判定した場合に、次ホップノードにパケットを送信するように、又は、パケットの数が最高閾値以上である場合に、次ホップノードのプロキシノードにパケットを送信するように、又は、パケットの数が中間閾値未満である場合に、任意のパケットを次ホップノードに送信するように適合された、パケット送信ユニットと、を含む。
【００９３】
従って、ルーティングノードは、送信ノードからパケットを受信し、ＤＨＴアルゴリズムとローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合される。
【００９４】
この実施形態では、ノード間で負荷をバランスさせるため、及びネットワークの輻輳の発生を回避するために、ノードが、そのルーティングテーブル内のノードのビジーレベルを参照して、パケット受信ノードを選択する。加えて、パケットの宛先が十分に考慮され、その結果、ノードによって処理されるパケットは、ベストエフォートのノードに送信される。
【００９５】
第４の実施形態
本発明の第４の実施形態は、バックアップリソースを選択する方法を提供する。方法は、状態公告ノードが、そのビジーレベルを、マルチキャストグループ内の他のノードに公告し、バックアップリソース選択ノードが、受信したノードのビジーレベルに従って、プロキシノードを選択することを含む。
【００９６】
図５は、本発明の実施形態で提供されるネットワーク構成を示す。ＩＰＴＶマルチキャストエージェント（ＩＭＡ３）がそのビジーレベルを公告する場合、アプリケーション層マルチキャストグループ内のバックアップリソースを選択する処理は、以下の通りである。
【００９７】
１．ＩＭＡ３は、ローカルノードに使用可能なリソース（帯域幅、ＣＰＵの処理能力、及び記憶空間）を確認し、使用可能なリソースに従って、そのビジーレベルを決定し、他のノードによる参照のために、報告（Ｒｅｐｏｒｔ）メッセージを介してそのビジーレベルを公告し、その結果、他のノードは、ＩＭＡ３をプロキシノードとして又はバックアップリソースとして選択するかどうかを決定してもよい。
【００９８】
２．報告メッセージが上流に配信される場合、通過されるどのノードも、他のいずれかのブランチが、ＩＭＡ３がプロキシノードとして働くことを必要としているかどうかを判定し、必要としている場合、必要としているブランチに報告メッセージを中継し、バックアップ要求処理中ノードとして自らに印を付ける。他のいずれのブランチも、ＩＭＡ３がプロキシノードとして働くことを必要としていない場合、報告メッセージがデータソースノードＳに到達するまで、ノードは報告メッセージの上流への配信を継続する。
【００９９】
３．データソースノードＳは、ローカルノードの別のブランチがバックアップリソースを必要としていることを検知し、従って、報告メッセージをそのブランチに中継して、バックアップ要求処理中ノードとしてローカルノードに印を付ける。
【０１００】
４．データソースノードＳのブランチ内の子ノードが報告メッセージを受信した場合、子ノードは、その必要性に従って選択を行い、必要としていない場合は、その下流ノードに報告メッセージを継続して配信し、又は、必要としている場合は、そのバックアップリソースとしてＩＭＡ３を選択し、その下流ノードに報告メッセージを中継しない。
【０１０１】
５．ブランチ内のノードが、そのバックアップリソースとしてＩＭＡ３を選択した場合、ノードは、データソースノードＳにバックアップ要求（Ｂａｃｋｕｐ  Ｒｅｑ）を送信し、Ｓは、先着順サービスの原則に従って、ＯＫ又は失敗メッセージを使用して、バックアップを要求しているノードに応答する。
【０１０２】
６．ＯＫメッセージを受信したノードは、ＩＭＡ３をそのプロキシノードとみなし、失敗応答を受信したノードは、失敗メッセージを転送しない。
【０１０３】
例えば、ＩＭＡ６は、ＩＭＡ３をそのバックアップリソースとして選択し、バックアップ要求を介して、その選択をデータソースノードＳに通知し、データソースノードＳは、バックアップ要求に応答してＯＫメッセージを返す。ＯＫを受信したら、ＩＭＡ６は、ＩＭＡ３をそのプロキシノードとみなす。
【０１０４】
この実施形態では、ノードが、他のノードのビジーレベル（処理能力）を参照して、適切なノードをそのプロキシノードとして選択し、従って、選択されるノードは適切であり、リソースのバックアップを遂行することができる。
【０１０５】
第５の実施形態
図６は、本発明の第５の実施形態による、バックアップリソースを選択するシステムを示す。システムは、
ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストするように適合された、状態公告ノードと、
受信した、状態公告ノードによって公告されたビジーレベルに従って、プロキシノードを選択するように適合された、バックアップリソース選択ノードと、を含む。
【０１０６】
第４及び第５の実施形態の技術的解決法では、マルチキャストグループ内で、ノードが、他のノードのビジーレベル（処理能力）を参照して、適切なノードをそのプロキシノードとして選択し、従って、選択されるノードは適切であり、リソースのバックアップを遂行することができる。
【０１０７】
本発明の実施形態で提供される技術的解決法に対応するソフトウェアは、コンピュータハードディスク又はコンパクトディスクなどの、コンピュータ読み取り可能な記憶媒体内に記憶されてもよい。
【０１０８】
実施形態では、ノードが、他のノードのビジーレベル（処理能力）を参照して、適切なノードをそのプロキシノードとして選択し、従って、選択されるノードは適切であり、リソースのバックアップを遂行することができる。
【０１０９】
本発明について、いくつかの例示的実施形態を介して説明してきたが、本発明はそのような実施形態に限定されない。当業者が、本発明の精神及び範囲から逸脱することなく、本発明に対して様々な修正及び変形を行うことができることは明白である。本発明は、それらの修正及び変形を、それらが特許請求の範囲又はその均等物によって規定される保護範囲に入るならば、包含することを意図するものである。
【図１】
2010538552.tif 000012
【図２】
2010538552.tif 000013
【図３】
2010538552.tif 000014
【図４】
2010538552.tif 000015
【図５】
2010538552.tif 000016
【図６】
2010538552.tif 000017
【手続補正書】
【提出日】平成22年3月5日(2010.3.5)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
ｃｈｏｒｄアルゴリズムでは、ノードがパケットをルーティングしている場合、ノードは、そのルーティングテーブルから、パケット内のキーに従って、近接ノードＩＤを見出し、そのノードＩＤに対応するノードにパケットを転送する。パケットが宛先ノード（ノードＩＤがキーであるノード）に到達するまで、どのノードも、この規則に従ってパケットをルーティングする。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
しかし、Ｐ２Ｐオーバレイシステムでは、各ノードの処理能力は様々であり、異なるキーを有するパケットは、異なるホップ数を経由してルーティングされる。結果として、Ｐ２Ｐオーバレイシステム内のいくつかのノードは、より多くのパケットを処理し、他のノードは、より少ないパケットを処理する。多数のパケットを処理するノード、及び劣った処理能力のノードは、十分な能力を提供できない可能性があり、これにより、Ｐ２Ｐオーバレイシステム内の輻輳が発生し、結果として、後続のパケットは転送も処理もされなくなる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
Ｐ２Ｐオーバレイシステム内のノードのルーティングテーブルにおいて、ノードは、ｋ個の利用可能なノードから次ホップを選択することができる。ｋ個のノードのうち、１つは、ＤＨＴを介して検索された近接ノードであり、その他のノードは全て、近接ノードに隣接している。輻輳通知が、近接ノードが輻輳していることを示す場合、送信ノードは、次ホップとして、その他のｋ−１個のノードから１つを選択する。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノードのビジーレベルを所定の間隔で更新し、
分散ハッシュテーブル（ＤＨＴ）アルゴリズムと前記ノードのビジーレベルとに従ってパケット受信ノードを選択し、前記選択されたパケット受信ノードにパケットを送信する、
ことを含む、パケットルーティングの方法。
【請求項２】
前記ノードのビジーレベルを所定の間隔で更新するステップは、
ルーティングテーブル内のノードに前記所定の間隔で状態レベル問い合わせ要求を送信し、
前記状態レベル問い合わせ要求を受信したノードが、ノードのビジー状態を確認し、該ビジー状態に従ってノードのビジーレベルを決定し、該ビジーレベルを運ぶ状態レベル問い合わせ応答を返し、
前記状態レベル問い合わせ応答を受信すると、前記状態レベル問い合わせ応答内で運ばれた前記ビジーレベルに従ってノードに対応するビジーレベルを更新する、
ことを含む、請求項１に記載の方法。
【請求項３】
前記ノードのビジー状態を確認し、該ビジー状態に従ってノードのビジーレベルを決定するステップは、
前記状態レベル問い合わせ要求を受信したノードが、前記所定の間隔内にローカルノードによって受信されたパケットの数を確認し、前記ノードのビジーレベルを、前記パケットの数、中央処理ユニット（ＣＰＵ）の状態、メモリサイズ、ネットワーク帯域幅、及びノードの意向のうちの少なくとも１つに従って決定する、
ことを含む、請求項２に記載の方法。
【請求項４】
前記ビジーレベルは、全てのパケットの処理が可能なビジーレベル１と、ノードが管理しているキー範囲内のパケットのみの処理が可能なビジーレベル２と、パケットが全く処理できないビジーレベル３とを含み、
前記状態レベル問い合わせ要求を受信したノードのビジーレベルがビジーレベル２である場合、前記状態レベル問い合わせ応答は、前記状態レベル問い合わせ要求を受信したノードが管理しているキー範囲を運び、
前記状態レベル問い合わせ要求を受信したノードのビジーレベルがビジーレベル３である場合、前記状態レベル問い合わせ応答は、前記状態レベル問い合わせ要求を受信したノードが管理しているキー範囲と、ノードのプロキシノードのキーとを運ぶ、請求項２又は３に記載の方法。
【請求項５】
前記ＤＨＴアルゴリズムと前記ノードのビジーレベルとに従ってパケット受信ノードを選択し、前記選択されたパケット受信ノードにパケットを送信するステップは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップノードを探索し、前記次ホップノードのビジーレベルを判定し、前記ビジーレベルが２又は３である場合、パケットの宛先が、前記次ホップノードが管理するキー範囲内であるか否かを確認し、前記宛先が前記範囲内である場合、前記次ホップノードがビジーレベル２にあるならば、前記次ホップノードに前記パケットを送信し、又は、前記次ホップノードがビジーレベル３にあるならば、前記次ホップノードのプロキシノードに前記パケットを送信する、
ことを含む、請求項４に記載の方法。
【請求項６】
前記ノードのビジーレベルを所定の間隔で更新するステップは、
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を前記所定の間隔で測定し、
前記パケットの数を、予めネゴシエーションされた最高閾値及び／又は中間閾値と比較し、
比較結果に従って、ノードのビジーレベルを更新する、
ことを含む、請求項１に記載の方法。
【請求項７】
前記ＤＨＴアルゴリズムと前記ノードのビジーレベルとに従ってパケット受信ノードを選択し、前記選択されたパケット受信ノードにパケットを送信するステップは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップノードを探索し、前記ローカルノードによって前記次ホップノードに送信されたパケットの数を測定し、前記パケットの数が前記中間閾値以上である場合、前記パケットの宛先が前記次ホップノードが管理するキー範囲内であるか否かを確認し、前記宛先が前記範囲内である場合、前記パケットの数が前記中間閾値と前記最高閾値との間であるならば、前記次ホップノードに前記パケットを送信し、又は、パケットの前記数が前記最高閾値以上であるならば、前記次ホップノードのプロキシノードに前記パケットを送信する、
ことを含む、請求項６に記載の方法。
【請求項８】
ノードのビジーレベルを所定の間隔で更新し、分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、ルーティングテーブル内のノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたルーティングノードにパケットを送信するように適合された、送信ノード。
【請求項９】
状態レベル問い合わせ要求をローカルルーティングテーブル内のノードに所定の間隔で送信するように適合された、メッセージ送信モジュールと、
状態レベル問い合わせ応答を受信し、前記ルーティングテーブル内の対応するノードのビジーレベルを、前記状態レベル問い合わせ応答内で運ばれるビジーレベルに従って更新するように適合された、ビジーレベル更新モジュールと、
分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、前記ビジーレベル更新モジュールによって更新された前記ルーティングテーブル内の前記ノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、
を備える、請求項８に記載の送信ノード。
【請求項１０】
前記パケット送信モジュールは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップルーティングノードを探索し、前記次ホップルーティングノードのビジーレベルを判定し、該ビジーレベルは、全てのパケットの処理が可能なビジーレベル１と、前記次ホップノードが管理しているキー範囲内のパケットのみの処理が可能なビジーレベル２と、パケットを全く処理できないビジーレベル３と、を含み、前記ビジーレベルが２又は３である場合、パケットの宛先が、前記次ホップルーティングノードが管理しているキー範囲内であるか否かを判定するように適合された、確認ユニットと、
前記宛先が前記次ホップルーティングノードが管理しているキー範囲内であると前記確認ユニットが判定した場合、前記次ホップルーティングノードがビジーレベル２にあるならば、前記次ホップノードにパケットを送信するように、又は、前記次ホップルーティングノードがビジーレベル３にあるならば、前記次ホップルーティングノードのプロキシノードにパケットを送信するように適合された、パケット送信ユニットと、
を備える、請求項９に記載の送信ノード。
【請求項１１】
ローカルノードによってローカルルーティングテーブル内のノードに送信されたパケットの数を所定の間隔で測定するように適合された、測定モジュールと、
前記測定モジュールによって測定された前記パケットの数と、予めネゴシエーションされた最高閾値及び／又は中間閾値とを比較するように適合された、比較モジュールと、
前記比較モジュールの比較結果に従ってノードのビジーレベルを更新するように適合された、ビジーレベル更新モジュールと、
分散ハッシュテーブル（ＤＨＴ）アルゴリズムと、前記ルーティングテーブル内の前記ノードのビジーレベルとに従って、パケット受信ルーティングノードを選択し、前記選択されたパケット受信ルーティングノードにパケットを送信するように適合された、パケット送信モジュールと、
を備える、請求項８に記載の送信ノード。
【請求項１２】
前記パケット送信モジュールは、
前記ＤＨＴアルゴリズムに従って前記ルーティングテーブル内の次ホップルーティングノードを探索し、前記ローカルノードによって前記次ホップノードに送信されたパケットの数を確認し、前記パケットの数が前記中間閾値以上である場合、パケットの宛先が前記次ホップルーティングノードが管理しているキー範囲内であるか否かを判定するように適合された、確認ユニットと、
前記宛先が前記次ホップルーティングノードが管理しているキー範囲内であると前記確認ユニットが判定した場合、前記パケットの数が前記中間閾値と前記最高閾値との間であるならば、前記次ホップルーティングノードにパケットを送信するように、又は、前記パケットの数が前記最高閾値以上であるならば、前記次ホップルーティングノードのプロキシノードにパケットを送信するように適合された、パケット送信ユニットと、
を備える、請求項１１に記載の送信ノード。
【請求項１３】
請求項８〜１２のいずれか１項に記載の送信ノードと、
前記送信ノードからのパケットを受信し、前記ＤＨＴアルゴリズムとローカルに記憶された他のノードのビジーレベルとに従って、次ホップルーティングノードを選択するように適合された、ルーティングノードと、
を備える、パケットルーティングのシステム。
【請求項１４】
状態公告ノードによって、ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストし、
バックアップリソース選択ノードによって、受信したノードのビジーレベルに従ってプロキシノードを選択する、
ことを含む、バックアップリソースを選択する方法。
【請求項１５】
前記ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストするステップは、
前記状態公告ノードによって、前記ローカルノードの前記ビジーレベルを確認し、前記ローカルノードのビジーレベルを、前記マルチキャストグループ内の他のノードにブロードキャストする、
ことを含み、
前記受信したノードのビジーレベルに従ってプロキシノードを選択するステップは、
前記バックアップリソース選択ノードによって、前記状態公告ノードによってブロードキャストされた前記ビジーレベルを受信すると、前記バックアップリソース選択ノードによって、前記プロキシノードを必要としているか否かを判定し、必要としている場合、前記受信したノードのビジーレベルに従って前記プロキシノードを選択し、又は、必要としていない場合、前記ビジーレベルを別のノードに中継する、
ことを含む、請求項１４に記載の方法。
【請求項１６】
ローカルノードのビジーレベルを、１つのマルチキャストグループ内の他のノードにブロードキャストするように適合された、状態公告ノードと、
受信した状態公告ノードによってブロードキャストされたビジーレベルに従ってプロキシノードを選択するように適合された、バックアップリソース選択ノードと、
を備える、バックアップリソースを選択するシステム。
【国際調査報告】
2010538552.tif 000018
2010538552.tif 000019
2010538552.tif 000020
2010538552.tif 000021