(57)【特許請求の範囲】
【請求項１】
検索したいデータを格納するエントリデータとエントリデータの各ビットを検索対象とするかどうかを規定するマスクデータとを有するマスク付き連想メモリと、検索データを入力して前記マスク付き連想メモリの検索を行う連想メモリ検索手段と、前記マスク付き連想メモリに格納されたエントリデータの更新を行う連想メモリ更新手段とを有するマスク付き連想メモリ検索システムにおいて、
前記マスク付き連想メモリに格納される前記エントリのデータ内に作業用ビットを設け、
前記連想メモリ更新手段は、追加もしくは削除するエントリの前記作業用ビットの値と前記作業用ビットに対応する作業用ビットマスクの値を設定して前記マスク付き連想メモリに入力する手段と、前記検索データ内に設定される検索作業ビットの値を前記連想メモリ検索手段に通知する手段を備え、
前記連想メモリ検索手段は、前記連想メモリ更新手段から通知された検索作業ビットの値を、前記マスク付き連想メモリに入力する検索データに設定する手段を備え
ていることを特徴とするマスク付き連想メモリ検索システム。
【請求項２】
前記作業用ビットは１ビットによって構成されていることを特徴とする請求項１記載のマスク付き連想メモリ検索システム。
【請求項３】
前記作業用ビットは複数のビットによって構成されていることを特徴とする請求項１記載のマスク付き連想メモリ検索システム。
【請求項４】
前記マスク付き連想メモリに格納され前記作業用ビットマスクの値が「一致検索不要」を示す値に設定されているエントリデータは、前記検索作業ビットの値に関係なく検索対象とし、前記マスク付き連想メモリに格納され前記作業用ビットマスクの値が「一致検索要」を示す値に設定されているエントリデータは、前記作業用ビットの値が前記検索作業ビットの値と一致したエントリデータは検索対象とするが、前記作業用ビットの値と前記検索作業ビットの値が不一致のエントリデータは検索対象外とすることを特徴とする請求項１〜３のいずれかに記載のマスク付き連想メモリ検索システム。
【請求項５】
前記連想メモリ更新手段はエントリ追加手段を備えており、前記マスク付き連想メモリに一つもしくは複数のエントリを追加する際には、前記検索作業ビットが「作業完」を示す値に設定されている状態で、追加するエントリの前記作業用ビット及び前記作業用ビットに対応する作業用ビットマスクの値をそれぞれ「作業中」を示す値及び「一致検索要」を示す値に設定して前記マスク付き連想メモリに格納することを特徴とする請求項４記載のマスク付き連想メモリ検索システム。
【請求項６】
前記エントリ追加手段は、前記エントリの追加を完了した時点で、前記連想メモリ検索手段に対して前記検索用の作業ビットの値を「作業中」を示す値に変更することを要求し、前記連想メモリ検索手段は、前記要求に基づき検索データの前記検索用の作業ビットの値を「作業中」を示す値に変更して検索することを特徴とする請求項５記載のマスク付き連想メモリ検索システム。
【請求項７】
前記エントリ追加手段は、前記追加したエントリの作業用ビット及び該作業用ビット対応する作業用ビットマスクの値をそれぞれ「作業完」を示す値及び「一致検索不要」を示す値に設定した後、前記連想メモリ検索手段に対して前記検索用の作業ビットの値を「作業完」を示す値に変更することを要求し、前記連想メモリ検索手段は、前記要求に基づき検索データの前記検索用の作業ビットの値を「作業完」を示す値に変更して検索することを特徴とする請求項６記載のマスク付き連想メモリ検索システム。
【請求項８】
前記連想メモリ更新手段はエントリ削除手段を備えており、前記マスク付き連想メモリから一つもしくは複数のエントリを削除する際には、前記検索作業ビットが「作業完」を示す値に設定されている状態で、削除対象のエントリの前記作業用ビット及び該作業用ビットに対応する作業用ビットマスクの値をそれぞれ「作業完」を示す値及び「一致検索要」を示す値に設定することを特徴とする請求項４記載のマスク付き連想メモリ検索システム。
【請求項９】
前記エントリ削除手段は、削除対象エントリの更新を完了した時点で、前記連想メモリ検索手段に対して前記検索用の作業ビットの値を「作業中」を示す値に変更することを要求し、前記連想メモリ検索手段は、前記要求に基づき検索データの前記検索用の作業ビットの値を「作業中」を示す値に変更して検索することを特徴とする請求項８記載のマスク付き連想メモリ検索システム。
【請求項１０】
前記エントリ削除手段は、前記検索用の作業ビットの値が「作業中」である状態において、前記更新した削除対象エントリを前記マスク付き連想メモリから削除した後、前記連想メモリ検索手段に対して前記検索用の作業ビットの値を「作業完」を示す値に変更することを要求し、前記連想メモリ検索手段は、前記要求に基づき検索データの前記検索用の作業ビットの値を「作業完」を示す値に変更して検索することを特徴とする請求項９記載のマスク付き連想メモリ検索システム。
【請求項１１】
前記連想メモリ更新手段はエントリ追加手段とエントリ削除手段を備えており、前記検索作業ビットが「作業完」を示す値に設定されている状態で、追加するエントリの前記作業用ビット及び前記作業用ビットに対応する作業用ビットマスクの値をそれぞれ「作業中」を示す値及び「一致検索要」を示す値に設定して前記マスク付き連想メモリに格納するとともに、削除対象のエントリの前記作業用ビット及び前記作業用ビットに対応する作業用ビットマスクの値をそれぞれ「作業完」を示す値及び「一致検索要」を示す値に設定した後、前記連想メモリ検索手段に対して前記検索用の作業ビットの値を「作業中」を示す値に変更することを要求し、前記連想メモリ検索手段は、前記要求に基づき検索データの前記検索用の作業ビットの値を「作業中」を示す値に変更して検索することを特徴とする請求項４記載のマスク付き連想メモリ検索システム。
【請求項１２】
前記連想メモリ更新手段は、前記検索用の作業ビットの値が「作業中」である状態において、前記追加したエントリの作業用ビット及び該作業用ビットに対応する作業用ビットマスクの値をそれぞれ「作業完」を示す値及び「一致検索不要」を示す値に設定するとともに、前記更新した削除対象エントリを前記マスク付き連想メモリから削除した後、前記連想メモリ検索手段に対して前記検索用の作業ビットの値を「作業完」を示す値に変更することを要求し、前記連想メモリ検索手段は、前記要求に基づき検索データの前記検索作業ビットの値を「作業完」を示す値に変更して検索することを特徴とする請求項１１記載のマスク付き連想メモリ検索システム。
【請求項１３】
請求１〜１０に記載の連想メモリ検索システムを用いてデータの転送先を決定する手段が構成されていることを特徴とする通信装置。
【請求項１４】
請求１〜１０に記載の連想メモリ検索システムを用いてパケットの優先度もしくは転送順序を決定する手段が構成されていることを特徴とする通信装置。
【請求項１５】
請求項１１または請求項１２に記載の通信装置を用いて、ネットワークに接続された機器間でデータの通信が行われていることを特徴とするネットワークシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マスク付き連想メモリ検索システムに関し、特に同時に複数のエントリの追加および削除処理を行うマスク付き連想メモリ検索システムに関する。
【０００２】
【従来の技術】
連想メモリは、アドレスを用いてワードへ読み書きできる機能を有する他に、検索キーを入力して検索キーに一致するワードを検索して、そのアドレスを出力することのできるメモリである。
【０００３】
特にマスク付き連想メモリは、ワードの他に各ワードのそれぞれのビットに対応するマスクデータを有することのできるメモリであり、検索キーの一部分のみを比較対象として、ワードと一致するかを検索することが可能である。
【０００４】
最近の急速なインターネットの普及によるルーティングテーブルの経路数の増加によって引き起こされる経路検索処理負荷を削減するための手段の一手法として、このマスク付き連想メモリが利用されている。
【０００５】
複数の入出力ポートを持つＩＰルーティング処理装置（ルータ）を用いて、ＩＰルーティング処理を行うには、入力ポートに到着したパケットのヘッダ情報から、３２ビットの「相手ＩＰアドレス」を検出し、この検出された相手ＩＰアドレスに適合する出力ポートに、上記到着したパケットを送出する必要があり、つまり、到着したパケットを送出すべき出力ポートを決定する必要がある。
【０００６】
この場合、上記「相手ＩＰアドレス」を検索キーとし、ルータ内に存在するルーティングテーブル中の項目を検索し、上記検索キーと一致した上記項目に登録されている出力ポートを選択することによって、上記到着したパケットを送出すべき出力ポートを決定する。
【０００７】
この出力ポートを決定する処理としては、例えば、特開平１１−１０２５８９号公報等に記載のベストマッチ方式が採用されている。
【０００８】
このベストマッチ処理は、まず、ルーティングテーブル内のＩＰアドレスを、そのＩＰアドレス毎に１対１対応で、別途用意されているネットマスク情報によって、「相手ＩＰアドレス」の一部のビットをマッチングの対象から除外するマスク処理を行った後、このマスク処理されたデータを検索キーとして、被検索データと比較処理し、複数の候補とマッチすると、マスクの長さ（マスクのビット幅）が最も長いデータ（マッチング対象から除外したビット幅が最も短いデータ）を最優先候補として採用する処理である。
【０００９】
例えば、マスクデータ上、「１」の立っているビットが比較対象であるとした場合、マスクデータが「11111111 11111111 11111111 00000000」である３２ビット幅のデータ（比較対照が２４ビットであるデータ）と、マスクデータが「11111111 11111111 00000000 00000000」である３２ビット幅のデータ（比較対照が１６ビットであるデータ）とに、検索キーがマッチした場合、比較対象が２４ビットである前者のデータを選択する。
【００１０】
このベストマッチ処理を高速に実施するために、マスク付き連想メモリが利用されている。マスク付き連想メモリでは、入力する検索キーに対して複数の格納エントリが一致することがあり得る。複数の格納エントリが一致した場合の検索結果は、マスク付き連想メモリの種類により異なる。例えば以下のようなマスク付き連想メモリが存在する。
（１）複数エントリが一致した場合はエラーになるもの
（２）もっとも値の小さいアドレスに格納されたエントリを出力するもの
（３）エントリごとに設定された優先度に従って出力するもの。
【００１１】
また、ＩＰアドレスのベストマッチ検索に適用するために、特開平１１−７３７８２号公報記載の発明では、検索キーに一致する格納エントリの中でマスク長の最も長いエントリを出力している。
【００１２】
以上のように、マスク付き連想メモリでは、検索エントリと一致する格納エントリが必ずしもヒットするとは限らず、ある格納エントリが検索でヒットするかは、他の格納エントリの値に影響されることがある。従って、マスク付き連想メモリに複数のエントリの追加および削除を行う際には、更新処理の間に予期しない検索結果が発生することの無いようにするために、複数のエントリを同時に検索対象もしくは検索対象外とする機能を有することが望ましい。
【００１３】
そのため、複数の格納エントリを同時に追加および削除する必要がある場合、従来は図１２に示す連想メモリ検索システムが利用されている。
【００１４】
この従来の連想メモリ検索システムは、連想メモリ検索手段１”と連想メモリ更新手段２”と第１のマスク付き連想メモリ３−１と第２のマスク付き連想メモリ３−２を有する。連想メモリ検索手段１”は、第１のマスク付き連想メモリ３−１もしくは第２のマスク付き連想メモリ３−２のどちらかに対して、検索データを入力して検索を行う。
【００１５】
連想メモリ検索手段１”が、第１のマスク付き連想メモリ３−１を利用して検索を行っている状態で、複数の格納エントリの追加もしくは削除を行って検索をする必要がある場合には、連想メモリ更新手段２”が、第１のマスク付き連想メモリ３−１にもともと格納されているエントリの内容に新たに追加および削除するエントリの内容を反映した全格納エントリを第２のマスク付き連想メモリ３−２に対して書き込みを行った後、連想メモリ検索手段１”は、検索対象を第２のマスク付き連想メモリ３−２に切り替えて検索を行う。このような制御は一般にバンク切り替え制御と呼ばれている。
【００１６】
【発明が解決しようとする課題】
この従来の、マスク付き連想メモリに対する複数のエントリの追加・削除を同時に実施するバンク切り替え制御方式では、エントリの更新前と更新後において、検索対象となるマスク付き連想メモリが異なるため、更新前に検索対象となるマスク付き連想メモリと、更新後に検索対象となるマスク付き連想メモリの２つが必要となり、検索するために必要なエントリ数の２倍のエントリ数を有するマスク付き連想メモリを備えなければならない。
【００１７】
また、更新処理の際には、内容に変更の無いエントリを含めて、全てのエントリを更新後に検索対象となるマスク付き連想メモリに書き込む必要があるため、更新する必要の無いエントリに関しても、マスク付き連想メモリに対して書き込まなければならず、更新処理に時間がかかるという問題がある。
【００１８】
本発明の目的は、上記問題点に鑑み、一つのマスク付き連想メモリによって複数の格納エントリを同時に追加および削除可能とする手段を提供することにある。
【００１９】
本発明の他の目的は、内容に変更の無いエントリの再書き込みを不要とし、追加および削除対象となるエントリのみを更新しながら、同一のタイミングで検索対象もしくは検索対象外となるように制御することにより、更新処理時間の短縮化を図ることにある。
【００２０】
【課題を解決するための手段】
本発明のマスク付き連想メモリ検索システムは、マスク付き連想メモリ内のデータの１ビットもしくは複数ビットを作業ビットとして利用することにより、一つのマスク付き連想メモリを用いて複数エントリの追加および削除を一度に実施することを特徴とする。
【００２１】
具体的には、マスク付き連想メモリ内の格納エントリに、１ビットの作業ビットと１ビットの作業ビットマスクを設け、一方、検索データにも１ビットの検索作業ビットを設ける。そして、検索データの作業ビットが「０」の状態で、追加対象のエントリの作業ビット及び作業ビットマスクを「１」に設定して追加処理を行い、また、削除対象のエントリの作業ビットを「０」に、作業ビットマスクを「１」に設定して更新処理を行う。
【００２２】
この状態では、追加処理されたエントリ及び削除するために更新処理されたエントリの作業ビットマスクがいずれも「１」に設定されているため、これらのエントリについては作業ビットの一致検索が行われる。更新処理されたエントリの作業ビットは「０」であり検索データの作業ビットと一致しているので検索対象となるが、追加処理されたエントリの作業ビットは「１」であり検索データの作業ビットと一致しないので検索対象外となる。
【００２３】
更新及び追加処理が終了した後、検索作業ビットの値を「１」に変更すると、その時点からは、更新処理されたエントリは検索作業ビットが不一致となって検索対象外となり、一方、追加処理されたエントリは検索作業ビットが一致するので検索対象となる。従って、追加対象のエントリを検索対象にし、削除対象のエントリを検索対象外とする処理を同一タイミングで実施することができる。
【００２４】
その後、削除対象のエントリを削除し、また、追加対象のエントリの作業ビット及び作業ビットマスクを「０」に変更して検索作業ビットとの比較を不要とした後、検索作業ビットの値を「０」に戻すことにより、次の更新処理が可能な状態にする。
【００２５】
即ち本発明によれば、まず、検索作業ビットが「０」の状態で、作業ビットの値を「１」、作業ビットマスクの値を「０」にしてエントリを追加しているので、エントリの追加途中において、追加エントリが検索対象となることはない。
【００２６】
また、検索作業ビットが「０」の状態で、削除対象エントリの作業ビットの値を「０」、作業ビットマスクの値を「１」にする処理では、削除対象エントリの作業ビットの値と検索作業ビットの値が一致しているので、削除対象エントリが検索対象外となることはなく、更新及び追加処理中に、それまで検索対象となっているエントリに影響を及ぼすことはない。
【００２７】
更新及び追加処理終了後、検索作業ビットの値を「０」から「１」に変更することにより、それまで検索対象外であった追加対象のエントリが検索対象となると同時に、それまで検索対象であった削除対象エントリが検索対象外となる。
【００２８】
一方、更新対象外のエントリについては、作業ビットマスクの値が「０」に設定されているため、作業ビットの一致検索は行われず、検索作業ビットの値に関係なく、常に検索対象の状態のままである。
【００２９】
【発明の実施の形態】
図１は、本発明の実施の形態を示すマスク付きメモリ検索システムのブロック図である。本発明のマスク付きメモリ検索システムは、マスク付き連想メモリ３と、マスク付き連想メモリ３に対して検索データを入力する連想メモリ検索手段１と、マスク付き連想メモリ３の内容の書き換えを行う連想メモリ更新手段２より構成される。
【００３０】
マスク付き連想メモリ３は、複数の格納エントリ７（第１の格納エントリ７−１，第２の格納エントリ７−２，第３の格納エントリ７−３，第４の格納エントリ７−４，第５の格納エントリ７−５，第６の格納エントリ７−６，…）を有する。格納エントリ７は、データ部分と、各データに対応するマスク部分を有する。該マスクは、マスク付き連想メモリ３の検索処理において、対応するデータのビットが検索の対象であるかどうかを規定する。
【００３１】
なお、説明の便宜上、格納エントリの作業ビットマスクの値が「０」の場合を「一致検索不要」、格納エントリの作業ビットマスクの値が「１」の場合を「一致検索要」と定義する。
【００３２】
本発明のマスク付き連想メモリ検索システムでは、データ部分の１ビットを作業ビット７０（７０−１，７０−２，７０−３，７０−４，７０−５，７０−６）と定義して、作業ビット７０に対応するマスクビットを作業ビットマスク７２（７２−１，７２−２，７２−３，７２−４，７２−５，７２−６）と定義する。作業ビット７０を除く残りのデータ部分はエントリデータ７１（７１−１，７１−２，７１−３，７１−４，７１−５，７１−６）と定義し、エントリデータ７１に対応するマスクビットをエントリマスク７３（７３−１，７３−２，７３−３，７３−４，７３−５，７３−６）と定義する。
【００３３】
エントリデータ７１およびエントリマスク７３は、実際に検索を行いたいデータが格納される。作業ビット７０は、マスク付き連想メモリ３に複数の格納エントリ７を追加する際に、追加したエントリが同時に検索対象となるようにし、また、複数の格納エントリ７を削除する際に、削除対象のエントリを同時に検索対象外となるようにするために利用する。
【００３４】
連想メモリ更新手段２は、更新要求１３が入力されると、マスク付き連想メモリ３内の格納エントリ７の更新を行うために、更新作業ビット６０、更新エントリデータ６１、更新作業ビットマスク６２、更新エントリマスク６３で構成される更新データを作成して、マスク付き連想メモリ３に対して更新要求を送出し、マスク付き連想メモリ３の格納エントリの一つに関して、作業ビット７０を更新作業ビット６０に、エントリデータ７１を更新エントリデータ６１に、作業ビットマスク７２を更新作業ビットマスク６２に、エントリマスク７３を更新エントリマスク６３に置き換える。
【００３５】
連想メモリ検索手段１は、検索要求１２が入力されると、検索データ５を作成して、マスク付き連想メモリ３に入力する。検索データ５は、検索作業ビット５０および、検索したいデータである検索エントリデータ５１より構成される。検索作業ビット５０は、連想メモリ更新手段２から入力される検索作業ビット指定信号４により規定される。
【００３６】
マスク付き連想メモリ３は、連想メモリ検索手段１より検索データ５が入力されると、検索データ５にマッチする格納エントリの検索を行って、その結果を検索結果８として出力する。その際、各格納エントリの作業ビットマスク７２の値が「１」であるものについては、作業ビット７０の値を検索データ５の検索作業ビット５０と比較し、一致しているものは検索対象とし、不一致のものは検索対象外とする。また、格納エントリの作業ビットマスク７２の値が「０」であるものについては、作業ビット７０の値の如何に関わらず検索対象とする。
【００３７】
なお、説明の便宜上、検索作業ビット５０と作業ビット７０は、その値が「０」の場合を「作業完」、その値が「１」の場合を「作業中」と定義する。
【００３８】
図２〜図４は、本発明のマスク付き連想メモリ検索システムの動作を示すフローチャートであり、図２は、複数の格納エントリ７Ａを追加する場合に、同時に検索対象とする方法に関するフローチャート、図３は、複数の格納エントリ７Ｄを削除する場合に、同時に検索対象外とする方法に関するフローチャート、図４は、複数の格納エントリ７Ａの追加し、かつ、複数の格納エントリ７Ｄを削除する場合に、同時に追加する格納エントリ７Ａを検索対象とし、削除する格納エントリ７Ｄを検索対象外とする方法に関するフローチャートである。
【００３９】
初期状態では、図１のマスク付き連想メモリ検索システムに示す通り、検索作業ビット５０の値を「０」とし、全ての格納データ７において、作業ビット７０の値は「０」、作業ビットマスク７２の値は「０」とする。作業ビットマスク７２の値が「０」であるため、全ての格納データ７は、検索作業ビット５０の値に関係なく検索対象となっている。
【００４０】
まず、複数の格納エントリの追加手順を図２のフローチャートを用いて説明する。
【００４１】
連想メモリ更新手段２は、追加要求を受けた格納エントリ７Ａに関して、更新作業ビット６０を「１」、更新作業ビットマスク６２を「１」として更新データ６を作成し、マスク付き連想メモリ３に新しいエントリを追加する（ステップ１０１）。
【００４２】
追加対象の格納エントリ７Ａの書き込みが全て完了していない場合（ステップ１０２：Ｎ）、同様に、更新作業ビット６０を「１」、更新作業ビットマスク６２を「１」とした更新データ６を作成し、マスク付き連想メモリ３に新しい格納エントリ７の追加（ステップ１０１）を繰り返す。
【００４３】
追加した格納エントリ７Ａは、作業ビット７０Ａが「１」（「作業中」）、作業ビットマスク７２Ａが「１」（「一致検索要」）であるため、検索作業ビット５０の値が「１」（「作業中」）で入力された場合のみ検索にマッチする。初期状態では、検索作業ビット５０の値は「０」（「作業完」）であるため、追加した格納エントリ７Ａは全て検索対象外である。
【００４４】
追加したいエントリ７Ａの書き込みが全て完了すると（ステップ１０２：Ｙ）、連想メモリ更新手段２は連想メモリ検索手段１に対して変更要求４を出力して、検索作業ビット５０の値を「１」（「作業中」）に変更するように要求し、連想メモリ検索手段１は、以後の検索に関して、検索作業ビット５０の値を「１」（「作業中」）にして検索を行う（ステップ１０３）。
【００４５】
検索作業ビット５０の値が「１」（「作業中」）に変わることにより、追加した格納エントリ７Ａは同時に検索対象となり、また、以前からマスク付き連想メモリ３内に格納されていたエントリ７は、作業ビットマスク７２が「０」（「一致検索不要」）であるため検索作業ビット５０の値如何に関わらず検索対象となるので、マスク付き連想メモリ３内の全ての格納エントリ７が検索対象となる。
【００４６】
次に、連想メモリ更新手段２は、追加した格納エントリ７Ａに関して、更新作業ビット６０が「０」、更新作業ビットマスク６２が「０」である更新データ６を作成して、マスク付き連想メモリ３内の追加した格納エントリ７Ａの作業ビット７０Ａおよび作業ビットマスク７２Ａの値をそれぞれ「０」（「作業完」及び「一致検索不要」）に更新する（ステップ１０４）。
【００４７】
追加した格納エントリ７Ａに関して、全ての更新処理が完了していない場合（ステップ１０５：Ｎ），同様に、更新作業ビット６０が「０」、更新作業ビットマスク６２が「０」である更新データ６を作成して、マスク付き連想メモリ３内の追加した格納エントリの作業ビット７０Ａおよび作業ビットマスク７２Ａの更新処理（ステップ１０４）を繰り返す。
【００４８】
この更新処理により作業ビットマスク７２Ａの値が「０」となった追加格納エントリ７Ａは、その後検索作業ビット５０の値に関係無く、検索対象となる。従って、この更新処理中に検索対象となる格納データ７に変化は発生しない。
【００４９】
追加した格納エントリ７Ａに関して、全ての更新処理が完了すると（ステップ１０５：Ｙ），連想メモリ更新手段２は、検索作業ビット５０の値を「０」（「作業完」）に変更する要求を行い、連想メモリ検索手段１は、以後の検索に関して、検索作業ビット５０の値を「０」（「作業完」）にして検索を行う（ステップ１０６）。
【００５０】
更新処理が完了すると、マスク付き連想メモリ３内に格納されている全ての格納エントリ７の作業ビット７０および作業ビットマスク７２の値は「０」（「作業完」及び「一致検索不要」）となり、初期状態に戻るので、検索作業ビット５０の値に関係なく、全ての格納エントリが検索対象となる。
【００５１】
次に、複数の格納エントリの削除手順を図３のフローチャートを用いて説明する。
【００５２】
連想メモリ更新手段２は、削除対象である格納エントリ７Ｄに関して、更新作業ビット６０を「０」、更新作業ビットマスク６２を「１」として更新データ６を作成し、マスク付き連想メモリ３内の削除対象である格納エントリ７Ｄに関して、作業ビット７０Ｄの値を「０」（「作業完」）に、作業ビットマスク７２Ｄの値を「１」（「一致検索要」）に更新する（ステップ２０１）。
【００５３】
削除対象であるエントリの更新が全て完了していない場合（ステップ２０２：Ｎ），同様に、マスク付き連想メモリ３内の削除対象である格納エントリ７Ｄに関して、作業ビット７０Ｄの値を「０」に、更新作業ビット７２Ｄの値を「１」に更新（ステップ２０１）する操作を繰り返す。
【００５４】
削除対象の格納エントリ７Ｄは、作業ビット７０Ｄが「０」（「作業完」）作業ビットマスク７２Ｄが「１」（「一致検索要」）であるため、検索作業ビット５０として「０」（「作業完」）が入力された場合のみ検索にマッチする。初期状態では、検索作業ビット５０の値は「０」であるため、削除対象として更新された格納エントリ７Ｄは全て検索対象のままであり、従ってこの更新処理中に検索対象となる格納データ７に変化は発生しない。
【００５５】
削除対象である格納エントリ７Ｄの更新がすべて完了すると（ステップ２０２：Ｙ）、連想メモリ更新手段２は連想メモリ検索手段１に対して変更要求４を出力して、検索作業ビット５０の値を「１」（「作業中」）に変更するように要求し、連想メモリ検索手段１は、以後の検索に関して、検索作業ビット５０の値を「１」（「作業中」）にして検索を行う（ステップ１０３）。
【００５６】
検索作業ビット５０の値が「１」（「作業中」）に変わることにより、その作業ビット７０Ｄが「０」（「作業完」）である削除対象の格納エントリ７Ｄはすべて同時に検索対象外となる。
【００５７】
次に、連想メモリ更新手段２は、削除対象の格納データ７Ｄに関して、マスク付き連想メモリ３から削除する（ステップ２０４）。
【００５８】
削除対象の格納エントリ７Ｄに関して、全ての削除処理が完了していない場合、（ステップ２０５：Ｎ）、削除対象の格納エントリ７Ｄを繰り返しマスク付き連想メモリ３から削除する（ステップ２０４）。この時、すでに削除対象の格納エントリ７Ｄは検索の対象外であるため、削除処理により、検索対象となる格納データ７に変化は発生しない。
【００５９】
削除対象の格納データ７Ｄに関して、全ての削除処理が完了すると（ステップ２０５：Ｙ）、連想メモリ更新手段２は、連想メモリ検索手段１に対して検索作業ビット５０の値を「０」（「作業完」）に変更する要求４を出力する。連想メモリ検索手段１は、以後の検索に関して、検索作業ビット５０の値を「０」（「作業完」）にして検索を行う（ステップ１０６）。以後、検索作業ビット５０の値は初期状態と同じ「０」（「作業完」）に戻る。
【００６０】
次に、複数の格納エントリ７Ａの追加および複数の格納エントリ７Ｄの削除を同時に行う手順を図４のフローチャートを用いて説明する。
【００６１】
まず、図２の場合と同様に手順１０１，１０２に従って、連想メモリ更新手段２は、追加対象のエントリ７Ａに関して、更新作業ビット６０を「１」、更新作業ビットマスク６２を「１」として更新データ６を作成して、マスク付き連想メモリ３に格納する。
【００６２】
次に、図３の場合と同様に手順２０１，２０２に従って、連想メモリ更新手段２は、削除対象エントリ７Ｄに関して、更新作業ビット６０を「０」、更新作業ビットマスク６２を「１」として更新データ６を作成して、マスク付き連想メモリ３の削除対象エントリ７Ｄの内容を更新する。
【００６３】
なお、手順１０１，１０２の追加処理と手順２０１，２０２の削除対象更新処理はその順番が逆であってもよい。
【００６４】
次に、図２の場合と同様の手順１０３に従って、連想メモリ更新手段２は連想メモリ検索手段１に対して変更要求４を出力して、検索作業ビット５０の値を「１」に変更するように要求し、連想メモリ検索手段１は、以後の検索に関して、検索作業ビット５０の値を「１」にして検索を行う。
【００６５】
検索作業ビット５０の値が「１」に変わることにより、一斉に、追加した格納エントリ７Ａは検索対象となり、削除対象エントリ７Ｄは検索対象外となる。
【００６６】
次に、図２の場合と同様の手順１０４，１０５に従って、連想メモリ更新手段２は、追加エントリ７Ａに関して、更新作業ビット「０」、更新作業ビットマスク「０」である更新データ６を作成して、マスク付き連想メモリ３の追加エントリの内容を更新する。
【００６７】
次に、図３の場合と同様の手順２０４，２０５に従って、連想メモリ更新手段２は、削除対象エントリ７Ｄを、マスク付き連想メモリ３から削除する。
【００６８】
なお、手順１０４，１０５の追加エントリ７Ａの更新処理と、２０４，２０５の削除対象エントリ７Ｄの削除処理は、その順番が逆であってもよい。
【００６９】
次に、図２の場合と同様の手順１０６に従って、連想メモリ更新手段２は、検索作業ビット５０の値を「０」に変更する要求を行い、連想メモリ検索手段１は、以後の検索に関して、検索作業ビット５０の値を「０」にして検索を行う。
【００７０】
この時、マスク付き連想メモリ３内に格納されている全ての格納エントリ７の作業ビット７０および作業ビットマスク７２は、初期状態と同く、作業ビット７０が「０」、作業ビットマスク７２が「０」であり、検索作業ビット５０の値に関係なく、全ての格納エントリが検索対象である。よって、作業ビット５０の値を「１」から「０」に変更しても全てが検索対象のままであり、作業ビット５０の値も初期状態と同じ「０」に戻る。
【実施例】
図５は、本発明の連想メモリ検索システムを利用したルータ装置２０の例を示すブロック図である。ルータ装置２０は、連想メモリ検索手段１と連想メモリ更新手段２とマスク付き連想メモリ３と転送情報メモリ１０と転送先ネットワークアドレス更新手段１１により構成される。
【００７１】
ルータ装置２０は、入力パケット２１を受信すると、本発明の転送メモリ検索システムを利用して、次の転送先である第２のルータを決定して、出力パケット２５を出力する。入力パケット２１は、転送先アドレス２２、目的地アドレス２３、他のデータ２４より構成されている。
【００７２】
ルータ装置２０にパケット２１が入力されると、連想メモリ検索手段１は、目的地アドレス２３と連想メモリ更新手段２より指定された検索作業ビット５０より、検索データ５を作成して、マスク付き連想メモリ３の検索を行う。
【００７３】
マスク付き連想メモリ３の出力する検索結果８は、転送情報メモリ１０に入力され、検索結果８に対応する転送情報９が転送先ネットワークアドレス更新手段１１に出力される。転送ネットワークアドレス更新手段１１は、転送情報９より、入力パケット２１の次の転送先である第２のルータを決定し、入力パケット内の転送先アドレス２２を第２の転送先アドレス２６に置き換えたデータを出力パケットとして、第２のルータに対して出力する。
【００７４】
以下、図５に示すルータ装置２０の動作手順を、図６〜図１０に示された具体的な例を用いて説明する。
【００７５】
図６は、更新前の格納エントリ例を示しており、マスク付き連想メモリ３は、第１〜第７の格納エントリ７（７−１，７−２，７−３，７−４，７−５，７−６、７−７）により構成され、転送情報メモリ１０には、格納エントリ７毎に、それぞれ次の転送先ルータ情報（７４−１，７４−２，７４−３，７４−４，７４−５，７４−６，７４−７）が格納されている。
【００７６】
格納エントリ７−５，７−６、７−７は、常に検索対象とならない空き格納エントリである。本実施例の、空き格納エントリは、エントリデータが０．０．０．０でエントリマスク２５５．２５５．２５５．２５５とすることにより、常に検索にヒットしないエントリにしているが、格納エントリのビットに余りがある場合には、空き格納エントリかどうかを判定するビットを定義して、空き格納エントリを識別することにより検索対象外となるように設定しても良い。
【００７７】
更新前には検索作業ビット５０の値は「０」である。各格納エントリ７の作業ビットマスク７２が「０」であるため、格納エントリ７−１，７−２，７−３，７−４は全て検索対象となっている。
【００７８】
本状態において、検索エントリデータ５１「１９２．１６８．４．５」が入力された場合、一致するエントリの中で最もマスク長の長い第４の格納エントリ７−４がヒットして、転送先ルータはRouter Ｂとなる。
【００７９】
以下、エントリデータが「１９２．１６８．０．０」でエントリマスク「２５５．２５５．０．０」である格納エントリを「１９２．１６８．０．０／２５５．２５５．０．０」と表現する。
【００８０】
図６において、第３の格納エントリ「１９２．１６８．０．０／２５５．２５５．０．０」と第４の格納エントリ「１９２．１６８．４．０／２５５．２５５．２５５．０」を削除して、第５の格納エントリに「１９２．１６８．０．０／２５５．２５５．０．０」を、第６の格納エントリに「１９２．１６８．５．０／２５５．２５５．２５５．０」を追加する処理を同時に実現する手順を具体的に説明する。
【００８１】
まず、図４のフローチャートの手順１０１，１０２に従って、第５の格納エントリと第６の格納エントリの追加を行い、図４のフローチャートの手順２０１，２０１に従って、第３の格納エントリ、第４の格納エントリの作業ビットおよび作業ビットマスクを更新した結果が、図７である。
【００８２】
図７では、図６と同様に、第１〜第４の格納エントリが検索対象であり、第５〜第７格納エントリは検索対象外である。
【００８３】
次に、図４のフローチャートの手順１０３に従って、検索作業ビット５０の値を「１」に変更したのが図８である。
【００８４】
図８において、検索作業ビット５０が「１」に変更されたことにより、第３の格納エントリ７−３、第４の格納エントリ７−４が検索対象から検索対象外に変更され、第５の格納エントリ７−５と第６の格納エントリ７−６が検索対象外から検索対象に変更されるので、一度に削除対象のエントリを検索対象外にし、追加対象のエントリを検索対象とすることができる。
【００８５】
検索エントリ５１「１９２．１６８．４．５」を入力した際には、第５の格納エントリ「１９２．１６８．０．０／２５５．２５５．０．０」がヒットし、転送先ルータはRouter Ｃに変更される。
【００８６】
次に、図４のフローチャートの手順１０４，１０５に従って、追加した格納エントリ７Ａの作業ビット７０Ａを「０」に作業ビットマスク７２Ａを「０」に更新し、図４のフローチャートの手順２０４，２０５に従って、削除対象の格納エントリ７Ｄを消去した結果が図９である。
【００８７】
図９では、削除対象のエントリ７Ｄである第３の格納エントリ７−３および第４の格納エントリ７−４は、空きエントリとなり、追加したエントリである第５の格納エントリ７−５および第６の格納エントリ７−６の作業ビット（７０−５，７０−６）および作業ビットマスク（７２−５，７２―６）は、他の格納エントリと同じ値となる。
【００８８】
次に、図４のフローチャートの手順１０６に従って、検索作業ビット５０の値を「０」に変更した結果が図１０である。
【００８９】
図１０では、検索作業ビット５０の値および、各格納エントリの作業ビットおよび作業ビットマスクの値が図６の最初の値に戻っており、次の更新処理を行うことが可能な状態である。
【００９０】
なお、本実施例のルータは、マスク付き連想メモリ５を用いて、転送先ルータ装置のアドレスの解決を行っているが、パケットデータから入力する任意のフィールドをマスク付き連想メモリに入力することにより、ＱｏＳ（Quality of Service）の優先度を決定したり、転送する順番を決定したりするようなルータ装置に同様に適用可能である。
【００９１】
図１１は、本発明の他の実施形態を示すマスク付きメモリ検索システムのブロック図である。
【００９２】
この実施の形態における連想メモリ検索システムでは、データ部分の複数ビットを作業ビットして割り当てることにより、複数の格納エントリの追加および削除処理に関して、平行して複数種類の処理を実施可能としたことを特徴としている。
【００９３】
本実施形態の連想メモリ検索システムは、連想メモリ検索手段１’と連想メモリ更新手段２’とマスク付き連想メモリ格納メモリ３より構成される。
【００９４】
マスク付き連想メモリ３内の格納エントリ７’は、作業ビット７０、第２の作業ビット７０’、エントリデータ７１、作業ビットマスク７２、第２の作業ビットマスク７２’、エントリマスク７２より構成される。
【００９５】
連想メモリ更新手段２’は、更新作業ビット６０、第２の更新作業ビット６０’、更新エントリデータ６１、更新作業ビットマスク６２、第２の更新作業ビットマスク６２’、更新作業ビットマスク６３より構成される更新データ６’を作成して、マスク付き連想メモリ３の格納エントリ７’を更新する。
【００９６】
連想メモリ更新手段２’は、連想メモリ検索手段１’に対して、検索作業ビット指定信号４’を出力し、検索作業ビット５０および第２の検索作業ビットの値５０’を指定する。
【００９７】
連想メモリ検索手段１’は、検索要求１２が入力されると、検索対照のデータと、連想メモリ更新手段２’より指定された検索作業ビット５０および第２の検索作業ビット５０’より、検索データ５’を作成して、マスク付き連想メモリ検索システムの検索を行う。
【００９８】
本実施の形態におけるマスク付き連想メモリ検索システムでは、例えば、連想メモリ更新手段２’が、格納エントリ７’の作業ビット７０および作業ビットマスク７２を利用して、エントリの更新を行っている途中で、別の更新要求１３’が入力された場合に、作業ビット７０’および作業ビットマスク７２’の値を利用して、新たに要求された更新要求処理を実施することにより、２種類の更新要求を平行して処理することが可能である。
【００９９】
なお、本実施の形態におけるマスク付き連想メモリ検索システムでは、格納エントリの２ビットを作業ビットとして割り当てることにより、最大２種類の更新要求を平行して処理しているが、格納エントリのｎビットを作業ビットとして割り当てることにより、最大ｎ種類の更新要求を平行して処理することが可能である。
【０１００】
【発明の効果】
本発明のマスク付き連想メモリ検索システムは、マスク付き連想メモリ内のデータの１ビットを作業ビットとして利用することによりエントリの追加及び削除処理を、マスク付き連想メモリ内の検索対象に影響を及ぼすことなく行うことができるので、一つのマスク付き連想メモリにより複数エントリの追加および削除を一度に実施することが可能である。
【０１０１】
また、複数エントリの追加および削除を同時に行う際に、更新対象のエントリのみを変更すればよく、バンク切り替え処理のように更新対象外のエントリを含む全てのエントリを更新する必要が無いので、マスク付き連想メモリを二重に設ける必要はなく、更新処理時間も短縮することができる。
【０１０２】
さらに、作業ビットとして格納エントリ内の複数ビットを割り当てることにより、複数エントリの追加および削除に関する処理を、複数種類並行して実施することが可能となる。
【図面の簡単な説明】
【図１】本発明の実施の形態を示すマスク付きメモリ検索システムのブロック図である。
【図２】本発明のマスク付き連想メモリ検索システムの動作を示すフローチャートである。
【図３】本発明のマスク付き連想メモリ検索システムの動作を示すフローチャートである。
【図４】本発明のマスク付き連想メモリ検索システムの動作を示すフローチャートである。
【図５】本発明の連想メモリ検索システムを利用したルータ装置の例を示すブロック図である。
【図６】図６のルータ装置の動作を説明するための図である。
【図７】図６のルータ装置の動作を説明するための図である。
【図８】図６のルータ装置の動作を説明するための図である。
【図９】図６のルータ装置の動作を説明するための図である。
【図１０】図６のルータ装置の動作を説明するための図である。
【図１１】本発明の他の実施形態を示すマスク付きメモリ検索システムのブロック図である。
【図１２】従来のマスク付き連想メモリ検索システムを示すブロック図である。
【符号の説明】
１  連想メモリ検索手段
２  連想メモリ更新手段
３  マスク付き連想メモリ
４  検索作業ビット
５  検索データ
６  更新データ
７，７−１，７−２，７−３，７−４，７−５，７−６  格納エントリ
７Ａ  追加対象の格納エントリ
７Ｄ  削除対象の格納エントリ
８  検索結果
９  転送情報
１０  転送情報メモリ
１１  転送先ネットワークアドレス更新手段
１２  検索要求
１３  更新要求
２０  ルータ装置
２１  入力パケット
２２  転送先アドレス
２３  目的地アドレス
２４  入力パケットの他のデータ
２５  出力パケット
２６  第２の転送先アドレス
５０  検索作業ビット
５０’  第２の検索作業ビット
５１  検索エントリデータ
６０  更新作業ビット
６０’  第２の更新作業ビット
６１  更新エントリデータ
６２  更新作業ビットマスク
６２’  第２の更新作業ビットマスク
６３  更新エントリマスク
７０，７０−１，７０−２，７０−３，７０−４，７０−５，７０−６  作業ビット
７０’，７０’−１，７０’−２，７０’−３，７０’−４，７０’−５，７０’−６  第２の作業ビット
７０Ａ  追加対象の格納エントリの作業ビット
７０Ｄ  削除対象の格納エントリの作業ビット
７１，７１−１，７１−２，７１−３，７１−４，７１−５，７１−６  エントリデータ
７２，７２−１，７２−２，７２−３，７２−４，７２−５，７２−６  作業ビットマスク
７２’，７２’−１，７２’−２，７２’−３，７２’−４，７２’−５，７２’−６  第２の作業ビットマスク
７２Ａ  追加対象の格納エントリの作業ビットマスク
７２Ｄ  削除対象の格納エントリの作業ビットマスク
７３，７３−１，７３−２，７３−３，７３−４，７３−５，７３−６  エントリマスク
７４，７４−１，７４−２，７４−３，７４−４，７４−５，７４−６、７４−７  転送先ルータ情報
【図１】
0003709978.tif 000002
【図２】
0003709978.tif 000003
【図３】
0003709978.tif 000004
【図４】
0003709978.tif 000005
【図５】
0003709978.tif 000006
【図６】
0003709978.tif 000007
【図７】
0003709978.tif 000008
【図８】
0003709978.tif 000009
【図９】
0003709978.tif 000010
【図１０】
0003709978.tif 000011
【図１１】
0003709978.tif 000012
【図１２】
0003709978.tif 000013