(57)【要約】    【課題】  ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成を可能にすると共に、ネットワークで使用できるスパニングツリーの数が２分の１に制限されていた従来の問題を回避し、拡張性を保持することができるネットワークシステムを提供する。    【解決手段】  複数のノードを接続したネットワーク上でスパニングツリーを構成するネットワークシステムであって、現時点でフレーム転送が行われている複数のスパニングツリー（＃４００１〜＃４００６）に対する、ノード追加又はノード削除によるツリー再構成に使用するための少なくとも一の予備用のツリー（＃４０９５）を設け、予備用ツリー（＃４０９５）を複数のスパニングツリー（＃４００１〜＃４００６）のツリー再構成において共用する。【選択図】    図１４
2006279842.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを接続したネットワーク上でフレームを転送する経路として複数のツリーを使用するネットワークシステムにおいて、
前記ネットワークにノードが追加又は削除されることにより前記ツリーを再構成する際に使用する少なくとも一の予備用のツリーを設け、
前記予備用ツリーを、前記複数のツリーの前記ツリー再構成において共用することを特徴とするネットワークシステム。
【請求項２】
前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する管理用サーバを備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項３】
専用の管理サーバを備え、前記管理サーバが、前記予備用ツリーの使用状況を管理する機能を備え、
前記追加され又は削除されるノードが、前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する機能を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項４】
前記追加され又は削除されるノードが、前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する機能を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項５】
前記管理サーバが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項２に記載のネットワークシステム。
【請求項６】
前記追加され又は削除されるノードが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項３又は請求項４に記載のネットワークシステム。
【請求項７】
前記管理サーバは、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記予備用ツリーの使用状況を確認し、前記予備用ツリーが使用可能である場合に、前記追加又は削除対象のノードに対して許可を通知すると共に、要求された前記ツリーのルートノードに対してツリー再構成を要求することを特徴とする請求項２に記載のネットワークシステム。
【請求項８】
前記ツリーのルートノードが、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記管理サーバに対して前記予備用ツリーの使用状況を問い合わせると共に、
前記管理サーバは、前記予備用ツリーが使用可能である場合に、前記ツリーのルートノードに対してツリー再構成を要求することを特徴とする請求項３に記載のネットワークシステム。
【請求項９】
前記追加され又は削除されるノードが、前記予備用ツリーの使用予約を前記ネットワーク内に通知し、
前記予備用ツリーが使用中でなければ、前記予備用ツリーの使用を前記ネットワーク内に通知して、当該ツリーのルートノードに対して追加又は削除の要求を行い、
当該ツリーのルートノードが、前記追加又は削除の要求を受け、ツリー再構成の処理を実行することを特徴とする請求項４に記載のネットワークシステム。
【請求項１０】
前記ノードが、
転送に利用するツリーを決定するＳＴＰコントローラと、
前記ノードの追加又は削除によるツリー再構成のための制御を行う再構成コントローラと、
宛先ごとのフレームの転送出力先を記録するフォワーディングテーブルと、
前記タグに従って前記フレームの転送先のＳＴＰコントローラを決定する分別器とを備えることを特徴とする請求項１から請求項９の何れか１項に記載のネットワークシステム。
【請求項１１】
前記ノードの前記再構成コントローラが、
所定の制御フレームによってツリーの再構成を行う再構成処理部と、
他のノードとの間で前記制御フレームの送受信を行う制御フレーム送受信部と、
再構成におけるツリーの安定を検出するための安定タイマとを備えることを特徴とする請求項１０に記載のネットワークシステム。
【請求項１２】
前記追加されるノードが、ノード追加によるツリー再構成に際し、前記ネットワーク内を送信される制御フレームの受信処理のみを行うことにより、前記制御フレームから、前記ツリー毎に、ルートとなるノードのアドレスを取得することを特徴とする請求項４に記載のネットワークシステム。
【請求項１３】
前記ツリーがスパニングツリーであることを特徴とする請求項１から請求項１２のいずれかの請求項に記載のネットワークシステム。
【請求項１４】
複数のノードを接続したネットワーク上でフレームを転送する経路として複数のツリーを使用するネットワークシステムのツリー再構成処理方法であって、
前記ネットワークにノードが追加又は削除されることにより前記ツリーを再構成する際に使用する少なくとも一の予備用のツリーを設け、  前記複数のツリーの前記ツリー再構成において、前記予備用ツリーを共用することを特徴とするツリー再構成処理方法。
【請求項１５】
前記ネットワークに設けた管理サーバが、前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理することを特徴とする請求項１４に記載のツリー再構成処理方法。
【請求項１６】
前記ネットワークに設けた管理サーバが、前記予備用ツリーの使用状況を管理し、
前記追加され又は削除されるノードが、前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理することを特徴とする請求項１４に記載のツリー再構成処理方法。
【請求項１７】
前記追加され又は削除されるノードが、前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理することを特徴とする請求項１４に記載のツリー再構成処理方法。
【請求項１８】
前記管理サーバが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項１５に記載のツリー再構成処理方法。
【請求項１９】
前記追加され又は削除されるノードが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項１６又は請求項１７に記載のツリー再構成処理方法。
【請求項２０】
前記管理サーバが、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記予備用ツリーの使用状況を確認し、前記予備用ツリーが使用可能である場合に、前記追加又は削除対象のノードに対して許可を通知すると共に、要求された前記ツリーのルートノードに対してツリー再構成を要求することを特徴とする請求項１５に記載のツリー再構成処理方法。
【請求項２１】
前記ツリーのルートノードが、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記管理サーバに対して前記予備用ツリーの使用状況を問い合わせると共に、
前記管理サーバは、前記予備用ツリーが使用可能である場合に、前記ツリーのルートノードに対してツリー再構成を要求することを特徴とする請求項１６に記載のツリー再構成処理方法。
【請求項２２】
前記追加され又は削除されるノードが、前記予備用ツリーの使用予約を前記ネットワーク内に通知し、
前記予備用ツリーが使用中でなければ、前記予備用ツリーの使用を前記ネットワーク内に通知して、当該ツリーのルートノードに対して追加又は削除の要求を行い、
当該ツリーのルートノードが、前記追加又は削除の要求を受け、ツリー再構成の処理を実行することを特徴とする請求項１７に記載のツリー再構成処理方法。
【請求項２３】
前記追加されるノードが、ノード追加によるツリー再構成に際し、前記ネットワーク内を送信される制御フレームの受信処理のみを行うことにより、前記制御フレームから、前記ツリー毎に、ルートとなるノードのアドレスを取得することを特徴とする請求項１７に記載のツリー再構成処理方法。
【請求項２４】
複数のノードを接続したネットワーク上でフレームを転送する経路として複数のツリーを使用するネットワークシステムのノードであって、
前記ネットワークにノードが追加又は削除されることにより前記ツリーを再構成する際に使用する少なくとも一の予備用のツリーを、前記複数のツリーの前記ツリー再構成において共用するための機能を備えることを特徴とするノード。
【請求項２５】
前記追加され又は削除されるノードが、前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する機能を備えることを特徴とする請求項２４に記載のノード。
【請求項２６】
前記追加され又は削除されるノードが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項２５に記載のノード。
【請求項２７】
前記追加され又は削除されるノードが、前記予備用ツリーの使用予約を前記ネットワーク内に通知し、
前記予備用ツリーが使用中でなければ、前記予備用ツリーの使用を前記ネットワーク内に通知して、当該ツリーのルートノードに対して追加又は削除の要求を行い、
当該ツリーのルートノードが、前記追加又は削除の要求を受け、ツリー再構成の処理を実行することを特徴とする請求項２４に記載のノード。
【請求項２８】
転送に利用するツリーを決定するＳＴＰコントローラと、
前記ノードの追加又は削除によるツリー再構成のための制御を行う再構成コントローラと、
宛先ごとのフレームの転送出力先を記録するフォワーディングテーブルと、
前記タグに従って前記フレームの転送先のＳＴＰコントローラを決定する分別器とを備えることを特徴とする請求項２４から請求項２７の何れか１項に記載のノード。
【請求項２９】
前記再構成コントローラが、
所定の制御フレームによってツリーの再構成を行う再構成処理部と、
他のノードとの間で前記制御フレームの送受信を行う制御フレーム送受信部と、
再構成におけるツリーの安定を検出するための安定タイマとを備えることを特徴とする請求項２８に記載のノード。
【請求項３０】
複数のノードを接続したネットワーク上でフレームを転送する経路として複数のツリーを使用するネットワークシステムにおいて、コンピュータ装置上で実行されツリー再構成処理を行うためのツリー再構成処理プログラムであって、
前記コンピュータ装置を、
前記ネットワークにノードが追加又は削除されることにより前記ツリーを再構成する際に使用する少なくとも一の予備用のツリーを、前記複数のツリーの前記ツリー再構成において共用させる手段として機能させることを特徴とするツリー再構成処理プログラム。
【請求項３１】
前記ネットワークに設けた管理サーバを構成するコンピュータ装置を、前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する手段として機能させることを特徴とする請求項３０に記載のツリー再構成処理プログラム。
【請求項３２】
前記ネットワークに設けた管理サーバを構成するコンピュータ装置を、前記予備用ツリーの使用状況を管理する手段として機能させ、
前記追加され又は削除されるノードを構成するコンピュータ装置を、前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する手段として機能させることを特徴とする請求項３０に記載のツリー再構成処理プログラム。
【請求項３３】
前記追加され又は削除されるノードを構成するコンピュータ装置を、前記予備用ツリーの使用状況を管理し、かつ前記ノードの追加、削除におけるツリー再構成の対象となる前記ツリーの状態を管理する手段として機能させることを特徴とする請求項３０に記載のツリー再構成処理プログラム。
【請求項３４】
前記管理サーバが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項３１に記載のツリー再構成処理プログラム。
【請求項３５】
前記追加され又は削除されるノードが、前記ツリー毎に、ルートとなるノードのアドレスと、ツリー再構成の有無を示すフラグを含む管理テーブルを備えることを特徴とする請求項３２又は請求項３３に記載のツリー再構成処理プログラム。
【請求項３６】
前記管理サーバに、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記予備用ツリーの使用状況を確認し、前記予備用ツリーが使用可能である場合に、前記追加又は削除対象のノードに対して許可を通知すると共に、要求された前記ツリーのルートノードに対してツリー再構成を要求する機能を実行させることを特徴とする請求項３１に記載のツリー再構成処理プログラム。
【請求項３７】
前記ツリーのルートノードに、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記管理サーバに対して前記予備用ツリーの使用状況を問い合わせると共に、
前記管理サーバは、前記予備用ツリーが使用可能である場合に、前記ツリーのルートノードに対してツリー再構成を要求する機能を実行させることを特徴とする請求項３２に記載のツリー再構成処理プログラム。
【請求項３８】
前記追加され又は削除されるノードが、前記予備用ツリーの使用予約を前記ネットワーク内に通知し、
前記予備用ツリーが使用中でなければ、前記予備用ツリーの使用を前記ネットワーク内に通知して、当該ツリーのルートノードに対して追加又は削除の要求を行い、
当該ツリーのルートノードが、前記追加又は削除の要求を受け、ツリー再構成の処理を実行する機能を実行させることを特徴とする請求項３３に記載のツリー再構成処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークシステムに関し、特にスパニングツリーの再構成時にネットワークを停止させることの無いネットワークシステム、スパニングツリー再構成処理方法及びスパニングツリー再構成処理プログラムに関する。
【背景技術】
【０００２】
従来、イーサネット(R)にあっては、出力ポートが未決定時には、フレームをブロードキャストして、その送信元アドレスと受信ポートを学習することにより、出力ポートを決定する方法がとられている。そのため、ネットワークの物理形状としてループ（円環）形状を含む場合に、ブロードキャストされたフレームが循環し続ける可能性がある。
【０００３】
このようなフレームの循環を防止することを目的として、スパニングツリープロトコル（Spanning Tree Protocol、以下ＳＴＰと称する）と呼ばれる制御方法がＩＥＥＥにおいて規定されており（ＩＥＥＥ８０２．１Ｄやその高速版であるＩＥＥＥ８０２．１ｗ）、これにより、論理的にループを排除したネットワークを構成することが可能となる。
【０００４】
しかし、ＳＴＰでは、ノードやリンクの追加、削除時に、スパニングツリー（Spanning Tree）の全体または一部を停止させてツリーの再構築を行うため、再構築中にネットワークが停止することにより、フレームの廃棄が発生する場合があった。
【０００５】
これを回避するために、例えば、次世代イーサネット(R)アーキテクチャＧＯＥ（Global Optical Ethernet(R)）の提案−（３）サービス無停止型スパニングツリー再構築と負荷分散−（２０００年電子情報通信学会通信ソサイエティ大会講演論文集：２００２年８月２０日発行）（非特許文献１）においては、次に述べる方式が提案されている。
【０００６】
ＳＴＰを使用するネットワークにおいて、スパニングツリーを２面用意し、ノードやリンクの追加、削除の際に、フレームの転送にはネットワークの構成変更前のスパニングツリーを使用したまま、他方のスパニングツリーを用いてネットワーク構成変更後の新たなスパニングツリーを生成する。そして、新たなスパニングツリーの安定後に、フレーム転送に使用するスパニングツリーをその新たなスパニングツリーに切り替えるといった手法である。
【０００７】
この方式では、ノードやリンクの追加、削除によりネットワークの構成変更が行われる際に不安定となっているスパニングツリーはフレーム転送に用いられず、常に安定状態のスパニングツリーを利用しながら、ネットワーク構成変更を行うことが可能となる。
【０００８】
【非特許文献１】次世代イーサネット(R)アーキテクチャＧＯＥ（Global Optical Ethernet(R)）の提案  −（３）サービス無停止型スパニングツリー再構築と負荷分散−（２０００年電子情報通信学会通信ソサイエティ大会講演論文集：２００２年８月２０日発行）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述した従来の技術においては、以下に述べるような課題があった。
【００１０】
第１に、上述した非特許文献１に述べられている方式では、ネットワークにおいて使用できるスパニングツリーの数が制限される。
【００１１】
すなわち、非特許文献１の方式では、スパニングツリーを２面用意して、片方をフレーム転送用、他方をネットワーク構成変更に伴う新たなスパニングツリー構築用に用いられる。
【００１２】
従って、フレーム転送用のスパニングツリーをＮ面使用する場合には、２Ｎ面のスパニングツリーを用意することが必要となる。スパニングツリーを複数面使用する場合、一般的にはＶＬＡＮタグによって、ツリーを識別することが主流となっており、ネットワークで使用できるスパニングツリーの面数は一般にVLAN-ID数として規定される４０９６から予約ID数（VLAN-ID=4095は予約されており使用できない）を引いた４０９５面となる。
【００１３】
非特許文献１による方式では、フレーム転送に使用する２倍の面数のスパニングツリーが必要となることから、実際にフレーム転送用に使用できるスパニングツリーの面数は最大で２０４７面となり通常時の半分に制限されることになる。このことから、ネットワークの拡張性が制限されるという問題がある。
【００１４】
第２に、非特許文献１による方式では、スパニングツリーの処理負荷が増大する。
【００１５】
すなわち、非特許文献１による方式では、上述のように、フレーム転送用にＮ面のスパニングツリーを使用する場合に、その２倍の面数（２Ｎ）のスパニングツリーを動作させるため、スパニングツリーを制御するための制御フレームの数を２倍の処理しなければならず、処理負荷が増大する。
【００１６】
本発明の目的は、ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成を可能にすると共に、ネットワークで使用できるスパニングツリーの数が２分の１に制限されていた従来の問題を回避し、拡張性を保持することができるネットワークシステム、ツリー再構成処理方法、ノード、ツリー再構成処理プログラムを提案することにある。
【００１７】
また、本発明の他の目的は、スパニングツリーを制御するための制御フレームの数を少なくして、制御フレームの処理に要する処理の負荷を低減させることのできるネットワークシステム、ツリー再構成処理方法、ノード、ツリー再構成処理プログラムを提供することにある。
【課題を解決するための手段】
【００１８】
上記目的を達成するため本発明のネットワークシステムでは、  複数のノードを接続したネットワーク上でフレームを転送する経路として複数のツリーを使用するネットワークシステムにおいて、前記ネットワークにノードが追加又は削除されることにより前記ツリーを再構成する際に使用する少なくとも一の予備用のツリーを設け、前記予備用ツリーを、前記複数のツリーの前記ツリー再構成において共用する構成としている。
【００１９】
本発明によれば、管理サーバが、追加され又は削除されるノードからの追加又は削除要求を受け、前記予備用ツリーの使用状況を確認し、前記予備用ツリーが使用可能である場合に、前記追加又は削除対象のノードに対して許可を通知すると共に、要求された前記ツリーのルートノードに対してツリー再構成を要求する。
【００２０】
または、前記ツリーのルートノードが、前記追加され又は削除されるノードからの追加又は削除要求を受け、前記管理サーバに対して前記予備用ツリーの使用状況を問い合わせると共に、前記管理サーバは、前記予備用ツリーが使用可能である場合に、前記ツリーのルートノードに対してツリー再構成を要求する。
【００２１】
また、追加され又は削除されるノードが、前記予備用ツリーの使用予約を前記ネットワーク内に通知し、前記予備用ツリーが使用中でなければ、前記予備用ツリーの使用を前記ネットワーク内に通知して、当該ツリーのルートノードに対して追加又は削除の要求を行い、当該ツリーのルートノードが、前記追加又は削除の要求を受け、ツリー再構成の処理を実行する。
【００２２】
（作用）
本発明は、フレーム転送が行われている複数のスパニングツリーに対する、ノードの追加又はノード削除によるツリー再構成の際に、管理サーバが、スパニングツリーに追加され又はスパニングツリーから削除されるノードからの追加又は削除要求を受けると、予備用ツリーの使用状況を確認し、予備用ツリーが使用可能である場合に、追加又は削除対象のノードに対して許可を通知すると共に、要求されたスパニングツリーのルートノードに対してツリー再構成を要求する。要求を受けたスパニングツリーのルートノードは、予備用ツリーを使用することにより、ネットワークを停止させることなくツリー再構成の処理を実行する。
【００２３】
あるいは、スパニングツリーのルートノードが、スパニングツリーに追加され又はスパニングツリーから削除されるノードからの追加又は削除要求を受けると、管理サーバに対して予備用ツリーの使用状況を問い合わせる。使用状況の問い合わせを受けた管理サーバは、予備用ツリーが使用可能である場合に、スパニングツリーのルートノードに対してツリー再構成を要求する。
【００２４】
また、スパニングツリーの状態を管理する専用の管理サーバを備えない場合には、スパニングツリーに追加され又はスパニングツリーから削除されるノードが、予備用ツリーの使用予約をネットワーク内に通知し、予備用ツリーが使用中でなければ、予備用ツリーの使用をネットワーク内に通知することで、スパニングツリーのルートノードに対して追加又は削除の要求を行う。
【００２５】
これにより、ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成が可能となる。
【発明の効果】
【００２６】
本発明のネットワークシステムによれば、以下に述べるような優れた効果が達成される。
【００２７】
複数のスパニングツリーに対する、ノードの追加又はノード削除によるツリー再構成に使用するための少なくとも一の予備用のツリーを設け、この予備用ツリーを複数のスパニングツリーのツリー再構成において共用する構成としたので、ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成を可能にすると共に、ネットワークで使用できるスパニングツリーの数が２分の１に制限されていた従来の課題を回避し、拡張性を保持することができる。
【００２８】
また、スパニングツリーを制御するための制御フレームの数を少なくして、制御フレームの処理に要する処理の負荷を低減させることができる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００３０】
以降の説明の中で、複数のスパニングツリーおよび複数のノード群を識別する識別子としてタグを用いた説明を行うが、このタグは、ＶＬＡＮタグのほかに、本特許出願人による特開２００４−１４０７７６号に開示される拡張タグ及び他のタグもしくは識別手段のうち、単独もしくは何れか１つ以上の組み合わせを意味する。
【００３１】
ここで、本発明において用いるタグのうち、上記特開２００４−１４０７７６号に開示される拡張タグ付きフレームのフォーマットについて説明する。
【００３２】
図１は、ＩＥＥＥ８０２．１Ｑで規定されているＶＬＡＮタグ付きのイーサネット(R)フレームのフォーマットである。ＶＬＡＮタグ付きイーサネット(R)フレーム３２００は、送信先ＭＡＣアドレス３２０１と、送信元ＭＡＣアドレス３２０２と、ＶＬＡＮタグ３２０３と、イーサネット(R)属性情報３２０４と、ペイロード３２０５と、ＦＣＳ（Frame Check Sequence）３２０６とから構成される。
【００３３】
これに対して、図２は、本発明の拡張タグ付きイーサネット(R)フレームのフォーマットである。拡張タグ付きイーサネット(R)フレーム３３００は、送信先ＭＡＣアドレス３２０１と、送信元ＭＡＣアドレス３２０２と、拡張タグ格納領域３３０１と、イーサネット(R)属性情報３２０４と、ペイロード３２０５と、ＦＣＳ３２０６とから構成され、既存のＶＬＡＮタグ付きイーサネット(R)フレーム３２００のＶＬＡＮタグ３２０３が拡張タグ格納領域３３０１に置き換わる。
【００３４】
また図３に示すように別の構成の拡張タグ付きイーサネット(R)フレーム３４００も存在し、これは送信先ＭＡＣアドレス３２０１と、送信元ＭＡＣアドレス３２０２と、拡張タグ格納領域３３０１と、ＶＬＡＮタグ３２０３と、イーサネット(R)属性情報３２０４と、ペイロード３２０５と、ＦＣＳ３２０６とから構成され、拡張タグ格納領域３３０１は送信元ＭＡＣアドレス３２０２の後に挿入される。
【００３５】
拡張タグ格納領域３３０１には１つまたは複数の拡張タグを格納可能である。拡張タグ１個のサイズは４バイトであり、ＶＬＡＮタグ３２０３と同一サイズとなっている。拡張タグ付きイーサネット(R)フレーム３３００、３４００の最上段の拡張タグとＶＬＡＮタグ付きイーサネット(R)フレーム３２００のＶＬＡＮタグは同一の位置に同一のサイズで格納されており、その区別は各々のタグの上位２バイトに格納される値を変更することにより区別する（詳細については後述する）。
【００３６】
これにより、拡張タグ付きイーサネット(R)フレーム３３００、３４００は、ＶＬＡＮタグ付きイーサネット(R)フレーム３２００と互換性を有しており、既存ノード、拡張タグ対応ノードの双方においてどちらのフレームも処理可能である。
【００３７】
図４は、拡張タグ格納領域３３０１を示している。図４に示す格納例では、８個の拡張タグ３５００〜３５０７が格納されている。
【００３８】
フォワーディングタグ３５００には宛先ノード（宛先クライアントが接続するノード）の識別子や宛先までのラベル（例えばＭＰＬＳラベル）が格納される。また、宛先ノードの識別子を格納したフォワーディングタグ３５００に加えて、送信元ノードの識別子を格納する場合もある。各ノードはこのフォワーディングタグを参照してフレーム転送先を決定する。このフォワーディングタグ３５００は拡張タグ付きイーサネット(R)フレーム３３００、３４００において必ず格納される。
【００３９】
拡張タグの種類としては、カスタマ分離タグ３５０１、プロテクションタグ３５０２、ＯＡＭ＆Ｐタグ３５０３、品質情報タグ３５０４、フレーム制御タグ３５０５、セキュリティタグ３５０６、ユーザ拡張タグ３５０７が格納されている。
【００４０】
カスタマ分離タグ３５０１には、各ノードに収容されるカスタマ毎に情報を分離するための識別子が格納される。カスタマとしては、同一のＶＬＡＮの所属するカスタマを同一カスタマとする場合や、２つ以上のノードの特定のポートに収容されるカスタマを同一カスタマとする場合や、網内のノードに接続する２つ以上のホストを同一カスタマとする場合などがある。これらのカスタマに対して分離識別子が割り当てられ、各カスタマからのフレームにはカスタマ分離タグ３５０１内にこの分離識別子が格納される。カスタマ分離タグ３５０１によってカスタマを識別することにより、カスタマ単位の付加サービス（例えば、特定カスタマに対する優先制御など）の提供が可能となる。また、カスタマ分離タグ３５０１は複数スタックして使うことも可能である。この場合、分離可能なカスタマ数を大幅に増やすことができる。なお、カスタマ分離タグ３５０１をスタックする場合には、スタックした最終段のカスタマ分離タグ３５０１は最終段であることを示す特別なカスタマ分離タグを使用する。
【００４１】
プロテクションタグ３５０２には、障害発生時の障害情報や障害復旧のための迂回経路情報が格納される。ＯＡＭ＆Ｐタグ３５０３には、運用／管理情報が格納される。
【００４２】
品質情報タグ３５０４には、遅延、ジッタ、パケットロス率やフレームのネットワーク内への流入時間を示すタイムスタンプ、帯域制御情報等の品質情報が格納される。品質情報タグ３５０４にタイムスタンプ値が格納されている場合、フレームを受信したノードは現在の時刻とタイムスタンプ値よりそのフレームの網内遅延（ネットワーク内での滞在時間）を算出することができる。網内遅延の保証値が定められている場合には、保証値を実現できるよう優先処理を実施することができる。また、品質情報タグ３５０４に要求帯域や蓄積データ量やトラヒッククラス等の帯域制御情報が格納されている場合、そのフローの蓄積データ量やトラヒッククラスと他のフローのトラヒック状況を考慮して、要求帯域を確保するための帯域制御を実施することができる。
【００４３】
フレーム制御タグ３５０５には、フレームのネットワーク内での生存時間を制限するホップカウンタ（ＴＴＬ  ：  Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）や誤り検出のためのＣＲＣなどの情報が格納される。ＴＴＬが格納される場合には、経由するノード毎にＴＴＬ値が減算され、ＴＴＬ＝０となったところでこのフレームは廃棄される。これにより、ループ経路になった場合でもフレームが循環し続けるのを防ぐことができる。またＣＲＣが格納される場合には、入口側ノードにおける拡張タグ格納領域３３０１のＣＲＣ演算結果が格納されており、出口側ノードにおいて再度ＣＲＣ演算を実施して格納値と比較することにより、拡張タグ格納領域３３０１の誤りを検出可能である。
【００４４】
セキュリティタグ３５０６には、フレームの信頼性、ネットワーク構築時やネットワーク構成変更時の秘匿性を確保するための情報が格納される。セキュリティタグ３５０６の利用例としては以下の例があげられる。ネットワーク内で通信するカスタマにはカスタマ毎のセキュリティ識別子が予め設定され、その識別子はカスタマが接続する各ノードで保持される。各カスタマはフレーム転送の際に、設定されたセキュリティ識別子を常にセキュリティタグ３５０６に格納することにより、カスタマ分離タグ３５０１の情報を改ざんした悪意のあるカスタマからのフレーム送受信を防ぐことができる。また、ネットワーク構築時やネットワーク構成変更時において、ノード間でネゴシエートして共通のセキュリティ識別子を設定する。当該ノード間のフレーム転送の際に、設定したセキュリティ識別子を常にセキュリティタグ３５０６に格納することにより、悪意のあるノードをネットワークに接続するのを防ぐことができる。
【００４５】
ユーザ拡張タグ３５０７には、ユーザが独自に定義する任意の情報が格納される。ユーザが独自にタグのフォーマット及び格納情報を定義し、その処理内容を定義することにより、ユーザ独自の機能拡張を図ることができ、ネットワークの柔軟性を高められる。
【００４６】
フォワーディングタグ３５００以外の拡張タグ３５０１〜３５０７は、必要に応じて格納される。フォワーディングタグ３５００は、拡張タグ格納領域３３０１の先頭に格納され、その他の拡張タグ３５０１〜３５０７はその後方に格納される。フォワーディングタグ３５００よりも後方であれば、予め決められた固定位置でも、任意の位置でも良い。
【００４７】
以降、２系統存在するスパニングツリーのうち、新しくネットワークに挿入されるデータフレームの転送に利用しているスパニングツリーを現用ツリー、現用ツリーとなっていないツリーを予備用ツリーと表現する。
【００４８】
ＢＰＤＵ(Bridge Protocol Data Unit)とは、スパニングツリー生成のために交換されるＩＥＥＥ８０２．１Ｄ（従来技術１）およびＩＥＥＥ８０２．１ｗ（従来技術２）に記載される制御データおよび、本発明の現用と予備用の識別情報等を含む制御フレームのことをいう。
【００４９】
図５は、ＩＥＥＥ８０２．１Ｄ（従来技術１）およびＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  BPDU２２０５の構造を示すフォーマット図である。
【００５０】
ＭＡＣ  ＤＡ２２０１は、宛先ＭＡＣアドレスを格納する領域である。
【００５１】
ＭＡＣ  ＳＡ２２０２は、送信元ＭＡＣアドレスを格納する領域である。
【００５２】
タグ領域２２０３は、複数のスパニングツリーを識別する識別子としてのタグを挿入する領域である。また、従来技術には記載されていないが、前記タグは、ＶＬＡＮタグのほかに、本特許出願人による特開２００４−１４０７７６号に開示される拡張タグ、及び他のタグもしくは識別手段の何れか１つ以上の組み合わせたタグでもよい。
【００５３】
Ｔｙｐｅ２２０４は、フレームのタイプ識別子を格納する領域である。
【００５４】
BPDU領域２２０５は、ＩＥＥＥ８０２．１Ｄ（従来技術１）およびＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ＢＰＤＵ  ｐａｒａｍｅｔｅｒｓに相当する情報を格納する領域である。
【００５５】
ＦＣＳ２２０６は、フレームチェックシーケンスを格納する領域である。
【００５６】
Ｐｒｏｔｏｃｏｌ  Ｉｄｅｎｔｉｆｉｅｒ２２０５１は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｐｒｏｔｏｃｏｌ  Ｉｄｅｎｔｉｆｉｅｒと等しい情報を格納する領域である。
【００５７】
Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  Ｉｄｅｎｔｉｆｉｅｒ２２０５２は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  Ｉｄｅｎｔｉｆｉｅｒと等しい情報を格納する領域である。
【００５８】
ＢＰＤＵ  Ｔｙｐｅ２２０５３は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、ＢＰＤＵ  Ｔｙｐｅと等しい情報を格納する領域である。
【００５９】
Ｆｌａｇｓ２２０５４は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｆｌａｇｓと等しい情報を格納する領域である。
【００６０】
Ｒｏｏｔ  Ｉｄｅｎｔｉｆｉｅｒ２２０５５は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｒｏｏｔ  Ｉｄｅｎｔｉｆｉｅｒと等しい情報を格納する領域である。
【００６１】
Ｒｏｏｔ  Ｐａｔｈ  Ｃｏｓｔ２２０５６は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｒｏｏｔ  Ｐａｔｈ  Ｃｏｓｔと等しい情報を格納する領域である。
【００６２】
Ｂｒｉｄｇｅ  Ｉｄｅｎｔｉｆｉｅｒ２２０５７は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｂｒｉｄｇｅ  Ｉｄｅｎｔｉｆｉｅｒと等しい情報を格納する領域である。
【００６３】
Ｐｏｒｔ  Ｉｄｅｎｔｉｆｉｅｒ２２０５８は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｐｏｒｔ  Ｉｄｅｎｔｉｆｉｅｒと等しい情報を格納する領域である。
【００６４】
Ｍｅｓｓａｇｅ  Ａｇｅ２２０５９は、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｍｅｓｓａｇｅ  Ａｇｅと等しい情報を格納する領域である。
【００６５】
ＭＡＸ  Ａｇｅ２２０５Ａは、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、ＭＡＸ  Ａｇｅと等しい情報を格納する領域である。
【００６６】
Ｈｅｌｌｏ  Ｔｉｍｅ２２０５Ｂは、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｈｅｌｌｏ  Ｔｉｍｅと等しい情報を格納する領域である。
【００６７】
Ｆｏｒｗａｒｄ  Ｄｅｌａｙ２２０５Ｃは、ＩＥＥＥ８０２．１Ｄ（従来技術１）もしくはＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｆｏｒｗａｒｄ  Ｄｅｌａｙと等しい情報を格納する領域である。
【００６８】
図６は、ＩＥＥＥ８０２．１Ｄ（従来技術１）およびＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｔｏｐｏｌｏｇｙ  Ｃｈａｎｇｅ  Ｎｏｔｉｆｉｃａｔｉｏｎ  BPDUの構造を示すフォーマット図である。
【００６９】
ＭＡＣ  ＤＡ２２０１は、宛先ＭＡＣアドレスを格納する領域である。
【００７０】
ＭＡＣ  ＳＡ２２０２は、送信元ＭＡＣアドレスを格納する領域である。
【００７１】
タグ領域２２０３は、従来技術には記載されていないが、複数のスパニングツリーを識別する識別子としてのタグを挿入する領域である。前記タグは、ＶＬＡＮタグのほかに、上記特開２００４−１４０７７６号に開示される拡張タグ、及び他のタグもしくは識別手段の何れか１つ以上の組み合わせたタグでもよい。
【００７２】
Ｔｙｐｅ２２０４は、フレームのタイプ識別子を格納する領域である。
【００７３】
BPDU領域２２０５は、ＩＥＥＥ８０２．１Ｄ（従来技術１）およびＩＥＥＥ８０２．１ｗ（従来技術２）に記載の、Ｔｏｐｏｌｏｇｙ  Ｃｈａｎｇｅ  Ｎｏｔｉｆｉｃａｔｉｏｎ  ＢＰＤＵ  ｐａｒａｍｅｔｅｒｓに相当する情報を格納する領域である。
【００７４】
ＦＣＳ２２０６は、フレームチェックシーケンスを格納する領域である。
【００７５】
次に、図７を用いて、拡張タグフレーム３３００および３４００の他のフレームフォーマットについて説明する。
【００７６】
図７の上部はＶＬＡＮタグ３２０３の詳細なフレームフォーマットである。ＴＰＩＤ（Ｔａｇ  Ｐｒｏｔｏｃｏｌ  Ｉｄｅｎｔｉｆｉｅｒ）２８００には、値「０ｘ８１００」が設定されている。なお、標準規格外ではあるが値「０ｘ９１００」が使用される場合もある。また、ＴＣＩ２８０１はＰｒｉｏｒｉｔｙフィールド２８０２とＣＦＩフィールド２８０３とＶＬＡＮ−ＩＤフィールド２８０４から構成される。
【００７７】
Ｐｒｉｏｒｉｔｙフィールド２８０２にはフレームの優先度が格納され、その優先度の値はＩＥＥＥ８０２．１ｐにおいて規定されている。また、ＣＦＩフィールドには特殊ルーティング情報の有無またはＭＡＣアドレスのフォーマットの種別を示す値が格納され、ＶＬＡＮ−ＩＤフィールド２８０４にはＶＬＡＮ−ＩＤが格納される。
【００７８】
これに対して、図７の下部に示す拡張タグフレームフォーマットでは、ＴＰＩＤ２８００及びＴＣＩ２８０１の中のＣＦＩフィールド２８０３はＶＬＡＮタグ３２０３と同様であり、Ｐｒｉｏｒｉｔｙフィールド２８０２がＰｒｉｏｒｉｔｙ／タグＴｙｐｅフィールド５００３に、ＶＬＡＮ−ＩＤフィールド２８０４が拡張タグ情報フィールド５００４に変更される。なお、対応するフィールドのサイズは同様である。
【００７９】
本拡張タグフレームフォーマットでは、Ｐｒｉｏｒｉｔｙ／タグＴｙｐｅフィールド５００３に拡張タグ３５００〜３５０８の種別を格納する。なお、拡張タグ３５００〜３５０８使用時にも従来のＩＥＥＥ８０２．１ｐをサポートできるように、既存のＶＬＡＮタグ３２０３のＰｒｉｏｒｉｔｙフィールド２８０２（ＩＥＥＥ８０２．１ｐ）におけるＰｒｉｏｒｉｔｙ値の一部を拡張タグ３５００〜３５０８の種別として用いる。
【００８０】
具体的には１１０、１００、００１、０００を拡張タグ３５００〜３５０８用として用いることとし、１１１（予約用）、１０１（会話型マルチメディア用）、０１１（クリティカルアプリケーション用）、０１０（標準的ストリーム用）については従来のＩＥＥＥ８０２．１ｐ互換とする。
【００８１】
そのため、使用できる拡張タグ３５００〜３５０８は４つに制限しており、例えばフォワーディングタグ３５００、ブロードキャストフォワーディングタグ３５０８、カスタマ分離タグ３５０１、ＯＡＭ＆Ｐタグ３５０３を使用し、Ｐｒｉｏｒｉｔｙ/タグＴｙｐｅフィールドの値との対応を００１＝フォワーディングタグ３５００、０００＝ブロードキャストフォワーディングタグ３５０８、１１０＝カスタマ分離タグ３５０１、１００＝ＯＡＭ＆Ｐタグ３５０３とする。これにより、上記４種類の拡張タグを識別できると共に、ＩＥＥＥ８０２．１ｐの中の４つの優先度をサポートできる。各ネットワーク上の各ノードには、上記Ｐｒｉｏｒｉｔｙ/タグＴｙｐｅフィールドの値と拡張タグとの対応が記憶されている。なお、使用する拡張タグの選択とそれに対応するＰｒｉｏｒｉｔｙ/タグＴｙｐｅフィールドの値の設定についてはこの例に限定されるわけではない。
【００８２】
また、図７に示す拡張タグフレームフォーマットでは、拡張タグ情報フィールド５００４において、拡張タグ３５００〜３５０８のタグ種別に応じたアドレス情報などの情報が格納される。例えば、フォワーディングタグ３５００の場合、宛先ノードのアドレス情報が格納され、ブロードキャストフォワーディングタグ３５０８の場合、送信元ノードのアドレス情報が格納され、カスタマ分離タグ３５０１の場合、カスタマの識別情報が格納される。
【００８３】
（実施の形態１）
【００８４】
以下、本発明の第１の実施の形態について、図面を参照して詳細に説明する。
【００８５】
図８を参照すると、本発明の第１の実施の形態によるネットワークシステムは、ノード３００１〜３００６、クライアント９１〜９６、リンク８１〜８６、リンク２１〜２８を含む。
【００８６】
ノード３００１の有する機能を以下に記載する。
【００８７】
（１）リンク２１もしくはリンク２４より到着したフレームを、リンク２４もしくはリンク２１に転送する。
【００８８】
（２）リンク８１より到着したフレームに、転送に必要なタグ（拡張タグ等）を付加した上で、リンク２１もしくはリンク２４に転送する。
【００８９】
（３）リンク２１もしくはリンク２４より到着したフレームを、ノード間の転送に必要なタグ（拡張タグ等）を削除した上で、リンク８１に転送する。
【００９０】
（４）スパニングツリーを構成するために、他のノードとの間で制御フレーム（BPDU）の送受信を行う。
【００９１】
ノード３００２〜３００６は、ノード３００１と同様のノードである。以後、ノード３００１〜３００６を代表して、ノード３００１を用いて記述を行うが、これらノード３００１についての記述は、特に断りのない限り他のノード３００２〜３００６においても同様に実現可能である。
【００９２】
クライアント９１は、図８では１台のクライアント端末しか描いていないが、１つ以上のクライアントの集合としてもよく、リンク８１を通じて、ノード３００１との間でフレームの送受信を行う機能を有する。
【００９３】
クライアント９２〜９６は、クライアント９１と同様のクライアント端末またはクライアント群である。以後、クライアント９１〜９６を代表してクライアント９１を用いて記述を行うが、クライアント９１についての記述は、特に断りのない限り他のクライアント９２〜９６においても同様に適用可能である。
【００９４】
リンク８１は、クライアント９１からノード３００１、及び、ノード３００１からクライアント９１を結ぶ双方向リンクである。
【００９５】
リンク８２〜８６は、リンク８１と同様のリンクである。以後、リンク８１〜８６を代表してリンク８１を用いて記述を行うが、リンク８１についての記述は、特に断りのない限り他のリンク８２〜８６においても同様に適用可能である。
【００９６】
リンク２１は、ノード３００１からノード３００２、及び、ノード３００２からノード３００１を結ぶ、双方向リンクである。
【００９７】
リンク２２〜２８は、リンク２１と同様のリンクである。以後、リンク２２〜２８を代表してリンク２１を用いて記述を行うが、リンク２１についての記述は、特に断りのない限り他のリンク２２〜２８においても同様に適用可能である。
【００９８】
図９は、図８に示すネットワークを構成するノード３００１の構成を詳細に示した図である。
【００９９】
ノード３００１は、フレーム転送器１１１と、タグ挿入器１１２と、タグ削除器１１３と、フォワーディングテーブル１１４と、ＳＴＰコントローラ１１５と、再構成コントローラ１１６、フレーム分別器１１７と、設定インタフェース１１８を備える。
【０１００】
フレーム転送器１１１は、フレーム分別器１１７を介してリンク２１もしくはリンク２４から受信したフレーム、或いはタグ挿入器１１２より受信したフレームを、フォワーディングテーブル１１４の記述内容に従い、リンク２１もしくはリンク２４、或いはタグ削除器１１３に転送する。
【０１０１】
タグ挿入器１１２は、リンク８１を通じてクライアント９１より受信したフレームに対し、タグ（拡張タグ）を挿入することにより、フレーム転送器１１１に転送する。なお、タグ（拡張タグ）を挿入することなく、受信したフレームをそのままフレーム転送器１１１に転送することもできるほか、同一フレームに１個以上のタグ（例えば、図４に示した３５００〜３５０８のうちの各タグの関係に矛盾が生じない複数のタグ）を挿入し、もしくは、到着したフレームをコピーし、コピーしたそれぞれのフレームに対して、同一もしくは異なるタグ（拡張タグ）を、１個以上挿入することも可能である。
【０１０２】
タグ削除器１１３は、リンク８１に接続されており、フレーム転送器１１１より受信したフレームに付加されているタグ（拡張タグ）を外し、リンク８１を通じてクライアントに転送する。なお、設定によって、タグ（拡張）を外さずに、受信したフレームをそのままリンク８１に転送することも可能である。
【０１０３】
フォワーディングテーブル１１４は、フレーム転送器１１１からの問い合わせに対し、ＭＡＣアドレス、タグ、もしくは入力ポートの他、１つ以上の組み合わせをキーとして、1つ以上のフレーム転送先ポートをフレーム転送器１１１に返答する。キーおよび転送先ポートは、ＳＴＰコントローラ１１５、再構成コントローラ１１６により設定される。
【０１０４】
フレーム分別器１１７は、受信したフレームについてフレーム種別を解析し、当該フレームがデータフレームである場合に、前記フレームをフレーム転送器１１１に転送し、当該フレームがBPDUである場合、ＳＴＰコントローラ１１５、再構成コントローラ１１６に転送し、当該フレームが再構成用制御フレームである場合、再構成コントローラ１１６に転送する。
【０１０５】
ＳＴＰコントローラ１１５は、フレーム分別器１１７からＢＰＤＵを受信し、ＢＰＤＵ内のRoot Identifierフィールド ２２０５５、Root Path Costフィールド ２２０５６、Bridge Identifierフィールド ２２０５７、Port Identifierフィールド ２２０５８に含まれる情報を用いて、IEEE802.1D／1wの処理手順に従いスパニングツリーのポート情報を更新し、新たなＢＰＤＵを作成し、この新たなBPDUをフレーム転送器１１１に対して送信する。ＳＴＰコントローラ１１５で制御するスパニングツリーは、再構成コントローラ１１６または設定インタフェース１１８からのトリガにより起動/停止される。各スパニングツリーのパラメータは設定インタフェース１１８によって設定される。
【０１０６】
再構成コントローラ１１６は、フレーム分別器１１７から再構成制御フレームを受信し、受信した再構成制御フレームに応じた制御を行い、必要に応じて制御フレームを再生成し、フレーム転送器１１１に対して、再構成制御フレームを送信する。なお、再構成制御フレームの種類やそれに応じた処理については後述する。また、フレーム分別器１１７からＢＰＤＵを受信すると、ＢＰＤＵに含まれる情報からスパニングツリーのルートノード情報を取得し、保持する。詳細については、後述する。再構成制御に関するパラメータ設定や起動トリガは設定インタフェース１１８を介して行われる。また、再構成制御の中でＳＴＰコントローラ１１５に対して、スパニングツリーの起動/停止のトリガを与える。処理の詳細については、後述する。
【０１０７】
設定インタフェース１１８は、ネットワーク管理者から入力されるスパニングツリーの起動/停止、再構成制御の起動（ノード追加要求、ノード削除要求）に関するトリガ、または、スパニングツリーのパラメータや再構成制御のパラメータ（タイマ値など）をＳＴＰコントローラ１１５、再構成コントローラ１１６に通知する。ネットワーク管理者の入力端末と設定インタフェース１１８との間の形態としては、シリアル接続またはＴＥＬＮＥＴ接続を介してコマンドラインインタフェースで入力される場合や、ＷＥＢサーバ等からグラフィックユーザインタフェースで入力される場合があり、設定インタフェース１１８は各々の形態をサポートする。
【０１０８】
図１０は、本実施の形態の図８における、タグをキーとして出力ポートを決定するための、フォワーディングテーブル１１４の構成例である。
【０１０９】
タグフィールド１１４１は、サーチのインデックスになるフィールドであり、このフィールドの情報と、受信したフレームのタグに書かれている内容が一致するかどうかが調べられる。
【０１１０】
フラグ１１４２は、そのタグが現用か予備用かを意味するフラグ値が記載される。フラグ１１４２には「０」か「１」が記載され、「１」の場合は、そのタグが現用であり、「０」の場合は、そのタグは予備用であり、共有するタグ（本実施例では４０９５）が現用であることを意味する。従って、「１」の場合はそのタグのエントリを参照して出力ポートを決定し、「０」の場合は共有するタグのエントリを参照して出力ポートを決定する。
【０１１１】
また、出力ポート１１４３は、そのタグが付加されたフレームを転送すべきポートを記載するフィールドである。
【０１１２】
なお、本実施の形態は、本動作例に示すような、タグの内容によって転送先ポートを決定するタグフォワーディングを行う場合のみならず、従来より行われている、ＭＡＣアドレスによって転送先を決定する通常のＭＡＣアドレス転送においても、同様に適用可能である。この場合は、出力ポートフィールド１１４３に、複数のポートが記載される。
【０１１３】
また、図１１は、本発明の第１の実施の形態の図８における、ノード３００１の再構成コントローラ１１６の構成を詳細に示した図である。
【０１１４】
再構成コントローラ１１６は、タグ削除器１１６１と、制御フレーム送受信部１１６２と、タグ挿入器１１６３と、再構成処理部１１６４と、拡張再構成処理部１１６５と、再構成管理テーブル１１６６と、安定タイマ１１６７を備えて構成される。
【０１１５】
制御フレーム送受信部１１６２は、再構成処理部１１６４の制御によって、ツリーの再構成処理に必要な制御フレームである、再構成制御フレームの送受信を行う。この制御フレームの種類と内容については、後述する。
【０１１６】
タグ削除器１１６１は、フレーム分別器１１７から入力された制御フレームに挿入されているタグを削除し、制御フレーム送受信部１１６２に転送する。もし、フレーム分別器１１７から受信した制御フレームにタグが添付されていない場合には、受信した制御フレームをそのまま制御フレーム送受信部１１６２に転送する。
【０１１７】
制御フレーム送受信部１１６２は、タグ削除器１１６１より再構成制御フレームを受信し、フレームに含まれる情報を、再構成処理部１１６４に通知する。また、再構成処理部１１６４からスパニングツリーの再構成処理において使用される再構成用の制御フレーム（再構成制御フレーム）を受信し、タグ挿入器１１６３に通知する。
【０１１８】
タグ挿入器１１６３は、制御フレーム送受信部１１６２より再構成制御フレームを受信し、あらかじめ設定されているタグ（デフォルトのVLANタグ（例えば、「０」か「１」の値）か、制御用VLANタグとして用意されたVLANタグ（任意の値））を挿入し、フレーム転送器１１１に送信する。なお、タグを挿入することなく、フレームをそのまま転送する設定も可能である。
【０１１９】
再構成処理部１１６４は、タグ削除器１１６１でタグが削除された制御フレームを、制御フレーム送受信部１１６２から受け取り、受け取った各制御フレームに応じた処理を行う。また、制御フレームを次ノードに転送する必要がある場合は、再構成処理部１１６４から制御フレーム送受信部１１６２、さらにタグ挿入器１１６３を経て、タグが付加された制御フレームがフレーム転送器１１１によって、適切なポートに転送され、次ノードに転送される。
【０１２０】
拡張再構成処理部１１６５は、再構成処理部１１６４との間で再構成処理の開始と終了の通知をやり取りすると共に、再構成処理部１１６４による制御内容を、ＳＴＰコントローラ１１５や他のノード（或いはサーバ）に通知する機能を有する。
【０１２１】
再構成管理テーブル１１６６は、ツリー再構成に使用する予備用ツリーの使用状況及びツリー再構成の対象となるツリーに関する情報を格納するテーブルである。
【０１２２】
安定タイマ１１６７は、再構成処理部１１６４によって複数のタイマモードがセットされ、タイマモード毎に設定された時間が経過すると、再構成処理部１１６４に対してタイマ満了通知を送信する。
【０１２３】
この安定タイマ１１６７にセットされるタイマモードとしては、タイマモード１からタイマモード４の４種類がある。それらの内容については、後述のツリー再構成の処理の説明で詳述する。
【０１２４】
本発明においては、スパニングツリープロトコル（ＳＴＰ）により構築したネットワークにおいて、現時点でフレーム転送が行われている複数のスパニングツリー（現用ツリー）と共に、ネットワークに新たなノードが追加され又はネットワークからノードが削除される際になされるツリーの再構成のために使用する予備用のスパニングツリー（予備用ツリー）を用意し、当該予備用ツリーを各現用ツリーの再構成において共用する構成としている。
【０１２５】
例えば、ＶＬＡＮによるネットワークにおいては、スパニングツリープロトコルにより最大４０９５面の論理的なツリーを管理することが可能である。
【０１２６】
このようなネットワークにおいて、各スパニングツリーにツリー再構成のための予備用ツリーを設けた場合には、現用ツリーの管理が最大２０４７面のツリーに限定されてしまうことになる。
【０１２７】
本発明では、複数の現用ツリーによって予備用ツリーを共用するシステム構成とすることにより、少なくとも１面の予備用ツリーを用意すればよくなり、このため、最大で４０９４（＝４０９５−１）面の現用ツリーを管理することが可能となる。
【０１２８】
実際のネットワーク形態としては、例えば、数百面の現用ツリーに対して、予備用ツリーを１面ないし数面設けるといった形態が考えられる。この予備用ツリーの面数については、現用ツリーの面数などのパラメータに応じて任意に設定することができ、最低１面の予備用ツリーが設けられていればよい。
【０１２９】
予備用ツリーは、少なくとも１つ用意され、ノードの追加、削除によるツリー再構成の際に、予備用ツリーを共有して使用（共用）することで、ネットワーク再構成を実現する。
【０１３０】
予備用ツリーを共用してネットワーク再構成を行う場合の処理としては、以下の処理が必要となる。
【０１３１】
（１）新たに追加されるノードからの追加要求又は削除されるノードからの削除要求があった場合に、ツリー再構成に使用する予備用ツリーの使用状況の管理を行うための処理。
【０１３２】
（２）ノードの追加、削除の処理を行う際に、ツリー再構成の対象となるツリーの再構成処理を実施済みか否かの状態を管理し、処理の順番を管理するための処理。
【０１３３】
本発明の第１の実施の形態によるネットワークシステムについて、図面を参照して説明する。
【０１３４】
図１２は、第１の実施の形態によるネットワークシステムの構成を示す図である。ネットワーク構成は図８に示す構成と同じであり、ここでは、クライアント９１〜９６を省略している。
【０１３５】
第１の実施の形態においては、新たなサーバの追加又はサーバの削除に伴うスパニングツリーの再構成において使用する、予備用ツリーの共有を制御するための管理用サーバ５０００を備えている。この管理用サーバ５０００は、ルートノードに設定されているノード３００１のＳＴＰコントローラ１１５に、設定インタフェース１１８を介して接続されている。
【０１３６】
この第１の実施の形態では、（１）ツリー再構成に使用する予備用ツリーの使用状況の管理を行うための処理と、（２）ツリー再構成の対象となるツリーの再構成処理実施状況および処理の順番の管理を行うための処理を、管理用サーバ５０００によって行う。
【０１３７】
管理用サーバ５０００については、ネットワークを構成するノードと個別に設けても良いし、ネットワークを構成するノード（例えば、ルートノード）にその機能を持たせることによっても実現することもできる。
【０１３８】
この管理用サーバ５０００は、プログラム制御されるコンピュータ装置（ＣＰＵ）で実現され、以下に説明する機能を達成する。
以下に述べる機能を実行する。
【０１３９】
（１）新たに加わるノードからの追加要求又はノードからの削除要求があった場合に、ツリー再構成に使用する予備用ツリーの使用状況の管理を行う機能。
【０１４０】
この使用状況の管理では、予備用ツリーが使用中であるかどうかの確認、予備用ツリーの確保と解放を行う。
【０１４１】
（２）ツリー再構成の対象となるツリーの再構成処理実施状況および処理の順番に関する管理を行う機能。
【０１４２】
ツリー再構成の対象となるツリーを認識し、当該対象となるツリーのルートノードに対し再構成処理に必要な制御を行う。
【０１４３】
また、管理用サーバ５０００には、図１２に示した再構成コントローラ１１６と同様の再構成管理テーブル１１６６が備えられており、必要な情報が予め設定されている。
【０１４４】
この管理用サーバ５０００の再構成管理テーブル１１６６の設定内容例を図１３に示す。
【０１４５】
図１３において、再構成管理テーブル１１６６には、現用の各スパニングツリーのツリーＩＤ５０１１、現用の各スパニングツリーのルートノードのＭＡＣアドレス５０１２が、予め設定されている。また、各スパニングツリーの再構成処理の完了の有無を示す再構成処理フラグ５０１３が設定される。この再構成処理フラグ５０１３については、以下に述べる再構成処理において随時設定される。
【０１４６】
以下、図１２から図１８を参照して、ネットワークに新たなノードが追加される場合の動作について説明する。
【０１４７】
ここでは、図１４に示すように、現用ツリーとして、ツリー＃４００１〜＃４００６の６つのツリーが存在し、その６つの現用ツリーが共用する予備用ツリーとして、１つのツリー＃４０９５が用意されたネットワークシステムについて、説明する。
【０１４８】
ノードが追加される前の各現用ツリー＃４００１〜＃４００６、予備用ツリー＃４０９５は、それぞれノード３００１〜３００６で構成されており、各スパニングツリーの状態を太線で示している。
【０１４９】
図１４に示すネットワーク状態においては、現用ツリー＃４００１ではノード３００１がルートノード、現用ツリー＃４００２ではノード３００２がルートノード、現用ツリー＃４００３ではノード３００３がルートノード、現用ツリー＃４００４ではノード３００４がルートノード、現用ツリー＃４００５ではノード３００５がルートノード、現用ツリー＃４００６ではノード３００６がルートノードとなっており、予備用ツリー＃４０９５ではノード３００１がルートノードとなっている。
【０１５０】
ここで、上記のような構成のネットワークに、図１５に示すように、新たなノード＃３０１２が追加される場合の処理について、図１６のシーケンス図を参照して説明する。
【０１５１】
まず、図１５に示すように、現用ツリー＃４００１に対する新たなノード３０１２の追加が実行される。
【０１５２】
（ステップＡ−１）
ノード３０１２からの追加要求メッセージを受けると、管理用サーバ５０００は、予備用ツリー＃４０９５の使用状態（使用が競合するかどうか、競合する場合どのノードが使用しているか等）の確認を行う。
【０１５３】
管理用サーバ５０００は、予備用ツリー＃４０９５が再構成処理のために使用されているか、使用されている場合にはどの現用ツリーが使用しているかを常時認識している。具体的には、予備用ツリー＃４０９５の使用状態を管理するフラグ（予備用ツリー使用状態管理フラグ）を内部管理し、いずれかのノードにより使用されている場合はフラグ＝ＯＮ、いずれのノードにも使用されていない場合はフラグ＝ＯＦＦとする。フラグ＝ＯＮの時に他のノードから使用要求があった場合、そのノードに対しては使用不可を返答する。
【０１５４】
（ステップＡ−２）
管理用サーバ５０００は、予備用ツリー＃４０９５が未使用状態である場合、すなわち予備用ツリー使用状態管理フラグ＝ＯＦＦである場合、フラグ＝ＯＮとして、ノード３０１２の追加処理に伴う再構成処理のために予備用ツリー＃４０９５を確保する。その後、ノード３０１２に対して現用ツリー＃４００１への追加を許可する旨のメッセージを通知する。
【０１５５】
（ステップＡ−３）
さらに、管理用サーバ５０００は、現用ツリー＃４００１のルートノード３００１に対して、予備用ツリー＃４０９５のルートノードとなることを要求するメッセージを通知する。
【０１５６】
（ステップＡ−４）
管理用サーバ５０００からの上記要求を受けた、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値よりも小さい値に設定変更する。これにより、ルートノード３００１はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが他のノードよりも小さくなるため予備用ツリー＃４０９５のルートノードとなる。その結果、予備用ツリー＃４０９５のスパニングツリーの状態は、図１７に示すように、現用ツリー＃４００１と同じ状態となる。
【０１５７】
（ステップＡ−５）
これにより、現用ツリー＃４００１において、予備用ツリー＃４０９５を利用して新たなノード３０１２を追加するための再構成処理（再構成処理）が実行される。このツリーの再構成処理の詳細については後述する。
【０１５８】
（ステップＡ−６）
現用ツリー＃４００１の再構成処理の終了後、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値に設定変更する。これにより、ルートノード３００１はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが通常の値に戻るためツリー＃４０９５のルートノードは網内のノードの中でＭＡＣアドレスが最も小さいノードが選択される状態に戻る。
【０１５９】
（ステップＡ−７）
さらに、現用ツリー＃４００１のルートノード３００１は、管理用サーバ５０００に対して、現用ツリー＃４００１へのノード３０１２の追加による再構成処理が完了した旨のメッセージを通知する。
【０１６０】
（ステップＡ−８）
管理用サーバ５０００では、上記再構成処理完了の通知を受けると、再構成管理テーブル５００１のエントリ５０１１のツリーＩＤ（＃４００１）に対応する再構成処理フラグ５０１３を「済（ＯＮ）」に設定する。
【０１６１】
その後、次のツリーである、図１４に示す現用ツリー＃４００２に対する新たなノード３０１２の追加が実行される。
【０１６２】
管理サーバ５０００は、再構成管理テーブル１１６６を参照し、再構成処理フラグフィールド５０１３が未処理状態であるツリーを選択し、そのツリーを次の再構成対象ツリーとして決定する。なお、未処理状態ツリーが複数存在する場合の決定方法については、特に制限はないが、例えば、ＩＤが若い順に行う等の方法が考えられる。
【０１６３】
ここでは、管理サーバ５０００は、再構成管理テーブル１１６６を参照して、ツリー＃４００２を次の再構成対象ツリーとする。
【０１６４】
（ステップＡ−９）
管理用サーバ５０００は、ノード３０１２に対して現用ツリー＃４００２への追加を許可する旨のメッセージを通知する。
【０１６５】
（ステップＡ−１０）
さらに、管理用サーバ５０００は、現用ツリー＃４００２のルートノード３００２に対して、予備用ツリー＃４０９５のルートノードとなることを要求するメッセージを通知する。
【０１６６】
（ステップＡ−１１）
これにより、管理用サーバ５０００からの上記要求を受けた、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値よりも小さい値に設定変更する。これにより、ルートノード３００２はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが他のノードよりも小さくなるため予備用ツリー＃４０９５のルートノードとなる。その結果、予備用ツリー＃４０９５のスパニングツリーの状態は、現用ツリー＃４００２と同じ状態となる。
【０１６７】
（ステップＡ−１２）
これにより、現用ツリー＃４００２において、予備用ツリー＃４０９５を利用して新たなノード３０１２を追加するための再構成処理（再構成処理）が実行される。このツリーの再構成処理の詳細については後述する。
【０１６８】
（ステップＡ−１３）
現用ツリー＃４００２の再構成処理の終了後、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値に設定変更する。これにより、ルートノード３００２はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが通常の値に戻るためツリー＃４０９５のルートノードは網内のノードの中でＭＡＣアドレスが最も小さいノードが選択される状態に戻る。
【０１６９】
（ステップＡ−１４）
さらに、現用ツリー＃４００２のルートノード３００２は、管理用サーバ５０００に対して、現用ツリー＃４００２へのノード３０１２の追加による再構成処理が完了した旨のメッセージを通知する。
【０１７０】
（ステップＡ−１５）
管理用サーバ５０００では、上記再構成処理完了の通知を受けると、再構成管理テーブル５００１のエントリ５０１１のツリーＩＤ（＃４００２）に対応する再構成処理フラグ５０１３を「済（ＯＮ）」に設定する。
【０１７１】
以下、上記と同じ処理を繰り返すことによって、現用ツリー＃４００３から＃４００６に対するノード３０１２の追加処理が実行される。
【０１７２】
以下、同様の手順によって、ノード＃３０１２の現用ツリー＃４００１〜＃４００６への追加処理が実行される。
【０１７３】
そして、全ての現用ツリー＃４００１〜＃４００６へのノード＃３０１２の追加処理が完了した時点で、管理用サーバ５０００は、予備用ツリー使用状態管理フラグ＝ＯＦＦとして、予備用ツリー＃４０９５を解放する。以降、他のノードから予備用ツリー＃４０９５の使用要求があった場合、先着のノードに対して予備用ツリーの使用が可能となる。
【０１７４】
上記のようにしてノード３０１２が追加された現用ツリー＃４００１〜＃４００６の状態を図１８に示す。
【０１７５】
なお、図１６においては、ネットワークシステムに対してノード＃３０１２が追加される場合の処理について説明したが、ネットワークを構成するノードが削除される場合の処理についても、図１６と同様の処理がなされる。すなわち、図１６において、「追加（又は追加処理）」とあるのを「削除（又は削除処理）」とすることで、ノードが削除される場合の処理が説明される。
【０１７６】
次いで、上記ステップＡ−５におけるツリーの再構成処理（再構成処理）の詳細について、図１９、２０を参照して説明する。
【０１７７】
ツリーの再構成処理で使用される再構成制御メッセージの処理（後述のシーケンスにおける制御メッセージ処理）は以下のように扱われる。
【０１７８】
フレームを受信したフレーム分別器１１７は、受信フレームを解析し、BPDUである場合、ＳＴＰコントローラ１１５と再構成コントローラ１１６に転送し、再構成制御メッセージである場合、再構成コントローラ１１６に転送する。
【０１７９】
再構成コントローラ１１６では、タグ削除器１１６１においてタグを削除した制御フレームを、制御フレーム送受信部１１６２が再構成処理部１１６４に転送する。再構成処理部１１６４において、各制御フレームに応じた処理を行った後、次ノードに転送する必要がある場合は、再構成処理部１１６４から制御フレーム送受信部１１６２、さらにタグ挿入器１１６３を経て、タグが付加された制御フレームがフレーム転送器１１１によって、適切なポートに転送され、次ノードに転送される。
【０１８０】
ここで、スパニングツリーの再構成処理において使用される再構成制御メッセージについて説明する。再構成制御メッセージは、以下の５種類のメッセージからなる。
（１）トポロジー変更申請メッセージ
このトポロジー変更申請メッセージとしては、１）トポロジー変更申請メッセージ１（予備用ツリーのトポロジー変更の申請）と、２）トポロジー変更申請メッセージ２（新予備用ツリーのトポロジー変更の申請）がある。
【０１８１】
（２）トポロジー変更申請応答メッセージ
このトポロジー変更申請応答メッセージには、申請メッセージの応答として、１）変更可能の応答、２）変更不可の応答、３）再構成不可の応答が含まれる。
【０１８２】
（３）トポロジー変更応答確認メッセージ
トポロジー変更申請応答メッセージが変更可能の応答である場合に、変更可能を受信したことの確認通知をするメッセージである。
【０１８３】
（４）切替メッセージ
この切替メッセージには、１）切替メッセージ１（予備用＝偶数タグ、現用＝奇数タグへの切替トリガ）、２）切替メッセージ２（現用＝偶数タグ、予備用＝奇数タグへの切替トリガ）が含まれる。
【０１８４】
（５）ＳＴＰインスタンス起動／停止要求メッセージ
指定したIDのスパニングツリーの起動／停止を各エッジノードに要求するためのメッセージである。
【０１８５】
（ノード追加によるツリー再構成）
図１５に示すような、ノード３００１がルートノードとなっている現用ツリー＃４００１に、追加ノード３０１２が追加される場合の再構成処理について、図１９のシーケンス図に従って説明する。
【０１８６】
ここでは、図１６に示す処理によって、現用ツリー＃４００１と予備用ツリー＃４０９５の双方において、ノード３００１がルートノードとなっている。
【０１８７】
図２０は、安定タイマ１１６７のタイマモードの内容を示している。ここでは、タイマモード１〜タイマモード４があり、ぞれぞれのタイマモードを使用するノードの種別と、タイマモードが設定されるタイミングを示す起動トリガ及びその使用目的を示している。
【０１８８】
（ステップＢ−１：追加ノード３０１２）
追加ノード３０１２において、再構成コントローラ１１６の再構成処理部１１６４が、設定インタフェース１１８または拡張再構成処理部１１６５からノード追加用の再構成制御起動トリガを受け取る。再構成制御起動トリガでは、起動したいツリーのIDを［タグ］で指定している。
【０１８９】
（１）再構成制御起動トリガで指定された［タグ］に自ノードＩＤが指定されている場合、再構成処理部１１６４はＳＴＰコントローラ１１５に対して、指定された［タグ］のＳＴＰインスタンスを起動する命令を通知する。
【０１９０】
また、他ノードに対して、指定された［タグ］のＳＴＰ追加の要求を示すＳＴＰインスタンス起動／停止要求メッセージをブロードキャスト送信する。
【０１９１】
（２）再構成制御起動トリガで指定された［タグ］が自ノードＩＤと一致しない場合、再構成処理部１１６４は以降に説明する再構成処理を開始する。
【０１９２】
（ステップＢ−２：ネットワーク内の各ノード）
ネットワーク内の各ノードの再構成処理部１１６４では、ＳＴＰインスタンス起動／停止要求メッセージを受信すると、ＳＴＰコントローラ１１５に対して、通知された［タグ］のＳＴＰインスタンスを作成する命令を通知する。
【０１９３】
（ステップＢ−３：追加ノード３０１２）
追加ノード３０１２の再構成処理部１１６４では、フレーム分別器１１７から転送されるBPDUの受信処理のみを行い、受信したBPDUに格納された情報の中から、ＶＬＡＮタグ値からスパニングツリーのＩＤを、またＢｒｉｄｇｅ＿ＩＤからそのツリーのルートノードのＭＡＣアドレスを取得し、各々の情報を図１３に示す再構成管理テーブル１１６６に保持する。
【０１９４】
（ステップＢ−４：追加ノード３０１２）
追加ノード３０１２の再構成処理部１１６４では、ステップＢ−３において、再構成管理テーブル１１６６からルートノード３００１のＭＡＣアドレスを取得し、ルートノード３００１に対して、トポロジー変更申請メッセージ１をユニキャスト転送する。
【０１９５】
ルートノード３００１のＭＡＣアドレスが再構成管理テーブル１１６６に存在しない場合、ステップＢ−３において取得できるまで待ち合わせる。
【０１９６】
なお、信頼性向上のために、転送先でのトポロジー変更申請メッセージ１の廃棄に備えて、応答メッセージ１を受信するまで、トポロジー変更申請メッセージ１を所定時間（ここではＸ秒とする）毎に複数回（ここでは、最大送信回数をＹ回とする）送信する。
【０１９７】
（ステップＢ−５：ルートノード３００１）
ルートノード３００１の再構成処理部１１６４では、トポロジー変更申請メッセージ１を受信すると再構成処理の可否を判定し、追加対象のノード３０１２宛てに、その判定結果を含むトポロジー変更申請応答メッセージ１を送信する。
【０１９８】
ここで、（１）トポロジー変更申請メッセージ１で指定された［タグ］のツリーが自ノードがルートとなっているツリーではない場合、「再構成使用不可」である旨のトポロジー変更申請応答メッセージ１をトポロジー変更申請メッセージ１の送信元であるノード３０１２に対して送信する。
【０１９９】
（２）トポロジー変更申請メッセージ１で指定された［タグ］のツリーが自ノードがルートとなっているツリーであり、かつ他ノードからの申請によって再構成処理中でない場合、「変更可能」である旨のトポロジー変更申請応答メッセージ１をトポロジー変更申請メッセージ１の送信元であるノード３０１２に対して送信する。
【０２００】
安定タイマ１１６７のタイマモード１を起動する。
【０２０１】
同時にルートノードで管理する再構成処理受付フラグを「ON」とする。
【０２０２】
なお、再構成処理受付フラグは、１つのノードからの再構成処理の申請のみに対して再構成処理を行うためのフラグであり、この再構成処理受付フラグがＯＮである間は、当該ツリーのルートノード３００１は、他ノードからの再構成処理は受け付けないことを意味している。この例では、ノード３０１２からのノード追加処理のみを行い、その処理が終了するまでの間は、ノード３０１２以外のノードからの追加処理、削除処理は受け付けないことになる。
【０２０３】
（３）トポロジー変更申請メッセージ１で指定された［タグ］のツリーが自ノードがルートとなっているツリーであり、他ノードからの再構成処理中の場合、「変更不可」である旨のトポロジー変更申請応答メッセージ１を送信する。
【０２０４】
（ステップＢ−６：追加ノード３０１２）
追加対象のノード３０１２の再構成処理部１１６４では、ルートノード３００１からのトポロジー変更申請応答メッセージ１の受信処理を行う。
【０２０５】
（１）自身が送信したトポロジー変更申請メッセージ１に対するトポロジー変更申請応答メッセージ１（ＭＡＣ＿ＤＡ＝自ＭＡＣアドレスであることにより判断）が、トポロジー変更申請メッセージ１の送信後所定時間（Ｘ秒）以内に到着した場合、そのトポロジー変更申請応答メッセージ１の内容に応じて以下の処理を行う。
【０２０６】
（ａ）「変更可能」の場合
ルートノード３００１に対し、応答確認メッセージを送信する。
【０２０７】
安定タイマ１１６７に対し、タイマモード１を起動する。
【０２０８】
予備用ツリーの再構築（ステップＢ−７以降の処理）を開始する。
【０２０９】
（ｂ）「変更不可」の場合
安定タイマ１１６７に対し、タイマモード４を起動する。
【０２１０】
安定タイマ１１６７からタイマモード４の完了通知を受けると、トポロジー変更申請メッセージ１を再送する（ステップＢ−４に戻る）。
【０２１１】
（ｃ）「再構成不可」の場合、
再構成処理を異常終了とし、再構成処理部１１６４は拡張再構成処理部１１６５にその旨を通知する。
【０２１２】
（２）送信後、トポロジー変更申請応答メッセージ１がＸ秒以内に到着しなかった場合、トポロジー変更申請メッセージ１の送信回数に応じて以下の処理を行う。
【０２１３】
（ａ）送信回数がＹ回以下の場合
トポロジー変更申請メッセージ１の送信からＸ秒後に申請メッセージ１を再送する（ステップＢ−４に戻る）。
【０２１４】
（ｂ）送信回数がＹ回を超えた場合
安定タイマ１１６７に対し、タイマモード４を起動する。
【０２１５】
安定タイマ１１６７からタイマモード４の完了通知を受けると、トポロジー変更申請メッセージ１を再送する（ステップＢ−４に戻る）。この場合の再構成処理を異常終了とするまでの再送回数の上限回数を所定値に設定する（ここでは、Ｂ回）。
【０２１６】
そして、トポロジー変更申請メッセージ１の再送によっても、応答メッセージ１がＸ秒以内に到着せず、再送の送信回数がＢ回を超えた場合には、再構成処理を異常終了とし、拡張再構成処理部１１６５にその旨を通知する。
【０２１７】
（ステップＢ−７：追加ノード３０１２）
ステップＢ−６において、トポロジー変更申請応答メッセージ１の内容が「変更可能」の場合、追加ノード３０１２の再構成処理部１１６４では、ＳＴＰコントローラ１１５に対し、予備用ツリー（ツリーＩＤ＝＃４０９５）のＳＴＰインスタンスを作成する命令を通知する。
【０２１８】
これにより、［タグ］＝「４０９５」のＳＴＰインスタンスがＳＴＰコントローラ１１５内で作成されることにより、［タグ］＝「４０９５」のBPDUの送信が開始される。その結果、ネットワーク内ではノード３０１２を含んだスパニングツリーが再構成される。
【０２１９】
（ステップＢ−８：ルートノード３００１）
ルートノード３００１では、安定タイマ１１６７からタイマモード１の完了通知を受信すると、再構成処理部１１６４が予備用ツリー＃４０９５の安定を検出する。
【０２２０】
ここで、タイマモード１の完了までに、追加ノード３０１２から応答確認メッセージを受信している場合、再構成処理部１１６４は、予備用ツリー＃４０９５を予備用から現用に、ツリー＃４００１を現用から予備用に変更するために、ネットワーク内の各ノードに対し、切替メッセージ１をブロードキャストで送信する。
【０２２１】
タイマモード１の完了までに、追加ノード３０１２から応答確認メッセージを受信してない場合、再構成処理部１１６４は、安定タイマ１１６７に対し、タイマモード１をリセットし、再構成処理を終了し、拡張再構成処理部１１６５にその旨を通知する。
【０２２２】
（ステップＢ−９：追加ノード３０１２及びネットワーク内の各ノード）
追加ノード３０１２を含むネットワーク内の各ノードでは、再構成処理部１１６４が切替メッセージ１の受信処理を行う。
【０２２３】
再構成処理部１１６４は、切替メッセージ１を受信することにより、タグ「４０９５」＝現用、タグ「４００１」＝予備用にして、再構成管理テーブル１１６６を書き換える。
【０２２４】
また、フォワーディングテーブル１１４のタグ「４００１」に対する出力ポートついて、タグ「４０９５」のエントリを参照するように書き換える。すなわち、フォワーディングテーブル１１４のタグ「４００１」のエントリに関して、フラグフィールド１１４２の値を０とする。この結果、タグ「４００１」は予備用となるため、タグ「４０９５」のエントリを参照して出力ポートを決定する。これ以降、データフレームはツリー＃４０９５の転送経路上を転送される。
【０２２５】
さらに、追加ノード３０１２では、再構成処理部１１６４が、安定タイマ１１６７に対し、タイマモード２を起動する。
【０２２６】
安定タイマ１１６７からタイマモード２の完了通知を受けると、ルートノード３００１に対して申請メッセージ２を送信する（タイマモード２の時間分待機することにより、旧現用ツリー（＃４００１）上に流れるフレームが存在しなくなるのを保証する）。
【０２２７】
（ステップＢ−１０：追加ノード３０１２）
申請メッセージ２の送信後、追加ノード３０１２の再構成処理部１１６４は、ＳＴＰコントローラ１１５に対し、予備用ツリー（＃４００１）のＳＴＰインスタンスを作成する命令を通知する。
【０２２８】
［タグ］＝「４００１」のＳＴＰインスタンスがＳＴＰコントローラ１１５内で作成されることにより、追加ノード３０１２において［タグ］＝「４００１」を制御情報として含むBPDUの送信が開始される。
【０２２９】
（ステップＢ−１１：ルートノード３００１）
ルートノード３００１の再構成処理部１１６４は、申請メッセージ２を受信すると、安定タイマ１１６７に対し、タイマモード１を起動する。
【０２３０】
（ステップＢ−１２：ルートノード３００１）
さらに、ルートノード３００１の再構成処理部１１６４は、安定タイマ１１６７からタイマモード１の完了通知を受信すると、ツリー＃４００１の安定を検出し、ツリー＃４００１を予備用から現用に、ツリー＃４０９５を現用から予備用に変更するために、ネットワーク内の各ノードに対して、切替メッセージ２をブロードキャスト送信する。また、安定タイマ１１６７に対し、タイマモード３を起動する（タイマ３モードの待機により、ツリー＃４０９５にデータフレームの残りが存在しなくなることを保証する。）
【０２３１】
（ステップＢ−１３：追加ノード３０１２及びネットワーク内の各ノード）
追加ノード３０１２を含むネットワーク内の各ノードの再構成処理部１１６４は、切替メッセージ２の受信処理を行う。
【０２３２】
再構成処理部１１６４は、タグ「４００１」＝現用、タグ「４０９５」＝予備用にして、再構成管理テーブル１１６６を書き換える。
【０２３３】
また、フォワーディングテーブル１１４のタグ「４００１」に対する出力ポートに関し、タグ「４００１」のエントリを参照するように内容を書き換える。すなわち、フォワーディングテーブル１１４のタグ「４００１」のエントリに関して、フラグフィールド１１４２の値を１とする。この結果、タグ「４００１」は現用となるため、タグ「４００１」のエントリを参照して出力ポートを決定する。これ以降、データフレームはツリー＃４００１の転送経路上を転送される。
【０２３４】
追加ノード３０１２では、再構成処理部１１６４が拡張再構成処理部１１６５に対し、再構成処理の正常終了を通知する。
【０２３５】
（ステップＢ−１４：ルートノード３００１）
ルートノード３００１の再構成処理部１１６４は、安定タイマ１１６７からタイマモード３の完了通知を受信すると、再構成処理受付フラグ＝「ＯＦＦ」にする。以降、他ノード（ＶＬＡＮペア）の追加／削除が可能となる。
【０２３６】
（ノード削除によるツリー再構成）
図１８に示すような、ノード３００１がルートノードとなるツリー＃４００１からノード３０１２が削除される場合の再構成処理を図２１のシーケンス図を参照して説明する。
【０２３７】
ここで、ツリー＃４００１が現用ツリー、ツリー＃４０９５が予備用ツリーである。また、ノード３００１が両方のツリーのルートノードとなっている。
【０２３８】
（ステップＣ−１：削除ノード３０１２）
削除ノード３０１２の再構成処理部１１６４が、設定インタフェース１１８または拡張再構成処理部１１６５からノード削除用の再構成制御起動トリガを受信する。再構成制御起動トリガには、ノード追加用と同様に削除処理を起動したいツリーのＩＤを[タグ]で指定している。
【０２３９】
（１）再構成制御起動トリガで指定された［タグ］が自ノードＩＤの場合、再構成処理部１１６４はＳＴＰコントローラ１１５に対して、指定された［タグ］のＳＴＰインスタンスを停止する命令を通知する。
【０２４０】
また、他ノードに対して、指定された［タグ］のＳＴＰインスタンスを停止の要求を示すＳＴＰインスタンス起動／停止要求メッセージをブロードキャスト送信する。
（２）起動トリガで指定された［タグ］が自ノードＩＤと一致しない場合、再構成処理部１１６４は以降の再構成処理を開始する。
【０２４１】
（ステップＣ−２：ネットワーク内の各ノード）
ネットワーク内の各ノードの再構成処理部１１６４では、ＳＴＰインスタンス起動／停止要求メッセージを受信したら、ＳＴＰコントローラ１１５に対して、通知された［タグ］のＳＴＰインスタンスを停止する命令を通知する。
【０２４２】
（ステップＣ−３：削除ノード３０１２）
削除ノード３０１２の再構成処理部１１６４では、再構成制御起動トリガを受信後、再構成管理テーブル１１６６からルートノード３００１のＭＡＣアドレスを取得し、ルートノード３００１に対して、トポロジー変更申請メッセージ１をユニキャスト転送する。
【０２４３】
ただし、ルートノード３００１のＭＡＣアドレスが再構成管理テーブル１１６６にない場合、対象タグのペアのタグ３００１のBPDUを受信して、ルートノードのＭＡＣアドレスを取得できるまで待ち合わせる。
【０２４４】
なお、ノード追加の再構成処理の場合と同様に、信頼性向上のために、転送先でのトポロジー変更申請メッセージ１の廃棄に備えて、応答メッセージ１を受信するまで、トポロジー変更申請メッセージ１を所定時間（ここではＸ秒とする）毎に複数回（ここでは、最大送信回数をＹ回とする）送信する。  
【０２４５】
（ステップＣ−４：ルートノード３００１）
ルートノード３００１の再構成処理部１１６４では、トポロジー変更申請メッセージ１を受信すると再構成処理の可否を判定し、削除対象のノード３０１２宛てに、その判定結果を含むトポロジー変更申請応答メッセージ１を送信する。
【０２４６】
（１）トポロジー変更申請メッセージ１で指定された［タグ］のツリーが自ノードがルートとなっているツリーではない場合、「再構成使用不可」である旨のトポロジー変更申請応答メッセージ１を送信する。
【０２４７】
（２）トポロジー変更申請メッセージ１で指定された［タグ］のツリーが自ノードがルートとなっているツリーであり、かつ他ノードからの申請によって再構成処理中でない場合、「変更可能」である旨のトポロジー変更申請応答メッセージ１を送信する。
【０２４８】
安定タイマ１１６７のタイマモード１を起動する。
【０２４９】
再構成処理受付フラグを「ＯＮ」とする。
【０２５０】
（３）トポロジー変更申請メッセージ１で指定された［タグ］のツリーが自ノードがルートとなっているツリーであり、他ノードからの再構成処理中の場合、「変更不可」である旨のトポロジー変更申請応答メッセージ１を送信する。
【０２５１】
（ステップＣ−５：削除ノード３０１２）
削除対象のノード３０１２の再構成処理部１１６４では、ルートノード３００１からのトポロジー変更申請応答メッセージ１の受信処理を行う。
【０２５２】
（１）自身が送信したトポロジー変更申請メッセージ１に対するトポロジー変更申請応答メッセージ１（ＭＡＣ＿ＤＡ＝自ＭＡＣアドレスであることにより判断）が、トポロジー変更申請メッセージ１の送信後所定時間（Ｘ秒）以内に到着した場合、そのトポロジー変更申請応答メッセージ１の内容に応じて以下の処理を行う。
【０２５３】
（ａ）「変更可能」の場合
ルートノード３００１に対し、応答確認メッセージを送信する。
【０２５４】
安定タイマ１１６７に対し、タイマモード１を起動する。
【０２５５】
予備用ツリーの再構築（ステップＣ−６以降の処理）を開始する。
【０２５６】
（ｂ）「変更不可」の場合
安定タイマ１１６７に対し、タイマモード４を起動する。
【０２５７】
安定タイマ１１６７からタイマモード４の完了通知を受けると、トポロジー変更申請メッセージ１を再送する（ステップＣ−３に戻る）。
【０２５８】
（ｃ）「再構成不可」の場合
再構成処理を異常終了とし、再構成処理部１１６４は拡張再構成処理部１１６５にその旨を通知する。
【０２５９】
（２）送信後、トポロジー変更申請応答メッセージ１がＸ秒以内に到着しなかった場合、トポロジー変更申請メッセージ１の送信回数に応じて以下の処理を行う。
【０２６０】
（ａ）送信回数がＹ回以下の場合
トポロジー変更申請メッセージ１の送信からＸ秒後に申請メッセージ１を再送する（ステップＣ−３に戻る）。
【０２６１】
（ｂ）送信回数がＹ回を超えた場合
安定タイマ１１６７に対し、タイマモード４を起動する。
【０２６２】
安定タイマ１１６７からタイマモード４の完了通知を受けると、トポロジー変更申請メッセージ１を再送する（ステップＣ−３に戻る）。この場合の再構成処理を異常終了とするまでの再送回数の上限回数を所定値に設定する（ここでは、Ｂ回）。
【０２６３】
そして、トポロジー変更申請メッセージ１の再送によっても、応答メッセージ１がＸ秒以内に到着せず、再送の送信回数がＢ回を超えた場合には、再構成処理を異常終了とし、拡張再構成処理部１１６５にその旨を通知する。
【０２６４】
（ステップＣ−６：削除ノード３０１２）
ステップＣ−５において、トポロジー変更申請応答メッセージ１の内容が「変更可能」の場合、削除ノード３０１２の再構成処理部１１６４では、ＳＴＰコントローラ１１５に対し、予備用ツリー（ツリーＩＤ＝＃４０９５）のＳＴＰインスタンスを停止する命令を通知する。
【０２６５】
これにより、［タグ］＝「４０９５」のＳＴＰインスタンスがＳＴＰコントローラ１１５内から削除されることにより、［タグ］＝「４０９５」のBPDUの送信が停止される。その結果、ネットワーク内ではノード３０１２を除いたスパニングツリーが再構成される。
【０２６６】
（ステップＣ−７：ルートノード３００１）
ルートノード３００１では、安定タイマ１１６７からタイマモード１の完了通知を受信すると、再構成処理部１１６４がツリー＃４０９５の安定を検出する。
【０２６７】
ここで、タイマモード１の完了までに、削除対象のノード３０１２から応答確認メッセージを受信している場合、再構成処理部１１６４は、ツリー＃４０９５を予備用から現用に、ツリー＃４００１を現用から予備用に変更するために、ネットワーク内の各ノードに対し、切替メッセージ１をブロードキャストで送信する。
【０２６８】
タイマモード１の完了までに、追加ノード３０１２から応答確認メッセージを受信してない場合、再構成処理部１１６４は、安定タイマ１１６７に対し、タイマモード１をリセットし、再構成処理を終了し、拡張再構成処理部１１６５にその旨を通知する。
【０２６９】
（ステップＣ−８：削除ノード３０１２及びネットワーク内の各ノード）
削除対象のノード３０１２を含むネットワーク内の各ノードでは、再構成処理部１１６４が切替メッセージ１の受信処理を行う。
【０２７０】
再構成処理部１１６４は、切替メッセージ１を受信することにより、タグ「４０９５」＝現用、タグ「４００１」＝予備用にして、再構成管理テーブル１１６６を書き換える。
【０２７１】
また、フォワーディングテーブル１１４のタグ「４００１」に対する出力ポートに関し、タグ「４０９５」のエントリを参照するようにその内容を書き換える。すなわち、フォワーディングテーブル１１４のタグ「４００１」のエントリに関して、フラグフィールド１１４２の値を０とする。この結果、タグ「４００１」は予備用であるため、タグ「４０９５」のエントリを参照して出力ポートを決定する。これ以降、データフレームはツリー＃４０９５の転送経路上を転送される。
【０２７２】
さらに、削除対象のノード３０１２では、再構成処理部１１６４が、安定タイマ１１６７に対し、タイマモード２を起動する。
【０２７３】
安定タイマ１１６７からタイマモード２の完了通知を受けると、ルートノード３００１に対して申請メッセージ２を送信する（タイマモード２の時間分待機することにより、旧現用ツリー（＃４００１）上に流れるフレームが存在しなくなるのを保証する）。
【０２７４】
（ステップＣ−９：削除ノード３０１２）
申請メッセージ２の送信後、削除対象ノード３０１２の再構成処理部１１６４は、ＳＴＰコントローラ１１５に対し、予備用ツリー（＃４００１）のＳＴＰインスタンスを停止する命令を通知する。
【０２７５】
［タグ］＝「４００１」のＳＴＰインスタンスがＳＴＰコントローラ１１５内から削除されることにより、削除ノード３０１２では、［タグ］＝「４００１」のBPDUの送信が停止される。
【０２７６】
（ステップＣ−１０：ルートノード３００１）
ルートノード３００１の再構成処理部１１６４は、申請メッセージ２を受信すると、安定タイマ１１６７に対し、タイマモード１を起動する。
【０２７７】
（ステップＣ−１１：ルートノード３００１）
さらに、ルートノード３００１の再構成処理部１１６４は、安定タイマ１１６７からタイマモード１の完了通知を受信すると、ツリー＃４００１の安定を検出し、ツリー＃４００１を予備用から現用に、ツリー＃４０９５を現用から予備用に変更するために、ネットワーク内の各ノードに対して、切替メッセージ２をブロードキャスト送信する。また、安定タイマ１１６７に対し、タイマモード３を起動する（タイマ３モードの待機により、ツリー＃４０９５にデータフレームの残りが存在しなくなることを保証する。）
【０２７８】
（ステップＣ−１２：追加ノード３０１２及びネットワーク内の各ノード）
削除対象ノード３０１２を含むネットワーク内の各ノードの再構成処理部１１６４は、切替メッセージ２の受信処理を行う。
【０２７９】
再構成処理部１１６４は、タグ「４００１」＝現用、タグ「４０９５」＝予備用にして、再構成管理テーブル１１６６を書き換える。
【０２８０】
また、フォワーディングテーブル１１４のタグ「４００１」に対する出力ポートに関し、タグ「４００１」のエントリを参照するように内容を書き換える。すなわち、フォワーディングテーブル１１４のタグ「４００１」のエントリに関して、フラグフィールド１１４２の値を１とする。この結果、タグ「４００１」は現用であるため、タグ「４００１」のエントリを参照して出力ポートを決定する。これ以降、データフレームはツリー＃４００１の転送経路上を転送される。
【０２８１】
削除対象ノード３０１２では、再構成処理部１１６４が拡張再構成処理部１１６５に対し、再構成処理の正常終了を通知する。
【０２８２】
（ステップＣ−１３：ルートノード３００１）
ルートノード３００１の再構成処理部１１６４は、安定タイマ１１６７からタイマモード３の完了通知を受信すると、再構成処理受付フラグ＝「ＯＦＦ」にする。以降、他ノード（ＶＬＡＮペア）の追加／削除が可能となる。
【０２８３】
以上のようにツリーの再構成処理を行うことにより、ネットワークを停止させることなくスパニングツリーの再構成が実施される。
【０２８４】
従来の予備用ツリーを使用しないネットワークシステムでは、装置のメンテナンスやリプレイス、ネットワークの増強などのために、新たにノードを追加し又はノードを削除する際に、ツリーの再構成に伴うパケットロスが発生し、サービス中のトラヒックに影響を及ぼす可能性があった。そのため、ユーザに対してこのようなネットワーク再構成作業を行うための許可を取る作業が必要であったり、または、ユーザに対する影響を最小化するためにサービス中のトラヒックが少ない深夜や休日に作業を行う必要があった。これにより、ネットワーク運用コストが増大するという問題があった。本実施の形態によれば、ネットワークを停止させる必要がないので、時間にとらわれずにネットワーク再構成作業を実施可能であり、ネットワーク運用コストを大幅に軽減することができるようになる。
【０２８５】
第１の実施の形態の効果について述べる。第１の実施の形態によれば、上述のように、ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成を可能にすると共に、ネットワークで使用できるスパニングツリーの数が２分の１に制限されていた従来の問題を回避し、使用できるスパニングツリーの数をスパニングツリーの最大数−１まで拡張可能であるという効果が実現される。また、スパニングツリーを制御するための制御フレームの数を少なくすることができるので、各ノードにおける制御フレームの処理に要する処理の負荷を低減させることのできる。
【０２８６】
（第２の実施の形態）
次いで、本発明の第２の実施の形態によるネットワークシステムについて説明する。
【０２８７】
この第２の実施の形態では、予備用ツリーの使用状態の管理をサーバが行い、ノードの追加、削除におけるツリー管理をネットワークに対して追加又は削除されるノードによって行う構成となっている。
【０２８８】
第２の実施の形態によるネットワーク構成は、図１２に示す構成と同じであるが、管理用サーバ５０００が再構成管理テーブル１１６６を備えていない点が第１の実施の形態と相違する。
【０２８９】
ネットワークに追加され又はネットワークから削除されるノード３０１２は、ツリーの再構成を開始する前に、ネットワーク上を流れるBPDUの受信処理を行い、受信したBPDUに格納された情報の中から、ＶＬＡＮタグ値からスパニングツリーのＩＤを、またＢｒｉｄｇｅ＿ＩＤからそのツリーのルートノードのＭＡＣアドレスを取得することにより、図１３に示す再構成管理テーブル１１６６を作成する。
【０２９０】
以下、図２２を参照して、ノードが追加される場合の動作について説明する。
【０２９１】
ここでは、図１４に示すように、現用ツリー＃４００１〜＃４００６の６つのツリーが存在し、その６つの現用ツリーが共用する１つの予備用ツリー＃４０９５が用意されたネットワークシステムについて説明する。
【０２９２】
ノードが追加される前の各現用ツリー＃４００１〜＃４００６、予備用ツリー＃４０９５は、それぞれノード３００１〜３００６で構成されており、各スパニングツリーの状態を太線で示している。
【０２９３】
図１４に示すネットワーク状態においては、現用ツリー＃４００１ではノード３００１が、現用ツリー＃４００２ではノード３００２が、現用ツリー＃４００３ではノード３００３が、現用ツリー＃４００４ではノード３００４が、現用ツリー＃４００５ではノード３００５、現用ツリー＃４００６ではノード３００６がそれぞれルートノードとなっており、予備用ツリー＃４０９５ではノード３００１がルートノードとなっている。
【０２９４】
ここで、上記のような構成のネットワークに、図１５に示すように、新たなノード＃３０１２が追加される場合の処理について、図２２のシーケンス図を参照して説明する。
【０２９５】
まず、図１５に示すように、現用ツリー＃４００１に対する新たなノード３０１２の追加が実行される。
【０２９６】
（ステップＤ−１）
新たに追加するノード３０１２から、現用ツリー＃４００１のルートノード３００１に対して追加要求メッセージを送信することにより、ツリーへの追加要求を行う。
【０２９７】
（ステップＤ−２）
ノード３０１２からの追加要求メッセージを受けると、現用ツリー＃４００１のルートノード３００１は、管理用サーバ５０００に対して、予備用ツリー＃４０９５の使用状態（使用が競合するかどうか、競合する場合どのノードが使用しているか等）についての問い合わせを行う。
【０２９８】
（ステップＤ−３）
管理用サーバ５０００は、予備用ツリー＃４０９５が再構成処理のために使用されているか、使用されている場合にはどの現用ツリーが使用しているかを、予備用ツリー使用状態管理フラグを用いて管理しており、予備用ツリー使用状態管理フラグ＝ＯＦＦである場合、フラグ＝ＯＮとして、ノード３０１２の追加処理に伴う再構成処理のために予備用ツリー＃４０９５を確保する。その後、ルートノード３００１に対して現用ツリー＃４００１への追加を許可するとともに、ルートノード３００１に対して予備用ツリー＃４０９５のルートノードとなることを要求するメッセージを通知する。
【０２９９】
（ステップＤ−４）
管理用サーバ５０００からの上記要求を受けた、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値よりも小さい値に設定変更する。これにより、ルートノード３００１はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが他のノードよりも小さくなるため予備用ツリー＃４０９５のルートノードとなる。その結果、予備用ツリー＃４０９５のスパニングツリーの状態は、図１７に示すように、現用ツリー＃４００１と同じ状態となる。
【０３００】
（ステップＤ−５）
これにより、現用ツリー＃４００１において、予備用ツリー＃４０９５を利用して新たなノード３０１２を追加するための再構成処理（再構成処理）が実行される。このツリーの再構成処理については、第１の実施の形態で説明した図１９、図２１の処理と同様の処理がなされる。
【０３０１】
（ステップＤ−６）
現用ツリー＃４００１の再構成処理の終了後、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値に設定変更する。これにより、ルートノード３００１はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが通常の値に戻るためツリー＃４０９５のルートノードは網内のノードの中でＭＡＣアドレスが最も小さいノードが選択される状態に戻る。
【０３０２】
（ステップＤ−７）
さらに、現用ツリー＃４００１のルートノード３００１は、管理用サーバ５０００に対して、現用ツリー＃４００１へのノード３０１２の追加による再構成処理が完了した旨のメッセージを通知する。
【０３０３】
（ステップＤ−８）
管理用サーバ５０００では、上記再構成処理完了の通知を受けると、予備用ツリー使用状態管理フラグをフラグ＝ＯＦＦとして、予備用ツリー＃４０９５を他のノードの追加削除処理に使用可能とする。
【０３０４】
追加ノード３０１２はツリーの再構成処理が終了すると、再構成管理テーブル１１６６に関して、再構成処理終了したツリーの再構成処理フラグ５０１３を「済み（ＯＮ）」に設定すると共に、再構成処理フラグ５０１３がＯＦＦであるツリーを選択して、その後、次のツリーである、図１４に示す現用ツリー＃４００２に対する新たなノード３０１２の追加が実行される。なお、未処理状態ツリーが複数存在する場合の決定方法については、特に制限はない。
【０３０５】
（ステップＤ−９）
新たに追加するノード３０１２から、現用ツリー＃４００２のルートノード３００２に対して追加要求メッセージを送信することにより、ツリーへの追加要求を行う。
【０３０６】
（ステップＤ−１０）
ノード３０１２からの追加要求メッセージを受けると、現用ツリー＃４００２のルートノード３００２は、管理用サーバ５０００に対して、予備用ツリー＃４０９５の使用状態（使用が競合するかどうか、競合する場合どのノードが使用しているか等）についての問い合わせを行う。
【０３０７】
（ステップＤ−１１）
管理用サーバ５０００は、予備用ツリー使用状態管理フラグ＝ＯＦＦである場合、フラグ＝ＯＮとして、ノード３０１２の追加処理に伴う再構成処理のために予備用ツリー＃４０９５を確保する。その後、ルートノード３００２に対して現用ツリー＃４００２への追加を許可するとともに、ルートノード３００２に対して予備用ツリー＃４０９５のルートノードとなることを要求するメッセージを通知する。
【０３０８】
（ステップＤ−１２）
管理用サーバ５０００からの上記要求を受けた、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値よりも小さい値に設定変更する。これにより、ルートノード３００２はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが他のノードよりも小さくなるため予備用ツリー＃４０９５のルートノードとなる。その結果、予備用ツリー＃４０９５のスパニングツリーの状態は、現用ツリー＃４００２と同じ状態となる。
【０３０９】
（ステップＤ−１３）
これにより、現用ツリー＃４００２において、予備用ツリー＃４０９５を利用して新たなノード３０１２を追加するための再構成処理（再構成処理）が実行される。このツリーの再構成処理については、第１の実施の形態で説明した処理と同様の処理がなされる。
【０３１０】
（ステップＤ−１４）
現用ツリー＃４００２の再構成処理の終了後、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値に設定変更する。これにより、ルートノード３００２はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが通常の値に戻るためツリー＃４０９５のルートノードは網内のノードの中でＭＡＣアドレスが最も小さいノードが選択される状態に戻る。
【０３１１】
（ステップＤ−１５）
さらに、現用ツリー＃４００２のルートノード３００２は、管理用サーバ５０００に対して、現用ツリー＃４００２へのノード３０１２の追加による再構成処理が完了した旨のメッセージを通知する。
【０３１２】
（ステップＤ−１６）
管理用サーバ５０００では、上記再構成処理完了の通知を受けると、予備用ツリー使用状態管理フラグをフラグ＝ＯＦＦとして、予備用ツリー＃４０９５を他のノードの追加削除処理に使用可能とする。
【０３１３】
追加ノード３０１２は、再構成管理テーブル１１６６に関して、再構成処理終了したツリーの再構成処理フラグ５０１３を「済み（ＯＮ）」に設定すると共に、再構成処理フラグ５０１３がＯＦＦであるツリーを選択して、その後、次のツリーに対する新たなノード３０１２の追加が実行される。
【０３１４】
以下、上記と同じ処理を繰り返すことによって、残りの現用ツリー＃４００３から＃４００６についてもノード３０１２の追加処理が実行される。
【０３１５】
上記のようにしてノード３０１２が追加された現用ツリー＃４００１〜＃４００６の状態を図１８に示す。
【０３１６】
なお、図２２においては、ネットワークシステムに対してノード＃３０１２が追加される場合の処理について説明したが、ネットワークを構成するノードが削除される場合の処理についても、図２２と同様の処理がなされる。すなわち、図２２において、「追加（又は追加処理）」とあるのを「削除（又は削除処理）」とすることで、ノードが削除される場合の処理が説明される。
【０３１７】
第２の実施の形態の効果について述べる。第２の実施の形態によれば、第１の実施の形態と同様に、ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成を可能にすると共に、ネットワークで使用できるスパニングツリーの数が２分の１に制限されていた従来の問題を回避し、使用できるスパニングツリーの数をスパニングツリーの最大数−１まで拡張可能であるという効果が実現される。また、スパニングツリーを制御するための制御フレームの数を少なくすることができるので、各ノードにおける制御フレームの処理に要する処理の負荷を低減させることのできる。
【０３１８】
（第３の実施の形態）
次いで、本発明の第３の実施の形態によるネットワークシステムについて説明する。
【０３１９】
この第３の実施の形態では、予備用ツリーの使用状態の管理と、ノードの追加、削除におけるツリー管理の何れも、ネットワークに対して追加され又はネットワークから削除されるノードによって行う構成となっている。すなわち、追加又は削除されるノードが、第１の実施の形態で示した管理用サーバ５０００の機能を併せ持つ構成としている。
【０３２０】
従って、ネットワーク構成については、図１２の構成から管理用サーバを省略した構成となっている。
【０３２１】
ネットワークに追加され又はネットワークから削除されるノード３０１２は、ツリーの再構成を開始する前に、ネットワーク上を流れるBPDUの受信処理を行い、受信したBPDUに格納された情報の中から、ＶＬＡＮタグ値からスパニングツリーのＩＤを、またＢｒｉｄｇｅ＿ＩＤからそのツリーのルートノードのＭＡＣアドレスを取得することにより、図１３に示す再構成管理テーブル１１６６を作成する。
【０３２２】
以下、図２３を参照して、ノードが追加される場合の動作について説明する。
【０３２３】
ここでは、図１４に示すように、現用ツリー＃４００１〜＃４００６の６つのツリーが存在し、その６つの現用ツリーが共用する１つの予備用ツリー＃４０９５が用意されたネットワークシステムについて説明する。
【０３２４】
ノードが追加される前の各現用ツリー＃４００１〜＃４００６、予備用ツリー＃４０９５は、それぞれノード３００１〜３００６で構成されており、各スパニングツリーの状態を太線で示している。
【０３２５】
図１４に示すネットワーク状態においては、現用ツリー＃４００１ではノード３００１が、現用ツリー＃４００２ではノード３００２が、現用ツリー＃４００３ではノード３００３が、現用ツリー＃４００４ではノード３００４が、現用ツリー＃４００５ではノード３００５、現用ツリー＃４００６ではノード３００６がそれぞれルートノードとなっており、予備用ツリー＃４０９５ではノード３００１がルートノードとなっている。
【０３２６】
ここで、上記のような構成のネットワークに、図１５に示すように、新たなノード＃３０１２が追加される場合の処理について、図２３のタイミングチャートを参照して説明する。
【０３２７】
まず、図１５に示すように、現用ツリー＃４００１に対する新たなノード＃３０１２の追加が実行される。
【０３２８】
（ステップＥ−１）
追加されるノード３０１２が、ネットワーク内の各現用ツリー＃４００１〜＃４００６に対して、予備用ツリー＃４０９５の使用をブロードキャストにより通知する。
【０３２９】
（ステップＥ−２）
一定時間経過後、他のノード（全ての現用ツリー＃４００１〜＃４００６のノード）からの予備用ツリー＃４０９５の使用中を示す通知がなければ、ネットワーク内の各現用ツリー＃４００１〜＃４００６に対して、予備用ツリー＃４０９５の確保をブロードキャストにより通知する。
【０３３０】
（ステップＥ−３）
追加ノード３０１２は、再構成管理テーブル１１６６に関して、再構成処理フラグ５０１３がＯＦＦであるツリーを選択して（この場合ツリー＃４００１）、その後、現用ツリー＃４００１のルートノード３００１に対して追加要求メッセージを送信することにより、ツリーへの追加要求を行う。
【０３３１】
（ステップＥ−４）
追加ノード３０１２からの追加要求メッセージを受けると、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値よりも小さい値に設定変更する。これにより、ルートノード３００１はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが他のノードよりも小さくなるため予備用ツリー＃４０９５のルートノードとなる。その結果、予備用ツリー＃４０９５のスパニングツリーの状態は、図１７に示すように、現用ツリー＃４００１と同じ状態となる。
【０３３２】
（ステップＥ−５）
これにより、現用ツリー＃４００１において、予備用ツリー＃４０９５を利用して新たなノード３０１２を追加するための再構成処理（再構成処理）が実行される。このツリーの再構成処理については、第１の実施の形態で説明した処理と同様の処理がなされる。
【０３３３】
（ステップＥ−６）
現用ツリー＃４００１の再構成処理が終了後、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤを初期値に戻す。
【０３３４】
現用ツリー＃４００１の再構成処理の終了後、現用ツリー＃４００１のルートノード３００１は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値に設定変更する。これにより、ルートノード３００１はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが通常の値に戻るためツリー＃４０９５のルートノードは網内のノードの中でＭＡＣアドレスが最も小さいノードが選択される状態に戻る。
【０３３５】
（ステップＥ−７）
さらに、現用ツリー＃４００１のルートノード３００１は、追加ノード３０１２に対して、現用ツリー＃４００１へのノード３０１２の追加が完了した旨を通知する。
【０３３６】
（ステップＥ−８）
追加ノード３０１２では、上記再構成処理完了の通知を受けると、再構成管理テーブル５００１のエントリ５０１１のツリーＩＤ（この場合、＃４００１）に対応する再構成処理フラグ５０１３を「済（ＯＮ）」に設定する。また、予備用ツリー使用状態管理フラグをフラグ＝ＯＦＦとして、予備用ツリー＃４０９５を他のノードの追加削除処理に使用可能とする。
【０３３７】
追加ノード３０１２は、再構成管理テーブル１１６６に関して、再構成処理終了したツリーの再構成処理フラグ５０１３を「済み（ＯＮ）」に設定すると共に、再構成処理フラグ５０１３がＯＦＦであるツリーを選択して、その後、次のツリーである、図１４に示す現用ツリー＃４００２に対する新たなノード３０１２の追加が実行される。
【０３３８】
（ステップＥ−９）
追加されるノード３０１２から、再構成処理フラグ５０１３がＯＦＦである現用ツリー＃４００２のルートノード３００２に対して追加要求メッセージを送信することにより、ツリーへの追加要求を行う。
【０３３９】
（ステップＥ−１０）
追加ノード３０１２からの追加要求メッセージを受けると、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値よりも小さい値に設定変更する。これにより、ルートノード３００２はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが他のノードよりも小さくなるため予備用ツリー＃４０９５のルートノードとなる。その結果、予備用ツリー＃４０９５のスパニングツリーの状態は、現用ツリー＃４００２と同じ状態となる。
【０３４０】
（ステップＥ−１１）
これにより、現用ツリー＃４００２において、予備用ツリー＃４０９５を利用して新たなノード３０１２を追加するための再構成処理（再構成処理）が実行される。このツリーの再構成処理については、第１の実施の形態で説明した図１９、図２１の処理と同様の処理がなされる。
【０３４１】
（ステップＥ−１２）
現用ツリー＃４００２の再構成処理が終了後、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤを初期値に戻す。
【０３４２】
現用ツリー＃４００２の再構成処理の終了後、現用ツリー＃４００２のルートノード３００２は、予備用ツリー＃４０９５に関するＢｒｉｄｇｅ＿ＩＤのプライオリティ値をデフォルト値に設定変更する。これにより、ルートノード３００２はツリー＃４０９５のＢｒｉｄｇｅ＿ＩＤが通常の値に戻るためツリー＃４０９５のルートノードは網内のノードの中でＭＡＣアドレスが最も小さいノードが選択される状態に戻る。
【０３４３】
（ステップＥ−１３）
さらに、現用ツリー＃４００２のルートノード３００２は、追加ノード３０１２に対して、現用ツリー＃４００２への追加が完了した旨を通知する。
【０３４４】
（ステップＥ−１４）
追加ノード３０１２では、上記再構成処理完了の通知を受けると、再構成管理テーブル５００１のエントリ５０１１のツリーＩＤ（この場合、＃４００２）に対応する再構成処理フラグ５０１３を「済（ＯＮ）」に設定する。また、予備用ツリー使用状態管理フラグをフラグ＝ＯＦＦとして、予備用ツリー＃４０９５を他のノードの追加削除処理に使用可能とする。
【０３４５】
追加ノード３０１２は、再構成管理テーブル１１６６に関して、再構成処理終了したツリーの再構成処理フラグ５０１３を「済み（ＯＮ）」に設定すると共に、再構成処理フラグ５０１３がＯＦＦであるツリーを選択して、その後、次のツリーに対する新たなノード３０１２の追加が実行される。
【０３４６】
以下、上記と同じ処理を繰り返すことによって、残りの現用ツリー＃４００３から＃４００６に対するノード３０１２の追加処理が実行される。
【０３４７】
そして、全ての現用ツリー＃４００１〜＃４００６へのノード３０１２の追加処理が完了した時点で、追加ノード３０１２は、ネットワーク内の各現用ツリー＃４００１〜＃４００６に対して、予備用ツリー＃４０９５の解放を、ブロードキャストにより通知する。
【０３４８】
上記のようにしてノード３０１２が追加された現用ツリー＃４００１〜＃４００６の状態を図１８に示す。
【０３４９】
なお、図２３においては、ネットワークシステムに対してノード＃３０１２が追加される場合の処理について説明したが、ネットワークを構成するノードが削除される場合の処理についても、図２３と同様の処理がなされる。すなわち、図２３において、「追加（又は追加処理）」とあるのを「削除（又は削除処理）」とすることで、ノードが削除される場合の処理が説明される。
【０３５０】
第３の実施の形態の効果について述べる。第３の実施の形態によれば、ネットワーク構成の変更時にネットワークを停止させることなくスパニングツリーの再構成を可能にすると共に、ネットワークで使用できるスパニングツリーの数が２分の１に制限されていた従来の問題を回避し、使用できるスパニングツリーの数をスパニングツリーの最大数−１まで拡張可能とすることができる効果と共に、第１の実施の形態で示した管理用サーバ５０００の機能を追加又は削除されるノードに持たせることにより、ツリー再構成のための管理用サーバを設ける必要がなくなる効果が得られる。
【０３５１】
なお、上記各実施例のネットワークシステムにおける、各ノード及び管理用サーバの各機能ついては、ハードウェアによることは勿論として、それらの各機能を有するスパニングツリー再構成処理プログラムを、各ノードを構成するコンピュータ装置上で実行することで実現することが可能である。
【０３５２】
このスパニングツリー再構成処理プログラムは、磁気ディスク、半導体メモリその他の記録媒体に格納され、その記録媒体からノード及び管理用サーバであるコンピュータ装置にロードされ、コンピュータ装置の動作を制御することにより、上述した各機能を実現する。
【０３５３】
以上好ましい実施例をあげて本発明を説明したが、本発明は必ずしも上記実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【図面の簡単な説明】
【０３５４】
【図１】従来のＶＬＡＮタグ付きイーサネット(R)フレームの構成例を示す図である。
【図２】本発明の拡張タグ付きイーサネット(R)フレームの構成例を示す図である。
【図３】本発明の拡張タグ付きイーサネット(R)フレームの他の構成例を示す図である。
【図４】本発明の拡張タグ格納領域の構成例を示す図である。
【図５】本発明におけるＣｏｎｆｉｇｕｒａｔｉｏｎ  BPDUのフレーム構成を示すフォーマット図である。
【図６】本発明におけるＴｏｐｏｌｏｇｙ  Ｃｈａｎｇｅ  Ｎｏｔｉｆｉｃａｔｉｏｎ  BPDUのフレーム構成を示すフォーマット図である。
【図７】本発明における、拡張フレームの他の構成例を示す図である。
【図８】本発明の第１の実施の形態によるネットワークシステムの構成を示すブロック図である。
【図９】本発明の第１の実施の形態によるネットワークを構成するノードの構成を詳細に示すブロック図である。
【図１０】本発明の第１の実施の形態によるノードのタグをキーとして出力ポートを決定するためのフォワーディングテーブルの内容例を示す図である。
【図１１】本発明の第１の実施の形態のノードの再構成コントローラの構成を詳細に示したブロック図である。
【図１２】第１の実施の形態によるネットワークシステムの構成を示す図である。
【図１３】第１の実施の形態による再構成管理テーブルの設定内容例を示す図である。
【図１４】第１の実施の形態によるネットワークシステムのツリー構成を示す図である。
【図１５】ネットワークに新たなノードが追加される場合のネットワーク構成を示す図である。
【図１６】第１の実施の形態においてネットワークに新たなノードが追加される場合の処理の内容を説明するシーケンス図である。
【図１７】新たなノードが追加される場合の予備用ツリーの状態を示す図である。
【図１８】図１４に示すネットワークシステムにおいてノードが追加された現用ツリーの状態を示す図である。
【図１９】ノードの追加によるツリーの再構成処理の詳細を示すシーケンス図である。
【図２０】安定タイマのタイマモードの設定内容を説明する図である。
【図２１】ノードの削除によるツリーの再構成処理の詳細を示すシーケンス図である。
【図２２】第２の実施の形態においてネットワークに新たなノードが追加される場合の処理の内容を説明するシーケンス図である。
【図２３】第３の実施の形態においてネットワークに新たなノードが追加される場合の処理の内容を説明するシーケンス図である。
【符号の説明】
【０３５５】
＃４００１〜＃４００６：現用ツリー
＃４０９５：予備用ツリー
１１１：    フレーム転送器
１１２，１１６３：    タグ挿入器
１１３，１１６１：    タグ削除器
１１４：    フォワーディングテーブル
１１５：    ＳＴＰコントローラ
１１６：    再構成コントローラ
１１７：    フレーム分別器
１１８：    設定インタフェース
１１６２：  制御フレーム送受信部
１１６４：  再構成処理部
１１６５：  拡張再構成処理部
１１６６：  再構成管理テーブル
１１６７：  安定タイマ
３００１、３００２、３００３、３００４、３００５、３００６：    ノード
３０１２：追加対象（又削除対象）のノード
５０００：  管理用サーバ
５０１１：  ＳＴＰ−ＩＤ
５０１２：  ルートノードのＭＡＣアドレス
５０１３：  再構成処理フラグ
【図１】
2006279842.tif 000003
【図２】
2006279842.tif 000004
【図３】
2006279842.tif 000005
【図４】
2006279842.tif 000006
【図５】
2006279842.tif 000007
【図６】
2006279842.tif 000008
【図７】
2006279842.tif 000009
【図８】
2006279842.tif 000010
【図９】
2006279842.tif 000011
【図１０】
2006279842.tif 000012
【図１１】
2006279842.tif 000013
【図１２】
2006279842.tif 000014
【図１３】
2006279842.tif 000015
【図１４】
2006279842.tif 000016
【図１５】
2006279842.tif 000017
【図１６】
2006279842.tif 000018
【図１７】
2006279842.tif 000019
【図１８】
2006279842.tif 000020
【図１９】
2006279842.tif 000021
【図２０】
2006279842.tif 000022
【図２１】
2006279842.tif 000023
【図２２】
2006279842.tif 000024
【図２３】
2006279842.tif 000025