"外部から入力された検索キーを複数の連想メモリに登録されている各エントリの検索キーと比較して一致したエントリの内容を検索結果として出力する検索装置において、前記検索キーから1つの連想メモリを識別するビット位置を示す複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの検索回数を算出する算出手段と、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数を基に、検索回数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定する優先順位決定手段と、前記優先順位が高い検索パターンと前記検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記検索キーを再配置する再配置手段と、を有することを特徴とする検索装置。請求項1記載の検索装置において、前記検索結果として出力されるエントリの内容で検索され前記検索キーを含む検索情報が格納されたデータテーブルを有し、前記再配置手段は、前記優先順位が最も高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置するとき、前記複数の連想メモリのいずれかで連想メモリの格納数の上限値を超えた場合、次に優先順位が高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置することを特徴とする検索装置。請求項2記載の検索装置において、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数が算出されておらず、かつ、前記データテーブルに前記検索キーを含む検索情報が格納されている場合、前記算出手段は、前記データテーブルから読み出した検索キーから前記複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの配置予定数を算出し、前記優先順位決定手段は、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの配置予定数を基に、配置予定数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定することを特徴とする検索装置。外部から入力された検索キーを複数の連想メモリに登録されている各エントリの検索キーと比較して一致したエントリの内容を検索結果として出力する検索装置の検索キー再配置方法において、前記検索キーから1つの連想メモリを識別するビット位置を示す複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの検索回数を算出し、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数を基に、検索回数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定し、前記優先順位が高い検索パターンと前記検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記検索キーを再配置することを特徴とする検索キー再配置方法。請求項4記載の検索キー再配置方法において、前記検索結果として出力されるエントリの内容で検索され前記検索キーを含む検索情報が格納されたデータテーブルを有し、前記優先順位が最も高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置するとき、前記複数の連想メモリのいずれかで連想メモリの格納数の上限値を超えた場合、次に優先順位が高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置することを特徴とする検索キー再配置方法。請求項5記載の検索キー再配置方法において、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数が算出されておらず、かつ、前記データテーブルに前記検索キーを含む検索情報が格納されている場合、前記データテーブルから読み出した検索キーから前記複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの配置予定数を算出し、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの配置予定数を基に、配置予定数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定することを特徴とする検索キー再配置方法。図3においては、検索要件つまり検索キーが多数であり単一のTCAMに格納できないために、複数のTCAM16-0~16-Nを設け、TCAM16-0~16-Nに全ての検索キーを格納している。この場合、検索に際して、検索キーを分類せずTCAM16-0~16-Nに格納した場合、全てのTCAMTCAM16-0~16-Nから該当の検索キーを検索する。このため、TCAM16-0~16-Nに順次検索を実施させる。この場合、一件の検索を実施するために最初のTCAM16-0に検索を要求してから、該当検索キーが格納されているTCAM16-iが検索応答を返すまでに、最悪の場合、最後のTCAM16-Nが検索応答を返すまでの時間が必要となるという問題があった。この場合の検索時間の概念図を図4と図5に示す。図4は異なる3つの検索キーで4つのTCAMを順次検索し、検索途中でヒットがなかった場合を示している。図5は異なる3つの検索キーで4つのTCAMを順次検索し、検索途中でヒットがあった場合を示している。このため、TCAMへの検索キーの配置を行う際に分類を行い、検索実行するTCAMを限定させることが考えられるが、検索キーを無作為に分類して配置したとしても、頻繁に検索を実施する検索キーが一部のTCAMに集中して配置された場合がある。図6に頻繁に検索を実施する3つの検索キーが同一のTCAMに配置された場合の検索の様子を示す。この場合、次検索の応答がTCAMから送られてくるまで次の検索要求をTCAMに発行できず、検索実施中に他の検索を行うことができないという問題があった。開示の検索装置は、検索を高速化でき検索処理可能数が向上することを目的とする。開示の一実施形態による検索装置は、外部から入力された検索キーを複数の連想メモリに登録されている各エントリの検索キーと比較して一致したエントリの内容を検索結果として出力する検索装置において、前記検索キーから1つの連想メモリを識別するビット位置を示す複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの検索回数を算出する算出手段と、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数を基に、検索回数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定する優先順位決定手段と、前記優先順位が高い検索パターンと前記検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記検索キーを再配置する再配置手段と、を有する。本実施形態によれば、検索を高速化することができ検索処理可能数が向上する。以下、図面に基づいて実施形態を説明する。<ルーティングテーブル検索装置の構成>図7にルーティングテーブル検索装置の一実施形態の構成図を示す。図7に示すルーティングテーブル検索装置24は図2におけるルーティングテーブル検索装置14に対応している。すなわち、ルーティングテーブル検索装置24はネットワークシステムを構成するスイッチ内のルーティングテーブル検索装置である。ルーティングテーブル検索装置24はデータテーブル25、TCAM26-0~16-N、検索制御部27、検索統計処理部28、検索統計テーブル29、検索パターンテーブル30を有している。データテーブル25はMAC学習テーブルであり、検索情報つまりMACアドレス、転送先ポート等を格納する。TCAM26-0~26-Nにはデータテーブルに対応したインデックスが格納される。検索制御部27は要求処理部31、応答処理部32、登録削除処理部33を有する。要求処理部31は検索キーデコード部31Aと検索キー再編集部31Bを有している。要求処理部31はプロセッサ13からの要求処理を受理し、配下の各TCAM26-0~26-Nの検索キーを作成して通知する。応答処理部32はTCAM26-0~26-Nからの検索結果として通知されるインデックスを受理し、データテーブル25から該当インデックスの検索情報を参照してプロセッサ13への応答を生成する。登録削除処理部33はプロセッサ13からの検索情報の登録/削除要求に基づきテータテーブル25及びTCAM26-0~26-Nからの検索情報の登録と削除を行う。検索統計テーブル29には、一定の期間中に各検索要件に対して実施された検索回数が検索パターン毎に格納される。また、検索パターンテーブル30には検索キーからインデックスを求める際のビットパターンが格納されている。検索統計処理部28は、一定の期間中に収集した検索回数の統計を基に、検索キーから検索パターンテーブル30を基に特定のビットを抽出して、検索要件を配置する際のTCAMを識別するためのTCAM番号とする。ビット抽出の際には統計の結果から検索される頻度つまり検索回数が各TCAM26-0~26-Nで可能な限り均一となるものを選択する。図8にTCAM26-0~26-Nそれぞれにおけるデータ構成の一実施形態を示す。TCAMには、検索キーとしての送信先MACアドレスと、検索結果としてのデータテーブル25のインデックスが、各エントリに配置される。図9にデータテーブル25におけるデータ構成の一実施形態を示す。データテーブル25には、送信先MACアドレスと、転送先ポートのポート番号、エントリの削除要否を示すダイナミック/スタティック情報、削除の際に削除対象かどうかの情報を示すエージングタイムが、各エントリに配置される。各エントリはインデックスを用いて参照される。図10に検索統計テーブル29におけるデータ構成の一実施形態を示す。検索統計テーブルには、検索パターン0~z毎にTCAM26-0~26-Nそれぞれの検索を実施した統計数である検索回数が配置される。図11に検索パターンテーブル30におけるデータ構成の一実施形態を示す。検索パターンテーブルには、検索パターン0~z毎に、検索キーつまり送信先MACアドレスからTCAM番号を決めるビット位置を示すインデックスビットが配置される。例えばインデックスビットは値1でTCAM番号を決めるビット位置を示し、検索キーが5ビット、TCAM番号が0~3であるとすると、インデックスビットは11000,01100,00110,00011,10100,10010,10001,01010,01001,00101などである。<保守時間を設けてTCAMへの要件配置を変更する場合>以下、検索処理動作について、スイッチにおけるMAC学習テーブルの処理を例として詳細に説明する。本実施形態では、MACアドレスの検索、登録、削除を行いながら、検索回数の統計処理を行う検索処理と、統計結果を分析して検索回数又は頻度が各TCAMで均一となるような検索パターンを選択してTCAMの格納情報を再配置する保守処理を、周期的に交互に繰り返す。これにより、各TCAM26-0~26-Nへの検索実施頻度の均一性を維持する。<検索処理>図2に示すようなスイッチは、パケットを受信すると、そのパケットの送信先MACアドレスからどのポートにパケットを転送すべきかを判定するため、送信先MACアドレスを検索キーとしてMAC学習テーブルつまりデータテーブル25の検索を行い、転送先ポートを求める。プロセッサ13は要求処理部31に対して受信したパケットの送信先MACアドレスを検索要求として発行する。要求処理部31は送信先MACアドレスを検索キーとしてTCAM26-0~26-Nに対して検索を実行する。その際に要求処理部31の検索キーデコード部31Aは検索パターンテーブル30から現在の運用中の検索パターン番号に従って、TCAMを識別するためのTCAM番号を決めるビット位置であるインデックスビットを抽出する。検索キー再編集部31Bは送信先MACアドレスからインデックスビットで指示されるビットを抽出し、抽出したビットでTCAM番号を決定し、決定したTCAM番号に該当するTCAMを検索キーである送信先MACアドレスで検索する。TCAM26-0~26-Nは検索キーの送信先MACアドレスが登録済みの場合、検索結果として、エントリありの情報とデータテーブル25の該当インデックスを応答処理部32に対して通知する。応答処理部32はTCAM26-0~26-Nより受理したインデックスを基にデータテーブル25の検索情報を読み出し、エージングタイムの情報を削除しないデータとして更新する。また、プロセッサ13にデータテーブル25から読み出した検索情報を転送し、検索統計処理部28に検索が行われたMACアドレスを通知する。検索統計処理部28は応答処理部32よりMACアドレスを受理すると、検索パターンテーブル30に登録されている全パターンについてインデックスビットを抽出し、該当するTCAMの検索回数を加算する。検索キーが未登録の場合、TCAMはエントリなしの情報を応答処理部32に対して通知する。応答処理部32はプロセッサ13に対して該当MACアドレスは未登録と通知する。図12に検索処理のフローチャートを示す。図12において、ステップS11でプロセッサ13は検索制御部27に対して検索要求を出す。ステップS12で要求処理部31は検索制御部27内の図示しないレジスタに保存されている運用中の検索パターン番号を取得し、当該運用中の検索パターン番号で検索パターンテーブル30を検索してTCAM番号を決めるビット位置つまりインデックスビットを取得する。ステップS13で要求処理部31は検索キーである送信先MACアドレスからTCAM番号を決めるビット位置を抽出し、抽出したビットから検索するTCAMを決定する。ステップS14で要求処理部31は該当TCAMに検索要求を実施する。ステップS15で該当TCAMは応答処理部32に検索結果を通知する。ステップS16で応答処理部32はTCAM検索がヒットしたか否かを判別する。ヒットした場合、ステップS17で応答処理部32はヒットしたTCAMエントリ内の結果つまりデータテーブルのインデックスを基に、データテーブル25の情報を収集し、収集した内容をプロセッサ13に通知する。ステップS18で応答処理部32は検索統計処理部28に検索キーと共に検索統計テーブル更新要求を通知する。この後、検索統計処理部28はステップS19~S23を、検索パターン番号iを0から1ずつインクリメントして検索パターンテーブル30の検索パターン数分だけ繰り返す。すなわち、ステップS20で検索統計処理部28は検索パターンテーブル30から検索パターン番号iについてのTCAM番号を決めるビット位置であるインデックスビットを取得する。ステップS21で検索統計処理部28は検索キーつまり送信先MACアドレスからTCAM番号を決めるビット位置を抽出し、統計情報更新対象のTCAM番号=Aを決定する。ステップS22で検索統計処理部28は検索統計テーブル29におけるの検索パターン番号iかつTCAM番号=Aに対応する検索回数に1を加算する。ステップS19~S23の繰り返し処理を終了すると、この処理を終了して通常処理に移行する。一方、ステップS16でTCAM検索がヒットしなかった場合、ステップS24で応答処理部32は検索要求した検索キーがTCAMに未登録であることをプロセッサ13に通知し、この処理を終了して登録処理に移行する。<登録処理>送信先MACアドレスを検索キーとして検索を行い、検索を行ったMACアドレスが検索システムに未登録であった場合、その送信先MACアドレスについてデータテーブル25つまりMAC学習テーブルへの登録処理を行う。プロセッサ13はMACアドレス未登録の通知を受理すると、検索制御部27の登録削除処理部33に対して送信先MACアドレス、転送先ポート、ダイナミック/スタティック情報を通知して登録要求を発行する。登録削除処理部33は登録要求を受理すると、データテーブル25にエントリを登録してダイナミック/スタティック情報がダイナミックの場合はエージングタイムを削除するデータ、スタティックの場合は削除しないデータとして更新する。また、送信先MACアドレスから現在の運用中の検索パターン番号に従ってインデックスビットを抽出し、登録を行うべきTCAMを判別し、送信先MACアドレスとデータテーブル25に登録したエントリのインデックスを該当TCAMに登録する。図13に登録処理のフローチャートを示す。図13において、ステップS31でプロセッサ13は登録削除処理部33に対して登録要求を実施する。ステップS32で登録削除処理部33は運用中のパターン番号を取得し、当該パターン番号で検索パターンテーブル30を検索してTCAM番号を決めるビット位置を取得する。ステップS33で登録削除処理部33は検索キーである送信先MACアドレスからTCAM番号を決めるビット位置を抽出し、検索するTCAMを決定する。ステップS34で登録削除処理部33は該当TCAMに空き領域が存在するかをチェックする。ステップS35の判断で空き領域が存在する場合は、ステップS36で登録削除処理部33は登録要求データを該当TCAM及びデータテーブル25に登録する。そして、ステップS37で登録削除処理部33はプロセッサ13に正常終了を通知する。一方、ステップS35の判断で空き領域が存在しない場合は、ステップS38で登録削除処理部33はプロセッサ13に異常終了を通知する。ステップS37又はS38の実行後、この処理を終了して通常処理に移行する。<削除処理>システムに登録された送信先MACアドレスが一定期間検索されない場合、そのMACアドレスについてMAC学習テーブルであるデータテーブル25からの削除処理を行う。一般的なスイッチの場合、例えば300秒程度の期間、検索が行われない場合は削除を行う。プロセッサ13は周期的に登録削除処理部33に削除要求を発行する。登録削除処理部33はデータテーブル25の各エントリのダイナミック/スタティック情報を参照し、スタティックの場合は何も行わない、ダイナミックの場合はエージングタイムを参照して削除しないデータであればエージングタイムを削除するデータに更新する。削除するデータであればデータテーブル25から該当のエントリを削除して、そのエントリの送信先MACアドレスから運用中の検索パターン番号のインデックスビットを抽出し、削除を行うべきTCAM番号を決定し、該当するTCAMから該当するエントリの削除を行う。図14に削除処理のフローチャートを示す。図14において、ステップS41でプロセッサ13は登録削除処理部33に対して削除要求を実施する。ステップS42で登録削除処理部33は運用中の検索パターン番号を取得し、当該パターン番号で検索パターンテーブル30を検索してTCAM配置の決定に用いているビット位置を取得する。ステップS43で登録削除処理部33は削除する検索キーである送信先MACアドレスからTCAM番号を決めるビット位置を抽出し、検索するTCAMを決定する。ステップS44で登録削除処理部33は該当TCAMを検索し、削除データが登録されているエントリを特定する。ステップS45で登録削除処理部33はヒットしたTCAMエントリ内の結果であるデータテーブルのインデックスを基に、データテーブル25のエントリを特定する。ステップS46で登録削除処理部33は該当TCAM及びデータテーブルを空き状態に設定する。ステップS47で登録削除処理部33はプロセッサ13に正常終了を通知し、この処理を終了して通常処理に移行する。<保守処理>保守処理とは、それまで運用で取得された統計結果を分析して検索頻度が各TCAMで均一となるような検索パターンを選択し、TCAMの格納情報を再配置する処理のことである。図15に保守処理全体のフローチャートを示す。図15において、ステップS51で検索統計処理部28は現在時刻が保守開始時間であるか否かを判別する。保守開始時間であれば、ステップS52で検索統計処理部28は検索統計テーブル29に統計分析結果があるか否かを判別し、統計分析結果があればステップS53で検索統計処理部28は保守処理統計分析を実行する。その後、ステップS54で検索統計処理部28は保守処理再配置1を実行する。一方、例えば初期状態などで、ステップS52において統計分析結果がないと判別された場合、ステップS55で検索統計処理部28はデータテーブル25に検索情報が登録されているか否かを判別する。そして、データテーブル25に検索情報が登録されている場合、ステップS56で検索統計処理部28は保守処理再配置2を実行する。データテーブル25に検索情報が登録されていない場合、ステップS57で検索統計処理部28は保守処理再配置3を実行する。ステップS54,S56,S57を実行すると、この処理を終了して通常処理に移行する。<保守処理統計分析>検索回数の統計情報を基に、現状のデータテーブル25のエントリをどのTCAMに配置すべきかを、検索パターンテーブル30に登録されている検索パターンから選択する。このために、検索検索統計処理部28は検索統計テーブル29から各検索パターンにおけるTCAMの検索回数を読み込む。図16Aに説明のため、検索キーを5ビット、TCAMを4つの検索パターンとした場合の例を示す。図中、各行で左端に示す検索キーにおいて梨地で示すブロックは検索パターンテーブル30に登録されているインデックスビットTCAM番号を決めるビット位置を示す。例えば検索パターン0では最上位の第5ビットと第4ビットがインデックスビットである。検索キーの右側には検索統計テーブル29から読み出した各TCAMの検索回数を示している。検索検索統計処理部28は各検索パターン別の統計情報を読み込んで、各検索パターンでの各TCAMの検索回数のうち最小数を求める。なお、最小数が複数ある場合、TCAM番号の若番の値を選択する。図16Bに選択した最小数をアンダーバーで示す。最少数が求められたら、検索パターン毎に各TCAMの検索回数からその最小数を減算し、減算後の各TCAMの検索回数を全て合計する。図16Cに検索パターン毎の合計値SUMを欄外に示す。この後、その検索パターンで振り分けを行った場合に、各TCAMの格納数上限を超過しないという条件を満たし、かつ、検索パターン毎の合計値SUMが最小のパターンを最適なパターンとして選択する。合計値SUMが最小の検索パターンは各TCAMの検索回数が最も均一化された検索パターンである。これによって、図16A,Cに実線で囲って示す第2行の検索パターンが、各TCAMの検索回数が最も均一であり最適なパターンつまり再配置検索パターンとして選択される。図17に保守処理統計分析のフローチャートを示す。この処理では、検索統計テーブルの情報から最も均一化されたTCAMの再配置検索パターンを算出する。また、再配置検索パターンの中で優先順位を決定する。図17において、検索統計処理部28はステップS61~S69を、検索パターン番号iを0から1ずつインクリメントして検索パターンテーブル30の検索パターン数分だけ繰り返す。ステップS62で検索統計処理部28は検索回数最小値=Bを初期化する。次に、検索統計処理部28はステップS63~S67を、TCAM番号Jを0から1ずつインクリメントしてTCAM数分だけ繰り返す。ステップS64で検索統計処理部28は検索統計テーブル29から検索パターン番号iかつTCAM番号jの検索回数=Aを取得する。ステップS65で検索統計処理部28は検索回数最小値=Bが検索回数=Aを超えるか否かを判別し、A<Bの場合にのみステップS66で検索回数=Aを検索回数最小値=Bに設定し検索回数最小値Bを更新する。ステップS68で検索統計処理部28は検索回数の均一性の指標値=Cを算出する。検索頻度の指標値算出方法としては、次式に示すように、検索パターン毎に各TCAMの検索回数=Aと検索回数最小値=Bとの差分を求めて、差分を合計する。C_pattern=ΣA_tcam-B_patternここで、C_patternは各検索パターンの指標値、A_tcamは検索パターン内の各TCAM検索回数、B_patternは検索パターン内の各TCAM検索回数の最小値である。ステップS70で検索統計処理部28は各検索パターンの指標値=Cを比較して検索パターンの優先順を決定する。この場合、C_patternが最小である検索パターンが最も均一化された再配置検索パターンである。検索パターンの優先順位をC_patternが小さい順に決定する。なお、C_patternが同値の場合は若番の検索パターンを優先する。<保守処理再配置1>再配置検索パターンとして選択した検索パターンに従い、TCAMに登録されているデータを再配置する。まず、検索検索統計処理部28より全てのTCAMの登録データを全てクリアする。クリア実施後、検索検索統計処理部28での統計分析結果から選択された再配置検索パターンに従い、データテーブル25から順次MACアドレスを読み出して、MACアドレスから該当検索パターンのインデックスビットに示されるビットを取得して再配置を行うべきTCAM番号を判別する。そして、該当するTCAMにデータテーブル25から読み出したMACアドレスと該当エントリのインデックスの登録を行い、全てのエントリの登録完了後に検索統計テーブル29の統計情報をクリアし、検索処理に移行する。なお、上記再配置中にどれか一つのTCSMでも、TCAMの格納数上限値を超えた場合は、例えば図16Cにおいて次に合計値SUMが小さい検索パターンを再配置検索パターンに採用して再配置処理を実施する。図18に保守処理再配置1のフローチャートを示す。この処理では、統計分析で得られた再配置検索パターンを基にTCAMの再配置を行う。また、このTCAMの再配置を行った再配置検索パターンを運用中の検索パターン番号として検索制御部27内のレジスタに保存する。図18において、ステップS71で検索統計処理部28はTCAM格納データをクリアする。ステップS72で検索統計処理部28は統計分析で得られた最優先の再配置検索パターンを取得し、最優先の再配置検索パターンの検索パターンで検索パターンテーブル30からTCAM番号を決めるビット位置つまりインデックスビットを取得する。検索統計処理部28はステップS73~S78を、データテーブル25のエントリ番号iを0から1ずつインクリメントしてデータテーブル25のエントリ数分だけ繰り返す。ステップS74で検索統計処理部28はデータテーブル25のエントリ番号iから検索キーであるMACアドレスを取得する。ステップS75で検索統計処理部28は取得したMACアドレスからTCAM番号を決めるビット位置つまりインデックスビットで指示されるビットを抽出し、抽出したビットで再配置するTCAM番号を決定する。ステップS76で検索統計処理部28は該当TCAMにデータテーブル25から読み出したMACアドレスと該当エントリのインデックスを登録して再配置する。ステップS77で検索統計処理部28は格納数上限値を超過しているTCAMがあるか否かを判別する。格納数上限値を超過しているTCAMがなければステップS78に進み、格納数上限値を超過しているTCAMがあれば、ステップS80で検索統計処理部28は次の優先順位の検索パターンがあるか否かを判別する。次の優先順位の検索パターンがなければステップS79に進み、ある場合はステップS81に進む。ステップS81で検索統計処理部28はTCAM格納データをクリアする。次に、ステップS82で検索統計処理部28は次の優先順位の検索パターンを取得し、取得した検索パターンを再配置検索パターンとし、再配置検索パターンで検索パターンテーブル30からTCAM番号を決めるビット位置つまりインデックスビットを取得してステップS73に進む。ステップS73~S78の繰り返しを終了した場合、又は、ステップS80で次の優先順位の検索パターンがない場合は、ステップS79で検索統計処理部28は検索統計テーブル29を初期化すると共に、TCAMの再配置を行った再配置検索パターンを検索制御部27内の図示しないレジスタに保存することで運用中の検索パターン番号に設定して、この処理を終了して通常処理に移行する。<保守処理再配置2>検索システムが最初に立ち上がった場合等は検索の統計情報が計上されていない。その際はデータテーブル25の登録状況により初期配置を行う必要がある。データテーブル25には登録されているが、TCAM26-0~26-Nには登録されてない場合について、説明する。データテーブル25にエントリ自体は配置されているが、検索統計テーブル29に統計情報がないような状態では、TCAM26-0~26-Nに登録する検索パターンを統計情報によらず選択する必要がある。その場合、検索パターン選択の条件を検索回数ではなく、各TCAMに登録されるエントリ数で判断し、各TCAMのエントリ数が可能な限り均一に配置されるような検索パターンを選択する。処理手順としては、1データテーブルから順次MACアドレスを読み出して、検索パターンテーブル30の全ての検索パターンに従ってインデックスビットを抽出し、各TCAMに配置される配置予定数をそれぞれ求める。2全ての検索パターンについて配置する配置予定数の算出が終わったら、パターン毎に配置されるTCAMの配置予定数の最小数を求める。3最小数が求められたら、各TCAMの配置予定数からその最小数を減算し、その値を全て合計する。4全ての検索パターンについて合計値を求め、TCAMの配置条件に到達していないもののうち、一番合計数が少ない検索パターンを再配置検索パターンとして選択する。図19に、検索統計テーブル29に統計分析情報がなく、かつ、データテーブル25に登録がある場合における保守処理再配置2のフローチャートを示す。この処理では、データテーブル25の検索キーであるMACアドレスと、検索パターンテーブル30の情報を基に、最も配置予定数が均一化される検索パターンを再配置検索パターンに採用して再配置処理を実施する。図19において、ステップS90で検索統計処理部28はTCAM格納データをクリアする。検索統計処理部28はステップS91~S98を、データテーブル25のエントリ番号iを0から1ずつインクリメントしてデータテーブル25のエントリ数分だけ繰り返し、かつ、ステップS93~S97を、検索パターン番号jを0から1ずつインクリメントして検索パターンテーブル30の検索パターン数分だけ繰り返す。これにより、データテーブル25の情報と検索パターンテーブル30の情報を基に、各検索パターンにおける各TCAMの配置予定数を算出する。このため、ステップS92で検索統計処理部28はデータテーブル25のエントリ番号iから検索キーであるMACアドレスを取得する。ステップS94で検索統計処理部28は検索パターンテーブル30の検索パターン番号jからTCAM番号を決めるビット位置つまりインデックスビットを取得する。ステップS95で検索統計処理部28はMACアドレスから該当検索パターンのインデックスビットに示されるビットを取得して配置候補のTCAM番号kを決定する。そして、ステップS96で検索統計処理部28は検索統計テーブル29の検索パターン番号jかつTCAM番号kの配置予定数=Aを1だけインクリメントする。ここでは、配置予定数=Aを管理するために検索統計テーブル29を流用している。次に、ステップS100で検索統計処理部28は図17に示す保守処理統計分析を実行する。ここでは、検索統計テーブル29に登録されている各検索パターンにおける各TCAMの配置予定数を検索回数とみなし各検索パターンの中で優先順位を決定し、最も配置予定数が均一化された検索パターンを再配置検索パターンとする次に、ステップS110で検索統計処理部28は図18に示す保守処理再配置1を実行する。ここでは、ステップS100の保守処理統計分析で得られた再配置検索パターンを基にTCAMの再配置を行う。<保守処理再配置3>MAC学習テーブルとしてのデータテーブル25に何も登録されていない状態で初期化を行う場合は、検索パターンテーブル30の特定の検索パターン番号、例えば若番を運用中の検索パターン番号として選択し、通常処理に移行する。図20にデータテーブル25に登録がなく、かつ、検索パターンテーブル30に統計分析情報がない場合における保守処理再配置3のフローチャートを示す。図20において、ステップS121で検索統計処理部28はTCAM格納データをクリアする。ステップS122で検索統計処理部28は検索パターン番号=0を検索制御部27内の図示しないレジスタに保存することで運用中の検索パターン番号に設定し、検索パターンテーブル30から検索パターン番号=0のTCAM番号を決めるビット位置つまりインデックスビットを取得する。その後、この処理を終了して通常処理に移行する。<検索時間の閑散期にTCAMへの要件配置を変更する場合>検索処理が常時輻輳しているわけではなく、ある程度閑散となる期間がある場合、TCAM26-0~26-Nを使った検索処理から、データテーブル25を直接順次検索してTCAM26-0~26-Nの検索を行わないようにし、その間にTCAM26-0~26-Nのデータ再配置を行うことで保守処理中にも検索処理が可能となる。検索処理の閑散期を求めるため、検索統計データテーブル29について検索パターン毎のTCAM別検索回数統計の他に、新たに図21に示す時刻統計テーブルを用いて、時刻別検索実行回数の統計を追加し、その情報を基に保守期間を判断する。図21では、例えば数分から数10分程度のタイムスロット毎に検索回数が格納される。一定周期数分から数10分程度毎に時刻別の検索実行回数の統計をサンプリングし、その周期内で最も検索実行回数が少なかった時間帯を閑散期として次周期の保守処理実行時間とする。図22に時刻統計のサンプリングと保守処理開始時刻の様子を示す。例えば統計周期を1日、統計周期の開始、終了時刻図中では基準時刻と記載を0:00として、サンプリング単位を1時間とした場合、周期のタイムスロット数は24スロットとなる。現基準時刻になった際に、前基準時刻から現基準時刻までにサンプリングした検索実行回数の統計を解析し、最も検索実行回数が少なかった時間帯を現基準時刻から次基準時刻の間に保守処理を実行する時間帯とする。解析終了後は時刻別統計をクリアして、新たに統計のサンプリングを開始する。<保守処理期間中の検索処理>保守処理期間中の検索処理は、保守処理と同時に検索を実行するため、TCAM26-0~26-Nの検索処理を行わず、データテーブル25に格納されているデータを直接参照して検索キーが一致するエントリを順次調査する。また、保守処理期間中はTCAM別の検索回数統計情報の計上を行わない。図23に保守処理期間を含む検索処理のフローチャートを示す。図23において、ステップS131でプロセッサ13は検索制御部27に対して検索要求を出す。ステップS132で要求処理部31は保守処理期間中つまり保守時間中であるか否かを判別する。保守処理期間中であればステップS133に進み、保守処理期間中でなければステップS138に進んで、図12に示す検索処理を実行する。保守処理期間中はステップS133で要求処理部31は直接データテーブル25を若番のエントリから順次参照し、プロセッサ13から受け取った送信先MACアドレスが一致するエントリの有無を調査する。そして、ステップS134で要求処理部31は応答処理部32に検索結果を通知する。ステップS135で要求処理部31は検索結果から一致するエントリの有無を判別する。一致するエントリがあった場合、ステップS134で要求処理部31はエントリありの情報とデータテーブル25の該当エントリ番号インデックスを応答処理部32に通知しているので、応答処理部32はステップS136で要求処理部31より受理した通知を基にデータテーブル25の情報を読み出し、エージングタイムの情報を削除しないデータとして更新し、プロセッサ13にデータテーブルの情報を転送する。一致するエントリがない場合、要求処理部31はステップS134でエントリなしの情報を応答処理部32に通知しているので、ステップS137で応答処理部32はプロセッサ13に対して該当MACアドレスは未登録と通知する。上記のステップS136,S137,S138の実行後、この処理を終了して通常処理に移行する。<保守処理期間中の登録削除処理>保守処理期間中に登録削除処理部34は登録要求を受理すると、データテーブル25にエントリを登録し、ダイナミック/スタティック情報がダイナミックの場合はエージングタイムを削除するデータとし、スタティックの場合は削除しないデータとして更新する。TCAM26-0~26-Nへの登録は保守処理の再配置により行う。なお、保守処理期間中は図14に示す削除処理を実行しない。保守処理期間中の保守処理は図15に示す保守処理全体の処理と同様である。上記の実施形態では、複数のTCAMの検索が均一になるように、検索キーを複数のTCAMに再配置しているため、1つの検索実行で複数のTCAMへのアクセスが必要でなくなり、処理負荷の軽減及び検索時間の短縮つまり検索の高速化が可能となる。図24に頻繁に検索を実施する3つの検索キーが別のTCAMに配置されている場合の検索の様子を示す。また、1つの検索実行中に他のTCAMは未アクセスの状態になるため、次の検索要求を受け付けた際に未アクセスのTCAMに対する検索が可能となり、検索処理輻輳時の検索処理可能数が向上する。更に、特定のTCAMへのアクセスが続くワーストケースの場合に比べ、約30の性能向上を見込むことができる。なお、上記実施形態ではTCAMを用いてルーティングテーブル検索装置24を構成しているが、TCAMに限らずBCAMBinaryContentAddressableMemoryなどの他種の連想メモリを用いるものであっても良い。付記1外部から入力された検索キーを複数の連想メモリに登録されている各エントリの検索キーと比較して一致したエントリの内容を検索結果として出力する検索装置において、前記検索キーから1つの連想メモリを識別するビット位置を示す複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの検索回数を算出する算出手段と、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数を基に、検索回数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定する優先順位決定手段と、前記優先順位が高い検索パターンと前記検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記検索キーを再配置する再配置手段と、を有することを特徴とする検索装置。付記2付記1記載の検索装置において、前記検索結果として出力されるエントリの内容で検索され前記検索キーを含む検索情報が格納されたデータテーブルを有し、前記再配置手段は、前記優先順位が最も高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置するとき、前記複数の連想メモリのいずれかで連想メモリの格納数の上限値を超えた場合、次に優先順位が高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置することを特徴とする検索装置。付記3付記2記載の検索装置において、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数が算出されておらず、かつ、前記データテーブルに前記検索キーを含む検索情報が格納されている場合、前記算出手段は、前記データテーブルから読み出した検索キーから前記複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの配置予定数を算出し、前記優先順位決定手段は、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの配置予定数を基に、配置予定数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定することを特徴とする検索装置。付記4付記1乃至3のいずれか1項記載の検索装置において、前記算出手段は、前記複数の検索パターンを保持する検索パターンテーブルと、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数又は配置予定数を保持する検索統計テーブルと、を有することを特徴とする検索装置。付記5外部から入力された検索キーを複数の連想メモリに登録されている各エントリの検索キーと比較して一致したエントリの内容を検索結果として出力する検索装置の検索キー再配置方法において、前記検索キーから1つの連想メモリを識別するビット位置を示す複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの検索回数を算出し、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数を基に、検索回数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定し、前記優先順位が高い検索パターンと前記検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記検索キーを再配置することを特徴とする検索キー再配置方法。付記6付記5記載の検索キー再配置方法において、前記検索結果として出力されるエントリの内容で検索され前記検索キーを含む検索情報が格納されたデータテーブルを有し、前記優先順位が最も高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置するとき、前記複数の連想メモリのいずれかで連想メモリの格納数の上限値を超えた場合、次に優先順位が高い検索パターンと前記データテーブルから読み出した検索キーを用いて前記複数の連想メモリから識別した連想メモリに前記データテーブルから読み出した検索キーを再配置することを特徴とする検索キー再配置方法。付記7付記6記載の検索キー再配置方法において、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの検索回数が算出されておらず、かつ、前記データテーブルに前記検索キーを含む検索情報が格納されている場合、前記データテーブルから読み出した検索キーから前記複数の検索パターンそれぞれについて前記複数の連想メモリそれぞれの配置予定数を算出し、前記複数の検索パターン毎の前記複数の連想メモリそれぞれの配置予定数を基に、配置予定数が前記複数の連想メモリで均一となる順に前記複数の検索パターンの優先順位を決定することを特徴とする検索キー再配置方法。"