JPH0349334A - 多段ネットワーク制御方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は通信ネットワークの制御に係わり、特に回線交
換式ネットワークとパケット交換式ネットワークの両方
に適用することが出来、利用可能なネットワークの経路
を迅速に決定してそのような経路を介する通信を可能に
する装置に関する。

［従来の技術］ 多重ステージ交換ネットワークを通る経路の捜し出しを
実行することが要求されたときは、そのネットワークを
介して回線交換式ネットワーク或いはパケット交換式ネ
ットワークが確立され得る速度は事実上制限される。こ
の経路捜し出しの処理には、基本的に確定すべきことが
三つ、即ち、１）ある与えられたネットワーク入口とあ
る与えられたネットワーク出口との間に一つ以上の経路
を識別すること、２）これら識別されたの中のいずれか
の経路がネットワークの全ステージを通じて空き状態で
あるか否かを決定すること、３）もし前記識別された経
路の中で一つ以上の経路が空き状態であれば、一つの経
路を特定の通信に利用するために選択すること、の三つ
が含まれる。−旦、ある空き経路が選択されると、その
経路を介する通信を可能にするために更に制御動作が必
要となる。「ベル・システム・テクニカル・ジャーナル
（Ｂｅｌｌ　　Ｓｙｓｔｅｍ　　Ｔｅｃｈｎｉｃａｌ　
　Ｊｏｕｒｎａｌ）Ｊ、１９６４年９月号の２２０８頁
乃至２２１４頁に掲載されているＡ。

フェイナ−（Ａ、Ｆｅ１ｎｅｒ）氏等の論文に開示され
ているように、ＩＥＳＳ（登録商標）交換機設計におい
て決定すべき基本的な事項は、経路捜し出しの機能を交
換機のネットワーク自体から分離することである。セン
トラル・プロセッサーは全経路の捜索を行ない、そのメ
モリーに関連する全ての交換動作情報の連続した記録を
保持する。

幾つかの経路が一時に捜索されるが、この捜索において
は、ネットワークの二つのステージ（段）の話中／空き
情報を組合わせである結果を得る動作と、それに続いて
この結果を第三ステージ等の話中／空き情報を組合わせ
る動作とが順次行われる。ネットワークの設計は、音声
情報、画像情報、データ情報に亘る広い揮類の通信、特
にフォトニック（光）通信領域で履行されるように設計
されたネットワークに発展するので、ステージ順次の経
路捜し出しを用いて回線交換式ネットワーク或いはパケ
ット交換式ネットワークを設定することが出来るトラン
ザクション速度は、特に複数のステージを含む大規模な
ネットワークにおいてネットワークの性能を著しく制限
することとなろう。

（解決手段） 上記従来の問題点は、単一のソフトウェア制御プロセッ
サーを用いずに、ステージに特定されている話中／空き
情報を各ステージに対する個々のメモリーを利用して記
憶し、且つ経路の捜し出しが全ステージに対する話中／
空き情報を順次にではなく、むしろ同時に組合わせるこ
とによって達成するハードウェアを用いて履行される典
型的な通信ネットワーク制御構成での本発明の原理に従
って解決することが出来、技術的な発展を達成すること
が出来る。ここに記載された例示的なネットワークにと
っては、一連の入口番号、経路番号及び出口番号から成
る単一の２進数が所定入口と所定出口との間の特定のネ
ットワーク経路を独自に識別する。前記所定の入口及び
出口間のネットワーク経路に対して全経路の構成要素、
例えばネットワークのノードやリンクに対するステージ
の話中／空き情報はステージ・メモリーの一つのアドレ
スに記憶される。ある特定ステージのメモリー・アドレ
スは入口及び出口番号のビットの特定の小セットである
。全ステージに対して全ての空き経路を同時に決定する
ためにメモリーの読み取りが同時に行われ、ある経路が
選択された後で全ステージ・メモリーが同時に更新され
る。選択された経路に関連する経路番号を持つ入口及び
出口の連続する番号を含む２進数のビットのうち、ステ
ージに特有のサブセットが、その経路の全構成要素にア
クセスして通信出来るようにするために用いられる。

本発明による方法は、それぞれがネットワークステージ
のうちの一つのステージにステージの話中／空き情報を
記憶する複数のメモリーを有する複数ステージネットワ
ーク装置で使用される。

ステージの話中／空き情報は特定のネットワーク入口か
らそのネットワークを通り特定のネットワーク出口に達
する空き経路を捜し出すために、少なくとも三つのメモ
リーから同時に組み合わされる。

例示されたネットワーク制御装置（第１図）は５１２Ｘ
５１２の多重ステージ・クロスオーバ型ネットワーク（
第３８図）を制御するために用いられる。このネットワ
ークは特定入口から特定出口に達する複数の経路を持っ
ている。各ステジ・メモリーは全ての経路に対するステ
ージの話中／空きビットを特定入口と特定出口に基づい
てアドレス可能な一つの記憶場所に記憶する。これらス
テージの話中／空きビットは全経路及び全ステージに関
して同時に読み出される。これら読み出されたビットに
基づいて一つの空き経路が決定され、ステージの話中／
空き情報が全ステージに関して同時に更新される。決定
された経路を通信可能にするようにネットワーク制御動
作が行われる。回線切断要求が受信されたときは、ステ
ージの話中／空き情報が空き状態への回復を規定するた
めに全ステージに関して同時に更新される。ネットワー
ク制御装置はその経路を通じる通信が出来なくなるよう
にし、経路メモリーからその経路情報を消去する。

ネットワークの各交換ノードはその二つ以上の入力リン
クに同時に受信されている通信を伝送することが可能で
あるから、ネットワーク経路の捜し出しを達成するため
に用いられるステージの話中／空き情報は個々のリンク
の話中／空き状態を規定する。各ステージ・メモリーは
、それぞれが幾つかのビット位置を持つ複数のアドレス
可能な記憶場所を有する。各ビット位置は関連するステ
ージのリンクの中の一つのリンクにステージの話中／空
き情報を記憶する。複数の入口信号はネットワーク入口
の中のいずれか一つの入口を表わすためにコード化され
、複数の出口信号はネットワーク出口の中のいずれか一
つの出口を表わすためにコード化される。所定の入口信
号及び出口信号から各ステージ・メモリーのアドレスが
生成される。ステージの話中／空き情報は経路を捜し出
すためにアドレスされた全記憶場所の全ビット位置から
同時に読み出される。−旦空き経路が決定されると、ス
テージの話中／空き情報は全ステージ・メモリーで同時
に更新される。複数の経路信号が、ネットワーク入口と
ネットワーク出口との間の複数の経路のうちのいずれか
一つの経路を表わすためにコード化される。所定の入口
信号、出口信号及び経路信号がある与えられたステージ
の特定のリンクを通じる通信を可能にするために用いら
れる。

代わりに、ネットワークの各交換ノードが一時に一つの
通信のみを伝えるために用いられるときは、ネットワー
ク経路の捜し出しを達成するために用いるステージの話
中／空き情報が、リンクでは無くノードの話中／空き状
態を規定する。

本発明の一つの特定の例示的実施例は、５１２Ｘ５１２
の多重ステージ・クロスオーバ型ネットワーク１２００
（第３８図）を制御するネットワーク制御装置１３００
（第１図）に用いられる。

ネットワーク１２００の規模及びこの規模のネットワー
クで経路捜し出しを遂行することの潜在的な複雑さを良
く理解するために、先ず１６Ｘ１６のクロスオーバ型ネ
ットワーク１１７０（第３４図乃至第３６図）に言及し
、且つステージ間のクロスオーバ接続パターンに言及す
る。第３７図は１６Ｘ１６のネットワーク１１７０の規
模と５１２ｘ５１２のネットワーク１２００の規模とを
相対的に表わす図である。更に中間的な規模を持つ１２
８Ｘ１２８のネットワークが示されている。

クロスオーバ型ネットワーク１２００（第３８図）は１
５個のステージを有するが、ステージ１．２．３．１３
．１４及び１５は交換機能を遂行せず、単にＦ−８のフ
ァン・アウト／ファン・インを履行するために用いられ
る。ネットワーク制御装置１３００は、クロスオーバ型
ネットワーク１２００に対し、複数のステージ制御器１
２０１乃至１２０９を介して個々にステージ４乃至１２
に関する経路捜し出し、接続及び切断を遂行するために
用いられる。この実施例においては、交換ステージ４乃
至１２のノードは第６図のノードのような完全な能力を
持つ交換ノードである。

ネットワーク制御装置１３００　（第１図）は、それぞ
れがクロスオーバ型ネットワーク１２００のリンク・ス
テージの中の一つのリンク・ステージにステージの話中
／空き情報を記憶する、複数のステージ争メモリー１３
１２を有する。ステージの話中／空き情報はクロスオー
バ型ネットワーク１２００の特定入口からクロスオーバ
型ネットワーク１２００の特定出口への空き経路を捜し
出すために、全ステージ・メモリー１３１２から同時に
組み合わされる。クロスオーバ型ネットワーク１２００
は、特定入口から特定出口への８個の経路を有する。各
ステージ・メモリー１３１２は、８個の経路の全部に関
するステージの話中／空きビットを、特定入口及び特定
出口に基づいてアドレスすることが出来る一つの記憶場
所に記憶する。

これらステージの話中／空きビットは全経路及び全ステ
ージに対して同時に読み出される。８個の話中／空き検
査ユニットが、８個の経路の全部について総合的な話中
／空き状態を決定する。空き経路選択ユニット１３１６
は個々の通信に使用するために空き経路の中の一つの空
き経路を選択する。全ステージ・メモリー１３１２は、
選択された経路を話中状態として規定し直すために同時
に更新される。信号は選択された経路を通信可能にする
ようにノード拳ステージ制御器１２０１乃至１２０９へ
伝送され、その経路を規定する情報が経路メモリー１３
１８に書き込まれる。回線切断要求が受信されると、ス
テージの話中／空き情報は再び空き状態を表わすために
全ステージ・メモリー１３１２内で同時に変更される。

信号はその経路を通じる通信が出来なくなるようにする
ためにステージ制御器１２０１乃至１２０９（第３８図
）へ伝送され、その経路情報は経路メモリー１３１８（
第１図）から消去される。

（実施例の説明） 本発明の説明は、以下の２つの部分から構成される。第
１に、ブロックを減少させたネットワークトポロジーに
ついて説明する。このトポロジーは、フォトニック領域
で実施されるのが望ましい。

第２に、速く経路を発見し、ブロックを減少させたネッ
トワークを介して通信を確立するネットワーク制御構成
について述べる。

ネットワークトポロジー 第２図は、拡張（ファンアウト）セクション１６１０と
、完全シャツフル等価ネットワーク１６２０と、および
集束（ファイン）セクション１６３０とからなるシステ
ム１６００の線図である。システム１６００はＮ−４個
の入口およびＭ−４個の出口とををする。完全シャツフ
ル等価ネットワーク１６２０は、２×２ノードからなる
４つのノード段（ステージ）１６２１−０．１６２１−
１．１６２１−２．１６２１−３と、および各々が連続
するノード段を完全シャツフル相互接続させるところの
３つのリンク段１６２２−０．１６２２−１．１６２２
−２とを含む。拡張セクション１６１０は、Ｎ−４個の
入口を第１ノード段１６２１−０の１６個（Ｎ個より大
）の入力に拡張する。

集束セクション１６３０は最終ノード段１６２１−３の
１６個（Ｍ個より大）の出力をＭ−４個の出口へ集束す
る。システム１６００は、Ｎ個の入口の各々とＭ個の出
口の各々との間に、２以上の経路を有する。ノード段１
６２１−０．１６２１−１．１６２１−２．１６２１−
３の個々のノードは、シャツフルネットワーク制御器１
６５０からの命令に応答して、対応の段制御器１６４０
．１６４１．１６４２．１６４３によって制御される。

拡張セクション１６１０とおよび集束セクション１６３
０との３つの代替態様を、第３図、第４図、第５図に示
す。拡張セクション１７１０　（第３図）においては、
Ｎ−４個の入口の各々は、ノード段１６２１−０の４個
の入力に直接接続されている。集束セクション１７３０
においては、ノード段１６２１−３の４個の出力が、Ｍ
−４個の出口の各々に直接接続されている。拡張セクシ
ョン１８１０　（第４図）は、１×４ノードの単一段１
８１１を有し、集束セクション１８３０は４Ｘ１ノード
の単一段１８３１を有する。拡張セクション１９１０　
（第５図）はＩＸ２ノードの２つの段１９１１，１９１
２を有し、集束セレクション１９３０は２×１ノードの
２つの段１９３１．１９３２を有する。拡張セクション
１７１０．１８１０．１９１０の各々は、Ｎ個つ入口の
各々を、本文内で定義されるような完全シャツフル維持
パターン内でノード段１６２１−０の多重入力に接続す
る。集束セクション１７３０．１８３０．１９３０の各
々は、ノード段１６２１−３の多重出力を、本文内で定
義されるような完全シャツフル維持パターン内でＭ個の
出口の各々に接続する。

システム１６００において使用される３種類の代替２×
２交換ノード１５１０．１５２０．１５３０を第６図、
第７図、第８図に示す。ｎ個の入力と、ｍ個の出力とを
有するノードは、それが、ｍｉｎ　　（ｎ、ｍ）個の信
号を同時に伝送可能ならば、それは全容量ノードである
という。ノードが一時に１つの信号のみしか伝送出来な
いならば、そのノードは一容量ノードであるという。−
８二ノードには、入力または出力のいずれかを選択可能
であるものと、選択不能なものとがある。

全容量ノードであるノード１５１０　（第６図）は、２
つの選択器１５１１．１５１２を含む。選択器１５１１
は、選択信号Ｓ１に応答してノード入力１１、Ｉ２のい
ずれかをノード出力ｏ１に接続する。選択器１５１２は
、選択信号Ｓ２に応答してノード入力１１、Ｉ２のいず
れかをノード出力ｏ２に接続する。

入力選択可能−容量ノードであるノード１５２０（第７
図）は、２つのＡＮＤゲート１５２１．１５２２と、１
つのＯＲゲート１５２３とを含む。

ＡＮＤゲート１５２１は、選択信号Ｓ１に応答して、信
号を入力■１からＯＲゲート１５２３を経由して両方の
出口０１．０２に伝送する。ＡＮＤゲート１５２２は、
選択信号Ｓ２に応答して信号を入力Ｉ２からＯＲゲート
１５２３を経由して、両方の出力０１．０２に伝送する
。任意の時間においては、選択信号Ｓ１、Ｓ２のうちの
１つのみが論理１である。

選択不能−容量ノードであるノード１５３０（第８図）
は、１つのＯＲゲート１５３１と、１つのＡＮＤゲート
１５３２とを含む。制御信号Ｃが論理１であるとき、Ａ
ＮＤゲー）１５３２は入力１１、Ｉ２における信号の論
理和集合を両方の出力０１．０２に伝送する。制御信号
Ｃが論理０であるとき、ＡＮＤゲート１５３２は論理０
を両方の出口０１．０２に伝送する。任意の時間におい
ては、人力１１、Ｉ２のうちの１つのみが能動信号を受
取る。

ノード１５３０は、本明細書でｎＸｍモジュールと呼称
されるさらに一般化された交換ノードの特殊例を示す。

ｎ個の入力とｍ個の出力とを有するｎｘｍモジュールは
、ｎ個の入力における信号の論理和集合をｍ個の出力す
べてに経路選択するか、ｎ個の入力における信号のいず
れをもｍ個の出力のいずれにも経路選択しないか、のい
ずれかである。もしｎＸｍモジュールのネットワークが
、ｎｘｍモジュールのたかだか１個の入力が能動信号を
有するように制御されるならば、ｎＸｍモジュールは信
号をｍ個の出力のすべてに経路選択するか、ｍ個の出力
を空き（アイドル）のままにするか、のいずれかである
。ノード１５３０は２×２モジユールであり、本明細書
では２モジユールともいう。

システム１６００　（第５図）が、完全シャツフル等価
ネットワーク１６２０の交換ノードとしてのノード１５
３０、拡張セクション１９１０．集束セクション１９３
０のような、２モードを使用して具体化されたとき、完
全シャツフル等価ネットワーク１６２０の２モジユール
は、２モジユールのいずれもただ１つの能動入力信号し
か有しないように、必要に応じて個々に不能化（ｄｌｓ
ａｂｌｅ）されるかまたは可能化（ｅｎａｂｌｅ）され
る。

最終拡張ノード段１９１２の２モジユールも、Ｎ個の入
力のある１つで受取られた信号が、ノード段１６２１−
０の２つの２モジユールのみに伝送されるように個々に
不能化されるかまたは可能化される（第５図に図示せず
）。特定の２モジユール出力がある論理値にロックされ
てしまうような故障に対するシステム１６００の許容度
を改善するために、拡張セクションおよび集束セクショ
ンのすべての２モジユールを制御可能にしても良い。

第９図は、Ｎ−４個の入口と、Ｍ−１６個の出口とを有
するシステム１６０１の線図である。システム１６０１
は、集束セクション１６３０が必要とされていないこと
を除けば、システム１６００（第２図）と同一である。

第１０図は、Ｎ−１６個の入口と、Ｍ−４個の出口とを
有するシステム１６０２の線図である。

システム１６０２は、拡張セクション１６１０が必要と
されていないことを除けば、システム１６００（第２図
）と同一である。

システム１６００のようなシステムのブロッキング特性
について説明する前に、厳密に非ブロッキングなネット
ワークの機能的原理について説明する。ネットワークが
厳密非ブロッキングであるための条件は、任意の入力−
出力対の間の最小経路数が、その対の間でブロック可能
な最大経路数を超えていなければならないということで
ある。

しかし、ネットワークが、厳密に非ブロッキングである
ための十分条件（しかし必要条件ではない）は、任意の
入力−出力対の間の最小経路数が任意の入力−出力対の
間でブロック可能な最大経路数を超えることである。式
の形で表示すれば、この十分条件は次の様になる； 経路≧ブロックされる経路＋１ ネッ；・ワークが有効であるための属性は、経路とブロ
ックされる経路との数の変動が、任意の入力−出力対選
択に対して、きわめてわずかなこと（または全く変動し
ない）である。

単一段の厳密に非ブロッキングなネットワーク１００２
を第１１図に示す。ネットワーク１００２において、任
意の入力−出力対の間の経路の最少数は１に等しい。各
水平レールは入力に１対１で関係し、また各垂直レール
は出力に１対１で関係するので、ブロックされる経路は
存在しない。

したがって、次の関係を得る。

経路−１≧ブロツクされる経路＋１−０＋１したがって
、ネットワーク１００２は、厳密非ブロツキングネット
ワークである。ネットワーク１００２にはＮＸＭ個の交
差点があるが、−時に使用される交差点の数は多くとも
ｍｉ　ｎ　　（Ｎ、　Ｍｌである。より効率的なネット
ワークを形成するために、ブロックされる可能性のある
経路数よりもさらに多くの経路を形成してしかも同時に
交差点の数を減少するように多重段が使用される。

２４Ｘ２４の厳密非ブロツキング３段クロス（Ｃ１ｏｓ
）ネットワーク１００４を第１２図に示す。各々の入口
と出口との間には、それぞれ中間段のスイッチを１つず
つ通過する５つの経路が存在する。任意の入口（出口）
は、そのスイッチ上の他の２個の入口（出口）によって
２つの経路がブロックされることもある。したがって、
厳密非ブロツキング条件を適用すると、次の関係を得る
：５≧（２＋２）　＋１゜ ネットワーク１００４内の交差点の数は３×５×８＋８
ｘ８ｘ５＋５ｘ３ｘ８−５６０である。比較のために計
算すると、２４Ｘ２４クロスバ−ネットワークは５７６
個の交差点を有する。

−膜化厳密非ブロッキング３段クロスネットワーク１０
０６を第１３図に示す。（第１３図においては股間リン
クは省略されている。）厳密非ブロツキング条件をネッ
トワーク１００６に適用すると、任意の入力−出力対の
間の経路の最小数はｒである。ブロックされる経路の最
大数は（ｎ　−１）＋（ｎ−１）に等しく、したがって
、ｒ≧ｎ十ｍ−１であるならば、ネットワーク１００６
は厳密非ブロッキングである。８段クロスネットワーク
において、ある役向の各スイッチを３段クロスネットワ
ークで単に置き換えることにより、８段クロスネットワ
ークから反復的にＳ＋２段クロスネットワークが形成可
能である。第１４図に示すような厳密非ブロヅキング５
段クロスネットワーク１００８は、図示されている数の
股間リンクを有する。ホトニック（光）領域においてク
ロスネットワークを具体化するときの２つの問題点は：
１）交換要素が正方形でなくかつ大型であること、２）
股間リンクの数が異なること（位置的に中心に行くほど
増加する）である。

多段相互接続ネットワーク（ＭＩＮ）１０１０を第１５
図に示すが、このネットワーク（ＭＩＮ）は次の５つの
条件によって定義される；（１）ＭＩＮは、ある任意数
Ｓのノード段を有する； （２）段ｉには、「１個のノードがあり、各々ノードは
ｎ４個の入力と、ｍ１個の出力とを有する。； （３）異なる段にあるノードは、異なるｎ９、ｍｌの値
を有する； （４）１≦ｉ≦Ｓ−１において、段ｉ内のノードの出力
は、（リンクを経由して）段ｉｌｌ内のノードの入力に
接続される； （５）１≦ｉ≦Ｓ−１に対しては、ｒ、ｍ、−１＋１　
　　ｉｌｌ　。

拡張−膜化シャッフル（ＥＧＳ）ネットワーク１０１２
を第１６図に示す。ＥＧＳは特定仕様のリンク相互接続
パターンを備えたＭＩＮである。

任意の段ｉにおいて、ノードには連続的に０からｒｌ−
１までの番号が付けられ、また特定ノードの出力には連
続的に０からのｍ、−１までの番号が付けられている。

次に段ｉのノードの出力には、連続的に０からｒｉ　ｍ
ｉ　−１までの番号が付けられ；したがって、ｘ８番目
のノード上の０１番番目 の出力には、ｘ　ｊｍ　ｊ＋　ＯＩの番号が付けられて
いる。ＥＧＳ相互接続パターンは次のように説明できる
。段ｉ内の出力ｘｉ　ｍｉ　＋ＯＩは段ｉ＋１内のノー
ド（ＸｉｍＩ＋０１）ｍｏｄｒ１＋１に接続される。こ
の相互接続パターンは、リンクを次の役向のノードに連
続的に割り当てる（いわゆる完全シャツフル）。ＥＧＳ
相互連続パターンの主要な意味は、与えられた２つの段
の中の任意の２つのノード間の経路の数が、１より大き
い数だけ異なることはないことである。ｉくｊに対して
は、段ｉ内のノードと段ｊ内のノードとの間の経路の数
は であり、ここで　Ｘ　はＸ以上の範囲の最小整数を示し
、また　Ｘ　はＸ以下の範囲の最大整数を示す。Ｎ−ｎ
　ｓ　　ｒ　ｓ個の入口とＭｗａｍＳｒ、個の出口とを
有するＥＧＳネットワークを考えてみる。

任意の入口−出口対の間の経路の最小数は、によって与
えられる。

ＥＧＳネットワークの例１０１４を第１７図、第１８図
に示す。入力Ｘと出力ｙとの間の経路の数を求めるため
に、次の計算を行う。

入力Ｘと出力ｙとのチャネルグラフ（線図）Ｌ（ｘ、　
　ｙ）は、Ｘとｙとの間のすべての和集合（ｕｎｉｏｎ
）である。ブロックされる経路の数の上限を求めるため
には、任意のチャネルグラフをインターセクト（ｉｎｔ
ｅｒｓｅｃｔ　；交差）可能な呼の数と、６呼がブロッ
ク可能な経路の数とを求めなければならない。チャネル
グラフを第１９図に太線で示す。

第２０図において、チャネルグラフＬ　（ｘ、　　ｙ）
は、破線で示されている。１つのインターセクト呼（第
２０図において太線で示す）はＬ　（ｘ、　　ｙ）の３
つの経路の１つをブロックする。ノード段ｉからノード
段ｊ　　（ｊ＞ｉ）へのｊ−４リンク上でＬ　（ｘ、ｙ
）とインターセクトする呼を考えてみる。ノード段ｋか
らノード段に＋１へのリンクを段にリンクとして表すこ
とにする。インターセクト呼Ｃ（ｉ、ｊ）のリンクｉに
よってブロックされる入力Ｘと出力ｙとの間の経路の数
は、ＸからＣ（ｉ、ｊ）の段ｉノードへの経路の数と、
Ｃ（ｉ、　　ｊ）の段ｊ＋ｌノードからｙへの経路の数
との積で与えられる。任意の入力（すなわち段１ノード
）から任意の段ｉノードへの経路の最大数は、 であり、また任意の段ｉ＋１から任意の出力（すなわち
８段ノード）への経路の最大数はである。したがって、
Ｘとｙとの間の経路のうちＣ（ｉ、　　ｊ）のリンクｉ
によってブロックされる経路の最大数は、 である。リンクｔ＋１によってブロックされる経路の追
加数は、 によって与えられる。第２項の引算項は、第１項がリン
クｉによってブロックされるいくつかの経路；すなわち
、リンクｉを経由してリンクｉ＋１に到達するすべての
これらの経路を含むことに対する補正である。Ｃ（ｉ、
ｊ）の残りのリンクの各々に対して同様な補正を行うと
、Ｃ（ｉ、ｊ）によってブロックされる経路の数は次式
によって与えられることがわかる。

ブロックされる経路（ｉ、ｊ） であるような段Ｕが存在しなければならない。

ネットワーク１０１２　（第２１図）を参照するとき、
次のことを考慮されたい。

ｎ　≦Ｎ１．■ｎ、　　　　　はｋにおいて非減少であ
るので、１≦ｋｉｔに対して すべての入口は、すべての段ｔ＋１ノードに至る少なく
とも１つの経路を有することと、インクセクト呼Ｃ（ｉ
、ｊ）はｉ≦ｔ＋１を有し、であるようなある段ｔが存
在しなければならない。

同様に、Ｕ≦に≦Ｓに対して さなければならないことである。この情報のすべてを使
用して、ブロックされる経路に対する表現が、 ブロックされる経路（ｉ、ｊ） となる。ここで通常のように、ｔ＋１≧ｕ−２は、すべ
てのインターセクト呼に対して定数である。したがって
、単一のインターセクト呼によってブロックされる経路
上の上限が、エントリー点、出発点プラス定数の分離的
関数である。

ここで、チャネルグラフをインターセクト可能な呼の最
大数を求めることが残されている。単一のインターセク
ト呼によってブロックされる経路の数はエントリー点、
出発点プラス定数の分離的関数であるので、各段におい
てエントリー点、シかも出発可能な呼の最大数を求める
だけでよい。

ある呼のエントリー点および出発点を組み合わせる必要
は無い。ここで、特定の条件に合致するネットワークの
連続段の任意のセットに対して成立するＥＧＳネットの
重要な性質（前方向−後方向不変特性といわれる）を考
える。もし前方向−後方向不変特性が、ネットワークの
ある部分に対して成立するならば、各段における着呼お
よび発呼の最大数は極端に減少可能である。

前方同一後方向不変特性（ＦＢＩＰ）はつぎのように説
明可能である。ある段ｉノードによって到達されること
が可能なすべての段ｊノードは正確に同一セットの段ｉ
ノードに到達する。

ト！ ｎｍｋ　　　　が、「ｊを割り切れるならば、ＦＢＩＰ
はＥＧＳネットワーク内の段１１段ｊに対して成立する
。ネットワーク１０１４に対する段３と段５とのあるノ
ード間の経路が第２２図内で太線で示されている。任意
の段３ノードによって到達されることが可能なすべての
段５ノードは正確に同一セットの段３ノードに到達する
。ＦＢＩＰは、それがインターセクト呼を著しく減少し
かつ多段モジュール化を形成する。

第２３図に示すネットワーク１０１２を参照して、ＦＢ
ＩＰが段１から段ｌまでに対して成立すれると仮定する
。したがって、ある入口Ｘによって到達されることが可
能なすべての段ｉノードは正確に同一セットの第１段ノ
ードすなわち入口に到達する。任意の段ｉノードはたか
だか■ｎ、　　　　個の入口（段ｉから段１までのｌ ＩＰが段ｉ＋２から段Ｓまでに対して成立するな段ｉ＋
２（第２３図の点Ｂ）から出て、段Ｓに到達することが
可能である。最悪のケースを考えて、段ｉにおいて、ま
たは段ｉの前で入るすべての呼が段ｉ＋１において、ま
たは段ｉ＋１の前で出ることおよび段ｉ＋２の後で出る
すべての呼が段ｉ＋１においてまたは段ｉ＋１の後で入
ることと仮定しよう。したがって、１≦ｉ≦Ｓ−２のあ
るｉられる。ｉに対して最小化し、かったかだか、ｍ１
ｎ（Ｎ−１、Ｍ−１）個の呼がチャネルグラフをインタ
ーセクト可能であることを考慮して、チャネルグラフを
インターセクトする呼の最大数ωは、 （第２３図の点Ａ）までのチャネルグラフＬ　（ｘ、　
　　　によって与えられるという結果をえる。この結ｙ
）に入ることが可能である。同様に、もしＦＢ　　　　
果を得るのに使用される独立変数は、もしＦＢＩら段ｉ
までのものに対して、また　　■鴨≦ω・ｐ＝ｊ が成立するすべての段ｊから段Ｓまでのものに対して成
立するならばそれは妥当である。

したがって、これまでに、 （１）任意の入口−出口対の間にすくなくとも（２）段
ｉにおいてチャネルグラフに入り、かつ段ｊにおいてチ
ャネルグラフを出る呼によってブロックされるたかだか 対してＭを割り切れるならば、チャネルグラフをインタ
ーセクトするたかだか が存在するということを求めてきた。したがって、さら
に求めなければならないものは、チャネルグラフの各段
において入りかつ出るところの呼の最大数である。

ネットワーク１０１２　（第２３図）において、段１か
ら段ｊまでの点Ａにおいて、たかだかｒＩｎＰ−１個の
呼がＬ　（ｘ、ｙ）に入ることがａｌ 可能である。しかしまた、段１から段ｉまでにたかだか
Ｗ個の呼が入ることが可能である。ネットワーク１０１
２の段ｉ＋２から段Ｓまでの点Ｂかから出ることが可能
である。しかしまた、段ｉ＋２から段ＳまでたかだかＷ
個の呼がでることが可能である。したがって、ｍ１ｎ（
［ｎｐ−１・ω］　個の呼が段１から段ｉまでに入るこ
とが可能であり、まここで厳密非ブロツキングＥＧＳネ
ットワークであるための基本的条件は； でに入ることが可能である。

段ｉ−１から入る呼 の最大数を仮定すると、 段ｉにおいて入るたかだ 得られる。

また同様に、 段ｉにおいて出るたかだ 得られる。

おいて入る呼の最大数、 ロックされる経路の数、 において出る呼の最大数、 り切れ、 また ｒＩｍＰ≦ω。

Ｊ に対して、 ロックされる経路の数、 ■）　　　がＭを割り切れ、 Ｊ トワークにおいて、 およびそのネッ ωはインターセクト呼の最大数、 および はすべてのインターセクト呼に対するブロックされる経
路の一定成分である。

したがって、次のことが厳密非ブロッキングＥＧＳネッ
トワークに対する基本定理ということが可能である二Ｎ
−ｎ１１１個の入口と、Ｍ　−ｍ　８ｒ　個の出口とを
有する任意のＥＧＳネットワーりであって、そのネット
ワークにおいて、であり、 ここで ｔは ■ｎｐ膠・ となるようなｉの最大値、 Ｕは　　Ｈｍｐ儲、　　　となるようなｊの最小値、て
α−−１）であって、そのネットワークにおいであると
ころの任意のＥＧＳネットワークは点対点接続に対して
厳密に非ブロッキングである。

以上の展開は、全容量ノード（容量−ｍｉｎ（ｎ、、ｍ
、！　）を仮定してきた。同様な展開は、選択可能−容
量ノードに対して、また選択不能−容量ノードに対して
行うことが可能である。変数αを導入することによって
別の結果を同時に得ることができ、全容量ノードに対し
てはα−１、選択可能−容量ノードに対してはα−〇１
選択不能−容量ノードに対してはα−−１である。した
がって、厳密非ブロッキングＥＧＳネットワークに対す
る基本定理は次のように言える： Ｎ−ｎ１　ｒ１個の入口と、Ｍｍｍｓｒｓ個の出口とを
有する任意のＥＧＳネットワーク（ここで全容量ノード
に対してα−１、選択可能−容量ノードに対してα−０
、選択不能−容量ノードに対し門 ■ラ　　がＭを割り切れ、およびそのネット四 ワークにおいて、 であり、ここで、 ｔは ｒＩｎＰ粥。

となるようなｉの最大値、 Ｕは　ＩＩｒｎ、、＜Ｍ、　　となるようなｉの最小値
、であるところの任意のＥＧＳネットワークは点対点接
続に対して厳密非ブロッキングである。

ＥＧＳネットワークの設計にきわめて大きなフレキシビ
リティがあることは、主として、非ブロツキング動作に
対する条件が総体的（グローバル）なものであり、かつ
その条件がＮ％Ｍ、α、およびｎｌとｍｌとの種々の積
にのみ依存としてい、ることからきている。このように
、一般に、非ブロツキング条件は特定のｎｌとｍｌとの
間の関係には関係しない。

非ブロッキングＥＧＳネットワークの一例１０１６を第
２４図に示す。このネットワークの各膜内の出力リンク
が次の段（完全シャツフル）内のノードに順次に割り当
てられるならば、ネットワークの現状接続状態にかかわ
らず、任意の空き入力は、任意の空き出力に接続が可能
であり、すなわちこのネットワークはＭ密非ブロッキン
グである。

多段相互接続ネットワーク（Ｍｉｓ）Ｇは、次の２条件
のいずれかが成立するならば、完全シャツフル等価ネッ
トワークであると言われる。

条件１； Ｇのすべての段ｌに対して、 のみであるならば、Ｇの段ｉ内のノードαが、Ｇの段ｉ
十１内のノードβに接続されるように、Ｇの段ｉノード
ｒ１から、整数セット（０，１，・・・条件２； Ｇのすべての段ｉに対して、 のみであるならば、Ｇの段ｉ＋１内のノードβが、Ｇの
段ｉ内のノードαに接続されるように、Ｇの段ｉノード
ｒｓから、整数セット（０，１，・・・ｒ、−１１への
１対１マツピングｖｌが存在する。

ＥＧＳネットは、各Φ、が単に同一マツピングであると
きに、条件１が成立するという点で、完全シャツフル等
価ネットワークである。

条件１ｅ： Ｃ１が整数、 １ｒＩ □工Ｆ。

であり、 （ここで　　◆１ｅ：Ｃ１，）のみであるならば、入口
αがＧの段１内のノードβに結合されるように、ＧのＮ
個の入口から整数セット　（０，１，・・・Ｎ−１）へ
の１対１マツピングΦ１が存在する。

トのＳマツピングΦ、を表し、 条件２ｅ： １ｒＩ Ｃ２が整数、　１「＝Ｐであり、 トのＳマツピングｖＩを表す。

拡張手段は、次の２条件のいずれかが成立するならば、
完全シャツフル保持パターンにおいて、ＧのＮ個の入口
の各々を、Ｇの第１段ノードの多重入力に接続するもの
と言える。

（ここで　Ｖｌ　６　Ｃ２，）のみであるならば、Ｇの
段１内のノードβが６の入口αに接続されるように、Ｇ
のＮ個の入口から整数セット＋０．１゜・・・、Ｎ−１
１への１対１マツピング１ｖｌが存在する。

集束手段は、次の２条件のいずれかが成立するならば、
完全シャツフル保持パターンにおいて、Ｇの最終段Ｓの
ノードの多重出力をＧのＭ個の出口の各々に接続するも
のと言える。

条件ＩＣ： Ｃ７＞＜整数、　　み１２ド　　であり、Ｉ　　　　　
　　Ｍ （ここで　　φ、εＣ１，）のみであるならば、Ｇの段
Ｓ内のノードαが出口βに接続されるように、ＧのＭ個
の出口から整数セット１０，１．・・・２Ｍ−１）への
１対１マツピングΦ０が存在する。

条件２ｃ： ５ｒ３ Ｃ２が整数、　　Ｔ＝ドであり、 （ここで　マＳεＣ２・　　　）のみであるならば、出
口がＧの段Ｓ内のノードαに接続されるように、ＧのＭ
個の出口から整数セット＋０．　１．・・・１Ｍ−１）
への１対１マツピングＶｏが存在する。

このような拡張手段とおよび集束手段とを備えたネット
ワークＧは、Ｎ個の１×Ｆノードの拡張段と、後続のＧ
の８個の段と、後続のＭ個のＦ−×１ノードの集束段と
からなるｓ＋２段の完全シャツフル等価ネットワークと
等測的に表すことが可能である。もし条件１（２）が成
立するならば、Φ１　（マｌ）が、Ｎ個の入口ノードに
適用されて、条件１ｅ（２ｅ）に従って、入口ノードα
がＧの段１内のノードβに接続され、およびΦ。（’Ｖ
ｏ）がＭ個の出口ノードに適用されて、条件ＩＣ（２Ｃ
）に従って、Ｇの段Ｓ内のノードαが出口ノードβに接
続される。厳密非ブロツキング条件に関する上記の定理
は、このようなネットワークに適用される。

第２５図に示すクロスオーバーネットワーク１０２０は
完全シャツフル等価ネットワークである。

このことは、各役向のノードのラベル付けと段の間の相
互接続とを調べることによって、容易に確認できる。完
全シャツフル等価ネットワークに、このような規則化さ
れた物理的相互接続パターンが存在することは、具体化
を考慮するときに重要である。

段ごとに２に個の２Ｘ２ノードを設けたクロスオーバー
ネットワークにおいては、各リンク段ｉは２ｒｉ個の分
割を有するクロスオーバ相互接続パターンからなり、こ
こでｒｉ　ｇ　Ｉ（ｋ）　＝　（０，１，＝−、に−１
）である。

「１に対して選択される種々の値は、ネットワークの性
能および接続性に大いに影響する。

ｒｉ選択の１つのきわめて有用なパターン（完全シャツ
フル等価ネットワークを形成する）は、１　　（Ｋ）の
任意の順列によってｒｔ、ｒｚ、・・・ｒｋを与える事
であり、 ｉ≧ｋに対しては　　　ｒＨ＝ｒｊ （ここでｊ　＝　１　＋　（１−１）ｍａｄ　ｄ　’す
なわち’に＋１　”　ｒｌ、ｒｋ＋２　＝　ｒ２＋”’
Ｊ２ｋ　＝　’に＋　　などである。

完全シャツフル等価ネットワーク群にないネットワーク
に対応する多くの他の有用なパターンが存在する。

第２６図に示すＥＧＳネットワーク１０２２は完全シャ
ツフル等価ネットワークの重要な特殊ケースを示す。ネ
ットワーク１０２２においては、Ｓ’；Ｊ、　ｎ１＝１
．　ｍ１＝Ｆ、　ｒ４＝Ｎ、　ｎ５＝Ｆ、　Ｍ５＝＝１
．　ｒ５＝＋Ｎ、であり、また、ここで、次のように定
義する。

Ｐ　（Ｂ）−ある空き状態の入口および出口が接続可能
比ない（ブロックされる）確率。

Ｐ　（Ｆ）−段２ないし段Ｓ−１内のあるｎＸｎノード
が故障のために使用不能である確率。

０ＣＣ−ある入口または出口が話中である確率。

α−〇　−容量ｎＸｎノード（選択可能）に対して。

α−１全容量ｎｘｎノードに対して。

すると： Ｎ、Ｆ、ｎ、Ｓ、Ｐ　（Ｂ）、ＯＣＣおよびαはによっ
て近似的に関係づけされる。

３≦Ｓ≦２ｉｏ＆Ｎ＋１−ｃｃに対して、次のように定
義する：すなわち ８段を有するネットワークに対してＰｓ（Ｂ）＝　ＰＣ
Ｂ）。

このとき： Ｐ　　　（Ｂ）およびＰ　　（Ｂ）は、ｓ＋１　　　　
　　　　　　　　　　　　ｓｐｓ＋１（Ｂ）　＝　ｐ、
（Ｂ）ｒｎ（１−Ｐ（Ｆ）＞（ｎ−１）ｎ’−ｘ　ＯＣ
Ｃ／Ｆｌによって近似的に関係づけられる。

大であり、Ｐ　　ＣＢ）はＳに対して２乗で減少する；
すなわちＳに対してプロットされたＰｓ（Ｂ）＝　１−
　およびＰｓ＋ｔ（Ｂ）　＝　［Ｐｓ（Ｂ）１２．　　
ト仮定ｔ　ル。

このとき ＰＳ＋１　＝　（Ｉｆｆ″’）２＝　１０−２．　Ｐｓ
＋２（Ｂ）　＝　（ｔｏ−２１２＝　１０″、　ＰＳ＋
３（Ｂ）　＝　［１０−’］Ｑ：　１０ジ ＰＳ＋４（Ｂ）　＝＋＋　［１ｆｆ”１２＝　１０−”
、となる。従って、このようなネットワークにおいて、
単に４個の段を加えることによって、ブ０ツキングの確
率を１０　から１０−１６に減少した。

ブロッキングの確率に対する前の近似表示は、８段のノ
ードを備え、段ｉがｎ、Ｘｍ１ノードがらなり、Ｎ−ｎ
ｌｒｌ個の入口とＭ−ｒ８ｍＳ個の出口とを有する任意
の完全シャツフル等価ネットワークＧに対して一般化可
能である。Ｐ　（Ｆ）−０，０ＣＣ−１、α−１と置く
と、Ｇにおけるブロッキングの確率Ｐ　（Ｇ）は、近似
的に、で与えられる。

この劇的な効果を表すために、 Ｐ（Ｇ）　（，５は、ブロッキングの確率がすべてにお
いて有意である。適用例に使用されるネットワークに対
するひかえめなしきい値である。

（以下余白） ネットワーク制御 第１６図に示すネットワーク１０１２は、リンクを連続
的に次の段のスイッチに単に割り当てた相互接続パター
ン、すなわち完全シャツフル相互接続を有するＥＧＳネ
ットである。ネットワーク１０１２において任意の入口
Ｘと任意の出口ｙとの間の経路の数Ｐは、 によって与えられる。Ｉ（ｋ）は整数セット　（ｏ。

１、・・・、に−１）を表すものとする。入口Ｘがら出
口ｙへのある経路を３列の数字（ｘ＋　”’、ｙ）、こ
こで２本はＩ　（Ｐ）の要素、で表す。経路（ｘ、Ｐ’
、ｙ）は、　Ｍ４　　に対して段ｉのを通過する。段ｉ
と段ｉ１１との間のリンクを段ｉリンクとして表す。経
路（ｘ、Ｐ＊、ｙ）は１≦ｉ＜Ｓ−１・　に対して段ｉ
のスイッチを利用する。

第２７図はスイッチが全容ｆｌ　、ｃａｐ（Ｓθ＝而可
面Ｌｍｉ）。

であるネットワーク１０１２において、経路探索（ハン
ト）を行うのに使用される経路探索処理の流れ図である
。処理は、ブロック１１０２から始まり、以前に未チエ
ツクの経路２本が選択される。

ブロック１１０４において、１≦ｉ≦Ｓ−１の範囲すべ
てのｉに対してＬ　　（ｘ、Ｐ＊、ｙ）の話中／空き状
態がチエツクされる。判定ブロック１１０６において、
すべてのＬ　　（ｘ、Ｐ＊、ｙ）が空きでないと判定さ
れると、処理は判定ブロック１１１０へ進む。ブロック
１１１０において、他の未チエツク経路があるか否かが
判定される。

もしあれば処理は、ブロック１１０２に戻り、新たな未
チエツク経路に対して、処理の流れ図が反復される。し
かし、判定ブロック１１１０において、他の未チエツク
経路が存在しないと判定されたならば、処理は、ブロッ
ク１１１２に分岐して、ここで入口Ｘと出口ｙとの間の
全ての経路が、ブロックされていると結論づけられる。

ネットワーク１０１２のスイッチは全容量であると仮定
されたので、第２７図の流れ図においてリンクＬ、がチ
エツクされる。

第２８図はスイッチが一容量すなわちＣａＰ（Ｓ＋）＝
　１゜であるネットワーク１０１２において、・経路探
索（ハント）を行うのに使用される経路探索処理の流れ
図である。処理はブロック１１２２から始まり、ここで
は以前に未チエツクの経路Ｐ＊が選択される。ブロック
１１２４において、１≦ｉ≦Ｓの範囲の全てのｉに対し
てＳ　１　　（ｘ　、Ｐ　’　、　　ｙ　）の話中／空
き状態がチエツクされる。判定ブロック１１２６におい
て、全てのＳ、（ｘ、Ｐ’、ｙ）！ が空きであるか否かの判定がなされる。

全てのＳｌ　　（ｘ、Ｐ＊、ｙ）が空きであるならば、
処理はブロック１１２６からブロック１１２８に進み、
ここで入口Ｘを出口ｙに接続するために、経路Ｐ＊が使
用可能であると結論づけられる。ブロック１１２６にお
いて、全てのＳ（ｘ、Ｐ＊ｙ）が空きでないと判定され
たならば、処理は判定ブロック１１３０へ進む。ブロッ
ク１１３０において、他の未チエツク経路があるか否か
が判定される。あれば、処理はブロック１１２２に戻り
、新たな未チエツク経路に対して処理の流れ図が反復さ
れる。しかし、もし判定ブロック１１３０において、他
の未チエツク経路が存在しないと判定されたならば、処
理は、ブロック１１３２に分岐して、ここで入口Ｘと出
口ｙとの間の全ての経路がブロックされているとは結論
づけられる。ネットワーク１０１２のスイッチは一容量
であると仮定されたので、第２８図の流れ図においては
スイッチＳ、がチエツクされる。

ネットワーク１０１２に対する経路探索を行うときに、
平行作業が可能である。全てのｉおよび＊ Ｐ　に対する全てのＳｌ　　（ｘ、Ｐ’、ｙ）またはＬ
−（ｘ、ＰＩ　　ｙ）の話中／空き状態が同時に読取り
可能であり、したがって、全てのＰ経路について、それ
らが話中かまたは空きかを同時に求めることが可能であ
る。もし空きがあれば、このとき空きとして見出された
ものの中から、特定の経路が選択される。

考えているネットワークが、ＥＧＳネットワークでなく
、ＥＧＳネットワークの異種同形のモデルであるならば
、経路選択アルゴリズムを適用する前に、入口Ｘおよび
出口ｙはそれらのＥＧＳ等価物にマツプ化されなければ
ならない。スイッチを作動するには逆のマツプ化が必要
とされる。

もし各入口／出口対に対する全ての経路が他の全ての入
口／出口対に対する全ての経路から分離されているなら
ば、多重接続の上にオーバーラツプ動作を行うことが可
能である。

便宜上、　　　　　ｎｍｊ：＝Ｍ１．　　　　と表す。

ト もしＭがＭｌを割切れるならば、以前に与えられたＰＳ
Ｓｌ　（ｘ、ｐ＊　、Ｙ）およびり、　　（Ｘ。

Ｐ＊、ｙ）に対する等式は次の様になる：ｐ＝− Ｎ＝Ｍ＝２”、　１１　＝ｍ３　＝　１．　ｍｌ　＝ｎ
ｇ　＝２’　＝Ｆ、であり、かつ２≦ｉ≦Ｓ−１に対し
てｎ　１−ｍ　１−２　（ここでｎ、には整数）である
ところのネットワークＧを考える。このとき、 Ｍｌ　＝　２ｓ−２ｘ　Ｆ　＝　２ｓ−２ｘ　２に＝　
２”−２ＭＨ＝２銅である。

したがって、項ｘＭ１　＋　Ｐ”Ｍ　＋　’ｙは、ｘ２
５＋に−２＋　ｐ傘２°＋ｙとなり、ｘ、ｙは整数値０
．１．・、２　−１の範囲であり、Ｐ＊は整数値０，１
．・・・、２Ｓ＋に″２−１　　の範囲である。従って
、　　Ｐ”２”　　は値０．２ｎ、２’２’−３’２”
ｌ”・、２ｓ＋に＝−２”　　　　　　　　ヲ有Ｌ、マ
ｔ：　ｐ傘りｎ＋ｙ　　ｌ；！Ｏから　２５＋に−２−
１までの全ての整数値の範囲である。また、　　Ｘ・２
Ｓ＋に−２は、値０，２Ｓ＋に−２，、、，２３＋に＋
ｎ−２−２５＋に−２ヲ有Ｌ、従ッテ、ｘ２５＋に−２
＋　ｐ中２ｎ　＋ｙ　　は０から　２５＋に＋ｎ−２−
１　　　マチの全ての整数値の範囲である。従って、戊
、＋Ｐ”Ｍ　＋ｙユｘ２Ｓ＋に−２やＰゆ２１やｙ　　
は次のようなＳ＋に＋ｎ−２ビットの２進数として表す
ことが可能である； また、　ｒＩ＝ｒｓ＝Ｎ＝Ｍ＝２ｎ　　　と、２≦ｉ≦
Ｓ−１に対して、　ｒｉ＝二五へ＝２ｎ＋に一１とが得
られる。さらに、２≦ｉ≦Ｓに対して２≦ｉ≦Ｓ−１に
対して、次の表現を考えてみる。

２進数を２Ｓ−ｉで割って、底関数をとることは、２進
数をＳ−ｉ桁だけ右に移動することと等価である。従っ
て、 ｘＭｌ　＋　Ｐ”Ｍ　＋　ｙ、　　の２進表示の右から
ｌｏｇ　２　Ｍｔビットだけ移動されたｌｏｇ２ｒ、ビ
ットの窓（つ２進数に等価である： ｎ＋に−１ ２進数のモジュロ（法）２　　　は２進数の最古側ｎ＋
に一１ビットによって与えられる。従っ２進数に等価で
ある； 従って、Ｓｔ　　（ｘ、Ｐ’、ｙ）は、右からｌｏｇ　
２　Ｍ＋＋ｔビットだけ移動されたｌｏｇ２（ｒ　１ｍ
＋　）ビットの窓によって与えられる。

シャツフルネットワークのスイッチおよびリンクの入口
／出口および経路番号に対する関係を、第２９図に示す
例示的ネットワーク１１４０について説明する。第３０
図は、単一２進数を形成するための、入口１３７、経路
４１７、出口２９１の連鎖２進表示を示す。第３１図は
、２進数の連続ビットの中のある数を単に選択すること
により、ある役向の特定のスイッチの決定が可能である
ことを示す。段２のスイッチと段１６のスイッチとを識
別するために使用される特定の１１個の連続ビットが第
３１図に示されている。同様に、段２および段１６内の
特定のリンクを識別するために使用される１２個の連続
ビットもまた示されている。１１個のビットストリング
は２０４８個のスイッチの中から１個を識別する。１２
個のビットストリングは、４０９６個のリンクの中から
１個を識別する。第３１図にはまた、スイッチおよびリ
ンクを識別するために使用された連続ビットに隣接する
ビットを基礎にして、種々の段の特定の入力および出力
を識別するための方法も示されている。たとえば、段２
、段１６の入力が識別され、段１、段２、段１６の出力
が、識別されている。

ネットワーク１１４０に対しては、出力経路選択は「自
己経路選択」であって、入力に対しては独立である。

クロスオーバネットワークとシャツフルネットワークと
は異種同形である。２つのネットワークタイプの種々の
段の間の変換を第３２図に略図で示す。第３２図におい
て識別されている特定の変換が、本明細書内で第１表−
第３表に記載されている。第３２図において、ブロック
１１５０内に識別されているクロスオーバネットワーク
のｉ段のスイッチおよび出力とブロック１１５４内に識
別されているシャツフルネットワークの段ｉのスイッチ
および出力とは、ブロック１１５２の変換１．２．３．
４によって関係づけられている。同様に、ブロック１１
６０内に示されているクロスオーバーネットワークの段
ｉ＋ｌに対するスイッチおよび入力と、ブロック１１６
４内に示されているシャツフルネットワークの段ｉ＋ｌ
に対するスイッチおよび入力とは、ブロック１１６２の
変換９，１０．１１．１２よって定義されているように
、関係づけられている。クロスオーバネットワークに対
する段ｉのスイッチおよび出力番号と、クロスオーバネ
ットワークに対する段ｉ＋１のスイッチおよび入力番号
との間の変換は、ブロック１１５６の変換１３，１４．
１５．１６によって定義されている。シャツフルネット
ワークの連続段の間の対応関係は、ブロック１１５８の
変換５゜６．７．８によってあたえられる。変換工ない
し１６が第１表−第３表に記載されている。各変換に対
して、変換されるべき数値はＢ。−１・・・８１６ｏに
よって表されるｎビットの２進数である。

矛 ワ 表 ここで、５１２Ｘ５１２クロスオーバネツトワーク１２
００　（第３８図）を制御するための装置について説明
する。このようなネットワークの大きさをよりよく理解
するために、まず１６Ｘ１６クロスオーバネツトワーク
１１７０　（、第３４図−第３６図）を参照して、段か
ら段へのクロスオーバ接続のパターンに注目されたい。

第３７図は、１６Ｘ１６ネツトワーク１１７０と５１２
Ｘ５１２ネツトワーク１２００との相対的大きさを示し
たものである。そこには中間的大きさである１２８Ｘ１
２８ネツトワークも示されている。クロスオーバネット
ワーク１２００　（、第３８図）は１５個の段を含む：
しかじ、段１．　２．　３．　１３．　１４．１５は、
スイッチング機能を行わず、ファンアウト／ファンイン
Ｆ−８を実行するためにのみ使用される。クロスオーバ
ネットワーク制御器１３００は、それぞれ段４ないし段
１２に、付属の複数の膜制御器１２０１ないし１２０９
を介して、ネットワーク１２００に対して経路探索、接
続および切断を行うのに使用される。この実施例に対し
ては、交換段４ないし１２のノードは第５図のノードの
ような全容量交換ノードである。ファンアウト段１．２
．３のノードおよびファンイン段１３．１４．１５のノ
ードおよびファンイン段１３．１４．１５のノードは、
それぞれ、単純ファンアウト要素および単純ファンイン
要素である。

プログラム内蔵制御下で操作される単一プロセッサとし
て、またはハードウェア論理回路装置として具体化が可
能なりロスオーバネットワーク制御器１３００は、たと
えば第３９図、第４０図に示す制御処理を実行して、そ
れぞれ接続および切断をおこなわせる。

接続処理（第３９図）は、与えられた接続要求に対する
ネットワーク１２００の入口／出口対がブロック１４０
２内の待ち行列に記憶されたときに開始する。記憶され
た入口／出口対が処理されるべきとき、ブロック１４０
４において、入口および出口の番号が、ネットワーク１
２００にトポロジー的に等価のシャツフルネットワーク
の対応する入口および出口番号へ変換される。次にブロ
ック１４６０において本文で後に説明する処理を用いて
分離経路チエツクが行われ、これにより、この接続要求
に対して可能なある経路が、同時処理されている他の接
続要求に対して可能なある経路とインターセクトするか
を判定する。進行中の他の接続要求と衝突がなければ、
実行はブロック１４０８に移り、ここで等価シャツフル
ネットワークの入口から出口までの全ての経路に付属す
るスイッチまたはリンクが決定される。ネットワーク１
２００においては、スイッチ（またはノード）は全容量
スイッチであるので、ネットワークを通過する与えられ
た経路のリンクを決定すれば十分である。もしネットワ
ークスイッチが一容量スイッチであるならば、ネットワ
ークを通過する与えられた経路の経路要素が一旦決定さ
れると、ブロック１４１２において経路メモリが更新さ
れ、これにより等価シャツフルネットワークに対する入
口番号、出口番号および経路番号を用いて空き経路を定
義する。ブロック１４１４において、ネットワーク段制
御器１２０１ないし１２０９に対し接続命令が送られる
。

さらに、識別された経路に対しては、その経路要素（ス
イッチまたはリンク）は、全ての段に対しブロック１４
１６において話中とマークされる。

ブロック１４０６に戻って、もし与えられた接続要求が
、処理中の他の接続要求と衝突すると判定されたならば
、与えられた接続要求に関する情報が、ブロック１４２
０において待ち行列内に記憶される。ブロック１４１０
において、他の接続要求の１つに対して、空き行列が一
旦見出だされると、ブロック１４２０の待ち行列に対し
て、情報が提供される。次にブロック１４０６の非接続
経路チエツクが反復される。ブロック１４１０において
、接続要求に対し空き経路が見出されなかったならば、
ブロック１４２２、ブロック１４２４が実行される。ブ
ロック１４２２においては、接続処理が完了したとの報
告が、ブロック１４２０の待ち行列に対してなされる。

ブロック１４２４においては、不成功に終った接続要求
は後に再び処理可能であるというようなブロッキング障
害報告がブロック１４０２の待ち行列に対してなされる
。

切断処理（第４０図）は、与えられた切断要求に対する
ネットワーク１２００の入口がブロック１４４０内の待
ち行列内に記憶されたときに開始する。記憶された入口
が処理されるべきとき、ブロック１４４２において、入
口番号がネットワーク１２００にトポロジー的に等価の
シャツフルネットワークの対応する入口番号に変換され
る。ブロック１４４４において経路メモリを指示するの
にシャツフル入口番号が使用され、これにより接続用の
シャツフル出口番号および経路番号を決定する。ブロッ
ク１４４８において、ネットワーク段制御器１２０１な
いし１２０９に対し切断命令が送られる。さらに、識別
された経路に対しては、その経路要素（スイッチまたは
リンク）は全ての段に対し再び空きとマークされる。

ネットワーク制御器１３００のハードウェア実施態様を
第４２図−第４４図に示す。特定のネットワーク１２０
０人ロ／出ロ対を指定する接続要求は接続要求待ち行列
１３０２内に記憶される。

９ビツトの２進クロスオーバ入口番号および９ビツトの
２進クロスオーバ出口番号は、対応する９ビツトのシャ
ツフル入口番号および９ビツトのシャツフル出口番号へ
変換するために、クロスオーバからシャツフルへのマツ
プ化装置１３０４（ｍ５０図）に伝送される。シャツフ
ル入口および出口番号は、接続／切断要求待ち行列１３
０５内に記憶され、次に分離（非接続）経路チエツク装
置１３０６　（第４６図）に伝送される。装置１３０６
は、現在の入口／出口番号対が、他の入口／出口番号対
に関連する経路とは分離したリンクであるネットワーク
１２００内の経路を形成するかどうかを判定する。２以
上の接続要求がネットワーク１２００内に分離経路を形
成するとき、本明細書では操作のオーバーラツプモード
と称されるものの中で、多重の接続要求および経路探索
が同時に処理可能である。次に接続／切断要求待ち行列
１３０８内にシャツフル入口／出口番号が記憶される。

経路探索が実行されるべきとき、接続要求待ち行列１３
０８は、ネットワーク１２００のリンク段４ないし１１
に対応するリンクのためのリンクの話中／空きビットを
記憶する複数のメモリ１３１２に読取要求信号を伝送す
る。（リンク段ｉはノード段ｉとノード段ｉ＋１との間
のリンク段である。）９ビツトのシャツフル入口信号お
よび９ビツトのシャツフル出口信号も、また接続要求待
ち行列１３０８から並列に伝送され、メモリ１３１２の
位置をアドレスするのに、入口信号および出口信号の中
の所定のものが使用される。

ネットワーク１２００において、任意の指定された入口
／出口対に付属して８つの経路がある。

各メモリ１３１２は各々ビットからなる５１２の位置（
メモリー位置）を有する。与えられたメモリ１３１２の
５１２の位置の各々は、第３０図のように連鎖結合され
た入口番号、経路番号および出口番号によって形成され
る２進数から抽出された所定の９ビツトの異なる値に対
応する。しかし、任意の段に対する経路番号は抽出され
ない。この結果、メモリ１３１２の位置は、与えられた
入口／出口番号対に付属の８つの経路の各々に対するリ
ンク段の話中／空き状態を定義する。メモリ１３１２の
アドレスされた位置の全ての８ビツトは読取られ、同時
にたとえば多重入力ＯＲゲートとして態様化された複数
の経路話中／空きチエツク装置１３１４によって結合さ
れる。経路チエツク装置１３１４の１つは、その入力信
号がリンクの空き状態を指示したときに空き信号を伝送
する。

空き経路選択装置１３６１　（第５１図）は、装置１３
１４の各々から話中／空き信号を受取り、定義された空
き経路の１つを所定の方法で選択する。

次に、空き経路選択装置１３１６は、８つの経路の中の
選択された１つに対応する２進数を伝送する。装置１３
１６はまた、実際に経路が見出されなかったならば、経
路ブロック指示信号を伝送する。経路ブロック指示信号
は、接続要求待ち行列１３０２に送り戻されて、接続要
求が後に反復可能となるようにする。経路ブロック指示
信号の反転は、話中ビットをメモリ１３１２の各々内に
書き込むための書込要求信号として使用される。空き経
路番号は、メモリ１３１２に伝送されてさらに特定経路
と、従って、入口および出口番号によってアドレスされ
た位置の特定ビットとを識別する。さらに、書出要求に
応答して、経路メモリ１３１８が更新され、経路メモリ
１３１８は、シャツフル入口によって定義されたアドレ
スにおいて、シャツフル出口番号と選択された空き経路
番号とを記憶する。

切断要求待ち行列１３２０は、切断されるべきクロスオ
ーバ入口を、対応するシャツフル入口に変換するための
クロスオーバからシャツフルへのマツプ化装置１３０４
に伝送することによって、切断をおこなう。次にシャツ
フル入口は、経路メモリ１３１８をアドレスするのに使
用される。切断要求待ち行列１３２０は、経路メモリ１
３１８に読取要求信号を伝送して、シャツフル入口アド
レスによって定義された経路メモリ１３１８の位置に記
憶されているシャツフル８口は、次に、シャツフル入口
とともに、待ち行列１３０５と、分離（非接続）経路チ
エツク装置１３０６と待ち行列１３０８とを経由して、
アドレスメモリ１３１２に伝送される。アドレスされた
経路メモリー３１８の位置はまた、切断されるべき経路
の経路番号も含む。読取られた経路番号はミ並列にメモ
リ１３１２の各々に伝送され、空き状態に戻されるべき
特定ビットをさらに指定する。その後、切断要求待ち行
列１３２０は、メモリ１３１２内で空き状態への変更を
おこなわせる書込要求を伝送し、かつまた、その接続に
関する情報を経路メモリー３１８から削除する。ノード
段制御器１２０１．１２０９の各々はトランスレータを
含み、トランスレータは、シャツフル入口、出口および
経路信号の所定の結合を形成して、新たな経路の部分と
して可能化されるかまたは切断のために不能化されるべ
きノードとノード入力からノード出力への接続を決定す
る。これらのトランスレータの設計は次の論理を基礎と
している。ｘＭ　　＋Ｐ＊Ｍ＋ま た推理に従って、１１　　（ｘ、Ｐ本、Ｙ）（Ｓｉ（ｘ
、Ｐ＊、ｙ）上に使用される入力）とを決定可能である
。

（ｘ、　Ｐ　　、　ｙ）はｘＭ　　＋Ｐ＊Ｍ＋ｙの２進
表＊ 示の右からｎ十に一１＋Ｓ−ｉビットだけ移動した１ビ
ツトの窓によって与えられる。

次にＯ（ｘ、Ｐ’、ｙ）はｘＭ　　＋Ｐ＊Ｍ＋ｙ＋　　
　　　　　　　　　　　　　　　　　　１の２進表示の
右から５−ｉ−１ビツトだけ移動した１ビツトの窓によ
って与えられる。

Ｑ　　（ｘ、Ｐ’、ｙ）をシャツフル領域からクロスオ
ーバ領域へマツプ化するためには、第１表における表現
（３）、（４）と、第３表における表現（１２ａ）のそ
れぞれを利用する。必要な排他的ＯＲ機能はハードウェ
ア内に容易に態様化され、またこれらの機能への入力は
ｘＭ　　＋Ｉ”Ｍ＋ｙの２進表示から直接得られる。ク
ロスオーバからシャツフルへのマツプ化装置１３０４　
（第５０図）は、適切な入口および出口信号を結合する
１セツトの排他的ＯＲゲートを含む。ネットワークは、
８個のファンアウトおよびファンインを有するので、全
体ネットワークは、１ないし８のファンアウトのための
３つの段と、スイッチイングのための９つの段と１ない
し８のファンインのための３つの段とからなる合計１５
の段で構成されるものと解釈可能である。ファンアウト
／ファンインは、各々８個の入口／出口のうちの１つ（
４（１１のスイッチのうちの１つの入口／出口）を選択
的に装備することによって達成される。次に選択された
５１２個入口および出口スイッチは、第１表の表現（１
）を用いてシャツフル領域にマツプ化される。

結果として得られた論理を第５０図に示す。

メモリ１３１２は、各々リンク話中／空きビットを記憶
する５１２Ｘ８のランダムアクセスメモリである。経路
話中／空きチエツク装置１３１４はＯＲゲートとして態
様化される。選択装置１３１６（第５１図）はＡＮＤ、
ＮＡＮＤ、０ＲＳＮＯＲゲートを配置して態様化され、
これにより３つの経路信号を用いて選択空き経路を定義
し、経路ブロック指示信号と書き込み要求信号との両方
の目的に使用される単一信号を発生する。

分離経路チエツク装置１３０６は、第４６図に示す論理
配置を基礎としている。チエツクされる２つの入力／出
力対は、（Ｘ９．Ｘ８、Ｘｌ、Ｘ６、Ｘ５、Ｘ４、Ｘ３
、Ｘ２、Ｘｌ）−（Ｙ９゜Ｙ８．Ｙ７．Ｙ６．Ｙ５．Ｙ
４．Ｙ３．Ｙ２．Ｙｌ）および（ｘ９．　　ｘ８．　ｘ
７．　　ｘ６．　　ｘ５．　　ｘ４、ｘ３．ｘ２．ｘｉ
）−（ｙ９．ｙ８．ｙ７゜ｙ６．ｙ５．ｙ４．ｙ３．ｙ
２．ｙｌ）として表されている。装置１３０６の論理配
置は、第４９図に示すネットワーク１３３０内で１×２
ｎである第１段の要素によって示されるようなファンア
ウトから独立であり、２ｎ×１要素である最終段要素に
よって示されるようなファンインから独立である分離経
路をチエツクするために適用可能である。装置１３０６
の論理配置は、入口／出口対に対してｘＭ　　＋Ｐ’Ｍ
＋ｙの２進表示を考えてみる。

Ｌ　　（ｘ、Ｐ＊、ｙ）は、４≦ｉ≦１１に対するこれ
らの２進値の右から＋ｏｇ２Ｍｌ＋１−１２−ｔビット
だけ移動したｌｏｇ　２　　（ｒ　ｔ　ｍｔ　）　−ｎ
　＋　ｋ−９＋３−１２ビツトの窓によって与えられる
。

段１．２．３のずれの段のリンクも、ただ１つの入口に
よってアクセス可能であり（ファンアウトの３つの段）
および段１２．１３．１４のいずれの段のリンクもただ
１つの出口によって、アクセス可能である（ファンイン
の３つの段）ので、Ｌｌは、４≦ｉ≦１１に対してのみ
考えれば良い。

次に、 Ｌ　　（ｘ、Ｐ’、り、Ｌ　　（ｘ”、Ｐ’、ｙ”）を
考えてみる。

Ｒ４（ｘ、Ｐ傘、ｙ）＝Ｘ８Ｘ７Ｘ６Ｘ５ｘ４Ｘ３Ｘ２
Ｘ１ｐｐｐＹ９Ｌ４（”ＩＰ傘、ｙ’）＝ｘｇｘｔｘ６
ｘ５ｘ４ｘ３ｘ２ｘｔｐｐｐｙ９ｐｐｐの領域は、可能
な８つの値の全てをとることが可能なので、これらの２
セツトのリンクは、残りのビットの少なくとも１つの位
置において異なるならば、そのときのみ分離している。

従って、これら２つのリンクセットは、もしＲ４：　（
ＸｓΦＸｓ）　＋　（Ｘ７Φｘ７）　＋　−＋　（ＸＩ
ｆＢ　Ｘｌ）＋　ＣＹｑΦｙ９）ｍｔならば、分離して
いる。

Ｒ５：　（Ｘ７Φに、）＋　・＋　（ＸｌΦＸＩ）＋（
Ｙ９Φｙｇ）＋（ＹｓΦｙｇ）＝１Ｐ’、ｙ−）から分
離している。このように逐次進んで最後には ＤｌＢ　＝（ｘＩｅｘｌ）＋（ＹｇΦ）’９）　＋　−
＋　（Ｙ２　ｅ　Ｙ２）　＝　１゜に到達するであろう
。リンクの全セットは、各々ＤＩ−１であるか、または
Ｒ７＝　Ｒ４ｘＤ５　ｘ−ｘＤｌｌ　Ｗ　１である場合
のみ分離している。第４６図に示す論理はＤＴのプール
代数の実行である。

２つの入口／出口対がリンク分離していると判定された
ときは、接続を形成するための経路探索機能は、第４７
図のタイミング図表に示すようにオーバーラツプ作業モ
ード内で実行可能である。

図示のように、メモリ１３１２の読取りを行うのに必要
な時間と、ＯＲゲート１３１４とおよび空き経路選択装
置１３１６とからなる論理回路要素のそれに続いて行わ
れる演算と；および経路メモリ１３１８の書き込みとな
らびに話中ビットのメモリ１３１２への書き込みとのた
めのそれに続く時間と；が第４７図ではＲ１、Ｌｌ、Ｗ
ｌで示されている。第２の接続要求のための対応する時
間はＲ２、Ｒ２、Ｗ２で示されている。図示のように、
第２の読取りは、第１の読取り結果が論理ゲートの幾つ
かのレベルを通過して伝搬中である。

第４８図に示すように、ネットワーク制御器メモリの多
重コピー等が使用れるときは、第４５図に示すように、
対応する４つの書き込みが行われる前に、４つの読み込
みを行うことが可能である。

代替態様として、第１の入口と第１の出口との間の経路
、および第２の入口と第２の出口との間の経路、で衝突
があるかどうかをチエツクする代わりに、選択された経
路があたかも衝突することがないかのごとく単に処理し
、もし衝突が起きた場合は、第２の入口と第２の出口と
の間で代替経路を選択することが可能である。衝突の存
在は、第２の選択経路に対する話中空き指示信号のいず
れかが話中とマークされているかどうかで検出される；
話中とマークされている場合は、すでに話中として検出
したものを除き、その第２の経路に対する話中−空き指
示信号は、空きとして保留されなければならず、第２の
入口および出口の間の代替経路の探索が行われる。

多くのＥＧＳネットワークにおいては、２つの接続要求
が分離している確率は高い。Ｎ個の入口およびＭ個の出
口と、８個の段と、および段１１；おける各スイッチ上
に０１個の入口および段ｉにおける各スイッチ上にｍｔ
個の出口、ここでｎｎｊ≦Ｎ　　に対して ＮＩＩＩＯｒｎｏｄＩ！１．、ｌ　　　およびと１ もしｔ≧Ｕのみならば、 Ｓ（ｘ、ｙ）（Ｉ　Ｓ（ｘ’、ｙ’戸φとを有する。Ｅ
ＧＳネットワークを考えてみよう。

Ｌ　（ａ、ｂ）を入口ａと出口すとの間の全ての経路内
の全てのリンクのセット、ｓ　＜ａ、ｂ）を入口ａと出
口すとの間の全ての経路の全てのスイッチのセット、お
よびΦを空すなわちゼロセットと定義する。これらの定
義を用いて次の定理を説明する。

リンク分離経路の定理： もしｔ≧Ｕのみならば、 ＬｗＪ　　はＷ以下の範囲の最大整数、および Ｍ　はＷ以上の範囲の最小整数である。

Ｌ（ｘ、ｙ）　ｒ）Ｌ（ｘ’、ｙつ＝φスイッチ分離経
路の定理： 任意に選択されたｘ、ｙおよびＸ′、ｙ−に対しては、
２つのケースを考える。； ケースＯ； ＸおよびＸ゛はＮ個の入口のセットから交替に選ばれ、
すなわちＸおよびＸ′は同じ入り口であってもよい。同
様に、ｙおよびｙ′はＭ個の出口のセットから交替に選
ばれる。このケースに対しては変数β−０とセットする
。

によってえられる。

スイッチ分離経路の確率： Ｓ（ｘ、い、−、Ｓ（ｘ’、ｙ’）　＝φ　である確率
は、ケースｌ； ＸおよびＸ″もｙおよびｙ′もいずれもＮ個の入口およ
びＭ個の出口のそれぞれのセットから交替では選ばれ無
い。従って、　　Ｓ７　及びＳ８　である。このケース
にたいしてはβ−１とセットする。

リンク分離経路の確率： Ｌ（ｘ、ｙ）（ｓ、　ｕｘ’、ｙ’）＝φ　”？’アル
ｉ１４；Ｌ、によって与えられる。

ｌｏｇ２　Ｎ≦Ｓ≦２　ｌｏｇ２　Ｎ：に対して：Ｐ（
分離）　−Ｐ　（与えられた入口／出口対の間の全ての
経路は他の入口／出口対空スイッチおよびリンクが分離
している）− いくつかの経路に対して、共通のスイッチを有する２つ
の入口／出口対を選択するには、通りの方法がある。

２つの入口／出口対を選択するには、 −５１２、Ｓ−９に対しては、インターセクト経由を有
する２つの入口／出口対を選択するにはまた２つの入口
／出口対を選択するには従って、 さらに、Ｐ −，９９９ ら分離）− が分離）− （３対のうち少なくとも２対が分離） ９９６１３、Ｐ（各４対が他の３対か ９０９４、Ｐ（５対のうちある４対 ９９６　である。

【図面の簡単な説明】

第１図は、第３８図の５１２Ｘ５１２多段クロスオーバ
ネットワークを制御する例示的ネットワーク制御器の線
図； 第２図は、拡張セクション、完全シャツフル等価ネット
ワーク及び集束セクションからなるシステムに対する実
例的ネットワークトポロジーの線図； 第３図、第４図及び第５図は、異なる拡張及び集束態様
を有する第２図のネットワークトポロジーの線図； 第６図、第７図及び第８図は、第２図のシステムにおい
て使用される全容量ノード、選択可能−容量モード及び
選択不能−容量ノードのそれぞれの線図； 第９図は、集束セクションのない第２図のネットワーク
トポロジーに類似のネットワークトポロジーの線図； 第１０図は、拡張セクションのない第２図のネットワー
クトポロジーに類似のネットワークトポロジーの線図； 第１１図は、単一段の厳密非ブロツキングネットワーク
の線図； 第１２図は、厳密非ブロツキング３段クロス（ｅｌｏｓ
）ネットワークの線図； 第１３図は、−膜化厳密非ブロッキング３段クロス（ｃ
ｌｏｓ）ネットワークの線図；第１４図は、厳密非ブロ
ツキング５段クロス（ｃｌｏｓ）ネットワークの線図； 第１５図は、多段相互接続ネットワーク（ＭＩＮ）の線
図； 第１６図は、拡張−膜化シャッフル（Ｅ　Ｇ　Ｓ）ネッ
トワークとここでは呼ばれるＭＩＮの特殊タイプの線図
； 第１７図及び１８図は、例示的ＥＧＳネットワークの線
図； 第１９図は、第１７図及び第１８図のネットワークの入
口Ｘから出口ｙまでのチャネルグラフＬ（ｘＳｙ）を示
す線図； 第２０図は、第１９図のチャネルグラフＬ　（ｘ。 ｙ）の他に単一のインターセクト呼を示す線図。 第２１図及び第２３図は、ネットワークにχ・１する非
ブロッキングタライテリヤ（基弗）を求めるのに使用さ
れる第１６図のネットワークの線図；第２２図は、前方
同一後方向不変特性（ＦＢＩＰ）とここでは呼ばれるネ
ットワーク特性を説明するのに使用される第１８図の線
図； 第２４図は、例示的非ブロッキングＥＧＳネットワーク
の線図； ｔｊｚ　２５図は、特定の完全シャツフル等価ネットワ
ークロスオーバ（または半クロスオーバ）ネットワーク
の線図； 第２６図は、完全シャツフル等価ネットワークの重要な
特殊ケースを表わすＥＧＳネットワークの線図； 第２７図は、全容量ノードを有する第１６図のＥＧＳネ
ットワークにおける経路探索機能を実行するのに使用さ
れる経路探索処理の流れ図；第２８図は、−容量ノード
を有する第１６図のＥＧＳネットワークにおける経路探
索機能を実行するのに使用される経路探索処理の流れ図
；第２９図は、シャツフルネットワークのスイッチ及び
リンクの入口、経路及び出口番号に対する関係を説明す
るのに使用される例示的シャツフルネットワークの線図
； 第３０図は、単一２進数を形成するための第２９図のネ
ットワークに対する入口、経路及び出口番号の連鎖２進
数表示を示す線図： 第３１図は、単一２進数から第２９図のネットワークに
対するスイッチ、リンク、入力及び出力を決定すること
を示す線図； 第３２図は、２つの異種同形のタイプのネットワーク即
ちクロスオーバネットワークとシャツフルネットワーク
との間の変換であってここでは第１表−第３表に記載さ
れているところの変換の略示図； 第３４図、第３５図、第３６図は、第３３図に従って配
置されたとき、１次元配列のノードを用いた１６Ｘ１６
の２次元クロスオーバネットワークが形成される線図； 第３７図は、第３４−第３６図の１６Ｘ１６クロスオー
バネツトワークと、１２８Ｘ１２ｇクロスオーバネット
ワークと及び第３８図の５１２×５１２クロスオーバネ
ツトワークとの相対的大きさを示す線図； 第３８図は、５１２Ｘ５１２クロスオーバネツトワーク
及び対応のクロスオーバネットワーク制御器の線図； 第３９図は、第３８図のクロスオーバネットワーク制御
器に対する接続要求処理の流れ図；第４０図は、第３８
図のクロスオーバネットワーク制御器に対する切断要求
処理の流れ図；第４２図、第４３図、第４４図は、第４
１図に従って配置されたとき、第３８図のクロスオーバ
ネットワークのハードウェア論理回路態様が形成される
ところの線図： 第４５図は、ネットワーク制御器メモリの複製コピーを
有する代替ネットワーク制御器態様の線図： 第４６図は、第４２図−第４４図の制御器の切り離し経
路チエツク装置の線図； 第４７図は、第４２図−第４４図の制御器によるオーバ
ーラツプ経路探索処理を示すタイミング線図； 第４８図は、第４５図の代替制御器によるオーバーラツ
プ経路探索処理を示すタイミング線図；第４９図は、１
×２　要素の第１段と２　　ＸＩ要素の最終段とを有す
るネットワークでありかつそれに対して第４６図の切り
離し経路チエツク装置が適用可能であるネットワークの
線図；第５０図は、第４２図−第４４図の制御器の、ク
ロスオーバからシャツフルへのマツプ化装置の線図； 第５１図は、第４２図−第４４図の制御器の空き経路選
択装置の線図； 出　願　人：アメリカン　テレフォン　アンド完全、＋
　？＋７７　ｒ１等等価−・リークＦＩＧ。 ＦＩＧ。 完全シテフフ！、膚９イｄ５字７に一りノードを貴 ノート′を貫 ノード段 ！−ド１２ ＦＩＧ。 完全ツヤ）・フ・；等価−ノトフーク ？−段 ノーを段 ノード段 ｌ−ド段 ＦＩＧ。 ）ＩＩＩ出力 ＦＩＧ、　　１１ ＦＩＧ。 ＦＩＧ。 Ｎ。 二田 鴨口 一ベ ＦＩＧ。 ＦＩＧ。 ＦＩＧ。 ＦＩＧ。 ＦＩＧ。 ＦＩＧ。 ７４ツチｘ　Ｘ　ｘ　Ｘ　１１　Ｘ　Ｘ　Ｘ　Ｘ　Ｐ　
Ｐ　Ｐ　Ｐ　Ｐ　Ｐ２二［７７Ｅ］ｙ段２のリンク　　
　　　　　　　　　段１６のリンクＸ段２の人力　　　
　　　　　　　１段１６の人力人力口ｘｘｘｘｘｘｘｘ
ｐｐｐｐｐ［］ｐｐｐｙｙｙｙｙｙｙｙｙＦＩＧ。 ノーパＬマ ！°ンクＬ１ 一−Ｌ゛段′Ｓツクを貧 ノード段 ！、′／りＬ艷 ％ト’段）グ１２ ノート１３計 ＦＩＧ。 ノーｔ′段 ５７段 ノート段すンクＬジ ノ→゛ｔマ ＦＩ（３゜ Ｇ ネットワークの相対的大きさ ＦＩＧ。 ＦＩＧ。 ＦＩＧ。 ノーｉ’？、６１１１１□−ノー）”ａｖｔ＋５ｌｌ−
’＜ＦＩＧ− ＦＩＧ。 ＦＩＧ− ＦＩＧ。 ＦＩＧ。 手 続 補 正 書（自発） 平成２年６月

Claims (1)

1. 【特許請求の範囲】 （１）複数の入口と複数の出口とを有するネットワーク
   と複数のステージ（段）と、前記ステージの中の関連す
   るステージに対するステージの話中／空き情報を記憶す
   る複数の手段とを有する多段ネットワーク制御方法にお
   いて、 前記入口の中の特定の入口から前記ネットワークを介し
   て前記出口の中の特定の出口へ通じる空き経路を捜し出
   すために、少なくとも三個の記憶手段から同時にステー
   ジの話中／空き情報を組み合わせるステップを有するこ
   とを特徴とする多段ネットワーク制御方法。（２）前記
   ネットワークは、前記特定の入口から前記特定の出口へ
   の間に複数の経路を有し、前記複数の記憶手段のそれぞ
   れは、前記複数の経路中の関連する経路の話中／空き情
   報を保持する複数の保持手段を有し、 前記組み合わせステップは、前記三個の記憶手段の全て
   の保持手段から同時にステージの話中／空き情報を読み
   出すステップを有する ことを特徴とする請求項１記載の方法。 （３）前記ネットワークが、前記特定の入口から前記特
   定の出口への間に複数の経路を有し、前記複数の記憶手
   段のそれぞれが、前記複数の経路の中の関連する経路用
   のステージの話中／空き情報を保持する複数の保持手段
   を有し、 前記組合せステップは、前記複数の記憶手段の全てがそ
   れらの全ての保持手段から同時にステージの話中／空き
   情報を読み出すステップを有することを特徴とする請求
   項１記載の方法。 （４）前記組合せステップは、 前記複数の経路の中でステージの話中／空き情報の前記
   読み出しにより空き状態として示されている一つの経路
   を決定するステップ、 話中状態を表示するために前記決定された経路と関連す
   る保持手段のそれぞれにおいてステージの話中／空き情
   報を同時に更新するステップ、を有することを特徴とす
   る請求項３記載の方法。 （５）前記組合せステップは、回線切り離し要求に応じ
   て、空き状態を表示するために前記決定された経路と関
   連する保持手段のそれぞれにおいてステージの話中／空
   き情報を同時に更新するステップを有する ことを特徴とする請求項４記載の方法。 （６）前記ネットワークを通じる各話中経路を示す情報
   を記憶する経路メモリー手段を有し、前記複数の経路の
   中で読み出された前記ステージの話中／空き情報により
   空き状態として示されている一つの経路を決定するステ
   ップ、 前記決定された経路を示す情報を前記経路メモリー手段
   に書き込むステップ、 を有することを特徴とする請求項３記載の方法。 （７）回線切り離し要求に応じて、前記決定された経路
   を示す前記情報を前記経路メモリー手段から消去するス
   テップ、 を有することを特徴とする請求項６記載の方法。 （８）前記複数の経路の中で読み出された前記ステージ
   の話中／空き情報により空き状態として示されている一
   つの経路を決定するステップ、前記決定された経路が前
   記特定の入口から前記特定の出口への通信を可能とする
   ように前記ネットワークを制御するステップ、 を有することを特徴とする請求項３記載の方法。 （９）回線切り離し要求に応じて、前記決定された経路
   が前記特定の入口から前記特定の出口への通信を不能と
   するように前記ネットワークを制御するステップ、 を有することを特徴とする請求項８記載の方法。 （１０）前記複数の出口のそれぞれが出口番号で表され
   、前記複数の経路のそれぞれが経路番号で表され、前記
   装置が、更に前記ネットワークを通る各話中経路を示す
   情報を記憶するための経路メモリー手段を有し、この経
   路メモリー手段はそれぞれが前記複数の入口の中の一つ
   の入口に対応する複数の記憶場所を有し、 前記複数の経路の中でステージの話中／空き情報の前記
   読み出しにより空き状態として示されている一つの経路
   を決定するステップ、 前記特定の出口を表わす出口番号と前記決定された経路
   を表わす経路番号とを、前記特定の入口に対応する前記
   経路メモリー手段の前記記憶場所に書き込むステップ、 を有することを特徴とする請求項３記載の方法。 （１１）前記複数の入口のそれぞれが入口番号で表され
   、前記複数の経路のそれぞれが経路番号で表され、前記
   装置が、更に前記ネットワークを通じる各話中経路を示
   す情報を記憶するための経路メモリー手段を有し、この
   経路メモリー手段はそれぞれが前記複数の出口の中の一
   つの出口に対応する複数の記憶場所を有し、 前記複数の経路の中で読み出された前記ステージの話中
   ／空き情報により空き状態として示されている一つの経
   路を決定するステップ、 前記特定の入口を表わす入口番号と前記決定された経路
   を表わす経路番号とを、前記特定の出口に対応する前記
   経路メモリー手段の前記記憶場所に書き込むステップ、 を有することを特徴とする請求項３記載の方法。 （１２）前記複数の記憶手段のそれぞれが、それぞれ前
   記ステージの中の関連するステージに同一のステージの
   話中／空き情報を記憶する第一及び第二の複製手段を有
   し、 前記組合せステップは更に、 前記入口の中の特定された第一の入口から前記ネットワ
   ークを介して前記出口の中の特定された第一の出口に通
   じる第一の空き経路を捜し出し、前記入口の中の特定さ
   れた第二の入口から前記ネットワークを介して前記出口
   の中の特定された第二の出口に通じる第二の空き経路を
   捜し出すために、前記三個の記憶手段の前記第一及び第
   二の複製手段から同時にステージの話中／空き情報を読
   み出すステップ、 を有することを特徴とする請求項１記載の方法。 （１３）前記情報の読み出し後に、現在のステージの話
   中／空き状態を表示するために、前記三個の記憶手段の
   前記第一及び第二の複製手段から再び前記ステージの話
   中／空き情報を読み出す前に、前記三個の記憶手段の前
   記第一及び第二の複製手段の両方において前記ステージ
   の話中／空き情報を同時に更新するステップ、 を有することを特徴とする請求項１２記載の方法。 （１４）前記ステージのそれぞれが、複数のリンクを有
   し、前記複数の記憶手段のそれぞれが、前記関連するス
   テージのリンクの中の一つのリンクに前記ステージの話
   中／空き情報を記憶する複数のビット記憶場所から成る
   複数のアドレス可能な記憶場所を有し、前記装置は更に
   前記複数の入口の中のいずれか一つの入口を表わすよう
   に符号化された複数の入口信号と前記複数の出口の中の
   いずれか一つの出口を表わすように符号化された複数の
   出口信号とを発生する手段を有し、 前記組合せステップは更に、 前記記憶手段のそれぞれに対して、前記記憶手段の記憶
   場所をアドレスするために、前記特定の入口及び前記特
   定の出口を表わす所定の入口信号及び出口信号からアド
   レスを発生するステップ、前記特定の入口から前記全て
   の複数のステージの空き状態リンクを介して、前記特定
   の出口へ通じる経路を捜し出すために全てのアドレスさ
   れている前記記憶手段の記憶場所の中のビット記憶場所
   の全部から同時にステージの話中／空き情報を読み出す
   ステップ、 を有することを特徴とする請求項１記載の方法。 （１５）前記ネットワークは、それぞれ前記入口の中の
   一つの入口と前記出口の中の一つの出口とからなる入口
   ・出口の対に対して同数の前記ネットワークを通る経路
   を有し、アドレス可能な記憶手段の記憶場所の各ビット
   記憶場所が、前記同数の経路に対応し、 前記特定の入口と前記特定の出口から成る入口・出口の
   対に対して同数の経路の中の一つの経路を、読み出され
   た前記ステージの話中／空き情報により空き状態として
   示されている経路として決定するステップ、 空き状態を表示するために、アドレスされた前記記憶手
   段の全記憶場所の前記決定された経路と対応するビット
   記憶場所において前記ステージの話中／空き情報を同時
   に更新するステップ、を有することを特徴とする請求項
   １４記載の方法。 （１６）前記ネットワークは、それぞれが前記入口の中
   の一つの入口と前記出口の中の一つの出口とからなる入
   口・出口の対に対して同数の前記ネットワークを通る経
   路を有し、前記装置は更に前記同数の経路の中のいずれ
   か一つの経路を表わすように符号化された複数の経路番
   号を発生する手段を有し、 前記特定の入口と前記特定の出口から成る入口・出口の
   対に対して同数の経路の中の一つの経路を、読み出され
   た前記ステージの話中／空き情報により空き状態として
   示されている経路として決定するステップ、 前記記憶手段のそれぞれに対して、その記憶手段に関連
   するステージの前記リンクの中の一つのリンクを介して
   通信を可能にするために、前記特定の入口と前記特定の
   出口と前記所定の経路とを表わす前記各入口信号と前記
   各出口信号と前記各経路信号の中のそれぞれ所定の信号
   を使用するステップ、 を有することを特徴とする請求項１４記載の方法。 （１７）前記ステージのそれぞれは、複数のノードを有
   し、前記記憶手段のそれぞれはそれぞれ前記関連するス
   テージのリンクの中の一つに前記ステージの話中／空き
   情報を記憶する複数のビット記憶場所からなる複数のア
   ドレス可能な記憶場所を有し、前記装置は、更に前記複
   数の入口の中のいずれか一つの入口を表わすように符号
   化された複数の入口信号と前記複数の出口の中のいずれ
   か一つの出口を表わすように符号化された複数の出口信
   号とを発生する手段を有し、 前記組合せステップは更に、 前記記憶手段のそれぞれに対して、前記記憶手段の記憶
   場所をアドレスするために前記特定の入口及び前記特定
   の出口を表わす所定の入口信号及び出口信号からアドレ
   スを発生するステップ、前記特定の入口から前記全ての
   複数のステージの空きノードを介して、前記特定の出口
   へ通じる経路を捜し出すために全てのアドレスされてい
   る前記記憶手段の記憶場所の全ビット記憶場所から同時
   にステージの話中／空き情報を読み出すステップ、 を有することを特徴とする請求項１記載の方法。 （１８）前記ネットワークは、それぞれが前記入口の中
   の一つの入口と前記出口の中の一つの出口とからなる入
   口・出口の対に対して同数の前記ネットワークを通る経
   路を有し、アドレス可能な記憶手段の記憶場所の各ビッ
   ト記憶場所が、前記同数の経路に対応し、 前記特定の入口と前記特定の出口から成る入口・出口の
   対に対して同数の経路の中の一つの経路を、読み出され
   た前記ステージの話中／空き情報により空き状態として
   示されている経路として決定するステップ、 空き状態を表示するために、アドレスされた前記記憶手
   段の全記憶場所の前記決定された経路と対応するビット
   記憶場所において、前記ステージの話中／空き情報を同
   時に更新するステップ、を有することを特徴とする請求
   項１７記載の方法。 （１９）前記ネットワークはそれぞれが前記入口の中の
   一つの入口と前記出口の中の一つの出口とから成る入口
   ・出口の対に対して同数の前記ネットワークを通る経路
   を有し、前記装置は更に前記同数の経路の中のいずれか
   一つの経路を表わすように符号化された複数の経路番号
   を発生する手段を有し、 前記特定の入口と前記特定の出口から成る入口・出口の
   対に対して同数の経路の中の一つの経路を、読み出され
   た前記ステージの話中／空き情報により空き状態として
   示されている経路として決定するステップ、 前記記憶手段のそれぞれに対して、その記憶手段に関連
   するステージの前記リンクの中の一つのリンクを介して
   通信を可能にするために前記特定の入口と前記特定の出
   口と前記所定の経路とを表わす前記各入口信号と前記各
   出口信号と前記各経路信号の中のそれぞれ所定の信号を
   使用するステップ、 を有することを特徴とする請求項１７記載の方法。 （２０）複数の入口と複数の出口とを有し複数のステー
   ジを含むネットワークと、 前記ステージの中の関連するステージ用のステージの話
   中／空き情報を記憶する複数の手段と、前記入口の中の
   特定の一つの入口から前記ネットワークを介して前記出
   口の中の特定の一つの出口に回線を接続する要求に応答
   して、その接続のための空き経路を捜し出すために前記
   記憶手段のうちの少なくとも三個から同時にステージの
   話中／空き情報を組み合わせる手段と を有することを特徴とする多段ネットワーク制御装置。 （２１）前記ネットワークは、前記特定の入口から前記
   特定の出口への間に複数の経路を有し、前記複数の記憶
   手段のそれぞれは、前記複数の経路の中の関連する経路
   用にステージの話中／空き情報を保持させる複数の保持
   手段を有し、前記情報組み合わせ手段は、前記接続要求
   に応答して、前記三個の記憶手段の全ての保持手段から
   同時にステージの話中／空き情報の読み出しを生じさせ
   る手段 を有することを特徴とする請求項２０記載の装置。 （２２）前記ネットワークは、前記特定の入口から前記
   特定の出口への間に複数の経路を有し、前記複数の記憶
   手段のそれぞれは、前記複数の経路の中の関連する経路
   用のステージの話中／空き情報をに保持させる複数の手
   段を有し、 前記情報組み合わせ手段は、前記回線接続要求に応答し
   て、前記全ての複数の記憶手段の全ての保持手段から同
   時にステージの話中／空き情報の読み出すを生じさせる
   手段 を有することを特徴とする請求項２０記載の装置。 （２３）前記ステージの話中／空き情報に応答して前記
   複数の経路の中で空き状態として示されている経路を決
   定する手段、 この決定手段に応答して話中状態を表示するために、前
   記決定された経路と関連する保持手段のそれぞれにおい
   てステージの話中／空き情報を同時に更新する手段、 を有することを特徴とする請求項２２記載の装置。 （２４）回線切り離し要求に応答して、空き状態を表示
   するために、前記決定された経路と関連する保持手段の
   それぞれにおいて、ステージの話中／空き情報を同時に
   更新する手段 を有することを特徴とする請求項２３記載の装置。 （２５）前記ネットワーク中の各話中経路を示す情報を
   記憶する経路メモリー手段、 読み出された前記ステージの話中／空き情報に応答して
   、複数の経路の中で前記空き状態として示されている一
   つの経路を決定する手段、この決定手段に応答して、前
   記決定された経路を示す情報の前記経路メモリー手段内
   への書き込みを生じさせる手段、 を有することを特徴とする請求項２２記載の装置。 （２６）回線切り離し要求に応答して、前記決定された
   経路を示す前記情報を前記経路メモリー手段から消去す
   る手段 を有することを特徴とする請求項２５記載の装置。 （２７）読み出された前記ステージの話中／空き情報に
   応答して、前記複数の経路の中で空き状態として示され
   ている一つの経路を決定する手段と、この決定手段に応
   答して、前記決定された経路が前記特定の入口から前記
   特定の出口への通信を可能とするように前記ネットワー
   クを制御する手段と、を有することを特徴とする請求項
   ２２記載の装置。 （２８）回線を切断する要求に応答して、前記決定され
   た経路が前記特定の入口から前記特定の出口への通信を
   不能とするように前記ネットワークを制御する手段、 を有することを特徴とする請求項２７記載の装置。 （２９）前記複数の記憶手段は、それぞれが前記ステー
   ジの中の関連するステージに同一のステージの話中／空
   き情報を記憶する第一及び第二の複製手段を有し、 前記組み合わせ手段は、前記入口のうちの特定された第
   一の入口から前記ネットワークを介して前記出口のうち
   の特定された第一の出口へ接続する第一の要求と、前記
   入口のうちの特定された第二の入口から前記ネットワー
   クを介して前記出口のうちの特定された第二の出口へ接
   続する第二の要求とに応答して、前記第一接続のための
   第一空き経路及び前記第二接続のための第二空き経路を
   捜し出すために前記三個の記憶手段の第一及び第二の複
   製手段から同時にステージの話中／空き情報の読み出し
   を生じさせる手段 を有することを特徴とする請求項２７記載の装置。