JPH09130404A - パケット交換装置 - Google Patents
パケット交換装置Info
- Publication number
- JPH09130404A JPH09130404A JP23176096A JP23176096A JPH09130404A JP H09130404 A JPH09130404 A JP H09130404A JP 23176096 A JP23176096 A JP 23176096A JP 23176096 A JP23176096 A JP 23176096A JP H09130404 A JPH09130404 A JP H09130404A
- Authority
- JP
- Japan
- Prior art keywords
- pipe
- atm
- input
- controller
- output
- 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.)
- Pending
Links
- 230000006727 cell loss Effects 0.000 claims abstract description 55
- 238000004891 communication Methods 0.000 claims abstract description 35
- 230000006854 communication Effects 0.000 claims abstract description 35
- 239000013598 vector Substances 0.000 claims description 66
- 238000000034 method Methods 0.000 claims description 61
- 230000015654 memory Effects 0.000 claims description 36
- 238000005096 rolling process Methods 0.000 claims description 28
- 230000000903 blocking effect Effects 0.000 claims description 5
- 230000003111 delayed effect Effects 0.000 claims description 5
- 238000003860 storage Methods 0.000 claims description 5
- 125000004122 cyclic group Chemical group 0.000 abstract 2
- 238000012163 sequencing technique Methods 0.000 abstract 2
- 210000004027 cell Anatomy 0.000 description 163
- 239000004744 fabric Substances 0.000 description 25
- 238000012545 processing Methods 0.000 description 24
- 238000009826 distribution Methods 0.000 description 21
- 238000013459 approach Methods 0.000 description 20
- 238000010586 diagram Methods 0.000 description 18
- 230000006870 function Effects 0.000 description 18
- 239000000872 buffer Substances 0.000 description 10
- 238000003780 insertion Methods 0.000 description 10
- 230000037431 insertion Effects 0.000 description 10
- 238000013461 design Methods 0.000 description 9
- 230000005540 biological transmission Effects 0.000 description 6
- 238000004458 analytical method Methods 0.000 description 5
- 238000005290 field theory Methods 0.000 description 5
- 230000008901 benefit 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
- 230000008569 process Effects 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
- 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
- 238000013341 scale-up Methods 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
- 238000011084 recovery Methods 0.000 description 2
- 238000010845 search algorithm Methods 0.000 description 2
- 238000000638 solvent extraction Methods 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
- 230000002457 bidirectional effect Effects 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 238000005266 casting Methods 0.000 description 1
- 230000022131 cell cycle 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
- 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 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
- 230000008054 signal transmission Effects 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 230000005236 sound signal Effects 0.000 description 1
- 238000001228 spectrum Methods 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
- 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/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/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5647—Cell loss
-
- 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/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5651—Priority, marking, classes
-
- 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/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5652—Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
-
- 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〜１６V-1
（又は簡単に、出力モジュール）を有する。
【００４６】ＡＴＭ動作において、入力インタフェース
１２0〜１２N-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へ変換するためにファン
イン又は集線ファクタＦを有する。
基本構造１４のＦＮ個の出力をＮ個の出力モジュールの
出力ラインの出力Out0〜OutN-1へ変換するためにファン
イン又は集線ファクタＦを有する。
【００５０】各出力モジュール１６0〜１６V-1は、到着
ＡＴＭを先入れ先出し待ち行列に格納し、出力ポートが
利用可能なときに、これら先入れ先出し待ち行列の各々
の先頭にあるＡＴＭパケットを、望まれる出力ラインOu
t0〜OutN-1へルーティングする。
ＡＴＭを先入れ先出し待ち行列に格納し、出力ポートが
利用可能なときに、これら先入れ先出し待ち行列の各々
の先頭にあるＡＴＭパケットを、望まれる出力ラインOu
t0〜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 (19)
- 【請求項１】 複数の入力ラインから複数の出力ライン
に通信パケットを交換するパケット交換装置において、 （Ａ）前記複数の入力ラインのそれぞれの入力ラインに
接続された入力ポートと、出力ポートとを有する複数の
入力インタフェースと、 （Ｂ）複数の入力ポートを複数のＰ個の出力ポートに切
り換えるネットワークと、 前記（Ａ）の複数の入力インタフェースの出力は、前記
ネットワークのＩ個の入力ポートのそれぞれのグループ
Ｆにファンアウトされ、 前記（Ｂ）のネットワークは、複数のＣ個のパイプを有
する ここで、Ｃは、Ｐ／Ｉに等しい整数とする （Ｃ）複数の出力モジュールと、 前記複数のモジュールは、それら全体で複数の入力を有
し、 前記出力モジュールの入力は、前記複数のＰ個の出力ポ
ートのそれぞれの出力ポートに接続され、それら全体で
複数の出力を有し、前記複数の出力モジュールの出力
は、前記複数の出力ラインのそれぞれの出力ラインに接
続され、 前記Ｃ個のパイプの各々のパイプは、複数の出力ライン
のそれぞれの出力ラインに接続可能な複数の入力ライン
からのパスを有し、 （Ｄ）前記パケット交換装置を介して、通信パケット用
のパスを探索する複数の優先レベルを有する帯域外制御
器と、からなることを特徴とするパケット交換装置。 - 【請求項２】 前記入力インタフェースの各々は、通信
パケットを記憶する記憶装置を有し、 前記（Ｄ）の帯域外制御器は、制御器が未閉塞パスを探
索している間、第１パイプを介して第２パイプのパイプ
制御器の入力への閉塞されていない未閉塞パスを見出す
ことができない通信パケットと、前記入力インタフェー
スに記憶されている通信パケットと用のパスの要求をロ
ールすることを特徴とする請求項１の装置。 - 【請求項３】 前記入力インタフェースの各々は、通信
パケットを記憶する記憶装置を有し、 前記（Ｄ）の帯域外制御器は、制御器が未閉塞パスを探
索している間、第１パイプと第２パイプの両方を介して
第３パイプのパイプ制御器の入力への未閉塞パスを見出
すことができない通信パケットと、前記入力インタフェ
ースに記憶されている通信パケットと用のパスの要求を
ロールすることを特徴とする請求項１の装置。 - 【請求項４】 前記入力インタフェースの各々は、通信
パケットを記憶する記憶装置を有し、 前記（Ｄ）の帯域外制御器は、制御器が未閉塞パスを探
索している間、第１パイプと第２パイプと第３パイプを
介して第４パイプのパイプ制御器の入力への未閉塞パス
を見出すことができない通信パケットと、前記入力イン
タフェースに記憶されている通信パケットと用のパスの
要求をロールすることを特徴とする請求項１の装置。 - 【請求項５】 前記帯域外制御器は、内部ブロッキング
によるＡＴＭセルの損失の可能性を減らすために、参照
の順番をＡＴＭセルに割り当てることを特徴とする請求
項１の装置。 - 【請求項６】 前記帯域外制御器は、参照の順番をＡＴ
Ｍセルに割り当て、第１パイプと第２パイプと第３パイ
プを介して第４パイプのパイプ制御器の入力への未閉塞
パスを見出すことができない通信パケット用のパスの要
求をロールすることを特徴とする請求項１の装置。 - 【請求項７】 通信パケットを切り換えるパケット交換
装置において、 複数のＩ個の入力を、複数のＰ個の出力に切り換えるネ
ットワークと、 前記ネットワークは、複数のＣ個のパイプを有し、ここ
で、ＣはＰ／Ｉに等しい整数であり、 前記各パイプは、その入力をその出力に切り換えるそれ
ぞれのパターンを有し、前記パイプの切り換えパターン
は、他のパイプの切り換えパターンから独立しており、 前記複数のＰ個の出力に接続される複数の出力モジュー
ルと前記パケット交換装置を介して、通信パケット用の
パスを探索する複数の優先レベルを有する帯域外制御器
とを有することを特徴とするパケット交換装置。 - 【請求項８】 前記帯域外制御器は、第１パイプを介し
て第２パイプのパイプ制御器の入力への未閉塞パスを見
出すことができない通信パケットの要求をロールするこ
とを特徴とする請求項７の装置。 - 【請求項９】 前記帯域外制御器は、第１パイプと第２
パイプを介して第３パイプのパイプ制御器の入力への未
閉塞パスを見出すことができない通信パケットの要求を
ロールすることを特徴とする請求項７の装置。 - 【請求項１０】前記帯域外制御器は、第１パイプと第２
パイプと第３パイプを介して第４パイプのパイプ制御器
の入力への未閉塞パスを見出すことができない通信パケ
ットの要求をロールすることを特徴とする請求項７の装
置。 - 【請求項１１】 前記帯域外制御器は、内部ブロッキン
グによるＡＴＭセルの損失の可能性を減らすために、参
照の順番をＡＴＭセルに割り当てることを特徴とする請
求項７の装置。 - 【請求項１２】 前記帯域外制御器は、参照の順番をＡ
ＴＭセルに割り当て、第１パイプを介して第２パイプの
パイプ制御器の入力への未閉塞パスを見出すことができ
ない通信パケットの要求をロールすることを特徴とする
請求項７の装置。 - 【請求項１３】 前記帯域外制御器は、参照の順番をＡ
ＴＭセルに割り当て、第１パイプと第２パイプの両方を
介して第３パイプのパイプ制御器の入力への未閉塞パス
を見出すことができない通信パケットの要求をロールす
ることを特徴とする請求項７の装置。 - 【請求項１４】 前記帯域外制御器は、参照の順番をＡ
ＴＭセルに割り当て、第１パイプと第２パイプと第３パ
イプを介して第４パイプのパイプ制御器の入力への未閉
塞パスを見出すことができない通信パケット用の要求を
ロールすることを特徴とする請求項７の装置。 - 【請求項１５】 前記アウト部バンド制御器は、前記パ
ケット交換装置を介して、通信パケット用のパスを制御
し、見出し、確立することを特徴とする請求項７の装
置。 - 【請求項１６】 ＡＴＭパケットを交換するＡＴＭ交換
装置において、 （Ａ）ＡＴＭ通信ラインに接続されるそれぞれの入力と
出力とを有する複数のＡＴＭインタフェースカードと、 （Ｂ）複数のＩ個の入力をＰ個の出力に切り換えるネッ
トワークと、 前記ネットワークは、複数のＦ個のパイプを有し、 前記Ｆは、Ｐ／Ｉに等しい整数であり、 前記入力インタフェースの各出力は、前記Ｆ個のパイプ
のそれぞれの入力に接続されて、Ｆ倍でファンアウトさ
れ、 前記各パイプは、その入力をその出力に切り換えるそれ
ぞれのパターンを有し、 前記パイプの各切り換えパターンは、他のタイプの切り
換えパターンから独立しており、 （Ｃ）前記複数のＰ個の出力に接続され、複数の出力を
有する複数の出力モジュールと、 （Ｄ）ＡＴＭパケット用の前記ＡＴＭ交換装置を介し
て、前記複数の入力インタフェースの一つの入力から、
前記複数の出力モジュールの一つの所望の出力へのパス
を探索する複数の優先レベルを有する帯域外制御器と、
を有することを特徴とするＡＴＭ交換装置。 - 【請求項１７】 前のＡＴＭパケット期間の間、ＡＴＭ
パケットが閉塞されており、次のＡＴＭパケット期間の
間、ＡＴＭパケット用の前記ＡＴＭ交換装置を介して、
前記複数の入力インタフェースのうちの一つの入力か
ら、前記複数の出力モジュールのうちの一つの所望の出
力へのパスを探索するために、前記複数の入力インタフ
ェースのある入力インタフェースは、二つのＡＴＭパケ
ット期間の間、ＡＴＭパケットを記憶するメモリを有す
ることを特徴とする請求項１６の装置。 - 【請求項１８】 前記遅延したＡＴＭパケットは、タイ
ムスタンプを使用することなしに、前記ＡＴＭ交換装置
を介して、その出力モジュールのそれぞれの所望の出力
に適切なシーケンスで通信されることを特徴とする請求
項１７の装置。 - 【請求項１９】 前記複数の入力インタフェースのある
入力インタフェースは、 各来入ＡＴＭパケット用の優先フィールドを読み出す手
段と、 前記優先フィールド内の値に基づいて、パイプ探索期間
の間、そのＡＴＭパケットに割り当てられた要求ベクト
ルを解放する手段と、を有することを特徴とする請求項
１７の装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/522,209 US5724352A (en) | 1995-08-31 | 1995-08-31 | Terabit per second packet switch having assignable multiple packet loss probabilities |
| US522209 | 1995-08-31 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH09130404A true JPH09130404A (ja) | 1997-05-16 |
Family
ID=24079920
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP23176096A Pending JPH09130404A (ja) | 1995-08-31 | 1996-09-02 | パケット交換装置 |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US5724352A (ja) |
| EP (1) | EP0760589A3 (ja) |
| JP (1) | JPH09130404A (ja) |
| CN (1) | CN1149223A (ja) |
| AU (1) | AU701967B2 (ja) |
| CA (1) | CA2180775C (ja) |
| SG (1) | SG48467A1 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2006065457A (ja) * | 2004-08-25 | 2006-03-09 | Fuji Xerox Co Ltd | インタフェース回路生成装置およびインタフェース回路 |
| JP2007096676A (ja) * | 2005-09-28 | 2007-04-12 | Fujitsu Ltd | ネットワーク構成装置およびネットワーク構成方法 |
Families Citing this family (39)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6067286A (en) * | 1995-04-11 | 2000-05-23 | General Datacomm, Inc. | Data network switch with fault tolerance |
| US6188690B1 (en) * | 1996-12-12 | 2001-02-13 | Pmc-Sierra, Inc. | Method and apparatus for high speed, scalable communication system |
| US5856977A (en) * | 1997-05-15 | 1999-01-05 | Yang; Muh-Rong | Distribution network switch for very large gigabit switching architecture |
| KR100212064B1 (ko) | 1997-05-21 | 1999-08-02 | 윤종용 | 2n X n 다중화 스위치 구조 |
| US6192049B1 (en) * | 1997-07-15 | 2001-02-20 | Lucent Technologies Inc. | Jitterless and lossless switching fabric with network routing |
| JP3077647B2 (ja) * | 1997-11-04 | 2000-08-14 | 日本電気株式会社 | コンセントレータ型ａｔｍスイッチシステム |
| GB2334651A (en) * | 1998-02-18 | 1999-08-25 | Power X Limited | Scheduling means for data switching apparatus |
| US6772256B1 (en) * | 1998-05-27 | 2004-08-03 | Micron Technology, Inc. | Routing arbiter for data network switching |
| US6636932B1 (en) * | 1998-05-27 | 2003-10-21 | Micron Technology, Inc. | Crossbar switch and control for data networks switching |
| EP0986226B1 (en) | 1998-09-11 | 2007-01-17 | Hitachi, Ltd. | Ip packet communication apparatus |
| US6611518B1 (en) * | 1998-09-18 | 2003-08-26 | Samsung Electronics Co., Ltd. | Methods and apparatus for flexible device interface port assignment in a data communications switching system |
| JP3344383B2 (ja) * | 1999-10-04 | 2002-11-11 | 日本電気株式会社 | スケジューラ |
| US6724758B1 (en) * | 1999-12-20 | 2004-04-20 | Cisco Technology, Inc. | Stage specific dilation in multi-stage interconnection networks |
| US7016365B1 (en) * | 2000-03-31 | 2006-03-21 | Intel Corporation | Switching fabric including a plurality of crossbar sections |
| JP3816314B2 (ja) * | 2000-07-11 | 2006-08-30 | 三菱電機株式会社 | パケット交換装置 |
| US6721313B1 (en) | 2000-08-01 | 2004-04-13 | International Business Machines Corporation | Switch fabric architecture using integrated serdes transceivers |
| US6885679B1 (en) * | 2000-09-29 | 2005-04-26 | Nortel Networks Limited | System and method for layer 2 frame delineation recovery |
| US6868085B1 (en) | 2000-10-27 | 2005-03-15 | Telefonaktiebolaget Lm Ericsson (Publ) | Method for parallel searching a look-up table |
| US6894970B1 (en) * | 2000-10-31 | 2005-05-17 | Chiaro Networks, Ltd. | Router switch fabric protection using forward error correction |
| US7420969B2 (en) * | 2000-11-29 | 2008-09-02 | Rmi Corporation | Network switch with a parallel shared memory |
| US7050391B1 (en) * | 2000-12-22 | 2006-05-23 | Turin Networks | Method and apparatus for efficient link redundancy |
| KR20020054207A (ko) * | 2000-12-27 | 2002-07-06 | 오길록 | 분배결합 패킷 스위칭 장치 |
| US20020136229A1 (en) * | 2001-01-09 | 2002-09-26 | Lucent Technologies, Inc. | Non-blocking crossbar and method of operation thereof |
| US6608836B2 (en) * | 2001-05-10 | 2003-08-19 | Turin Networks | Method and apparatus for egress channel architecture that supports protection within SONET/sdh based networks |
| US6999468B2 (en) * | 2001-06-04 | 2006-02-14 | Turin Networks | Method and apparatus for line and path selection within SONET/SDH based networks |
| US7031261B1 (en) | 2001-06-04 | 2006-04-18 | Turin Networks | Method and apparatus for egress channel architecture that supports protection within SONET/SDH based networks |
| EP1271825A1 (en) * | 2001-06-25 | 2003-01-02 | Lucent Technologies Inc. | Method and system for multiplexed optical information transport |
| US7154887B2 (en) * | 2001-07-12 | 2006-12-26 | Lsi Logic Corporation | Non-blocking grooming switch |
| GB0215504D0 (en) * | 2002-07-04 | 2002-08-14 | Univ Cambridge Tech | Hybrid electro-optic packet and cell switch |
| US7551640B1 (en) * | 2002-09-20 | 2009-06-23 | Cisco Technology, Inc. | Method and apparatus for errorless frame timing adjustment |
| US7656880B1 (en) * | 2004-06-09 | 2010-02-02 | Verizon Laboratories Inc. | Prioritized segmentation and reassembly methods and systems |
| US7382185B1 (en) * | 2004-09-10 | 2008-06-03 | Rockwell Collins, Inc. | Loop segment switching system |
| US7873056B2 (en) * | 2004-11-18 | 2011-01-18 | Nec Corporation | Switch device, switching method and switch control program |
| US7356638B2 (en) * | 2005-10-12 | 2008-04-08 | International Business Machines Corporation | Using out-of-band signaling to provide communication between storage controllers in a computer storage system |
| US8363649B2 (en) * | 2007-05-25 | 2013-01-29 | Konda Technologies Inc. | Fully connected generalized multi-link multi-stage networks |
| US7683665B1 (en) | 2009-04-21 | 2010-03-23 | International Business Machines Corporation | Multiple parallel programmable finite state machines using a shared transition table |
| US8958418B2 (en) * | 2011-05-20 | 2015-02-17 | Cisco Technology, Inc. | Frame handling within multi-stage switching fabrics |
| US10523500B2 (en) * | 2017-09-26 | 2019-12-31 | Quanta Computer Inc. | Method and system for automatically configuring fanout mode of a network switch port in an interconnected network |
| US11146505B2 (en) | 2018-01-11 | 2021-10-12 | Intel Corporation | Low latency compact Clos network controller |
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 |
| US5122892A (en) * | 1989-05-08 | 1992-06-16 | At&T Bell Laboratories | Space-division switching network having reduced functionality nodes |
| US5040173A (en) * | 1989-05-08 | 1991-08-13 | At&T Bell Laboratories | Network control arrangement based on topological equivalence |
| US5077483A (en) * | 1989-05-08 | 1991-12-31 | At&T Bell Laboratories | Network topology for reduced blocking and photonic system implementation thereof |
| US5258978A (en) * | 1989-05-08 | 1993-11-02 | At&T Bell Laboratories | Space-division switching network having reduced functionality nodes |
| US4993016A (en) * | 1989-05-08 | 1991-02-12 | At&T Bell Laboratories | Network control arrangement for processing a plurality of connection requests |
| US5453981A (en) * | 1990-10-16 | 1995-09-26 | Kabushiki Kaisha Toshiba | Method of controlling communication network incorporating virtual channels exchange nodes and virtual paths exchange nodes |
| EP0533900B1 (en) * | 1991-04-10 | 1997-08-06 | Koninklijke Philips Electronics N.V. | Low delay or low loss cell switch for atm |
| GB2258366B (en) * | 1991-08-02 | 1995-03-29 | Plessey Telecomm | An ATM switching arrangement |
| 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 |
| JP3178949B2 (ja) * | 1993-09-30 | 2001-06-25 | 富士通株式会社 | Ａｔｍスイッチ方式 |
| JP2655481B2 (ja) * | 1994-04-28 | 1997-09-17 | 日本電気株式会社 | 出力バッファ型ａｔｍスイッチにおける優先制御方法 |
| US5544160A (en) * | 1994-12-30 | 1996-08-06 | At&T Corp. | Terabit per second packet switch |
-
1995
- 1995-08-31 US US08/522,209 patent/US5724352A/en not_active Expired - Fee Related
-
1996
- 1996-07-09 CA CA002180775A patent/CA2180775C/en not_active Expired - Fee Related
- 1996-07-25 SG SG1996010345A patent/SG48467A1/en unknown
- 1996-08-21 EP EP96306084A patent/EP0760589A3/en not_active Withdrawn
- 1996-08-26 AU AU64269/96A patent/AU701967B2/en not_active Ceased
- 1996-08-27 CN CN96111863.6A patent/CN1149223A/zh active Pending
- 1996-09-02 JP JP23176096A patent/JPH09130404A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2006065457A (ja) * | 2004-08-25 | 2006-03-09 | Fuji Xerox Co Ltd | インタフェース回路生成装置およびインタフェース回路 |
| JP2007096676A (ja) * | 2005-09-28 | 2007-04-12 | Fujitsu Ltd | ネットワーク構成装置およびネットワーク構成方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5724352A (en) | 1998-03-03 |
| CN1149223A (zh) | 1997-05-07 |
| EP0760589A2 (en) | 1997-03-05 |
| CA2180775C (en) | 2001-02-13 |
| EP0760589A3 (en) | 1999-01-13 |
| SG48467A1 (en) | 1998-04-17 |
| CA2180775A1 (en) | 1997-03-01 |
| AU6426996A (en) | 1997-03-06 |
| AU701967B2 (en) | 1999-02-11 |
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 | |
| Tobagi | Fast packet switch architectures for broadband integrated services digital networks | |
| US5274642A (en) | Output buffered packet switch with a flexible buffer management scheme | |
| US5544160A (en) | Terabit per second packet switch | |
| JPH08293877A (ja) | 通信システム | |
| JPH10285187A (ja) | Ａｔｍスイッチ用の分散形バッファリング・システム | |
| EP0977404A2 (en) | Scalable scheduled cell switch and method for switching | |
| Chao et al. | Design and implementation of Abacus switch: A scalable multicast ATM switch | |
| 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) | テラビット／秒パケットスイッチ | |
| 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 | |
| HK1003318A (en) | A terabit per second packet switch having assignable multiple packet loss probabilities | |
| HK1003317A (en) | Terabit per second packet switch | |
| Pashan et al. | Technologies for broadband switching | |
| Wu | Network approach to ATM traffic management: BISDN system modeling and simulation | |
| Shyy et al. | On-board B-ISDN fast packet switching architectures. Phase 2: Development. Proof-of-concept architecture definition report | |
| Kaleemuddin | Evaluation of pipelined switch architectures for ATM networks | |
| SANG | PIPELINE BANYAN: DESIGN, ANALYSIS AND VLSI IMPLEMENTATION | |
| OKAMOTO | Modular Expandable Multi-Stage ATM Cross-Connect System Architecture for ATM Broadband Networks | |
| Li | Design and evaluation of high-performance ATM switching architectures |