(57)【特許請求の範囲】
【請求項１】
複数のブリッジによる冗長経路を含むネットワークに用いられるスパニングツリー用ブリッジにおいて、
ルートポートのリンクダウンを検出する機能と、
受信したＢＰＤＵの情報から受信ポートの代表ブリッジの変化を検出する機能と、
前記ルートポートのリンクダウンを検出したとき又は前記代表ブリッジの変化を検出したときにルートブリッジに就任する機能と、
前記代表ブリッジの変化を検出したときにそのブリッジの受信ポートの閉鎖ポートをフォワーディング状態に遷移させる機能と、
他のブリッジから自身のＢＰＤＵに優るＢＰＤＵを受信したときに代表ブリッジが変化している旨のＴＣＮ−ＢＰＤＵを送信し、ＴＣＮ−ＢＰＤＵを受信したときに直ちにそのＴＣＮ−ＢＰＤＵを伝播し、そのブリッジがルートブリッジのときには直ちにＴＣ検出フラグをセットしたＢＰＤＵを全ポートに送信する機能と、
前記ＴＣフラグがセットされたＢＰＤＵを受信したときに直ちにそのＢＰＤＵを伝送して自身のブリッジフォワーディングテーブルの内容を削除する機能とを備えたことを特徴とするスパニングツリー用ブリッジ。
【請求項２】
前記代表ブリッジの変化を検出したときにルートブリッジに就任したブリッジは、他のブリッジから自身のＢＰＤＵより優れたＢＰＤＵを受信したときにルートブリッジでなくなることを特徴とする請求項１記載のスパニングツリー用ブリッジ。
【請求項３】
複数のブリッジによる冗長経路を含むネットワークに用いられるスパニングツリー用ブリッジの経路変更方法において、
ルートポートのリンクダウンを検出したときにルートブリッジに就任し、このルートブリッジを就任した旨のルートブリッジ情報に変更したＢＰＤＵを送信するステップと、
自身の受信ポートの持つルートブリッジ情報よりも劣るルートブリッジ情報を持つＢＰＤＵを受信して代表ブリッジの変化を検出したときにルートブリッジに就任して自身のＢＰＤＵを送信し、このときルートブリッジに就任したブリッジの受信ポートのうち閉鎖ポートを直ちにフォワーディング状態に遷移させるステップと、
他のブリッジから自身のＢＰＤＵに優るＢＰＤＵを受信したときに代表ブリッジが変化している旨のＴＣＮ−ＢＰＤＵを送信するステップと、
前記ＴＣＮ−ＢＰＤＵを受信したときに直ちにそのＴＣＮ−ＢＰＤＵを各ブリッジに伝播し、そのブリッジがルートブリッジであるときには直ちにＴＣ検出フラグをセットしたＢＰＤＵを全ポートに送信するステップと、
前記ＴＣ検出フラグがセットされたＢＰＤＵを受信したときに直ちにそのＢＰＤＵを伝送して自身のフォワーディングテーブルの内容を削除するステップとを含むことを特徴とするスパニングツリー用ブリッジを用いた経路変更方法。
【請求項４】
前記代表ブリッジの変化を検出したときにルートブリッジに就任したブリッジは、他のブリッジから自身のＢＰＤＵより優れたＢＰＤＵを受信したときにルートブリッジでなくなることを特徴とする請求項３記載のスパニングツリー用ブリッジを用いた経路変更方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のブリッジによる冗長経路を含むネットワークに用いられるスパニングツリー用ブリッジ及びそれを用いた経路変更方法に関する。
【０００２】
【従来の技術】
複数のブリッジによる冗長経路を含むネットワークでは、経路の決定にスパニングツリープロトコルが用いられる。
【０００３】
例えば図７に示すように、ＬＡＮ１とＬＡＮ２がブリッジＡによって接続され、ＬＡＮ１にパソコン等のノードｎ１が接続され、更にＬＡＮ２にＨＵＢが接続されたネットワークの場合、ノードｎ１から送信されたパケットは、ＬＡＮ１→ブリッジ→ＬＡＮ２→ＨＵＢを介してＨＵＢに接続されるパソコン等のノードｎ２を含むブロードキャストドメインの全てのノードに送信されることになる。そして、このようなネットワークに対して、ＬＡＮ１とＬＡＮ２との間にブリッジＡと並列にＨＵＢを接続すると、ノードｎ１から送信されたパケットは、ネットワーク上をループし、その結果、ノードｎ１以外のノード（ノードｎ１を除くその他のブロードキャストドメインのノード）からパケットを送信することができなくなる。
【０００４】
そこで、図７に示すようなブリッジＡとＨＵＢのみでネットワークを構成した場合、あるノードから送信されたパケットがネットワーク上をループするのを取り除くためにスパニングツリーが用いられる。
【０００５】
また、図８に示すように、パソコン等のノードｎ１が接続されたＬＡＮ１と、ＨＵＢが接続されたＬＡＮ２との間に２つのブリッジＡ，Ｂを並列に接続し、ノードｎ１とＨＵＢに接続されたパソコン等の各ノードｎ２，ｎ３，ｎ４，…との間で通信を行う場合、通常は一方のブリッジＡを使用して通信を行い、このブリッジＡがリンクダウンしたときに他方のブリッジＢを使用して通信を行うことでネットワークに冗長性を持たせるためにスパニングツリーが用いられる。
【０００６】
ここで、スパニングツリーの基本的なアルゴリズムは下記（１）〜（５）からなる。
【０００７】
（１）Configuration Bridge Protocol Data Units（以下ＢＰＤＵ）という特別なフレームをブリッジ間で交換する。交換したＢＰＤＵにもとづいて以下の作業を行う。
（２）ネットワークのルートブリッジを選択する。ルートブリッジはブリッジ接続されたＬＡＮ全体に１個だけ存在する。
（３）各ブリッジはルートブリッジに至る最短経路を計算する（ルートブリッジへの最短経路を与えるポートはルートポートと呼ばれる）。
（４）各ＬＡＮに対し、そのＬＡＮに接続されているブリッジから「指定ブリッジ（designated bridge)」を選択する。
（５）各ブリッジはスパニングツリーに属するポート（指定ポート：designated port)とそうでないポート（閉鎖ポート：blocked port) を選択する。閉鎖ポートで受信したデータフレームはすべて廃棄される。また、閉鎖ポートからのフレームの送信は一切行われない。なお、受信したＢＰＤＵは一切フォワーディングされない。
【０００８】
上述したＢＰＤＵのデータ部分には少なくともルートＩＤ、ブリッジＩＤ、ルートパス・コストが含まれている。ルートＩＤは、ルートブリッジ（と仮定されたブリッジ）のＩＤであり、ブリッジのＭＡＣアドレスおよび管理者が指定する優先度から作成される。ブリッジＩＤは、ＢＰＤＵを送信したブリッジＩＤであり、ブリッジのＭＡＣアドレスおよび管理者が指定する優先度から作成される。ルートパス・コストは、ＢＰＤＵを送信したブリッジからルートブリッジに至る最短（と思われる）経路のコストである。
【０００９】
初期状態（電源投入時）では、各ブリッジは自分自身がルートブリッジであり、ルートパス・コストは０であると仮定する。各ブリッジは、ＢＰＤＵの初期値をすべてのポートに送信すると同時に、ほかのブリッジから送信されたＢＰＤＵをすべてのポートから受信する。ブリッジがあるポートからよりよいＢＰＤＵを受信した場合、ブリッジはそのポートに対するＢＰＤＵの送信を停止し、その後自分自身が送信するＢＰＤＵの値を変更する。これにより、スパニングツリーが安定状態になった場合、各ＬＡＮのなかで１個のブリッジのみがＢＰＤＵを送信するようになる。
【００１０】
上記ＢＰＤＵの優劣は、例えばＢＰＤＵ１とＢＰＤＵ２がある場合、下記（１）〜（４）の規則にもとづいて優劣の判断がなされる。
（１）ＢＰＤＵ１のルートＩＤがＢＰＤＵ２のルートＩＤよりも数値的に小さい場合には、ＢＰＤＵ１はＢＰＤＵ２よりもよいＢＰＤＵと判断される。
（２）ＢＰＤＵ１のルートＩＤがＢＰＤＵ２のルートＩＤと数値的に等しい場合には、ＢＰＤＵ１のルートパス・コストがＢＰＤＵ２のルートパス・コストよりも小さければ、ＢＰＤＵ１はＢＰＤＵ２よりもよいＢＰＤＵと判断される。
（３）ＢＰＤＵ１のルートＩＤがＢＰＤＵ２のルートＩＤと数値的に等しく、かつＢＰＤＵ１のルートパス・コストがＢＰＤＵ２のルートパス・コストと等しい場合には、ＢＰＤＵ１のブリッジＩＤがＢＰＤＵ２のブリッジＩＤよりも数値的に小さければ、ＢＰＤＵ１はＢＰＤＵ２よりもよいＢＰＤＵと判断される。
（４）ＢＰＤＵ１のルートＩＤがＢＰＤＵ２のルートＩＤと数値的に等しく、かつＢＰＤＵ１のルートパス・コストがＢＰＤＵ２のルートパス・コストと等しく、かつＢＰＤＵ１のブリッジＩＤがＢＰＤＵ２のブリッジＩＤと数値的に等しい場合には、ＢＰＤＵ１のポートＩＤがＢＰＤＵ２のポートＩＤよりも小さければ、ＢＰＤＵ１はＢＰＤＵ２よりもよいＢＰＤＵと判断される。
【００１１】
そして、各ブリッジは自身のＢＰＤＵの初期値と、全ポートから受信した他のブリッジからのＢＰＤＵを比較し、もっともよいＢＰＤＵからルートＩＤを選択する。次に、各ブリッジは、〈ルートパス・コスト〉＝〈もっともよいＢＰＤＵ中のルートパス・コスト〉＋パスコストに従って自分自身のルートパス・コストを計算する。なお、パスコストとは、各ポートが個別にもっているルートへのコストであり、その値は管理者が設定可能である。
【００１２】
いったんルートＩＤ、ルートポート、ルートパス・コストが定まると、これらの値にもとづいて各ブリッジはそれ以降に自分自身が送信するＢＰＤＵの内容を更新する。さらに、更新した自分自身のＢＰＤＵとルートポート以外のポートから受信したＢＰＤＵを比較し、ルートポート以外の各ポートに対して、自分自身が指定ブリッジになるかどうか判断する。指定ブリッジとなったポートは指定ポートと呼ばれ、指令ブリッジとならなかったポートは閉鎖ポートと呼ばれる。
【００１３】
そして、ルートポート、指定ポート、閉鎖ポートに対する、ＢＰＤＵの送信およびデータフレームのフォワーディングは、ルートポートではＢＰＤＵを送信せずデータフレームをフォワーディングし、指定ポートではＢＰＤＵを送信してデータフレームをフォワーディングし、閉鎖ポートではＢＰＤＵを送信せずデータフレームをフォワーディングしない。
【００１４】
以上のようにしてスパニングツリーがいったん構成されると、各ブリッジは下記の（１）〜（４）に示す定常動作を行う。この定常動作は、ブリッジの故障や新たなブリッジの追加によっていったん構成したスパニングツリーを再構成するために必要な動作である。
【００１５】
（１）ＢＰＤＵには、「message age 」という要素が含まれている。この値は、ルートブリッジがこのＢＰＤＵに対応するＢＰＤＵを生成してからの経過時間を示す。
（２）ルートブリッジは、全ポートに対して、定期的に自分自身のＢＰＤＵを送信する。このとき、message age は０に設定される。
（３）各ブリッジは受信したＢＰＤＵを保存する。また、各ポートに保存されているＢＰＤＵのmessage age の値を時間の経過とともに増加させる（message age タイマー）。
（４）ルートブリッジ以外のブリッジは、ルートポートからＢＰＤＵを受信すると、自分自身のＢＰＤＵを全指定ポートに送信する。この際、message age の値には、ルートポートのmessage age と等しいかそれより大きく、受信ＢＰＤＵのmessage age よりも大きい値が使われる。
【００１６】
ここで、スパニングツリーの再構成は下記（１）、（２）に示すような場合に発生する。
【００１７】
（１）保存されているＢＰＤＵのmessage age タイマーがタイムアウトした場合（max age を超えた場合）
（２）あるポートに保存してあるＢＰＤＵよりもよいＢＰＤＵや、message age の値が小さなＢＰＤＵを同じポートから受信した場合
上記の事象が発生した場合、ブリッジはルートＩＤ、ルートコスト、ルートポートの再計算を行う。
【００１８】
ところで、スパニングツリーの構成（再構成）が開始されてからネットワーク上のすべてのブリッジが定常状態にならないうちに、データフレームの送信を行うのは非常に危険である。それは、スパニングツリー構成中には一時的なループが発生している可能性があるためである。したがって、各ブリッジは自分自身の指定ポートを決定してもすぐにはデータフレームのフォワーディングを開始しない。
【００１９】
ブリッジの各ポートの状態としては下記の３種類がある。
（１）listening ：データフレームに関する作業は何もおこなわない。
（２）learning：始点ＭＡＣアドレスの学習はおこなうがフォワーディングはおこなわない。
（３）forwarding：データフレームのフォワーディングもおこなう。
listening 状態およびlearning状態の長さはforward delay と呼ばれ、ルートブリッジがその値を決定し、ＢＰＤＵにその値を入れて各ブリッジに伝える。  また、listening 状態およびlearning状態で用いられるタイマーはforwardingタイマーを呼ばれる。
【００２０】
スパニングツリーの再構成が発生すると、ホストの位置が変化し、旧い学習テーブルの内容が正しくなくなる場合がある。このため、スパニングツリーに対応しているブリッジは学習テーブルaging タイマーのタイムアウト値として以下の２種類の値をもっている。
（１）通常値：この値は数分といった長い時間に設定される。
（２）トポロジー変化後に使用される値：この値はforward delay の値と同じ値になる。
【００２１】
ブリッジはスパニングツリーの再構成を検知すると、一定期間学習テーブルaging タイマーのタイムアウト値をforward delay と同じ値に設定する。
【００２２】
ところで、スパニングツリー・アルゴリズムは、下記（１）〜（５）に示すように、スパニングツリーの再構成が発生したことをすべてのブリッジに通知する仕組みをもっている。
【００２３】
（１）ブリッジがトポロジーの変化を検知すると、そのブリッジはＴＣＮ−ＢＰＤＵ(Topology Change Notification ＢＰＤＵ）と呼ばれるフレームをルートポートにhello time間隔で送信する。ルートポートからＴＣＡ(Topology Change Acknowledgment)フラグが立ったＢＰＤＵを受信するまでこれを継続する。
（２）ＴＣＮ−ＢＰＤＵを受信したブリッジもまた、ＴＣＮ−ＢＰＤＵをそれ自身のルートポートに送信する。一方、ＴＣＮ−ＢＰＤＵを受信したポートに対しては次のＢＰＤＵの送信時に、ＢＰＤＵのＴＣＡフラグを立ててＢＰＤＵを送信する。
（３）ルートブリッジはＴＣＮ−ＢＰＤＵを受信するか、あるいは自分自身のポートの状態が変化した場合、その時点からmax age ＋forward delay 時間のあいだＴＣ(Topology Change) フラグの立ったＢＰＤＵを送信する。
（４）ＴＣフラグの立ったＢＰＤＵをルートポートから受信したブリッジは、自分自身のＢＰＤＵについてもＴＣフラグを立てて送信する。これは、ルートポートからＴＣフラグが立っていないＢＰＤＵを受信するまで継続する。
（５）ルートポートからＴＣフラグの立ったＢＰＤＵを受信しているあいだ、ブリッジはforward delay の値を学習テーブルaging タイマーのタイムアウト値として用いる。
【００２４】
このように、スパニングツリーは、冗長なブリッジ・ネットワークにおいてループを自動的に取り除くとともに、機器の故障やケーブル不良などによるネットワーク・トポロジーの変更を自動的に検知し、ループが発生しないようにネットワーク・トポロジーを動的に変更するアルゴリムである。
【００２５】
ところで、スパリングツリーは、ネットワークにループを作らないように働くが、ルートポートが何らかの原因（例えばケーブルの繋ぎ変え、ポートの無効設定、通信障害による通信経路の変更など）でリンクダウンした場合、停止していた閉鎖ポートを復帰させてスパニングツリーを再構成する動作が実行される。その場合の動作を図９のネットワークを例にとって説明する。
【００２６】
図９に示すネットワークは、３つのブリッジＡ，Ｂ，Ｃが互いに接続されたもので、定常状態においてブリッジＡがルートブリッジ、ブリッジＢが代表ブリッジ、ブリッジＢに向かうブリッジＣのポートを閉鎖ポートとして通信が行われるようにスパニングツリーが構成されているものとする。なお、各ブリッジに接続されるノードは、説明に必要な部分のみを図示し、その他の部分については省略している。
【００２７】
図９のネットワークでは、ブリッジＢに接続されたノードｎ１とブリッジＣに接続されたノードｎ２との間で通信を行った場合、ブリッジＢのノードｎ１からの信号はブリッジＡ、ブリッジＣを通ってブリッジＣのノードｎ２に送られることになる。
【００２８】
今、ブリッジＡとブリッジＢとの間が何らかの原因で不通になると、そのままではブリッジＢに接続されたノードｎ１とブリッジＣに接続されたノードｎ２との間の通信が行えなくなるので、ブリッジＣの閉鎖ポートを開き、通信経路を変更してスパニングツリーを再構成する必要がある。
【００２９】
そこで、従来のスパニングツリーでは、ブリッジＡとブリッジＢとの間が不通になると、ブリッジＢは、ルートブリッジであるブリッジＡから定期的に送信されるＢＰＤＵを受信しなくなる。これにより、ブリッジＢは、ブリッジＡとの間のリンクダウンを検出する。ブリッジＢがリンクダウンを検出すると、ブリッジＢからブリッジＣにＢＰＤＵが送信されなくなる。これにより、ブリッジＣは、本来ブリッジＡ、ブリッジＢを経由して送信されてくるＢＰＤＵを受信しなくなる。そして、ブリッジＣは、ブリッジＢからＢＰＤＵを受信しなくなった時点からの経過時間が予め設定された指定時間を経過すると、ブリッジＢとブリッジＣとの間の通信が可能となるように閉鎖ポートを徐々に開く動作を開始する。そして、ブリッジＣの閉鎖ポートが完全に開くと、ブリッジＢに接続されたノードとブリッジＣに接続されたノードとの間の通信が可能となる。
【００３０】
【発明が解決しようとする課題】
しかしながら、従来の方法では、リンクダウンを検出した後、閉鎖ポートを開いてブリッジＢに接続されたノードｎ１とブリッジＣに接続されたノードｎ２との間の通信が可能となるまでに時間を要し、通信の中断からの復帰が遅く、通信効率の低下を招いていた。
【００３１】
そこで、本発明は、上記問題点に鑑みてなされたものであり、通信経路の変更が生じた場合でも瞬時に対応して通信の中断からの復帰を早めることができるスパニングツリー用ブリッジ及びそれを用いた経路変更方法を提供することを目的としている。
【００３２】
【課題を解決するための手段】
上記目的を達成するため、請求項１の発明は、複数のブリッジによる冗長経路を含むネットワークに用いられるスパニングツリー用ブリッジにおいて、
ルートポートのリンクダウンを検出する機能と、
受信したＢＰＤＵの情報から受信ポートの代表ブリッジの変化を検出する機能と、
前記ルートポートのリンクダウンを検出したとき又は前記代表ブリッジの変化を検出したときにルートブリッジに就任する機能と、
前記代表ブリッジの変化を検出したときにそのブリッジの受信ポートの閉鎖ポートをフォワーディング状態に遷移させる機能と、
他のブリッジから自身のＢＰＤＵに優るＢＰＤＵを受信したときに代表ブリッジが変化している旨のＴＣＮ−ＢＰＤＵを送信し、ＴＣＮ−ＢＰＤＵを受信したときに直ちにそのＴＣＮ−ＢＰＤＵを伝播し、そのブリッジがルートブリッジのときには直ちにＴＣ検出フラグをセットしたＢＰＤＵを全ポートに送信する機能と、
前記ＴＣフラグがセットされたＢＰＤＵを受信したときに直ちにそのＢＰＤＵを伝送して自身のブリッジフォワーディングテーブルの内容を削除する機能とを備えたことを特徴とする。
【００３３】
請求項２の発明は、請求項１のスパニングツリー用ブリッジにおいて、
前記代表ブリッジの変化を検出したときにルートブリッジに就任したブリッジは、他のブリッジから自身のＢＰＤＵより優れたＢＰＤＵを受信したときにルートブリッジでなくなることを特徴とする。
【００３４】
請求項３の発明は、複数のブリッジによる冗長経路を含むネットワークに用いられるスパニングツリー用ブリッジの経路変更方法において、
ルートポートのリンクダウンを検出したときにルートブリッジに就任し、このルートブリッジを就任した旨のルートブリッジ情報に変更したＢＰＤＵを送信するステップと、
自身の受信ポートの持つルートブリッジ情報よりも劣るルートブリッジ情報を持つＢＰＤＵを受信して代表ブリッジの変化を検出したときにルートブリッジに就任して自身のＢＰＤＵを送信し、このときルートブリッジに就任したブリッジの受信ポートのうち閉鎖ポートを直ちにフォワーディング状態に遷移させるステップと、
他のブリッジから自身のＢＰＤＵに優るＢＰＤＵを受信したときに代表ブリッジが変化している旨のＴＣＮ−ＢＰＤＵを送信するステップと、
前記ＴＣＮ−ＢＰＤＵを受信したときに直ちにそのＴＣＮ−ＢＰＤＵを各ブリッジに伝播し、そのブリッジがルートブリッジであるときには直ちにＴＣ検出フラグをセットしたＢＰＤＵを全ポートに送信するステップと、
前記ＴＣ検出フラグがセットされたＢＰＤＵを受信したときに直ちにそのＢＰＤＵを伝送して自身のフォワーディングテーブルの内容を削除するステップとを含むことを特徴とする。
【００３５】
請求項４の発明は、請求項３のスパニングツリー用ブリッジを用いた経路変更方法において、
前記代表ブリッジの変化を検出したときにルートブリッジに就任したブリッジは、他のブリッジから自身のＢＰＤＵより優れたＢＰＤＵを受信したときにルートブリッジでなくなることを特徴とする。
【００３６】
【発明の実施の形態】
図１は本発明によるスパニングツリー用ブリッジの内部機能の概略を示すブロック図である。
【００３７】
図１に示すように、スパニングツリー用ブリッジ１は、他のブリッジに接続されるポート２を有し、リンクダウン検出機能、代表ブリッジ変化検出機能、トポロジー変化検出機能、閉鎖ポート制御機能、ルートブリッジ就任機能、テーブルクリア機能といった各機能を個々に備えている。
【００３８】
なお、代表ブリッジとは、相互に接続されるブリッジの中で相対的に１段上位に位置するブリッジである。
【００３９】
まず、各ブリッジ間で送受信されるＢＰＤＵについて図２（ａ）〜（ｃ）を参照しながら説明する。図２（ａ）はブリッジ間で送受信されるＢＰＤＵのフレーム・フォーマットを示す図、図２（ｂ）はＢＰＤＵのデータに含まれるフラグのフレーム・フォーマットを示す図、図２（ｃ）はＢＰＤＵのデータに含まれるルートＩＤ、ブリッジＩＤのフレーム・フォーマットを示す図、図２（ｄ）はトポロジーの変化を検出したときに送信されるＴＣＮ−ＢＰＤＵのフレーム・フォーマットを示す図である。
【００４０】
図２（ａ）に示すように、ＢＰＤＵは、ヘッダ部分とデータ部分から構成される。図２（ｂ）に示すように、フラグは、ＴＣＡ、未使用領域、ＴＣから構成される。ＴＣＡのｂｉｔが立ったＢＰＤＵをルートポートから受信したブリッジは、ルートポートへのＴＣＮ−ＢＰＤＵの送信を停止する。ＴＣのｂｉｔが立ったＢＰＤＵをルートポートから受信したブリッジは、ＴＣフラグの立っていないＢＰＤＵを受信するまで、学習テーブルaging タイマーのタイムアウト値をforward delay の値に設定し、自分自身もＴＣフラグの立ったＢＰＤＵを送信する。
【００４１】
図２（ｃ）に示すように、ルートＩＤおよびブリッジＩＤは、上位２octet は管理者が設定するpriority、下位６octet はブリッジのＭＡＣアドレスである。ルートＩＤおよびブリッジＩＤは、上位２octet の管理者が設定するpriorityが優先され、ＭＡＣアドレスを含めた全体の大小によってブリッジの上位下位の判別ができるようになっている。例えば各ブリッジのＢＰＤＵのルートＩＤの上位２octet をデフォルトの状態とした場合、ルートＩＤのＭＡＣアドレスの一番小さいブリッジがルートブリッジとなる。
【００４２】
その他、ルートパス・コストは、ルートへの最短（と思われる）コストである。ポートＩＤは、上位１octet は管理者が設定するpriority、下位１octet はブリッジに固有のＩＤである。
【００４３】
message age は、ルートブリッジからの経過時間を示し、単位は１／２５６秒である。したがって、この値が２５６の場合、ルートは１秒前にこのＢＰＤＵに対応するＢＰＤＵを送信したことになる。
【００４４】
max age は、ＢＰＤＵの有効期間を示し、単位は１／２５６秒である。また、hello timeは、ルートブリッジがＢＰＤＵを送信する時間間隔を示し、単位は１／２５６秒である。すなわち、ルートブリッジはhello time間隔でＢＰＤＵを送信する。
【００４５】
forward delay は、listening の期間、learningの期間、スパニングツリーの再構成が発生した場合の学習テーブルaging タイマーに用いられるパラメータを示し、単位は１／２５６秒である。
【００４６】
トポロジーチェンジタイマーは、フラグのＴＣを立てる期間を計測するタイマーである。
【００４７】
次に、各ブリッジ１が備える機能について説明する。まず、ルートポートのリンクダウン検出機能は、ルートブリッジに向かう方向のポート（ルートポート）の情報によってリンクダウンを検出する機能である。更に説明すると、ポート間が接続されているときは導通しており、ポート間の接続が外れたときに発生する割込信号によってリンクダウンを検出している。なお、このリンクダウンの検出は、ポーリングでも可能である。ブリッジは、ルートポートのリンクダウンを検出すると、自身がルートブリッジを主張するＢＰＤＵ（ルートＩＤのＭＡＣアドレスを自身のアドレスに書き換えたもの）を代表ポートから送信する。
【００４８】
代表ブリッジの変化検出機能は、そのブリッジに接続されている他のブリッジから受信するＢＰＤＵ情報と、自身のＢＰＤＵ情報とを比較して代表ブリッジの変化を検出する機能である。更に説明すると、他のブリッジから受信するＢＰＤＵ内のルートＩＤと、自身のＢＰＤＵ内のルートＩＤとを比較し、他のブリッジから受信するＢＰＤＵ内のルートＩＤが自身のルートＩＤの情報よりも悪いルートＩＤであるときに代表ブリッジが変化したと判断している。
【００４９】
トポロジー変化検出機能は、そのネットワークにおいてトポロジーが変化しているか否かを検出する機能である。更に説明すると、ブリッジは、トポロジーの変化を検出すると、図２（ｄ）に示すＴＣＮ−ＢＰＤＵをルートポートにhellon time 間隔で送信する。このＴＣＮ−ＢＰＤＵを受信したブリッジは、そのＴＣＮ−ＢＰＤＵを直ちにルート方向に伝播し、各ブリッジを経由して最終的にルートブリッジに送られる。そして、ルートブリッジは、ＴＣＮ−ＢＰＤＵを受信すると、自身のＢＰＤＵのフラグのＴＣを立て、すなわちＴＣ検出フラグをセットしてＢＰＤＵを送信する。このＴＣ検出フラグがセットされたＢＰＤＵを受信したブリッジは、そのＢＰＤＵを直ちに伝播し、各ブリッジに送られる。
【００５０】
閉鎖ポート制御機能は、リンクダウン検出機能によりルートポートのリンクダウンが検出された後、代表ブリッジの変化検出機能により代表ブリッジが変化したと判断したときに、元々閉鎖ポートに設定されたブリッジの閉鎖ポートを直ちに開けてフォワーディング状態に遷移させる制御を行う機能である。
【００５１】
ルートブリッジ就任機能は、リンクダウン検出機能によりルートポートのリンクダウンを検出したときに、このリンクダウンを検出したブリッジがルートブリッジを就任する機能である。また、ルートブリッジ就任機能は、代表ブリッジの変化検出機能により代表ブリッジが変化したと判断したときに、この代表ブリッジの変化を検出したブリッジがルートブリッジに就任する機能でもある。
【００５２】
なお、ルートブリッジ就任機能によりルートブリッジに就任したブリッジは、他のブリッジから受信するＢＰＤＵが自身のＢＰＤＵよりも良いものを受信した場合にはルートブリッジの就任が解除される。
【００５３】
フォワーディングテーブルのテーブルクリア機能は、トポロジー変化検出機能によりセットされたＴＣ検出フラグを検出したときに、フォワーディングテーブルの内容（データベースの情報）を削除する機能である。更に説明すると、トポロジー変化検出機能によりルートブリッジからＴＣ検出フラグがセットされたＢＰＤＵを受信したときに、フォワーディングテーブルのデータベースの情報を削除している。この機能は一度動作してからトポロジーチェンジタイマ期間は動作しないようになっている。
【００５４】
次に、上記のように構成される各ブリッジの動作を図３及び図４に基づいて説明する。図３はルートポートのリンクダウン検出時のフローチャート、図４は他のブリッジからＢＰＤＵを受信したときのフローチャートを示している。
【００５５】
ルートポートのリンクダウン検出時では、図３に示すように、ルートポートのリンクダウン情報を得ると（ＳＴ１）、得たリンクダウン情報からリンクダウンポートがルートポートか否かを判別する（ＳＴ２）。そして、リンクダウンポートがルートポートであると判断すると、そのブリッジはルートブリッジを就任する（ＳＴ３）。
【００５６】
図４に示すように、他のブリッジからＢＰＤＵを受信し、ＢＰＤＵ情報を得ると（ＳＴ４）、その得たＢＰＤＵ情報のＴＣフラグが立っているか否か判別する（ＳＴ５）。ＴＣフラグが立っていないと判断したときは、後述するＳＴ８の動作に移行する。これに対し、ＴＣフラグが立っていると判断すると、トポロジーチェンジタイマー期間か否かを判別する（ＳＴ６）。トポロジーチェンジタイマー期間でないと判断すると、後述するＳＴ８の動作に移行する。これに対し、トポロジーチェンジタイマー期間であると判断すると、自身の不図示の記憶手段に格納されたフォワーディングテーブルをクリアしてデータベース情報を削除する（ＳＴ７）。
【００５７】
フォワーディングテーブルの内容がクリアされると、得たＢＰＤＵが代表ブリッジからのＢＰＤＵか否かを判別する（ＳＴ８）。得たＢＰＤＵが代表ブリッジからのＢＰＤＵでないと判断すると、そのまま処理が終了する。これに対し、ＢＰＤＵ代表ブリッジのＢＰＤＵと判断すると、得たＢＰＤＵのルートブリッジの優先度と自身のＢＰＤＵのルートブリッジの優先度を比較し、どちらの優先度が高いか判別する（ＳＴ９）。得たＢＰＤＵのルートブリッジの優先度が自身のＢＰＤＵのルートブリッジの優先度と同等かそれより高いと判断したときは、そのまま処理が終了する。これに対し、自身のＢＰＤＵのルートブリッジの優先度が低いと判断したときには、ルートブリッジに就任する（ＳＴ１０）。
【００５８】
なお、図４のフローチャートでは、ＳＴ６においてトポロジーチェンジタイマー期間か否かを判別しているが、この動作を省略し、ＴＣフラグが立っていると判断したときに、フォワーディングテーブルの内容を削除してもよい。
【００５９】
次に、上記構成のスパニングツリー用ブリッジを用いたネットワークにおいて、ケーブルの繋ぎ変え、ポートの無効設定、通信障害による通信経路の変更などが生じてトポロジーに変化があった場合の動作について説明する。
【００６０】
ここでは、説明を簡略するため、図５（ａ）〜（ｅ）に示すネットワーク構成を例にとって説明する。図５（ａ）は定常状態を示す図であり、図５（ｂ）〜（ｅ）はブリッジＤとブリッジＥとの間の接続が解除されたトポロジーチェンジ時のデータのやりとりを示す図である。なお、図５において、各ブリッジＡ〜ＥのＲはルートポート、Ｄは代表ポート、Ｂは閉鎖ポートを示している。
【００６１】
図５のネットワークでは、図５（ａ）の定常状態のとき、ブリッジＡをルートブリッジ、ブリッジＣのブリッジＤに向かう受信ポートを閉鎖ポートＢとしてスパニングツリーが構成されている。
【００６２】
今、図５（ｂ）に示すように、ブリッジＤのルートポートＲとブリッジＥの代表ポートＤとの間の接続が解除されると、ブリッジＣやブリッジＥを介してのデータ通信（ＢＰＤＵを除く）が不可能となるため、以下に説明するように、ブリッジＣの閉鎖ポートＢを開きフォワーディング状態に遷移させて経路変更を行い、スパニングツリーを再構成する動作が実行される。
【００６３】
図５（ｂ）に示すように、ブリッジＤのルートポートＲとブリッジＥの代表ポートＤ間の接続が解除されると、ブリッジＤはリンクダウンを検出し、ルートブリッジに就任する。そして、ブリッジＤは、ルートＩＤを自分のＭＡＣアドレスに変更したＢＰＤＵを代表ポートＤからブリッジＣの閉鎖ポートＢに送信する。
【００６４】
図５（ｂ）に示すように、ブリッジＣは、ブリッジＤからのＢＰＤＵを閉鎖ポートＢから受信すると、この受信したＢＰＤＵの情報と自身のＢＰＤＵの情報とを比較する。ブリッジＣは、ループの切断前にブリッジＤを経由して送られていたＢＰＤＵを自身のＢＰＤＵとして持っている。したがって、ブリッジＣは、閉鎖ポートＢの代表ブリッジであるブリッジＤの代表ポートＤから閉鎖ポートＢの持つルートブリッジ情報に劣るルートブリッジ情報を持つＢＰＤＵを受信することになる。これにより、ブリッジＣは、自身のＢＰＤＵより劣ったＢＰＤＵをブリッジＤから受信したと判断し、ルートブリッジに就任し、劣ったＢＰＤＵを受信した受信ポートの閉鎖ポートＢを直ちに開く動作を行い、代表ポートＤとする。なお、その際に、ブリッジＣは、ルートブリッジであるブリッジＡから定期的に送信されるＢＰＤＵをブリッジＢを介して代表ポートＤから受信していれば、ルートブリッジに就任することはない。
【００６５】
そして、ブリッジＣは、図５（ｃ）に示すように、自身のＢＰＤＵを代表ポートＤからブリッジＤの代表ポートＤに送信する。ブリッジＤは、代表ポートＤからブリッジＣのＢＰＤＵを受信すると、この受信したＢＰＤＵの情報と自身のＢＰＤＵの情報とを比較する。この場合、ブリッジＤは、代表ポートＤから自身のＢＰＤＵより優るＢＰＤＵを受信するので、ルートブリッジでなくなる。そして、ブリッジＤは、代表ポートＤからＴＣＮ−ＢＰＤＵをブリッジＣの代表ポートＤに送信する。
【００６６】
ブリッジＣは、ブリッジＤからのＴＣＮ−ＢＰＤＵを代表ポートＤから受信すると、図５（ｄ）に示すように、そのＴＣＮ−ＢＰＤＵをブリッジＢの代表ポートに送信する。その際、ブリッジＣは、ルートブリッジであるブリッジＡから定期的に送信されるＢＰＤＵをブリッジＢを介して代表ポートＤから受信すると、ルートブリッジでなくなる。
【００６７】
更に、ブリッジＢは、ブリッジＣからのＴＣＮ−ＢＰＤＵを代表ポートＤから受信すると、そのＴＣＮ−ＢＰＤＵをルートブリッジであるブリッジＡの代表ポートＤに送信する。すなわち、ブリッジＤから送信されるＴＣＮ−ＢＰＤＵは、各ブリッジＣ、ブリッジＢを介してルートブリッジであるブリッジＡまで送信される。
【００６８】
ブリッジＡは、ブリッジＢからのＴＣＮ−ＢＰＤＵを代表ポートＤから受信すると、トポロジーが変化している旨を各ブリッジに知らせるべく、図５（ｅ）に示すように、ＴＣ検出フラグをセットしたＢＰＤＵをブリッジＢのルートポートＲおよびブリッジＥのルートポートＲに送信する。ブリッジＢは、ブリッジＡからのＴＣ検出フラグをセットしたＢＰＤＵをルートポートＲから受信すると、そのＢＰＤＵをブリッジＣのルートポートＲに送信する。更に、ブリッジＣは、ブリッジＢからのＴＣ検出フラグをセットしたＢＰＤＵをルートポートＲから受信すると、そのＢＰＤＵをブリッジＤのルートポートＲに送信する。すなわち、ルートブリッジであるブリッジＡから送信されるＴＣフラグをセットしたＢＰＤＵは、全てのブリッジＢ〜Ｅに対して順次伝番される。そして、このＴＣ検出フラグをセットしたＢＰＤＵを受信した各ブリッジＢ，Ｃ，Ｄ，Ｅは、自身のフォワーディングテーブルの内容を削除する。
【００６９】
自身のフォワーディングテーブルの内容が削除された各ブリッジＢ，Ｃ，Ｄ，Ｅは、ブリッジの特徴でもあるアドレス情報の自動学習機能によりフォワーディングテーブルが作られる。すなわち、通信がはじまると、各ブリッジは送られてくるパケットのＭＡＣアドレス情報を参照し、パケットを出したノードに接続されているブリッジのポートを自動学習し、すべてのパケットがブリッジを通過すると各ブリッジのフォワーディングテーブルが出来上がる。
【００７０】
また、別の例として、ブリッジＡの代表ポートＤとブリッジＥのルートポートＲとの間の接続を解除した場合の動作図を図６（ａ）〜（ｅ）に示す。
【００７１】
図６のネットワークでは、図５（ａ）と同様に、図６（ａ）の定常状態のとき、ブリッジＡをルートブリッジ、ブリッジＣのブリッジＤに向かう受信ポートを閉鎖ポートＢとしてスパニングツリーが構成されている。
【００７２】
今、図６（ｂ）に示すように、ブリッジＡの代表ポートＤとブリッジＥのルートポートＲとの間の接続が解除されると、ブリッジＣ、ブリッジＤやブリッジＥを介してのデータ通信（ＢＰＤＵを除く）が不可能となるため、以下に説明するように、ブリッジＣの閉鎖ポートＢを開きフォワーディング状態に遷移させて経路変更を行い、スパニングツリーを再構成する動作が実行される。
【００７３】
図６（ｂ）に示すように、ブリッジＡの代表ポートＤとブリッジＥのルートポートＲ間の接続が解除されると、ブリッジＥはリンクダウンを検出し、ルートブリッジに就任する。そして、ブリッジＥは、ルートＩＤを自分のＭＡＣアドレスに変更したＢＰＤＵを代表ポートＤからブリッジＤのルートポートＲに送信する。ブリッジＤは、ブリッジＥからのＢＰＤＵをルートポートＲから受信すると、この受信したＢＰＤＵの情報と自身のＢＰＤＵの情報とを比較する。ブリッジＤは、ルートブリッジであるブリッジＡからブリッジＢ、ブリッジＣを経由して送られるＢＰＤＵによって自身のＢＰＤＵが更新されている。したがって、ブリッジＤは、ルートポートＲの持つルートブリッジ情報に劣るルートブリッジ情報を持つＢＰＤＵを受信することになる。これにより、ブリッジＤは、自身のＢＰＤＵより劣ったＢＰＤＵをブリッジＥから受信したと判断し、自身のＢＰＤＵを代表ポートＤからブリッジＣの閉鎖ポートＢに送信する。この時点では、ブリッジＤは、受信ポートが開いた状態なので、特にポートを開く動作は行わない。また同時に、ブリッジＤは、自身のＢＰＤＵを代表ポートＤからブリッジＥの代表ポートＤに送信する。ブリッジＥは、代表ポートＤからブリッジＤのＢＰＤＵを受信すると、この受信したＢＰＤＵの情報と自身のＢＰＤＵの情報とを比較する。この場合、ブリッジＥは、代表ポートＤから自身のＢＰＤＵより優るＢＰＤＵを受信したと判断するので、ルートブリッジではなくなる。
【００７４】
図６（ｃ）に示すように、ブリッジＣは、ブリッジＤからのＢＰＤＵを閉鎖ポートＢから受信すると、この受信したＢＰＤＵの情報と自身のＢＰＤＵの情報とを比較する。ブリッジＣは、ループの切断前にブリッジＤを経由して送られてくるＢＰＤＵによって自身のＢＰＤＵが更新されている。したがって、ブリッジＣは、閉鎖ポートＢの代表ブリッジであるブリッジＤの代表ポートＤから閉鎖ポートＢの持つルートブリッジ情報に劣るルートブリッジ情報を持つＢＰＤＵを受信することになる。これにより、ブリッジＣは、自身のＢＰＤＵより劣ったＢＰＤＵをブリッジＤから受信したと判断し、劣ったＢＰＤＵを受信した閉鎖ポートＢを直ちに開く動作を行い、代表ポートＤとする。
【００７５】
そして、ブリッジＣは、図６（ｃ）に示すように、自身のＢＰＤＵを代表ポートＤからブリッジＤの代表ポートＤに送信する。ブリッジＤは、代表ポートＤからブリッジＣのＢＰＤＵを受信すると、この受信したＢＰＤＵの情報と自身のＢＰＤＵの情報とを比較する。この場合、ブリッジＤは、代表ポートＤから自身のＢＰＤＵより優るＢＰＤＵを受信したと判断するので、ルートブリッジでなくなる。そして、ブリッジＤは、代表ポートＤからＴＣＮ−ＢＰＤＵをブリッジＣの代表ポートＤに送信する。このＴＣＮ−ＢＰＤＵはブリッジＥの代表ポートＤにも送信される。
【００７６】
ブリッジＣは、ブリッジＤからのＴＣＮ−ＢＰＤＵを代表ポートＤから受信すると、図６（ｄ）に示すように、そのＴＣＮ−ＢＰＤＵをブリッジＢの代表ポートに送信する。その際、ブリッジＣは、ルートブリッジであるブリッジＡから定期的に送信されるＢＰＤＵをブリッジＢを介してルートポートＲから受信していると、ルートブリッジでなくなる。
【００７７】
更に、ブリッジＢは、ブリッジＣからのＴＣＮ−ＢＰＤＵを代表ポートＤから受信すると、そのＴＣＮ−ＢＰＤＵをルートブリッジであるブリッジＡの代表ポートＤに送信する。すなわち、ブリッジＤから送信されるＴＣＮ−ＢＰＤＵは、各ブリッジＣ、ブリッジＢを介してルートブリッジであるブリッジＡまで送信される。
【００７８】
ブリッジＡは、ブリッジＢからのＴＣＮ−ＢＰＤＵを代表ポートＤから受信すると、トポロジーが変化している旨を各ブリッジに知らせるべく、図６（ｅ）に示すように、ＴＣ検出フラグをセットしたＢＰＤＵをブリッジＢのルートポートＲに送信する。ブリッジＢは、ブリッジＡからのＴＣ検出フラグをセットしたＢＰＤＵをルートポートＲから受信すると、そのＢＰＤＵをブリッジＣのルートポートＲに送信する。更に、ブリッジＣは、ブリッジＢからのＴＣ検出フラグをセットしたＢＰＤＵをルートポートＲから受信すると、そのＢＰＤＵをブリッジＤのルートポートＲに送信する。そして、ブリッジＤは、ブリッジＣからのＴＣ検出フラグをセットしたＢＰＤＵをルートポートＲから受信すると、そのＢＰＤＵをブリッジＥのルートポートＲに送信する。すなわち、ルートブリッジであるブリッジＡから送信されるＴＣフラグをセットしたＢＰＤＵは、全てのブリッジＢ〜Ｅに対して順次伝番される。そして、このＴＣ検出フラグをセットしたＢＰＤＵを受信した各ブリッジＢ，Ｃ，Ｄ，Ｅは、自身のフォワーディングテーブルの内容を削除する。
【００７９】
自身のフォワーディングテーブルの内容が削除された各ブリッジＢ，Ｃ，Ｄ，Ｅは、ブリッジの特徴でもあるアドレス情報の自動学習機能によりフォワーディングテーブルが作られる。すなわち、通信がはじまると、各ブリッジは送られてくるパケットのＭＡＣアドレス情報を参照し、パケットを出したノードに接続されているブリッジのポートを自動学習し、すべてのパケットがブリッジを通過すると各ブリッジのフォワーディングテーブルが出来上がる。
【００８０】
このように、本実施の形態では、ルートポートでリンクダウンを検出したとき、ＢＰＤＵの有効期間を経時するマックスエイジタイマー満了時と同様にトポロジーチェンジ検出処理をし、ルートブリッジとなる。また、受信ポートの持つルートブリッジ情報よりも劣るルートブリッジ情報を持つＢＰＤＵを代表ブリッジから受信した場合にも、マックスエイジタイマー満了時と同様にトポロジーチェンジ検出処理をし、ルートブリッジとなり、これによりルートブリッジとなった場合には、元々閉鎖ポートであったポートは直ちにフォワーディング状態に遷移させる。そして、ＴＣＮ−ＢＰＤＵを受信したブリッジは、ホールドタイムを無視して、直ちにＴＣＮ−ＢＰＤＵを伝播する。もし、ルートブリッジであれば、直ちにＴＣ検出フラグをセットしたＢＰＤＵを全ポートに送信する。そして、ＴＣ検出フラグがセットされたＢＰＤＵを受信したブリッジは、ホールドタイムを無視して直ちにＢＰＤＵを伝送する。その後すぐに、フォワーディングテーブルのデータベース情報を削除する。
【００８１】
したがって、本例によれば、複数のブリッジによる冗長経路を含むネットワークにおいて、ケーブルの繋ぎ変え、ポートの無効設定および通信障害による通信経路の変更に瞬時に対応し、通信の中断からの復帰を早くすることができる。
【００８２】
なお、本例においては、説明の簡略を図るため、図１に示すネットワーク構成を一例として説明したが、図１のネットワーク構成に限らず、複数のブリッジによる冗長経路を含むネットワーク、言い換えれば、独立したブロードキャストドメイン毎に動作するスパニングツリーに対して本例の構成および経路変更方法を採用することができる。
【００８３】
【発明の効果】
以上の説明で明らかなように、本発明によれば、複数のブリッジによる冗長経路を含むネットワークにおいて、ケーブルの繋ぎ変え、ポートの無効設定および通信障害による通信経路の変更に瞬時に対応し、通信の中断からの復帰を早くすることができる。
【図面の簡単な説明】
【図１】本発明によるスパニングツリー用ブリッジの機能ブロック図
【図２】（ａ）〜（ｄ）各ブリッジ間で送受信されるＢＰＤＵのフレーム・フォーマットを示す図
【図３】図１のスパニングツリー用ブリッジを用いたルートポートのリンクダウン検出時のフローチャート、
【図４】図１のスパニングツリー用ブリッジを用いたネットワークにおいて、他のブリッジからＢＰＤＵを受信したときのフローチャート
【図５】図１のスパニングツリー用ブリッジを用いたネットワークにおいて、ルートブリッジ以外のブリッジ間の接続が解除されてトポロジー変化が生じたときの動作説明図
【図６】図１のスパニングツリー用ブリッジを用いたネットワークにおいて、ルートブリッジと他のブリッジ間の接続が解除されてトポロジー変化が生じたときの動作説明図
【図７】スパニングツリーの目的を説明するための図
【図８】スパニングツリーの目的を説明するための図
【図９】スパリングツリー用ブリッジを用いたネットワークにおいて、トポロジー変化が生じたときの従来の動作を説明するための図
【符号の説明】
１（Ａ〜Ｅ）…スパニングツリー用ブリッジ、２…ポート、Ｒ…ルートポート、Ｄ…代表ポート、Ｂ…閉鎖ポート。
【図１】
0003715501.tif 000002
【図２】
0003715501.tif 000003
【図３】
0003715501.tif 000004
【図４】
0003715501.tif 000005
【図５】
0003715501.tif 000006
【図６】
0003715501.tif 000007
【図７】
0003715501.tif 000008
【図８】
0003715501.tif 000009
【図９】
0003715501.tif 000010