JPH0418518B2 - - Google Patents

Description

【発明の詳細な説明】 以上の順序で本発明を説明する。

Ａ 産業上の利用分野 Ｂ 従来技術 Ｃ 発明が解決しようとする問題点 Ｄ 問題点を解決するための手段 Ｅ 実施例 Ｆ 発明の効果 Ａ 産業上の利用分野 この発明は、多段相互接続ネツトワーク
（MIN）上で音声とデータを交換する
（switching）ための方法に関するものである。よ
り詳しくは、この発明は、複数のビツトが、
MINの交換要素の各記憶位置に格納されている
ような方法である。各交換要素中の各記憶位置
は、フレームの特定のタイムスロツトをあらわ
し、各位置に格納されているビツトは入力または
出力の状態と、個々の時間スロツトの間の交換要
素の構成をあらわす。

Ｂ 従来技術 単一のスイツチ上でデータ及び音声サービスを
総合することの利点は、スイツチ設計の視野を拡
げたことにある。伝統的には、パケツト交換がデ
ータ通信のための理想的な機構であると考えられ
ている。これは、データ・トラフイツクが典型的
には統計的マルチプレクシングとパケツト交換に
なじみやすいからである。音声の場合、時間とシ
ーケンスの点で連続性が要求される。それゆえ、
音声にはわずかな保証された交換遅延が必要であ
り、それは通常交換機構によつて与えられる。パ
ケツト交換の結果としての可変的な遅延は、音声
トラフイツクのための一定でわずかな遅延条件を
達成するためには問題である。

この遅延の問題を解決するために、音声及びデ
ータ交換の両方を支援するべく多段交換ネツトワ
ークが開発された。音声とデータ交換の統合は、
本来的な自己巡回技術により、交換ネツトワーク
がネツトワークを介する接続経路を迅速かつ同時
的に変化させることができるようになつたので可
能となつた。

今までに開発された顕著な２つの多段交換ネツ
トワークとして、AT＆Ｔ Bell Laboratories
の高速パケツト交換と、General Telephone
and Electronics（GTE）のバースト交換がある。
高速パケツト交換は、多段交換ネツトワーク中の
中間段においてカツト・スルー（cut−through）
技術とバツフア・パケツトとを使用する。カツ
ト・スルー技術は、T.KermaniとL.Kleinrock著
の“Uirtural Cut−Through：Ａ New
computer Communication Switching
Technique”と題する論文に記述されている。こ
の論文は、Computer Networks、Vol.3，
pp.267−287，1979年９月に掲載されている。カ
ツト・スルー技術及びパケツトの緩衝技法によ
り、音声とデータをネツトワークを介して迅速に
伝達することが可能ならしめられる。しかし、競
合により、交換の処理能力が、ポート帯域利用量
の約40％で飽和してしまう。さらに、パケツトの
遅延と微分遅延を音声交換の許容範囲にとどめる
ために、より狭い帯域の利用が必要である。一
方、バースト交換は、利用可能なリンクに対する
過剰コミツトメントを特徴とする回路交換に基づ
くシステムである。この交換システムは、パケツ
トまたは音声バーストをもつチヤネルがこれらの
リンクを求めて競合することを可能とするよう
に、沈黙検出技術を使用する。しかし、音声バー
ストの数が増加するにつれて、バーストが失われ
る確率が高まる。このように、バースト交換の場
合、リンク競合によりパケツトが失われるという
ことに関心が注がれる。

多段相互接続ネツトワーク上で音声とデータを
交換する方法は、1986年４月28日に出願された米
国特許出願第856321号にも記述されている。この
方法によれば、各パケツトが、そのパケツトにネ
ツトワークを巡回させるための複数のアドレス・
ビツトを含む。各パケツトはまた優先順位パケツ
トを含み、最高の優先レベルをもつ各パケツト
は、ネツトワークを通過するときにブロツクされ
ないことを保証される。しかし、この方法に関与
する問題は、数ミル秒の遅延を生じることであ
る。この遅延により、トークン・リング・ローカ
ル・エリア・ネツトワークなどの短い遅延を要す
る適用技術にこの使用することができなくなつて
いる。

高速パケツト交換は米国特許第4491945号に記
述されている。GTEのバースト交換は、S.R.
Amstutz、“Burst Switching−Ａ Method for
Distributed and Integrated Voice and Data
Switching、”IEEE Communication Magazine、
pp.36〜42，1983年11月に記述されている。

米国特許第4539676号及び米国特許第4413337号
は、ともに、統合音声／データ交換システムを記
述する。しかし、このどちらの特許も音声とデー
タを分離する。すなわち、この両特許において
は、音声トラフイツクが、データ・トラフイツク
とは異なる交換機構を介して交換される。

ワシントン、シアトルで1980年６月に開催され
た1980International Conference of
Communicationsで提出された“An
Architecture for Integratwd Voice／Data
Switch”と題するRossらによる論文は、入来ト
ラフイツクを回路及びパケツト・トラフイツクに
分離する方法を記述する。これによれば、回路ト
ラフイツクは次にパケツト・トラフイツクとは分
離して記憶される。回路トラフイツクは次に回路
トラフイツク専用のバスを介して送られ、その
間、データは、データ・トラフイツク専用のバス
を介して送られる。この双対的なバス転送は本質
的に、システムの帯域を、データ及び回路バスの
帯域に限定してしまう。

Ｃ 発明が解決しようとする問題点 本発明の目的は、分散制御を有し、きわめて重
要なことは遅延が非常に小さい、高帯域統合音
声／データ交換技術を提供することにある。

本発明の別の目的は、統合音声／データPBX
（第５世代）における第２レベル・スイツチとし
て、且つ統合首都圏エリア・ネツトワークにおけ
るスイツチとして、ローカル・エリア・ネツトワ
ークに接続して使用することのできる統合音声／
データ交換システムを提供することにある。

Ｄ 問題点を解決するための手段 本発明は、同期的及び非同期データの交換のた
めの多段相互接続ネツトワークを制御する方法を
与える。このネツトワークは、複数の導通性リン
クを相互接続するために使用される複数の交換要
素をもつ。これらの導通性リンクは、交換要素の
選択された入力から、フレームのシーケンス中の
各シーケンスの間に交換要素の選択された出力へ
同期及び非同期データを送るために使用される。
本発明の方法の第１のステツプは、複数のビツト
をネツトワークの複数の交換要素の記憶位置に格
納するステツプを有する。第２のステツプは、
各々の個別の交換要素中に格納された対応するビ
ツトのセツトによつてあらわされた構成に対応す
るように、各タイムスロツトの間に各交換要素の
構成をセツトすることである。各交換要素が呈す
る構成は次に、その交換要素の入力における選択
されたリンクを、その交換要素の出力における選
択されたリンクに相互接続をするために使用され
る。各リンクは、１つの交換要素からの別の交換
要素にデータを送るために使用される。

本発明は、フレームのシーケンスにおける各フ
レームの各タイムスロツトの間に交換要素の構成
をセツトするために必要な情報を各交換要素に格
納することによつて遅延を小さくするものであ
る。こうして、遅延が小さいことにより、本発明
は、遅延が小さいことを要求する適用技術に使用
することのできる交換方法を提供する。そのよう
な適用技術の１つに、大きいリングを構成するた
めに複数のトークン・リング・ローカル・エリ
ア・ネツトワークを接続することがある。別の適
用技術としては、複数のスイツチをカスケードす
ることによつて構成される大規模音声／データ・
ネツトワークがある。

Ｅ 実施例 第１図は、本発明を具体化する多段相互接続交
換ネツトワーク１０のブロツク図である。この交
換ネツトワークは、クリア・チヤネル回路交換と
パケツト・データ交換からなる遠隔通信ネツトワ
ークの構成に使用するように意図されている。通
信装置は、統計的時分割多重化フオーマツトでパ
ケツト・ストリームを発生するインターフエー
ス・モジユール（Ｉ／Ｆモジユール）12を介して
交換ネツトワークとインターフエースする。Ｉ／
Ｆモジユールは、異なるユーザー・インターフエ
ースを使用する回路駆動機構１３とパケツト駆動
装置１４をサポートする。回路駆動インターフエ
ースの例はD4フオーマツトをもつ包括的T1／
DS1であり、パケツト駆動インターフエースの例
は、X.25プロトコルをサポートするX.21または
RS232C物理リンクである。ISDNインターフエ
ースは必ずしも実施されないけれども、Ｉ／Ｆモ
ジユールは、ISDN付属装置のユーザーにサービ
スするように拡張すべく、開放式であり得る。

多段相互接続ネツトワークは複数の交換要素５
を有し、それらは、ネツトワークのリンク６を相
互接続するために使用される。第１図の最左端に
あつて入力アダプタ２のすぐ右に接続されている
リンクはネツトワークの入力と呼ばれ、第１図の
最右端にあつて出力アダプタ４の左に接続されて
いるリンクはネツトワークの出力と呼ばれる。図
示されているネツトワークは、各段（ステージ）
に交換要素のための列をもつ３段ネツトワークで
ある。任意の１つの入力から、ネツトワークの各
段における交換要素を介し、それらの交換要素に
よつて相互接続されるリンクを介して任意の１つ
の出力に至る接続がパスと呼ばれる。こうして、
例えば、第１図左上の入力アダプタと第１図右上
の出力アダプタの間にセツト・アツプされ得る電
気的接続がパスである。このパスは、第１図上部
の４つのリンクと、第１図上部の３つの交換要素
によつてセツト・アツプされる。

第２図には、第１図に示されている交換要素５
のより詳細な構成を示す図が示されている。この
交換要素は、ネツトワークの一対のリンクに接続
された２個の入力６１と、ネツトワークの別の一
対のリンクに接続された２個の出力６２とを有し
ている。この適用技術においては、“入力”とい
う用語は、“入力ポート”という用語と同義語に
使用するものとする。交換要素はまた、状態メモ
リまたはシフトレジスタ２５を有する。この状態
メモリまたはシフトレジスタは、この例では512
個の記憶位置２−１〜２−512をもつ。

各記憶位置はその中に少くとも５ビツトを記憶
する容量をもつ。各記憶位置の左側の第１及び第
２のビツトが“交換保留状態ビツト”と呼ばれる
（第２図中の参照番号２６で示される箇所を参
照）。これら第１及び第２のビツトはそれぞれ、
上方及び下方の入力が交換保留状態にあるかどう
かを示すために使用される。それのビツト“１”
は、対応する入力が“交換保留状態”にあること
をあらわす。尚、この“状態”という用語につい
ては後述する。例えば参照番号２７で示されてい
る各記憶位置の右の３ビツトは、その記憶位置に
対応するタイムスロツトの間に交換要素がとるべ
き構成をあらわすために使用される構成ビツトで
ある。シフトレジスタ２５のメモリは、この例で
は、フレームの512個のタイムスロツトに対応す
る512個の記憶位置を有している。こうして、例
えば、記憶位置２−２に記憶されている５ビツト
が、フレームのタイムスロツト２の間に、対応す
る交換要素入力が交換保留状態になく（最初の２
ビツトが00）、構成が010であらわされることを示
すために使用される。第２図の破線２１ａ，２１
ｃ及び２１ｄは、その交換要素の入力から出力へ
の４つの可能な電気的接続をあらわす。

第３図は、交換要素がとり得るさまざまな構成
を例示するために使用される。第３図の左側は２
×２交換要素がとり得る８個の可能な構成をあら
わす。それに対応する右側の３ビツト・コード
（構成ビツト）は、その左側の交換要素の対応す
る構成をあらわすために使用される。こうして、
例えば、010が、その左側の構成30−４に対応す
る。この実施例では、フレームの任意のタイムス
ロツトにおいて、交換要素が、第３図に示す８個
の構成30−１〜30−８のうちの任意の構成をとり
得る。例えば、30−４で示されビツト010により
あらわされる構成により、61−１に接続されたリ
ンクが出力62−１に電気的に接続され、一方61−
２における入力のリンクはどの出力にも接続され
ない。

このネツトワークは、フレーム毎に一定の数の
ビツトからなるフレーム中で動作する。例えば、
ここではフレーム毎に512ビツトが考慮されてい
る。フレーム中の各ビツトは、接続をセツト・ア
ツプすることを企て、または確立された接続のた
めにデータを移送するために使用されることにな
る。チヤネルは先ず、スロツトと呼ばれるフレー
ム中の特定のビツトのために、ネツトワークを通
じるパスを請求することによつて接続をセツト・
アツプする。チヤネルは次にそのパスとスロツト
とを、接続を破棄するまでの後の各フレーム中で
使用する。上述の例では、チヤネルは64Kbpsで
伝送し、１つのスロツトを使用し、フレーム毎に
512のスロツトが存在する。それゆえ、このネツ
トワークは32Mbpsでデータを伝送しなくてはな
らない。

そこで次に、ネツトワーク内の（２×２）交換
要素でどのようにして接続が確立されるかについ
て説明する。これと同一のプロトコルは、ネツト
ワークの任意のステージにおけるすべての交換要
素で採用される。あるスロツトにおける交換要素
入力に接続が存在しない場合、そのスロツトにお
ける交換要素入力ポートにはビツト０が受取られ
る。交換要素入力に対する接続要求は、非接続状
態になくてはならない交換要素入力において、あ
るスロツトの間に入来ビツト１によつて報知され
る。この１ビツトは、スタート・ビツトと呼ばれ
る。交換要素入力は、交換要素のその入力が交換
要素のどの出力にも接続されていないとき非接続
状態にある。スタート・ビツトが受信された後
は、次のフレームの同一のスロツトにおいて、交
換要素要求セツト・ビツト（すなわち、この交換
要素の上方または下方の出力に対する接続の要
求）が受信される。交換要素が、この交換要求セ
ツト・ビツトが受信されるべきことを知るために
は、その入力のための別の状態が必要である。そ
こでこの状態を、対応する交換保留状態ビツトの
ビツト“１”によつてあらわされる、交換要素入
力ポートにおける“交換セツテイング保留”状態
と呼ぼう。交換要素セツテイング要求ビツトが受
信されたとき、交換要素は、要求された出力が使
用中であるかどうかを判断し、入力のACK／
NAK線に肯定または否定の承認を即時に送り返
す。このとき、“０”がNAK、“１”がACKをあ
らわす。もしゲート遅延により、ACK／NAKが
その同一のスロツトにおける入力に送り返される
のを阻止されるなら、ACK／NAKは、衝突を検
出する際の余分なフレーム遅延を除いてはプロト
コルを変更することなく次のフレームの同一のス
ロツトにおいて送り返すことができる。もし要求
された出力が空いているなら、接続が確立され、
入力の状態が“接続確立”状態にセツトされる。

それと同時に、ビツト１がその出力に配置さ
れ、後のステージに対する接続要求を表示する。
そのスイツチのある入力に接続が確立されている
交換要素出力において受信されるACK／NAK
は、次のフレーム中のそのスロツトにおけるその
入力でACK／NAK線上に送り返される。入力が
非接続状態である場合、ACK／NAK線は常にゼ
ロであり、これは否定承認を表示する。“交換セ
ツテイング保留”状態においては、入力における
ACK／NAK線が１にセツトされる。尚、交換要
素の入力がとり得る３つの状態をエンコードする
ためには、入力毎に余分なビツトが必要であるこ
とに注意されたい。前述の３ビツト・エンコーデ
イング・リストにこれを追加すると、スロツト毎
に５ビツト・エンコーデイングとなる（第２図参
照）。

次に、ネツトワーク全体に亘つてどのようにし
てパスが確立されるかを説明する。そこで、アダ
プタがある特定の出力ポートに対するあるチヤネ
ルのパスを確立する必要があると仮定する。アダ
プタは、フレーム中のどのスロツトが不使用であ
るかを知つている。アダプタは空きスロツトを選
択し、高論理レベル、すなわち接続要求を、それ
が接続される交換要素入力にセツトする。次のフ
レームの同一のスロツトにおいて、アダプタは構
成ビツトの第１のビツトを送り、それは、ネツト
ワークの第１のステージ中の要求された交換要素
セツテイングをあらわす。スロツトの終わりで、
アダプタは、ネツトワークのステージ１でパスが
確立されたかどうかを示すACKまたはNAKを入
手する。もしNAKが受信されたなら、アダプタ
はフレーム中で別の空きスロツトを捜し、上述の
パス・セツト・アツプ手続を反復する。もし接続
が、ACKによつて表示されて、ネツトワークの
ステージ１で確立されるなら、アダプタは次のフ
レームの同一のスロツトで行先アドレスの次のビ
ツトを送る。交換要素のための接続セツト・アツ
プにおいて前述したように、要求された接続をそ
の出力に成功裡にセツト・アツプしたステージ１
中の交換要素は、ステージ２の交換セツテイング
要求を中断することになる。ステージ２は、要求
されたステージ２の接続が成功裡にセツト・アツ
プされたか否かに応じて、ステージ１の交換要素
にACKまたはNAKを送り返す。一方、ステージ
１は、後のフレームの同一のスロツトで、この
ACKまたはNAKをアダプタに中継する。アダプ
タは、各ステージ毎に１ビツト、且つフレーム毎
に１ビツト、構成ビツトの順次的なビツトを送出
する。こうして、最悪の場合、アダプタがセツ
ト・アツプを要求するのとNAKの間の時間は2n
であり、ここでｎはステージの数である。この最
悪の場合は、ネツトワークの最後のステージに競
合が存在するときに発生する。

上述のように一たんパスが確立されると、アダ
プタは、その接続を使用するチヤネルからデー
タ・ビツトを送るために後のフレーム中の同一の
スロツトを使用することになる。各交換要素は、
確立された回路のためにパスを留保するので、確
立されたパスは決してブロツクされることがな
く、データ・ビツトは失われない。さらに、各ビ
ツトのための交換セツテイングがセツト・アツプ
されているので、ネツトワークの各ステージにお
ける１ビツトの移送遅延が実現される。パスに
は、フレーム中で任意のビツトを割当てることが
できるので、チヤネルは、１フレームの最大交換
遅延プラス各ステージ毎の１フレーム・ビツトを
感知し得る。また、ステージの数は、典型的には
フレーム中のビツトの数に較べると小さいので
（フレーム毎の512ビツトを、ステージの10という
最大段数と比較されたい）、チヤネルによつて感
知される最大遅延はフレーム長に近く、その平均
はフレーム長の約半分である。フレーム長は、
（フレーム毎に１チヤネル・ビツトが伝送される
がゆえに）高々１チヤネル・ビツト時間でなくて
はならないので、チヤネルは、約１チヤネル・ビ
ツト時間という最大遅延と、1/2チヤネル・ビツ
ト時間という平均遅延を感知する。

確立されたパスは次のようにして破棄される。
すなわち、入力アダプタが出力アダプタにある特
定のビツト・パターンを送る。出力アダプタは次
に、接続されている交換要素の出力ポードでの対
応するスロツトにおいてNAKをセツトする。こ
のNAKは、フレーム毎に１ステージずつ後方に
横断して、接続全体が破棄されるまで、一度に１
ステージずつパスまたは接続を破棄してゆく。
尚、このことは交換要素で特殊な処理を要さない
ことに注意されたい。そのことは、ネツトワーク
中の後のステージが要求されたパスをセツト・ア
ツプできないときに接続またはパスのセツト・ア
ツプの間に行なわれる動作と同一である。そのパ
スに沿う各交換要素は、出力でNAKを受け取る
ときに、入力を非接続状態にセツトする。

次に、第１図の多断相互接続ネツトワークの動
作について説明する。これらのネツトワークは、
ネツトワークを通つて接続を巡らせるために、ネ
ツトワークの各ステージにおいて所望の出力アド
レスの１ビツトを使用することができるという点
で自己巡回的である。MINの各入力及び出力ポ
ートにはアダプタが接続されている。基本的なス
キームにおいては、ネツトワークを通つて交換さ
れるべき複数の固定速度チヤネルが各アダプタに
接続される。尚、別の適用技術のための別のスキ
ームも後述する。この基本的なスキームは、ブロ
ツキングが問題でないような比較的低いトラフイ
ツク状況で望ましい。説明の便宜上、（端数を丸
めて）64Kbpsチヤネルを使用し、ネツトワーク
が（２×２）交換要素から構成されるものと仮定
する。これらのチヤネルは、個別にアダプタに与
えられてもよく、あるいは上位チヤネルとして集
合させてもよい。上述の基本的なスキームは、ど
のようにしてネツトワークが操作され、交換要素
を通る接続が確立され、データが確立された接続
を通つて伝送されるのかということと、どによう
にして接続が破棄されるのかということをあらわ
す。尚、高トラフイツク状況におけるブロツキン
グを減少するためには、多少の修正と制約が基本
的スキームに加えられる。

基本的スキームは、フレームのスロツトに対応
するチヤネルのための接続をアダプタが確立する
様子を記述する。この接続またはパスの確立は、
すべてのパスに対して並列に実行され、MINの
自己巡回的性質を利用し、それゆえきわめて効率
的である。これにより、回路を、パケツトまたは
回路交換モードのどちらかで使用することが可能
となる。パケツト交換の場合、スロツトを留保す
る接続がセツト・アツプされ、単一パケツトの期
間に破棄される。回路交換の場合、回路の期間接
続が保持される。バースト交換（無音検出を伴う
音声など）の場合、各バースト毎に接続を破棄し
再確立することができる。尚、ネツトワーク中の
確率的な遅延によりリアルタイム・パケツトが失
われることがあるような高速パケツト交換とは逆
に、多段ビツト交換においては、一たん接続が確
率されると、スロツトは接続が破棄されるまで留
保され、ネツトワーク中の競合によりビツトが失
われてしまうことはない。このように、内部的に
は、回路は回路交換様式で動作されるが、接続の
並列セツト・アツプにより、チヤネルに対して
は、接続パケツト交換としてあらわれることが可
能となる。尚、ここでは固定サイズ・チヤネル
（この例ではチヤネル毎に64Kbps）が仮定されて
いるけれども、より大型のチヤネルを得るために
フレーム中の複数スロツトを要求することもでき
る。

上述のように、この基本的スキームは、ネツト
ワークを、単一ビツトが１スロツト中で送られ
る、ビツト交換であるとして記述した。これは明
らかに最小サイズのスロツトであるけれども、ス
ロツトは適用技術に応じて、バイド、ワードまた
はそれ以上に増加することができる。従つて、例
えば、もしスロツトが１バイト幅であるなら、交
換要素における多重化は一度に１バイトであり、
接続アドレス全体は単一スロツトで送ることがで
きる。この基本的スキームにおけるプロトコルに
対する修正は簡単である。また、交換要素のサイ
ズは（２×２）であると仮定されたが、望むなら
これも増加することができる。しかし、交換要素
のサイズに伴つて状態の数が増加するので、（２
×２）交換要素の簡便さが望ましいであろう。

基本的スキームの修正 上述の記載は基本的スキームに関するものであ
るが、より以上の処理能力が要求される場合、基
性的スキームの修正であるより複雑な方法が採用
されなくてはならない。上記基本的スキームに記
述されているように、チヤネルは、チヤネルが最
早不要となりパスが破棄されるまで、フレーム及
び後の各フレーム中の特定のスロツトに対してネ
ツトワークを通じるパスを請求することによりセ
ツト・アツプされる。しかし、修正されたスキー
ムの場合、チヤネルは、異なるタイムスロツトの
間に所与のパスの一部をセツトすることによつて
セツトアツプされる。こうして、ネツトワークの
第１のステージを通る所与のパスの一部がフレー
ムのシーケンス内の１つのスロツトの間に確立さ
れ、他方、第２のステージを通る所与のパスの別
の部分がフレームのシーケンス内の別のスロツト
の間に確立されることになる。

この修正されたスキームは、次の相違点を除く
と基本的スキームと同一である。すなわち、通信
リンクは、スロツト化されたフレーム様式で操作
されるので、各スロツトがリンク帯域の一部分を
あらわす。基本的スキームよりもブロツキングを
低減することによつてリンク帯域の利用効率を改
善するために、スロツトの割振りは、あるステー
ジでスロツトｉを使用するチヤネルが、次のステ
ージにおける空きスロツトを選択する自由をもつ
という意味で動的であり得る。

基本的スキームと同様に、スロツトにおいて、
交換要素入力に接続が存在しないとき、そのスロ
ツトのための交換要素入力ポートにおいてビツト
０が受信される。また、基本的スキームと同様
に、交換要素入力に対する接続要求は、非接続状
態になくてはならない交換要素入力におけるスロ
ツトの間の入来ビツト１によつて報知される。こ
のビツト１はスタート・ビツトと呼ばれる。ま
た、基本的スキームにおいては、次のフレームの
同一スロツトにおいて、ステージ・アドレスと呼
ばれる交換要素要求セツテイング・ビツト（これ
は、ネツトワーク中の交換要素のステージ位置と
同一の位置における行先アダプタ・アドレス内に
ある）が受信される。このビツトを使用して、交
換要素が、交換要素の上方または下方の出力ポー
トに対する接続を決定する。あるステージでスタ
ート・ビツトが受信されると、そのステージはパ
ス保留状態を入力し、次のフレームの同一のスロ
ツトで入来するステージ・アドレスを待つ。ステ
ージ・アドレスの最初のビツトが到着するとすぐ
に、交換要素は、自己のステージ・アドレスを除
去し、次の複数のフレーム内の同一の出力スロツ
トを使用して後のステージのためのスタート・ビ
ツト及びアドレス・ビツトを送るために、出力ポ
ート・フレームに空きスロツトを割当てる。しか
し、基本的スキームにおいては、交換要素が、要
求が到着した以前のフレームのスロツトに対応す
るスロツトの間に要求された出力が使用中かどう
かを判断する。修正されたスキームにおいては、
交換要素が、出力が使用中でないフレーム中の任
意のスロツトを検索する。こうして、修正された
スキームを用いると、あるフレームの異なるタイ
ムスロツトの間、及び後のフレームにおいて、同
期的または非同期的なデータが各フレームを通じ
て伝送されることになる。この同一のプロトコル
は、ネツトワークの任意のステージにおけるすべ
ての交換要素で使用される。最後に、スタート・
ビツトが出力アダプタに到着することになる。チ
ヤネルが複数のスロツトのパスを要求する通路
は、ｎ個のスタート・ビツトをｎ個の不使用のス
ロツトに送りその後各スロツトに同一のステー
ジ・アドレスを送ることによつて、入力アダプタ
から初期化される。

第４図は、この修正されたスキームのために使
用される交換要素のブロツク図である。本質的に
は、２個のフレーム・バツフア５１ａ及び５１ｂ
と、２個のタイムスロツト交換（TSI）接続テー
ブル５２ａ及び５２ｂと、２個の入力状況レジス
タ５３ａ及び５３ｂをもつ制御プロセツサ（CP）
５３が、基本的スキームで使用された交換要素に
追加される。

状態メモリ２５は同一のままであるが、交換要
素の出力の状況は、個別の記憶位置中の個別のビ
ツトにより決定される。他方、基本的なスキーム
は、それと同一の対応するビツトを、出力の状況
でなく入力の状況を識別するために使用する。こ
こでは状況という用語は、出力が空きかまたは使
用中であるかということを言う。このように、修
正されたスキームにおいては、交換要素の出力の
状況は既知であるが、この知識が直ちに交換要素
の入力の状況をもたらす訳ではない。それゆえ、
追加的な２個の入力状況レジスタ５３ａ及び５３
ｂがこの目的のため使用される。入力状況レジス
タを使用する代わりに、出力が空きか使用中かを
表示するために、状態メモリ中の各メモリ位置に
さらに２個のビツトを追加してもよい。

各入力線毎に１個設けられたフレーム・バツフ
アは、入力シーケンスに従つて順次格納される情
報ビツトの１つのフレームに対して保留（hold
up）する容量をもつ。また、やはり各入力線毎
に１つ設けられたTSI接続テーブルが、交換要素
によつて出力線に対して交換されるべきデータ・
ビツトのシーケンスを与える。

制御プロセツサ（CP）は、状態メモリ中のビ
ツトと、入力線から入来するビツトとデコードす
る。CPはまた、出力線に対する入力ビツトの交
換シーケンスを計画する。

接続要求が入力スロツトSi中のCP回路によつ
て検出されると、CPが入力状況レジスタ中にフ
ラグを立てて、タイムスロツトの間に交換要素入
力が要求保留状態にあるべきことを表示する。次
のフレームの同一のスロツトにおいて、入力リン
ク中のビツトが、接続を確立するための出力リン
ク・アドレスをもつ（上方に対しては０、下方に
対しては１）。基本的スキームにようにスロツト
Siの接続状況をチエツクする代わりに、CPは要
求された出力中で任意の空きチヤネルSoを選択
し、Soを要求のために割振る。CPは次に、新し
い要求と接続を反映するためにSoエントリにお
いて状態メモリを更新する。それと同時に、Siの
内容が、対応するTSI接続テーブル５２ａ中のSo
のエントリに格納される。

尚、テーブル・エントリを計画し更新するため
にCP中で相当な遅延Ｄが生じ得ることに注意さ
れたい。それゆえ、CP回路は、Ｄがフレーム・
サイズよりも小さくなるように十分高速でなくて
はならない。

接続手段の残りは、基本的スキームに類似して
いる。すなわち、ACK／NAKが次のフレームの
同一のスロツト（Si）に送り返される。Siから少
くとも１フレーム離れたスロツトSoにおいては、
次のステージでの接続要求が送られる。

一たんパスが確立されると、各段のアダプタと
交換要素が、接続セツト・アツプの間に決定され
るスロツトを使用することになる。それゆえ、ス
ロツト２で例えば、状態メモリの第２のエントリ
であるカウンタ５４が、第３図に示す７つの構成
のうちの１つとして交換要素の接続をはかるため
に使用される。第２のスロツトの入力ビツトを交
換のために利用するのではなく、出力のための
TSI接続テーブル５２ａ及び５２ｂ中の第２のエ
ントリの内容がフレーム・バツフア中のビツト位
置を規定する。これらの位置のビツトは次に、交
換要素の個別の出力に送られる。この場合、フレ
ーム・バツフア５２ａ中の10番目のビツトと、フ
レーム・バツフア５２ｂ中の26番目のビツトが、
それぞれ上方出力６２と下方出力６２へ送らが、
それぞれ上方出力６２と下方出力６２へ送られ
る。

パスを破棄するためのプロトコルは、基本的ス
キームの場合と同様である。異なるのは、スロツ
トＴでNAKが受取られたとき、交換要素が、状
態メモリのエントリＴを非接続状態にセツトする
のみならず、対応する入力線を識別するための状
態メモリの内容をデコードし、対応する入力スロ
ツトを識別するためにTSI接続テーブルの内容を
デコードすることである。交換要素は次に、識別
された入力状況レジスタの状態を遊休状態に更新
する。

基本的スキーム及び修正されたスキームのため
のアダプタ 第５図には、入力アダプタ（第１図参照番号
２）のブロツク図が示されている。入力アダプタ
は、フレーム・バツフア２１、走査ユニツト２
２、送信ユニツト２３、試行ユニツト２４及びス
ロツト交換テーブル２５というサブ・ユニツトを
有する。他方、出力ポート・アダプタは、ネツト
ワークの最後のステージから信号を受け取り、こ
れらを出力線に送る。

先ず、フレーム・バツフア２１について説明す
る。フレーム・バツフアはフレーム中のスロツト
と同じ数のビツトを含む。各スロツトにおいて、
フレーム・バツフアは入来ビツトを捕捉し、フレ
ーム・バツフアの対応するビツトにそれを格納す
る。このフレーム・バツフアは、１クロツク・サ
イクルにおける任意のビツト位置からの読取及び
任意のビツト位置への書込をサポートする。もし
読取と書込の位置が同一ならば、レジスタの古い
内容が読出されて、そこに書込まれる新しい内容
によつて置き換えられる。読み出すべき位置のア
ドレスは、走査ユニツト２２から得られる。フレ
ーム・バツフア２１から読出される内容は、送信
ユニツト２３に与えられる。

次に走査ユニツト２２について説明する。各ス
ロツトにおいて、入来ビツトは走査ユニツト２２
（及びフレーム・バツフア２１）によつて補捉さ
れる。走査ユニツトは、各スロツト毎に１ビツト
をもつスロツト使用レジスタを含む。初期的に
は、このレジスタは、どのスロツトも使用中でな
いことを表示するように、０にセツトされてい
る。走査ユニツトはまた、各スロツト毎に１ビツ
トをもつ呼出セツト・アツプ・レジスタを有し、
このレジスタのビツト１は、対応するスロツトの
ために呼出し要求が処理されつつあることを示
す。このスロツト使用レジスタの対応するビツト
の０によつて表示されてスロツトが使用されてお
らず、且つ呼出セツト・アツプ・レジスタの対応
するビツトが０であるなら、承認ビツト（後述）
及び、このスロツトを行先とするスロツト交換テ
ーブル中のレジスタがセツトされる。もし、スロ
ツト使用レジスタの対応するビツト中の０によつ
て表示される不使用のスロツトで入力アダプタに
よつてビツト１が受け取られるなら、このことは
呼出しセツト・アツプ要求を表示している。すな
わち、呼出しセツト・アツプ・レジスタの対応す
るビツトが１にセツトされ、このスロツトを行先
とする承認ビツトが１にセツトされる。走査ユニ
ツトは次に後のフレームの同一のスロツトで受取
られる次のｎビツト（ｎはネツトワークのステー
ジの数である）を集め、試行ユニツトに呼出し要
求パケツトを送る。呼出し要求パケツトは、呼出
し要求が受信されたスロツト番号と、後のフレー
ム上のスロツトで受信される次のｎビツトを含
む。走査ユニツトはまた、試行ユニツト２４か
ら、回路接続が、呼出しセツト・アツプ要求に応
答して確立されたかどうか、またはそのような回
路接続が確立し得ないことを示すメツセージをも
受け取る。確立された回路接続の場合、メツセー
ジは要求が到達したスロツト番号（入スロツト番
号）と、回路接続が確立されたスロツト番号（出
スロツト番号）とを含む。このメツセージを受け
取ると、走査ユニツト２２は、スロツト交換テー
ブル２５の入スロツト位置に出スロツト番号を入
力し、呼出し要求レジスタの対応するビツトを０
にリセツトし、スロツト使用レジスタの対応する
ビツトを１にセツトする。もし要求が満足されな
いなら、走査ユニツトが承認ビツト・テーブル中
の入スロツト番号に対応する承認ビツトをリセツ
トする。

次に承認ビツト２８について説明する。承認ビ
ツトは、ポート・アダプタによつて、呼出しセツ
ト・アツプ要求に応答して回路接続が確立された
ことを承認するために使用される。承認ビツト
は、走査ユニツト２２によつてセツトされる。呼
出しセツト・アツプ要求の場合、要求が受信され
たときに行先の承認ビツトが１にセツトされる。
そのビツトは、走査ユニツトが、試行ユニツトか
ら、要求が満足され得ないことを示すメツセージ
を受け取つたとき、または、第１ステージからの
承認線が、接続が既に終了したことを示す０を戻
すとき、０にリセツトされる。

次にスロツト交換テーブル２５について説明す
る。スロツト交換テーブルは、フレーム中のスロ
ツトの数と同数のレジスタを含むレジスタ・フア
イルである。このテーブル中のレジスタは、前述
のように、走査ユニツトによつてセツトまたはリ
セツトされる。同一のスロツト中であるレジスタ
がセツトされており別のレジスタがリセツトされ
ているということが可能である。各スロツト（例
えばスロツト５）において、そのスロツトに対応
するレジスタ（例えばスロツト交換テーブル中の
レジスタ５）の内容が、走査バス２６上でフレー
ム・バツフア２１に送られる。フレーム・バツフ
アはこのアドレスを、読出され送信ユニツト２３
に送られるべきエントリを選択するために使用す
る。

次に、送信ユニツト２３について説明する。送
信ユニツト２３は、フレーム・バツフアからと試
行ユニツトからの入力を多重化する。各スロツト
において、もしスロツト使用レジスタの対応する
ビツトが１なら、フレーム・バツフア入力が選択
され、一方このビツトが０なら、試行ユニツト入
力が選択される。送信ユニツトは、選択されたデ
ータ・ビツトを、この入力アダプタに接続され
た、ネツトワークの第１のステージ中の交換要素
に送る。送信ユニツトはまた、ネツトワークか
ら、パケツトがネツトワークを介して成功裡に送
信されたか否かを表示する承認をも受取る。
NAK線ビツトは、試行ユニツト２４と承認ビツ
ト２８に送られる。もしこの線上でビツト０
（NAK）が受信されるなら、入力アダプタの対
応する承認ビツトがリセツトされる（後述）。

次に、試行ユニツト２４について説明する。試
行ユニツト２４は走査ユニツト２２から呼出しセ
ツト・アツプ要求を受け取る。呼出し要求パケツ
トは、パケツトが入力線上で到達したスロツト
（入スロツト）と、接続が確立されるべき要求出
力線アドレスとを表示する。呼出し要求パケツト
は、保留要求待ち行列２７に格納される。試行ユ
ニツトは、接続のセツト・アツプを試みるべき空
き（すなわち、対応するスロツト使用レジスタ中
で０をもつ）スロツトを選択する。試行ユニツト
は次に、呼出し要求全体が送られてしまうか、ま
たはNAKがスロツト中の送信ユニツトから受信
されるまで後のフレームの選択されたスロツト中
の呼出し要求の１ビツトを選択する。送出された
呼出し要求はビツト１で始まり、その後一度に１
ビツトづつ、ネツトワークの各ステージのセツテ
イングが続く。もしNAKが呼出し要求の最後の
ビツトが送出された2nフレーム後（ｎはネツト
ワーク中のステージの数）受信されないなら、回
路はセツト・アツプされており、そうでないな
ら、試行ユニツトが次の空きスロツトを選択し、
所望の接続をセツト・アツプするために上述の手
続を引込める。もし接続が確立されているなら、
試行ユニツトが走行ユニツトに、要求が到達した
スロツト（入スロツト）と回路が確立されたスロ
ツトを表示するメツセージを送り、試行ユニツト
が保留待ち行列の先頭からパケツトを削除する。
もし試行ユニツトがフレーム中のどの空きスロツ
ト上でも接続をセツト・アツプできないなら、試
行ユニツトは、所望の回路が利用できないことを
示すメツセージを走査ユニツトに送り、保留待ち
行列から呼出し要求パケツトを削除する。

Ｆ 発明の効果 以上説明したように、本発明によれば、ネツト
ワークの交換要素の構成をセツトするために必要
な情報を各交換要素に格納することによつて、遅
延が十分小さくなるという効果が与えられる。

【図面の簡単な説明】

第１図は、本発明が適用される多段相互接続ネ
ツトワークのブロツク図、第２図は、交換要素の
ブロツク図、第３図は、交換要素の構成を示す
図、第４図は、修正されたスキームに係る交換要
素のブロツク図、第５図は、入力アダプタのブロ
ツク図である。 ２……入力アダプタ、４……出力アダプタ、５
……交換要素、６……リンク。

Claims (1)

1. 【特許請求の範囲】 １ 同期的及び非同期的データの交換のために、
   多段相互接続ネツトワークの制御方法であつて、
   該ネツトワークは、複数の交換要素をもち、該交
   換要素は、第１のフレームのシーケンスの間に、
   該交換要素の選択された入力から、該交換要素の
   選択された出力に、同期的及び非同期的データを
   転送するために使用されるものであり、該ネツト
   ワークは、多段相互接続ネツトワークの第１段の
   各々の交換要素の各々の入力毎に入力アダプタが
   存在するように、複数の入力アダプタをもつもの
   である、多段相互接続ネツトワークの制御方法に
   おいて、 (a) 上記データの伝送に使用されるのと同じ上記
   リンク上で構成ビツトを伝送することによつ
   て、上記交換要素中に、該構成ビツトを記憶す
   る段階であつて、該各々の構成ビツトは、中央
   制御装置を通じて渡すのではなく上記複数の入
   力アダプタのうちの１つの入力アダプタから伝
   送され、該各々の構成ビツトは、フレームのシ
   ーケンス中のあるフレームの空スロツトで伝送
   され、該各々の構成ビツトは、多段相互接続ネ
   ツトワークを通じて径路を確立する際に、関連
   する交換要素によつて使用されるべき出力を示
   すために使用され、１つの交換要素と１つの構
   成ビツトの間の関連は、フレームのシーケンス
   中のどのフレームに従い該構成ビツトが伝送さ
   れるかによつて識別されるようにする段階と、 (b) 上記各々の交換要素に記憶された構成ビツト
   の対応する組によつてあらわされる構成に対応
   するように、各々の特定のタイム・スロツトの
   間に、上記各々の交換要素の構成を設定する段
   階であつて、上記各々の交換要素の各々の構成
   は、各々個別の交換要素の出力における選択さ
   れたリンクに対して、各々個々の交換要素の入
   力における、上記ネツトワークのリンクのうち
   の選択されたリンクを相互接続するために使用
   され、該選択されたリンクの各々は、上記ネツ
   トワークの上記交換要素のうちの１つの交換要
   素から別の交換要素にデータを送るために使用
   されるものである段階を有する、 多段相互接続ネツトワークの制御方法。