JPH09130403A - パケット交換装置及び同制御方法 - Google Patents
パケット交換装置及び同制御方法Info
- Publication number
- JPH09130403A JPH09130403A JP23175996A JP23175996A JPH09130403A JP H09130403 A JPH09130403 A JP H09130403A JP 23175996 A JP23175996 A JP 23175996A JP 23175996 A JP23175996 A JP 23175996A JP H09130403 A JPH09130403 A JP H09130403A
- Authority
- JP
- Japan
- Prior art keywords
- output
- controller
- pipe
- packet
- busy
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims description 74
- 238000005266 casting Methods 0.000 claims abstract description 3
- 239000013598 vector Substances 0.000 claims description 85
- 230000015654 memory Effects 0.000 claims description 38
- 238000005096 rolling process Methods 0.000 claims description 29
- 239000004744 fabric Substances 0.000 claims description 28
- 238000012545 processing Methods 0.000 claims description 28
- 238000003860 storage Methods 0.000 claims description 22
- 230000008569 process Effects 0.000 claims description 5
- 210000004027 cell Anatomy 0.000 description 164
- 230000006727 cell loss Effects 0.000 description 48
- 230000006870 function Effects 0.000 description 22
- 238000009826 distribution Methods 0.000 description 21
- 238000013459 approach Methods 0.000 description 19
- 238000010586 diagram Methods 0.000 description 18
- 238000013461 design Methods 0.000 description 11
- 238000004891 communication Methods 0.000 description 10
- 230000006854 communication Effects 0.000 description 10
- 238000003780 insertion Methods 0.000 description 10
- 230000037431 insertion Effects 0.000 description 10
- 230000005540 biological transmission Effects 0.000 description 8
- 238000004458 analytical method Methods 0.000 description 5
- 238000005290 field theory Methods 0.000 description 5
- 230000000903 blocking effect Effects 0.000 description 4
- 230000003111 delayed effect Effects 0.000 description 4
- RGNPBRKPHBKNKX-UHFFFAOYSA-N hexaflumuron Chemical compound C1=C(Cl)C(OC(F)(F)C(F)F)=C(Cl)C=C1NC(=O)NC(=O)C1=C(F)C=CC=C1F RGNPBRKPHBKNKX-UHFFFAOYSA-N 0.000 description 4
- 230000002123 temporal effect Effects 0.000 description 4
- PCTMTFRHKVHKIS-BMFZQQSSSA-N (1s,3r,4e,6e,8e,10e,12e,14e,16e,18s,19r,20r,21s,25r,27r,30r,31r,33s,35r,37s,38r)-3-[(2r,3s,4s,5s,6r)-4-amino-3,5-dihydroxy-6-methyloxan-2-yl]oxy-19,25,27,30,31,33,35,37-octahydroxy-18,20,21-trimethyl-23-oxo-22,39-dioxabicyclo[33.3.1]nonatriaconta-4,6,8,10 Chemical compound C1C=C2C[C@@H](OS(O)(=O)=O)CC[C@]2(C)[C@@H]2[C@@H]1[C@@H]1CC[C@H]([C@H](C)CCCC(C)C)[C@@]1(C)CC2.O[C@H]1[C@@H](N)[C@H](O)[C@@H](C)O[C@H]1O[C@H]1/C=C/C=C/C=C/C=C/C=C/C=C/C=C/[C@H](C)[C@@H](O)[C@@H](C)[C@H](C)OC(=O)C[C@H](O)C[C@H](O)CC[C@@H](O)[C@H](O)C[C@H](O)C[C@](O)(C[C@H](O)[C@H]2C(O)=O)O[C@H]2C1 PCTMTFRHKVHKIS-BMFZQQSSSA-N 0.000 description 3
- 210000004460 N cell Anatomy 0.000 description 3
- 230000009286 beneficial effect Effects 0.000 description 3
- 230000008901 benefit Effects 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 3
- 230000007423 decrease Effects 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000012986 modification Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 240000003537 Ficus benghalensis Species 0.000 description 2
- 230000003139 buffering effect Effects 0.000 description 2
- 230000008859 change Effects 0.000 description 2
- 238000009792 diffusion process Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- XOFYZVNMUHMLCC-ZPOLXVRWSA-N prednisone Chemical compound O=C1C=C[C@]2(C)[C@H]3C(=O)C[C@](C)([C@@](CC4)(O)C(=O)CO)[C@@H]4[C@@H]3CCC2=C1 XOFYZVNMUHMLCC-ZPOLXVRWSA-N 0.000 description 2
- 238000011084 recovery Methods 0.000 description 2
- 238000013341 scale-up Methods 0.000 description 2
- 238000010845 search algorithm Methods 0.000 description 2
- 230000008054 signal transmission Effects 0.000 description 2
- 238000012546 transfer Methods 0.000 description 2
- 238000013519 translation Methods 0.000 description 2
- -1 IJKL Chemical compound 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 238000007906 compression Methods 0.000 description 1
- 230000006835 compression Effects 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000013144 data compression Methods 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 238000000605 extraction Methods 0.000 description 1
- 230000000737 periodic effect Effects 0.000 description 1
- 230000000135 prohibitive effect Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 230000004044 response Effects 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 230000005236 sound signal Effects 0.000 description 1
- 238000013517 stratification Methods 0.000 description 1
- 230000001360 synchronised effect Effects 0.000 description 1
- 230000001052 transient effect Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/02—Details
- H04L12/16—Arrangements for providing special services to substations
- H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
- H04L12/1886—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/10—Packet switching elements characterised by the switching fabric construction
- H04L49/104—Asynchronous transfer mode [ATM] switching fabrics
- H04L49/105—ATM switching elements
- H04L49/106—ATM switching elements using space switching, e.g. crossbar or matrix
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/15—Interconnection of switching modules
- H04L49/1553—Interconnection of ATM switching modules, e.g. ATM switching fabrics
- H04L49/1576—Crossbar or matrix
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/20—Support for services
- H04L49/201—Multicast operation; Broadcast operation
- H04L49/203—ATM switching fabrics with multicast or broadcast capabilities
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/25—Routing or path finding in a switch fabric
- H04L49/253—Routing or path finding in a switch fabric using establishment or release of connections between ports
- H04L49/255—Control mechanisms for ATM switching fabrics
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5679—Arbitration or scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5681—Buffer or queue management
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】
【課題】 パケット交換装置及び同制御方法の改善。
【解決手段】 パケットを少なくとも１個の入力ライン
から複数の出力ラインへ切り換えるためのパケット交換
装置１０Ａが、入力ラインに接続された１個の入力ポー
トと１個の出力ポートとをそれぞれ有する複数の入力イ
ンタフェース１２と、複数の入力ポート１７を複数の出
力ポート１９に切り換えるためのネットワーク１４Ａ
と、複数の出力モジュール１６と、入力ラインからの少
なくとも１個のパケットを多数の出力ラインへマルチキ
ャスティングする帯域外制御器２０とからなり、出力モ
ジュールが共に複数の入力を有し、その入力がそれぞれ
の出力ポートに接続され、共に複数の出力を有し、出力
モジュール出力の各々がそれぞれの出力ラインに接続さ
れ、パイプ１８が各々、複数の入力ラインの各々からの
パスであってそれぞれの出力ラインに接続可能であるよ
うなパスを有する。
から複数の出力ラインへ切り換えるためのパケット交換
装置１０Ａが、入力ラインに接続された１個の入力ポー
トと１個の出力ポートとをそれぞれ有する複数の入力イ
ンタフェース１２と、複数の入力ポート１７を複数の出
力ポート１９に切り換えるためのネットワーク１４Ａ
と、複数の出力モジュール１６と、入力ラインからの少
なくとも１個のパケットを多数の出力ラインへマルチキ
ャスティングする帯域外制御器２０とからなり、出力モ
ジュールが共に複数の入力を有し、その入力がそれぞれ
の出力ポートに接続され、共に複数の出力を有し、出力
モジュール出力の各々がそれぞれの出力ラインに接続さ
れ、パイプ１８が各々、複数の入力ラインの各々からの
パスであってそれぞれの出力ラインに接続可能であるよ
うなパスを有する。
Description
【０００１】
【発明の属する技術分野】本発明は、毎秒１テラビット
レベルの総処理能力で通信するためにデータパケットを
用いる大型電気通信交換装置に関し、詳しくは大型電気
通信交換装置を用いてマルチキャスティングを行うため
の装置及び方法に関する。
レベルの総処理能力で通信するためにデータパケットを
用いる大型電気通信交換装置に関し、詳しくは大型電気
通信交換装置を用いてマルチキャスティングを行うため
の装置及び方法に関する。
【０００２】
【従来の技術】電気通信においては、世界の数百万の電
話音声による呼（音声呼）を扱うために、可聴周波信号
の符号化、多重化、送信、及び復号化に長い間ディジタ
ル交換を用いて来た。音声呼用の電気通信交換装置は需
要に対処するために非常に大きなサイズに成長して来て
いる。
話音声による呼（音声呼）を扱うために、可聴周波信号
の符号化、多重化、送信、及び復号化に長い間ディジタ
ル交換を用いて来た。音声呼用の電気通信交換装置は需
要に対処するために非常に大きなサイズに成長して来て
いる。
【０００３】音声呼トラヒックについての「経路選定に
よる送信」（ルーティング）及び制御を行う交換システ
ムの大方は、回路交換装置と称され、これは、各呼につ
いて発信側当事者（発発呼者）と受信側当事者（被呼
者）との間に一種の双方向可聴回路が設定されることを
意味する。設定される回路は、好ましくないひずみ又は
時間遅れなしに対面会話を模擬（シミュレーション）す
るのに必要な帯域幅及び移送タイミングを有する。
よる送信」（ルーティング）及び制御を行う交換システ
ムの大方は、回路交換装置と称され、これは、各呼につ
いて発信側当事者（発発呼者）と受信側当事者（被呼
者）との間に一種の双方向可聴回路が設定されることを
意味する。設定される回路は、好ましくないひずみ又は
時間遅れなしに対面会話を模擬（シミュレーション）す
るのに必要な帯域幅及び移送タイミングを有する。
【０００４】回路交換に代わる交換としてパケット交換
がある。パケット交換においては、情報の１個以上のパ
ケットへの変換に発呼者が関係する。この情報は、符号
化された音声でも、符号化されたコンピュータデータで
も、又は符号化された映像でもよい。発呼者の番号が一
般にパケットヘッダに含まれ、パケットを宛先へ導く。
がある。パケット交換においては、情報の１個以上のパ
ケットへの変換に発呼者が関係する。この情報は、符号
化された音声でも、符号化されたコンピュータデータで
も、又は符号化された映像でもよい。発呼者の番号が一
般にパケットヘッダに含まれ、パケットを宛先へ導く。
【０００５】パケット交換ネットワークは、各パケット
をそのそれぞれの宛先に過度の遅れなしにルーティング
するというタスクを有する。被呼者は通常、パケットを
受信して情報を適切な形式に復号化するための装置を有
する。
をそのそれぞれの宛先に過度の遅れなしにルーティング
するというタスクを有する。被呼者は通常、パケットを
受信して情報を適切な形式に復号化するための装置を有
する。
【０００６】常に拡張しつつある広範囲の種類にわたる
通信箇所へ音声、コンピュータデータ（ＬＡＮ／ＷＡ
Ｎ）、ファクシミリデータ、画像データ、及び映像デー
タを搬送するパケット交換トラヒックの極めて急速な成
長は、国家情報インフラストラクチャについての諸提案
と共に、パケット交換プロトコル及びシステムアーキテ
クチャの両方に対してチャレンジとなって来た。
通信箇所へ音声、コンピュータデータ（ＬＡＮ／ＷＡ
Ｎ）、ファクシミリデータ、画像データ、及び映像デー
タを搬送するパケット交換トラヒックの極めて急速な成
長は、国家情報インフラストラクチャについての諸提案
と共に、パケット交換プロトコル及びシステムアーキテ
クチャの両方に対してチャレンジとなって来た。
【０００７】パケット交換サービスの普遍的利用を可能
にするような世界標準を定義する仕事に多くの設備供給
業者（ベンダ）及びサービス提供業者（プロバイダ）が
参加している。この協同努力の結果として、最近の非同
期転送モード（ＡＴＭ）規格に基づいて確率論的に分配
された到着率を有するデータパケットを効率よくルーテ
ィングし移送する手段としての、ＡＴＭが急速に開発さ
れ、配置されるようになっている。
にするような世界標準を定義する仕事に多くの設備供給
業者（ベンダ）及びサービス提供業者（プロバイダ）が
参加している。この協同努力の結果として、最近の非同
期転送モード（ＡＴＭ）規格に基づいて確率論的に分配
された到着率を有するデータパケットを効率よくルーテ
ィングし移送する手段としての、ＡＴＭが急速に開発さ
れ、配置されるようになっている。
【０００８】ＡＴＭは、このようにしてパケット志向の
規格となったが、そのデータパケット先行技術の大方
（X.25、フレームリレー、等）と異なり、ＡＴＭはセル
と称される短い、固定長の５３バイトのパケットを用い
る。ＡＴＭは又、先行技術に比して非常に能率化された
形式のエラー回復及び流れ制御手法を用いる。実際に
は、ＡＴＭ規格は本質的にリンクレベルでの大抵のエラ
ー保護及び流れ制御を除去し、これらの機能をネットワ
ークの縁部にあるより高度なレベルのプロトコルに任せ
ている。
規格となったが、そのデータパケット先行技術の大方
（X.25、フレームリレー、等）と異なり、ＡＴＭはセル
と称される短い、固定長の５３バイトのパケットを用い
る。ＡＴＭは又、先行技術に比して非常に能率化された
形式のエラー回復及び流れ制御手法を用いる。実際に
は、ＡＴＭ規格は本質的にリンクレベルでの大抵のエラ
ー保護及び流れ制御を除去し、これらの機能をネットワ
ークの縁部にあるより高度なレベルのプロトコルに任せ
ている。
【０００９】この手法によって、短いセルを、ネットワ
ーク遅れ及びジッタが最小の状態で急速にルーティング
することが可能となり、ＡＴＭが音声、データ、及び映
像のサービスのいずれについても使用可能となる。ＡＴ
Ｍはコンピュータ、ＬＡＮ（特定区域内情報通信網）及
びＷＡＮ（広域情報通信網）産業によって採用されて来
ており、その結果、ソースコンピュータからいくつもの
ＬＡＮ、ＷＡＮ、及び公衆交換ネットワークまでの、継
ぎ目なしのパケット通信が現実のものとなっている。
ーク遅れ及びジッタが最小の状態で急速にルーティング
することが可能となり、ＡＴＭが音声、データ、及び映
像のサービスのいずれについても使用可能となる。ＡＴ
Ｍはコンピュータ、ＬＡＮ（特定区域内情報通信網）及
びＷＡＮ（広域情報通信網）産業によって採用されて来
ており、その結果、ソースコンピュータからいくつもの
ＬＡＮ、ＷＡＮ、及び公衆交換ネットワークまでの、継
ぎ目なしのパケット通信が現実のものとなっている。
【００１０】もしこのレベルの接続性が平均的消費者に
利用可能の場合、そしてもし音声、広帯域データ及び映
像を組み合わせた先進の広帯域サービスが妥当な価格で
同様に利用可能の場合、将来生成されるＡＴＭトラヒッ
クの量は事実上無制限となる。その結果、このＡＴＭパ
ケットトラヒックをルーティングするのに必要な交換装
置及び交差接続の数及びサイズ（大きさ）も又、今後１
０年以内に驚異的な割合で伸びる。
利用可能の場合、そしてもし音声、広帯域データ及び映
像を組み合わせた先進の広帯域サービスが妥当な価格で
同様に利用可能の場合、将来生成されるＡＴＭトラヒッ
クの量は事実上無制限となる。その結果、このＡＴＭパ
ケットトラヒックをルーティングするのに必要な交換装
置及び交差接続の数及びサイズ（大きさ）も又、今後１
０年以内に驚異的な割合で伸びる。
【００１１】長距離及びゲートウェイ通信用のＡＴＭ交
換装置及び交差接続は、総帯域幅として１５５Ｇｂｐｓ
（ギガビット／秒）（ＳＯＮＥＴ ＯＣ−３ １５５Ｍ
ｂｐｓ（メガビット／秒）のレートで１０００個の入
力）から２.４ Ｔｂｐｓ（テラビット／秒）（ＳＯＮＥ
Ｔ ＯＣ−４８の２.４ Ｇｂｐｓのレートで１０００個
の入力）までの範囲の帯域幅を要する。
換装置及び交差接続は、総帯域幅として１５５Ｇｂｐｓ
（ギガビット／秒）（ＳＯＮＥＴ ＯＣ−３ １５５Ｍ
ｂｐｓ（メガビット／秒）のレートで１０００個の入
力）から２.４ Ｔｂｐｓ（テラビット／秒）（ＳＯＮＥ
Ｔ ＯＣ−４８の２.４ Ｇｂｐｓのレートで１０００個
の入力）までの範囲の帯域幅を要する。
【００１２】加えて、もし公衆交換ネットワークを通し
ての家庭及び／又はＬＡＮ／ＷＡＮ接続への広帯域サー
ビスに対する需要が、或る専門家が信じるように、伸び
る場合には、市内電話交換回線会社は、１００Ｇｂｐｓ
（イーサネット１０Ｍｂｐｓレート及び２０％占有率で
５０,０００個の入力）から７７５Ｇｂｐｓ（ＳＯＮＥ
Ｔ ＯＣ−３の１５５Ｇｂｐｓレート及び１０％占有率
で ５０,０００個の入力）までの範囲の総帯域幅を有す
る都市圏ネットワーク（ＭＡＮ）通信用のＡＴＭ交換装
置及び交差接続を要する。
ての家庭及び／又はＬＡＮ／ＷＡＮ接続への広帯域サー
ビスに対する需要が、或る専門家が信じるように、伸び
る場合には、市内電話交換回線会社は、１００Ｇｂｐｓ
（イーサネット１０Ｍｂｐｓレート及び２０％占有率で
５０,０００個の入力）から７７５Ｇｂｐｓ（ＳＯＮＥ
Ｔ ＯＣ−３の１５５Ｇｂｐｓレート及び１０％占有率
で ５０,０００個の入力）までの範囲の総帯域幅を有す
る都市圏ネットワーク（ＭＡＮ）通信用のＡＴＭ交換装
置及び交差接続を要する。
【００１３】必要上、ＡＴＭ用の現在のアーキテクチャ
的研究及びハードウエア／ソフトウエア開発の大部分
は、より近い時点の市場ニーズを満たすようなはるかに
小さな総帯域幅を有する交換装置に集中している。例え
ば、ＬＡＮ／ＷＡＮ社会内での提案の大方は１５０Ｍｂ
ｐｓから１２Ｇｂｐｓまでの範囲の総帯域幅をサポート
するものであり、電気通信社会内での公開された提案の
大部分は２０Ｇｂｐｓから１６０Ｇｂｐｓまでの範囲の
総帯域幅をサポートするものであった。
的研究及びハードウエア／ソフトウエア開発の大部分
は、より近い時点の市場ニーズを満たすようなはるかに
小さな総帯域幅を有する交換装置に集中している。例え
ば、ＬＡＮ／ＷＡＮ社会内での提案の大方は１５０Ｍｂ
ｐｓから１２Ｇｂｐｓまでの範囲の総帯域幅をサポート
するものであり、電気通信社会内での公開された提案の
大部分は２０Ｇｂｐｓから１６０Ｇｂｐｓまでの範囲の
総帯域幅をサポートするものであった。
【００１４】これらのアーキテクチャをより大きなサイ
ズへ拡張した場合は通常、コストの極端に高い、サイズ
の極端に大きい、そして／又は技術に優先する他の制限
から物理的に実現不可能なシステムしか得られない。
ズへ拡張した場合は通常、コストの極端に高い、サイズ
の極端に大きい、そして／又は技術に優先する他の制限
から物理的に実現不可能なシステムしか得られない。
【００１５】例えば、大型で処理能力の高い交換装置の
非常に一般的な設計においては、入力ポートと出力ポー
トとの間に多数のパスを設けるように何段ものリンク
（リンクステージ）によって相互接続された多数の段階
の交換ノード（ノードステージ）から構成された多段相
互接続ネットワークが用いられる。このようなネットワ
ークの例として、クロス、バンヤン及びベネス網があ
る。
非常に一般的な設計においては、入力ポートと出力ポー
トとの間に多数のパスを設けるように何段ものリンク
（リンクステージ）によって相互接続された多数の段階
の交換ノード（ノードステージ）から構成された多段相
互接続ネットワークが用いられる。このようなネットワ
ークの例として、クロス、バンヤン及びベネス網があ
る。
【００１６】多段ネットワークの設計から、非常に高い
性能レベル（閉塞確率が低い、遅れが少ない、障害許容
度が高い、等）が得られ、又システムレベルのコストが
低くなる。その理由は、ネットワークリソース（ノード
及びリンク）が、そのネットワーク内に設定可能な異な
る多数のパスによって時分割利用されるからである。し
かし、パケット持続時間（期間）が非常に短いためＡＴ
Ｍ用の多段ネットワークを物理的に実現することは問題
である。
性能レベル（閉塞確率が低い、遅れが少ない、障害許容
度が高い、等）が得られ、又システムレベルのコストが
低くなる。その理由は、ネットワークリソース（ノード
及びリンク）が、そのネットワーク内に設定可能な異な
る多数のパスによって時分割利用されるからである。し
かし、パケット持続時間（期間）が非常に短いためＡＴ
Ｍ用の多段ネットワークを物理的に実現することは問題
である。
【００１７】大型で処理能力の高いＡＴＭ交換アーキテ
クチャの設計は、結果として得られるＡＴＭ交換装置の
全体性能に大きく影響を及ぼす２つの基本的な問題を扱
う必要がある。これらの問題の第１は、分配ネットワー
クの内部リンク（スイッチングファブリックとも呼称）
（本説明では、交換基本構造）内の閉塞によるセル損失
である。又第２の問題は、同じ時点に交換装置を通過す
る２個以上のＡＴＭセルによる出力ポートについての回
線競合に基づくセル損失である。
クチャの設計は、結果として得られるＡＴＭ交換装置の
全体性能に大きく影響を及ぼす２つの基本的な問題を扱
う必要がある。これらの問題の第１は、分配ネットワー
クの内部リンク（スイッチングファブリックとも呼称）
（本説明では、交換基本構造）内の閉塞によるセル損失
である。又第２の問題は、同じ時点に交換装置を通過す
る２個以上のＡＴＭセルによる出力ポートについての回
線競合に基づくセル損失である。
【００１８】第１の問題は通常、入力ポートと出力ポー
トとの間に多数のパスが存在するように十分な交換基本
構造（ノード及びリンク）を有するネットワークを設計
することによって解決できる。その結果、もし２個以上
のＡＴＭセルが交換基本構造内の同じ共用リソース（ノ
ード及びリンク）を用いようと企てた場合、セルは通
常、内部のネットワーク閉塞問題を除去する２個の別個
のパスを見出すことができる。第２の問題を解決するに
は、交換装置の設計者が、同時に存在するセルの取り扱
い手法を見出して特定する必要がある。
トとの間に多数のパスが存在するように十分な交換基本
構造（ノード及びリンク）を有するネットワークを設計
することによって解決できる。その結果、もし２個以上
のＡＴＭセルが交換基本構造内の同じ共用リソース（ノ
ード及びリンク）を用いようと企てた場合、セルは通
常、内部のネットワーク閉塞問題を除去する２個の別個
のパスを見出すことができる。第２の問題を解決するに
は、交換装置の設計者が、同時に存在するセルの取り扱
い手法を見出して特定する必要がある。
【００１９】同じ出力ポート向けのセルを扱う交換装置
についての一般的な設計手法が、文献（A Growable Pac
ket Switch Arkitecture, IEEE Transactions on Commu
nications, February, 1992, by Eng et al.）及び別の
文献（The Knockout Switch,ISS AT&T Technical Paper
s, 1987, by Yeh et al.） で解析されている。
についての一般的な設計手法が、文献（A Growable Pac
ket Switch Arkitecture, IEEE Transactions on Commu
nications, February, 1992, by Eng et al.）及び別の
文献（The Knockout Switch,ISS AT&T Technical Paper
s, 1987, by Yeh et al.） で解析されている。
【００２０】この一般的設計手法においては、図１に示
すように、交換装置を２個の別個の部分に分割する。す
なわち、Ｎｘ（ＦＮ）分配ネットワーク（Ｎ個の入力ポ
ートを有する）とＫ個のｍｘｎ出力パケットモジュール
からなる出力パケットモジュール群（合計Ｍ＝Ｋｎ個の
出力ポートを有する）である。
すように、交換装置を２個の別個の部分に分割する。す
なわち、Ｎｘ（ＦＮ）分配ネットワーク（Ｎ個の入力ポ
ートを有する）とＫ個のｍｘｎ出力パケットモジュール
からなる出力パケットモジュール群（合計Ｍ＝Ｋｎ個の
出力ポートを有する）である。
【００２１】分配ネットワークから発するリンクの各々
が、或る１個の出力パケットモジュール（又は簡単に、
出力モジュール）への入力のうちの１個の入力において
成端することを要するとの条件が与えられた場合、式Ｆ
Ｎ＝Ｋｍが満足される必要がある。図１の交換基本構造
はメモリを持たないＮｘ（ＦＮ）ファンアウト交換装置
で、その機能は、到着ＡＴＭセルをそのセルの望む出力
ポートに接続された出力モジュール上のｍ個の入力のど
れかにルーティングすることである。
が、或る１個の出力パケットモジュール（又は簡単に、
出力モジュール）への入力のうちの１個の入力において
成端することを要するとの条件が与えられた場合、式Ｆ
Ｎ＝Ｋｍが満足される必要がある。図１の交換基本構造
はメモリを持たないＮｘ（ＦＮ）ファンアウト交換装置
で、その機能は、到着ＡＴＭセルをそのセルの望む出力
ポートに接続された出力モジュール上のｍ個の入力のど
れかにルーティングすることである。
【００２２】出力モジュールは２個以上のセルが特定の
１個の出力ポートについて回路競合する場合に遅らせる
必要があるセルを格納するために利用可能なバッファを
有するｍｘｎ交換装置である。もし到着トラヒックが全
ての出力ポートにわたって均一に分配され、且つもし出
力モジュール内のバッファが十分に大きい場合には、
ｍ：ｎの比率は、ネットワーク内のセル損失確率を、望
まれるセル損失確率レベルのどれよりも低くならせるの
に十分な大きさに常に選定できる。
１個の出力ポートについて回路競合する場合に遅らせる
必要があるセルを格納するために利用可能なバッファを
有するｍｘｎ交換装置である。もし到着トラヒックが全
ての出力ポートにわたって均一に分配され、且つもし出
力モジュール内のバッファが十分に大きい場合には、
ｍ：ｎの比率は、ネットワーク内のセル損失確率を、望
まれるセル損失確率レベルのどれよりも低くならせるの
に十分な大きさに常に選定できる。
【００２３】実際には、もしネットワークのサイズ
（Ｎ）が大きく、且つもしＲが交換装置負荷状態を表す
場合、上記文献のエングほか（Eng et al） によって示
されるようなｍｘｎ出力モジュールを有するネットワー
クのセル損失確率は次式で表される。
（Ｎ）が大きく、且つもしＲが交換装置負荷状態を表す
場合、上記文献のエングほか（Eng et al） によって示
されるようなｍｘｎ出力モジュールを有するネットワー
クのセル損失確率は次式で表される。
【数１】
【００２４】現在のパケット交換装置のセル損失確率が
約１０-12 という受け入れ可能な値なので、現在の装置
の値よりも小さなセル損失確率であれば受け入れ可能と
考えられる。
約１０-12 という受け入れ可能な値なので、現在の装置
の値よりも小さなセル損失確率であれば受け入れ可能と
考えられる。
【００２５】内部での回路競合によるＡＴＭセル損失の
ほかに、Ｎ個のセルの全てが分配ネットワークの入力に
同時に到着するようなＡＴＭパケット交換装置において
は、セルは、次のＮ個のセルからなるセルグループがネ
ットワークの入力ポートに到着する前に、パス探索処理
パイプラインの各ステージによって処理されなければな
らない。
ほかに、Ｎ個のセルの全てが分配ネットワークの入力に
同時に到着するようなＡＴＭパケット交換装置において
は、セルは、次のＮ個のセルからなるセルグループがネ
ットワークの入力ポートに到着する前に、パス探索処理
パイプラインの各ステージによって処理されなければな
らない。
【００２６】例えば、もし着信伝送ラインがＳＯＮＥＴ
ＯＣ−４８の２.５ Ｇｂｐｓレートをサポートする場
合、一緒に到着するＮ個のＡＴＭセルからなるセルグル
ープは、１７６ｎｓ（２.５ Ｇｂｐｓリンク上の１個の
ＡＴＭセルの期間）毎に処理されてパイプライン中の次
のステージに送られなければならない。
ＯＣ−４８の２.５ Ｇｂｐｓレートをサポートする場
合、一緒に到着するＮ個のＡＴＭセルからなるセルグル
ープは、１７６ｎｓ（２.５ Ｇｂｐｓリンク上の１個の
ＡＴＭセルの期間）毎に処理されてパイプライン中の次
のステージに送られなければならない。
【００２７】Ｎの値が大きい場合には、Ｎ個のセルの全
てについてパス探索作業を完了するのにかなりの量の処
理電力（パワー）を要する（注記：もしＮ＝２５６の場
合には毎秒１.４５ｘ１０9回のパス探索を完了しなけれ
ばならず、これは平均処理レート６８４ｐｓ毎に１回の
パス探索実行に相当する）。
てについてパス探索作業を完了するのにかなりの量の処
理電力（パワー）を要する（注記：もしＮ＝２５６の場
合には毎秒１.４５ｘ１０9回のパス探索を完了しなけれ
ばならず、これは平均処理レート６８４ｐｓ毎に１回の
パス探索実行に相当する）。
【００２８】現在の商用マイクロプロセッサは毎秒約１
億個の命令を処理できる。もし各パス探索が命令を１個
だけ取るとした場合には、これらのパス探索を行うのに
少なくとも１５個のマイクロプロセッサがその処理時間
の１００％を消費することになる。したがって、大型の
ＡＴＭパケット交換装置には単一のマイクロプロセッサ
以外のものを基盤とした制御器が必要となる。
億個の命令を処理できる。もし各パス探索が命令を１個
だけ取るとした場合には、これらのパス探索を行うのに
少なくとも１５個のマイクロプロセッサがその処理時間
の１００％を消費することになる。したがって、大型の
ＡＴＭパケット交換装置には単一のマイクロプロセッサ
以外のものを基盤とした制御器が必要となる。
【００２９】
【発明が解決しようとする課題】このパス探索問題を解
決するには２つの手法が考えられる。その第１は、パス
探索に帯域内、すなわち自己ルーティングの制御手法を
用いるものである。上記のクロス、バンヤン及びベネス
ネットワークの多段ネットワークは一般に、帯域内制御
器及び制御手法を用いる。帯域内制御手法においては、
接続要求がＡＴＭセルに仮置き（プリペンド）され、交
換装置を通して、続くＡＴＭペイロードによって用いら
れるのと同じパスに沿ってルーティングされる。
決するには２つの手法が考えられる。その第１は、パス
探索に帯域内、すなわち自己ルーティングの制御手法を
用いるものである。上記のクロス、バンヤン及びベネス
ネットワークの多段ネットワークは一般に、帯域内制御
器及び制御手法を用いる。帯域内制御手法においては、
接続要求がＡＴＭセルに仮置き（プリペンド）され、交
換装置を通して、続くＡＴＭペイロードによって用いら
れるのと同じパスに沿ってルーティングされる。
【００３０】帯域内制御手法では一般に、並行処理要素
をネットワーク内の全てのノードを通して分配すること
が要求されるのでその結果、到着した接続要求及びＡＴ
Ｍセルをどのようにルーティングすべきかを定めるとき
にローカル化されたパス探索作業（そのノードを通過す
るセルについてのみの（パス探索作業）を行うために、
比較的複雑なハードウエアをネットワークの各ノードに
おいて複製設置することになる。
をネットワーク内の全てのノードを通して分配すること
が要求されるのでその結果、到着した接続要求及びＡＴ
Ｍセルをどのようにルーティングすべきかを定めるとき
にローカル化されたパス探索作業（そのノードを通過す
るセルについてのみの（パス探索作業）を行うために、
比較的複雑なハードウエアをネットワークの各ノードに
おいて複製設置することになる。
【００３１】その第２は、帯域外制御器及び帯域外制御
手法を用いるもので、これにより制御器と交換基本構造
とが論理的に分離されるので、結果として得られる制御
信号が交換基本構造に入力されてパスが設定される前
に、パス探索を行う制御器へ接続要求をルーティングす
る必要がある。交換の第２の手法においては、多数のパ
ス探索作業が非常に短い時間内に行われなければならな
いことから、帯域外制御器が上記のような極めて大きい
処理パワーを持つことが要求される。
手法を用いるもので、これにより制御器と交換基本構造
とが論理的に分離されるので、結果として得られる制御
信号が交換基本構造に入力されてパスが設定される前
に、パス探索を行う制御器へ接続要求をルーティングす
る必要がある。交換の第２の手法においては、多数のパ
ス探索作業が非常に短い時間内に行われなければならな
いことから、帯域外制御器が上記のような極めて大きい
処理パワーを持つことが要求される。
【００３２】帯域内制御手法を用いる交換装置内のパス
探索はローカル化されたトラヒック情報だけに基づき、
交換装置トラヒックの全てに関する全体的情報には基づ
いていないので、帯域内制御器が行うルーティングは内
部閉塞に関しては必ずしも最適ではない。その結果、帯
域内制御手法に基づくネットワークは、帯域外制御手法
に基づくより廉価の交換装置と同じ動作特性を得るため
には、より多くの交換基本構造（ステージ及びノード）
を必要とする。
探索はローカル化されたトラヒック情報だけに基づき、
交換装置トラヒックの全てに関する全体的情報には基づ
いていないので、帯域内制御器が行うルーティングは内
部閉塞に関しては必ずしも最適ではない。その結果、帯
域内制御手法に基づくネットワークは、帯域外制御手法
に基づくより廉価の交換装置と同じ動作特性を得るため
には、より多くの交換基本構造（ステージ及びノード）
を必要とする。
【００３３】したがって、各パケットについて最適なパ
ス探索を得るために、全てのパスについての全体的考察
が得られるようなパケット交換装置用制御器の技術が求
められている。
ス探索を得るために、全てのパスについての全体的考察
が得られるようなパケット交換装置用制御器の技術が求
められている。
【００３４】個々のユーザにとっては、探索され使用さ
れるパスは１個の入力から望まれる１個の出力までのパ
スである。これらの１入力から１出力へのユーザにとっ
ては、これらユーザのパケットについて閉塞のないパス
を迅速に且つ効率よく見出すことが重要である。この１
入力から１出力へ通信する機能が用いられるほかに、１
個の入力から多数の出力へ通信する機能が数多く用いら
れている。この動作機能はマルチキャスティングとして
知られている。
れるパスは１個の入力から望まれる１個の出力までのパ
スである。これらの１入力から１出力へのユーザにとっ
ては、これらユーザのパケットについて閉塞のないパス
を迅速に且つ効率よく見出すことが重要である。この１
入力から１出力へ通信する機能が用いられるほかに、１
個の入力から多数の出力へ通信する機能が数多く用いら
れている。この動作機能はマルチキャスティングとして
知られている。
【００３５】マルチキャスティングとは、交換装置が単
一の入力ＡＴＭセルを多数の出力ポートへルーティング
する能力である。マルチキャスティングは、単一のソー
スを多数の宛先へ送信する必要のある用途にとって重要
な機能である。
一の入力ＡＴＭセルを多数の出力ポートへルーティング
する能力である。マルチキャスティングは、単一のソー
スを多数の宛先へ送信する必要のある用途にとって重要
な機能である。
【００３６】この機能の普通の用途としては、有線テレ
ビ（ＣＡＴＶ）のヘッドエンド（信号送出部）内の映像
サーバから特定のテレビショーにチャネルを合わせた家
庭の全てに映像トラヒックを分配する場合の用途が考え
られる。マルチキャスティングは又、電気通信環境にお
ける単一のコンピュータ上の単一ユーザから空間的に分
散する多数のコンピュータ上のユーザへ電子メールのメ
ッセージを分配する場合にも有用である。
ビ（ＣＡＴＶ）のヘッドエンド（信号送出部）内の映像
サーバから特定のテレビショーにチャネルを合わせた家
庭の全てに映像トラヒックを分配する場合の用途が考え
られる。マルチキャスティングは又、電気通信環境にお
ける単一のコンピュータ上の単一ユーザから空間的に分
散する多数のコンピュータ上のユーザへ電子メールのメ
ッセージを分配する場合にも有用である。
【００３７】マルチキャスティングの場合のルーティン
グに必要なプロトコル及び信号フォーマットはＡＴＭ規
格には明確な定義がないが、考え得る手法の１つとして
は、望まれる出力ポートの全てを含むリンクされたリス
トを指す特別ＶＰＩ／ＶＣＩアドレスを用いて出力ポー
トの全てへの接続を設定することをユーザに要求するプ
ロトコルを用いる手法がある。
グに必要なプロトコル及び信号フォーマットはＡＴＭ規
格には明確な定義がないが、考え得る手法の１つとして
は、望まれる出力ポートの全てを含むリンクされたリス
トを指す特別ＶＰＩ／ＶＣＩアドレスを用いて出力ポー
トの全てへの接続を設定することをユーザに要求するプ
ロトコルを用いる手法がある。
【００３８】自己ルーティング制御手法に基づく多くの
ＡＴＭ交換装置においては、よく用いられる選り抜きの
交換装置設計は、マルチキャスティングすべき到着ＡＴ
Ｍセルの多数のコピーをネットワーク内に注入する前
に、入力ラインカードがこれら多数のコピーの作成を行
うような設計である。この既知の設計においては、入力
ラインカードのハードウエアに比較的複雑な追加部分が
必要となる。
ＡＴＭ交換装置においては、よく用いられる選り抜きの
交換装置設計は、マルチキャスティングすべき到着ＡＴ
Ｍセルの多数のコピーをネットワーク内に注入する前
に、入力ラインカードがこれら多数のコピーの作成を行
うような設計である。この既知の設計においては、入力
ラインカードのハードウエアに比較的複雑な追加部分が
必要となる。
【００３９】その理由は単一の入力ＡＴＭセルがＮ個の
出力ポートの全てへの送信を要求するため、各入力ライ
ンカードがＡＴＭセルのコピーをＮ個作成してネットワ
ークに注入する能力を持たなければならないからであ
る。このことが、ラインカードに巨大な重荷を課すこと
になる。
出力ポートの全てへの送信を要求するため、各入力ライ
ンカードがＡＴＭセルのコピーをＮ個作成してネットワ
ークに注入する能力を持たなければならないからであ
る。このことが、ラインカードに巨大な重荷を課すこと
になる。
【００４０】したがって、ラインカードの設計に重荷を
課さずにマルチキャスティングを行うことのできるＡＴ
Ｍ交換装置が求められている。又、単一データセルから
多数の出力へのマルチキャスティングを行うＡＴＭパケ
ット交換装置を制御する分散型の帯域外制御器が求めら
れている。
課さずにマルチキャスティングを行うことのできるＡＴ
Ｍ交換装置が求められている。又、単一データセルから
多数の出力へのマルチキャスティングを行うＡＴＭパケ
ット交換装置を制御する分散型の帯域外制御器が求めら
れている。
【００４１】
【課題を解決するための手段】簡単に述べれば、本発明
の一態様に基づき、次に述べるＡＴＭパケット交換装置
用の分散型帯域外制御器を設けることによって、上記の
問題が克服される。すなわち、１ＡＴＭセル周期分の記
憶装置を有するラインインタフェースと、単一ステージ
の、複雑性を減少させた交換基本構造と、宛先出力ライ
ンが接続された多数の出力モジュールへの送信を可能に
する帯域外制御器と、出力モジュールに接続された各宛
先出力ラインへ望まれるＡＴＭセルのコピーを供給する
出力モジュールとを有するＡＴＭパケット交換装置用の
分散型帯域外制御器である。
の一態様に基づき、次に述べるＡＴＭパケット交換装置
用の分散型帯域外制御器を設けることによって、上記の
問題が克服される。すなわち、１ＡＴＭセル周期分の記
憶装置を有するラインインタフェースと、単一ステージ
の、複雑性を減少させた交換基本構造と、宛先出力ライ
ンが接続された多数の出力モジュールへの送信を可能に
する帯域外制御器と、出力モジュールに接続された各宛
先出力ラインへ望まれるＡＴＭセルのコピーを供給する
出力モジュールとを有するＡＴＭパケット交換装置用の
分散型帯域外制御器である。
【００４２】本発明の別の態様に基づき、マルチキャス
ティング通信パケットの各々について多数のパスを見出
すためのパケット交換装置用の制御器を設けることによ
って、上記の問題が克服される。この制御器は、パケッ
ト交換装置の交換基本構造と出力モジュールとの間の各
接続の使用又は不使用の状態（使用／不使用状態）を格
納するためのメモリを有する。
ティング通信パケットの各々について多数のパスを見出
すためのパケット交換装置用の制御器を設けることによ
って、上記の問題が克服される。この制御器は、パケッ
ト交換装置の交換基本構造と出力モジュールとの間の各
接続の使用又は不使用の状態（使用／不使用状態）を格
納するためのメモリを有する。
【００４３】このメモリは、いくつもの使用又は不使用
の状態のテーブル（使用／不使用状態テーブル）に分割
され、これらの使用／不使用状態テーブルは、、マルチ
キャスティングパケットについての要求されたパスの各
々を迅速に見出すために、同時にアクセスされる。
の状態のテーブル（使用／不使用状態テーブル）に分割
され、これらの使用／不使用状態テーブルは、、マルチ
キャスティングパケットについての要求されたパスの各
々を迅速に見出すために、同時にアクセスされる。
【００４４】本発明の別の態様に基づき、各パイプがい
くつものクロスバー交換機を有するようないくつものパ
イプ、からなる交換基本構造を有するパケット交換装置
のための制御器を設けることによって、上記の問題が克
服される。このパケット交換装置用制御器は、パケット
交換装置の複数の入力ラインのうちの１個の入力ライン
上で受信されたマルチキャスティング電気通信パケット
について複数のパスを見出すための制御器である。
くつものクロスバー交換機を有するようないくつものパ
イプ、からなる交換基本構造を有するパケット交換装置
のための制御器を設けることによって、上記の問題が克
服される。このパケット交換装置用制御器は、パケット
交換装置の複数の入力ラインのうちの１個の入力ライン
上で受信されたマルチキャスティング電気通信パケット
について複数のパスを見出すための制御器である。
【００４５】このパケット交換装置用の制御器は、いく
つものパイプのうちのそれぞれのパイプを各々が制御す
るようないくつものパイプ探索制御器からなる。これら
のパイプ探索制御器（又は簡単に、パイプ制御器）は各
々、複数のクロスバー交換機を有し、これらのクロスバ
ー交換機は各々、連関するそれぞれのクロスバー交換機
制御器を有する。このパケット交換装置制御器は又、使
用中又は不使用中の状態のテーブル（使用中／不使用中
状態テーブル）を格納するための記憶部を有する。
つものパイプのうちのそれぞれのパイプを各々が制御す
るようないくつものパイプ探索制御器からなる。これら
のパイプ探索制御器（又は簡単に、パイプ制御器）は各
々、複数のクロスバー交換機を有し、これらのクロスバ
ー交換機は各々、連関するそれぞれのクロスバー交換機
制御器を有する。このパケット交換装置制御器は又、使
用中又は不使用中の状態のテーブル（使用中／不使用中
状態テーブル）を格納するための記憶部を有する。
【００４６】記憶部内の使用中／不使用中状態テーブル
の各ビットは、それぞれのクロスバー交換機のそれぞれ
の接続に連関し、その接続の動作を制御するためにそれ
ぞれの使用中／不使用中状態ビットを格納する。
の各ビットは、それぞれのクロスバー交換機のそれぞれ
の接続に連関し、その接続の動作を制御するためにそれ
ぞれの使用中／不使用中状態ビットを格納する。
【００４７】更に、パケット交換装置制御器は、マルチ
キャスティングパケットについて同時に接続された１個
以上の出力ラインについて少なくとも１個の出力モジュ
ールへの少なくとも１個のパスを要求するために、使用
中／不使用中状態テーブルの各ビットにアクセスでき
る。したがって、非常に迅速で且つ効率のよいマルチキ
ャスティングパケット作業が可能となる。
キャスティングパケットについて同時に接続された１個
以上の出力ラインについて少なくとも１個の出力モジュ
ールへの少なくとも１個のパスを要求するために、使用
中／不使用中状態テーブルの各ビットにアクセスでき
る。したがって、非常に迅速で且つ効率のよいマルチキ
ャスティングパケット作業が可能となる。
【００４８】
【発明の実施の形態】図２に、大型で汎用のＡＴＭ通信
用交換装置１０（又は簡単に、ＡＴＭ交換装置）をブロ
ック図で示す。ＡＴＭ交換装置１０は、いくつもの入力
インタフェース１２0〜１２N-1、交換基本構造１４、及
びバッファ付き出力パケットモジュール１６0〜１６V-1
（又は簡単に、出力モジュール）を有する。ＡＴＭ動作
において、入力インタフェース１２0〜１２N-1は高速デ
ィジタル増幅器で、交換基本構造１４の多数入力ポート
への入力上で受信された情報をファンアウトするための
適合ネットワーク及び電力増幅器として作用する。
用交換装置１０（又は簡単に、ＡＴＭ交換装置）をブロ
ック図で示す。ＡＴＭ交換装置１０は、いくつもの入力
インタフェース１２0〜１２N-1、交換基本構造１４、及
びバッファ付き出力パケットモジュール１６0〜１６V-1
（又は簡単に、出力モジュール）を有する。ＡＴＭ動作
において、入力インタフェース１２0〜１２N-1は高速デ
ィジタル増幅器で、交換基本構造１４の多数入力ポート
への入力上で受信された情報をファンアウトするための
適合ネットワーク及び電力増幅器として作用する。
【００４９】入力インタフェース１２0〜１２N-1の各々
は又、下で述べるように、１個のＡＴＭセルを格納する
能力を要する。同様にＡＴＭ動作において、バッファ付
き出力モジュール １６0〜１６V-1 は集線装置で、２個
以上のパケットが出力Out0〜OutN-1のうちの同じ出力に
向けられて回線競合する場合にパケット損失を減少させ
るためにバッファ処理が行われる。
は又、下で述べるように、１個のＡＴＭセルを格納する
能力を要する。同様にＡＴＭ動作において、バッファ付
き出力モジュール １６0〜１６V-1 は集線装置で、２個
以上のパケットが出力Out0〜OutN-1のうちの同じ出力に
向けられて回線競合する場合にパケット損失を減少させ
るためにバッファ処理が行われる。
【００５０】交換基本構造１４はファンアウトＦを有
し、ここで入力インタフェース １２0〜１２N-1 からの
出力が各々、交換基本構造１４内でＦ個の入力にファン
アウトされる。すなわち、もしＡＴＭ交換装置１０がＮ
ｘＮ交換装置の場合、交換基本構造１４はＦＮ個の内部
入力と出力モジュール １６0〜１６V-1 へのＦＮ個の出
力とを有する。
し、ここで入力インタフェース １２0〜１２N-1 からの
出力が各々、交換基本構造１４内でＦ個の入力にファン
アウトされる。すなわち、もしＡＴＭ交換装置１０がＮ
ｘＮ交換装置の場合、交換基本構造１４はＦＮ個の内部
入力と出力モジュール １６0〜１６V-1 へのＦＮ個の出
力とを有する。
【００５１】出力モジュール １６0〜１６V-1 は、交換
基本構造１４のＦＮ個の出力をＮ個の出力モジュールの
出力ラインの出力Out0〜OutN-1へ変換するためにファン
イン又は集線ファクタＦを有する。各出力モジュール１
６0〜１６V-1は、到着ＡＴＭを先入れ先出し待ち行列に
格納し、出力ポートが利用可能なときに、これら先入れ
先出し待ち行列の各々の先頭にあるＡＴＭパケットを、
望まれる出力ラインOut0〜OutN-1へルーティングする。
基本構造１４のＦＮ個の出力をＮ個の出力モジュールの
出力ラインの出力Out0〜OutN-1へ変換するためにファン
イン又は集線ファクタＦを有する。各出力モジュール１
６0〜１６V-1は、到着ＡＴＭを先入れ先出し待ち行列に
格納し、出力ポートが利用可能なときに、これら先入れ
先出し待ち行列の各々の先頭にあるＡＴＭパケットを、
望まれる出力ラインOut0〜OutN-1へルーティングする。
【００５２】交換基本構造１４は、その入力ポート１７
0〜１７N-1の各々から出力ポート１９0〜１９N-1の各々
への多数のパスを得るための一般的な分配ネットワーク
で、これは交換装置、具体的にはクロスバー交換機、の
ネットワークである。しかし、Ｎの大きさが３２を超え
ると、交換基本構造の交換構成要素として動作するよう
に単一のクロスバーからＮｘＮ交換装置を形成するのは
極めて非実際的とある。したがって、図２に示す全体的
なアーキテクチャを実現するための別の方法が必要であ
る。
0〜１７N-1の各々から出力ポート１９0〜１９N-1の各々
への多数のパスを得るための一般的な分配ネットワーク
で、これは交換装置、具体的にはクロスバー交換機、の
ネットワークである。しかし、Ｎの大きさが３２を超え
ると、交換基本構造の交換構成要素として動作するよう
に単一のクロスバーからＮｘＮ交換装置を形成するのは
極めて非実際的とある。したがって、図２に示す全体的
なアーキテクチャを実現するための別の方法が必要であ
る。
【００５３】図３に、Ｎのサイズが少なくとも２５６で
あるようなＮ個の入力について実際的且つ可能なＡＴＭ
交換装置１０Ａを示す。閉塞を防止するために各入力ポ
ート１７0〜１７N-1から交換基本構造１４Ａを通して多
数のパスが設けられる。これらの多数のパスは、いくつ
ものグループ（パイプと称する）に分割され、各グルー
プによって、ネットワーク内の各入力ポート１７0〜１
７N-1と各出力ポート１９0〜１９N-1との間に１個だけ
のパスが設けられる。
あるようなＮ個の入力について実際的且つ可能なＡＴＭ
交換装置１０Ａを示す。閉塞を防止するために各入力ポ
ート１７0〜１７N-1から交換基本構造１４Ａを通して多
数のパスが設けられる。これらの多数のパスは、いくつ
ものグループ（パイプと称する）に分割され、各グルー
プによって、ネットワーク内の各入力ポート１７0〜１
７N-1と各出力ポート１９0〜１９N-1との間に１個だけ
のパスが設けられる。
【００５４】すなわち、交換基本構造１４Ａは、多数の
パイプ１８0〜１８L-1から構成される。出力モジュール
１６0〜１６V-1 は本質的に図２に示す出力モジュール
と同じである。
パイプ１８0〜１８L-1から構成される。出力モジュール
１６0〜１６V-1 は本質的に図２に示す出力モジュール
と同じである。
【００５５】本出願と米国において同時継続出願中であ
り共通被譲渡人を有する米国特許出願（名称：TERABIT
PER SECOND PACKET SWITCH, EPC No.95309013.1,出願日
１９９５年１２月１２日）（ここに本出願の参考文献と
する）に見られる交換装置は、単段、メモリなしで非自
己ルーティングのネットワークである。
り共通被譲渡人を有する米国特許出願（名称：TERABIT
PER SECOND PACKET SWITCH, EPC No.95309013.1,出願日
１９９５年１２月１２日）（ここに本出願の参考文献と
する）に見られる交換装置は、単段、メモリなしで非自
己ルーティングのネットワークである。
【００５６】交換基本構造１４Ａは完全ＮｘＮクロスバ
ー交換機のように無条件に非閉塞ではないので、制御器
２０を設けて各ＡＴＭセルについて４個のパイプを通し
て１個のパスを探索するように構成する。パイプ１８0
〜１８3の各々がＡＴＭセルを搬送できるパスを有する
ので、制御器２０の実の目的は未閉塞パスを見出すこと
である。
ー交換機のように無条件に非閉塞ではないので、制御器
２０を設けて各ＡＴＭセルについて４個のパイプを通し
て１個のパスを探索するように構成する。パイプ１８0
〜１８3の各々がＡＴＭセルを搬送できるパスを有する
ので、制御器２０の実の目的は未閉塞パスを見出すこと
である。
【００５７】ＡＴＭ交換装置１０Ａにおいて、もし入力
ラインの数Ｎが２５６に等しく且つもし各入力ラインが
標準の２.５Ｇｂｐｓ のデータレートで稼働する場合に
は、その総処理能力は０.６４０Ｔｂｐｓ となる。この
ようなＡＴＭ交換装置を２倍の５１２個の入力ライン及
び出力ラインを有する交換装置へスケールアップすなわ
ち拡大するのは容易であり、結果として１Ｔｂｐｓより
も大きい総処理能力が得られる。
ラインの数Ｎが２５６に等しく且つもし各入力ラインが
標準の２.５Ｇｂｐｓ のデータレートで稼働する場合に
は、その総処理能力は０.６４０Ｔｂｐｓ となる。この
ようなＡＴＭ交換装置を２倍の５１２個の入力ライン及
び出力ラインを有する交換装置へスケールアップすなわ
ち拡大するのは容易であり、結果として１Ｔｂｐｓより
も大きい総処理能力が得られる。
【００５８】又、１０２４ｘ１０２４のサイズのＡＴＭ
交換装置へのスケールアップは現在の技術の範囲内と考
えられ、商業的に入手可能な構成要素の速度が増加し且
つ新しいより高速の技術が開発されるにつれて、本発明
のアーキテクチャは、更に拡大が可能であることが信じ
られる。
交換装置へのスケールアップは現在の技術の範囲内と考
えられ、商業的に入手可能な構成要素の速度が増加し且
つ新しいより高速の技術が開発されるにつれて、本発明
のアーキテクチャは、更に拡大が可能であることが信じ
られる。
【００５９】図４に、ＡＴＭ交換装置の具体的な実施例
１０Ａを示す。この具体的な実施例において、ＡＴＭ交
換装置１０Ａは２５６個の入力インタフェース１２0〜
１２2 55を有しこれらの入力インタフェースは２５６個
のＡＴＭ入力 In0〜In255 に接続される。入力インタフ
ェースの出力は交換基本構造１４Ａの入力ポート １７0
〜１７N-1 に接続される。
１０Ａを示す。この具体的な実施例において、ＡＴＭ交
換装置１０Ａは２５６個の入力インタフェース１２0〜
１２2 55を有しこれらの入力インタフェースは２５６個
のＡＴＭ入力 In0〜In255 に接続される。入力インタフ
ェースの出力は交換基本構造１４Ａの入力ポート １７0
〜１７N-1 に接続される。
【００６０】交換基本構造１４Ａは合計６４個の１６ｘ
１６クロスバー交換機１５0〜１５6 3 からなり、これら
６４個ののクロスバー交換機は４個のパイプ１８0〜１
８3に分割される。ファンアウトＦは４に等しく、した
がって、もし出力ポートの数がＦＮの場合、出力ポート
は１０２４個 （符号１９0〜１９1023）となる。
１６クロスバー交換機１５0〜１５6 3 からなり、これら
６４個ののクロスバー交換機は４個のパイプ１８0〜１
８3に分割される。ファンアウトＦは４に等しく、した
がって、もし出力ポートの数がＦＮの場合、出力ポート
は１０２４個 （符号１９0〜１９1023）となる。
【００６１】出力ポート１９0〜１９1023 は１６個の６
４ｘ１６出力モジュール １６0〜１６15 の入力にそれ
ぞれ接続される。１６個の６４ｘ１６出力モジュール１
６0〜１６15 は２５６個の出力ラインOut0〜Out255に接
続される。
４ｘ１６出力モジュール １６0〜１６15 の入力にそれ
ぞれ接続される。１６個の６４ｘ１６出力モジュール１
６0〜１６15 は２５６個の出力ラインOut0〜Out255に接
続される。
【００６２】当業者には、構成要素の他の組み合わせを
用いること、例えば図４の６４ｘ１６出力モジュールの
代わりに３２個の３２ｘ８出力モジュールを用いるこ
と、が可能であることが認識されよう。
用いること、例えば図４の６４ｘ１６出力モジュールの
代わりに３２個の３２ｘ８出力モジュールを用いるこ
と、が可能であることが認識されよう。
【００６３】ＡＴＭ交換基本構造１４Ａは又、制御器２
０を備え、制御器２０は、各ＡＴＭパケットについて交
換基本構造１４Ａを通した利用可能なパイプを探索して
見出すタスクを有する。制御器２０は、交換基本構造１
４Ａが４個のパイプに分割され、その結果としてパイプ
探索タスクが４個の並行するパイプ探索タスクに分けら
れるという事実を用いてそのタスクを行う。これら４個
の並行するパイプ探索タスクは各々、受け入れ可能な量
だけ時間的にシフトされる。このような制御器２０の一
実施例を図５に示す。
０を備え、制御器２０は、各ＡＴＭパケットについて交
換基本構造１４Ａを通した利用可能なパイプを探索して
見出すタスクを有する。制御器２０は、交換基本構造１
４Ａが４個のパイプに分割され、その結果としてパイプ
探索タスクが４個の並行するパイプ探索タスクに分けら
れるという事実を用いてそのタスクを行う。これら４個
の並行するパイプ探索タスクは各々、受け入れ可能な量
だけ時間的にシフトされる。このような制御器２０の一
実施例を図５に示す。
【００６４】前に説明し図４及び図５に示した ０.６４
０ＴｂｐｓでＮ＝２５６の実施例において、制御器２０
は約８個の印刷回路基板（ＰＣＢ）上に設けられてい
る。制御器２０は、２５６個までのライン入力インタフ
ェース１２0〜１２255から２５６個までの１６ビット要
求ベクトルを受け入れて、各１７６ｎｓのＡＴＭセル期
間以内にこれらの要求ベクトルの各々についてパス探索
を行い、これにより交換基本構造１４Ａ内に接続を設立
するために用いられる１０２４個の１６ビット接続ベク
トルが生成される。
０ＴｂｐｓでＮ＝２５６の実施例において、制御器２０
は約８個の印刷回路基板（ＰＣＢ）上に設けられてい
る。制御器２０は、２５６個までのライン入力インタフ
ェース１２0〜１２255から２５６個までの１６ビット要
求ベクトルを受け入れて、各１７６ｎｓのＡＴＭセル期
間以内にこれらの要求ベクトルの各々についてパス探索
を行い、これにより交換基本構造１４Ａ内に接続を設立
するために用いられる１０２４個の１６ビット接続ベク
トルが生成される。
【００６５】これには、制御器２０が少なくとも４６Ｍ
ｂｐｓのプロセッサクロックレートで動作することが必
要となる。クロックレートがこのように中位であること
から、制御器２０内の論理回路を既製のＣＭＯＳ ＥＰ
ＬＤ又は類似のデバイスで実現することが可能となり、
したがって制御器２０（個数が多い場合）のコストが非
常に妥当な値となる。
ｂｐｓのプロセッサクロックレートで動作することが必
要となる。クロックレートがこのように中位であること
から、制御器２０内の論理回路を既製のＣＭＯＳ ＥＰ
ＬＤ又は類似のデバイスで実現することが可能となり、
したがって制御器２０（個数が多い場合）のコストが非
常に妥当な値となる。
【００６６】要求ベクトルを入力インタフェース１２0
〜１２255から制御器２０へ移動させること及び接続ベ
クトルを制御器２０から交換基本構造１４Ａのクロスバ
ー交換機１５0〜１５63 へ移動させることはかなり難し
いタスクである。その理由は、大量の制御情報を１７６
ｎｓのＡＴＭセル期間毎に移送する必要があるからであ
る。
〜１２255から制御器２０へ移動させること及び接続ベ
クトルを制御器２０から交換基本構造１４Ａのクロスバ
ー交換機１５0〜１５63 へ移動させることはかなり難し
いタスクである。その理由は、大量の制御情報を１７６
ｎｓのＡＴＭセル期間毎に移送する必要があるからであ
る。
【００６７】例えば、２５６個の入力インタフェースを
有するＡＴＭ交換装置において、２５６個の１６ビット
要求ベクトルを１７６ｎｓ毎に制御器２０に移送して入
力インタフェースサブシステムと制御器２０のサブシス
テムとの間に２３Ｇｂｐｓの総帯域幅を得る必要があ
る。
有するＡＴＭ交換装置において、２５６個の１６ビット
要求ベクトルを１７６ｎｓ毎に制御器２０に移送して入
力インタフェースサブシステムと制御器２０のサブシス
テムとの間に２３Ｇｂｐｓの総帯域幅を得る必要があ
る。
【００６８】加えて、クロスバー交換機１５0〜１５63
を制御するために、１０２４個の１６ビット接続ベクト
ルを１７６ｎｓ毎に交換基本構造１４Ａへ移送する必要
がある。これには、制御器２０のサブシステムと交換基
本構造１４Ａのサブシステムとの間に９３Ｇｂｐｓの総
帯域幅を要する。この９３Ｇｂｐｓの接続ベクトル情報
は、標準の圧縮手法によって２９Ｇｂｐｓに圧縮するこ
とが可能である（各ＡＴＭセル期間中に１個の出力に只
１個の入力だけをルーティングすることができるという
条件で）。
を制御するために、１０２４個の１６ビット接続ベクト
ルを１７６ｎｓ毎に交換基本構造１４Ａへ移送する必要
がある。これには、制御器２０のサブシステムと交換基
本構造１４Ａのサブシステムとの間に９３Ｇｂｐｓの総
帯域幅を要する。この９３Ｇｂｐｓの接続ベクトル情報
は、標準の圧縮手法によって２９Ｇｂｐｓに圧縮するこ
とが可能である（各ＡＴＭセル期間中に１個の出力に只
１個の入力だけをルーティングすることができるという
条件で）。
【００６９】しかし、この制御情報は高い信頼性で送達
する必要があるので、これらのサブシステム間の制御接
続又は制御リンクは二重に冗長でなければならない（図
４には図示しない）。したがって実際には、入力インタ
フェースカードと制御器２０との間には４６Ｇｂｐｓで
データが流れ、制御器２０と交換基本構造４Ａとの間に
は５８Ｇｂｐｓでデータが流れる。望ましくは、この制
御情報の送信には高速直列制御リンク２２が用いられ
る。
する必要があるので、これらのサブシステム間の制御接
続又は制御リンクは二重に冗長でなければならない（図
４には図示しない）。したがって実際には、入力インタ
フェースカードと制御器２０との間には４６Ｇｂｐｓで
データが流れ、制御器２０と交換基本構造４Ａとの間に
は５８Ｇｂｐｓでデータが流れる。望ましくは、この制
御情報の送信には高速直列制御リンク２２が用いられ
る。
【００７０】このような場合、入力インタフェース１２
0〜１２255は４個のグループにグループ化され、それに
より、要求ベクトルを入力インタフェース １２0〜１２
255から制御器２０へ移動させるのに６４個の直列リン
クだけしか必要とせず、又結果として得られる接続ベク
トルを制御器２０からパイプ１８0〜１８3へ移動させる
のに１２８個の直列リンクだけしか必要としない（上記
データ圧縮手法が接続ベクトルにも適用されると仮定し
て）。
0〜１２255は４個のグループにグループ化され、それに
より、要求ベクトルを入力インタフェース １２0〜１２
255から制御器２０へ移動させるのに６４個の直列リン
クだけしか必要とせず、又結果として得られる接続ベク
トルを制御器２０からパイプ１８0〜１８3へ移動させる
のに１２８個の直列リンクだけしか必要としない（上記
データ圧縮手法が接続ベクトルにも適用されると仮定し
て）。
【００７１】帯域外制御手法を用いる場合にはこれら高
速直列制御リンク２２のハードウエアのコストが付加的
にかかるが、これらのリンク２２による全体のシステム
ハードウエアのコスト増加はあまりない。
速直列制御リンク２２のハードウエアのコストが付加的
にかかるが、これらのリンク２２による全体のシステム
ハードウエアのコスト増加はあまりない。
【００７２】図４及び図５の２５６個の入力のＡＴＭ交
換装置１０Ａは、ＡＴＭセルを入力インタフェース１２
0〜１２255と交換基本構造１４Ａとの間でルーティング
するのに必要な１０２４個の高速直列制御リンク２２を
既に有しており（Ｆ＝４のファンアウトを含めた場
合）、又ＡＴＭセルを交換基本構造出力ポート １９0〜
１９1023から出力モジュール １６0〜１６15へルーティ
ングするのに更に１０２４個の高速直列制御リンク２２
が用いられる。
換装置１０Ａは、ＡＴＭセルを入力インタフェース１２
0〜１２255と交換基本構造１４Ａとの間でルーティング
するのに必要な１０２４個の高速直列制御リンク２２を
既に有しており（Ｆ＝４のファンアウトを含めた場
合）、又ＡＴＭセルを交換基本構造出力ポート １９0〜
１９1023から出力モジュール １６0〜１６15へルーティ
ングするのに更に１０２４個の高速直列制御リンク２２
が用いられる。
【００７３】これらのことを考慮すると、制御情報のル
ーティング用に６４個及び１２８個の合計１９２個の高
速直列制御リンク２２を加えても、システム内の高速直
列制御リンクの総数の増加はわずか９％に過ぎない。
ーティング用に６４個及び１２８個の合計１９２個の高
速直列制御リンク２２を加えても、システム内の高速直
列制御リンクの総数の増加はわずか９％に過ぎない。
【００７４】文献（The Knockout Switch） にあるイェ
ーほか（Yeh et al.）の計算を適用すると、図４及び図
５に示すＡＴＭ交換装置１０ＡのＡＴＭセル損失確率は
４.３４ｘ１０-3である。但し、入力の接続は対称であ
り、本出願と米国において同時継続出願中の米国特許出
願（名称：TERABIT PER SECOND PACKET SWITCH, EPCNo.
95309013.1,出願日１９９５年１２月１２日）に設定さ
れているように独立してはいないものと仮定する。この
セル損失確率は、前に述べた受け入れ可能なＡＴＭセル
損失確率の値である１ｘ１０-12 未満には及ばない。
ーほか（Yeh et al.）の計算を適用すると、図４及び図
５に示すＡＴＭ交換装置１０ＡのＡＴＭセル損失確率は
４.３４ｘ１０-3である。但し、入力の接続は対称であ
り、本出願と米国において同時継続出願中の米国特許出
願（名称：TERABIT PER SECOND PACKET SWITCH, EPCNo.
95309013.1,出願日１９９５年１２月１２日）に設定さ
れているように独立してはいないものと仮定する。この
セル損失確率は、前に述べた受け入れ可能なＡＴＭセル
損失確率の値である１ｘ１０-12 未満には及ばない。
【００７５】ＡＴＭセル損失確率を削減するために、制
御器２０は、多くの統計的利点を有し「ローリング」
（延伸）として知られる、時間的拡散手法を用いる。ロ
ーリングは、トラヒック負荷をより均一に分配すること
を目的とする３個の基本的目標に関わりこれらの目標を
達成し満足させるための、負荷を時間的に延伸する手法
である。
御器２０は、多くの統計的利点を有し「ローリング」
（延伸）として知られる、時間的拡散手法を用いる。ロ
ーリングは、トラヒック負荷をより均一に分配すること
を目的とする３個の基本的目標に関わりこれらの目標を
達成し満足させるための、負荷を時間的に延伸する手法
である。
【００７６】これらの目標とは、（１）トラヒックを、
全てのパイプ１８0〜１８3にわたって均一になるように
空間的に分配し、これによって１個のパイプがトラヒッ
ク負荷の比例的な部分だけを搬送するようにすること、
及び（２）トラヒックを、各パイプ１８0〜１８3内の１
６ｘ１６クロスバー交換機の全てにわたって均一になる
ように空間的に分配し、これによってクロスバー交換機
の各々が平等に負荷されるようにすることである。
全てのパイプ１８0〜１８3にわたって均一になるように
空間的に分配し、これによって１個のパイプがトラヒッ
ク負荷の比例的な部分だけを搬送するようにすること、
及び（２）トラヒックを、各パイプ１８0〜１８3内の１
６ｘ１６クロスバー交換機の全てにわたって均一になる
ように空間的に分配し、これによってクロスバー交換機
の各々が平等に負荷されるようにすることである。
【００７７】又第３の目標は（３）与えられたＡＴＭセ
ル期間内に到着するトラヒックを２個のＡＴＭセル期間
にわたって時間的に分配し、これによって非常に高いト
ラヒック量が存在し且つそのトラヒック量が或る１個の
特定の出力モジュール向けであるような特別なＡＴＭセ
ル期間においてトラヒック負荷を効果的に減少させるこ
とができるようにすることである。
ル期間内に到着するトラヒックを２個のＡＴＭセル期間
にわたって時間的に分配し、これによって非常に高いト
ラヒック量が存在し且つそのトラヒック量が或る１個の
特定の出力モジュール向けであるような特別なＡＴＭセ
ル期間においてトラヒック負荷を効果的に減少させるこ
とができるようにすることである。
【００７８】この効果的なトラヒック負荷低減は、混雑
したＡＴＭセル期間の間に到着するＡＴＭセルのうちの
或るものを遅れさせることによって達成される。
したＡＴＭセル期間の間に到着するＡＴＭセルのうちの
或るものを遅れさせることによって達成される。
【００７９】これらのセルは、次に続くＡＴＭセル期間
で今競合対象となっているリソース、すなわち今競合対
象となっている出力モジュールへの接続、に対して競合
するトラヒックの負荷状態がより低くなる確率が最も高
いＡＴＭセル期間まで遅らされ、これによって、これら
遅らされたセルは、次のＡＴＭセル期間においてルーテ
ィングされる確率がより高くなる。
で今競合対象となっているリソース、すなわち今競合対
象となっている出力モジュールへの接続、に対して競合
するトラヒックの負荷状態がより低くなる確率が最も高
いＡＴＭセル期間まで遅らされ、これによって、これら
遅らされたセルは、次のＡＴＭセル期間においてルーテ
ィングされる確率がより高くなる。
【００８０】交換基本構造１４Ａはメモリがないため、
次のＡＴＭセル期間を待たねばならないＡＴＭセルは、
それぞれの入力インタフェース１２0〜１２255に格納さ
れる。
次のＡＴＭセル期間を待たねばならないＡＴＭセルは、
それぞれの入力インタフェース１２0〜１２255に格納さ
れる。
【００８１】負荷分配についてのパケットトラヒック制
御のこれら３個の目標を満足させるほかに又、ローリン
グは次の２個の非常に重要なＡＴＭシステム目標を満足
させる。その第１としての目標（通算４）は、出力モジ
ュール１６0〜１６15 においてＡＴＭストリームが再構
築される際に、たとえストリーム内のＡＴＭセルの或る
ものが他のＡＴＭセルと異なるように遅らされた場合で
もＡＴＭセルの順序が維持されることを、ＡＴＭ交換基
本構造１４Ａが保証しなければならないことである。
御のこれら３個の目標を満足させるほかに又、ローリン
グは次の２個の非常に重要なＡＴＭシステム目標を満足
させる。その第１としての目標（通算４）は、出力モジ
ュール１６0〜１６15 においてＡＴＭストリームが再構
築される際に、たとえストリーム内のＡＴＭセルの或る
ものが他のＡＴＭセルと異なるように遅らされた場合で
もＡＴＭセルの順序が維持されることを、ＡＴＭ交換基
本構造１４Ａが保証しなければならないことである。
【００８２】次に目標（５）は、制御器２０が、各ＡＴ
Ｍセルのその望まれる出力モジュールへの４個のパスの
各々を通してのルーティングを企図するが次に続くパス
探索企図についてはそれらの企図の各々がより軽く負荷
された１６ｘ１６クロスバー交換機において行われるよ
うにすることである。
Ｍセルのその望まれる出力モジュールへの４個のパスの
各々を通してのルーティングを企図するが次に続くパス
探索企図についてはそれらの企図の各々がより軽く負荷
された１６ｘ１６クロスバー交換機において行われるよ
うにすることである。
【００８３】そして、これによって第１の企図が前に多
くのＡＴＭセルがルーティングされた１６ｘ１６クロス
バー交換機において行われ（したがって出力モジュール
への利用可能なパスが極めてわずかしかない）、その一
方、第４すなわち最後のパス探索企図が事実上「空」の
１６ｘ１６クロスバー交換機において行われる（したが
って出力モジュールへの利用可能なパスが多数得られ
る）ようにすることを、ローリング手法が保証しなけれ
ばならないことが目標（５）に含まれる。
くのＡＴＭセルがルーティングされた１６ｘ１６クロス
バー交換機において行われ（したがって出力モジュール
への利用可能なパスが極めてわずかしかない）、その一
方、第４すなわち最後のパス探索企図が事実上「空」の
１６ｘ１６クロスバー交換機において行われる（したが
って出力モジュールへの利用可能なパスが多数得られ
る）ようにすることを、ローリング手法が保証しなけれ
ばならないことが目標（５）に含まれる。
【００８４】ローリング手法は、できるだけ多くの呼を
空間的ネットワークの一部分に詰め込む空間的パス探索
手法に似ている。その手法の場合、システムの或る部分
に１００％に近い占有率を強制することによって、残り
の呼は、もし占有率が１００％より低い場合、システム
の残りの部分を通してのルーティングに成功する確率が
極めて高いという結果となる。したがって、ローリング
手法はその第４すなわち最後のパス探索企図においてＡ
ＴＭセルがルーティングに成功する確率が非常に高い。
空間的ネットワークの一部分に詰め込む空間的パス探索
手法に似ている。その手法の場合、システムの或る部分
に１００％に近い占有率を強制することによって、残り
の呼は、もし占有率が１００％より低い場合、システム
の残りの部分を通してのルーティングに成功する確率が
極めて高いという結果となる。したがって、ローリング
手法はその第４すなわち最後のパス探索企図においてＡ
ＴＭセルがルーティングに成功する確率が非常に高い。
【００８５】目標（５）は、多数のＡＴＭセルをネット
ワークの一部分に詰め込むことから表面的には、トラヒ
ックのネットワークにわたっての空間的分配を求める目
標（１）と矛盾するように見える。しかし、下で述べる
ように、ローリング手法で得られる時間的拡散によっ
て、ネットワークが目標（１）及び（５）の両方を同時
に満足させることが可能となる。
ワークの一部分に詰め込むことから表面的には、トラヒ
ックのネットワークにわたっての空間的分配を求める目
標（１）と矛盾するように見える。しかし、下で述べる
ように、ローリング手法で得られる時間的拡散によっ
て、ネットワークが目標（１）及び（５）の両方を同時
に満足させることが可能となる。
【００８６】図４の２５６個の入力ポート１７0〜１７
255の各々が、分配ネットワークを通してルーティング
する必要のあるＡＴＭセルを有すると仮定し、又交換基
本構造１４Ａが４個のパイプ１８0〜１８3から構成され
ると仮定すると、帯域外制御器２０は、ＡＴＭセルをル
ーティングできるようになる前にＡＴＭセルについて２
５６ｘ４＝１０２４回の独特別個のパス探索を行う必要
がある。
255の各々が、分配ネットワークを通してルーティング
する必要のあるＡＴＭセルを有すると仮定し、又交換基
本構造１４Ａが４個のパイプ１８0〜１８3から構成され
ると仮定すると、帯域外制御器２０は、ＡＴＭセルをル
ーティングできるようになる前にＡＴＭセルについて２
５６ｘ４＝１０２４回の独特別個のパス探索を行う必要
がある。
【００８７】接続を要求する２５６個のＡＴＭセルを４
個のパイプ全てにわたって均一に分配するために、ロー
リング手法では、要求を同じサイズの４個のグループに
分割する。第１のグループは、最初にパイプ１８0 内の
ＡＴＭセルについてパス探索を行い、次にパイプ１８1
内の、更にはパイプ１８2 内の、そして最後にはパイプ
１８3 内の、ＡＴＭセルについてパス探索を行う。
個のパイプ全てにわたって均一に分配するために、ロー
リング手法では、要求を同じサイズの４個のグループに
分割する。第１のグループは、最初にパイプ１８0 内の
ＡＴＭセルについてパス探索を行い、次にパイプ１８1
内の、更にはパイプ１８2 内の、そして最後にはパイプ
１８3 内の、ＡＴＭセルについてパス探索を行う。
【００８８】第２のグループは、最初にパイプ１８1 内
のＡＴＭセルについてパス探索を行い、次にパイプ１８
2 内の、更にはパイプ１８3 内の、そして最後にはパイ
プ１８0 内の、ＡＴＭセルについてパス探索を行う。第
３のグループは、最初にパイプ１８2 内のＡＴＭセルに
ついてパス探索を行い、次にパイプ１８3 内の、更には
パイプ１８0 内の、そして最後にはパイプ１８1 内の、
ＡＴＭセルについてパス探索を行う。
のＡＴＭセルについてパス探索を行い、次にパイプ１８
2 内の、更にはパイプ１８3 内の、そして最後にはパイ
プ１８0 内の、ＡＴＭセルについてパス探索を行う。第
３のグループは、最初にパイプ１８2 内のＡＴＭセルに
ついてパス探索を行い、次にパイプ１８3 内の、更には
パイプ１８0 内の、そして最後にはパイプ１８1 内の、
ＡＴＭセルについてパス探索を行う。
【００８９】第４のグループは、最初にパイプ１８3 内
のＡＴＭセルについてパス探索を行い、次にパイプ１８
0 内の、更にはパイプ１８1 内の、そして最後にはパイ
プ１８2 内の、ＡＴＭセルについてパス探索を行う。こ
の環状のパス探索順序付けによって、ルーティングされ
たＡＴＭセルが４個のパイプの全てにわたって均一に分
配されることが保証される。
のＡＴＭセルについてパス探索を行い、次にパイプ１８
0 内の、更にはパイプ１８1 内の、そして最後にはパイ
プ１８2 内の、ＡＴＭセルについてパス探索を行う。こ
の環状のパス探索順序付けによって、ルーティングされ
たＡＴＭセルが４個のパイプの全てにわたって均一に分
配されることが保証される。
【００９０】加えて、もし４個の同一サイズのグループ
の各グループ内のＡＴＭセルが、単一グループ内のＡＴ
Ｍセルがどの１６ｘ１６クロスバー交換機についてもそ
の１６個の入力のうちの正確に４個の入力へルーティン
グされることが可能なように選択される場合には、ルー
ティングされたＡＴＭセルも又１６ｘ１６クロスバー交
換機の全てにわたって均一に分配される。
の各グループ内のＡＴＭセルが、単一グループ内のＡＴ
Ｍセルがどの１６ｘ１６クロスバー交換機についてもそ
の１６個の入力のうちの正確に４個の入力へルーティン
グされることが可能なように選択される場合には、ルー
ティングされたＡＴＭセルも又１６ｘ１６クロスバー交
換機の全てにわたって均一に分配される。
【００９１】図５及び図６を参照して、本発明に基づく
ローリング手法のタイミング図について説明する。目標
（１）、（２）、及び（５）を同時に満足するために、
帯域外制御器２０によって、目標（３）に述べた時間遅
れ／時間分配が用いられる。目標（３）によって要求さ
れるこれらのＡＴＭセルの遅れは、各ＡＴＭセル期間の
間に与えられる必要がある。
ローリング手法のタイミング図について説明する。目標
（１）、（２）、及び（５）を同時に満足するために、
帯域外制御器２０によって、目標（３）に述べた時間遅
れ／時間分配が用いられる。目標（３）によって要求さ
れるこれらのＡＴＭセルの遅れは、各ＡＴＭセル期間の
間に与えられる必要がある。
【００９２】全ての場合において、或る１個のＡＴＭセ
ルのグループが、制御器２０の環状構造に沿ってパイプ
１８3 からパイプ１８0 へ移送されるときに、制御器２
０が、ＡＴＭセルを１セル期間だけ遅らせる必要のある
次のＡＴＭセル期間へ、セルを割り当てし直す。この割
り当てし直しと遅れとから、各セルグループはその第４
すなわち最後のパス探索において、非常に軽く負荷され
た１６ｘ１６クロスバー交換機のセットに出会うことに
なる。
ルのグループが、制御器２０の環状構造に沿ってパイプ
１８3 からパイプ１８0 へ移送されるときに、制御器２
０が、ＡＴＭセルを１セル期間だけ遅らせる必要のある
次のＡＴＭセル期間へ、セルを割り当てし直す。この割
り当てし直しと遅れとから、各セルグループはその第４
すなわち最後のパス探索において、非常に軽く負荷され
た１６ｘ１６クロスバー交換機のセットに出会うことに
なる。
【００９３】割り当てし直しと遅れとを用いるこのロー
リング手法の別の利点は、これによって、６４個を超え
る同時到着のＡＴＭセルを構造基本構造１４Ａを通して
どの単一出力モジュール１６0〜１６15 へルーティング
することも可能になる点である（交換基本構造１４Ａか
ら各出力モジュール １６0〜１６15へは６４個の接続又
はリンクしかないが）。
リング手法の別の利点は、これによって、６４個を超え
る同時到着のＡＴＭセルを構造基本構造１４Ａを通して
どの単一出力モジュール１６0〜１６15 へルーティング
することも可能になる点である（交換基本構造１４Ａか
ら各出力モジュール １６0〜１６15へは６４個の接続又
はリンクしかないが）。
【００９４】これは、ローリング手法で可能となる。そ
の理由は、ＡＴＭセルの全てを同じＡＴＭセル期間の間
にルーティングする必要がないからである。すなわち、
帯域外制御器２０にローリング手法を用いた場合、極端
にトラヒック負荷の高い過渡的なセル期間においてさえ
も、交換基本構造１４Ａ及び出力モジュール １６0〜１
６15 の両方においてセル損失確率が極めて低いという
結果が得られる。
の理由は、ＡＴＭセルの全てを同じＡＴＭセル期間の間
にルーティングする必要がないからである。すなわち、
帯域外制御器２０にローリング手法を用いた場合、極端
にトラヒック負荷の高い過渡的なセル期間においてさえ
も、交換基本構造１４Ａ及び出力モジュール １６0〜１
６15 の両方においてセル損失確率が極めて低いという
結果が得られる。
【００９５】ＡＴＭセルが交換基本構造１４Ａを通して
ルーティングされる際にこれらＡＴＭセルの或るものに
生じる１ＡＴＭセル期間分の遅れにより、通常は、適切
なセル順序を維持するという目標（４）を満足すること
が困難であるという結論に到達することになる。
ルーティングされる際にこれらＡＴＭセルの或るものに
生じる１ＡＴＭセル期間分の遅れにより、通常は、適切
なセル順序を維持するという目標（４）を満足すること
が困難であるという結論に到達することになる。
【００９６】しかし、帯域外制御器２０におけるパス探
索の環状順序付けにより、ＡＴＭセルストリーム内の遅
れセルが常に、遅れのないセルよりも低い番号のパイプ
を通してルーティングされることが保証される（この場
合、パイプ１８0 が最も低い番号のパイプであり、パイ
プ１８3 が最も高い番号のパイプである）。
索の環状順序付けにより、ＡＴＭセルストリーム内の遅
れセルが常に、遅れのないセルよりも低い番号のパイプ
を通してルーティングされることが保証される（この場
合、パイプ１８0 が最も低い番号のパイプであり、パイ
プ１８3 が最も高い番号のパイプである）。
【００９７】この情報と、ＡＴＭセルの遅れが、最高で
１ＡＴＭセル期間分であるという事実とが相まって、も
しセルが、最も低い番号のパイプから最も高い番号のパ
イプへの順序、すなわちパイプ１８0、 パイプ１８1、
パイプ１８2、 及びパイプ１８3 の順序で交換基本構造
１４Ａから引き出されて出力モジュール１６0〜１６1 5
の各出力モジュールの先入れ先出し待ち行列 １７４0〜
１７４63（図７に示す）に入れられた場合には、適切な
セル順序が維持されることが確実となる。
１ＡＴＭセル期間分であるという事実とが相まって、も
しセルが、最も低い番号のパイプから最も高い番号のパ
イプへの順序、すなわちパイプ１８0、 パイプ１８1、
パイプ１８2、 及びパイプ１８3 の順序で交換基本構造
１４Ａから引き出されて出力モジュール１６0〜１６1 5
の各出力モジュールの先入れ先出し待ち行列 １７４0〜
１７４63（図７に示す）に入れられた場合には、適切な
セル順序が維持されることが確実となる。
【００９８】図７において、出力モジュール１６0 （及
び他の１５個の出力モジュール１６1〜１６15） は、米
国特許第５,４１２,６４６号（名称："ASYNCHRONOUS TR
ANSFER MODE SWITCH ARCHITECTURE"、1995年5月2日Cyr
et al.に発行、本出願の被譲渡人に譲渡）（ここに本出
願の参考文献とする）に述べられている集線装置の６４
ｘ１６型としての実施例である。
び他の１５個の出力モジュール１６1〜１６15） は、米
国特許第５,４１２,６４６号（名称："ASYNCHRONOUS TR
ANSFER MODE SWITCH ARCHITECTURE"、1995年5月2日Cyr
et al.に発行、本出願の被譲渡人に譲渡）（ここに本出
願の参考文献とする）に述べられている集線装置の６４
ｘ１６型としての実施例である。
【００９９】図７の出力モジュール１６0 は、上に引用
したシルほか（Cyr et al.）の特許出願の第４図に示さ
れる汎用集線装置の特定の例である。出力モジュール
１６0〜１６15は上記引用特許出願によく説明されてい
るので、ここでの記述を簡素化するためこれらの出力モ
ジュールについて更に述べることはしない。
したシルほか（Cyr et al.）の特許出願の第４図に示さ
れる汎用集線装置の特定の例である。出力モジュール
１６0〜１６15は上記引用特許出願によく説明されてい
るので、ここでの記述を簡素化するためこれらの出力モ
ジュールについて更に述べることはしない。
【０１００】ローリング手法の方程式について更によく
理解を得るために、遊園地の平面図５００を示す図８を
参照して実生活を例に取った類比説明を行う。多数の来
場者を遊園地の駐車場５１１、５１２、５１３又は５１
４から遊園地５２０へ、来場者の２地点間往復輸送用の
列車を使って輸送することを考える。列車システム５３
０は、予め定められた経路を各々が有する４本の往復輸
送列車から構成される。これは交換基本構造１４Ａの４
個のパイプに類似である。
理解を得るために、遊園地の平面図５００を示す図８を
参照して実生活を例に取った類比説明を行う。多数の来
場者を遊園地の駐車場５１１、５１２、５１３又は５１
４から遊園地５２０へ、来場者の２地点間往復輸送用の
列車を使って輸送することを考える。列車システム５３
０は、予め定められた経路を各々が有する４本の往復輸
送列車から構成される。これは交換基本構造１４Ａの４
個のパイプに類似である。
【０１０１】各列車は１６台の車両（或る１個の特定の
パイプ内の１６ｘ１６クロスバー交換機を表す）から構
成され、各車両は１６個の座席（単一の１６ｘ１６クロ
スバー交換機から発する出力リンクを表す）を備える。
この類比において、各来場者（顧客）（１個のＡＴＭセ
ルを表す）が遊園地５２０を囲む４カ所の駐車場５１
１、５１２、５１３又は５１４に到着する。その結果、
各顧客は即座に４グループの１つに入れられる。駐車場
は同じサイズなので、各グループは平均すれば等しい数
の顧客から構成される。
パイプ内の１６ｘ１６クロスバー交換機を表す）から構
成され、各車両は１６個の座席（単一の１６ｘ１６クロ
スバー交換機から発する出力リンクを表す）を備える。
この類比において、各来場者（顧客）（１個のＡＴＭセ
ルを表す）が遊園地５２０を囲む４カ所の駐車場５１
１、５１２、５１３又は５１４に到着する。その結果、
各顧客は即座に４グループの１つに入れられる。駐車場
は同じサイズなので、各グループは平均すれば等しい数
の顧客から構成される。
【０１０２】それから、どの単一の駐車場５１１、５１
２、５１３又は５１４内の顧客も、分かれて１６個の列
の１つに並ばされる。ここで各列は往復輸送列車のそれ
ぞれの車両に連関する。遊園地５２０は互いに異なる１
６カ所のテーマ区域（過去の国、未来の国、等）に区分
され、特定の車両の１６個の座席の各々には、その座席
に座る顧客が入場できるテーマ区域を示す札が付けられ
ている。
２、５１３又は５１４内の顧客も、分かれて１６個の列
の１つに並ばされる。ここで各列は往復輸送列車のそれ
ぞれの車両に連関する。遊園地５２０は互いに異なる１
６カ所のテーマ区域（過去の国、未来の国、等）に区分
され、特定の車両の１６個の座席の各々には、その座席
に座る顧客が入場できるテーマ区域を示す札が付けられ
ている。
【０１０３】駐車場に到着する前に各顧客は、その日を
過ごしたいテーマ区域１カ所を１６カ所のテーマ区域
（１６個の出力モジュール１６0〜１６15 を表す）から
任意に選択しなければならない。それから顧客は、自分
の駐車場の乗車場５３１、５３２、５３３又は５３４を
通る４本の往復輸送列車のうちの１本の列車上で自分の
望むテーマ区域に連関する利用可能な座席を見出す必要
がある。
過ごしたいテーマ区域１カ所を１６カ所のテーマ区域
（１６個の出力モジュール１６0〜１６15 を表す）から
任意に選択しなければならない。それから顧客は、自分
の駐車場の乗車場５３１、５３２、５３３又は５３４を
通る４本の往復輸送列車のうちの１本の列車上で自分の
望むテーマ区域に連関する利用可能な座席を見出す必要
がある。
【０１０４】もし顧客が、４本の列車が通った後も利用
可能な座席を見出すことができなかった場合には、その
顧客はその日には遊園地に入場できない（このひどい状
態は、分配ネットワークの４個のパイプの全てにおける
閉塞という、小さいが有限の可能性に基づくＡＴＭセル
の損失を表す）。
可能な座席を見出すことができなかった場合には、その
顧客はその日には遊園地に入場できない（このひどい状
態は、分配ネットワークの４個のパイプの全てにおける
閉塞という、小さいが有限の可能性に基づくＡＴＭセル
の損失を表す）。
【０１０５】顧客が乗車を試みることのできる乗車場に
停車する最初の列車は、他の３カ所の駐車場の列車乗車
場を既に通って来ているので、その顧客の予め指定され
た座席は空いていないかもしれない。しかし、もしその
座席がその列車で空いていれば、その列車がその顧客を
まっすぐに遊園地５２０へ届ける。
停車する最初の列車は、他の３カ所の駐車場の列車乗車
場を既に通って来ているので、その顧客の予め指定され
た座席は空いていないかもしれない。しかし、もしその
座席がその列車で空いていれば、その列車がその顧客を
まっすぐに遊園地５２０へ届ける。
【０１０６】もし顧客が最初の列車への乗車に不成功だ
った場合、顧客は第２の列車を待って乗車を試みなけれ
ばならないが、その列車は他の２カ所の駐車場の列車乗
車場を既に通って来ている列車である。もし顧客が第２
の列車上にその顧客の予め指定された座席を見出すこと
ができた場合には、列車は更に１カ所の駐車場の列車乗
車場に停車した後、その顧客を遊園地５２０に届ける。
った場合、顧客は第２の列車を待って乗車を試みなけれ
ばならないが、その列車は他の２カ所の駐車場の列車乗
車場を既に通って来ている列車である。もし顧客が第２
の列車上にその顧客の予め指定された座席を見出すこと
ができた場合には、列車は更に１カ所の駐車場の列車乗
車場に停車した後、その顧客を遊園地５２０に届ける。
【０１０７】もし顧客が最初の列車と第２の列車との両
方に乗車不成功の場合、その顧客は、他の駐車場の列車
乗車場を１カ所だけ通って来る第３の列車を待って乗車
を試みなければならない。もし顧客が第３の列車上にそ
の顧客の予め指定された座席を見出すことができた場合
には、列車は更に２カ所の駐車場の列車乗車場に停車し
た後、その顧客を遊園地５２０に届ける。
方に乗車不成功の場合、その顧客は、他の駐車場の列車
乗車場を１カ所だけ通って来る第３の列車を待って乗車
を試みなければならない。もし顧客が第３の列車上にそ
の顧客の予め指定された座席を見出すことができた場合
には、列車は更に２カ所の駐車場の列車乗車場に停車し
た後、その顧客を遊園地５２０に届ける。
【０１０８】もし顧客がこれら最初の３本の列車のどれ
にも乗車不成功の場合、その顧客は、第４すなわち最後
の列車を待って乗車を試みなければならない。幸いに、
この列車はどの駐車場の乗車場も通って来ていないので
到着する列車は空であり、その顧客の座席は、その顧客
と同じ駐車場の別の顧客が同じ座席を取ろうと試みる場
合にのみ取られることになる。
にも乗車不成功の場合、その顧客は、第４すなわち最後
の列車を待って乗車を試みなければならない。幸いに、
この列車はどの駐車場の乗車場も通って来ていないので
到着する列車は空であり、その顧客の座席は、その顧客
と同じ駐車場の別の顧客が同じ座席を取ろうと試みる場
合にのみ取られることになる。
【０１０９】列車システム５３０は上記の目標（５）を
満足させる。その理由は、引き続いて到着する列車の各
々が前の列車よりも負荷のされかたが軽いからである。
したがって、ＡＴＭセルをローリング（延伸）する制御
器２０は実際、目標（１）、（２）、及び（５）を満足
させることができる。
満足させる。その理由は、引き続いて到着する列車の各
々が前の列車よりも負荷のされかたが軽いからである。
したがって、ＡＴＭセルをローリング（延伸）する制御
器２０は実際、目標（１）、（２）、及び（５）を満足
させることができる。
【０１１０】ローリング手法は、それだけを用いた場
合、ＡＴＭ交換装置１０ＡのＡＴＭセル損失確率を４.
３４ｘ１０-3 から約１０-11 に改善する。ガロアフィ
ールド理論に基づいて交換基本構造１４の入力への独立
した接続を有し且つローリング手法を組み込んだ帯域外
制御器２０を有するＡＴＭ交換装置１０Ａについてのセ
ル損失確率を、文献（"A Growable Packet Switch Arch
itecture"） の解析手法を用いて、解析的にモデル化し
計算することができる。
合、ＡＴＭ交換装置１０ＡのＡＴＭセル損失確率を４.
３４ｘ１０-3 から約１０-11 に改善する。ガロアフィ
ールド理論に基づいて交換基本構造１４の入力への独立
した接続を有し且つローリング手法を組み込んだ帯域外
制御器２０を有するＡＴＭ交換装置１０Ａについてのセ
ル損失確率を、文献（"A Growable Packet Switch Arch
itecture"） の解析手法を用いて、解析的にモデル化し
計算することができる。
【０１１１】パイプ１８0 内の１６ｘ１６クロスバー交
換機の各々が、 Ｒａ＝ＲL／４＋Ｒｒｅｓに等しい与え
られたトラヒック負荷を受ける。ここに、Ｒｒｅｓは、
パイプ１８3 において閉塞され再企図のためパイプ１８
0 にルーティングされる１６ｘ１６クロスバー交換機へ
の１６個の入力の一部分として定義される。
換機の各々が、 Ｒａ＝ＲL／４＋Ｒｒｅｓに等しい与え
られたトラヒック負荷を受ける。ここに、Ｒｒｅｓは、
パイプ１８3 において閉塞され再企図のためパイプ１８
0 にルーティングされる１６ｘ１６クロスバー交換機へ
の１６個の入力の一部分として定義される。
【０１１２】セル損失確率を解決するための最初の企図
において、Ｒｒｅｓ＝ＲL／１６ と仮定する。すると、
パイプ１８0 内の単一１６ｘ１６クロスバー交換機のセ
ル損失確率は、エングほか（Eng et al.）の式を用い
て、次式により定められる。
において、Ｒｒｅｓ＝ＲL／１６ と仮定する。すると、
パイプ１８0 内の単一１６ｘ１６クロスバー交換機のセ
ル損失確率は、エングほか（Eng et al.）の式を用い
て、次式により定められる。
【数２】 ここにｍ＝１、ｎ＝１、そして交換機負荷状態はＲａ＝
ＲL＋／４＋ＲL＋／１６で与えられる。
ＲL＋／４＋ＲL＋／１６で与えられる。
【０１１３】これらの指定事項を用いると、全負荷され
た（ＲL＋＝１.０）パイプ１８0 の１６ｘ１６クロスバ
ー交換機についてのセル損失確率は結果として次式で計
算できる。 Ｐ（パイプ１８0 内のセル損失確率）＝１.３ｘ１０-1
た（ＲL＋＝１.０）パイプ１８0 の１６ｘ１６クロスバ
ー交換機についてのセル損失確率は結果として次式で計
算できる。 Ｐ（パイプ１８0 内のセル損失確率）＝１.３ｘ１０-1
【０１１４】したがって、最初の企図後に第２のパイプ
へ送られる１６ｘ１６クロスバー交換機への１６個の入
力の一部分（ｆ1-2） は次式で与えられる。 ｆ1-2＝ＲａｘＰ（パイプ１８0 内のセル損失確率） ＝（３.１３ｘ１０-1）（１.３ｘ１０-1）＝４.０６ｘ
１０-2
へ送られる１６ｘ１６クロスバー交換機への１６個の入
力の一部分（ｆ1-2） は次式で与えられる。 ｆ1-2＝ＲａｘＰ（パイプ１８0 内のセル損失確率） ＝（３.１３ｘ１０-1）（１.３ｘ１０-1）＝４.０６ｘ
１０-2
【０１１５】対称性から、これはパイプ１８3からパイ
プ１８0へ送られた入力の一部分とも同じであるべき
で、したがって上記の剰余についての仮定ＲL＋／１６
＝０.０６２は正しくない。この仮定を正し、第２の企
図を行うことにより、今はＲｒｅｓ＝ＲL＋／３２ と仮
定する。したがって、パイプ１８0 内の単一の６ｘ６ク
ロスバー交換機のセル損失確率は、前と同様にエングほ
か（Eng et al.）の式を用いｍ＝１、ｎ＝１、そして交
換機負荷状態がＲａ＝ＲL／４＋ＲL／３２として定めら
れる。
プ１８0へ送られた入力の一部分とも同じであるべき
で、したがって上記の剰余についての仮定ＲL＋／１６
＝０.０６２は正しくない。この仮定を正し、第２の企
図を行うことにより、今はＲｒｅｓ＝ＲL＋／３２ と仮
定する。したがって、パイプ１８0 内の単一の６ｘ６ク
ロスバー交換機のセル損失確率は、前と同様にエングほ
か（Eng et al.）の式を用いｍ＝１、ｎ＝１、そして交
換機負荷状態がＲａ＝ＲL／４＋ＲL／３２として定めら
れる。
【０１１６】これらの指定事項を用いると、全負荷され
た（ＲL＝１.０）パイプ１８0 の１６ｘ１６クロスバー
交換機についてのセル損失確率は結果として次式で計算
できる。 Ｐ（パイプ１８0 内のセル損失確率）＝１.２ｘ１０-1
た（ＲL＝１.０）パイプ１８0 の１６ｘ１６クロスバー
交換機についてのセル損失確率は結果として次式で計算
できる。 Ｐ（パイプ１８0 内のセル損失確率）＝１.２ｘ１０-1
【０１１７】したがって、最初の企図後に第２のパイプ
へ送られる１６ｘ１６クロスバー交換機への１６個の入
力の一部分（ｆ1-2） は次式で与えられる。 ｆ1-2＝ＲａｘＰ（パイプ１８0 内のセル損失確率） ＝（２.８１ｘ１０-1）（１.２ｘ１０-1）＝３.３７ｘ
１０-2
へ送られる１６ｘ１６クロスバー交換機への１６個の入
力の一部分（ｆ1-2） は次式で与えられる。 ｆ1-2＝ＲａｘＰ（パイプ１８0 内のセル損失確率） ＝（２.８１ｘ１０-1）（１.２ｘ１０-1）＝３.３７ｘ
１０-2
【０１１８】この計算結果は、仮定値のＲｒｅｓ＝ＲL
／３２ ＝３.１３ｘ１０-2 に非常に近い。したがっ
て、この仮定は適切と考えられる。閉塞されたセルは次
のパス探索のためにパイプ１８1 に送られ、そこでは前
の企図からのＡＴＭセルには無視できる数しか出会わな
い。
／３２ ＝３.１３ｘ１０-2 に非常に近い。したがっ
て、この仮定は適切と考えられる。閉塞されたセルは次
のパス探索のためにパイプ１８1 に送られ、そこでは前
の企図からのＡＴＭセルには無視できる数しか出会わな
い。
【０１１９】したがって、パイプ１８1 内の１６ｘ１６
クロスバー交換機は、成長可能パケット交換装置として
解析用にモデル化でき（ｍ＝１，ｎ＝１、Ｒａ＝
ｆ1-2）、 結果として得られるこのモデルのセル損失確
率は、 １.４ｘ１０-21 である。パケット１８2 へ送ら
れるパケット１８1 内の１６ｘ１６クロスバー交換機へ
の１６個の入力の一部分は、４.２ｘ１０-4 である。
クロスバー交換機は、成長可能パケット交換装置として
解析用にモデル化でき（ｍ＝１，ｎ＝１、Ｒａ＝
ｆ1-2）、 結果として得られるこのモデルのセル損失確
率は、 １.４ｘ１０-21 である。パケット１８2 へ送ら
れるパケット１８1 内の１６ｘ１６クロスバー交換機へ
の１６個の入力の一部分は、４.２ｘ１０-4 である。
【０１２０】同様なアーギュメント（引数）を用いて、
結果として得られる、パイプ１８2へ入るセルについて
のセル損失確率が１.９ｘ１０-4 であり、結果として得
られる、パイプ１８3 へ送られる１６ｘ１６クロスバー
交換機への１６個の入力の一部分が７.９ｘ１０-8 であ
ることを示すことができる。
結果として得られる、パイプ１８2へ入るセルについて
のセル損失確率が１.９ｘ１０-4 であり、結果として得
られる、パイプ１８3 へ送られる１６ｘ１６クロスバー
交換機への１６個の入力の一部分が７.９ｘ１０-8 であ
ることを示すことができる。
【０１２１】結果として得られる、パイプ１８3 内のセ
ル損失確率は３.７ｘ１０-8 であり、結果として得られ
る、パイプ１８3 においてルーティングされない（すな
わち４回のパイプ企図の全てにおいてルーティングされ
ない）１６ｘ１６クロスバー交換機への１６個の入力の
一部分は２.９ｘ１０-15である。
ル損失確率は３.７ｘ１０-8 であり、結果として得られ
る、パイプ１８3 においてルーティングされない（すな
わち４回のパイプ企図の全てにおいてルーティングされ
ない）１６ｘ１６クロスバー交換機への１６個の入力の
一部分は２.９ｘ１０-15である。
【０１２２】したがって、帯域外制御器２０内でローリ
ング手法を用いることによって、その構造基本構造１４
Ａの入力において独立の接続を有するＡＴＭ交換装置１
０ＡのＡＴＭセル損失確率を受け入れ不可能な値の １.
４７ｘ１０-6から受け入れ不可能な値の ２.９ｘ１０
-15 へ減少させることができる。
ング手法を用いることによって、その構造基本構造１４
Ａの入力において独立の接続を有するＡＴＭ交換装置１
０ＡのＡＴＭセル損失確率を受け入れ不可能な値の １.
４７ｘ１０-6から受け入れ不可能な値の ２.９ｘ１０
-15 へ減少させることができる。
【０１２３】上記のローリング手法に関連して選好（プ
レファランス）手法を用いることにより、ＡＴＭ交換装
置１０Ａのセル損失確率が更に減少する。図８の遊園地
の類比に戻って、同じ列内の２人以上の顧客が同じ特定
の座席を要求する場合にこれらの顧客のうちのどの顧客
にその特定の座席を与えるべきかを定めるのに、列車乗
車場において何らかの調停が必要であった。
レファランス）手法を用いることにより、ＡＴＭ交換装
置１０Ａのセル損失確率が更に減少する。図８の遊園地
の類比に戻って、同じ列内の２人以上の顧客が同じ特定
の座席を要求する場合にこれらの顧客のうちのどの顧客
にその特定の座席を与えるべきかを定めるのに、列車乗
車場において何らかの調停が必要であった。
【０１２４】同様に、２個以上の到着ＡＴＭセルが同じ
特定のリンクへのアクセスを要求する場合にこれらのセ
ルのうちのどのセルにその特定のリンクを割り当てるべ
きかを選択するのに、帯域外制御器２０が調停を行う必
要がある。用いられる調停によって、ＡＴＭセル損失確
率に有利な効果を及ぼすことができる。
特定のリンクへのアクセスを要求する場合にこれらのセ
ルのうちのどのセルにその特定のリンクを割り当てるべ
きかを選択するのに、帯域外制御器２０が調停を行う必
要がある。用いられる調停によって、ＡＴＭセル損失確
率に有利な効果を及ぼすことができる。
【０１２５】考え得る調停の１つは、ＡＴＭセルのどれ
にリンクを割り当てるかを任意に定める手法である。こ
の任意選択手法は、上記ローリング手法の分析について
取られた手法である。
にリンクを割り当てるかを任意に定める手法である。こ
の任意選択手法は、上記ローリング手法の分析について
取られた手法である。
【０１２６】しかし、別の調停手法も可能である。有利
な結果をもたらす特定な１つの調停手法は、選好（プレ
ファランス）手法と称される。選好調停手法において
は、特定のグループ化を行って、ＡＴＭセルの各々に選
好重みを割り当てて選好重み付けを行う。そして、２個
以上のセルが同じリンクへのアクセスを要求する場合
に、より高い選好重みを有するＡＴＭセルに、より低い
選好重みを有するＡＴＭセルに対する優先権が与えられ
る。その結果、ＡＴＭセルのグループ構成内に事実上の
階層が形成される。
な結果をもたらす特定な１つの調停手法は、選好（プレ
ファランス）手法と称される。選好調停手法において
は、特定のグループ化を行って、ＡＴＭセルの各々に選
好重みを割り当てて選好重み付けを行う。そして、２個
以上のセルが同じリンクへのアクセスを要求する場合
に、より高い選好重みを有するＡＴＭセルに、より低い
選好重みを有するＡＴＭセルに対する優先権が与えられ
る。その結果、ＡＴＭセルのグループ構成内に事実上の
階層が形成される。
【０１２７】階層の形成は、より高い選好重みを有する
顧客がより低い選好重みを有する顧客よりもよいサービ
スを提供されることから、表面的には好ましくない特性
を交換基本構造１４Ａ内に生成することになるように見
える。
顧客がより低い選好重みを有する顧客よりもよいサービ
スを提供されることから、表面的には好ましくない特性
を交換基本構造１４Ａ内に生成することになるように見
える。
【０１２８】実際、各グループ内で最高の選好重みを有
する顧客は、そのＡＴＭセルを決して他の顧客のＡＴＭ
セルによって阻止閉塞されることがない。これは不公平
に見えるが、この階層形成の影響を詳しく分析すると、
これによってシステムの性能が実際に改善される、すな
わち、選好重みが最も低くて階層の底部に位置する顧客
も含めて全ての顧客について、セル損失確率がより低く
なることが判る。
する顧客は、そのＡＴＭセルを決して他の顧客のＡＴＭ
セルによって阻止閉塞されることがない。これは不公平
に見えるが、この階層形成の影響を詳しく分析すると、
これによってシステムの性能が実際に改善される、すな
わち、選好重みが最も低くて階層の底部に位置する顧客
も含めて全ての顧客について、セル損失確率がより低く
なることが判る。
【０１２９】この分析結果の集約を図９に示す。図９に
おいて、ＡＴＭセルの損失の確率、すなわちセルが利用
可能なパスに割り当てられない確率を、帯域外制御器２
０によって互いに異なるパイプにおいて企図されたパス
探索の回数の関数として示す。この分析において、グル
ープのサイズを４、すなわち４個までのＡＴＭセルが同
じリンクへのアクセスを求めて同時に競合できると仮定
した。その結果、４つの異なる選好重みが割り当てられ
て、各グループに連関する４個の入力ポートについての
階層が形成された。
おいて、ＡＴＭセルの損失の確率、すなわちセルが利用
可能なパスに割り当てられない確率を、帯域外制御器２
０によって互いに異なるパイプにおいて企図されたパス
探索の回数の関数として示す。この分析において、グル
ープのサイズを４、すなわち４個までのＡＴＭセルが同
じリンクへのアクセスを求めて同時に競合できると仮定
した。その結果、４つの異なる選好重みが割り当てられ
て、各グループに連関する４個の入力ポートについての
階層が形成された。
【０１３０】或る１個の特定の入力ポートに連関する選
好重みは、時間と共に変動しない固定定数であると仮定
する。結果として得られた図９の曲線９０１、９０２、
９０３及び９０４によって示されることは、より多くの
パイプにおいてより多くのパス探索が行われるにつれて
セル損失確率が減少することである。しかし、予想され
たように、より低い選好重みを有する入力については
（曲線９０３、９０４）、より高い選好重みを有する入
力（曲線９０１、９０２）よりもセル損失確率が高い。
好重みは、時間と共に変動しない固定定数であると仮定
する。結果として得られた図９の曲線９０１、９０２、
９０３及び９０４によって示されることは、より多くの
パイプにおいてより多くのパス探索が行われるにつれて
セル損失確率が減少することである。しかし、予想され
たように、より低い選好重みを有する入力については
（曲線９０３、９０４）、より高い選好重みを有する入
力（曲線９０１、９０２）よりもセル損失確率が高い。
【０１３１】これらの曲線に重ね合わせて、階層調停手
法の代わりに任意選択調停手法を用いた場合の、パスを
利用できない確率の曲線を符号９１０で示す。予想外の
驚く結果として、互いに異なる４個のパイプについてパ
ス探索が企図された後に任意選択調停手法を用いた場合
には、階層調停手法についてのセル損失確率の平均より
もセル損失確率が高くなることが示された。
法の代わりに任意選択調停手法を用いた場合の、パスを
利用できない確率の曲線を符号９１０で示す。予想外の
驚く結果として、互いに異なる４個のパイプについてパ
ス探索が企図された後に任意選択調停手法を用いた場合
には、階層調停手法についてのセル損失確率の平均より
もセル損失確率が高くなることが示された。
【０１３２】実際、任意選択調停手法の曲線９１０は、
入力ポートの全てについての平均セル損失確率が、階層
調停手法における選好重みの最も低い入力ポートについ
ての平均セル損失確率を示す曲線９０３及び９０４より
も著しく高いことを示している。この現象は、３個の異
なるパイプにおいて３回のパス探索を行った後に、第４
のパイプに入るＡＴＭセル要求の分配が、任意の調停手
法が用いられるか又は選好の調停手法が用いられるかに
よって非常に異なるという事実によって説明できる。
入力ポートの全てについての平均セル損失確率が、階層
調停手法における選好重みの最も低い入力ポートについ
ての平均セル損失確率を示す曲線９０３及び９０４より
も著しく高いことを示している。この現象は、３個の異
なるパイプにおいて３回のパス探索を行った後に、第４
のパイプに入るＡＴＭセル要求の分配が、任意の調停手
法が用いられるか又は選好の調停手法が用いられるかに
よって非常に異なるという事実によって説明できる。
【０１３３】任意の選択調停手法においては、ＡＴＭセ
ルの全てがパスを要求する確率は、小さいが等しい。し
かし、階層調停手法においては、より高い選好重みを有
するＡＴＭセルの大部分がパスを要求する確率は実際上
ゼロである。その一方、最も低い選好重みを有するＡＴ
Ｍセルがパスを要求する確率はかなり高い。その理由
は、その特定のＡＴＭセルが前の３回のパス探索企図の
全てにおいてリンクへのアクセスを拒否されているから
である。
ルの全てがパスを要求する確率は、小さいが等しい。し
かし、階層調停手法においては、より高い選好重みを有
するＡＴＭセルの大部分がパスを要求する確率は実際上
ゼロである。その一方、最も低い選好重みを有するＡＴ
Ｍセルがパスを要求する確率はかなり高い。その理由
は、その特定のＡＴＭセルが前の３回のパス探索企図の
全てにおいてリンクへのアクセスを拒否されているから
である。
【０１３４】しかし、制御器の第４すなわち最後のパス
探索に高い確率で到着する単一の要求においては、低い
確率で到着する多数の要求よりも、ルーティングされる
ＡＴＭセルの数が多い。その理由は、単一の要求の場合
には出力リンクについての競合が生じないので必ず要求
が満足されるからである。
探索に高い確率で到着する単一の要求においては、低い
確率で到着する多数の要求よりも、ルーティングされる
ＡＴＭセルの数が多い。その理由は、単一の要求の場合
には出力リンクについての競合が生じないので必ず要求
が満足されるからである。
【０１３５】その結果、図９の曲線から明らかなよう
に、帯域外制御器２０においてリンク競合を解決してパ
スを定めるために選好重みを入力ポートに割り当てるこ
とにより且つ階層調停手法を用いることにより、交換基
本構造１４Ａの最悪の場合のセル損失確率が、ローリン
グ手法を導入することによって達成された ２.９ｘ１０
-15 から更に低い値の２.４ｘ１０-16へ減少させること
ができる。なお、より高い重みを割り当てられた入力ポ
ートが、図９に示すようにより低いセル損失確率を得て
いることを注記したい。
に、帯域外制御器２０においてリンク競合を解決してパ
スを定めるために選好重みを入力ポートに割り当てるこ
とにより且つ階層調停手法を用いることにより、交換基
本構造１４Ａの最悪の場合のセル損失確率が、ローリン
グ手法を導入することによって達成された ２.９ｘ１０
-15 から更に低い値の２.４ｘ１０-16へ減少させること
ができる。なお、より高い重みを割り当てられた入力ポ
ートが、図９に示すようにより低いセル損失確率を得て
いることを注記したい。
【０１３６】図５に戻って、ローリング及び選好の手法
の物理的実施例を設けるために、ＡＴＭ交換装置１０Ａ
を４個のサブシステムに分割する。これら４個のサブシ
ステムは、入力インタフェース１２0〜１２255と、出力
モジュール １６0〜１６15と、交換基本構造１４Ａと、
帯域外制御器２０とからなる。
の物理的実施例を設けるために、ＡＴＭ交換装置１０Ａ
を４個のサブシステムに分割する。これら４個のサブシ
ステムは、入力インタフェース１２0〜１２255と、出力
モジュール １６0〜１６15と、交換基本構造１４Ａと、
帯域外制御器２０とからなる。
【０１３７】ネットワーク内の入力インタフェース１２
0〜１２255は、到着伝送ラインと交換基本構造１４Ａに
接続されるリンクとの間及び到着伝送ラインと帯域外制
御器２０に接続されるリンクとの間に必要なインタフェ
ース機能を提供する。その結果、入力インタフェース１
２0〜１２255は、入力伝送ラインに成端を用意する必要
がある。
0〜１２255は、到着伝送ラインと交換基本構造１４Ａに
接続されるリンクとの間及び到着伝送ラインと帯域外制
御器２０に接続されるリンクとの間に必要なインタフェ
ース機能を提供する。その結果、入力インタフェース１
２0〜１２255は、入力伝送ラインに成端を用意する必要
がある。
【０１３８】例えばもし入力伝送ラインがＳＯＮＥＴリ
ンクの場合、入力インタフェースは、クロック回復、リ
ンクエラー検出ＳＯＮＥＴポインタ処理及びフレーム描
写、ＡＴＭセル引き出し、及び分配ネットワーク内で到
着ＡＴＭセルをシステムクロックに同期させるための弾
性格納機能、の諸機能を用意しなければならない。
ンクの場合、入力インタフェースは、クロック回復、リ
ンクエラー検出ＳＯＮＥＴポインタ処理及びフレーム描
写、ＡＴＭセル引き出し、及び分配ネットワーク内で到
着ＡＴＭセルをシステムクロックに同期させるための弾
性格納機能、の諸機能を用意しなければならない。
【０１３９】引き出されたＡＴＭセルは、入力インタフ
ェースの先入れ先出し（ＦＩＦＯ）バッファにロードさ
れる。入力インタフェースは又、このＦＩＦＯバッファ
からＡＴＭセルを読んで、セルからＡＴＭヘッダを引き
出す必要がある。それから、各ＡＴＭヘッダのＶＰＩ／
ＶＣＩフィールドが、入力インタフェース上に位置する
翻訳テーブルへのアドレスとして用いられる。
ェースの先入れ先出し（ＦＩＦＯ）バッファにロードさ
れる。入力インタフェースは又、このＦＩＦＯバッファ
からＡＴＭセルを読んで、セルからＡＴＭヘッダを引き
出す必要がある。それから、各ＡＴＭヘッダのＶＰＩ／
ＶＣＩフィールドが、入力インタフェース上に位置する
翻訳テーブルへのアドレスとして用いられる。
【０１４０】翻訳テーブルの出力が、新しいＶＰＩ／Ｖ
ＣＩフィールドと、ＡＴＭセルがルーティングされる先
の出力モジュールのアドレスとを供給する。新しいＶＰ
Ｉ／ＶＣＩフィールドがＡＴＭセル内に、前のＶＰＩ／
ＶＣＩフィールドの入れ替えとして書き込まれ、一方、
出力モジュールのアドレスが要求ベクトルとして、交換
基本構造１４Ａ用の帯域外制御器２０にルーティングさ
れる。
ＣＩフィールドと、ＡＴＭセルがルーティングされる先
の出力モジュールのアドレスとを供給する。新しいＶＰ
Ｉ／ＶＣＩフィールドがＡＴＭセル内に、前のＶＰＩ／
ＶＣＩフィールドの入れ替えとして書き込まれ、一方、
出力モジュールのアドレスが要求ベクトルとして、交換
基本構造１４Ａ用の帯域外制御器２０にルーティングさ
れる。
【０１４１】帯域外制御器２０が要する処理時間量は固
定値なので、入力インタフェースは、入力インタフェー
スがそのパス探索を完了して結果を交換基本構造１４Ａ
に中継し終わるまでそのＡＴＭセルをバッファ内に単に
保持するだけである。
定値なので、入力インタフェースは、入力インタフェー
スがそのパス探索を完了して結果を交換基本構造１４Ａ
に中継し終わるまでそのＡＴＭセルをバッファ内に単に
保持するだけである。
【０１４２】交換基本構造１４ＡにＡＴＭセルを適切に
ルーティングするための新しい設定がロードされると、
入力インタフェースはＡＴＭセルを交換基本構造１４Ａ
に注入することができ、ＡＴＭセルは望む出力モジュー
ル１６0〜１６15 へ交換基本構造１４Ａを通して自動的
にルーティングされる。なお、入力インタフェース１２
0〜１２255は実際には、交換基本構造１４Ａの４個のパ
イプ１８0〜１８3の各々への１個のリンクを与えられ
る。
ルーティングするための新しい設定がロードされると、
入力インタフェースはＡＴＭセルを交換基本構造１４Ａ
に注入することができ、ＡＴＭセルは望む出力モジュー
ル１６0〜１６15 へ交換基本構造１４Ａを通して自動的
にルーティングされる。なお、入力インタフェース１２
0〜１２255は実際には、交換基本構造１４Ａの４個のパ
イプ１８0〜１８3の各々への１個のリンクを与えられ
る。
【０１４３】加えて、交換基本構造１４Ａ内でローリン
グ（延伸）（すなわち時間的拡散）手法を用いるには、
２個の引き続くＡＴＭセル期間のうちの１個の期間の間
に４個のリンクの各々に注入されるべきＡＴＭセルのコ
ピーが必要である。その結果、入力インタフェース１２
0〜１２255におけるタイミングは、ＡＴＭ交換装置１０
Ａ内の他の残りのサブシステムのタイミングと密接に連
結し同期する必要がある。
グ（延伸）（すなわち時間的拡散）手法を用いるには、
２個の引き続くＡＴＭセル期間のうちの１個の期間の間
に４個のリンクの各々に注入されるべきＡＴＭセルのコ
ピーが必要である。その結果、入力インタフェース１２
0〜１２255におけるタイミングは、ＡＴＭ交換装置１０
Ａ内の他の残りのサブシステムのタイミングと密接に連
結し同期する必要がある。
【０１４４】図５の２５６個の入力インタフェース１２
0〜１２255は、０から２５５までのアドレス番号が付け
られるが、各入力インタフェースには又、ＡからＰまで
の英字で与えられる別アドレスが割り当てられる。これ
らの別アドレスは、交換基本構造１４Ａ内のどの入力ポ
ートに入力インタフェースが接続されるかを識別するた
めに用いられる。
0〜１２255は、０から２５５までのアドレス番号が付け
られるが、各入力インタフェースには又、ＡからＰまで
の英字で与えられる別アドレスが割り当てられる。これ
らの別アドレスは、交換基本構造１４Ａ内のどの入力ポ
ートに入力インタフェースが接続されるかを識別するた
めに用いられる。
【０１４５】或る１個の特定の入力インタフェースが接
続される４個のクロスバー交換機からなる実際の交換機
セットは、前に述べたガロアフィールド理論の手法によ
って定められる。これらの手法によって、どのパイプの
どの１６ｘ１６クロスバー交換機上でもその全ての入力
間の独立性が保証される。
続される４個のクロスバー交換機からなる実際の交換機
セットは、前に述べたガロアフィールド理論の手法によ
って定められる。これらの手法によって、どのパイプの
どの１６ｘ１６クロスバー交換機上でもその全ての入力
間の独立性が保証される。
【０１４６】図５の出力モジュール１６0〜１６15 の各
々には、ＡＡからＰＰまでのアドレスが付けられ、各出
力モジュールは、ＡＴＭ交換装置１０Ａ内で重要な機能
を実行する。すなわち、図５の出力モジュール１６0〜
１６15 の各々は、交換基本構造１４Ａから発するそれ
ぞれの６４個のリンクからなるリンクセットのリンクに
成端を用意する。
々には、ＡＡからＰＰまでのアドレスが付けられ、各出
力モジュールは、ＡＴＭ交換装置１０Ａ内で重要な機能
を実行する。すなわち、図５の出力モジュール１６0〜
１６15 の各々は、交換基本構造１４Ａから発するそれ
ぞれの６４個のリンクからなるリンクセットのリンクに
成端を用意する。
【０１４７】各出力モジュール１６0〜１６15 は又、２
つの基本的な機能を行う。第１に各出力モジュールは、
６４個の入力のうちの１個に到着する角ＡＴＭセルを６
個の出力ポートのうちの望む１個へルーティングするた
めに、小程度の空間切換を行う。第２に各出力モジュー
ルは、多数のパイプが同時に同じ出力Out0〜Out255宛に
向けられることに連関する問題に対処するためにＡＴＭ
セルのバッファ処理を行う。
つの基本的な機能を行う。第１に各出力モジュールは、
６４個の入力のうちの１個に到着する角ＡＴＭセルを６
個の出力ポートのうちの望む１個へルーティングするた
めに、小程度の空間切換を行う。第２に各出力モジュー
ルは、多数のパイプが同時に同じ出力Out0〜Out255宛に
向けられることに連関する問題に対処するためにＡＴＭ
セルのバッファ処理を行う。
【０１４８】これらの２つの機能を実現するには数多く
の方法がある。最も簡単率直な方法はたぶん、ＡＴＭセ
ル期間（１７６ｎｓ）の間に６４回のメモリ書き込みと
６４回のメモリ読み出しとを行うことのできる共用のメ
モリスイッチを設けることである。すると、メモリは、
不使用中のメモリの場所を載せた１７番目のリンクされ
たリスト（リンクリスト）と共に、１６個の互いに関連
のないリンクリスト（１個のリストが出力Out0〜Out255
の各々にそれぞれ対応する）として取り扱うことができ
る。
の方法がある。最も簡単率直な方法はたぶん、ＡＴＭセ
ル期間（１７６ｎｓ）の間に６４回のメモリ書き込みと
６４回のメモリ読み出しとを行うことのできる共用のメ
モリスイッチを設けることである。すると、メモリは、
不使用中のメモリの場所を載せた１７番目のリンクされ
たリスト（リンクリスト）と共に、１６個の互いに関連
のないリンクリスト（１個のリストが出力Out0〜Out255
の各々にそれぞれ対応する）として取り扱うことができ
る。
【０１４９】簡単ではあるがこの方法は、１７６ｎｓ毎
に８０回のメモリアクセスを要するので、メモリには
２.２ｎｓ のアクセス時間が要求される。
に８０回のメモリアクセスを要するので、メモリには
２.２ｎｓ のアクセス時間が要求される。
【０１５０】別の方法は、６４ｘ１６出力モジュール１
６0〜１６15 の各々を１個の６４ｘ１６集線装置と１個
の１６ｘ１６共用メモリスイッチとに分割する方法であ
る。この集線装置は、ＡＴＭセル期間毎に６４回の書き
込みと１６回の読み出しとを行うメモリシステムである
が、出力競合問題に要するバッファはこのメモリには設
けられていないため、メモリサイズは小さくてよい（そ
してメモリ速度は速くする）。
６0〜１６15 の各々を１個の６４ｘ１６集線装置と１個
の１６ｘ１６共用メモリスイッチとに分割する方法であ
る。この集線装置は、ＡＴＭセル期間毎に６４回の書き
込みと１６回の読み出しとを行うメモリシステムである
が、出力競合問題に要するバッファはこのメモリには設
けられていないため、メモリサイズは小さくてよい（そ
してメモリ速度は速くする）。
【０１５１】加えて、６４ｘ１６集線装置は、６４個の
別個のメモリチップにわたって拡散された単一のリンク
リストとして実現できる。その結果、各メモリチップ
は、ＡＴＭセル期間毎に１回だけの書き込みと１６回ま
での読み出しとを要するだけである。
別個のメモリチップにわたって拡散された単一のリンク
リストとして実現できる。その結果、各メモリチップ
は、ＡＴＭセル期間毎に１回だけの書き込みと１６回ま
での読み出しとを要するだけである。
【０１５２】１６ｘ１６共用メモリスイッチは、ＡＴＭ
セル期間毎に３２回のメモリアクセスを行うだけである
ので、より遅い（そしてより大きい）メモリを用いるこ
とができ、出力競合問題対処用のバッファ処理は、出力
モジュールのこの共用メモリ部分に持たせることができ
る。
セル期間毎に３２回のメモリアクセスを行うだけである
ので、より遅い（そしてより大きい）メモリを用いるこ
とができ、出力競合問題対処用のバッファ処理は、出力
モジュールのこの共用メモリ部分に持たせることができ
る。
【０１５３】交換基本構造１４Ａは本質的に、帯域外制
御器２０によって生成される制御信号に応動して入力イ
ンタフェースと出力モジュールとの間に必要な接続を設
ける小さな回路スイッチのグループである。図５に示す
ＡＴＭ交換装置１０Ａの実施例において、交換基本構造
１４Ａは、６４個の１６ｘ１６クロスバー交換機からな
り、これらの交換機のうちのそれぞれ１６個の交換機の
グループが１個のパイプを構成する。
御器２０によって生成される制御信号に応動して入力イ
ンタフェースと出力モジュールとの間に必要な接続を設
ける小さな回路スイッチのグループである。図５に示す
ＡＴＭ交換装置１０Ａの実施例において、交換基本構造
１４Ａは、６４個の１６ｘ１６クロスバー交換機からな
り、これらの交換機のうちのそれぞれ１６個の交換機の
グループが１個のパイプを構成する。
【０１５４】４個のパイプは、パイプ１８0、パイプ１
８1、パイプ１８2、及びパイプ １８3 と名付けられ、
或る与えられた１個のパイプ内の１６個の１６ｘ１６ク
ロスバー交換機は、交換機０〜１５と名付けられる。ク
ロスバー交換機は、帯域外制御器２０によって生成され
た制御信号を受信する能力と、引き続くＡＴＭセル間の
保護周波数帯期間中に交換機設定の全てを再構成する能
力とを必要とする。
８1、パイプ１８2、及びパイプ １８3 と名付けられ、
或る与えられた１個のパイプ内の１６個の１６ｘ１６ク
ロスバー交換機は、交換機０〜１５と名付けられる。ク
ロスバー交換機は、帯域外制御器２０によって生成され
た制御信号を受信する能力と、引き続くＡＴＭセル間の
保護周波数帯期間中に交換機設定の全てを再構成する能
力とを必要とする。
【０１５５】各１６ｘ１６クロスバー交換機は、入力Ａ
〜入力Ｐの名を付けられた１６個の入力をサポートし
又、出力ＡＡ〜出力ＰＰの名を付けられた１６個の出力
をサポートする。
〜入力Ｐの名を付けられた１６個の入力をサポートし
又、出力ＡＡ〜出力ＰＰの名を付けられた１６個の出力
をサポートする。
【０１５６】各入力インタフェースが、４個のパイプ１
８0〜１８3の各々における異なる１６ｘ１６クロスバー
交換機に接続されると上に述べたが、パイプ１８0 内の
入力Ｘに接続する入力インタフェースは、他の３個のパ
イプ １８1〜１８3 内の入力Ｘにも同様に接続されるこ
とを注記したい。ここに、Ｘは集合｛Ａ,Ｂ,...,Ｐ｝の
要素である。
８0〜１８3の各々における異なる１６ｘ１６クロスバー
交換機に接続されると上に述べたが、パイプ１８0 内の
入力Ｘに接続する入力インタフェースは、他の３個のパ
イプ １８1〜１８3 内の入力Ｘにも同様に接続されるこ
とを注記したい。ここに、Ｘは集合｛Ａ,Ｂ,...,Ｐ｝の
要素である。
【０１５７】入力インタフェース１２0〜１２255と交換
基本構造１４Ａ内のクロスバー交換機との間の実際の接
続は、上に引用したガロアフィールド理論の手法を用い
て定められる。これらの手法によって、交換基本構造１
４Ａの各パイプ内の交換機におけるルーティングについ
て入力間の独立性が保証される。
基本構造１４Ａ内のクロスバー交換機との間の実際の接
続は、上に引用したガロアフィールド理論の手法を用い
て定められる。これらの手法によって、交換基本構造１
４Ａの各パイプ内の交換機におけるルーティングについ
て入力間の独立性が保証される。
【０１５８】図５は又、６４個のクロスバー交換機の各
々からの出力ＹＹが、ＹＹと名付けた６４ｘ１６出力モ
ジュール上の６４個の入力のうちの１個にルーティング
されることを示す。ここにＹＹは集合｛ＡＡ,ＢＢ,...,
ＰＰ｝の要素である。
々からの出力ＹＹが、ＹＹと名付けた６４ｘ１６出力モ
ジュール上の６４個の入力のうちの１個にルーティング
されることを示す。ここにＹＹは集合｛ＡＡ,ＢＢ,...,
ＰＰ｝の要素である。
【０１５９】交換基本構造１４Ａ用の帯域外制御器２０
の基本的機能は、或る１個の特定のＡＴＭセルが４個の
パイプ１８0〜１８3のうちのどのパイプを通してルーテ
ィングされるかを定めることである。
の基本的機能は、或る１個の特定のＡＴＭセルが４個の
パイプ１８0〜１８3のうちのどのパイプを通してルーテ
ィングされるかを定めることである。
【０１６０】帯域外制御器２０が、ＡＴＭセルが閉塞さ
れることなしにルーティングされるその経路となるパイ
プを定めるのに成功すると、そのパイプを通してパスを
設定するタスクは簡単である。その理由は、パイプを定
義することによって、到着ＡＴＭセルの入力ポートと望
む出力ポートとの間のそのパイプを通してのパスは１個
しか存在しないからである。
れることなしにルーティングされるその経路となるパイ
プを定めるのに成功すると、そのパイプを通してパスを
設定するタスクは簡単である。その理由は、パイプを定
義することによって、到着ＡＴＭセルの入力ポートと望
む出力ポートとの間のそのパイプを通してのパスは１個
しか存在しないからである。
【０１６１】その結果として、交換ネットワークの基本
的なパス探索タスクは本質的に、ＡＴＭ交換装置１０Ａ
内のパイプ探索という、より簡単なタスクに変えられた
ことになる。
的なパス探索タスクは本質的に、ＡＴＭ交換装置１０Ａ
内のパイプ探索という、より簡単なタスクに変えられた
ことになる。
【０１６２】帯域外制御器２０は更に、交換基本構造１
４Ａの１６ｘ１６クロスバー交換機と出力モジュール１
６0〜１６15 との間の中間リンク（ＦＮ）の各々の状態
を、「使用中で利用不可能」又は「不使用中で利用可
能」と特定するために、大型の使用中／不使用中状態テ
ーブルを必要とする。しかし、この大型の使用中／不使
用中状態テーブルは、制御器２０が並行してアクセスで
きるような多数の小さな使用中／不使用中状態テーブル
に分割され、これによって多数のパイプ探索作業が並行
して行われる。
４Ａの１６ｘ１６クロスバー交換機と出力モジュール１
６0〜１６15 との間の中間リンク（ＦＮ）の各々の状態
を、「使用中で利用不可能」又は「不使用中で利用可
能」と特定するために、大型の使用中／不使用中状態テ
ーブルを必要とする。しかし、この大型の使用中／不使
用中状態テーブルは、制御器２０が並行してアクセスで
きるような多数の小さな使用中／不使用中状態テーブル
に分割され、これによって多数のパイプ探索作業が並行
して行われる。
【０１６３】一般的な成長可能パケット交換機を有する
大型の交換装置用の制御器２０を実現するには多くの方
法がある。極端な場合には、パイプ探索を行うのに、４
つのレベルの並行処理が制御器２０のアーキテクチャに
適用される。まず、３つのレベルの並行処理を用いる一
実施例について詳細説明を行い、次に制御器２０用の第
４のレベルの並行処理について述べる。
大型の交換装置用の制御器２０を実現するには多くの方
法がある。極端な場合には、パイプ探索を行うのに、４
つのレベルの並行処理が制御器２０のアーキテクチャに
適用される。まず、３つのレベルの並行処理を用いる一
実施例について詳細説明を行い、次に制御器２０用の第
４のレベルの並行処理について述べる。
【０１６４】第１のレベルの並行処理は、４個のパイプ
１８0〜１８3の各々にそれぞれのパイプ探索制御器２４
0〜２４3を設けることによって得られる。このレベルの
並行処理によって、４個のパイプ探索制御器２４0〜２
４3の全てにおいてパイプ探索を同時に行うことが可能
となる。
１８0〜１８3の各々にそれぞれのパイプ探索制御器２４
0〜２４3を設けることによって得られる。このレベルの
並行処理によって、４個のパイプ探索制御器２４0〜２
４3の全てにおいてパイプ探索を同時に行うことが可能
となる。
【０１６５】第２のレベルの並行処理は、クロスバー交
換機制御器（又は簡単に、交換機制御器） ２６0〜２６
63を各パイプ探索制御器２４0〜２４3内に１６個ずつ設
けることによって得られる。別個独特の個々の交換機制
御器 ２６0〜２６63がそれぞれ交換基本構造１４Ａの各
パイプ内の１６ｘ１６クロスバー交換機の各々に連関す
る。その結果、パイプ探索作業は、各パイプ探索制御器
２４0〜２４3のそれぞれの１６個のパイプ探索制御器の
全てにおいて並行して実行できる。
換機制御器（又は簡単に、交換機制御器） ２６0〜２６
63を各パイプ探索制御器２４0〜２４3内に１６個ずつ設
けることによって得られる。別個独特の個々の交換機制
御器 ２６0〜２６63がそれぞれ交換基本構造１４Ａの各
パイプ内の１６ｘ１６クロスバー交換機の各々に連関す
る。その結果、パイプ探索作業は、各パイプ探索制御器
２４0〜２４3のそれぞれの１６個のパイプ探索制御器の
全てにおいて並行して実行できる。
【０１６６】第３のレベルの並行処理は、交換機制御器
２６0〜２６63の各々に、そのそれぞれの１６ｘ１６ク
ロスバー交換機に接続された１６個の出力リンクの全て
にわたって並行処理を行わせることによって得られる。
２６0〜２６63の各々に、そのそれぞれの１６ｘ１６ク
ロスバー交換機に接続された１６個の出力リンクの全て
にわたって並行処理を行わせることによって得られる。
【０１６７】実際には、交換機制御器 ２６0〜２６63の
各々が、その使用中／不使用中状態メモリから１６個の
使用中／不使用中状態ビットを並行して読み出し、これ
らの１６個のビットに基づいて並行してパイプ探索作業
を行い、それから、結果として得られる１６個の使用中
／不使用中状態ビットをそれぞれの使用中／不使用中状
態メモリに、他の使用中／不使用中状態メモリと並行し
て書き込む。
各々が、その使用中／不使用中状態メモリから１６個の
使用中／不使用中状態ビットを並行して読み出し、これ
らの１６個のビットに基づいて並行してパイプ探索作業
を行い、それから、結果として得られる１６個の使用中
／不使用中状態ビットをそれぞれの使用中／不使用中状
態メモリに、他の使用中／不使用中状態メモリと並行し
て書き込む。
【０１６８】６４個の交換機制御器 ２６0〜２６63を代
表する交換機制御器 ２６0を図１０に示す。１６個の使
用中／不使用中状態ビットの同時処理は、交換機制御器
２６0に１６個の別個のリンク制御器ＡＡ〜ＰＰを設
け、これらのリンク制御器ＡＡ〜ＰＰの各々に、１個の
中間リンクについての、交換基本構造１４Ａ内とそのそ
れぞれの出力モジュールとの間の部分の使用中／不使用
中状態ビットを処理するタスクを割り当てることによっ
て行われる。
表する交換機制御器 ２６0を図１０に示す。１６個の使
用中／不使用中状態ビットの同時処理は、交換機制御器
２６0に１６個の別個のリンク制御器ＡＡ〜ＰＰを設
け、これらのリンク制御器ＡＡ〜ＰＰの各々に、１個の
中間リンクについての、交換基本構造１４Ａ内とそのそ
れぞれの出力モジュールとの間の部分の使用中／不使用
中状態ビットを処理するタスクを割り当てることによっ
て行われる。
【０１６９】図１０に示す実施例において、ＡＴＭ交換
装置１０Ａを制御するのに要する大型の使用中／不使用
中状態メモリが、多数の単一ビットメモリ（使用中／不
使用中状態フリップフロップ）に分割され、これらの単
一ビットの使用中／不使用中状態メモリの各々は、その
それぞれのリンク制御器ＡＡ〜ＰＰに論理的及び物理的
に連関付けられる。
装置１０Ａを制御するのに要する大型の使用中／不使用
中状態メモリが、多数の単一ビットメモリ（使用中／不
使用中状態フリップフロップ）に分割され、これらの単
一ビットの使用中／不使用中状態メモリの各々は、その
それぞれのリンク制御器ＡＡ〜ＰＰに論理的及び物理的
に連関付けられる。
【０１７０】入力インタフェース１２0〜１２255によっ
て生成される要求ベクトルについての全般的なデータの
流れを図５に示す。例えば、図５の入力インタフェース
１２0 がその要求ベクトルを制御接続線２１0 を介して
パイプ探索制御器２４0 にルーティングし、パイプ探索
制御器２４0 において要求ベクトルがパイプ探索リング
（すなわち制御器２０）に挿入される。
て生成される要求ベクトルについての全般的なデータの
流れを図５に示す。例えば、図５の入力インタフェース
１２0 がその要求ベクトルを制御接続線２１0 を介して
パイプ探索制御器２４0 にルーティングし、パイプ探索
制御器２４0 において要求ベクトルがパイプ探索リング
（すなわち制御器２０）に挿入される。
【０１７１】そしてローリング手法から、要求ベクトル
が、リングに沿って循環しながらパイプ探索制御器 ２
４1、パイプ探索制御器 ２４2、及びパイプ探索制御器
２４3を通って環状に移動することが要求される。
が、リングに沿って循環しながらパイプ探索制御器 ２
４1、パイプ探索制御器 ２４2、及びパイプ探索制御器
２４3を通って環状に移動することが要求される。
【０１７２】概して、入力インタフェース１２0〜１２
255の各々が、１個の要求ベクトルを生成し、各要求ベ
クトルは、システム内の出力モジュールの数に等しい数
のビットを有する。したがって、図５の単一の入力イン
タフェースからの要求ベクトルは、１６ビットのデータ
語であり、要求ベクトルの各ビットは、１６個の出力モ
ジュールのうちの１個を指す。
255の各々が、１個の要求ベクトルを生成し、各要求ベ
クトルは、システム内の出力モジュールの数に等しい数
のビットを有する。したがって、図５の単一の入力イン
タフェースからの要求ベクトルは、１６ビットのデータ
語であり、要求ベクトルの各ビットは、１６個の出力モ
ジュールのうちの１個を指す。
【０１７３】もし或る１個の入力インタフェース内のＡ
ＴＭセルがｉ番目の出力モジュール上の出力ポートへの
接続を要求する場合には、要求ベクトル内のビット
「ｉ」は論理値「１」に設定され、要求ベクトル内の他
の全てのビットは論理値「０」に設定される。制御器２
０がこの特定の要求ベクトルを入力インタフェースから
受信した場合、制御器２０は、ソース入力インタフェー
スとｉ番目の出力モジュールとの間にパスが要求されて
いることを識別特定できる。
ＴＭセルがｉ番目の出力モジュール上の出力ポートへの
接続を要求する場合には、要求ベクトル内のビット
「ｉ」は論理値「１」に設定され、要求ベクトル内の他
の全てのビットは論理値「０」に設定される。制御器２
０がこの特定の要求ベクトルを入力インタフェースから
受信した場合、制御器２０は、ソース入力インタフェー
スとｉ番目の出力モジュールとの間にパスが要求されて
いることを識別特定できる。
【０１７４】入力インタフェースからの１６ビットの要
求ベクトル全体がそれぞれの制御接続線２１0〜２１255
を介して４個のパイプ探索制御器２４0〜２４3へルーテ
ィングされ、制御器２０が要求ベクトルを、その特定の
パイプ探索制御器に連関する１６個の交換機制御器のう
ちの１個に挿入する。図１０に示すように、１６ビット
の要求ベクトルが、交換機制御器に注入され、その特定
の交換機制御器内の１６個のリンク制御器全てにわたっ
て分配される。
求ベクトル全体がそれぞれの制御接続線２１0〜２１255
を介して４個のパイプ探索制御器２４0〜２４3へルーテ
ィングされ、制御器２０が要求ベクトルを、その特定の
パイプ探索制御器に連関する１６個の交換機制御器のう
ちの１個に挿入する。図１０に示すように、１６ビット
の要求ベクトルが、交換機制御器に注入され、その特定
の交換機制御器内の１６個のリンク制御器全てにわたっ
て分配される。
【０１７５】各リンク制御器は、クロスバー交換機と出
力モジュールとの間の単一のリンクに連関し、本質的に
要求ベクトルの１６ビットのうちの１ビットを処理す
る。この有限状態機械回路は、単一のリンク制御器に連
関し、１個のフリップフロップ（このリンク制御器のリ
ンクに連関する使用中／不使用中状態ビットを格納する
ために必要とされる単一ビットメモリ）と４個の論理ゲ
ートとからなる（図１１）。
力モジュールとの間の単一のリンクに連関し、本質的に
要求ベクトルの１６ビットのうちの１ビットを処理す
る。この有限状態機械回路は、単一のリンク制御器に連
関し、１個のフリップフロップ（このリンク制御器のリ
ンクに連関する使用中／不使用中状態ビットを格納する
ために必要とされる単一ビットメモリ）と４個の論理ゲ
ートとからなる（図１１）。
【０１７６】リンク制御器作業の状態テーブルの記述例
を図１２に示す。ここで状態変数は、使用中／不使用中
状態ビットによって定義される。リンク制御器ハードウ
エアが、１個の要求ベクトル入力ビット（「要求−入」
と表記）と、１個の要求ベクトル出力ビット（「要求−
出」と表記）と、１個の接続ベクトル出力ビット（「接
続」と表記）とを用意する。
を図１２に示す。ここで状態変数は、使用中／不使用中
状態ビットによって定義される。リンク制御器ハードウ
エアが、１個の要求ベクトル入力ビット（「要求−入」
と表記）と、１個の要求ベクトル出力ビット（「要求−
出」と表記）と、１個の接続ベクトル出力ビット（「接
続」と表記）とを用意する。
【０１７７】要求ベクトル入力ビットは、もし入力がこ
のリンク制御器に連関するリンクを通しての接続を望む
場合には論理値「１」、そうでなければ論理値「０」で
ある。要求ベクトル出力ビットは、もし論理値「１」の
入力要求ベクトルビットがこの特定のリンク制御器によ
って満足されなかった場合には論理値「１」、そうでな
ければ論理値「０」である。
のリンク制御器に連関するリンクを通しての接続を望む
場合には論理値「１」、そうでなければ論理値「０」で
ある。要求ベクトル出力ビットは、もし論理値「１」の
入力要求ベクトルビットがこの特定のリンク制御器によ
って満足されなかった場合には論理値「１」、そうでな
ければ論理値「０」である。
【０１７８】接続ベクトル出力ビットは、もし論理値
「１」の入力要求ベクトルビットがこの特定のリンク制
御器によって満足されず、ＡＴＭセルがこのリンク制御
器に連関するリンクを通してその望む出力モジュールへ
ルーティングされるとの表示がある場合には論理値
「１」、そうでなければ論理値「０」である。
「１」の入力要求ベクトルビットがこの特定のリンク制
御器によって満足されず、ＡＴＭセルがこのリンク制御
器に連関するリンクを通してその望む出力モジュールへ
ルーティングされるとの表示がある場合には論理値
「１」、そうでなければ論理値「０」である。
【０１７９】図１０の使用中／不使用中状態フリップフ
ロップが、各ＡＴＭセルスロット（期間）の開始時に論
理状態値「０」（不使用）の状態にリセットされ、論理
値「１」の要求を持ってリンク制御器に入る最初の要求
ベクトルビットが、リンクに割り当てられ（論理値
「１」の接続ベクトルビットと論理値「０」の出力要求
ベクトルビットとを生成）、使用中／不使用中状態フリ
ップフロップが、論理値「１」（使用中）の状態に設定
される。
ロップが、各ＡＴＭセルスロット（期間）の開始時に論
理状態値「０」（不使用）の状態にリセットされ、論理
値「１」の要求を持ってリンク制御器に入る最初の要求
ベクトルビットが、リンクに割り当てられ（論理値
「１」の接続ベクトルビットと論理値「０」の出力要求
ベクトルビットとを生成）、使用中／不使用中状態フリ
ップフロップが、論理値「１」（使用中）の状態に設定
される。
【０１８０】この特定のＡＴＭセル期間内にリンク制御
器に入る次の要求ベクトルビットはこのリンクを通して
の接続を拒否される（接続ベクトルビット上に論理値
「０」の出力を強制し、入力要求ベクトルビットと同一
の出力要求ビットを生成）。
器に入る次の要求ベクトルビットはこのリンクを通して
の接続を拒否される（接続ベクトルビット上に論理値
「０」の出力を強制し、入力要求ベクトルビットと同一
の出力要求ビットを生成）。
【０１８１】或る単一の交換機制御器を通るいくつかの
互いに続く１６ビットのモノキャスト（非マルチキャス
ティング）要求ベクトルの時間経過に伴う変化を、結果
として得られるその交換機制御器内に格納される使用中
／不使用中状態ビットの状態と共に、図１２に示す。結
果として得られる出力要求ベクトル及び出力接続ベクト
ルが、パイプ探索制御器 ２４0〜２４3 の各々の全般的
動作を示している。
互いに続く１６ビットのモノキャスト（非マルチキャス
ティング）要求ベクトルの時間経過に伴う変化を、結果
として得られるその交換機制御器内に格納される使用中
／不使用中状態ビットの状態と共に、図１２に示す。結
果として得られる出力要求ベクトル及び出力接続ベクト
ルが、パイプ探索制御器 ２４0〜２４3 の各々の全般的
動作を示している。
【０１８２】制御器２０内でローリング手法を用いる際
には、２つの基本的イベント、すなわち「挿入」及び
「使用中／不使用中状態フリップフロップ消去」につい
ての非常に正確な時間的順序付けを要求される。図１３
のタイミング説明図で、制御器２０内の論理回路に用い
られる同期及びデータの流れを説明する。
には、２つの基本的イベント、すなわち「挿入」及び
「使用中／不使用中状態フリップフロップ消去」につい
ての非常に正確な時間的順序付けを要求される。図１３
のタイミング説明図で、制御器２０内の論理回路に用い
られる同期及びデータの流れを説明する。
【０１８３】図に示すように、制御器２０（パイプ探索
リング）のまわりのデータの流れは、パイプ探索制御器
２４0から、パイプ探索制御器 ２４1へ、パイプ探索制
御器２４2へ、パイプ探索制御器 ２４3へと廻り、パイ
プ探索制御器 ２４0へ戻る。別アドレスＡ、Ｂ、Ｃ、及
びＤを有する入力インタフェースによって生成された要
求ベクトルは、パイプ探索制御器 ２４0に挿入される。
リング）のまわりのデータの流れは、パイプ探索制御器
２４0から、パイプ探索制御器 ２４1へ、パイプ探索制
御器２４2へ、パイプ探索制御器 ２４3へと廻り、パイ
プ探索制御器 ２４0へ戻る。別アドレスＡ、Ｂ、Ｃ、及
びＤを有する入力インタフェースによって生成された要
求ベクトルは、パイプ探索制御器 ２４0に挿入される。
【０１８４】別アドレスＥ、Ｆ、Ｇ、及びＨを有する入
力インタフェースによって生成された要求ベクトルは、
パイプ探索制御器 ２４1に挿入される。別アドレスＩ、
Ｊ、Ｋ、及びＬを有する入力インタフェースによって生
成された要求ベクトルは、パイプ探索制御器 ２４2に挿
入される。別アドレスＭ、Ｎ、Ｏ、及びＰを有する入力
インタフェースによって生成された要求ベクトルは、パ
イプ探索制御器 ２４3に挿入される。
力インタフェースによって生成された要求ベクトルは、
パイプ探索制御器 ２４1に挿入される。別アドレスＩ、
Ｊ、Ｋ、及びＬを有する入力インタフェースによって生
成された要求ベクトルは、パイプ探索制御器 ２４2に挿
入される。別アドレスＭ、Ｎ、Ｏ、及びＰを有する入力
インタフェースによって生成された要求ベクトルは、パ
イプ探索制御器 ２４3に挿入される。
【０１８５】「挿入」の時期と「使用中／不使用中状態
フリップフロップ消去」の時期とは、各パイプ探索制御
器内で、異なる時点に発生する。パイプ探索制御器側か
ら見ると、要求ベクトルのビットは、パイプ探索制御器
を通してアルファベット順に（ＡからＰ）流れる（「使
用中／不使用中状態フリップフロップ消去」の時期を無
視した場合）。
フリップフロップ消去」の時期とは、各パイプ探索制御
器内で、異なる時点に発生する。パイプ探索制御器側か
ら見ると、要求ベクトルのビットは、パイプ探索制御器
を通してアルファベット順に（ＡからＰ）流れる（「使
用中／不使用中状態フリップフロップ消去」の時期を無
視した場合）。
【０１８６】この順序付けによって、前に述べた選好手
法の利点が制御器２０内で保証されることになる。その
理由は、別アドレスＡを有する入力インタフェースから
生成された要求ベクトルが、別アドレスＢ、Ｃ、及びＤ
等を有する入力インタフェースから生成された要求ベク
トルに対する優先権を常に与えられるからである。
法の利点が制御器２０内で保証されることになる。その
理由は、別アドレスＡを有する入力インタフェースから
生成された要求ベクトルが、別アドレスＢ、Ｃ、及びＤ
等を有する入力インタフェースから生成された要求ベク
トルに対する優先権を常に与えられるからである。
【０１８７】或る１個の特定の１６ｘ１６クロスバー交
換機上での入力間の独立性を強制することから利益が得
られる反面、パイプ探索回路の複雑性が僅かに増加す
る。ガロアフィールド理論を用いることによって得られ
る入力インタフェースと交換基本構造１４Ａとの間の接
続の独立性から、単一の入力インタフェースからの要求
ベクトルも、パイプ探索リングの各ステージにおいてい
くつもの異なる交換機制御器へ適切にルーティングされ
なければならない。
換機上での入力間の独立性を強制することから利益が得
られる反面、パイプ探索回路の複雑性が僅かに増加す
る。ガロアフィールド理論を用いることによって得られ
る入力インタフェースと交換基本構造１４Ａとの間の接
続の独立性から、単一の入力インタフェースからの要求
ベクトルも、パイプ探索リングの各ステージにおいてい
くつもの異なる交換機制御器へ適切にルーティングされ
なければならない。
【０１８８】ガロアフィールド理論で生成された接続は
混合特性があるため、各入力インタフェース１２0〜１
２255は交換基本構造１４Ａ内の異なる１６ｘ１６クロ
スバー交換機セットに接続される必要があり、その結
果、異なる入力インタフェース上で生成された要求ベク
トルが、制御器２０内の全く異なる交換機制御器セット
を通してルーティングされなければならない。
混合特性があるため、各入力インタフェース１２0〜１
２255は交換基本構造１４Ａ内の異なる１６ｘ１６クロ
スバー交換機セットに接続される必要があり、その結
果、異なる入力インタフェース上で生成された要求ベク
トルが、制御器２０内の全く異なる交換機制御器セット
を通してルーティングされなければならない。
【０１８９】要求ベクトルは制御器２０内のリンク上で
時間多重化されているので、或る１個の特定のＡＴＭセ
ル期間内の要求ベクトルで１つのパイプ探索ステージに
おいて或る１個の特定の交換機制御器から排除された要
求ベクトルは全て、次のパイプ探索ステージにおいて異
なる交換機制御器へルーティングされなければならない
（定義上）。
時間多重化されているので、或る１個の特定のＡＴＭセ
ル期間内の要求ベクトルで１つのパイプ探索ステージに
おいて或る１個の特定の交換機制御器から排除された要
求ベクトルは全て、次のパイプ探索ステージにおいて異
なる交換機制御器へルーティングされなければならない
（定義上）。
【０１９０】要求ベクトルのこの動的ルーティングを行
うために、各パイプ探索制御器２４0〜２４3は、図５に
示すようなそれぞれの小型の交換ネットワーク３０0、
３０1、３０2、及び３０3に接続される。代案として、
交換ネットワーク３０0、３０1、３０2、及び３０3の代
わりに簡単な多重装置（マルチプレクサ）を用いると、
制御器２０のコストが大幅に減少する。
うために、各パイプ探索制御器２４0〜２４3は、図５に
示すようなそれぞれの小型の交換ネットワーク３０0、
３０1、３０2、及び３０3に接続される。代案として、
交換ネットワーク３０0、３０1、３０2、及び３０3の代
わりに簡単な多重装置（マルチプレクサ）を用いると、
制御器２０のコストが大幅に減少する。
【０１９１】幸いに、必要とされるこれら小型の交換ネ
ットワーク ３０0、３０1、３０2、及び３０3 （又はマ
ルチプレクサ）の構成は、ＡＴＭセル期間に等しい周期
を有する周期的なものであり、又この必要とされる構成
は、論理に基づいて定めることができるので、制御器２
０の回路設計の際に小型の交換ネットワーク（マルチプ
レクサ）の形にハードコード化して形成することが可能
である。
ットワーク ３０0、３０1、３０2、及び３０3 （又はマ
ルチプレクサ）の構成は、ＡＴＭセル期間に等しい周期
を有する周期的なものであり、又この必要とされる構成
は、論理に基づいて定めることができるので、制御器２
０の回路設計の際に小型の交換ネットワーク（マルチプ
レクサ）の形にハードコード化して形成することが可能
である。
【０１９２】前に述べたように、図５に示すＡＴＭ交換
装置１０Ａは入力ラインの数を５１２、１０２４、又は
更に大きい値にまで拡大（スケールアップ）してもよ
い。これらのサイズの交換装置においては、入力ライン
が２.５Ｇｂｐｓ のデータレートで動作していると仮定
すると、総処理能力は１.０Ｔｂｐｓ を超えることにな
る。
装置１０Ａは入力ラインの数を５１２、１０２４、又は
更に大きい値にまで拡大（スケールアップ）してもよ
い。これらのサイズの交換装置においては、入力ライン
が２.５Ｇｂｐｓ のデータレートで動作していると仮定
すると、総処理能力は１.０Ｔｂｐｓ を超えることにな
る。
【０１９３】このようなサイズの交換装置においては、
制御器２０がこれらのパイプの全てを通してこれらのパ
スの全てについて探索を行うに十分な処理パワーを与え
るために第４のレベルの並行処理が必要である。５１２
個及び１０２４個の入力ラインを有するＡＴＭ交換装置
の場合、それぞれの制御器内の線上のデータレートは、
２０４Ｍｂｐｓ及び３８６Ｍｂｐｓとなり、ＡＴＭ交換
装置１０Ａの２５６個の入力ライン規模における１１３
Ｍｂｐｓよりもかなり高いレートである。
制御器２０がこれらのパイプの全てを通してこれらのパ
スの全てについて探索を行うに十分な処理パワーを与え
るために第４のレベルの並行処理が必要である。５１２
個及び１０２４個の入力ラインを有するＡＴＭ交換装置
の場合、それぞれの制御器内の線上のデータレートは、
２０４Ｍｂｐｓ及び３８６Ｍｂｐｓとなり、ＡＴＭ交換
装置１０Ａの２５６個の入力ライン規模における１１３
Ｍｂｐｓよりもかなり高いレートである。
【０１９４】第４のレベルの並行処理の背後にある基本
概念は、前に述べた制御器２０の設計変更で、この変更
では、要求ベクトルが複数のパイプ探索のステージを通
して並行してルーティングされることが要求される。詳
しくは、或る１個の特定のパイプに挿入される要求ベク
トルの全てが、複数のパイプ探索ステージを通して一緒
にルーティングされる。これらの要求ベクトルが１個の
挿入グループを構成するものと考える。
概念は、前に述べた制御器２０の設計変更で、この変更
では、要求ベクトルが複数のパイプ探索のステージを通
して並行してルーティングされることが要求される。詳
しくは、或る１個の特定のパイプに挿入される要求ベク
トルの全てが、複数のパイプ探索ステージを通して一緒
にルーティングされる。これらの要求ベクトルが１個の
挿入グループを構成するものと考える。
【０１９５】図５に示す実施例において、制御器２０の
この設計手法では１６ビットの要求ベクトルからなる４
個のグループが形成され、各挿入グループは６４ビット
からなる。４個の挿入グループには、要求ベクトルの４
個の別名からなる一連の名称が付けられる。その結果、
図５の設計し直されたパイプ探索システムの４個の挿入
グループは、ＡＢＣＤ、ＥＦＧＨ、ＩＪＫＬ、及びＭＮ
ＯＰと呼ぶ。
この設計手法では１６ビットの要求ベクトルからなる４
個のグループが形成され、各挿入グループは６４ビット
からなる。４個の挿入グループには、要求ベクトルの４
個の別名からなる一連の名称が付けられる。その結果、
図５の設計し直されたパイプ探索システムの４個の挿入
グループは、ＡＢＣＤ、ＥＦＧＨ、ＩＪＫＬ、及びＭＮ
ＯＰと呼ぶ。
【０１９６】なお、単一の６４ビット挿入グループＡＢ
ＣＤが図５のパイプ探索制御器２４0 内の１６個の交換
機制御器のうちの１個の交換機制御器を通してルーティ
ングされているときには、パイプ探索制御器２４0 内の
他の１５個の交換機制御器の各々を通してルーティング
中の６４ビット挿入グループＡＢＣＤが存在することを
注記したい。その結果、或る単一時点においてパイプ１
８0 を通してルーティングされている１６個の挿入グル
ープＡＢＣＤに連関する要求ベクトルビットが合計で１
０２４個存在する。
ＣＤが図５のパイプ探索制御器２４0 内の１６個の交換
機制御器のうちの１個の交換機制御器を通してルーティ
ングされているときには、パイプ探索制御器２４0 内の
他の１５個の交換機制御器の各々を通してルーティング
中の６４ビット挿入グループＡＢＣＤが存在することを
注記したい。その結果、或る単一時点においてパイプ１
８0 を通してルーティングされている１６個の挿入グル
ープＡＢＣＤに連関する要求ベクトルビットが合計で１
０２４個存在する。
【０１９７】設計変更された制御器２０は、８クロック
周期毎にＮ個全ての入力ポートについて要求ベクトルを
（４個全てのパイプ探索制御器２４0〜２４3を通して送
ることにより）処理する。そして、このタスクが単一の
１７６ｎｓのＡＴＭセル期間内に完了しなければならな
いので、制御器２０内の必要クロックレートは、ＮｘＮ
のＡＴＭ交換装置のサイズ（総処理能力）に関係なく４
６Ｍｂｐｓである。
周期毎にＮ個全ての入力ポートについて要求ベクトルを
（４個全てのパイプ探索制御器２４0〜２４3を通して送
ることにより）処理する。そして、このタスクが単一の
１７６ｎｓのＡＴＭセル期間内に完了しなければならな
いので、制御器２０内の必要クロックレートは、ＮｘＮ
のＡＴＭ交換装置のサイズ（総処理能力）に関係なく４
６Ｍｂｐｓである。
【０１９８】その結果、制御器２０は、ネットワークの
サイズに関係なく８個の処理ステップを行わなければな
らないので、そのプロセスは「Ｏ(1) パス探索アルゴリ
ズム」と呼ばれる。図５のＮ＝２５６個の入力のＡＴＭ
交換装置１０Ａについてのこの「Ｏ(1) パス探索アルゴ
リズム」の実行中に、１７６ｎｓ毎に、 １６,３８４の
リンク制御器パス探索及び１６,３８４ のリンク制御器
パス探索点検が行われる。
サイズに関係なく８個の処理ステップを行わなければな
らないので、そのプロセスは「Ｏ(1) パス探索アルゴリ
ズム」と呼ばれる。図５のＮ＝２５６個の入力のＡＴＭ
交換装置１０Ａについてのこの「Ｏ(1) パス探索アルゴ
リズム」の実行中に、１７６ｎｓ毎に、 １６,３８４の
リンク制御器パス探索及び１６,３８４ のリンク制御器
パス探索点検が行われる。
【０１９９】したがって、もし各パス探索及び各パス探
索点検がそれぞれ命令の実行であると考えた場合、制御
器２０は、毎秒１８６ギガ個の命令処理レートを維持す
る能力を有する並行プロセッサと見ることができる。
索点検がそれぞれ命令の実行であると考えた場合、制御
器２０は、毎秒１８６ギガ個の命令処理レートを維持す
る能力を有する並行プロセッサと見ることができる。
【０２００】制御器２０において（サイズに関係なく）
妥当なデータレートを維持するための交換条件は、サイ
ズが増大するにつれて、リンク制御き論理回路の複雑性
が増加し、又制御器の、互いに続くステージ間を通る信
号接続が増加することである。１Ｔｂｐｓを超える総処
理能力のＡＴＭ交換装置の設計では、互いに続くパイプ
探索制御器ステージ間に４０９６個から３２,７６８ 個
の範囲の信号を（４６Ｇｂｐｓのレートで）ルーティン
グする必要がある。
妥当なデータレートを維持するための交換条件は、サイ
ズが増大するにつれて、リンク制御き論理回路の複雑性
が増加し、又制御器の、互いに続くステージ間を通る信
号接続が増加することである。１Ｔｂｐｓを超える総処
理能力のＡＴＭ交換装置の設計では、互いに続くパイプ
探索制御器ステージ間に４０９６個から３２,７６８ 個
の範囲の信号を（４６Ｇｂｐｓのレートで）ルーティン
グする必要がある。
【０２０１】互いに続くパイプ探索制御器ステージ間を
通る信号接続の増加に加えて、制御器２０内での並行処
理の採用によっても又、各リンク制御器のハードウエア
要件を僅かに増加させる必要が生じる。理由は、今や各
リンク制御器がその挿入グループ内の４個のビットにつ
いて並行パス探索をサポートしなければならないからで
ある。第４のレベルの並行処理によって制御器２０に追
加される余分のハードウエアは、その結果としてより低
い処理レートが得られることによって補償される。
通る信号接続の増加に加えて、制御器２０内での並行処
理の採用によっても又、各リンク制御器のハードウエア
要件を僅かに増加させる必要が生じる。理由は、今や各
リンク制御器がその挿入グループ内の４個のビットにつ
いて並行パス探索をサポートしなければならないからで
ある。第４のレベルの並行処理によって制御器２０に追
加される余分のハードウエアは、その結果としてより低
い処理レートが得られることによって補償される。
【０２０２】［マルチキャスティング作業］出力パケッ
トモジュールは、その内蔵する機能の高さから、分配ネ
ットワーク及び分散制御器と概ね同等の複雑性を有す
る。例えば、各出力パケットモジュールは、多数の先入
れ先出し（ＦＩＦＯ）型のメモリを要する集線装置機能
を持たなければならない。そしてこれらのメモリに必要
なアクセス速度は集線装置の入力及び出力の数に直接に
比例する。
トモジュールは、その内蔵する機能の高さから、分配ネ
ットワーク及び分散制御器と概ね同等の複雑性を有す
る。例えば、各出力パケットモジュールは、多数の先入
れ先出し（ＦＩＦＯ）型のメモリを要する集線装置機能
を持たなければならない。そしてこれらのメモリに必要
なアクセス速度は集線装置の入力及び出力の数に直接に
比例する。
【０２０３】加えて、各出力パケットモジュールは又、
望む出力ポートから一時的に阻止閉塞されたパケットを
収容するために、大きな共用バッファメモリを備えなけ
ればならない。このバッファメモリの必要アクセス速度
は、出力パケットモジュールからの出力の数に比例す
る。出力パケットモジュールは又、出力パケットモジュ
ールが受信するパケットを、パケットの望む出力ポート
へ正しい時間シーケンスで導く手段を備えなければなら
ない。
望む出力ポートから一時的に阻止閉塞されたパケットを
収容するために、大きな共用バッファメモリを備えなけ
ればならない。このバッファメモリの必要アクセス速度
は、出力パケットモジュールからの出力の数に比例す
る。出力パケットモジュールは又、出力パケットモジュ
ールが受信するパケットを、パケットの望む出力ポート
へ正しい時間シーケンスで導く手段を備えなければなら
ない。
【０２０４】更に、各出力パケットモジュールは、マル
チキャスティングセルの多数のコピーを作成すること、
マルチキャスティングセルの各々に新しいＶＰＩ／ＶＣ
Ｉフィールドを注入すること、及びマルチキャスティン
グセルを適切にルーティングすることによって、出力パ
ケットモジュールの入力と出力との間でセルをマルチキ
ャスティングする処理を行わなければならない。
チキャスティングセルの多数のコピーを作成すること、
マルチキャスティングセルの各々に新しいＶＰＩ／ＶＣ
Ｉフィールドを注入すること、及びマルチキャスティン
グセルを適切にルーティングすることによって、出力パ
ケットモジュールの入力と出力との間でセルをマルチキ
ャスティングする処理を行わなければならない。
【０２０５】これら出力パケットモジュールの行う機能
を考えると、より大きな出力パケットモジュールにおい
ては、これらの機能の全てを備えるタスクが困難且つ高
価になることは明らかである。したがって、出力パケッ
トモジュールに必要なサイズを減少させるのを助けるト
レードオフ手法は非常に有益である。
を考えると、より大きな出力パケットモジュールにおい
ては、これらの機能の全てを備えるタスクが困難且つ高
価になることは明らかである。したがって、出力パケッ
トモジュールに必要なサイズを減少させるのを助けるト
レードオフ手法は非常に有益である。
【０２０６】図５に示すシステムにおいて、出力パケッ
トモジュールの各々は、６４個の入力リンクと１６個の
出力リンクとをサポートするように設計されている。こ
のサイズは、分配ネットワーク（交換基本構造）１４Ａ
に用いられるクロスバー交換機の数に直接に関連する。
理由は、各出力パケットモジュールが、分配ネットワー
ク１４Ａ内のクロスバー交換機の各々からその出力パケ
ットモジュールへ正確に１個のリンクをルーティングす
る必要があるからである。
トモジュールの各々は、６４個の入力リンクと１６個の
出力リンクとをサポートするように設計されている。こ
のサイズは、分配ネットワーク（交換基本構造）１４Ａ
に用いられるクロスバー交換機の数に直接に関連する。
理由は、各出力パケットモジュールが、分配ネットワー
ク１４Ａ内のクロスバー交換機の各々からその出力パケ
ットモジュールへ正確に１個のリンクをルーティングす
る必要があるからである。
【０２０７】出力パケットモジュールから発する出力の
数は常に、出力パケットモジュールへの入力の数の１／
Ｆ倍である。ここにＦは、分配ネットワーク１４Ａによ
って与えられるファンアウトである。図５に示す分配ネ
ットワーク（交換基本構造）においてＦは４である。
数は常に、出力パケットモジュールへの入力の数の１／
Ｆ倍である。ここにＦは、分配ネットワーク１４Ａによ
って与えられるファンアウトである。図５に示す分配ネ
ットワーク（交換基本構造）においてＦは４である。
【０２０８】帯域外制御手法に基づく本発明のＡＴＭ交
換装置アーキテクチャによって、交換基本構造１４Ａの
状態に関する全体的な情報を、多数の異なる方法で用い
ることが可能になる。同様に、到着ＡＴＭセル用のパス
をパイプ探索システム内で迅速にルーティングするその
仕方によって、帯域内／自己ルーティング制御手法に基
づくアーキテクチャにおいてはたぶん非常に困難と考え
られるいくつもの機能について、実現の機会が与えられ
る。マルチキャスティングはこれらの機能の１つであ
る。
換装置アーキテクチャによって、交換基本構造１４Ａの
状態に関する全体的な情報を、多数の異なる方法で用い
ることが可能になる。同様に、到着ＡＴＭセル用のパス
をパイプ探索システム内で迅速にルーティングするその
仕方によって、帯域内／自己ルーティング制御手法に基
づくアーキテクチャにおいてはたぶん非常に困難と考え
られるいくつもの機能について、実現の機会が与えられ
る。マルチキャスティングはこれらの機能の１つであ
る。
【０２０９】マルチキャスティングは、ＡＴＭについて
は、ＡＴＭ交換装置が単一の入力ＡＴＭセルを多数の出
力ポートへルーティングする能力として定義される。マ
ルチキャスティングは、単一のソースを多数の宛先へ送
信する必要のある用途にとって重要な機能である。
は、ＡＴＭ交換装置が単一の入力ＡＴＭセルを多数の出
力ポートへルーティングする能力として定義される。マ
ルチキャスティングは、単一のソースを多数の宛先へ送
信する必要のある用途にとって重要な機能である。
【０２１０】この機能の普通の用途としては、有線テレ
ビ（ＣＡＴＶ）のヘッドエンド（信号送出部）内の映像
サーバから特定のテレビショーにチャネルを合わせた家
庭の全てに映像トラヒックを分配する場合の用途が考え
られる。マルチキャスティングは又、電気通信環境にお
ける単一のコンピュータ上の単一ユーザから空間的に分
散する多数のコンピュータ上のユーザへ電子メールのメ
ッセージを分配する場合にも有用である。
ビ（ＣＡＴＶ）のヘッドエンド（信号送出部）内の映像
サーバから特定のテレビショーにチャネルを合わせた家
庭の全てに映像トラヒックを分配する場合の用途が考え
られる。マルチキャスティングは又、電気通信環境にお
ける単一のコンピュータ上の単一ユーザから空間的に分
散する多数のコンピュータ上のユーザへ電子メールのメ
ッセージを分配する場合にも有用である。
【０２１１】マルチキャスティングの場合のルーティン
グに必要なプロトコル及び信号フォーマットはＡＴＭ規
格には明確な定義がないが、将来のＡＴＭプロトコルに
おいては、望まれる出力ポートの全てを含むリンクされ
たリストを指す特別ＶＰＩ／ＶＣＩアドレスを用いて出
力ポートの全てへの接続を設定することをユーザに要求
するようになる可能性が高い。
グに必要なプロトコル及び信号フォーマットはＡＴＭ規
格には明確な定義がないが、将来のＡＴＭプロトコルに
おいては、望まれる出力ポートの全てを含むリンクされ
たリストを指す特別ＶＰＩ／ＶＣＩアドレスを用いて出
力ポートの全てへの接続を設定することをユーザに要求
するようになる可能性が高い。
【０２１２】図１８を参照して、本発明に基づくマルチ
キャスティングについて説明する。マルチキャスティン
グのタスクは、２つの部分に分割される。第１に、分配
ネットワーク（交換基本構造）１４Ａが出力パケットモ
ジュール１６0〜１６15 の間にマルチキャスティングを
行う。そして第２に出力パケットモジュール １６0〜１
６15の各々が、その入力ポートと出力ポートとの間にマ
ルチキャスティングを行う。
キャスティングについて説明する。マルチキャスティン
グのタスクは、２つの部分に分割される。第１に、分配
ネットワーク（交換基本構造）１４Ａが出力パケットモ
ジュール１６0〜１６15 の間にマルチキャスティングを
行う。そして第２に出力パケットモジュール １６0〜１
６15の各々が、その入力ポートと出力ポートとの間にマ
ルチキャスティングを行う。
【０２１３】その結果、出力パケットモジュール１６0
〜１６15 は、その入力の１つに到着するＡＴＭセルの
いくつかのコピーを作成するだけでよい（出力パケット
モジュール１６0〜１６15 は、セルをコピーする手法を
用いてマルチキャスティングを実現してもよい）。
〜１６15 は、その入力の１つに到着するＡＴＭセルの
いくつかのコピーを作成するだけでよい（出力パケット
モジュール１６0〜１６15 は、セルをコピーする手法を
用いてマルチキャスティングを実現してもよい）。
【０２１４】分配ネットワーク１４Ａは、マルチキャス
ティングに関与するその入力ラインカード １７0〜１７
255 （入力ポート）と各出力パケットモジュールとの間
にマルチキャスティングを行う機能を容易に提供でき
る。図１８は、ＡＴＭセルが入力ラインカード１７0か
ら出力パケットモジュール１６0、１６7、及び １６15
へ、そして出力ライン０、１、１２０、及び２４０へマ
ルチキャスティングされる場合を示す。
ティングに関与するその入力ラインカード １７0〜１７
255 （入力ポート）と各出力パケットモジュールとの間
にマルチキャスティングを行う機能を容易に提供でき
る。図１８は、ＡＴＭセルが入力ラインカード１７0か
ら出力パケットモジュール１６0、１６7、及び １６15
へ、そして出力ライン０、１、１２０、及び２４０へマ
ルチキャスティングされる場合を示す。
【０２１５】もしラインカードによって生成された要求
ベクトルが、１ビットを超える数のビットを論理値
「１」に設定されている場合には、パイプ探索用の制御
器２０はＡＴＭセルを多数の出力パケットモジュールへ
のルーティングを自動的に企図する（前に述べたハード
ウエアへの変更を要しない）。ＡＴＭセルは単に、入力
ラインカード１７0 から分配ネットワーク１４Ａを通し
１個よりも多い数のパスを通して流れるだけである。し
たがって、入力ラインカードによるセルのコピー処理は
不要である。
ベクトルが、１ビットを超える数のビットを論理値
「１」に設定されている場合には、パイプ探索用の制御
器２０はＡＴＭセルを多数の出力パケットモジュールへ
のルーティングを自動的に企図する（前に述べたハード
ウエアへの変更を要しない）。ＡＴＭセルは単に、入力
ラインカード１７0 から分配ネットワーク１４Ａを通し
１個よりも多い数のパスを通して流れるだけである。し
たがって、入力ラインカードによるセルのコピー処理は
不要である。
【０２１６】出力パケットモジュール１６0〜１６15 に
ついては、もし、図１８の出力パケットモジュール１６
0 のように、出力パケットモジュール内でのマルチキャ
スティングが必要な場合には、出力パケットモジュール
が、出力ラインへ送達するために受信バッファ内の多数
の箇所にパケットをコピーするか又は、マルチキャステ
ィング時に出力パケットモジュールを作動させる方法を
用いて、格納されているセルに多数回アクセスする必要
がある。
ついては、もし、図１８の出力パケットモジュール１６
0 のように、出力パケットモジュール内でのマルチキャ
スティングが必要な場合には、出力パケットモジュール
が、出力ラインへ送達するために受信バッファ内の多数
の箇所にパケットをコピーするか又は、マルチキャステ
ィング時に出力パケットモジュールを作動させる方法を
用いて、格納されているセルに多数回アクセスする必要
がある。
【０２１７】このように、余分なハードウエアをほとん
ど必要とせずに、ＡＴＭ交換装置１０ＡがＡＴＭセルを
マルチキャスティングすることができる。
ど必要とせずに、ＡＴＭ交換装置１０ＡがＡＴＭセルを
マルチキャスティングすることができる。
【０２１８】マルチキャスティングは、１個のパケット
を１個の入力ラインから、又は１個のパケットグループ
を１個の入力ライングループから、出力パケットモジュ
ール１６0〜１６15 の出力ラインの全て又はほとんど全
てへ転送する手法であるが、このマルチキャスティング
は、もし交換装置１０Ａを通しての総データ帯域幅が入
力制限によって制御されない場合には、セル損失確率に
非常に顕著な影響を及ぼす。このような入力制限は技術
的には理解されているが、本発明の技術的範囲外である
ため、図示しない。
を１個の入力ラインから、又は１個のパケットグループ
を１個の入力ライングループから、出力パケットモジュ
ール１６0〜１６15 の出力ラインの全て又はほとんど全
てへ転送する手法であるが、このマルチキャスティング
は、もし交換装置１０Ａを通しての総データ帯域幅が入
力制限によって制御されない場合には、セル損失確率に
非常に顕著な影響を及ぼす。このような入力制限は技術
的には理解されているが、本発明の技術的範囲外である
ため、図示しない。
【０２１９】もし１個の入力セルが１セル期間内に全て
の出力ラインを使用することが許される場合には、他の
入力ライン上のトラヒックは、そのセル期間及び次のセ
ル期間について、残されているラインについて競合せざ
るを得ないことは理解されよう。。シミュレーションに
よれば、非マルチキャスティングＡＴＭセルトラヒック
については、ＡＴＭ交換装置１０Ａが非常に低いセル損
失確率を有することが知られている。
の出力ラインを使用することが許される場合には、他の
入力ライン上のトラヒックは、そのセル期間及び次のセ
ル期間について、残されているラインについて競合せざ
るを得ないことは理解されよう。。シミュレーションに
よれば、非マルチキャスティングＡＴＭセルトラヒック
については、ＡＴＭ交換装置１０Ａが非常に低いセル損
失確率を有することが知られている。
【０２２０】図５に示すような全負荷されている交換装
置については、平均セル損失確率値は１ｘ１０-12 より
もはるかによい。そして、このセル損失確率値は、入力
ライン占有率が１００％から減少するにつれて急速に低
下する。
置については、平均セル損失確率値は１ｘ１０-12 より
もはるかによい。そして、このセル損失確率値は、入力
ライン占有率が１００％から減少するにつれて急速に低
下する。
【０２２１】マルチキャスティング中、入力パケットが
交換装置１０Ａの出力帯域幅を超えないように制限され
た場合には、交換装置１０Ａの示すセル閉塞確率は非マ
ルチキャスティング時の閉塞確率と同じかそれよりもよ
い値を示す。このことの理由は、マルチキャスティング
時には、出力パケットモジュール１６0〜１６15 におい
て必要事項としてコピー処理が行われることから分配ネ
ットワーク１４Ａを通して要求されるパス数がより少な
いためである。
交換装置１０Ａの出力帯域幅を超えないように制限され
た場合には、交換装置１０Ａの示すセル閉塞確率は非マ
ルチキャスティング時の閉塞確率と同じかそれよりもよ
い値を示す。このことの理由は、マルチキャスティング
時には、出力パケットモジュール１６0〜１６15 におい
て必要事項としてコピー処理が行われることから分配ネ
ットワーク１４Ａを通して要求されるパス数がより少な
いためである。
【０２２２】以上の説明は、本発明のいくつかの実施例
に関するもので、この技術分野の当業者であれば、本発
明の形式、詳細、及び用例について種々の変形例を考え
ることが可能である。例えば、交換基本構造に４個より
も多くのパイプを用いてもよく、その場合には制御器に
修正を要する。そして、これらの修正、変更はいずれも
本発明の技術的範囲に包含される。
に関するもので、この技術分野の当業者であれば、本発
明の形式、詳細、及び用例について種々の変形例を考え
ることが可能である。例えば、交換基本構造に４個より
も多くのパイプを用いてもよく、その場合には制御器に
修正を要する。そして、これらの修正、変更はいずれも
本発明の技術的範囲に包含される。
【０２２３】
【発明の効果】以上述べたごとく、本発明によれば、帯
域外制御手法においてローリング（延伸）処理、複数レ
ベルの並行処理等を組み合わせて行うことにより、各パ
ケットについて最適なパス探索を得るために、全てのパ
スについての全体的考察が得られるようなパケット交換
装置用の分散型帯域外制御器の技術が得られる。又、単
一データセルから多数の出力へのマルチキャスティング
を行うＡＴＭパケット交換装置を制御への適用が可能で
ある。
域外制御手法においてローリング（延伸）処理、複数レ
ベルの並行処理等を組み合わせて行うことにより、各パ
ケットについて最適なパス探索を得るために、全てのパ
スについての全体的考察が得られるようなパケット交換
装置用の分散型帯域外制御器の技術が得られる。又、単
一データセルから多数の出力へのマルチキャスティング
を行うＡＴＭパケット交換装置を制御への適用が可能で
ある。
【０２２４】交換基本構造を多数のパイプに分割し、並
行してパス探索を行うことにより、効率のよいルーティ
ングが可能となり、ＡＴＭセル損失確率が減少する。し
たがって、ＡＴＭ交換装置の通信効率が改善され、高速
度でのＡＴＭデータ伝送が可能となる
行してパス探索を行うことにより、効率のよいルーティ
ングが可能となり、ＡＴＭセル損失確率が減少する。し
たがって、ＡＴＭ交換装置の通信効率が改善され、高速
度でのＡＴＭデータ伝送が可能となる
【図１】一般的な成長可能パケット交換装置を示すブロ
ック図である
ック図である
【図２】図１を少し書き換えた一般的な成長可能パケッ
ト交換装置を示すブロック図である。
ト交換装置を示すブロック図である。
【図３】本発明に基づき交換基本構造を多数であるＬ個
のパイプに分割した成長可能パケット交換装置を示すブ
ロック図である。
のパイプに分割した成長可能パケット交換装置を示すブ
ロック図である。
【図４】４個のパイプ（Ｌ＝４）を有しパイプの構成を
示す本発明の特定の実施例を示す、図３に類似のブロッ
ク図である。
示す本発明の特定の実施例を示す、図３に類似のブロッ
ク図である。
【図５】図４の実施例を示す簡素化ブロック図において
制御器をより詳細に示したブロック図である。
制御器をより詳細に示したブロック図である。
【図６】図５に示す制御器への要求のタイミングシーケ
ンスを示す説明図である。
ンスを示す説明図である。
【図７】出力パケットモジュールの実施例の簡素化ブロ
ック図である。
ック図である。
【図８】アミューズメントパークとそのサテライト駐車
場との平面図におけるローリング及びその動作を示す説
明図である。
場との平面図におけるローリング及びその動作を示す説
明図である。
【図９】プレファレンスの割り当てのありなし両方の場
合についての種々のＡＴＭセル損失確率の計算値曲線で
ある。
合についての種々のＡＴＭセル損失確率の計算値曲線で
ある。
【図１０】代表的なクロスバー交換機制御器及びそのリ
ンク制御器の簡素化ブロック図である。
ンク制御器の簡素化ブロック図である。
【図１１】リンク制御器の詳細論理図である。
【図１２】図１１に示すリンク制御器についての状態テ
ーブルである。
ーブルである。
【図１３】図１４〜図１６と共に、要求シーケンスに応
動するクロスバー交換機制御器の動作を示す説明図であ
る。
動するクロスバー交換機制御器の動作を示す説明図であ
る。
【図１４】図１３及び図１５〜図１６と共に、要求シー
ケンスに応動するクロスバー交換機制御器の動作を示す
説明図である。
ケンスに応動するクロスバー交換機制御器の動作を示す
説明図である。
【図１５】図１３〜図１４及び図１６と共に、要求シー
ケンスに応動するクロスバー交換機制御器の動作を示す
説明図である。
ケンスに応動するクロスバー交換機制御器の動作を示す
説明図である。
【図１６】図１３〜図１５と共に、要求シーケンスに応
動するクロスバー交換機制御器の動作を示す説明図であ
る。
動するクロスバー交換機制御器の動作を示す説明図であ
る。
【図１７】２レベルのセル損失優先度を有する４個のパ
イプ探索制御器を有する交換装置を通してのパス探索要
求のローリング（延伸）処理を示す説明図である。
イプ探索制御器を有する交換装置を通してのパス探索要
求のローリング（延伸）処理を示す説明図である。
【図１８】２レベルのセル損失優先度を有する４個のパ
イプ探索制御器を有する交換装置を通してのパス探索要
求のローリング（延伸）処理を示す説明図である。
イプ探索制御器を有する交換装置を通してのパス探索要
求のローリング（延伸）処理を示す説明図である。
１０、１０Ａ ＡＴＭ交換装置 １２0〜１２N-1、１２0〜１２255 入力インタフェース １４、１４Ａ 交換基本構造 １５0〜１５63 クロスバー交換機 １６0〜１６V-1、１６0〜１６15 出力パケットモジュ
ール １７0〜１７N-1、１７0〜１７255 入力ポート １８0〜１８L-1、１８0〜１８3 パイプ １９0〜１９N-1、１９0〜１９1023 出力ポート ２０ 制御器 ２１0〜２１255 制御接続線 ２２ 高速直列制御リンク ２４0〜２４3 パイプ探索制御器 ２６0〜２６63 クロスバー交換機制御器（交換機制御
器） ３０0、３０1、３０2、３０3 交換ネットワーク １７４0〜１７４63 先入れ先出し（ＦＩＦＯ）待ち行
列 ５００ 遊園地平面図 ５１１、５１２、５１３、５１４ 駐車場 ５２０ 遊園地 ５３０ 列車システム ５３１、５３２、５３３、５３４ 乗車場 In0〜InN-1、 In0〜In255 入力 Out0〜OutN-1、Out0〜Out255 出力
ール １７0〜１７N-1、１７0〜１７255 入力ポート １８0〜１８L-1、１８0〜１８3 パイプ １９0〜１９N-1、１９0〜１９1023 出力ポート ２０ 制御器 ２１0〜２１255 制御接続線 ２２ 高速直列制御リンク ２４0〜２４3 パイプ探索制御器 ２６0〜２６63 クロスバー交換機制御器（交換機制御
器） ３０0、３０1、３０2、３０3 交換ネットワーク １７４0〜１７４63 先入れ先出し（ＦＩＦＯ）待ち行
列 ５００ 遊園地平面図 ５１１、５１２、５１３、５１４ 駐車場 ５２０ 遊園地 ５３０ 列車システム ５３１、５３２、５３３、５３４ 乗車場 In0〜InN-1、 In0〜In255 入力 Out0〜OutN-1、Out0〜Out255 出力
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ゲイロード ワーナー リチャード アメリカ合衆国，60532 イリノイ，リス ル，オールド カレッジ ロード 6730
Claims (18)
- 【請求項１】 パケットを複数の入力ラインのうちの少
なくとも１個の入力ラインから複数の出力ラインへ切り
換えるためのパケット交換装置であって、 各々が前記複数の入力ラインのうちのそれぞれ１個の入
力ラインに接続された１個の入力ポートを有し且つ１個
の出力ポートを有する、複数の入力インタフェースと、 複数のＩ個の入力ポートを複数のＰ個の出力ポートに切
り換えるためのネットワークであって、前記複数の入力
インタフェース出力ポートの各々が該ネットワークの該
Ｉ個の入力ポートのうちのＦ個の入力ポートからなるそ
れぞれの入力ポートグループにファンアウトされ、該ネ
ットワークがＣ個の複数のパイプを有し、ＣがＰ／Ｉに
等しい値の正数であるような、ネットワークと、 複数の出力モジュールであって、該複数の出力モジュー
ルが共に複数の入力を有し、該出力モジュール入力の各
々が前記複数のＰ個の出力ポートのうちのそれぞれの出
力ポートに接続され、該複数の出力モジュールが共に複
数の出力を有し、該出力モジュール出力の各々が前記複
数の出力ラインのうちのそれぞれの出力ラインに接続さ
れるような、複数の出力モジュールと、 前記複数の入力ラインからの少なくとも１個のパケット
を多数の出力ラインへマルチキャスティングする帯域外
制御器と、からなり、 前記Ｃ個のパイプの各々が、前記複数の入力ラインの各
々からのパスであって前記複数の出力ラインのそれぞれ
の出力ラインに接続可能であるようなパスを有する、こ
とを特徴とする、パケット交換装置。 - 【請求項２】 前記入力インタフェースの各々がパケッ
トを格納するための記憶部を有し、 前記帯域外制御器が、第１のパイプを通しての閉塞され
ない未閉塞パスを見出すことができなかったパケットに
ついてのパスに対する要求を第２のパイプのパイプ制御
器へローリングし、マルチキャスティングデータパケッ
トの各々についてのそれぞれの出力ラインへの未閉塞パ
スをパイプ制御器が探索する間、該パケットが前記入力
インタフェースに格納される、ことを特徴とする請求項
１の装置。 - 【請求項３】 前記入力インタフェースの各々が、パケ
ットを格納するための記憶部を有し、 前記帯域外制御器が、第１のパイプ及び第２のパイプの
両方のパイプを通しての未閉塞パスを見出すことができ
なかったパケットについてのパスに対する要求を第３の
パイプのパイプ制御器へローリングし、マルチキャステ
ィングデータパケットの各々についてのそれぞれの出力
ラインへの未閉塞パスをパイプ制御器が探索する間、該
パケットが前記入力インタフェースに格納される、こと
を特徴とする請求項１の装置。 - 【請求項４】 前記入力インタフェースの各々が、パケ
ットを格納するための記憶部を有し、 前記帯域外制御器が、第１のパイプ、第２のパイプ、及
び第３のパイプを通して未閉塞パスを見出すことができ
なかったパケットについてのパスに対する要求を第４の
パイプのパイプ制御器へローリングし、マルチキャステ
ィングデータパケットの各々についてのそれぞれの出力
ラインへの未閉塞パスをパイプ制御器が探索する間、該
パケットが前記入力インタフェースに格納される、こと
を特徴とする請求項１の装置。 - 【請求項５】 マルチキャスティングデータパケットに
対する複数のパスの所在箇所を探索するためのパケット
交換装置用の制御装置であって、 交換基本構造と前記出力モジュールとの間の各接続につ
いての使用中／不使用中状態を格納するためのメモリ手
段であって複数の使用中／不使用中状態テーブルに分割
されたメモリ手段と、 前記複数の使用中／不使用中状態テーブルの各々にアク
セスするための、且つマルチキャスティングデータパケ
ットの各々について宛先出力ラインが接続される先の各
出力モジュールへのパスの所在箇所を求める手段と、か
らなることを特徴とする、パケット交換装置用の制御装
置。 - 【請求項６】 マルチキャスティングデータパケットに
ついての複数のパスの所在箇所を探索するためのパケッ
ト交換装置用の制御装置であって、該パケット交換装置
が、複数のパイプを有する交換基本構造を有し、該複数
のパイプの各々が複数のクロスバー交換機を有するよう
な、パケット交換装置用の制御装置において、該パケッ
ト交換装置用の制御装置が、 複数のパイプ探索制御器であって、該パイプ探索制御器
の各々が、前記複数のパイプのそれぞれのパイプを制御
し、該パイプ探索制御器の各々が、複数のクロスバー交
換機制御器を有し、前記パイプの前記クロスバー交換機
の各々がそれぞれのクロスバー交換機制御器を有するよ
うな、複数のパイプ探索制御器と、 使用中／不使用中状態テーブルを格納するための複数の
記憶手段であって、該複数の記憶手段の各々が、前記複
数のクロスバー交換機制御器のそれぞれのクロスバー交
換機制御器と連関し且つそれについてのそれぞれの使用
中／不使用中状態テーブルを格納するような、複数の記
憶手段と、 マルチキャスティング要求ベクトルを用いて前記使用中
／不使用中状態テーブルの各々に同時にアクセスする手
段と、からなることを特徴とする、パケット交換装置用
の制御装置。 - 【請求項７】 前記使用中／不使用中状態テーブルの各
々が、複数の使用中／不使用中状態ビットを有し、該複
数の使用中／不使用中状態ビットの各々が、そのそれぞ
れのクロスバー交換機のそれぞれの出力の使用中／不使
用中状態に対応することを特徴とする請求項６の制御装
置。 - 【請求項８】 前記クロスバー交換機制御器の各々がそ
の複数の使用中／不使用中状態ビットを同時に処理する
ことを特徴とする請求項７の制御装置。 - 【請求項９】 前記使用中／不使用中状態ビットの各々
が、そのそれぞれのクロスバー交換機のそれぞれの出力
に対応するそれぞれの出力制御器に格納されることを特
徴とする請求項７の制御装置。 - 【請求項１０】 前記各出力制御器が、各パケット処理
時間周期の間そのそれぞれの出力を制御するために１個
の使用中／不使用中状態ビットを処理することを特徴と
する請求項９の制御装置。 - 【請求項１１】 マルチキャスティングデータパケット
の各々についての多数のパスの所在箇所を求めるための
パケット交換装置用の制御装置であって、該パケット交
換装置が、複数のパイプを有する交換基本構造を有し、
該複数のパイプの各々が複数のクロスバー交換機を有す
るような、パケット交換装置用の制御装置において、該
パケット交換装置用の制御装置が、 複数のパイプ探索制御器であって、該パイプ探索制御器
の各々が、前記複数のパイプのそれぞれのパイプを制御
し、該パイプ探索制御器の各々が、複数のクロスバー交
換機制御器を有し、前記パイプの前記クロスバー交換機
の各々がそのそれぞれのクロスバー交換機制御器によっ
て制御されるような、複数のパイプ探索制御器と、 使用中／不使用中状態テーブルを格納するための複数の
記憶手段であって、該複数の記憶手段の各々が、前記複
数のクロスバー交換機制御器のそれぞれのクロスバー交
換機制御器と連関し且つそれについてのそれぞれの使用
中／不使用中状態テーブルを格納するような、複数の記
憶手段と、 前記使用中／不使用中状態テーブルの各々に同時にアク
セスする手段とからなり、 前記複数の記憶手段の各々が、 使用中／不使用中状態ビットを格納する手段と、 前記記憶手段から前記使用中／不使用中状態ビットを読
み出すための手段と、 要求ビットを用いて前記使用中／不使用中状態ビットに
対して論理演算を行って、結果として得られ前記記憶手
段に格納される使用中／不使用中状態ビットと、要求出
力ビットと、接続ビットとを産出する手段と、 前記論理演算を行う手段の前記接続ビットに応動して、
もし前記接続ビットが設定された場合に前記それぞれの
クロスバー交換機を通してパスを接続する手段とからな
る、ことを特徴とする、パケット交換装置用の制御装
置。 - 【請求項１２】 前記制御装置が更に、 前記要求アウトビットを別のパイプにおける前記複数の
記憶手段のうちの別の記憶手段に転送する手段であっ
て、前記要求アウトビットが前記別の記憶手段のそれぞ
れの論理演算手段に入力され、別の使用中／不使用中状
態ビットに対して論理演算されて、結果として得られる
使用中／不使用中状態ビットと、別の要求アウトビット
と、別の接続ビットとを産出するような、前記要求アウ
トビットを別のパイプにおける前記複数の記憶手段のう
ちの別の記憶手段に転送する手段からなることを特徴と
する請求項１１の制御装置。 - 【請求項１３】 前記要求ビットが、要求ベクトルとし
て並行して送信されることを特徴とする、請求項１１の
制御装置。 - 【請求項１４】 前記要求ビットのうちの１６個の要求
ビットが、１６個の記憶手段への要求ベクトルとして並
行して送信されることを特徴とする請求項１１の制御装
置。 - 【請求項１５】 各パケット周期期間中にパケット交換
装置を制御するための方法であって、該パケット交換装
置が、複数のパイプを有する交換基本構造と複数の出力
モジュールとを有し、該複数のパイプの各々が複数のク
ロスバー交換機を有するような、パケット交換装置を制
御するための方法において、 各パケット周期期間の初めに全ての使用中／不使用中状
態ビットを不使用中として設定するステップと、 クロスバー交換機制御器の使用中／不使用中状態メモリ
から各クロスバー交換機の出力ポートの数に等しい数の
複数の使用中／不使用中状態ビットを並行して読み出す
ステップと、 前記複数の使用中／不使用中状態ビットとマルチキャス
ティング要求ベクトル入力とに基づいて、並行するパイ
プ探索演算を行い、更新された使用中／不使用中状態ベ
クトルと、接続ベクトルと、マルチキャスティング要求
ベクトル出力とを産出するステップと、 前記更新された使用中／不使用中状態ベクトルを前記使
用中／不使用中状態メモリに並行して格納するステップ
と、 前記接続ベクトルを前記複数のクロスバー交換機のうち
の１個のクロスバー交換機へ転送して、パケットについ
て前記交換基本構造の入力から前記交換基本構造の出力
へのパスを設定するステップと、からなることを特徴と
する、パケット交換装置を制御するための方法。 - 【請求項１６】 前記方法が更に、 満たされていない要求を含む前記マルチキャスティング
要求ベクトル出力を前記要求ベクトル入力から別のパイ
プ内の第２のクロスバー交換機制御器へ転送するステッ
プと、 前記マルチキャスティング要求ベクトル出力を、前記第
２のクロスバー交換機に対するマルチキャスティング要
求ベクトル入力として用いるステップと、 前記第２のクロスバー交換機制御器の使用中／不使用中
状態メモリから各クロスバー交換機の出力ポートの数に
等しい数の複数の使用中／不使用中状態ビットを並行し
て読み出すステップと、 前記複数の使用中／不使用中状態ビットのうちの１６個
の使用中／不使用中状態ビットと前記マルチキャスティ
ング要求ベクトル入力とに基づいて、並行するパイプ探
索演算を行い、第２の更新された使用中／不使用中状態
ベクトルと、第２の接続ベクトルと、第２のマルチキャ
スティング要求ベクトル出力とを産出するステップと、 前記第２の更新された使用中／不使用中状態ベクトルを
前記第２のクロスバー交換機制御器の前記使用中／不使
用中状態メモリに並行して格納するステップと、 前記第２の接続ベクトルを前記複数のクロスバー交換機
のうちの１個のクロスバー交換機へ転送して、パケット
について前記交換基本構造の入力から前記交換基本構造
の出力へのパスを設定するステップと、からなることを
特徴とする請求項１５の方法。 - 【請求項１７】 前記並行するパイプ探索演算を行うス
テップが、 複数のリンク制御器を各クロスバー交換機制御器内に設
け各リンク制御器が前記交換基本構造と前記複数の出力
モジュールのうちの１個の出力モジュールとの間のそれ
ぞれの中間リンクについて使用／不使用状態ビットを処
理するように構成することによって、複数の使用又は不
使用の状態のビットを同時に処理するステップからな
る、ことを特徴とする請求項１５の方法。 - 【請求項１８】 前記並行するパイプ探索演算を行うス
テップが、 １６個のリンク制御器を各クロスバー交換機制御器内に
設け各リンク制御器が前記交換基本構造と前記複数の出
力モジュールのうちの１個の出力モジュールとの間のそ
れぞれの中間リンクについて使用又は不使用の状態のビ
ットを処理するように構成することによって、１６個の
使用／不使用状態ビットを同時に処理するステップから
なる、ことを特徴とする請求項１５の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/521,676 US5724349A (en) | 1995-08-31 | 1995-08-31 | Terabit per second ATM packet switch having out-of-band control with multi casting |
| US521676 | 1995-08-31 |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001026683A Division JP3459235B2 (ja) | 1995-08-31 | 2001-02-02 | パケット交換装置及び同制御方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09130403A true JPH09130403A (ja) | 1997-05-16 |
| JP3177584B2 JP3177584B2 (ja) | 2001-06-18 |
Family
ID=24077668
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP23175996A Expired - Fee Related JP3177584B2 (ja) | 1995-08-31 | 1996-09-02 | パケット交換装置及び同制御方法 |
| JP2001026683A Expired - Fee Related JP3459235B2 (ja) | 1995-08-31 | 2001-02-02 | パケット交換装置及び同制御方法 |
Family Applications After (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001026683A Expired - Fee Related JP3459235B2 (ja) | 1995-08-31 | 2001-02-02 | パケット交換装置及び同制御方法 |
Country Status (8)
| Country | Link |
|---|---|
| US (1) | US5724349A (ja) |
| EP (1) | EP0760590A3 (ja) |
| JP (2) | JP3177584B2 (ja) |
| KR (1) | KR100396109B1 (ja) |
| CN (1) | CN1149222A (ja) |
| AU (1) | AU703210B2 (ja) |
| CA (1) | CA2180776C (ja) |
| SG (1) | SG48466A1 (ja) |
Families Citing this family (34)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6185222B1 (en) * | 1995-09-28 | 2001-02-06 | Cisco Technology, Inc. | Asymmetric switch architecture for use in a network switch node |
| US5905873A (en) * | 1997-01-16 | 1999-05-18 | Advanced Micro Devices, Inc. | System and method of routing communications data with multiple protocols using crossbar switches |
| US6618396B1 (en) | 1997-07-29 | 2003-09-09 | Matsushita Electric Industrial Co Ltd | Data transmitting device, data receiving device, and data recording device |
| US6526021B1 (en) * | 1998-04-03 | 2003-02-25 | Alcatel Network Systems, Inc. | Clear channel 1:N SONET transport system and method |
| SE514343C2 (sv) | 1998-10-21 | 2001-02-12 | Switchcore Ab | Metod och anordning för multicasting |
| US8245260B1 (en) | 1999-05-04 | 2012-08-14 | Unisys Corporation | Video server |
| US7784079B1 (en) | 1999-05-04 | 2010-08-24 | Unisys Corporation | Video on demand transaction server |
| US7106728B1 (en) | 2000-05-01 | 2006-09-12 | Industrial Technology Research Institute | Switching by multistage interconnection of concentrators |
| US7451474B1 (en) | 2000-05-15 | 2008-11-11 | Unisys Corporation | Set top network protocol |
| US6591285B1 (en) | 2000-06-16 | 2003-07-08 | Shuo-Yen Robert Li | Running-sum adder networks determined by recursive construction of multi-stage networks |
| JP3816314B2 (ja) * | 2000-07-11 | 2006-08-30 | 三菱電機株式会社 | パケット交換装置 |
| US7188357B1 (en) | 2000-11-16 | 2007-03-06 | Unisys Corporation | Video-on demand video server disk/memory streaming selection methodology |
| US7609695B2 (en) * | 2001-06-15 | 2009-10-27 | Industrial Technology Research Institute | Optimizing switching element for minimal latency |
| US7103059B2 (en) * | 2001-06-15 | 2006-09-05 | Industrial Technology Research Institute | Scalable 2-stage interconnections |
| EP1271825A1 (en) * | 2001-06-25 | 2003-01-02 | Lucent Technologies Inc. | Method and system for multiplexed optical information transport |
| CN100365961C (zh) * | 2004-01-15 | 2008-01-30 | 宁波隆兴电信设备制造有限公司 | 远程环回检测电路 |
| US7728664B2 (en) * | 2006-11-21 | 2010-06-01 | Broadcom Corporation | Low noise amplifier with multiple inputs and multiple outputs |
| US8868813B2 (en) | 2011-12-30 | 2014-10-21 | Bedrock Automation Platforms Inc. | Communications control system with a serial communications interface and a parallel communications interface |
| US9467297B2 (en) | 2013-08-06 | 2016-10-11 | Bedrock Automation Platforms Inc. | Industrial control system redundant communications/control modules authentication |
| US11144630B2 (en) | 2011-12-30 | 2021-10-12 | Bedrock Automation Platforms Inc. | Image capture devices for a secure industrial control system |
| US9437967B2 (en) | 2011-12-30 | 2016-09-06 | Bedrock Automation Platforms, Inc. | Electromagnetic connector for an industrial control system |
| US11314854B2 (en) | 2011-12-30 | 2022-04-26 | Bedrock Automation Platforms Inc. | Image capture devices for a secure industrial control system |
| US11967839B2 (en) | 2011-12-30 | 2024-04-23 | Analog Devices, Inc. | Electromagnetic connector for an industrial control system |
| US9600434B1 (en) | 2011-12-30 | 2017-03-21 | Bedrock Automation Platforms, Inc. | Switch fabric having a serial communications interface and a parallel communications interface |
| US9191203B2 (en) | 2013-08-06 | 2015-11-17 | Bedrock Automation Platforms Inc. | Secure industrial control system |
| US12061685B2 (en) | 2011-12-30 | 2024-08-13 | Analog Devices, Inc. | Image capture devices for a secure industrial control system |
| US10834820B2 (en) | 2013-08-06 | 2020-11-10 | Bedrock Automation Platforms Inc. | Industrial control system cable |
| US8862802B2 (en) | 2011-12-30 | 2014-10-14 | Bedrock Automation Platforms Inc. | Switch fabric having a serial communications interface and a parallel communications interface |
| US10834094B2 (en) | 2013-08-06 | 2020-11-10 | Bedrock Automation Platforms Inc. | Operator action authentication in an industrial control system |
| US8971072B2 (en) | 2011-12-30 | 2015-03-03 | Bedrock Automation Platforms Inc. | Electromagnetic connector for an industrial control system |
| US9727511B2 (en) * | 2011-12-30 | 2017-08-08 | Bedrock Automation Platforms Inc. | Input/output module with multi-channel switching capability |
| US10613567B2 (en) | 2013-08-06 | 2020-04-07 | Bedrock Automation Platforms Inc. | Secure power supply for an industrial control system |
| CN105281061A (zh) | 2014-07-07 | 2016-01-27 | 基岩自动化平台公司 | 工业控制系统电缆 |
| US9582209B2 (en) * | 2015-06-24 | 2017-02-28 | Vmware, Inc. | Efficient data deployment for a parallel data processing system |
Family Cites Families (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4035584A (en) * | 1975-12-08 | 1977-07-12 | Bell Telephone Laboratories, Incorporated | Space division network for time-division switching systems |
| US4592048A (en) * | 1984-05-03 | 1986-05-27 | At&T Bell Laboratories | Integrated packet switching and circuit switching system |
| US4686669A (en) * | 1985-02-07 | 1987-08-11 | American Telephone And Telegraph Company, At&T Bell Laboratories | Path hunting in a distributed control switching system |
| US4887079A (en) * | 1986-12-23 | 1989-12-12 | At&T Bell Laboratories | Rearrangeable multiconnection switching networks constructed using combinatorial designs |
| US4872158A (en) * | 1988-03-31 | 1989-10-03 | American Telephone And Telegraph Company, At&T Bell Laboratories | Distributed control rapid connection circuit switch |
| US5077483A (en) * | 1989-05-08 | 1991-12-31 | At&T Bell Laboratories | Network topology for reduced blocking and photonic system implementation thereof |
| US4993016A (en) * | 1989-05-08 | 1991-02-12 | At&T Bell Laboratories | Network control arrangement for processing a plurality of connection requests |
| US5040173A (en) * | 1989-05-08 | 1991-08-13 | At&T Bell Laboratories | Network control arrangement based on topological equivalence |
| US5258978A (en) * | 1989-05-08 | 1993-11-02 | At&T Bell Laboratories | Space-division switching network having reduced functionality nodes |
| US5122892A (en) * | 1989-05-08 | 1992-06-16 | At&T Bell Laboratories | Space-division switching network having reduced functionality nodes |
| GB2258366B (en) * | 1991-08-02 | 1995-03-29 | Plessey Telecomm | An ATM switching arrangement |
| US5241536A (en) * | 1991-10-03 | 1993-08-31 | Northern Telecom Limited | Broadband input buffered atm switch |
| US5291482A (en) * | 1992-07-24 | 1994-03-01 | At&T Bell Laboratories | High bandwidth packet switch |
| US5311345A (en) * | 1992-09-30 | 1994-05-10 | At&T Bell Laboratories | Free space optical, growable packet switching arrangement |
| US5345441A (en) * | 1992-10-20 | 1994-09-06 | At&T Bell Laboratories | Hierarchical path hunt for multirate connections |
| GB2273224B (en) * | 1992-12-05 | 1997-01-22 | Netcomm Ltd | An ATM Cell switch suitable for multicast switching |
| JP2655464B2 (ja) * | 1992-12-25 | 1997-09-17 | 日本電気株式会社 | パケット交換方式 |
| US5583861A (en) * | 1994-04-28 | 1996-12-10 | Integrated Telecom Technology | ATM switching element and method having independently accessible cell memories |
| US5544160A (en) * | 1994-12-30 | 1996-08-06 | At&T Corp. | Terabit per second packet switch |
-
1995
- 1995-08-31 US US08/521,676 patent/US5724349A/en not_active Expired - Lifetime
-
1996
- 1996-07-09 CA CA002180776A patent/CA2180776C/en not_active Expired - Fee Related
- 1996-07-25 SG SG1996010332A patent/SG48466A1/en unknown
- 1996-08-21 EP EP96306089A patent/EP0760590A3/en not_active Withdrawn
- 1996-08-26 AU AU64268/96A patent/AU703210B2/en not_active Ceased
- 1996-08-27 CN CN96111862A patent/CN1149222A/zh active Pending
- 1996-08-28 KR KR1019960036003A patent/KR100396109B1/ko not_active Expired - Fee Related
- 1996-09-02 JP JP23175996A patent/JP3177584B2/ja not_active Expired - Fee Related
-
2001
- 2001-02-02 JP JP2001026683A patent/JP3459235B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CA2180776C (en) | 2001-02-13 |
| JP3459235B2 (ja) | 2003-10-20 |
| JP3177584B2 (ja) | 2001-06-18 |
| CN1149222A (zh) | 1997-05-07 |
| JP2001244992A (ja) | 2001-09-07 |
| KR970013985A (ko) | 1997-03-29 |
| CA2180776A1 (en) | 1997-03-01 |
| AU6426896A (en) | 1997-03-06 |
| SG48466A1 (en) | 1998-04-17 |
| EP0760590A2 (en) | 1997-03-05 |
| US5724349A (en) | 1998-03-03 |
| AU703210B2 (en) | 1999-03-18 |
| EP0760590A3 (en) | 1999-05-12 |
| KR100396109B1 (ko) | 2003-11-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3459235B2 (ja) | パケット交換装置及び同制御方法 | |
| JPH09130404A (ja) | パケット交換装置 | |
| US5537403A (en) | Terabit per second packet switch having distributed out-of-band control of circuit and packet switching communications | |
| US5274642A (en) | Output buffered packet switch with a flexible buffer management scheme | |
| Tobagi | Fast packet switch architectures for broadband integrated services digital networks | |
| US5544160A (en) | Terabit per second packet switch | |
| Cidon et al. | Real-time packet switching: A performance analysis | |
| JPH10513334A (ja) | 切換方法及び装置 | |
| US6345040B1 (en) | Scalable scheduled cell switch and method for switching | |
| JPH08293877A (ja) | 通信システム | |
| JPH10285187A (ja) | Ａｔｍスイッチ用の分散形バッファリング・システム | |
| JPH08307432A (ja) | 通信方法 | |
| US5642349A (en) | Terabit per second ATM packet switch having distributed out-of-band control | |
| Wong et al. | Design and analysis of a novel fast packet switch-pipeline banyan | |
| JP3450110B2 (ja) | テラビット／秒パケットスイッチ | |
| Obara et al. | High speed transport processor for broad-band burst transport system | |
| Wong et al. | Pipeline banyan-a parallel fast packet switch architecture | |
| HK1003316A (en) | Terabit per second atm packet switch having out-of-band control with multicasting | |
| Li et al. | Design and implementation of a multicast-buffer ATM switch | |
| HK1003317A (en) | Terabit per second packet switch | |
| HK1003318A (en) | A terabit per second packet switch having assignable multiple packet loss probabilities | |
| Li | Design and evaluation of high-performance ATM switching architectures | |
| Al-Hashim | Design and analysis of a high-performance fault-tolerant ATM network | |
| Kaleemuddin | Evaluation of pipelined switch architectures for ATM networks | |
| SANG | PIPELINE BANYAN: DESIGN, ANALYSIS AND VLSI IMPLEMENTATION |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080406 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090406 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090406 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100406 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110406 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120406 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120406 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130406 Year of fee payment: 12 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130406 Year of fee payment: 12 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140406 Year of fee payment: 13 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |