(57)【特許請求の範囲】
【請求項１】
検索されるビットデータと、前記ビットデータにおいて必要なビット長をマスクするためのマスク識別用データとを有してなる、互いに異なるエントリデータを記憶する一方、それぞれのエントリデータと、検索キーとなるビットデータとの突合せを行なう複数のエントリユニットをそなえるとともに、
各エントリユニットにおける同一ビット桁単位の前記突合せの結果と当該ビット桁のマスク識別ビットとを反映した情報について入力され、各ビット桁単位でエントリユニット間相互に反映された反映結果情報として出力する突合せ・マスク状態出力手段をそなえ、
各エントリユニットに、
前記突合せの結果、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータに一致する場合に、該突合せ・マスク状態出力手段からの前記反映結果情報を用いた論理演算により、当該エントリデータのうちでマスクされないビット長に関する情報を出力する論理演算手段と、
該論理演算手段からの出力信号に基づいて、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータとの突合せが一致する全てのエントリデータのうちで、マスクされないビット長が最も長いエントリデータである場合にのみ、前記検索キーに対する検索該当情報を出力する検索結果出力手段とをそなえて構成され、
該エントリユニットが、
少なくとも前記エントリデータのビット数分、前記エントリデータのビット配列に従って配置され、上記エントリデータを1ビット単位に分割して記憶するとともに、前記のエントリデータと検索キーとなるビットデータとの突合せを分割された1ビット単位に行なう、連想メモリセルと、
各連想メモリセルからの突合せ結果を反映させて前記のエントリデータ全体としてキーとなるビットデータとの突合せ結果として一致しているか否かの情報を出力しうる突合せ結果出力手段とをそなえ、
該連想メモリセルが、
前記検索されるデータを1ビット単位のデータに分割して記憶するデータレジスタと、該データレジスタに記憶される１ビットのデータに対応するマスク識別ビットを記憶するマスクレジスタと、上記のデータレジスタおよびマスクレジスタに記憶されたビットを用いて前記キーとなるビットデータとエントリデータとを分割された1ビット単位で突合せる突合せ回路とをそなえるとともに、該論理演算手段が、前記分割された1ビット単位ごとに論理演算を行なう論理演算回路をそなえて構成されるとともに、
該論理演算回路が、
該マスクレジスタからのマスク識別ビットが、対応する該データレジスタに記憶された１ビットのデータがマスクされていないことを示すものであり、かつ、該突合せ結果出力手段から前記突合せ結果として一致している旨の情報が入力される場合にのみ、その旨を第１演算結果として該突合せ・マスク状態出力手段に出力する第１論理演算素子と、
該第１論理演算素子からの論理演算結果が前記第１演算結果であって、隣接するビット桁における該突合せ・マスク状態出力手段からの出力結果が前記第１演算結果以外である場合にのみ、その旨を第２演算結果として該検索結果出力手段に出力する第２演算素子とをそなえ、
かつ、該検索結果出力手段が、上記第２演算素子から第２演算結果を入力された場合に、前記検索該当情報を出力するように構成されたことを特徴とする、連想メモリ装置。
【請求項２】
該突合せ・マスク状態出力手段が、各エントリデータにおける同一桁のビットを記憶する連想メモリセル間において共有に張られたラインにより構成されたことを特徴とする、請求項１記載の連想メモリ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えばネットワークの中継点においてアドレス交換を行なう際に用いて好適の、連想メモリ装置に関する。
【０００２】
【従来の技術】
近年、インターネット技術の利用が急速に普及していること等に伴い、ネットワークの高速化はより重要な課題となっている。特に、ネットワークの中継点となるルータにおいては、ネットワークを流れるパケット（例えばＩＰ〔Internet Protocol〕データグラム）を、高速のルーティング動作で正しいルートで配布できるようにすることが要求されている。
【０００３】
このようなネットワーク上でルーティング動作を行なう際には、宛先アドレスの検索装置として、従来よりＣＡＭ（Content Addressable Memory；連想メモリ）デバイスが用いられている。ここで、ＣＡＭデバイスは、入力されるパケットに対する宛先アドレスをハードウェアにより検索処理を行なうものである。
このＣＡＭデバイスは、上述の宛先アドレス検索装置として用いる場合には、上述のアドレス検索の際に、検索に該当するアドレスのうちでマスクされていないプリフィックス・ビットの長さが最も長いものを選択するという、いわゆるロンゲスト・プリフィックス・マッチ（Longest Prefix Match）検索を行なう機能を有することが要求されている。
【０００４】
上述のロンゲスト・プリフィックス・マッチ検索を行なうＣＡＭデバイスとしては、例えば図１５に示すような３値ＣＡＭ（Ternary-CAM）１００がある。この３値ＣＡＭ１００は、検索キーとなるアドレス１０１に基づいて、エントリされた宛先アドレス１０４のうちでマッチするもの（アドレスビットの突合せを行なって一致するもの）を検索するものである。
【０００５】
この図１５に示す３値ＣＡＭ１００は、それぞれ別個の宛先アドレス(address１〜ｎ)１０４および宛先アドレス１０４に対応したプリフィックス・ビット１０５を記憶しうる複数のエントリユニット１０３−１〜１０３−ｎ，エントリユニット１０３−１〜１０３−ｎごとに設けられたマッチライン１０２およびプライオリティエンコーダ１０６をそなえて構成されている。
【０００６】
ここで、各エントリユニット１０３−１〜１０３−ｎに格納される宛先アドレス１０４は、プリフィックス・ビットの１０５の連続するビット長（値「１」が連続するビットの長さ）に応じて、予め順番に格納されている。
なお、プリフィックス・ビット１０５が値「１」の場合には、対応するアドレスビット桁の突合せの際に突合せ結果を無視しないという条件が与えられ、プリフィックス・ビット１０５が値「０」の場合には、対応するアドレスビット桁の突合せの際に突合せ結果を無視するという条件（Don't care条件）が与えられるようになっている。
【０００７】
この場合においては、エントリユニット１０３−１には、プリフィックス・ビット１０５が最も長い宛先アドレスが記憶され、エントリユニット１０３−２には、エントリユニット１０３−１の宛先アドレスに次ぐプリフィックス・ビットの長さの宛先アドレスが記憶され、以下、エントリユニット１０３−３〜１０３−ｎには、プリフィックス・ビットの長さ順に従って宛先アドレスが記憶されるようになっている。
【０００８】
さらに、プライオリティエンコーダ１０６には各エントリユニット１０３−１〜１０３−ｎからの検索該当信号（match）が競合した場合に、プリフィックス・ビット１０５が長いエントリユニット１０３−１〜１０３−ｎからの検索該当信号を検索結果として出力するようになっている。
また、図１６は図１５のエントリユニット１０３−１〜１０３−ｎを構成するＣＡＭセル２００を示すブロック図である。即ち、各エントリユニット１０３−１〜１０３−ｎは、宛先アドレスとして想定されるビット数分、図１６に示すＣＡＭセル２００をそなえて構成されている。
【０００９】
ここで、一つのＣＡＭセル２００は、宛先アドレスを構成する１ビットのアドレスデータを記憶するデータレジスタ２０１，アドレスデータに対応する１ビットのプリフィックス・ビットを記憶するマスクレジスタ２０２，データレジスタ２０１からのアドレスデータとビットライン２０６，２０７からの検索キーとなるアドレスデータとを比較するコンパレータ２０３およびマスクレジスタ２０２の値に基づきマスク処理（符号２０８参照）を施すマスク回路２０４をそなえて構成されている。
【００１０】
このような構成により、図１５に示す３値ＣＡＭ１００では、検索キーとなるアドレスとの一致検索が各エントリユニット１０３−１〜１０３−ｎにて行なわれ、検索キーとなるアドレスに一致する宛先アドレスを格納するエントリユニット１０３−１〜１０３−ｎでは、その旨を検索該当信号（match信号）としてマッチ・ライン１０２を通じてプライオリティエンコーダ１０６に出力する。
【００１１】
この場合において、予め全エントリ（エントリユニット１０３−１〜１０３−ｎに記憶される宛先アドレス）をプリフィックス・ビット１０５の長さ順に並べて収容しているので、複数の宛先アドレスが該当した場合においても、プライオリティエンコーダ１０６では検索該当するもののうち優先度が最上位に配されたエントリユニット１０３−１〜１０３−ｎからのマッチ信号を、ロンゲスト・プリフィックス・マッチ結果として出力している。
【００１２】
ところで、上述の図１５に示す３値ＣＡＭ１００においては、正しくロンゲスト・プリフィックス・マッチ結果を求めるためには、予め全エントリをプリフィックスの長さ順に並べて収容しておく必要がある。即ち、新規の配布先登録や使われなくなった配布先の削除を行なう際には、エントリの追加・削除を行なう必要が生ずる。
【００１３】
具体的には、エントリの追加の際には、プリフィックスの長さに応じて、エントリユニット１０３−１〜１０３−ｎのうちのいずれかの挿入すべきエントリユニット１０３−１〜１０３−ｎを決定すると、当該位置以下のエントリを繰り下げて追加すべき位置のエントリユニット１０３−１〜１０３−ｎを空にした後に、追加すべきエントリを記憶する。これにより、エントリは、プリフィックスの長さの序列が崩れないように追加できるようになっている。
【００１４】
このように、上述のエントリの追加または削除を行なう場合には、全エントリを改めてプリフィックス順に並べなおして再度収容する作業が必要となるが、これら一連のアップデート作業は大変時間を要し、稼動中のＣＡＭデバイスを停止しなければならない。
ネットワークの高速化を更に進めるためには、ＣＡＭデバイスの高速・連続動作が要求されるため、このようなアップデート作業は大きな障害となる。また、インターネットの普及に伴い、エントリ数の増大や、ＩＰｖ６（Internet Protocol version 6）適用下でのアドレスビット増大によるＣＡＭの大容量化の要請もあり、このような大容量化されたＣＡＭについて上述のごときアップデート作業を行なう場合には作業負荷が更に増大する。
【００１５】
これに対し、US Patent （米国特許）No. 6,144,574では、任意のプリフィックス長のエントリを任意の位置に収容してアップデート作業の負荷を軽減しつつ、最初の検索サイクルでフル・マッチ（マルチ・マッチ）検索結果および最長プリフィックス長を得て、２回目のサイクルにおいて１回目のサイクルで得られた最長プリフィックス長をフィードバックして全エントリのプリフィックスの検索動作を再度行ない該当したエントリをロンゲスト・プリフィックス・マッチ検索結果として出力する装置について開示されている。
【００１６】
【発明が解決しようとする課題】
しかしながら、上述の装置においては、検索処理として２回の検索サイクルを経るような回路構成となっており、このような２回の検索サイクルを行なう構成においても尚、高速化を阻害するという課題がある。即ち、前述のＣＡＭデバイスの高速化，大容量化の要請のためには、上述のごとき２回の検索処理を行なうために要する処理時間を更に短縮化するための技術を提供することが要求されることとなる。
【００１７】
本発明は、このような課題に鑑み創案されたもので、アップデート作業の負荷を軽減するとともに、大容量化に容易に対応できるような構成としつつ１回の検索動作でロンゲスト・プリフィックス・マッチを出力することにより、検索処理のための処理時間を短縮できるようにした、連想メモリ装置を提供することを目的とする。
【００１８】
【課題を解決するための手段】
このため、本発明の連想メモリ装置は、検索されるビットデータと、前記ビットデータにおいて必要なビット長をマスクするためのマスク識別用データとを有してなる、互いに異なるエントリデータを記憶する一方、それぞれのエントリデータと、検索キーとなるビットデータとの突合せを行なう複数のエントリユニットをそなえるとともに、各エントリユニットにおける同一ビット桁単位の前記突合せの結果と当該ビット桁のマスク識別ビットとを反映した情報について入力され、各ビット桁単位でエントリユニット間相互に反映された反映結果情報として出力する突合せ・マスク状態出力手段をそなえ、各エントリユニットに、前記突合せの結果、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータに一致する場合に、該突合せ・マスク状態出力手段からの前記反映結果情報を用いた論理演算により、当該エントリデータのうちでマスクされないビット長に関する情報を出力する論理演算手段と、該論理演算手段からの出力信号に基づいて、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータとの突合せが一致する全てのエントリデータのうちで、マスクされないビット長が最も長いエントリデータである場合にのみ、前記検索キーに対する検索該当情報を出力する検索結果出力手段とをそなえて構成され、該エントリユニットを、少なくとも前記エントリデータのビット数分、前記エントリデータのビット配列に従って配置され、上記エントリデータを1ビット単位に分割して記憶するとともに、前記のエントリデータと検索キーとなるビットデータとの突合せを分割された1ビット単位に行なう、連想メモリセルと、各連想メモリセルからの突合せ結果を反映させて前記のエントリデータ全体としてキーとなるビットデータとの突合せ結果として一致しているか否かの情報を出力しうる、突合せ結果出力手段とをそなえ、さらに、該連想メモリセルが、前記検索されるデータを1ビット単位のデータに分割して記憶するデータレジスタと、該データレジスタに記憶される１ビットのデータに対応するマスク識別ビットを記憶するマスクレジスタと、上記のデータレジスタおよびマスクレジスタに記憶されたビットを用いて前記キーとなるビットデータとエントリデータとを分割された1ビット単位で突合せる突合せ回路とをそなえるとともに、該論理演算手段を、前記分割された1ビット単位ごとに論理演算を行なう論理演算回路をそなえて構成されるとともに、該論理演算回路が、該マスクレジスタからのマスク識別ビットが、対応する該データレジスタに記憶された１ビットのデータがマスクされていないことを示すものであり、かつ、該突合せ結果出力手段から前記突合せ結果として一致している旨の情報が入力される場合にのみ、その旨を第１演算結果として該突合せ・マスク状態出力手段に出力する第１論理演算素子と、該第１論理演算素子からの論理演算結果が前記第１演算結果であって、隣接するビット桁における該突合せ・マスク状態出力手段からの出力結果が前記第１演算結果以外である場合にのみ、その旨を第２演算結果として該検索結果出力手段に出力する第２演算素子とをそなえ、かつ、該検索結果出力手段が、上記第２演算素子から���２演算結果を入力された場合に、前記検索該当情報を出力するように構成されたことを特徴としている。
【００２１】
また、上述の連想メモリ装置においては、該突合せ・マスク状態出力手段を、各エントリデータにおける同一桁のビットを記憶する連想メモリセル間において共有に張られたラインにより構成することもできる。
【００２２】
【発明の実施の形態】
以下、図面を参照することにより、本発明の実施の形態について説明する。
（ａ１）第１実施形態の説明
図１は本発明の第１実施形態にかかる連想メモリ装置としてのＣＡＭを示す図であり、この図１に示すＣＡＭ４００は、例えば図３に示すようなネットワーク上のルータ１〜５において、ルーティング処理を行なう際に、宛先アドレスから出力先のルートを検索するアドレス検索装置として用いることができるものである。
【００２３】
すなわち、この図３に示すルータ５は、入力されるパケットに付された宛先アドレスを解析するとともに、出力先ルートとしての出力ポート♯１〜♯５に対応してＣＡＭ４００に記憶された宛先アドレスを参照することにより、この入力されたパケットに該当する出力ポートを検索するようになっている。
具体的には、このルータ（ルーティング装置）５は、上述のＣＡＭ４００とともに、入力されるパケットに付された宛先アドレスを解析するとともに、ＣＡＭ４００における検索結果として得られた出力ポートから当該パケットが転送されるようにルーティング処理する出方路決定部５−１をそなえている。なお、図３中においては、出力ポート♯１〜♯５はそれぞれルータ１，２ａ，３ａ，３ｃ，４に接続されている。
【００２４】
また、ルータ５に第１実施形態にかかる連想メモリ装置４００を適用することにより、入力されたパケット６に付された宛先アドレス（例えばＩＰアドレス）に応じて、接続先となる経路の出力ポート番号を高速に検索できるようになっており、これにより、ルータ５においては、得られた番号の出力ポートから、当該パケットをルータ１，２ａ，３ａ，３ｃ又は４のいずれかに転送することができる。
【００２５】
さらに、連想メモリ装置４００は、この図１に示すように、ｎ個のエントリユニット４０１−ｓ（ｓ＝１〜ｎ）およびエントリデータのとりうるビット数（図１においてはｋビット）＋１ビット分そなえられたプリフィックス・マッチ・ライン（Prefix Match Line）４０４，４０４−１〜４０４−ｋをそなえて構成されている。
【００２６】
ここで、エントリユニット４０１−ｓは、前述の図１５に示すＣＡＭデバイス１００と同様、検索されるビットデータとしての宛先アドレスと、この宛先アドレスにおいて必要なビット長をマスクするためのマスク識別用ビットとして機能しうるプリフィックス・ビットと、を有してなるエントリデータを記憶するとともに、このエントリデータと検索キーとなるビットデータとの突合せを行なうものである。
【００２７】
具体的には、後述するように、値が「１」のプリフィックス・ビットについては、対応するアドレスビット桁はマスクしないと識別するためのものであって、値が「０」のプリフィックス・ビットについては、対応するアドレスビット桁をマスクすると識別するためのものである。
これにより、ＣＡＭ４００においては、図３に示すパケット６に付されたアドレスビットを検索キーとして出方路決定部５−１から入力されて、図１に示す各ルータ１，２ａ，３ａ，３ｃ又は４のエリアを示すＩＰアドレスをエントリデータとして、それぞれ突合せを行なうことにより、突合せが一致する（マッチする）出力ポート番号を抽出できるようになっているのである。
【００２８】
さらに、プリフィックス・マッチ・ライン４０４−１〜４０４−ｋは、各エントリユニット４０１−ｓのアドレスデータが検索キーとなるビットデータに一致するもののうちで、マスクされていない同一桁間のビット（プリフィックス・ビット）の検索キーとなるビットデータとの突合せ結果のマッチング状態について出力するもので、プリフィックス・マッチ・ライン４０４は、固定的に状態「１」を出力するものである。
【００２９】
これにより、各エントリユニット４０１−ｓにおいては、最長ｋビットの、マスクされていないプリフィックス・ビットからなるエントリデータについて、突合せを行なうことができるようになっている。
換言すれば、プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋは、各エントリユニット４０１−ｓにおける同一ビット桁単位の突合せの結果と当該ビット桁のマスク識別ビットとを反映した情報について入力され、各ビット桁単位でエントリユニット４０１−ｓ間相互に反映された反映結果情報として出力するものであり、突合せ・マスク状態出力手段としての機能を有している。
【００３０】
ところで、上述のエントリユニット４０１−ｓは、連想メモリセル４１０，マルチ・マッチ・ライン（Multi Match Line）４０３−ｓおよびロンゲスト・プリフィックス・マッチ・ライン（Longest Prefix Match Line）４０５−ｓをそなえて構成されている。
ここで、連想メモリセル４１０は、図１中、行（row）方向に横並びにエントリデータのとりうるビット数（図１においてはｋビット）＋１ビット分配置されてなるものであり、各エントリユニット４０１−ｓにおける連想メモリセル４１０は、詳細には後述する図２に示すような構成を有している。
【００３１】
さらに、マルチ・マッチ・ライン４０３−ｓは、各連想メモリセル４１０からの突合せ結果を反映させて、エントリデータ全体としてキーとなるビットデータとの突合せ結果として一致しているか否かの情報を出力しうるものであり、突合せ結果出力手段としての機能を有する。
また、ロンゲスト・プリフィックス・マッチ・ライン４０５−ｓは、後述するＡＮＤ回路４０７からの出力信号に基づいて、自身のエントリユニット４０１−ｓに記憶されたエントリデータが、検索キーとなるビットデータとの突合せが一致する全てのエントリデータのうちで、マスクされないビット長が最も長いエントリデータである場合にのみ、検索キーに対する検索該当情報としてロンゲスト・プリフィックス・マッチ信号を出力するものであり、検索結果出力手段として機能する。
【００３２】
また、エンコーダ４０８はロンゲスト・プリフィックス・マッチ・ライン４０５−ｓからの状態信号を入力されて、マスクされないビット長が最も長い検索該当アドレスに関するエンコード情報を外部の出方路決定部（図３の符号５−１参照）に出力するようになっている。
ところで、連想メモリセル４１０は、図２に示すようにデータレジスタ（Data Register）５０１，マスクレジスタ（Mask Register）５０２，コンパレータ（Comparator）５０３，マスク回路（Mask Circuit）５０４およびＡＮＤ回路４０６，４０７をそなえて構成されている。なお、データレジスタ５０１，マスクレジスタ５０２，コンパレータ５０３およびマスク回路５０４からなる回路部４０２については、前述の図１６に示すものと基本的に同様の回路構成を有している。
【００３３】
なお、以下においては、説明の便宜上、エントリユニット４０１−１における最上位ビット（ｋ番目のビット）を記憶する連想メモリセル４１０（図１中左上端のもの）の構成に着目して説明することとする。
ここで、データレジスタ５０１は検索されるアドレスデータを１ビット単位のデータに分割して記憶するもので、マスクレジスタ５０２は、データレジスタ５０１に記憶される１ビットのデータに対応するマスク識別ビットを記憶するものである。これらのアドレスデータおよびマスク識別ビットは、図示しない主制御装置等からの設定データとしてビットライン５０６，５０７を介して入力されるようになっている。
【００３４】
したがって、エントリユニット４０１−ｓを構成する各連想メモリセル４１０のデータレジスタ５０１が協働することにより、アドレスデータの全ビットを記憶することができる一方、エントリユニット４０１−ｓを構成する各連想メモリセル４１０のマスクレジスタ５０２が協働することにより、マスク識別用データの全ビットを記憶することができるようになっている。
【００３５】
なお、上述のマスク識別用ビットとしては、マスクされないプリフィックス・ビット桁については「１」とする一方、マスクされるビット桁については「０」が設定されるようになっている。
さらに、コンパレータ５０３は、上述のデータレジスタ５０１に記憶された１ビットのアドレスデータと、ビットライン５０６，５０７を介して入力された検索キーとなるアドレスデータの対応ビットデータとを比較するものであり、比較結果は、後段のマスク回路５０４に出力するようになっている。
【００３６】
また、マスク回路５０４は、コンパレータ５０３からの比較結果について、マスクレジスタ５０２にて記憶されているマスク条件をかけて出力するものである。具体的には、マスクレジスタ５０２に記憶されているビット値を入力されて、このビット値が、ドントケア条件または“ignore”を示す「０」である場合に、コンパレータ５０３の比較結果に関わらず（コンパレータ５０３の比較結果が不一致“unmatched”であっても）突合せ一致を示すマッチ信号を上述のマルチ・マッチ・ライン４０３−１に出力するものである（図１における符号４０９参照）。
【００３７】
マルチ・マッチ・ライン４０３−ｓは、エントリユニット４０１−ｓを構成する各連想メモリセル４１０のマスク回路５０４から、上述の突合せ結果を入力されて、全ての連想メモリセル４１０のマスク回路５０４において突合せ結果としてマッチ信号が入力されている場合にのみ、マルチ・マッチ状態「１」となる一方、そうでない場合においては無効状態「０」となる。
【００３８】
換言すれば、マルチ・マッチ・ライン４０３−ｓは、エントリユニット４０１−ｓの各ビットのうちで、一つでも不一致（アンマッチ）があると無効「０」となり、全ビットが一致（マッチ）または“ignore”の場合のみ有効「１」となる。したがって、上述のコンパレータ５０３およびマスク回路５０４により、データレジスタ５０１およびマスクレジスタ５０２に記憶されたビットを用いて、検索キーとなるビットデータとエントリデータとを、分割された1ビット単位で付き合わせる突合せ回路としての機能を有している。
【００３９】
さらに、ＡＮＤ回路４０６は、マスクレジスタ５０２にて格納されているビット値と、自身のエントリユニット４０１−１におけるマルチ・マッチ・ライン４０３−１の状態値とをＡＮＤ演算するものであり、ＡＮＤ演算結果は、ＡＮＤ回路４０７およびプリフィックス・マッチ・ライン４０４−ｋに出力されようになっている。
【００４０】
換言すれば、ＡＮＤ回路４０６は、マスクレジスタ５０２からのマスク識別ビットが、対応するデータレジスタ５０１に記憶された１ビットのデータがマスクされていないことを示すものであり、かつ、マルチ・マッチ・ライン４０３−１から突合せ結果として一致している旨の情報「１」が入力される場合にのみ、その旨「１」を第１演算結果としてプリフィックス・マッチ・ライン４０４−ｋに出力する第１論理演算素子として機能する。
【００４１】
また、プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋは、それぞれ、各エントリユニット４０１−１〜４０１−ｎの同一ビット桁の連想メモリセル４１０間において共有に張られたラインにより構成され、各連想メモリセル４１０のＡＮＤ回路４０６の出力にワイヤードノア接続されている。
すなわち、各プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋは、図４（ａ）に否定論理和（ＮＯＲ）回路４０４Ａとして等価的に示すように、同一桁の連想メモリセル４１０の各ＡＮＤ回路４０６からの信号を入力としてＮＯＲ演算を行なって、このＮＯＲ演算結果を出力するようになっている。これにより、同一ビット桁の連想メモリセル４１０におけるＡＮＤ回路４０６からの出力信号の全てが「０」の場合のみ「１」を出力し、それ以外の場合には「０」を出力するようになっている。
【００４２】
換言すれば、プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋは、各エントリユニット４０１−１〜４０１−ｎにおける同一桁の連想メモリセル４１０において、アドレスデータが検索キーとなるビットデータに一致し、かつマスクされていないビット桁が存在する場合に、その旨をビット桁ごとに通知するようになっている。
【００４３】
これにより、各エントリの同一ビット桁において一箇所でもＡＮＤ回路４０６出力が有効「１」であれば、列（column）方向に各セルが他のエントリと共有で持つプリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋの該当ビットを無効とするようになっているのである。
なお、このプリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋの値の配列は、後述するように、突合せが一致するエントリデータのうちの最長のプリフィックス・ビットのビット長を示している。
【００４４】
また、ＡＮＤ回路４０７は、ＡＮＤ回路４０６におけるＡＮＤ演算結果とエントリユニット４０１−１を構成する前段桁の（ｋ−１番目の）プリフィックス・マッチ・ライン４０４−（ｋ−１）の状態値とをＡＮＤ演算するものであり、ＡＮＤ演算結果は、ロンゲスト・プリフィックス・マッチ・ライン４０５−１に出力されようになっている。
【００４５】
換言すれば、ＡＮＤ回路４０７は、ＡＮＤ回路４０６からの論理演算結果が上述の第１演算結果としての「１」であって、隣接するビット桁におけるプリフィックス・マッチ・ライン４０４−（ｋ−１）からの出力結果が第１演算結果以外「０」である場合にのみ、その旨を第２演算結果としてロンゲスト・プリフィックス・マッチ・ライン４０５−１に出力する第２論理演算素子として機能する。
【００４６】
なお、各ロンゲスト・プリフィックス・マッチ・ライン４０５−１〜４０５−ｎはそれぞれ、対応するエントリユニット４０１−１〜４０１−ｎを構成する連想メモリセル４１０におけるＡＮＤ回路４０７の出力にワイヤードオア接続されている。即ち、図４（ｂ）にＯＲ回路４０５Ａとして等価的に示すように、各連想メモリセル４１０のＡＮＤ回路４０７出力を入力信号としてＯＲ演算を施した結果を出力するようになっている。
【００４７】
この場合においては、ロンゲスト・プリフィックス・マッチ・ライン４０５−１〜４０５−ｎは、ＡＮＤ回路４０７の出力信号において少なくとも一つが「１」である場合のみロンゲスト・プリフィックス・マッチ信号として「１」を出力し、それ以外の場合には「０」を出力するようになっている。
換言すれば、ロンゲスト・プリフィックス・マッチ・ライン４０５−１〜４０５−ｎは、各エントリユニット４０１−１〜４０１−ｎのアドレスデータが検索キーとなるビットデータに一致するもののうちで、マスクされていないビット（プリフィックス・ビット）の長さが最も長くなるアドレスデータに関する情報（アドレスデータを記憶するエントリユニットに関する情報）を出力するようになっている。
【００４８】
具体的には、図１に示す場合においては、プリフィックス・ビットが最も長くなるアドレスデータを記憶するエントリユニットは、エントリユニット４０１−ｎであり、エントリユニット４０１−ｎのロンゲスト・プリフィックス・マッチ・ライン４０５−ｎのみがロンゲスト・プリフィックス・マッチ状態「１」を出力し、ロンゲスト・プリフィックス・マッチ・ライン４０５−１〜４０５−（ｎ−１）においては、「０」を出力するようになっている。
【００４９】
したがって、上述の各エントリユニット４０１−１〜４０１−ｎを構成する連想メモリセル４１０のＡＮＤ回路４０６，４０７は、自身のエントリユニットに記憶されたエントリデータが、検索キーとなるビットデータに一致する場合に、プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋからの反映結果情報を用いた論理演算により、当該エントリデータのうちでマスクされないビット長に関する情報を出力する論理演算手段として構成され、各連想メモリセル４１０のＡＮＤ回路４０６，４０７は、１ビット単位ごとに論理演算を行なう論理演算回路として構成される。
【００５０】
なお、上述のＡＮＤ回路４０６，４０７については、例えばＣＭＯＳ（Complementary Metal Oxide Semiconductor）論理回路，ＮＭＯＳ（N channel MOS）論理回路またはＰＭＯＳ（P channel MOS）論理回路により構成できるようになっている。
また、各エントリユニット４０１−１〜４０１−ｎの最下位ビット桁（図１中、０番目のビット桁）における連想メモリセル４１０において、マスクレジスタ５０２には、マスクビット「０」が設定されることにより、プリフィックス・マッチ・ライン４０４の値は固定的に「１」に設定されている。
【００５１】
さらに、この連想メモリセル４１０のＡＮＤ回路４０７には、下位ビットのプリフィックス・ラインは存在しないので、検索動作時には、入力値として「１」を固定しておく。
上述の構成により、本発明の第１実施形態にかかる連想メモリ装置の動作例について、図５〜図８を用いて以下に説明する。
【００５２】
前述の図３に示すルータ５では、入力されるパケット６についてルーティング処理を施す。即ち、ルータ５内の出方路決定部５−１において、パケット６の宛先アドレスとしてのビットデータをＣＡＭ４００に渡す。ＣＡＭ４００では、渡された宛先アドレスのビットデータを検索キーとし、入力されたアドレスデータが出力ポート♯１〜♯５のいずれに対するパケットかを、記憶されたアドレスデータを当該パケットの宛先アドレスを検索キーとして検索する。
【００５３】
出方路決定部５−１では、ＣＡＭ４００からの検索該当結果を受けると、当該パケット６を検索結果として得られた出力先ルート（出力ポート情報）に基づいて、当該パケットを転送する。
以下、図５〜図８を用いることにより、上述のＣＡＭ４００における宛先となる出力ポートの検索処理について具体的に説明していくこととする。なお、図５〜図８に示す場合においては、ＣＡＭ４００のエントリユニット４０１−１〜４０１−５としては、５つの宛先側ルータ１，２ａ，３ａ，３ｃ，４に応じたアドレスデータを記憶するようになっており、各エントリユニット４０１−１〜４０１−５に記憶されるアドレスデータとしては例えば６ビット（ｋ＝５）の宛先アドレスが記憶される。
【００５４】
なお、図５〜図８中において、各エントリユニット４０１−１〜４０１−５における連想メモリセル４１０のマスクレジスタ５０２に記憶されたプリフィックス・ビットが“０”のビットはドントケア（Don't care）条件が与えられ、“Ｘ”で表している。
この場合においては、例えば、エントリユニット４０１−１にはルータ１側の宛先アドレスが下位３ビットのマスクとともにエントリされ、エントリユニット４０１−２にはルータ２ａ側の宛先アドレスが下位３ビットのマスクとともにエントリされ、エントリユニット４０１−３にはルータ３ａ側の宛先アドレスが下位２ビットのマスクとともにエントリされている。
【００５５】
さらに、エントリユニット４０１−４には、ルータ３ａの上位に属するルータ３ｃへルータ３ａを介さずに直接転送するための宛先アドレスが、下位１ビットのマスクとともにエントリされ、エントリユニット４０１−５には、ルータ４側の宛先アドレスが下位４ビットのマスクとともにエントリされている。
さて、ＣＡＭ４００に、図５に示すような宛先アドレスが「１１００１０」が検索キーとして入力されると、各エントリユニット４０１−１〜４０１−５における連想メモリセル４１０のコンパレータ５０３では、エントリされた宛先アドレスデータとの突合せをビット単位に行ない、突合せの結果両ビットが一致している場合にはマッチ信号「１」をマスク回路５０４に出力し、一致していない場合にはアンマッチ信号「０」を出力する。
【００５６】
このとき、ドントケア条件“X”が与えられた連想メモリセル４１０ではマスクレジスタ５０２からマスク回路５０４に出力されるプリフィックス・ビットが“０”であり、マスク回路５０４では比較動作結果がマスクされマッチ信号を出力する。
さらに、マルチ・マッチ・ライン４０３−１〜４０３−５においては、各エントリユニット４０１−１〜４０１−５の連想メモリセル４１０の全てからマッチ信号が出力されている場合にはマルチ・マッチ状態「１」を設定し、一つでもアンマッチ信号が出力されている場合にはマルチ・マッチしていない状態「０」を設定する（図５における▲１▼参照）。
【００５７】
この場合においては、エントリユニット４０１−１におけるドントケア条件が与えられた下位３ビットの連想メモリセル４１０では、マスク回路５０４（図２参照）においてマッチ信号を出力し、上位３ビットの連想メモリセル４１０においてもコンパレータ５０３からマスク回路５０４を介してマッチ信号が出力される。従って、マルチ・マッチ・ライン４０３−１ではマルチ・マッチ状態「１」が設定される。
【００５８】
エントリユニット４０１−３，４０１−５のマルチ・マッチ・ライン４０３−３，４０３−５においても、上述のマルチ・マッチ・ライン４０３−１とほぼ同様に、マルチ・マッチ状態「１」が設定される。
一方、エントリユニット４０１−２に記憶されたアドレスデータにおいては最上位から３ビット目（図５中下線が付されたビット値参照）が、エントリユニット４０１−４に記憶されたアドレスデータにおいては最上位から２ビット目および４ビット目（図５中下線が付されたビット値参照）が、それぞれ検索キーのアドレスビットに一致しない。
【００５９】
すなわち、該当するそれぞれの連想メモリセル４１０ではアンマッチ信号「０」が出力されるため、マルチ・マッチ・ライン４０３−２，４０３−４はマルチ・マッチしていない状態「０」が設定される。
また、各連想メモリセル４１０のＡＮＤ回路４０６においては、マスクレジスタ５０２からのプリフィックス・ビット（マスク識別用ビット）と、マルチ・マッチ・ライン４０３−１〜４０３−５からの状態信号とをＡＮＤ演算することにより、プリフィックス・ビットが“１”でかつ自エントリがマッチ状態であるか否かを検出する。この場合においては、図６に示すエントリユニット４０１−１，４０１−３，４０１−５におけるビット列７−１，７−３，７−５がこれに該当する（図６における▲２▼参照）。
【００６０】
各連想メモリセル４１０のＡＮＤ回路４０６で得られた上述の検出結果を、プリフィックス・マッチ・ライン４０４−１〜４０４−ｋに広報することにより、マッチした全エントリにおける最長のプリフィックス・ビット長を得ている。即ち、各プリフィックス・マッチ・ライン４０４−１〜４０４−ｋでは、エントリされたアドレスデータの同一桁ビットに対応する連想メモリセル４１０間において、ＡＮＤ回路４０６の出力信号が一つでも「１」であれば、無効状態「０」を設定する（図７の▲３▼参照）。
【００６１】
この場合においては、３つのマルチ・マッチ状態のエントリユニット４０１−１，４０１−３，４０１−５のうちで、各連想メモリセル４１０のマスクレジスタ５０２に協働して記憶されているプリフィックス・ビットのビット長が最も長くなるのは、上位４ビット長のプリフィックス・ビットが与えられているエントリユニット４０１−３のエントリデータであり、上位４ビット桁のプリフィックス・マッチ・ライン４０４−３〜４０４−６は無効状態「０」が設定されることになる。
【００６２】
すなわち、マルチ・マッチ状態のエントリユニット４０１−１，４０１−３，４０１−５に記憶されたエントリデータの下位２ビットはいずれもマスク・ビットであり、該当する連想メモリセル４１０のＡＮＤ回路４０６は、いずれも「０」を出力する。従って、プリフィックス・マッチ・ライン４０４−１，４０４−２については有効状態「１」が設定されることになる。
【００６３】
なお、上述のプリフィックス・マッチ・ライン４０４，４０４−１〜４０４−６の状態に基づき、最長プリフィックス長を判別することができる。この場合においては、最長プリフィックス・ビット長は、無効状態が連続する上位４ビットであると判別することができる。
さらに、上述の最長プリフィックス・ビット長を持つエントリユニット４０１−１〜４０１−５を、ロンゲスト・プリフィックス・マッチ・ライン４０５−１〜４０５−５により検出する。
【００６４】
ここで、各連想メモリセル４１０のマスクレジスタ５０２に協働して記憶されたマスク識別用データは、マスクされていないビット桁の範囲は「１」のビット列により構成され、マスクされているビット桁の範囲は「０」のビット列により構成される。
また、マルチ・マッチ状態の各エントリデータにおけるマスク識別用データを比較して少なくとも一つのエントリデータにおいてマスクされていないビット桁が存在する範囲では、プリフィックス・マッチ・ライン４０４−１〜４０４−５の状態を示すビットは連続した「０」のビット列となる一方（図７中は点線で示している）、全てのエントリデータにてマスクされたビット桁となっている範囲では「１」のビット列となる（図７中は実線で示している）。
【００６５】
そこで、マルチ・マッチ状態の各エントリユニット４０１−１，４０１−３，４０１−５において、マスク識別用データの「１」が連続した連想メモリセル４１０のうちで一番下位の連想メモリセル４１０に注目すると、この連想メモリセル４１０から見て下位ビットのプリフィックス・マッチ・ラインが無効である場合には、他のマッチしたエントリユニットが存在し、当該エントリが最長プリフィックス・ビット長を持つエントリではないことが分かる（図８における▲４▼参照）。
【００６６】
一方、マスク識別用データの「１」が連続した連想メモリセル４１０のうちで一番下位の連想メモリセル４１０から見て下位ビットのプリフィックス・マッチ・ラインが有効である場合には、当該エントリユニットが最長プリフィックス長のエントリデータを記憶していることが分かる（図８における▲６▼参照）。
例えば、マルチ・マッチ状態のエントリユニット４０１−１においては、上位３ビット目の連想メモリセル４１０が、マスク識別用データの「１」が連続した連想メモリセル４１０のうちで一番下位のものとなる。このエントリユニット４０１−１の上位３ビット目の連想メモリセル４１０に着目すると、下位ビットのプリフィックス・マッチ・ライン４０４−３は無効であるため、他のマッチしたエントリユニットが存在し、当該エントリが最長プリフィックス・ビット長を持つエントリではないことが分かる。
【００６７】
この場合においては、当該連想メモリセル４１０のＡＮＤ回路４０７では、ＡＮＤ回路４０６からの出力信号と隣接する下位ビット桁のプリフィックス・マッチ・ライン４０３−３の状態信号とについてＡＮＤ演算を施しているが、プリフィックス・マッチ・ライン４０３−３が無効状態「０」であるため、ＡＮＤ回路４０７では「０」が出力される。
【００６８】
エントリユニット４０１−１の上位２ビットの連想メモリセル４１０についても、上位３ビット目の連想メモリセル４１０の場合と同様に、下位ビットのプリフィックス・マッチ・ライン４０４−４，４０４−５が無効状態「０」であるため、これらの連想メモリセル４１０のＡＮＤ回路４０７においても「０」が出力される。更には、エントリユニット４０１−１の下位３ビットの連想メモリセル４１０においては、マスク識別用ビットとして「０」がマスクレジスタ５０２に記憶されているので、ＡＮＤ回路４０７においても「０」が出力される。
【００６９】
したがって、エントリユニット４０１−１における他のビット桁の連想メモリセル４１０においても「０」が出力されることになるため、各連想メモリセル４０７にワイヤードオア接続されたロンゲスト・プリフィックス・マッチ・ライン４０５−１では、検索非該当情報「０」を出力する。エントリユニット４０１−５のロンゲスト・プリフィックス・マッチ・ライン４０５−５においても、上述の場合と同様に、検索非該当情報「０」を出力する。
【００７０】
また、マルチ・マッチ状態のエントリユニット４０１−３において、マスク識別用データとして連続するビット値「１」における一番下位のビットを記憶する連想メモリセル（上位４ビット目の連想メモリセル）４１０に着目すると、下位ビットのプリフィックス・マッチ・ライン４０４−２が有効であるため、ＡＮＤ回路４０７においては「１」を出力する（図８における▲５▼参照）。
【００７１】
なお、エントリユニット４０１−３における上位３ビットの連想メモリセル４１０におけるＡＮＤ回路４０７においては前述したエントリユニット４０１−１における上位２ビットの連想メモリセル４１０の場合と同様に、下位２ビットの連想メモリセル４１０におけるＡＮＤ回路４０７においてはエントリユニット４０１−１における下位３ビットの連想メモリセル４１０の場合と同様に、それぞれ「０」が出力される。
【００７２】
したがって、エントリユニット４０１−３のロンゲスト・プリフィックス・マッチ・ライン４０５−３においては、上位４ビット目の連想メモリセル４１０のＡＮＤ回路４０７のみから「１」が出力されることになるので、検索該当情報として「１」を出力することができるのである（図８における▲６▼参照）。
なお、エントリユニット４０１−１〜４０１−５のうちで、マルチ・マッチ状態でないエントリデータを記憶するエントリユニット４０１−２，４０１−４の連想メモリセル４１０においては、マルチ・マッチ・ライン出力として「０」が出力されて無効となっているので、それぞれのロンゲスト・プリフィックス・マッチ・ライン４０５−２，４０５−４においても検索非該当情報「０」を出力している。
【００７３】
上述の検索該当情報を入力されたエンコーダ４０８については、エンコードされた検索該当結果を前述の出方路決定部５−１に通知する。出方路決定部５−１では、ＣＡＭ４００からの検索結果情報から得られる出力先ルート情報（出力ポート情報）に基づいて、パケット転送処理を行なう。
このように、本発明の第１実施形態における連想メモリ装置４００およびこの連想メモリ装置４００が適用されたルーティング装置によれば、エントリユニット４０１−１〜４０１−ｎに、ＡＮＤ回路４０６，４０７とロンゲスト・プリフィックス・マッチ・ライン４０５−１〜４０５−ｎをそなえたことにより、アップデート作業の負荷を軽減して時間短縮を図るとともに、大容量化に容易に対応できるような構成としつつ、クロックを必要とせずに一回の検索動作でロンゲスト・プリフィックス・マッチ結果を出力することができ、検索時間の短縮化を図ることができるほか、アップデート作業の簡素化や時間短縮を図ることが可能となり、ＩＰネットワークの高速化に貢献することができる利点がある。
【００７４】
（ａ２）第１実施形態の第１変形例の説明
上述の第１実施形態にかかる連想メモリ装置４００においては、各エントリユニット４０１−１〜４０１−ｎを構成する全ビットの連想メモリセル４１０をアドレスの突合せに用いているが、本発明によれば、例えば図９に示す連想メモリ装置４００Ａのように、アドレス検索処理の前段において下位ビット（例えば下位２ビット）をアドレスデータに付加したものを検索キーとして突合せを行なうように構成してもよい。
【００７５】
すなわち、アドレス検索処理の際に用いられる検索キーとしてのビットデータとして、下位２ビットを除く上位ビットについては宛先アドレスのデータにより構成されるとともに、下位２ビットについては、検索目的のビットデータである宛先アドレスに対する突合せに重みを与える重みビットとして構成してもよい。具体的には、下位２ビットについては例えば特定のパケットに与えられた優先度を示すビットデータにより構成され、ＣＡＭ４００Ａにおけるアドレス検索を上述のアドレスデータとともに優先度を示すビットデータに基づいて行なうようにしてもよい。
【００７６】
例えば図１０に示すように、エントリユニット４０１−１および４０１−３に記憶されているアドレスデータが符号Ａとして示すように共通のものであっても、エントリユニット４０１−１における下位ビットには、優先度低「Ｌ」を示す優先度付与ビットが記憶され、エントリユニット４０１−３においては、優先度高「ＶＨ」を示す優先度付与ビットを記憶するように構成する。
【００７７】
これにより、同一のアドレスデータを持つエントリユニット４０１−１，４０１−３間においても、パケットのヘッダ部に付された優先度付与ビットにより出力ポートが異なるように設定できるのである。
図１０に示すように、アドレスデータ「Ａ」を有するパケット６が入力された場合には、アドレスデータについてはエントリユニット４０１−１，４０１−３の双方が該当することになるが、このパケット６には優先度高を示す「ＶＨ」を示すビットが下位ビットに記憶されているので、エントリユニット４０１−３が該当アドレスとして出力されることになる。
【００７８】
すなわち、アドレス検索処理の前段において、特定のパケットに対して優先度の高いルーティング処理を行なうために上述の下位２ビットのデータを付加して、ＣＡＭ４００Ａによるアドレス検索処理を行なうことを通じて、ＱＯＳ（Quality Of Service）等のためのアプリケーションを実現できるようになっている。なお、上述のアドレス検索処理の前段において付加される下位２ビットのデータについては、例えば上述の出方路決定部５−１におけるアドレス解析の際に付加されるか、又は外部のルータにて付加されるようになっており、ＣＡＭ４００Ａでは、このように下位ビットが付加されたアドレスデータを検索キーとして、アドレス検索処理を行なうようになっている。
【００７９】
例えば、図１０に示すように、出方路決定部５−１において、入力されたＩＰパケットのアドレスを解析した結果、外部ルータにおいてパケットデータのヘッダ部が宛先ＩＰアドレス６Ａ，送信元ＩＰアドレス６Ｂとともに当該パケットの優先度としてのクラス情報６Ｃが得られた場合には、宛先アドレス６Ａのみならず当該クラス情報６ＣについてもＣＡＭ４００Ａにおける検索処理のキーとして用いるようになっている。
【００８０】
ところで、図９に示すＣＡＭ４００Ａは、前述の図１に示すＣＡＭ４００に比して、各エントリユニット４０１−１〜４０１−ｎにおける下位２ビット桁の連想メモリセル４１０Ａが、前述の図１に示すものと同様の回路部４０２をそなえて構成されるとともに、プリフィックス・マッチ・ライン（図１における符号４０４，４０４−１参照）をそなえていない点が異なるが、その他の構成については、基本的に前述の図１に示すものと同様である。なお、図９中、図１，図２と同一の符号は同様の部分を示している。
【００８１】
すなわち、プリフィックス・マッチ・ライン４０４−２〜４０４−ｋは、エントリデータの一部における同一桁のビット、具体的には、エントリデータの下位２ビットを除く上位ビットにおける同一桁のビットを記憶する連想メモリセル４１０間において、共有に張られたラインにより構成されている。
また、下位２ビット桁の各連想メモリセル４１０Ａは、対応するエントリユニット４０１−１〜４０１−ｎのマルチ・マッチ・ライン４０３−１〜４０３−ｎを共有しており、これにより、下位２ビットを除く上位ビットにおける連想メモリセル４１０の突合せに参加することができるようになっている。
【００８２】
さらに、連想メモリセル４１０Ａは、詳細には前述の図２の場合と同様、データレジスタ５０１，マスクレジスタ５０２，コンパレータ５０３およびマスク回路５０４を有する回路部４０２そなえて構成されている。
ここで、上述のデータレジスタ５０１およびマスクレジスタ５０２は、例えば特定のＩＰパケットに付された優先度に関するビットデータを記憶するものである。即ち、データレジスタ５０１およびマスクレジスタ５０２にて優先度を示すビットデータを記憶することにより、同一の宛先アドレスが記憶されたエントリユニット間においても、優先度により出力すべき出力ポートを配することができるようになっている。
【００８３】
また、コンパレータ５０３は、データレジスタ５０１およびマスクレジスタ５０２に記憶されたビットデータと、上述のＱＯＳ等を実現するために検索キーとしてのアドレスデータに付加されたビットを突き合わせるようになっており、突合せ結果については、それぞれのマルチ・マッチ・ライン４０３−１〜４０３−ｎに出力するようになっている。
【００８４】
なお、下位３ビット目の桁における連想メモリセル（プリフィックス・マッチ・ライン４０４−２が共有に張られている連想メモリセル）４１０のＡＮＤ回路４０７には、前段桁のプリフィックス・マッチ・ラインからの状態値信号の替わりに、固定値「１」が入力されるようになっている。
これにより、各エントリユニット４０１−１〜４０１−ｎにおいては、最長ｋ−２ビットの、マスクされていないプリフィックス・ビットからなるエントリデータについて、突合せを行なうことができるようになっている。
【００８５】
上述の構成により、第１実施形態の第１変形例にかかる連想メモリ装置４００Ａでは、前述の第１実施形態の場合と基本的に同様に、検索キーとなるアドレスデータ（ビットデータ）と、各エントリユニット４０１−１〜４０１−ｎに記憶されたエントリデータとの突合せを行ない、突合せの結果が一致する（マルチ・マッチ状態の）エントリデータのうちで、プリフィックス・ビット長が最も長いエントリデータを検索該当結果としてエンコーダ４０８に出力している。
【００８６】
ここで、図９に示す連想メモリ装置４００Ａでは、上述のアドレス検索処理の前段階において、検索キーとなるアドレスデータの下位桁に、予めＱＯＳ等を実現するためのアプリケーションにより例えば２ビットが付加される。
また、各エントリユニット４０１−１〜４０１−ｎの下位２ビット桁の連想メモリセル４１０Ａにおいては、上述のアドレスデータの下位２ビットに付加されたビットデータの突合せを行ない、この突合せ結果をマルチ・マッチ・ライン４０３−１〜４０３−ｎに出力する。これにより、パケットに付されたアドレスデータとともに、アドレス検索処理の前段階において付加されたビットに基づいて、マルチ・マッチ状態を判断している。
【００８７】
したがって、第１実施形態の第１変形例によれば、エントリデータの下位２ビットについては、検索目的のビットデータである宛先アドレスに対する突合せに重みを与える重みビットとして構成することができるので、前述の第１実施形態の場合と同様の利点があるほか、ＱＯＳ（Quality Of Service）等を実現する際のアプリケーションによるビットを上記の下位２ビットとして付加することができ、連想メモリ装置としての検索速度を向上できるだけでなく利用者の利用態様に合わせて最適の検索処理を行なうシステムを容易に構築することができる利点もある。
【００８８】
さらに、ＣＡＭ４００Ａのセル面積を、前述の第１実施形態におけるもの（符号４００）よりも小さくすることができるので、チップ面積を小さくして、装置規模の縮小化を図ることも可能である。
（ａ３）第１実施形態の第２変形例の説明
図１１は本発明の第２変形例にかかるＣＡＭ４００Ｂを示す図であるが、この図１１に示すように、アドレス検索処理の前段において下位ビットではなく上位ビット（例えば下位２ビット）をアドレスデータに付加したものを検索キーとして突合せを行なうように構成してもよい。
【００８９】
すなわち、アドレス検索処理の際に用いられる検索キーとしてのビットデータとして、上位２ビットを除く下位ビットについては宛先アドレスのデータにより構成されるとともに、上位２ビットについては、検索目的のビットデータである宛先アドレスに対する突合せに重みを与える重みビットとして構成してもよい。具体的には、上位２ビットについては例えば特定のパケットに与えられた優先度を示すビットデータにより構成され、ＣＡＭ４００Ｂにおけるアドレス検索を上述のアドレスデータとともに優先度を示すビットデータに基づいて行なうようにしてもよい。
【００９０】
ここで、アドレス検索処理の前段で付加される２ビットのデータとしては、前述の図１０の場合と同様に、例えばルーティング処理に際して、特定のパケットに対して優先度の高いルーティング処理を行なう等、ＱＯＳ等を実現する際のアプリケーションによる付加ビットとして用いることができるようになっている。ところで、図１１に示す連想メモリ装置４００Ｂは、前述の図１に示す連想メモリ装置４００に比して、各エントリユニット４０１−１〜４０１−ｎにおける上位２ビット桁の連想メモリセル４１０Ｂが、前述の図１に示すものと同様の回路部４０２をそなえて構成されるとともに、プリフィックス・マッチ・ライン（図１における符号４０４−（ｋ−１），４０４−ｋ参照）をそなえていない点が異なるが、その他の構成については、基本的に前述の図１に示すものと同様である。なお、図１１中、図１，図２と同一の符号は同様の部分を示している。
【００９１】
すなわち、プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−（ｋ−２）は、エントリデータの一部における同一桁のビット、具体的には、エントリデータの上位２ビットを除く下位ビットにおける同一桁のビットを記憶する連想メモリセル４１０間において、共有に張られたラインにより構成されている。
【００９２】
また、上位２ビット桁の連想メモリセル４１０Ｂについては、前述の図９に示す連想メモリセル４１０Ａと同様、データレジスタ５０１，マスクレジスタ５０２，コンパレータ５０３およびマスク回路５０４を有する回路部４０２をそなえて構成され、データレジスタ５０１およびマスクレジスタ５０２に記憶されたビットデータと、上述のＱＯＳ等を実現するために検索キーとしてのアドレスデータに付加されたビットを突き合わせるようになっている。
【００９３】
これにより、各エントリユニット４０１−１〜４０１−ｎにおいては、最長ｋ−２ビットの、マスクされていないプリフィックス・ビットからなるエントリデータについて、突合せを行なうことができるようになっている。
上述の構成により、第１実施形態の第２変形例にかかる連想メモリ装置４００Ｂでは、前述の第１実施形態の場合と基本的に同様に、検索キーとなるアドレスデータ（ビットデータ）と、各エントリユニット４０１−１〜４０１−ｎに記憶されたエントリデータとの突合せを行ない、突合せの結果が一致する（マルチ・マッチ状態の）エントリデータのうちで、プリフィックス・ビット長が最も長いエントリデータを検索該当結果としてエンコーダ４０８に出力している。
【００９４】
この連想メモリ装置４００Ｂにおいては、上述のごときアドレス検索処理の前段階において、検索キーとなるアドレスデータの上位桁に、予めＱＯＳ等を実現するためのアプリケーションにより例えば２ビットが付加されている。
これにより、各エントリユニット４０１−１〜４０１−ｎの上位２ビット桁の連想メモリセル４１０Ａにおいては、アドレス検索処理の際に、上述のアドレスデータの上位２ビットに付加されたビットデータの突合せを行ない、この突合せ結果をマルチ・マッチ・ライン４０３−１〜４０３−ｎに出力する。これにより、パケットに付されたアドレスデータとともに、アドレス検索処理の前段階において付加されたビットに基づいて、マルチ・マッチ状態を判断している。
【００９５】
したがって、第１実施形態の第２変形例によれば、エントリデータの上位２ビットについては、検索目的のビットデータである宛先アドレスに対する突合せに重みを与える重みビットとして構成することができるので、前述した第１実施形態の第１変形例の場合と同様の利点を得ることができる。
（ｂ１）第２実施形態の説明
図１２は本発明の第２実施形態にかかる連想メモリ装置を示す図であり、この図１２に示す連想メモリ装置６００についても、前述の第１実施形態の場合と同様のルータ５において適用することができるものである。
【００９６】
また、第２実施形態にかかる連想メモリ装置６００は、前述の第１実施形態の場合（符号４００参照）と同様の構成を有する複数のＣＡＭ６０１−１〜６０１−ｍが、外部接続ライン６０２，６０２−１〜６０２−ｋを介してカスケード接続されてなるものである。
ここで、外部接続ライン６０２，６０２−１〜６０２−ｋはそれぞれ、各ＣＡＭ６０１−１〜６０１−ｍにおけるプリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋ（図１参照）を相互に直列接続するものである。
【００９７】
また、エントリブロックとしての各ＣＡＭ６０１−１〜６０１−ｍは、前述の図１に示すＣＡＭ４００と同様、複数のエントリユニット（図１の符号４００−１〜４００−ｎ参照）をそなえるとともにエンコーダ（符号４０８参照）をそなえている。また、外部接続ライン６０２，６０２−１〜６０２−ｋは、複数のＣＡＭ６０１−１〜６０１−ｍを相互に接続するための外部接続手段として機能する。
【００９８】
これにより、各ＣＡＭ６０１−１〜６０１−ｍのプリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋにおいては、外部接続ライン６０２，６０２−１〜６０２−ｋを通じて、各ＣＡＭ６０１−１〜６０１−ｍを構成するエントリユニット４０１−１〜４０１−ｎ間相互に反映された情報を出力することができるようになっている。
【００９９】
なお、各ＣＡＭ６０１−１〜６０１−ｍにおいては、それぞれエンコーダをそなえて構成されているが、図示しない出方路決定部（図３の符号５−１参照）では、各エンコーダの出力６０３を用いてパケットの出力ポートを決定することができる。
したがって、前述の第１実施形態の場合と同様のＣＡＭを複数個接続することにより、各ＣＡＭ６０１−１〜６０１−ｍ全体として収容しうるエントリデータを増大させることができるようになっている。
【０１００】
上述の構成により、本発明の第２実施形態にかかる連想メモリ装置６００がルータ５（図３参照）に適用された場合においても、前述の第1実施形態の場合と基本的に同様に、出方路決定部５−１において、入力されるパケット６について出力先ルートを検索する際に、パケット６に付された宛先アドレスデータ６０４を検索キーとして連想メモリ装置６００を検索することにより、出力先ルートを獲得する。
【０１０１】
すなわち、ルータ５内の出方路決定部５−１において、パケット６の宛先アドレスとしてのビットデータを連想メモリ装置６００に渡す。連想メモリ装置６００では、渡された宛先アドレスのビットデータを検索キーとし、入力されたアドレスデータ６０４が出力ポート♯１〜♯５のいずれに対するパケットかを、記憶されたアドレスデータから検索し、検索該当結果を上述の出方路決定部５−１に戻す。
【０１０２】
このような検索動作を行なう連想メモリ装置６００においては、外部接続ライン６０２，６０２−１〜６０２−ｋを通じて、各ＣＡＭ６０１−１〜６０１−ｍを構成するエントリユニット４０１−１〜４０１−ｎ間相互に反映された情報を出力しているので、各ＣＡＭ６０１−１〜６０１−ｍを構成するエントリユニット４０１−１〜４０１−ｎに記憶されたエントリデータのうちで、検索キーとなるアドレスデータ６０４に一致しかつプリフィックス・ビットが最も長いものを、１回の検索動作で検索することを可能としている。
【０１０３】
換言すれば、各ＣＡＭ６０１−１〜６０１−ｍを並列的に動作させることができるので、前述の第１実施形態の場合と同様、複数回の検索ステップを経ることなく検索結果を出力することができるのである。
このように、本発明の第２実施形態にかかる連想メモリ装置６００によれば、複数のＣＡＭ６０１−１〜６０１−ｍを外部接続ライン６０２，６０２−１〜６０２−ｋを介して相互に接続することができるので、前述の第１実施形態の場合と同様の利点があるほか、全体として収容しうるエントリデータを増大させることができ、ネットワークにおけるエントリ数増大に容易に対応することができる利点がある。
【０１０４】
（ｂ２）第２実施形態の第１変形例の説明
図１３は本発明の第２実施形態の第１変形例にかかる連想メモリ装置を示す図であり、この図１３に示す連想メモリ装置７００は、前述の第２実施形態におけるもの（符号６００参照）に比して、前述の第１実施形態の場合（符号４００参照）と同様の構成を有する複数のＣＡＭ７０１−１〜７０１−ｍが接続されて、収容しうるエントリ数を増大できるようになっている点は共通するが、これらのＣＡＭ７０１−１〜７０１−ｍが接続される態様が異なっている。
【０１０５】
すなわち、図１３に示す連想メモリ装置７００においては、外部接続手段としての外部接続ライン７０３，７０３−１〜７０３−ｋが、ＣＡＭ７０１−１〜７０１−ｍの各プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋを並列に接続するようになっている。
換言すれば、外部接続ライン７０３，７０３−１〜７０３−ｋと各プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋとは、階層化接続されており、外部接続ライン７０３，７０３−１〜７０３−ｋが上位層のメイン・プリフィックス・マッチ・ラインとして、各プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋが下位層のサブ・プリフィックス・マッチ・ラインとして機能することになる。
【０１０６】
さらに、上述の外部接続ライン７０３，７０３−１〜７０３−ｋには、ＣＡＭ７０１−１〜７０１−ｍごとに、プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋを切り離し制御する制御回路部７０５−１〜７０５−ｍをそなえている。
また、これらの制御回路部７０５−１〜７０５−ｍはそれぞれ、外部から入力されるブロック制御信号７０４−１〜７０４−ｍに基づいて、ＣＡＭ７０１−１〜７０１−ｍにおける各プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋを切り離し制御する制御回路７０８をそなえて構成されており、これにより、各ＣＡＭ７０１−１〜７０１−ｍのイネーブル又はディセーブル状態を制御することができるようになっている。
【０１０７】
換言すれば、制御回路部７０５−１〜７０５−ｍにより、外部接続ライン７０３，７０３−１〜７０３−ｋを通じて相互に接続された複数個のエントリブロックとしてのＣＡＭ７０１−１〜７０１−ｍにおける少なくとも一つを切り離し制御できるようになっている。
なお、図１３においては、ＣＡＭ７０１−１，７０１−ｍがイネーブル状態として外部接続ライン７０３，７０３−１〜７０３−ｋに接続されるように、ＣＡＭ７０１−２がディセーブル状態として外部接続ライン７０３，７０３−１〜７０３−ｋから分離されるように、制御回路部７０５−１，７０５−２〜７０５−ｍにおける制御回路７０８がそれぞれ制御されるようになっている。
【０１０８】
これにより、エントリブロックとしてのＣＡＭ７０１−２については、前述のロンゲスト・プリフィックス・マッチ検索に参加させないように制御できるようになっている。
なお、７０６はエンコーダであり、このエンコーダ７０６は、エントリブロックとしての各ＣＡＭ７０１−１〜７０１−ｍからのロンゲスト・プリフィックス・マッチ信号の出力（図１における符号４０５−１〜４０５−ｎ参照）に基づいて、検索該当結果を図示しない出方路決定部に出力するものである。
【０１０９】
上述の構成により、本発明の第２実施形態の第１変形例にかかる連想メモリ装置７００では、全てのブロック制御信号がイネーブル状態である場合には、前述の第２実施形態の場合と同様に、各ＣＡＭ７０１−１〜７０１−ｍを構成するエントリユニット（図１における符号４０１−１〜４０１−ｎ参照）に記憶されたエントリデータのうちで、検索キーとなるアドレスデータに一致しかつプリフィックス・ビットが最も長いものを、１回の検索動作で検索することを可能としている。
【０１１０】
また、各制御回路部７０５−１〜７０５−ｍの状態を制御するためのブロック制御信号７０４−１〜７０４−ｍのいずれかが、ブロックディセーブル信号として入力された場合には、当該制御回路部７０５−１〜７０５−ｍにおいては該当するＣＡＭ７０１−１〜７０１−ｍを外部接続ライン７０３，７０３−１〜７０３−ｍから分離させる。これにより、分離されたＣＡＭ７０１−１〜７０１−ｍを上述の検索動作の対象から外すことができる。
【０１１１】
なお、検索動作の対象から外されたＣＡＭ７０１−１〜７０１−ｍについては、他のイネーブル状態のＣＡＭを作動状態としつつ、独立してアップデート作業を行なったりすることができるほか、検索動作の必要の無いアドレス群を記憶するＣＡＭを分離しておくことで、分離されたＣＡＭに対する配線負荷を軽減させている。
【０１１２】
このように、本発明の第２実施形態の第１変形例によれば、外部接続ライン７０３，７０３−１〜７０３−ｋにより、複数のＣＡＭ７０１−１〜７０１−ｍを相互に接続するとともに、制御回路部７０５−１〜７０５−ｍが介装されたことにより、前述の第２実施形態の場合と同様の利点があるほか、分離されたＣＡＭについて独立してアップデート作業を行なうことができるので、ネットワーク管理の便宜に資することができる。
【０１１３】
さらに、運用中においては、検索動作の必要の無いアドレス群を記憶するＣＡＭを分離しておくことで、分離されたＣＡＭに対する配線負荷を軽減させることができるので、検索動作を高速化させることができるほか、回路駆動のための消費電力を削減させることができる利点もある。
なお、上述の第２実施形態の第１変形例においては、エントリブロックとしての１チップのＣＡＭを、複数チップ階層化接続されているが、本発明によればこれに限定されず、１チップ内において、（複数のエントリユニットからなる）エントリブロックを複数有して構成するとともに、各エントリブロックにおけるマルチ・マッチ・ライン４０４，４０４−１〜４０４−ｋが外部接続ライン７０３，７０３−１〜７０３−ｋにより階層化接続（並列接続）されるように構成することも可能である。
【０１１４】
このような１チップのＣＡＭ内のエントリブロックにおけるマルチ・マッチ・ライン４０４，４０４−１〜４０４−ｋを階層化接続することによっても、上述の場合と同様の利点が得られることはいうまでもない。
（ｂ２）第２実施形態の第２変形例の説明
図１４は本発明の第２実施形態の第２変形例にかかる連想メモリ装置を示す図であり、この図１４に示す連想メモリ装置８００は、前述の図１２又は図１３に示すものに比して、複数の（２つの）ＣＡＭ８０１，８１１が接続される点は共通するが、各ＣＡＭ８０１，８１１の構成とともに、これらのＣＡＭ８０１，８１１が接続される態様が異なっている。
【０１１５】
ここで、各ＣＡＭ８０１，８１１は、前述の第１実施形態にかかるＣＡＭ４００に比して、突合せ・マスク状態出力手段としての各プリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋからの出力信号についてエンコードするエンコーダ（エンコード手段）８０３をそなえている点が異なり、これ以外の構成については第１実施形態にかかるＣＡＭ４００と基本的に同様である。なお、図１４中において、図１と同一の符号は、同様の部分を示している。
【０１１６】
また、この図１４に示す連想メモリ装置８００においては、各ＣＡＭ８０１，８１１はバス８１０を介して相互に接続されており、上述のエンコーダ８０３からのエンコード出力信号（符号８０４参照）についても外部接続手段としてのバス８１０を通じて外部に出力することができる。
換言すれば、バス８１０は、エンコーダ８０３にてエンコードされた出力信号について、エントリブロックとしての各ＣＡＭ８０１，８１１間でバス通信を行なうことができるようになっているのである。
【０１１７】
また、バス８１０を通じて接続された図示しない制御部は、バス制御および各ＣＡＭ８０１，８１１の調停機能を有するもので、出方路決定部（図３の符号５−１参照）としての機能を含めることができるようになっている。
すなわち、制御部では、検索キーとなるアドレスデータを、バス８１０を通じて各ＣＡＭ８０１，８１１に通知することができるようになっており、これにより、それぞれのＣＡＭ８０１，８１１においては、検索キーに突合せが一致するエントリデータのうちで、最もプリフィックス・ビットが長いエントリデータを抽出することができるのである。
【０１１８】
また、制御部では、バス８１０を通じて各ＣＡＭ８０１，８１１のエンコーダ８０３から入力されたエンコード出力信号に基づいて、ＣＡＭ８０１，８１１においてロンゲスト・プリフィックス・マッチしたエントリデータのうちで、さらにプリフィックス・ビットの長さを比較して、プリフィックス・ビットの長い方のエントリデータを有するＣＡＭ８０１，８１１からのロンゲスト・プリフィックス・マッチ信号を検索結果として受け取るように、各ＣＡＭ８０１，８１１のエンコーダ４０８′に対してバス８１０を通じて指示するようになっている（図１４における符号８０５，８１５参照）。
【０１１９】
換言すれば、ＣＡＭ８０１，８１１のエンコーダ４０８′においては、それぞれのロンゲスト・プリフィックス・マッチ結果が得られるようになっているが、各ＣＡＭ８０１，８１１のエンコーダ８０３にて出力されたエンコード出力信号を受けた制御部からの指示に基づいて、これら２つのロンゲスト・プリフィックス・マッチ結果のうちで、２つのＣＡＭ８０１，８１１全体としての１つのロンゲスト・プリフィックス・マッチ結果を得ることができるのである。
【０１２０】
なお、図１４中においては、信号８０４，８０５についてはバス８１０と区別して図示しているが、それぞれの信号ごとにバス８１０接続用の独立した入出力ポートを設ける必要はなく、単独の入出力ポートで共用化させることができる。上述の構成により、本発明の第２実施形態の第２変形例にかかる連想メモリ装置８００では、図示しない制御部において、検索キーとなるアドレスデータを、バス８１０を通じて各ＣＡＭ８０１，８１１に通知する。各ＣＡＭ８０１，８１１では、前述の第１実施形態の場合とほぼ同様に、検索キーに突合せが一致するエントリデータのうちで、最もプリフィックス・ビットが長いエントリデータを抽出する。
【０１２１】
また、制御部では、バス８１０を通じて各ＣＡＭ８０１，８１１のエンコーダ８０３から入力されたエンコード出力信号に基づいて、ＣＡＭ８０１，８１１においてロンゲスト・プリフィックス・マッチしたエントリデータのうちで、さらにプリフィックス・ビットの長さを比較して、プリフィックス・ビットの長い方のエントリデータを有するＣＡＭ８０１，８１１からのロンゲスト・プリフィックス・マッチ信号を検索結果として受け取るべく、各ＣＡＭ８０１，８１１のエンコーダ４０８′に対してバス８１０を通じて指示する。
【０１２２】
ＣＡＭ８０１，８１１のエンコーダ４０８′においては、バス８１０を通じて制御部からの指示を受けて、それぞれのロンゲスト・プリフィックス・マッチ結果のうちで、２つのＣＡＭ８０１，８１１全体としての１つのロンゲスト・プリフィックス・マッチ結果を得ることができるのである。
例えば、ＣＡＭ８０１からのロンゲスト・プリフィックス・マッチ結果のエントリデータのプリフィックス・ビット長が、ＣＡＭ８１１からのものよりも長い場合には、制御部からバス８１０を通じて入力された指示に基づき、ＣＡＭ８１１のエンコーダ４０８′の出力（図１４における符号８１９参照）についてはマスクされる一方、ＣＡＭ８０１のエンコーダ４０８′からは得られたロンゲスト・プリフィックス・マッチ結果が検索該当結果として出力される（図１４における符号８０９参照）。
【０１２３】
このように、本発明の第２実施形態の第２変形例にかかる連想メモリ装置によれば、エンコーダ８０３をそなえたことにより、各ＣＡＭ８０１，８１１のプリフィックス・マッチ・ライン４０４，４０４−１〜４０４−ｋからの出力信号をエンコードして出力することができるので、前述の第２実施形態の場合と同様の利点があるほか、外部に出力するピン数を削減することができ、例えばＩＰｖ６の導入する場合等のように、ネットワークの改良または規模増大に伴ってアドレスビットが増大する場合においても、ピン数の増大を抑制させることができる利点もある。
【０１２４】
（ｃ）その他
上述の各実施形態においては、本発明の連想メモリ装置を、ＩＰ層のネットワークに適用した場合、具体的にはＩＰパケットをルーティングするルータに適用した場合について詳述したが、本発明によればこれに限定されず、ＩＰ層以外のネットワークにおいて検索動作を行なう際も本発明を適用することができる。
（ｄ）付記
（付記１）  検索されるビットデータと、前記ビットデータにおいて必要なビット長をマスクするためのマスク識別用データとを有してなる、互いに異なるエントリデータを記憶するとともに、それぞれのエントリデータと、検索キーとなるビットデータとの突合せを行なう複数のエントリユニットと、
各エントリユニットにおける同一ビット桁単位の前記突合せの結果と当該ビット桁のマスク識別ビットとを反映した情報について入力され、各ビット桁単位でエントリユニット間相互に反映された反映結果情報として出力する突合せ・マスク状態出力手段をそなえ、
各エントリユニットに、
前記突合せの結果、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータに一致する場合に、該突合せ・マスク状態出力手段からの前記反映結果情報を用いた論理演算により、当該エントリデータのうちでマスクされないビット長に関する情報を出力する論理演算手段と、
該論理演算手段からの出力信号に基づいて、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータとの突合せが一致する全てのエントリデータのうちで、マスクされないビット長が最も長いエントリデータである場合にのみ、前記検索キーに対する検索該当情報を出力する検索結果出力手段をそなえて構成されたことを
特徴とする、連想メモリ装置。
【０１２５】
（付記２）  該エントリユニットが、
少なくとも前記エントリデータのビット数分そなえられ、上記エントリデータを1ビット単位に分割して記憶するとともに、前記のエントリデータと検索キーとなるビットデータとの突合せを分割された1ビット単位に行なう、連想メモリセルと、
各連想メモリセルからの突合せ結果を反映させて前記のエントリデータ全体としてキーとなるビットデータとの突合せ結果として一致しているか否かの情報を出力しうる突合せ結果出力手段とをそなえて構成されたことを
特徴とする、付記1記載の連想メモリ装置。
【０１２６】
（付記３）  該連想メモリセルが、
前記検索されるデータを1ビット単位のデータに分割して記憶するデータレジスタと、該データレジスタに記憶される１ビットのデータに対応するマスク識別ビットを記憶するマスクレジスタと、上記のデータレジスタおよびマスクレジスタに記憶されたビットを用いて前記キーとなるビットデータとエントリデータとを分割された1ビット単位で突合せる突合せ回路とをそなえるとともに、該論理演算手段が、前記分割された1ビット単位ごとに論理演算を行なう論理演算回路をそなえて構成されるとともに、
該論理演算回路が、
該マスクレジスタからのマスク識別ビットが、対応する該データレジスタに記憶された１ビットのデータがマスクされていないことを示すものであり、かつ、該突合せ結果出力手段から前記突合せ結果として一致している旨の情報が入力される場合にのみ、その旨を第１演算結果として該突合せ・マスク状態出力手段に出力する第１論理演算素子と、
該第１論理演算素子からの論理演算結果が前記第１演算結果であって、隣接するビット桁における該突合せ・マスク状態出力手段からの出力結果が前記第１演算結果以外である場合にのみ、その旨を第２演算結果として該検索結果出力手段に出力する第２演算素子とをそなえ、
かつ、該検索結果出力手段が、上記第２演算素子から第２演算結果を入力された場合に、前記検索該当情報を出力するように構成されたことを特徴とする、付記２記載の連想メモリ装置。
【０１２７】
（付記４）  該突合せ・マスク状態出力手段が、各エントリデータにおける同一桁のビットを記憶する連想メモリセル間において共有に張られたラインにより構成されたことを特徴とする、付記２記載の連想メモリ装置。
（付記５）  該エントリユニットが複数そなえられたエントリブロックを複数個相互に接続するための外部接続手段をそなえるとともに、該突合せ・マスク状態出力手段が、該外部接続手段を通じて、各エントリブロックを構成するエントリユニット間相互に反映された前記結果情報を出力するように構成されたことを特徴とする、付記１記載の連想メモリ装置。
【０１２８】
（付記６）  該外部接続手段が、各エントリブロックにおける該突合せ・マスク状態出力手段を直列に接続されたことを特徴とする、付記５記載の連想メモリ装置。
（付記７）  該外部接続手段が、各エントリブロックにおける該突合せ・マスク状態出力手段を並列に接続されたことを特徴とする、付記５記載の連想メモリ装置。
【０１２９】
（付記８）  該外部接続手段に、上記相互に接続された複数個のエントリブロックにおける少なくとも一つを切り離し制御する制御回路部が介装されたことを特徴とする、付記５〜７のいずれかに記載の連想メモリ装置。
（付記９）  各エントリブロックが、該突合せ・マスク状態出力手段からの出力信号をエンコードするエンコード手段をそなえるとともに、該外部接続手段が、該エンコード手段にてエンコードされた出力信号について、各エントリブロック間でバス通信を行ないうるバスラインをそなえて構成された構成されたことを特徴とする、付記５記載の連想メモリ装置。
【０１３０】
（付記１０）  該突合せ・マスク状態出力手段が、各エントリデータの一部における同一桁のビットを記憶する連想メモリセル間において、共有に張られたラインにより構成されたことを特徴とする、付記２記載の連想メモリ装置。
（付記１１）  該突合せ・マスク状態出力手段が、各エントリデータの少なくとも下位１ビットを除く上位ビットにおける同一桁のビットを記憶する連想メモリセル間において、共有に張られたラインにより構成されたことを特徴とする、付記１０記載の連想メモリ装置。
【０１３１】
（付記１２）  該突合せ・マスク状態出力手段が、各エントリデータの少なくとも上位１ビットを除く下位ビットにおける同一桁のビットを記憶する連想メモリセル間において、共有に張られたラインにより構成されたことを特徴とする、付記１０記載の連想メモリ装置。
（付記１３）  前記各エントリデータの少なくとも下位１ビットが、検索目的のビットデータに対する突合せに重みを与える重みビットであることを特徴とする、付記１１記載の連想メモリ装置。
【０１３２】
（付記１４）  前記各エントリデータの少なくとも上位１ビットが、検索目的のビットデータに対する突合せに重みを与える重みビットであることを特徴とする、付記１２記載の連想メモリ装置。
（付記１５）  該検索結果出力手段が、該第２論理演算素子からの出力信号についてワイヤード接続するワイヤード接続ラインにより構成されたことを特徴とする、付記３記載の連想メモリ装置。
【０１３３】
（付記１６）  該突合せ・マスク状態出力手段が、第１論理演算素子からの出力信号についてワイヤード接続するワイヤード接続ラインにより構成されたことを特徴とする、付記３記載の連想メモリ装置。
（付記１７）  前記の第１論理演算素子または第２論理演算素子が、ＣＭＯＳ論理回路により構成されたことを特徴とする、付記３記載の連想メモリ装置。
【０１３４】
（付記１８）  前記の第１論理演算素子または第２論理演算素子が、ＮＭＯＳ論理回路により構成されたことを特徴とする、付記３記載の連想メモリ装置。
（付記１９）  前記の第１論理演算素子または第２論理演算素子が、ＰＭＯＳ論理回路により構成されたことを特徴とする、付記３記載の連想メモリ装置。
（付記２０）  出力先ルートに対応して宛先アドレスを記憶する連想メモリと、入力されるパケットに付された宛先アドレスを解析するとともに、該連想メモリを参照することにより得られた出力先ルートへ当該パケットが転送されるようにルーティング処理する出方路決定部とをそなえてなるルーティング装置であって、
該連想メモリが、
検索される宛先アドレスを構成するビットデータと、前記ビットデータにおいて必要なビット長をマスクするためのマスク識別用データとを有してなる、互いに異なるエントリデータを記憶するとともに、それぞれのエントリデータと、検索キーとなる宛先アドレスを構成するビットデータとの突合せを行なう複数のエントリユニットと、
各エントリユニットにおける同一ビット桁単位の前記突合せの結果と当該ビット桁のマスク識別ビットとを反映した情報について入力され、各ビット桁単位でエントリユニット間相互に反映された反映結果情報として出力する突合せ・マスク状態出力手段とをそなえ、
各エントリユニットに、
前記突合せの結果、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータに一致する場合に、該突合せ・マスク状態出力手段からの前記反映結果情報を用いた論理演算により、当該エントリデータのうちでマスクされないビット長に関する情報を出力する論理演算手段と、
該論理演算手段からの出力信号に基づいて、自身のエントリユニットに記憶されたエントリデータが、前記キーとなるビットデータとの突合せが一致する全てのエントリデータのうちで、マスクされないビット長が最も長いエントリデータである場合にのみ、前記検索キーに対する検索該当情報を出力する検索結果出力手段をそなえて構成されたことを
特徴とする、ルーティング装置。
【０１３６】
【発明の効果】
以上詳述したように、本発明によれば、エントリユニットに、論理演算手段と検索結果出力手段とをそなえたことにより、アップデート作業の負荷を軽減して時間短縮を図るとともに、大容量化に容易に対応できるような構成としつつ、クロックを必要とせずに一回の検索動作でロンゲスト・プリフィックス・マッチ結果を出力することができ、検索時間の短縮化を図ることができるほか、アップデート作業の簡素化や時間短縮を図ることが可能となり、ネットワークの高速化に貢献することができる利点がある。
【図面の簡単な説明】
【図１】本発明の第１実施形態にかかる連想メモリ装置としてのＣＡＭを示す図である。
【図２】本発明の第１実施形態にかかる連想メモリセルを示すブロック図である。
【図３】本発明の第１実施形態におけるネットワーク構成を示す図である。
【図４】（ａ）はプリフィックス・マッチ・ラインを等価的に示す図であり、（ｂ）はロンゲスト・プリフィックス・マッチ・ラインを等価的に示す図である。
【図５】本発明の第１実施形態の動作例を説明するための図である。
【図６】本発明の第１実施形態の動作例を説明するための図である。
【図７】本発明の第１実施形態の動作例を説明するための図である。
【図８】本発明の第１実施形態の動作例を説明するための図である。
【図９】本発明の第１実施形態の第１変形例における連想メモリ装置を示す図である。
【図１０】本発明の第１実施形態の第１変形例におけるルータの動作を説明するための図である。
【図１１】本発明の第１実施形態の第２変形例における連想メモリ装置を示す図である。
【図１２】本発明の第２実施形態にかかる連想メモリ装置を示す図である。
【図１３】本発明の第２実施形態の第１変形例にかかる連想メモリ装置を示す図である。
【図１４】本発明の第２実施形態の第２変形例にかかる連想メモリ装置を示す図である。
【図１５】ロンゲスト・プリフィックス・マッチ検索を行なうＣＡＭデバイスとしての３値ＣＡＭを示す図である。
【図１６】図１５のエントリユニットを構成するＣＡＭセルを示すブロック図である。
【符号の説明】
１，２ａ，２ｂ，２ｃ，３ａ，３ｂ，３ｃ，４，５  ルータ
５−１  出方路決定部
１０１  アドレス
１０２  マッチ・ライン
１０３−１〜１０３−ｎ  エントリユニット
１０４  宛先アドレス
１０５  プリフィックス・ビット
１０６  プライオリティエンコーダ（Priority encoder）
２０１  データレジスタ
２０２  マスクレジスタ
２０３  コンパレータ
２０４  マスク回路
２０５  マッチ・ライン
２０６，２０７  ビットライン
４００，４００Ａ，４００Ｂ  連想メモリ装置（ＣＡＭ）
４０１−１〜４０１−ｎ  エントリユニット
４０２  回路部
４０３−１〜４０３−ｎ  マルチ・マッチ・ライン
４０４，４０４−１〜４０４−ｋ  プリフィックス・マッチ・ライン
４０４Ａ  ＮＯＲ回路
４０５−１〜４０５−ｎ  ロンゲスト・プリフィックス・マッチ・ライン
４０５Ａ  ＯＲ回路
４０６，４０７  ＡＮＤ回路
４０８，４０８′  エンコーダ
４１０，４１０Ａ  連想メモリセル
５０１  データレジスタ
５０２  マスクレジスタ
５０３  コンパレータ
５０４  マスク回路
５０６，５０７  ビットライン
６００，７００  連想メモリ装置
６０１−１〜６０１−ｍ，７０１−１〜７０１−ｍ  ＣＡＭ
６０２，６０２−１〜６０２−ｋ  外部接続ライン
７０３，７０３−１〜７０３−ｋ  外部接続ライン
７０４−１〜７０４−ｍ  ブロック制御信号
７０５−１〜７０５−ｍ  制御回路部
７０６  エンコーダ
７０８  制御回路
８００  連想メモリ装置
８０１，８１１  ＣＡＭ
８０３  エンコーダ
８１０  バス
【図１】
0003863733.tif 000002
【図２】
0003863733.tif 000003
【図３】
0003863733.tif 000004
【図４】
0003863733.tif 000005
【図５】
0003863733.tif 000006
【図６】
0003863733.tif 000007
【図７】
0003863733.tif 000008
【図８】
0003863733.tif 000009
【図９】
0003863733.tif 000010
【図１０】
0003863733.tif 000011
【図１１】
0003863733.tif 000012
【図１２】
0003863733.tif 000013
【図１３】
0003863733.tif 000014
【図１４】
0003863733.tif 000015
【図１５】
0003863733.tif 000016
【図１６】
0003863733.tif 000017