図面 (/)

技術 情報処理装置およびその制御方法

出願人 キヤノン株式会社
発明者 深田昌敬
出願日 2012年2月13日 (8年1ヶ月経過) 出願番号 2012-028860
公開日 2013年8月22日 (6年7ヶ月経過) 公開番号 2013-164814
状態 特許登録済
技術分野 検索装置
主要キーワード サブシステムバス 最大エントリ数 通信タイマ 並行転送 検索ジョブ リアセンブル オンチップバス LRU
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2013年8月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (11)

課題

内部メモリ外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐ。

解決手段

検索制御部204は、内部メモリに配置された内部メモリテーブル206、および、外部メモリに配置された外部メモリテーブル208から構成される論理的に一つの検索テーブルに登録されたデータの検索処理を行う。内部メモリ検索部205は、内部メモリテーブル206に登録されたデータの検索処理を行う。外部メモリ検索部207は、外部メモリテーブル208に登録されたデータの検索処理を行う。検索制御部204は、要求される検索モードに応じて、内部メモリ検索部205による検索処理と外部メモリ検索部207による検索処理を並列的または逐次的に実行する。

概要

背景

近年、汎用コンピュータ(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が開示する技術は、シングルヒットモードにおいて外部メモリ検索処理においてヒットしたエントリと、内部メモリの任意のエントリを入れ替えて、連続するパケットの検索要求を効率的に処理しようとする。しかし、シングルヒットモードの場合、すべてのジョブを内部メモリ検索処理と外部メモリ検索処理に分けて行えば、内部メモリ検索処理におけるヒット率が高く、内部メモリ検索処理におけるヒットに伴い、外部メモリ検索処理を終了する処理を行う必要がある。その結果、必ずしも効率的な検索処理にはならない問題がある。

さらに、検索ジョブキューの内部メモリ検索処理のジョブが終了した際、対応する外部メモリ検索ジョブキューのジョブを終了させるには、処理の複雑化と回路規模の増大が伴い、消費電力も増大させる問題がある。

概要

内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐ。検索制御部204は、内部メモリに配置された内部メモリテーブル206、および、外部メモリに配置された外部メモリテーブル208から構成される論理的に一つの検索テーブルに登録されたデータの検索処理を行う。内部メモリ検索部205は、内部メモリテーブル206に登録されたデータの検索処理を行う。外部メモリ検索部207は、外部メモリテーブル208に登録されたデータの検索処理を行う。検索制御部204は、要求される検索モードに応じて、内部メモリ検索部205による検索処理と外部メモリ検索部207による検索処理を並列的または逐次的に実行する。 4

目的

本発明は、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐことを目的とする

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

装置の内部メモリに配置された内部メモリテーブル、および、前記装置の外部にある外部メモリに配置された外部メモリテーブルから構成される論理的に一つの検索テーブル登録されたデータの検索処理を行う情報処理装置であって、前記内部メモリテーブルに登録されたデータの検索処理を行う第一の検索手段と、前記外部メモリテーブルに登録されたデータの検索処理を行う第二の検索手段と、前記検索テーブルから一つのデータが検出されると前記検索処理を終了する第一の検索モードか、前記検索テーブルから一つのデータが検出されても前記検索処理を継続する第二の検索モードかに基づいて、前記第一の検索手段による検索処理と前記第二の検索手段による検索処理を並列的または逐次的に実行する制御手段とを有することを特徴とする情報処理装置。

請求項2

前記制御手段は、前記検索モードが前記第一の検索モードの場合、前記第一の検索手段による検索処理、前記第二の検索手段による検索処理の順に逐次的に検索処理を実行することを特徴とする請求項1に記載された情報処理装置。

請求項3

前記制御手段は、前記外部メモリテーブルに登録された所定のデータを検出して前記検索処理が終了した場合、前記内部メモリテーブルに登録された任意のデータを前記所定のデータで置き換えることを特徴とする請求項1または請求項2に記載された情報処理装置。

請求項4

前記制御手段は、前記内部メモリテーブルに登録された所定のデータを検出して前記検索処理が終了した場合、前記内部メモリテーブルの先頭に登録されたデータを前記所定のデータで置き換えることを特徴とする請求項1または請求項2に記載された情報処理装置。

請求項5

前記制御手段は、前記検索モードが前記第二の検索モードの場合、前記第一の検索手段による検索処理と前記第二の検索手段による検索処理を並列的に実行することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。

請求項6

さらに、処理要求を入力する入力手段、および、前記処理要求の種類を判別する判別手段を有し、前記制御手段は、前記処理要求の種類がデータ検索に対応する場合、前記第一および第二の検索手段により前記並列的または逐次的な検索処理を実行することを特徴とする請求項1から請求項5の何れか一項に記載された情報処理装置。

請求項7

前記制御手段は、前記処理要求の種類がデータ登録に対応する場合、前記内部メモリに空きがあれば登録すべきデータを前記内部メモリテーブルに登録し、前記内部メモリに空きがなければ前記登録すべきデータを前記外部メモリテーブルに登録することを特徴とする請求項6に記載された情報処理装置。

請求項8

前記制御手段は、前記処理要求の種類がデータ削除に対応し、削除すべきデータが前記内部メモリテーブルに登録されている場合、前記削除すべきデータに対応する前記内部メモリテーブルのデータを前記外部メモリテーブルの最後に登録されたデータで置き換えることを特徴とする請求項6または請求項7に記載された情報処理装置。

請求項9

前記制御手段は、前記削除すべきデータが前記外部メモリテーブルに登録されている場合、前記削除すべきデータに対応する前記外部メモリテーブルのデータを前記外部メモリテーブルの最後に登録されたデータで置き換えることを特徴とする請求項8に記載された情報処理装置。

請求項10

装置の内部メモリに配置された内部メモリテーブル、および、前記装置の外部にある外部メモリに配置された外部メモリテーブルから構成される論理的に一つの検索テーブルに登録されたデータの検索処理を行う情報処理装置の制御方法であって、前記内部メモリテーブルに登録されたデータの検索処理を行う第一の検索手段、および、前記外部メモリテーブルに登録されたデータの検索処理を行う第二の検索手段を用いて前記検索処理を行い、前記検索テーブルから一つのデータが検出されると前記検索処理を終了する第一の検索モードか、前記検索テーブルから一つのデータが検出されても前記検索処理を継続する第二の検索モードかに基づいて、前記第一の検索手段による検索処理と前記第二の検索手段による検索処理を並列的または逐次的に実行することを特徴とする制御方法。

請求項11

コンピュータ装置に請求項10に記載された制御を実行させるためのプログラム

技術分野

0001

本発明は、検索テーブル登録されたデータの検索処理を行う情報処理に関する。

背景技術

0002

近年、汎用コンピュータ(PC)のみならず、コンピュータ組込機器においてもネットワークプロトコル処理を高速に実行することが要求される。しかし、ソフトウェア処理によるギガビットイーサネット(登録商標)の充分な処理速度の達成は、コンピュータ組込機器が搭載するプロセッサ能力を遥かに超える。

0003

そこで、TOE (TCP/IP offload engine)といったプロトコル処理特化した補助デバイスを付加して、プロセッサに頼らず、広帯域ネットワーク通信を実現することが一般化した。TCP/IPのプロトコル処理に特徴的な処理として、TCP処理におけるソケット検索リッスン状態検索がある。また、IPsec処理におけるSPD (security policy database)検索やSAD (security association database)検索がある。また、IP処理におけるリアセンブル検索などもあり、様々な用途の検索を行う必要がある。

0004

TCP/IPによる送信処理受信処理を高速化するため、プロトコル処理における検索処理をCAM(content addressable memory)を用いて高速化する手法がある。しかし、CAMを利用した連想メモリは高価なため、その代替として、RAMを用いて逐次比較の結果を出力する方式の連想メモリが使用される。検索装置を利用した検索処理は、検索キーにより検索装置から該当アドレスを取得し、取得したアドレスを用いてデータの読み出し、書き込みを行う。

0005

また、ネットワーク規模の増大に伴い、ソケット、SP (security policy)、SA (security association)などのエントリ数の上限を増加させる必要がある。しかし、エントリ数の上限の増加に比例して連想メモリの容量を増加させる必要があり、実装コストが増大する。そこで、検索テーブルの一部をDRAMなど外部メモリに格納し、オンチップ上のSRAMなど内部メモリに格納された検索テーブルと外部メモリに格納された検索テーブルを論理的に一つの検索テーブルとして構成して検索処理を行う。このように、メモリの実装コストの増加を抑えながら、登録可能な検索対象データのエントリ数を増やす手法がある。しかし、外部メモリのアクセスには時間がかかり、その結果、外部メモリに登録されたデータの検索に時間がかかる問題がある。

0006

特許文献1は、外部メモリに対する検索処理を行うジョブ(以下、外部メモリ検索処理)と、内部メモリに対する検索処理を行うジョブ(以下、内部メモリ検索処理)を分けて検索処理を実行する。それにより、他の検索処理を行うジョブに与える遅延時間を削減して効率的な検索処理を行う技術を開示する。さらに、エントリデータが一つでも検索キーと一致すれば検索を終了するシングルヒットモードの場合、外部メモリ検索処理でヒットしたエントリと、内部メモリの任意のエントリを入れ替えて、連続するパケット検索要求を効率的に処理する手法を提案する。

0007

プロトコル処理における連続するパケットの検索は、同一のエントリがヒットする確率が高い。また、プロトコル処理における検索処理には、上記のシングルヒットモードと、すべてのエントリと検索キーを比較して一致するものをすべて選ぶ全検索モードがある。

0008

特許文献1が開示する技術は、シングルヒットモードにおいて外部メモリ検索処理においてヒットしたエントリと、内部メモリの任意のエントリを入れ替えて、連続するパケットの検索要求を効率的に処理しようとする。しかし、シングルヒットモードの場合、すべてのジョブを内部メモリ検索処理と外部メモリ検索処理に分けて行えば、内部メモリ検索処理におけるヒット率が高く、内部メモリ検索処理におけるヒットに伴い、外部メモリ検索処理を終了する処理を行う必要がある。その結果、必ずしも効率的な検索処理にはならない問題がある。

0009

さらに、検索ジョブキューの内部メモリ検索処理のジョブが終了した際、対応する外部メモリ検索ジョブキューのジョブを終了させるには、処理の複雑化と回路規模の増大が伴い、消費電力も増大させる問題がある。

先行技術

0010

特開2011-040038号公報

発明が解決しようとする課題

0011

本発明は、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐことを目的とする。

課題を解決するための手段

0012

本発明は、前記の目的を達成する一手段として、以下の構成を備える。

0013

本発明にかかる情報処理は、装置の内部メモリに配置された内部メモリテーブル、および、前記装置の外部にある外部メモリに配置された外部メモリテーブルから構成される論理的に一つの検索テーブルに登録されたデータの検索処理を行う際に、前記内部メモリテーブルに登録されたデータの検索処理を行う第一の検索手段、および、前記外部メモリテーブルに登録されたデータの検索処理を行う第二の検索手段を用いて前記検索処理を行い、前記検索テーブルから一つのデータが検出されると前記検索処理を終了する第一の検索モードか、前記検索テーブルから一つのデータが検出されても前記検索処理を継続する第二の検索モードかに基づいて、前記第一の検索手段による検索処理と前記第二の検索手段による検索処理を並列的または逐次的に実行することを特徴とする。

発明の効果

0014

本発明によれば、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合に生じる検索処理性能の低下を防ぐことができる。

図面の簡単な説明

0015

実施例のコンピュータ機器の構成例を説明するブロック図。
通信部の構成例を説明するブロック図。
通信部のサブプロセッサ役割を説明する図。
検索部の構成例を説明するブロック図。
検索部の検索処理を説明するフローチャート
シングルヒットモード検索処理を説明するフローチャート。
検索テーブルエントリの入替処理を説明するフローチャート。
全検索モード検索処理を説明するフローチャート。
登録処理を説明するフローチャート。
削除処理を説明するフローチャート。

実施例

0016

以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。

0017

[装置の構成]
図1のブロック図により実施例のコンピュータ機器の構成例を説明する。なお、図1に示すコンピュータ機器はコンピュータ組込機器の一例である。

0018

図1に示すコンピュータ機器の主プロセッサ101は、システムバス102を介して、後述する各構成に接続されている。なお、システムバス102は、英国ARM社が提唱するAMBA 3.0 AXI (Advanced eXtensible Interface)仕様に代表されるクロスバースイッチ構造のオンチップバスである。システムバス102は、コンピュータ機器に要求される送受信データの並行転送動作が可能である。

0019

割込制御部401は、各構成や通信部105からの割込イベントを主プロセッサ101に伝達する。タイマ402は、ソフトウェアなどによって起動され、時間計測タイムアウトイベントを発生する。汎用入出力(IO)インタフェイス409に接続された入力キー410は、コンピュータ機器の動作モードの設定や、IPアドレスに代表される各種通信パラメータを入力するため入力部である。表示制御部403に接続された表示部404は、コンピュータ機器の状態や設定内容などを表示するモニタである。

0020

二次記憶制御部405に接続されたハードディスクドライブ(HDD)406は、コンピュータ機器の機能を実現するソフトウェアとその関連データ、および、各サブシステムのサブプロセッサが実行するファームウェアとその関連データなどを格納する。HDD406は、さらに、コンピュータ機器の動作履歴通信履歴などの履歴情報を格納する。なお、コンピュータ機器の機能を実現するソフトウェアには、オペレーティングシステム(OS)、コンピュータ機器の各機能を実現するアプリケーションプログラムアプリケーションプロトコル周辺機器を制御するためのデバイスドライバなどが含まれる。

0021

主メモリ制御部103に接続された主メモリ104は、RAMであり、主プロセッサのワークメモリとして機能する。つまり、主プロセッサ101は、HDD406に格納されたソフトウェアを主メモリ104にロードして、OSやアプリケーションプログラムを実行する。

0022

メモリ制御部412に接続されたNVRAM413は、書換可能な不揮発性メモリであり、コンピュータ機器の起動時に動作するブートプログラムやコンピュータ機器の初期状態の設定に必要なパラメータなどが格納される。NVRAM413は、さらに、コンピュータ機器の起動時に各構成を制御するためのデバイスドライバや各構成の起動時に設定するパラメータなどを格納する。

0023

通信部105は、コンピュータ機器を有線ネットワーク136に接続する。無線LANサブシステム408は、コンピュータ機器をIEEE802.11a/b/g/n規格準拠する無線ネットワークに接続する。汎用バスインタフェイス411は、コンピュータ機器をUSBやIEEE1394などのシリアルバスに接続する。なお、後述するように、通信部105は、パケット情報処理検索テーブルを用いて、パケットの検索要求に対する検索処理などのプロトコル処理を行うTOEサブシステム(情報処理装置)として機能する。

0024

コンピュータ機器の電源投入されると、主プロセッサ101は、NVRAM413に格納されたブートプログラムを実行し、上記の各構成を初期化する。そして、HDD406に格納されたソフトウェアを主メモリ104にロードして、OSやアプリケーションプログラムを実行する。また、主プロセッサ101は、サブシステムの初期化時、通信部105が内蔵する後述する複数のサブプロセッサがそれぞれ実行するファームウェアを主メモリ104にロードして、各サブプロセッサを起動する。各サブプロセッサは、主メモリ104にロードされた対応するファームウェアを内蔵する命令キャッシュメモリにロードして、ファームウェアを実行する。

0025

[通信部]
図2のブロック図により通信部105の構成例を説明する。

0026

バスブリッジ116は、通信部105の内部バスであるサブシステムバス123とシステムバス102を接続する。なお、サブシステムバス123はクロスバースイッチ接続である。通信部105は五つのサブプロセッサ111〜115を内蔵し、これらサブプロセッサによるマルチプロセッサ処理により、主システムからオフロードしたTCP/IPのプロトコル処理を高速に実行する。共有メモリ125は、サブプロセッサ111〜115間の通信と情報共有のためのメモリである。通信タイマ124は、プロトコル処理に必要な時間計測およびタイムアウトイベントを発生する。

0027

通信部105は、有線ネットワーク136に接続するためのハードウェアとしてPHY134とMAC (media access controler)133を備える。PHY134は、OSI参照モデル物理層(第一層)のプロトコル処理と電気信号を扱う。MAC133は、OSI参照モデルのデータリンク層(第二層)の下位副層に相当するMAC層プロトコルを処理する。

0028

データパス制御部132は、受信パケットデータ送信パケットデータを、例えば、主メモリ104または共有メモリ125とMAC133の間でDMA転送する機能を有する。データパス制御部132は、転送処理中にパケットデータのチェックサム演算を行う。検索部122は、連想メモリを有し、サブプロセッサの要求に応じて、プロトコル処理の様々な管理情報の格納と検索処理を行う情報処理装置(コンピュータ装置)である。

0029

通信部105は、暗号通信プロトコル(IPsec、SSL、TLSなど)処理を実行し、そのために鍵管理部126、乱数発生器127、暗号器129を有する。鍵管理部126は、生成した暗号鍵乱数素数機密に保持する。乱数発生器127は、暗号処理に必要な乱数値を生成する。暗号器129はAES暗号器であり、さらに、認証やディジタル署名などに使われるSHA-1やRFC1321として標準化されているMD5などのハッシュ関数を発生する。

0030

●サブプロセッサ
図3により通信部105のサブプロセッサ111〜115の役割を説明する。TCP/IPプロトコル処理は、アプリケーション層501、ソケットAPI502、トランスポート層(TCP/UDP層)503、インターネット層(IP層)504、MACドライバ505、MAC層506、PHY層507の階層構造を有す。

0031

通信部105は、インターネットプロトコル(IP)を処理するIP層504の処理機能、並びに、転送制御プロトコル(TCP)およびユーザデータグラムプロトコル(UDP)を処理するTCP/UDP層503の処理機能を有する。さらに、MAC層506との間で通信データと通信情報交換するMACドライバ505の機能、並びに、アプリケーション通信のインタフェイスIであるソケットAPI502の一部機能を有する。通信部105は、これら機能を各サブプロセッサに分散して処理を行う。

0032

例えば、ソケットAPI502の処理をサブプロセッサ111に割り当てる。TCPとUDPの処理のうち受信動作515に関わる処理をサブプロセッサ112に割り当て、送信動作516に関わる処理をサブプロセッサ113に割り当てる。MACドライバ505とIPの処理のうち受信動作515に関わる処理をサブプロセッサ114に割り当て、送信動作516に関わる処理をサブプロセッサ115に割り当てる。このように処理を分散する意図は、一連のプロトコル処理を三つのパイプラインステージ511〜513に分割し、パイプライン動作を行うことにある。また、送信動作516と受信動作515を分けることで、それぞれの機能を分担するサブプロセッサ同士を並列的に動作させる。

0033

各サブプロセッサ間の処理データの伝達と制御情報共有は共有メモリ125を介して行われる。例えば、TCPは転送データの到達保証を行う観点から、受信側から送信側に対して、確認応答と称する到達確認情報コネクション間で伝達する。この確認応答を行うには、サブプロセッサ112とサブプロセッサ113との間で確認応答の伝達514が必要になる。このようなTCPの制御情報の伝達は共有メモリ125を介して行われる。なお、サブプロセッサ間における到達確認情報の伝達と制御情報の共有は主メモリ104を用いて行ってもよい。

0034

●検索部
サブプロセッサは、プロトコル処理における処理を検索部122に要求し、処理要求とともに処理の種類などを示すパラメータを検索部122に供給する。検索処理の種類には第一の検索モードであるシングルヒットモード検索、第二の検索モードである全検索モード検索、データ登録、および、データ削除が含まれる。また、検索処理に関するパラメータには検索モード、検索キー、登録または削除すべきデータなどが含まれる。

0035

検索部122は、データ検索を要求されると、読出処理比較処理によってデータの検索処理を実行し、検索結果を要求元のサブプロセッサに返す。検索モードには、上述したようにシングルヒットモードと全検索モードがある。なお、全検索モードにおいては、複数のエントリデータにヒットする可能性がある。

0036

検索部122は、データ登録が要求されるとパラメータに含まれるデータを検索テーブルへ登録し、データ削除が要求されるとパラメータに含まれるデータに対応するエントリデータを検索テーブルから削除する。

0037

図4のブロック図により検索部122の構成例を説明する。検索処理入力部201は、サブプロセッサから処理要求を入力する。検索ジョブキュー202は、検索処理入力部201が入力した処理要求に対応するジョブのキューイング手段として機能する。なお、検索部122は、処理要求に対応するジョブをキューイングせずに一つずつ実行してもよい。

0038

モード判別部203は、ジョブを解析し、上述した処理の種類を判別する。検索制御部204は、判別された種類の検索処理の実行を制御する。つまり、モード判別部203は、検索制御部204の指示に従い検索ジョブキュー202から検索ジョブを取り出し、検索ジョブの内容を判別して、検索制御部204に検索モード、検索キー、データなどのパラメータを渡す。

0039

内部メモリテーブル206は、検索部122の内部メモリに配置され、検索対象のエントリデータを格納する。なお、内部メモリの代わりに共有メモリ125に内部メモリテーブル206を配置してもよい。内部メモリ検索部205は、内部メモリに対する検索処理を行い、内部メモリテーブル206からエントリデータを読み出し、読み出したエントリデータと検索キーを比較する一連の検索処理を行う第一の検索部である。

0040

外部メモリテーブル208は、検索対象のエントリデータを格納する。外部メモリテーブル208は、例えば主メモリ104の所定領域に割り当てられる。外部メモリ検索部207は、外部メモリテーブル208に対する検索処理を行い、外部メモリテーブル208からエントリデータを読み出し、読み出したエントリデータと検索キーを比較する一連の検索処理を行う第二の検索部である。

0041

つまり、内部メモリテーブル206と外部メモリテーブル208の組み合わせによってパケット情報処理検索テーブルが構成される。

0042

検索処理の一連の動作は、内部メモリ検索部205と外部メモリ検索部207によって行われる。しかし、内部メモリ検索処理と外部メモリ検索処理が並列に実行可能であれば、両処理を行う一つの構成によって検索処理の一連の動作を行ってもよいし、複数の構成を有してもよい。あるいは、内部メモリ検索処理と外部メモリ検索処理を時分割で行う一つの構成としてもよい。

0043

検索制御部204は、検索結果通知部209を介して、検索処理の要求元のサブプロセッサに検索結果を通知する。さらに、検索設定部210は、検索部122に対する設定情報を与える手段として機能する。つまり、検索部122の初期化時、主プロセッサ101は、検索設定部210に対し、最大エントリ数や外部メモリテーブル208を保持する主メモリ104のアドレス空間を設定するなどの処理を行う。なお、エントリ数と外部メモリテーブルのアドレス空間についてソフトウェアにより柔軟に設定が可能な構成例を説明したが、エントリ数や外部メモリテーブルのアドレス空間は予め固定されていてもよい。

0044

[検索処理]
図5のフローチャートにより検索部122の検索処理を説明する。

0045

サブプロセッサによって検索処理の要求が所定のレジスタに書き込まれると、検索処理入力部201は、検索処理の要求を入力して、対応する検索ジョブを検索ジョブキュー202にキューイングする(S301)。

0046

モード判別部203は、検索ジョブのキューイングを検知すると、検索制御部204が検索処理中か否かを調べ(S302)、検索処理中の場合は検索処理が終了するまで待機する。検索処理中ではない、または、検索処理が終了すると、モード判別部203は、検索ジョブキュー202から検索ジョブを取り出し(S303)、検索処理の種類を判別する。

0047

検索処理の種類がデータ登録の場合(S304)、検索制御部204はデータの登録処理を行う(S305)。検索処理の種類がデータ削除の場合(S306)、検索制御部204はエントリデータの削除処理を行う(S307)。検索処理の種類がシングルヒットモード検索の場合(S308)、検索制御部204はシングルヒットモード検索処理を行う(S309)。検索処理の種類が全検索モード検索の場合(S310)、検索制御部204は全検索モード検索処理を行う(S311)。

0048

検索処理の種類が何れにも該当しない場合、モード判別部203は、検索制御部204に検索処理の指定エラーを出力する(S312)。検索制御部204は、各処理の終了後、検索結果通知部209を介して、処理結果を検索処理の要求元のサブプロセッサに通知する(S313)。

0049

なお、図5に示す検索部122の処理フローは一例であり、検索処理の実行前に処理内容を判別し、判別結果に基づき検索処理を実行する手順であればよい。

0050

●シングルヒットモード検索処理
図6のフローチャートによりシングルヒットモード検索処理(S309)を説明する。

0051

検索制御部204は、内部メモリ検索部205にシングルヒットモード検索処理を開始させる。内部メモリ検索部205は、内部メモリテーブル206からエントリを読み出し、検索キーと比較する(S601)。内部メモリ検索部205は、比較の結果、検索がヒット(検索キーに対応するデータを検出)したか否かを判定し(S602)、ヒットした場合は処理をステップS609に進め、ヒットしなかった場合は処理をステップS603に進める。

0052

検索がヒットしなかった場合、内部メモリ検索部205は、内部メモリテーブル206の全エントリとの比較を行ったか否かを判定し(S603)、全エントリとの比較が未了の場合は処理をステップS601に戻す。また、内部メモリ検索部205が全エントリとの比較を完了したと判定した場合、検索制御部204は、内部メモリ検索部205の検索処理を終了し、処理をステップS604に進める。つまり、内部メモリテーブル206の全エントリとの比較が完了するか、検索にヒットするエントリが見付かるまでステップS601、S602、S603が繰り返される。

0053

検索がヒットせずに、内部メモリテーブル206の全エントリとの比較が完了すると、検索制御部204は、登録エントリ数を参照して、外部メモリテーブル208にエントリがあるか否かを判定する(S604)。外部メモリテーブル208にエントリがない場合は処理をステップS608へ進める。

0054

外部メモリテーブル208にエントリがある場合、検索制御部204は、外部メモリ検索部207にシングルヒットモード検索処理を開始させる。外部メモリ検索部207は、外部メモリテーブル208からエントリを読み出し、検索キーと比較する(S605)。外部メモリ検索部207は、比較の結果、検索がヒットしたか否かを判定し(S606)、ヒットした場合は処理をステップS609に進め、ヒットしなかった場合は処理をステップS607に進める。

0055

検索がヒットしなかった場合、外部メモリ検索部207は、外部メモリテーブル208の全エントリとの比較を行ったか否かを判定し(S607)、全エントリとの比較が未了の場合は処理をステップS605に戻す。また、外部メモリ検索部207が全エントリとの比較を完了したと判定した場合、検索制御部204は、外部メモリ検索部207の検索処理を終了し、処理をステップS608に進める。つまり、外部メモリテーブル208の全エントリとの比較が完了するか、検索にヒットするエントリが見付かるまでステップS605、S606、S607が繰り返される。

0056

外部メモリテーブル208にエントリがない、または、外部メモリテーブル208の全エントリとの比較が完了すると、検索制御部204は、検索結果として「ミスヒット」を要求元のサブプロセッサに通知する(S608)。そして、シングルヒットモード検索処理を終了する。

0057

一方、検索がヒットした場合、検索制御部204は、ヒットしたエントリIDを一時保存し(S609)、検索テーブルエントリの入替処理を行う(S610)。そして、検索結果「ヒット」と、ヒットしたエントリIDを要求元のサブプロセッサに通知し(S611)、シングルヒットモード検索処理を終了する。

0058

●検索テーブルエントリの入替処理
図7のフローチャートにより検索テーブルエントリの入替処理(S610)を説明する。

0059

検索制御部204は、外部メモリテーブル208のエントリがヒットしたか否かを判定する(S701)。外部メモリテーブル208のエントリがヒットした場合は、ヒットしたエントリと内部メモリテーブル206の任意のエントリを入れ替える(第一の入替)(S702)。内部メモリテーブル206の任意のエントリは、先頭を除いたラウンドロビンで管理され、外部メモリテーブル208のエントリとの入れ替えが行われる度に選択されるエントリ(入替対象のエントリ)が更新される。

0060

なお、入替対象のエントリは、内部メモリテーブル206の先頭エントリでもよいし、使われてから最も長い時間が経ったエントリをLRU(least recently used)などの任意のアルゴリズムを用いて選択してもよい。

0061

また、内部メモリテーブル206のエントリがヒットした場合、検索制御部204は、ヒットしたエントリが内部メモリテーブル206の先頭エントリか否かを判定し(S703)、先頭エントリの場合は入替処理を終了する。また、先頭エントリではない場合、ヒットしたエントリと内部メモリテーブル206の先頭エントリを入れ替える(第二の入替)(S704)。

0062

内部メモリテーブル206のエントリがヒットした場合、検索テーブルエントリの入れ替えは行わずに、次回の検索をヒットした内部メモリテーブル206のエントリから始める方式でもよい。また、先頭エントリからではなく、複数のエントリグループから優先的に検索を行ってもよい。

0063

なお、検索テーブルエントリの入替処理は、内部メモリテーブル206と外部メモリテーブル208にエントリを配置して、論理的に一つの検索テーブル(パケット処理情報検索テーブル)を構成することができる手順であればよい。

0064

●全検索モード検索処理
図8のフローチャートにより全検索モード検索処理(S311)を説明する。

0065

検索制御部204は、内部メモリ検索部205と外部メモリ検索部207に全検索モード検索処理を開始させる。内部メモリ検索部205は、内部メモリテーブル206からエントリを読み出して検索キーとの比較を行い、外部メモリ検索部207は、外部メモリテーブル208からエントリを読み出して検索キーとの比較を行う(S801)。

0066

内部メモリ検索部205と外部メモリ検索部207は、検索がヒットしたか否かを判定し(S802)、ヒットした場合はヒットしたエントリIDを保存し、ヒットしたエントリの数をカウントする(S803)。そして、内部メモリテーブル206の全エントリとの比較、および、外部メモリテーブル208の全エントリとの比較を行ったか否かを判定する(S804)。このように、内部メモリ検索部205と外部メモリ検索部207は、並列的に、全エントリとの比較が終了するまで、ステップS801からS804の処理を繰り返し継続する。

0067

全エントリとの比較が終了すると、検索制御部204は、ヒットしたエントリがあるか否かを判定し(S805)、ヒットしたエントリがあればヒットしたエントリIDとヒットしたエントリ数を要求元のサブプロセッサに通知する(S806)。また、ヒットしたエントリがない場合はヒット数がゼロである旨を要求元のサブプロセッサに通知する(S807)。そして、全検索モード検索処理を終了する。

0068

●登録処理
図9のフローチャートにより登録処理(S305)を説明する。

0069

検索制御部204は、内部メモリテーブル206を格納する内部メモリに空きがあるか否かを判定する(S901)。内部メモリに空きがあれば、内部メモリ検索部205を介して、登録を要求されたデータ(以下、対象データ)を内部メモリテーブル206に登録(追加)する(S902)。また、内部メモリに空きがない場合、外部メモリテーブル208を格納する外部メモリに空きがあるか否かを判定する(S903)。外部メモリに空きがあれば、外部メモリ検索部207を介して、対象データを外部メモリテーブル208に登録(追加)する(S904)。

0070

対象データの登録に成功すると、検索制御部204は、登録エントリ数のカウント値インクリメントし(S905)、登録に成功した旨を要求元のサブプロセッサに通知する(S906)。また、内部メモリと外部メモリに空きがなかった場合、検索制御部204は、登録に失敗した旨を表すエラー通知を要求元のサブプロセッサに通知する(S907)。そして、登録処理を終了する。

0071

なお、登録処理は、内部メモリテーブル206と外部メモリテーブル208にエントリを配置して、論理的に一つの検索テーブル(パケット処理情報検索テーブル)を構成することができる手順であればよい。

0072

●削除処理
図10のフローチャートにより削除処理(S307)を説明する。

0073

検索制御部204は、内部メモリ検索部205を介して、削除が要求されたエントリデータ(以下、対象データ)が内部メモリテーブル206に登録されているか否かを判定する(S1001)。そして、対象データが内部メモリテーブル206に登録されている場合は処理をステップS1004に進める。また、対象データが内部メモリテーブル206に登録されていない場合は、外部メモリ検索部207を介して、対象データが外部メモリテーブル208に登録されているか否かを判定する(S1002)。そして、対象データが外部メモリテーブル208にも登録されていない場合は削除処理の「指定エラー」を要求元のサブプロセッサに通知し(S1003)、削除処理を終了する。

0074

対象データが内部メモリテーブル206に登録されている場合、検索制御部204は、外部メモリテーブル208にエントリがあるか否かを判定する(S1004)。外部メモリテーブル208にエントリがない場合は、内部メモリ検索部205を介して、内部メモリテーブル206から対象データに対応するエントリを削除する(S1005)。また、外部メモリテーブル208にエントリがある場合は、内部メモリ検索部205および外部メモリ検索部207を介して、外部メモリテーブル208の最終エントリデータを、内部メモリテーブルの対象データに対応するエントリに登録する(S1006)。言い替えれば、対象データのエントリを外部メモリテーブル208の最後に登録されたデータ(最終エントリデータ)で置き換える。

0075

対象データが外部メモリテーブル208に登録されている場合、検索制御部204は、外部メモリ検索部207を介して、対象データが外部メモリテーブル208の最終エントリか否かを判定する(S1007)。対象データが最終エントリではない場合、外部メモリ検索部207を介して、外部メモリテーブル208の最終エントリデータを、外部メモリテーブル208の対象データに対応するエントリに登録する(S1008)。言い替えれば、対象データのエントリを外部メモリテーブル208の最終エントリで置き換える。

0076

次に、検索制御部204は、登録エントリ数のカウント値をデクリメントし(S1009)、削除に成功した旨を要求元のサブプロセッサに通知して(S1010)、削除処理を終了する。

0077

なお、削除処理は、内部メモリテーブル206と外部メモリテーブル208にエントリを配置して、論理的に一つの検索テーブル(パケット処理情報検索テーブル)を構成することができる手順であればよい。

0078

また、内部メモリテーブル206のエントリを削除する場合、内部メモリテーブル206へ移動する外部メモリテーブル208のエントリは任意のエントリにすることができる。その場合、外部メモリテーブル208の最終エントリを、内部メモリテーブル206に移動したエントリに移動すると効率的な検索が可能になる。

0079

このように、検索処理に先立ち、要求された検索処理の種類を判別し、全検索モード検索の場合は内部メモリ検索処理と外部メモリ検索処理を並列的に実行する。また、シングルヒットモード検索の場合は、内部メモリ検索処理、外部メモリ検索処理の順に検索処理を逐次的に実行する。

0080

つまり、内部メモリと外部メモリを用いて論理的に一つの検索テーブルを構成した場合、並列的な検索処理により全検索モードにおける検索性能の低下を抑える。

0081

また、シングルヒットモード検索においては、逐次的な検索処理により、低速な外部メモリよりも高速な内部メモリの検索を優先して、検索処理性能を最大限に発揮することができる。その際、同一のエントリがヒットする確率が高いプロトコル処理における連続するパケットのシングルヒットモード検索において、内部メモリの検索を優先することで、外部メモリの検索処理を終了させるための処理の実行回数を削減することができる。その結果、不要な処理と複雑な処理を避けることができ、処理の複雑化と回路規模の増大を防ぎ、消費電力の増大も防ぐことができる。

0082

また、外部メモリに登録されたエントリが連続するパケットの検索対象エントリである場合、遅延時間の削減が可能になり、検索処理を効率化を図ることができる。

0083

[その他の実施例]
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア(プログラム)を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ(又はCPUやMPU等)がプログラムを読み出して実行する処理である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ