(57)【要約】      （修正有）【課題】検索条件にＰｒｅｆｉｘの値やＤｏｎ’ｔ  Ｃａｒｅシンボルがある場合でも、高いスループットで受信したパケットのフィルタリングやルーティング処理を行う。【解決手段】予め登録した複数の条件の中から入力されたデータと合致する条件を検索する検索装置は、この複数の条件を１つまたは複数のグループに分けておき、入力されたデータが各条件と不一致であることをグループ毎に検出する不一致検出手段と、入力されたデータと条件とを照合して合致する条件を検索する一致検索手段を備えている。不一致検出手段は、入力されたデータの数値をメモリの読み出しアドレスとして、メモリに記憶されているグループ毎のシンボルを読み出すことにより各グループに対する入力データの不一致を検出して一致検索手段に通知し、一致検索手段では入力されたデータと不一致が検出されたグループの条件との照合は行わないようにして検索回数を削減する。【選択図】図５
2015046711.tif 000002
【特許請求の範囲】
【請求項１】
予め登録した複数の条件の中から入力されたデータと合致する条件を検索する検索装置であって、
前記条件のそれぞれは、１つまたは複数のグループに属し、
前記条件を記憶するメモリを備え、
前記入力されたデータが前記条件と不一致であることを前記グループ毎に検出する不一致検出手段と、
前記入力されたデータと前記条件とを照合して前記入力されたデータと合致する条件を検索する一致検索手段とを備え、
前記条件は、前記条件に含まれるＤｏｎ’ｔＣａｒｅシンボルが０の場合と１の場合に展開され、前記メモリの各アドレスには、前記条件の一部または全てが前記各アドレスの数値と等しいか否かを表すシンボルが前記グループ毎に記憶されており、
前記不一致検出手段は、前記入力された数値の一部または全てを前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を検出する手段と、前記検出の結果を前記一致検索手段に通知する手段とを備え、
前記一致検索手段は入力されたデータと前記不一致が検出されたグループの条件との照合は行わないこと
を特徴とする検索装置。
【請求項２】
前記不一致検出手段は、
前記入力された数値を、当該桁数またはビット数より小さい複数のブロックからなる部分入力数値に分割する分割手段と、
前記部分入力数値を前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を前記ブロック毎に検出する手段を備え、
前記ブロック毎の各グループに対する不一致の検出結果を集計する集計手段とを備えること
を特徴とする請求項１記載の検索装置。
【請求項３】
前記条件は、Ｐｒｅｆｉｘ値とＤｏｎ’ｔＣａｒｅシンボルの数とＤｏｎ’ｔＣａｒｅシンボルの位置の少なくとも一つに基づいてグループ分けされること
を特徴とする請求項１または２記載の検索装置。
【請求項４】
前記条件の少なくとも一つがただ一つのグループにのみ属すること
を特徴とする請求項１乃至３のいずれか一つに記載の検索装置。
【請求項５】
予め登録した複数の条件の中から入力されたデータと合致する条件を検索する検索方法であって、
前記条件のそれぞれは、１つまたは複数のグループに属し、
前記入力されたデータがメモリに記憶された前記条件と不一致であることを前記グループ毎に検出する不一致検出ステップと、
前記入力されたデータと前記条件とを照合して前記入力されたデータと合致する条件を検索する一致検索ステップとを備え、
前記条件は、前記条件に含まれるＤｏｎ’ｔＣａｒｅシンボルが０の場合と１の場合に展開され、前記メモリの各アドレスには、前記条件の一部または全てが前記各アドレスの数値と等しいか否かを表すシンボルが前記グループ毎に記憶されており、
前記不一致検出ステップは、前記入力された数値の一部または全てを前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を検出するステップと、前記検出の結果を前記一致検索ステップに通知するステップとを備え、
前記一致検索ステップは入力されたデータと前記不一致が検出されたグループの条件との照合は行わないこと
を特徴とする検索方法。
【請求項６】
前記不一致検出ステップは、
前記入力された数値を、当該桁数またはビット数より小さい複数のブロックからなる部分入力数値に分割するステップと、
前記部分入力数値を前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を前記ブロック毎に検出するステップと、
前記ブロック毎の各グループに対する不一致の検出結果を集計するステップとを備えること
を特徴とする請求項５記載の検索方法。
【請求項７】
前記条件は、Ｐｒｅｆｉｘ値とＤｏｎ’ｔＣａｒｅシンボルの数とＤｏｎ’ｔＣａｒｅシンボルの位置の少なくとも一つに基づいてグループ分けされること
を特徴とする請求項５または６記載の検索方法。
【請求項８】
前記条件の少なくとも一つがただ一つのグループにのみ属すること
を特徴とする請求項５乃至７のいずれか一つに記載の検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力したデータと合致する条件を検索する検索装置および方法に関する。
【背景技術】
【０００２】
通信端末の多くは、受信したパケットにフィルタリングやルーティングなどの処理を行うため、検索装置を搭載している。この検索装置は、受信したパケットの一部または全てを入力とし（入力データ）、事前に登録した条件テーブルから入力データと合致する条件を検索する装置である。この検索装置は、合致した条件を発見した場合にはその条件番号を出力し、合致する条件がなかった場合には一致する条件なし（不一致）の検索結果を出力する。そして、通信端末は、検索装置の出力する検索結果に従い、受信したパケットを廃棄したり、出力ポートを決定したりする。
【０００３】
ブロードバンドの普及に伴い、通信端末には高スループット化が求められている。そのため、検索装置にも高スループット化、つまり、単位時間当たりに検索可能な入力データの数を増やすことが求められている。さらに、省エネの観点からは低消費エネルギー化も必要である。
【０００４】
検索装置が入力データと合致する条件を検索する方式として、線形探索方式がある。本方式は、入力データと条件１つ１つを比較して、入力データと合致する条件を探しだす方式である（一致検索）。本方式を実装した検索装置の構成例を図１４に示す。検索装置１０は、条件テーブルを記憶する条件メモリ４０と、入力データと条件を比較する比較器５０から構成されている。本構成において、入力データがスタートとともに入力されると、比較器は条件メモリに読出しアドレスを送信し、条件メモリに記憶された条件を１つずつ読み出して入力データと比較する。そして、全条件と入力データを比較し終えると、その結果を検索結果として外部に出力する構成となっている。
【０００５】
上記方式では、入力データと全条件とを比較した後でなければ検索結果を出力できないため、１つの入力データを処理するのに時間がかかっていた。さらに、条件数と同じ回数だけメモリにアクセスする必要があるため、電力を多く消費するという問題があった。
【０００６】
この問題を解決するため特許文献１では不一致検出手段を用いた検索装置が提案されている。特許文献１の検索装置では、入力データと不一致の条件を短時間で検出可能な不一致検出手段を検索装置に具備することにより、入力データと不一致の条件を条件メモリから読み出して比較する処理数を削減し、検索装置の平均検索時間を短くすることができる。
【０００７】
図１５は、特許文献１の検索装置のブロック図である。検索装置１０は、図１４の線形探索方式と同様の方法で入力データと一致する条件を検索する一致検索手段３０と、入力データと合致しない条件を短時間で検出可能な不一致検出手段２０とで構成される。この検索装置１０においては、登録される条件は複数のグループに分けられる。例えば、４種の条件（条件＃０：００００、条件＃１：０１００、条件＃２：１０００、条件＃３：１０１１）が条件テーブルに登録されている場合、条件＃０と条件＃１をグループ＃０とし、条件＃２と条件＃３をグループ＃１とする。
【０００８】
検索装置１０に入力される入力データは、まず不一致検出手段２０に入力される。この不一致検索手段２０は、入力データと合致する条件が存在していない（不一致）グループを短時間で検出する。そして、不一致検出手段２０は、不一致を検出したグループを不一致検出結果として一致検索手段３０に出力する。不一致検出手段２０で不一致が検出されたグループは一致検索手段３０で検索する必要がなくなるため、一致検索手段３０において条件をメモリから読み出して入力データと比較する処理数が削減でき、検索装置１０の平均検索時間を短くすることができる。
【０００９】
特許文献１の不一致検出手段は、条件メモリを用いてグループ毎の不一致を検出する。この条件メモリには、グループ毎に条件が登録される。条件をメモリに登録する方法を図１６を用いて説明する。条件メモリの各ｂｉｔは、それぞれのグループに対応する。たとえば、条件メモリのｂｉｔ［０］はグループ＃０に対応し、ｂｉｔ［１］はグループ＃１に対応する。そして、各アドレスにはグループ毎の条件テーブルの値の有無が記憶されており、条件テーブルの値と等しいアドレスには、その条件が属するグループに「有」が記憶され、それ以外の領域には、「無」が記憶されている。
【００１０】
例えば、条件＃０（値が００００でグループ＃０に属する）により、条件メモリのアドレス００００のｂｉｔ［０］には「有」のシンボルが記憶され、同様に、条件＃１（値が０１００でグループ＃０に属する）により、条件メモリのアドレス０１００のｂｉｔ［０］、条件＃２（値が１０００でグループ＃１に属する）により条件メモリのアドレス１０００のｂｉｔ［１］、条件＃３（値が１０１１でグループ＃１に属する）により条件メモリのアドレス１０１１のｂｉｔ［１］には「有」のシンボルが記憶される。そして、それ以外の領域には、「無」のシンボルが記憶される。
【００１１】
本メモリを用いてグループ毎の不一致を検出する場合には、図１７のように、入力データと等しいアドレスを読み出せばよい。例えば、入力データが０１００の場合には、条件メモリのアドレス０１００を読み出す。アドレス０１００のｂｉｔ［０］には「有」の条件が記憶され、ｂｉｔ［１］には「無」の条件が記憶されているため、グループ＃１に不一致の検出結果が出力される。グループ＃１に不一致が検出されるとその後の一致検索手段において、入力データとグループ１の条件との比較が不要となる。
【００１２】
このように、入力データと等しいアドレスを読み出すだけで、各グループ毎にデータの不一致が検出できるので、一致検索処理において不一致が検出されたグループの一致検索が不要となり、入力データと比較する処理数を削減することができる。
【００１３】
上記構成は１回のメモリアクセスでグループ毎の不一致を検出することが可能であるが、入力データと一致条件の数値範囲が大きくなった場合には必要なメモリ容量が大きくなる。たとえば、入力データと一致条件がｍ ｂｉｔの数値範囲の場合、必要なメモリ容量は２mｂｉｔとなる。そのため、特許文献１では、ｍ ｂｉｔをｎ ｂｉｔずつのブロックに分割し、並列して不一致を検出する手段をとり、メモリ容量の削減を図っている。
【００１４】
図１８は、従来の検索装置における検索条件テーブルを２つのブロックに分割した場合の条件テーブルおよび条件メモリを説明する図である。図１８では、図１６で例示した条件テーブルをブロック＃０とブロック＃１の２つのブロックに分割し、各ブロック毎に条件メモリを用意する。分割した各ブロックにおいても条件テーブルを２つのグループに分けて、それぞれの条件の値と等しい条件メモリのアドレスには、その条件が属するグループに「有」が記憶され、それ以外の領域には、「無」が記憶されている。
【００１５】
例えば、上位２ｂｉｔのブロック＃１の場合には、条件＃０（値が００でグループ＃０に属する）により、条件メモリ＃２のアドレス００のｂｉｔ［０］には「有」のシンボルが記憶され、同様に、条件＃１（値が０１でグループ＃０に属する）により、条件メモリ＃２のアドレス０１のｂｉｔ［０］、条件＃２（値が１０でグループ＃１に属する）により条件メモリ＃２のアドレス１０のｂｉｔ［１］、条件＃３（値が１０でグループ＃１に属する）により条件メモリ＃２のアドレス１０のｂｉｔ［１］には「有」のシンボルが記憶される。そして、それ以外の領域には、「無」のシンボルが記憶される。下位２ｂｉｔのブロック＃０についても同等に、条件テーブルにおける値の有無が条件メモリ＃１に記憶されている。
【００１６】
図１９は、図１６の条件メモリにおける不一致判定処理の一例を示す図である。条件メモリが２つのブロックに分割されているので、入力データ０１００も２つのブロックに分割して、不一致検出を行う。例えば、上記２ビット０１と同じ値のアドレス０１の値を読み出すことにより、グループ＃１の不一致を検出することができる。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開２０１３−３６４４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上述したように、特許文献１の不一致検出手段を用いた検索装置では、入力データと条件が完全に一致する「完全一致検索」において、高スループット化と低消費電力化を達成することができた。しかしながら、特許文献１の不一致演出手段は、値が０でも１でもよいＤｏｎ’ｔ  Ｃａｒｅシンボルに対応することができないため、ルータなどで用いられているＰｒｅｆｉｘ検索に適用することができないという問題がある。
【００１９】
本発明が解決しようとする課題は、Ｄｏｎ’ｔ  Ｃａｒｅに対応できる不一致検出手段を備え、Ｐｒｅｆｉｘ検索に適用可能な検索装置を提供することにある。
【課題を解決するための手段】
【００２０】
上述したような課題を解決するために、本発明に係る検索装置は、予め登録した複数の条件の中から入力されたデータと合致する条件を検索する検索装置であって、前記条件のそれぞれは、１つまたは複数のグループに属し、前記条件を記憶するメモリを備え、前記入力されたデータが前記条件と不一致であることを前記グループ毎に検出する不一致検出手段と、前記入力されたデータと前記条件とを照合して前記入力されたデータと合致する条件を検索する一致検索手段とを備え、前記条件は、前記条件に含まれるＤｏｎ’ｔＣａｒｅシンボルが０の場合と１の場合に展開され、前記メモリの各アドレスには、前記条件の一部または全てが前記各アドレスの数値と等しいか否かを表すシンボルが前記グループ毎に記憶されており、前記不一致検出手段は、前記入力された数値の一部または全てを前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を検出する手段と、前記検出の結果を前記一致検索手段に通知する手段とを備え、前記一致検索手段は入力されたデータと前記不一致が検出されたグループの条件との照合は行わないことを特徴とする。
【００２１】
また、前記不一致検出手段は、前記入力された数値を、当該桁数またはビット数より小さい複数のブロックからなる部分入力数値に分割する分割手段と、前記部分入力数値を前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を前記ブロック毎に検出する手段を備え、前記ブロック毎の各グループに対する不一致の検出結果を集計する集計手段とを備えるようにしてもよい。
【００２２】
また、前記条件は、Ｐｒｅｆｉｘ値とＤｏｎ’ｔＣａｒｅシンボルの数とＤｏｎ’ｔＣａｒｅシンボルの位置の少なくとも一つに基づいてグループ分けされるようにしてもよい。
【００２３】
また、前記条件の少なくとも一つがただ一つのグループにのみ属するようにしてもよい。
【００２４】
上述したような課題を解決するために、本発明に係る検索方法は、予め登録した複数の条件の中から入力されたデータと合致する条件を検索する検索方法であって、前記条件のそれぞれは、１つまたは複数のグループに属し、前記入力されたデータがメモリに記憶された前記条件と不一致であることを前記グループ毎に検出する不一致検出ステップと、前記入力されたデータと前記条件とを照合して前記入力されたデータと合致する条件を検索する一致検索ステップとを備え、前記条件は、前記条件に含まれるＤｏｎ’ｔＣａｒｅシンボルが０の場合と１の場合に展開され、前記メモリの各アドレスには、前記条件の一部または全てが前記各アドレスの数値と等しいか否かを表すシンボルが前記グループ毎に記憶されており、前記不一致検出ステップは、前記入力された数値の一部または全てを前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を検出するステップと、前記検出の結果を前記一致検索ステップに通知するステップとを備え、前記一致検索ステップは入力されたデータと前記不一致が検出されたグループの条件との照合は行わないことを特徴とする。
【００２５】
また、前記不一致検出ステップは、前記入力された数値を、当該桁数またはビット数より小さい複数のブロックからなる部分入力数値に分割するステップと、前記部分入力数値を前記メモリの読み出しアドレスとして、前記メモリから前記グループ毎のシンボルを読み出すことにより前記各グループに対する不一致を前記ブロック毎に検出するステップと、前記ブロック毎の各グループに対する不一致の検出結果を集計するステップとを備えるようにしてもよい。
【００２６】
前記条件は、Ｐｒｅｆｉｘ値とＤｏｎ’ｔＣａｒｅシンボルの数とＤｏｎ’ｔＣａｒｅシンボルの位置の少なくとも一つに基づいてグループ分けされるようにしてもよい。
【００２７】
前記条件の少なくとも一つがただ一つのグループにのみ属するようにしてもよい。
【発明の効果】
【００２８】
本発明によれば、不一致検出手段を備えた検出装置において、検索条件にＰｒｅｆｉｘの値やＤｏｎ’ｔ  Ｃａｒｅシンボルがある場合でも、不一致検出結果を高くすることが可能となり、一致検索手段における入力データと条件の比較数を削減し、検索装置におけるスループットを向上させ、さらには低消費電力化を図ることができる。
【図面の簡単な説明】
【００２９】
【図１】図１は、本発明の実施の形態に係る条件メモリ内の条件テーブルの一例を表す図である。
【図２】図２は、本発明の実施の形態に係るＰｒｅｆｉｘ値が設定されている場合のマスク処理を説明する図である。
【図３】図３は、本発明の実施の形態に係る条件テーブルのＤｏｎ’ｔＣａｒｅシンボルを展開した場合の条件テーブルを説明する図である。
【図４】図４は、本発明の実施の形態に係るＤｏｎ’ｔＣａｒｅシンボルを展開した条件テーブルを登録した条件メモリを説明する図である。
【図５】図５は、本発明の実施の形態に係る不一致検出手段のブロック図である。
【図６】図６は、本発明の実施の形態に係る条件テーブルを２つのブロックに分割した場合の条件テーブルおよび条件メモリを説明する図である。
【図７】図７は、本発明の実施の形態に係る条件テーブルを２つのブロックに分割した場合の不一致検出手段のブロック図である。
【図８】図８は、Ｐｒｅｆｉｘ値によるグループ分けを行わなかった場合の条件テーブルおよび条件メモリを説明する図である。
【図９】図９は、本発明の実施の形態に係るＰｒｅｆｉｘ値によるグループ分けを行った場合の条件テーブルおよび条件メモリを説明する図である。
【図１０】図１０は、Ｄｏｎ’ｔＣａｒｅシンボルの位置によるグループ分けを行わなかった場合の条件テーブルを説明する図である。
【図１１】図１１は、本発明の実施の形態に係るＤｏｎ’ｔ  Ｃａｒｅシンボルの位置によるグループ分けを行わず、かつ条件テーブルを２つのブロックに分割した場合の条件テーブルおよび条件メモリを説明する図である。
【図１２】図１２は、Ｄｏｎ’ｔＣａｒｅシンボルの位置によるグループ分けを行った場合の条件テーブルを説明する図である。
【図１３】図１３は、本発明の実施の形態に係るＤｏｎ’ｔ  Ｃａｒｅシンボルの位置によるグループ分けを行い、かつ条件テーブルを２つのブロックに分割した場合の条件テーブルおよび条件メモリを説明する図である。
【図１４】図１４は、従来の検索装置のブロック図である。
【図１５】図１５は、従来の不一致検出手段を備えた検索装置のブロック図である。
【図１６】図１６は、従来の検索装置における条件テーブル及び条件メモリを一例を示す図である。
【図１７】図１７は、従来の検索装置における不一致検索手段における不一致判定処理の一例を示す図である。
【図１８】図１８は、従来の検索装置における条件テーブルをを２つのブロックに分割した場合の条件テーブルおよび条件メモリを説明する図である。
【図１９】図１９は、従来の検索装置における条件テーブルをを２つのブロックに分割した場合の条件メモリにおける不一致判定処理の一例を示す図である。
【発明を実施するための形態】
【００３０】
（第１の実施の形態）
本発明の第１の実施の形態を説明する。本実施の形態は、不一致検出手段のメモリに条件を登録する際、Ｄｏｎ’ｔ  Ｃａｒｅを含む１つの条件を、Ｄｏｎ’ｔ  Ｃａｒｅのシンボルが１の場合と０の場合というように条件を複数個に展開し、展開したＤｏｎ’ｔ  Ｃａｒｅシンボルを含まない全条件をメモリに登録する。
【００３１】
まず、ルータ等で用いられるＰｒｅｆｉｘ検索を、図１を参照して説明する。Ｐｒｅｆｉｘ検索において、条件テーブルの列は、条件と、Ｐｒｅｆｉｘと、優先度から構成される。Ｐｒｅｆｉｘは、入力データと条件の照合において、Ｄｏｎ’ｔ  Ｃａｒｅ設定しない（照合対象になる）ｂｉｔ数が最上位ｂｉｔから何ｂｉｔかを示している。
【００３２】
例えば、図２のように、条件が００００でＰｒｅｆｉｘが１の場合、００１０という値を持つ入力データが入力されると、入力データと条件の下位３ｂｉｔはＤｏｎ’ｔ  Ｃａｒｅ扱いとなり、照合の対象にはならない。この場合、入力データである００１０と条件００００の最上位ｂｉｔのみが照合対象となり、最上位ｂｉｔは両方とも０であるため、一致することになる。また、複数の条件が入力データと一致した場合には優先度が参照され、優先度が高い条件に一致したと判定される。
【００３３】
不一致検出手段にＰｒｅｆｉｘ検索用の条件を登録する例を、図３を用いて説明する。本図では、条件＃０は条件値が００００でＰｒｅｆｉｘが３、条件＃１は条件値が０１００でＰｒｅｆｉｘが４、条件＃２は条件値が１０００でＰｒｅｆｉｘが４、条件＃３は条件値が１０１１でＰｒｅｆｉｘが４とする。さらに、条件＃０と＃１がグループ＃０に属し、条件＃２と＃３がグループ＃１に属するとする。
【００３４】
まず初めに、各条件のＰｒｅｆｉｘの値に応じてＤｏｎ’ｔ  Ｃａｒｅを設定する（Ｐｒｅｆｉｘの展開）。本図では、条件＃０のＰｒｅｆｉｘが３であるため、条件＃０は０００＊になる。次に、各条件のＤｏｎ’ｔ  Ｃａｒｅ（＊）が１の場合と０の場合に条件を展開する（Ｄｏｎ’ｔ  Ｃａｒｅの展開）。
【００３５】
本図の例では、条件＃０のみがＤｏｎ’ｔ  Ｃａｒｅを含んでいるので、条件＃０のみを展開する。条件＃０は、０００＊であるため、この条件＃０は、００００と０００１という２つの条件に展開される。つまり、条件テーブルの条件が５種あることと同じになる。
【００３６】
最後に、図４に示すように、Ｐｒｅｆｉｘ検索用に５種に展開された条件を従来と同様に不一致検出手段のメモリに登録すればよい。ここで、Ｄｏｎ’ｔ  Ｃａｒｅを展開した２つの条件、００００と０００１は、条件＃０が属していたグループ＃０に属する。このように、条件テーブルがＤｏｎ’ｔ  Ｃａｒｅを含んでいる場合には、Ｄｏｎ’ｔ  Ｃａｒｅの展開を行って、メモリに登録することにより、Ｐｒｅｆｉｘ値およびＤｏｎ’ｔ  Ｃａｒｅを考慮する必要がなくなるので、入力データが入力された時の動作は、従来の完全一致検索での不一致検出手段の動作と同様に不一致検出が可能となる。
【００３７】
以上のような処理を行う不一致検出手段の構成例を図５に示す、不一致検出手段２０は入力データを遅延させて一致検索手段に入力するための遅延手段２１と、条件テーブルが記憶されている条件メモリ２２から構成されており、条件メモリ２２に入力データを読み出しアドレスとして入力すると各グループ毎の不一致検出結果が出力される。尚、検出装置全体の構成は図１５と同様である。
【００３８】
尚、図６に示すように、Ｄｏｎ’ｔ  Ｃａｒｅの展開を行った場合にも、条件テーブルをｎｂｉｔずつの複数のブロックに分割し、各ブロック毎に並列に不一致を検出することも可能である。この場合の不一致検出手段の構成を図７に示す。不一致検出手段２０は、入力データを複数のブロックに分割するデータ分割手段２４と各ブロック毎に不一致検出結果を出力する条件メモリ２２および２３、ブロック毎に不一致検出結果を集計する集計手段２５を備える。不一致検出手段２０は各グループ毎に不一致検出結果を集計して一致検索手段に出力する。
【００３９】
本実施の形態において、検索する条件テーブルの条件値は４種類としたが、入力データおよび各条件の数値範囲や、条件の登録数によらず他の条件値の場合でも本発明が適用可能であることはいうまでもない。条件のグループ分けについても２つのグループに限らず、各条件の数値範囲や、条件の登録数に応じて適宜選択すればよい。例えば、グループ数を１つにした場合でも、本発明の適用は可能である。また、各グループの条件数を等しくする必要はない。
【００４０】
本実施の形態では、Ｐｒｅｆｉｘ値に応じて上位ｂｉｔからＤｏｎ’ｔ  Ｃａｒｅ設定をしないｂｉｔ数を設定するＰｒｅｆｉｘ検索方式に適用した例を示したが、Ｄｏｎ’ｔ  Ｃａｒｅがランダムに設定されているような場合にも適用可能である。
【００４１】
また、本実施の形態において、一致判定手段は線形検索方式を実装した構成となっているが、構成はこれのみに限られず、たとえば２分探索木方式やＢ木探索、さらには、ＣＡＭ（Content addressing memory）を用いてもよい。
【００４２】
本実施の形態においては、検索装置が検索結果を出力する例を示したが、それぞれの条件が入力データと合致した場合に出力すべきデータ（関連データ）を一致検索手段のメモリに格納し、判定結果の代わりに上記関連データを出力する構成でもよい。例えば、関連データを出力ポートや出力キューとすることもできる。
【００４３】
本実施の形態では、本発明をハードウェアに実装した例を示したが、本発明をプログラム言語で記述したソフトウェアに実装してもよいことはいうまでもない。
【００４４】
（第２の実施の形態）
図８、９を用いて、本発明の第２の実施の形態を説明する。本実施の形態も第１の実施の形態と同様に、Ｄｏｎ’ｔ  Ｃａｒｅシンボルを展開するが、条件をＰｒｅｆｉｘに基づいてグループ分けしている点が、第１の実施の形態と異なる。
【００４５】
第１の実施の形態では、Ｐｒｅｆｉｘや条件に含まれるＤｏｎ’ｔ  Ｃａｒｅシンボルを考慮することなく、各条件が属するグループが決めていた。しかし、このやり方では、各グループに属する条件のＰｒｅｆｉｘ値によっては不一致検出手段が不一致を検出できる確率が低下し、一致判定手段で検索する条件数を削減できない場合がある。
【００４６】
例えば、図８に示すように、条件＃０は条件値が００００でＰｒｅｆｉｘが０、条件＃１は条件値が０１００でＰｒｅｆｉｘが４、条件＃２は条件値が１０００でＰｒｅｆｉｘが０、条件＃３は条件値が１０１１でＰｒｅｆｉｘが４とする。この場合、Ｐｒｅｆｉｘを展開すると、条件＃０と＃２は、＊＊＊＊となる。
【００４７】
＊＊＊＊のＤｏｎ’ｔ  Ｃａｒｅを展開すると、００００〜１１１１のすべての数値範囲を取りうるため、図８に示すように不一致を検出するメモリには全て「有」のシンボルが書き込まれてしまい、入力データが不一致検出手段に入力されても全グループに対して不一致を検出することができず、後段の一致検出手段で入力データと全条件の比較が必要になってしまう。
【００４８】
この問題を解決するため本実施の形態では、図９に示すように、Ｐｒｅｆｉｘの値に応じてグループ分けを行う。例えば、図８の４種の条件の場合には、Ｐｒｅｆｉｘ値が０である条件＃０と＃２をグループ＃０とし、Ｐｒｅｆｉｘ値が４である条件＃１と＃３をグループ＃１とする。このようにグループ分けを行うことにより、図９に示すように、＊＊＊＊という条件はグループ＃０のみに存在することになり、不一致を検出するメモリのｂｉｔ［１］には「無」のシンボルが存在できるようになる。
【００４９】
このように、Ｐｒｅｆｉｘの値に応じてグループ分けを行うことにより、グループ＃１に関しては不一致を検出できるようになり、一致検索手段における入力データと条件の比較数を削減することができるようになる。グループ分けの方法としては、各条件の値ができるだけ同じグループにのみ存在するようにグループ分けを行えば、上述したように特定のグループに対する不一致の検出確率を高くすることができる。さらに、各条件の値が一つのグループのみ存在するようにグループ分けを行えば、より不一致の検出確率を高くすることができる。
【００５０】
（第３の実施の形態）
第２の実施の形態では、Ｐｒｅｆｉｘの値に応じて条件のグループ分けを実施する例を示したが、Ｄｏｎ’ｔ  Ｃａｒｅの数や位置に応じて条件のグループ分けを行ってもよい。
【００５１】
すなわち、不一致検出手段において、不一致となるグループが検出できる確率が高くなるように条件テーブルのグループ分けを行うことにより、一致検索手段における入力データと条件との比較する稼働を削減することが可能である。Ｄｏｎ’ｔ  Ｃａｒｅの数に応じてグループ分けを行う場合は、例えば、同じ数のＤｏｎ’ｔ  Ｃａｒｅシンボルを有する条件を同じグループにすることにより不一致となるグループが検出できる確率を高くすることができる。
【００５２】
図１０〜図１３を用いて、Ｄｏｎ’ｔ  Ｃａｒｅの位置に応じて条件のグループ分けを行う場合を説明する。
【００５３】
図１０は、Ｄｏｎ’ｔ  Ｃａｒｅがランダムに設定されている場合の条件テーブルの構成例である。図１０に示すように、条件＃０は条件値が０００＊であり、最下位ｂｉｔがＤｏｎ’ｔ  Ｃａｒｅ設定されている。同様に、条件＃１は最上位ｂｉｔがＤｏｎ’ｔ  Ｃａｒｅ設定され、条件＃２は最下位ｂｉｔがＤｏｎ’ｔ  Ｃａｒｅ設定され、条件＃３は最上位ｂｉｔがＤｏｎ’ｔ  Ｃａｒｅ設定されている。
【００５４】
この条件テーブルにおいて、各条件のＤｏｎ’ｔ  Ｃａｒｅシンボルを展開すると図１０に示すように８つの条件に展開される。
【００５５】
本実施の形態では、この条件テーブルを２つのブロックに分割して各ブロック毎に並列に不一致を検出する場合を説明する。図１１は、図１０の条件テーブルを２つのブロックに分けて不一致検出をする場合のメモリの構成例である。
【００５６】
この例では、上位２ｂｉｔのブロック＃１と下位２ｂｉｔのブロック＃０のそれぞれのアドレス領域には、グループ＃１、グループ＃０の両方に「有」が記憶されているアドレスがそれぞれ２アドレスずつ存在するため、不一致検出ができる確率が低くなってしまう。
【００５７】
これに対して、図１２に示すように、Ｄｏｎ’ｔ  Ｃａｒｅの位置が同じ条件＃０と条件＃２、条件＃１と条件＃３がそれぞれ同じグループになるようにグループ分けを行った場合を説明する。図１３は、図１２の条件テーブルを２つのブロックに分けて不一致検出をする場合のメモリの構成例である。
【００５８】
図１３のメモリを用いた場合には、上位２ｂｉｔのブロック＃１と下位２ｂｉｔのブロック＃０のそれぞれのアドレス領域において、グループ＃１、グループ＃０の両方に「有」が記憶されているアドレスがそれぞれ１アドレスずつとなり、図１１の場合と比較して、不一致となるグループの検出確率を高くすることができる。
【００５９】
このように、Ｄｏｎ’ｔ  Ｃａｒｅシンボルの位置に応じてグループ分けを行うことにより、不一致となるグループの検出確率を高くすることができ、一致検索手段における入力データと条件の比較数を削減することができるようになる。グループ分けの方法としては、各条件の値ができるだけ同じグループにのみ存在するようにグループ分けを行えば、上述したように特定のグループに対する不一致の検出確率を高くすることができる。さらに、各条件の値が一つのグループのみ存在するようにグループ分けを行えば、より不一致の検出確率を高くすることができる。
【００６０】
尚、第３の実施の形態では、Ｄｏｎ’ｔ  Ｃａｒｅの数が１つの場合の例を説明したが、これに限られず、Ｐｒｅｆｉｘの値、Ｄｏｎ’ｔ  Ｃａｒｅの数や位置に応じて適宜条件テーブルのグループ分けや複数ブロックへの分割を行うことにより、不一致となるグループの検出確率を高くすることができ、一致検索手段における入力データと条件の比較数を削減することができるようになる。
【００６１】
以上のように、本発明の実施の形態によれば、不一致検出手段を備えた検出装置において、検索条件にＰｒｅｆｉｘの値やＤｏｎ’ｔ  Ｃａｒｅシンボルがある場合でも、不一致検出結果を高くすることが可能となり、一致検索手段における入力データと条件の比較数を削減し、検索装置におけるスループットを向上させ、さらには低消費電力化を図ることができる。
【産業上の利用可能性】
【００６２】
本発明は、検索条件にＰｒｅｆｉｘの値やＤｏｎ’ｔ  Ｃａｒｅシンボルがある場合でも、高いスループットで受信したパケットのフィルタリングやルーティング処理を行うことができる通信装置に適用できる。
【符号の説明】
【００６３】
１０…検索装置、２０…不一致検出手段、２１…遅延手段、２２、２３…条件メモリ、２４…データ分割手段、２５…集計手段、３０…一致検索手段、４０…条件メモリ、５０…比較部。
【図１】
2015046711.tif 000003
【図２】
2015046711.tif 000004
【図３】
2015046711.tif 000005
【図４】
2015046711.tif 000006
【図５】
2015046711.tif 000007
【図６】
2015046711.tif 000008
【図７】
2015046711.tif 000009
【図８】
2015046711.tif 000010
【図９】
2015046711.tif 000011
【図１０】
2015046711.tif 000012
【図１１】
2015046711.tif 000013
【図１２】
2015046711.tif 000014
【図１３】
2015046711.tif 000015
【図１４】
2015046711.tif 000016
【図１５】
2015046711.tif 000017
【図１６】
2015046711.tif 000018
【図１７】
2015046711.tif 000019
【図１８】
2015046711.tif 000020
【図１９】
2015046711.tif 000021