(57)【要約】【課題】パケットフィルタ回路およびパケットフィルタリング装置において、小型化、高速化を実現する。【解決手段】複数の一致条件と、受信したパケットとを比較してパケットフィルタリングを行うパケットフィルタリング回路１０は、バッファ回路１１と、不一致判定回路１３と、部分一致判定回路１４とを含む。不一致判定回路１３は、パケットに含まれる照合データを、いくつかのビット群に分割し、分割された部分ごとに一致条件の一部分と比較する。不一致判定回路１３は、分割された照合データの、少なくともいずれかのビット群で一致条件と不一致の場合に、照合データと一致条件とが不一致であると判定する。部分一致判定回路１４は、不一致判定回路１３で不一致と判定されない場合に、複数の一致条件のうち、照合データの一部のビット群と一致する一致条件について、照合データと比較する。【選択図】図６
2013236245.tif 000002
【特許請求の範囲】
【請求項１】
複数の一致条件と、受信したパケットとの比較結果に基づいてパケットフィルタリングを行うパケットフィルタ回路であって、
受信したパケットを保持するバッファ回路と、
前記パケットに含まれる、第１および第２のビット群からなる照合データの前記第１のビット群を、各前記一致条件の第１の部分と比較し、前記第２のビット群を、各前記一致条件の第２の部分と比較し、少なくともいずれかのビット群で前記照合データと不一致の場合に、前記照合データと前記一致条件とが不一致であると判定する不一致判定回路と、
前記第１および第２のビット群のいずれもが各前記一致条件の各部分と一致する場合に、複数の前記一致条件のうち、前記第１の部分が前記照合データの第１のビット群と一致する一致条件について、前記照合データと一致するか否かを判定する部分一致判定回路とを含み、
前記バッファ回路は、前記不一致判定回路および前記部分一致判定回路による判定結果に応じてパケットを処理する、
パケットフィルタ回路。
【請求項２】
前記部分一致判定回路は、
複数の前記一致条件の前記第２の部分それぞれを部分一致判定条件として記憶するための第２のメモリを含み、
前記不一致判定回路は、
複数の前記一致条件の前記第１の部分の値それぞれと、当該第１の部分の値に対応する第２の部分の値の前記第２のメモリにおける格納アドレスとを対応づけて不一致判定条件として記憶するための第１のメモリを含み、前記照合データの第１のビット群と、前記第１の部分とが一致する場合に、当該一致する値と対応づけられた前記格納アドレスを読み出して出力し、
前記部分一致判定回路は、前記不一致判定回路により出力される格納アドレスに基づいて、前記第２のメモリから前記第２の部分を読み出すことにより前記判定を行う、
請求項１記載のパケットフィルタ回路。
【請求項３】
前記第２のメモリは、
各アドレスについて、次に前記第２のメモリにおいてアクセスすべきアドレスを示すアドレスフィールド、および、前記一致条件の第２の部分の値を格納するデータフィールドとを含み、
前記部分一致判定回路は、複数の前記一致条件の前記第１の部分の値に対応する第２の部分の値が複数ある場合に、前記アドレスフィールドに示されるアドレスに従って、逐次、前記データフィールドに格納される値を出力することにより前記判定を行う、
請求項２記載のパケットフィルタ回路。
【請求項４】
前記部分一致判定回路は、
前記バッファ回路から前記照合データの第２のビット群を受け付け、受け付けた前記第２のビット群と、前記第２のメモリにおいて指定されたアドレスの前記データフィールドに格納される値とを比較して一致または不一致の比較結果を出力する比較器を含み、
前記比較器による比較結果が不一致の場合に、前記第２のメモリの前記アドレスフィールドに示される値に従って前記照合データと前記一致条件とを比較する、
請求項３記載のパケットフィルタ回路。
【請求項５】
前記パケットフィルタ回路は、
前記不一致判定回路により不一致と判定されず、かつ、前記部分一致判定回路により一致と判定される場合に、一致信号を前記バッファ回路へ出力する判定結果出力回路を含む、
請求項１記載のパケットフィルタ回路。
【請求項６】
前記パケットフィルタ回路は、
前記不一致判定回路により不一致と判定された場合、または、前記部分一致判定回路により不一致と判定された場合に、不一致信号を前記バッファ回路へ出力する判定結果出力回路を含む、
請求項１記載のパケットフィルタ回路。
【請求項７】
複数の一致条件と、受信したパケットとの比較結果に基づいてパケットフィルタリングを行うパケットフィルタリング装置であって、
受信したパケットを保持するバッファ部と、
前記パケットに含まれる、第１および第２のビット群からなる照合データの前記第１のビット群を、各前記一致条件の第１の部分と比較し、前記第２のビット群を、各前記一致条件の第２の部分と比較し、少なくともいずれかのビット群で前記照合データと不一致の場合に、前記照合データと前記一致条件とが不一致であると判定する不一致判定部と、
前記第１および第２のビット群のいずれもが各前記一致条件の各部分と一致する場合に、複数の前記一致条件のうち、前記第１の部分が前記照合データの第１のビット群と一致する一致条件について、前記照合データと一致するか否かを判定する部分一致判定部とを含み、
前記バッファ部は、前記不一致判定部および前記部分一致判定部による判定結果に応じてパケットを処理する、
パケットフィルタリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットフィルタ回路およびパケットフィルタリング装置に関し、特に、小型化、高速化を実現するための技術に関する。
【背景技術】
【０００２】
近年、無線通信機器が普及するとともに、通信速度も高速化してきており、通信トラフィックが増加している。高速の通信を実現するため、パケットフィルタリングの高速化も求められている。パケットフィルタリングを行うパケットフィルタ回路は、ＴＣＡＭ（Ternary  Content  Addressable  Memory）等の専用のメモリ回路を備えることにより、高速化を実現している。
【０００３】
また、小型の通信機器の通信機能、通信速度が向上しており、家庭内でネットワークを構成する機器も増加している。そのため、組み込み機器にも使用できる、小型で低消費電力を実現するパケットフィルタリング装置が必要とされている。
【０００４】
通常、パケットフィルタ回路は、パケットを蓄えるパケットバッファと、予め１以上の一致条件を登録した一致判定回路とにより構成される。このパケットフィルタ回路は、ルータやサーバ等で使用される。また、下記の非特許文献１に記載の技術は、パケットバッファと、一致判定回路と、不一致判定回路とを備えている。一致判定回路は、照合データと、各一致条件とを逐次比較する。不一致判定回路は、一度のメモリアクセスにより、照合データと各一致条件との不一致を判定する。そのため、非特許文献１に記載の技術は、受信したパケットと、各一致条件とが一致しない場合は、一致判定回路による各照合が完了する前に、不一致判定回路により不一致を判定することにより、高速化を実現している。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】三浦直樹、他５名、「不一致判定回路を用いた高速パケットフィルタ回路」、電子情報通信学会技術研究報告、社団法人  電子情報通信学会、２００９年３月、第１０８巻、４７８号、p.101‐106
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記非特許文献１に記載の不一致判定回路は、高速化を実現するために、メモリを用いて照合データと一致条件とを比較している。非特許文献１では、メモリの各アドレスに「一致」か「不一致」かの判定結果を格納する。このとき、判定結果「一致」を格納するアドレスは、一致条件の値と対応している。その他のアドレスには判定結果「不一致」が格納される。パケットフィルタ回路は、照合データの値を、メモリの読み出しアドレスとしてメモリの各アドレスに格納される判定結果を参照することにより、「不一致」か「一致」かを判定する。
【０００７】
このように、非特許文献１は、照合データがとりうる値の範囲が大きくなるほど、より大きなメモリ領域を確保する必要がある。例えば照合データがｎビットであると、２＾ｎ（「＾」は、べき乗を示す）個の判定結果を格納するためのメモリ領域が必要となる。そこで、必要となるメモリ領域を削減するため、ｎビットの照合データをｍビットごとに分割して照合する（ｍ＜ｎ）。ｍビットの照合に必要なメモリ領域は、２＾ｍであるため、この手法によると、判定結果を格納するために必要なメモリ領域が、２＾ｎから（ｎ／ｍ）×２＾ｍに削減することができる。
【０００８】
ただし、上記の場合、ｍビットごとに分割して判定するため、不一致と判定すべきデータを不一致と判定できない場合がある。例えば、一致条件が１６ビットの0x1234と0x4567である場合（「0x」は16進数であることを示す）、0x1237という照合データは、本来は不一致と判定されるべきである。しかし、不一致判定回路において、４ビットごとに分割して判定すると、この場合は不一致と判定されない。そのため、不一致判定回路において不一致と判定されない場合は、一致判定回路による照合データと一致条件との比較処理を待つ必要があり、パケットフィルタリングが遅延する。
【０００９】
そのため、パケットフィルタ回路において、さらなる高速化の技術が必要とされている。
【００１０】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１１】
一実施の形態に従うパケットフィルタ回路は、複数の一致条件と、受信したパケットとの比較結果に基づいてパケットフィルタリングを行うものであり、バッファ回路と、不一致判定回路と、部分一致判定回路とを含む。バッファ回路は、受信したパケットを保持する。不一致判定回路は、パケットに含まれる照合データを、いくつかのビット群に分割し、分割された部分ごとに一致条件の一部分と比較する。不一致判定回路は、分割された照合データの、少なくともいずれかのビット群で一致条件と不一致の場合に、照合データと一致条件とが不一致であると判定する。部分一致判定回路は、不一致判定回路で不一致と判定されない場合に、複数の一致条件のうち、照合データの一部のビット群と一致する一致条件について、照合データと一致条件とが一致するか否かを判定する。バッファ回路は、不一致判定回路および部分一致判定回路による判定結果に応じてパケットを処理する。
【発明の効果】
【００１２】
一実施の形態に従うパケットフィルタ回路は、不一致判定回路において、照合データと複数の一致条件とを所定のビット群ごとに比較し、不一致判定回路で不一致と判定されない場合に、一致判定回路において照合データと一致条件との比較に要する時間を短縮化することができ、パケットフィルタリングの効率が向上する。
【図面の簡単な説明】
【００１３】
【図１】関連技術におけるパケットフィルタリング装置５１の構成を示す機能ブロック図である。
【図２】関連技術における一致条件６１と、不一致判定回路５４による判定方法とを示す図である。
【図３】関連技術において、不一致判定回路５４が不一致を判定できない状況を示す図である。
【図４】パケットフィルタリング装置１の構成を示す図である。
【図５】パケットフィルタ回路１０の構成を示す機能ブロック図である。
【図６】パケットフィルタ回路１０の構成を示す図である。
【図７】第１の一致条件保持部２１ａを構成するメモリの詳細を示す図である。
【図８】部分一致判定条件保持メモリ２３の記憶内容例を示す図である。
【図９】一致条件の一例と、本実施形態における照合データと一致条件との比較例を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照しつつ、本発明の実施の形態について説明する。以下の説明では、同一の部品には同一の符号を付してある。それらの名称および機能も同じである。したがって、それらについての詳細な説明は繰り返さない。
【００１５】
＜１．１  関連技術の構成の詳細＞
ここで、本実施形態と比較するため、関連技術の構成を説明する。
【００１６】
図１は、関連技術におけるパケットフィルタリング装置５１の構成を示す機能ブロック図である。パケットフィルタリング装置５１は、パケットを転送するか否かを判定するための複数の一致条件（パケットの転送を許可するＩＰアドレス等）を保持している。パケットフィルタリング装置５１は、パケットに含まれる照合データ（一致条件と比較するためのパケットの一部分であり、例えばパケットのヘッダに含まれる送信先アドレス）が一致条件と一致するか否かに応じてパケットを処理する。パケットの処理とは、例えば、照合データと一致条件とが一致する場合は、パケットフィルタリング装置５１は、パケット転送等の処理を行う。また、パケットフィルタリング装置５１は、照合データが一致条件の全てと不一致の場合は、パケットを廃棄する等の処理を行う。
【００１７】
図１に示すように、パケットフィルタリング装置５１は、バッファ回路５２と、一致判定回路５３と、不一致判定回路５４と、ＯＲ回路５５とを含む。
【００１８】
バッファ回路５２は、パケットフィルタリング装置５１が外部の通信機器より受け付けたパケットを蓄積する。また、パケットフィルタリング装置５１は、外部の通信機器からの判定要求に応じて、パケットフィルタリングを開始する。パケットフィルタリング装置５１は、一致判定回路５３および不一致判定回路５４による判定結果に従って、パケットを処理する。
【００１９】
一致判定回路５３は、複数の一致条件を保持しており、照合データをバッファ回路５２から受け付けて、照合データを、複数の一致条件と逐次比較し、いずれかの一致条件と一致するか否かを判定する。一致判定回路５３は、照合データに一致する一致条件があると判定した場合は、一致判定信号をバッファ回路５２へ出力する。一致判定回路５３は、全ての一致条件と照合データとを比較して、照合データに一致する一致条件がないと判定した場合は、不一致判定信号をＯＲ回路５５へ出力する。
【００２０】
不一致判定回路５４は、照合データと一致条件とが不一致であるか判定する。不一致判定回路５４は、メモリを含み、メモリアドレスと対応づけて、一致または不一致の判定結果を格納する。不一致判定回路５４は、照合データをもとにしたアドレスを参照することにより、照合データと一致条件とが不一致であるか判定する。この場合、一致条件のビット数に応じたメモリ領域が必要となる。
【００２１】
例えば一致条件が１６ビットであれば、２＾１６個の判定結果を格納するメモリ領域が必要となる。そこで、この関連技術では、メモリ領域の削減のため、一致条件を４ビットごとに４つに分割して、分割された各部分において取りうる値の範囲をメモリアドレスとして各アドレスにおいて一致または不一致の判定結果を格納する。この場合、必要なメモリ領域は、４×２＾４となる。詳しくは後述する。
【００２２】
ＯＲ回路５５は、不一致判定回路５４および一致判定回路５３の出力結果を受け付けて、いずれかにおいて不一致判定信号が出力された場合に、不一致判定信号をバッファ回路５２へ出力する。
【００２３】
関連技術においては、照合データと一致条件とが不一致である場合、不一致判定回路５４では、メモリアドレスを参照することにより判定結果が得られる。これに対し、一致判定回路５３では、照合データを、個々の一致条件と逐次比較する。そのため不一致判定回路５４の判定結果が一致判定回路５３よりも早く出力される傾向にある。ただし、不一致判定回路５４では、一致条件を分割して照合データと比較しているため、不一致判定回路５４において不一致と判定されない場合であっても、照合データと一致条件とが不一致であることがある。この場合は、一致判定回路５３により全ての一致条件と照合データとを比較するまで不一致を確定することができず、処理が遅延する。
【００２４】
＜１．２  関連技術における不一致判定回路５４の不一致判定方法＞
図２は、関連技術における一致条件６１と、不一致判定回路５４による判定方法とを示す図である。
【００２５】
例えば、図２に示すように、一致条件６１は、「0x1234」（第１の一致条件６１ａ）と「0x4567」（第２の一致条件６１ｂ）であるとする。
【００２６】
不一致判定回路５４は、一致条件６１を４つに分割し、各部分について、メモリアドレスのインデックス値と対応づけて一致または不一致の判定結果を格納している（第１の一致条件保持部７１、第２の一致条件保持部７２、第３の一致条件保持部７３、第４の一致条件保持部７４）。例えば第１の一致条件保持部７１は、一致条件６１の始めの４ビットの判定結果をメモリアドレスと対応づけて格納している。図２の例では、一致条件６１の始めの４ビットは、第１の一致条件６１ａは「１」、第２の一致条件６１ｂは「４」である。そこで、第１の一致条件保持部７１は、メモリアドレスのインデックス値「１」と「４」とに対応づけて、判定結果「一致」を格納している。第２の一致条件保持部７２、第３の一致条件保持部７３、第４の一致条件保持部７４についても同様に、一致条件６１の各部分の判定結果を、メモリアドレスのインデックス値と対応づけて格納している。
【００２７】
こうすることにより、不一致判定回路５４において、照合データが一致条件６１と不一致であるか判定するのに必要な領域は、４×２＾４個となる。
【００２８】
＜１．３  関連技術の不一致判定回路５４が不一致を判定できない状況＞
図３は、関連技術において、不一致判定回路５４が不一致を判定できない状況を示す図である。
【００２９】
図３において、一致条件は図２と同様、「0x1234」と「0x4567」とする。照合データ７６の値が「0x1237」の場合に、不一致判定回路５４において照合データ７６が各一致条件と不一致であるか、図３に示すように判定される。すなわち、照合データ７６の始めの４ビットに示される値「0x1」に基づいて、第１の一致条件７１保持部のメモリアドレスのインデックスを参照して判定結果「一致」がメモリから読みだされる。同様に、照合データ７６の４ビットごとのビット群が一致条件の一部分と一致するか不一致であるか判定される。
【００３０】
ＯＲ回路７５は、第１の一致条件保持部７１、第２の一致条件保持部７２、第３の一致条件保持部７３、第４の一致条件保持部７４の各メモリの少なくともいずれか１つから不一致が読みだされれば「不一致」を出力する。しかし、この場合、いずれのメモリからも「一致」が読みだされるため、ＯＲ回路７５は、判定結果「不一致」を出力せず、「一致」を出力する。
【００３１】
このように、照合データの各ビット群を、一致条件の各部分と比較した場合、実際は照合データと一致条件とが不一致である場合においても、不一致判定回路５４から「不一致」が出力されないことがある。そのため、パケットフィルタリング装置５１において不一致を確定するには、一致判定回路５３による判定結果を待つ必要がある。
【００３２】
＜２．１  本実施形態のパケットフィルタリング装置１の構成の概要＞
次に、図面を用いて本実施形態のパケットフィルタリング装置１の構成について、まず概要を説明する。
【００３３】
図４は、パケットフィルタリング装置１の構成を示す図である。
図４に示すように、パケットフィルタリング装置１は、ＭＰＵ（Micro-Processing  Unit）２と、ＲＡＭ（Random  Access  Memory）３と、ＲＯＭ(Read  Only  Memory）４と、通信モジュール５と、パケットフィルタ回路１０とを含む。
【００３４】
ＭＰＵ２は、プロセッサ等を備え、通信モジュール５やパケットフィルタ回路１０等の動作を制御して、パケットフィルタリング装置１のパケットフィルタリング処理を制御する。
【００３５】
ＲＡＭ３は、ＭＰＵ２の処理に供するため、ＲＯＭ４から読みだされたプログラムやデータ等を保持するメモリ領域である。
【００３６】
ＲＯＭ４は、プログラムやデータ等を格納する。
通信モジュール５は、外部の通信機器と通信するための通信インタフェースである。通信モジュール５は、例えば有線ＬＡＮ（Local  Area  Network）、無線ＬＡＮ（IEEE  802.11n）による通信インタフェースに対応している。
【００３７】
パケットフィルタ回路１０は、通信モジュール５により受信されたパケットを保持し、パケットに含まれる照合データ（パケットヘッダの一部分など）が一致条件と一致するか否かに応じてパケットフィルタリングを行う。一致条件は、パケットフィルタ回路１０において、パケットを転送するか廃棄するか等の処理を行うため、照合データと比較されるデータである。例えば、照合データが、パケットヘッダに含まれる送信先ＩＰアドレスであれば、個々の一致条件は、パケットフィルタリング装置１がパケットの転送を許可する情報通信機器のＩＰアドレスである。本実施形態では、照合データと、複数の一致条件のいずれかとが一致する場合はパケットを転送し、一致しない場合は、パケットを廃棄する。
【００３８】
なお、本実施形態では、照合データと、複数の一致条件それぞれとを比較するため、一致条件を複数のビット群に分割して（本実施形態では、照合データおよび一致条件を１６ビットのデータとし、一致条件を４ビットごとに分割している）、不一致判定回路１３において不一致判定条件２１としてメモリにおいて保持している。また、部分一致判定回路１４において、一致条件の一部（一致条件のうち１２ビット）を部分一致判定条件２２としてメモリにおいて保持している。
【００３９】
パケットフィルタ回路１０は、図４に示すように、バッファ回路１１と、判定結果出力回路１２と、不一致判定回路１３と、部分一致判定回路１４とを含む。パケットフィルタ回路１０は、ＭＰＵ２の判定要求に応じてパケットフィルタリングを行う。詳しくは後述する。
【００４０】
＜２．２  パケットフィルタ回路１０の構成＞
図５は、パケットフィルタ回路１０の構成を示す機能ブロック図である。
【００４１】
図５に示すように、パケットフィルタ回路１０は、通信モジュール５において受信されたパケットを受け付け、ＭＰＵ２からパケットの判定要求を受け付けることによりパケットフィルタリングを開始する。
【００４２】
バッファ回路１１は、パケットを保持するとともに、パケットの判定要求を受け付けて部分一致判定回路１４および不一致判定回路１３へ判定開始信号を出力する。バッファ回路１１は、後述する判定結果出力回路１２から出力される判定結果に応じた処理を行う。例えば、バッファ回路１１は、照合データと一致条件とが一致する場合はパケット転送等の処理を行い、不一致の場合はパケットを廃棄する等の処理を行う。
【００４３】
不一致判定回路１３は、照合データと、一致条件とが不一致であるか判定する。上記のように、不一致判定回路１３は、一致条件を複数のビット群に分割して不一致判定条件２１として保持しており、照合データを、所定ビットずつ、並列に、一致条件の各部分と比較する。不一致判定回路１３の詳細は後述するが、不一致判定回路１３は、照合データの、各ビット群の比較結果の少なくともいずれかが不一致であれば不一致判定信号を判定結果出力回路１２へ出力する。一方、不一致判定回路１３は、照合データの、各ビット群の比較結果がいずれも一致であれば、部分一致判定回路１４において部分一致判定条件２２を保持しているメモリのアドレスのインデックス値を示す値を部分一致判定回路１４へ出力する。
【００４４】
部分一致判定回路１４は、照合データと、一致条件とが一致するか判定する。上記のように、部分一致判定回路１４は、一致条件を部分一致判定条件２２として保持している。部分一致判定回路１４の詳細は後述するが、部分一致判定回路１４は、不一致判定回路１３において、照合データの各ビット群の比較結果がいずれも一致する場合に、複数の一致条件のうち、照合データの一部のビット群と一致する一致条件について、逐次、照合データと比較する。このように、部分一致判定回路１４は、照合データと比較するための一致条件の範囲を一部に限定して、照合データと一致条件とが一致するか判定する。そのため、パケットフィルタリング装置１は、照合データと一致条件とが不一致の場合に、関連技術のように全ての一致条件と照合データとを比較する場合よりも、比較回数を減らすことができる。
【００４５】
判定結果出力回路１２は、不一致判定回路１３および部分一致判定回路１４による、照合データと一致条件との比較結果に基づいて、照合データと一致条件とが一致するか不一致であるかを出力する。詳細は後述するが、判定結果出力回路１２は、不一致判定回路１３により不一致と判定されず、かつ、部分一致判定回路１４により一致と判定される場合に、一致判定信号をバッファ回路１１へ出力する。また、判定結果出力回路１２は、不一致判定回路１３により不一致と判定された場合、または、部分一致判定回路１４により不一致と判定された場合に、不一致判定信号をバッファ回路１１へ出力する。
【００４６】
＜２．３  パケットフィルタ回路１０の詳細＞
次に、図面を用いてパケットフィルタ回路１０の詳細な構成を説明する。
【００４７】
図６は、パケットフィルタ回路１０の構成を示す図である。
＜２．３．１  バッファ回路１１＞
図６に示すように、バッファ回路１１は、照合データを保持している。図６の例では、照合データを１６ビットとし、４ビットごとの４つのビット群（Ａ，Ｂ，Ｃ，Ｄの４つのビット群）に分割して不一致判定回路１３へ出力している。
【００４８】
図示する例において、照合データの「Ａ」のビット群を第１のビット群とし、「Ｂ」「Ｃ」「Ｄ」の３つのビット群を第２のビット群とすると、バッファ回路１１は、第２のビット群を比較器４９へ出力する。
【００４９】
＜２．３．２  不一致判定回路１３＞
不一致判定回路１３は、照合データの各ビット群と、一致条件の各部分とを並列に比較して比較結果を出力する。不一致判定回路１３は、第１の不一致判定部３０と、第２の不一致判定部３１と、第３の不一致判定部３２と、第４の不一致判定部３３と、ＮＯＲ回路３４とを含む。不一致判定回路１３は、第１の不一致判定部３０、第２の不一致判定部３１、第３の不一致判定部３２、第４の不一致判定部３３を用いて、照合データの各ビット群を、並列に一致条件と比較する。
【００５０】
第１の不一致判定部３０は、ラッチ回路４０と、ＤＥＣ（デコーダ）８０と、第１の一致条件保持部２１ａとを含む。図示する例では、第１の不一致判定部３０は、照合データの「Ａ」のビット群について、対応する一致条件の一部分との一致または不一致を出力する。
【００５１】
ラッチ回路４０は、照合データの一部のビット群（ビット群「Ａ」）のデータを保持する。
【００５２】
第１の一致条件保持部２１ａは、メモリにより構成され、一致条件の一部分の取りうる値をインデックスアドレスと対応づけて、一致または不一致の判定結果を格納する。
【００５３】
第１の一致条件保持部２１ａを保持するメモリについて、詳細を説明する。
図７は、第１の一致条件保持部２１ａを構成するメモリの詳細を示す図である。
【００５４】
第１の一致条件保持部２１ａを構成するメモリは、アドレス２１ｅと、判定結果格納領域２１ｆと、条件番号２１ｇとにより構成される。なお、図６に示す第１の一致条件保持部２１ａでは、アドレス２１ｅを省略して示している。
【００５５】
アドレス２１ｅは、照合データの「Ａ」のビット群において取りうる値と対応づけられている。本実施形態では、照合データの「Ａ」のビット群は４ビットであるとしているため、アドレス２１ｅにおいて、アドレス「０」から「１５」まで用意されている。
【００５６】
判定結果２１ｆは、アドレス２１ｅに示される、照合データの「Ａ」のビット群において取りうる値と対応づけられて、一致条件と一致しているか不一致であるかの判定結果を格納する領域である。
【００５７】
条件番号２１ｇは、判定結果２１ｆにおいて「一致」の判定結果を格納するものについて、後述する部分一致判定条件２２を保持するメモリにおいて参照すべきインデックスアドレスの値を格納する。判定結果２１ｆにおいて「不一致」の判定結果を格納するものについては、条件番号２１ｇは値を格納していない。
【００５８】
図６に戻り説明を続ける。
ＤＥＣ８０は、第１の一致条件保持部２１ａを構成するメモリに対し、ラッチ回路４０において保持されている値に対応するアドレスのメモリ領域を活性化させる。
【００５９】
第１の不一致判定部３０は、ＤＥＣ８０により活性化されたアドレスにかかるメモリ領域の判定結果２１ｆを読み出してＮＯＲ回路３４に出力するとともに、条件番号２１ｇを読み出して部分一致判定回路１４のセレクタ４６へ出力する。なお、本実施形態では、不一致判定回路１３は、ＮＯＲ回路３４において、第１の不一致判定部３０、第２の不一致判定部３１、第３の不一致判定部３２、第４の不一致判定部３３の少なくともいずれかから「不一致」の判定結果が出力された場合に、不一致と判定することとする。そのため、第１の一致条件保持部２１ａを構成するメモリにおいて、照合データの「Ａ」のビット群に対応する判定結果２１ｆが「不一致」であれば、信号ＨＩが出力される。
【００６０】
第２の不一致判定部３１は、ラッチ回路４１と、ＤＥＣ８１と、第２の一致条件保持部２１ｂとを含む。図示する例では、第２の不一致判定部３１は、照合データの「Ｂ」のビット群について、対応する一致条件の一部分との一致または不一致を出力する。
【００６１】
ラッチ回路４１は、照合データの一部のビット群（ビット群「Ｂ」）のデータを保持する。
【００６２】
第２の一致条件保持部２１ｂは、メモリにより構成され、一致条件の一部分の取りうる値をインデックスアドレスと対応づけて、一致または不一致の判定結果を格納する。第２の一致条件保持部２１ｂを構成するメモリは、図７を用いると、アドレス２１ｅと、判定結果２１ｆとにより構成される。第２の一致条件保持部２１ｂを構成するメモリは、照合データの「Ｂ」のビット群が取りうる値をインデックスアドレスと対応づけて、判定結果２１ｆにおいて「一致」または「不一致」の判定結果を格納する。
【００６３】
第３の不一致判定部３２、第４の不一致判定部３３は、第２の不一致判定部３１と同様の構成を備える。相違点は、第２の不一致判定部３１が照合データの「Ｂ」のビット群について、一致条件と比較した処理を行うのに対し、第３の不一致判定部３２は、照合データの「Ｃ」のビット群について処理し、第４の不一致判定部３３は、照合データの「Ｄ」のビット群について処理する点である。
【００６４】
第３の不一致判定部３２は、ラッチ回路４２と、ＤＥＣ８２と、第３の一致条件保持部２１ｃとを含む。第３の一致条件保持部２１ｃを構成するメモリは、第２の一致条件保持部２１ｂと同様に、アドレス２１ｅと、判定結果２１ｆとにより構成される。第３の一致条件保持部２１ｃを構成するメモリは、照合データの「Ｃ」のビット群が取りうる値をインデックスアドレスと対応づけて、判定結果２１ｆにおいて「一致」または「不一致」の判定結果を格納する。
【００６５】
第４の不一致判定部３３は、ラッチ回路４３と、ＤＥＣ８３と、第４の一致条件保持部２１ｄとを含む。第４の一致条件保持部２１ｄを構成するメモリは、照合データの「Ｄ」のビット群が取りうる値をインデックスアドレスと対応づけて、判定結果２１ｆにおいて「一致」または「不一致」の判定結果を格納する。
【００６６】
ＮＯＲ回路３４は、不一致判定回路１３における判定結果を出力する。なお、本実施形態では、第１の不一致判定部３０等において不一致と判定された場合に第１の不一致判定部３０等から信号ＨＩが出力されることとしているが、不一致判定回路１３の出力としては、不一致と判定された場合はＮＯＲ回路３４により信号ＬＯＷが出力される。そのため、第１の一致条件保持部２１ａ等のいずれにおいても「一致」が読みだされた場合は、ＮＯＲ回路３４の出力信号は信号ＨＩとなる。
【００６７】
＜２．３．３  部分一致判定回路１４＞
部分一致判定回路１４は、照合データと一致条件とが一致するか判定する。部分一致判定回路１４は、不一致判定回路１３において照合データの第１のビット群（照合データの「Ａ」のビット群）が一致条件と一致する場合に、照合データと比較する一致条件の範囲を、照合データの第１のビット群と一致するものに絞る。
【００６８】
部分一致判定回路１４は、部分一致判定条件保持メモリ２３と、ラッチ回路４４と、制御回路４５と、セレクタ４６と、比較回路４７と、ＡＮＤ回路４８と、比較器４９と、ＤＥＣ８４とを含む。
【００６９】
セレクタ４６は、第１の一致条件保持部２１ａの条件番号２１ｇの出力と、後述する部分一致判定条件保持メモリ２３のアドレスフィールドに示される値とを受け付けて、いずれかの値を、後述する制御回路４５の制御によりラッチ回路４４へ出力する。
【００７０】
ラッチ回路４４は、セレクタ４６から出力される値を保持する。
ＤＥＣ８４は、部分一致判定条件保持メモリ２３に対し、ラッチ回路４４において保持されている値に対応するインデックスアドレスのメモリ領域を活性化させる。ラッチ回路４４には、部分一致判定条件２２において活性化させるインデックスアドレスの値が格納される。
【００７１】
ここで、部分一致判定条件保持メモリ２３の詳細を説明する。
図８は、部分一致判定条件保持メモリ２３の記憶内容例を示す図である。
【００７２】
部分一致判定条件保持メモリ２３は、アドレス２２ａと、アドレスフィールド２２ｂと、データフィールド２２ｃとにより構成される。
【００７３】
アドレス２２ａは、部分一致判定条件保持メモリ２３におけるインデックスアドレスを示している。
【００７４】
データフィールド２２ｃは、照合データの第２のビット群（図６の例では「Ｂ」「Ｃ」「Ｄ」のビット群）と比較するための、一致条件の一部分を格納している。データフィールド２２ｃに格納されている値は、比較器４９において照合データの第２のビット群と比較される。
【００７５】
アドレスフィールド２２ｂは、データフィールド２２ｃに格納される値と、照合データの第２のビット群とが一致しない場合に、部分一致判定条件保持メモリ２３において次に参照すべきインデックスアドレスの値を格納するための領域である。例えば、図８の例では、アドレス２２ａに示される「ｋ」のレコードは、アドレスフィールド２２ｂにおいて「ｋ＋１」と示されている。そのため、アドレス２２ａにおいて「ｋ」に対応するデータフィールド２２ｃの値が、照合データの第２のビット群と一致しない場合は、アドレス２２ａにおいて「ｋ＋１」に示されるインデックスアドレスの各データが次に参照される。なお、アドレスフィールド２２ｂにおいて「０」と示されている場合は、次に参照すべき一致条件がないことを示す。
【００７６】
図６に戻り説明を続ける。
部分一致判定条件保持メモリ２３において、ＤＥＣ８４により活性化されているメモリ領域のアドレスフィールド２２ｂの値は、比較回路４７とセレクタ４６に出力される。
【００７７】
比較回路４７は、部分一致判定条件保持メモリ２３のアドレスフィールド２２ｂの値を参照し、次に比較すべき一致条件があるか、または比較すべき一致条件がないか判定する。本実施形態では、照合データと一致条件との比較において、次に比較すべき一致条件がない場合、アドレスフィールド２２ｂの値を「０」とすることとしている。そのため、比較回路４７は、部分一致判定条件保持メモリ２３のアドレスフィールド２２ｂから出力される値が「０」に一致するか判定し、「０」に一致する場合（比較回路４７においてＹＥＳ）は、他に比較すべき一致条件がないため、判定結果出力回路１２へ判定終了を示す信号を出力する。また、比較回路４７は、部分一致判定条件保持メモリ２３のアドレスフィールド２２ｂから出力される値が「０」でない場合（比較回路４７においてＮＯ）は、他に比較すべき一致条件があるため、ＡＮＤ回路４８へ信号を出力する。
【００７８】
比較器４９は、バッファ回路１１から照合データの第２のビット群（第２のビット群にかかる照合データ９２）を受け付ける。また、比較器４９は、部分一致判定条件保持メモリ２３のデータフィールド２２ｃの値（一致条件の一部分９１）を受け付ける。これら照合データと、データフィールド２２ｃの値とを比較して、一致するか否か判定する。比較器４９は、判定結果をＡＮＤ回路４８と判定結果出力回路１２とに出力する。
【００７９】
ＡＮＤ回路４８は、部分一致判定条件保持メモリ２３を用いた照合データと、一致条件との比較処理を続けるか否かを制御回路４５へ出力する。ＡＮＤ回路４８は、比較器４９による比較結果の出力と、比較回路４７の判定結果を受け付ける。ＡＮＤ回路４８は、比較器４９において、照合データと一致条件とが一致しない場合で、かつ、比較回路４７において、次に比較すべき一致条件があると判定された場合、照合データと、データフィールド２２ｃの値との比較を続けるため、制御回路４５へ信号を出力する。
【００８０】
制御回路４５は、ＡＮＤ回路４８からの出力結果を受け付けて、セレクタ４６の出力を制御する。制御回路４５は、ＡＮＤ回路４８からの信号の出力がない場合は、セレクタ４６の出力を、不一致判定回路１３から出力される、第１の一致条件保持部２１ａの条件番号２１ｇのものとする。制御回路４５は、ＡＮＤ回路４８からの信号の出力があると、部分一致判定条件保持メモリ２３のアドレスフィールド２２ｂの値を、セレクタ４６の出力とする。
【００８１】
＜２．３．４  判定結果出力回路１２＞
判定結果出力回路１２は、不一致判定回路１３および部分一致判定回路１４の判定結果を受け付けて、バッファ回路１１へ一致判定信号または不一致判定信号を出力する。判定結果出力回路１２は、ＡＮＤ回路９３と、ＮＯＴ回路９４と、ＯＲ回路９５と、ＡＮＤ回路９６とを含む。
【００８２】
ＡＮＤ回路９６は、不一致判定回路１３において不一致と判定されず、かつ、比較器４９において一致すると判定された場合に、一致判定信号を出力する。
【００８３】
ＯＲ回路９５は、ＡＮＤ回路９３とＮＯＴ回路９４との出力を受け付けて、少なくともいずれかの信号がＨＩであれば不一致判定信号を出力する。ＮＯＴ回路９４は、不一致判定回路１３において不一致と判定された場合（不一致判定回路１３の出力は信号ＬＯＷ）に、信号ＨＩを出力する。ＡＮＤ回路９３は、不一致判定回路１３において不一致と判定されず、比較回路４７において、照合データと比較すべき一致条件が他にないと判定され（比較回路４７においてＹＥＳ、照合データと一致条件との比較が終了した場合）、かつ、比較器４９において照合データと一致条件とが一致しない場合に、信号ＨＩを出力する。
【００８４】
＜３  照合データと一致条件との比較例＞
以上のように本実施形態について説明してきたが、ここで、照合データと一致条件との比較例について説明する。
【００８５】
図９は、一致条件の一例と、本実施形態における照合データと一致条件との比較例を示す図である。
【００８６】
図９に示すように、照合データを「0x4123」とする。一致条件は、それぞれ「0x0123」「0x2234」「0x3012」等とする。第１の一致条件保持部２１ａには、照合データの「Ａ」のビット群について、判定結果２１ｆにおいて一致または不一致の判定結果を格納するとともに、条件番号２１ｇにおいて、参照すべき部分一致判定条件保持メモリ２３のインデックスアドレスの値が格納されている。
【００８７】
照合データが「0x4123」であるため、照合データの各部分において、不一致判定回路１３は、不一致と判定しない。不一致判定回路１３は、第１の一致条件保持部２１ａの、インデックスアドレス「４」に該当する条件番号２１ｇの値をセレクタ４６へ出力する。
【００８８】
部分一致判定回路１４は、部分一致判定条件保持メモリ２３のアドレス２２ａおよびアドレスフィールド２２ｂとを参照し、アドレス２２ａの「ｋ」「ｋ＋１」「ｋ＋２」に示される一致条件を、比較器４９において順に照合データと比較する。比較の結果、照合データ「0x4123」は、一致条件のいずれとも一致しないと判定される。
【００８９】
このように、本実施形態によると、複数の一致条件のうち、照合データの一部のビット群と一致するものについて、照合データと一致条件との比較を行う。そのため、複数の一致条件と、照合データとがいずれも不一致の場合に、関連技術のように照合データと全ての一致条件との比較を待つ必要がない。
【００９０】
また、部分一致判定回路１４の部分一致判定条件保持メモリ２３は、ＲＡＭにより実現できる。そのため、パケットフィルタリング装置１は、ＲＡＭにおいて保持するテーブルを用いたシーケンス制御によりパケットフィルタリングを行うことができ、回路の小型化を図ることができる。本実施形態は、例えば組み込みＬＳＩに適しており、内蔵メモリを持つマイコンや、ＡＳＳＰ（Application  Specific  Standard  Product）や、ＳｏＣ（System-on-a-chip）への実装も容易である。小型化により、モバイル機器に対しても本実施形態のパケットフィルタ回路を応用することが可能となる。
【００９１】
また、ＲＡＭを用いる場合は、活性化させるアドレスが指定されるため、照合データと一致条件とを比較するために全てのメモリ領域を活性化させる場合と比較すると、パケットフィルタ回路の低消費電力化を図ることができる。
【００９２】
このように各実施形態について説明してきたが、これら実施形態を組み合わせてもよいことはいうまでもない。
【００９３】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【００９４】
１  パケットフィルタリング装置、２  ＭＰＵ、３  ＲＡＭ、４  ＲＯＭ、５  通信モジュール、１０  パケットフィルタ回路、１１  バッファ回路、１２  判定結果出力回路、１３  不一致判定回路、１４  部分一致判定回路、２１  不一致判定条件、２２  部分一致判定条件、２１ａ  第１の一致条件保持部、２１ｂ  第２の一致条件保持部２１ｂ、２１ｃ  第３の一致条件保持部２１ｃ、２１ｄ  第４の一致条件保持部２１ｄ、２２  部分一致判定条件、２３  部分一致判定条件保持メモリ、３０  第１の不一致判定部、３１  第２の不一致判定部、３２  第３の不一致判定部、３３  第４の不一致判定部、３４  ＮＯＲ回路、４０  ラッチ回路、４１  ラッチ回路、４２  ラッチ回路、４３  ラッチ回路、４４  ラッチ回路、４５  制御回路、４６  セレクタ、４７  比較回路、４８  ＡＮＤ回路、４９  比較器、５１  パケットフィルタリング装置、５２  バッファ回路、５３  一致判定回路、５４  不一致判定回路、５５  ＯＲ回路、６１  一致条件、７１  第１の一致条件保持部、７２  第２の一致条件保持部、７３  第３の一致条件保持部、７４  第４の一致条件保持部、７５  ＯＲ回路、７６  照合データ、８０  ＤＥＣ、８１  ＤＥＣ、８２  ＤＥＣ、８３  ＤＥＣ、８４  比較器、９１  一致条件の一部分、９２  照合データ、９３  ＡＮＤ回路、９４  ＮＯＴ回路、９５  ＯＲ回路、９６  ＡＮＤ回路。
【図１】
2013236245.tif 000003
【図２】
2013236245.tif 000004
【図３】
2013236245.tif 000005
【図４】
2013236245.tif 000006
【図５】
2013236245.tif 000007
【図６】
2013236245.tif 000008
【図７】
2013236245.tif 000009
【図８】
2013236245.tif 000010
【図９】
2013236245.tif 000011