(57)【特許請求の範囲】
【請求項１】
パケットの宛先アドレスをもとにスイッチングを行う伝送装置において、
前記パケットのハッシュパラメータにもとづき、負荷分散グループを検索する負荷分散グループ検索部と、
前記負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比と、を含む負荷分散比設定テーブルと、
前記負荷分散比設定テーブルを用いて、検索された前記負荷分散グループに対応する前記負荷分散比を検索する負荷分散比検索部と、
前記ハッシュパラメータにもとづき、ハッシュ演算を施して、前記パケットに対応するハッシュ値を算出するハッシュ演算部と、
検索された前記負荷分散比の端から前記ハッシュ値を数えたところまでに存在する前記特定ビットの個数により、方路選択番号を決定する方路選択番号決定部と、
検索された前記負荷分散グループと、前記方路選択番号とにもとづいて、パケットの出力方路情報を決定する出力方路情報決定部と、
を有することを特徴とする伝送装置。
【請求項２】
前記負荷分散比設定テーブルは、分散粒度の値に対応するビット幅を持つ前記負荷分散比が登録されることを特徴とする請求項１記載の伝送装置。
【請求項３】
前記ハッシュ演算部は、分散粒度の値を２進数で表記したときのビット幅を、前記ハッシュ値が必要なビット幅とすることを特徴とする請求項１記載の伝送装置。
【請求項４】
ＭＰＬＳのラベルスイッチングを行う伝送装置において、
パケットのハッシュパラメータにもとづき、負荷分散グループを検索する負荷分散グループ検索部と、
前記負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比と、を含む負荷分散比設定テーブルと、
前記負荷分散比設定テーブルを用いて、検索された前記負荷分散グループに対応する前記負荷分散比を検索する負荷分散比検索部と、
前記ハッシュパラメータにもとづき、ハッシュ演算を施して、前記パケットに対応するハッシュ値を算出するハッシュ演算部と、
検索された前記負荷分散比の端から前記ハッシュ値を数えたところまでに存在する前記特定ビットの個数により、方路選択番号を決定する方路選択番号決定部と、
検索された前記負荷分散グループと、前記方路選択番号とにもとづいて、前記パケットを出力すべきＬＳＰ情報を決定する出力方路情報決定部と、
を有することを特徴とする伝送装置。
【請求項５】
前記負荷分散比設定テーブルは、分散粒度の値に対応するビット幅を持つ前記負荷分散比が登録されることを特徴とする請求項４記載の伝送装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は伝送装置に関し、特に、伝送路上を流れるパケットの負荷分散を行って、パケットの伝送を行う伝送装置に関する。
【０００２】
【従来の技術】
近年、インターネットの急速な普及により、ネットワーク・トポロジーが複雑化し、かつ情報量も著しく増加しており、ネットワークの広帯域化及び伝送路の冗長構成等による高信頼性化が求められている。そのため、ネットワーク内のノード間の接続形態としては、マルチリンクやメッシュで接続されることが多くなっている。
【０００３】
このような状況の中で、ネットワーク帯域を効率よく使って、パケットの遅延や損失を防ぐためには、伝送路上の負荷を分散する必要があり、通常、ハッシュ（Hash）演算を用いた負荷分散制御が広く行われている。ハッシュ演算とは、与えられた原文（データ）から固定長の疑似乱数を生成する演算手法のことであり、生成した擬似乱数値はハッシュ値と呼ばれる。
【０００４】
図７は従来の負荷分散制御の概要を示す図である。図に示すテーブル２００は、０〜１５までの数を４つに分割して、区間ｋ１〜ｋ４を形成しており、区間ｋ１〜ｋ４のそれぞれは、出力方路の番号＃１〜＃４が記載されている。
【０００５】
従来の負荷分散制御としては、まず、受信したパケット１００のヘッダ内にある情報をハッシュ演算して、ハッシュ値を求める。そして、複数の区間毎に各出力方路番号が記載されたテーブル２００に対して、算出されたハッシュ値がどの区間内に含まれるかを検索して、パケット１００が出力されるべき方路を決定する。
【０００６】
例えば、パケット１００のハッシュ値が５であったならば、４〜７の区間ｋ２に該当するので、パケット１００は、番号＃２の方路から出力されることになる。このような制御を行うことで、各伝送路上の負荷を分散することができる。
【０００７】
【発明が解決しようとする課題】
しかし、上記のような従来の負荷分散制御では、テーブル２００は、出力方路数分の区間を用意し、算出したハッシュ値がどの区間に含まれるかを、区間ｋ１から逐一比較していかなければならない。このため、出力方路数が多くなると、ハードウェア構成が複雑となり、また高速に出力方路を決定することができないといった問題があった。
【０００８】
本発明はこのような点に鑑みてなされたものであり、負荷分散制御を効率よく行って、出力方路を高速に決定する伝送装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明では上記課題を解決するために、図１に示すような、パケットの宛先アドレスをもとにスイッチングを行う伝送装置１０において、パケットのハッシュパラメータにもとづき、負荷分散グループを検索する負荷分散グループ検索部１１と、負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比と、を含む負荷分散比設定テーブルＴ１と、負荷分散比設定テーブルＴ１を用いて、検索された負荷分散グループに対応する負荷分散比を検索する負荷分散比検索部１２と、ハッシュパラメータにもとづき、ハッシュ演算を施して、入力パケットに対応するハッシュ値を算出するハッシュ演算部１３と、検索された負荷分散比の端からハッシュ値を数えたところまでに存在する特定ビットの個数により、方路選択番号を決定する方路選択番号決定部１４と、検索された負荷分散グループと、方路選択番号とにもとづいて、パケットの出力方路情報を決定する出力方路情報決定部１５と、を有することを特徴とする伝送装置１０が提供される。
【００１０】
ここで、負荷分散グループ検索部１１は、パケットのハッシュパラメータにもとづき、負荷分散グループを検索する。負荷分散比設定テーブルＴ１は、負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比とを含む。負荷分散比検索部１２は、負荷分散比設定テーブルＴ１を用いて、検索された負荷分散グループに対応する負荷分散比を検索する。ハッシュ演算部１３は、ハッシュパラメータにもとづき、ハッシュ演算を施して、入力パケットに対応するハッシュ値を算出する。方路選択番号決定部１４は、検索された負荷分散比の端からハッシュ値を数えたところまでに存在する特定ビットの個数により、方路選択番号を決定する。出力方路情報決定部１５は、検索された負荷分散グループと、方路選択番号とにもとづいて、パケットの出力方路情報を決定する。
【００１１】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。図１は本発明の伝送装置の原理図である。伝送装置１０は、パケットの宛先アドレスをもとにスイッチングを行って、パケット伝送を行う装置であり、例えば、マルチリンク接続またはメッシュ接続されたネットワーク内に配置されたＩＰルータ等に適用可能である。
【００１２】
負荷分散グループ検索部１１は、パケットのハッシュパラメータ（ヘッダ内に含まれるＤＡ（送信先アドレス））にもとづき、負荷分散グループを検索する。具体的には、負荷分散グループ検索部１１は、ＤＡの値と負荷分散グループの値とが対応した内部テーブルを有しており、この内部テーブルから負荷分散グループを求めることになる。
【００１３】
負荷分散比検索部１２は、負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比とから構成される負荷分散比設定テーブルＴ１を用いて、検索された負荷分散グループに対応する負荷分散比を取り出す。
【００１４】
ハッシュ演算部１３は、ハッシュパラメータ（ヘッダ内に含まれるＤＡ及びＳＡ（送信元アドレス））にもとづき、ハッシュ演算を施して、１つの入力パケットに対応する１つのハッシュ値を算出する。
【００１５】
方路選択番号決定部１４は、検索された負荷分散比の端からハッシュ値を数え、数えたところまでに存在する特定ビットの個数により、方路選択番号を決定する。例えば、図では負荷分散比の最下位ビットからハッシュ値までを数えたときに、特定ビット（△マーク）が１つあるので、方路選択番号が１と決定されている。
【００１６】
出力方路情報決定部１５は、検索された負荷分散グループと、方路選択番号とにもとづいて、パケットの出力方路情報（パケットが出力される物理ポートの番号など）を決定する。
【００１７】
次に負荷分散比設定テーブルＴ１について説明する。図２は負荷分散比設定テーブルＴ１を示す図である。負荷分散比設定テーブルＴ１には、負荷分散グループに対応した負荷分散比が登録される。
【００１８】
例えば、負荷分散グループ３に対して、負荷分散比は“0101000100000000”となっている。この負荷分散比のビット幅は、分散粒度に対応しており、この場合、分散粒度は１６としているので、負荷分散比のビット幅は１６ビットとなっている。なお、分散粒度とは、分散比の細かさのことで、分散粒度がＮならば、１／Ｎの単位で負荷分散を行うことが可能である。
【００１９】
次にハッシュ演算部１３について説明する。図３はハッシュ値算出を説明するための図である。ハッシュ演算部１３では、ハッシュ演算をする際に、受信したパケットのＤＡとＳＡをハッシュ・パラメータとして、ハッシュ値を求める。
【００２０】
また、分散粒度を２進数で表記したときのビット幅がハッシュ値として必要なビット幅となる。例えば、分散粒度が１６ならば、ハッシュ値は０〜１５の値を取りうる必要があるので、これを２進数に直すと“0000”〜“1111”となり、ハッシュ値としては４ビット必要となる。
【００２１】
次に負荷分散比設定テーブルＴ１で登録される負荷分散比の設定について説明する。図４は負荷分散比の設定例を示す図である。方路選択番号０、１、２、３の負荷分散比を４：２：１：１とし、分散粒度は１６とする。すると、この場合の方路選択番号に対する比率は８：４：２：２となる。
【００２２】
したがって、負荷分散比に応じた方路選択番号０〜３の分岐比は、方路選択番号０は８／１６、方路選択番号１は４／１６、方路選択番号２は２／１６、方路選択番号３は２／１６となり、これを境界値に直すと図に示すように、方路選択番号０と１の境界値は８、方路選択番号１と２の境界値は１２（＝８＋４）、方路選択番号２と３の境界値は１４（＝８＋４＋２）となる。
【００２３】
したがって、負荷分散比の設定は特定ビットを“１”として、各方路間の境界値に対応するビットに設定すればよく、最下位ビットを０ビット目からとして、８ビット目、１２ビット目、１４ビット目に“１”を設定することで、負荷分散比は“0101000100000000”となる。
【００２４】
なお、この例では、出力方路数を４としているため、方路選択番号は４つしかないので方路選択番号０〜３を用いているが、１つの負荷分散比で設定可能な方路選択番号の数（分散方路数）は分散粒度で決定する。すなわち、分散粒度が１６ならば１〜１６の方路選択が可能である。
【００２５】
次に方路選択番号の決定処理について説明する。図５は方路選択番号の決定処理を示す図である。負荷分散比設定テーブルＴ１より得られた負荷分散比の最下位ビットから、ハッシュ演算部１３で求めたハッシュ値まで数えたとき、“１”がいくつあるかで方路選択番号は決定される。
【００２６】
ここでは、パケットの負荷分散比が“0101000100000000”で、ハッシュ値が“1100”（＝１２）であるので、負荷分散比の最下位ビットを０ビット目とし、１２ビット目まで数えると“１”が２個あるため、方路選択番号は２となる。
【００２７】
次に出力方路情報決定部１５について説明する。図６は出力方路設定テーブルを示す図である。出力方路情報決定部１５は、内部テーブルとして、出力方路設定テーブルＴ２を有する。
【００２８】
出力方路情報決定部１５は、負荷分散グループ検索部１１で検索された負荷分散グループと、方路選択番号決定部１４で決定された方路選択番号とにもとづき、出力方路設定テーブルＴ２を用いて、パケットの出力方路情報を決定する。図の場合、負荷分散グループ０で方路選択番号が２では、出力方路情報＃２が決定される。
【００２９】
以上説明したように、本発明の伝送装置１０では、負荷分散グループ毎の負荷分散比をビット配列で設定し、ビットの位置によって境界値を表し、ハッシュ値まで数えたところに存在する特定ビットの個数により、方路選択番号を決定し、その後、出力方路情報を決定する構成とした。これにより、ハッシュ値と境界値との比較回路を持たなくてすむため、回路規模を削減でき、かつ高速に出力方路を決定することが可能になる。
【００３０】
なお、本発明の伝送装置１０の適用装置を考えた場合、ＭＰＬＳ（Multi-Protocol Label Switching）のラベルスイッチングを行う装置に適用することができる。ＭＰＬＳは、上位層を使わずにレイヤ２で直結してパケット転送を実現する技術である。
【００３１】
このような装置に対して、エッジ−エッジ間に複数設定されているＬＳＰ（Label Switched Path）のトラフィック量が一定になるように、本発明を適用することにより、ＴＥ（Traffic Engineering）のロードバランシング制御を高速に行うことが可能になる。
【００３２】
（付記１）  パケットの宛先アドレスをもとにスイッチングを行う伝送装置において、
前記パケットのハッシュパラメータにもとづき、負荷分散グループを検索する負荷分散グループ検索部と、
前記負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比と、を含む負荷分散比設定テーブルと、
前記負荷分散比設定テーブルを用いて、検索された前記負荷分散グループに対応する前記負荷分散比を検索する負荷分散比検索部と、
前記ハッシュパラメータにもとづき、ハッシュ演算を施して、前記パケットに対応するハッシュ値を算出するハッシュ演算部と、
検索された前記負荷分散比の端から前記ハッシュ値を数えたところまでに存在する前記特定ビットの個数により、方路選択番号を決定する方路選択番号決定部と、
検索された前記負荷分散グループと、前記方路選択番号とにもとづいて、パケットの出力方路情報を決定する出力方路情報決定部と、
を有することを特徴とする伝送装置。
【００３３】
（付記２）  前記負荷分散比設定テーブルは、分散粒度の値に対応するビット幅を持つ前記負荷分散比が登録されることを特徴とする付記１記載の伝送装置。
（付記３）  前記ハッシュ演算部は、分散粒度の値を２進数で表記したときのビット幅を、前記ハッシュ値が必要なビット幅とすることを特徴とする付記１記載の伝送装置。
【００３４】
（付記４）  ＭＰＬＳのラベルスイッチングを行う伝送装置において、
パケットのハッシュパラメータにもとづき、負荷分散グループを検索する負荷分散グループ検索部と、
前記負荷分散グループと、出力方路間の境界値に対応する特定ビットを含みビット配列で表された負荷分散比と、を含む負荷分散比設定テーブルと、
前記負荷分散比設定テーブルを用いて、検索された前記負荷分散グループに対応する前記負荷分散比を検索する負荷分散比検索部と、
前記ハッシュパラメータにもとづき、ハッシュ演算を施して、前記パケットに対応するハッシュ値を算出するハッシュ演算部と、
検索された前記負荷分散比の端から前記ハッシュ値を数えたところまでに存在する前記特定ビットの個数により、方路選択番号を決定する方路選択番号決定部と、
検索された前記負荷分散グループと、前記方路選択番号とにもとづいて、前記パケットを出力すべきＬＳＰ情報を決定する出力方路情報決定部と、
を有することを特徴とする伝送装置。
【００３５】
（付記５）  前記負荷分散比設定テーブルは、分散粒度の値に対応するビット幅を持つ前記負荷分散比が登録されることを特徴とする付記４記載の伝送装置。
（付記６）  前記ハッシュ演算部は、分散粒度の値を２進数で表記したときのビット幅を、前記ハッシュ値が必要なビット幅とすることを特徴とする付記４記載の伝送装置。
【００３６】
【発明の効果】
以上説明したように、本発明の伝送装置は、入力パケットのハッシュパラメータから得られる負荷分散比とハッシュ値にもとづき、検索された負荷分散比の端からハッシュ値を数えたところまでに存在する特定ビットの個数により方路選択番号を決定する。そして、負荷分散グループ及び方路選択番号から、パケットの出力方路情報を決定する構成とした。これにより、負荷分散のための出力方路決定処理を効率よく高速に行うことが可能になる。
【図面の簡単な説明】
【図１】本発明の伝送装置の原理図である。
【図２】負荷分散比設定テーブルを示す図である。
【図３】ハッシュ値算出を説明するための図である。
【図４】負荷分散比の設定例を示す図である。
【図５】方路選択番号の決定処理を示す図である。
【図６】出力方路設定テーブルを示す図である。
【図７】従来の負荷分散制御の概要を示す図である。
【符号の説明】
１０  伝送装置
１１  負荷分散グループ検索部
１２  負荷分散比検索部
１３  ハッシュ演算部
１４  方路選択番号決定部
１５  出力方路情報決定部
Ｔ１  負荷分散比設定テーブル
【図１】
0003910451.tif 000002
【図２】
0003910451.tif 000003
【図３】
0003910451.tif 000004
【図４】
0003910451.tif 000005
【図５】
0003910451.tif 000006
【図６】
0003910451.tif 000007
【図７】
0003910451.tif 000008