JP4504606B2 - ネットワークスイッチにおいてトラフィックを成形する装置及び方法 - Google Patents

Description

【０００１】
（技術分野）
本発明は、一般的にはネットワーク通信の分野に関し、特定的にはネットワークスイッチにおけるトラフィックを成形する（シェーピング）装置及び方法に関する。
【０００２】
（従来の技術）
一般的に、ネットワーク通信システムは、ネットワーク内の多くのユーザを相互接続する。各ユーザは、ポートにおいてネットワークに接続される。ネットワークは多くのノードの相互接続によって形成され、源（ソース）の１ユーザからの入力ポートへの情報入力はネットワークを通してノードからノードへ、出力ポートへ、そして行先（デスティネーション）の別のユーザへ渡される。源から行先へ転送される情報はパケット化され、各ノードは入力ポートにおける入力パケットを出力ポートにおける出力パケットにスイッチする。ＡＴＭ（非同期転送モード）ネットワークの場合には、パケットは更にセルに分割される。
【０００３】
現在の技術では、高速パケットスイッチは、各スイッチポートにおいて毎秒数十万パケットを転送する。各スイッチポートは、広帯域統合サービスデジタル回路網（ＢＩＳＤＮ）の場合、典型的には50Ｍビット／秒から2.4Ｇビット／秒のレートで情報を転送するように設計されている。スイッチサイズは、数ポートから数千ポートまでの範囲である。
【０００４】
“高速パケットスイッチ”なる用語は、可変長パケット及び固定長パケットの両方を取扱うことができるスイッチを含む。固定長パケットの使用は、スイッチ設計を簡易化することができる。短い固定長パケット（セル）を使用する高速パケットスイッチを、ＡＴＭスイッチと呼ぶ。高速パケットスイッチは、単一の統合回路網内で異なる型の通信サービスを取扱う。これらのサービスは、音声、ビデオ、及びデータ通信を含むことができる。ネットワークを通して伝送される音声及びビデオサービスが許容できる遅延及び遅延変動は制限されるから、ＡＴＭスイッチはこれらのサービスに適している。広帯域ＩＳＤＮのためのＡＴＭ標準は、５バイトのヘッダー及び48バイトのデータの53バイトの長さを有するセルを定義している。ＡＴＭフォーラムトラフィック管理仕様は、以下のような多くのサービスクラス定義を指定している。
ＣＢＲ：連続ビットレート。音声及びビデオのような厳密に制約された遅延及び遅延変動を要求する実時間応用のために。ＣＢＲサービスクラスは、一貫して使用可能な固定された量の帯域幅を要求する。
ＲＴ−ＶＢＲ：実時間可変ビットレート。源が、時間に伴って変化するレートで伝送し（当分野においては“バースティ”という）、しかも厳密に制約された遅延及び遅延変動で受信しなければならないような応用用。
ＮＲＴ−ＶＢＲ：非実時間可変ビットレート。遅延またはその変動に関してのサービスは要求しないが、損失に対して感応性を有するバースティ応用用。
ＵＢＲ：無指定ビットレート。ファイル転送及びｅメールのような非実時間応用用。これは、関連するサービスを保証せず、従って割振られた帯域幅資源を用いず、セル損失比またはセル転送遅延に関して保証せず、そして現在のネットワーク輻輳レベルに関する明示フィードバックを用いずに、セルの非連続バーストを伝送する
ＧＦＲ：保証（された）フレームレート。これも非実時間応用用。このサービスカテゴリは、契約した最小レートで、またはそれ以下でトラフィックを伝送する源のために損失保証を与える。源が契約した最小レートを超えれば、そのレートより上のトラフィックはどのような損失保証も受けられない。
ＡＢＲ：使用可能ビットレート。ネットワーク内で使用可能な帯域幅の量に依存して、情報転送レートを変化させることができる非実時間応用用。
【０００５】
典型的なＡＴＭスイッチにおいては、セル処理機能はネットワークのノード内で遂行される。各ノードはＡＴＭスイッチであり、入力コントローラ（ＩＣ）、スイッチファブリック（ＳＦ）、出力コントローラ（ＯＣ）、及びノード制御（Ｃ）を含む。ノード制御は、接続の確立及び解放、帯域幅予約、バッファリング制御、輻輳制御、保守、及びネットワーク管理を含む機能のために使用される。
【０００６】
各スイッチにおいては、入力コントローラは典型的に同期しているので、入力コントローラからの全てのセルは同時にスイッチファブリックに到着し、セルはそれらの優先順位に従って受入れられたり、または拒絶されたりすることができる。スイッチファブリックを通るトラフィックはスロットされ、スイッチファブリック遅延は、タイムスロット持続時間、パイプライン遅延、及びキューイング遅延の合計に等しい。
【０００７】
ノード制御は、スイッチファブリックをバイパスする直接通信経路によって、またはスイッチファブリックを通して伝送される制御セルを介しての何れかによって、入力コントローラ及び出力コントローラと通信する。
【０００８】
スイッチへの外部接続は、一般的に双方向である。双方向接続は、入力コントローラ（Ｃ）及び出力コントローラ（ＯＣ）を互いにグループにしてポートコントローラ（ＰＣ）を形成させることによって形成する。
【０００９】
仮想チャンネル内のセルの入力シーケンスはスイッチファブリックにまたがって保存されるので、各仮想チャンネル内のセルの出力シーケンスは入力シーケンスと同一である。セルは、セルヘッダー内にそのセルが属している接続を識別する仮想チャンネル識別子（ＶＣＩ）を含んでいる。各セルのヘッダー内の各入力ＶＣＩは入力コントローラにおいて変換され、出力識別子を指定する。この変換は入力コントローラにおいて、典型的には、入力ＶＣＩを使用してテーブルを表引きし、接続テーブルをアドレスすることによって遂行される。この接続テーブルは、その接続がルートされているスイッチファブリックの出力ポートを指定するルート指定フィールドをも含んでいる。接続の優先順位、サービスのクラス、及びトラフィックの型のような他の情報も、接続毎に接続テーブル内に含ませることができる。
【００１０】
ＡＴＭスイッチにおいては、セルの到着はスケジュールされていない。典型的な動作では、同一の出力ポートを各々が要求している複数のセルが異なる入力ポートに同時に到着するかも知れない。これらの要求が出力ポートの出力容量を超えるような動作を、出力競合（回線争奪）と称する。出力ポートは一時に固定された数（例えば、１つ）のセルしか伝送できないから、伝送のためには固定された数のセルだけしか受入れることができず、従ってそのポートへルートされた他のセルは破棄するか、または待ち行列内にバッファしなければならない。スイッチモジュールを通るセルをルート指定するために、例えば自己ルート指定及びラベルルート指定のような、異なる方法が使用される。
【００１１】
自己ルート指定ネットワークは、各セルにルート指定タグをプレフィックスする入力コントローラと共に動作する。典型的には、入力コントローラはルート指定テーブルからルート指定タグを入手する表引きを使用する。ルート指定タグはセルが送給される出力ポートを指定する。各スイッチング要素は、ルート指定タグを検査することによって迅速にルート指定決定を行うことができる。自己ルート指定ネットワークは、セルが入るスイッチポートには無関係に、要求された行先へ各セルが到着することを保証する。
【００１２】
ラベルルート指定ネットワークは、各スイッチング要素内の変換テーブルを参照する各セル内のラベルと共に動作する。ラベルは各スイッチング要素内で変換され、従ってスイッチング要素の任意のネットワークを使用することができる。
【００１３】
スイッチは２つの主要設計、即ち時分割、及び空間分割を有している。時分割スイッチングファブリックでは、全てのセルは、全ての入力及び出力ポートによって共通に共用される単一の通信チャンネルを通って流れる。空間分割スイッチングでは、入力ポートと出力ポートとの間に複数の経路が設けられている。これらの経路は同時に動作するので、スイッチファブリックを横切って同時に多くのセルを伝送することができる。従って、スイッチファブリックの合計容量は、各経路の帯域幅と、セルを同時に伝送できる経路の平均数との積である。
【００１４】
トラフィックロードがネットワーク内の使用可能なシステム資源を越えると、輻輳が発生して性能が劣化する。セルの数がネットワークの輸送容量内にある時には、送給されるセルの数が、輻輳を生じさせずに送られるセルの数に等しいように、全てのセルを送給することができる。しかしながら、もしノードがトラフィックを処理できないレベルまでトラフィックが増加すれば、輻輳が発生する。
【００１５】
輻輳は、幾つかの要因によって惹起される。もしネットワーク内のノードがそれらに要求される種々のタスク（キューイングバッファ、更新テーブル等）を遂行するのに遅過ぎれば、たとえ余分なライン容量が存在しているとしても、待ち行列が累積する。一方、たとえノードが無限に速いとしても、入力トラフィックレートが何等かの出力の特定グループのための出力トラフィックレートの容量を超えれば、待ち行列が累積する。
【００１６】
もしノードがキューイングセルのための自由バッファを有していなければ、ノードは新たに到着するセルを破棄しなければならない。パケットデータトラフィックの場合、あるセルが破棄されると、破棄されたセルを含んでいたパケットが多分多数回伝送され、輻輳エポックを更に拡張させる。
【００１７】
ＡＴＭスイッチにおいては、あるサービスレートを保証するためにセルの到着をスケジュールする必要はなく、それによって設計者は十分なバッファ空間を設けることができる。惹起される１つの問題は、セルが均一な分布で到着しないことである。事実、殆どのトラフィックは、それらの間にランダムな持続時間の遅延を設けて伝送される“バースト”（ランダムなサイズを有するセルのグループ）で到着する。より予測可能なデータストリームを形成させるために、セルバーストは、当分野においては“成形器”（シェーパー）として知られているデバイスによって成形される。成形器はセルバーストを受入れて、所定の“形状”に従ってセルを均一に分散させる。異なる形状には異なる仮想チャンネル（ＶＣ）が必要であり、従って各ＶＣを独立的に成形する成形器を有することが望ましい。
【００１８】
（発明の概要）
一般的に言えば、本発明は、接続毎に成形を行うような、ネットワークスイッチにおいてトラフィックを成形するための装置、及び方法に関する。本発明による成型器は、２つの基本ブロック、即ちセル記述子（ＣＤ）処理ブロック、及び形状ＩＤ処理ブロックを備えている。ＣＤ処理ブロック及び形状ＩＤ処理ブロックは、ＣＤの管理をＣＤ出力時点のスケジューリングから切り離すように動作する。ＣＤ処理ブロックは、トークン（形状ＩＤ）を、形状ＩＤブロックへ出力する。もしこのトークンが確認されれば、それは直ちにＣＤ処理ブロックへ返送され、確認されなければそれは処理されない。トークンが“成熟”していれば、そのトークンはＣＤ処理ブロックへ返送される。次いで、ＣＤ処理ブロックはＣＤを出力する。
【００１９】
接続毎の形状ＩＤと共に“今”及び“後刻”リストを使用し、それぞれ仮想接続（ＶＣ）及び仮想経路（ＶＰ）内の優先権を与える。これは、ＶＰ内で成形中の接続の相対的優先順位を保存する。換言すれば、たとえより高い優先順位のＶＣがトークンを生成しなくとも、それを最初に送ることができ、それによってセルの優先順位が保存される。また、カレンダー待ち行列を使用することによって“仮想終了時”（ＶＦＴ）計算の複雑さが減少する。
【００２０】
（実施の形態）
本発明は、以下の添付図面に基づく詳細な説明から容易に理解されよう。なお、類似構造的要素に対しては類似参照番号を付してある。
【００２１】
以下の説明は、当分野に精通している者が本発明を製造し、使用できるようになされるものであり、本発明を遂行するために発明者が企図した最良モードを記述している。しかしながら、以下に本発明の基本的原理を詳細に記載してネットワークスイッチにおいてトラフィックを成形する装置及び方法を説明するので、当分野に精通していれば種々の変更は容易に明白であろう。これら全ての変更、等価、及び代替は、本発明の思想及び範囲内にあることを意図している。
【００２２】
先ず図１を参照する。複数のネットワークユーザが、源／行先（Ｓ／Ｄ）４で表されている。各ユーザは、典型的に、源（Ｓ）として情報を送り、行先（Ｄ）として情報を受信する。Ｓ／Ｄユニット４の源（Ｓ）は、他のＳ／Ｄユニット４の行先（Ｄ）へ情報を送る。情報を源から行先へ転送するために、各Ｓ／Ｄユニット４はマルチノード（Ｎ）ネットワーク１を通して接続されている。ネットワーク１は、多くのノード（Ｎ）５を含んでいる。ノードは、ノードからノードへ接続されているから、一般的に、ネットワーク１内にノード５のチェーンを形成することによって、Ｓ／Ｄユニット４のどの特定の１つをも、他のＳ／Ｄユニット４のどの１つへも接続することができる。一般的に、Ｓ／Ｄユニット４とノード５との間の接続、及びノード５間の接続は、情報を両方向に転送することを可能にする双方向リンク８によっている。
【００２３】
明瞭化のために、図１に図示したノード（Ｎ）５の数は比較的少数であるが、ネットワークは数百またはそれ以上のノードを含むことができる。またＳ／Ｄユニット４は、Ｓユーザ、即ち４-０、４-１、４-２、４-３、４-４、…、４-（Ｓ−２）、４-（Ｓ−１）を含む。Ｓの値はどのような整数であることもできるが、典型的にはＳは数百またはそれ以上である。
【００２４】
典型的な実施の形態では、図１の通信システムはＡＴＭネットワークであり、情報転送の単位はセルである。複数のセルが、情報のパケットを形成する。ネットワーク１は、画像、音声、及びデータを含む異なる型の情報を支援するようにセル及びパケットと通信する。
【００２５】
図２において、Ｓ／Ｄユニット４-ｘは、複数Ｃのノード（Ｎ）５-０、５-１、…、５-（Ｃ−１）を通してＳ／Ｄユニット４-ｙに接続されている。
【００２６】
図２に示すＳ／Ｄユニット４-ｘは、図１のＳ／Ｄユニット４の何れかの典型である。例えば、Ｓ／Ｄユニット４-ｘは、図１のＳ／Ｄユニット４-２を表すことができる。同様に、図２のＳ／Ｄユニット４-ｙは、図１のＳ／Ｄユニット４の何れかを表すことができる。例えば、図２のＳ／Ｄユニット４-ｙは、図１のＳ／Ｄユニット４-４を表すことができる。この例では、ノード５-０、５-１、…、５-（Ｃ−１）は、図１のＳ／Ｄユニット４-２をＳ／Ｄユニット４-４に接続するために使用されているネットワーク１内のＣノードを表している。
【００２７】
図２において、双方向リンク８-０、８-１、…、８-（Ｃ−１）、８-（Ｃ）は、複数Ｃのノード（Ｎ）５-０、５-１、…、５-（Ｃ−１）を通してＳ／Ｄユニット４-ｘからＳ／Ｄユニット４-ｙに接続されている。図２において、情報は、Ｓ／Ｄユニット４-ｘ内の源（Ｓ）からＳ／Ｄユニット４-ｙ内の行先（Ｄ）へ転送することができる。同様に、情報をＳ／Ｄユニット４-ｙ内の源（Ｓ）からＳ／Ｄユニット４-ｘ内の行先（Ｄ）へ転送することができる。情報は、図２の何れの方向へも転送することはできるが、説明の目的から、源（Ｓ）と行先（Ｄ）との間の転送が、Ｓ／Ｄユニット４-ｘからＳ／Ｄユニット４-ｙへであるのか、またはＳ／Ｄユニット４-ｙからＳ／Ｄユニット４-ｘへであるのかを考えると便利である。方向には関係なく、各転送は源（Ｓ）から行先（Ｄ）へである。
【００２８】
図３に、図２の仮想チャンネル内での源（Ｓ）から行先（Ｄ）への転送に使用される回路を示す。図３において、図２のＳ／Ｄユニット４-ｘ内の源ユニット４-（Ｓ）は、図２のＳ／Ｄユニット４-ｙ内の源ユニット４-（Ｄ）に接続されている。
【００２９】
図３において、各リンク８-０、８-１、…、８-（Ｃ−１）、８-（Ｃ）は、情報を順方向に転送するための順方向（Ｆ）チャンネルと、情報を逆方向に転送するための逆方向（Ｒ）チャンネルとを含んでいる。図３の逆方向チャンネルは、源ユニット４-（Ｓ）から行先ユニット４-（Ｄ）への情報の転送に関している。図３の逆方向チャンネルは、図１のネットワークに関連して使用される制御情報を送る目的のためのものである。逆方向チャンネル（Ｒ）は、図２に関連して説明したＳ／Ｄユニット４-ｙからＳ／Ｄユニット４-ｘへの情報の順方向の転送に使用される順方向チャンネル（Ｆ）とは区別される。順方向（Ｆ）及び逆方向（Ｒ）の両チャンネルは、源ユニット４-（Ｓ）から行先ユニット４-（Ｄ）への転送に関している。図３の各ノードは、順方向（Ｆ）回路６及び逆方向（Ｒ）回路７を含んでいる。図３において、順方向チャンネル８-０Ｐ、８-１Ｆ、…、８-（Ｃ−１）Ｆは、入力としてそれぞれ順方向回路６-０、６-１、…、６-（Ｃ−１）に接続されている。順方向チャンネル８-（Ｃ）Ｆは、ノード６-（Ｃ−１）からユニット４-（Ｄ）まで接続されている。同様に、逆方向チャンネル８-０Ｒ、８-１Ｒ、…、８-（Ｃ−１）Ｒは、逆方向回路７-０、７-１、…、７-（Ｃ−１）から接続されている。逆方向チャンネル８-（Ｃ）Ｒは、Ｄユニット-（Ｄ）から逆方向回路７-（Ｃ−１）まで接続されている。
【００３０】
図３において、各ノード５は、順方向（Ｆ）回路６から逆方向（Ｒ）回路７まで接続されているフィードバック接続９を有している。詳述すれば、フィードバックチャンネル９-０、９-１、…、９-（Ｃ−１）は、それぞれノード５-０、５-１、…、５-（Ｃ−１）内の順方向（Ｆ）回路６から逆方向（Ｒ）回路７まで接続されている。図３の回路においては、仮想チャンネル接続は、順方向チャンネルセッティングアップに沿って、Ｓユニット４-（Ｓ）とＤユニット４-（Ｄ）との間に順方向の通信経路を作っている。図１のネットワーク１内には他の仮想チャンネルも確立されているので、各ノード、及び図３のノードを含む行先においてバッファリングが必要である。
【００３１】
図４に、図３の信号経路を有するノードの１つの典型的な実施の形態を示す。図４において、ノード５は、Ｎリンク１８-０、１８-１、…、１８-ｎ、…、１８-（Ｎ−１）を含む。図４の各リンク１８は、図２の双方向リンク８に類似している。図４では、リンク１８-０、１８-１、…、１８-ｎ、…、１８-（Ｎ−１）は、ポートコントローラ１１-０、１１-１、…、１１-ｎ、…、１１-（Ｎ−１）に接続されている。
【００３２】
図４のノードは、例えば、リンク１８の１つ（例えば、図４の入力リンク１８-０）を、スイッチファブリック１０を通して別のリンク１８の１つ（例えば、リンク１８-ｎ）に接続することによって、図３の情報転送に関連して使用される。この例では、スイッチファブリック１０は、リンク１８-０をリンク１８-ｎに接続するように機能する。
【００３３】
図４のノードが図２のノード５-１を表すような例では、図２のリンク８-１は図４のリンク１８-０であり、図２のリンク８-２は図４のリンク１８-ｎである。
このような接続では、図４のノードは、情報を例えばリンク１８-０からリンク１８-ｎへ接続し、また情報を逆方向にリンク１８-ｎからリンク１８-０へ接続する。リンク１８-０及び１８-ｎは、説明のために任意に選択したものである。Ｎリンク１８の何れかを、他の何れかのリンク１８へ接続するために、図２の回路内で選択することができる。
【００３４】
図４のノードを図３の仮想チャンネル接続（源（Ｓ）が左側、行先（Ｄ）が右側）に使用する場合、説明の目的からリンク１８-０がノード５への順方向入力であり、リンク１８-ｎがノードからの順方向出力であるものとする。
【００３５】
図４において、ポートコントローラ（ＰＣ）１１-０、１１-１、…、１１-ｎ、…、１１-（Ｎ−１）は、それぞれ入力コントローラ１４-０、１４-１、…、１４-ｎ、…、１４-（Ｎ−１）を有し、またそれぞれ出力コントローラ１５-０、１５-１、…、１５-ｎ、…、１５-（Ｎ−１）を有している。図４において、順方向情報セルは、図３の源４-Ｓからバス１８-０１、入力コントローラ１４-０、バス２０-ｎ０、スイッチファブリック１０、バス２０-ｎ１、コントローラ１５-ｎ、及びバス１８-ｎ０を通して図３の行先４-（Ｄ）へ送られる。ポートコントローラは、共用キューイングユニット５１内に配置されている共通バッファ記憶装置を共用し、バス４１-０、４１-、４１-ｎ、…、４１-（Ｎ−１）を通してユニット５１に双方向に接続されている。
【００３６】
図５に、図４のキューイングユニット５１の詳細を示す。キューイングユニット５１は、データ待ち行列ユニット５２及び待ち行列制御ユニット５３を含む。データ待ち行列ユニット５２及び待ち行列制御ユニット５３は、各々双方向バス４１-０、４１-１、…、４１-ｎ、…、４１-（Ｎ−１）に接続されている。バス４１上の制御情報は待ち行列ユニット５３へ接続され、バス４１上のデータはデータ待ち行列ユニット５２へ接続される。
【００３７】
図５に示す待ち行列制御ユニット５３は、データ待ち行列ユニット５２及びキューイングユニット５１の総合動作を制御する待ち行列管理者５４を含んでいる。待ち行列管理者は、典型的に、ソフトウェアを実行することができる処理ユニットを含む。バス４１上の入力情報がデータ待ち行列ユニット５２内への格納を要求すると、待ち行列管理者５４は自由バッファリストユニット５９から使用可能なバッファ位置を検出し、その使用可能なデータ位置をデータ待ち行列ユニット５２に割当てる。待ち行列管理者の一般的機能及び動作は公知である。キューイングに加えて、及び本発明の方法で動作させるために、総合通信ネットワークの効率的な動作を促進するように若干のセルを時折破棄する必要があり得る。待ち行列管理者５４の制御の下にある破棄ユニット５５は、先に割振られた待ち行列割当てを破棄する時点を決定する。キューイング動作の結果は、ポート毎の待ち行列ユニット５６内に格納され、ユニット５６自体はデキューユニット５７を活動させ、ユニット５７自体はマルチキャストサーバーを通して動作して先に割振られたバッファ位置を除去する。除去されると、デキューされたバッファ位置はユニット５９内の自由バッファリストへ戻されて追加され、再割当てのために使用可能になる。
【００３８】
破棄ユニット５５は、３つのユニット、即ちＦＩＦＯユニット６１（サブユニット６１-１及び６１-２を含む）、破棄ユニット６２、及びポインタ完全性ユニット６３からなる。破棄ユニット５５は、
１．全ての接続の契約されたサービス品質（QｏＳ）を保証（損なう接続を破棄することによって）
２．バッファ輻輳の監視及び制御
３．バッファが輻輳し始めるとＡＴＭヘッダー内に明示順方向輻輳指示（ＥＦＣＩ）のタグ付けを遂行
４．輻輳が過大になると接続毎にセル及びフレームの破棄を遂行
５．非保証接続（ＡＢＲ、ＧＦＲ、及びＵＢＲ）間の公平さの保証
６．種々のＥＦＣＩ及び破棄しきい値を支援することによって、ＡＢＲ、ＧＦＲ、及びＵＢＲの異なる品質の提供
７．ポインタ完全性検証（ポインタの重複が発生していないことを確認する）に責を負う。
【００３９】
前述したように、成型器ブロック６０はセルバーストを離間させ、セルを均一に分散させる。図６（Ａ）は、サンプル伝送ストリームを示している。セルは１ｍｓ離間し、これらがバーストとして知られるグループに束ねられ、バースト間には不規則な遅延が存在している。成形器はセルバーストを受入れて、図６（B）に示すように、セルが均一な３ｍｓ間隔で伝送されるようにセルを均一に分配する。
【００４０】
一般的に言えば、図７に示すように、本発明により構成された成型器６０は、２つの基本ブロック、即ちセル記述子（ＣＤ）処理ブロック７０、および形状ID処理ブロック７２を備えている。これらの機能ブロックは、分離したＡＳＩＣとして実現することも、または同一チップ上に実現することもできる。以下に、CD処理ブロック７０をDALEK７０と称し、また形状ＩＤ処理ブロック７２をTARDIS７２と称する。公知のように、セル記述子（ＣＤ）は、各セルを表す記述子である。より効率的な処理を行うために、各セルの代わりに各セル毎のＣＤが制御経路を通してルートされる。破棄サブシステム５５及び成型器６０がＣＤを処理すると、対応するセルがメモリから出力される。ＣＤフォーマットの例を図８に示す。
【００４１】
DALEK７０はＣＤを格納し、トークン（形状ＩＤ）を生成する。形状ＩＤは基本的には、セルの伝送可能なレートを指定する所定の“形状”である。動作中本発明の成型器は、成形されたセルレートをユーザが指定することを可能にし、またはユーザはソフトウェア制御の決定を据え置くことができる。トークンはDALEK７０からTARDIS７２へ出力される。TARDIS７２は形状ＩＤを処理し、トークンをDALEK７０へ戻す。詳細を後述するように、DALEK７０自体は適切なＣＤを出力する。
【００４２】
各セル毎のＣＤ内の接続識別子（接続ＩＤ）から、DALEK７０は適切な形状ＩＤを決定する。TARDIS７２は、各独自の形状ＩＤ毎にセル間の最小時間間隔を指定するテーブルを含んでいる。トークンが“成熟”する（即ち、セルが特定の接続のために出て行くことができるようになる）と、トークンがDALEK７０へ返送される。次いで、DALEKはどのＶＣが優先順位を有しているのかを正確に決定し、セルを送出する。即ち、たとえより高い優先順位のＶＣ上のセルが始めにトークンを生成しなくとも、それが送られる。本発明によれば、特定の接続を、他の接続には無関係に成形することができる。また、多数の異なる接続を、同一の形状ＩＤに従って成形することができる。従って、高及び低優先順位トラフィックを同一の物理的接続内へ送ることができる。
【００４３】
図９は、本発明の１実施の形態のより詳細なブロック図である。DALEK７０は３つの分離したメモリアレイ、即ち形状ＲＡＭ７０１、COIN ＲＡＭ７０２、及びデータＲＡＭ７０３を使用する。同様に、TARDISは３つのアレイ、即ちGCRA（総称セルレートアルゴリズム）ＲＡＭ７２１、リンクＲＡＭ７２２、及びMINT ＲＡＭ７２３と対話する。DALEK７０及びTARDIS７２は、それらの関連ＲＡＭアレイと共に、成型器６０の完全論理機能を実現している。
【００４４】
TARDIS７２とDALEK７０との間の関係は、それぞれマスター及びスレーブの一方である。TARDIS７２は２つのブロックを接続するインタフェースを制御し、主タイミングシーケンス信号をDALEK７０へ供給する。対話は、形状ＩＤ及び管理データを含む。形状ＩＤはTARDIS７２とDALEK７０との間で交換され、ＣＤの管理をＣＤ出力時点のスケジューリングから切り離す。前者はDALEK７０の責任であり、後者はTARDIS７２の責任である。６つ（各方向に３つ）の形状ＩＤを、各主タイミングシーケンスでDALEK７０とTARDIS７２との間で渡すことができる。
【００４５】
DALEK７０は、TARDIS７２を介して外部ＣＰＵによって管理される。TARDIS７２は、各主タイミングシーケンス毎に１回、全てのDALEK７０読出しレジスタを読出してローカルコピーを維持し、これらのコピーはＣＰＵによって読出される。同様に、DALEK７０のために意図されているＣＰＵ書込みデータは、ＣＰＵから到着する１主タイミングシーケンス中にTARDIS７２からDALEK７０へ転送される。DALEK７０状態レジスタの若干のビットは、TARDIS７２の割込み出力を表明することができる。これらの各割込み源は、個々に動作可能にされる。TARDIS７２からDALEK７０へ転送される全てのイベントフラグはＣＰＵによって読出されるまで捕捉され、保持される。DALEK７０とTARDIS７２との間の通信は、共用データバス＋制御信号を使用して達成される。形状ＩＤ及び管理データの両者は、同一のバスを共用する。主タイミングシーケンスに基づく時分割多重化が、全ての要求されたデータの転送のために必要なタイミング及び帯域幅を保証する。
【００４６】
TARDIS ブロック
図１０は、TARDIS７２（及び関連ＲＡＭ）のブロック図であって、このブロックを通る形状ＩＤトークンのデータの流れを示している。先ず、形状ＩＤトークンがDALEK７０から受信され、その適合性が調べられる。適合する形状ＩＤトークンは直ちにDALEK７０へ返送され、一方適合しない形状ＩＤトークンはカレンダー待ち行列内へ挿入される。形状ＩＤトークンはカレンダー待ち行列から“成熟”リストへ転送され、次いで形状ＩＤトークンはDALEK７０へ伝送される。TARDIS７２は、主タイミングシーケンスに同期しているシーケンス（後述）を使用して動作し、シーケンス同期をDALEK７０へ供給する。TARDIS７２によって管理されるデータ構造は、DALEK７０へ直ちに出力するための、１組のGCRA構成及び状態データ、スケジュールされた形状ＩＤのカレンダー待ち行列リンクド（リンクされた）リストアレイ、及び形状ＩＤの“成熟”リンクドリストを含む。
【００４７】
形状毎のGCRA構成及び状態データは、TARDIS７２によってGCRA ＲＡＭ７２１内に維持される。構成データは、形状のレートを定義する最小セル間隔を含む。状態データは、スケジュール時及びカウントフィールドを含む。スケジュール時は、次の形状ＩＤトークンの出力時点である。カウントは、現在TARDIS７２内に存在している形状ＩＤトークンの数である。最小セル間隔は、主ＣＰＵからアクセス可能である。GCRAデータは、各主タイミングシーケンス中に６回まで、形状ＩＤトークンの出力時点をスケジュールするために使用される。若干のスケジュールされた形状ＩＤトークンは、後述するように、カレンダー待ち行列へ挿入され、他の形状ＩＤトークンは形状のカウントフィールド内に保持される。
【００４８】
カレンダー待ち行列リンクドリストアレイは、TARDIS７２によってMINT ＲＡＭ７２３及びリンクＲＡＭ７２２内に維持される。この構造は、各カレンダー時毎に１つの64Kリンクドリストのアレイである。カレンダ待ち行列をリンクされたリストのアレイとして実現すると、複数の形状の形状ＩＤトークンを同時にスケジュールすることができる。MINT RAM７２３はリンクされたリストの先頭と末尾を保持する。各スケジュールされた形状ＩＤトークンは、通常は、計算されたスケジュール時のためのカレンダー待ち行列に添付される。若干の環境の下では、形状ＩＤは現時点＋１のためのリストに添付される。
【００４９】
各主タイミングシーケンス中に、カレンダー時が前進する。新しい現時点のためのカレンダー待ち行列リストは、“成熟”リンクドリストの末尾に転送される。このようにすると、“古い”カレンダー時のためのカレンダー待ち行列リストは自動的に空にされる。“成熟”リンクドリストは、内部論理及びリンクＲＡＭ７２２を使用するTARDIS７２によって維持される。この構造は、直ちにDALEK７０へ出力するために待ち行列に入れられた形状ＩＤの単一のリンクされたリストである。
【００５０】
各主タイミングシーケンス中に、３つまでの形状ＩＤトークンをDALEK７０へ転送することができる。シーケンス中に受信された適合形状ＩＤトークンに優先順位が与えられ、次の順位は“成熟”リンクドリストからの形状ＩＤトークンである。これにより、適合セルのストリームに対して輻輳が与える衝撃を最小にすることができる。カレンダー待ち行列及び“成熟”リンクドリストのためのリンクは、共にリンクＲＡＭ７２２を使用する。各形状からは、単一の形状ＩＤトークンだけしかスケジュールすることができないから、即ちこれらのリスト構造の何れにも１つしか存在しないから、16Kリンクだけでよい。リンクＲＡＭ７２２のアドレスは形状ＩＤであり、戻されるデータは同一リスト内の次の形状ＩＤトークンである。図１１はカレンダー待ち行列を示し、図１２は“成熟”リンクドリスト構造を示している。
【００５１】
TARDIS７２内では、時間は、１主タイミングシーケンスの分解能及び64K主タイミングシーケンスの範囲を与える16ビット２進フィールドで表される。現時点は各主タイミングシーケンスの開始時に１回インクリメントされる。最小セル間隔は、主タイミングシーケンスの1／256の分解能、及び64K主タイミングシーケンスの範囲を与える24ビット２進フィールドで表される。間隔の16の最上位ビットは、“整数部”として知られている。間隔の８つの最下位ビットは、“小数部”として知られている。各形状のピークセルレート（ＰＣＲ）は、レートの逆数である最小セル間隔として定義されている。最小及び最大許容レートを、図１３のテーブルに示す。
【００５２】
高帯域幅限界は、TARDIS７２によって強化されてはいない。従って、より高い帯域幅（即ち、より小さい最小セル間隔）を有する形状ＩＤが正しく成形される保証はない。成型器６０の出力帯域幅が制限されているので、他の成形された接続が存在する場合には、このような形状ＩＤは重大なセル遅延変動を受ける恐れがある。低帯域幅限界は、TARDIS７２によって強化されている。この限界よりも大きい最小セル間隔を有するように構成された形状ＩＤは成形されない（即ち、それはあたかも最小セル間隔が0.001：00であるかのように処理される）。図１４は、本発明の１実施の形態により、TARDIS７２内で構成することができる最小セル間隔の例を示している。
【００５３】
TARDIS７２内のスケジューリングは、
１．DALEK７０から形状ＩＤトークンを受信した時（主タイミングシーケンス内で３つまで）、
２．“成熟”リストの先頭の形状ＩＤトークンがDALEK７０へ伝送される時（主タイミングシーケンス内で３つまで）、
に遂行される。図１５は、スケジュール動作のための真理値表である。この表の以下の説明では、上述した形状ＩＤトークンが単一の形状に属していることに注目されたい。TARDIS７２によって支援される16Ｋ形状は独立的に処理される。
【００５４】
形状ＩＤトークンがDALEK７０から受信され、TARDIS７２内に形状ＩＤトークンが存在しない（カウント０によって指示される）場合に、スケジューラの“最初のイン”結果が発生する。“最初のイン”は、形状ＩＤトークンをDALEK７０へ戻させ（それが適合している場合）、またカレンダー待ち行列内へ挿入させる。更に、カウントがインクリメントされる。これは、TARDIS７２内に“実”形状ＩＤが存在しないにも拘わらず、“ゴースト”形状ＩＤトークンがTARDIS７２内に存在し続けるという、このアルゴリズムの重要な特性を示している。カウントは、実際に、“実”形状ＩＤトークンの数＋１“ゴースト”である。
【００５５】
“次のイン”のスケジューラ結果は、DALEK７０から１つまたは複数の形状ＩＤトークンが受信され、TARDIS７２内に既に形状ＩＤトークンが存在している（非０カウントによって指示される）場合に発生する。形状ＩＤトークン内の“次のイン”結果は、カウントに対するインクリメントの形状でTARDIS７２内に保持される。この形状は、現在は適合していないので、形状ＩＤトークンはDALEK７０へは戻されない。また、形状ＩＤトークンが既に存在しているので、それはカレンダー待ち行列内へ挿入もされない。
【００５６】
“次のアウト”のスケジューラ結果は、“成熟”リストの先頭の形状ＩＤトークンがDALEK７０へ送られ、TARDIS７２内に複数の形状ＩＤトークンが存在している（１より大きいカウントによって指示される）場合に発生する。“次のアウト”により、カレンダー待ち行列内へ形状ＩＤトークンが挿入され、カウントがデクレメントされる。“ゴーストアウト”のスケジューラ結果は、“成熟”リストの先頭の形状ＩＤトークンがDALEK７０へ送られ、TARDIS７２内に“ゴースト”形状ＩＤトークンだけが存在している（１のカウントによって指示される）場合に発生する。“ゴーストアウト”により、カウントは０にセットされる。この特別な“ゴースト”形状ＩＤは、システムへ出力すべきＣＤが見出されないのでDALEK７０によって無視される。
【００５７】
形状ＩＤトークン内の“最初のイン”及び“次のアウト”スケジューリング結果は、カレンダー待ち行列リスト（スケジュール時のためのリスト）に添付しなければならない。各形状ＩＤを配置するのは正確に何処であるかの決定は、以下の２つの要因によって複雑にされる。
１．カレンダー待ち行列が64Ｋのエントリを有しているので、ポインタは規則的に循環（ラップアラウンド）する。
２．“成熟”リストにおける輻輳が、スケジュール時を“過去”に配置することができる。
図１６のテーブルは、カレンダー待ち行列挿入時計算のための真理値表を定義している。もし“現時点”が選択されれば、形状ＩＤトークンは（現時点＋１）カレンダー待ち行列に配置される。次いで、それは、次の主タイミングシーケンスにおいて“成熟”リストに添付される。
【００５８】
TARDIS７２によって遂行される動作シーケンスは、主タイミングシーケンスに密に結合されている。これらのシーケンスを、スケジュール、成熟、及び管理と名付ける。
【００５９】
スケジュールシーケンス
このシーケンスは、形状ＩＤのスケジューリングを遂行する。このシーケンスは、DALEK７０から形状ＩＤトークンを受信することによって、または形状ＩＤトークンを“成熟”リストからDALEK７０へ伝送することによって開始される。このシーケンスは、形状ＩＤエントリをカレンダー待ち行列内へ挿入し、据置きカウントを更新する。図１７のテーブルは、このシーケンスを示している。
１．GCRA ＲＡＭ：形状ＩＤのための現在のGCRA構成及び状態を読出せ。
２．内部論理内のスケジューリングアルゴリズムの実行せよ。
３．GCRA ＲＡＭ：更新されたGCRA構成及び状態の書込め。
４．MINT ＲＡＭ：スケジュール時カレンダー待ち行列の現在の先頭／末尾を読出せ。
５．MINT ＲＡＭ：スケジュール時カレンダー待ち行列の更新されたの先頭／末尾を書込め。
６．リンクＲＡＭ：古いカレンダー待ち行列末尾からリンクを新しい末尾に書込め。
MINT ＲＡＭ及びリンクＲＡＭ動作は、スケジューリングアルゴリズムが“最初のイン”または“次のアウト”の結果を戻した時に限って遂行される。
【００６０】
成熟シーケンス
このシーケンスは、形状ＩＤトークンのリストを、現時点カレンダー待ち行列から“成熟”リンクドリストの末尾へ転送し、最初の３つの形状ＩＤをTARDIS７２内へロードする。それは、各主タイミングシーケンス中に１回開始される。図１８のテーブルは、
MINT ＲＡＭ：カレンダー待ち行列から現時点リストを読出せ、
MINT ＲＡＭ：カレンダー待ち行列内の現時点リストをクリアせよ、
リンクＲＡＭ：現時点リストを“成熟”リストの末尾へリンクせよ、
リンクＲＡＭ：“成熟”リスト内の次の（第２の）形状ＩＤトークンを読出せ、
リンクＲＡＭ：“成熟”リスト内の次の（第３の）形状ＩＤトークンを読出せ、
のシーケンスを示している。
【００６１】
管理シーケンス
このシーケンスは、最小セル間隔をCCRA ＲＡＭへ／から書込む、または読出す。これらの動作により、ＣＰＵは最小セル間隔を構成し、監視することができる。図１９のテーブルはこのシーケンスを示している。テーブルは、次のシーケンスを示している。
１．書込みレジスタＷＲ ＳＩＤによって指し示されたアドレス（形状ＩＤ）が読出され、データ（ＭＣＩ）が読出しレジスタＲＲ ＭＣＩ ＩＮＴ及びＲＲ ＭＣＩ ＦＲＡ内に配置される。読出しレジスタは、読出し要求に関してだけロードされる。
２．書込みレジスタＷＲ ＳＩＤによって指し示されたアドレス（形状ＩＤ）が、データ（ＭＣＩ）を使用して書込みレジスタＷＲ ＭＣＩ ＩＮＴ及びＷＲ ＭＣＩ ＦＲＡ内に書込まれる。このステップは、書込み要求に関してだけ発生する。
【００６２】
総合シーケンス例
TARDIS７２が遂行する総合シーケンスの例を図２０に示す。このようなシーケンスは、各主タイミングシーケンス中に走る。各総合シーケンスは、上述したスケジュール、成熟、及び監視シーケンスを組合わせる。図２０の例は、
１． DALEK７０からの３つの形状ＩＤトークンが、全てスケジュール“最初のイン”を有している、
２． DALEK７０からの３つの“成熟”形状ＩＤトークンが、全て“次のアウト”スケジュール結果を有している、
３． ＣＰＵがGCRA ＲＡＭ構成書込みを要求している、
という最悪シナリオを示している。
【００６３】
DALEK ブロック
DALEKは、成型器内に現在存在しているセル記述子（ＣＤ）の格納を制御する（各接続ＩＤ毎のリンクされたリストの管理を含む）。図２１は、ＣＤ処理機能ブロック、即ちDALEK７０内へ、及びそれからのＣＤ及び関連形状ＩＤトークンの流れを示している。システムからＣＤを受信すると、形状ＩＤの表引きが先ず遂行される。ＣＤは“後刻”リスト内に格納され、形状ＩＤトークンはTARDIS７２へ出力される。形状が確認されると、形状ＩＤトークンがTARDIS７２からDALEK７０へ入力される。ＣＤは“今”リストへ移動し、ＣＤはシステムへ返送される。
【００６４】
DALEK７０は、システム主タイミングシーケンスに同期しているシーケンスを使用して動作する。シーケンス同期は、TARDIS７２によって与えられる。主タイミングシーケンスは、37クロック期間の長さである。これは約685ｎｓ、またはＳＴＳ−１２Ｃをベースとするシステムにおいては１セル時間である。接続ＩＤ毎の構成可能なＣＬＰオプションフィールドにより、各ＣＤは“ＣＬＰクリア”か、“ＣＬＰ不変”の何れかとして処理することができる。“ＣＬＰクリア”接続ＩＤ上のＣＤは、DALEK７０へエントリされるとリセットされるＣＬＰビットを有している。“ＣＬＰ不変”接続ＩＤ上のＣＤは、不変のまま渡されるＣＬＰビットを有している。ＣＬＰ及びその関連パリティビットは、DALEK７０によって変更される唯一のＣＤのフィールドである。
【００６５】
DALEK７０によって管理されているデータ構造、及びDALEK７０を通るデータの流れを以下に説明する。任意の時点に、DALEK７０内の各ＣＤは、２つのリンクされたリスト構造の一方内に格納される。各形状ＩＤ毎に１つの、１組の“後刻”リンクドリストは、ＣＤを受信した時からそれらが伝送のための準備が整うまで、ＣＤを保持する。“今”リンクドリストは、伝送のための準備が整っている全てのＣＤを保持する。
【００６６】
各主タイミングシーケンス中に、３つまでのＣＤをシステムから受信することができる。各ＣＤは、ToShapeビット及び接続ＩＤフィールドを含む。ToShapeビットがセットされている（形状ＩＤマッピングに対する有効接続ＩＤが存在している）各ＣＤは、DALEK７０によって外部ＲＡＭアレイ（即ち、データバッファ７０３）内に格納される。一旦格納されたＣＤはリスト間で転送されても移動せず、代わりにリンクが操作される。リンクは、ＣＤの一部としてデータバッファ７０３内に格納される。
【００６７】
形状ＲＡＭ７０１と呼ばれる外部ＲＡＭアレイは、接続ＩＤから形状ＩＤへのマッピングテーブルを保持している。成形は、形状ＩＤに対して遂行される。複数の接続ＩＤを単一の形状ＩＤへマップすることができる。接続ＩＤのためのＣＬＰオプションフィールドは、その形状ＩＤと共に形状ＲＡＭ７０１内に格納される。ToShapeビットがセットされているＣＤは、16Ｋ“後刻”リンクドリストの１つに添付される。“後刻”リストは、ＣＤ内のフィールドから４レベルの優先順位を適用する優先順序をベースとしている。このフィールドは、成形された接続内の優先順位（通常は、ＶＣ優先順位）を定義する。“後刻”リストの先頭及び末尾は、COIN ＲＡＭ７０２と呼ばれる分離した外部ＲＡＭ内に格納される。
【００６８】
受信したＣＤの格納と同時に、DALEK７０は、GCRA評価のために形状ＩＤをTARDIS７２へ送る。そのＣＤはそれがリストの先頭に到達し、形状ＩＤがTARDIS７２から入力されるまで“後刻”リスト内に留まる。TARDIS７２から入力される形状ＩＤトークンは、その形状ＩＤを有するＣＤをシステムへ出力できることを指示する。ＣＤ選択は、最高優先順位においてその形状ＩＤのためのリストを占有することである。それは、“後刻”リストの先頭から“今”リストの末尾へ転送される。
【００６９】
“今”リストは、直ちに出力する準備が整っているＣＤを受入れるための出力待ち行列を提供する。各主タイミングシーケンス中に１つのＣＤしか出力することができないにも拘わらず、３つまでの形状ＩＤをTARDIS７２から入力することができるので、このリストが必要である。“今”リストは、ＣＤ内のフィールドから４レベルの優先順位を適用する優先順序をベースとしている。このフィールドは、成形された接続間の優先順位（通常は、ＶＰ優先順位）を定義する。“今”リストの先頭及び末尾は、１つの“今”リストだけが存在しているので、DALEK７０内に格納される。
【００７０】
３つの全ての外部ＲＡＭアレイ内に保持されているデータは、パリティビットによって保護される。全メモリ読出し動作に続いてパリティが調べられ、エラーがあればフラグが立てられる。同様に、システムから受信したＣＤのパリティが調べられ、エラーにフラグが立てられる。図２２は、これらのデータ構造及びDALEK７０を通るデータの流れを示している。
【００７１】
DALEK７０によって遂行される動作シーケンスは、主タイミングシーケンスと密に結合されている。これらのシーケンスには、受信、転送、伝送、及び管理と命名されている。
【００７２】
受信シーケンス
このシーケンスは、システムからＣＤを受入れ、形状ＩＤをデコードし、そしてそのＣＤを形状ＩＤ“後刻”リンクドリストに添付する。形状ＩＤトークンは、このシーケンス中にTARDIS７２へ渡される。図のテーブルはこのシーケンスを示している。
１．形状ＲＡＭ：ＣＤ接続ＩＤフィールドからデコードされた形状ＩＤを読出せ。
２．COIN ＲＡＭ：形状ＩＤ／優先順位リストの先頭／末尾を読出し、次いで更新されたデータを書込め。
３．データバッファ：ＣＤ及びヌルリンクを書込み、次いでリストの古い末尾へのリンクを書込め。
【００７３】
転送シーケンス
このシーケンスは、ＣＤを“後刻”リンクドリストから“今”リンクドリストへ転送する。転送は、TARDIS７２から形状ＩＤトークンを受信することによって開始される。図２４のテーブルはこのシーケンスを示している。
１．COIN ＲＡＭ：全ての４優先順位“後刻”リストの先頭／末尾を読出せ。
２．データバッファ：“今”優先順位、及び選択された“後刻”リストの先頭のリンクを読出せ。
３．COIN ＲＡＭ：“後刻”リストの新しい先頭／末尾を書込め（データバッファリンクから）。
４．データバッファ：“今”リストの新しい末尾へのリンクを書込め。
【００７４】
伝送シーケンス
このシーケンスは、“今”リンクドリストからＣＤを読出し、システムへそのＣＤを出力する。図２５はこのシーケンスを示している。
１． データバッファ：ＣＤをワード毎に読出せ。
２． ＣＤ データバス駆動。
３． ＣＤ ＳＨＰ ＲＤＹ表明。
【００７５】
管理シーケンス
このシーケンスは、形状ＩＤを形状ＲＡＭへ書込み（もし要求されれば）、形状ＲＡＭから形状ＩＤを読出す。これらの動作により、DALEK７０内の形状ＩＤマッピングへの接続ＩＤの構成及び監視が可能になる。図２６のテーブルはこのシーケンスを示している。
１．書込みレジスタＣＰＵ ＷＲ ＣＩＤによって指し示されているアドレス（接続ＩＤ）が書込みレジスタ内のデータ（形状ＩＤ）を使用して書込まれる。
２．ＣＰＵ ＷＲ ＣＩＤによって指し示されているアドレス（接続ＩＤ）が読出され、そのデータ（形状ＩＤ）が読出しレジスタＣＰＵ ＲＤ ＣＩＤ内に配置される。
【００７６】
総合シーケンス例
図２７に、DALEK７０が遂行する総合シーケンスの例を示す。このようなシーケンスは、各主タイミングシーケンス中に走る。各総合シーケンスは、前項に記載した受信、転送、伝送、及び管理シーケンスを組合わせる。ここで選択した総合シーケンスの例は、次の最悪シナリオである。
１．システムから３つのＣＤを受信して３つの受信シーケンスが開始される。
２．TARDIS７２から３つの形状ＩＤトークンを受信して３つの転送シーケンスが開始される。
３．“今”リストが占有されて伝送シーケンスが開始される。
４．ＣＰＵ ＳＲ ＷＲＲＥＱビットが表明されて管理シーケンスが開始される。
【００７７】
先に定義したように、接続毎の形状ＩＤと共に“今”及び“後刻”を本発明に使用する場合には、それぞれ仮想接続（ＶＣ）及び仮想経路（ＶＰ）内に優先順位を与える。これにより、ＶＰ内で成形されている接続のための相対優先順位が効果的に保存される。また、カレンダー待ち行列を使用すると、“仮想終了時間”（ＶＦＴ）計算の複雑さが減少し、得られたＶＦＴはそのアルゴリズムの複雑さ［Ｏ（１）対Ｏ（Ｎ log Ｎ）］と境を接する一定の時間を有している。最後に、“活動リスト”を使用することにより、接続毎のスケジューリングの複雑さが減少する。
【００７８】
当分野に精通していれば、本発明の範囲及び思想から逸脱することなく本発明に種々の変更をなしえることが理解されよう。特許請求の範囲内で上述した以外に実施できることは明白である。
【図面の簡単な説明】
【図１】 マルチノードネットワークを通して接続されている複数の源／行先（Ｓ／Ｄ）ユーザの概要ブロック図である。
【図２】 図１のネットワーク内のノードのシーケンスを通して１つのＳ／Ｄユーザを別のＳ／Ｄユーザに接続する回路の概要図である。
【図３】 情報を源（Ｓ）から順方向（Ｆ）に行先（Ｄ）へ送り、制御信号を逆方向（Ｒ）へ源（Ｓ）に伝送する仮想チャンネル接続を有する図２の回路の概要図である。
【図４】 図１のネットワーク内のノード（Ｎ）の典型的な１つの概要図である。
【図５】 図４のノード内のキューイングユニットの概要図である。
【図６Ａ】 各セルが１ｍｓ離間し、トラフィックの“バースト”がランダムに離間しているセルトラフィックを示す図である。
【図６Ｂ】 セルが３ｍｓの均一間隔に“成形”された後の図６Ａのセルトラフィックを示す図である。
【図７】 本発明により構成された成型器の機能ブロックのブロック図である。
【図８】 セル記述子（ＣＤ）フォーマットの例である。
【図９】 本発明により構成された成型器の一例のブロック図である。
【図１０】 形状ＩＤ処理ブロックを通る形状ＩＤのデータの流れを示す図である。
【図１１】 本発明により構成されたカレンダー待ち行列を示す図である。
【図１２】 形状ＩＤの“成熟”リンクドリストを示す図である。
【図１３】 本発明の一実施の形態による最小及び最大セル間隔のテーブルである。
【図１４】 最小セル間隔の例のテーブルである。
【図１５】 スケジューリング動作のための真理値表である。
【図１６】 カレンダー待ち行列挿入時点計算の真理値表である。
【図１７】 形状ＩＤをスケジュールするためのスケジュールシーケンスを示す図である。
【図１８】 形状ＩＤ処理ブロックの“成熟”シーケンスの動作を示す図である。
【図１９】 形状ＩＤ処理ブロックの管理シーケンスの動作を示す図である。
【図２０】 形状ＩＤ処理ブロックが遂行する総合シーケンスの例を示す図である。
【図２１】 ＣＤ処理ブロックを通るＣＤ及び形状ＩＤのデータの流れを示す図である。
【図２２】 ＣＤ処理ブロック内のデータ構造及びデータの流れを示す図である。
【図２３】 ＣＤ処理ブロックにおける受信シーケンスの動作を示す図である。
【図２４】 ＣＤ処理ブロックにおける転送シーケンスの動作を示す図である。
【図２５】 ＣＤ処理ブロックにおける伝送シーケンスの動作を示す図である。
【図２６】 ＣＤ処理ブロックにおける管理シーケンスの動作を示す図である。
【図２７】 ＣＤ処理ブロックによって遂行される総合シーケンスの例を示す図である。

Claims (9)

1. 成型器ユニットであって、
   複数のセル記述子を受信し処理する処理ブロックと、接続ＩＤから形状ＩＤへのマッピングテーブルを保持している形状ＲＡＭと、“後刻”リストの先頭及び末尾を格納しているCOIN ＲＡＭと、当該複数のセル記述子を格納するデータバッファアレイとを具備するセル記述子（ＣＤ）処理ブロックと、
   複数の形状ＩＤを処理する処理ブロックと、形状毎のGCRA構成及び状態データを格納する総称セルレートアルゴリズム（GCRA）ＲＡＭと、カレンダー待ち行列リンクドリストアレイを格納するリンクＲＡＭとを具備する形状ＩＤ処理ブロックと、
   を備え、
   上記セル記述子処理ブロックは、受信した上記複数のセル記述子に対応する上記複数の形状ＩＤを上記形状ＩＤ処理ブロックへ出力し、
   上記形状ＩＤ処理ブロックは、上記複数の形状ＩＤそれぞれの適合性を検査し、適合した形状ＩＤを上記セル記述子処理ブロックへ返送し、そして、適合していない形状ＩＤをカレンダー待ち行列内へ挿入し、さらに、成熟した形状ＩＤを当該カレンダー待ち行列から当該セル記述子処理ブロックへ返送するよう構成されていることを特徴とする成型器ユニット。
2. 上記形状ＩＤ処理ブロックは、上記カレンダー待ち行列を格納するMINT ＲＡＭを更に備えていることを特徴とする請求項１に記載の成型器ユニット。
3. ネットワークスイッチ内でセルトラフィックを成形する方法であって、
   セル記述子処理ブロックにおいてセル記述子（ＣＤ）を受信するステップと、
   上記セル記述子から形状ＩＤをデコードし、上記セル記述子を“後刻”リスト内に格納するステップと、
   上記形状ＩＤを形状ＩＤ処理ブロックへ出力するステップと、
   上記形状ＩＤの適合性を検査するステップと、
   もし上記形状ＩＤが適合していれば、上記形状ＩＤを上記セル記述子処理ブロックへ返送するステップと、
   もし上記形状ＩＤが適合していなければ、上記形状ＩＤをカレンダー待ち行列内へ挿入し、上記形状ＩＤが成熟した時に、上記形状ＩＤを当該カレンダー待ち行列から成熟リストへ転送し、次いで上記形状ＩＤを上記セル記述子処理ブロックへ返送するステップと、
   上記セル記述子処理ブロックが上記形状ＩＤを受信した時に、上記セル記述子を“今”リストへ移動させるステップと、
   上記セル記述子を上記セル記述子処理ブロックから出力するステップと、
   を含むことを特徴とする方法。
4. 各形状ＩＤは異なる接続に対応し、上記“今”及び“後刻”リストは、仮想接続（ＶＣ）の優先順位を特定することを特徴とする請求項３に記載の方法。
5. 上記形状ＩＤが成熟した時には、たとえより高い優先順位のＶＣが当該形状ＩＤを生成しなくても、上記セル記述子処理ブロックがＶＣを決定して送出し、これにより、高い優先順位のＶＣがより低い優先順位のＶＣの前に送られることを特徴とする請求項４に記載の方法。
6. 各接続は、異なるレートで成形されることを特徴とする請求項３に記載の方法。
7. 複数の接続は全て同一の形状ＩＤにセットされることを特徴とする請求項３に記載の方法。
8. 通信システムであって、
   情報を供給する複数の源と、
   上記複数の源からの上記情報を受信する複数の行先と、
   上記複数の源と上記複数の行先とを接続するネットワークを形成する１つまたはそれ以上のノードと、
   を備え、
   上記ネットワークは、上記情報を輸送するための複数のチャンネルを有し、上記ノードのそれぞれはキューイング制御ユニットを含み、上記キューイング制御ユニットは、
   待ち行列管理部と、
   破棄ブロックと、
   成型器と、
   を含み、上記成形器は、
   セル記述子（ＣＤ）処理ブロックと、
   形状ＩＤ処理ブロックと、
   を含み、
   上記セル記述子処理ブロックは、
   複数のセル記述子（ＣＤ）を受信し、
   上記複数のセル記述子から対応する複数の形状ＩＤをデコードし、そして、当該複数のセル記述子を“後刻”リスト内に格納し、
   上記複数の形状ＩＤを上記形状ＩＤ処理ブロックに出力し、
   上記形状ＩＤ処理ブロックは、
   上記複数の形状ＩＤそれぞれの適合性を検査し、
   適合した形状ＩＤを上記セル記述子処理ブロックへ直接返送し、
   適合していない形状ＩＤをカレンダー待ち行列へ挿入し、成熟した形状ＩＤを当該カレンダー待ち行列から上記セル記述子処理ブロックへ返送することを特徴とし、
   上記キューイング制御ユニットは、更に、
   上記成型器によって出力された上記複数のセル記述子を受信及び処理するポート毎の待ち行列ユニットと、
   上記ポート毎の待ち行列ユニットからの出力を受信及び処理するデキューユニットと、
   上記デキューユニットからの出力を受信及び処理するマルチキャストサーバーと、
   上記マルチキャストサーバーからの出力を受信及び記憶する自由バッファリストユニットと、
   を含むことを特徴とする通信システム。
9. 上記セル記述子処理ブロックが上記形状ＩＤを上記形状ＩＤ処理ブロックから受信した時に、上記セル記述子処理ブロックは、上記形状ＩＤに対応するセル記述子を“今”リストへ移動させ、そして上記形状ＩＤに対応するセル記述子を出力することを特徴とする請求項８に記載の通信システム。

Images