JPH0669929A

JPH0669929A - メッセージ経路指定方法及び装置

Info

Publication number: JPH0669929A
Application number: JP5106617A
Authority: JP
Inventors: Ian D Judd; イアン・ダビッド・ジュド; Reginald Beer; レジナルド・ビーア
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1992-06-23
Filing date: 1993-05-07
Publication date: 1994-03-11
Anticipated expiration: 2011-10-02
Also published as: GB2268374A; EP0580281B1; CA2095053C; DE69331868T2; CA2095053A1; EP0580281A3; DE69331868D1; US5465251A; EP0580281A2; GB9213240D0; JP2539155B2

Abstract

(57)【要約】【目的】ソース・ノードから宛先ノードに送られるメッ
セージの、移動すべき経路を定める、経路アドレスを含
むネットワーク・アドレス指定方式を提供すること。【構成】各ノードで、経路アドレスが所定の値と比較さ
れ、該アドレスと所定の値とが異なると判定されると、
ノードはメッセージを次のノードに伝送する前にアドレ
スを変更する。最低限３つのポートを有するスイッチ・
ノードでは、出力ポートの識別が経路アドレスから決定
され、当該出力ポートからメッセージを送出する前に該
アドレスの部分が削除される。最低限１つの開始機能ノ
ードが定義されるネットワークを形成する方法も記述さ
れ、開始機能ノードは照会メッセージを隣接するノード
に出し、隣接するノードは、そのノードで実現される作
動可能なポートの番号の詳細を返答、開始機能ノード
は、隣接するノード上の作動可能なポートに接続される
ノードに、アドレス指定された照会メッセージを出す。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はネットワーク・アドレス
指定、より詳しくは相互接続されたノードのネットワー
クでメッセージを経路指定する方法及び装置に関する。

【０００２】

【従来の技術】ネットワーク内の相互接続されたノード
の間でデータを伝送するために種々の異なるタイプのネ
ットワーク構成が提案され使用されている。例えば、ロ
ーカル・エリア・ネットワーク(LAN) は通常１つの施設内
に分散されているコンピュータに基づいた幾つかの装置
を備える。LAN は大抵は３つの基本的なトポロジー、即
ち星、バス及びリング型の１つで配列される。フリッジ
の形式のスイッチ即ち経路指定機能(router)により幾つ
かの異なるLAN を相互接続することによって、より複雑
なネットワーク形成が可能である。

【０００３】ネットワーク内でメッセージの形式のデー
タ及びコマンドが１つのノードから別のノードに転送さ
れる方法を定義する幾つかの異なるプロトコルがある。
大抵のネットワーク・プロトコルでは、ノード間でメッ
セージを経路指定する通常の方法は、メッセージの一部
分として宛先ノードのアドレスを指定する見出し情報及
び、多くの場合、メッセージを生成するノードのアドレ
ス (ソース・アドレス) を含むことである。見出しで指
定されたアドレスは、ネットワークが形成されるときノ
ードに割当てられている固有アドレスである。あるネッ
トワーク方式では、スイッチにより特定のノードに１つ
の値を割当てることを必要とする。ある形式のスイッチ
を介して相互接続された幾つかのリング・ネットワーク
を含むネットワークでは、一般にアドレス情報は目標ネ
ットワーク及び目標ネットワーク内の宛先ノードを識別
する２つの成分を有する。

【０００４】ネットワークを介してソース・ノードから
宛先にメッセージが送られるとき、アドレスが電源投入
時の当該ノードに割当てられた固有アドレスと一致する
かどうかを判定するために、メッセージを受信する各ノ
ードが宛先アドレス情報を処理する。もし一致がなけれ
ば、ノードは該メッセージを次の (ダウンストリーム
の) ノードに転送し、次のノードは同じ方法でアドレス
情報を処理する。リング構成では、一般に全ての構成ノ
ードは二重ポート化されるので、それらのノードはどの
出力経路でメッセージが転送されるべきかを判定するこ
とを要求されない。しかしながら、他のトポロジーで
は、成分ノードが単一ポート、二重ポート、又は３以上
のポートを含むスイッチ・ノードである場合があり、ス
イッチ・ノードは経路指定ハードウェアを含み、任意の
特定のメッセージのための出力ポートの一致を判定する
必要がある。ある経路指定方式では、出力ノードを決定
するために、スイッチはメッセージ内の宛先アドレスを
テーブルに含まれたアドレスのリストと比較する。

【０００５】

【発明が解決しようとする課題】従来の技術の経路指定
方法には幾つかの固有の欠点がある。第一に、各ノー
ド、特にスイッチ・ノードで必要とする経路指定ハード
ウェアは複雑であるとともに電源投入時に絶対ノード・
アドレスを割当てることも必要である。

【０００６】本発明の目的は、従来のアドレス指定方式
を改善し、複数の相互接続されたノードを有するネット
ワークでソース・ノードから宛先ノードにメッセージを
経路指定するために、ネットワークによる経路を指定す
る経路アドレス値を含む、宛先ノードに運ぶことになっ
ているメッセージをソース・ノードから出すステップ
と、ソース・ノードに接続されたノードでメッセージを
受信するステップと、経路アドレス値の所定の部分が所
定の値に対応するかどうかを判定するステップと、もし
対応すれば、そのメッセージを受け入れ、さもなけれ
ば、経路アドレス値を変更し、変更された経路アドレス
値を含むメッセージを次のノードに転送するステップ
と、メッセージが宛先ノードに達している時点で経路ア
ドレス値が所定の値と対応するまで前記受信、判定及び
転送するステップを続けるステップとを含む方法を提供
することにある。

【０００７】

【課題を解決するための手段】このように、簡単な経路
指定方法が提供されるので、メッセージで用いられる経
路アドレスは、経路アドレスの部分を検査し、その部分
を所定の値と比較することにより、各ノードが簡単な経
路決定を行なうことを可能にする。良好な経路指定方法
では、ネットワーク内の全てのノードの所定の値が０で
ある。このように、各ノードでは極めて簡単な経路指定
ハードウェアが保持される。

【０００８】本発明の方法の使用が有利であるネットワ
ークのタイプは、ストリング、ループ又は星型に配列し
うる単一ポート・ノードと二重ポート・ノードの混合で
構成され、かつネットワークの種々のストリング又はル
ープ部分の間の相互接続を提供するために幾つかのスイ
ッチ・ノードも用いられる。

【０００９】良好な方法では、経路アドレスが所定の値
に対応しないことを判定する際に、二重ポート・ノード
は、経路アドレスの部分を、ダウンストリーム・ノード
に引渡す前に減分する。次のノードは、もしそれも二重
ポート・ノードであれば、経路アドレスを同じ方法で処
理する。従って、宛先ノードは、０値を有する経路アド
レスを含むメッセージを受信するノードである。このよ
うに、相互接続された二重ポート・ノードのストリング
又はループは ^ホップ・カウント^(hop count)を減分す
ることによりアドレス指定される。これは簡単かつ効率
的であり、メッセージ・フレームが無限にループを循環
する可能性はない。

【００１０】良好な方法では、メッセージが少なくとも
３つのポートの１つを介してスイッチ・ノードに入る
と、メッセージの経路アドレス成分が分析され、当該ノ
ードが宛先ノードであるかどうかを判定する。もし宛先
ノードでなければ、スイッチ・ノードは、経路アドレス
の所定の部分から、メッセージを次のノードに転送する
ときに経由することになっている出力ノードの一致を判
定する。経路アドレスは、該経路アドレスの所定の部分
を削除することにより、転送する前に変更される。そし
て次のノードは変更された経路アドレスを含むメッセー
ジを処理する。

【００１１】本発明の経路指定方法のもう１つの利点は
経路アドレスのモジュール方式の性質から生じる。小さ
なネットワークはしばしば単一数字(digit) 経路アドレ
スを用いることによりアドレス指定できる。しかしなが
ら、経路アドレスは数千のノードを有する非常に大きな
スイッチ式ネットワークをサポートするために拡張する
こともできる。

【００１２】良好な経路指定方法では、経路アドレスは
チャネル・アドレスをも含むメッセージ・アドレス・フ
ィールドの部分を形成する。この経路は宛先ノードへの
経路を指定し、チャネルは宛先ノード内の受信プロセス
を選択する。メッセージを受信するように予め１つのチ
ャネル・アドレスが都合よく決められ、宛先ノードによ
り全ての他のチャネルがインバウンド・データ転送に動
的に割当てられる。１つの４ビット数字が最大15の同時
インバウンド転送まで可能になるように、チャネル・ア
ドレスがモジュール化される。しかしながら、ノード毎
に数千の同時インバウンド転送を可能にするようにアド
レスを拡張することができる。

【００１３】本発明のもう１つの状況では、複数の相互
接続されたノードを有するネットワークを形成する方法
が提供される。前記方法は、ネットワーク内で１つ以上
の開始機能ノードを定義するステップと、照会メッセー
ジ(query-message) に含まれた経路アドレスで指定され
た経路を介して各開始機能ノードから隣接ノードに照会
メッセージを送るステップと、メッセージを受信した際
に、隣接ノードは回答メッセージに応答して該隣接ノー
ドにより設置されたポートの数を指定するステップと、
照会メッセージ経路アドレスで指定された経路を介し
て、開始機能ノードから、隣接するノードに設置された
ポートと接続された各ノードに、形成メッセージを送る
ステップと、開始機能ノードに接続されたノードの各々
の経路アドレス、及び開始機能ノード内のコンフィギュ
レーションテーブル内の各ノードにより実現された関連
ポートの数を記憶するステップとを含む。

【００１４】この形成手法を用いて、開始機能はネット
ワーク内を一度に１リンクずつウォークスルー(walk th
rough)する。開始機能からの照会メッセージによりアド
レス指定されたノードの各々は、アドレス指定されたノ
ードに設置された作動可能なポートの番号を含む回答メ
ッセージを送る。そして開始機能は第１のノードにある
作動可能なポートに接続されたノードの各々に照会メッ
セージを送る。開始機能がネットワーク全体をウォーク
(walk)し終わるまで、このプロセスが続く。従って、本
発明による形成手法は、従来の技術のSCSIバスによる場
合のように、アドレス・スイッチを手動でセットする必
要なしにネットワークを形成することができる。

【００１５】良好な形成手法では、開始機能は(循環ネ
ットワークで起きるように)それが前に訪れたノードへ
再びウォークした時点を容易に検出できるべきである。
これはネットワーク内の各スイッチ・ノードに固有識別
番号(ID)を割当てることにより達成される。スイッチ・
ノードが照会メッセージによりアドレス指定されると、
該スイッチ・ノードはIDならびに回答メッセージ内の作
動可能なポートの数を返送する。開始機能はIDを対応す
る経路アドレスとともに記憶し、同じスイッチ・ノード
が後の照会メッセージに応答するとき、開始機能はIDを
既にテーブルに含まれたものと比較するので、該開始機
能が循環ネットワークをウォークし回ったと判定するこ
とができる。良好な形成方法では、各開始機能もIDを割
当てられる。

【００１６】

【実施例】符号化されていないデータ・バイト内のビッ
トは左から右に7から0の番号を付与され、ビット7が最
上位ビットである。整数の最上位バイトは1である。ビ
ット値は、例えば1bとして表示され、16進値は、例えば
A2h として表示される。

【００１７】本発明で用いられるアドレス指定方式は接
続に従って３つのタイプのノードを識別する。これらは
単一ポート・ノード、二重ポート・ノード及びスイッチ
である(3〜16ポート)。本発明を用いるネットワークで
は、これらのノードは一般に電子装置、例えばコンピュ
ータ、印刷装置、記憶装置等である。

【００１８】図１は直列リンク12,14にそれぞれ接続さ
れた２つのポート16,18を備える二重ポート・ノード10
を示す。また、ポート16,18 をノード機能22に接続する
３ウェイ経路指定機能20も備えられる。アドレス・フィ
ールドにより、経路指定機能20はインバウンド・フレー
ムをノード自身に送るか又は別のポートのアウトバウン
ド回線に送る。ノードは、フレームを生成したいとき、
経路指定機能20に対し指定ポートで該フレームを送信す
るように指示する。 (特定のコマンドに関する全てのメ
ッセージ及びデータ・フレームは同じポートを用い
る。)

【００１９】図１４はＮポート・ノードの主要な機能の
構成装置をより詳細に示す。各ポートは直列リンクのイ
ンバウンド及びアウトバウンド部分を含むポート・ロジ
ック400,420 を備える。ポート１では、インバウンド側
は、インバウンド直列リンクを介して受信されたデータ
を、ビット直列データから (例えば１バイト幅の) ビッ
ト並列データに変換する、非直列化器及び復号器ロジッ
ク410 を含む。非直列化器はクロック回復、ビット同期
及びバイト同期を実行することもできる。これらの機能
は本発明の理解に不可欠なものではないので、これ以上
の説明は行なわない。到来データは復号を必要とするこ
ともある。例えば、リンク上では１バイトが10ビット文
字として表示されることがある。ロジック410 はCRC及
びFNS検査ロジック414に接続される。このロジックは、
到来データとともに含まれたCRC情報を検査するととも
に、到来フレームのフレーム・シーケンス番号(FSN) が
予想された値に対応することも検査する。このように、
ノードは、到来するデータのフレームが正しいシーケン
スで受信されていることを検査できる。アウトバウンド
側は、CRC及びFSN生成ロジック416 ならびに直列化及び
符号化ロジック412 を含み、その機能はインバウンド側
のロジック410及び414の機能の当然の結果である。ポー
トＮは対応するロジック422,424,426及び428を備える。

【００２０】ポート・ロジック400及び420に接続される
のは、１つのポートを介してノードに到着するデータの
フレームを該ノード内の異なるポート又は宛先プロセス
に経路指定する機能を有する経路指定ロジック450 であ
る。経路指定ロジック450 に備えられるのは、後に説明
するように各フレーム内のアドレス・フィールドを解釈
し、それを１ポート・ノード、２ポート・ノード又はス
イッチ・ノードの規則により更新するアドレス解釈及び
更新ロジック452 である。このロジックはＮ個の要求信
号を生成する。これらの信号の各々は、バンク(bank)に
あるラッチをセットするか又は他のポートの１つにある
ラッチ (例えばポートＮにある要求ラッチ468)を要求す
るためにライン460 を介して送られ、当該ポートに該フ
レームを転送するように要求する。フレーム・バッファ
454 はアドレス解釈及び更新ロジック452 に接続され、
一時的にフレームを保持するために用いられる。このバ
ッファは該フレーム内のバイトの合計数のカウント、制
御フィールド、更新されたアドレス・フィールド及びデ
ータ・フィールドを記憶する。これらの種々のフィール
ドを含むフレームのフォーマットの説明は以下に記述す
る。図１４には１つのフレーム・バッファだけが示され
ている。実際には、連続的なデータ転送を持続させるた
めにポートは普通少なくとも２つのフレーム・バッファ
を備える。これは別のバッファの転送中に１つのバッフ
ァがリンクから満たされることを可能にする。更に経路
指定ロジック450 に含まれるのは、マルチプレクサ456
及び要求ラッチ458 のバンクである。動作中、マルチプ
レクサ456 は、別のポートからのフレーム・バッファ、
例えばポートＮのフレーム・バッファ464 からポート１
を介して転送されることになっているフレームを選択す
る。要求ラッチ458 のバンクは、ポート１からの転送を
待っているフレームを他のポート内のどのフレーム・バ
ッファが含むかをマルチプレクサ456 に対して表示す
る。もし２つ以上のラッチが同時にセットされれば、優
先順位循環アルゴリズムを用いて特定の要求のサービス
を選択することができる。

【００２１】経路指定ロジック450 はポート１に関して
説明したものに対応するロジック装置を含む。アドレス
解釈及び更新ロジック462 はフレームのアドレス・フィ
ールドを解釈し、もし必要ならアドレスを更新する。フ
レーム・バッファ464 はフレームの一時記憶装置を提供
する。マルチプレクサ466 及び要求ラッチ468 はポート
Ｎを介してのフレームの転送を制御する。更に経路指定
ロジック450 には、フレーム・バッファ 480、マルチプ
レクサ482 及び要求ラッチ484 が含まれる。これらのロ
ジック装置は、ノード機能、例えばノード内の宛先プロ
セスによりこのノードにアドレス指定されるデータの転
送に用いられる。例えば、これはデータを印刷する印刷
装置でのプロセスか又は到来データをディスクに書込む
ディスク・ファイル内のプロセスであるかも知れない。
動作中、ノード内のプロセスを宛先とする、ポート１に
より受信されたフレームについて、アドレス解釈及び更
新ロジック452 は要求ラッチ484 のバンク内のラッチを
セットする要求信号を生成する。セットされたラッチ
は、バッファ454 に保持されたフレームがノード内の宛
先プロセスに転送されることになっていることを、マル
チプレクサ482 に通知する。該フレームはバッファ454
からバッファ480 に転送される。

【００２２】ここで、このようなノードを用いうるネッ
トワークに戻る。下記は実現しうるネットワークのタイ
プの例である。 (1) 専用接続図２は２つの単一ポート・ノード30及び32の間の最も簡
単な専用接続のケースを示す。 (2) ストリング図３はストリングとして知られている二重ポート・ノー
ド36,38,40,42 の線形ネットワークを示す。ストリング
のどちらかの先端のノードは単一ポート・ノード34、１
つの接続されないポートを有する二重ポート・ノード又
はスイッチ・ノードとなりうる。 (3) ループループは図４に示すように二重ポート・ノード44,45,4
6,47,48のみを含む循環ネットワークである。任意の１
つのノードが故障しても残りのノードの任意の対の間の
通信を不通にしえないので、ループはストリングよりも
良好な使用可能度を与える。他のノードの間の通信を妨
げずに、ノードをループに挿入し、又はノードをループ
から取り除くこともできる。 (4) スイッチ図５は２つのスイッチ106,114、３つのストリング100,1
02,104;108,110;116,118、及びスイッチ114にノード118
を連結する循環経路を含む複合ネットワークを示す。ス
イッチは多数のノードの相互接続を可能にする。それら
は障害許容度を達成するために代替経路が与えられるこ
とも可能にする。

【００２３】直列リンクの反対の端にある２つのポート
は、フレームと呼ばれる単位で通信する。フレームはフ
ラグとして知られる特別なプロトコル文字により各端で
区切られた少なくとも４データ・バイトのシーケンスを
含む。フレームは図６に示すような３フィールド又は４
フィールドのシーケンスに分割される。・制御フィールド: 制御フィールドは１バイトで、常に
存在する。制御フィールドはフレーム・タイプ及びシー
ケンス番号を指示する。アドレス指定方式^Ｂ^の場合、
後で説明するように、制御フィールドは数字削除(Digit
_delete)フラグを含む。・アドレス・フィールド: アドレス・フィールドは１〜
６バイトで、常に存在する。後に説明するように、この
フィールドはフレームを経路指定するために用いられ
る。・データ・フィールド: データ・フィールドは128 バイ
トで、随時存在する。後に説明する形成メッセージを除
き、データ・フィールドの内容は本発明の理解には関係
ない。・CRCフィールド: CRCフィールドは２バイトで、常に存
在する。このフィールドは制御、アドレス及びデータ・
フィールドの標準循環冗長検査である。これ以上の説明
は行なわない。

【００２４】アドレス及びデータ・フィールドの最大の
長さは、ネットワーク・サイズ、通信効率及び実現費用
の間の均衡をとるように選択される。

【００２５】フレームのアドレス・フィールドは第１
に、該フレームを、選択された経路を介して宛先ノード
に経路指定するために用いられる。経路アドレスはソー
ス・ノードに地理的に関連している。これは経路指定ハ
ードウェアを簡略化し、電源投入時に絶対ノード・アド
レスを割当てる必要性を回避する。

【００２６】アドレス・フィールドの第２の機能は宛先
ノード内でチャネルを選択することである。チャネルは
メッセージを受信するか又は１つのデータ転送を受信す
る機能を含む。あらゆるノードはメッセージを受信する
チャネルを提供しなければならない。大部分のノード
は、少なくとも１つの、データを受信するチャネルも提
供する。それらは任意の数のインバウンド・データ同時
転送をサポートする追加のチャネルを実現することがで
きる。実際には、装置は１つのデータ・チャネルのみを
サポートしうるが、アダプタ又は制御装置は一般に幾つ
かのデータ・チャネルを提供する。

【００２７】アパー・レベル (upper-level)・プロトコ
ルは、ソース・ノードと宛先ノードの間でメッセージ・
フレームを交換することにより、データ転送を開始す
る。宛先ノードは、データ・フレームを受信するチャネ
ルを割振り、該ノードが現在受け入れできるバイト数を
指示する。

【００２８】従って、フレーム・アドレス・フィールド
は、ネットワークの複雑さ及び宛先フィールドにより実
現されたチャネルの数により１バイト乃至６バイトを含
む。アドレス・フィールドは制御フィールドに続く最初
のバイトで始まる。それは２つ又は３つの成分を含み、
各成分は、図７に示すように、少なくとも１つの４ビッ
ト数字に分割される。・経路: この成分はフレームを宛先ノードへ経路指定す
る。各数字はソース・ノードから宛先ノードへの経路に
あるストリング又はスイッチに対応する。二重ポート・
ノードによりフレームが転送されると、経路にある最初
の１つ又は２つの数字が削除される。これは次の経路指
定の決定のためにアドレスの残りの部分を明らかにす
る。このプロセスは後にずっと詳細に説明する。・チャネル: この成分はフレームを宛先ノード内に振向
ける。後に説明するように、解釈は使用されるアドレス
指定方式(^Ａ^又は^Ｂ^)による。１つのチャネルがメッ
セージを受信するように予め定義され、残りのチャネル
はインバウンド・データ転送に使用可能である。一般に
データ・チャネルはアパー・レベル・プロトコルにより
動的に割振られる。・埋込み (pad): アドレス・フィールドを生成するのに
必要なバイト数を表わす１つの数字である。宛先ノード
にチャネルが割振られているのでアドレス指定するのに
必要なビット数はすでに判明しており、この値は通常は
重要ではない。

【００２９】下記のセクションで記述されるように、ノ
ードの各タイプは異なる規則を用いてインバウンド・フ
レームのアドレス・フィールドを解釈する。機能的に等
しい２つの異なる方式(Ａ及びＢ)が記述される。ハード
ウェアで実現するためには方式^Ａ^の方がいくらか簡単
であるが、方式^Ｂ^の方がコンパクトなアドレス・フィ
ールドを有する傾向がある。どちらの方式も図１４に関
連して記述されているようなロジックを用いて実現され
る。

【００３０】[方式Ａ]この方式では、スイッチの各々は
それがフレームを転送するとき経路アドレスの最初のバ
イトを削除する。

【００３１】メッセージを受信する全てのノードについ
て、アドレス指定されたチャネルが１つの数字0hにより
予め定義される。他の全てのチャネルはデータ転送に使
用可能である。従って、単一数字のチャネル・アドレス
では最大15のデータ・チャネルまで可能である。２つの
数字のチャネル・アドレスでは最大240 のデータ・チャ
ネルまで可能であり、以下同様である。

【００３２】下記の全てのケースで、^Hi_digit^(上位
数字)はアドレス・フィールドにある最初のバイトのビ
ット7〜4を参照し、^Lo_digit^(下位数字)はビット3〜0
を参照する。

【００３３】下記の異なるタイプのノードはアドレス・
フィールドを異なる方法で解釈する。既に説明したよう
に、図１４におけるアドレス解釈及び交換ロジック452
又は462 がこのプロセスを実行する。・単一ポート・ノード: このノードは下記のようにアド
レス・フィールドを解釈する。 If Hi_digit = 0h then Do; フレームを受け入れる;アドレス・フィールドの残りを
チャネルと解釈する; End; Else フレームを拒絶する;

【００３４】単一ポート・ノード内のポートはノード照
会回答メッセージ(Query-node-reply-message)による参
照のために番号^０^を付与される。その詳細については
後で説明する。・二重ポート・ノード: このノードは下記のようにアド
レス・フィールドを解釈する。 If Hi_digit = 0h then Do; フレームを受け入れる;アドレス・フィールドの残りを
チャネルと解釈する; End; Else Do; Hi_digitを減分する;他のポートでフレームを転送する; End;

【００３５】二重ポート・ノードは、アドレス・フィー
ルドの最初の数字を、横切られるノードの ^hop-count^
(ホップ・カウント)として扱う。ループ・カウントが０
になるまで該ループ・カウントを減分することにより、
ストリング又はループ内の宛先ノードが突き止められ
る。方式Ａを用いて、任意の２つのノードの間の通信を
可能にするために、ストリングで形成しうるノードの最
大数は、終了(end) ノードを含めて17である。これはス
トリング内の全てのノードをアドレス指定するために１
つの16進数字を使用するためである。例えば、これは１
つのアダプタ・ポートに16の装置を接続することを可能
にする。

【００３６】二重ポート・ノードの２つのポートは、ノ
ード照会回答メッセージにより参照するために番号^０^
及び^１^を付与される。その詳細は後に説明する。スイッチ・ノード: このノードはアドレス・フィールド
を下記のように解釈する。 If Hi_digit = 0h then Do; If Lo_digit = 0h then Do; フレームを受け入れる;アドレス・フィールドの残りを
チャネルと解釈する; End; Else Do; Output_port(出力ポート) = (Input_port(入力ポート)
+ Lo_digit) Modulo(モジューロ) 16を選択する; 最初のアドレス・バイトを削除する;フレームをOutput_
portを介して転送する; End; End; Else フレームを拒絶する;

【００３７】実施例では ^0^から始まる番号が順次にス
イッチ・ポートに付与される。 (ポート番号は一定であ
るが、フレーム・アドレス指定は入力ポートによって変
動する。)実際には、全ての開始機能は、作動可能なノ
ード及びそれらの経路アドレスを発見するために形成プ
ロセスを実行する必要がある。スイッチはフレームを受
信したそのポートから該フレームを転送させることはで
きない。

【００３８】ここで、方式Ａを用いるネットワークの例
を、図５に示すものに対応するネットワーク・トポロジ
ーを示す図８に関連して説明する。ブロックに付与され
た番号は (想定された) ポート番号である。説明の都合
のために、 ^開始機能^ と表示された部分から、最も近
いポートから時計回りにポート番号が付与される。各ブ
ロック内の番号はその開始機能に関連する当該ノードの
16進数の経路アドレスである。循環経路上の二重ポート
・アドレス216,218 は開始機能で用いられた経路により
２つのアドレスを有する。

【００３９】開始機能ノード200 から二重ポート・ノー
ド210 へのメッセージの経路指定を例にとれば、アドレ
ス・フィールドで指定された経路アドレスは221hを含
む。メッセージを受信すると、ノード202 は前に定義さ
れた二重ポート・アルゴリズムに従って上位数字が0hと
等しくないと判定し、従って上位数字を2hから1hに減分
する。同様に、二重ポート・ノード204 は上位数字1hを
0hに減分し、メッセージをスイッチ・ノード206 に転送
する。スイッチ206 は上位数字(0h)及び下位数字(2h)の
両者を検査し、上位及び下位数字の双方がともに 0h に
等しくないと判定し、そして前に定義されたスイッチ・
アルゴリズムに従って、ポートのどちらにメッセージを
転送すべきかを決定する。入力ポートは番号０を付与さ
れ、従って(入力ポート＋下位数字) モジューロ16が２
に等しいと判定される。ポート２からメッセージを転送
する前に、スイッチ206 は最初のアドレス・バイトを削
除し、1hの経路アドレスを残す。ノード208 はアドレス
を検査し、経路アドレス値を0hに減分する。次にノード
210 は経路アドレスを処理し、それが宛先ノードである
と判定することにより、そのメッセージを受け入れる。

【００４０】[方式Ｂ]この方式では、スイッチの各々は
経路アドレスの最初の１つ又は２つの数字を削除する。
これは、フレーム制御フィールドで数字削除フラグを定
義することにより達成される。数字削除をセットするこ
とにより最初の数字が論理的に削除される。数字削除を
クリア(clear) し、アドレス・フィールドの最初のバイ
トを物理的に削除することにより、二番目の数字が削除
される。そして数字削除をセットすることにより三番目
の数字が論理的に削除される。以下同様である。

【００４１】数字0hで始まる全てのチャネルは無効であ
る。１つの数字1hによりアドレス指定されたチャネル
は、全てのノードがメッセージを受信するように予め定
義される。他の全てのチャネルはデータ転送に使用可能
である。従って、単一数字チャネル・アドレスは最大14
のデータ・チャネルまで可能にする。２つの数字は最大
244 のデータ・チャネルまで可能にする。以下同様であ
る。以下の全ての場合に、^次の数字^(next_digit)は、
制御フィールド内の数字削除、及び前の規則により削除
されている数字を考慮に入れた後に、現在のアドレス・
フィールド内の次の活動状態の数字を指す。・単一ポート・ノード: このノードはアドレス・フィー
ルドを下記のように解釈する。フレームを受け入れる; If Next_digit = 0h then Next_digitを削除する; If (New) Next_digit((新たな)次の数字) = 0h then Ne
xt_digitを削除する; アドレス・フィールドの残りをチャネルと解釈する;

【００４２】単一ポート・ノードがストリングの末尾に
あるとき、先導する１つの０を削除する必要がある。形
成プロセス中に単一ポート・ノードがノード照会メッセ
ージを受信すると、先導する２つの０を削除する必要が
ある。・二重ポート・ノード: このノードはアドレス・フィー
ルドを下記のように解釈する。 If Next_digit = 0h then Do; フレームを受け入れる;Next_digitを放棄する; If (New) Next_digit = 0h then Next_digitを放棄す
る; アドレス・フィールドの残りをチャネルと解釈する; End; Else Do; Next_digitを減分する;他のポートでフレームを転送す
る; End;

【００４３】形成プロセス中に二重ポート・ノードがノ
ード照会メッセージを受信するとき、１つの０がチャネ
ル・アドレス前に削除される必要がある。・スイッチ・ノード: このタイプのノードはアドレス・
フィールドを下記のように解釈する。 If Next_digit = 0h then Next_digitを削除する; If (New) Next_digit = 0h then Do; フレームを受け入れる;Next_digitを削除する; アドレス・フィールドの残りをチャネルと解釈する; End; Else Do; Output_port = (Input_port + (new) Next_digit) Modu
lo 16を選択する;(new) Next_digitを削除する;選択さ
れたポートを介してフレームを転送する; End;

【００４４】ストリングの端にスイッチがあるとき、先
導する１つの０が削除される必要がある。

【００４５】次に、アドレス指定方式Ｂを用いるネット
ワークの例を図９に関連して説明する。ノード300 から
ノード310 へのメッセージの経路指定を例にとると、メ
ッセージ・フレーム・アドレス・フィールド内の経路ア
ドレスは221hである。ノード302 がNext_digitを1hに減
分し、121hの経路アドレスを含むメッセージをノード30
4 に転送する。ノード304 で、Next_digitが0hに減分さ
れ、021hの経路アドレスを含むメッセージがスイッチ・
ノード306 に転送される。ノード306 はNext_digitを削
除し、出力ポートをポート２として計算する。(新たな)
Next_digitが削除され、1hの経路アドレスを含むメッセ
ージがノード308 に転送される。次いでノード308 はNe
xt_digitを0hに減分する。ノード310 は、メッセージを
受信すると、該ノードが宛先ノードであると判定してメ
ッセージを受け入れ、該メッセージが指向しているノー
ド内のチャネル・アドレスを決定する。

【００４６】方式Ｂにより、図８の対応するノード214,
216及び218の５ビット数字経路アドレスと対照的に、ノ
ード314,316及び318が４ビット数字経路アドレスを用い
てアドレス指定可能である。従って、方式Ｂを用いるネ
ットワークでは、通常は数字の数を少なくしてノードを
アドレス指定する必要がある。

【００４７】次に、ネットワークを形成するために用い
る手法について説明する。ネットワークを介して送られ
たコマンド毎に、ノードは(1) 開始機能、即ちコマンド
を出したノード、又は(2) 目標、即ちコマンドを受信し
たノードに分類される。

【００４８】開始機能になる可能性のあるノードの各々
は、ネットワーク内に存在する他のノード及びそれらの
経路アドレスを決定するために形成プロセスを実行する
必要がある。トランスポート層はノード照会(Query_nod
e)及び形成をサポートするノード照会回答(Query_node_
reply)を定義する。アパー・レベル・プロトコルは装置
タイプ及び一連番号のような重要製品データを検索する
ことが予想される。例えば、SCSIは照会(Inquiry) コマ
ンドを与える。

【００４９】ノードが製造されると、全てのスイッチ及
び開始機能はIDを割当てなければならない。IDは一般に
EPROM に記憶され、製造業者により割当てられた４バイ
トのベンダ(vendor)識別及びそれに続く４バイトのノー
ド識別を含む。スイッチ及び開始機能の識別は符号なし
の２進整数である。形成プロセス中に循環ネットワーク
を検出するためにIDが用いられる。

【００５０】形成プロセスでは、各開始機能はネットワ
ークを一度に１つのリンクずつウォークする。最初に開
始機能はその作動可能なポートの１つを選択し、隣接ノ
ードにノード照会メッセージを出す。隣接ノードはノー
ド照会回答を返送し、それが持っているポートの数とそ
のうちで作動可能なポートの数及び、作動可能なポート
のIDを表示する。開始機能はこの情報を対応する経路ア
ドレスと一緒にコンフィギュレーションテーブルに入れ
る。 (一般に、コンフィギュレーションテーブルはアパ
ー・レベル・プロトコルにより与えられた他の情報、例
えばSCSI照会コマンドからの装置タイプ及び一連番号も
含む。) そして開始機能は、それがネットワーク全体を
ウォークし終るまで、隣接ノードにある作動可能なポー
トの１つを介してノード照会を次々と出す。

【００５１】もしネットワークが循環型であれば、開始
機能は、それは前に訪れたノードを再びウォークした時
点を検出する必要がある。これは、スイッチ・ノード及
び他の開始機能から受信したIDを、コンフィギュレーシ
ョンテーブル内の前のエントリと比較することにより達
成することができる。

【００５２】もし作動できないポートをノードが持って
いれば、開始機能は形成中に当該リンクをウォークしよ
うとしない。 (これはエラーを生じるであろう。) もし
ポートがその後作動可能になれば、各開始機能は対応す
るノードからの非同期メッセージにより警告される。そ
して各開始機能は新たなリンクをウォークし、それが単
一ポート・ノード、作動可能ではない別のポートに出会
うか、又はそれが既知のIDを返送するまで、そのコンフ
ィギュレーションテーブルにノードを加える。

【００５３】各開始機能は、それが電源をオンにする
と、形成プロセスを完全に実行する必要がある。各開始
機能は、新たなリンクが作動可能になる結果としてそれ
が非同期メッセージを受信すると、形成プロセスを部分
的にも実行する必要がある。

【００５４】もしリンクが恒久的なエラー (例えば、リ
ンクが切断されている) に出会えば、当該リンクで接続
された２つのノードのうちの近い方からの非同期メッセ
ージにより各開始機能が警告される。そして各開始機能
はそのコンフィギュレーションテーブルからのエラーの
範囲外のノードへの経路を削除しなければならない。

【００５５】目標(例えば、装置)であるだけのノードは
形成プロセスを実行し又はコンフィギュレーションテー
ブルを構築する必要はない。該ノードは開始機能からの
ノード照会メッセージに応答するだけである。

【００５６】形成プロセスをサポートするために２つの
タイプのメッセージ、すなわちノード照会メッセージ及
びノード照会回答メッセージが定義される。

【００５７】形成プロセス中にノード照会メッセージが
開始機能から他のあらゆる作動可能なノードに送られ
る。宛先ノードはノード照会回答メッセージを返送す
る。この交換は経路の完全性を検査するための遠隔循環
(wrap)検査も可能にする。

【００５８】宛先ノードへのエントリで、ノード照会メ
ッセージのアドレス・フィールドに残るべき値は、方式
Ａでは0000h である。方式Ｂの場合、数字削除フラグを
考慮に入れた後、残るべきアドレス・フィールドは001h
+ (起こりうる埋込み数字)である。これは、ノードが
単一ポートであるか、二重ポートであるか又はスイッチ
・ノードであるかどうかに関係なく、メッセージが受け
入れられることを保証する。開始機能は、もし同じ目標
ノードへのいくつかの代替経路を用いようとするなら
ば、各経路を介していったんノード照会を出す必要があ
る。

【００５９】ノード照会メッセージは、図１０に示され
る２つの僅かに異なるフォーマットを有する。単一ポー
ト・ノード又は二重ポート・ノードがノード照会メッセ
ージを受信すると、フォーマット１は方式Ａでのみ認め
られる。他の全てのケースでは、フォーマット２が用い
られる。２つのフォーマットの成分は下記の通りであ
る。・メッセージ・コード(Message_code): これはメッセー
ジをノード照会メッセージと識別する。・埋込み: 方式Ａでは、単一ポート・ノード又は二重ポ
ート・ノードがアドレス・フィールドの最後のバイトを
メッセージ・コードと解釈するので、このバイトが生成
される。・タグ: この２バイト・フィールドがノード照会回答メ
ッセージで返送される。タグは開始機能によって割当て
られるので、当該開始機能からの現に活動状態のタグの
中の唯一のものでなければならない。・戻りアドレス: この４バイト・フィールドは、結果と
して生じるノード照会回答メッセージのアドレス・フィ
ールドに入れるべき値を指定する。それは、左位置合わ
せされ４バイトに埋込まれた経路及びチャネルを含む、
全アドレスを含む。方式Ａの場合、チャネルは0hであ
り、埋込みは０又は１以上のFhの数字である。方式Ｂの
場合、チャネルは1hであり、埋込みは０又は１以上の0h
の数字である。これは宛先ノードが重要な数字を決定す
ることを可能にする。・ID: この８バイト・フィールドは、ノード照会メッセ
ージを出した開始機能のIDを含む。

【００６０】もう１つのタイプのメッセージは、あらゆ
るノードがノード照会回答メッセージに応答して返送す
べきノード照会回答メッセージである。ノード照会回答
メッセージは、対応するノード照会メッセージを受信し
た同じポートに返送される。該回答メッセージは、アド
レス指定されたノードによって実現されたポートの全番
号、作動可能なポート及び現に使用中のポートを示す。
ポートは、それが遠隔ノードから信号を受信していると
き作動可能である。ノード照会回答メッセージの成分は
図１２に示す。・メッセージ・コード: このバイトはメッセージをノー
ド照会回答メッセージとして識別する。現在のポート(C
urrent_port)のビット7〜4はどのポートが現に使用中で
あるかを示す符号なしの２進整数を含む。全ポート(Tot
al_port)のビット3〜0は実現されたポートの数よりも１
少ない符号なしの２進整数を含む。・タグ: この２バイト・フィールドはノード照会メッセ
ージからコピーされる。タグはこの回答がどのノード照
会メッセージに対して生成されているかを識別する。・ポート・マスク (Port_mask): この16ビット・フィー
ルドはどのポートが現に作動可能であるかを示す。もし
ポート０が作動可能であれば左端のビットがセットされ
る。以下同様にセットされる。・アパー・レベル・プロトコル(ULP = Upper_level_pro
tocol): このバイトはノードと通信するアパー・レベル
・プロトコルを識別する。現に定義された唯一の値は ^
SCSI-2^ を表わす ^00^Xである。・開始機能(Init): これは、1bにセットされると、ノー
ドが開始機能であることを示す。・ID: ノードが開始機能又はスイッチである場合にの
み、この８バイト・フィールドが存在する。

【００６１】ノード照会回答フレーム内のアドレス・フ
ィールドは、対応するノード照会メッセージ内の戻りア
ドレスからコピーされる。しかしながら、完全な埋込み
バイトはどれも放棄されなければならない。

【００６２】種々の異なるアプリケーションで前述のネ
ットワーク・アドレス指定及び形成方式を用いることが
できる。その２つの例をここで説明する。他のタイプの
ネットワークで容易に本発明を用いうることが分かる。

【００６３】・パーソナルコンピュータ: 図１２に示す
ように、二重ポート装置のストリングはパーソナルコン
ピュータに入出力装置を接続するのに特に魅力的であ
る。一般にパーソナルコンピュータのシステム装置内に
あるアダプタ50はリンク51を介してディスク装置52に接
続される。そしてディスク装置52はリンク53を介してデ
ィスク装置54に接続される。ディスク装置54はリンク55
を介して印刷装置56に接続される。ストリングの使用は
装置当りの接続費用を少なくするとともにアダプタでの
配線の混雑を回避する。本発明の方法及び装置を用い
て、前記２つのディスク装置と印刷装置の各々における
経路指定ハードウェアが簡単なままに保持される。更
に、既に割当てられたアドレスをこれらの装置が持つ必
要はない。これは装置によっては、該装置がストリング
に付加されるとき、スイッチにより手動でアドレスを割
当てる必要性を回避する。より広い帯域幅又は一定の障
害許容度を与えるためにオプションとしてリンク57を設
けることによりループをクローズ(close) することがで
きる。

【００６４】・ファイル・サーバー (File server): フ
ァイル・サーバーのような共有システムでは、高い使用
可能度が重要である。このアプリケーションも二重ポー
ト・ディスク装置を必要とするが、ここでは第２のポー
トの主たる理由は、主要な接続経路での障害の場合にバ
ックアップ経路を提供することである。よって、実際に
は、全ての直列ディスク装置はたぶん二重ポート化され
る。ディスク・アレイに関連して、図１３に示すよう
に、二重ポート・ディスク装置は障害点が１つもない形
成を可能にする。この形成では、対のサーバー60及び62
が専用リンクを介して２つのスイッチ64及び66に接続さ
れ、二重ポート・ディスク装置68,70,72及び74の各ポー
トは前記スイッチの１つに接続される。各装置への専用
リンクの使用は、他の装置の動作に影響しない完全な同
時保守を可能にする。

【図面の簡単な説明】

【図１】本発明の手法を用いるネットワークに存在しう
るような二重ポート・ノードの主要な機能の構成装置を
示す図である。

【図２】相互接続された一対の単一ポート・ノードを含
むネットワークを示す図である。

【図３】相互接続された単一ポート・ノード及び二重ポ
ート・ノードのストリングを含むネットワーク構成を示
す図である。

【図４】ループ構成で相互接続された幾つかの二重ポー
ト・ノードを含むネットワークを示す図である。

【図５】単一ポート・ノード、二重ポート・ノード及び
スイッチ・ノードを含む、相互接続されたノードのネッ
トワークの例を示す図である。

【図６】ノード間の通信で用いるフレームのフォーマッ
トを示す図である。

【図７】図６のアドレス・フィールド成分のフォーマッ
トを示す図である。

【図８】本発明のアドレス指定方式の１つの実施例 (方
式Ａ) を用いるネットワークを示す図である。

【図９】本発明のアドレス指定方式の代替実施例 (方式
Ｂ) を用いるネットワークを示す図である。

【図１０】ネットワーク形成プロセスで用いるノード照
会メッセージの２つのフォーマットを示す図である。

【図１１】ネットワーク形成プロセスで用いるノード照
会回答メッセージのフォーマットを示す図である。

【図１２】本発明を良好に用いうるパーソナルコンピュ
ータ・ネットワークを示す図である。

【図１３】本発明を用いうるファイル・サーバー・ネッ
トワークの例を示す図である。

【図１４】Ｎポート・ノードの主要な機能の構成装置を
示す図である。

【符号の説明】

10 二重ポート・ノード 12 直列リンク 14 直列リンク 16 ポート 18 ポート 20 ３ウェイ経路指定機能 22 ノード機能 30 単一ポート・ノード 36 二重ポート・ノード 50 アダプタ 52 ディスク１ 54 ディスク２ 56 ディスク３ 60 サーバー 64 スイッチ 68 ディスク装置 106 スイッチ 200 単一ポート・ノード 202 二重ポート・ノード 206 スイッチ 300 単一ポート・ノード 302 二重ポート・ノード 306 スイッチ 400 ポート・ロジック 410 非直列化器及び復号器ロジック 412 直列化及び符号化ロジック 414 CRC及びFNS検査ロジック 416 CRC及びFSN生成ロジック 420 ポート・ロジック 422 非直列化器及び復号器ロジック 424 直列化及び符号化ロジック 426 CRC及びFNS検査ロジック 428 CRC及びFSN生成ロジック 450 経路指定ロジック 452 アドレス解釈及び更新ロジック 454 フレーム・バッファ 456 マルチプレクサ 458 要求ラッチ 460 ライン 462 アドレス解釈及び更新ロジック 464 フレーム・バッファ 466 マルチプレクサ 468 要求ラッチ 480 フレーム・バッファ 482 マルチプレクサ 484 要求ラッチ

───────────────────────────────────────────────────── フロントページの続き (72)発明者レジナルド・ビーアイングランド、エス・オー５１ピー・エックス、ハンプシャー、チャンドラーズ・フォード、クレベランズ・クロース４

Claims

【特許請求の範囲】

【請求項１】複数の相互に接続されたノードの集合であ
るネットワークとして構築されたデータ処理システムに
おいて、メッセージをソースノードから宛先ノードに対
して経路指定する方法であって、前記ソースノードが前記宛先ノードに対して伝達するメ
ッセージであって、前記ネットワークにおける経路を特
定する経路アドレス値を含むものを前記ソースノードが
発生するステップと、前記ソースノードに接続された一のノードによって前記
メッセージの前記経路アドレス値の中の所定の部分が所
定の値に相当するかどうかを判断するステップと、前記判断の結果、前記所定の部分が所定の値に相当する
場合には前記メッセージを受け入れるステップと、前記判断の結果、前記所定の部分が前記所定の値に相当
しない場合には前記経路アドレス値を修正し、前記メッ
セージを前記修正された経路アドレス値とともに次のノ
ードに送信するステップと、を含む経路指定方法。
【請求項２】前記ネットワークは二重ポートを有するノ
ードを含んでおり、該二重ポートを有するノードは先行
ノードから前記メッセージを受け入れた際に、前記経路
アドレスの前記所定の部分が前記二重ポートを有するノ
ードに係わる所定の値を含んでいないと判断した時に
は、前記二重ポートを有するノードは次のノードにメッ
セージを送信するに先立って前記経路アドレスの前記所
定の部分の値を減じる請求項１の経路指定方法。
【請求項３】前記ネットワークは三つ以上のポートを有
する交換ノードを含んでおり、前記交換ノードが前記メ
ッセージを受け入れた際に、前記経路アドレスの前記所
定の部分が前記交換ノードに対応する所定の値を含んで
いないと判断した時には、前記交換ノードは前記経路ア
ドレスからメッセージが伝達されるべきポートを特定
し、次のノードに前記メッセージを送信するに先立って
前記経路アドレスのうち前記伝達されるべきポートに該
当する部分を削除することを特徴とする請求項１，また
は請求項２の方法。
【請求項４】ノードが相互接続されたネットワークを形
成する方法であって、前記ネットワーク中において少なくとも一つの開始機能
ノードを定義するステップと、各々の前記開始機能ノードから照会メッセージに含まれ
ている経路アドレスによって特定された経路上にある隣
接ノードに対して前記照会メッセージを送信するステッ
プと、前記メッセージを受け取った後に、前記隣接ノードはそ
のノードに設けられた作動可能なポートの数の表示を含
む応答メッセージによって応答するステップと、前記開始機能ノードが前記照会メッセージの経路アドレ
スによって特定された経路上の前記隣接ノードに設けら
れた各々の前記作動可能なポートに接続されたノードに
対して形成メッセージを送るステップと、前記開始機能ノードに接続されたノードの各々の前記経
路アドレスと各々のノードに設けられた前記作動可能な
ポートの数を前記開始機能ノードのコンフィグレーショ
ンテーブルに記憶するステップと、を含む方法。
【請求項５】ノードが相互接続されたネットワークにお
いてメッセージの経路を指定するための装置であって、隣接ノードからメッセージを受け取る手段であって、前
記メッセージは宛先ノードに到達するまでに前記メッセ
ージが通過すべき経路を特定する経路アドレス値を含む
ものであることと、前記経路アドレス値の所定の部分が一の所定の値である
かどうかを判断する手段であって、もしそうであるとき
は前記メッセージを受け入れる手段と、前記経路アドレス値の所定の部分が前記一の所定の値で
ないときは修正された経路アドレス値を含む前記メッセ
ージを次のノードに転送する手段と、を含むメッセージ経路指定装置。