(57)【要約】【課題】ＩＰｖ６プロトコルに基づくルータ装置に設けられ、１個のＣＡＭ検索システムが、処理可能なビット幅よりも長いビット幅を有する検索キーを用いて、検索回数と検索速度とを高速化でき、かつプロセッサの処理負荷を軽減可能なルーティングエンジン装置を提供する。【解決手段】ルーティングエンジン装置１０が、ＩＰｖ６フレームと、フィルタ検索，フロー検索およびトレース検索の３種類の検索処理に要する検索情報を保持する領域および３種類の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサ１０ｃと、プロセッサ１０ｃにて変換されたヘッダ情報セルの検索情報に基づいて３種類の検索処理を行ない３種類の検索結果をそのヘッダ情報セルに書き込みそのヘッダ情報セルをプロセッサ１０ｃに送信するＣＡＭ検索システム１とをそなえて構成する。【選択図】  図２
2005012271.tif 000002
【特許請求の範囲】
【請求項１】
フレームのヘッダ情報に基づいて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置であって、
該フレームと、該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、
該プロセッサにて変換された該ヘッダ情報セルの該検索情報に基づいて該複数種類の検索処理を行ない該複数の検索結果を該ヘッダ情報セルに書き込み該ヘッダ情報セルを該プロセッサに対して送信する連想メモリ（以下、ＣＡＭ［Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ］検索システムと称する。）とをそなえて構成されたことを特徴とする、ルーティングエンジン装置。
【請求項２】
フレームのヘッダ情報に基づいて該フレームの転送処理をする転送処理部と該ヘッダ情報を用いて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置とを有するルータ装置であって、
該ルーティングエンジン装置が、
該フレームと、該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、
該プロセッサにて変換された該ヘッダ情報セルの該検索情報に基づいて該複数種類の検索処理を行ない該複数の検索結果を該ヘッダ情報セルに書き込み該ヘッダ情報セルを該プロセッサに対して送信するＣＡＭ検索システムとをそなえるとともに、
該転送処理部が、
該ＣＡＭ検索システムから送信された該ヘッダ情報セルを上記のフレームに変換し、該変換したフレームを外部ネットワークに接続された外部ノードに転送するように構成されたことを特徴とする、ルータ装置。
【請求項３】
フレームのヘッダ情報に基づいて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置におけるメモリ検索方法であって、
該フレームと、該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサが、該ヘッダ情報セルを送信するヘッダ情報セル送信ステップと、
該ＣＡＭ検索システムが、該ヘッダ情報セル送信ステップにて入力された該ヘッダ情報セルに含まれる検索情報に基づいて該複数の検索キーを生成する検索キー生成ステップと、
該ＣＡＭ検索システムが、該検索キー生成ステップにて生成された該複数の検索キーに基づいて該複数の検索処理を行なう検索処理ステップと、
該プロセッサが、該検索処理ステップにて検索処理された該複数の検索結果を表す複数の連想データを受信する検索結果受信ステップとをそなえたことを特徴とする、ルーティングエンジン装置におけるメモリ検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えばルータ装置（ルータ又は転送装置）のアドレス検索に関し、受信フレームのＩＰｖ６（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ６  ｐｒｏｔｏｃｏｌ）アドレスが、アドレステーブルに予め登録された登録ＩＰｖ６アドレスに保持されているか否かについて、ハードウェアを用いて高速検索するＣＡＭ検索（連想メモリ検索）に用いて好適な、ルーティングエンジン装置，ルータ装置およびルーティングエンジン装置におけるメモリ検索方法に関する。
【０００２】
【従来の技術】
近年、インターネットの利用者数の急激な増加によって、ＩＰアドレスの枯渇が指摘されており、より多くのＩＰアドレスを確保するために、移動通信システムは、ＩＰｖ６プロトコルへの対応を図っている。このＩＰｖ６プロトコルは、階層化アドレス（ＩＰｖ６アドレス）と呼ばれるアドレス割り当て手順を主に規定している（例えば非特許文献１）。
【０００３】
このＩＰｖ６アドレスは、１２８ビットを有し、前半の６４ビットおよび後半の６４ビットが結合したアドレスであって、例えば、１６進数を用いて、
「１０４０：０Ａ２３：０Ｃ１０：０８００：Ｃ０２Ｄ：００ＦＣ：Ｅ０９Ａ：７６ＢＢ」と表される。このアドレスの前半および後半は、それぞれ、ネットワークプレフィクス（ネットワーク識別子又はネットワークアドレス）およびホストＩＤ（Ｈｏｓｔ  Ｉｄｅｎｔｉｆｉｅｒ：ホストコンピュータ，端末，ルータ装置，ポート（物理ポート）又はインターフェースを表す。
【０００４】
このＩＰｖ６アドレスにより、アドレス枯渇が解消し十分な数のアドレスを確保でき、また、移動通信システムにおいて携帯端末にモバイルＩＰアドレスを割り当て可能となる。そして、各ルータは、ルーティングテーブル（アドレステーブル）をルックアップすることによりルーティング検索を行なう。さらに、各ルータは、受信フレームの種別判定と、受信フレームの破棄又は取得のための検索処理とを並行して処理するようになっている。
【０００５】
従来のルータの検索方法は、受信フレームのアドレスについて、ルーティングテーブルを参照してその受信フレームの転送先のポート情報を出力する。この検索は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ），ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）およびＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）を用いたソフトウェア処理によって行なわれている。
【０００６】
一方、近年、ＩＰｖ６プロトコルが一般化し、フレーム処理の高速化，大容量化が進展し、ソフトウェア処理を用いた検索は遅延が生じる。このため、各ルータは、ルーティング検索の機能の向上を図るために、例えば外付けのＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェアにより構成されたＣＡＭ検索システムを設けて、ＣＰＵの検索処理を支援し、検索の高速化を図っている。
【０００７】
ここで、ＣＡＭとは、多数のデータを保持するメモリである。また、ＣＡＭ検索システムとは、検索対象のデータとＣＡＭに保持されたデータとを比較して、その検索対象のデータを保持しているときにその保持アドレスを出力するものである。
ＣＡＭ検索システムにおけるテーブル検索の一例は、受信フレームが廃棄対象であるか否かの判定（フィルタ検索）と、受信フレームのプライオリティの取得（フロー検索）とが知られている。このプライオリティとは、ルータ又は伝送路において輻輳が生じたときの処理の優先度のレベルである。例えば、フレーム廃棄又は転送に関する判定、およびバッファに保持された複数のフレームデータのうちの他のフレームデータよりも先に読み出すか否かの判定は、このプライオリティに基づいて行なわれる。また、フロー検索は、入力されたフレームのうちの特定アドレスと、例えばＩＰｖ６プロトコルのような特定プロトコル種別とを有するものを検索する。ここで、フローとは、同一の条件により抽出されたフレーム群である。
【０００８】
図１８は従来のＣＡＭ検索システムの概略的な構成図である。この図１８に示すルータ１００は、アドレス解決するＮＤＰ（Ｎｅｔｗｏｒｋ  Ｄａｔａ  Ｐｒｏｃｅｓｓｏｒ：ネットワークデータプロセッサ）１００ａと、複数個のＣＡＭ検索システム１００ｂ〜１００ｄとをそなえて構成されている。
ここで、アドレス解決とは、ＩＰｖ６アドレスからＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスを取得することであり、例えば、受信フレームの送信先ＩＰｖ６アドレスに基づいてその受信フレームを出力するポート情報を出力する。
【０００９】
また、従来のテーブル検索は、ＮＤＰ１００ａが、１個の入力フレームから必要な情報を抽出し、２種類の検索についてそれぞれ２個の検索キー（ＳＥＡＲＣＨ  ＫＥＹ）を生成し、各検索キーをＣＡＭ検索システム１００ｂ〜１００ｃに送信している。
各ＣＡＭ検索システム１００ｂ〜１００ｄは、それぞれ、負荷の大きい（重い）検索処理に特化し、ＮＤＰ１００ａから入力された検索キーに基づいて検索処理するＣＡＭ部１０１ｂと、このＣＡＭ部１０１ｂにて検索された検索結果のアドレス（Ａｄｄｒｅｓｓ）から読み出した検索結果のＭＥＭデータ（ＤＡＴＡ）をＮＤＰ１００ａに対して送信するＭＥＭ部（連想データ保持部）１０１ａとをそなえて構成されている。このＭＥＭデータは、ＣＡＭ部１０１ｂが出力した検索結果アドレスにより示されるデータであって、ＣＡＭ部１０１ｂが、ＣＡＭ部１０１ｂに入力された検索データと一致（ヒット又はマッチ）するＣＡＭデータを保持している場合に出力される、その一致するＣＡＭデータにアドレスを介して対応付けられたデータ（連想データ）である。
【００１０】
そして、１個のＮＤＰ１００ａが、ＣＡＭ検索システム１００ｂ〜１００ｃからの複数の検索結果（ＨＩＴ  ＳＴＡＴＵＳ：ヒットステータスおよびＤＡＴＡ：検索結果データ）をマージし、マージされた検索結果に基づいてフレームを処理するようになっている。ここで、マージとは、特に断らない限り、複数のデータを１個のセルデータに併合することを意味する。
【００１１】
従って、ＮＤＰ１００ａが、複数の検索依頼を受信すると、その複数の検索のそれぞれについてＣＡＭ検索システム１００ｂ〜１００ｄのうちの検索に対応するものを選択して検索している。すなわち、複数の検索はフレーム毎に処理され、１回の検索依頼で１検索のみ検索結果が得られる。
また、検索キーは複数のビット幅を有し、処理可能なデータは、ＣＡＭ検索システム１００ｂ〜１００ｄの処理可能なビット幅よりも短いビット幅を有するデータに制約される。また、各検索結果は、ＮＤＰ１００ａによってマージされている。
また、アドレス検索方法は、種々のものが提案されている。
【００１２】
例えば、アドレスを上位と下位とに分割してサーチする機能を設けたアドレスサーチ装置（以下、アドレスサーチマシンと称する。）が提案されている（例えば特許文献１）。特許文献１記載のアドレスサーチマシンは、アドレスサーチ要求を出すパケットエンジンと、サーチ対象のアドレスを登録するＣＡＭと、ルーティング情報を格納するＳＳＲＡＭ（Ｓｙｎｃｈｒｏｎｏｕｓ  ＳＲＡＭ：シンクロナスＳＲＡＭ）と、ＣＡＭおよびＳＳＲＡＭの動作を制御するサーチマシンコントローラとを有し、ＩＰｖ４アドレスサーチ機能に加え、アドレスを上位と下位とに分割してサーチを実行するＩＰｖ６アドレスサーチ機能をそなえている。
【００１３】
これにより、従来のＩＰｖ４アドレスサーチマシンから、特別なハードウェアを追加することなく、ＩＰｖ６アドレスサーチが実現できる。
さらに、ハードウェアルーティングに必要とされる大容量かつ複数パラメータの検索を実現可能とするフレーム転送制御方法も提案されている（例えば特許文献２）。
【００１４】
特許文献２記載のフロー検索回路は、各登録データの有効／無効の範囲を、各ビット毎に設定できる可変マスク機能を有するＣＡＭを使用し、また、フィールドＩＤ検索部とフローＩＤ検索部に対しＣＡＭは共通に使用されるようになっている。
これにより、大容量の設定が可能なＲＡＭを用いたツリー検索と、複数のパラメータにより検索可能なＣＡＭを用いたフロー検索を組み合わせることにより、ハードウェアルーティングに必要とされる大容量かつ複数パラメータの検索を実現できる。
【００１５】
また、連想メモリを使用する方法も提案されている（例えば、特許文献３）。特許文献３には、検索データが複数のデータにまたがり、しかもそれら複数のデータの順序を入れ替える必要が生じる場合であっても高速検索を可能とする連想メモリが開示されている。
これにより、配列変換回路をそなえたものであるため、データの順序入れ替えのためのマイクロプロセッサをそなえる必要がなく、システムの簡単化，検索速度の向上が図られる。
【００１６】
【特許文献１】
特開２００２−２９０４４８号公報
【特許文献２】
特開２００２−１７６４３７号公報
【特許文献３】
特開平７−２２６０９２号公報
【非特許文献１】
ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ２４６０．ｔｘｔに記載されたプロトコル
【００１７】
【発明が解決しようとする課題】
しかしながら、このアドレス検索方法を用いると、３個以上のＣＡＭ検索システム１００ｂ〜１００ｄが必要となり、プロセッサの負荷が過大となりスループットが低下し、性能を十分に発揮できない。さらに、フィルタ検索等の各検索種別にそれぞれＣＡＭ検索システム１００ｂ〜１００ｄを要し、メモリ領域を有効に利用しにくい。
【００１８】
また、ＩＰｖ６プロトコルは、広大なアドレス空間を認識するために、ＣＡＭデータ（連想メモリデータ）および検索キーの各ビット幅を、既存のビット幅よりも長いビット幅に規定している。従って、ＩＰｖ６フレームに対応するルータを設計する場合、既存のＣＡＭ検索システム１００ｂ〜１００ｄは、処理可能なビット幅が短いので、長いビット幅のＩＰｖ６アドレスを、１回で処理することができない。
【００１９】
一方、ＣＡＭ検索システム１００ｂ〜１００ｄは、長いＩＰｖ６アドレスを例えば２個等の複数のアドレスに分割（分離）して、２回の検索を行なうこともできる（以下、２度引き検索と称する。）。この場合、ＣＡＭ検索システム１００ｂ〜１００ｄは、１回目の検索結果のインデックスを、２回目の検索キーとして入力される。このため、２回の検索に要する時間は、ヘッダ情報セルが生成される時間間隔（ＩＰｖ６フレームを受信する間隔）よりも長いので検索時間について制約を受けるという第２の課題がある。
【００２０】
そして、制御回路は、入出力ポートがいずれも連続的に常時アクセスされ、また、２回の書き込みおよび２回の読み出しを要するので、やはり、負荷が大きいという第３の課題がある。
そのうえ、特許文献１，２記載の装置は、いずれも、ＣＡＭ検索システム１００ｂ〜１００ｄの検索終了までのタイミング測定等の制御が必要であり、プロセッサの負荷が大きい。
【００２１】
さらに、データの高速化にともない、従来のルータにおけるプロセッサの処理速度は相対的に遅延し、この遅延によってプロセッサのオーバーヘッドが生じる。このオーバーヘッドは検索キーの生成および検索結果のマージ処理に起因するものである。このため、オーバーヘッドの処理負荷を分散でき、かつプロセッサに都合のよいインターフェースをサポートすることが望まれている。
【００２２】
本発明は、このような課題に鑑み創案されたもので、ＩＰｖ６プロトコルに基づくルータ装置に設けられ、１個のＣＡＭ検索システムが、処理可能なビット幅よりも長いビット幅を有する検索キーを用いて、検索回数と検索速度とを高速化でき、かつプロセッサの処理負荷を軽減可能なルーティングエンジン装置，ルータ装置およびルーティングエンジン装置におけるメモリ検索方法を提供することを目的とする。
【００２３】
【課題を解決するための手段】
このため、本発明のルーティングエンジン装置は、フレームのヘッダ情報に基づいてフレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置であって、フレームと、複数種類の検索処理に要する検索情報を保持する領域および複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、プロセッサにて変換されたヘッダ情報セルの検索情報に基づいて複数種類の検索処理を行ない複数の検索結果をヘッダ情報セルに書き込みヘッダ情報セルをプロセッサに対して送信する連想メモリ（ＣＡＭ）とをそなえて構成されたことを特徴としている（請求項１）。
【００２４】
また、本発明のルータ装置は、フレームのヘッダ情報に基づいてフレームの転送処理をする転送処理部とヘッダ情報を用いてフレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置とを有するルータ装置であって、ルーティングエンジン装置が、フレームと、複数種類の検索処理に要する検索情報を保持する領域および複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、プロセッサにて変換されたヘッダ情報セルの検索情報に基づいて複数種類の検索処理を行ない複数の検索結果をヘッダ情報セルに書き込みヘッダ情報セルをプロセッサに対して送信するＣＡＭ検索システムとをそなえるとともに、転送処理部が、ＣＡＭ検索システムから送信されたヘッダ情報セルを上記のフレームに変換し、変換したフレームをルータ装置の外部に転送するように構成されたことを特徴としている（請求項２）。
【００２５】
さらに、本発明のルーティングエンジン装置におけるメモリ検索方法は、フレームのヘッダ情報に基づいてフレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置におけるメモリ検索方法であって、フレームと、複数種類の検索処理に要する検索情報を保持する領域および複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサが、ヘッダ情報セルを送信するヘッダ情報セル送信ステップと、ＣＡＭ検索システムが、ヘッダ情報セル送信ステップにて入力されたヘッダ情報セルに含まれる検索情報に基づいて複数の検索キーを生成する検索キー生成ステップと、ＣＡＭ検索システムが、検索キー生成ステップにて生成された複数の検索キーに基づいて複数の検索処理を行なう検索処理ステップと、プロセッサが、検索処理ステップにて検索処理された複数の検索結果を表す複数の連想データを受信する検索結果受信ステップとをそなえたことを特徴としている（請求項３）。
【００２６】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（Ａ）本発明の一実施形態の説明
図１は本発明の一実施形態に係るルータ（ルータ装置又は転送装置）の構成例を示す図である。この図１に示すルータ８は、フレーム（ＩＰｖ４フレーム又はＩＰｖ６フレーム）のヘッダ情報に基づいてフレームの転送処理をする転送処理部とヘッダ情報を用いてフレームの転送に関する３種類の検索処理を行なうＩＰｖ６ルーティングエンジン（ルーティングエンジン装置又はルーティングエンジン部）とを有するものである。
【００２７】
このルータ８は、以下に詳述するように、受信したフレームのヘッダに含まれる送信先アドレス（送信先ＩＰｖ４アドレス又は送信先ＩＰｖ６アドレス）に基づいてアドレス解決して出力ポートに転送する転送機能と、フィルタ検索，フロー検索およびトレース検索の３種類の検索処理機能とを有する。これらの転送および３種類の検索は、ともに、ルータ８に設けられた本発明のＩＰｖ６ルーティングエンジン１０にて行なわれる。
【００２８】
また、ルータ８は、検索処理の種別について、４以上の所望の検索項目を設定することもでき、設計方針又は仕様等に基づいて種々の検索種別を増加させることが可能である。以下において、一例として３種類の検索処理について説明する。
なお、以下の説明において、ＩＰｖ４フレームおよびＩＰｖ６フレームの各々は、移動通信用のモバイルＩＰｖ４フレームおよびモバイルＩＰｖ６フレームをも含む。
【００２９】
（１）３種類の検索（フィルタ検索，フロー検索およびトレース検索）
（１−１）フィルタ検索は、ＩＰｖ６フレームが廃棄対象であるか否かを判定する処理であって、ＩＰｖ６フレームの送信元ＭＡＣアドレスおよび送信先ＭＡＣアドレスと、送信元ＩＰｖ６アドレスおよび送信先ＩＰｖ６アドレスと、ＩＰｖ６プロトコルの規定に基づいてフレーム転送又はフレーム破棄を行なう。
【００３０】
（１−２）フロー検索とは、ＩＰｖ６フレームのプライオリティの例えば８レベル（３ビット）のうちのいずれかを判定するための処理であって、ＩＰｖ６フレームのうちの特定アドレスを有するフレームと、例えばＩＰｖ６プロトコルのような特定プロトコル種別を有するフレームとを検索するための処理である。なお、フローとは同一の条件により抽出されたフレーム群を表す。また、プライオリティのレベルは８以下又は８以上の段階に設定することもできる。
【００３１】
（１−３）トレース検索とは、ＩＰｖ６フレームがトレース対象であるか否かを判定する処理であって、ネットワーク又はリンクにおいて、障害発生を検出するための障害検出用データと、転送状況を診断するための診断用データとをそれぞれ送受信するための処理である。トレースとは、フレームの送信元アドレスおよび送信先アドレス間において転送された経路又はノード（ルータ，サーバ装置又はクライアント装置）の履歴を意味する。換言すれば、トレース検索とは、ＩＰｖ６フレームの送信先ＩＰｖ６アドレス又はＩＰｖ６フレームの送信元ＩＰｖ６アドレスに基づいてＩＰｖ６フレームのうちの転送経路を出力するＩＰｖ６フレームを抽出するか否かを判定する検索処理を表す。
【００３２】
また、トレース検索は、受信したＩＰｖ６フレームが、処理の対象であるか否かを判定する点においてフィルタ検索の一種でもある。一方、トレース検索は、トレースに要する情報の抽出後においても受信フレームをバッファ部（バッファ又はセルバッファ）に保持する半面、フィルタ検索は、受信フレームから障害発生通知を受信し障害ノード又は障害箇所に関する情報が抽出されると、その受信フレームはバッファ部から消去される点で異なる。
【００３３】
（１−４）３種類の検索方法
これらの３種類の検索は、受信フレームの送信元ＩＰｖ６アドレスおよび送信先ＩＰｖ６アドレス等の検索対象データが、ルータ８に設けられたメモリに保持されているか否かを検索するものであり、検索対象データと同一データ又は検索対象データに対応するデータを保持している場合にその保持アドレスを出力する。
【００３４】
（１−５）３種類の検索の開始契機
３種類の検索の開始契機については、フィルタ検索およびフロー検索はともにＩＰｖ６フレームを受信する毎に行なわれる。トレース検索の開始契機は、一定間隔又はルータ８が有するネットワーク又はリンクのトラヒック量が、ネットワークの伝送速度，伝送容量，保守管理およびユーザとの契約に基づいて決定された閾値を超えたときに開始する。
【００３５】
（１−６）検索対象フレーム
ルータ８と外部装置（外部ノード）８７との間において送受信されるフレームは、ＩＰｖ４およびＩＰｖ６の両フレームである。このうちのＩＰｖ４フレームは、インターフェース部９０および本体スイッチ部９１において処理され、また、ＩＰｖ６フレームは、ＩＰｖ６ルーティングエンジン１０において処理される。
【００３６】
（１−７）３種類の検索を行なうモジュール
３種類の検索は、ＩＰｖ６ルーティングエンジン１０に設けられた後述するＣＡＭ検索システム１において行なわれ、また、転送機能は、ＩＰｖ６ルーティングエンジン１０に設けられたネットワークプロセッサ（ＮＤＰ１０ｃ）において行なわれる。すなわち、ＣＡＭ検索システム１が、処理負荷の大きい３種類の検索に特化し、これにより、ＮＤＰ１０ｃの負荷が軽減されるようになっている。
【００３７】
ここで、ＣＡＭ検索システム１にて参照される登録データ（蓄積データ）の登録方法と、その登録データを用いた検索方法について概略的に説明する。
登録データは、図３（ａ），図３（ｂ）および図４にそれぞれ示すＣＡＭアレイ３ａおよびＭＥＭアレイ４ａと接続された入出力インターフェース部３ｃ，４ｃから、データを入力することにより、あるいは管理者がデータを登録したメモリを設置することにより行なわれる。
【００３８】
さらに詳述すると、登録データの登録方法は、１個のＣＡＭアレイ３ａが登録可能なビット幅を有するデータの場合、参照される登録データをＣＡＭアレイ３ａに登録し、検索結果（例えば出力ポート情報）をＭＥＭアレイ４ａに登録する。このＭＥＭアレイ４ａのメモリアドレスは、ＣＡＭアレイ３ａのメモリアドレスと同一に割り当てられ（後述する図６，図１１（ａ），図１１（ｂ）参照）、ＣＡＭアレイ３ａとＭＥＭアレイ４ａとは共通のエントリアドレスを有する。従って、ＭＥＭアレイ４ａは、ＣＡＭアレイ３ａのエントリアドレスと同一のエントリアドレスに、読み出しのためのデータを保持している。すなわち、ＭＥＭアレイ４ａは、ＣＡＭアレイ３ａに入力されたエントリアドレスと一対一に対応させて検索結果（例えば出力ポート情報）を保持しているのである。
【００３９】
これにより、検索に必要なデータ（ＣＡＭエントリ）がＣＡＭ検索システム１に入力され、ＣＡＭ部３において、制御回路２から入力されたデータ（検索キー）がＣＡＭアレイ３ａ自身に保持されているか否かが検索される。そして、データが保持されている場合、ＣＡＭ部３が検索結果アドレスを出力し、このアドレスがＭＥＭ部４に入力される。ＭＥＭアレイ４ａはＣＡＭアレイ３ａに入力（登録）したＣＡＭエントリと同一アドレスに一対一に又は多対一に対応させて登録したデータを出力するのである。すなわち、この出力されたデータが検索結果（例えば出力ポート情報）である。
【００４０】
また、ＣＡＭ部３は、ＣＡＭ検索システム１が処理可能なＩＰｖ６アドレスのビット幅よりも長いビット幅を有するデータを検索する場合、長いデータを２分割し、前半と後半との２回の検索を行なう。この２回の検索結果を関連付けるために、本発明のルータ８はインデックスポインタを用いている。
これらの登録および検索について詳述する。以下、図１に示すインターフェース部９０および本体スイッチ部９１について説明し、その後ＩＰｖ６ルーティングエンジン１０について説明する。
【００４１】
（２）ルータ８の構成
図１に示すルータ８は、インターフェース部９０と、本体スイッチ部９１と、ＩＰｖ６ルーティングエンジン１０とをそなえて構成されている。
（２−１）インターフェース部９０
インターフェース部９０は、外部装置８７とルータ８とをインターフェースするものであって、ＣＰＵ９０ａ，ＲＯＭ８８，ＲＡＭ８９，第１スイッチ部９０ｂおよびインターフェース処理部９０ｃをそなえて構成されている。
【００４２】
ここで、外部装置８７は、ルータ８の入力ポートおよび出力ポートのそれぞれに接続されＩＰｖ４フレームおよびＩＰｖ６フレームをともに送受信するルータ又はサーバ装置又はクライアント装置であって、１００Ｍｂｐｓ（Ｍｅｇａ  Ｂｉｔ  Ｐｅｒ  Ｓｅｃｏｎｄ）イーサネッインターフェース又は１Ｇｂｐｓ（Ｇｉｇａ  Ｂｉｔ  Ｐｅｒ  Ｓｅｃｏｎｄ）イーサネット（Ｒ）インターフェース等のインターフェースを有する。以下の説明において、インターフェースとは、特に断らない限り、フレームフォーマットの変換を意味する。
【００４３】
ＣＰＵ９０ａは、ＲＯＭ８８およびＲＡＭ８９と協働して、インターフェース部９０ｃ，第１スイッチ部９０ｂを制御するものである。
インターフェース処理部９０ｃは、ルータ８自身と、１００Ｍｂｐｓイーサネット（Ｒ）インターフェース又は１Ｇｂｐｓイーサネット（Ｒ）インターフェース等の外部装置８７との間におけるフレーム送受信と、ルータ８内部の第１スイッチ部９０ｂとの間におけるフレーム送受信とを行なうものであって、フレームを送受信するための複数のインターフェースポートを有する。
【００４４】
なお、インターフェース部９０は、各ポートの接続先および各ポートの配置位置等に応じて複数のサブインターフェース部として構成されてもよい。
これにより、インターフェース部９０は、複数の異なるインターフェースのフレームを処理できる。
次に、第１スイッチ部９０ｂは、受信フレームがＩＰｖ４フレームの場合はそのＩＰｖ４フレームについてアドレス解決しその解決したアドレスを外部装置８７に送信するとともに、受信フレームがＩＰｖ６フレームの場合はそのＩＰｖ６フレームを本体スイッチ部９１に送信するものであって、ＩＰｖ４フレームについてのルーティングテーブル９０ｄとＩＰｖ４フレームについてアドレス解決するルーティングテーブルとを有する。
【００４５】
また、第１スイッチ部９０ｂは、本体スイッチ部９１にてスイッチされたＩＰｖ４フレーム又はＩＰｖ６フレームを受信し各フレームをインターフェース処理部９０ｃに送信する。
これにより、外部装置８７が送信したＩＰｖ４フレームは、インターフェース部９０のポートを介して第１スイッチ部９０ｂにおいて折り返し転送によりアドレス解決される。また、本体スイッチ部９１およびＩＰｖ６ルーティングエンジン１０のそれぞれにて折り返し転送されたＩＰｖ４フレームは、第１スイッチ部９０ｂをそのまま通過させられて外部装置８７に転送される。
【００４６】
また、外部装置８７が送信したＩＰｖ６フレームは、本体スイッチ部９１を介してＩＰｖ６ルーティングエンジン１０に転送される。一方、本体スイッチ部９１から送信されたＩＰｖ６フレームは、そのまま外部装置８７に送信される。
（２−２）本体スイッチ部９１
本体スイッチ部９１は、インターフェース部９０とＩＰｖ６ルーティングエンジン１０との間におけるフレームをスイッチ又は中継するものであって、インターフェース部９０およびＩＰｖ６ルーティングエンジン１０間においてＩＰｖ４およびＩＰｖ６の各フレームを送受信する第２スイッチ部９１ａと、この第２スイッチ部９１ａを制御する制御部（ＣＰＵ９１ｂ，ＲＯＭ８８およびＲＡＭ８９）とをそなえて構成されている。
【００４７】
ここで、第２スイッチ部９１ａは、ＩＰｖ４フレームについてアドレス解決するルーティングテーブル９１ｃを有する。
そして、インターフェース部９０と本体スイッチ部９１とが協働することにより、ＣＡＭ検索システム１から送信されたヘッダ情報セルを上記のＩＰｖ６フレームのヘッダに変換し、この変換したＩＰｖ６フレームを外部ネットワークに接続された外部装置８７に転送する転送処理部（９０，９１）として機能している。
【００４８】
また、この転送処理部（９０，９１）は、外部ネットワークに接続された外部装置８７とＮＤＰ１０ｃとの間のフレームフォーマットを変換し、ＩＰｖ４フレームおよびＩＰｖ６フレーム等の複数の受信フレームのうちのＩＰｖ４フォーマット（第１フォーマット）を有するＩＰｖ４フレーム（第１フレーム）を外部装置８７に対して折り返し転送するとともにＩＰｖ４フレームおよびＩＰｖ６フレーム等の複数の受信フレームのうちのＩＰｖ６フォーマット（第２フォーマット）を有するＩＰｖ６フレーム（第２フレーム）をＮＤＰ１０ｃに出力し、ＮＤＰ１０ｃからのＩＰｖ６フォーマット（第３フォーマット）を有するＩＰｖ６フレーム（第３フレーム）を外部装置８７に対して送信するようになっている。
【００４９】
これにより、第１スイッチ部９０ｂと同様に、外部装置８７からのＩＰｖ４フレームは、ルーティング又はアドレス解決されて折り返し転送される。また、本体スイッチ部９１は、ＩＰｖ６フレームを受信すると、ＩＰｖ６フレームをＩＰｖ６ルーティングエンジン１０に送信する。また、ＩＰｖ６ルーティングエンジン１０からのＩＰｖ６フレームは、そのまま、ルータ８を通過して外部装置８７に送信される。
【００５０】
なお、インターフェース部９０は、複数のサブインターフェース部から構成された場合は、各サブインターフェース部を特定したフレームの送受信ができるようになっている。
（３）ＩＰｖ６ルーティングエンジン１０
ＩＰｖ６ルーティングエンジン１０のフレームに関する処理は、受信したＩＰｖ６フレームについての受信フォーマット処理（第１フレーム処理）と、ＩＰｖ６フレームのアドレス解決および３種類の検索についての検索処理と、ＩＰｖ６フレームのヘッダを書き替えるヘッダ処理と、送信するＩＰｖ６フレームについての送信フォーマット処理（第２フレーム処理）との主に４種類であり、次の（３−１）〜（３−４）に説明する。また、３種類の検索処理は、ＣＡＭ検索システム１によって行なわれ、（３−２−２）に説明する。３種類の検索処理以外の各処理は、ＮＤＰ１０ｃによって行なわれる。
【００５１】
（３−１）第１フレーム処理
第１フレーム処理は、受信したＩＰｖ６フレームのヘッダ情報の抽出と、ＩＰｖ６フレームのペイロード（ペイロードデータ）の一時的な保持と、抽出したヘッダ情報にルータ８の装置内部情報の付加とをＮＤＰ１０ｃにて行なう。
（３−２）検索処理
検索処理は、ＩＰｖ６フレームのアドレス解決処理と、３種類の検索処理との両処理を含む。
【００５２】
（３−２−１）アドレス解決
アドレス解決は、受信したＩＰｖ６フレームのヘッダの送信先ＩＰｖ６アドレスに基づいて出力ポートを選択することである。
（３−２−２）本発明の３種類の検索方法（ルーティングエンジン装置におけるメモリ検索方法）
本発明のルーティングエンジン装置におけるメモリ検索方法は、フレームのヘッダ情報に基づいてフレームの転送に関する３種類の検索処理を行なう。ここで、３種類の検索のうちのフィルタ検索とフロー検索とは、いずれも、ＩＰｖ６ルーティングエンジン１０にて、各ＩＰｖ６フレームについて行なわれる。トレース検索は、設定時に、各ＩＰｖ６フレームについて行なわれる。管理者又は管理プログラムが、障害データおよび診断データの収集又は診断を必要と判定したときに設定される。
【００５３】
ヘッダ情報セルは、ＮＤＰ１０ｃによってＣＡＭ検索システム１に送信され、このＣＡＭ検索システム１において、ヘッダ情報セルに含まれる検索情報に基づいて検索される。その後、この検索結果は、ＣＡＭ検索システム１によってヘッダ情報セルに書き込まれ、ＮＤＰ１０ｃに送信される。
図７は本発明の一実施形態に係るヘッダ情報セルのフォーマット例を示す図であって、この図７に示すヘッダ情報セルは、フィルタ検索，フロー検索およびトレース検索の各検索種別の識別情報と各検索結果データとのそれぞれの保持領域を有するメモリに保持されたデータである。このヘッダ情報セルは、受信したＩＰｖ６フレーム毎にＮＤＰ１０ｃによって生成され、ＩＰｖ６ルーティングエンジン１０のＣＡＭ検索システム１に設けられたバッファに送信される。そして、ヘッダ情報セルは、ＣＡＭ検索システム１によって検索キー（ＣＡＭに入力するＣＡＭエントリデータ）に変換され、この検索キーを用いて３種類の検索が行なわれる。
【００５４】
従って、ヘッダ情報セルは、ＮＤＰ１０ｃ，ＣＡＭ検索システム１およびＩＰｖ６ルーティングエンジン１０がそれぞれ書き込みおよび読み出し可能になっている。
これにより、各ＩＰｖ６フレームは、破棄対象か否かが判定され、そのＩＰｖ６フレームのプライオリティが抽出され、また、所定期間、ＩＰｖ６フレームは、トレース検索によってネットワークにおける障害発生の有無が検出される。
【００５５】
（３−３）ヘッダ処理
ヘッダ処理は、ルーティング検索により決定されたＩＰｖ６フレームの出力ポートの書き替えと、ＩＰｖ６フレームのヘッダの書き替えとを行なう。
（３−４）第２フレーム処理
第２フレーム処理は、ＮＤＰ１０ｃから第３スイッチ部１０ｂに対してＩＰｖ６フレームを送信するためのフォーマット処理であって、第１フレーム処理にて保持されたペイロードの読み出しと、そのペイロードを含む出力ＩＰｖ６フレームの再生成とを行なう。
【００５６】
なお、上記の４種類（第１フレーム処理，検索処理，ヘッダ処理および第２フレーム処理）の処理については、図８（ａ），図８（ｂ）を参照して後述する。
（３−５）ＩＰｖ４フレームおよびＩＰｖ６フレームのルーティング検索
これにより、ルータ８に入力されたＩＰｖ４フレームは、上記の第１スイッチ部９０ｂと第２スイッチ部９１ａとにてそれぞれルーティング検索されて折り返し転送される。
【００５７】
一方、ＩＰｖ６フレームは、インターフェース部９０，本体スイッチ部９１を介してＩＰｖ６ルーティングエンジン１０に入力され、ＮＤＰ１０ｃによってそのＩＰｖ６フレームについてのルーティング検索される。
（３−６）ヘッダ情報セルを用いた本発明のルーティングエンジン装置におけるメモリ検索方法
本発明のルーティングエンジン装置におけるメモリ検索方法は、ＮＤＰ１０ｃが、ＣＡＭ検索システム１に対して３種類の検索処理に要する検索情報を保持する領域および３種類の検索結果を書き込むための領域を含むヘッダ情報セルを送信する（ヘッダ情報セル送信ステップ）。
【００５８】
次に、ＣＡＭ検索システム１が、ヘッダ情報セル送信ステップにて入力されたヘッダ情報セルに含まれる検索情報に基づいて３種類の検索キーを生成する（検索キー生成ステップ）。
そして、ＣＡＭ検索システム１が、検索キー生成ステップにて生成された３種類の検索キーに基づいて３種類の検索処理を行なう（検索処理ステップ）。
【００５９】
また、ＮＤＰ１０ｃが、検索処理ステップにて検索処理された３種類の検索結果を表す３種類の連想データを受信する（検索結果受信ステップ）。
この連想データとは、ＣＡＭ検索システム１が出力した検索結果データであって、ＣＡＭ検索システム１において、ＣＡＭ検索システム１に入力された検索データと一致するデータが保持されている場合に出力されるその一致するデータにアドレスを介して対応付けられたデータである。
【００６０】
（３−６−１）フィルタ検索
これにより、フィルタ検索の場合は、ＮＤＰ１０ｃが、図７に示すヘッダ情報セルの９，１０を付された領域（以下、領域９，１０と表示する。）に、受信フレームから抽出した送信元ＩＰｖ６アドレスおよび送信先ＩＰｖ６アドレスを書き込み、そして、この送信元および送信先の各ＩＰｖ６アドレスを含むヘッダ情報セルを、ＣＡＭ検索システム１に対して渡す。そして、ＣＡＭ検索システム１は、受信フレームに含まれる送信元ＩＰｖ６アドレス，送信先ＩＰｖ６アドレスと、予め保持した検索対象用のＩＰｖ６アドレスとを比較する。
【００６１】
ここで、両ＩＰｖ６アドレスが一致（ヒット）した場合には、ＣＡＭ検索システム１は、受信フレームを廃棄対象と認識し、図８に示すテーブル２の連想データの「ｄｉｓｃａｒｄ」をアクティブにする。また、ヘッダ情報セル全体をみたときは、図７に示すヘッダ情報セルの最上段の「廃棄」領域のビットがオン（アクティブ）にされ、このヘッダ情報セルがＮＤＰ１０ｃに返される。以後、ＮＤＰ１０ｃは、その「廃棄」対象のビットの処理を停止するのである。
【００６２】
このように、フィルタ検索時の検索対象データに、ＩＰｖ６アドレスが用いられる。なお、図５に示すＣＡＭエントリに含まれる他のフィールドデータ（例えば送信元ポート番号等）を検索対象とすることもできる。
（３−６−２）フロー検索
また、フロー検索の場合は、ＣＡＭ検索システム１は、ヘッダ情報セルに８レベルのいずれかの値をプライオリティ領域に書き込み、ヘッダ情報セルをＮＤＰ１０ｃに返す。
【００６３】
なお、フィルタ検索およびフロー検索の開始の各契機は、ヘッダ情報セルの送信とともに、常時、行なわれる。
（３−６−３）トレース検索
トレース検索は、障害発生の有無を判定するので、必ずしも常時行なわれるものではない。このトレース検索は、ルータ８が障害発生を検出するためのトレースモードに移行したときに行なわれる。
【００６４】
（３−６−４）従来の検索方法と本発明のルーティングエンジン装置におけるメモリ検索方法との比較
従来の検索方法は、１回の検索依頼に対して１個の検索結果のみが得られた。すなわち、従来の検索は、フィルタ検索およびフロー検索のそれぞれについて２個の検索テーブルを要し、また、２個の検索テーブルのそれぞれを読み出して検索結果を書き込みしていたので、処理遅延が生じることがあった。
【００６５】
これに対して、本発明のルーティングエンジン装置におけるメモリ検索方法によれば、ＮＤＰ１０ｃがヘッダ情報セルをＣＡＭ検索システム１に１回送信することにより、ＣＡＭ検索システム１に対して３種類の検索を依頼でき、また、ＣＡＭ検索システム１から受信したヘッダ情報セルから３種類の検索結果を取得できる。さらに、ＮＤＰ１０ｃは、受信したヘッダ情報セルに含まれる検索結果以外の情報も参照することができる。
【００６６】
従って、ＣＡＭ検索システム１が、３種類の検索に要する処理を支援するので、ＮＤＰ１０ｃの負荷が軽減され、高速かつ大容量のＩＰｖ６フレームのトラヒックを効果的に処理できる。
なお、ＮＤＰ１０ｃの機能は、通常のプロセッサ又はＣＰＵにより実現され、また、ＮＰ（Ｎｅｔｗｏｒｋ  Ｐｒｏｃｅｓｓｏｒ）又はＮＰＵ（Ｎｅｔｗｏｒｋ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と同義である。
【００６７】
（４）ＩＰｖ６ルーティングエンジン１０の構成
ＩＰｖ６ルーティングエンジン１０は、フレームのヘッダ情報に基づいてフレームの転送に関する３種類の検索処理を行なうものであって、ＣＰＵ１０ａ，ＲＯＭ８８およびＲＡＭ８９と、第３スイッチ部１０ｂと、ＮＤＰ１０ｃと、ＣＡＭ検索システム１とをそなえて構成されている。ＩＰｖ６ルーティングエンジン１０は、ＩＰｖ６アドレス宛先ポート解決をも行なう。
【００６８】
（４−１）ＣＰＵ１０ａ，ＲＯＭ８８およびＲＡＭ８９
ＣＰＵ１０ａ，ＲＯＭ８８およびＲＡＭ８９は、協働することにより、第３スイッチ部１０ｂ，ＮＤＰ１０ｃおよびＣＡＭ検索システム１のそれぞれを制御するものである。
（４−２）第３スイッチ部１０ｂ
第３スイッチ部１０ｂは、本体スイッチ部９１からのＩＰｖ４フレームを受信した場合は、ＩＰｖ４フレームをルーティングおよびアドレス解決して折り返し転送し、また、ＩＰｖ６フレームを受信した場合は、ＩＰｖ６フレームをＮＤＰ１０ｃに送信するものである。第３スイッチ部１０ｂは、受信ＩＰｖ４フレームについてルーティングおよびアドレス解決のためのルーティングテーブル１０ｄとを有する。
【００６９】
また、第３スイッチ部１０ｂは、ＮＤＰ１０ｃからのＩＰｖ６フレームについてのルーティングおよびアドレス解決されたＩＰｖ６フレームを受信しそのＩＰｖ６フレームを本体スイッチ部９１に送信する。
これにより、第３スイッチ部１０ｂは、本体スイッチ部９１およびＩＰｖ６ルーティングエンジン１０間においてＩＰｖ４フレームを折り返し転送し、また、ＩＰｖ６フレームをＮＤＰ１０ｃに送信する。
【００７０】
（４−３）ＮＤＰ１０ｃ
ＮＤＰ１０ｃは、ＩＰｖ６フレームと、３種類の検索処理に要する検索情報を保持する領域および３種類の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するものである。
このＮＤＰ１０ｃは、ＩＰｖ６フレームに含まれるヘッダ情報とルータ８の装置内部情報とを含むヘッダ情報セルを、３種類の検索処理に要する検索情報として生成するようになっている。この装置内部情報とは、例えば図７に示すように、３種類の検索処理を識別するための識別情報（３種類の検索処理について処理内容を識別するための識別情報。つまり、識別情報は各々の検索結果を表す。），受信したＩＰｖ６フレームの送信元ＩＰｖ６アドレスおよび送信先ＩＰｖ６アドレス等の情報である。
【００７１】
具体的には、ＮＤＰ１０ｃは、ＣＡＭ検索システム１との間におけるヘッダ情報セルの入出力と、ＩＰｖ６フレームについてのアドレス解決およびプレフィクス検索と、第３スイッチ部１０ｂとの間のＩＰｖ６フレーム送受信機能との各処理を行なう。ここで、プレフィクスはネットワーク識別子であり、ＩＰｖ６アドレスの前半に格納されたデータである。
【００７２】
また、ＮＤＰ１０ｃのＩＰｖ６フレームとヘッダ情報セルとを相互変換するためのメモリ（メモリ領域）は、ＣＡＭ検索システム１に設けられたバッファ部５又は別個のバッファ部（図示省略）を設けてもよい。
ここで、ヘッダ情報セルの入出力（処理）機能は、ＮＤＰ１０ｃに加えてＣＰＵ１０ａ（又はＮＤＰ１０ｃ），ＲＯＭ８８およびＲＡＭ８９が協働することにより実現される。また、アドレス解決機能およびプレフィクス機能は、いずれも、ＣＰＵ１０ａ，ＲＡＭ８９およびルーティングテーブル９１ｄの各々の協働により実現される。このルーティングテーブル９１ｄはＩＰｖ６フレームについてのルーティングテーブルである。さらに、第３スイッチ部１０ｂとの間のＩＰｖ６フレームの送受信機能は、ＮＤＰ１０ｃに加えてＣＰＵ１０ａ（又はＮＤＰ１０ｃ），ＲＯＭ８８およびＲＡＭ８９が協働することにより実現される。
【００７３】
これにより、ヘッダ情報セルの送受信機能について、ＮＤＰ１０ｃは、ＣＡＭ検索システム１に対してヘッダ情報セルを渡す（検索依頼）とともに、ＣＡＭ検索システム１からヘッダ情報セルを返される（結果受信）。さらに、ＮＤＰ１０ｃは、第３スイッチ部１０ｂからＩＰｖ４フレームを受信し、また、ＣＡＭ検索システム１にてアドレス解決されたデータリンクレイヤアドレスを有するＩＰｖ６フレームを第３スイッチ部１０ｂに対して送信する。
【００７４】
従って、ＮＤＰ１０ｃは、ルーティングに関する処理を行なうために、１種類の受信ＩＰｖ６フレームについて、その受信ＩＰｖ６フレームのヘッダ情報とルータ８の装置内部情報とを含む固定長フォーマットのセル（ヘッダ情報セル）形式を用いて、ＩＰｖ６フレームに関する情報を内部処理している。
このように、ＮＤＰ１０ｃは、フィルタ検索，フロー検索およびトレース検索を支援するとともに、ＩＰｖ６フレームの経路検索に基づくアドレス解決を支援する。
【００７５】
（４−４）ヘッダ情報セルのフォーマット
図７は本発明の一実施形態に係るヘッダ情報セルのフォーマット例を示す図であって、ＣＡＭ検索システム１のバッファに保持されているデータ例が表示されている。この図７に示すヘッダ情報セルは、ＮＤＰ１０ｃが処理するセルのサイズに適合するように固定長のフォーマットを有し、そのサイズの一例は、３２ビット幅で２４行である。
【００７６】
ここで、２〜１０を付された領域（領域２〜１０）は、３種類の検索を識別する検索キー（Ｓｅａｒｃｈ  Ｋｅｙ：検索キーデータ）の作成のために参照する領域である。
また、１１〜１６を付された領域（以下、領域１１〜１６と表示する。）は、ＣＡＭ検索システム１が書き込む領域であって、検索結果およびステータス信号を一緒にマージ（複数のデータを１セルデータに集約，併合又は結合すること。）して値を書き込む領域である。なお、領域２〜１６以外の領域（影付きで表示された領域）は、ＣＡＭ検索システム１による書き込みおよび読み出しが不要な領域を表す。
【００７７】
換言すれば、ＮＤＰ１０ｃは、検索に必要なデータをヘッダ情報セルの領域２〜１０に書き込み、この書き込みしたヘッダ情報セルをＣＡＭ検索システム１に渡す（入力する）。また、ＣＡＭ検索システム１はその領域２〜１０のデータを用いて検索し、その検索結果を領域１１〜１６に書き込む。そして、ＣＡＭ検索システム１は、検索結果が書き込まれたヘッダ情報セルをＮＤＰ１０ｃに対して出力する（返す）。
【００７８】
これにより、ＮＤＰ１０ｃは、フィルタ検索，フロー検索およびトレース検索の各検索結果を知る。また、ＮＤＰ１０ｃがＣＡＭ検索システム１に対して１個のヘッダ情報セルを渡すことが検索依頼に相当し、ＣＡＭ検索システム１がＮＤＰ１０ｃに対して３種類の検索結果をマージされたヘッダ情報セルを返すことが検索結果の通知に相当する。
【００７９】
ヘッダ情報セルについてさらに詳述すると、領域１１（ｄｉｓｃａｒｄ）はフレーム廃棄を指示するビットであり、このビットがＨ（Ｈｉｇｈ：アクティブを表す）であると、そのフレームが廃棄対象であることを表す。また、領域１２（Ｈｉｔ  Ｆｌａｇ）は入力フレームがプライオリティを含むことを表し、領域１３（ｐｒｉｏｒｉｔｙ）はフレームのプライオリティを８レベル（３ビット）で表す。これらの領域１２，１３によってプライオリティを得るためのフロー検索が行なわれる。さらに、領域１４（Ｈｉｔ  Ｆｌａｇ）はフレームがトレース対象であるか否かを１ビットで表すための領域である。また、領域１５（ｔｒａｃｅ−ｍｏｄｅ）はトレースモードを表す。なお、領域１６（ＣＡＭ  Ｅｒｒｏｒ）はＣＡＭ検索システム１が正常でない動作をしていることを表す。
【００８０】
これにより、ＮＤＰ１０ｃがＣＡＭ検索システム１に対してヘッダ情報セルを送信すると、ＣＡＭ検索システム１は、ヘッダ情報セルから検索に必要な情報を含む検索キーを生成する。検出キーは、ＣＡＭに入力するＣＡＭエントリデータであって、この検索キーを用いてＣＡＭ検索システム１がフィルタ検索を開始する。また、フィルタ検索されている間に、ＣＡＭ検索システム１は、フロー検索に必要な情報を含む検索キーを生成してフロー検索を開始する。同様に、フロー検索されている間に、ＣＡＭ検索システム１は、トレース検索に必要な情報を含む検索キーを生成してトレース検索を開始する。
【００８１】
そして、ＣＡＭ検索システム１は、フロー検索又はトレース検索と並行して、フィルタ検索の結果を含む連想データを出力し、さらに、検索処理して検索結果を出力するまでに要する時間が経過した後に得られるフロー検索の結果と、やはり検索結果が出力されるまでに要する時間後に得られるトレース検索の結果とをそれぞれ連想データとして出力する。また、３種類の検索結果を含む連想データは、１個のヘッダ情報セルにマージされ、マージされたヘッダ情報セルがＮＤＰ１０ｃに返される。
【００８２】
なお、フィルタ検索とフロー検索との２種類の検索のみを行なう場合においても、フィルタ検索およびフロー検索の各検索結果がマージされてヘッダ情報セルが出力される。
このように、ＮＤＰ１０ｃからＣＡＭ検索システム１に対して、１回の検索依頼メッセージを送信し、ＣＡＭ検索システム１が３種類の検索を行ない、かつ３種類の検索結果をＮＤＰ１０ｃに送信するので、ＮＤＰ１０ｃの負荷が大幅に減少しＮＤＰ１０ｃを支援できる。
【００８３】
（５）ＣＡＭ検索システム１
ＣＡＭ検索システム１は、ＮＤＰ１０ｃにて変換されたヘッダ情報セルの検索情報に基づいて３種類の検索処理を行ない３種類の検索結果をヘッダ情報セルに書き込みヘッダ情報セルをＮＤＰ１０ｃに対して送信するものである。ＣＡＭ検索システム１は、負荷の大きい（重い）検索処理を支援し、かつＮＤＰ１０ｃとの間においてヘッダ情報セルを入出力するようになっている。
【００８４】
図２は本発明の一実施形態に係るＣＡＭ検索システム１のブロック図である。この図２に示すＣＡＭ検索システム１は、ＩＰｖ６フレームについて廃棄又は通過を判定するフィルタ検索と、ＩＰｖ６フレームのプライオリティを判定するフロー検索と、ＩＰｖ６フレームの送信元ＩＰｖ６アドレス又は送信先ＩＰｖ６アドレスに基づいてＩＰｖ６フレームの転送経路を出力する対象となるＩＰｖ６フレームを抽出するか否かを判定するトレース検索との各検索処理を行ない、各検索結果をヘッダ情報セルに書き込むものであって、書き込みおよび読み出し部（以下、書き込み／読み出し部と表記する。）１ａと、ＣＡＭ部（検索結果保持部）３と、ＭＥＭ部（連想データ保持部）４と、制御回路（送受信制御回路）２とをそなえて構成されている。なお、図２に示す符号のうちの上述したものと同一符号を有するものは、それらと同一又は同一機能を有する。
【００８５】
（５−１）書き込み／読み出し部（書き込みおよび読み出し手段）１ａ
書き込み／読み出し部１ａは、制御回路２，ＣＡＭ部３およびＭＥＭ部４のそれぞれのデータについて、書き込みおよび読み出しをするものであって、例えばＬＳＩ（ＣＡＭ−ＬＳＩ）が用いられ、データ処理の高速化が図られている。
（５−２）ＣＡＭ部３
図３（ａ）は本発明の一実施形態に係るＣＡＭ部３のブロック図である。この図３（ａ）に示すＣＡＭ部３は、参照用の複数の登録データを保持し複数の登録データのうちの制御回路２にて生成された検索キーと一致する登録データのメモリアドレスを出力するものである。具体的には、このＣＡＭ部３は、アドレス解決と、３種類の検索（フィルタ検索，フロー検索およびトレース検索）と、各検索結果を示すステータス信号の出力とを行なうものであって、ＣＡＭアレイ３ａと、ＣＡＭメモリ制御部３ｂと、入出力インターフェース部（Ｉ／Ｏ  Ｉｎｔｅｒｆａｃｅ）３ｃとをそなえて構成されている。なお、このＣＡＭ部３は、例えばＬＳＩによって実現される。また、ＣＡＭ部３は、３種類の検索処理のうちの１種類又は２種類の検索処理を行なうようにもできる。
【００８６】
ここで、ＣＡＭアレイ３ａは、メモリセルが配列されたものであって、ｐ１行ｑ１列（ｐ１，ｑ１はともに自然数を表す。）のメモリセルを有するテーブルにより構成されている。
図３（ｂ）は本発明の一実施形態に係るＣＡＭアレイ３ａのデータ例を説明するための図である。この図３（ｂ）に示すＣＡＭアレイ３ａは、各アドレス（例えば０ｘ００００）に、メモリセル個数に相当する個数のメモリセル（２８８ビット）を保持している。ここで、「０ｘ」で始まる数値は１６進数を表す。
【００８７】
次に、図３（ａ）に示すＣＡＭメモリ制御部３ｂは、検索キー生成部６（図２参照）から受信した検索キーをＣＡＭアレイ３ａに入力し、また、ＣＡＭアレイ３ａにて検索演算されたメモリセルのアドレス（Ａｄｄｒｅｓｓ）とステータス信号（Ｓｔａｔｕｓ）とをそれぞれ検索結果として出力するものである。このＣＡＭメモリ制御部３ｂは、ヘッダ情報セルの連続したメモリ領域に３種類の検索テーブルを登録する登録部として機能し、登録された３種類のＣＡＭデータ（検索種別コードを含む）をＣＡＭ部３に保持するようになっている。
【００８８】
また、ステータス信号は、ＣＡＭアレイ３ａに、一致データが１個保持されていることを表す「ヒット」と、一致データが複数保持されていることを表す「マルチヒット」と、一致するデータがないことを表す「ミスヒット」とをそれぞれ出力する。
入出力インターフェース部３ｃは、制御回路２によるＣＡＭアレイ３ａに保持されたアドレスおよびデータの書き込みおよび読み出しを制御するものである。例えば、書き込み／読み出し部１ａは、通常のメモリと同様に、ＣＡＭアレイ３ａのメモリアドレスを指定しそのメモリアドレスに保持されたデータを読み出し、また、指定したメモリアドレスにデータすなわちＣＡＭエントリを書き込むのである。そして、入出力インターフェース部３ｃは、ＣＡＭアレイ３ａにヘッダ情報セル，ルーティングテーブルおよびアドレス解決テーブル等のデータを登録し、また、ＣＡＭアレイ３ａの保持データを読み出してデータ登録内容を確認する。
【００８９】
これにより、ＣＡＭメモリ制御部３ｂは、制御回路２から検索キーを指定して入力されると、検索キーについてＣＡＭアレイ３ａを検索し、検索キーに一致するＣＡＭエントリを保持している場合はそのＣＡＭエントリの保持アドレスと、ヒット（又はマルチヒット）を示すステータス信号とを出力する。また、ＣＡＭメモリ制御部３ｂは、検索キーに一致するＣＡＭエントリを保持していない場合はミスヒットを表すステータス信号を出力する。
【００９０】
なお、検索キーとＣＡＭエントリとは、共通のデータフォーマットを有し、また、データとしてＩＰｖ６アドレスを含むことができる。
また、これにより、ＩＰｖ６フレームについてのアドレス解決と、３種類の検索処理とが実現できる。
（５−３）ＭＥＭ部４
ＭＥＭ部４は、ＣＡＭ部３のアドレス配置と同一のアドレス配置を有しＣＡＭ部３から出力されたメモリアドレス（検索結果アドレス）に保持されたデータを出力するものである。このＭＥＭ部４は、ＭＥＭ部４自身又はＣＡＭ部３に保持した３種類の検索結果を含む連想データを制御回路２に入力する。ＭＥＭ部４は、ＭＥＭ部４自身に保持しているデータについての検索機能を有していない点で、保持データについて検索可能なＣＡＭ部３と異なる。また、機能ブロックはＣＡＭ部３に示すブロックと類似している。
【００９１】
図４は本発明の一実施形態に係るＭＥＭ部４のブロック図である。この図４に示すＭＥＭ部４は、ＭＥＭアレイ４ａと、ＭＥＭメモリ制御部４ｂと、入出力インターフェース部４ｃとをそなえて構成されている。各機能は例えば外付けのＩＣ又はチップデバイスにより実現される。
ここで、ＭＥＭアレイ４ａは、ｐ２行ｑ２列（ｐ２，ｑ２はともに自然数を表す。）のメモリセルを有し、図３（ｂ）に示すＣＡＭ部３と同様に、各メモリアドレスに、メモリセル個数に相当する個数のメモリセルを有する。このＭＥＭアレイ４ａは、連想データおよびインデックス等の検索テーブル（後述する）に定義された各種のデータを予め保持しており、また、メモリアドレスの配列は、ＣＡＭアレイ３ａのメモリアドレスの配列と同一にされている。
【００９２】
また、ＭＥＭメモリ制御部４ｂは、ＣＡＭ部３から入力されたメモリアドレスをＭＥＭアレイ４ａに入力するとともにＭＥＭアレイ４ａにてルックアップされた保持データを出力するものである。なお、ＭＥＭメモリ制御部４ｂは、メモリアドレスに加えてＣＡＭ部３から保持データの読み出し又は書き込みを制御するための制御信号も併せて入力されるようになっている。
【００９３】
さらに、入出力インターフェース部４ｃは、ＣＡＭ部３からのメモリアドレスおよび制御信号の入力に従って書き込み／読み出し部１ａとの間においてデータの書き込みおよび読み出しを制御するものであって、ＭＥＭアレイ４ａにデータを登録し、また、ＭＥＭアレイ４ａの保持データを読み出してデータ登録を確認する。
【００９４】
そして、ＭＥＭ部４は、検索結果の各情報データを制御回路２の検索結果処理部７に入力するようになっている。
これにより、検索動作は、ＣＡＭ部３は、入力された検索キーを用いてＣＡＭエントリ（ＣＡＭ部３に入力されるデータ）に照らして検索し、一致したデータを保持している場合は、その一致したデータが保持されたＣＡＭ部３自身のメモリアドレスをＭＥＭ部４に入力する。
【００９５】
ＭＥＭ部４は、ＣＡＭ部３から入力されたＣＡＭ部３のメモリアドレスと同一値を有するＭＥＭ部４のメモリアドレスに保持されたデータを読み出し、その読み出したデータを検索結果として出力する。
（５−４）制御回路２
図２に示す制御回路２は、ＮＤＰ１０ｃからのヘッダ情報セルに基づいて３種類の検索キーを生成するとともに、３種類の検索キーについての３種類の検索結果をＮＤＰ１０ｃに対して送信するものである。この図２に示す制御回路２は、ＮＤＰ１０ｃからのヘッダ情報セルを入力されると、ＣＡＭ部３に対して検索キーを生成して送信（ＴＸ）し、また、ＣＡＭ部３によって検索結果を書き込まれたヘッダ情報セルを受信（ＲＸ）し、そのヘッダ情報セルを再度ＮＤＰ１０ｃに対して送信するものであって送受信回路として機能しており、この制御回路２は、バッファ部５と、インターフェース回路２ａ，２ｂと、検索キー生成部６と、検索結果処理部７とをそなえて構成されている。
【００９６】
ここで、バッファ部５は、ヘッダ情報セルを保持するものであり、各種のデータを一時的に保持しており、少なくともヘッダ情報セルを保持可能な領域を有する。
また、バッファ部５は、ＩＰｖ６フレームの転送に関する３種類の検索種別を表す検索識別と、３種類の検索種別の各検索結果を表す検索結果と、３種類の検索種別に要する検索情報を表す検索情報と、ＩＰｖ６フレームのヘッダ情報を表すヘッダ情報との各領域を含むヘッダ情報セルを保持する。
【００９７】
なお、バッファ部５は、ヘッダ情報セルのほかに、ＮＤＰ１０ｃから受信したＩＰｖ６フレームを保持するようにもできる。このバッファ部５の詳細については、図１３を参照して後述する。
また、インターフェース回路２ａは、ＮＤＰ１０ｃからのデータの取り込みタイミングを調整する機能を有し、また、好ましくは、パリティチェック機能とバックプレッシャー機能とを有する。インターフェース回路２ｂは、バッファ部５に保持されたデータの出力タイミングを調整してＮＤＰ１０ｃに出力するものであり、また、パリティ付加機能およびバックプレッシャーを受信して出力を停止する機能を有することもできる。
【００９８】
さらに、検索キー生成部６は、バッファ部５に保持されたヘッダ情報セルから抽出した情報に基づいて３種類の検索処理を表す３種類の検索キーを生成するものである。
また、検索結果処理部７は、検索キー生成部６にて生成された３種類の検索キーについての検索結果を含む３種類の連想データに基づいてヘッダ情報セルを生成しヘッダ情報セルをＮＤＰ１０ｃに対して送信するものである。
【００９９】
具体的には、検索結果処理部７は、３種類の連想データをバッファ部５に書き込むことにより、ヘッダ情報セルに検索結果を反映させるようになっており、ＣＡＭ検索システム１からの検索結果データについて検索要否を判定し、各検索結果データを並び替え処理するとともに、上記３種類の検索結果とステータス信号とを、バッファ部５においてヘッダ情報セルとマージする。検索結果処理部７は、処理後の情報データを、検索キー生成部６に対してフィードバックするようにもなっている。
【０１００】
（５−５）検索キーとヘッダ情報セルと検索テーブルとの関係
図２に示すＮＤＰ１０ｃとＣＡＭ検索システム１との間のインターフェースにおいて送受信されるデータはヘッダ情報セルである。また、制御回路２からＣＡＭ部３に送信されるデータは検索キーであり、ＣＡＭ部３からＭＥＭ部４に送信されるデータは検索結果アドレスである。さらに、ＭＥＭ部４から制御回路２へ送信されるデータは、検索結果（連想データ）である。
【０１０１】
検索テーブルは、ＣＡＭ部３およびＭＥＭ部４のそれぞれに予め保持されたデータであって、共通のアドレスを介して対応する。これらは、ＣＡＭ部３およびＭＥＭ部４における３種類の検索処理に必要なデータ（ＣＡＭエントリおよびＭＥＭエントリ）として構成されたものである。
検索キー生成部６は、ヘッダ情報セルに含まれる検索キーを生成するために必要な情報を抽出し、その抽出した情報を検索キーに変換する。この検索キーは、検索テーブルの保持データであるＣＡＭエントリ（ＣＡＭエントリデータ）と比較されることであって検索が実行される。
【０１０２】
（５−６）ＣＡＭ部３，ＭＥＭ部４および検索テーブルの関係
検索テーブルに保持されるデータは、ＣＡＭ部３が保持するデータと、ＭＥＭ部４が保持するデータとが相互に関連付けられた１セットのデータ（データ群）から構成されている。換言すれば、ＣＡＭ部３に入力（登録）するＣＡＭエントリと、ＭＥＭ部４に入力（登録）するＭＥＭエントリ（ＭＥＭエントリデータ）との各データが、この検索テーブルによって、対応付けられて、一括して参照されるようになっている。この検索テーブルを構成するデータフォーマットの各内容（データ定義）と、実際のデータ例とをそれぞれ、図５，図６（ａ）および図６（ｂ）を参照して詳述する。
【０１０３】
（５−６−１）検索テーブル例
図５は本発明の一実施形態に係る検索テーブルを説明するための図である。この図５に示す検索テーブル９は、１回目のＣＡＭエントリ９ａと、１回目のＭＥＭエントリ９ｂと、２回目のＣＡＭエントリ９ｃと、２回目のＭＥＭエントリ９ｄとの４領域を対応付けたものである。また、この検索テーブル９を用いてフィルタ検索についての検索結果を一例として説明する。フロー検索およびトレース検索の検索結果についてもフィルタ検索の検索結果とほぼ同一なので重複した説明を省略する。
【０１０４】
また、以下の説明においては、特に断らない限り、１回目のＣＡＭエントリ９ａを前半データと称し、また、２回目のＣＡＭエントリ９ｃを後半データと称する。
図５に示す１回目のＣＡＭエントリ９ａは、ＣＡＭアレイ３ａに格納され、検索種別，送信先ポート番号，…，送信ＶＩＤ（Ｖｉｒｔｕａｌ  Ｉｄｅｎｔｉｆｉｅｒ：仮想識別子）を、このフォーマットで保持している。これらの「検索種別，送信先ポート番号，…，送信ＶＩＤ」と同一フォーマットが、１回目の検索キーにも適用され、検索時に値を比較される。また、ＭＥＭエントリ９ｂは、ＣＡＭエントリ９ａと同一アドレスのＭＥＭアレイ４ａに格納され、そのデータは、１回目検索結果である連想データである。ＭＥＭエントリ９ｂは、分割された前半データと後半データとを関連付けるポインタとしてのインデックス（Ｉｎｄｅｘ）を保持するものである。
【０１０５】
そして、２回目のＣＡＭエントリ９ｃは、ＣＡＭアレイ３ａに格納され、検索種別、Ｉｎｄｅｘ、送信先ＩＰｖ６アドレス、送信元ＩＰｖ６アドレスをそれぞれ、このフォーマットで保持している。これらの検索種別、Ｉｎｄｅｘ、送信先ＩＰｖ６アドレス、送信元ＩＰｖ６アドレスと同一のフォーマットが２回目の検索キーに適用され、検索時に値が比較される。
【０１０６】
ここで、ＣＡＭエントリ９ｃのインデックスフィールドには、ＭＥＭエントリ９ｂのインデックス値と同一値を登録し、かつ他のエントリとの間でインデックス値の重複が生じないようにし、これにより、前半データと後半データとを１対１に、又は１対多にも対応付け可能である。
１対１の場合、インデックス値は、後半データを指し示すポインタとして動作し、１対多の場合、インデックス値は、前半データ又は後半データのグループを示すグループＩＤとして動作する。
【０１０７】
ＭＥＭエントリ９ｄは、ＣＡＭエントリ９ｃと同一アドレスのＭＥＭアレイ４ａに格納され、その格納されるデータは、２回目の検索結果である連想データである。ＭＥＭエントリ９ｄは、また、フィルタ検索結果として、例えば破棄（ｄｉｓｃａｒｄ）を保持するものである。
そして、１回目のＣＡＭエントリ９ａと２回目のＣＡＭエントリ９ｃとが、ＭＥＭエントリ９ｂのアドレスポインタによって関連付けられ、かつ検索結果がＭＥＭエントリ９ｄとして結合しているのである。
【０１０８】
従って、１回目の検索後の連想データは、最終的な検索結果ではなく、単に中間的なインデックスを保持するのみであり、２回目の検索後の最終的な連想データは、１回目の検索後の連想データのアドレスと異なるアドレスの領域に格納される。そして、検索時においては、１回目の検索結果のインデックス値が、２回目の検索キーのインデックス値として用いられる。なお、対応するＣＡＭエントリも同様に、異なる２種類のデータが異なるアドレスに格納される。
【０１０９】
また、検索テーブル９は、２種類のＣＡＭ部３とＭＥＭ部４との異なるメモリに保持されたデータが、相互に関連付けられたものであり、これらの４領域が１セットとして、フィルタ検索における検索テーブルとして機能しているのである。
（５−６−２）アドレス領域の分割方法の一例
次に、図６（ａ），図６（ｂ）をそれぞれ参照してアドレス領域の分割方法の一例について説明する。
【０１１０】
図６（ａ）は本発明の一実施形態に係るＣＡＭ領域のデータ保持例を説明するための図であり、この図６（ａ）に示すＣＡＭ領域（ＣＡＭ部３のＣＡＭアレイ３ａ）は、アドレス０ｘ００００，０ｘ１０００に、それぞれ、フィルタ１，フィルタ２の各先頭データを保持している。さらに、アドレス０ｘ２０００，０ｘ３０００，０ｘ４０００，０ｘ５０００は、それぞれ、フロー１，フロー２，トレース１，トレース２の各先頭データを保持している。これらのＣＡＭ領域は、検索時において検索される領域である。
【０１１１】
図６（ｂ）は本発明の一実施形態に係るＭＥＭ領域のデータ保持例を保持するための図であり、アドレス領域が分割された場合の一例を示す。この図６（ｂ）に示すＭＥＭ領域（ＭＥＭ部４のＭＥＭアレイ４ａ）は、ＣＡＭ領域と同一のアドレス構成を有し、３種類の検索の連想データ（検索結果）を保持している。具体的には、ＭＥＭ領域の０ｘ００００にフィルタ２へのポインタ（インデックス）が保持され、０ｘ１０００に検索結果「ｄｉｓｃａｒｄ」が保持されている。フロー検索およびトレース検索についても、フィルタ検索と同様であり、０ｘ２０００にフロー２へのインデックスが保持され、０ｘ３０００に検索結果「ｐｒｉｏｒｉｔｙ」の８通りの値のうちのいずれかの値が保持されている。０ｘ４０００にトレース２へのインデックスが保持され、０ｘ５０００に検索結果「ｔｒａｃｅ−ｍｏｄｅ」が保持されている。
【０１１２】
そして、ＭＥＭ部４に入力されるデータ（ＭＥＭエントリ）は、ＭＥＭ部４のＭＥＭアレイ４ａ（ＭＥＭ領域）において、ＣＡＭ部３に入力されるデータ（ＣＡＭエントリ）のメモリ領域（メモリ配列）の割り当てに対応したメモリ領域を割り当てられている。すなわち、ＭＥＭエントリのＭＥＭアレイ４ａにおける展開は、ＣＡＭエントリのＣＡＭアレイ３ａにおける展開と同様である。
【０１１３】
また、定義したＣＡＭアドレスが相互に重複しないように、メモリ領域を分けて定義することもできる。換言すれば、前半のＣＡＭデータに対応するＭＥＭデータを格納するアドレス領域と、後半のＣＡＭデータに対応するＭＥＭデータを格納するアドレス領域とが、重複しないように、予め、定義されているのである。
【０１１４】
このように、１個のＣＡＭ部３を用いて、３種類の検索と、３種類の検索においての前半と後半との計６種類（３×２＝６）を区別できる。
また、ＣＡＭエントリは検索される一方、ＭＥＭエントリは検索されず、これらのＣＡＭエントリおよびＭＥＭエントリは、データの性格（データの特性又はデータの意味）が異なる。従って、両エントリは、同一メモリに保持することができない。
【０１１５】
このため、ＣＡＭ部３の検索動作は、検索キーを、ＣＡＭエントリの参照により検索する。そして、一致データがある場合は、ＣＡＭ部３はその一致データが格納されたアドレスをＭＥＭ部４へ入力する。また、ＭＥＭ部４は、検索テーブルに定義されたデータ（連想データおよびインデックスを含む）を予め書き込まれているので、ＣＡＭ部３からのアドレスによって指定されたアドレスのデータを読み出して検索結果とする。
【０１１６】
（６）ＩＰｖ６ルーティングエンジン１０のフレーム処理と制御回路２との対応
ＩＰｖ６ルーティングエンジン１０のフレーム処理は、４種類（第１フレーム処理，検索処理，ヘッダ処理，第２フレーム処理）の態様を有する。この４種類の処理態様と制御回路２との対応について図８（ａ），図８（ｂ）を参照して説明する。
【０１１７】
図８（ａ）は本発明の一実施形態に係るＣＡＭ検索システム１の検索方法を説明するための図であり、図８（ｂ）は本発明の一実施形態に係る制御回路２を説明するための図である。これらの図８（ａ），図８（ｂ）に示すもののうちの上述したものと同一符号を有するものは、それらと同一のものを表す。
ＮＤＰ１０ｃは、ＩＰｖ６フレームからヘッダ情報を抽出して生成したヘッダ情報セルをＣＡＭ検索システム１に渡す（ＴＸ）。ＣＡＭ検索システム１は、ヘッダ情報セルの書き込み可能な領域に検索結果を書き込む。
【０１１８】
具体的には、ＮＤＰ１０ｃが、ＩＰｖ６フレームをヘッダとペイロードとに分割し、ペイロードを、データを保持するフレームバッファ１０ｅに保持し、ヘッダ情報セルを生成して制御回路２に送信する。
制御回路２は、インターフェース２ａが、ヘッダ情報セルを受信し、バッファ部５に書き込む。そして、検索キー生成部６は、バッファ部５に未だ検索処理されていないヘッダ情報セルの存在を検知すると、必要な情報をバッファ部５から読み出し、この読み出した情報と検索インデックスとに基づいて検索キーを生成しＣＡＭ部３に送信する。
【０１１９】
ＣＡＭ検索システム１は、検索テーブル９を登録するときは、ＣＰＵ１０ａから出力されるＣＡＭエントリ９ａ、ＭＥＭエントリ９ｂ、ＣＡＭエントリ９ｃおよびＭＥＭエントリ９ｄを、それぞれ、書き込み／読み出し部１ａが、ＣＡＭ部３およびＭＥＭ部４に順次書き込むことにより、図５に定義された検索テーブル９をＣＡＭアレイ３ａおよびＭＥＭアレイ４ａに生成する。
【０１２０】
また、ＣＡＭ検索システム１は、ＮＤＰ１０ｃからの検索依頼を受信すると、ＮＤＰ１０ｃからヘッダ情報セルを受信してバッファ部５へ書き込むインターフェース２ａと、ヘッダ情報セルを保持するバッファ部５と、バッファ部５から必要なデータを読み出して必要に応じて検索結果処理部７からインデックスを受信し、検索キーを生成してＣＡＭ部３へ送信する検索キー生成部６と、検索キーをＣＡＭエントリと比較して一致データを検索し、検索結果ステータスを検索結果処理部７へ送信し、検索結果アドレスをＭＥＭ部４に送信するＣＡＭ部３と、受信したアドレスに登録済みのＭＥＭエントリデータを検索結果処理部７に送信するＭＥＭ部４と、ＣＡＭ部３およびＭＥＭ部４から受信した検索結果に基づいて必要に応じてインデックスを検索キー生成部に送信し、前半および後半の検索結果をマージし、また、３種類の検索結果をマージして、そのマージした検索結果データをそのバッファ部５に保持された所定のヘッダ情報セルにマージして書き込む検索結果処理部７と、バッファ部５に検索結果処理済みのヘッダ情報セルの存在を検知してバッファ部５からそのヘッダ情報セルを読み出し、ＮＤＰ１０ｃに送信するインターフェース２ｂとによって構成される。
【０１２１】
次に、図８（ａ）に示すＣＡＭ部３は、フィルタ検索，フロー検索およびトレース検索を行なう。ＣＡＭ部３は、制御回路２からの検索キーに対応する検索対象データを保持している場合は、制御回路２に対して検索対象データが保持されていることを表すメッセージ（Ｈｉｔ  Ｓｔａｔｕｓ）を通知する。また、ＣＡＭ部３は、ＭＥＭ部４に対して検索結果アドレスを送信する。
【０１２２】
ＭＥＭ部４は、ＣＡＭ部３から受信したアドレスに応じて、フィルタ検索のインデックス、フィルタ検索結果（ｄｉｓｃａｒｄ）、フロー検索のインデックス、フロー検索の結果（ｐｒｉｏｒｉｔｙ）、トレース検索のインデックスおよびトレース検索の結果（ｔｒａｃｅ−ｍｏｄｅ）の各データを検索結果処理部７に入力する。
また、検索結果処理部７は、ＣＡＭ部３からフィルタ、フロー、トレースの３種類のそれぞれの前半の検索結果ステータス（Ｈｉｔ  Ｓｔａｔｕｓ）を受信し、ＭＥＭ部４から各検索結果のデータを受信し、フィルタ、フロー、トレースの各検索のインデックスについては、検索キー生成部７に送信し、フィルタ、フロー、トレースの各検索のそれぞれについて前半および後半の検索結果ステータスをマージおよび判定することにより、これら３種類のそれぞれについて最終的な検索結果を得ることができる。
【０１２３】
さらに、３種類の検索結果をさらにマージし、そのマージしたデータをバッファ部５に保持された所定のヘッダ情報セルの所定のビット位置にマージして書き込む。
インターフェース２ｂは、バッファ部５に検索結果処理済みのヘッダ情報セルの存在を検知してバッファ部５からそのヘッダ情報セルを読み出しＮＤＰ１０ｃに送信する。
ＮＤＰ１０ｃは、検索結果を含むヘッダ情報セルを受信（ＲＸ）する。
【０１２４】
これにより、ヘッダ情報セルは、ＮＤＰ１０ｃからＣＡＭ検索システム１に対する検索依頼として機能するとともに、ＣＡＭ検索システム１における検索結果としても機能する。従って、ハードウェアを用いた超高速な検索を行なうことが可能になる。
さらに、外部装置８７（図１参照）からのフレーム（ＩＰｖ４およびＩＰｖ６の各フレーム）がインターフェース部９０にて受信されると、その受信フレームは、本体スイッチ部９１を介してＩＰｖ６ルーティングエンジン１０に入力され（Ｐ１と付された点線部分参照）、ＮＤＰ１０ｃにおいて、フレームのヘッダとペイロードとが分割されてＩＰｖ６アドレスの宛先が解決される。そして、ＩＰｖ６ルーティングエンジン１０のＮＤＰ１０ｃからＣＡＭ検索システム１にヘッダ情報セルが入力され（Ｐ３と付された点線部分参照）、ＣＡＭ検索システム１にてそのヘッダ情報セルに対応するフィルタ検索、フロー検索およびトレース検索される。そして、検索処理を含むヘッダ情報セルが、ＣＡＭ検索システム１からＮＤＰ１０ｃに対して送信される（Ｐ３と付された点線部分参照）。
【０１２５】
従って、ＮＤＰ１０ｃは、ＩＰｖ６ルーティングエンジン１０によって支援される。
一方、ＣＡＭ検索システム１にて検索されて得られたｄｉｓｃａｒｄ、ｐｒｉｏｒｉｔｙおよびｔｒａｃｅ−ｍｏｄｅに基づいて各処理が終了し、また、ＩＰｖ６アドレスの宛先解決処理によって、転送先ポートを書き込まれたヘッダを有するＩＰｖ６フレームが生成され、生成されたＩＰｖ６フレームは、転送先ポートのある経路方向に転送され、インターフェース部９０から、外部装置８７に対して送信される（Ｐ２と付された点線部分参照）。
【０１２６】
このように、ルータ８は、外部装置８７とから入力されたフレームの転送先アドレス解決と、フィルタ、フローおよびトレースの各処理と、転送先となる外部装置８７に対するフレーム送信が可能となる。
（７）ＩＰｖ６ルーティングエンジン１０の処理
次に、図９（ａ）および図９（ｂ）を参照してＩＰｖ６ルーティングエンジン１０におけるフレーム処理について説明する。ここで、フレーム処理のステップは、第１フレーム処理，検索処理，ヘッダ処理および第２フレーム処理の４ステップがある。
【０１２７】
図９（ａ）は本発明の一実施形態に係るフレーム処理の流れを説明するためのフローチャートであり、図９（ｂ）は本発明の一実施形態に係る検索処理の流れを模式的に示す図である。
（７−１）第１フレーム処理（ステップＳＯ１）
ＮＤＰ１０ｃは、インターフェース部９０のポートから第３スイッチ部１０ｂを介して、検索前のフレーム８０（図９（ｂ）参照）を入力されると、フレーム８０のヘッダ８０ａを抽出する（ＳＯ１−１）。
【０１２８】
また、ＮＤＰ１０ｃは、フレーム８０のペイロード８０ｂをフレームバッファ１０ｅに待避させる（ＳＯ１−２）。次に、ＮＤＰ１０ｃは、ＳＯ１−１にて抽出したヘッダ８０ａに、フレーム８０と１対１に対応しルータ８の内部の各種情報を含む装置内部情報８１ａを付加し、ヘッダ８０ａおよび装置内部情報８１ａを有するヘッダ情報セル８１を生成する（ＳＯ１−３）。
【０１２９】
（７−２）検索処理（ステップＳＯ２）
この検索処理の種類は、ＩＰｖ６アドレス等に基づいて送信先ポートを決定するＩＰｖ６アドレス解決検索と、廃棄フレームを決定するフィルタ検索と、フレームの優先度（ｐｒｉｏｒｉｔｙ）を決定するフロー検索と、トレース対象フレームを決定するトレース検索等がある。
【０１３０】
ＩＰｖ６アドレス解決検索は、ＮＤＰ１０ｃ内部のＩＰｖ６アドレス解決検索部９１ｅに対して、ヘッダ情報セル８１を送信し、検索結果をヘッダ情報セル８１に反映させる。
次に、フィルタリング、フローおよびトレースの各検索については、ヘッダ情報セル８１をＣＡＭ検索システム１に送信し、各検索結果をヘッダ情報セル８１に反映させ、さらに、ＮＤＰ１０ｃに返却させる。
【０１３１】
さらに、他の検索は、他の検索結果をヘッダ情報セル８１に反映させて返却させることにより、処理できる。
これにより、すべての検索結果が反映されたヘッダ情報セル８１を得られる（ＳＯ２）。
（７−３）ヘッダ処理（ステップＳＯ３）
ステップＳＯ３のヘッダ処理は、ＮＤＰ１０ｃが、全ての検索結果が反映された出力先ポートを指定し、必要に応じてヘッダ情報を書き替え、廃棄対象フレームは廃棄し、ｐｒｉｏｒｉｔｙ値の優先度に応じてフレーム出力順序を指定し、トレース対象フレームは、トレース処理のために、ＣＰＵ１０ａに対して通知、その他のヘッダ処理を行なうヘッダ処理ステップである（ＳＯ３−１）。
【０１３２】
これにより、ルーティングエンジンに入力されたＩＰｖ６フレームの出力ポートの決定と、廃棄処理と、優先制御と、トレース機能と、その他の機能が実現される。
（７−４）第２フレーム処理（ステップＳＯ４）
ステップＳＯ４の第２フレーム処理は、各処理を終了したヘッダを元のペイロードに挿入し、出力フレームを生成する処理である。
【０１３３】
ＮＤＰ１０ｃは、各検索処理およびヘッダ処理を終了したヘッダ情報セル８１（装置内部情報８１ｂ＋ヘッダ８２ａ）から出力フレームのためのヘッダ８２ａを抽出し、また、フレームバッファ１０ｅから対応するペイロード８０ｂを読み出し、これらのヘッダ８２ａおよびペイロード８０ｂをマージして出力フレーム８２を再生する。この出力フレーム８２は、出力ポートから外部装置８７に対して送信される。
【０１３４】
ＳＯ２における３種類の検索について詳述する。ＮＤＰ１０ｃは、検索前のヘッダ情報セル８１（装置内部情報８１ａ＋ヘッダ８０ａ）をＣＡＭ検索システム１に送信する。ＣＡＭ検索システム１において、受信したヘッダ情報セルから必要な情報が抽出され、そして、３種類の検索キーが生成され、生成した３個の検索キーがＣＡＭ部３へ送信される。ＣＡＭ部３は各検索キーを用いてフィルタ検索，フロー検索およびトレース検索を処理し、アドレスをＭＥＭ部４に入力し、ＭＥＭ部４は、３種類の検索結果をマージし、ヘッダ情報セルに含めるデータを、バッファ部５に書き込む。さらに、インターフェース部２ｂは、バッファ部５より、３種類の検索が終了したヘッダ情報セル８１（装置内部情報８１ｂ＋ヘッダ８２ａ）を読み出し、読み出したヘッダ情報セル８１をＮＤＰ１０ｃに対して送信する。
【０１３５】
このように、ＮＤＰ１０ｃはヘッダ情報セルをＣＡＭ検索システム１に対して１回入力すると、ＣＡＭ検索システム１が自動的に３回検索し、３種類の検索結果をマージする。従って、ＮＤＰ１０ｃは、検索キーの生成処理が不要となり、さらに、１回の検索依頼によって、３種類の検索依頼が可能となる。
また、ＮＤＰ１０ｃは、ＣＡＭ検索システム１から受信したヘッダ情報セルから検索結果を取得できる。さらに、受信したヘッダ情報セルに含まれる他の情報も参照することができる。
【０１３６】
（８）制御回路２
図１０は本発明の一実施形態に係る制御回路２の概略的なブロック図である。
（８−１）検索キー生成部６
この図１０に示す検索キー生成部６は、検索キーを生成するものであって、並び替え処理部６ａと、検索種別コード生成部６ｄと、第１セレクタ６ｅとをそなえて構成されている。
【０１３７】
検索キー生成部６は、バッファ部５に保持されたデータを変換して検索キーを生成し、その検索キーについての検索種別コードを生成し、検索キーと検索種別コードとのペアデータを所望のタイミングでＣＡＭ検索システム１に入力するものであって、検索種別コード生成部６ｄおよび並び替え処理部６ｂと、２面バッファ（他面バッファ）６ｃとをそなえて構成されている。また、並び替え処理部６ａは、バッファ部５に保持されたヘッダ情報セルに含まれる３種類の検索処理の検索順序を制御するバッファ制御部として構成されている。
【０１３８】
この検索キー生成および並び替え処理部６ｂは、バッファ部５からのデータ読み出しと、その読み出しデータをフォーマット変換して得られる検索キーの生成とを行なうものである。
また、２面バッファ６ｃは、２毎（２ページ）のバッファ領域１，２（ＢＵＦＦ１，２）からなり、これらのバッファ領域１，２が、それぞれ、バッファ部５からの検索キーを交互に保持する。なお、バッファ数は３面以上でもよい。
【０１３９】
検索種別コード生成部６ｄは、２面バッファ６ｃに保持された検索キーのそれぞれに対応した検索種別コードを生成するものである。この検索種別コードの表現例は、４ビットのコード（００００〜１１１１）である。例えば、００００，０００１はフィルタ検索の１回目，２回目をそれぞれ表し、００１０，００１１はフロー検索の１回目，２回目をそれぞれ表し、そして、０１００，０１０１は、トレース検索の１回目，２回目をそれぞれ表す。これら以外の４ビットコードは上記３種類の検索処理と異なる検索処理のために予約されている。なお、この表現方法は設計方針等に基づいて種々の表現方法を用いることができる。
【０１４０】
第１セレクタ６ｅは、検索キー生成および並び替え処理部６ｂからの検索キーと、検索種別コード生成部６ｄからの検索種別コードと、検索結果処理部７からのインデックスとを入力され、検索種別コードを付加された検索キーを出力するものである。このインデックスとは、前半のＣＡＭデータと後半のＣＡＭデータとを対応付けるための情報データである。
【０１４１】
これにより、バッファ部５には、ＮＤＰ１０ｃから受信したヘッダ情報セルがインターフェース部２ａによって書き込まれて保持され、検索キー生成のために、検索キー生成部６から必要な部分が読み出され、検索結果の反映のために、検索結果処理部７の所定の部分に書き込まれ、検索処理後のヘッダ情報セルをＮＤＰ１０ｃに対して送信するためにインターフェース部２ｂにより読み出される。ヘッダ情報セルは、ＮＤＰ１０ｃから順次受信され、書き込まれ、順次、読み出し、ＮＤＰ１０ｃに送信する。
【０１４２】
従って、バッファ部５に保持されたデータの保持された順番は変更されず、先入れ先出し処理の動作と同一動作となる。
（８−２）検索結果処理部７
検索結果処理部７は、ＣＡＭ検索システム１からの検索結果の要否を判定し各検索結果データを並び替え処理するものであって、第１レジスタ７ａ，第２レジスタ７ｂ，判定および並び替え処理部７ｃ，第２セレクタ７ｄをそなえて構成されている。
【０１４３】
ここで、第１レジスタ７ａ，第２レジスタ７ｂは、それぞれ、ＣＡＭ部３およびＭＥＭ部４からの検索結果データを保持するものであって、例えばＬＳＩ内の記憶素子である。
検索結果処理部７は、バッファ部５に保持されたヘッダ情報セルに含まれる３種類の検索結果を保持する部分に、検索結果を書き込む書き込み制御を行なうバッファ書き込み制御部として機能している。判定および並べ替え処理部７ｃは、３種類の検索結果をヘッダ情報セルのフォーマットに並べ替えてセレクタ７ｄを介してバッファ部５に書き込む。そして、この判定および並べ替え処理部７ｃにおけるステータス判定からこの並べ替え処理を経てバッファ部５に書き込む処理までが検索結果のマージに相当する。
【０１４４】
さらに、第１レジスタ７ａ，第２レジスタ７ｂのそれぞれからのデータが有効か無効かを判定し、また、ＣＡＭ部３からの３種類の検索結果を一旦保持して各保持データをマージし、ヘッダ情報セルの所定領域に書き込むものである。判定および並び替え処理部７ｃは、ＣＡＭ部３からのフィルタ検索の検索結果が一致（ヒット）又は不一致（ミスヒット）を判定し一致の場合は、そのときのＭＥＭデータを保持する一方、不一致の場合はそのときのＭＥＭデータを破棄しかつ保持している検索結果をデフォルト（初期値）にする。
【０１４５】
加えて、判定および並び替え処理部７ｃは、第２セレクタ７ｄを経て、３種類の検索結果をバッファ部５に保持された所定のヘッダ情報セルに書き込みしてマージする。これにより、データのマージ機能が実現される。
第２セレクタ７ｄは、判定および並び替え処理部７ｃからのデータを選択して出力するものである。
【０１４６】
（８−３）制御回路２における２度引きの処理
（８−３−１）制御回路２が検索処理を開始するときには、予め図５に示す検索テーブル９がＣＡＭ部３およびＭＥＭ部４に登録済みである必要がある。この検索テーブル９を形成するＣＡＭエントリ９ａ、９ｃおよびＭＥＭエントリ９ｂ、９ｄは、ＣＰＵ１０ａにより、書き込み／読み出し１ａを介してＣＡＭ部３およびＭＥＭ部４に書き込まれる。
【０１４７】
フィルタ、フローおよびトレース検索のための各検索テーブルの内容は、ＣＰＵ１０ａのソフトウェアプログラムにより作成される。このプログラムは、フィルタ検索テーブル生成部、フロー検索テーブル生成部およびトレース検索テーブル生成部をもって構成される。
次に、ＣＰＵ１０ａのプログラムが生成する検索テーブルについてさらに詳述する。
【０１４８】
本発明のルーティングエンジン１０におけるメモリ検索にあたり、まず、データを登録する。ＣＰＵ１０ａは、ＣＡＭ部３のメモリ領域を割り当てるとともにこのＣＡＭ部３のメモリ領域のメモリアドレスと同一のメモリアドレスを有するＭＥＭ部４のメモリ領域を割り当てる（メモリ領域割り当てステップ）。
（８−３−１−１）ＣＰＵ１０ａは、フィルタ検索のＣＡＭエントリの前半データであるＣＡＭエントリ９ａを、書き込み／読み出し部１ａ経由で、ＣＡＭアレイ３ａのアドレス０ｘ００００から始まるフィルタ１（フィルタ前半）のＣＡＭ領域に書き込む（図６（ａ）参照）。
【０１４９】
（８−３−１−２）ＣＰＵ１０ａは、フィルタ検索の前半データに対応する検索結果データであり、フィルタ検索の後半データを示すポインタでもあるインデックス（ＭＥＭエントリ９ｂ）を書き込み／読み出し部１ａを経由で、ＭＥＭアレイ４ａのアドレス０ｘ００００から始まるフィルタ１（フィルタ２へのインデックス）のＭＥＭ領域のうちのＣＡＭエントリ９ａと同一アドレスに書き込む（図６（ｂ）参照）。
【０１５０】
（８−３−１−３）ＣＰＵ１０ａは、フィルタ検索の後半データであるＣＡＭエントリ９ｃを、書き込み／読み出し部１ａを経由でＣＡＭアレイ３ａのアドレス０ｘ１０００から始まるフィルタ２（フィルタ後半）のＣＡＭ領域に書き込む（図６（ａ）参照）。このときのＣＡＭエントリ９ｃのインデックスフィールド値は、ＭＥＭエントリ９ｂのインデックスフィールド値と同一値を用いる。
【０１５１】
（８−３−１−４）ＣＰＵ１０ａは、フィルタ検索の後半データに対応する検索結果データであり、フィルタ検索の最終検索結果でもある（ｄｉｓｃａｒｄ＝ＭＥＭエントリ９ｄ）を書き込み／読み出し部１ａ経由でＭＥＭアレイ４ａのアドレス０ｘ１０００から始まるフィルタ２（フィルタの連想データ、すなわち、ｄｉｓｃａｒｄ）のＭＥＭ領域に、ＣＡＭエントリ９ｃと同一アドレスに書き込む（図６（ｂ）参照）。
【０１５２】
以上の（８−３−１−１），（８−３−１−２），（８−３−１−３），（８−３−１−４）の４通りの書き込み処理により、図５に示すフィルタ検索の検索テーブルの１個を、ＣＡＭ部３およびＭＥＭ部４に設ける。そして、この処理を登録すべきフィルタ検索の検索テーブルの個数分だけ繰り返す。また、フロー検索の検索テーブルおよびトレース検索の検索テーブルについても同様である。
【０１５３】
（８−３−２）制御回路２による２度引き検索について詳述する。
２度引き検索は、制御回路２の検索キー生成部６が検索結果処理部７と協働しＣＡＭ部３およびＭＥＭ部４を制御することにより行なう。フィルタ検索は、次の手順で行なわれる。
ステップ１  並び替え
検索キー生成および並び替え処理部６ｂがバッファ部５のヘッダ情報セルから必要なデータを読み出し、並び替えて、バッファ１に前半データと後半データとを保持する。
【０１５４】
ステップ２  １回目の検索キー生成
検索種別コード生成部が、フィルタ１の検索種別コードを生成し、バッファ１が前半データを出力し、第１セレクタ６ｅがこれらを選択統合してフィルタ検索の１回目の検索キーを生成し、ＣＡＭ部３に送信する。
ステップ３  ＣＡＭ検索１回目
ＣＡＭ部３は、受信した検索キーをＣＡＭ部３自身が保持するＣＡＭエントリと比較し、一致したＣＡＭエントリのアドレスを出力する。ここで、検索キーは、フィルタ１の検索種別コードを含むので、図６（ａ）のアドレス０ｘ００００から始まるフィルタ１のＣＡＭ領域に登録されたＣＡＭエントリにしか一致しないはずである。
【０１５５】
従って、ヒット時に出力するアドレスは、０ｘ００００以上０ｘ１０００未満のアドレスである。また、ヒットステータスを検索結果処理部７に送信する。
ステップ４  ＭＥＭ読み出し
ＭＥＭ部４は、ＣＡＭ部３から受信したアドレスに登録されたＭＥＭエントリを読み出し、検索結果処理部７に送信する。ここで、このＭＥＭエントリは、フィルタ１の検索結果であり、フィルタ２へのインデックスでもある。
【０１５６】
ステップ５  ２回目検索キー生成
検索種別コード生成部がフィルタ２の検索種別コードを生成し、検索結果処理部のレジスタ７ａは、フィルタ２へのインデックスを第１セレクタ６ｅに送信し、バッファ１が後半データを出力し、第１セレクタ６ｅがこれらを選択統合してフィルタ検索の２回目検索キーを生成し、ＣＡＭ部３に送信する。
【０１５７】
ステップ６  ＣＡＭ検索２回目
ＣＡＭ部３は、受信した検索キーをＣＡＭ部３自身が保持しているＣＡＭエントリと比較し、一致したＣＡＭエントリのアドレスを出力する。この検索キーは、フィルタ２の検索種別コードを有するので、図６（ａ）のアドレス０ｘ１０００から始まるフィルタ２のＣＡＭ領域に登録されたＣＡＭエントリにしか一致しないはずである。従って、ヒット時に出力するアドレスは、０ｘ１０００以上０ｘ３０００未満のアドレスである。また、ヒットステータスを検索結果処理部７に送信する。
【０１５８】
ステップ７  ＭＥＭ読み出し２
ＭＥＭ部４は、ＣＡＭ部３から受信したアドレスに登録されたＭＥＭエントリを読み出し、検索結果処理部７に送信する。ここで、このＭＥＭエントリは、フィルタ２の検索結果であり、フィルタ検索の検索結果のｄｉｓｃａｒｄ値である。
ステップ８
検索結果処理部７は、ステップ３にて得られたフィルタ１（フィルタ前半）検索結果のヒットステータスと、ステップ６にて得られたフィルタ２（フィルタ後半）の検索結果のヒットステータスとをレジスタ７ｂに保持している。
【０１５９】
これにより、前半および後半を併せて最終的なフィルタ検索のヒットステータスを判定する。判定基準は、「両方ともヒット（マルチヒットをも含む）時のみ、ヒットを判定する。」である。
そして、ヒットと判定されると、ステップ７にて得られたｄｉｓｃａｒｄ値を、前半後半併せた最終的なフィルタ検索結果のｄｉｓｃａｒｄ値とする
ステップ８のここまでの検索結果のマージが、判定と並び替え７ｃにおいて行なわれ、セレクタ７ｄがこのｄｉｓｃａｒｄ値を選択してバッファ部５の所定のヘッダ情報セルの所定のビット位置へ書き込むことによりマージする。
【０１６０】
このように、フィルタ検索は、前半と後半との２回に分けられており、制御回路２は、１回目の検索時に検索キーの前半を検索し、その検索結果としてインデックスを得る。そして、制御回路２は、２回目の検索時にインデックスを検索キーに加えて検索し、その検索結果である連想データを得る。
また、このように、制御回路２は、２回の検索により、ＣＡＭ部３のビット幅を超える長さのビット幅を有する検索キーを用いて検索できる。さらに、フロー検索およびトレース検索については、検索テーブル１，２と異なる他の領域テーブルに検索テーブルを書き込むための領域が設けられフィルタ検索の場合と同一の検索処理が行なわれる。
【０１６１】
なお、メモリ領域の割り当ては、２回以上の多数回数の検索が可能である。
（８−４）ＣＡＭデータとＭＥＭデータとのデータ例
図１１（ａ），図１１（ｂ）はそれぞれ本発明の一実施形態に係るＣＡＭ部３とＭＥＭ部４との各データ例を示す図である。この図１１（ａ）に示すデータは、ＣＡＭ部３に保持されたＣＡＭエントリと、このＣＡＭエントリが保持されるＣＡＭアドレスとを示し、また、図１１（ｂ）に示すデータは、ＭＥＭ部４に保持されたＭＥＭエントリと、このＭＥＭエントリが保持されるＭＥＭアドレスとを示している。
【０１６２】
ここで、ＣＡＭ部３のＣＡＭアドレス０ｘ００００に、フィルタ１のＣＡＭエントリが保持され、また、ＭＥＭ部４のＭＥＭアドレス０ｘ００００に、フィルタ１のＭＥＭエントリが保持されている。そして、これらのＣＡＭエントリとＭＥＭエントリとの１組が、フィルタ１の検索テーブルを構成している。
同様に、ＣＡＭ部３のＣＡＭアドレス０ｘ００１０に、フィルタ２のＣＡＭエントリが書き込まれ、また、ＭＥＭアドレス０ｘ００１０に、フィルタ２のＭＥＭエントリが書き込まれており、これらのＣＡＭエントリとＭＥＭエントリとのセットが、フィルタ２の検索テーブルを構成している。
【０１６３】
また、ＣＡＭエントリ値「０ｘ１００１０ＡＡＡＡ．．．．．．ＡＡＡＡＢＢＢＢ．．．．．．ＢＢＢＢ０００」と、ＭＥＭエントリ値０ｘ１０００００００とが同一アドレス（０ｘ００１０，０ｘ００１０）に割り当てられる。さらに、ＣＡＭエントリ値「０ｘ０１１１１２２２２３３３３３４４５５６６６７７７００００．．．．００００」と、ＭＥＭエントリ０ｘ００１０００００とが同一アドレス（０ｘ００００，０ｘ００００）に割り当てられ、これにより、別個の異なるＣＡＭ部３とＭＥＭ部４とが同一アドレスの付与によって関連付けられている。すなわち、アドレス０ｘ００１０のＣＡＭエントリとＭＥＭエントリとの組が、フィルタ１の検索テーブルであり、また、アドレス０ｘ００１０のＣＡＭエントリとＭＥＭエントリとの組が、フィルタ２の検索テーブルである。
【０１６４】
そして、インデックス０ｘ００１０によって、アドレス０ｘ００００のフィルタ１の検索テーブルと、アドレス０ｘ００１０のフィルタ２の検索テーブルとが関連付けられて１組となっている。この関連付けられた「１組」は、１種類のフィルタ検索を定義（設定）するものであり、また、設定を要するフィルタの個数ｎ（ｎは自然数を表す。）に相当する個数のフィルタを設けるためには、「ｎ組」のフィルタ検索テーブルを設定する。
【０１６５】
なお、検索テーブルの各領域値について、特に、ＣＡＭアドレス０ｘ００００のＣＡＭエントリ値「０ｘ０１１１１２２２２３３３３３４４５５６６６７７７００００．．．．００００」の２８８ビットについて詳述する。
ＣＡＭエントリの先頭値０は検索種別を表しフィルタ１の検索テーブルのＣＡＭエントリであることを表す。１１１１は送信先ポート番号０ｘ１１１１であり、２２２２は送信元ポート番号０ｘ２２２２である。また、３３３３３，４４，５５，６６６，７７７は、各々定義された領域値である。さらに、１８４ビットの「００００．．．．００」は未使用部分として全て”０”が書き込まれている。ＣＡＭエントリ値の最後尾の”００”はパリティビットである。
【０１６６】
一方、ＭＥＭアドレス０ｘ００００のＭＥＭエントリ値「０ｘ００１０００００」の最初の００１０はインデックス値０ｘ００１０であり、００００は未使用部分であり全て”０”としている。そして、このＭＥＭエントリのアドレスは０ｘ００００であり、この０ｘ００００によってＣＡＭエントリと関連付けられており、従って、このＭＥＭエントリの検索種別がフィルタ１の検索テーブルを表す。
【０１６７】
次に、下段にあるＣＡＭアドレス０ｘ００１０には、ＣＡＭエントリ値「０ｘ１００１０ＡＡＡＡ．．．．．．ＡＡＡＡＢＢＢＢ．．．．．．ＢＢＢＢ０００」が書き込まれている。ここで、先頭値１は検索種別がフィルタ２の検索テーブル３０ｃのＣＡＭエントリであることを表す。００１０はインデックス値０ｘ００１０のＣＡＭエントリを表す。「ＡＡＡＡ．．．．．．ＡＡＡＡ」は送信先ＩＰｖ６アドレス（１２８ビット）であり、「ＢＢＢＢ．．．．．．ＢＢＢＢ」は送信元ＩＰｖ６アドレス（１２８ビット）である。０は未使用部分を表し、最後尾の００はパリティビットである。
【０１６８】
一方、ＭＥＭアドレス０ｘ００１０のＭＥＭエントリ値「０ｘ１０００００００」の最初の１はｄｉｓｃａｒｄビットを表し廃棄対象であることを表す。０００００００は未使用部分であり全て”０”である。さらに、このＭＥＭエントリはアドレス０ｘ００１０によってＣＡＭエントリと関連付けられているので、検索種別はフィルタ２の検索テーブルのＭＥＭエントリであることが識別される。
【０１６９】
また、フロー検索およびトレース検索の各検索テーブルも、フィルタ検索の検索テーブルと同様なので、重複した説明を省略する。
これにより、ＣＡＭ検索システム１は、１個のＣＡＭ部３の１つの連続したメモリ領域（ＣＡＭデータを保持する連続領域）に３種類の検索テーブルを設けるとともに、３種類の検索テーブルおよび検索キーに検索処理を識別する検索種別コードを検索対象として格納する。
【０１７０】
これにより、３種類の検索テーブルが登録され、また、ＣＡＭデータに検索種別コードが格納され、検索種別コードを含む検索キーによる検索は、検索種別が異なるＣＡＭエントリと一致しないので、１個のＣＡＭ部３で３種類の検索ができる。
また、従って、ＣＡＭ部３のメモリ領域の全体について検索が行なわれた場合においても、検索種別コードが異なるＣＡＭデータは検索されず、ヒットしないことが保証されるので、検索されない場合と等価であり、ＣＡＭ部３は独立したＣＡＭ検索システム１として動作できる。
【０１７１】
（９）制御回路２のバッファ部５のバッファリング処理
次に、制御回路２に設けられたバッファ部５におけるデータの書き込みおよび読み出しについてそれぞれ説明する。
従来のバッファは、１本の入力ポートと１本の出力ポートとを有し、これらの２本の入出力ポートの全てがデータの送受信のために閉塞している。このため、従来のバッファは、常時、連続的にアクセスされ、２種類のデータの読み出しと２種類のデータの書き込みとを連続的に同時にすることはできない。
【０１７２】
本発明の制御回路２に設けられたバッファ部５は、４本の入出力ポートを有する点と、６個（６段）のリングバッファからなる点とを有し、これらの２点についてそれぞれ図１３〜図１５（ａ），図１５（ｂ）を参照して説明する。
図１３は本発明の一実施形態に係るバッファ部５の４本の入出力ポートを説明するための図である。この図１３に示すもので上述したものと同一符号を有するものは、それらと同一のもの又は同一機能を有するものである。
【０１７３】
図１３に示すバッファ部５は、ヘッダ情報セルを一時的に保持するものであって、６個のデュアルポートメモリが用いられている。この図１３に示すバッファ部５は、ＮＤＰ１０ｃ側のポート（以下、Ａポートと称する。）の読み出し線および書き込み線を設け、また、検索キー生成部６および検索結果処理部７側のポート（以下、Ｂポートと称する。）の書き込みおよび読み出し線を設けており、これにより、ＮＤＰ１０ｃと検索結果処理部６および検索結果処理部７とがともにアクセス（書き込みおよび読み出し）可能になっている。そして、バッファ部５の動作は、２回書き込み、２回読み出しするようになっている。なお、ＤＰＲＡＭ（Ｄｕａｌ  Ｐｏｒｔ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と区別するために、ＱＰＲＡＭ（Ｑｕａｄ  Ｐｏｒｔ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と表記する。
【０１７４】
さらに、バッファ部５について詳述する。
図１４は本発明の一実施形態に係るバッファ部５のブロック図であり、この図１４に示すもので、上述した符号と同一符号を有するものはそれらと同一のものである。
ここで、バッファ部５は、６個のデュアルポートメモリ（ＤＰＲＡＭ）＃１〜＃６と、Ａポートの書き込み線および読み出し線と、Ｂポートの書き込み線および読み出し線と、入出力側にそれぞれ設けられた２個のバススイッチ部（第２メモリ選択部）１５ａと、入出力側にそれぞれ設けられた２個のセレクタ（第１メモリ選択部）１５ｂとをそなえて構成されている。
【０１７５】
２個のセレクタ１５ａは、いずれも、各バスラインに書き込み制御信号を出力することにより、デュアルポートメモリ＃１〜＃６のうちの書き込み対象のデュアルポートメモリ＃１にデータを書き込むものである。
２個のバススイッチ部１５ｂは、各バスラインに読み出し制御信号を出力することにより、複数のデュアルポートメモリのうちの読み出し対象のデュアルポートメモリからデータを読み出すものである。
【０１７６】
このバススイッチ部１５ａは、データの送信先を切り替えるためのものであって、各デュアルポートメモリ＃１〜＃６の書き込み可能信号（書き込みイネーブル信号：ＷＥ［Ｗｒｉｔｅ  Ｅｎａｂｌｅ］）に接続されたデータバスに制御信号を出力し、デュアルポートメモリ＃１〜＃６のうちの特定の一個の書き込み可能になっている。
【０１７７】
例えば、バススイッチ部１５ａは、例えばデュアルポートメモリ＃１にデータを書き込む場合、デュアルポートメモリ＃１の書き込みイネーブル信号ＷＥをオンにするとともに他のデュアルポートメモリ＃２〜＃６の書き込みイネーブル信号ＷＥをオフにする。
これにより、ＮＤＰ１０ｃは、６個のデュアルポートメモリ＃１〜＃６のうちの＃１〜＃６個までの所望のメモリを選択でき、従って、データの送信先の切り替え制御が可能になる。
【０１７８】
また、セレクタ１５ｂは、複数の入力データのうちの通過させるデータを選択して切り替えるものである。ポートＢ（出力）側のデータバスに接続されたデュアルポートメモリ＃１〜＃６からのデータと、これらのデュアルポートメモリ＃１〜＃６を識別する情報データとが含まれ、これにより、所望のデータ取得先を切り替えるのである。
【０１７９】
なお、バススイッチ部１５ａおよびセレクタ１５ｂの各機能は、いずれも、セレクタ素子等によって発揮される。また、図１４に示すもので、上述したものと同一符号を有するものは、それらと同一のものを表す。
次に、デュアルポートメモリ＃１〜＃６は、いずれも、Ｆ（Ｆｕｌｌ）フラグ，Ｓ（Ｓｅａｒｃｈ）フラグおよびＲ（Ｒｅａｄｙ）フラグとの３種類のフラグを有する。
【０１８０】
ここで、Ｆフラグはセルデータを保持していることを表し、このフラグがオンのときは新規なセルデータを書き込みできないことを表す。ＳフラグはＣＡＭ検索システム１が検索している最中および読み出ししている最中であることを表す。ＲフラグはＣＡＭ検索システム１が検索終了および読み出ししている最中であることを表す。これらの３種類のフラグは、いずれも、読み出しが終了するとオフになって再度書き込み可能となる。
【０１８１】
さらに、バッファ部５は、６個のデュアルポートメモリ＃１〜＃６をそなえ、６個のリングバッファとして構成されている。
図１５（ａ），図１５（ｂ）はそれぞれ本発明の一実施形態に係るバッファ部５のリングバッファ構成を説明するための図であり、いずれも、６個のＤＰＲＡＭ＃１〜＃６バッファが巡回的（リング状）に接続されていることを模式的に表示している。
【０１８２】
この図１５（ａ）又は図１５（ｂ）に示すバッファ部５は、例えば６個又は８個の巡回的に接続されたデュアルポートメモリバッファ＃１〜＃６を有し、これにより、バススイッチ１５ａ等は、デュアルポートメモリ＃１〜＃６にデータを順番に書き込みし、また、順番にデータを各デュアルポートメモリ＃１〜＃６から読み出しする。
【０１８３】
ここで、各デュアルポートメモリ＃１〜＃６は、ＡポートとＢポートとの２本の書き込みおよび読み出し可能なポートを有し、一方のポート（Ａポート又はＢポート）から書き込みするのと同時に他方のポート（Ｂポート又はＡポート）から読み出しできるようになっている。そして、書き込み方法は、バススイッチ１５ａがデータをバッファ１に書き込み、次のデータをバッファ２に書き込み、順次、次のバッファに書き込み、バッファ６の次は、バッファ１に書き込む。すなわち、巡回されて書き込まれる。
【０１８４】
バススイッチ１５ａは、データを書き込むデュアルポートメモリ＃１〜＃６を、各デュアルポートメモリ＃１〜＃６に付与されたＩＤ（Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ：識別子）に基づいて巡回的に選択しているのである。
なお、デュアルポートメモリ＃ｉ（ｉは２以上の自然数を表す。）の個数ｉは、種々変更して実施可能である。
【０１８５】
また、各デュアルポートメモリ＃１〜＃６は、それぞれ、データを保持していることを示すフルフラグ（Ｆｕｌｌ  Ｆｌａｇ）を出力可能になっている。そして、Ａポート側のバススイッチ１５ａは、バッファ１にデータ（ヘッダ情報セル）を書き込みし、フラグをオンにする（フラグを立てる）。また、Ａポート側のバススイッチ１５ａは、順次、次のバッファに次のヘッダ情報セルを書き込みしフラグをオンにする。なお、フラグがオンになっているバッファｋ（ｋは１〜６の自然数を表す。）は、データを書き込まれず、Ａポート側のバススイッチ１５ａは、フラグがオフになるまで待つ。
【０１８６】
一方、Ａポート側のセレクタ１５ｂは、バッファ１のヘッダ情報セルを読み出し、Ｆ、Ｓ、Ｒの各フラグをオフにする（フラグを倒す）。なお、各フラグがオフのバッファｋは、読み出されず、Ａポート側のセレクタ１５ｂは、そのバッファｋの各フラグがオンになるまでウェイトする。
これにより、各フラグの状態を監視することにより、Ａポート側のバススイッチ１５ａがデータを書き込み可能か否かをモニタすることができる。また、Ａポート側のセレクタ１５ｂは、読み出し可能か否かをモニタすることができる。
【０１８７】
以下、４個の各入出力ポートの入出力と、ステータス信号（ステータスフラグ）との関係についてＤＰＲＡＭ１を例にして図１５，図１６（ａ）〜図１６（ｅ）をそれぞれ参照して説明する。ＤＰＲＡＭ２〜６についてもＤＰＲＡＭ１と同様である。
図１６（ａ）〜図１６（ｅ）はそれぞれ本発明の一実施形態に係るＤＰＲＡＭ１のステータスフラグを説明するためのタイムチャートである。なお、図１６（ａ）に示すＤＰＲＡＭ１のＡポートと、図１６（ｂ）に示すＤＰＲＡＭ１のＢポートとの各処理は、いずれも、後述する図１７に示すポート００５と００６とに対応している。また、Ｆ０１〜Ｆ２５を付された部分は、図１７に示す処理に対応する。
【０１８８】
ＤＰＲＡＭ１のＡポートは、時刻Ｔ００においてセルＡと表示されたデータ（入力されたヘッダ情報セル）の書き込みを開始する。時刻Ｔ００における３種類のステータスフラグは図１４に示す論理Ｌ１のようになる。この書き込み開始されたセルＡは、時刻Ｔ０３においてセルＡの書き込みが終了する。また、図１６（ｃ）に示すＦフラグは、時刻Ｔ００においてオン（ハイ）にされて、セルＡの読み出しが終了する時刻Ｔ１１までオンが維持される。
【０１８９】
また、ＤＰＲＡＭ１のＢポートは、時刻Ｔ０２において、キーの読み出しを開始する。キーとは、入力ヘッダ情報セルから検索キー生成のために抽出されたデータ（Ａと表示されたもの）。時刻Ｔ０２におけるステータスフラグは図１４に示す論理Ｌ２のようになる。さらに、図１６（ｄ）に示すＳフラグはオンにされる。
【０１９０】
時刻Ｔ０５において、Ｂポートは、キーＡの読み出しを終了し、また、セルＡについての結果Ａの書き込みを開始する。この結果Ａは検索が終了し元のヘッダ情報セルにマージするデータである。時刻Ｔ０５におけるステータスフラグは変化しない。
さらに、時刻Ｔ０８においてＢポートはセルＡについての結果Ａの書き込みを終了し、また、Ａポートは、セルＡの読み出しを開始する。この時刻Ｔ０８において、ＡポートについてのＲフラグがオンにされ、時刻Ｔ０８におけるステータスフラグは図１４に示す論理Ｌ３のようになる。
【０１９１】
時刻Ｔ１１において、Ａポートは、セルＡについての読み出しを終了する。この時刻Ｔ１１において、Ｆフラグ、ＳフラグおよびＲフラグがともにオフにされる。時刻Ｔ１１におけるステータスフラグは図１４に示す論理Ｌ４のようになる。
さらに、図１４に示すＢポート側のセレクタ１５ｂにて得られる各データは、検索キー生成部６に出力される。また、Ｂポート側のバススイッチ１５ａにて得られる各データは、検索結果処理部７から入力される。
【０１９２】
以上、ＤＰＲＡＭ１の入出力動作について詳述した。
このほかに、ＤＰＲＡＭ１〜６が、図１５（ａ）に示すリングバッファを形成し、各々のＡポートとＢポートとのそれぞれが、図１７に示すように順次書き込みと読み出しとを行なうことにより、バッファ部５の４種類のポートについてそれぞれ、常時連続的にデータ書き込みおよび読み出しが可能なバッファシステムとして機能するのである。
【０１９３】
このように、ＣＡＭ検索システム１は、セルの連続的な送受信が可能となり、効率的なセル処理が実現する。また、このように、ステータスフラグを用いることにより、バッファ部５の各ＤＰＲＡＭがシーケンシャルに動作できる。
このようにして、ＤＰＲＡＭ＃１〜＃６のそれぞれが、巡回的にヘッダ情報セルをバッファリングするので、ＣＡＭ検索システム１は、連続的にヘッダ情報セルの受信および送信が可能となり、かつ連続的に検索キーの生成と、検索結果のマージとが可能となる。この結果、検索処理が連続して行なえるので、高速化が図れる。
【０１９４】
（１０）検索動作の説明
上述の構成により、本発明の一実施形態に係るＣＡＭ検索システム１が１個のヘッダ情報セルを受信しその受信したヘッダ情報セルに基づいて検索する場合の動作について説明する。なお、検索テーブルは、フィルタ検索テーブル１組のみ登録された場合のものである。フロー検索およびトレース検索については、以下に示すフィルタ検索の動作とほぼ同様なので、重複した説明を省略する。
【０１９５】
（１０−１）制御回路２における動作
図１０を参照して、ＣＡＭ検索方法について詳述する。ここで、ビット幅を拡張することにより、３種類の検索処理のフローを説明する。００２〜０２５までの各処理は、ひとかたまりの処理としてパイプライン化されており、１つのヘッダ情報セル処理中に他の処理を並行して可能となる。０１８の時点から、次のセルの検索種別コード＝０の検索キー送信を開始できる。
【０１９６】
００１  プロセッサ（ＮＤＰ１０ｃ）は、インターフェースからバッファ部５にセルを書き込む。
００２  検索キー生成部６は、バッファ部５から必要なデータを読み出して、そのデータのフォーマットを変換して検索キーを生成し、その検索キーを２面バッファ６ｃの片方の面に一時的に保持する。
【０１９７】
００３  検索キー生成部６は、２面バッファ６ｃに保持された検索キーに、検索種別コード生成部６ｄにて生成された検索種別コード「０」を付加し、その検索種別コード「０」付きの検索キー（検索種別コード「０」の検索キー）をＣＡＭ部３に送信する。この送信が、検索依頼のメッセージに相当する。
００４  検索キー生成部６は、００３（００３の処理）が終了すると、続けて検索種別コード「２」の検索キーをＣＡＭ部３に送信開始する。
【０１９８】
００５  検索キー生成部６は、００４の終了に続けて検索種別コード「４」の検索キーをＣＡＭ部３に送信開始する。
００６  次に、検索結果処理部７は、検索種別コード「０」の検索結果ステータスをＣＡＭ部３から受信して一時的に第２レジスタ７ｂに保持する。これと同時に、ＣＡＭ部３は、ＭＥＭ部４に対して検索結果アドレスを入力する。
【０１９９】
００７  また、検索キー生成部６は、検索種別コード「１」の検索キーをＣＡＭ部３に送信開始する。
００８  検索結果処理部７は、検索種別コード「０」の検索結果連想データ（インデックスに相当する）をＭＥＭ部４から読み出してその読み出した検索結果連想データを検索キー生成部６に入力する。
【０２００】
００９  検索キー生成部６は、検索種別コード「１」に、００８において得られたインデックスを付加し、検索キーをＣＡＭ部３に送信する。
０１０  検索結果処理部７は、検索種別コード「２」の検索結果ステータスをＣＡＭ部３から受信して一時的に第２レジスタ７ｂに保持する。これと同時に、ＣＡＭ部３は、ＭＥＭ部４に対して検索結果アドレスを入力する。
【０２０１】
０１１  検索キー生成部６は、検索種別コード「３」の検索キーをＣＡＭ部３に送信開始する。
０１２  検索結果処理部７は、検索種別コード「２」の検索結果連想データ（インデックス）をＭＥＭ部４から読み出してその読み出した検索結果連想データを検索キー生成部６に入力する。
【０２０２】
０１３  検索キー生成部６は、検索種別コード「３」に、０１２において得られたインデックスを付加し、検索キーをＣＡＭ部３に送信する。
０１４  検索結果処理部７は、検索種別コード「４」の検索結果ステータスをＣＡＭ部３から受信して一時的に第２レジスタ７ｂに保持する。これと同時に、ＣＡＭ部３は、ＭＥＭ部４に対して検索結果アドレスを入力する。
【０２０３】
０１５  検索キー生成部６は、検索種別コード「５」の検索キーをＣＡＭ部３に送信開始する。
０１６  検索結果処理部７は、検索種別コード「４」の検索結果連想データ（インデックス）をＭＥＭ部４から読み出してその読み出した検索結果連想データを検索キー生成部６に入力する。
【０２０４】
０１７  検索キー生成部６は、検索種別コード「５」に、０１６において得られたインデックスを付加し、検索キーをＣＡＭ部３に送信する。
０１８  検索結果処理部７は、検索種別コード「１」の検索結果ステータスをＣＡＭ部３から受信して一時的に第２レジスタ７ｂに保持する。
０１９  検索結果処理部７は、検索種別コード「１」の検索結果連想データ（インデックス）をＭＥＭ部４から読み出して第１レジスタ７ａに一時的に保持する。
【０２０５】
０２０  検索結果処理部７は、検索種別コード「３」の検索結果ステータスをＣＡＭ部３から受信して一時的に第２レジスタ７ｂに保持する。
０２１  検索結果処理部７は、検索種別コード「３」の検索結果連想データ（インデックス）をＭＥＭ部４から読み出して第１レジスタ７ａに一時的に保持する。
【０２０６】
０２２  検索結果処理部７は、検索種別コード「５」の検索結果ステータスをＣＡＭ部３から受信して一時的に第２レジスタ７ｂに保持する。
０２３  検索結果処理部７は、検索種別コード「５」の検索結果連想データ（インデックス）をＭＥＭ部４から読み出して第１レジスタ７ａに一時的に保持する。
【０２０７】
０２４  検索結果処理部７は、００６，０１０，０１４，０１８，０２０および０２２にてそれぞれ取得した検索結果ステータスをマージして判定し、その判定結果と０１９，０２１および０２３にてそれぞれ取得した検索結果連想データをフォーマット変換してバッファ部５に書き込む。
０２５  インターフェース部９０は、バッファ部５に保持されたセルデータを読み出す。
【０２０８】
このように、ＮＤＰ１０ｃは３個の検索キーを生成して送信し、また、３個の検索結果の連想データを１回受信する毎にマージする必要がなくなり、プロセッサの負担を減少させることができる。
さらに、ｍ番目（ｍは自然数を表す。）のヘッダ情報セルについての各処理が行なわれているときに、０１８の時点からｍ＋１番目のヘッダ情報セルについての各処理を開始することができ、検索処理のパイプライン化が可能となる。
【０２０９】
（１０−２）検索キーの生成および検索結果処理
図１０に示す制御回路２において、入力されたヘッダ情報セルが検索キー生成部６に取り込まれることを契機に動作が開始し（図１０に示す００１から００２と付したところ参照）、検索キーの生成について以下の（Ｋ１）〜（Ｋ１０）に詳述する。
【０２１０】
（Ｋ１）ヘッダ情報セルは並べ替え処理部６ｂを経て、２面バッファ６ｃのバッファ１の前半に、次の検索キーを書き込まれる。検索キー（２８８ビット）バッファ１の前半の内容は次のようになる。
０ｘＳ１１１１２２２２３３３３３４４５５６６６７７７００００．．．．００００
ここで、先頭ビット「Ｓ」（検索種別コード）はこの時点においてはコードを記録されていない。
【０２１１】
さらに、末尾ビット「００００，００００」のシーケンス列は１８４ビットである。以下に説明する（Ｋ２）〜（Ｋ４）についても同様である。
（Ｋ２）検索キー生成部６は、フィルタ１の検索を開始し、検索種別コードを生成し、下記の検索キー（２８８ビット。完全に表示したもの）をＣＡＭ部３へ送信する。また、ＣＡＭ部３へ送信する内容はフィルタ１（Ｓ＝０ｘ０）である。
【０２１２】
０ｘ０１１１１２２２２３３３３３４４５５６６６７７７００００．．．．００００
（Ｋ３）検索キー生成部６は、フロー１の検索を開始し、検索種別コードを生成し、下記の検索キー（２８８ビット。完全に表示したもの）をＣＡＭ部３へ送信し、ＣＡＭ部３へ送信する内容はフロー１（Ｓ＝０ｘ２）である。
０ｘ２１１１１２２２２３３３３３４４５５６６６７７７００００．．．．００００
（Ｋ４）検索キー生成部６は、トレース１の検索を開始し、検索種別コードを生成し、下記の検索キー（２８８ビット。完全に表示したもの）をＣＡＭ部３へ送信し、ＣＡＭ部３へ送信する内容はトレース１（Ｓ＝０ｘ４）である。
【０２１３】
０ｘ４１１１１２２２２３３３３３４４５５６６６７７７００００．．．．００００
（Ｋ５）この間、並行して、検索キー生成部６は、並べ替え処理部６ａを経て、バッファ１の後半に、下記の検索キー（２８８ビット。一部不完全な表示）の書き込みを続行する。バッファ１の後半の内容を次に示す。
０ｘＳＩＩＩＩＡＡＡＡ．．．．．．ＡＡＡＡＢＢＢＢ．．．．．．ＢＢＢＢ０００
ここで、先頭ビット「Ｓ」（検索種別コード）はこの時点においてはコードを記録されていない。また、”ＩＩＩＩ”の部分はインデックスを表しこの時点では未定である。なお、”ＡＡＡＡ．．．”および”ＢＢＢＢ．．．”の部分の例はいずれも１２８ビットである。
【０２１４】
（Ｋ６）ＣＡＭ部３における処理を経て、制御回路２にフィルタ１の検索結果が返ってくる。上記検索キーは、ＣＡＭアドレス０ｘ００００のＣＡＭエントリにマッチするので、ヒットステータスおよびヒットしたアドレス（すなわち０ｘ００００）が得られ、このＭＥＭアドレスのＭＥＭエントリである０ｘ００１０００００が読み出されるので、結果として、インデックス０ｘ００１０が得られる。
【０２１５】
（Ｋ７）そこで、フィルタ２の検索が開始される。すなわち、検索種別コードが生成され、かつ、Ｉｎｄｅｘ値０ｘ００１０を含めた、下記の検索キー（２８８ビット。完全に表示したもの）がＣＡＭ部３へ送信される。ＣＡＭ部３へ送信する内容はフィルタ２（Ｓ＝０ｘ１）である。、”ＡＡＡＡ．．．”および”ＢＢＢＢ．．．”の部分の例はいずれも１２８ビットである。
【０２１６】
０ｘ１００１０ＡＡＡＡ．．．．．．ＡＡＡＡＢＢＢＢ．．．．．．ＢＢＢＢ０００
（Ｋ８）フロー１の検索結果が返ってくる。
検索キーにマッチするＣＡＭエントリがない場合は、ミスヒットステータスが得られ、有効なアドレスは得られない。このときは、フロー２の検索は省略される。
【０２１７】
（Ｋ９）フィルタ２の検索結果が返ってくる。
検索キーは、ＣＡＭアドレス０ｘ００１０のＣＡＭエントリにマッチするので、ヒットステータスおよびヒットしたアドレス（すなわち  ０ｘ００１０）が得られる。このアドレスはＭＥＭエントリである０ｘ１０００００００が読み出されるので、結果として、ｄｉｓｃａｒｄ＝１  すなわち、廃棄対象フレームの結果が得られる。
【０２１８】
なお、フィルタ検索は、フィルタ１およびフィルタ２を含めた全体として、ヒットステータスとなり、有効な検索結果として  ｄｉｓｃａｒｄ＝１  が得られる。
また、フロー２の検索結果は、検索されず、ミスヒットと判定される。検索結果は、デフォルトプライオリティの値として、ｐｒｉｏｒｉｔｙ＝０ｘ７  を返す。なお、フロー検索は、フロー１およびフロー２を含めた全体として、ミスヒットステータスとなり、有効な検索結果は得られない。
【０２１９】
（Ｋ１０）トレース２の検索結果は、検索されず、ミスヒット扱いとなる。検索結果は、デフォルトのトレースモード値として、ｔｒａｃｅ−ｍｏｄｅ＝０を返す。このトレース検索は、トレース１およびトレース２を含めた全体として、ミスヒットステータスとなり、有効な検索結果は得られない。
このため、判定および並び替え処理部７ｃ（図１０参照）は、バッファ部５に保持されたヘッダ情報セルに含まれる３種類の検索処理の検索順序を並べ替えて、並び替えたヘッダ情報セルをバッファ部５に書き込む。
【０２２０】
なお、判定および並べ替え処理部７ｃにおけるステータス判定からこの並べ替え処理までが、検索結果のマージに相当する。
これにより、２度引き処理により、１個のＣＡＭ部３を用いて、３種類の検索について前半，後半の検索するので、計６種類の検索テーブルを区別できる。
このように、１個のＣＡＭ部３の１個の連続したメモリ領域に３種類の検索テーブルが登録され、ＣＡＭデータおよび検索キーのそれぞれの中に検索種別コードが含められ、検索種別コードも検索対象とされる。
【０２２１】
また、このように、ＣＡＭ部３の領域全体について検索を実行しても、検索種別コードが異なるＣＡＭデータにはヒットせず、独立のＣＡＭ部３のように動作させることができる。ＮＤＰ１０ｃ等の各種のＣＰＵにおける処理負担が軽減する。
（１０−３）バッファ部５（ＱＰＲＡＭ，セルバッファ，６段リングバッファ）のデータ入出力動作
上述の構成により、本発明の一実施形態に係るＣＡＭ検索方法のバッファ部５のデータ入出力について詳述する。
【０２２２】
図１７は本発明の一実施形態に係るバッファ部５（ＱＰＲＡＭ）のタイムチャート例を示す図である。この図１７に示す１６個の信号はポート種別を表し、１６個のうちの上側の１〜４は、バッファ部５の４個のポートを表す。また、下側の５〜１６は、バッファ部５の内部のポートについての動作タイミングを表す。以下、横軸方向に付された時刻Ｔ００〜Ｔ２５における動作について時系列にしたがって説明する。
【０２２３】
時刻Ｔ００のトランザクション（１つのデータ転送動作）は、図１４のポート００１からポート００５に対するＦ０１（セルＡ）の書き込みを開始する。なお、以下に説明する各時刻におけるトランザクションをＴＲで表す。すなわち、時刻Ｔ００において、ＴＲ０１が行なわれる。
時刻Ｔ０２において、ポート００６からポート００２に対するＦ０７（キー７）の読み出しを開始する（ＴＲ０２）。
【０２２４】
時刻Ｔ０３において、ＴＲ０１が終了する。また、ポート００１からポート００７に対するＦ０２（セルＢ）の書き込みを開始する（ＴＲ０３）。
時刻Ｔ０５において、ＴＲ０２が終了する。また、ポート００３からポート００６に対するＦ１３（結果Ａ）の書き込みを開始する（ＴＲ０４）。ここで、検索結果処理部７は、検索結果ステータスのマージと判定し、並び替え処理部６ａに対してインデックスをフィードバックする。さらに、ポート００８からポート００２に対するＦ０８（キーＢ）の読み出しを開始する（ＴＲ０５）。
【０２２５】
時刻Ｔ０６において、ＴＲ０３が終了する。また、ポート００１から００９に対するＦ０３（セルＣ）の書き込みを開始する（ＴＲ０６）。
時刻Ｔ０８において、ポート００５からポート００４に対するＦ１９（セルＡ）の読み出しを開始する（ＴＲ０７）。また、ＴＲ０４が終了し、ＴＲ０５が終了する。さらに、ポート００３からポート００８に対するＦ１４（結果Ｂ）の書き込みを開始する（ＴＲ０８）。そして、ポート０１０からポート００２に対するＦ０９（キーＣ）の読み出しを開始する（ＴＲ０９）。
【０２２６】
時刻Ｔ０９において、ＴＲ０６が終了する。また、ポート００１からポート０１１に対するＦ０４（セルＤ）の書き込みを開始する（ＴＲ１０）。
時刻Ｔ１１において、ＴＲ０７が終了する。ポート００７からポート００４に対するＦ２０（セルＢ）の読み出しを開始する（ＴＲ０７）。また、ＴＲ０８が終了し、ＴＲ０９が終了する。さらに、ポート００２からポート０１０に対するＦ１５（結果Ｃ）の書き込みを開始する（ＴＲ１２）。そして、ポート０１２からポート００２に対するＦ１０（キーＤ）の読み出しを開始する（ＴＲ１３）。
【０２２７】
時刻Ｔ１２において、ＴＲ１０が終了する。また、ポート００１からポート０１３に対するＦ０５（セルＥ）の書き込みを開始する（ＴＲ１４）。
時刻Ｔ１４において、ＴＲ１１が終了する。ポート００９からポート００４に対するＦ２１（セルＣ）の読み出しを開始する（ＴＲ１５）。また、ＴＲ１２が終了し、ＴＲ１３が終了する。さらに、ポート００３からポート０１２に対するＦ１６（結果Ｄ）の書き込みを開始する（ＴＲ１６）。そして、ポート０１４からポート００２に対するＦ１１（キーＥ）の読み出しを開始する（ＴＲ１７）。
【０２２８】
時刻Ｔ１５において、ＴＲ１４が終了する。また、ポート００１からポート０１５に対するＦ０６（セルＦ）の書き込みを開始する（ＴＲ１８）。
時刻Ｔ１７において、ＴＲ１５が終了する。ポート０１１からポート００４に対するＦ２２（セルＣ）の読み出しを開始する（ＴＲ１９）。また、ＴＲ１６が終了し、ＴＲ１７が終了する。さらに、ポート００３からポート０１４に対するＦ１７（結果Ｅ）の書き込みを開始する（ＴＲ２０）。そして、ポート０１６からポート００２に対するＦ１２（キーＦ）の読み出しを開始する（ＴＲ２１）。
【０２２９】
時刻Ｔ１８において、ＴＲ１８が終了する。
時刻Ｔ２０において、ＴＲ１９が終了する。ポート０１３からポート００４に対するＦ２３（セルＤ）の読み出しを開始する（ＴＲ１９）。また、ＴＲ２０が終了し、ＴＲ２１が終了する。さらに、ポート００３からポート０１６に対するＦ１８（結果Ｆ）の書き込みを開始する（ＴＲ２３）。
【０２３０】
時刻Ｔ２３において、ＴＲ２２が終了する。ポート０１５からポート００４に対するＦ２４（セルＥ）の読み出しを開始する（ＴＲ２４）。また、ＴＲ２３が終了する。
時刻Ｔ２６において、ＴＲ２４が終了する。
このようにして、００１の前段に設けられたプロセッサから００１に対して連続して６個のセル（セルＡ〜Ｆ）を送信される。
【０２３１】
また、６セルの処理中は、ポート００４の外側（外部装置８７側）のＮＤＰ１０ｃは、受信可能になっている。すなわち、ＮＤＰ１０ｃは、ポート００４を有するＣＡＭ検索システム１に対してバックプレッシャーを通知しない。
このバックプレッシャーとは、フレーム損失を防止するためのメッセージである。例えば、ＣＡＭ部３からの検索結果が過剰に出力された場合において各検索結果データを含むヘッダ情報セルが、ＣＡＭ検索システム１からＮＤＰ１０ｃに対して送信され続けると、ＮＤＰ１０ｃにおいてフレーム損失が発生する。このため、通常は、ＮＤＰがポート００４に対してデータの出力を抑制するメッセージを送信する。
【０２３２】
従って、ＮＤＰ１０ｃは、制御回路２が、ＣＡＭ検索システム１に対してプロセッサに対する出力を抑制するバックプレッシャーを送信するようになっている。
そして、このように、プロセッサとＣＡＭ検索システム１との間におけるインターフェースにおいて送受信データが送受信される。また、プロセッサ（ＮＤＰ１０ｃ）は、ルーティングするために、１個の入力フレームに対して、そのフレームのヘッダ情報と装置内部情報とを含む固定長フォーマットのセル（ヘッダ情報セル）の形式でフレーム情報を内部処理する。
【０２３３】
さらに、ヘッダ情報セルに、３種類の検索キーを生成するのに必要な情報領域と、３種類の検索結果を取り込むための領域とが追加されるので、プロセッサとＣＡＭ検索システム１との間は、１個のヘッダ情報セルの送受信によって処理が可能になる。また、このＣＡＭ検索システム１が処理した後の処理が、プロセッサの外部のハードウェアに委ねられ、プロセッサの性能を十分に発揮できる。
【０２３４】
次に、３種類の検索を高速に実行するためのＣＡＭ制御と、パイプライン処理とについて説明する。
（１１）検索処理の高速化
（１１−１）ＣＡＭ制御の高速化
上記のＣＡＭ部３のビット幅を拡張する方法を用いた場合、２回の検索によるレイテンシ（Ｌａｔｅｎｃｙ：待ち時間）の増大およびスループットの低下が発生する。すなわち、前半の検索結果を後半の検索キーとしなければならないため、後半の検索開始は、ＣＡＭ部３の検索時間だけ待たされる。従って、ＣＡＭ部３がパイプライン処理を実行可能であっても、前半の検索が終了するまで後半の検索開始が待たされることによって、全体としてのＣＡＭ部３のスループットが低下する。
【０２３５】
ここで、レイテンシとは、メモリから保持データを読み出すために必要な時間である。すなわち、レイテンシは、ＮＤＰ１０ｃ（およびＣＰＵ９０ａ，９１ｂ，１０ａ）が、バッファ部５又はＣＡＭ検索システム１に設けられたＣＡＭアレイ３ａ，ＭＥＭアレイ４ａ等の各種のメモリに保持されたデータの読み出し要求を出力した瞬間から、その読み出し要求が要求する保持データが転送される瞬間までの時間を意味する。
【０２３６】
３種類（例えば、検索１、検索２、検索３の３種類）の検索をＣＡＭ部３のビット幅を拡張するＣＡＭ制御方法を用いる場合、検索１前半の検索結果を待たずに、検索２前半、続いて検索３前半を開始し、検索１前半の結果を踏まえて検索１後半を行ない、検索２後半、検索３後半の順序で計６回検索する。
上記のように、検索順序を制御することにより、全体としてのレイテンシとスループットとを向上させ、ＣＡＭ部３のスループット性能を最大限に活用することが可能となる。
【０２３７】
（１１−２）パイプライン処理
また、図１２（ａ），図１２（ｂ）はそれぞれ本発明の一実施形態に係るパイプライン処理を説明するための図である。この図１２（ａ）に示すシーケンシャル処理は、従来の２度引き検索処理である。ＣＡＭ検索システム１は、キー（検索キー）１を入力されて検索を開始し、１回目の検索結果のインデックスを出力し、そして、このインデックスが２回目の検索キーとしてＣＡＭ検索システム１に入力される。すなわち、各検索結果が次の検索キーとしてフィードバックされるようになっている。
【０２３８】
また、レイテンシを表すτ（タウ）を用いて検索時間を説明する。ここで、１τ＝１／６６ＭＨｚ＝１５ｎ（ナノ）秒に相当する。一方、ヘッダ情報セルが２４τ間隔で送信されるので、６回の検索に要する時間（検索キーが送信６回分を１周期として１周期に要する時間）は、シーケンシャルな検索によると５４τである。従って、ヘッダ情報セルが２４τ毎に入力されるので、検索処理はこのヘッダ情報セルが入力される間隔に追いつくことができない。
【０２３９】
これに対して、図１２（ｂ）に示すパイプライン処理は、受信セルの前半の検索キー（図５参照）が、ＣＡＭ検索システム１に入力され、その検索中に、後半の検索キーがＣＡＭ検索システム１に入力され、３種類の検索結果がマージされて送信セルに反映されるのである。
従って、３種類の検索を並行（パイプライン化）することにより、２４τ時間内に次次と検索が可能となる。そして、１周期に要する時間がシーケンシャル処理に比較して、約半分の検索時間に短縮される。
【０２４０】
さらに、検索キーに検索種別コードが付与されることにより、３種類の検索が行なわれ、また、３種類の検索テーブルについてそれぞれ前半および後半の２回に分割した検索により、合計６種類のテーブルの検索が行なわれる。すなわち、１個のＣＡＭ検索システム１に６種類の検索テーブル用のメモリ領域が割り当てられる。
【０２４１】
このように、本発明のＣＡＭ検索システム１の制御方法は、ＣＡＭ部３のビット幅よりも長いビット幅を有するアドレスデータについても高速に検索できる。
（Ｄ）本発明と従来の技術との比較
以下、従来の技術（特許文献１，２）と、本発明のルーティングエンジン装置，ルータ装置およびルーティングエンジン装置におけるメモリ検索方法とは、３点の相違点がある。
【０２４２】
（１２）制御回路２の有無について
（１２−１）特許文献１記載のアドレスサーチマシンおよびＩＰｖ６ルーティングエンジン１０は、ともに、ヘッダ情報を用いて３種類の検索キーを生成し、また、その検索結果をマージするＣＡＭ検索専用回路を設けた点については同一である。
【０２４３】
これに対して、特許文献１記載のアドレスサーチマシンに設けられたプロセッサおよびＣＡＭ検索専用回路間のインターフェースは、コマンドレジスタとリザルトレジスタとを用いている点において、プロセッサがベッダ情報セルを送受信回路（制御回路２）に送信し、ＣＡＭ検索システム１からそのヘッダ情報セルを受信するＩＰｖ６ルーティングエンジン１０と異なる。
【０２４４】
従って、ＩＰｖ６ルーティングエンジン１０は、ＣＡＭ検索システム１の検索終了までのタイミング測定等の制御が不要になり、プロセッサ負荷が低減される。さらに、ＩＰｖ６ルーティングエンジン１０において、ＣＡＭ部３にて検索されて出力された検索データが過剰になった場合は、ＮＤＰ１０ｃにおいてフレーム損失を防止でき、バックプレッシャー機能を有する点において、このバックプレッシャー機能を設けていない特許文献１と異なる。
【０２４５】
（１２−２）また、ヘッダ情報セルに関し、特許文献１記載のアドレスサーチマシンはプロセッサおよびＣＡＭ検索専用回路間のインターフェースにおけるセル処理について何ら言及されていない点において、送受信回路（制御回路２）が、ＮＤＰ１０ｃのセル処理に適合するように固定長のフォーマットのセルを処理するＩＰｖ６ルーティングエンジン１０と異なる。
【０２４６】
従って、ＩＰｖ６ルーティングエンジン１０は、プロセッサが処理するヘッダ情報セルが、そのまま使用されるのでプロセッサ負荷が低減する。
（１２−３）さらに、バッファ部５に関し、特許文献１記載のアドレスサーチマシンはヘッダ情報セルを一時的に保持するバッファについて何ら言及されていない点において、バッファ部５をそなえたＩＰｖ６ルーティングエンジン１０と異なる。
【０２４７】
また、ＩＰｖ６ルーティングエンジン１０は、検索キー生成のための情報および検索結果情報に加えて、プロセッサが再度利用できる情報を含んでおり、この再度利用可能な情報を変更せずに、ヘッダ情報セルをプロセッサに返すことができる。従って、ＩＰｖ６ルーティングエンジン１０のプロセッサは、データ退避等の処理をともなわずにヘッダ情報セルに含まれる情報を利用でき、これにより、プロセッサのリソースを有効利用でき、プロセッサ負荷が低減される。
【０２４８】
（１３）３回の検索方法について
（１３−１）従来の技術と本ルータとの各ＣＡＭ検索システムが、ＣＡＭ部のビット幅よりも長い検索キーを処理する場合において、各ＣＡＭ検索システムの検索は、３回に分割されて検索する点は同一である。
これに対して、特許文献１記載のアドレスサーチマシンは、長い検索キーを分割して３のＣＡＭ検索システム（図１４参照）を用いて検索する点について、長い検索キーを分割して、同一のＣＡＭ検索システムを用いて３回検索するＩＰｖ６ルーティングエンジン１０と異なる。
【０２４９】
従って、ＩＰｖ６ルーティングエンジン１０は、ＣＡＭ検索システムの個数が減少しかつハードウェアの規模が縮小され、ルータのコストを低減できる。
（１３−２）特許文献１記載のアドレスサーチマシンは、ＩＰｖ４プロセッサに対応する６４ビットのＣＡＭ検索システムを用いてＩＰｖ６アドレス１２８ビットを２分割し検索処理を行なっており、ビット幅は６４ビットに限定している。すなわち、特許文献１記載のアドレスサーチマシンは、ＩＰｖ４プロトコルに対応するＣＡＭ検索システムをＩＰｖ６プロトコルに転用している。
【０２５０】
これに対して、ＩＰｖ６ルーティングエンジン１０は、例えば２８８ビット幅のＣＡＭ検索テーブルを用いており、ＩＰｖ６アドレスの１２８ビットを分割せずに処理し、また、ＩＰｖ４アドレスの処理との兼用をしていない。
従って、ＩＰｖ６ルーティングエンジン１０は、ＩＰｖ６フレームに特化している。これにより、ＩＰｖ６ルーティングエンジン１０は、ＩＰｖ６アドレスの分割が不要になり、ＩＰｖ６アドレスを分割した検索テーブルの管理が不要となって検索テーブルの管理が簡略化される。
【０２５１】
（１３−３）検索種別について
特許文献１記載のアドレスサーチマシンは、ＩＰアドレスのサーチに限定されている点において、ＩＰアドレス以外の他の情報をも含めた検索テーブルを検索できるＩＰｖ６ルーティングエンジン１０と異なる。すなわち、ＩＰｖ６ルーティングエンジン１０は、例えば、送信先および送信元ポート番号、フローラベル、トラヒッククラス等のＩＰアドレス以外の情報をも用いて、フィルタ機能（フレーム廃棄機能）と、帯域制限機能等を実現するためのフレームのプライオリティを決定する機能（フロー識別機能）と、ネットワークシステムの調査等のために特定の受信フレームを抽出してプロセッサ処理する機能（トレース機能）との各機能を実現できる。
【０２５２】
（１３−４）検索キーのビット幅について
ＩＰｖ６ルーティングエンジン１０は、３種類のパラメータを用いてＣＡＭ検索するために、マスク条件を変更して３回検索する。ここで、ＩＰｖ６ルーティングエンジン１０は、ＣＡＭ部３のビット幅よりも長いビット幅を用いて検索するものではなく、さらに、ＣＡＭ部３のビット幅の短さ（不足）によって検索キーを分割しているものではない。
【０２５３】
従って、ＩＰｖ６ルーティングエンジン１０は、ＩＰｖ６アドレスおよび送信元ＩＰｖ６アドレスの両アドレスと、ヘッダ情報を含むＣＡＭ部３のビット幅よりも長いビット幅を有する検索キーを用いてＣＡＭ検索を実現できる。
（１４）ＣＡＭ検索の高速化について
ＩＰｖ６ルーティングエンジン１０は３回検索の順序を制御することにより、検索の待ち時間をなくすことができ、高速化できる。
【０２５４】
（Ｅ）その他
本発明は上述した実施態様およびその変形態ように限定されるものではなく、本発明の趣旨を逸脱しない範囲で、種々変形して実施することができる。
例えば、上記の説明において、各処理と各処理が行なわれる機能ブロックとは、設計方針等に基づいて種々変更可能であって、本発明のルーティングエンジン装置１０およびルーティングエンジン装置１０におけるメモリ転送方法は、上記の各例に限定されるものではない。
【０２５５】
ＩＰｖ６によってＩＰｖ６アドレスが飛躍的に増加し、また、アドレスを端末に自動的に設定できる。ネットワークを介して自動的に情報データを送受信する装置が増加する。この装置はネットワーク接続を主な目的としたものではなく、単に情報データの送受信のためにＩＰネットワークを利用するだけである。従って、利用者にネットワークの知識を要求せずにアドレスを設定する。
【０２５６】
なお、ルータ８は、近隣検索プロトコルが規定する処理を行なうようにもできる。この近隣検索プロトコルとは、同一リンクに接続された２台のノード間に適用されるプロトコルであって、ＩＰｖ６フレームに含まれるアドレスからＭＡＣアドレスに変換しその変換したデータリンクレイヤアドレスを取得する手順が定められている。
【０２５７】
近隣検索プロトコルは、ＩＰｖ４プロトコルが規定するＡＲＰ（Ａｄｄｒｅｓｓ  Ｒｅｓｏｌｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）に相当するものである。
このＡＲＰとは、ネットワークに設けられた２台のノード（ルータ，サーバ装置又はクライアント装置）間に適用されるプロトコルであって、ＩＰフレームを送信する送信側ノードが、そのＩＰフレームを受信する受信側ノードのＭＡＣアドレスを知るためのものである。送信側ノードにおいて、ＩＰレイヤ処理部にて生成されたＩＰフレームが、ＭＡＣアドレスを付与されて送信されるようになっている。
【０２５８】
従って、データリンクレイヤの処理は、ＩＰｖ６アドレスからＭＡＣアドレスに変換する必要がある。ここで、データリンクレイヤは、宛先ノードのＭＡＣアドレスを通常知らないので、送信側ノードは、受信側ノードのＭＡＣアドレスを得るために、宛先ノードのＩＰｖ６アドレスを含むメッセージをネットワークの全てのノードに対して送信する。そして、そのメッセージを受信したノードは、メッセージに含まれるＩＰｖ６アドレスを参照して自分自身宛のリクエストであることを知ると、自分自身のＭＡＣアドレスを送信するようになっている。
【０２５９】
これにより、外部装置８７は、ルータ８のＩＰｖ６アドレスおよびプレフィクスを含む要請メッセージをリンクに接続された全てのノードに対して送信する。そして、そのＩＰｖ６アドレスを有するルータ８は、この要請メッセージを受信すると、外部装置８７に対してＭＡＣアドレスを含む応答メッセージを送信する。
【０２６０】
上記のレイテンシと別個の概念として、アクセスタイムが知られている。このアクセスタイムとは、書き込み又は読み出しの動作に要する時間であり、概略的には、レイテンシに保持データの転送時間を加えた時間を意味する。
（Ｆ）付記
（付記１）  フレームのヘッダ情報に基づいて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置であって、
該フレームと、該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、
該プロセッサにて変換された該ヘッダ情報セルの該検索情報に基づいて該複数種類の検索処理を行ない該複数の検索結果を該ヘッダ情報セルに書き込み該ヘッダ情報セルを該プロセッサに対して送信する連想メモリ（ＣＡＭ［Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ］検索システム）とをそなえて構成されたことを特徴とする、ルーティングエンジン装置。
【０２６１】
（付記２）  外部ネットワークに接続された外部ノードと該プロセッサとの間のフレームフォーマットを変換し、複数の受信フレームのうちの第１フォーマットを有する第１フレームを該外部ノードに対して折り返し転送するとともに該複数の受信フレームのうちの第２フォーマットを有する第２フレームを該プロセッサに出力し、該プロセッサからの第３フォーマットを有する第３フレームを該外部ノードに対して送信する転送処理部をさらにそなえて構成されたことを特徴とする、付記１記載のルーティングエンジン装置。
【０２６２】
（付記３）  該プロセッサが、
該フレームに含まれるヘッダ情報と装置内部情報とを含むヘッダ情報セルを、該複数種類の検索処理に要する検索情報として生成するように構成されたことを特徴とする、付記１記載のルーティングエンジン装置。
（付記４）  該ＣＡＭ検索システムが、
該プロセッサからの該ヘッダ情報セルに基づいて検索キーを生成するとともに、該検索キーについての検索結果をプロセッサに対して送信する制御回路と、
参照用の複数の登録データを保持し該複数の登録データのうちの該制御回路にて生成された該検索キーと一致する登録データのメモリアドレスを出力する検索結果保持部と、
該検索結果保持部のアドレス配置と同一のアドレス配置を有し該検索結果保持部から出力された該メモリアドレスに保持されたデータを出力する連想データ保持部とをそなえて構成されたことを特徴とする、付記３記載のルーティングエンジン装置。
【０２６３】
（付記５）  該制御回路が、
該ヘッダ情報セルを保持するバッファ部と、
該バッファ部に保持された該ヘッダ情報セルから抽出した情報に基づいて該複数種類の検索処理を表す複数の検索キーを生成する検索キー生成部と、
該検索キー生成部にて生成された該複数の検索キーについての検索結果を含む複数の連想データに基づいて該ヘッダ情報セルを生成し該ヘッダ情報セルを該プロセッサに対して送信する検索結果処理部とをそなえて構成されたことを特徴とする、付記４記載のルーティングエンジン装置。
【０２６４】
（付記６）  該バッファ部が、
該フレームの転送に関する複数の検索種別を表す検索識別と、該複数の検索種別の各検索結果を表す検索結果と、該複数の検索種別に要する検索情報を表す検索情報と、該フレームのヘッダ情報を表すヘッダ情報との各領域を含むヘッダ情報セルを保持するように構成されたことを特徴とする、付記５記載のルーティングエンジン装置。
【０２６５】
（付記７）  該バッファ部が、
該ヘッダ情報セルの書き込みおよび読み出しを共用する複数のバスラインと接続され該複数のバスラインを介して書き込み制御信号と読み出し選択信号とを入出力可能な複数のデュアルポートメモリと、
各バスラインに該書き込み制御信号を出力することにより、該複数のデュアルポートメモリのうちの書き込み対象のデュアルポートメモリにデータを書き込む第１メモリ選択部と、
各バスラインに出力された該読み出し選択信号に基づいて、該複数のデュアルポートメモリのうちの読み出し対象のデュアルポートメモリからデータを第２メモリ選択部とをそなえて構成されたことを特徴とする、付記５記載のルーティングエンジン装置。
【０２６６】
（付記８）  該制御回路が、
該ＣＡＭ検索システムから該プロセッサに対するデータ出力の抑制を通知するバックプレッシャーメッセージを送信するように構成されたことを特徴とする、付記１記載のルーティングエンジン装置。
（付記９）  該ＣＡＭ検索システムが、
該フレームについて廃棄又は通過を判定するフィルタ検索と、該フレームのプライオリティを判定するフロー検索と、該フレームの送信先アドレス又は該フレームの送信元アドレスに基づいて該フレームのうちの転送経路を出力するフレームを抽出するか否かを判定するトレース検索とのうちの少なくとも１種類の検索処理を行ない、各検索結果を該ヘッダ情報セルに書き込むように構成されたことを特徴とする、付記１〜付記８のいずれか一に記載のルーティングエンジン装置。
【０２６７】
（付記１０）  該ＣＡＭ検索システムが、
該ヘッダ情報セルの連続したメモリ領域に複数の連想メモリデータを登録する登録部を設け、
該登録部が、該登録された該複数の連想メモリデータと該検索種別コードとを対応付けて該バッファ部に保持するように構成されたことを特徴とする、付記９記載のルーティングエンジン装置。
【０２６８】
（付記１１）  該ＣＡＭ検索システムが、
該ヘッダ情報セルに含まれる情報を含む連想メモリデータを該連想メモリデータに分割し、該連想メモリデーのうちの第１テーブルと第２テーブルとを対応付けるインデックスを生成し、該インデックスに該検索キーを加えたものを該第２データとして該バッファ部に保持し、該第２データと分割前の全体の連想メモリデータに対応する連想データを保持するように構成されたことを特徴とする、付記７記載のルーティングエンジン装置。
【０２６９】
（付記１２）  該ＣＡＭ検索システムが、
該連想メモリデータを保持する連続領域に該複数の検索テーブルを設けるとともに、該複数の検索テーブルおよび該検索キーに該検索処理を識別する検索種別コードを検索対象として格納するように構成されたことを特徴とする、付記１１記載のルーティングエンジン装置。
【０２７０】
（付記１３）  該ＣＡＭ検索システムが、さらに、
該バッファ部に保持された該ヘッダ情報セルに含まれる複数の検索処理の検索順序を制御するバッファ制御部をそなえて構成されたことを特徴とする、付記１２記載のルーティングエンジン装置。
（付記１４）  フレームのヘッダ情報に基づいて該フレームの転送処理をする転送処理部と該ヘッダ情報を用いて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置とを有するルータ装置であって、
該ルーティングエンジン装置が、
該フレームと、該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、
該プロセッサにて変換された該ヘッダ情報セルの該検索情報に基づいて該複数種類の検索処理を行ない該複数の検索結果を該ヘッダ情報セルに書き込み該ヘッダ情報セルを該プロセッサに対して送信するＣＡＭ検索システムとをそなえるとともに、
該転送処理部が、
該ＣＡＭ検索システムから送信された該ヘッダ情報セルを上記のフレームに変換し、該変換したフレームを外部ネットワークに接続された外部ノードに転送するように構成されたことを特徴とする、ルータ装置。
【０２７１】
（付記１５）  該転送処理部が、
該外部ノードと該プロセッサとの間のフレームフォーマットを変換し、複数の受信フレームのうちの第１フォーマットを有する第１フレームを該外部ノードに対して折り返し転送するとともに該複数の受信フレームのうちの第２フォーマットを有する第２フレームを該プロセッサに出力し、該プロセッサからの第３フォーマットを有する第３フレームを該外部ノードに対して送信するように構成されたことを特徴とする、付記１４記載のルータ装置。
【０２７２】
（付記１６）  フレームのヘッダ情報に基づいて該フレームの転送処理をする転送処理部と該ヘッダ情報を用いて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置とを有するルータ装置であって、
該複数種類の検索処理を表す複数の検索キーを用いて複数種類の検索処理を行ない複数の検索結果を保持する検索結果保持部と、
該検索結果保持部における該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルを保持するバッファ部と、
該バッファ部に保持された該ヘッダ情報セルから抽出した情報に基づいて該検索結果保持部に保持された該複数の検索キーを生成する検索キー生成部とをそなえて構成されたことを特徴とする、ルータ装置。
【０２７３】
（付記１７）  フレームのヘッダ情報に基づいて該フレームの転送に関する複数種類の検索処理を行なうルーティングエンジン装置における検索方法であって、
該フレームと、該複数種類の検索処理に要する検索情報を保持する領域および該複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサが、該ヘッダ情報セルを送信するヘッダ情報セル送信ステップと、
該ＣＡＭ検索システムが、該ヘッダ情報セル送信ステップにて入力された該ヘッダ情報セルに含まれる検索情報に基づいて該複数の検索キーを生成する検索キー生成ステップと、
該ＣＡＭ検索システムが、該検索キー生成ステップにて生成された該複数の検索キーに基づいて該複数の検索処理を行なう検索処理ステップと、
該プロセッサが、該検索処理ステップにて検索処理された該複数の検索結果を表す複数の連想データを受信する検索結果受信ステップとをそなえたことを特徴とする、ルーティングエンジン装置におけるメモリ検索方法。
【０２７４】
（付記１８）  該検索処理ステップが、
該ＣＡＭ検索システムに設けられ該ヘッダ情報セルの連続したメモリ領域に複数の連想メモリデータを登録する登録部が、第１のメモリ領域を割り当てるとともに該第１のメモリ領域のメモリアドレスと同一のメモリアドレスを有する第２のメモリ領域を割り当てるメモリ領域割り当てステップと、
該登録部が、該複数の連想メモリデータのうちの第１の連想メモリデータを該メモリ領域割り当てステップにて割り当てられた該第１のメモリ領域に格納するとともに、該複数の連想メモリデータのうちの第２の連想メモリデータを該第２のメモリ領域に格納する格納ステップと、
該登録部が、該格納ステップにて該第１の連想メモリデータを格納した該第１のメモリ領域の第１アドレスと同一の該第２のメモリ領域の第２アドレスにインデックスを格納するインデックス格納ステップと、
該登録部が、該インデックス格納ステップにて格納した該インデックスと、上記の検索キー生成ステップにて生成された該複数の検索キーとに基づいて上記の複数の検索処理を行なう第２検索処理ステップとをそなえて構成されたことを特徴とする、付記１７記載のルーティングエンジン装置におけるメモリ検索方法。
【０２７５】
【発明の効果】
以上、詳述したように、本発明のルーティングエンジン装置，ルータ装置およびルーティングエンジン装置におけるメモリ検索方法によれば、以下のような効果ないしは利点がある。
本発明のルーティングエンジン装置によれば、フレームと、複数種類の検索処理に要する検索情報を保持する領域および複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、プロセッサにて変換されたヘッダ情報セルの検索情報に基づいて複数種類の検索処理を行ない複数の検索結果をヘッダ情報セルに書き込みヘッダ情報セルをプロセッサに対して送信する連想メモリとをそなえて構成されているので、例えばプロセッサ等に接続されたＣＡＭ検索システムにおいて、ヘッダ情報セルの採用およびフォーマット変換を、プロセッサとは別個に外部に設けられたハードウェアにより肩代わりでき、これにより、プロセッサ等の負荷が低減し、インデックスポインタを用いて複数回の検索によって検索結果保持部が処理可能なビット幅を超えたビット幅のデータについての検索を実現できる（請求項１）。
【０２７６】
また、本発明のルータ装置によれば、ルーティングエンジン装置が、フレームと、複数種類の検索処理に要する検索情報を保持する領域および複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサと、プロセッサにて変換されたヘッダ情報セルの検索情報に基づいて複数種類の検索処理を行ない複数の検索結果をヘッダ情報セルに書き込みヘッダ情報セルをプロセッサに対して送信するＣＡＭ検索システムとをそなえて構成されているので、ＣＡＭ検索システムにおける例えば３種類の検索の順序を制御でき、これにより、検索結果保持部のスループットを最大限、有効利用した高速検索が実現できる（請求項２）。
【０２７７】
さらに、本発明のルーティングエンジン装置におけるメモリ検索方法によれば、フレームと、複数種類の検索処理に要する検索情報を保持する領域および複数の検索結果を書き込むための領域を含むヘッダ情報セルとを相互に変換するプロセッサが、ヘッダ情報セルを送信するヘッダ情報セル送信ステップと、ＣＡＭ検索システムが、ヘッダ情報セル送信ステップにて入力されたヘッダ情報セルに含まれる検索情報に基づいて複数の検索キーを生成する検索キー生成ステップと、ＣＡＭ検索システムが、検索キー生成ステップにて生成された複数の検索キーに基づいて複数の検索処理を行なう検索処理ステップと、プロセッサが、検索処理ステップにて検索処理された複数の検索結果を表す複数の連想データを受信する検索結果受信ステップとをそなえているので、複数種類かつビット幅の長いデータの検索処理について、検索結果保持部の設置個数を減少させることができる。さらに、プロセッサ等の負荷を低減するため、ＣＡＭ検索システムの全体を低コスト化で構築でき、また、処理が大幅に高速化する（請求項３）。
【０２７８】
加えて、本発明によれば、ヘッダ情報セルの連続送受信に対応でき、ネットワークプロセッサとＣＡＭ検索システムとの間におけるインターフェースにおいて、バックプレッシャー機能に対応でき、これにより、データの送受信信頼性が向上する。
また、本発明によれば、運用中のＭＥＭデータ書き替え機能に対応できる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る転送装置の構成例を示す図である。
【図２】本発明の一実施形態に係るＣＡＭ検索システムのブロック図である。
【図３】（ａ）は本発明の一実施形態に係る検索結果保持部のブロック図であり、（ｂ）は本発明の一実施形態に係るＣＡＭアレイのデータ例を説明するための図である。
【図４】本発明の一実施形態に係る連想データ保持部のブロック図である。
【図５】本発明の一実施形態に係る検索テーブルを説明するための図である。
【図６】（ａ）は本発明の一実施形態に係るＣＡＭ領域のデータ保持例を説明するための図であり、（ｂ）は本発明の一実施形態に係るＭＥＭ領域のデータ保持例を保持するための図である。
【図７】本発明の一実施形態に係るヘッダ情報セルのフォーマット例を示す図である。
【図８】（ａ）は本発明の一実施形態に係るＣＡＭ検索システムの検索方法を説明するための図であり、（ｂ）は本発明の一実施形態に係る制御回路を説明するための図である。
【図９】（ａ）は本発明の一実施形態に係るフレーム処理の流れを説明するためのフローチャートであり、（ｂ）は本発明の一実施形態に係る検索処理の流れを模式的に示す図である。
【図１０】本発明の一実施形態に係る制御回路の概略的なブロック図である。
【図１１】（ａ），（ｂ）はそれぞれ本発明の一実施形態に係る検索結果保持部と連想データ保持部との各データ例を示す図である。
【図１２】（ａ），（ｂ）はそれぞれ本発明の一実施形態に係るパイプライン処理を説明するための図である。
【図１３】本発明の一実施形態に係るバッファ部の４本の入出力ポートを説明するための図である。
【図１４】本発明の一実施形態に係る複数個のリングバッファのブロック図である。
【図１５】（ａ），（ｂ）はそれぞれ本発明の一実施形態に係るバッファ部のリングバッファ構成を説明するための図である。
【図１６】（ａ）〜（ｅ）はそれぞれ本発明の一実施形態に係るＤＰＲＡＭのステータスフラグを説明するためのタイムチャートである。
【図１７】本発明の一実施形態に係るＱＰＲＡＭのタイムチャート例を示す図である。
【図１８】従来のＣＡＭ検索システムの概略的な構成図である。
【符号の説明】
１    ＣＡＭ検索システム
１ａ    書き込み／読み出し部
２    制御回路
２ａ，２ｂ    インターフェース回路
３    ＣＡＭ部（検索結果保持部）
３ａ    ＣＡＭアレイ
３ｂ    ＣＡＭメモリ制御部
３ｃ，４ｃ    入出力インターフェース部
４    ＭＥＭ部（連想データ保持部）
４ａ    ＭＥＭアレイ
４ｂ    ＭＥＭメモリ制御部
５    バッファ部（セルバッファ，６段リングバッファ，ＱＰＲＡＭ）
６    検索キー生成部
６ａ    並び替え処理部
６ｂ    検索キー生成および並び替え処理部
６ｃ    ２面バッファ
６ｄ    検索種別コード生成部
６ｅ    セレクタ（第１セレクタ）
７    検索結果処理部
７ａ    第１レジスタ
７ｂ    第２レジスタ
７ｃ    判定および並び替え処理部
７ｄ    セレクタ（第２セレクタ）
８    ルータ（ルータ装置又は転送装置）
９    検索テーブル
９ａ    １回目のＣＡＭエントリ
９ｂ    １回目のＭＥＭエントリ
９ｃ    ２回目のＣＡＭエントリ
９ｄ    ２回目のＭＥＭエントリ
１０    ＩＰｖ６ルーティングエンジン（ルーティングエンジン装置）
１０ｂ    第３スイッチ
１０ｃ    ＮＤＰ（ネットワークデータプロセッサ）
１０ｄ，９０ｄ，９１ｃ，９１ｄ    ルーティングテーブル
１０ｅ    フレームバッファ
１５ａ    バススイッチ部（第２メモリ選択部）
１５ｂ    セレクタ（第１メモリ選択部）
８０，８２    フレーム
８０ａ，８２ａ    ヘッダ
８０ｂ    ペイロード
８１    ヘッダ情報セル
８１ａ    装置内部情報
８７    外部装置（外部ノード）
８８    ＲＯＭ
８９    ＲＡＭ
９０    インターフェース部（転送処理部）
９０ａ，９１ｂ，１０ａ    ＣＰＵ
９０ｂ    第１スイッチ部
９０ｃ    インターフェース処理部
９１    本体スイッチ部（転送処理部）
９１ａ    第２スイッチ部
９１ｅ    ＩＰｖ６アドレス解決検索部
【図１】
2005012271.tif 000003
【図２】
2005012271.tif 000004
【図３】
2005012271.tif 000005
【図４】
2005012271.tif 000006
【図５】
2005012271.tif 000007
【図６】
2005012271.tif 000008
【図７】
2005012271.tif 000009
【図８】
2005012271.tif 000010
【図９】
2005012271.tif 000011
【図１０】
2005012271.tif 000012
【図１１】
2005012271.tif 000013
【図１２】
2005012271.tif 000014
【図１３】
2005012271.tif 000015
【図１４】
2005012271.tif 000016
【図１５】
2005012271.tif 000017
【図１６】
2005012271.tif 000018
【図１７】
2005012271.tif 000019
【図１８】
2005012271.tif 000020