(57)【特許請求の範囲】
【請求項１】
ネットワークにおけるノード間に論理接続を確立する方法であって、
前記ネットワークにおいて論理的に接続されたノードのグループのそれぞれによって識別子を生成するステップと、
物理的に接続された一対の前記グループ間において、識別子を交換するステップと、
前記交換された識別子が異なる場合にのみ、前記物理的に接続された一対のグループ間において、論理接続を確立するステップと、
を含む、方法。
【請求項２】
前記論理的に接続されたノードのグループは、１つまたは複数のノードを含む、
請求項１に記載の方法。
【請求項３】
前記物理的に接続された一対のグループ間で交換された識別子が同じであるならば、ループをチェックするステップを含む、
請求項１または２に記載の方法。
【請求項４】
ループが存在しないならば、前記識別子を生成するステップおよび前記識別子を交換するステップが繰り返される、
請求項３に記載の方法。
【請求項５】
ループが存在するならば、前記物理的に接続された一対のグループ間には新たな論理接続を確立しない、
請求項３に記載の方法。
【請求項６】
前記生成するステップ、前記交換するステップおよび前記論理接続を確立するステップを、すべてのノードが論理的に接続されてネットワーク・トポロジが確立されるまで、繰り返す、請求項１から５のいずれかに記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ネットワークにおけるループの防止に関し、より具体的には、ループを含む物理ネットワークからループ無しの論理ネットワーク（とりわけ、すべてのノードが接続される論理ネットワーク）の提供に関する。また、この発明は、特に開発中のIEEE1394ｂのネットワーキング標準に従うアーキテクチャに関する。
【０００２】
【従来の技術】
標準であるIEEE1394ファミリーは、高水準で動的に構成することができるバス・アーキテクチャに関するものである。これらの標準に関連する情報は、電気電子技術者協会（ＩＥＥＥ）から入手することができる。
【０００３】
IEEE1394aでは、配線トポロジは、バスが機能しなくなるようなループを含むべきではないということを要求している。そのコンテキストにおいて、ループは、所与のノードへの、任意の数の他のノードを経由した複数の独立した接続経路の存在、と定義されている。
【０００４】
【発明が解決しようとする課題】
IEEE1394bの拡張版にあるように、自動的に何らかのループの存在を検知してバス・トポロジからそれらを論理的に取り除くメカニズムを適切に設けるべき、ということが提案されている。
【０００５】
【課題を解決するための手段】
この発明は、ネットワークにおけるノード間に論理接続を確立する方法を提供する。この方法は、ネットワークにおいて論理的に接続されたノード・グループのそれぞれによる識別子の生成と、論理的に接続されたノード・グループのうち物理的に接続されたノード・グループ間における識別子の交換と、交換された識別子が異なる前記物理的に接続されたノード・グループ間における論理接続の確立と、を含む。
【０００６】
この発明のさらなる側面によると、この発明は、論理ループを持たないネットワーク・トポロジを確立する方法を提供する。この方法は、ａ／ノード間における論理接続を持たない物理接続から開始し、ｂ／上記示される論理接続を確立する方法を実行して、論理的に接続されたノード・グループを提供し、ｃ／すべてのノードが論理的に接続されるまで上記ステップｂ／を繰り返し実行する、ことを含む。
【０００７】
【発明の実施の形態】
任意のトポロジ（初期的にループを含んでもよい）において接続されたノードを得て、すべてのノードが共に接続されることを保証しつつループ無しの他のトポロジを発見する分散アルゴリズムを説明する。
【０００８】
このトポロジ発見アルゴリズムは、個々のノードレベルから始まり、ループが形成されなければ他のノードへの接続を確立することにより成長するという意味で、「有機的（organic：オーガニック）」である。ノードのループ無しの集まり（これを、「島」と呼ぶ）が形成されると、それらは、ループを形成することにならない限り、それら自身が他のノードと合体することにより成長する。この処理は、すべてのノード上の物理接続を持つすべてのポートが試験されて、アクティブまたはディスエーブル（disable）のいずれかになるまで続く。
【０００９】
「島」は、ここでは、論理ループを全く含まない、接続されたノードのグループとして定義される。この制限において、島は、１つのノードから構成されることもできる。
【００１０】
用語「固有識別子」は、ここでは、それぞれのノードによって生成される最善努力型の固有識別子（best-effort unique identifier：ＢＩＤ）について使用される。ＢＩＤは、理想的にはそれぞれのノードに対して固有である数字であるが、実際には、ノードにおける乱数および他の数値的な識別子の何らかの組み合わせであることができる。島では、島自身が、すべてのノードおよびポートに伝達され、すべてのノードおよびポートに共通であるＢＩＤをとる。
【００１１】
「ソフト・リセット（soft reset）」は、ここでは、バス・トポロジを変更することなく、ツリーＩＤ処理（tree ID process）を呼び出すリセットについて使用される。
【００１２】
「ピング（ping）」は、バス上の特定のアドレスを持つノードに送信される特定のパケットである。アドレスによって特定されたノードは、送信者に返答を返すことにより、パケットの受信を通知する。
【００１３】
ここで説明する方法の実施形態では、それぞれのノードは最善努力型の固有識別子（ＢＩＤ）を生成するが、このＢＩＤは、島におけるすべてのノードおよびポートに共通であり、ノードが、ノード自身の任意のポートをイネーブル（enable）またはディスエーブルすることができると仮定する。
【００１４】
そのような方法を実現するためのアルゴリズムを以下に説明する。このアルゴリズムは、コスト・メトリック（cost metric）の概念に基づいており、ノードにおいて競い合う物理接続を区別する。「最善」すなわち最も低いコストの競争者を定義することができる多くの方法がある。以下のアルゴリズムの説明では、１つの考えられる定義を使用する。ここでは、ＢＩＤ(ｘ)＜ＢＩＤ(ｙ)ならば、ｘをマスター、ｙをスレーブとする。
【００１５】
トポロジ発見のアルゴリズム
/*  ２つの島の間で、マスター−スレーブ関係を交渉する。
【００１６】
注釈：マスター−スレーブ交渉は、島のすべてのノードおよびポートに共通であるＢＩＤの交換に基づく  */
ＢＩＤを交換する。
【００１７】
0004519261.tif 000002
【００１８】
ＢＩＤ(ｘ)＝＝ＢＩＤ(ｙ)ならば、
/*  無作為に同じＢＩＤを選んでしまったか、またはループが存在する可能性がある。ループの存在についてのテストを実行する：ピングを実行した(ピンギング（pinging）という)後にループが存在しないことがわかったならば、それぞれの島は自身のＢＩＤをリフレッシュする（後に決める対応で）。「交換ＢＩＤ」
0004519261.tif 000003
マスターポートが、自身のバスについて調停する。
【００１９】
0004519261.tif 000004
【００２０】
このアルゴリズムの処理の例として、図１から図４は、ループを含む４個のノードのネットワークに対するアルゴリズムの経過を示している。
【００２１】
図１は、基本的な４ノードのトポロジを表す。物理的に接続されたノードはＢＩＤを交換し、アルゴリズムに従ってマスター−スレーブ（Ｍ，Ｓ）のポート指定が行われる。ノード間のリンクが破線で表されており、これは、リンクは物理的には存在するが、論理的に確立されていないことを示す。
【００２２】
図２は、ノード１が、自身のバスについて調停し該バスが許可された後の、図１のネットワークの状態を示す。その後、ノード１は、ノード２（ノード１のスレーブ）に対してそのバスを調停するよう要求し、そしてそれが成功している。したがって、ノード１および２の間に論理的にリンクを確立することができる。同じ処理が、ノード３および４の間にも生じる。
【００２３】
図３は、上側の一対のノード（島）および下側の一対のノード（島）がソフト・リセットを実行し、それぞれの島が最善努力型の固有ＢＩＤを生成した後の状態を示す。両方の島は、自分たちの接続を成長させようと試みる。すなわち、ノード１はノード４へのリンクを試験することにより、ノード２はノード３へのリンクを試験することにより試みる。ノード１および２は、自分たちのバスを調停する。しかし、ここで説明する例では、ノード１が勝って、ノード１に自身のバスが許可されたと仮定する（これは、ノード２−ノード３の対話を抑止する）。図２に関して上記説明した処理が、ノード１および４の間に生じる。
【００２４】
図４は、ノード１および４の間にリンクが確立された場合の状態を示す。ソフト・リセットが起こり、ノード１、２および４から構成される大きくなった島が、統合されたＢＩＤをとる。ノード２は、ノード３へのリンクを試みようとする。しかしながら、ノード２および３のＢＩＤは同じであるので、ノード２はループの存在を疑い、自身の他方のポート上にピング・パケットを送信する。ピング・パケットはノード３によって受け取られ、その受領が通知される。ノード２は、確立しようとしているノード２−ノード３のリンクがループを作るということに気づき、よってそのポートをディスエーブルする。
【００２５】
図３に示されるケースにおいて、両方の島が無作為に同じＢＩＤをとった場合には、アルゴリズムは、完全に対称的な島に出くわすこととなる。ノード１からノード４に表向き送られたピング・パケットは、ノード４と同じノードＩＤおよびＢＩＤを持つノード２によって受け取られて通知される。このことは、ノード３からノード２へのピング・パケットについても生じる。すると、このアルゴリズムはループの存在を仮定し、ノード１および４をリンクするポートをディスエーブルし、次にノード２および３をリンクするポートをディスエーブルする。したがって２つの島は、分離して孤立したままである。
【００２６】
しかしながら、この問題は、それぞれの島が真の固有ＢＩＤを持つ場合、またはバス上のどこであっても単一の固有ＢＩＤが存在する場合には生じない。後者の状態は、真の固有ＩＤが、トポロジを介してその優位性を最終的には伝えることができるために生じる。たとえば、別個の複数の島が同じＢＩＤをとったために行き詰まり状態が存在するとしても、固有ＢＩＤの島は、これら別個の複数の島のうちの１つを併合し、その後この新しい大きくなった島が、その固有ＢＩＤをとる。帰納的にすべての島がその固有ＢＩＤによって併合されるまで、この処理は続く。この処理を図５に示す。
【００２７】
図５は、同じ「ｂ」のＢＩＤ値をとった２つの島と、「ａ」の異なるＢＩＤ値を持つ他の島がある場合の構成を示す。「ｂ」のＢＩＤ値を持つ２つの島は、この明細書で前に説明した理由により分離したままである。しかし、「ａ」のＢＩＤ値を持つ島は、ＢＩＤ＝「ｂ」の島のうちの一方を併合することができる（点線で示されている）。その後、この新しい島は、「ｂ」のＢＩＤ値をとらなければ、他方の島を併合することができる。
【００２８】
「ループ」が検出された後でも、ソフト・リセットを使用することによりこの問題を支援することができる。
【００２９】
この発明は、以下の実施態様を含む。
【００３０】
（１）ネットワークにおいて論理的に接続されたノード・グループのそれぞれによる識別子の生成と、
前記論理的に接続されたノード・グループのうち物理的に接続されたノード・グループ間における識別子の交換と、
前記交換された識別子が異なる前記物理的に接続されたノード・グループ間における論理接続の確立と、
を含むネットワークにおけるノード間に論理接続を確立する方法。
【００３１】
（２）前記論理的に接続されたノード・グループが、１つのノードを含む上記（１）に記載の方法。
【００３２】
（３）一対の前記物理的に接続されたノード・グループについて交換された識別子が同じであるならば、ループをチェックするステップを含む上記（１）または（２）に記載の方法。
【００３３】
（４）ループが存在しないならば、上記識別子の生成および識別子の交換のステップが繰り返される請求項３に記載の方法。
【００３４】
（５）ループが存在するならば、前記一対の物理的に接続されたノード・グループ間の物理的な接続をディスエーブルする上記（３）に記載の方法。
【００３５】
（６）ａ／ノード間における論理接続を持たない物理接続から開始し、
ｂ／上記（１）から（５）のいずれかに記載されている論理接続を確立する方法を実行して、論理的に接続されたノード・グループを提供し、
ｃ／すべてのノードが論理的に接続されるまで、上記ｂ／のステップを繰り返し実行する、論理ループを持たないネットワーク・トポロジを確立する方法。
【図面の簡単な説明】
【図１】確立された論理リンクを持たない４ノードのトポロジの例を示す図。
【図２】この発明の実施形態に従う方法により確立された第１の論理リンクを持つ、図１のトポロジを示す図。
【図３】この発明の実施形態に従う方法の第２の繰り返し中における図１のトポロジを示す図。
【図４】この発明の実施形態に従う方法の第２の繰り返し後の図３のトポロジを示す図。
【図５】共通の識別子を持つ２つのノード・グループと、異なる識別子の１つのノード・グループを含むトポロジを示す図。
【図１】
0004519261.tif 000005
【図２】
0004519261.tif 000006
【図３】
0004519261.tif 000007
【図４】
0004519261.tif 000008
【図５】
0004519261.tif 000009