(57)【要約】      （修正有）【課題】ネットワーク装置の消費電力を低減すること、及び高速にデータを転送できるネットワーク・システムを提供する。【解決手段】経路情報テーブルを具備するネットワーク装置において、１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、一致するワード内の経路情報同士の論理演算結果を中間データとして出力する１次検索手段と、中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、経路情報に対しワード毎に圧縮演算を行って得られた第２の記憶データを経路情報の各ワードに対応させて格納し、２次検索データをワード単位で第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段とを具備する。【選択図】なし【特許請求の範囲】
【請求項１】
経路情報を格納する複数のワードと、前記経路情報の１個または複数個に対応し前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能な１個または複数個のマスク情報とから構成される経路情報テーブルを具備するネットワーク装置において、
１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で前記経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、
一致するワード内の前記経路情報同士の論理演算結果を中間データとして出力する１次検索手段と、
前記中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、
前記経路情報に対しワード毎に前記圧縮演算を行って得られた第２の記憶データを前記経路情報の各ワードに対応させて格納し、
前記２次検索データをワード単位で前記第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段と、
ワード毎に１次一致信号が不一致のとき対応する前記２次一致信号を不一致状態にすることにより最終一致信号を生成する無効化手段と、
前記最終一致信号に基づき前記入力通信データに対応する出力通信データの転送先アドレスを決定する手段とを、
具備することを特徴とするネットワーク装置。
【請求項２】
経路情報を格納する複数のワードと、前記経路情報の１個または複数個に対応し前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能な１個または複数個のマスク情報とから構成される経路情報テーブルを備え、
１次検索データとして入力通信データ中の宛先ネットワーク・アドレスが入力されたとき、前記宛先ネットワーク・アドレスをワード単位で前記経路情報と比較する１次検索を行い、一致するワード内の前記経路情報同士の論理演算結果を中間データとして生成し、
前記中間データに対してビット幅を圧縮する演算を行い２次検索データを生成し、
前記１次検索において一致した１個または複数個の前記ワード内の経路情報に対して前記圧縮演算を行って得られた結果と前記２次検索データをワード単位で比較する２次検索を行い、
前記２次検索において一致したワードに対応する前記経路情報に基づき、前記入力通信データに対応する出力通信データの転送先アドレスを決定することを、
特徴とするネットワーク装置の転送先アドレス決定方法。
【請求項３】
経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを具備するネットワーク装置において、
１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で前記経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、
一致するワード内の前記マスク情報同士と前記１次検索データとの論理演算結果を中間データとして出力する１次検索手段と、
前記中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、
前記経路情報に対しワード毎に前記圧縮演算を行って得られた第２の記憶データを前記経路情報の各ワードに対応させて格納し、
前記２次検索データをワード単位で前記第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段と、
ワード毎に１次一致信号が不一致のとき対応する前記２次一致信号を不一致状態にすることにより最終一致信号を生成する無効化手段と、
前記最終一致信号に基づき前記入力通信データに対応する出力通信データの転送先アドレスを決定する手段とを、
具備することを特徴とするネットワーク装置。
【請求項４】
経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを備え、
１次検索データとして入力通信データ中の宛先ネットワーク・アドレスが入力されたとき、前記宛先ネットワーク・アドレスをワード単位で前記経路情報と比較する１次検索を行い、一致するワード内の前記マスク情報同士と前記１次検索データとの論理演算結果を中間データとして生成し、
前記中間データに対してビット幅を圧縮する演算を行い２次検索データを生成し、
前記１次検索において一致した１個または複数個の前記ワード内の経路情報に対して前記圧縮演算を行って得られた結果と前記２次検索データをワード単位で比較する２次検索を行い、
前記２次検索において一致したワードに対応する前記経路情報に基づき、前記入力通信データに対応する出力通信データの転送先アドレスを決定することを、
特徴とするネットワーク装置の転送先アドレス決定方法。
【請求項５】
経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを具備するネットワーク装置において、
１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で前記経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、
一致するワード内の前記マスク情報同士の論理演算結果を中間データとして出力する１次検索手段と、
前記中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、
前記マスク情報に対しワード毎に前記圧縮演算を行って得られた第２の記憶データを前記経路情報の各ワードに対応させて格納し、
前記２次検索データをワード単位で前記第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段と、
ワード毎に１次一致信号が不一致のとき対応する前記２次一致信号を不一致状態にすることにより最終一致信号を生成する無効化手段と、
前記最終一致信号に基づき前記入力通信データに対応する出力通信データの転送先アドレスを決定する手段とを、
具備することを特徴とするネットワーク装置。
【請求項６】
経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを備え、
１次検索データとして入力通信データ中の宛先ネットワーク・アドレスが入力されたとき、前記宛先ネットワーク・アドレスをワード単位で前記経路情報と比較する１次検索を行い、一致するワード内の前記マスク情報同士の論理演算結果を中間データとして生成し、
前記中間データに対してビット幅を圧縮する演算を行い２次検索データを生成し、
前記１次検索において一致した１個または複数個の前記ワード内のマスク情報に対して前記圧縮演算を行って得られた結果と前記２次検索データをワード単位で比較する２次検索を行い、
前記２次検索において一致したワードに対応する前記経路情報に基づき、前記入力通信データに対応する出力通信データの転送先アドレスを決定することを、
特徴とするネットワーク装置の転送先アドレス決定方法。
【請求項７】
請求項１、３又は５のいずれか１項に記載のネットワーク装置を介してネットワークに接続された通信機器間でデータ通信を行うことを特徴とするネットワーク・システム。
【請求項８】
請求項２、４又は６のいずれか１項に記載の方法を用い、ネットワークに接続された通信機器間でデータ通信を行うことを特徴とするネットワーク・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連想メモリおよびその検索方法およびネットワーク装置およびネットワーク・システムに関する。特に検索マスク機能を有する連想メモリとその検索方法およびネットワーク装置およびネットワーク・システムに関する。
【背景技術】
【０００２】
従来のコンピュ−タ・ネットワーク・システムに用いられるネットワーク装置（例えばルータ）では、最適転送先を計算するために、ネットワーク・アドレスの有効部分の長さを考慮して比較する機能が不可欠であり、この機能を実現するために連想メモリが用いられている。
【０００３】
従来のコンピュータ・ネットワークの一接続例を図１１に示す。ネットワークに参加しているユーザ機器（例えばパーソナル・コンピュータ）は、他のユーザ機器と識別するために、その機器がネットワークに参加するときに、あらかじめ決められた規則に従って特定のネットワーク・アドレスを割り当てられる。ここではネットワーク・アドレスは複数桁の数値、例えば３桁の数値（ａ．ｂ．ｃ）で表現されるものとして説明する。また、あらかじめ決められた規則は、例えばネットワーク・アドレスの先頭の数値でイギリス、ドイツ、日本などの国を示し、第２番目の数値で国の中の企業名を示す、というように階層構造をとっている。以降、この階層をセグメントと呼ぶこととする。
【０００４】
図１１においては、セグメントの階層構造を模擬的に示したものである。図において太線で囲まれた１つの矩形が１つのセグメントである。図１１では、ネットワーク・アドレスの先頭の数値が１であるセグメント１と、先頭の数値が２であるセグメント２と、先頭の数値が３であるセグメント３が、最上位のセグメントとして存在している。セグメント１の下の階層に、上位２つの数値が１．２であるネットワーク・アドレスを持つセグメント４と、上位２つの数値が１．３であるネットワーク・アドレスを持つセグメント５とがあり、セグメント４の中にネットワーク・アドレス１．２．６を持つユーザ機器４０１−１が接続されている。セグメント２の下の階層に、上位２つの数値が２．６であるネットワーク・アドレスを持つセグメント６があり、セグメント６の中にネットワーク・アドレス２．６．４を持つユーザ機器４０１−２とネットワーク・アドレス２．６．５を持つユーザ機器４０１−３とが接続されている。また、セグメント３の下の階層に、上位２つの数値が３．２であるネットワーク・アドレスを持つセグメント７がある。図に例示されているアドレスにおいて、＊はドント・ケアを意味する。
【０００５】
これら各ネットワーク・アドレスは、その各桁を８進数で表現した全体で９ビットのビット列で表現されるものと仮定する。例えば、ネットワーク・アドレス（１．２．＊）は２進数のビット列“００１．０１０．０００”で表現される。以降、この表現のビット列を記憶データと呼ぶ。ここで、ネットワーク・アドレスの中の＊はドント・ケアであるので、対応する２進数表現の記憶データ“００１．０１０．０００”のビット列の上位６ビットが有効であり、それ以下のビットは無効であることを示す必要がある。そこで、マスク情報と呼ばれる情報を記憶データと対にして記憶させている。以降、この対を構造化データと呼ぶ。前記の例では、対応するマスク情報は２進数表現のビット列“１１１．１１１．０００”で表現される。ここで、“１”がマスク無効状態を、“０”がマスク有効状態を示している。
【０００６】
各セグメントは、ネットワークに参加しているユーザ機器間の通信データを転送するためにネットワーク装置を、有している。図１１の接続例では、セグメント１はネットワーク装置４００−１を、セグメント２はネットワーク装置４００−２を、セグメント３はネットワーク装置４００−３を、セグメント４はネットワーク装置４００−４を、セグメント５はネットワーク装置４００−５を、セグメント６はネットワーク装置４００−６を、セグメント７はネットワーク装置４００−７を、それぞれ有している。また、図１１の接続例では、各ネットワーク装置はそのセグメント直下のネットワーク装置またはユーザ機器と接続されている。さらに、ネットワーク装置４００−１は、ネットワーク装置４００−２、ネットワーク装置４００−３，およびネットワーク装置４００−６とも接続している。
【０００７】
セグメントが有するネットワーク装置は、そのネットワーク装置に接続されているユーザ機器または他のネットワーク装置から入力された転送データを、転送データに付随する宛先ネットワーク・アドレスとネットワーク装置の接続関係を基に最適な転送ルートを計算し、その最適なルートを経由して転送先にデータを転送する機能を有する。
【０００８】
ここで図１１において宛先ネットワーク・アドレスがユーザ機器４０１−２に対応する（２．６．４）である通信データを、ネットワーク装置４００−１が転送する場合、図から明らかに分かるように、セグメント２を示すネットワーク・アドレス（２．＊．＊）に対応するネットワーク装置４００−２に転送するよりも、セグメント６を示すネットワーク・アドレス（２．６．＊）に対応するネットワーク装置４００−６に転送する方が、最適である。つまり、マスク情報を考慮して宛先ネットワーク・アドレスと一致するネットワーク・アドレスの中で、マスク有効状態のビット数が最も少ないマスク情報を持つネットワーク・アドレスに対応する、ネットワーク装置を選ぶのが最適であることがわかる。
【０００９】
このように、各ユーザ機器同士を直接通信回線で接続するのではなくネットワーク装置により転送データの転送を制御して通信を行うことにより、有限の通信回線を、効率よく使用している。
【００１０】
次に、これら従来のネットワーク装置の転送先ネットワーク・アドレス計算の説明を図１２を用いて行う。図ではネットワーク装置４００−１を例に示しているが、他のネットワーク装置もこれと同様に構成することができる。
【００１１】
ネットワーク装置４００−１に入力された転送データに付随する宛先ネットワーク・アドレスは、検索データ１０１として従来の連想メモリ１００に入力される。従来の連想メモリ１００は、ネットワーク装置４００−１に接続されているネットワーク装置４００−２、４００−３，４００−４、４００−５、および４００−６が属するセグメントを示すネットワーク・アドレスを、前述の構造化データの形式で格納している。従って図１２の例では、１次連想メモリ・ワード１０９−１には、ネットワーク装置４００−２が属するセグメント２を示すネットワーク・アドレス（２．＊．＊）を前述のように記憶データ“０１０．０００．０００”とマスク情報“１１１．０００．０００”の対で表現される構造化データの形式で格納している。同様に、１次連想メモリ・ワード１０９−２にはネットワーク装置４００−３が属するセグメント３を示すネットワーク・アドレス（３．＊．＊．）を、１次連想メモリ・ワード１０９−３にはネットワーク装置４００−４が属するセグメント４を示すネットワーク・アドレス（１．２．＊）を、１次連想メモリ・ワード１０９−４にはネットワーク装置４００−５が属するセグメント５を示すネットワーク・アドレス（１．３．＊）を、１次連想メモリ・ワード１０９−５にはネットワーク装置４００−６が属するセグメント６を示すネットワーク・アドレス（２．６．＊）を、上述の構造化データの形式で格納している。
【００１２】
連想メモリ１００は、通常のメモリと同様にアドレスを指定して記憶データの書き込み、読み出しを行う機能のほかに、対応するマスク情報を考慮して検索データ１０１と比較した結果一致する記憶データの中で、マスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線１０２を有効状態にする機能を有している。従来、この種の連想メモリ１００としては、例えば、日本特許３１９１７３７号などに開示されたものが知られている。
【００１３】
連想メモリ１００が出力した一致線１０２−１〜１０２−５はエンコーダ４０２によりメモリ・アドレス信号４０３に符号化される。メモリ４０４には、連想メモリ１００の各１次連想メモリ・ワード１０９−１〜１０９−５に格納されているセグメントを示すネットワーク・アドレスに対応するネットワーク装置のネットワーク・アドレスを、連想メモリ１００の格納アドレスと同一のアドレスのワードに格納している。たとえば、連想メモリ１００の１次連想メモリ・ワード１０９−１にはアドレス（２．＊．＊）が格納されているので、これに対応する図１１のネットワーク装置４００−２のネットワーク・アドレスがメモリ４０４のワード１に格納されている。同様にメモリ４０４のワード２にはネットワーク装置４００−３のネットワーク・アドレスが、ワード３にはネットワーク装置４００−４のネットワーク・アドレスが、ワード４にはネットワーク装置４００−５のネットワーク・アドレスが、ワード５にはネットワーク装置４００−６のネットワーク・アドレスが、格納されている。メモリ４０４はメモリ・アドレス信号４０３をリード・アドレスとして指定される格納データを、メモリ・データ信号４０５として出力する。メモリ・データ信号４０５は、転送データの新たな転送先ネットワーク・アドレスとして利用される。
【００１４】
なお、図には示していないが、各ネットワーク装置４００−１乃至４００−７はその内部にＣＰＵを有しており、そのＣＰＵにより上述したネットワーク装置の動作の制御が行われる。
【００１５】
次に、各従来のネットワーク装置による、転送先アドレス計算の動作例を説明する。例えばネットワーク装置４００−１に入力された転送データの宛先ネットワーク・アドレスがユーザ機器４０１−３に対応する（２．６．５）の場合、従来の連想メモリ１００で検索すると１次連想メモリ・ワード１０９−１の（２．＊．＊）、および１次連想メモリ・ワード１０９−５の（２．６．＊）が一致するが、その中でマスク情報の有効状態のビットが最も少ない１次連想メモリ・ワード１０９−５に対応する一致線１０２−５のみが有効状態となる。これにより、エンコーダ４０２はメモリ・アドレス信号４０３として“５”を出力し、メモリ４０４はワード５に格納されているネットワーク装置４００−６のネットワーク・アドレス（２．６．＊）をメモリ・データ信号４０５として出力する。これにより、ネットワーク装置４００−１は、付随する宛先ネットワーク・アドレスが（２．６．５）である入力通信データを、ネットワーク装置４００−６に向けて転送する。ネットワーク装置４００−６は転送されてきたデータに基づいて上述と同様な動作を行い、次々とネットワーク装置がデータを転送し、最終的に、宛先である（２．６．５）のネットワーク・アドレスを有するユーザ機器４０１−３にデータが転送されることになる。
【００１６】
（従来の連想メモリの説明）
図１３は、従来の連想メモリの構成例を示すブロック図である。ｎビットｍ語（ワードともいう）構成（ｍ、ｎは自然数）の連想メモリ１００は、ｎビットｍ語構成の１次検索用連想メモリ１０３と、ｎビットｍ語構成の２次検索用連想メモリ１０４とを有し、ｎビットの検索データ１０１を入力するための１次ビット線１０５−１〜１０５−ｎと、最終検索結果を出力するｍ本の一致線１０２−１〜１０２−ｍとを有する。
【００１７】
ｎビットｍ語構成の１次検索用連想メモリ１０３は、１次ビット線１０５−１〜１０５−ｎを入力とし、１次一致線１１６−１〜１１６−ｍおよび中間データ線１０６−１〜１０６−ｎを出力とする。１次検索用連想メモリ１０３は、各ｎビットの記憶データおよびマスク情報から構成される構造化データを格納できる１次連想メモリ・ワード１０９−１〜１０９−ｍを有する。１次連想メモリ・ワード１０９−ｊ（ｊは１以上ｍ以下の自然数）は、ｎビットの記憶データを格納するためのデータ・セル１１０−ｊ−１〜１１０−ｊ−ｎと、対応するｎビットのマスク情報を格納するためのマスク・セル１１１−ｊ−１〜１１１−ｊ−ｎとを有する。ここで、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットに対応するデータ・セル１１０に記憶データの無効状態を格納し、対応するマスク・セル１１１にマスク情報の有効状態を格納することにより表現するものとする。１次検索用連想メモリ１０３は、対応するマスク情報を考慮して１次ビット線１０５−１〜１０５−ｎの状態と比較した結果一致する記憶データを検索する１次検索を行い、一致した記憶データを格納している１次連想メモリ・ワード１０９に対応する１次一致線１１６に有効状態を出力し、他の１次一致線１１６には無効状態を出力する。また、一致した記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値を中間データ線１０６−１〜１０６−ｎに出力する。中間データ線１０６−１〜１０６−ｎの状態は、ｎビットの中間データ１０７として、２次ビット線１０８−１〜１０８−ｎに入力される。
【００１８】
ｎビットｍ語構成の２次検索用連想メモリ１０４は、２次ビット線１０８−１〜１０８−ｎを入力とし、２次一致線１２６−１〜１２６−ｍを出力とする。２次検索用連想メモリ１０４は、ｎビットの２次記憶データを格納できる２次連想メモリ・ワード１１２−１〜１１２−ｍを有する。ｊ番目の２次連想メモリ・ワード１１２−ｊは、ｎビットの２次記憶データを格納するためのデータ・セル１１３−ｊ−１〜１１３−ｊ−ｎを有する。２次検索用連想メモリ１０４は、２次ビット線１０８−１〜１０８−ｎの状態と一致する２次記憶データを検索する２次検索を行い、一致した２次記憶データを格納している２次連想メモリ・ワード１１２に対応する２次一致線１２６に有効状態を出力し、他の２次一致線１２６には無効状態を出力する。２次一致線１２６−１〜１２６−ｍの状態は、一致線１０２−１〜１０２−ｍとして、外部に出力される。本従来例ではｎビットの２次記憶データとして、データ・セル１１３−ｊ−１〜１１３−ｊ−ｎに、対応する１次連想メモリ・ワード１０９−ｊのデータセル１１０−ｊ−１〜１１０−ｊ−ｎに格納されているｎビットの記憶データと同じ値を格納している。
【００１９】
図１４は、ｎビットｍ語構成の従来の連想メモリ１００におけるｎビットｍ語構成の１次検索用連想メモリ１０３の構成例を示すブロック図である。ｎビットｍ語構成の１次検索用連想メモリ１０３は、ｎビットの１次連想メモリ・ワード１０９−１〜１０９−ｍと、抵抗１２１−１〜１２１−ｎと、反転論理ゲート１２２−１〜１２２−ｎとを有している。ｊ番目の１次連想メモリ・ワード１０９−ｊは、ｎ個の連想メモリ・セル１１８−ｊ−１〜１１８−ｊ−ｎを有している。ｊ番目の１次連想メモリ・ワード１０９−ｊには、対応するデータ・ワード線１１５−ｊと、マスク・ワード線１１７−ｊが入力のために接続され、対応する１次一致線１１６−ｊ、および一致データ中間論理線１１４−１〜１１４−ｎが出力のために接続され、ｎ本の１次ビット線１０５−１〜１０５−ｎが入出力のために接続されている。
【００２０】
ｊ番目の１次連想メモリ・ワード１０９−ｊのｋビット目（ｋは１以上ｎ以下の自然数）の連想メモリ・セル１１８−ｊ−ｋには、対応するデータ・ワード線１１５−ｊと、マスク・ワード線１１７−ｊが入力のために接続され、対応する１次一致線１１６−ｊ、および一致データ中間論理線１１４−ｋが出力のために接続され、１次ビット線１０５−ｋが入出力のために接続されている。
【００２１】
連想メモリ・セル１１８−ｊ−ｋは、１次ビット線１０５−ｋを介して外部から入力される記憶データの対応するビット情報を格納するデータ・セル１１０−ｊ−ｋと、データ・セル１１０−ｊ−ｋに記憶されたビット情報と外部から１次ビット線１０５−ｋを介して入力される情報とを比較する比較器１１９−ｊ−ｋと、外部から１次ビット線１０５−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル１１１−ｊ−ｋと、論理ゲート１２０−ｊ−ｋとを備えている。ここで、マスク・セル１１１−ｊ−ｋに格納されたビット情報がマスク有効状態の場合には、対応するデータ・セル１１０−ｊ−ｋには、記憶データの無効状態を格納する。
【００２２】
なお、本例では、マスク情報のマスク有効状態を“０”、マスク無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。記憶データと同様に、中間データ線１０６−１〜１０６−ｎの有効状態を“１”、無効状態を“０”とする。１次一致線１１６−１〜１１６−ｍ、２次一致線１２６−１〜１２６−ｍ、および一致線１０２−１〜１０２−ｍの有効状態を“１”、無効状態を“０”とする。
【００２３】
データ・セル１１０−ｊ−ｋは、対応するデータ・ワード線１１５―ｊが有効状態の場合、対応する１次ビット線１０５―ｋに書き込みデータがドライブされていれば記憶データとして格納し、対応する１次ビット線１０５―ｋがドライブされていなければ格納している記憶データを対応する１次ビット線１０５―ｋに出力する。対応するデータ・ワード線１１５−ｊが無効状態ならば、１次ビット線１０５−ｋに対してなんら操作は行わない。また、対応するデータ・ワード線１１５−ｊの値にかかわらず、格納している記憶データを同一の連想メモリ・セル１１８−ｊ−ｋの中の比較器１１９−ｊ−ｋと論理ゲート１２０−ｊ−ｋとに出力する。
【００２４】
マスク・セル１１１−ｊ−ｋは、対応するマスク・ワード線１１７−ｊが有効状態の場合、対応する１次ビット線１０５−ｋに書き込みデータがドライブされていれば書き込みデータをマスク情報として格納し、対応する１次ビット線１０５−ｋがドライブされていなければ、格納しているマスク情報を対応する１次ビット線１０５−ｋに出力する。対応するマスク・ワード線１１７−ｊが無効状態ならば、１次ビット線１０５―ｋに対してなんら操作は行わない。また、対応するマスク・ワード線１１７−ｊの値にかかわらず、格納しているマスク情報を同一の連想メモリ・セル１１８−ｊ−ｋの中の比較器１１９−ｊ−ｋに出力する。
【００２５】
１次一致線１１６−１〜１１６−ｍは、１次検索動作の開始前には、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【００２６】
比較器１１９−ｊ−ｋは、対応する１次ビット線１０５−ｋと、それに同一の連想メモリ・セル１１８−ｊ−ｋの中のデータ・セル１１０−ｊ−ｋに格納されている記憶データと、マスク・セル１１１−ｊ−ｋに格納されているマスク情報とを入力とする。比較器１１９−ｊ−ｋは、マスク情報がマスク有効状態“０”ならば、対応する１次一致線１１６−ｊを開放状態にし、それ以外の場合には、１次ビット線１０５−ｋの値と記憶データとが一致するならば対応する１次一致線１１６−ｊを開放状態にし、一致しないならば無効状態“０”を出力する。したがって、ｊ番目の１次連想メモリ・ワード１０９−ｊの中のｎ個の比較器１１９−ｊ−１〜１１９−ｊ−ｎがすべて１次一致線１１６−ｊを開放状態にしているときに、１次一致線１１６−ｊは有効状態“１”となり、それ以外の場合には無効状態“０”となる、１次一致線１１６の有効状態“１”を真としたワイアードＡＮＤ論理接続を構成している。つまり１次検索動作時には、マスク情報がマスク有効状態“０”のために比較対象から除外されたビットを除いて、１次連想メモリ・ワード１０９−ｊが格納している記憶データと１次ビット線１０５−１〜１０５−ｎの値とが完全に一致する場合に限り、１次一致線１１６−ｊは有効状態“１”となり、それ以外の場合は無効状態“０”となる。
【００２７】
論理ゲート１２０−ｊ−ｋは、同一の１次連想メモリ・ワード１０９−ｊの中の１次一致線１１６−ｊが有効状態“１”かつ、同一の連想メモリ・セル１１８−ｊ−ｋの中のデータ・セル１１０−ｊ−ｋに格納された記憶データが有効状態“１”のときに、対応する一致データ中間論理線１１４−ｋに中間データ線１０６の無効状態“０”を出力し、それ以外の場合には開放状態にする。一致データ中間論理線１１４−ｋは、抵抗１２１−ｋを介して中間データ線１０６の有効状態“１”に接続されており、対応するｍ個の論理ゲート１２０−１−ｋ〜１２０−ｍ−ｋとワイアード論理接続を構成している。したがって、接続されているｍ個の論理ゲート１２０−１−ｋ〜１２０−ｍ−ｋがすべて一致データ中間論理線１１４−ｋを開放状態にしているときに、一致データ中間論理線１１４−ｋは中間データ線１０６の有効状態“１”となり、それ以外の場合には中間データ線１０６の無効状態“０”となる。
【００２８】
反転論理ゲート１２２−１〜１２２−ｎは、対応する一致データ中間論理線１１４−１〜１１４−ｎの論理状態を反転し、中間データ線１０６−１〜１０６−ｎに出力する。
【００２９】
したがって、中間データ線１０６−ｋには、ｍ個の論理ゲート１２０−１−ｋ〜１２０−ｍ−ｋと、一致データ中間論理線１１４−ｋ、抵抗１２１−ｋ、および反転論理ゲート１２２−ｋにより、１次検索実行後に有効状態“１”となっている１次一致線１１６−１〜１１６−ｍを有するすべてのｋビット目の連想メモリ・セル１１８−１−ｋ〜１１８−ｍ−ｋの中のデータ・セル１１０−１−ｋ〜１１０−ｍ−ｋに格納されている記憶データどうしを、記憶データの有効状態を真とする論理和演算の結果が得られることになる。本例では、記憶データの有効状態“１”を真とする論理和演算の結果が得られる。これらの動作により、中間データ線１０６−１〜１０６−ｎには、１次検索実行後に検索データ１０１と一致した記憶データの中で、最も無効状態“０”のビット数が少ない記憶データと同じ値が出力されることになる。
【００３０】
図１５は、ｎビットｍ語構成の従来の連想メモリ１００におけるｎビットｍ語構成の２次検索用連想メモリ１０４の構成例を示すブロック図である。ｎビットｍ語構成の２次検索用連想メモリ１０４は、２次連想メモリ・ワード１１２−１〜１１２−ｍを有している。ｊ番目の２次連想メモリ・ワード１１２−ｊは、ｎ個の連想メモリ・セル１２３−ｊ−１〜１２３−ｊ−ｎを有している。２次連想メモリ・ワード１１２−ｊには、対応するデータ・ワード線１２５−ｊが入力のために接続され、対応する２次一致線１２６−ｊが出力のために接続され、ｎ本の２次ビット線１０８−１〜１０８−ｎが入出力のために接続されている。
【００３１】
ｊ番目の２次連想メモリ・ワード１１２−ｊのｋビット目の連想メモリ・セル１２３−ｊ−ｋには、対応するデータ・ワード線１２５−ｊが入力のために接続され、対応する２次一致線１２６−ｊが出力のために接続され、２次ビット線１０８−ｋが入出力のために接続されている。
【００３２】
連想メモリ・セル１２３−ｊ−ｋは、２次ビット線１０８−ｋを介して外部から入力される２次記憶データの対応するビット情報を格納するデータ・セル１１３−ｊ−ｋと、データ・セル１１３−ｊ−ｋに記憶されたビット情報と外部から２次ビット線１０８−ｋを介して入力される情報とを比較する比較器１２４−ｊ−ｋとを備えている。
【００３３】
データ・セル１１３−ｊ−ｋは、対応するデータ・ワード線１２５−ｊが有効状態の場合、対応する２次ビット線１０８−ｋに書き込みデータがドライブされていれば２次記憶データとして格納し、対応する２次ビット線１０８−ｋがドライブされていなければ格納している２次記憶データを対応する２次ビット線１０８−ｋに出力する。対応するデータ・ワード線１２５−ｊが無効状態ならば、２次ビット線１０８−ｋに対してなんら操作は行わない。また、対応するデータ・ワード線１２５−ｊの値にかかわらず、格納している２次記憶データを同一の連想メモリ・セル１２３−ｊ−ｋの中の比較器１２４−ｊ−ｋに出力する。
【００３４】
２次一致線１２６−１〜１２６−ｊは、２次検索動作の開始前には、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【００３５】
比較器１２４−ｊ−ｋは、対応する２次ビット線１０８−ｋと、それに同一の連想メモリ・セル１２３−ｊ−ｋの中のデータ・セル１１３−ｊ−ｋに格納されている２次記憶データとを入力とする。比較器１２４−ｊ−ｋは、２次ビット線１０８−ｋの値と２次記憶データとが一致するならば対応する２次一致線１２６−ｊを開放状態にし、一致しないならば無効状態“０”を出力する。ｊ番目の２次連想メモリ・ワード１１２−ｊの中のｎ個の比較器１２４−ｊ−１〜１２４−ｊ−ｎがすべて２次一致線１２６−ｊを開放状態にしているときに、２次一致線１２６−ｊは有効状態“１”となり、それ以外の場合には無効状態“０”となる、２次一致線１２６の有効状態“１”を真としたワイアードＡＮＤ論理接続を構成している。つまり２次検索動作時には、２次連想メモリ・ワード１１２−ｊが格納している２次記憶データと２次ビット線１０８−１〜１０８−ｋの値とが完全に一致する場合に限り、２次一致線１２６−ｊは有効状態“１”となり、それ以外の場合は無効状態“０”となる。
【００３６】
（従来の連想メモリの動作）
次に、上述の従来の連想メモリ１００を、図１１のネットワーク装置４００−１における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図１６を用いて説明する。したがって図１６では、連想メモリ１００を９ビット５語（ワード）の構成と仮定する。
【００３７】
各１次連想メモリ・ワード１０９−１〜１０９−５に格納されている記憶データ、マスク情報として、図１１のネットワーク装置４００−１の接続情報が記憶されているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態“０”、マスク情報の該当ビットをマスク有効状態“０”とすることで表現される。
【００３８】
つまり、１次連想メモリ・ワード１０９−１にはセグメント２を示すネットワーク・アドレス（２．＊．＊）を構造化データで表現するため、２進数表現で記憶データとして “０１０．０００．０００”を、マスク情報として“１１１．０００．０００”を格納してある。同様に１次連想メモリ・ワード１０９−２にはセグメント３を示すネットワーク・アドレス（３．＊．＊）を構造化データで表現するため、２進数表現で記憶データとして “０１１．０００．０００”を、マスク情報として“１１１．０００．０００”を格納してある。１次連想メモリ・ワード１０９−３にはセグメント４を示すネットワーク・アドレス（１．２．＊）を構造化データで表現するため、２進数表現で記憶データとして “００１．０１０．０００”を、マスク情報として“１１１．１１１．０００”を格納してある。１次連想メモリ・ワード１０９−４にはセグメント５を示すネットワーク・アドレス（１．３．＊）を構造化データで表現するため、２進数表現で記憶データとして “００１．０１１．０００”を、マスク情報として“１１１．１１１．０００”を格納してある。１次連想メモリ・ワード１０９−５にはセグメント６を示すネットワーク・アドレス（２．６．＊）を構造化データで表現するため、２進数表現で記憶データとして “０１０．１１０．０００”を、マスク情報として“１１１．１１１．０００”を格納してある。
【００３９】
また、２次検索用連想メモリ１０４の２次連想メモリ・ワード１１２−１〜１１２−５には、対応する１次連想メモリ・ワード１０９−１〜１０９−５の記憶データと同一の値を２次記憶データとして格納しているものとする。したがって、２次連想メモリ・ワード１１２−１には２進数表現で“０１０．０００．０００”が、２次連想メモリ・ワード１１２−２には２進数表現で“０１１．０００．０００”が、２次連想メモリ・ワード１１２−３は２進数表現で“００１．０１０．０００”が、２次連想メモリ・ワード１１２−４には２進数表現で“００１．０１１．０００”が、２次連想メモリ・ワード１１２−５には２進数表現で“０１０．１１０．０００”が、それぞれ格納されている。
【００４０】
１次検索動作の前には、すべての１次一致線１１６−１〜１１６−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。また、２次検索動作の前には、すべての２次一致線１２６−１〜１２６−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【００４１】
以降、検索データ１０１として図１１のユーザ機器４０１−３の８進数表現のネットワーク・アドレス（２．６．５）を入力し検索動作を行った場合の動作説明をする。
【００４２】
検索データ１０１の９ビットの２進数表現の値“０１０．１１０．１０１”は、９本の１次ビット線１０５−１〜１０５−９に入力され、１次検索用連想メモリ１０３は１次検索を実行する。結果として、１次連想メモリ・ワード１０９−１に格納されている８進数表現の（２．＊．＊）と、１次連想メモリ・ワード１０９−５に格納されている８進数表現の（２．６．＊）が１次ビット線１０５−１〜１０５−９の状態と一致する。従って、１次検索の結果として、１次一致線１１６−１、１１６−５の２本が有効状態“１”となり、残りの１次一致線１１６−２、１１６−３、および１１６−４は無効状態“０”となる。
【００４３】
このとき、中間データ線１０６−１からは、１次連想メモリ・ワード１０９−１内の対応する記憶データ“０”と１次連想メモリ・ワード１０９−５内の対応する記憶データ“０”とに対しての、“１”を真とした論理和結果“０”が出力される。中間データ線１０６−２からは、１次連想メモリ・ワード１０９−１内の対応する記憶データ“１”と１次連想メモリ・ワード１０９−５内の対応する記憶データ“１”とに対しての、“１”を真とした論理和結果“１”が出力される。以降同様に、中間データ線１０６−３からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１０６−４からは“０”と“１”とに対しての“１”を真とした論理和結果“１”が、中間データ線１０６−５からは“０”と“１”とに対しての“１”を真とした論理和結果“１”が、中間データ線１０６−６からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１０６−７からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１０６−８からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１０６−９からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、それぞれ出力される。従って、中間データ１０７として、２進数表現で“０１０１１００００”が得られる。
【００４４】
中間データ１０７の値は、２次ビット線１０８−１〜１０８−９に入力され、２次検索用連想メモリ１０４は２次検索を実行する。結果として、２次連想メモリ・ワード１１２−５に格納されている２進数表現の“０１０１１００００”のみが２次ビット線１０８−１〜１０８−９の状態と完全に一致する。したがって、２次一致線１２６−５のみが有効状態“１”となり、残りの２次一致線１２６−１、１２６−２、１２６−３、および１２６−４は無効状態“０”となる。これにより連想メモリ１００は一致線１０２−５のみに有効状態“１”を出力することになる。
【００４５】
したがって、従来の連想メモリ１００は、入力した検索データ１０１と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線１０２−５のみに有効状態を出力できることがわかる。また、図示しないクロック信号により１次検索、２次検索にそれぞれ１クロック時間を要する場合においても、１次検索を実行する１次検索用連想メモリ１０３と、２次検索用連想メモリを実行する２次検索用連想メモリ１０４を独立に有しているため、１クロック毎に検索データ１０１を入力し、転送先ネットワーク・アドレスの計算を実行することが可能なことがわかる。
【００４６】
上述した従来のｎビットｍ語構成の連想メモリ１００は、ｎビットｍ語構成の１次検索用連想メモリ１０３が生成したｎビットの中間データ１０７を２次検索用連想メモリ１０４の入力とするため、２次検索用連想メモリ１０４はｎビットｍ語構成とする必要がある。
【００４７】
ここで１次検索用連想メモリ１０３のデータ・セル１１０−１−１〜１１０−ｍ−ｎ、マスク・セル１１１−１−１〜１１１−ｍ−ｎ、および２次検索用連想メモリ１０４のデータ・セル１１３−１−１〜１１３−ｍ−ｎは、６個のＭＯＳトランジスタから構成される一般的なスタティックＲＡＭ素子で構成できる。この場合、スタティックＳＲＡＭ素子を構成する各ＭＯＳトランジスタの面積は、一般的に、従来の連想メモリ１００を製造する際に許される最小面積のＭＯＳトランジスタと等しい。
【００４８】
ところが、図１４に示すように１次一致線１１６−ｊは、ｎ個の連想メモリ・セル１１８−ｊ−１〜１１８−ｊ−ｎの中の比較器１１９−ｊ−１〜１１９−ｊ−ｎとワイアード論理接続をするための配線長が必要であるために配線容量は非常に大きく、その配線容量を駆動するため、比較器１１９を構成するＭＯＳトランジスタの面積は非常に大きくなる。例えば、０．２５μｍ製造プロセスの場合、６４個の連想メモリ・セル１１８を接続するためには１ｍｍほどの配線長が必要となり、この配線長の配線容量はおよそ０．３ｐＦ程度となる。この容量を駆動するためのトランジスタ・サイズは製造プロセスで許される最小面積のＭＯＳトランジスタの１０〜３０倍は必要である。同様に、図１５に示すように２次一致線１２６−ｊも、ｎ個の連想メモリ・セル１２３−ｊ−１〜１２３−ｊ−ｎとワイアード論理接続をするための配線長が必要であり、比較器１２４を構成するＭＯＳトランジスタの面積も、最小面積のＭＯＳトランジスタの１０〜３０倍は必要となる。また、図１４に示すように、一致データ中間論理線１１４−ｋも、ｍ個の１次連想メモリ・ワード１０９−１〜１０９−ｍの中の論理ゲート１２０−１−ｋ〜１２０−ｍ−ｋとワイアード論理接続をするための配線長が必要であり、論理ゲート１２０を構成するＭＯＳトランジスタの面積も、最小面積のＭＯＳトランジスタの１０〜３０倍は必要であることになる。
【００４９】
ここで、比較器１１９，比較器１２４、および論理ゲート１２０を構成するＭＯＳトランジスタの面積を、最小面積のＭＯＳトランジスタの１０倍と仮定し、また、比較器１１９は４個のＭＯＳトランジスタにより構成され、比較器１２０は３個のＭＯＳトランジスタにより構成され、論理ゲート１２０は２個のＭＯＳトランジスタにより構成されると仮定すると、１次検索用連想メモリ１０３を構成する連想メモリ・セル１１８の面積は最小面積のＭＯＳトランジスタの７２倍となり、２次検索用連想メモリ１０４を構成する連想メモリ・セル１２３の面積は最小面積のＭＯＳトランジスタの３６倍となる。
【００５０】
したがって、従来のｎビットｍ語構成の連想メモリ１００では、１次検索用連想メモリ１０３と２次検索用連想メモリ１０４とは、ともにｎビットｍ語構成であるから、１次検索用連想メモリ１０３以外の構成要素の合計面積として、検索データ１０１のビット幅によらずに、１次検索用連想メモリ１０３の面積の０．５０倍も必要であるという問題があった。
【００５１】
また、ｍ本の１次一致線１１６−１〜１１６−ｍの中で１次検索後も有効状態を保持するのは、最大でも、マスク情報のビット長と同じｎ本のみであり、残りの（ｍ−ｎ）本は検索前に有効状態にプリ・チャージした電荷を放電することになる。ｍ本の２次一致線１２６−１〜１２６−ｍの中で２次検索後も有効状態を保持するのは１本のみであり、残りの（ｍ−１）本は検索前に有効状態にプリ・チャージした電荷を放電することになる。従って、１語６４ビットで３２７６８語構成の場合、１次一致線１１６、２次一致線１２６を合わせて、最小の場合においても、（３２７６８−６４）＋（３２７６８−１）＝６５４７１本の配線容量を検索動作のたびにプリ・チャージしなければならない。一致データ中間論理線１１４−１〜１１４−ｎ、１次ビット線１０５−１〜１０５−ｎ、２次ビット線１０８−１〜１０８−ｎはともにｎ本であり、上述の例では計１９２本であるので無視できる。すなわち、従来の連想メモリ１００の消費電力のほとんどは、１次一致線１１６、２次一致線１２６を検索動作のたびにプリ・チャージするのに要する電力であることがわかる。ここで、０．２５μｍ製造プロセスで１語６４ビットで３２７６８語構成の場合には、１次一致線１１６、２次一致線１２６の１本あたりの配線容量は前述のようにそれぞれおよそ０．３ｐＦとなる。したがって、電源電圧を２．５Ｖとし、検索を実行する周期を２０ｎｓとすると、チップ全体の消費電力は、
（０.３ｐＦ×２.５Ｖ）÷２０ｎｓ×２.５Ｖ×６５４７１本＝６.１４Ｗ
となり、消費電力が非常に大きいという問題があった。
【００５２】
そのため、従来の連想メモリ１００を転送先ネットワーク・アドレスの計算に用いたネットワーク装置の消費電力も非常に大きくなってしまうという問題があった。
【００５３】
特許文献１の日本特許３１９１７３７号には、１次検索用連想メモリに、ｎビットの選択手段とｎビットの記憶手段とを設けるとともに、各連想メモリ・セル内の比較器の動作を制御することにより、１次検索用連想メモリのトランジスタ数をほとんど増加させることなしに２次検索用連想メモリの構成要素を兼用させる構成例も記載されている。この場合には、上述のチップ面積、消費電力の問題は解決されるが、同一の構成要素を１次検索、２次検索で兼用するために、１クロック毎に検索データ１０１を入力することはできず、転送先ネットワーク・アドレスの計算の実行速度は、上述の連想メモリ１００の場合の２分の１以下に低下してしまうという問題があった。
【特許文献１】日本特許３１９１７３７号
【発明の開示】
【発明が解決しようとする課題】
【００５４】
そこで、本発明の目的は、検索データと一致する記憶データの中で対応するマスク情報の有効状態のビット数が最も少ない記憶データを識別する信号を出力する演算を１クロック毎に実行可能であり、なおかつ単位チップ面積あたりの記憶容量の大きい連想メモリを提供することにある。
【００５５】
他の目的は、検索データと一致する記憶データの中で対応するマスク情報の有効状態のビット数が最も少ない記憶データを識別する信号を出力する演算を１クロック毎に実行可能であり、なおかつ消費電力の小さい連想メモリを提供することである。
【００５６】
更に他の目的は、ネットワーク装置の消費電力を低減すること、及び高速にデータを転送できるネットワーク・システムを提供することにある。
【課題を解決するための手段】
【００５７】
上記目的を達成するために、本発明では、手段１として、経路情報を格納する複数のワードと、前記経路情報の１個または複数個に対応し前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能な１個または複数個のマスク情報とから構成される経路情報テーブルを具備するネットワーク装置において、１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で前記経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、一致するワード内の前記経路情報同士の論理演算結果を中間データとして出力する１次検索手段と、前記中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、前記経路情報に対しワード毎に前記圧縮演算を行って得られた第２の記憶データを前記経路情報の各ワードに対応させて格納し、前記２次検索データをワード単位で前記第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段と、ワード毎に１次一致信号が不一致のとき対応する前記２次一致信号を不一致状態にすることにより最終一致信号を生成する無効化手段と、前記最終一致信号に基づき前記入力通信データに対応する出力通信データの転送先アドレスを決定する手段とを、具備することを特徴とするネットワーク装置。
【００５８】
手段２として、経路情報を格納する複数のワードと、前記経路情報の１個または複数個に対応し前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能な１個または複数個のマスク情報とから構成される経路情報テーブルを備え、１次検索データとして入力通信データ中の宛先ネットワーク・アドレスが入力されたとき、前記宛先ネットワーク・アドレスをワード単位で前記経路情報と比較する１次検索を行い、一致するワード内の前記経路情報同士の論理演算結果を中間データとして生成し、前記中間データに対してビット幅を圧縮する演算を行い２次検索データを生成し、前記１次検索において一致した１個または複数個の前記ワード内の経路情報に対して前記圧縮演算を行って得られた結果と前記２次検索データをワード単位で比較する２次検索を行い、前記２次検索において一致したワードに対応する前記経路情報に基づき、前記入力通信データに対応する出力通信データの転送先アドレスを決定することを特徴とするネットワーク装置の転送先アドレス決定方法。
【００５９】
手段３として、経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを具備するネットワーク装置において、１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で前記経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、一致するワード内の前記マスク情報同士と前記１次検索データとの論理演算結果を中間データとして出力する１次検索手段と、前記中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、前記経路情報に対しワード毎に前記圧縮演算を行って得られた第２の記憶データを前記経路情報の各ワードに対応させて格納し、前記２次検索データをワード単位で前記第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段と、ワード毎に１次一致信号が不一致のとき対応する前記２次一致信号を不一致状態にすることにより最終一致信号を生成する無効化手段と、前記最終一致信号に基づき前記入力通信データに対応する出力通信データの転送先アドレスを決定する手段とを具備することを特徴とするネットワーク装置。
【００６０】
手段４として、経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを備え、１次検索データとして入力通信データ中の宛先ネットワーク・アドレスが入力されたとき、前記宛先ネットワーク・アドレスをワード単位で前記経路情報と比較する１次検索を行い、一致するワード内の前記マスク情報同士と前記１次検索データとの論理演算結果を中間データとして生成し、前記中間データに対してビット幅を圧縮する演算を行い２次検索データを生成し、前記１次検索において一致した１個または複数個の前記ワード内の経路情報に対して前記圧縮演算を行って得られた結果と前記２次検索データをワード単位で比較する２次検索を行い、前記２次検索において一致したワードに対応する前記経路情報に基づき、前記入力通信データに対応する出力通信データの転送先アドレスを決定することを特徴とするネットワーク装置の転送先アドレス決定方法。
【００６１】
手段５として、経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを具備するネットワーク装置において、１次検索データとして入力された、入力通信データ中の宛先ネットワーク・アドレスをワード単位で前記経路情報と比較し、一致するワードを識別する１次一致信号を出力すると共に、一致するワード内の前記マスク情報同士の論理演算結果を中間データとして出力する１次検索手段と、前記中間データに対してビット幅を圧縮する演算を行い、２次検索データを生成する圧縮演算手段と、前記マスク情報に対しワード毎に前記圧縮演算を行って得られた第２の記憶データを前記経路情報の各ワードに対応させて格納し、前記２次検索データをワード単位で前記第２の記憶データと比較し、一致するワードを識別する２次一致信号を出力する２次検索手段と、ワード毎に１次一致信号が不一致のとき対応する前記２次一致信号を不一致状態にすることにより最終一致信号を生成する無効化手段と、前記最終一致信号に基づき前記入力通信データに対応する出力通信データの転送先アドレスを決定する手段とを具備することを特徴とするネットワーク装置。
【００６２】
手段６として、経路情報と、前記経路情報の各ビット列を検索対象から除外するか否かを対応するビットの状態により設定可能なマスク情報とを、対にして格納する複数のワードから構成される経路情報テーブルを備え、１次検索データとして入力通信データ中の宛先ネットワーク・アドレスが入力されたとき、前記宛先ネットワーク・アドレスをワード単位で前記経路情報と比較する１次検索を行い、一致するワード内の前記マスク情報同士の論理演算結果を中間データとして生成し、前記中間データに対してビット幅を圧縮する演算を行い２次検索データを生成し、前記１次検索において一致した１個または複数個の前記ワード内のマスク情報に対して前記圧縮演算を行って得られた結果と前記２次検索データをワード単位で比較する２次検索を行い、前記２次検索において一致したワードに対応する前記経路情報に基づき、前記入力通信データに対応する出力通信データの転送先アドレスを決定することを特徴とするネットワーク装置の転送先アドレス決定方法。
【００６３】
手段７として、請求項１、３又は５のいずれか１項に記載のネットワーク装置を介してネットワークに接続された通信機器間でデータ通信を行うことを特徴とするネットワーク・システム。
【００６４】
手段８として、請求項２、４又は６のいずれか１項に記載の方法を用い、ネットワークに接続された通信機器間でデータ通信を行うことを特徴とするネットワーク・システム。
【発明を実施するための最良の形態】
【００６５】
（第一の実施例の構成）
次に、本発明の第一の実施の形態について図面を参照して詳細に説明する。図１は、本発明の連想メモリ１の一構成例を示すブロック図である。ｎビットｍ語構成（ｍ、ｎは自然数）の連想メモリ１は、ｎビットｍ語構成の連想メモリ２と、ｐビットｍ語構成（ｐは自然数）の２次検索用連想メモリ３と、ｍ個の無効化手段２２−１〜２２−ｍとを有し、ｎビットの検索データ１０を入力するための１次ビット線１２−１〜１２−ｎと、最終検索結果を出力するｍ本の一致線１１−１〜１１−ｍを有する。
【００６６】
ｎビットｍ語構成の連想メモリ２は、ｎビットｍ語構成の１次検索用連想メモリ４と、計数手段１７とを有し、１次ビット線１２−１〜１２−ｎを入力とし、１次一致線１３−１〜１３−ｍおよび計数出力線１８−１〜１８−ｐを出力とする。
【００６７】
１次検索用連想メモリ４は、各ｎビットの記憶データおよびマスク情報から構成される構造化データを格納できる１次連想メモリ・ワード７−１〜７−ｍを有し、１次ビット線１２−１〜１２−ｎを入力とし、１次一致線１３−１〜１３−ｍおよび中間データ線１４−１〜１４−ｎを出力とする。１次連想メモリ・ワード７−ｊ（ｊは１以上ｍ以下の自然数）は、ｎビットの記憶データを格納するためのデータ・セル５−ｊ−１〜５−ｊ−ｎと、対応するｎビットのマスク情報を格納するためのマスク・セル６−ｊ−１〜６−ｊ−ｎとを有する。ここで、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットに対応するデータ・セル５に記憶データの無効状態を格納し、対応するマスク・セル６にマスク情報の有効状態を格納することにより表現するものとする。
【００６８】
１次検索用連想メモリ４は、対応するマスク情報を考慮して１次ビット線１２−１〜１２−ｎの状態と比較し、一致する記憶データを検索する１次検索を行い、一致した記憶データを格納している１次連想メモリ・ワード７に対応する１次一致線１３に有効状態を出力し、他の１次一致線１３には無効状態を出力する。また、一致した記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値を中間データ線１４−１〜１４−ｎにｎビットの中間データ１５として出力する。図から明らかなように、第一の実施の形態のｎビットｍ語構成の１次検索用連想メモリ４は、図１３を用いて説明した従来のｎビットｍ語構成の連想メモリ１００の１次検索用連想メモリ１０３と全く同様に構成することができる。ｎビットの中間データ１５の状態は、ｎ本の計数入力線１６−１〜１６−ｎに入力される。
【００６９】
計数手段１７は、ｎ本の計数入力線１６−１〜１６−ｎを入力とし、ｐ本の計数出力線１８−１〜１８−ｐを出力とする。計数手段１７は、ネットワーク・アドレスの最下位階層に対応する中間データ１５のビット位置から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数し、計数結果を計数出力線１８−１〜１８−ｐに、ｐビットの２次検索データ１９として出力する。ｐビットの２次検索データ１９は、ｐ本の２次ビット線２０−１〜２０−ｐに入力される。
【００７０】
このとき、計数結果の最小値は１０進数で０、最大値は１０進数でｎとなる。したがって、計数結果が２進数に符号化されている場合には計数出力線１８−１〜１８−ｐの本数ｐは、次の式１を満たす自然数となる。
ｐ−１  ≦  Ｌｏｇ２（ｎ＋１）  ≦  ｐ    ……  式１
【００７１】
Ｘを正の実数とし、関数Ｒｏｕｎｄｕｐ（Ｘ）を、正の実数Ｘの小数点以下を切り上げた整数に変換する関数と定義すると式１は次のように記述できる。
ｐ＝Ｒｏｕｎｄｕｐ（Ｌｏｇ２（ｎ＋１））    ……  式２
【００７２】
例えば、中間データ１５のビット幅ｎが１０進数で９の場合には２次検索データ１９のビット幅ｐは１０進数で４となり、中間データ１５のビット幅ｎが１０進数で１２８の場合には２次検索データ１９のビット幅ｐは１０進数で８となる。計数入力線１６−１〜１６−ｎの本数ｎが１０進数で９のときに計数結果を４ビットの２進数に符号化する計数手段１７の真理値表を、表１に示す。
【００７３】
【表１】
2007295553.tif 000002
表１において、＊はドント・ケアを表す。
【００７４】
計数入力線１６−１〜１６−ｎの本数ｎが９以外の場合にも同様に構成できることは言うまでもない。計数入力線１６−１〜１６−ｎの本数ｎが１０進数で６４の場合、計数手段１７は約８０００ゲート相当の組み合わせ回路で実現でき、０．２５μｍ製造プロセスで実現した場合、信号遅延は４ｎｓ程度となる。
【００７５】
ｐビットｍ語構成の２次検索用連想メモリ３は、２次ビット線２０−１〜２０−ｐを入力とし、２次一致線２１−１〜２１−ｍを出力とする。２次検索用連想メモリ３は、ｐビットの２次記憶データを格納できる２次連想メモリ・ワード９−１〜９−ｍを有する。ｊ番目の２次連想メモリ・ワード９−ｊは、ｐビットの２次記憶データを格納するためのデータ・セル８−ｊ−１〜８−ｊ−ｐを有する。２次検索用連想メモリ３は、２次ビット線２０−１〜２０−ｐの状態と一致する２次記憶データを検索する２次検索を行い、一致した２次記憶データを格納している２次連想メモリ・ワード９に対応する２次一致線２１に有効状態を出力し、他の２次一致線２１には無効状態を出力する。図から明らかなように、第一の実施の形態のｐビットｍ語構成の２次検索用連想メモリ３は、図１３を用いて説明した従来のｎビットｍ語構成の２次検索用連想メモリ１０４とは、１語の構成がｐビットに変更されている点を除き、全く同様に構成することができる。
【００７６】
ｍ本の２次連想メモリ・ワード９−１〜９−ｍは、ｍ本の１次連想メモリ・ワード７−１〜７−ｍと１対１に対応する。対応の仕方は任意であるが、本実施例ではｊ番目の２次連想メモリ・ワード９−ｊは、ｊ番目の１次連想メモリ・ワード７−ｊに対応するものとする。ｊ番目の２次連想メモリ・ワード９−ｊのデータ・セル８−ｊ−１〜８−ｊ−ｐには、計数手段１７がｎビットの計数入力線１６−１〜１６−ｎに対して実行する演算と同一の演算を、対応する１次連想メモリ・ワード７−ｊが格納しているｎビットの記憶データに対して実行した結果として得られるｐビットの演算結果を、ｐビットの２次記憶データとして格納する。
【００７７】
ｊ番目の無効化手段２２−ｊは、２次連想メモリ・ワード９−ｊが出力する２次一致線２１−ｊと、２次連想メモリ・ワード９−ｊに対応する１次連想メモリ・ワード７−ｊが出力する１次一致線１３−ｊとを入力とする。無効化手段２２−ｊは、１次一致線１３−ｊが１次一致線の無効状態である場合には一致線１１−ｊに一致線の無効状態を出力し、１次一致線１３−ｊが１次一致線の有効状態である場合には一致線１１−ｊに２次一致線２１−ｊの状態を出力する。図１では、無効化手段２２−ｊを、１次一致線の有効状態、２次一致線の有効状態を真とする論理積演算回路により構成した場合を示しているが、ワイアード論理回路などによっても構成可能なことは言うまでもない。
【００７８】
（第一の実施例の動作）
次に、上述の本発明の第一の実施の形態の連想メモリ１を、図１１のネットワーク装置４００−１における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図２を用いて説明する。したがって図２では連想メモリ１を９ビット５語構成と仮定する。検索データ１０のビット幅ｎが９であるから、連想メモリ２の中の１次検索用連想メモリ４は９ビット５語構成となる。また、検索データ１０のビット幅ｎが９であるから、式１より２次検索データ１９のビット幅ｐは４となり、２次検索用連想メモリ３の構成は４ビット５語構成となる。また、計数手段１７は、９ビットの計数入力線１６−１〜１６−９の状態を表１に従って４ビットに変換した値を、計数出力線１８−１〜１８−４に出力することになる。
【００７９】
なお、以下の本説明では、マスク情報のマスク有効状態を“０”、マスク無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。記憶データと同様に、中間データ線１４−１〜１４−９の有効状態を“１”、無効状態を“０”とする。１次一致線１３−１〜１３−５、２次一致線２１−１〜２１−５、および一致線１１−１〜１１−５の有効状態を“１”、無効状態を“０”とする。
【００８０】
各９ビットの１次連想メモリ・ワード７−１〜７−５に格納されている記憶データ、マスク情報として、図１１のネットワーク装置４００−１の接続情報が記憶されているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態“０”、マスク情報の該当ビットをマスク有効状態“０”とすることで表現される。
【００８１】
つまり、１次連想メモリ・ワード７−１にはセグメント２を示すネットワーク・アドレス（２．＊．＊）を構造化データで表現するため、２進数表現で記憶データには “０１０．０００．０００”を、マスク情報として“１１１．０００．０００”を格納してある。同様に１次連想メモリ・ワード７−２にはセグメント３を示すネットワーク・アドレス（３．＊．＊）を構造化データで表現するため、２進数表現で記憶データには “０１１．０００．０００”を、マスク情報として“１１１．０００．０００”を格納してある。１次連想メモリ・ワード７−３にはセグメント４を示すネットワーク・アドレス（１．２．＊）を構造化データで表現するため、２進数表現で記憶データには “００１．０１０．０００”を、マスク情報として“１１１．１１１．０００”を格納してある。１次連想メモリ・ワード７−４にはセグメント５を示すネットワーク・アドレス（１．３．＊）を構造化データで表現するため、２進数表現で記憶データには “００１．０１１．０００”を、マスク情報として“１１１．１１１．０００”を格納してある。１次連想メモリ・ワード７−５にはセグメント６を示すネットワーク・アドレス（２．６．＊）を構造化データで表現するため、２進数表現で記憶データには “０１０．１１０．０００”を、マスク情報として“１１１．１１１．０００”を格納してある。
【００８２】
また、各４ビットの２次連想メモリ・ワード９−１〜９−５には、計数手段１７が９ビットの計数入力線１６−１〜１６−９に対して実行する演算と同様に、対応する１次連想メモリ・ワード７−１〜７−５が格納している９ビットの記憶データの値を表１に従って４ビットに変換した値を、それぞれ２次記憶データとして格納する。したがって、２次連想メモリ・ワード９−１は、１次連想メモリ・ワード７−１が格納している記憶データ“０１０．０００．０００”を表１に従って変換した結果得られる、１０進数表現で７、２進数表現で“０１１１”を２次記憶データとして格納している。２次連想メモリ・ワード９−２は、１次連想メモリ・ワード７−２が格納している記憶データ“０１１．０００．０００”を表１に従って変換した結果得られる、１０進数表現で６、２進数表現で“０１１０”を２次記憶データとして格納している。２次連想メモリ・ワード９−３は、１次連想メモリ・ワード７−３が格納している記憶データ“００１．０１０．０００”を表１に従って変換した結果得られる、１０進数表現で４、２進数表現で“０１００”を２次記憶データとして格納している。２次連想メモリ・ワード９−４は、１次連想メモリ・ワード７−４が格納している記憶データ“００１．０１１．０００”を表１に従って変換した結果得られる、１０進数表現で３、２進数表現で“００１１”を２次記憶データとして格納している。２次連想メモリ・ワード９−５は、１次連想メモリ・ワード７−５が格納している記憶データ“０１０．１１０．０００”を表１に従って変換した結果得られる、１０進数表現で４、２進数表現で“０１００”を２次記憶データとして格納している。
【００８３】
１次検索動作の前には、すべての１次一致線１３−１〜１３−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。また、２次検索動作の前には、すべての２次一致線２１−１〜２１−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【００８４】
以降、検索データ１０として図１１のユーザ機器４０１−３の８進数表現のネットワーク・アドレス（２．６．５）を入力し検索動作を行った場合の動作説明をする。
【００８５】
検索データ１０の９ビットの２進数表現の値“０１０．１１０．１０１”は、９本の１次ビット線１２−１〜１２−９に入力され、連想メモリ２の中の１次検索用連想メモリ４は１次検索を実行する。結果として、１次連想メモリ・ワード７−１に格納されている８進数表現の（２．＊．＊）と、１次連想メモリ・ワード７−５に格納されている８進数表現の（２．６．＊）とが１次ビット線１２−１〜１２−９の状態と一致する。従って、１次検索の結果として、１次一致線１３−１、１３−５の２本が有効状態“１”となり、残りの１次一致線１３−２、１３−３、および１３−４は無効状態“０”となる。
【００８６】
このとき、中間データ線１４−１からは、１次連想メモリ・ワード７−１内の対応する記憶データ“０”と１次連想メモリ・ワード７−５内の対応する記憶データ“０”とに対しての、“１”を真とした論理和結果“０”が出力される。中間データ線１４−２からは、１次連想メモリ・ワード７−１内の対応する記憶データ“１”と１次連想メモリ・ワード７−５内の対応する記憶データ“１”とに対しての、“１”を真とした論理和結果“１”が出力される。以降同様に、中間データ線１４−３からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１４−４からは“０”と“１”とに対しての“１”を真とした論理和結果“１”が、中間データ線１４−５からは“０”と“１”とに対しての“１”を真とした論理和結果“１”が、中間データ線１４−６からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１４−７からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１４−８からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、中間データ線１４−９からは“０”と“０”とに対しての“１”を真とした論理和結果“０”が、それぞれ出力される。従って、９ビットの中間データ１５として、２進数表現で“０１０１１００００”が得られ、計数入力線１６−１〜１６−９に入力される。
【００８７】
計数手段１７は、９ビットの計数入力線１６−１〜１６―９の状態を表１に従って変換した結果得られる、１０進数表現で４、２進数表現で“０１００”の値を、４ビットの２次検索データ１９として計数出力線１８−１〜１８−４に出力する。
【００８８】
２次検索データ１９の値は、２次ビット線２０−１〜２０−４に入力され、２次検索用連想メモリ３は２次検索を実行する。結果として、２次連想メモリ・ワード９−３、および９−５に格納されている２進数表現の“０１００”が、２次ビット線２０−１〜２０−４の状態と完全に一致する。したがって、２次一致線２１−３、および２１−５が有効状態“１”となり、残りの２次一致線２１−１、２１−２、および２１−４は無効状態“０”となる。
【００８９】
２次検索終了後、１次一致線１３−１は有効状態“１”であるので無効化手段２２−１は２次一致線２１−１の状態“０”を一致線１１−１に出力する。１次一致線１３−２は無効状態“０”であるので無効化手段２２−２は無効状態“０”を一致線１１−２に出力する。１次一致線１３−３は無効状態“０”であるので無効化手段２２−３は無効状態“０”を一致線１１−３に出力する。１次一致線１３−４は無効状態“０”であるので無効化手段２２−４は無効状態“０”を一致線１１−４に出力する。１次一致線１３−５は有効状態“１”であるので無効化手段２２−５は２次一致線２１−５の状態“１”を一致線１１−５に出力する。したがって、２次検索終了後、一致線１１−５のみが有効状態“１”となり、残りの一致線１１−１、１１−２、１１−３、および１１−４は無効状態“０”となる。したがって、本発明の第一の実施の形態の連想メモリ１は、前述の従来の連想メモリ１００と同様に、入力した検索データ１０と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線１１−５のみに、正しく有効状態を出力できることがわかる。
【００９０】
また、従来の連想メモリ１００と同様に、本発明の第一の実施の形態の連想メモリ１は、図１に示すように１次検索を実行する１次検索用連想メモリ４と、２次検索を実行する２次検索用連想メモリ３とを独立に有しているため、図示しないクロック信号により１次検索、２次検索にそれぞれ１クロック時間を要するとした場合においても、１クロック毎に検索データ１０を入力し、転送先ネットワーク・アドレスの計算を実行することが可能である。
【００９１】
ここで、図１３に示す従来の連想メモリ１００と、図１に示す連想メモリ１との構成要素を比較すると、１次検索および中間データ生成を行う１次検索用連想メモリ１０３と１次検索用連想メモリ４とは共にｎビットｍ語構成で同一であるが、ｎビットｍ語構成の２次検索用連想メモリ１０４がｐビットｍ語構成の２次検索用連想メモリ３に変更されている点と、ｎビットの計数手段１７、およびｍ個の無効化手段２２−１〜２２−ｍが追加されている点が異なる。
【００９２】
前述のように、従来の連想メモリ１００の比較器１１９，比較器１２４、および論理ゲート１２０を構成するＭＯＳトランジスタの面積を、最小面積のＭＯＳトランジスタの１０倍と仮定し、また、比較器１１９は４個のＭＯＳトランジスタにより構成され、比較器１２０は３個のＭＯＳトランジスタにより構成され、論理ゲート１２０は２個のＭＯＳトランジスタにより構成されると仮定すると、１次検索用連想メモリ１０３を構成する連想メモリ・セル１１８の面積は最小面積のＭＯＳトランジスタの７２倍となり、２次検索用連想メモリ１０４を構成する連想メモリ・セル１２３の面積は最小面積のＭＯＳトランジスタの３６倍となる。
【００９３】
前述のように連想メモリ１の１次検索用連想メモリ４、２次検索用連想メモリ３の１ビットあたりの構成は、それぞれ従来の連想メモリ１００の１次検索用連想メモリ１０３，２次検索用連想メモリ１０４と同様である。したがって、１語６４ビットで３２７６８語構成の場合には、１次検索用連想メモリ４の面積は、最小面積のＭＯＳトランジスタの１５０９９４９４４倍となる。また、式１より２次連想メモリの構成は、７ビット３２７６８語構成となるので、２次検索用連想メモリ３の面積は、８２５７５３６倍となる。計数手段１７は前述のように６４ビット入力の場合で約８０００ゲートで構成でき、１ゲートは最小面積のＭＯＳトランジスタ４個で構成できると仮定すると、計数手段１７の面積は最小面積のＭＯＳトランジスタの３２０００倍となる。また無効化手段２２は論理積ゲートで構成することができ、１個の論理積ゲートは最小面積のＭＯＳトランジスタ６個で構成できると仮定すると、３２６７８個の無効化手段２２の面積の合計は、最小面積のＭＯＳトランジスタの１９６０６８倍となる。
【００９４】
上記のように無効化手段２２、計数手段１７の面積は、１次検索用連想メモリ４，２次検索用連想メモリ３の面積に比べて非常に小さいため無視することができる。したがって、従来の連想メモリ１００の面積を１としたとき、連想メモリ１の面積はチップ全体として、次の式３で表される。ここでは、正の実数Ｘの小数点以下を切り上げて正の整数に変換する前述のＲｏｕｎｄｕｐ（Ｘ）関数を用いて表現する。
（７２×ｎ＋３６×Ｒｏｕｎｄｕｐ（Ｌｏｇ２（ｎ＋１）））／
（（７２＋３６）×ｎ）  ……式３
【００９５】
式３から、検索データ１０のビット幅ｎが６４の場合には、連想メモリ１の面積は、従来の連想メモリ１００の面積の約７０．３％となり、約３１％の面積を削減することができる。したがって、本発明の連想メモリ１は、従来の連想メモリ１００と同一チップ面積の場合には、記憶容量を約４２．２％増大できることになる。さらに、式３から容易にわかるように、検索データ１０のビット幅ｎが大きくなるほど、本発明の面積削減効果も大きくなる。例えば検索データ１０のビット幅ｎが１２８ビットの場合には、連想メモリ１の面積は従来の連想メモリ１００の約６８．８％となる。
【００９６】
また、ｍ本の１次一致線１３−１〜１３−ｍの中で１次検索後も有効状態を保持するのは、従来の１次検索用連想メモリ１０３と同様に最大でも、マスク情報のビット長と同じｎ本のみであり、残りの（ｍ−ｎ）本は検索前に有効状態にプリ・チャージした電荷を放電することになる。０．２５μｍ製造プロセスで６４ビット３２７６８語の連想メモリ１を構成した場合、１本あたりの１次一致線１３の配線容量は前述のようにおよそ０．３ｐＦとなる。
【００９７】
したがって、電源電圧を２．５Ｖとし、検索を実行する周期を２０ｎｓとすると、３２７６８本の１次一致線１３のプリ・チャージに必要な合計消費電力の最小値は、
（0.3ｐＦ×2.5Ｖ）÷20ｎｓ×2.5Ｖ×（32768−64）本＝3.07Ｗ
となる。したがって、本発明の第一の実施の形態の連想メモリ１の１次検索用連想メモリ４の消費電力は、従来の連想メモリ１００の一次検索用連想メモリ１０３の消費電力と変わらない。
【００９８】
また、６４ビット３２７６８語構成の従来の連想メモリ１００の２次検索用連想メモリ１０４の消費電力は、上述のように、１次一致線１３と同じ配線容量を持つ２次一致線２１を最大（ｍ−１）本プリ・チャージする必要があることから、
（0.3ｐＦ×2.5Ｖ）÷20ｎｓ×2.5Ｖ×（32768−１）本＝3.07Ｗ
となる。
【００９９】
本発明の連想メモリ１の２次検索用連想メモリ３では、ｍ本の２次一致線２１−１〜２１−ｍの中で２次検索後も有効状態を保持するのは、最小１本、最大でｍ本であり、検索前に有効状態にプリ・チャージした電荷を放電することになるのは最大で（ｍ−１）本、最小では０本である。また、２次一致線２１の１本あたりの配線容量は２次検索用連想メモリ３のビット幅ｐに比例する。したがって、０．２５μｍ製造プロセスで６４ビット３２７６８語の連想メモリ１を構成した場合、電源電圧を２．５Ｖとし、検索を実行する周期を２０ｎｓとすると、２３７６８本の２次一致線２１のプリ・チャージに必要な合計消費電力の最大値は、
（0.3ｐＦ×2.5Ｖ）÷20ｎｓ×2.5Ｖ×７／64×（32768−１）本＝0.34Ｗ
となる。
【０１００】
ここで、上記のように連想メモリ１の語数ｍはビット幅ｎに比べて非常に大きいため、（ｍ−ｎ）≒（ｍ−１）の近似が成立する。したがって、従来の連想メモリ１００の消費電力を１としたとき、連想メモリ１のチップ全体の消費電力は、次の式４で表される。ここでは、正の実数Ｘの小数点以下を切り上げて正の整数に変換する、前述のＲｏｕｎｄｕｐ（Ｘ）関数を用いて表現する。
（１＋Ｒｏｕｎｄｕｐ（Ｌｏｇ２（ｎ＋１））／ｎ）／２  ……式４
【０１０１】
式４から、検索データ１０のビット幅ｎが６４の場合には、連想メモリ１の消費電力は、従来の連想メモリ１００の消費電力の約５５．４％となり、約４４．５％の消費電力を削減することができる。さらに、式４から容易にわかるように、検索データ１０のビット幅ｎが大きくなるほど、本発明の消費電力削減効果も大きくなる。例えば検索データ１０のビット幅ｎが１２８ビットの場合には、連想メモリ１の消費電力は従来の連想メモリ１００の約５３．１％となる。
【０１０２】
ここで、図１のｎビットの中間データ１５のすべてのビットが同時に無効状態とならない場合、すなわち、マスク情報の全ビットがマスク有効状態であるような構造化データを１次検索用連想メモリ４に格納していない場合には、計数結果の最小値は１０進数で０、最大値は１０進数で（ｎ−１）となる。したがって、計数結果が２進数に符号化されている場合には計数出力線１８−１〜１８−ｐの本数ｐは、次の式５を満たす自然数となる。
ｐ＝Ｒｏｕｎｄｕｐ（Ｌｏｇ２（ｎ））    ……式５
【０１０３】
例えば、中間データ１５のビット幅ｎが１０進数で１２８の場合には２次検索データ１９のビット幅ｐは１０進数で７となる。したがって、式１に基づく場合よりも、２次検索用連想メモリ３のビット幅を縮小することができ、連想メモリ１全体の面積および消費電力をさらに削減することが可能である。
【０１０４】
もちろん、計数手段１７が計数結果を２次検索データ１９に符号化する方法は、２進数への符号化に限定されず任意である。その場合の２次検索データ１９のビット幅ｐは、式１，式５によらずに、符号化方法によって決定される。
【０１０５】
また、本実施例では、１つのマスク情報を１つの記憶データに対応させるよう構成しているが、１つのマスク情報を複数の記憶データに対応させるよう構成しても良いことはいうまでもない。
【０１０６】
さらに、本実施例では、ネットワーク・アドレスの最下位階層に対応する中間データ１５のビット位置を中間データ線１４−ｎ、最上位階層に対応する中間データ１５のビット位置を中間データ線１４−１としたため、計数手段１７は中間データ線１４−ｎから上位ビット方向に連続する中間データの無効状態のビット数を計数したが、ネットワーク・アドレスの最下位階層、最上位階層は、それぞれ中間データ１５の任意のビット位置に対応しても良いことはいうまでもない。
【０１０７】
（第二の実施例の構成）
次に、本発明の第二の実施の形態について図面を参照して詳細に説明する。図３は本発明の第二の実施の形態のｎビットｍ語構成（ｍ、ｎは自然数）の連想メモリ２３の一構成例を示すブロック図である。本実施例のｎビットｍ語構成の連想メモリ２３の構成要素を、第一の実施の形態のｎビットｍ語構成の連想メモリ１と比較すると、連想メモリ２が連想メモリ２４に変更されていること、連想メモリ２４の構成要素である計数手段１７が計数手段２５に変更されていること、およびそれに伴い計数手段２５の出力線の名称が計数出力線２６−１〜２６−ｐ（ｐは自然数）に変更されていることのみが異なり、他の部分は同様に構成される。つまり、本実施例の連想メモリ２３の構成要素の中で第一の実施の形態の連想メモリ１から変更されているものは、計数手段２５のみである。従って、第一の実施例と異なる点についてのみ説明を行う。
【０１０８】
本実施例の計数手段２５は、計数入力線１６−１〜１６−ｎ上のｎビットの中間データ１５を入力とし、ｐ本の計数出力線２６−１〜２６−ｐ上にｐビットの２次検索データ１９を出力する。第一の実施の形態の計数手段１７は、ネットワーク・アドレスの最下位階層に対応する中間データ１５のビット位置から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数するが、本実施例の計数手段２５は、計数入力線１６−１〜１６−ｎの中で中間データの無効状態が入力されている本数を単純に計数する。このとき、計数結果の最小値は１０進数で０、最大値は１０進数でｎとなる。したがって、計数結果が２進数に符号化されている場合には計数出力線２６−１〜２６−ｐの本数ｐは、前述の式１を満たす自然数となる。ｐビットの２次検索データ１９は、ｐ本の２次ビット線２０−１〜２０−ｐに入力される。
【０１０９】
ｐビットｍ語構成の２次検索用連想メモリ３は、ｍ本のｐビット幅の２次連想メモリ・ワード９−１〜９−ｍを有する。ｍ本の２次連想メモリ・ワード９−１〜９−ｍは、ｍ本の１次連想メモリ・ワード７−１〜７−ｍと１対１に対応する。対応の仕方は任意であるが、本実施例ではｊ番目（ｊは１以上ｍ以下の自然数）の２次連想メモリ・ワード９−ｊは、ｊ番目の１次連想メモリ・ワード７−ｊに対応するものとする。ｊ番目の２次連想メモリ・ワード９−ｊを構成するｐ個のデータ・セル８−ｊ−１〜８−ｊ−ｐには、計数手段２５がｎビットの計数入力線１６−１〜１６−ｎに対して実行する演算と同一の演算を対応する１次連想メモリ・ワード７−ｊが格納しているｎビットの記憶データに対して実行した結果として得られるｐビットの演算結果を、ｐビットの２次記憶データとして格納する。つまり、ｊ番目の２次連想メモリ・ワード９−ｊを構成するｐ個のデータ・セル８−ｊ−１〜８−ｊ−ｐには、対応する１次連想メモリ・ワード７−ｊが格納しているｎビットの記憶データの中で、記憶データの無効状態であるビットの総数を、２次記憶データとして格納する。
【０１１０】
（第二の実施例の動作）
次に、上述の本発明の第二の実施の形態の連想メモリ２３を、図１１のネットワーク装置４００−１における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図４を用いて説明する。したがって図２の第一の実施の形態の連想メモリ１の動作説明と同様に、図４では連想メモリ２３を９ビット５語構成とする。検索データ１０のビット幅ｎが９であるから、連想メモリ２４の中の１次検索用連想メモリ４は９ビット５語構成となる。また、検索データ１０のビット幅ｎが９であるから、式１より２次検索データ１９のビット幅ｐは４となり、２次検索用連想メモリ３の構成は４ビット５語構成となる。
【０１１１】
なお、本説明では図２の第一の実施の形態の連想メモリ１の動作説明と同様に、マスク情報のマスク有効状態を“０”、マスク無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。記憶データと同様に、中間データ線１４−１〜１４−９の有効状態を“１”、無効状態を“０”とする。１次一致線１３−１〜１３−５、２次一致線２１−１〜２１−５、および一致線１１−１〜１１−５の有効状態を“１”、無効状態を“０”とする。
【０１１２】
図２の第一の実施の形態の連想メモリ１の動作説明と同様に、各９ビットの１次連想メモリ・ワード７−１〜７−５に格納されている記憶データ、マスク情報には、図１１のネットワーク装置４００−１の接続情報を記憶しているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態“０”、マスク情報の該当ビットをマスク有効状態“０”とすることで表現される。
【０１１３】
また、各４ビットの２次連想メモリ・ワード９−１〜９−５には、計数手段２５が９ビットの計数入力線１６−１〜１６−９に対して実行する演算と同様に、対応する１次連想メモリ・ワード７−１〜７−５が格納している９ビットの記憶データの中で記憶データの無効状態“０”であるビットの数を計数した結果を、それぞれ２次記憶データとして格納する。
【０１１４】
したがって、２次連想メモリ・ワード９−１は、１次連想メモリ・ワード７−１が格納している記憶データ“０１０．０００．０００”における記憶データの無効状態“０”のビットの総数である、１０進数表現で８、２進数表現で“１０００”を２次記憶データとして格納している。２次連想メモリ・ワード９−２は、１次連想メモリ・ワード７−２が格納している記憶データ“０１１．０００．０００”における記憶データの無効状態“０”のビットの総数である、１０進数表現で７、２進数表現で“０１１１”を２次記憶データとして格納している。２次連想メモリ・ワード９−３は、１次連想メモリ・ワード７−３が格納している記憶データ“００１．０１０．０００”における記憶データの無効状態“０”のビットの総数である、１０進数表現で７、２進数表現で“０１１１”を２次記憶データとして格納している。２次連想メモリ・ワード９−４は、１次連想メモリ・ワード７−４が格納している記憶データ“００１．０１１．０００”における記憶データの無効状態“０”のビットの総数である、１０進数表現で６、２進数表現で“０１１０”を２次記憶データとして格納している。２次連想メモリ・ワード９−５は、１次連想メモリ・ワード７−５が格納している記憶データ“０１０．１１０．０００”における記憶データの無効状態“０”のビットの総数である、１０進数表現で６、２進数表現で“０１１０”を２次記憶データとして格納している。
【０１１５】
１次検索動作の前には、すべての１次一致線１３−１〜１３−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。また、２次検索動作の前には、すべての２次一致線２１−１〜２１−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【０１１６】
以降、検索データ１０として図１１のユーザ機器４０１−３の８進数表現のネットワーク・アドレス（２．６．５）を入力し検索動作を行った場合の動作を、図２の第一の実施の形態の連想メモリ１の動作と異なる点についてのみ説明する。
【０１１７】
検索データ１０の９ビットの２進数表現の値“０１０．１１０．１０１”は、９本の１次ビット線１２−１〜１２−９に入力され、連想メモリ２４の中の１次検索用連想メモリ４は１次検索を実行する。１次検索の結果として、図２の第一の実施の形態の連想メモリ１の動作と同様に、１次一致線１３−１、１３−５の２本が有効状態“１”となり、残りの１次一致線１３−２、１３−３、および１３−４は無効状態“０”となる。また、中間データ線１４−１〜１４−９上の９ビットの中間データ１５として、２進数表現で“０１０１１００００”が得られ、計数入力線１６−１〜１６−９に入力される。
【０１１８】
計数手段２５は、９ビットの計数入力線１６−１〜１６―９の中で中間データの無効状態“０”が入力されている本数を計数する。結果として得られた１０進数表現で６、２進数表現で“０１１０”を、４ビットの２次検索データ１９として計数出力線２６−１〜２６−４に出力する。
【０１１９】
２次検索データ１９の値は、２次ビット線２０−１〜２０−４に入力され、２次検索用連想メモリ３は２次検索を実行する。結果として、２次連想メモリ・ワード９−４、および９−５に格納されている２進数表現の“０１１０”が、２次ビット線２０−１〜２０−４の状態と完全に一致する。したがって、２次一致線２１−４、および２１−５が有効状態“１”となり、残りの２次一致線２１−１、２１−２、および２１−３は無効状態“０”となる。
【０１２０】
２次検索終了後、１次一致線１３−１は有効状態“１”であるので無効化手段２２−１は２次一致線２１−１の状態“０”を一致線１１−１に出力する。１次一致線１３−２は無効状態“０”であるので無効化手段２２−２は無効状態“０”を一致線１１−２に出力する。１次一致線１３−３は無効状態“０”であるので無効化手段２２−３は無効状態“０”を一致線１１−３に出力する。１次一致線１３−４は無効状態“０”であるので無効化手段２２−４は無効状態“０”を一致線１１−４に出力する。１次一致線１３−５は有効状態“１”であるので無効化手段２２−５は２次一致線２１−５の状態“１”を一致線１１−５に出力する。したがって、２次検索終了後、一致線１１−５のみが有効状態“１”となり、残りの一致線１１−１、１１−２、１１−３、および１１−４は無効状態“０”となる。
【０１２１】
したがって、本発明の第二の実施の形態の連想メモリ２３は、前述の従来の連想メモリ１００と同様に、入力した検索データ１０と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線１１−５のみに、正しく有効状態を出力できることがわかる。
【０１２２】
本発明の第二の実施の形態の連想メモリ２３における、面積、消費電力の削減効果は第一の実施の形態の連想メモリ１と同様である。本実施例の計数手段２５は、計数入力線１６−１〜１６−ｎの中で中間データの無効状態が入力されている本数を単純に計数するため、計数入力線１６−１〜１６−ｎから正規化された物理量、例えば電荷量、電流、光量などが計数手段２５に入力される場合には容易に計数する事が可能である。
【０１２３】
計数入力線１６−１〜１６−ｎの本数ｎが一定であることから、計数手段２５は、計数入力線１６−１〜１６−ｎの中で中間データの有効状態が入力されている本数を計数し、２次連想メモリ・ワード９には対応する１次連想メモリ・ワード７が格納しているｎビットの記憶データの中で記憶データの有効状態であるビットの総数を２次記憶データとして格納してもよいことは言うまでもない。
【０１２４】
また、第一の実施の形態の連想メモリ１の説明と同様に、図３のｎビットの中間データ１５のすべてのビットが同時に無効状態とならない場合、すなわち、マスク情報の全ビットがマスク有効状態であるような構造化データを１次検索用連想メモリ４に格納していない場合には、計数出力線２６−１〜２６−ｐの本数ｐは前述の式５により得られることも明らかであり、連想メモリ２３全体の面積および消費電力をさらに削減することが可能である。
【０１２５】
もちろん、計数手段２５が計数結果を２次検索データ１９に符号化する方法は、２進数への符号化に限定されず任意である。その場合の２次検索データ１９のビット幅ｐは、式１，式５によらずに、符号化方法によって決定される。
【０１２６】
（第三の実施例の構成）
次に、本発明の第三の実施の形態について図面を参照して詳細に説明する。図５は本発明の第三の実施の形態の連想メモリ２７の一構成例を示すブロック図である。ｎビットｍ語構成（ｍ、ｎは自然数）の連想メモリ２７は、ｎビットｍ語構成の連想メモリ２８と、ｐビットｍ語構成（ｐは自然数）の２次検索用連想メモリ４８と、ｍ個の無効化手段２２−１〜２２−ｍとを有し、ｎビットの検索データ１０を入力するための１次ビット線１２−１〜１２−ｎと、最終検索結果を出力するｍ本の一致線１１−１〜１１−ｍを有する。
ｎビットｍ語構成の連想メモリ２８は、ｎビットｍ語構成の１次検索用連想メモリ２９と、計数手段３２とを有し、１次ビット線１２−１〜１２−ｎを入力とし、１次一致線１３−１〜１３−ｍおよび計数出力線５０−１〜５０−ｐを出力とする。
【０１２７】
図１に示した第一の実施の形態の連想メモリ１は、対応するマスク情報を考慮して検索データと比較した結果一致する記憶データを検索する１次検索の結果一致した記憶データ同士に対して記憶データの有効状態を真とした論理和演算により中間データ１５を生成する１次検索用連想メモリ４により構成した場合の実施例であるが、図５に示す第三の実施の形態の連想メモリ２７は、対応するマスク情報を考慮して検索データと比較した結果一致する記憶データを検索する１次検索の結果一致した記憶データに対応するマスク情報同士に対してマスク情報の有効状態を真とした論理積演算により中間データ１５を生成する１次検索用連想メモリ２９により構成した場合の実施例である。
【０１２８】
１次検索用連想メモリ２９は、各ｎビットの記憶データおよびマスク情報から構成される構造化データを格納できる１次連想メモリ・ワード３０−１〜３０−ｍを有し、１次ビット線１２−１〜１２−ｎを入力とし、１次一致線１３−１〜１３−ｍおよび中間データ線３１−１〜３１−ｎを出力とする。１次連想メモリ・ワード３０−ｊ（ｊは１以上ｍ以下の自然数）は、ｎビットの記憶データを格納するためのデータ・セル５−ｊ−１〜５−ｊ−ｎと、対応するｎビットのマスク情報を格納するためのマスク・セル６−ｊ−１〜６−ｊ−ｎを有する。ここで、構造化データのドント・ケア“＊”状態のビットは、対応するマスク・セル６にマスク情報の有効状態を格納することにより表現するものとする。
【０１２９】
１次検索用連想メモリ２９は、対応するマスク情報を考慮して１次ビット線１２−１〜１２−ｎの状態と比較した結果一致する記憶データを検索する１次検索を行い、一致した記憶データを格納している１次連想メモリ・ワード３０に対応する１次一致線１３に有効状態を出力し、他の１次一致線１３には無効状態を出力する。また、一致した記憶データに対応するマスク情報同士に対してマスク情報の有効状態を真とした論理積演算を行い、得られた値を中間データ線３１−１〜３１−ｎにｎビットの中間データ１５として出力する。ｎビットの中間データ１５の状態は、ｎ本の計数入力線１６−１〜１６−ｎに入力される。
【０１３０】
計数手段３２は、ｎ本の計数入力線１６−１〜１６−ｎを入力とし、ｐ本の計数出力線５０−１〜５０−ｐを出力とする。計数手段３２は、ネットワーク・アドレスの最下位階層に対応する中間データ１５のビット位置から上位階層側に連続している中間データの有効状態のビット数を、最初の中間データの無効状態のビットが現れるまで計数し、計数結果を計数出力線５０−１〜５０−ｐに、ｐビットの２次検索データ１９として出力する。ｐビットの２次検索データ１９は、ｐ本の２次ビット線２０−１〜２０−ｐに入力される。
【０１３１】
このとき、計数結果の最小値は１０進数で０、最大値は１０進数でｎとなる。したがって、計数結果が２進数に符号化されている場合には計数出力線５０−１〜５０−ｐの本数ｐは、前述の式１を満たす自然数となる。
【０１３２】
ｐビットｍ語構成の２次検索用連想メモリ４８は、２次ビット線２０−１〜２０−ｐを入力とし、２次一致線２１−１〜２１−ｍを出力とする。２次検索用連想メモリ４８は、ｐビットの２次記憶データを格納できる２次連想メモリ・ワード４９−１〜４９−ｍを有する。ｊ番目の２次連想メモリ・ワード４９−ｊは、ｐビットの２次記憶データを格納するためのデータ・セル８−ｊ−１〜８−ｊ−ｐを有する。２次検索用連想メモリ４８は、２次ビット線２０−１〜２０−ｐの状態と一致する２次記憶データを検索する２次検索を行い、一致した２次記憶データを格納している２次連想メモリ・ワード４９に対応する２次一致線２１に有効状態を出力し、他の２次一致線２１には無効状態を出力する。図から明らかなように、第三の実施の形態のｐビットｍ語構成の２次検索用連想メモリ４８は、図１を用いて説明した第一の実施の形態のｐビットｍ語構成の２次検索用連想メモリ３と全く同様に構成することができる。
【０１３３】
ｍ本の２次連想メモリ・ワード４９−１〜４９−ｍは、ｍ本の１次連想メモリ・ワード３０−１〜３０−ｍと１対１に対応する。対応の仕方は任意であるが、本実施例ではｊ番目の２次連想メモリ・ワード４９−ｊは、ｊ番目の１次連想メモリ・ワード３０−ｊに対応するものとする。ｊ番目の２次連想メモリ・ワード４９−ｊのデータ・セル８−ｊ−１〜８−ｊ−ｐには、計数手段３２がｎビットの計数入力線１６−１〜１６−ｎに対して実行する演算と同一の演算を対応する１次連想メモリ・ワード３０−ｊが格納しているｎビットのマスク情報に対して実行した結果として得られるｐビットの演算結果を、ｐビットの２次記憶データとして格納する点のみが、第一の実施の形態の連想メモリ１の２次検索用連想メモリ３と異なる。
【０１３４】
ｊ番目の無効化手段２２−ｊは、２次連想メモリ・ワード４９−ｊが出力する２次一致線２１−ｊと、２次連想メモリ・ワード４９−ｊに対応する１次連想メモリ・ワード３０−ｊが出力する１次一致線１３−ｊとを入力とする。無効化手段２２−ｊは、１次一致線１３−ｊが１次一致線の無効状態である場合には一致線１１−ｊに一致線の無効状態を出力し、１次一致線１３−ｊが１次一致線の有効状態である場合には一致線１１−ｊに２次一致線２１−ｊの状態を出力する。図５では、無効化手段２２−ｊを、１次一致線の有効状態、２次一致線の有効状態を真とする論理積演算回路により構成した場合を示しているが、ワイアード論理回路などによっても構成可能なことは言うまでもない。
【０１３５】
図６は、ｎビットｍ語構成の第三の実施の形態の連想メモリ２７におけるｎビットｍ語構成の１次検索用連想メモリ２９の一構成例を示すブロック図である。ｎビットｍ語構成の１次検索用連想メモリ２９は、ｎビットの１次連想メモリ・ワード３０−１〜３０−ｍと、抵抗３８−１〜３８−ｎとを有している。ｊ番目の１次連想メモリ・ワード３０−ｊは、ｎ個の連想メモリ・セル３３−ｊ−１〜３３−ｊ−ｎを有している。ｊ番目の１次連想メモリ・ワード３０−ｊには、対応するデータ・ワード線３６−ｊと、マスク・ワード線３７−ｊが入力のために接続され、対応する１次一致線１３−ｊ、および中間データ線３１−１〜３１−ｎが出力のために接続され、ｎ本の１次ビット線１２−１〜１２−ｎが入出力のために接続されている。
【０１３６】
ｊ番目の１次連想メモリ・ワード３０−ｊのｋビット目（ｋは１以上ｎ以下の自然数）の連想メモリ・セル３３−ｊ−ｋには、対応するデータ・ワード線３６−ｊと、マスク・ワード線３７−ｊが入力のために接続され、対応する１次一致線１３−ｊ、および中間データ線３１−ｋが出力のために接続され、１次ビット線１２−ｋが入出力のために接続されている。
【０１３７】
連想メモリ・セル３３−ｊ−ｋは、１次ビット線１２−ｋを介して外部から入力される記憶データの対応するビット情報を格納するデータ・セル５−ｊ−ｋと、データ・セル５−ｊ−ｋに記憶されたビット情報と外部から１次ビット線１２−ｋを介して入力される情報とを比較する比較器３４−ｊ−ｋと、外部から１次ビット線１２−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル６−ｊ−ｋと、および論理ゲート３５−ｊ−ｋとを備えている。
【０１３８】
なお、本実施例では、マスク情報のマスク有効状態を“０”、マスク無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。マスク情報と同様に、中間データ線３１−１〜３１−ｎの有効状態を“０”、無効状態を“１”とする。１次一致線１３−１〜１３−ｍ、２次一致線２１−１〜２１−ｍ、および一致線１１−１〜１１−ｍの有効状態を“１”、無効状態を“０”とする。
【０１３９】
データ・セル５−ｊ−ｋは、対応するデータ・ワード線３６―ｊが有効状態の場合、対応する１次ビット線１２―ｋに書き込みデータがドライブされていれば記憶データとして格納し、対応する１次ビット線１２―ｋがドライブされていなければ格納している記憶データを対応する１次ビット線１２―ｋに出力する。対応するデータ・ワード線３６−ｊが無効状態ならば、１次ビット線１２−ｋに対してなんら操作は行わない。また、対応するデータ・ワード線３６−ｊの値にかかわらず、格納している記憶データを同一の連想メモリ・セル３３−ｊ−ｋの中の比較器３４−ｊ−ｋに出力する。
【０１４０】
マスク・セル６−ｊ−ｋは、対応するマスク・ワード線３７−ｊが有効状態の場合、対応する１次ビット線１２−ｋに書き込みデータがドライブされていれば書き込みデータをマスク情報として格納し、対応する１次ビット線１２−ｋがドライブされていなければ、格納しているマスク情報を対応する１次ビット線１２−ｋに出力する。対応するマスク・ワード線３７−ｊが無効状態ならば、１次ビット線１２―ｋに対してなんら操作は行わない。また、対応するマスク・ワード線３７−ｊの値にかかわらず、格納しているマスク情報を同一の連想メモリ・セル３３−ｊ−ｋの中の比較器３４−ｊ−ｋおよび論理ゲート３５−ｊ−ｋに出力する。
【０１４１】
１次一致線１３−１〜１３−ｍは、１次検索動作の開始前には、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【０１４２】
比較器３４−ｊ−ｋは、対応する１次ビット線１２−ｋと、それに同一の連想メモリ・セル３３−ｊ−ｋの中のデータ・セル５−ｊ−ｋに格納されている記憶データと、マスク・セル６−ｊ−ｋに格納されているマスク情報を入力とする。比較器３４−ｊ−ｋは、マスク情報がマスク有効状態“０”ならば、対応する１次一致線１３−ｊを開放状態にし、それ以外の場合には、１次ビット線１２−ｋの値と記憶データが一致するならば対応する１次一致線１３−ｊを開放状態にし、一致しないならば無効状態“０”を出力する。ｊ番目の１次連想メモリ・ワード３０−ｊの中のｎ個の比較器３４−ｊ−１〜３４−ｊ−ｎがすべて１次一致線１３−ｊを開放状態にしているときに、１次一致線１３−ｊは有効状態“１”となり、それ以外の場合には無効状態“０”となる、１次一致線１３の有効状態“１”を真としたワイアードＡＮＤ論理接続を構成している。つまり１次検索動作時には、マスク情報がマスク有効状態“０”のために比較対象から除外されたビットを除いて、１次連想メモリ・ワード３０−ｊが格納している記憶データと１次ビット線１２−１〜１２−ｎが完全に一致する場合に限り、１次一致線１３−ｊは有効状態“１”となり、それ以外の場合は無効状態“０”となる。
【０１４３】
論理ゲート３５−ｊ−ｋは、同一の１次連想メモリ・ワード３０−ｊの中の１次一致線１３−ｊが有効状態“１”かつ、同一の連想メモリ・セル３３−ｊ−ｋの中のマスク・セル６−ｊ−ｋに格納されたマスク情報が無効状態“１”のときに、対応する中間データ線３１−ｋに中間データ線３１の無効状態“１”を出力し、それ以外の場合には開放状態にする。中間データ線３１−ｋは、抵抗３８−ｋを介して中間データ線３１の有効状態“０”に接続されており、対応するｍ個の論理ゲート３５−１−ｋ〜３５−ｍ−ｋと、中間データ線３１の有効状態“０”を真としたワイアードＡＮＤ論理接続を構成している。つまり、中間データ線３１−ｋには、ｍ個の論理ゲート３５−１−ｋ〜３５−ｍ−ｋと、抵抗３８−ｋにより、１次検索実行後に有効状態“１”となっている１次一致線１３−１〜１３−ｍを有するすべてのｋビット目の連想メモリ・セル３３−１−ｋ〜３３−ｍ−ｋの中のマスク・セル６−１−ｋ〜６−ｍ−ｋに格納されているマスク情報同士を、マスク情報の有効状態“０”を真とした論理積演算した結果が得られることになる。これらの動作により、中間データ線３１−１〜３１−ｎには、１次検索実行後に検索データ１０と一致した記憶データに対応するマスク情報の中で、最もマスク情報の有効状態“０”のビット数が少ないマスク情報と同じ値が出力されることになる。
【０１４４】
（第三の実施例の動作）
次に、上述の本発明の第三の実施の形態の連想メモリ２７を、図１１のネットワーク装置４００−１における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図７を用いて説明する。したがって図２の第一の実施の形態の連想メモリ１の動作説明と同様に、図７では連想メモリ２７を９ビット５語構成とする。検索データ１０のビット幅ｎが９であるから、連想メモリ２８の中の１次検索用連想メモリ２９は９ビット５語構成となる。また、検索データ１０のビット幅ｎが９であるから、式１より２次検索データ１９のビット幅ｐは４となり、２次検索用連想メモリ４８の構成は４ビット５語構成となる。
【０１４５】
本説明では、マスク情報のマスク有効状態を“０”、マスク無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。マスク情報と同様に、中間データ線３１−１〜３１−９の有効状態を“０”、無効状態を“１”とする。１次一致線１３−１〜１３−５、２次一致線２１−１〜２１−５、および一致線１１−１〜１１−５の有効状態を“１”、無効状態を“０”とする。
【０１４６】
図２の第一の実施の形態の連想メモリ１の動作説明と同様に、各９ビットの１次連想メモリ・ワード３０−１〜３０−５に格納されている記憶データ、マスク情報には、図１１のネットワーク装置４００−１の接続情報を記憶しているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、マスク情報の該当ビットをマスク有効状態“０”とすることで表現される。接続情報の中のドント・ケア“＊”状態のビットに対応する記憶データのビットの状態は任意であるが、説明のため、記憶データの無効状態“０”を格納するものとする。これにより、図７の１次連想メモリ・ワード３０−１〜３０−５が格納している記憶データ、マスク情報は、図２の１次連想メモリ・ワード７−１〜７−５が格納している記憶データ、マスク情報と同一のものになる。
【０１４７】
また、各４ビットの２次連想メモリ・ワード４９−１〜４９−５には、計数手段３２が９ビットの計数入力線１６−１〜１６−９に対して実行する演算と同様に、対応する１次連想メモリ・ワード３０−１〜３０−５が格納している９ビットのマスク情報の中で、ネットワーク・アドレスの最下位階層に対応するビット位置から上位階層側に連続しているマスク情報の有効状態“０”のビット数を最初のマスク情報の無効状態“１”のビットが現れるまで計数した結果を、それぞれ２次記憶データとして格納する。
【０１４８】
したがって、１次連想メモリ・ワード３０−１がマスク情報“１１１．０００．０００”を格納しているので、２次連想メモリ・ワード４９−１には１０進数表現で６、２進数表現で“０１１０”を２次記憶データとして格納する。１次連想メモリ・ワード３０−２がマスク情報“１１１．０００．０００”を格納しているので、２次連想メモリ・ワード４９−２には１０進数表現で６、２進数表現で“０１１０”を２次記憶データとして格納する。１次連想メモリ・ワード３０−３がマスク情報“１１１．１１１．０００”を格納しているので、２次連想メモリ・ワード４９−３には１０進数表現で３、２進数表現で“００１１”を２次記憶データとして格納する。１次連想メモリ・ワード３０−４がマスク情報“１１１．１１１．０００”を格納しているので、２次連想メモリ・ワード４９−４には１０進数表現で３、２進数表現で“００１１”を２次記憶データとして格納する。１次連想メモリ・ワード３０−５がマスク情報“１１１．１１１．０００”を格納しているので、２次連想メモリ・ワード４９−５には１０進数表現で３、２進数表現で“００１１”を２次記憶データとして格納する。
【０１４９】
１次検索動作の前には、すべての１次一致線１３−１〜１３−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。また、２次検索動作の前には、すべての２次一致線２１−１〜２１−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【０１５０】
以降、検索データ１０として図１１のユーザ機器４０１−３の８進数表現のネットワーク・アドレス（２．６．５）を入力し検索動作を行った場合の動作を説明する。
【０１５１】
検索データ１０の９ビットの２進数表現の値“０１０．１１０．１０１”は、９本の１次ビット線１２−１〜１２−９に入力され、連想メモリ２８の中の１次検索用連想メモリ２９は１次検索を実行する。結果として、１次連想メモリ・ワード３０−１に格納されている８進数表現の（２．＊．＊）と、１次連想メモリ・ワード３０−５に格納されている８進数表現の（２．６．＊）が１次ビット線１２−１〜１２−９の状態と一致する。従って、１次検索の結果として、１次一致線１３−１、１３−５の２本が有効状態“１”となり、残りの１次一致線１３−２、１３−３、および１３−４は無効状態“０”となる。
【０１５２】
このとき、中間データ線３１−１からは、１次連想メモリ・ワード３０−１内の対応するマスク情報“１”と１次連想メモリ・ワード３０−５内の対応するマスク情報“１”とに対しての、“０”を真とした論理積結果“１”が出力される。中間データ線３１−２からは、１次連想メモリ・ワード３０−１内の対応するマスク情報“１”と１次連想メモリ・ワード３０−５内の対応するマスク情報“１”とに対しての、“０”を真とした論理積結果“１”が出力される。以降同様に、中間データ線３１−３からは“１”と“１”とに対しての“０”を真とした論理積結果“１”が、中間データ線３１−４からは“０”と“１”とに対しての“０”を真とした論理積結果“１”が、中間データ線３１−５からは“０”と“１”とに対しての“０”を真とした論理積結果“１”が、中間データ線３１−６からは“０”と“１”とに対しての“０”を真とした論理積結果“１”が、中間データ線３１−７からは“０”と“０”とに対しての“０”を真とした論理積結果“０”が、中間データ線３１−８からは“０”と“０”とに対しての“０”を真とした論理積結果“０”が、中間データ線３１−９からは“０”と“０”とに対しての“０”を真とした論理積結果“０”が、それぞれ出力される。従って、９ビットの中間データ１５として、２進数表現で“１１１１１１０００”が得られ、計数入力線１６−１〜１６−９に入力される。
【０１５３】
計数手段３２は、９本の計数入力線１６−１〜１６―９の状態の中で、ネットワーク・アドレスの最下位階層に対応するビット位置１６−９から上位階層側に連続しているマスク情報の有効状態“０”のビット数を最初のマスク情報の無効状態“１”のビットが現れるまで計数し、結果として得られる、１０進数表現で３、２進数表現で“００１１”を、計数出力線５０−１〜５０−４に出力する。計数出力線５０−１〜５０−４の状態は４ビットの２次検索データ１９として２次ビット線２０−１〜２０−４に入力される。
【０１５４】
２次ビット線２０−１〜２０−４に２次検索データ１９が入力されると、２次検索用連想メモリ４８は２次検索を実行する。結果として、２次連想メモリ・ワード４９−３、４９−４および４９−５に格納されている２進数表現の“００１１”が、２次ビット線２０−１〜２０−４の状態と完全に一致する。したがって、２次一致線２１−３、２１−４および２１−５が有効状態“１”となり、残りの２次一致線２１−１、および２１−２は無効状態“０”となる。
【０１５５】
２次検索終了後、１次一致線１３−１は有効状態“１”であるので無効化手段２２−１は２次一致線２１−１の状態“０”を一致線１１−１に出力する。１次一致線１３−２は無効状態“０”であるので無効化手段２２−２は無効状態“０”を一致線１１−２に出力する。１次一致線１３−３は無効状態“０”であるので無効化手段２２−３は無効状態“０”を一致線１１−３に出力する。１次一致線１３−４は無効状態“０”であるので無効化手段２２−４は無効状態“０”を一致線１１−４に出力する。１次一致線１３−５は有効状態“１”であるので無効化手段２２−５は２次一致線２１−５の状態“１”を一致線１１−５に出力する。したがって、２次検索終了後、一致線１１−５のみが有効状態“１”となり、残りの一致線１１−１、１１−２、１１−３、および１１−４は無効状態“０”となる。したがって、本発明の第三の実施の形態の連想メモリ２７は、前述の従来の連想メモリ１００と同様に、入力した検索データ１０と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線１１−５のみに、正しく有効状態を出力できることがわかる。
【０１５６】
本発明の第三の実施の形態の連想メモリ２７における、面積、消費電力の削減効果は第一の実施の形態の連想メモリ１と同様である。
【０１５７】
本実施例の計数手段３２は、第二の実施の形態の連想メモリ２３の計数手段２５と同様に、計数入力線１６−１〜１６−ｎの中で中間データの有効状態が入力されている本数を単純に計数してもよいことはいうまでもない。また、同様に、計数入力線１６−１〜１６−ｎの本数ｎが一定であることから、計数手段３２は、計数入力線１６−１〜１６−ｎの中で中間データの無効状態が入力されている本数を計数してもよいことも言うまでもない。また、計数手段３２は、中間データ１５のネットワーク・アドレスの最上位階層に対応するビット位置から下位階層側に連続しているマスク情報の無効状態のビット数を最初のマスク情報の有効状態のビットが現れるまで計数してもよいことも言うまでもない。もちろん、計数手段３２の演算方法によらずに、２次連想メモリ・ワード４９には、対応する１次連想メモリ・ワード３０が格納しているｎビットのマスク情報に対して計数手段２５が実行する演算と同じ演算を実行した値を２次記憶データとして格納する。
【０１５８】
また、第一の実施の形態の連想メモリ１の説明と同様に、図５のｎビットの中間データ１５のすべてのビットが同時に有効状態とならない場合、すなわち、マスク情報の全ビットがマスク有効状態であるような構造化データを１次検索用連想メモリ２９に格納していない場合には、計数出力線５０−１〜５０−ｐの本数ｐは前述の式５により得られることも明らかであり、連想メモリ２７全体の面積および消費電力をさらに削減することが可能である。
【０１５９】
もちろん、計数手段３２が計数結果を２次検索データ１９に符号化する方法は、２進数への符号化に限定されず任意である。その場合の２次検索データ１９のビット幅ｐは、式１，式５によらずに、符号化方法によって決定される。
【０１６０】
また、図７と図２を比較すれば明らかなように、本実施例の１次検索用連想メモリ２９が出力する、１次検索の結果一致した記憶データに対応するマスク情報同士に対してマスク有効状態を真とする論理積結果である中間データ線３１−１〜３１−ｎと、記憶データの有効状態を真とする検索データ１０とを論理積演算することにより、第一の実施例の１次検索用連想メモリ４が出力する中間データ線１４−１〜１４−ｎと同一の値を得ることができる。したがって、第一の実施例の１次検索用連想メモリ４を前記の構成で代替できることはいうまでもない。
【０１６１】
（第四の実施例の構成）
次に、本発明の第四の実施の形態について図面を参照して詳細に説明する。図８は本発明の第四の実施の形態のｎビットｍ語構成（ｍ、ｎは自然数）の連想メモリ４１の一構成例を示すブロック図である。本実施例のｎビットｍ語構成の連想メモリ４１の構成要素を、第一の実施の形態のｎビットｍ語構成の連想メモリ１と比較すると、外部からの入力信号としてクロック信号３９が追加されていること、２次検索データ１９が２次検索データ記憶手段４２に記憶されるように変更されていること、１次一致線１３−１〜１３−ｍにｍビットの記憶手段４３が挿入されていること、およびｊ番目（ｊは１以上ｍ以下の自然数）の無効化手段２２−ｊの一方の入力信号が１次一致線１３−ｊから、記憶手段４３が出力する同期化１次一致線４４−ｊに変更されていることのみが異なり、他の部分は同様に構成される。従って、第一の実施例と異なる点についてのみ説明を行う。
【０１６２】
本実施例では、ｎビットｍ語構成の連想メモリ２が出力するｐ本（ｐは１以上ｎ以下の自然数）の計数出力線１８−１〜１８−ｐは、クロック信号３９に同期して２次検索データ記憶手段４２に格納される。２次検索データ記憶手段４２は、格納しているｐビットの状態を対応するｐ本の２次ビット線２０−１〜２０−ｐに出力する。
【０１６３】
ｍビットの記憶手段４３は、１次一致線１３−１〜１３−ｍを入力とし、同期化１次一致線４４−１〜４４−ｍを出力とする。同期化１次一致線４４−１〜４４−ｍは、それぞれ対応する無効化手段２２−１〜２２−ｍに入力される。ｍビットの記憶手段４３は、１次検索用連想メモリ４が検索データ１０に対して１次検索を行った結果出力する１次一致線１３−１〜１３−ｍをクロック信号に同期して格納する。該検索データ１０に対応する２次検索を２次検索用連想メモリ３が実行した結果が２次一致線２１−１〜２１−ｍに出力されるタイミングと同期するように、記憶手段４３は格納した前記１次一致線１３−１〜１３−ｍの状態を同期化１次一致線４４−１〜４４−ｍに出力する。
【０１６４】
ｍ本の２次連想メモリ・ワード９−１〜９−ｍは、ｍ本の１次連想メモリ・ワード７−１〜７−ｍと１対１に対応する。対応の仕方は任意であるが、本実施例ではｊ番目の２次連想メモリ・ワード９−ｊは、ｊ番目の１次連想メモリ・ワード７−ｊに対応するものとする。
【０１６５】
ｊ番目の無効化手段２２−ｊは、２次連想メモリ・ワード９−ｊが出力する２次一致線２１−ｊと、２次連想メモリ・ワード９−ｊに対応する１次連想メモリ・ワード７−ｊが出力する１次一致線１３−ｊを記憶手段４３により同期化した同期化１次一致線４４−ｊを入力とする。無効化手段２２−ｊは、同期化１次一致線４４−ｊが１次一致線の無効状態である場合には一致線１１−ｊに一致線の無効状態を出力し、同期化１次一致線４４−ｊが１次一致線の有効状態である場合には一致線１１−ｊに２次一致線２１−ｊの状態を出力する。
【０１６６】
第一の実施の形態の連想メモリ１，第二の実施の形態の連想メモリ２３，第三の実施の形態の連想メモリ２７では、同一の検索データ１０に対する１次検索と２次検索が連続して実行されていたが、本実施例では、１次検索用連想メモリ４が出力する１次一致線１３−１〜１３−ｍと、計数出力線１８−１〜１８−ｐを、それぞれ記憶する手段を有することにより、１次検索用連想メモリ４と２次検索用連想メモリ３とでパイプライン処理を構成することができる。これにより、クロック信号３９の周波数を向上させることが可能となる。
【０１６７】
クロック信号３９の周波数をさらに向上させるために、さらに記憶手段を挿入した場合においても、記憶手段４３が同期化１次一致線４４−１〜４４−ｍに検索データ１０に対する１次検索の結果を出力するタイミングを、該検索データに対する２次検索の結果が２次一致線２１−１〜２１−ｍに出力されるタイミングと同期するように出力することにより可能なことは明らかである。例えば、中間データ１５を格納する記憶手段を連想メモリ２に有することにより、１次検索用連想メモリ４による１次検索の実行と、計数手段１７による演算とをパイプライン処理することも可能なことは言うまでもない。
【０１６８】
また、前記の中間データ１５を格納する記憶手段を挿入する構成のように、第一の実施の形態の連想メモリ１，第二の実施の形態の連想メモリ２３，第三の実施の形態の連想メモリ２７においても、検索データ１０に対する１次検索結果が１次一致線１３−１〜１３−ｍに出力されるタイミングと、該検索データ１０に対する２次検索結果が２次一致線２１−１〜２１−ｍに出力されるタイミングが異なる場合には、記憶手段４３を１次一致線１３−１〜１３−ｍに挿入することにより同期化すればよいことは言うまでもない。
【０１６９】
（第五の実施例の構成）
次に、本発明の第五の実施の形態について図面を参照して詳細に説明する。図９は本発明の第五の実施の形態のｎビットｍ語構成（ｍ、ｎは自然数）の連想メモリ４５の一構成例を示すブロック図である。本実施例のｎビットｍ語構成の連想メモリ４５の構成要素を、第四の実施の形態のｎビットｍ語構成の連想メモリ４１と比較すると、ｐビットｍ語構成（ｐは１以上ｎ以下の自然数）の２次検索用連想メモリ３が２次検索用連想メモリ４６に変更されていること、無効化手段２２−１〜２２−ｍが無効化手段４７に変更されていること、無効化手段４７が同期化１次一致線４４−１〜４４−ｍのみを入力とし、２次一致線２１−１〜２１−ｍを出力とするように変更されたこと、２次検索用連想メモリ４６が２次検索結果に応じて状態を変更した後の２次一致線２１−１〜２１−ｍを一致線１１−１〜１１−ｍとして外部に出力するように変更されていることのみが異なり、他の部分は同様に構成される。従って、第四の実施例と異なる点についてのみ説明を行う。
【０１７０】
同期化１次一致線４４−１〜４４−ｍ上の１次検索結果に対応する２次検索データを入力とする無効化手段４７は、同期化１次一致線４４−１〜４４−ｍを入力とし、２次一致線２１−１〜２１−ｍを出力とし、ｍ個のプリ・チャージ制御手段５１−１〜５１−ｍを有する。
【０１７１】
本実施例の無効化手段４７は、検索データ１０に対応する２次検索を２次検索用連想メモリ４６が実行する前に、同期化１次一致線４４−１〜４４−ｍ上に出力されている該検索データ１０に対応する１次検索結果に応じて対応する２次一致線２１−１〜２１−ｍを有効状態にプリ・チャージ、または無効状態にディス・チャージすることを特徴とする。ｊ番目（ｊは１以上ｍ以下の自然数）のプリ・チャージ制御手段５１−ｊは同期化１次一致線４４−ｊを入力とし、同期化１次一致線４４−ｊが１次一致線の有効状態のときには２次一致線２１−ｊを２次一致線の有効状態にプリ・チャージし、同期化１次一致線４４−ｊが１次一致線の無効状態のときには２次一致線２１−ｊを２次一致線の無効状態にディス・チャージする。
【０１７２】
つまり無効化手段４７は、１次検索用連想メモリ４が検索データ１０に対する１次検索を実行した結果一致した１次連想メモリ・ワード７−ｊに対応する２次一致線２１−ｊを２次検索の前に一致線の有効状態にプリ・チャージし、１次検索の結果不一致であった１次連想メモリ・ワード７に対応する２次一致線２１を無効状態にディス・チャージする。１次連想メモリ・ワード７−１〜７−ｍと、２次一致線２１−１〜２１−ｍの対応の仕方は任意であるが、本実施例では１次連想メモリ・ワード７−ｊと２次一致線２１−ｊが対応するものとする。
【０１７３】
第四の実施例の２次検索用連想メモリ３は２次検索を実行する前にすべての２次一致線２１−１〜２１−ｍを２次一致線の有効状態にプリ・チャージしていたが、本発明の２次検索用連想メモリ４６は２次検索を実行する前に２次一致線２１−１〜２１−ｍのプリ・チャージを実行しない点のみが異なり、他の部分は第四の実施の形態の２次検索用連想メモリ３と同様に構成される。第４の実施の形態の２次検索用連想メモリ３と同様に、２次検索用連想メモリ４６が２次検索データ記憶手段４２に格納されている２次検索データに対する２次検索を実行した結果、２次連想メモリ・ワード９−ｊの全てのデータ・セル８−ｊ−１〜８−ｊ−ｐに格納されている２次記憶データが２次検索データと一致した場合、２次連想メモリ・ワード９−ｊは２次一致線２１−ｊを開放状態とし、それ以外の場合には２次一致線２１−ｊに２次一致線の無効状態を出力する。本実施例では、２次一致線２１の有効状態と一致線１１の有効状態が同じ状態とし、２次一致線２１−１〜２１−ｍの状態を一致線１１−１〜１１−ｍとして連想メモリ４５の外部に出力する。
【０１７４】
つまり、一致線１１−ｊは、１次検索用連想メモリ４が検索データ１０に対して１次検索を実行した結果１次連想メモリ・ワード７−ｊが一致し、かつ、２次検索用連想メモリ４６が該検索データ１０に対応する２次検索データに対して２次検索を実行した結果２次連想メモリ・ワード９−ｊが一致した場合のみ一致線の有効状態となり、それ以外の場合には一致線の無効状態となる。したがって、無効化手段４７は、第四の実施の形態の無効化手段２２と同様に機能していることがわかる。
【０１７５】
第四の実施の形態の連想メモリ４１と同様に、第五の実施の形態の連想メモリ４５は、１次検索用連想メモリ４が出力する１次一致線１３−１〜１３−ｍと、計数出力線１８−１〜１８−ｐを、それぞれ記憶する手段を有することにより、１次検索用連想メモリ４と２次検索用連想メモリ４６とでパイプライン処理を構成することができる。これにより、クロック信号３９の周波数を向上させることが可能となる。
【０１７６】
第五の実施の形態の連想メモリ４５では、２次検索用連想メモリ４６のｍ本の２次一致線２１−１〜２１−ｍは、２次検索毎に、最大でも検索データ１０のビット長ｎに対応するｎ本のみが有効状態にプリ・チャージされ、最大でもｎ本が無効状態にディス・チャージされることになる。
【０１７７】
ここで第一の実施の形態の説明と同様に、０．２５μｍ製造プロセスで６４ビット３２７６８語の連想メモリ４５を構成した場合、電源電圧を２．５Ｖとし、検索を実行する周期を２０ｎｓとすると、２次検索毎のプリ・チャージ、ディス・チャージに必要な合計消費電力の最大値は、
（0.3ｐＦ×７／64×2.5Ｖ）÷20ｎｓ×2.5Ｖ×64本＝0.0006Ｗ
となる。このとき、１次検索用連想メモリ４が１次検索を実行するときの消費電力は第一の実施の形態と同様に３．０７Ｗであるから、２次検索用連想メモリ４６の消費電力は連想メモリ４５全体の消費電力の０．０２％となる。
【０１７８】
ここで、式４と同様に（ｍ−ｎ）≒（ｍ−１）との近似をした場合、従来の連想メモリ１００の消費電力を１としたとき、連想メモリ４５のチップ全体の消費電力は、次の式６で表される。ここでは、正の実数Ｘの小数点以下を切り上げて正の整数に変換する前述のＲｏｕｎｄｕｐ（Ｘ）関数を用いて表現する。
（１＋（Ｒｏｕｎｄｕｐ（Ｌｏｇ２（ｎ＋１））／ｎ）×ｎ／ｍ）／２
＝（１＋Ｒｏｕｎｄｕｐ（Ｌｏｇ２（ｎ＋１））／ｍ）／２  ……式６
【０１７９】
式６より、検索データ１０のビット幅ｎが６４、連想メモリ４１の語数が３２７６８の場合には、連想メモリ４５の消費電力は、従来の連想メモリ１００の消費電力の約５０．０１％となり、約４９．９％の消費電力を削減することができる。ｎ≪ｍの場合には、式６の値は約０．５０となり、従来の連想メモリ１００の消費電力に対して、第五の実施の形態の連想メモリ４５の消費電力は、ほぼ１／２となることがわかる。
【０１８０】
（第六の実施例）
次に、本発明の第一の実施の形態の連想メモリ１を転送先ネットワーク・アドレス計算に用いた本発明のネットワーク装置の一構成例を示すブロック図を図１０に示す。本発明のネットワーク装置４００は、入力通信データ４０８とクロック信号３９とを入力とし、出力通信データ４０９を出力する。入力通信データ４０８は、送出元ネットワーク・アドレス４１０と、転送先ネットワーク・アドレス４１１と、宛先ネットワーク・アドレス４１２と、データ部４１３とを有している。出力通信データ４０９は、送出元ネットワーク・アドレス４１０と、第２の転送先ネットワーク・アドレス４１４と、宛先ネットワーク・アドレス４１２と、データ部４１３とを有している。図１０では本発明のネットワーク装置４００を、図１１のネットワーク装置４００−１に適用した場合を例として説明する。
【０１８１】
ネットワーク装置４００は、宛先ネットワーク・アドレス抽出部４０６と、本発明の第一の実施の形態の連想メモリ１と、エンコーダ４０２と、メモリ４０４と、転送先ネットワーク・アドレス変更部４０７とにより構成される。ネットワーク装置４００は、クロック信号３９に同期して動作するものとする。
【０１８２】
宛先ネットワーク・アドレス抽出部４０６は、入力通信データ４０８の宛先ネットワーク・アドレス４１２を抽出し、検索データ１０として、連想メモリ１に入力する。
【０１８３】
第一の実施の形態の連想メモリ１は、前述のように、１次検索用連想メモリ４と、計数手段１７と２次検索用連想メモリ３と無効化手段２２とを有している。本例では連想メモリ１は９ビット５語構成ととする。また、計数手段１７は、表１および式１に従って１次検索用連想メモリ４が出力した９ビットの中間データ１５を４ビットの２次検索データ１９に変換し、４ビット５語構成の２次検索用連想メモリ３に出力するものとする。ここで、図１０では、記憶データの有効状態は“１”、無効状態は“０”とし、マスク情報の有効状態は“０”、無効状態は“１”とする。
【０１８４】
１次検索用連想メモリ４は、図１１のネットワーク装置４００−１に接続されているネットワーク装置４００−２、４００−３，４００−４、４００−５、および４００−６が属するセグメントを示すネットワーク・アドレスを、前述の構造化データの形式で格納している。従って図１０の例では、１次連想メモリ・ワード７−１には、ネットワーク装置４００−２が属するセグメント２を示すネットワーク・アドレス（２．＊．＊）を前述のように記憶データ“０１０．０００．０００”とマスク情報“１１１．０００．０００”との対で表現される構造化データの形式で格納している。
【０１８５】
同様に、１次連想メモリ・ワード７−２にはネットワーク装置４００−３が属するセグメント３を示すネットワーク・アドレス（３．＊．＊．）を、記憶データ“０１１．０００．０００”とマスク情報“１１１．０００．０００”との対で表現される構造化データの形式で格納している。１次連想メモリ・ワード７−３にはネットワーク装置４００−４が属するセグメント４を示すネットワーク・アドレス（１．２．＊）を、記憶データ“００１．０１０．０００”とマスク情報“１１１．１１１．０００”との対で表現される構造化データの形式で格納している。１次連想メモリ・ワード７−４にはネットワーク装置４００−５が属するセグメント５を示すネットワーク・アドレス（１．３．＊）を、記憶データ“００１．０１１．０００”とマスク情報“１１１．１１１．０００”との対で表現される構造化データの形式で格納している。１次連想メモリ・ワード７−５にはネットワーク装置４００−６が属するセグメント６を示すネットワーク・アドレス（２．６．＊）を、記憶データ“０１０．１１０．０００”とマスク情報“１１１．１１１．０００”との対で表現される構造化データの形式で格納している。
【０１８６】
また前述のように、２次連想メモリ・ワード９−１は、１次連想メモリ・ワード７−１が格納している記憶データ“０１０．０００．０００”を表１に従って変換した結果得られる、１０進数表現で７、２進数表現で“０１１１”を２次記憶データとして格納している。２次連想メモリ・ワード９−２は、１次連想メモリ・ワード７−２が格納している記憶データ“０１１．０００．０００”を表１に従って変換した結果得られる、１０進数表現で６、２進数表現で“０１１０”を２次記憶データとして格納している。
【０１８７】
２次連想メモリ・ワード９−３は、１次連想メモリ・ワード７−３が格納している記憶データ“００１．０１０．０００”を表１に従って変換した結果得られる、１０進数表現で４、２進数表現で“０１００”を２次記憶データとして格納している。２次連想メモリ・ワード９−４は、１次連想メモリ・ワード７−４が格納している記憶データ“００１．０１１．０００”を表１に従って変換した結果得られる、１０進数表現で３、２進数表現で“００１１”を２次記憶データとして格納している。２次連想メモリ・ワード９−５は、１次連想メモリ・ワード７−５が格納している記憶データ“０１０．１１０．０００”を表１に従って変換した結果得られる、１０進数表現で４、２進数表現で“０１００”を２次記憶データとして格納している。
【０１８８】
連想メモリ１は、前述のように、入力された検索データ１０と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線１１−１〜１１−５のみに有効状態を出力する。
【０１８９】
エンコーダ４０２は、連想メモリ１が出力した一致線１１−１〜１１−５をメモリ・アドレス信号４０３に符号化し、メモリ４０４に出力する。
【０１９０】
メモリ４０４には、連想メモリ１の各１次連想メモリ・ワード７−１〜７−５に格納されているセグメントを示すネットワーク・アドレスに対応するネットワーク装置のネットワーク・アドレスを、連想メモリ１の格納アドレスと対応するアドレスのワードに格納している。本例では連想メモリ１の格納アドレスと同一のアドレスが対応するものとする。たとえば、連想メモリ１の１次連想メモリ・ワード７−１にはアドレス（２．＊．＊）が格納されているが、これに対応する図１１のネットワーク装置４００−２のネットワーク・アドレスがメモリ４０４のワード１に格納されている。
【０１９１】
同様にメモリ４０４のワード２にはネットワーク装置４００−３のネットワーク・アドレスが、ワード３にはネットワーク装置４００−４のネットワーク・アドレスが、ワード４にはネットワーク装置４００−５のネットワーク・アドレスが、ワード５にはネットワーク装置４００−６のネットワーク・アドレスが、格納されている。メモリ４０４はメモリ・アドレス信号４０３をリード・アドレスとして指定される格納データを、メモリ・データ信号４０５として転送先ネットワーク・アドレス変更部４０７に出力する。ここで、一致線１１−１〜１１−ｍの状態を直接メモリ４０４のワード線に入力することにより、エンコーダ４０２を削除できることは言うまでもない。
【０１９２】
転送先ネットワーク・アドレス変更部４０７は、出力通信データ４０９の第２の転送先アドレス４１４を、メモリ・データ信号４０５の値に変更した後、第２の転送先ネットワーク・アドレス４１４に対応するネットワーク装置またはユーザ機器に転送を行う。
【０１９３】
次に本発明のネットワーク装置４００の動作を、図１１のネットワーク装置４００−１に適用した場合におけるユーザ機器４０１−１からユーザ機器４０１−３への通信データの転送を例として説明する。したがって、ネットワーク・アドレスを８進数で表現すると、入力通信データ４０８の送出元ネットワーク・アドレス４１０は（１．２．６）、宛先ネットワーク・アドレス４１２は（２．６．５）となっており、転送先ネットワーク・アドレス４１１は当然、ネットワーク装置４００−１のネットワーク・アドレスとなっている。
【０１９４】
ネットワーク装置４００−１に前記の入力通信データ４０８が入力されると、宛先ネットワーク・アドレス抽出部４０６は、宛先ネットワーク・アドレス４１２の８進数表現で（２．６．５）の値を検索データ１０として連想メモリ１に出力する。
【０１９５】
連想メモリ１では、前記の８進数表現で（２．６．５）の検索データ１０に対して１次検索用連想メモリ４で１次検索を行い、結果として１次連想メモリ・ワード７−１および７−５が一致し、１次一致線１３−１および１３−５に有効状態を出力する。また、前述のように、一致した記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、９ビットの中間データ１５として２進数表現で“０１０．１１０．０００”を計数手段１７に出力する。計数手段１７は、表１に従って９ビットの中間データ１５を、２進数表現で“０１００”の４ビットの２次検索データ１９に変換し、４ビット５語構成の２次検索用連想メモリ３に出力する。
【０１９６】
２次検索用連想メモリ３は、２次検索データ１９に対して２次検索を実行し、結果として２次連想メモリ・ワード９−３および９−５が一致し、２次一致線２１−３および２１−５に有効状態を出力する。無効化手段２２は、対応する１次一致線１３−１〜１３−５が無効状態である場合には２次一致線２１−１〜２１−５の状態を無効状態に変更した後、一致線１１−１〜１１−５に出力する。したがって、無効化手段２２は一致線１１−５のみに有効状態を出力することになる。
【０１９７】
これにより、エンコーダ４０２はメモリ・アドレス信号４０３として“５”を出力し、メモリ４０４はネットワーク装置４００−６のネットワーク・アドレスをメモリ・データ信号４０５として出力する。転送先ネットワーク・アドレス変更部４０７は、出力通信データ４０９の第２の転送先ネットワーク・アドレス４１４をメモリ・データ信号４０５の状態に変更し、出力通信データ４０９をネットワーク装置４００−６に向けて転送する。このようにネットワーク装置４００は、宛先ネットワーク・アドレス４１２に対する最適な経路を選択して転送を行えることが分かる。
【０１９８】
本発明のネットワーク装置４００は本発明の連想メモリ１により構成されるため、１クロック毎に転送先ネットワーク・アドレス計算を実行できるにもかかわらず、従来のネットワーク装置と比較して消費電力を大幅に削減することが可能である。したがって、電源装置、冷却装置などに小規模のものを用いることができるため、転送速度を犠牲とせずにネットワーク装置全体としてのコストを削減することができる。
【０１９９】
また、従来の連想メモリ１００と本発明の連想メモリ１が同一のチップ面積の場合、チップあたりの構造化データの格納語数の増加に伴いネットワーク装置４００に内蔵する連想メモリ１の個数を削減することができる。従って、複数の連想メモリが出力した検索結果の比較処理が不要になるため、ネットワーク装置４００を用いたコンピュータ・ネットワーク・システムのデータ転送速度を高速化することができる。
【産業上の利用可能性】
【０２００】
上述のように、本発明の連想メモリは、外部から与えられた検索データをマスク情報を考慮して格納している記憶データと比較する第１の検索結果を利用して計算される中間データに対してビット幅を圧縮する演算を行い第２の検索データを生成する計数手段と、前記記憶データおよび前記マスク情報と対応する第２の記憶データを前記第２の検索データと比較する第２の検索手段と、第１の検索結果が不一致であった記憶データに対応する第２の検索手段の比較結果を無効化する無効化手段を有しているため、検索データと一致する記憶データの中で対応するマスク情報の有効状態のビット数が最も少ない記憶データを識別する信号を出力する演算を１クロック毎に実行可能であるにもかかわらず、従来の連想メモリと比べてチップ面積を大幅に削減することが可能である。
【０２０１】
例えば、検索データが６４ビット幅の場合には、従来の連想メモリと比べてチップ面積を約３１％削減できる。つまり同一チップ面積の場合には記憶容量を約４２％増大させることが可能である。検索データのビット幅が大きくなるほど、本発明の面積削減効果も大きくなるため、ネットワーク・アドレスのビット幅が３２ビットから１２８ビットに拡大する次世代インターネットなどに適用した場合には、著しい効果を発揮することとになる。
【０２０２】
また、本発明の連想メモリは、検索データと一致する記憶データの中で対応するマスク情報の有効状態のビット数が最も少ない記憶データを識別する信号を出力する演算を１クロック毎に実行可能であるにもかかわらず、従来の連想メモリに比べて、消費電力を約５０％削減することができる。
【０２０３】
更に、本発明の連想メモリを、転送先ネットワーク・アドレス計算を行うネットワーク装置に組み込めば、従来に比較して消費電力が小さくなるため、電源装置、冷却装置に小規模のものを使用することが可能になり、ネットワーク装置全体としてのコストを削減できる、等の優れた効果を有する。
【０２０４】
コンピュータ・ネットワーク・システムのネットワーク装置に適用した場合は、データ転送速度を高速化でき、上述のようにチップあたりの記憶容量増加によりネットワーク装置に内蔵する連想メモリのチップ数を削減することにより複数チップが出力した検索結果の比較処理が不要になるためである。
【図面の簡単な説明】
【０２０５】
【図１−１】本発明の第一の実施の形態の連想メモリの一構成例を示すブロック図である（その１）。
【図１−２】本発明の第一の実施の形態の連想メモリの一構成例を示すブロック図である（その２）。
【図２−１】本発明の第一の実施の形態の連想メモリの動作例を示す図である（その１）。
【図２−２】本発明の第一の実施の形態の連想メモリの動作例を示す図である（その２）。
【図３−１】本発明の第二の実施の形態の連想メモリの一構成例を示すブロック図である（その１）。
【図３−２】本発明の第二の実施の形態の連想メモリの一構成例を示すブロック図である（その２）。
【図４−１】本発明の第二の実施の形態の連想メモリの動作例を示す図である（その１）。
【図４−２】本発明の第二の実施の形態の連想メモリの動作例を示す図である（その２）。
【図５−１】本発明の第三の実施の形態の連想メモリの一構成例を示すブロック図である（その１）。
【図５−２】本発明の第三の実施の形態の連想メモリの一構成例を示すブロック図である（その２）。
【図６−１】本発明の第三の実施の形態の連想メモリにおける１次連想メモリの一構成例を示すブロック図である（その１）。
【図６−２】本発明の第三の実施の形態の連想メモリにおける１次連想メモリの一構成例を示すブロック図である（その２）。
【図７−１】本発明の第三の実施の形態の連想メモリの動作例を示す図である（その１）。
【図７−２】本発明の第三の実施の形態の連想メモリの動作例を示す図である（その２）。
【図８−１】本発明の第四の実施の形態の連想メモリの一構成例を示すブロック図である（その１）。
【図８−２】本発明の第四の実施の形態の連想メモリの一構成例を示すブロック図である（その２）。
【図９−１】本発明の第五の実施の形態の連想メモリの一構成例を示すブロック図である（その１）。
【図９−２】本発明の第五の実施の形態の連想メモリの一構成例を示すブロック図である（その２）。
【図１０−１】本発明の連想メモリを転送先ネットワーク・アドレス計算に用いた本発明のネットワーク装置の一構成例を示すブロック図である（その１）。
【図１０−２】本発明の連想メモリを転送先ネットワーク・アドレス計算に用いた本発明のネットワーク装置の一構成例を示すブロック図である（その２）。
【図１０−３】本発明の連想メモリを転送先ネットワーク・アドレス計算に用いた本発明のネットワーク装置の一構成例を示すブロック図である（その３）。
【図１１】コンピュータ・ネットワークの接続例を示す図である。
【図１２】従来のネットワーク装置の転送先ネットワーク・アドレス計算の説明図である。
【図１３−１】従来の連想メモリの構成例を示すブロック図である（その１）。
【図１３−２】従来の連想メモリの構成例を示すブロック図である（その２）。
【図１４−１】従来の連想メモリにおける１次連想メモリの構成例を示すブロック図である（その１）。
【図１４−２】従来の連想メモリにおける１次連想メモリの構成例を示すブロック図である（その２）。
【図１５】従来の連想メモリにおける２次連想メモリの構成例を示すブロック図である。
【図１６−１】従来の連想メモリの動作例を示す図である（その１）。
【図１６−２】従来の連想メモリの動作例を示す図である（その２）。
【符号の説明】
【０２０６】
１，２  連想メモリ
３      ２次検索用連想メモリ
４      １次検索用連想メモリ
１５    中間データ
１７    計数手段
１９    ２次検索データ
２２    無効化手段
３９    クロック信号
４００  ネットワーク機器
４０２  エンコーダ
４０３  メモリ・アドレス信号
４０４  メモリ
４０５  メモリ・データ信号
４０６  宛先ネットワーク・アドレス抽出部
４０７  転送先ネットワーク・アドレス変更部
４０８  入力通信データ
４０９  出力通信データ
４１０  送出元ネットワーク・アドレス
４１２  宛先ネットワーク・アドレス
４１３  データ部
４１４  第２の転送先ネットワーク・アドレス
【図１−１】
2007295553.tif 000003
【図１−２】
2007295553.tif 000004
【図２−１】
2007295553.tif 000005
【図２−２】
2007295553.tif 000006
【図３−１】
2007295553.tif 000007
【図３−２】
2007295553.tif 000008
【図４−１】
2007295553.tif 000009
【図４−２】
2007295553.tif 000010
【図５−１】
2007295553.tif 000011
【図５−２】
2007295553.tif 000012
【図６−１】
2007295553.tif 000013
【図６−２】
2007295553.tif 000014
【図７−１】
2007295553.tif 000015
【図７−２】
2007295553.tif 000016
【図８−１】
2007295553.tif 000017
【図８−２】
2007295553.tif 000018
【図９−１】
2007295553.tif 000019
【図９−２】
2007295553.tif 000020
【図１０−１】
2007295553.tif 000021
【図１０−２】
2007295553.tif 000022
【図１０−３】
2007295553.tif 000023
【図１１】
2007295553.tif 000024
【図１２】
2007295553.tif 000025
【図１３−１】
2007295553.tif 000026
【図１３−２】
2007295553.tif 000027
【図１４−１】
2007295553.tif 000028
【図１４−２】
2007295553.tif 000029
【図１５】
2007295553.tif 000030
【図１６−１】
2007295553.tif 000031
【図１６−２】
2007295553.tif 000032