(57)【要約】【課題】連想メモリのエントリを節約することができるようにする。【解決手段】分離部１１１は、ＩＰアドレスとＴＣＰポート番号を分離する。比較器１１２は、分離されたＴＣＰポート番号を、設定されている比較値と比較し、ＴＣＰポート番号が、その比較値以上の値であれば１を、比較値より小さいとき０を出力する。レンジＩＤ生成部１１３は、比較器１１２からの８ビットから、４ビットのレンジＩＤを生成する。レンジ検索データ生成部１１４は、分離されたＩＰアドレスとレンジＩＤを結合して、ＣＡＭ１に供給する。ＣＡＭ１は、ＩＰアドレスＤＡとレンジＩＤを検索データとして、ワードメモリを検索する。【選択図】      図７
2004318951.tif 000002
【特許請求の範囲】
【請求項１】
第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶手段と、
第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成手段と、
前記生成手段により生成された前記検索属性データを含む第２の検索データに対応する前記第２の被検索データを記憶している前記記憶部を検出する検出手段と
を備えることを特徴とする検索装置。
【請求項２】
前記属性は、データの値の大きさであり、
前記生成手段は、前記第１の検索データの全部または一部の値の大きさを、Ｎ個の比較値と比較し、それぞれの前記比較値との比較結果に基づいて、前記検索属性データを生成し、
前記被検索属性データは、前記第１の被検索データの全部または一部を、Ｎ個の前記比較値と比較して得られたそれぞれの比較結果に基づくデータである
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶ステップと、
第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成ステップと、
前記生成ステップの処理で生成された前記検索属性データを含む第２の検索データに対応する前記第２の被検索データを記憶している前記記憶部を検出する検出ステップと
を含むことを特徴とする検索方法。
【請求項４】
第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶ステップと、
第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成ステップと、
前記生成ステップの処理で生成された前記検索属性データを含む第２の検索データに対応する前記第２の被検索データを記憶している前記記憶部を検出する検出ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項５】
第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶ステップと、
第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成ステップと、
前記生成ステップの処理で生成された前記検索属性データを含む第２の検索データに対応する前記第２の被検索データを記憶している前記記憶部を検出する検出ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、検索装置および方法、記録媒体、並びにプログラムに関し、特に、連想メモリを利用した検索を効率的に行うことができるようにした検索装置および方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
図１は、連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ，内容アドレス式メモリ；Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ（ＣＡＭ））１の構成例を示している（特許文献参照）。
【０００３】
入力制御部１１は、外部から入力された、例えば、検索のためのデータ（検索データ）をラッチして、マスクレジスタ１２に供給する。
【０００４】
マスクレジスタ１２は、入力制御部１１から入力されたマスクデータ選択信号により、検索に関与させないデータ部分にマスクをかけるために、自分自身が記憶するマスクデータをＣＡＭブロック１３に供給する。
【０００５】
ＣＡＭブロック１３には、図２に示すように、ｍビットの複数のワードメモリ２１−１，２１−２，・・・（以下、個々に区別する必要がない場合、ワードメモリ２１と称する。他の場合も同様である）が設けられている。このワードメモリ２１には、例えば、検索されるデータ（被検索データ）を格納することができる。なお、被検索データを構成するビットには、１または０以外に、“Ｄｏｎ’ｔ  Ｃａｒｅ”を定義することができる。この“Ｄｏｎ’ｔ  Ｃａｒｅ”が定義されると、その部分は、検索の対象とされず、その他の部分が検索データと対応していれば、その被検索データを格納するワードメモリ２１が検索される。
【０００６】
ＣＡＭブロック１３は、制御部１７より、検索データに基づく検索の指令を受けると、検索データの、マスクジスタ１２によりマスクがかけられていない部分と一致するビットパターンを有する被検索データが格納されているワードメモリ２１を検索し、その検索結果を、出力制御部１６を介して出力する。
【０００７】
図３は、ＣＡＭ１を利用したパケットフィルタリングを行うルータ５１の利用例を示している。ルータ５１は、ＣＡＭ１を利用して、ネットワーク５２間のルーティングの時にパケットの通行を許可あるいは禁止する判断を行う。
【０００８】
ルータ５１は、ネットワーク５２から送信されてきたネットワークフレームから、ＩＰアドレスとＴＣＰポート番号等を抽出するとともに、それがＣＡＭ１に格納されており、転送可能なネットワークに属するものか否かを判定する。転送可能であると判定した場合、ルータ５１は、そのネットワーク５２に向けてデータを転送する。
【０００９】
図４は、ルータ５１のパケットフィルタリングに関する部分の構成例を示している。
【００１０】
ネットワークインタフェース（Ｉ／Ｆ）７１は、ネットワーク５２に接続され、そのネットワーク５２を介して送信されてきたネットワークフレームを受信し、検索データ抽出部７２に供給する。ネットワークＩ／Ｆ７１は、パケットバッファ７４から供給されたネットワークフレームを、送信先が接続されているネットワーク５２に転送する。
【００１１】
検索データ抽出部７２は、ネットワークＩ／Ｆ７１から供給されたネットワークフレームのヘッダ部分からディスティネーションＩＰアドレス（以下、ＩＰアドレスＤＡと称する）（３２ビット）およびディスティネーションＴＣＰポート番号（以下、ＴＣＰポート番号ＤＡと称する）（１６ビット）を抽出して、ＣＡＭ１に供給する。
【００１２】
ネットワークフレームのヘッダ部分には、ディスティネーションＩＰアドレスやディスティネーションＴＣＰポート番号が格納されている。
【００１３】
検索データ抽出部７２はまた、ネットワークＩ／Ｆ７１から供給されたネットワークフレームをそのまま出力制御部７３に供給する。
【００１４】
ＣＡＭ１（ＣＡＭブロック１３）のワードメモリ２１には、この場合、図５に示すように、転送可能なネットワーク５２に属するＩＰアドレスＤＡとＴＣＰポート番号ＤＡが格納されている（エントリされている）。なお、ＩＰアドレスＤＡは、８ビット単位で４つに区切られているが、その下位８ビット“ｘ”は、“Ｄｏｎ’ｔ  ｃａｒｅ”に定義されてエントリされている。“Ｄｏｎ’ｔ  ｃａｒｅ”に定義されている部分は、検索の対象から除外され、それ以外の部分が検索データと対応すれば、それを格納するワードメモリ２１は、検索される。
【００１５】
ＣＡＭ１は、検索データ抽出部７２からのＩＰアドレスＤＡとＴＣＰポート番号ＤＡを検索データとして、それが格納されているワードメモリ２１を検索し、その検索結果（ヒットした旨またはミスヒットした旨）を、出力制御部７３に出力する。
【００１６】
例えば、ＩＰアドレスＤＡが、４３．６．４８．１５のＩＰアドレスＤＡと２３のＴＣＰポート番号ＤＡが、検索データ抽出部７２から供給された場合、それに対応する被検索データがワードメモリ２１−１に格納されているので、この場合、ＣＡＭ１は、ヒットした旨を、出力制御部７３に出力する。
【００１７】
出力制御部７３は、ＣＡＭ１から、ヒットした旨の通知を受けると、検索データ抽出部７２から供給されたネットワークフレームを、パケットバッファ７４に供給する。一方、ミスヒットした旨の通知を受けると、出力制御部７３は、検索データ抽出部７２からのネットワークフレームを破棄する。
【００１８】
パケットバッファ７４に供給されたネットワークフレームは、そこで一時的に記憶された後、ネットワークＩ／Ｆ７１を介して、送信先に対応するネットワーク５２に転送される。
【００１９】
【特許文献】
特開平１０−２５５４８５号公報
【００２０】
【発明が解決しようとする課題】
ところで、ＩＰアドレスＤＡが、４３．６．４８．ｘであって、ＴＣＰポート番号が、例えば、０番から１０２４番までの範囲のパケットについて通行を許可する場合、ＣＡＭ１には、図６に示すように、各ＴＣＰポート番号についてのエントリが必要となり、結局、１０２４個のワードメモリ２１を使用することになる。
【００２１】
このように一定の範囲に属する被検索データ（ＴＣＰポート番号が０番から１０２４番までの範囲）についてもそれぞれエントリし、ワードメモリ２１を使用すると、ＣＡＭ１は、通常のＲＡＭに比べ、構造上、ビット単価が高いため、ルータ５１自体がコスト高になってしまう課題があった。
【００２２】
本発明はこのような状況に鑑みてなされたものであり、例えば、ルータ５１におけるＣＡＭ１の被検索データを効率よくエントリするものである。
【００２３】
【課題を解決するための手段】
本発明の検索装置は、第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶手段と、第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成手段と、生成手段により生成された検索属性データを含む第２の検索データに対応する第２の被検索データを記憶している記憶部を検出する検出手段とを備えることを特徴とする。
【００２４】
属性は、データの値の大きさとし、生成手段は、第１の検索データの全部または一部の値の大きさを、Ｎ個の比較値と比較し、それぞれの比較値との比較結果に基づいて、検索属性データを生成し、被検索属性データは、第１の被検索データの全部または一部を、Ｎ個の比較値と比較して得られたそれぞれの比較結果に基づくデータとすることができる。
【００２５】
本発明の検索方法は、第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶ステップと、第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成ステップと、生成ステップの処理で生成された検索属性データを含む第２の検索データに対応する第２の被検索データを記憶している記憶部を検出する検出ステップとを含むことを特徴とする。
【００２６】
本発明の記録媒体のプログラムは、第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶ステップと、第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成ステップと、生成ステップの処理で生成された検索属性データを含む第２の検索データに対応する第２の被検索データを記憶している記憶部を検出する検出ステップとを含むことを特徴とする。
【００２７】
本発明のプログラムは、第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データを記憶する記憶ステップと、第１の検索データの全部または一部の属性に対応する検索属性データを生成する生成ステップと、生成ステップの処理で生成された検索属性データを含む第２の検索データに対応する第２の被検索データを記憶している記憶部を検出する検出ステップとを含む処理をコンピュータに実行させることを特徴とする。
【００２８】
本発明の検索装置および方法、並びにプログラムにおいては、第１の被検索データの全部または一部の属性に対応する被検索属性データを含む第２の被検索データが記憶され、第１の検索データの全部または一部の属性に対応する検索属性データが生成され、生成された検索属性データを含む第２の検索データに対応する第２の被検索データを記憶している記憶部が検出される。
【００２９】
【発明の実施の形態】
図７は、本発明を適用したルータ１０１の構成例を示している。このルータ１０１には、図４のルータ５１のＣＡＭ１に代えて、ＣＡＭ１１５が設けられ、検索データ抽出部７２とそのＣＡＭ１１５の間に、分離部１１１、８個の比較器１１２−１乃至１１２−８、レンジＩＤ生成部１１３、およびレンジ検索データ生成部１１４が設けられている。
【００３０】
分離部１１１は、検索データ抽出部７２から抽出されたＩＰアドレスＤＡとＴＣＰポート番号ＤＡを分離して、分離したＴＣＰポート番号ＤＡを、比較器１１２のそれぞれに供給する。分離部１１１はまた、分離したＩＰアドレスＤＡをレンジ検索データ生成部１１４に供給する。
【００３１】
各比較器１１２のそれぞれには、所定の比較値が設定されている。例えば、図８に示すように、比較器１１２−１には、１０２４の、比較器１１２−２には、２０００の、比較器１１２−３には、４０００の、比較器１１２−４には、６０００の、比較器１１２−５には、８０００の、比較器１１２−６には、１００００の、比較器１１２−７には、３００００の、そして比較器１１２−８には、６５０００の比較値がそれぞれ設定されている。
【００３２】
比較器１１２は、分離部１１１から供給されたＴＣＰポート番号ＤＡを、設定されている比較値と比較し、ＴＣＰポート番号ＤＡが、その比較値以上の値であれば、１を、比較値より小さいとき、０を、それぞれレンジＩＤ生成部１１３に供給する。すなわちレンジＩＤ生成部１１３には、この例の場合、８ビットのデータが入力される。
【００３３】
レンジＩＤ生成部１１３は、比較器１１２からの８ビットを、４ビットにエンコードして（レンジＩＤを生成して）、レンジ検索データ生成部１１４に供給する。
【００３４】
例えば、ＴＣＰポート番号ＤＡが、テレネット（ＴＥＬＮＥＴ）の番号である２３などのＷｅｌｌ−ｋｎｏｗｎポートの番号である場合、各比較器１１２からの８ビットのデータ“００００００００”は、レンジＩＤ生成部１１３により、４ビット“０ｈ”（１６進数）にエンコードされる。
【００３５】
すなわち、図８に示すように、例えば、０乃至１０２３番のＴＣＰポート番号ＤＡからは、“０”のレンジＩＤが、１０２４乃至１９９９番のＴＣＰポート番号ＤＡからは、“１”のレンジＩＤが生成される。
【００３６】
なお、レンジＩＤ生成部１１３の出力を、４ビットとしたため、本来であれば、１６個の比較器１１２を設けることができ、１６種類の比較値を設定することができる。レンジＩＤのビット数を増やせば、比較値の種類を増やすことができる。
【００３７】
レンジ検索データ生成部１１４は、分離部１１１から供給されたＩＰアドレスＤＡとレンジＩＤ生成部１１３からのレンジＩＤを結合して、ＣＡＭ１に供給する。
【００３８】
ＣＡＭ１（ＣＡＭブロック１３）は、図９に示すように、ルーティング時に通行を許可するパケットのＩＰアドレスＤＡと、そのＴＣＰポート番号ＤＡが、比較値１１２のそれぞれに設定された比較値と同じ比較値と比較されることによって生成されたレンジＩＤを被検索データとしてワードメモリ２１に格納している。
【００３９】
すなわち、従来では、図６に示したように、ＩＰアドレスＤＡが、４３．６．４８．ｘであって、ＴＣＰポート番号ＤＡが、例えば、０番から１０２３番までの範囲のパケットについて通行を許可する場合、１０２４個のワードメモリ２１を使用したが、本発明では、その範囲を、レンジＩＤ（０）とＩＰアドレスＤＡ（４３．６．４８．ｘ）の１つのエントリで済むので（１個のワードメモリ２１−１（図９））、ワードメモリ２１を節約することができる。
【００４０】
ＣＡＭ１は、レンジ検索データ生成部１１４から供給された、ＩＰアドレスＤＡ（３２ビット）とレンジＩＤ（４ビット）を検索データとして、ワードメモリ２１を検索する。
【００４１】
すなわち図９に示すワードメモリ２１によれば、
ＩＰアドレスが４３．６．４８．０／２４でＴＣＰポート番号が０乃至１０２３、
ＩＰアドレスが４３．６．４９．０／２４でＴＣＰポート番号が０乃至１０２３、
ＩＰアドレスが４３．６．４８．０／２４でＴＣＰポート番号が１０２４乃至１９９９、
ＩＰアドレスが４３．６．４９．０／２４でＴＣＰポート番号が１０２４乃至１９９９、
ＩＰアドレスが４３．６．５０．０／２４でＴＣＰポート番号が２０００乃至３９９９、
ＩＰアドレスが４３．６．５１．０／２４でＴＣＰポート番号が２０００乃至３９９９、
ＩＰアドレスが４３．６．４８．０／２４でＴＣＰポート番号が４０００乃至５９９９、
ＩＰアドレスが４３．６．４９．０／２４でＴＣＰポート番号が４０００乃至５９９９、
ＩＰアドレスが４３．６．４８．０／２４でＴＣＰポート番号が６０００乃至７９９９、
ＩＰアドレスが４３．６．４９．０／２４でＴＣＰポート番号が８０００乃至９９９９
のパケットの転送が許可される。
【００４２】
以上のように、一定範囲のＴＣＰポート番号ＤＡのそれぞれについてエントリせずに、その範囲にレンジＩＤを付与してエントリするようにしたので、ＣＡＭ１のエントリ数（ワードメモリ２１）を節約することができる。
【００４３】
【発明の効果】
本発明によれば、被検索データのエントリ数を節約することができる。
【図面の簡単な説明】
【図１】ＣＡＭの構成例を示すブロック図である。
【図２】図１のＣＡＭのワードメモリの構成例を示す図である。
【図３】従来のルータの利用例を示す図である。
【図４】図３のルータの構成例を示すブロック図である。
【図５】図３のＣＡＭのワードメモリの構成例を示す図である。
【図６】図３のＣＡＭのワードメモリの他の構成例を示す図である。
【図７】本発明を適用したルータの構成例を示すブロック図である。
【図８】図７の比較器の比較値、およびその出力を示す図である。
【図９】図７のＣＡＭのワードメモリの構成例を示す図である。
【符号の説明】
７１  ネットワークインタフェース，  ７２  検索データ抽出部，  ７３  出力制御部，  ７４  パケットバッファ，  １０１  ルータ，  １１１  分離器，１１２  比較器，  １１３  レンジＩＤ生成部，  １１４  レンジ検索データ生成部
【図１】
2004318951.tif 000003
【図２】
2004318951.tif 000004
【図３】
2004318951.tif 000005
【図４】
2004318951.tif 000006
【図５】
2004318951.tif 000007
【図６】
2004318951.tif 000008
【図７】
2004318951.tif 000009
【図８】
2004318951.tif 000010
【図９】
2004318951.tif 000011