JP3662618B2 - マルチプロトコルアドレス検索用連想メモリおよびその検索方法 - Google Patents
マルチプロトコルアドレス検索用連想メモリおよびその検索方法 Download PDFInfo
- Publication number
- JP3662618B2 JP3662618B2 JP01510295A JP1510295A JP3662618B2 JP 3662618 B2 JP3662618 B2 JP 3662618B2 JP 01510295 A JP01510295 A JP 01510295A JP 1510295 A JP1510295 A JP 1510295A JP 3662618 B2 JP3662618 B2 JP 3662618B2
- Authority
- JP
- Japan
- Prior art keywords
- protocol
- sequencer
- entry
- identifier
- search
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
- 230000015654 memory Effects 0.000 title claims description 61
- 238000000034 method Methods 0.000 title claims description 26
- 238000010586 diagram Methods 0.000 description 21
- 238000004891 communication Methods 0.000 description 14
- 238000001514 detection method Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- COCAUCFPFHUGAA-MGNBDDOMSA-N n-[3-[(1s,7s)-5-amino-4-thia-6-azabicyclo[5.1.0]oct-5-en-7-yl]-4-fluorophenyl]-5-chloropyridine-2-carboxamide Chemical compound C=1C=C(F)C([C@@]23N=C(SCC[C@@H]2C3)N)=CC=1NC(=O)C1=CC=C(Cl)C=N1 COCAUCFPFHUGAA-MGNBDDOMSA-N 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 230000000873 masking effect Effects 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【０００１】
【産業上の利用分野】
本発明は、マルチプロトコルアドレス検索用連想メモリおよびその検索方法に関し、詳しくは、１つの連想メモリで複数の異なるプロトコルのアドレス（マルチプロトコルアドレス）を、それぞれのプロトコルに応じて検索することができ、高速かつ低コストにネットワークの経路制御を行うことができるマルチプロトコルアドレス検索用連想メモリおよびその検索方法に関する。
【０００２】
【従来の技術】
連想メモリ（ＣＡＭ）は、内容アドレス式メモリとも呼ばれ、通常の半導体メモリのようにデータを記憶する記憶部と、この記憶部に記憶されるデータを検索する検索部とを有している。記憶部には検索されるデータが予め記憶され、検索部において、記憶部に記憶されているデータと検索しようとするデータとが一致検索され、一致するデータの有無や記憶されているアドレス等が単一サイクルで検索され出力される。連想メモリを用いることにより、膨大な量のデータの中から目的とするデータを瞬時に得ることができるため、検索処理を頻繁に行うシステムの性能向上のために用いられる。
【０００３】
ここで、ネットワークの経路制御を例に挙げて、上述する連想メモリの適用例について説明する。まず、ネットワークの概略について述べる。
【０００４】
ネットワークに接続されたコンピュータ間は、ある特定のデータ通信プロトコル（以下、単にプロトコルと記述する）を用いてデータ通信が行われる。このようなプロトコルとしては、例えばＩＰ（Internet Protocol ）、ＩＰＸ（Internetwork Packet Exchange，Novel の Netwareで使われる）、DECNet、AppleTalk など多くの種類が存在し、そのビット長、データの格納順序、格納位置などは、それぞれのプロトコル毎に異なっているのが一般的である。又、ルータは異なるネットワークを相互接続するのに使われ、複数のプロトコルの経路制御が可能なものもある。これはマルチプロトコルルータと呼ばれる。
【０００５】
それぞれのプロトコルは、ネットワーク上に存在する全てのコンピュータに識別子としてプロトコルアドレス（当該プロトコルのアドレス：以下、単にアドレスと記述する）を割り当てる。これにより、それぞれのコンピュータは一意に識別される。しかし、マルチプロトコルルータは、アドレスだけではコンピュータを一意に識別することはできない。なぜなら、あるプロトコルと別の異なるプロトコルとが、それぞれ異なるコンピュータに同一アドレスを割り当てた場合、それぞれのプロトコルにより割り当てられたアドレスだけでは、コンピュータを一意に識別することができないという問題が発生するからである。例えば図９においてコンピュータ３からコンピュータ１へデータを転送する場合、ルータは目的地のアドレス１２３４からだけではコンピュータ１にデータを送るべきか、コンピュータ２にデータを送るべきか識別できない。
【０００６】
この問題点を解決するために、通常ＬＡＮ（Local Area Network）のフレームには上位のプロトコルの識別をするための識別子が含まれている。ルータはプロトコル識別子とアドレスを組み合わせて送信先を決定する。このようなＬＡＮのフレームとして、イーサネット（Ethernet）のフレームを例に挙げて説明を行う。
【０００７】
図６は、ＬＡＮの１つであるイーサネットのフレームの概念図である。このフレームは概念的なものであり現実のものとは異なるが、このイーサネットのフレームの転送先および転送元のアドレスＤＡおよびＳＡと、既存のプロトコルのプロトコルタイプＴＹＰと、既存のプロトコルのデータグラムと、通信エラー検出用データＣＲＣとから構成される。また、既存のプロトコルのデータグラムは、この既存のプロトコルのデータグラムの通信元および通信先のアドレスｓａおよびｄａと、通信されるデータｄａｔａから構成されるとする。
【０００８】
次に、ルータを介した通信について説明する。ここで、図７（ａ）はルータを用いたネットワーク接続の概念図、図７（ｂ）はコンピュータＡからルータＲに入力されるイーサネットのフレームの概念図、図７（ｃ）はルータＲからコンピュータＢに出力されるイーサネットのフレームの概念図である。なお、コンピュータＡ、ＢのＭＡＣ（Media Access Control）アドレス（イーサネットのアドレス）および既存のプロトコルのアドレスを、それぞれＧＡ、ＧＢおよびＬＡ、ＬＢとし、ルータＲのＭＡＣアドレスをＧＲとして以下の説明を続ける。
【０００９】
図７（ａ）に示すように、データの転送を行うルータＲには、各種のプロトコルのイーサネットのフレームが入力され、ルータＲにおいて、それぞれのプロトコルに応じて転送先が決定され、ルータＲからそれぞれの通信先にそれぞれのフレームが出力される。例えば、コンピュータＡからコンピュータＢにデータを送信する場合、コンピュータＡが用いるプロトコルのフレームがルータＲに入力され、ルータＲにおいて、コンピュータＡが用いるプロトコルに応じて転送先が決められ、その結果、ルータＲからコンピュータＢにフレームが出力される。
【００１０】
図７（ｂ）に示すように、コンピュータＡからルータＲに転送されるイーサネットのフレームには、このフレームの転送先および転送元のアドレスＧＲおよびＧＡと、既存のプロトコルのプロトコルタイプＴＹＰと、既存のプロトコルのデータグラムが含まれる。また、既存のプロトコルのデータグラムは、通信元および通信先のアドレスＬＡおよびＬＢと、通信されるデータｄａｔａを含んでいる。このイーサネットのフレームは、プロトコルタイプＴＹＰの既存のプロトコルのフレームが、イーサネットの転送元のアドレスＧＡから転送先のアドレスＧＲに、即ち、コンピュータＡからルータＲに転送されることを意味する。
【００１１】
このイーサネットのフレームがルータＲに入力されると、ルータＲはプロトコルタイプＴＹＰとＬＢから転送先を決定する。即ち、ルータは、コンピュータＢのアドレスＬＢを自分の持つテーブルで検索して、コンピュータＢのＭＡＣアドレスおよび、どのネットワークに接続されているかを知り、コンピュータＢの接続されているネットワークに図７（ｃ）で示されるイーサネットフレームを送出する。即ち、ＧＲはＧＢに、ＧＡはＧＲに変換される。
【００１２】
図７（ｃ）に示すように、ルータＲからコンピュータＢに転送されるイーサネットのフレームは、このフレームの転送先および転送元のアドレスＧＢおよびＧＲと、既存のプロトコルのプロトコルタイプＴＹＰと、既存のプロトコルのデータグラムを含んでいる。また、既存のプロトコルのデータグラムは、通信元および通信先のアドレスＬＡおよびＬＢと、通信されるデータｄａｔａを含んでいる。このイーサネットのフレームは、プロトコルタイプＴＹＰの既存のプロトコルのフレームが、イーサネットの転送元のアドレスＧＲから転送先のアドレスＧＢに、即ち、ルータＲからコンピュータＢに転送されることを意味する。
【００１３】
このように、ルータＲにより、送出先の決定が正しく行われることにより、複数のネットワーク上に異なる複数のプロトコルのフレームが混在する場合であっても、それぞれのコンピュータを一意に識別し、相互接続してデータ通信を行うことができる。マルチプロトコルルータは、各プロトコル毎に別々のアドレス検索テーブルを用意している。ＣＡＭをテーブルに使う場合は各プロトコル毎にＣＡＭのチップを割り当てることになる。
【００１４】
最後に、ルータが送出先を決定する場合に行うアドレス検索への連想メモリの適用例について説明する。上述するルータＲによるアドレス検索において、連想メモリは、既存のプロトコルの通信先のアドレスＬＢから、イーサネットのフレームの転送先のアドレスＧＢを得るために用いられる。
【００１５】
図８は、従来のネットワークのアドレス検索への連想メモリの適用例の模式図である。同図において、それぞれの連想メモリは、このネットワークで用いられる全てのプロトコルと１対１に対応し、それぞれの連想メモリには、対応するプロトコルのアドレスが、ネットワークに接続される全てのコンピュータについて予め記憶される。ルータＲにそれぞれのプロトコルに応じたイーサネットのフレームが入力されると、ルータＲにより、プロトコルタイプＴＹＰに対応する連想メモリが選択され、この連想メモリにおいて、既存のプロトコルの通信先のアドレスＬＢを用いた検索が行われ、高速にイーサネットの通信先のアドレスＧＢを得ることができる。
【００１６】
上述する連想メモリのアドレス検索への適用例においては、送出先アドレスの検索を高速に行うことができる。しかし、従来の連想メモリでは、異なる複数のプロトコルのデータグラム、特に、そのビット長、格納順序などが異なるアドレスデータを１つの連想メモリで検索することができないため、プロトコル毎に異なる連想メモリを用いなければならなかった。このため、使用する連想メモリの個数が増え、コスト高になるという問題点があった。これに対してコストを削減するために、連想メモリを使用せずにソフトウェアで検索を行うと、ソフトウェアによる検索は検索時間がかかり過ぎるという問題点があった。
【００１７】
【発明が解決しようとする課題】
本発明の目的は、前記従来技術に基づく種々の問題点をかえりみて、所定プロトコル識別子が記憶されているエントリを検出するとともに、所定プロトコル識別子に基づいてシーケンサを選択し、このシーケンサにより、所定プロトコル識別子により検出されたエントリの中からさらに所定プロトコルアドレスが記憶されているエントリを検出することにより、複数のそれぞれ異なるプロトコルのアドレスを１つの連想メモリテーブルで検索することができ、ネットワークの経路制御の高速化および低コスト化を同時に実現することができるマルチプロトコルアドレス検索用連想メモリおよびその検索方法を提供することにある。
【００１８】
【課題を解決するための手段】
上記目的を達成するために、本発明は、複数個の所定ビット長のセグメントからなるエントリを複数個有する連想メモリテーブルと、一致検索の手順をプロトコル毎に制御するシーケンサの選択手段とを備え、
前記エントリには少なくともプロトコル識別子およびプロトコルアドレスが記憶され、所定プロトコル識別子に一致するエントリが検出されるとともに、前記所定プロトコル識別子に応じたシーケンサが前記選択手段により選択され、前記検出されたエントリにおいて前記選択されたシーケンサにより、前記セグメント単位の前記プロトコルアドレスの論理積一致検索が行われることを特徴とするマルチプロトコルアドレス検索用連想メモリを提供するものである。
【００１９】
さらに、前記シーケンサを前記プロトコル毎に備えるのが好ましい。
【００２０】
また、本発明は、予めそれぞれのプロトコルに応じたプロトコル識別子およびプロトコルアドレスをそれぞれのエントリの異なるセグメントに記憶した後、
前記プロトコル識別子が記憶されているセグメントの一致検索を行い、前記所定プロトコル識別子が記憶されている前記エントリを検出するとともに、前記所定プロトコル識別子に基づいてシーケンサ識別子を獲得し、
次いで、前記シーケンサ識別子により前記所定プロトコル識別子に応じたシーケンサを選択し、
その後、前記選択されたシーケンサの制御に従って、前記所定プロトコル識別子により一致検出されたエントリの前記プロトコルアドレスが記憶されているセグメントの一致検索を行い、前記所定プロトコルアドレスが記憶されている前記エントリを検出することを特徴とするマルチプロトコルアドレスの検索方法を提供するものである。
【００２１】
ここで、予め前記プロトコル識別子に対応する前記シーケンサ識別子を前記セグメントの一部に記憶した後、
前記所定プロトコル識別子により一致検出されたエントリの前記セグメントの一部に記憶されたシーケンサ識別子を獲得するのが好ましい。
【００２２】
また、前記所定プロトコル識別子をデコードすることにより、前記シーケンサ識別子を獲得するのが好ましい。
【００２３】
【発明の作用】
本発明のマルチプロトコルアドレス検索用連想メモリは、シーケンサの選択手段、さらにはそれぞれのプロトコルに対応するシーケンサを備えるものである。既に述べたように、それぞれのプロトコルアドレスは、ビット長、格納位置などが異なるため、例えばＩＰアドレスとＩＰＸアドレスとを同一の検索手順により検索することはできない。そこで、本発明においては、ＲＯＭ、ＲＡＭ、レジスタなどによるルックアップテーブルや、デコード回路などのシーケンサの選択手段を備えることにより、それぞれのプロトコルに応じてシーケンサを選択し、それぞれのプロトコルに応じて当該プロトコルのアドレスを検索することができる。従って、本発明のマルチプロトコルアドレス検索用連想メモリによれば、複数の異なるプロトコルのアドレスを１つの連想メモリテーブルに記憶して、これらの中から所定プロトコルの所定アドレスを有するエントリを検出することができる。
【００２４】
また、本発明のマルチプロトコルアドレスの検索方法は、それぞれのエントリの異なるセグメントにプロトコル識別子およびプロトコルアドレスを記憶しておき、まず、プロトコル識別子が記憶されているセグメントを検索して、所定プロトコル識別子が記憶されているエントリを検出するとともに、この所定プロトコル識別子からシーケンサ識別子を獲得し、このシーケンサ識別子によりこのプロトコルに対応するシーケンサを選択し、続いて、このシーケンサに従って、所定プロトコル識別子により検出されたエントリのプロトコルアドレスが記憶されているセグメントを検索して、所定プロトコルアドレスが記憶されているエントリを検出するものである。従って、本発明のマルチプロトコルアドレスの検索方法によれば、プロトコル識別子により、それぞれのプロトコルアドレスがどのプロトコルのアドレスであるかを認識できるため、複数の異なるプロトコルのアドレスを１つの連想メモリに記憶して、これらをプロトコル識別子およびプロトコルアドレスにより検索することができる。これにより、ネットワークの経路制御を高速で行うことができるとともに、低コストでシステムを構築することができる。
【００２５】
【実施例】
以下に、添付の図面に示す好適実施例に基づいて、本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法を詳細に説明する。
【００２６】
図１は、本発明のマルチプロトコルアドレス検索用連想メモリの一実施例のブロック図である。このブロック図に示すように、本発明のマルチプロトコルアドレス検索用連想メモリ１０は、それぞれのプロトコルに応じたエントリデータを記憶し、このエントリデータと検索データとの一致検索を行う連想メモリテーブル１２と、それぞれのプロトコル毎に設けられ、エントリデータの検索の手順を制御するシーケンサ（群）１４と、プロトコルに応じてシーケンサ１４を選択するシーケンサの選択手段１６とから構成される。
【００２７】
また、図２は、上述する連想メモリテーブルの一実施例の概念図である。この連想メモリテーブル１２は、エントリ０，１，…，ｍから構成され、それぞれのエントリ０〜ｍには、例えば、ＩＰエントリ、ＩＰＸエントリ、DECNetエントリ、AppleTalk エントリなどのデータが任意の順序で記憶される。また、それぞれのエントリ０〜ｍは、検索の基本単位であるセグメント０，１，…，ｎに分割される。なお、それぞれのセグメント０〜ｎは、同一ビット長を有していても、異なるビット長を有していても良く、また、そのビット長は特に制限されるものではない。
【００２８】
次に、図３は、図２に示す連想メモリテーブルのエントリの一実施例の概念図である。エントリのセグメント０には、プロトコルＩＤ（識別子）およびシーケンサＩＤが記憶され、セグメント１〜ｎには、プロトコルＩＤに対応するプロトコルアドレスが記憶される。なお、それぞれのセグメント０〜ｎのビット長は、３２〜６４ビット程度である。例えば、セグメント１〜ｎのビット長が３２ビットである場合、セグメント１〜ｎに記憶されるプロトコルアドレスは、ＩＰエントリの場合、ＩＰアドレスは３２ビットであるからセグメント１だけに記憶される。同様に、ＩＰＸエントリの場合、ＩＰＸアドレスは８０ビットであるからセグメント１，２およびセグメント３の１６ビットまでに記憶される。このように、セグメントの個数は、セグメントのビット長およびプロトコルアドレスのビット長に応じて適宜選択される。
【００２９】
ここで、図４に、セグメント０に記憶されるプロトコルＩＤおよびシーケンサＩＤの具体例を示す。同図においては、説明を容易にするために、どのプロトコルに対応するデータであるかが、例えばＩＰ，ＩＰＸのようにコメントとして示されている。また、プロトコルＩＤは、イーサネット規格によるものが示されている。なお、シーケンサＩＤは、プロトコルＩＤに対応するシーケンサを選択するための番号であり、それぞれのプロトコルと１対１に対応する番号である。一例を述べれば、ＩＰの場合、プロトコルＩＤは０８００（１６進数）であり、これに対するシーケンサＩＤは番号１である。なお、この図に示す例では、セグメント０は、１６ビット長のプロトコルＩＤと、３ビット長のシーケンサＩＤとの１９ビットの大きさで構成される。
【００３０】
次に、図５に示す連想メモリテーブルの模式図を用いて、上述するように構成され、複数の異なるプロトコルに対応するエントリデータが記憶された本発明の連想メモリにおいて、所定プロトコルのアドレスが記憶されているエントリの検索方法について述べる。なお、図５に示す連想メモリテーブルは、エントリ０，１，…，４から構成され、それぞれのエントリ０，１，…，４は、セグメント０，１，…，４に分割されている。
【００３１】
まず、１回目の検索では、この連想メモリテーブルの全てのエントリ０〜４のセグメント０において、シーケンサＩＤをマスクしながら一致検索が行われ、所定プロトコルＩＤが記憶されているエントリが検出される。例えば、図４に示す例のように、検索データとして０８００（１６進数）が与えられると、セグメント０のプロトコルＩＤに０８００（１６進数）が記憶されたエントリだけが一致検出される。その結果、ここではエントリ０，２および３において一致検出され、エントリ１および４において不一致が検出されたとする。
【００３２】
その後、所定プロトコルＩＤにより一致検出されたエントリ０，２または３のセグメント０に記憶されているシーケンサＩＤを読み出し、例えば、図４に示す例では、プロトコルＩＤが０８００（１６進数）であるエントリに記憶されているシーケンサＩＤ、即ち、番号１を読み出し、このシーケンサＩＤに応じてシーケンサを選択する。シーケンサが選択されると、所定プロトコルＩＤにより一致検出されたエントリ０，２および３のセグメント１〜４におけるプロトコルアドレスの検索手順は、選択されたシーケンサにより制御される。
【００３３】
ここで、上述するシーケンサについて説明する。既に述べたように、それぞれのエントリのセグメント１〜ｎに記憶されるプロトコルアドレスは、プロトコルが異なれば、そのビット長、格納順序などが異なる。従って、検索しようとするプロトコルに応じて、セグメント１〜ｎにおける検索手順を変更する必要がある。この検索手順を制御するのがシーケンサである。なお、シーケンサは、ネットワークにおいて用いられるプロトコルに対して、１対１に連想メモリの内部または外部に用意されていれば良い。
【００３４】
次に、２回目の検索では、１回目の検索でセグメント０において所定プロトコルＩＤにより一致検出されたエントリ０，２および３のセグメント１において一致検索が行われ、所定プロトコルアドレスの最初の１セグメント分のデータが記憶されているエントリが検出される。なお、不一致が検出されたエントリ１および４のセグメント１においては一致検索は行われない。２回目の検索の結果、ここではエントリ０および３において一致検出され、エントリ２において不一致が検出されたとする。
【００３５】
そして、３回目の検索では、２回目の検索でセグメント１において所定プロトコルアドレスの最初の１セグメント分のデータにより一致検出されたエントリ０および３のセグメント２において一致検出が行われ、所定プロトコルアドレスの２番目の１セグメント分のデータが記憶されているエントリが検出される。なお、セグメント１において一致検出されなかったエントリ２のセグメント２においては一致検索は行われない。３回目の検索の結果、ここではエントリ３において一致検出され、エントリ０において不一致が検出されたとする。従って、エントリ３に所定プロトコルＩＤおよび所定プロトコルアドレスが記憶されていることが検出される。このように、論理積検索を行うことにより、効率の良い検索が行われる。
【００３６】
例えば、ＩＰエントリの場合、ＩＰアドレスは３２ビット（１セグメント）であるから、ＩＰのシーケンサは、所定プロトコルＩＤにより一致検出されたエントリのセグメント１の検索を行い、所定プロトコルアドレスが記憶されているエントリを検出する。このように、ＩＰエントリの場合、セグメント０および１を論理積検索することにより、所定プロトコルＩＤおよび所定プロトコルアドレスが記憶されているエントリを検出することができる。
【００３７】
一方、ＩＰＸエントリの場合、ＩＰＸアドレスは８０ビット（３セグメント（２セグメント＋１６ビット））であるから、ＩＰＸのシーケンサは、まず、所定プロトコルＩＤにより一致検出されたエントリのセグメント１の検索を行い、所定プロトコルアドレスの最初の１セグメント分のデータが記憶されているエントリを検出し、続いて、セグメント１においても所定プロトコルアドレスの最初の１セグメント分のデータにより一致検出されたエントリのセグメント２の検索を行って、所定プロトコルアドレスの２番目の１セグメント分のデータが記憶されているエントリを検出し、さらに、セグメント２においても所定プロトコルアドレスの２番目の１セグメント分のデータにより一致検出されたエントリのセグメント３の後半１６ビットをマスクして検索を行い、所定プロトコルアドレスの３番目の１セグメントの１６ビット分のデータが記憶されているエントリを検出する。このように、ＩＰＸエントリの場合、セグメント０〜３を論理積検索することにより、所定プロトコルＩＤおよび所定プロトコルアドレスが記憶されているエントリを検出することができる。
【００３８】
本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法は、基本的に以上のように構成される。なお、本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法を実施例に基づいて説明したが、本発明はこれに限定されるものではない。
【００３９】
例えば、上述する実施例においては、それぞれのエントリのセグメント０にプロトコルＩＤおよびシーケンサＩＤを記憶しているが、セグメント０には限定されず、どのセグメントに記憶しても良い。即ち、１回目の検索において、プロトコルＩＤが記憶されているセグメントを検索すれば良い。
また、本発明のシーケンサの選択手段として、セグメント０にシーケンサＩＤを記憶し、所定プロトコルＩＤからこれと１対１に対応するシーケンサＩＤを獲得する、いわゆるルックアップ方式によりシーケンサＩＤを獲得しているが、例えば所定プロトコルＩＤをデコードすることにより、シーケンサＩＤを獲得しても良い。この場合、図３のエントリの、シーケンサ識別子の部分は不要となる。同様に、シーケンサＩＤを連想メモリテーブルではなく、他のメモリ装置、例えばレジスタ、ＲＡＭ、ＲＯＭなどに記憶するよう構成しても良いし、これらのメモリ装置や上述するデコード回路などは、本発明の連想メモリの内部あるいは外部に設けても良い。
さらに、それぞれのエントリには、少なくともプロトコルＩＤあるいはシーケンサＩＤおよびプロトコルアドレスが記憶されるが、例えばこれらのデータ以外のデータを記憶するように構成しても良い。
【００４０】
【発明の効果】
以上詳細に説明した様に、本発明のマルチプロトコルアドレス検索用連想メモリは、それぞれのプロトコルに応じてプロトコルアドレスの検索手順を制御するシーケンサの選択手段を有するものである。また、本発明のマルチプロトコルアドレスの検索方法は、予め連想メモリテーブルのそれぞれのエントリに、プロトコルＩＤおよびプロトコルアドレスをそれぞれ異なるセグメントに記憶した後、まず、プロトコルＩＤが記憶されたセグメントを検索して、所定プロトコルＩＤが記憶されているエントリを検出するとともに、この所定プロトコルＩＤに基づいてシーケンサを選択し、続いて、選択されたシーケンサにより、所定プロトコルＩＤにより検出されたエントリのプロトコルアドレスが記憶されたセグメントを検索して、所定プロトコルアドレスが記憶されているエントリを検出するものである。即ち、本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法によれば、複数の異なるプロトコルアドレスを１つの連想メモリで検索することができるため、高速にネットワークの経路制御ができることは勿論、低コスト化も同時に実現することができる。
【図面の簡単な説明】
【図１】本発明のマルチプロトコルアドレス検索用連想メモリの一実施例のブロック図である。
【図２】本発明のマルチプロトコルアドレス検索用連想メモリにおける連想メモリテーブルの一実施例の概念図である。
【図３】本発明のマルチプロトコルアドレス検索用連想メモリにおける連想メモリテーブルのエントリの一実施例の概念図である。
【図４】本発明のマルチプロトコルアドレス検索用連想メモリにおける連想メモリテーブルのエントリのセグメント０の一実施例の概念図である。
【図５】本発明のマルチプロトコルアドレスの検索方法を説明する一実施例の概念図である。
【図６】イーサネットのフレームの概念図である。
【図７】（ａ）はルータを用いたネットワーク接続の概念図、（ｂ）はコンピュータＡからルータＲに入力されるイーサネットのフレームの概念図、（ｃ）はルータＲからコンピュータＢに出力されるイーサネットのフレームの概念図である。
【図８】従来のネットワークのアドレス検索への連想メモリの適用例の模式図である。
【図９】従来のルータを用いたネットワーク接続の概念図である。
【符号の説明】
１，２，３ コンピュータ
１０ 連想メモリ（ＣＡＭ）
１２ 連想メモリテーブル
１４ シーケンサ
１６ シーケンサの選択手段
【産業上の利用分野】
本発明は、マルチプロトコルアドレス検索用連想メモリおよびその検索方法に関し、詳しくは、１つの連想メモリで複数の異なるプロトコルのアドレス（マルチプロトコルアドレス）を、それぞれのプロトコルに応じて検索することができ、高速かつ低コストにネットワークの経路制御を行うことができるマルチプロトコルアドレス検索用連想メモリおよびその検索方法に関する。
【０００２】
【従来の技術】
連想メモリ（ＣＡＭ）は、内容アドレス式メモリとも呼ばれ、通常の半導体メモリのようにデータを記憶する記憶部と、この記憶部に記憶されるデータを検索する検索部とを有している。記憶部には検索されるデータが予め記憶され、検索部において、記憶部に記憶されているデータと検索しようとするデータとが一致検索され、一致するデータの有無や記憶されているアドレス等が単一サイクルで検索され出力される。連想メモリを用いることにより、膨大な量のデータの中から目的とするデータを瞬時に得ることができるため、検索処理を頻繁に行うシステムの性能向上のために用いられる。
【０００３】
ここで、ネットワークの経路制御を例に挙げて、上述する連想メモリの適用例について説明する。まず、ネットワークの概略について述べる。
【０００４】
ネットワークに接続されたコンピュータ間は、ある特定のデータ通信プロトコル（以下、単にプロトコルと記述する）を用いてデータ通信が行われる。このようなプロトコルとしては、例えばＩＰ（Internet Protocol ）、ＩＰＸ（Internetwork Packet Exchange，Novel の Netwareで使われる）、DECNet、AppleTalk など多くの種類が存在し、そのビット長、データの格納順序、格納位置などは、それぞれのプロトコル毎に異なっているのが一般的である。又、ルータは異なるネットワークを相互接続するのに使われ、複数のプロトコルの経路制御が可能なものもある。これはマルチプロトコルルータと呼ばれる。
【０００５】
それぞれのプロトコルは、ネットワーク上に存在する全てのコンピュータに識別子としてプロトコルアドレス（当該プロトコルのアドレス：以下、単にアドレスと記述する）を割り当てる。これにより、それぞれのコンピュータは一意に識別される。しかし、マルチプロトコルルータは、アドレスだけではコンピュータを一意に識別することはできない。なぜなら、あるプロトコルと別の異なるプロトコルとが、それぞれ異なるコンピュータに同一アドレスを割り当てた場合、それぞれのプロトコルにより割り当てられたアドレスだけでは、コンピュータを一意に識別することができないという問題が発生するからである。例えば図９においてコンピュータ３からコンピュータ１へデータを転送する場合、ルータは目的地のアドレス１２３４からだけではコンピュータ１にデータを送るべきか、コンピュータ２にデータを送るべきか識別できない。
【０００６】
この問題点を解決するために、通常ＬＡＮ（Local Area Network）のフレームには上位のプロトコルの識別をするための識別子が含まれている。ルータはプロトコル識別子とアドレスを組み合わせて送信先を決定する。このようなＬＡＮのフレームとして、イーサネット（Ethernet）のフレームを例に挙げて説明を行う。
【０００７】
図６は、ＬＡＮの１つであるイーサネットのフレームの概念図である。このフレームは概念的なものであり現実のものとは異なるが、このイーサネットのフレームの転送先および転送元のアドレスＤＡおよびＳＡと、既存のプロトコルのプロトコルタイプＴＹＰと、既存のプロトコルのデータグラムと、通信エラー検出用データＣＲＣとから構成される。また、既存のプロトコルのデータグラムは、この既存のプロトコルのデータグラムの通信元および通信先のアドレスｓａおよびｄａと、通信されるデータｄａｔａから構成されるとする。
【０００８】
次に、ルータを介した通信について説明する。ここで、図７（ａ）はルータを用いたネットワーク接続の概念図、図７（ｂ）はコンピュータＡからルータＲに入力されるイーサネットのフレームの概念図、図７（ｃ）はルータＲからコンピュータＢに出力されるイーサネットのフレームの概念図である。なお、コンピュータＡ、ＢのＭＡＣ（Media Access Control）アドレス（イーサネットのアドレス）および既存のプロトコルのアドレスを、それぞれＧＡ、ＧＢおよびＬＡ、ＬＢとし、ルータＲのＭＡＣアドレスをＧＲとして以下の説明を続ける。
【０００９】
図７（ａ）に示すように、データの転送を行うルータＲには、各種のプロトコルのイーサネットのフレームが入力され、ルータＲにおいて、それぞれのプロトコルに応じて転送先が決定され、ルータＲからそれぞれの通信先にそれぞれのフレームが出力される。例えば、コンピュータＡからコンピュータＢにデータを送信する場合、コンピュータＡが用いるプロトコルのフレームがルータＲに入力され、ルータＲにおいて、コンピュータＡが用いるプロトコルに応じて転送先が決められ、その結果、ルータＲからコンピュータＢにフレームが出力される。
【００１０】
図７（ｂ）に示すように、コンピュータＡからルータＲに転送されるイーサネットのフレームには、このフレームの転送先および転送元のアドレスＧＲおよびＧＡと、既存のプロトコルのプロトコルタイプＴＹＰと、既存のプロトコルのデータグラムが含まれる。また、既存のプロトコルのデータグラムは、通信元および通信先のアドレスＬＡおよびＬＢと、通信されるデータｄａｔａを含んでいる。このイーサネットのフレームは、プロトコルタイプＴＹＰの既存のプロトコルのフレームが、イーサネットの転送元のアドレスＧＡから転送先のアドレスＧＲに、即ち、コンピュータＡからルータＲに転送されることを意味する。
【００１１】
このイーサネットのフレームがルータＲに入力されると、ルータＲはプロトコルタイプＴＹＰとＬＢから転送先を決定する。即ち、ルータは、コンピュータＢのアドレスＬＢを自分の持つテーブルで検索して、コンピュータＢのＭＡＣアドレスおよび、どのネットワークに接続されているかを知り、コンピュータＢの接続されているネットワークに図７（ｃ）で示されるイーサネットフレームを送出する。即ち、ＧＲはＧＢに、ＧＡはＧＲに変換される。
【００１２】
図７（ｃ）に示すように、ルータＲからコンピュータＢに転送されるイーサネットのフレームは、このフレームの転送先および転送元のアドレスＧＢおよびＧＲと、既存のプロトコルのプロトコルタイプＴＹＰと、既存のプロトコルのデータグラムを含んでいる。また、既存のプロトコルのデータグラムは、通信元および通信先のアドレスＬＡおよびＬＢと、通信されるデータｄａｔａを含んでいる。このイーサネットのフレームは、プロトコルタイプＴＹＰの既存のプロトコルのフレームが、イーサネットの転送元のアドレスＧＲから転送先のアドレスＧＢに、即ち、ルータＲからコンピュータＢに転送されることを意味する。
【００１３】
このように、ルータＲにより、送出先の決定が正しく行われることにより、複数のネットワーク上に異なる複数のプロトコルのフレームが混在する場合であっても、それぞれのコンピュータを一意に識別し、相互接続してデータ通信を行うことができる。マルチプロトコルルータは、各プロトコル毎に別々のアドレス検索テーブルを用意している。ＣＡＭをテーブルに使う場合は各プロトコル毎にＣＡＭのチップを割り当てることになる。
【００１４】
最後に、ルータが送出先を決定する場合に行うアドレス検索への連想メモリの適用例について説明する。上述するルータＲによるアドレス検索において、連想メモリは、既存のプロトコルの通信先のアドレスＬＢから、イーサネットのフレームの転送先のアドレスＧＢを得るために用いられる。
【００１５】
図８は、従来のネットワークのアドレス検索への連想メモリの適用例の模式図である。同図において、それぞれの連想メモリは、このネットワークで用いられる全てのプロトコルと１対１に対応し、それぞれの連想メモリには、対応するプロトコルのアドレスが、ネットワークに接続される全てのコンピュータについて予め記憶される。ルータＲにそれぞれのプロトコルに応じたイーサネットのフレームが入力されると、ルータＲにより、プロトコルタイプＴＹＰに対応する連想メモリが選択され、この連想メモリにおいて、既存のプロトコルの通信先のアドレスＬＢを用いた検索が行われ、高速にイーサネットの通信先のアドレスＧＢを得ることができる。
【００１６】
上述する連想メモリのアドレス検索への適用例においては、送出先アドレスの検索を高速に行うことができる。しかし、従来の連想メモリでは、異なる複数のプロトコルのデータグラム、特に、そのビット長、格納順序などが異なるアドレスデータを１つの連想メモリで検索することができないため、プロトコル毎に異なる連想メモリを用いなければならなかった。このため、使用する連想メモリの個数が増え、コスト高になるという問題点があった。これに対してコストを削減するために、連想メモリを使用せずにソフトウェアで検索を行うと、ソフトウェアによる検索は検索時間がかかり過ぎるという問題点があった。
【００１７】
【発明が解決しようとする課題】
本発明の目的は、前記従来技術に基づく種々の問題点をかえりみて、所定プロトコル識別子が記憶されているエントリを検出するとともに、所定プロトコル識別子に基づいてシーケンサを選択し、このシーケンサにより、所定プロトコル識別子により検出されたエントリの中からさらに所定プロトコルアドレスが記憶されているエントリを検出することにより、複数のそれぞれ異なるプロトコルのアドレスを１つの連想メモリテーブルで検索することができ、ネットワークの経路制御の高速化および低コスト化を同時に実現することができるマルチプロトコルアドレス検索用連想メモリおよびその検索方法を提供することにある。
【００１８】
【課題を解決するための手段】
上記目的を達成するために、本発明は、複数個の所定ビット長のセグメントからなるエントリを複数個有する連想メモリテーブルと、一致検索の手順をプロトコル毎に制御するシーケンサの選択手段とを備え、
前記エントリには少なくともプロトコル識別子およびプロトコルアドレスが記憶され、所定プロトコル識別子に一致するエントリが検出されるとともに、前記所定プロトコル識別子に応じたシーケンサが前記選択手段により選択され、前記検出されたエントリにおいて前記選択されたシーケンサにより、前記セグメント単位の前記プロトコルアドレスの論理積一致検索が行われることを特徴とするマルチプロトコルアドレス検索用連想メモリを提供するものである。
【００１９】
さらに、前記シーケンサを前記プロトコル毎に備えるのが好ましい。
【００２０】
また、本発明は、予めそれぞれのプロトコルに応じたプロトコル識別子およびプロトコルアドレスをそれぞれのエントリの異なるセグメントに記憶した後、
前記プロトコル識別子が記憶されているセグメントの一致検索を行い、前記所定プロトコル識別子が記憶されている前記エントリを検出するとともに、前記所定プロトコル識別子に基づいてシーケンサ識別子を獲得し、
次いで、前記シーケンサ識別子により前記所定プロトコル識別子に応じたシーケンサを選択し、
その後、前記選択されたシーケンサの制御に従って、前記所定プロトコル識別子により一致検出されたエントリの前記プロトコルアドレスが記憶されているセグメントの一致検索を行い、前記所定プロトコルアドレスが記憶されている前記エントリを検出することを特徴とするマルチプロトコルアドレスの検索方法を提供するものである。
【００２１】
ここで、予め前記プロトコル識別子に対応する前記シーケンサ識別子を前記セグメントの一部に記憶した後、
前記所定プロトコル識別子により一致検出されたエントリの前記セグメントの一部に記憶されたシーケンサ識別子を獲得するのが好ましい。
【００２２】
また、前記所定プロトコル識別子をデコードすることにより、前記シーケンサ識別子を獲得するのが好ましい。
【００２３】
【発明の作用】
本発明のマルチプロトコルアドレス検索用連想メモリは、シーケンサの選択手段、さらにはそれぞれのプロトコルに対応するシーケンサを備えるものである。既に述べたように、それぞれのプロトコルアドレスは、ビット長、格納位置などが異なるため、例えばＩＰアドレスとＩＰＸアドレスとを同一の検索手順により検索することはできない。そこで、本発明においては、ＲＯＭ、ＲＡＭ、レジスタなどによるルックアップテーブルや、デコード回路などのシーケンサの選択手段を備えることにより、それぞれのプロトコルに応じてシーケンサを選択し、それぞれのプロトコルに応じて当該プロトコルのアドレスを検索することができる。従って、本発明のマルチプロトコルアドレス検索用連想メモリによれば、複数の異なるプロトコルのアドレスを１つの連想メモリテーブルに記憶して、これらの中から所定プロトコルの所定アドレスを有するエントリを検出することができる。
【００２４】
また、本発明のマルチプロトコルアドレスの検索方法は、それぞれのエントリの異なるセグメントにプロトコル識別子およびプロトコルアドレスを記憶しておき、まず、プロトコル識別子が記憶されているセグメントを検索して、所定プロトコル識別子が記憶されているエントリを検出するとともに、この所定プロトコル識別子からシーケンサ識別子を獲得し、このシーケンサ識別子によりこのプロトコルに対応するシーケンサを選択し、続いて、このシーケンサに従って、所定プロトコル識別子により検出されたエントリのプロトコルアドレスが記憶されているセグメントを検索して、所定プロトコルアドレスが記憶されているエントリを検出するものである。従って、本発明のマルチプロトコルアドレスの検索方法によれば、プロトコル識別子により、それぞれのプロトコルアドレスがどのプロトコルのアドレスであるかを認識できるため、複数の異なるプロトコルのアドレスを１つの連想メモリに記憶して、これらをプロトコル識別子およびプロトコルアドレスにより検索することができる。これにより、ネットワークの経路制御を高速で行うことができるとともに、低コストでシステムを構築することができる。
【００２５】
【実施例】
以下に、添付の図面に示す好適実施例に基づいて、本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法を詳細に説明する。
【００２６】
図１は、本発明のマルチプロトコルアドレス検索用連想メモリの一実施例のブロック図である。このブロック図に示すように、本発明のマルチプロトコルアドレス検索用連想メモリ１０は、それぞれのプロトコルに応じたエントリデータを記憶し、このエントリデータと検索データとの一致検索を行う連想メモリテーブル１２と、それぞれのプロトコル毎に設けられ、エントリデータの検索の手順を制御するシーケンサ（群）１４と、プロトコルに応じてシーケンサ１４を選択するシーケンサの選択手段１６とから構成される。
【００２７】
また、図２は、上述する連想メモリテーブルの一実施例の概念図である。この連想メモリテーブル１２は、エントリ０，１，…，ｍから構成され、それぞれのエントリ０〜ｍには、例えば、ＩＰエントリ、ＩＰＸエントリ、DECNetエントリ、AppleTalk エントリなどのデータが任意の順序で記憶される。また、それぞれのエントリ０〜ｍは、検索の基本単位であるセグメント０，１，…，ｎに分割される。なお、それぞれのセグメント０〜ｎは、同一ビット長を有していても、異なるビット長を有していても良く、また、そのビット長は特に制限されるものではない。
【００２８】
次に、図３は、図２に示す連想メモリテーブルのエントリの一実施例の概念図である。エントリのセグメント０には、プロトコルＩＤ（識別子）およびシーケンサＩＤが記憶され、セグメント１〜ｎには、プロトコルＩＤに対応するプロトコルアドレスが記憶される。なお、それぞれのセグメント０〜ｎのビット長は、３２〜６４ビット程度である。例えば、セグメント１〜ｎのビット長が３２ビットである場合、セグメント１〜ｎに記憶されるプロトコルアドレスは、ＩＰエントリの場合、ＩＰアドレスは３２ビットであるからセグメント１だけに記憶される。同様に、ＩＰＸエントリの場合、ＩＰＸアドレスは８０ビットであるからセグメント１，２およびセグメント３の１６ビットまでに記憶される。このように、セグメントの個数は、セグメントのビット長およびプロトコルアドレスのビット長に応じて適宜選択される。
【００２９】
ここで、図４に、セグメント０に記憶されるプロトコルＩＤおよびシーケンサＩＤの具体例を示す。同図においては、説明を容易にするために、どのプロトコルに対応するデータであるかが、例えばＩＰ，ＩＰＸのようにコメントとして示されている。また、プロトコルＩＤは、イーサネット規格によるものが示されている。なお、シーケンサＩＤは、プロトコルＩＤに対応するシーケンサを選択するための番号であり、それぞれのプロトコルと１対１に対応する番号である。一例を述べれば、ＩＰの場合、プロトコルＩＤは０８００（１６進数）であり、これに対するシーケンサＩＤは番号１である。なお、この図に示す例では、セグメント０は、１６ビット長のプロトコルＩＤと、３ビット長のシーケンサＩＤとの１９ビットの大きさで構成される。
【００３０】
次に、図５に示す連想メモリテーブルの模式図を用いて、上述するように構成され、複数の異なるプロトコルに対応するエントリデータが記憶された本発明の連想メモリにおいて、所定プロトコルのアドレスが記憶されているエントリの検索方法について述べる。なお、図５に示す連想メモリテーブルは、エントリ０，１，…，４から構成され、それぞれのエントリ０，１，…，４は、セグメント０，１，…，４に分割されている。
【００３１】
まず、１回目の検索では、この連想メモリテーブルの全てのエントリ０〜４のセグメント０において、シーケンサＩＤをマスクしながら一致検索が行われ、所定プロトコルＩＤが記憶されているエントリが検出される。例えば、図４に示す例のように、検索データとして０８００（１６進数）が与えられると、セグメント０のプロトコルＩＤに０８００（１６進数）が記憶されたエントリだけが一致検出される。その結果、ここではエントリ０，２および３において一致検出され、エントリ１および４において不一致が検出されたとする。
【００３２】
その後、所定プロトコルＩＤにより一致検出されたエントリ０，２または３のセグメント０に記憶されているシーケンサＩＤを読み出し、例えば、図４に示す例では、プロトコルＩＤが０８００（１６進数）であるエントリに記憶されているシーケンサＩＤ、即ち、番号１を読み出し、このシーケンサＩＤに応じてシーケンサを選択する。シーケンサが選択されると、所定プロトコルＩＤにより一致検出されたエントリ０，２および３のセグメント１〜４におけるプロトコルアドレスの検索手順は、選択されたシーケンサにより制御される。
【００３３】
ここで、上述するシーケンサについて説明する。既に述べたように、それぞれのエントリのセグメント１〜ｎに記憶されるプロトコルアドレスは、プロトコルが異なれば、そのビット長、格納順序などが異なる。従って、検索しようとするプロトコルに応じて、セグメント１〜ｎにおける検索手順を変更する必要がある。この検索手順を制御するのがシーケンサである。なお、シーケンサは、ネットワークにおいて用いられるプロトコルに対して、１対１に連想メモリの内部または外部に用意されていれば良い。
【００３４】
次に、２回目の検索では、１回目の検索でセグメント０において所定プロトコルＩＤにより一致検出されたエントリ０，２および３のセグメント１において一致検索が行われ、所定プロトコルアドレスの最初の１セグメント分のデータが記憶されているエントリが検出される。なお、不一致が検出されたエントリ１および４のセグメント１においては一致検索は行われない。２回目の検索の結果、ここではエントリ０および３において一致検出され、エントリ２において不一致が検出されたとする。
【００３５】
そして、３回目の検索では、２回目の検索でセグメント１において所定プロトコルアドレスの最初の１セグメント分のデータにより一致検出されたエントリ０および３のセグメント２において一致検出が行われ、所定プロトコルアドレスの２番目の１セグメント分のデータが記憶されているエントリが検出される。なお、セグメント１において一致検出されなかったエントリ２のセグメント２においては一致検索は行われない。３回目の検索の結果、ここではエントリ３において一致検出され、エントリ０において不一致が検出されたとする。従って、エントリ３に所定プロトコルＩＤおよび所定プロトコルアドレスが記憶されていることが検出される。このように、論理積検索を行うことにより、効率の良い検索が行われる。
【００３６】
例えば、ＩＰエントリの場合、ＩＰアドレスは３２ビット（１セグメント）であるから、ＩＰのシーケンサは、所定プロトコルＩＤにより一致検出されたエントリのセグメント１の検索を行い、所定プロトコルアドレスが記憶されているエントリを検出する。このように、ＩＰエントリの場合、セグメント０および１を論理積検索することにより、所定プロトコルＩＤおよび所定プロトコルアドレスが記憶されているエントリを検出することができる。
【００３７】
一方、ＩＰＸエントリの場合、ＩＰＸアドレスは８０ビット（３セグメント（２セグメント＋１６ビット））であるから、ＩＰＸのシーケンサは、まず、所定プロトコルＩＤにより一致検出されたエントリのセグメント１の検索を行い、所定プロトコルアドレスの最初の１セグメント分のデータが記憶されているエントリを検出し、続いて、セグメント１においても所定プロトコルアドレスの最初の１セグメント分のデータにより一致検出されたエントリのセグメント２の検索を行って、所定プロトコルアドレスの２番目の１セグメント分のデータが記憶されているエントリを検出し、さらに、セグメント２においても所定プロトコルアドレスの２番目の１セグメント分のデータにより一致検出されたエントリのセグメント３の後半１６ビットをマスクして検索を行い、所定プロトコルアドレスの３番目の１セグメントの１６ビット分のデータが記憶されているエントリを検出する。このように、ＩＰＸエントリの場合、セグメント０〜３を論理積検索することにより、所定プロトコルＩＤおよび所定プロトコルアドレスが記憶されているエントリを検出することができる。
【００３８】
本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法は、基本的に以上のように構成される。なお、本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法を実施例に基づいて説明したが、本発明はこれに限定されるものではない。
【００３９】
例えば、上述する実施例においては、それぞれのエントリのセグメント０にプロトコルＩＤおよびシーケンサＩＤを記憶しているが、セグメント０には限定されず、どのセグメントに記憶しても良い。即ち、１回目の検索において、プロトコルＩＤが記憶されているセグメントを検索すれば良い。
また、本発明のシーケンサの選択手段として、セグメント０にシーケンサＩＤを記憶し、所定プロトコルＩＤからこれと１対１に対応するシーケンサＩＤを獲得する、いわゆるルックアップ方式によりシーケンサＩＤを獲得しているが、例えば所定プロトコルＩＤをデコードすることにより、シーケンサＩＤを獲得しても良い。この場合、図３のエントリの、シーケンサ識別子の部分は不要となる。同様に、シーケンサＩＤを連想メモリテーブルではなく、他のメモリ装置、例えばレジスタ、ＲＡＭ、ＲＯＭなどに記憶するよう構成しても良いし、これらのメモリ装置や上述するデコード回路などは、本発明の連想メモリの内部あるいは外部に設けても良い。
さらに、それぞれのエントリには、少なくともプロトコルＩＤあるいはシーケンサＩＤおよびプロトコルアドレスが記憶されるが、例えばこれらのデータ以外のデータを記憶するように構成しても良い。
【００４０】
【発明の効果】
以上詳細に説明した様に、本発明のマルチプロトコルアドレス検索用連想メモリは、それぞれのプロトコルに応じてプロトコルアドレスの検索手順を制御するシーケンサの選択手段を有するものである。また、本発明のマルチプロトコルアドレスの検索方法は、予め連想メモリテーブルのそれぞれのエントリに、プロトコルＩＤおよびプロトコルアドレスをそれぞれ異なるセグメントに記憶した後、まず、プロトコルＩＤが記憶されたセグメントを検索して、所定プロトコルＩＤが記憶されているエントリを検出するとともに、この所定プロトコルＩＤに基づいてシーケンサを選択し、続いて、選択されたシーケンサにより、所定プロトコルＩＤにより検出されたエントリのプロトコルアドレスが記憶されたセグメントを検索して、所定プロトコルアドレスが記憶されているエントリを検出するものである。即ち、本発明のマルチプロトコルアドレス検索用連想メモリおよびその検索方法によれば、複数の異なるプロトコルアドレスを１つの連想メモリで検索することができるため、高速にネットワークの経路制御ができることは勿論、低コスト化も同時に実現することができる。
【図面の簡単な説明】
【図１】本発明のマルチプロトコルアドレス検索用連想メモリの一実施例のブロック図である。
【図２】本発明のマルチプロトコルアドレス検索用連想メモリにおける連想メモリテーブルの一実施例の概念図である。
【図３】本発明のマルチプロトコルアドレス検索用連想メモリにおける連想メモリテーブルのエントリの一実施例の概念図である。
【図４】本発明のマルチプロトコルアドレス検索用連想メモリにおける連想メモリテーブルのエントリのセグメント０の一実施例の概念図である。
【図５】本発明のマルチプロトコルアドレスの検索方法を説明する一実施例の概念図である。
【図６】イーサネットのフレームの概念図である。
【図７】（ａ）はルータを用いたネットワーク接続の概念図、（ｂ）はコンピュータＡからルータＲに入力されるイーサネットのフレームの概念図、（ｃ）はルータＲからコンピュータＢに出力されるイーサネットのフレームの概念図である。
【図８】従来のネットワークのアドレス検索への連想メモリの適用例の模式図である。
【図９】従来のルータを用いたネットワーク接続の概念図である。
【符号の説明】
１，２，３ コンピュータ
１０ 連想メモリ（ＣＡＭ）
１２ 連想メモリテーブル
１４ シーケンサ
１６ シーケンサの選択手段
Claims (5)
- 複数個の所定ビット長のセグメントからなるエントリを複数個有する連想メモリテーブルと、一致検索の手順をプロトコル毎に制御するシーケンサの選択手段とを備え、
前記エントリには少なくともプロトコル識別子およびプロトコルアドレスが記憶され、所定プロトコル識別子に一致するエントリが検出されるとともに、前記所定プロトコル識別子に応じたシーケンサが前記選択手段により選択され、前記検出されたエントリにおいて前記選択されたシーケンサにより、前記セグメント単位の前記プロトコルアドレスの論理積一致検索が行われることを特徴とするマルチプロトコルアドレス検索用連想メモリ。 - さらに、前記シーケンサを前記プロトコル毎に備える請求項１に記載のマルチプロトコルアドレス検索用連想メモリ。
- 予めそれぞれのプロトコルに応じたプロトコル識別子およびプロトコルアドレスをそれぞれのエントリの異なるセグメントに記憶した後、
前記プロトコル識別子が記憶されているセグメントの一致検索を行い、前記所定プロトコル識別子が記憶されている前記エントリを検出するとともに、前記所定プロトコル識別子に基づいてシーケンサ識別子を獲得し、
次いで、前記シーケンサ識別子により前記所定プロトコル識別子に応じたシーケンサを選択し、
その後、前記選択されたシーケンサの制御に従って、前記所定プロトコル識別子により一致検出されたエントリの前記プロトコルアドレスが記憶されているセグメントの一致検索を行い、前記所定プロトコルアドレスが記憶されている前記エントリを検出することを特徴とするマルチプロトコルアドレスの検索方法。 - 予め前記プロトコル識別子に対応する前記シーケンサ識別子を前記セグメントの一部に記憶した後、
前記所定プロトコル識別子により一致検出されたエントリの前記セグメントの一部に記憶されたシーケンサ識別子を獲得する請求項３に記載のマルチプロトコルアドレスの検索方法。 - 前記所定プロトコル識別子をデコードすることにより、前記シーケンサ識別子を獲得する請求項３に記載のマルチプロトコルアドレスの検索方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01510295A JP3662618B2 (ja) | 1995-02-01 | 1995-02-01 | マルチプロトコルアドレス検索用連想メモリおよびその検索方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01510295A JP3662618B2 (ja) | 1995-02-01 | 1995-02-01 | マルチプロトコルアドレス検索用連想メモリおよびその検索方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH08212790A JPH08212790A (ja) | 1996-08-20 |
| JP3662618B2 true JP3662618B2 (ja) | 2005-06-22 |
Family
ID=11879485
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP01510295A Expired - Lifetime JP3662618B2 (ja) | 1995-02-01 | 1995-02-01 | マルチプロトコルアドレス検索用連想メモリおよびその検索方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3662618B2 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000151709A (ja) * | 1998-11-12 | 2000-05-30 | Nec Corp | ルーティングアドレス検索システム |
| CN1324861C (zh) * | 2002-10-03 | 2007-07-04 | In4S公司 | 位串的校验方法及装置 |
| WO2014141566A1 (ja) | 2013-03-13 | 2014-09-18 | 長瀬産業株式会社 | 半導体装置及び半導体装置に対するエントリアドレス書き込み／読み出し方法 |
-
1995
- 1995-02-01 JP JP01510295A patent/JP3662618B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH08212790A (ja) | 1996-08-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10715439B2 (en) | Longest prefix matching providing packet processing and/or memory efficiencies in processing of packets | |
| US5815664A (en) | Address reporting device and method for detecting authorized and unauthorized addresses in a network environment | |
| US6957272B2 (en) | Stackable lookup engines | |
| US10333845B2 (en) | Forwarding data packets | |
| US20060098644A1 (en) | Translating native medium access control (MAC) addresses to hierarchical MAC addresses and their use | |
| JPH10164118A (ja) | Ｌａｎ間接続装置 | |
| EP1540522A1 (en) | Technique to improve network routing using best-match and exact-match techniques | |
| JP6437693B2 (ja) | マルチキャストデータパケット転送 | |
| US7440460B2 (en) | Apparatus and method for forwarding mixed data packet types in a high-speed router | |
| JP2000196672A (ja) | ネットワ―ク間中継装置 | |
| US7145911B2 (en) | Method and system for parallel hash transformation for an address input | |
| US8018935B2 (en) | Address search | |
| JP3662618B2 (ja) | マルチプロトコルアドレス検索用連想メモリおよびその検索方法 | |
| EP4423993A1 (en) | Mac-based routing | |
| US9014195B2 (en) | Packet forwarding method and system | |
| US10242740B2 (en) | T-CAM bier bit-string lookups | |
| JP3132426B2 (ja) | 高速ｌａｎスイッチング制御方法とそのシステム | |
| CN101099347A (zh) | 可掩码内容可寻址存储器 | |
| EP2958286B1 (en) | A method of using generic modification instructions to enable flexible modifications of packets and an apparatus thereof | |
| US7275077B2 (en) | Method for associating a first address with a second address of reduced size for directly addressing a context memory on a computer | |
| JP3567903B2 (ja) | アドレスサーチ装置、同方法および同手順を記録した記録媒体 | |
| JP3487342B2 (ja) | 転送先情報検索方式 | |
| KR980013128A (ko) | 이더넷 스위치를 이용한 3계층 라우팅 처리방법 및 장치 | |
| JP3508057B2 (ja) | レイヤ３スイッチ | |
| JPH11308218A (ja) | レイヤ３マルチキャスト送信方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050121 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050308 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050324 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080401 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090401 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090401 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100401 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100401 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110401 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110401 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130401 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140401 Year of fee payment: 9 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313111 |
|
| R360 | Written notification for declining of transfer of rights |
Free format text: JAPANESE INTERMEDIATE CODE: R360 |
|
| R360 | Written notification for declining of transfer of rights |
Free format text: JAPANESE INTERMEDIATE CODE: R360 |
|
| R371 | Transfer withdrawn |
Free format text: JAPANESE INTERMEDIATE CODE: R371 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313111 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |