(57)【特許請求の範囲】
【請求項１】
情報処理装置であって、
第１の検索対象データを登録する第１のメモリと、
前記第１の検索対象データと論理的に結合された第２の検索対象データを登録し、前記第１のメモリよりも高速に動作可能な第２のメモリと、
前記第１のメモリと前記第２のメモリのいずれか一方から、１つの検索対象データが検出されると探索処理を終了するモードである場合、検索対象データを、前記第２のメモリから前記第１のメモリへ順番に検索する第１の検索手段と、
前記第１のメモリと前記第２のメモリのいずれか一方から、１つの検索対象データが検出されても探索処理を終了しないモードである場合、検索対象データを、前記第２のメモリから検索することに並行して、前記第１のメモリから検索する第２の検索手段と、
前記第１の検索手段により、前記第１のメモリにおいて所定の検索対象データが検出された場合には、当該所定の検索対象データを前記第１のメモリから前記第２のメモリに移動させ、前記第２の検索手段により、前記第１のメモリにおいて所定の検索対象データが検出された場合には、当該所定の検索対象データを前記第１のメモリから前記第２のメモリに移動させない移動手段とを有することを特徴とする情報処理装置。
【請求項２】
前記第１の検索対象データ、および、前記第２の検索対象データは１つの検索テーブルに登録されていることを特徴とする請求項1に記載の情報処理装置。
【請求項３】
前記第１の検索手段により、前記第１のメモリにおいて所定の検索対象データが検出された場合、前記第２の検索対象データに含まれる少なくとも一部のデータと、前記所定の検索対象データとを入れ替える入替手段を更に有することを特徴とする請求項1または2に記載の情報処理装置。
【請求項４】
前記移動手段は、前記第１の検索手段により、前記第２のメモリにおいて所定の検索対象データが検出された場合、前記第２の検索対象データの先頭に、前記所定の検索対象データを移動させることを特徴とする請求項1または2に記載の情報処理装置。
【請求項５】
新たな検索対象データを登録する際に、前記第２のメモリに、新たな検索対象データを登録する空きがあるかを判定する判定手段と、
前記判定手段により、前記第２のメモリに空きがあると判定された場合には当該新たな検索対象データを前記第２のメモリに登録し、前記第２のメモリに空きがないと判定された場合には当該新たな検索対象データを前記第１のメモリに登録する登録手段とを更に有することを特徴とする請求項1から4の何れか一項に記載の情報処理装置。
【請求項６】
前記第２のメモリから前記第２の検索対象データの少なくとも一部のデータを削除する削除手段を更に有し、
前記削除手段によりデータが削除された場合、前記移動手段は、前記第１の検索対象データの少なくとも一部を前記第２のメモリに移動させることを特徴とする請求項1から5の何れか一項に記載の情報処理装置。
【請求項７】
第１の検索対象データを登録する第１のメモリと、前記第１の検索対象データと論理的に結合された第２の検索対象データを登録し、前記第１のメモリよりも高速に動作可能な第２のメモリとを有する情報処理装置の制御方法であって、
前記第１のメモリと前記第２のメモリのいずれか一方から、１つの検索対象データが検出されると探索処理を終了するモードである場合、検索対象データを、前記第２のメモリから前記第１のメモリへ順番に検索する第１の検索工程と、
前記第１のメモリと前記第２のメモリのいずれか一方から、１つの検索対象データが検出されても探索処理を終了しないモードである場合、検索対象データを、前記第２のメモリから検索することに並行して、前記第１のメモリから検索する第２の検索工程と、
前記第１の検索工程において、前記第１のメモリにおいて所定の検索対象データが検出された場合には、当該所定の検索対象データを前記第１のメモリから前記第２のメモリに移動させ、前記第２の検索工程において、前記第１のメモリにおいて所定の検索対象データが検出された場合には、当該所定の検索対象データを前記第１のメモリから前記第２のメモリに移動させない移動工程とを有することを特徴とする制御方法。
【請求項８】
コンピュータに請求項7に記載された制御方法を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索テーブルに登録されたデータの検索処理を行う情報処理に関する。
【背景技術】
【０００２】
近年、汎用コンピュータ(PC)のみならず、コンピュータ組込機器においてもネットワークプロトコル処理を高速に実行することが要求される。しかし、ソフトウェア処理によるギガビットイーサネット（登録商標）の充分な処理速度の達成は、コンピュータ組込機器が搭載するプロセッサの能力を遥かに超える。
【０００３】
そこで、TOE (TCP/IP offload engine)といったプロトコル処理に特化した補助的デバイスを付加して、プロセッサに頼らず、広帯域なネットワーク通信を実現することが一般化した。TCP/IPのプロトコル処理に特徴的な処理として、TCP処理におけるソケット検索やリッスン状態検索がある。また、IPsec処理におけるSPD (security policy database)検索やSAD (security association database)検索がある。また、IP処理におけるリアセンブル検索などもあり、様々な用途の検索を行う必要がある。
【０００４】
TCP/IPによる送信処理と受信処理を高速化するため、プロトコル処理における検索処理をCAM (content addressable memory)を用いて高速化する手法がある。しかし、CAMを利用した連想メモリは高価なため、その代替として、RAMを用いて逐次比較の結果を出力する方式の連想メモリが使用される。検索装置を利用した検索処理は、検索キーにより検索装置から該当アドレスを取得し、取得したアドレスを用いてデータの読み出し、書き込みを行う。
【０００５】
また、ネットワーク規模の増大に伴い、ソケット、SP (security policy)、SA (security association)などのエントリ数の上限を増加させる必要がある。しかし、エントリ数の上限の増加に比例して連想メモリの容量を増加させる必要があり、実装コストが増大する。そこで、検索テーブルの一部をDRAMなど外部メモリに格納し、オンチップ上のSRAMなど内部メモリに格納された検索テーブルと外部メモリに格納された検索テーブルを論理的に一つの検索テーブルとして構成して検索処理を行う。このように、メモリの実装コストの増加を抑えながら、登録可能な検索対象データのエントリ数を増やす手法がある。しかし、外部メモリのアクセスには時間がかかり、その結果、外部メモリに登録されたデータの検索に時間がかかる問題がある。
【０００６】
特許文献1は、外部メモリに対する検索処理を行うジョブ（以下、外部メモリ検索処理）と、内部メモリに対する検索処理を行うジョブ（以下、内部メモリ検索処理）を分けて検索処理を実行する。それにより、他の検索処理を行うジョブに与える遅延時間を削減して効率的な検索処理を行う技術を開示する。さらに、エントリデータが一つでも検索キーと一致すれば検索を終了するシングルヒットモードの場合、外部メモリ検索処理でヒットしたエントリと、内部メモリの任意のエントリを入れ替えて、連続するパケットの検索要求を効率的に処理する手法を提案する。
【０００７】
プロトコル処理における連続するパケットの検索は、同一のエントリがヒットする確率が高い。また、プロトコル処理における検索処理には、上記のシングルヒットモードと、すべてのエントリと検索キーを比較して一致するものをすべて選ぶ全検索モードがある。
【０００８】
特許文献1が開示する技術は、シングルヒットモードにおいて外部メモリ検索処理においてヒットしたエントリと、内部メモリの任意のエントリを入れ替えて、連続するパケットの検索要求を効率的に処理しようとする。しかし、シングルヒットモードの場合、すべてのジョブを内部メモリ検索処理と外部メモリ検索処理に分けて行えば、内部メモリ検索処理におけるヒット率が高く、内部メモリ検索処理におけるヒットに伴い、外部メモリ検索処理を終了する処理を行う必要がある。その結果、必ずしも効率的な検索処理にはならない問題がある。
【０００９】
さらに、検索ジョブキューの内部メモリ検索処理のジョブが終了した際、対応する外部メモリ検索ジョブキューのジョブを終了させるには、処理の複雑化と回路規模の増大が伴い、消費電力も増大させる問題がある。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開2011-040038号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐことを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１３】
本発明にかかる情報処理装置は、第１の検索対象データを登録する第１のメモリと、前記第１の検索対象データと論理的に結合された第２の検索対象データを登録し、前記第１のメモリよりも高速に動作可能な第２のメモリと、前記第１のメモリと前記第２のメモリのいずれか一方から、１つの検索対象データが検出されると探索処理を終了するモードである場合、検索対象データを、前記第２のメモリから前記第１のメモリへ順番に検索する第１の検索手段と、前記第１のメモリと前記第２のメモリのいずれか一方から、１つの検索対象データが検出されても探索処理を終了しないモードである場合、検索対象データを、前記第２のメモリから検索することに並行して、前記第１のメモリから検索する第２の検索手段と、前記第１の検索手段により、前記第１のメモリにおいて所定の検索対象データが検出された場合には、当該所定の検索対象データを前記第１のメモリから前記第２のメモリに移動させ、前記第２の検索手段により、前記第１のメモリにおいて所定の検索対象データが検出された場合には、当該所定の検索対象データを前記第１のメモリから前記第２のメモリに移動させない移動手段とを有することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐことができる。
【図面の簡単な説明】
【００１５】
【図１】実施例のコンピュータ機器の構成例を説明するブロック図。
【図２】通信部の構成例を説明するブロック図。
【図３】通信部のサブプロセッサの役割を説明する図。
【図４】検索部の構成例を説明するブロック図。
【図５】検索部の検索処理を説明するフローチャート。
【図６】シングルヒットモード検索処理を説明するフローチャート。
【図７】検索テーブルエントリの入替処理を説明するフローチャート。
【図８】全検索モード検索処理を説明するフローチャート。
【図９】登録処理を説明するフローチャート。
【図１０】削除処理を説明するフローチャート。
【発明を実施するための形態】
【００１６】
以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。
【００１７】
［装置の構成］
図1のブロック図により実施例のコンピュータ機器の構成例を説明する。なお、図1に示すコンピュータ機器はコンピュータ組込機器の一例である。
【００１８】
図1に示すコンピュータ機器の主プロセッサ101は、システムバス102を介して、後述する各構成に接続されている。なお、システムバス102は、英国ARM社が提唱するAMBA 3.0 AXI (Advanced eXtensible Interface)仕様に代表されるクロスバースイッチ構造のオンチップバスである。システムバス102は、コンピュータ機器に要求される送受信データの並行転送動作が可能である。
【００１９】
割込制御部401は、各構成や通信部105からの割込イベントを主プロセッサ101に伝達する。タイマ402は、ソフトウェアなどによって起動され、時間計測やタイムアウトイベントを発生する。汎用入出力(IO)インタフェイス409に接続された入力キー410は、コンピュータ機器の動作モードの設定や、IPアドレスに代表される各種通信パラメータを入力するため入力部である。表示制御部403に接続された表示部404は、コンピュータ機器の状態や設定内容などを表示するモニタである。
【００２０】
二次記憶制御部405に接続されたハードディスクドライブ(HDD)406は、コンピュータ機器の機能を実現するソフトウェアとその関連データ、および、各サブシステムのサブプロセッサが実行するファームウェアとその関連データなどを格納する。HDD406は、さらに、コンピュータ機器の動作履歴や通信履歴などの履歴情報を格納する。なお、コンピュータ機器の機能を実現するソフトウェアには、オペレーティングシステム(OS)、コンピュータ機器の各機能を実現するアプリケーションプログラムやアプリケーションプロトコル、周辺機器を制御するためのデバイスドライバなどが含まれる。
【００２１】
主メモリ制御部103に接続された主メモリ104は、RAMであり、主プロセッサのワークメモリとして機能する。つまり、主プロセッサ101は、HDD406に格納されたソフトウェアを主メモリ104にロードして、OSやアプリケーションプログラムを実行する。
【００２２】
メモリ制御部412に接続されたNVRAM413は、書換可能な不揮発性メモリであり、コンピュータ機器の起動時に動作するブートプログラムやコンピュータ機器の初期状態の設定に必要なパラメータなどが格納される。NVRAM413は、さらに、コンピュータ機器の起動時に各構成を制御するためのデバイスドライバや各構成の起動時に設定するパラメータなどを格納する。
【００２３】
通信部105は、コンピュータ機器を有線ネットワーク136に接続する。無線LANサブシステム408は、コンピュータ機器をIEEE802.11a/b/g/n規格に準拠する無線ネットワークに接続する。汎用バスインタフェイス411は、コンピュータ機器をUSBやIEEE1394などのシリアルバスに接続する。なお、後述するように、通信部105は、パケット情報処理検索テーブルを用いて、パケットの検索要求に対する検索処理などのプロトコル処理を行うTOEサブシステム（情報処理装置）として機能する。
【００２４】
コンピュータ機器の電源が投入されると、主プロセッサ101は、NVRAM413に格納されたブートプログラムを実行し、上記の各構成を初期化する。そして、HDD406に格納されたソフトウェアを主メモリ104にロードして、OSやアプリケーションプログラムを実行する。また、主プロセッサ101は、サブシステムの初期化時、通信部105が内蔵する後述する複数のサブプロセッサがそれぞれ実行するファームウェアを主メモリ104にロードして、各サブプロセッサを起動する。各サブプロセッサは、主メモリ104にロードされた対応するファームウェアを内蔵する命令キャッシュメモリにロードして、ファームウェアを実行する。
【００２５】
［通信部］
図2のブロック図により通信部105の構成例を説明する。
【００２６】
バスブリッジ116は、通信部105の内部バスであるサブシステムバス123とシステムバス102を接続する。なお、サブシステムバス123はクロスバースイッチ接続である。通信部105は五つのサブプロセッサ111〜115を内蔵し、これらサブプロセッサによるマルチプロセッサ処理により、主システムからオフロードしたTCP/IPのプロトコル処理を高速に実行する。共有メモリ125は、サブプロセッサ111〜115間の通信と情報共有のためのメモリである。通信タイマ124は、プロトコル処理に必要な時間計測およびタイムアウトイベントを発生する。
【００２７】
通信部105は、有線ネットワーク136に接続するためのハードウェアとしてPHY134とMAC (media access controler)133を備える。PHY134は、OSI参照モデルの物理層（第一層）のプロトコル処理と電気信号を扱う。MAC133は、OSI参照モデルのデータリンク層（第二層）の下位副層に相当するMAC層のプロトコルを処理する。
【００２８】
データパス制御部132は、受信パケットデータと送信パケットデータを、例えば、主メモリ104または共有メモリ125とMAC133の間でDMA転送する機能を有する。データパス制御部132は、転送処理中にパケットデータのチェックサム演算を行う。検索部122は、連想メモリを有し、サブプロセッサの要求に応じて、プロトコル処理の様々な管理情報の格納と検索処理を行う情報処理装置（コンピュータ装置）である。
【００２９】
通信部105は、暗号通信プロトコル（IPsec、SSL、TLSなど）処理を実行し、そのために鍵管理部126、乱数発生器127、暗号器129を有する。鍵管理部126は、生成した暗号鍵、乱数、素数を機密に保持する。乱数発生器127は、暗号処理に必要な乱数値を生成する。暗号器129はAES暗号器であり、さらに、認証やディジタル署名などに使われるSHA-1やRFC1321として標準化されているMD5などのハッシュ関数を発生する。
【００３０】
●サブプロセッサ
図3により通信部105のサブプロセッサ111〜115の役割を説明する。TCP/IPプロトコル処理は、アプリケーション層501、ソケットAPI502、トランスポート層（TCP/UDP層）503、インターネット層（IP層）504、MACドライバ505、MAC層506、PHY層507の階層構造を有す。
【００３１】
通信部105は、インターネットプロトコル(IP)を処理するIP層504の処理機能、並びに、転送制御プロトコル(TCP)およびユーザデータグラムプロトコル(UDP)を処理するTCP/UDP層503の処理機能を有する。さらに、MAC層506との間で通信データと通信情報を交換するMACドライバ505の機能、並びに、アプリケーション通信のインタフェイスIであるソケットAPI502の一部機能を有する。通信部105は、これら機能を各サブプロセッサに分散して処理を行う。
【００３２】
例えば、ソケットAPI502の処理をサブプロセッサ111に割り当てる。TCPとUDPの処理のうち受信動作515に関わる処理をサブプロセッサ112に割り当て、送信動作516に関わる処理をサブプロセッサ113に割り当てる。MACドライバ505とIPの処理のうち受信動作515に関わる処理をサブプロセッサ114に割り当て、送信動作516に関わる処理をサブプロセッサ115に割り当てる。このように処理を分散する意図は、一連のプロトコル処理を三つのパイプラインステージ511〜513に分割し、パイプライン動作を行うことにある。また、送信動作516と受信動作515を分けることで、それぞれの機能を分担するサブプロセッサ同士を並列的に動作させる。
【００３３】
各サブプロセッサ間の処理データの伝達と制御情報の共有は共有メモリ125を介して行われる。例えば、TCPは転送データの到達保証を行う観点から、受信側から送信側に対して、確認応答と称する到達確認情報をコネクション間で伝達する。この確認応答を行うには、サブプロセッサ112とサブプロセッサ113との間で確認応答の伝達514が必要になる。このようなTCPの制御情報の伝達は共有メモリ125を介して行われる。なお、サブプロセッサ間における到達確認情報の伝達と制御情報の共有は主メモリ104を用いて行ってもよい。
【００３４】
●検索部
サブプロセッサは、プロトコル処理における処理を検索部122に要求し、処理要求とともに処理の種類などを示すパラメータを検索部122に供給する。検索処理の種類には第一の検索モードであるシングルヒットモード検索、第二の検索モードである全検索モード検索、データ登録、および、データ削除が含まれる。また、検索処理に関するパラメータには検索モード、検索キー、登録または削除すべきデータなどが含まれる。
【００３５】
検索部122は、データ検索を要求されると、読出処理と比較処理によってデータの検索処理を実行し、検索結果を要求元のサブプロセッサに返す。検索モードには、上述したようにシングルヒットモードと全検索モードがある。なお、全検索モードにおいては、複数のエントリデータにヒットする可能性がある。
【００３６】
検索部122は、データ登録が要求されるとパラメータに含まれるデータを検索テーブルへ登録し、データ削除が要求されるとパラメータに含まれるデータに対応するエントリデータを検索テーブルから削除する。
【００３７】
図4のブロック図により検索部122の構成例を説明する。検索処理入力部201は、サブプロセッサから処理要求を入力する。検索ジョブキュー202は、検索処理入力部201が入力した処理要求に対応するジョブのキューイング手段として機能する。なお、検索部122は、処理要求に対応するジョブをキューイングせずに一つずつ実行してもよい。
【００３８】
モード判別部203は、ジョブを解析し、上述した処理の種類を判別する。検索制御部204は、判別された種類の検索処理の実行を制御する。つまり、モード判別部203は、検索制御部204の指示に従い検索ジョブキュー202から検索ジョブを取り出し、検索ジョブの内容を判別して、検索制御部204に検索モード、検索キー、データなどのパラメータを渡す。
【００３９】
内部メモリテーブル206は、検索部122の内部メモリに配置され、検索対象のエントリデータを格納する。なお、内部メモリの代わりに共有メモリ125に内部メモリテーブル206を配置してもよい。内部メモリ検索部205は、内部メモリに対する検索処理を行い、内部メモリテーブル206からエントリデータを読み出し、読み出したエントリデータと検索キーを比較する一連の検索処理を行う第一の検索部である。
【００４０】
外部メモリテーブル208は、検索対象のエントリデータを格納する。外部メモリテーブル208は、例えば主メモリ104の所定領域に割り当てられる。外部メモリ検索部207は、外部メモリテーブル208に対する検索処理を行い、外部メモリテーブル208からエントリデータを読み出し、読み出したエントリデータと検索キーを比較する一連の検索処理を行う第二の検索部である。
【００４１】
つまり、内部メモリテーブル206と外部メモリテーブル208の組み合わせによってパケット情報処理検索テーブルが構成される。
【００４２】
検索処理の一連の動作は、内部メモリ検索部205と外部メモリ検索部207によって行われる。しかし、内部メモリ検索処理と外部メモリ検索処理が並列に実行可能であれば、両処理を行う一つの構成によって検索処理の一連の動作を行ってもよいし、複数の構成を有してもよい。あるいは、内部メモリ検索処理と外部メモリ検索処理を時分割で行う一つの構成としてもよい。
【００４３】
検索制御部204は、検索結果通知部209を介して、検索処理の要求元のサブプロセッサに検索結果を通知する。さらに、検索設定部210は、検索部122に対する設定情報を与える手段として機能する。つまり、検索部122の初期化時、主プロセッサ101は、検索設定部210に対し、最大エントリ数や外部メモリテーブル208を保持する主メモリ104のアドレス空間を設定するなどの処理を行う。なお、エントリ数と外部メモリテーブルのアドレス空間についてソフトウェアにより柔軟に設定が可能な構成例を説明したが、エントリ数や外部メモリテーブルのアドレス空間は予め固定されていてもよい。
【００４４】
［検索処理］
図5のフローチャートにより検索部122の検索処理を説明する。
【００４５】
サブプロセッサによって検索処理の要求が所定のレジスタに書き込まれると、検索処理入力部201は、検索処理の要求を入力して、対応する検索ジョブを検索ジョブキュー202にキューイングする(S301)。
【００４６】
モード判別部203は、検索ジョブのキューイングを検知すると、検索制御部204が検索処理中か否かを調べ(S302)、検索処理中の場合は検索処理が終了するまで待機する。検索処理中ではない、または、検索処理が終了すると、モード判別部203は、検索ジョブキュー202から検索ジョブを取り出し(S303)、検索処理の種類を判別する。
【００４７】
検索処理の種類がデータ登録の場合(S304)、検索制御部204はデータの登録処理を行う(S305)。検索処理の種類がデータ削除の場合(S306)、検索制御部204はエントリデータの削除処理を行う(S307)。検索処理の種類がシングルヒットモード検索の場合(S308)、検索制御部204はシングルヒットモード検索処理を行う(S309)。検索処理の種類が全検索モード検索の場合(S310)、検索制御部204は全検索モード検索処理を行う(S311)。
【００４８】
検索処理の種類が何れにも該当しない場合、モード判別部203は、検索制御部204に検索処理の指定エラーを出力する(S312)。検索制御部204は、各処理の終了後、検索結果通知部209を介して、処理結果を検索処理の要求元のサブプロセッサに通知する(S313)。
【００４９】
なお、図5に示す検索部122の処理フローは一例であり、検索処理の実行前に処理内容を判別し、判別結果に基づき検索処理を実行する手順であればよい。
【００５０】
●シングルヒットモード検索処理
図6のフローチャートによりシングルヒットモード検索処理(S309)を説明する。
【００５１】
検索制御部204は、内部メモリ検索部205にシングルヒットモード検索処理を開始させる。内部メモリ検索部205は、内部メモリテーブル206からエントリを読み出し、検索キーと比較する(S601)。内部メモリ検索部205は、比較の結果、検索がヒット（検索キーに対応するデータを検出）したか否かを判定し(S602)、ヒットした場合は処理をステップS609に進め、ヒットしなかった場合は処理をステップS603に進める。
【００５２】
検索がヒットしなかった場合、内部メモリ検索部205は、内部メモリテーブル206の全エントリとの比較を行ったか否かを判定し(S603)、全エントリとの比較が未了の場合は処理をステップS601に戻す。また、内部メモリ検索部205が全エントリとの比較を完了したと判定した場合、検索制御部204は、内部メモリ検索部205の検索処理を終了し、処理をステップS604に進める。つまり、内部メモリテーブル206の全エントリとの比較が完了するか、検索にヒットするエントリが見付かるまでステップS601、S602、S603が繰り返される。
【００５３】
検索がヒットせずに、内部メモリテーブル206の全エントリとの比較が完了すると、検索制御部204は、登録エントリ数を参照して、外部メモリテーブル208にエントリがあるか否かを判定する(S604)。外部メモリテーブル208にエントリがない場合は処理をステップS608へ進める。
【００５４】
外部メモリテーブル208にエントリがある場合、検索制御部204は、外部メモリ検索部207にシングルヒットモード検索処理を開始させる。外部メモリ検索部207は、外部メモリテーブル208からエントリを読み出し、検索キーと比較する(S605)。外部メモリ検索部207は、比較の結果、検索がヒットしたか否かを判定し(S606)、ヒットした場合は処理をステップS609に進め、ヒットしなかった場合は処理をステップS607に進める。
【００５５】
検索がヒットしなかった場合、外部メモリ検索部207は、外部メモリテーブル208の全エントリとの比較を行ったか否かを判定し(S607)、全エントリとの比較が未了の場合は処理をステップS605に戻す。また、外部メモリ検索部207が全エントリとの比較を完了したと判定した場合、検索制御部204は、外部メモリ検索部207の検索処理を終了し、処理をステップS608に進める。つまり、外部メモリテーブル208の全エントリとの比較が完了するか、検索にヒットするエントリが見付かるまでステップS605、S606、S607が繰り返される。
【００５６】
外部メモリテーブル208にエントリがない、または、外部メモリテーブル208の全エントリとの比較が完了すると、検索制御部204は、検索結果として「ミスヒット」を要求元のサブプロセッサに通知する(S608)。そして、シングルヒットモード検索処理を終了する。
【００５７】
一方、検索がヒットした場合、検索制御部204は、ヒットしたエントリIDを一時保存し(S609)、検索テーブルエントリの入替処理を行う(S610)。そして、検索結果「ヒット」と、ヒットしたエントリIDを要求元のサブプロセッサに通知し(S611)、シングルヒットモード検索処理を終了する。
【００５８】
●検索テーブルエントリの入替処理
図7のフローチャートにより検索テーブルエントリの入替処理(S610)を説明する。
【００５９】
検索制御部204は、外部メモリテーブル208のエントリがヒットしたか否かを判定する(S701)。外部メモリテーブル208のエントリがヒットした場合は、ヒットしたエントリと内部メモリテーブル206の任意のエントリを入れ替える（第一の入替）(S702)。内部メモリテーブル206の任意のエントリは、先頭を除いたラウンドロビンで管理され、外部メモリテーブル208のエントリとの入れ替えが行われる度に選択されるエントリ（入替対象のエントリ）が更新される。
【００６０】
なお、入替対象のエントリは、内部メモリテーブル206の先頭エントリでもよいし、使われてから最も長い時間が経ったエントリをLRU (least recently used)などの任意のアルゴリズムを用いて選択してもよい。
【００６１】
また、内部メモリテーブル206のエントリがヒットした場合、検索制御部204は、ヒットしたエントリが内部メモリテーブル206の先頭エントリか否かを判定し(S703)、先頭エントリの場合は入替処理を終了する。また、先頭エントリではない場合、ヒットしたエントリと内部メモリテーブル206の先頭エントリを入れ替える（第二の入替）(S704)。
【００６２】
内部メモリテーブル206のエントリがヒットした場合、検索テーブルエントリの入れ替えは行わずに、次回の検索をヒットした内部メモリテーブル206のエントリから始める方式でもよい。また、先頭エントリからではなく、複数のエントリグループから優先的に検索を行ってもよい。
【００６３】
なお、検索テーブルエントリの入替処理は、内部メモリテーブル206と外部メモリテーブル208にエントリを配置して、論理的に一つの検索テーブル（パケット処理情報検索テーブル）を構成することができる手順であればよい。
【００６４】
●全検索モード検索処理
図8のフローチャートにより全検索モード検索処理(S311)を説明する。
【００６５】
検索制御部204は、内部メモリ検索部205と外部メモリ検索部207に全検索モード検索処理を開始させる。内部メモリ検索部205は、内部メモリテーブル206からエントリを読み出して検索キーとの比較を行い、外部メモリ検索部207は、外部メモリテーブル208からエントリを読み出して検索キーとの比較を行う(S801)。
【００６６】
内部メモリ検索部205と外部メモリ検索部207は、検索がヒットしたか否かを判定し(S802)、ヒットした場合はヒットしたエントリIDを保存し、ヒットしたエントリの数をカウントする(S803)。そして、内部メモリテーブル206の全エントリとの比較、および、外部メモリテーブル208の全エントリとの比較を行ったか否かを判定する(S804)。このように、内部メモリ検索部205と外部メモリ検索部207は、並列的に、全エントリとの比較が終了するまで、ステップS801からS804の処理を繰り返し継続する。
【００６７】
全エントリとの比較が終了すると、検索制御部204は、ヒットしたエントリがあるか否かを判定し(S805)、ヒットしたエントリがあればヒットしたエントリIDとヒットしたエントリ数を要求元のサブプロセッサに通知する(S806)。また、ヒットしたエントリがない場合はヒット数がゼロである旨を要求元のサブプロセッサに通知する(S807)。そして、全検索モード検索処理を終了する。
【００６８】
●登録処理
図9のフローチャートにより登録処理(S305)を説明する。
【００６９】
検索制御部204は、内部メモリテーブル206を格納する内部メモリに空きがあるか否かを判定する(S901)。内部メモリに空きがあれば、内部メモリ検索部205を介して、登録を要求されたデータ（以下、対象データ）を内部メモリテーブル206に登録（追加）する(S902)。また、内部メモリに空きがない場合、外部メモリテーブル208を格納する外部メモリに空きがあるか否かを判定する(S903)。外部メモリに空きがあれば、外部メモリ検索部207を介して、対象データを外部メモリテーブル208に登録（追加）する(S904)。
【００７０】
対象データの登録に成功すると、検索制御部204は、登録エントリ数のカウント値をインクリメントし(S905)、登録に成功した旨を要求元のサブプロセッサに通知する(S906)。また、内部メモリと外部メモリに空きがなかった場合、検索制御部204は、登録に失敗した旨を表すエラー通知を要求元のサブプロセッサに通知する(S907)。そして、登録処理を終了する。
【００７１】
なお、登録処理は、内部メモリテーブル206と外部メモリテーブル208にエントリを配置して、論理的に一つの検索テーブル（パケット処理情報検索テーブル）を構成することができる手順であればよい。
【００７２】
●削除処理
図10のフローチャートにより削除処理(S307)を説明する。
【００７３】
検索制御部204は、内部メモリ検索部205を介して、削除が要求されたエントリデータ（以下、対象データ）が内部メモリテーブル206に登録されているか否かを判定する(S1001)。そして、対象データが内部メモリテーブル206に登録されている場合は処理をステップS1004に進める。また、対象データが内部メモリテーブル206に登録されていない場合は、外部メモリ検索部207を介して、対象データが外部メモリテーブル208に登録されているか否かを判定する(S1002)。そして、対象データが外部メモリテーブル208にも登録されていない場合は削除処理の「指定エラー」を要求元のサブプロセッサに通知し(S1003)、削除処理を終了する。
【００７４】
対象データが内部メモリテーブル206に登録されている場合、検索制御部204は、外部メモリテーブル208にエントリがあるか否かを判定する(S1004)。外部メモリテーブル208にエントリがない場合は、内部メモリ検索部205を介して、内部メモリテーブル206から対象データに対応するエントリを削除する(S1005)。また、外部メモリテーブル208にエントリがある場合は、内部メモリ検索部205および外部メモリ検索部207を介して、外部メモリテーブル208の最終エントリデータを、内部メモリテーブルの対象データに対応するエントリに登録する(S1006)。言い替えれば、対象データのエントリを外部メモリテーブル208の最後に登録されたデータ（最終エントリデータ）で置き換える。
【００７５】
対象データが外部メモリテーブル208に登録されている場合、検索制御部204は、外部メモリ検索部207を介して、対象データが外部メモリテーブル208の最終エントリか否かを判定する(S1007)。対象データが最終エントリではない場合、外部メモリ検索部207を介して、外部メモリテーブル208の最終エントリデータを、外部メモリテーブル208の対象データに対応するエントリに登録する(S1008)。言い替えれば、対象データのエントリを外部メモリテーブル208の最終エントリで置き換える。
【００７６】
次に、検索制御部204は、登録エントリ数のカウント値をデクリメントし(S1009)、削除に成功した旨を要求元のサブプロセッサに通知して(S1010)、削除処理を終了する。
【００７７】
なお、削除処理は、内部メモリテーブル206と外部メモリテーブル208にエントリを配置して、論理的に一つの検索テーブル（パケット処理情報検索テーブル）を構成することができる手順であればよい。
【００７８】
また、内部メモリテーブル206のエントリを削除する場合、内部メモリテーブル206へ移動する外部メモリテーブル208のエントリは任意のエントリにすることができる。その場合、外部メモリテーブル208の最終エントリを、内部メモリテーブル206に移動したエントリに移動すると効率的な検索が可能になる。
【００７９】
このように、検索処理に先立ち、要求された検索処理の種類を判別し、全検索モード検索の場合は内部メモリ検索処理と外部メモリ検索処理を並列的に実行する。また、シングルヒットモード検索の場合は、内部メモリ検索処理、外部メモリ検索処理の順に検索処理を逐次的に実行する。
【００８０】
つまり、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合、並列的な検索処理により全検索モードにおける検索性能の低下を抑える。
【００８１】
また、シングルヒットモード検索においては、逐次的な検索処理により、低速な外部メモリよりも高速な内部メモリの検索を優先して、検索処理性能を最大限に発揮することができる。その際、同一のエントリがヒットする確率が高いプロトコル処理における連続するパケットのシングルヒットモード検索において、内部メモリの検索を優先することで、外部メモリの検索処理を終了させるための処理の実行回数を削減することができる。その結果、不要な処理と複雑な処理を避けることができ、処理の複雑化と回路規模の増大を防ぎ、消費電力の増大も防ぐことができる。
【００８２】
また、外部メモリに登録されたエントリが連続するパケットの検索対象エントリである場合、遅延時間の削減が可能になり、検索処理を効率化を図ることができる。
【００８３】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【図１】
0005967967.tif 000002
【図２】
0005967967.tif 000003
【図３】
0005967967.tif 000004
【図４】
0005967967.tif 000005
【図５】
0005967967.tif 000006
【図６】
0005967967.tif 000007
【図７】
0005967967.tif 000008
【図８】
0005967967.tif 000009
【図９】
0005967967.tif 000010
【図１０】
0005967967.tif 000011