(57)【特許請求の範囲】
【請求項１】
検索キーが、エントリされたフィルタ条件を満足するか否かを比較判定するためのフィルタ条件比較方法において、
前記検索キーの値のとり得る範囲を２以上の所定の自然数で分割することによって得られる分割領域毎に、前記検索キーのフィルタ条件をテーブルにエントリしておく第１のステップと、
入力された検索キーの値と、当該キーの値が含まれる分割領域に対応するフィルタ条件とを比較して前記検索キー値が満足するフィルタ条件を求める第２のステップとを有することを特徴とするフィルタ条件比較方法。
【請求項２】
複数種類の検索キーがある場合に、前記各種類の入力された検索キーにおいて、
前記第１のステップおよび第２のステップをそれぞれ実行するステップと、
全種類の入力された検索キーが満足するフィルタ条件を求める第３のステップと、
前記第３のステップで求められたフィルタ条件に対応するフィルタ条件ＩＤリストのうち、所定の優先度に基づいて、最も優先度の高いフィルタ条件ＩＤを選択する第４のステップを有する請求項１記載のフィルタ条件比較方法。
【請求項３】
前記テーブルの各フィルタ条件のエントリに、当該フィルタ条件の種別を特定するための演算コードを指定しておく請求項１または２記載のフィルタ条件比較方法。
【請求項４】
前記演算コードに、完全一致が指定されている場合には、当該フィルタ条件のエントリに、前記検索キーとの論理積演算を行なうためのビットマスク値を登録しておき、前記検索キーと前記ビットマスク値との論理積演算によって比較判定を行なう請求項３記載のフィルタ条件比較方法。
【請求項５】
前記演算コードに、部分一致が指定されている場合には、当該フィルタ条件のエントリに、比較部分の基準となるベース値と、前記比較部分以下のビット数を示すシフト値と、前記比較部分における一致条件を満たす数値が各ビットに対応するように展開されたビットマップとを登録しておき、前記検索キーにおける前記比較部分のビット列を前記ビットマップに対応する形式に展開し、前記ビットマップとの論理積演算によって比較判定を行なう請求項３または４記載のフィルタ条件比較方法。
【請求項６】
前記演算コードに、範囲指定が指定されている場合には、当該フィルタ条件のエントリに、当該範囲の下限境界と上限境界とを登録しておき、前記検索キーと前記下限境界および前記上限境界との大小比較によって比較判定を行なう請求項３から５のいずれか１項記載のフィルタ条件比較方法。
【請求項７】
検索キーが、エントリされたフィルタ条件を満足するか否かを比較判定するためのフィルタ条件比較システムにおいて、
前記検索キーの値のとり得る範囲を２以上の所定の自然数で分割することによって得られる分割領域毎に、前記検索キーのフィルタ条件をエントリするテーブルと、
入力された検索キーの値と、当該キーの値が含まれる分割領域に対応するフィルタ条件とを比較して前記検索キー値が満足するフィルタ条件を求める条件比較手段とを備えることを特徴とするフィルタ条件比較システム。
【請求項８】
前記条件比較手段は、複数種類の検索キーがある場合に、前記各種類の入力された検索キーにおいて、
全種類の入力された検索キーが満足するフィルタ条件を求め、条件比較手段によって求められたフィルタ条件に対応するフィルタ条件ＩＤリストのうち、所定の優先度に基づいて、最も優先度の高いフィルタ条件ＩＤを選択するＩＤ決定手段をさらに備える請求項７記載のフィルタ条件比較システム。
【請求項９】
前記テーブルの各フィルタ条件のエントリには、当該フィルタ条件の種別を特定するための演算コードが指定されている請求項７または８記載のフィルタ条件比較システム。
【請求項１０】
前記演算コードに、完全一致が指定されている場合には、前記テーブルにおける当該フィルタ条件のエントリに、前記検索キーとの論理積演算を行なうためのビットマスク値が登録されており、前記条件比較手段は、前記検索キーと前記ビットマスク値との論理積演算によって比較判定を行なう請求項９記載のフィルタ条件比較システム。
【請求項１１】
前記演算コードに、部分一致が指定されている場合には、当該フィルタ条件のエントリに、比較部分の基準となるベース値と、前記比較部分以下のビット数を示すシフト値と、前記比較部分における条件を満たす数値が各ビットに対応するように展開されたビットマップとが登録されており、前記条件比較手段は、前記検索キーにおける前記比較部分のビット列を前記ビットマップに対応する形式に展開し、展開したビットマップと、エントリされている前記ビットマップとの論理積演算によって比較判定を行なう請求項９または１０記載のフィルタ条件比較システム。
【請求項１２】
前記演算コードに、範囲指定が指定されている場合には、当該フィルタ条件のエントリに、当該範囲の下限境界と上限境界とが登録されており、前記検索キーと前記下限境界および前記上限境界との大小比較によって比較判定を行なう請求項９から１１のいずれか１項記載のフィルタ条件比較システム。
【請求項１３】
前記ＩＤ決定手段は、連想メモリを用いて論理積演算を行なう請求項８記載のフィルタ条件比較システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、検索キーが、エントリされたフィルタ条件に満足するか否かを比較判定するためのフィルタ条件比較方法に関し、特に、ルータ等に代表されるＩＰ転送装置においてＱｏＳ制御等を行なうためのフィルタ条件比較方法に関する。
【０００２】
【従来の技術】
ルータ等に代表されるＩＰ転送装置では、様々なサービス品質、すなわちＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）をサポートするために、きめ細かいフィルタ条件の指定を行なうことができるようになっている。このようなフィルタ条件に基づくフィルタ処理では、従来、ＩＰ転送装置が備えるＣＰＵにおいて、転送されるデータがフィルタ条件を満足するか否かの比較判定を行なったうえで、それらのデータ転送処理、すなわちルーティングを行なっている。
【０００３】
しかしながら、ルーティングをハードウェアで行なう場合には、フィルタ処理やＱｏＳ処理のための分類（クラシファイ）処理が問題となる。クラシファイ処理では、入力インタフェース番号、ＩＰＳＡ（送信元アドレス）、ＩＰＤＡ(宛先アドレス)、レイヤ４のプロトコル番号、レイヤ４のポート番号（送信元、宛先）などの複数のフィールドに対してそれぞれフィルタ条件が設定される。
【０００４】
ハードウェアが得意とする完全一致検索を使用する方法では、とりうる値のあらゆる組み合わせをテーブルに登録しておき、一致するかどうかを検索することでクラス分けを行なう。例えば、フィルタ条件として、入力インタフェース番号＝１、 ＩＰＳＡ＝１．２.３．０/２４、 ＩＰＤＡ＝１．２.４．０/２４、 レイヤ４のプロトコル番号＝６（ＴＣＰ）、レイヤ４の送信元ポート番号＝１０００〜１９９９、 レイヤ４の宛先ポート番号＝８０が設定されていたとする。ルータでは、この設定された条件にマッチするパケットに対しては、同じＱｏＳ処理を行なうという条件を指定する。フローエントリを登録する方式の場合は実際に処理したパケット毎に登録を行い、｛入力インタフェース番号＝１、 ＩＰＳＡ＝１．２.３．１０、ＩＰＤＡ＝１．２.４．０／２０、レイヤ４のプロトコル番号＝６, Ｌ４送信元ポート＝１０３０、 レイヤ４の宛先ポート番号＝８０｝というように個別に登録し、条件検索では、登録された値との完全一致を判定することで確認する。しかし、このようにするとハードウェアに登録するエントリが膨大になってしまうという問題が発生する。
【０００５】
一方、ドントケア（ｄｏｎ’ｔ ｃａｒｅ）条件を指定できる連想メモリ、すなわちＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）を用いれば、指定条件のビット列をドントケア（ｄｏｎ’ｔ ｃａｒｅ）指定で定義することができる。ターナリ−（ｔｅｒｎａｒｙ）ＣＡＭと呼ばれるＣＡＭでは、”０”、”１”、”ｄｏｎ’ｔ ｃａｒｅ”の３値を設定できるので、例えば、ＩＰＳＡ＝１．２．３．０／２４にマッチするエントリを登録するときには、フィルタ条件を、２進数で、”０００００００１ ００００００１０ ００００００１１ ｘｘｘｘｘｘｘｘ” (ｘはｄｏｎ’ｔ ｃａｒｅ、）と登録することによって、ＩＰアドレス＝１．２.３．０〜１．２.３．２５５の２５６個の値を指定するフィルタ条件を、１エントリだけで表現できるようになる。
【０００６】
また、レイヤ４の送信元ポート番号＝１０００〜１９９９を指定する場合には、この条件を２のべき乗に展開し、１６進数で｛０ｘ３ｅ８−０ｘ３ｅｆ、０ｘ３ｆ０−０ｘ３ｆ、０ｘ４００-０ｘ５ｆｆ、０ｘ６００−０ｘ６ｆｆ、０ｘ７００−０ｘ７７ｆ、０ｘ７８０−０ｘ７ｂｆ、０ｘ７ｃ０−０ｘ７ｄｆ、０ｘ７ｅ０−０ｘ７ｅｆ｝の８つのＣＡＭエントリで、フィルタ条件を表現することになる。このように、フィルタ条件が所定の範囲で与えられるときには、ＣＡＭを使用することによってハードウェアにおけるクラシファイの条件判定を効率的に行なうことができるが、２のべき乗展開などで範囲指定をする要素が増えた場合には、エントリの管理が面倒になってしまうという問題があった。
【０００７】
【発明が解決しようとする課題】
以上述べたように、従来のフィルタ条件比較方法では、以下に示す問題点を有する。
（１）  ハードウェアによる全文一致検索では、ハードウェアに登録するエントリが膨大になってしまい、エントリした全てのフィルタ条件について検索を行なうために、処理時間に時間を要してしまう。
（２）  指定条件が所定の範囲で与えられるときには、ＣＡＭを使用することによってハードウェアにおけるクラシファイの条件判定を効率的に行なうことができるが、２のべき乗展開などで、範囲指定をするエントリが増えた場合には、エントリの管理が面倒になってしまう。
【０００８】
本発明は、評価すべき条件式のエントリ数を減らし、比較判定処理を効率化できるフィルタ条件比較方法およびシステムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記課題を解決するために、本発明では、検索キーが、エントリされたフィルタ条件を満足するか否かを比較判定するためのフィルタ条件比較方法において、
前記検索キーの値のとり得る範囲を２以上の所定の自然数で分割することによって得られる分割領域毎に、前記検索キーのフィルタ条件をテーブルにエントリしておく第１のステップと、
入力された検索キーの値と、当該キーの値が含まれる分割領域に対応するフィルタ条件とを比較して前記検索キー値が満足するフィルタ条件を求める第２のステップとを有することを特徴とする。
【００１０】
本発明のフィルタ条件比較方法では、検索キーの値のとり得る範囲を２以上の所定の自然数で分割することによって得られる分割領域毎に、前記検索キーのフィルタ条件をテーブルにエントリし、そこにエントリした条件でしが比較判定を行なわないので、比較判定対象のフィルタ条件の要素数を削減し、比較判定処理を効率化することができるようになる。
【００１１】
また、本発明の他のフィルタ条件比較方法では、複数種類の検索キーがある場合に、前記各種類の入力された検索キーにおいて、
前記第１のステップおよび第２のステップをそれぞれ実行するステップと、
全種類の入力された検索キーが満足するフィルタ条件を求める第３のステップと、
前記第３のステップで求められたフィルタ条件に対応するフィルタ条件ＩＤリストのうち、所定の優先度に基づいて、最も優先度の高いフィルタ条件ＩＤを選択する第４のステップを有する。
【００１２】
このようにすれば、全種類の検索キーを満たすフィルタ条件を求め、その中から、優先度の高いフィルタ条件ＩＤを選択するといった、柔軟な条件評価が可能になる。
【００１３】
また、本発明の他のフィルタ条件比較方法では、前記テーブルの各フィルタ条件のエントリに、当該フィルタ条件の種別を特定するための演算コードを指定しておく。
【００１４】
本発明のフィルタ条件比較方法では、１エントリで、ビットマスクとの論理積による比較評価、範囲指定による比較評価等のフィルタ条件を表現することができるようになる。このようにすれば、エントリが必要以上に増えなくなるため、エントリの管理が容易となる。
【００１５】
【発明の実施の形態】
本発明の一実施形態のフィルタ条件比較方法について図面を参照して詳細に説明する。本実施形態のフィルタ条件比較方法は、複数種類の検索キー（入力キー）がエントリされたフィルタ条件を満足するか否かを比較判定する方法である。本実施形態のフィルタ条件比較方法では、まず、入力キーの値ｘが満たす全てのファルタ条件（条件エントリ）のＩＤを取得し、そのＩＤ値の論理和をＩＤリストとして求め、複数の入力キー種別のそれぞれについて求めたＩＤリストのビットマップの論理積を、全て種類の入力キーが満たすフィルタ条件ＩＤの候補として求め、得られた複数のＩＤ候補のうち、最も優先度の高いものをフィルタ条件ＩＤとして決定する。
【００１６】
図１は、本実施形態のフィルタ条件比較方法を実行するためのシステムの構成を示すブロック図である。図１に示すように、このシステムは、条件比較部１１０と、３つのキー種テーブル１２０と、ＩＤ決定部１３０と、ＩＤ／ストリームＩＤ変換部１４０とを備えている。条件比較部１１０は、検索キー１００の各キー種１〜３の値、すなわち入力されたキーの値が、それぞれのキー種のキー種テーブル１２０に登録されたフィルタ条件を満足するか否かを比較判定し、入力キーの値が満足するフィルタ条件のＩＤのＩＤリストを取得する。ＩＤ決定部１３０は、全種類の入力キーが同時に満たすフィルタ条件ＩＤを決定する。ＩＤ決定部１３０では、複数ＩＤが得られた場合には、最も優先度の高いＩＤを決定ＩＤとする。ＩＤ／ストリームＩＤ変換部１４０は、決定したＩＤを、複数のフィルタ条件を満たし、アクション（フィルタリング、ＱｏＳ設定、ヘッダ変換コード等）を指定するストリームＩＤに変換する。
【００１７】
図２は、キー種テーブル１２０の構成を示す図である。キー種テーブルは、テーブル１２１〜１２３を有している。テーブル１２１には、各入力キーの値のとり得る範囲を所定の自然数Ｎで分割することによって得られるＮ個の分割領域についての条件エントリの開始アドレス値が保持されている。テーブル１２２には、Ｎ個の分割領域毎のフィルタ条件（条件１〜５）が、前述の開始アドレスからエントリされている。このようにすれば、評価対象のフィルタ条件の数を絞り込むことができるようになる。テーブル１２３には、各フィルタ条件に対応するＩＤ候補を示すＩＤリスト（ｉｄ＿ｌｉｓｔ１〜５）が登録されている。
【００１８】
図２では、分割数Ｎ＝６４として、入力キーの値をｘ＝０ｘ４４３とした例が示されている。本実施形態のフィルタ条件比較方法では、入力キーの値０ｘ４４３より、テーブル１２１の０ｘ４００〜０ｘ７ｆｆの範囲に対応するフィルタ条件が条件比較の対象となるため、まず、テーブル１２１よりテーブル１２２の開始アドレス値（ポインタ値）０ｘ２００を得る。キー種テーブル１２０では、テーブル１２２のアドレス０ｘ２００に条件３〜５が記述されている。本実施形態のフィルタ条件比較方法では、入力キーの値０ｘ４４３と条件３〜５との比較を行い、ＩＤリスト３〜５のうち、入力キーの値０ｘ４４３が満たすフィルタ条件に対応するＩＤリストを取得する。
【００１９】
図３は、テーブル１２２にエントリされるフィルタ条件のフォーマットの例を示す図である。図３には、３種類のフォーマットが示されている。各フォーマットは、演算コード、すなわちオペコード（Ｏｐｃｏｄｅ）、Ｅビット（Ｅｎｄ  Ｆｌａｇ）、Ｌビット（Ｌｉｎｋ  Ｆｌａｇ）、Ａビット（Ａｎｄ  Ｏｐｅｒａｔｉｏｎ）、Ｂビット（Ｂｏｏｌｅａｎ）の５つの共通フィールドを有している。まず、先頭のオペコードは、フィルタ条件の種別を示す。オペコード＝１が指定されているエントリ１２２1は、完全一致をフィルタ条件とするエントリである。このフィルタ条件では、入力キーとの比較は、フルビットのビットマスク演算によって行われるため、共通フィールドの後にその演算のビットマスク値（ｂｉｔｍａｓｋ）がエントリされている。オペコード＝２が指定されているエントリ１２２2は、フィルタ条件が検索キーにおける所定のビットの部分一致をフィルタ条件とするエントリである。したがって、入力キーとの比較は、部分的なビットマスク演算によって行われるため、共通フィールドの後に、比較部分の基準となるベース値（ｂａｓｅ）と、比較部分以下のビット数を示すシフト値（ｓｈｉｆｔ）と、比較部分におけるフィルタ条件を満たす数値が各ビットに対応するように展開されたビットマップ（ｒｅｇｉｏｎ  ｍａｐ）とが、エントリされている。このフィルタ条件によって、入力キーの値が２のべき乗空間にあるか否かの判定が可能となる。オペコード＝３が指定されているエントリ１２２3は、所定の範囲をフィルタ条件とするエントリである。そのため、このエントリの共通フィールドの後には、下限境界値（Ｌｏｗｅｒ  ｂｏｕｎｄａｒｙ）と上限境界値（Ｕｐｐｅｒ  ｂｏｕｎｄａｒｙ）がエントリされている。
【００２０】
Ｅビットは、そのフィルタ条件が１つの領域内における最後のエントリであるか否かを示す。Ｌビットは、そのエントリが前回のエントリとリンク関係にあるか否かを示し、入力キーの値が前回のエントリ内の条件を満たしていたならば、そのエントリについての評価の必要がないことを示す。Ａビットは、そのエントリが前のエントリと論理積（ＡＮＤ）関係にあるか否かを示す。入力キーの値が前回のエントリの条件を満たしていて、そのエントリに示す条件も満たす場合に指定条件を満たすものと判定される。Ｂビットは、そのエントリ内のコードで示される論理演算の結果の値が０であるか１であるかによって、フィルタ条件を満たしているか否かを判定するために使用される。
【００２１】
図４は、条件比較部１１０の動作を示すフローチャートである。入力キーの値ｘが入力されると、条件比較部１１０は、テーブル１２２の開始アドレスを求め、そのアドレスのエントリを読み出し、そのエントリの先頭からオペコード（Ｏｐｃｏｄｅ）をフェッチする（ステップＡ１）。
【００２２】
次に、前回のエントリの比較結果における真理値ｙが１であって、Ｌビットの値が１である場合、すなわち、入力キーの値ｘが前回のエントリのフィルタ条件を満たしていて、今回のエントリが前回のエントリとリンク関係にある場合には、今回のエントリによる判定処理が不要となるので、後述する判定処理ステップＡ４〜Ａ６をスキップして、ステップＡ１２に進む（ステップＡ２）。ステップＡ２で前述の条件に該当しなかった場合には、オペコードを参照し（ステップＡ３）、それぞれの各オペコードに対応する判定処理（ｏｐｃｏｄｅ１処理（ステップＡ４）、ｏｐｃｏｄｅ２処理（ステップＡ５）、ｏｐｃｏｄｅ３処理（ステップＡ６））を実行する。これらの処理では、条件比較結果の真理値ｙが得られる。なお、ｙは、非零のときに１となる０／１の真理値である。
【００２３】
次に、条件比較部１１０は、今回のエントリのＡビットが１であるか否か判断し（ステップＡ７）、Ａビットが１である場合には、今回のエントリの比較結果における真理値ｙと前回のエントリの比較結果の真理値Ｄ（ｙ）との論理積をｙとする（ステップＡ８）。Ａビットが０である場合には、ステップＡ８の処理を行なわずにステップＡ９に進む。
【００２４】
ステップＡ９ではｙの値をチェックし、ｙ＝１であれば、入力キーの値ｘが今回のエントリのフィルタ条件を満たしていることになるので、そのフィルタ条件に対応するＩＤリスト（ｉｄ＿ｌｉｓｔ）をテーブル１２３から取得する（ステップＡ１０）。ＩＤリストは、１ビットが１つのＩＤに対応するビットマップである。入力キーの値ｘが、比較の結果、複数のエントリを満たす場合には、これまでに得られたＩＤリスト（ｉｄ＿ｌｉｓｔ）の論理和を求める（ステップＡ１１）。こうすることによって、これまでのフィルタ条件の比較結果を示すビットマップであるＩＤリストを得ることができる。
【００２５】
次に、条件比較部１１０は、今回のエントリのＥビットが１であるか否か判断し（ステップＡ１２）、Ｅビットが１である場合には、これまでに得られたＩＤリストを出力し、Ｅビットが０である場合には、ステップＡ１に戻って、次のエントリを読み出す。
【００２６】
図５は、各オペコードに対応する判定処理を示すフローチャートである。まず、オペコード１処理について説明する。オペコード１処理（ｏｐｃｏｄｅ１）では、入力キーの値ｘとエントリのビットマップとの論理積ｙを求める（ステップＢ１）。そして、論理積ｙと、今回のエントリのＢビットとの排他的論理和の反転値を比較照合結果ｍａｔｃｈとして出力する（ステップＢ５）。このｍａｔｃｈは、論理積結果ｙ、Ｂビットともに０か１である場合に１となる。
【００２７】
次に、オペコード２処理について説明する。オペコード２処理（ｏｐｃｏｄｅ２）では、入力キーの値ｘからエントリのベース値（ｂａｓｅ）を減算し、その減算値をシフト値（ｓｈｉｆｔ）の数だけ右シフトさせ、ビットマップ（ｒｅｇｉｏｎ  ｍａｐ）のサイズ（ｓｉｚｅ）でマスクし、そのマスク結果をｚとする（ステップＢ２）。さらに、１をｚビットだけ左シフトしたものとビットマップ値（ｂｉｔｍａｐ）の論理積演算結果をｙとする（ステップＢ３）。そして、ステップＢ５を実行してｍａｔｃｈを求める。
【００２８】
次に、オペコード３処理について説明する。オペコード３処理（ｏｐｃｏｄｅ３）では、まず、入力キーエントリの下限境界（ｌｏｗｅｒ）より大きく、上限境界（ｕｐｐｅｒ）より小さいか否かをチェックし（ステップＢ４）、ステップＢ５を実行してｍａｔｃｈを求める。
【００２９】
図６は、ＩＤ決定部１３０およびＩＤ／ストリームＩＤ変換部１４０の処理の一例を示す図である。図６には、得られたＩＤリストのビットマップの論理積をとる処理が示されている。ＩＤ決定部１３０は、条件比較部１１０におけるキー種１〜３の３種類の条件比較により得られたそれぞれのＩＤリスト（ｉｄ＿ｌｉｓｔ｛ｋｅｙ１｝、ｉｄ＿ｌｉｓｔ｛ｋｅｙ２｝、ｉｄ＿ｌｉｓｔ｛ｋｅｙ３｝）の論理積をとることで、各キー種に対する条件を全て満たすフィルタ条件ＩＤを取得する。図６に示す例では、キー種１に対するＩＤリストとして、”００００１１１０”が得られたものとする。ここで、ＩＤリストでは、値が１であるビットの位置が、入力キーが満たす各フィルタ条件のＩＤ番号に対応しており、キー種１の入力値ｘは、ＩＤ=１、２、３の条件を満たしていることがわかる。同様に、キー種２ではＩＤリストとして、”０００１１０１０”（ＩＤ＝１、３、４）が得られ、キー種３ではＩＤリストとして、”００００１０１１”（ＩＤ=０、１、３）がそれぞれ得られたものとする。これら３つのＩＤリストの論理積（ＡＮＤ）は、”００００１０１０”となるので、キー種１〜３に対する全ての条件を満たすＩＤとして、ＩＤ＝１、３が得られる。ここで、ＩＤの値が小さい方を優先度（ｐｒｉｏｒｉｔｙ）が高い（ｈｉｇｈ）とした場合には、ＩＤ＝１が決定ＩＤとなり、このＩＤ＝１を用いて、ＩＤ／ストリームＩＤ変換部１４０においてストリームＩＤ１（ｓｔｒｅａｍ  ｉｄ１）が取得される。ここで、ストリームＩＤは、入力キーに対するストリームを特徴付け、パケットを転送処理するための各種条件を取得するためのＩＤであって、アクション（フィルタリング、ＱｏＳ設定、ヘッダ変換コード等）を指定するＩＤである。
【００３０】
図７は、ＩＤ決定部１３０およびＩＤ／ストリームＩＤ変換部１４０における処理の他の例を示す図である。図７では、ＣＡＭ（連想メモリ）を用いてストリームＩＤを取得する。ここで用いるＣＡＭは、ターナリーＣＡＭ（ｔｅｒｎａｒｙ  ＣＡＭ）と呼ばれるものであり、各ビットを”１”、”０”、”ｄｏｎ’ｔｃａｒｅ”の３値のいずれに指定することができるものである。ＲＡＭ上に書き込まれたストリームＩＤ１〜３に対応するＩＤ条件は、ストリームＩＤ１〜３が登録されているアドレスと同じアドレスにそれぞれ登録されている。ストリームＩＤ１に対するＩＤ条件は、キー種１（ｋｅｙ１）ではＩＤ＝１を含むこと、キー種２（ｋｅｙ２）、キー種３（ｋｅｙ３）でもＩＤ＝１を含むことがＣＡＭに登録されている。ターナリーＣＡＭに登録されているｘは、”ｄｏｎ’ｔ   ｃａｒｅ”であることを表わしており、そのビットが０であっても、１であっても関係ないことを表わしている。
【００３１】
キー種１に対するＩＤリスト（ｉｄ＿ｌｉｓｔ｛ｋｅｙ１｝）が”００００１１１０”であれば、ＩＤ＝１を含むので、ストリームＩＤ１の条件に一致する。キー種２に対するＩＤリスト（ｉｄ＿ｌｉｓｔ｛ｋｅｙ２｝）が”０００１１０１０”、キー種３に対するＩＤリスト（ｉｄ＿ｌｉｓｔ｛ｋｅｙ３｝）が”００００１０１１”であれば、いずれもＩＤ=１を含むのでストリームＩＤ１（ｓｔｒｅａｍ  ｉｄ１）に対するＣＡＭエントリにマッチする。同じ入力に対してストリームＩＤ２（ｓｔｒｅａｍ  ｉｄ２）のＣＡＭエントリでは、キー種２の指定”ｘｘｘｘｘ１ｘｘ”がＩＤ=２を含むことを条件としているのでマッチしない。ストリームＩＤ３（ｓｔｒｅａｍ  ｉｄ３）のＣＡＭエントリでは、キー種１〜３に対してＩＤ＝３を含むことを条件としていて、また、キー種１〜３のＩＤリストがいずれもマッチするのでストリームＩＤ３の条件にもマッチすることがわかる。つまり、上述した例では、ストリームＩＤ１、ストリームＩＤ３の２つのエントリにマッチする。一般に、ＣＡＭは、若番アドレスに登録されたエントリのアドレスを解として返すので、優先度（ｐｒｉｏｒｉｔｙ）の高い（ｈｉｇｈ）ストリームＩＤの条件を若番アドレスに登録しておけば、優先度の高いストリームＩＤ（ここではｓｔｒｅａｍ  ｉｄ１）が選択される。
【００３２】
次に、本実施形態のフィルタ条件比較方法の具体例について説明する。図８は、本実施形態のフィルタ条件比較方法の具体例１を示す図である。図８には、キー種テーブル１２０に登録される２つの条件エントリが、リンクされている場合が示されている。入力キー値ｘは、０ｘ４４３であるとする。本実施形態のフィルタ条件比較方法では、まず、ｘとエントリ６０１との比較を行なう。エントリ６０１のオペコードは２であるので、エントリ６０１は範囲指定ビットマップを表わしている。エントリ６０１では、ビットマップのサイズ値（ｓｉｚｅ）は０ｘｆであり、ベース値（ｂａｓｅ）が０ｘ４００で、シフト値（ｓｈｉｆｔ）が４であるので、（（０ｘ４４３ー０ｘ４００）＞＞４）＆０ｘｆの演算によってｚ＝４が得られる。また、ｙ=（１＜＜４） & ０ｘ０００ｆ＝０でＢ＝１なので、入力キーの値ｘは、エントリ６０１の条件を満たさないことがわかる。なお、エントリ６０１では、０ｘ４１？、０ｘ４２？、０ｘ４３？（？は、０〜ｆのいずれか）が一致するエントリとなっている。
【００３３】
次に、本実施形態のフィルタ条件比較方法では、入力キーの値ｘとエントリ６０２との比較を行なう。エントリ６０１と同様に、エントリ６０２のオペコードも２であるので、エントリ６０２は範囲指定ビットマップを表わしている。エントリ６０２は、ベース値（ｂａｓｅ）=０ｘ４４０、 シフト値（ｓｈｉｆｔ）＝０であるので（（０ｘ４４３−０ｘ４４０＞＞０）＆０ｘｆ）の演算によってｚ＝３が得られる。また、ｙ=（１＜＜３）＆ ０ｘ００１ｆ＝８でＢ＝１なので入力キーの値ｘは、エントリ６０２を満たすことがわかる。エントリ６０２のＥビットは１であるため、ここで比較を終了する。
【００３４】
次に、入力キーの値ｘが０ｘ４３２であった場合について説明する。エントリ６０１との比較では、ｚ=（（０ｘ４３２ー０ｘ４００）＞＞４）＆０ｘｆ＝３となり、Ｙ=（１＜＜３）& ０Ｘ０００ｆ=８となるので、入力キーの値ｘはエントリ６０１の条件を満たすことがわかる。エントリ６０１では、Ｅ＝０なので、次のエントリであるエントリ６０２についての比較が行なわれる。エントリ６０２はＬ＝１であり、さらに前回のエントリであるエントリ６０１での判定結果は、ｙ＝１であったので、図４のステップＡ２の処理により、オペコード処理を行わずにステップＡ１２にスキップする。さらに、エントリ６０２のＥビットが１であるので、ステップＡ１２の処理によって処理を終了する。
【００３５】
図９は、本実施形態のフィルタ条件比較方法の具体例２を示す図である。図９では、入力キーの値ｘを０ｘ４４３としている。まず、本実施形態のフィルタ条件比較方法では、エントリ６０３との比較が行われる。エントリ６０３のオペコードは３なので範囲指定比較（ｒｅｇｉｏｎ  ｂｏｕｎｄａｒｙ）が行われる。上限境界値と下限境界値がエントリ６０３から取り出され、入力キーの値０ｘ４４３がそれぞれの条件を満たすか否かがチェックされる。エントリ６０３では、０ｘ２２２≦ｘ≦０ｘ４５６かつＢ＝１であるので、条件を満たしていることがわかる。
【００３６】
さらに、本実施形態のフィルタ条件比較方法では、エントリ６０４、６０５との比較が行われる。エントリ６０４では、オペコードが１であるので、ビットマップ演算が行われる。（０Ｘ４４３ & ０Ｘ０００１）＝１かつＢ＝１であるので条件を満たしている。エントリ６０５は、エントリ６０３と同様に条件を満たしているが、Ａ＝１であるので、エントリ６０４の結果を使用する。図４のステップＡ８の処理により、エントリ６０４、６０５がともにｙ＝１となるので条件を満たすという結果が得られる。
【００３７】
図１０は、本実施形態のフィルタ条件比較方法における各エントリの設定方法の一例を示す図である。図１０では、与えられたフィルタ条件をテーブル１２２にどのように設定するかが例示されている。まず、ｘ=０ｘ４１、０ｘ４２、０ｘ４４、０ｘ４５に一致する入力値を検出するためのフィルタ条件の設定例がエントリ６０６に示されている。オペコード値２の領域ビットマップを用い、ベース値（ｂａｓｅ）＝０ｘ４０、シフト値（ｓｈｉｆｔ）＝０、ビットマップ（ｒｅｇｉｏｎ  ｍａｐ）＝０ｘ００３６とする。このようにすれば、ｚ＝（（ｘー０ｘ４０）＞＞０）＆０ｘｆをビット位置として評価し、ビットマップ（ｒｅｇｉｏｎ  ｍａｐ）=０ｘ３６よりｘ＝０ｘ４１、０ｘ４２、０ｘ４４、０ｘ４５が一致条件となる。
【００３８】
入力キーの値ｘが全ての値（ａｎｙ（ｄｏｎ’ｔ  ｃａｒｅ））に一致する値を指定するフィルタ条件の設定例がエントリ６０７に示されている。ここでは、オペコードにビットマスク演算（１）を設定し、ビットマスク（ｂｉｔｍａｓｋ）＝０、Ｂ＝０と設定する。こうすることによって、全ての入力キーの値ｘに一致するための条件指定が可能になる。
【００３９】
なお、これまで説明した処理フローは、ＣＰＵでソフトウェア処理する際や、ネットワークプロセッサと呼ばれるパケット転送処理用のプロセッサチップでフィルタ条件、ＱｏＳ条件の判定をする際にも適用することができる。
【００４０】
図１１は、ハードウェアで構成された条件比較部１１０の構成を示すブロック図である。図１１に示すように、条件比較部１１０は、オペコード１の処理を行なうブロック２００と、オペコード２の処理を行なうブロック３００と、オペコード３の処理を行なうブロック４００と、セレクタ５００と、オペコードのデコードをするデコーダ５１０と、Ａビットに基づく処理を行なうブロック５２０とから構成される。
【００４１】
オペコード１の処理を行なうブロック２００は、入力キーの値ｘを保持するレジスタ２１０とビットマスク値（ｍａｓｋ）を保持するレジスタ２３０を有しており、複数ビットの論理積演算（ＡＮＤ）を行なう論理回路であるＡＮＤブロック２２０を用いて、レジスタ２１０と２３０のビット論理積演算を行なう。さらに、非零判定を行なうためにＡＮＤブロック２２０の全ビットの論理和演算が、ブロック２４０が備えるＯＲ回路で実行され、Ｂビットの値に応じて論理和の結果が０／１どちらである場合にマッチとするかを選択するかをブロック２４０が備えるセレクタで選択する。
【００４２】
オペコード２の処理を行なうブロック３００では、入力キー値ｘからベース値を減算し、その減算結果をシフト（ｓｈｉｆｔ）値だけ右シフトするレジスタ３１０を備える。レジスタ３１０の結果である２進値をバイナリデコーダ（ｂｉｎａｒｙ  ｄｅｃｏｄｅｒ）３２０でデコードしてビット位置を求め、そのビットとビットマップ（ｒｅｇｉｏｎ  ｍａｐ値）を保持するレジスタ３４０との論理積をＡＮＤブロック３３０でとる。論理積をとった結果について、ブロック３５０において非零判定が行われ、Ｂビットの値に基づく０／１の選択が行なわれる。
【００４３】
オペコード３の処理ブロック４００では下限境界値（ｌｏｗｅｒ）より大きいことを確認する比較ブロック４１０と、上限境界値（ｕｐｐｅｒ）より小さいことを確認する比較ブロック４２０の結果をそれぞれ論理積演算し、Ｂビットの値に基づく０／１の選択を行なったものを処理結果として出力する。
【００４４】
ハードウェアで構成された条件比較部１１０では、ブロック２００、３００、４００を並列に動作させておき、デコーダ５１０によってデコード（ｄｅｃｏｄｅ）されたオペコードのデコード値に基づいてセレクタ５００で結果を選択する。選択された結果は、ブロック５２０に入力される。ブロック５２０は、Ａビットが０であるときには、セレクタ５００によって選択された結果をそのまま結果ｙとして出力し、Ａビットが１であるときには、前回のエントリの結果との論理積をとってその結果ｙを出力する。
【００４５】
このように、条件比較部１１０をハードウェアで構成すれば、ＣＰＵおよびネットワークプロセッサで比較判定処理を行なうよりも、比較判定処理に要する処理時間を短縮することが可能になり、パケット転送処理能力を向上させることが可能となる。
【００４６】
【発明の効果】
以上述べたように、本発明のフィルタ条件比較方法は、以下に示す効果を有する。
（１）  検索キーの値のとり得る範囲を所定の自然数で分割することによって得られる分割領域毎に、前記検索キーのフィルタ条件をテーブルにエントリし、そこにエントリした条件でした比較を行わないので、比較判定対象のフィルタ条件の要素数を削減して、処理を効率化することができるようになる。
（２）  複数種類の検索キー全てを満たすフィルタ条件を求め、その中から、優先度の高いフィルタ条件を選択するといった、柔軟な条件評価が可能になる。
（３）  １つのエントリで表現するフィルタ条件を多様化することができるようになる。したがって、エントリが必要以上に増えなくなるため、エントリの管理が容易となる。
【図面の簡単な説明】
【図１】本発明の一実施形態のフィルタ条件比較方法を実行するためのシステムの構成を示すブロック図である。
【図２】キー種テーブルの構成を示す図である。
【図３】エントリされるフィルタ条件のフォーマットの例を示す図である。
【図４】条件比較部の動作を示すフローチャートである。
【図５】各オペコードに対応する判定処理を示すフローチャートである。
【図６】ＩＤ決定部およびＩＤ／ストリームＩＤ変換部の処理の一例を示す図である。
【図７】ＩＤ決定部およびＩＤ／ストリームＩＤ変換部における処理の他の例を示す図である。
【図８】本発明の一実施形態のフィルタ条件比較方法の具体例１を示す図である。
【図９】本発明の一実施形態のフィルタ条件比較方法の具体例２を示す図である。
【図１０】本発明の一実施形態のフィルタ条件比較方法における各エントリの設定方法の一例を示す図である。
【図１１】ハードウェアで構成された条件比較部の構成を示すブロック図である。
【符号の説明】
１００    検索キー
１１０    条件比較部
１２０    キー種テーブル
１２１〜１２３    テーブル
１２２1〜１２２3    エントリ
１３０    ＩＤ決定部
１４０    ＩＤ／ストリームＩＤ変換部
２００、３００、４００、５２０    ブロック
２１０、２２０、３１０、３４０    レジスタ
２２０、３３０    ＡＮＤブロック
３２０    バイナリデコーダ
４１０、４２０    比較ブロック
５００    セレクタ
５１０    デコーダ
６０１〜６０７    エントリ
Ａ１〜Ａ１２、Ｂ１〜Ｂ５    ステップ
【図１】
0003707545.tif 000002
【図２】
0003707545.tif 000003
【図３】
0003707545.tif 000004
【図４】
0003707545.tif 000005
【図５】
0003707545.tif 000006
【図６】
0003707545.tif 000007
【図７】
0003707545.tif 000008
【図８】
0003707545.tif 000009
【図９】
0003707545.tif 000010
【図１０】
0003707545.tif 000011
【図１１】
0003707545.tif 000012