(57)【要約】【課題】検索処理の速度を高速に保ちつつ、検索データベースの管理処理の高速化と簡易化とを図ることが可能なパケット処理検索システムを提供する。【解決手段】処理演算装置２２はパケット受信装置１で受信されたパケットをパケット記憶装置２１へ格納し、パケットデータのうちの先頭のデータであるヘッダ情報を抽出し、パケット検索装置３に該当パケットの処理内容検索処理を依頼する。検索処理演算装置３２は依頼されたパケットヘッダと、検索データ記憶装置３１に格納されている検索条件とを比較することによって検索処理を行い、検索処理の結果を処理演算装置２２へ返信する。処理演算装置２２は検索結果にしたがって、パケット記憶装置２１から該当パケットの処理内容を読出し、読出した内容にしたがってパケット処理を行う。【選択図】      図１
2004172917.tif 000002
【特許請求の範囲】
【請求項１】
入力されたパケットに対してパケットフィルタ検索を行うパケット検索装置であって、前記パケットのヘッダ情報の複数の情報領域各々に対する検索条件文を第１の検索法で検索する第１の検索処理手段と、前記第１の検索処理手段の検索結果に対して前記第１の検索法とは異なる第２の検索法で検索する第２の検索処理手段とを有することを特徴とするパケット検索装置。
【請求項２】
前記第１の検索処理手段は、前記ヘッダ情報を複数の情報領域に分割し、前記情報領域毎に各検索条件文を二分検索木によって分散して検索を行うことを特徴とする請求項１記載のパケット検索装置。
【請求項３】
前記第２の検索処理手段は、前記第１の検索処理手段の検索結果を集約したものをハッシュ法によって検索を行うことを特徴とする請求項２記載のパケット検索装置。
【請求項４】
前記第１及び第２の検索処理手段の検索結果各々を前記情報領域毎に管理するための検索データベースを含むことを特徴とする請求項１から請求項３のいずれか記載のパケット検索装置。
【請求項５】
前記検索データベースは、複数の検索キーを保持することを特徴とする請求項４記載のパケット検索装置。
【請求項６】
前記第２の検索処理手段において検索結果の組合せのみを管理することを特徴とする請求項３から請求項５のいずれか記載のパケット検索装置。
【請求項７】
前記ヘッダ情報によってＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）情報及びフィルタ情報検索を少なくとも行うことを特徴とする請求項１から請求項６のいずれか記載のパケット検索装置。
【請求項８】
前記パケット検索処理を少なくともルータ装置及びファイアウォール装置上で行うことを特徴とする請求項１から請求項７のいずれか記載のパケット検索装置。
【請求項９】
入力されたパケットに対してパケットフィルタ検索を行ってからパケット処理を行うパケット処理検索方法であって、前記パケットのヘッダ情報の複数の情報領域各々に対する検索条件文を第１の検索法で検索する第１のステップと、前記第１のステップの検索結果に対して前記第１の検索法とは異なる第２の検索法で検索する第２のステップとを有することを特徴とするパケット処理検索方法。
【請求項１０】
前記第１のステップは、前記ヘッダ情報を複数の情報領域に分割し、前記情報領域毎に各検索条件文を二分検索木によって分散して検索を行うことを特徴とする請求項９記載のパケット処理検索方法。
【請求項１１】
前記第２のステップは、前記第１のステップの検索結果を集約したものをハッシュ法によって検索を行うことを特徴とする請求項１０記載のパケット処理検索方法。
【請求項１２】
前記第１及び第２のステップの検索結果各々を検索データベースを用いて前記情報領域毎に管理することを特徴とする請求項９から請求項１１記載のパケット処理検索方法。
【請求項１３】
前記検索データベースは、複数の検索キーを保持することを特徴とする請求項１２記載のパケット処理検索方法。
【請求項１４】
前記第２のステップにおいて検索結果の組合せのみを管理することを特徴とする請求項１１から請求項１３のいずれか記載のパケット処理検索方法。
【請求項１５】
前記パケットのヘッダ情報によってＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）情報及びフィルタ情報検索を少なくとも行うことを特徴とする請求項９から請求項１４のいずれか記載のパケット処理検索方法。
【請求項１６】
前記パケット検索処理を少なくともルータ装置及びファイアウォール装置上で行うことを特徴とする請求項９から請求項１５のいずれか記載のパケット処理検索方法。
【請求項１７】
入力されたパケットに対してパケットフィルタ検索を行ってからパケット処理を行うパケット処理検索方法のプログラムであって、コンピュータに、前記パケットのヘッダ情報の複数の情報領域各々に対する検索条件文を第１の検索法で検索する第１の処理と、前記第１の処理の検索結果に対して前記第１の検索法とは異なる第２の検索法で検索する第２の処理とを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケット検索装置及びそれに用いるパケット処理検索方法並びにそのプログラムに関し、特にルータ装置、ファイアウォール装置上のパケットフィルタ検索を行い、パケット処理を行うパケット処理システムに関する。
【０００２】
【従来の技術】
従来、ルータ装置やファイアウォール装置におけるパケット処理システムやパケットフィルタ検索システムとしては、パケットの先頭データであるヘッダ情報によって、該当パケットの優先度付けや転送の可否の特定を行うシステムがある（第１の従来技術とする）（例えば、非特許文献１参照）。このパケットフィルタ検索システムにおいては、検索方式として、パケットヘッダの情報を検索に必要な複数の情報領域データに分割し、各情報領域データを検索キーとして検索を行っている。
【０００３】
また、他のパケットフィルタ検索システムとしては、検索方式として、２分木検索法を改良した検索用の検索木のデータベースを構築して検索を行うシステムがある（第２の従来技術とする）（例えば、非特許文献２参照）。
【０００４】
さらに、別のパケットフィルタ検索システムとしては、ハッシュ（Ｈａｓｈ）法によって検索を実行するマイクロプロセッサを複数段に構成し、パイプライン効果によって処理速度の向上を行うシステムがある（第３の従来技術とする）（例えば、特許文献１参照）。
【０００５】
【特許文献１】
特開２０００−１７４８０５号公報（第６〜９頁、図１〜３）
【非特許文献１】
Ｐ．Ｇｕｐｔａ  ａｎｄ  Ｎ．ＭｃＫｅｏｗｎ，“Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｃａｔｉｏｎ  ｏｎ  Ｍｕｌｔｉｐｌｅ  Ｆｉｅｌｄｓ”，ＡＣＭＳＩＧＣＯＭＭ’９９，Ｓｅｐｔｅｍｂｅｒ  １９９９
【非特許文献２】
Ｆ．Ｂａｂｏｅｓｃｕ  ａｎｄ  Ｇ．Ｖａｒｇｈｅｓｅ  Ｓｃａｌａｂｌｅ，Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ＡＣＭ  ＳＩＧＣＯＭＭ‘０１  Ａｕｇｕｓｔ，２００１
【０００６】
【発明が解決しようとする課題】
しかしながら、上述した第１の従来技術では、パケットの優先度付けや転送の可否の特定を行う情報を上記検索キーに対応させて検索データベースに保持しなければならない。そのため、検索データベースは情報領域データに対してすべての情報を記憶装置に反映する必要があり、登録条件数に比べて必要な記憶装置の容量が巨大になるので、データベースを管理する場合、制御用ＣＰＵ（中央処理装置）に大きな処理能力が必要とされる。
【０００７】
また、第２の従来技術では、メモリ容量を減少させることが可能となるが、その検索データベースに対して、新たに検索条件を追加する場合や、すでに記憶装置に反映されたデータベースから検索条件を削除する場合、最適化されたデータベースを再度、はじめから構築し直す必要がある。その結果、この方法でも検索データベースを管理する制御用ＣＰＵに大きな処理能力が必要とされる。
【０００８】
さらに、第３の従来技術では、マイクロプロセッサ間での処理内容にデータ依存があるため、検索データベースの管理が複雑になり、制御用ＣＰＵに大きな処理能力が必要とされる。
【０００９】
このように、従来の方式では、検索方法そのものの処理能力の向上や、検索データベースの記憶領域の縮小化が行われてきている。しかしながら、近年、悪意のあるユーザが、違反したデータパケットをルータ装置等に対して転送することがある。この場合、ルータ装置では、違反したパケットに対して、どのように違反しているのかを制御用ＣＰＵでのソフト処理によって判断して処理を行っている。したがって、制御用ＣＰＵの処理能力が違反パケットのために低下し、本来行わなければならないルーティング情報の管理ができなくなるという問題が発生する。
【００１０】
その結果、ルータ装置の制御用ＣＰＵやファイアウォール装置における制御用ＣＰＵにおいて、運用性や信頼性に対して大きな影響を与えることが考えられる。そこで、システム使用者は違反パケットを転送するユーザを特定し、制御用ＣＰＵにパケットが転送されないようにフィルタ動作をハードウェア処理で行い、システムを外部の攻撃から守ることが必要とされている。
【００１１】
したがって、上述した従来のパケットフィルタ検索システムでは、検索処理の処理能力だけを最適化すると、検索データベースに必要な記憶装置が大容量となるため、パケットフィルタ検索データベースの構築処理が低速になるという問題がある。
【００１２】
また、従来のパケットフィルタ検索システムでは、検索データベースを格納するのに必要な記憶装置の容量の縮小化だけを最適化すると、検索データベースの最適化処理が複雑になり、結果的に、データベースへの追加、削除が複雑になるため、パケットフィルタ検索データベースの編集処理が低速になるという問題がある。
【００１３】
そこで、本発明の目的は上記の問題点を解消し、検索処理の速度を高速に保ちつつ、検索データベースの管理処理の高速化と簡易化とを図ることができるパケット検索装置及びそれに用いるパケット処理検索方法並びにそのプログラムを提供することにある。
【００１４】
【課題を解決するための手段】
本発明によるパケット検索装置は、入力されたパケットに対してパケットフィルタ検索を行うパケット検索装置であって、前記パケットのヘッダ情報の複数の情報領域各々に対する検索条件文を第１の検索法で検索する第１の検索処理手段と、前記第１の検索処理手段の検索結果に対して前記第１の検索法とは異なる第２の検索法で検索する第２の検索処理手段とを備えている。
【００１５】
本発明によるパケット処理検索方法は、入力されたパケットに対してパケットフィルタ検索を行ってからパケット処理を行うパケット処理検索方法であって、前記パケットのヘッダ情報の複数の情報領域各々に対する検索条件文を第１の検索法で検索する第１のステップと、前記第１のステップの検索結果に対して前記第１の検索法とは異なる第２の検索法で検索する第２のステップとを備えている。
【００１６】
本発明によるパケット処理検索方法のプログラムは、入力されたパケットに対してパケットフィルタ検索を行ってからパケット処理を行うパケット処理検索方法のプログラムであって、コンピュータに、前記パケットのヘッダ情報の複数の情報領域各々に対する検索条件文を第１の検索法で検索する第１の処理と、前記第１の処理の検索結果に対して前記第１の検索法とは異なる第２の検索法で検索する第２の処理とを実行させている。
【００１７】
すなわち、本発明のパケット処理検索システムは、パケット検索処理を２つの処理段階に分割し、別々の検索法によってフィルタ情報の検索を行うことを特徴としている。
【００１８】
第１の検索処理は、パケットヘッダ情報を複数の情報領域に分割し、各情報領域別に各検索条件文を二分検索木によって分散して検索を行う。また、第２の検索処理は、第１の検索処理の検索結果を集約したものをハッシュ（Ｈａｓｈ）法によって検索を行う。
【００１９】
これによって、本発明では、第１の検索処理の結果に対して各情報領域別に検索データベースを管理するため、検索データベースの管理処理の高速化が可能となり、第２の検索処理では検索結果の組合せのみの管理であるため、情報の簡易化が可能となる。
【００２０】
したがって、本発明のパケット処理検索システムでは、全体の検索処理システムとして考えると、検索処理の速度を高速に保ちつつ、検索データベースの管理処理の高速化と簡易化とを図ることが可能となる。
【００２１】
【発明の実施の形態】
次に、本発明の実施例について図面を参照して説明する。図１は本発明の一実施例によるパケット処理検索システムの構成を示すブロック図である。図１において、本発明の一実施例によるパケット処理検索システムはパケット受信装置１と、パケット処理装置２と、パケット検索装置３と、パケット送信装置４と、制御装置５と、入出力装置６とから構成されている。
【００２２】
パケット受信装置１はパケットを受信し、パケット送信装置４はパケットをシステム外へ送信する。パケット処理装置２はパケットデータを処理し、パケット検索装置３はパケットデータの中の検索条件情報から該当パケットに必要な処理を検索する。制御装置５はパケット処理装置２とパケット検索装置３とを運用・管理し、入出力装置６はシステム使用者が制御装置５に対して処理内容を設定する。
【００２３】
パケット受信装置１はパケット処理検索システム外部から転送されるパケットデータを受信し、パケット処理装置２に転送する機能を備えている。パケット送信装置４はパケット処理装置２で処理されたパケットデータをパケット処理検索システム外部へ送信する機能を備えている。
【００２４】
パケット処理装置２はパケットデータを格納し、格納したパケットに対する処理内容を記憶するパケット記憶装置２１と、パケット記憶装置２１から読出したデータによって処理内容の判断を行い、処理を実行する処理演算装置２２とを備えている。その処理内容としては、パケットデータの編集やパケット転送やパケットの廃棄等のそのシステムに適した処理内容を使用すればよい。
【００２５】
パケット検索装置３は検索処理に必要な検索条件等のデータが格納された検索データ記憶装置３１と、検索データ記憶装置３１から読出したデータによって検索処理を実行する検索処理演算装置３２とから構成され、検索処理演算装置３２をコンピュータで実現する場合にそのコンピュータで実行されるプログラムを格納する記録媒体３３が接続されている。この構成によって、パケット検索装置３はパケットデータの先頭データであるヘッダ情報を基に、該当パケットのフィルタ及びＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）の処理内容を検索する。
【００２６】
制御装置５は入出力装置６を通してシステム使用者がシステムに対して行った設定内容を受信し、その設定内容をパケット記憶装置２１に記憶させることによって、パケット処理装置２に対して処理内容を設定する。また、制御装置５は入出力装置６を通して受信した検索条件を検索データ記憶装置３１に記憶させることによって、パケット検索装置３に対して検索条件を設定する。制御装置５はこれらの設定が完了した場合、入出力装置６によってシステム使用者に設定完了を通知する。
【００２７】
入出力装置６はシステム使用者が上記の設定内容や検索条件を含むシステムに対する設定を行う装置であり、その設定の結果をシステム使用者へ通知する装置である。
【００２８】
システムの動作順序としては、システム使用者は入出力装置６によって、システムに対する設定内容を要求する。制御装置５は入出力装置６を通して要求された設定内容によって、パケット処理装置２及びパケット検索装置３それぞれに設定を行う。
【００２９】
パケット受信装置１で受信されたパケットデータは、パケット処理装置２へ転送される。この時、処理演算装置２２は受信したパケットをパケット記憶装置２１へ格納する。また、処理演算装置２２はパケットデータのうちの先頭のデータであるヘッダ情報を抽出し、パケット検索装置３に該当パケットの処理内容検索処理を依頼する。
【００３０】
検索処理演算装置３２では依頼されたパケットヘッダと、検索データ記憶装置３１に格納されている検索条件とを比較することによって、パケットの検索処理を行い、その検索処理の結果を処理演算装置２２へ返信する。処理演算装置２２は検索処理の結果を受信すると、その検索処理の結果にしたがってパケット記憶装置２１から該当パケットの処理内容を読出し、読出した内容にしたがってパケット処理を行う。
【００３１】
処理内容でシステム外へ転送する場合には、パケット送信装置４にパケットデータを送信する。パケット送信装置４は受信したパケットデータをシステムの外部へと転送する。
【００３２】
システム使用者は、上記の設定内容が必要でなくなった場合、入出力装置６を通して設定した内容の削除要求を行うことが可能である。削除要求を受取った制御装置５はパケット処理装置２及びパケット検索装置３に対して設定の削除処理を行う。
【００３３】
図２は本発明の一実施例における検索対象パケットの構成例を示す図である。図２において、検索対象パケットＡはＭＡＣ（ＭＡＣ）ヘッダ（Ｈｅａｄｅｒ）Ａ１と、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ヘッダＡ２と、ＴＣＰ／ＵＤＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）ヘッダＡ３と、通信データＡ４とから構成されている。
【００３４】
ヘッダの検索条件の情報領域としては、階層化されたネットワークの検索対象パケットＡの先頭データのＩＰヘッダＡ２に宛て先を示す宛て先ＩＰアドレス、送信元を示す送信元ＩＰアドレス、パケット優先度を示すサービスタイプ、パケットの処理内容を特定するプロトコル、パケットの大きさを示すパケット長等がある。システム使用者はこれらの情報領域に対して条件文を設定する。この場合には、情報領域と条件文とを複数組合せることも可能である。システム使用者はこの組合せに対して処理内容を決定し、システムへ設定する。
【００３５】
図３は図１の検索処理演算装置３２における処理ブロックを示すブロック図である。図３において、検索処理演算装置３２は情報領域分別手段３２ａと、二分木検索手段３２ｂと、検索結果集約手段３２ｃと、ハッシュ検索手段３２ｄとから構成されている。
【００３６】
情報領域分別手段３２ａは受信したパケットデータのヘッダ情報を、検索に使用する複数の情報領域＃１〜＃５に分別する。例えば、上記の図２に示すＩＰヘッダＡ２の場合には、情報領域＃１が「宛て先ＩＰアドレス」、情報領域＃２が「送信元ＩＰアドレス」、情報領域＃３が「サービスタイプ」、情報領域＃４が「プロトコル」、情報領域＃５が「パケット長」となる。但し、上記の情報領域の数はこの数に限定されず、また情報領域の内容も上記の例に限定されない。
【００３７】
二分木検索手段３２ｂは情報領域分別手段３２ａで分別された複数の情報領域＃１〜＃５に対応して検索処理３２ｂ１〜３２ｂ５が実行される。検索処理３２ｂ１〜３２ｂ５では情報領域＃１〜＃５を入力として与えると、設定された条件文に適応した場合、そのＩＤを出力する。
【００３８】
検索結果集約手段３２ｃは二分木検索手段３２ｂの各情報領域別の検索結果としてＩＤが送られてくると、そのＩＤを集約する。ハッシュ検索手段３２ｄは検索結果集約手段３２ｃで集約された二分木検索手段３２ｂの各情報領域別の検索結果検索から、ハッシュ（Ｈａｓｈ）法を利用して最終的な処理内容を確定する。
【００３９】
上記の二分木検索手段３２ｂの検索処理とハッシュ検索手段３２ｄの検索処理とが終了した時点で、パケット検索装置３は与えられたパケットヘッダから処理内容の検索することが可能となる。さらに、本実施例ではその検索処理が高速であり、またその検索管理テーブル（Ｔａｂｌｅ）の管理処理が簡易化されることとなる。
【００４０】
図４は本発明の一実施例における検索木の最適化の一例を示す図であり、図５は本発明の一実施例における検索木の最適化の一例を示す図であり、図６は本発明の一実施例における検索処理の概略を示す図であり、図７は本発明の一実施例による検索処理を示すフローチャートである。これら図１〜図７を参照して本発明の一実施例による検索処理について説明する。尚、図７に示す処理はコンピュータが記録媒体３３のプログラムを実行することで実現される。
【００４１】
受信したパケットデータのヘッダ情報は検索処理演算装置３２に転送される。ヘッダ情報は複数の情報領域に分割することができる。パケットデータの処理内容はこの複数の情報領域を用いることによって、システム使用者が処理内容を決定する。
【００４２】
まず、検索処理演算装置３２では、図３に示すように、受信したパケットデータのヘッダ情報を、情報領域分別手段３２ａによって検索に使用する複数の情報領域＃１〜＃５に分割し（図７ステップＳ１〜Ｓ３）、二分木検索手段３２ｂによって複数の情報領域＃１〜＃５に対応した検索処理３２ｂ１〜３２ｂ５が実行される（図７ステップＳ４，Ｓ５）。検索処理３２ｂ１〜３２ｂ５各々は情報領域＃１〜＃５が入力として与えられると、設定された条件文に適応した場合、そのＩＤを出力する。
【００４３】
本実施例では検索処理３２ｂ１〜３２ｂ５として二分木検索を行っている。現在、フィルタ条件としては、ＴＣＰパケットやＵＤＰパケットのソースポートやデスティネーションポートによる指定まで必要とされ、さらに１０進数の範囲指定まで必要とされている。このようなフィルタ条件が指定された場合には、ハッシュ法を用いると、ハッシュテーブル（Ｈａｓｈ  Ｔａｂｌｅ）が数多く必要となり、データベース管理が複雑になってしまう。そのため、本実施例では上記の二分木検索法を用いている。
【００４４】
この検索処理３２ｂ１〜３２ｂ５において、情報領域別で分割して検索することによって、各検索木を分割することになる。その結果、分割しない場合の検索木よりも小さな検索木として管理することが可能となり、検索木の編集処理が小さくなる。また、この検索処理３２ｂ１〜３２ｂ５では各検索処理において、相互依存が必要ないため、検索処理を並列に行うことが可能となり、検索処理が高速になる。さらに、検索処理３２ｂ１〜３２ｂ５は演算回路を複数段にすることで、パイプライン化も実行可能となり、処理能力の向上を図ることもできる。尚、この検索処理３２ｂ１〜３２ｂ５では検索処理を直列に順次行うことも、またこれらの組合せも可能である。
【００４５】
さらにまた、本実施例では、検索木について最適化を行っている。検索木の最適化の手法として、「Ｆ．Ｂａｂｏｅｓｃｕ  ａｎｄ  Ｇ．Ｖａｒｇｈｅｓｅ  Ｓｃａｌａｂｌｅ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ＡＣＭ  ＳＩＧＣＯＭＭ’０１，Ａｕｇｕｓｔ，２００１」に記載されているような一般的な手法として、図４に示すように、２つの枝を持たない二分木Ｂの支点を一つの分岐条件への圧縮を行う（検索木Ｃ）。その結果、本実施例では、検索木Ｃを用いることで、処理の高速化や記憶領域の縮小化を図ることができる。
【００４６】
一方、本実施例では、さらに検索木の高速化の手法として、図５に示すように、すべての枝が枝分かれしている部分木Ｄを２つ以上の枝を持つ支点への縮小化を行う  （検索木Ｅ）。図５に示す例では、縮小化前では、３回の比較処理が必要であるのに対して、検索木Ｅに示すように、縮小化によって１度の比較処理に短縮されるため、検索処理を高速化することが可能となる。
【００４７】
すなわち、検索木は、図４に示す圧縮と図５に示す縮小化とによって最適化を行う。本実施例では、さらにこの最適化の単位を検索木全体に行うのではなく、８ｂｉｔの領域に分割して最適化を行う。この場合、分割しないで、全体で最適化された検索木のほうが、処理速度と記憶領域とに優れているが、新たな条件文の追加登録を行う場合やすでに設定された条件文を削除する場合、最適化された検索木全体を再編集する必要があるため、その編集処理が遅くなってしまう。
【００４８】
また、分割する単位が８ｂｉｔ数であるのは、情報領域の一つとして使用されるネットワークアドレス自体が、８ｂｉｔ単位で分割して管理されるためである。よって、条件文の値の違いが８ｂｉｔで分割されることになるので、分割してから最適化する検索木と全体で最適化された最適木とでは、それらの処理能力及び記憶領域の差が小さくてすむ。
【００４９】
二分木検索手段３２ｂの検索処理３２ｂ１〜３２ｂ５の段階で、各情報領域別に検索結果のＩＤが得られる。しかしながら、最終的な検索結果は検索処理３２ｂ１〜３２ｂ５の組合せによって決定される。そこで、これらの複数の検索結果を検索結果集約手段３２ｃで集約し（図７ステップＳ６）、その集約された検索結果から最終的な処理内容をハッシュ検索手段３２ｄによって確定する（図７ステップＳ７，Ｓ８）。
【００５０】
ハッシュ検索手段３２ｄはハッシュ法を利用して、検索結果集約手段３２ｃで集約された検索結果に対する検索を行う。この場合には、図６に示すように、複数の検索結果ａのＩＤから一つの定まったテーブル（検索キーｂ）を作成する。このテーブルは各情報領域別に格納される場所が予め定められている。
【００５１】
したがって、このテーブルから求められるハッシュ値は、ハッシュ関数が一方向性を持つため、各検索結果のＩＤ値が違えば、そのハッシュ値が異なる値を示す特性を持つことになり、各条件結果の組合せが判別可能となり、最終検索結果ｃを得ることが可能となる。上記のように、ハッシュ値で管理にすることによって、処理の高速化が可能となる。また、テーブル管理が検索結果のＩＤ値によって行われるため、必要とするハッシュ値を少なくすることが可能となる。
【００５２】
二分木検索手段３２ｂの検索処理とハッシュ検索手段３２ｄの検索処理とが終了した時点で、パケット検索装置３は与えられたパケットヘッダから処理内容の検索が可能となる。さらに、本実施例ではその検索処理が高速であり、またその検索管理テーブルの管理処理が簡易化されることとなる。
【００５３】
例えば、３２ｂｉｔのＩＰアドレスと１６ｂｉｔのアプリケーション情報（ＴＣＰポート情報）とから検索を行う場合、本実施例では３２ｂｉｔのＩＰアドレスと１６ｂｉｔのアプリケーション情報とをそれぞれ８ｂｉｔのＩＤとしてからハッシュ値を算出するため、従来の３２ｂｉｔのＩＰアドレスと１６ｂｉｔのアプリケーション情報とからハッシュ値を算出する処理よりも高速にすることができ、その検索管理テーブルの管理処理も簡易化することができる。
【００５４】
図８は本発明の一実施例における検索木の管理テーブルの構成例を示す図である。検索木の具体的な実装案としては、図８に示すように、例えば、各支点の情報を、０の圧縮ｂｉｔ数（ｂｉｔ０の連枝数）、１の圧縮ｂｉｔ数（ｂｉｔ１の連枝数）、枝の数（枝数）、各枝の先につながる支点のメモリアドレス（Ｎｅｘｔ  ｐｏｉｎｔｅｒ）のような管理テーブルを実装すれば、圧縮や集約された支点情報を一元的に管理することが可能となり、単一メモリにも実装可能となる。また、各検索木別に記憶装置が実装可能となれば、メモリアクセスの競合の問題も少なくすることが可能である。
【００５５】
次に、実際に検索条件の管理方法について具体的に考える。システム使用者は、ヘッダ情報の各種情報領域に対して条件文を登録または削除を行う。この場合、制御装置５では検索木が分割されているため、登録・削除を行う情報領域の検索木のみの編集処理で実現することができる。
【００５６】
続いて、システム使用者は、実際のフィルタやＱｏＳの「処理内容」と処理内容に対する「各種情報領域に条件文の組合せ」とを登録・削除する。登録の場合、条件文はすでに検索木で登録されているため、条件文の組合せからハッシュ検索手段３２ｄのハッシュ値を計算し、計算されたハッシュ値をアドレス（Ｎｅｘｔ  ｐｏｉｎｔｅｒ）とするテーブルに処理内容として記述する。
【００５７】
また、処理内容の設定を削除する場合には、検索木を編集する必要がなく、ハッシュ値のテーブルを削除するだけで実現可能となるため、制御装置５は検索条件とその処理内容との登録・削除が容易となる。
【００５８】
図９は本発明の他の実施例によるパケット処理検索システムの構成を示すブロック図である。図９において、本発明の他の実施例によるパケット処理検索システムは図１に示すパケット処理装置２とパケット検索装置３とを統合したパケット検索処理装置７を設けた以外は図１に示す本発明の一実施例によるパケット処理検索システムと同様の構成となっており、同一構成要素には同一符号を付してある。
【００５９】
パケット検索処理装置７はパケット処理とパケット検索とを実行する処理演算装置７２と、パケットデータとパケットフィルタ検索データベースと処理内容とを記憶するパケット検索データ記憶装置７１と、検索処理演算装置７２をコンピュータで実現する場合にそのコンピュータで実行されるプログラムを格納する記録媒体７３とを備えている。
【００６０】
処理演算装置７２はパケットデータを受信し、各情報領域に分割し、検索木によって検索し、その結果をテーブルにまとめてハッシュ値を計算する。その結果、処理演算装置７２は処理内容を決定し、パケットデータの処理を行うという一連の処理を一つの演算回路で実施する。
【００６１】
また、記録媒体７３にこの一連の処理演算命令を記憶させ、汎用プロセッサに実行させてもよい。このように、処理内容を決定し、パケットデータの処理を行うという一連の処理を一つの演算回路で実施することで、装置規模の小型化が可能となり、拡張性のある方式として利用可能となる。
【００６２】
本発明の一実施例ではパケット処理と検索処理とを別々な演算処理機で実行させているが、本実施例のように、汎用プロセッサでのソフトウェア処理として、上記の本発明の一実施例による検索方式をそのまま適用しても、十分な改善速度が得られる。
【００６３】
図１０は本発明の別の実施例によるパケット処理検索システムの構成を示すブロック図である。図１０において、本発明の別の実施例によるパケット処理検索システムは図１に示すパケット検索装置３をパケット条件文検索を行うパケット検索装置８とパケット条件組合せ検索を行うパケット検索装置９とに分割した以外は図１に示す本発明の一実施例によるパケット処理検索システムと同様の構成となっており、同一構成要素には同一符号を付してある。
【００６４】
パケット検索装置８は、図３に示す二分木検索手段３２ｂの検索処理のみを実行する装置であり、パケット処理装置２からパケットヘッダを受信し、各情報領域に分割して、検索木による検索処理を行う。パケット検索装置８はその検索結果をパケット検索装置９へ返す。
【００６５】
パケット検索装置９はパケット検索装置８から各検索木の検索処理結果を得ると、その結果から、図３に示すハッシュ検索手段３２ｄの検索処理のみを実行し、検索した結果をパケット処理装置２へ返す。尚、パケット検索装置８，９は検索処理演算装置８２，９２をコンピュータで実現する場合にそのコンピュータで実行されるプログラムを格納する記録媒体８３，９３を備えている。
【００６６】
本実施例では、図３に示す二分木検索手段３２ｂの検索処理とハッシュ検索手段３２ｄの検索処理とが、検索条件に対して相互依存した処理内容が存在しないため、この場合、各処理内容を別々の装置に分割することが可能であり、図１に示す構成よりもさらに処理速度の向上が可能となる。
【００６７】
このように、本発明では、各検索条件文を二分検索木によって実装し、複数の検索条件文の組合せをハッシュ法によって管理しているため、検索データベースの管理の処理を高速に行うことができる。
【００６８】
また、本発明では、制御用ＣＰＵがルーティングプロトコルの処理等に集中することが可能となるため、操作性、保守性、セキュリティを向上させることができる。
【００６９】
さらに、本発明では、ソフトウェアによる実装から複数の演算回路を並列処理化、パイプライン化可能となるため、検索システムとして必要な処理能力に見合ったシステムが構築可能となり、拡張性のある検索システムを構築することができる。
【００７０】
【発明の効果】
以上説明したように本発明は、パケットフィルタ検索を行ってからパケット処理を行うパケット処理検索システムにおいて、パケット検索処理を第１及び第２の処理段階に分割し、第１及び第２の処理段階において各々異なる検索法によってフィルタ情報の検索を行うことによって、検索処理の速度を高速に保ちつつ、検索データベースの管理処理の高速化と簡易化とを図ることができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の一実施例によるパケット処理検索システムの構成を示すブロック図である。
【図２】本発明の一実施例における検索対象パケットの構成例を示す図である。
【図３】図１の検索処理演算装置における処理ブロックを示すブロック図である。
【図４】本発明の一実施例における検索木の最適化の一例を示す図である。
【図５】本発明の一実施例における検索木の最適化の一例を示す図である。
【図６】本発明の一実施例における検索処理の概略を示す図である。
【図７】本発明の一実施例による検索処理を示すフローチャートである。
【図８】本発明の一実施例における検索木の管理テーブルの構成例を示す図である。
【図９】本発明の他の実施例によるパケット処理検索システムの構成を示すブロック図である。
【図１０】本発明の別の実施例によるパケット処理検索システムの構成を示すブロック図である。
【符号の説明】
１  パケット受信装置
２  パケット処理装置
３，８，９  パケット検索装置
４  パケット送信装置
５  制御装置
６  入出力装置
７  パケット検索処理装置
２１  パケット記憶装置
２２，７２  処理演算装置
３１，８１，９１  検索データ記憶装置
３２，８２，９２  検索処理演算装置
３３，７３，８３，９３  記録媒体
７１  パケット検索データ記憶装置
【図１】
2004172917.tif 000003
【図２】
2004172917.tif 000004
【図３】
2004172917.tif 000005
【図４】
2004172917.tif 000006
【図５】
2004172917.tif 000007
【図６】
2004172917.tif 000008
【図７】
2004172917.tif 000009
【図８】
2004172917.tif 000010
【図９】
2004172917.tif 000011
【図１０】
2004172917.tif 000012