(57)【要約】【課題】パケット分類に要する処理時間を短縮できるとともに、消費電力を低減することを可能とする。【解決手段】識別子群生成部１１０で、入力パケット中の予め特定された識別子値の組み合わせからなる識別子群値を生成し、検索部１２０で、識別子群値のそれぞれに対して、識別子群値の１つ以上の検索候補と検索候補を特定する候補ＩＤとを対応させた検索候補表を保持し、候補ＩＤのうちの所定の候補ＩＤを順次指定して、各識別子群値と一致する検索候補を対応する検索候補表中から検索し、検索して得られた各検索候補に対応する候補ＩＤに応じた分類値を出力する。【選択図】  図１
2005303417.tif 000002
【特許請求の範囲】
【請求項１】
入力パケット中の所定のフィールドに記録されたデータからなる１つ以上の識別子値に基づいて、前記入力パケットを分類する情報として分類値を生成するパケットクラシファイア装置において、
前記入力パケット中の予め特定された識別子値の組み合わせからなる識別子群値について任意の検索候補を検索し、その検索結果に応じて前記入力パケットに対する分類値を出力する検索部を備え、
前記検索部は、前記識別子値の組み合わせからなる１つ以上の識別子群値のそれぞれに対して、前記識別子群値の１つ以上の検索候補と前記検索候補を特定する候補ＩＤとを対応させた検索候補表を保持し、前記候補ＩＤのうちの所定の候補ＩＤを順次指定して、前記各識別子群値と一致する前記検索候補を対応する前記検索候補表中から検索し、検索して得られた前記各検索候補に対応する候補ＩＤに応じた前記分類値を出力することを特徴とするパケットクラシファイア装置。
【請求項２】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、前記候補ＩＤに応じたマスクである識別子群マスクを前記識別子群値に施してマスク識別子群値を生成し、前記検索候補表で前記候補ＩＤと前記候補ＩＤに応じた識別子群マスクを施した識別子群値候補であるマスク識別子群値候補とを対応させて保持し、前記マスク識別子群値と一致する前記マスク識別子群値候補を前記検索候補表から検索し、検索して得られた前記マスク識別子群値候補に対応する候補ＩＤに応じた前記分類値を出力することを特徴とするパケットクラシファイア装置。
【請求項３】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、前記識別子群値のハッシュ値を算出し、前記検索候補表で前記識別子群値のハッシュ値の候補である識別子群ハッシュ値候補と前記識別子群ハッシュ値候補を特定する候補ＩＤとを対応させて保持し、前記識別子群値のハッシュ値と一致する前記識別子群ハッシュ値候補を前記検索候補表から検索し、検索して得られた前記識別子群ハッシュ値候補に対応する候補ＩＤに応じた前記分類値を出力することを特徴とするパケットクラシファイア装置。
【請求項４】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、前記検索候補表の所定のエントリに前記識別子群値候補としてデータの範囲を指定する範囲指定情報を保持し、前記識別子群値が前記データの範囲を指定する前記識別子群値候補と一致した場合、一致した前記識別子群値候補に対応する候補ＩＤに応じた前記分類値を出力することを特徴とするパケットクラシファイア装置。
【請求項５】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、所定の候補ＩＤに対する前記分類値として、前記入力パケットの廃棄の要否、または前記入力パケットの廃棄の必要性を判断させる廃棄判断の要否を示す情報を示す分類値を生成することを特徴とするパケットクラシファイア装置。
【請求項６】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、所定の候補ＩＤに対する前記分類値として、前記入力パケット中の所定のフィールドを除去させる指示の情報、前記入力パケット中に新たなフィールドを付加し所定のデータを記録させる指示の情報、または前記入力パケット中の所定のフィールドを除去するとともに新たなフィールドを付加し、除去される前記フィールドに記録されたデータを変換して得られるデータを新たに付加される前記フィールドに記録させる指示の情報を示す分類値を生成することを特徴とするパケットクラシファイア装置。
【請求項７】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、前記候補ＩＤとして、前記検索候補表中の所定のエントリの候補ＩＤのみを対象として指定することを特徴とするパケットクラシファイア装置。
【請求項８】
請求項１に記載のパケットクラシファイア装置において、
前記検索部は、前記分類値を前記入力パケットに付加して出力することを特徴とするパケットクラシファイア装置。
【請求項９】
入力パケット中の所定のフィールドに記録された１つ以上のデータである識別子値に基づいて、前記入力パケットを分類する情報である分類値を生成するパケットクラシファイア装置において、
前記識別子値の組み合わせからなる１つ以上の識別子群値のそれぞれに対して、前記識別子群値の１つ以上の識別子群値候補と前記識別子群値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、前記各識別子群値と一致する前記識別子群値候補を対応する前記一次検索候補表中から検索し、検出した前記識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成する一次検索部と、
前記識別子群ＩＤのそれぞれに対して、前記識別子群ＩＤの１つ以上の検索候補と前記検索候補を特定する候補ＩＤとを対応させた二次検索候補表を保持し、前記各識別子群ＩＤと一致する前記検索候補を対応する前記二次検索候補表中から検索し、検索された前記各検索候補に対応する候補ＩＤに応じた前記分類値を生成して出力する二次検索部とを備えることを特徴とするパケットクラシファイア装置。
【請求項１０】
入力パケット中の所定のフィールドに記録された１つ以上のデータである識別子値に基づいて、前記入力パケットを分類する情報である分類値を生成するパケットクラシファイア装置において、
前記識別子値の組み合わせからなる１つ以上の識別子群値のそれぞれに対して、前記識別子群値の１つ以上の識別子群値候補と前記識別子群値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、前記各識別子群値と一致する前記識別子群値候補を対応する前記一次検索候補表中から検索し、検出した前記識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成する一次検索部と、
前記各識別子群ＩＤから１つ以上の所定の前記識別子群ＩＤを選択して１つ以上の選択識別子群ＩＤを生成し、前記各識別子群ＩＤのそれぞれに対して、前記選択識別子群ＩＤの１つ以上の検索候補と前記検索候補を特定する候補ＩＤとを対応させた二次検索候補表を保持し、前記各選択識別子群ＩＤと一致する前記検索候補を対応する前記二次検索候補表中から検索し、検索された前記各検索候補に対応する候補ＩＤに応じた前記分類値を生成して出力する１つ以上の二次検索部とを備えることを特徴とするパケットクラシファイア装置。
【請求項１１】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記一次検索部のいずれかは、前記候補ＩＤに応じたマスクである識別子群マスクを前記識別子群値に施してマスク識別子群値を生成し、前記一次検索候補表で前記候補ＩＤと前記候補ＩＤに応じた識別子群マスクを施した識別子群値候補であるマスク識別子群値候補とを対応させて保持し、前記マスク識別子群値と一致する前記マスク識別子群値候補を前記一次検索候補表から検索し、検索して得られた前記マスク識別子群値候補と対応する前記候補ＩＤに応じた識別子群ＩＤを生成することを特徴とするパケットクラシファイア装置。
【請求項１２】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記一次検索部のいずれかは、前記識別子群値のハッシュ値を算出し、前記一次検索候補表で前記識別子群値のハッシュ値の候補である識別子群ハッシュ値候補と前記識別子群ハッシュ値候補を特定する候補ＩＤとを対応させて保持し、前記識別子群値のハッシュ値と一致する前記識別子群ハッシュ値候補を前記一次検索候補表から検索し、検索して得られた前記識別子群ハッシュ値候補と対応する候補ＩＤに応じた識別子群ＩＤを生成することを特徴とするパケットクラシファイア装置。
【請求項１３】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記一次検索部のいずれかは、前記一次検索候補表の所定のエントリに前記識別子群値候補としてデータの範囲を指定する範囲指定情報を保持し、前記識別子群値が前記データの範囲を指定する前記識別子群値候補と一致した場合、一致した前記識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成することを特徴とするパケットクラシファイア装置。
【請求項１４】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記二次検索部は、所定の候補ＩＤに対する前記分類値として、前記入力パケットの廃棄の要否、または前記入力パケットの廃棄の必要性を判断させる廃棄判断の要否を示す情報を示す分類値を生成することを特徴とするパケットクラシファイア装置。
【請求項１５】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記二次検索部は、所定の候補ＩＤに対する前記分類値として、前記入力パケット中の所定のフィールドを除去させる指示の情報、前記入力パケット中に新たなフィールドを付加し所定のデータを記録させる指示の情報、または前記入力パケット中の所定のフィールドを除去するとともに新たなフィールドを付加し、除去される前記フィールドに記録されたデータを変換して得られるデータを新たに付加される前記フィールドに記録させる指示の情報を示す分類値を生成することを特徴とするパケットクラシファイア装置。
【請求項１６】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記一次検索部は、前記候補ＩＤとして、前記一次検索候補表中の所定のエントリの候補ＩＤのみを対象として指定し、
前記二次検索部は、前記候補ＩＤとして、前記二次検索候補表中の所定のエントリの候補ＩＤのみを対象として指定することを特徴とするパケットクラシファイア装置。
【請求項１７】
請求項９または請求項１０に記載のパケットクラシファイア装置において、
前記二次検索部は、前記分類値を前記入力パケットに付加して出力することを特徴とするパケットクラシファイア装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット通信技術に関し、特にネットワークを介して受信したパケット中に記載されている情報に応じて各パケットを分類するパケットクラシファイア装置に関する。
【背景技術】
【０００２】
従来、受信したパケットの経路制御を行うネットワーク機器として、Ｌ２スイッチ（Layer 2 Switch）やＬ３スイッチ（Layer 3 Switch）などの中継機器が知られている。これらは、それぞれ、ＯＳＩ（Open System Interconnection）参照モデルにおけるレイヤ２、レイヤ３の情報に基づいて、受信したパケットの経路制御などを行うものである。
一方、通信の多様化に伴い、例えばレイヤ３のＩＰ（Internet Protocol）、レイヤ４のＴＣＰ（Transmission Control Protocol）、ＵＤＰ（User Datagram Protocol）などの、様々な通信プロトコルに基づいて通信が行われるようになってきた。
【０００３】
また、通信品質（ＱｏＳ：Quality of Serviceともいう）を考慮した中継機器も研究され、これらの中継機器では、パケットの所定のフィールドに記録された情報、例えばＩＰｖ４の場合は、ＴｏＳ（Type of Service）値などの情報に応じてパケットを振り分けて、パケットごとに異なる通信品質で通信が行われる（例えば、特許文献１など参照）。そして、通信品質に応じて多様にパケットを分類しようとする場合、プログラムに基づいてパケットのヘッダ情報などを読み出すパケット分類が行われていた。
【０００４】
なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
【特許文献１】特開２００３−２４４２２５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような従来のパケット分類技術では、種々の通信プロトコルの下に生成されたパケットを多様に分類しようとする場合、検索処理に要する時間を短縮する工夫が十分なされていないため、処理時間が長く、消費電力が大きく、高価であるなどの問題があった。
本発明はこのような課題を解決するためのものであり、パケット分類に要する処理時間を短縮できるとともに、消費電力を低減することが可能なパケットクラシファイア装置を提供することを目的としている。
【課題を解決するための手段】
【０００６】
このような目的を達成するために、本発明にかかるパケットクラシファイア装置は、入力パケット中の所定のフィールドに記録されたデータからなる１つ以上の識別子値に基づいて、入力パケットを分類する情報として分類値を生成するパケットクラシファイア装置において、入力パケット中の予め特定された識別子値の組み合わせからなる識別子群値について任意の検索候補を検索し、その検索結果に応じて入力パケットに対する分類値を出力する検索部を備え、検索部で、識別子値の組み合わせからなる１つ以上の識別子群値のそれぞれに対して、識別子群値の１つ以上の検索候補と検索候補を特定する候補ＩＤとを対応させた検索候補表を保持し、候補ＩＤのうちの所定の候補ＩＤを順次指定して、各識別子群値と一致する検索候補を対応する検索候補表中から検索し、検索して得られた各検索候補に対応する候補ＩＤに応じた分類値を出力するようにしたものである。
【０００７】
具体的には、検索部で、候補ＩＤに応じたマスクである識別子群マスクを識別子群値に施してマスク識別子群値を生成し、検索候補表で候補ＩＤと候補ＩＤに応じた識別子群マスクを施した識別子群値候補であるマスク識別子群値候補とを対応させて保持し、マスク識別子群値と一致するマスク識別子群値候補を検索候補表から検索し、検索して得られたマスク識別子群値候補に対応する候補ＩＤに応じた分類値を出力するようにしてもよい。
【０００８】
あるいは、検索部で、識別子群値のハッシュ値を算出し、検索候補表で識別子群値のハッシュ値の候補である識別子群ハッシュ値候補と識別子群ハッシュ値候補を特定する候補ＩＤとを対応させて保持し、識別子群値のハッシュ値と一致する識別子群ハッシュ値候補を検索候補表から検索し、検索して得られた識別子群ハッシュ値候補に対応する候補ＩＤに応じた分類値を出力するようにしてもよい。
【０００９】
また、検索部で、検索候補表の所定のエントリに識別子群値候補としてデータの範囲を指定する範囲指定情報を保持し、識別子群値がデータの範囲を指定する識別子群値候補と一致した場合、一致した識別子群値候補に対応する候補ＩＤに応じた分類値を出力するようにしてもよい。
【００１０】
分類値については、検索部で、所定の候補ＩＤに対する分類値として、入力パケットの廃棄の要否、または入力パケットの廃棄の必要性を判断させる廃棄判断の要否を示す情報を示す分類値を生成するようにしてもよい。
【００１１】
あるいは、検索部で、所定の候補ＩＤに対する分類値として、入力パケット中の所定のフィールドを除去させる指示の情報、入力パケット中に新たなフィールドを付加し所定のデータを記録させる指示の情報、または入力パケット中の所定のフィールドを除去するとともに新たなフィールドを付加し、除去されるフィールドに記録されたデータを変換して得られるデータを新たに付加されるフィールドに記録させる指示の情報を示す分類値を生成するようにしてもよい。
【００１２】
また、検索部で、候補ＩＤとして、検索候補表中の所定のエントリの候補ＩＤのみを対象として指定するようにしてもよい。
【００１３】
また、検索部で、分類値を入力パケットに付加して出力するようにしてもよい。
【００１４】
また、本発明にかかる他のパケットクラシファイア装置は、入力パケット中の所定のフィールドに記録された１つ以上のデータである識別子値に基づいて、入力パケットを分類する情報である分類値を生成するパケットクラシファイア装置において、識別子値の組み合わせからなる１つ以上の識別子群値のそれぞれに対して、識別子群値の１つ以上の識別子群値候補と識別子群値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、各識別子群値と一致する識別子群値候補を対応する一次検索候補表中から検索し、検出した識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成する一次検索部と、識別子群ＩＤのそれぞれに対して、識別子群ＩＤの１つ以上の検索候補と検索候補を特定する候補ＩＤとを対応させた二次検索候補表を保持し、各識別子群ＩＤと一致する検索候補を対応する二次検索候補表中から検索し、検索された各検索候補に対応する候補ＩＤに応じた分類値を生成して出力する二次検索部とを備えるものである。
【００１５】
また、本発明にかかる他のパケットクラシファイア装置は、入力パケット中の所定のフィールドに記録された１つ以上のデータである識別子値に基づいて、入力パケットを分類する情報である分類値を生成するパケットクラシファイア装置において、識別子値の組み合わせからなる１つ以上の識別子群値のそれぞれに対して、識別子群値の１つ以上の識別子群値候補と識別子群値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、各識別子群値と一致する識別子群値候補を対応する一次検索候補表中から検索し、検出した識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成する一次検索部と、各識別子群ＩＤから１つ以上の所定の識別子群ＩＤを選択して１つ以上の選択識別子群ＩＤを生成し、各識別子群ＩＤのそれぞれに対して、選択識別子群ＩＤの１つ以上の検索候補と検索候補を特定する候補ＩＤとを対応させた二次検索候補表を保持し、各選択識別子群ＩＤと一致する検索候補を対応する二次検索候補表中から検索し、検索された各検索候補に対応する候補ＩＤに応じた分類値を生成して出力する１つ以上の二次検索部とを備えるものである。
【００１６】
より具体的には、一次検索部のいずれかで、候補ＩＤに応じたマスクである識別子群マスクを識別子群値に施してマスク識別子群値を生成し、一次検索候補表で候補ＩＤと候補ＩＤに応じた識別子群マスクを施した識別子群値候補であるマスク識別子群値候補とを対応させて保持し、マスク識別子群値と一致するマスク識別子群値候補を一次検索候補表から検索し、検索して得られたマスク識別子群値候補と対応する候補ＩＤに応じた識別子群ＩＤを生成するようにしてもよい。
【００１７】
あるいは、一次検索部のいずれかで、識別子群値のハッシュ値を算出し、一次検索候補表で識別子群値のハッシュ値の候補である識別子群ハッシュ値候補と識別子群ハッシュ値候補を特定する候補ＩＤとを対応させて保持し、識別子群値のハッシュ値と一致する識別子群ハッシュ値候補を一次検索候補表から検索し、検索して得られた識別子群ハッシュ値候補と対応する候補ＩＤに応じた識別子群ＩＤを生成するようにしてもよい。
【００１８】
また、一次検索部のいずれかで、一次検索候補表の所定のエントリに識別子群値候補としてデータの範囲を指定する範囲指定情報を保持し、識別子群値がデータの範囲を指定する識別子群値候補と一致した場合、一致した識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成するようにしてもよい。
【００１９】
分類値としては、二次検索部で、所定の候補ＩＤに対する分類値として、入力パケットの廃棄の要否、または入力パケットの廃棄の必要性を判断させる廃棄判断の要否を示す情報を示す分類値を生成するようにしてもよい。
【００２０】
また、二次検索部で、所定の候補ＩＤに対する分類値として、入力パケット中の所定のフィールドを除去させる指示の情報、入力パケット中に新たなフィールドを付加し所定のデータを記録させる指示の情報、または入力パケット中の所定のフィールドを除去するとともに新たなフィールドを付加し、除去されるフィールドに記録されたデータを変換して得られるデータを新たに付加されるフィールドに記録させる指示の情報を示す分類値を生成するようにしてもよい。
【００２１】
また、一次検索部で、候補ＩＤとして、一次検索候補表中の所定のエントリの候補ＩＤのみを対象として指定し、二次検索部で、候補ＩＤとして、二次検索候補表中の所定のエントリの候補ＩＤのみを対象として指定するようにしてもよい。
【００２２】
また、二次検索部で、分類値を入力パケットに付加して出力するようにしてもよい。
【発明の効果】
【００２３】
本発明によれば、入力パケット中の予め特定された識別子値の組み合わせからなる識別子群値と一致する検索候補が、候補ＩＤを順次指定することにより検索候補表中から検索されて、その検索候補に対応する候補ＩＤに応じた分類値が出力されるため、従来のようにプログラムを用いた場合と比較して、パケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できるという効果を有するパケットクラシファイア装置を提供することができるものである。
【発明を実施するための最良の形態】
【００２４】
次に、本発明の実施の形態について図面を参照して説明する。
［第１の実施の形態］
まず、図１を参照して、本発明の第１の実施の形態にかかるパケットクラシファイア装置について説明する。図１は本発明の第１の実施の形態にかかるパケットクラシファイア装置の構成を示すブロック図である。
このパケットクラシファイア装置１００は、入力パケット中の所定のフィールドに記録されたデータに基づいて、入力パケットを分類する装置であり、識別子群生成部１１０、および検索部１２０が設けられている。
【００２５】
識別子群生成部１１０は、当該パケットクラシファイア装置１００の前段に設けられたパケット構文解析装置１０から出力された制御信号に含まれる識別子値［ｍ］（ｍは１〜Ｍの整数、Ｍは自然数）を、複数の識別子群に分けて識別子群値［ｎ］（ｎは１〜Ｎの整数、Ｎは自然数）として出力する回路部である。
検索部１２０は、識別子群生成部１１０から出力された識別子群値［ｎ］を対象に一致検索を行い、検索結果に応じた分類値を出力する回路部である。
【００２６】
ここで、パケット構文解析装置１０は、入力されたパケットデータを構成するパケットの構文解析を行い、例えば送信元アドレス、宛先アドレス、ＴＣＰ（Transmission Control Protocol）ポート番号、次ヘッダＩＤなどを特定する識別子値［ｍ］を、パケット中の対応する情報とタイミングを合わせて生成し、出力するものとする。
【００２７】
また、パケット構文解析装置１０は、パケット構文解析が終了したことを示すフラグ（以下、パケット構文解析終了フラグという）をも出力するものとする。
パケット構文解析終了フラグは、例えば１ビットの信号からなり、パケット構文解析終了フラグが「１」のときパケット構文解析の終了を示し、「０」のときは終了していないことを示すものとする。
【００２８】
識別子群生成部１１０には、各識別子値［ｍ］およびパケット構文解析終了フラグが入力され、パケット構文解析終了フラグが「１」になったことを検出して、識別子群値を生成する処理を開始する。
入力される各識別子値［ｍ］は、パケットデータと、パケットデータ中の識別子値が含まれる部分を特定する識別子マークとして、識別子群生成部１１０に入力されるようにしてもよく、以下では、各識別子値［ｍ］がパケットデータと１つ以上の識別子マークとによって構成されるものとする。
【００２９】
［識別子群生成部］
次に、図２を参照して、識別子群生成部１１０について説明する。図２は、識別子群生成部１１０の具体的構成例を示すブロック図である。
この識別子群生成部１１０には、第ｎの識別子抽出部１１１n（ｎは１〜Ｎの整数）、第ｎのパラメータレジスタ１１２n、および遅延回路１１３，１１４が設けられている。
第ｎの識別子抽出部１１１nは、パケット構文解析装置１０からパケットデータと識別子マークとして各識別子値［ｍ］（ｍは１〜Ｍの整数）が入力され、上記の識別子群値［ｎ］を生成する回路部である。
【００３０】
第ｎのパラメータレジスタ１１２nは、識別子抽出部１１１nの動作を指定する１つ以上のパラメータ（以下、パラメータ群という）を記憶し、記憶したパラメータ群を識別子抽出部１１１nに出力する回路部である。
遅延回路１１３，１１４は、最終の識別子群値の生成処理が終了したタイミングとなるように、入力されたパケット構文解析終了フラグを遅延させる回路部である。
【００３１】
パケットデータおよび識別子マークは、例えば３２ビットずつパラレルに、識別子群生成部１１０に入力してもよい。
各パラメータレジスタ１１２nには、上記のパケットデータおよび識別子マークに加え、リセット、クロック、およびパケット構文解析終了フラグの信号も入力される。ここで、リセットおよびクロックの信号は、外部から入力され、パケットの先頭のタイミングでリセットするように入力されるものとする。
【００３２】
各パラメータレジスタ１１２nは、上記の各識別子マークの比較対象の識別子マーク値［ｋ］（ｋは１〜Ｋの整数，Ｋは自然数）、識別子群長［ｎ］などの、各識別子抽出部１１１nの動作を指定するパラメータ群を記憶する。ここで、「Ｋ」を例えば４とし、識別子マーク値［ｋ］を例えば１バイトのデータとし、識別子群値［ｎ］を例えば４バイト（１ワード）のデータとしてもよい。
このとき、識別子群長［ｎ］を、例えばバイト単位で表し、３ビットのデータとしてもよい。具体的には、識別子群長［ｎ］が「００１」のとき、識別子群値のデータ長が１バイト（８ビット）としてもよい。ここで、各パラメータレジスタ１１２nが記憶するパラメータ群は、外部のＣＰＵなどからの信号に応じて任意に設定できるようにしてもよい。
【００３３】
遅延回路１１３，１１４には、パケット構文解析終了フラグに加え、クロックの信号が入力される。遅延回路１１３，１１４は、本実施例では、入力されたパケット構文解析終了フラグを２クロック分、遅延させるようになっている。
パケット構文解析装置１０からパケット構文解析終了フラグが入力されない場合、パケット構文解析終了フラグは、例えば以下の方法で設定できる。第１の方法は、パケット構文解析装置１０から出力される識別子マークのうち、最終の次ヘッダ位置を示すフラグが検出されたとき、このフラグを用いるものである。第２の方法は、指定した識別子マーク値を検出し、識別子マーク値で特定されるパケットデータが予め指定された値であることを検出したタイミングにフラグを立てるものである。
【００３４】
［識別子抽出部の動作］
次に、図３〜図５を参照して、各識別子抽出部１１１nの動作について説明する。図３〜図５は、各識別子抽出部１１１nの動作をＶＨＤＬ（ＶＨＳＩＣ（Very High Speed Integrated Circuit）−Hardware Description Language）的に記載した説明図である。以下では、４種類（Ｋが４となる）の識別子マーク値と、３２ビットの識別子マークが、パラレルで各識別子抽出部１１１n（ｎは１〜Ｎの整数）に入力されるものとする。
【００３５】
まず、識別子マークのうちの第１ビット目から第８ビット目の値が、識別子マーク値［１］、識別子マーク値［２］、識別子マーク値［３］、または識別子マーク値［４］のうちのいずれか１つ以上と等しいという条件が満たされているか否かを判断する（Ｓ３１１）。以下、この条件をＳ３１１条件という。
ステップＳ３１１でＳ３１１条件が満たされていると判断したとき、「検出ａ」として「１」を代入し（Ｓ３１２）、後述の「格納位置カウンタ値」に「１」を加算して「格納位置ａ」に代入する（Ｓ３１３）。ステップＳ３１１でＳ３１１条件が満たされないと判断したときは、「検出ａ」として「０」を代入し（Ｓ３１４）、後述の「格納位置カウンタ値」を「格納位置ａ」に代入する（Ｓ３１５）。
【００３６】
次に、識別子マークのうちの第９ビット目から第１６ビット目の値が、識別子マーク値［１］、識別子マーク値［２］、識別子マーク値［３］、または識別子マーク値［４］のうちのいずれか１つ以上と等しいという条件が満たされているか否かを判断する（Ｓ３２１）。以下、この条件をＳ３２１条件という。
ステップＳ３２１でＳ３２１条件が満たされていると判断したとき、「検出ｂ」として「１」を代入し（Ｓ３２２）、ステップＳ３１３またはＳ３１５で設定した「格納位置ａ」に「１」を加算して「格納位置ｂ」に代入する（Ｓ３２３）。ステップＳ３２１でＳ３２１条件が満たされないと判断したときは、「検出ｂ」として「０」を代入し（Ｓ３２４）、「格納位置ａ」を「格納位置ｂ」に代入する（Ｓ３２５）。
【００３７】
同様に、識別子マークのうちの第１７ビット目から第２４ビット目の値が、識別子マーク値［１］、識別子マーク値［２］、識別子マーク値［３］、または識別子マーク値［４］のうちのいずれか１つ以上と等しいという条件が満たされているか否かを判断する（Ｓ３３１）。以下、この条件をＳ３３１条件という。
ステップＳ３３１でＳ３３１条件が満たされていると判断したとき、「検出ｃ」として「１」を代入し（Ｓ３３２）、ステップＳ３２３またはＳ３２５で設定した「格納位置ｂ」に「１」を加算して「格納位置ｃ」に代入する（Ｓ３３３）。ステップＳ３３１でＳ３３１条件が満たされないと判断したときは、「検出ｃ」として「０」を代入し（Ｓ３３４）、「格納位置ｂ」を「格納位置ｃ」に代入する（Ｓ３３５）。
【００３８】
同様に、識別子マークのうちの第２５ビット目から第３２ビット目の値が、識別子マーク値［１］、識別子マーク値［２］、識別子マーク値［３］、または識別子マーク値［４］のうちのいずれか１つ以上と等しいという条件が満たされているか否かを判断する（Ｓ３４１）。以下、この条件をＳ３４１条件という。
ステップＳ３４１でＳ３４１条件が満たされていると判断したとき、「検出ｄ」として「１」を代入し（Ｓ３４２）、ステップＳ３３３またはＳ３３５で設定した「格納位置ｃ」に「１」を加算して「格納位置ｄ」に代入する（Ｓ３４３）。ステップＳ３４１でＳ３４１条件が満たされないと判断したときは、「検出ｄ」として「０」を代入し（Ｓ３４４）、「格納位置ｃ」を「格納位置ｄ」に代入する（Ｓ３４５）。
【００３９】
以上の処理によって、識別子マークの検出ごとにフラグ（「検出ａ」〜「検出ｄ」）が立てられ、これらのフラグの位置の情報が、格納位置カウンタの初期値の次から順番に、カウントされ「格納位置ａ」〜「格納位置ｄ」として生成される。
次に、ステップＳ３５１〜Ｓ３５６までの処理は、格納位置カウンタ値を更新する格納位置カウンタ値更新動作の処理である。まず、クロックが入力されたら、以下の各ステップでの処理を開始する（Ｓ３５１）。次に、クロックが立ち上がりのタイミングを検出する（Ｓ３５２）。次に、リセット信号が「１」であるという条件が成立するか否かを判断し（Ｓ３５３）、「１」であると判断したときは、格納位置カウンタ値として「０」を代入する（Ｓ３５４）。これにより、格納位置カウンタ値を初期化する。
【００４０】
ステップＳ３５３でリセット信号が「１」でないと判断したときは、格納位置カウンタ値として「格納位置ｄ」を代入する（Ｓ３５５）。これにより、リセット信号が入力された後のクロックからの、格納位置カウンタ値の更新が行われる。ステップＳ３５５での処理が完了したら格納位置カウンタ値初期化動作の処理は終了する（Ｓ３５６）。
【００４１】
次に、ステップＳ３６１〜Ｓ３７３までの処理は、パケットデータから読み取った識別子の値をレジスタに格納する識別子読取動作の処理である。まず、クロックが入力されたら、以下の各ステップでの処理を開始する（Ｓ３６１）。次に、クロックが立ち上がりのタイミングを検出する（Ｓ３６２）。次に、リセット信号が「１」であるという条件が成立するか否かを判断し（Ｓ３６３）、「１」であると判断したときは、識別子群レジスタ値［１］〜識別子群レジスタ値［Ｎ］として「０」を代入する（Ｓ３６４１〜Ｓ３６４Ｎ）。これにより、識別子群レジスタ値が初期化される。ここで、Ｎは識別子群の総個数である。
【００４２】
ステップＳ３６３でリセット信号が「１」でないと判断したときは、「検出ａ」のフラグが「１」であるか否かを判断し（Ｓ３６５）、「１」であると判断したときは、パケットデータの、例えば１ビット目から８ビット目までのデータを読み出し、識別子群レジスタ値［格納位置ａ］に代入する（Ｓ３６６）。ステップＳ３６５で「検出ａ」のフラグがでないと判断したときは、「検出ｂ」のフラグが「１」であるか否かを判断し（Ｓ３６７）、「１」であると判断したときは、パケットデータの、例えば９ビット目から１６ビット目までのデータを読み出し、識別子群レジスタ値［格納位置ｂ］に代入する（Ｓ３６８）。
【００４３】
同様に、ステップＳ３６７で「検出ｂ」のフラグが「１」でないと判断したときは、「検出ｃ」のフラグが「１」であるか否かを判断し（Ｓ３６９）、「１」であると判断したときは、パケットデータの、例えば１７ビット目から２４ビット目までのデータを読み出し、識別子群レジスタ値［格納位置ｃ］に代入する（Ｓ３７０）。次に、ステップＳ３６９で「検出ｃ」のフラグが「１」でないと判断したときは、「検出ｄ」のフラグが「１」であるか否かを判断し（Ｓ３７１）、「１」であると判断したときは、パケットデータの、例えば２５ビット目から３２ビット目までのデータを読み出し、識別子群レジスタ値［格納位置ｄ］に代入する（Ｓ３７２）。これにより、リセット信号が入力された後のクロックからの、識別子の読み取りが行われる。ステップＳ３７２での処理が完了したら識別子読取動作の処理は終了する（Ｓ３７３）。
【００４４】
次に、ステップＳ３８１〜Ｓ３８７までの処理は、識別子群レジスタ値を識別子群値に代入する識別子群値代入動作の処理である。まず、クロックが入力されたら、以下の各ステップでの処理を開始する（Ｓ３８１）。次に、クロックが立ち上がりのタイミングを検出する（Ｓ３８２）。次に、リセット信号が「１」であるという条件が成立するか否かを判断し（Ｓ３８３）、「１」であると判断したときは、識別子群値［１］〜識別子群値［Ｎ］として「０」を代入する（Ｓ３８４１〜Ｓ３８４Ｎ）。これにより、識別子群値が初期化される。
【００４５】
ステップＳ３８３でリセット信号が「１」でないと判断したときは、「パケット構文解析終了フラグ」が「１」であるか否かを判断し（Ｓ３８５）、「１」であると判断したときは、識別子群レジスタ値［ｎ］を識別子群値［ｎ］に代入する（Ｓ３８６１〜Ｓ３８６Ｎ）。これにより、リセット信号が入力された後のクロックからの、識別子群値への代入が行われる。ステップＳ３８６Ｎでの処理が完了したら識別子群値代入動作の処理は終了する（Ｓ３８７）。
【００４６】
［検索部］
次に、図１を参照して、検索部１２０について説明する。検索部１２０は、各識別子値を組み合わせた１つ以上の識別子群値のそれぞれに対して、識別子群値の１つ以上の検索候補と検索候補を特定する候補ＩＤとを対応させた検索候補表を保持し、候補ＩＤのうちの所定の候補ＩＤを順次指定して各識別子群値と一致する検索候補を対応する検索候補表中から検索し、検索して得られた各検索候補に対応する候補ＩＤに応じた分類値を、入力パケットに別途付加して、または入力パケットとは別個に出力するようになっている。
【００４７】
具体的構成として、検索部１２０には、識別子群検索器１２１1〜１２１N、候補ＩＤ生成器１２２、ＡＮＤ回路１２３、一致候補ＩＤ記憶器１２４、および分類値生成器１２５が設けられている。
識別子群検索器１２１1〜１２１Nは、識別子群生成部１１０から出力された各識別子群値［ｎ］（ｎは１〜Ｎの整数）が入力され、所定の検索を行い、検索で一致するデータがあったか否かを示す一致フラグ［ｎ］を出力する１つ以上の回路部である。
候補ＩＤ生成器１２２は、各識別子群検索器１２１1〜１２１Nに検索対象の候補を特定する候補ＩＤを出力する回路部である。
【００４８】
ＡＮＤ回路１２３は、各識別子群検索器１２１1〜１２１Nから出力された一致フラグ［ｎ］がすべて一致することを示す「１」の値の信号であるとき「１」になり、その他のときは「０」の値をとる全一致フラグを出力する回路部である。
一致候補ＩＤ記憶器１２４は、識別子群生成終了フラグ、全一致フラグおよび候補ＩＤが入力され、全一致フラグが「１」のときの候補ＩＤを記憶し、一致候補ＩＤおよび検索終了フラグを出力する回路部である。
分類値生成器１２５は、一致候補ＩＤおよび検索終了フラグが入力され、分類値を生成する回路部である。
【００４９】
第ｎの識別子群検索器１２１nには、識別子群生成部１１０から出力された各識別子群値［ｎ］と、候補ＩＤ生成器１２２から出力された候補ＩＤとが入力される。ここで、識別子群検索器１２１nには、予めＫ個の識別子群候補［ｎ、ｋ］（ｋは１〜Ｋの整数）が検索候補表として格納されているものとする。
ここで、ｋは候補ＩＤによって指定され、Ｋは識別子群検索器１２１nごとに異なるものでもよい。また、識別子群検索器１２１nが記憶する識別子群候補［ｎ、ｋ］は、外部から設定できるようにしてもよい。
【００５０】
第ｎの識別子群検索器１２１nは、候補ＩＤ生成器１２２から出力された候補ＩＤで特定される識別子群候補［ｎ、ｋ］と識別子群値［ｎ］との一致判定を候補ＩＤの順番で行い、一致したときに一致フラグ［ｎ］をＡＮＤ回路１２３に出力する。
他の各識別子群検索器についても、第ｎの識別子群検索器１２１nと同様の信号が入力されて同様の処理がなされ、同様の信号が出力される。ただし、識別子群候補は、識別子群検索器ごとに異なる。
【００５１】
第ｎの識別子群検索器１２１nは、さらに図６および図７に示すように構成してもよい。ここで、識別子群値のすべてのビットを識別子群候補と比較しなくても一致判定ができる場合がある。
図６に示す構成では、このような場合に、識別子群値のビットのうちの比較する必要のないビットにマスクを施し、マスクを施した識別子群値と識別子群候補とを比較するようになっている。
【００５２】
検索部１２０を構成する所定の識別子群検索器１２１nは、検索候補表の所定のエントリに識別子群値候補としてデータの範囲を指定する範囲指定情報が記録され、識別子群値がデータの範囲を指定する識別子群値候補と一致するとき、一致する識別子群値候補に対応する候補ＩＤに応じた分類値を入力パケットに別途付加して出力するようにしてもよい。
また、検索部１２０を構成する所定の識別子群検索器１２１nは、候補ＩＤが検索候補表中の所定のエントリの候補ＩＤのみを対象として指定するようにしてもよい。
【００５３】
図６に示す第ｎの識別子群検索器１２１nには、マスク処理器６１１、候補マスクレジスタ６１２、選択器６１３、比較処理器６２１、識別子群値候補レジスタ６２２、および選択器６２３が設けられている。
マスク処理器６１１は、入力された識別子群値［ｎ］にマスクを施す処理（以下、マスク処理という）を行う回路部である。
候補マスクレジスタ６１２は、マスク処理器６１１が行うマスク処理に用いられるマスク（以下、識別子群マスクという）の候補を検索候補表として記憶する回路部である。
【００５４】
選択器６１３は、入力された候補ＩＤに応じて候補マスクレジスタ６１２が記憶する識別子群マスクを選択してマスク処理器６１１に出力する回路部である。
比較処理器６２１は、マスク処理後の識別子群値（以下、マスク識別子群値という）と識別子群値候補（以下、マスク識別子群値候補という）とを比較し、一致判定を行う回路部である。
識別子群値候補レジスタ６２２は、マスク識別子群値の比較対象であるマスク識別子群値候補を検索候補表として記憶する回路部である。
選択器６２３は、入力された候補ＩＤに応じて識別子群値候補レジスタ６２２が記憶するマスク識別子群値候補を選択して比較処理器６２１に出力する回路部である。
【００５５】
識別子群マスクは、例えば「０」と「１」の組み合わせであり、マスク処理器６１１は例えばＡＮＤ回路からなり、マスク識別子群値［ｎ］は例えば「０」の値をとるビットが所定数以上並び、比較対象でないことを示すようにしてもよい。
比較処理器６２１は、一致判定の結果を「０」と「１」からなる一致フラグとして出力する。一致フラグが「１」のときは一致したことを示し、「０」のときは一致しなかったことを示す。
【００５６】
上記のように構成することにより、ＩＰｖ４アドレスのように、識別子の一部に所定のマスクをかけて一致判定を行うことが一般的な識別子と、ＭＡＣ（Media Access Control）アドレスなどのマスク処理が不要な識別子とが識別子群値に混在する場合、すべての識別子にマスク情報を指定するのではなく、マスクが必要な識別子のみにマスク情報を指定し、マスク処理を行うことが可能となるため、例えばマスク情報を記憶するメモリの容量の削減などの回路規模の削減と、マスク処理の処理量の削減が可能となる。
【００５７】
また、識別子が長く、すべてのビットを対象に一致処理を行うのでは、処理に時間がかかることがある。図７に示す構成は、識別子のハッシュ値を算出し、得られたハッシュ値を対象に一致処理を行い、一致したときに全体のビットについて一致判定を行い、処理時間を削減するものである。
【００５８】
図７に示す第ｎの識別子群検索器１２１nには、ハッシュ処理器７０１、ハッシュ値比較処理器７１１、ハッシュ候補レジスタ７１２、選択器７１３、一致検証処理器７２１、識別子群値候補レジスタ７２２、および選択器７２３が設けられている。
ハッシュ処理器７０１は、入力された識別子群値［ｎ］のハッシュ値を算出する回路部である。
ハッシュ値比較処理器７１１は、ハッシュ処理器７０１が算出したハッシュ値と比較対象の候補（以下、識別子群ハッシュ値候補という）とを比較し、その結果をハッシュ値一致フラグとして出力する回路部である。
ハッシュ候補レジスタ７１２は、ハッシュ値比較処理器７１１が比較に用いる識別子群ハッシュ値候補を検索候補表として記憶する回路部である。
【００５９】
選択器７１３は、入力された候補ＩＤに応じてハッシュ候補レジスタ７１２が記憶する識別子群ハッシュ値候補を選択してハッシュ値比較処理器７１１に出力する回路部である。
一致検証処理器７２１は、ハッシュ値比較処理器７１１から出力されたハッシュ値一致フラグが一致を示すとき、識別子群と識別子群値候補とを比較し、一致判定を行う回路部である。
識別子群値候補レジスタ７２２は、識別子群値の比較対象である識別子群値候補を検索候補表として記憶する回路部である。
選択器７２３は、入力された候補ＩＤに応じて識別子群値候補レジスタ７２２が記憶する識別子群値候補を選択して一致検証処理器７２１に出力する回路部である。
【００６０】
ここで、ハッシュ値を生成する技術については、公知であり、その説明を省略する。また、ハッシュ処理器７０１が算出するハッシュ値は、そのビット数が入力された識別子群のビット数より少なく、ハッシュ処理器７０１での処理時間を短縮できるような値をとるものとする。ハッシュ値の生成方法は、特定のものに限定されるものではなく、本発明の趣旨に沿うものであればその種類を問題としない。
【００６１】
ハッシュ値比較処理器７１１が出力するハッシュ値一致フラグは、ハッシュ値一致フラグが「１」のとき、ハッシュ処理器７０１が算出したハッシュ値と識別子群ハッシュ値候補とが一致したことを示し、「０」のときは一致しなかったことを示す。
同様に、一致検証処理器７２１が出力する一致フラグは、一致フラグが「１」のとき、識別子群と識別子群値候補とが一致したことを示し、「０」のときは一致しなかったことを示す。
【００６２】
上記のように構成することにより、ＩＰｖ６アドレスのように識別子のビット数が多い識別子を検索するときに、全ビットの一致を直接判定するのではなく、ハッシュ処理によってビット数を短縮した後で一致判定を行うことにより、処理時間を短縮することが可能となる。特に、候補数が多い場合は、ハッシュ処理を行うことによって処理時間を短縮できる。
【００６３】
一致候補ＩＤ記憶器１２４は、識別子群生成終了フラグが入力された後、全一致フラグが「１」になったときの候補ＩＤ（上記の一致候補ＩＤ）を記憶し、検索終了フラグとともに分類値生成器１２５に出力する。
複数の候補ＩＤのときに一致する場合は、最優先の候補ＩＤ（例えば、一致した候補のうちの最小値）を一致候補としてもよい。
また、全一致フラグが「１」となる回数が最大１回に限られる場合や、最優先の候補から順に候補ＩＤが生成されている場合などでは、候補ＩＤで示すすべての候補が一致すると判断した（全一致フラグが「１」）時点で、以後の一致判定を中断して、一致候補ＩＤと検索終了フラグを出力するようにしてもよい。
【００６４】
分類値生成器１２５は、Ｋ個の分類候補を保持し、検索終了フラグと一致候補ＩＤが入力されたら、入力された一致候補ＩＤに対応する分類候補［Ｌ］（＝分類候補［一致候補ＩＤ］。Ｌは１〜Ｋの整数）を選択し、分類値として出力する。
分類値生成器１２５から出力される分類値は、パケットクラシファイア装置１００の出力であり、他の装置で、パケットデータの分類を行うときに利用することができる。
【００６５】
上記の検索部１２０は、所定の候補ＩＤに対して、入力パケットの廃棄の要否（例えば、フィルタ処理）、または入力パケットの廃棄の必要性を判断させる廃棄判断の要否を示す情報を示す分類値を生成するようにしてもよい。
また、検索部１２０は、所定の候補ＩＤに対して、入力パケット中の所定のフィールドを除去させる指示の情報、入力パケット中に新たなフィールドを付加し所定のデータを記録させる指示の情報、または入力パケット中の所定のフィールドを除去するとともに新たなフィールドを付加し、除去されるフィールドに記録されたデータを変換して得られるデータを新たに付加されるフィールドに記録させる指示の情報を示す分類値を生成するようにしてもよい。
【００６６】
以上説明したように、本発明の第１の実施の形態にかかるパケットクラシファイア装置は、入力パケット中の予め特定された識別子値の組み合わせからなる識別子群値と一致する検索候補について、候補ＩＤを順次指定することにより検索候補表中から検索し、その検索候補に対応する候補ＩＤに応じた分類値を出力するようにしたので、従来のようにプログラムを用いた場合と比較して、パケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できるという効果を有するパケットクラシファイア装置を提供することができるものである。
【００６７】
また、ビット数の長い識別子群値などの検索候補に応じてマスクを施して検索を行うようにしたため、一致判定を行うビット数を低減でき、さらにパケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
また、ビット数の長い識別子群値などの検索候補に応じてハッシュ値を算出し、ハッシュ値を対象として予備的に検索を行うようにしたため、個々のビット数の長い識別子群値の一致判定を行うビット数を低減でき、さらにパケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
【００６８】
また、識別子群値候補としてデータの範囲を指定する範囲指定情報を検索候補表にエントリするようにしたため、検索候補表の規模を小さくすることができ、回路規模を縮小することができる。
また、入力パケットの廃棄などの要否を分類値として生成するため、判断に時間を要する処理を分類して専用の装置などに出力することが可能となり、回路規模を縮小できるとともに、上記の専用の装置などが行う処理の負担を軽減することができる。
【００６９】
また、入力パケット中の所定のフィールドの除去、付加、書き換えなどを示す分類値を生成できるため、タグの付け替えなどの処理を指示することができる。
また、検索候補表中の所定のエントリの候補ＩＤのみを検索対象とすることができるため、パケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
【００７０】
［第２の実施の形態］
次に、図８を参照して、本発明の第２の実施の形態にかかるパケットクラシファイア装置について説明する。図８は、本発明の第２の実施の形態にかかるパケットクラシファイア装置のブロック構成を示す図である。
図８において、パケットクラシファイア装置８００は、本発明の第１の実施の形態の検索部１２０が、一次検索部８２０n（ｎは１〜Ｎの整数）と、二次検索部８３０とに分けられた構成を有している。
本発明の第２の実施の形態にかかる識別子群生成部８１０は、出力信号の出力先が本発明の第１の実施の形態にかかる識別子群生成部１１０と異なるため、符号を変えているが処理内容は、識別子群生成部１１０と同様である。
【００７１】
各一次検索部８２０nは、各識別子値を組み合わせた１つ以上の識別子群値のそれぞれに対して、識別子群値の１つ以上の識別子群値候補と、識別子群値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、各識別子群値と一致する識別子群値候補を対応する一次検索候補表中から検索し、検出した識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成するようになっており、識別子群生成部１１０から出力された識別子群値［ｎ］をデータ数の少ない識別子群ＩＤに変換するものである。
【００７２】
［一次検索部］
次に、図９を参照して、本発明の第２の実施の形態にかかる各一次検索部について説明する。図９（ａ）は、本発明の第２の実施の形態にかかる各一次検索部８２０nのブロック構成を示す図である。
図９（ａ）において、各一次検索部８２０nには、識別子群検索器８２１n候補ＩＤ生成器８２２n、および一致候補ＩＤ記憶器８２３nが設けられている。
【００７３】
識別子群検索器８２１nは、識別子群生成部８１０から出力された識別子群値［ｎ］を識別子群ＩＤ［ｎ］に変換するための検索を行う回路部である。
候補ＩＤ生成器８２２nは、識別子群検索器８２１nが検索する対象候補を指定する候補ＩＤを出力する回路部である。
一致候補ＩＤ記憶器８２３nは、識別子群検索器８２１nが行った検索で一致が得られたとき、一致の得られた候補ＩＤに応じて識別子群ＩＤ［ｎ］を出力する回路部である。
【００７４】
識別子群検索器８２１nには、識別子群値［ｎ］と、候補ＩＤ生成器８２２nから出力された候補ＩＤとが入力される。
識別子群検索器８２１nは、識別子群値［ｎ］と比較対象の１つ以上、候補を予め記憶しておき、候補ＩＤ生成器８２２nから出力された候補ＩＤに対応する比較対象の候補と、上記の識別子群値［ｎ］との一致判定を行い、その結果を一致フラグとして出力する。
識別子群検索器８２１nが記憶する識別子群の１つ以上の候補を候補ＩＤごとに対応させた表が、上記の一次検索候補表である。一致フラグは、一致判定で一致と判定されたときに「１」の値をとり、一致と判定されないときは「０」の値をとるフラグである。
【００７５】
ここで、上記の「比較対象の候補」は外部のＣＰＵなどからの入力に応じて変更できるようにしてもよい。
また、各識別子群検索器８２１nは、異なる方法で検索を行うようにしてもよく、その際、上記の「比較対象の候補」は、識別子群検索器８２１nごとに異なるものを用いてもよい。さらに候補ＩＤ生成器８２２nが発生する候補ＩＤについても、上記の「比較対象の候補」と同様に、外部から変更できるようにしてもよい。
【００７６】
一致候補ＩＤ記憶器８２３nには、識別子群検索器８２１nが出力した一致フラグと、候補ＩＤ生成器８２２nが出力した候補ＩＤとが入力される。
一致候補ＩＤ記憶器８２３nは、識別子群検索器８２１nから一致を示す一致フラグ（値が「１」をとる）が入力された際に、候補ＩＤに応じた識別子群ＩＤ［ｎ］を生成し、出力する。
ここで、識別子群ＩＤ［ｎ］を、一致フラグが「１」のときの候補ＩＤとし、処理時間の短縮を図るようにしてもよい。一致候補ＩＤ記憶器８２３nは、また、検索が終了したことを示す検索終了フラグ［ｎ］を一致フラグとともに出力する。
【００７７】
［二次検索部］
次に、図９を参照して、本発明の第２の実施の形態にかかる二次検索部について説明する。図９（ｂ）は、本発明の第２の実施の形態にかかる二次検索部８３０のブロック構成を示す図である。
二次検索部８３０は、識別子群ＩＤのそれぞれに対して、識別子群ＩＤの１つ以上の検索候補と、検索候補を特定する候補ＩＤとを対応させた二次検索候補表を保持し、各識別子群ＩＤと一致する検索候補を対応する二次検索候補表中から検索し、検索された各検索候補に対応する候補ＩＤに応じた分類値を生成し、入力パケットに別途付加して、または入力パケットとは別個に出力するようになっている。
【００７８】
具体的には、二次検索部８３０には、識別子群ＩＤ検索器８３１n、候補ＩＤ生成器８３２、全一致フラグ生成ＡＮＤ回路８３３、全終了フラグＡＮＤ回路８３４、一致候補ＩＤ記憶器８３５、および分類値生成器８３６が設けられている。
識別子群ＩＤ検索器８３１nは、各一次検索部８２０nから出力された識別子群ＩＤ［ｎ］に基づいて検索を行い、検索の結果を内容とする一致フラグを出力する回路部である。
【００７９】
候補ＩＤ生成器８３２は、識別子群ＩＤ検索器８３１nが検索する対象候補を指定する候補ＩＤを出力する回路部である。
全一致フラグ生成ＡＮＤ回路８３３は、各識別子群ＩＤ検索器８３１nが出力したすべての一致フラグが一致したか否かを内容とする全一致フラグを出力する回路部である。
全終了フラグＡＮＤ回路８３４は、各一次検索部８２０nから出力された検索終了フラグがすべて検索の終了を示すか否かを内容とする全検索終了フラグを出力する回路部である。
【００８０】
一致候補ＩＤ記憶器８３５は、全検索終了フラグ、全一致フラグおよび候補ＩＤが入力され、全一致フラグが「１」のときの候補ＩＤを記憶し、一致候補ＩＤおよび検索終了フラグを出力する回路部である。
分類値生成器８３６は、一致候補ＩＤおよび検索終了フラグが入力され、分類値を生成する回路部である。
【００８１】
識別子群ＩＤ検索器８３１nが記憶する識別子群の１つ以上の候補を候補ＩＤごとに対応させた表が、二次検索候補表である。
識別子群ＩＤ検索器８３１nおよび候補ＩＤ生成器８３２は、本発明の第１の実施の形態の第ｎの識別子群検索器１２１nおよび候補ＩＤ生成器１２２とは、検索対象が識別子群ＩＤ［ｎ］であるという点で異なるが、構成および動作は同様であり、これらの構成および動作についての説明は省略する。
同様に、全一致フラグ生成ＡＮＤ回路８３３および分類値生成器８３６は、本発明の第１の実施の形態のＡＮＤ回路１２３および一致候補ＩＤ記憶器１２４についても、構成および動作についての説明は省略する。
【００８２】
全終了フラグＡＮＤ回路８３４には、各一次検索部８２０nから出力された検索終了フラグ［ｎ］が入力される。
全終了フラグＡＮＤ回路８３４は、入力されたすべての検索終了フラグ［ｎ］が検索の終了を示すときに例えば「１」の値をとり、いずれか１つ以上の検索終了フラグが検索が終了していないことを示すときに例えば「０」の値をとる全検索終了フラグを出力するようになっている。以下では、全検索終了フラグの値を上記のように定義されるものとする。
【００８３】
一致候補ＩＤ記憶器８３５は、上記の全検索終了フラグが「１」のとき、処理を行い、全一致フラグが「１」になったときの候補ＩＤ（上記の一致候補ＩＤ）を記憶し、検索終了フラグとともに分類値生成器８３６に出力する。
一致候補ＩＤ記憶器８３５は、全検索終了フラグが「１」のときに処理を行う点を除けば、本発明の第１の実施の形態の分類値生成器１２５と同様の処理を行うようにしてもよい。
【００８４】
ここで、上記のいずれか１つ以上の一次検索部８２０nが、候補ＩＤに応じたマスクである識別子群マスクを識別子群値に施してマスク識別子群値を生成し、一次検索候補表が、候補ＩＤと、候補ＩＤに応じた識別子群マスクを施した識別子群値候補であるマスク識別子群値候補とを対応させた一次検索候補表を保持し、マスク識別子群値と一致するマスク識別子群値候補を一次検索候補表から検索し、検索して得られたマスク識別子群値候補と対応する候補ＩＤに応じた識別子群ＩＤを生成するように構成してもよい。
【００８５】
また、上記のいずれか１つ以上の一次検索部８２０nが、識別子群値のハッシュ値を算出し、一次検索候補表が、識別子群値のハッシュ値の候補である識別子群ハッシュ値候補と、識別子群ハッシュ値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、識別子群値のハッシュ値と一致する識別子群ハッシュ値候補を一次検索候補表から検索し、検索して得られた識別子群ハッシュ値候補と対応する候補ＩＤに応じた識別子群ＩＤを生成するように構成してもよい。
【００８６】
また、上記のいずれか１つ以上の一次検索部８２０nが、一次検索候補表の所定のエントリに識別子群値候補としてデータの範囲を指定する範囲指定情報が記録され、識別子群値がデータの範囲を指定する識別子群値候補と一致するとき、一致する識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成するように構成してもよい。
また、上記の二次検索部８３０が、所定の候補ＩＤに対して、入力パケットの廃棄の要否、または入力パケットの廃棄の必要性を判断させる廃棄判断の要否を示す情報を示す分類値を生成するように構成してもよい。
【００８７】
また、上記の二次検索部８３０が、所定の候補ＩＤに対して、入力パケット中の所定のフィールドを除去させる指示の情報、入力パケット中に新たなフィールドを付加し所定のデータを記録させる指示の情報、または入力パケット中の所定のフィールドを除去するとともに新たなフィールドを付加し、除去されるフィールドに記録されたデータを変換して得られるデータを新たに付加されるフィールドに記録させる指示の情報を示す分類値を生成するように構成してもよい。
【００８８】
また、上記のいずれか１つ以上の一次検索部８２０nが、候補ＩＤが一次検索候補表中の所定のエントリの候補ＩＤのみを対象として指定し、上記の二次検索部８３０が、候補ＩＤが二次検索候補表中の所定のエントリの候補ＩＤのみを対象として指定するように構成してもよい。
【００８９】
以上説明したように、本発明の第２の実施の形態にかかるパケットクラシファイア装置は、一次検索部を設け、識別子群値をＩＤ化してから二次検索部が検索を行うようにしたため、パケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
また、ビット数の長い識別子群値などの検索候補に応じてマスクを施して検索を行うようにしたため、一致判定を行うビット数を低減でき、さらにパケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
【００９０】
また、ビット数の長い識別子群値などの検索候補に応じてハッシュ値を算出し、ハッシュ値を対象として予備的に検索を行うようにしたため、個々のビット数の長い識別子群値の一致判定を行うビット数を低減でき、さらにパケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
また、識別子群値候補としてデータの範囲を指定する範囲指定情報を検索候補表にエントリするようにしたため、検索候補表の規模を小さくすることができ、回路規模を縮小することができる。
【００９１】
また、入力パケットの廃棄などの要否を分類値として生成するため、判断に時間を要する処理を分類して専用の装置などに出力することが可能となり、回路規模を縮小できるとともに、上記の専用の装置などが行う処理の負担を軽減することができる。
また、入力パケット中の所定のフィールドの除去、付加、書き換えなどを示す分類値を生成できるため、タグの付け替えなどの処理を指示することができる。
また、検索候補表中の所定のエントリの候補ＩＤのみを検索対象とすることができるため、パケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
【００９２】
［第３の実施の形態］
次に、図３を参照して、本発明の第３の実施の形態にかかるパケットクラシファイア装置について説明する。図１０は、本発明の第３の実施の形態にかかるパケットクラシファイア装置のブロック構成を示す図である。
図１０において、パケットクラシファイア装置１０００は、識別子群値を、一次検索部８２０n（ｎは１〜Ｎの整数）に入力する識別子群値［ｎ］（ｎは１〜Ｎの整数）と、一次検索部８２０nを介さず、直接、二次検索部８３０に入力する識別子群値［ｎ］（ｎはＮ＋１〜Ｎ＋Ｏの整数，ＮおよびＯは自然数）分けて処理を行うようになっている。
【００９３】
本発明の第３の実施の形態にかかるパケットクラシファイア装置１０００の各構成部のうち、本発明の第１の実施の形態にかかるパケットクラシファイア装置１００または本発明の第２の実施の形態にかかるパケットクラシファイア装置８００の構成部と同様のものについては、同一の符号を付し、その説明を省略する。
また、本発明の第３の実施の形態にかかる識別子群生成部１０１０は、出力信号の出力先が本発明の第１の実施の形態にかかる識別子群生成部１１０と異なるため、符号を変えているが処理内容は、識別子群生成部１１０と同様である。
【００９４】
図１１は、本発明の第３の実施の形態にかかる二次検索部１０３０のブロック構成を示す図である。図１１において、二次検索部１０３０には、識別子群検索器１２１n（ｎは１〜Ｎの整数）、識別子群ＩＤ検索器８３１n（ｎはＮ＋１〜Ｎ＋Ｏの整数，ＮおよびＯは自然数）、候補ＩＤ生成器１０３２、全一致フラグ生成ＡＮＤ回路１０３３、全終了フラグＡＮＤ回路８３４、一致候補ＩＤ記憶器１０３５、および分類値生成器１０３６が設けられている。
【００９５】
識別子群検索器１２１nは、本発明の第１の実施の形態の識別子群検索器１２１nからなり、識別子群ＩＤ検索器８３１nは、本発明の第２の実施の形態の識別子群ＩＤ検索器８３１nからなる。
候補ＩＤ生成器１０３２各識別子群検索器にそれぞれの候補ＩＤを出力する回路部である。
全一致フラグ生成ＡＮＤ回路１０３３は、各識別子群検索器１２１nおよび各識別子群ＩＤ検索器８３１nが出力したすべての一致フラグが一致したか否かを内容とする全一致フラグを出力する回路部である。
【００９６】
全終了フラグＡＮＤ回路８３４は、各一次検索部８２０nから出力された検索終了フラグがすべて検索の終了を示すか否かを内容とする全検索終了フラグを出力すると回路部である。
一致候補ＩＤ記憶器１０３５は、全検索終了フラグ、全一致フラグおよび候補ＩＤが入力され、全一致フラグが「１」のときの候補ＩＤを記憶し、一致候補ＩＤおよび検索終了フラグを出力する回路部である。
分類値生成器１０３６は、一致候補ＩＤおよび検索終了フラグが入力され、分類値を生成する回路部である。
【００９７】
本発明の第３の実施の形態にかかる候補ＩＤ生成器１０３２、全一致フラグ生成ＡＮＤ回路１０３３、一致候補ＩＤ記憶器１０３５および分類値生成器１０３６は、それぞれ、本発明の第２の実施の形態にかかる候補ＩＤ生成器８３２、全一致フラグ生成ＡＮＤ回路８３３、一致候補ＩＤ記憶器８３５および分類値生成器８３６と、構成および動作が同様であり、これらの構成および動作についての説明は省略する。
【００９８】
このように、本発明の第３の実施の形態にかかるパケットクラシファイア装置１０００は、識別子群をＩＤ化して検索を行う方法と、識別子群を、直接、検索する方法とを併せ持つものである。
このようにすることにより、ＩＤ化できる識別子群に関しては、処理を大幅に削減できるとともに、ＩＤ化できない識別子群が含まれる場合でも処理が可能となる。ここで、「ＩＤ化できない識別子群」としては、例えばポート番号などの値を範囲で示したものなどが該当する。
【００９９】
以上説明したように、本発明の第３の実施の形態にかかるパケットクラシファイア装置は、本発明の第２の実施の形態の効果に加え、識別子群値をＩＤ化できるものとできないものと分けて処理をできるようにしたため、種々の識別子群値を分類することができる。
【０１００】
［第４の実施の形態］
次に、図１２を参照して、本発明の第４の実施の形態にかかるパケットクラシファイア装置について説明する。図１２は、本発明の第４の実施の形態にかかるパケットクラシファイア装置のブロック構成を示す図である。
図１２において、本発明の第４の実施の形態にかかるパケットクラシファイア装置１２００の構成部のうち、本発明の第２の実施の形態にかかるパケットクラシファイア装置８００の構成部と同様のものには、同一の符号を付し、その説明を省略する。
【０１０１】
本発明の第４の実施の形態にかかるパケットクラシファイア装置１２００は、識別子群生成部８１０と、一次検索部８２０n（ｎは１〜Ｎの整数）と、所定の識別子群ＩＤの組み合わせで検索を行う複数の二次検索部１２３０p（ｐは１〜Ｐの整数、Ｐは自然数）と、パケットデータを二次検索部１２３０p（ｐは１〜Ｐの整数）が行う処理に要する処理時間分だけ遅延させるパケットバッファ部１２４０とを備えている。
【０１０２】
このうち、一次検索部８２０nは、各識別子値を組み合わせた１つ以上の識別子群値のそれぞれに対して、識別子群値の１つ以上の識別子群値候補と、識別子群値候補を特定する候補ＩＤとを対応させた一次検索候補表を保持し、各識別子群値と一致する識別子群値候補を対応する一次検索候補表中から検索し、検出した識別子群値候補に対応する候補ＩＤに応じた識別子群ＩＤを生成する。
【０１０３】
また、二次検索部１２３０pは、各識別子群ＩＤから１つ以上の所定の識別子群ＩＤを選択して１つ以上の選択識別子群ＩＤを生成し、各識別子群ＩＤのそれぞれに対して、選択識別子群ＩＤの１つ以上の検索候補と、検索候補を特定する候補ＩＤとを対応させた二次検索候補表を保持し、各選択識別子群ＩＤと一致する検索候補を対応する二次検索候補表中から検索し、検索された各検索候補に対応する候補ＩＤに応じた分類値を生成し、入力パケットに別途付加して出力するようになっている。
【０１０４】
本発明の第４の実施の形態にかかる二次検索部１２３０pは、所定のパケット処理を行うパケット処理部２０p（ｐは１〜Ｐの整数）ごとに設けられている。
ここで、上記のパケット処理は、分類値［ｐ］に応じて異なるキューにパケットを振り分けるＱｏＳ（Quality of Service）処理、分類値［Ｐ］に応じてパケットを廃棄などするフィルタ処理、分類値［Ｐ］に応じてパケットの特定のヘッダを書き換え、追加、または、削除するヘッダ変更処理、分類値［Ｐ］に応じて暗号化、復号化、署名データの付与、認識などを行うパケット認証暗号処理（例えば、ＩＰｓｅｃ：Security Architecture for the Internet Protocol）があげられる。
【０１０５】
ここで、上記の「ヘッダ変更処理」には、例えばＩＰカプセル化の処理、ＮＡＴ（Network Address Translation）およびＶＬＡＮ（Virtual LAN）のタグ処理が含まれる。
そのため、本発明の第４の実施の形態にかかるパケットクラシファイア装置１２００は、パケットクラシファイア装置１２００での処理後に行うパケット処理に応じて、二次検索部１２３０pが設けられているという見方もできる。
【０１０６】
ここで、本発明の第４の実施の形態にかかる二次検索部１２３０pは、Ｓ個の検索識別子群選択器１２３１s（ｓは１〜Ｓの整数、Ｓは自然数）が、各識別子群ＩＤ検索器８３１sの前段に設けられている点では異なるが、各識別子群ＩＤ検索器８３１s以降、分類値生成器８３６までの構成および動作は、本発明の第２の実施の形態において説明したものと同様である。
【０１０７】
検索識別子群選択器１２３１sは、入力された識別子群ＩＤ［ｎ］（ｎは１〜Ｎの整数）から所定の識別子群ＩＤを選択して識別子群ＩＤ検索器８３１sに出力するようになっている。ここで、検索識別子群選択器１２３１sが選択する識別子群ＩＤは、固定されていてもよく、外部のＣＰＵなどからの入力で変更できるようにしてもよい。
【０１０８】
また、検索識別子群選択器の個数「Ｓ」は、二次検索部１２３０pごとに異なっていてもよい。個数「Ｓ」をパケット処理部２０pが行うパケット処理（同様に、二次検索部１２３０pが行う検索）に応じて変更できるようにしてもよい。
パケット処理によっては、検索対象とすべき識別子群や、その識別子群の数も異なるからである。ここで、パケット処理と二次検索部１２３０pの構成および動作が関連付けられ、固定されている場合、個数「Ｓ」を予め関連が固定されたパケット処理に合わせておくことで、回路規模を削減できる。
【０１０９】
さらに、すべての検索識別子群選択器１２３１sが識別子群ＩＤを選択して識別子群ＩＤ検索器８３１sに出力するのでな、外部のＣＰＵなどからの入力で識別子群ＩＤを選択して出力する検索識別子群選択器を変更できるようにしてもよい。
また、一部の固定された検索識別子群選択器１２３１sが識別子群ＩＤを選択して識別子群ＩＤ検索器８３１sに出力するようにしてもよい。
この場合、二次検索部１２３０p、識別子群ＩＤ検索器８３１sなどの変更に要する手段（例えば、上記の外部のＣＰＵなど）を削除または小規模にできるため好適である。
【０１１０】
以上説明したように、本発明の第４の実施の形態にかかるパケットクラシファイア装置は、本発明の第２の実施の形態の効果に加え、出力後のパケット処理ごとに二次検索部を設け、識別子群値をＩＤ化してから二次検索部がＩＤ化した識別子群値を選択し、選択されたものを対象に検索を行うようにしたため、二次検索部での処理量を稼ぐことができ、さらにパケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できる。
【産業上の利用分野】
【０１１１】
本発明にかかるパケットクラシファイア装置は、パケットを分類するのに要する処理時間を短縮できるとともに、消費電力を低減できるという効果が有用なネットワーク上の中継器やスイッチなどの用途にも適用できる。
【図面の簡単な説明】
【０１１２】
【図１】本発明の一実施の形態にかかるパケットクラシファイア装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態にかかる識別子群生成部の構成を示すブロック図である。
【図３】本発明の第１の実施の形態にかかる識別子群生成部の動作について説明するための図である。
【図４】本発明の第１の実施の形態にかかる識別子群生成部の動作について説明するための図である。
【図５】本発明の第１の実施の形態にかかる識別子群生成部の動作について説明するための図である。
【図６】本発明の第１の実施の形態にかかる識別子群検索器のブロック構成例である。
【図７】本発明の第１の実施の形態にかかる識別子群検索器の他のブロック構成例である。
【図８】本発明の第２の実施の形態にかかるパケットクラシファイア装置の構成を示すブロック図である。
【図９】本発明の第２の実施の形態にかかる各一次検索部および二次検索部の構成を示すブロック図である。
【図１０】本発明の第３の実施の形態にかかるパケットクラシファイア装置の構成を示すブロック図である。
【図１１】本発明の第３の実施の形態にかかる二次検索部の構成を示すブロック図である。
【図１２】本発明の第４の実施の形態にかかるパケットクラシファイア装置の構成を示すブロック図である。
【図１３】本発明の第４の実施の形態にかかる各二次検索部の構成を示すブロック図である。
【符号の説明】
【０１１３】
１０…パケット構文解析装置、１００，８００，１０００，１２００…パケットクラシファイア装置、１１０，８１０，１０１０…識別子群生成部、１１１1〜１１１N，１１１n…識別子抽出部、１１２1〜１１２N，１１２n…パラメータレジスタ、１１３，１１４…遅延回路、１２０…検索部、１２１1〜１２１N，１２１n，８２１n…識別子群検索器、１２２，８２２n，８３２，１０３２…候補ＩＤ生成器、１２３…ＡＮＤ回路、１２４，８２３n，８３５，１０３５…一致候補ＩＤ記憶器、１２５，８３６，１０３６…分類値生成器、６１１…マスク処理器、６１２…候補マスクレジスタ、６１３，６２３，７１３，７２３…選択器、６２１…比較処理器、６２２…識別子群値候補レジスタ、７０１…ハッシュ処理器、７１１…ハッシュ値比較処理器、７１２…ハッシュ候補レジスタ、７２１…一致検証処理器、７２２…識別子群値候補レジスタ、８２０1〜８２０N，８２０n…一次検索部、８３０，１０３０，１２３０1〜１２３０P，１２３０p…二次検索部、８３１1〜８３１N，８３１n，８３１s…識別子群ＩＤ検索器、８３３，１０３３…全一致フラグ生成ＡＮＤ回路、８３４…全終了フラグＡＮＤ回路、１２３１1〜１２３１S，１２３１s…検索識別子群選択器。
【図１】
2005303417.tif 000003
【図２】
2005303417.tif 000004
【図３】
2005303417.tif 000005
【図４】
2005303417.tif 000006
【図５】
2005303417.tif 000007
【図６】
2005303417.tif 000008
【図７】
2005303417.tif 000009
【図８】
2005303417.tif 000010
【図９】
2005303417.tif 000011
【図１０】
2005303417.tif 000012
【図１１】
2005303417.tif 000013
【図１２】
2005303417.tif 000014
【図１３】
2005303417.tif 000015