(57)【要約】【課題】本発明は、全ノード間のパスが一致するＥＣＴを維持したまま、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることを目的とする。【解決手段】本発明に係るノード２１は、複数のノードが接続された通信ネットワークを構成するノードであって、各ノードの所属するエリア情報、自己と共通のエリアに所属する各ノードの物理リンクの状態を表すリンクステート情報、及び自己の所属するエリア内における自己のノードから各ノードへの経路を定めたツリー情報を格納するトポロジ情報データベース２３と、トポロジ情報データベース２３に格納されているリンクステート情報が更新されると、更新後のリンクステート情報に基づいて、自己のノードから自己の所属するエリア内における各ノードへの経路を定めたツリー情報を生成するツリー再設定部として機能するパス設定管理部２４と、を備える。【選択図】図２
2015154287.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードが接続された通信ネットワークであって、
前記複数のノードは、
予め設定されたいずれかのエリアに所属し、
前記複数のノードのうちの隣接するいずれかのノード間の物理リンクに障害が発生したとき、障害発生リンクの情報及び障害発生エリアの情報を互いに共有し、
前記複数のノードのうちの前記障害発生エリアに所属する各ノードは、
前記障害発生リンクの情報に基づき、自己のノードから前記障害発生エリア内における各ノードへの経路を定めたツリー情報を生成する
通信ネットワーク。
【請求項２】
前記複数のノードのうちの隣接するエリアの境界に配置されるノードは、
隣接する両方のエリアに所属し、
前記複数のノードのうちの前記障害発生エリアのみに所属する各ノードが前記ツリー情報を生成したときに、エリア間を接続するノードが他のノードから自己のノードに変更になった場合に、前記障害発生リンクの情報に基づき、自己のノードから前記障害発生エリアに隣接するエリア内における各ノードへの経路を定めたツリー情報を生成する
ことを特徴とする請求項１に記載の通信ネットワーク。
【請求項３】
複数のノードが接続された通信ネットワークを構成する前記ノードであって、
各ノードの所属するエリア情報、自己と共通のエリアに所属する各ノードの物理リンクの状態を表すリンクステート情報、及び自己の所属するエリア内における自己のノードから各ノードへの経路を定めたツリー情報を格納するトポロジ情報データベースと、
前記トポロジ情報データベースに格納されている前記リンクステート情報が更新されると、更新後の前記リンクステート情報に基づいて、自己のノードから自己の所属するエリア内における各ノードへの経路を定めたツリー情報を生成するツリー再設定部と、
を備えるノード。
【請求項４】
自己のノードが接続されているノードとの通信断を検出すると、前記トポロジ情報データベースに格納されている自己のリンクステート情報を通信断の発生後の状態に更新し、通信断の発生個所を特定可能な障害発生リンクの情報を自己に接続されている各ノードへ送信するリンクステート情報設定部と、
自己に接続されているいずれかのノードから前記障害発生リンクの情報を受信すると、前記トポロジ情報データベースに格納されている当該ノードに関する前記リンクステート情報を通信断の発生後の状態に更新するリンクステート情報更新部と、
自己に接続されているいずれかのノードから前記障害発生リンクの情報を受信すると、受信した前記障害発生リンクの情報を、受信元のノードとは異なるノードへ転送するリンクステート情報転送部と、
をさらに備える請求項３に記載のノード。
【請求項５】
複数のノードが接続された通信ネットワークにおける経路設定方法であって、
前記複数のノードに備わるメモリに、各ノードの所属するエリア情報を予め記憶させておき、
前記複数のノードが、前記複数のノードのうちの隣接するいずれかのノード間のリンクに障害が発生したとき、障害発生リンクの情報及び障害発生エリアの情報を共有する通知手順と、
前記複数のノードのうちの前記障害発生エリアに所属する各ノードが、前記障害発生リンクの情報に基づき、前記障害発生エリア内における自己のノードから各ノードへの経路を定めたツリー情報を生成するツリー生成手順と、
を順に有する通信ネットワークにおける経路設定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークおよびノードに関する。
【背景技術】
【０００２】
パケット転送通信ネットワークでは、パケット転送通信ネットワークを構成するノードがネットワークのトポロジについて自律的に学習し、その情報を基にパケットの転送経路（パス）を算出および決定することができる。主にパス選択の判断基準として用いられるものはパスのコストであり、パスのコストは、ノード間のホップ数、またはノードを接続するリンクの帯域幅などのメトリクス、またはこれらの両方により特定することができる。ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）やＩＳ−ＩＳ（Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ−ｔｏ−Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ）はパケット転送通信ネットワークにおいて、リンクステート型ルーティングプロトコルとして広く利用されており、各ノードのパスのコストの広告（アドバタイズメント）によりノード間でネットワークのトポロジを共有し、ダイクストラアルゴリズムを用いて最短パスを確立する。
【０００３】
リンクステート型ルーティングプロトコルは主にＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）によるパケット転送通信ネットワークに利用されるが、ＩＳ−ＩＳの拡張により、ＳＰＢ（Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｂｒｉｄｇｅ）やＴＲＩＬＬ（Ｔｒａｎｓｐａｒｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  ｏｆ  Ｌｏｔｓ  ｏｆ  Ｌｉｎｋｓ）といった、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）層での利用の拡張が行われている（非特許文献１及び２参照）。
【０００４】
広域イーサネット（登録商標）などの大規模ネットワークを運用する場合には、故障時の運用パスの把握や、帯域制御を容易とするために、パケット転送パスの往復パスを一致させる必要がある。ダイクストラアルゴリズムを用いたＥＣＴ（Ｅｑｕａｌ  Ｃｏｓｔ  Ｔｒｅｅ）は、パケット転送パスを一致させる技術の一つである。自身のノードから全てのノードへの最短パスの集合（ツリー）を生成し、特定ノードへのパスが複数ある場合は、ノードに設定されているＩＤ等により、パスを識別し、それに合わせてツリーも複数生成する。このとき、タイブレークアルゴリズムにより、複数のツリーから１つを選択することで、全てのノード間におけるパスおよびツリーを一致させる。タイブレークアルゴリズムでは、例えば、ノードに設定されているＩＤの合計が最小、または最大となるツリーというように、ツリーを識別するアルゴリズムを複数用意する。その後、優先度の高いアルゴリズムを１つ選択することで、ツリーを一意的に定める。全てのノードにおいて、同じネットワークトポロジ情報を持ち、同じＥＣＴを用いてツリーを生成し、同じ優先度のツリー識別アルゴリズムを実行するため、全てのノード間におけるパスは一致する。
【０００５】
ＥＣＴを使用したパケット転送通信ネットワークでは、ネットワークトポロジに変化が生じた場合、全ノードへネットワークトポロジ等の情報を含んだリンクステート情報が共有され、その情報を基に各ノードは全ノードに対する最短パスの集合であるツリーを計算する。このツリー計算時間がネットワークのノード数及びリンク数の増加に伴い大きくなるため、故障発生時における最短パス切替時間も大きくなるという課題がある。
【０００６】
前記課題を解決するために、例えばＩＳ−ＩＳでは、ネットワーク全体を、レベル１のノードで形成されたエリアと、複数のエリアを繋ぐレベル２のノードに分けた階層型ルーティングを実行することで、故障等の影響を受けるノード数を小さくする。宛先が転送元ノードと同一エリア内で実行するレベル１ルーティングと、エリア間をルーティングするレベル２ルーティングを合わせて、ネットワーク全体でパケットを転送する。しかし、ＩＳ−ＩＳのようにエリアを分けてルーティングを実行した場合、各ノード間のパスが一致しないことがあるため、ＥＣＴを使用することができない。図１を用いて、ＩＳ−ＩＳを用いた階層型ルーティングを適用した時の各ノード間のパスが一致しない状態の概略を示す。
【０００７】
図１のように構成されたネットワークは、各ノードのＩＤが１から１７のノードで、すべてのリンクのコストが等しいとする。ノード間をつなぐ細い線は物理リンクを示し、ノード間をつなぐ太い線は論理リンクを示す。ノードＩＤ１〜６はエリアＡに、ノードＩＤ７〜１１はエリアＢに、ノードＩＤ１２〜１７はエリアＣに、属している。ノードＩＤ１、２、３、１５、１６、１７はレベル１のノード、ノードＩＤ４〜１４はレベル２のノードである。ここで、最短パスが複数ある場合、設定されているＩＤが最小となるアルゴリズムを採用しているものとする。ノードＩＤ１からノードＩＤ１７への最短パスは、ノードＩＤ１７がノードＩＤ１のエリアＡの外であるエリアＣにあるため、まずノードＩＤ１から最小コストのパスとなるエリアＡ内のレベル２のノードであるノードＩＤ４を経由し、同様にノードＩＤ４から最小コストのパスとなるエリアＣのレベル２のノードであるノードＩＤ１２を、ノードＩＤ６、９を経由して通過し、エリアＣ内でレベル１ルーティングを実行、ノード１４を経て、ノードＩＤ１７へ到達する。一方、ノードＩＤ１７からＩＤノード１への最短パスは、ノードＩＤ１７のエリアＣの外であるエリアＡにあるため、まずノードＩＤ１７から最小コストのパスとなるエリアＣ内のレベル２のノードであるノードＩＤ１４を経由し、同様にノードＩＤ１４から最小コストのパスとなるエリアＣのレベル２のノードであるノードＩＤ６へ、ノードＩＤ１１、８を経由して通過し、エリアＡ内でレベル１ルーティングを実行、ノードＩＤ３を経て、ノード１へ到達する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】ＩＥＥＥ  ８０２．１ａｑ，  Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ  （ＭＡＣ）  Ｂｒｉｄｇｅｓ  ａｎｄ  Ｖｉｒｔｕａｌ  Ｂｒｉｄｇｅｄ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ−Ａｍｅｎｄｍｅｎｔ  ２０：Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｂｒｉｄｇｉｎｇ，２０１２
【非特許文献２】ＩＥＴＦ  ＲＦＣ５５５６，Ｔｒａｎｓｐａｒｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  ｏｆ  Ｌｏｔｓ  ｏｆ  Ｌｉｎｋｓ（ＴＲＩＬＬ）：Ｐｒｏｂｌｅｍ  ａｎｄ  Ａｐｐｌｉｃａｂｉｌｉｔｙ  Ｓｔａｔｅｍｅｎｔ
【発明の概要】
【発明が解決しようとする課題】
【０００９】
前記のように、ＩＳ−ＩＳのようにエリアを分けてルーティングを実行した場合では、全てのノード間のパスが一致しない状態が発生する。このように、ＩＳ−ＩＳで用いるエリアを分けたルーティングとＥＣＴを組み合わせることはできないため、ツリー計算時間がネットワークのノード数及びリンク数の増加に伴い大きくなると、ネットワークトポロジに変化が生じた場合における最短パスの切替時間も大きくなるという課題がある。
【００１０】
そこで、本発明は、全ノード間のパスが一致するＥＣＴを維持したまま、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ネットワークトポロジをエリアで分け、ネットワークトポロジに変化が生じた場合、ネットワークトポロジに変化の生じたエリアに所属するノードのリンクステート情報を更新し、更新後のリンクステート情報に基づいて当該エリア内のツリーを生成する。ここで、本発明では、エリアの境界に配置されたノードは両方のエリアに所属させ、当該ノードのリンクステート情報はエリアを接続するノードが変更にならなければ更新しないようにする。
【００１２】
具体的には、本発明に係る通信ネットワークは、
複数のノードが接続された通信ネットワークであって、
前記複数のノードは、
予め設定されたいずれかのエリアに所属し、
前記複数のノードのうちの隣接するいずれかのノード間の物理リンクに障害が発生したとき、障害発生リンクの情報及び障害発生エリアの情報を互いに共有し、
前記複数のノードのうちの前記障害発生エリアに所属する各ノードは、
前記障害発生リンクの情報に基づき、自己のノードから前記障害発生エリア内における各ノードへの経路を定めたツリー情報を生成する。
【００１３】
本発明に係る通信ネットワークでは、
前記複数のノードのうちの隣接するエリアの境界に配置されるノードは、
隣接する両方のエリアに所属し、
前記複数のノードのうちの前記障害発生エリアのみに所属する各ノードが前記ツリー情報を生成したときに、エリア間を接続するノードが他のノードから自己のノードに変更になった場合に、前記障害発生リンクの情報に基づき、自己のノードから前記障害発生エリアに隣接するエリア内における各ノードへの経路を定めたツリー情報を生成してもよい。
【００１４】
具体的には、本発明に係るノードは、
複数のノードが接続された通信ネットワークを構成する前記ノードであって、
各ノードの所属するエリア情報、自己と共通のエリアに所属する各ノードの物理リンクの状態を表すリンクステート情報、及び自己の所属するエリア内における自己のノードから各ノードへの経路を定めたツリー情報を格納するトポロジ情報データベースと、
前記トポロジ情報データベースに格納されている前記リンクステート情報が更新されると、更新後の前記リンクステート情報に基づいて、自己のノードから自己の所属するエリア内における各ノードへの経路を定めたツリー情報を生成するツリー再設定部と、
を備える。
【００１５】
本発明に係るノードでは、
自己のノードが接続されているノードとの通信断を検出すると、前記トポロジ情報データベースに格納されている自己のリンクステート情報を通信断の発生後の状態に更新し、通信断の発生個所を特定可能な障害発生リンクの情報を自己に接続されている各ノードへ送信するリンクステート情報設定部と、
自己に接続されているいずれかのノードから前記障害発生リンクの情報を受信すると、前記トポロジ情報データベースに格納されている当該ノードに関する前記リンクステート情報を通信断の発生後の状態に更新するリンクステート情報更新部と、
自己に接続されているいずれかのノードから前記障害発生リンクの情報を受信すると、受信した前記障害発生リンクの情報を、受信元のノードとは異なるノードへ転送するリンクステート情報転送部と、
をさらに備えてもよい。
【００１６】
具体的には、本発明に係る通信ネットワークにおける経路設定方法は、
複数のノードが接続された通信ネットワークにおける経路設定方法であって、
前記複数のノードに備わるメモリに、各ノードの所属するエリア情報を予め記憶させておき、
前記複数のノードが、前記複数のノードのうちの隣接するいずれかのノード間のリンクに障害が発生したとき、障害発生リンクの情報及び障害発生エリアの情報を共有する通知手順と、
前記複数のノードのうちの前記障害発生エリアに所属する各ノードが、前記障害発生リンクの情報に基づき、前記障害発生エリア内における自己のノードから各ノードへの経路を定めたツリー情報を生成するツリー生成手順と、
を順に有する。
【発明の効果】
【００１７】
本発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができるため、高速なパスの切替を行うことができる。
【図面の簡単な説明】
【００１８】
【図１】ＩＳ−ＩＳを用いたルーティングにＥＣＴを適用した場合の往路と復路の一例を示す。
【図２】本実施形態に係る転送ノードの一例を示す。
【図３】第一の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示す。
【図４】第二の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示す。
【図５】第三の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１及び３の間のリンクに障害が発生した後のノードＩＤ１、６、１１からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図６】第四の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は（ａ）における各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１及び３の間のリンクに障害が発生した後のノードＩＤ１７、１１、６からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図７】第五の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ３に障害が発生した後のノードＩＤ１、６、１１からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図８】第六の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は（ａ）における各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ３に障害が発生した後のノードＩＤ１７、１１、６からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図９】第七の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１１及び１４の間のリンクに障害が発生した後のノードＩＤ１、６、１１からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１０】第八の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は（ａ）における各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１１及び１４の間のリンクに障害が発生した後のノードＩＤ１７、１２、６からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１１】第九の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１４に障害が発生した後のノードＩＤ１、６、１１からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１２】第十の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は（ａ）における各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１４に障害が発生した後のノードＩＤ１７、１２、６からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１３】第十一の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ６に障害が発生した後のノードＩＤ１、７、１１からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１４】第十二の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は（ａ）における各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ６に障害が発生した後のノードＩＤ１７、１１、７からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１５】第十三の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１、６、１１からのツリーを示し、（ｂ）は各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１１に障害が発生した後のノードＩＤ１、６、１２からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【図１６】第十四の実施形態におけるパケット転送通信ネットワークの一例であり、（ａ）はノードＩＤ１７、１１、６からのツリーを示し、（ｂ）は（ａ）における各エリアのツリーを重ね合わせたツリーを示し、（ｃ）はノードＩＤ１１に障害が発生した後のノードＩＤ１７、１２、６からのツリーを示し、（ｄ）は（ｃ）における各エリアのツリーを重ね合わせたツリーを示す。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。なお、本発明は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本発明は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２０】
（本発明の概要）
［パケット通信ノードの実施形態］
図２は、本実施形態に係るノードの一例を示す。本実施形態に係るノード２１は、パケット転送通信ネットワークを構成する各ノードである。ノード２１は、リンクステート情報設定部２２と、トポロジ情報データベース２３と、パス設定管理部２４と、パケット転送部２５と、複数のポート２６−１〜２６−ｎを備える。パス設定管理部２４がツリー再設定部として機能し、パケット転送部２５がリンクステート情報更新部及びリンクステート情報転送部として機能する。
【００２１】
本実施形態に係るノードは、本実施形態に係る通信ネットワークにおける経路設定方法を実行する。本実施形態に係る通信ネットワークにおける経路設定方法は、エリア情報記憶手順と、通知手順と、ツリー生成手順と、順に有する。
エリア情報記憶手順では、各ノードに備わるメモリに、各ノードの所属するエリア情報を記憶させる。
通知手順では、複数のノードのうちのいずれかのノード間のリンクに障害が発生したとき、各ノードが、障害発生リンクの情報及び障害発生エリアの情報を共有する。
ツリー生成手順では、複数のノードのうちの障害発生エリアに所属する各ノードが、障害発生リンクの情報に基づき、障害発生エリア内における自己のノードから各ノードへの経路を定めたツリー情報を生成する。
【００２２】
リンクステート情報設定部２２はリンクステート情報を生成する。リンクステート情報は、他のノードとの物理リンクの状態を示す情報であり、例えば、自己のノード２１が接続されているノードの識別情報と、自己のノード２１が所属しているエリア情報と、を含む。自己のノードが接続されているノードの識別情報は、ポート２６−１〜２６−ｎに論理的に接続されている隣接のノードの識別情報及びポート情報の組み合わせである。リンクステート情報は、ポート２６−１〜２６−ｎに論理的に接続した場合のコスト値を含んでもよい。そして、リンクステート情報設定部２２は、生成したこれらの情報を、トポロジ情報データベース２３に共有するとともに、パケット転送部２５およびポート２６−１〜２６−ｎを経由して他の各ノードに共有する。所属するエリアはオペレータが決定したものを設定する。
【００２３】
ポート２６−１〜２６−ｎの接続先が故障したか、或いはポート２６−１〜２６−ｎの接続先とのリンクに障害発生したことによって、ポート２６−１〜２６−ｎのいずれかの接続先との通信が途絶えた場合、リンクステート情報設定部２２はこの通信断を検出し、これを契機に障害発生リンクの情報及び障害発生エリアの情報を生成する。障害発生リンクの情報は、通信断の発生個所を特定可能な情報である。例えば、ノードＩＤ１のポート２６−１が接続先との通信が途絶えた場合、障害発生リンクの情報は、自己のノードＩＤ１、通信断のあったポート２６−１のポート番号、及び接続先のノードＩＤ３を含む。障害発生エリアの情報は、自己のノードの所属するエリアを識別可能な情報である。
【００２４】
トポロジ情報データベース２３は、ノード２１が所属するエリア内の各ノードのリンクステート情報と、ネットワーク全体の各ノードが所属するエリアと、各エリアの優先度と、ノード２１が所属するエリア内の各ノードへのツリー情報と、ノード２１が所属するエリアから他のエリアへのツリー情報と、他のエリアへ接続するノードを記録している。ノード２１が所属しないエリアのノードのリンクステート情報がパケット転送部２５より共有された場合、そのノードの所属するエリアについてのみ抽出して記録する。
【００２５】
パス設定管理部２４は、ツリー再設定部として機能し、トポロジ情報データベース２３が記録しているリンクステート情報を基に、ノード２１が所属するエリア内の各ノードへのツリーの形成を行う。ツリーの形成は、各ノードで共通のＥＣＴを用いて生成する。本実施形態では、一例として、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用する場合について説明する。このとき、複数のツリーが形成された場合は、複数のツリーを個別に識別し、タイブレークアルゴリズムにより使用するツリーを複数の中から選択し、パケット転送時にパケット転送部２５に対し、ツリーを指定する。
【００２６】
また、ノード２１が所属するエリア内のネットワークのトポロジが変化した時、パス設定管理部２４は、トポロジ情報データベース２３が更新したリンクステート情報を基に、ノード２１が所属するエリア内の各ノードへのツリーを再形成する。このとき、リンクステート情報に記載されているノードと所属エリアの情報を基に、各エリアのネットワークトポロジを把握し、エリア内の各ノードへのツリーを形成する。また、エリア間のネットワークのトポロジが変化した時、パス設定管理部２４は、トポロジ情報データベース２３が更新したリンクステート情報を基に、エリア間のツリーを再形成する。
【００２７】
パケット転送部２５は、リンクステート情報更新部として機能し、ポートから受信したリンクステート情報をトポロジ情報データベース２３へ転送する。また、パケット転送部２５は、リンクステート情報設定部２２で生成されたリンクステート情報を、ポート２６を通して転送する。また、パケット転送部２５は、パス設定管理部２４から指定されたパスに従ってパケットを、リンクステート情報転送部として機能し、ポート２６を通して転送する。このパケットには、ポートから受信したリンクステート情報も含まれる。
【００２８】
またパケット転送部２５は、ポート２６において複数の同じパケットを受信した場合、トポロジ情報データベース２３のツリーを確認し、最短パスではない方を廃棄する。両方のパケットが最短パスの場合、トポロジ情報データベース２３のエリア優先度を確認し。優先度の低いエリアから転送されたパケットを廃棄する。
【００２９】
ポート２６は、リンクステート情報の送受信と、パケットの受信と、パス設定管理部２４よりパケット転送部２５を通して指定された最短パスに従ってパケットを転送する。
【００３０】
ノード２１が複数のエリアに所属し、所属する複数のエリア間を接続するノードとなる場合、リンクステート情報設定部２２は、前記機能に加え、パス設定管理部２４でツリー生成後、その条件となる送信元ノードとツリーの組み合わせをリンクステート情報に追記する。そして、リンクステート情報設定部２２は、その組み合わせを、トポロジ情報データベース２３に共有するとともに、パケット転送部２５およびポート２６を経由して他の各ノードに共有する。また、ノード２１が複数のエリアに所属する場合、パス設定管理部２４は、前記機能に加え、複数のエリア毎にツリーを形成する。
【００３１】
（第一の実施形態）
図３は、本発明におけるパケット転送通信ネットワークの第一の実施形態を示す図である。図３では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合に、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１から全ノードへの最短パスの集合であるツリーの例を示している。図３に示すパケット転送通信ネットワークは、ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図３（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図３（ｂ）は図３（ａ）の各エリアのツリーを重ね合わせたツリーを示している。
【００３２】
図３（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【００３３】
図３（ｂ）に、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーを示す。ネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。
【００３４】
ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスである。この場合、ノードＩＤ１のパケット転送部２５は、ノードＩＤ３、６を経由するのではなく、ノードＩＤ４、７を経由するようにパケットを転送する。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスである。この場合、ノードＩＤ６のケット転送部２５は、ノードＩＤ８、１１を経由するのではなく、ノードＩＤ９、１２を経由するようにパケットを転送する。
【００３５】
（第二の実施形態）
図４は、本発明におけるパケット転送通信ネットワークの第二の実施形態を示す図である。図４では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合に、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１７から全ノードへの最短パスの例を示している。図４に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図４（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図４（ｂ）は図４（ａ）の各エリアのツリーを重ね合わせたツリーを示している。
【００３６】
図４（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【００３７】
図４（ｂ）に、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーを示す。ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。
【００３８】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、第１の実施形態と同じＥＣＴを用いてツリーを生成する。図４（ｂ）に示すノードＩＤ１７からノードＩＤ１への最短経路は、エリアを接続するノードが両エリアのネットワークトポロジを把握し、各エリアのツリーを組み合わせることで、より最適なツリーを生成することができるため、図３（ｂ）に示すノードＩＤ１からノードＩＤ１７へのパスと一致している。このため、実施形態１及び２に係る発明を用いることで、エリアを分けてルーティングを実行した場合であっても、ノード間のパスを一致させることができる。
【００３９】
（第三の実施形態）
本実施形態では、第一の実施形態においてツリーを作成した後に、最優先エリアのリンク間で故障が生じ、ネットワークのトポロジが変化した場合について説明する。図５は、本発明におけるパケット転送通信ネットワークの第三の実施形態を示す図である。図５では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１とノードＩＤ３の間のリンクで故障が発生した際の、ノードＩＤ１からのツリーに対する切替動作の例を示す図である。
【００４０】
図５に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図５（ａ）は、故障発生前のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図５（ｂ）は図５（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図５（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図５（ｄ）は図５（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００４１】
図５（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【００４２】
図５（ｂ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。ここまでは、実施形態１と同様である。
【００４３】
ノードＩＤ１とノードＩＤ３の間のリンクで故障が発生したとすると、通知手順において、ノードＩＤ１及びノードＩＤ３のリンクステート情報設定部２２は、エリアＡに所属するノードＩＤ１とノードＩＤ３の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。ノードＩＤ１は、リンクステート情報がエリアＡに所属するノードで生成されたことを確認する。一方で、エリアＢ、Ｃに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。ここで、エリアＡに所属するノードＩＤ６，７は、エリアＡのノードからエリアＢのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【００４４】
ノードＩＤ１〜５のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１〜５のパス設定管理部２４はエリアＡのツリーを再生成する。例えば、図５（ｃ）にあるように、ノードＩＤ１はエリアＡに所属するノードＩＤ４、２、５を経由する最短パスと、ノードＩＤ４、６、３を経由する最短パスと、ノードＩＤ４、７を経由する最短パスの集合であるツリーを再生成する。エリアＢ、Ｃはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００４５】
図５（ｄ）にあるように、エリアＡのノードＩＤ１からの再生成したツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ４、２、５を経由する最短パスと、ノードＩＤ４、６、３と経由する最短パスと、ノードＩＤ４、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ４、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ４、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ４、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。
【００４６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＡに障害が発生している場合に、エリアＢ及びＣのツリーの再生成は行わず、エリアＡのツリーのみを再生成する。エリアＡに所属するノードＩＤ１以外のノードも、ノードＩＤ１と同様に、各ノードからのツリーを切り替える。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００４７】
（第四の実施形態）
本実施形態では、実施形態２においてツリーを作成した後に、最優先エリアのリンク間で故障が生じ、ネットワークのトポロジが変化した場合について説明する。図６は、本発明におけるパケット転送通信ネットワークの第四の実施形態を示す図である。図６では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１とノードＩＤ３の間のリンクで故障が発生した際の、ノードＩＤ１７からのツリーに対する切替動作の例を示す図である。
【００４８】
図６に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図６（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図６（ｂ）は図６（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図６（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図６（ｄ）は図６（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００４９】
図６（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【００５０】
図６（ｂ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。ここまでは、実施形態２と同様である。
【００５１】
ノードＩＤ１とノードＩＤ３の間のリンクで故障が発生したとすると、通知手順において、ノードＩＤ１及びノードＩＤ３のリンクステート情報設定部２２は、エリアＡに所属するノードＩＤ１とノードＩＤ３の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。エリアＢからエリアＡへ接続するノードであるノードＩＤ６は、リンクステート情報がエリアＡに所属するノードで生成されたことを確認する。一方で、エリアＢ、Ｃに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。ここで、エリアＡに所属するノードＩＤ６，７は、エリアＡのノードからエリアＢのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【００５２】
ノードＩＤ１〜５のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１〜５のパス設定管理部２４はエリアＡのツリーを再生成する。例えば、図６（ｃ）にあるように、ノードＩＤ６はエリアＡに所属するノードＩＤ３と経由する最短パスと、ノードＩＤ４、１と経由する最短パスと、ノードＩＤ４、２と経由する最短パスと、ノードＩＤ７、５と経由する最短パスの集合であるツリーを再生成する。エリアＢ、Ｃはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００５３】
図６（ｄ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からの再生成したツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。
【００５４】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＡに障害が発生している場合に、エリアＢ及びＣのツリーの再生成は行わず、エリアＡのみを再生成する。このため、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００５５】
（第五の実施形態）
本実施形態では、実施形態１においてツリーを作成した後に、最優先エリアのノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図７は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図７では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ３で故障が発生した際の、ノードＩＤ１からのツリーに対する切替動作の例を示す図である。
【００５６】
図７に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図７（ａ）は、故障発生前のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図７（ｂ）は図７（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図７（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図７（ｄ）は図７（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００５７】
図７（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【００５８】
図７（ｂ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。ここまでは、実施形態１と同様である。
【００５９】
ノードＩＤ３で故障が発生したとすると、通知手順において、ノードＩＤ１のリンクステート情報設定部２２はエリアＡに所属するノードＩＤ１とノードＩＤ３の間のリンクの通信断、ノードＩＤ６のリンクステート情報設定部２２はエリアＡに所属するノードＩＤ６とノードＩＤ３の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。ノードＩＤ１は、リンクステート情報がエリアＡに所属するノードで生成されたことを確認する。一方で、エリアＢ、Ｃに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。ここで、エリアＡに所属するノードＩＤ６，７は、エリアＡのノードからエリアＢのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【００６０】
ノードＩＤ１〜５のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１〜５のパス設定管理部２４はエリアＡのツリーを再生成する。例えば、図７（ｃ）にあるように、ノードＩＤ１はエリアＡに所属するノードＩＤ４、２、５を経由する最短パスと、ノードＩＤ４、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスの集合であるツリーを再生成する。エリアＢ、Ｃはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００６１】
図７（ｄ）にあるように、エリアＡのノードＩＤ１からの再生成したツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ４、２、５を経由する最短パスと、ノードＩＤ４、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ４、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ４、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ４、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。
【００６２】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＡに障害が発生している場合に、エリアＢ及びＣのツリーの再生成は行わず、エリアＡのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００６３】
（第六の実施形態）
本実施形態では、実施形態２においてツリーを作成した後に、最優先エリアのノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図８は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図８では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ３で故障が発生した際の、ノードＩＤ１７からのツリーに対する切替動作の例を示す図である。
【００６４】
図８に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図８（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図８（ｂ）は図８（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図８（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図８（ｄ）は図８（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００６５】
図８（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【００６６】
図８（ｂ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。ここまでは、実施形態２と同様である。
【００６７】
ノードＩＤ３で故障が発生したとすると、通知手順において、ノードＩＤ１のリンクステート情報設定部２２はエリアＡに所属するノードＩＤ１とノードＩＤ３の間のリンクの通信断、ノードＩＤ６のリンクステート情報設定部２２はエリアＡに所属するノードＩＤ６とノードＩＤ３の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。エリアＢからエリアＡへ接続するノードであるノードＩＤ６は、リンクステート情報がエリアＡに所属するノードで生成されたことを確認する。一方で、エリアＢ、Ｃに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。ここで、エリアＡに所属するノードＩＤ６，７は、エリアＡのノードからエリアＢのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【００６８】
ノードＩＤ１〜５のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１〜５のパス設定管理部２４はエリアＡのツリーを再生成する。例えば、図８（ｃ）にあるように、ノードＩＤ６はエリアＡに所属するノードＩＤ４、１と経由する最短パスと、ノードＩＤ４、２と経由する最短パスと、ノードＩＤ７、５と経由する最短パスの集合であるツリーを再生成する。エリアＢ、Ｃはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００６９】
図８（ｄ）にあるようにエリアＡのノードＩＤ６からの再生成したツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、４、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。
【００７０】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＡに障害が発生している場合に、エリアＢ及びＣのツリーの再生成は行わず、エリアＡのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００７１】
（第七の実施形態）
本実施形態では、実施形態１においてツリーを作成した後に、優先エリアの低いエリアＣのリンク間で故障が生じ、ネットワークのトポロジが変化した場合について説明する。図９は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図９では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１１とノードＩＤ１４の間のリンクで故障が発生した際の、ノードＩＤ１からのツリーに対する切替動作の例を示す図である。
【００７２】
図９に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図９（ａ）は、故障発生前のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図９（ｂ）は図９（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図９（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図９（ｄ）は図９（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００７３】
図９（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【００７４】
図９（ｂ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。ここまでは、実施形態１と同様である。
【００７５】
ノードＩＤ１１とノードＩＤ１４の間のリンクで故障が発生したとすると、通知手順において、ノードＩＤ１１及びノードＩＤ１４のリンクステート情報設定部２２は、エリアＡに所属するノードＩＤ１１とノードＩＤ１４の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。ノードＩＤ１１は、リンクステート情報がエリアＣに所属するノードで生成されたことを確認する。一方で、エリアＡ、Ｂに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。ここで、エリアＣに所属するノードＩＤ１１，１２は、エリアＢのノードからエリアＣのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【００７６】
ノードＩＤ１３〜１７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１３〜１７のパス設定管理部２４はエリアＣのツリーを再生成する。例えば、図９（ｃ）にあるように、ノードＩＤ１１はエリアＣに所属するノードＩＤ１２、１４、１７と経由する最短パスと、ノードＩＤ１２、１５と経由する最短パスと、ノードＩＤ１３、１６と経由する最短パスの集合であるツリーを再生成する。エリアＡ、Ｂはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００７７】
図９（ｄ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からの再生成したツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、９、１２、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。
【００７８】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＣに障害が発生している場合に、エリアＡ及びＢのツリーの再生成は行わず、エリアＣのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００７９】
（第八の実施形態）
本実施形態では、実施形態２においてツリーを作成した後に、優先エリアの低いエリアＣのリンク間で故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１０は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１０では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１１とノードＩＤ１４の間のリンクで故障が発生した際の、ノードＩＤ１７からのツリーに対する切替動作の例を示す図である。
【００８０】
図１０に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１０（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図１０（ｂ）は図１０（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１０（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１２、１７からのツリーを示し、図１０（ｄ）は図１０（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００８１】
図１０（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【００８２】
図１０（ｂ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。ここまでは、実施形態２と同様である。
【００８３】
ノードＩＤ１１とノードＩＤ１４の間のリンクで故障が発生したとすると、通知手順において、ノードＩＤ１１及びノードＩＤ１４のリンクステート情報設定部２２は、エリアＣに所属するノードＩＤ１１とノードＩＤ１４の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。ノードＩＤ１７は、リンクステート情報がエリアＣに所属するノードで生成されたことを確認する。一方で、エリアＡ、Ｂに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。
【００８４】
ここでノードＩＤ１７から最も近いエリアＢ及びＣの両方に所属するノードＩＤ１１へのパスが通信断となっている。このため、ノードＩＤ１７からのツリーにおいて、エリアＣからエリアＢへ接続するノードがノードＩＤ１１からノードＩＤ１２へ変わる。その場合、エリアＣに所属するノードＩＤ１１，１２は、前記変更内容をリンクステート情報に追記し、ネットワーク内の各ノードに共有する。
【００８５】
ノードＩＤ１３〜１７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１３〜１７のパス設定管理部２４はエリアＣのツリーを再生成する。例えば、図１０（ｃ）にあるように、ノードＩＤ１７はエリアＣに所属するノードＩＤ１４、１２、１１を経由する最短パスと、ノードＩＤ１４、１６、１３を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合であるツリーを再生成する。
【００８６】
また、本実施形態では、エリアＣ及びＢの両方に所属するノードＩＤ１１及び１２のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１１及び１２のパス設定管理部２４はエリアＢのツリーを再生成する。例えば、図１０（ｃ）にあるように、ノードＩＤ１２はエリアＢに所属するノードＩＤ９、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１０を経由する最短パスの集合であるツリーを再生成する。エリアＢにおけるその他のノードＩＤ６〜１０のノード及びエリアＡの各ノードはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００８７】
図１０（ｄ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１２からのツリーと、エリアＣのノードＩＤ１７からの再生成したツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１２、９、６、３、１を経由する最短パスと、ノードＩＤ１４、１２、９、６、４、２を経由する最短パスと、ノードＩＤ１４、１２、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１６、１３を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ６は、ノードＩＤ１２からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。
【００８８】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＢ及びＣの両方のエリアに所属するノードＩＤ１１のリンクに障害が発生している場合に、エリアＣに加えてエリアＢ及びＣの接続ノードであるノードＩＤ１１及び１２のツリーのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００８９】
（第九の実施形態）
本実施形態では、実施形態１においてツリーを作成した後に、優先エリアの低いエリアＣのノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１１は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１１では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１４で故障が発生した際の、ノードＩＤ１からのツリーに対する切替動作の例を示す図である。
【００９０】
図１１に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１１（ａ）は、故障発生前のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図１１（ｂ）は図１１（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１１（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図１１（ｄ）は図１１（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００９１】
図１１（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【００９２】
図１１（ｂ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。ここまでは、実施形態１と同様である。
【００９３】
ノードＩＤ１４で故障が発生したとすると、通知手順において、ノードＩＤ１１のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１１とノードＩＤ１４の間のリンクの通信断、ノードＩＤ１２のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１２とノードＩＤ１４の間のリンクの通信断、ノードＩＤ１６はエリアＣに所属するノードＩＤ１６とノードＩＤ１４の間のリンクの通信断、ノードＩＤ１７のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１７とノードＩＤ１４の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。ノードＩＤ１１は、リンクステート情報がエリアＣに所属するノードで生成されたことを確認する。一方で、エリアＡ、Ｂに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。ここで、エリアＣに所属するノードＩＤ１１，１２は、エリアＢのノードからエリアＣのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【００９４】
ノードＩＤ１３〜１７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１３〜１７のパス設定管理部２４はエリアＣのツリーを再生成する。例えば、図１１（ｃ）にあるように、ノードＩＤ１１はエリアＣに所属するノードＩＤ１２、１５、１７を経由する最短パスと、ノードＩＤ１３、１６を経由する最短パスの集合であるツリーを再生成する。エリアＡ、Ｂはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【００９５】
図１１（ｄ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からの再生成したツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、９、１２、１５、１７を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。
【００９６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＣに障害が発生している場合に、エリアＡ及びＢのツリーの再生成は行わず、エリアＣのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【００９７】
（第十の実施形態）
本実施形態では、第二の実施形態においてツリーを作成した後に、優先エリアの低いエリアＣのノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１２は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１２では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１４で故障が発生した際の、ノードＩＤ１７からのツリーに対する切替動作の例を示す図である。
【００９８】
図１２に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１２（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図１２（ｂ）は図１２（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１２（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１２、１７からのツリーを示し、図１２（ｄ）は図１２（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【００９９】
図１２（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【０１００】
図１２（ｂ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。ここまでは、実施形態２と同様である。
【０１０１】
ノードＩＤ１４で故障が発生したとすると、通知手順において、ノードＩＤ１１のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１１とノードＩＤ１４の間のリンクの通信断、ノードＩＤ１２のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１２とノードＩＤ１４の間のリンクの通信断、ノードＩＤ１６のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１６とノードＩＤ１４の間のリンクの通信断、ノードＩＤ１７のリンクステート情報設定部２２はエリアＣに所属するノードＩＤ１７とノードＩＤ１４の間のリンクの通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。ノードＩＤ１７は、リンクステート情報がエリアＣに所属するノードで生成されたことを確認する。一方で、エリアＡ、Ｂに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。
【０１０２】
ここで、本実施形態では、ノードＩＤ１７から最も近いエリアＢ及びＣの両方に所属するノードＩＤ１１へのパスが通信断となっている。このため、ノードＩＤ１７からのツリーにおいて、エリアＣからエリアＢへ接続するノードがノードＩＤ１１からノードＩＤ１２へ変わる。その場合、エリアＣに所属するノードＩＤ１１，１２は、前記変更内容をリンクステート情報に追記し、ネットワーク内の各ノードに共有する。
【０１０３】
ノードＩＤ１３〜１７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１３〜１７のパス設定管理部２４はエリアＣのツリーを再生成する。例えば、図１２（ｃ）にあるように、ノードＩＤ１７、１５、１２、１１、１３、１６を経由する最短パスの集合であるエリアＣのツリーを再生成する。
【０１０４】
また、本実施形態では、エリアＢに所属するノードＩＤ１１及び１２のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１１及び１２のパス設定管理部２４はエリアＢのツリーを再生成する。例えば、図１２（ｃ）にあるように、ノードＩＤ１２はエリアＢに所属するノードＩＤ９、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１０を経由する最短パスの集合であるツリーを再生成する。エリアＡはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【０１０５】
図１２（ｄ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からの再生成したツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１５、１２、９、６、３、１を経由する最短パスと、ノードＩＤ１５、１２、９、６、４、２を経由する最短パスと、ノードＩＤ１５、１２、９、７、５を経由する最短パスと、ノードＩＤ１５、１２、１０を経由する最短パスと、ノードＩＤ１５、１２、１１、８を経由する最短パスと、ノードＩＤ１５、１２、１１、１３、１６を経由する最短パスの集合である。ここで、ノードＩＤ６は、ノードＩＤ１２からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。
【０１０６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＣに障害が発生している場合に、エリアＡのツリーの再生成は行わず、エリアＢ及びＣのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【０１０７】
（第十一の実施形態）
本実施形態では、第一の実施形態においてツリーを作成した後に、最優先エリアと他のエリアを接続するノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１３は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１３では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ６で故障が発生した際の、ノードＩＤ１からのツリーに対する切替動作の例を示す図である。
【０１０８】
図１３に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１３（ａ）は、故障発生前のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図１３（ｂ）は図１３（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１３（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、７、１１からのツリーを示し、図１３（ｄ）は図１３（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【０１０９】
図１３（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【０１１０】
図１３（ｂ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。ここまでは、実施形態１と同様である。
【０１１１】
ノードＩＤ６で故障が発生したとすると、通知手順において、ノードＩＤ３、４、７、８、９のリンクステート情報設定部２２は通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。具体的には、ノードＩＤ３はエリアＡに所属するノードＩＤ３とノードＩＤ６の間のリンクの通信断、ノードＩＤ４はエリアＡに所属するノードＩＤ４とノードＩＤ６の間のリンクの通信断、ノードＩＤ７はエリアＡ、Ｂに所属するノードＩＤ７とノードＩＤ６の間のリンクの通信断、ノードＩＤ８はエリアＢに所属するノードＩＤ８とノードＩＤ６の間のリンクの通信断、ノードＩＤ９はエリアＢに所属するノードＩＤ９とノードＩＤ６の間のリンクの通信断という情報をリンクステート情報とする。ノードＩＤ１は、ノードＩＤ３、４、７で生成されたリンクステート情報がエリアＡに所属するノードで生成されたことを、ノードＩＤ７は、ノードＩＤ７、８、９で生成されたリンクステート情報がエリアＢに所属するノードで生成されたことを確認する。一方で、エリアＣに所属する各ノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。
【０１１２】
ここで、本実施形態では、ノードＩＤ１から最も近いエリアＡ及びＢの両方に所属するノードがノードＩＤ６へのパスが通信断となっている。このため、ノードＩＤ１からのツリーにおいて、エリアＡからエリアＢへ接続するノードがノードＩＤ６からノードＩＤ７へ変わる。その場合、エリアＢに所属するノードＩＤ７は、前記変更内容をリンクステート情報に追記し、ネットワーク内の各ノードに共有する。
【０１１３】
ノードＩＤ１〜５のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１〜５のパス設定管理部２４はエリアＡのツリーを再生成する。例えば、図１３（ｃ）にあるように、ノードＩＤ１はエリアＡに所属するノードＩＤ３を経由する最短パスと、ノードＩＤ４、３、５を経由する最短パスと、ノードＩＤ４、７を経由する最短パスの集合であるエリアＡのツリーを再生成する。
【０１１４】
また、本実施形態では、エリアＡ及びＢの両方に所属するノードＩＤ６及び７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ６及び７のパス設定管理部２４はエリアＢのツリーを再生成する。例えば、図１３（ｃ）にあるように、ノードＩＤ７はエリアＢに所属するノードＩＤ９、１１、８を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ１０を経由する最短パスの集合であるエリアＢのツリーを再生成する。エリアＢにおけるその他のノードＩＤ８〜１２のノード及びエリアＣの各ノードはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【０１１５】
図１３（ｄ）にあるように、エリアＡのノードＩＤ１からの再生成したツリーと、エリアＢのノードＩＤ７からの再生成したツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスと、ノードＩＤ４、７、９、１１、８を経由する最短パスとノードＩＤ４、７、９、１１、１３、１６を経由する最短パスと、ノードＩＤ４、７、９、１１、１４、１７を経由する最短パスと、ノードＩＤ４、７、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスの集合となる。ここで、ノードＩＤ１１は、ノードＩＤ７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。
【０１１６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＡ及びＢの両方に所属するノードＩＤ６に障害が発生している場合に、エリアＣのツリーの再生成は行わず、エリアＡ及びＢのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【０１１７】
（第十二の実施形態）
本実施形態では、第二の実施形態においてツリーを作成した後に、最優先エリアと他のエリアを接続するノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１４は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１４では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ６で故障が発生した際の、ノードＩＤ１７からのツリーに対する切替動作の例を示す図である。
【０１１８】
図１４に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１４（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図１４（ｂ）は図１４（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１４（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ７、１１、１７からのツリーを示し、図１４（ｄ）は図１４（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【０１１９】
図１４（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【０１２０】
図１４（ｂ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。ここまでは、実施形態２と同様である。
【０１２１】
ノードＩＤ６で故障が発生したとすると、通知手順において、ノードＩＤ３、４、７、８、９のリンクステート情報設定部２２は通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。具体的には、ノードＩＤ３はエリアＡに所属するノードＩＤ３とノードＩＤ６の間のリンクの通信断、ノードＩＤ４はエリアＡに所属するノードＩＤ４とノードＩＤ６の間のリンクの通信断、ノードＩＤ７はエリアＡ、Ｂに所属するノードＩＤ７とノードＩＤ６の間のリンクの通信断、ノードＩＤ８はエリアＢに所属するノードＩＤ８とノードＩＤ６の間のリンクの通信断、ノードＩＤ９はエリアＢに所属するノードＩＤ９とノードＩＤ６の間のリンクの通信断という情報をリンクステート情報とする。ノードＩＤ７は、ノードＩＤ３、４、７で生成されたリンクステート情報がエリアＡに所属するノードで生成されたことを、ノードＩＤ１１は、ノードＩＤ７、８、９で生成されたリンクステート情報がエリアＢに所属するノードで生成されたことを確認する。一方で、エリアＣに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。
【０１２２】
ここで、本実施形態では、ノードＩＤ１１から最も近いエリアＡ及びＢの両方に所属するノードへのパスが通信断となっている。このため、ノードＩＤ１１からのツリーにおいて、エリアＢからエリアＡへ接続するノードがノードＩＤ６からノードＩＤ７へ変わる。その場合、エリアＡに所属するノードＩＤ７は、前記変更内容をリンクステート情報に追記し、ネットワーク内の各ノードに共有する。
【０１２３】
ノードＩＤ１〜１２のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ１〜７のパス設定管理部２４はエリアＡのツリーを再生成する。例えば、図１４（ｃ）にあるように、ノードＩＤ７はエリアＡに所属するノードＩＤ４、１、３を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ５を経由する最短パスの集合であるエリアＡのツリーを再生成する。
【０１２４】
また、ノードＩＤ８〜１２のパス設定管理部２４はエリアＢのツリーを再生成する。例えば、図１４（ｃ）にあるように、ノードＩＤ１１はエリアＢに所属するノードＩＤ８を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合であるエリアＢのツリーを再生成する。エリアＣはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【０１２５】
図１４（ｄ）にあるように、エリアＡのノードＩＤ７からの再生成したツリーと、エリアＢのノーＩＤド１１からの再生成したツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８を経由する最短パスと、ノードＩＤ１４、１１、９、７、４、１、３を経由する最短パスと、ノードＩＤ１４、１１、９、７、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。
【０１２６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＡ及びＢの両方に所属するノードに障害が発生している場合に、エリアＣのツリーの再生成は行わず、エリアＡ及びＢのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【０１２７】
（第十三の実施形態）
本実施形態では、第一の実施形態においてツリーを作成した後に、優先度の低いエリアと他のエリアを接続するノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１５は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１５では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１１で故障が発生した際の、ノードＩＤ１からのツリーに対する切替動作の例を示す図である。
【０１２８】
図１５に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１５（ａ）は、故障発生前のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１１からのツリーを示し、図１５（ｂ）は図１５（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１５（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ１、６、１２からのツリーを示し、図１５（ｄ）は図１５（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【０１２９】
図１５（ａ）にあるように、エリアＡにおけるノードＩＤ１からのツリーは、ノードＩＤ３、６を経由する最短パスと、ノードＩＤ４、７を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合である。エリアＢにおいて、エリアＡからエリアＢへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ８、１１を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合である。エリアＣにおいて、エリアＢからエリアＣへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ１３、１６を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１２、１５を経由する最短パスの集合である。エリアＡからエリアＢへ接続するノードはノードＩＤ６が、エリアＢからエリアＣへ接続するノードはノードＩＤ１１が担う。
【０１３０】
図１５（ｂ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１１からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８、１１、１３、１６を経由する最短パスと、ノードＩＤ３、６、８、１１、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。同様に、ノードＩＤ１１は、ノードＩＤ６からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、１１を経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。ここまでは、実施形態１と同様である。
【０１３１】
ノードＩＤ１１で故障が発生したとすると、通知手順において、ノードＩＤ８、９、１２、１３、１４のリンクステート情報設定部２２は通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。具体的には、ノードＩＤ８はエリアＢに所属するノードＩＤ８とノードＩＤ１１の間のリンクの通信断、ノードＩＤ９はエリアＢに所属するノードＩＤ９とノードＩＤ１１の間のリンクの通信断、ノードＩＤ１２はエリアＢ、Ｃに所属するノードＩＤ１２とノードＩＤ１１の間のリンクの通信断、ノードＩＤ１３はエリアＣに所属するノードＩＤ１３とノードＩＤ１１の間のリンクの通信断、ノードＩＤ１４はエリアＣに所属するノードＩＤ１４とノードＩＤ１１の間のリンクの通信断という情報をリンクステート情報とする。ノードＩＤ６は、ノードＩＤ８、９、１２で生成されたリンクステート情報がエリアＢに所属するノードで生成されたことを、ノードＩＤ１２は、ノードＩＤ１２、１３、１４で生成されたリンクステート情報がエリアＣに所属するノードで生成されたことを確認する。一方で、エリアＡに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。
【０１３２】
ここで、本実施形態では、ノードＩＤ６から最も近いエリアＢ及びＣの両方に所属するノードがノードＩＤ１１へのパスが通信断となっている。このため、ノードＩＤ６からのツリーにおいて、エリアＢからエリアＣへ接続するノードがノードＩＤ１１からノードＩＤ１２へ変わる。その場合、エリアＣに所属するノードＩＤ１２は、前記変更内容をリンクステート情報に追記し、ネットワーク内の各ノードに共有する。
【０１３３】
ノードＩＤ６〜１７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ６〜１０のパス設定管理部２４はエリアＢのツリーを再生成する。例えば、図１５（ｃ）にあるように、ノードＩＤ６はエリアＢに所属するノードＩＤ８を経由する最短パスと、ノードＩＤ９、１２を経由する最短パスと、ノードＩＤ７、１０を経由する最短パスの集合であるエリアＢのツリーを再生成する。
【０１３４】
また、ツリー生成手順において、ノードＩＤ１１〜１７のパス設定管理部２４はエリアＣのツリーを再生成する。例えば、図１５（ｃ）にあるように、ノードＩＤ１２はエリアＣに所属するノードＩＤ１４、１６、１３を経由する最短パスと、ノードＩＤ１４、１７を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合であるエリアＣのツリーを再生成する。エリアＡはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【０１３５】
図１５（ｄ）にあるように、エリアＡのノードＩＤ１からのツリーと、エリアＢのノードＩＤ６からのツリーと、エリアＣのノードＩＤ１２からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ３、６、８を経由する最短パスと、ノードＩＤ３、６、９、１２、１４、１６、１３を経由する最短パスと、ノードＩＤ３、６、９、１２、１４、１７を経由する最短パスと、ノードＩＤ３、６、９、１２、１５を経由する最短パスと、ノードＩＤ４、７、１０を経由する最短パスと、ノードＩＤ４、２、５を経由する最短パスの集合となる。ここで、ノードＩＤ６は、ノードＩＤ１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ４を経由するパスの方が、ノードＩＤ３、６と経由するパスと比較して、最短パスであると判断し、ノードＩＤ６へパケットを転送しない。
【０１３６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＢ及びＣの両方に所属するノードに障害が発生している場合に、エリアＡのツリーの再生成は行わず、エリアＢ及びＣのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【０１３７】
（第十四の実施形態）
本実施形態では、第二の実施形態においてツリーを作成した後に、優先度の低いエリアと他のエリアを接続するノードで故障が生じ、ネットワークのトポロジが変化した場合について説明する。図１６は、本発明におけるパケット転送通信ネットワークの第五の実施形態を示す図である。図１６では、リンクステート型ルーティングプロトコルおよび複数のツリーが存在する場合、ノードＩＤの和が最も小さいツリーを選択するアルゴリズムのＥＣＴを使用し、エリアを分けたパケット転送通信ネットワークにおいて、ノードＩＤ１１で故障が発生した際の、ノードＩＤ１７からのツリーに対する切替動作の例を示す図である。
【０１３８】
図１６に示すパケット転送通信ネットワークは、パケット通信ノードＩＤ１〜１７により構成され、ノードＩＤ１〜７をエリアＡ、ノードＩＤ６〜１２をエリアＢ、ノードＩＤ１１〜１７をエリアＣとし、エリアの優先度はＡ、Ｂ、Ｃの順である。図１６（ａ）はエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ６、１１、１７からのツリーを示し、図１６（ｂ）は図１６（ａ）の各エリアのツリーを重ね合わせたツリーを示している。図１６（ｃ）は、切替動作後のエリアＡ、Ｂ、Ｃのそれぞれにおける、ノードＩＤ７、１２、１７からのツリーを示し、図１６（ｄ）は図１６（ｃ）の各エリアのツリーを重ね合わせたツリーを示している。
【０１３９】
図１６（ａ）にあるように、エリアＣにおけるノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。エリアＢにおいて、エリアＣからエリアＢへ接続するノードであるノードＩＤ１１からのツリーは、ノードＩＤ８、６を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１２、１０を経由する最短パスの集合である。エリアＡにおいて、エリアＢからエリアＡへ接続するノードであるノードＩＤ６からのツリーは、ノードＩＤ３、１を経由する最短パスと、ノードＩＤ４、２を経由する最短パスと、ノードＩＤ７、５、を経由する最短パスの集合である。エリアＣからエリアＢへ接続するノードはノードＩＤ１１が、エリアＢからエリアＡへ接続するノードはノードＩＤ６が担う。
【０１４０】
図１６（ｂ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１１からのツリーと、エリアＣのノードＩＤ１７からのツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１１、８、６、３、１を経由する最短パスと、ノードＩＤ１４、１１、８、６、４、２を経由する最短パスと、ノードＩＤ１４、１１、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１１、１３を経由する最短パスと、ノードＩＤ１４、１６を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ１１は、ノードＩＤ１７からノードＩＤ１２への最短パスを生成する場合、ノードＩＤ１４を経由するパスの方が、ノードＩＤ１４、１１と経由するパスと比較して、最短パスであると判断し、ノードＩＤ１２へパケットを転送しない。同様に、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。ここまでは、実施形態２と同様である。
【０１４１】
ノードＩＤ１１で故障が発生したとすると、通知手順において、ノードＩＤ８、９、１２、１３、１４のリンクステート情報設定部２２は通信断という情報をリンクステート情報としてネットワーク内の各ノードに共有する。具体的には、ノードＩＤ８はエリアＢに所属するノードＩＤ８とノードＩＤ１１の間のリンクの通信断、ノードＩＤ９はエリアＢに所属するノードＩＤ９とノードＩＤ１１の間のリンクの通信断、ノードＩＤ１２はエリアＢ、Ｃに所属するノードＩＤ１２とノードＩＤ１１の間のリンクの通信断、ノードＩＤ１３はエリアＣに所属するノードＩＤ１３とノードＩＤ１１の間のリンクの通信断、ノードＩＤ１４はエリアＣに所属するノードＩＤ１４とノードＩＤ１１の間のリンクの通信断という情報をリンクステート情報とする。ノードＩＤ１２は、ノードＩＤ８、９、１２で生成されたリンクステート情報がエリアＢに所属するノードで生成されたことを、ノードＩＤ１７は、ノードＩＤ１２、１３、１４で生成されたリンクステート情報がエリアＣに所属するノードで生成されたことを確認する。一方で、エリアＡに所属するノードは、自身が所属するエリアのネットワーク内におけるリンクステート情報ではないため、各ノードの所属するエリアに変更がないことを確認し、廃棄する。
【０１４２】
ここで、本実施形態では、ノードＩＤ１７から最も近いエリアＢ及びＣの両方に所属するノードへのパスが通信断となっている。このため、ノードＩＤ１７からのツリーにおいて、エリアＣからエリアＢへ接続するノードがノードＩＤ１１からノードＩＤ１２へ変わる。その場合、エリアＢに所属するノードＩＤ１２は、前記変更内容をリンクステート情報に追記し、ネットワーク内の各ノードに共有する。エリアＢに所属するノードＩＤ６，７は、エリアＢのノードからエリアＡのノードへ接続するノードに変更がないため、リンクステート情報に追記しない。
【０１４３】
ノードＩＤ８〜１７のリンクステート情報が変更されている。そこで、本実施形態では、ツリー生成手順において、ノードＩＤ８〜１２のパス設定管理部２４はエリアＢのツリーを再生成する。例えば、図１６（ｃ）にあるように、ノードＩＤ１２はエリアＢに所属するノードＩＤ９、６、８を経由する最短パスと、ノードＩＤ９、７を経由する最短パスと、ノードＩＤ１０を経由する最短パスの集合であるエリアＢのツリーを再生成する。
【０１４４】
また、ツリー生成手順において、ノードＩＤ３〜１７のパス設定管理部２４はエリアＣのツリーを再生成する。例えば、図１６（ｃ）にあるように、ノードＩＤ１７はエリアＣに所属するノードＩＤ１４、１２を経由する最短パスと、ノードＩＤ１４、１６、１３を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合であるエリアＣのツリーを再生成する。
エリアＡはリンクステート情報が変更されていないため、ツリーの再生成は行わない。
【０１４５】
図１６（ｄ）にあるように、エリアＡのノードＩＤ６からのツリーと、エリアＢのノードＩＤ１２からの再生成したツリーと、エリアＣのノードＩＤ１７からの再生成したツリーを重ね合わせたネットワーク全体のツリーは、ノードＩＤ１７からのツリーは、ノードＩＤ１４、１２、９、６、３、１を経由する最短パスと、ノードＩＤ１４、１２、９、６、４、２を経由する最短パスと、ノードＩＤ１４、１２、９、６、８を経由する最短パスと、ノードＩＤ１４、１２、９、７、５を経由する最短パスと、ノードＩＤ１４、１２、１０を経由する最短パスと、ノードＩＤ１４、１６、１３を経由する最短パスと、ノードＩＤ１５を経由する最短パスの集合である。ここで、ノードＩＤ６は、ノードＩＤ１１からノードＩＤ７への最短パスを生成する場合、ノードＩＤ９を経由するパスの方が、ノードＩＤ８、６を経由するパスと比較して、最短パスであると判断し、ノードＩＤ７へパケットを転送しない。
【０１４６】
以上説明したように、本実施形態に係るパケット転送通信ネットワークは、エリアＢ及びＣの両方に所属するノードに障害が発生している場合に、エリアＡのツリーの再生成は行わず、エリアＢ及びＣのみを再生成する。このため、本実施形態に係る発明は、ネットワークトポロジに変化が生じた場合における最短パスの再計算時間を小さくすることができ、高速なパスの切替を行うことができる。
【産業上の利用可能性】
【０１４７】
前記全ての実施形態は、ＳＰＢを用いることで実現することができる。
【符号の説明】
【０１４８】
２１：ノード
２２：リンクステート情報設定部
２３：トポロジ情報データベース
２４：パス設定管理部
２５：パケット転送部
２６：ポート
【図１】
2015154287.tif 000003
【図２】
2015154287.tif 000004
【図３】
2015154287.tif 000005
【図４】
2015154287.tif 000006
【図５】
2015154287.tif 000007
【図６】
2015154287.tif 000008
【図７】
2015154287.tif 000009
【図８】
2015154287.tif 000010
【図９】
2015154287.tif 000011
【図１０】
2015154287.tif 000012
【図１１】
2015154287.tif 000013
【図１２】
2015154287.tif 000014
【図１３】
2015154287.tif 000015
【図１４】
2015154287.tif 000016
【図１５】
2015154287.tif 000017
【図１６】
2015154287.tif 000018