(57)【要約】【課題】本発明は、データ通信ネットワークのための負荷平衡化装置を提供する。【解決手段】  本装置は、入来データ・パケットに対してハッシュ関数を計算するためのハッシュ論理を備える。ハッシュ論理に、閾値検出器が接続され、所定の閾値を超えた下流オブジェクトの利用に応答して、下流オブジェクト間でデータ・パケットを再分配させるため、ハッシュ論理において、第１組のパラメータから第２組のパラメータへの、ハッシュ関数のパラメータの再画定をトリガする。使用の際、ハッシュ論理は、第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介してネットワークの下流オブジェクトにルーティングするためにパケットを送出し、閾値を超えた場合には、第１組および第２組のパラメータを用いた別個のハッシュ計算に応じて第１のルーティング経路および第２のルーティング経路の１つにパケットを選択的に送出する。
2005536087.tif 000002
【特許請求の範囲】
【請求項１】
データ通信ネットワークのための負荷平衡化装置であって、
入来データ・パケットに対してハッシュ関数を計算するハッシュ論理と、
前記ハッシュ論理に接続された閾値検出器であって、所定の閾値を超えた下流オブジェクトの利用に応答して、前記下流オブジェクト間で前記データ・パケットを再分配させるため、前記ハッシュ論理において、第１組のパラメータから第２組のパラメータへの、前記ハッシュ関数のパラメータの再画定をトリガする閾値検出器と、
を備え、前記ハッシュ論理は、使用の際、前記第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介して前記ネットワークの下流オブジェクトにルーティングするために前記パケットを送出し、前記閾値を超えた場合には、前記第１組および前記第２組のパラメータを用いた別個のハッシュ計算に応じて前記第１のルーティング経路および第２のルーティング経路の１つに前記パケットを選択的に送出し、以降、前記別個のハッシュ計算の１つの結果に基づいて前記第１および第２のルーティング経路のうち選択された１つを介して前記パケットをルーティングする、負荷平衡化装置。
【請求項２】
前記ハッシュ論理は、使用の際、前記別個のハッシュ計算の結果が交差する場合には前記データ・パケットを前記第１のルーティング経路に送出し、その他の場合、前記データ・パケットを前記第２のルーティング経路に送出する、請求項１に記載の装置。  
【請求項３】
前記ハッシュ論理に接続され、所定の値を超えた寿命を有するフローについて、選択的に前記ハッシュ論理を迂回させるためのフィルタを更に備える、請求項１または２に記載の装置。  
【請求項４】
前記第１のルーティング経路および前記第２のルーティング経路を更に備え、前記第１のルーティング経路は前記ハッシュ論理に接続された第１のルーティング論理を備え、前記第２のルーティング経路は前記ハッシュ論理に接続された第２のルーティング論理を備え、前記第１のルーティング経路は前記第２のルーティング経路よりも高速であり、前記第２のルーティング経路上で、パケット・フロー・ステータスに基づいて下流オブジェクトを選択する、請求項４に記載の装置。
【請求項５】
前記第１のルーティング論理は少なくとも１つのネットワーク・プロセッサを備え、前記第２のルーティング論理は少なくとも１つの汎用プロセッサを備える、請求項４に記載の装置。
【請求項６】
前記第２のルーティング論理は、データ・パケットのフローにおいてフロー・デリミッタを検出し、開始インジケータを検出すると、前記第２のパラメータを用いて前記ハッシュ関数に従って対応するフローをルーティングするように構成されている、請求項４または請求項５に記載の装置。
【請求項７】
前記第２のルーティング論理は、所定のイナクティブ時間を超えたパケットのフローを検出し、かかるフローを前記第２のパラメータを用いて前記ハッシュ関数に従ってルーティングするように構成されている、請求項６に記載の装置。
【請求項８】
前記第２のルーティング論理は、所定の寿命を超えたパケットのフローを検出し、かかるフローを前記第１のルーティング論理に送出するように構成されている、請求項７に記載の装置。
【請求項９】
前出のいずれかの請求項に記載の負荷平衡化装置を備えた特定用途向け集積回路。
【請求項１０】
請求項１ないし７のいずれかに記載の負荷平衡化装置を備えたネットワーク・インフラストラクチャ・ノード。
【請求項１１】
請求項９に記載のネットワーク・インフラストラクチャ・ノードを備えたデータ通信ネットワーク。
【請求項１２】
データ通信ネットワークにおける負荷平衡化の方法であって、
入来データ・パケットに対してハッシュ関数を計算するステップと、
所定の閾値を超えた下流オブジェクトの利用に応答して、前記下流オブジェクト間で前記データ・パケットを再分配させるため、第１組のパラメータから第２組のパラメータへの、前記ハッシュ関数のパラメータの再画定をトリガするステップと、
前記第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介して前記ネットワークの下流オブジェクトにルーティングするために前記パケットを送出し、前記閾値を超えた場合には、前記第１組および前記第２組のパラメータを用いた別個のハッシュ計算に応じて前記第１のルーティング経路および第２のルーティング経路の１つに前記パケットを選択的に送出し、以降、前記別個のハッシュ計算の１つの結果に基づいて前記第１および第２のルーティング経路のうち選択された１つを介して前記パケットをルーティングするステップと、
を備える、方法。
【請求項１３】
前記別個のハッシュ計算の結果が交差する場合には前記データ・パケットを前記第１のルーティング経路に送出し、その他の場合、前記データ・パケットを前記第２のルーティング経路に送出するステップを備える、請求項１１に記載の方法。  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にデータ・ネットワークにおける負荷平衡化（load balancing）に関し、特定すれば、データ・ネットワークにおける負荷平衡化のための方法および装置に関する。
【背景技術】
【０００２】
データ・ネットワークは、通常、データ通信ネットワーク・インフラストラクチャを介して複数のクライアント・コンピュータに相互接続された複数のサーバ・コンピュータを備えている。ネットワーク・インフラストラクチャは、通常、クライアント・コンピュータとサーバ・コンピュータとの間でデータ・パケットをルーティングするための、スイッチ、ルータ等の複数の中間データ通信デバイスまたはノードを備えている。かかるデータ通信デバイスは、典型的に、複数の入力／出力（Ｉ／Ｏ）ポート、あるポート上で受信したデータ・パケットを他のポートの１つ以上にルーティングするためのスイッチ機構、および、スイッチ機構を制御して、過渡的なデータ・パケットに含まれるアドレス情報に基づいてポート間で適切な接続を行うための制御論理を備えている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
かかるデータ・ネットワークに関連する問題は、ネットワーク・インフラストラクチャ内の異なるノード間で負荷を平衡化することである。ネットワーク・インフラストラクチャが処理するデータ・トラヒックの量が増大すると、インフラストラクチャ内のノードにかかる負荷間のバランスをタイムリーに維持することが難しくなる。従って、通信が妨げられ、遅延が発生する。
【課題を解決するための手段】
【０００４】
本発明によれば、データ通信ネットワークのための負荷平衡化装置が提供される。この装置は、入来データ・パケットに対してハッシュ関数を計算するハッシュ論理と、ハッシュ論理に接続された閾値検出器であって、所定の閾値を超えた下流オブジェクトの利用に応答して、下流オブジェクト間でデータ・パケットを再分配させるため、ハッシュ論理において、第１組のパラメータから第２組のパラメータへの、ハッシュ関数のパラメータの再画定をトリガする閾値検出器と、を備え、ハッシュ論理は、使用の際、第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介してネットワークの下流オブジェクトにルーティングするためにパケットを送出し、閾値を超えた場合には、第１組および前記第２組のパラメータを用いた別個のハッシュ計算に応じて第１のルーティング経路および第２のルーティング経路の１つにパケットを選択的に送出し、以降、別個のハッシュ計算の１つの結果に基づいて第１および第２のルーティング経路のうち選択された１つを介してパケットをルーティングする。
【０００５】
好ましくは、ハッシュ論理は、使用の際、別個のハッシュ計算の結果が交差する場合にはデータ・パケットを第１のルーティング経路に送出し、その他の場合、データ・パケットを第２のルーティング経路に送出する。本発明の好適な実施形態では、この装置は、ハッシュ論理に接続され、所定の値を超えた寿命を有するフローについて、選択的にハッシュ論理を迂回させるためのフィルタを更に備える。本発明の特に好適な実施形態では、この装置は、第１のルーティング経路および第２のルーティング経路を更に備え、第１のルーティング経路はハッシュ論理に接続された第１のルーティング論理を備え、第２のルーティング経路はハッシュ論理に接続された第２のルーティング論理を備え、第１のルーティング経路は第２のルーティング経路よりも高速であり、第２のルーティング経路上で、パケット・フロー・ステータスに基づいて下流オブジェクトを選択する。
【０００６】
第１のルーティング論理は少なくとも１つのネットワーク・プロセッサを備え、第２のルーティング論理は少なくとも１つの汎用プロセッサを備えることができる。第２のルーティング論理は、データ・パケットのフローにおいてフロー・デリミッタを検出し、開始インジケータを検出すると、第２のパラメータを用いてハッシュ関数に従って対応するフローをルーティングするように構成することができる。また、第２のルーティング論理は、所定のイナクティブ時間を超えたパケットのフローを検出し、かかるフローを第２のパラメータを用いてハッシュ関数に従ってルーティングするように構成することができる。更に、第２のルーティング論理は、所定の寿命を超えたパケットのフローを検出し、かかるフローを第１のルーティング論理に送出するように構成することができる。
【０００７】
本発明は、本明細書において前述した負荷平衡化装置を備えた特定用途向け集積回路に拡張される。また、本発明は、本明細書において前述した負荷平衡化装置を備えたネットワーク・インフラストラクチャ・ノードに拡張される。更に、本発明は、かかるネットワーク・インフラストラクチャ・ノードを備えたデータ通信ネットワークに拡張される。
【０００８】
別の態様から本発明を見ると、データ通信ネットワークにおける負荷平衡化の方法が提供される。この方法は、入来データ・パケットに対してハッシュ関数を計算するステップと、所定の閾値を超えた下流オブジェクトの利用に応答して、下流オブジェクト間でデータ・パケットを再分配させるため、第１組のパラメータから第２組のパラメータへの、ハッシュ関数のパラメータの再画定をトリガするステップと、第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介してネットワークの下流オブジェクトにルーティングするためにパケットを送出し、閾値を超えた場合には、第１組および前記第２組のパラメータを用いた別個のハッシュ計算に応じて第１のルーティング経路および第２のルーティング経路の１つにパケットを選択的に送出し、以降、別個のハッシュ計算の１つの結果に基づいて第１および第２のルーティング経路のうち選択された１つを介してパケットをルーティングするステップと、を備える。
【０００９】
本発明の好適な実施形態では、この方法は、別個のハッシュ計算の結果が交差する場合にはデータ・パケットを第１のルーティング経路に送出し、その他の場合、データ・パケットを第２のルーティング経路に送出するステップを備える。  
【００１０】
ハードウエアにおいて１０，０００および１００，０００のフローを最適に平衡化するため、フローで最低限の状態を維持するが、ホスト間のＴＣＰフロー等のアクティブ・フローの接続性を維持する方式を決定することが必要である。
【００１１】
本発明の好適な実施形態では、反復ハードウエア負荷平衡化技法が提供される。この技法では、ハッシュ関数を用いて、データ通信ネットワークにおける多数のホスト、中間ノード、および／またはネットワーク・インタフェース間でパケット・フローを平衡化する。フローに関連したソースのアドレス等、フローの持続時間一定である各パケットの一部に、ハッシュを実行する。この技法では、１組のみのハッシュ・パラメータによってハッシュ関数を計算する状態と、２組のハッシュ・パラメータが与えられる状態とが交互に生じる。１つの状態では、１つのハッシュ結果が既知である。他の状態では、２つのハッシュ結果間の差が既知である。この技法は、ルーティング高速経路およびルーティング低速経路を識別する。ルーティング高速経路は、ネットワーク・プロセッサまたは同様の特定用途向け集積回路（ＡＳＩＣ：application specific integrated circuit）等の専用ハードウエアにおいて実行可能である。ルーティング低速経路は、汎用プロセッサ（ＧＰＰ：general purpose processor）上のソフトウエアのいいて実行する方が良い。継続性が維持されない限り、負荷平衡化したオブジェクト間で進行中のデータ・フローは移動しない。これにより、フロー接続性が断続せず、パケットは整理し直されないことが保証されて有利である。更に、２つのハッシュ関数の交点の外側のデータ・フローについて状態を保持する。しかしながら、この保持された状態は、絶えず積極的に低減される。これは、ハードウエアのコストを最小限に抑えるので有利である。更に、ネットワーク・プロセッサ・ハードウエア等の専用ハードウエアによって高速経路ルーティングを実行することによって、データ通信の性能は、今まで利用可能であったレベルよりも向上する。
【００１２】
ここで、本発明の好適な実施形態について、添付図面を参照して、一例としてのみ説明する。
【発明を実施するための最良の形態】
【００１３】
まず図１を参照すると、データ通信ネットワーク１４０は、複数のネットワーク・オブジェクト１０〜１２０を備えている。ネットワーク・オブジェクトは、ネットワーク・ノード１０〜９０および、ネットワーク・ノード１０〜３０間でデータ・パケットを伝達するための介入ネットワーク・リンク１００〜１２０を含む。ネットワーク・ノード１０〜９０は、終点ノード１０〜６０およびインフラストラクチャ・ノード７０〜９０を含む。リンク１１０〜１２０のインフラストラクチャ・ノード７０〜９０は、集合的に、ネットワーク・インフラストラクチャ１３０を形成する。終点ノード１０〜６０は、複数のクライアント・データ処理デバイス１０〜３０および複数のサーバ・コンピュータ・システム４０〜６０を含む。クライアント１０〜３０およびサーバ４０〜６０は、介入ネットワーク・インフラストラクチャ１００を介して相互接続されている。各クライアント１０〜３０は、パーソナル・コンピュータ、ラップトップ・コンピュータ、パーソナル・デジタル・アシスタント、携帯電話等とすることができる。各サーバ４０〜６０は、ファイル・サーバ、プリント・サーバ、または同様のホスト・データ処理またはデータ保存リソースとすることができる。
【００１４】
動作において、クライアント１０〜３０およびサーバ４０〜６０間のデータ通信は、ネットワーク・インフラストラクチャ１３０を介したデータ・パケットのフローによって行われる。データ・パケット・フローは、１つ以上のデータ通信プロトコルに従って、クライアント１０〜３０およびサーバ４０〜６０間の途中で、ネットワーク・インフラストラクチャのインフラストラクチャ・ノード７０〜９０間を通る。各インフラストラクチャ・ノード７０〜９０は、パケット・ルーティング機能を実行して、受信したデータ・パケットを適切な受信側オブジェクトに転送する。
【００１５】
ここで図２を参照すると、各インフラストラクチャ・ノード７０〜９０は、第１のルーティング論理２２０、第２ルーティング論理２１０、ならびに、第１のルーティング論理２２０および第２のルーティング論理２１０の双方に接続された負荷平衡器２００を備えている。第１のルーティング論理２２０および第２のルーティング論理２１０は双方とも、同一のルーティング機能を実行する。しかしながら、第１のルーティング論理２２０は、第２のルーティング論理２１０よりも高速でルーティング機能を実行する。このため、第１のルーティング論理２２０は、比較的高速のルーティング経路を提供し、第２のルーティング論理２１０は、比較的低速のルーティング経路を提供する。
【００１６】
ここで図３を実行すると、本発明の特に好適な実施形態において、各インフラストラクチャ・ノードは、制御ポイント４００に接続されたネットワーク・プロセッサ（ＮＰ：network processor）３００を備えている。負荷平衡器２００および第１のルーティング論理２２０は双方とも、ＮＰ３００において実施される。具体的には、ＮＰ３００は、パケット・ルーティング機能を実行するための第１のルーティング論理２２０のハードワイヤード（hardwired）論理実施と共に、負荷平衡器２００の負荷平衡化決定を実行するための実行可能ソフトウエアを備えている。負荷平衡器２００は、フィルタ２３０と、このフィルタ２３０に接続されたハッシュ論理（hash logic）とを備えている。
【００１７】
ＮＰ３００に接続された制御ポイント（ＣＰ：controlpoint）４００は、メモリ４２０に接続された汎用処理ユニット（ＧＰＰ：general purpose processing unit）４１０を備えている。メモリ４２０には、ＧＰＰ４１０によって実行された場合に、フロー状態コントローラ４３０、閾値検出器４４０および４９０、ハッシュ・パラメータ発生器４５０、競合フロー状態テーブル４６０、「長生き」フロー状態テーブル４８０、およびルータ４７０を実行するためのコンピュータ・プログラム・コードが保存されている。フロー状態コントローラ４３０は、クライアント−サーバのフローの状態を計算する。閾値検出器４４０は、サーバ４０〜６０の現在の負荷ステータスを監視して負荷管理を行う。ルータ４７０は、第２のルーティング論理２１０を実現する。ＣＰ４００によるパケット・ルーティング機能の実行は、ＮＰ３００によるパケット・ルーティング機能の実行よりも低速である。
【００１８】
動作において、負荷平衡器２００は、フィルタ２３０およびハッシュ論理２４０の現在のステータスに応じて、入来データ・パケットの各フローを第１のルーティング論理２２０またはＣＰ４００のどちらで処理するかを決定する。フィルタ２３０およびハッシュ論理２４０の双方のステータスは、ネットワーク１４０におけるダウンストリーム・オブジェクトの１つ以上に対する主な要求に基づいて、ＣＰ４００によって制御される。かかる負荷平衡化は、例えば、最適でない方法で分配されたクライアント要求によるダウンストリーム・オブジェクトの１つ以上の不必要な過負荷を防ぐために望ましい。不必要な過負荷を防ぐことによって、ネットワーク１４０における利用可能なサービス・レベルは最適化される。負荷平衡器２００は、内部のハッシュ論理２４０によって、ハッシュ関数を実行して、ネットワーク内のオブジェクト間でデータ・パケット・フローを平衡化する。具体的には、ハッシュ論理２４０は、ソース・アドレス等、パケット・フローの持続時間の間一定である入来データ・パケットの一部に対してハッシュ関数を実行する。負荷平衡器２００では、２つのハッシュ関数の結果間の差が既知である状態と、１つのみのハッシュ関数の結果が既知である状態とが交互に生じる。フィルタ２３０は、いくつかのパケット・フローについてハッシュ論理２４０を避けさせることができる。
【００１９】
動作において、フィルタ２３０は、データ・パケットの入来フローを、第１のルーティング論理２２０またはハッシュ論理２４０のいずれかに送出する。ハッシュ論理２４０は、ＣＰ４００からの制御入力に応じて、パケットを、第１のルーティング論理２２０または第２のルーティング論理２１０が実施されているＣＰ４００のいずれかに送出する。パケットが第１のルーティング論理２２０に渡された場合、これに、ハッシュ論理２４０またはフィルタ２３０からのルーティング情報を結合する。追加されたルーティング情報は、第１のルーティング論理２２０に、特定のルーティング経路を選ばせる。ハッシュ関数が、パケットを第２のルーティング論理２２０に再送出した場合、パケットにはルーティング情報も含まれる。
【００２０】
ここで図４を参照すると、制御ポイント４００は、ステップ５００において、負荷平衡器２００のハッシュ論理２４０およびフィルタ２３０の双方を初期化することから開始する。フィルタ２３０は無効にセットされる。ハッシュ論理２４０の初期パラメータは、オペレータの構成に基づくものとすることができる。あるいは、初期ハッシュ・パラメータは、平衡化するオブジェクト４０〜６０のリソース容量の自動化問合せに基づくものとしても良い。かかるリソース性能の例は、ＣＰＵ速度、インタフェース速度等を含む。ステップ５１０では、ＣＰ４００は、平衡化されるオブジェクト４０〜６０におけるリソース利用に関連してフィードバック・メモリ４３０に統計値を蓄積する。
【００２１】
ステップ５２０では、閾値検出器４４０が、所定の閾値に対してフロー状態コントローラ４３０に蓄積された統計値を調べて、オブジェクト４０〜６０のうち少なくとも１つが他のオブジェクトに対して過度に利用されているか否かを判定する。判定結果が肯定である場合、ステップ５３０において、新たなハッシュ・パラメータを、ハッシュ・パラメータ発生器４５０によって計算し、第２組のパラメータとしてハッシュ論理２４０にロードする。新たなハッシュ・パラメータは、収集した統計値に基づいてネットワーク・トラヒックを最適に分配させる。ステップ５４０において、ＣＰ４００は、第２のルーティング論理２１０として機能する。具体的には、ＣＰ４００は、ハッシュ論理２４０が古い１組のパラメータおよび新しい１組のパラメータの双方によってハッシュ関数を計算した場合に異なるハッシュ結果を出したパケットを負荷平衡器２００から受信する。かかる「競合フロー」について、ＣＰ４００は、競合フロー状態テーブル４６０内でフロー状態ごとの情報を確立し維持する。ＣＰ４００が構成可能時間間隔内で競合フローのパケットを受信しない場合、またはＣＰ４００が少なくとも一度ＴＣＰ  ＦＩＮビット等のフローエンド・インジケータを受信した場合、対象のフローは終了したと見なされ、その状態は「古いので終了」と示される。
【００２２】
ステップ５４５では、ＣＰ４００は、パケットを、第２のルーティング論理４７０を介して、負荷平衡化したオブジェクト４０〜６０の１つに転送する。パケットが属するフローのステータスが「古いので終了」と示されている場合、パケットは、新たなハッシュ・パラメータを用いたハッシュ計算の結果に転送される。その他の場合、パケットは、古いハッシュ・パラメータを用いたハッシュ計算の結果に転送される。
【００２３】
ステップ５４０において、フロー終了の検出に割り当てた時間間隔以上の時間間隔の後、ステップ５５０において、閾値検出器４９０は、所定の閾値に対して未終了の競合フローの数を調べる。閾値検出器４９０が、閾値として設定されたフロー以下の量を検出した場合、ステップ５６０において、未終了の全競合フローのローカル状態を「長生き」フロー状態テーブル４８０に移し、競合フロー状態テーブル４６０をクリアする。この場合、ステップ５６０において、「長生き」フロー状態テーブル４８０の内容は、負荷平衡器２００のフィルタ関数２３０に転送され、ハッシュ論理２４０の古いハッシュ・パラメータは除去される。ステップ５５０において、閾値検出器４９０が、閾値として設定されたフローよりも多い未終了競合フローを検出した場合、ＣＰ４００は負荷平衡器２００からのハッシュ競合パケットの受信を続ける。
【００２４】
ステップ５７０では、ＣＰ４００は、「長生き」フローに属するパケットのコピーを受信する。ステップ５８０では、ＣＰ４００は、パケットがＴＣＰ  ＦＩＮビット等のフローエンド・インジケータを有するか否か、または「長生き」フローが所定の間隔イナクティブであったか否かを判定するためにチェックを行う。双方の判定結果が否定である場合、ＣＰ４００はステップ５７０に戻り、「長生き」フローに属するパケットのコピーの受信を続ける。
【００２５】
ステップ５８０においてフローの終了が検出された場合、ステップ５８５において、「長生き」フロー・テーブル４８０およびフィルタ２３０の双方から、対応するフロー・エントリを除去する。ステップ５９０では、ＣＰ４００は、「長生き」フロー・テーブル４８０が空であるか否かを調べる。これが空であれば、ＣＰ４００のステータスは、ステップ５１０におけるフィードバック情報の蓄積に戻る。「長生き」フロー・テーブル４８０が空でない場合、ＣＰ４００はステップ５７０に戻り、「長生き」フローに属するパケットのコピーを受信する。
【００２６】
ＣＰ４００によって、ディープ・パケット処理を実行して、終了すると見なされる進行中のフローを識別することも可能である。例えば、ある状況では、進行中のフィルタ転送プロトコル（ＦＴＰ：File Transfer Protocol）フローを、不都合なく新たなサーバにルーティングすることができる。
【００２７】
ここで図５を参照すると、動作において、ステップ６００では、フィルタ２３０は、各入来パケットごとにフィルタ・ルールが設定されているかチェックする。イエスの場合、ステップ６１０において、フィルタ２３０は、ローカル・フィルタ・ルールに対してパケット・フロー識別子の照合を行う。フィルタ・ルールが存在しないか、またはルールが一致しない場合、ステップ６２０において、パケットをハッシュ論理２４０に転送する。パケットがフィルタ・ルールと一致した場合、一致したフィルタ・ルールに基づいて、ステップ６３０において、パケットにそのルーティング情報を結合する。ステップ６４０において、パケットをＣＰ４００にコピーし、ステップ６５０において、パケットを第１のルーティング論理２２０に送信する。
【００２８】
図６を参照すると、ハッシュ論理２４０では２つの状態が交互に生じる。すなわち、１組のハッシュ・パラメータが既知であるか、または１組の古いハッシュ・パラメータおよび１組の新しいハッシュ・パラメータが既知である状態である。ステップ７００において、ハッシュ論理２４０は、新しい１組のパラメータに基づいてハッシュ結果を計算する。ステップ７１０では、ハッシュ論理２４０は、古い１組のハッシュ・パラメータが存在するか否かを判定するためチェックを行う。古い１組のパラメータが存在しない場合、ステップ７２０において、パケットおよびハッシュ結果を第１のルーティング論理２２０に渡して、適切なターゲット・オブジェクト４０〜６０にパケットを送信する。古い１組のハッシュ・パラメータが存在する場合、ステップ７３０において、古い１組のパラメータに基づいて、ハッシュ結果を再び計算する。ステップ７４０では、ハッシュ結果をチェックして、双方のハッシュ計算が同一の結果を生じたか否かを判定する。同一の結果を生じた場合、適切なターゲット・オブジェクト４０〜６０にルーティングするため、ステップ７２０においてパケットを第１のルーティング論理２２０に渡す。同一の結果を生じない場合、ステップ７５０において、低速経路でルーティグするため、パケットおよび双方のハッシュ結果をＣＰ４００に渡す。
【００２９】
本明細書において述べた本発明の実施形態において、ネットワーク１３０における各インフラストラクチャ９０〜１１０は、負荷平衡化機能を備えている。しかしながら、ネットワーク１３０は、インフラストラクチャ・ノードの一部のみが負荷均衡機能を備えるように組み立てることも可能であることは認められよう。
【００３０】
データ通信ネットワークのための負荷平衡化装置は、入来データ・パケットに対してハッシュ関数を計算するためのハッシュ論理を備えている。ハッシュ論理に、閾値検出器が接続され、所定の閾値を超えた下流オブジェクトの利用に応答して、下流オブジェクト間でデータ・パケットを再分配させるため、ハッシュ論理において、第１組のパラメータから第２組のパラメータへの、ハッシュ関数のパラメータの再画定をトリガする。使用の際、ハッシュ論理は、使用の際、第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介してネットワークの下流オブジェクトにルーティングするためにパケットを送出し、閾値を超えた場合には、第１組および第２組のパラメータを用いた別個のハッシュ計算に応じて第１のルーティング経路および第２のルーティング経路の１つにパケットを選択的に送出し、以降、別個のハッシュ計算の１つの結果に基づいて第１および第２のルーティング経路のうち選択された１つを介してパケットをルーティングする。
【００３１】
まとめると、本発明の一例として本明細書中で述べてきたことは、データ通信ネットワークのための負荷均衡化装置２００であり、入来データ・パケットに対してハッシュ関数を計算するためのハッシュ論理２４０を備えている。ハッシュ論理２４０に、閾値検出器が４４０接続され、所定の閾値を超えた下流オブジェクトの利用に応答して、下流オブジェクト間でデータ・パケットを再分配させるため、ハッシュ論理２４０において、第１組のパラメータから第２組のパラメータへの、ハッシュ関数のパラメータの再画定をトリガする。使用の際、ハッシュ論理２４０は、第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介してネットワークの下流オブジェクトにルーティングするためにパケットを送出し、閾値を超えた場合には、第１組および第２組のパラメータを用いた別個のハッシュ計算に応じて第１のルーティング経路および第２のルーティング経路の１つにパケットを選択的に送出し、以降、別個のハッシュ計算の１つの結果に基づいて第１および第２のルーティング経路のうち選択された１つを介してパケットをルーティングする。しかしながら、本発明は、２組のハッシュ・パラメータに限定されないことは認められよう。本発明の別の実施形態では、ハッシュ論理２４０によって、３組以上のハッシュ・パラメータも使用可能である。
【図面の簡単な説明】
【００３２】
【図１】データ通信ネットワークのブロック図である。
【図２】データ通信ネットワークのインフラストラクチャ・ノードのブロック図である。
【図３】インフラストラクチャ・ノードの別のブロック図である。
【図４】インフラストラクチャ・ノードの制御点に関連したフローチャートである。
【図５】インフラストラクチャ・ノードの負荷平衡器に関連したフローチャートである。
【図６】インフラストラクチャ・ノードの負荷平衡器に関連した別のフローチャートである。
【図１】
2005536087.tif 000003
【図２】
2005536087.tif 000004
【図３】
2005536087.tif 000005
【図４】
2005536087.tif 000006
【図５】
2005536087.tif 000007
【図６】
2005536087.tif 000008
【手続補正書】
【提出日】平成16年6月24日(2004.6.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ通信ネットワークのための負荷平衡化装置であって、
入来データ・パケットに対してハッシュ関数を計算するハッシュ論理と、
前記ハッシュ論理に接続された閾値検出器であって、所定の閾値を超えた下流オブジェクトの利用に応答して、前記下流オブジェクト間で前記データ・パケットを再分配させるため、前記ハッシュ論理において、第１組のパラメータから第２組のパラメータへの、前記ハッシュ関数のパラメータの再画定をトリガする閾値検出器と、
を備え、前記ハッシュ論理は、使用の際、前記第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介して前記ネットワークの下流オブジェクトにルーティングするために前記パケットを送出し、更に、前記閾値を超えた場合には、前記第１組および前記第２組のパラメータを用いた別個のハッシュ計算に応じて前記第１のルーティング経路および第２のルーティング経路の１つに前記パケットを選択的に送出し、以降、前記別個のハッシュ計算の１つの結果に基づいて前記第１および第２のルーティング経路のうち選択された１つを介して前記パケットをルーティングするための手段を有する、負荷平衡化装置。
【請求項２】
前記ハッシュ論理は、使用の際、前記別個のハッシュ計算の結果が一致する場合には前記データ・パケットを前記第１のルーティング経路に送出するための手段を有し、その他の場合、前記データ・パケットを前記第２のルーティング経路に送出するための手段を有する、請求項１に記載の装置。  
【請求項３】
前記ハッシュ論理に接続され、所定の値を超えた寿命を有するフローについて、選択的に前記ハッシュ論理を迂回させるためのフィルタを更に備える、請求項１または２に記載の装置。  
【請求項４】
前記第１のルーティング経路および前記第２のルーティング経路を更に備え、前記第１のルーティング経路は前記ハッシュ論理に接続された第１のルーティング論理を備え、前記第２のルーティング経路は前記ハッシュ論理に接続された第２のルーティング論理を備え、前記第１のルーティング経路は前記第２のルーティング経路よりも高速であり、前記第２のルーティング経路上で、パケット・フロー・ステータスに基づいて下流オブジェクトを選択する、請求項１に記載の装置。
【請求項５】
前記第１のルーティング論理は少なくとも１つのネットワーク・プロセッサを備え、前記第２のルーティング論理は少なくとも１つの汎用プロセッサを備える、請求項４に記載の装置。
【請求項６】
前記第２のルーティング論理は、データ・パケットのフローにおいてフロー・デリミッタを検出し、開始インジケータを検出すると、前記第２組のパラメータを用いて前記ハッシュ関数に従って対応するフローをルーティングするように構成されている、請求項４または請求項５に記載の装置。
【請求項７】
前記第２のルーティング論理は、所定のイナクティブ時間を超えたパケットのフローを検出し、かかるフローを前記第２組のパラメータを用いて前記ハッシュ関数に従ってルーティングするように構成されている、請求項６に記載の装置。
【請求項８】
前記第２のルーティング論理は、所定の寿命を超えたパケットのフローを検出し、かかるフローを前記第１のルーティング論理に送出するように構成されている、請求項７に記載の装置。
【請求項９】
前出のいずれかの請求項に記載の負荷平衡化装置を備えた特定用途向け集積回路。
【請求項１０】
請求項１ないし７のいずれかに記載の負荷平衡化装置を備えたネットワーク・インフラストラクチャ・ノード。
【請求項１１】
請求項１０に記載のネットワーク・インフラストラクチャ・ノードを備えたデータ通信ネットワーク。
【請求項１２】
データ通信ネットワークにおける負荷平衡化の方法であって、
入来データ・パケットに対してハッシュ関数を計算するステップと、
所定の閾値を超えた下流オブジェクトの利用に応答して、前記下流オブジェクト間で前記データ・パケットを再分配させるため、第１組のパラメータから第２組のパラメータへの、前記ハッシュ関数のパラメータの再画定をトリガするステップと、
前記第１組のパラメータを用いたハッシュ計算に基づいて第１のルーティング経路を介して前記ネットワークの下流オブジェクトにルーティングするために前記パケットを送出し、前記閾値を超えた場合には、前記第１組および前記第２組のパラメータを用いた別個のハッシュ計算に応じて前記第１のルーティング経路および第２のルーティング経路の１つに前記パケットを選択的に送出し、以降、前記別個のハッシュ計算の１つの結果に基づいて前記第１および第２のルーティング経路のうち選択された１つを介して前記パケットをルーティングするステップと、
を備える、方法。
【請求項１３】
前記別個のハッシュ計算の結果が一致する場合には前記データ・パケットを前記第１のルーティング経路に送出し、その他の場合、前記データ・パケットを前記第２のルーティング経路に送出するステップを備える、請求項１２に記載の方法。  
【国際調査報告】
2005536087.tif 000009
2005536087.tif 000010
2005536087.tif 000011