(57)【要約】【課題】ループを発生させずに任意の情報処理装置宛のパケットの転送経路を変更できるようにする。【解決手段】経路更新手段１ａにより、経路４ａが異なる経路４ｂに更新される。次に、特定手段１ｂにより、パケットが転送先アドレスの情報処理装置３に到達可能な範囲５ａが特定される。次に変更手段１ｃにより、到達可能な範囲５ａ内にある通信装置に隣接する到達不可能な範囲内にある通信装置において、パケットを到達可能な範囲５ａにある通信装置に転送できるように、読み出した転送情報が変更される。次に送信手段１ｄにより、変更された転送情報が、対応する通信装置に転送される。また、追加手段１ｅにより、転送情報を変更したことによって、パケットが転送先アドレスに新たに到達可能となる範囲が、到達可能な範囲５ａに追加される。すると特定手段１ｂにより、新たな到達可能な範囲５ｂが特定される。【選択図】図１
2011029975.tif 000002
【特許請求の範囲】
【請求項１】
転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するネットワーク管理装置であるコンピュータに、
パケットの転送経路の変更を伴うイベントが発生すると、前記ネットワーク管理装置が記憶する前記通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手順と、
転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、前記到達可能な範囲以外の部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手順と、
前記ネットワーク管理装置が記憶する各転送情報を読み出し、前記到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを前記到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手順と、
変更した転送情報を、対応する通信装置に送信する送信手順と、
転送情報を変更したことによって、前記転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、前記到達可能な範囲に追加する追加手順と、
を実行させるためのネットワーク管理プログラム。
【請求項２】
前記経路更新手順では、パケットの転送経路の変更を伴う前記イベントとして、前記通信装置の出力ポートのいずれかが通信不可能であることを示す情報を、前記通信装置から受信すると、前記ネットワーク管理装置が記憶する前記通信装置ごとの転送情報から得られる経路を、前記通信不可能な出力ポートを経由せずにパケット転送が可能となるように更新する請求項１記載のネットワーク管理プログラム。
【請求項３】
前記コンピュータに、
前記追加手順の後に、前記通信装置の少なくとも１つが前記到達可能な範囲外にあれば、前記特定手順と前記変更手順と前記送信手順と前記追加手順とを実行させる、
ための請求項１記載のネットワーク管理プログラム。
【請求項４】
前記コンピュータは、転送先アドレスと通信装置の識別子との組と、転送情報の転送順序を示す順序番号との対応関係を示す順序番号情報を記憶し、
前記コンピュータに、
転送先アドレスごとに、前記特定手順、前記変更手順、および前記追加手順を繰り返し行い、同一回の前記変更手順で到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にあると判定された通信装置の順序番号として同じ値を、前記順序番号情報に記憶させる順序番号生成手順を更に実行させ、
前記送信手順は、通信装置ごとの順序番号が同じ複数の転送先アドレスに対応する転送情報の出力ポートの変更内容をまとめた１つの転送情報を送信する、
請求項１乃至３記載のネットワーク管理プログラム。
【請求項５】
転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するネットワーク管理装置であって、
パケットの転送経路の変更を伴うイベントが発生すると、前記ネットワーク管理装置が記憶する前記通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手段と、
転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、前記到達可能な範囲以外の部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手段と、
前記ネットワーク管理装置が記憶する各転送情報を読み出し、前記到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを前記到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手段と、
変更した転送情報を、対応する通信装置に送信する送信手段と、
転送情報を変更したことによって、前記転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、前記到達可能な範囲に追加する追加手段と、
を有するネットワーク管理装置。
【請求項６】
転送先アドレスと通信装置の識別子との組と、転送情報の転送順序を示す順序番号との対応関係を示す順序番号情報を記憶する記憶手段と、
転送先アドレスごとに、前記特定手段、前記変更手段、および前記追加手段が処理を繰り返し実行し、前記変更手段における同一回の処理で到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にあると判定された通信装置の順序番号として同じ値を、前記順序番号情報に記憶させる順序番号生成手段とを更に有し、
前記送信手段は、通信装置ごとの順序番号が同じ複数の転送先アドレスに対応する転送情報の出力ポートの変更内容をまとめた１つの転送情報を送信する、
請求項５記載のネットワーク管理装置。
【請求項７】
転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するコンピュータが、
パケットの転送経路の変更を伴うイベントが発生すると、前記コンピュータが記憶する前記通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手順と、
転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、前記到達可能な範囲以外の部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手順と、
前記コンピュータが記憶する各転送情報を読み出し、前記到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを前記到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手順と、
変更した転送情報を、対応する通信装置に送信する送信手順と、
転送情報を変更したことによって、前記転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、前記到達可能な範囲に追加する追加手順と、
を実行するネットワーク管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信装置をコンピュータに管理させるネットワーク管理プログラム、ネットワーク管理装置、およびネットワーク管理方法に関する。
【背景技術】
【０００２】
コンピュータネットワークは、スイッチなどの多数の通信装置を介してコンピュータ（情報処理装置）同士が接続されている。各通信装置は、パケットの宛先に応じて適切な転送先を判断する。そこで、パケットの転送方向を通信装置に任意に指定することで、パケットの転送経路を任意に制御することが可能となる。例えばループ型（リング状）のネットワークに対するルーティング情報の再構成技術がある。
【０００３】
ところで、コンピュータネットワークには、ループ型のネットワークよりも複雑な構成のネットワークがある。例えば、以下の（１）〜（５）に示す特徴を持つネットワークについて考える。
（１）パケットによる通信を行うコンピュータをノードとし、各ノードはアドレスを持つ。
（２）転送されるパケットには転送先のノードのアドレス情報が格納されている。
（３）スイッチは、ＦＤＢ（Forwarding Data Base）を持つ。ＦＤＢには、パケットの転送先となるノードのアドレスに対応する出力ポートが記述されている。
（４）スイッチは到着したパケットの転送先となるノードを示すアドレスに基づき、ＦＤＢを参照し、出力ポートを決定する。そしてスイッチは、決定した出力ポートへパケットを転送する。
（５）各スイッチのＦＤＢは、ネットワーク管理装置により設定される。
【０００４】
上記の特徴を持つネットワークの一例としてInfiniBand（商標）がある。また、ETHERNET（登録商標）においても、（１）〜（４）の特徴は満たしている。そのため、ETHERNET（登録商標）でも、ネットワーク管理装置がＦＤＢを設定するようなスイッチを導入すれば、上記の特徴を持つネットワークとなる。
【０００５】
このようなネットワークでは、転送先ノードごとにパケットの転送経路を設定することができる。そのため適切にＦＤＢを各スイッチに設定することで、帯域や冗長性を適切に確保できる。
【０００６】
このようなネットワークにおいて、以下のような理由により経路を変更する場合がある。
〔障害発生時〕障害箇所を回避するような経路に更新することで、障害時にも通信処理を継続させる。
【０００７】
〔保守作業時〕保守作業により切断される箇所を回避するような経路に更新することで、保守作業時にも通信処理を継続させる。
〔性能チューニング時〕ある特定の用途に合わせた経路に変更することで、特定用途における性能を向上させる。
【０００８】
これらの経路変更事由に該当するイベントが発生すると、ネットワーク管理装置が、経路変更処理を実行する。経路変更処理は以下のような手順で実施される。
〔第１のステップ〕ネットワーク管理装置が、障害回避や性能向上の目的を実現する経路を計算し、各スイッチのＦＤＢを作成する。
【０００９】
〔第２のステップ〕ネットワーク管理装置が、作成したＦＤＢを各スイッチに配布する。ネットワーク管理装置から配布されたＦＤＢによって、各スイッチが内部のＦＤＢを変更することで、ネットワーク全体での経路変更が完了する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００１−３０８８９３号公報
【特許文献２】特開２００６−２７０１６９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、従来のＦＤＢの配布では、どのスイッチから順にＦＤＢを配布するかが特に考慮されていないため、経路変更処理途中にループが発生する可能性がある。ここで「ループ」とは、パケットの転送経路上での始点と終点とが同じとなる経路（閉路）である。
【００１２】
例えばノードＸ宛のパケットについて、経路変更前は、スイッチＡからスイッチＢに送信していたものとする。この場合、スイッチＡはノードＸ宛のパケットをスイッチＢに転送するが、スイッチＢはノードＸ宛のパケットをスイッチＡ以外に転送するように、各スイッチのＦＤＢが設定されている。ここで、何らかの経路変更事由が発生し、ノードＸ宛のパケットについて、スイッチＢからスイッチＡに送信するように経路変更を行うものとする。
【００１３】
このとき、従来では、スイッチＢに対するＦＤＢの変更をスイッチＡよりも先に実行してしまう場合があり得る。この場合、スイッチＢのＦＤＢ変更直後は、スイッチＡはＦＤＢ変更前の状態のままである。するとスイッチＡは、ノードＸ宛のパケットを依然としてスイッチＢに転送する。スイッチＢはＦＤＢが変更されたことにより、ノードＸ宛のパケットをスイッチＡに転送する状態となる。その結果、ノードＸ宛のパケットの転送についてスイッチＡとスイッチＢとの間でループが発生してしまう。
【００１４】
なおループを発生させない方法として、一旦全てのスイッチのＦＤＢをリセットし、再設定しなおす方法も考えられる。この場合、更新処理中、通信が途絶えてしまうことになる。特に障害回避の事例においては、送信先ノードへのパケット転送に関して障害の影響を受けていない到達可能なスイッチについても、リセットされることで送信先ノードへのパケットの到達が不能になってしまう。すなわち、ネットワークの一部に障害が発生しただけなのにすべての通信が不能になってしまう。このような障害の影響を拡大してしまう対処方法は、ネットワークの安定運用の観点から不適切である。
【００１５】
このような問題は、ＦＤＢにより転送先を管理するスイッチを用いたネットワークに限らず、送信先ごとのパケットの転送情報をネットワーク管理装置から変更可能なネットワーク一般に発生する。
【００１６】
本発明はこのような点に鑑みてなされたものであり、ループを発生させずに任意の情報処理装置宛のパケットの転送経路を変更できるネットワーク管理プログラム、ネットワーク管理装置、およびネットワーク管理方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
上記課題を解決するために、転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するネットワーク管理装置であるコンピュータに以下の処理を実行させるネットワーク管理プログラムが提供される。
【００１８】
ネットワーク管理プログラムに従って、コンピュータは、パケットの転送経路の変更を伴うイベントが発生すると、ネットワーク管理装置が記憶する通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手順を実行する。次にコンピュータは、転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、到達可能な範囲以外の部分経路を、転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手順を実行する。次にコンピュータは、ネットワーク管理装置が記憶する各転送情報を読み出し、到達可能な範囲内にある通信装置に隣接する到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手順を実行する。そしてコンピュータは、変更した転送情報を、対応する通信装置に送信する送信手順と、転送情報を変更したことによって、転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、到達可能な範囲に追加する追加手順とを実行する。
【００１９】
また上記課題を解決するために、上記ネットワーク管理プログラムを実行するコンピュータと同様の機能を有するネットワーク管理装置が提供される。さらに上記課題を解決するために、上記ネットワーク管理プログラムを実行するコンピュータと同様の手順で処理を行うネットワーク管理方法が提供される。
【発明の効果】
【００２０】
ループを発生させずにパケットの転送経路の変更が可能となる。
【図面の簡単な説明】
【００２１】
【図１】第１の実施の形態の概要を示す図である。
【図２】第２の実施の形態に係るシステム構成例を示す図である。
【図３】スイッチのハードウェア構成を示す図である。
【図４】スイッチに格納されるＦＤＢのデータ構造例を示す図である。
【図５】ネットワーク管理装置のハードウェア構成例を示す図である。
【図６】ネットワーク管理装置の機能を示すブロック図である。
【図７】結線情報のデータ構造例を示す図である。
【図８】ＦＤＢ記憶部のデータ構造例を示す図である。
【図９】経路情報の概念図である。
【図１０】第２の実施の形態に係る経路変更処理の手順を示すフローチャートである。
【図１１】結線情報更新例を示す図である。
【図１２】更新後の経路情報の例を示す図である。
【図１３】ＦＤＢ更新指示の処理手順を示すフローチャートである。
【図１４】対象ノードに到達可能な経路探索処理の手順を示すフローチャートの前半である。
【図１５】対象ノードに到達可能な経路探索処理の手順を示すフローチャートの後半である。
【図１６】到達経路判定テーブルのデータ構造例を示す図である。
【図１７】隣接するスイッチの探索処理の手順を示すフローチャートの前半である。
【図１８】隣接するスイッチの探索処理の手順を示すフローチャートの後半である。
【図１９】隣接スイッチリストのデータ構造例を示す図である。
【図２０】隣接するスイッチを到達可能な経路に追加する処理の手順を示すフローチャートである。
【図２１】隣接するスイッチを到達可能な経路に追加後の到達経路判定テーブルの例を示す図である。
【図２２】第１周期目のＦＤＢ配布時の到達可能な経路と隣接するスイッチを示す図である。
【図２３】第２周期目のＦＤＢ配布時の到達可能な経路と隣接するスイッチを示す図である。
【図２４】第３の実施の形態に係るネットワーク管理装置の機能を示すブロック図である。
【図２５】第３の実施の形態に係る経路更新処理の手順を示すフローチャートである。
【図２６】半順序番号一覧表作成処理の手順を示すフローチャートである。
【図２７】半順序番号一覧表のデータ構造例を示す図である。
【図２８】ＦＤＢ更新指示の手順を示すフローチャートである。
【図２９】ＤＬＩＤ「０ｘ１」宛のパケットの転送経路の初期状態と最終状態とを示す図である。
【図３０】ＤＬＩＤ「０ｘ２」宛のパケットの経路情報の初期状態と最終状態とを示す図である。
【図３１】ＤＬＩＤ「０ｘ３」宛のパケットの経路情報の初期状態と最終状態とを示す図である。
【図３２】転送先アドレスごとの半順序番号を示す図である。
【図３３】半順序番号一覧表の例を示す図である。
【図３４】ＤＬＩＤ「Ｆ」のスイッチ内のＦＤＢの内容の遷移例を示す図である。
【発明を実施するための形態】
【００２２】
以下、本実施の形態について図面を参照して説明する。
〔第１の実施の形態〕
図１は、第１の実施の形態の概要を示す図である。ネットワーク管理装置１は、複数の通信装置２ａ〜２ｌを管理する。通信装置２ａ〜２ｌは、転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う。例えば通信装置２ａ〜２ｌは、レイヤ３スイッチである。また転送情報は、例えばＦＤＢである。
【００２３】
ネットワーク管理装置１は、経路更新手段１ａ、特定手段１ｂ、変更手段１ｃ、送信手段１ｄ、および追加手段１ｅを有している。
経路更新手段１ａは、パケットの転送経路の変更を伴うイベントが発生すると、ネットワーク管理装置１が記憶する通信装置ごとの転送情報から得られる経路４ａを、異なる経路４ｂに更新する。例えば経路更新手段１ａは、パケットの転送経路の変更を伴うイベントとして、通信装置の出力ポートのいずれかが通信不可能であることを示す情報を、通信装置から受信する。その場合、経路更新手段１ａは、ネットワーク管理装置１が記憶する通信装置ごとの転送情報から得られる経路４ａを、通信不可能な出力ポートを経由せずにパケット転送が可能となるような経路４ｂに更新する。例えば経路更新手段１ａは、通信可能な伝送路を辿って最もホップ数が小さくなるような経路を生成する。
【００２４】
特定手段１ｂは、転送先アドレスで示された情報処理装置３に隣接する通信装置２ａを含み、更新前の経路４ａと更新後の経路４ｂとの一致する部分経路を、転送先アドレスに示される情報処理装置３にパケットが到達可能な範囲５ａとして特定する。転送先アドレスで示された情報処理装置３に隣接する通信装置とは、例えばネットワーク管理装置１が管理する通信装置２ａ〜２ｌの中で、他の通信装置２ｂ〜２ｌを経由せずに情報処理装置３に接続された通信装置２ａである。さらに特定手段１ｂは、到達可能な範囲５ａ以外の部分経路を、転送先アドレスで示された情報処理装置３にパケットが到達不可能な範囲として特定する。
【００２５】
なお特定手段１ｂは、追加手段１ｅにより、転送先アドレスで示される情報処理装置３に、パケットが新たに到達可能となる範囲の追加が行われた場合、通信装置２ａ〜２ｌの少なくとも１つが到達可能な範囲外にあれば、再度、更新後の到達可能な範囲５ｂを特定する。
【００２６】
変更手段１ｃは、ネットワーク管理装置１が記憶する各転送情報を読み出す。そして変更手段１ｃは、到達可能な範囲５ａ，５ｂ内にある通信装置に隣接する到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを到達可能な範囲５ａ，５ｂにある通信装置に転送できるように、読み出した転送情報を変更する。ここで隣接する通信装置とは、例えばホップ数が１の通信装置である。なお変更手段１ｃは、例えば特定手段１ｂにより到達可能な範囲５ａ，５ｂが特定されるごとに、転送情報の変更を行う。
【００２７】
送信手段１ｄは、変更手段１ｃにより転送情報が変更されるごとに、変更された転送情報６ａ〜６ｅを、対応する通信装置に送信する。
追加手段１ｅは、転送情報を変更したことによって、転送先アドレスで示される情報処理装置３にパケットが新たに到達可能となる範囲を、到達可能な範囲５ａに追加する。その結果、新たな到達可能な範囲５ｂが生成される。なお追加手段１ｅは、例えば変更手段１ｃにより転送情報が変更されるごとに、パケットが転送先アドレスに新たに到達可能となる範囲を、到達可能な範囲５ａに追加する。
【００２８】
このようなネットワーク管理装置１によれば、パケットの転送経路の変更を伴うイベントが発生すると、経路更新手段１ａにより、経路４ａが異なる経路４ｂに更新される。次に、特定手段１ｂにより、転送先アドレスで示された情報処理装置３に隣接する通信装置２ａを含み、更新前の経路４ａと更新後の経路４ｂとの一致する部分経路が、転送先アドレスで示された情報処理装置にパケットが到達可能な範囲５ａとして特定される。さらに特定手段１ｂにより、到達可能な範囲５ａ以外の部分経路が、転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定される。次に変更手段１ｃにより、各転送情報が読み出され、到達可能な範囲内にある通信装置に隣接する到達不可能な範囲内にある通信装置において、パケットを到達可能な範囲にある通信装置に転送できるように、読み出した転送情報が変更される。例えば、図１に示す通信装置２ｇ，２ｋが、到達可能な範囲内にある通信装置に隣接する到達不可能な範囲内にある通信装置として選択され、通信装置２ｇ，２ｋの転送情報が更新される。
【００２９】
次に送信手段１ｄにより、変更された転送情報が、対応する通信装置に転送される。例えば通信装置２ｇ，２ｋの転送情報が更新された場合、通信装置２ｇ，２ｋに対して転送情報６ａ，６ｂが転送される。これにより第１周期目の転送情報の送信が完了する。
【００３０】
また、追加手段１ｅにより、転送情報を変更したことによって、パケットが転送先アドレスに新たに到達可能となる範囲が、到達可能な範囲５ａに追加される。すると特定手段１ｂにより、新たな到達可能な範囲５ｂが特定される。
【００３１】
新たな到達可能な範囲５ｂが特定されたことで、新たな通信装置が、到達可能な範囲内にある通信装置に隣接する到達不可能な範囲内にある通信装置となる。そこで変更手段１ｃにより、到達可能な範囲内にある通信装置に隣接する到達不可能な範囲内にある通信装置の転送情報が、転送先アドレスで示される情報処理装置３にパケットを転送できるように変更される。例えば通信装置２ｆ，２ｈ，２ｌの転送情報が更新される。変更された転送情報６ｃ〜６ｅは、送信手段１ｄにより対応する通信装置２ｆ，２ｈ，２ｌに転送される。
【００３２】
ここで、追加手段１ｅにより、転送情報を変更したことによって、パケットが転送先アドレスに新たに到達可能となる範囲が、到達可能な範囲５ｂに追加される。図１の例では、通信装置２ｆ，２ｈ，２ｌに転送情報６ｃ〜６ｅが転送されることで、すべての通信装置２ａ〜２ｌが、パケットが転送先アドレスに示される情報処理装置３に到達可能な範囲に含まれることとなる。
【００３３】
このように、パケットが転送先アドレスに示される情報処理装置３に到達可能な範囲内の通信装置に隣接する通信装置から順番に更新した転送情報を転送し、到達可能な範囲を徐々に広げていくことで、ループを発生させずにパケットの転送経路の更新が可能となる。すなわち、到達可能な範囲内の通信装置は、転送先アドレスに示される情報処理装置３へのパケットを、到達可能な範囲外の通信装置には転送しない。そのため、到達可能な範囲内の通信装置に隣接する到達可能な範囲外の通信装置の転送情報を更新しても、ループが発生することはない。そして、到達可能な範囲を徐々に拡張していけば、いずれはすべての通信装置２ａ〜２ｌが到達可能な範囲内となる。その結果、経路の変更途中でループを発生させることなく、通信装置２ａ〜２ｌを経由する情報処理装置３宛のパケットの転送経路が、初期の経路４ａから更新後の経路４ｂに変更される。
【００３４】
このような経路変更時のループの発生防止は、ネットワーク上の通信の信頼性向上に大きく寄与する。すなわち、ネットワークが大規模になると、すべてのスイッチのＦＤＢを更新するのに時間がかかる。これは、１台のスイッチのＦＤＢの更新指示から更新完了の応答まで、最大で１００ｍｓかかることや、多数のスイッチに対するＦＤＢの更新指示を同時に行うと、ネットワークが不安定となるため、順番にＦＤＢの更新をせざるを得ないためである。連続して制御パケットを送信すると、その間、ループ状態が継続してしまう。ループ状態が長引けば、パケットが正しく宛先に転送できない状態が続き、ネットワークのサービス品質の劣化につながる。換言すると、ループ状態の発生が防止されることで、サービスの品質が向上する。
【００３５】
なお、パケットの転送経路の変更を伴うイベントとしては、通信不可能であることを示す情報の受信に限らず、保守作業により切断される箇所の入力や、性能チューニングを目的とした経路変更の入力などがある。
【００３６】
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、InfiniBand（商標）における障害発生時の経路縮退の事例である。
【００３７】
図２は、第２の実施の形態に係るシステム構成例を示す図である。図２に示すように、複数のスイッチ２１〜３２が高速のデータ伝送可能な通信ケーブルで接続されることによってネットワークが形成されている。スイッチ２１は、スイッチ２２，２６に接続されている。スイッチ２２は、上記接続に加え、スイッチ２３，２７に接続されている。スイッチ２３は、上記接続に加え、スイッチ２４，２５に接続されている。スイッチ２５は、上記接続に加え、スイッチ３１に接続されている。スイッチ２６は、上記接続に加え、スイッチ２７，２８に接続されている。スイッチ２７は、上記接続に加え、スイッチ２８，２９に接続されている。スイッチ２８は、上記接続に加え、スイッチ３０に接続されている。スイッチ２９は、上記接続に加え、スイッチ３１に接続されている。スイッチ３０は、上記接続に加え、スイッチ３２に接続されている。スイッチ３１は、上記接続に加え、スイッチ３２に接続されている。
【００３８】
スイッチ２１〜３２には、それぞれネットワーク上で一意に識別するための識別子（ＩＤ）が設定されている。スイッチ２１のＩＤは「Ａ」である。スイッチ２２のＩＤは「Ｂ」である。スイッチ２３のＩＤは「Ｃ」である。スイッチ２４のＩＤは「Ｄ」である。スイッチ２５のＩＤは「Ｅ」である。スイッチ２６のＩＤは「Ｆ」である。スイッチ２７のＩＤは「Ｇ」である。スイッチ２８のＩＤは「Ｈ」である。スイッチ２９のＩＤは「Ｉ」である。スイッチ３０のＩＤは「Ｊ」である。スイッチ３１のＩＤは「Ｋ」である。スイッチ３２のＩＤは「Ｌ」である。
【００３９】
各スイッチ２１〜３２には、ネットワークを介したデータ通信を行うコンピュータが接続されている。このコンピュータを、以下「ノード」と呼ぶ。スイッチ２１には、ノード４１ａ，４１ｂ，・・・が接続されている。スイッチ２２には、ノード４２ａ，４２ｂ，・・・が接続されている。スイッチ２３には、ノード４３ａ，４３ｂ，・・・が接続されている。スイッチ２４には、ノード４４ａ，４４ｂ，・・・が接続されている。スイッチ２５には、ノード４５ａ，４５ｂ，・・・が接続されている。スイッチ２６には、ノード４６ａ，４６ｂ，・・・が接続されている。スイッチ２７には、ノード４７ａ，４７ｂ，・・・が接続されている。スイッチ２８には、ノード４８ａ，４８ｂ，・・・が接続されている。スイッチ２９には、ノード４９ａ，４９ｂ，・・・が接続されている。スイッチ３０には、ノード５０ａ，５０ｂ，・・・が接続されている。スイッチ３１には、ノード５１ａ，５１ｂ，・・・が接続されている。スイッチ３２には、ノード５２ａ，５２ｂ，・・・が接続されている。
【００４０】
各スイッチ２１〜３２は、入力されたパケットを、そのパケットの送信先に応じて他のポートから出力する。これにより、任意のノードから出力されたパケットが、スイッチ２１〜３２を介して送信先のノードに転送される。
【００４１】
通信対象となる各ノードには、ＬＩＤという識別子が割り当てられている。例えば、ノード４１ａのＬＩＤは「０ｘ１」、ノード５２ａのＬＩＤは「０ｘ２」、ノード４５ａのＬＩＤは「０ｘ３」である。ネットワーク上を伝送されるパケットでは、送信先がＤＬＩＤ（Destination LID）で指定される。パケットに示されるＤＬＩＤと同じ値のＬＩＤが割り当てられたノードが、そのパケットの送信先である。
【００４２】
各スイッチ２１〜３２には、パケットに示されるＤＬＩＤに対応付けて、該当ＤＬＩＤを送信先とするパケットをどのポートへ出力するのかを記述した転送情報（ＦＤＢ）が保持されている。そして各スイッチ２１〜３２は、自分のスイッチに到達したパケットのＤＬＩＤを参照し、ＦＤＢに基づき出力するポートを決定し、決定したポートに到達したパケットを転送する。
【００４３】
各スイッチ２１〜３２のＦＤＢはＳＭ（Subnet Manager）により設定される。またネットワークの一部に障害が生じるとＳＭはその障害を検出し、ネットワーク管理装置１００に障害内容（例えば不通となったポートのポート番号）を通知する。そして、ＳＭはネットワーク管理装置１００からの指示に従って自身のＦＤＢを書き換えることで、障害箇所を回避する経路設定を行う。
【００４４】
このように図２に示すシステムでは、ＦＤＢに基づいたパケットのルーティングが行われる。そのため、適切にＦＤＢを各スイッチに設定すれば、スパニングツリー以外の通信経路をとることも可能であり、帯域や冗長性を確保できる。他方、自由度が高いため、ＦＤＢの設定を誤ると意図せずにループ状態が作り出されることも有り得る。
【００４５】
スイッチ２８には、さらにネットワーク管理装置１００が接続されている。ネットワーク管理装置１００は、ネットワーク全体の運用を管理するコンピュータである。例えばネットワーク管理装置１００は、パケットの送信先ごとに、そのパケットの転送経路を決定し、その内容をスイッチ２１〜３２に通知する。ネットワーク上で障害が発生した場合などの経路変更事由の発生時には、ネットワーク管理装置１００は、パケットの転送経路を変更し、変更結果をスイッチ２１〜３２に通知する。各スイッチは、ネットワーク管理装置１００から通知された経路に沿って、各パケットを転送する。
【００４６】
なおネットワーク管理装置１００は、経路を通知する場合、経路の更新途中でループが発生しないように、適切な順番でスイッチ２１〜３２に経路を示すＦＤＢを通知する。
また、各スイッチ２１〜３２は、書き換え可能な記憶装置内にＦＤＢを保持している。そして各スイッチ２１〜３２は、ＦＤＢの内容に従って、パケットを転送（フォワーディング）する。
【００４７】
図３は、スイッチのハードウェア構成を示す図である。スイッチ２１には、通信ケーブル接続用の複数のポート２１−１，２１−２，２１−３，２１−４，２１−５，２１−６，・・・が設けられている。各ポート２１−１，２１−２，２１−３，２１−４，２１−５，２１−６，・・・には、ポート番号が付与されている。また図３の例では、ポート２１−１にスイッチ２２が接続され、ポート２１−２にスイッチ２６が接続され、ポート２１−５にノード４１ａが接続され、ポート２１−６にノード４１ｂが接続されている。
【００４８】
各ポート２１−１，２１−２，２１−３，２１−４，２１−５，２１−６，・・・は、スイッチ２１内部でフォワーディング回路２１ａに接続されている。フォワーディング回路２１ａは、１つのポートから入力されたパケットを、そのパケットの送信先に応じて転送先のポートを選択し、選択したポートからパケットを出力する。
【００４９】
またフォワーディング回路２１ａには、ＣＰＵ（Central Processing Unit）２１ｂやメモリ２１ｃが接続されている。ＣＰＵ２１ｂは、メモリ２１ｃに記憶されたプログラム（図示せず）に従って、ＳＭの機能を実現する。ＣＰＵ２１ｂは、ＳＭの機能の一部として、スイッチ２１の動作状況の監視や、環境設定などを行う。例えばＣＰＵ２１ｂは、各ポート２１−１，２１−２，２１−３，２１−４，・・・を介した通信状況を監視し、障害を検出した場合、制御パケットによって障害の発生をネットワーク管理装置１００に通知する。また、ネットワーク管理装置１００から動作状況の通知要求が入力されると、ＣＰＵ２１ｂは、障害の発生の有無を含む現在の動作状況を制御パケットによってネットワーク管理装置１００に通知する。またＣＰＵ２１ｂは、ネットワーク管理装置１００からの指示に従ってＦＤＢを書き換える。
【００５０】
メモリ２１ｃは、書き換え可能な記憶装置である。例えば半導体記憶装置がメモリ２１ｃとして使用される。メモリ２１ｃには、ＦＤＢ６０が格納される。ＣＰＵ２１ｂは、ネットワーク管理装置１００から更新用のＦＤＢを受け取ると、取得したＦＤＢでメモリ２１ｃ内のＦＤＢ６０を更新する。またフォワーディング回路２１ａは、ＦＤＢ６０を参照して、入力されたパケットの転送先となるポートを決定する。
【００５１】
図４は、スイッチに格納されるＦＤＢのデータ構造例を示す図である。ＦＤＢ６０は、複数の出力ポート設定テーブル６１，６２，・・・を有している。出力ポート設定テーブル６１，６２，・・・は、６４個のＤＬＩＤに１つ設けられている。
【００５２】
各出力ポート設定テーブル６１，６２，・・・には、ＤＬＩＤと出力ポートとの欄が設けられている。出力ポート設定テーブル６１，６２，・・・内の横方向に並べられた情報が互いに対応付けられている。
【００５３】
ＤＬＩＤの欄には、パケットの送信先となるノードのＬＩＤが設定される。出力ポートの欄には、対応するノードを転送先（ＤＬＩＤ）とするパケットを出力すべきポートのポート番号が設定されている。なお、ＤＬＩＤに対応する出力ポートが存在しない場合、出力ポートの欄に「0xff」と設定される。出力ポートとして「0xff」が設定されたノードを転送先（ＤＬＩＤ）とするパケットは、スイッチ２１において破棄される。一般には、未使用のＬＩＤを転送先（ＤＬＩＤ）とする場合に、出力ポートとして「0xff」が設定される。
【００５４】
なお、図３にはスイッチ２１のハードウェア構成を示したが、他のスイッチ２２〜３２のハードウェア構成も図３と同様である。また、図４にはスイッチ２１内のＦＤＢ６０のデータ構造例を示したが、他のスイッチ２２〜３２に格納されるＦＤＢのデータ構造も同様である。
【００５５】
次に、ネットワーク管理装置１００の機能を詳細に説明する。
図５は、ネットワーク管理装置のハードウェア構成例を示す図である。ネットワーク管理装置１００は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ（Random Access Memory）１０２と複数の周辺機器が接続されている。
【００５６】
ＲＡＭ１０２は、ネットワーク管理装置１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。
【００５７】
バス１０８に接続されている周辺機器としては、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７がある。
【００５８】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、ネットワーク管理装置１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００５９】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００６０】
入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００６１】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００６２】
通信インタフェース１０７は、通信ケーブルを介してスイッチ２８に接続されている。通信インタフェース１０７は、スイッチ２８を経由して、ネットワーク上の各スイッチ２１〜３２との間で制御パケットを用いたデータ通信を行う。
【００６３】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
図６は、ネットワーク管理装置の機能を示すブロック図である。ネットワーク管理装置１００は、結線情報記憶部１１０、ＦＤＢ記憶部１２０、障害検知部１３０、経路生成部１４０、ＦＤＢ配布順序決定部１５０、およびＦＤＢ配布処理部１６０を有している。
【００６４】
結線情報記憶部１１０は、ネットワークにおけるスイッチ２１〜３２間の通信ケーブルによる接続状況を示す結線情報の記憶機能である。例えばＲＡＭ１０２またはＨＤＤ１０３の記憶領域の一部が、結線情報記憶部１１０として使用される。
【００６５】
ＦＤＢ記憶部１２０は、各スイッチに配布するＦＤＢを記憶する記憶機能である。例えばＲＡＭ１０２またはＨＤＤ１０３の記憶領域の一部が、ＦＤＢ記憶部１２０として使用される。
【００６６】
障害検知部１３０は、ネットワークの障害を検出する。例えば障害検知部１３０は、障害を検出したスイッチから障害を通知する制御パケットを受信し、その制御パケットの内容に基づいて、障害箇所を判断する。また障害検知部１３０は、定期的に各スイッチ２１〜３２に対して動作状況の通知要求を示す制御パケットを送信し、その応答内容によって障害箇所を判断する。障害検知部１３０は、スイッチ間の通信障害を検出すると、障害箇所の通信が不能となったことを、結線情報記憶部１１０に登録する。また障害検知部１３０は、障害を検出すると、障害の発生を経路生成部１４０に通知する。
【００６７】
経路生成部１４０は、ネットワーク上の各スイッチ２１〜３２に接続されたノードごとに、そのノードを送信先とするパケットの転送経路を示す経路情報を生成する。例えば経路生成部１４０は、障害検知部１３０から障害が発生した旨の通知を受け取ると、結線情報記憶部１１０に格納されたスイッチ間の結線情報と、スイッチ間の通信障害の発生状況とを判断する。次に経路生成部１４０は、正常に通信できる伝送路を経由する経路情報を生成する。経路生成部１４０は、生成した経路情報に基づいて、各スイッチの更新用のＦＤＢを作成する。そして、経路生成部１４０は、作成したＦＤＢをＦＤＢ記憶部１２０に格納する。この際、スイッチ２１〜３２に既に配布済みのＦＤＢは、経路の初期状態の判断用にＦＤＢ記憶部１２０から削除されずに残される。
【００６８】
ＦＤＢ配布順序決定部１５０は、経路生成部１４０によって更新後の経路が生成され、その経路に応じた新たなＦＤＢが作成されると、スイッチ２１〜３２ごとに作成されたＦＤＢの配布順序を決定する。具体的には、ＦＤＢ配布順序決定部１５０は、ノードを１つ選択し、結線情報記憶部１１０とＦＤＢ記憶部１２０とを参照して、現在の経路でパケットが到達可能な経路（到達可能経路）を判断する。次にＦＤＢ配布順序決定部１５０は、到達可能経路上のスイッチに隣接するスイッチを、選択したノードに関するＦＤＢ配布対象としてＦＤＢ配布処理部１６０に通知する。その後、ＦＤＢ配布処理部１６０によりＦＤＢの配布が行われると、ＦＤＢ配布順序決定部１５０は、到達可能経路を再度判断し、選択したノードにパケットが到達可能なスイッチに隣接するスイッチを順次ＦＤＢ配布対象とする。ＦＤＢ配布順序決定部１５０は、送信先のノードのＤＬＩＤとＦＤＢ配布対象として決定したスイッチの情報とを、ＦＤＢ配布処理部１６０に通知する。
【００６９】
ＦＤＢ配布処理部１６０は、ＦＤＢ配布対象のスイッチに対して、選択したノードを送信先とするパケットの出力ポートを示すＦＤＢを、制御パケットによって送信する。ＦＤＢ配布処理部１６０は、ＦＤＢを送信したスイッチからＦＤＢ更新完了の応答を受け取ると、その旨をＦＤＢ配布順序決定部１５０に伝える。
【００７０】
次に、結線情報記憶部１１０内の結線情報について説明する。
図７は、結線情報のデータ構造例を示す図である。結線情報記憶部１１０には、結線情報１１１が格納されている。結線情報１１１には、複数のスイッチ管理情報１１１ａ〜１１１ｌが含まれている。各スイッチ管理情報１１１ａ〜１１１ｌは、スイッチＩＤ（ＳＷ  ＩＤ）、各ポートのポート番号（ポート＃）、各ポートの状態、各ポートの接続先の情報が設定されている。
【００７１】
各ポートの状態には、接続可能を示す状態と、接続不能を示す状態とが設定される。接続可能の状態は、図中、丸印で示されている。各ポートの接続先の情報としては、そのポートから通信ケーブルを介して接続されたスイッチのＩＤが設定される。
【００７２】
このような複数のスイッチ管理情報１１１ａ〜１１１ｌを有する結線情報１１１によって、図２に示したネットワークの接続関係がネットワーク管理装置１００で認識される。
次にＦＤＢ記憶部１２０に格納されているＦＤＢについて説明する。
【００７３】
図８は、ＦＤＢ記憶部のデータ構造例を示す図である。ＦＤＢ記憶部１２０には、スイッチ２１〜３２ごとのＦＤＢ１２１〜１２６，・・・が格納されている。各ＦＤＢは、ＤＬＩＤで６４個分のテーブルに別れている。各テーブルのデータ構造は、図４に示したスイッチ２１内のＦＤＢ６０と同様である。
【００７４】
以上のような構成のネットワーク管理装置１００により、ネットワーク上で障害が発生した際に、送信先ごとのパケットの経路情報が変更される。その際、ネットワーク管理装置１００は、ループが発生しないような適切な順番で各スイッチ２１〜３２にＦＤＢを配布する。
【００７５】
ところで、経路生成部１４０では、結線情報記憶部１１０内の結線情報１１１と、ＦＤＢ記憶部１２０内のＦＤＢ１２１〜１２６とに基づいて、経路情報を生成することができる。
【００７６】
図９は、経路情報の概念図である。経路情報７１，７２，・・・は、ＤＬＩＤごとに作成される。そして各経路情報７１，７２，・・・では、ＤＬＩＤで示されたノードを送信先とするパケットを、ネットワーク上の各スイッチ２１〜３２が、どの結線関係を介して転送すべきかが設定されている。図９の例では、経路情報７１内の丸で囲まれた文字が、各スイッチのＩＤを示している。そして、各スイッチからのパケットの転送先が矢印で示されている。パケットが転送されないが、結線関係が存在する経路は、線分で示されている。
【００７７】
このような経路情報７１，７２，・・・は、図７に示した結線情報１１１と、各スイッチのＦＤＢとを用いて構築できる。具体的には経路生成部１４０は、結線情報１１１に基づいて、スイッチ間の結線の有無を認識する。次に経路生成部１４０は、１つのＤＬＩＤを選択し、ＦＤＢ記憶部１２０内の各ＦＤＢから、選択したＤＬＩＤに対応する出力ポートを取得する。次に経路生成部１４０は、取得した出力ポートから結線された他のスイッチを、結線情報１１１に基づいて判断する。そして、経路生成部１４０は、選択したＤＬＩＤで示されるノードを送信先とするパケットの各スイッチにおける転送先を、経路情報に設定する。
【００７８】
現在運用中の状態を示す経路情報７１，７２，・・・は、例えばネットワーク管理装置１００が各スイッチ２１〜３２にＦＤＢを配布したとき、経路生成部１４０が作成し、ＲＡＭ１０２やＨＤＤ１０３に格納しておくことができる。経路情報７１，７２，・・・のデータ構造としては、例えば有向グラフのデータ形式を採用できる。また、ＦＤＢの配布順序を決定するときに、その都度、経路生成部１４０が更新前の結線情報１１１とＦＤＢ１２１〜１２６とに基づいて生成することもできる。
【００７９】
このような経路情報で示されるパケットの転送経路は、経路変更事由の発生に伴って変更される。
次に経路変更処理について詳細に説明する。
【００８０】
図１０は、第２の実施の形態に係る経路変更処理の手順を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。
［ステップＳ１１］障害検知部１３０は、経路変更事由発生の有無を判断する。例えば障害検知部１３０は、いずれかのスイッチから障害の発生を示す制御パケットを受信すると、経路変更事由が発生したものと判断する。なお、障害の発生を示す制御パケットには、障害を検知したスイッチのＩＤ、および障害により通信不能となったポートのポート番号が含まれている。また障害検知部１３０は、障害によって通信不能となっていた経路の通信が回復したこと（通信復旧）を示す制御パケットを受信した場合にも、経路変更事由が発生したものと判断する。経路変更事由が発生した場合、処理がステップＳ１２に進められる。障害が発生していなければ、ステップＳ１１の処理が繰り返される。
【００８１】
［ステップＳ１２］障害検知部１３０は、結線情報を更新する。例えば障害が発生した場合、障害検知部１３０は、結線情報記憶部１１０内の結線情報１１１から、障害により通信不能となった経路に接続されたスイッチのスイッチ管理情報を検索する。そして、障害検知部１３０は、該当するスイッチ管理情報の障害発生ポートの状態を、通信不能に設定する。
【００８２】
［ステップＳ１３］経路生成部１４０は、更新された結線情報に基づいて、パケットの送信先となるノードごとにパケットの転送経路を判断し、その転送経路に沿ったパケット転送を行うためのスイッチ２１〜３２ごとのＦＤＢを生成する。経路生成部１４０は、生成したＦＤＢを、ＦＤＢ記憶部１２０に追加格納する。その際、経路生成部１４０は、新たに作成したＦＤＢ（更新後ＦＤＢ）と、既にスイッチ２１〜３２に配布されているＦＤＢ（更新前）とを区別できるようにしておく。例えば、経路生成部１４０は、ＦＤＢに版数情報を付与することで、更新前後のＦＤＢを区別可能とすることができる。また、経路生成部１４０は、作成日時を示すタイムスタンプをＦＤＢに付与することで、更新前後のＦＤＢを区別可能とすることもできる。
【００８３】
［ステップＳ１４］ＦＤＢ配布順序決定部１５０とＦＤＢ配布処理部１６０とが連携して、各スイッチ２１〜３２のＦＤＢ更新指示を行う。この処理の詳細は後述する（図１３参照）。
【００８４】
次に、障害発生時の結線情報更新例について説明する。
図１１は、結線情報更新例を示す図である。図１１の例は、４箇所で障害が発生した場合である。１箇所目は、ＩＤ「Ａ」のスイッチ２１とＩＤ「Ｆ」のスイッチ２６との間である。２箇所目は、ＩＤ「Ｆ」のスイッチ２６とＩＤ「Ｈ」のスイッチ２８との間である。３箇所目は、ＩＤ「Ｉ」のスイッチ２９とＩＤ「Ｋ」のスイッチ３１との間である。４箇所目は、ＩＤ「Ｊ」のスイッチ３０とＩＤ「Ｌ」のスイッチ３２との間である。この場合、障害発生箇所の両端に接続されているスイッチの、障害発生箇所に接続されたポートの状態が「不能（図中、ばつ印で示す）」に変更されている。
【００８５】
障害発生により結線情報１１１が更新されると、経路生成部１４０によって更新後のパケットの転送経路が判断され、経路情報が生成される。
図１２は、更新後の経路情報の例を示す図である。パケットの送信先となるノードごとに、更新後の経路情報７１ａ，７２ａ，・・・が生成される。例えば、ＤＬＩＤ「０ｘ１」のノードに送信するパケットの更新前の経路情報７１（図９参照）と更新後の経路情報７１ａとを比較すると、４台のスイッチにおいてパケットの転送先が変更されている。具体的には、ＩＤ「Ｆ」のスイッチ２６におけるＤＬＩＤ「０ｘ１」のパケットの転送先は、ＩＤ「Ａ」のスイッチ２１からＩＤ「Ｇ」のスイッチ２７に変更されている。ＩＤ「Ｇ」のスイッチ２７におけるＤＬＩＤ「０ｘ１」のパケットの転送先は、ＩＤ「Ｆ」のスイッチ２６からＩＤ「Ｃ」のスイッチ２３に変更されている。ＩＤ「Ｈ」のスイッチ２８におけるＤＬＩＤ「０ｘ１」のパケットの転送先は、ＩＤ「Ｆ」のスイッチ２６からＩＤ「Ｇ」のスイッチ２７に変更されている。ＩＤ「Ｋ」のスイッチ３１におけるＤＬＩＤ「０ｘ１」のパケットの転送先は、ＩＤ「Ｉ」のスイッチ２９からＩＤ「Ｅ」のスイッチ２５に変更されている。ＩＤ「Ｌ」のスイッチ３２におけるＤＬＩＤ「０ｘ１」のパケットの転送先は、ＩＤ「Ｊ」のスイッチ３０からＩＤ「Ｋ」のスイッチ３１に変更されている。
【００８６】
このように更新後の経路情報が生成されると、更新後の経路情報に従ってパケットが伝送されるように、各スイッチ２１〜３２に対してＦＤＢ更新指示が出される。
図１３は、ＦＤＢ更新指示の処理手順を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。なお図１３に示した処理は、ネットワークを介してパケットの送信先となるノードごとに実行される。以下、ＦＤＢ更新の対象となっているノードを「対象ノード」と呼ぶ。
【００８７】
［ステップＳ２１］ＦＤＢ配布順序決定部１５０は、対象ノードの初期状態の経路情報を、現在の経路情報として設定する。ここで初期状態とは、ＦＤＢ配布前に各スイッチ２１〜３２に配布されているＦＤＢで示される運用中の経路情報である。
【００８８】
プログラム上では、例えば「curroute = initroute」という命令が実行される。ここで「curroute」は、現在の経路情報を示す変数である。「initroute」は、初期状態の経路情報を示す変数である。「＝」の記号は、左辺の変数に右辺の変数の値を代入することを意味する代入演算子である。
【００８９】
［ステップＳ２２］ＦＤＢ配布順序決定部１５０は、対象ノードに到達可能な経路を探索する。到達可能な経路探索処理の詳細は後述する（図１４、図１５参照）。
プログラム上では、例えば「reachroute = reachable(initroute, targetroute)」という命令が実行される。ここで、「reachable()」は、到達可能範囲探索用の関数である。「targetroute」は、更新後の経路情報を示す変数である。初期状態の経路情報「initroute」と更新後の経路情報「targetroute」とがパラメータとして指定された、関数「reachable()」がＦＤＢ配布順序決定部１５０で実行される。そして、ＦＤＢ配布順序決定部１５０により、処理結果が到達可能な経路情報を示す変数「reachroute」に代入される。
【００９０】
［ステップＳ２３］ＦＤＢ配布順序決定部１５０は、到達可能な経路に隣接するスイッチを探索する。この処理の詳細は後述する（図１７、図１８参照）。
プログラム上では、例えば「neighbors = searchneighbor(reachroute, targetroute)」という命令が実行される。ここで、「searchneighbor()」は、隣接スイッチ探索用の関数である。到達可能な経路情報「reachroute」と更新後の経路情報「targetroute」とがパラメータとして指定された関数「searchneighbor()」がＦＤＢ配布順序決定部１５０で実行される。その結果、隣接スイッチリストを示す変数「neighbors」に代入される。
【００９１】
［ステップＳ２４］ＦＤＢ配布処理部１６０は、隣接するスイッチへのＦＤＢ更新指示を行う。具体的には、ＦＤＢ配布処理部１６０は、経路生成部１４０から対象ノードに関する更新後の経路情報を取得する。次にＦＤＢ配布処理部１６０は、更新後の経路情報のうち、隣接するスイッチからのパケットの転送先を取得する。次にＦＤＢ配布処理部１６０は、結線情報記憶部１１０から、隣接するスイッチのスイッチ管理情報を取得し、更新後の経路情報に従ってパケットを転送する場合に、対象ノードへのパケットの出力先となるポートを判断する。次にＦＤＢ配布処理部１６０は、ＦＤＢ記憶部１２０から隣接するスイッチのＦＤＢを取得し、出力先となるポートの判断結果に基づいて、対象ノードのＤＬＩＤに対応する出力ポートを更新する。そしてＦＤＢ配布処理部１６０は、更新後のＦＤＢを含む制御パケットを、隣接するスイッチに送信する。その制御パケットには、スイッチ内のＦＤＢの更新指示が含まれている。
【００９２】
ＦＤＢの更新指示を含む制御パケットを受信したスイッチでは、その制御パケットに含まれるＦＤＢによって、内部のメモリ内のＦＤＢを更新する。更新が完了すると、スイッチは、更新完了の応答をネットワーク管理装置１００に返す。ＦＤＢ配布処理部１６０は、スイッチから更新完了の応答を受信すると、ＦＤＢ記憶部１２０内の隣接するスイッチのＦＤＢを更新すると共に、更新後のＦＤＢに基づいて現在の経路情報「curroute」を更新する。そして、ＦＤＢ配布処理部１６０は、更新完了をＦＤＢ配布順序決定部１５０に通知する。
【００９３】
［ステップＳ２５］ＦＤＢ配布順序決定部１５０は、隣接するスイッチを到達可能な経路に追加する。この処理の詳細は後述する（図２０参照）。
プログラム上では、例えば「addreachable(reachroute, neighbors)」という命令が実行される。ここで「addreachable()」は、到達可能な経路情報への隣接スイッチ追加用の関数である。到達可能な経路情報「reachroute」と隣接スイッチを示す情報「neighbors」とがパラメータとして指定された関数「addreachable()」がＦＤＢ配布順序決定部１５０で実行される。そしてＦＤＢ配布順序決定部１５０により、隣接スイッチを追加するという変更が施された到達可能な経路情報「reachroute」が生成される。この処理の詳細は後述する。
【００９４】
［ステップＳ２６］ＦＤＢ配布順序決定部１５０は、すべてのスイッチが到達可能となったか否かを判断する。具体的には、ＦＤＢ配布順序決定部１５０は、現在の経路情報と、更新後の経路情報とが一致している場合、すべてのスイッチが到達可能であると判断する。
【００９５】
プログラム上では、例えば「isallreachable(curroute, targetroute)」という命令が実行される。ここで「isallreachable()」は、パラメータとして入力された２つの経路情報の一致・不一致を判断する関数である。現在の経路情報「curroute」と更新後の経路情報「targetroute」とがパラメータとして指定された関数「isallreachable()」がＦＤＢ配布順序決定部１５０で実行される。
【００９６】
すべてのスイッチが到達可能であれば、処理が終了する。到達不能なスイッチが存在する場合、処理がステップＳ２３に進められる。
このようにして、到達可能な経路に隣接するスイッチから順に、ＦＤＢ更新指示を出すことができる。そして、ＦＤＢが更新されたスイッチを到達可能な経路に含め、隣接するスイッチを再探索することで、最終的に、すべてのスイッチに対するＦＤＢの更新指示が可能となる。
【００９７】
次に、対象ノードに到達可能な経路情報の生成処理について詳細に説明する。
図１４は、対象ノードに到達可能な経路探索処理の手順を示すフローチャートの前半である。以下、図１４に示す処理をステップ番号に沿って説明する。
【００９８】
［ステップＳ３１］ＦＤＢ配布順序決定部１５０は、各スイッチのＦＤＢに登録されている対象ノードのＬＩＤについて、更新前と更新後とのＦＤＢにおける出力ポートを比較する。次にＦＤＢ配布順序決定部１５０は、スイッチのＩＤをリストアップした到達経路判定テーブルを生成する。そしてＦＤＢ配布順序決定部１５０は、各スイッチのＦＤＢに登録されているパケットの転送先アドレス（ＤＬＩＤ）について、更新前後で出力ポートが一致している場合、リスト内の該当するスイッチのＩＤに一致フラグを立てる。
【００９９】
［ステップＳ３２］ＦＤＢ配布順序決定部１５０は、対象ノードに隣接するスイッチの情報を取得する。例えばＦＤＢ配布順序決定部１５０は、結線情報１１１を参照し、接続先として対象ノードのＬＩＤが設定されたポートを有するスイッチを、隣接するスイッチと判定する。そして、ＦＤＢ配布順序決定部１５０は、隣接するスイッチのＩＤを、変数「firstsw」に設定する。
【０１００】
［ステップＳ３３］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルを参照し、変数「firstsw」で示されるスイッチの一致フラグを確認する。一致フラグが立っていれば、処理がステップＳ３４に進められる。一致フラグが立っていなければ、到達可能な経路を生成できないため処理が終了する。
【０１０１】
［ステップＳ３４］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルにおける変数「firstsw」で示されるスイッチに対して、到達可能フラグを立てる。
［ステップＳ３５］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルにおける変数「firstsw」で示されるスイッチに対して、探索済みフラグを立てる。
【０１０２】
［ステップＳ３６］ＦＤＢ配布順序決定部１５０は、幅優先探索キューに変数「firstsw」に設定されているスイッチ情報（ＩＤ）を入力する。その後、処理がステップＳ４１（図１５参照）に進められる。
【０１０３】
図１５は、対象ノードに到達可能な経路探索処理の手順を示すフローチャートの後半である。以下、図１５に示す処理をステップ番号に沿って説明する。
［ステップＳ４１］ＦＤＢ配布順序決定部１５０は、幅優先探索キューからスイッチ情報を取り出す。ＦＤＢ配布順序決定部１５０は、取り出したスイッチ情報を、変数「cursw」に設定する。ここで、幅優先探索キューにスイッチ情報が存在し、スイッチ情報が取得できた場合、処理がステップＳ４２に進められる。幅優先探索キューが空であり、新たに取得すべきスイッチ情報が存在しない場合、処理が終了する。
【０１０４】
［ステップＳ４２］ＦＤＢ配布順序決定部１５０は、変数「cursw」で示されるスイッチに隣接するスイッチのＩＤを取得する。例えばＦＤＢ配布順序決定部１５０は、結線情報１１１を参照し、変数「cursw」で示されるスイッチに接続されている他のスイッチを探索する。ＦＤＢ配布順序決定部１５０は、探索により検出されたスイッチのＩＤのうち、未取得のＩＤを１つ取得する。そして、ＦＤＢ配布順序決定部１５０は、取得したＩＤを変数「nextsw」に設定する。ここで、未取得のＩＤが存在し、スイッチのＩＤが取得できた場合、処理がステップＳ４３に進められる。全てのＩＤが取得済みであり、新たに取得すべきＩＤが存在しない場合、処理がステップＳ４１に進められる。
【０１０５】
［ステップＳ４３］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルを参照し、変数「nextsw」で示されるスイッチの探索済みフラグを確認する。探索済みフラグが立っていれば、処理がステップＳ４２に進められる。探索済みフラグが立っていなければ、処理がステップＳ４４に進められる。
【０１０６】
［ステップＳ４４］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルを参照し、変数「nextsw」で示されるスイッチの一致フラグを確認する。一致フラグが立っていれば、処理がステップＳ４５に進められる。一致フラグが立っていなければ、処理がステップＳ４２に進められる。
【０１０７】
［ステップＳ４５］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルにおける変数「nextsw」で示されるスイッチに対して、到達可能フラグを立てる。
［ステップＳ４６］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルにおける変数「nextsw」で示されるスイッチに対して、探索済みフラグを立てる。
【０１０８】
［ステップＳ４７］ＦＤＢ配布順序決定部１５０は、幅優先探索キューに変数「nextsw」に設定されているスイッチ情報（ＩＤ）を入力する。その後、処理がステップＳ４２に進められる。
【０１０９】
このようにして、初期状態での対象ノードに到達可能な経路情報が生成される。具体的には、到達経路判定テーブルに到達可能な経路を示す情報が設定される。
図１６は、到達経路判定テーブルのデータ構造例を示す図である。到達経路判定テーブル１５１は、ＲＡＭ１０２の記憶領域内にＦＤＢ配布順序決定部１５０によって格納される。到達経路判定テーブル１５１は対象ノードに対応付けられており、その対象ノードのＬＩＤが設定されている。
【０１１０】
到達経路判定テーブル１５１には、スイッチＩＤ、一致フラグ、到達可能フラグ、および探索済みフラグの欄が設けられている。スイッチＩＤの欄には、ネットワーク上の各スイッチ２１〜３２のＩＤが設定される。
【０１１１】
一致フラグの欄には、対象ノードに関する更新前と更新後とのＦＤＢにおける出力ポートの比較結果が、スイッチごとに設定される。図１６の例では、一致フラグの欄の初期状態は「０」（フラグが立っていない）である。一致フラグを立てる場合、一致フラグの欄の値が「１」に変更される。
【０１１２】
到達可能フラグの欄には、対象ノードにパケットが到達可能か否かを示すフラグが、スイッチごとに設定される。図１６の例では、到達可能フラグの欄の初期状態は「０」（フラグが立っていない）である。到達可能フラグを立てる場合、到達可能フラグの欄の値が「１」に変更される。
【０１１３】
探索済みフラグの欄には、各種探索処理の実行時に、探索を行ったか否かを示すフラグが設定される。図１６の例では、探索フラグの欄の初期状態は「０」（フラグが立っていない）である。探索フラグを立てる場合、探索フラグの欄の値が「１」に変更される。
【０１１４】
なお図１６に示した到達経路判定テーブル１５１は、図９に示した経路情報７１から図１２に示した経路情報７１ａに移行するようなＦＤＢの更新を行う場合に、到達可能な経路探索を行った後の状態である。この到達経路判定テーブル１５１を参照すると、ＩＤが「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」、「Ｅ」の各スイッチ２１〜２５については、ＦＤＢを更新せずとも対象ノードにパケットが到達可能であることが分かる。
【０１１５】
到達可能な経路の初期状態が生成されると、次に隣接するスイッチの探索処理が実行される。
図１７は、隣接するスイッチの探索処理の手順を示すフローチャートの前半である。以下、図１７に示す処理をステップ番号に沿って説明する。なお、隣接するスイッチの探索処理の開始時には、到達経路判定テーブル１５１の探索フラグの欄は、すべて「０」に初期化される。
【０１１６】
［ステップＳ５１］ＦＤＢ配布順序決定部１５０は、対象ノードに隣接するスイッチの情報を取得する。そして、ＦＤＢ配布順序決定部１５０は、隣接するスイッチのＩＤを、変数「firstsw」に設定する。
【０１１７】
［ステップＳ５２］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブルを参照し、変数「firstsw」で示されるスイッチの到達可能フラグを確認する。到達可能フラグが立っていれば、処理がステップＳ５３に進められる。到達可能フラグが立っていなければ、到達可能な経路を生成できないため処理が終了する。
【０１１８】
［ステップＳ５３］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１における変数「firstsw」で示されるスイッチに対して、探索済みフラグを立てる。
［ステップＳ５４］ＦＤＢ配布順序決定部１５０は、幅優先探索キューに変数「firstsw」に設定されているスイッチ情報（ＩＤ）を入力する。その後、処理がステップＳ６１（図１８参照）に進められる。
【０１１９】
図１８は、隣接するスイッチの探索処理の手順を示すフローチャートの後半である。以下、図１８に示す処理をステップ番号に沿って説明する。
［ステップＳ６１］ＦＤＢ配布順序決定部１５０は、幅優先探索キューからスイッチ情報を取り出す。ＦＤＢ配布順序決定部１５０は、取り出したスイッチ情報を、変数「cursw」に設定する。ここで、幅優先探索キューにスイッチ情報が存在し、スイッチ情報が取得できた場合、処理がステップＳ６２に進められる。幅優先探索キューが空であり、新たに取得すべきスイッチ情報が存在しない場合、処理が終了する。
【０１２０】
［ステップＳ６２］ＦＤＢ配布順序決定部１５０は、変数「cursw」で示されるスイッチに隣接するスイッチを探索する。ここで、隣接するスイッチとは、変数「cursw」で示されるスイッチに直接接続されるスイッチであり、かつ更新後のＦＤＢにおける出力ポートが変数「cursw」の方向となるスイッチである。ＦＤＢ配布順序決定部１５０は、探索により検出されたスイッチのＩＤのうち、未取得のＩＤを１つ取得する。そして、ＦＤＢ配布順序決定部１５０は、取得したＩＤを変数「nextsw」に設定する。ここで、未取得のＩＤが存在し、スイッチのＩＤが取得できた場合、処理がステップＳ６３に進められる。全てのＩＤが取得済みであり、新たに取得すべきＩＤが存在しない場合、処理がステップＳ６１に進められる。
【０１２１】
［ステップＳ６３］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１を参照し、変数「nextsw」で示されるスイッチの探索済みフラグを確認する。探索済みフラグが立っていれば、処理がステップＳ６２に進められる。探索済みフラグが立っていなければ、処理がステップＳ６４に進められる。
【０１２２】
［ステップＳ６４］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１を参照し、変数「nextsw」で示されるスイッチの到達可能フラグを確認する。到達可能フラグが立っており、到達可能であれば、処理がステップＳ６６に進められる。到達可能フラグが立っておらず、到達不能であれば、処理がステップＳ６５に進められる。
【０１２３】
［ステップＳ６５］ＦＤＢ配布順序決定部１５０は、変数「nextsw」に設定されているスイッチのＩＤを、隣接スイッチリスト「neighbors」に追加する。その後、処理がステップＳ６２に進められる。
【０１２４】
［ステップＳ６６］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１における変数「nextsw」で示されるスイッチに対して、探索済みフラグを立てる。
［ステップＳ６７］ＦＤＢ配布順序決定部１５０は、幅優先探索キューに変数「nextsw」に設定されているスイッチ情報（ＩＤ）を入力する。その後、処理がステップＳ６２に進められる。
【０１２５】
このようにして、到達経路に隣接するスイッチのＩＤが、隣接スイッチリストに登録される。
図１９は、隣接スイッチリストのデータ構造例を示す図である。隣接スイッチリスト１５２は、ＲＡＭ１０２の記憶領域内にＦＤＢ配布順序決定部１５０によって格納される。到達経路判定テーブル１５１は、パケットの転送先を示すＤＬＩＤに対応付けられており、そのＤＬＩＤが設定されている。また隣接スイッチリスト１５２には、現在の到達経路内のスイッチに隣接し、かつ到達経路に含まれていないスイッチのＩＤが登録されている。
【０１２６】
隣接スイッチリスト１５２がＦＤＢ配布処理部１６０に渡されると、ＦＤＢ配布処理部１６０により、隣接するスイッチに対して、対象ノードの更新後のＦＤＢが配布される。その後、ＦＤＢ配布順序決定部１５０により、隣接するスイッチが、到達可能な経路に追加される。
【０１２７】
次に隣接するスイッチを到達可能な経路に追加する処理について詳細に説明する。
図２０は、隣接するスイッチを到達可能な経路に追加する処理の手順を示すフローチャートである。以下、図２０に示す処理をステップ番号に沿って説明する。なお、隣接するスイッチを到達可能な経路に追加する処理の開始時には、到達経路判定テーブル１５１の探索フラグの欄は、すべて「０」に初期化される。
【０１２８】
［ステップＳ７１］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１における隣接スイッチリストに含まれるスイッチに対し、一致フラグと到達可能フラグを立てる。
【０１２９】
［ステップＳ７２］ＦＤＢ配布順序決定部１５０は、対象ノードに隣接するスイッチの情報を取得する。そして、ＦＤＢ配布順序決定部１５０は、隣接するスイッチのＩＤを、変数「firstsw」に設定する。
【０１３０】
［ステップＳ７３］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１における変数「firstsw」で示されるスイッチに対して、探索済みフラグを立てる。
［ステップＳ７４］ＦＤＢ配布順序決定部１５０は、幅優先探索キューに変数「firstsw」に設定されているスイッチ情報（ＩＤ）を入力する。
【０１３１】
［ステップＳ７５］ＦＤＢ配布順序決定部１５０は、幅優先探索キューからスイッチ情報を取り出す。ＦＤＢ配布順序決定部１５０は、取り出したスイッチ情報を、変数「cursw」に設定する。ここで、幅優先探索キューにスイッチ情報が存在し、スイッチ情報が取得できた場合、処理がステップＳ７６に進められる。幅優先探索キューが空であり、新たに取得すべきスイッチ情報が存在しない場合、処理が終了する。
【０１３２】
［ステップＳ７６］ＦＤＢ配布順序決定部１５０は、変数「cursw」で示されるスイッチに隣接するスイッチを探索する。ここで、隣接するスイッチとは、変数「cursw」で示されるスイッチに直接接続されるスイッチであり、かつ更新後のＦＤＢにおける出力ポートが変数「cursw」の方向となるスイッチである。ＦＤＢ配布順序決定部１５０は、探索により検出されたスイッチのＩＤのうち、未取得のＩＤを１つ取得する。そして、ＦＤＢ配布順序決定部１５０は、取得したＩＤを変数「nextsw」に設定する。ここで、未取得のＩＤが存在し、スイッチのＩＤが取得できた場合、処理がステップＳ７７に進められる。全てのＩＤが取得済みであり、新たに取得すべきＩＤが存在しない場合、処理がステップＳ７５に進められる。
【０１３３】
［ステップＳ７７］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１を参照し、変数「nextsw」で示されるスイッチの探索済みフラグを確認する。探索済みフラグが立っていれば、処理がステップＳ７６に進められる。探索済みフラグが立っていなければ、処理がステップＳ７８に進められる。
【０１３４】
［ステップＳ７８］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１を参照し、変数「nextsw」で示されるスイッチの一致フラグを確認する。一致フラグが立っていれば、処理がステップＳ７９に進められる。探索済みフラグが立っていなければ、処理がステップＳ７６に進められる。
【０１３５】
［ステップＳ７９］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１における変数「nextsw」で示されるスイッチに対して、到達可能フラグを立てる。
［ステップＳ８０］ＦＤＢ配布順序決定部１５０は、到達経路判定テーブル１５１における変数「nextsw」で示されるスイッチに対して、探索済みフラグを立てる。
【０１３６】
［ステップＳ８１］ＦＤＢ配布順序決定部１５０は、幅優先探索キューに変数「nextsw」に設定されているスイッチ情報（ＩＤ）を入力する。その後、処理がステップＳ７６に進められる。
【０１３７】
このように到達経路判定テーブル１５１が更新されることで、更新後のＦＤＢを配布したスイッチが、到達可能な経路に追加される。
図２１は、隣接するスイッチを到達可能な経路に追加後の到達経路判定テーブルの例を示す図である。図２１の例は、図１６に示した到達経路判定テーブル１５１の状態から、図１９に示した隣接スイッチリスト１５２に含まれるスイッチを、到達可能な経路に追加したものである。この場合、更新後の到達経路判定テーブル１５１では、隣接スイッチリスト１５２に含まれていたＩＤ「Ｇ」、「Ｋ」のスイッチ２７，３１について、一致フラグ、到達可能フラグ、および探索済みフラグが立てられている。またＩＤ「Ｉ」のスイッチ２９は、対象ノードへのパケットの転送先をＩＤ「Ｇ」のスイッチ２７としている。そのためＩＤ「Ｇ」のスイッチ２７が到達可能な経路に追加されていると同時に、ＩＤ「Ｉ」のスイッチ２９についても到達可能な経路に追加される。その結果、更新後の到達経路判定テーブル１５１では、ＩＤ「Ｉ」のスイッチ２９についても、一致フラグ、到達可能フラグ、および探索済みフラグが立てられている。
【０１３８】
更新後のＦＤＢを配布したスイッチを到達可能な経路に追加することで、到達可能な経路の範囲が広がる。到達可能な経路を広げた後に、到達可能な経路に隣接するスイッチの探索を行えば、前回の探索とは異なるスイッチが検出される。このように、ＦＤＢを配布したスイッチを到達可能な経路に追加しながら、到達可能な経路に隣接するスイッチの探索を行うことで、最終的には、ネットワーク上のすべてのスイッチに対して更新後のＦＤＢを配布することができる。
【０１３９】
以下、到達可能な経路の状態遷移に応じた隣接するスイッチの変遷について、ＦＤＢ配布周期ごとに説明する。ＦＤＢ配布周期とは、図１３に示すステップＳ２３〜Ｓ２５の処理の繰り返し周期である。
【０１４０】
図２２は、第１周期目のＦＤＢ配布時の到達可能な経路と隣接するスイッチを示す図である。図２２には、送信先のＤＬＩＤを「０ｘ１」とするパケットを転送するためのＦＤＢを更新する場合の経路情報７１ａ〜７１ｃが示されている。各経路情報７１ａ〜７１ｃは、スイッチが丸印で示されており、各スイッチからのパケットの転送方向が矢印で示されている。障害により通信不能となった経路には、ばつ印が示されている。
【０１４１】
図中右側には、最終状態の経路情報７１ａが示されている。図中左側には、初期状態の経路情報７１ｂが示されている。初期状態の経路情報７１ｂから最終状態の経路情報７１ａとなるように、各スイッチのＦＤＢが更新される。
【０１４２】
そのため、まず初期状態の経路情報７１ｂから、ＤＬＩＤ「０ｘ１」で指定されたノードにパケットが到達可能経路８１が探索される。図２２の例では、初期状態の経路情報７１ｂにおいて、ＩＤ「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」、「Ｅ」の各スイッチを含む経路が、到達可能経路８１となっている。次に到達可能経路８１に隣接するスイッチが探索される。図２２の例では、ＩＤ「Ｇ」、「Ｋ」、の各スイッチが検出されている。
【０１４３】
そこで、ＤＬＩＤ「０ｘ１」を送信先のノードとするパケットの転送に関する更新後のＦＤＢが、検出されたスイッチに配布される。例えば、ＩＤ「Ｇ」のスイッチには、ＩＤ「Ｂ」のスイッチに接続されたポートを出力ポートとするＦＤＢが配布される。またＩＤ「Ｋ」のスイッチには、ＩＤ「Ｅ」のスイッチに接続されたポートを出力ポートとするＦＤＢが配布される。
【０１４４】
ＦＤＢ配布の第１周期終了後の経路情報７１ｃでは、ＦＤＢを配布したスイッチについて、ＤＬＩＤ「０ｘ１」で指定されたノードにパケットを到達可能となる。
図２３は、第２周期目のＦＤＢ配布時の到達可能な経路と隣接するスイッチを示す図である。第２周期目では、ＦＤＢ配布の第１周期終了後の経路情報７１ｃから、ＤＬＩＤ「０ｘ１」で指定されたノードにパケットが到達可能経路８２が探索される。図２３の例では、経路情報７１ｃにおいて、ＩＤ「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」、「Ｅ」、「Ｇ」、「Ｉ」、「Ｋ」の各スイッチを含む経路が、到達可能経路８２となっている。次に到達可能経路８２に隣接するスイッチが探索される。図２３の例では、ＩＤ「Ｆ」、「Ｈ」、「Ｌ」の各スイッチが検出されている。
【０１４５】
そこで、ＤＬＩＤ「０ｘ１」を送信先のノードとするパケットの転送に関する更新後のＦＤＢが、検出されたスイッチに配布される。例えば、ＩＤ「Ｆ」のスイッチには、ＩＤ「Ｇ」のスイッチに接続されたポートを出力ポートとするＦＤＢが配布される。またＩＤ「Ｈ」のスイッチには、ＩＤ「Ｇ」のスイッチに接続されたポートを出力ポートとするＦＤＢが配布される。さらにＩＤ「Ｌ」のスイッチには、ＩＤ「Ｋ」のスイッチに接続されたポートを出力ポートとするＦＤＢが配布される。
【０１４６】
ＦＤＢ配布の第２周期終了後の経路情報７１ｄでは、新たにＦＤＢを配布したスイッチについても、ＤＬＩＤ「０ｘ１」で指定されたノードにパケットを到達可能となる。その結果、すべてのスイッチが到達可能となっている。
【０１４７】
このように到達可能経路に隣接するスイッチから順にＦＤＢを配布すれば、ＦＤＢの更新過程でループが発生することがない。その結果、経路変更事由が発生した場合であっても、信頼性の高い通信を継続しながら、パケットの転送経路の変更が可能となる。
【０１４８】
すなわち第２の実施の形態では、初期経路（initroute）と更新後の経路（targetroute）を比較し、一致している箇所のみが取り出される。そして、一致する経路のみで転送先アドレスで示されたノードに到達可能な範囲（reachroute）が特定される。到達可能な範囲が特定されると、到達不能なスイッチのうち、更新後の経路において到達可能な範囲に隣接するスイッチ（neighbors）の更新が行われる。当該スイッチが複数ある場合、どちらを先に更新してもよい。そしてＦＤＢの更新により到達可能になった範囲が新たに到達可能な範囲に加えられる。このような処理が、すべてのスイッチが到達可能となるまで繰り返される。
【０１４９】
このような処理によりループの発生が防止される。その理由は以下の通りである。
到達不能な範囲のスイッチのＦＤＢ更新によってループを発生させるためには、到達可能な範囲のスイッチから到達不能な範囲のスイッチへの転送が必要である。しかし、到達可能な範囲のスイッチは当該転送先アドレスへ向かうツリーを構成しており、到達不能な範囲へ転送される経路がない。このためループは発生しない。また、現在到達可能な経路は切断されない。なぜならば到達可能な範囲を操作していないためである。従って、ループの発生が防止されている。
【０１５０】
〔第３の実施の形態〕
次に第３の実施の形態について説明する。第３の実施の形態は、ＦＤＢ配布の高速化を図ったものである。
【０１５１】
ＦＤＢは、パケットの宛先となるノードのアドレス（ＤＬＩＤ）ごとに更新処理が行われる。更新処理回数は、最大で、「更新スイッチ数」×「転送先アドレス数」である。すなわち、仮に転送先アドレス数が６４であり、更新するスイッチ数が１０であれば、６４０の更新処理が必要である。
【０１５２】
ＦＤＢの構成によっては、複数の転送先アドレスに対する出力ポート情報をまとめて更新できるものがある。例えば、InfiniBand（商標）のＦＤＢは６４個の転送先アドレスごとに１つのテーブルから構成されている。この６４個を１度にまとめて更新できる。そこで、第３の実施の形態では、ＦＤＢ更新処理をまとめる機構を導入し、処理の高速化を図る。
【０１５３】
図２４は、第３の実施の形態に係るネットワーク管理装置の機能を示すブロック図である。ネットワーク管理装置２００は、結線情報記憶部２１０、ＦＤＢ記憶部２２０、障害検知部２３０、経路生成部２４０、ＦＤＢ配布順序決定部２５０、ＦＤＢまとめ処理部２６０、およびＦＤＢ配布処理部２７０を有している。このうち結線情報記憶部２１０、ＦＤＢ記憶部２２０、障害検知部２３０、経路生成部２４０、およびＦＤＢ配布処理部２７０については、第２の実施の形態の同名の要素と同様の機能であるため説明を省略する。
【０１５４】
ＦＤＢ配布順序決定部２５０は、ＤＬＩＤごとに各スイッチの更新の順番を示す半順序番号を生成する。半順序番号とは、各スイッチのＦＤＢを更新する順序を示した番号である。ただし、どちらを先に更新してもかまわない場合は同一の番号とする。
【０１５５】
ＦＤＢまとめ処理部２６０は、スイッチごとに更新順序番号が同じＤＬＩＤのＦＤＢの更新内容をまとめて、統合した１つのＦＤＢを作成する。
図２５は、第３の実施の形態に係る経路更新処理の手順を示すフローチャートである。以下、図２５に示す処理をステップ番号に沿って説明する。
【０１５６】
［ステップＳ１０１］障害検知部２３０は、経路変更事由発生の有無を判断する。この処理の詳細は、図１０に示したステップＳ１１と同様である。経路変更事由が発生した場合、処理がステップＳ１０２に進められる。障害が発生していなければ、ステップＳ１０１の処理が繰り返される。
【０１５７】
［ステップＳ１０２］障害検知部２３０は、結線情報を更新する。この処理の詳細は、図１０に示したステップＳ１２と同様である。
［ステップＳ１０３］経路生成部２４０は、更新された結線情報に基づいて、パケットの送信先となるノードごとにパケットの転送経路を判断し、その転送経路に沿ったパケット転送を行うためのスイッチ２１〜３２ごとのＦＤＢを生成する。この処理の詳細は、図１０に示したステップＳ１３と同様である。
【０１５８】
［ステップＳ１０４］ＦＤＢ配布順序決定部２５０は、半順序番号一覧表を作成する。この処理の詳細は後述する（図２６参照）。
［ステップＳ１０５］ＦＤＢまとめ処理部２６０とＦＤＢ配布処理部２７０とが連携して、各スイッチ２１〜３２のＦＤＢ更新指示を行う。この処理の詳細は後述する（図２８参照）。
【０１５９】
次に、半順序番号一覧表作成処理について詳細に説明する。
図２６は、半順序番号一覧表作成処理の手順を示すフローチャートである。以下、図２６に示す処理をステップ番号に沿って説明する。
【０１６０】
［ステップＳ１１１］ＦＤＢ配布順序決定部２５０は、対象ノードの初期状態の経路情報を、現在の経路情報として設定する。プログラム上では、例えば「curroute = initroute」という命令が実行される。この処理の詳細は、図１３のステップＳ２１と同様である。
【０１６１】
［ステップＳ１１２］ＦＤＢ配布順序決定部２５０は、対象ノードに到達可能な経路を探索する。到達可能な経路探索処理の詳細は後述する。プログラム上では、例えば「reachroute = reachable(initroute, targetroute)」という命令が実行される。この処理の詳細は、図１３のステップＳ２２と同様である。
【０１６２】
［ステップＳ１１３］ＦＤＢ配布順序決定部２５０は、次に設定する半順序番号を初期化する。プログラム上では、例えば「order=1」という命令が実行される。これは変数「order」に「１」の値を代入することを意味する。
【０１６３】
［ステップＳ１１４］ＦＤＢ配布順序決定部２５０は、ＦＤＢ配布順序決定部１５０は、到達可能な経路に隣接するスイッチを探索する。プログラム上では、例えば「neighbors = searchneighbor(reachroute, targetroute)」という命令が実行される。この処理の詳細は、図１７，図１８に示した処理と同様である。
【０１６４】
［ステップＳ１１５］ＦＤＢ配布順序決定部２５０は、半順序番号一覧表に、隣接するスイッチの半順序番号を設定する。すなわち、次に設定する半順序番号として保持されている数値を、ステップＳ１１３で検出された隣接するスイッチの半順序番号として、半順序番号一覧表に設定する。プログラム上では、例えば「savetotable(order, neighbors)」という命令が実行される。ここで「savetotable()」は、半順序番号一覧表へのデータの設定を行う関数である。次に設定する半順序番号「order」と隣接するスイッチのリスト「neighbors」とがパラメータとして指定された関数「savetotable()」がＦＤＢ配布順序決定部２５０で実行される。その結果、半順序番号一覧表内の隣接するスイッチに対応付けて、半順序番号が設定される。
【０１６５】
［ステップＳ１１６］ＦＤＢ配布順序決定部２５０は、次に設定する半順序番号をカウントアップする。プログラム上では、例えば「order++」という命令が実行される。これは変数「order」の値を１だけインクリメントすることを意味する。
【０１６６】
［ステップＳ１１７］ＦＤＢ配布順序決定部２５０は、隣接するスイッチを到達可能な経路に追加する。この処理の詳細は、図２０に示した処理と同様である。
［ステップＳ１１８］ＦＤＢ配布順序決定部２５０は、すべてのスイッチが到達可能となったか否かを判断する。具体的にはＦＤＢ配布順序決定部２５０は、すべてのスイッチが到達可能な経路に含まれる場合、すべてのスイッチが到達可能になったと判断する。プログラム上では、例えば「isallreachable2(reachroute)」という命令が実行される。ここで「isallreachable2()」は、パラメータとして入力された到達可能な経路に、すべてのスイッチが含まれるか否かを判断する関数である。
【０１６７】
すべてのスイッチが到達可能であれば、処理が終了する。到達不能なスイッチが存在する場合、処理がステップＳ１１４に進められる。
図２６に示したような処理がパケットの送信先となるすべてのノードに関して実行される。その結果、半順序番号一覧表が生成される。
【０１６８】
図２７は、半順序番号一覧表のデータ構造例を示す図である。半順序番号一覧表２５１では、マトリックス形式の表の各列にスイッチのＩＤが割り当てられ、各行に転送先アドレスが割り当てられている。行と列との交差する位置に、該当するスイッチと該当する転送先アドレスとの組に対応する半順序番号が設定されている。
【０１６９】
ところで、図２７に示した例において、同一のスイッチに送信すべき複数のＦＤＢを、すべてまとめ、１つのスイッチに対して１回のＦＤＢ配布で済ませようとすると、ループを発生させないようなＦＤＢ更新ができなくなる可能性がある。例えば、図２７に示すＩＤ「Ｂ」のスイッチとＩＤ「Ｃ」のスイッチに着目する。転送先アドレス「０ｘ１」に対応するＦＤＢは、ＩＤ「Ｂ」のスイッチの方がＦＤＢ配布順が先である。他方、転送先アドレス「０ｘ６」に対応するＦＤＢは、ＩＤ「Ｃ」のスイッチの方がＦＤＢ配布順が先である。すると、ＩＤ「Ｂ」のスイッチとＩＤ「Ｃ」のスイッチとのどちらに先にＦＤＢを配布すべきか決定できなくなる。このように、同一スイッチに転送すべきＦＤＢをすべてまとめてしまうと、各スイッチに付与された数値の集合をスイッチ間で比較しても順序関係を判別できない場合がある。そのため、半順序番号一覧表２５１で各スイッチに付与された数値の集合は、半順序関係となる。そこで、本実施の形態では、各スイッチに付与される数値を「半順序番号」と呼んでいる。
【０１７０】
このような半順序番号一覧表２５１がＦＤＢ配布順序決定部２５０により作成され、一次的にＲＡＭ１０２内の記憶領域に格納される。そして、ＦＤＢまとめ処理部２６０とＦＤＢ配布処理部２７０とが、半順序番号一覧表２５１を参照してＦＤＢの配布順を判断し、適宜ＦＤＢをまとめながら、各スイッチに対するＦＤＢ更新指示を行う。
【０１７１】
図２８は、ＦＤＢ更新指示の手順を示すフローチャートである。以下、図２８に示す処理をステップ番号に沿って説明する。
［ステップＳ１２１］ＦＤＢまとめ処理部２６０は、更新対象の半順序番号を示す変数「order」を「１」に初期化する。プログラム上では、例えば「order=1」という命令が実行される。
【０１７２】
［ステップＳ１２２］ＦＤＢまとめ処理部２６０は、すべてのスイッチそれぞれを処理対象として、ステップＳ１２３〜Ｓ１２５の処理を実行する。
［ステップＳ１２３」ＦＤＢまとめ処理部２６０は、半順序番号一覧表２５１を参照し、処理対象スイッチに設定された更新対象の半順序番号に対応する転送先アドレスを列挙する。プログラム上では、例えば「dests = searchfromorder(order)」という命令が実行される。ここで「searchfromorder()」は、入力されたパラメータと同じ値の半順序番号に対応する転送先アドレスを半順序番号一覧表から探索する。探索結果として得られた転送先アドレスが、変数「dests」に設定される。
【０１７３】
［ステップＳ１２４］ＦＤＢまとめ処理部２６０は、ステップＳ１２３で検出された転送先アドレスに対応する出力ポートの値を更新したＦＤＢを生成する。具体的には、ＦＤＢまとめ処理部２６０は、列挙されなかった転送先アドレスについては更新前の出力ポート番号を、列挙された転送先アドレスについては更新後の出力ポート番号を記述したＦＤＢを作成する。
【０１７４】
プログラム上では、例えば「tmpFDB = maketmpFDB(dests, initroute, targetroute)」という命令が実行される。maketmpFDB()は、部分的に更新したＦＤＢを作成する関数である。パラメータとして、変数「dests」、初期状態の経路情報「initroute」、最終状態の経路情報「targetroute」が入力される。関数「maketmpFDB()」では、変数「dests」で示される転送先アドレスそれぞれに関する初期状態の経路情報「initroute」と最終状態の経路情報「targetroute」とが比較され、処理対象スイッチにおける転送先アドレスごとの更新後の出力ポートが判定される。そして、変数「dests」で示される転送先アドレスの出力ポートを更新するＦＤＢが作成される。
【０１７５】
［ステップＳ１２５］ＦＤＢ配布処理部２７０は、処理対象のスイッチへのＦＤＢ更新指示を行う。具体的にはＦＤＢ配布処理部２７０は、ステップＳ１２４で生成したＦＤＢを含むＦＤＢ更新指示を、処理対象のスイッチに対して制御パケットにより送信する。
【０１７６】
［ステップＳ１２６］ＦＤＢまとめ処理部２６０は、すべてのスイッチに対してステップＳ１２３〜Ｓ１２５の処理を完了したら、処理をステップＳ１２７に進める。
［ステップＳ１２７］ＦＤＢまとめ処理部２６０は、更新対象の半順序番号の値をカウントアップする。プログラム上では、例えば「order++」という命令が実行される。これは、変数「order」の値を１だけインクリメントすることを意味する。
【０１７７】
［ステップＳ１２８］ＦＤＢまとめ処理部２６０は、更新対象の半順序番号が、半順序番号の最大値を超えたか否かを判断する。半順序番号の最大値とは、半順序番号一覧表に設定されている数値のうち、最も大きな値である。プログラム上では、例えば「order>maxorder」という判断処理が実行される。「maxorder」は、半順序番号の最大値を示す変数である。
【０１７８】
更新対象の半順序番号が最大値を超えた場合、処理が終了する。更新対象の半順序番号が最大値を超えていなければ、処理がステップＳ１２２に進められる。
このようにして、半順序番号が同じ転送先アドレスの出力ポートの変更内容を同時に反映させたＦＤＢを作成し、半順序番号の小さい順にＦＤＢを配布することで、ＦＤＢ更新途中でのループを発生させずに、効率的な更新が可能となる。
【０１７９】
次に図２９〜図３４を参照して、第３の実施の形態におけるＦＤＢ更新状況を具体的に説明する。
図２９は、ＤＬＩＤ「０ｘ１」宛のパケットの転送経路の初期状態と最終状態とを示す図である。初期状態の経路情報７１に示されるパケットの転送経路から、最終状態の経路情報７１ａに示される転送経路に変更するには、まずＩＤ「Ｇ」、「Ｋ」のスイッチの出力ポートが変更される。すると、これらのスイッチに関しては、ＤＬＩＤ「０ｘ１」を転送先アドレスとするパケットの半順序番号は「１」となる。次にＩＤ「Ｈ」、「Ｌ」のスイッチの出力ポートが変更される。すると、これらのスイッチに関しては、ＤＬＩＤ「０ｘ１」を転送先アドレスとするパケットの半順序番号は「２」となる。
【０１８０】
図３０は、ＤＬＩＤ「０ｘ２」宛のパケットの経路情報の初期状態と最終状態とを示す図である。初期状態の経路情報７２に示されるパケットの転送経路から、最終状態の経路情報７２ａに示される転送経路に変更するには、まずＩＤ「Ｂ」のスイッチの出力ポートが変更される。すると、このスイッチに関しては、ＤＬＩＤ「０ｘ２」を転送先アドレスとするパケットの半順序番号は「１」となる。次にＩＤ「Ａ」、「Ｇ」のスイッチの出力ポートが変更される。すると、これらのスイッチに関しては、ＤＬＩＤ「０ｘ２」を転送先アドレスとするパケットの半順序番号は「２」となる。次にＩＤ「Ｆ」、「Ｈ」、「Ｉ」のスイッチの出力ポートが変更される。すると、これらのスイッチに関しては、ＤＬＩＤ「０ｘ２」を転送先アドレスとするパケットの半順序番号は「３」となる。次にＩＤ「Ｊ」のスイッチの出力ポートが変更される。すると、これらのスイッチに関しては、ＤＬＩＤ「０ｘ２」を転送先アドレスとするパケットの半順序番号は「４」となる。
【０１８１】
図３１は、ＤＬＩＤ「０ｘ３」宛のパケットの経路情報の初期状態と最終状態とを示す図である。初期状態の経路情報７３に示されるパケットの転送経路から、最終状態の経路情報７３ａに示される転送経路に変更するには、まずＩＤ「Ｇ」のスイッチの出力ポートが変更される。すると、このスイッチに関しては、ＤＬＩＤ「０ｘ３」を転送先アドレスとするパケットの半順序番号は「１」となる。次にＩＤ「Ｆ」、「Ｈ」、「Ｉ」のスイッチの出力ポートが変更される。すると、これらのスイッチに関しては、ＤＬＩＤ「０ｘ３」を転送先アドレスとするパケットの半順序番号は「２」となる。次にＩＤ「Ｊ」のスイッチの出力ポートが変更される。すると、このスイッチに関しては、ＤＬＩＤ「０ｘ３」を転送先アドレスとするパケットの半順序番号は「３」となる。
【０１８２】
図３２は、転送先アドレスごとの半順序番号を示す図である。図３２の例では、各スイッチを表す丸印の横に、そのスイッチの半順序番号が示されている。このような転送先アドレスごとの半順序番号を集計することで、半順序番号一覧表が生成される。
【０１８３】
図３３は、半順序番号一覧表の例を示す図である。半順序番号一覧表２５２には、各スイッチにおける転送先アドレス（ＤＬＩＤ）ごとの半順序番号が登録されている。
ここでスイッチごとに半順序番号が同じ転送先アドレスの更新内容をまとめたＦＤＢが、半順序番号ごとに作成される。
【０１８４】
例えばＤＬＩＤ「Ｆ」のスイッチ２６であれば、半順序番号が「２」のＤＬＩＤ「０ｘ１」、「０ｘ３」に関する出力ポートの変更内容を含むＦＤＢと、半順序番号が「３」のＤＬＩＤ「０ｘ２」に関する出力ポートの変更内容を含むＦＤＢとが作成される。そして、作成されたＦＤＢが半順序番号の小さい順にスイッチ２６に送信される。
【０１８５】
図３４は、ＤＬＩＤ「Ｆ」のスイッチ内のＦＤＢの内容の遷移例を示す図である。スイッチ２６の更新前のＦＤＢ６１ａでは、ＤＬＩＤ「０ｘ１」宛のパケットの出力ポートの番号は「３」、ＤＬＩＤ「０ｘ２」宛のパケットの出力ポートの番号は「２」、ＤＬＩＤ「０ｘ３」宛のパケットの出力ポートの番号は「２」である。ここで、ＩＤ「Ｆ」のスイッチ２６以外のスイッチを対象としたＦＤＢ更新第１周期（半順序番号「１」のＦＤＢ更新）が完了した後、ＦＤＢ更新第２周期によるスイッチ２６を含む各スイッチへのＦＤＢ配信が行われる。
【０１８６】
スイッチ２６には、ＦＤＢ更新第２周期において、部分更新用のＦＤＢ６１ｂが配信される。そのＦＤＢ６１ｂがスイッチ２６に格納される。ＦＤＢ６１ｂでは、ＤＬＩＤ「０ｘ１」宛のパケットの出力ポートの番号が「１」に、ＤＬＩＤ「０ｘ３」宛のパケットの出力ポートの番号が「１」にそれぞれ変更されている。ＤＬＩＤ「０ｘ２」宛のパケットの出力ポートの番号は「２」のままである。
【０１８７】
さらにＦＤＢ更新第３周期において、部分更新用のＦＤＢ６１ｃが配信され、スイッチ２６に格納される。ＦＤＢ６１ｃでは、ＤＬＩＤ「０ｘ２」宛のパケットの出力ポートの番号は「１」に変更されている。
【０１８８】
このように、半順序番号が同じ転送先アドレスに関する出力ポートの変更用のＦＤＢは、１つにまとめられる。その結果、ＦＤＢの配信回数を削減することができる。例えば、図３３の例であれば、ＦＤＢ更新第１周期において、ＩＤ「Ｂ」、「Ｇ」、「Ｋ」の各スイッチにＦＤＢが配信される。すなわちＦＤＢ更新第１周期では、３回のＦＤＢ配信が行われる。ＦＤＢ更新第２周期において、ＩＤ「Ａ」、「Ｆ」、「Ｇ」、「Ｈ」、「Ｉ」、「Ｌ」の各スイッチにＦＤＢが配信される。すなわちＦＤＢ更新第２周期では、６回のＦＤＢ配信が行われる。ＦＤＢ更新第３周期において、ＩＤ「Ｆ」、「Ｈ」、「Ｉ」、「Ｊ」の各スイッチにＦＤＢが配信される。すなわちＦＤＢ更新第３周期では、４回のＦＤＢ配信が行われる。ＦＤＢ更新第４周期において、ＩＤ「Ｊ」のスイッチにＦＤＢが配信される。すなわちＦＤＢ更新第４周期では、１回のＦＤＢ配信が行われる。この結果、３＋６＋４＋１の計１４回のＦＤＢ配信によって、すべてのスイッチのＦＤＢ更新が完了する。
【０１８９】
ここで、ＦＤＢをまとめる処理を行わなかった場合、ＤＬＩＤ「０ｘ１」のＦＤＢ更新で５回、ＤＬＩＤ「０ｘ２」のＦＤＢ更新で７回、ＤＬＩＤ「０ｘ３」のＦＤＢ更新で５回のＦＤＢ配信が行われる。従って、まとめ処理を行わなければ、５＋７＋５の計１７回のＦＤＢ配信が行われる。
【０１９０】
このように、半順序番号が同じ場合、異なる転送先アドレスに関する出力ポートの変更内容を１つのＦＤＢにまとめることで、ＦＤＢの配信回数を削減できる。すなわち、まとめ処理を行わなければ、ＦＤＢの送信処理回数は最大で、「更新スイッチ数」×「ＤＬＩＤ数」である。他方、第３の実施の形態に示すようにまとめ処理を行えば、ＦＤＢの送信回数は最大でも「更新スイッチ数」×「最大半順序番号」となり、ＦＤＢの送信を大幅に削減できる。
【０１９１】
なお図３３の例では、説明を分かりやすくするため送信アドレスが３つの場合を想定しているが、転送先アドレス数が多くなるほど、ＦＤＢをまとめることによる処理効率の向上効果が大きくなる。しかも多数のスイッチを用いたコンピュータネットワークでは、通常大量のノードが接続されている。そのため、ＦＤＢをまとめることにより、ＦＤＢ更新処理効率を大幅に向上させることができる。
【０１９２】
しかも、半順序番号が同じ場合にのみＦＤＢをまとめるようにしたため、転送先アドレスごとに見た場合、ＦＤＢ更新過程でループを発生することがない。すなわち、第３の実施の形態によれば、ループを発生させずにＦＤＢを更新できるという高信頼性の確保と、ＦＤＢ配信回数を削減することによる処理効率の向上との両立が可能となる。
【０１９３】
〔その他の応用例〕
上記第２，第３の実施の形態では、障害発生時に自動的にＦＤＢを配信することを想定している。そのため、終了状態の経路情報についてもネットワーク管理装置１００，２００が作成している。しかし、経路変更事由には障害発生以外にも、例えば性能チューニングがある。性能チューニングでは、終了状態の経路情報を、管理者が任意に入力する場合もある。そのような場合、ネットワーク管理装置１００，２００は、任意に入力された経路情報を更新後の経路情報として、経路変更処理を実行する。
【０１９４】
上記第２，第３の実施の形態では、ノード間のデータ通信に利用される伝送路を介してＦＤＢを配布するため、ＦＤＢに依存せずに転送が可能な制御パケットを用いてＦＤＢを送信している。しかし、ノード間のデータ通信のネットワークとは別に、管理用のネットワークでネットワーク管理装置１００，２００と各スイッチ２１〜３２とを接続することもできる。この場合、ネットワーク管理装置１００，２００は、各スイッチに対して管理用のネットワークを介して、ノード間のデータ通信用のパケットのフォワーディングに用いるＦＤＢを配布する。
【０１９５】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、ネットワーク管理装置１００，２００が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。
【０１９６】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１９７】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１９８】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０１９９】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【０２００】
以上説明した実施の形態の主な技術的特徴は、以下の付記の通りである。
（付記１）  転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するネットワーク管理装置であるコンピュータに、
パケットの転送経路の変更を伴うイベントが発生すると、前記ネットワーク管理装置が記憶する前記通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手順と、
転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、前記到達可能な範囲以外の部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手順と、
前記ネットワーク管理装置が記憶する各転送情報を読み出し、前記到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを前記到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手順と、
変更した転送情報を、対応する通信装置に送信する送信手順と、
転送情報を変更したことによって、前記転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、前記到達可能な範囲に追加する追加手順と、
を実行させるためのネットワーク管理プログラム。
【０２０１】
（付記２）  前記経路更新手順では、パケットの転送経路の変更を伴う前記イベントとして、前記通信装置の出力ポートのいずれかが通信不可能であることを示す情報を、前記通信装置から受信すると、前記ネットワーク管理装置が記憶する前記通信装置ごとの転送情報から得られる経路を、前記通信不可能な出力ポートを経由せずにパケット転送が可能となるように更新する付記１記載のネットワーク管理プログラム。
【０２０２】
（付記３）  前記コンピュータに、
前記追加手順の後に、前記通信装置の少なくとも１つが前記到達可能な範囲外にあれば、前記特定手順と前記変更手順と前記送信手順と前記追加手順とを実行させる、
ための付記１記載のネットワーク管理プログラム。
【０２０３】
（付記４）  前記コンピュータは、転送先アドレスと通信装置の識別子との組と、転送情報の転送順序を示す順序番号との対応関係を示す順序番号情報を記憶し、
前記コンピュータに、
転送先アドレスごとに、前記特定手順、前記変更手順、および前記追加手順を繰り返し行い、同一回の前記変更手順で到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にあると判定された通信装置の順序番号として同じ値を、前記順序番号情報に記憶させる順序番号生成手順を更に実行させ、
前記送信手順は、通信装置ごとの順序番号が同じ複数の転送先アドレスに対応する転送情報の出力ポートの変更内容をまとめた１つの転送情報を送信する、
付記１乃至３記載のネットワーク管理プログラム。
【０２０４】
（付記５）  前記順序番号生成手順は、転送先アドレスごとの前記変更手順の実行回数が増えるごとに、前記変更手順で到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にあると判定された通信装置の順序番号の値を大きくし、
前記送信手順は、小さい値の順序番号が対応付けられた転送先アドレスと通信装置の識別子との組ほど、当該組に含まれる通信装置への転送情報の転送を先に実行することを特徴とする付記４記載のネットワーク管理プログラム。
【０２０５】
（付記６）  転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するネットワーク管理装置であって、
パケットの転送経路の変更を伴うイベントが発生すると、前記ネットワーク管理装置が記憶する前記通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手段と、
転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、前記到達可能な範囲以外の部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手段と、
前記ネットワーク管理装置が記憶する各転送情報を読み出し、前記到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを前記到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手段と、
変更した転送情報を、対応する通信装置に送信する送信手段と、
転送情報を変更したことによって、前記転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、前記到達可能な範囲に追加する追加手段と、
を有するネットワーク管理装置。
【０２０６】
（付記７）  転送先アドレスと通信装置の識別子との組と、転送情報の転送順序を示す順序番号との対応関係を示す順序番号情報を記憶する記憶手段と、
転送先アドレスごとに、前記特定手段、前記変更手段、および前記追加手段が処理を繰り返し実行し、前記変更手段における同一回の処理で到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にあると判定された通信装置の順序番号として同じ値を、前記順序番号情報に記憶させる順序番号生成手段とを更に有し、
前記送信手段は、通信装置ごとの順序番号が同じ複数の転送先アドレスに対応する転送情報の出力ポートの変更内容をまとめた１つの転送情報を送信する、
付記６記載のネットワーク管理装置。
【０２０７】
（付記８）  転送先アドレスと出力ポートとの対応関係を示す転送情報に基づいてパケット転送を行う複数の通信装置を、管理するコンピュータが、
パケットの転送経路の変更を伴うイベントが発生すると、前記コンピュータが記憶する前記通信装置ごとの転送情報から得られる経路を、異なる経路に更新する経路更新手順と、
転送先アドレスで示された情報処理装置に隣接する通信装置を含み、更新前の経路と更新後の経路との一致する部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達可能な範囲として特定し、前記到達可能な範囲以外の部分経路を、前記転送先アドレスで示された情報処理装置にパケットが到達不可能な範囲として特定する特定手順と、
前記コンピュータが記憶する各転送情報を読み出し、前記到達可能な範囲内にある通信装置に隣接する前記到達不可能な範囲内にある通信装置の転送情報の出力ポートを、パケットを前記到達可能な範囲にある通信装置に転送できるように、読み出した転送情報を変更する変更手順と、
変更した転送情報を、対応する通信装置に送信する送信手順と、
転送情報を変更したことによって、前記転送先アドレスで示された情報処理装置にパケットが新たに到達可能となる範囲を、前記到達可能な範囲に追加する追加手順と、
を実行するネットワーク管理方法。
【符号の説明】
【０２０８】
１  ネットワーク管理装置
１ａ  経路更新手段
１ｂ  特定手段
１ｃ  変更手段
１ｄ  送信手段
１ｅ  追加手段
２ａ〜２ｌ  通信装置
３  情報処理装置
４ａ，４ｂ  経路
５ａ，５ｂ  到達可能な範囲
６ａ〜６ｅ  転送情報
【図１】
2011029975.tif 000003
【図２】
2011029975.tif 000004
【図３】
2011029975.tif 000005
【図４】
2011029975.tif 000006
【図５】
2011029975.tif 000007
【図６】
2011029975.tif 000008
【図７】
2011029975.tif 000009
【図８】
2011029975.tif 000010
【図９】
2011029975.tif 000011
【図１０】
2011029975.tif 000012
【図１１】
2011029975.tif 000013
【図１２】
2011029975.tif 000014
【図１３】
2011029975.tif 000015
【図１４】
2011029975.tif 000016
【図１５】
2011029975.tif 000017
【図１６】
2011029975.tif 000018
【図１７】
2011029975.tif 000019
【図１８】
2011029975.tif 000020
【図１９】
2011029975.tif 000021
【図２０】
2011029975.tif 000022
【図２１】
2011029975.tif 000023
【図２２】
2011029975.tif 000024
【図２３】
2011029975.tif 000025
【図２４】
2011029975.tif 000026
【図２５】
2011029975.tif 000027
【図２６】
2011029975.tif 000028
【図２７】
2011029975.tif 000029
【図２８】
2011029975.tif 000030
【図２９】
2011029975.tif 000031
【図３０】
2011029975.tif 000032
【図３１】
2011029975.tif 000033
【図３２】
2011029975.tif 000034
【図３３】
2011029975.tif 000035
【図３４】
2011029975.tif 000036