JPH10126422A - 同時サーチ内容アドレス可能メモリ回路のための装置および方法 - Google Patents

同時サーチ内容アドレス可能メモリ回路のための装置および方法

Info

Publication number
JPH10126422A
JPH10126422A JP9276556A JP27655697A JPH10126422A JP H10126422 A JPH10126422 A JP H10126422A JP 9276556 A JP9276556 A JP 9276556A JP 27655697 A JP27655697 A JP 27655697A JP H10126422 A JPH10126422 A JP H10126422A
Authority
JP
Japan
Prior art keywords
word
vci
match
vpi
comparison
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.)
Granted
Application number
JP9276556A
Other languages
English (en)
Other versions
JPH10126422A5 (ja
JP4402178B2 (ja
Inventor
Jon Ashor Loschke
ジョン・アショア・ロシュク
Charley Michael Parks
チャーリー・マイケル・パークス
Mark Franklin
マーク・フランクリン
Kenneth Wade Jones
ケニス・ウェイド・ジョーンズ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Motorola Solutions Inc
Original Assignee
Motorola Inc
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Motorola Inc filed Critical Motorola Inc
Publication of JPH10126422A publication Critical patent/JPH10126422A/ja
Publication of JPH10126422A5 publication Critical patent/JPH10126422A5/ja
Application granted granted Critical
Publication of JP4402178B2 publication Critical patent/JP4402178B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3081—ATM peripheral units, e.g. policing, insertion or extraction
    • H04L49/309—Header conversion, routing tables or routing tags
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90339—Query processing by using parallel associative memories or content-addressable memories
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H04Q11/0478—Provisions for broadband connections

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【課題】 簡単な構成で実施できる内容アドレス可能メ
モリ回路および交換識別子の同時サーチを可能にする。 【解決手段】 ＡＴＭヘッダを含む基準ワードの内容に
対応する出力ワードが生成される内容アドレス可能メモ
リ回路１００を実施するための回路および方法が提供さ
れる。第１の態様では、２進サーチ論理回路１０４がメ
モリアレイ１０１を２進サーチして内容が基準ワードに
等しい整合ワードを検出する。出力信号は整合が検出さ
れたかあるいはメモリアレイ１０１の２進サーチを整合
ワードのロケーションアドレスの上または下のアドレス
で継続すべきことを示す。第２の態様では、内容アドレ
ス可能メモリ回路１００は交換識別子、仮想回路識別子
および仮想経路識別子の同時サーチを行いＡＴＭヘッダ
に対して仮想経路接続または仮想回路接続が存在するか
否かを判定する。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は一般的にはデジタル
電子装置に関し、かつより特定的には交換ネットワーク
においてヘッダ情報を管理するために使用される装置に
関する。
【０００２】
【従来の技術】通信およびコンピュータネットワークは
種々のハードウエア機器およびソフトウエアから構成さ
れかつ用途および複雑さが増大してきている。コンピュ
ータの典型としてのコンピュータネットワークの人気お
よびネットワークユーザの間で転送されるデータの量の
増大はネットワークの容量およびプロトコルを時間と共
に増大させている。種々のネットワーク通信プロトコル
はデータをネットワークによって結合された装置の間で
転送する。イーサネットおよび非同期転送モードはその
ような通信プロトコルの例である。
【０００３】非同期転送モード（以後“ＡＴＭ”と称す
る）はツイストケーブルを使用して２５メガビット／秒
程度の低いかつ光ケーブルを使用して１０ギガビット／
秒程度の高い帯域幅を提供する。ＡＴＭスイッチまたは
交換機（ＡＴＭ ｓｗｉｔｃｈ）はセルをネットワーク
内の種々のポイントの間で転送する。セルは制御情報、
ヘッダおよびデータパケットを含む。セル内のヘッダは
ＡＴＭ交換機がデータを導くことができるようにする交
換識別子（ｓｗｉｔｃｈｉｎｇ ｉｄｅｎｔｉｆｉｅｒ
ｓ）を含む。ＡＴＭスイッチはプログラムされたリスト
に対してそれが受信する各々の交換識別子を問合せてど
の出力チャネルにセルが出力されるべきかを決定する。
データパケットが中間ノードによって受信されたとき、
データパケットに付随するヘッダにデスティネイション
情報が含まれている。ノードはそのメモリを調べてデス
ティネイション情報が前に記憶されているか否かを決定
することによりその伝送に対するデータパケットを導く
ことにそれが前に同意したか否かを判定する。もし同意
しておれば、フォワードアドレス（ｆｏｒｗａｒｄｉｎ
ｇ ａｄｄｒｅｓｓ）もまた記憶されておりかつノード
はそのデータパケットをデスティネイションアドレスに
向かうルートにおける次のノードへと送る。それが各々
のデータ転送を受信したとき、ノードはそのメモリの内
容を問合せてそれが送信を送ることに同意したか否かを
決定する。もしデスティネイション情報があらかじめ送
られれば、メモリはそのデータパケットを次のノードに
導くために該デスティネイション情報に関連するフォワ
ードアドレスを作成する。
【０００４】内容アドレス可能メモリまたは連想記憶装
置（以後“ＣＡＭ”と称する）はＡＴＭスイッチのため
の交換識別子を記憶する。連想または内容アドレス可能
メモリにおいては、整合ワードおよび交換識別子がメモ
リ内に関連する対として記憶される。ＣＡＭが基準ワー
ドを受信したとき、それは該基準ワードに等しい整合ワ
ードがメモリに格納されているか否かを判定する。もし
格納されておれば、それは整合した基準ワードに関連す
るリンクワードを作成する。ＣＡＭの重要な面は整合ワ
ードおよびその関連するリンクワードの間の関連または
連想であり、各々のワードがその定義と関連して記憶さ
れている辞書とよく似ている。辞書においては、ある提
供されたワードがルックアップされかつ該ワードに関連
する定義が生成される。ＣＡＭにおいては、提供された
基準ワードがルックアップされ、すなわち、整合ワード
と比較され、かつもしそれらが等しければ、整合ワード
に関連するリンクワードが生成される。
【０００５】一般に、ＡＴＭのＣＡＭのメモリアレイは
整合ワードテーブルおよびリンクワードテーブルへと編
成される。もし基準ワードが整合ワードテーブルからの
エントリと整合すれば、関連するリンクワードが出力に
生成される。もし整合が検出されなければ、出力ワード
は、例えば、エラーフラグビットをセットすることによ
り不首尾または障害を指示する。ＡＴＭの用途において
は、基準ワードは交換識別子からなる。交換識別子は仮
想パス識別子（ｖｉｒｔｕａｌ ｐａｔｈ ｉｄｅｎｔ
ｉｆｉｅｒ）（以後“ＶＰＩ”と称する）および仮想チ
ャネル識別子（ｖｉｒｔｕａｌ ｃｈａｎｎｅｌ ｉｄ
ｅｎｔｉｆｉｅｒ）（以後“ＶＣＩ”と称する）から構
成される。ＣＡＭはヘッダにおけるＶＰＩおよびＶＣＩ
をＣＡＭにおけるＶＰＩおよびＶＣＩエントリと比較す
る。交換識別子は仮想パス接続（以後“ＶＰＣ”と称す
る）または仮想回路接続（以後“ＶＣＣ”と称する）が
存在するか否かを決定する。
【０００６】小さなサイズのＣＡＭはしばしばこの機能
をハードウエアで提供し、従って基準ワードが同時に整
合ワードテーブルにおけるそれぞれのワードと比較され
るようにし、それによって出力ワードが１クロックサイ
クルで生成される全並列モード（ｆｕｌｌ ｐａｒａｌ
ｌｅｌ ｍｏｄｅ）で動作する。しかしながら、より大
きなＣＡＭの必要性が増大するに応じて、並列モードは
長いサーチ時間のため可能ではなくなる。
【０００７】
【発明が解決しようとする課題】大きなＣＡＭを実施す
るための従来より知られた技術はメモリを区別可能なま
たは別個のクラスに予めソートする（ｐｒｅｓｏｒｔ）
ことである。例えば、４，０９６ワードの深さのＣＡＭ
は特定の整合およびリンクワード対がＣＡＭの１つにの
み記憶される４つの別個のより浅い１，０２４ワードの
ＣＡＭへと予め分類される。しかしながら、この手法は
他のものが実質的に空きを有する一方で１つのクラスに
対応するＣＡＭが満たされることになり、それによって
ＣＡＭの深さを実効的に低減する。必要に応じて各々の
ＣＡＭのサイズを動的に調整するためＣＡＭに論理を加
えることはＣＡＭの複雑さおよびコストを実質的に増大
させる。
【０００８】さらに、ＶＣＣまたはＶＰＣを確立するた
め、並列サーチ戦略が使用されてもあるいは直列サーチ
戦略が使用されても、各々のＣＡＭエントリに対して２
つのサーチが必要とされる。第１のサーチはＶＣＣをチ
ェックし、入力ヘッダおよび交換識別子を比較する。第
２のサーチはＶＰＣに対するもので、入力ヘッダおよび
交換識別子を比較する。
【０００９】並列サーチを行うために２つの知られた手
法が使用される。１つの方法は１つのＣＡＭアレイを使
用し、各アレイを２回問合せる。他の方法は２つの別個
のＣＡＭを使用し、各々のＣＡＭがＶＣＩまたはＶＰＩ
のみを記憶する。１つのＣＡＭの手法はデュアルＣＡＭ
手法よりも多くの時間を必要とする。しかしながら、デ
ュアルＣＡＭ手法は交換ネッワトークにより多くのハー
ドウエアおよびコストを加えることになる。
【００１０】
【課題を解決するための手段】本発明の一態様によれ
ば、内容アドレス可能メモリ（ＣＡＭ）を実施する方法
が提供され、該方法は第１のメモリアレイおよび第２の
メモリアレイを提供する段階であり、前記第１のメモリ
アレイは整合ワードを備えかつ前記第２のメモリアレイ
はリンクワードを備えるもの、基準ワードを前記ＣＡＭ
に提供する段階、前記第１のメモリアレイを２進サーチ
して前記基準ワードに等しい整合ワードを検出する段
階、そして前記第２のメモリアレイから前記整合ワード
に対応するリンクワードを出力する段階、を具備するこ
とを特徴とする。
【００１１】本発明の別の態様では、制御情報の同時サ
ーチのための方法が提供され、該方法はヘッダから第１
および第２のフィールドを読み取る段階、そして並列的
に、（１）前記第１のフィールドおよび第１のタグ
（２）前記第２のフィールドおよび第２のタグ、そして
（３）所定のベクトルを備えた第２のフィールド、を比
較する段階、を具備することを特徴とする。
【００１２】この場合、前記読み取る段階は、メモリア
レイの２進インデクシングを行う段階を具備すると好都
合である。
【００１３】また、前記第１のフィールドおよび前記第
２のフィールドはＡＴＭヘッダを含むものとすることが
できる。
【００１４】さらに、前記比較する段階に応じて前記第
１のフィールドおよび前記第２のフィールドを変換する
段階を具備すると好都合である。
【００１５】
【発明の実施の形態】図１は、本発明に係わるネットワ
ークデータルーティング回路において使用される内容ア
ドレス可能メモリ（ＣＡＭ）回路１００のブロック図で
ある。ＣＡＭ１００はデータを記憶しかつ新規な方法に
従って比較のためにデータをアクセスする。この機構は
ＣＡＭ１００の部分からヘッダ情報を人為的に排除する
ことなくアクセス時間を低減する。ＣＡＭ１００はこれ
によってそのメモリの使用において高速でありかつ効率
的である。さらに、ＶＣＣまたはＶＰＣ整合のための各
々の個々の比較は開示された発明の第２の面によって加
速される。
【００１６】図１を参照して説明を続けると、ＣＡＭ１
００はメモリワードのアレイ１０１、比較回路１０５、
２進サーチ論理回路１０４、およびエントリキュー１０
６を具備する。ＣＡＭ１００は基準ワードの内容に基づ
き出力ワードを提供するために端子１２０に出力を有す
る。ここで使用されているように、用語「端子（ｔｅｒ
ｍｉｎａｌ）」は単一の導電ラインに言及しかつまた複
数の導電ラインを含むバスラインを含む。ＣＡＭ１００
はデスティネイションヘッダ信号または他の伝送された
データをネットワークから受けるための入力を端子１２
１に有する。基準ワードは前記デスティネイションヘッ
ダ信号の一部として伝送される。
【００１７】メモリワードのアレイ１０１はスタティッ
クＲＡＭセルのコアを備えかつ整合ワードテーブル１０
２およびリンクワードテーブル１０３として構成され、
それによって各々のロケーションアドレスにおいて記憶
されたメモリワードが整合ワードおよび関連するリンク
ワードから構成されるようにされる。１つの実施形態で
は、各々のスタティックＲＡＭセルは４つのトランジス
タからなりかつ５ナノセカンドのアクセス時間を有す
る。用途に応じて、メモリワードのアレイ１０１はこれ
に代えてダイナミックＲＡＭまたはフラッシュメモリか
ら構成できる。端子１２４における入力は前記アレイか
らメモリワードを選択するロケーションアドレス信号を
受信し、かつ端子１２２および１２３における第１およ
び第２の出力はそれぞれ選択された整合ワードおよびリ
ンクワードを提供する。
【００１８】比較回路１０５はそれぞれ基準ワードおよ
び選択された整合ワードを受けるたに端子１２１および
１２２において第１および第２の入力を有し、かつ５つ
の出力信号、「より大きい（ＧＲＥＡＴＥＲ）」信号、
「等しい（ＥＱＵＡＬ）」信号、「ＶＣＣ整合（ＶＣＣ
ＭＡＴＣＨ）」信号、「ＶＰＣ整合（ＶＰＣＭＡＴＣ
Ｈ）信号」、および「ＶＰＣ有効（ＶＰＣＶＡＬＩ
Ｄ）」信号を提供するための出力を端子１２５に有す
る。比較回路１０５は基準ワードおよび前記選択された
整合ワードの内容を比較しかつその比較の論理的結果に
対応する出力信号を肯定する。例えば、もし入力基準ワ
ードが選択された整合ワードより大きければ、比較器１
０５は「より大きい」信号を肯定する。ＶＣＣおよびＶ
ＰＣ整合に対してはそれぞれ前記「ＶＣＣ整合」および
「ＶＰＣ整合」が肯定される。もしＶＰＣ整合が存在す
れば、比較器１０５は「ＶＰＣ有効」信号を肯定する。
比較器１０５および「より大きい」信号、「等しい」信
号、「ＶＣＣ整合」信号、「ＶＰＣ整合」信号、および
「ＶＰＣ有効」信号については図８および図１０を参照
して後に説明する。
【００１９】前記エントリキュー１０６はテーブル更新
のために基準ワードを受信する。ＣＡＭ１００に加えら
れるべき基準ワードまたはＣＡＭ１００から削除される
べき基準ワードはバッファリングされる。いくつかの実
施形態では、エントリキュー１０６におけるバッファリ
ングされたエントリ（ｂｕｆｆｅｒｅｄ ｅｎｔｒｉｅ
ｓ）は整合ワードテーブルをサーチする前に直線的にま
たはリニアに（ｌｉｎｅａｒｌｙ）サーチされる。整合
ワードテーブルをサーチする方法はすぐ後に説明する。
さらに別の実施形態では、エントリキュー１０６は除去
されかつ基準ワードがＣＡＭが利用可能になるや否やソ
ートされる。
【００２０】前記２進サーチ論理回路１０４は整合ワー
ドテーブル１０２の２進サーチを行い整合ワードテーブ
ル１０２におけるエントリが基準ワードと同じ内容を有
するか否かを判定する。２進サーチはサーチされるべき
テーブルが所定の順序にソートされる必要がある。従っ
て、システムのスタートアップ時に、かつ基準ワードを
受け入れる前に、メモリワードのアレイ１０１は整合ワ
ードテーブル１０２のエントリに基づき所定の順序にソ
ートされる。示された実施形態では、最も小さな基準ワ
ードを有する基準ワード−リンクワード対がメモリワー
ドのアレイ１０１の最初のエントリに記憶され、第２に
小さな基準ワードを有する基準ワードがメモリワードの
アレイの第２のエントリに格納されるなどとなる。
【００２１】理論上は、整合ワードテーブルは任意の所
定の順序にソートすることができる。しかしながら、こ
の順序は比較回路１０５によって認識することができ、
従ってそれがある与えられた基準ワードを選択された整
合ワードと比較するときにそれが整合する整合ワード
が、もしそれが整合ワードテーブル１０２に見出される
べきであれば、前記選択された整合ワードよりもより高
いまたはより低いアドレスを有するか否かを決定できな
ければならない。
【００２２】図２は、２進サーチ論理回路１０４によっ
て使用されて基準ワードに整合する整合ワードが格納さ
れているかを判定するためにメモリワードのアレイ１０
１を２進サーチするための２進サーチアルゴリズムのＣ
ＡＭ構成の流れ図である。整合テーブルは予め、例え
ば、ローからハイへと増大するロケーションアドレスで
ソートされているものと仮定する。ステップ２０１にお
いて、基準ワードが、例えば、ネットワークバスから受
信される。ステップ２０２において、メモリアレイの中
間点（ｍｉｄｐｏｉｎｔ）に対応するロケーションアド
レスがアレイから整合ワードおよび関連するリンクワー
ドを選択するために提供される。ステップ２０３は選択
された整合ワードを基準ワードと比較する。もしそれら
が等しければ、（ステップ２０４）、選択されたリンク
ワードがステップ２０５においてＣＡＭの出力に提供さ
れかつ２進サーチは終了する。
【００２３】もし選択された整合ワードが基準ワードに
等しくなければ（ステップ２０４）、２進サーチ論理回
路はステップ２０６においてアレイ全体が既に基準ワー
ドと比較されたか否かを判定する。もしメモリワードの
アレイ１０１全体がまだテストされていなければ、基準
ワードと整合する整合ワードが検出される可能性のある
メモリアレイのハーフ（ｈａｌｆ）の中間点に対応する
新しいロケーションアドレスが提供される。ステップ２
０３および２０４による各々の比較の後にメモリの半分
が整合する整合ワードを含む可能性からはずされ、それ
はメモリアレイの所定の順序への前もってのソートのた
めである。従って、２進サーチの各々のサイクルはメモ
リアレイのテストされていない部分の半分を累進的に低
減する。
【００２４】もしステップ２０６が整合する整合ワード
が検出されることなくメモリアレイ全体がテストされた
ことを判定すれば、ステップ２０７においてエラーフラ
グが出力にセットされかつ２進サーチが終了する。しか
しながら、もしメモリアレイの一部がテストするために
残っておれば、ステップ２０８においてメモリアレイの
テストされていない部分の中間点に対応する新しいロケ
ーションアドレスが提供される。新しいロケーションア
ドレスはステップ２０２において新しい整合およびリン
クワードを選択しかつこのサイクルは２進サーチが終了
するまで反復する。
【００２５】図１に戻ると、２進サーチ論理回路１０４
はメモリワードのアレイにロケーションアドレス信号を
提供するための第１の出力を端子１２４に有する。２進
サーチのいずれかのサイクルにおいて、ロケーションア
ドレスはメモリワードのアレイ１０１のテストされてい
ない部分の本質的に中間点となるよう選択される。も
し、一般的にあるように、整合ワードテーブルにおいて
偶数のエントリがあれば、正確な中間点のロケーション
アドレスはなく、従って次のより高いまたはより低いロ
ケーションアドレスが選択され、すなわち、アレイの上
部ハーフの最も低いアドレスが選択される。
【００２６】このロケーションアドレス信号がメモリワ
ードのアレイ１０１によって受信されたとき、選択され
た整合ワードおよび選択されたリンクワードがそれぞれ
端子１２２および１２３における第１および第２の出力
に生成される。選択された整合ワードは比較回路１０５
において基準ワードと比較され、該比較回路１０５は比
較の結果に対応する出力信号を生成する。該出力信号は
比較の６つの結果の内の１つを指示し、すなわち第１に
基準ワードおよび整合ワードが等しいこと、第２により
高いロケーションアドレスにおいてサーチを継続するこ
と、および第３により低いロケーションアドレスにおい
てサーチを継続すること、および第４にもしＶＰＣが生
じればサーチを終了すること、および第５にもしＶＣＣ
が発生すればサーチを終了すること、および第６に比較
器１０５が前記「ＶＰＣ有効」信号を肯定しこれは出力
論理ピンに伝搬することがある。
【００２７】２進サーチ論理回路１０４は比較回路１０
５から出力信号を受ける端子１２５に第１の入力を有す
る。端子１２３における第２の入力はリンクワードテー
ブル１０３から選択された整合ワードに関連する選択さ
れたリンクワードを受信する。もし前記基準および選択
された整合ワードの内容が等しければ、２進サーチ論理
回路１０４はその端子１２０におけるその出力に選択さ
れたリンクワードを生成し、これはＣＡＭ１００の出力
に結合される。ＣＡＭ１００の出力は従って選択された
リンクワードを含み、多分フラグビットを加えて整合が
首尾よく行われたことを指示する。限定的なものではな
いが、サーチの数、サーチの時間量、およびＣＡＭ内の
首尾よいヒットの割合を含む他の情報をＣＡＭ１００の
出力に提供することもできる。
【００２８】もし基準および選択整合ワードが整合しな
ければ、比較回路１０５からの出力信号は整合する整合
ワードが、もしそれが整合ワードテーブル１０２に格納
されておれば、前記中間点のローケションアドレスより
上に位置するかあるいは下に位置するかを示す。もし、
例えば、比較回路１０５がサーチが前の中間点のロケー
ションアドレスより上の整合ワードテーブル１０２のハ
ーフにおいて継続すべきことを示しておれば、２進サー
チ論理回路１０４は今テストした領域のすぐ上の整合ワ
ードテーブルの領域の中間点において新しいロケーショ
ンアドレスを提供する。該新しい中間点のロケーション
アドレスに対応する新しい整合ワードは前記基準ワード
と比較されかつサイクルそれ自体が反復する。
【００２９】２進サーチにおいて、新しい整合ワードに
対する基準ワードの各々の比較は整合を生じるかあるい
は整合が検出できる可能なロケーションアドレスとして
の整合ワードテーブル１０２の半分を除去する。引き続
くサイクルが効果的に整合ワードテーブル１０２の残り
の部分をそれが新しいテーブルであるかのように処理
し、メモリワードのアレイ１０１の残りの部分の中間点
に対応する新しいロケーションアドレスを送る。
【００３０】２進サーチの各々のサイクルを完了するた
めに必要な時間は一般にメモリワードのアレイ１０１を
含むスタティックＲＡＭコアの速度によって決定され
る。メモリワードのアレイ１０１が４，０９６のメモリ
エントリの深さである実施形態では、各サイクルを完了
するのに必要な時間は１０ナノセカンドである。４，０
９６メモリワードを１つのメモリワードに低減するため
に１２の引き続くバイセクション（ｂｉｓｅｃｔｉｏｎ
ｓ）が必要であり、メモリワードのアレイ１０１は多く
ても１２のサイクルで２進サーチすることができる。従
って完全なサーチは１２０ナノセカンドで完了する。１
６，３８４メモリワードの容量を有するメモリワードの
アレイ１０１に対しては、２つの付加的な２進サーチサ
イクルを提供しなければならず、従ってサーチは１４０
ナノセカンドで完了する。
【００３１】２進サーチは基準ワードと整合する整合ワ
ードが検出されることなく完了することもあり得る。そ
の場合、ＣＡＭ１００の出力に何らのリンクワードも提
供されず、かつ整合が検出されなかったかあるいはサー
チが完了したことを示すエラーフラグビットが一般に提
供される。
【００３２】いくつかの用途においては、新しいエント
リを含めるためあるいはもはや有用でないエントリを削
除するため整合ワードテーブル１０２およびリンクワー
ドテーブル１０３を更新することが必要である。このた
め、２進サーチ論理回路１０４は新しいエントリを受け
るために端子１２１に接続された第３の入力を有する。
もしメモリワードのアレイ１０１が満杯でありかつ存在
するエントリが削除できなければ、新しいエントリはこ
れ以上処理されることはなく、かつ新しいエントリが受
け入れられないことを示すためにエラービットが出力ワ
ードにおいてセットされる。
【００３３】もしメモリワードのアレイ１０１が空きの
ロケーションを有しておれば、新しいエントリが受け入
れられかつ挿入される。新しいエントリはメモリワード
のアレイ１０１の所定の順序を保つように挿入されなけ
ればならないことに注意を要する。１つの実施形態で
は、２進サーチ論理回路１０４は前記空きのロケーショ
ンで開始し、すなわちメモリワードのアレイ１０１の最
上部で開始し、かつ該新しいエントリおよびメモリワー
ドのアレイ１０１の所定の順序を維持する必要性に照ら
して記憶されたメモリワードを調べる。前記新しいエン
トリはそうすることが前記所定の順序を維持する場合に
は前記空きのロケーションに挿入される。２進サーチ論
理回路１０４は新しいエントリの適切なロケーションを
決定する。
【００３４】これに対し、もしＣＡＭ１００が前記挿入
プロセスの間にアイドルであれば、４，０９６ワードの
深さであるメモリワードのアレイ１０１は新しいエント
リを正しいロケーションに挿入するために平均で約２０
マイクロセカンド、最悪の場合約４０マイクロセカンド
を必要とする。
【００３５】図３は、本発明に係わる非同期転送モデル
（ＡＴＭ）セル３００を示す。ＡＴＭセルはヘッダ３０
２を含み、該ヘッダ３０２はそれ自体で交換ネットワー
クのためのルーティング情報を含む。ヘッダ３０２の情
報は端子１２１を介して図１の比較器１０５に入力され
る。前記交換識別子はデータパケットをヘッダ３０２に
含まれるＶＣＩおよびＶＰＩに基づき導く。バイト１は
包括的なフロー制御（ｇｅｎｅｒｉｃ ｆｌｏｗ ｃｏ
ｎｔｒｏｌ）（以後“ＧＦＣ”と称する）のための４ビ
ットおよびユーザネットワークインタフェース（以後
“ＵＮＩ”と称する）プロトコルにおけるＶＰＩのため
の４ビットを含む。しかしながら、ネットワーク・ネッ
トワークインタフェース（以後“ＮＮＩ”と称する）プ
ロトコルにおいては、バイト１はＶＰＩのために８ビッ
トを含む。バイト２はＶＰＩのために４ビットを含みＶ
ＣＩのために４ビットを含む。バイト３はＶＣＩのため
に８ビットを含む。バイト４は、ＵＮＩおよびＮＮＩプ
ロトコルの双方に対して、ＶＣＩのために４ビットを含
みかつペイロードタイプ識別子（ｐａｙｌｏａｄ ｔｙ
ｐｅ ｉｄｅｎｔｉｆｉｅｒ）（以後“ＰＴＩ”と称す
る）のために４ビットを含む。残りのバイトはデータパ
ケットを含む。データパケット（以後「データ」と称す
る）はコンピュータコード、電話通信、または任意の導
かれるべき情報から構成できる。
【００３６】図４は、本発明に係わるＶＣＩおよびＶＰ
Ｉを含む物理チャネル４００を示す。物理チャネル４０
０は光ケーブル、ツイストケーブル、および電話ケーブ
ルのような、物理的なデータ伝送構造を表す。物理チャ
ネル４００はＶＰＣおよびＶＣＣを含み、この場合ＶＰ
ＣおよびＶＣＣは個々のＶＰＩおよびＶＣＩを含む。Ｖ
ＰＣは、すべて同じＶＰＩを備えかつすべて同じ方式で
スイッチングされる、複数の回路のトランクとして概念
化しあるいは概念的に説明することができる。１つのＶ
ＣＣは異なるＶＰＩ内の異なるＶＣＩに導くＶＰＩ内の
１つの特定のＶＣＩである。ＶＣＣおよびＶＰＣのため
のルーティングは図５において後に説明する。この実施
形態では、４，０９６までのＶＰＩが可能でありかつＶ
ＰＩごとに６５，５３６までのＶＣＩが可能である。
【００３７】図５は、本発明に係わるＶＣＣおよびＶＰ
Ｃを含むＡＴＭスイッチ５０７を示す。ＡＴＭスイッチ
５０７は複数の入力パスを受け入れかつ種々のデータを
備えた複数の出力パスを発生する。ＡＴＭスイッチ５０
７は入力および出力パス内のデータを処理しかつパスの
ルーティングは瞬時的に（急速に：ｏｎ ｔｈｅ ｆｌ
ｙ）行われる。ＡＴＭスイッチ５０７は複数の物理チャ
ネル４００を備えた交換ネットワークを示している。１
つの例では、ＡＴＭスイッチ５０７は物理チャネル５０
１、物理チャネル５０２、および物理チャネル５０３を
受け入れる。ＡＴＭスイッチ５０７は個々のヘッダ３０
２に基づき入力セル、ＶＣＩおよびＶＰＩ、を物理チャ
ネル５０４、物理チャネル５０５、および物理チャネル
５０６に導く。
【００３８】ＣＡＭ１００はヘッダ３０２におけるＶＰ
ＩおよびＶＣＩをＣＡＭ１００におけるＶＰＩおよびＶ
ＣＩエントリと比較する。もしＶＰＩおよびＶＰＣを識
別するＣＡＭ１００内の特別のＶＣＩ値に対する整合が
生じればＶＰＣが存在する。整合データはＡＴＭスイッ
チ５０７にデータをどこに導くかおよびヘッダ３０２に
おけるデータのすべてまたは一部をどのように変換する
かを通知する。
【００３９】１つの例では、物理チャネル５０１は５の
ＶＰＩ値を含み、１のＶＣＩ値、２のＶＣＩ値、および
３のＶＣＩ値を備えている。ＣＡＭ１００は整合ワード
テーブル１０２をサーチしかつＶＰＣを識別する特別の
ＶＣＩ値と上のＶＰＩおよびＶＣＩに対する整合が生じ
る。整合ワードに関連するリンクワードは７のＶＰＩに
対する変換値を含む。ＡＴＭスイッチ５０７は物理チャ
ネル５０１を物理チャネル５０４に導きかつＶＰＩ値を
５から７に変換するが、ＶＣＩは１，２および３の値を
保持する。従って、ＶＰＣに対しては、ＶＰＩ値は変換
されるがＶＣＩ値は同じ値に留まっている。
【００４０】他の例では、物理チャネル５０２は１のＶ
ＰＩ値を含み、１のＶＣＩ値、２のＶＣＩ値、および３
のＶＣＩ値を、ヘッダ３０２に備えている。ＣＡＭ１０
０は整合ワードテーブル１０２をサーチしかつＶＰＩお
よびＶＣＩ値の双方に対して整合が生じ、ＶＣＣを生じ
る。整合ワードに関連するリンクワードは５のＶＰＩに
対する変換値を含みかつ１，２および３のＶＣＩ値に対
してそれぞれ１２，１３および１４のＶＣＩに対する変
換値を含む。ＡＴＭスイッチ５０７は物理チャネル５０
２を物理チャネル５０６に導きかつＶＰＩ値を１から５
に変換し、かつＶＣＩ値を１，２および３から１２，１
３および１４にそれぞれ変換する。従って、ＶＣＣに対
しては、ＶＰＩ値およびＶＣＩ値の双方が変換される。
【００４１】図６は、フローチャート形式で、ヘッダ３
０２のサーチの知られた方法を示す。ステップ６０１に
おいて、所定の組のＶＰＩおよびＶＣＩ値がヘッダ３０
２におけるデータを導くためにＣＡＭ１００にロードさ
れる。最初のサーチはＶＣＩおよびＶＰＩ値をヘッダ３
０２から読み出すことによって始まる、ステップ６０
２。該最初のサーチはヘッダ３０２におけるＶＰＩおよ
びＶＣＩ値を整合ワードテーブル１０２におけるＶＰＩ
およびＶＣＩ値と比較することによりＶＣＣに対して行
われる、ステップ６０３。ステップ６０４において、Ｖ
ＰＩおよびＶＣＩ値が整合するか否かの判定が行われ
る。もし該判定が真（整合）であれば、ステップ６０５
においてＶＣＣは有効とされる。該ＶＰＩおよびＶＣＩ
値は関連するリンクワードにおいて規定される値に変換
される。しかしながら、前記判定が偽（整合なし）であ
れば、ステップ６０６において、ヘッダ３０２における
ＶＰＩ値を整合ワードテーブル１０２におけるＶＰＩ値
と比較しかつ整合ワードテーブル１０２における特別の
ＶＰＣビットをチェックする。ステップ６０７におい
て、ＶＰＩ値が整合するか否かおよび整合ワードテーブ
ル１０２に特別のＶＰＣビットが存在するかの判定が行
われる。もし該判定が真であれば、ＶＰＣは有効であ
る、ステップ６０８。ＶＰＩ値は関連するリンクワード
において規定された値に変換される。しかしながら、も
し前記判定が偽（整合なし）であれば、サーチは整合な
しに終了する。当業者は容易にこの知られたアルゴリズ
ムは２つの別個のＣＡＭルックアップを必要とし、１つ
のＣＡＭが２回使用されるかあるいは２つのＣＡＭが各
々１度使用されるかを理解するであろう。いずれの場合
も、時間またはシリコンが過剰に使用される。
【００４２】図７は、フローチャート形式で、本発明に
係わるヘッダ３０２のサーチを示す。ステップ７０１に
おいて、ヘッダ３０２におけるデータを導くために所定
の組のＶＰＩおよびＶＣＩ値がＣＡＭ１００にロードさ
れる。示された実施形態では、ＶＣＩおよびＶＰＩ値
は、図１において前に述べたように、増大する数でソー
トされかつ記憶される。しかしながら、開示された発明
の両方の面（ａｓｐｅｃｔｓ）はお互いに独立に実施す
ることができあるいは組合せることができる。両方のサ
ーチは、ステップ７０２において、ヘッダ３０２からＶ
ＣＩおよびＶＰＩ値を読み出すことで始まる。ステップ
７０３は３つの比較からなり、第１の比較はヘッダ３０
２からのＶＰＩを整合ワードテーブル１０２からのＶＰ
Ｉと比較することからなり、第２の比較はヘッダ３０２
からのＶＣＩを整合ワードテーブル１０２からのＶＣＩ
と比較することからなり、第３の比較は整合ワードテー
ブル１０２からのＶＣＩを論理“１”の特別のＶＣＩ値
に対して比較することからなる。
【００４３】引き続くステップ、７０４および７０５、
は直列的に発生するように説明するが、同時に行われ
る。ステップ７０４においては、前記第１の比較（ヘッ
ダ３０２からのＶＰＩが整合ワードからのＶＰＩと等し
い）および前記第２の比較（ヘッダ３０２からのＶＣＩ
が整合ワードからのＶＣＩと等しい）が真（整合）であ
るか否かが判断される。もし該判断が真（整合）であれ
ば、ステップ７０６においてＶＣＣは有効でありかつＶ
ＰＩおよびＶＣＩ値は関連するリンクワードにおける値
に変換される。しかしながら、もし前記判断が偽であれ
ば、ＶＣＣサーチは整合なしに終了する。ＶＰＣサーチ
はヘッダ３０２のＶＰＩ値をＣＡＭ１００における整合
ワードテーブル１０２のエントリのＶＰＩ値と比較しか
つ整合ワードテーブル１０２のエントリにおける特別の
ＶＣＩ値に対してチェックを行う。ステップ７０５にお
いて、ＶＰＩ値が整合しかつ特別のＶＣＩ値が整合ワー
ドテーブル１０２のエントリに存在するかが判定され
る。もしこの判定が真（整合）であれば、ステップ７０
７においてＶＰＣは有効でありかつＶＰＩ値は関連する
リンクワードにおける値に変換される。しかしながら、
もし前記判定が偽であれば、ＶＰＣサーチは整合なしに
終了する。もし前記ＶＰＣが有効であれば、前記「ＶＰ
Ｃ有効」信号は論理ピンを肯定する。
【００４４】ＶＰＣを識別する前記特別のＶＣＩ値は整
合ワードテーブル１０２の初期ロードにおいてセットさ
れかつ任意的なものである。この実施形態では、前記特
別のＶＣＩ値は１６の論理“１”を含む。
【００４５】有効なＶＰＣに対して論理ピンを「ＶＰＣ
有効」信号により肯定することは試験を簡単にしかつエ
ンドユーザによる動作または運用を簡単にする。前記論
理ピンは装置の状態を識別することによりＣＡＭ１００
の試験を簡単にする。装置を適切にテストするためにＶ
ＰＣまたはＶＣＣが有効であるか否かを判定する必要性
が存在する。他の利点はエンドユーザがＶＰＣが有効で
あるか否かを前記ピンにおける論理ハイによって認識す
ることである。システム設計者のような、エンドユーザ
は前記論理ピンを使用して有効なＶＰＣに基づき他のシ
ステム機能をイネーブルまたはディスエーブルする。例
えば、もしシステム設計者が有効なＶＰＣに基づき他の
ＡＴＭスイッチに導く必要があれば、前記論理ピンが制
御回路のためのゲート信号として使用される。前記論理
ピンはシステム設計を簡単にしかつ柔軟性を増大する。
【００４６】図８は、比較器１０５のブロック図を示
す。比較器１０５は３つの比較要素、すなわち比較器１
０６、比較器１０７、および比較器１０８、そしてＡＮ
Ｄゲート１０９およびＡＮＤゲート１１０から構成され
ている。比較器１０５は端子１２１に基準ワードをそし
て端子１２２に整合ワードを受信する。この実施形態で
は、基準ワードはヘッダ３０２である。比較器１０６は
１つの入力に１６ビットのＶＰＩ、すなわちヘッダ３０
２からの１２ビット（バイト１およびバイト２のビット
５：８）および４ビット、を受ける。４ビットはマスク
により最上位ビットとして加えられ、かつユーザ定義さ
れる。前記４ビットを加えることは図１０において後に
説明する。４ビットは各々の比較要素が同じ１６ビット
の比較器の設計で実施できるようにする。比較器１０６
は他の入力に１６ビットのＶＰＩ、すなわち整合ワード
からの１２ビットおよび４ビット、を受ける。４ビット
はマスクにより最上位ビットとして加えられ、かつユー
ザ定義される。比較器１０７は１つの入力にヘッダ３０
２からの１６ビットのＶＣＩを受ける。比較器１０７は
他の入力に整合ワードからの１６ビットのＶＣＩを受け
る。比較器１０８は一方の入力に１６ビットのＶＣＩを
整合ワードから受ける。比較器１０８は他の入力に特別
の１６ビットのＶＣＩ値を受ける。
【００４７】ＶＰＩＨはヘッダ３０２からのＶＰＩを示
し、ＶＰＩＭは整合ワードからのＶＰＩを示し、ＶＣＩ
Ｈはヘッダ３０２からのＶＣＩを示し、ＶＣＩＭは整合
ワードからのＶＣＩを示す。各々の比較要素は２つの１
６ビット入力が等しいか否かをビットごとの比較で判定
する。比較器１０６の出力はもし２つのＶＰＩ入力が等
しければ「イコール１（ＥＱＵＡＬ１）」を発生する。
比較器１０７はもし２つのＶＣＩ入力が等しければ「イ
コール２（ＥＱＵＡＬ２）」信号を発生する。比較器１
０８の出力はもし２つのＶＣＩ入力が等しければ「イコ
ール３（ＥＱＵＡＬ３）」信号を発生する。
【００４８】ＡＮＤゲート１０９は１つの入力に前記
「イコール１」信号を受けかつ他の入力に前記「イコー
ル２」信号を受信する。ＡＮＤゲート１１０は１つの入
力に前記「イコール１」信号を受けかつ他の入力に前記
「イコール３」信号を受ける。ＡＮＤゲート１０９の出
力は「ＶＣＣ整合」信号を発生する。ＡＮＤゲート１１
０の出力は前記「ＶＰＣ整合」信号および前記「ＶＰＣ
有効」信号を発生する。
【００４９】比較要素、比較器１０６、比較器１０７お
よび比較器１０８、はＶＰＣまたはＶＣＣが存在するか
否かを判定する。ヘッダ３０２からのＶＰＩおよびＶＣ
Ｉ情報および整合ワードテーブル１０２からの整合ワー
ドを比較することにより、各々の比較要素は入力が等し
いか否かを判定する。もしヘッダ３０２からのＶＰＩお
よび整合ワードがビットごとのベースで同じであれば
「イコール１」信号は論理“１”である。もしヘッダ３
０２からのＶＣＩおよび整合ワードがビットごとのベー
スで同じであれば「イコール２」は論理“１”である。
もし整合ワードからのＶＣＩおよび前記特別のＶＣＩが
ビットごとのベースで同じであれば「イコール３」は論
理“１”である。ＡＮＤゲート１０９の出力、「ＶＣＣ
整合」信号、はもしＶＣＣが存在すれば論理“１”であ
る。ＡＮＤゲート１１０の出力、「ＶＰＣ整合」信号お
よび「ＶＰＣ有効」信号、はＶＰＣが存在すれば論理
“１”である。比較器１０８は比較器１０６および比較
器１０７がそれぞれ「イコール１」および「イコール
２」を発生するよりも早く「イコール３」を発生する。
「イコール（ＥＱＵＡＬ）」信号は２ビットを含み、１
ビットは「イコール１」を表しかつ１ビットは「イコー
ル２」を表す。「イコール１」および「イコール２」信
号の発生については図１０においてより詳細に説明す
る。前記特別のＶＣＩ値は１６の論理“１”を含み、従
って比較器１０８は整合ワードからのＶＣＩを論理
“１”につきチェックする。比較器１０６および比較器
１０７は論理“１”および論理“０”に対する両方の入
力を比較する必要があり、比較器１０８は整合ワードか
らのＶＣＩを論理“１”についてチェックするのみであ
り、従って、比較器１０６および比較器１０７よりも高
速で比較を行う。
【００５０】図９は、比較器１０８の回路図を示す。比
較器１０８は整合ワードから１６ビットのＶＣＩを受け
かつ前記特別のＶＣＩ値とビットごとの比較を行う。こ
の実施形態では、前記特別のＶＣＩ値はオール論理
“１”を含む。従って、比較器１０８は整合ワードから
の１６ビットのＶＣＩを論理“１”につきチェックす
る。ＮＡＮＤゲート１１２は整合ワードのＶＣＩから４
ビット、ビット０，１，２および３、を受信する。ＮＡ
ＮＤゲート１１４は整合ワードのＶＣＩから４ビット、
ビット４，５，６および７、を受信する。ＮＡＮＤゲー
ト１１６は整合ワードのＶＣＩから４ビット、ビット
８，９，１０および１１、を受信する。ＮＡＮＤゲート
１１８は整合ワードのＶＣＩから４ビット、ビット１
２，１３，１４および１５、を受信する。ＮＯＲゲート
１２０はＮＡＮＤゲート１１２の出力、ＮＡＮＤゲート
１１４の出力、ＮＡＮＤゲート１１６の出力、およびＮ
ＡＮＤゲート１１８の出力を受ける。ＮＯＲゲート１２
０の出力は前記「イコール３」信号を発生する。
【００５１】比較器１０８の動作は特別のＶＣＩ値に対
して論理“１”を使用することにより論理を最小にする
ことに基づいている。比較を単純化することにより、比
較器１０８は整合ワードからのＶＣＩを論理“１”につ
いてチェックする。「イコール３」信号はもし整合ワー
ドからのＶＣＩが論理“１”から構成されておれば論理
“１”である。他の実施形態では、比較器１０８は異な
るビットパターンにつきテストを行うことができ、ある
いはプログラム可能とすることができる。そのような場
合、比較器１０８は、図１０において以下に説明するよ
うに、比較器１０６および比較器１０７と同様に構成で
きる。
【００５２】図１０は、比較器１０６および比較器１０
７の詳細なブロック図を示す。このブロック図はマスク
可能なＸＯＲブロック１０２２および各々１つまたはそ
れ以上の比較モジュールａ，ｂを備えた一連の比較レベ
ルブロックから構成され、この場合ａおよびｂは整数の
指数またはインデクスであり、ａは１から４におよび、
ｂは０から１５におよぶ。比較レベル１は１６の比較モ
ジュール１，ｊからなり、この場合ｊは０から１５にお
よぶ整数指数である。比較レベル２は８つの比較モジュ
ール２，ｋからなり、この場合ｋは０から７におよぶ整
数指数である。比較レベル３は４つの比較モジュール
３，ｍからなり、この場合ｍは０から３におよぶ整数指
数である。比較レベル４は２つの比較モジュール４，ｎ
からなり、この場合ｎは０から１におよぶ整数指数であ
る。前記マスク可能ＸＯＲブロック１０２２はヘッダ３
０２から１６ビットのＶＰＩを、整合ワードから１６ビ
ットのＢＰＩを、ヘッダ３０２から１６ビットのＶＣＩ
を、そして整合ワードから１６ビットのＶＣＩを、そし
てマスクバスを受ける。
【００５３】マスク可能ＸＯＲブロック１０２２はＶＰ
ＩＨのすべてのビットをＶＰＩＭのすべてのビットと、
一度に２ビットずつ、比較する。また、マスク可能ＸＯ
Ｒブロック１０２２は、一度に２ビットずつ、ＶＣＩＨ
のすべてのビットをＶＣＩＭのすべてのビットと比較す
る。マスク可能ＸＯＲブロックはＶＰＩＨおよびＶＰＩ
Ｍの２つの最上位ビットを比較しかつその結果を比較モ
ジュール１，１５に出力する。マスク可能ＸＯＲブロッ
クはＶＰＩＨおよびＶＰＩＭの次の２つの最上位ビット
を比較しかつその結果を比較モジュール１，１４に出力
する。比較モジュール１，８はＶＰＩＨおよびＶＰＩＭ
の２つの最下位ビットの比較結果を受ける。同様の方法
で、マスク可能ＸＯＲブロックはＶＣＩＨおよびＶＣＩ
Ｍの２つの最上位ビットを比較しかつその結果を比較モ
ジュール１，７へ出力する。比較モジュール１，０はＶ
ＣＩＨおよびＶＣＩＭの２つの最下位ビットの比較結果
を受信する。マスク可能ＸＯＲブロック１０２２によっ
て８つの信号が発生されビットごとのベースで比較され
た４つのビットの結果およびその結果の補数を表しかつ
比較レベル１における比較モジュールに提供される。
【００５４】比較レベル１における比較モジュール
１，ｊ（８≦ｊ≦１５に対して）は８つの入力、ＶＰＩ
ＧＨ（ｊ），ＶＰＩＧＨ（ｊ−１），ＶＰＩＧ
Ｍ（ｊ），ＶＰＩＧＭ（ｊ−１）および４つの前の信号
の補数をマスク可能ＸＯＲブロック１０２２から受け
る。比較レベル１における比較モジュール１，ｊ（０≦
ｊ≦７に対して）は８つの入力、ＶＣＩＧＨ（ｊ），Ｖ
ＣＩＧＨ（ｊ−１），ＶＣＩＧＭ（ｊ），ＶＣＩＧ
Ｍ（ｊ−１）および前記４つの信号の補数をマスク可能
ＸＯＲブロック１０２２から受ける。各々の信号はＶＰ
ＩＨおよびＶＰＩＭ、およびＶＣＩＨおよびＶＣＩＭの
間のｊまたはｊ−１に対応する比較を表す。ＶＰＩＧＨ
（ｊ）はＶＰＩＨのｊ番目のビットがＶＰＩＭのｊ番目
のビットより大きいか否かを表す。
【００５５】比較レベル１における各比較モジュールは
４つの出力を表す。比較モジュール１，ｊ（８≦ｊ≦１
５に対し）はＶＰＩＧＨ（ｊ，ｊ−１），ＶＰＩＧ
Ｍ（ｊ，ｊ−１）、および前の２つの信号の各々の補数
を発生しかつそれらを入力として比較レベル２の比較モ
ジュールに供給する。比較モジュール１，ｊ（０≦ｊ≦
７）はＶＣＩＧＨ（ｊ，ｊ−１），ＶＣＩＭ（ｊ，ｊ−
１）、および前の２つの信号の各々の補数を発生しかつ
それらを入力として比較レベル２の比較モジュールに供
給する。
【００５６】比較レベル２の各比較モジュールは比較レ
ベル１における比較モジュール１，ｊの内の２つから８
つの出力を受ける。比較レベル２の各比較モジュールは
４つの出力を発生する。比較モジュール２，ｋ（４≦ｋ
≦７に対して）はＶＰＩＧＨ（ｊ，ｊ−３），ＶＰＩＧ
Ｍ（ｊ，ｊ−３）、および前の２つの信号の各々の補数
を発生しかつそれらを入力として比較レベル３の比較モ
ジュールに供給する。比較モジール２，ｋ（０≦ｋ≦３
に対して）はＶＣＩＧＨ（ｊ，ｊ−３），ＶＣＩ
Ｍ（ｊ，ｊ−３）、および前の２つの信号の各々の補数
を発生しかつそれらを入力として比較レベル３の比較モ
ジュールに供給する。
【００５７】比較モジュール３，ｍ（２≦ｍ≦３に対し
て）はＶＰＩＧＨ（ｊ，ｊ−７），ＶＰＩＧＭ（ｊ，ｊ
−７）、および前の２つの信号の各々の補数を発生しか
つそれらを入力として比較レベル４の比較モジュールに
供給する。比較モジュール３ ，ｍ（０≦ｍ≦１に対し
て）はＶＣＩＧＨ（ｊ，ｊ−７），ＶＣＩＭ（ｊ，ｊ−
７）、および前の２つの信号の各々の補数を発生しかつ
それらを入力として比較レベル４の比較モジュールに供
給する。比較モジュール４，１はＶＰＩＧＨ（ｊ，ｊ−
７），ＶＰＩＧＭ（ｊ，ｊ−７）、および前の２つの信
号の各々の補数を受ける。比較モジュール４，１は「よ
り大１（Ｇｒｅａｔｅｒ１）」および「イコール１（Ｅ
ｑｕａｌ１）」信号を発生する。比較モジュール４，０
はＶＣＩＧＨ（ｊ，ｊ−７），ＶＣＩＭ（ｊ，ｊ−
７）、および前の２つの信号の各々の補数を受信する。
比較モジュール４，０は「より大２（Ｇｒｅａｔｅｒ
２）」および「イコール２（Ｅｑｕａｌ２）」信号を発
生する。
【００５８】図１０の比較器は比較器１０６および比較
器１０７の機能を達成する。図１０の比較器は入力、Ｖ
ＰＩＨ，ＶＰＩＭ，ＶＣＩＨおよびＶＣＩＭの並列比較
によるモジュール手法を使用する。このモジュール手法
（ｍｏｄｕｌａｒ ａｐｐｒｏａｃｈ）の利点は整合す
る負荷との並列比較を含む。整合する負荷は並列比較を
行う安定した、一貫した設計を提供する。他の利点は６
４ビットのマスク可能ＸＯＲはユーザに６４ビットの内
の任意のものを無視しあるいは「マスキング（ｍａｓｋ
ｉｎｇ）」除去する柔軟性を与える。この実施形態で
は、それぞれのビットが比較され、いずれのビットもマ
スク除去されない。
【００５９】図１１は、図１０に示された比較モジュー
ルの回路図を示す。該回路図は図１０における任意の比
較モジュールを表す。比較モジュールはＶＰＩまたはＶ
ＣＩを比較するために使用され、従って回路図はＶＰＩ
またはＶＣＩの双方に対する信号を示す。この回路図へ
の入力は（ｊ−ｐ）ビットを備えて示されており、この
場合ｐは０，１，３または７を表す整数である。図１０
から思い起こすと、比較レベル１および比較レベル２に
おける比較モジュールへの入力は（ｊ−１）であり、比
較レベル３の比較モジュールへの入力は（ｊ−３）であ
り、かつ比較レベル４における比較モジュールへの入力
は（ｊ−７）である。従って、（ｊ−ｐ）は任意の比較
レベルにおける比較モジュールへの任意の入力を表して
いる。同様の方法で、前記回路図の出力は（ｊ−ｑ）で
あり、この場合ｑは整数１，３，７でありかつｑは常に
ｐより大きい。比較レベル４における比較モジュールに
おいては、出力は「より大１」、「より大２」、「イコ
ール１」および「イコール２」である。
【００６０】出力、ＶＣＩＧＭ（ｊ−ｑ）およびＶＰＩ
ＧＭ（ｊ−ｑ）はｐ型トランジスタ１１０２のドレイン
にかつｎ型トランジスタ１１０４のソースに結合され、
かつｐ型トランジスタ１１０８のドレインにおよびｎ型
トランジスタ１１１０のソースに結合されている。トラ
ンジスタ１１０２のソースは電源Ｖｄｄに結合されてい
る。トランジスタ１１０８のソースは容量１１２４の１
つの端子に、ｐ型トランジスタ１１１４のソースおよび
ｐ型トランジスタ１１２０のソースに、そしてトランジ
スタ１１１２のドレインに接続されている。トランジス
タ１１１２のソースは電源Ｖｄｄに接続されている。容
量１１２４の他の端子はグランドＶｓｓに結合されてい
る。トランジスタ１１０４のドレインは容量１１０６の
１つの端子、トランジスタ１１１０のドレインおよびｎ
型トランジスタ１１１６のドレインに、そしてｎ型トラ
ンジスタ１１１８のソースに結合されている。容量１１
０６の他の端子はグランドＶｓｓに結合されている。ト
ランジスタ１１１８のドレインはグランドＶｓｓに結合
されている。トランジスタ１１０４のゲートおよびトラ
ンジスタ１１０８のゲートはＶＣＩＧＭ（ｊ）またはＶ
ＰＩＧＭ（ｊ）の入力に結合されている。トランジスタ
１１０２のゲートはトランジスタ１１１４のゲートにか
つＶＣＩＧＭ（ｊ−ｐ）またはＶＰＩＧＭ（ｊ−ｐ）の
補数の入力に結合されている。トランジスタ１１１０の
ゲートはｎ型トランジスタ１１２２のゲート、トランジ
スタ１１１２のゲート、およびＶＣＩＧＭ（ｊ）または
ＶＰＩＧＭ（ｊ）の入力に結合されている。ｐ型トラン
ジスタ１１２０のゲートはｎ型トランジスタ１１１６の
ゲートにかつ入力、ＶＣＩＧＭ（ｊ−ｐ）またはＶＰＩ
ＧＭ（ｊ−ｐ）に結合されている。出力、ＶＣＩＧ
Ｍ（ｊ−ｑ）またはＶＰＩＧＭ（ｊ−ｑ）、はトランジ
スタ１１２０のドレインにかつトランジスタ１１１６の
ソースに結合され、そしてトランジスタ１１１４のドレ
インにおよびトランジスタ１１２２のソースに結合され
ている。トランジスタ１１２２のドレインはグランドＶ
ｓｓに結合されている。
【００６１】
【発明の効果】以上から、内容アドレス可能メモリ回路
および交換識別子の同時的サーチを実施するための回路
および方法が提供されたことが理解されるべきである。
前記内容アドレス可能メモリ回路は現存する半導体プロ
セス技術によって実施することができかつ半導体ダイ上
に容易に集積される。交換識別子の同時的サーチは１つ
のＣＡＭのみを使用しかつ同時サーチを使用してＶＰＣ
またはＶＣＣを決定する。
【００６２】本発明が特定の実施形態に関して説明され
たが、当業者にはさらに他の修正および改善をなすこと
ができる。例えば、ＡＴＭセルヘッダ３０２の識別情報
の量が増大するに応じてより多くの並列サーチが必要に
なる。例えば、将来のより複雑なネットワークに対する
より大きな帯域幅により、より多くの交換識別子が並列
サーチを必要とする。従って、本発明はより多くの並列
サーチを含むよう拡張できる。従って、本発明は添付の
特許請求の範囲に規定された発明の精神および範囲から
離れることのないすべてのそのような変更を含むことが
理解されるべきである。
【図面の簡単な説明】
【図１】本発明に従って構成された内容アドレス可能メ
モリ回路を示すブロック図である。
【図２】本発明に係わる内容アドレス可能メモリ回路を
実施するための方法を示す流れ図である。
【図３】本発明に係わる非同期転送モード（ＡＴＭ）セ
ルのヘッダを示す説明図である。
【図４】本発明に係わる仮想回路識別子および仮想経路
識別子を含む物理チャネルを示す説明図である。
【図５】本発明に係わる仮想回路接続および仮想経路接
続を含むＡＴＭスイッチを示す説明図である。
【図６】ＡＴＭセルのヘッダサーチの知られた方法を示
す流れ図である。
【図７】本発明に係わるＡＴＭセルのヘッダのサーチを
示す流れ図である。
【図８】本発明に係わる比較器を示すブロック図であ
る。
【図９】図８に示される比較器の詳細を示す回路図であ
る。
【図１０】図８に示される比較器の詳細なブロック図で
ある。
【図１１】図１０に示される２ビット比較器を示す回路
図である。
【符号の説明】
１００ 内容アドレス可能メモリ（ＣＡＭ）回路 １０１ メモリワードのアレイ １０２ 整合ワードテーブル １０３ リンクワードテーブル １０４ ２進サーチ論理回路 １０５ 比較器 １０６ａ エントリキュー １０６，１０７，１０８ 比較器 １０９，１１０ ＡＮＤゲート １１２，１１４，１１６，１１８ ＮＡＮＤゲート １２０ ＮＯＲゲート １０２２ マスク可能ＸＯＲブロック
───────────────────────────────────────────────────── フロントページの続き (72)発明者 マーク・フランクリン アメリカ合衆国テキサス州78759、オース チン、オーク・ノール・ドライブ 11305 (72)発明者 ケニス・ウェイド・ジョーンズ アメリカ合衆国テキサス州78749、オース チン、ジョン・チサム・レーン 6308

Claims (5)

    【特許請求の範囲】
  1. 【請求項１】 内容アドレス可能メモリ（ＣＡＭ）を実
    施する方法であって、 第１のメモリアレイおよび第２のメモリアレイを提供す
    る段階であり、前記第１のメモリアレイは整合ワードを
    備えかつ前記第２のメモリアレイはリンクワードを備え
    るもの、 基準ワードを前記ＣＡＭに提供する段階、 前記第１のメモリアレイを２進サーチして前記基準ワー
    ドに等しい整合ワードを検出する段階、そして前記第２
    のメモリアレイから前記整合ワードに対応するリンクワ
    ードを出力する段階、 を具備することを特徴とする内容アドレス可能メモリ
    （ＣＡＭ）を実施する方法。
  2. 【請求項２】 制御情報の同時サーチのための方法であ
    って、 ヘッダから第１および第２のフィールドを読み取る段
    階、そして並列的に、 １）前記第１のフィールドおよび第１のタグ ２）前記第２のフィールドおよび第２のタグ、そして ３）所定のベクトルを備えた第２のフィールド、を比較
    する段階、 を具備することを特徴とする制御情報の同時サーチのた
    めの方法。
  3. 【請求項３】 前記読み取る段階は、メモリアレイの２
    進インデクシングを行う段階を具備することを特徴とす
    る請求項２に記載の方法。
  4. 【請求項４】 前記第１のフィールドおよび前記第２の
    フィールドはＡＴＭヘッダを含むことを特徴とする請求
    項２に記載の方法。
  5. 【請求項５】 さらに、前記比較する段階に応じて前記
    第１のフィールドおよび前記第２のフィールドを変換す
    る段階を具備することを特徴とする請求項２に記載の方
    法。
JP27655697A 1996-09-27 1997-09-24 同時サーチ内容アドレス可能メモリ回路のための装置および方法 Expired - Fee Related JP4402178B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/722,587 1996-09-27
US08/722,587 US5956336A (en) 1996-09-27 1996-09-27 Apparatus and method for concurrent search content addressable memory circuit

Publications (3)

Publication Number Publication Date
JPH10126422A true JPH10126422A (ja) 1998-05-15
JPH10126422A5 JPH10126422A5 (ja) 2005-06-16
JP4402178B2 JP4402178B2 (ja) 2010-01-20

Family

ID=24902490

Family Applications (1)

Application Number Title Priority Date Filing Date
JP27655697A Expired - Fee Related JP4402178B2 (ja) 1996-09-27 1997-09-24 同時サーチ内容アドレス可能メモリ回路のための装置および方法

Country Status (4)

Country Link
US (1) US5956336A (ja)
EP (1) EP0833257A3 (ja)
JP (1) JP4402178B2 (ja)
CA (1) CA2213961A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7249216B2 (en) 2002-12-12 2007-07-24 Fujitsu Limited Data relay apparatus, content addressable/associative memory device, and content addressable/associative memory device use information search method

Families Citing this family (55)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3003779B2 (ja) * 1997-06-24 2000-01-31 日本電気株式会社 通信システム
JPH11149481A (ja) * 1997-11-19 1999-06-02 Sharp Corp 情報処理装置
US6260166B1 (en) * 1998-06-01 2001-07-10 Compaq Computer Corporation Observability register architecture for efficient production test and debug
US6735773B1 (en) 1998-06-27 2004-05-11 Intel Corporation Method and apparatus for issuing commands to a network processor configured to provide a plurality of APIs
US6311212B1 (en) * 1998-06-27 2001-10-30 Intel Corporation Systems and methods for on-chip storage of virtual connection descriptors
US6728249B2 (en) 1998-06-27 2004-04-27 Intel Corporation System and method for performing cut-through forwarding in an ATM network supporting LAN emulation
US6657959B1 (en) 1998-06-27 2003-12-02 Intel Corporation Systems and methods for implementing ABR with guaranteed MCR
US6604136B1 (en) 1998-06-27 2003-08-05 Intel Corporation Application programming interfaces and methods enabling a host to interface with a network processor
US6603768B1 (en) 1998-06-27 2003-08-05 Intel Corporation Multi-protocol conversion assistance method and system for a network accelerator
US6724767B1 (en) * 1998-06-27 2004-04-20 Intel Corporation Two-dimensional queuing/de-queuing methods and systems for implementing the same
US6658002B1 (en) 1998-06-30 2003-12-02 Cisco Technology, Inc. Logical operation unit for packet processing
US6560610B1 (en) 1999-08-10 2003-05-06 Washington University Data structure using a tree bitmap and method for rapid classification of data in a database
US6542391B2 (en) * 2000-06-08 2003-04-01 Netlogic Microsystems, Inc. Content addressable memory with configurable class-based storage partition
US6526474B1 (en) 1999-10-25 2003-02-25 Cisco Technology, Inc. Content addressable memory (CAM) with accesses to multiple CAM arrays used to generate result for various matching sizes
US6374326B1 (en) * 1999-10-25 2002-04-16 Cisco Technology, Inc. Multiple bank CAM architecture and method for performing concurrent lookup operations
US6853640B1 (en) * 1999-11-19 2005-02-08 Nippon Telegraph And Telephone Corporation Data selection apparatus
US6725326B1 (en) 2000-08-15 2004-04-20 Cisco Technology, Inc. Techniques for efficient memory management for longest prefix match problems
EP1189394A3 (de) * 2000-09-19 2004-01-07 Siemens Aktiengesellschaft Verfahren und Vorrichtung für die Reduzierung von Adressen für ATM-bzw. IP-Netze
DE10058457A1 (de) * 2000-11-24 2002-06-13 Marconi Comm Gmbh Verfahren und Vorrichtung zum Multiplexen von Datenpaketen
KR20020067339A (ko) * 2001-02-16 2002-08-22 삼성전자 주식회사 프레임릴레이망과 비동기전달모드간의 가입자정합방법
US6606681B1 (en) 2001-02-23 2003-08-12 Cisco Systems, Inc. Optimized content addressable memory (CAM)
US6862281B1 (en) 2001-05-10 2005-03-01 Cisco Technology, Inc. L4 lookup implementation using efficient CAM organization
US7002965B1 (en) 2001-05-21 2006-02-21 Cisco Technology, Inc. Method and apparatus for using ternary and binary content-addressable memory stages to classify packets
US7260673B1 (en) 2001-07-20 2007-08-21 Cisco Technology, Inc. Method and apparatus for verifying the integrity of a content-addressable memory result
US6744652B2 (en) 2001-08-22 2004-06-01 Netlogic Microsystems, Inc. Concurrent searching of different tables within a content addressable memory
US7065083B1 (en) 2001-10-04 2006-06-20 Cisco Technology, Inc. Method and apparatus for dynamically generating lookup words for content-addressable memories
US6775737B1 (en) 2001-10-09 2004-08-10 Cisco Technology, Inc. Method and apparatus for allocating and using range identifiers as input values to content-addressable memories
US7210003B2 (en) 2001-10-31 2007-04-24 Netlogic Microsystems, Inc. Comparand generation in a content addressable memory
US6993622B2 (en) * 2001-10-31 2006-01-31 Netlogic Microsystems, Inc. Bit level programming interface in a content addressable memory
US7117300B1 (en) * 2001-12-27 2006-10-03 James David V Method and apparatus for restricted search operation in content addressable memory (CAM) devices
US7401180B1 (en) 2001-12-27 2008-07-15 Netlogic Microsystems, Inc. Content addressable memory (CAM) device having selectable access and method therefor
US7301961B1 (en) 2001-12-27 2007-11-27 Cypress Semiconductor Corportion Method and apparatus for configuring signal lines according to idle codes
US6715029B1 (en) 2002-01-07 2004-03-30 Cisco Technology, Inc. Method and apparatus for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information
US6970971B1 (en) * 2002-01-08 2005-11-29 Cisco Technology, Inc. Method and apparatus for mapping prefixes and values of a hierarchical space to other representations
US6961808B1 (en) 2002-01-08 2005-11-01 Cisco Technology, Inc. Method and apparatus for implementing and using multiple virtual portions of physical associative memories
US7237058B2 (en) * 2002-01-14 2007-06-26 Netlogic Microsystems, Inc. Input data selection for content addressable memory
US6871262B1 (en) 2002-02-14 2005-03-22 Cisco Technology, Inc. Method and apparatus for matching a string with multiple lookups using a single associative memory
US7114026B1 (en) 2002-06-17 2006-09-26 Sandeep Khanna CAM device having multiple index generators
US7177978B2 (en) * 2002-08-10 2007-02-13 Cisco Technology, Inc. Generating and merging lookup results to apply multiple features
US7689485B2 (en) * 2002-08-10 2010-03-30 Cisco Technology, Inc. Generating accounting data based on access control list entries
US7103708B2 (en) * 2002-08-10 2006-09-05 Cisco Technology, Inc. Performing lookup operations using associative memories optionally including modifying a search key in generating a lookup word and possibly forcing a no-hit indication in response to matching a particular entry
EP1530763B1 (en) * 2002-08-10 2018-04-18 Cisco Technology, Inc. Associative memory with enhanced capabilities
US7082492B2 (en) * 2002-08-10 2006-07-25 Cisco Technology, Inc. Associative memory entries with force no-hit and priority indications of particular use in implementing policy maps in communication devices
US7065609B2 (en) * 2002-08-10 2006-06-20 Cisco Technology, Inc. Performing lookup operations using associative memories optionally including selectively determining which associative memory blocks to use in identifying a result and possibly propagating error indications
US7349382B2 (en) * 2002-08-10 2008-03-25 Cisco Technology, Inc. Reverse path forwarding protection of packets using automated population of access control lists based on a forwarding information base
US7441074B1 (en) 2002-08-10 2008-10-21 Cisco Technology, Inc. Methods and apparatus for distributing entries among lookup units and selectively enabling less than all of the lookup units when performing a lookup operation
US7028136B1 (en) 2002-08-10 2006-04-11 Cisco Technology, Inc. Managing idle time and performing lookup operations to adapt to refresh requirements or operational rates of the particular associative memory or other devices used to implement the system
US7941605B1 (en) 2002-11-01 2011-05-10 Cisco Technology, Inc Methods and apparatus for generating a result based on a lookup result from a lookup operation using an associative memory and processing based on a discriminator portion of a lookup word
WO2004054186A1 (ja) * 2002-12-12 2004-06-24 Fujitsu Limited データ中継装置、連想メモリデバイス、および連想メモリデバイス利用情報検索方法
US20040153911A1 (en) * 2002-12-24 2004-08-05 Alon Regev Testing of a CAM
US7680769B2 (en) * 2003-01-14 2010-03-16 International Business Machines Corporation Method of creating a database and search keys and for searching the database
US6988106B2 (en) * 2003-07-09 2006-01-17 Cisco Technology, Inc. Strong and searching a hierarchy of items of particular use with IP security policies and security associations
US7346062B2 (en) * 2003-07-10 2008-03-18 International Business Machines Corporation Apparatus and method to coordinate calendar searches in a network scheduler given limited resources
WO2006103743A1 (ja) * 2005-03-28 2006-10-05 Duaxes Corporation 通信制御装置及び通信制御システム
US8050185B2 (en) * 2005-08-24 2011-11-01 Hewlett-Packard Development Company, L.P. Sampling of network traffic based on CAM lookup

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5317708A (en) * 1990-06-29 1994-05-31 Digital Equipment Corporation Apparatus and method for an improved content addressable memory
DE69330904T2 (de) * 1992-12-04 2002-06-20 At & T Corp., New York Paketnetz-Schnittstelle
WO1994022253A1 (en) * 1993-03-20 1994-09-29 International Business Machines Corporation Method and apparatus for extracting connection information from protocol headers
US5422838A (en) * 1993-10-25 1995-06-06 At&T Corp. Content-addressable memory with programmable field masking
US5414707A (en) * 1993-12-01 1995-05-09 Bell Communications Research, Inc. Broadband ISDN processing method and system
US5467349A (en) * 1993-12-21 1995-11-14 Trw Inc. Address handler for an asynchronous transfer mode switch
US5659697A (en) * 1994-12-14 1997-08-19 International Business Machines Corporation Translation lookaside buffer for faster processing in response to availability of a first virtual address portion before a second virtual address portion

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7249216B2 (en) 2002-12-12 2007-07-24 Fujitsu Limited Data relay apparatus, content addressable/associative memory device, and content addressable/associative memory device use information search method

Also Published As

Publication number Publication date
EP0833257A3 (en) 2000-10-18
EP0833257A2 (en) 1998-04-01
US5956336A (en) 1999-09-21
CA2213961A1 (en) 1998-03-27
JP4402178B2 (ja) 2010-01-20

Similar Documents

Publication Publication Date Title
JP4402178B2 (ja) 同時サーチ内容アドレス可能メモリ回路のための装置および方法
US6161144A (en) Network switching device with concurrent key lookups
US6957272B2 (en) Stackable lookup engines
US7023807B2 (en) Network switching device with pipelined search engines
US5422838A (en) Content-addressable memory with programmable field masking
KR950003656B1 (ko) 멀티플 패킷 목적지를 갖는 패킷 스위칭 회로망과, 패킷 루팅 방법
US5920886A (en) Accelerated hierarchical address filtering and translation using binary and ternary CAMs
US6532229B1 (en) Low cost link aggregation method and system
US6253280B1 (en) Programmable multiple word width CAM architecture
EP0600683B1 (en) Packet network interface
US5893137A (en) Apparatus and method for implementing a content addressable memory circuit with two stage matching
US20030026259A1 (en) Method and apparatus for a four-way hash table
WO1991008633A1 (en) Basic element for the connection network of a fast packet switching node
EP1510045A1 (en) Processing packets based on context indications
JP2003508957A (ja) ネットワーク・プロセッサ処理コンプレックス及び方法
US6570866B1 (en) High-speed flexible longest match retrieval
US6452908B1 (en) Route searching circuit and communication apparatus using the same
US6819671B1 (en) Relay control circuit using hashing function algorithm
US6415354B1 (en) Pipelined methods and apparatus for weight selection and content addressable memory searches
CN112667526B (zh) 一种访问控制列表电路实现方法及其电路
US6327261B1 (en) Translation process for an ATM cell header
US5130976A (en) Batcher and banyan switching elements
US5740172A (en) Method for searching a packet transmission path in a broadband information and communication system
Kartalopoulos An associative RAM-based CAM and its application to broadband communications systems
JPH05191411A (ja) パターン探索方法及び装置

Legal Events

Date Code Title Description
A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20040921

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20040921

A711 Notification of change in applicant

Free format text: JAPANESE INTERMEDIATE CODE: A711

Effective date: 20041217

RD02 Notification of acceptance of power of attorney

Free format text: JAPANESE INTERMEDIATE CODE: A7422

Effective date: 20050722

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20060523

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060822

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20061024

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20070216

A911 Transfer to examiner for re-examination before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20070413

A912 Re-examination (zenchi) completed and case transferred to appeal board

Free format text: JAPANESE INTERMEDIATE CODE: A912

Effective date: 20070622

RD04 Notification of resignation of power of attorney

Free format text: JAPANESE INTERMEDIATE CODE: A7424

Effective date: 20081107

RD03 Notification of appointment of power of attorney

Free format text: JAPANESE INTERMEDIATE CODE: A7423

Effective date: 20081113

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20091029

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: 20121106

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20121106

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20131106

Year of fee payment: 4

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees