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

データ判定装置およびデータ判定プログラム

国内特許コード P150012242
整理番号 2011-036
掲載日 2015年9月1日
出願番号 特願2011-273040
公開番号 特開2013-126058
登録番号 特許第5920698号
出願日 平成23年12月14日(2011.12.14)
公開日 平成25年6月24日(2013.6.24)
登録日 平成28年4月22日(2016.4.22)
発明者
  • 三浦 直樹
  • 浦野 正美
  • 松田 吉雄
  • 本田 良太
出願人
  • 日本電信電話株式会社
  • 国立大学法人金沢大学
発明の名称 データ判定装置およびデータ判定プログラム
発明の概要 【課題】パケットのフィルタリングを行う端末等において、照合データと登録データとの一致/不一致を判定するためのテーブルを作成するソフトウェアや、事前にテーブル作成する手間を不要とするデータ判定装置及びプログラムを提供する。
【解決手段】モード選択信号を登録モードに設定し、登録させたい条件(登録候補のデータ)を含むパケットをパケットフィルタ回路に入力する。登録候補のデータが入力されると、その登録候補のデータと条件テーブル102Bに格納されている登録データとが比較器102Dによって比較され、不一致の判定結果が得られると、レジスタ群102Cに記憶されているアドレス情報(空きアドレス)に基づいて、入力された登録候補のデータが条件テーブル102Bに登録データとして書き込まれる。同様にして、条件テーブル102Bからの登録データの削除も、比較器102Dでの比較結果(一致の判定結果)を利用して行う。
【選択図】図4
従来技術、競合技術の概要


ネットワークに接続された通信端末には、受信したパケットのフィルタリングを行うため、パケットフィルタ回路を搭載する端末がある。このパケットフィルタ回路は、受信したパケットに含まれるIPアドレスなどの照合データと、一致条件として事前に登録されている登録データ群中の登録データとを比較し、照合データと登録データとの一致/不一致を判定し、この判定結果に基づいてパケットの廃棄や透過等の処理を行う。ネットワークの大容量化に伴い、通信端末が送受信するパケット数が増加し、パケットフィルタ回路には、多量のパケットに対して判定を行うこと、すなわち高スループット化が求められている。



パケットフィルタ回路において、照合データと登録データとの一致/不一致を判定する方式の1つに線形探索方式(例えば、非特許文献1参照)がある。この線形探索方式は、照合データと登録データとを1つずつ照合し、照合データと登録データとが一致した場合は一致と判定し、照合データが何れの登録データとも一致しない場合は不一致と判定する。すなわち、線形探索方式は、照合データと全ての登録データとを照合した後で、不一致が判定される方式である。



〔従来例1〕
線形探索方式を実装したパケットフィルタ回路の代表的な構成を図22に示す。このパケットフィルタ回路200は、バッファ回路201と一致判定回路202とから成る。



バッファ回路201は、入力される判定要求信号とパケットをもとに、判定開始信号と照合データ(パケットの一部または全部からなるデータ)を、一致判定回路202に送る。一致判定回路202は、バッファ回路201からの照合データと一致条件として事前に登録されている登録データ群中の登録データとを比較して、一致の判定を行う。



一致判定回路202は、照合データと一致する登録データを検出した場合に、その時点でバッファ回路201に一致判定信号を出力する。全ての登録データとの照合を行っても、一致する登録データを検出できなかった場合には、バッファ回路201に不一致判定信号を出力する。



一致判定回路202からの一致判定信号/不一致判定信号はバッファ回路201に送られる。バッファ回路201は、一致判定信号が送られてくると、受信したパケットを透過し、不一致判定信号が送られてくると、受信したパケットを破棄する。



このような動作から分かるように、線形探索方式を実装したパケットフィルタ回路は、照合データと全ての登録データとを照合した後でなければ不一致と判定することができないため、一致判定に比べて不一致判定には時間を要する。通信端末におけるフィルタリング処理では、受信したパケットが不一致と判定される場合も多く、不一致判定に時間を要することがスループットを低下させる原因となっている。



パケットフィルタ回路において、照合データと登録データとの一致/不一致を判定する他の方式に、2分探索方式(例えば、非特許文献2参照)がある。この2分探索方式は、照合対象となる登録データを半分に絞り込んで行く方式である。この方式は、照合対象となる登録データを半分に絞り込んで行く方式であるため、照合対象となる登録データが線形探索方式に比べて減少し、一致を判定するまでの時間が短縮される。



しかしながら、この方式も、照合対象となる全ての登録データとの照合が完了した後でなければ不一致を判定することができず、不一致判定に時間を要することになる。他にも、ハッシュ関数を用いた方式(例えば、非特許文献3参照)などもあるが、何れの方式もすべて、照合対象となる全ての登録データとの照合を完了した後で、不一致が判定される方式であるため、不一致の判定に時間を要することになる。



そこで、例えば特許文献1や非特許文献4に、照合データと全ての登録データとの照合を完了する前に不一致を判定するようにしたパケットフィルタ回路が提案されている。このパケットフィルタ回路では、一致判定回路に加えて、不一致判定回路を用いる。



〔従来例2〕
図23に非特許文献4に示されたパケットフィルタ回路を示す。このパケットフィルタ回路300は、バッファ回路201と、一致判定回路202と、不一致判定回路203と、ORゲート204とから成る。



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



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



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



このパケットフィルタ回路300の動作を図24を用いて説明する。図24は、不一致と判定される「パケット1」と一致と判定される「パケット2」が連続して入力される場合のタイミングチャートを示している。



先ず、バッファ回路201が「パケット1」の照合データと判定開始信号を、一致判定回路202と不一致判定回路203に出力する。一致判定回路202と不一致判定回路203は、判定開始信号を受けて、「パケット1」の判定処理を同時に開始する。不一致判定回路203は、「パケット1」の照合データと一致する登録データがないと判定すると、その時点で不一致判定信号を出力する。この不一致判定信号は、ORゲート204を介して、バッファ回路201へ与えられる。不一致判定回路203での一致する登録データがない旨の判定は短時間で行われる。



バッファ回路201は、不一致判定信号が送られてくると、一致判定回路202が判定途中であっても、受信した「パケット1」を廃棄する。「パケット1」の処理が終了すると、バッファ回路201は、「パケット2」の照合データと判定開始信号を出力する。これにより、一致判定回路202と不一致判定回路203で、「パケット2」の判定処理が同時に開始される。一致判定回路202は、「パケット2」の照合データと一致する登録データを検出すると、その時点で一致信号を出力する。この一致信号はバッファ回路201へ与えられる。バッファ回路201は、一致信号が送られてくると、受信した「パケット2」を透過させる。



以上の動作から分かるように、このパケットフィルタ回路300では、不一致判定回路203が一致判定回路202よりも先に不一致を判定することで、判定処理時間が短縮され、実効スループットが向上する。



〔不一致判定回路〕
パケットフィルタ回路300において、不一致判定回路203は、短時間で不一致を判定するために、メモリを用いて照合データと予め登録されている登録データの有無情報とを一度に比較して、不一致の判定を行う。



不一致判定回路203に用いられるメモリの構成を図25に示す。このメモリMは、登録データの値をアドレスとして「一致(登録データ有り)」の判定を記憶し、それ以外のアドレスには「不一致(登録データ無し)」の判定を記憶する。図25では、登録データが「1」,「6」,「10」,「14」,「18」という5つの値である場合が示されている。この場合、メモリMのアドレスの「1」,「6」,「10」,「14」,「18」には「一致」の判定を格納し、それ以外のアドレスには「不一致」の判定を格納する。



このようなメモリMを用いることにより、照合時には、入力される照合データの値が読み出しアドレスとしてメモリMにアクセスされ、メモリMからは「一致」または「不一致」の判定が出力される。不一致判定回路203は、このメモリMからの出力をもとに、不一致を判定する。



図25に示したメモリMは、照合データが取り得る値の最大値と等しい容量が必要になる。つまり、照合データと登録データのビット長がnビットである場合、メモリMは2n個の判定を記憶することが必要になる。そこで、メモリの容量を削減するために、前述した非特許文献4には、nビットの照合データと登録データをmビットずつ、複数のメモリに分割して、並列に照合処理を行うことでメモリの容量を削減する手法が開示されている。



図26はn=16、m=4の場合の例である。図26では、各登録データの上位4ビットをメモリM1に割り当て、次の4ビットをメモリM2に、更に次の4ビットをメモリM3に、下位4ビットをメモリM4に割り当てている。例えば、16ビットの「0x1234」と「0x4567」という2つの登録データを4つのメモリに分割して記憶する場合、4ビットずつに分割された各登録データを、図25と同様にして、各メモリに記憶する。ここで、「0x」は16進数表示であることを意味する。



「0x1234」という登録データの場合、メモリM1には上位4ビットの値である「0x1」をアドレスとして「一致」の判定を記憶する。メモリM2には次の4ビットの値である「0x2」のアドレスに、メモリM3には更に次の4ビットの値である「0x3」のアドレスに、そしてメモリM4には下位4ビットの値である「0x4」のアドレスに、「一致」の判定を記憶する。



「0x4567」という登録データの場合も同様に、メモリM1には「0x4」のアドレスに、メモリM2には「0x5」のアドレスに、メモリM3には「0x6」のアドレスに、メモリM4には「0x7」のアドレスに、「一致」の判定を記憶する。これら以外の全てのアドレスには「不一致」の判定を記憶する。



このように、nビットの登録データをmビットずつ、複数のメモリに分割して、「一致」/「不一致」の判定を記憶させることにより、メモリの容量を(n/m)2mに削減できる。



不一致判定回路203のメモリを分割した構成とした場合、不一致判定時には、複数のメモリで並列に独立して照合を行い、どれか一つのメモリから不一致が出力されると照合データは不一致と判定される。例えば、図27に示すように、「0x1235」という照合データが入力された場合、メモリM1、メモリM2、メモリM3からは「一致」の判定が、メモリM4からは「不一致」の判定が出力され、照合データは不一致と判定される。



しかし、照合データが不一致にもかかわらず不一致と判定できない場合がある。例えば、図28に示すように、「0x1237」という照合データが入力された場合、このデータは登録データではないので、不一致と判定されるべきであるが、全てのメモリM1~M4(以下、このメモリを不一致テーブルと呼ぶ)は「一致」の判定を出力するため、一致と判定される。この場合、一致判定回路202が全ての登録データとの照合を行い、最終的に不一致と判定するため、誤った判定を行うことはない。



〔一致判定回路〕
一致判定回路202には、前述したように、照合データと登録データとを順次照合していく線形探索方式や順次半分に絞り込んでゆく2分探索方式、ハッシュ探索方式法などを実装して用いることができる。いずれの方式を用いるにせよ、一致判定回路202には、登録データを記憶させておくメモリ(以下、このメモリを条件テーブルと呼ぶ)が必要であり、この条件テーブルから登録データを効率よく読み出すことにより照合データの一致/不一致を判定する。

産業上の利用分野


この発明は、入力された照合データが予め登録されている登録データ群中の登録データと一致するか否かを判定するデータ判定装置およびデータ判定プログラムに関するものである。

特許請求の範囲 【請求項1】
入力された照合データが予め登録されている登録データ群中の登録データと一致するか否かを判定するデータ判定装置において、
前記登録データが格納される登録データ格納手段と、
前記登録データ格納手段における前記登録データが格納されていないアドレスを含むアドレス情報を記憶するアドレス情報記憶手段と、
前記登録データ格納手段に格納されている登録データと前記照合データとを比較し一致/不一致の判定結果を得る比較手段と、
前記登録データ格納手段に格納されている登録データを更新する際に、前記登録データ格納手段に登録すべき登録候補のデータの入力を受けて、その登録候補のデータと前記登録データ格納手段に格納されている登録データとの比較を前記比較手段によって行わせ、不一致の判定結果が得られた場合、前記アドレス記憶手段に記憶されているアドレス情報に基づいて、前記入力された登録候補のデータを登録データとして前記登録データ格納手段に書き込む手段と
前記登録データ格納手段に格納されている登録データを更新する際に、前記登録データ格納手段から削除すべき削除候補のデータの入力を受けて、その削除候補のデータと前記登録データ格納手段に格納されている登録データとの比較を前記比較手段によって行わせ、一致の判定結果が得られた場合、前記アドレス記憶手段に記憶されているアドレス情報に基づいて、前記入力された削除候補のデータと一致する登録データを前記登録データ格納手段から削除する手段と
を備えることを特徴とするデータ判定装置。

【請求項2】
請求項1に記載されたデータ判定装置において、
前記照合データの一部の情報をアドレスとして該アドレスの値を一部の情報として含んでいる登録データが前記登録データ格納手段に格納されているか否かを示す情報を格納した登録データ有無情報格納手段と、
前記登録データ有無情報格納手段に格納されている情報に基づいて前記照合データが前記登録データ格納手段に格納されている登録データと一致していないことを判定する不一致判定手段と、
前記登録データ有無情報格納手段に格納されている情報を更新する際に、前記登録データ有無情報格納手段に格納されている情報を全て削除した後、前記登録データ格納手段に格納されている登録データを読み出し、この読み出した登録データの一部の情報をアドレスとして前記登録データ有無情報格納手段にアクセスし、このアクセスした登録データ有無情報格納手段のアドレスに、当該アドレスの値を一部の情報として含んでいる登録データが前記登録データ格納手段に格納されていることを示す情報を書き込む手段と
を備えることを特徴とするデータ判定装置。

【請求項3】
請求項1又は2に記載されたデータ判定装置の各手段での処理をコンピュータで実行させるためのデータ判定プログラム
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2011273040thum.jpg
出願権利状態 登録
(有)金沢大学ティ・エル・オーは、金沢大学の研究者の出願特許を産業界へ技術移転することを主目的として、金沢大学の教官の出資により設立された技術移転機関です。
ご興味のある方は、下記「問合せ先」へ整理番号と共にご連絡願います。
なお、既に活用のお申し込み・お打合わせ等の段階に入っている場合もございますので、予めご承知おきください。


PAGE TOP

close
close
close
close
close
close
close