JPH07282018A - パケットの経路指定デッドロック回避方法及び装置 - Google Patents

パケットの経路指定デッドロック回避方法及び装置

Info

Publication number
JPH07282018A
JPH07282018A JP7012797A JP1279795A JPH07282018A JP H07282018 A JPH07282018 A JP H07282018A JP 7012797 A JP7012797 A JP 7012797A JP 1279795 A JP1279795 A JP 1279795A JP H07282018 A JPH07282018 A JP H07282018A
Authority
JP
Japan
Prior art keywords
route
network
packet
node
path
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP7012797A
Other languages
English (en)
Other versions
JP2817770B2 (ja
Inventor
Harish Sethu
ハリシ・セス
Robert F Stucke
ロバート・フレデリック・スタッケ
Craig B Stunkel
クレイグ・ブライアン・スタンケル
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH07282018A publication Critical patent/JPH07282018A/ja
Application granted granted Critical
Publication of JP2817770B2 publication Critical patent/JP2817770B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Multi Processors (AREA)

Abstract

(57)【要約】 【目的】 大規模双方向マルチステージ相互接続クロス
ポイント・スイッチ・ベース・パケット・ネットワーク
におけるデッドロックの無い経路指定を確立する装置及
び方法を提供する。 【構成】 システム内の経路テーブルに含まれる経路の
選択において、システムのある区分、例えばシステムの
半分５０３内のノード間をもっぱら流れるパケット・ト
ラフィックを、他の区分、例えばシステムの別の半分５
０７内のノード間を流れるパケット・トラフィックから
分離するために、特定の経路を禁止するように、ネット
ワーク全体が効果的に区分される。この点に関し、シス
テムの共通区分内のノード間を通過するパケットの経路
を抽出するために、他のシステム区分を通過するパス５
２４、５４４を含む経路が禁止される。複数のシステム
区分、例えばシステムの異なる半分に含まれるノード間
でパケットを伝搬する経路の選択においては、こうした
経路の禁止は発生しない。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はマルチステージ相互接続
クロスポイント・ベースのパケット交換を確立するため
の装置及び方法に関する。特に本発明は、大容量並列処
理システム内で使用される高速パケット・ネットワーク
内に組込むのに適するが、それに限るものではない。
【０００２】
【従来の技術】強力で知能的で比較的安価なマイクロプ
ロセッサの継続的な進歩及び市場での可用性により、大
容量並列処理が、これまで従来式のメインフレーム・コ
ンピュータにより処理されてきた広範なアプリケーショ
ン、例えばトランザクション処理、シミュレーション及
び構造解析などを処理するために、益々魅力的な手段に
成りつつある。
【０００３】大容量並列処理システムでは、しばしば数
百または数千にも上る相当数の比較的単純なマイクロプ
ロセッサを基本とする別々の処理要素が、一般に高速パ
ケット・ネットワークから形成される通信構造を介して
相互接続され、各こうした処理要素がネットワーク上の
別々のポートとして現れる。この構造はパケット形式の
構造経路メッセージを、これらの処理要素の任意の１つ
から他へ経路指定し、それらの間の通信を提供する。こ
れらの各々の処理要素は、通常、別々のマイクロプロセ
ッサ及びその関連支援回路を含み、後者はとりわけ、一
時記憶用のランダム・アクセス・メモリ（ＲＡＭ）及び
永久記憶用の読出し専用メモリ（ＲＯＭ）、及び入出力
回路により代表される。各処理要素は更に通信サブシス
テムを含み、これは適切な通信インタフェース及び他の
ハードウェア、並びにこの要素をパケット・ネットワー
クにインタフェースするように集合的に機能する制御ソ
フトウェアにより形成される。
【０００４】一般に、大容量並列処理システムの全体性
能は、そこで使用される根元的なパケット・ネットワー
クの性能により制限される。その点でパケット・ネット
ワークが余りに遅く、特に全体システム・スループット
に悪影響を及ぼす程度に遅いと、結果的な低下は著し
く、所与のアプリケーションにおいて大容量並列処理シ
ステムを使用する効果が低減する。
【０００５】特に、大容量並列処理システムにおいて、
各処理要素はアプリケーションの予め定められた細分化
部分を実行する。その対応するアプリケーション部分の
実行において、各要素は一般に、例えば異なる要素上で
実行されるアプリケーション部分からデータを要求し、
処理結果データを例えば、更に別の処理要素上で実行さ
れる別のアプリケーション部分に提供する。全ての要素
間における処理の相互依存の性質により、各処理要素
は、その時これらの各々の要素において実行されるアプ
リケーション部分からの要求により、データを別のこう
した要素に転送できなければならない。一般に処理要
素、例えば"宛先"要素が、別のこうした要素、例えば"
出所"要素または"発信元"要素に対してデータを要求す
ると、宛先要素は少なくともこの特定のアプリケーショ
ン部分に関し、その要素が出所要素により伝送される必
要データを含むパケットを受信するまで遊休状態を維持
する。パケットを受信すると、宛先要素は再度このアプ
リケーション部分の処理を開始する。パケット・ネット
ワークを通じて宛先からの要求を含むパケットを出所処
理要素に移送し、次に要求データを含む応答パケットを
反対方向に移送するためには、有限量の時間が必要であ
る。この時間は、宛先要素において実行されるそのアプ
リケーション部分に、ある程度の待ち時間を不可避に挿
入する。システム内のほとんどの処理要素が、出所要素
において実行されるアプリケーション部分に対応する宛
先要素として機能するので、この通信により誘導される
待ち時間が余りに長いと、システム・スループットが顕
著に低下する。結果的に、このことは全体システム性能
を著しく低下させることになる。これを回避するために
パケット・ネットワークは各パケットを任意の２つの通
信処理要素間で、この待ち時間を低減するように、可能
な限り速く移送しなければならない。更に、典型的な大
容量並列処理システムにおいて一般に使用される相当数
の処理要素、及びこのシステム内の任意のある要素が、
任意の時刻において、他のこうした要素と通信するため
に必要な付随のニーズを考慮すると、ネットワークは相
当に大きな数、例えば予測されるピーク負荷のパケット
を処理要素間で同時に経路指定できなければならない。
【０００６】しかしながら、実際には、大容量並列処理
システムで使用される必要性能、特に伝送帯域幅を所有
するパケット交換ネットワークは、様々な理由から、そ
の開発が極めて困難であることがわかっており、そのた
めにこうしたシステムの急速な普及及び使用の増加があ
る程度阻止されてきた。
【０００７】パケット・ネットワークの様々な形態が今
日存在するが、１つの共通のアーキテクチャとしては、
比較的小さなクロスポイント・スイッチのマルチステー
ジ相互接続構成を使用する。各スイッチは、通常、８ポ
ート双方向ルータであり、全てのポートがクロスポイン
ト・マトリックスを通じて内部的に相互接続される。こ
うしたネットワークでは、１ステージ内の各スイッチは
ネットワークの片側（すなわち、いわゆる"入力"）にお
いて開始し、特定の対応するパス（典型的にはバイト幅
物理接続）を通じて、次の続くステージ内のスイッチに
相互接続され、このようにして、ネットワークの反対側
（すなわち、いわゆる"出力"）の最後のステージに到達
するまで継続される。こうしたスイッチは、今日、動作
的には非ブロッキング（non-blocking）の比較的安価な
単一の集積回路（以降では"スイッチ・チップ"として参
照される）として調達可能であるので、これらのスイッ
チ・チップが好まれて使用される。実際に、中央キュー
の使用に頼る非ブロッキング８ウェイ・ルータとして実
現されるこうしたスイッチ・チップが、P．Hochschild
らによる係属中の米国特許出願第０２７９０６号"A Cen
tral Shared QueueBased Time Multiplexed Packet Swi
tch with Deadlock Avoidance"（１９９３年３月４日出
願）に述べられている（本願の出願人に権利譲渡され
る）。
【０００８】こうした双方向マルチステージ・パケット
交換ネットワークは、他のパケット交換ネットワーク・
トポロジと比較して比較的単純であり、その全てのポー
ト間で高い伝送帯域幅を提供するが、残念ながらこのタ
イプのネットワークは、経路指定デッドロックを受け易
い。これらのデッドロックは稀にしか発生しないが、同
一ステージ内の任意の２つのスイッチ間に複数の経路が
存在するために、実際に発生する。
【０００９】この点に関し、８個のこうしたスイッチ・
チップが２つの相互接続ステージに編成される単純な３
２ポート・ネットワークについて考えてみよう。すなわ
ち、４個のスイッチによる入力ステージの後に、４個の
スイッチによる出力ステージが続き、これらの全てのス
イッチ・チップが単一のスイッチ・ボード上に含まれ
る。この構成では、入力ステージにおいて、異なるスイ
ッチ・チップ上の任意の２つのポート間を通過するパケ
ットは、出所（"入力"）ポートを含む入力ステージ内の
スイッチ・チップを通過して、出力ステージの４個のス
イッチ・チップの１個に経路指定される。次に、この後
者のスイッチ・チップが、パケットをこのパケットの宛
先（"出力"）ポートを含む入力ステージ内のスイッチに
逆経路指定する（すなわち、その方向を反転する）。ス
イッチ・チップ間の経路は、通常、比較的短い時間に渡
り、各バイト・ワイズ（byte-wise）・パスがほぼ等し
い数のパケットを伝搬し、ネットワーク全体を通じての
トラフィック・フローを平均化するように、システム初
期化の間に予め定義される。これらの経路が設定される
と、スイッチ・チップまたはパス故障或いは保守状態以
外では経路は稀にしか変更されない。各処理要素が使用
可能な割当てられた経路が、次に再度システム初期化の
間に（局所）経路テーブルの形式でその要素に提供され
る。引続きルーチンのオペレーションの間に、各処理要
素がパケットを形成すると、その要素はこのパケットの
宛先にもとづきその経路テーブルから経路を読出し、単
にその経路をパケットのヘッダ内に適切な経路バイトの
値として挿入する。パケットが次にネットワーク内に送
出され、パケット内の対応する経路バイトの値により指
定される継続するスイッチ・チップ（及び交換ステー
ジ）を経由して、経路指定される。パケットが交換ステ
ージを経由して横断すると（すなわち、ここでは同一ス
テージの２個のスイッチ・チップを通過する）、ステー
ジ内の最後のスイッチ・チップがパケット・ヘッダから
対応する経路バイトを切捨てる。
【００１０】経路は従来、経路指定デッドロックの潜在
性を考慮すること無く定義されてきた。従って、各々が
例えば異なるスイッチ・チップのグループの中央キュー
内に存在する対応するパケットが、連続ステージ内のス
イッチ・チップ対を接続する共通パス上を同時に経路指
定されるのを待機する度に、経路指定デッドロックが発
生する。こうした状態が発生すると、これらの各々のス
イッチ・チップは、グループ内の他のスイッチ・チップ
がそれらのパケットをこれらの特定のパス上に経路指定
するのを待機する。このグループのどのパケットも、こ
のグループの任意の１つのパケットが経路指定されるま
で、その関連する中央キューを通過することができない
ので、これら全てのパケットがひたすら待機し、対応す
るパスがデッドロック状態となり、その上をトラフィッ
ク・フローが生じなくなる。その結果、デッドロックが
発生すると、これらのパケットが宛先指定される処理要
素についても、これらのパケットを待機し続けることに
なり、それらの処理のスループットを停止させる。結果
的にネットワークの帯域幅はデッドロックにより影響さ
れない残りの処理要素だけを優遇するようになり、処理
の作業負荷が著しく偏り、システム・スループットを多
大に低下させることになる。
【００１１】デッドロックを回避する問題に直面して、
当業者は最初に経路指定デッドロックを予測するため
に、特定のタイプの大域アービトレーション手法が使用
可能であると考え、多数の非デッドロック状態のパスの
いずれかを選択し、その上でパケットを伝送し、デッド
ロックを回避することを期待するであろう。この手法
は、潜在的な経路指定デッドロックを検出し、それに従
い調停するために全ての中央キューを通過する全てのパ
ケットがモニタされることを必要とする。残念ながら、
これらの機能を達成する回路は極めて複雑であり、全て
の各スイッチ回路の外部に配置されて、それらの各々と
接続される必要がある。これはパケット交換ネットワー
クのサイズ、複雑度、従ってコストを押し上げることに
なる。この手法自体は、極めて非現実的である。
【００１２】こうしたことを考慮して、当業者は２重の
スイッチ・ボードを有するパケット・ネットワークを形
成するなどの別の手法に注目するであろう。この手法を
３２プロセッサ・システムと共に使用することにより、
１つのスイッチ・ボードのポート１６乃至３１で表され
る１６個のポートが、別のスイッチ・ボードの同じポー
トに接続される。両方のボード上の残りの各ポート０乃
至１５は、３２個の別々の処理要素の対応する１つに接
続される。オペレーションにおいて、共通のスイッチ・
ボードに接続される出所ポートと宛先ポートとの間を通
過するパケットが、もっぱらその１つのスイッチ・ボー
ド内に経路指定され、他のスイッチ・ボード内に含まれ
るスイッチ・チップに影響を及ぼすことはない。異なる
スイッチ・ボード上の出所ポートと宛先ポートとの間を
経路指定されるパケットだけがボード間を経路指定され
る。片方のスイッチ・ボード内だけを流れるパケットを
他のスイッチ・ボード内だけを同時に流れるパケットと
潜在的に相互作用しないように分離することにより、こ
の手法はデッドロックを排除する。更にこの手法は伝送
帯域幅を悪化させない。残念なことにこの手法は２重の
スイッチ・ボード及び関連回路を必要とすることにより
高価である。それにも関わらず、スイッチ・ボード及び
関連回路を２重化する追加のコストが３２プロセッサ・
システムにおいては許容可能である。この手法自体が、
３２プロセッサ・システムにおけるデッドロックを回避
するために使用される。実際に３２プロセッサ・システ
ムでは、１つのスイッチ・ボードだけではパケット・ネ
ットワークの形成を妨げる十分なデッドロックの潜在性
が存在する。しかしながら、このコスト的な欠点は、例
えば５１２プロセッサ・システムなどのように、ネット
ワーク内で必要とされる最小１６個のスイッチボードに
加え、追加の１６個のスイッチ・ボードを必要とする大
規模システムの場合に、高額でより付けないに過ぎな
い。
【００１３】最後に、当業者は、特定の経路の使用を単
に禁止することにより、経路指定デッドロックを回避す
る手法を考慮するであろう。この特定の手法により、同
一ステージ内の２個のスイッチ・チップ間の全ての経路
の特定のサブセットだけが、それらの間のパケット・ト
ラフィックの伝搬に使用可能と定義され、経路テーブル
内に含まれる。１度選択されると、これらの経路は保守
状態または故障状態以外では変化しない。サブセットを
形成する経路は、特に経路指定デッドロックが発生しな
いように選択される。各追加の経路が禁止されるとネッ
トワーク帯域幅が低下するので、この手法の目標はでき
る限り少ない経路を禁止することである。
【００１４】しかし残念ながら、経路が禁止されると"
禁止されない"経路がシステム内の全てのノードに関し
て、対称でないことが知られている。その結果、伝送帯
域幅がネットワーク全体に渡り均等に低減されず、ネッ
トワーク全体に渡って帯域幅の非対称が生じる。これら
の非対称の結果、ネットワークは伝送帯域幅が特定の"
ホット"・ポートにおいて非常に高くなる傾向にあり、
他では実質的に０となる、いわゆる"ホット・スポット"
を発展させる傾向を示す。これは次に、他のポートを犠
牲にして"ホット"・ポートに関連する処理要素を優遇す
るように処理スループットを偏らせ、ネットワーク全体
に渡る作業負荷処理の平衡を失わせる。結果的にシステ
ム性能の低下が生じる。実際に、経路がもっぱらスイッ
チ・ボード内で禁止されると、ネットワーク全体に渡り
一定の帯域幅の低下をもたらす残りの禁止されない経路
の任意の組合わせを見い出すことができないことが判明
した。
【００１５】経路を禁止する手法は、単に各処理要素に
対応する経路テーブル内に含むための特定のエントリの
選択を要求するだけなので、この手法は、具体化が非常
に単純で高度にコスト有効である。従ってこの手法は、
ネットワーク全体に渡り対称的な帯域幅の低下を生成不
能でない限り、マルチステージ・クロスポイント・パケ
ット・ネットワークに取り入れられることが望まれる。
【００１６】相互接続双方向マルチステージ・クロスポ
イント・ベースのネットワークを、大容量並列処理シス
テムの通信中枢として使用する関心にも関わらず、これ
らのネットワークにおけるデッドロックの潜在性の増
加、並びに特に大規模ネットワークにおける現実的なソ
ルーションの欠如が少なくとも今日まで、３２をはるか
に越えるプロセッサを有するこうしたネットワークを使
用する大容量並列処理システムの市場での使用可能性を
抑制してきており、特定の大規模処理アプリケーション
におけるこれらのシステムの使用を妨げてきた。
【００１７】従って、大規模双方向マルチステージ相互
接続クロスポイント交換ネットワークにおいて、特に、
大規模大容量並列処理システムにおいて、デッドロック
の発生を防止する現実的な手法が必要とされる。こうし
た手法は具体化が単純であり、高度にコスト有効である
べきであり、ネットワーク帯域幅が結果的に低減される
場合、ネットワーク全体に渡り、実質的に対称で受諾可
能なレベルの帯域幅の低減を提供するべきである。こう
した手法がこうしたシステム内に含まれると、これらの
システムは市販されると３２をはるかに上回る、例えば
５１２或いはそれ以上の別々のプロセッサに拡張され
る。従って、こうしたシステムは従来不可能であった追
加のアプリケーション処理のニーズに応えることができ
る。
【００１８】
【発明が解決しようとする課題】本発明により、大規模
双方向マルチステージ相互接続クロスポイント・スイッ
チ・ベース・パケット・ネットワークにおいて、経路指
定デッドロックの発生を防止するための、従来技術に固
有の欠点を有利に克服する単純でコスト有効な手法が提
供される。この手法は、理想的には大規模大容量並列処
理システムの通信中枢を形成するこうしたパケット・ネ
ットワークにおいて使用される。
【００１９】
【課題を解決するための手段】特に本発明により、特定
の予め定義された経路が経路テーブルの形成の間に、こ
れらのノードを使用するネットワーク内における特定の
ノード、例えば処理要素の相対ロケーションにもとづき
考慮から除外される。禁止された経路は、もしそれらが
使用されなければ、閉ループ経路指定パターン、従って
経路指定デッドロックの発生を防止する経路として選択
される。経路テーブルに含まれる経路の選択においてシ
ステムのある区分、例えばシステムの半分内のノード間
をもっぱら流れるパケット・トラフィックを別の区分、
例えばシステムの他の半分内のノード間を流れるパケッ
ト・トラフィックから分離するために経路が禁止され
る。この点に関し、システムの共通区分内のノード間を
通過するパケットの経路を抽出するために、システムの
別の区分を通過するパス（ケーブルなど）を含む経路が
禁止される。複数のシステム区分、例えばシステムの異
なる半分に含まれるノード間でパケットを伝搬する経路
の選択においては、こうした経路の禁止は発生しない。
【００２０】例えば、８×８のスイッチ回路（ここで
は"スイッチ・チップ"としても参照される）の使用にお
いて、多数の同一の３２０ポート・スイッチ・ボードを
有する５１２プロセッサ・システムが構成され、これら
が２つの相互接続ステージ、すなわち、個々の処理要素
に接続されるノード・スイッチ・ボード（ＮＳＢ）及び
ノード・スイッチ・ボード自身を相互接続するために使
用される中間スイッチ・ボード（ＩＳＢ）に編成され
る。各ＮＳＢは１６個のそれぞれ異なる処理要素に接続
される１６ポートと、１６個の各ＩＳＢ上の異なるポー
トに相互接続される別の１６ポートを提供する。
【００２１】このシステムにおいて禁止される経路を決
定するために、１６個の連続的なＮＳＢ（例えばＮＳＢ
０乃至１５、及び１６乃至３１）及び２５６個の連続的
な処理要素が各半分を構成するように、システムが半分
に分割されて効果的に考慮される。第１の８個のＩＳＢ
が一方の半分に含まれ、残りの８個のＩＳＢが他の半分
に含まれる。システムの共通の半分内に配置される処理
要素間を通過するパケットに対して、システムのその半
分内に完全に含まれるＩＳＢポートを含む使用可能経路
だけが許可され他の経路は禁止される。従って、システ
ム初期化の間に、後者の任意の経路は、これらの処理要
素を接続する大域経路テーブル内に含まれない。或いは
システムの異なる半分内に配置される処理ノード間を通
過するパケットに対しては、こうした経路は禁止されな
い。従ってこの場合には、大域経路テーブル内に結果的
に含まれる経路の選択は、システムの半分にもとづく制
限無しに、使用可能な全ての経路の中から実施される。
【００２２】システムの各区分例えば半分を、他の任意
の区分例えば他の半分内に含まれる処理要素対間をもっ
ぱら流れるパケット・トラフィックから分離することに
より、これらのパケットの相互作用により生じる経路指
定デッドロックが有利に防止される。これにより市販の
並列処理システムは、より多くの処理要素を含むように
容易に拡張され、従来可能であった以上に広範な様々な
アプリケーション処理ニーズに応えることができる。
【００２３】
【実施例】当業者には容易に理解されるように、双方向
マルチステージ相互接続クロスポイント・ベース・パケ
ット・スイッチを含むパケット・ネットワークは、それ
らの特定のアプリケーションに関係無く、ここで指摘さ
れるタイプの経路指定デッドロックの影響を受け易い。
従って次の説明を考慮した後に、当業者においては、本
発明の教示がほとんどのこうしたパケット・ネットワー
クに容易且つ高度にコスト有効に組込まれ、これらのデ
ッドロックの発生を伝送帯域幅の僅かな低減により、防
止することが理解されよう。従って、本発明は実質的に
任意のサイズのパケット・ネットワークにおいて即刻使
用され、公衆または専用電話回線（例えば局所、広域ま
たは首都圏ネットワーク）または他の類似のネットワー
クなどのデジタル通信、或いは大容量並列処理システム
の通信中枢などの特殊アプリケーションに関わり無く、
広範且つ様々な範囲のパケット交換環境に渡って使用さ
れる。しかしながら、後述の説明を単純化するために、
本発明は大容量並列処理システム、そして特に、ＩＢＭ
により今日製造されるスケーラブル並列処理システムの
ＳＰファミリにおいて使用されるIBM9076 SP-1高性能通
信ネットワークにおいて使用されるように述べられる。
【００２４】本発明の理解を容易にするために、最初に
並列処理システムのパケット経路指定の様々な態様、特
に、そこで使用される双方向クロスポイント方式パケッ
ト・ネットワークに関する態様について述べ、次に典型
的な経路指定デッドロック状況について、そして最後
に、これらのデッドロックの発生を有利に防止する本発
明について詳細に述べることにする。
【００２５】最初に、図１に示される従来の３２プロセ
ッサ並列処理システム５について考えてみる。このシス
テムは３２個のノード・パケット・スイッチ１００（こ
こでは"パケット・ネットワーク"または単に"ネットワ
ーク"としても参照される）を含み、各ノードには３２
個の別々の（しかしながら一般には同一の）処理要素１
１０（特に処理要素１１０0、１１０1、．．．、１１０
31）が接続される。各要素はシステムの処理ノードを形
成する。ネットワークはこれらの処理ノードの１つから
他のノードへの高速伝送を提供する。処理要素自身はそ
れぞれマイクロプロセッサを基本とし、通常、ＩＢＭに
より製造されるRS6000 RISCマイクロプロセッサを使用
する。本発明は任意のこれらの要素のアーキテクチャま
たは回路には無関係であるので、当業者には容易に明ら
かとなろうこれらの態様については詳細には述べない。
しかしながら、本発明は後に詳述されるように、これら
の処理要素の１つにおいて実行されるシステム初期化ソ
フトウェア、及びこれらの各々の要素内に記憶される経
路テーブル内において実現される。従って、これらの特
定の態様については、特に後述される。
【００２６】図示のように、ネットワーク１００は８個
の別々の８×８双方向スイッチ回路１２０により構成さ
れ、これらは２つの相互接続ステージ、すなわち４個の
スイッチ回路１２０0、１２０1、１２０2及び１２０3を
含む"入力"ステージと、４個のスイッチ回路１２０4、
１２０5、１２０6及び１２０7を含む"出力"ステージと
に編成される。"入力"及び"出力"の指定は、純粋に説明
の都合において任意であり、実際には、ネットワーク上
のステージまたはポートは入力または出力ステージ或い
はポートとして機能する。これらの各々のスイッチ回路
は、好適には、中央キュー・ベースの非ブロッキング８
ウェイ・ルータである。各スイッチ回路は単一の集積回
路として、すなわち、いわゆる"チップ"として集積化さ
れ、ここでは各こうしたスイッチ回路自身を"スイッチ
・チップ"として参照する。もちろん当業者には理解さ
れるように、各スイッチ回路は単一のチップとしてだけ
具体化される必要はない。いずれの場合にも、スイッチ
・チップ自身は本発明の１部を形成しないので、これに
ついては詳細には述べないことにして、この回路のその
他の詳細に関して述べることとする。図示のように、各
スイッチ・チップは中央キューを含み、これらは対応す
るスイッチ回路１２０0、１２０1、１２０2、．．．、
１２０7内のキュー１３０0、１３０1、１３
０2、．．．、１３０7として表される。基本的に各中央
キューの目的は、とりわけ入力阻止及びデッドロックを
改良するために、対応するスイッチ回路を通過する別の
経路を提供することであり、後者すなわちデッドロック
は、入力ポート（特に内部のＦＩＦＯバッファ）及び逆
のトラフィックにより充填されたキューに起因する（こ
れは本発明が対象とするのとは異なる形態のデッドロッ
クである）。
【００２７】ネットワークの入力及び出力ステージは、
接続マトリックス１４０を介して相互接続され、これら
の各々の接続は実質的にバイト幅物理リンク（ケーブ
ル）であり、特にそれらの内のリンク１４０0、１４
０1、１４０2及び１４０3が番号付けされて示される。
このマトリックスを介して、入力ステージ内のそれぞれ
のスイッチ・チップのポートが別々にまた物理的に出力
ステージ内のあらゆるスイッチ・チップの対応するポー
トに接続される。例えば、スイッチ・チップ１２０0は
ポート０乃至７を備え、そのポート４乃至７を通じ、対
応するケーブルを介して、各スイッチ・チップ１２
０4、１２０5、１２０6及び１２０7上のポート４に接続
される。８個のスイッチ・チップ及び接続マトリックス
１４０を含むパケット・スイッチ１００は、集合的に単
一のスイッチ・ボードを含む。各スイッチ・チップのポ
ート０乃至３はスイッチ・ボード外のリンクに接続さ
れ、各スイッチ・チップのポート４乃至７は、接続マト
リックス１４０内のリンク（ケーブル）に接続され、そ
れを介して同一ボード内の別のスイッチ・チップのポー
トに接続される。
【００２８】ある要素が別の要素からデータを要求した
り、データを供給したりするなど処理要素が互いに通信
するために、"出所"処理要素は自身が実行するアプリケ
ーション部分にもとづき、命令またはデータと共に適切
なメッセージを含むパケットを形成し、そのパケット
を"宛先"処理要素に伝送するためにパケット・スイッチ
１００に送信する。宛先要素はパケット内に含まれるデ
ータまたは命令を処理し、適切な応答を生成する。応答
は次に、宛先処理要素において実行されるアプリケーシ
ョン部分にもとづき、別のパケットに形成され、例えば
出所または異なる処理要素に伝送して処理するためにネ
ットワークに返送される。
【００２９】ネットワークを介するパケット伝送を容易
にするために、各パケットは経路バイト形式の特定の経
路指定命令を有するヘッダを含む。後述のように、全て
の経路が予め定義される。出所処理要素がアセンブル中
の任意のパケットの宛先を決定すると、その要素は単
に、宛先処理要素をアドレスとして有するその内部（局
所）経路テーブルをアクセスし、適切な経路バイト値の
形式で経路を読出す。この値が単に経路バイトとしてパ
ケットのヘッダに挿入される。
【００３０】図２はパケット・ネットワークを通じて伝
送される典型的なパケット、すなわちパケット２００の
構成を示す。個々のパケットは例えば２５５バイト長で
ある。図示のように、パケット２００は連続するフィー
ルド、すなわち長さフィールド２１０、経路フィールド
２２０（それ自身経路バイト２２０1、２２
０2、．．．、２２０nを含む）、シーケンス番号フィー
ルド２３０及びデータ・フィールド２４０を含む。長さ
フィールド２１０は、パケット長をバイトで指定する８
ビット・ボリュームを含む。経路フィールド２２０は複
数のバイト、特に経路バイト２２０1、２２
０2、．．．、２２０nを含み、これらは集合的にパケッ
トがネットワーク全体を通じてその出所ノードから宛先
ノードに至る特定の単一の経路（パス）を指定する。フ
ィールド２３０は出所処理要素により提供されるシーケ
ンス番号を保持する。この番号は、このパケットに対応
して出所処理要素により割当てられ、宛先処理要素によ
り使用され、所与のシーケンスにおけるパケットの順番
を識別する。この番号自体は、宛先におけるシーケンス
外のパケットの処理の防止のためのチェックに使用され
る。データ・フィールド２４０は連続するバイトを含
み、これらは集合的にパケットにより宛先処理ノードに
伝搬されるデータ（実際のデータまたは命令を含む）を
形成する。フィールド２１０、２２０及び２３０は集合
的にパケット・ヘッダを形成する。
【００３１】経路指定フィールド２２０に現れる経路バ
イトの数（ｎ）は、パケットが通過する交換ステージの
数により決定される。その点に関し、各経路バイトは２
つの連続スイッチ・チップに対応する経路指定命令を保
持する。従って、パケットが宛先処理ノードに達するま
でに、図１に示されるように、ネットワーク内の２つの
連続ステージ内の２個のスイッチ・チップを通過するだ
けであれば、フィールド２２０は経路バイト２２０1だ
けを含むことになる。レイヤ・ネットワーク（layer ne
twork）においては、追加の対のスイッチ・チップが使
用される。全ての経路バイトが同一の形式を有する。こ
の点に関し、経路バイト（Ｒ［７：０］）は１ビットの
フィールド選択子（Ｒ［７］、図示せず）、及び２つの
３ビットの経路フィールド（Ｒ［６：４］及びＲ［２：
０］、両者共に図示せず）を含む。ビットＲ［７］の値
が０の場合、スイッチ・チップはパケットを２進値Ｒ
［６：４］により指定されるそのチップ上の出力ポート
に経路指定し、次にビットＲ［７］の値を１に設定す
る。或いはビットＲ［７］の値が１の場合、スイッチ・
チップはパケットをビットＲ［２：０］で指定されるそ
のチップ上の出力ポートに経路指定し、その間に、この
完全な経路バイトを廃棄する。このようにして、パケッ
トから経路バイトを解析する。従って、各経路バイトは
２つの連続スイッチ・チップに対する経路指定命令を提
供する。ｎ個の経路バイトを経路フィールド２２０内に
連結することにより、各パケットはスイッチ・チップの
最大２ｎのステージを通じて経路指定される。
【００３２】要約すると、パケットを受信するスイッチ
・チップは、そのパケット内にその時、存在する第１の
経路バイトを調査し、そのパケットをそのバイトにより
示されるポートに経路指定する。そうする間に、そのパ
ケットのパス内のあらゆる別のスイッチ・チップは、そ
の完全な経路バイトをパケットから切り取る（除去す
る）。これは次に、経路フィールド２２０内の次に続く
経路バイトを、次のスイッチ・チップ及び交換ステージ
に対応する第１の経路バイトとして形成する。宛先処理
ノードに到来する時、パケットは経路バイトを含んでい
ない。各スイッチ・チップはその時パケットにより伝搬
される第１バイト以後の追加の経路バイトを意識せず、
第１バイトに対してその回路は、その特定の経路指定を
実行する。更に各スイッチ・チップは第１バイト以外の
経路バイトと、続くデータ・バイトとを区別しない。
【００３３】上述のように、経路指定はパケット・アセ
ンブリの間に最初に予め定義された経路バイトをパケッ
ト・ヘッダに挿入し、次にそのパケットの実際の経路指
定が導かれ指令されることにより、出所処理要素及び宛
先処理要素に関係なく、これらの各々のバイトの特定の
値によりネットワーク内において達成される。
【００３４】図３は、図１に示されるシステム５を構成
する処理ノード１１０を示し、特に、これらのノードの
メモリ内に存在してパケット経路指定を実行する様々な
ファイル及びテーブルを示す。パケット・スイッチ（ネ
ットワーク）１００は時分割の２つのモードで機能す
る。それらの一方は実行フェーズであり、この間、スイ
ッチ回路は単に入来パケットを経路指定する。他はサー
ビス・フェーズであり、この間、プロセッサは初期化さ
れるか、ネットワークが回線交換方式でモニタ及び管理
される。ネットワークに接続される全てのスイッチが、
モード間で同期化ロック・ステップ方式で転送する。実
行フェーズの間、特定の処理要素は特定のタスクを任せ
られる。例えば、処理要素１１０0及び１１０1は、シス
テム５から他のネットワークへの、または処理システム
へのリンクを提供し、それらの間で情報を転送するため
の入出力ノードとして指定される。他の処理要素、例え
ば処理要素１１０2、１１０3、．．．、１１０31は、全
て実際のアプリケーション処理のための計算ノードとし
て使用される。処理要素の１つ、例えば処理要素１１０
31は、サービス・フェーズの間の様々なネットワークオ
ペレーションを引受けるサービス・プロセッサとして使
用される。必要に応じて実行フェーズの間、サービス・
プロセッサは計算ノードとしても機能することができ
る。サービス・プロセッサはハードウェア的見地から
は、他の全ての処理要素と同一であるが、サービス・プ
ロセッサはそのメモリ（ここではメモリ３４０）内に、
サービス・フェーズの間に実行される追加のソフトウェ
ア、とりわけ初期化ルーチン３７０を含み、これを実行
する。例えばこのフェーズは全てのスイッチ回路及びネ
ットワークに接続される全ての他の装置（全ての他の処
理要素を含む）に対して、初期化、通信リンク同期、大
域時間同期、故障判断、及び分離、及び様々な診断サー
ビスを提供する。初期化機能はサービス・フェーズの１
部に過ぎないのでサービス・フェーズのこの部分、特に
パケット経路指定及び本発明に関連する観点についての
み、以降で述べることにする。初期化フェーズは、シス
テムが任意のアプリケーション処理を請け負う以前に、
請け負わされる。
【００３５】サービス・プロセッサ１１０31はそのメモ
リ３４０内に、ネットワークに接続される全ての処理要
素を含むそれぞれの及びあらゆる装置、及びこれらの装
置をリンクするためにネットワーク内において使用され
る特定の双方向物理接続（ケーブル）を集合的に定義す
る構造化エントリのデータベース、特にトポロジ・ファ
イル３５０を記憶する。データベースが生成される方法
は本発明には関連しないので、ここでは触れないことに
する。トポロジ・ファイルにおいて、スイッチ回路及び
他の装置の最大数が装置エントリにより最初に識別さ
れ、任意のこれらの回路及び装置間に存在する各物理接
続のエントリがそれに続く。装置エントリは２つの数値
フィールドを含み、これらは"装置番号（ｎv）；スイッ
チ回路番号（ｎs）"の形式を取る。これらの値が提供さ
れると装置識別（ｉｄ）の番号付けが０乃至ｎvの範囲
において、またスイッチ回路ｉｄの番号付けが０乃至ｎ
sの範囲において仮定される。最大１６個の装置及び８
個のスイッチ回路を含むネットワークでは、装置エント
リは単に"16 8"である。各接続エントリは６つのフィー
ルドを有し、これは"装置１タイプ；装置１ｉｄ；装置
１ポート；装置２タイプ；装置２ｉｄ；装置２ポート"
の形式を取る。装置タイプ情報は装置の性質、すなわち
その装置が処理要素かどうかを指定し、そうであれば、
その要素がサービス・プロセッサかどうか、或いはスイ
ッチ回路かどうかを指定する。接続エントリの例は"tb0
14 0 s 3 6"であり、これは"ｉｄ１４の処理要素が全
２重方式で、そのポート０からスイッチ回路３の入出力
両ポート６に接続される"ことを意味する。ネットワー
クの配線は、通常、極めて規則的であり、良好に定義さ
れ対称的である。しかしながら、実際には幾つかのスイ
ッチ・ボードは、保守状態或いは故障状態の結果とし
て、故意に分離される他のネットワーク・コンポーネン
ト、例えばケーブル、スイッチ回路（特に使用されるス
イッチ・チップ）または処理要素のために、パワー・ダ
ウン状態の可能性がある。従って、任意の瞬間における
ネットワーク・トポロジは極めて不規則であったりす
る。
【００３６】いずれにしても、初期化及び特に初期化ル
ーチン３７０の実行の間、サービス・プロセッサ１１０
31はその時存在するトポロジ・ファイル３５０を読出
し、次にテスト・メッセージを同報し、それに対応する
応答を受信することにより、ネットワークに接続される
各装置と同様、ネットワーク内の各接続の状態を物理的
に判断する。これらの応答にもとづき、サービス・プロ
セッサは、例えば既知のブレッドス・ファースト探索
（breadth-first search）により、ネットワークの各
（出所）ノードをネットワークのあらゆる他の（宛先）
ノードに接続するための全ての使用可能な経路を判断す
る。双方向マルチステージ・クロスポイントネットワー
クに固有のパス冗長性により、異なるスイッチ・ステー
ジ内の異なるスイッチ回路を通過して、１対の出所ノー
ド及び宛先ノードを接続する複数の経路がしばしば存在
する。各共通の出所／宛先ノード対間の複数の経路を鑑
み、サービス・プロセッサは次にこれらの各々のノード
対に対応するこれらの経路の１つを選択し、その経路を
メモリ３４０内の大域経路テーブル３６０に記憶する。
これらの経路はネットワーク内におけるトラフィック渋
滞及びホット・スポットを回避するために単位時間に渡
り、ネットワーク全体を通じてパケット・トラフィック
の実質的に一様な分布を達成するように、主に最短パス
にもとづき選択される。
【００３７】ネットワーク１００の使用可能な各出所／
宛先ノード対間のパスを定義する大域経路テーブル３６
０が完全に構成されると、サービス・プロセッサ１１０
31は次にネットワークを通じ、そのテーブルの対応部分
を自身を含む各個々の処理要素に局所経路テーブルとし
て、そこに記憶するために提供する。この部分は、その
特定の処理要素を出所ノードとしてリストする経路だけ
を含む。従って、例えば処理要素１１０0はそのメモリ
３１０内に、局所経路テーブル３２０を記憶し、サービ
ス・プロセッサ１１０31はそのメモリ３４０内に、局所
経路テーブル３８０を記憶する。他の処理要素について
も同様である。パケット形成の間、上述のように、各処
理要素は単にその局所経路テーブルをアクセスするだけ
で、その時アセンブルされるパケットの宛先にもとづ
き、その宛先の経路指定バイトの値をテーブルからその
パケットのヘッダにコピーする。
【００３８】上述の説明を考慮して、経路指定デッドロ
ックを表す図１を再度参照することにする。
【００３９】経路指定デッドロックは、各々が例えばス
イッチ・チップの異なる交換ステージ内の中央キューに
存在する対応パケットが、連続するステージ内のスイッ
チ・チップ対を接続する共通パス上における経路指定を
同時に待機する度に発生する。従って、ここで"Ａ"と記
されるパケットがスイッチ・チップ１２０0の中央キュ
ー１３０0に内在し、処理ノード１１０0から"丸Ａ"で示
される破線のパスを介して、処理ノード１１０4に経路
指定されるのを待機しているものと仮定する。このパス
を通じ、パケット"Ａ"はスイッチ・チップ１２０0によ
り、ケーブル１４０0を介してスイッチ・チップ１２０4
のポート４に導かれ、次にこの後者のチップのポート５
及びケーブル１４０1を介して、入力ステージ特に処理
ノード１１０4に接続されるスイッチ・チップ１２０1の
ポート０に経路指定されて戻される。同様にキュー１３
０0に内在するパケット"Ａ"と同時に、スイッチ・チッ
プ１２０4、１２０1及び１２０5のそれぞれの中央キュ
ー１３０4、１３０1及び１３０5に、３つの他のパケッ
ト"Ｂ"、"Ｃ"及び"Ｄ"が内在するものと仮定する。パケ
ット"Ｂ"はスイッチ・チップ１２０4のノード１に接続
される処理要素１１０17から、"丸Ｂ"で示される破線の
パスを介して、スイッチ・チップ１２０5のノード３に
接続される処理要素１１０21に経路指定される。同様に
パケット"Ｃ"は、スイッチ・チップ１２０1のノード２
に接続される処理要素１１０6から、"丸Ｃ"で示される
破線のパスを介して、スイッチ・チップ１２０0のノー
ド２に接続される処理要素１１０2に経路指定される。
同様にパケット"Ｄ"は、スイッチ・チップ１２０5のノ
ード１に接続される処理要素１１０21から、"丸Ｄ"で示
される破線のパスを介して、スイッチ・チップ１２０4
のノード０に接続される処理要素１１０16に経路指定さ
れる。
【００４０】図示のように、全ての４つのパケットは同
時に衝突する経路を有し、同一セットの４つのケーブル
を介する。各経路はそのケーブルを他の２つの経路と共
用する。結果的に、各スイッチ・チップ１２０0、１２
０1、１２０4及び１２０5は、対応する中央キューに内
在するこれらのパケットと共に、これらのスイッチ・チ
ップの任意の他の１つが最初にそのパケットを経路指定
するのを待機することになる。各パケットは基本的にス
イッチ・チップの１つにおいて（但し、異なるポートを
通じて）その方向を反転する、すなわち"ターン・アラ
ウンド"するので、これらの全てのパケットにより取ら
れる経路は、集合的に閉ループ・パターン（番号Ｉ−Ｉ
Ｉ−ＩＩＩ−ＩＶで示され、ここでは"サイクル"として
参照される）を形成することになる。スイッチ・チップ
はこれらのどの特定のパケットを最初に経路指定するか
を決定できないので、全てのスイッチ・チップは単に待
機し、いずれのパケットも経路指定されない。サイクル
内の４つの各々のパケット自身が、残りの３つのパケッ
トを妨害することになる。結果的に、経路指定デッドロ
ックが発生する。このデッドロックが持続する間、対応
するパスはパケット・トラフィックを伝搬しない。従っ
て、処理要素１１０4、１１０23、１１０2及び１１０16
は単にパケットの到来を待機し、これらのパケットを要
求するアプリケーション部分の処理が延期される。これ
はすなわち、システム５の処理スループットを低下させ
ることになる。経路指定デッドロックが発生すると、こ
の状態は何らかの手段により解決されるまで無期限に継
続する。経路指定デッドロックは比較的稀にしか発生し
ないが、並列処理システムの規模が増大すると、これら
のデッドロックの発生の潜在性も増加する。
【００４１】この現象を鑑み、本発明は比較的大規模な
大容量並列処理システムにおいて、経路指定デッドロッ
クの発生を防止する手法を提供する。本手法は具体化が
非常に単純で高度にコスト有効であり、パケット・ネッ
トワークにおける伝送帯域幅の適度で受諾可能な低減を
強要するに過ぎない。
【００４２】本手法により、特定の予め定義された経路
が、大域経路テーブルの形成の間にこれらの経路を使用
する特定の処理要素（ネットワーク・ノード）の相対ロ
ケーションにもとづき考慮から除外される。禁止された
経路は、もしそれらが使用されないと、閉ループ経路指
定パターン、従って経路指定デッドロックの発生を防止
する経路として選択される。経路テーブルに含まれる経
路の選択において、システムのある区分、例えばシステ
ムの半分内のノード間をもっぱら流れるパケット・トラ
フィックを別の区分、例えばシステムの他の半分内のノ
ード間を流れるパケット・トラフィックから分離するた
めに経路が禁止される。この点に関し、システムの共通
区分内のノード間を通過するパケットの経路を抽出する
ために、システムの別の区分を通過するパス（ケーブル
など）を含む経路が禁止される。複数のシステム区分、
例えばシステムの異なる半分内のノード間でパケットを
伝搬する経路の選択においては、こうした経路の禁止は
発生しない。システムの各区分、例えば半分を他の区
分、例えばシステムの他の半分内の処理要素対間をもっ
ぱら流れるパケット・トラフィックから分離することに
より、これらのパケットの相互作用により生じる経路指
定デッドロックが有利に防止される。
【００４３】比較的大規模な大容量並列処理システム、
例えば５１２の別々の処理要素を使用するシステムにお
いて必要なプロセッサ間経路指定機能を提供するため
に、システムは多数のスイッチ・ボードを使用する。各
スイッチ・ボードは上述されたように同一であり、２つ
の相互接続ステージ、すなわち個々の処理要素に接続さ
れるノード・スイッチ・ボード（ＮＳＢ）、及びノード
・スイッチ・ボード自身を相互接続するために使用され
る中間スイッチ・ボード（ＩＳＢ）に編成される。５１
２プロセッサ・システムは、通常、４８個の別々のスイ
ッチ・ボードを使用し、これらの内の３２個のボードは
ＮＳＢ専用であり、残りの１６個のボードはＩＳＢ専用
である。各ＮＳＢは１６個のそれぞれ異なる処理要素に
接続される１６ポートと、１６個の各ＩＳＢ上の異なる
ポートに相互接続される別の１６ポートを提供する。こ
の構成では、ＮＳＢはパケットを自身が接続される個々
の処理要素との間で経路指定し、ＩＳＢはパケットを異
なるＮＳＢ間で経路指定し、全ての完全な経路が、上述
のようにパケット・ヘッダに含まれる経路指定バイトに
より指定される。
【００４４】５１２プロセッサ・システムの例が、図４
にシステム４００として示される。図示のように、この
システムは集合的に処理ノード４１０として示される５
１２の異なる処理要素４１５0、．．．、４１
５15、．．．４１５496、．．．４１５511を提供し、物
理的見地から１６個の処理要素を含む３２個の物理ラッ
ク、特に処理ラック４１０0、．．．４１０31に編成さ
れる。各ラックはそれぞれのＮＳＢの１６ポートに接続
される。システム４００は３２個のＮＳＢ４４０0、４
４０1、４４０2、４４０3、４４０4、４４
０5、．．．、４４０30及び４４０31（ＮＳＢ０、ＮＳ
Ｂ１などとしても指定される）を含む。各ＮＳＢの残り
の１６ポートは、接続マトリックス４５０内の個々のケ
ーブルを介して、１６個のＩＳＢ４６０、特にＩＳＢ４
６０0、４６０1、４６０2、．．．、４６０15（ＩＳＢ
０、ＩＳＢ１などとしても指定される）の各々の対応す
るポートに相互接続される。例えば、ＮＳＢ４４０
0（ＮＳＢ０）上の１６個の各ポートは、１６個のＩＳ
Ｂの対応する異なる１つのポート０に接続されるように
示され、それによりＮＳＢ４４０0は各ＩＳＢにパケッ
トを経路指定できる。他のＮＳＢについても図示のよう
に、あらゆるＩＳＢに同様に相互接続される。ＩＳＢで
あろうとＮＳＢであろうと、全てのスイッチ・ボードは
互いに同一であるが、接続マトリックス４５０を明瞭に
表す都合上、ＩＳＢはＮＳＢと異なるように示される。
【００４５】システム４００において、中間スイッチ・
ボードなどの使用に頼る他の大規模大容量並列処理シス
テムと同様、本発明を使用しないと、経路指定デッドロ
ックが発生することが理解される。なぜなら、パケット
が異なるＮＳＢ間で経路指定される時、図１に示される
システム５のスイッチ１２０4及び１２０5内で、パケッ
ト"Ａ"及び"Ｃ"がそれらの方向を反転（"ターン・アラ
ウンド"）する時のように、その方向をＩＳＢ内で反転
するからである。図４に示されるように、パケットはＩ
ＳＢ内においては生成されず、単にそれを通じて別々の
ＮＳＢ間で経路指定されるだけなので、閉ループ経路指
定パターンがもしも発生すると、それらはＩＳＢに延び
る必要があり、ＮＳＢ内だけに存在するとは限らなくな
る。システム４００内の経路指定デッドロックは、任意
の１つまたは複数のＮＳＢ自身だけに制約されない。
【００４６】本発明の教示によれば、禁止する経路を決
定するために、システム４００は例証的に半分に区分さ
れる。この場合、１６個の連続するＮＳＢ（例えばＮＳ
Ｂ０乃至１５、及びＮＳＢ１６乃至３１）、及び２５６
個の連続する処理要素（例えばそれぞれ要素４１
５0、．．．、４１５255及び４１５256、．．．、４１
５511）は各半分に割当てられる。また最初の８個のＩ
ＳＢが片方の半分に含まれ、残りの８個のＩＳＢが他の
半分に含まれる。この点に関し、図５を参照すると、図
４のシステム４００を構成する全てのＮＳＢ並びにＩＳ
Ｂ４６０が示される。図示のように、システムは５０３
と５０７のそれぞれ半分に区分される。３２個の各ＮＳ
Ｂ上のポート０などの共通ポート（ラベル付けされてい
ない）が、別々の対応するパス（ケーブル）を介して、
単一のＩＳＢ上の３２個のポートの対応する１つに接続
される。全てのＮＳＢ上の残りの各ポート及び他のＩＳ
Ｂについても同様である。システムの半分５０３は、Ｎ
ＳＢ４４０0乃至４４０15及びＩＳＢ４６０0乃至４６０
15を含む。ここではＮＳＢ４４０0乃至４４０15は、パ
ス５１０0、0、５１０1、0、．．．、５１０15、0を介し
て、単一のＩＳＢの１６個の連続するポート（特にそれ
らの３つだけが示されている）、ここではＩＳＢ４６０
0の特にスイッチ・チップ５３０0乃至５３０3に接続さ
れるように示される。残りのシステムの半分５０７は、
ＮＳＢ４４０17乃至４４０31、及びＩＳＢ４６０8乃至
４６０15を含む。同様にこれらの特定のＮＳＢはパス５
１０16、15、５１０17、15、．．．、５１０31、15を介し
て、単一のＩＳＢの対応するポート、ここではＩＳＢ４
６０15の特にスイッチ・チップ５４０4乃至５４０7に接
続されるように示される。
【００４７】システムの共通半分、例えば半分５０３内
に配置される処理要素間を通過するパケットに対して
は、システムのその半分内に完全に含まれるＩＳＢを含
む使用可能な経路（ＮＳＢ４４０0と４４０15間の経路
５２２、及びＮＳＢ４４０31と４４０16間の経路５２４
など）だけが許可され、他の経路（ＮＳＢ４４０0と４
４０15間の破線で示される経路５３４、及びＮＳＢ４４
０31と４４０16間の破線で示される経路５３２）は禁止
される。従って、後者の任意の経路はシステム初期化の
間に、これらの処理要素を接続する大域経路テーブル内
に含まれない。禁止された経路はまた、その経路上の"
Ｘ"により示される。或いはシステムの異なる半分内に
配置される処理要素間を通過するパケットに対して、こ
うした経路が禁止されなくてもよい。この場合、経路選
択は大域経路テーブル内に結果的に含むものに対して、
システムの半分にもとづく制限無しに、ＮＳＢ４４０0
と４４０16間のその時使用可能な全ての経路（１つの場
合もある（特に図示せず））の中から実施される。
【００４８】経路の禁止は後述されるように、大域経路
テーブルが生成される間に、特定の経路指定指示を処理
することにより実行される。この処理は、全ての禁止経
路がネットワーク・ノードの所与の対間で定義される経
路として選択されることを防止する。
【００４９】自身の内部処理要素間で発生するパケット
・トラフィックに対応して、システムの各半分を分離
し、それにより他の半分に含まれる処理要素間を通過す
るパケットとの相互作用を排除することにより、経路指
定デッドロックが有利に防止される。
【００５０】驚くことに、上述のように５１２ポート交
換ネットワークの多数の分析の結果、ネットワークを通
過する期待されるトラフィック・パターンに関し、本発
明の手法によれば、ネットワークの最大伝送帯域幅が支
障無い程度に減少するだけであることが判明した。この
点に関し、本発明の使用は、ネットワークにおいて使用
可能な最大帯域幅のほぼ７４％を確保し、これは期待し
た約５０％を大きく上回るものである。従って、経路指
定デッドロックを回避するための本手法の使用による不
利益は、特に獲得される利点を鑑みれば、極めて受諾可
能と言える。
【００５１】上述の説明を鑑み、図６は、図４に示され
るシステム４００内に配置されるサービス・プロセッサ
（例として処理要素４１５511）内で実行される、本発
明の教示によりパケット経路を定義する経路テーブル発
生器ルーチン６００のハイレベル流れ図を示す。ルーチ
ン６００は、上述のようにサービス・プロセッサ内で実
行される初期化ルーチンの１部である。
【００５２】図６に示されるように、ルーチン６００へ
のエントリに際し、実行は最初にブロック６１０に移行
し、トポロジ・ファイル及び付随する経路指定指示を読
出す。デッドロック回避経路指定を提供するために、パ
ケット・ネットワーク内の各装置、例えばスイッチ回路
（または特にそこで使用されるスイッチ・チップ）に対
応する適切な指示、すなわちその装置を通過する経路指
定が制限されているか否か、換言すると、パケットがこ
の回路を通じて方向を反転可能か否かを示す指示が、ト
ポロジ・ファイル内に含まれなければならない。ネット
ワーク１００を実現する図１に示されるスイッチ・ボー
ドについて考えてみる。上述のように、各スイッチ・チ
ップのポート０乃至３は、スイッチ・ボードの外部のリ
ンクに接続され、各スイッチ・チップのポート４乃至７
は接続マトリックス１４０内のリンク（ケーブル）に接
続され、それを通じて、同一ボード内の別のスイッチ・
チップのポートに接続される。トポロジ・ファイル内に
おいて特定のスイッチ・チップに対して指定される経路
指定指示"ｎｒ"は、そのチップに関し、経路指定制限が
存在しないことを意味する。パケットはこのチップ上の
任意の８個のポートに入力することができ、チップ上の
他のポートから去ることができる。この例では、パケッ
トはチップ内でその方向を反転（"ターン・アラウン
ド"）することができる。或いはスイッチ・チップに対
して、トポロジ・ファイル内に経路指定指示"n-i-t"が
存在すると、ポート４乃至７に入力するパケットは、チ
ップ上のポート０乃至３からだけ出力するようにその経
路指定が制限される。すなわち、そのパケットはチップ
内で方向を反転することを禁止される。しかしなが
ら、"n-i-t"指示は、スイッチ・チップの任意のポート
０乃至３に到来するパケットに対しては制限せず、これ
はそのチップ上の任意の他のポートに経路指定される。
デッドロック回避指示を有するトポロジ・ファイル内の
サンプル行は次の通りである。
【数１】aux routing n-i-t 330 331 332 333 ここで、"aux routing"は、経路指定指示を有する補助
行を意味する。そして、"330 331 332 333"は、トポロ
ジ・ファイル内で使用されるフォーマットの特定のスイ
ッチ回路の数値識別子である。
【００５３】ブロック６１０が完全に実行されると、実
行はブロック６２０に移行し、トポロジ・ファイル内で
指定される各ケーブル（リンク）に関連する重みを０に
設定する。更に出所ノード・カウンタに相当するノード
ｉが０に初期化される。その後、実行はブロック６３０
に移行する。この特定のブロックはトポロジ・ファイル
内に含まれるデータと付随するデッドロック回避経路指
定指示とを一緒に使用することにより、パケット・ネッ
トワークを通じて現出所ノード（ノードｉ）をシステム
内のあらゆる宛先ノードに接続するために使用可能な経
路のセットを抽出する。具体的には、既知のブレッドス
・ファースト探索（breadth-first search）により、最
短長を有する経路、すなわち必ずしも物理的に最短長を
有するわけではないが、最少の個々のリンク（ケーブ
ル）を有する経路が選択される。上述された各スイッチ
回路に関連するデッドロック回避経路選択を表す擬似コ
ードを次に示す。
【数２】case of routing_directive is { "nr":total_permissible_oports=8; /*スイッチ・チップ上の全出力ポート*/ "n-i-t":if(input_port<4) total_permissible_oports=8; else total_permissible_oports=4; } i=0; while(i<total_permissible_oports) do { permissible_oport[i]=i i=i+1 }
【００５４】最短パス経路のセットの選択は、ブロック
６４０に示されるように、経路が現出所ノードから全て
の宛先ノードに延びるまで、すなわち経路が宛先ベース
になるまで出所ベースで発生する。１つの最短長経路だ
けが出所ノードから宛先ノードに生じる場合、その経路
が選択されて使用される。或いは複数のこうした経路が
この出所ノードと共通宛先ノード間で生じる場合、集合
的に最低の重みのケーブルを有する経路が選択される。
重みベースの選択により、パケット・ネットワーク全体
を通じて最小のケーブルの共用を維持するように、トラ
フィック負荷が平衡される。出所ノードと宛先ノードの
間で特性の経路が選択されると、その経路内の各ケーブ
ルに関連する重みが１だけ増分される。ブロック６３０
及び６４０は、理解を容易にするために別個のブロック
として示されるが、オペレーションは一般に結合され
る。
【００５５】全ての宛先ノードに対応して全ての経路が
選択されると、実行はブロック６５０に移行し、全ての
選択経路を大域経路テーブルに書込む。これにより現出
所ノードに対する経路テーブルが形成される。その後、
実行は判断ブロック６６０に移行し、ネットワーク内の
あらゆるノードに対して、経路テーブルが大域経路テー
ブルに書込まれたかどうかを判断する。経路テーブルが
あらゆるノードに対して書込まれていない場合には、判
断ブロック６６０は実行を否定パス６６７を介して、ブ
ロック６７０に移行させる。この後者のブロックの実行
により、出所ノード・カウンタｉが１増分される。実行
は次にパス６７５を介して、ブロック６３０へループし
て戻り、次に続くノードの経路を判断しそれを書込む。
或いは経路テーブルが全てのノードについて書込まれる
と、実行は判断ブロック６６０からの肯定パス６６３を
介して、ルーチン６００を終了する。このルーチンの実
行の後、初期化処理の完了に先立ち、上述のサービス・
プロセッサはネットワークを通じ、大域経路テーブルの
対応部分を、自身を含む各々の及びあらゆる個々の処理
要素に提供する（特にコピーする）。そして、こうして
記憶されたものが、後に局所経路テーブルとして使用さ
れる。この部分は、その特定の処理要素が出所ノードの
時に選択される経路を含むだけである。
【００５６】これまでの説明から当業者には理解される
ように、本発明は５１２の別々の処理要素を有する大容
量並列処理システムに関連して述べられてきたが、もち
ろんこれに限るものではない。実際に、本発明は実質的
に双方向マルチステージ相互接続クロスポイント・ベー
ス・パケット・ネットワークを使用する任意のサイズの
並列処理システムにおける、経路指定デッドロックの回
避にも適用される。その点に関し、本発明は６４プロセ
ッサ・システム、２５６プロセッサ・システム、及び他
のサイズの類似のシステム、並びにマルチステージ相互
接続クロスポイント・パケット・ネットワークを使用す
る他のシステムにそれらの最終利用に関係無く、容易に
組込むことが可能である。
【００５７】更に、本発明の教示はパケット・ネットワ
ークを２つの別々の半分に区分し、それらの間の経路指
定を制限する状況において述べられたが、こうしたネッ
トワークは本発明により任意の数の別々の区分に分割さ
れ、これらの各区分内だけをもっぱら通過するパケット
・トラフィックを分離するように編成される。もちろ
ん、区分数が増加すると、それに伴い区分化を達成する
ために必要となる禁止経路の数も増加する。残念なが
ら、禁止経路の数が増えるとパケット・トラフィックを
伝搬する使用可能な経路が減少し、従って、ネットワー
クの伝送帯域幅が減少する。支障の無い帯域幅の減少を
鑑みると、達成されるパケット分離及びデッドロック回
避の点から、２つの区分が優れたトレードオフを提供す
ることが判明した。
【００５８】まとめとして、本発明の構成に関して以下
の事項を開示する。
【００５９】（１）パケット・ネットワークの外部の複
数のノードを集合的に相互接続するクロスポイント・ス
イッチの連続ステージを含む前記ネットワークを有する
装置において、パケットが前記ネットワーク及び少なく
とも１つの前記スイッチを介して、規定経路上を第１の
前記ノードから第２の前記ノードに伝搬されるものにお
いて、前記ネットワーク内における経路指定デッドロッ
クの発生を回避する実質的な方法であって、パケットが
前記複数のノード内の個々のノードから、異なる対応す
る前記経路を介して、前記複数のノードのあらゆる他の
ノードに伝搬されるように、前記ネットワークを介する
複数の規定経路を第１に定義するステップであって、前
記の各定義経路が少なくとも１つのリンクに伸び、第１
のネットワーク区分だけに接続される第１及び第２の前
記ノード間を通過するパケットが、第２のネットワーク
区分に伸びるリンクを有する経路上で伝搬されないよう
に、前記ネットワークを前記第１及び前記第２のネット
ワーク区分に分割するように前記規定経路を定義する、
前記第１の定義ステップと、全ての前記規定経路を結果
の経路テーブルに記憶するステップとを含む、方法。 （２）前記第１の定義ステップが、前記第１及び前記第
２のネットワーク区分にそれぞれ接続される第３及び第
４のノード間を通過するパケットが、前記第１及び前記
第２のネットワーク区分間に伸びる少なくとも１つのリ
ンクを有する経路上で伝搬されるように、前記複数の規
定経路を定義する第２の定義ステップを含む、前記
（１）記載の方法。 （３）前記ネットワーク内において出所ノードから宛先
ノードに経路指定されるパケットをアセンブルする際
に、前記第３及び前記第４の両ノード内において、前記
パケットの結果的経路を生成するために、前記経路テー
ブルをアクセスするステップと、前記結果的経路を前記
パケットにコピーするステップと、前記パケットを前記
結果的経路上で前記ネットワークを介して経路指定する
ステップとを含む、前記（２）記載の方法。 （４）前記経路テーブルの異なる部分を、前記複数の各
ノードに対応する別々の局所経路テーブルにダウンロー
ドするステップであって、前記の各経路テーブル部分が
前記各ノードを出所ノードとして有する全ての前記規定
経路を指定する、前記ダウンロード・ステップを含み、
前記経路コピー・ステップが、前記出所ノードから前記
宛先ノードに伝搬されるパケットの前記結果的経路を生
成するために、前記パケットの前記宛先ノードにもとづ
き、前記出所ノードの前記局所経路テーブルをアクセス
するステップを含む、前記（３）記載の方法。 （５）前記の各パケットが少なくとも１つの経路バイト
を含む経路フィールドを有するヘッダを含み、前記経路
フィールドが前記各パケットが前記ネットワークを伝わ
る経路を集合的に指定し、各個々の前記経路バイトが前
記各パケットが対応する前記クロスポイント・スイッチ
の１つを横断する経路を定義し、前記結果的経路のコピ
ー・ステップが前記結果的経路内の各連続する前記経路
バイトの値を前記ヘッダ内の別々の対応する連続経路バ
イトにコピーするステップを含む、前記（４）記載の方
法。 （６）各ネットワーク区分が前記ネットワークの異なる
半分を構成する、前記（５）記載の方法。 （７）前記装置をサービス・フェーズ及び実行フェーズ
で動作させるステップであって、前記第１の定義ステッ
プ及び前記規定経路記憶ステップを前記サービス・フェ
ーズの間に実行し、前記結果的経路アクセス・ステッ
プ、前記結果的経路コピー・ステップ及び前記パケット
経路指定ステップを前記実行フェーズの間に実行する前
記動作ステップを含む、前記（５）記載の方法。 （８）前記第１の定義ステップが、トポロジ・ファイル
内のネットワーク装置及び相互接続データに応答して、
出所ノードとしての前記の各ノードから、宛先ノードと
してのあらゆる他の使用可能な前記ノードの１つへの全
ての使用可能な最短パス経路を決定するステップであっ
て、前記トポロジ・ファイル内に含まれるある前記装置
に対するデッドロック回避指示により禁止される前記装
置を通過するパスを有する経路を、前記最短パス経路か
ら除外する、前記決定ステップと、ある前記出所ノード
とある前記宛先ノード間で１つの前記最短パス経路が存
在する場合、前記最短パス経路を前記経路テーブルに、
前記出所ノードと前記宛先ノード間の規定経路として書
込むステップと、ある前記出所ノードとある前記宛先ノ
ード間で複数の最短パス経路が存在する場合、前記最短
パス経路の中から、集合的に最小の重みを有する１つの
前記最短パス経路を、前記出所ノードと前記宛先ノード
間の前記規定経路として選択するステップと、前記規定
経路内の各リンクに対応する別々の重みを、予め定義さ
れた量だけ増分するステップとを含む、前記（５）記載
の方法。 （９）前記全ての使用可能な経路の決定ステップが、前
記全ての使用可能な最短パス経路を突き止めるブレッド
ス・ファースト探索を実行するステップを含む、前記
（８）記載の方法。 （１０）前記装置をサービス・フェーズ及び実行フェー
ズで動作させるステップであって、前記第１の定義ステ
ップ及び前記規定経路記憶ステップを前記サービス・フ
ェーズの間に実行し、前記結果的経路アクセス・ステッ
プ、前記結果的経路コピー・ステップ及び前記パケット
経路指定ステップを前記実行フェーズの間に実行する前
記動作ステップを含む、前記（９）記載の方法。 （１１）各ネットワーク区分が前記ネットワークの異な
る半分を構成する、前記（１０）記載の方法。 （１２）パケット・ネットワークの外部の複数のノード
を集合的に相互接続するクロスポイント・スイッチの連
続ステージを含む前記ネットワークを有するシステムに
おいて、パケットが前記ネットワーク及び少なくとも１
つの前記スイッチを介して、規定経路上を第１の前記ノ
ードから第２の前記ノードに伝搬されるものにおいて、
前記ネットワーク内における経路指定デッドロックの発
生を回避する装置であって、パケットが前記複数のノー
ド内の個々のノードから、異なる対応する前記経路を介
して、前記複数のノードのあらゆる他のノードに伝搬さ
れるように、前記ネットワークを介する複数の規定経路
を定義する第１の手段であって、前記の各定義経路が少
なくとも１つのリンクに伸び、第１のネットワーク区分
だけに接続される第１及び第２の前記ノード間を通過す
るパケットが、第２のネットワーク区分に伸びるリンク
を有する経路上で伝搬されないように、前記ネットワー
クを前記第１及び前記第２のネットワーク区分に分割す
るように前記規定経路を定義する、前記第１の定義手段
と、全ての前記規定経路を結果の経路テーブルに記憶す
る手段とを含む装置。 （１３）前記第１の定義手段が、前記第１及び前記第２
のネットワーク区分にそれぞれ接続される第３及び第４
のノード間を通過するパケットが、前記第１及び前記第
２のネットワーク区分間に伸びる少なくとも１つのリン
クを有する経路上で伝搬されるように、前記複数の規定
経路を定義する、前記（１２）記載の装置。 （１４）前記ネットワーク内において出所ノードから宛
先ノードに経路指定されるパケットをアセンブルする間
に、前記第３及び前記第４の両ノード内において、前記
パケットの結果的経路を生成するために、前記経路テー
ブルをアクセスし、前記結果的経路を前記パケットにコ
ピーし、前記パケットを前記結果的経路上で前記ネット
ワークを介して経路指定する手段を含む、前記（１３）
記載の装置。 （１５）前記経路テーブルの異なる部分がダウンロード
される前記複数の各ノードに対応する別々の局所経路テ
ーブルであって、前記の各経路テーブル部分が前記各ノ
ードを出所ノードとして有する全ての前記規定経路を指
定する、前記局所経路テーブルと、前記出所ノードから
前記宛先ノードに伝搬されるパケットの前記結果的経路
を生成するために、前記パケットの前記宛先ノードにも
とづき、前記出所ノードの前記局所経路テーブルをアク
セスする手段とを含む、前記（１４）記載の装置。 （１６）前記の各パケットが少なくとも１つの経路バイ
トを含む経路フィールドを有するヘッダを含み、前記経
路フィールドが前記各パケットが前記ネットワークを伝
わる経路を集合的に指定し、各個々の前記経路バイトが
前記各パケットが対応する前記クロスポイント・スイッ
チの１つを横断する経路を定義し、前記結果的経路内の
各連続する前記経路バイトの値を、前記ヘッダ内の別々
の対応する連続経路バイトにコピーする、前記（１５）
記載の装置。 （１７）各ネットワーク区分が前記ネットワークの異な
る半分を構成する、前記（１６）記載の装置。 （１８）前記第１の定義手段が、トポロジ・ファイル内
のネットワーク装置及び相互接続データに応答して、出
所ノードとしての前記の各ノードから、宛先ノードとし
てのあらゆる他の使用可能な前記ノードの１つへの全て
の使用可能な最短パス経路を決定する手段であって、前
記トポロジ・ファイル内に含まれるある前記装置に対す
るデッドロック回避指示により禁止される前記装置を通
過するパスを有する経路を、前記最短パス経路から除外
する、前記決定手段と、ある前記出所ノードとある前記
宛先ノード間で１つの前記最短パス経路が存在する場
合、前記最短パス経路を前記経路テーブルに、前記出所
ノードと前記宛先ノード間の規定経路として書込む手段
と、ある前記出所ノードとある前記宛先ノード間で複数
の最短パス経路が存在する場合、前記最短パス経路の中
から、集合的に最小の重みを有する１つの前記最短パス
経路を、前記出所ノードと前記宛先ノード間の前記規定
経路として選択する手段と、前記規定経路内の各リンク
に対応する別々の重みを、予め定義された量だけ増分す
る手段とを含む、前記（１６）記載の装置。 （１９）前記システムが並列処理システムであり、前記
の各ノードが別々の処理要素を含む、前記（１６）記載
の装置。 （２０）前記並列処理システムが５１２個の別々の処理
要素を含み、前記スイッチが３２ポート・スイッチ・ボ
ードに編成され、前記システムが３２個のノード・スイ
ッチ・ボード（ＮＳＢ）と１６個の中間スイッチ・ボー
ド（ＩＳＢ）による複数のスイッチ・ボードを含み、前
記ＩＳＢが、前記の各ＮＳＢ上の１６ポートのそれぞれ
が、異なる対応するリンクを介して、前記の各ＮＳＢ上
の同一の対応するポートに接続されるように、また前記
の各ＮＳＢ上の残りの１６ポートが１６個の異なる連続
する前記処理要素に接続されるように、全ての前記ＮＳ
Ｂを集合的に相互接続する、前記（１９）記載の装置。
【００６０】
【発明の効果】以上説明したように、本発明によれば、
大規模双方向マルチステージ相互接続クロスポイント・
スイッチ・ベース・パケット・ネットワークにおいて、
デッドロックの無い経路指定を確立する単純でコスト・
パフォーマンスの良い装置及び方法が提供される。
【図面の簡単な説明】
【図１】３２個の別々の処理要素を使用する従来の並列
処理システム５のハイレベル・ブロック図である。
【図２】図１に示されるシステム５を通過するパケット
３００及びその構成フィールドを表す図である。
【図３】図１に示されるシステム５を構成する処理ノー
ド１１０、及び特にこれらのノードのメモリ内に存在し
てパケット経路指定を達成する様々なファイル及びテー
ブルを示す図である。
【図４】５１２の処理要素を含み、本発明の教示を使用
する並列処理システム４００のハイレベル・ブロック図
である。
【図５】システム４００内に配置される中間スイッチ・
ボード（ＩＳＢ）及びそれらの相互接続ノード・スイッ
チ・ボード（ＮＳＢ）を示し、パケット経路の例が本発
明の教示により決定される。
【図６】サービス・プロセッサ内で実行される経路テー
ブル発生器ルーチン６００のハイレベル流れ図であり、
図４に示される処理要素４１５511が、本発明の教示に
よりパケット経路を定義するためにシステム４００内に
配置される。
【符号の説明】
５、４００ ３２プロセッサ並列処理システム １００ ノード・パケット・スイッチ １１０ 処理要素、処理ノード １２０ ８×８双方向スイッチ回路 １４０、４５０ 接続マトリックス ２００ パケット ２１０ 長さフィールド ２２０ 経路指定フィールド ２３０ シーケンス番号フィールド ２４０ データ・フィールド ３２０、３８０ 局所経路テーブル ３４０ メモリ ３５０ トポロジ・ファイル ３６０ 大域経路テーブル ３７０ 初期化ルーチン ４６０ ＩＢＳ ６００ 経路テーブル発生器ルーチン ６６７ 否定パス
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ロバート・フレデリック・スタッケ アメリカ合衆国12477、ニューヨーク州ソ ガティーズ、リッジ・ロード 14 (72)発明者 クレイグ・ブライアン・スタンケル アメリカ合衆国06801、コネチカット州ベ スル、グリーン・パスチャー・ロード 10

Claims (20)

    【特許請求の範囲】
  1. 【請求項１】パケット・ネットワークの外部の複数のノ
    ードを集合的に相互接続するクロスポイント・スイッチ
    の連続ステージを含む前記ネットワークを有する装置に
    おいて、パケットが前記ネットワーク及び少なくとも１
    つの前記スイッチを介して、規定経路上を第１の前記ノ
    ードから第２の前記ノードに伝搬されるものにおいて、
    前記ネットワーク内における経路指定デッドロックの発
    生を回避する実質的な方法であって、 パケットが前記複数のノード内の個々のノードから、異
    なる対応する前記経路を介して、前記複数のノードのあ
    らゆる他のノードに伝搬されるように、前記ネットワー
    クを介する複数の規定経路を第１に定義するステップで
    あって、前記の各定義経路が少なくとも１つのリンクに
    伸び、第１のネットワーク区分だけに接続される第１及
    び第２の前記ノード間を通過するパケットが、第２のネ
    ットワーク区分に伸びるリンクを有する経路上で伝搬さ
    れないように、前記ネットワークを前記第１及び前記第
    ２のネットワーク区分に分割するように前記規定経路を
    定義する、前記第１の定義ステップと、 全ての前記規定経路を結果の経路テーブルに記憶するス
    テップと、 を含む、方法。
  2. 【請求項２】前記第１の定義ステップが、前記第１及び
    前記第２のネットワーク区分にそれぞれ接続される第３
    及び第４のノード間を通過するパケットが、前記第１及
    び前記第２のネットワーク区分間に伸びる少なくとも１
    つのリンクを有する経路上で伝搬されるように、前記複
    数の規定経路を定義する第２の定義ステップを含む、請
    求項１記載の方法。
  3. 【請求項３】前記ネットワーク内において出所ノードか
    ら宛先ノードに経路指定されるパケットをアセンブルす
    る際に、前記第３及び前記第４の両ノード内において、
    前記パケットの結果的経路を生成するために、前記経路
    テーブルをアクセスするステップと、 前記結果的経路を前記パケットにコピーするステップ
    と、 前記パケットを前記結果的経路上で前記ネットワークを
    介して経路指定するステップと、 を含む、請求項２記載の方法。
  4. 【請求項４】前記経路テーブルの異なる部分を、前記複
    数の各ノードに対応する別々の局所経路テーブルにダウ
    ンロードするステップであって、前記の各経路テーブル
    部分が前記各ノードを出所ノードとして有する全ての前
    記規定経路を指定する、前記ダウンロード・ステップを
    含み、 前記経路コピー・ステップが、前記出所ノードから前記
    宛先ノードに伝搬されるパケットの前記結果的経路を生
    成するために、前記パケットの前記宛先ノードにもとづ
    き、前記出所ノードの前記局所経路テーブルをアクセス
    するステップを含む、請求項３記載の方法。
  5. 【請求項５】前記の各パケットが少なくとも１つの経路
    バイトを含む経路フィールドを有するヘッダを含み、前
    記経路フィールドが前記各パケットが前記ネットワーク
    を伝わる経路を集合的に指定し、各個々の前記経路バイ
    トが前記各パケットが対応する前記クロスポイント・ス
    イッチの１つを横断する経路を定義し、前記結果的経路
    のコピー・ステップが前記結果的経路内の各連続する前
    記経路バイトの値を前記ヘッダ内の別々の対応する連続
    経路バイトにコピーするステップを含む、請求項４記載
    の方法。
  6. 【請求項６】各ネットワーク区分が前記ネットワークの
    異なる半分を構成する、請求項５記載の方法。
  7. 【請求項７】前記装置をサービス・フェーズ及び実行フ
    ェーズで動作させるステップであって、前記第１の定義
    ステップ及び前記規定経路記憶ステップを前記サービス
    ・フェーズの間に実行し、前記結果的経路アクセス・ス
    テップ、前記結果的経路コピー・ステップ及び前記パケ
    ット経路指定ステップを前記実行フェーズの間に実行す
    る前記動作ステップを含む、請求項５記載の方法。
  8. 【請求項８】前記第１の定義ステップが、 トポロジ・ファイル内のネットワーク装置及び相互接続
    データに応答して、出所ノードとしての前記の各ノード
    から、宛先ノードとしてのあらゆる他の使用可能な前記
    ノードの１つへの全ての使用可能な最短パス経路を決定
    するステップであって、前記トポロジ・ファイル内に含
    まれるある前記装置に対するデッドロック回避指示によ
    り禁止される前記装置を通過するパスを有する経路を、
    前記最短パス経路から除外する、前記決定ステップと、 ある前記出所ノードとある前記宛先ノード間で１つの前
    記最短パス経路が存在する場合、前記最短パス経路を前
    記経路テーブルに、前記出所ノードと前記宛先ノード間
    の規定経路として書込むステップと、 ある前記出所ノードとある前記宛先ノード間で複数の最
    短パス経路が存在する場合、前記最短パス経路の中か
    ら、集合的に最小の重みを有する１つの前記最短パス経
    路を、前記出所ノードと前記宛先ノード間の前記規定経
    路として選択するステップと、 前記規定経路内の各リンクに対応する別々の重みを、予
    め定義された量だけ増分するステップと、 を含む、請求項５記載の方法。
  9. 【請求項９】前記全ての使用可能な経路の決定ステップ
    が、前記全ての使用可能な最短パス経路を突き止めるブ
    レッドス・ファースト探索を実行するステップを含む、
    請求項８記載の方法。
  10. 【請求項１０】前記装置をサービス・フェーズ及び実行
    フェーズで動作させるステップであって、前記第１の定
    義ステップ及び前記規定経路記憶ステップを前記サービ
    ス・フェーズの間に実行し、前記結果的経路アクセス・
    ステップ、前記結果的経路コピー・ステップ及び前記パ
    ケット経路指定ステップを前記実行フェーズの間に実行
    する前記動作ステップを含む、請求項９記載の方法。
  11. 【請求項１１】各ネットワーク区分が前記ネットワーク
    の異なる半分を構成する、請求項１０記載の方法。
  12. 【請求項１２】パケット・ネットワークの外部の複数の
    ノードを集合的に相互接続するクロスポイント・スイッ
    チの連続ステージを含む前記ネットワークを有するシス
    テムにおいて、パケットが前記ネットワーク及び少なく
    とも１つの前記スイッチを介して、規定経路上を第１の
    前記ノードから第２の前記ノードに伝搬されるものにお
    いて、前記ネットワーク内における経路指定デッドロッ
    クの発生を回避する装置であって、 パケットが前記複数のノード内の個々のノードから、異
    なる対応する前記経路を介して、前記複数のノードのあ
    らゆる他のノードに伝搬されるように、前記ネットワー
    クを介する複数の規定経路を定義する第１の手段であっ
    て、前記の各定義経路が少なくとも１つのリンクに伸
    び、第１のネットワーク区分だけに接続される第１及び
    第２の前記ノード間を通過するパケットが、第２のネッ
    トワーク区分に伸びるリンクを有する経路上で伝搬され
    ないように、前記ネットワークを前記第１及び前記第２
    のネットワーク区分に分割するように前記規定経路を定
    義する、前記第１の定義手段と、 全ての前記規定経路を結果の経路テーブルに記憶する手
    段と、 を含む装置。
  13. 【請求項１３】前記第１の定義手段が、前記第１及び前
    記第２のネットワーク区分にそれぞれ接続される第３及
    び第４のノード間を通過するパケットが、前記第１及び
    前記第２のネットワーク区分間に伸びる少なくとも１つ
    のリンクを有する経路上で伝搬されるように、前記複数
    の規定経路を定義する、請求項１２記載の装置。
  14. 【請求項１４】前記ネットワーク内において出所ノード
    から宛先ノードに経路指定されるパケットをアセンブル
    する間に、前記第３及び前記第４の両ノード内におい
    て、前記パケットの結果的経路を生成するために、前記
    経路テーブルをアクセスし、前記結果的経路を前記パケ
    ットにコピーし、前記パケットを前記結果的経路上で前
    記ネットワークを介して経路指定する手段を含む、請求
    項１３記載の装置。
  15. 【請求項１５】前記経路テーブルの異なる部分がダウン
    ロードされる前記複数の各ノードに対応する別々の局所
    経路テーブルであって、前記の各経路テーブル部分が前
    記各ノードを出所ノードとして有する全ての前記規定経
    路を指定する、前記局所経路テーブルと、 前記出所ノードから前記宛先ノードに伝搬されるパケッ
    トの前記結果的経路を生成するために、前記パケットの
    前記宛先ノードにもとづき、前記出所ノードの前記局所
    経路テーブルをアクセスする手段と、 を含む、請求項１４記載の装置。
  16. 【請求項１６】前記の各パケットが少なくとも１つの経
    路バイトを含む経路フィールドを有するヘッダを含み、
    前記経路フィールドが前記各パケットが前記ネットワー
    クを伝わる経路を集合的に指定し、各個々の前記経路バ
    イトが前記各パケットが対応する前記クロスポイント・
    スイッチの１つを横断する経路を定義し、前記結果的経
    路内の各連続する前記経路バイトの値を、前記ヘッダ内
    の別々の対応する連続経路バイトにコピーする、請求項
    １５記載の装置。
  17. 【請求項１７】各ネットワーク区分が前記ネットワーク
    の異なる半分を構成する、請求項１６記載の装置。
  18. 【請求項１８】前記第１の定義手段が、 トポロジ・ファイル内のネットワーク装置及び相互接続
    データに応答して、出所ノードとしての前記の各ノード
    から、宛先ノードとしてのあらゆる他の使用可能な前記
    ノードの１つへの全ての使用可能な最短パス経路を決定
    する手段であって、前記トポロジ・ファイル内に含まれ
    るある前記装置に対するデッドロック回避指示により禁
    止される前記装置を通過するパスを有する経路を、前記
    最短パス経路から除外する、前記決定手段と、 ある前記出所ノードとある前記宛先ノード間で１つの前
    記最短パス経路が存在する場合、前記最短パス経路を前
    記経路テーブルに、前記出所ノードと前記宛先ノード間
    の規定経路として書込む手段と、 ある前記出所ノードとある前記宛先ノード間で複数の最
    短パス経路が存在する場合、前記最短パス経路の中か
    ら、集合的に最小の重みを有する１つの前記最短パス経
    路を、前記出所ノードと前記宛先ノード間の前記規定経
    路として選択する手段と、 前記規定経路内の各リンクに対応する別々の重みを、予
    め定義された量だけ増分する手段と、 を含む、請求項１６記載の装置。
  19. 【請求項１９】前記システムが並列処理システムであ
    り、前記の各ノードが別々の処理要素を含む、請求項１
    ６記載の装置。
  20. 【請求項２０】前記並列処理システムが５１２個の別々
    の処理要素を含み、前記スイッチが３２ポート・スイッ
    チ・ボードに編成され、前記システムが３２個のノード
    ・スイッチ・ボード（ＮＳＢ）と１６個の中間スイッチ
    ・ボード（ＩＳＢ）による複数のスイッチ・ボードを含
    み、前記ＩＳＢが、前記の各ＮＳＢ上の１６ポートのそ
    れぞれが、異なる対応するリンクを介して、前記の各Ｎ
    ＳＢ上の同一の対応するポートに接続されるように、ま
    た前記の各ＮＳＢ上の残りの１６ポートが１６個の異な
    る連続する前記処理要素に接続されるように、全ての前
    記ＮＳＢを集合的に相互接続する、請求項１９記載の装
    置。
JP7012797A 1994-04-04 1995-01-30 パケットの経路指定デッドロック回避方法及び装置 Expired - Fee Related JP2817770B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US222284 1994-04-04
US08/222,284 US5453978A (en) 1994-04-04 1994-04-04 Technique for accomplishing deadlock free routing through a multi-stage cross-point packet switch

Publications (2)

Publication Number Publication Date
JPH07282018A true JPH07282018A (ja) 1995-10-27
JP2817770B2 JP2817770B2 (ja) 1998-10-30

Family

ID=22831629

Family Applications (1)

Application Number Title Priority Date Filing Date
JP7012797A Expired - Fee Related JP2817770B2 (ja) 1994-04-04 1995-01-30 パケットの経路指定デッドロック回避方法及び装置

Country Status (4)

Country Link
US (1) US5453978A (ja)
EP (1) EP0676703B1 (ja)
JP (1) JP2817770B2 (ja)
DE (1) DE69518782D1 (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2006236362A (ja) * 2006-03-13 2006-09-07 Handotai Rikougaku Kenkyu Center:Kk マルチプロセッサシステム装置
US7203816B2 (en) 2001-03-01 2007-04-10 Semiconductor Technology Academic Research Center Multi-processor system apparatus allowing a compiler to conduct a static scheduling process over a large scale system of processors and memory modules
US11855913B2 (en) 2018-10-31 2023-12-26 Hewlett Packard Enterprise Development Lp Hierarchical switching device with deadlockable storage and storage partitions

Families Citing this family (55)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3512866B2 (ja) * 1994-09-19 2004-03-31 富士通株式会社 ネットワーク内ノードのグループ化およびデータ転送方法
US5721820A (en) * 1995-09-11 1998-02-24 International Business Machines Corporation System for adaptively routing data in switching network wherein source node generates routing message identifying one or more routes form switch selects
US6055618A (en) * 1995-10-31 2000-04-25 Cray Research, Inc. Virtual maintenance network in multiprocessing system having a non-flow controlled virtual maintenance channel
US5737318A (en) * 1995-12-27 1998-04-07 Philips Electronics North America Corporation Method for initializing a wireless, packet-hopping network
US5812549A (en) * 1996-06-25 1998-09-22 International Business Machines Corporation Route restrictions for deadlock free routing with increased bandwidth in a multi-stage cross point packet switch
US5781546A (en) * 1996-06-25 1998-07-14 International Business Machines Corporation Route restrictions for deadlock free routing with increased bandwidth in a multi-stage cross point packet switch
US6031835A (en) * 1997-04-04 2000-02-29 International Business Machines Corporation Method for deadlock free and and reliable routing in a packet switched network
US5884090A (en) * 1997-07-17 1999-03-16 International Business Machines Corporation Method and apparatus for partitioning an interconnection medium in a partitioned multiprocessor computer system
US6021442A (en) * 1997-07-17 2000-02-01 International Business Machines Corporation Method and apparatus for partitioning an interconnection medium in a partitioned multiprocessor computer system
US5887184A (en) * 1997-07-17 1999-03-23 International Business Machines Corporation Method and apparatus for partitioning an interconnection medium in a partitioned multiprocessor computer system
US5970232A (en) * 1997-11-17 1999-10-19 Cray Research, Inc. Router table lookup mechanism
US6085303A (en) * 1997-11-17 2000-07-04 Cray Research, Inc. Seralized race-free virtual barrier network
US6230252B1 (en) 1997-11-17 2001-05-08 Silicon Graphics, Inc. Hybrid hypercube/torus architecture
US6065063A (en) * 1998-01-29 2000-05-16 International Business Machines Corp. Deadlock avoidance method in a computer network
US6247077B1 (en) 1998-02-06 2001-06-12 Ncr Corporation Highly-scalable parallel processing computer system architecture
US6216174B1 (en) 1998-09-29 2001-04-10 Silicon Graphics, Inc. System and method for fast barrier synchronization
JP2000295279A (ja) * 1999-04-02 2000-10-20 Nec Corp パケットスイッチ
US6567856B1 (en) * 1999-06-02 2003-05-20 Sun Microsystems, Inc. Deadlock-free routing
US6603742B1 (en) 1999-06-02 2003-08-05 Sun Microsystems, Inc. Network reconfiguration
US6791939B1 (en) 1999-06-02 2004-09-14 Sun Microsystems, Inc. Dynamic generation of deadlock-free routings
US6631421B1 (en) 1999-06-02 2003-10-07 Sun Microsystems, Inc. Recursive partitioning of networks
US6584073B1 (en) 1999-06-02 2003-06-24 Sun Microsystems, Inc. Network topologies
US6606326B1 (en) * 1999-07-02 2003-08-12 International Business Machines Corporation Packet switch employing dynamic transfer of data packet from central shared queue path to cross-point switching matrix path
US6751698B1 (en) 1999-09-29 2004-06-15 Silicon Graphics, Inc. Multiprocessor node controller circuit and method
US6674720B1 (en) 1999-09-29 2004-01-06 Silicon Graphics, Inc. Age-based network arbitration system and method
US6381643B1 (en) 1999-11-08 2002-04-30 International Business Machines Corporation Mechanism and procedure for detecting switch mis-cabling
US7075896B1 (en) * 2000-03-16 2006-07-11 Hewlett-Packard Development Company, L.P. Method for automatic layout of switched network topologies
US7921188B2 (en) 2001-08-16 2011-04-05 Newisys, Inc. Computer system partitioning using data transfer routing mechanism
US6992988B2 (en) * 2001-08-20 2006-01-31 Sun Microsystems, Inc. System and method for deadlock-free routing on arbitrary network topologies
US7152113B2 (en) * 2001-10-19 2006-12-19 Sun Microsystems, Inc. Efficient system and method of node and link insertion for deadlock-free routing on arbitrary topologies
US7110389B2 (en) * 2001-11-19 2006-09-19 International Business Machines Corporation Fanning route generation technique for multi-path networks
US7200117B2 (en) * 2002-01-31 2007-04-03 Sun Microsystems, Inc. Method of optimizing network capacity and fault tolerance in deadlock-free routing
US7675909B2 (en) * 2004-12-15 2010-03-09 Tellabs Operations, Inc. Method and apparatus for horizontally slicing a multi-stage switch fabric
US20060268691A1 (en) * 2005-05-31 2006-11-30 International Business Machines Corporation Divide and conquer route generation technique for distributed selection of routes within a multi-path network
US7978719B2 (en) * 2005-06-10 2011-07-12 International Business Machines Corporation Dynamically assigning endpoint identifiers to network interfaces of communications networks
US7925728B2 (en) * 2005-09-08 2011-04-12 International Business Machines Corporation Facilitating detection of hardware service actions
US8347143B2 (en) 2006-01-30 2013-01-01 International Business Machines Corporation Facilitating event management and analysis within a communications environment
US7853639B2 (en) * 2006-09-12 2010-12-14 International Business Machines Corporation Performing process migration with allreduce operations
US7835284B2 (en) * 2006-10-06 2010-11-16 International Business Machines Corporation Method and apparatus for routing data in an inter-nodal communications lattice of a massively parallel computer system by routing through transporter nodes
US7680048B2 (en) * 2006-10-06 2010-03-16 International Business Machiens Corporation Method and apparatus for routing data in an inter-nodal communications lattice of a massively parallel computer system by dynamically adjusting local routing strategies
US8031614B2 (en) * 2006-10-06 2011-10-04 International Business Machines Corporation Method and apparatus for routing data in an inter-nodal communications lattice of a massively parallel computer system by dynamic global mapping of contended links
US7839786B2 (en) * 2006-10-06 2010-11-23 International Business Machines Corporation Method and apparatus for routing data in an inter-nodal communications lattice of a massively parallel computer system by semi-randomly varying routing policies for different packets
US8423987B2 (en) * 2007-01-30 2013-04-16 International Business Machines Corporation Routing performance analysis and optimization within a massively parallel computer
US8370844B2 (en) * 2007-09-12 2013-02-05 International Business Machines Corporation Mechanism for process migration on a massively parallel computer
US8055879B2 (en) * 2007-12-13 2011-11-08 International Business Machines Corporation Tracking network contention
US9225545B2 (en) 2008-04-01 2015-12-29 International Business Machines Corporation Determining a path for network traffic between nodes in a parallel computer
US8949453B2 (en) 2010-11-30 2015-02-03 International Business Machines Corporation Data communications in a parallel active messaging interface of a parallel computer
CN102204184B (zh) * 2011-05-17 2014-10-08 华为技术有限公司 Kvm数据传输的方法、业务板及系统
US8949328B2 (en) 2011-07-13 2015-02-03 International Business Machines Corporation Performing collective operations in a distributed processing system
US8930962B2 (en) 2012-02-22 2015-01-06 International Business Machines Corporation Processing unexpected messages at a compute node of a parallel computer
CN103577379B (zh) * 2013-10-17 2016-04-13 中国人民解放军国防科学技术大学 一种检测片上网络中死锁的方法
JP6623939B2 (ja) * 2016-06-06 2019-12-25 富士通株式会社 情報処理装置、通信手順決定方法、および通信プログラム
US11218401B2 (en) 2017-08-10 2022-01-04 Arista Networks, Inc. Computer network device, a computer internetwork and a method for computer networking
US10938751B2 (en) 2018-04-18 2021-03-02 Hewlett Packard Enterprise Development Lp Hierarchical switching devices
US10757038B2 (en) 2018-07-06 2020-08-25 Hewlett Packard Enterprise Development Lp Reservation-based switching devices

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0332253A (ja) * 1989-06-22 1991-02-12 Digital Equip Corp <Dec> 高速網状接続特定区域内情報通信網のための経路指定装置及び方法

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4763247A (en) * 1984-12-26 1988-08-09 Vmei "Lenin" Multiprocessor system formed by microprocessor matrix
US4766534A (en) * 1986-10-16 1988-08-23 American Telephone And Telegraph Company, At&T Bell Laboratories Parallel processing network and method
JPH01126760A (ja) * 1987-11-11 1989-05-18 Toshiba Corp 並列計算機システム
JPH0291755A (ja) * 1988-09-29 1990-03-30 Toshiba Corp メッセージ通信方式
JP3072646B2 (ja) * 1989-03-20 2000-07-31 富士通株式会社 並列計算機間通信制御方式
WO1992003792A1 (en) * 1990-08-10 1992-03-05 Syracuse University Method and apparatus for routing and partitioning a multistage interconnection network and for determining network passability
EP0471256A3 (en) * 1990-08-10 1993-08-04 Hitachi, Ltd. Atm switch and atm multiplexer
CA2048717A1 (en) * 1990-08-17 1992-02-18 Tsutomu Tanaka Growable interconnect fabric cell switch module
US5224100A (en) * 1991-05-09 1993-06-29 David Sarnoff Research Center, Inc. Routing technique for a hierarchical interprocessor-communication network between massively-parallel processors
US5313649A (en) * 1991-05-28 1994-05-17 International Business Machines Corporation Switch queue structure for one-network parallel processor systems

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0332253A (ja) * 1989-06-22 1991-02-12 Digital Equip Corp <Dec> 高速網状接続特定区域内情報通信網のための経路指定装置及び方法

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7203816B2 (en) 2001-03-01 2007-04-10 Semiconductor Technology Academic Research Center Multi-processor system apparatus allowing a compiler to conduct a static scheduling process over a large scale system of processors and memory modules
JP2006236362A (ja) * 2006-03-13 2006-09-07 Handotai Rikougaku Kenkyu Center:Kk マルチプロセッサシステム装置
US11855913B2 (en) 2018-10-31 2023-12-26 Hewlett Packard Enterprise Development Lp Hierarchical switching device with deadlockable storage and storage partitions

Also Published As

Publication number Publication date
JP2817770B2 (ja) 1998-10-30
US5453978A (en) 1995-09-26
EP0676703A3 (en) 1996-02-07
EP0676703B1 (en) 2000-09-13
EP0676703A2 (en) 1995-10-11
DE69518782D1 (de) 2000-10-19

Similar Documents

Publication Publication Date Title
JPH07282018A (ja) パケットの経路指定デッドロック回避方法及び装置
US5812549A (en) Route restrictions for deadlock free routing with increased bandwidth in a multi-stage cross point packet switch
US5781546A (en) Route restrictions for deadlock free routing with increased bandwidth in a multi-stage cross point packet switch
US6847647B1 (en) Method and apparatus for distributing traffic over multiple switched fiber channel routes
KR100219350B1 (ko) 분산된 노드 사이 스위칭과 분리된 데이터/제어 메시지 처리를 갖는 다중 노드 네트워크
US5701416A (en) Adaptive routing mechanism for torus interconnection network
US5175733A (en) Adaptive message routing for multi-dimensional networks
US5898826A (en) Method and apparatus for deadlock-free routing around an unusable routing component in an N-dimensional network
EP0197103B1 (en) Load balancing for packet switching nodes
US6031835A (en) Method for deadlock free and and reliable routing in a packet switched network
US6065063A (en) Deadlock avoidance method in a computer network
CN1004965B (zh) 电信网络和方法
US20130242731A1 (en) Deadlock prevention in direct networks of arbitrary topology
JPS61214694A (ja) データ伝送のスイッチング装置
EP0448049B1 (en) Packet transfer regulating apparatus
KR20020015691A (ko) 플릿 캐쉬 방식의 패브릭 라우터
JP2000013408A (ja) 交換システム
EP0653866B1 (en) Resolution of race conditions in cascaded switches
JP3950048B2 (ja) 複数の制御回線を用いた多重最小論理網においてスループットを増大させる拡張可能な装置および方法
CA2152637A1 (en) Network for Transferring Consecutive Packets Between Processor and Memory with a Reduced Blocking Time
US6389017B1 (en) Resource scheduling algorithm in packet switched networks with multiple alternate links
Flich et al. Improving the performance of regular networks with source routing
JP2535874B2 (ja) パケット交換網のル−ティング制御方式
Cherkasova et al. Designing fibre channel fabrics
KR102853775B1 (ko) 비정형 토폴로지 기반 네트워크 온 칩(NoC)의 멀티캐스트 라우팅 방법 및 장치

Legal Events

Date Code Title Description
LAPS Cancellation because of no payment of annual fees