(57)【特許請求の範囲】
【請求項１】
多段交換ネットワークの複数の入力ポートのうちの１つにおいて受信される入力セルをネットワークの複数の出力ポートのうちの１つ以上ヘマルチキャストする装置であって、多段交換ネットワークの第２段（１１３２）の入力ポートは多段交換ネットワークの第１段（１１３１）の出力ポートに接続されており、多段交換ネットワークの各段は１つ以上の交換機を含み、該装置は、多段交換ネットワークの少なくとも１つの段の少なくとも１つの交換機を備えており、
（ａ）データ・ペイロード（５２０）と、データ・ペイロードが出力されるべき、多段交換ネットワークの１つ以上の出力ポートを識別するビットマップ・セグメント（１３０１）とを含む入力セルを受信する手段（１１１０）と、
（ｂ）利用可能なセル・バッファ（１０２０）にデータ・ペイロードを格納する手段と、
（ｃ）複数のリンク・リスト出力キュー（１００１）と、を含む装置において、
（ｃ１）該複数のリンク・リスト出力キュー（１００１）は、セル・バッファアドレスエントリを格納するための、多段交換ネットワーク出力ポートの各々に対して少なくとも１つを含んでおり、
（ｄ）入力セルが送信されるべき多段交換ネットワークのポートまたは関連する１つ以上の次段の交換機の数と等しい数を格納するための、各セル・バッファに関連する参照カウンタ（１０５５）と、
（ｅ）多段交換ネットワークの出力ポートとデータ・ペイロードが運ばれるべき任意の１つ以上の次の段の交換機とを交換する段を識別するためにビットマップ・セグメントを翻訳しかつそれらの次の段の交換機に関連した１つ以上のリンク・リストの出力キューヘのエントリを作成する手段（３０７、マシーン９）とを含み、正確に１つがその入力エントリが送信されるべき次の段の各交換機ごとにあり、
（ｆ）対応するリンク・リスト出力キューにおけるエントリによって決定されたシーケンスにしたがって、データ・ペイロードの１コピーを識別された１つ以上の、次の段交換機または多段交換ネットワークの出力ポートの各々へ送信する手段（３０７、マシーン１０）と、
（ｇ）ペイロードは識別された１つ以上の次の段の交換機または多段交換ネットワークの各出力ポートヘ送信されるとき、リンク・リスト出力キューそれぞれにおいてそこからエントリを削除し、参照カウンタを１つだけ減少し、そして参照カウンタがゼロとなったとき、セル・バッファを利用可能とする手投（３０７、マシーン５）とを含むことを特徴とする装置。
【請求項２】
セル・バッファおよびリンク・リスト出力キューは、同じメモリ内に位置していることを特徴とする請求項１記載の装置。
【請求項３】
多段交換ネットワークの出力ポートそれぞれのリンク・リスト出力キューは、同じメモリ内に位置していることを特徴とする請求項１記載の装置。
【請求項４】
各多数多段ネットワーク出力ポートごとに別々のメモリが提供されており、リンク・リスト出力キューヘのエントリは並行して行われることを特徴とする請求項１記載の装置。
【請求項５】
ビットマップ・セグメントは別々のキューヘ置かれ、エントリは入力セル受信速度と等しいもしくはよりも速い速度で行われることを特徴とする請求項１記載の装置。
【請求項６】
リンク・リスト出力キューヘのエントリは、１以上の次段の交換機の数で乗じた入力セル受信速度と等しい速度で生じることを特徴とする請求項１記載の装置。
【請求項７】
少なくとも１つの出力ポートは複数の単一リンク・リスト出力キューを含み、前記少なくとも１つの多段交換ネットワークの出力ポートについての単一リンク・リスト出力キューそれぞれの処理は単独していることを特徴とする請求項１記載の装置。
【請求項８】
前記処理は、入力セルに含まれたヘッダ・データによって決定される優先順位に基づくことを特徴とする請求項１記載の装置。
【請求項９】
受信されたユニキャスト入力セルについての別個のリンク・リスト出力キューと、受信されたマルチキャスト入力セルについての別個のリンク・リスト出力キューとをさらに含むことを特徴とする請求項１記載の装置。
【請求項１０】
２つ以上のリンク・リスト出力キューが多段交換ネットワークの出力ポート用に用いられ，次のセルが処理されるべき２つ以上のリンク・リスト出力キューを示す１つ以上の追加ビットを有する単一リンク・リスト出力キューとして２つ以上のリンク・リスト出力キューが実装されることを特徴とする請求項１記載の装置。
【請求項１１】
多段交換ネットワークの複数の入力ポートのうちの１つにおいて受信される入力セルを複数の出力ポートのうちの１つ以上へマルチキャストする方法であって、多段交換ネットワークの第２段（１１３２）の入力ポートは多段交換ネットワークの第１段（１１３１）の出力ポートに接続されており、
（ａ）データ・ペイロード（５２０）と、データ・ペイロードが出力されるべき１つ以上の、多段交換ネットワークの１つ以上の出力ポートを識別するビットマップ・セグメント（１３０１）とを含む入力セルを受信する（１１１０）工程と、
（ｂ）利用可能なセル・バッファ（１０２０）にデータ・ペイロードを格納する工程と、
（ｃ）複数のリンク・リスト出力キュー（１００１）を確立する工程とからなる、複数の出力ポートのうちの１つ以上の多段交換ネットワークの出力ポートの１つ以上へ複数の入力ポートのうちの１つで受信された入力セルをマルチキャストする方法において、
（ｃ１）  複数のルーティングキューのうちの少なくとも１つのキューを多段交換ネットワークの各々の出力ポート（１１５０）ごとに識別する工程と、
（ｄ）  該入力セルが送られるべき多段交換ネットワークポートまたは関連する１つ以上の次段の交換機の数に等しい数を格納するための参照カウンタを各セル・バッファに関連させる工程と、
（ｅ）  データ・ペイロードが運ばれるべき多段ネットワークの出力ポートを識別するためにビットマップ・セグメントを翻訳する（３０７、マシーン９）工程と、
（ｆ）  それらの次段の交換機に関連したリンク・リスト出力キューヘ、該入力セルが送られるべき次段の多段交換機ごとに正確に１つのエントリを作成する（３０７、マシーン９）工程と、
（ｇ）  対応するリンク・リスト出力キューにおけるエントリによって決定されたシーケンスに従って、データ・ペイロードの１コピーを識別された１つ以上の次段の交換機または多段交換ネットワークの出力ポートの各々へ伝送する（３０７、マシーン１０）工程と、
（ｈ）ペイロードが識別された、１つ以上の次段の交換機または多段交換ネットワークの出力ポートに出力されるとき、リンク・リスト出力キューの各々において、そこからエントリを削除して（３０７、マシーン５）、参照カウンタを減少する工程と、
（ｉ）参照カウンタがゼロとなったとき、セル・バッファを利用可能とする（３０７、マシーン５）工程とからなることを特徴とする方法。
【請求項１２】
セル・バッファおよびリンク・リスト出力キューは、同じメモリ内に位置することを特徴とする請求項１１記載の装置。
【請求項１３】
多段交換ネットワークの出力ポートそれぞれのリンク・リスト出力キューは、同じメモリ内に位置していることを特徴とする請求項１１記載の装置。
【請求項１４】
多段交換ネットワークの各出力ポートごとに別々のメモリが提供されており、リンク・リスト出力キューヘのエントリは並行して行われることを特徴とする請求項１１記載の装置。
【請求項１５】
ビットマップ・セグメントは別々のキューヘ置かれ、エントリは入力セル受信速度と等しいもしくはよりも速い速度で行われることを特徴とする請求項１１記載の装置。
【請求項１６】
リンク・リスト出力キューヘのエントリは、出力ポートの数で乗じた入力セル受信速度と等しい速度で生じることを特徴とする請求項１１記載の装置。
【請求項１７】
少なくとも１つの出力ポートは複数のリンク・リスト出力キューを含み、前記少なくとも１つの出力ポートについての単一リンク・リスト出力キューそれぞれの処理は独立していることを特徴とする請求項１１記載の装置。
【請求項１８】
前記処理は、入力セルに含まれたヘッダ・データによって決定される優先順位に基づくことを特徴とする請求項１７記載の装置。
【請求項１９】
受信されたマルチキャスト入力セルについての別個のリンク・リスト出力キューと、受信されたユニキャスト入力セルについての別個のリンク・リスト出力キューとをさらに含むことを特徴とする請求項１１記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、自己ルーティング多段式ネットワークにおいてマルチキャスト・ルーティングを可能にする方法および装置に関し、特に、改良されたミニマムツリー・マルチキャスト・ルーティングを提供する方法および装置に関する。
【０００２】
【従来の技術】
非同期転送モード（ＡＴＭ）交換網には、ひとつの入力ポートからひとつ（ユニキャストと呼ぶ）、または複数の（マルチキャストと呼ぶ）出力ポートにセル転送を供給する目的がある。マルチキャスト接続を処理する能力は、どのＡＴＭ交換機の構成でも必須要件である。いくつかのＡＴＭ交換機ではミニマムツリー・マルチキャスティングを使用しているが、そこでは、マルチキャスト・セルは交換機内で可能な限り下流にまで（交換機内の最下流まで）複製される。すなわち、ある入力ポートに受信されたマルチキャスト・セルの単一のコピーは、各トリー（分岐）の頂点で、そこにつながる他の異なる頂点または出力の数だけ、複製される。ミニマムツリー・マルチキャスティングは、平均のキューイング遅延と交換機が必要とするバッファサイズを最小化する。
【０００３】
【発明が解決しようとする課題】
このようなミニマムツリー・マルチキャスティング能力を有するＡＴＭ交換機における継続的課題は、ひとつの出力ポートでの遅延が他の出力ポートに行くトラヒックに影響を及ぼす際に起きる輻輳を避けることである。
【０００４】
【課題を解決するための手段】
本発明は、交換ネットワークの複数の入力ポートのひとつで受信された入力セルを複数の出力ポートのうちのひとつ以上にマルチキャストする装置および方法に関するものである。データ・ペイロードと、データ・ペイロードが出力されるべきひとつ以上の出力ポートを識別するビットマップ・セグメントとを含む入力セルが受信される。データ・ペイロードは、利用可能なセル・バッファに格納され、各セル・バッファは、入力セルが出力されるべきポートの数と等しい数を格納するための参照カウンタと関連付けされる。ビットマップ・セグメントは、データ・ペイロードが運ばれるべき出力ポートを識別するため用いられ、出力ポートごとに少なくともひとつの複数のリンク・リスト出力キューが設けられる。ビットマップ・セグメントは、データ・ペイロードが運ばれるべき出力ポートを識別するために訳され、関連するリンク・リスト出力キューへエントリが作成される。データペイロードの１コピーは、対応するリンク・リスト出力キューにおけるエントリによって決定されたシーケンスにしたがって、識別された出力ポートそれぞれに伝送される。単一リンク・リスト・キューそれぞれにおいて、エントリは、データ・ペイロードが識別された出力ポートへ出力される際にそこから削除され、参照カウンタは１ずつ減らされる。参照カウンタがゼロと等しくなった場合、セル・バッファは別の受信された入力セルへ利用可能とされる。
【０００５】
関連する主題は、同時に同一の譲受人により出願された同時係属出願：米国特許出願第０８／５８４、９３５号（Ｃｈｉｕｓｓｉ  ２−１２−５）（米国特許第５，６８９，５０６号）発明の名称「多段式ネットワークにおける改良されたマルチキャスト・ルーティング」および米国特許出願第０８／５８４，９３６号（Ｃｈｉｕｓｓｉ  ３−１３−６）（米国特許第５，６８９，５００号）発明の名称「マルチキャスト・ルーティング輻輳フィードバックを有する多段式ネットワーク」に開示されている。
【０００６】
【発明の実施の形態】
全般説明
以下の説明では、各図のアイテムやブロックにはそれぞれ、関連する符号が付けられており、最初の番号がそのアイテムが最初に出てくる図を参照する（例えば、１１０は図１にある）。
【０００７】
図１を参照すると、ここでは、現在の交換機ノードの操作の概略を示す。本発明は、非同期転送モード（ＡＴＭ）または同様の交換機におけるマルチキャスティング技術を提供する。
【０００８】
図１は、３段式交換ノードまたはシステムにおける本発明の典型的なインプリメンテーションを図示している。このシステムでは、入力ポート・ユニット１１０の多数の入力ポートカードは、それぞれ単一の内部リンク１２０により中央相互接続交換ユニット（ここでは交換機構とも称する）１３０に接続し、そしてこの交換機構１３０は、単一の内部リンク１４０により出力ポート・ユニット１５０の多数の出力ポート・カードそれぞれに接続している。入力ポート・ユニット１１０は、具体的に６つのポート・カード（０〜５）を含み、出力ポート１５０は、６つの出力ポート・カード（０〜５）を含んでいる。一実施例では、入力ポート０と出力ポート０は、同一のポートカード０を共有する。６つのポート・カードは図に示すとおり、それぞれが３２の入力と３２の出力への相互接続を供給している。ポート・カードは、それぞれ、ＡＴＭ階層マネージャ（ＡＬＭ）およびＡＴＭバッファ・マネージャ（ＡＢＭ）集積回路を含んでいる。一実施例では、ルックアップ（ＬＵＴ１、ＬＵＴ２）、翻訳（ＴＲ）、ポリシング（ＰＯＬ）、およびヘッダ翻訳（ＨＴ）テーブルは、入力カウンタ９０３および出力カウンタ９０４（これらは全て後述する）と同様に単一のＡＬＭメモリ・ユニットの一部である。外部の入力１００および出力１６０から入力および出力ポート・ユニットへのリンクは、先頭から最後まで、１００の位が入力（出力）ポートを識別し、下二桁がその入力（出力）ポート・ユニットのサブポートを識別するように番号付けされている。例えば、入力サブポート１，０２は、入力ポート・ユニット１のサブポート２である。
【０００９】
図２を参照して、図２には、数個（一般的には３０）の入力サブポート回路（２１０）および出力サブポート回路（２１２）と、これらのサブポート回路を共通接続回路（２１１および２１３）によって、交換機構にまたは交換機構から（図１あるいは図１１）相互接続している複数の制御ロジックおよびＲＡＭメモリ・ブロック（２０１〜２０８）とを含むポート・カード具体例のブロック図が示されている。現在のインプリメンテーションにおける制御ロジックブロックは、関連するＲＡＭメモリ（２０４）を伴うＡＴＭ階層マネージャ（ＡＬＭ）（２０１および２０６）と、関連するＲＡＭメモリ（２０５）を伴うＡＴＭバッファ・マネージャ（ＡＢＭ）（２０２、２０３、２０７および２０８）との２つの集積回路で構成されている。入力と出力のサブポートは通常、サービスのため物理層転送インタフェース装置（図示せず）に接続される。システム構成の目的と管理上の目的、そして呼の組み立てのために、ＡＬＭとＡＢＭは両方ともマイクロプロセッサ・インタフェース（図示せず）が備えられている。ＡＬＭは、仮想接続の入力ポリシングと、交換機構のための経路ルックアップと、出力仮想回線アドレス変換と、パフォーマンス統計と、下記および付録の状態マシーン１および１１の説明により詳しく記述するその他の機能とを供給する。ＡＢＭは、入力および出力バッファリングと、出力マルチキャスト・ルーティングおよび出力サブポートへのレート制御と、輻輳制御およびフロー制御と、追加のパフォーマンス統計と、下記および付録の状態マシーン２、３、９および１０の説明により詳しく記述するその他の機能とを供給する。
【００１０】
図３を参照して、図３には、６つの入力ポートＩＰ０〜ＩＰ５と６つの出力ポートＯＰ０〜ＯＰ５とを相互接続するための交換モジュールＡＳＸのブロック図が示されている。交換モジュールＡＳＸは、図１の交換機構１３０を有する。ＡＳＸモジュールは、どの入力ポートも１つ以上の出力ポートへ経路付けをおこなう６×６ポート共有メモリ交換装置である。これは、出力キューイング、マルチキャスティング、一段および多段構成をサポートし、さらに非ブロック化ロスレス交換ノード操作を可能にする。これは、マイクロプロセッサ・インタフェース３０１を介して配列される。交換モジュールＡＳＸは、セル・バッファに接続する６つの入力ポート回路（３０２）および６つの出力ポート回路（３０３）を含んでいる。セル・バッファ・ユニット３０４は、経路付けアービトレーション回路３０５と、構成可能リンク・リスト３０６と、キュー処理装置３０７と、バックプレッシャ処理装置３０８と、マイクロプロセッサ・インタフェース３０１とに接続している。経路付けアービトレーション回路３０５とバックプレッシャ処理装置３０８は、入力および出力ポートに相互接続している。図１に示されるＡＳＸ回路の６つの出力キューＯＰ０〜ＯＰ５は、セルバッファ３０４およびリンク・リスト３０６の中にあり、ポート・カードのＡＢＭ回路と同様に動作する。
【００１１】
図１１を参照すると、ここには、入力ポート１１１０と、３段交換ユニット（交換機構）１１３０と、出力ポート・ユニット１１５０とを含む交換機ノードが具体的に図示されている。図１１に示されている交換機ノードは、１８×１８のポート交換機構を供給する。入力ポート１１１０および出力ポート１１５０は、図１の入力ポート１１０および出力ポート１５０と同じ回路を用いて実装される。３段交換機構１１３０は、６つの交換モジュールＡＳＸを含む第１ステージ（入力）１１３１と、６つの交換モジュールＡＸＢを持つ第２ステージ（クロスバー）１１３２と、６つの交換モジュールＡＳＸを含む第３ステージ（出力）１１３３とを持って実装される。第１ステージの６つの各ＡＳＸモジュールは、３つの入力ポート・カードのいずれからも入力を受け取ることができ、６つの第２ステージのＡＸＢモジュールのどれにもアクセス可能な３→６伸長機として構成されている。第２ステージの６つの各ＡＸＢモジュールは、６つの第３ステージのＡＳＸモジュールのどれにもアクセス可能な６×６ポート・クロスバーで構成されている。第３ステージの６つの各ＡＳＸモジュールは、３つの出力ポート・カードのいずれにも出力可能な６→３集線装置として構成される。ＡＳＸモジュールは、図３参照により前に説明したものと同じである。
【００１２】
図４に示されるＡＸＢモジュールは、プロセッサ・ベースであり、６つの出力ポート４０２に相互接続する６つの入力ポート４０１と、相互接続されたマイクロプロセッサ・インタフェース４０３と、バックプレッシャ処理装置４０４と、経路付けアービトレーション回路４０５とを含む。バックプレッシャ処理装置４０４および経路付けアービトレーション回路４０５は、それぞれ４１０および４２０のパスを経由して、第１ステージ１１３１および第３ステージ１１３３の交換モジュールにもつながっている。ＡＸＢモジュールは、６×６ポート・クロスバ相互接続装置である。ＡＸＢモジュールの多くの機能は、ＡＳＸの機能と同様のものである。しかしながら、バッファリングが利用されるのは入力４０１および出力４０２ポート・ユニットだけである。このように、ＡＸＢモジュールは、内部のＲＡＭストレージを必要としない。
【００１３】
本発明によれば、マルチキャスト要求に関連し、１段（図１）または多段ＡＴＭ交換システム（図１１）のいずれかの入力ポートから受信されたＡＴＭセル（または同様のパケット）も、その交換機の出力ポートのマルチキャスト要求により定義されたどのセットにも、可能な最小の数のストレージ・サイトと、交換機を通る単一のパスで所望の出口（出力ポート）の全てに到着するように交換する相互接続リンクを利用して分配される。この資源の最適使用を達成するため、所望の出口のセットを定義するオリジナルのマルチキャスト要求Ｄは、交換機の相互接続リンクを通してミニマルツリー・パスを構成する明示的なな経路のセットの１つもしくはそれ以上の部品に分解される。本発明によれば、これらの最適経路要素の表現は、ストレージ制御機構およびリンク割当機構を含む交換システムの制御構成要素が、これを直接的に翻訳し要求されるシステム資源の最適使用が達成することができるものである。
【００１４】
本発明の最適経路の各部分の表現方法は、ヘッダにリンクの明示的な出力ポートのビットマップ（図５の５２１など）を含めるように変更することによって交換機構に入力された標準のＡＴＭセル（図５の５００）を変更または拡張して、現在の位置から１段以上の交換機構を通って、要求された出力ポートまで渡るようにするものである。含まれるべき出力ポート・ビットマップのパターンは、マルチキャスト・リクエスト−典型的にはセル・ヘッダ（図５の５０１）中の仮想回線（ＶＣ）アドレス（ＶＰＩ，ＶＣＩ）を参照することによる−で識別される翻訳テーブル（図９）ロケーションから抜き出したものである。多段交換機構（図１１など）の場合、出力ポート・ビットマップは、全体の段数の部分だけを通るツリーパスを識別してもよい。部分的な各パスの終点で、ビットマップの既に通過した部分は廃棄され、ビットマップの新しい部分が、ここでもＶＣアドレスまたはその他の実装で決められたシステム固有の接続情報を参照することにより抜き出され（または生成され）付加される。この新しい部分的なパス・ビットマップは、現在の交換機構ロケーションより、出力ポート方向に向かって先のサブツリーの構成要素だけを表している。この部分パス分解の階層的またはモジュール方式テクニックにより、通過するトータルのパスは、どんな一時点一地点で、交換機ノードまたはシステムのストレージと伝送の効率を損なうことなく、一度にセルに付加できるであろうリンクやポートよりかなり多くのリンクとポートから構成されているが、各ビットマップ・セグメントまたはサブツリー表現は少ないビット数で持つことができる。
【００１５】
交換システムの各ノードにおいて、すなわち、交換機内のリンクおよび／またはポートの相互連結の各ポイントにおいて、セルは、今度はそのパス内の各前方のリンクへのアクセスのため格納されていてもよい。本発明では、このノードから前方に移動するリンクの数とは無関係に、セルは各交換ノードごとに一回格納される。これを達成するためのテクニックは、まず、セルが加えられた参照カウント・フィールドで格納されることであり、この参照カウントは、そのセルが格納されるノードから前方のリンクの数のビットマップ表現から自動的に生まれるものである。次に、セルが格納されるので、このノードから前方に通過するようにする各リンクへの配信のためそれをキューイングするのに必要な情報もまた、各入力リンクまたはポートからひとつのセルをサーブするのに要する時間内で格納される。このマルチキャスト・キューイング情報の並行ストレージは、交換機のノードを入力するためにセル用に余地がある場合、そのマルチキャスト・ツリー内のノードから前方のリンクおよび／またはポートすべてへの配信が確実になされることを保障する。上記のインプリメンテーションにおいて、マルチキャスト・キューイング情報の並行ストレージは、次の２つの異なる方法で成し遂げられる。
【００１６】
１．最高帯域幅のシステム要素については、完全に並列キューイング機構が、これらの要素のセル・サービス時間内でセルと並行にセルのマルチキャスト目的地のすべてについての入力を行う。
２．低い帯域幅のシステム要素、特に出力の数が大きいものについては、ビットマップが、セルの格納と並行に且つセル・サービス時間内で特別マルチキャスト・ステージング・キュー内に格納される。セル・サービス時間内で追加のタイムスロットが提供され、よって各ステージング・キュー・エントリが格納されるマルチキャスト目的地ビットマップにしたがって、マルチキャスト・ステージングから出力キューに多数のキュー・エントリが行われる。各セル・サービス時間内のそのような追加のタイムスロットを十分な数提供することにより、すべてのセルがシステムから物質的に離れることのできる率を超える率でマルチキャスト・エントリが行える。キューイング・ハードウエアのそのようなタイムシェアリングにより、低い帯域幅の要素についてインプリメンテーション全体の節約が成し遂げられる。
【００１７】
【詳細な説明】
【仮想接続情報】
図９および１０を同時に参照して、図１の交換システムにおける仮想接続のセットアップについて説明する。発呼者のマルチキャスト要求に応じて（図１４のステップ１４０１）、交換システムは、マルチキャスト仮想接続（ＶＣ）識別子を確立し、仮想接続（または翻訳）テーブル図９の９００を初期設定し、各発呼者のＶＣに関連する情報を格納および更新する。各ＶＣテーブル・エントリは、具体的に、３つの連続したワードからなり、図９に示されたフォーマットを有する。特定のポート・カードについて、仮想接続テーブルのサイズは、ポートがサポートするように設計される最大数の入力仮想接続の関数である。
【００１８】
ＶＣテーブル９００に対するアドレス９０１はＶＣ＿ｉｎｄｅｘおよびメモリ内のテーブルのベース位置に対するポインタを用いて次のように計算される。
【００１９】
【数１】
0003577188.tif 000002
このＶＣテーブル・アドレス９０１は、次の情報を含むこのマルチキャスト仮想接続に関する情報を格納するよう用いられる。
●出力ポート・ビットマップ（たとえば３６ビット・ワイド）９０５は、セルが経路付けされるべき交換システムの出力ポートを示す。ユニキャスト・セルについては、そのフィールド内の単一ビットのみが「１」に設定され、マルチキャスト・セルについては、多数のセルが「１」に設定される。ビット３２から３５が部分カード０から１５を出力するものを識別しながら、個々のビット０から３１は、それぞれ出力カードの出力ポート０から３１に対応する。
●遅延優先順位（ＤＰ）フィールド９１１が、この仮想接続のための４つの遅延優先順位（０〜３）のひとつを提供する。ここで０の値は、低相対的待ち時間を有する。
●ルーティング・フィールドのキュー９１２は、出力ポートに関連し、入力キューイング・ロジックにより用いられ、このセルを格納する出力キュー（ポート・カード上のアウト０〜アウト５）を識別する。ポート・カード上では、ポート・ビットマップは、出力キューを決定するためには用いられない。
●バックプレッシャのキュー（ＱＢ）９１３は、入力キューイング・ロジックにより使用され、交換機能内のトラヒック輻輳を決定し、マルチキャスト・セルをスイッチ機能へ送信する。
【００２０】
接続タグ９０８は、ポート・カードのためのヘッダ翻訳ルックアップ（ＨＴＬ）テーブル（図７）に対するアドレス（ＨＸＬＵ）を割り出し、ｈｔｍ＿ｉｎｄｅｘを得るために用いられる。ｈｔｍ＿ｉｎｄｅｘから、ヘッダ翻訳（ＨＴ）テーブル（図６）に対するアドレスが得られる。ＨＴテーブルは、接続ごとの発信または新たなＶＰＩ／ＶＣＩが記憶され、アクセスされるところである。１６ビットの接続タグは、６４Ｋまでの出力ＶＣをサポートする。ＨＸＬＵデータ、ＨＸＬＵフォーマット、ＨＴテーブル・データおよびＨＴテーブル・フォーマットは、本明細書の後のセクションに記載されている。
【００２１】
ＶＣテーブルが確率すると、スイッチ・システム（図１または図１１）は、要求されるマルチキャスト接続の標準のＡＴＭセルを受ける準備が整う。
【００２２】
ステップ１４０２において、システムは図８のルックアップ・テーブルＬＵＴ１、ＬＵＴ２と、図８のＨＴテーブルと、図７のＨＴＬテーブルを確立する。ステップ１４０３において、マルチキャスト・セルは、標準のＡＴＭフォーマットにおけるシステムにより受け取られる。
【００２３】
図５を参照して、図１の入力ポート・ユニット１１０で受信された標準ＡＴＭセル５００のフォーマットについて説明する。ＡＴＭセル・フォーマットは、５バイト（４０ビット）長のＡＴＭヘッダ５０１と、４０バイト長のペイロードとを含む。ＡＴＭヘッダは、４ビットの基準フロー制御（ＧＦＣ）と、８ビットの仮想パス識別子（ＶＰＩ）５０２と、１６ビットの仮想チャネル識別子（ＶＣＩ）５０３と、３ビットのペイロードタイプ識別子（ＰＴＩ）と、１ビットのセル・ロス優先順位（ＣＬＰ）と、８ビットのヘッダ・エラー・コントロール（ＨＥＣ）とを有する。
【００２４】
図１４の１４０４から１４１０までのさまざまなステップは、本発明にしたがった有限状態マシーンにより実行される。これらのさまざまなマシーンの特別な作動の詳細は、この明細の付録により詳しく記載されている。１段ＡＴＭ交換機の操作は、１４０１から１４１１までのステップにより記述され、マシーン１から３および７から１１を利用する。多段ＡＴＭ交換機は、１４０１から１４０６および１４０９から１４１１までのステップを含み、付録に記載のすべてのマシーン１〜１１を利用する。
【００２５】
ステップ１４０４（マシーン１により実行される）では、ＡＴＭセルのヘッダは入力ポート・カードにより修正される。入力ポート・ユニット１１０から（図１のリンク１２０を通って）出力され、交換ユニット１３０に入力された修正されたフォーマットの出力セルは、ローカル・ヘッダ５２３と、低標準ヘッダ５２４と、ペイロードとを含むように５２０で示されている。本発明によれば、標準ヘッダ５０１のＶＰＩおよびＶＣＩセグメントが用いられて、図８のルックアップ・テーブルＬＵＴ１およびＬＵＴ２と、図９のＶＣ（翻訳）テーブルと、図７のＨＴＬテーブルと、図６のＨＴテーブルとにアクセスし、ローカル・ヘッダを生成する。具体的なローカル・ヘッダは、優先順位ビット（Ｐ）を含む複数のセグメントと、接続タグ５２２と、出力ポート・マップ５２１と、ルーティングのキュー（ＱＲ）と、サービス特徴情報（ＮＩ、ＣＩ）、ポリシング情報（ＰＯＬ）と、Ｓビットとを含む。低標準ヘッダ５２４は、ヘッダ翻訳プロセスの間に得られる標準ヘッダのＧＦＣ、ＶＣＩ、ＰＴＩおよびＣＬＰセグメントを含む。ヘッダ翻訳は、次のパラグラフに詳細に記述される。
【００２６】
ヘッダ翻訳
図１の本発明の交換ノードの具体例は、標準ＵＮＩおよびＮＮＩインターフェイスで動作可能である。ＵＮＩインターフェイスについては、５ビットのサブポート部材と、ＶＰＩ５０２の８つの最小有効ビット（ＬＳＢｓ：ｌｅａｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔｓ）と、ＶＣＩ５０３の１４ＬＳＢとが、２７ビットの潜在アドレス・スペースを創造する。ＮＮＩインターフェイスについては、追加の４つのＶＰＩビット（ＡＴＭセル５００のヘッダのＧＦＣビット）が３１ビットの潜在アドレス・スペースを創造するために用いられる。
【００２７】
仮想接続インデックス（ＶＣ＿Ｉｎｄｅｘ）は、ＶＣテーブル９００（翻訳テーブルとしても参照される）（図９）に対するＶＣ＿Ａｄｄｒｅｓｓを割り出し、特定の仮想接続に関連する出力ポート・ビットマップ９０５（マルチキャスト・ビットマップとしても参照される）を得る。インデクシングには２つのレベルが用いられる。ＵＮＩインターフェイスについては、第１のレベルが、８Ｋまでの単一ＶＰＩ接続のスペースに対する各サブポートをマッピングする。ＮＮＩインターフェイスについては、第１のレベルが６４Ｋまでの単一ＶＩＰ接続のスペースに対する各サブポートをマッピングする。ＵＮＩおよびＮＮＩ両方のインターフェイスについては、第２のレベルが６４Ｋまでの仮想接続のスペースに対する各ＶＰＩ接続をマッピングする。図８は、ルックアップ・テーブルＬＵＴ１およびＬＵＴ２を用いて２レベル・インデクシングの例を示している。サポート部材８０１は、アクセスＬＵＴ１＿Ａｄｄｒｅｓｓとして用いられ、テーブルＬＵＴ１からＶＰ＿ＢａｓｅおよびＭＡＸ＿ＶＰＩ番号を得る。（ＡＴＭセル５００で受け取られた）ＶＰＩ５０２がＶＰ＿ＢａｓｅとＶＰ＿Ｂａｓｅ＋ＭＡＸ＿ＶＰＩとの間に下がる場合、ＡＴＭセルは受け入れられる。あるいは、受け入れられない。ＶＰ＿Ｂａｓｅ＋ＶＰＩ５０２は、テーブルＬＵＴ２に対するアクセス・アドレス（ＬＵＴ２＿Ａｄｄｒｅｓｓ）として用いられ、ＶＰ＿Ｂａｓｅ、ＭＡＸ＿ＶＣＩ、ＶＣＩ＿Ｉｎｄｅｘを得るために用いられる。受け取られたＶＰＩ５０２がＶＰ＿Ｂａｓｅ＋ＭＡＸ＿ＶＣＩよりも小さい場合、ＡＴＭセル５００は、受け入れられる。または受け入れられない。
【００２８】
図８に示されたように、テーブルＬＵＴ２から得られた仮想接続ＶＣテーブル・アドレス９０１は、図９のＶＣ（翻訳）テーブル９００、ポリシング・テーブル９０２および入力カウンタ９０３にアクセスするために用いられるＶＰ＿Ｂａｓｅ＋ＶＣ＿Ｉｎｄｅｘである。
【００２９】
図９を参照すると、ポリシング・テーブル９０２は、翻訳テーブル９００として同様にアクセスされ、標準「ＵＰＣ」操作のためのメモリと制御情報を提供する。すなわち、セルをマーク付けまたは注目するために用いられる。
【００３０】
入力カウンタ９０３および出力カウンタ９０４は、ポリシングの結果の統計を集めるために用いられる。
【００３１】
ＶＣ翻訳テーブル９００は、ＶＣテーブル・アドレス９０１を用いて、出力ポート・ビットマップ９０５と、接続タグ９０８と、遅延優先順位９１１と、ルーティングのキュー（ＱＲ）フィールド９１２へ各仮想接続のためのアクセスを提供する。
【００３２】
出力ポート・ビットマップ・フィールド９０５は、本発明の例示的マルチキャスト接続のために、相互接続する交換ユニット１３０を介して入力ポート１０２からマップを提供する。
【００３３】
マルチキャスト接続のための翻訳テーブル９００エントリが一度アクセスされると、ヘッダ翻訳を発生することができる。
【００３４】
ヘッダ翻訳は、入力ポート・ユニット１１０のサブポート・キューから読み込まれた出力セルのためのローカル・ヘッダ５２３および低標準ヘッダ５２４を生成するために用いられる。ヘッダ翻訳は、図６に示されたヘッダ翻訳（ＨＴ）テーブル６００にアクセスすることにより発生する。ヘッダ翻訳（ＨＴ）テーブル６００は、フィールド：つまりＰ（ワード上の奇数パリティ）と、Ｒ（予約された）と、Ｓ（ＶＰ交換フラッグ）と、ｖｐｉ４（ＧＦＣ／ＶＰＩヘッダ・ビットを置き換えるか否かを示すための制御ビット）と、新たなＶＰＩ＿４（ＶＰＩの最も有効なビットＭＳＢ）と、新たなＶＰＩ＿８（ＶＰＩの８つの最小有効ビットＬＳＢ）；新たなＶＣＩ（１６ビットと）からなる。
【００３５】
前述したように、新たなＶＰＩおよびＶＣＩの値６０１は、呼セットアップの間に発信ＶＣごとのマイクロプロセッサによって図６のヘッダ翻訳（ＨＴ）テーブルに格納された。「ｖｐｉ４ビット」と呼ばれる新たＶＰＩ／ＶＣＩの値が格納された制御ビット新たなＶＰＩの４ＭＳＢがいかにして処理されるかを決定する。ＶＰ交換フラグＳとともにこれらの値およびＡＴＭヘッダ５０１は、図５の出力セル５２０のための新たな修正されたヘッダ（ローカル・ヘッダ５２３および低標準ヘッダ５２４）を生成するために用いられる。
【００３６】
ＰＴＩおよびＣＬＰビットは、ＡＴＭヘッダ５０１から読み込まれ、出力セル５２０の低標準ヘッダ５２４へ挿入される。Ｓビットは、（ＡＴＭヘッダ５０１に格納された）オリジナルのＶＣＩまたは（ＨＴテーブル６００に格納された）新たなＶＣＩが発信低標準ヘッダ５２４に挿入されるか否かを決定する。ｖｐｉ４ビットは、（ＡＴＭヘッダ５０１に格納された）ＧＦＣフィールドまたは新たなＶＰＩ（ＨＴテーブル６００に格納された新たなＶＰＩの４ＭＳＢビット）が発信低標準ヘッダ５２４のフィールド５１５に挿入されるか否かを決定する。新たなＶＰＩ（ＨＴテーブル６００に格納された新たなＶＰＩの４ＬＳＢビット）の残りのビットもまた、低標準ヘッダ５２４のフィールドに挿入される。
【００３７】
修正ヘッダ・セグメント５２３および５２４を生成するには、２レベルのルックアップを介して、適切なＨＴテーブル６００エントリへアクセスしなければならない。ＶＣテーブル９００のワード９０７の接続タグは、図７のヘッダ翻訳ルックアップ（ＨＴＬ）テーブルに対するインデックスとして用いられる。ＨＴＬテーブル内のバードのアドレス、ｈｘｌｕ、は、次の式：
【数２】
0003577188.tif 000003
から得られる。
【００３８】
ＨＴＬのｈｘｌｕ＿ａｄｄｒｅｓｓは、接続タグと関連する図６のＨＴテーブル６００内のｈｔｔ＿ａｄｄｒｅｓｓを指すインデックス（ｈｔｍ＿ｉｎｄｅｘ７０１）を格納する。ｈｔｔ＿ａｄｄｒｅｓｓは、ローカル・ヘッダ５２３および低標準ヘッダ５２４に格納される得られた出力セルのためのＳやｖｐｉ４ビットと同様に、新たなＶＰＩおよびＶＣＩの値を得るために用いられる。
【００３９】
ＨＴテーブル６００におけるワードのアドレスは、次の式：
【数３】
0003577188.tif 000004
から得られる。
【００４０】
ユニキャスト・セルについては、ｈｔｍ＿ｏｆｆｓｅｔ（マルチキャスト・アドレス・オフセットとしても参照される）は、ゼロと等しく画定される。マルチキャスト・セルについては、多重ヘッダ（マルチキャスト出力ポートごとにひとつ）は、連続メモリ位置に格納される。マルチキャスト・セルの出力ポート接続ごとに、適切なｈｔｍ＿ｏｆｆｓｅｔが用いられる。ｈｔｍ＿ｏｆｆｓｅｔは、マルチキャスト・ヘッダそれぞれにアクセスするために用いられる。
【００４１】
６４Ｋの出力ＶＣをサポートするには、メモリの６４ＫのワードがＨＴＬテーブル７００に必要である。
【００４２】
交換機１３０から（図１のリンク１４０を通して）出力され、出力ポート・ユニット１５０に入力されるセルのフォーマットは、図５における５４０として示される。セル５４０のフォーマットは、修正ローカル・ヘッダ５４２（出力ポート・マップ・セグメントが出力ポート・バックプレッシャ・マップで置換された状態）と、低標準ヘッダと、ペイロードとを含む。出力ポート・ユニット１５０から出力されるセルのフォーマットは、図５における５６０で示される。セル５６０は、新たなＶＰＩセグメントを持ち、新たなＶＣＩセグメントを持っても持たなくてもよいことを除けば、５００で示される標準ＡＴＭセルである。
【００４３】
開示された実施例によれば、図６、７、８および９のテーブルは、すべてポート・カードのＡＬＭ集積回路のＡＬＭメモリに格納される。
【００４４】
マルチキャスト接続処理
次の例は、入力ポート・ユニット１１０、交換ユニット１３０および出力ポート・ユニット１５０で行われるマルチキャスト接続処理を記述する。
【００４５】
処理の例として、出力ポート１０１（すなわち、サブポート１またはポート・カード１、出力ポート０１）、１０４、２０３、２０４および４０２へのデリバリのためのマルチキャスト接続リクエストと関連する入力ポート１０２（すなわち、サブポート１，０２）に到着したセルを考えよう。マルチキャスト・セルのデリバリは、入力ポート１０２と要求された出力ポートとの間に確立された仮想接続（ＶＣ）を介して発生する。前述したように、ステップ１４０１および１４０２において、最初にマルチキャスト接続が確立されたとき、図１の交換システムは、発呼者のマルチキャスト・リクエストに答えて、出力ポート・ビットマップＰＢＭや、キュー番号ＱＮや、遅延優先順位ＤＬＰや、接続タグなどのエントリを含むＬＵＴ１、ＶＣ、ＨＴＬおよびＨＴテーブルを確立し、ＶＰＩおよびＶＣＩ識別子をマルチキャスト接続の間に送られたセルすべてと関連付ける。ステップ１４０３では、ＶＰＩおよびＶＣＩ識別子は、入力ポート１０２が修正ヘッダ５２３および５２４をステップ１４０１で生成できるようにする。修正ヘッダ５２３および５２４で識別された出力ポート・ビットマップ５２１は、交換ノードが入力ポート１０２と識別された出力ポートとの間の所望の仮想接続を確立できるようにする。
【００４６】
出力ポート１０１（すなわち、出力カード１、出力ポート０１）のための出力ビットマップは、図９のＶＣテーブル９００の出力ポート・ビットマップ９０５におけるビット１における「１」とビット０，２−３１におけるすべての「０」とを有し、出力ポート・ビットマップ９０５のビット３２〜３５は、２進数にコード化され、出力カード１を示す「０００１」となる。
【００４７】
ＡＴＭセル５００は、ポート・カードに配されるＡＴＭレイヤ・マネジャ（ＡＬＭ）およびＡＴＭバッファ・マネジャ（ＡＢＭ）回路により処理される。本例では、ＡＴＭセルは入力ポート１０２に到着するので、ポートカード１のＡＬＭ１およびＡＢＭ１がＡＴＭセルを処理する。
【００４８】
本例のマルチキャスト・リクエストについては、各ＡＴＭセルは、代表的ペイロード・ビット・パターン「１１０１」で、相互交換ユニット１３０を介して出力ポート・カード１、２および４に運ばれるはずである。
【００４９】
入力キューイング
ステップ１４０５（マシーン２によって実行される）において、セルが入力サブポート（たとえば、入力ポート１０２）からポート・カード１へ入力されるとき、セルはＡＢＭメモリに格納される（図１０）。ＡＢＭメモリ（図１０）は、セルに関する情報を格納するために２つの別々のメモリ・セクション：つまりポインタ・メモリ１０１０とセル・メモリ１０２０とを有する。それらはそれぞれ、入力セクション１０１１、１０２１および出力セクション１０１２、１０２５に対応するエリアへさらに分割される。セルの格納アドレスは、利用可能なメモリ・アドレス（すなわち、フリー・リスト）のリンク・リスト１００１から得られる。セル・ベース上に配置されたリンク・リスト１００１は、セル・メモリ１０２０の入力セクション１０２１内のセル・バッファにアクセスするために用いられる。
【００５０】
既知の方法で、インデクシング・スキームは、リンク・リスト１００１上の各セルを見失わないようにする。インデックスは、物理的メモリ・アドレスではなく、テーブルへのオフセットである。これらのインデックスは、リンク・リストを形成するため連鎖されている。各インデックスは、リンク・リスト内の次のエントリに対するポインタである。ポインタは、リンク・リスト１００１のキュー・ポインタ・セクションに割り当てられ、格納される。入力リンク・リスト・メモリ１００１内のポインタとセル・バッファ１０２３に格納されたセルとの間には一対一対応が存在する。これは、与えられたリストのヘッド・レジスタがセル・メモリに格納されているセルのインデックスを格納するということである。
【００５１】
入力ポート・ビットマップ（ローカル・ヘッダ５２３のワード５２１）は、ポインタ・メモリ１０１０の入力ポート・ビットマップ・セクション１００３に格納される。
【００５２】
交換機構１１３０に予定されている入力ポート・カードを残すセルは、セル・メモリ１０２０から読み込まれ、入力リンク・リストから離れる、つまりキューから外される（ｄｅｃｕｅｕｅｄ）。各タイムスロットにおいて、入力セルはセル・メモリ１０２０に格納され、メモリからのセルは交換機構１１３０に送られる。
【００５３】
セルをキューから外すには、ステップ１４０６（マシーン３により実行される）において、入力キュー１００１から取り除かれ、読み込み選択アルゴリズムにしたがってタイムスロットごとに一度ずつ交換機構１１３０に送られる。付録内のマシーン３として記述されるマシーンで参照される本発明の読み込み選択アルゴリズムにしたがって、キューは、ラウンド・ロビン基準にしたがって滞在される。キューが空の場合またはキュー内のすべての遅延優先順位（Ｐｒ０〜Ｐｒ３）がバックプレッシャ化された（マシーン３に詳細に記載されている）場合、そのキューはその機会をのがし、その選択ロジックによって飛ばされる。
【００５４】
ステップ１４０６（マシーン３により実行される）がセルを出力した後、セルはステップ１４０７（マシーン７により実行される）で記述されるように交換機構により処理される。一段単一装置が実装される場合、その装置のオペレーション、ステップ１４０７および１４０８は、マシーン７および８で記述される（後述する）ものと基本的に同一である。キュー・バックプレッシャがクロスバープロセス（マシーン５、６および７の一部として記述される）を介して間接的にではなく出力ポート・カードに直接信号が送られる。
【００５５】
ルーティング・ビットマップは相互交換ユニット１１３０を介してルーティングをカバーしているので、ＶＣ対ルーティング・マップ・ルックアップ機能は必要ない。相互交換ユニット１１３０内のオペレーションは、比較的簡単であり、図１０のＡＢＭ回路メモリの前述のオペレーションと同様である。
【００５６】
ステップ１４０８（マシーン８で実行される）では、質問内のセルが割り当てられる相互交換ユニット１１３０の複数の出力キュー（Ｏｕｔ０〜Ｏｕｔ５）のいずれにおいても、問題のそのセルの先の他のすべてのエントリがサーブされたあと、マルチキャスト・セルは入力ポート・ユニットのセル・バッファ１０２３から抜き出され、格納された参照カウントはひとつずつ減らされ、セルは図１０で示された出力ポート・ユニット１１５０へそのキューに関するリンク１１４０を横切って運ばれる。参照カウントについての減少オペレーションがゼロの値を示した場合、これは、そのセルのすべてのキュー・エントリがサーブされたことを示し、相互交換ユニットにおける関連セル・バッファはフリーであると印付けされる。
【００５７】
図１０のインプリメンテーションの例では、初期のルーティング・ビットマップのみが入力ポートを介して延在し、交換ステージ１１３０と相互接続する。したがって、出力ポート・ユニットに対するエントリ上で、そのユニットのＶＣ対マップ・ルックアップ回路（すなわち、ＬＵＴ１、ＬＵＴ２およびＴＲテーブル）に対して２回目のリファレンスが行われなければならない。
出力キューイング
【００５８】
次のセクションは、出力ポート・カード上の出力キューイングの概略を説明する。
【００５９】
ステップ１４０９（マシーン９により実行される）において、交換機構１１３０から出力ポート・カードを入力するセルは、それらが伝送されるまで、セル・メモリ（たとえば、図１０の１０２５）の出力セクションに格納される。出力セルは、キューごとに優先順位リンク・リストで３２の出力サブポート・キューへ構成される。各リンク・リストは、異なる遅延優先順位に対応する。
【００６０】
図９の仮想接続（ＶＣ）テーブル９００からのキュー番号ＱＮおよび遅延優先順位ＤＬＰは、出力キューのひとつと得られたセルの４つのリストのうちのひとつを識別し、適切な出力リンク・リスト１００４上のセルをキューに入れるために使用される。
【００６１】
リストごとに、次の値が維持される：
●ヘッド    リストの最初のセルに対するポインタ
●テイル    リストの最後のセルに対するポインタ
リスト上の各セルを見失わないようにするために間接的ポインタ・スキームが用いられる。インデックス・ペア（ＩＰ）と呼ばれる小さなブロックのインデックス値は、リンク・リスト５５１を形成するために連鎖される。各ＩＰは、次の２つのフィールドを含む：
●セル・インデックス    セル・データの最初のワードに対するインデックス
●次のインデックス    リンク・リスト内の次のエントリに対するポインタ
ＩＰは、セル・バッファ１０２３とは別に出力ＩＰメモリ１０５１に割り当てられ、格納される。これは、ＩＰに対する得られたリスト・ポイントのヘッド：ひとつのインデックスはセルの位置を提供し、もう一方のインデックスは次のＩＰの位置を提供することを意味する。これは、ＩＰｓ（ＩＰフリー・リスト）用とセル（出力フリー・リスト）用の２つのフリー・リストが必要である。
【００６２】
出力ポートの出力キューイングは、図１０の出力ポインタ・メモリ１０１２と出力セル・メモリ１０２５を用いる。
【００６３】
出力ポインタ・メモリ１０１２は、出力側用に次のデータを含む：
●ＩＰフリー・リスト（出力ＩＰメモリ１０５１に格納されている）
●出力フリー・リストおよびマルチキャスト・フリー・リスト（出力リンク・リスト・メモリに格納されている）
●出力リスト（３２個のキュー×４＝１２８個のサブポート・リスト；出力ＩＰメモリ１０５１に格納されている）
●出力ヘッダ翻訳オフセット（出力ヘッダ翻訳オフセット・テーブル１０５２に格納されている）
●サブポート・マルチキャスト・ビットマップ／マルチキャスト・カウンタ（セル・メモリに格納される出力セルごとにひとつ；サブポート・マルチキャスト・ビットマップ・エリア１０５４に格納されている）
●ラウンド・ロビン・スケジュール（１００５に格納されている）
出力インデックス・ペア（ＩＰ）メモリ１０５１は、ＩＰフリー・リストと、さまざまな出力サブポートの全実行中のキュー・エントリとを含む。インデックス・ペア（ＩＰ）フリー・リストは、出力ＩＰｓを格納するように規定されるポインタ・メモリ１０１０の１０５１内のインデックス・ペア（セル・インデックスおよびリンク・ポインタ）のリンク・リストである。そのリストは、リスト内の最初と最後のエントリをそれぞれ指すヘッド・レジスタとテイル・レジスタとからなる。出力ＩＰは２つのワードからなる。第１のワードは、セル・インデックスであり、第２のワードは、次のインデックスである。セル・インデックス・フィールドは、セル・メモリ１０２０内の３２Ｋまでの出力セルのアドレスを決めるに十分な１５ビットである。最初のフリー・アドレスは、出力ＩＰフリー・リストのヘッド・レジスタ内に格納される次のインデックスの値から求められる。フリー・リストから得られ、さまざまなサブポート出力キューにリンクされたＩＰｓは、出力セル・メモリ１０２５内の格納セルのセル・インデックスで修正される。よって、さまざまなサブポート・キュー上のいくつかのエントリは、すべて同じセル・ストレージ・ロケーションを参照する。
【００６４】
出力リンク・リスト・メモリ１００４は、出力フリーとマルチキャスト・ステージング・リンク・リストとを両方含む。出力フリー・リストは、ユニキャストおよびマルチキャスト・セルに用いられるポインタ・メモリ内のフリー・ブロックのリンク・リストである。フリー・リストは、リスト内の最初と最後のエントリをそれぞれ指すヘッド・レジスタとテイル・レジスタからなる。マルチキャスト・ステージング・リンク・リスト・エントリは、あるワード−次のインデックスポインタからなる。次のインデックス・ポインタは、セル・メモリ内の３２Ｋまでのマルチキャスト・セルのアドレスを決めるに十分である。優先順位ごとにひとつのマルチキャスト・リストはそれぞれ、リスト内の最初と最後のセルをそれぞれ指すヘッド・レジスタとテイル・レジスタからなる。
【００６５】
マルチキャスト・キューがサブポート・キュー（たとえばＳｕｂ０）へセルをリンクする場合、サブポート・キューと関連するオフセットは１０５２に格納される。オフセットは、ヘッダ翻訳の間マルチキャストの特別なレッグのヘッダ翻訳エントリを求めるために用いられる。出力ＩＰメモリ１０５２におけるセル・インデクス・ペア（ＩＰ）ごとにひとつのヘッダ翻訳オフセットが存在する。
【００６６】
サブポート・ビットマップ１０５４は、各ビットが出力ポート・カード上のサブポートに対応する３２ビットからなる。各入力ＶＣ接続は、関連接続タグおよびサブポート・ビットマップ１０５４を有する。サブポート・ビットマップ１０５４は、ＶＣ接続がセットアップするときにポート・カード・マイクロプロセッサにより書き込まれる。セルが交換機構１１３０から到着したあと、受信されたセルが書き込まれる出力サブポート・キューを決定するためにアクセスされる。特定の接続のためのサブポート・ビットマップは、接続に対応する接続タグ・データを用いて１０５４に位置決めされる。ユニキャスト・セルについては、サブポート・ビットマップ１０５４のたったひとつのビットが設定され、セルは対応するサブポート・リストに付加される。サブポート・マルチキャストについては後のパラグラフで記述する。
【００６７】
ステップ１４１０（マシーン１０により実行される）では、マルチキャスト・セルがマルチキャスト・リストのヘッドに行く場合、サブポート・マルチキャスト・ビットマップ１０５４は、セルのコピーが予定されている場所を決定するために検索される。セル・メモリ１０２０内のマルチキャスト・セルは、それぞれ、ポインタ・メモリ１００５に格納された関連サブサポート・マルチキャスト・ビットマップ１０５４を有する。サブポート・マルチキャスト・ビットマップがマルチキャスト・キューのヘッドでエントリにより読み込まれると、マルチキャスト・アドレス・オフセットはその場所に格納される。セル・メモリ内の出力セルは、それぞれ、セルの多くのコピーがいかにして作られるかを決定する単一の５ビット（３２カウント）マルチキャスト・カウンタ１０５５と関連している。ユニキャスト・セルが交換機構から受け取られ、セル・メモリに書き込まれた場合に、マルチキャスト・カウントは、「１」に初期化される。マルチキャスト・セルが交換機構から受け取られた場合、マルチキャスト・カウンタは、サブポート・マルチキャスト・ビットマップがマルチキャスト・キューにより読み込まれ、スキャンされる前には初期化されない。得られたセルのマルチキャスト・カウンタ１０５５は、セルがサブポート・キューから読み込まれるごとに減少される。マルチキャスト・カウントが０と等しい場合、マルチキャスト・セル・ロケーションは出力フリー・リストに移動される。リンク・リスト１００４内の次のマルチキャスト・セルはマルチキャスト・リストのヘッドへ行く。
【００６８】
ラウンド・ロビン・スケジュールは、ポインタ・メモリ１０１０内の１００５に格納される複数のエントリからなる。タイムスロットごとに１エントリが読み込まれる。
【００６９】
各タイムスロットごとに、ひとつのセルがサブポート・キューから取り除かれ、出力サブポートへ送られる。読み取り選択アルゴリズムは、前述の入力側と同様である。しかしながら、厳密な順番でキューをサーブする代わりに、キューはさまざまな長さの重みづけされたラウンド・ロビン・スケジュール１００５を用いて処理される。テーブル内の各エントリは、「読み込まれるセルなし」の値と同様、このタイムスロットを読み込むためにサポート番号を指定する。
【００７０】
サブポート出力速度は、特定のサブポートがスケジュールに現われる周波数により決定される。４６１の具体的なスケジュール長さ（Ｌ）は、１．５Ｍｂｐｓステップで１．５Ｍｂｐｓから６２２Ｍｂｐｓまでのデータ転送率を許容する。特定のサブポート・キューを参照する（ｒｅｆｅｒｅｎｃｉｎｇ）するエントリの数をＮ、合計のスケジュール長さをＬとすると、可能な速度は、次の式：
【数４】
0003577188.tif 000005
で算出される。
【００７１】
遅延優先順位は、前述した１６エントリ重みづけされたラウンド・ロビン・スケジュールを用いて、入力側と全く同様の方法でサブポート・キュー内でサービスされる。
【００７２】
５６０で示されるサブポートからの出力セルのデータ・フォーマットは、ＶＰＩが新しいこと、ＶＣＩが新しくてもそうでなくともよいことを除けば入力セルのデータ・フォーマットと同一である。
【００７３】
サブポート・マルチキャスト・オペレーションは、次のように進行する。
交換機構１３０から受け取られた各セルについて、ポインタ・メモリ５１０に記憶されたサブポート・ビットマップにアクセスするために接続タグが用いられる。サブポート・ビットマップにおける１個以上のビットが「１」に設定される場合、受け取られたセルは、マルチキャスト・セルである。セルは、他の仮想接続のユニキャスト・セルとともに介在ベース上の適切なサブポート・キューすべてに順次に伝送されるまで、特定のマルチキャスト・キュー上に一時的に格納される。
【００７４】
たとえば、キュー処理装置は、各タイムスロットごとに、２つのセルをキューに入れ、ひとつのセルをキューから外す十分な能力を有すると仮定する。マルチキャスト・キュー上で待っているいくつかのセルが存在する場合、キューに入れられたセルのひとつをマルチキャスト・キューから取りだし、適切なサブポート・キューに送る。フルロード状態で、新たなユニキャストがタイムスロットごとに到着する場合、これにより特定のサブポート・リスト上のユニキャスト・セルと１：１で介在されたマルチキャスト・セルを生じる。もちろん、アイドル・セルが交換機構から受け取られた場合、マルチキャスト・セルのひとつに置き換えることができる。得られたセルは、サブポート・ビットマップに指定された予定されたサブポートに書き込まれるまで、マルチキャスト・キューのヘッドに残る。マルチキャスト・セルは３２までのサブポート・キューに書き込まれることが可能なので、そのセルについて、それらのセル・インデックス・フィールドにおいてどれも同じ値を有する、すなわちセル・メモリ内の同じセルを指す３２個の異なる出力ＩＰが存在する。セルが各サブポート・キューに書き込まれた場合、マルチキャスト・リストのヘッドから取り除かれ、マルチキャスト・リストのヘッド・レジスタが更新される。
【００７５】
本発明のマルチキャスト・リクエストについて、図１０の右上の出力ポート・ユニットは、ポート１０１および１０４用のビットマップ表現つまり「１００１」を生じる。上述のパラグラフ２に記述された低パフォーマンス要素について、第２のインプリメンテーションとしてこのケースを引用する。オリジナルの翻訳（入力ポート・ユニット内）により、有効なルーティング・マップ・エントリの存在によって、セルは出力ポート・ユニットのセル・バッファ内のフリーな場所に格納されるが、この場合、マルチキャスト・ルーティング・ビットマップはなく、マルチキャスト・ビットマップ内の数「１」と等しい参照カウントを有する。
【００７６】
セルのストレージと並行して、マルチキャスト・ルーティング・ビットマップとセル・ストレージ・バッファに対するポインタとを含むエントリが出力ポート・ユニットのマルチキャスト・ステージング・キューに入力される。一般的に、このステージング・キューは、ＦＩＦＯキューでもある。マルチキャスト・エントリがステージング・キューのヘッドに行くと、出力ポート・ユニット・ロジックは、１回に１つずつ、それぞれセル・ストレージ・バッファに対するポインタのコピーとともに、最終出力キュー（例のライン１０１および１０４）へ分配する。マルチキャスト・ステージング・キューの出力に十分早いサービス速度を供給することにより、制御ロジックは、最終の出力ポートへのデリバリ速度よりも早い速度でマルチキャストのすべてのコピーを提供することができる。このたった２つのスピードアップ要素は、最終出力ポートを介しておそらく分配されるマルチキャスト・リクエストのどの組合せにおいてもセル入力においてこの目的を達成するに十分である。
【００７７】
最後に、前にキューに入れられたエントリが出力ポートでサービスされるので、２つのコピー（例の１０１と１０４）は取り除かれ、セル・バッファ参照カウントは減少されるであろう。そして、上述したように、セル・バッファ参照カウントがゼロになった場合は、セルはフリーと印付けされる。
【００７８】
交換機構（すなわち、交換ユニット１３０および１１３０）のロスレス・オペレーションを確実とし、いずれの出力ポートもオーバーロード状態によるセル・メモリの不均衡なシェアを持たないようにするために、バックプレッシャが利用される。バックプレッシャは、各キューの遅延優先順位に選択的に付与される。各タイムスロットごとに、キュー・リストに割り当てられた最大数のメモリ位置は、動的に更新される。いずれかのリストのサイズがその算出された論理限界を超える場合、そのキュー・リストに応じたバックプレッシャ状況ビットが主張される。調整的に、状況ビットはバックプレッシャ・ビットマップとして参照される。各キュー・リストのバックプレッシャ状況は、特別キュー・リストからのセルが交換機構の次のステージまたは出力ポートへ伝送されるべきか否かを示す。バックプレッシャ・ビットマップは、出力ポート・カード１１３０の出力側から第３ステージ・モジュール１１３３へ；第３ステージ・モジュール１１３３から第２ステージ・クロスバー・モジュール１１３２へ；第２ステージ・モジュール１１３２から第１ステージ・モジュール１１３１へ；第１ステージ・モジュール１１３１から出力ポート・カード１１１０の入力側へ輻輳フィードバックを提供する。
【００７９】
マシーン１１で実行されるステップ１４１１において、テーブル６および７に記述された接続タグおよび出力・オフセットに基づいて出力セル・ヘッダが翻訳される。
【００８０】
多段交換ユニット構成
図１１を参照して、多段交換ユニット１１５０構成に用いられた３つのタイプのバックプレッシャ機構について記述する。これらのバックプレッシャ機構は、実際の物理的連結性パスではなく論理的パスを示す。たとえば、第１のステージ・モジュールからポート・カードの入力側への実際の物理的接続は存在しない。
【００８１】
第３ステージから第２ステージへ
第２ステージにより発生される第３ステージにおけるバッファのオーバーフローの防止は、２つのパートで行われる。第１のパートでは、バックプレッシャ情報が第３ステージ・モジュール１１３３から各第２ステージ・クロスバー・モジュール１１３２へ伝送される。第２のパートでは、第２ステージが後のパラグラフで記述されるように、第１のステージ・モジュール１１３１と通信する。
【００８２】
各タイムスロットごとに、各第３ステージ・モジュール１１３３は、どのレコードのキュー（ＱＲ．）が現在の動的論理限界を超えたかを確かめる。得られた論理限界を超えたリストに対応するビットはバックプレッシャ・ビットマップに設定される。各モジュール１１３３からのバックプレッシャ・ビットマップは、専用のパスにより各クロスバー・モジュール１１３２へ直接搬送るされる。１８×１８ポート交換機構１１３０を考える。３つの出力ポートをサポートするよう構成されたモジュールのためのバックプレッシャ・ビットマップ・フォーマットが図１２に示されている。したがって、各出力モジュールは、図１１の各クロスバー・モジュール１１３２へ１２ビットの情報を伝送する。その結果、各クロスバーは、タイムスロットごとに一回、１８までの出力ポートに対応する完全なバックプレッシャ・ビットマップを受ける。
【００８３】
第２ステージから第１ステージへ
図１１を参照すると、第３ステージ・モジュール１１３３におけるバッファのオーバーフローを防止するため、または、クロスバー・モジュール１１３２における出力回線争奪を避けるために、第２ステージ・モジュール１１３２から第１ステージ・モジュールへのバックプレッシャが主張される。第２から第１ステージのフィードバックは、専用のパスを介して搬送される。第２ステージへ次のフィードバック：アクセプト；第３ステージ・モジュールにおけるバッファ・フル；第２ステージ・モジュールで利用できない出力ラインを提供する。
【００８４】
ポート・カードの入力側への第１ステージ
交換機構１１３０の第１ステージ・モジュール１１３１におけるバッファのオーバーフローを防止するために、第１ステージ・モジュール１１３１から入力ポート・カード１１１０へのバックプレッシャーが主張される。バックプレッシャの適用は、リンク・リスト（ＡＬカウンタ）のサイズが算出された論理限界を超えるか否かに基づいて行われる。フィードバックは、得られた入力ステージ・モジュールへ直接接続されたライン・カードの入力側に搬送される。
【００８５】
２つのパートでバックプレッシャ信号が起きる。まず、バックプレッシャ・ビットマップが第１ステージ・モジュールからバンドの外の対応する第３ステージ・モジュールへ伝送される。各入力ステージ・モジュールは、図１３に示されたように、それを扱う１８のキューについてバックプレッシャ・ビットマップを保持する。一面構造において、各第１ステージ・モジュール１１３１は、バックプレッシャ情報を専用のパスを介してひとつの第３ステージ・モジュール１１３３へつなぐ。
【００８６】
１８×１８のポート交換機構の出力ステージ・モジュールは、各面からバックプレッシャ・マップを取り、情報を発信ＡＴＭセルのポート・ビットマップに多重化する。出力モジュールは、２つのタイムスロットごとに順次にポート０〜８および９〜１７に対応するビットマップを出力する。ポート０〜８に対応するビットマップが発信ＡＴＭセルに伝送される場合、バックプレッシャ・マップ同期ビットは「１」に設定される。あるいは、ビットは「０」に設定される。
【００８７】
得られたポート・カードに予定されるセルがない場合は、アイドル・セルがそのポート・カードへバックプレッシャ・ビットマップを運ぶために生成される。
【００８８】
第３ステージに対するポートカードの出力側
各出力ポート・カードはまた、ポート・カード１１１０の入力側から交換機構へ伝送されるセルを介して、帯域内の（ｉｎ−ｂａｎｄ  ）交換機構１１３０のその対応する第３ステージ・モジュール１１３３へ４ビットのバックプレッシャ状況を各遅延優先順位ごとにひとつずつ供給する。４ビットの情報は、遅延優先順位０からはじまり、遅延優先順位３で終わるように、４つのタイムスロットのコースを通って順次伝送される。出力バックプレッシャ同期ビット（３）は情報に伴う。遅延優先順位「０」が送られた場合、それは「１」に設定される。あるいは、それは「０」に設定される。第１ステージ・モジュールは、着信ＡＴＭセルから２ビットのバックプレッシャ情報をはぎ取り、専用のパスを介して対応する第３ステージ・モジュール１１３３に出力ポート・カード・バックプレッシャ状況の第１ステージ出力側にそって情報を搬送する。入力ポート・カードが交換機構に予定されるセルを持たない場合、ＡＢＭは、交換機構へ遅延優先順位バックプレッシャ情報を運ぶためアイドル・セルを生成する。
【００８９】
本発明の別の実施例にしたがい、全般説明のパラグラフ１で参照された高パフォーマンスのインプリメンテーションについて説明する。付随のルーティング・ビットマップを伴うマルチキャスト・セルは、その入力ポート・ユニットから相互接続リンクをサーブするためにスケジュールに組まれた特定の時間（ひとつもしくはそれ以上のクロック間隔、連続の必要はない）で入力バスに現われる。この指定された時間の間に、セルは、マルチキャスト・ルーティング・ビットマップではなく、そのビットマップにセットされたビットの数の参照カウントで、相互接続交換ユニットのセル・バッファにおけるフリーな位置にコピーされる。コピーと並行して、ビットマップのビットは、ビットマップで識別され且つ内部リンクおよびセルが最終的に運ばれるであろう出力ポート・ユニットと関連するそれらのキューにおける並列キューイング・オペレーションを開始するために用いられる。このようにして並列ハードウエアおよび並行オペレーションを提供することにより、システムの最高スループット要素のクロック速度を減少することができる。
【００９０】
本発明の具体例
本発明のマルチキャスト・ルーティング技術の具体的且つさらに特定したインプリメンテーションが添付の付録に表現されている。付録は、本発明の機能を共に実行する１１の処理マシーンそれぞれについての動作シーケンス（高レベル類似コード・フォーマット）を記述する。その記述の目的により、マシーンは、明確なプログラム・シーケンスにおいて入力から出力まで実行するコントローラとして規定されている。マシーンは、状態レジスタおよび組合せロジックを用いて既知の有限状態マシーンとして実装される。データがさまざまな長さの時間でバッファに記憶される場合、バッファはマシーンに対する出力、そしてその後、入力として機能し、いずれかの側の「シーケンサー」は別の機械としてもっとも容易に理解される。
【００９１】
各マシーンの動作シーケンスについて説明する前に、記述されたマシーンすべてに関する２・３の一般的説明をする。動作シーケンスは、既知の高レベルプログラム制御文（たとえば、ｉｆ、ｔｈｅｎ、ｅｌｓｅなど）を使用する。特別な機能やプログラム文の適用を説明するコメントには、最初に「／／」をつける。たとえば／／これはコメントである。
【００９２】
さまざまなマシーンの操作およびマシーン間のデータの流れは、図１、３、４およびその他の図面を伴い図１１に示された多段ＡＴＭ交換の実施例に特別に関連して記述される。
【００９３】
マシーン１は、すべての入力サブポートで行われる（図１１の入力ポートユニット１１１０のＡＢＭ０からＡＢＭ１７についての）ＡＬＭ入力オペレーションの動作シーケンスを記述する。
【００９４】
マシーン２は、ＡＬＭから受信された各セルごとに（図１１の入力ポート・ユニット１１１０のＡＢＭ０からＡＢＭ１７についての）ＡＢＭ入力バッファの挿入の動作シーケンスを記述する。
【００９５】
マシーン３は、各セルの時間、（図１１の入力ポート・ユニット１１１０のＡＢＭ０からＡＢＭ１７についての）ＡＢＭ入力バッファの取りだし（ｕｎｌｏａｄｉｎｇ）の動作シーケンスを記述する。
【００９６】
マシーン４は、（図３にともに関連して図１１のＡＳＸ入力モジュール０〜５それぞれについての）第１ステージＡＳＸ交換入力バッファの挿入の動作シーケンスを記述する。
【００９７】
マシーン５は、並列キュー・リストすべてについて（それらの４つの優先順位レベルを超えて）（図３にともに関連して図１１のＡＳＸ入力モジュール０〜５それぞれについての）第１ステージＡＳＸ交換入力バッファの取りだしの動作シーケンスを記述する。
【００９８】
マシーン６は、「ランダム」開始点から循環的に、且つその点から「ランダム」な順番に、各入力ポートごとに（図４にともに関連して図１１のＡＸＢクロスバー０〜５それぞれについての）中央ステージＡＸＢクロスバー交換装置の動作シーケンスを記述する。
【００９９】
マシーン７は、ＡＳＸの各出力ポートごとに（図３にともに関連して図１１の各ＡＳＸ出力モジュール０〜５についての）第３ステージＡＳＸ交換出力バッファの挿入の動作シーケンスを記述する。
【０１００】
マシーン８は、ＡＳＸの各出力ポートごとに（図３にともに関連して図１１の各ＡＳＸ出力モジュール０〜５についての）第３ステージＡＳＸ交換出力バッファの取りだしの動作シーケンスを記述する。
【０１０１】
マシーン９は、ＡＳＸ出力モジュールから受け取られたセルごとに（図３にともに関連して図１１の出力ポート・ユニット１１５０のＡＢＭ０からＡＢＭ１７についての）ＡＢＭ出力バッファの挿入の動作シーケンスを記述する。
【０１０２】
マシーン１０は、ラウンド・ロビン・シーケンスにおいて、出力サブポートごとに（図３にともに関連して図１１の出力ポート・ユニット１１５０のＡＢＭ０からＡＢＭ１７についての）ＡＢＭ出力バッファの取りだしの動作シーケンスを記述する。
【０１０３】
マシーン１１は、関連するＡＢＭから使用可能なセルごとに（図３にともに関連して図１１の出力ポート・ユニット１１５０のＡＢＭ０からＡＢＭ１７についての）ＡＬＭ出力の動作シーケンスを記述する。
【０１０４】
これまで説明してきたものは、本発明の原理の適用の具体例に過ぎない。他の構成や方法が、本発明の趣旨および範囲を逸脱することなく当業者により実現されることも可能である。特に、４つの集積回路装置の特定の設定上で分離された特定数の順序マシーンによる記述は、明確にするためのものであり、記述されたオペレーションの原理は、固定あるいはプログラム可能なロジックや適切な性能のプロセッサを用いて他の構成で実現可能である。
【０１０５】
【付録】
0003577188.tif 000006
0003577188.tif 000007
0003577188.tif 000008
0003577188.tif 000009
0003577188.tif 000010
0003577188.tif 000011
0003577188.tif 000012
0003577188.tif 000013
0003577188.tif 000014
0003577188.tif 000015
0003577188.tif 000016
0003577188.tif 000017
0003577188.tif 000018
0003577188.tif 000019
0003577188.tif 000020
0003577188.tif 000021
0003577188.tif 000022
0003577188.tif 000023
0003577188.tif 000024
0003577188.tif 000025
0003577188.tif 000026
0003577188.tif 000027
0003577188.tif 000028
0003577188.tif 000029
0003577188.tif 000030
0003577188.tif 000031
0003577188.tif 000032
0003577188.tif 000033
0003577188.tif 000034
0003577188.tif 000035
0003577188.tif 000036
0003577188.tif 000037
0003577188.tif 000038
0003577188.tif 000039
0003577188.tif 000040
0003577188.tif 000041
0003577188.tif 000042
0003577188.tif 000043
0003577188.tif 000044
0003577188.tif 000045
【図面の簡単な説明】
【図１】本発明に係る単段ＡＴＭ交換機の具体例を示す図である。
【図２】ポート・カードのブロック図である。
【図３】交換モジュールＡＳＸのブロック図である。
【図４】交換ユニットＡＸＢのブロック図である。
【図５】本発明に用いられる標準且つ改良ＡＴＭセルのフォーマットを示す図である。
【図６】ヘッダ翻訳テーブルを示す図である。
【図７】ヘッダ翻訳ルックアップ・テーブルを示す図である。
【図８】ルックアップ・テーブルを用いる２レベルのインデクシングを示す図である。
【図９】本発明のインプリメンテーションで用いられた仮想接続（翻訳）テーブルを示す図である。
【図１０】ＡＢＭメモリを示す図である。
【図１１】３つのタイプのバックプレッシャ機構を用いる多段ＡＴＭ交換機を示す図である。
【図１２】バックプレッシャ・ビットマップの形式を示す図である。
【図１３】バックプレッシャ・ビットマップ具体例を示す図である。
【図１４】本発明の典型的動作シーケンスのフローチャートを示す図である。
【符号の説明】
１００  入力
１１０  入力ポート・ユニット
１２０  内部リンク
１３０  中央相互接続交換ユニット（交換機構）
１４０  内部リンク
１５０  出力ポート・ユニット
１６０  出力
【図１】
0003577188.tif 000046
【図２】
0003577188.tif 000047
【図３】
0003577188.tif 000048
【図４】
0003577188.tif 000049
【図５】
0003577188.tif 000050
【図６】
0003577188.tif 000051
【図７】
0003577188.tif 000052
【図８】
0003577188.tif 000053
【図９】
0003577188.tif 000054
【図１０】
0003577188.tif 000055
【図１１】
0003577188.tif 000056
【図１２】
0003577188.tif 000057
【図１３】
0003577188.tif 000058
【図１４】
0003577188.tif 000059