非同期動作検索回路
【課題】低消費電力でかつ高性能に検索できる。
【解決手段】本実施形態に係る非同期検索回路は、パケットの通過を許可するか否かを判定する検索種別に対応した複数のルール情報のうち第１ルール情報と、受信したパケットに関する情報とを比較する比較部であり、比較部は複数かつ比較部ごとに受信したパケットが異なり、比較部ごとに、複数の比較部で共通する第１ルール情報を受信した場合、比較部に比較処理をさせるように制御し、第１ルール情報とパケットに関する情報との比較が完了した場合又はパケットを受信しなかった場合に処理が完了したことを示す第２信号を生成する比較回路制御部と、複数の比較部からの全ての第２信号を受信した場合、第１ルール情報と異なる第２ルール情報を読み出し、第２ルール情報を複数の比較部に送信する読出し部とを具備し、比較回路制御部は、前記複数のルール情報を全て受信するまで順次比較処理させて第２信号を生成する。
【解決手段】本実施形態に係る非同期検索回路は、パケットの通過を許可するか否かを判定する検索種別に対応した複数のルール情報のうち第１ルール情報と、受信したパケットに関する情報とを比較する比較部であり、比較部は複数かつ比較部ごとに受信したパケットが異なり、比較部ごとに、複数の比較部で共通する第１ルール情報を受信した場合、比較部に比較処理をさせるように制御し、第１ルール情報とパケットに関する情報との比較が完了した場合又はパケットを受信しなかった場合に処理が完了したことを示す第２信号を生成する比較回路制御部と、複数の比較部からの全ての第２信号を受信した場合、第１ルール情報と異なる第２ルール情報を読み出し、第２ルール情報を複数の比較部に送信する読出し部とを具備し、比較回路制御部は、前記複数のルール情報を全て受信するまで順次比較処理させて第２信号を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えばＩＰ（Internet Protocol）網で使用されるルータ等のように、パケットフィルタリング機能を用いたパケットの転送処理に用いる非同期動作検索回路に関する。
【背景技術】
【０００２】
近年、インターネットに代表されるＩＰ網の利用拡大に伴い、企業および家庭内にＬＡＮ（Local Area Network）を構築し、このＬＡＮをインターネット等を介して外部のネットワークに接続させ、パケット転送を行うことが多い。しかし、ＬＡＮに収容された端末を外部のネットワークに接続すると、外部のネットワークからの不正アクセスにより、個人情報等の機密情報の漏えいまたは改竄が発生するおそれがあるため、ＬＡＮ内部のセキュリティの確保が重要な課題となる。
そこで従来では、ＬＡＮと外部ネットワークとの間でパケットを中継転送するルータなどのパケット転送処理装置に、パケットフィルタリング機能を持たせるようにしている。パケットフィルタリング機能は、受信されたパケットを予め設定されているルール情報と比較することにより、上記パケットの通過を許可するか否かを判定する。ルール情報は、パケット転送に使用される通信パラメータにより定義され、例えば、送信元アドレス、宛先アドレス、プロトコル、送信元ポート番号及び宛先ポート番号などがある。パケットフィルタリング処理の性能は、ルール情報の数の増加に伴って低下するため、ルール情報と受信パケットとの比較処理回路を並列化し、性能向上を狙う回路構成が存在する（例えば、非特許文献１参照）。
【０００３】
ところが、ルールの読み出し処理や比較処理回路は同期して動作する必要があり、通常はクロック信号に同期して動作する。このクロックは、動作タイミングをそろえるために回路に供給され、データ処理に対して直接関与しない。それにも関わらず、クロック信号は、ＬＳＩチップ全体に供給されるため、大きく電力を消費する。例えば、受信パケットが入力されておらず、処理としてはアイドル状態にも関わらず、クロックがＬＳＩ全体に供給されるために電力が大きく消費されてしまう。
【０００４】
そこで、電力消費を削減する観点から、クロック信号を用いずに、処理段ごとに送信信号（ｓｅｎｄ信号）と応答信号（ａｃｋ信号）とのハンドシェイクにより処理を進める非同期回路の適用が考えられる。非同期回路は、クロック信号が不要であり、さらにデータ入力されない場合は、制御回路間のハンドシェイクも発生しないので、電力消費を大きく削減することができる。
さらに、ＬＳＩ製造技術の微細化により、リーク電流に起因する静的消費電力の増加が問題となっているが、非同期回路は、制御部のハンドシェイクにより処理を行っている処理段において有効なデータが存在しているか否かを知ることが容易である。従って、有効なデータが存在しない場合、処理段の電源を遮断するいわゆるパワーゲーティングを容易に実現することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】西田享邦，川合健治，小池恵一，大山勝一，“１Ｇｂｉｔ／ｓホームルータ用ＬＳＩの開発”，信学技報，ＩＣＤ２００７−５８，ｐｐ．１２３−１２８，Ｊｕｌ．２００７
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非同期回路の場合、受信パケット情報とルール情報との比較処理の完了時間が比較回路ごとに異なる。そのため、複数の比較回路にルール情報を同時に送信すると、まだ比較処理が終了していない比較回路では、処理が間に合わず誤動作することがある。加えて、パケットフィルタリング処理では、１つの受信パケット情報と複数のルール情報との比較を行う必要があるが、受信パケット情報の受け入れ制御を行う制御部において、すべてのルール情報の比較が終了したことを検知できない。よって、すべてのルール情報との比較が終了する前に検索結果を出力して、次の受信パケット情報の受信を開始してしまい、正しく検索ができない可能性がある。
【０００７】
この発明は上記事情に着目してなされたもので、その目的とするところは、低消費電力でかつ高性能に検索することができる非同期動作検索回路を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するためにこの発明の一つの観点は、パケットの通過を許可するか否かを判定する検索種別に対応した複数のルール情報のうちの第１ルール情報と、受信したパケットに関する情報とを比較する比較部を具備し、前記比較部は複数あり、比較部ごとに受信したパケットが異なり、比較部ごとに、複数の比較部で共通する前記第１ルール情報を受信した場合、前記比較部に比較処理をさせるように制御し、該第１ルール情報とパケットに関する情報との比較が完了した場合または該パケットを受信しなかった場合にも処理が完了したことを示す第２信号を生成する比較回路制御部と、前記複数の比較部からの全ての第２信号を受信した場合、前記第１ルール情報とは異なる第２ルール情報を読み出し、該第２ルール情報を前記複数の比較部に送信する読出し部と、をさらに具備し、前記比較回路制御部は、前記複数のルール情報を全て受信するまで前記比較部に順次前記比較処理を行わせ、前記第２信号を生成することを特徴とする。
【発明の効果】
【０００９】
すなわちこの発明によれば、低消費電力でかつ高性能に検索することができる。
【図面の簡単な説明】
【００１０】
【図１】本実施形態に係る非同期動作検索回路を含むパケット処理回路を示すブロック図。
【図２】本実施形態に係る検索部を示すブロック図。
【図３】本実施形態に係る比較回路を示すブロック図。
【図４】比較回路の動作の一例を示すタイミングチャート。
【図５】本実施形態に係る比較部を示すブロック図。
【図６】本実施形態に係るルール読み出し部を示すブロック図。
【図７】ルール読出し部の状態遷移の一例を示す図。
【図８】一般的なＣ素子を用いた非同期回路のタイミングチャート。
【発明を実施するための形態】
【００１１】
以下、図面を参照しながら本発明の実施形態に係る非同期動作検索回路について詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
本実施形態に係る非同期検索回路を含むパケット処理回路１００について図１を参照して説明する。
パケット処理回路１００は、ネットワークインターフェース１０１，１０８、パーサ１０２、フレームコントローラ１０３、バッファメモリ１０４、非同期検索回路１０５、ＱｏＳ（Quality of Service）部１０６およびフレーム生成部１０７を含む。
【００１２】
ネットワークインターフェース１０１，１０８は、ＷＡＮ（Wide Area Network）またはＬＡＮとのインターフェースである。ネットワークインターフェース１０１は、ＷＡＮまたはＬＡＮからパケットデータを受信する。ネットワークインターフェース１０８は、後述するフレーム生成部１０７からパケットデータを受信して、ＷＡＮまたはＬＡＮに送信する。
パーサ１０２は、ネットワークインターフェース１０１からパケットデータを受け取り、受信パケット情報を抽出する。受信パケット情報は、ＩＰアドレスまたはポート番号といった、後述の非同期検索回路１０５における比較処理で必要とされるパケットに関する情報である。
フレームコントローラ１０３は、パーサ１０２からパケットデータを受け取り、バッファメモリ１０４に格納するように制御する。
【００１３】
バッファメモリ１０４は、フレームコントローラ１０３からパケットデータを受け取り、パケットデータを格納する。
非同期検索回路１０５は、パーサ１０２から受信パケット情報を受け取り、受信パケット情報と様々なルール情報とを比較する。ルール情報は、ルール番号、優先度値および比較情報を含む。ルール番号は、例えば後述するルール蓄積部２０７に蓄積されたルール情報のアドレスのような、ルール情報を識別するＩＤである。優先度値は、受信パケット情報とルールとが一致する場合に、どれほど優先して適用されるかを示す。ここでは、優先度が高いほど値が小さいとする。比較情報は、受信パケット情報と比較するための情報であって、それぞれの検索種別に対応してパケットの通過を許可するか否かを判定する情報である。例えば、経路検索であれば送信元アドレス、宛先アドレスなどの情報である。非同期検索回路１０５は、パケットデータの廃棄／通過、出力インターフェースの決定、通信品質クラス分けといった受信したパケットデータの取り扱いを決定する。なお、ルール情報は、非同期検索回路１０５内部に予め格納されていてもよいし、外部のルール情報蓄積部（図示せず）から比較処理のたびにルール情報を抽出して比較してもよい。非同期検索回路１０５の詳細については、図３を参照して後述する。
【００１４】
ＱｏＳ部１０６は、非同期検索回路１０５からルール情報と比較された受信パケット情報を受け取る。取り扱いが廃棄の場合、フレームコントローラ１０３にパケットデータを廃棄するように廃棄要求を送り、バッファメモリ１０４において当該パケットが使用していたバッファ領域を解放する。取り扱いが通過の場合、決定された通信品質クラスに従い、キューイングされ、指定されたパケット送信タイミングでフレーム生成部１０７に送信要求を送る。
【００１５】
フレーム生成部１０７は、ＱｏＳ部１０６から送信要求と、ルール情報と比較された受信パケット情報とを受け取り、パケットデータの読み出しをフレームコントローラ１０３に要求する。フレーム生成部１０７は、フレームコントローラ１０３を介してバッファメモリ１０４から当該パケットデータを受け取るとともに、非同期検索回路１０５においてルール情報と比較された受信パケット情報に基づき、ＭＡＣアドレスの書き換えや、ＩＰアドレスの書き換え等を行い、非同期検索回路１０５において決定されたインターフェースにパケットを送る。
【００１６】
次に、本実施形態に係る非同期検索回路１０５について図２のブロック図を参照して説明する。
本実施形態に係る非同期検索回路１０５は、受信パケット情報振分け部２０１、比較回路２０２、第１ルール読出し回路２０３−１、第２ルール読出し回路２０３−２、第３ルール読出し回路２０３−３、結果出力部２０４、第１検索結果蓄積部２０５−１、第２検索結果蓄積部２０５−２および第３検索結果蓄積部２０５−３を含む。さらに、第１ルール読出し回路２０３−１は、第１ルール読出し部２０６−１および第１ルール蓄積部２０７−１を含む。同様に、第２ルール読出し回路２０３−２は、第２ルール読出し部２０６−２および第１ルール蓄積部２０７−２を含み、第３ルール読出し回路２０３−３は、第２ルール読出し部２０６−３および第１ルール蓄積部２０７−３を含む。
【００１７】
以下便宜上、第１ルール読出し回路２０３−１および４個の比較回路２０２を第１ステージと呼び、第２ルール読出し回路２０３−２および４個の比較回路２０２を第２ステージと呼び、第３ルール読出し回路２０３−３および４個の比較回路２０２を第３ステージと呼ぶ。本実施形態では、各ステージにおいて比較回路２０２を４個並列させ、第１ステージから第３ステージまでの３段階の並列処理を行う例を示すが、これに限らず、１つのステージで並列させる比較回路の数およびステージ数は、いくつでもよい。このように比較回路を並列させることで、比較回路ごとに読出し回路を接続させずに、各ステージで１つの読出し回路が存在すればよく、回路規模を縮小させることができる。さらに各比較回路に、それぞれ別の受信パケット情報が入力され処理されるので、並列処理によりパフォーマンスを向上させることができる。
本実施形態に係る３つのステージの処理は、例えば、第１ステージにおいて論理インターフェースとＮＡＴ（Network Address Translation）検索を行い、第２ステージにおいて経路検索を行い、第３ステージにおいてパケット検索を行うことを想定する。しかし、これに限らず、各ステージにおいてどのような検索を行ってもよい。
【００１８】
受信パケット情報振分け部２０１は、パーサ１０２から受信した受信パケット情報を、比較処理が実行されていない、すなわち、受信パケット情報ａｃｋ信号を送信している第１ステージの比較回路に、受信パケット情報と受信パケット情報ｓｅｎｄ信号とを送信する。受信パケット情報ａｃｋ信号は、受信パケット情報と全てのルール情報との比較が終了したか否かを示す信号である。受信パケット情報ｓｅｎｄ信号は、受信パケット情報を送信したか否かを示す信号である。なお、受信パケット情報ｓｅｎｄ信号と受信パケット情報ａｃｋ信号とは１ビットの信号とするが、何ビットの信号を用いてもよい。
【００１９】
第１ステージの比較回路２０２は、受信パケット情報振分け部２０１から受信パケット情報ｓｅｎｄ信号と受信パケット情報とを受け取り、ルール読出し回路２０３−１からルール情報とルール情報ｓｅｎｄ信号とを受け取る。ルール情報ｓｅｎｄ信号は、ルール情報を送信したか否かを示す信号である。比較回路２０２は、受信パケット情報とルール情報との比較を行う。また、比較回路２０２は、ルール蓄積部２０７に蓄積されるルール情報と受信パケット情報とを比較し、第１ルール読出し回路２０３−１にルール情報ａｃｋ信号を送る。ルール情報ａｃｋ信号は、受信パケット情報と１つのルール情報との比較処理が完了したか否かを示す信号である。
ルール蓄積部２０７−１に蓄積されるすべてのルール情報について、受信パケット情報とルール情報とが一致したルール番号の中で最も優先度が高いルール番号（優先ルール番号）を決定する。全てのルールと比較処理が完了した場合は、受信パケット情報振分け部２０１に受信パケット情報ａｃｋ信号を送信する。なお、ルール情報ｓｅｎｄ信号とルール情報ａｃｋ信号とは１ビットの信号とするが、何ビットの信号を用いてもよい。
【００２０】
第２ステージの比較回路２０２−２は、第２ステージにおいて比較処理が完了している場合は、第１ステージの比較回路２０２−１へ受信パケット情報ａｃｋ信号を送り、第２ルール読出し回路２０３−２へルール情報ａｃｋ信号を送る。その後、第２ステージの比較回路２０２−２は、第１ステージの比較回路２０２−１から受信パケット情報とパケット情報ｓｅｎｄ信号と優先ルール番号とを受け取り、ルール読出し回路２０３−２からルール情報とルール情報ｓｅｎｄ信号とを受け取る。第２ステージの比較回路２０２−２も第１ステージの比較回路２０２−１と同様に、第２ステージのルール情報と受信パケット情報とを比較し、受信パケット情報と第２ステージの全てのルール情報との比較が終了後、検索結果となる優先ルール番号を生成する。その後、前段の第１ステージの比較回路２０２−１に受信パケット情報ａｃｋ信号を送る。
第３ステージの比較回路２０２−３は、第２ステージの比較回路２０２−２と同様の動作を行うため、ここでの説明を省略する。
【００２１】
結果出力部２０４は、第３ステージの比較回路２０２−３から、第１ステージから第３ステージまでの検索結果となる優先ルール番号および受信パケット情報を受け取る。結果出力部２０４は、外部（ここでは、図１のＱｏＳ部１０６）に、第１ステージから第３ステージの優先ルール番号に対応する検索結果を出力するために、第１検索結果蓄積部２０５−１から第３検索結果蓄積部２０５−３にあらかじめ設定されている検索結果を優先ルール番号を用いて読み出し、外部に出力する。
第１ルール読出し回路２０３−１のルール蓄積部２０７−１は、検索の種別に応じた複数のルール情報を予め蓄積する。
【００２２】
第１ルール読出し回路２０３−１のルール読出し部２０６−１は、第１ステージに属する全ての比較回路２０２から、比較が終了したことを示すルール情報ａｃｋ信号（第２信号ともいう）を受けとった場合に、ルール蓄積部２０７−１からルール情報を読み出し、各比較回路２０２へルール情報ｓｅｎｄ信号とルール情報とを送る。
ルール情報およびルール情報ｓｅｎｄ信号は、同一ステージの各比較回路２０２へブロードキャストされるため、まだ比較処理が終了していない比較回路２０２へルール情報を送ることにより誤動作する可能性がある。よって、全ての比較回路２０２からのルール情報ａｃｋ信号を受けてからルール情報を送ることで誤動作をなくすことができる。
なお、比較回路２０２が受信パケット情報を受けておらず、ルール情報との比較が不要である場合でも、ルール情報ａｃｋ信号を出力しないことによるルール読出し部２０３の読み出し処理のデッドロックを回避する必要があるため、比較回路２０２は、受信パケット情報を受信していない場合でも、受信パケット情報を受信して比較処理をしているときと同じように、ルール情報ｓｅｎｄ信号に応じてルール情報ａｃｋ信号を送信する。これにより、読み出し処理のデッドロックを避けることができる。
【００２３】
なお、第２ルール読出し部２０６−２および第３ルール読出し部２０６−３、第２ルール蓄積部２０７−２および第３ルール蓄積部２０７−３については、ルール蓄積部２０７に格納されるルール情報が違うこと以外は第１ルール読出し回路２０３−１と同様の動作を行うため、詳細な説明は省略する。
【００２４】
次に、比較回路２０２について図３のブロック図を参照して説明する。
比較回路２０２は、比較回路制御部３０１、カウンタ３０２、比較部３０３、第１レジスタ３０４、第２レジスタ３０５、第３レジスタ３０６、第４レジスタ３０７、第１遅延素子３０８、第２遅延素子３０９、第１Ｃ素子３１０、第２Ｃ素子３１１およびＯＲゲート３１２を含む。また、比較部３０３以外の部分を比較回路制御部と呼んでもよい。
【００２５】
第１遅延素子３０８は、受信パケット情報ｓｅｎｄ信号を受け取って、回路動作が不安定にならない程度に小さい遅延させ、比較回路制御部３０１からの出力（ｏｕｔ０）と合わせてＯＲゲート３１２に同時に入力されるようにする。
第２遅延素子３０９は、比較回路制御部３０１、カウンタ３０２、比較部３０３の中で最も処理遅延の大きい遅延量に合わせ、処理後の値の確定を保証する。
【００２６】
第１Ｃ素子３１０は、受信した受信パケット情報と検索結果の優先ルール番号とを後段のステージに送るため、データ保持を行うラッチ信号を生成し、第４レジスタ３０７へ送るとともに、受信パケット情報ｓｅｎｄ信号と受信パケット情報ａｃｋ信号とを制御する。なお、Ｃ素子は、レジスタと対に設置される一般的な制御回路であり、Ｃ素子の動作は図８に後述するような一般的な動作を行うためここでの説明は省略する。
第２Ｃ素子３１１は、比較回路制御部３０１、カウンタ３０２、比較部３０３の出力にそれぞれ接続されている、第１レジスタ３０４、第２レジスタ３０５および第３レジスタ３０６へのラッチ信号を生成するとともに、ルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号を制御する。これにより、比較回路制御部３０１、カウンタ３０２および比較部３０３は、第２Ｃ素子３１１で送受されるルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号に同期して動作する。
【００２７】
第１レジスタ３０４は、後述する比較回路制御部３０１からステートマシンの状態を示す状態情報を受け取って保持し、再び比較回路制御部３０１へ出力するとともにカウンタ３０２および比較部３０３へ出力する。
第２レジスタ３０５は、カウンタ３０２からの出力であるカウンタ値を保持し、再びカウンタ３０２へ出力するとともに、比較回路制御部３０１へカウンタ値を出力する。
第３レジスタ３０６は、比較部３０３からの出力（優先ルール番号や優先度）を保持し、再び比較部３０３へ出力する。
第４レジスタ３０７は、第３レジスタ３０６から検索結果となる優先ルール番号を、受信パケット情報振分け部２０１または前ステージの比較回路２０２から受信パケット情報をそれぞれ受け取って値を保持し、優先ルール番号と受信パケット情報とを出力する。第２ステージ以降の比較部３０３である場合は、第４レジスタ３０７では、受信パケット情報と前ステージの検索結果である優先ルール番号とをあわせて受け取り、前ステージの優先ルール番号とともに、比較部３０３で処理を完了した優先ルール番号と受信パケット情報とを、後のステージへ出力する。
【００２８】
比較回路制御部３０１は、レジスタ３０４と合わせてステートマシンを形成し、ルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号に同期して動作する。このステートマシンは、図３の示すプログラムのように、状態「Ｉｄｌｅ」、「ＳＴ１」および「ＳＴ２」の３つの状態情報を生成する。比較回路制御部３０１は、動作が開始すると初期状態である状態「Ｉｄｌｅ」から状態「ＳＴ１」へと移行する。状態「ＳＴ１」では、ダウンカウントされるカウンタ３０２のカウンタ値を参照して、カウンタ値が０となったとき、状態「ＳＴ２」に遷移する。状態「ＳＴ２」では、処理が終了すると状態「Ｉｄｌｅ」となる。なお、図３に示すステートマシンの状態遷移のプログラムの記述は一例であり、これに限らずこのような動作を行うステートマシンであればよい。
【００２９】
カウンタ３０２は、レジスタ３０５と合わせてカウンタ動作を行い、比較回路制御部３０１から状態情報を受け取り、比較回路制御部３０１（実際はレジスタ３０４の出力）が状態「Ｉｄｌｅ」の場合、レジスタ３０５の初期値を保持するように動作する。ここでは、カウンタ値の初期値は、ルール蓄積部２０７に蓄えられているルール情報の数とするが任意の値でもよい。比較回路制御部３０１（レジスタ３０４の出力）が状態「ＳＴ１」の場合、ダウンカウントする。レジスタ３０５の値が「０」となると比較回路制御部３０１の状態が「ＳＴ２」に遷移し、状態「ＳＴ２」の場合、状態「Ｉｄｌｅ」と同様に初期値を設定する。
比較部３０３は、ルール読出し部２０６からルール情報を、受信パケット情報振分け部２０１または前ステージの比較回路２０２から受信パケット情報を、比較回路制御部３０１から状態情報を、およびレジスタ３０６の出力をそれぞれ受け取る。比較部３０３は、ルール情報と受信パケット情報とを比較し、優先ルール番号と優先度を出力する。具体的な動作については、図５を参照して後述する。
【００３０】
次に、比較回路２０２の動作の具体例に関するタイミングチャートについて図４を参照して説明する。なお、図４は、各信号の出力が時系列で示され、受信パケット情報ｓｅｎｄ信号を受信したときのタイミングチャートを示す。また、図４に示すそれぞれの信号は、図３の同一符号の信号に対応している。
ステップＳ４０１では、受信パケット情報ｓｅｎｄ信号が入力されたとき、すなわち受信パケット情報ｓｅｎｄ信号が「０」となったときに動作を開始し、比較回路制御部３０１が状態「Ｉｄｌｅ」から状態「ＳＴ１」に遷移する。
ステップＳ４０２では、比較回路制御部３０１の状態が「ＳＴ１」に遷移したことにより、比較部３０３の比較部出力３６０がクリアされ、カウンタ３０２の初期値がセットされる。ここでは、カウンタ出力３５８が、「１２７」となる。
【００３１】
ステップＳ４０３では、比較部３０３が、ルール情報ごとに、ルール情報と受信パケット情報とを比較する。このとき、第２Ｃ素子３１１では、ルール情報ｓｅｎｄ信号が「０」となり、これに伴い、ルール情報ａｃｋ信号が「０」となり、第２Ｃ素子３１１にルール情報ｓｅｎｄ信号を送出したＣ素子がそのルール情報ａｃｋ信号を受信し、ルール情報ｓｅｎｄ信号を「１」にし、それが遅延素子で遅延された後、第２Ｃ素子３１１のルール情報ｓｅｎｄ信号が「１」になったとき、ラッチ信号が生成され、これに伴いルール情報ａｃｋ信号が「１」となったときラッチ信号が立ち下がる。またこの際、カウンタの値が１ずつダウンカウントされる。なお、本実施形態では、１２８個のルール情報があるので１２８回の比較が行われることになる。
ステップＳ４０４では、１２８回の比較が行われて、カウンタレジスタ出力３５９が「０」となった場合に、比較回路制御部３０１の状態が「ＳＴ１」から「ＳＴ２」に遷移する。
ステップＳ４０５では、比較回路制御部３０１の状態「ＳＴ２」では、ｏｕｔ０信号が「０」となる。ｏｕｔ０信号と受信パケット情報ｓｅｎｄ信号とが入力されたＯＲゲート３１２から、受信パケット情報ｓｅｎｄ信号３６２が「０」となって第１Ｃ素子３１０に送られる。その後、第１Ｃ素子３１０において、受信パケット情報ｓｅｎｄ信号３５４が「０」となる。
【００３２】
ステップＳ４０６では、受信パケット情報ｓｅｎｄ信号３６２の入力が「０」であり、受信パケット情報ａｃｋ信号の入力（図示せず）が「１」である場合、第１Ｃ素子３１０は、出力である受信パケット情報ａｃｋ信号３６３を「０」とし、前のステージに受信パケット情報ｓｅｎｄ信号を受け取ったことを通知する。
ステップＳ４０７では、前のステージからの受信パケット情報ｓｅｎｄ信号３５４が「１」となり、その信号が第１Ｃ素子３１０で受信されると、第１Ｃ素子３１０は、ラッチ信号を生成し、受信パケット情報と優先ルール番号とが第４レジスタ３０７に保持され、比較部レジスタ出力３６１となる。ここでは、ルール番号「１３」であるルール情報が優先ルール番号として選択される例を示す。
ステップＳ４０８では、一連のハンドシェイクを終了するため、第１Ｃ素子３１０は、受信パケット情報ａｃｋ信号３６３を「１」にして、前のステージの比較回路に処理が終了したことを通知する。
比較部３０３は、以上のステップを新たな受信パケット情報を受け取るたびに繰り返し行う。
【００３３】
次に、比較部３０３の詳細な動作について図５を参照して説明する。
比較部３０３は、パケット情報比較部５０１、優先度値比較部５０２、論理積部５０３、第１選択部５０４および第２選択部５０５を含む。
パケット情報比較部５０１は、受信パケット情報振分け部２０１または前のステージの比較回路２０２から受信パケット情報を、ルール読出し部２０６からルール情報をそれぞれ受け取り、受信パケット情報とルール情報中の比較情報とを比較して一致するかどうかを判定する。パケット情報比較部５０１は、受信パケット情報が一致する場合には、「１」を出力し、受信パケット情報が一致しない場合には、「０」を出力する。
優先度値比較部５０２は、ルール読出し回路２０３からルール情報中の優先度値を、優先度レジスタからの出力をそれぞれ受け取り、優先度レジスタ値と優先度値とを比較する。優先度レジスタ値が優先度値よりも大きい（優先度値の方が優先度レジスタ値よりも優先度が高い）場合は、「１」を出力し、優先度レジスタ値が優先度値以下である場合は、「０」を出力する。
【００３４】
論理積５０３は、パケット情報比較部５０１からの出力と優先度値比較部５０２からの出力とを受け取り、これらを論理積して１ビットの更新信号を生成する。比較回路制御部３０１の状態「ＳＴ１」の場合、受信パケット情報とルール情報とが一致し、かつ優先度値が優先度レジスタ値より優先（優先値が小さい）である場合、すわなち、パケット情報比較部５０１および優先度値比較部５０２の値が共に「１」である場合、論理積部５０３は、値が「１」である更新信号を生成する。パケット情報比較部５０１および優先度値比較部５０２の出力がどちらか少なくとも「０」である場合は、論理積部５０３は、値が「０」である更新番号が生成される。
第１選択部５０４は、比較回路制御部３０１の状態が「Ｉｄｌｅ」の場合、ルール番号初期値を設定する。更新信号が「０」である場合は、第１選択部５０４において「１」が選択され、番号レジスタ値はそのまま保持される。更新信号が「１」である場合は、第１選択部５０４において「２」が選択され、番号レジスタ値が受け取った新たなルール番号で書き換えられる。
【００３５】
第２選択部５０５は、比較回路制御部３０１の状態が「Ｉｄｌｅ」の場合、優先度初期値を設定する。更新信号が「０」である場合は、第２選択部５０５において「１」が選択され、優先度レジスタ値はそのまま保持される。更新信号が「１」である場合は、第２選択部５０５において「２」が選択され、優先度レジスタ値が受け取った新たな優先度値で書き換えられる。
以上の処理を全てのルール情報について比較し、全てのルール情報について完了した場合、受信パケット情報がルール情報に一致し、かつ最も優先度の高いルール番号を有する優先ルール番号を得ることができる。比較回路制御部３０１の状態が「ＳＴ２」の場合、次のステージに比較回路２０２の検索結果となるルール番号を保持し続ける。
なお、優先度レジスタおよび番号レジスタは、値を保持できる記憶素子であればよく、本実施形態では、第３レジスタ３０６のことである。
【００３６】
次に、ルール読出し部２０６およびルール蓄積部２０７の一例について図６を参照して説明する。
ルール読出し部２０６は、有限ステートマシン６０１（以下、ＦＳＭ（Finite State Machine））、ＡＮＤゲート６０２、第１Ｃ素子（Ｃ１）６０３、第２Ｃ素子（Ｃ２−０、Ｃ２−１、Ｃ２−Ｎ）６０４、マージ回路６０５、および遅延素子（Ｄ２）６０６を含む。なお、Ｎは２以上の自然数である。
【００３７】
ルール蓄積部２０７は、インクリメント素子６５１、アドレスレジスタ６５２、およびＳＲＡＭ６５３を含む。
ＡＮＤゲート６０２は、受信パケット情報ｓｅｎｄ信号を論理積する。
ＦＳＭ６０１は、各比較回路２０２から「０」である受信パケット情報ｓｅｎｄ信号を受け取ることにより動作を開始する。本回路は、複数の比較回路２０２のうち１つでも受信パケット情報を受け取ったとき、つまり「０」である受信パケット情報ｓｅｎｄ信号を１つでも受け取ったときに動作を開始する必要があるため、各比較回路２０２からの受信パケット情報ｓｅｎｄ信号は、ＡＮＤゲート６０２により論理積されてＦＳＭ６０１に入力される。これにより、ＦＳＭ６０１は、いずれか１つでも受信パケット情報を受け取った比較回路２０２があることを認識することができる。
【００３８】
第１Ｃ素子６０３は、第２Ｃ素子６０４（Ｃ２−０、Ｃ２−１、Ｃ２−Ｎ）のルール情報ａｃｋ信号がマージされた信号を受け取る。そして、第１Ｃ素子６０３は、第２Ｃ素子６０４（Ｃ２−０からＣ２−Ｎまで）のマージされたルール情報ａｃｋ信号が１のとき、すなわち、前回第２Ｃ素子が制御するレジスタに送出したルール情報が各比較回路２０２へ送出完了し、比較処理が完了し第２Ｃ素子が次のルール情報を受け入れ可能になった場合、ｋｅｙ＿ａｃｋを「１」にし、送信要求を受け入れられることをＦＳＭ６０１へ送る。「１」のｋｅｙ＿ａｃｋを受けたＦＳＭ６０１により「０」となり、ＦＳＭと第１Ｃ素子との間のハンドシェイクにより、ｋｅｙ＿ｒｅｑが「１」、ｋｅｙ＿ａｃｋが「０」を受けた第１Ｃ素子６０３は、ルール蓄積部２０７のアドレスレジスタ６５２の値を更新または保持するためのラッチ信号をアドレスレジスタ６５２へ送る。
【００３９】
第２Ｃ素子６０４（Ｃ２−０からＣ２−Ｎ）は、それぞれが接続される比較回路２０２からのルール情報ａｃｋ信号が「１」の場合、すなわち各々の比較回路２０２において先に送ったルール情報と受信パケット情報との比較が完了している場合に、遅延素子Ｄ２により遅延させられたＣ１のｓｅｎｄ信号が「０」すなわち、各比較回路へのルール情報送信要求があった場合、ルール情報ａｃｋ信号を「０」にして、ｓｅｎｄ信号を受け取ったことをマージ回路６０５を介してＣ１に送る。また、ハンドシェイクにより「１」となったルール情報ｓｅｎｄ信号を受信した各第２Ｃ素子６０４は、ルール蓄積部２０７から読み出したルール情報をレジスタに蓄積または保存するためのラッチ信号を生成する。これと同時に、各比較回路２０２に対して新たなルール情報で比較を開始させるために、ルール情報ｓｅｎｄ信号を各比較回路２０２に送る。
【００４０】
マージ回路６０５は、例えば、ＭｕｌｌｅｒのＣ素子であり、第２Ｃ素子６０４のルール情報ａｃｋ信号をマージする。ＭｕｌｌｅｒのＣ素子を用いる理由は、複数入力されるルール情報ａｃｋ信号の中で、最後に立ち下がった（１から０への遷移）信号に合わせて出力を立ち下げ、最後に立ち上がった（０から１への遷移）信号に合わせて出力を立ち上げるためである。つまり、第２Ｃ素子のＣ２−０からＣ２−Ｎが受け取ったルール情報ａｃｋ信号うち、どのａｃｋ出力が遅くなるのかわからないのでＭｕｌｌｅｒのＣ素子を用いることが望ましい。マージされたルール情報ａｃｋ信号は、Ｃ２−０からＣ２−Ｎのａｃｋ出力の中で最も遅いルール情報ａｃｋ信号に合わせることができるので、全ての比較回路が１つのルール情報と受信パケット情報との比較を完了したことを保証して次のルール情報を各比較回路に送ることができ、誤動作をなくすことができる。
遅延素子（Ｄ２）６０６は、ルール蓄積部２０７のメモリアクセス遅延にあわせた遅延量を加えて第２Ｃ素子６０４へ送る。
インクリメント素子６５１は、アドレスレジスタ６５２の値を１つインクリメントする。
アドレスレジスタ６５２は、インクリメント素子６５１により更新の度にアドレスがインクリメントされるので、本動作を繰り返すことにより、ＳＲＡＭ６５３に記憶されるルール情報を順次変更することができる。
ＳＲＡＭ６５３は、複数のルール情報が記憶されるメモリであり、インクリメントされたアドレスレジスタ６５１の値に応じた次のルール番号となるアドレス値のルール情報を出力する。
【００４１】
次に、ルール読出し部２０６におけるＦＳＭ６０１の状態について図７を参照して説明する。
図７はＦＳＭ６０１の状態遷移図を示し、「Ｉｄｌｅ」、「ｒｅｑ＿Ｌ」および「ｒｅｑ＿Ｈ」の３つの状態が存在する。
状態「Ｉｄｌｅ」において、ルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号ともに１である場合で、かつ、いずれかの比較回路２０２からの検索要求がある場合（すなわち、受信パケット情報ｓｅｎｄ信号が「０」（ｓｅａｒｃｈ＿ｒｅｑが「０」）となった場合）、状態「ｒｅｑ＿Ｌ」に遷移する（ステップＳ７０１）。ＦＳＭ６０１の状態が状態「Ｒｅｑ＿Ｌ」に遷移した場合、ルール情報を送るためにルール情報ｓｅｎｄ信号を「０」にする（ｋｅｙ＿ｒｅｑを０にする）。次段は読み出しアドレスを生成する回路となっており、前回の読み出しアドレス生成が終了している場合、すぐにａｃｋ信号を返す（ｋｅｙ＿ａｃｋが０）。ＦＳＭ６０１におけるｋｅｙ＿ｒｅｑおよびｋｅｙ＿ａｃｋがともに０となるため、状態が「ｒｅｑ＿Ｈ」に遷移する（ステップＳ７０２）。状態「ｒｅｑ＿Ｈ」では、ルール情報ｓｅｎｄ信号を１にし、ルール情報ａｃｋ信号が１になるタイミングを監視し、さらに、ｓｅａｒｃｈ＿ｒｅｑの状態により、状態「Ｉｄｌｅ」に遷移するか（ステップＳ７０３）、状態「ｒｅｑ＿Ｌ」に遷移し（ステップＳ７０４）、次のルール番号（読み出しアドレス）となるルール情報を送るため、ルール情報ｓｅｎｄ信号を０にする（ｋｅｙ＿ｒｅｑを０にする）。「Ｒｅｑ＿Ｌ」、「ｒｅｑ＿Ｈ」の繰り返しにより次々と読み出しアドレスを生成する。但し、受信パケットｓｅｎｄ信号が「１」（ｓｅａｒｃｈ＿ｒｅｑが「１」）であり、どの比較回路２０２においても比較処理を行わないような場合には、状態「Ｉｄｌｅ」に戻り、次の検索要求が来るまでルール情報の送出を停止する。これによって、無駄な電力消費を押さえることができる。
【００４２】
ここで、一般的な非同期回路の一例である、一線式束データ方式の非同期回路ブロックと各信号のタイミングチャートを図８に示す。図８上側は、一般的な非同期回路のブロック図の一例を示し、図８下側は、図８上側のブロック図におけるタイミングチャートを示す。
非同期回路は、同期回路のように各レジスタに供給されるクロック信号に代わり、レジスタと対に置かれるＣ素子間のハンドシェイクによってレジスタのラッチ信号を生成して、処理を行う。レジスタに供給されるラッチ信号がすぐ近くに配置される制御回路から供給される点と、データが入力されない場合は制御回路間のハンドシェイクが発生せずラッチ信号も生成されない点から、非同期回路のほうが、クロック信号を用いた同期回路の電力消費よりも電力消費が少なく、大幅に削減することができる。
【００４３】
以下、基本的な束データ方式の非同期回路とＣ素子の動作タイミングとについて説明する。
ｉ−１ステージからの送信要求を受け取るとｉステージでの処理が開始される。はじめに、ｓｅｎｄ ｉ ｏｕｔが０となり（ステップＳ１）、ｄｅｌａｙ時間経過後ｓｅｎｄ ｉ ｉｎが０となる（ステップＳ２）。そのときのａｃｋ ｉ＋１ ｉｎが１なので、送信要求を受け取ったことを伝えるべく、ａｃｋ ｉ ｏｕｔを０とする（ステップＳ３）。このとき、ａｃｋ ｉ ｉｎも０となる（ステップＳ４）。それと同時に、ｓｅｎｄ ｉ＋１ ｏｕｔを０にする（ステップＳ５）。ａｃｋ ｉ ｉｎ信号は０となっているので、ｓｅｎｄ ｉ ｏｕｔが１となる（ステップＳ８０６）。続いて、ｓｅｎｄ ｉ ｉｎは、ｄｅｌａｙ時間遅延して１になる（ステップＳ７）。このタイミングでラッチまたはレジスタにおいてデータの更新または保持を行うために、ｃｌｋ ｉが立ち上がる（ステップＳ８）。その後ａｃｋ ｉ ｏｕｔは、１に変わり（ステップＳ９）、ｃｌｋ ｉをたち下げる。このとき、ａｃｋ ｉ ｉｎも１となる（ステップＳ１０）。以上によりデータパスの信号伝播（処理）が制御される。
【００４４】
続いて、ｓｅｎｄ ｉ ｏｕｔを０にして次のデータ処理を開始しようとする場合（ステップＳ１３）、ｄｅｌａｙ時間遅れて、ｓｅｎｄ ｉ ｉｎが１になる（ステップＳ１４）。このとき、ｓｅｎｄ ｉ＋１ ｏｕｔは１であり（ステップＳ１２）、次のステージからのａｃｋ ｉ＋１ ｉｎは０であるため（ステップＳ１１）、次段で先ほどのデータ伝播（処理）が完了していないことがわかる。そのため、ａｃｋ ｉ＋１ ｉｎが１になるまで、ａｃｋ ｉ ｏｕｔを０にするのを待つ。ａｃｋ ｉ＋１ ｉｎが１になり（ステップＳ１５）、その後ａｃｋ ｉ ｏｕｔが０となり（ステップＳ１６）、データ処理が完了したことが通知されたときに、ｓｅｎｄ ｉ＋１ ｏｕｔを０にして（ステップＳ１７）、次段にデータを転送する。その後は同様の動作を行えばよい。
【００４５】
以上に示した本実施形態に係る非同期動作検索回路によれば、クロック信号を必要とせずにハンドシェイクにより制御を行うことができるので、同期回路よりも大幅に低い消費電力で検索回路を動作させることができる。また、全ての比較回路からのａｃｋ信号を受信してから次のルール情報を送ることで、誤動作することがなく正確な検索処理を行うことができる。さらに、ステージごとに全てのルール情報と比較完了してから検索結果を出力することにより、正確な検索処理を行うことができる。よって、処理性能が高く低消費電力で検索処理を行うことができる。
【００４６】
要するにこの発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００４７】
１００・・・パケット処理回路、１０１，１０８・・・ネットワークインターフェース、１０２・・・パーサ、１０３・・・フレームコントローラ、１０４・・・バッファメモリ、１０５・・・非同期検索回路、１０６・・・ＱｏＳ部、１０７・・・フレーム生成部、１０８・・・ネットワークインターフェース、２０１・・・受信パケット振分け部、２０２−１，２０２−２，２０２−３・・・比較回路、２０３・・・ルール読出し回路、２０４・・・結果出力部、２０５・・・検索結果蓄積部、２０６・・・ルール読出し部、２０７・・・ルール蓄積部、３０１・・・比較回路制御部、３０２・・・カウンタ、３０３・・・比較部、３０４，３０５，３０６，３０７・・・レジスタ、３０８，３０９・・・遅延素子、３１０，３１１，６０３，６０４・・・Ｃ素子、３１２・・・ＯＲゲート、５０１・・・パケット情報比較部、５０２・・・優先度値比較部、５０３・・・論理積部、５０４，５０５・・・選択部、６０１・・・有限ステートマシン（ＦＳＭ）、６０２・・・ＡＮＤゲート、６０５・・・マージ回路、６５１・・・アドレスレジスタ、６５２・・・ＳＲＡＭ、６５３・・・インクリメント素子。
【技術分野】
【０００１】
この発明は、例えばＩＰ（Internet Protocol）網で使用されるルータ等のように、パケットフィルタリング機能を用いたパケットの転送処理に用いる非同期動作検索回路に関する。
【背景技術】
【０００２】
近年、インターネットに代表されるＩＰ網の利用拡大に伴い、企業および家庭内にＬＡＮ（Local Area Network）を構築し、このＬＡＮをインターネット等を介して外部のネットワークに接続させ、パケット転送を行うことが多い。しかし、ＬＡＮに収容された端末を外部のネットワークに接続すると、外部のネットワークからの不正アクセスにより、個人情報等の機密情報の漏えいまたは改竄が発生するおそれがあるため、ＬＡＮ内部のセキュリティの確保が重要な課題となる。
そこで従来では、ＬＡＮと外部ネットワークとの間でパケットを中継転送するルータなどのパケット転送処理装置に、パケットフィルタリング機能を持たせるようにしている。パケットフィルタリング機能は、受信されたパケットを予め設定されているルール情報と比較することにより、上記パケットの通過を許可するか否かを判定する。ルール情報は、パケット転送に使用される通信パラメータにより定義され、例えば、送信元アドレス、宛先アドレス、プロトコル、送信元ポート番号及び宛先ポート番号などがある。パケットフィルタリング処理の性能は、ルール情報の数の増加に伴って低下するため、ルール情報と受信パケットとの比較処理回路を並列化し、性能向上を狙う回路構成が存在する（例えば、非特許文献１参照）。
【０００３】
ところが、ルールの読み出し処理や比較処理回路は同期して動作する必要があり、通常はクロック信号に同期して動作する。このクロックは、動作タイミングをそろえるために回路に供給され、データ処理に対して直接関与しない。それにも関わらず、クロック信号は、ＬＳＩチップ全体に供給されるため、大きく電力を消費する。例えば、受信パケットが入力されておらず、処理としてはアイドル状態にも関わらず、クロックがＬＳＩ全体に供給されるために電力が大きく消費されてしまう。
【０００４】
そこで、電力消費を削減する観点から、クロック信号を用いずに、処理段ごとに送信信号（ｓｅｎｄ信号）と応答信号（ａｃｋ信号）とのハンドシェイクにより処理を進める非同期回路の適用が考えられる。非同期回路は、クロック信号が不要であり、さらにデータ入力されない場合は、制御回路間のハンドシェイクも発生しないので、電力消費を大きく削減することができる。
さらに、ＬＳＩ製造技術の微細化により、リーク電流に起因する静的消費電力の増加が問題となっているが、非同期回路は、制御部のハンドシェイクにより処理を行っている処理段において有効なデータが存在しているか否かを知ることが容易である。従って、有効なデータが存在しない場合、処理段の電源を遮断するいわゆるパワーゲーティングを容易に実現することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】西田享邦，川合健治，小池恵一，大山勝一，“１Ｇｂｉｔ／ｓホームルータ用ＬＳＩの開発”，信学技報，ＩＣＤ２００７−５８，ｐｐ．１２３−１２８，Ｊｕｌ．２００７
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非同期回路の場合、受信パケット情報とルール情報との比較処理の完了時間が比較回路ごとに異なる。そのため、複数の比較回路にルール情報を同時に送信すると、まだ比較処理が終了していない比較回路では、処理が間に合わず誤動作することがある。加えて、パケットフィルタリング処理では、１つの受信パケット情報と複数のルール情報との比較を行う必要があるが、受信パケット情報の受け入れ制御を行う制御部において、すべてのルール情報の比較が終了したことを検知できない。よって、すべてのルール情報との比較が終了する前に検索結果を出力して、次の受信パケット情報の受信を開始してしまい、正しく検索ができない可能性がある。
【０００７】
この発明は上記事情に着目してなされたもので、その目的とするところは、低消費電力でかつ高性能に検索することができる非同期動作検索回路を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するためにこの発明の一つの観点は、パケットの通過を許可するか否かを判定する検索種別に対応した複数のルール情報のうちの第１ルール情報と、受信したパケットに関する情報とを比較する比較部を具備し、前記比較部は複数あり、比較部ごとに受信したパケットが異なり、比較部ごとに、複数の比較部で共通する前記第１ルール情報を受信した場合、前記比較部に比較処理をさせるように制御し、該第１ルール情報とパケットに関する情報との比較が完了した場合または該パケットを受信しなかった場合にも処理が完了したことを示す第２信号を生成する比較回路制御部と、前記複数の比較部からの全ての第２信号を受信した場合、前記第１ルール情報とは異なる第２ルール情報を読み出し、該第２ルール情報を前記複数の比較部に送信する読出し部と、をさらに具備し、前記比較回路制御部は、前記複数のルール情報を全て受信するまで前記比較部に順次前記比較処理を行わせ、前記第２信号を生成することを特徴とする。
【発明の効果】
【０００９】
すなわちこの発明によれば、低消費電力でかつ高性能に検索することができる。
【図面の簡単な説明】
【００１０】
【図１】本実施形態に係る非同期動作検索回路を含むパケット処理回路を示すブロック図。
【図２】本実施形態に係る検索部を示すブロック図。
【図３】本実施形態に係る比較回路を示すブロック図。
【図４】比較回路の動作の一例を示すタイミングチャート。
【図５】本実施形態に係る比較部を示すブロック図。
【図６】本実施形態に係るルール読み出し部を示すブロック図。
【図７】ルール読出し部の状態遷移の一例を示す図。
【図８】一般的なＣ素子を用いた非同期回路のタイミングチャート。
【発明を実施するための形態】
【００１１】
以下、図面を参照しながら本発明の実施形態に係る非同期動作検索回路について詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
本実施形態に係る非同期検索回路を含むパケット処理回路１００について図１を参照して説明する。
パケット処理回路１００は、ネットワークインターフェース１０１，１０８、パーサ１０２、フレームコントローラ１０３、バッファメモリ１０４、非同期検索回路１０５、ＱｏＳ（Quality of Service）部１０６およびフレーム生成部１０７を含む。
【００１２】
ネットワークインターフェース１０１，１０８は、ＷＡＮ（Wide Area Network）またはＬＡＮとのインターフェースである。ネットワークインターフェース１０１は、ＷＡＮまたはＬＡＮからパケットデータを受信する。ネットワークインターフェース１０８は、後述するフレーム生成部１０７からパケットデータを受信して、ＷＡＮまたはＬＡＮに送信する。
パーサ１０２は、ネットワークインターフェース１０１からパケットデータを受け取り、受信パケット情報を抽出する。受信パケット情報は、ＩＰアドレスまたはポート番号といった、後述の非同期検索回路１０５における比較処理で必要とされるパケットに関する情報である。
フレームコントローラ１０３は、パーサ１０２からパケットデータを受け取り、バッファメモリ１０４に格納するように制御する。
【００１３】
バッファメモリ１０４は、フレームコントローラ１０３からパケットデータを受け取り、パケットデータを格納する。
非同期検索回路１０５は、パーサ１０２から受信パケット情報を受け取り、受信パケット情報と様々なルール情報とを比較する。ルール情報は、ルール番号、優先度値および比較情報を含む。ルール番号は、例えば後述するルール蓄積部２０７に蓄積されたルール情報のアドレスのような、ルール情報を識別するＩＤである。優先度値は、受信パケット情報とルールとが一致する場合に、どれほど優先して適用されるかを示す。ここでは、優先度が高いほど値が小さいとする。比較情報は、受信パケット情報と比較するための情報であって、それぞれの検索種別に対応してパケットの通過を許可するか否かを判定する情報である。例えば、経路検索であれば送信元アドレス、宛先アドレスなどの情報である。非同期検索回路１０５は、パケットデータの廃棄／通過、出力インターフェースの決定、通信品質クラス分けといった受信したパケットデータの取り扱いを決定する。なお、ルール情報は、非同期検索回路１０５内部に予め格納されていてもよいし、外部のルール情報蓄積部（図示せず）から比較処理のたびにルール情報を抽出して比較してもよい。非同期検索回路１０５の詳細については、図３を参照して後述する。
【００１４】
ＱｏＳ部１０６は、非同期検索回路１０５からルール情報と比較された受信パケット情報を受け取る。取り扱いが廃棄の場合、フレームコントローラ１０３にパケットデータを廃棄するように廃棄要求を送り、バッファメモリ１０４において当該パケットが使用していたバッファ領域を解放する。取り扱いが通過の場合、決定された通信品質クラスに従い、キューイングされ、指定されたパケット送信タイミングでフレーム生成部１０７に送信要求を送る。
【００１５】
フレーム生成部１０７は、ＱｏＳ部１０６から送信要求と、ルール情報と比較された受信パケット情報とを受け取り、パケットデータの読み出しをフレームコントローラ１０３に要求する。フレーム生成部１０７は、フレームコントローラ１０３を介してバッファメモリ１０４から当該パケットデータを受け取るとともに、非同期検索回路１０５においてルール情報と比較された受信パケット情報に基づき、ＭＡＣアドレスの書き換えや、ＩＰアドレスの書き換え等を行い、非同期検索回路１０５において決定されたインターフェースにパケットを送る。
【００１６】
次に、本実施形態に係る非同期検索回路１０５について図２のブロック図を参照して説明する。
本実施形態に係る非同期検索回路１０５は、受信パケット情報振分け部２０１、比較回路２０２、第１ルール読出し回路２０３−１、第２ルール読出し回路２０３−２、第３ルール読出し回路２０３−３、結果出力部２０４、第１検索結果蓄積部２０５−１、第２検索結果蓄積部２０５−２および第３検索結果蓄積部２０５−３を含む。さらに、第１ルール読出し回路２０３−１は、第１ルール読出し部２０６−１および第１ルール蓄積部２０７−１を含む。同様に、第２ルール読出し回路２０３−２は、第２ルール読出し部２０６−２および第１ルール蓄積部２０７−２を含み、第３ルール読出し回路２０３−３は、第２ルール読出し部２０６−３および第１ルール蓄積部２０７−３を含む。
【００１７】
以下便宜上、第１ルール読出し回路２０３−１および４個の比較回路２０２を第１ステージと呼び、第２ルール読出し回路２０３−２および４個の比較回路２０２を第２ステージと呼び、第３ルール読出し回路２０３−３および４個の比較回路２０２を第３ステージと呼ぶ。本実施形態では、各ステージにおいて比較回路２０２を４個並列させ、第１ステージから第３ステージまでの３段階の並列処理を行う例を示すが、これに限らず、１つのステージで並列させる比較回路の数およびステージ数は、いくつでもよい。このように比較回路を並列させることで、比較回路ごとに読出し回路を接続させずに、各ステージで１つの読出し回路が存在すればよく、回路規模を縮小させることができる。さらに各比較回路に、それぞれ別の受信パケット情報が入力され処理されるので、並列処理によりパフォーマンスを向上させることができる。
本実施形態に係る３つのステージの処理は、例えば、第１ステージにおいて論理インターフェースとＮＡＴ（Network Address Translation）検索を行い、第２ステージにおいて経路検索を行い、第３ステージにおいてパケット検索を行うことを想定する。しかし、これに限らず、各ステージにおいてどのような検索を行ってもよい。
【００１８】
受信パケット情報振分け部２０１は、パーサ１０２から受信した受信パケット情報を、比較処理が実行されていない、すなわち、受信パケット情報ａｃｋ信号を送信している第１ステージの比較回路に、受信パケット情報と受信パケット情報ｓｅｎｄ信号とを送信する。受信パケット情報ａｃｋ信号は、受信パケット情報と全てのルール情報との比較が終了したか否かを示す信号である。受信パケット情報ｓｅｎｄ信号は、受信パケット情報を送信したか否かを示す信号である。なお、受信パケット情報ｓｅｎｄ信号と受信パケット情報ａｃｋ信号とは１ビットの信号とするが、何ビットの信号を用いてもよい。
【００１９】
第１ステージの比較回路２０２は、受信パケット情報振分け部２０１から受信パケット情報ｓｅｎｄ信号と受信パケット情報とを受け取り、ルール読出し回路２０３−１からルール情報とルール情報ｓｅｎｄ信号とを受け取る。ルール情報ｓｅｎｄ信号は、ルール情報を送信したか否かを示す信号である。比較回路２０２は、受信パケット情報とルール情報との比較を行う。また、比較回路２０２は、ルール蓄積部２０７に蓄積されるルール情報と受信パケット情報とを比較し、第１ルール読出し回路２０３−１にルール情報ａｃｋ信号を送る。ルール情報ａｃｋ信号は、受信パケット情報と１つのルール情報との比較処理が完了したか否かを示す信号である。
ルール蓄積部２０７−１に蓄積されるすべてのルール情報について、受信パケット情報とルール情報とが一致したルール番号の中で最も優先度が高いルール番号（優先ルール番号）を決定する。全てのルールと比較処理が完了した場合は、受信パケット情報振分け部２０１に受信パケット情報ａｃｋ信号を送信する。なお、ルール情報ｓｅｎｄ信号とルール情報ａｃｋ信号とは１ビットの信号とするが、何ビットの信号を用いてもよい。
【００２０】
第２ステージの比較回路２０２−２は、第２ステージにおいて比較処理が完了している場合は、第１ステージの比較回路２０２−１へ受信パケット情報ａｃｋ信号を送り、第２ルール読出し回路２０３−２へルール情報ａｃｋ信号を送る。その後、第２ステージの比較回路２０２−２は、第１ステージの比較回路２０２−１から受信パケット情報とパケット情報ｓｅｎｄ信号と優先ルール番号とを受け取り、ルール読出し回路２０３−２からルール情報とルール情報ｓｅｎｄ信号とを受け取る。第２ステージの比較回路２０２−２も第１ステージの比較回路２０２−１と同様に、第２ステージのルール情報と受信パケット情報とを比較し、受信パケット情報と第２ステージの全てのルール情報との比較が終了後、検索結果となる優先ルール番号を生成する。その後、前段の第１ステージの比較回路２０２−１に受信パケット情報ａｃｋ信号を送る。
第３ステージの比較回路２０２−３は、第２ステージの比較回路２０２−２と同様の動作を行うため、ここでの説明を省略する。
【００２１】
結果出力部２０４は、第３ステージの比較回路２０２−３から、第１ステージから第３ステージまでの検索結果となる優先ルール番号および受信パケット情報を受け取る。結果出力部２０４は、外部（ここでは、図１のＱｏＳ部１０６）に、第１ステージから第３ステージの優先ルール番号に対応する検索結果を出力するために、第１検索結果蓄積部２０５−１から第３検索結果蓄積部２０５−３にあらかじめ設定されている検索結果を優先ルール番号を用いて読み出し、外部に出力する。
第１ルール読出し回路２０３−１のルール蓄積部２０７−１は、検索の種別に応じた複数のルール情報を予め蓄積する。
【００２２】
第１ルール読出し回路２０３−１のルール読出し部２０６−１は、第１ステージに属する全ての比較回路２０２から、比較が終了したことを示すルール情報ａｃｋ信号（第２信号ともいう）を受けとった場合に、ルール蓄積部２０７−１からルール情報を読み出し、各比較回路２０２へルール情報ｓｅｎｄ信号とルール情報とを送る。
ルール情報およびルール情報ｓｅｎｄ信号は、同一ステージの各比較回路２０２へブロードキャストされるため、まだ比較処理が終了していない比較回路２０２へルール情報を送ることにより誤動作する可能性がある。よって、全ての比較回路２０２からのルール情報ａｃｋ信号を受けてからルール情報を送ることで誤動作をなくすことができる。
なお、比較回路２０２が受信パケット情報を受けておらず、ルール情報との比較が不要である場合でも、ルール情報ａｃｋ信号を出力しないことによるルール読出し部２０３の読み出し処理のデッドロックを回避する必要があるため、比較回路２０２は、受信パケット情報を受信していない場合でも、受信パケット情報を受信して比較処理をしているときと同じように、ルール情報ｓｅｎｄ信号に応じてルール情報ａｃｋ信号を送信する。これにより、読み出し処理のデッドロックを避けることができる。
【００２３】
なお、第２ルール読出し部２０６−２および第３ルール読出し部２０６−３、第２ルール蓄積部２０７−２および第３ルール蓄積部２０７−３については、ルール蓄積部２０７に格納されるルール情報が違うこと以外は第１ルール読出し回路２０３−１と同様の動作を行うため、詳細な説明は省略する。
【００２４】
次に、比較回路２０２について図３のブロック図を参照して説明する。
比較回路２０２は、比較回路制御部３０１、カウンタ３０２、比較部３０３、第１レジスタ３０４、第２レジスタ３０５、第３レジスタ３０６、第４レジスタ３０７、第１遅延素子３０８、第２遅延素子３０９、第１Ｃ素子３１０、第２Ｃ素子３１１およびＯＲゲート３１２を含む。また、比較部３０３以外の部分を比較回路制御部と呼んでもよい。
【００２５】
第１遅延素子３０８は、受信パケット情報ｓｅｎｄ信号を受け取って、回路動作が不安定にならない程度に小さい遅延させ、比較回路制御部３０１からの出力（ｏｕｔ０）と合わせてＯＲゲート３１２に同時に入力されるようにする。
第２遅延素子３０９は、比較回路制御部３０１、カウンタ３０２、比較部３０３の中で最も処理遅延の大きい遅延量に合わせ、処理後の値の確定を保証する。
【００２６】
第１Ｃ素子３１０は、受信した受信パケット情報と検索結果の優先ルール番号とを後段のステージに送るため、データ保持を行うラッチ信号を生成し、第４レジスタ３０７へ送るとともに、受信パケット情報ｓｅｎｄ信号と受信パケット情報ａｃｋ信号とを制御する。なお、Ｃ素子は、レジスタと対に設置される一般的な制御回路であり、Ｃ素子の動作は図８に後述するような一般的な動作を行うためここでの説明は省略する。
第２Ｃ素子３１１は、比較回路制御部３０１、カウンタ３０２、比較部３０３の出力にそれぞれ接続されている、第１レジスタ３０４、第２レジスタ３０５および第３レジスタ３０６へのラッチ信号を生成するとともに、ルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号を制御する。これにより、比較回路制御部３０１、カウンタ３０２および比較部３０３は、第２Ｃ素子３１１で送受されるルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号に同期して動作する。
【００２７】
第１レジスタ３０４は、後述する比較回路制御部３０１からステートマシンの状態を示す状態情報を受け取って保持し、再び比較回路制御部３０１へ出力するとともにカウンタ３０２および比較部３０３へ出力する。
第２レジスタ３０５は、カウンタ３０２からの出力であるカウンタ値を保持し、再びカウンタ３０２へ出力するとともに、比較回路制御部３０１へカウンタ値を出力する。
第３レジスタ３０６は、比較部３０３からの出力（優先ルール番号や優先度）を保持し、再び比較部３０３へ出力する。
第４レジスタ３０７は、第３レジスタ３０６から検索結果となる優先ルール番号を、受信パケット情報振分け部２０１または前ステージの比較回路２０２から受信パケット情報をそれぞれ受け取って値を保持し、優先ルール番号と受信パケット情報とを出力する。第２ステージ以降の比較部３０３である場合は、第４レジスタ３０７では、受信パケット情報と前ステージの検索結果である優先ルール番号とをあわせて受け取り、前ステージの優先ルール番号とともに、比較部３０３で処理を完了した優先ルール番号と受信パケット情報とを、後のステージへ出力する。
【００２８】
比較回路制御部３０１は、レジスタ３０４と合わせてステートマシンを形成し、ルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号に同期して動作する。このステートマシンは、図３の示すプログラムのように、状態「Ｉｄｌｅ」、「ＳＴ１」および「ＳＴ２」の３つの状態情報を生成する。比較回路制御部３０１は、動作が開始すると初期状態である状態「Ｉｄｌｅ」から状態「ＳＴ１」へと移行する。状態「ＳＴ１」では、ダウンカウントされるカウンタ３０２のカウンタ値を参照して、カウンタ値が０となったとき、状態「ＳＴ２」に遷移する。状態「ＳＴ２」では、処理が終了すると状態「Ｉｄｌｅ」となる。なお、図３に示すステートマシンの状態遷移のプログラムの記述は一例であり、これに限らずこのような動作を行うステートマシンであればよい。
【００２９】
カウンタ３０２は、レジスタ３０５と合わせてカウンタ動作を行い、比較回路制御部３０１から状態情報を受け取り、比較回路制御部３０１（実際はレジスタ３０４の出力）が状態「Ｉｄｌｅ」の場合、レジスタ３０５の初期値を保持するように動作する。ここでは、カウンタ値の初期値は、ルール蓄積部２０７に蓄えられているルール情報の数とするが任意の値でもよい。比較回路制御部３０１（レジスタ３０４の出力）が状態「ＳＴ１」の場合、ダウンカウントする。レジスタ３０５の値が「０」となると比較回路制御部３０１の状態が「ＳＴ２」に遷移し、状態「ＳＴ２」の場合、状態「Ｉｄｌｅ」と同様に初期値を設定する。
比較部３０３は、ルール読出し部２０６からルール情報を、受信パケット情報振分け部２０１または前ステージの比較回路２０２から受信パケット情報を、比較回路制御部３０１から状態情報を、およびレジスタ３０６の出力をそれぞれ受け取る。比較部３０３は、ルール情報と受信パケット情報とを比較し、優先ルール番号と優先度を出力する。具体的な動作については、図５を参照して後述する。
【００３０】
次に、比較回路２０２の動作の具体例に関するタイミングチャートについて図４を参照して説明する。なお、図４は、各信号の出力が時系列で示され、受信パケット情報ｓｅｎｄ信号を受信したときのタイミングチャートを示す。また、図４に示すそれぞれの信号は、図３の同一符号の信号に対応している。
ステップＳ４０１では、受信パケット情報ｓｅｎｄ信号が入力されたとき、すなわち受信パケット情報ｓｅｎｄ信号が「０」となったときに動作を開始し、比較回路制御部３０１が状態「Ｉｄｌｅ」から状態「ＳＴ１」に遷移する。
ステップＳ４０２では、比較回路制御部３０１の状態が「ＳＴ１」に遷移したことにより、比較部３０３の比較部出力３６０がクリアされ、カウンタ３０２の初期値がセットされる。ここでは、カウンタ出力３５８が、「１２７」となる。
【００３１】
ステップＳ４０３では、比較部３０３が、ルール情報ごとに、ルール情報と受信パケット情報とを比較する。このとき、第２Ｃ素子３１１では、ルール情報ｓｅｎｄ信号が「０」となり、これに伴い、ルール情報ａｃｋ信号が「０」となり、第２Ｃ素子３１１にルール情報ｓｅｎｄ信号を送出したＣ素子がそのルール情報ａｃｋ信号を受信し、ルール情報ｓｅｎｄ信号を「１」にし、それが遅延素子で遅延された後、第２Ｃ素子３１１のルール情報ｓｅｎｄ信号が「１」になったとき、ラッチ信号が生成され、これに伴いルール情報ａｃｋ信号が「１」となったときラッチ信号が立ち下がる。またこの際、カウンタの値が１ずつダウンカウントされる。なお、本実施形態では、１２８個のルール情報があるので１２８回の比較が行われることになる。
ステップＳ４０４では、１２８回の比較が行われて、カウンタレジスタ出力３５９が「０」となった場合に、比較回路制御部３０１の状態が「ＳＴ１」から「ＳＴ２」に遷移する。
ステップＳ４０５では、比較回路制御部３０１の状態「ＳＴ２」では、ｏｕｔ０信号が「０」となる。ｏｕｔ０信号と受信パケット情報ｓｅｎｄ信号とが入力されたＯＲゲート３１２から、受信パケット情報ｓｅｎｄ信号３６２が「０」となって第１Ｃ素子３１０に送られる。その後、第１Ｃ素子３１０において、受信パケット情報ｓｅｎｄ信号３５４が「０」となる。
【００３２】
ステップＳ４０６では、受信パケット情報ｓｅｎｄ信号３６２の入力が「０」であり、受信パケット情報ａｃｋ信号の入力（図示せず）が「１」である場合、第１Ｃ素子３１０は、出力である受信パケット情報ａｃｋ信号３６３を「０」とし、前のステージに受信パケット情報ｓｅｎｄ信号を受け取ったことを通知する。
ステップＳ４０７では、前のステージからの受信パケット情報ｓｅｎｄ信号３５４が「１」となり、その信号が第１Ｃ素子３１０で受信されると、第１Ｃ素子３１０は、ラッチ信号を生成し、受信パケット情報と優先ルール番号とが第４レジスタ３０７に保持され、比較部レジスタ出力３６１となる。ここでは、ルール番号「１３」であるルール情報が優先ルール番号として選択される例を示す。
ステップＳ４０８では、一連のハンドシェイクを終了するため、第１Ｃ素子３１０は、受信パケット情報ａｃｋ信号３６３を「１」にして、前のステージの比較回路に処理が終了したことを通知する。
比較部３０３は、以上のステップを新たな受信パケット情報を受け取るたびに繰り返し行う。
【００３３】
次に、比較部３０３の詳細な動作について図５を参照して説明する。
比較部３０３は、パケット情報比較部５０１、優先度値比較部５０２、論理積部５０３、第１選択部５０４および第２選択部５０５を含む。
パケット情報比較部５０１は、受信パケット情報振分け部２０１または前のステージの比較回路２０２から受信パケット情報を、ルール読出し部２０６からルール情報をそれぞれ受け取り、受信パケット情報とルール情報中の比較情報とを比較して一致するかどうかを判定する。パケット情報比較部５０１は、受信パケット情報が一致する場合には、「１」を出力し、受信パケット情報が一致しない場合には、「０」を出力する。
優先度値比較部５０２は、ルール読出し回路２０３からルール情報中の優先度値を、優先度レジスタからの出力をそれぞれ受け取り、優先度レジスタ値と優先度値とを比較する。優先度レジスタ値が優先度値よりも大きい（優先度値の方が優先度レジスタ値よりも優先度が高い）場合は、「１」を出力し、優先度レジスタ値が優先度値以下である場合は、「０」を出力する。
【００３４】
論理積５０３は、パケット情報比較部５０１からの出力と優先度値比較部５０２からの出力とを受け取り、これらを論理積して１ビットの更新信号を生成する。比較回路制御部３０１の状態「ＳＴ１」の場合、受信パケット情報とルール情報とが一致し、かつ優先度値が優先度レジスタ値より優先（優先値が小さい）である場合、すわなち、パケット情報比較部５０１および優先度値比較部５０２の値が共に「１」である場合、論理積部５０３は、値が「１」である更新信号を生成する。パケット情報比較部５０１および優先度値比較部５０２の出力がどちらか少なくとも「０」である場合は、論理積部５０３は、値が「０」である更新番号が生成される。
第１選択部５０４は、比較回路制御部３０１の状態が「Ｉｄｌｅ」の場合、ルール番号初期値を設定する。更新信号が「０」である場合は、第１選択部５０４において「１」が選択され、番号レジスタ値はそのまま保持される。更新信号が「１」である場合は、第１選択部５０４において「２」が選択され、番号レジスタ値が受け取った新たなルール番号で書き換えられる。
【００３５】
第２選択部５０５は、比較回路制御部３０１の状態が「Ｉｄｌｅ」の場合、優先度初期値を設定する。更新信号が「０」である場合は、第２選択部５０５において「１」が選択され、優先度レジスタ値はそのまま保持される。更新信号が「１」である場合は、第２選択部５０５において「２」が選択され、優先度レジスタ値が受け取った新たな優先度値で書き換えられる。
以上の処理を全てのルール情報について比較し、全てのルール情報について完了した場合、受信パケット情報がルール情報に一致し、かつ最も優先度の高いルール番号を有する優先ルール番号を得ることができる。比較回路制御部３０１の状態が「ＳＴ２」の場合、次のステージに比較回路２０２の検索結果となるルール番号を保持し続ける。
なお、優先度レジスタおよび番号レジスタは、値を保持できる記憶素子であればよく、本実施形態では、第３レジスタ３０６のことである。
【００３６】
次に、ルール読出し部２０６およびルール蓄積部２０７の一例について図６を参照して説明する。
ルール読出し部２０６は、有限ステートマシン６０１（以下、ＦＳＭ（Finite State Machine））、ＡＮＤゲート６０２、第１Ｃ素子（Ｃ１）６０３、第２Ｃ素子（Ｃ２−０、Ｃ２−１、Ｃ２−Ｎ）６０４、マージ回路６０５、および遅延素子（Ｄ２）６０６を含む。なお、Ｎは２以上の自然数である。
【００３７】
ルール蓄積部２０７は、インクリメント素子６５１、アドレスレジスタ６５２、およびＳＲＡＭ６５３を含む。
ＡＮＤゲート６０２は、受信パケット情報ｓｅｎｄ信号を論理積する。
ＦＳＭ６０１は、各比較回路２０２から「０」である受信パケット情報ｓｅｎｄ信号を受け取ることにより動作を開始する。本回路は、複数の比較回路２０２のうち１つでも受信パケット情報を受け取ったとき、つまり「０」である受信パケット情報ｓｅｎｄ信号を１つでも受け取ったときに動作を開始する必要があるため、各比較回路２０２からの受信パケット情報ｓｅｎｄ信号は、ＡＮＤゲート６０２により論理積されてＦＳＭ６０１に入力される。これにより、ＦＳＭ６０１は、いずれか１つでも受信パケット情報を受け取った比較回路２０２があることを認識することができる。
【００３８】
第１Ｃ素子６０３は、第２Ｃ素子６０４（Ｃ２−０、Ｃ２−１、Ｃ２−Ｎ）のルール情報ａｃｋ信号がマージされた信号を受け取る。そして、第１Ｃ素子６０３は、第２Ｃ素子６０４（Ｃ２−０からＣ２−Ｎまで）のマージされたルール情報ａｃｋ信号が１のとき、すなわち、前回第２Ｃ素子が制御するレジスタに送出したルール情報が各比較回路２０２へ送出完了し、比較処理が完了し第２Ｃ素子が次のルール情報を受け入れ可能になった場合、ｋｅｙ＿ａｃｋを「１」にし、送信要求を受け入れられることをＦＳＭ６０１へ送る。「１」のｋｅｙ＿ａｃｋを受けたＦＳＭ６０１により「０」となり、ＦＳＭと第１Ｃ素子との間のハンドシェイクにより、ｋｅｙ＿ｒｅｑが「１」、ｋｅｙ＿ａｃｋが「０」を受けた第１Ｃ素子６０３は、ルール蓄積部２０７のアドレスレジスタ６５２の値を更新または保持するためのラッチ信号をアドレスレジスタ６５２へ送る。
【００３９】
第２Ｃ素子６０４（Ｃ２−０からＣ２−Ｎ）は、それぞれが接続される比較回路２０２からのルール情報ａｃｋ信号が「１」の場合、すなわち各々の比較回路２０２において先に送ったルール情報と受信パケット情報との比較が完了している場合に、遅延素子Ｄ２により遅延させられたＣ１のｓｅｎｄ信号が「０」すなわち、各比較回路へのルール情報送信要求があった場合、ルール情報ａｃｋ信号を「０」にして、ｓｅｎｄ信号を受け取ったことをマージ回路６０５を介してＣ１に送る。また、ハンドシェイクにより「１」となったルール情報ｓｅｎｄ信号を受信した各第２Ｃ素子６０４は、ルール蓄積部２０７から読み出したルール情報をレジスタに蓄積または保存するためのラッチ信号を生成する。これと同時に、各比較回路２０２に対して新たなルール情報で比較を開始させるために、ルール情報ｓｅｎｄ信号を各比較回路２０２に送る。
【００４０】
マージ回路６０５は、例えば、ＭｕｌｌｅｒのＣ素子であり、第２Ｃ素子６０４のルール情報ａｃｋ信号をマージする。ＭｕｌｌｅｒのＣ素子を用いる理由は、複数入力されるルール情報ａｃｋ信号の中で、最後に立ち下がった（１から０への遷移）信号に合わせて出力を立ち下げ、最後に立ち上がった（０から１への遷移）信号に合わせて出力を立ち上げるためである。つまり、第２Ｃ素子のＣ２−０からＣ２−Ｎが受け取ったルール情報ａｃｋ信号うち、どのａｃｋ出力が遅くなるのかわからないのでＭｕｌｌｅｒのＣ素子を用いることが望ましい。マージされたルール情報ａｃｋ信号は、Ｃ２−０からＣ２−Ｎのａｃｋ出力の中で最も遅いルール情報ａｃｋ信号に合わせることができるので、全ての比較回路が１つのルール情報と受信パケット情報との比較を完了したことを保証して次のルール情報を各比較回路に送ることができ、誤動作をなくすことができる。
遅延素子（Ｄ２）６０６は、ルール蓄積部２０７のメモリアクセス遅延にあわせた遅延量を加えて第２Ｃ素子６０４へ送る。
インクリメント素子６５１は、アドレスレジスタ６５２の値を１つインクリメントする。
アドレスレジスタ６５２は、インクリメント素子６５１により更新の度にアドレスがインクリメントされるので、本動作を繰り返すことにより、ＳＲＡＭ６５３に記憶されるルール情報を順次変更することができる。
ＳＲＡＭ６５３は、複数のルール情報が記憶されるメモリであり、インクリメントされたアドレスレジスタ６５１の値に応じた次のルール番号となるアドレス値のルール情報を出力する。
【００４１】
次に、ルール読出し部２０６におけるＦＳＭ６０１の状態について図７を参照して説明する。
図７はＦＳＭ６０１の状態遷移図を示し、「Ｉｄｌｅ」、「ｒｅｑ＿Ｌ」および「ｒｅｑ＿Ｈ」の３つの状態が存在する。
状態「Ｉｄｌｅ」において、ルール情報ｓｅｎｄ信号およびルール情報ａｃｋ信号ともに１である場合で、かつ、いずれかの比較回路２０２からの検索要求がある場合（すなわち、受信パケット情報ｓｅｎｄ信号が「０」（ｓｅａｒｃｈ＿ｒｅｑが「０」）となった場合）、状態「ｒｅｑ＿Ｌ」に遷移する（ステップＳ７０１）。ＦＳＭ６０１の状態が状態「Ｒｅｑ＿Ｌ」に遷移した場合、ルール情報を送るためにルール情報ｓｅｎｄ信号を「０」にする（ｋｅｙ＿ｒｅｑを０にする）。次段は読み出しアドレスを生成する回路となっており、前回の読み出しアドレス生成が終了している場合、すぐにａｃｋ信号を返す（ｋｅｙ＿ａｃｋが０）。ＦＳＭ６０１におけるｋｅｙ＿ｒｅｑおよびｋｅｙ＿ａｃｋがともに０となるため、状態が「ｒｅｑ＿Ｈ」に遷移する（ステップＳ７０２）。状態「ｒｅｑ＿Ｈ」では、ルール情報ｓｅｎｄ信号を１にし、ルール情報ａｃｋ信号が１になるタイミングを監視し、さらに、ｓｅａｒｃｈ＿ｒｅｑの状態により、状態「Ｉｄｌｅ」に遷移するか（ステップＳ７０３）、状態「ｒｅｑ＿Ｌ」に遷移し（ステップＳ７０４）、次のルール番号（読み出しアドレス）となるルール情報を送るため、ルール情報ｓｅｎｄ信号を０にする（ｋｅｙ＿ｒｅｑを０にする）。「Ｒｅｑ＿Ｌ」、「ｒｅｑ＿Ｈ」の繰り返しにより次々と読み出しアドレスを生成する。但し、受信パケットｓｅｎｄ信号が「１」（ｓｅａｒｃｈ＿ｒｅｑが「１」）であり、どの比較回路２０２においても比較処理を行わないような場合には、状態「Ｉｄｌｅ」に戻り、次の検索要求が来るまでルール情報の送出を停止する。これによって、無駄な電力消費を押さえることができる。
【００４２】
ここで、一般的な非同期回路の一例である、一線式束データ方式の非同期回路ブロックと各信号のタイミングチャートを図８に示す。図８上側は、一般的な非同期回路のブロック図の一例を示し、図８下側は、図８上側のブロック図におけるタイミングチャートを示す。
非同期回路は、同期回路のように各レジスタに供給されるクロック信号に代わり、レジスタと対に置かれるＣ素子間のハンドシェイクによってレジスタのラッチ信号を生成して、処理を行う。レジスタに供給されるラッチ信号がすぐ近くに配置される制御回路から供給される点と、データが入力されない場合は制御回路間のハンドシェイクが発生せずラッチ信号も生成されない点から、非同期回路のほうが、クロック信号を用いた同期回路の電力消費よりも電力消費が少なく、大幅に削減することができる。
【００４３】
以下、基本的な束データ方式の非同期回路とＣ素子の動作タイミングとについて説明する。
ｉ−１ステージからの送信要求を受け取るとｉステージでの処理が開始される。はじめに、ｓｅｎｄ ｉ ｏｕｔが０となり（ステップＳ１）、ｄｅｌａｙ時間経過後ｓｅｎｄ ｉ ｉｎが０となる（ステップＳ２）。そのときのａｃｋ ｉ＋１ ｉｎが１なので、送信要求を受け取ったことを伝えるべく、ａｃｋ ｉ ｏｕｔを０とする（ステップＳ３）。このとき、ａｃｋ ｉ ｉｎも０となる（ステップＳ４）。それと同時に、ｓｅｎｄ ｉ＋１ ｏｕｔを０にする（ステップＳ５）。ａｃｋ ｉ ｉｎ信号は０となっているので、ｓｅｎｄ ｉ ｏｕｔが１となる（ステップＳ８０６）。続いて、ｓｅｎｄ ｉ ｉｎは、ｄｅｌａｙ時間遅延して１になる（ステップＳ７）。このタイミングでラッチまたはレジスタにおいてデータの更新または保持を行うために、ｃｌｋ ｉが立ち上がる（ステップＳ８）。その後ａｃｋ ｉ ｏｕｔは、１に変わり（ステップＳ９）、ｃｌｋ ｉをたち下げる。このとき、ａｃｋ ｉ ｉｎも１となる（ステップＳ１０）。以上によりデータパスの信号伝播（処理）が制御される。
【００４４】
続いて、ｓｅｎｄ ｉ ｏｕｔを０にして次のデータ処理を開始しようとする場合（ステップＳ１３）、ｄｅｌａｙ時間遅れて、ｓｅｎｄ ｉ ｉｎが１になる（ステップＳ１４）。このとき、ｓｅｎｄ ｉ＋１ ｏｕｔは１であり（ステップＳ１２）、次のステージからのａｃｋ ｉ＋１ ｉｎは０であるため（ステップＳ１１）、次段で先ほどのデータ伝播（処理）が完了していないことがわかる。そのため、ａｃｋ ｉ＋１ ｉｎが１になるまで、ａｃｋ ｉ ｏｕｔを０にするのを待つ。ａｃｋ ｉ＋１ ｉｎが１になり（ステップＳ１５）、その後ａｃｋ ｉ ｏｕｔが０となり（ステップＳ１６）、データ処理が完了したことが通知されたときに、ｓｅｎｄ ｉ＋１ ｏｕｔを０にして（ステップＳ１７）、次段にデータを転送する。その後は同様の動作を行えばよい。
【００４５】
以上に示した本実施形態に係る非同期動作検索回路によれば、クロック信号を必要とせずにハンドシェイクにより制御を行うことができるので、同期回路よりも大幅に低い消費電力で検索回路を動作させることができる。また、全ての比較回路からのａｃｋ信号を受信してから次のルール情報を送ることで、誤動作することがなく正確な検索処理を行うことができる。さらに、ステージごとに全てのルール情報と比較完了してから検索結果を出力することにより、正確な検索処理を行うことができる。よって、処理性能が高く低消費電力で検索処理を行うことができる。
【００４６】
要するにこの発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００４７】
１００・・・パケット処理回路、１０１，１０８・・・ネットワークインターフェース、１０２・・・パーサ、１０３・・・フレームコントローラ、１０４・・・バッファメモリ、１０５・・・非同期検索回路、１０６・・・ＱｏＳ部、１０７・・・フレーム生成部、１０８・・・ネットワークインターフェース、２０１・・・受信パケット振分け部、２０２−１，２０２−２，２０２−３・・・比較回路、２０３・・・ルール読出し回路、２０４・・・結果出力部、２０５・・・検索結果蓄積部、２０６・・・ルール読出し部、２０７・・・ルール蓄積部、３０１・・・比較回路制御部、３０２・・・カウンタ、３０３・・・比較部、３０４，３０５，３０６，３０７・・・レジスタ、３０８，３０９・・・遅延素子、３１０，３１１，６０３，６０４・・・Ｃ素子、３１２・・・ＯＲゲート、５０１・・・パケット情報比較部、５０２・・・優先度値比較部、５０３・・・論理積部、５０４，５０５・・・選択部、６０１・・・有限ステートマシン（ＦＳＭ）、６０２・・・ＡＮＤゲート、６０５・・・マージ回路、６５１・・・アドレスレジスタ、６５２・・・ＳＲＡＭ、６５３・・・インクリメント素子。
【特許請求の範囲】
【請求項１】
パケットの通過を許可するか否かを判定する検索種別に対応した複数のルール情報のうちの第１ルール情報と、受信したパケットに関する情報とを比較する比較部を具備し、前記比較部は複数あり、比較部ごとに受信したパケットが異なり、
比較部ごとに、複数の比較部で共通する前記第１ルール情報を受信した場合、前記比較部に比較処理をさせるように制御し、該第１ルール情報とパケットに関する情報との比較が完了した場合または該パケットを受信しなかった場合に処理が完了したことを示す第２信号を生成する比較回路制御部と、
前記複数の比較部からの全ての第２信号を受信した場合、前記第１ルール情報とは異なる第２ルール情報を読み出し、該第２ルール情報を前記複数の比較部に送信する読出し部と、をさらに具備し、
前記比較回路制御部は、前記複数のルール情報を全て受信するまで、前記比較部に順次前記比較処理を行わせ、前記第２信号を生成することを特徴とする非同期動作検索回路。
【請求項２】
前記比較回路制御部は、前記比較部において全てのルール情報と前記パケット情報との比較が完了したのちに、前記パケット情報と一致しかつ優先度が最も高い優先ルール番号を出力するように制御することを特徴とする請求項１に記載の非同期動作検索回路。
【請求項３】
前記読出し部は、少なくとも１つの前記比較部において該比較部に対応するパケットが受信されているときに、前記第２ルール情報を読み出すように制御することを特徴とする請求項１または請求項２に記載の非同期動作検索回路。
【請求項１】
パケットの通過を許可するか否かを判定する検索種別に対応した複数のルール情報のうちの第１ルール情報と、受信したパケットに関する情報とを比較する比較部を具備し、前記比較部は複数あり、比較部ごとに受信したパケットが異なり、
比較部ごとに、複数の比較部で共通する前記第１ルール情報を受信した場合、前記比較部に比較処理をさせるように制御し、該第１ルール情報とパケットに関する情報との比較が完了した場合または該パケットを受信しなかった場合に処理が完了したことを示す第２信号を生成する比較回路制御部と、
前記複数の比較部からの全ての第２信号を受信した場合、前記第１ルール情報とは異なる第２ルール情報を読み出し、該第２ルール情報を前記複数の比較部に送信する読出し部と、をさらに具備し、
前記比較回路制御部は、前記複数のルール情報を全て受信するまで、前記比較部に順次前記比較処理を行わせ、前記第２信号を生成することを特徴とする非同期動作検索回路。
【請求項２】
前記比較回路制御部は、前記比較部において全てのルール情報と前記パケット情報との比較が完了したのちに、前記パケット情報と一致しかつ優先度が最も高い優先ルール番号を出力するように制御することを特徴とする請求項１に記載の非同期動作検索回路。
【請求項３】
前記読出し部は、少なくとも１つの前記比較部において該比較部に対応するパケットが受信されているときに、前記第２ルール情報を読み出すように制御することを特徴とする請求項１または請求項２に記載の非同期動作検索回路。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−５３４２（Ｐ２０１３−５３４２Ａ）
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願番号】特願２０１１−１３６６２７（Ｐ２０１１−１３６６２７）
【出願日】平成２３年６月２０日（２０１１．６．２０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願日】平成２３年６月２０日（２０１１．６．２０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]