(57)【特許請求の範囲】
【請求項１】
ネットワークから受信したパケットを複数の振り分け先に振り分け負荷を分散する負荷分散方法において、
振り分け配分の重み値と、前記受信したパケットを振り分けたとき前記重み値の逆数とセッションで実行される処理の重みの乗算値を積算した値であって振り分けに応じた積算値とを振り分け先毎に保持し、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける
ことを特徴とする負荷分散方法。
【請求項２】
ネットワークから受信したパケットを複数の振り分け先に振り分け負荷を分散する負荷分散装置において、
振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持する保持手段と、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける振り分け手段とを有し、
前記積算値は、前記受信したパケットを振り分けたとき前記重み値の逆数とセッションで実行される処理の重みの乗算値を積算した値であることを特徴とする負荷分散装置。
【請求項３】
ネットワークから受信したパケットを複数の振り分け先に振り分け負荷を分散する負荷分散装置において、
振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持する保持手段と、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける振り分け手段とを有し、
前記積算値は、前記受信したパケットを振り分けたとき前記重み値の逆数とパケットのファイルタイプの重みの乗算値を積算した値であることを特徴とする負荷分散装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、負荷分散方法及びその装置に関し、ネットワーク内におけるノード間リンクおよび処理用サーバヘの負荷分散方法及びその装置に関する。
【０００２】
【従来の技術】
インターネットで転送または処理されるパケット量の急増に伴い，１本のリンクでは転送できないほどの潜在的なパケット転送能力や，１つのサーバでは処理できないほどの潜在的なパケット処理能力が求められており、これらのパケットを複数のリンクやサーバにおいて負荷分散して転送または処理することが求められてきている。また、これらの複数のリンクやサーバは、通常処理能力が異なるため、その処理能力比に応じてパケットを振り分ける必要がある。
【０００３】
図１は、従来の負荷分散装置の一例の構成図、図２は、図１における出力選択の様子を示す図である。同図中、ネットワークから受信したパケットはスイッチ部１０に供給され、これと共にパケットのアドレス等がキーとしてハッシュ関数生成部１２に供給される。ハッシュ関数生成部１２はこのキーにハッシュ関数を適用して例えば値が０〜９９の乱数を生成し、出力決定部１４に供給する。出力決定部１４には、値０〜４９に対応して出力端子１６ａ、値５０〜７９に対応して出力端子１６ｂ、値８０〜９９に対応して出力端子１６ｃそれぞれを選択するように各出力の重みが予め設定されており、出力決定部１４はハッシュ関数生成部１２からの値に応じた選択指示信号をスイッチ部１０に供給する。スイッチ部１０はこの選択指示信号に従って、供給されるパケットをスイッチングし、このパケットは出力端子１６ａ，１６ｂ，１６ｃのいずれかから重みに応じて割り当てておいたリンクもしくはサーバに振り分ける。
【０００４】
図３は、従来の負荷分散装置の他の一例の構成図、図４は、図３における出力選択の様子を示す図である。同図中、ネットワークから受信したパケットはスイッチ部２０及び出力決定部２２に供給される。出力決定部２２には出力端子２４ａ，２４ｂ，２４ｃそれぞれに行が設けられ、各行にパケットの割当数と重み値が設定されたテーブル２６が設けられている。
【０００５】
出力決定部２２は、パケットが供給される毎にテーブル２２のポインタ２８が指示する行を検索し、検索した行の割当数と重み値とを読み出して比較部３０で比較する。比較部３０は割当数が重み値以上となるとポインタ２８に次の行を指示するようにスキップを指示する。割当数が重み値未満であれば出力決定部２２は、その行に対応する出力端子の選択指示信号をスイッチ部２０に供給する。スイッチ部２０はこの選択指示信号に従って、供給されるパケットをスイッチングし、このパケットは出力端子２４ａ，２４ｂ，２４ｃのいずれかから重みに応じて割り当てておいたリンクもしくはサーバに振り分ける。
【０００６】
なお、テーブル２２の全ての行の割当数が重み値以上となったとき、全ての行の割当数が０にリセットされる。
【０００７】
【発明が解決しようとする課題】
図１の従来例においては、キーとハッシュ関数の偏りにより、ハッシュ関数を適用した結果の乱数に偏りが生じ、重み値の比通りに各リンクもしくはサーバにパケットを割り当てるためには、実際にリンクもしくはサーバに割り当てたパケット数の集計と、ハッシュ関数を適用した乱数毎に割り当てるリンクもしくはサーバの周期的な調整が必要となる。さらに、乱数がランダムであっても短期間では確率的に偏りが生じる可能性があり長期レンジでなければ重みに従った適切な負荷分散ができないという問題点があった。
【０００８】
図３の従来例においては、重みの絶対値の差が大きい場合には、重み値が小さなリンクもしくはサーバへの割当が終了したのち割当数がリセットされるまでの期間では、重み値が大きなリンクもしくはサーバへの割当が集中するという問題があった。
【０００９】
本発明は、上記の点に鑑みなされたものであり、振り分け先のリンクもしくはサーバに対し、任意の時間において重み値に比例してできるだけ均一にパケットを振り分けることができる負荷分散方法及びその装置を提供することを目的とする。
【００１０】
【課題を解決するための手段】
請求項１に記載の発明は、振り分け配分の重み値と、前記受信したパケットを振り分けたとき前記重み値の逆数とセッションで実行される処理の重みの乗算値を積算した値であって振り分けに応じた積算値とを振り分け先毎に保持し、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分けることにより、
各振り分け先で実行される処理の重みに応じて、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００１１】
請求項２に記載の発明は、振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持する保持手段と、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける振り分け手段とを有し、
前記積算値は、前記受信したパケットを振り分けたとき前記重み値の逆数とセッションで実行される処理の重みの乗算値を積算した値であることにより、
各振り分け先で実行される処理の重みに応じて、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００１２】
また、積算値は、重み値の逆数を積算することにより、
振り分け先毎の積算値を比較する前に加算を行うだけで済み、かけ算や割り算を行う必要がなく高速の振り分けを行うことができる。
【００１３】
また、積算値は、前記重み値の逆数とパケット長の積を積算することにより、
振り分けた各パケットのパケット長に応じて、重み値に比例してできるだけ均一にすることができる。
【００１５】
請求項３に記載の発明では、振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持する保持手段と、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける振り分け手段とを有し、
前記積算値は、前記受信したパケットを振り分けたとき前記重み値の逆数とパケットのファイルタイプの重みの乗算値を積算した値であることにより、
振り分けた各パケットのファイルタイプの重みに応じて、重み値に比例してできるだけ均一にすることができる。
【００１６】
付記７に記載の発明では、振り分けイベントは、パケットの受信により発生することにより、
パケット単位で、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００１７】
付記８に記載の発明では、振り分けイベントは、セッションの開始により発生することにより、
セッション単位で、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００１８】
請求項４に記載の発明では、保持手段は、前記積算値をキーとしてソートされていることにより、
振り分け先毎の積算値を比較する必要がなく高速の振り分けを行うことができる。
【００１９】
【発明の実施の形態】
図５は、インターネットおける処理サーバへの割り当てセッション数に基づいた負荷分散を行う本発明の負荷分散装置の第１実施例のブロック図を示す。この実施例では、負荷分散はセッション毎に行う。図５において、出力先決定部４２内のテーブル５７には、出力先のサーバＳ１，Ｓ２，Ｓ３それぞれに行が設けられ、各行に累積値（バイト数）と重み値の逆数が設定されている。ここでは、それぞれの重み値の逆数を例えば１／１０，１／６，１／４とし、累積値はそれぞれの重み値の逆数の１／２、つまり、１／２０，１／１２，１／８に設定されている。
【００２０】
図５に示すように、イベント検出部４０は、最初のＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）のコネクション確立要求のＳｙｎパケットなどによりセッションの開始を検出し、出力先決定部４２に通知する。出力先決定部４２においては、最小値判定部４９で各サーバ毎の積算値を比較し、積算値が最小であるサーバＳ１に当該セッションを割り当てて出力部４４に通知すると共に、サーバＳ１の積算値に重み値の逆数である１／１０を加算する。出力部４４では、イベント検出部４０を通して供給されるパケットを出力先決定部４２で割り当てられたサーバＳ１に向けて出力する。
【００２１】
以降、イベント検出部４０においてセッションの開始を検出する毎に、出力先決定部４２において、図６に示すように各サーバの積算値を更新しながら、積算値に基づいて出力先のサーバを決定し、出力部４４が該当サーバにパケットを転送し、それぞれのサーバＳ１，Ｓ２，Ｓ３ヘの割当セッション数が、５：３：２＝１０：６：４となる。なお、図６にはテーブル５７のうちの各サーバ毎の積算値だけを記載している。
【００２２】
上記実施例では、重み値の逆数を積算することにより、振り分け先毎の積算値を比較する前に加算を行うだけで済み、かけ算や割り算を行う必要がなく高速の振り分けを行うことができる。また、セッションの開始タイミングで、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００２３】
なお、上記実施例では、積算値の初期値を各サーバの重み値の逆数の１／２としたが、積算値の初期値は全て０でもよいし、重みの逆数値といったように任意の値でも良い。
【００２４】
また、この実施例では積算値は、イベント検出部４０においてセッションの開始と共に、このセッションで実行されるアプリケーション（処理）を判別し、出力先決定部４２で上記アプリケーションに応じ各サーバの重み値の逆数に予め定められたアプリケーション毎の重みを乗算した値を、積算値として積算する構成としても良い。ここでは、受信パケットが例えば「ｈｔｔｐ」または「ｆｔｐ」である場合、ｈｔｔｐのパケットについてはアプリケーションの重みを「２」とし、「ｆｔｐ」のパケットについてはアプリケーションの重みを「１」とする。これによって、各振り分け先で実行される処理に重みに応じて、重み値に比例してできるだけ均一にすることができる。
【００２５】
また、出力先決定部４２でアプリケーションの代わりに、パケットが画像ファイルか、テキストファイルか、動画ファイルか等のファイル種別を判別し、出力先決定部４２では上記ファイル種別に応じ、各サーバの重み値の逆数に、例えば画像ファイルは「５０」、テキストファイルは「５」、動画ファイルは「２００」のようにファイル種別毎の重みを乗算した値を、積算値に積算する構成としても良い。これによって、振り分けた各パケットのファイルタイプの重みに応じて、重み値に比例してできるだけ均一にすることができる。
【００２６】
更に、イベント検出部４０ではパケットの受信毎に出力先決定部４２に対しイベント通知を行い、出力先決定部４２では、各サーバの重み値の逆数に受信したパケットのパケット長を乗算した値を、積算値に積算する構成としても良い。これによって、振り分けた各パケットのパケット長に応じて重み値に比例してできるだけ均一にすることができる。
【００２７】
図７は、インターネットおける処理サーバへの割り当てセッション数に基づいた負荷分散を行う本発明の負荷分散装置の第２実施例のブロック図を示す。この実施例では、負荷分散はセッション毎に行う。同図中、図５と同一部分には同一符号を付す。図７において、出力先決定部４２内のテーブル６７には、出力先のサーバＳ１，Ｓ２，Ｓ３それぞれに行が設けられ、各行に累積値（バイト数）と重み値の逆数が設定されている。ここでは、それぞれの重み値の逆数を例えば１／１０，１／６，１／４とし、累積値は全て０に設定されている。このテーブル６７は累積値が昇順となるように各行をソートするソート機能を有している。そして、最上行（積算値が最小）のサーバの番号を出力部４４に通知する。
【００２８】
図７に示すように、イベント検出部４０は、最初のＴＣＰのＳｙｎパケットなどによりセッションの開始を検出し、出力先決定部４２に通知する。出力先決定部４２においては、最上行のサーバＳ１に当該セッションを割り当て出力部４４に通知する。これと共に、サーバＳ１の積算値に重み値の逆数である１／１０を加算し、加算後の積算値１／１０をそれより大きな積算値が出るまでバブルソートの手順で各行の積算値と比較して下の行に移動させる。これによって、テーブル６７は最上行の積算値が最小となるようにソートされる。出力部４４では、イベント検出部４０を通して供給されるパケットを出力先決定部４２で割り当てられたサーバＳ１に向けて出力する。
【００２９】
図８に示すように、２番目のパケットとして、最初のパケットと同一のセッションのパケットが到着すると、イベント検出部４０はそのパケットを出力部４４を通して同一のサーバＳ１に転送すると共に、出力先決定部４２に積算値の加算を指示する。出力先決定部４２においては、テーブル６７のサーバＳ１の積算値に重みの逆数１／１０を加算し、またソートを行う。
【００３０】
以降、図９に示すように、イベント検出部４０において、新たなセッション開始が検出された場合には、出力先決定部４２において、テーブル６７でソートした最小の積算値を持つサーバＳ２を選択すると共に、積算値への重みの逆数の加算とソートを行う。また、開始が既に検出されたセッションと同一セッションのパケットの到着時には、出力先決定部４２において、積算値の加算とソートのみを行うことにより、セッション単位でパケットが各サーバに振り分けられる。そして、最終的に、各サーバＳ１，Ｓ２，Ｓ３に転送されたパケット数が１０：６：４となる。
【００３１】
この実施例では、テーブル６７は最上行の積算値が最小となるようにソートされているため、振り分け先毎の積算値を比較する必要がなく高速の振り分けを行うことができる。
【００３２】
ところで、上記の第１，第２実施例では、インターネットおける処理サーバへの割り当てセッション数に基づいた負荷分散を行っているが、インターネットのルータに設けられ、マルチリンクにおいて総転送パケット長に基づいて負荷分散を行うものであっても良い。この場合、イベント検出部４０は例えばパケットが到着する毎にパケット到着を出力決定部４２に通知し、各リンクの積算値を更新しながら、積算値に基づいて出力先のリンクを決定し、出力部４４は該当リンクにパケットを転送する。
【００３３】
なお、テーブル５７，６７が請求項記載の保持手段に対応し、出力先決定部４２及び出力部４４が振り分け手段に対応する。
【００３４】
（付記１）  ネットワークから受信したパケットを複数の振り分け先に振り分け負荷を分散する負荷分散方法において、
振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持し、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける
ことを特徴とする負荷分散方法。
【００３５】
（付記２）  ネットワークから受信したパケットを複数の振り分け先に振り分け負荷を分散する負荷分散装置において、
振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持する保持手段と、
振り分けイベントの発生時に、前記積算値が最小の振り分け先に前記受信したパケットを振り分ける振り分け手段とを
有することを特徴とする負荷分散装置。
【００３６】
（付記３）  付記２記載の負荷分散装置において、
前記積算値は、前記重み値の逆数を積算することを特徴とする負荷分散装置。
【００３７】
（付記４）  付記２記載の負荷分散装置において、
前記積算値は、前記重み値の逆数とパケット長の積を積算することを特徴とする負荷分散装置。
【００３８】
（付記５）  付記２記載の負荷分散装置において、
前記積算値は、前記重み値の逆数とセッションで実行される処理の重みの積を積算することを特徴とする負荷分散装置。
【００３９】
（付記６）  付記２記載の負荷分散装置において、
前記積算値は、前記重み値の逆数とパケットのファイルタイプの重みの積を積算することを特徴とする負荷分散装置。
【００４０】
（付記７）  付記２乃至６のいずれか記載の負荷分散装置において、
前記振り分けイベントは、パケットの受信により発生することを特徴とする負荷分散装置。
【００４１】
（付記８）  付記２乃至６のいずれか記載の負荷分散装置において、
前記振り分けイベントは、セッションの開始により発生することを特徴とする負荷分散装置。
【００４２】
（付記９）  付記２記載の負荷分散装置において、
前記保持手段は、前記積算値をキーとしてソートされていることを特徴とする負荷分散装置。
【００４３】
【発明の効果】
上述の如く、請求項１に記載の発明は、振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持し、振り分けイベントの発生時に、積算値が最小の振り分け先に受信したパケットを振り分けることにより、各振り分け先に対し、任意の時間において重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００４４】
請求項２に記載の発明は、振り分け配分の重み値と、振り分けに応じた積算値とを振り分け先毎に保持する保持手段と、振り分けイベントの発生時に、積算値が最小の振り分け先に受信したパケットを振り分ける振り分け手段とを有することにより、各振り分け先に対し、任意の時間において重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００４５】
請求項３に記載の発明では、積算値は、重み値の逆数を積算することにより、振り分け先毎の積算値を比較する前に加算を行うだけで済み、かけ算や割り算を行う必要がなく高速の振り分けを行うことができる。
【００４６】
請求項４に記載の発明では、積算値は、重み値の逆数とパケット長の積を積算することにより、振り分けた各パケットのパケット長に応じて、重み値に比例してできるだけ均一にすることができる。
【００４７】
請求項５に記載の発明では、積算値は、重み値の逆数とセッションで実行される処理の重みの積を積算することにより、各振り分け先で実行される処理に重みに応じて、重み値に比例してできるだけ均一にすることができる。
【００４８】
付記６に記載の発明では、積算値は、重み値の逆数とパケットのファイルタイプの重みの積を積算することにより、振り分けた各パケットのファイルタイプの重みに応じて、重み値に比例してできるだけ均一にすることができる。
【００４９】
付記７に記載の発明では、振り分けイベントは、パケットの受信により発生することにより、パケット単位で、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００５０】
付記８に記載の発明では、振り分けイベントは、セッションの開始により発生することにより、セッション単位で、重み値に比例してできるだけ均一にパケットを振り分けることができる。
【００５１】
付記９に記載の発明では、保持手段は、積算値をキーとしてソートされていることにより、振り分け先毎の積算値を比較する必要がなく高速の振り分けを行うことができる。
【図面の簡単な説明】
【図１】従来の負荷分散装置の一例の構成図である。
【図２】図１における出力選択の様子を示す図である。
【図３】従来の負荷分散装置の他の一例の構成図である。
【図４】図３における出力選択の様子を示す図である。
【図５】本発明の負荷分散装置の第１実施例のブロック図である。
【図６】本発明の負荷分散装置の第１実施例における各サーバの積算値の更新を説明するための図である。
【図７】本発明の負荷分散装置の第２実施例のブロック図である。
【図８】本発明の負荷分散装置の第２実施例における各サーバの積算値の更新を説明するための図である。
【図９】本発明の負荷分散装置の第２実施例における各サーバの積算値の更新を説明するための図である。
【符号の説明】
４０  イベント検出部
４２  出力先決定部
４４  出力部
５７，６７  テーブル
【図１】
0004417582.tif 000002
【図２】
0004417582.tif 000003
【図３】
0004417582.tif 000004
【図４】
0004417582.tif 000005
【図５】
0004417582.tif 000006
【図６】
0004417582.tif 000007
【図７】
0004417582.tif 000008
【図８】
0004417582.tif 000009
【図９】
0004417582.tif 000010