(57)【要約】【課題】消費電力の急増を抑制してノイズの発生を防ぐ。【解決手段】動作クロックに基づいて複数の検索キーを受信する第１及び第２の検索キー蓄積部と、予めアドレス条件を設定した複数の検索テーブル１２２−１、２と、複数の検索キーを複数の検索テーブル１２２−１、２に対応付ける検索キー分配部１２１と、複数の検索キーが対応付けられた複数のテーブルで並列的に検索を実行する検索制御部は、複数のテーブル１２２−１、２に対応付けられた検索キーについて、順次検索を開始する。【選択図】図３
2006135660.tif 000002
【特許請求の範囲】
【請求項１】
動作クロックに基づいて複数の検索キーを受信する検索キー受信部と、
予めアドレス条件を設定した複数の検索テーブルと、
前記複数の検索キーを前記複数の検索テーブルに対応付ける検索キー分配部と、
前記複数の検索キーが対応付けられた前記複数のテーブルで並列的に検索を実行する検索制御部と、を備えた連想メモリにおいて、
前記検索制御部は、前記複数のテーブルに対応付けられた検索キーについて、順次検索を開始することを特徴とする連想メモリ。
【請求項２】
前記検索制御部は、前記動作クロックの立ち上がりエッジと立ち下がりエッジで、前記複数の検索テーブルに対応付けられた検索キーについて順次検索を開始することを特徴とする請求項１に記載の連想メモリ。
【請求項３】
前記検索キー受信部は、前記動作クロックの立ち上がりエッジと立ち下がりエッジで、前記複数の検索キーを順次受信することを特徴とする請求項１に記載の連想メモリ。
【請求項４】
前記検索キー分配部は、前記検索キーを対応付ける検索テーブルを変更するための検索種別を設定する検索種別設定部を有し、
前記検索キー受信部は、前記検索種別を示す信号を受信する検索種別信号受信部を含み、
前記検索種別設定部は、前記検索種別信号受信部が受信した信号に基づいて前記検索キーを対応付ける検索テーブルを変更することを特徴とする請求項１に記載の連想メモリ。
【請求項５】
パケットを入力する入力回線と、
パケットを出力する複数の出力回線と、
宛先アドレスのビット毎に一致条件を指定した宛先アドレス条件と、宛先アドレス条件毎に転送情報を設定した経路エントリを複数備えて、前記入力回線へ入力されたパケットの宛先アドレスに一致する前記宛先アドレス条件を検索し、前記宛先アドレス条件に一致したパケットの転送先を、当該宛先アドレス条件に対応する転送情報に設定する経路テーブル検索部と、
前記転送情報に対応する前記複数の出力回線のいずれかに前記パケットを転送するパケット転送部と、
を備えたパケット転送装置において、
前記経路テーブル検索部は、
前記宛先アドレス条件を設定する複数のエントリを有する連想メモリと、
前記入力されたパケットの宛先アドレスと、前記連想メモリのエントリとを比較して、一致する宛先アドレス条件を検索する検索処理部と、
前記検索処理部で検索した前記パケットの宛先アドレスと一意に対応する宛先アドレス条件に基づいて、前記パケットの転送情報を設定する転送情報設定部と、を備え、
前記連想メモリは、
動作クロックに基づいて前記入力回線から複数の検索キーを受信する検索キー受信部と、
前記宛先アドレス条件を設定した複数の検索テーブルと、
前記複数の検索キーを前記複数の検索テーブルに対応付ける検索キー分配部と、
前記複数の検索キーが対応付けられた前記複数のテーブルで並列的に検索を実行する検索制御部と、を備え、
前記検索制御部は、前記複数のテーブルに対応付けられた検索キーについて、順次検索を開始することを特徴とするパケット転送装置。
【請求項６】
前記検索制御部は、前記動作クロックの立ち上がりエッジと立ち下がりエッジで、前記複数の検索テーブルに対応付けられた検索キーについて順次検索を開始することを特徴とする請求項５に記載のパケット転送装置。
【請求項７】
前記検索キー受信部は、前記動作クロックの立ち上がりエッジと立ち下がりエッジで、前記複数の検索キーを順次受信することを特徴とする請求項５に記載のパケット転送装置。
【請求項８】
前記検索キー分配部は、前記検索キーを対応付ける検索テーブルを変更するための検索種別を設定する検索種別設定部を有し、
前記検索キー受信部は、前記検索種別を示す信号を受信する検索種別信号受信部を含み、
前記検索種別設定部は、前記検索種別信号受信部が受信した信号に基づいて前記検索キーを対応付ける検索テーブルを変更することを特徴とする請求項５に記載のパケット転送装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速な経路テーブル検索を行う連想メモリ（ＣＡＭ＝Contents Addressable Memory）及びＣＡＭを用いたネットワーク装置に関する。
【背景技術】
【０００２】
ＩＰ（Internet Protocol）ネットワークを構成するルータやスイッチは、パケットの宛先を決定するルーティング検索や、パケットが属するフロー検出のためのフローテーブル検索を行っている。
【０００３】
このようなネットワーク装置では、検索を行うアドレスを検索キー（ビット列）として入力し、予め設定したテーブルで入力した検索キーに対応するアドレスを出力する連想メモリ（ＣＡＭ＝Contents Addressable Memory）を用いた経路テーブル検索方法が広く採用されている。
【０００４】
近年、ネットワーク規模の大型化やトラフィックの増加などにより、連想メモリ（以下、ＣＡＭ）の検索を高速化することが検討されている。ＣＡＭの高速化としては、ＣＡＭへ入力するデータ量を向上させる手法があり、単位クロック時間当りの入力データ量を増加させるため、クロック信号の立上がりエッジと立下りエッジの両エッジで異なるデータをＣＡＭへ送信するDouble Data Rate (以下，DDR)方式がある。
【０００５】
また、他の高速化としては、ＣＡＭの検索処理を並列的に行うことで、単位時間当たりの検索処理能力を向上するものが知られている（例えば、特許文献１）。これは、ＣＡＭの記憶領域を複数のバンクに分けておき、入力された検索キーを上位ビットと下位ビットに分け、複数のバンクで同時に上位ビットと下位ビットの検索処理を行うものである。
【特許文献１】米国特許第６３７４３２６号
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、上記特許文献１の従来例では、並列検索を行う複数のバンクの検索動作タイミングが同一タイミングである。この場合、ＣＡＭの全てのバンクが同時に検索されることになり、全く検索を行っていない状態から検索頻度が高くなる場合に、消費電流が大きく増加し、消費電流の増加に伴うＣＡＭ内の電源ノイズが大きくなり、このノイズによりＣＡＭの検索動作が正しく行われない可能性がある。
【０００７】
また、ＣＡＭの入力に関して上述のようなＤＤＲが知られているが、上記特許文献１の従来例では、検索キーの入力についてＤＤＲを適用した場合にどのようなタイミングで処理が行われるかについて記載はなく、一般的なＳＤＲ（Single  Data  Rate）を適用した場合では、並列化により検索処理を向上させても、入力の帯域幅が拡張されていないため、ＣＡＭ全体の性能向上は望めない、という問題がある。
【０００８】
本発明は、これらの問題点に鑑みてなされたもので、ＣＡＭへの検索キーの入力帯域とＣＡＭの検索性能をバランスさせて、ＣＡＭの全体的な性能を向上させながら、検索実行時の消費電流の急増に伴う電源ノイズを抑え、ＣＡＭの誤動作を防ぐことを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、動作クロックに基づいて複数の検索キーを受信する検索キー受信部と、予めアドレス条件を設定した複数の検索テーブルと、前記複数の検索キーを前記複数の検索テーブルに対応付ける検索キー分配部と、前記複数の検索キーが対応付けられた前記複数のテーブルで並列的に検索を実行する検索制御部と、を備え、前記検索制御部は、前記複数のテーブルに対応付けられた検索キーについて、順次検索を開始する。
【００１０】
また、前記検索キー受信部は、前記動作クロックの立ち上がりエッジと立ち下がりエッジで、前記複数の検索キーを順次受信する。
【発明の効果】
【００１１】
したがって、本発明は、複数の検索テーブルを異なる検索キーで順次検索処理を開始させてから並列的に処理することで連想メモリの高速化を達成し、複数の検索処理を順次開始するようにしたので、連想メモリの消費電力が段階的に上昇させることができ、消費電力の急増に起因するノイズの誘発を抑制して、安定した検索処理を実現できる。
【００１２】
また、検索キーの入力をＤＤＲで行うようにしたので、単位時間当たりに検索テーブルへ入力可能なデータ（検索キー）量を増大し、連想メモリの処理能力をさらに向上させることが可能となる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の一実施形態を添付図面に基づいて説明する。
【００１４】
図１は、本発明のＣＡＭ（Contents Addressable Memory）を用いたルータを示し、以下、ルータの概要動作を図１、図２および図３を用いて説明する。
【００１５】
図１は本発明のルータ２００のブロック図を示す。ルータ２００はネットワーク１からのパケットを受信するＮ個の入力回線２０１−ｉ（ｉ＝１〜Ｎ）と、ネットワーク１にパケットを送信するＮ個の出力回線２０２−ｉ（ｉ＝１〜Ｎ）と、送受信するパケットの処理を行うＮ個のインターフェース部２１０−ｉ（ｉ＝１〜Ｎ）と、インターフェース部２１０−ｉを結合する一つのパケット中継処理部２５０と、各インターフェース部２１０−ｉを制御するプロセッサ２８０から構成される。なお、プロセッサ２８０は、制御端末１０からの指令を受ける。
【００１６】
インターフェース部２１０−ｉは、パケットの受信処理を行うパケット受信回路２３０と、入力（受信）したパケットの宛先ＩＰアドレスに基づいて該パケットの次ホップＩＰアドレスと該パケットを出力する回線の番号（出力回線番号あるいはポート番号）を判定し、これらの情報をパケット受信回路２３０に出力する経路テーブル検索部１００と、パケット中継処理部２５０から受信したパケットの送信処理を行うパケット送信回路２７０と、ＭＡＣアドレスとＩＰアドレスの対応関係を示すＡＲＰ（Address Resolution Protocol）テーブル検索部２２０から構成される。
【００１７】
パケットが入力回線２０１−ｉより入力されるとパケット受信回路２３０は、受信したパケットのヘッダに内部ヘッダ部を付加して本パケットを蓄積すると同時に、ヘッダ内の宛先ＩＰアドレスを経路テーブル検索部１００に送信する。
【００１８】
経路テーブル検索部１００は前記宛先ＩＰアドレスより入力したパケットを出力する出力回線の番号である出力回線番号と該パケットを受信する次のホップ（ルータまたは端末）のＩＰアドレスである次ホップＩＰアドレスを判定し、パケット出力回線情報としてパケット受信回路２３０に送信する。
【００１９】
パケット受信回路２３０は、パケット出力回線情報内の出力回線番号と次ホップＩＰアドレスを内部ヘッダ部に書き込み、パケット中継処理部２５０へ送信する。
【００２０】
パケットを受信したパケット中継処理部２５０は、出力回線番号に対応するインターフェース部２１０−ｉのパケット送信回路２７０に当該パケットを送信する。パケット送信回路２７０は本パケットを蓄積すると同時に、内部ヘッダ部の次ホップＩＰアドレスをＡＲＰテーブル検索部２２０に送信する。
【００２１】
ＡＲＰテーブル検索部２２０は次ホップＩＰアドレスに対応するＭＡＣアドレスを判定し、ＭＡＣアドレス情報としてパケット送信回路２７０に送信する。
【００２２】
パケット送信回路２７０は上記ＭＡＣアドレス情報を受信すると、本情報内のＭＡＣアドレスを宛先ＭＡＣアドレスとして、インターフェース部２１０−ｉの入出力回線のＭＡＣアドレスを送信元ＭＡＣアドレスとしてそれぞれパケットに書き込み、内部ヘッダ部を削除して蓄積していたパケットを出力回線２０２−ｉに送信する。
【００２３】
次に図２は、本発明の経路テーブル検索部１００のブロック図を示す。経路テーブル検索部１００は宛先ＩＰアドレスを蓄積する宛先ＩＰアドレス蓄積部１８０が信号線２１を介してパケット受信回路２２０に接続され、宛先ＩＰアドレス蓄積部１８０は検索制御部１１０に接続される。検索制御部１１０の検索結果は、信号線２２を介してパケット受信回路２３０に接続される。
【００２４】
検索制御部１１０は、経路エントリのＩＰアドレス条件を設定するＣＡＭ１２０を有し、宛先ＩＰアドレス蓄積部１８０に格納された情報（検索キー）から、ルータ２００へ入力されたパケットの次ホップＩＰアドレスと出力回線番号を判定する。
【００２５】
本発明の経路テーブル検索部１００は、一つのＣＡＭ１２０の記憶領域を論理的に複数（例えば、２つ）のテーブル（検索グループ）に分割し、分割した第１検索グループ（検索テーブル）１２２−１と第２検索グループ（検索テーブル）１２２−２を用いて複数の検索キー（例えば、宛先ＩＰアドレス）を、予め設定したアドレス条件に一致するかを並列的に検索する。ここで、「並列的」とは、処理開始、終了時刻が一致する場合だけでなく、２以上の処理が同時に進行している期間が少なくとも０．５クロック存在することをいう。
【００２６】
ＣＡＭ１２０は複数ビットの一致条件を格納するエントリを複数備え、検索キーが入力されるとエントリ内の一致条件（アドレス条件）と検索キーの一致比較を行い、一致したエントリのアドレスのなかで最も小さなアドレス値を高速に出力する。
【００２７】
そして、ＣＡＭ１２０で一致すべきアドレス条件を判定した場合には、検索結果保持テーブル１６０より上記検索キーと一致したアドレス条件に対応する次ホップＩＰアドレスと出力回線番号を読み出して検索処理を終了する。
【００２８】
経路テーブル検索部１００は、上記検索結果に対応した次ホップＩＰアドレスと出力回線番号をパケット出力回線情報としてパケット受信回路２３０に送信し、パケット受信回路２３０はこのパケット出力回線情報に基づいてパケットをパケット中継処理部２５０に送信する。
【００２９】
図３は、本発明のＣＡＭ１２０のブロック図である。
【００３０】
ＣＡＭ１２０は、ＩＰアドレスなどの検索キーを伝達する信号線（データ線）２５を介して検索制御部１１０に接続され、検索制御部１１０はメモリクロック信号線２７の動作クロックに同期してＤＤＲ（Doble Data Rate）で宛先ＩＰアドレス蓄積部１８０に格納された複数の宛先ＩＰアドレス等を検索キーとしてＣＡＭ１２０に送信する。ＣＡＭ１２０は、受信した複数の検索キーで第１検索グループ１２２−１と第２検索グループ１２２−２を並列的に検索し、検索結果をメモリクロック信号線２７のクロックに同期して、ＤＤＲで検索制御部１１０に送信する。なお、ＣＡＭ１２０はメモリクロック信号線２７を介して検索制御部１１０からクロックの供給を受け、ＣＡＭ１２０の各部の同期をとる。
【００３１】
さらに、ＣＡＭ１２０は、検索の種別を示す情報を伝達する信号線２８を介して検索制御部１１０と接続され、後述するように、検索制御部１１０は、信号線２８を介して検索の種別（モード）を示す情報（以下、検索種別情報）をＣＡＭ１２０に送信し、ＣＡＭ１２０では受信した検索種別情報に応じて検索のモードを切り替える。
ＣＡＭ１２０の記憶領域は、複数の検索グループに論理的に分割されており、ここでは、第１の検索グループ１２２−１と第２の検索グループ１２２−２の２つで構成した場合を示す。
【００３２】
ＣＡＭ１２０は、検索制御部１１０から検索キー及び検索種別情報を受信し、複数の検索キーを第１検索グループ１２２−１と第２検索グループ１２２−２へ分配する検索キー分配部１２１を備える。ここで、信号線２５から受信する検索キーは、後述するように、クロック線２７の動作クロックの立ち上がり（Rise）エッジで一つの検索キーを受信し、同じくクロックの立ち下がり（Fall）エッジで一つの検索キーを受信するＤＤＲでデータ転送が行われる。
【００３３】
検索キー分配部１２１は、複数のデータ記憶ブロック１２３ａ−ｉ（但し、ｉ＝１〜ｎ）を備える第１検索グループ１２２−１と、複数のデータ記憶ブロック１２３ｂ−ｉ（但し、ｉ＝１〜ｎ）を備える第２検索グループ１２２−２へ、検索種別情報に応じてＤＤＲで受信した検索キーをそれぞれ投入し、並列的な一致検索を起動する。この並列的な一致検索をすることによって、ＤＤＲを用いて高速で受信した検索キーに対して逐一一致検索処理を行う場合に比べて、検索処理による遅延を低減することができ、高速に処理結果を出力することができる。
【００３４】
第１検索グループ１２２−１は、検索キーに一致したアドレス条件を生成するヒットアドレス生成回路１２４−１に接続され、同様に、第２検索グループ１２２−２は、検索キーに一致したアドレス条件を生成するヒットアドレス生成回路１２４−２に接続され、第１及び第２検索グループ１２２−１、２で行われた検索結果が生成される。
【００３５】
２つのヒットアドレス生成回路１２４−１、２の検索結果は、検索結果出力部１２５へ送られる。検索結果出力部１２５では、２つの検索結果をＤＤＲにより信号線２６を介して検索制御部１１０に送信する。
【００３６】
ここで、第１検索グループ１２２−１と第２検索グループ１２２−２の各データ記憶ブロック１２３ａ−ｉ、１２３ｂ−ｉは、図４に示すように構成され、各データ記憶ブロックはデータＡ０ｉ（ｉ＝１〜ｎ）とマスクＡ０ｉ（ｉ＝１〜ｎ）を格納する領域に分けられる。
【００３７】
そして各検索グループ１２２−１、２は所定のデータ幅ｗとデータ記憶ブロック数で構成され、例えば、データ幅ｗ＝７２bit、データ記憶ブロック数＝６４Ｋなどで構成される。この場合のＣＡＭ１２０のエントリ数は、データ記憶ブロック数に検索グループの数を乗じたものであり、上記の場合、１２８Ｋエントリとなる。これに対し、従来の並列検索処理では、同じ検索処理をしようとしたときに、１４４bitのＣＡＭのデータ幅に合わせて、ＤＤＲで入力した２つの７２bitの検索キーを合成して１４４bitの検索キーとし、この１４４bitの検索キーを複製して２つの１４４bitのＣＡＭにそれぞれ入力し、さらに１４４bitのデータ幅のうちそれぞれのＣＡＭでの検索対象外の７２bitにマスクをかけて検索を行うことがあった。この場合、それぞれのＣＡＭのデータ幅のうち、結果的にマスクをかけてしまう７２bit分は検索に関与しない無駄なデータ記憶領域になっていた。この従来技術に比べて、図４を用いて説明した上記ＣＡＭでは、無駄なデータ記憶領域を確保する必要がなくなり、同じ容量のＣＡＭでエントリ数又は並列段数を増やすことができる。
【００３８】
次に、図５は検索キー分配部１２１の詳細を示すブロック図である。検索キー分配部１２１は、検索制御部１１０からの検索種別情報を受信し、この検索種別情報に対応して第１または第２検索グループに検索の実行指示を指令する検索種別判定部１２１１を有する。
【００３９】
さらに、検索種別判定部１２１１は、データ線２５からクロック信号の立ち上がりエッジのデータを第１の検索キーとして取得し、蓄積する第１検索キー蓄積部１２１２へ第１の検索キーを第１検索グループ１２２−１へ送信するように指令する。また、検索種別判定部１２１１は、データ線２５からクロック信号の立ち下がりエッジのデータを第２の検索キーとして取得し、蓄積する第２検索キー蓄積部１２１３へ第２の検索キーを第２検索グループ１２２−２へ送信するように指令する。
【００４０】
また、検索種別判定部１２１１は、検索制御部１１０から受信した検索種別情報に応じて第１検索グループ１２２−１と第２検索グループ１２２−２で並列的に行われる検索のモードを切り替える。
【００４１】
この検索モードは、例えば、データ線２５から複数の検索キーが入力され、第１検索グループ１２２−１と第２検索グループ１２２−２で並列的に検索を実行する並列モードと、データ線２５から一つの検索キーが入力され、第１検索グループ１２２−１または第２検索グループ１２２−２の何れか一方で検索を実行する単独モードなどである。このモード切替を行うことによって、検索処理が集中的に必要な場合には高速検索のために並列処理を行い、検索処理がそれほど必要ない場合には一方の検索グループを用いずに消費電力を低減することができる。
【００４２】
検索制御部１１０は、データ線２５に検索キーを出力するとともに信号線２８に検索種別情報を出力する。
【００４３】
検索種別判定部１２１１は、信号線２８から受信した検索種別情報が並列モードを示す場合、第１検索キー蓄積部１２１２と第２検索キー蓄積部１２１３に、受信した検索キーを第１検索グループ１２２−１と第２検索グループ１２２−２へそれぞれ出力するよう指令する。この後、検索種別判定部１２１１は、第１及び第２検索グループ１２２−１、２に対して検索を実行するように指令する。また、検索種別判定部１２１１は、現在行っている検索の種別を検索結果出力部１２５に通知する。検索結果出力部１２５は、検索種別判定部１２１１からの検索種別情報に応じて、ヒットアドレス生成回路１２４−１または１２４−２の出力をどのように扱うかを決定する。このように検索種別判定部１２１１が検索種別を検索結果出力部１２５に通知することによって、ＤＤＲによる検索キー受信及び並列検索処理が行われた場合には、検索結果出力部１２５がこれに合わせてＤＤＲで結果を出力することができ、検索結果を遅延させることなく出力することができる。
【００４４】
図６は、検索結果出力部１２５の詳細を示すブロック図である。検索結果出力部１２５は、上記図５の検索種別判定部１２１１からの検索種別情報を受信して、検索モードを判定する検索種別判定部１２５１と、検索種別判定部１２５１からの指令に応じて、ヒットアドレス生成回路１２４−１から受信した第１の検索結果を出力する第１検索結果蓄積部１２５２と、検索種別判定部１２５１からの指令に応じて、ヒットアドレス生成回路１２４−２から受信した第２の検索結果を出力する第２検索結果蓄積部１２５３から構成される。
【００４５】
検索種別判定部１２５１は、検索種別情報が並列モードであれば、２つの検索結果蓄積部１２５２、１２５３に対して、ＤＤＲで検索制御部１１０に検索結果を送信するように指令し、単独モードの場合には第１検索結果蓄積部１２５２または第２検索結果蓄積部１２５３の何れか一方から検索結果を出力するよう指令する。
【００４６】
第１及び第２検索結果蓄積部１２５２、１２５３は、出力側を信号線２６に接続されており、並列モードの場合、第１検索結果蓄積部１２５２は、メモリクロック信号線２７のクロックに同期して立ち上がりエッジで第１の検索結果を信号線２６に送り、第２検索結果蓄積部１２５３は、メモリクロック信号線２７のクロックに同期して立ち下がりエッジで第２の検索結果を信号線２６に送る。
【００４７】
一方、検索種別判定部１２５１が単独モードと判定したときには、ヒットアドレス生成回路１２４−１または１２４−２の出力を取得した何れか一方の検索結果蓄積部の出力を信号線２６から送信する。
【００４８】
次に、図７を参照しながら、ＣＡＭ１２０で行われる処理の一例について説明する。この図７のフローチャートは、ＣＡＭ１２０に検索キーが入力されるたびに実行されるものである。
【００４９】
まず、Ｓ１では検索キー分配部１２１の検索種別判定部１２１１が検索制御部１１０から信号線２８より検索動作種別（検索種別情報）を受信して、検索処理を開始する。
【００５０】
Ｓ２では、検索種別判定部１２１１が、第１検索キー蓄積部１２１２および第２検索キー蓄積部１２１３に対して、受信した検索キーを記憶するように指令する。
【００５１】
Ｓ３では、検索キーの記憶指示を受信した第１検索キー蓄積部１２１２が、メモリ動作クロック信号の立上りエッジのタイミングにて、データ線２５から第１の検索キーを取得して、蓄積し、第１検索グループ１２２−１へ第１の検索キーを出力する。
【００５２】
Ｓ４では、検索キーの記憶指示を受信した第２検索キー蓄積部１２１３がメモリ動作クロック信号の立下りエッジのタイミングにて、データ線２５から第２の検索キーを取得し、蓄積し、第２検索グループ１２２−２へ第２検索キーを出力する。
【００５３】
Ｓ５では、検索種別判定部１２１１が、第１検索グループ１２２−１と第２検索グループ１２２−２へ検索の実行を指令する。また、検索キー分配部１２１は、検索結果出力部１２５に検索種別情報を送信する。このように検索種別を検索結果出力部に通知することによって、ＤＤＲによる検索キー受信及び並列検索処理が行われた場合には、検索結果出力部がこれに合わせてＤＤＲで結果を出力することができ、検索結果を遅延させることなく出力することができる。
【００５４】
Ｓ６では、第１検索グループ１２２−１と第２検索グループ１２２−２が、それぞれ上記入力された第１検索キーと第２検索キーの一致比較を並列的に行う。なお、本実施例では、第１検索グループ１２２−１と第２検索グループ１２２−２のデータＡ０−ｉとデータＢ０−ｉは同じであり、マスクＡ０−ｉとマスクＢ０−ｉも同一の内容とするが、検索目的によっては必ずしも同一の内容でなくてもよい。
【００５５】
第１検索グループ１２２−１と第２検索グループ１２２−２がそれぞれ、各エントリに設定されたアドレス条件と各検索キーとの比較を並列的に行う。そして、第１検索グループ１２２−１は検索結果をヒットアドレス生成回路１２４−１に出力し、第２検索グループ１２２−２は検索結果をヒットアドレス生成回路１２４−２に出力する。ヒットアドレス生成回路１２４−１、２では、それぞれ第１及び第２検索キーと一致したアドレス条件を生成して、検索結果出力部１２５へ出力する。
【００５６】
Ｓ７では、検索キー分配部１２１から検索種別情報を受信した検索結果出力部１２５が、第１検索結果蓄積部１２５２および第２検索結果蓄積部１２５３に検索結果を記憶するよう指令する。ヒットアドレス生成回路１２４−１、２からの検索結果は、図６に示したように、第１検索キーに対応する検索結果が第１検索結果蓄積部１２５２に格納され、第２検索キーに対応する検索結果が第２検索結果蓄積部１２５３に格納される。
【００５７】
Ｓ８では、検索結果の記憶指示を受信した第１検索結果蓄積部１２５２が、メモリ動作クロック信号の立上りエッジのタイミングにて、第１検索キーに対応する検索結果を信号線２６から検索制御部１１０へ出力する。
【００５８】
次に、Ｓ９では、検索結果の記憶指示を受信した第２検索結果蓄積部１２５３が、メモリ動作クロック信号の立ち下がりエッジのタイミングにて、第２検索キーに対応する検索結果を信号線２６から検索制御部１１０へ出力する。
【００５９】
以上の処理により、検索制御部１１０から入力された２つの検索キーに対して、第１検索グループ１２２−１と第２検索グループ１２２−２で並列的に検索が実行され、検索結果出力部１２５がＤＤＲで検索制御部１１０に出力することになる。このようにＤＤＲで出力することによって、ＤＤＲによる検索キー受信及び並列検索処理が行われた結果を遅延させることなく出力することができる。
【００６０】
上記ＣＡＭ１２０の動作について、図８のタイミングチャートを参照しながら説明する。
【００６１】
クロックが立ち上がりとなるＣ１の時点で、検索キー分配部１２１の検索種別判定部１２１１は第１検索キー（図中キー１）を取得し、次のクロックの立ち下がりとなるＣ２で、検索種別判定部１２１１は第２検索キー（図中キー２）を取得する。
【００６２】
そして、第１検索キー蓄積部１２１２及び第２検索キー蓄積部１２１３へ入力された第１及び第２検索キーは、Ｃ３、Ｃ４の時点で第１検索グループ１２２−１と第２検索グループ１２２−２へそれぞれ入力される。
【００６３】
第１検索グループ１２２−１では、Ｃ３〜Ｃ７の２クロックで第１検索キーの検索を行い、第２検索グループ１２２−２では、Ｃ４〜Ｃ８の２クロックで第２検索キーの検索を行う。したがって、Ｃ４〜Ｃ７の期間でＣＡＭ１２０の第１検索グループ１２２−１と第２検索グループ１２２−２は並列的に検索処理を実行する。なお、第１検索グループ１２２−１と第２検索グループ１２２−２の検索処理は、１クロックずつ２つのステップに分けて実行される。検索処理の負荷が低いときには、検索処理を１クロックで完了することも可能である。
【００６４】
Ｃ７〜Ｃ８では第１検索キーの検索結果に応じたアドレス条件が生成され、ヒットアドレス生成回路１２４−１から検索結果出力部１２５へ転送される。同様に、Ｃ８〜Ｃ９では第２検索キーの検索結果に応じたアドレス条件が生成され、ヒットアドレス生成回路１２４−２から検索結果出力部１２５へ転送される。
【００６５】
そして、Ｃ９のクロックの立ち上がりの時点で、信号線２６に第１検索キーの検索結果が出力され、Ｃ１０のクロックの立ち下がりの時点で、信号線２６に第２検索キーの検索結果が出力される。
【００６６】
このように、本発明のＣＡＭ１２０では、一つの記憶領域を２つの検索グループに分割し、各検索グループの各エントリの内容を同一のデータとマスクとすることにより、２つの異なる検索キーを並列的に処理することが可能となる。これにより、ＣＡＭ１２０の見かけ上の性能を向上することができるのである。
【００６７】
つまり、図８の例では、一つの検索キーの入力から出力までに４．５クロックを要しており、２つの検索キーの処理に要する時間は５クロックとなり、従来技術では１つ処理するのに４．５クロックを要する検索キーを２つの処理するには９クロックを要していたのに対し、見かけ上の性能（検索処理能力）は８０％程向上することになる。これにより、本発明では高速かつ低コストのＣＡＭを提供することができる。
【００６８】
次に、ＣＡＭの検索動作には多大な電力を必要とするため、上記従来例のように複数のテーブル（バンク）で同時に検索を開始する場合、ＣＡＭの消費電力が急激に増える。このため、ＣＡＭ内でノイズの発生を招くことになる。すなわち、前記従来例では、複数のテーブルで同時に検索処理の開始を開始するため、ＣＡＭの消費電力が急増し、一気に消費電力のピークに達するためノイズを誘発することになる。
【００６９】
これに対して、本発明のＣＡＭ１２０では、図８で示すように、第１検索キーの検索処理が開始される時刻Ｃ３で、第１検索グループ１２２−１の消費電力が増える。この後、第２検索キーの検索処理が開始される時刻Ｃ４で、第２検索グループ１２２−２の電力消費が増大する。したがって、検索処理の開始に伴う、ＣＡＭ１２０の消費電力の増加は、２段化に分けて行われることになる。
【００７０】
したがって、本発明では、ＣＡＭ１２０の複数の検索テーブルを順次作動させることで、消費電力が一気にピークに達するのを防ぎ、段階的に消費電力を上昇させるので、ノイズの発生を抑制することが可能となるのである。
【００７１】
以上のように、本発明によれば、複数の検索テーブルを順次作動させてから並列的に処理することでＣＡＭ１２０の高速化を達成し、また、データ記憶ブロックを無駄なく利用することができるので、大容量のＣＡＭ１２０を提供できるのである。さらに、複数の検索処理を順次開始するようにしたので、ＣＡＭ１２０の消費電力が急にピークに達するのを抑制し、ノイズの誘発を防止でき、安定した検索処理を実現できる。
【００７２】
＜変形例１＞
図９は、第１の変形例を示し、ＣＡＭ１２０に設定した２つの検索グループを構成する各データ記憶ブロック１２３ａ−ｉ、１２３ｂ−ｉからマスクを削除して、データのみとしたもので、その他の構成は上記実施形態と同様である。
【００７３】
検索キーにマスクを施す必要がない場合には、図１２のように、各エントリにはデータ（アドレス条件）のみを格納すれば良く、マスクを格納する記憶領域が不要となるので、さらに、ＣＡＭ１２０のエントリ数を増大することができる。
【００７４】
なお、上記実施形態において、ＣＡＭ１２０に検索キーを一つずつＤＤＲ入力する例を示したが、複数の検索キーを１ワードに結合し、ＣＡＭ１２０がワード単位で受信するようにしても良い。この場合、ＣＡＭ１２０は、１ワードから複数の検索キーを抽出し、これら複数の検索キーを、各検索グループへ順次投入すればよい。
【産業上の利用可能性】
【００７５】
以上のように、本発明は、ＣＡＭの検索リソースと、ＣＡＭと検索制御デバイス間の検索キーの入力帯域を有効活用し、経路テーブル検索を高速に行うことができるので、高速なルータやＬ３スイッチなどのパケット転送装置に適用することができる。
【図面の簡単な説明】
【００７６】
【図１】本発明の一実施形態を示す、ルータのブロック図。
【図２】ルータの経路テーブル検索部の構成を示すブロック図。
【図３】経路テーブル検索部のＣＡＭの構成を示すブロック図。
【図４】ＣＡＭの検索グループの一例を示す説明図。
【図５】ＣＡＭの検索キー分配部の詳細を示すブロック図。
【図６】ＣＡＭの検索結果出力部の詳細を示すブロック図。
【図７】ＣＡＭで行われる制御の手順の一例を示すフローチャート。
【図８】ＣＡＭで行われる制御の一例を示すタイミングチャート。
【図９】第１の変形例を示し、ＣＡＭの検索グループの一例を示す説明図。
【符号の説明】
【００７７】
１００  経路テーブル検索部
１２０  ＣＡＭ
１２１  検索キー分配部
１２２−１  第１検索グループ
１２２−２  第２検索グループ
１２４−１、２  ヒットアドレス生成回路
１２５  検索結果出力部
【図１】
2006135660.tif 000003
【図２】
2006135660.tif 000004
【図３】
2006135660.tif 000005
【図４】
2006135660.tif 000006
【図５】
2006135660.tif 000007
【図６】
2006135660.tif 000008
【図７】
2006135660.tif 000009
【図８】
2006135660.tif 000010
【図９】
2006135660.tif 000011