(57)【特許請求の範囲】
【請求項１】
入力データの一部のビット列を検索キーとし、所定のデータ記憶手段に予め格納されている複数のデータによって構成されているデータテーブルの中から、上記検索キーと一致する項目を含むデータ群を検索するテーブル検索処理を行なう複数のテーブル検索装置と;
上記複数のテーブル検索装置のそれぞれに実行させる検索処理または更新処理を示す処理内容を、上記テーブル検索装置毎に個別に示す処理内容指示データを具備する処理内容指示テーブルと;
上記処理内容指示テーブルにおける処理内容指示データを読み込み、上記処理内容指示データに従って、上記複数のテーブル検索装置のうちの少なくとも１つのテーブル検索装置に上記テーブル検索処理を実行させているときに、上記データ記憶手段に格納されている上記データテーブルを変更するテーブル更新処理を、上記複数のテーブル検索装置のうちの他のテーブル検索装置に実行させるコントローラと；
テーブル検索終了レジスタと、テーブル更新レジスタと、切り替え要求レジスタとによって構成されているタイミングレジスタであって、上記コントローラに設けられ、切り替えタイミングをはかり、上記各テーブル検索装置の処理内容を切り替えるタイミングレジスタと；
を有することを特徴とするデータベース管理装置。
【請求項２】
請求項１において、
上記処理内容指示データは、上記処理内容指示テーブルの外部から変更可能であることを特徴とするデータベース管理装置。
【請求項３】
請求項１において、
上記コントローラは、上記複数のテーブル検索装置のそれぞれについて、上記処理内容指示データを上記処理内容指示テーブルに同時に設定するものであることを特徴とするデータベース管理装置。
【請求項４】
請求項１において、
上記処理内容指示テーブルは、上記複数のテーブル検索装置に新たなテーブル検索装置が追加されたときに、上記追加された新たなテーブル検索装置に対応する処理内容指示データを追加可能であることを特徴とするデータベース管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力データの一部のビット列を検索キーとし、メモリ（ＲＡＭ）等のデータ記憶手段に予め格納されている複数のデータによって構成されているデータテーブルの中から、上記検索キーと一致する項目を含むデータ群を選択するテーブル検索処理を行い、必要に応じてデータテーブルのデータを変更するテーブル検索装置のデータベース管理技術に関する。
【０００２】
【従来の技術】
従来のデータベース管理において、データ記憶手段に予め格納されている複数のデータによって構成されているデータテーブルを更新処理する場合、データテーブルの中から、上記検索キーと一致する項目を含むデータ群を選択するテーブル検索処理を一時停止させるか、または、テーブル更新処理とテーブル検索処理とをシーケンシャルに実行する。
【０００３】
【発明が解決しようとする課題】
上記従来例では、上記のように、データテーブルを更新する場合、テーブル検索処理を一時停止させるか、または、テーブル更新処理とテーブル検索処理とをシーケンシャルに実行するので、データテーブルを更新処理すると、テーブル検索処理速度を低下させるという問題がある。
【０００４】
本発明は、テーブル検索処理速度を低下させることなく、データテーブルを更新処理することができるデータベース管理装置を提供することを目的とするものである。
【０００５】
【課題を解決するための手段】
本発明は、入力データの一部のビット列を検索キーとし、所定のデータ記憶手段に予め格納されている複数のデータによって構成されているデータテーブルの中から、上記検索キーと一致する項目を含むデータ群を検索するテーブル検索処理を行なう複数のテーブル検索装置と、上記複数のテーブル検索装置のそれぞれに実行させる検索処理または更新処理を示す処理内容を、上記テーブル検索装置毎に個別に示す処理内容指示データを具備する処理内容指示テーブルと、上記処理内容指示テーブルにおける処理内容指示データを読み込み、上記処理内容指示データに従って、上記複数のテーブル検索装置のうちの少なくとも１つのテーブル検索装置に上記テーブル検索処理を実行させているときに、上記データ記憶手段に格納されている上記データテーブルを変更するテーブル更新処理を、上記複数のテーブル検索装置のうちの他のテーブル検索装置に実行させるコントローラと、テーブル検索終了レジスタと、テーブル更新レジスタと、切り替え要求レジスタとによって構成されているタイミングレジスタであって、上記コントローラに設けられ、切り替えタイミングをはかり、上記各テーブル検索装置の処理内容を切り替えるタイミングレジスタとを有するデータベース管理装置である。
【０００６】
【発明の実施の形態および実施例】
（実施例１）
図１は、本発明の一実施例であるデータベース管理装置ＤＭ１を示す図である。
【０００７】
データベース管理装置ＤＭ１は、複数のテーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４と、処理内容指示テーブルＤＴ１と、コントローラＣ１とを有する。
【０００８】
テーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４は、入力データの一部のビット列を検索キーとし、所定のデータ記憶手段（メモリ）に予め格納されている複数のデータによって構成されているデータテーブルの中から、上記検索キーと一致する項目を含むデータ群を検索するテーブル検索処理を行なう装置である。
【０００９】
処理内容指示テーブルＤＴ１は、複数のテーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４のそれぞれに実行させる処理内容を、テーブル検索装置毎に個別に示す処理内容指示データＤＤを具備するテーブルである。つまり、処理内容指示テーブルＤＴ１は、複数のテーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４のそれぞれに実行させるテーブル検索処理またはテーブル更新処理、または、実行停止を指示する（設定する）データを具備するテーブルである。また、処理内容指示データＤＤは、処理内容指示テーブルＤＴ１の外部から変更可能である。
【００１０】
コントローラＣ１は、処理内容指示テーブルＤＴ１における処理内容指示データＤＤを読み込み、複数のテーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４のうちの少なくとも１つのテーブル検索装置にテーブル検索処理を実行させているときに、上記データ記憶手段に格納されている上記データテーブルを変更するテーブル更新処理を、複数のテーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４のうちの他のテーブル検索装置に実行させるものである。
【００１１】
また、コントローラＣ１は、複数のテーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４のそれぞれについて、処理内容指示データＤＤを処理内容指示テーブルＤＴ１に同時に設定するものである。
【００１２】
テーブル検索装置ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４のそれぞれは、その内部にメモリ等の記憶手段を有する。
【００１３】
上記各処理内容指示データＤＤは、図１に示すように、０または１の値を取り、テーブル検索装置ＴＳ１〜ＴＳ４毎に、どちらか一方の処理内容指示データＤＤにのみ１を設定することができる。つまり、テーブル検索装置ＴＳ１〜ＴＳ４毎に、テーブル検索処理またはテーブル更新処理に、１を設定することができる。また、テーブル検索装置ＴＳ１〜ＴＳ４のうちの所定のテーブル検索処理に１が設定されていれば、テーブル検索処理に１が設定されているテーブル検索装置について、テーブル検索処理が実行され、テーブル更新処理に１が設定されているテーブル検索装置について、テーブル更新処理が実行される。
【００１４】
図２は、上記実施例において、テーブル検索装置のうちで、未使用のテーブル検索装置ＴＳｎについて、その処理内容指示テーブルＤＴ１を決定する処理内容指示データＤＤを設定する説明図である。
【００１５】
所定のテーブル検索装置ＴＳｎを、テーブル検索処理にもテーブル更新処理にも用いない場合、図２に示すように、テーブル検索装置ＴＳｎに対応する２つの処理内容指示データＤＤをともに０に設定する。これによって、このテーブル検索装置ＴＳｎは、入力データに対して何も実行しない。
【００１６】
コントローラＣ１は、処理内容指示テーブルＤＴ１中の処理内容指示データＤＤを読み込み、各テーブル検索装置ＴＳ１〜ＴＳ４のうちで所定のテーブル検索装置に対応して１が設定されている処理内容指示データＤＤの示す処理を、上記所定のテーブル検索装置に実行させるように、上記所定のテーブル検索装置に指示する。
【００１７】
図３は、上記実施例において、テーブル検索装置ＴＳ１〜ＴＳ４のうちで、未使用のテーブル検索装置ＴＳｎを、テーブル検索処理またはテーブル更新処理に用いようとする場合に、処理内容指示データＤＤを設定する動作の説明図である。
【００１８】
未使用のテーブル検索装置ＴＳｎに対して、上記いずれかの処理内容を実行させる場合、図３に示すように、その処理内容に対応する処理内容指示データＤＤを１に設定し、コントローラＣ１が未使用のテーブル検索装置ＴＳｎに処理内容の変更を指示する。
【００１９】
次に、上記実施例において、テーブル検索処理とテーブル更新処理との動作について説明する。
【００２０】
各テーブル検索装置ＴＳ１〜ＴＳ４は、テーブル検索処理とテーブル更新処理のどちらを実行するのか、または、どちらの処理も実行しないのかが、コントローラＣ１によって予め指示される。
【００２１】
図１に示す例では、テーブル検索装置ＴＳ１とＴＳ２とが、テーブル検索処理を実行し、テーブル検索装置ＴＳ３とＴＳ４とが、テーブル更新処理を実行する。
【００２２】
まず、テーブル検索処理を実行するテーブル検索装置ＴＳ１、ＴＳ２は、入力データに対してテーブル検索処理結果（出力）をコントローラＣ１に送出し、コントローラＣ１は、各テーブル検索装置ＴＳ１、ＴＳ２から得た一部の出力結果、または、全ての出力結果を出力する。テーブル更新処理を実行するテーブル検索装置ＴＳ３、ＴＳ４に入力する入力データは、命令（データ登録命令、または、データ削除命令）と、上記命令で使用するデータとによって構成され、上記入力データによって、テーブル検索装置ＴＳ３、ＴＳ４内のメモリデータの更新を行う。
【００２３】
各テーブル検索装置ＴＳ１〜ＴＳ４の処理内容を変更する場合、コントローラＣ１に設けられている切り替えタイミングレジスタＲによって、切り替えタイミングをはかり、各テーブル検索装置ＴＳ１〜ＴＳ４の処理内容の切り替えを実行する。タイミングレジスタＲはテーブル検索終了レジスタと、テーブル更新レジスタと、切り替え要求レジスタとによって構成され、各レジスタは０または１の値を取る。
【００２４】
図４は、上記実施例において、コントローラＣ１が有する切り替えタイミングレジスタＲの値とその意味とを示す図である。
【００２５】
テーブル検索装置ＴＳ１〜ＴＳ４が実行する処理の状態（処理開始と、処理終了）が変更したときに、各テーブル検索装置ＴＳ１〜ＴＳ４は、その変更後の状態を、状態信号によって、コントローラＣ１に伝える。テーブル検索処理を実行する各テーブル検索装置ＴＳ１〜ＴＳ４が、全てテーブル検索処理を終了している場合に、上記テーブル検索終了データに１が設定される。また、テーブル更新処理を実行する各テーブル検索装置ＴＳ１〜ＴＳ４が、全てテーブル更新処理を終了している場合に、上記テーブル更新終了データに１が設定される。  次に、上記処理内容切り替え動作のシーケンスについて説明する。
【００２６】
図５は、上記実施例において、処理内容指示テーブルＤＴ１を用いて、テーブル検索装置ＴＳ１〜ＴＳ４が実行する処理内容を切り替える場合に、処理内容指示テーブルＤＴ１における処理内容指示データＤＤを切り替える説明図である。
【００２７】
まず、図５（１）に示すように、テーブル検索装置ＴＳ１〜ＴＳ４のうちで、処理内容を変更すべきテーブル検索装置に対応する処理内容指示テーブルＤＴ１内の処理内容指示データＤＤを変更する。次に、外部から、コントローラＣ１に切り替え要求信号を送り、コントローラＣ１内の切り替え要求レジスタの値が０から１に変更される。次に、テーブル検索終了レジスタの値と、テーブル更新終了レジスタの値とがともに１になったときに、処理内容指示データＤＤで示される処理内容を、テーブル検索装置ＴＳ１〜ＴＳ４のそれぞれに対して指示し、切り替え要求レジスタの値を０に変更し、切り替え終了信号を出力する。
【００２８】
図６は、本発明の第２の実施例であるデータベース管理装置ＤＭ２を示す図である。
【００２９】
データベース管理装置ＤＭ２は、データベース管理装置ＤＭ１において、新たに制御する検索エンジン（テーブル検索装置ＴＳｎ）を追加した場合における回路図である。
【００３０】
テーブル検索装置ＴＳｎを新たに追加する場合、図６に示すように、追加するテーブル検索装置ＴＳｎに対応する処理内容指示データＤＤを処理内容指示テーブルＤＴ１に追加することによって、処理内容の並列度を拡張することができる。
【００３１】
データベース管理装置ＤＭ１、ＤＭ２は、特に、通信ネットワークにおける通信ノード（ルータ装置、およびスイッチ装置等）のテーブル検索処理、および、テーブル更新処理に有効である。通信ノードのテーブル検索処理は、データを運ぶパケットの行き先アドレスを検索キーとし、データテーブル内の被検索データと一致検索を行い、次の接続先通信ノードまたは端末装置のネットワークアドレスを見つけ出す処理である。
【００３２】
次に、ルータ装置が有するデータテーブルと、これを用いたテーブル検索処理とについて説明する。
【００３３】
図８は、ルータ装置が有するデータテーブルの一例を示す図である。
【００３４】
現在のインターネットでは、インターネットプロトコルを中心としたネットワークで構成され、上記テーブル検索において、最長プレフィクス一致検索（ベストマッチ処理）が採用されている。
【００３５】
次に、ベストマッチ処理について説明する。
【００３６】
ベストマッチ処理において、各通信ノードのデータテーブルには、図８に示すように、被検索データとして、行き先アドレスとマスクデータとが構成され、出力データとして、出力ポート番号とネクストホップアドレスとの組によって構成されている。図８の例では、インターネットプロトコルアドレスの慣例に従い、３２ｂｉｔ長のデータをＢｙｔｅ単位で１０進数表現し、その間を「.」で結ぶ形で表現している。
【００３７】
まず、マスクデータで「１」を立てたビット領域だけ、被検索データを有効にするネットマスク処理を行う。この処理によってできたデータを、プレフィクスと言い、マスクで指示したビット長をプレフィクス長という。
【００３８】
図８に示す例では、行き先アドレスのうちで、下線で示した部分がプレフィクスの領域だけ、与えられたキーデータと被検索データとの一致検索を行い、一致した結果のうちで、最もプレフィクスが長い被検索データを選択する。たとえば、キーデータ１０．１２７．１２８．５５を、図８を用いてベストマッチ処理を行った場合、全てのプレフィクスに一致し、このうちで、プレフィクス長が最も長い被検索データ１０．１２７．１２８．１０を選択する。このベストマッチ処理によって、フォワーディングするパケットが最短で到達するルート（通信ノードの出力ポート番号とネクストホップアドレス）を決定する。
【００３９】
なお、従来例では、上記通信ノードにおいて、テーブル更新処理を行う場合、上記テーブル検索処理を一時停止させるか、または、テーブル更新処理とテーブル検索処理とをシーケンシャルに処理する必要があるので、テーブル検索処理速度が低下する。
【００４０】
しかし、上記実施例によれば、テーブル検索装置ＴＳ１〜ＴＳ４毎に、テーブル検索処理またはテーブル更新処理を指示し、テーブル検索処理とテーブル更新処理とを並列処理するので、テーブル検索処理速度を低下させることなく、テーブル更新処理を実行することができる。
【００４１】
また、上記実施例によれば、処理内容指示テーブルＤＴ１の内部に登録されている処理内容指示データＤＤを、必要に応じて変更することができるので、コントローラＣ１が処理内容切り替えのタイミングを取ることによって、テーブル検索処理速度を低下させることなく、上記テーブル検索装置ＴＳ１〜ＴＳ４毎に、テーブル検索処理からテーブル更新処理への変更、または、テーブル更新処理からテーブル検索処理への変更を行なうことができる。
【００４２】
（実施例２）
図７は、本発明の第３の実施例であるデータベース管理装置ＤＭ３を示す図である。
【００４３】
データベース管理装置ＤＭ３は、データベース管理装置ＤＭ１と同じ数のテーブル検索装置を有し、また、処理内容指示テーブルＤＴ１と、コントローラＣ１とを有するが、テーブル検索装置ＴＳ１１、ＴＳ１２、ＴＳ１３の処理内容（処理速度、または、有するメモリ容量等）が異なる。データベース管理装置ＤＭ３では、処理内容指示テーブルＤＴ１とコントローラＣ１とが、各テーブル検索装置ＴＳ１、ＴＳ１１、ＴＳ１２、ＴＳ１３の処理内容の設定を制御することによって、データベース管理装置ＤＭ１と同様のデータベース管理を行なうことができる。したがって、データベース管理装置ＤＭ３において、テーブル検索処理とテーブル更新処理とを並列実行でき、テーブル検査処理速度を落とさずに、テーブル更新処理を実行することができる。
【００４４】
【発明の効果】
本発明によれば、テーブル検索処理速度を低下させることなく、データテーブルを更新処理することができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の一実施例であるデータベース管理装置ＤＭ１を示す図である。
【図２】上記実施例において、テーブル検索装置のうちで、未使用のテーブル検索装置ＴＳｎについて、その処理内容指示テーブルＤＴ１を決定する処理内容指示データＤＤを設定する説明図である。
【図３】上記実施例において、テーブル検索装置ＴＳ１〜ＴＳ４のうちで、未使用のテーブル検索装置ＴＳｎを、テーブル検索処理またはテーブル更新処理に用いようとする場合に、処理内容指示データＤＤを設定する動作の説明図である。
【図４】上記実施例において、コントローラＣ１が有する切り替えタイミングレジスタＲの値とその意味とを示す図である。
【図５】上記実施例において、処理内容指示テーブルＤＴ１を用いて、テーブル検索装置ＴＳ１〜ＴＳ４が実行する処理内容を切り替える場合に、処理内容指示テーブルＤＴ１における処理内容指示データＤＤを切り替える説明図である。
【図６】本発明の第２の実施例であるデータベース管理装置ＤＭ２を示す図である。
【図７】本発明の第３の実施例であるデータベース管理装置ＤＭ３を示す図である。
【図８】ルータ装置が有するデータテーブルの一例を示す図である。
【符号の説明】
ＤＭ１、ＤＭ２、ＤＭ３…データベース管理装置、
ＴＳ１、ＴＳ２、ＴＳ３、ＴＳ４…テーブル検索装置、
ＤＴ１…処理内容指示テーブル、
Ｃ１…コントローラ、
ＤＤ…処理内容指示データ。
【図１】
0003705570.tif 000002
【図２】
0003705570.tif 000003
【図３】
0003705570.tif 000004
【図４】
0003705570.tif 000005
【図５】
0003705570.tif 000006
【図６】
0003705570.tif 000007
【図７】
0003705570.tif 000008
【図８】
0003705570.tif 000009