(57)【要約】【課題】  ネットワークを構成するノード及びブリッジの位相検出方法及び装置を提供する。【解決手段】  ネットワークを構成するノードにモード変更を要請するメッセージを送信する段階、ノードにチェックメッセージを送信する段階、ノードがチェックメッセージを受信した結果である受信ノード情報をノードから受信する段階、受信ノード情報で同じ回線に結合したノードの結合情報を計算する段階、及び結合情報と受信ノード情報とを通じてブリッジ及びノードの位相情報を抽出する段階を含むネットワークを構成するノード及びブリッジの位相検出方法。【選択図】      図３
2006295917.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）ネットワークを構成するノードにモード変更を要請するメッセージを送信する段階と、
（ｂ）前記ノードにチェックメッセージを送信する段階と、
（ｃ）前記ノードが前記チェックメッセージを受信した結果である受信ノード情報を前記ノードから受信する段階と、
（ｄ）前記受信ノード情報で同じ回線に結合したノードの結合情報を計算する段階と、
（ｅ）前記結合情報と前記受信ノード情報とを通じてブリッジ及びノードの位相情報を抽出する段階と、を含むネットワークを構成するノード及びブリッジの位相検出方法。
【請求項２】
前記ネットワークは、ホームネットワークを含む請求項１に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項３】
前記（ａ）段階のモード変更は、プロミスキャスモードに変更することを含む請求項１に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項４】
前記（ｂ）段階は、前記チェックメッセージをユニキャストで送信する段階を含む、請求項１に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項５】
（ａ）所定時間にノードにチェックメッセージを送信する段階と、
（ｂ）前記ノードが前記チェックメッセージを受信した結果である受信ノード情報を前記ノードから受信する段階と、
（ｃ）前記受信ノード情報で同じ回線に結合したノードの結合情報を計算する段階と、
（ｄ）前記ノードの結合情報と前記受信ノード情報とを通じてブリッジ及びノードの位相情報を抽出する段階と、を含むネットワークを構成するノード及びブリッジの位相検出方法。
【請求項６】
前記ネットワークは、ホームネットワークを含む請求項５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項７】
前記（ａ）段階において、前記モードは、プロミスキャスモードに変更するモードである請求項５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項８】
前記（ａ）段階は、前記チェックメッセージをユニキャストで送信する段階を含む、請求項５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項９】
（ａ）第１ノードからモード変更を要請するメッセージを受信してモードを変更する段階と、
（ｂ）前記変更したモードで第２ノードからチェックメッセージを受信する段階と、
（ｃ）前記受信したチェックメッセージの受信者情報を含む受信ノード情報を第３ノードに送信する段階と、を含むネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１０】
前記ネットワークは、ホームネットワークを含む請求項９に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１１】
前記（ａ）段階は、プロミスキャスモードに変更する段階を含む、請求項９に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１２】
前記（ｂ）段階で前記チェックメッセージは、ユニキャストで送信されたメッセージであり、
第４ノードを受信者とするチェックメッセージも受信する請求項９に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１３】
前記第４ノードは、同じ回線に連結されたノードである請求項１２に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１４】
前記第１ノード、第２ノード及び第３ノードのうち、２つ以上のノードが同じノードである請求項９に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１５】
（ａ）所定時間にモードを変更する段階と、
（ｂ）前記変更したモードで第１ノードからチェックメッセージを受信する段階と、
（ｃ）前記受信したチェックメッセージの受信者情報を集めて第２ノードに送信する段階と、を含むネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１６】
前記ネットワークは、ホームネットワークを含む請求項１５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１７】
前記（ａ）段階は、プロミスキャスモードに変更する段階を含む、請求項１５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１８】
前記（ｂ）段階で前記チェックメッセージは、ユニキャストで送信されたメッセージであり、
第３ノードを受信者とするチェックメッセージも受信する請求項１５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項１９】
前記第３ノードは、同じ回線に連結されたノードである請求項１８に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項２０】
前記第１ノードと前記第２ノードは、同じノードである請求項１５に記載のネットワークを構成するノード及びブリッジの位相検出方法。
【請求項２１】
モード変更を要請するメッセージとチェックメッセージとを生成するメッセージ生成部と、
前記メッセージをネットワークを構成するノードに送信する送信部と、
前記ノードが前記チェックメッセージを受信した結果である受信ノード情報を受信する受信部と、
前記受信ノード情報で同じ回線に結合したノードの結合情報を計算する結合情報計算部と、
前記結合情報と前記受信ノード情報とを通じてブリッジ及びノードの位相情報を抽出する位相情報抽出部と、を備えるネットワーク装置。
【請求項２２】
前記ネットワークは、ホームネットワークを含む請求項２１に記載のネットワーク装置。
【請求項２３】
前記モード変更を要請するメッセージは、他のノードにプロミスキャスモードに変更することを要請するメッセージを備える請求項２１に記載のネットワーク装置。
【請求項２４】
前記送信部は、前記チェックメッセージをユニキャストに送信する請求項２１に記載のネットワーク装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを構成するノード及びブリッジの位相検出方法及び装置に関する。
【背景技術】
【０００２】
通信ネットワークで、ブリッジは、１つのＬＡＮをイーサネット（登録商標）やトークンリングのように同じプロトコルを使っている他のＬＡＮと連結させる製品をいい、各ＬＡＮに連結されているステーションは、プロトコルを変えずとも、ＬＡＮを拡張させうる。ブリッジは、ＬＡＮ上の各メッセージを調べた後、同じＬＡＮに送信すべきメッセージは受け取り、連結されている他のＬＡＮに送信すべきメッセージは送信するように動作する。
【０００３】
ブリッジに連結されたネットワークにおいて、コンピュータやノードのアドレスは、実際位置と特別な相関関係はない。このような理由で、あらゆるメッセージはネットワーク上のあらゆるアドレスに送られるが、そのメッセージは、ただ目的地ノードによってのみ受取られる。
【０００４】
ブリッジは、如何なるアドレスが如何なるネットワークに位置するかをあらかじめ把握し、メッセージを正確に他のネットワークに伝達できるようにあらかじめ表を作成して置く。このような表をフィルタリングデータベースと称する。
【０００５】
ブリッジで連結されたネットワークは、一般的に常にＬＡＮに相互連結されており、あらゆるメッセージをブロードキャスティングするために、大型ネットワークである場合、不要なネットワークトラフィックが殺到することもある。このような理由で、インターネットのようなルーティングネットワークは、各ノードにアドレスを割り当てることによって、メッセージやパケットを、全方向ではない、一方向にのみ伝達させている。ブリッジは、ネットワークのデータリンク階層で、通信線路に沿ってあるネットワークからその次のネットワークにデータフレームをコピーすることを行う。
【０００６】
ブリッジに連結されて通信を行う各個体をノードという。ネットワークの構成時、複数のブリッジがノード間に存在できる。したがって、ネットワークを管理するためにブリッジの位相を管理し、如何なるブリッジに如何なるノードが連結されているかについての情報を得ることが必要である。
【０００７】
図１は、ブリッジの動作を簡略に示す例示図である。図１において、ブリッジ１００を中心にノード１  ２０１、ノード２  ２０２が同じ回線に連結されており、ノード３  ２０３は、他の回線に連結されている。一方、ブリッジ１００は、自身の両ポート（ポート１、ポート２）に連結されたノードが如何なるノードであるかをテーブルまたはデータベース化してフィルタリングデータベースに保存する。
【０００８】
ポート１には、ノード１、ノード２が連結されているという情報及びノード１、ノード２のＭＡＣアドレスが１９１に保存されている。ポート２には、ノード３が連結されているという情報とノード３のＭＡＣアドレスが１９２に保存されている。ブリッジ１００は、ポート１を通じて入ったデータがポート２に連結されたデータであるか否かを判断して、ポート２に連結されたノードに送るものであれば、ポート１を通じて入ったデータをポート２に送る。しかし、ポート２に連結されたノードでなければ、データは捨てる。もし、ポートが複数個存在し、特定ポートを通じて入ったデータが、前記特定ポート以外の他のポートに送られるデータがなければ、ブリッジがデータを捨てるメカニズムを取る。
【０００９】
もし、ノード１  ２０１がノード２  ２０２にデータを送信するならば、ブリッジ１００はポート１を通じて入ったデータをポート２に送信しない。ノード１  ２０１とノード２  ２０２は同一回線に連結されているので、ノード２  ２０２は、データを受け取ることができる。
【００１０】
一方、ノード１  ２０１がノード３  ２０３にデータを送信するならば、ブリッジ１００はポート２にノード３が連結されているという情報を１９２に保存しているので、受信したデータをポート２を通じて送信する。
【００１１】
過去ブリッジが連結された位相を検出するためにスパニングツリープロトコル（Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ）を使用した。位相を検出することは、ブリッジで構成されたネットワークでのループの発生を防止し、メッセージがループを通じて過多に伝達される現象を防止するためである。スパニングツリープロトコルについての詳細な情報は８０２．１ｄに明示されている。スパニングツリーの動作は図２のようである。
【００１２】
図２は、従来のネットワークでスパニングツリープロトコルが動作する過程を示す例示図である。まずルートブリッジ１０１を選択する。この際、ルートブリッジを選択するためには、多様な基準を適用しうる。例えば、最も優先順位の低いブリッジを選択し、２つ以上の場合、ＭＡＣアドレスが最も低いブリッジをルートとして選択する。そして、各ブリッジからルートへ行くための最適の経路を選択した後、ルートポートを選定する。
【００１３】
ルートポートは、ルートブリッジと連結されたポートを意味する。次いで、ルートブリッジまでの経路上にあるブリッジの費用をいずれも合わせてルートコストを計算する。そして、各ブロードキャストセグメントでルートブリッジまでの通信を担当する指定ブリッジ１０４を選定する。最後に、ルートポートと指定ポートとを除外したブロッキングポートを決定する。ブロッキングポートは、他のポートを通じてデータが伝送されるので、データを送る必要のないポートを意味する。指定ブリッジ１０４が存在するので、１０２ブリッジは、データを送る必要がないために、ブロッキングポートを有するようになる。
【００１４】
このような過程を通じて不要なメッセージが重複伝送されるループを防止し、最適の経路を通じてメッセージを送信しうる。
【００１５】
ところで、このようなプロトコルは、ブリッジの位相を検出し、ループを防止するためのものであり、ネットワークを構成するノードの位相を検出するためのものではない。また、ルータで使われるプロトコルはルーティングのみのために使われ、実際サブネットワーク内に存在するブリッジは検出できなかった。特に、ホームネットワークのような小規模のネットワークを構成するブリッジは、複雑なプロトコルを支援しない場合が多いので、簡単にブリッジ及びノードの位相を検出して、管理できる方案が必要である。
【特許文献１】日本特許公開平９−１８６７１６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明の技術的課題は、ネットワークを構成するブリッジ及びノードの位相情報を検出するところにある。
【００１７】
本発明の他の技術的課題は、ホームネットワークのような小規模のネットワークに存在するブリッジに複雑なプロトコルを付加せずに、ネットワークを管理するところにある。
【００１８】
本発明の目的は、以上で言及した目的に制限されず、言及されていない他の目的は下の記載から当業者に明確に理解されうる。
【課題を解決するための手段】
【００１９】
ネットワークを構成するノード及びブリッジの位相検出方法及び装置に関する。
【００２０】
本発明の一実施形態によるネットワークを構成するノード及びブリッジの位相検出方法は、ネットワークを構成するノードにモード変更を要請するメッセージを送信する段階、前記ノードにチェックメッセージを送信する段階、前記ノードが前記チェックメッセージを受信した結果である受信ノード情報を前記ノードから受信する段階、前記受信ノード情報で同じ回線に結合したノードの結合情報を計算する段階、及び前記結合情報と前記受信ノード情報とを通じてブリッジ及びノードの位相情報を抽出する段階を含む。
【００２１】
本発明の他の実施形態によるネットワークを構成するノード及びブリッジの位相検出方法は、第１ノードからモード変更を要請するメッセージを受信してモードを変更する段階、前記変更したモードで第２ノードからチェックメッセージを受信する段階及び前記受信したチェックメッセージの受信者情報を含む受信ノード情報を第３ノードに送信する段階を含む。
【００２２】
本発明の一実施形態によるネットワーク装置は、モード変更を要請するメッセージとチェックメッセージとを生成するメッセージ生成部、前記メッセージをネットワークを構成するノードに送信する送信部、前記ノードが前記チェックメッセージを受信した結果である受信ノード情報を受信する受信部、前記受信ノード情報で同じ回線に結合したノードの結合情報を計算する結合情報計算部、及び前記結合情報と前記受信ノード情報とを通じてブリッジ及びノードの位相情報を抽出する位相情報抽出部を含む。
【００２３】
その他の実施例の具体的な事項は詳細な説明及び図面に含まれている。
【発明の効果】
【００２４】
本発明を具現することによって、ネットワークを構成するブリッジ及びノードの位相情報を検出しうる。
【００２５】
本発明を具現することによって、ホームネットワークのような小規模のネットワークに存在するブリッジに複雑なプロトコルを付加せずもと、ネットワークを管理しうる。
【発明を実施するための最良の形態】
【００２６】
本発明の利点及び特徴、そしてこれを達成する方法は添付された図面に基づいて詳細に後述されている実施例を参照すれば明確になる。しかし、本発明は以下で開示される実施例に限定されるものではなく、この実施例から外れて多様な形に具現でき、本明細書で説明する実施例は本発明の開示を完全にし、本発明が属する技術分野で当業者に発明の範ちゅうを完全に報せるために提供されるものであり、本発明は請求項及び発明の詳細な説明により定義されるだけである。一方、明細書全体に亙って同一な参照符号は同一な構成要素を示す。
【００２７】
以下、添付された図面を参照して本発明の望ましい実施形態を詳細に説明する。
【００２８】
説明に先立って本明細書で使用する用語の意味を簡略に説明する。しかし、用語の説明は、本明細書の理解を助けるためのものであって、明示的に本発明を限定する事項として記載していない場合には、本発明の技術的思想を限定する意味として使用するものではないということを注意せねばならない。
・ノード
ノードはネットワークを構成するそれぞれのデバイスを通称する。コンピュータ、ノート型パソコン、ＦＡＸなどを含む。また、ホームネットワークにおいてホームネットワークに連結された家電製品、例えば、ＴＶ、冷蔵庫、オーディオなどを含む。
・プロミスキャスモード（Ｐｒｏｍｉｓｃｕｏｕｓ  ｍｏｄｅ）
このモードは、該当回線に送受信されるデータであるパケットまたはフレームが自身が受信者ではなくても、一旦そのフレームを受信するモードを意味する。したがって、他のノードが受信するフレームも受信する。通常、ネットワークを管理するか、トラフィックをモニタリングするエイジェントノードとして使用する。プロミスキャスモードになれば、１つの回線に物理的に連結されている他のノードに受信されるデータを感知しうる。すなわち、自身が連結されている回線を通じて送受信されるあらゆるデータパケットを読取り得るモードである。
・位相（Ｔｏｐｏｌｏｇｙ）
ノードの連結状態を意味する。位相情報はネットワークに結合した多様なデバイスが如何なる形で、如何なる方式で具現されたかを知らせる。位相情報を使用してネットワークの過負荷を防止し、伝送品質を適切に調節しうる。図３及び図４の連結された流れを通じて別のプロトコルを提供しなくても、ブリッジ及びノード間の位相が分かる。
【００２９】
図３は、本発明の一実施形態によるネットワークの位相とブリッジとの連結状態を検出するために送受信されるメッセージの流れを示す例示図である。
【００３０】
図３は、二つのブリッジに四つのノードが結合された状態である。ノードのうち、マスターのノード１  ２１１が開始メッセージをブロードキャストモードで伝送する。ブロードキャストモードは、あらゆるノードにデータを送るモードを意味する。開始メッセージはあらゆるノードに伝えられ、ネットワークを構成するノードはプロミスキャスモードに転換する。プロミスキャスモードに転換した結果、あらゆるノードは自身が結合された回線を通じて送受信されるパケット、フレームのようなあらゆるデータを読取り得る。受信モードを変更した後、マスターであるノード１  ２１１は、ネットワークに存在するあらゆるノードにユニキャストでチェックメッセージを送信する。ユニキャストで送るという意味は、受信者になるノードにだけメッセージを伝達することを意味する。ところが、ユニキャストモードで送るが、ネットワークのあらゆるノードはプロミスキャスモードに変更されたために、他のノードに伝達されるチェックメッセージを感知しうる。ノード１から説明すれば次の通りである。
【００３１】
まず、ノード１  ２１１がノード１  ２１１にユニキャストでメッセージを伝送する。ブリッジ１  １１１は、５０１回線と連結されたポート１にノード１が連結されていることを知っているために、ポート２にチェックメッセージを伝送しない。如何なるポートに如何なるノードが連結されているかについてのフィルタリングデータベースの構成については後述する。したがって、ノード１  ２１１がノード１  ２１１に送信したチェックメッセージはノード１  ２１１だけが感知しうる。
【００３２】
一方、ノード１  ２１１がノード２  ２１２にチェックメッセージを送る場合、これはブリッジ１  １１１を経て回線５０２を通じてノード２  ２１２に伝送される。したがって、回線５０２には、ノード１  ２１１が送ったチェックメッセージが伝送され、プロミスキャスモードであるノード３  ２１３もチェックメッセージを受信しうる。したがって、ノード２  ２１２とノード３  ２１３はノード２についてのチェックメッセージを受信したものとなる。一方、ブリッジ２  １１２は、ポート１に連結された回線５０２にノード２が連結されていることをフィルタリングデータベースなどを通じて知っているので、チェックメッセージをポート２を通じて５０３回線に伝達しない。その結果、ノード４  ２１４は、プロミスキャスモードであるが、５０３を通じてチェックメッセージが伝送されていないために、ノード２についてのチェックメッセージを受信できない。もちろん、ノード１  ２１１の場合、チェックメッセージを送るので、５０１回線を通じてプロミスキャスモードであるノード１  ２１１もチェックメッセージを受信しうる。
【００３３】
同じ原理で、ノード１  ２１１がノード３  ２１２にチェックメッセージを送る場合にも、ノード２  ２１２とノード３  ２１３が受信する。もちろん、ノード１  ２１１がチェックメッセージを送るので、５０１回線を通じてプロミスキャスモードであるノード１  ２１１もチェックメッセージを受信しうる。同じ原理で、ノード４  ２１４は、ブリッジ２  １１２を通じてチェックメッセージが伝えられないので、プロミスキャスモードとしてもノード３についてのチェックメッセージを受信できない。
【００３４】
次いで、ノード１  ２１１がノード４  ２１４にチェックメッセージを送信する。チェックメッセージは、５０１回線を通じてブリッジ１  １１１を通過して５０２回線を通じて再びブリッジ２  １１２を通過して５０３回線を通じてノード４  ２１４に受信される。したがって、５０１、５０２、５０３回線に連結されたノード１、ノード２、ノード３、ノード４いずれもノード４に対するチェックメッセージを受信する。
【００３５】
あらゆるノードに対するチェックメッセージの送信が終われば、チェックメッセージの受信結果を受信して、ブリッジ及びノードの構造を検討する。これについては図４で説明する。
【００３６】
図４は、本発明の一実施形態によるネットワークの位相とブリッジとの連結状態を検出するために、前記図３以後に送受信されるメッセージ及び動作を示す例示図である。
【００３７】
各ノード２１１、２１２、２１３、２１４は、プロミスキャスモード状態で自身が受信したチェックメッセージの受信者情報を集める。ノード１  ２１１は、ノード１、ノード２、ノード３、ノード４についてチェックメッセージを感知したので、これを集合で表せば、Ｓ１＝｛１、２、３、４｝となる。Ｓｉは、ｉ番目ノードが感知したチェックメッセージの受信ノード番号についての集合である。Ｓ２＝｛２、３、４｝となり、Ｓ３＝｛２、３、４｝、そしてＳ４＝｛４｝となる。各ノード２１１、２１２、２１３、２１４は、自身が集めた受信ノード情報であるＳ１、Ｓ２、Ｓ３、Ｓ４をマスターであるノード１  ２１１に送信する。ノード１  ２１１は、集めた情報から如何なるノードが１つの回線を構成し、如何なる回線間にブリッジが連結されているかを検討し、ブリッジの位相とノード間の連結状態を抽出する。
【００３８】
図４において、各ノードが送信する受信ノード情報は、チェックメッセージの受信者情報を集めたものである。ここで、チェックメッセージの受信者が自身であるか、あるいは自身ではなくても、同じ回線に連結されるか、自身が連結された回線を通じて送信される場合には、その受信者情報が受信ノード情報に追加される。したがって、受信ノード情報が同じ場合には、２ノードが同じ回線に連結されていることを意味する。
【００３９】
図３及び図４を参照して説明したように、ブリッジは、特定ポートに入ったデータを他のポートに送信するか、あるいはポートが複数個である場合、如何なるポートに送信するかを決定しなければならない。このためには、如何なるポートに如何なるノードが連結されているか、あるいは如何なるポートを通じて該当ノードが到達できるか否かを知っていなければならないが、このような情報が保存されているのが、フィルタリングデータベースである。ネットワークの運用中には、このような情報は、データ送受信によりあらかじめ保存されている。但し、ネットワークがリセットされるか、新たに動作する時には、このような情報がない。したがって、フィルタリングデータベースを通じて、そのような情報がないときは、ＡＲＰ（Ａｄｄｒｅｓｓ  Ｒｅｓｏｌｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）パケットを通じて、該当ノードのＭＡＣアドレスを受取りつつ、如何なるポートを通じてＡＲＰに対する応答が送受信されたかを判断する。説明の便宜上、図面からブリッジの左側はポート１であり、右側はポート２である。
【００４０】
例えば、図３において、ノード１がノード２にユニキャストでチェックメッセージを送ろうとする時、ノード２のＭＡＣアドレスを知らない場合、まずノード２のＩＰアドレスまたは識別子などをＡＲＰパケットに設定してノード１が送る。ＡＲＰパケットは、ネットワーク全体に伝達されうるが、これについての応答は、ノード２だけが行える。ＡＲＰパケットに対する応答は、ブリッジ１  １１１を通じて伝えられるので、ブリッジ１  １１１は、ポート２を通じてノード２が到達可能であるという結論を下しうる。その結果、ブリッジ１  １１１は、ポート２のフィルタリングデータベースにノード２の情報を設定する。
【００４１】
一方、ノード４に対してノード１がユニキャストでチェックメッセージを送る場合、やはりノード４のＭＡＣアドレスを知らない状態であるために、まずノード４のＩＰアドレスまたは識別子などをＡＲＰパケットに設定して、ノード１が送る。ＡＲＰパケットは、ネットワーク全体に伝達されうるが、これについての応答は、ノード４だけが行える。ＡＲＰパケットに対する応答は、ブリッジ２  １１２を通じて伝えられるので、ブリッジ２  １１２は、ポート２を通じてノード２が到達できるという結論を下しうる。その結果、ブリッジ２  １１２は、ポート２のフィルタリングデータベースにノード４の情報を設定する。同様に、ＡＲＰパケットに対する応答は、ブリッジ１  １１１を通じてノード１に伝えられるので、やはりブリッジ１  １１１のポート２もノード４が到達できるという情報を設定する。フィルタリングデータベースにノードの情報を満たせば、無駄に他の回線にデータを送信しなくなる。例えば、ノード１がノード３にデータを送信する時、ブリッジ１  １１１は、データを通過させるが、ブリッジ２  １１２はデータを通過させない。
【００４２】
図５は、本発明の一実施形態によるブリッジを検出するアルゴリズムである。集合Ｓ  ＳｅｔＳは、図４において、各ノードがノード１に送ったＳｉからなる集合である。図４の例で、Ｓは｛｛１、２、３、４｝、｛２、３、４｝、｛２、３、４｝、｛４｝｝である。Ｐは、あらゆるノード数ほどの集合を元素として有する集合であって、｛｛φ・・・・・・｛φ｝が基本値である。Ｆは、あらゆるノード数ほどの元素を有するフラッグ（Ｆｌａｇ）の集合であって、｛−１・・・・・・−１｝が基本値である。Ｐは、図５のアルゴリズムを通じてノードＩのような回線に連結されているノードの集合であるＰｉの集合である。すなわち、同じ回線に結合したノードの結合情報を意味する。Ｆは、各ノードが如何なるノードの集合に含まれるかに対する計算が完了したか否かを示す。アルゴリズムにより計算する前であるために、いずれも−１値を有する。Ｆｉは、ノードｉについての情報を示す。Ｐｉが求められれば、同じＰｉに存在する他のノードも同じ情報を有するようになるので、これ以上計算しない。
【００４３】
Ｓ１０でＦｉが０であるか否かを検討する。０ならば、既にｉノードが含まれた集合Ｐｉが求められたことを意味するので、次のノードであるノードｉ＋１に進行する。しかし、０がなければ、Ｐｉを求めるための過程であるＳ２０を行う。
【００４４】
Ｓ２１でＰｉにノードｉを追加する。ノードｉが結合した回線には、ノードｉが当然に結合されているからである。次いで、ノードｉ以後のノードに対して結合如何を検討する。この際、ノードｉ以後のノードから検査するのは、ｉ番目以前のノードは既にＳ２０過程を経たためである。ノードｉ以後のノードからノードｎまで検査を行うために、ｊという因子を使用する。
【００４５】
まず、Ｆｊが０であるか否かを検査する。０である場合、既にノードｊに対するＰｊは求められたことを意味する。これは、ｉ番目以前のノードであるｋがＰｋを求める過程でｊを含み、これ以上進行させる必要がないからである。しかし、Ｆｊが０でない−１であれば、まだ他のＰｋグループに属したものでないために、Ｓｊを比較する。
【００４６】
ＳｉとＳｊとが同じであれば、同じ回線に結合されているので、Ｆｊを０にし、Ｐｉにノードｊを追加する（Ｓ２２）。Ｆｊを０にして、今後の重複計算を防止する。そして、次回ノードについて、やはりＳ２０過程を行う。そのような結果によって同じ回線に連結されたノード同士でグループを作るようになる。図４で生成された結果によりＰを求めると、｛｛１｝、｛２、３｝、φ、｛４｝｝となる。Ｐの意味は、ノード１が単独で回線に連結されており、ノード２とノード３とが同じ回線に連結されており、ノード４も単独で回線に連結されていることを意味する。したがって、Ｐを通じて同じ回線に結合したノードの結合情報が分かる。
【００４７】
一方、如何なるノードが同じ回線を共有するかについての結果である、Ｐを求めたので、次にこれら回線と回線とを連結するブリッジの位相がどうなるかを計算する過程が必要である。
【００４８】
図６は、本発明の一実施形態によるブリッジの位相を計算するアルゴリズムである。図５のアルゴリズムを通じて求められたＰとＳとを用いてＢというｎｘｎ行列を満たしうる。Ｂ［ｉ］［ｊ］が０である場合、ＰｉとＰｊとがブリッジで連結されていないということを意味する。そして、Ｂ［ｉ］［ｊ］が１である場合、ＰｉとＰｊとがブリッジで連結されていることを意味する。したがって、Ｂ［ｉ］［ｊ］とＢ［ｉ］［ｊ］は、同じ値を有する。Ｓ３０で、ＰｉとＰｊとの間にブリッジの有無を検討する。ＳｉとＳｊとの差がＰｉである場合、ＰｉとＰｊは、連結されているので、Ｂ［ｉ］［ｊ］に１を割り当てる。
【００４９】
図６のアルゴリズムを通じて算出された結果は次の表と同じである。
【００５０】
【表１】
2006295917.tif 000003
前記結果を通じて、ノード１が連結された回線とノード２とノード３とが連結された回線間にブリッジが存在することが分かる。またノード２とノード３とが連結された回線とノード４が連結された回線間にも、ブリッジが存在することが分かる。行列Ｂを通じて如何なるブリッジが如何なる回線間に存在するかについての位相情報が分かる。また、前述したＰを通じて如何なるノードが同じ回線に連結されているかが分かるので、ＰとＢとを通じてノードとブリッジとの位相情報が分かる。
【００５１】
図５及び図６のアルゴリズムは、ノード間の回線連結を説明するための一実施形態としてのアルゴリズムであり、図５及び図６に開示されていない他の方法でも多様に具現されうる。
【００５２】
図７は、本発明の一実施形態によるマスターでの作業の順序を示すフローチャートである。まず、マスターとなるノードが決まらねばならない。これは、特定ノードとなるか、またはユーザの指定により変更され続ける。マスターは、モード変更を要請する開始メッセージを全体ノードに送信する（Ｓ１１０）。これは、ブロードキャスト方式で送信して他のノードのＭＡＣアドレスを知らなくても、伝送可能にする。開始メッセージを受けたノードは自身の受信モードをプロミスキャスモードに転換する。これにより、ノードは自身が結合した回線を通過するあらゆるパケットを受信しうる。
【００５３】
マスターとなるノードは、チェックメッセージを送信する（Ｓ１１２）。この際、チェックメッセージは、ユニキャストとして、１ノードに１つのチェックメッセージを送る。ユニキャストに送るということは、１つのノードだけを受信者としてメッセージを送ることを意味する。ところが、あらゆるノードがプロミスキャスモードに転換したので、自身の回線に結合された他のノードを受信者とするチェックメッセージも受信しうる。このように全体ノードに対して各々ユニキャストでチェックメッセージを送れば、各ノードは、自身を受信者とするか、あるいは自身が結合された、または連結された回線の他のノードを受信者とするチェックメッセージを受信でき、自身が受信したチェックメッセージの受信者情報を集めて受信ノード情報を生成する。
【００５４】
マスターは、他のノードからこの受信ノード情報を受信する（Ｓ１１４）。受信ノード情報の一実施形態は、図４でのＳｉである。そして、受信ノード情報においてマスターは、結合情報を計算する（Ｓ１１６）。結合情報の一実施形態としては、図５のアルゴリズムを通じて得たＰｉである。最後にマスターは、受信ノード情報と結合情報でノードとブリッジとの位相情報を抽出する（Ｓ１１８）。Ｓ１１８過程は、図６のアルゴリズムを一実施形態とする。
【００５５】
図７は、１つのノードがマスターとなって、開始メッセージを送信し、チェックメッセージを送信し、その結果を受信して、位相情報を抽出する過程をいずれも行っている。しかし、これは必ずしも１つのノードで行われる必要はない。例えば、第１ノードが特定時間に開始メッセージを送信しつつ、開始メッセージ内にチェックメッセージを送る第２ノードを指定する。そうすると、他のノードがプロミスキャスモードに変更した後で、第２ノードがチェックメッセージを送りうる。また、このチェックメッセージを受信して、各ノードが生成した受信ノード情報も第３ノードに伝送して、第３ノードが計算を行える。これは、チェックメッセージまたは開始メッセージに第３ノードのＩＰまたは識別情報を含むことで可能となる。したがって、図７で説明した過程は１つ以上のノードで分けて行える。
【００５６】
また、開始メッセージの伝送を必要としない。一定時間に位相情報を得るように各ノードを設定しうる。そうすると、一定時間になれば、あらゆるノードが自動でプロミスキャスモードに変更した後、マスターとなるノードがチェックメッセージを送る。そして、チェックメッセージを受信した各ノードから受信ノード情報を受信して、図７のＳ１１６、Ｓ１１８過程を行える。
【００５７】
図８は、本発明の一実施形態によるネットワーク位相情報を抽出するネットワーク装置の構成図である。
【００５８】
本実施例で使われる‘部’という用語、すなわち、‘モジュール’あるいは‘テーブル’はソフトウェアまたはＦＰＧＡまたはＡＳＩＣのようなハードウェア構成要素を意味し、モジュールは所定の役割を行う。しかし、モジュールはソフトウェアまたはハードウェアに限定されるものではない。モジュールはアドレッシングできる保存媒体に位置すべく構成されても良く、１つまたはそれ以上のプロセッサーを再生させるように構成されても良い。したがって、一例としてモジュールはソフトウェア構成要素、客体向けソフトウェア構成要素、クラス構成要素及びタスク構成要素のような構成要素と、プロセス、関数、属性、プロシージャー、サブルーチン、プログラムコードのセグメント、ドライバー、ファームウェア、マイクロコード、回路、データ、データベース、データ構造、テーブル、アレイ及び変数を含む。構成要素とモジュール内で提供される機能はより少数の構成要素及びモジュールに結合されるか、追加的な構成要素とモジュールにさらに分離されうる。のみならず、構成要素及びモジュールはデバイスまたは保安マルチメディアカード内の１つまたはそれ以上のＣＰＵを再生させるように具現されることもある。
【００５９】
ネットワーク装置は、他の装置とデータを送受信できる装置を意味する。ここでは、コンピュータ、ノート型パソコン、ＰＤＡ、ＦＡＸなどの通信が主な機能である場合以外にも、ホームネットワークを構成する冷蔵庫、テレビ、電子レンジなども通信のための機能を有する場合、ネットワーク装置に該当する。そして、ネットワーク装置は、前述したノードを意味する。ネットワーク装置２００は、メッセージ生成部２９１、送信部２９２、受信部２９３、結合情報計算部２９４及び位相情報抽出部２９５を含む。
【００６０】
メッセージ生成部２９１は、他のノードに位相抽出のためのモード変更を要請する開始メッセージと各ノードに送るチェックメッセージとを生成する。送信部２９２は、生成されたメッセージを他のノードに送る。一実施形態で、モード変更を要請する開始メッセージは、ブロードキャスト方式で送って、あらゆるノードが開始メッセージを受信可能にする。一方、各ノードに送られるチェックメッセージは、ユニキャストで送り、受信者に指定されたノードだけ受信させうる。但し、本発明の一実施形態によってプロミスキャスモードに変更されたノードは同じ回線に結合した他のノードを受信者とするチェックメッセージを受信しうる。
【００６１】
受信部２９３は、チェックメッセージを受信したノードが生成して伝送する受信ノード情報を受信し、これを結合情報計算部２９４に伝達する。結合情報計算部２９４は、受信ノード情報を通じていかなるノードが１つの回線に結合されたかを計算する。一実施形態として、図５で説明したアルゴリズムを行える。
【００６２】
各ノードが、結合された情報を得れば、位相情報抽出部２９５は、ブリッジとノードとの間の位相情報を抽出する。位相情報は、ブリッジが如何なるノードの結合の間に存在するか、そして、如何なるノードが如何なるブリッジに連結されているかなどの情報を意味する。
【００６３】
図８は、開始メッセージとチェックメッセージとを送信するマスターが位相情報を計算する役割も行う場合の一実施形態である。もし、マスターが開始メッセージとチェックメッセージを送りつつ、前記チェックメッセージを受信して位相情報を抽出するノードを指定するか、既に決まっている場合には、メッセージ生成部２９１を備えなくても良い。
【産業上の利用可能性】
【００６４】
本発明は、ネットワークを構成するノード及びブリッジの位相検出方法及び装置に関する技術分野に好適に適用されうる。本発明が属する技術分野で当業者ならば本発明がその技術的思想や必須特徴を変更せずとも他の具体的な形に実施されうるということが理解できるであろう。
【００６５】
したがって、前述した実施例は全ての面で例示的なものであって、限定的なものではないと理解せねばならない。本発明の範囲は詳細な説明よりは特許請求の範囲により表れ特許請求の範囲の意味及び範囲、そしてその等価概念から導かれるあらゆる変更または変形された形態が本発明の範囲に含まれると解釈されねばならない。
【図面の簡単な説明】
【００６６】
【図１】ブリッジの動作を簡略に示す例示図である。
【図２】従来のネットワークでスパニングツリープロトコルが動作する過程を示す例示図である。
【図３】本発明の一実施形態によるネットワークの位相とブリッジとの連結状態を検出するために送受信されるメッセージの流れを示す例示図である。
【図４】本発明の一実施形態によるネットワークの位相とブリッジとの連結状態を検出するために、前記図３以後に送受信されるメッセージ及び動作を示す例示図である。
【図５】本発明の一実施形態によるブリッジを検出するアルゴリズムである。
【図６】本発明の一実施形態によるブリッジの位相を計算するアルゴリズムである。
【図７】本発明の一実施形態によるマスターでの作業の順序を示すフローチャートである。
【図８】本発明の一実施形態によるネットワーク位相情報を抽出するネットワーク装置の構成図である。
【符号の説明】
【００６７】
１００                    ブリッジ
２００                    ノード
５０１、５０２、５０３    回線
【図１】
2006295917.tif 000004
【図２】
2006295917.tif 000005
【図３】
2006295917.tif 000006
【図４】
2006295917.tif 000007
【図５】
2006295917.tif 000008
【図６】
2006295917.tif 000009
【図７】
2006295917.tif 000010
【図８】
2006295917.tif 000011