JPH02237248A - 多段相互接続ネツトワークにおける交換方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明は、一般に多段相互接続ネットワーク（Ｍ　Ｉ　
Ｎ）を介してデータ・パケットを交換する方法に関する
。具体的には、本発明は、分散制御によりＭＩＮを介し
てデータ・パケットを交換する方法に関する。こうした
方法は、１つまたは１組の宛先（ホット・スポット）へ
の・過大なトラフィックが、ネットワークの他の宛先に
向かう均一なトラフィックの品質をほとんど低下させず
に支援できるようにする。各パケット中の各アドレス・
ビットが、ネットワークの特定の段でパケットの経路を
決定し、パケットは、現在バッファ内にあるパケットの
アドレス・ビット及びバッファの可用性に基づいてバッ
ファのある段で受け入れられる。

Ｂ．従来技術 計算機の能力に対する要件が増大するにつれて、計算要
件を支援するために複数のプロセ・ソサを相互接続する
ことがますます重要になってきている。

すなわち、プロセッサ同士またはプロセ・ソサと共用メ
モリを接続する高速ネッｌ・ワークが求められている。

プロセッサをメモリに相互接続するネットワークは多数
知られている。これらのネ・ソトワークのうちで、ＭＩ
Ｎは高帯域幅をもたらし、ネ・ソトワークに段を追加し
てモジュール式にサイズを増大することができ、複雑さ
がＯ　（Ｎ１ｏｇＮ）（ただしＮはプロセッサまたはメ
モリ・モジュールの数）であるので、特に魅力がある。

最も重要なことであるが、ＭＩＮは、分散アルゴリズム
を用いて、集中制御装置をもつネットワークで発生する
ネ・ソクなしに制御することができる。

ＭＩＮをプロセッサとメモリの相互接続に使用する際に
発生する深刻な問題は、ツリーの飽和である。この問題
は、プフィスター（Ｐｆ　ｉｓｔｅｒ）　　の論文「多
段相互接続ネットワークにおけるホット・スポットの争
奪及び結合（Ｈｏｔ　Ｓｐｏｔ　Ｃｏｎｔｅｎｔｉｏｎ
ａｎｄ　Ｃｏｍｂｉｎｉｎｇ　ｉｎ　Ｍｕｌｔｉｓｔａ
ｇｅ　ＩｎｔｅｒｃｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋ
ｓ）　Ｊ　Ｉ　Ｅ　Ｅ　Ｅコンピュータ紀要（ＩＥＥＥ
Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ
）　）Ｃ　−　３　４　（　１　０　）　１１９８５年
１０月、ｐｐ．．９４３−９４８に記載されている。デ
ータ・パッケージのトラフイツクを、ネットワーク内の
様々なメモリ装置に均一に伝送するときは、この問題は
発生しない。しかし、プロセッサからホット・スポット
と呼ばれる特定のメモリに向かう過大なトラフィックが
あるとき、ホット・スポットに通じるバッファは、ホッ
ト・スポットにアドレス指定されたパケットで満杯にな
る。バッファが満杯になると、プロセッサから他のメモ
リへのトラフイックが阻止され、したがってネットワー
ク全体が停止する。

上記論文では、ツリーの飽和を緩和するために結合と呼
ばれる方法が開示されている。しかし、１）特定のアレ
イ・アクセス・７寸ターン、２）ホ・ソト・スポットに
対する結合不能な更新、また＋ｔ　３　）特定のデータ
項目ではなくメモリ装置へのー■寺的な過大負荷のため
に、結合不能で不均一なデータ・アクセス・パターンが
発生することがある。さらに、結合法は、共用メモリの
ないシステムでｌｉ４吏用できないことがある。

ＭＩＮは遠隔通信パケ・ｙ｝交換用に提案されたもので
ある。たとえば、ターナー（Ｔｕｒｎｅｒ　）の米国特
許第４４９４２３０号及び米国特許第４４９１９４５号
を参照のこと。これらの特許は、遠隔通信パケット交換
のためにＭＩＮを使用することを教示している。こうし
たネ・ソトワークでトラフィックが不均一てあると、ネ
・ソトワーク内のある宛先に向かうパケ・ソトの不均一
で過大なトラフィックのためにツリーの飽和が発生した
とき、これらのネットワークに類似の閉塞が起こる。こ
の出願でも結合はうまく曇かない。

アカシの米国特許第４５００９９０号は、ＣＳＭＡ／Ｃ
Ｄネットワークでノ寸ケ・ソトを満杯の／ク・ソファに
再伝送させるバッファあふれ信号を生成する方法が記載
されている。この方法は、ＣＳＭＡ／ＣＤ　（イーサネ
ット型式）構内ネットワークに固有のもので、ＭＩＮで
は使用できない。

サーヴエル（Ｓｅｒｖｅｌ　）の米国特許第４６０３４
１６号は、ビット直列方式で大カリンクに到達したパケ
ットをパケット並列形式に変換し、この並列形式でタイ
ム・スロット交換し、最終的にビット直列形式に再変換
するという交換方法を記載している。内部では、１つの
パケットが１２８ビットの並列形式で同時に伝送される
。交換は単一段として編成されている。メモリはタイム
・スロット交換装置と同様で、パケットは到達したとき
メモリ・モジュールに記憶される。次いでパケットが正
確な時間にメモリから読み取られ、出力線に供給される
。この交換方法は、ＭＩＮにおけるホット・スポット問
題を解決するには有用でない。

チャン（Ｃｈａｎ　）の米国特許第４５５６９７２号は
、パケット交換機から回路交換機を介してある宛先に割
り振られたリンクの数が、その宛先に向かうパケット・
１・ラフィックのボリュームに基づいて動的に制御され
るという、パケット交換機から回路交換機へのインター
フェースを教示している。パケット交換機を通過する間
のパケットの遅延を監視する方法は、ターナーの米国特
許第４５５１８３３号に記載されている。

そして、最後に、」二位コンピュータ・システムと複数
のデバイス制御装置の間で同期をとる方法が、ラビンソ
ン（　Ｒｕｂ　ｉｎｓｏｎ　）の米国特許第４４４９１
８２号に教示されている。各プロセッサは、競合状態を
生み出すことなくそれ自体の速度で動作し、入出力バス
上のハードウェア・インターロック機能が不要である。

Ｃ．開示の概要 本発明は、ホット・スポット・トラフィックによって均
一トラフィックのパフォーマンスが低下するのを防止す
るための、多段相互接続ネットワーク（ＭＩＮ）を介し
てデータ・パケットを交換する方法である。各パケット
中の各アドレス・ビットによって、ネットワークの特定
の各段でそのパケットが向うべき出力リンクを決定する
。パケットは、受入れ検査に合格した場合にだけその段
の大カバッファで受け入れられる。この受入れ検査は、
ネットワークのある段の大カバッファでのバッファの可
用性だけではなく、パケットのアドレス・ビットカハッ
ファ中の他のパケットのアドレス・ビットとどう関係し
ているか、及びネットワークの段にも基づくものである
。受入れ検査に合格しなかった場合、そのパケットはＭ
ＩＮの前の段に保持され、その段のバッファ中のパケッ
トノ待チ行列の後尾に移され、すなわちその待ち行列で
より低い優先順位を与えられる。

Ｄ．問題点を解決するための手段 ホット・スポットが存在すると、あるプロセッサから発
してホット・スポットにアドレス指定されたパケットが
通過しなければならないすべてのパッファは、そのホッ
ト・スポットに向かうパケットで満杯になる。そのため
にツリーの飽和が起こる。ツリーの飽和を防止するには
、ホット・スポットにアドレス指定されたパケットでバ
ッファを満杯にならないようにする。これは、移動中の
到来パケットのアドレスをすでにあるバッファ内にある
パケットのアドレスと比較することによって実施される
。交換バッファがすでに到来パケットと同じユニットに
向かうパケットを含んでいる場合、その到来パケットは
バッファに入るべく受け入れられない。あるパケットが
受け入れられない場合、そのパケットは、他のパケット
が転送できるように、現在のバッファ内のパケット待ち
行列の最後尾に移される。

この方式で交換機を動作させると、どのバッファにも、
ホット・スポットに向かうパケットがせいぜい１つしか
あり得ないので、ホット・スポットに通じるバッファの
連鎖が同じホット・スポットに向かう複数のパケットで
満杯になることが防止される。さらに、潜在的なホット
・スポット・トラフィックとして検出されたパケットが
、その待ち行列の後尾に移されて、均一のトラフィック
が通過できるようになるので、均一のトラフィックは閉
塞されない。

ネットワーク内の各交換機は以下のように動作する。あ
るクロック・サイクルの開始時に、各交換機入力待ち行
列にあるパケットが転送すべく選択される。待ち行列の
先頭にある２つのパケットが同じ出力に向かう場合、そ
のうちの１つが仲裁方式によって選択される。選択され
たパケットは同時に次の段に送られ、そこで一時的にバ
ッファに保持される。次の段バッファが満杯、すなわち
到来パケットと同じ宛先に向かうパケットを含んでいる
場合、否定応答が前の段に送られ、そのパケットはその
前の段バッファの後尾に移される。

そうでない場合は、パケットが次の段バッファに入れら
れ、前の段バッファから削除される。

Ｅ．実施例 第１図に、本発明の代表的な３段ＭＩＮ１０の構成図を
示す。ＭＩＮＩＯは、交換機１６ａ−１及びバッファ記
憶機構１４ａ−ｘを介してメモリ装置１８ａ−ｈと通信
するプロセッサ１２ａ−ｈを含む、マルチプロセッサ・
コンピュータ・システムである。当業者なら理解できる
ように、本発−１０＝ 明は、任意の数の段で使用できるように容易に適応でき
る。各プロセッサ１２ａ−ｈはそれぞれデータのパケッ
トを発信し、当該の各バッファ入力線１３ａ−ｈを介し
て各バッファ記憶機構１４ａｈに送る。こうしてバッフ
ァ記憶機構１４ａ−ｈが受け取ったデータのパケットは
、次に、ＭＩＮ１０を介してメモリ装置１８ａ−ｈに送
られる。

第１図では、わかりやすいように、一部の参照番号を省
略してある。

ＭＩＮＩＯは複数の段として構成され、各段が複数の２
人力２出力交換機１６ａ−１を含む。ＭＩＮＩＯの第１
段は、交換機１６ａ−ｄを含み、第２段は交換機１ｅｅ
−ｈを含む、第３段は交換機１６ｉ−１を含む。このよ
うにＭＩＮＩＯの各段には４つの２人力２出力交換機が
示してあるが、当業者なら理解できるように、ＭＩＮＩ
ＯはＮ入力Ｍ出力及びその他の相互接続パターンをもつ
交換機を含むことができる。ＭＩＮＩＯの段相互間の相
互接続パターンは、当業者には周知である。

各交換機ＩＥｔａ−１は２つのバッファ記憶機構１４ａ
−ｘを備えており、１つの交換機の各バッファ記憶機構
はそれぞれ、様々なメモリ装置１８ａ−ｈにアドレス指
定されたそれ自体のパケット待ち行列を含む。プロセッ
サ１２ａ−ｈは、メモリ装置１８ａ−ｈに向かうパケッ
トを、前述のように第１段交換機１８ａ−ｄのバッファ
記憶機構１４ａ−ｈのうち当該のものの待ち行列に入れ
る。

パケットは、それが発信プロセッサ１２ａ−ｈの１つに
よって送られるメモリ装置１８ａ−ｈのアドレスを含む
。パケッ１・内のアドレスは、交換機１６ａ−１が、パ
ケットを発信プロセッサ１２ａ−ｈからＭＩＮ１０を介
して宛先メモリ装置１８ａ−ｈの１つに経路設定するた
めに使用する。

プロセッサ１２ａ−ｈが、メモリ装置１８ａｈに均一に
アドレス指定されたパケットを発信するとき、ＭＩＮＩ
Ｏを通る１・ラフィックは均一となる。しかし、メモリ
装置１８ａ−ｈにアドレス指定されたパケットが不均衡
に特定のメモリ装置１８ａ−ｈにアドレス指定されると
きは、不均衡に大きな数のパケットがアドレス指定され
た宛先メモリ装置１８ａ−ｈはホソト・スポットになる
。

そのホット・スポットに通じるＭＩＮＩＯを通る経路が
塞がって、ツリーの飽和をもたらすことがある。その場
合、そのホット・スポット以外のメモリ装置１８ａ−ｈ
に向かうトラフイックは、それが塞がった経路を通過し
なければならない場合、阻止される。

たとえば、プロセッサ１２ａ−ｈからのパケットが不均
衡にメモリ１８ｃにアドレス指定されると、第１図でバ
ッファ記憶機構１４ｓ１　ｔを黒く塗って示すように、
バッファ記憶機構１４ｓ１　ｔを満杯にする。ＭＩＮＩ
Ｏの第３段の他のバッファ記憶機構はどれもホット・ス
ポット・メモリ装置１８ｃに通じていす、したがってＭ
ＩＮＩＯの第３段の他のバッファ記憶機構はホット・ス
ポット・メモリ１８ｃに向かうトラフィックによって満
杯にならない。しかし、Ｍ工Ｎ１０の第２段では、図の
ように、バッファ記憶機構１４１１ｊ１ｍｓｎはすべて
ホット・スポット・メモリ１８ｃに通じている。バッフ
ァ記憶機構１４１１　ｊはバッファ記憶機構１４ｓに通
じ、バッファ記憶機構１４ｍ１ｎはバッファ記憶機構１
４ｔに通じている。したがって、バッファ記憶機構１４
ｔｉ　ｊ１ｍ１ｎの待ち行列はすべて、ホット・スポッ
ト・メモリ装置１８ｃに向かうトラフィックで満杯とな
り、バツファ記憶機構１４１１ｊ１ｍｚ　ｎを通過しな
ければならないメモリ装置１８ｃ以外のメモリ位置に向
かうパケットが遅延されることがある。

ＭＩＮＩＯの第１段では、すべての第１の段バツファ記
憶機構１４ａ−ｈが、ホット・スポット・メモリ装置１
８ｃに向かう経路にある第２段バツファ１４　ＩＮ　ｊ
１ｍ１ｎの１つに通じているので、すべてのバッファ記
憶機構１４ａ−ｈが、メモリ装置１８ｃにアドレス指定
されたパケットで満杯になることがある。すなわち、す
べての第１段バ・ソファ記憶機構１４ａ−ｈの待ち行列
が、ホット・スポット・トラフィックで満杯になり、Ｍ
ＩＮ１０トラフィックがすべて停止することがある。

このツリーの飽和の問題を防止するために、本発明の方
法では、転送中のパケットのアドレスをすてに受信側バ
ッファ記憶機構１４ａ−Ｘ中にあるすべてのパケッ１・
のアドレスと比較し、この比較に基づいて受入れ検査を
実行することによって、任意のホット・スポット・メモ
リ装置１８ａ−ｈにアドレス指定されたＭＩＮＩＯ内の
パケッ１・が、どのバッファ記憶機構１ｔ３ａ−１をも
満杯にしないようにする。具体的には、受信側バッファ
記憶機構１４ａ−ｘは、転送されたパケットと同じ宛先
に向かうパケットをすでに含んでいる場合、転送された
パケットを受け入れない。そのため、どノハッファ記憶
機構にも、ホット・メモリ装置に向かうパケットがせい
ぜい１つしかあり得ないので、特定のホット・スポット
・メモリ装置１８ａ−ｈに通じるバッファ記憶機構１４
ａ−ｘの連鎖が満杯になることが防止される。

したがって、あるクロツク・サイクルの開始時に、各バ
ッファ記憶機構の先頭にあるパケットが、ＭＩＮＩＯの
次の後の段のバッファ記憶機構に転送すべく選択される
。２つのパケットが同じ交換機出力にアドレス指定され
る場合、それらの１っが落とされ、もう１つか転送され
る。次の段で、どの到来パケットも、一時的到来パケッ
ト・バッファ（たとえば、第２図の到来パケット・バッ
ファ１１Ｅｉａ）に保持され、受入れ検査が実行される
。

次の段のバッファ記憶機構が転送されるパケットと同じ
宛先に向かうパケットを含む場合、否定応答信号（ＮＡ
ＣＫ）が前の段に送られる。次いで、そのパケットが前
の段のバッファ記憶機構の待ち行列の後尾に移される。

そうでない場合、パケットが次の段のバッファ記憶機構
に入れられ、前の段のバッファ記憶機構から削除される
。

ＭＩＮＩＯの各段で、個々の宛先メモリ装置１８ａ−ｈ
のアドレスを含むパヶッ１・内のアドレス・フィールド
の１ビットは、交換機ＩＥｉａ−１が、各クロツク・サ
イクル中にそのパケットを経路設定するために使用する
。交換機１６ａ−１内でのこの経路設定は、パケットの
アドレス・フィールド中の上記のビットに応じて、ＭＩ
ＮＩＯの次の段にパケットを転送するために交換機１ｔ
３ａ−１の２つの出力ポートのどちらを使用すべきかを
決定することによって実行される。したがって、ＭＩＮ
ＩＯの各段て、パケットの経路設定に使用される宛先ア
ドレスのビットは、経路設定ビットである。

２つのパケットが同じクロック・サイクル中に個々の交
換機１６ａ−１の同じ出力ポートへの経路設定を必要と
する場合、競合が発生する。競合パケットのうちの１つ
が回転木馬方式で選択される。ただし、当業者なら理解
できるように、ランダム選択など競合するパケット対か
らパケットを選択するための他の方法も使用できる。

第２図に、交換機ｌｅａとバッファ記憶機構１４ａの構
成図を示す。交換機１６ａとバッファ記憶機構１４ａの
詳細な構造及び機能について述べるが、当業者には当然
のことながら、この説明はＭＩＮＩＯ内の交換機１ｔ３
ａ−１とバッファ１４ａ−Ｘのどれにも同様に当てはま
る。

交換機１ｔ３ａは２つのサブスイッチ１００ａ１ｂを含
む。交換機１６ａ内のザブスイッチ１００ａＮ　ｂは、
それぞれ入力データ線１３ａ１ｂｔ到来ハケッ１・・バ
ッファ１１ｅａＮｂ１及びバッファ記憶機構１　４ａ１
ｂを介してプロセッサ１２ａ１ｂからデータ・パケッ１
・を受け取る。入力データ線１３ａを介してサブスイッ
チ１００ａが受け取ったパケットは、パケットの経路設
定ビットに応じてサブスイッチ１００ａの出力データ線
１５ａまたはサブスイッチ１００ｂのデータ線１５ｂに
送られる。同様に、データ線１３ｂを介してサブスイッ
チｉ　ｏｏｂが受け取ったパケットは、受け取ったパケ
ットの経路設定ビットに応じて、出力データ線１５ａま
たは１５ｂに送られる。

ＭＩＮＩＯの第１段で、プロセッサ１２ａ１ｂから任意
のメモリ装置１８ａ−ｈに送られるデータ・パケットは
、それぞれ当該の到来パケット・バッファ１１６ａ，ｂ
に入れられる。たとえば到来パケット・バッファに入れ
られたパケットが、サブスイッチ１００ａが以前に受け
取りサブスイッチ１００ａのバッファ記憶機構１４ａ内
の待ち行列に記憶したパケットと比較される。新しく受
け取ったパケットとこの待ち行列中にすでに記憶されて
いたパケットの比較は、受入れ検査及びバッファ制御モ
ジュール１０８ａ内で実行される。サブスイッチ１００
ｂでも同様の動作が行なわれる。

当該の否定応答（ＮＡＣＫ）線１００ａ，ｂが、各受入
れ検査モジュール１０８ａ１ｂに設けられている。線１
１０ａ１ｂはそれぞれ新しく受け取ったパケットを転送
したＭＩＮＩＯの前の段に、またはパケットを発信する
プロセッサ１２ａ−ｈに接続されている。交換機１６ａ
の場合、線１１０ａ１’ｂはそれぞれプロセッサ１２ａ
，ｂに接続されている。受入れ検査モジュール１０８ａ
または１０８ｂが、それぞれ到来パケット・バッファ１
ｌｅａまたは１１６ｂに入れられたパケットを受け入れ
るべきだと決定した場合、それぞれ線１１０ａまたは１
１０ｂは論理レベルＯに設定される。

受入れ検査モジュール１０８ａまたは１０８ｂが、それ
ぞれ到来パケット・バッファ１１６ａまたは１１６ｂに
到着するパケットをそれぞれ拒絶すべきだと決定した場
合、それぞれ線１　１０ａまたは１１０ｂが論理レベル
１に設定される。

各サブスイッチ１００ａ１ｂはまた、それぞれ選択機構
１０６ａ，ｂを備えている。サブスイッチ１００ａ１ｂ
内の各選択機構１０６ａ，ｂは、バッファ記憶機構１　
４ａ１ｂの両方に接続されている。たとえば、選択機構
１０６ａはバッファ記憶機構１４ａと１４ｂの両方に接
続され、選択機構１０６ｂはバッファ記憶機構１４ａと
１４ｂの両方に接続されている。すなわち、どちらの待
ち行列中のパケットも、サブスイッチ１００ａ１ｂの一
方を介して経路設定でき、各バッファ記憶機構１４ａｔ
ｂの先頭にあるパケットが、各パケットの経路設定ビッ
トに応じて選択機構１０６ａ１ｂの一方に提示される。

両方の経路設定ビットが１である場合、両方のパケット
が選択機構１０６ｂに送られる。両方の経路設定ビット
がＯの場合、両方のパケットが選択機構１０６ａに送ら
れる。すなわち、バッファ記憶機構１４ａ１ｂの先頭に
同じ経路設定ビットをもつパケソトがあり、かつ両方の
バッファ記憶機構が同じサイクル中に選択機構１０（３
ａ１ｂのうち同じものにパケットを提示する場合、競合
が発生する。競合のある選択機構１０Ｅ３ａ１ｂの１つ
に提示された２つのパケットのうちの１つが、その選択
機構により回転木馬式調停によって次の段のバッファ記
憶機構１４ｉまたはパッファ記憶機構１４ｋに転送すべ
く選択される。第３段の交換機１６ｉ−１の場合、この
選択処理で、バッファ記憶機構１４ａ−ｘの１つではな
くメモリ装置１８ａ−ｈの１つに転送するパケットが選
択される。

ＭＩＮＩＯの次の段（第２段）がそれぞれ選択機構１０
８ａ１ｂによって線１５ａまたは１５ｂに送られたパケ
ットを受け入れる場合、第２段の交換機１ｅｅ，ｆから
の当該の否定応答線１１２ａ１ｂ上で論理レベルＯを受
け取る。そのパケットが第２段で拒絶されると、当該の
否定応答線１１２ａ，ｂｌで論理レベル１を受け取る。

線１１２ａ上で選択機構１０６ａが受け取った否定応答
信号は、選択機構１０６ａがバッファ１４ａまたは１４
ｂのどちらからパケットを選択するかに応じて、選択機
構１０６ａから線１１３ａを介して受入れ検査モジュー
ル１０８ａに、または線１１３ｂを介して受入れ検査モ
ジュール１０８ｂに中継される。線１１２ｂｌで選択機
構１０６ｂが受け取った否定応答信号も同様に、線１１
３ｄを介して受入れ検査モジュール１０８ｂに、または
線１１３ｃを介して受取り検査モジュール１０８ｂに中
継される。受入れ検査モジュール１　０　８　ａ　Ｎｂ
のどちらかが、パケットが受け入れられたことを示す論
理レベルｒＯＪの否定応答信号を受け取った場合、それ
を転送した方のパケットは、バッファ記憶機構１４ａｓ
ｂから削除される。

第３図に、クロック・サイクル１５０を示す。

ＭＩＮＩＯは単一のクロック信号によって同期されてい
るが、当業者なら理解できるように、本発明の方法は、
２つ以上のクロックをもつシステム及び非同期動作を含
むシステムでも使用できる。

クロック・サイクル１５０の立上りの時点１５２で、プ
ロセッサ１８ａ１ｂからのパケットがそれぞれ到来パケ
ット・バッファ１１６ａ，ｂにクロックされる。同様に
、ＭＩＮ１０内の前の段からのパケットが、ＭＩＮＩＯ
の第２段及び第３段の到来パケット・バッファにクロツ
クされる。受け取ったパケットは、そのパケットが転送
される先のサブスイッチ１００ａ，ｂに応じて、受入れ
検査モジュール１０８ａまたは１０８ｂによってバッフ
ァ記憶機構１０２ａ１ｂの内容と組合せ比較される。時
点１５４で否定応答信号が生成され、ＭＩＮＩＯの前の
段に送り戻される。時点１５６て、バッファ記憶機構１
４ａｉｂの状態が、次の段による到来パケットの受入れ
または拒絶を反映するように変更される。たとえば、転
送されたパケットが時点１５４で受け入れられた場合、
次のパケットが時点１５６でバッファ待ち行列の先頭に
ある。

時点１５６の後で、必要ならバッファ記憶機構１　４　
ａ　１ｂ内の待ち行列の先頭にある新しいパケッ１・が
選択機構１０６ａまたは１０６ｂによって選択され、次
の段の到来パケット・バッファに送られる。ＭＩＮＩＯ
内の次のクロツク・サイクル１５０の開始時に、交換機
１ｅａ−１の入力端に提示されたパケットが次の段にゲ
ートされる。

クロック・サイクル１５０は、段間でパケットを転送す
るための単一ハーフ・サイクルで示されているが、当業
者なら容易に理解できるように、この設計は、ＭＩＮ１
０の段間で長いパケットを転送するための複数のサブサ
イクルに容易に適応できる。さらに、当然のことながら
、クロック・サイクル１５０の立上りがサイクルの始め
として示されているが、クロック・サイクル１５０内の
任意の時点をクロツクの始めに指定できる。

第４Ａ図及び４Ｂ図に、サブスイッチ１００ａをより詳
細に示す。２つのサブスイッチ１　０　０　ａ　Ｎｂは
、先に第２図に関して説明したように各交換機１６ａ−
１内に含まれており、当然のことながら、サブスイッチ
１００ｂの機能はサブスイッチ１００ａのそれと対称的
である。

パケットが線１３ａ（第４Ｂ図）を介してサブスイッチ
１００ａに到辻し、到来パケット・バッファ１１６ａに
記憶される。次いで、前述のように、そのように受け取
ったパケットを受け入れるかどうかの決定が行なわれる
。すなわち、到来パケット・バッファ１１６ａは、パケ
ットの宛先アドレスを、バッファ記憶機構１４ａの待ち
行列内に記憶されたすべてのパケットの宛先アドレスと
比較すべく、バス２６３を介して受入れ検査モジュール
１０８ａに送る。バッファ記憶機構１４ａの待ち行列中
の各パケットは、個々のデータ・レジスタ２５４ａ−Ｎ
内に記憶される。すなわち、バッファ１４ａの待ち行列
は、データ・レジスタ２５４ａ−Ｈに記憶されたパケッ
トを含む。各データ・レジスタ２５４ａ−Ｈの内容は、
同時に個々の比較機構２Ｅｔ４ａ−Ｎ中の新しいパケッ
トと比較される。

各比較機構２６４ａ−Ｈの出力が、ＯＲゲート２６６中
で論理和が取られる。ＯＲゲート２６６の出力が高レベ
ルの場合、到来パケッ１・のアドレスがバッファ記憶機
構１４ａのレジスタ２５４ａ−Ｎ中のパケットの１つと
一致する。次いで、ＯＲゲート２６６の出力が、線２７
２」二のバッファ満杯信号及び線１１８ａ上の有効パケ
ット信号と共にＯＲゲー１−　２　８　８に送られて、
線１１０ａ上に否定応答出力（ＮＡＫＯＵＴ）信号を供
給する。

線２７２上のバッファ満杯信号は、次の読取りアドレス
を次の書込みアドレス＋加算器２３８からの１つのモジ
ューロｎと比較することによって比較機構２４４（第４
Ａ図）から供給され、ＯＲゲート２６８に送られて、バ
ッファ記憶機構１４ａが満杯になったとき別のパケット
がバッファ記憶機構１４ａに入れられないようにする。

このため、その結果が線２７２上に出るバッファ満杯検
査と、その結果がゲート２６６の出力端に出る個別の受
入れ検査が、パケットを受け入れる前に実行できる。す
なわち、線１　１０ａ上のＯＲゲート２６８の出力は、
バッファ記憶機構１４ａに余裕があるかどうか、及び新
しいパケットがバッファ記憶機構１４ａ中のすでにある
パケソトと同じ個別のメモリ装置１８ａ−ｈに向かうも
のであるかどうかの両方に基づいて、そのパケットが受
け入れられるかどうかを示す。

バッファ記憶機構１４ａのデータ・レジスタ２５４ａ−
Ｎは、出力バス２５０及ひ比較機＋ｆｉＹ２６４ａ−Ｈ
に接続されている。データ・レジスタ２５４ａ−Ｎから
のパケットが、ＭＩＮＩＯ内の次の段またはメモリ装置
１８ａ−ｈに送るべく、時に１つずつ、出力バス２５０
に供給される。したがって、待ち行列の１つのデータ・
レジスタ２５４ａ−Ｎが、サブスイッチ１００ａの制御
論理に応じて選択され、選択されたレジスタ２５４ａ−
ＮがＭＩＮＩＯの次の段に送るべくバッファ記憶機構１
４ａから読み出される。転送中のパケットの経路設定ビ
ットは、出力バス２５０から線２７３を介してゲート２
７５ａ１ｂに供給され、線１２０ａと１２０ｂを介して
それぞれ選択機横１０６ａ１ｂに有効パケッｌ・信号を
供給する。このようにして、選択機構１０６ａ，ｂの１
つが選択されて、そのパケットが経路設定される。

ＭＩＮＩＯの各サイクル１５０中に、バッファ記憶機構
１４ａのデータ・レジスタ２５４ａ−Ｎからのパケッ１
・を選択するために、加算器２１８が増分される。加算
器２１８はモジューロｎ加算器である。ただしｎはバッ
ファ記憶機構１４ａ内のデータ・レジスタ２５４ａ−Ｈ
の数である。加算器２１８の出力は読取リアドレス２１
６に入力される。読取りアドレス２１６のアドレス出力
は、ｎ本の読取り許可（ＲＥ）出力線のうちの１本」−
に論理レベルを供給する復号器２４２に入力される。復
号器２４２の読取り許可線は、各データ・レシスタ２５
４ａ−Ｈに個別に接続されている。

すなわち、復号器２５４の読取り許可出力線は、それぞ
れｎ個のデータ・レジスタ２５４ａ−Ｈのうちの１つを
選択して、選択されたデータ・レジスタ２５４ａ−Ｎを
読み取らせ、その内容を出力バス２５０に供給させて、
Ｍ工Ｎ１０の次の段に送らせる。

新しいパケットをバッファ記憶機構１４ａに記憶するた
めに、どのデータ・レジスタ２５４ａ−Ｎが入力バス２
７０からの新しいパケットで書き込まれるかを決定する
こきは、出力バス２５０にどのレジスタ２５４ａ−Ｎが
読み出されるかを決定することよりも複ｉｆＣである。

新しいパケットを受け取ったバッファ記憶機構１４ａ内
のデータ・レジスタ２５４ａ−Ｈのバッファ記憶機’ｔ
Ｒ　１　４　ａ内のアドレスは、書込みアドレス２１４
によって決定される。

書込みアドレス２１４の出力が復号器２２８に入力され
て、線２２８ａ−Ｎｕに対応する書込み許可生成機構２
４８ａ−Ｈに対する信号を生成する。各書込み許可生成
機構２４８ａ−Ｎは、書き込むべきレジスタ２５４ａ−
Ｎを選択するための１対の線２４９ａ−Ｎを備えている
。各書込み許可生成機構２４８ａ−Ｎ内で、復号器２２
８の出力は、１）線１１８ａｌの有効到来パケット信号
、２）線１１２ａ上の否定応答入力（ＮＡＫＩＮ）信号
、及び３）線１１０ａ上の否定応答出力（ＮＡＫＯＵＴ
）信号と結合される。これらの信号は、論理ゲート２２
０、２２２、２２４及び２２６によって結合されて、大
カバス２７０からの到来パケットを選択されたレジスタ
２５４ａ−Ｈにコピーするための許可信号を、生成機構
２４８ａ−Ｎ内で生成する。すなわぢ、有効な到来パケ
ットかあ２つ る場合、それは選択された書込み許可レジスタ２５４ａ
−Ｎに入れられる。

モシューロｎ加算器２１２は、書込みアドレスを、■）
パケットが到来しパケットがバッファ記憶機構１４ａか
ら読み出されるか、あるいはパケットが到来せずパケッ
トがバッファ記憶機構１４ａから出て行かない場合に１
だけ増分され、２）パケットが到来しパケットがバッフ
ァ記憶機構１４ａから出て行かない場合に２だけ増分さ
れ、３）パケットが到来せずパケットがバッファ記憶機
構１４ａから読み出される場合には増分されない。

これらの決定を下すのに必要な信号は、線１１０ａＮ　
　１　１２ａ１　１　１８ａＪ二にあり、その論理動作
は論理ゲート２０２、２０４、２０６、２０８、２１０
によって実行される。

バッファ記憶機構１４ａの待ち行列の先頭にあるパケッ
トが選択機構１０６ａ１ｂまたはＭＩＮ１０の次の段に
よって実行される調停で拒絶された場合、それはバッフ
ァ記憶機構１４ａ待ち行列の後尾の到来パケットの後に
入れられる。このパケットは出力バス２５０上て利用て
き、ｓ　１　１　２ａ上の否定応答信号が高レベルの場
合、それは正しいレジスタ２５４ａ−Ｈにコピーされる
。したがって、サブスイッチ１００ａの論理回路は、出
力パケットが否定応答され到来パケットが到来しない場
合に書込みアドレスで書込み信号を生成する。

そうでない場合、その論理回路は、それを書込みアドレ
ス＋１つのモジューロｎに対応するレジスタにコピーす
る。ただし、ｎはレジスタ２５４ａの数一Ｎである。

第５図に、サブスイッチ１００ａ内の選択機構１０６ａ
を詳細に示す。選択機構１０６ａ１ｂは同じなので、そ
れらのうちの１つだけを詳細に説明する。選択機構１０
６ａは２つの入力をもつ。

第１の入力（ＤＡＴＡ　　ＩＮ　　１）は、データ線１
０４ａを介してバッファ記憶機構１４ａからパケットを
供給し、第２の入力はデータ線１０４ｂを介してバッフ
ァ記憶機構１４ｂからパケットを供給する。前述のよう
に、選択機構１０６ａは、単一のクロック・サイクル中
にデータが両方のデータ線１０４ａ１ｂを介して供給さ
れる場合、調停をしなければならない。

図の調停方式は、データが１回の調停中に一方のデータ
線１０４ａまたは１０４ｂがら選択され、次の調停中に
もう一方のデータ線１０４ａまたは１０４ｂから選択さ
れるという、回転木馬方式である。前述のように、ラン
ダム選択方式など他の方法も使用できる。１クロック・
サイクル中に選択機構１０６ａに２つの入力ではなく１
つしが入力がない場合、その１つの入力がデータ出力線
１５ａに供給され、選択機構１０６ａによる選択または
調停の必要はない。

各パケットの再経路指定ビットは、選択機構ＩＱ６ａま
たは１０６ｂのどちらがパケットを転送するかを決定す
る。この経路指定ビットが線２７３上のバッファ記憶機
構１４ａまたは１４ｂの有効パケット・ビットと（第４
Ａ図のサブスイッチ１００ａのゲート２７５ａと２７５
ｂにおけるように）論理積が取られて、線１　２　０　
ａ１ｂＮ　ｃ及びｄｉに■ＰＳ信号を生成する。したが
って、たとえば、バソファ記憶機構１４ａが選択機構１
０６ａに刻する経路指定ビッ１・をもつ有効パケットを
供給する場合、選択機構１０１３ａの線１２０ａ」一の
選択機構レベル■ＰＳか真となる。同様に、バッファ記
憶機構１４ｂがパケットを選択機構１０６ａに転送する
場合、選択機構１０ｔ３ａの線１２　０　ｃ　ｌのレベ
ルＶＰＳが真となる。同様に、第２図を特に参照すると
、バッファ記憶機構１４ａか選択機構１０ｆ３ｂに対す
る経路指定ビットをもつ脊効パケットを供給する場合、
選択機構１０６１）の線１２０ｂＪ−の選択機構レベル
ｖＰＳが真となる。バッファ記憶機構１４ｂがパケット
を選択機構１０６ｂに転送する場合、選択機構１０６ｂ
の線１２０ｄｌ二のｖＰＳが真となる。

パケットが選択機構１０６ａから線１５ａを介して転送
されるとき、次の段に対する有効パケット信号が、線１
１４ａｌに供給される。線１１４ａのレベルは、ゲート
３０８から供給される。ゲート３０８は、線１２０ａま
たは１２０ｃのどちらが高レベルであったかに応じて、
ゲート３００または３０６から高レベル入力を受け取る
。すなわち、バッファ記憶機構１４ａまたは１４ｂのど
ちらからの有効パケットを示す有効パケット・レベルＶ
ＰＳを線１２０ａまたは１２０ｃのどちらを介して受け
取ろうとも、有効パケット信号ｖＰは、線１１４ａｌで
依然として高レベルにある可能性がある。

前述のように、１本の線１２０ａ１ｃだけが高レベルに
あって、１つのパケットだけが選択機構１０６ａに供給
されることを示す場合、その１つのパケットが線１５ａ
を介して転送される。１つのパケットだけが進んで、ゲ
ート３１０または３１２を開き、必要に応じてバス１０
４ａまたは１０　４　ｂ　」二で受け取ったパケットを
転送するときに、ゲート２９２ならびに、ゲート２９６
、２９８、３００の論理回路、ゲート３０２、３０４、
３ｏ６の論理回路が、存効パケット線１１４ａを高レベ
ルにする。調停を行なわなければならないとき、回転木
馬方式は、ゲー１−　３　０　０または３０６の出力を
交互に伍レベルにして、ゲー１−３１０または３１２を
開くフリップ・フロツプ２９０によって実行される。次
の調停中に、フリソプ・フロツプ２９０の状態が反転さ
れて、反対のデータ・バス１０４ａ１ｂを選択させる。

選択機構１０６ａからバス１５ａを介して転送されたデ
ータが後の段で受け入れられるとき、その後の段は、否
定応答線１１２ａを介して否定応答を選択機横１０（３
ａに供給する。しかし、転送されたパケットは、バッフ
ァ記憶機構１４ａまたは１４ｂのどちらから到来するこ
ともあり、そのバッファ記憶機構がその待ち行列からデ
ータ・パケットを削除し、他のバッファ記憶機構１４ａ
１ｂはその待ち行列から何も削除しないようにするため
、否定応答信号を正しいバッファ記憶機構１４ａ１ｂに
経路設定しなければならない。したがって、２本の否定
応答線１１３ａ，ｂが設けられている。否定応答線１１
３ａは受入れ検査モジュール１０８ａを介してバッファ
記憶機構１４ａに接続され、否定応答線１１３ｂは受入
れ検査モジュール１０８ｂを介してバッファ記憶機構１
４ｂに接続される。

線１１２ａ上の否定応答信号を正しい否定応答線１１３
ａ，ｂにゲー１・するため、ゲート３０８の２つの入力
が、別々のゲート２９４、２９Ｂに供給される。前述の
ように、どちらのバッファ記憶機構１４ａ１ｂがパケッ
１・を転送したかに応じて、ゲー｝　３　０　８１のこ
れらの２つの入力のどちらか一方が高レベルになる。し
たがって、これらの２つの入力は、否定応答線１１２ａ
ｌの信号を、ゲート２９４、２９６を介して否定応答線
１１３ａｚ　ｂの１方にゲートする。

第６図に、１）本発明の方法を使用した場合、及び、２
）本発明の方法を使用せず、バッファ１４ａ−ｘが宛先
が同じ他のパケットをすてに持っている場合でもパケッ
トがバッファ１４ａ−ｘに受け入れられるという、従来
技術を使用した場合の、ＭＩＮＩＯのサイクル遅延とＭ
ＩＮＩＯのスループットの関係を示す。グラフ３５０に
示したデータは、８段に配列された２×２個のサブスイ
ッチをもつ２５６Ｘ２５６ポートのネ・ソトワーク（図
示せず）て収集したものである。水平軸」二の正規化ス
ループットとは、実際のスループ・ノ｝・と、ネットワ
ーク内に衝突のない理想的なスループ・ソトの比率であ
る。ただし、１ボート当り１サイクル当り１パケットが
理想であると仮定する。均一トラフィック及びパケッ１
・の５％が単一のホ・ソ１・・スポットに向かうトラフ
イックについてデータを収集したこのシステムのバッフ
ァの長さは８であった。

ＭＩＮを通過するトラフイックが均一なときの従来技術
のサイクル遅延を、曲線３５８に示す。

その場合、最大正規化スループットは約０．５５である
。曲線３５２は、５％のホ，ソト・スポ，ソトの場合の
従来技術の方法のスループットを示したもので、最大ス
ループットが０．０７である。曲線３５６は、本発明の
方法を用いた場合の均一トラフィックのときの遅延とス
ループ・ソトの関係を示す。波形３５６で示されるよう
に、本発明の方法は、均一トラフィックの場合、従来技
術の方法よりも高スループッ１・での成績がやや悪く、
波形３５８では最高のスループットが０．５５であるの
に対し、約０．５０である。

しかし、１・ラフィックの５％がホット・スポットに向
かうとき、本発明のシステムを使用するＭＩＮの性能は
、曲線３５４を見ればわかるように、曲線３５２に示さ
れた性能と比べて大きな改善を示す。すなわち、本発明
の方法は、曲線３５６、３５８に示すように均一トラフ
ィックではやや性能が低下するものの、曲線３５２、３
５４を比較するとわかるように、非均一トラフィックで
は遅延が大幅に減少し性能が向上する。

本発明の方法は、バッファ１４ａ−ｘの内容が、調停を
実行する際にＭＩＮＩＯの後続段としてどのように使用
されるかに基づいて、あらゆるクラスの交換アルゴリス
ムをもたらす。特定のいくつかの実施例を以下に示す。

曲線３５６、３５８て示されるように、均一トラフィッ
クは、この基本方式により、幾らか悪影響を受ける。こ
の影響は、特にネットワークの後の段で現れる。という
のは、後の段では、パケットが転送されるときに、同じ
宛先に向かうパケットが次のバッファ段に存在する確率
が高くなるからである。そのために、ネッ１・ワーク内
で不必要な阻止が起こる。本発明の方法の他の実施例は
、受信側ハノファ１　４．　ａ　−　ｘのｉ、１』ぢ行
列か最小長よりも大きい場合にのみ、同し宛先を持つパ
ケッ１・があるかとうかを検査するものである。たとえ
ば、待ち行列の長さがパケッｌ−　１つまたは２つより
多い場合にのみ、その宛先が検査される。こうした力式
を選択する理由は、到来パケッ１・と同じ宛先に向かう
パケットが通常の環境で発生する確率がより高い、ＭＩ
Ｎ１０の後の段で、通常はロードが小さくなりバッファ
待ち行列が短くなるためてある。

第１の実施例及ひ代｛各実施例について収集したデータ
からは、Ｍ■Ｎ１０の最後の数段についてのみ代替方法
を実行し、ＭＩＮＩＯの最初の数段では第１の方法を使
用する場合、ホット・スポット・トラフィックの場合の
ネソ１・ワーク性能は基本方式とほぼ同じてあるか、均
一ロードのもとでは良好な性能を保持することがわかる
。

ホッ１・・スポット・トラフィックの場合に基本方式を
使用するネットワークのスループットが、均一ローディ
ングの場合よりも小さくなる理由は、ホット・スポット
・パケットが数サイクルごとに待ち行列の先頭にきて、
しばしばその数サイクルを浪費することである。この問
題を緩和するもう１つの実施例は、パケットに関連する
優先ビットを設けるものである。その場合、あるパケッ
トが次の段のバッファ内にある宛先の同じ別のパケット
によって阻止される場合、そのパケットにより低い優先
順位が割り当てられることがある。

Ｆ．発明の効果 以上のように本発明の多段接続ネットワークにおける交
換方法によれば、ホット・スポット・トラフィックによ
って均一トラフィックのパフォーマンスが低下するのを
防止することができる。

【図面の簡単な説明】

第１図は、本発明で使用する代表的な３段ＭＩＮの概略
図である。 第２図は、第１図のＭＩＮ内の、交換機の１つ及びそれ
に関連するバッファ記憶機構の概略図である。 第３図は、第１図のＭＩＮのあるクロック・サイクルで
発生する事象を示すタイミング図である。 第４図は、第４Ａ図と第４Ｂ図から成り、第２図の交換
機内のサブス１イッチのより詳細な概略図である。 第５図は、第２図の交換機のサブスイッチ内の選択機構
回路の詳細な概略図である。 第６図は、従来技術の方法と本発明の方法の両方を使用
したＭＩＮのスループットとローデイング特性の関係を
示すグラフである。 １０・・・・多段相互接続ネッ１・ワーク（ＭＩＮ）、
１２・・・・プロセッザ、１４・・・・バッファ、１６
・・・・交換機、１８・・・・メモリ装置、１０４・・
・・選択機構、１０８・・・・受入れ検査及びバッファ
制御モジュール。 手続補正書 （方式） ６．補正の対象 平成 １年１０月１３日 （１）委任状（代理権を証明する書面）（２）明細書の
図面の簡単な説明の欄 ］−通

Claims (2)

【特許請求の範囲】
1. （１）少なくとも１つ以上の入力ポート及び出力ポート
   を有し、該入力ポートにはパケットを受け入れるバッフ
   ァが備えられた複数の交換機から構成される多段相互接
   続ネットワークにおける交換方法に関し、 ａ）入力ポートにおけるパケット到着を確認するステッ
   プ ｂ）バッファが満杯であるかを確認するステップ ｃ）パケットの受入れ検査が合格したかを個別に確認す
   るステップ ｄ）ステップａ）で識別されたパケットをバッファが満
   杯でなくかつ個別受入れ検査が合格の場合のみバッファ
   に受け入れるステップ とからなることを特徴とする多段相互接続ネットワーク
   における交換方法。
2. （２）前記受入れ検査において、前記ステップａ）で確
   認されたパケットと同一方向へ向かうパケットを既に前
   記バッファが有していないときに合格であるとする特許
   請求の範囲第１項の多段相互接続ネットワークにおける
   交換方法。