(57)【要約】【課題】検索キーを分割してＬＰＭ検索を行う場合においても、正しい検索結果を得ることが可能な検索回路を得ること。【解決手段】入力された検索キーを複数の分割検索キーに分割し、検索キー内の先頭のデータが含まれる上位の分割検索キーから対応するテーブル１ａ〜１ｃを用いて順に最長一致検索を行って、所望の結果情報を得る検索制御部２と、分割検索キーの数だけ設けられるテーブル１ａ〜１ｃであり、分割検索キーに対応する所定の結果情報を含むエントリを格納するテーブル１ａ〜１ｃと、を備える検索回路であり、テーブル１ａ〜１ｃは、検索キーの分割によって分割検索キーに対する結果情報が得られなくなることを回避するためのダミーエントリを有することを特徴とする検索回路。【選択図】      図１
2004336427.tif 000002
【特許請求の範囲】
【請求項１】
入力された検索キーを複数の分割検索キーに分割し、前記検索キー内の先頭のデータが含まれる上位の分割検索キーから対応するテーブルを用いて順に最長一致検索を行って、所望の結果情報を得る検索制御手段と、
前記分割検索キーの数だけ設けられるテーブルであり、前記分割検索キーに対応する所定の結果情報を含むエントリを格納するテーブルと、
を備える検索回路であって、
前記テーブルは、前記検索キーの分割によって前記分割検索キーに対する結果情報が得られなくなることを回避するためのダミーエントリを有することを特徴とする検索回路。
【請求項２】
前記テーブルは、前記分割検索キーの検索対象である分割検索キー対応データまたは他のテーブルから取得したタグと前記分割検索キーの組合せからなる検索対象情報と、前記分割検索キーが前記検索対象情報と一致する必要のある長さを示すマスク長と、前記検索対象情報に対応する所定の結果情報または他のテーブルで分割検索キーと組み合わせて検索するためのタグのいずれかの結果データと、を含むエントリを格納し、
前記ダミーエントリは、前記テーブル内の第１のエントリが前記テーブル内の第２のエントリを包含している場合に、前記第２のエントリに対応する前記結果データのタグを先頭に有する検索対象情報と、前記タグの長さを指定するマスク長と、前記第１のエントリの結果情報を含んで構成され、前記第１と第２のエントリの検索対象情報間で包含関係が生じるテーブルよりも下位のテーブルに格納されることを特徴とする請求項１に記載の検索回路。
【請求項３】
入力された検索キーを複数の分割検索キーに分割し、前記検索キー内の先頭のデータが含まれる上位の分割検索キーから対応するテーブルを用いて順に最長一致検索を行って、所望の結果情報を得る検索制御手段と、
前記分割検索キーの数だけ設けられるテーブルであり、前記分割検索キーの検索対象である分割検索キー対応データまたは他のテーブルから取得したタグと前記分割検索キーの組合せからなる検索対象情報と、前記分割検索キーが前記検索対象情報と一致する必要のある長さを示すマスク長と、前記検索対象情報に対応する所定の結果情報または他のテーブルで検索するためのタグからなる結果データとを含むエントリを格納するテーブルと、
前記テーブルにエントリを追加する場合に、この追加エントリと前記テーブルに格納されているエントリとの包含関係を調べ、包含関係がある場合に、前記エントリとともに必要なテーブルに前記ダミーエントリを追加する包含関係検出・ダミーエントリ管理手段と、
を備えることを特徴とする検索回路。
【請求項４】
前記包含関係検出・ダミーエントリ管理手段は、前記追加エントリと前記テーブルのエントリとの間に包含関係がある場合に、包含されるエントリに対応する前記結果データのタグを先頭に有する検索対象情報と、前記タグの長さを指定するマスク長と、包含するエントリの結果情報を含むダミーエントリを、前記追加エントリと前記テーブルのエントリの検索対象情報間で包含関係が生じるテーブルよりも下位のテーブルに追加することを特徴とする請求項３に記載の検索回路。
【請求項５】
入力された検索キーを複数の分割検索キーに分割し、前記検索キー内の先頭のデータが含まれる上位の分割検索キーから対応するテーブルを用いて順に最長一致検索を行って、所望の結果情報を得る検索制御手段と、
前記分割検索キーの数だけ設けられるテーブルであり、前記分割検索キーの検索対象である分割検索キー対応データまたは他のテーブルから取得したタグと前記分割検索キーの組合せからなる検索対象情報と、前記分割検索キーが前記検索対象情報と一致する必要のある長さを示すマスク長と、前記検索対象情報に対応する結果であり他のテーブルで検索するためのタグと、前記検索対象情報に対応する最終結果である結果情報と、前記結果情報が有効か否かを示すデータ有効フラグを含むエントリを格納するテーブルと、
を備え、
前記検索制御手段は、前記テーブルに前記分割検索キーに一致するエントリがない場合に、このテーブルより前に検索が行われたテーブルで前記データ有効フラグが有効となっているエントリの結果情報を最終的な結果として取得することを特徴とする検索回路。
【請求項６】
前記テーブルにエントリを追加する場合で、追加エントリと前記テーブルのエントリとの間に包含関係が生じる場合に、包含されるエントリの結果情報に包含するエントリの結果情報を格納し、前記データ有効フラグを有効にする処理を、前記追加エントリと前記テーブルのエントリの検索対象情報間で包含関係が生じるテーブルに対して実行する包含関係検出・ダミーエントリ管理手段をさらに備えることを特徴とする請求項５に記載の検索回路。
【請求項７】
前記検索制御手段は、分割される前のエントリの検索対象情報の先頭データを含む検索対象情報を有する上位のテーブルから、最後のデータを含む検索対象情報を有する下位のテーブルに向かって、順に独立して検索を実施できるように、前記テーブルごとに複数備えられ、
上位側のテーブルに接続される検索制御手段は、その検索結果を、前記テーブルの下位側のテーブルに接続される検索制御手段に通知する機能を備えることを特徴とする請求項１〜６のいずれか１つに記載の検索回路。
【請求項８】
入力された検索キーを複数の分割検索キーに分割し、それぞれの前記分割検索キーの最長一致検索を行って、所望の結果情報を得る検索制御手段と、
前記分割検索キーの数だけ設けられるテーブルであり、前記分割検索キーに対応する所定のタグを含むエントリを格納する第１のテーブルと、
それぞれの前記第１のテーブルによって出力されたタグを組み合わせた検索キーに対応する所定の結果情報を含むエントリを格納する第２のテーブルと、
を備える検索回路であって、
前記第２のテーブルは、前記検索キーの分割によって前記分割検索キーに対する結果情報が得られなくなることを回避するためのダミーエントリを有することを特徴とする検索回路。
【請求項９】
所定の通信方式でパケットを送受信する複数の通信インタフェースと、これらの通信インタフェースを接続し、前記通信インタフェース間のパケットの交換を行うスイッチと、を備え、前記通信インタフェースを介して受信したパケットを、その宛先ＩＰアドレスから出力先の通信インタフェースを検索して転送するパケット転送装置において、
前記通信インタフェースは、
受信した前記パケットの宛先アドレスに基づいて、請求項１〜８のいずれか１つに記載の検索回路によって前記パケットの出力先を検索して前記スイッチに送出する受信側パケット処理手段と、
他の前記通信インタフェースから前記スイッチを介して受信したパケットをカプセル化して送信する送信側パケット処理手段と、
を備えることを特徴とするパケット転送装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、パケットなどを、パケットのヘッダに書かれたアドレスに基づき転送先を決定するアドレス検索回路およびこのアドレス検索回路を有するパケット転送装置に関するものである。
【０００２】
【従来の技術】
従来、パケットの転送を行なうルータでは、パケットの宛先ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスから転送先のポートなどの情報を得るための検索を高速に行なうために、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ，連想メモリ）などのデバイスを用いて実現している。また、一般的な検索アルゴリズムであるツリーと組み合わせることによって、上記デバイスが対応している検索キー長を超える検索をサポートし、長いアドレスからの転送先ポートなどの情報の検索を容易にしている。たとえば、ルータにおける検索キーであるパケットの宛先アドレスを任意の数に分割し、この分割した検索キーのそれぞれに対応した種類のテーブルを設け、このテーブルに、分割した検索キーに対応したデータまたは別のテーブルを示すポインタまたはインデックスを格納して最長一致（Ｌｏｎｇｅｓｔ  Ｐｒｅｆｉｘ  Ｍａｔｃｈ，以下、ＬＰＭという）検索を実現するテーブル検索装置が提案されている（たとえば、特許文献１参照）。
【０００３】
【特許文献１】
特開２００１−３２６６７９号公報（第２頁、第２図）
【０００４】
【発明が解決しようとする課題】
しかしながら、上述した従来の技術のように検索キーを複数に分割してＬＰＭ検索を行う場合には、ミスヒットが発生してしまうという問題点があった。図２４は、従来のＬＰＭ検索の問題点を説明するための図である。ここでは、ＩＰｖ６のパケットに格納されている宛先ＩＰアドレス（以下、アドレスという）を用いて、パケットの転送先を求める場合を例に挙げて説明する。また、説明を簡略化するために、検索キーを２つに分割して検索を行う場合を例に挙げる。
【０００５】
図２４（ａ）は、検索キーを分割しない場合のテーブルの内容を示すものであり、２つのエントリＡ，Ｂの「検索対象情報」に、それぞれの転送先の「結果」であるアドレスＡ，Ｂが対応付けされている。また、それぞれのエントリに項目「マスク長」が設けられている。すなわち、アドレス「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」（１６進数表示である。以下に示されるアドレスも同様に１６進数表示で表示する。）を有するパケットの場合には、エントリＡに一致するので、アドレスＡに出力（転送）し、４８ビットでマスクした結果得られるアドレスがアドレス「４０００：０１０２：０３０４：００００：００００：００００：００００：００００」であるパケットの場合にはアドレスＢに出力（転送）することを示している。なお、エントリＡ，Ｂともに４８ビット目まで同じであるが、ＬＰＭ検索では、検索キーと長く一致する方の検索対象情報の結果が優先される。
【０００６】
図２４（ｂ）は、上記（ａ）のテーブルを２つに分割したテーブルを示し、第１のテーブルには、分割された上位６４ビットのアドレスからなる「検索対象情報」と、それに対応する「マスク長」と「結果データ」が格納され、第２のテーブルには、分割された検索キーの下位６４ビットのアドレスからなる「検索対象情報」と、それに対応する「マスク長」と「結果データ」が格納される。なお、図示していないが、第１のテーブルのエントリＡと第２のテーブルのエントリＡとは、インデックスなどで対応付けされている。また、エントリＢに格納されるアドレスは、１２８ビットのうち上位４８ビットをマスクしたもので転送先を判断することが可能なために、第１のテーブルには格納されるが第２のテーブルには格納されていない。
【０００７】
たとえば、アドレス「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」を有するパケット１の場合、検索キーであるアドレスは、第１の分割検索キー「４０００：０１０２：０３０４：０５０６」と第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」に分割される。まず、第１の分割検索キーは第１のテーブルのエントリＡに一致し、第２のテーブルで検索する情報を得る。そして、第２の分割検索キーを第２のテーブルで検索すると、エントリＡに一致し、結果としてアドレスＡを取得する。また、アドレス「４０００：０１０２：０３０４：００００：０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」を有するパケット２の場合、検索キーであるアドレスは、第１の分割検索キー「４０００：０１０２：０３０４：００００」と第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」に分割され、第１の分割検索キーは第１のテーブルのエントリＢに一致するので、結果としてアドレスＢを取得する。
【０００８】
一方、アドレス「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：００００」を有するパケット３の場合には、検索キーであるアドレスは、第１の分割検索キー「４０００：０１０２：０３０４：０５０６」と第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：００００」に分割されるが、検索結果が得られなくなってしまう。すなわち、第１の分割検索キーは第１のテーブルのエントリＡに一致し、第２のテーブルで検索する情報を得るが、第２の分割検索キーで第２のテーブルを検索すると、第２のテーブルには上記検索条件に合致するエントリは存在せず、ミスヒットという結果になる。しかし、このパケット３は、図２４（ａ）よりエントリＢに一致するパケットであるので、実際にはアドレスＢを結果として取得しなければならない。このように、エントリＡとエントリＢとの間に包含関係が存在する場合に、検索キーを分割してＬＰＭ検索を実施すると、このようなミスヒットが生じてしまうという問題点があった。
【０００９】
この発明は、上記に鑑みてなされたもので、検索キーを分割してＬＰＭ検索を行う場合においても、正しい検索結果を得ることが可能な検索回路およびこの検索回路を使用したパケット転送装置を得ることを目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するため、この発明にかかる検索回路は、入力された検索キーを複数の分割検索キーに分割し、前記検索キー内の先頭のデータが含まれる上位の分割検索キーから対応するテーブルを用いて順に最長一致検索を行って、所望の結果情報を得る検索制御手段と、前記分割検索キーの数だけ設けられるテーブルであり、前記分割検索キーに対応する所定の結果情報を含むエントリを格納するテーブルと、を備える検索回路であって、前記テーブルは、前記検索キーの分割によって前記分割検索キーに対する結果情報が得られなくなることを回避するためのダミーエントリを有することを特徴とする。
【００１１】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかる検索回路およびパケット転送装置の好適な実施の形態を詳細に説明する。
【００１２】
実施の形態１．
図１はこの発明にかかる検索回路の構成を模式的に示すブロック図である。この検索回路は、ＬＰＭ検索を行うＣＡＭなどから構成される複数のテーブル（検索エンジン）１ａ〜１ｃ、検索キーを２以上の分割検索キーに分割して、各テーブル１ａ〜１ｃを用いて検索を実行する検索制御部２、検索回路を管理する図示しない管理装置からのエントリの追加・削除要求があったエントリ（検索キー、結果）をテーブル１ａ〜１ｃに設定する検索キー分割・タグ管理部３、エントリの包含関係などの必要な情報を管理し、それらの情報を検索キー分割・タグ管理部３による設定時に提供する包含関係検出・ダミーエントリ管理部４を備えて構成される。なお、この図１ではＣＡＭなどのテーブルは、複数個に分けて表示されているが、論理的に複数に分かれていればよい。また、３つのテーブル１ａ〜１ｃを用いる場合を示しているが、これに限られる趣旨ではない。さらに、以下の説明では、検索キーとしてパケットに格納された宛先ＩＰアドレス（アドレス）を用い、このアドレスに上記パケットを転送するための出力先を検索する場合を例に挙げるが、この検索回路の用途がこれのみに限定される訳ではない。
【００１３】
テーブル１ａ〜１ｃは、検索回路に入力された検索キー（アドレス）のＬＰＭ検索を行って、出力先の結果を得るものであり、上記検索キーを分割した数のテーブルから構成される。図２４（ａ）に示されるようにアドレスとその出力先（結果）が決定されているエントリのアドレスが複数のアドレス（以下、分割検索キー対応データという）に分割され、先頭のビットが含まれる上位の分割検索キー対応データから順に第１のテーブル、第２のテーブル、・・・にエントリとして格納される。なお、この明細書では、２つのテーブルを比較したときに、第１のテーブルに近い方のテーブルを相対的に上位のテーブルといい、第１のテーブルから遠い方のテーブルを相対的に下位のテーブルという。
【００１４】
図２は、テーブルの構成の一例を示す図である。この図２に示されるように、テーブル１は、分割検索キーに対応する長さのアドレスである分割検索キー対応データが格納される「検索対象情報」、分割検索キーが「検索対象情報」と一致する必要のあるデータの長さを示すマスク長が格納される「マスク長」、そして「検索対象情報」に格納されたエントリと一致する場合の結果が格納される「結果データ」を含む項目から構成される。「結果データ」には、マスク長でマスクされた「検索対象情報」に格納されるエントリから出力先を導くことができる場合には、その出力先が格納され、出力先を導くことができない場合には下位に存在するつぎのテーブルで検索を行う際に必要なタグが格納される。「検索対象情報」には、第１のテーブル１ａでは、分割検索キーに対応する長さのアドレスが格納されるが、第２のテーブル１ｂ以下のテーブルでは、タグに分割検索キーに対応する長さのアドレスが組み合わされた検索対象情報が格納される。
【００１５】
検索制御部２は、検索キーを２以上の分割検索キーに分割し、各テーブル１ａ〜１ｃに適切な検索を実行するためのキーを出力して、正しい検索結果を求める機能を有する。検索キーの分割検索キーへの分割は、各テーブル１ａ〜１ｃと同じ数に分割するとともに、各テーブル１ａ〜１ｃに格納されている検索対象情報内のアドレス（分割検索キー対応データ）と同じビット数で分割するように行われる。この明細書では、分割された分割検索キーの先頭のビットを含む分割検索キーから順に第１の分割検索キー、第２の分割検索キー、第３の分割検索キー、・・・とする。また、テーブルと同様に、２つの分割検索キーを比較した場合に、第１の分割検索キーに近い方の分割検索キーを相対的に上位の分割検索キーといい、第１の分割検索キーに遠い方の分割検索キーを相対的に下位の分割検索キーという。この検索制御部２は、たとえば、第１のテーブル１ａに第１の分割検索キーを出力した結果、タグを得た場合に、そのタグとつぎの第２の分割検索キーを組み合わせたものを第２のテーブル１ｂに出力する。このようにして、あるテーブルから最終的な結果であるパケットの出力先が得られると、検索処理を終了する。
【００１６】
検索キー分割・タグ管理部３は、テーブル１ａ〜１ｃへの新たなエントリ（分割検索キー対応データ、結果データ）の追加や削除要求があった場合に、包含関係検出・ダミーエントリ管理部４の指示に基づいて、検索制御部２とテーブル１ａ〜１ｃで正しく検索できるように設定する機能を有する。
【００１７】
包含関係検出・ダミーエントリ管理部４は、テーブル１ａ〜１ｃへのエントリの追加がある場合に、追加されるエントリとテーブル１ａ〜１ｃ内のエントリとの間の包含関係などを調査して、正しく検索を行うことが可能か否かを管理し、必要な場合には、上記包含関係などの必要な情報に基づいてダミーエントリの追加や削除などの指示を、検索キー分割・タグ管理部３に提供する機能を有する。
【００１８】
なお、ダミーエントリとは、上述した従来のＬＰＭ検索の問題点で説明したパケット３のような検索結果がミスヒットとなることを防ぎ、本来の転送先を得ることができるようにするために、テーブル１に挿入されるエントリである。具体的には、ダミーエントリは、追加するエントリとテーブル１内のエントリの間に包含関係がある場合に、包含されている方のエントリの結果データに格納されているタグに任意のアドレスを付加した「分割対象情報」、上記タグの長さをマスク長とした「マスク長」、包含する方のエントリの最終的な結果情報である出力先を格納する「結果データ」を含むデータ構造を有する。
【００１９】
つぎに、図３〜図１２を参照して、包含関係検出・ダミーエントリ管理部４の動作について説明する。包含関係検出・ダミーエントリ管理部４は、既にテーブル１ａ〜１ｃに格納されているエントリとの包含関係を考慮してエントリの追加と削除の２つの処理を行うが、ここでは、最初にエントリの追加について説明し、つぎにエントリの削除について説明する。
【００２０】
図３は、エントリ追加時の全体の処理手順を示すフローチャートである。まず、管理装置からエントリ追加の要求があると、包含関係検出・ダミーエントリ管理部４は、追加するエントリの検索キーを、それぞれのテーブル１ａ〜１ｃで規定された分割検索キー長の第１〜第３の分割検索キー対応データに分割する（ステップＳ１）。つぎに、追加するエントリが、他のエントリとどのような包含関係になっているか判定し、ダミーエントリが必要か否か、また必要な場合にはどのようなダミーエントリが必要かを決定する（ステップＳ２）。つぎに、それぞれのテーブル１ａ〜１ｃにエントリを追加し（ステップＳ３）、ステップＳ２の結果により、エントリ追加処理を終了するか、ダミーエントリを追加するかの判定を行う（ステップＳ４）。ダミーエントリの追加が必要でないと判定された場合（ステップＳ４でＮｏの場合）には、そのまま処理を終了し、ダミーエントリの追加が必要と判定された場合（ステップＳ４でＹｅｓの場合）には、ステップＳ２で得られた結果からダミーエントリの追加を行い（ステップＳ５）、処理を終了する。
【００２１】
ここで、ステップＳ２における包含関係検出処理の詳細について説明する。図４〜図８は、包含関係検出の判定内容を示す図である。なお、これらの包含関係検出の判定内容を示す図は、後述するエントリを削除する場合に行われる包含関係検出の判定と同じであるので、図中には、両者についての判定がまとめて記載されている。図４は、追加されるエントリと、既にテーブルに格納されているエントリとの包含関係に基づいて、ダミーエントリが必要か否かを判定するものである。この包含関係の判定は、追加するエントリの検索キーを分割する前の状態で行う。追加するエントリ（以下、追加エントリという）が他のエントリを包含しておらず、かつ他のエントリに包含されていない場合には、ダミーエントリは必要がない。
【００２２】
また、追加エントリが他のエントリを包含しておらず、かつ他のエントリに包含されている場合には、図４に示される包含関係１に対応してダミーエントリの有無が決定される。図５は、包含関係１における追加エントリのマスク長と、追加エントリを包含するエントリのマスク長との関係からダミーエントリが必要か否かの判定結果を示す図である。ここで、領域１とは、マスク長が第１のテーブル１ａに格納される分割検索キー対応データの長さ（以下、第１の分割検索キー長という）以下である場合をいい、領域２とは、マスク長が、第１の分割検索キー長より長く、第１の分割検索キー長と第２のテーブル１ｂに格納される分割検索キー対応データの長さ（以下、第２の分割検索キー長という）の和以下である場合をいい、領域３とは、マスク長が、第１の分割検索キー長と第２の分割検索キー長の和よりも長い場合をいう。また、追加エントリが複数のエントリに包含されている場合には、最もマスク長の長いエントリに対して、この図５の判定を適用する。
【００２３】
たとえば、追加エントリのマスク長、追加エントリを包含するエントリのマスク長ともに領域１にある場合には、ダミーエントリの追加の必要はない。また、追加エントリのマスク長が領域２にあり、追加エントリを包含するエントリのマスク長が領域１にある場合には、図８に示されるダミーエントリの「追加１−１」の処理が必要と判断される。図８は、ダミーエントリの追加判定の結果とその処理内容を規定する図である。たとえば、上記「追加１−１」の場合には、追加エントリを包含しているエントリのダミーエントリを第２のテーブル１ｂに追加する処理が選択される。
【００２４】
また、図４で、追加エントリが他のエントリを包含しており、かつ他のエントリに包含されていない場合には、図６に示される包含関係２に対応してダミーエントリの有無が決定される。この図６は、追加エントリのマスク長と、追加エントリが包含しているエントリのマスク長との関係からダミーエントリが必要か否かを判定するものである。そして、この判定の結果、図８に規定されるダミーエントリの追加または変更処理が必要と判断される。ここで、追加エントリが、複数のエントリを二重に包含している場合は、最もマスク長の短いエントリに対して、この図６の判定を適用する。また、追加エントリが、複数のエントリを包含しているが、二重に包含している関係にはない場合には、それぞれのエントリに対して図６の判定を適用する（すなわち、複数のエントリＡ，Ｂと追加エントリＣが、Ａ⊂Ｃ，Ｂ⊂ＣでかつＡ⊆ＢでもなくＢ⊆Ａでもない場合には、エントリＡ、エントリＢの両者に対して図６の判定を行う）。
【００２５】
さらに図４で、追加エントリが他のエントリを包含しており、かつ他のエントリに包含されている場合には、図７に示される包含関係３に対応してダミーエントリの有無が決定される。この図７は、追加エントリのマスク長と、追加エントリが包含しているエントリのマスク長と、追加エントリが包含されるエントリのマスク長の関係からダミーエントリが必要か否かを判定するものである。そして、この判定の結果、図８に規定されるダミーエントリの追加または変更処理が必要と判断される。ここで、追加エントリが、複数のエントリを二重に包含している場合は、最もマスク長の短いエントリに対して、この図７の判断を適用する。また、追加エントリが、複数のエントリを包含しているが、二重に包含している関係にはない場合には、それぞれのエントリに対して図７の判定を適用する（すなわち、複数のエントリＡ，Ｂと追加するエントリＣが、Ａ⊂Ｃ，Ｂ⊂ＣでかつＡ⊆ＢでもＢ⊆Ａでもない場合には、エントリＡ、エントリＢの両者に対して図７の判定を行う）。さらに、追加エントリが複数のエントリに包含されている場合には、最もマスク長の長いエントリに対して、この図７の判定を適用する。
【００２６】
これらのように、追加エントリと既にテーブル１ａ〜１ｃに格納されているエントリとの包含関係の判定にあたっては、エントリ同士のマスク長も考慮して行われる。以上のような包含関係を求めるアルゴリズムは様々なものが考えられるが、例えば特開平１１−１０３３１３号公報に示された方法などを適用することができる。
【００２７】
つぎに、上述した図３のステップＳ３におけるエントリ追加処理の詳細について説明する。ここでは、既に登録されているエントリの追加が行われないように管理装置でチェックされているという前提での処理手順を示す。
【００２８】
図９は、エントリ追加の処理手順を示すフローチャートである。まず、包含関係検出・ダミーエントリ管理部４は、エントリの追加のために、該エントリの第１の分割検索キー対応データと同じエントリが第１のテーブルにあるか否かを判定する（ステップＳ１０１）。このとき、第１の分割検索キー対応データだけでなく、マスク長も考慮することが通常の検索とは異なる（以下では、エントリの設定に関する処理の場合、エントリの有無の判定はマスク長も考慮しているものとする）。判定の結果、第１の分割検索キー対応データと同じエントリがないと判定された場合（ステップＳ１０１でＮｏの場合）には、追加エントリのマスク長の判定を行う（ステップＳ１０２）。追加エントリのマスク長が、“マスク長≦第１の分割検索キー長（領域１）”である場合（ステップＳ１０２でＹｅｓの場合）には、第１のテーブル１ａに、エントリを追加する（ステップＳ１０３）。このフローは追加エントリのマスク長が第１の分割検索キー長以下の場合の通常のフローである。
【００２９】
また、ステップＳ１０２で、マスク長が領域１でないと判定された場合（ステップＳ１０２でＮｏの場合）には、包含関係検出・ダミーエントリ管理部４は、使用していない第２のテーブル１ｂ用のタグ（以下、タグ１とする）を取得し（ステップＳ１０４）、第１の分割検索キー対応データを「検索対象情報」とし、取得したタグ１を「結果データ」とするエントリとして第１のテーブル１ａに追加する（ステップＳ１０５）。つぎに、追加エントリのマスク長の判定を行う（ステップＳ１０６）。このとき、追加エントリのマスク長が“第１の分割検索キー長（領域１）＜マスク長≦第１の分割検索キー長＋第２の分割検索キー長（領域２）”であると判定された場合（ステップＳ１０６でＹｅｓの場合）には、第２のテーブル１ｂに、タグ１と第２の分割検索キー対応データの組合せを「検索対象情報」とし、追加エントリの結果を「結果データ」として、エントリを追加する（ステップＳ１０７）。このフローは、追加エントリのマスク長が第１の分割検索キー長より長く、第１の分割検索キー長と第２の分割検索キー長の合計以下の場合で、かつ第１の分割検索キーと同じエントリが未だ登録されていない場合のフローである。
【００３０】
上記ステップＳ１０６で、追加エントリのマスク長が領域２でないと判定された場合（ステップＳ１０６でＮｏの場合）には、包含関係検出・ダミーエントリ管理部４は、使用していない第３のテーブル１ｃ用のタグ（以下、タグ２とする）を取得し（ステップＳ１０８）、タグ１と第２の分割検索キー対応データの組合せを「検索対象情報」とし、取得したタグ２を「結果データ」とするエントリとして第２のテーブル１ｂに追加する（ステップＳ１０９）。そして、取得したタグ２と第３の分割検索キー対応データを「検索対象情報」として、追加エントリの結果を「結果データ」として、第３のテーブル１ｃに追加する（ステップＳ１１０）。このフローは、追加エントリのマスク長が第１の分割検索キー長と第２の分割検索キー長の合計より長い場合で、かつ第１の分割検索キー対応データ＋第２の分割検索キー対応データと同じエントリが未だ登録されていない場合のフローである。
【００３１】
一方、ステップＳ１０１で、既に第１のテーブル１ａにエントリが存在する場合（ステップＳ１０１でＹｅｓの場合）には、そのエントリの結果がタグか否かを判定する（ステップＳ１１１）。エントリの結果がタグでないと判定された場合（ステップＳ１１１でＮｏの場合）には、このエントリを第１のテーブル１ａから削除する（ステップＳ１１２）。なお、このエントリは、マスク長が領域１の長さと等しい場合で、後でこのエントリ用のダミーエントリの追加を行う。その後、上述したステップＳ１０２以降の処理を行う。このフローは既に第１のテーブル１ａに追加するエントリと同じエントリがあり、かつそのエントリのマスク長が第１の分割検索キー長と等しい特別な場合のフローである。
【００３２】
なお、このような状況で、第１の分割検索キー対応データが等しく、マスク長が領域２または３の場合、元のエントリに、タグ情報を「結果データ」として登録しなければならないため、上記ステップＳ１１２でエントリを削除している。ただし、ここではエントリを削除しているが、後で行われるダミーエントリ追加処理によって、削除したエントリの代わりのエントリを第２のテーブル１ｂに追加する処理を行う。
【００３３】
また、ステップＳ１１１で、エントリの結果がタグであると判定された場合（ステップＳ１１１でＹｅｓの場合）には、包含関係検出・ダミーエントリ管理部４は、そのタグ値（以下、このタグ値もタグ１とする）を第１のテーブル１ａから取得する（ステップＳ１１３）。つぎに、追加エントリのマスク長の判定を行う（ステップＳ１１４）。追加エントリのマスク長が領域１でないと判定された場合（ステップＳ１１４でＮｏの場合）には、第２のテーブル１ｂに取得したタグ１＋第２の分割検索キー対応データのエントリがあるか否かの判定を行う（ステップＳ１１５）。第２のテーブル１ｂに取得したタグ１＋第２の分割検索キー対応データのエントリがないと判定された場合（ステップＳ１１５でＮｏの場合）には、第２のテーブル１ｂにおけるタグ１の使用数をインクリメントして、上述したステップＳ１０６以降の処理を行う。このフローは、マスク長が第１の分割検索キー長より長い場合で、第１の分割検索キー対応データと同じ値のエントリが既に登録されている場合でかつ、第２の分割検索キー対応データに関しては、同じ値のエントリが未だ登録されていない場合のフローである。
【００３４】
上述したステップＳ１１５の判定で、第２のテーブル１ｂにタグ１＋第２の分割検索キー対応データのエントリがあると判定された場合（ステップＳ１１５でＹｅｓの場合）には、エントリの結果がタグか否かを判断する（ステップＳ１１７）。タグでないと判断された場合（ステップＳ１１７でＮｏの場合）には、このエントリを第２のテーブル１ｂから削除する（ステップＳ１１８）。その後、上述したステップＳ１０６以降の処理を行う。このフローは、既に第１と第２のテーブル１ａ，１ｂにエントリがあり、かつそのエントリのマスク長が第１の分割検索キー長＋第２の分割検索キー長の合計と等しい場合のフローである。
【００３５】
また、ステップＳ１１７でエントリの結果がタグであると判定された場合（ステップＳ１１７でＹｅｓの場合）には、そのタグ値（以下、このタグ値もタグ２とする）を取得する（ステップＳ１１９）。つぎに、追加エントリのマスク長の判定を行う（ステップＳ１２０）。追加エントリのマスク長が領域２でない場合、すなわち領域３である場合（ステップＳ１２０でＮｏの場合）には、第３のテーブル１ｃにおけるタグ２の使用数をインクリメントして、ステップＳ１１０の処理を行う。このフローは、マスク長が第１の分割検索キー長＋第２の分割検索キー長の合計より長い場合で、かつ第１と第２の分割検索キー対応データまで同じ値のエントリが登録されている場合である。
【００３６】
一方、ステップＳ１２０で、追加エントリのマスク長が領域２であると判定された場合（ステップＳ１２０でＹｅｓの場合）には、エントリの追加を行わず、そのまま処理が終了する。このエントリについての処理は、ダミーエントリ追加のときに行われる。
【００３７】
また、ステップＳ１１４で、追加エントリのマスク長が領域１であると判定された場合（ステップＳ１１４でＹｅｓの場合）にも、エントリの追加を行わず、そのまま処理が終了する。このエントリについての処理は、ダミーエントリ追加の時に行われる。
【００３８】
以上のようにして、第１〜第３のテーブル１ａ〜１ｃにエントリが追加される。
【００３９】
つぎに、図３のステップＳ５におけるダミーエントリ追加処理について説明する。この図８は、図５〜図７の包含関係の判定処理で行われた結果に対するダミーエントリの追加処理内容を規定している。図９に示されるエントリ追加処理の終了後、追加エントリに関するステップＳ２における包含関係の判定結果と図８の処理内容に基づいて、各テーブル１ａ〜１ｃについてダミーエントリの追加処理または変更処理が行われる。
【００４０】
以上のようにして、新たなエントリがテーブル１ａ〜１ｃに追加される際に、追加エントリと既にテーブルに格納されているエントリとの間の包含関係を考慮しないために生じる検索時のミスヒットを防ぐためのダミーエントリが必要に応じて追加されるようにしている。
【００４１】
つぎに、包含関係検出・ダミーエントリ管理部４によるエントリの削除について説明する。図１０は、エントリ削除時の全体の処理手順を示すフローチャートである。まず、管理装置からエントリの削除要求があると、検索キーをそれぞれテーブル１ａ〜１ｃで規定された分割検索キー長を有する第１〜第３の分割検索キー対応データに分割する（ステップＳ１１）。つぎに、エントリを削除したことでダミーエントリが不要になるかどうか、他のエントリとの包含関係に基づいて判定し（ステップＳ１２）、それぞれのテーブル１ａ〜１ｃのエントリを削除する（ステップＳ１３）。
【００４２】
その後、ステップＳ１２の結果に基づいて、エントリ削除処理を終了するか、さらにダミーエントリを削除するかの判定を行う（ステップＳ１４）。ダミーエントリの削除がない場合（ステップＳ１４でＮｏの場合）には、そのまま処理が終了する。また、ダミーエントリの削除がある場合（ステップＳ１４でＹｅｓの場合）には、不要なダミーエントリの削除を行い（ステップＳ１５）、処理を終了する。なお、ステップＳ１２における包含関係検出処理は、エントリの追加処理において図４〜図７で説明した場合と同じであるので、その説明を省略する。ただし、この場合には、追加処理内容を規定している図８ではなく、削除処理内容を規定している図１２が使用される。
【００４３】
ここで、上述したステップＳ１３におけるエントリ削除処理の詳細について説明する。なお、未登録のエントリに対する削除が行われないように管理装置でチェックされているという前提での処理手順を示す。
【００４４】
図１０は、エントリ削除処理の手順を示すフローチャートである。まず、エントリを削除するために、包含関係検出・ダミーエントリ管理部４は、削除するエントリについて、第１のテーブル１ａにおける該エントリの結果がタグであるか否かを判定する（ステップＳ２０１）。第１のテーブル１ａにおけるエントリの結果がタグでないと判定された場合（ステップＳ２０１でＮｏの場合）には、第１の分割検索キー対応データのエントリを第１のテーブル１ａから削除し（ステップＳ２１３）、エントリ削除処理を終了する。このフローは、削除するエントリのマスク長が領域１である場合の通常のフローある。
【００４５】
つぎに、ステップＳ２０１で、第１のテーブル１ａにおけるエントリの結果がタグであると判定された場合（ステップＳ２０１でＹｅｓの場合）には、包含関係検出・ダミーエントリ管理部４は、削除するエントリのマスク長の判定を行う（ステップＳ２０２）。ここで、削除するエントリのマスク長が領域１でないと判定された場合（ステップＳ２０２でＮｏの場合）には、第２のテーブル１ｂのエントリの結果がタグであるか否かを判定する（ステップＳ２０３）。第２のテーブル１ｂのエントリの結果がタグでないと判断された場合（ステップＳ２０３でＮｏの場合）には、第２の分割検索キー対応データのエントリを第２のテーブル１ｂから削除する（ステップＳ２０９）。その後、第２のテーブル１ｂにおけるタグ１の使用数をディクリメントし（ステップＳ２１０）、タグ１の使用数が０になったか否かを判定する（ステップＳ２１１）。タグ１の使用数が０になった場合（ステップＳ２１１でＹｅｓの場合）には、該当するタグ１を解放し（ステップＳ２１２）、上述したステップＳ２１３の処理を行う。このフローは、削除するエントリのマスク長が領域２で、第１の分割検索キー対応データが同じ値のエントリが他にない場合のフローである。
【００４６】
一方、ステップＳ２１１でタグ１の使用数が０でないと判定された場合（ステップＳ２１１でＮｏの場合）には、そのまま処理を終了する。このフローは、削除するエントリのマスク長が領域２で、第１の分割検索キー対応データが同じ値のエントリが他にある場合のフローである。
【００４７】
また、ステップＳ２０３で、第２のテーブル１ｂのエントリの結果がタグであると判定された場合（ステップＳ２０３でＹｅｓの場合）には、削除するエントリのマスク長の判定を行う（ステップＳ２０４）。ここでマスク長が領域２でないと判定されると（ステップＳ２０４でＮｏの場合）、第３のテーブル１ｃからエントリを削除する（ステップＳ２０５）。その後、第３のテーブル１ｃにおけるタグ２の使用数をディクリメントし（ステップＳ２０６）、タグ２の使用数が０になったか否か判定する（ステップＳ２０７）。タグ２の使用数が０になった場合（ステップＳ２０７でＹｅｓの場合）には、該当するタグ２を解放し（ステップＳ２０８）、上述したステップＳ２０６以降の処理を行う。このフローは、削除するエントリのマスク長が領域３のエントリで、第２の分割検索キー対応データまでが同じ値のエントリが他にない場合のフローである。
【００４８】
一方、ステップＳ２０７でタグ２の使用数が０でないと判定された場合（ステップＳ２０７でＮｏの場合）には、そのまま処理を終了する。このフローは、削除するエントリのマスク長が領域３で、第２の分割検索キー対応データまで同じ値のエントリが他にある場合のフローである。
【００４９】
また、ステップＳ２０４でマスク長が領域２であると判断された場合（ステップＳ２０４でＹｅｓの場合）には、そのまま処理を終了する。このフローは、削除するエントリのマスク長が第１の分割検索キー長＋第２の分割検索キー長の合計と等しい場合で、第２の分割検索キー対応データまで同じ値のエントリが他にある場合のフローである。この削除するエントリ自身はダミーエントリとして登録されているので、ダミーエントリ削除の処理工程で削除される。
【００５０】
上述したステップＳ２０２で、マスク長が領域１であると判断された場合（ステップＳ２０２でＹｅｓの場合）にも、そのまま処理を終了する。このフローは、削除するエントリのマスク長が第１の分割検索キー長の合計と等しい場合で、第１の分割検索キー対応データと同じ値のエントリが他にある場合のフローである。このフローも、このエントリ自身はダミーエントリ削除の処理工程で削除される。
【００５１】
以上のようにして、第１〜第３のテーブル１ａ〜１ｃからエントリが削除される。
【００５２】
つぎに、図１０のステップＳ１５におけるダミーエントリ削除処理について説明する。図１２は、ダミーエントリの削除内容を示す図である。この図１２は、図４〜図７の包含関係の判定処理で行われた結果に対するダミーエントリの削除処理内容を規定している。図１１に示されるエントリ削除処理の終了後、削除するエントリに関するステップＳ１２における包含関係の判定結果と図１２の処理内容に基づいて、各テーブルについてダミーエントリの削除処理または変更処理が行われる。
【００５３】
以上のようにして、テーブル１ａ〜１ｃからエントリが削除される際に、削除されるエントリと既にテーブルに格納されているエントリとの間の包含関係を含めてダミーエントリを削除するようにしている。
【００５４】
なお、上述した説明では、検索キーを３分割した場合を例に挙げたが、検索キーを２分割または４分割以上する場合でも同様の処理手順でエントリの追加または削除処理を実現することができる。
【００５５】
ここで、ダミーエントリの追加処理、削除処理およびダミーエントリが追加された場合の検索処理について具体的な例を挙げて説明する。まず、ダミーエントリの追加処理ついて、１つのエントリが既に格納されている２つのテーブルに、新たにエントリを追加する場合を例に挙げて説明する。
【００５６】
図１３は、テーブルが２つの場合のエントリ追加の様子を示す図であり、図１３（ａ）は、新たなエントリを追加する前のテーブルの様子を示している。ここでは、第１および第２のテーブル１ａ，１ｂには、図２４（ａ）のテーブルのエントリＡに対応するエントリが格納されている。これらのテーブル１ａ，１ｂに図２４（ａ）のテーブルのアドレス（検索キー）が「４０００：０１０２：０３０４：００００：００００：００００：００００：００００」であり、マスク長が４８ビットであり、転送先がアドレスＢであるエントリＢを追加する場合には、まず、包含関係検出・ダミーエントリ管理部４は、アドレス（検索キー）を第１の分割検索キー「４０００：０１０２：０３０４：００００」と第２の分割検索キー「００００：００００：００００：００００」に分割する。
【００５７】
追加エントリとテーブル１ａ，１ｂに格納されているエントリとの包含関係を調べると、追加エントリはエントリＡを包含しているが他のエントリを包含していないので、図４から包含関係２に該当する。また、追加エントリのマスク長（４８ビット）は第１の分割検索キー長（６４ビット）以下であり、エントリＡのマスク長は１２８ビットで領域２にあることから、図７の「ダミーエントリ追加２−１」に該当する。
【００５８】
第１のテーブル１ａには、第１の分割検索キー対応データと同じエントリが存在せず（ステップＳ１０１でＮｏの場合）、またマスク長（４８ビット）は領域１にあるので（ステップＳ１０２でＹｅｓの場合）、第１のテーブル１ａに第１の分割検索キー対応データが追加される。ここでは、図１３（ｂ）に示されるように、「検索対象情報」に「４０００：０１０２：０３０４：００００」が追加され、「マスク長」に「４８」が追加され、「結果データ」に「アドレスＢ」が追加される。
【００５９】
そして、包含関係の結果は「ダミーエントリ追加２−１」であり、これは図８から、「第２のテーブルに、追加したエントリのダミーエントリ追加」の処理を行う。したがって、第２のテーブル１ｂには、「検索対象情報」が「タグα＋００００：００００：００００：００００」であり、「マスク長」がタグαのビット数である「ｎ」であり、そして「結果データ」が「アドレスＢ」であるダミーエントリが追加される。その結果が図１３（ｃ）に示されている。なお、「検索対象情報」のタグαの後に付される数値は、「マスク長」がタグαのビット数であるので、任意の数値に設定することができる。
【００６０】
つぎに、２つのテーブルからエントリを削除する場合について、図１４を参照しながら説明する。図１４は、２つのテーブルからエントリを削除する様子を示す図であり、図１４（ａ）は図１３（ｃ）の状態に相当する。上記したように、削除するエントリＢは、テーブル１ａ，１ｂ内の他のエントリに対して図４の包含関係２に該当し、また、図１２の「ダミーエントリ削除２−１」に該当する。
【００６１】
第１のテーブル１ａにおける第１の分割検索キー対応データのエントリＢの「結果データ」はタグでないので（ステップＳ２０１でＮｏの場合）、第１のテーブル１ａから第１の分割検索キー対応データのエントリが削除される（ステップＳ２１３）。この様子が図１４（ｂ）に示されている。
【００６２】
また、図１２の「ダミーエントリ削除２−１」から「第２のテーブルに、削除したエントリのダミーエントリ削除」の処理が実行される。したがって、第１のテーブル１ａで削除したエントリのダミーエントリ、すなわち、「検索対象情報」が「タグα＋００００：００００：００００：００００」であり、「マスク長」が「ｎ」であり、「結果データ」が「アドレスＢ」であるダミーエントリが第２のテーブル１ｂから削除される。その結果が図１４（ｃ）に示されている。
【００６３】
つぎに、ダミーエントリを有するテーブルを用いた検索の手順について、図１５を参照しながら説明する。この図１５は、図２４に示した従来例に、実施の形態１を適用した場合の例であり、図１３（ｃ）と同一のものであり、第２のテーブル１ｂに上記検索回路によって挿入されたダミーエントリが格納されている。このダミーエントリは、タグ以外の部分は比較対象としないように、マスク長が設定されており、「結果データ」にはエントリＢと同じ結果が格納されている。このようにすることで、図２４の従来例では正しく検索ができなかった検索キーが「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：００００」であるパケット３も、第１の分割検索キー「４０００：０１０２：０３０４：０５０６」は、第１のテーブル１ａのエントリＡにヒットしてタグαを取得し、つぎに、タグα＋第２の分割検索キー「タグα＋０７０８：０９０ａ：０ｂ０ｃ：００００」は、マスク長がタグαの長さである第２のテーブル１ｂのダミーエントリにヒットするので、最終的に正しい結果であるアドレスＢを取得することが可能となる。
【００６４】
このようにダミーエントリを追加することで、検索制御部２およびテーブル１は、従来と全く同じ処理で長い検索キーを分割したＬＰＭ検索でも正しく検索ができるようになる。
【００６５】
この実施の形態１によれば、新たに追加／削除を行うエントリと、テーブル１に格納されているエントリの包含関係を求め、その結果、両者の間に包含関係が存在する場合には、テーブル１ａ〜１ｃにダミーエントリの追加／削除、変更を行うように構成したので、複数に分割したＬＰＭ検索でも正しく検索を行うことが可能になる。
【００６６】
実施の形態２．
実施の形態１では、ダミーエントリを追加することで、複数に分割したＬＰＭ検索が正しくできるようにしたものであるが、この実施の形態２では、エントリの内容にフラグを追加し、検索時にこのフラグの値によって結果を選択することで、複数に分割したＬＰＭ検索でも正しく検索を行うことが可能な検索回路について説明する。
【００６７】
図１６は、この発明にかかる検索回路のテーブルの実施の形態２の構成を示す図である。このテーブルには、検索を行う際のキーとなる「検索キー」と、この検索キーに一致するエントリに対する結果を格納する「検索結果」の項目からなる。「検索キー」は、タグと分割検索キーの組合せからなる「検索対象情報」、マスク長を示す「マスク長」の項目を含んで構成される。また、「検索結果」は、つぎのテーブルの検索を行なうか否かを示す「処理継続フラグ」、つぎのテーブルを検索するときのキーの一部となるタグを格納する「タグ」、検索の最終結果が格納される「結果データ」、その結果データが有効か否かを示す「データ有効フラグ」の項目を含んで構成される。なお、項目「検索対象情報」は、最上位のテーブルの場合には、分割検索キー対応データのみが格納される。
【００６８】
また、以下の説明では、「処理継続フラグ」に格納されるフラグにおいて、「１」は、つぎのテーブルの検索を行う場合を示しており、「１」でない数値（たとえば、「０」）は、つぎのテーブルの検索を行わない場合を示している。さらに、「データ有効フラグ」に格納されるフラグにおいて、「１」は、有効を示し、「１」でない数値（たとえば、「０」）は、無効を示している。なお、この定義は、この明細書の説明においてなされるものであり、上記と異なるようにそれぞれのフラグを定義してもよい。
【００６９】
この実施の形態２では、「データ有効フラグ」を有効にセットし、「結果データ」にダミーエントリで追加した内容のデータを登録することによって、ダミーエントリを追加した場合と同じ効果を得られるようにしている。なお、この実施の形態２における検索回路のその他の構成は、上述した実施の形態１の図１と同一であるので、その説明を省略している。
【００７０】
この実施の形態２におけるエントリの追加・削除の処理に関しては、実施の形態１とほぼ同じ手順で処理が行われるが、ダミーエントリを追加する場合の処理が、「データ有効フラグ」を有効にして、包含されているエントリの「結果データ」に、包含しているエントリの結果データ（結果情報）を登録する処理に代わる点と、ダミーエントリを削除する場合の処理が、「データ有効フラグ」を無効にする処理に代わる点が異なる。
【００７１】
つぎに、この検索回路による検索方法について説明する。図１７は、この発明にかかる検索回路の実施の形態２による検索の処理手順を示すフローチャートである。この説明でも、検索キーを３分割した場合を例に挙げる。まず、検索制御部２は、検索キーを分割して得られる第１の分割検索キーで第１のテーブル１ａの検索を行い（ステップＳ３０１）、エントリがあるか否かを判定する（ステップＳ３０２）。エントリがある場合（ステップＳ３０２でＹｅｓの場合）には、そのエントリの処理継続フラグが１であるか否かを判定し（ステップＳ３０３）、処理継続フラグが１の場合（ステップＳ３０３でＹｅｓの場合）には、その結果得られるタグと第２の分割検索キーの組合せで第２のテーブル１ｂを用いて検索し（ステップＳ３０４）、第２のテーブル１ｂにエントリがあるか否かを判定する（ステップＳ３０５）。第２のテーブル１ｂにエントリがある場合（ステップＳ３０５でＹｅｓの場合）には、そのエントリの処理継続フラグが１であるか否かを判定し（ステップＳ３０６）、処理継続フラグが１の場合（ステップＳ３０６でＹｅｓの場合）には、その結果得られるタグと第３の分割検索キーの組合せで第３のテーブル１ｃを検索し（ステップＳ３０７）、第３のテーブル１ｃにエントリがあるか否かを判定する（ステップＳ３０８）。第３のテーブル１ｃにエントリがある場合（ステップＳ３０８でＹｅｓの場合）には、この３回目検索結果のデータ有効フラグが１であるか否かを判定し（ステップＳ３０９）、データ有効フラグが１である場合には、３回目の検索結果を有効な結果として出力し（ステップＳ３１０）、検索処理を終了する。
【００７２】
また、ステップＳ３０６で第２のテーブル１ｂのエントリの処理継続フラグが１でない場合（ステップＳ３０６でＮｏの場合）、またはステップＳ３０８で第３のテーブル１ｃにエントリがない場合（ステップＳ３０８でＮｏの場合）には、２回目検索結果のデータ有効フラグが１であるか否かを判定する（ステップＳ３１１）。２回目検索結果のデータ有効フラグが１の場合（ステップＳ３１１でＹｅｓの場合）には、２回目の検索結果を有効な結果として出力し（ステップＳ３１２）、検索処理を終了する。
【００７３】
さらに、ステップＳ３０３で第１のテーブル１ａのエントリの処理継続フラグが１でない場合（ステップＳ３０３でＮｏの場合）、ステップＳ３０５で第２のテーブル１ｂにエントリがない場合（ステップＳ３０５でＮｏの場合）、またはステップＳ３１１で２回目検索結果のデータ有効フラグが１でない場合（ステップＳ３１１でＮｏの場合）には、１回目検索結果のデータ有効フラグが１であるか否かを判定する（ステップＳ３１３）。１回目検索結果のデータ有効フラグが１の場合（ステップＳ３１３でＹｅｓの場合）には、１回目の検索結果を有効な結果として出力し（ステップＳ３１４）、検索処理を終了する。
【００７４】
また、ステップＳ３０２で第１のテーブル１ａにエントリがない場合（ステップＳ３０２でＮｏの場合）、ステップＳ３０９で３回目検索結果のデータ有効フラグが１でない場合（ステップＳ３０９でＮｏの場合）、またはステップＳ３１３で１回目検索結果のデータ有効フラグが１でない場合（ステップＳ３１３でＮｏの場合）には、結果はミスヒットとして出力し（ステップＳ３１５）、検索処理を終了する。
【００７５】
このような手順で処理を行うことによって、たとえばパケットが入力されてきたときの検索で、１回目の検索でミスヒットになった場合（ステップＳ３０２でＮｏの場合）はミスヒットとするが、２回目や３回目の検索（ステップＳ３０４，Ｓ３０７）で、ミスヒットになった場合（ステップＳ３０５，Ｓ３０８のそれぞれでＮｏの場合）は、それより前の検索結果のデータ有効フラグが有効かどうかを判断し（ステップＳ３１１，Ｓ３１３）、その結果が無効の場合にはミスヒットとし、有効の場合にはその検索した結果を最終的な結果として出力することが可能となる。なお、検索は、１回目を除き前の検索で処理継続フラグ＝１の場合（ステップＳ３０３，Ｓ３０６のそれぞれでＹｅｓの場合）に行なう（ステップＳ３０１，Ｓ３０４，Ｓ３０７）。
【００７６】
なお、上述した説明では、検索キーを３分割した場合を例に挙げたが、検索キーを２分割または４分割以上する場合でも同様の処理手順でエントリの追加または削除処理と、検索処理を実現することができる。
【００７７】
図１８は、図１３で説明した例をこの実施の形態２の場合に適用した場合を示す図である。この図１８に示されるように、エントリＡ，Ｂの分割検索キー対応データの間に包含関係がある場合に、第１のテーブル１ａから得られる包含されるエントリＡの「タグ」に、第２のテーブル１ｂでのつぎの検索で使用するタグを格納するとともに、「結果データ」に、包含するエントリＢの結果データ（結果情報）であるアドレスＢを格納し、「データ有効フラグ」を有効（１）にする。このようなデータ構造によって、上述したアドレス「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：００００」を有するパケット３の場合、第１の分割検索キー「４０００：０１０２：０３０４：０５０６」は第１のテーブル１ａのエントリＡに一致するので、「タグ」としてタグαを取得し、「処理継続フラグ」が１であるので、さらに第２のテーブル１ｂでの検索を継続する。しかし、第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：００００」は第２のテーブル１ｂのエントリに一致するものがないので、第１のテーブル１ａに戻って、「データ有効フラグ」が１（有効）であるので、その「結果データ」に格納されているアドレスＢをパケット３の結果とすることで正しい検索を行うことができる。
【００７８】
この実施の形態２によれば、新たに追加／削除を行うエントリの包含関係を求め、その判定結果からデータ有効フラグおよび結果のデータをテーブル１ａ〜１ｃに登録するように構成したので、検索時にミスヒットになった場合でも、それより前の検索結果のデータ有効フラグが有効である場合には、検索結果を判断することができるようになる。その結果、複数に分割したＬＰＭ検索でも正しく検索することができる。
【００７９】
実施の形態３．
この実施の形態３では、実施の形態１，２で説明した検索回路で、検索のパイプライン処理を実現するための検索制御ブロック２を複数備えたものを、パケット転送装置に適用した場合について説明する。
【００８０】
図１６は、この発明にかかるパケット転送装置の全体の構成を示すブロック図である。このパケット転送装置は、物理レイヤの終端やパケットの転送先の検索などを行なう複数のインタフェース１０ａ，１０ｂ，・・・と、それぞれのインタフェース１０ａ，１０ｂ，・・・を接続し、パケットの交換を行うスイッチ１１を備えて構成される。また、インタフェース１０ａ，１０ｂ，・・・は、物理レイヤの終端を行なう物理レイヤ処理部１２、受信したパケットの転送先などを求める検索を行なう受信側パケット処理部１３、スイッチ１１から送信されるパケットのカプセル化などを行なう送信側パケット処理部１４を備えて構成される。
【００８１】
図１７は、受信側パケット処理部の構成を示すブロック図である。この図１７に示されるように、受信側パケット処理部１３は、物理レイヤ処理部１２から送られてくるパケットを受信し、ヘッダのチェックなどを行なうパケット入力部２０、パケットのヘッダから検索に必要な情報を抽出するヘッダ抽出部２１、抽出されたヘッダからパケットの出力先を検索する検索回路２２、検索結果をパケットに追加（挿入）するヘッダ挿入部２３、パケットをスイッチ１１が交換できるフォーマットに変換するパケット出力部２４を備えて構成される。
【００８２】
検索回路２２は、ＣＡＭなどから構成される第１〜第３のテーブル（検索エンジン）１ａ〜１ｃ、検索キーを分割して各テーブル１ａ〜１ｃに適切なキーを出力することで、正しい検索結果を求める第１〜第３の検索制御部２ａ〜２ｃを備えて構成される。この第１〜第３の検索制御部２ａ〜２ｃの機能は、基本的に実施の形態１，２で説明した検索制御部２と同じであるが、パイプライン処理を行なうことができるように検索結果およびキーを次段の検索制御部に通知する機能を有する。
【００８３】
図２１は、受信側パケット処理部における処理のタイミングの概要を示す図である。この図２１に示されるように、パケット１，２，３，４，・・・と順に受信側パケット処理部１３のパケット入力部２０に入力されるものとする。まず、第１の検索制御部２ａではパケット１の第１のテーブル１ａを用いた検索処理が行われる。つぎのタイミングで、第１の検索制御部２ａによる検索結果が検索制御部２に出力され、その検索結果と第２の分割検索キーの組合せによってパケット１の第２のテーブル１ｂを用いた検索処理が行われる。同時に、第１の検索制御部２ａではつぎのパケット２の第１のテーブル１ａを用いた検索処理が行われる。以後、同様にしてそれぞれの検索制御部２ａ〜２ｃでそれぞれ別々のパケットについての検索処理を同時に実行し、第３のテーブル１ｃで検索結果が得られると、パケット１から順にヘッダ挿入部２３に出力される。なお、ここでは、テーブル１ａ〜１ｃと検索制御部２ａ〜２ｃが３つの場合を示したが、これらを２つに構成しても、４つ以上に構成してもよい。
【００８４】
この実施の形態３によれば、複数の検索制御部２ａ〜２ｃを設け、パイプライン処理を実行可能なように構成したので、短い検索キーの検索の場合と同等のスループットを実現できるパケット転送装置を実現することが可能となる。
【００８５】
実施の形態４．
実施の形態１〜３では、検索キーを複数の分割検索キーに分割して、第１の分割検索キーを用いて第１のテーブルを検索し、その検索した結果と残りの第２の分割検索キーを合わせた新たな検索キーで、つぎの第２のテーブルの検索を行うというように順次処理を行なうことで、データ長の長い検索キーの検索を行なっていた。しかし、この実施の形態４では、分割した分割検索キーで並行して、それぞれのテーブルを検索し、検索したそれぞれの結果データ（タグ）を合わせたものをキーとしてテーブルを検索し、最終的な結果を求める場合を説明する。
【００８６】
図２２は、この発明の実施の形態４による検索方法の概略を模式的に示す図である。検索回路に入力された検索キーは複数の分割検索キーに分割され、それぞれ同時に対応するテーブルに入力される。ここでは、２つの分割検索キーに分割する場合を例に挙げて説明する。図２３は、図２２のそれぞれのテーブルに格納されるエントリの内容を示す図である。これらのテーブル１ａ，１ｂに格納される内容は、上述した図１３の例と同じものである。第１のテーブル１ａには検索キーの上位６４ビットのアドレスが格納されており、第２のテーブル１ｂには検索キーの下位６４ビットのアドレスが格納されている。検索キーが２つの分割検索キーに分割され、それぞれの分割検索キーが第１と第２のテーブル１ａ，１ｂによって同時に検索される。そして、それぞれ、検索結果としてタグを検索制御部２に出力する。
【００８７】
つぎに、検索制御部２は、それぞれのテーブル１ａ，１ｂから出力されたタグを組み合わせたものを最終検索キーとして、最終テーブル１ｄに出力し、最終テーブル１ｄから検索結果を得る。この最終テーブル１ｄは図２３に示されるように、エントリとしてタグの組合せと、タグの長さを指定するマスク長と、タグの組合せに対する結果データが格納される。なお、図２２と図２３における第１と第２のテーブル１ａ，１ｂは、特許請求の範囲の第１のテーブルに相当し、最終テーブル１ｄは、同じく第２のテーブルに相当する。
【００８８】
たとえば、図２３で上述したアドレス「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：０ｄ０ｅ」を有するパケット１が検索回路に入力した場合には、上位６４ビットの第１の分割検索キー「４０００：０１０２：０３０４：０５０６」と、下位６４ビットの第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：０ｄ０ｅ」に分割され、第１の分割検索キーは第１のテーブル１ａに、第２の分割検索キーは第２のテーブル１ｂにそれぞれ入力される。その結果、第１のテーブル１ａではエントリ１に該当するので「タグａ１」が出力され、第２のテーブル１ｂではエントリ２に該当するので「タグａ２」が出力される。そして、これらのタグを組み合わせた最終検索キー「タグａ１＋タグａ２」が最終テーブル１ｄに入力される。最終テーブル１ｄでは、エントリＡに該当するので「結果データ」としてアドレスＡが出力される。
【００８９】
また、上述したアドレス「４０００：０１０２：０３０４：００００：０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」を有するパケット２の場合は、第１の分割検索キー「４０００：０１０２：０３０４：００００」は第１のテーブル１ａのエントリＢに一致するので、タグｂ１を取得し、第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：０ｄ０４」は第２のテーブル１ｂのエントリＡに一致するので、タグａ２を取得する。これらのタグを合わせた「タグｂ１＋タグａ２」で最終テーブル１ｄを検索すると、その結果エントリＢに該当するので「結果データ」としてアドレスＢを取得する（エントリＢはマスク長が１つのタグ長となっているので、上位のタグがタグｂ１ならば、下位が何であってもエントリＢに該当する）。
【００９０】
さらに、上述したアドレス「４０００：０１０２：０３０４：０５０６：０７０８：０９０ａ：０ｂ０ｃ：００００」を有するパケット３の場合は、第１の分割検索キー「４０００：０１０２：０３０４：０５０６」は第１のテーブル１ａのエントリＡに一致するので、タグａ１を取得し、第２の分割検索キー「０７０８：０９０ａ：０ｂ０ｃ：００００」は第２のテーブル１ｂに該当するエントリがないので、ミスヒットになる。ミスヒットになった場合はエントリに使用しないタグ値（この例ではｘ）を割り当てる。最後に、これらのタグを合わせた「タグａ１＋タグｘ」で最終テーブル１ｄを検索し、その結果ダミーエントリに該当するので、「結果データ」としてアドレスＢを取得する。
【００９１】
ただし、この場合も単にエントリのアドレスを分割して登録した各テーブル１ａ，１ｂ，１ｄに、分割した検索キーで検索するだけでは、図２４の従来の問題点で示した場合と同様に正しく検索できない場合があるため、実施の形態１，２のようにエントリ同士の包含関係を調べ、包含関係が存在する場合には、必要なテーブルにダミーエントリを追加したりフラグを立てたりする必要がある。
【００９２】
なお、上述した説明では、検索キーを２分割した場合を例に挙げたが、検索キーを３分割以上する場合でも同様の処理手順でエントリの追加または削除処理を実現することができる。
【００９３】
この実施の形態４によれば、「検索対象情報」に対する「結果データ」としてタグを設定し、検索キーを複数に分割した分割検索キーを、それぞれのテーブルで同時に検索して得られたタグ値を組み合わせたものを検索キーとして、最終テーブルを用いて検索を行うように構成したので、複数に分割したＬＰＭ検索でも正しく検索し、検索時間を短くすることができるようになる。
【００９４】
なお、実施の形態１，２，４に示した検索回路を、図２０に示される受信側パケット処理部１３中の検索回路２２に設置して、パケット転送装置を構成することができる。特に、実施の形態４の場合には、検索キーを分割した分割検索キーを同時に検索するので、長い検索キーであっても短い検索キーの場合と同等のスループットを実現できる。
【００９５】
【発明の効果】
以上説明したように、この発明によれば、新たに追加・削除を行うエントリと、テーブルに格納されているエントリの包含関係を求め、その結果、両者の間に包含関係が存在する場合には、テーブルにダミーエントリの追加、削除、変更を行うように構成したので、複数に検索キーを分割したＬＰＭ検索でも、検索キーの分割によって分割検索キーに対する結果情報が得られなくなることを回避して、正しく検索を行うことができるという効果を有する。
【図面の簡単な説明】
【図１】この発明による検索回路の構成を模式的に示すブロック図である。
【図２】テーブルの構成の一例を示す図である。
【図３】エントリ追加時の全体の処理手順を示すフローチャートである。
【図４】包含関係を判定する条件を示す図である。
【図５】図４の包含関係１におけるダミーエントリの必要の有無を判定する条件を示す図である。
【図６】図４の包含関係２におけるダミーエントリの必要の有無を判定する条件を示す図である。
【図７】図４の包含関係３におけるダミーエントリの必要の有無を判定する条件を示す図である。
【図８】ダミーエントリの追加判定の結果とその処理内容を規定する図である。
【図９】エントリ追加の処理手順を示すフローチャートである。
【図１０】エントリ削除時の全体の処理手順を示すフローチャートである。
【図１１】エントリ削除処理の手順を示すフローチャートである。
【図１２】ダミーエントリの削除内容を示す図である。
【図１３】テーブルが２つの場合のエントリ追加の様子を示す図である。
【図１４】テーブルが２つの場合のエントリを削除する様子を示す図である。
【図１５】この発明によるテーブルの構成を示す図である。
【図１６】この発明による検索回路のテーブルの実施の形態２の構成を示す図である。
【図１７】この発明による検索回路の実施の形態２による検索の処理手順を示すフローチャートである。
【図１８】テーブルが２つの場合のエントリの追加の様子を示す図である。
【図１９】この発明によるパケット転送装置の全体の構成を示すブロック図である。
【図２０】受信パケット処理部の構成を示すブロック図である。
【図２１】受信側パケット処理部における処理のタイミングの概要を示す図である。
【図２２】この発明の実施の形態４による検索方法の概略を模式的に示す図である。
【図２３】この発明の実施の形態４のテーブルの一例を示す図である。
【図２４】従来のＬＰＭ検索の問題点を説明するための図である。
【符号の説明】
１  テーブル（検索エンジン）、２  検索制御部、３  検索キー分割・タグ管理部、４  包含関係検出・ダミーエントリ管理部、１０  インタフェース、１１スイッチ、１２  物理レイヤ処理部、１３  受信側パケット処理部、１４  送信側パケット処理部、２０  パケット入力部、２１  ヘッダ抽出部、２２  検索回路、２３  ヘッダ挿入部、２４  パケット出力部。
【図１】
2004336427.tif 000003
【図２】
2004336427.tif 000004
【図３】
2004336427.tif 000005
【図４】
2004336427.tif 000006
【図５】
2004336427.tif 000007
【図６】
2004336427.tif 000008
【図７】
2004336427.tif 000009
【図８】
2004336427.tif 000010
【図９】
2004336427.tif 000011
【図１０】
2004336427.tif 000012
【図１１】
2004336427.tif 000013
【図１２】
2004336427.tif 000014
【図１３】
2004336427.tif 000015
【図１４】
2004336427.tif 000016
【図１５】
2004336427.tif 000017
【図１６】
2004336427.tif 000018
【図１７】
2004336427.tif 000019
【図１８】
2004336427.tif 000020
【図１９】
2004336427.tif 000021
【図２０】
2004336427.tif 000022
【図２１】
2004336427.tif 000023
【図２２】
2004336427.tif 000024
【図２３】
2004336427.tif 000025
【図２４】
2004336427.tif 000026