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