TOP > 国内特許検索 > データ判定装置およびデータ判定プログラム > 明細書

明細書 :データ判定装置およびデータ判定プログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5920698号 (P5920698)
公開番号 特開2013-126058 (P2013-126058A)
登録日 平成28年4月22日(2016.4.22)
発行日 平成28年5月18日(2016.5.18)
公開日 平成25年6月24日(2013.6.24)
発明の名称または考案の名称 データ判定装置およびデータ判定プログラム
国際特許分類 H04L  12/66        (2006.01)
H04L  13/08        (2006.01)
FI H04L 12/66 B
H04L 13/08
請求項の数または発明の数 3
全頁数 30
出願番号 特願2011-273040 (P2011-273040)
出願日 平成23年12月14日(2011.12.14)
審査請求日 平成26年9月1日(2014.9.1)
特許権者または実用新案権者 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】504160781
【氏名又は名称】国立大学法人金沢大学
発明者または考案者 【氏名】三浦 直樹
【氏名】浦野 正美
【氏名】松田 吉雄
【氏名】本田 良太
個別代理人の代理人 【識別番号】100064621、【弁理士】、【氏名又は名称】山川 政樹
【識別番号】100098394、【弁理士】、【氏名又は名称】山川 茂樹
【識別番号】100153006、【弁理士】、【氏名又は名称】小池 勇三
審査官 【審査官】阿部 弘
参考文献・文献 特開2004-173148(JP,A)
特開2007-053703(JP,A)
特開2010-165102(JP,A)
三浦 直樹 他,不一致判定回路を用いた高速パケットフィルタ回路,電子情報通信学会技術研究報告,日本,社団法人電子情報通信学会,2009年 3月 4日,Vol.108 No.478,P. 101-106
調査した分野 H04L 12
H04L 13
特許請求の範囲 【請求項1】
入力された照合データが予め登録されている登録データ群中の登録データと一致するか否かを判定するデータ判定装置において、
前記登録データが格納される登録データ格納手段と、
前記登録データ格納手段における前記登録データが格納されていないアドレスを含むアドレス情報を記憶するアドレス情報記憶手段と、
前記登録データ格納手段に格納されている登録データと前記照合データとを比較し一致/不一致の判定結果を得る比較手段と、
前記登録データ格納手段に格納されている登録データを更新する際に、前記登録データ格納手段に登録すべき登録候補のデータの入力を受けて、その登録候補のデータと前記登録データ格納手段に格納されている登録データとの比較を前記比較手段によって行わせ、不一致の判定結果が得られた場合、前記アドレス記憶手段に記憶されているアドレス情報に基づいて、前記入力された登録候補のデータを登録データとして前記登録データ格納手段に書き込む手段と
前記登録データ格納手段に格納されている登録データを更新する際に、前記登録データ格納手段から削除すべき削除候補のデータの入力を受けて、その削除候補のデータと前記登録データ格納手段に格納されている登録データとの比較を前記比較手段によって行わせ、一致の判定結果が得られた場合、前記アドレス記憶手段に記憶されているアドレス情報に基づいて、前記入力された削除候補のデータと一致する登録データを前記登録データ格納手段から削除する手段と
を備えることを特徴とするデータ判定装置。
【請求項2】
請求項1に記載されたデータ判定装置において、
前記照合データの一部の情報をアドレスとして該アドレスの値を一部の情報として含んでいる登録データが前記登録データ格納手段に格納されているか否かを示す情報を格納した登録データ有無情報格納手段と、
前記登録データ有無情報格納手段に格納されている情報に基づいて前記照合データが前記登録データ格納手段に格納されている登録データと一致していないことを判定する不一致判定手段と、
前記登録データ有無情報格納手段に格納されている情報を更新する際に、前記登録データ有無情報格納手段に格納されている情報を全て削除した後、前記登録データ格納手段に格納されている登録データを読み出し、この読み出した登録データの一部の情報をアドレスとして前記登録データ有無情報格納手段にアクセスし、このアクセスした登録データ有無情報格納手段のアドレスに、当該アドレスの値を一部の情報として含んでいる登録データが前記登録データ格納手段に格納されていることを示す情報を書き込む手段と
を備えることを特徴とするデータ判定装置。
【請求項3】
請求項1又は2に記載されたデータ判定装置の各手段での処理をコンピュータで実行させるためのデータ判定プログラム
発明の詳細な説明 【技術分野】
【0001】
この発明は、入力された照合データが予め登録されている登録データ群中の登録データと一致するか否かを判定するデータ判定装置およびデータ判定プログラムに関するものである。
【背景技術】
【0002】
ネットワークに接続された通信端末には、受信したパケットのフィルタリングを行うため、パケットフィルタ回路を搭載する端末がある。このパケットフィルタ回路は、受信したパケットに含まれるIPアドレスなどの照合データと、一致条件として事前に登録されている登録データ群中の登録データとを比較し、照合データと登録データとの一致/不一致を判定し、この判定結果に基づいてパケットの廃棄や透過等の処理を行う。ネットワークの大容量化に伴い、通信端末が送受信するパケット数が増加し、パケットフィルタ回路には、多量のパケットに対して判定を行うこと、すなわち高スループット化が求められている。
【0003】
パケットフィルタ回路において、照合データと登録データとの一致/不一致を判定する方式の1つに線形探索方式(例えば、非特許文献1参照)がある。この線形探索方式は、照合データと登録データとを1つずつ照合し、照合データと登録データとが一致した場合は一致と判定し、照合データが何れの登録データとも一致しない場合は不一致と判定する。すなわち、線形探索方式は、照合データと全ての登録データとを照合した後で、不一致が判定される方式である。
【0004】
〔従来例1〕
線形探索方式を実装したパケットフィルタ回路の代表的な構成を図22に示す。このパケットフィルタ回路200は、バッファ回路201と一致判定回路202とから成る。
【0005】
バッファ回路201は、入力される判定要求信号とパケットをもとに、判定開始信号と照合データ(パケットの一部または全部からなるデータ)を、一致判定回路202に送る。一致判定回路202は、バッファ回路201からの照合データと一致条件として事前に登録されている登録データ群中の登録データとを比較して、一致の判定を行う。
【0006】
一致判定回路202は、照合データと一致する登録データを検出した場合に、その時点でバッファ回路201に一致判定信号を出力する。全ての登録データとの照合を行っても、一致する登録データを検出できなかった場合には、バッファ回路201に不一致判定信号を出力する。
【0007】
一致判定回路202からの一致判定信号/不一致判定信号はバッファ回路201に送られる。バッファ回路201は、一致判定信号が送られてくると、受信したパケットを透過し、不一致判定信号が送られてくると、受信したパケットを破棄する。
【0008】
このような動作から分かるように、線形探索方式を実装したパケットフィルタ回路は、照合データと全ての登録データとを照合した後でなければ不一致と判定することができないため、一致判定に比べて不一致判定には時間を要する。通信端末におけるフィルタリング処理では、受信したパケットが不一致と判定される場合も多く、不一致判定に時間を要することがスループットを低下させる原因となっている。
【0009】
パケットフィルタ回路において、照合データと登録データとの一致/不一致を判定する他の方式に、2分探索方式(例えば、非特許文献2参照)がある。この2分探索方式は、照合対象となる登録データを半分に絞り込んで行く方式である。この方式は、照合対象となる登録データを半分に絞り込んで行く方式であるため、照合対象となる登録データが線形探索方式に比べて減少し、一致を判定するまでの時間が短縮される。
【0010】
しかしながら、この方式も、照合対象となる全ての登録データとの照合が完了した後でなければ不一致を判定することができず、不一致判定に時間を要することになる。他にも、ハッシュ関数を用いた方式(例えば、非特許文献3参照)などもあるが、何れの方式もすべて、照合対象となる全ての登録データとの照合を完了した後で、不一致が判定される方式であるため、不一致の判定に時間を要することになる。
【0011】
そこで、例えば特許文献1や非特許文献4に、照合データと全ての登録データとの照合を完了する前に不一致を判定するようにしたパケットフィルタ回路が提案されている。このパケットフィルタ回路では、一致判定回路に加えて、不一致判定回路を用いる。
【0012】
〔従来例2〕
図23に非特許文献4に示されたパケットフィルタ回路を示す。このパケットフィルタ回路300は、バッファ回路201と、一致判定回路202と、不一致判定回路203と、ORゲート204とから成る。
【0013】
バッファ回路201は、入力される判定要求信号とパケットをもとに、判定開始信号と照合データ(パケットの一部または全部からなるデータ)を、一致判定回路202および不一致判定回路203に送る。一致判定回路202は、バッファ回路201からの照合データと一致条件として事前に登録されている登録データ群中の登録データとを比較して、一致の判定を行う。一方、不一致判定回路203は、入力された照合データと予め登録されている登録データの有無情報(後述)とを比較して、不一致の判定を行う。
【0014】
一致判定回路202は、照合データと一致する登録データを検出した場合に、その時点で一致判定信号を出力する。全ての登録データとの照合を行っても、一致する登録データを検出できなかった場合には、不一致判定信号を出力する。不一致判定回路203は、照合データと登録データの有無情報とを比較し、その照合データと一致する登録データがないと判定すると、不一致判定信号を出力する。一致判定回路202からの一致判定信号はバッファ回路201へ送られる。一致判定回路202からの不一致判定信号および不一致判定回路203からの不一致判定信号はORゲート204を介してバッファ回路201へ送られる。
【0015】
バッファ回路201は、一致判定信号が送られてくると、受信したパケットを透過し、不一致判定信号が送られてくると、受信したパケットを破棄する。そして、このパケットの処理後、バッファ回路201は、次のパケットの照合データと判定開始信号を出力し、一致判定回路202と不一致判定回路203は、そのパケットの判定処理に移行する。
【0016】
このパケットフィルタ回路300の動作を図24を用いて説明する。図24は、不一致と判定される「パケット1」と一致と判定される「パケット2」が連続して入力される場合のタイミングチャートを示している。
【0017】
先ず、バッファ回路201が「パケット1」の照合データと判定開始信号を、一致判定回路202と不一致判定回路203に出力する。一致判定回路202と不一致判定回路203は、判定開始信号を受けて、「パケット1」の判定処理を同時に開始する。不一致判定回路203は、「パケット1」の照合データと一致する登録データがないと判定すると、その時点で不一致判定信号を出力する。この不一致判定信号は、ORゲート204を介して、バッファ回路201へ与えられる。不一致判定回路203での一致する登録データがない旨の判定は短時間で行われる。
【0018】
バッファ回路201は、不一致判定信号が送られてくると、一致判定回路202が判定途中であっても、受信した「パケット1」を廃棄する。「パケット1」の処理が終了すると、バッファ回路201は、「パケット2」の照合データと判定開始信号を出力する。これにより、一致判定回路202と不一致判定回路203で、「パケット2」の判定処理が同時に開始される。一致判定回路202は、「パケット2」の照合データと一致する登録データを検出すると、その時点で一致信号を出力する。この一致信号はバッファ回路201へ与えられる。バッファ回路201は、一致信号が送られてくると、受信した「パケット2」を透過させる。
【0019】
以上の動作から分かるように、このパケットフィルタ回路300では、不一致判定回路203が一致判定回路202よりも先に不一致を判定することで、判定処理時間が短縮され、実効スループットが向上する。
【0020】
〔不一致判定回路〕
パケットフィルタ回路300において、不一致判定回路203は、短時間で不一致を判定するために、メモリを用いて照合データと予め登録されている登録データの有無情報とを一度に比較して、不一致の判定を行う。
【0021】
不一致判定回路203に用いられるメモリの構成を図25に示す。このメモリMは、登録データの値をアドレスとして「一致(登録データ有り)」の判定を記憶し、それ以外のアドレスには「不一致(登録データ無し)」の判定を記憶する。図25では、登録データが「1」,「6」,「10」,「14」,「18」という5つの値である場合が示されている。この場合、メモリMのアドレスの「1」,「6」,「10」,「14」,「18」には「一致」の判定を格納し、それ以外のアドレスには「不一致」の判定を格納する。
【0022】
このようなメモリMを用いることにより、照合時には、入力される照合データの値が読み出しアドレスとしてメモリMにアクセスされ、メモリMからは「一致」または「不一致」の判定が出力される。不一致判定回路203は、このメモリMからの出力をもとに、不一致を判定する。
【0023】
図25に示したメモリMは、照合データが取り得る値の最大値と等しい容量が必要になる。つまり、照合データと登録データのビット長がnビットである場合、メモリMは2n個の判定を記憶することが必要になる。そこで、メモリの容量を削減するために、前述した非特許文献4には、nビットの照合データと登録データをmビットずつ、複数のメモリに分割して、並列に照合処理を行うことでメモリの容量を削減する手法が開示されている。
【0024】
図26はn=16、m=4の場合の例である。図26では、各登録データの上位4ビットをメモリM1に割り当て、次の4ビットをメモリM2に、更に次の4ビットをメモリM3に、下位4ビットをメモリM4に割り当てている。例えば、16ビットの「0x1234」と「0x4567」という2つの登録データを4つのメモリに分割して記憶する場合、4ビットずつに分割された各登録データを、図25と同様にして、各メモリに記憶する。ここで、「0x」は16進数表示であることを意味する。
【0025】
「0x1234」という登録データの場合、メモリM1には上位4ビットの値である「0x1」をアドレスとして「一致」の判定を記憶する。メモリM2には次の4ビットの値である「0x2」のアドレスに、メモリM3には更に次の4ビットの値である「0x3」のアドレスに、そしてメモリM4には下位4ビットの値である「0x4」のアドレスに、「一致」の判定を記憶する。
【0026】
「0x4567」という登録データの場合も同様に、メモリM1には「0x4」のアドレスに、メモリM2には「0x5」のアドレスに、メモリM3には「0x6」のアドレスに、メモリM4には「0x7」のアドレスに、「一致」の判定を記憶する。これら以外の全てのアドレスには「不一致」の判定を記憶する。
【0027】
このように、nビットの登録データをmビットずつ、複数のメモリに分割して、「一致」/「不一致」の判定を記憶させることにより、メモリの容量を(n/m)2mに削減できる。
【0028】
不一致判定回路203のメモリを分割した構成とした場合、不一致判定時には、複数のメモリで並列に独立して照合を行い、どれか一つのメモリから不一致が出力されると照合データは不一致と判定される。例えば、図27に示すように、「0x1235」という照合データが入力された場合、メモリM1、メモリM2、メモリM3からは「一致」の判定が、メモリM4からは「不一致」の判定が出力され、照合データは不一致と判定される。
【0029】
しかし、照合データが不一致にもかかわらず不一致と判定できない場合がある。例えば、図28に示すように、「0x1237」という照合データが入力された場合、このデータは登録データではないので、不一致と判定されるべきであるが、全てのメモリM1~M4(以下、このメモリを不一致テーブルと呼ぶ)は「一致」の判定を出力するため、一致と判定される。この場合、一致判定回路202が全ての登録データとの照合を行い、最終的に不一致と判定するため、誤った判定を行うことはない。
【0030】
〔一致判定回路〕
一致判定回路202には、前述したように、照合データと登録データとを順次照合していく線形探索方式や順次半分に絞り込んでゆく2分探索方式、ハッシュ探索方式法などを実装して用いることができる。いずれの方式を用いるにせよ、一致判定回路202には、登録データを記憶させておくメモリ(以下、このメモリを条件テーブルと呼ぶ)が必要であり、この条件テーブルから登録データを効率よく読み出すことにより照合データの一致/不一致を判定する。
【先行技術文献】
【0031】

【特許文献1】特開2010-165102号公報
【0032】

【非特許文献1】David E.Taylor "Survey and Taxonomy of Packet Classification Techniques" ACM Computing Surveys,Vo1.37,No.3,September 2005,pp.238-275.
【非特許文献2】弓場、星 "木構造を用いた見出し探索の技法"情報処理、Vol.21,No1,January 1980,pp.28-49.
【非特許文献3】Yeim-Kuan Chang and Wen-Hsin Cheng "A Small IP Forwarding Table Using Hashing "Proceeding of The l8th International Conference on AINA,2004.
【非特許文献4】三浦直樹他、「不一致判定回路を用いた高速パケットフィルタ回路」、電子情報通信学会技術報告VLD2008-143, pp. 101-106, 2009年3月。
【発明の概要】
【発明が解決しようとする課題】
【0033】
しかしながら、上述した従来のパケットフィルタ回路200(図22)や300(図23)において、一致判定回路202における条件テーブルの作成には、予め各アドレスに対して書き込むべき登録データの一覧表を作成して、メモリに書き込むのが一般的である。通常、このデータ作成は、ソフトウェアで別途実行され、データが作成された後、メモリに書き込まれる。
【0034】
特に、一致判定回路202に加えて不一致判定回路203を設けたパケットフィルタ回路300では、不一致判定回路203における不一致テーブルの作成についても、一致判定回路202と同様にして、予め各アドレスに対して書き込むべきデータの一覧表を作成してメモリに書き込む必要があり、更には、登録データを変更した場合、改めて不一致テーブルへの「一致」/「不一致」の判定データや条件テーブルへの登録データを全て作成し直し、再度メモリに書き込む必要がある。
【0035】
このように、従来のパケットフィルタ回路では、別途テーブルを作成する必要があり、テーブルを作成するためのソフトウェアや事前にテーブルを作成する手間が必要であるという問題点があった。
【0036】
本発明は、このような課題を解決するためになされたもので、その目的とするところは、照合データと登録データとの一致/不一致の判定機能を利用することにより、一致/不一致を判定するためのテーブルを作成するためのソフトウェアや事前にテーブル作成する手間を不要とすることが可能なデータ判定装置およびデータ判定プログラムを提供することにある。
【課題を解決するための手段】
【0037】
このような目的を達成するために、本願の請求項1に係る発明は、入力された照合データが予め登録されている登録データ群中の登録データと一致するか否かを判定するデータ判定装置において、登録データが格納される登録データ格納手段と、登録データ格納手段における登録データが格納されていないアドレスを含むアドレス情報を記憶するアドレス情報記憶手段と、登録データ格納手段に格納されている登録データと照合データとを比較し一致/不一致の判定結果を得る比較手段と、登録データ格納手段に格納されている登録データを更新する際に、登録データ格納手段に登録すべき登録候補のデータの入力を受けて、その登録候補のデータと登録データ格納手段に格納されている登録データとの比較を比較手段によって行わせ、不一致の判定結果が得られた場合、アドレス記憶手段に記憶されているアドレス情報に基づいて、入力された登録候補のデータを登録データとして登録データ格納手段に書き込む手段と、登録データ格納手段に格納されている登録データを更新する際に、登録データ格納手段から削除すべき削除候補のデータの入力を受けて、その削除候補のデータと登録データ格納手段に格納されている登録データとの比較を比較手段によって行わせ、一致の判定結果が得られた場合、アドレス記憶手段に記憶されているアドレス情報に基づいて、入力された削除候補のデータと一致する登録データを登録データ格納手段から削除する手段とを備えることを特徴とする。
【0038】
この発明によれば、登録データ格納手段(条件テーブル)に格納されている登録データを更新する際に、登録データ格納手段に登録すべき登録候補のデータが入力されると、その登録候補のデータと登録データ格納手段に格納されている登録データとが比較手段(比較器)によって比較され、不一致の判定結果が得られると、アドレス記憶手段(レジスタ)に記憶されているアドレス情報(この場合、登録データが格納されていない空きアドレス)に基づいて、入力された登録候補のデータが登録データとして登録データ格納手段に書き込まれる。このようにして、本発明では、登録候補のデータが入力される毎に、その登録候補のデータが登録データ格納手段に格納されていなければ、次々に登録データとして登録データ格納手段の空きアドレスに書き込まれて行く。
【0040】
また、この発明によれば、登録データ格納手段(条件テーブル)に格納されている登録データを更新する際に、登録データ格納手段から削除すべき削除候補のデータが入力されると、その登録候補のデータと登録データ格納手段に格納されている登録データとが比較手段(比較器)によって比較され、一致の判定結果が得られると、アドレス記憶手段(レジスタ)に記憶されているアドレス情報(この場合、一致する登録データが格納されているアドレス)に基づいて、入力された削除候補のデータと一致する登録データが登録データ格納手段から削除される。このようにして、本発明では、削除候補のデータが入力される毎に、その削除候補のデータが登録データ格納手段に格納されていれば、次々にその削除候補のデータと一致する登録データが登録データ格納手段から削除されて行く。
【0041】
本願の請求項2に係る発明は、請求項1に係る発明において、照合データの一部の情報をアドレスとして該アドレスの値を一部の情報として含んでいる登録データが登録データ格納手段に格納されているか否かを示す情報を格納した登録データ有無情報格納手段と、登録データ有無情報格納手段に格納されている情報に基づいて照合データが登録データ格納手段に格納されている登録データと一致していないことを判定する不一致判定手段と、登録データ有無情報格納手段に格納されている情報を更新する際に、登録データ有無情報格納手段に格納されている情報を全て削除した後、登録データ格納手段に格納されている登録データを読み出し、この読み出した登録データの一部の情報をアドレスとして登録データ有無情報格納手段にアクセスし、このアクセスした登録データ有無情報格納手段のアドレスに、当該アドレスの値を一部の情報として含んでいる登録データが登録データ格納手段に格納されていることを示す情報を書き込む手段とを備えることを特徴とする。
【0042】
この発明によれば、登録データ有無情報格納手段(不一致テーブル)に格納されている情報の更新に際しては、登録データ有無情報格納手段に格納されている情報が全て削除された後、登録データ格納手段(条件テーブル)に格納されている登録データが読み出される。そして、この読み出された登録データの一部の情報をアドレスとして登録データ有無情報格納手段がアクセスされ、このアクセスした登録データ有無情報格納手段のアドレスに、当該アドレスの値を一部の情報として含んでいる登録データが登録データ格納手段に格納されていることを示す情報(「一致(登録データ有り)」)が書き込まれる。アクセスされなかったアドレスには登録データが登録データ格納手段に格納されていないことを示す情報(「不一致(登録データ無し)」)が残される。このようにして、本発明では、自動的に、登録データ有無情報格納手段のアドレスに、そのアドレスの値を一部の情報として含んでいる登録データが登録データ格納手段に格納されているか否かを示す情報が書き込まれて行く。
【0043】
本発明に係るデータ判定装置は、コンピュータによって実行されるプログラムとしても実現でき、プログラムを記録媒体に記憶することも、ネットワークを通して提供することも可能である。
【発明の効果】
【0044】
本発明によれば、登録データ格納手段に格納されている登録データを更新する際に、登録データ格納手段に登録すべき登録候補のデータの入力を受けて、その登録候補のデータと登録データ格納手段に格納されている登録データとの比較を比較手段によって行わせ、不一致の判定結果が得られた場合、アドレス記憶手段に記憶されているアドレス情報に基づいて、入力された登録候補のデータを登録データとして登録データ格納手段に書き込むようにしたので、また、登録データ格納手段に格納されている登録データを更新する際に、登録データ格納手段から削除すべき削除候補のデータの入力を受けて、その削除候補のデータと登録データ格納手段に格納されている登録データとの比較を比較手段によって行わせ、一致の判定結果が得られた場合、アドレス記憶手段に記憶されているアドレス情報に基づいて、入力された削除候補のデータと一致する登録データを登録データ格納手段から削除するようにしたので、登録候補のデータが入力される毎に、照合データと登録データとの一致/不一致の判定機能を利用して、次々に登録データ格納手段の空きアドレスに登録データとして書き込まれて行くものとなり、また、削除候補のデータが入力される毎に、照合データと登録データとの一致/不一致の判定機能を利用して、次々に削除候補のデータと一致する登録データが登録データ格納手段から削除されて行くものとなり、一致/不一致を判定するためのテーブルを作成するためのソフトウェアや事前にテーブル作成する手間を不要とすることが可能となる。
【図面の簡単な説明】
【0045】
【図1】本発明に係るデータ判定装置を含むパケットフィルタ回路の一実施の形態を示す図である。
【図2】このパケットフィルタ回路における不一致判定回路の構成を示す図である。
【図3】この不一致判定回路における不一致テーブルの構成を示す図である。
【図4】このパケットフィルタ回路における一致判定回路の構成を示す図である。
【図5】この一致判定回路における条件テーブルの構成を示す図である。
【図6】この一致判定回路における索引テーブルの構成を示す図である。
【図7】この一致判定回路におけるレジスタ群の構成を示す図である。
【図8】初期化された不一致テーブルの状態を示す図である。
【図9】初期化された索引テーブル、条件テーブル、レジスタ群の状態を示す図である。
【図10】「条件a0」を登録する場合の各テーブルの更新手順を説明する図である。
【図11】「条件b0」を登録する場合の各テーブルの更新手順を説明する図である。
【図12】「条件a1」を登録する場合の各テーブルの更新手順を説明する図である。
【図13】「条件a0」、「条件b0」、「条件a1」の登録が完了した時点の索引テーブル、条件テーブル、レジスタ群の状態を示す図である。
【図14】「条件a1」を削除する場合の各テーブルの更新手順を説明する図である。
【図15】「条件a0」を削除する場合の各テーブルの更新手順を説明する図である。
【図16】登録要求時の処理手順の流れを示すフローチャートである。
【図17】登録要求時の処理手順における分岐(I)での処理の流れを示すフローチャートである。
【図18】登録要求時の処理手順における分岐(II)での処理の流れを示すフローチャートである。
【図19】削除要求時の処理手順の流れを示すフローチャートである。
【図20】削除要求時の処理手順における分岐(III)での処理の流れを示すフローチャートである。
【図21】削除要求時の処理手順における分岐(IV)での処理の流れを示すフローチャートである。
【図22】線形探索方式を実装した従来のパケットフィルタ回路(従来例1)の代表的な構成を示す図である。
【図23】非特許文献4に示された従来のパケットフィルタ回路(従来例2)を示す図である。
【図24】従来例2のパケットフィルタ回路の動作を説明するためのタイムチャートである。
【図25】従来例2のパケットフィルタ回路における不一致判定回路に用いられるメモリの構成を示す図である。
【図26】従来例2のパケットフィルタ回路における不一致判定回路において登録データを4つのメモリに分割して記憶させるようにした例を示す図である。
【図27】「0x1235」という照合データが入力された場合の4つのメモリからの一致/不一致の判定結果の出力状況を示す図である。
【図28】「0x1237」という照合データが入力された場合の4つのメモリからの一致/不一致の判定結果の出力状況を示す図である。
【発明を実施するための形態】
【0046】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。図1はこの発明に係るデータ判定装置を含むパケットフィルタ回路の一実施の形態を示す図である。

【0047】
このパケットフィルタ回路100は、バッファ回路101と、一致判定回路102と、不一致判定回路103と、ORゲート104とから成る。バッファ回路101には、判定要求信号とパケットが入力される。一致判定回路102と不一致判定回路103には、バッファ回路101からの判定開始信号と照合データに加えて、モード選択信号が入力される。

【0048】
なお、本実施の形態の形態において、モード選択信号の設定によっては、入力される照合データは条件〔登録条件(登録候補のデータ)/削除条件(削除候補のデータ)〕と判断される。この点は後で詳述する。このパケットフィルタ回路100において、一致判定回路102と不一致判定回路103とが、本発明に係るデータ判定装置の主要な構成要素を成す。

【0049】
このパケットフィルタ回路100において、バッファ回路101は、入力される判定要求信号とパケットをもとに、判定開始信号と照合データ(パケットの一部または全部からなるデータ)を、一致判定回路102および不一致判定回路103に送る。一致判定回路102は、バッファ回路101からの照合データと一致条件として事前に登録されている登録データ群中の登録データと比較して、一致の判定を行う。一方、不一致判定回路103は、入力された照合データと予め登録されている登録データの有無情報とを比較して、不一致の判定を行う。

【0050】
一致判定回路102は、照合データと一致する登録データを検出した場合に、その時点で一致判定信号を出力する。全ての登録データとの照合を行っても、一致する登録データを検出できなかった場合には、不一致判定信号を出力する。不一致判定回路103は、照合データと登録データの有無情報とを比較し、その照合データと一致する登録データがないと判定すると、不一致判定信号を出力する。一致判定回路102からの一致判定信号はバッファ回路101へ送られる。一致判定回路102からの不一致判定信号および不一致判定回路103からの不一致判定信号はORゲート104を介してバッファ回路101へ送られる。

【0051】
バッファ回路101は、一致判定信号が送られてくると、受信したパケットを透過し、不一致判定信号が送られてくると、受信したパケットを破棄する。そして、このパケットの処理後、バッファ回路101は、次のパケットの照合データと判定開始信号を出力し、一致判定回路102と不一致判定回路103は、そのパケットの判定処理に移行する。

【0052】
〔不一致判定回路の構成〕
不一致判定回路103の構成を図2に示す。不一致判定回路103は、ビット分割/選択回路103A、不一致テーブル103B1~103B4、ANDゲート103C、処理部103D、及びインバータ103Eから成る。図2は、照合データの長さを32ビット長とし、8ビットずつ4分割にした例である。

【0053】
この実施の形態では、不一致テーブル103B(103B1~103B4)はメモリで構成される。各登録データの上位8ビットを不一致テーブル103B1に割り当て、次の8ビットを不一致テーブル103B2に、更に次の8ビットを不一致テーブル103B3に、下位8ビットを不一致テーブル103B4に割り当てている。この例では、8ビットに分割しているので、不一致テーブル103Bは256ワード×1ビットの構成をとる。

【0054】
不一致テーブル103B1のアドレスは登録データの上位8ビットの値に対応し、そのアドレスの値が登録データの対応する8ビットの値として含まれている場合、不一致テーブル103B1の対応するアドレスに「一致」の判定を書き込む。この例では「1」を割り当てる。登録データに含まれていなければ、「不一致」の判定を書き込む。この例では「0」を割り当てる。不一致テーブル103B2~103B4についても同様である。

【0055】
不一致テーブル103B1の構成例を図3に示す。図3では、「登録条件1(登録データ1)」の上位8ビットの値は「1」であるので、不一致テーブル103B1のアドレス「1」に「1」(一致)が格納される。「登録条件2(登録データ2)」では、上位8ビットの値が「10」なので、不一致テーブル103B1のアドレス「10」に「1」(一致)が格納される。なお、「登録条件1(登録データ1)」および「登録条件2(登録データ2)」中の数字は、8ビット列の値を10進数で表したものである。

【0056】
〔不一致判定回路の基本動作〕
次に、不一致回路103の基本動作を説明する。バッファ回路101からの照合データは、ビット分割/選択回路103Aに送られる。バッファ回路101からの判定開始信号は処理部103Dに送られる。

【0057】
照合データが入力されると、ビット分割/選択回路103Aは、入力された照合データから各8ビットを選択して、上位8ビットを不一致テーブル103B1に、次の8ビットを不一致テーブル103B2へというように、各不一致テーブル103Bへ出力する。

【0058】
各不一致テーブル103Bでは、ビット分割/選択回路103Aから送られた各8ビットの値がアドレスとして入力され、そのアドレスに格納されているデータが読み出される。この各不一致テーブル103Bからの読出しは、判定開始信号を受けた処理部103Dの指示に従って行われる。

【0059】
この時、4つの不一致テーブル103Bから読み出されたデータに、一つでも「0」即ち「不一致」の判定があれば、ANDゲート103Cは不一致の判定である「0」を出力する。読み出されたデータが全て「1」、つまり全てが「一致」の判定であった場合には、ANDゲート103Cは一致の判定である「1」を出力する。このANDゲート103Cからの一致/不一致の判定は、インバータ103Eによって反転されて、ORゲート104(図1)を通過し、バッファ回路101へ送られる。

【0060】
この例では、上位8ビット、次の8ビットと言うように順次分割選択しているが、ビットの順序や各ビットの選択はこれに限るものではない。必要に応じて、任意の8ビットを選択的に抽出して各不一致テーブル103Bに出力するように構成することは容易である。また8ビットである必要も無い。

【0061】
〔一致判定回路の構成〕
次に、一致判定回路102の構成を図4に示す。一致判定回路102は、索引テーブル102A、条件テーブル102B、レジスタ群102C、比較器102D、セレクタ102E1~102E3、及び処理部102F等から成る。索引テーブル102A、条件テーブル102Bは、本実施の形態ではメモリで構成される。また、この例において、照合データは32ビット長で、条件テーブル102Bには登録データを最大512個まで登録できるものとしている。

【0062】
条件テーブル102Bの構成を図5に示す。条件テーブル102Bは判定するための一致条件を登録データ(登録条件)として格納しておくテーブルである、この実施の形態では、登録データを最大512個登録できるものとしている。従って、条件テーブル102Bのワード数は512であり、このワードを指定するメモリのアドレスは9ビット長になる。

【0063】
まず、512個の登録データを全32ビットの内の上位8ビットの値で分類する。上位8ビットの値が共通である登録データを1つのグループとみなす。例えば、上位8ビットの値が「a」の登録データが2つあるとすると、これを「条件a0」,「条件a1」で表す。以下では、これらを、簡単に「a0」,「a1」と表すこともある。「条件b0」,「条件c0」等も同様である。

【0064】
条件テーブル102Bのデータは、4つのフィールドに分割される。第1のフィールドは1ビット幅で、そのワードが登録データを格納しているかどうかを表すビットである。これをVB(Valid Bit)と呼び、登録データが格納されているとき「1」、格納されていないとき「0」を割り当てる。

【0065】
第2のフィールドをFLT(条件)フィールドと呼び、登録データを格納する。この実施の形態では、照合データを32ビットとしているので、32ビットがこのフィールドに割り当てられる。第3のフィールドには1ビットを割り当て、同じグループに属する登録データが、以降のアドレスに格納されているかどうかを表す。このビットをNF(Next Flag)フィールドと呼び、格納されていればNFフィールドに「1」を格納し、第4のフィールドであるNA(Next Address)フィールドに、次の登録データが格納されているアドレスを格納する。他のアドレスに同じグループに属する登録データが格納されていなければ、NFフィールドには「0」を格納し、NAフィールドには「0」を格納する。従って、NAフィールドは1ビット幅、NAフィールドは9ビット幅である。

【0066】
図5に示した条件テーブル102Bの内容について具体的に説明する。まず、第1行(条件テーブル102Bの0番地)はVB=1となっており、このアドレスには登録データが格納されていることを表す。この場合、その登録データはFLTフィールドに格納されており、「条件a0」であることが分かる。次のNFフィールドは「1」なので、上位8ビットが「a」である登録データが、まだこの条件テーブル102Bに格納されていることを示している。NAフィールドが「2」となっているので、次の登録データは条件テーブル102Bの2番地のところに格納されていることになる。そこで、2番地を見ると、VB=1となっており、FLTフィールドには「条件a1」が格納されていることが分かる。第3のフィールドである、NFフィールドは「0」となっており、このグループに属する登録データはこれ以上存在しないことが分かる。この場合、NAフィールドには「0」を割り当てる。「条件b」、「条件c」についても同様である。

【0067】
次に、アドレスの510番地について説明する。VB=0であるので、このアドレスには登録データは格納されていないことを表す。この場合、NFフィールドには「1」を設定し、NAフィールドには、以降のワードで登録データが格納されていない最初の空きアドレスが格納される。ここでは、「511」が格納されているので、次の空きアドレスは511番地であることを示す。FLTフィールドの値は任意である。

【0068】
次に、索引テーブル102Aの構成を説明する。図6にその構成を示す。索引テーブル102Aは、照合データの上位8ビットの値をアドレスとするメモリである。従って256ワードからなる。各ワードは、1ビット幅のMF(Match Flag)フィールドと9ビット幅のIA(Index Address)フィールドからなる。索引テーブル102Aにおいて、例えばそのアドレス「a」には、上位8ビットの値が「a」である登録データが、条件テーブル102Bに格納されているかどうかの情報、およびそれに付随する情報が格納される。

【0069】
索引テーブル102Aにおいて、アドレス「a」のフィールドMFの値は、上位8ビットの値が「a」である登録データが、条件テーブル102Bに存在しているか否かを示している。すなわち、アドレス「a」のフィールドMFの値が「1」であれば、上位8ビットの値が「a」である登録データが、条件テーブル102Bに存在していることを意味している。アドレス「a」のIAフィールドには、上位8ビットの値が「a」である登録データのうち、最初に比較される登録データが格納されている条件テーブル102Bのアドレスが格納される。上位8ビットの値が「a」である登録データが条件テーブル102Bに存在していなければ、索引テーブル102Aの「a」番地には、MF=0,IA=0を設定する。

【0070】
例えば、索引テーブル102Aのアドレス「0」をみるとMF=1になっているので、上位8ビットの値が「0」である登録データが条件テーブル102Bに存在していることを示している。IAフィールドの値は「1」となっているので、最初に比較される登録データは、条件テーブル102Bの1番地に格納されていることになる。

【0071】
尚、索引テーブル102AのMFフィールドは不一致判定回路103の不一致テーブル103B1と同じである。従って、不一致判定回路103の不一致テーブル103B1は省略することもできる。或は、逆に索引テーブル102AのMFフィールドは削除し、不一致判定回路103の不一致テーブル103B1で代用することも可能である。

【0072】
〔一致判定回路の基本動作〕
次に、一致判定回路102の基本動作を説明する。バッファ回路101からの照合データは、その全ビットが比較器102Dに、上位8ビットが索引テーブル102Aに送られる。バッファ回路101からの判定開始信号は処理部102Fに送られる。以下の処理動作は、判定開始信号を受けた処理部102Fの指示に従って行われる。

【0073】
今、照合データの上位8ビットの値が「a」であったとする。この場合、まず、図6に示す索引テーブル102Aの「a」番地がアクセスされ、データが読み出される。この例において、読み出されたデータのうちMFフィールドの値は「1」であるので、上位8ビットの値が「a」である登録データが条件テーブル102Bに存在していることが分かり、読み出されたデータのうちIAフィールドの値「0」が条件テーブル102Bに出力される。

【0074】
図5の条件テーブル102Bでは、索引テーブル102Aから出力されたIAフィールドの値「0」が、今度は条件テーブル102Aのアドレス「0」として使用され、0番地のデータが読み出される。このとき、VB=1であるから、この登録データは有効であり、FLTフィールドのデータ、つまり登録データとして格納されている「条件a0」が比較器102Dに送られる。これにより、比較器102Dは、バッファ回路101からの照合データと「条件a0」とを比較し、一致/不一致を判定する。一致と判定すれば、判定処理は終了する。

【0075】
不一致と判定された場合は、条件テーブル102Bで読み出された0番地のNFフィールドの値を参照する。図5では、NF=1であるので、上位8ビットの値が「a」である登録データがまだ存在することが分かり、その登録データが格納されている条件テーブル102Bのアドレス「2(=NA)」を、自分自身である条件テーブル102Bのアドレスとして出力させる。これにより、条件テーブル102Bの2番地のFLTフィールドから「条件a1」が読み出され、比較器102Dに送られる。比較器102Dは、バッファ回路101からの照合データと「条件a1」とを比較し、一致/不一致を判定する。一致と判定すれば、判定処理は終了する。

【0076】
不一致と判定された場合は、条件テーブル102Bの2番地のNFフィールドのデータを参照する。図5ではNF=0となっており、上位8ビットの値が「a」である登録データは他に存在しないと判定され、判定処理が終了する。判定処理が終了すると、次のパケットの処理に移行する。

【0077】
〔各種テーブルの自動更新〕
次に、この一致判定回路102、不一致判定回路103を有したパケットフィルタ回路100で、本実施の形態の特徴的な機能である不一致テーブル103B、索引テーブル102A、条件テーブル102Bの自動更新機能について説明する。

【0078】
この自動更新機能は、パケットフィルタ回路100の照合データと登録データとの一致/不一致の判定機能を利用して、不一致テーブル103B、索引テーブル102A、条件テーブル102Bを自動的に生成或は削除をする機能である。図1におけるモード選択信号、図4におけるレジスタ群102Cは、この自動更新機能を実現するために設けられたものである。

【0079】
レジスタ群102Cの構成を図7に示す。レジスタ群102Cは、WADRレジスタ102C1、tmpレジスタ102C2、MCDレジスタ102C3、CADRレジスタ102C4、BADRレジスタ102C5から成る。WADRレジスタ102C1、tmpレジスタ102C2、MCDレジスタ102C3は1ビット幅のNFフィールド、9ビット幅のNAフィールドから成る。CADRレジスタ102C4、BADRレジスタ102C5は9ビット幅のNAフィールドのみから成る。

【0080】
〔初期化モード〕
まず、初期化モードについて説明する。このモードは、不一致テーブル103B、索引テーブル102A、条件テーブル102B、レジスタ群102Cを初期化するものである。モード選択信号を初期化モードに設定し、クロックを入力するだけで自動的に初期化が行われる。この初期化はカウンタ等の小規模ハードウエアで実現できる。

【0081】
図2に示した不一致判定回路103では、モード選択信号に従う処理動作を行わせるハードウェア構成を、処理部103Dに設けている。また、図4に示した一致判定回路102では、モード選択信号に従う処理動作を行わせるハードウェア構成を、処理部102Fに設けている。

【0082】
図8に初期化された不一致テーブル103B1~103B4の状態を示す。処理部103Dは、モード選択信号が初期化モードとして入力されると、不一致テーブル103B1~103B4の全てのアドレスに対して格納データを「0」すなわち「不一致」に設定する。

【0083】
図9(a),(b),(c)に初期化された索引テーブル102A、条件テーブル102B、レジスタ群102Cの状態を示す。処理部102Fは、モード選択信号が初期化モモードとして入力されると、索引テーブル102A、条件テーブル102B、レジスタ群102Cを初期化する。

【0084】
この初期化によって、索引テーブル102Aでは、全てのアドレスに対して「0」が格納される。条件テーブル102Bでは、全てのアドレスに対して、VBフィールドとFLTフィールドには「0」が設定される。NFフィールドはアドレス「511」に対してのみ「0」が設定され、それ以外のアドレスでは「1」が設定される。NAフィールドはアドレス「511」に対してのみ「0」が設定され、それ以外のアドレスにはそのアドレスより1大きい値が設定される。レジスタ群102Cでは、WADRレジスタ102C1のNFフィールドに「1」が設定され、それ以外には全て「0」が設定される。

【0085】
〔登録モード〕
次に、条件を登録する動作モードである登録モードについて説明する。モード選択信号を登録モードに設定し、順次、登録させたい条件(登録候補のデータ)を含むパケットをパケットフィルタ回路100に入力する。これにより、既に述べた一致判定回路102での一致/不一致の判定処理の動作に従って、入力された登録候補のデータが順次条件テーブル102Bに自動的に格納され、同時に付随するアドレス等が必要に応じて各テーブルに格納される。不一致判定回路103でも、入力された登録候補のデータについて、登録データの有無を示す情報が不一致テーブル103B1~103B4に格納される。以下、この登録モードとした場合の具体的な動作について説明する。

【0086】
先ず、各テーブルが図8、図9のように初期化された状態で、最初の「条件a0」を登録する場合を説明する。登録候補のデータである「条件a0」を含むパケットがパケットフィルタ回路100に入力されると、バッファ回路101を経由して、「条件a0」が不一致判定回路103、一致判定回路102に入力される。最初の登録候補のデータであるから、不一致判定回路103、一致判定回路102は判定動作に従って、ともに不一致と判定する。一致判定回路102が不一致と判定した時点で、すなわち比較器102Dが不一致と判定した時点で、各種テーブルの更新が開始される。この登録モードでは不一致判定回路103の判定結果は無視される。

【0087】
以下、図10を参照して、一致判定回路102の動作および各テーブルの更新手順を詳細に説明する。以下の(1)、(2)等の順序は図10中のそれに対応する。また、この動作はモード選択信号(登録モード)を受けた処理部102Fの指示に従って行われる。

【0088】
(1)「条件a0」は上位8ビットの値が「a」であるから、索引テーブル102Aの「a」番地がアクセスされる(図16:ステップS101)。この場合、「a」番地のMFフィールドは「0」なので、不一致と判定される(ステップS102のYES)。これにより、分岐(I)へ処理が移る(ステップS103)。分岐(I)のフローチャートを図17に示す。分岐(I)の処理では、レジスタ群102CのWADRレジスタ102C1のNAフィールドの値「0」が条件テーブル102Bに送られ、条件テーブル102Bの0番地のデータが読み出される(ステップS101)。

【0089】
(2)条件テーブル102Bから読み出されたデータのうち、NF,NAフィールドの値をレジスタ群102Cのtmpレジスタ102C2に保存する(ステップS102)。従って、tmpレジスタ102C2の値(NF,NA)は(0,0)から(1,1)に更新される。

【0090】
(3)次に、レジスタ群102CのWADRレジスタ102C1のNF,NAフィールドの値を、それぞれ索引テーブル102Aの「a」番地のMFフィールド、IAフィールドにコピーする(ステップS203)。これにより、索引テーブル102Aの「a」番地の値(MF,IA)は(0,0)⇒(1、0)と更新される。

【0091】
(4)レジスタ群102CのWADRレジスタ102C1のNAフィールドには「0」即ち0番地が記憶されているので、この値をもとに条件テーブル102Bの0番地をアクセスし、各フィールド(VB,FLT,NF,NA)の値を(0,0,1,1)から(1、条件a0,0,0)と更新する(ステップS204)。これは、条件テーブル102Bの0番地は有効であり、登録データとして「条件a0」が格納されていることを表している。上位8ビットの値が「a」である条件は、まだ存在していないので、NF=0、NA=0と設定される。

【0092】
(5)最後に、tmpレジスタ102C2のNF,NAフィールドの値をWADRレジスタ102C1のNF,NAフィールドにコピーする(ステップS205)。これにより、WADRレジスタ102C1の値は(NF,NA)=(1,1)となり、次の登録に備えられる。この場合、次の登録時には、WADRレジスタ102C1のNAフィールドの値をアドレスとし、このアドレスで示される条件テーブル102Bの1番地に登録データが書き込まれることになる。

【0093】
以上の手順から、WADRレジスタ102C1のデータは、条件テーブル102Bにおいて、まだ登録データが書き込まれていない最小のアドレス、つまり空きアドレスの内最も小さいアドレスを意味していることが分かる。登録候補のデータを登録するときにはこのアドレスに書き込むことになる。初期化により、WADRレジスタ102C1のNAフィールドは「0」としているので、最初の登録データは0番地に格納されるように設定されていたことになる。従って、この例では、最初の「条件a0」が条件テーブル102Bの0番地に格納された訳である。また、WADRレジスタ102C1のNAフィールドの値を、索引テーブル102Aの「a」番地のIAフィールドにコピーすればよいことになる。

【0094】
一方、不一致判定回路103では、ビット分割/選択回路103Aによって「条件a0」の各8ビットの値をアドレスとして、不一致テーブル103B1~103B4のアドレスにデータ「1」が書き込まれる。これで、不一致テーブル103B1~103B4の更新は完了する。この動作はモード選択信号(登録モード)を受けた処理部103Dの指示に従って行われる。新たな条件を登録するときにも、同じ動作をさせる。既に「1」が書かれていても、「1」を書き込むことになるが、なんら問題がないことは当然である。従って、以下では不一致テーブル103Bの更新については説明を省略する。

【0095】
次に、図11を参照して、「条件b0」を登録する場合を説明する。この例では、説明の都合上、b=1とする。これは「条件a0」の登録と基本的には同じである。従って、図16に示したステップS102のYESに応じて、分岐(I)へ移り(ステップS103)、図17に示した分岐(I)の処理が行われることになる。

【0096】
(1)「条件b0」は上位8ビットの値が「1」であるから、索引テーブル102Aの1番地がアクセスされる(図16:ステップS101)。この場合、1番地のMFフィールドはMF=0なので、不一致と判定される(ステップS102のYES)。これにより、分岐(I)へ処理が移る(ステップS103)。分岐(I)の処理(図17)では、レジスタ群102CのWADRレジスタ102C1のNAフィールドの値「1」が条件テーブル102Bに送られ、条件テーブル102Bの1番地のデータが読み出される(ステップS101)。

【0097】
(2)条件テーブル102Bから読み出されたデータのうち、NF,NAフィールドの値をレジスタ群102Cのtmpレジスタ102C2に保存する。従って、tmpレジスタ102C2の値(NF,NA)は(1,1)から(1,2)に更新される。

【0098】
(3)次に、WADRレジスタ102C1のNF,NAフィールドの値を、それぞれ索引テーブル102Aの1番地のMF,IAフィールドにコピーする(ステップS203)。これにより、索引テーブル102Aの1番地の値(MF,IA)は(0,0)⇒(1、1)と更新される。

【0099】
(4)WADRレジスタ102C1のNAフィールドには「1」即ち1番地が記憶されているので、この値をもとに条件テーブル102Bの1番地をアクセスし、各フィールド(VB,FLT,NF,NA)の値を(0,0,1,2)から(1、条件b0,0,0)と更新する(ステップS204)。

【0100】
(5)最後に、tmpレジスタ102C2のNF,NAフィールドの値をWADRレジスタ102C1のNF,NAフィールドにコピーする(ステップS205)。これにより、WADRレジスタ102C1の値は(NF,NA)=(1,2)となり、次の登録に備えられる。この場合、次の登録時には、WADRレジスタ102C1のNAフィールドの値をアドレスとし、このアドレスで示される条件テーブル102Bの2番地に登録データが書き込まれることになる。

【0101】
次に、登録モードの最後として、上位8ビットの値が「a」で、他のビットが異なる「条件a1」を登録する場合について説明する。

【0102】
この場合、上位8ビットの値が「a」なので、索引テーブル102Aの「a」番地をアクセスする。索引テーブル102Aの「a」番地のMFフィールドの値は「1」なので、一致と判定される。これにより、索引テーブル102AのIAフィールドの値「0」をもとに、条件テーブル102Bの0番地がアクセスされ、0番地から読み出された「条件a0」が比較器102Dに送られる。

【0103】
比較器102Dには「条件a1」が入力されている。「条件a0」と「条件a1」は異なっているとしているので、比較器102Dは不一致と判定する。この場合、NF=0なので、上位8ビットの値が「a」である登録データは、これが最後であることを示している。この時点で、「条件a1」は登録されるべきデータと判断され、各テーブルの更新が開始される。もし、「条件a1」が「条件a0」が同じであれば、比較器102Dで一致と判定され、この時点で処理は終了する。

【0104】
以下、この「条件a1」を登録する手順を、「条件a0」と「条件b0」が登録された時点のテーブルを出発点として、図12を参照して詳細に説明する。

【0105】
(1)「条件a1」は上位8ビットの値が「a」であるから、索引テーブル102Aの「a」番地がアクセスされる(図16:ステップS101)。この場合、「a」番地のMFフィールドはMF=1なので(ステップS103のNO)、一致と判定される。これにより、「a」番地のIAフィールドの値「0」をアドレスとして(ステップS104)、条件テーブル102Bの0番地のデータがリードされる(ステップS105)。そして、リードされたデータの内、FLTフィールドのデータである「条件a0」が比較器102Dに送られ、入力されている「条件a1」と比較される(ステップS106)。この場合、比較器102Dは、不一致と判定する(ステップS106のNO)。

【0106】
(2)この時、読み出された条件テーブル102Bの「a」番地のNFフィールドの値は「0」なので(ステップS107のYES)、上位8ビットの値が「a」である登録データはこれが最後であることが分かる。この時点で、判定が終了し、「条件a1」が登録すべきデータであると判断される。これにより、分岐(II)へ処理が移る(ステップS108)。分岐(II)のフローチャートを図18に示す。分岐(II)の処理では、不一致と判定された最後の登録データ、この場合「条件a0」が格納されていた条件テーブル102Bのアドレス「0」をCADRレジスタ102C4に保存する(ステップS301)。

【0107】
(3)「条件a1」を格納すべき空きアドレスは、WADRレジスタ102C1のNAフィールドに格納されているので、この値「2」をもとに、条件テーブル102Bの2番地のデータを読み出し(ステップS302)、そのデータのうちNF,NAフィールドの値をtmpレジスタ102C2に保存する(ステップS303)。

【0108】
(4)同じくWADRレジスタ102C1のNAフィールドの値をもとに、条件テーブル102Bの2番地にアクセスし、各フィールド(VB,FLT,NF,NA)の値を(0,0,1,3)から(1、条件a1,0,0)と更新する(ステップS304)。この場合、索引テーブル102Aの書き換えは必要ない。

【0109】
(5)続いて、条件テーブル102Bで「条件a0」が格納されているところのNAフィールドの値を、「条件a1」が格納されているアドレスに変更する。この場合、「条件a0」を格納しているアドレスは、CADRレジスタ102C4に保存されているので、この値「0」を基に、条件テーブル102Bの0番地をアクセスし、WADRレジスタ102C1のNF,NAフィールドの値を、条件テーブル102BのNFフィールド,NAフィールドにコピーする(ステップS305)。

【0110】
(6)最後に、tmpレジスタ102C2のNFフィールド,NAフィールドの値をWADRレジスタ102C1のNFフィールド,NAフィールドにコピーし、次の空きアドレスとする(ステップS306)。これで、「条件a1」の登録が完了する。

【0111】
図13(a),(b),(c)に「条件a0」、「条件b0」、「条件a1」の登録が完了した時点の索引テーブル102A、条件テーブル102B、レジスタ群102Cの状態を示す。

【0112】
〔削除モード〕
次に、登録された条件を削除する動作モードである削除モードについて説明する。モード選択信号を削除モードに設定するとともに、削除したい条件(削除候補のデータ)を含むパケットをパケットフィルタ回路100に入力する。入力された削除候補のデータは既に登録されているはずなので、パケットフィルタ回路100は一致と判定する。この判定結果をもとに、各種テーブルを更新する。

【0113】
例えば、図13の状態において、「条件a1」を削除するものとする。「条件a1」はバッファ回路101を経由して不一致判定回路103、一致判定回路102へ送られる。このモードにおいても不一致判定回路103の判定結果は考慮しない。この場合、一致判定回路102の索引テーブル102Aの「a」番地がアクセスされる。索引テーブル102Aの「a」番地のMFフィールドの値は「1」なので、一致と判定され、IAフィールドの値「0」を用いて、条件テーブル102Bの0番地がアクセスされる。0番地に格納されている「条件a0」が読み出され、入力されている「条件a1」と比較器102Dにおいて比較され、不一致と判定される。

【0114】
このとき、0番地のNFフィールドの値は「1」であるので、上位8ビットの値が「a」である登録データがまだ存在する。条件テーブル102Bの0番地のNAフィールドの値を参照すると、NA=2なので、次に条件テーブル102Bの2番地がアクセスされる。これにより、2番地に格納されている「条件a1」が読み出され、入力されている「条件a1」と比較され、一致と判定される。一致と判定された時点で、この条件を削除することが決定される。この一致判定結果をもとに、索引テーブル102A、条件テーブル102Bを更新する。

【0115】
この場合は、上位8ビットの値が「a」である「条件a0」が残っているので、索引テーブル102Aは書き換える必要はない。条件テーブル102Bでは、「条件a1」が格納されていたアドレスを空きアドレスとして、最終的にWADRレジスタ102C1に格納し、「条件a1」が格納されていたアドレスのNF,NAフィールドの値を、「条件a0」が格納されている番地のNF,NAフィールドにコピーすれば良い。付随して、適宜、他のフィールドのデータも書き換える。以下、この削除モードとした場合の具体的な動作について説明する。

【0116】
〔条件a1の削除〕
以下、「条件a1」を削除する場合の手順を、図13の状態を出発点とした図14を参照して詳細に説明する。ここでも、不一致判定回路103の判定結果は無視する。また、この実施の形態では、不一致判定回路103の不一致テーブル103Bは更新されないので、不一致判定回路103の動作については説明を省略し、一致判定回路102の動作および各テーブルの更新手順を説明する。この動作はモード選択信号(削除モード)を受けた処理部102Fの指示に従って行われる。

【0117】
(1)「条件a1」はバッファ回路101を経由して一致判定回路102へ送られる。一致判定回路102の索引テーブル102Aの「a」番地のデータがリードされる(図19:ステップS401)。この場合、「a」番地のMFフィールドの値は「1」なので、一致と判定される(ステップS402のNO)。これにより、「a」番地のIAフィールドの値をアドレスとして(ステップS403)、条件テーブル102Bの0番地のデータがリードされる(ステップS404)。このときのアドレス「0」はCADRレジスタ102C4に保存される(ステップS403)。そして、リードされたデータの内、FLTフィールドのデータである「条件a0」が比較器102Dに送られ、入力されている「条件a1」と比較される(ステップS405)。この場合、比較器102Dは、不一致と判定する(ステップS405のNO)。

【0118】
(2)この時、条件テーブル102Bの0番地のNFフィールドの値は「1」なので(ステップS406のNO)、上位8ビットの値が「a」である登録データがまだ他に存在する。このため、0番地のNAフィールドの値「2」を参照して、次に条件テーブル102Bの2番地のデータがリードされる(ステップS407)。そして、リードされたデータの内、FLTフィールドのデータである「条件a1」が比較器102Dに送られ、入力されている「条件a1」と比較される(ステップS408)。この場合、比較器102Dは、一致と判定する(ステップS408のYES)。

【0119】
(3)一致と判定されたアドレスである「2」はCADRレジスタ102C4のNAフィールドに保存される(ステップS412)。同時に、CADRレジスタ102C4のNAフィールドの直前の値、即ち、一つ前に判定された登録データが格納されていた条件テーブル102Bのアドレス「0」は、BADRレジスタ102C5に移される(ステップS413)。

【0120】
(4)また、一致と判定された「条件a1」が格納されていた条件テーブル102Bの2番地のNF,NAフィールドの値をMCDレジスタ102C3に保存する(ステップS414)。そして、分岐(IV)の処理へ移る(ステップS415)。分岐(IV)の処理のフローチャートを図21に示す。

【0121】
(5)分岐(IV)の処理では、次に、CADRレジスタ102C4に保存されている一致と判定された「条件a1」が格納されていたアドレス「2」を用いて、条件テーブル102Bの2番地をアクセスし、この2番地のNF,NAフィールドに、WADRレジスタ102C1のNF,NAフィールドの値をコピーする。同時にVBフィールドの値を「1」→「0」,FLTフィールドの値を「条件a1」→「0」と書き換える(ステップS601)。これで、条件テーブル102Bの2番地は空きアドレスとなり、2番地の次の空きアドレスである3番地が設定されたことになる。

【0122】
(6)続いて、BADRレジスタ102C5に蓄えられているデータ「0」、即ち一つ前に判定を行った条件テーブル102Bのアドレスをもとに、条件テーブル102Bの0番地をアクセスし、0番地のNF,NAフィールドにMCDレジスタ102C3に保存されているNF,NAフィールドの値をコピーする(ステップS602)。

【0123】
続いて、tmpレジスタ102C2のNFフィールドの値を「1」に更新し、NAフィールドにCADRレジスタ102C4のNAフィールドの値をコピーする(ステップS603)。これにより、削除された「条件a1」が格納されていた番地のNF,NAフィールドの値を、「条件a0」が格納されている番地のNF,NAフィールドに移したことになる。

【0124】
(7)最後に、tmpレジスタ102C2のNF,NAフィールドの値をWADRレジスタ102C1のNF,NAフィールドにコピーして(ステップS604)、削除が完了する。WADRレジスタ102C1には、削除された登録データが格納されていた条件テーブル102Bのアドレスが保存され、次の空きアドレスとして使用される。

【0125】
〔条件a0の削除〕
「条件a1」を削除する場合には、索引テーブル102Aを変更する必要は無かった。しかし、図13の状態で、最初に比較される「条件a0」を削除する場合は、索引テーブル102Aも変更しなければならない。この場合も、一致判定回路102の判定結果をもとに、各テーブルを更新することができる。

【0126】
「条件a0」を削除する場合は、「条件a0」が格納されている条件テーブル102BのアドレスのNF,NAフィールドの値を索引テーブル102AのMF,IAフィールドに設定し、「条件a0」が格納されている条件テーブル102BのアドレスのNF,NAフィールドに現在の空きアドレス(WADRレジスタ102C1に格納されているアドレス)を移し、「条件a0」が格納されているアドレスをWADRレジスタ102C1に格納すればよい。

【0127】
以下、図15を参照して、「条件a0」の削除の具体的な手順を説明する。ここでも、「条件a0」、「条件a1」、「条件b0」が登録されている状態(図13)を出発点とする。

【0128】
(1)「条件a0」はバッファ回路101を経由して一致判定回路102へ送られる。一致判定回路102の索引テーブル102Aの「a」番地のデータがリードされる(図19:ステップS401)。この場合、「a」番地のMFフィールドの値は「1」なので、一致と判定される(ステップS402のNO)。これにより、「a」番地のIAフィールドの値をアドレスとして(ステップS403)、条件テーブル102Bの0番地のデータがリードされる(ステップS404)。このときのアドレス「0」はCADRレジスタ102C4に保存される(ステップS403)。

【0129】
そして、リードされたデータの内、FLTフィールドのデータである「条件a0」が比較器102Dに送られ、入力されている「条件a0」と比較される(ステップS405)。この場合、比較器102Dは、一致と判定する(ステップS405のYES)。そして、一致と判定された条件テーブル102Bの0番地のNF,NAフィールドの値をMCDレジスタ102C3のNF,NAフィールドに保存し(ステップS410)、分岐(III)の処理へ移行する(ステップS411)。分岐(III)の処理のフローチャートを図20に示す。

【0130】
(2)分岐(III)の処理では、CADRレジスタ102C4のNAフィールドに保存されている一致と判定された条件のアドレス「0」を用いて、条件テーブル102Bの0番地をアクセスし、WADRレジスタ102C1のNF,NAフィールドの値(現在の空きアドレス)を、0番地のNF,NAフィールドにコピーする。また、VBフィールドの値を「1」→「0」,FLTフィールドの値を「条件a0」→「0」と書き換える(ステップS501)。この動作により、条件テーブル102Bの0番地は空きアドレス、0番地の次の空きアドレスは3番地と設定されたことになる。

【0131】
(3)同時に、CADRレジスタ102C4のNAフィールドに保存されている、一致と判定された登録データが格納されていた条件テーブル102Bのアドレス「0」を、tmpレジスタ102C2のNAフィールドにコピーする。同時に、tmpレジスタ102C2のNFフィールドの値を1に設定する(ステップS502)。

【0132】
(4)ついで、入力された登録データの上位8ビットの値である「a」を用いて、索引テーブル102Aの「a」番地をアクセスし、MCDレジスタ102C3のNF,NAフィールドに保存されているデータ、つまり削除された「条件a0」の次の「条件a1」が格納されている条件テーブル102Bのアドレスを、索引テーブル102AのMF,IAフィールドにコピーする(ステップS503)。

【0133】
(5)最後に、tmpレジスタ102C2のNF,NAフィールド値をWADRレジスタ102C1のNF,NAフィールドにコピーして(ステップS504)、「条件a0」の削除が完了する。WADRレジスタ102C1には、今削除された「条件a0」が格納されていた、条件テーブル102Bのアドレスである0番地が、格納されたことになる。次に、登録候補のデータを登録する場合は、条件テーブル102Bの0番地にそのデータが登録データとして格納されることになる。

【0134】
〔リフレッシュモード〕
次に、リフレッシュモードについて説明する。上述した削除モードでは、不一致判定回路103の不一致テーブル103Bは更新されない。そのため、本来不一致であるはずのアドレスに、「一致」が設定されたまま残っている可能性がある。この状態の不一致テーブル103Bで通常の動作をさせると、本来不一致のパケットを一致と判定してしまうことになる。不一致判定回路103で一致と判定した場合には、最終的に一致判定回路102で判定されるため、判定結果に誤りは生じない。しかし、登録データの削除が積み重なると、一致判定回路102で最終判定されるパケットが増え、スループットが低下する可能性がある。それを防ぐため、条件テーブル102Bのデータをもとに不一致テーブル103Bの更新を行う。

【0135】
この動作は、モード選択信号をリフレッシュモードに設定することにより、このモード選択信号(リフレッシュモード)を受けた処理部102Fや103Dの指示に従って行われる。リフレッシュモードに設定されると、不一致テーブル103Bが図8のように初期化される。他のテーブルは変更されない。ついで、条件テーブル102Bの各番地のデータが順次読み出され、FLTフィールドのデータがビット分割選択回路103Aによって不一致テーブル103Bに送られる。

【0136】
この番地のVBフィールドの値を参照して、VB=1であれば、即ち登録された条件であると判断されると、各不一致テーブル103Bの対応するアドレスに、データ「1」を格納する。この動作が条件テーブル102Bの全てのアドレスに対して実行され、条件テーブル102Bに正しく対応した不一致テーブル103Bが構成される。このアドレスは8ビットのリングカウンタ等を用意することにより自動的に生成できる。

【0137】
これまで、モード選択信号の生成については、本発明においては本質的ではないので、詳細は触れなったが、モードの数に応じて適宜複数ビットを備えればよい。例えば、2ビットを用意し、(00)を通常のモード、(01)を登録モード、(10)を削除モード、(11)をリフレッシュモード、というように割り当てればよい。

【0138】
以上の説明から分かるように、本実施の形態によれば、パケットフィルタ回路100の照合データと登録データとの一致/不一致の判定動作およびそれを実現するハードウエアを利用して、パケットフィルタ回路100に含まれる各種のテーブルを自動的に作成、更新ができるようにしたため、テーブルを作成するためのソフトウェアや事前にテーブルを作成する手間が不要になった。

【0139】
なお、上述した実施の形態において、パケットフィルタ回路の各機能部は、CPU(中央演算装置)やメモリなどの記憶装置、インターフェースからなるコンピュータ(ハードウェア)にコンピュータプログラム(ソフトウェア)をインストールすることによって実現され、上述した各機能部は、上記のコンピュータの各種ハードウェア資源と上記コンピュータプログラムとが協働することによって実現される。

【0140】
また、上記のコンピュータプログラムは、コンピュータが読み取り可能な記録媒体や記憶装置に格納された状態で提供されても良く、電気通信回線を介して提供されても良い。

【0141】
〔実施の形態の拡張〕
本発明の実施の形態として一致判定回路102、不一致判定回路103を有するパケットフィルタ回路100について、各種テーブルの自動更新(登録・削除等)を説明したが、本発明はこの構成に限定されないことは言うまでも無い。

【0142】
本発明の主旨は、パケットフィルタ回路100において、通常のパケットの判定動作およびそれを実現する回路を利用して、各種テーブルを自動的に更新する機能を実現することである。

【0143】
例えば、図22に示した不一致判定回路を有さないパケットフィルタ回路200についても、図4に示したような構成を採用して、一致判定回路202における条件テーブルへの一致条件の登録や削除を行わせることが可能である。
【符号の説明】
【0144】
100…パケットフィルタ回路、101…バッファ回路、102…不一致判定回路、102A…索引テーブル、102B…条件テーブル、102C…レジスタ群、102C1…WADRレジスタ、102C2…tmPレジスタ、102C3…MCDレジスタ、102C4…CADRレジスタ、102C5…BADRレジスタ、102D…比較器、102E1~102E3…セレクタ、102F…処理部、103…不一致判定回路、103A…ビット分割/選択回路、103(103B1~103B4)…不一致テーブル、103C…ANDゲート、103D…処理部、103E…インバータ。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22
【図24】
23
【図25】
24
【図26】
25
【図27】
26
【図28】
27