JPH03154544A - 分散制御型クロスポイント交換機 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は電子交換機に関するもので、特に、コンピュー
ターネットワーク用の片側クロスポイント交換機に関す
る。

Ｂ、従来技術および課題 クロスポイント交換機は、電話産業およびコンピュータ
産業において、通信回線間のデータ交換に使用される。

クロスポイント交換機の一形態は、クリストス・ジロー
ジｔａ　（Ｃｈｒｌｓｔｏｓ　Ｃｅｏｒｇｌｏｕ）が米
国特許第４６３５２５０号で述べている片側クロスポイ
ント交換機である。

第１図は、従来の片側クロスポイント交換機の一例であ
る。１０１−１１８はデータ回線で、内部バス２０１−
２０８と交差しており、両者併せて交換マトリックスを
形成する。クロスポイント交換素子（クロスポイント）
は各交点に位置しており、第１図のマトリックスでは、
　１２８個のクロスポイント交換素子が存在する。また
各データ回線は、ポート・アダプタを介して、交換ポー
ト（ポート）に接続している。２本のデータ回線間（す
なわち２つのポート間）の接続は、適当な内部バスと各
データ回線との交点に位置するクロスポイント交換素子
を、ＯＮすることによって行われる。たとえば、データ
回線１０４と１１２間（すなわちデータ回線１０４と同
１０２とにつながる各ボート間）の接続は、交換素子１
０と１２をＯＮすることにより、バス２０８を用いて行
うことができる。同一　の接続を、他の内部バスを用い
て行うことも可能である。ただし、選択した内部バスが
、別のポート対間の接続に供用中でないことが条件とな
る。すべてのボート間で同時に対接続を行うには、バス
の本数がポートの総数の少なくとも半分あればよい。こ
のような交換システムは、あるボート間の対接続が別の
ボート間の対接続によってブロックされることがないと
ころから、ノンブロッキング交換機と呼ばれる。第１図
に示す交換機は、ポート１６個に対して内部バスが８本
あるため、ノンブロッキングである。

片側クロスポイント争マトリックスは、一般に１個以上
の交換チップによって構成される。システムのポート数
が少ない場合には、マトリックス全体を単一のチップに
受け持たせることができる。

ポート数が多い場合は、マトリックスを矩形のブロック
に区画し、個々のブロックを適当なサイズの交換チップ
によって受け持たせることになる。

各ブロックないし区画は、それぞれが小規模な片側クロ
スポイント交換機である。したがって、片側クロスポイ
ント交換機は、それ自身が小型の片側クロスポイント交
換機であるようなコンポーネントから成る、と見なすこ
とができる。これらコンポーネントは、一般には基盤目
状に配置される。

第１図を例にとって示せば、この交換マトリックスは４
個の交換チップから成り、各チップは８木の水平なデー
タ回線と、４本の垂直な内部バスを有している。

片側クロスポイント交換機の大きな特徴のひとつは、内
部バスが・・・他のボート間の対接続に供用中でない限
り・・・柔軟に対接続を行えることにある。

これによって、一部のバスに障害が発生しても、システ
ムは稼働を続けることが可能になる。バスが故障するご
とに同時に行い得る対接続数が減少し、システムの能力
も低下するが、故障したバスを供用から外しても、ポー
トはひとつとして使用不能になることはない。

第１図に示すように、クロスポイント交換機の交換ゲー
トは、制御バス１Ｂを介し、制御装置１４によって制御
される。制御装置１４は、ボート噌アダプタ・バス１−
８を通じてポート・アダプタからの接続／切断要求を受
け取り、マトリックスＬの適当なりロスポイントを活動
させたり体止させたりする。要求の願文が高くなると、
それを捌くには高速な制御装置が必要になる。これは、
交換機がマルチプロセッサ拳システムにおいてコンピュ
ータ同士を連結する場合にしばしば見られることで、個
々の接続の持続時間はきわめて短いものとなる。

片側クロスポイントのネットワークを制御するための制
御装置の一例が、クリストス・ジョークｅに授与された
米国特許第４６３００４５号である。この制御装置は、
パイプライン処理によって高速を達成している。ちなみ
にパイプライン処理とは、ある要求のある段階を、別の
要求の別の段階と同時に処理することである。

しかしながら、交換マトリックスにおけるボート数が増
大すると、単一の制御装置を用いた米国特許第４６３０
０４５号のやり方では限界がある。

たとえば複数の接続／切断要求が、同時ないしは短時間
に少数のボートに殺到した場合、長い待ち時間を過ごす
ものもでてくる。単一の制御装置では、パイプライン処
理を用いたとしても、エマシン・サイクルあたり高々ひ
とつの要求にしか対応できないからである。さらに、制
御装置に障害が発生した際には、制御装置自身が作業を
続けられず、システム全体が稼働不能になってしまう。

制御装置がシステム全体の障害を招きかねない要に位置
しているからである。バックアップ用の制御装置を設置
することで障害に対する抗姑性を持たせはできるものの
、それによって正常稼働時の性能を向上させることは期
待できない。

本発明はこれらふたつの問題点を、単一の制御装置に代
えて複数の制御装置に交換マ）　ＩＪフックス制御を分
散することにより、いささかなりとも克服しようとする
ものである。

両側クロスポイント交換機での分散制御は、アムダール
（Ａｍｄａｈり他に授与された米国特許第３２２６６８
８号に記載されている。ただし、両側クロスポイント命
ネットワークでは、あるボート対を接続する場合に単一
の交換経路しが存在せず、また全てのボート間で任意に
対接続を行うこともできない。前記特許においてアムダ
ールは、両側クロスポイント交換機を介して互いに接続
された一群の制御モジュールと一群の被制御モジュール
ををする、モジニーｌし化コンビューターンステムにつ
いて述べている。一群のセンス−ユニットがクロスポイ
ントを制御することによって、同一マシン争サイクル内
でひとつ以上の要求を処理できるようにしたものである
。しかしながら、各要求が前もって特定の制御装置に割
り振られているため、制ＯＩＩ装置に障害が発生すれば
、これらの要求も影響を受けることになる。さらに、こ
の手法は、片側クロスポイントｅネットワークには適用
できない。片側クロスポイント・ネットワークにおいて
は接続経路が膨大な数にのぼるとともに、任意のポート
間で対接続を行うことが可能だからである。

Ｃ１発明の概要および解決課題 本発明は、従来技術における上述の課題の解決を意図し
ており、単一の制御装置に替えて複数の制御装置に片側
クロスポイント交換マトリックスの制御を分散すること
により、 （ａ）大規模な片側クロスポイント交換機の速度を改善
し、 Ｃｂ）片側クロスポイント交換機によって設定／解除し
得る接続数をエマシン畳サイクルあたりひとつ以上に増
大させ、 （Ｃ）片側クロスポイント交換機の信頼性を島め、 （ｄ）片側クロスポイント交換機側の０′ｌｌ装置の機
能に冗長度をもたせる、 などの目的を達成しようとするものである。すなわち、
同一規格の制御装置を並列に稼働させ、各制御装置には
交換マトリックスの所定の範囲内における接続を受け持
たせるわけである。ボートからの接続／切断要求は、複
数の制御装置に分散して振り分けられる。その際、各要
求に各１台の制御装置が、漏れなく対応できるようにし
ておく。

制御装置に障害が発生した場合には、各要求が障害のな
い制御装置へと迂回するよう、分散方法を変更する。こ
れにより、少なくとも１台のｍｌｌ　ｆａｌｌ　装置が
完全に機能している限り、交換機は稼働を続けることが
可能になる。

上記の手法によれば、故障した制御装置に割り振られた
制御機能を、生きている制御装置に移管できるため、信
頼性が向上する。また、多数の要求に平行して対応でき
るため、性能も向上する。

制御装置の台数にこれといった決まりはなく、コスト、
性能、信頼性などなどの面から、最適な台数を選べばよ
いのである。

Ｄ、実施例 本発明の実施例の概略図を、第２図に示す。１６ポート
を宵する片側クロスポイント交換機が１６個の交換チッ
プによって構成されており、各チップは４行４列の基盤
目状に配置されている。

個々の交換チップは、４木の水平なデータ回線と４本の
垂直な内部バスから成る交換マ）　ＩＪフックス収容し
ている。各交換チップの内にくバスの本数は全て同じで
あっても、基盤目上の縦のチップ列ごとに別の本数であ
っても、どちらでもよい。その本数は、ポートからの要
求を制御装置間にどう分散するかとか、ブロッキングを
どの程度まで許すかなどの、設計上の絡みによって左右
される。

本数を決める際の基本的な考え方については、後はど述
べることにする。

システム内の垂直な内部バスの総本数は、各バス群ごと
の本数を合計したものとなる。第２図の例では、最初の
チップ列に４本、中央２つのチップ列に各３本、最後の
チップ列に２本で、計１２本の内部バスが存在すること
になる。これに対し、単一の制御装置に交換マトリック
スを受け持たせた場合、システムをノンブロッキングで
稼働するために必要な内部バスは（１６ボートに対して
）８本で済む。余分な４本は、制御の分散にともなうオ
ーバーヘッドを意味するものである。オーバーヘッドは
、制御装置を何台にするか、ボートからの要求を制御装
置間にどう分散するが、ブロッキングをどの程度まで許
すがなど、さまざまな要素によって左右される。オーバ
ーヘッドの詳細については、要求を制御装置間に分散す
る方法と関連して、後はど述べることにする。

第２図の実施例においては、各チップ列はそれぞれ１台
の制御装置によって制御される。したがって、制御装置
の総数は４台となり、チップ列の数に一致する。ただし
、各チップ列に制御装置を１台ずつ割り当てているのは
、便宜上の問題にすぎない。各制御装置に少なくとも１
本の内部バスがつながっている限り、制御装置の台数は
自由に設定することができる。一般には、制御装置の台
数、内部バスの本数およびその制御装置への割り当ては
、設計時点で意図したコスト、性能、信頼性に見合うよ
うに決められる。しかしながら、以下においては、制御
装置の台数はチップ列の数と等しいものとして説明を行
うことにする。

ポートΦアダプタ２０で発生した接続／切断要求は、ボ
ートｅバス１８を介して制御装置へと送られる。一般に
要求のデータ構造は、ポート対の入口側と出口側の各ボ
ート番号と、実行すべき動作から成る。実行すべき動作
とは、接続するのかまたは切断するのかの別である。各
制御装置はシステム支援プロセッサ２２によってプログ
ラムされ、接続／切断要求によって指定された入口／出
口の番号（ボート対）が然るべき組み合わせであった場
合、これに応じた接続／切断動作を行うようになる。ボ
ートから送り出された要求は、ポート−バス１８を介し
て全ての制御装置に到達する。しかし、これを認識でき
るのは、この要求が指定するポート対に関して接続／切
断を行うようにプログラムされた、特定の制御ＨＭだけ
である。各ポートのステータス、つまり各ボートが開放
状態か接続状態かの別は、ポート・ステータス表２４に
保存され、制御装置の閲覧に供される。

各制御装置は、ボート・ステータス番アクセス・バス２
６を介して、閲覧を行う。また、各制御装置ハ、システ
ム支援バス２８を介して、／ステム支援プロセッサ２２
に接続される。そして、システム支援プロセッサ２２は
、システムの初期設定を通じて、制御装置をプログラム
する役割を担う。

これにより、各制御装置は特定のポート対からの要求に
対して反応するようになるわけである。同プロセッサは
また、制御装置の障害を検出し、障害を起こしていない
制御装置をプログラムし直す役割をも担う。これにより
、故障した１□！制御装置の機能を、故障していないも
のに分散して振り替えるわけである。さらに、システム
支援プロセッサ２２に付設されたオペレータ・コンソー
ル３０によって、システム構成を設定し、システムの運
用を監視することができる。

第２図の制御装置の詳細を、第３図に示す。制御装置は
システム内の任意の２つのボートを接続することができ
るが、そのために使用する垂直な内部バスは、自らが制
御を担当するバスの内、いずれか１本に限られる。つま
り、制御装置は空いているバスを１本選んで、このバス
と目的のボートにつながる２本のデータ回線との交点に
位置する各クロスポイントをＯＮすることにより、両ボ
ートの間の接続を行うわけである。切断の場合は、ＯＦ
Ｆすることになる。ちなみに空いているバスとは、接続
を行おうとした時点で、他の接続のために供用されてい
ないバスを指す。クロスポイントの特定は、制御装置が
アドレス回線の行番号と列番号とを指定することによっ
て行う。行番号によってデータ回線を選び出し、列番号
によって内部バスを選び出すわけである。行番号と列番
号の組み合わせが決まればクロスポイントが決まり、制
御回線３２によって、このクロスポイントをＯＮしたり
ＯＦＦしたりできるようになる。なお、図において制御
回線は、１木の線で略記しである。

各制御装置は所定のボート対についてのみ、接続／切断
要求を認識できるようプログラムされる。

これを受け持つのは、ｆｌｉｌ制御装置内のボート番号
一覧表３４である。ボート番号一覧表はランダム・アク
セス拳メモリ（ＲＡＭ）でできており、ボート・バス１
８からの要求が指定する入口側と出口側の各ボートの番
号が、この表と照合される。たとえば、ボートの総数が
２５６ならば、各ボート番号は８ビツトで表わされ、ボ
ート番号−品表は、容ｆｆ１Ｅｔ５５３６ビツトのＲＡ
Ｍを使うことになる。

メモリｅサイズは；　　６５５３８ワードＸ１ビツトで
ある。また、第２図の例のようにボートの総数が１６な
らば、メモリ舎サイズは２５６ワードＸ１ビツトとなる
。制御装置が、あるボート対の入口側と出口側の各ボー
トの番号を認識できるようにプログラムされている場合
は、ボート番号一覧表のそのボート対に当たるビットに
′１°゛が立ち、そうでない場合はｌ　Ｏｌが立つ。ボ
ート番号一覧表３４の中身となるデータは、サービスを
バス２８を介して、システム支援プロセッサ２２から供
給される。システムの初期化を通じて、システム支援プ
ロセッサは、どの制御装置がどのボート対を受け持つか
を決定し、それにしたがってボート番号一覧表の中身を
供給するわけである。同様に、支援プロセッサがある制
御装置を故障と判断したならば、その制御装置のボート
番号一覧表を変更し、故障した制御装置に割り振られて
いたボート対を、生きている制御装置間に分散して振り
替える。

接続要求を処理するに当たって、まず処理制御装置は、
出口側のボートのステータスを確かめなければならない
。そのボートが他の接続によって、入口側にせよ出口側
にせよ、既に使用中かも知れないからである。ところで
、ボート・ステータス表２４は、各ボートのステータス
・・・空いているが、塞がっているか・・・を保存する
ものであった。ボート舎ステータス表はマルチφワード
ＲＡＭでできており、このＲＡＭの各番地は各ボートに
対応している。番地ごとに指定された記憶場所には、対
応するボートのステータスがそれぞれ記憶されているわ
けである。なお、ステータス情報としては、最低限、当
該ボートが空いているか塞がっているかを現わすための
１ビツトが必要である。

ボート−ステータス表２４は、全ての制御装置によって
共存されており、各制御装置は、ボート・ステータス・
アクセス・バス２６を介して同表を閲覧する。このバス
を通じてステータス表を収めたＲＡＭにアクセスできる
制御装置は、−時に１台に限られる。入口側ボートＡと
出口側ボートＢとの間で対接続を行おうとすれば、制御
装置はポート争ステータ゛ス表でＡおよびＢの各ステー
タスをチエツクしなければならない。両方とも空いてい
たならば、制御装置はボート・ステータス表上の両ポー
トのステータスを“接続中°′に更新する。なお、閲覧
と更新は、いつでも一体化した作業として行われる。あ
る制御装置が閲覧中のステータス表は、その更新が終わ
るまで、別の制御装置が閲覧することはできない。言い
替えれば、制御装置は閲覧／更新作業が完了するまで、
バス２６を占有していることになる。

ボートｅステータスΦアクセス令バス２６を：ｌｒ＋制
御装置が共有する方法は、いろいろある。単純なものと
しては時分割多重方式があるが、この方式では、各制御
装置は当該バスに対して順番にアクセスを行い、所定の
持ち時間ずつこれを占有する。

占有している間に閲覧／更新作業を完了しなければなら
ないため、持ち時間は複数のパス舎サイクルに亘ること
になる。別の方式としては、各制御装置が三々五々、必
要に応じてバスに要求を出し、バスが空いていたならば
アクセスを行うというやり方もある。複数の制御装置か
ら同時に要求が出された場合は、ラウントロピン（順繰
り総当たり方式）などの調整規則によって解決を図るわ
けである。

ポートΦアダプタで発生した接続要求は、以下のように
処理される。要求がボー）Ａで発生し、出口としてボー
トＢを指定しているものとする。

各制御装置は、バスを通じてこの要求を受け取り、Ａお
よびＢのポート番号の対をボート番号一覧表と照合する
。当該番号対のビットに１１．　ｌが立っている制御装
置は１台だけで、その制御装置が要求の処理へと進み、
他の制御装置は要求を無視する。

要求の処理へと進んだ制御装置はボート会ステータス表
を閲覧し、ボートＡおよびＢが空いているかどうかを確
かめて、空いていたならば、両ボートのステータスを“
′接続中”に更新する。ぎ欠に制御装置は、自らの制御
下にある垂直な内部バスを１本選び、接続に備える。自
らの制御下にあるバスで、その時点において他の接続に
供用されていないものであれば、どれを選んでも構わな
い。

実際に接続を行うに当たっては、バス・ステータス・レ
ジスタ３６の助けを借りることになる。このレジスタに
おいては、当該制御装置の制御下にあるバスごとにそれ
ぞれ１ビツトが割り当てられており、各バスのステータ
ス・・・空きか、使用中か・・・を表わす。たとえば、
使用中のバスについてはｌ　Ｏｌが立ち、未使用のバス
については１１″が立つといった具合である。さらに優
先度エンコーダ（図示せず）が、レジスタからの出力に
基づいて、選択すべき空きバスの番号を決める。バス番
号が決まった時点で、制御装置は、そのバスとポー）Ａ
およびＢにつながる各データ回線との交点に位置するク
ロスポイントをそれぞれＯＮして、接続を行うわけであ
る。これら一連の作業の流れは、制御ロジック３８によ
って進行状況が計時され、調整される。制御ロジックは
、回路素子に対して所要の制御信号を提供する役割を担
っている。

一方、ホード・ステータス表を閲覧した結果、ボートＡ
またはＢいずれかのステータスが既に接続中となってい
たならば、制御装置はこの要求をボートから外す。次い
で、制御装置は入口側のポート会アダプタに対し、接続
できない旨をボート・バスを介して通知する。これを受
けてボート・アダプタは、あるレベルの１リジエクトｌ
　（接続拒否）メツセージを返すことにより、ボートの
他端の要求を発した装置に対して、その旨を伝達する。

制御装置が担当するチップ列の全てのバスが使用中だっ
た場合は、別のレベルのリノエクトφメツセージが返さ
れる。全てのバスが使用中というのは、ブロッキング状
帳に他ならない。ブロッキングを回避するには、自らが
担当する範囲において同時に発生し得る最大接続数を捌
けるだけのバスを、各制御装置に割り当てておけばよい
。

各制御装置の制御下にある個々の垂直な内部バスのステ
ータスを保存するバス令ステータス番レジスタは、各制
御装置ごとに専用のものが用ぐ（されている。これら内
部バスは、各制御装置が独占的に使用するものだがらで
ある。これに対し、各ボートのステータスを保存するボ
ート−ステータス表は、全ての制御装置に共有されるも
のである。

切断要求の処理も、同様のやり方で、接続要求を処理し
たのと同じ制御装置によって行われれる。

制御装置は、その切断要求が自ら１こ曲番すたものと判
明したならば、接続のために使われて％１ｆニクロスポ
イントをＯＦＦすることにより、ＩクスをＭ：　）１１
する。したがって、バス・ステータス−レジスタ上のこ
のバスのステータスは、　′空き１番こ戻される。ポー
ト番ステータス表も、対応する２本のノくスが“空き”
であることを表わすよう番こ更新される。

本発明の利点のひとつは障害に対する抗姑性、特に制御
装置の障害に対する抗姑性１こある。ｊｌｌｌ＋御装置
が故障すると、その影響は、当該制御装置ｆｉ　ｈ（本
来担当することになっていた全ての要上１こ及シζ。

制御装置に障害に対する抗姑性を持たせるセこ（ま、ふ
たつのステップを遂行しなければならなし）。すなわち
、　（１）障害を検出し、　（ｉｔ）生きて−）る制御
装置をプログラムし直して、これら与こ故ＰＩした制御
装置の機能を移管する、の両ステップである。制御装置
の障害を検出する１こは、（１ろし）ろな方法がある。

ひとつのやり方は、自己テストを行わせることで、各制
御装置が正常動作時（こ（まｔ’Ｕり返し自らをテスト
し、誤りが見つかツを二場合（４ンステム支援プロセツ
サに報告するよう設計しておけばよい。このような自己
テスト回路の設計技術については、下記各文献及びそこ
における引用文献に記載されている旨を付記することで
、説明に代える。

１、　　Ｊ、　Ｐ、　Ｈａｙｓ　ａｎｄ　Ｅ、　Ｊ、　
ＭｃＣＩｕｓｋｅｙ。

“Ｔｅ５ｔａｂ口１ｔｙ　ｃｏｎｓｉｄｅｒａｔｉｏｎ
ｓ　Ｉｎｍ１ｃｒｏｐｒｏｃｅｓｓｏｒ−ｂａＳｅｄ　
ｄｅｓｌＢ、”　ＩＥＥＥＣｏｍｐｕｔｅｒ、　Ｖｏｌ
、　１３．　Ｎｏ、　３．　Ｍａｒｃｈ　１９８０゜Ｐ
Ｉ）、　＋７−２［ｉ。

２、　　Ｅ、　Ｊ、　ＭｃＣＩｕｓｋｅｙ、　”Ｂｕｌ
ｌｔｉｎ　５ｅｌｆ−ｔｅｓｔｔｅｃｈｎｌｃ＋ｕｅｓ
、”　ＩＥＥＥ　Ｄｅｓｌｇｎ　ａｎｄ　Ｔｅ５ｔ、　
Ｖａ２、　　Ｎｏ、２．　　入ｐｒｉｌ　　ｌ！１８５
．　　ｐｐ、２１−２８゜障害を検出するもうひとつの
方法は、システム支援プロセッサが、各制御装置を定期
的にテストするように設計しておくことである。いずれ
かの方法によって制御装置の故障が発見されたならば、
システム支援プロセッサは故障した制御装置の機能を、
残りの制御装置間に分散して振り分ける。

つまり、故障した制御装置に本来割り振られて０た要求
は、生きている制御装置間に振り替えられるわけである
。これを行うには、生きている制御装置のボート番号一
覧表を更新し、それまでは故障した制御装置が認識する
ことになっていた入口／出口の番号の組み合わせ（ボー
ト対）を、生きている制御装置が認識できるようにする
ことが考えられる。制？Ｂ装置が故障すれば、対応する
内部バスも使用不能に陥るの・はいうまでもない。その
結果、一部にブロッキングが生じることもあり得る。生
きている制御装置が自らに振り向けられた要求の全てを
捌くには、バスが足りないかも知れないからである。し
かしながら、ボートは全て、依然として使用可能である
。また、このようなブロッキングへの対策として、設計
段階において、いずれかの制御装置が故障した際に発生
する余分な負荷を受け持つためのバスを、あらかじめ追
加しておくことも考えられよう。

片側クロスポイント・マトリックスによって得られる抗
姑性を活かして、本発明は信頼性の高い交換システムを
構築するために用いることができる。全ての制御装置に
よって共菅されるボート・ステータス表が、システム全
体の障害を招く要となるのを避けるには、誤り訂正コー
ドによって保護すればよい。ポート壷バスは二重化によ
って信頼性を高めることができるし、性能も向上する。

二重化した結果、要求を２本の独立した経路を通して、
制御装置に振り向けられるからである。

要求の分散方法 上記において、ｍ台の制御装置はおのおの、要求によっ
て指定された入口側と出口側のボート２号が所定のもの
であった場合に、その要求を認識するようにセットされ
ている。システムの総ボート数をＮ個とし、各ボートは
自分以外の任式のボートへの接続を要求できるものとす
れば、全部でＮ（Ｎ−１）個の独立した要求が発生し得
る。

各要求はそれぞれが、独自の入口側と出口側のボート番
号の対を１旨定しているわけである。これらＮ（Ｎ−１
）個の接続要求・・・すなわち、それによって指定され
たボート対・・・を制御装置に分散して割り振っておき
、接続要求が発生した場合、ただ１台の制御Ｈ２だけが
これを認識できるようにしなければならない。

ボート対を個々の制御装置に割り振るに当たっては、全
体をどのように分散するかについて、何らかの規則や方
針が必要になる。この分散規則に基づいて策定された割
り振りにしたがって、システム支援プロセッサは各制御
装置のボート番号一覧表をセットするわけである。以下
においては、どのような割り振りがよいかを選ぶための
ハ飴を検討し、割り振りを行うための具体的な方法につ
いて説明する。

ふたつのボートを仮にＡおよびＢとし、両ボート間が接
続されているならば、いずれか一方が要求を発する側の
ボート（入口側のボート）となり、他方が出口側のボー
トとなる。もちろんＡＢ間の接続においては、Ａから要
求が発生することもあれば、Ｂから要求が発生すること
もある。つまり、どちらが入口側になるかということで
、Ａから要求が発生すればＢが出口側になり、Ｂから要
求が発生すればＡが出口側になる。したがって、両ボー
トにまつわる要求は、いずれがその要求を発した側であ
るかに関わらず、同一の制御装置が処理するはずである
。すなわち、どの制御装置％〒に割り振るかを考えるに
当たっては、ボート対ＡＢ（Ａが入口側−Ｂが出口側）
は、ボート対ＢＡと同様に扱われることになる。そこで
、要求を：１ｉｌｌ　１３０装置に割り振る方法のひと
つとして、ＡおよびＢから成るボート対を、Ａが先であ
るかＢが先であるかを区別せずに、同一の制御装置に割
り振るやり方が考えられる。

総数Ｎ　（Ｎ−１）個の独立したボート対があったとし
ても、各ボート対についてどちらのボートが先かを区別
しないとすれば、Ｎ（Ｎ−１）７２個のみを考えればよ
いことになる。Ｎ（Ｎｌ）７２個のボート対は、第４図
のような矩形のグリッドとして表わすことができる（図
では、Ｎ＝１６の場合を示す）。第４図において各点は
それぞれ１個のボート対を表わし、全部でＮ　（Ｎ−り
／２個のボート対が示されている（図では、１２０個）
。たとえば、ボート１と４とにまつわる要求は、グリッ
ドの下から１行目と左から４列目の交点に当たり、（Ｌ
　　４）と表記される。これらの点は、全体が三角形に
配置されており、底辺に沿って（Ｎ−１）個、底辺に沿
っても（Ｎ−１）個の点があるのが分かる。これにより
、要求を制御装置に割り振る問題を、第４図の各点が表
わすボート対をどの制御装置に割り振るがという問題上
して、視覚的にとらえることが可能になったわけである
。

全ての点がいずれかの制御装置に割り振られ、どの点も
複数の制御装置には割り振られていない限り、割り振り
方がどうであれ、機能自体に支障はない。しかしながら
、割り振り方によっては、以下のような問題が生じる可
能性がある。

１、［問題コ特定の制御装置に負荷が集中するり念があ
り、せっかくの平行処理能力に制約を与え、システムの
速度を低下させることにつながる。これは、多数の点を
１台の制御装置に割り振った場合に、起こり得ることで
ある。

［対策コ理想をいえば、ボートがらの要求が、各制御装
置に均等に割り振られるのが望ましい。そのような場合
、各ボートが他のボートにアクセスする割り合いが全て
等しいと仮定すれば、第４図の各点での対接続が発生す
る確率も全て等しいものとなる。したがって、通常は、
これらの点をほぼ同じサイズの）ｆｆに区画し、各群を
個別の制御装置に割り当てることにより、負荷の均等化
が図れる。

２、　　Ｃ問題ｊ遊体中のボート間で接続を行おうとし
た場合、これらのボートを担当する制御装置に割り当て
られた垂直バスのうち１本が、空き状態でなければなら
ない。

［対策コ理想をいえば、各制御装置に充分な本数のバス
が与えられ、次からっぎへとどのような要求が来たとし
ても、さらに要求が指定した入口側と出口側のボートが
いずれも遊体中で、したがって全ての要求を処理しなけ
ればならないとしても、空きバスが必ず１木見つかるこ
とが望ましい。単一の制御装置で片側マトリックスを制
御する場合は、バスがＮ／２本あれば、これを溝たすこ
とが可能である。一方、分散制御を行う場合においては
、各制御装置が交換機をノンプロンキング化するための
バスを、適当な本数保有していなければならない。その
本数は、各点のボート対を制御装置に割り振るやり方に
よって左右される。話を分かりやすくするために、第４
図において（１，２）、（１，３）　　　（１，４）、
　（１，５）　　（１，１３）、　（１，７）、（１，
８）、　（１，９）の８点が、１台の制御装置に割り当
てられていると仮定する。

ボート１がいずれのポート対にも関係しているため、対
接続は同時にひとつしか行えない。

したがって、バスが１本あれば、これら８つのポート対
全てをカバーすることができる。

つぎに、（１，２）、（３，４）　　　（５，８）、　
（７，８）（９，１０）、　（１１，１２）、（１３，
１４）（１５，１Ｂ）の８点が、１台の制御装置に割り
当てられているとする。これらの対接続は、全て同時に
行うことができる。したがって、交換機をノンブロッキ
ング化するためには、この制御装置は８本のバスを保有
しなければならない。割り振りを工夫することによって
、制御装置が全体として必要とするバスの本数を最少化
できるのが分かる。

区画を行うための具体的な方針を述べるに当たっては、
つぎのような原則に基づいて検討を行うことにする。

１、ポート対を表わす点の数が、各区画ごとにほぼ同じ
であること。

２、ノンブロッキングで稼働するために、区画全体に適
当な本数のバスを配備することになるが、その本数をで
きるだけ少なくすること。

まず、制御装置が２台の場合がら始める。基本的な考え
方は、第４図の三角形を面積がほぼ等しいふたつの領域
に、水平に分割するというものである。第５図に、１６
ポートの交換機を想定し、このような方針に基づいて区
画した例を示す。

ポート対を表わす点の総数は１２０個で、これらが水平
な直線によって二分されている。上部の三角形の区画に
は５５個の点が含まれ、下部の区画には６５個の点が含
まれる。なお、両区画のサイズの差はボートの総数Ｎに
よって左右され、この例では、もとの三角形を水平な直
線で二分した場合、各区画が同数の点を含むようにはで
きない。

区画が決まれば、各区画に含まれる個々の点は、それぞ
れ対応する制御装置に割り振られる。第５図において、
同時に実行可能な対接続の数は各区画とも５個であるか
ら、両区画併せて１０本のバスがあれば、ノンブロッキ
ング化が図れることになる。

一般にボートの総数をＮとし、制御装置を２台として区
画を行った場合、基本的な考えは、Ｎ（Ｎ−１）／２個
の点を含む三角形を二分し、ｊ−部がやはり三角形にな
るようにするというものである。このように区画すれば
、両区画に含まれる点の数の差は最少となる。また、上
部の区画において同時に実行し得る対接続の最大数は、
その区画の高さの半分となり、下部の区画において同時
に実行し得る対接続の最大数は、その区画の高さとなる
。したがって、この区画法を使用した場合に要するバス
の総数は、０．６４６Ｎである。！１１−の制御装置装
置を用いた場合に比べ、３０パーセントのオーバーヘッ
ドということになる。第５図の例では０．６４６Ｎ＝１
０，３３６であるから、１０．３３８以下の最大の整数
値を取って、１０本がバスの所要本数となる。これは、
前段で述べた値と一致する。

理論的には、三角形の領域をを等面積の区画に二分し、
ノンブロッキングで稼働するためには、バスの総数は、
Ｏ，Ｅｆ４６Ｎを下回ってはならない。したがって、上
記の割り振りは、バスの本数からみれば最善のものとい
うことができる。

基本的な考えが明らかになれば、任意の台数の制御装置
について、これを−膜化するのは簡単なことである。今
度は、三角形の領域を複数の水平な区画に分割し、各区
画の面積がほぼ等しくなるようにすればよい。各区画に
おいて同時に実行し得る対接続の最大数は、その富さか
ら容易に導くことができる。最」二段の区画では高さの
コ１′分、その他の区画については高さが、同時に実行
し得る対接続の最大数である。具体的な例として、この
方法で算定したバスの所要本数を制御装置の台数Ｎの小
数倍で表わし、つぎに示す。

表 第６図は、制御装置４台を有する１６ボートの交換機を
、同じ方法によって区画したものである。

各区画は上から下へそれぞれ２８個、２７個、３６個、
２９個の点を含む。各区画をノンブロンキングで稼働す
るために必要なバスの本数は、それぞれ４木、３本、３
本、２本で、総計は１２木になる。

第７図は、制御装置４台を有する２５６ボートの交換機
を、同じ方法によって区画したものである。三角形全体
に含まれる点の総数は、２５６Ｘ２５５÷２＝３２６４
０個となる。四つの区画は上から下へそれぞれ８１２８
個、８１７２個、８２４１個、８１０９個の点を含む。

各区画の高さは１２８．５３．４Ｌ　　３４である。し
たがって、全ての区画をノンブロッキングで稼働するた
めに必要なバスの総数は、６４＋５３＋４１＋３４．＝
１９２本となる。

要求の分散方法　２ 上記の方法は、各区画に含まれる点の数がほぼ同じとい
うものであった。ここでは、各区画に含まれる点の数を
、ちょうど同じにした場合の割り振り方について述べる
。この方法は、ボート数Ｎが制御装置の台数Ｍの倍数で
あるときに適用できる。第８図は、この方法によって、
４台の制御装置を存する１６ボートの交換機を区画した
ものである。

やり方は、簡単である。まず、Ｎ／２Ｍをｋと置く。三
角形の底辺から数えて最初のに行を制御装置１に、つぎ
のに行を制御装置２にと、＄制御表ＷＭまで順に割り振
っていく。Ｍまでいけば、Ｎ／２行をカバーしたことに
なる。残りの行については、順序を逆にして割り振って
いく。つまり、最初のに行を制御装置Ｍに、つぎのに行
を制御装置Ｍ−１にと、制御装置２まで進むわけである
。

この時点で、残りはに一１行となっているので、これを
制御装置１に割り振る。これによって、制御装置１以外
の全ての制御装置には２に行が、制御装置１には２に一
１行が、割り振られたことになる。

各制御装置が要する垂直なバスの本数は、区画２から区
画Ｍについては高々Ｎ／Ｍ本（第８図の例では４本）、
区画１については高々Ｎ／Ｍ−１本となる。したがって
、この方法によれば、ノンブロッキングで稼働するため
に要するバスの耐氷数は、最大でＮ−１本となる。

いま述べた要求分散方法２においては、各制御装置はち
ょうど同じ数の点を割り振られている。

したがって、平均してみれば、各制御装置の負荷は均衡
することになる。一方、第７図の各区画間では、そこに
含まれる点の数に、最大１，６バーセントのばらつきが
ある。実際には、Ｍに比べてＮが大きくなるので、区画
のサイズに若干のばらつきがあっても、性能に大きな影
響は与えない。

したがって、はとんどの場合、バスの数にオーバーヘッ
ドの少ない要求分散法１の方が好ましいといえる。

いずれかの制御装置が故障した場合、そこに割り振られ
ていた機能を、生きている制御装置間に分散して振り替
えなければならない。このようなシステム構成の変更に
おいては、　（ｉ）生きている制御装置が受け持ってい
る接続に、それと気付かれぬように行う、　（ｉｉ）全
ての接続を−月停止して、制御装置の初期化をやり直す
、のふたつのやり方がある。

（ｉ）の方が好ましいのだが、いずれの方法を取るにせ
よ、生きている制ノ装置１台当たりのボート対は増加す
ることになる。また、一般１こは、各区画において同時
に発生し得る最大接続数も増加する。その結果、いずれ
かの区画にお℃）でノくスの本数が最大接続数を下回っ
た際には、ブロッキングにいたる可能性がある。したが
って、制御装置の故障に当たってボート対の振り替えを
行う場合は、このようなブロッキングを最少化するよう
配慮しなければならない。

１、生きている制御装置を停止せず振替えを行う：　好
ましいやり方である。システムの運用を停止することな
く、故障した制御装置の機能を生きている制御装置間に
分散して振り替えるもので、影響を受ける接続は、故障
した制御装置が担当していたものにとどまる。生きてい
る制御波；？７にもともと割り振られていたボート対は
、変更を受けない。故障した制御装置に割り振られて０
たボート対は、生きている制御装置間に分散して振り替
えられる。

具体的には、障害の発生した区画に割り振られているボ
ート対を、障害のない区画に分散して振り替えなければ
ならない。どのように振り替えるかは、もとの割り振り
によって左右される。繰り返しになるが、故障した制御
装置に割り振られていた全てのボート対が生きている制
御装置に振り替えられ、どのボート対も複数の制御装置
には割り振られていない限り、振り替え方がどうであれ
、機能自体に支障はない。しかし、振り替えを実行する
に当たっては、もとの割り振りを行う場合と同様の原則
に基づいて行うべきである。すなわち、 （ｉ）ボート対を表わす点の数が、各区画ごとにほぼ同
じであること。

（ｔ　ｉ）ノンブロッキングで稼働するために、区画全
体に適当な本数のバスを配備することになるが、その本
数をできるだけ少なくすること。これにより、制御装置
の故障に伴うブロッキングを、最少化することができる
。

このことから、第６図に示されたやり方にしたがって、
障害のある区画に含まれる各点を他の区画に振り替えれ
ばよいのが分かる。もとの割り振りを決定する基礎とな
った考え方が、故障した制御装置が担当する区画内の各
点を振り替える際にも、適用できるわけである。それは
、基本的には、問題の領域をＭ−１個の水平な区画に分
割し、各区画に含まれる点の数がほぼ同じになるように
するというものであった。

たとえば、制御装置１が故障したと仮定する。

第６図でいえば、−容土の区画に相当する部分である。

ここに含まれる２８個の点を３群に分割し、残りの３台
の制御装置に割り振ることになる。その割り振りは、つ
ぎのようになる。

第１群： （１５，１Ｂ）、（１４，１５）、（１４，１Ｇ）（１
３，１４）、（１３，１５）、（１３，１６）（１２，
１３）、（１２，１４）、（１２，１５）（１２、１６
） 第２群： （１１，１２）、（１１，１３）、（１１，１４）（Ｉ
Ｃｌ３）、（１１，１６）、（１０，１ｔ）（１０，１
２）、（１０，１３）、（１０，１４）（１０，１５）
、（１０，１６） 第３群： （９，１０）、　（９，１１）、　（９，１２）（９，
１３）、（９，１４）、（９，１５）（９，１６） 第１群には１０個、第２群には１１個、第３　ＪｔＦに
は７個の点が、それぞれ含まれている。第１群を制御装
置２に、第２群を制御装置３に、第３群を制御装置４に
、割り振ればよいわけである。

２、運用を一旦停止してシステム構成を改ＮＵする：　
いずれかの制御装置が故障するのを侍って、ボート対の
制御装置への割り振りを−がらやり直す方法である。基
本的な馬え方は、Ｎ（Ｎ−１）７２個の点を残った制御
装置間に割り振るのというもので、そのアルゴリズムに
ついては既に述べたとおりである。全ての接続を一旦停
止するという意味で、故障した制御装置が担当する接続
を停止するだけだった前述の方法とは著しい対）１．０
を見せるが、新しい割り振りを最適化することができる
ため、爾後のブロッキングを低く押さえることができる
。

いずれの方法においても、割り振りのやり直しを行うの
はシステム支援プロセッサで、当該プロセッサは、制御
装置に割り振られたボート対の状態を常に監視している
。新たな故障が発生しても、以上のやり方で対応すれば
よい。最悪の場合は、生きている制御装置が１台になり
、　Ｎ　（Ｎ−１）７２個のボート対が全てこれに割り
畷られることになる。

本技術の一部を修正したり変更することによって多くの
応用例が考えられるが、代表的なものを以下に述べるに
止める。

たとえば、上記の実施例においては、各制御装置には、
それぞれほぼ同数の独立したボート対が割り振られてい
た。その結果、各制御装置の負荷は、平均してみれば、
いずれも等しくなる。もちろん、要求の分布は一様であ
る・・・どのボート対もほぼ等しい確率で現われる・・
・と仮定していたわけである。しかしながら、要求の分
布が片寄っている・・・特定のボート対が他よりも頻繁
に現われる・・・場合には、ボート対の割り振りを不均
一にすることによって、制御装置間の負荷バランスを均
衡させることができる。つまり、各制御装置に異なった
数のボート対を割り振り、装置ごとに全ボート対の出現
確率を累計したとき、それがほぼ同一になるようにして
もよいわけである。

分散制御でノンブロッキング稼働を実現しようとすれば
、オーバーヘッド用のバスを追加しなければならない。

しかしながら、実際の運用においては、各区画で同時に
発生し得る最大接続数より少ないバスでも、外見上はと
んどブロッキングを起こさずに稼働することができる。

接続要求は本来ランダムに発生するものであり、そのよ
うに膨大な数の接続が一時に集中することは、きわめて
希だからである。たとえば、１００万回のｄ求につき１
回のブロッキングが発生するとしても、システムの性能
が低下したと感じるのは無理である。

したがって、ある程度のブロッキングは認めた上で、設
計を行うのもひとつの選択である。

Ｅ１発明の効果 以上のように本発明によれば、交換機の大幅な速度改善
が達成され信頼性の高い交換機が実現される。

【図面の簡単な説明】

第１図は、従来技術による、単一の制御装置を何する片
側クロスポイント交換機の概略図である。 第２図は、本発明の実施例に基づく、複数の制御装置を
有する片側クロスポイント交換機の概略図である。 第３図は、第２図の制御装置およびそれに付随するイン
タフェースの詳細図である。 第４図は、１６ボートの交換機におけるデータ回線対の
一覧を示す図で、要求を制御装置に分配する方法を分か
りやすく示すために、三角形に配置した図である。 第５図は、制御装置が２台の場合、１６ボートの交換機
におけるデータ回線対を、制御Ｈ置に分散して割り付け
る方法を示した図である。 第６図は、制御装置が４台の場合、１６ボートの交換機
におけるデータ回線対を、制御装置に分散して割り付け
る方法を示した図である。 第７図は、制御装置が４台の場合、２５６ボートの交換
機におけるデータ回線対を、制御装置）ηに分散して割
り付ける方法を示した図である。 第８図は、制御装置が２台の場合、１６ボートの交換機
におけるデータ回線対を、制御装置に分散して割り付け
るための、別の方法を示した図である。

Claims (3)

【特許請求の範囲】
1. （１）片側クロスポイント交換機で、 一群のポートと、 前記各ポートに１本ずつ接続されたデータ回線と、 一群のバスと、 前記各データ回線と前記各バスとを接続する各１個のク
   ロスポイント交換素子と、 前記各ポートが前記他のポートに接続されているか否か
   のステータスを保存しておくためのステータス表となる
   手段と、 接続および切断の要求を受け取るための一群の制御装置
   で、 前記各制御装置が、前記内部バスの少なくとも１本に接
   続している前記クロスポイント交換素子を制御し、 前記各制御装置が、ポート対の一覧表を保存するための
   手段を有し、前記一覧表に収載されたポート対について
   のみ接続および切断の要求を取り扱い、 前記各制御装置が、要求のあった接続または切断を実行
   する以前に前記ステータス表となる手段を閲覧し、接続
   を求められている各ポートのステータスを確認し、要求
   のあった接続または切断を実行した時点で前記ステータ
   ス表となる手段を更新するような一群の制御装置と、 発生し得る各ポート対を前記各制御装置のそれぞれに一
   意的に割り振るためのシステム支援プロセッサとなる手
   段とを有することを特徴とする片側クロスポイント交換
   機。
2. （２）請求項１の片側クロスポイント交換機で、さらに
   、 前記各制御装置の障害を検出するための手段を有し、 前記システム支援プロセッサが、障害を起こしていない
   制御装置間に、前記障害を起こした制御装置に割り振ら
   れていたポート対を振り替えることを特徴とする 片側クロスポイント交換機。
3. （３）請求項１の片側クロスポイント交換機で、さらに
   、 前記制御装置が同時に稼働することによって、同時に多
   数の接続および切断要求を取り扱うことを特徴とする 片側クロスポイント交換機。