(57)【要約】【課題】ノード間をループの無い論理的トポロジを構築および修復するのに、ポートをフォワーディング状態にするための待ち時間を無くしてトポロジ構築および修復を高速化する。【解決手段】トポロジを構築するポートステート制御機構１は、ブロッキング状態のポートからブロッキング要求を出し、この要求による調停に負けたノードはブロッキング状態に遷移させ、上位ノードに対してブロッキング要求受理を通知し、これを通知されたノードは直ちにブロッキング状態を解除してフォワーディンング状態に遷移させる。トポロジを再構築する再調停トリガ機構２は、通信障害発生ノードのポートをブロッキング状態にし、トポロジ情報をクリアし、トポロジ復旧メッセージを次のノードに転送し、メッセージを受信したノードはトポロジ情報を捨ててマスタノードとなり次のノードに対して調停を開始する。【選択図】　図１
2004129100.tif 000002
【特許請求の範囲】
【請求項１】
多数のフレーム転送装置間で情報転送するため、各フレーム転送装置をノードとし、物理的にループを含むトポロジから不要なリンクを論理的に切断し、各ノード間をループのない論理的トポロジを構築するポートステート制御機構を備えた情報転送システムであって、
前記ポートステート制御機構は、
リングトポロジにある各ノードにおいて、ブロッキング状態のポートからブロッキング要求を出す手段と、
この要求による調停に負けたノードはブロッキング状態に遷移させ、上位ノードに対してブロッキング要求受理を通知する手段と、
ブロッキング要求受理を通知されたノードは直ちにブロッキング状態を解除してフォワーディンング状態に遷移させる手段とを備えたことを特徴とする情報転送システム。
【請求項２】
前記ノード間の通信障害発生時に論理的トポロジを再構築する再調停トリガ機構を設け、
前記再調停トリガ機構は、
ハードウェア的に通信障害を検出したノードのポートをブロッキング状態にし、トポロジ情報をクリアし、トポロジ復旧メッセージを次のノードに転送する手段と、
前記メッセージを受信したノードはトポロジ情報を捨ててマスタノードとなり次のノードに対して調停を開始する手段とを備えたことを特徴とする請求項１に記載の情報転送システム。
【請求項３】
多数のフレーム転送装置間で情報転送するため、各フレーム転送装置をノードとし、物理的にループを含むトポロジから不要なリンクを論理的に切断し、各ノード間をループのない論理的トポロジを構築するポートステート制御を行う情報転送システムの論理的トポロジ構築方法であって、
前記ポートステート制御は、
リングトポロジにある各ノードにおいて、ブロッキング状態のポートからブロッキング要求を出す過程と、
この要求による調停に負けたノードはブロッキング状態に遷移させ、上位ノードに対してブロッキング要求受理を通知する過程と、
ブロッキング要求受理を通知されたノードは直ちにブロッキング状態を解除してフォワーディンング状態に遷移させる過程とを有することを特徴とする情報転送システムの論理的トポロジ構築方法。
【請求項４】
前記ノード間の通信障害発生時に論理的トポロジを再構築する再調停トリガ機構を設け、
前記再調停トリガ機構は、
ハードウェア的に通信障害を検出したノードのポートをブロッキング状態にし、トポロジ情報をクリアし、トポロジ復旧メッセージを次のノードに転送する過程と、
前記メッセージを受信したノードはトポロジ情報を捨ててマスタノードとなり次のノードに対して調停を開始する過程とを有することを特徴とする請求項３に記載の情報転送システムの論理的トポロジ構築方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、スイッチングハブなどの多数のフレーム転送装置間の情報転送システムに係り、特にフレーム転送装置におけるポートステート制御機構およびトポロジ復旧メッセージ機構に関する。
【０００２】
【従来の技術】
この種の情報転送方式には、情報転送ルートとして、物理的にループを含むトポロジから不要なパス（リンク）を論理的に切断し、ループのない論理的な木構造を構築するものがある。また、木構造を構成するノード間に物理的または論理的な切断（断線）が発生したときには木構造を再構築できるようにしている。
【０００３】
ポートステート制御機能は、上記の不要なリンクを論理的にブロッキングすることにより、系全体で論理的ループが発生しないように保障するために用意される。この機能で制御するポートステートは、各ポートに対して、一般フレームの転送を許可するフォワーディング状態と、一般フレームの転送を禁止するブロッキング状態とする。
【０００４】
トポロジ復旧メッセージ機能は、上記の断線発生時に系全体にそのことを速報して再調停を促すことにより、断線状態からの速やかな復帰を支援するために用意される。このときの調停は、論理的トポロジを構築するために隣接ノード間で行なわれ、トポロジ情報の交換・評価・ポートステート制御などの一連の処理を行う。
【０００５】
上記の木構造構築と再構築を可能とする手段として、スパニングツリープロトコル（ＳＴＰ）がある（例えば、非特許文献１参照）。
【０００６】
このＳＴＰのアルゴリズムは、大まかには２つに分けられ、１つは木構造を構成するためのトポロジ情報の処理、もう１つはステーションキャッシュのリフレッシュを支援する処理（変更通知機構）になる。
【０００７】
木構造を構築するには、どれか１つのノードをルートとして決め、他の各ノードについては隣接するノード間でトポロジ情報を交換しあい、ポート（接続端）の接続先がルートにより近いノードを「親（ルートポート）」、ルートからより遠いノードを「子（代表ポート）」を決定するという処理をすべてのノードで実行し、これら親子関係のトポロジ情報を系全体に広めて木構造を構築する。
【０００８】
なお、各ノードは、受信したトポロジ情報をそのまま伝送するのではなく、自ノードの保有トポロジ情報の更新に使われ、次のトポロジ情報送信時に更新された情報を送信することで、新しいトポロジ情報が間接的に伝搬していく。また、トポロジ情報はＢＰＤＵ（Ｂｒｉｄｇｅ　Ｐｒｏｔｏｃｏｌ　Ｄａｔａ　Ｕｎｉｔ）に格納される。
【０００９】
木構造の再構築には、変更通知機構を使用する。この変更通知処理は、・トポロジの変更を検知したらルートに通知する、・ルートは全ノードに変更を通知する、トポロジ変更通知が出ている間はステーションキャッシュのエージングタイムを短くする、という処理になる。
【００１０】
【非特許文献１】
ＩＳＯ／ＩＥＣ　Ｆｉｎａｌ　ＤＩＳ　１５８０２−３（ＩＥＥＥ　Ｐ８０２．１Ｄ／Ｄ１７）〜８章　Ｔｈｅ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｐｒｏｔｏｃｏｌ
【００１１】
【発明が解決しようとする課題】
従来のスパニングツリープロトコル（ＳＴＰ）によるポートステート制御およびトポロジ修復には以下の問題点がある。
【００１２】
（１）論理的トポロジの構築までに長い時間が必要
ＳＴＰを使った場合には論理的トポロジ構築までに数十秒オーダの時間を要する。ＳＴＰブリッジがポートを転送可能状態（フォワーディング状態）に遷移させるまでの過程を図５に示す。
【００１３】
この処理は、隣接するブリッジ同士は、設定ＢＰＤＵの送受信を通じてお互いのトポロジ情報を交換し、その優先順位を比較することでブリッジ間の上下関係を決定し、最終的にポートロールを決定する。
【００１４】
ここで、ポートロールとは、ポートの論理的な役割であり、ルートポート、代表ポートであればフォワーディング状態へ遷移でき、補欠ポートならばブロッキング状態を維持しなければならない。但し、ルートポートまたは代表ポートに選定されてからすぐにフォワーディング状態に遷移できるわけでなく、以下に説明するように長い時間がかかる。
【００１５】
図５において、ポートＰは、設定ＢＰＤＵを受信したときに、トポロジ情報評価によって、ルートポートまたは代表ポートに選ばれたとすると、リスニング状態に遷移させる。このリスニング状態のポートＰは転送遅延時間（あるブリッジから発信された情報が系全体に広まるのにかかる時間）Ｔｆｗｄ経過後にラーニング状態に遷移させる。次いで、ラーニング状態のポートＰは転送遅延時間Ｔｆｗｄ経過後にフォワーディング状態に遷移させる。
【００１６】
従って、ポートロールが決定してから転送遅延時間の２倍の時間が経過しないと、そのポートは一般フレームを転送することはできない。
【００１７】
（２）断線発生時に論理的トポロジを修復するまでに更に時間がかかる。
【００１８】
断線が発生した場合には、（可能ならば）切断箇所を迂回する新たな論理的トポロジを構築しなければならない。速やかな論理的トポロジ構築の為には、断線があったことを系全体にアナウンスする必要がある。
【００１９】
ＳＴＰでは系全体に速報する手段としてＴＣＮメッセージがあるが、これはステーションキャッシュをクリアする為だけに使われ、トポロジ情報更新のトリガとしての意味は持たない。しかも、ＴＣＮメッセージ方式では一度ルートブリッジまでＴＣＮメッセージを通知し、次にルートブリッジが系全体に通知するというステツプを踏むために、ケースによっては余計な時間がかかってしまう。
【００２０】
このため、ＳＴＰブリッジは定期的に受信する設定ＢＰＤＵが来なくなったことでしか断線を検出することができない。断線発生からトポロジ復帰までにかかる時間は、図６に示すように、系全体が断線に気づくまでの転送遅延時間Ｔｆｗｄがトポロジ再構築にかかる時間Ｔｆｗｄ×２に追加され、理論的には転送遅延時間Ｔｆｗｄ×３となる。
【００２１】
なお、ＳＴＰに改良を加え、トポロジ収束時間の短縮を図ったＲＳＴＰ（ラピッドスパニングツリープロトコル）が提案されている。このＲＳＴＰは、ポートがフォワーディング状態に遷移できる条件をいくつか追加することで、ループ発生の心配がないケースにおいてのみ時間短縮してフォワーディング状態に移れるとしている。しかし、このＲＳＴＰにおいても、遷移条件が限られる上、ノード数が数千など大量になる場合に待ち時間無しでフォワーディング状態に遷移できるものでないと推察される。
【００２２】
本発明の目的は、ポートをフォワーディング状態にするための待ち時間を無くし、トポロジ構築およびトポロジ修復を高速化できる情報転送システムおよび情報転送システムの論理的トポロジ構築方法を提供することにある。
【００２３】
【課題を解決するための手段】
本発明は、前記の課題を解決するため、以下のシステムおよび論理的トポロジ構築方法を特徴とする。
【００２４】
（１）多数のフレーム転送装置間で情報転送するため、各フレーム転送装置をノードとし、物理的にループを含むトポロジから不要なリンクを論理的に切断し、各ノード間をループのない論理的トポロジを構築するポートステート制御機構を備えた情報転送システムであって、
前記ポートステート制御機構は、
リングトポロジにある各ノードにおいて、ブロッキング状態のポートからブロッキング要求を出す手段と、
この要求による調停に負けたノードはブロッキング状態に遷移させ、上位ノードに対してブロッキング要求受理を通知する手段と、
ブロッキング要求受理を通知されたノードは直ちにブロッキング状態を解除してフォワーディンング状態に遷移させる手段とを備えたことを特徴とする。
【００２５】
（２）前記ノード間の通信障害発生時に論理的トポロジを再構築する再調停トリガ機構を設け、
前記再調停トリガ機構は、
ハードウェア的に通信障害を検出したノードのポートをブロッキング状態にし、トポロジ情報をクリアし、トポロジ復旧メッセージを次のノードに転送する手段と、
前記メッセージを受信したノードはトポロジ情報を捨ててマスタノードとなり次のノードに対して調停を開始する手段とを備えたことを特徴とする。
【００２６】
（３）多数のフレーム転送装置間で情報転送するため、各フレーム転送装置をノードとし、物理的にループを含むトポロジから不要なリンクを論理的に切断し、各ノード間をループのない論理的トポロジを構築するポートステート制御を行う情報転送システムの論理的トポロジ構築方法であって、
前記ポートステート制御は、
リングトポロジにある各ノードにおいて、ブロッキング状態のポートからブロッキング要求を出す過程と、
この要求による調停に負けたノードはブロッキング状態に遷移させ、上位ノードに対してブロッキング要求受理を通知する過程と、
ブロッキング要求受理を通知されたノードは直ちにブロッキング状態を解除してフォワーディンング状態に遷移させる過程とを有することを特徴とする。
【００２７】
（４）前記ノード間の通信障害発生時に論理的トポロジを再構築する再調停トリガ機構を設け、
前記再調停トリガ機構は、
ハードウェア的に通信障害を検出したノードのポートをブロッキング状態にし、トポロジ情報をクリアし、トポロジ復旧メッセージを次のノードに転送する過程と、
前記メッセージを受信したノードはトポロジ情報を捨ててマスタノードとなり次のノードに対して調停を開始する過程とを有することを特徴とする。
【００２８】
【発明の実施の形態】
図１は本発明の実施形態を示し、ノードＮｉ（ｉはノードＩＤ）の機能ブロック図である。
【００２９】
本実施形態は、リングトポロジにおいて、トポロジの構築・修正をＳＴＰよりも高速に行なうためのプロトコルを実現するためのもので、対象トポロジをリングに限定したことで、高速化のための幾つかの改良が可能となる。その主たる機能ブロックは、ポートステート制御ブロック（ブロッキングポートドリフト機構）１とトポロジ情報更新器（再調停トリガ機構）２にある。これらを中心にして、以下に詳細を説明する。
【００３０】
（１）ブロッキングポートドリフト機構
ＳＴＰではポートをフォワーディング状態に遷移させるための条件が転送遅延時間の２倍待つことであった。本実施形態になるＲＴＰ（リングトポロジプロトコル）では下位ノードへブロッキングの義務を移管した時点で直にもフォワーディング状態に遷移させることができる。
【００３１】
隣接するノード同士は調停ＲＰＤＵ（Ｒｉｎｇ　Ｐｒｏｔｏｃｏｌ　Ｄａｔａ　Ｕｎｉｔ）の送受信を通じて互いのトポロジ情報を交換し、その優先順位を比較することでノード間の上下関係を決定し、最終的にはポートロールを決定する。図１では、ノードＮｉの両端ポートＬまたはポートＲを介してトポロジ情報バッファ３Ｌ，３Ｒで隣接ノードとは調停ＲＰＤＵを送受信し、受信したトポロジ情報はトポロジ優劣判定アルゴリズム４で優先順位を判定し、決定したポートロールをポートロール記憶部５Ｌ，５Ｒに保存する。
【００３２】
調停ＲＰＤＵはＲＴＰ固有のフレームで、この中にトポロジ情報や各種フラグ類が格納される。調停ＲＰＤＵを送信するポートがブロッキング状態の時は、その調停ＲＰＤＵの中にあるブロッキング要求フラグをセットして送信する（ブロッキング要求メッセージと呼ぶ）。
【００３３】
ポートステート制御ブロック１は、ブロッキング要求メッセージによって生じた調停にて敗北した場合、そのブロッキング要求を受け入れてポートをブロッキング状態に遷移させ、上位ノードに対してブロッキング要求受理フラグをセツトした調停ＲＰＤＵを返信する（ブロッキング要求受理メッセージ）。
【００３４】
そして、ブロッキング要求受理メッセージを受信したとき、受信したポートを直ちにフォワーディング状態に遷移させる。
【００３５】
この調停動作の繰り返しによって、ブロッキングポートは確実に下流へと漂流してゆく。最終的にはマスタノードから最も遠いノードがブロッキングをし続けることでリングトポロジのループが切断される。
【００３６】
このようにして調停されたポートステートは、その設定部６Ｌ，６Ｒに設定され、スイッチングアルゴリズム＆アドレステーブル７に保存および隣接ポート間のフレーム転送制御に使用する。
【００３７】
図２は、隣接ノード間での調停例を示し、ｓｔｅｐ：０〜５の手順で調停される。図中において、“●―‖”印がブロッキングポートを示している。また“○”印（上位ポート）および“●”印（下位ポート）はフォワーディングポートを示している。以下、各ｓｔｅｐ順に説明する。
【００３８】
〔ｓｔｅｐ０〕ノードＮ１・Ｎ２間が切れていて、該当ポートはブロッキング状態且つリングダウン（切れた）状態である。
【００３９】
〔ｓｔｅｐ１〕ノードＮ１・Ｎ２間を接続したことで両ノードは該当ポートのリンクが成立したことを認識する。但し、この段階では、該当ポートはどちらもブロッキング状態のままである。
【００４０】
〔ｓｔｅｐ２〕ノードＮ１およびＮ２は調停ＲＰＤＵを送信する。この時、該当ポートはブロッキング状態にあるため、調停ＲＰＤＵのブロッキング要求フラグがセットされる（ブロッキング要求メッセージ）。
【００４１】
〔ｓｔｅｐ３〕ノードＮ１およびＮ２は受信した調停ＲＰＤＵからトポロジ情報を取り出して、自身のトポロジ情報と優劣比較を行なう。この例では、ノードＮ１の方が優れたトポロジ情報を持っていたのでノードＮ２が調停に「敗北」したことになる。従って、ノードＮ２が持つトポロジ情報の代表値が更新される。
【００４２】
〔ｓｔｅｐ４〕調停に負けたノードＮ２は直ちに上位ポートをフォワーディング状態に、上位ポートではないポートをブロッキング状態にして、上位ノードＮ１に対してブロッキング要求受理フラグをセツトした調停ＲＰＤＵを返信する（ブロッキング要求受理メッセージ）。
【００４３】
〔ｓｔｅｐ５〕ノードＮ１はブロッキング要求受理メッセージを受けて該当ポートのブロッキングを解除する。
【００４４】
〔結果〕以上の調停によって、ノードＮ１−Ｎ２間の論理ブロッキングポートはノードＮ２の反対側のポートまで「ドリフト」（ｄｒｉｆｔ：漂流）される。この処理が繰り返されることで、論理ブロッキングポートは系の末端までドリフトされ、論理トポロジは完成する。
【００４５】
図３にブロッキングポートが調停によってドリフトされてゆく様子をｓｔｅｐ：０〜５で示す（個々の調停については詳細を省く）。この例ではノードＮ１が加わったことによってブロッキングポートが向かって左から右へ移動している。
【００４６】
（２）再調停トリガ機構
ＳＴＰでは断線などの通信障害発生時に論理トポロジを迅速に修復する手段が提供されていない。本実施形態になるＲＴＰでは再調停を促す特殊メッセージを障害発生時に頒布させることで、論理トポロジを速やかに再構築する。
【００４７】
各ノードはハードウェア的にリンク状態を監視し、リンクダウンなどによって通信障害を検出したら、再調停トリガ機構２により、直ちにそのポートをブロッキング状態に固定して調停トリガＲＰＤＵを送信する（トポロジ復旧メッセージ）。その次に、そのノード自身のトポロジ情報をクリアし、マスタノードとして調停を開始する。
【００４８】
トポロジ復旧メッセージを受信したノードは直ちにそのメッセージを対向ポートに転送して、自身のトポロジ情報をクリアし、マスタノードとして調停を開始する。
【００４９】
トポロジ復旧メッセージはリング上を転送されてゆき、その経路上にいるノードのトポロジ情報をクリアすることで次々と調停動作のトリガを引いてゆき、断線箇所に到達した時点で消滅する。
【００５０】
このトポロジ復旧メッセージが迅速に回覧されることによって調停開始の出遅れを最小限に抑えることが可能となる。なお、調停トリガＲＰＤＵは通常の調停ＲＰＤＵよりも早く巡回される必要がある。
【００５１】
図４は断線から論理トポロジ復旧までのリカバリの模様を示し、６ノードリングの例である。以下、各ｓｔｅｐ順に説明する。
【００５２】
〔ｓｔｅｐ０〕断線発生前の状態を示している。ノードＮ１がマスタを務めており、最遠のノードＮ２がブロッキングを承っている。
【００５３】
なお、ノードの中に書かれた３桁の数値は向かって左から、マスタノードＩＤ、距離（ホップ数）、上位ノードＩＤを示している。例えば、ノードＮ２は１．３．３という値を持っているが、この時ノードＮ２はマスタノードＮ１までホップ数３の位置にいてマスタノードへの経路はノードＮ３側であると認識している。
【００５４】
また、図中の“○”印は上位ポート、“●”印は下位ポートを示している。ポート記号に“‖”印がついているポートはブロッキング状態であることを示している。
【００５５】
〔ｓｔｅｐ１〕ノードＮ１−Ｎ６間で断線が発生した。
【００５６】
〔ｓｔｅｐ２〕ノードＮ１およびＮ６によって送信されたトポロジ復旧メッセージ（Ｈｅａｌｉｎｇ　Ｍｓｇ）がリング上を転送されてゆき、その経路上のノードのトポロジ情報が初期化されている様子を示す。
【００５７】
〔ｓｔｅｐ３〕リング上を１周したトポロジ復旧メッセージは断線箇所に辿り着きそこで消滅した。ここまでの過程によって系全体のノードがトポロジ情報をクリアされたことになる。
【００５８】
〔ｓｔｅｐ４〕トポロジ復旧メッセージが通過したノードは早速調停を始めるが、説明を分かりやすくするために個々の細かい調停動作の記述は省略し、トポロジ情報の伝播過程を大雑把に図示することにする。
【００５９】
図中の矢印がこの様子を示しており、矢印の先端がトポロジ情報の伝播前線Ａ，Ｂである。矢印の先端がノードに刺さっている図はそのノードが該当トポロジ情報を受信して処理した状態であることを示す。また、矢印の先端が枠外にある図はトポロジ復旧メッセージが伝送路上を走っている状態を示す。。矢印の尻尾が掛かっているノードは既にトポロジ復旧メッセージが通過して、そのトポロジ情報がクリアされてマスタノード化している状態である。気象予報で報じられる桜前線をイメージするとこの図を理解しやすくなると思われる。
【００６０】
図４ではノードＮ１およびＮ２のトポロジ情報の伝播をピックアツブして表示している。ノードＮ１から発信されたトポロジ情報ＡはノードＮ４を経由してノードＮ５の直前まできている。一方、ノードＮ２から発信されたトポロジ情報ＢはノードＮ５およびＮ６まで到達した状態にある。ノードＮ２が持っていた論理ブロッキングポートはノードＮ５に押し流されている。
【００６１】
〔ｓｔｅｐ５〕ノードＮ１からの調停前線ＡがノードＮ２からの調停前線Ｂを駆逐してノードＮ３に到達した状態である。ノードＮ５にあったブロッキングポートは調停前線Ａによって押し流され、ノードＮ２を経由してノードＮ３までドリフトして来た。
【００６２】
〔ｓｔｅｐ６〕調停前線Ａは遂にノードＮ６まで辿り着き消滅した。ここまでの過程によってリング上の全ノードが「マスタノードはノードＮ１である」と認識するに到った。論理ブロッキングポートはノードＮ６の左側のリングポート上に存在している（物理ブロッキングとカブっている）。
【００６３】
〔ｓｔｅｐ７〕トポロジ修復後の姿。
【００６４】
【発明の効果】
以上のとおり、本発明によれば、ブロッキングポートドリフト機構でループのない論理的トポロジを構築するため、ポートをフォワーディング状態にするのに、転送遅延時間×２の待ち時間を必要とせず、トポロジ構築時間が短くなる上に、ノードのループ化を確実に防止することができる。また、各ノードに転送遅延時間を設定する必要がなく、管理上の手間も軽減される。
【００６５】
また、再調停トリガ機構で論理的トポロジを復旧させるため、ＳＴＰよりも短時間で断線ノードの迂回を行うことができる。
【図面の簡単な説明】
【図１】本発明の実施形態を示す論理的トポロジ構築および修復の機能ブロック図。
【図２】実施形態における調停手順例。
【図３】実施形態におけるブロッキングポートがドリフトされる様子を示す図。
【図４】実施形態における断線リカバリの模様を示す図。
【図５】従来のＳＴＰブリッジのポートステートの遷移を示す図。
【図６】従来の断線リカバリの過程を示す図。
【符号の説明】
１…ポートステート制御ブロック
２…トポロジ情報更新器
３Ｌ，３Ｒ…トポロジ情報バッファ
４…トポロジ優劣判定アルゴリズム
５Ｌ，５Ｒ…ポートロール保存部
６Ｌ，６Ｒ…ポートステート保存部
７…スイッチングアルゴリズム＆アドレステーブル
【図１】
2004129100.tif 000003
【図２】
2004129100.tif 000004
【図３】
2004129100.tif 000005
【図４】
2004129100.tif 000006
【図５】
2004129100.tif 000007
【図６】
2004129100.tif 000008