JPH1070556A

JPH1070556A - Ａｔｍスイッチ

Info

Publication number: JPH1070556A
Application number: JP11949397A
Authority: JP
Inventors: C Rooa Hugh; ヒュー・シー・ローア; Gooshiyu Abijitsuto; アビジット・ゴーシュ; H Howerd John; ジョン・エイチ・ハワード; Harufusa Kondo; 晴房近藤; B Osborne Randy; ランディ・ビー・オズボーン; Shien Chia; チア・シェン; Jien Chin; チン・ジェン
Original assignee: Mitsubishi Electric Research Laboratories Inc
Current assignee: Mitsubishi Electric Research Laboratories Inc
Priority date: 1996-05-10
Filing date: 1997-05-09
Publication date: 1998-03-10
Also published as: US5732087A

Abstract

(57)【要約】【課題】ディジタル通信ネットワークのＡＴＭスイッ
チが、多くの異なる適用と目的のために広範囲のクラス
のスケジューリングアルゴリズムを実行することが出来
る。【解決手段】待ち合わせシステムは、優先順位により
構成されたＡＴＭスイッチを有するタグ方式の主待ち行
列７０と、伝送がまだスケジューリングされないＡＴＭ
セルを有し、かつ、仮想チャネルにより構成されている
副待ち行列７４とを備える。待ち合わせ決定モジュール
７２は、入信するＡＴＭセルがどの待ち行列に配置され
るべきかを決定する。再待ち合わせ決定モジュール７８
は、個々の仮想チャネルをブロック化しない事象が起こ
ると動作する。【効果】ブロック化及び非ブロック化されたチャネル
の流れを制御することができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、セル（sells）
すなわちパケット（packets）がネットワークをノード
からノードへ横切るディジタル通信ネットワークに関
し、詳細には、セルがネットワーク内で一つのノードか
ら他のノードへ伝送される順序をスケジューリングする
改善されたシステムを有するディジタル通信ネットワー
クのＡＴＭスイッチに関するものである。

【０００２】

【従来の技術】一般に、ディジタル通信ネットワークに
おいて、メッセージすなわち情報の流れは、パケットつ
まりセルと呼ばれる小さい単位のシーケンスへ分割され
る。このようなセルすなわちパケットは、ノードからノ
ードへ伝送される。各ノードにおいて、ネットワークス
イッチと呼ばれるスイッチは、このセルすなわちパケッ
トを伝送する順番と、それらが伝送される次のノードを
選択する。従って、このようなネットワークでは、ディ
ジタル情報は、タイムリーな方法でその最終宛先へ到達
する。これらのネットワークスイッチは、タイムリーな
引き渡しの確実な保証を必要とする通信量、オーディオ
とビデオの連続媒体の通信量、及び非常に高速な応答を
必要とする通信量から成る多様な特性のネットワーク通
信量を支援出来ることが望ましい。

【０００３】一つの重要な種類のディジタル通信ネット
ワークは、非同期伝送モード（ＡＴＭ：Asynchronous T
ransfer Mode）ネットワークである。ネットワークを通
してノードからノードへ伝送される一定の大きさの小さ
いセルのシーケンスへ、データつまり情報を分割するこ
とにより、ＡＴＭネットワークは、ネットワーク内の一
つの地点つまりノードから一つ以上の他の地点つまりノ
ードへ、データの伝送を行う。このようなノードには、
高速パケットすなわちセルのスイッチングとネットワー
クのノード間の伝送とを行うＡＴＭスイッチがある。Ａ
ＴＭネットワークの一般的原理は、ジェイ・ブレイン・
ライレス（J.Bryan Lyles）とダニエル・シー・スウィ
ンハート（Daniel C. Swinehart）著、“新しいギガビ
ット環境とローカルとＡＴＭの役割（The Emerging Env
ironment and the Role of LocalATM）”、アイ・トリ
プル・イー・通信誌、３０巻、４号、１９９２年４月、
５２〜５８ページ、および、シー・ラム（C. Lamb）
著、“ＡＴＭへの促進（Speeding to the ATM）”、ユ
ニックス・レビュー、１０巻、１０号、１９９２年１０
月、２９〜３６ページ、の文献に述べられている。

【０００４】ＡＴＭネットワークに係わる主要な問題の
一つは、各スイッチにより伝送されるセルのスケジュー
リングの問題である。セルは、一般に、各スイッチによ
り待ち行列にバッファリングされる。渋滞がないとする
と、これらのセルは、スイッチにおいて入信リンクから
受信され、直ちに、送信リンクを通してほかの宛先へ伝
送される。しかし、セルが多数の入力（入信）リンクを
通して到着し、同一時間に同一出力（送信）リンクへ伝
送されなければならない場合、セルが望んでいる順番で
送られるように、セルの待ち行列を形成されることが必
要である。

【０００５】セルが何時、どの順番で伝送されると言う
スケジューリングを受け入れるために、セルがスイッチ
への到着順番に従って伝送される先入れ先出し方式“Ｆ
ＩＦＯ”順位システムを利用することが広く行われてい
る。リアルタイム適用を支援するネットワークの場合、
セルは一般に、また、優先順位を割り当てられ、優先順
位により個々の待ち行列に格納される。その後、セル
は、個々の待ち行列の優先順位により規定された順番で
伝送される。ＦＩＦＯと優先順位スケジューリングと
は、データの紛失なくタイムリーな伝送と言う限られた
保証を行うことしか出来ないので、これらの単純なシス
テムは、リアルタイム適用の限定された数とクラスとを
支援することしか出来ないことは理解されるであろう。

【０００６】例えば、ＡＴＭローカルワイドエリア・ネ
ットワークは、入信ネットワークリンクから発信リンク
への通信をスケジューリングし、送る非常に単純なスケ
ジューリングアルゴリズムを行う。通信量はＡＴＭ規定
によりＦＩＦＯ順序で処理されるが、少数の優先順位レ
ベル、普通２レベル、が非常に限定されたリアルタイム
通信条件で適用を支援するために設定されている。不幸
なことに、少数の静的に割り当てられた優先順位は、多
数の適用が進歩し、早い速度で発達しているために、中
程度規模のローカルエリアネットワークに対してかろう
じて足りている。さらに、適用がオーディオとビデオな
どの連続（複合）メディアを伝送することが必要とする
場合、すなわち、適用が予測できる応答をリアルタイム
で必要である場合、ネットワークサービスの品質と適時
制御とに対しすべての種類の予測と保証を行うことは、
実際に不可能である。

【０００７】進歩したＡＴＭネットワークスイッチが、
米国特許第５，４５５，８２５号公報に記載されてい
る。このＡＴＭネットワークスイッチは、スイッチのす
べての出力回線に共用される待ち行列とバッファメモリ
とから成っている。すなわち、すべての入力ポートから
の入力セルは、共通のバッファメモリへ直接に配置され
ている。共通の待ち合わせと共用されるバッファは、統
計的多重化を改善し、高速性能と低コストを具現化して
いる。共用されたバッファ内の各セルの参照は、共用さ
れた待ち行列に配置されている。各入力セルに関して、
数値的タグが決定され、待ち行列内に収められている。
セルは、待ち合わせ／探索モジュールによりこれらのタ
グに基づいた伝送のために待ち行列から選択される。リ
アルタイム通信量から成る多数クラスの通信量は、スイ
ッチにおいて支援され、各クラスは、単純な優先順位、
ＦＩＦＯ、つまりリアルタイムなどのそれ自身のスケジ
ューリングアルゴリズムとポリシーを有する。このよう
なスイッチは、多くの利点を有するが、仮想チャネル上
の伝送のブロック化をスイッチで制御することは、困難
である。従って、ラウンドロビン（round-robin）つま
りクレジット方式（credit-based）の種類の流れ制御を
実行することは、難しい。

【０００８】図１に関し、従来のＡＴＭスイッチ１０が
呈示されている。このようなＡＴＭスイッチは、米国特
許第５，４５５，８２５号公報により教示されているよ
うに実行することができ、この特許はここに参考に取り
入れられている。ＡＴＭスイッチ１０は入信回線１４を
有し、この回線は入力処理モジュール１６へ接続されて
おり、その出力は、待ち行列（合わせ）／探索モジュー
ル１８とセルバッファメモリ２０とへそれぞれ送られ
る。待ち行列／探索モジュール１８は、制御器２２の制
御を受ける。この制御器２２は、数ある中で、入力処理
モジュール１６と出力処理モジュール２４とを制御す
る。各入力処理モジュール１６と各出力処理モジュール
２４は、制御器２２により構成または再構成されるマイ
クロプロセッサとメモリまたはほかの手段から成ってお
り、スイッチに到着または出発する各セルにたいするネ
ットワークの条件に適切なすべての処理を行う。

【０００９】待ち行列／探索モジュール１８の出力は、
セルバッファメモリ２０の出力用に、各出力処理モジュ
ール２４へ送られる。符号２６で示されているように、
入力処理モジュール１６の出力は、宛先情報、タグおよ
びバッファアドレスが含まれており、これらは、待ち行
列／探索モジュール１８へ接続されている。さらに、符
号２８で示されているように、セルのヘッダーと本体
は、セルバッファメモリ２０へ接続されている。

【００１０】動作状態において、セルは、入力リンク１
４を経て入力処理モジュール１６へ達する。入力処理モ
ジュール１６は、到着セルについてセルごとの処理を行
う。すべてのＡＴＭスイッチに必要な正規の準備機能の
ほかに、入力処理モジュール１６は、セルの仮想チャネ
ルのスケジューリングアルゴリズムにより各セルのタグ
値を計算する。タグ値は、また、そのチャネルの状態と
セルの到着時間を基準にしている。仮想チャネルは、す
べてのほかのデータの流れから分離した、特定データ流
れの端末間の接続をなしている。ＡＴＭネットワークに
おいて、仮想チャネルは、セルのヘッダー内のビットの
フィールドにより識別される。入力処理モジュール１６
は、また、仮想チャネルの状態情報とスイッチにより維
持されたほかの情報を計算し、更新する。

【００１１】計算に続いて、タグ、宛先情報およびセル
のバッファアドレスが、待ち行列／探索モジュール１８
へ接続され、そこで、それらは待ち行列に格納される。
セルのヘッダーとセルのデータは、セルバッファメモリ
２０へ接続される。この時点で、セルのアドレス、宛先
およびタグは、待ち行列内にあり、そのセルのヘッダー
とデータは、セルバッファメモリ２０に格納される。次
に、入力処理モジュール１６は、自由に次のセルを受信
し、処理を始める。従って、入力処理は、対応する入力
リンク１４の１セルサイクルに割り当てられた時間内に
完了されなければならず、それは、入力リンク１４の帯
域幅でＡＴＭセルを受信するに必要な時間である。

【００１２】制御器２２の制御を受けて、待ち行列／探
索モジュール１８は、各出力処理モジュール２４に対応
する宛先ビットのセルについて、順次待ち行列を探索す
る。出力処理モジュール２４は、セルが送られる前に、
必要なすべての残りの計算を行う。次に、出力処理モジ
ュール２４は、出力リンク３０により、セルをネットワ
ークのほかのノード、つまり、その最終宛先へ伝送す
る。待ち行列／探索モジュール１８により行われた探索
は、最も早く接続した入力リンク１４とスイッチの出力
リンク３０へ割り付けられた１セルサイクル内で、すべ
ての出力処理器について完了されなければならない。米
国特許第５，４５５，８２５号公報は、待ち行列／探索
システムを詳細に述べている。

【００１３】

【発明が解決しようとする課題】上述したような従来の
ＡＴＭスイッチでは、仮想チャネル上の伝送のブロック
化をスイッチで制御することは困難であり、ラウンドロ
ビン（round-robin）つまりクレジット方式（credit-ba
sed）の種類の流れ制御を実行することは難しいという
問題点があった。

【００１４】この発明は、前述した問題点を解決するた
めになされたもので、二つの待ち行列を使用して、ブロ
ック化及び非ブロック化されたチャネルの流れを制御す
ることができるＡＴＭスイッチを得ることを目的とす
る。

【００１５】

【課題を解決するための手段】この発明に係るＡＴＭス
イッチは、非同期伝送モードネットワークにおいて使用
されるＡＴＭスイッチであって、出力回線への伝送の前
にセルを格納し、セルがタグ方式優先順位探索に基づき
伝送のために選択される主待ち行列と、ブロック化され
たチャネルのセルを格納し、そのチャネルがブロック化
されないときには、セルが前記主待ち行列への伝送のた
めに選択される副待ち行列と、セルを入力回線から受信
し、セルのチャネルがブロック化されるか否かにより、
セルを前記主待ち行列と前記副待ち行列のいずれか一つ
へ向かわせる待ち合わせ決定モジュールとを備えたもの
である。

【００１６】また、この発明に係るＡＴＭスイッチは、
さらに、前記主待ち行列から伝送されたセルのチャネル
の表示を受信する入力を有し、伝送されたセルの同一優
先順位クラスのブロック化されないチャネルのセルを前
記主待ち行列へ伝送するように前記副待ち行列を制御す
る再待ち合わせ決定モジュールを備えたものである。

【００１７】

【発明の実施の形態】

実施の形態１．図２に関し、この発明は、制御器２２Ａ
と関連して二重待ち行列アーキテクチャ（二重待ち行列
／探索モジュール）１８Ａを使用している。ＡＴＭスイ
ッチ１０Ａの残りの構造は、一般に、図１に示された従
来のスイッチ１０と同じである。二重待ち行列アーキテ
クチャ１８Ａと制御器２２Ａの詳細は、図３と図４に関
して説明する。

【００１８】図３に関し、この発明において、主待ち行
列７０は、非ブロック化された活性仮想チャネルに対応
する宛先へのセルを待ち合わせするために使用される。
主待ち行列７０は、図１に示された待ち行列／探索モジ
ュール１８と同様に、米国特許第５，４４５，８２５号
公報に述べられているように実行される。この主待ち行
列７０の他に、この発明は、入信セルが主待ち行列７０
か、または副待ち行列７４かのいずれかに配置されなけ
ればならないことを決定する待ち合わせ決定モジュール
７２を使用している。この待ち合わせ決定モジュール７
２は、入力セルに対応する仮想チャネルが、ブロック化
されるか、または、非ブロック化されるかを決定するた
めに仮想チャネルテーブル７６を使用する。ブロック化
されたチャネルのセルは、副待ち行列７４へ向けられ
る。非ブロック化されたチャネルのセルは、主待ち行列
７０へ向けられる。

【００１９】副待ち行列７４は、例えば、Ｈ．コンドー
ほか（H.Kondoh et al）著、“ＡＴＭスイッチＬＳＩ用
効率的自己時間設定待ち行列アーキテクチャ（An Effic
ientSelf-Timed Queue Architecture for ATM Switch L
SI's）”、特注集積回路会議において、サンディェゴ、
１９９４年５月（コンドーほか１９９４年）、および、
“ＳＴＳタイプ共有バッファリングに基づく新しいＡＴ
ＭスイッチアーキテクチャおよびそのＬＳＩ実施（A Ne
w ATM Switch Architecture Based on STS-type Shared
Buffering and its LSI Implementation）”、Ｋ．オ
ーシマほか（K.Oshima）著、１９９２年国際スイッチン
グシンポジュウムにおいて、横浜、日本、１９２２年１
０月、３５９〜３６３ページ、述べられた優先順位待ち
行列に似た方法で実行することが出来、これは、ここに
参考に引用されている。これらの引用には、宛先ベクト
ルが設定されているセルの待ち行列が述べられている。
待ち行列は、選択された宛先に一致する待ち行列のヘッ
ドに最も近いセルについて探索される。

【００２０】この発明において、セルは、再待ち合わせ
決定モジュール７８により、副待ち行列７４から主待ち
行列７０へコピーされる。この再待ち合わせ決定モジュ
ール７８は、副待ち行列７４からのセルが選択されるべ
き仮想チャネルを決定するために、仮想チャネルテーブ
ル７６をアクセスする。一般的に言って、再待ち合わせ
決定モジュール７８は、仮想チャネルが非ブロック化に
なると、副待ち行列７４からのセルをアクセスする。例
えば、それは、伝送されたセルの仮想チャネルとして同
じ優先順位クラスの仮想チャネルの副待ち行列７４から
の他のセルで、主待ち行列７０から送られたセルを置き
換えることが出来る。

【００２１】副待ち行列７４は、コンドー他の優先順位
待ち行列を同じように実行したものではない。むしろ、
コンドー他により述べられた宛先ビットは、仮想チャネ
ル情報により置き換えられる。副待ち行列７４において
再待ち合わせ決定モジュール７８により実行された探索
は、与えられた仮想チャネルの最初のセルに関するもの
である。

【００２２】図３は、セルが主待ち行列７０から伝送さ
れるべき宛先を示す宛先選択モジュール８０も示してい
る。この示された宛先は、また、セルが副待ち行列７４
から主待ち行列７０へコピーされる次の仮想チャネルを
選択するために、再待ち合わせ決定モジュール７８によ
り使用される。

【００２３】このＡＴＭスイッチは、ウエート付けされ
た適切な待ち合わせ、初期の第一デットライン、単調な
速度、仮想クロック、および多くのほかのものから成
る、広いクラスのリアルタイム通信のアドミッション制
御とスケジューリングアルゴリズムとを支援することが
出来る。それはまた、静的適応バッファ管理から成る、
“ＡＴＭスイッチネットワークへの提案ＦＣＶＣ（流れ
制御された仮想チャネル）（The FCVC（Flow-Controlle
d Virtual Channels）Proposal for ATM Network
s）”、Ｈ．Ｔ．クング（H.T.Kung）およびＡ．チャッ
プマン（A.Chapman）著、１９９４年ＡＴＭフォーラム
へ提出されたバージョン２．１、に提案されているなど
のクレジット方式流れ制御を支援することも出来る。速
度方式流れ制御、すべての優先順位レベルのラウンドロ
ビンスケジューリング、および、多くのクラスの通信量
は、それぞれがそれ自身のスケジューリング、バッファ
リング、および流れ制御のポリシーを有しており、可能
でもある。

【００２４】クレジット方式流れ制御は、非リアルタイ
ム通信におけるセル紛失を防止するプロセスであり、特
に、この場合、広範囲に変化する帯域幅の、多くの高い
優先順位リアルタイムの通信量がある。その目的は、渋
滞によるセルの損失、つまり、すべてのスイッチにおけ
るバッファのあふれが発生せずに、すべての与えられた
時に、各ネットワークのすべての使用されていない帯域
幅を非リアルタイムの通信へ引き渡すことである。この
プロセスの基礎となる原理はシンプルである。即ち、ノ
ードは、これらのセルを受信するために下流のノードで
使用できるバッファがあることを知るまで、セルを伝送
することが出来ない。この知識は、クレジット情報の形
で下流のノードから上流のノードへ伝送される。上流の
ノードは、例えば、仮想チャネルテーブルにおいて、各
分離したスケジューリング可能な仮想チャネルについて
クレジットカウントを維持する。上流ノードは、クレジ
ットカウントを使用して、上流ノードがその仮想チャネ
ルのセルを下流のノードへ安全に伝送することが出来る
か、どうかを決定する。

【００２５】クレジットカウントが正である場合、上流
のノードは、その多くのセルを下流のセルへ伝送するこ
とが出来る。クレジットカウントがゼロの場合、上流の
ノードが下流のノードから新しいクレジットを受け取る
まで、上流のノードは、その仮想チャネルのセルをその
場所のバッファへ保持しなければならない。このよう
に、クレジットが使用できない場合、スイッチは仮想チ
ャネルのセル（つまりＶＰＣ）をそのバッファに保持
し、クレジットが使用できるようになると、これらのセ
ルをバッファから開放する。セルを保持する能力は、主
と副の待ち行列７０と７４およびＶＣテーブル７６によ
り可能になる。動作中に、入信セルは、セルが対応する
仮想チャネルを決定するために、待ち合わせ決定モジュ
ール７２により検査される。ＶＣテーブル７６内のルッ
クアップにより決定されるように、仮想チャネルが、負
のクレジットカウントによりブロック化されるならば、
セルは、副待ち行列７４に入れられる。さもなければ、
セルは、主待ち行列７０へ入れられる。クレジットカウ
ントが正になると、再待ち合わせ決定モジュール７８
は、セルを主待ち行列７０へ伝送する。

【００２６】制御器２２Ａ、および、二重待ち行列／探
索モジュール１８Ａの主と副の待ち行列７０，７４とＶ
Ｃテーブル７６を図４に関し詳細に説明する。三つの部
門、すなわち、バッファメモリ２０内のセルのセルアド
レス１００、仮想チャネル識別子（ＶＣ）９６、およ
び、優先順位またはほかのスケジューリング変数を表す
タグ９８は、制御器２２Ａにより受信される。セルアド
レスは、セルが受信され、メモリ２０に格納されると、
割り当てられる。このＶＣは、ＶＰＩ／ＶＣＩコンバー
タ９０により計算され、スイッチのヘッダーの一部とし
てセルへ付けられる。セルのタグ９８は、米国特許第
５，４４５，８２５号公報に述べられているように、テ
ーブルックアップまたはリアルタイムスケジューリング
アルゴリズムにより計算される。二重待ち行列によるこ
の制御器の最終出力は、セルバッファアドレス１０２の
シーケンスを送ることにより、セルを伝送のため、各セ
ル伝送サイクルにおいて各物理的出力リンクについて一
つをスケジューリングする。

【００２７】ＶＣテーブル７６は、各仮想チャネルにつ
いてエントリー１０４を有し、制御器２２Ａが集積回路
に収容される場合、オンチップ・データベースとして働
く。ＶＣテーブル７６へのアクセスは、好適に逐次処理
される。ＶＣテーブル７６内の領域には、宛先ベクトル
１０６があり、このチャネルのセルが伝送されなければ
ならない各出力リンクについて一つのビットを有する。
宛先ベクトル１０６は、仮想チャネルが創生されると、
定義される。多重送信チャネルは、一つ以上のビットの
宛先ベクトルが設定されたチャネルである。タグ領域１
０８は、仮想チャネルについて現行の優先順位を含んで
いる。この優先順位は、仮想チャネルについて受信され
た各セルのタグ領域９８から更新され、副待ち行列７４
からロードされた主待ち行列７０にエントリー１２２の
タグ領域１２０を設定するために使用される。

【００２８】数値的領域“ＲＣＶ”１１０は、この仮想
待ち行列について最新に受信されたセルの一連番号を表
す。この領域は、仮想待ち行列が最初に創生され、セル
が受信されるごとに増分される場合、ゼロへ初期化され
る。数値的領域“ＸＭＩＴ”１１２は、この仮想チャネ
ルに最新に伝送されたセルの一連番号を表す。この領域
は、仮想チャネルが最初に創生され、セルが伝送され
て、主待ち行列７０から除かれるごとに、ゼロへ初期化
される。多重送信仮想チャネルの場合、領域１１２は、
セルがすべての分岐へ伝送されてしまうと、増分される
だけである。数値的領域“ＬＩＭＩＴ”１１４は、流れ
制御アルゴリズムにより伝送のために許可された最高位
のセル一連番号である。例えば、この領域は、クレジッ
ト方式流れ制御の考察に関連して以降に詳細に説明され
ているように、クレジットセルが下流のノードから受信
されると、更新される。ＶＣテーブル７６の三つの数値
的領域１１０，１１２，および１１４は、それらの領域
がセルアドレスにあるほどの多くのビットを有するとす
るならば、重なっている一定幅の２進値であってもよ
い。従って、すべてのカウンターが回り込んでいるなら
ば、その値が、ｎだけ異なる値で混乱すると言う危険は
ない。ここで、ｎはシステム内のセルの全部の数であ
る。従って、すべての比較が、品質について厳密に行わ
れる。

【００２９】“Ｐフラッグ ”１１６は、副待ち行列７
４がエントリーに対応する仮想チャネルについて使用さ
れるか、されないかを示すために使用される。この場合
の制限は、設定されたＰフラッグを有する仮想待ち行列
が、流れ制御されず、ラウンドロビンスケジューリング
で予測されないことである。動的優先順位は、Ｐフラッ
グが設定されているチャネルにおいてのみ可能である。
設定されている場合、例えば、１の値を有する場合、こ
の仮想待ち行列のすべてのセルは、受信されると直ち
に、主待ち行列７０に直接に待ち合わせられなければな
らない。従って、この領域は、待ち合わせ決定モジュー
ル７２により検査される。設定されていない場合、例え
ば、ゼロの値を有する場合、せいぜい、この仮想待ち行
列の一つのセルは、すべての与えられた時に、主待ち行
列７０に入れられる。正規の動作状態において、多重送
信チャネルは、一組のＰフラッグを有していなければな
らない。これは、多重送信チャネルの各セルが、主待ち
行列７０に個々に入れられ、従って、独立して、その分
岐のそれぞれに伝送される。もし多重送信チャネルが設
定されていないＰフラッグを有するならば、先行のセル
がすべての分岐へ伝送される前に、セルは、すべての分
岐へ伝送されない。

【００３０】“Ｆフラッグ”１１７は、仮想チャネルが
流れ制御、例えば、クレジット方式の流れ制御を受けて
いるか、いないかを示すために使用される単一のビット
領域である。設定される場合、例えば、１の値を有する
場合、対応する仮想チャネルは、流れ制御を受けず、従
って、制限領域は使用されない。ゼロの値は、“ＸＭＩ
Ｔ”１１２の値が“ＬＩＭＩＴ”１１４の値に等しくな
っているときはいつでも、仮想チャネルがブロック化さ
れており、制限値が更新されるまでブロック化されたま
まであることを意味している。

【００３１】主待ち行列７０は、米国特許第５，４４
５，８２５号公報に述べられた種類のタグ方式の探索可
能なＦＩＦＯである。主待ち行列７０の各エントリー１
１８は、伝送されるのにそのまま適格であるセルを表
す。個々の仮想チャネルに関し、その現在バッファリン
グされているセルのゼロ、１、または、すべては、“Ｐ
フラッグ”領域１１６の値に従って、主待ち行列７０の
エントリー１１８により表される。

【００３２】主待ち行列７０のエントリー１１８は、四
つの領域を有する。宛先ベクトル１２２は、ＶＣテーブ
ル７６の宛先領域から初期化されるが、対応リンクへの
伝送が完了すると、そのビットはリセットされる。数値
的タグ１２０は、エントリー１１８により表されたセル
の優先順位を表す。ＶＣ領域１２４は、このエントリー
に対応する仮想チャネルのＶＣを格納する。セルアドレ
ス領域１２６は、このエントリーの個々のセルのアドレ
スを表すか、または、それがナル値（null value）なら
ば、セルアドレスが、副待ち行列７４から得られること
を表す。

【００３３】ＶＣテーブルエントリー１０４のＰフラッ
グ領域１１６が１であるならば、その仮想チャネルのバ
ッファリングされたセルのすべては、それらのタグによ
り決定された優先順位における伝送に対し自動的に適格
であり、すべてが主待ち行列７０の個々のエントリーに
より表される。ところで、これは、リアルタイムチャネ
ル、多重送信チャネル、または、流れ制御を受けないほ
かのチャネルの場合である。しかし、Ｐフラッグがゼロ
ならば、仮想チャネルは、流れ制御、ラウンドロビンス
ケジューリング、または、その両方を受ける。主待ち行
列７０は、せいぜい一つのエントリーを有し、これはそ
の仮想チャネルのバッファ内の第一セルを表している。
先行のセルが取り出され、伝送された後にのみ、新しい
エントリーが主待ち行列７０へ加えられる。流れ制御に
よりブロック化された仮想チャネルは、主待ち行列７０
にエントリーを有していない。

【００３４】副待ち行列７４は、主待ち行列７０に明示
して収められていないバッファ内の各セルについて一つ
のエントリー１２８を有する。副待ち行列７４内の各エ
ントリー１２８は、二つの領域を有する。すなわち、Ｖ
Ｃ１３０およびそのセルアドレス１３２である。副待ち
行列７４は、探索が上述のように宛先ベクトルによるよ
りもむしろ、ＶＣの直接整合により行われることを除い
て、コンドー他の記述に似た探索可能なＦＩＦＯであ
る。

【００３５】このシステムでは、バッファメモリ２０の
各セルは、非ナル（non-null）のセルアドレスの主待ち
行列７０内のエントリーによるか、または、副待ち行列
７４内のエントリーにより表される。さらに、セルが副
待ち行列７４内のエントリーにより表されるならば、仮
想チャネルが伝送について適格であるか、ないかによ
り、ＶＣは、主待ち行列７０内のエントリーにより表さ
れるか、または、表されない。

【００３６】副待ち行列を図５及び図６に関し説明す
る。副待ち行列は、自己時間設定ＶＬＳＩ・ＦＩＦＯ回
路３１により実行される。このような待ち行列は、コン
ドー他により述べられている。待ち行列エントリーは、
ＦＩＦＯ３１の尾部（テイル）へ挿入され、ＦＩＦＯの
未使用エントリーを占有するために、待ち行列のヘッド
へ向かって前方へ自動的にシフトされる。各待ち行列エ
ントリーは、レジスター３９内にあり、仮想チャネル番
号（ＶＣ＃）領域４１とアドレス領域３５とを有する。
各ＶＣ＃領域４１は、仮想チャネルを表す２進番号を有
する。探索回路５０とバス読み取り回路４５とが図５に
も示されている。

【００３７】図５の実施例において、符号３５と３７で
示されたと同じ仮想待ち行列へ宛先指定された二つのセ
ルがある。スケジューリングアルゴリズムは、これらセ
ルの主待ち行列への伝送の順番を設定する。好適な実施
態様において、与えられたＶＣ＃の最初のセルは、伝送
される。このようにして、そのエントリー３９のＶＣ＃
領域４１の番号が、希望の仮想チャネルと同じ数値を有
するならばいつでも、エントリーが伝送されるアドレス
領域３５において識別されたアドレスのバッファメモリ
２０内のセルは、主待ち行列へ伝送される。

【００３８】動作状態において、主待ち行列へ伝送する
ためにセルを探索するように、制御器２Ａが二重待ち行
列／探索モジュール１８Ａへ命令すると、このモジュー
ル１８Ａは、希望の仮想チャネルを探索回路５０へ指定
することにより、探索する。次に、探索回路５０は、待
ち行列のヘッドに最も近く、希望の仮想チャネルに対応
する仮想チャネル番号を有する待ち行列エントリー３９
を選択する。それは、例えば、待ち行列内の選択された
エントリーを示す“１”を有する２進値により出力する
ことにより、どのエントリーが選択されたエントリーで
あるかを示すベクトル５１を出力する。バス読み取り回
路４５は、出力ベクトル５１を受信し、次に、選択され
たエントリーのセルアドレス領域３５を得るために、選
択されたエントリーをアクセスする。バス読み取り回路
４５は、このセルアドレスをその出力４９に送る。次
に、選択されたエントリーは、ＶＣ＃領域を非ＶＣ値、
例えば、１を設定することにより、待ち行列から取り出
される。

【００３９】探索回路５０を図６に関して詳細に説明す
る。この図は、四つの待ち行列エントリー３４，３６，
３８，および４０を示しており、それぞれはＶＣ＃領域
４２を有する。同等比較器４８は、待ち行列エントリー
の仮想チャネル番号を受信し、希望仮想チャネルとの同
等比較を行う。この比較は、各待ち行列エントリーの排
他的論理和によるビット平行法により、希望の仮想チャ
ネルについて行われる。排他的論理和の出力は、一緒に
否定論理和されて、各待ち行列エントリーに対しこの出
力を送る。あるいは、ビット平行の排他的論理和は、希
望の仮想チャネルの各待ち行列エントリーについて行わ
れ、この排他的論理和の出力は、一緒に論理積されて、
各待ち行列エントリーの出力へ送られる。同等比較器４
８は、一組のゼロと１の値を生成し、ゼロの値は、対応
するセルは選択に適格でないことを示し、１の値は、対
応するセルが選択に適格であることを示す。

【００４０】同等比較器４８の出力は、各エントリーの
ビットをすぐ隣のエントリーのビットと比較する比較回
路５８へ送られた一組のビットである。これは、示され
ているように、論理和ゲート５２と排他的論理和ゲート
５４により行われる。この結果は、出力ビット５６の多
くて一つは値１を有し、対応するエントリーは伝送のた
めに選択されていることを示す。

【００４１】お分かりのように、加速器６０は、探索を
加速するために使用され、従って、１セルサイクル内で
順次選択される。加速器６０は、上部ステージへ接続さ
れたその出力６４と共に下部ステージからの入力６２を
有する従来の先取り回路である。

【００４２】このシステムの動作を説明する。各到着す
るセルに関し、制御器２２Ａは、セル・バッファ・アド
レスと、ＶＣと優先順位タグとを有するスイッチ・ヘッ
ダーとを受信する。セルが到着すると、ＶＣテーブル７
６はＶＣにより索引され、対応するエントリー１０４が
取り出される。宛先ビットがこのエントリーに設定され
ていなければ、セルは直ちに廃棄され、そのセルアドレ
スは、バッファメモリに使用される開放されたセルプー
ルへ戻される。セルがほかのスイッチモジュールの物理
的リンクへ宛先指定されると、宛先ビットは設定されな
い。あるいは、次に行われることは、ＶＣテーブルのほ
かの領域の値に依存する。“ＲＣＶ”領域１１０は増分
され、新しいタグ値９８は、ＶＣテーブル７６の領域１
０８へコピーされる。“Ｐフラッグ”領域１１６が設定
されているならば、宛先ベクトル、タグ、ＶＣ、および
セルアドレスから成るエントリー１１８は、主待ち行列
へ加えられる。エントリーは、副待ち行列へは加えられ
ない。“Ｐフラッグ”領域１１６が設定されていなけれ
ば、セル・バッファ・アドレスとＶＣとから成るエント
リー１２８が、その代わりに、副待ち行列７４の尾部へ
加えられる。

【００４３】さらに、“Ｐフラッグ”領域１１６が設定
されていなければ、ＶＣテーブル７６の“ＸＭＩＴ”領
域１１２は、“ＲＣＶ”領域１１０と“ＬＩＭＩＴ”領
域１１４の両方の古い値と比較される。“ＸＭＩＴ”が
古い“ＲＣＶ”と等しく、かつ、“Ｆフラッグ”（領域
１１７）＝１、または“ＸＭＩＴ”が“ＬＩＭＩＴ”と
等しくなければ、エントリー１１８は、宛先ベクトル、
タグ、ＶＣ、およびナルのセルアドレスから成る主待ち
行列７０へ加えられる。このルールにより、各到着する
セルは、主待ち行列７０または副待ち行列７４へ加えら
れる。セルが副待ち行列７４へ加えられる場合、仮想チ
ャネルのエントリーがすでに主待ち行列７０にないなら
ば、エントリーも主待ち行列７０へ加えられる。この状
態は、“ＲＣＶ”カウンターと“ＸＭＩＴ”カウンター
が等しく、仮想チャネルが流れ制御によりブロック化さ
れない場合に発生する；すなわち、その“ＸＭＩＴ”カ
ウンターは“ＬＩＭＩＴ”値に等しくない、つまり、チ
ャネルは流れ制御されない。

【００４４】出力スケジューリングは、シーケンサー
（示されていない）により駆動され、各セルサイクルご
とに１回各物理的宛先へ進む。各宛先については、その
後の進行が行われる。最初に、主待ち行列が、整合宛先
ビットと最小タグによりエントリー１１８について探索
される。なにも見つからないならば、アイドルセルが伝
送のために戻される。さもなければ、エントリー１１８
が選択されるならば、ＶＣがエントリーから検索され、
選択されたエントリーの宛先がリセットされる。次に、
選択されたエントリー１１８のセルアドレス領域が検査
される。セルアドレスがナルでないならば、そのセルア
ドレスは、セルを送るためにメモリ２０をアクセスする
出力回線へ向かう。あるいは、セルアドレスがナルなら
ば、対応するＶＣの副待ち行列７４内の最初のエントリ
ー１２８のセルアドレス１３２は、伝送のために出力回
線により出力される。このようにして、セルアドレスの
ナル値は、セルアドレス１０２を副待ち行列７４から出
力するために、多重化器（ＭＵＸ）１４０を切り換え
る。

【００４５】セルの伝送の後、全宛先ベクトルがゼロで
あるならば、“ＸＭＩＴ”カウンターが増分される。さ
らに、主待ち行列のエントリーからのセルアドレスがナ
ルであったならば、副待ち行列の選択されたエントリー
が、取り除かれる。最後に、ＶＣテーブルの“ＸＭＩ
Ｔ”領域の新しい値が、“ＲＣＶ”領域と“ＬＩＭＩ
Ｔ”領域の両方の値と比較器１３６により比較される。
新しい“ＸＭＩＴ”値が“ＲＣＶ”値と等しくなく、か
つ、“Ｆフラッグ”が１へ設定されるか、または、“Ｘ
ＭＩＴ”値が“ＬＩＭＩＴ”と等しいならば、新しいエ
ントリーが、ＶＣテーブルの宛先ベクトルとタグ、およ
びＶＣ、ナルのセルアドレスから成る主待ち行列へ加え
られる。従って、その仮想チャネルへ送る多くのセルが
あるならば、即ち、“ＸＭＩＴ”カウンターが“ＲＣ
Ｖ”カウンターを取り上げておらず、かつ、チャネルが
流れ制御によりブロック化されないならば、即ち、“Ｘ
ＭＩＴ”カウンターが“ＬＩＭＩＴ”カウンターを取り
上げていない場合にのみ、ＶＣのエントリーは、主待ち
行列へ戻り加えられる。

【００４６】すべての主待ち行列のエントリーの宛先ベ
クトルが、ゼロになると、主待ち行列のＦＩＦＯの自己
時間設定された回路は、そのエントリーを絞り出し、そ
れを待ち行列の後ろからエントリーで充填する。待ち行
列のその後のエントリーも、前へ移動し、空きのスロッ
トを満たす。同じことが、エントリーが削除される場合
の副待ち行列に当てはまる。

【００４７】この実施態様において、二つの動作が、流
れ制御を管理するために行われる。新しいクレジットを
含んでいるクレジット更新セルが、下流のノードから受
信されると、新しい“ＬＩＭＩＴ”値が計算されて、Ｖ
Ｃテーブルへ挿入される。その上、ＶＣテーブル７６の
“ＸＭＩＴ”領域が、“ＲＣＶ”領域の値と“ＬＩＭＩ
Ｔ”領域の値の両方と比較される。“ＸＭＩＴ”値が
“ＲＣＶ”値と等しくなく、かつ、“Ｆフラッグ”が１
に設定されるか、または、“ＸＭＩＴ”値が古い“ＬＩ
ＭＩＴ”値に等しいならば、新しいエントリーが、ＶＣ
テーブルからの宛先ベクトル及びタグと、ＶＣとナルの
セルアドレスとから成る主待ち行列へ加えられる。この
動作は１セルサイクルかかり、従って新しい“ＬＩＭＩ
Ｔ”値を含み、かつ特殊な処理を有するスイッチヘッダ
ーの特殊なフォーマットにより、行わなければならな
い。このようなセルが受信されると、“ＬＩＭＩＴ”値
は更新され、セルバッファアドレスが、アイドルセルプ
ールへ直ちに戻される。この動作は、待ち合わせ決定モ
ジュールを使用することにより行われる。

【００４８】クレジット方式流れ制御はまた、スイッチ
がそれ自身の一連番号を上流のノード番号と再同期化す
ることを可能にするセル一連番号の新しい値を有する、
上流ノードから受信されたクレジット点検セルも使用す
る。これは、失われたデータセルの状態から流れ制御の
状態を回復する手段である。制御器２２Ａが、“ＲＣ
Ｖ”カウンターのそれ自身の値がクレジット点検セルに
含まれた一連番号より小さいことを発見すると、制御器
２２Ａは、“ＲＣＶ”カウンターをその差だけ増分す
る。また、制御器２２Ａにより、“ＲＣＶ”と“ＸＭＩ
Ｔ”は、これらの同じ差だけ増分するが、“ＬＩＭＩ
Ｔ”の値よりも大きくない。このクレジット点検は、ク
レジット更新セルに似た、スイッチヘッダーの特殊なフ
ォーマットを有するセルにより実行される。

【００４９】流れ制御された仮想チャネルの最大クレジ
ットバランスは、ある大きい値であるが、スイッチに知
られたクレジットバランスは、“ＬＩＭＩＴ”値と“Ｘ
ＭＩＴ”値との差、モジュローｎ（modulo n）である。

【００５０】スイッチの高レベル制御は、大きい値を管
理し、それらを小さい単位で制御器へ引き渡す責任があ
る。

【００５１】“最早期デットラインを最初に／仮想クロ
ック（Earliest Deadline First and Virtual Cloc
k）”などのスケジューリングアルゴリズムによる場
合、一つの潜在的問題が起こる。これらのスケジューリ
ングアルゴリズムの場合、タグ値は、各仮想チャネルに
ついて単調に増加する。最後に、それらは、タグ領域の
大きさからオーバーフローする。このオーバーフローを
処理する一つの方法は、制御状態を主待ち行列へ加え
て、これにより、大きなタグ値（１にセットされた高順
位ビットを有する）が、非常に小さいタグ値より小さく
（ゼロの高順位ビットを有する）現れるようにすること
である。この制御状態は、タグが高順位ビットをオーバ
ーフローし始めると、加えられ、１の高順位ビットを有
するすべてのタグが最後に処理されてしまうと、リセッ
トされる。

【００５２】このアーキテクチャの一つの利点は、同じ
優先順位のすべての仮想チャネルのクレジット方式流れ
制御、リアルタイム伝送、およびランウドロビン・スケ
ジューリングが可能になることである。ランウドロビン
・スケジューリングは、同じ優先順位のすべての仮想チ
ャネルについて、例えば、Ｆフラッグをゼロ値へセット
しないことにより可能である。仮想チャネルが主待ち行
列から選択されるごとに、その最初のセルが伝送され、
次に、次のセルのエントリーが待ち行列の終わりに配置
される。主待ち行列はタグにより分類されるので、最後
に、それは、適切な優先順位レベルに到達するが、同一
タグ値を有するほかの仮想チャネルの後ろに残る。定義
により、同一優先順位を有する仮想チャネルからのセル
は、順位が仮想チャネル内で保存されている限り、すべ
ての順番で伝送される。ＦＩＦＯの順番が好適である場
合、これは、Ｐフラッグを１に設定することにより確実
に行われる。

【００５３】この設計において、多重送信チャネルの流
れ制御は難しい。多重送信チャネルのこのような流れ制
御は、各分岐を独立して制御することにより行うことが
出来る。実際に行うために、これは、各分岐を、それ自
身の“ＲＣＶ”、“ＸＭＩＴ”、および“ＬＩＭＩＴ”
の各値を有する個々の仮想チャネルにしている。また、
スイッチは、これら新しい仮想チャネルの源ノードでも
ある。しかし、“ＲＣＶ”値のすべてを即時に更新する
ことは困難である。

【００５４】本発明の幾つかの実施態様を説明したが、
前述の内容は、単に例証しており、限定するものでな
く、実施例によってのみ呈示されていることは、本技術
に精通した当事者には明らかである。多くの変形とほか
の実施態様は、この分野における普通の技術範囲内にあ
り、添付請求の範囲により定義されているように、本発
明の範囲内にあると判断される。

【００５５】すなわち、この発明の実施の形態１は、二
つの待ち行列を使用して、ブロック化および非ブロック
化されたチャネルの流れを制御する。一つの実施態様に
おいて、システムはタグ方式の主待ち行列を有し、これ
は、例えば、ブロック化されたチャネルにより、伝送の
ためにまだスケジューリングされていないＡＴＭセルを
有する優先順位と副待ち行列とにより編成されたＡＴＭ
セルを有し、仮想チャネルにより編成される。待ち合わ
せ決定モジュールは、入信するＡＴＭセルがどの待ち行
列に配置されるべきかを決定するために設けられてい
る。再待ち合わせ決定モジュールは、特定の仮想チャネ
ルを非ブロック化する事象が発生するときに、作動す
る。このような事象の発生時に、再待ち合わせ決定モジ
ュールは、副待ち行列をアクセスして、ほかのセルを
得、それに優先順位を割り当て、それを主待ち行列へ移
動する。待ち合わせ決定モジュールは、必要ならば、仮
想チャネルテーブルと共に、仮想チャネルを容易にブロ
ック化するために使用される。待ち行列の組み合わせ
は、また、ラウンドロビン・スケジューリングを可能に
する。

【００５６】

【発明の効果】この発明に係るＡＴＭスイッチは、以上
説明したとおり、非同期伝送モードネットワークにおい
て使用されるＡＴＭスイッチであって、出力回線への伝
送の前にセルを格納し、セルがタグ方式優先順位探索に
基づき伝送のために選択される主待ち行列と、ブロック
化されたチャネルのセルを格納し、そのチャネルがブロ
ック化されないときには、セルが前記主待ち行列への伝
送のために選択される副待ち行列と、セルを入力回線か
ら受信し、セルのチャネルがブロック化されるか否かに
より、セルを前記主待ち行列と前記副待ち行列のいずれ
か一つへ向かわせる待ち合わせ決定モジュールとを備え
たので、二つの待ち行列を使用して、ブロック化及び非
ブロック化されたチャネルの流れを制御することができ
るという効果を奏する。

【００５７】また、この発明に係るＡＴＭスイッチは、
以上説明したとおり、さらに、前記主待ち行列から伝送
されたセルのチャネルの表示を受信する入力を有し、伝
送されたセルの同一優先順位クラスのブロック化されな
いチャネルのセルを前記主待ち行列へ伝送するように前
記副待ち行列を制御する再待ち合わせ決定モジュールを
備えたので、二つの待ち行列を使用して、ブロック化及
び非ブロック化されたチャネルの流れを制御することが
できるという効果を奏する。

【図面の簡単な説明】

【図１】従来のＡＴＭスイッチの論理アーキテクチャ
の構成に係る制御器の制御を受けた待ち行列／探索モジ
ュールを示す図である。

【図２】この発明の実施の形態１に係るＡＴＭスイッ
チの構成を示す図である。

【図３】この発明の実施の形態１に係るＡＴＭスイッ
チの二重待ち行列／探索モジュールの構成を示す図であ
る。

【図４】図３の二重待ち行列／探索モジュールの詳細
構成を示す図である。

【図５】この発明の実施の形態１に係る、副待ち行
列、待ち行列内の各セルを表すＦＩＦＯのレジスター、
個々の仮想チャネルと整合するセルから待ち行列から選
択する探索回路、および情報を待ち行列から読み取るバ
ス読み取り回路の構成を示す図である。

【図６】図５の探索回路への四つの待ち行列エントリ
ーを示す図である。

【符号の説明】

１０ＡＡＴＭスイッチ、１８Ａ二重待ち行列／探索
モジュール、２０メモリ、２２Ａ制御器、７０主
待ち行列、７２待ち合わせ決定モジュール、７４副
待ち行列、７６仮想チャネル（ＶＣ）テーブル、７８
再待ち合わせ決定モジュール、８０宛先選択モジュ
ール。

───────────────────────────────────────────────────── フロントページの続き (71)出願人 595151497 201 ＢＲＯＡＤＷＡＹ，ＣＡＭＢＲＩＤＧＥ，ＭＡＳＳＡＣＨＵＳＥＴＴＳ 02139，Ｕ．Ｓ．Ａ. (72)発明者アビジット・ゴーシュアメリカ合衆国、カリフォルニア州、バークレイ、スレイター・レーン 42 (72)発明者ジョン・エイチ・ハワードアメリカ合衆国、マサチューセッツ州、ケンブリッジ、コグスウェル・アベニュー８ (72)発明者近藤晴房東京都千代田区丸の内二丁目２番３号三菱電機株式会社内 (72)発明者ランディ・ビー・オズボーンアメリカ合衆国、マサチューセッツ州、ニュートン、ウェセックス・ロード 33 (72)発明者チア・シェンアメリカ合衆国、マサチューセッツ州、ウォータータウン、ダートマウス・ストリート 42 (72)発明者チン・ジェンアメリカ合衆国、マサチューセッツ州、ボックスボロ、ミドル・ロード 70

Claims

【特許請求の範囲】

【請求項１】非同期伝送モードネットワークにおいて
使用されるＡＴＭスイッチであって、出力回線への伝送の前にセルを格納し、セルがタグ方式
優先順位探索に基づき伝送のために選択される主待ち行
列と、ブロック化されたチャネルのセルを格納し、そのチャネ
ルがブロック化されないときには、セルが前記主待ち行
列への伝送のために選択される副待ち行列と、セルを入力回線から受信し、セルのチャネルがブロック
化されるか否かにより、セルを前記主待ち行列と前記副
待ち行列のいずれか一つへ向かわせる待ち合わせ決定モ
ジュールとを備えたことを特徴とするＡＴＭスイッチ。
【請求項２】さらに、前記主待ち行列から伝送されたセルのチャネルの表示を
受信する入力を有し、伝送されたセルの同一優先順位ク
ラスのブロック化されないチャネルのセルを前記主待ち
行列へ伝送するように前記副待ち行列を制御する再待ち
合わせ決定モジュールを備えたことを特徴とする請求項
１記載のＡＴＭスイッチ。