JP2000512815A - スコアボードスケジューリングを有する非同期転送モードセル処理システム - Google Patents

Abstract

(57)【要約】 非同期転送モード通信システムのセルを処理するための方法および装置。ビット群は、セルの周期的なコンテナのセルタイムスロットのためのスケジューリング状態を示す一次スコアボードを備え、各ビットが対応するセルタイムスロットの使用可能度を示している。接続識別子テーブルは、セルタイムスロットの中の１つ、したがって単一一次スコアボードビットに対応するテーブルの各ロケーションに対して保持されている。セルスケジューリング命令は、ＡＴＭ伝送リンク（１２０）上の仮想接続のための接続ＩＤを指定する。プロセッサは、使用可能なセルタイムスロットに対応するビットが突き止められるまで一次スコアボードを検索し（１２６）、対応するビットをセットすることによって突き止められたセルスロットを予約し（１２８）、対応するロケーションの接続ＩＤを接続ＩＤテーブルに記憶する（１３０）。

Description

【発明の詳細な説明】 スコアボードスケジューリングを有する 非同期転送モードセル処理システム発明の分野 本発明は、一般に非同期転送モード（ＡＴＭ）通信システム、より詳細にはＡ ＴＭ通信システムにおけるＡＴＭセル処理動作に関するものである。関連出願 本出願は、各々がこれとともに同時に出願され、本譲受人に譲渡された下記の 米国特許出願に関連している。すなわち、“多重セル発生源多重化を有する非同 期転送モードセル処理システム（Asynchronous Transfer Mode Cell Processing System With Multiple Cell Source Multiplexing）”，出願第08/647,373号； “ロード多重命令およびメモリライトバックを有する非同期転送モードセル処理 システム（Asynchronous Transfer Mode Cell Processing System With Load M ultiple Instruction and Memory Write-Back）”，出願第08/647,372号；“セ ルバッファスペースギャザリングを有する非同期転送モードセル処理システム（ Asynchronous Transfer Mode Cell Processing System With Cell Buff er Space Gathering）”，出願第08,/647,371号；および“モジュロベース命 令分岐を有する非同期転送モードセル処理システム（Asynchronous Transfer Mo de Cell Processing System With Modulo‐Based Instruction Branchin g）”，出願第08/647,375号。発明の背景 非同期転送モード（ＡＴＭ）通信システムは、音声、データ、ビデオ、 および他の種類のユーザ情報トラフィックの高速、低遅延多重化および交換を支 援するように設計されている。ＡＴＭシステムはユーザトラフィックを固定長の ５３バイトセルにセグメント化する。各セルの５バイトヘッダは、一般的には対 応するセルに関連する仮想チャネル識別子（ＶＣＩ）および仮想パス識別子（Ｖ ＰＩ）を含んでいる。ＶＣＩフィールドおよびＶＰＩフィールドは一緒に、ユー ザがＡＴＭシステムのネットワーク接続をリクエストする場合、確立される仮想 接続（ＶＣ）を識別する。ＡＴＭシステムのこれらのアスペクトおよび他のアス ペクトに関する付加的詳細は、その両方が参照してここに組み込まれる、ＡＴＭ フォーラム、“ＡＴＭユーザネットワークインタフェース仕様（ATM User‐Netw ork Interface Specification）”（１９９４年９月、バージョン３．１）およ び１９９３年、ニューヨーク市のエリスハーウッド社発行のMartin de Prycker 著の文献“非同期転送モード（Asynchronous Transfer Mode：広帯域ＩＳＤＮの ための解決策（Solution for Broadband ISDN）”に見出すことができる。ユー ザトラフィックセルへの使用可能な伝送機会あるいはスロットの割り当ては、一 般にセルスケジューリングと呼ばれる。 １つの可能なＡＴＭセルスケジューリング技術は、所与のＶＣに関してセルを このＶＣに割り当ててＶＣをサービスすべき理想の時間を計算することを必要と する。したがって、ＡＴＭスケジューリングシステムは、スケジュールの記憶テ ーブル、リストもしくは他の種類のスケジュールにおいて、所与のＶＣ Ｘは時 間Ｙでスケジューリングの準備ができている事実を示すことができる。１つある いはそれ以上の他のアクティブＶＣは時間Ｙでサービスすることを予めリクエス トできたために、このようなセルスケジューリングシステムは、一般的には一方 の次元が時間であり、他方の次元が所与の時間にサービスされるようにスケジュ ールされるＶＣのリストであるスケジュールリクエストの２次元リストを必要と する。 このような２次元セルスケジュールに関する重要な問題は、時間だけにもはや 基づいて計算ができないという事実のために特定のＶＣを何時サ ービスするようスケジュールすべきかをスケジューリングシステムが決定するの が困難なことである。これは、任意の所与のスケジューリング時間において任意 の深さのバックアップがある可能性があるためである。結果として、サービスプ ロセッサは、連続するスケジュール時間に遅れて到達することがある。スケジュ ーリングシステムがサービスプロセッサに生じる遅延を認識していたならば、時 間外にスケジュールされているＶＣは、時間的により早くスケジュールすること ができたはずである。例えば、スケジューリングシステムは、遅延を明らかにで きれば、連続セル伝送事象間に必要な経過時間を保持している一方、所定のVCを 時間的により早くスケジュールできたであろう。この２次元スケジューリング技 術は、効率の悪いスケジューリングおよびその結果としてシステムスループット の減少を生じさせる。 従来技術のＡＴＭセルプロセッサは、多数の他の欠点ももつ。例えば、ほとん どの使用可能なセルプロセッサは、一般的には、増加されたスループット速度を もたらすハードワイヤード方式あるいは高度の汎用性をもたらすがスループット 速度の減少の犠牲を払っているプログラム可能な方式のいずれかを利用する。他 の問題は、従来技術のセルプロセッサ方式では、いろいろな異なるＡＴＭ方式の 製品で使用することに適している、共通の、再プログラム可能なアーキテクチャ をシステム設計者が提供できないことである。従来技術のセル処理に関する他の 重大な問題は、静的ランダムアクセスメモリ（ＳＲＡＭ）あるいは他の種類の制 御メモリあるいはシステムメモリからの制御情報にアクセスする際の待ち時間、 可変ビット伝送速度（ＶＢＲ）トラフィックがある場合の一定ビット伝送速度（ ＣＢＲ）トラフィックのスケジューリング、そして、仮想パス（ＶＰ）トンネリ ングのためにサポートを提供することができる従来技術装置の故障(failure)と を含んでいる., 上記から明らかなように、上記の従来技術の問題を避けるよう改良されたＡＴ Ｍセルスケジューリング技術、サービス技術および他の処理技術 が必要とされている。発明の概要 本発明は、ＡＴＭ通信システムにおいて非同期転送モード（ＡＴＭ）セルを処 理する装置および方法を提供する。本発明は、改良されたＡＴＭセルプロセッサ アーキテクチャのみならず改良されたセルスケジューリング技術およびサービス 技術を提供する。本発明によるＡＴＭセルプロセッサは、特に高速ＡＴＭセル処 理用途で使用するのに最適であり、一般的には全ハードワイヤード装置でのみ実 現できる速度でセルスループットを提供できると同時にプログラム可能な装置に 、より向上した汎用性を提供する。本発明によるセルプロセッサに基づく通信シ ステムは、異なる動作パラメータを生じるように容易に構成できるので、ＡＴＭ 規格の変更による影響を比較的受けない。多数のこのような変更は、比較的簡単 なソフトウェアおよび／またはファームウェア変更によって本発明のセルプロセ ッサで実現できる。 本発明の１つの態様はＡＴＭ通信システムにおいてセルを割り当てる方法を含 む。この方法は、一次スコアボードの形で第１のビット群を発生するステップを 含んでいる。一次スコアボードの各ビットは、通信システムの伝送リンクのセル タイムスロットを示し、所与の一次スコアボードビットの値は、対応するセルタ イムスロットが伝送のために使用可能であるか否かを示している。ＡＴＭシステ ムの所与の仮想接続のセルスケジューリングリクエストに応答して、プロセッサ は、目的タイムスロットに対応するビットで開始し、使用可能なタイムスロット に対応するビットが識別されるまでスコアボード上を進む、一次スコアボードの 検索を命令する。使用可能なタイムスロットは、そのとき、識別された一次スコ アボードビットをセットし、識別された一次スコアボードビットに対応するロケ ーションの接続ＩＤテーブルに、仮想接続のための接続識別子（ＩＤ）を記憶す ることによってスケジュールされる。一次スコアボードおよび接続ＩＤ テーブルは、両方共、ＡＴＭセルプロセッサが高速メモリポートを通してアクセ スする外部制御メモリに保持することができる。それとは別に、一次スコアボー ドおよび／または接続ＩＤテーブルは、スケジューリング時間をさらに減らすよ うにＡＴＭセルプロセッサの内部のメモリロケーションのセットに保持でき、そ れによって通信リンクのより高い速度およびより複雑なスケジューリングアルゴ リズムを効率的に実現することが可能になる。 スケジュールされたタイムスロットは、接続ＩＤテーブルでアドレスを指定す る処理命令（servicing instruction）に応じて処理される(serviced)。このロ ケーションの接続ＩＤは、このロケーションに対応する一次スコアボードビット として引き出される。この一次スコアボードビットはプロセッサの割り当てられ たセルフラグレジスタ（ＡＣＦＲ）にコピーされ、それから次のスケジューリン グリクエストのためにそのタイムスロットを解放するよう、このスコアボートは クリアされる。次に、プロセッサは、処理命令に応じて引き出された接続ＩＤに よって識別される仮想接続のために、セルの構築あるいは引き出しを指示し、ス ケジュールされたタイムスロットでＡＴＭリンクを介して伝送するためのセルを 待ち行列に入れる。 本発明の他の態様は、一次スコアボード検索時間を受容できる範囲に制限する 方法を含む。二次スコアボードは記憶ビット群の形で生成され、その結果各二次 スコアボードビットが、一次スコアボードビットの対応するブロックが使用可能 なセルタイムスロットを示すビットを含んでいるかどうかを示している。スケジ ュール命令に応じて一次スコアボードを検索する場合、ＡＴＭセルプロセッサは 、まずスケジュール命令において指定された目的スロットを含む一次スコアボー ドビットのブロックの引き出しおよび検索を命令する。引き出されたブロックに 使用可能なスロットが全くない場合、ＡＴＭセルプロセッサは、使用可能なスロ ットを含む一次スコアボードブロックのロケーションを決定するために二次スコ アボ ードを使用する。ＡＴＭセルプロセッサは、一次スコアボードビットの現ブロッ クへのアクセスと平行して二次スコアボードにアクセスできるので、現ブロック が使用可能なビットを含んでいない場合、ＡＴＭセルプロセッサは使用可能なビ ットを含んでいる一次スコアボードブロックを識別する二次スコアボード情報を 既に有することになる。この並列アクセス機能は検索処理速度を高める。使用可 能なスロットが引き出された一次スコアボードブロックで示される場合、ブロッ クの残りは、このブロックに残っている任意の他の使用可能なスロットがあるか どうかを決定するために検索される。使用可能なスロットが全く残っていない場 合、一次スコアボードブロックに対応する二次スコアボードビットは、ブロック の全てのスロットが使用不可能であることを示すようにセットされる。このよう に、プロセッサは、使用可能なタイムスロットを示すビットを含まない一次スコ アボードの部分すべてを検索するという時間浪費をしない。検索時間は、各二次 スコアボードビットによって示された一次スコアボードの数を適切に選択するこ とによって所望のメモリ読み出しサイクル数に制限される。二次スコアボードは 、セルプロセッサダイサイズを過度に増加させないで、ＡＴＭセルプロセッサの 内部のメモリロケーションのセット内に保持できる。 本発明の他の態様は、トンネリング操作を処理する技術を含む。１つあるいは それ以上の仮想パス接続の各々は、仮想チャネル接続のトンネリングのために一 次スコアボードに１つあるいはそれ以上のセルタイムスロットを確保する。この 一次スコアボードはマスタスコアボードと呼ばれる。仮想パス接続のために確保 されたスロットに対応するマスタスコアボードビットは適切なスケジュール命令 を使用してセットされる。トンネル制御スコアボードと呼ばれる別個の一次スコ アボードは、マスタスコアボード上にロケーションを確保する仮想パス接続の各 々に対して生成される。マスタスコアボード上の予約されていないセルタイムス ロットに対応するビットは、使用不可能性を示すようにセットされるのに対して 、所与 の仮想パス接続のために一次スコアボード上に確保されたセルタイムスロットに 対応するビットはクリアされて使用可能性を示すように、各トンネル制御ボード のビットは構成される。この接続が適切に確保されたビットロケーションに向け られるように、トンネル制御ボードを利用して、対応する仮想パストンネルを使 用する仮想チャネル接続をスケジュールする。 スケジュールされたセルタイムスロットは処理命令を発行ことによって処理さ れる。ＡＴＭセルプロセッサは、所与の仮想接続のためにまさに処理されようと するタイムスロットがトンネル機能を利用する仮想パス接続のために確保された タイムスロットであるかどうかを示すためにローカル制御メモリに駐在するマス タスコアボードのブロックあるいは他の部分をチェックできる。ＡＴＭセルプロ セッサがタイムスロットが仮想パス接続のために確保されたと判定した場合、こ のプロセッサは、対応するトンネル制御スコアボードの対応するタイムスロット をチェックすることによって処理するのはどの仮想チャネル接続であるかを決定 する。接続を処理した後、プロセッサは、予め予約されたバンド幅が伝送リンク 上で使用可能なままであるよ、うに、仮想パス接続用セル時間を再予約するため にマスタスコアボードの現セル時間を再スケジュールする。仮想チャネル接続が さらに処理を必要とする場合、プロセッサは対応するトンネル制御スコアボード でこの接続を再スケジュールする。仮想パス接続のためのマスタ一次スコアボー ドおよび別個のトンネル制御スコアボードの両方を使用することによって、ユー ザは、所与の仮想パス接続のための伝送リンク上で、例えば、多数のマスタスコ アボードビットによって表される一定ビット伝送速度（ＣＢＲ）セルストリーム を予約できると同時に、トンネル制御スコアボードを使用して所与の仮想パス接 続の個別の仮想チャネルのための使用可能なビット伝送速度（ＡＢＲ）接続をス ケジュールすることができる。 本発明の他の態様は、ソフトウェアテーブルへの高速アクセス（ＦＡＳ Ｔ）制御メモリからのデータブロックのバースト転送をもたらし、ロードされた 値についての次の操作から生じた結果を、この値が予め読み出された制御メモリ ロケーションに自動的にライトバックできるロード多重命令を含む。この命令は 、引き出されるデータブロックのＦＡＳＴ制御メモリのアドレス、データブロッ クの第１の検索ハーフワードがロードされるＣＰＵレジスタファイルのデスティ ネーションレジスタ、および引き出される全ハーフワード数を特定する、ＦＡＳ Ｔメモリからのロード多重（ＬＭＦＭ）命令として実行できる。ＬＭＦＭ命令は 、引き出されたハーフワードを受け取るプロセッサレジスタを関連づける情報の 記憶を、そのハーフワードが読み出された制御メモリロケーションに向けさせる リンクフィールドオプションも含む。したがって、自動メモリ更新機能は、例え ば、ＬＭＦＭ命令によって引き出されたハーフワードを受け取る１つあるいはそ れ以上のプロセッサレジスタ上で動作する算術論理演算装置（ＡＬＵ）命令に備 えることができる。この機能は１つあるいはそれ以上のオペランドを供給した制 御メモリロケーションに、対応するＡＬＵ演算の結果がライトバックされること を示す更新メモリ（ＵＭ）フィールドをＡＬＵ命令に含むことによってもたらす ことができる。 本発明の他の態様は、算術演算の結果のモジュロ部分の分岐を可能とするモジ ュロ算術機能である。典型的な実施例では、ＡＬＵ命令は、右側から左側へのビ ット数を指定するモジュロフィールドを含むように修正され、その後の対応する ＡＬＵ演算の結果は切り捨てられる。ゼロ結果の場合の分岐(branch on zero re sult)、非ゼロ結果の場合の分岐(branch on zero no-result)、負の結果の場合 の分岐(branch on negative result)、桁上げの場合の分岐(branch on carry)お よびオーバーフローの場合の分岐(branch on overflow)のような条件付分岐命令 は、ＡＬＵ命令結果のモジュロ部分だけで演算するように構成される。他の実施 例では、条件付分岐は、全部あるいは一部において、例えば、モジュロ部分の最 上位ビット（ＭＳＢ）桁からの桁上げによることができる。 本発明の他の態様は、多数のセルバッファの未使用部分が隣接する仮想メモリ 空間としてアドレス指定できるセルバッファＲＡＭ（ＣＢＲ）メモリ空間収集プ ロトコルである。空間収集プロトコルは、仮想ＣＢＲアドレスに付加された収集 ビットをセットするためにＣＰＵあるいはＡＴＭセルプロセッサの直接メモリア クセス（ＤＭＡ）コントローラを使用できる。ＣＢＲのアドレス発生器は、収集 ビットを検出し、物理アドレスのセット収集ビットを含むこれらの仮想アドレス をＣＢＲメモリ空間に変換する。この変換は、例えば、未使用の８バイトを任意 の所与の６４バイトセルバッファの最下部に到達するように物理アドレスの任意 のビットを所定の状態にセットし、仮想アドレスの任意のビットを物理アドレス の他の桁にシフトさせて、隣接仮想空間においてセルバッファからセルバッファ に移動させる。多重収集空間は、異なる収集ビット数を使用することによって他 の実施例においてもサポートされる。所与の仮想アドレスのセット収集ビットの 位置はＣＢＲメモリサイズに応じて変わり得る。 本発明の他の態様は、スケジューリングリクエストの多重レイヤおよび／また は外部セルソースに有効的に適合する“バブル”カウント技術を含む。スケジュ ーリングリクエストの多重レイヤの場合、第１および第２の一次スコアボードは 、例えば、上位および下位の優先順位トラフィック、高速および低速のセル速度 トラフィック、あるいは外部発生および内部発生のトラフィックのそれぞれのス ケジューリング／処理のために備えられている。バブルカウントは第２のスコア ボードのために保持され、カウントは、第１のスコアボードが処理される度に増 分され、アイドルスロットが第２のスコアボードで見られるが伝送のために待ち 行列に入れられていない度に減少される。したがって、第２のスコアボードのた めのスケジューリングリクエストは、バブルカウントに加えて目的時間に行われ る。外部セルソースおよび内部セルソースを多重化する場合、バブルカウントは 、所与の伝送リンクで送られているが一次スコアボードでスケジュールされてな いセル数を示すことができ、一次スコアボードが処理される度に 増分し、一次スコアボードのアイドルスロットが見られるが伝送のために待ち行 列に入れられていない度に減少することができる。バブルカウント応用のセル処 理は、一次スコアボードの目的アドレスを指定し、セットビットが目的アドレス から目的アドレスおよびバブルカウントの和の範囲にあるかどうかを決定するポ ップレンジ（ＰＯＰＲ）処理命令の使用によって容易にすることができる。 本発明の他の態様は、異なる仮想接続の間における完全な速度の独立性を提供 する能力と、所与の仮想接続がアクティブとみなされる任意の所与の時間に、単 一のスケジュールリクエストのみが一次スコアボートに存在することを必要とす る、本質的にフェアなバンド幅割り当てを提供する能力と、トラフィック優先順 位あるいはセル速度に基づいて多重スコアボードを使用してスケジューリングリ クエストの多重レイヤをサポートする能力と、セルプロセッサによって内部的に 構成され、あるいは検索されるセルと、外部ソースからのセルとの多重化をサポ ートする能力とを含んでいる。 本発明による典型的なセルプロセッサは、目的スロットが占有されている場合 、実際に第２の次元を取り除き、処理リクエストを時間外に押しやることによっ て、２次元セルスケジューリングに関連する前述の問題を解決する。結果として 、各タイムスロットは、通常、単一のリクエストペンディングだけを有し、引き 続くスケジューリング動作は、かなり正確な時間表示を有する。本発明による１ 次元スケジューリング方式は、一般的にセルスケジュールを示す一次スコアボー ドの検索を利用するが、全システムスループット性能が改善されるような効率的 な方法でこのスコアボード検索を実行する技術が本発明によって提供される。例 えば、本発明による典型的なセルスケジューリングシステムは、前述された二次 スコアボードを使用することによって、受容できる制限時間間隔内で、所与の可 能なロケーション範囲内において使用可能なセルロケーションを見出すことがで きる。 本発明の他の長所は、セルプロセッサ内でＣＰＵとともにＡＴＭ固有タスクを 処理するためにいろいろな専用回路を使用できることである。これらの専用回路 は、セルプロセッサＣＰＵからの多数のタイムクリティカル機能を取り除くこと ができ、それによって性能および機能性のレベルがかなり向上する。このような 専用回路の例は、ここではセルスケジューリングシステム（ＣＳＳ）と呼ばれる ハードウェアベースのトラフィック・シェイピング機構である。ＣＳＳは通常セ ルプロセッサＣＰＵによって、要求されたトラフィックパターンに関する指令を 行うが、ＣＳＳはＡＴＭセル処理動作の全てのトラフィック・シェイピング機能 を管理するように構成することができる。これにより、全体のプロセッサスルー プット性能を著しく落とすことなく、アルゴリズムトラフィック・シェイピング の利点をユーザが享受することができる。 本発明の前述の機能および長所は、所与の実施例において、例えば、（１）６ ００Ｍｂ／ｓあるいはそれ以上までの速度で、動作し、（２）使用可能なビット 伝送速度（ＡＢＲ）処理のためのＡＴＭフォーラムトラフィック管理仕様に従っ て動作し、（３）並行定ビット伝送速度（ＣＢＲ）、可変ビット速度（ＶＢＲ） およびＡＢＲの接続を管理する内蔵装置として作動し、それにより他のタスクの ためにホスト処理リソースをフリーにする、（４）トラフィック・シェイピング のアルゴリズム処理に伴う速度ベースおよびカンタム・フロー制御ベースのＡＢ Ｒ処理をサポートし、（５）ＡＴＭレイヤ処理アプリケーションで実行し、（６ ）仮想パストンネリングを実行し、それによって一連のＶＢＲ、ＡＢＲあるいは 未指定ビット伝送速度の接続がＣＢＲ仮想パス接続の中に割り当てできる（tunn eled across）、および／または（７）複数のスコアボードを使用して多重伝送 リンクを同時に管理し、スケジュールし、トラフィック・シェイピングできる、 セルプロセッサに帰する。本発明のこれらおよび多数の他の機能および長所は、 システム設計者にそのＡＴＭ製品のための共通の、再プログラム可能なセルプロ セッサアーキテクチャを提供する。したがって、本発 明は、より低いＡＴＭ製品開発コスト、より短い開発サイクルおよびサポート装 置のコストをかなり削減することができる。図面の簡単な説明 図１Ａは、非同期転送モード（ＡＴＭ）セル処理システムのブロック図である 。 図１Ｂは、図１Ａのセル処理システムで使用するのに適している典型的な制御 メモリ構成を示している。 図２は、本発明によるＡＴＭセルプロセッサの詳細なブロック図である。 図３Ａは、図２のセルプロセッサで使用するのに適している典型的なセルバッ ファＲＡＭ（ＣＢＲ）構成を示している。 図３Ｂおよび図３Ｃは、本発明による典型的なＣＢＲメモリ空間収集プロトコ ルの動作を示している。 図４は、本発明によるセルスケジューリング動作で使用するのに適している典 型的な一次スコアボードおよび接続ＩＤテーブルを示している。 図５は、本発明による典型的なセルススケジューリング操作の動作を示すフロ ー図である。 図６は、本発明による典型的なセル処理操作の動作を示すフロー図である。 図７は、本発明によるセルスケジューリング・処理動作の例を示す図である。 図８は、本発明による二次スコアボードを使用する限定検索を示すフロー図で ある。 図９は、本発明による図２のＡＴＭセルプロセッサで実行できるトンネリング 動作を示す。発明の詳細な説明 本発明は、下記の簡単な輪郭で詳述されるような多数の異なる部分で説明され る。 １． ＡＴＭセル処理システム １．１処理メモリ ２２ ２． ＡＴＭセルプロセッサアーキテクチャ ２．１ 総論 ２．２ 中央処理装置（ＣＰＵ）５０ ２．３ 自動メモリ更新を有するロード多重命令 ２．４ 結果のモジュロ部分の分岐に関するモジュロ演算 ２．５ セルバッファＲＡＭ（ＣＢＲ）５２ ２．６ ＣＢＲメモリ空間収集プロトコル ３． 一次スコアボード／接続ＩＤテーブルを使用するＣＳＳ５６の動作 ４． スケジューリング命令 ４．１ ＰＵＳＨＣ命令 ４．２ ＰＵＳＨＦ命令 ５． 処理命令 ５．１ ＰＯＰＣ命令 ５．２ ＰＯＰＦ命令 ６． セルスケジューリング処理の付加的細部 ６．１ 制限された一次スコアボード検索時間 ６．２ ＣＳＳ命令バッファ ６．３ 一次スコアボードおよび接続ＩＤテーブルのアドレス指定 ６．４ 一次スコアボードの初期設定 ６．５ 一次スコアボードサイズの選択 ６．６ 多重スケジュールの使用 ７． ＣＳＳ動作の例 ８． 二次スコアボードを使用する制限された一次スコアボード検索 ９． ＣＢＳ接続のためのバンド幅の予めの予約 １０．トンネリング １１．完全独立速度 １２．本来公正なバンド幅割り当て １３．スケジュールリクエストの多重レイヤ １４．外部ＡＴＭセル多重化 １つあるいはそれ以上の伝送リンク上の同期転送モード（ＡＴＭ）セルのスケ ジューリングとともにここに示されているけれども、本発明は、任意のバンド幅 割り当て資源上へのセルのスケジューリングに対してより一般的に適用可能であ る。例えば、ファーストイン・ファーストアウト（ＦＩＦＯ）キューは、所与の 実施例においてＡＴＭセルプロセッサと物理的伝送リンクとの間に配置でき、セ ルがリンク上に直接スケジュールされるよりもむしろキューの中にスケジュール される。さらに、セルは、リンク上に直接スケジュールされるよりもむしろＡＴ Ｍ交換機構、バックプレーンあるいは他の適当な装置を通して本発明によりスケ ジューリングできる。したがって、ここに使用されるような用語“伝送リンク” は任意のバンド幅割り当て資源を含み、キュー、交換機構、バックプレーンある いは他の装置がセルプロセッサと物理的伝送リンクとの間に置かれているこれら を含むように広義に解釈されるべきである。本発明はセルストリームをシェイピ ングするためにＡＴＭ交換システムで利用できることにも注目すべきである。例 えば、本発明によるセルスケジュールシステムは、セルが所与のパケットから構 成されるべき時よりもむしろ何時セルが送られるべきかを示すために使用できる 。セルスケジューリングシステムおよび他の関連セル処理要素はＡＴＭセル処理 交換システムの入力あるいは出力のいずれかに置くことができる。 １． ＡＴＭセル処理システム 図１Ａは、本発明による典型的な非同期転送モード（ＡＴＭ）セル処理システ ム１０を示している。このシステム１０は、この実施例では、ホストコンピュー タのホスト中央処理装置（ＣＰＵ）１４と対話するように 構成されているＡＴＭセルプロセッサ１２を含んでいる。セルプロセッサ１２は 、ネットワークインタフェース１６を介してＡＴＭ通信ネットワークを介してＡ ＴＭセルを送受信する。セルプロセッサ１２は、下記により詳細に記載されてい るＵＴＯＰＩＡポートインタフェースを介してネットワークインタフェース１６ と通信できる。ネットワークインタフェース１６は、同期光ネットワーク（ＳＯ ＮＥＴ）インタフェース装置のような物理レイヤ制御装置を示すことができる。 セルプロセッサ１２は、後述されるようにＡＴＭセルを処理するためにシステム メモリ１８、内容参照可能メモリ（ＣＡＭ）２０および制御メモリ２２をアクセ スする。制御メモリ２２は、ここでは高速アクセスソフトウェアテーブル（ＦＡ ＳＴ）制御メモリ、すなわち単にＦＡＳＴメモリとも呼ばれ、制御メモリを使っ てソフトウエアテーブルあるいはセルを処理するためにおよび接続サービスする ために使用される他のデータ構造を保持する。セルプロセッサ１２は、高速ＡＴ Ｍセル処理応用で使用するために設計され、一般的には全ハードワイヤード方式 とのみ関連する速度でセルスループットをもたらすように構成されると同時にプ ログラム可能な装置の汎用性長所をもたらす。例えば、セルプロセッサ１２は、 ６００Ｍｂ／ｓあるいはそれ以上までの速度で作動するように容易に構成される と同時にセルスケジューリングおよびトンネリングのような多数の動作パラメー タの全プログラム可能性をもたらす。セルプロセッサ１２とシステム１０の他の 要素との相互接続は単なる例示であり、多数の代替の構成は所与の応用で利用す ることができることを理解すべきである。 １．１ 制御メモリ２２ 図１Ｂは、ＦＡＳＴ制御メモリ２２の可能な実現をより詳細に示している。こ の典型的な制御メモリは、上部３２ｋ×３２構成部分および下部３２ｋ×３２構 成部分を含んでいる６４ｋ×３２の静的ＲＡＭ（ＳＲＡＭ）のように構成されて いる。ＡＴＭセルプロセッサ１２は、後述される ＦＡＳＴメモリコントローラを介して制御メモリ２２の内容に低呼び出し時間の アクセスができる。制御メモリ２２の内容は、下記により詳細に記載されている 一次スコアボードおよび接続ＩＤテーブルのようなルックアップテーブルのみな らず仮想接続記述子（ＣＤ）、プログラムコード、トラフィック・シェイピング メモリを含んでもよい。上部３２ｋ×３２構成部分は、８ｋバイト受信機リダク ションマップと、８ｋバイトの種々雑多な部分と、３．５ｋバイトの受信ＣＤと を含んでいる。受信ＣＤの各々は、対応する接続のための受信セルを処理するた めにセルプロセッサ１２によって利用される情報を含んでいる。８ｋバイトの種 々雑多な部分は、２５６×１６の一次スコアボードと、３２の使用可能なビット 伝送速度（ＡＢＲ）プロフィールセット、３２の定ビット伝送速度（ＣＢＲ）プ ロフィールセットと、セル間放出間隔（ＩＣＩ）変換テーブルへの送信使用可能 なセル伝送速度（ＡＣＲ）と、ＡＴＭ適合レイヤ５（ＡＡＬ５）セグメンテーシ ョンおよびリアセンブリ（ＳＡＲ）エグゼクティブとを含んでいる。下部３２ｋ ×３２構成部分は、８ｋバイト送信ポインタテーブルと、８ｋバイトの種々雑多 な部分と、３．５ｋバイトの送信ＣＤとを含んでいる。送信ＣＤの各々は、対応 する接続ための送信セルを生成するためにセルプロセッサ１２によって利用され る情報を含んでいる。図１Ｂの典型的な制御メモリ２２は、一次スコアボードの ための空間を含むように示されているけれども、外部メモリよりもむしろセルプ ロセッサ１２のオンチップメモリに一次スコアボードを記憶することは多数の用 途では好ましいこともある。 ２．ＡＴＭセルプロセッサアーキテクチャ ２．１ 総論 図２は、本発明による典型的なＡＴＭセルプロセッサ１２のブロック図である 。セルプロセッサ１２は、ＡＴＭネットワークプロトコルプロセッサの役をする ＣＰＵ５０を含んでいる。ＣＰＵ５０は、５１２×１６の セルバッファランダムアクセスメモリ（ＲＡＭ）５２と、システム１０のＦＡＳ Ｔ制御メモリ２２をアクセスするＦＡＳＴメモリコントローラ５４と、セルスケ ジューリングシステム５６と、外部バス接続部６０を介してシステム状態を供給 するチップ間信号（ＩＣＳ）システムと、プロセッサ命令キャッシュ６２と通信 する。セルプロセッサ１２は、ＳＯＮＥＴインタフェース装置のような物理レイ ヤ（ＰＨＹ）装置を介してＡＴＭネットワークに接続するためのＵＴＯＰＩＡポ ート６４を含んでいる。用語ＵＴＯＰＩＡは、ＡＴＭセルプロセッサ１２のよう なＡＴＭレイヤ装置とＳＯＮＥＴインタフェースのような物理レイヤ装置との間 の通信のためのＡＴＭフォーラムによって規定された標準ハンドシェーク／デー タ転送プロトコルを示す。他のプロトコルは、プロセッサ１２とＡＴＭネットワ ークとをインタフェースするためにも使用できる。セルプロセッサ１２は、高性 能の３２ビットの直接メモリアクセス（ＤＭＡ）インタフェースであってもよい ポート１バスインタフェース６８と、汎用１６ビットＤＭＡインタフェースであ ってもよいポート２バスインタフェース７２とをさらに含んでいる。ポート１イ ンタフェース６８は、バス接続部７０を介してシステム１０のホストＣＰＵに接 続でき、ポート２インタフェース７２は、システム１０のシステムメモリ１８お よび／またはＣＡＭ２０にバス接続部７４を介して相互接続できる。ＣＰＵ５０ は、本発明の譲受人のマサチューセッツ州Walthomのメーカー・コミュニケーシ ョンズＩｎｃによって開発されたソフトワイヤードＡＴＭネットワークプロトコ ル（ＳＷＡＮ（登録商標））プロセッサであってもよい。セルプロセッサ１２は 、用途指向集積回路（ＡＳＩＣ）あるいは他の適当なディジタルデータプロセッ サとして実現できる。典型的な単一パッケージセルプロセッサは、メーカー・コ ミュニケーションズによって開発された部品番号ＭＸ３０１０である。 ２．２ 中央処理装置（ＣＰＵ）５０ 次に、ＣＰＵ５０はより詳細に記載される。ＣＰＵ５０は、簡略命令セット計 算（ＲＩＳＣ）技術による限られた命令セットを使用するように構成されてもよ い。使用された特定な命令は、従来の複合命令セット計算（ＣＩＳＣ）技術も組 み込んでもよく、それによって付加的汎用性をもたらす。ＲＩＳＣプロセッサの パイプライン速度とＣＩＳＣプロセッサの命令セットパワーとを組合せることに よって、ＣＰＵ５０は、約６００Ｍｂ／ｓあるいはそれ以上程度の処理速度で全 ハードワイヤード装置のスループット性能に匹敵するスループット性能を達成す ることができる。ＣＰＵ５０は、ＡＴＭ用途に特に最適な命令およびデータアク セス方法を利用する。例えば、後述されるセルスケジューリング命令プッシュセ ル（ＰＵＳＨＣ）およびセルサービス命令ポップセル（ＰＯＰＣ）は、単一プロ セッサ命令サイクルで複合タスクを始動できるＡＴＭ指向命令である。これらの 専用命令および他の専用命令は、従来技術のＡＴＭ処理システムに対して著しい 性能利得をもたらす。 ＣＰＵ５０は、１６ビットの算術論理演算装置（ＡＬＵ）を含み、ハーフワー ドインクリメントの３２ビットの命令ワードを使用する１６ビットのプロセッサ であってもよい。ここで使用されるような用語“ハーフワード”は、一般に１６ ビットの構造、すなわち３２ビットワードの半分を示しているけれども、ハーフ ワードに関して述べられている本発明のいろいろな態様は、もちろん他のサイズ のデータ構造を利用できる。１６ビットのプロセッサとしてのＣＰＵ５０の構成 は、ＡＴＭセル処理応用で処理される大部分のデータ構造はサイズが１６ビット あるいはそれ以下であり、１６ビットよりも大きいこれらのＡＴＭデータ構造は 、その各々が１６ビットあるいはそれ以下である２つあるいは以上の別個のフィ ールドでしばしば構成されているという事実を利用する。１６ビットプロセッサ は、一般にこれらのＡＴＭデータ構造のより有効な圧縮および処理を可能にし、 高いパイプライン周波数をもたらすと同時に対費用効果を保持する。例えば、Ｃ ＰＵ５０のための全ての非ディスパッチ命令は単一クロッ クサイクルで実行するように設計されてもよい。ＣＰＵ５０は、入力クロック信 号の周波数を２倍にするか、あるいは他の方法で増加させるオンチップ位相ロッ クループ（ＰＬＬ）あるいは他の周波数乗算機構を含んでもよく、それによって ＣＰＵ５０は入力クロック周波数の倍数で作動できる。ＣＰＵ５０は、分岐命令 がサイクル当たり１命令の有効なサイクル速度で作動することを保証する遅延分 岐技術も利用できる。下記により詳細に説明されているＰＵＳＨＣ命令およびＰ ＯＰＣ命令のようなディスパッチ命令は、完了するのに１サイクル以上を一般に 必要とするが、その実行はＣＰＵ５０以外で生じるので、プロセッサ５０はディ スパッチ命令が実行している間機能停止されない。ＡＬＵは、所与のレジスタを 修正する命令の直後に多くの場合にはこの同じレジスタをアクセスする命令があ り得るという点でフィードバックを使用できる。 典型的な実施例のＣＰＵ５０は６４の１６ビットレジスタを含んでいる。これ らのレジスタの３２は汎用レジスタファイルを構成しているのに対して、残りの ３２は専用レジスタあるいはハードウェアレジスタとみなされる。ＡＬＵ命令は 、２つのソースレジスタの内容で作動するか、あるいはソースレジスタの内容お よび即値あるいは使用可能値で作動する。 ＣＰＵ５０のある種のレジスタによって、ＡＴＭセルプロセッサ１２は、ホス トＣＰＵ１４との両方向通信チャネルを実現できる。これらのレジスタは、ホス トＣＰＵ１４がコマンド、状態、アドレスおよび他の情報をプロセッサ１２に書 き込むことができる２つの１６ビットＣＯＭＭＩＮレジスタと、ホストＣＰＵ１ ４がコマンド、状態、アドレスおよびその他の情報をプロセッサ１２から読み出 すことができる２つの１６ビットＣＯＭＭＯＵＴレジスタとを含んでいる。プロ セッサ１２のＣＯＭＭＩＮレジスタおよびＣＯＭＭＯＵＴレジスタはホストＣＰ Ｕ１４によってポート１バスインタフェース５８を介してアクセスされる。 ＣＳＳ構成レジスタはＣＰＵ５０に含められる。ＣＳＳ構成レジスタは、一般 的にはＣＳＳ５６が使用される前にＡＴＭセルプロセッサ１２を 操作させるソフトウェアによって初期設定される。ＣＳＳ構成レジスタは、接続 識別子（ＩＤ）テーブルおよび一次スコアボードの制御メモリ２２のベースアド レスを示している。その両方ともセルスケジューリング動作で使用され、下記に より詳細に記載されている。このレジスタは、所与のスケジューリング動作で使 用されるスコアボードのサイズも示している。 割り当てられたセルフラグレジスタ（ＡＣＦＲ）は、ＣＰＵ５０に含められ、 セルスケジューリング動作およびサービス動作で使用される。例えば、ＡＣＦＲ は、ＰＯＰＣ動作の完了でＣＳＳ５６によってアクセスされる。ＣＳＳ５６は、 ＰＯＰＣ動作によって対象にされたスコアボードビットをＡＣＦＲにコピーし、 それから、ＣＰＵ５０は、ＡＣＦＲを調べリクエストセルが正確にスケジューリ ングされたかどうかを決定できる。 チップ間通信のための機構はＣＰＵ５０によって提供される。外部状態ステー タス装置７６は、ＩＣＳ５８およびＵＴＯＰＩＡポート６４を介して、ＣＰＵ５ ０がプロセッサ１２の外部要素、サブシステム等の状態を検出し、この状態情報 に基づく処理決定を行うことができる信号にアクセスできる。プロセッサ５０は 、ＩＣＳ５８を介して外部要素およびサブシステムに内部状態情報も供給できる 。 多数の条件分岐命令および無条件分岐命令はＣＰＵ５０に備えることができる 。条件分岐命令は、その分岐決定の根拠を外部状態ステータス装置７６を介して ＣＰＵ５０の入力として供給される多数の外部状態信号（ＥＳＳ）の中の１つの 論理状態に置くことができる。ＥＳＳは、適当なセル処理決定を行うためにＣＰ Ｕ５０によって読み出される内部状態信号に接続されている。例えば、分岐命令 は、特定されたＥＳＳが適当な論理状態にセットされている場合に分岐する目的 アドレスを指定できる。ソースファイルの対応する命令ワードの命令フィールド オプションが除外される場合、無条件分岐命令の形式が選択できる。 ＣＰＵ５０は、余分のＣＰＵクロックサイクルが付随するスループットの減少 なしに分岐命令を実行するために供給される遅延分岐と呼ばれ る技術を実行するように構成できる。分岐命令に遭遇すると、コミットスロット 命令（ＣＳＩ）と呼ばれる分岐直後の命令は、取り出され、実行パイプラインに 入力されると同時に分岐命令が処理される。分岐条件が真として評価される場合 あるいは無条件分岐が使用される場合、ネバーエグゼキュート（ＮＥ）演算子が 指定されない限り、目的命令の実行がＣＳＩの実行に続く。ＮＥ演算子は、一般 的に無条件分岐、すなわちＩＦＯが存在しない無条件分岐のみで指定される。分 岐条件が偽と評価される場合、ＣＳＩは、ユーザが分岐を有する条件付実行（Ｃ ）演算子を指定したかどうかに応じて実行されてもよいし、実行されなくてもよ い。存在するならば、Ｃ演算子によって、分岐が行われていない場合、ユーザは ＣＳＩを実行しないと指定できる。どの命令がコミットされた分岐のスロットに 入れることができるかに関するある種の制限を適用できる。例えば、コミットさ れた分岐のスロットは、無条件分岐の形式がＮＥ演算子と併用されない場合、Ａ ＬＵ条件分岐命令あるいは他の分岐命令を含まないように制限することができる 。 ＣＰＵは、ＡＬＵ演算の結果に基づいた分岐決定が結果を使用できる前に行わ れる予測分岐技術を利用するように構成されてもよい。ＣＰＵ５０は、最初に分 岐条件の結果を予測しようと試み、それから予測が真であるならば実行されるサ ブルーチンを実行することによって予測分岐を実行する。ＣＰＵが後で、約２Ｃ ＰＵサイクル〜３ＣＰＵサイクル内に通常行うことができるその予測が正しくな いと決定するならば、ＣＰＵは、望ましくないサブルーチンの実行を終了し、正 しいサブルーチンのプログラム実行を再指令する。本発明の典型的な実施例にお いて、ＡＬＵ条件付分岐機能はＡＬＵ命令の中に取り込まれる。この装置は分岐 オフセットを指定するのに十分な命令ワードのスペースを残すことができないた めに、約４命令ワードの固定分岐オフセットを使用してもよい。例えば、ＣＰＵ が所与の分岐を行うように決定するならば、ＣＰＵは、分岐命令から離れた所の 約４命令の位置に分岐する。分岐が行われない場合、ＣＰＵは逐次命 令実行を続ける。前述のように、分岐命令に関連したコミットスロット命令（Ｃ Ｓ１）は、分岐が行われるか否かにかかわらず実行できる。 ＣＰＵ５０は、ロード命令およびストア命令を使用し、ＣＰＵレジスタとセル バッファＲＡＭ（ＣＢＲ）５２との間にデータを転送する。典型的なロード命令 は、一般的にＣＢＲ５２からデータの１つあるいは２つのハーフワードを取り出 し、データを適当なＣＰＵレジスタに書き込む。適当なストア命令は、一般的に １つあるいは２つのＣＰＵレジスタの内容をＣＢＲ５２に書き込む。ＣＰＵ５０ は、このように単一命令を使用してＣＢＲ５２から１６ビットおよび３２ビット のデータ構造の読み出しおよび書き込みを可能にするように構成することができ る。ロードスケジューリングは、ＣＰＵ５０がプログラム実行を続けることがで きるように使用されると同時にＣＢＲ５２からのデータを待つ。ストア命令は、 ＣＰＵ５０がプログラム実行を続けることができるように書き込みバッファとと もに作動すると同時にデータがＣＢＲ５２に書き込まれる。 前述されたように、ＣＰＵ５０は、特に伝送するためのスケジューリングおよ びサービスのＡＴＭセルのために多数の命令を実行する。これらの命令は、プッ シュセル（ＰＵＳＨＣ）命令およびポップセル（ＰＯＰＣ）命令を含んでいる。 ＰＵＳＨＣ命令は、CPU５０によって実行されてセルの伝送のためのタイムスロ ットを探し、予約しようとして制御メモリ２２に記憶された一次スコアボードを ＣＳＳ５６に検索させる。ＰＯＰＣ命令は、ＣＰＵ５０によって実行され、ＣＳ Ｓ５６に指令して制御メモリ２２から指定されたタイムスロットに関連する接続 ＩＤを引き出し、スコアボードビットがセットされでいることが検出された場合 、前述の割り当てられたセルフラグレジスタ（ＡＣＦＲ）をセットし、対応する 一次スコアボードビットをクリアし、それによってタイムスロットロケーション を解放する。これらのセルスケジューリング動作およびサービス動作は図４〜図 ７とともにより詳細に記載される。 ２．３ 自動メモリ更新を有するロード多重命令 ＣＰＵ５０は、ロード多重高速メモリ（ＬＭＦＭ）命令を実行することによっ てＦＡＳＴ制御メモリ２２から直接その内部レジスタファイルへのデータのバー スト転送を開始できる。典型的なＬＭＦＭ命令は下記のフォーマットを利用でき る。 ＬＭＦＭ ｒｄ ＠ｒｓａ/ｒａｂ ＃ＨＷ｛ＬＮＫ｝ 上記のものにおいて、ｒｄは、ＣＰＵ５０の初期デスティネーションレジスタを 示し、ｒｓａおよびｒｓｂは、ＦＡＳＴ制御メモリ２２から転送されるデータブ ロックのアドレスビット（１８：１６）および（１５：０）のそれぞれを含むＣ ＰＵレジスタであり、＃ＨＷは、３２ビットメモリワードがＬＭＦＭ命令によっ てロードされると仮定すると、１６ビットのハーフワードの全計数を示し、｛Ｌ ＮＫ｝は、存在する場合、リンク機能が呼び出されるべきであることを示す命令 フィールドオプション（ＩＦＯ）を示している。リンク機能は、レジスタ内容が 読み出される制御メモリ２２のロケーションにＬＭＦＭ命令に応じてロードされ るＣＰＵレジスタを結合するようにＦＡＳＴメモリコントローラ５４に命令する 。このリンクは、ＦＡＳＴメモリコントローラ５４にあるいは他の場合にプロセ ッサ１２に所与の検索データブロックの制御メモリ２２のベースアドレスを記憶 することによって実行できる。本発明の自動メモリ更新機能によれば、ＡＬＵあ るいはこれらのＣＰＵレジスタを修正する他の命令は、更新メモリ（ＵＭ）ＩＦ Ｏを指定でき、それによって変更が制御メモリ２２にライトバックされる。予め 記憶された検索データブロックのベースアドレスは、変更がライトバックされる 特定の制御記憶ロケーションを識別するためにＣＰＵレジスタ番号とともに使用 される。さらに、制御メモリ２２から読み出される第１のハーフワードのコピー は、リンクＩＦＯが存在するならば、コントローラ５４のＦＡＳＴメモリの第１ のワードシャドウレジスタにメモリコントローラ５４によって書き込むことがで きる。したがって、ＣＰＵ５０によって実行されるソフトウェアプログラムは、 チャネル記述 子の第１のハーフワードにサービスルーチンアドレスを配置し、ＢＦ（分岐ＦＡ ＳＴメモリの第１のワードシャドウレジスタ）命令を使用し、第１のワードシャ ドウレジスタのアドレスに分岐できる。 ＬＭＦＭ命令によって、ＣＰＵ５０は、制御メモリ２２から引き出されるよう に多数のハーフワードを選択できる。ＦＡＳＴメモリコントローラ５４は、要求 される数のハーフワードを制御メモリ２２から引き出し、これらのハーフワード をレジスタｒｄに開始するＣＰＵレジスタファイルに直接書き込む。一実施例の ＬＭＦＭ命令は、制御メモリ２２から３２バイトまでのデータのバースト転送を 開始できる。ＦＡＳＴメモリコントローラ５４は、制御メモリ２２から戻され、 レジスタｒｄで開始し、レジスタｒｄ＋１、ｒｄ＋２等で続くハーフワードをＣ ＰＵレジスタファイルに１回１ハーフワード書き込む。コントローラ５４は、ハ ーフワードの量＃ＨＷが引き出されてしまうまで、制御メモリ２２からデータを 転送し続ける。転送が進行中である間、ＣＰＵ５０はプログラム実行を自由にし 続けるが、一般的に、バースト転送動作によるペンディング変更にあるレジスタ にアクセスしようと試みるべきでない。ハーフワードは、制御メモリ２２から戻 されるのでＣＰＵ５０に利用される。 ＣＰＵ５０は、戻されるハーフワードをアクセスする前に全転送が完了される よう待つ必要がない。データ構造のフィールドが処理されるのと同じ順序でデー タ構造のフィールドを配列することによって、ＣＰＵ５０は、単一命令を使用し て３２バイトのデータ構造を引き出すことができ、制御メモリ２２から受け取る ので引き出されたデータを処理し続けることができる。ＣＰＵ５０がアクティブ ＬＭＦＭ命令によるペンディング変更にあるレジスタにアクセスしようと試みる ならば、このレジスタのための新しい値が制御メモリ２２から戻されるまで機能 停止する。メモリコントローラ５４が使用可能である、すなわち書き込みバッフ ァアクセス、セルスケジューリング機能あるいはサービス機能あるいは他の動作 でビジーでないと仮定すると、所与のＬＭＦＭ命令に応じて読み出される第１の ハーフワードは、一般にＬＭＦＭ命令が実行された後約５ＣＰＵクロックサイク ルを後続処理するのに役立つ。したがって、連続ハーフワードは、その後バース ト転送が完了されるまでＣＰＵサイクル毎に一般に利用される。したがって、Ｃ ＰＵ機能停止を避けるために、所与のＬＭＦＭ命令のデスティネーションレジス タにアクセスする命令は約５ＣＰＵサイクルだけＬＭＦＭ命令から分離されるべ きであると同時に命令アクセスｒｄ＋１は約６ＣＰＵサイクル等だけＬＭＦＭ命 令から分離されるべきである。ＦＡＳＴメモリコントローラ５４が書き込みバッ ファアクセス、セルスケジューリング機能あるいはサービス機能、あるいは他の 動作でビジーであるならば、遅延はわずかに増加する可能性がある。このような 遅延の増加は処理命令の適当な選択および配置によって多数の用途に適合できる 。 前述のように、自動メモリ更新機能によって、ＣＰＵ５０は、例えば、演算の 結果がレジスタ内容を供給した制御メモリ２２のロケーションにライトバックさ れるべきである所与のＣＰＵレジスタの内容で操作されるＡＬＵ命令内に指定す ることができる。これによって、ＣＰＵ５０は、別個のストア命令を実行しない で引き出されたデータ構造を更新できる。自動メモリ更新機能は、典型的な実施 例において、制御メモリ２２の参照データブロックがＬＭＦＭデスティネーショ ンレジスタに結合されるようにＬＭＦＭ命令の前述のＬＮＫＩＦＯを指定し、そ れからＡＬＵ命令の更新命令（ＵＭ）ＩＦＯを含むことによって実行される。例 えば、指定されたｒｄ＝Ｒ１６およびＬＮＫ ＩＦＯを有するＬＭＦＭ命令の実 行によって、レジスタＲ１６〜Ｒ３１は、ＣＰＵレジスタｒａｅおよびｒｓｂに よってアドレスされる１６のハーフワードの制御メモリブロックに逐次結合され る。前述のように、このリンクは、引き出されたデータブロックの制御メモリ２ ２のベースアドレスをメモリコントローラ５４にあるいは他の場合にプロセッサ １２に記憶することによって実行できる。ＣＰＵレジスタ番号は、ベースアドレ スおよびレジスタ番号の各組合わせが特定 の制御メモリロケーションを指定するように、引き出されたデータブロックを供 給した制御メモリロケーションへのインデックスとして使用することができる。 例えば、リンクが３２の汎用の１６ビットのＣＰＵレジスタを有する実施例のア ドレス指定されたＮ個のハーフワードブロックのハーフワード０で開始すると仮 定すると、Ｎは、ｒｄがＲ１６であるならば、Ｎ＝１６であり、ｒｄがＲ２４で あるならば、Ｎ＝８であり、ｒｄが２８であるならば、Ｎ＝４であり、かつｒｄ が３０であるならば、Ｎ＝２であるようにレジスタｒｄの選択によって固有に決 定することができる。この例において、レジスタＲ１６、Ｒ２４、Ｒ２８あるい はＲ３０は、ＬＮＫ ＩＦＯを指定するＬＭＦＭ命令でｒｄのために選択できる 。したがって、レジスタ番号とともに引き出されたＮ個のハーフワードの記憶さ れているベースアドレスはメモリ更新を実行するために使用される。 自動メモリ更新機能とともに前述のＬＭＦＭ命令は、最大３２ＣＰＵサイクル だけ典型的なセル処理ルーチンの長さを減少できる。これは、ＳＲＡＭあるいは 他の種類の制御メモリからのアクセス制御情報に一般的に関連する呼び出し時間 を減少することによって従来技術のセルプロセッサに対して著しい長所をもたら す。自動メモリ更新機能は特にＡＬＵ命令と併用するのに最適であるけれども、 この機能は他の種類のＣＰＵ命令とも併用できることに注目すべきである。 ２．４ 結果のモジュロ部分の分岐を有するモジュロ演算 ＣＰＵ５０のＡＬＵは、モジュロ算術演算をサポートするように構成できる。 ＡＬＵ命令のＭＯＤ ＩＦＯは、その後にＡＬＵ演算の結果が切り捨てられるビ ット桁の数を右側から左側に指定するために使用することができる。例えば、 ＡＤＤ Ｒ０，０４ｘｈ，Ｒ５ ＭＯＤ１６ のようなＡＬＵ命令は、０４ｘｈをレジスタＲ０の内容に加え、この結果をレジ スタＲ５に記憶し、加算演算モジュロ１６を実行するようにＡＬＵ に命令する。モジュロ１６加算あるいは減算演算は、ＲＯ（３）ビットからの桁 上げあるいはボローがあるか否かにかかわらず、Ｒ０（１５：４）に影響を及ぼ さない。Ｒ５（１５：４）に書き込まれた結果はＲ０（１５：４）にある値であ るが、Ｒ５（３：０）は、加算演算あるいは減算演算の（３：０）ビットを受け 取る。所与のユーザは、典型的な実施例において２〜６４Ｋの任意の値としてＭ ＯＦ ＩＦＯを選択できる。６４Ｋの値は、ソフトウェアコンパイラによって選 択されたデフォルト値として使用して、ＭＯＦ ＩＦＯがＡＬＵ命令に全然ない 場合、全１６ビット演算を生じることができる。 本発明によれば、ＭＯＦ ＩＦＯがＡＬＵ命令内で指定される場合、ある種の 条件分岐命令は、１６ビットの結果のモジュロ部分だけにおよび／またはモジュ ロ部分の最上位ビット（ＭＳＢ）桁からの桁上げに基づいて評価できる。これら の条件分岐命令は、例えば、Branch on Zero(BZ)、Branch on Non-Zero(BNZ) 、Branch on Less than Zero(BLZ)、Branch on Overflow(BNO)、Branch o n No Overflow(BNO)、Branch on Carry(BC)およびBranch on No Carry(BNC)を含 んでいる。結果のモジュロ部分だけに基づいたＢＺおよびＢＮＺの条件分岐命令 を使うと、ユーザは、例えば、非ゼロベースアドレスを有するメモリポインタに おいて交差するページあるいはブロックの境界の発生のためにテストすることが できる。 ２．５ セルバッファＲＡＭ（ＣＢＲ）５２ 図３Ａは、ＡＴＭセルプロセッサ１２のセルバッファＲＡＭ（ＣＢＲ）５２を 示している。ＣＢＲ５２は、送受信方向の両方にセルをバッファリングするため に使用され、本実施例においてセルバッファと呼ばれる１６の６４バイトブロッ クに構成される。ＡＴＭセルは、ＵＴＯＰＩＡポート６４を介してＳＯＮＥＴイ ンタフェース１６のようなＰＨＹレイヤ装置から受信されたときＣＢＲ５２のＲ Ｘ ＣＥＬＬブロックに書き込むことができる。ＡＴＭセルは、物理レイヤに伝 送される前にＣＢＲ５２のＴＸ ＣＥＬＬブロックに構成できる。この典型的な実施例において、セルは、セルの バイト０がセルバッファのバイト４に存在するようにセルバッファに書き込まれ るかあるいは組み立てられる。これは、図３Ａに示されるような所与のセルバッ ファの前部端に４つの未使用バイトを残す。ＣＰＵ５０は、交換応用において使 用するのに適しているユーザ指向経路選択タグのような専用情報をセルバッファ の前部端のこれらの未使用バイトに書き込みができる。システム初期設定で、Ｃ ＢＲ５２は、図３Ａに示されるような受信セル記憶、送信セル構造およびバッフ ァプールキャッシュイングのためのセクションにセグメント化される。この実施 例の所与のセルは、所与の６４バイトのセルバッファの上部５６バイト以下しか 一般に占有しない。これは、ＲＡＭの約８バイトを各セルバッファの下部に残す 。これらの未使用セルバッファ部は、下記により詳細に記載されているメモリ空 間収集プロトコルを使用して効率的にアクセスできる。図３Ａの典型的な実施例 において、記憶セルは、５３バイトよりもむしろ５２バイトを占有するように示 されていることに注目すべきである。これは、この実施例において、所与のセル に関連するヘッダエラー制御（ＨＥＣ）バイトがチェックされ、このセルの記憶 以前に廃棄されると限定することなく仮定しているからである。 ２．６ ＣＢＲメモリ空間収集プロトコル 図３Ｂおよび図３Ｃは、本発明による典型的なメモリ空間収集プロトコルの動 作を示している。このプロトコルによって、図３Ａのセルバッファの未使用メモ リ空間は、“仮想”隣接空間としてアクセスできる。前述のように、図３Ａの典 型的なＣＢＲ５２は、各々が６４バイトの１６個のセルバッファ、すなわち１０ ２４バイトを含んでいる。１０ビットの全部は、１０２４バイトの各々をアクセ スするのに必要である。１つの典型的な実施例の空間収集プロトコルは、最初の ７ビットが６４バイトのセルバッファの各々の下部の８バイトの未使用部分で構 成されている仮想隣接 空間のバイトの中の１バイトを識別する、図３に示される１１ビットの仮想アド レスを使用する。仮想アドレスの第１１番目のビットは、収集ビットと呼ばれ、 セットされる場合、対応するアドレスを仮想アドレスとして、したがって仮想隣 接空間のバイトを示すアドレスとして識別する。空間収集プロトコルは、セット 収集ビットを有するアドレスを物理アドレスに変換する。物理アドレスは、ＣＢ Ｒ５２の１６個のセルバッファの未使用部分を含んでいる仮想隣接空間の特定の バイトを識別する。 図３Ｃは、空間収集プロトコルを実行するアドレスを処理する典型的なステッ プのセットを示すフロー図を示している。ステップ９０において、この収集ビッ トは、６４バイトのセルバッファの下部の未使用の８バイト部分の中に含まれる ＣＢＲバイトを識別する仮想アドレスのためにセットされる。収集ビットは、Ｃ ＰＵ５０、バスインタフェース６８あるいは７２に関連するＤＭＡコントローラ 、あるいは他の適当なアドレス調整機構によってセットできる。次に、セット収 集ビットを有する仮想アドレスはＣＢＲ５２に供給される。ステップ９２におい て、ＣＢＲ５２内のアドレス発生器は、セット収集ビットを有する仮想アドレス を物理アドレスに変換する。図３Ｂは、仮想アドレスから図３Ａの典型的なＣＢ Ｒ５２と併用するのに適している物理アドレスへの変換を示している。１０ビッ トの物理アドレスの最初の３ビットは、１１ビットの仮想アドレスの最初の３ビ ットから直接マッピングされる。これらのビットは、ＣＢＲ５２の特定セルバッ ファの下部の８バイトの中の１バイトを識別する。物理アドレスの次の３ビット は、物理アドレスが所与のセルバッファの下部８バイト部分に常にスキップする ように仮想アドレスに関係なく論理‘１’にセットされる。物理アドレスの最後 の４ビットは、図３Ｂに示されるような仮想アドレスの第３、第４、第５および 第６番目のビットからマッピングされる。収集ビットは、所与の仮想アドレスか ら物理アドレスへの前述の変換を生じるようにＣＢＲ５２のアドレス発生器に命 令した後に廃棄される。ステップ９４において、ＣＢＲ５２の仮想隣接メモリ空 間は物理アドレス を使用してアクセスされる。 前述の変換によって、６４バイトのセルバッファの未使用部分は、隣接メモリ 空間としてアクセスできる。したがって、本発明は、ＣＰＵ５０あるいはＤＭＡ コントローラをトリガして未使用バイトの実際のアドレスを適当に変更すること によって隣接メモリ空間を形成するように特定のアドレスを指定するデータアク セスを可能にする。仮想アドレスから物理アドレスへの特定の変換は、もちろん セルバッファの寸法および収集される未使用メモリ空間の相対ロケーションに応 じて変わる。他の実施例は、仮想アドレスに使用される収集ビットの数を調整す ることによっていくつかの別個の収集空間を抗供する。さらに、所与のアドレス 内の収集ビットの位置はメモリサイズに応じて変わることに注意すべきである。 ３． 一次スコアボード／接続ＩＤテーブルを使用するＣＳＳ５６の動作 次に、ＣＳＳ５６の動作はより詳細に説明される。ＡＴＭセルプロセッサ１２ のセルスケジューリング動作およびサービス動作は、この実施例では、アルゴリ ズム機能およびハードウェア支援機能の両方の組合わせとして実行される。セル スケジューリング機能のアルゴリズム部はＣＰＵ５０によって実行される。ハー ドウェア支援部はＣＳＳ５６によって実行される。セルスケジューリング処理は 、ＡＴＭ伝送リンクあるいは資源をセルの繰り返しコンテナとしで割り当てる他 のバンド幅を管理するものとみなすことができる。セルタイム毎に、一次スコア ボードによって示されるセルスケジューリングの次のロケーションがチェックさ れる。このロケーションが予約されているならば、セルが構成され、このロケー ションを予約した仮想接続（ＶＣ）のために送信される。このロケーションが予 約されていないならば、アイドルセルは、逆圧を保持する、すなわちセルプロセ ッサがあまりにも急速にスケジュール中を処理することを防止するように伝送で きる。 図４は、ＡＴＭセルプロセッサ１２が制御メモリ２２に作成できる典型的な 一次スコアボード１００および接続識別子（ＩＤ）テーブル１１０を示している 。一次スコアボード１００および接続ＩＤテーブル１１０は、一般的にＣＳＳ５ ８とともに作動するＣＰＵ５０によって保持される。ＣＳＳ５６は、ＣＰＵ５０ によって出されたセルスケジューリングリクエストおよびサービスリクエストに 応じて制御メモリ２２に記憶されている一次スコアボードおよび接続ＩＤテーブ ルを変更する。一次スコアボード１００は、セルスケジューリングを示し、多数 の１６ビットラインに配置されたビット群を含んでいる。この実施例において、 一次スコアボード１００は、これらの１６ビットラインの中の１２８〜１０２４ を含み、他のラインの数およびサイズは他の実施例で使用できる。接続ＩＤテー ブル１１０は、一次スコアボード１００のビットの各々に対する１６ビットのエ ントリを含み、したがってスコアボード１００の正確なライン数に応じて２０４ ８〜１６３８４のエントリを含んでいる。各１６ビットのエントリは、他の実施 例の３２ビットあるいは他の適当なビット数を含むように拡張できる。接続ＩＤ テーブル１１０の各エントリは、所与のＡＴＭ伝送リンクのセルタイムスロット を示し、所与のスケジューリングＶＣのための接続ＩＤを含むかあるいは対応す るセルタイムスロットがスケジューリングされなくて、したがって使用可能であ る場合接続ＩＤを全然含まないかのいずれかである。 本発明によるスコアボードは、セルスケジューリング動作を示す任意のビット 群あるいは他の情報要素であってもよい。ここではビットを使用して示されてい るけれども、所与のスコアボードは、セルスケジューリングおよびサービス状態 を示すために多ビット情報要素を含む他の情報要素の構成を使用できる。例えば 、ビット対あるいは他の適当な多ビット構造は、具体的な実施例におけるような 各タイムスロットのための単一ビットよりもむしろ各セルタイムスロットを示す ために使用できる。ここに使用されるような用語“スコアボード”は、これらの および他の代替の情報 要素のグルーピングを含むように理解されるべきである。本発明によるスコアボ ードは、メモリワードのアレイ、ルックアップテーブル、あるいは任意の他の適 当なメモリロケーションの構成に記憶できる。 前述のように、本発明のセルスケジューリング動作は、所与のシステム伝送リ ンクのＡＴＭセル機能をセルの周期的コンテナに分割するものとみなすことがで きる。伝送集中フレーム構造に対して周期的コンテナの境界は一般に任意である 。図４の典型的な実施例の周期的なコンテナ内の各ロケーションあるいはセルタ イムスロットは、一次スコアボード１００の単一ビット、したがって接続ＩＤテ ーブル１１０の単一エントリに対応する。一次スコアボード１００のビット数は 、接続ＩＤテーブル１１０のエントリ数に対応し、周期的なコンテナのセルタイ ムスロットの数にも等しい。一次スコアボード１００の連続ビットおよび接続Ｉ Ｄテーブル１１０の連続ロケーションは、ＡＴＭ伝送リンクの連続セルタイムス ロットを示している。ユーザは、この典型的な実施例の周期的なコンテナサイズ を２０４８〜１６３８４の任意のセル数にセットできる。他のセルの数も所与の 応用で必要に応じて使用できる。 ＡＴＭ伝送リンクのセルタイムスロットは、対応する一次スコアボードビット が論理‘１’にセットされるならば、特定の接続のためにスケジューリングされ たものとして示される。セルタイムスロットは、未スケジューリングとみなされ 、したがって、対応する一次スコアボードビットが論理‘０’であるならば使用 可能である。一次スコアボードビットは、ＣＰＵ５０によって実行されるＰＵＳ ＨＣ命令およびＰＯＰＣ命令に応じてＣＳＳ５６によってセットされ、クリアさ れる。 ＣＰＵ５０は、ユーザによって出されたＰＵＳＨＣ命令を実行することによっ てスケジューリング動作を開始する。ＰＵＳＨＣ命令は、接続ＩＤテーブル１１ ０内の１６ビットの接続ＩＤおよび目的ロケーションを指定する。ＣＳＳ５６は 、目的ロケーションに対応するビットのあるいはこのビット後の使用可能なセル タイムスロットを示す最初のビットを探 す一次スコアボード１００を検索することによってＰＵＳＨＣ命令に応答する。 使用可能なセルタイムスロットが一次スコアボードの最後のビットによって検出 されない場合、ＣＳＳ５６は、スコアボードの始点から検索を続ける。ＣＳＳ５ ６が使用可能なセルタイムスロットを見い出すと、ＣＳＳ５６は、一次スコアボ ードの対応するビットをセットし、１６ビット接続ＩＤを接続ＩＤテーブル１１ ０の対応するエントリに書き込む。ユーザは、接続ＩＤとして任意の１６ビット 値を供給する。一般に、接続ＩＤは対応するＶＣに対する接続記述子（ＣＤ）の 制御メモリ２２のベースアドレスの役をする。 ＰＵＳＨＣ命令はディスパッチ命令として実行できる。このように、ＣＰＵ５ ０は、他の命令を実行できると同時にＰＵＳＨＣ動作はＣＳＳ５６によって実行 される。ＣＰＵ５０は、前述のような外部状態信号の状態（ＥＳＳ）をチェック することによって何時ＰＵＳＨＣ動作が完了されるかを決定する。例えば、適当 なＥＳＳは、セルスケジューリング動作が進行中である間、セットすることがで きる。スケジューリング動作の完了で、ＣＰＵ５０は、内部スケジューリングア ドレスレジスタから生じるスケジューリングアドレスを読み出すことができる。 スケジューリングアドレスは、目的アドレスが予め予約されたことが検出された 場合、目的アドレスと異なってもよい。 ＣＰＵ５０は、いろいろなセルタイムスロットを予約したＶＣもサービスする 。ＣＰＵ５０は接続ＩＤテーブル１１０の対応するエントリーを調べることによ ってどのＶＣがタイムスロットを予約したかを決定する。ＣＰＵ５０は、所与の ユーザプログラムによって出されたＰＯＰＣ命令を実行することによって接続Ｉ Ｄテーブルエントリを読み出す。ＰＯＰＣ命令の実行によって、ＣＳＳ５６は、 アドレス指定接続ＩＤテーブルエントリを戻し、エントリに対応する一次スコア ボードビットの値をＣＰＵ５０の割り当てセルフラグレジスタ（ＡＣＦＲ）にコ ピーし、それから一次スコアボードビットをクリアする。 ＣＰＵ５０は、ポインタを保持し、現セルタイムスロットを示す接続ＩＤテー ブル１１０に入れる。ＣＰＵ５０は、ＰＯＰＣ命令が実行される度にこのポイン タを増分できる。一次スコアボードおよび接続ＩＤテーブルが周期的なコンテナ を示しているために、ＣＰＵ５０は、コンテナサイズを法としたその接続ＩＤテ ーブルポインタを操作する責任を負っている。 ＰＯＰＣ命令は、ディスパッチ命令としても実行できる。このように、ＣＰＵ ５０は、他の命令を実行できると同時にＰＯＰＣ動作はＣＳＳ５６によって実行 される。ＣＰＵ５０は、適当なＥＳＳの状態をチェックするかあるいは内部接続 ＩＤデスティネーションレジスタをアクセスすることによって何時ＰＯＰＣ動作 が完了されるかを決定する。ＣＰＵ５０がＣＳＳ５６によって書き込まれる前に 接続ＩＤデスティネーションレジスタにアクセスしようと試みるならばＰＯＰＣ 動作の完了を待つことを保証する適当な機構が装備されている。 前述されるようなＣＳＳ５６は、外部クロックが全然必要でない自己ペースシ ステムとして実行できる。ＵＴＯＰＩＡポート６４を通るＰＨＹレイヤ伝送リン クからの逆圧は、ＣＰＵ５０が送信のためのセルを待ち行列に入れることができ る速度を制限するために使用できる。逆圧の有益の効果を保持するために、割り 当てられていない（アイドル）セルは、割り当てられないタイムスロットがＰＯ ＰＣ命令によって接続ＩＤから取り除かれる場合、送信のための待ち行列に入れ られる。ＣＰＵ５０は、タイムスロットがＡＣＦＲの状態をテストすることによ って割り当てられるかあるいは割り当てられないかを決定できる。ＡＣＦＲがゼ ロであるならば、タイムスロットは割り当てられておらず、アイドルセルは必要 な逆圧を保持するために待ち行列に入れられる。アイドルセルの待ち行列は、伝 送リンクのセル間放出間隔（ＩＣＩ）は、プログラム化され、スケジューリング の中に入れられる間隔にほぼ等しいことを保証する。 ４．スケジューリング命令 ４．１ ＰＵＳＨＣ命令 図５は、セルスケジューリング命令ＰＵＳＨＣの動作をより詳細に示すフロー チャートである。典型的な用途では、ＣＰＵ５０は、新しい接続を追加する場合 あるいは現在のＶＣをサービスする場合、ＶＣをスケジューリングする。可変ビ ット伝送速度（ＶＢＲ）および使用可能なビット伝送速度（ＡＢＲ）ＶＣのよう な動的に割り当てられたタイムスロットを有するＶＣに関して、スケジューリン グは、各ＶＣに対する１つあるいはそれ以上のタイムスロットリクエストを含む ことができる。スケジューリングは、バンド幅の永久予約を利用する一定ビット 伝送速度（ＣＢＲ）ＶＣのための単一あるいは複数のスケジューリングタイムス ロットも含むことができる。 ＣＰＵ５０は、２つの実値パラメータ増分（Ｉ）および限界（Ｌ）および中間 変数のセットを使用する総称セル速度アルゴリズム（ＧＣＲＡ）を実行すること によって目的セルスロットタイムを決定する。アルゴリズムはＧＣＲＡ（Ｉ，Ｌ ）と呼ばれ、M.de Pryckerによる上記に引用された参考文献により詳細に記載さ れている。この実施例のパラメータＩは、対応するＶＣに対するセル間放出間隔 （ＩＣＩ）であり、パラメータＬは許容範囲の値を示している。ＩＣＩは、伝送 リンクの所与のＶＣの連続セル間の最少間隔を示している。ＣＢＲ接続およびＶ ＢＲ接続に関しては、ＩＣＩは、一般に時変でなく、一般的には約１／ＰＣＲで あり、ここでＰＣＲは所与のＶＣのためのピークセル速度を示す。ＡＢＲ接続に 関しては、ＩＣＩは、一般的にはネットワークからのフィードバックに基づいて 変わり、約１／ＡＣＲであり、ここでＡＣＲは所与のＶＣに対する使用可能なセ ル速度を示している。ＣＰＵ５０は、ここで参照として組み込まれるＡＢＲサー ビス仕様に基づくＡＴＭフォーラムレートによるＡＢＲ接続のためのＩＣＩを計 算する。ＩＣＩを計算するために利用される情報は、制御メモリ２２に記憶する ことができ、得られるＩＣＩは、高い接続速度を 利用可能にするために端数整数として制御メモリ２２に記憶することができる。 例えば、所与の接続伝送速度、１６セルタイム毎に５個のセルまで下げて決定で きる。このような場合、ＩＣＩは、残りを有する端数整数として記憶でき、セル は、ＧＣＲＡ結果の整数部だけを使用してスケジューリングできる。残りがセー ブされ、次のスケジューリング事象でＧＣＲＡに加えられる。 ＣＰＵ５０は、限界Ｌより小さい計算された理論的到着時間（ＴＡＴ）に接続 をスケジューリングすることによってセルスケジューリング衝突に起因するバン ド幅損失を制限できる。スケジューリングされた時間のコピーは、一般に前述の ＧＣＲＡ機能の適切な動作を可能にするためにこのようにスケジューリングされ た各ＶＣに対するチャネル記述子に記憶されている。ＧＣＲＡ機能は対応するＶ Ｃに対する目的セルタイムスロットを発生する。 図５のステップ１２０に示されるように、ＰＵＳＨＣ命令は、ユーザによって 発され、ＣＰＵ５０で受け取られる。ＰＵＳＨＣ命令は、一般にセルタイムスロ ットを要求するＶＣを識別する固有な１６ビットの接続ＩＤを指定する。接続Ｉ Ｄテーブルの目的アドレスは、前述のようにＣＰＵ５０によって計算されるかあ るいはＰＵＳＨＣ命令に付属することができる。ＣＰＵ５０は、接続ＩＤおよび 目的アドレスをＣＳＳ５６に供給する。ＣＳＳ５６は、接続ＩＤテーブルの目的 アドレスをステップ１２２に示されるように一次スコアボードの対応する目的ロ ケーションに変換することによってＰＵＳＨＣ命令に応答する。次に、ＣＳＳ５ ６は、ステップ１２４に示されるように、引き出し、目的セルタイムスロットに 対応する目的ロケーションのあるいは目的ロケーション後の最初の使用可能なセ ルタイムスロットを探す一次スコアボードの一部中を探索し始める。前述のよう に、ＣＳＳ５６は、使用可能なロケーションが目的ロケーションと一次スコアボ ードの終わりとの間に検出されないならば、一次スコアボードの始めから検索し 続けることができる。ステップ１２６において、 スロットが一次スコアボードの引き出された部分に使用可能であるか否かに関す る決定が行われる。セルが全然使用可能でない場合、他の一次スコアボードの部 分は、図示されるようなステップ１２４を繰り返すことによって引き出し、検索 できる。一旦使用可能なセルタイムスロットが検出されると、ＣＳＳ５６は、ス テップ１２８に示されるように、対応するスコアボードビットを論理‘１’にセ ットすることによって所与のＶＣに対してスケジューリングされるようなスロッ トを予約する。次に、ＰＵＳＨＣ命令に指定された１６ビットの接続ＩＤは、ス テップ１３０でスケジューリングされた一次スコアボードビットに対応する接続 ＩＤテーブルのロケーションに書き込まれる。ステップ１２０〜１３０は、ＡＴ Ｍセルプロセッサ１２に受け取られた各ＰＵＳＨＣ命令に対して繰り返される。 ＰＵＳＨＣ命令の実行中、一次スコアボードの全ビットが、使用可能なセルタ イムスロットが全然ないことを示す１にセットされるならば、ＣＳＳ５６は、前 述のＣＳＳ構成レジスタに１ビットをセットすることによってエラーを戻すこと ができる。このようなエラービットに対して頻繁にチェックすることはセルプロ セッサの有効な動作速度を著しく落とす可能性がある。この潜在的な問題は、タ イムスロットが一次スコアボードで使用可能であることを保証するステップを行 うことによってアドレス指定できる。例えば、ＣＳＳ５６は、次のＰＵＳＨＣ命 令を実行する前に一次スコアボードの現セルスロットを常に解放するように命令 されることができ、それによって少なくともこのタイムスロットが次のリクエス トをサービスするのに使用可能であることを確実にする。それとは別に、ＣＳＳ ５６は、新しい接続を付加するか、あるいは割り当てられていないスロットに遭 遇する場合のみ非アクティブ接続を起動するように構成することができ、新しい 接続が一次スコアボードの容量を超える場合、新しい接続が許可されないように する。一般に、各接続は、一次スコアボードの１ビット位置を消費する。制御ソ フトウェアには、一次スコアボードのアクティブＶＣ数の正確なカウントを備え ていて、新しい接続がスコアボード 容量を超える場合、新しい接続の確立を拒否するように構成されている。所与の 接続は、予め割り当てられたＣＢＲ接続の場合のように一次スコアボードの２つ 以上のスロットを消費でき、したがって、この事象において、使用可能なスロッ ト決定は調整される。 典型的なＰＵＳＨＣ命令は下記のフォーマットであってもよい。 ＰＵＳＨＣ ｒｓａ ＠ｒａｂ これにおいて、ｒｓａおよびｒｓｂはＣＰＵ５０のレジスタである。レジスタｒ ｓａは要求された接続に対する１６ビット接続ＩＤを含み、レジスタｒｓｂは、 接続ＩＤテーブルのアドレスの形式の目的セルタイムスロットを含んでいる。接 続ＩＤテーブルのベースアドレスはＣＳＳ構成レジスタから読み出すことができ る。ＣＳＳ５６は、レジスタｒｓｂからの接続ＩＤテーブルアドレスおよびＣＳ Ｓ構成レジスタから読み出されたベースアドレスを使用して対応する一次スコア ボードビットロケーションを計算する。次に、ＣＳＳ５６は、指定アドレスのあ るいは指定アドレスの後の使用可能なセルタイムスロットを探す一次スコアボー ドを検索する。レジスタｒｓａからの１６ビット接続ＩＤは、ＣＳＳ５６によっ てｒｓｂに含まれた目的アドレスによって指定されたロケーションのあるいはロ ケーション後の接続ＩＤテーブルの最初の使用可能なロケーションに書き込まれ る。スコアボード検索は、最初の使用可能なスコアボードビットロケーションを 決定し、それによって接続ＩＤテーブルの最初の使用可能なスロットを決定する 。 ４．２ ＰＵＳＨＦ命令 前述のＰＵＳＨＣ命令の可能な他の実行は、ＰＵＳＨＣ、高速モード（ＰＵＳ ＨＦ）命令である。ＰＵＳＨＦ命令によって、ＣＰＵ５０およびＣＳＳ５６は、 所与のＶＣに対する一次スコアボードビットを突き止め、予約するために前述の 機能を実行する。しかしながら、ＰＵＳＨＦ命令は、ＰＵＳＨＦ命令が接続ＩＤ テーブルを更新しない点で前述のＰＵＳＨＣ 命令と異なる。したがって、ＰＵＳＨＦ命令は、現ロケーションの接続ＩＤがＰ ＵＳＨＦ命令が実行される時点で一般に既知であるために、例えば、静的にスケ ジューリングされたＣＢＲ接続を再予約する際に役立つ。 ５． サービス命令 ５．１ ＰＯＰＣ命令 図６は、セルサービス命令ＰＯＰＣの動作をより詳細に示すフロー図である。 接続ＩＤテーブルの各ロケーションはＡＴＭ伝送リンクのセルスロットを示して いるので、ＣＰＵ５０はテーブルから接続ＩＤを逐次読み出すことができる。Ｃ ＰＵ５０は、接続ＩＤによって識別された接続をサービスする。接続サービスは 、例えば、従来のＡＴＭセグメンテーション・リアッセンブリ（ＳＡＲ）動作に おいて伝送するためにセルを形成し、それを待ち行列に入れるかあるいはメモリ から現在のセルを読み出し、伝送するためにこのセルを待ち行列に入れることを 含んでいる。ＵＴＯＰＩＡポート６４の送信器待ち行列からの逆圧は、プロセッ サが接続ＩＤテーブル１１０中を進行する速度を整調するスロットル機構を備え ている。逆圧ベース速度制御の効率を保持するために、ＣＰＵ５０は、割り当て られないロケーションが接続ＩＤテーブルから取り除かれる場合、ＵＴＯＰＩＡ ポート送信器待ち行列の割り当てられないセルあるいはアイドルセルを待ち行列 に入れる。 図６のステップ１５０において、所与のユーザプログラムからのＰＯＰＣ命令 は、ＣＰＵ５０で受け取られる。ＰＯＰＣ命令は、ＶＣに対する接続ＩＤを識別 する接続ＩＤテーブルのアドレスおよび対応する一次スコアボードビット指定す る。ステップ１５２において、ＣＳＳ５６は、接続ＩＤテーブルの指定ロケーシ ョンに記憶された接続ＩＤを制御メモリ２２から引き出す。ステップ１５４にお いて、ＣＳＳ５６は、特定接続ＩＤテーブルエントリに関連した一次スコアボー ドビットを引き出し、それをＡＣＦＲにコピーする。ＡＣＦＲの出力は、ＣＰＵ ５０が、指定ロケー ションがスケジューリングされたか（ＡＣＦＲ＝‘１’）あるいは割り当てられ なかった（ＡＣＦＲ＝‘０’）かどうかを決定し終わったことをＰＯＰＣ命令が 一度チェックできる指定ＥＳＳに接続することができる。ステップ１５６におい て、ＣＳＳ５６は、将来のスケジューリングリクエストに役立つようなセルタイ ムスロットをマークするために対応する一次スコアボードビットをクリアする。 ステップ１５８において、ＣＰＵ５０は、接続ＩＤテーブルで指定されるＶＣに 対するセルを構成し、ＡＴＭ伝送リンクを介して伝送するために構成されたセル を待ち行列に入れる。あるいはＣＰＵ５０ｈａ以前に構成されたセルを引き出し それを伝送のために待ち行列にいれる。ステップ１５０〜１５８は、ＣＰＵ５０ で受け取られた各ＰＯＰＣ命令に対して繰り返される。 典型的なＰＯＰＣ命令は下記のフォーマットであってもよい。 ＰＯＰＣ ｒｄ ＠ｒｓｂ これにおいて、ｒｄおよびｒｓｂはＣＰＵ５０のレジスタである。レジスタｒ ｓｂは、関心のある接続ＩＤテーブルエントリのアドレスを含んでいる。さらに 、接続ＩＤテーブルのベースアドレスはＣＳＳ構成レジスタから読み出すことが できる。ＣＳＳ５６は、アドレス指定接続ＩＤを読み出し、それをＣＰＵ５０の レジスタｒｄに書き込む。ＣＳＳ５６は、接続ＩＤテーブルアドレスからの対応 する一次スコアボードアドレスおよびＣＳＳ構成レジスタから読み出されたベー スアドレスを計算し、接続ＩＤテーブルエントリに関連したスコアボードビット を読み出し、その値をＡＣＦＲにコピーし、それからスコアボードビットをクリ アする。 ＣＰＵ５０は、前述の典型的なＰＯＰＣ命令以外の命令を利用して一次スコア ボードおよび接続ＩＤテーブルエントリを読み出し、書き込みもできることに注 目すべきである。 ５．２ ＰＯＰＦ命令 前述のＰＯＰＣの可能な他の実行はＰＯＰＣ、高速モード（ＰＯＰＦ） 命令である。ＰＯＰＦ命令によって、ＣＰＵ６０およびＣＳＳ５６は、所与のＶ Ｃに対する一次スコアボードビットを戻し、クリアするために前述の機能を実行 する。しかしながら、ＰＯＰＦ命令は、ＰＯＰＦ命令が接続ＩＤを戻さない点で 前述のＰＯＰＣ命令と異なる。したがって、ＰＯＰＦ命令は、例えば、ＣＰＵ５ ０がスコアボードビット群を高速にチェックできるということで役立つ。グルー プの所与のスコアボードビットがセットされるならば、ＣＰＵは接続ＩＤテーブ ルの対応するエントリの読み出しに移る。 ６． セルスケジューリング処理の付加的詳細 ６．１ 制限された一次スコアボード検索時間 ＣＳＳ５６は、使用可能なセルタイムスロットが所定のメモリ読み出しサイク ル数内で一次スコアボード内の任意の開始位置から識別できることを保証する本 発明による一次スコアボード検索技術を利用できる。この望ましい特性をもたら すように二次スコアボードを使用する典型的な検索技術が下記に詳細に記載され る。 ６．２ ＣＳＳ命令バッファ ＣＳＳ５６は、ＰＵＳＨＣ／ＰＯＰＣ命令バッファを含むように構成すること ができる。この命令バッファが２命令バッファとして選択されるならば、ＣＰＵ ５０は、機能停止状態に入らないで２つのセルスケジューリング命令あるいはサ ービス命令まで出すことができる。ＰＵＳＨＣ／ＰＯＰＣ命令バッファが満杯で ある間、バッファセルスケジューリング命令あるいはサービス命令の実行は、第 １の命令によって指定される演算が完了されるまでプロセッサ機能停止状態を生 じる可能性がある。 ６．３ −次スコアボードおよび接続ＩＤテーブルのアドレス指定 接続ＩＤテーブルおよび一次スコアボードのアドレス指定は、下記の ように提供できる。前述のように、制御メモリ２２のテーブルのベースアドレス を示す接続ＩＤテーブルアドレスのビット１５〜１８はＣＳＳ構成レジスタで指 定することができる。接続ＩＤテーブルアドレスのビット１〜１４は、前述のＰ ＵＳＨＣ命令およびＰＯＰＣ命令によって指定されるようなｒｓｂレジスタのビ ット０〜１３としてソフトウェアによって供給されることがある。１０２４ライ ン、したがって１６３８４エントリを有する典型的な一次スコアボードに関して は、指定された接続ＩＤテーブルエントリに対応するスコアボードアドレスは下 記のように発生することができる。 スコアボードアドレスビット（１８：１１）ＣＳＳ構成レジスタから読み 出す：ベースアドレス スコアボードアドレスビット（１０：１） ｒｓｂ（１３：４）から 読み出す：接続ＩＤテーブルＡＤＲ （１３：４） スコアボードアドレスビット（０） ０ｘｂとして固定 目的ビットアドレス ｒｓｂ（３：０）から読 み出す： 接続ＩＤテーブルＡＤＲ（３：０） ６．４ 一次スコアボードの初期設定 ＣＰＵ５０は、システム初期設定ルーチン中、一次スコアボードマトリックス を初期設定をする責任を負うことができる。ＣＰＵ５０は、一次スコアボードを 備える制御メモリ２２のロケーションに全てゼロを書き込むことによって一次ス コアボードを初期設定できる。一旦一次スコアボードが初期設定されると、ＣＰ Ｕ５０は、自由にセルスケジューリング命令を実行できる。このことから、全て のスケジューリング変更は、セルプロセッサ１２の内部機構が所与のスケジュー リングに対して首尾一貫のままとなることを確実にするようにＰＵＳＨＣ命令お よびＰＯＰＣ命令 によって実行されるべきである。しかしながら、ＣＰＵ５０は、内部機構に影響 を及ぼさないで他の適当な命令を使用していつでも一次スコアボードエントリあ るいは接続ＩＤテーブルエントリを読み出すことができる。 ６．５ 一次スコアボードサイズの選択 所望の一次スコアボードのサイズ、すなわち最寄りの２の冪乗に切り上げられ た数はＣＳＳ構成レジスタで指定することができる。２の冪乗以外の一次スコア ボードサイズは、ＣＰＵ５０があるスコアボードロケーションを使用不可能とマ ークを付けることによって使用可能にすることができる。例えば、所望のスケジ ューリングサイズは２３０４ビットであるならば、ユーザは、これらのロケーシ ョンの一連のＰＵＳＨＣ動作を実行することによって４０９６ビットスケジュー リングを選択でき、ビット２３０４〜４０９５を使用不可能とマークを付ける。 このことから、ＣＳＳ５６は、ＣＰＵ５０によって出されたセルスケジューリン グリクエストに応じてこれらのロケーションを予備として残しておくように試み ない。しかしながら、ＰＯＰＣ命令を使用して一次スコアボードを詳しく点検す るユーザは、ロケーション２３０３に到着する際にスコアボードの始めに注意深 く戻るべきである。換言すると、一旦不必要なロケーションが予約されてしまう と、このロケーションは、ＰＯＰＣ命令の目的アドレスとして指定されるべきで ない。さらに、ＣＰＵ５０は、モジュロ４０９６の代わりにＰＵＳＨＣの目的ア ドレスモジュロ２３０４を計算すべきである。 ６．６ 多重スケジューリングの使用 ＡＴＭセルプロセッサ１２は、多重スコアボードおよび接続ＩＤテーブルを使 用して多重セル処理スケジューリングをサポートするように構成することができ る。例えば、所与の実施例において、システム１０は、８つの２Ｋ接続ＩＤテー ブル、４つの４Ｋ接続ＩＤテーブル、２つの８Ｋ 接続ＩＤテーブルあるいは１つの１６Ｋ接続ＩＤテーブルまでサポートするのに 十分な制御メモリ２２を含むように構成できる。前述のように、ＣＳＳ構成レジ スタのビットはスコアボードサイズを選択するために使用することができる。８ つのスケジューリングが使用される場合、ＰＵＳＨＣおよびＰＯＰＣｒｓｂアド レスビット１２〜１４は、８つのブロック内で１つのスケジューリングを選択す るために使用できる。４つのスケジューリングが使用される場合、ｒｓｂアドレ スビット１３〜１４は４つのブロック内で１つのスケジューリングを選択するた めに使用できる。他の多重スケジューリングの数は同様に構成および選択できる 。 ７． ＣＳＳ動作の例 図７は、本発明によるセルスケジューリングおよびサービスの動作例を示して いる。接続ＩＤテーブル２１０は、制御メモリ２２にあるいはＡＴＭセルプロセ ッサ１２あるいはシステム１０の他の適当なロケーションに保持されている。こ の実施例の接続ＩＤテーブル２１０は、多数のポインタＰＴＲｉ，ｉ＝１、２、 ...Ｎの形式のエントリを含むものとして示されている。各ポインタは、一次ス コアボード２００のビットロケーションＢ［ｉ］に対応する。ＣＰＵ５０は、Ｒ ７と示される典型的なレジスタに、接続ＩＤテーブル２１０の目的ロケーション を識別するハーフワードアドレスを示す値、したがって現伝送時間のための目的 タイムスロットを保持する。この例において、レジスタＲ７は、ハーフワードア ドレス０２に対応するので、接続ＩＤテーブル２１０の第３のロケーションを識 別するバイトアドレス０４を含んでいる。テーブル２１０の第３のロケーション は、スコアボード２００の第１のラインの右側から第３番目のビットである第３ の一次スコアボードビットＢ［２］を示している。ビットＢ［２］はスコアボー ド２００の論理‘１’である。ＵＴＯＰＩＡポート６４の送信待ち行列が満杯で ないと仮定すると、ＣＰＵ５０は、下記のようにｐＯＰＣ命令を実行することに よって接続ＩＤテーブル２１０からエ ントリＰＴＲ２を読み出す。 ＰＯＰＣ Ｒ１０ ＠Ｒ７ ＣＳＳ５６は、ＰＴＲ２にある接続ＩＤをＣＰＵレジスタＲ１０に書き込み、 この接続ＩＤテーブルエントリに関連した一次スコアボードビットＢ［２］をＡ ＣＦＲにコピーし、それからスコアボードビットＢ［２］をクリアすることによ ってこのＰＯＰＣ命令に応答する。スコアボード２００のビット［２］は、ＰＯ ＰＣ命令が実行された時点で‘１’であるために、ＡＣＦＲは１にセットされる 。スコアボード２００’は、上記のＰＯＰＣ命令の実行後スコアボード状態を示 し、ビットＢ［２］がゼロにクリアされたことが分かる。次に、ＣＰＵ５０は、 ＡＣＦＲに接続された外部状態信号（ＥＳＳ）ラインをアクセスするために条件 分岐命令を使用してＡＣＦＲをチェックする。ビットＢ［２］に対応する指定さ れたタイムスロットが割り当てられたために、ＣＰＵ５０は、制御メモリ２２を アドレス指定し、タイムスロットを予約したＶＣのためのチャネル記述子をそこ から引き出すためにレジスタＲ１０に戻された接続ＩＤを使用する。それから、 ＣＰＵ５０は、ＳＡＲ応用のこのＶＣのためのセルを形成するか、トラフィック ・シェイピング応用のこのＶＣのための予め記憶されたセルを引き出すために引 き出されたチャネル記述子の情報を使用する。ダイナミックスケジューリングに 関するＳＡＲ応用において、ＣＰＵ５０は、チャネル記述子に記憶されたパラメ ータを使用する前述のＧＣＲＡ（Ｉ，Ｌ）アルゴリズムを実行することによって 次に接続がサービスされるべき時を決定できる。チャネル記述子は、一般的には 、目的スケジューリング時間と、ＩＣＩと、限界と、ＩＣＩが端数整数の場合、 余りの端数とを含んでいる。この情報から、ＣＰＵ５０は、所与のＶＣのために スケジューリングされるべきである接続ＩＤテーブル内で次のロケーションを決 定し、この結果をレジスタＲ２２のような典型的なレジスタに入れる。 次に、ＣＰＵ５０は、下記のＰＵＳＨＣ命令を実行することによってアクティ ブとして接続をスケジューリングする。 ＰＵＳＨＣ Ｒ１０ ＠Ｒ１９ この命令に応じて、ＣＳＳ５６は、レジスタＲ１９によって示された接続ＩＤテ ーブルアドレスに対応するスコアボードビットＢ［２２］で始まるスコアボード ２００’を検索する。この例では、ＣＳＳは、ビットＢ［２２］がスコアボード ２００’で‘１'にセットされるという事実によって示されるように、目的ロケ ーションが前の接続によって既に予約されたことを探す。したがって、ＣＳＳは 、使用可能なロケーションを探すまで、スコアボード２００’を検索し続ける。 使用可能なロケーションには、スコアボードビットＢ［２４］が論理“０”トさ れるという事実によって示されるように、Ｂ［２２］目的ロケーションから離れ て２つのセルスロットがある。次に、ＣＳＳ５６は、ビットＢ［２４］を‘１’ にセットし、レジスタＲ１０においてＣＰＵ５０によって供給された接続ＩＤを ＰＴＲ２４と示されたロケーションの接続ＩＤテーブル２１０に書き込むことに よって現接続のためのロケーションを予約する。スコアボード２００’’は、上 記のＰＵＳＨＣ命令の実行後のスコアボード状態を示している。ＣＰＵ５０は、 次の送信タイムスロット上に移すために、レジスタＲ７にあるサービスアドエＷ スすなわちこの例では４０９６であるスコアボートサイズを法とした数を増分す ることによって接続サービスおよび再スケジューリング処理を完了する。 ８． 二次スコアボードを使用する制限一次スコアボード検索 ＣＳＳ５６は、適当に制限された時間内に一次スコアボードの任意の開始ロケ ーションから単一の使用可能なセルタイムスロットを突き止める能力を備えるこ とがでぎる。例えば、１６３８４セルタイムスロットを有する実施例の全一次ス コアボードは、約８つの３２ビットの制御メモリ読み出しサイクル内にスコアボ ードの任意の開始位置から検索できる。本発明は、ここで二次スコアボードと呼 ばれる第２のビットマトリックスを発生し、保持することによってこの制限検索 時間機能を備えている。二次 スコアボードは、一般に前述の一次スコアボードよりも小さいので、通常外部制 御メモリ２２においてよりもむしろセルプロセッサ１２の内部のメモリロケーシ ョンに保持されている。二次スコアボードは、ＣＳＳ５６に一次スコアボードの 全密度に関する情報を供給する。より詳細には、二次スコアボードは、使用可能 なタイムスロットに対応するビットを含むことが既知である一次スコアボードの 領域の一次スコアボードの検索をＣＳＳ５６が命令するために使用する。したが って、一次スコアボード検索は直線的に進行する必要がなく、その代わりに、検 索は、二次スコアボード情報によって識別された領域に最初に命令され、次に、 使用可能なタイムスロットが５８個探し出されるまで、識別領域中を直線的に進 行する。指定領域のサイズが十分小さく形成されるならば、このような領域の線 形検索は速く実行でき、しっかりと制限された検索時間になる。二次スコアボー ドは、ビット群あるいは他の情報要素を記憶するのに適しているメモリロケーシ ョンのマトリックス、アレイあるいは他のメモリロケーションセットとしてセル プロセッサ１２の適当なメモリロケーションに記憶されている。前述のように、 一次スコアボードおよび／または接続ＩＤテーブルは、セルプロセッサ１２の内 部のメモリロケーションにも記憶することができる。 所与の二次スコアボードビットは、一次スコアボードの８つの１６ビットライ ンあるいは１２８の一次スコアボードビットの合計状態を示すように構成できる 。論理レベル‘０’の二次スコアボードビットは、１２８の一次スコアボードビ ットの少なくとも一つが一つの利用可能なタイムスロットを示していることをＣ ＳＳ５６に示している。論理‘１’レベルの二次スコアボードビットは、１２８ の一次スコアボードビットのすべてが使用不可能タイムスロットを示しているの でこの一次スコアボードの領域を検索する必要が全然ないことをＣＳＳ５６に示 している。もちろん、多数の他の二次スコアボード構成が可能である。 前述の典型的な二次スコアボードは、部分的にはダイサイズとスケジ ューリング時間との間のトレードオフを示している。前述のように、各二次スコ アボードビットは１２８の一次スコアボードビットの状態を示している。したが って、この領域が使用不可能である場合、二次スコアボードは一次スコアボード の特定の領域を避けるようにＣＳＳに命令することができる。しかしながら、所 与の領域に使用可能なタイムスロットがある場合、二次スコアボードは、８つの １６ビットラインの中のどれが使用可能なスロットに対応するビットを含むかを ＣＳＳに示すことができない。したがって、ＣＳＳは、使用可能ビットを検出す るために全て８つのラインの読み出しをしなければならないこともある。しかし 、１０２４あるいはそれ以上の１６ビットラインもの中から８つの１６ビットラ インに一次スコアボード検索を命令することによって、二次スコアボードは、こ の例では検索時間を本質的には４つの３２ビットの読み出しサイクルに制限した 。したがって、ＣＳＳ５６は、使用可能なセルタイムスロットを検索するときに 多数のライン中を走査する必要がない。二次スコアボードによって伝達される情 報は、セルスケジューリング時間をさらに減少させるように増加することができ るが、付加的メモリ、したがって増加されたダイサイズという犠牲を払っている 。それとは別に、二次スコアボードをアクセスするのに必要な付加的メモリ読み 出しサイクルは処理速度に影響を及ぼすけれども、二次スコアボードは外部メモ リに保持することができる。 上記の例において、二次スコアボードは、１２８の一次スコアボードビットの 状態を示すために単一ビットを使用する。１０２４ライン、すなわち１６３８４ ビットまでの任意のサイズにプログラム化できる一次スコアボードを示すために 使用される場合、二次スコアボードのサイズは１６３８４／１２８ビットあるい は２５６ビットであるべきである。検索時間は、二次スコアボードをより大きく することによってさらに減少することができる。例えば、ビットの数は、５１２ まで増加することができ、それによって各二次スコアボードビットは２つの一次 スコアボードライン の合計状態を示すことができる。これは、一次スコアボード検索を２読み出しサ イクルだけ減少させるが、付加的内部メモリ空間、したがってダイ領域という犠 牲を払っている。 この典型的な実施例の二次スコアボードは一次スコアボードで実行されるＰＵ ＳＨＣ動作およびＰＯＰＣ動作毎に監視すべきである。さらに、この実施例の一 次スコアボードで実行される毎ＰＵＳＨＣ動作は、二次スコアボードがブロック の使用可能性を監視できるように１２８ビットブロックの全て８つの１６ビット ラインを検索すべきである。ユーザがＰＵＳＨＣ命令を出す場合、ユーザは、セ ルをスケジューリングするために使用することができる一次スコアボード内の最 初のビット位置を示すＣＳＳ５６にアドレスを生じる。次に、ＣＳＳ５６は、こ の時間のあるいはこの時間後の第１のロケーションを探し、それを予約済みとマ ークを付ける責任を負う。ＣＳＳ５６は、第１の使用可能なビットのオフセット がブロックの中でより深いかどうかにかかわらず１２８ビットブロックの第１の ラインに対するその検索を開始する。これは、使用可能なビットが検出され、セ ットされるならば、使用可能なビットが、全て１２８ビットを調べずにはできな い１２８ビットブロックの最後のビットであったかどうかを決定する必要がある ためである。したがって、ＣＳＳ５６は、開始オフセットとは無関係に全て８つ の１６ビットラインを読み出す。ＣＳＳ５６は、使用可能なビットが検出され、 セットされ、このビットが１２８ビットブロックの最後のビットであることがわ かると、二次スコアボードの対応するビットをセットする。したがって、１２８ ビットブロックは、全体を使用不可能とマークを付けられているので、将来のス ケジューリングリクエストはこの使用不可能ブロックおよび他の使用不可能ブロ ックの周りに向けることができる。ＣＳＳ５６が対応する１２８ビットブロック 内のロケーションにアドレス指定するＰＯＰＣ命令を受け取るや否やＣＳＳ５６ は二次スコアボードビットをクリアする。これは、使用可能なロケーションが対 応するブロックで保証されるように、ＰＯＰＣ命令は一次 スコアボードの目的ビットをクリアするためである。 図８は、二次スコアボードを使用する典型的な検索処理を示すフロー図である 。ＰＵＳＨＣ命令は、ステップ２５０で受け取られ、前述のように一般的には接 続ＩＤおよび目的セルタイムスロットを指定する。目的ロケーションに対応する ビットを含む一次スコアボードビットの１２８ビットブロックが引き出され、検 索される場合、一次スコアボード検索処理はステップ２５２で開始する。ＣＳＳ ５６の一次スコアボードコントローラは、目的ロケーションのあるいは目的ロケ ーションの後の使用可能なセルタイムスロットのために引き出された１２８ビッ トの一次スコアボードブロックの全て８つの１６ビットワードを走査することに よって検索を実行できる。ＣＳＳ５６の二次スコアボードコントローラは、ある ロケーションが１２８ビットブロックで使用可能であるかどうかを知っているが 、このロケーションが目的時間あるいは目的時間後にあるかどうかは知らない。 したがって、一次スコアボードコントローラは、ブロックの第１のワードで始ま る一次スコアボードの全て８つの１６ビットラインを検索する。このコントロー ラは、目的ロケーションに対応するビット位置に到達するまで使用可能なビット を無視するが、目的ビットがブロックの最後の使用可能なビットであると分かる 場合、目的ロケーションまでその密度に注目する。ステップ２５４は使用可能な スロットが検索されている一次スコアボードブロックで突き止められたかどうか を決定する決定動作である。使用可能なセルタイムスロットが引き出された一次 スコアボードブロックで全然検出されない場合、ステップ２５６は、二次スコア ボードを利用して使用可能なタイムスロットを含むものと知られている次の一次 スコアボードブロックのアドレスを決定するために使用される。次に、この次の 一次スコアボードブロックはステップ２５８に示されるように引き出され、検索 される。第１あるいは次の一次スコアボードブロックが使用可能なセルタイムス ロットを示すビットを含むことが検出された場合、対応する一次スコアボードビ ットはスロットを予約すようにセットさ れ、ＶＣのための接続ＩＤは、ステップ２６０に示されるように接続ＩＤテーブ ルの適当なロケーションに記憶される。次に、ブロックに示される任意の他の使 用可能なセルタイムスロットがあるかどうかに関する決定がステップ２６２で行 われる。一次スコアボードブロックのビットに対応するセルタイムスロットが完 全に利用されない場合、この処理は二次スコアボードビットを変更しないで終了 する。セルタイムスロットが現スケジューリングリクエストの結果として完全に 利用される場合、ステップ２６４の二次スコアボードコントローラは、一次スコ アボードの現在完全に予約されたブロックに対応する二次スコアボードビットを セットする。したがって、目的ビットよりも前に検出された使用可能ビットが全 然ないと仮定すると、一次スコアボードコントローラは所与の一次スコアボード ブロックの全て８つの１６ビットのラインの読み出しを終了しなければならない ので、一次スコアボードコントローラが第２の使用可能なビットを検出しない場 合、１２８ビットのブロックが現在完全に利用されていることを二次スコアボー ドコントローラに知らせることができる。 一次スコアボードコントローラが、第１の一次スコアボードブロックのビット が全然使用可能でないことを検出するならば、図８のステップ２５６および２５ ８に示されるように次のブロックの使用可能なビットを検索し続ける。したがっ て、二次スコアボードは、一次スコアボードコントローラが完全に使用不可能で ある任意の次のブロックを検索することを防止するために使用される。一次スコ アボードコントローラは一次スコアボードの最初の検索を行うが、二次スコアボ ードコントローラは二次スコアボード中を走査する。一次スコアボード検索が使 用可能なビットを検出できない場合、二次スコアボードコントローラは、満杯で ない一次スコアボードの次のブロックのアドレスに関して待機する。次のブロッ クが目的ロケーションの後に位置するため、かつ二次スコアボードがこのブロッ クのビットが使用可能であると示しているために、一次スコアボードコントロー ラによる次の検索が使用可能なビットを検出することを保証する。 したがって、二次スコアボードの使用は、検索時間を８つの３２ビットの一次ス コアボード読み出しサイクル、すなわち、２×４の３２ビットワード、すなわち ２×８の１６ビットワードに制限される。第二の一次スコアボードブロックの検 索が必要である場合、この検索は、第２のブロックが唯一の残りの使用可能なビ ットを有する場合、１２８ビットのブロックの全て８つの１６ビットラインを読 み出すことができることが明らかであるはずである。次のブロックの最後の残り の使用可能なビットが検索の結果としてスケジューリングされる場合、一次スコ アボードコントローラは、二次スコアボードコントローラに、二次スコアボード の対応するビットをセットするように命令する。ＶＣが再スケジューリングされ る場合、現タイムスロットは、ＰＯＰＣサービス命令に応じて丁度クリアされる ために一般に使用可能であることに注目すべきである。したがって、再スケジュ ーリングＰＵＳＨＣ命令は、現タイムスロットがスコアボードの唯一の使用可能 なスロットである場合、最悪の最大検索時間を受ける。現タイムスロットは、ビ ットがスコアボードサイズに等しい多数のＰＯＰＣ命令が実行されるまで、一般 に再びサービスされない。 ９． ＣＢＲ接続のためのバンド幅の予めの予約 ＡＴＭセルプロセッサ１２は、ユーザがＣＰＵ５０によって実行されるアルゴ リズム機能およびＣＳＳ５６によって実行されるハードウェア支援機能の組合わ せによる多数の異なるスケジューリング方法論を実行することができる点で非常 に汎用性がある。例えば、ＡＴＭセルプロセッサ１２は、一定のビット伝送速度 （ＣＢＲ）が必要である接続のためのバンド幅の予めの予約をサポートできると 同時に可変ビット伝送速度（ＶＢＲ）を必要とする接続がＣＢＲ接続のために予 め予約されないセルタイムスロットでスケジューリングできる。セルプロセッサ １２によって、所与のユーザが一次スコアボードにおいて所望の数のロケーショ ンを予め予約できる。ユーザは、いくつかの異なる方法でこれを行うことができ る。 セルプロセッサ１２の初期設定で、ユーザは、一連のＰＵＳＨＣ命令を出すこと によって目的ロケーションを予約できる。ＰＯＰＣ命令を使用して予め予約され たロケーションのサービスをリクエストした後、ユーザは、この同じロケーショ ンを指定する接続を直ちに再スケジューリングする。これは、同じＶＣのための ロケーションを再スケジューリングし、実際はＰＯＰＣ命令のクリア動作を抑え る。ユーザは、接続が半永久的に予約されるべきかどうかを決定することもでき る。所与の接続がＣＢＲ接続としてマークを付けられ、対応するロケーションが 適当なＰＵＳＨＣ命令を出すことによってＰＯＰＣ命令直後に再予約されるファ ームウェア機能が実行できる。 １０． トンネリング ＡＴＭセルプロセッサ１２はトンネリング応用を支援できる。典型的なトンネ リング応用では、ユーザは、ＣＢＲ仮想パス（ＶＰ）接続を確立し、それからそ れの上部の一連の仮想チャネル接続をトンネルするリクエストを出すことができ た。ユーザは、一次スコアボードによって示されたセルスケジューリングの多数 のエントリを予約するバンド幅機構の前述の予めの予約を使用できた。ユーザは 、接続が所望のバンド幅量を有することを保証するのに十分なエントリを予約す る。実際は、ユーザはＶＰベースのトンネルのためのバンド幅を予約する。それ から、ユーザは、ＶＰを介して移動する一連の仮想チャネル接続を構成する。こ れを行うために、ユーザは、ＶＰのバンド幅をＶＰを介して移動する仮想チャネ ル接続の間に分ける。この処理は、仮想チャネル接続がビット伝送速度が時間に わたって変化できる使用可能なビット伝送速度（ＡＢＲ）接続であり得るという 事実によって複雑になる可能性がある。 図９は、本発明によるトンネリング動作を管理する典型的な技術を示している 。ＡＴＭセルプロセッサ１２は、２つの異なる種類の一次スコアボードを使用す るトンネリング動作を管理する。この例で使用される第１の 種類の一次スコアボードは、マスタスコアボードと呼ばれ、スコアボード３００ として図９に示される。それの３つがスコアボード３１０、３２０および３３０ として図９に示された第２の種類の一次スコアボードは、トンネル制御スコアボ ードと呼ばれる。４つのスコアボード３００、３１０、３２０および３３０の各 々は、前述の一次スコアボードと同様に制御メモリ２２に構成できる。マスタス コアボード３００は、実際の伝送リンクのためのセルスケジューリングを管理す るために使用される。マスタスコアボード３００は、ＶＰ１、ＶＰ２およびＶＰ ３と示された３つのＶＰトンネルのために永久に予約された多数のセルタイムス ロットを有し、スロットの残りは、前述のようにアクセスするための非トンネル 接続に使用可能である。 所与のユーザがトンネルＶＰ１、ＶＰ２あるいはＶＰ３のためのマスタスコ アボード３００のロケーションを予め予約する場合、対応するトンネル制御ボー ド３１０、３２０および３３０は制御メモリ２２のユーザによってセットアップ される。各トンネル制御ボードは、対応するトンネルを使用する接続をスケジュ ーリングするために使用される。トンネル制御ボードは一般的にはマスタースコ アボードと同じサイズである。ユーザは、マスタスコアボードの対応するトンネ ルのために選択されたロケーションには対応しないトンネル制御ボードの全ての ロケーションを使用不可能としてマークを付ける。ユーザは、マークスコアボー ドのこのトンネルのために予約されたロケーションに対応しない所与のトンネル 制御ボードの各ロケーションに一連のＰＵＳＨＣ命令を出すことによってこのマ ーキング動作を実行できる。一連のＰＵＳＨＣ命令を完了した後、ユーザはスケ ジューリング動作を開始できる。ユーザは、スケジューリングリクエストが適当 な予約ビットロケーションに向けられるように対応するトンネル制御ボードの所 与のトンネルのためのトンネル接続をスケジューリングする。 次に、スケジューリングリクエストは下記のようにサービスできる。 ユーザは、前述のようにＰＯＰＣ命令を出す。ＰＯＰＣ命令がトンネルのために 予約されるマスタスコアボードのロケーションを示す場合、トンネル制御ボード の対応するロケーションは、スケジューリングリクエストがこのロケーションの ために入力されたかどうかを決定するために自動的にチェックされる。リクエス トが入力された場合、ＣＳＳ５６は、リクエストをサービスし、それからＰＵＳ ＨＣ命令をトンネル制御ボードの目的ロケーションに出すことによって接続を再 スケジューリングする。この目的ロケーションは、前述された方法でＧＣＲＡを 使用して決定できる。次に、ユーザはマスタスコアボードのこのロケーションを 再予約する。マスタスコアボードおよびトンネル制御ボードの両方を使用するこ とによって、ユーザはマスタスコアボードを使用することによってＶＰのための 伝送リンク上のＣＢＲセルストリームを予約できると同時に個別のＶＣのための スケジューリングＶＢＲあるいはＡＢＲはトンネル制御ボードを使用する。 １１． 完全独立速度 本発明のＡＴＭセルプロセッサ１２は、異なるＶＣ中に全速度独立性を可能に する。これは、一般的にはサービス間隔を形成するためにタイマのタイムアウト によるので、利用可能にできる異なる速度数に制限される従来のセルプロセッサ とは著しく違っている。セルプロセッサ１２において、各ＶＣは、他のＶＣの速 度から独立して処理される固有な速度を有することができる。この速度は、ＣＰ Ｕ５０およびＣＳＳ５６が前述のようにＶＣのための目的スケジューリング時間 を決定するために使用できる。所与の接続の速度が、しばしばＡＢＲ ＶＣに関 する場合のように、ＡＴＭネットワークからのフィードバックに基づいて変更さ れる場合、代わりにＣＳＳ５６は、スケジューリング機構を変える必要がない。 ＣＳＳ５６は、速度および対応する間隔を再計算し、次のスケジューリングリク エストで再計算間隔を与える。 １２． 本来公正なバンド幅割り当て セルプロセッサ１２は、例えばいずれかの１回に所与のＶＣのための一次スコ アボード上に存在する単一のスケジューリングリクエストだけを必要とするよう に構成できる点で本来公正なセルスケジューリングを実行する。他の接続がアク ティブになる場合、この接続は、使用可能なリンクバンド幅に等しいアクセスを 直ちにできる。これは、アクティブ状態を保持するために単一ＶＣのための複数 のスケジューリングリクエストを必要とする場合がある従来技術のセルスケジュ ーリングシステムのかなりの改良を示している。このような従来技術システムで 得られるスケジューリングは、現在のユーザのトラフィックで輻輳になる可能性 があり、それによって新しいユーザがバンド幅の公正な割り当てをするのを困難 にする。 １３． スケジューリングリクエストの多重レイヤ 本発明の他の実施例は、単一伝送リンクのための複数の一次スコアボードを備 え、ＰＯＰＣ命令はこれらの複数のスコアボードを走査できる。例えば、高い優 先順位トラフィックは、一方の一次スコアボードでスケジューリングできるのに 対して、低い優先順位トラフィックは第２の一次スコアボードでスケジューリン グされる。これは、低い優先権スケジューリングリクエストは高い優先順位リク エストと干渉しないことを確実にする。それから、ＰＯＰＣ命令は、高い優先順 位のスコアボードを最初にチェックするために実行でき、ロケーションが検出さ れなかった場合、より低い優先順位スコアボートをチェックできる。ＡＴＭセル プロセッサは、より低い優先順位のための“バブル”カウントを保持できた。バ ブルカウントは、より高い優先順位がサービスされる度に、増分され、割り当て られていないスロットがより低い優先順位スコアボードから廃棄される度に、減 分される。より低い優先順位スコアボードためのスケジューリング リクエストは、（目的時間＋バブルカウント）で行われる。したがって、より高 い優先順位ボードは、より低い優先順位スコアボードに対する外部セル発生源を 示している。ここで使用されるような用語“バブルカウント”は、ソフトウェア 、ハードウェア、ファームウェアで実行されようとも、所望の計数機能をもたら すそれの組合わせで実行されようとも任意の種類のカウンタによって供給される カウントを含むことを意図されている。 本発明の他の代替実施例は異なるセル速度に対する異なる一次スコアボードを 提供できる。高いセル速度での接続は、一方のスコアボードでスケジューリング でき、より低い速度での接続は、他方のスコアボードでスケジューリングできる 。これは、多数の低いバンド幅ＶＣが一緒にグループ化され、延長された時間高 速度接続を妨げることを防止する。 １４． 外部ＡＴＭセル多重化 本発明のセルスケジューリング技術は、所与のＡＴＭ伝送リンクへのアクセス をリクエストする外部セル発生源に適合するために利用できる。この外部セル発 生源は、多数のセルタイムスロットを消費し、ＣＳＳ５６が伝送リンクへのアク セスすることを阻む。このような実施例では、ＣＳＳ５６は、外部セル発生源か らのセルと内部発生セルと混ぜる責任を負うことができる。外部セルは内部発生 セルよりも高い優先順位のものであると仮定すると、セルプロセッサ１２は、そ のスケジューリングを通して一時的に続けることができないこともある。セルプ ロセッサが再びスケジューリングを通して続けることができる場合、さらに時間 を引き延ばして存在するスケジューリングリクエストは必要よりも長く待つ。し たがって、セルプロセッサは、予めスケジューリングされたロケーションと現サ ービスアドレスとの間に存在するいかなるスケジューリングされていないロケー ションにもスキップし、次のスケジューリングされたロケーションに直接進むよ うに構成できた。このことによって、時間的にさらに引き延ば してスケジューリングされた接続があまりにも早くサービスされることになるが 、高い優先順位の外部セルがセルストリームに多重化されている間のスケジュー ルサービスの中断によって、未使用スロットは、末使用スロットに従うピークセ ル速度の接続を妨害することなしになくなることができる。 前述の多重レイヤスケジュールにおけるように、ＡＴＭセルプロセッサは、外 部セル発生源がある場合、バンド幅の有効な利用を生じるようにバブルカウント も利用できる。このような実施例のバブルカウントは、一次スコアボードでスケ ジュールされなかったＡＴＭ伝送リンク上に送られたセル数を示すことができる 。したがって、バブルカウントは、いかなるトラフィック・シェイピング違反も 生じなくて一次スコアボード上で割り当てられていないスロットに遭遇する場合 、廃棄することができる割り当てられていないスロット数も示している。行われ る全スケジューリングリクエストは、（目的時間＋バブルカウント）に対応する 時間にスケジューリングされるべきである。このようにバブルカウントを目的時 間に加えることは一般にサービス時間を増加させない。これは、他のリクエスト が目的時間あるいは目的時間後に存在するならば、リクエストはとにかく次から 次へと出され、他のリクエストが目的時間あるいは目的時間後に存在しないなら ば、生じるアイドルスロットは結局は廃棄されるためである。割り当てられてい ないスロットに一次スコアボードで遭遇する場合、バブルカウントはゼロでなけ れば、割り当てられていないスロットは、伝送するために待ち行列に入れられた アイドルセルの代わりに廃棄される。セルプロセッサは、一次スコアボードの次 のロケーションに直ぐに進む。バブルカウントは、そのとき１だけ減少される。 セルプロセッサが一次スコアボードで割り当てられていないスロットに遭遇し、 バブルカウントがゼロである場合、スロットは廃棄されなくて、セルプロセッサ は、その代わりに伝送リンク上でアイドルセルを待ち行列に入れる。 ＣＰＵ５０は、目的アドレスを指定し、現バブルカウントに等しい範 囲を利用するｐｏｐレンジ（ＰＯＰＲ）命令を含むように構成できた。ＰＯＰＲ 命令は、目的アドレスと（目的アドレス＋バブルカウント）との間のセットビッ トのために一次スコアボードを走査するようにＣＳＳ５６に命令する。セットビ ットが範囲内でセットされているのが全然検出されない場合、ＣＳＳ５６はＡＣ ＦＲをクリアし、バブルカウントはゼロにリセットされる。セットビットが範囲 内で検出される場合、ＣＳＳ５６はＡＣＦＲをセットし、接続ＩＤテーブルの対 応するエントリを戻し、バブルカウントは、セットビットの目的ロケーションと 実際のロケーションとの間のロケーションの数だけ減少される。前述されるよう に、このバブルカウント機構はセルプロセッサ１２のＣＰＵ５０を使用してソフ トウェアで実行できる。それとは別に、バブルカウント機構は、セルプロセッサ １２のＣＳＳ５６あるいは他のどこか内部で実行される別個のハードウェアおよ び／またはファームウェア機能であってもよい。 前述の記載は本発明の単なる例示であることを理解すべきである。添付クレー ムの範囲内の多数の他の実施例は当業者に明らかである。

【手続補正書】特許法第１８４条の８第１項 【提出日】平成９年１２月３日（１９９７．１２．３） 【補正内容】 （請求の範囲の差し替え頁の翻訳文） 請求の範囲 １． 非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の情報要素群の各要素がセルタイムスロットを示す第１の情報要素群 を発生するステップであって、前記第１の群の所与の要素の値が対応するセルタ イムスロットが伝送のために使用可能であるか否か示すこと、 第２の情報要素群の各要素が第１群の情報要素のブロックに対応し、かつ 情報要素の対応するブロックが使用可能なセルタイムスロットを示す少なくとも １つの情報要素を含むかどうかを示す、第２の情報要素群を発生するステップと 、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素群を検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に識別された要素を変更することによって前記仮想接続による使用のための前記 使用可能なタイムスロットをスケジューリングするステップとを含むことを特徴 とする非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 。 ２． 前記情報要素がビットであり、前記第１の群の各ビットがセルタイムスロ ットを示し、かつ前記第２の群の各ビットが少なくとも１つのタイムスロットが 前記第１の群のビットのブロックで使用可能であるかどうかを示すことを特徴と する請求項１の方法。 ３． 前記接続識別子を前記識別されたビットに対応する接続識別子テーブルロ ケーションに記憶するステップをさらに含むことを特徴とする請求項１８の方法 。 ４． 前記仮想接続のためのセルの伝送を命令するステップがスケジューリング されたセルタイムスロット中伝送のための仮想接続のためのセルを構成するステ ップをさらに含むことを特徴とする請求項１９の方法。 ５． 前記仮想接続のためのセルの伝送を命令するステップが、前記スケジュー リングされたセルタイムスロット中伝送のために前記仮想接続のための予め構成 されたセルを引き出すステップをさらに含むことを特徴とする請求項５の方法。 ６． 使用可能なセルタイムスロットが第１のビット群の第１のビットのブロッ クで全然突き止められない場合、使用可能なセルタイムスロットを示すビットを 含む第１のビット群の次のビットのブロックを識別するために第２のビット群を 使用するステップをさらに含むことを特徴とする請求項２０の方法。 ７.使用可能なセルタイムスロットを示すビットを含む第１のビット群の次のビ ットのブロックを引き出すステップと、 前記使用可能なセルタイムスロットを示すビットを突き止めるために次の ビットのブロックを検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に前記使用可能なタイムスロットを示すビットを変更することによって前記仮想 接続による使用のための前記使用可能なタイムスロットをスケジューリングする ステップと、 前記次のブロックが他の使用可能なセルタイムスロットを示す任 意の他のビットを含むかどうかを決定するステップと、 他の使用可能なセルタイムスロットを示す次のブロックに他のビットが全 然ない場合、前記第１の群の次のブロックが使用不可能なセルタイムスロットに 対応するビットだけを含むことを示すために第２のビット群のビットを変更する ステップとをさらに含むことを特徴とする請求項６の方法。 ８． 非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の要素群の各要素がセルタイムスロットを示す第１の情報要素群を発 生するステップであって、前記第１の群の所与の要素の値が対応するセルタイム スロットが伝送のために使用可能であるか否か示すこと、 仮想パス接続のための伝送リンクに少なくとも１つのセルタイムスロット を予約するステップと、 前記情報要素が前記予約セルタイムスロットが使用不可能であることを示 すように前記仮想パス接続のために予約されたセルタイムスロットに対応する第 １の情報要素群に情報要素をセットするステップと、 トンネル制御情報要素群を発生するステップとを含み、前記トンネル制御 群の各情報要素が伝送リンクのセルタイムスロットに対応し、前記トンネル制御 群情報要素の各々が前記仮想パス接続のために予約されたスロットに対応し、第 １の方法でセットされた情報要素が使用可能なタイムスロットを示し、かつ第２ の反対の方法でセットされた全ての他のトンネル制御群情報要素が使用不可能な タイムスロットを示すことを特徴とする非同期転送モード（ＡＴＭ）通信システ ムにおいてセルを割り当てる方法。 ９． 前記情報要素がビットであり、かつ 前記仮想パス接続に対応するサービスリクエストを受け取るステ ップと、 前記仮想パス接続のための前記トンネル制御ビット群を検索し、セルタイ ムスロットが対応するロケーションのためにスケジューリングされたかどうかを 決定するステップと、 前記タイムスロットが前記対応するロケーションのためにスケジューリン グされた場合、スケジューリングされたセルタイムスロットのセルの伝送を命令 するステップと、 前記対応するセルタイムスロットがスケジューリングのために再び使用可 能であることを示すために前記トンネル制御ビット群の対応するビットをリセッ トするステップと、 前記ビットが前記予約セルタイムスロットが使用不可能であることを示す ように前記仮想パス接続のために予約された前記セルタイムスロットに対応する 第１のビット群のビットをセットするステップとをさらに含むことを特徴とする 請求項８の方法。 １０．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１のビット群の各ビットがセルタイムスロットを示す第１のビット群を 発生するステッブであって、前記第１のビット群の所与のビットの値が、対応す るセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 第２のビット群の各ビットが、前記第１のビット群のビットのブロックに 対応し、前記対応するビットのブロックが使用可能なセルタイムスロットを示す 少なくとも１ビットを含むかどうかを示す第２のビット群を発生するステップと 、前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエストに応 じて検索される前記第１のビット群のブロックを決定するために第２のビット群 を使用するステップとを含むことを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおい てセルを割り当てる方法。 １１．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を記憶す る第１のメモリロケーション群であって、第１のビット群の所与の要素の値が対 応するセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 第２の情報要素群の各要素が、前記第１の要素群の情報要素のブロックに 対応し、かつ前記対応する要素のブロックが使用可能なセルタイムスロットを示 す少なくとも１ビットを含むかどうかを示す第２の情報要素群を記憶する第２の メモリロケーション群と、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素の群を検索し、かつ前記使用可能なタイムスロットがスケジュールされ たことを示すように識別された要素を変更することによって前記仮想接続によっ て使用するための使用可能なタイムスロットをスケジューリングするように作動 するプロセッサとを備えていることを特徴とする非同期転送モード（ＡＴＭ）通 信システムにおいてセルを割り当てる際に使用するための装置。 １２．前記第１の情報要素群が、各ビットがセルタイムスロットを示す第１のビ ット群として構成されることを特徴とする請求項１１の装置。 １３.第１のビット群および接続識別子テーブルを記憶するメモリをさらに含み 、前記接続識別子が前記識別されたビットに対応するメモリロケーションに記憶 されることを特徴とする請求項１２の装置。 １４．前記プロセッサがさらに、前記スケジューリングされたセルタイムスロッ ト中、伝送のために前記仮想接続のためのセルを構成するように作動することを 特徴とする請求項２３の装置。 １５．前記プロセッサがさらに、前記スケジューリングされたセルタイムスロッ ト中、伝送するための仮想接続に対する予め構成されたセルを引き出すように作 動することを特徴とする請求項２３の装置。 １６．前記プロセッサがさらに、使用可能なセルタイムスロットが前記第１のビ ット群の第１のビットのブロックで全然突き止められないならば、前記第２のビ ット群を使用し、使用可能なセルタイムスロットを示すビットを含む前記第１の ビット群の次のビットのブロックを識別するように作動することを特徴とする請 求項２４の装置。 １７．前記プロセッサがさらに、使用可能なセルタイムスロットを示すビットを 含む前記第１のビット群の次のビットのブロックを引き出し、次のビットのブロ ックを検索し、前記使用可能なセルタイムスロットを示すビットを突き止め、前 記使用可能なタイムスロットがスケジューリングされたことを示すために前記使 用可能なタイムスロットを示すビットを変更することによって前記仮想接続によ る使用のための前記使用可能なタイムスロットをスケジューリングし、前記次の ブロックが他の使用可能なセルタイムスロットを示す任意の他のビットを含むか どうかを決定し、他の使用可能なセルタイムスロットを示す前記次のブロックの 他のビットが全然ない場合、前記第１の群の次のブロックが使用不可能なセルタ イムスロットに対応するビットだけを含むことを示すために第２のビット群のビ ットを変更するように作動することを特徴とする請求項１６の装置。 １８．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の情報要素群の各要素がセルタイムスロットを示す第１の情報要素群 を発生するステップであって、前記第１の群の所与の要素の値が対応するセルタ イムスロットが伝送のために使用可能であるか否か示すこと、 前記仮想接続のための接続識別子を指定するスケジューリング命令および 前記目的タイムスロットに対応する接続識別子テーブルのアドレスを受け取るス テップと、 前記接続識別子テーブルアドレスを前記目的タイムスロットに対応する第 １のビット群のビットのためのアドレスに変換するステップと、 第１のビット群の一部を引き出すステップであって、前記第１のビット群 の一部が前記目的タイムスロットに対応するビットおよび次のセルタイムスロッ トに対応する少なくとも１つの付加ビットを含むこと、 前記ＡＴＭシステムの所与の仮想接続のスケジューリング命令に応じて 、使用可能なスロットに対応するビットが識別されるまで、前記第１のビット群 の一部を検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に識別された要素を変更することによって前記仮想接続による使用のための前記 使用可能なタイムスロットをスケジューリングするステップとを含むことを特徴 とする非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当でる方法 。 １９．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の情報要素群の各要素がセルタイムスロットを示す第１の情報要素群 を発生するステップであって、前記第１の群の所与の要素の値が対応するセルタ イムスロットが伝送のために使用可能であるか否か示す こと、 接続識別子テーブルのアドレスを指定するサービス命令を受け取るステッ プと、 前記接続識別子テーブルから指定されたアドレスに対応し、かつ前記ＡＴ Ｍシステムの仮想接続を識別する接続識別子を引き出すステップと、 前記第１のビット群を記憶するメモリから前記接続識別子テーブルの指定 されたアドレスに対応するビットを引き出すステップと、 前記引き出されたビットが、前記対応するセルタイムが前記仮想接続のた めにスケジューリングされたことを示す場合、前記仮想接続のためのセルの伝送 を指令するステップと、 前記セルタイムスロットがサービスされ、かつしたがって次のスケジュー リングリクエストのために使用可能であることを示すために前記対応するビット を変更するステップとを含むことを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおいてセルを割り当てる方法。 ２０．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の情報要素群の各要素がセルタイムスロットを示す第１の情報要素群 を発生するステップであって、前記第１の群の所与の要素の値が対応するセルタ イムスロットが伝送のために使用可能であるか否か示すこと、 仮想接続の接続識別子を指定するスケジューリング命令および目的セルス ロットに応じて前記第１のビット群内の第１のビットのブロックを引き出すステ ップであって、第１のビットのブロックが前記目的セルタイムスロットに対応す るビットを含むこと、 前記引き出された第１のブロック中を検索し、前記目的セルタイムスロッ トに対応するビットのあるいはこのビット後の使用可能なセル タイムスロットを示すビットを突き止めるステップと、 使用可能なセルタイムスロットが突き止められる場合、他の使用可能なセ ルタイムスロットを示す第１のビットのブロックの任意の他のビットがあるかど うかを決定するステップと、 他の使用可能なセルタイムスロットを示す第１のブロックに他のビットが 全然ない場合、前記第１の群の第１のブロックが使用不可能なセルタイムスロッ トに対応するビットだけを含むことを示すために第２のビット群のビットを変更 するステップとを含み、前記第２のビット群が、前記第１のビット群の複数のビ ットのブロックの各々に対するビットを含み、前記第２のビット群が、第１の群 ビットの対応するブロックが使用可能なセルタイムスロットを示すビットを含む かどうかを示すことを特徴とする非同期転送モート（ＡＴＭ）通信システムにお いてセルを割り当てる方法。 ２１．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 各ビット群が前記ＡＴＭシステムの通信リンクのためのトラフィックの一 部のスケジューリング状態を示す複数のビット群を供給するステップと、 前記伝送リンクの高優先順位トラフィックに関するスケジューリング状態 を示すために前記複数の群の第１のビット群を使用するステップと、 前記伝送リンクの低い優先順位トラフィックのスケジューリング状態を示 すように複数グループの第２のビット群を発生するステップと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応するビットで開始し、かつ使用可能なタイ ムスロットに対応するビットが識別されるまで第１の要素群中を進行して第１の ビット群を検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に識別ビットを変更することによって前記仮想接続による使用のための前記使用 可能タイムスロットをスケジューリングするステップとを含むことを特徴とする 非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法。 ２２．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各ビットがセルタイムスロットを示す第１のビット群を記憶す る第１のメモリロケーション群であって、前記第１のビット群の所与のビットの 値が対応するセルタイムスロットが伝送のために使用可能であるか否かを示すこ と、 前記仮想接続のための接続識別子を指定するスケジューリング命令および 目的タイムスロットに対応する接続識別子テーブルのアドレスを受け取り、前記 接続識別子テーブルアドレスを前記目的タイムスロットに対応する前記第１のビ ット群のビットのためのアドレスに変換し、かつメモリから前記目的タイムスロ ットに対応するビットおよび次のセルタイムスロットに対応する少なくとも１つ の付加ビットを含む前記第１のビット群の一部を引き出すように作動するプロセ ッサとを備え、 前記プロセッサがさらに、前記目的タイムスロットに対応するビットで開 始し、かつ使用可能なタイムスロットに対応するビットが識別されるまで第１の ビット群中を進行して前記第１のビット群を検索し、かつ使用可能なタイムスロ ットがスケジューリングされたことを示すために識別されたビットを変更するこ とによって前記仮想接続によって使用するための使用可能なタイムスロットをス ケジューリングするように作動することを特徴とする非同期転送モード（ＡＴＭ ）通信システムにおいてセルを割り当てる際に使用するための装置。 ２３．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各ビットがセルタイムスロットを示す第１のビット群を記憶す る第１のメモリロケーション群であって、前記第１のビット群の所与のビットの 値が対応するセルタイムスロットが伝送のために使用可能であるか否かを示すこ と、 接続識別子テーブルのアドレスを指定するサービス命令を受け取り、前記 接続識別子テーブルから前記識別されたアドレスに対応し、かつ前記ＡＴＭシス テムの仮想接続を識別する接続識別子を引き出し、前記第１のビット群を記憶す るメモリから前記接続識別子テーブルの指定されたアドレスに対応するビットを 引き出し、前記引き出されたビットが前記対応するセルタイムスロットが前記仮 想接続のためにスケジューリングされたことを示す場合、前記仮想接続のための セルの伝送を命令し、セルタイムスロットがサービスされ、したがって再び次の スケジューリングリクエストのために使用可能であることを示すために前記対応 するビットを変更するように作動するプロセッサとを備えていることを特徴とす る非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に使用 するための装置。 ２４．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各ビットがセルタイムスロットを示す第１のビット群を記憶す る第１のメモリロケーション群であって、前記第１のビット群の所与のビットの 値が対応するセルタイムスロットが伝送のために使用可能であるか否かを示すこ と、 仮想接続の接続識別子を指定するスケジューリング命令および目的セルス ロットに応じて、前記第１のビット群内の第１のビットのブロックを引き出し、 前記第１のビットのブロックが、目的セルタイムスロット に対応するビットを含むこと、前記目的セルタイムスロットに対応するビットの あるいはこのビットの後の使用可能なセルタイムスロットを示すビットを突き止 めるために引き出された第１のブロック中を検索し、使用可能なセルタイムスロ ットが突き止められる場合、他の使用可能なセルタイムスロットを示す前記第１ のビットのブロックに任意の他のビットがあるかどうかを決定し、他の使用可能 なセルタイムスロットを示す前記第１のブロックに任意の他のビットが全然ない 場合、前記第１の群の第１のブロックが使用不可能なセルタイムスロットに対応 するビットだけを含むことを示すために第２のビット群のビットを変更するよう に作動するプロセッサとを備え、前記第２のビット群が、前記第１のビット群の 複数のビットのブロックの各々のためのビットを含み、前記第２のビット群が、 第１のビット群の対応するブロックが使用可能なセルタイムスロットを示すビッ トを含むかどうかを示すことを特徴とする非同期転送モード（ＡＴＭ）通信シス テムにおいてセルを割り当てる際に使用するための装置。 ２５．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 各情報要素群が所与のセル速度を有する仮想接続群のスケジューリング状 態を示す複数の情報要素群を発生するステップと、 各群の各要素がセルタイムスロットを示すステップであって、群の所与の 要素の値が、対応するセルタイムスロットが伝送のために使用可能であるか否か を示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して第１の情報 要素群を検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に識別ビットを変更することによって前記仮想接続による使用 のための前記使用可能タイムスロットをスケジューリングするステップとを含む ことを特徴とする非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り 当てる方法。 ２６．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 各情報要素群が複数の伝送リンクを利用可能にするシステムの別個の伝送 リンクのスケジューリング状態を示す複数の情報要素群を発生するステップと、 各群の各要素がセルタイムスロットを示すステップであって、群の所与の 要素の値が、対応するセルタイムスロットが伝送のために使用可能であるか否か を示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して第１の情報 要素群を検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に識別ビットを変更することによって前記仮想接続による使用のための前記使用 可能タイムスロットをスケジューリングするステップとを含むことを特徴とする 非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法。 ２７．同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に使 用するための装置であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を記憶す る第１のメモリロケーション群であって、第１のビット群の所与の要素の値が対 応するセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 情報要素のトンネル制御群を記憶する第２のメモリロケーション群であっ て、前記トンネル制御群の各要素がセルタイムスロットに対応し、前記トンネル 制御情報群要素の各々が前記仮想パス接続のために予約されたスロットに対応し 、第１の方法でセットされた情報要素が使用可能なタイムスロットを示し、かつ 第２の方法でセットされた全ての他のトンネル制御群ビットが使用不可能なタイ ムスロットを示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素群を検索し、かつ前記使用可能なタイムスロットがスケジュールされた ことを示すために識別された要素を変更することによって前記仮想接続によって 使用するための使用可能なタイムスロットをスケジューリングするように作動す るプロセッサとを備えていることを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおいてセルを割り当てる際に使用するための装置。 ２８．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を記憶す る第１のメモリロケーション群であって、第１のビット群の所与の要素の値が対 応するセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 対応する複数の付加情報要素群を記憶する複数の付加メモリロケーション 群であって、各要素群が前記ＡＴＭシステムの伝送リンクのためのトラフィック の一部のスケジューリング状態を示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群 中を進行して前記第１の情報要素群を検索し、かつ前記使用可能なタイムスロッ トがスケジュールされたことを示すために識別された要素を変更することによっ て前記仮想接続によって使用するための使用可能なタイムスロットをスケジュー リングするように作動するプロセッサとを備えていることを特徴とする非同期転 送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に使用するための 装置。 ２９．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を記憶す る第１のメモリロケーション群であって、第１のビット群の所与の要素の値が対 応するセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 対応する複数の付加情報要素群を記憶する複数の付加メモリロケーション 群であって、各要素群が所与のセル速度を有する仮想接続の群のスケジューリン グ状態を示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素群を検索し、かつ前記使用可能なタイムスロットがスケジュールされた ことを示すために識別された要素を変更することによって前記仮想接続によって 使用するための使用可能なタイムスロットをスケジューリングするように作動す るプロセッサとを備えていることを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおいてセルを割り当てる際に使用するための装置。 ３０．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を記憶す る第１のメモリロケーション群であって、第１のビット群の所与の要素の値が対 応するセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 対応する複数の付加情報要素群を記憶する複数の付加メモリロケーション 群であって、各要素群が複数の伝送リンクを利用可能にするシステムの別個の伝 送リンクのスケジューリング状態を示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素群を検索し、かつ前記使用可能なタイムスロットがスケジュールされた ことを示すために識別された要素を変更することによって前記仮想接続によって 使用するための使用可能なタイムスロットをスケジューリングするように作動す るプロセッサとを備えていることを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおいてセルを割り当てる際に使用するための装置。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＫＥ，ＬＳ，ＭＷ，Ｓ Ｄ，ＳＺ，ＵＧ)，ＥＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ ，ＭＤ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＵ，ＢＡ ，ＢＢ，ＢＧ，ＢＲ，ＣＡ，ＣＮ，ＣＵ，ＣＺ，ＥＥ， ＦＩ，ＧＥ，ＨＵ，ＩＬ，ＩＳ，ＪＰ，ＫＧ，ＫＰ，Ｋ Ｒ，ＬＣ，ＬＫ，ＬＲ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ ，ＭＫ，ＭＮ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＲＯ，ＳＧ， ＳＩ，ＳＫ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ (72)発明者 ルシアー、ダニエル、ジェイ アメリカ合衆国、マサチューセッツ州 02019、ベリンガム、ビーチウッド ロー ド ６

Claims (1)

1. 【特許請求の範囲】 １． 非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を発生す るステップであって、前記第１の群の所与の要素の値が対応するセルタイムスロ ットが伝送のために使用可能であるか否か示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素群を検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に識別された要素を変更することによって前記仮想接続による使用のための前記 使用可能なタイムスロットをスケジューリングするステップとを含むことを特徴 とする非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 。 ２． 前記第１の情報要素群が、各ビットがセルタイムスロットを示す第１のビ ット群として構成されることを特徴とする請求項１の方法。 ３． 前記仮想接続のための接続識別子を指定するスケジューリング命令および 前記目的タイムスロットに対応する接続識別子テーブルのアドレスを受け取るス テップと、 前記接続識別子テーブルアドレスを前記目的タイムスロットに対応する第 １のビット群のビットに対するアドレスに変換するステップと、 メモリから前記第１のビット群の一部を引き出すステップとをさらに含 み、前記第１のビット群の一部が、前記目的タイムスロットに対応するビットお よび次のセルタイムスロットに対応する少なくとも１つの付加ビットを含むこと を特徴とする請求項２の方法。 ４． 前記接続識別子を前記識別ビットに対応する接続識別子テーブルロケーシ ョンに記憶するステップをさらに含むことを特徴とする請求項３の方法。 ５． 接続識別テーブルのアドレスを指定するサービス命令を受け取るステップ と、 前記指定アドレスに対応し、かつ前記ＡＴＭシステムの仮想接続を識別す る接続識別子を前記接続識別子テーブルから引き出すステップと、 前記第１のビット群を記憶するメモリから前記接続識別子テーブルの指定 されたアドレスに対応するビットを引き出すステップと、 前記引き出されたビットが、前記対応するセルタイムスロットが前記仮想 接続のためにスケジューリングされたことを示す場合、前記仮想接続のためのセ ルの伝送を命令するステップと、 前記セルタイムスロットがサービスされ、かつしたがって次のスケジュー リングリクエストのために再び使用可能であることを示す対応するビットを変更 するステップとをさらに含むことを特徴とする請求項２の方法。 ６． 前記仮想接続のためのセルの伝送を命令する方法が、スケジューリングさ れたセルタイムスロット中伝送のために仮想接続のためのセルをさらに構成する ステップを含むことを特徴とする請求項５の方法。 ７． 前記仮想接続のためのセルの伝送を命令する方法が、前記スケジューリン グされたセルタイムスロット中伝送のために前記仮想接続のための予め構成され たセルを引き出すステップをさらに含むことを特徴とする請求項５の方法。 ８． 第２のビット群を生成するステップをさらに含み、前記第２のビット群の 各ビットが、前記第１のビット群のビットのブロックに対応し、かつ対応するビ ットのブロックが使用可能なセルタイムスロットを示す少なくとも１つのビット を含むかどうかを示すむことを特徴とする請求項２の方法。 ９． 仮想接続の接続識別子を指定するスケジューリング命令および目的セルス ロットに応じて第１のビット群内の第１のビットのブロックを引き出すステップ であっで、前記第１のビットのブロックが目的セルタイムスロットに対応するビ ットを含むこと、 引き出された第１のブロック中を検索し、前記目的セルタイムスロットに 対応するビットのあるいはこのビット後の使用可能なセルタイムスロットを示す ビットを突き止めるステップと、 使用可能なセルタイムスロットが突き止められた場合、他の使用可能なセ ルタイムスロットを示す第１のビットのブロックに任意の他のビットがあるかど うかを決定するステップと、 他の使用可能なセルタイムスロットを示す第１のブロックの他のビットが 全然ない場合、前記第１の群の第１のブロックが使用不可能なセルタイムスロッ トに対応するビットだけ含むことを示すために第２のビット群のビットを変更す るステップとをさらに含み、前記第２のビット群が、前記第１のビット群の複数 のビットのブロックの各々のためのビットを含み、前記第２の群ビットが、第１ の群ビットの対応するブロックが使用可能なセルタイムスロットを示すビットを 含むかどうかを示すことを特徴とする請求項２の方法。 １０.使用可能なセルタイムスロットが第１のビット群の第１のビットのブロッ クで全然突き止められない場合、使用可能なセルタイムスロットを 示すビットを含む第１のビット群の次のビットのブロックを識別するために第２ のビット群を使用するステップをさらに含むことを特徴とする請求項９の方法。 １１.使用可能なセルタイムスロットを示すビットを含む第１のビット群の次の ビットのブロックを引き出すステップと、 前記使用可能なセルタイムスロットを示すビットを突き止めるために次の ビットのブロックを検索するステップと、 前記使用可能なタイムスロットがスケジューリングされたことを示すため に前記使用可能なタイムスロットを示すビットを変更することによって前記仮想 接続による使用のために前記使用可能なタイムスロットをスケジューリングする ステップと、 前記次のブロックが他の使用可能なセルタイムスロットを示す任意の他の ビットを含むかどうかを決定するステップと、 他の使用可能なセルタイムスロットを示す次のブロックに他のビットが全 然ない場合、前記第１の群の次のブロックが使用不可能なセルタイムスロットに 対応するビットだけを含むことを示すために第２のビット群のビットを変更する ステップとをさらに含むことを特徴とする請求項１０の方法。 １２.仮想パス接続のための伝送リンクに少なくとも１つのセルタイムスロット を予約するステップと、 前記ビットが前記予約セルタイムスロットが使用不可能であることを示す ように前記仮想パス接続のために予約されたセルタイムスロットに対応する第１ のビット群のビットをセットするステップと、 トンネル制御ビット群を発生するステップとをさらに含み、前記トンネル 制御群の各ビットが前記伝送リンクのセルタイムスロットに対応し、前記仮想パ ス接続のために予約されたスロットに対応する前記トン ネル制御群ビットの各々が使用可能なタイムスロットを示し、かつ全ての他のト ンネル制御群ビットが使用不可能なタイムスロットを示していることを特徴とす る請求項２の方法。 １３.前記仮想パス接続に対応するサービスリクエストを受け取るステップと、 セルタイムスロットが対応するロケーションのためにスケジューリングさ れたかどうかを決定するために前記仮想パス接続のための前記トンネル制御ビッ ト群を検索するステップと、 前記タイムスロットが前記対応するロケーションのためにスケジューリン グされた場合、スケジューリングされたセルタイムスロットのセルの伝送を命令 するステップと、 前記対応するセルタイムスロットがスケジューリングのために再び使用可 能であることを示すために前記トンネル制御ビット群の対応するビットをリセッ トするステップと、 前記ビットが前記予約セルタイムスロットが使用不可能であることを示す ように前記仮想パス接続のために予約された前記セルタイムスロットに対応する 第１のビット群のビットをセットするステップとをさらに含むことを特徴とする 請求項１２の方法。 １４.複数のビット群を供給するステップをさらに含み、各ビット群が前記ＡＴ Ｍシステムの伝送リンクのためのトラフィックの一部のスケジューリング状態を 示すことを特徴とする請求項２の方法。 １５．複数のビット群を供給するステップが、 前記伝送リンクの高い優先順位トラフィックに関するスケジューリング状 態を示すために前記第１のビット群を使用するステップと、 伝送リンクのより低い優先順位トラフィックのスケジューリング 状態を示す第２のビット群を発生するステップとをさらに含むことを特徴とする 請求項１４の方法。 １６.複数のビット群を供給するステップをさらに含み、各ビット群が所与のセ ル速度を有する仮想接続群のスケジューリング状態を示すことを特徴とする請求 項２の方法。 １７.複数のビット群を供給するステップをさらに含み、各ビット群が複数の伝 送リンクを利用可能にするシステムの別個の伝送リンクのスケジューリング状態 を示すことを特徴とする請求項２の方法。 １８.非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の群の各ビットがセルタイムスロットを示す第１のビット群を発生す るステップであって、前記第１のビット群の所与のビットの値が対応するセルタ イムスロットが伝送のために使用可能であるか否かを示すこと、 第２のビット群の各ビットが、前記第１のビット群のビットのブロックに 対応し、かつ対応するビットのブロックが使用可能なセルタイムスロットを示す 少なくとも１ビットを含むかどうかを示す第２のビット群を発生するステップと 、前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエストに応 じて検索される前記第１のビット群のブロックを決定するために第２のビット群 を使用するステップとを含むことを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおいてセルを割り当てる方法。 １９.非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる方法 であって、 第１の群の各ビットがセルタイムスロットを示す第１のビット群を発生す るステップであって、前記第１のビット群の所与のビットの値が、対応するセル タイムスロットが伝送のために使用可能であるか否かを示すこと、 仮想パス接続のための伝送リンクに少なくとも１つのセルタイムスロット を予約するステップと、 前記ビットが前記予約セルタイムスロットが使用不可能であることを示す ように前記仮想パス接続のために予約されたセルタイムスロットに対応する前記 第１のビット群のビットをセットするステップと、 トンネル制御群の各ビットがセルタイムスロットに対応するトンネル制御 ビット群を発生するステップとを含み、前記仮想パス接続のために予約されたス ロットに対応する前記トンネル制御群ビットの各々が使用可能なタイムスロット を示し、かつ全て他のトンネル制御グループビットが使用不可能なタイムスロッ トを示していることを特徴とする非同期転送モード（ＡＴＭ）通信システムにお いてセルを割り当てる方法。 ２０.前記仮想パス接続に対応するサービスリクエストを受け取るステップと、 セルタイムスロットが対応するロケーションのためにスケジューリングさ れたかどうかを決定するために前記仮想パス接続のための前記トンネル制御ビッ ト群を検索するステップと、 前記タイムスロットが前記対応するロケーションのためにスケジューリン グされた場合、スケジューリングされたセルタイムスロットのセルの伝送を命令 するステップと、 前記対応するセルタイムスロットがスケジューリングのために再び使用可 能であることを示すように前記トンネル制御ビット群の対応するビットをリセッ トするステップと、 前記ビットが前記予約セルタイムスロットが使用不可能であるこ とを示すように前記仮想パス接続のために予約された前記セルタイムスロットに 対応する前記第１のビット群のビットをセットするステップとをさらに含むこと を特徴とする請求項１９項の方法。 ２１．非同期転送モード（ＡＴＭ）通信システムにおいてセルを割り当てる際に 使用するための装置であって、 第１の群の各要素がセルタイムスロットを示す第１の情報要素群を記憶す る第１のメモリロケーション群であって、第１のビット群の所与の要素の値が対 応するセルタイムスロットが伝送のために使用可能であるか否かを示すこと、 前記ＡＴＭシステムの所与の仮想接続のセルスケジューリングリクエスト に応じて、目的タイムスロットに対応する要素で開始し、かつ使用可能なタイム スロットに対応する要素が識別されるまで第１の要素群中を進行して前記第１の 情報要素群を検索し、かつ前記使用可能なタイムスロットがスケジュールされた ことを示すために識別された要素を変更することによって前記仮想接続によって 使用するための使用可能なタイムスロットをスケジューリングするように作動す るプロセッサとを備えていることを特徴とする非同期転送モード（ＡＴＭ）通信 システムにおいてセルを割り当てる際に使用するための装置。 ２２．前記第１の情報要素群が、各ビットがセルタイムスロットを示す第１のビ ット群として構成されることを特徴とする請求項２１の装置。 ２３．前記プロセッサが、前記仮想接続のための接続識別子を指定するスケジュ ーリング命令および前記目的タイムスロットに対応する接続識別子テーブルのア ドレスを受け取り、前記接続識別子テーブルアドレスを前記目的タイムスロット に対応する第１のビット群のビットに対するアドレスに変換し、かつ前記目的タ イムスロットに対応するビットおよび次の セルタイムスロットに対応する少なくとも１つの付加的ビットを含む第１のビッ ト群の一部をメモリから引き出すように作動することを特徴とする請求項２２の 装置。 ２４.前記第１のビット群および接続識別子テーブルを記憶するメモリをさらに 含み、前記接続識別子が前記識別されたビットに対応するメモリロケーションに 記憶されていることを特徴とする請求項２２の装置。 ２５．前記プロセッサはさらに、接続識別子テーブルのアドレスを指定するサー ビス命令を受け取り、指定されたアドレスに対応し、かつＡＴＭシステムの仮想 接続を識別する接続識別子を前記接続識別子テーブルから引き出し、前記接続識 別子テーブルの前記指定されたアドレスに対応するビットを前記第１のビット群 を記憶するメモリから引き出し、前記引き出されたビットが前記対応するセルタ イムスロットが前記仮想接続のためにスケジューリングされた場合、前記仮想接 続のためのセルの伝送を命令し、かつ前記セルタイムスロットがサービスされ、 したがって次のスケジューリングリクエストに対して再び使用可能であることを 示ために前記対応するビットを変更するように作動することを特徴とする請求項 ２２の装置。 ２６．前記プロセッサがさらに、前記スケジューリングされたセルタイムスロッ ト中、伝送するための前記仮想接続のためのセルを構成するように作動すること を特徴とする請求項２５の装置。 ２７．前記プロセッサがさらに、前記スケジューリングされたセルタイムスロッ ト中、伝送するための仮想接続に対する予め構成されたセルを引き出すように作 動することを特徴とする請求項２５の装置。 ２８．第２のビット群の各ビットが、前記第１のビット群のビットのブロックに 対応し、かつ前記対応するビットのブロックが使用可能なタイムスロットを示す 少なくとも１ビットを含むかどうかを示す第２のビット群を記憶する第２のメモ リロケーション群をさらに含むことを特徴とする請求項２２の装置。 ２９．前記プロセッサがさらに、仮想接続および目的セルスロットの接続識別子 を指定するスケジューリング命令および目的セルスロットに応じて第１のビット 群内の第１のビットのブロックを引き出し、前記第１のビットのブロックが前記 目的セルタイムスロットに対応するビットを含むこと、引き出された第１のブロ ック中を検索し、前記目的セルタイムスロットに対応するビットのあるいはこの ビット後の使用可能なセルタイムスロットを示すビットを突き止め、使用可能な セルタイムスロットが突き止められた場合、他の使用可能なセルタイムスロット を示す第１のビットのブロックの任意の他のビットがあるかどうかを決定し、か つ他の使用可能なセルタイムスロットを示す第１のブロックの他のビットが全然 ない場合、前記第１のグループの第１のブロックが使用不可能タイムスロットに 対応するビットのみを含むことを示すために第２のビット群のビットを変更する ように作動し、前記第２のビット群が、前記第１のビット群の複数のビットのブ ロックの各々のためのビットを含み、前記第２の群ビットが、第１の群のビット の対応するブロックが使用可能なセルタイムスロットを示すビットを含むかどう かを示すことを特徴とする請求項２２の装置。 ３０．前記プロセッサがさらに、使用可能なセルタイムスロットが前記第１のビ ット群の第１のビットのブロックで全然突き止められないならば、前記第２のビ ット群を使用し、使用可能なセルタイムスロットを示すビットを含む前記第１の ビット群の次のビットのブロックを識別するように 作動することを特徴とする請求項２９の装置。 ３１．前記プロセッサがさらに、使用可能なセルタイムスロットを示すビットを 含む前記第１のビット群の次のビットのブロックを引き出し、次のビットのブロ ックを検索し、前記使用可能なセルタイムスロットを示すビットを突き止め、前 記使用可能なタイムスロットがスケジューリングされたことを示すために前記使 用可能なタイムスロットを示すビットを変更することによって前記仮想接続によ る使用のための前記使用可能なタイムスロットをスケジューリングし、前記次の ブロックが他の使用可能なセルタイムスロットを示す任意の他のビットを含むか どうかを決定し、他の使用可能なセルタイムスロットを示す前記次のブロックの 他のビットが全然ない場合、前記第１の群の次のブロックが使用不可能なセルタ イムスロットに対応するビットだけを含むことを示すために第２のビット群のビ ットを変更するように作動することを特徴とする請求項３０の装置。 ３２．トンネル制御ビット群を記憶する第２のメモリロケーション群をさらに含 み、前記トンネル制御群の各ビットがセルタイムスロットに対応し、仮想パス接 続のために予約されたスロットに対応する前記トンネル制御群ビットの各々が、 使用可能なタイムスロットを示し、かつ全て他のトンネル制御群ビットが使用不 可能なタイムスロットを示すことを特徴とする請求項２２の装置。 ３３.対応する複数の付加的ビット群を記憶する複数の付加的メモリロケーショ ン群をさらに含み、各ビット群が前記ＡＴＭシステムの伝送リンクのためのトラ フィックのスケジューリング状態を示すことを特徴とする請求項２２の装置。 ３４.対応する複数の付加的ビット群を記憶する複数の付加的メモリロケ ーション群をさらに含み、各ビット群が所与のセル速度を有する仮想接続の群の スケジューリング状態を示すことを特徴とする請求項２２の装置。 ３５.対応する複数の付加的ビット群を記憶する複数の付加的メモリロケーショ ン群をさらに含み、各ビット群が複数の伝送リンクを利用可能にするシステムの 別個の伝送リンクのスケジューリング状態を示すことを特徴とする請求項２２の 装置。