JP4195470B2 - 非サイクル有向グラフで接続された構成要素間の通信方法 - Google Patents

Description

関連出願
本出願は、本出願の譲受人にそれぞれ譲渡されており且つ本出願と同時に出願された名称「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｕｎｉｑｕｅ Ａｄｄｒｅｓｓ Ａｓｓｉｇｎｍｅｎｔ，Ｎｏｄｅ Ｓｅｌｆ−Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ Ｔｏｐｏｌｏｇｙ Ｍａｐｐｉｎｇ ｆｏｒ ａ Ｄｉｒｅｃｔｅｄ Ａｃｙｃｌｉｃ Ｇｒａｐｈ」による出願Ｓｅｒｉａｌ Ｎｏ．０７／９９４，４０２及び名称「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｔｒａｎｓｆｏｒｍｉｎｇ ａｎ Ａｒｂｉｔｒａｒｙ Ａｃｙｃｌｉｃ Ｔｏｐｏｌｏｇｙ Ｃｏｌｌｅｃｔｉｏｎ ｏｆ Ｎｏｄｅｓ ｉｎｔｏ ａｎ Ａｃｙｃｌｉｃ Ｄｉｒｅｃｔｅｄ Ｇｒａｐｈ」による出願Ｓｅｒｉａｌ Ｎｏ．０７／９９４，１１７に関連している。
発明の分野
本発明はコンピュータシステムに関する。さらに特定すれば、本発明は、コンピュータシステムの複数の任意に組立てられた要素の間に通信方式を確立し且つそれを利用する方法及び装置に関する。

背 景
所定のコンピュータシステムの内部の構成要素は、それらの要素自体の間で信号を搬送する能力を必要とする。非常に単純なシステムでは、システムの各要素をシステムのその他の全ての部品に直接ワイヤリングさせることが可能である。しかし、現実には、コンピュータを拡張自在にし、且つ未知の数のシステム部品に対応するために、コンピュータ設計者はずっと以前に通信バスの概念を開発した。

バスは、コンピュータシステム全体を通って走る１本又は複数本のワイヤなどの通信経路である。システムの各構成要素は、システム中のその他の構成要素の各々に理論上接続されるべきバスにプラグインされるだけで良い。構成要素間には単一の通信チャネルしか存在しえないので、各構成要素が他の構成要素と同時に通信できないことは言うまでもない。通信バスを利用する場合、１つの構成要素からの重要な情報部分をバスアクセスを待機しながらの係属状態に放置することのない効率良い方式で他の構成要素と通信するために各構成要素がバスを使用できるように、何らかの形態で共用構造を確定することが必要である。バス上の構成要素がバスを共用するための方法を一般にバスアービトレーション方式という。

重要な情報の流れを最大にするようにバスアービトレーション方式を最適化するという重大な要求に加えて、柔軟性をできる限り残しつつシステム遅延を最小にするために、バス自体の物理的（及び論理的／電気的）構成を最適化でき、また、そのようにすべきである。

バスに付随する他の構成要素と通信するためには、各構成要素はそのバスに関して実現された通信規約と一致する送受信回路などのハードウェアを具備しなければならない。そのような通信規格の１つは、この文書に付録Ａとして添付されている表題「Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｓｅｒｉａｌ Ｂｕｓ」のＩＥＥＥ規格文書Ｐ１３９４の中に記載されている。Ｐ１３９４に記載されている規格は同じバックプレーン上のカード、他のバックプレーン上のカード及び外部周辺機器の間で低コストで相互接続を実行しようとするものである。

従来の技術のバス又はネットワークは、どれをどこにプラグ接続すべきかを知ることを要求していた。たとえば、多くのコンピュータの背面には、特定の周辺機器に対応する指定ポートがある。コンピュータの中には、マウス及びキーボードなどの構成要素に対してＡＤＢと呼ばれるバスを使用し、他の周辺機器に対してはＳＣＳＩバスを使用するＭａｃｉｎｔｏｓｈのようにいくつかのバスを実現するものもある。これらの型のバスはディジーチェーン要素を一体に構成するが、その接続のトポロジーは限られている。他に知られているバス／ネットワークは、ネットワークのノードをリングとして、すなわち、動作するためには閉成されなければならないループに配列することを要求する。最後に、星状配列、すなわち、ハブ・スポーク配列は各ノードを中央マスタに直接リンクすることを必要としていた。従来の技術のシステムの各々には、望ましい程度の柔軟性が欠けている。

コンピュータの要素を１つのバスに任意に取り付けることが可能であり、それに際して、任意トポロジーをシステムにより構成要素の所定の配列を要求することなく機能システムに変更できることが望ましいであろうし、従って、それが本発明の目的である。
発明の概要
本発明の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関して公正バスアクセスアービトレーション方式を提供することである。
本発明の別の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関して優先バスアクセスアービトレーション方式を提供することである。
本発明の別の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関してトークンパッシングバスアービトレーションの方法を提供することである。
本発明のさらに別の目的は、非サイクル有向グラフに変更されているノードのネットワークにおいて誤りが検出されたとき又は動作中にノードが増減されたときにネットワーク中のどのノードによってもプレエンプティブバス初期設定をトリガしうるメカニズムを提供することである。

本発明のこれらの目的及びその他の目的は、システムバスに沿ったノードの任意アセンブリが非サイクル有向グラフに変更されているシステムで実現される。ノードの階層配列は１つのノードをルートと指定する一方で、他の全てのノードはそれらのノードがリンクしているノードとの間に親子関係を成立させている。各ノードは所定の肯定応答優先順位方式を成立させた複数の接続された子ポートを有しても良い。公正バスアクセスアービトレーションは、所定のポート優先順位に相応するシーケンスでバス許可を実行して、全ノードをバスでターンさせる。ルートノードは、等時性データ転送を要求するルートノードに対応するのに有用であるバスアクセスを獲得するために、常にその優先アクセス状態をアサートしても良い。あるいは、トークンパッシングアービトレーション方式を実現しても良く、その場合、バスアクセスに関わるトークンは先に説明した所定のポート優先順位方式に従ってノードを巡って渡されて行く。プレエンプティブバス初期設定は、必然的な誤りの検出時、あるいは既存のノードに対する接続の追加又は除去の時点でいずれかのノードによってトリガされれば良い。

発明の詳細な説明
任意のトポロジーを有するバスを利用する方法及び装置を説明する。以下の説明中、本発明を完全に理解させるために様々なコンピュータ素子などの数多くの特定の詳細な事項を述べる。しかしながら、そのような特定の詳細な事項がなくとも本発明を実施しうることは当業者には自明であろう。別の場合には、本発明を無用にわかりにくくしないために周知の制御構造やコード化技法を詳細には説明しなかった。

この詳細な説明を通して、説明に比喩による明確性を与えるために数多くの描写用語を導入している。たとえば、所定のトポロジーの中におけるノード間の親子関係という表現がしばしば見られる。この目的は、最終的に導出されるグラフに至る「方向」の概念を表わすことである。以下に説明するように、任意のトポロジーが非サイクル有向グラフに変化されたならば、１つのノードは「ルート」ノードとして識別されることになる。ルートノードは親ノードをもたず、ルートノードに論理の上ですぐ隣接している全てのノードはそのルートの子ノードである。「ツリー」の比喩は「ブランチ（枝）」及び「リーフ（葉）」と呼ばれるノードを取り入れることによって完成する。

ここで説明するバスアーキテクチャは単一のコンピュータに関わる素子に関連して説明されるのであるが、一般に、より広い範囲を有する。本発明は、バストポロジーを定義するに際して、装置のネットワークにおけるように一体にリンクされたノードの任意に組立てられたどのような集合体にも適用可能である。注意しなければならない１点は、ノードと物理的コンピュータ素子とを区別する必要があるということである。バスに常駐すべき各素子に関連して、少なくとも１つのノード物理層制御装置がある。状況によっては、所定の１つの素子を複数のノードと関連させると有利であろうが、通常の場合には、バスにある装置又は素子と、ノードとの間には１対１の対応がある。

そこで図１を参照すると、ノード１０のブロック線図が示されている。ノードを物理的にいかに実現するかは多少は任意である。本発明の好ましい実施例の実現形態では、ノードは付録Ａとして添付したＩＥＥＥ Ｐ１３９４ Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｓｅｒｉａｌ Ｂｕｓ通信規約に準拠するように設計されている。ノード１０はアービトレーション状態機械論理１１を含む。このアービトレーション状態論理機械論理は、ここで説明すべき技法及びアルゴリズムを実行するためのあらゆる論理回路を取り入れている。この回路はプログラマブルロジックアレイ（ＰＬＡ）から構成されていても良く、あるいはここで説明する機能を実行するように独自に設計されていても良い。ノード論理により実行されるべき機能を説明したならば、当業者はむやみに説明を加えなくとも本発明を実現することができるであろう。ノードは、その論理によって、バス初期設定、ツリー識別、自己識別及びバスアービトレーションの機能を含む最小限のアービトレーションプロトコルを実現するが、それら全ての機能については以下にさらに詳細に説明する。

図１に示すノード１０は送信側マルチプレクサ１２及び１３と、データ送信器、受信器及び再同期装置１４とをさらに含む。図１に示すノードは局所ホスト１５に結合している。局所ホスト１５は、システム中の他の構成要素と通信することが必要であるディスクドライブ、ＣＰＵ、キーボード又は他の何らかの構成要素などの、バスに付属させたい何らかの装置であれば良い。ノード１０は通信リンクを介して他のノードと通信する。リンクは２つのポートの間の接続であって、直接的、実用的な用語でいえばケーブルセグメントであるが、通常は何らかの物理通信チャネルとして実現されれば良い。リンクは、最低でも、それが接続する２つのポートの間に半二重通信チャネルを構成することが可能であるべきであろう。ポートはノードとリンクとの間のインタフェースである。本発明に従えば、ポートはデータ及びアービトレーション信号を送受信する能力を有していなければならない。ポートは、それがリンクを介して別のポートに接続しているか否かを判定することもできなければならない。これを容易にする１つの方法は、接続しているポートによってリンクを介して、リンクの他端にあるポートにより検出可能であるバイアス電圧を印加させるというものである。すなわち、１つのポートに、他端でポートに接続していないリンク、裸リンクが付属している場合には、そのポートは接続ポートではないと判定するのである。図１では、図示されているノード１０は接続リンク１７，１８及び１９をそれぞれ有する３つの外部ポート２１，２２及び２３を有する。

本発明を実現するためのノードに関わる実現規則のいくつかは、１つのノードが１つ又は複数のポートを有していて良いということである。ノードはそのポートのいずれか１つでデータを送受信可能であるべきであろう。ノードは一度にイネーブルされているポートのうち唯一つのポートでデータを受信可能であり且つ残る全てのイネーブルされたポートではこのデータを送信可能であるべきであろう。ノードはそのポートの全てを介して信号メッセージを同時に且つ独立して送受信可能であるべきであろう。ノードのポートごとに別個の信号トランシーバ、エンコーダ及びデコーダが要求される。最低限の実現ノードは局所ホスト装置を必要としない。たとえば、そのようなノードはケーブル延長として機能しても良い。これ以降、装置及び局所ホストを無視し、バストポロジーを言うときには、常に、ノードや様々なポートを介するバス接続に関連させて説明する。

グラフ変換
図２（ａ）及び図２（ｂ）は、任意に組立てられたノードの集合体を示す。これ以降、ノードを単に円として示すが、ノードは、それぞれ、図１に関して説明した素子と等価の素子を含むものと思われる。ただし、各ノードはその図に示した３つより多い数又は少ない数の外部ポートを有していても良いということに注意する。それぞれのノードを結合する図示されている線は、リンクを示すための方法である。ポートは図示されていないが、暗黙のうちに、リンクとノードを接続するインタフェースである。

ここで説明するバスアービトレーション技法は、任意のトポロジーを非サイクル有向グラフへと変更することを要求する。任意トポロジーグラフにおいては、ノードとリンクの集合体は１つのサイクルを形成しても良い。グラフ中の特定のノードから始まって、リンクを２度通ることをせずにリンクとノードを通過することによって同じノードに戻れる場合に、サイクルは成立する。図２（ａ）は、図示されているノードはいずれもループの中に接続していないことから、非サイクルグラフを示している。ところが、図２（ｂ）は、境界規定ボックス２５の中の領域が複数のサイクルを形成するノード４０〜４７の集合体を含んでいるために非サイクルグラフではない。説明すべきバスアービトレーション技法はサイクルが存在しないことを要求するので、ここではサイクルを変更するためのユーザ介入の方法についてもさらに説明する。

グラフを非サイクルしないという必要条件に加えて、グラフは有向グラフでなければならない。有向グラフは、隣接ノードの間に階層構造が成立しているようなグラフである。当初は、ノード間に親子関係は成立していない。すなわち、たとえば、ノード３１はノード３４に対して「親ノード」であっても良く、あるいはノード３４に対して「子ノード」であっても良い。従って、所定の任意トポロジーグラフを取り上げて、それを非サイクル有向グラフに変換することが必要である。ここで説明する方法は、ノードの数、あるいはノードが物理的にどのようにリンクしているかということとは無関係に且つリンクに沿った信号伝搬時間には関係なく、どのような所定の任意トポロジーに対してもこの変換を実行するように働く。

ノード通信
まず、非サイクル任意トポロジーグラフを有向グラフに変換するプロセスを説明する。次に、サイクル変更が要求されるケースを説明する。図３（ａ）は、ノードとリンクが状態ラベルを有し且つ通信される信号はグラフを有向にするためのグラフ変換プロセスを表して指示されているような図２（ａ）の任意グラフを示す。この時点で、ノード間の信号通信を説明しておくと有益である。図３（ｂ）は、リンク５２によって結合された２つのノード５０及び５１（以下、それぞれノードＡと、ノードＢ）を示す。説明した通り、リンクは図１に関連して先に説明したように各々のノードのトランシーバポートを結合する通信チャネルである。グラフ変換プロセスの間、ノードは隣接するノードとの間に親子関係を成立させることが必要になる。第１のノードのポートと第２のノードのポートとの間に少なくとも１つのリンクが接続していれば、それら２つのノードは隣接ノードであるという。図３（ｂ）〜図３（ｄ）では、変更されるべき関係はノードＢがノードＡの親であるということであり且つノードはその関係を成立させることが適切であると仮定する。

方向を設定するのに先立って、ノードＡがノードＢをその親として成立させることが適切になったとき、ノードＡはリンク５２が結合しているポートから信号「Ｙｏｕ Ａｒｅ Ｍｙ Ｐａｒｅｎｔ」（ＹＡＭＰ）を送信する。このメッセージは、ノードＡがＹＡＭＰ信号を発生していることをわかり且つノードＢは受信したメッセージがＹＡＭＰであることを理解できるのであれば、どのような形態をとっていても良い。ＹＡＭＰ信号５３がノードＢにより受信されると、ノードＢは「Ｙｏｕ Ａｒｅ Ｍｙ Ｃｈｉｌｄ」（ＹＡＭＣ）をリンク５２を介してノードＡへ送信することによってノードＡに応答する。ノードＡのアービトレーション状態機械論理１１はＹＡＭＰ信号５３の送信と、ＹＡＭＣ信号５４の受信との間の時間遅延を追跡し続ける。測定される時間は、ノードＡとノードＢとの間の伝搬遅延の２倍を指定する。ＹＡＭＣ信号を受信すると、ノードＡは「Ｙｏｕ Ａｒｅ Ｍｙ Ｃｈｉｌｄ Ａｃｋｎｏｗｌｅｄｇｅｄ」（ＹＡＭＣＡ）信号５５をもって応答する。これは、ノード間の伝搬時間遅延がＹＡＭＣの送信と、ＹＡＭＣＡの受信との間の時間遅延と等しいことをも確定する能力をノードＢに与える。半二重通信リンクの場合、ＹＡＭＣＡメッセージは通信チャネルを適正に方向付けする効果をも有する。

全二重通信リンクの場合には、３つの論理メッセージＹＡＭＰ、ＹＡＭＣ及びＹＡＭＣＡを代わりに２回の信号送信のみによって中継することができる。図３（ｃ）にはこの状況が示されており、ノードＡは戻りＹＡＭＣ信号５７を受信するまでＹＡＭＰ信号５６を加え続ける。ＹＡＭＣＡ信号は、論理上は、ＹＡＭＰ信号が到着しなくなったと検出されたときにノードＢへ送信される。
説明したこの三重非同期メッセージ交換の使用により、メッセージ交換に関わる双方のノードがリンクを介する伝搬時間遅延を確定できるようなメカニズムが構成される。この遅延値は以下にさらに説明する競合事象を変更するとき、並びにバス性能を最適化するための正規のバスアービトレーションの間に使用される。このパラメータの動的抽出は必須である。その代わりに、最適のバス性能は得られなくとも最大伝搬時間遅延を演繹的に規定することができる。

ノードＡ及びＢがノードＢはノードＡの親であることを意味するメッセージを交換した後には、リンクは有向になったと言うことができる。ノードＡはその論理によって、リンク５２が結合しているポートを親ポート（親ノードに話し掛ける）とラベル付けし、また、ノードＢはリンク５２が結合しているポートを子ポート（子ノードに話し掛ける）とラベル付けする。以下に説明する方法は所定の時点でノード及びポートに割当てられるラベルによって説明されるため、ポートが得るラベルを維持することは大切である。図３（ｄ）には速記図式表記が示されており、図中の方向矢印５８はノードＢがノードＡの親として設定されており且つリンクは有向であることを指示している。

方向確定
ここで図３（ａ）に戻ると共に、図６（ａ）〜図６（ｅ）のプロセスを参照して、任意トポロジー全体を方向づけするプロセスを説明する。トポロジー変換プロセスの説明を助けるためには、若干多彩な定義を導入することが必要である。第１に、「リーフ」ノードは１つのポートしか接続していないノードとして定義される。パワーアップ後又は他のバス初期設定後に初期設定されると、直ちにノードはその状態をリーフノードとして認識する。「ブランチ」ノードは少なくとも２つの接続するポートを有するノードである。１つを除く全ての接続ポートを介して、ブランチノードはＹＡＭＰ信号を受信しており且つそれに応答している。残るポートを介して、ブランチノードはＹＡＭＰ信号を送信しており、それにより、ノードが親ノードであることを確定する。ノードは、１つの親を有しており（ノードは親ノードを１つしかもつことができない）且つ他の全てのポートは子ノードに接続していることを確定するまで、ブランチ状態には到達しない。ブランチ状態に達するのに先立って、ノードがブランチであると確定されるまでノードが方向の設定を不可能にするサイクルの一部である可能性は存在しているので、ノードは「サイクル」ノードと考えられる。

グラフ変換手続きは、ステップ６０で、バス初期設定（パワーアップ又は誘導）のときに始まり、この時点で任意トポロジーの中のリーフノードはステップ６１で認識し、決定ボックス６６でそれらのノードが接続するポートを唯一つしかもたないことを判定することによって、ステップ６８でそれら自身をリーフノードとしてラベル付けする。図３（ａ）に示すグラフにおいては、ノード３３，３５，３６及び３７は、初期設定後、ステップ６９で各々がＹＡＭＰ信号を唯一の接続ポートを介して隣接するノードへ送信するリーフノードである。それらの信号を受信するノードは、次に、ステップ７０でＹＡＭＣ信号をリーフノードへ伝搬して戻すことにより、ＹＡＭＣＡ通信が完了したときにはそれぞれの親子ペアの間の所定のリンクについて１つの方向が確定する。ステップ７１では、各リーフノードは１つの接続ポートを親ポートとしてラベル付けし、親ノードにある各受信ポートは子ポートとしてラベル付けされる。

当初はリーフノードでないグラフ上のノードは、初め、先に述べた理由によって「サイクルノード」と考えられ、サイクルノード手続き６３に従って進行する。接続するポートのうち１つを除いて全てのポートを子ポートとしてラベル付けしているサイクルノードは、いずれも、後のステップ８５で、残ったラベル付けされていないポートからＹＡＭＰ信号を伝搬する。リンクについてその方向が設定されたとき、そこでサイクルノードはブランチノードとラベル付けされるようになる。すなわち、リーフノード３７がそのノード３４を親として確定した後は、ノード３４は唯一つのラベルなしポートを有するので（ノード３７に至るリンク接続を子ポートを介するものとしてラベル付けしている）、ノード３４はＹＡＭＰ信号をノード３１へ同報通信し、その結果、ノード３４はブランチノードになる。同様に、ノード３１がノード３３及び３４はその子ノードであると識別したならば、ノード３１はＹＡＭＰ信号をノード３０へ同報通信する。１つのノードが決定ボックス７５でその全てのポートを介してＹＡＭＰ信号を受信していたとき、そのノードはルートノードになる。図３（ａ）で、ノード３０がノード３１及び３２からＹＡＭＰ信号を受信した後、そのラベルはサイクルノードからルートノードであると変わる。図３（ａ）のグラフにおいては、必ずしもノード３０がルートになる必要はないであろう。ツリー中のリンクのうちいくつかが長い伝搬遅延を生じさせるのであれば、ノード３０は１つのポートでＹＡＭＰ信号を受信しており、次に別のポートを介してＹＡＭＰ信号を送信していたかもしれない。ノードのいずれもルート、さらにはリーフになって良く、リーフは適正に手続きをとる。図３（ｅ）は、図３（ａ）に示す通信信号に応答して、その結果得られた有向グラフを示し、各ノードはラベル付けされており且つ方向は黒の矢印によって指示されている。

ルート競合
状況によっては、ルート競合状態が起こりうる。これは、たとえば、任意トポロジーが図４に示す任意トポロジーに対し対称の配列を有するような場合に起こるであろう。図４に示す任意グラフでは、ノード１６０及び１６１はそれが結合している２つのリーフノードに対して親であることをそれぞれ確定している。次に、各ノードはＹＡＭＰ信号をほぼ同時に他方へ伝搬している。ルート競合状態は決定ボックス８６において関連する双方のノードにより認識される。各ノードはそれを親として指定する信号を受信しており、その一方で同じ信号を同じポートを介して送信している。競合しているノードの各々はステップ９１でＹＡＭＣ信号によって他方に応答し、それにより、各ノードはノード間の伝搬時間の２倍に等しい「決定時限」を確定できる。

ルート競合状態は、各ノードの各々の任意状態機械論理装置１１に組込まれているランダム決定メカニズムを利用することによって解決される。「決定時限」が経過するたびに、各ノードは、ステップ９２で、再び他方へＹＡＭＰ信号を送信すべきか否かを無作為に（５０％の確率をもって）決定する。ほぼ確実に限られた数のサイクルの中で、一方のノードはその一方が往復することなく他方を親として指定することを決定する。親と指定されたほうはステップ９５でルートになる。あるいは、ノードに所定の選択基準値を割当て、その大きいほう又は小さいほうの値が競合事象でどちらが優勢であるかを判定するようにしても良い。「決定時限」の動的確定は最適の性能を与えるものではあるが、本発明を実現する上で不可欠ではない。その代わりに、このアルゴリズムを使用するどのようなバスにおいても生じうる最悪の場合のリンク伝搬より長くありさえすれば、演繹的に定義された「決定時限」を使用しても良い。ルート競合を解決するために使用するのと同じ方法が、以下にさらに説明する他の競合事象を解決するためにも使用される。

ルート割当て
先に説明した通り、グラフ変換プロセスの結果はグラフ中の唯一つのノードへのルート属性の割当てである。ルートノードは後述するバスアービトレーション方式における最終的な決定を有し、従って、特別の優先順位時間間隔を使用せずに最大の優先順位をもってバスをアクセスすることができる。多くの場合、所定のシステムを最適化するために、ノードが製造されるときに、もしくは動的に（ランタイム中に）所定のノードにルート特性を割当てることが可能であるのが望ましい。所定のバスは、等時性データ転送を要求するノードを含んでいるかもしれない。等時性データは、所定の時間に何らかの値をもつように伝送されなければならないデータである。たとえば、コンパクトディスクから発する音楽は、断片的に転送され、必ずしも順序通りではないデータファイルとは異なり、聴取すべき順序で、大きな遅れなく転送され且つ出力される必要がある。

ルート指定に関してノードを３つのカテゴリに分類することができる。それらの指定は、製造中、装置への指定のハードワイヤリング、アービトレーション状態機械論理のプログラミング又は決定を実行するより高いレベルのソフトウェアの使用と、その後のその決定を維持したままの再ブートの開始によって適用されれば良い。ルートを指定されるのに関してノードが割当てられうる３つの指定は：ルートとなることを望まないノードと、ルートになりうる（なるべき）ノードと、ルートになるであろうノードである。ステップ８１及び８３では、それらの指定を試験する。第１のカテゴリに指定されるノードは、指示されたときに直ちにグラフ変換手続きを開始する。これは、通常、バス初期設定手続きの完了の直後である。第２のカテゴリのノードは、ステップ８４でグラフ変換手続きを開始することを指示された後に、そのプロセスの開始を所定の長さの時間だけ遅延させる。この遅延によって、ノードはルートになる機会を増す。（ＹＡＭＰ信号はその遅延によりそのノードまでより伝搬しやすい。）遅延の追加にもかかわらず、「ルートになりうる」ノードがルートと指定されることで終わらない可能性は依然としてある。これは与えられたトポロジーと、メッセージ伝搬遅延とによって決まる。遅延の量は、設計中、相当に複雑なグラフを通るときの最悪の場合の妥当な伝搬遅延より多くなるように定義できる。

ルート指定の可能性のうち第３のカテゴリに入るノードは、グラフを既に変換し終わり且つ全てのノードはそれ自体を識別した後にルートにならなければならないということを認識するのみであろう。アービトレーション状態機能論理がこの確定を実行しても良く、ホストシステムでランするソフトウェアであっても良い。これが起こると、ルートにならなければならないノードはバスに沿った他の全てのノードと、それが唯一のルートになろうとしていることを承諾し、以下でさらに説明する割込形バス初期設定信号を発信することによってグラフ変換プロセスを再開する。次に、ノードは、ステップ８２で、ルートになるのを待ち、その全てのポートでＹＡＭＰ信号を受信するまでグラフ変換に参加せず、それにより、そのノードは必然的にルートと指定されることになる。
ルートが確定されたならば、グラフは有向であるということができる。グラフ上の全ての隣接ノードの間に定義された関係が存在している。

サイクル変更
先に説明したグラフを有向にする手続きは非サイクルグラフについてのみ働く。任意トポロジーの中にサイクルがあれば、ステップ８０で始まる手続きによってサイクルを破断しなければならない。ステップ７９で、所定の時間切れ周期が経過した後に、ノードが依然としてリーフ、ブランチ又はルートではなく、サイクルノードとラベル付けされているとき、サイクルの存在は検出される。「サイクル検出」タイミングはバス初期設定機能の終了の直後に始まる。時間切れ周期は最悪の場合のグラフ変換プロセスの持続時間（「ルートになりうる」ノード及び起こりうるルート競合事象に関しての遅延時間の追加）より長くなってはならない。

あらゆるメッセージ交換は非同期事象であるので、「サイクル検出」時間切れ事象はグラフの全てのノードに対して同時に起こる必要はない。そのため、「サイクル検出」時間切れ事象にまだ到達していないノードがサイクル解決は進行中であることを指示するメッセージを受信することは可能である。そのようなノードはそのサイクル検出時間切れ間隔を終了し、適切なサイクル解決プロセスを開始する。

本発明に従ったサイクル解決の方法は組立て後のノードの集合体のユーザが介入することを要求する。ノードが「サイクル検出」時間切れを受けると、システムのユーザは図６（ｅ）のステップ１００で、サイクルが存在しており且つノードが次に関連しない出力装置を介して通知されるであろう。そこで、ユーザは、どのようなサイクルでも存在することを排除するために、リンクを遮断することを命令される。次に、ユーザはグラフ変換手続きに制御を戻す。
ループの各々が破断されて、サイクルが全く残っていないのであれば、先の節で説明したようなグラフを変換する手続きを、グラフ全体が非サイクルであると共に有向になるまで進行させて良い。

固有物理アドレスの割当て
元の任意トポロジーから非サイクル有向グラフを確定したならば、グラフの各ノードに固有の物理アドレスを割当てることが可能である。このプロセスは、全てのリーフノードがその単一の接続ポートを介してバス要求（ＢＲ）信号を送信することによりバスを要求することをもって始まる。その信号を受信した親ノードは、その子ポートの全てからＢＲ信号を受信し終わるまで待機し、次にＢＲ信号をその親に伝搬する。ＢＲ信号は、ルートがその子の全てからＢＲ信号を受信し終わるまでグラフを通って伝搬する。ルートがその子ポートの全てを介してバス要求を受信したならば、ルートはバスを１つのポートを介して許可し且つその残る子ポートを介してバス拒否（ＢＤ）信号を伝搬するための決定を実行する。どのバス要求を許可すべきかを選択する方法は、先に、たとえば、ポートを左から右へと又はポート番号づけに基づいて選択する場合などについて説明したような演繹的決定であっても良い。バス許可（ＢＧ）信号はルートからそれが要求している子へ送信される。その要求中の子が、それ自体、その子のうち１つからバス要求を伝搬した親ノードである場合には、その子ノードはその子ポートの１つを除く全てのポートを介して先に説明したのと同じ所定の方式でバス拒否信号を送信する。最終的には１つのリーフノードがバス許可信号を受信し、そのノードはバス許可確認（ＢＧＡ）信号によって応答し、ＢＧＡ信号はルートノードへと伝搬されて戻る。ＢＤ信号とＢＧＡ信号の伝搬は半二重通信チャネルの場合に必要になるであろう通信リンクの方向を定める働きをする。そこで、拒否された全てのノードは最終的にＢＧ信号を受信するノードによるアクティビティを待つ。

最終的にバスに対するアクセスを許可されるノードはアドレス割当てパケットを送信する。ノードはこのパケットをバスを介して送信し、パケットは他の全てのノードにより受信されて、それらのノードは、それぞれ、受信するアドレスパケットの数をカウントする。送信されるアドレスパケットは何らかの任意の情報を有していても良い。ノードの固有物理アドレスは、ノードがアドレスパケットを送信する前にカウントしたアドレスパケットの数に基づいている。すなわち、前もってアドレス情報は割当てられていないにもかかわらず、２つのノードが同じ物理アドレスを獲得することはない。アドレスパケットの実際の組成は任意であって、システムにより効率良く利用可能な何らかのビットストリームであれば良い。物理アドレス割当てパケットを送信した後、ノードは「子ＩＤ完了」信号（ＣＩＣ）信号を送信する。子ポートでこれを受信した親ノードは、次に、「子識別完了確認」（ＣＩＣＡ）信号を送信し、ポートを識別済子ポートとしてラベル付けする。次のＢＲ信号の伝搬に応答して、自身を識別したばかりであるノードの親は物理アドレスパケットを送信すべき次の子を選択する。１つの親ノードの子ノードの全てが自身を識別したならば、親ノードはバスを要求し、バスを許可したとき、その物理アドレス割当てパケットを伝搬する。この手続きは、所定の選択基準に従って、全てのノードがカウント動作によって固有物理アドレス割当てを確定するまで続く。図５は、左から右への事前定義済選択基準が実現されている図３（ｅ）のグラフを示す。ノードは固有のアドレスを割当てられ、ノード３３は第１のアドレスを受信し、前述のように、ルートノード３０は第８の、そして最後のアドレスを受信する。
この手続きが完了すると、グラフ中の各ノードは固有物理アドレスを有することになり、そのアドレスは前もって確定されている必要はなく、システム管理又はその他の目的のために利用されれば良い。

ノードの自己識別
ノード自己識別プロセスは本質的には先に説明した物理アドレス割当て手続きと同一のルーチンに従う。各ノードがその物理アドレス割当てパケットを送信するとき、そのパケットはノードに関連する局所ホストのＩＤ、それがどれほどの量の電力を必要とするか、さらに、たとえば、「ソフトパワーオン」属性を支援するか否か等々の別の情報を含んでいても良い。事実、ノード自己識別情報は、どの情報を送信するにしても、それは固有物理アドレスを獲得するためのカウントの基礎となることから、物理アドレス割当てパケットとして働くのである。
ノード自己識別パケットに関しては、ノードに関する特定の情報は告知しているノードの性質によって影響を受けるノードにより「聴取」されるだけで良い。先の場合と同様に、この手続きは全ノードがそのノード自己識別情報を送信し終わるまで進んで行く。

トポロジーマッピング
トポロジーマッピングの方法は、物理アドレス割当て及びノード自己識別と同じラインに沿って流れる。すなわち、この手続きでは、各ノードがアドレス割当て又はノード自己識別のプロセスを経過しているとき、そのノードに、ノードが有している子ポートの数及びディスエーブルされたポートを有しているか否かなどの全てのポートに関する情報をさらに送信する。ディスエーブルされたポートに関しては、どこからディスエーブルされるかを識別できるように、ディスエーブルしようとしているポートの相互間に通信規約を実現することが望ましいであろう。従って、ポートがディスエーブルされたポートを識別するとき、ポートはそれ独自のＩＤを指示する識別子並びにディスエーブルされる元になったポートＩＤを与える。

トポロジーマッピング手続きの間に受信する全てのポートに関わるあらゆるトポロジー情報を組立てることにより、ホスト又は何らかのソフトウェアレベルアプリケーションは解決したバストポロジーを論理的に再構成できるであろう。これは、リンクが予想外に故障した場合に、先にディスエーブルしたリンクがどのノードに対しても通信チャネルの損失を阻止するように働ける冗長性を実現することを含む数多くの目的のために有用である。

公正バスアクセスアービトレーション
トポロジーマッピング、ノード自己識別又は物理アドレス割当てのルーチンが完了したならば、バスが起動し、ラン中であると考えることができる。本発明に従って実現される１つのアービトレーション方式は、正当なバスアクセスのアービトレーション方式である。バスに対するアクセスを望むとき、ノードはその親ポートを介して（それがルートでない限り）バス要求（ＢＲ）信号を送信する。親は、１つの子からＢＲ信号を受信すると、他の全ての子ポートを介してバス拒否信号（ＢＤ）を送信する。そこで、親はＢＲ信号をその親を通って、その信号がルートに到達するまで上方へと伝搬する。ルートはそれが受信する第１のＢＲ信号に応答してバス許可信号（ＢＧ）を発行すると共に、その他の全ての子ポートを介してＢＤ信号を送信し、ＢＤ信号は下方へと伝搬することにより、リンクの方向を定める。ＢＧ信号は要求している側のノードに到達するまでグラフを通って下方へと伝搬し、そのノードは、次に、バス確認（ＢＡ）信号を送信し、それに続くのはノードがバスへ送信することを必要とした情報のパケットである。パケットが完了したとき、全てのノードはアイドル状態に戻るか、又はアイドル状態に入る。

ルートがバスに対するほぼ同時の要求を受信する場合、ノードのうち１つにバスアクセスを許可するために、ルートノードに関わる所定の選択基準を使用することができる。これは先に説明したのと同じ所定の優先順位選択基準であっても良い。

公正バスアクセスアービトレーションの別の一面は、親ノードがその子に対して優先権をもつことである。すなわち、親ノードは、バスを要求するときに、ＢＤ信号をその子ポートの全てを介して送信し、次にＢＲ信号をルートに向かって上方へと伝搬する。このメカニズムに伴って起こりうる１つの問題は、親がバスを介して送信すべき大量の情報を有している場合に、子ノードが適切なバスアクセスを獲得するのに障害を生じるかもしれないということである。従って、当該技術では広く使用され且つ良く知られているギャップシステムが導入されている。ノードはバスを利用した後に、再びバスを要求できるようになる前にギャップ周期１つ分待機しなければならない。これにより、バス上におけるノードのトポロジー配列にかかわらず、バスに沿ったどのノードにもバスを許可される均等な機会が与えられるのである。公正アービトレーションプロトコルを保証するためには、ギャップの長さはバスを通過するときの最悪の場合の信号伝搬遅延より大きくなければならない。ギャップ値をあらかじめ確定して、ノード論理にハードワイヤリングすることができるが、そのような方式は、結果として、最も極端なケースを除くあらゆる場合においてバスを最適に近い形で利用できる。トポロジーマッピング能力は、グラフ変換段階の間に実行される隣接ノード間の伝搬遅延の測定とあいまって、どの特定の実現形態に対してもバス性能を最適化する最適公正ギャップの計算を可能にする。

優先バスアービトレーション
上述の公正バスアクセスアービトレーションに従って実現されるバスアービトレーション方式においては、ルートは常にバス優先権を有していることが望ましいであろう。これが実現されるとき、ルートノードはそれ自身にいつでもバスを許可して良い。これは、まず、ＢＤ信号をグラフ中の全てのノードを通して下方へと送信することによって実行される。ルートに関わる優先バスアクセスは、等時性データ転送を実行するためにルートノードが要求されるような場合に非常に有用である。

トークンパッシングバスアービトレーション
先に説明した公正バスアクセスアービトレーション方式及び優先バスアクセスアービトレーション方式の代わりに、トークンパッシングバスアービトレーション方式を実現するに際して本発明を利用しても良い。比喩的にいえば、トークンパッシングバスアクセスは、バスがノード間を渡されているトークンを所有しているときにノードはバスを介して通信して良いという概念を表わす。各ノードがサイクル中の所定のポイントでバスを受けるように、トークンはノードからノードへとサイクル方式で渡されて行く。本発明においては、トークンパッシングは先に説明した物理アドレス割当てルーチンと同じ方式に従って実現される。実現される所定の選択メカニズムを使用して、トークンをノードからノードへと渡して行く順序を選択する。この順序は、固有アドレス割当ての順序を指示する図５に示すような順序に類似している。各ノードは、トークンを割当てられたとき、残るノードが聴取している間にバスに沿ってその情報パケットを伝搬する。次に、ノードは、先に説明したような所定の順序づけ方法に基づいてトークンを次の論理ノードに渡す。

プレエンプティブバス初期設定
本発明に従って実現しうる重要な特徴は、プレエンプティブバス初期設定の概念である。各ノードに組込まれている状態機械論理は、いくつかの条件に対してノードからその全てのポートを介して伝搬されるべきバス初期設定（ＢＩ）信号をトリガすることができる。ノードがバス初期設定条件を信号で報知する必要があると確定したとき、ノードはＢＩ信号をその全てのポートを介して、全ての隣接ノードがその信号を受信し、次に変更するように保証するのに十分な長さの時間だけ伝搬する。そこで、ノードはその後に先に説明した手続きの中でグラフ変換プロセスに至る開始手続きに入る。

プレエンプティブバス初期設定をトリガすることを必要にするか又は望ましくするであろういくつかの状況がある。第１に、これは予期せぬ誤りに対するノード応答であっても良い。加えて、ホストレベルでは、異なるノードがルート属性、たとえば、等時性データ転送ノードを獲得すべきであることを確定しても良い。この割当てはバス初期設定ルーチンを通して維持されるので、所望のノードはルート指定を受信するまで変換手続きの間は待機することになる。プレエンプティブバス初期設定に至る別の条件はリンクの破断であろうが、その場合、付属するノードについて新たな非サイクル有向グラフを計算することが必要であろう。最後にプレエンプティブバス初期設定が起こるべき重要な状況は、周辺機器の「ホットアディション」と呼ばれるような、装置がネットワークに追加されるときである。新たな装置が接続されるポートは新たなノードの有無を検出し、システムのユーザに対しては透明であるが、たとえば、遮断と再給電の必要なく周辺機器の増減を可能にするバス初期設定をトリガする。追加されたノードの存在を含む新たな非サイクル有向グラフを計算する。いくつかのノードを取り除いたとき、バス初期設定をトリガする必要はなくなる、たとえば、リーフノードを取り除いたときには、ネットワークに害はないということはありうる。しかしながら、動作中のバスからブランチノードが指定される場合には、グラフを再構成する必要がありそうである。

本発明を好ましい実施例によって説明したが、当業者により本発明の趣旨から逸脱せずに様々な変形や変更を実施しうることは理解されるであろう。従って、本発明は続く請求の範囲によって判断されるべきである。

図１は、本発明に従って利用されるハードウェア層実現のブロック線図を示す。 図２（ａ）は、ノードの任意の組立てられた集合体を示し、非サイクルのものを示す。 図２（ｂ）は、ノードの任意の組立てられた集合体を示し、サイクルを含むものを示す。 図３（ａ）は、本発明に従ったグラフ変換プロセスを受ける図２（ａ）のノードの任意に組立てられた集合体である。 図３（ｂ）は、本発明を実現するに際してのノード間の代替通信交換例を示す。 図３（ｃ）は、本発明を実現するに際してのノード間の代替通信交換例を示す。 図３（ｄ）は、本発明を実現するに際してのノード間の代替通信交換例を示す。 図３（ｅ）は、図２（ａ）のノードの任意に組立てられたネットワークから得られる有向グラフを図式的に示す。 図４は、ルート競合を変更することを要求する対称グラフ配列を示す。 図５は、指示されうる固有アドレス割当て順序をもつ非サイクル有向グラフを示す。 図６（ａ）は、本発明の好ましい実施例に従うプロセスの全体の流れを示す。 図６（ｂ）は、本発明の好ましい実施例に従うプロセスのリーフノード手続の流れを示す。 図６（ｃ）は、本発明の好ましい実施例に従うプロセスのサイクルノード手続の第１部分を示す。 図６（ｄ）は、本発明の好ましい実施例に従うプロセスのサイクルノード手続の第２部分を示す。 図６（ｅ）は、本発明の好ましい実施例に従うプロセスのルート競合処理の流れを示す。 図６（ｆ）は、本発明の好ましい実施例に従うプロセスのサイクル変更処理を示す。

符号の説明

１０ ノード
１１ アービトレーション状態機械論理
１４ データ送受信及び同期装置

Claims (13)

1. それぞれのノードが非サイクル有向グラフ内にある、第１のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第１のノードが少なくとも一つの隣接ノードと通信を行う方法において、
   前記少なくとも一つの隣接ノードの第２のノードに第１のノードから第１の「You are My Parent（ＹＡＭＰ）信号」を伝搬し、
   「ＹＡＭＰ信号」の伝搬後に、前記第１のノードが、前記第２のノードからの第２の「ＹＡＭＰ信号」を受信することなく、該第２のノードからの「You are My Child（ＹＡＭＣ）信号」を受信し、
   前記「ＹＡＭＣ信号」の受信に応答して前記第１のノードと第２のノードとの親子関係を、前記第１、第２のノードの少なくとも一方により確立し、
   前記第１ノードによる「ＹＡＭＰ信号」の伝搬と前記第１ノードによる「ＹＡＭＣ信号」の受信までのギャップ時間から第１、第２のノード間通信の伝搬時間を決定する方法。
2. 前記「ＹＡＭＣ信号」の受信に応答して、前記第１のノードから第２のノードに「You are My Child Acknowledged（ＹＡＭＣＡ）信号」を伝搬し、第２のノードからの第１のノードへの「ＹＡＭＣ信号」の伝搬と第１のノードからの「ＹＡＭＣＡ信号」の第２のノードでの受信までのギャップ時間から第１、第２のノード間通信の伝搬時間を決定することをさらに含む請求項１記載の方法。
3. 「ＹＡＭＣ信号」の受信前に、前記第１のノードが前記第２のノードからの第２の「ＹＡＭＰ信号」を受信したときには、前記第１、第２のノードのいずれによっても該第１、第２のノードの親子関係は確立されない請求項１記載の方法。
4. さらに、
   前記伝搬時間にしたがって決定時間を決定し、
   前記親子関係が確立されるまで、前記決定時間が経過するたびに、前記第１のノードが、「ＹＡＭＰ信号」を前記第２のノードに伝搬するか否かに関して行う無作為の決定を繰り返す請求項３記載の方法。
5. それぞれのノードが非サイクル有向グラフにある、第１のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第１のノードが少なくとも一つの隣接ノードと通信を行う方法において、
   前記少なくとも一つの隣接ノードの第２のノードからの第１の「You are My Parent（ＹＡＭＰ）信号」を第１のノードにて受信し、
   該第１の「ＹＡＭＰ信号」の受信に応答して第１のノードから「You are My Child（ＹＡＭＣ）信号」を第２のノードに伝搬し、
   前記第１のノードが第２の「ＹＡＭＰ信号」を前記第２のモードに伝搬しない場合に、前記第１のノードによる前記第１の「ＹＡＭＰ信号」の受信に応答して、前記第１、第２のノードの少なくとも一方が、前記第１のノードと第２のノードとの親子関係を確立し、
   前記「ＹＡＭＣ信号」の伝搬後、前記第２のノードからの「You are My Child Acknowledged（ＹＡＭＣＡ）信号」を第１のノードにて受信し、
   前記第１のノードによる「ＹＡＭＣ信号」の伝搬と「ＹＡＭＣＡ信号」の受信までのギャップ時間から前記第１、第２のノード間通信の伝搬時間を決定する方法。
6. 前記第１のノードが前記第２のノードに第２の「ＹＡＭＰ信号」を送信したときには、前記第１、第２のノードのいずれによっても該第１、第２のノードの親子関係は確立されない
   請求項５記載の方法。
7. さらに、
   前記伝搬時間にしたがって決定時間を決定し、
   前記親子関係が確立されるまで、前記決定時間が経過するたびに、前記第１のノードが、「ＹＡＭＰ信号」を前記第２のノードに伝搬するか否かに関して行う無作為の決定を繰り返す請求項６記載の方法。
8. それぞれのノードが非サイクル有向グラフにある、第１のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第１のノードが少なくとも一つの隣接ノードと通信を行う方法において、
   前記少なくとも一つの隣接ノードの第２のノードに第１のノードから第１の「You are My Parent（ＹＡＭＰ）信号」を伝搬し、
   「ＹＡＭＰ信号」の伝搬後に第２のノードから第２の「ＹＡＭＰ信号」を第１のノードにて受信し、
   第２の「ＹＡＭＰ信号」に応答して期間を決定し、
   第３の「ＹＡＭＰ信号」を第１のノードから第２のノードに伝搬するか否かを、前記第１のノードによって決定し、
   前記第１のノードが第３の「ＹＡＭＰ信号」を伝搬すると決定した場合には、第１のノードから第２のノードに第３の「ＹＡＭＰ信号」を伝搬し、
   第３の「ＹＡＭＰ信号」の伝搬後、第２のノードからの第１の「You are My Child（ＹＡＭＣ）信号」を第１のノードにて受信し、
   前記決定された期間において前記第１のノードがいずれの「ＹＡＭＰ信号」も受信しなかった場合に、前記第１の「ＹＡＭＰ信号」に応答して前記第１のノードと第２のノードとの親子関係を、該第１、第２のノードの少なくとも一方によって確立する方法。
9. 前記第１のノードが第３の「ＹＡＭＰ信号」を伝搬しないと決定した場合には、さらに、
   前記期間の満了前に、第２のノードからの第４の「ＹＡＭＰ信号」を第１のノードにて受信し、
   第４の「ＹＡＭＰ信号」に応答して第１のノードから第２のノードへ第２の「ＹＡＭＣ信号」を伝搬し、
   第４の「ＹＡＭＰ信号」に応答して第１、第２のノード間の親子関係を、該第１、第２のノードの少なくとも一方によって確立することを含む請求項８記載の方法。
10. 前記期間は所定の長さである請求項９記載の方法。
11. さらに、
    第２の「ＹＡＭＰ信号」に応答して第１のノードから第２のノードに第３の「ＹＡＭＣ信号」を伝搬し、
    前記期間の決定前であってかつ前記第２の「ＹＡＭＰ信号」の受信後、第２のノードからの第４の「ＹＡＭＣ信号」を第１のノードにて受信し、
    第１の「ＹＡＭＰ信号」の伝搬と第４の「ＹＡＭＣ信号」の受信までの時間ギャップにしたがって前記期間を決定することを含む請求項９記載の方法。
12. 前記第３の「ＹＡＭＰ信号」を第１のノードから第２のノードに伝搬するか否かに関する、前記第１のノードの決定は無作為に決定される
    請求項１１記載の方法。
13. さらに、
    前記期間が経過するたびに、「ＹＡＭＰ信号」を伝搬することに関する前記第１のノードの無作為の決定が、前記第１、第２のノードの親子関係が確立されるまで繰り返される請求項１２記載の方法。

Images