故障回復パス計算方法および故障回復パス計算システム
【課題】１＋１の冗長構成を、ネットワークの残資源を考慮して動的に設定する。
【解決手段】ノード１０−ｎ（ｎは自然数）とノード１０−ｎ同士のリンクとを有する通信ネットワーク１００において、集中管理サーバ３０は、送信元ノードであるノード１０−１から宛先ノードであるノード１０−１０に至る現用パスＰＰと、送信元ノード１０−１から、現用パスとは異なるノード１０−ｎを介して宛先ノード１０−ｎに至る予備パスとからなる１＋１冗長構成をとる通信経路に対して、現用パスを構成するリンクのいずれかに故障が発生した際に、予備パスを新たな現用パスとして使用すると共に新たな予備パスを算出する。予備パスを構成するリンクのいずれかに故障が発生した際にも、新たな予備パスを算出する。
【解決手段】ノード１０−ｎ（ｎは自然数）とノード１０−ｎ同士のリンクとを有する通信ネットワーク１００において、集中管理サーバ３０は、送信元ノードであるノード１０−１から宛先ノードであるノード１０−１０に至る現用パスＰＰと、送信元ノード１０−１から、現用パスとは異なるノード１０−ｎを介して宛先ノード１０−ｎに至る予備パスとからなる１＋１冗長構成をとる通信経路に対して、現用パスを構成するリンクのいずれかに故障が発生した際に、予備パスを新たな現用パスとして使用すると共に新たな予備パスを算出する。予備パスを構成するリンクのいずれかに故障が発生した際にも、新たな予備パスを算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、光(波長)パスやMPLS（Multi-Protocol Label Switching）を用いた伝送網に於ける故障回復パス計算方法および故障回復パス計算システムに関する。
【背景技術】
【０００２】
ネットワーク事業者は、予期しない故障の発生に対して迅速に代替の転送経路を提供し、転送品質の維持を行うことが求められる。特に重要なデータ送信を扱う基幹通信網インフラでは、高い耐障害性が要求される。
非特許文献１では、１つの始終点に対し、リンクもしくはノードを共有しない現用パスと予備パスを提供する１＋１のパス設計法が提案されている。
【０００３】
現用パスと予備パスはリンクもしくはノードを共有しないパスとして設計されるため、一方のパスの構成要素に故障が発生しても、他方のパスによる転送が可能となる。具体的には、１＋１の冗長構成では、現用パスと予備パスが同時に設定されており、データを両系に流し受信端で受信データを切り替えている。現用パスに故障を検出した場合には受信端で速やかに受信データを切り替えることで、データ損失を小さくすることが可能である。
【０００４】
しかし、現用パスが故障や工事により不通となると、一時的に予備パスのみの片肺運転となり、通信路の信頼性が低下する。このため、ネットワーク事業者は、故障が発生すると速やかに故障の復旧を行う必要がある。
【０００５】
図１１は、従来技術に於ける故障発生の例を示す図である。図１１（ａ）は、ネットワーク事業者の作業のガントチャートである。このガントチャートは、横方向が時間軸であり、右横方向に時間の経過を示している。図１１（ｂ）は、ネットワーク事業者が運用する通信ネットワークの概略の構成図である。
【０００６】
図１１（ｂ）に示すように、通信ネットワーク１００は、ノード１０−１〜１０−１０と、これらのノード１０−ｎ（ｎ＝１〜１０）相互を接続するリンクとで構成されている。通信路の送信元は、ノード１０−１である。通信路の宛先は、ノード１０−１０である。現用パスは、ノード１０−１から、ノード１０−２，１０−９，１０−６を経由して、ノード１０−１０に至る経路である。ノード１０−９とノード１０−６とを接続するリンクの放射状のマークは、このリンクに故障が発生したことを示している。
【０００７】
図１１（ａ）に示すように、Ｘ月２日の０時００分に、ノード１０−９とノード１０−６とを接続するリンクに故障が発生している。この現用パスの通信は途絶し、通信ネットワーク１００を管理するネットワーク事業者は、復旧作業が必要となる。復旧作業が完了したのはＸ月２日の１２時００分であり、この時点まで通信は途絶する。このように、故障が夜間に発生したとしてもネットワーク事業者は故障場所へ速やかに駆け付けて保守と修理とを行う必要があり、運用コストが増加する。
【０００８】
これに対し、新たな予備パスを自動的に設定すると、故障後においても一定のネットワーク稼働率を担保できるため、故障のメンテナンスに十分な時間を割り当てることが可能となり、ネットワーク事業者が行う保守稼動のコスト、すなわち運用コストを削減可能となる。
非特許文献１には、新たな予備パスを設定するため、１つの送信元と宛先の組合せに対して１＋１＋１の３ルートを事前に設計する技術が開示されている。
【０００９】
Disjointな（設備共有を行わない）３ルートを事前に設計するためにはネットワークは３辺連結グラフである必要がある。しかし、実際のネットワークモデルは３辺連結グラフでない場合が多く、３ルートを事前に設計する方法は実網への適用性が低いという課題がある。
【００１０】
非特許文献２には、１＋１の冗長構成をとる通信経路に於いて、動的にパスを算出する技術が開示されており、実際のネットワークモデルは３辺連結グラフでない場合が多い旨が記載されている。
更に、故障箇所に応じて動的にパスを設定することで、Disjoint制約を緩和して実網への適用性を高める方法が知られている。
【００１１】
図１０（ａ）〜（ｃ）は、従来技術に於ける動的パス設定の概要を示す図である。
図１０（ａ）に示す通信ネットワーク１００ａは、ノード１０ａ−１〜１０ａ−８を有している。ノード１０ａ−１は、送信元ノードである。ノード１０ａ−８は、宛先ノードである。ノード１０ａ−１〜１０ａ−８は、それぞれリンクによって通信可能に接続されている。現用パスＰＰ−０は、送信元ノードである１０ａ−１から、ノード１０ａ−２，１０ａ−５を介して、宛先ノードであるノード１０ａ−８へと至る経路である。予備パスＰＲ−０は、送信元ノードであるノード１０ａ−１から、ノード１０ａ−３，１０ａ−６，１０ａ−７を介して、宛先ノードであるノード１０ａ−８へと至る経路である。
【００１２】
図１０（ｂ）は、前述した図１０（ａ）に示す現用パスＰＰ−０の一部であったノード１０ａ−２とノード１０ａ−５とを接続するリンクが、故障リンクＦＴ−１となった場合である。このとき、前述した図１０（ａ）に示す予備パスＰＲ−０を新たな現用パスＰＰ−０とする。更に、故障リンクＦＴ−１と予備パスを構成するリンクとを使用しないパスを、新たな予備パスＰＲ−１とする。予備パスＰＲ−１は、送信元ノードである１０ａ−１から、ノード１０ａ−４，１０ａ−６，１０ａ−５を介して、宛先ノードであるノード１０ａ−８へと至る経路である。
【００１３】
図１０（ｃ）は、前述した図１０（ａ）に示す予備パスＰＲ−０の一部であったノード１０ａ−３とノード１０ａ−６とを接続するリンクが、故障リンクＦＴ−２となった場合である。このとき、故障リンクＦＴ−２と現用パスＰＰ−０を構成するリンクを使用しない経路を新たな予備パスＰＲ−２として提供する。予備パスＰＲ−２は、送信元ノードである１０ａ−１から、ノード１０ａ−３，１０ａ−４，１０ａ−６，１０ａ−７を介して、宛先ノードであるノード１０ａ−８へと至る経路である。
【００１４】
これにより、１＋１＋１冗長構成の場合と比べ、動的パスが使用できるリンク数やノード数が増加し、Disjoint制約が緩和され、完全に３辺連結ではないネットワークにおいても救済可能な（動的パスを設定可能な）故障パターン数を増加させることが可能となる。
【００１５】
しかしながら、上記の方式は始終点間の到達性のみを考慮しており運用中のネットワークの残資源を考慮していない。すなわち、利用可能な設備資源（具体的にはリンク帯域）が無限であるという前提のもとで、パスの遅延時間などを考慮したパスの計算法および必要帯域の計算法を提供している。一方で、既に１＋１冗長構成で設計されたネットワークへ動的なパス設定法を適用する場合は、すでに設定されたパスが資源を使用しているため、残資源が定義される。すなわち、既に設計済で運用中のネットワークに動的なパス設定法を適用する場合、動的パスは到達性を満たすだけではなく、残資源の制約も満たす必要がある。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】E. Mannie、 D. Papadimitriou、"Recovery (Protection and Restoration) Terminology for Generalized Multi-Protocol Label Switching (GMPLS) "、Mar. 2006.、IETF RFC4427 6.1、
【非特許文献２】S. Kamamura. et al.、“Sticky 1+1 Path Protection Method by Dynamic Disjoint Path Discovery”、2011 Feb.、Proceedings of IEEE ONDM
【発明の概要】
【発明が解決しようとする課題】
【００１７】
パス網においては、１＋１の冗長構成をとることで、信頼性を向上させることができる。一方で、片方のパスが故障や工事により不通となると、一時的な片肺運転の状態が発生し、通信路の信頼性が低下する。このためネットワーク事業者は、故障が発生すると速やかに故障の復旧を行う必要があり、よって運用コストが増加するという課題があった。
【００１８】
これに対して、事前に１＋１＋１の３ルートを設計する方法があるが、実網への適用性が低いという課題がある。１＋１の冗長構成を動的に設定する方法は、従来は、到達性のみが考慮されており、残資源の制約を満たすことは考慮されていなかった。
そこで、本発明は、１＋１の冗長構成を、ネットワークの残資源を考慮して動的に設定することを課題とする。
【課題を解決するための手段】
【００１９】
前記した課題を解決するため、請求項１に記載の発明は、ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、前記集中管理サーバは更に、前記通信ネットワークのトポロジと、送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、前記処理部は、前記現用通信経路を構成するリンクのいずれかに故障が発生した際に、前記予備通信経路を新たな現用通信経路とするように前記ノードに指示し、前記故障が発生したリンク、および、前記新たな現用通信経路を構成するリンクを含まない第１のトポロジを作成し、前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、前記第３のトポロジの最適経路を算出し、算出した最適経路を新たな予備通信経路として前記記憶部に記憶させることを特徴とする故障回復パス計算方法とした。
【００２０】
このようにすることで、本発明に係る故障回復パス計算方法によれば、１＋１の冗長構成のうち現用通信経路を構成するリンクのいずれかに故障が発生した際に、ネットワークの残資源を考慮して動的に、この１＋１冗長構成に復旧することが可能となる。
【００２１】
また、請求項２に記載の発明は、ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、前記集中管理サーバは更に、前記通信ネットワークのトポロジと、送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、前記処理部は、前記予備通信経路を構成するリンクのいずれかに故障が発生した際に、前記故障が発生したリンク、および、前記現用通信経路を構成するリンクを含まない第１のトポロジを作成し、前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、前記第３のトポロジの最適経路を算出し、算出した最適経路を新たな予備通信経路として前記記憶部に記憶させることを特徴とする故障回復パス計算方法とした。
【００２２】
このようにすることで、本発明に係る故障回復パス計算方法によれば、１＋１の冗長構成のうち予備通信経路を構成するリンクのいずれかに故障が発生した際に、ネットワークの残資源を考慮して動的に、この１＋１冗長構成に復旧することが可能となる。
【００２３】
また、請求項３に記載の発明は、前記処理部は、前記第３のトポロジの最適経路を、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出することを特徴とする請求項１または請求項２に記載の故障回復パス計算方法とした。
【００２４】
このようにすることで、本発明に係る故障回復パス計算方法によれば、上記いずれか１つの方法によって、最適経路を計算することが可能となる。
【００２５】
また、請求項４に記載の発明は、前記処理部は、前記第２のトポロジの最適経路と、前記第２のトポロジの最適経路が要求する資源量である第２の要求資源量と、前記第３のトポロジの最適経路が要求する資源量である第３の要求資源量とを算出し、前記第２の要求資源量に対する前記第３の要求資源量の比率が所定閾値以上のとき、前記第２のトポロジの最適経路を、前記新たな予備通信経路とすることを特徴とする請求項１または請求項２に記載の故障回復パス計算方法とした。
【００２６】
このようにすることで、本発明に係る故障回復パス計算方法によれば、第２のトポロジの最適経路が要求する要求資源量が、第３のトポロジの最適経路が要求する第３の要求資源量よりも、明らかに少ない場合は、第２のトポロジの最適経路を採用し、通信ネットワークの収容効率を向上させることが可能となる。
【００２７】
また、請求項５に記載の発明は、前記処理部は、前記第２のトポロジの最適経路と前記第３のトポロジの最適経路とは、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出することを特徴とする請求項４に記載の故障回復パス計算方法とした。
【００２８】
このようにすることで、本発明に係る故障回復パス計算方法によれば、上記いずれか１つの方法によって、最適経路を計算することが可能となる。
【００２９】
また、請求項６に記載の発明は、請求項１ないし請求項５のいずれか１項に記載の故障回復パス計算方法によって、冗長構成をとる通信経路を算出する集中管理サーバと、前記集中管理サーバが管理する通信ネットワークと、を備えたことを特徴とする故障回復パス計算システムとした。
【００３０】
このようにすることで、本発明に係る故障回復パス計算システムによれば、請求項１ないし請求項５のいずれか１項に記載の故障回復パス計算方法を、集中管理サーバに実行させることが可能となる。
【発明の効果】
【００３１】
本発明によれば、１＋１の冗長構成を、ネットワークの残資源を考慮して動的に設定することが可能となる。
【図面の簡単な説明】
【００３２】
【図１】第１の実施形態に於けるネットワーク構造の例を示す図である。
【図２】第１の実施形態に於ける集中管理サーバと各ノードの構成を示す図である。
【図３】第１の実施形態に於ける集中管理サーバと各ノードの情報要素を示す図である。
【図４】第１の実施形態に於ける故障回復パス計算法を示す図である。
【図５】第１の実施形態に於ける故障回復パス計算法を示すフローチャートである。
【図６】第１の実施形態と従来技術に於けるメンテナンス時間と故障発生率ＣＤＦとの関係を示す図である。
【図７】第１の実施形態に於ける故障発生の例を示す図である。
【図８】第２の実施形態に於ける故障回復パス計算法を示す図である。
【図９】第２の実施形態に於ける故障回復パス計算法を示すフローチャートである。
【図１０】従来技術に於ける動的パス設定の概要を示す図である。
【図１１】従来技術に於ける故障発生の例を示す図である。
【発明を実施するための形態】
【００３３】
以降、本発明を実施するための形態を、図面を参照して詳細に説明する。
【００３４】
（第１の実施形態の構成）
図１は、第１の実施形態に於けるネットワーク構造の例を示す図である。
通信ネットワーク１００は、複数のノード１０−１〜１０−１０と、この複数のノード１０−ｎ間を通信可能に接続するリンクと、網状態情報収集システム２０と、集中管理サーバ３０とを有している。リンクはノード１０−ｎ間を接続することで、各ノード１０−ｎ間の通信経路を提供している。通常、ノード１０−ｎ間にはトラヒックが発生しており、トラヒックはノード１０−ｎ間に設定される伝送パスを用いて転送される。伝送パスは光レイヤの波長パスや、MPLS（Multi-Protocol Label Switching）によるパケットレイヤのパスがある。
【００３５】
網状態情報収集システム２０は、通信ネットワーク１００の複数のノード１０−１〜１０−１０と接続されていると共に、集中管理サーバ３０に接続されている。集中管理サーバ３０は、通信ネットワーク１００の複数のノード１０−１〜１０−１０と接続されている。
【００３６】
網状態情報収集システム２０は、通信ネットワーク１００の網状態情報を収集して集中管理サーバ３０に通知する。集中管理サーバ３０は、パスの計算を行い、ノード１０−１〜１０−１０にパス情報を転送する。集中管理サーバ３０にはPCE（Path Computation Element）などが用いられる。
【００３７】
ノード１０−１は、送信元ノードである。ノード１０−１０は、宛先ノードである。ノード１０−１から、ノード１０−２，１０−９，１０−６を介してノード１０−１０に至る経路は、現用パスＰＰである。通信データは、ノード１０−１から、現用パスＰＰのリンクを介して、ノード１０−１０に送信される。
【００３８】
本実施形態に於いて、通信網の状態（具体的にはリンクの残資源）を考慮する必要があるため、動的なパスは故障パターンに応じてオンラインで計算される。オンラインの計算はサーバ上が必要とするデータベースを小さく設計できるが、オフラインの計算（事前の計算）と比べてリアルタイムな計算が必要であるため、サーバに計算負荷をかけないことが必要とされる。
【００３９】
図２（ａ），（ｂ）は、第１の実施形態に於ける集中管理サーバと各ノードの構成を示す図である。図２（ａ）は、第１の実施形態に於ける集中管理サーバ３０を示している。図２（ｂ）は、第１の実施形態に於けるノード１０−ｎに配置する機能とデータベースとを示している。なお、以下では、データベースをＤＢと記載している場合がある。
【００４０】
集中管理サーバ３０は、現用・予備パス計算部３１と、動的パス計算部３２と、ノード通信部３３と、リンク容量ＤＢ３４と、網トポロジＤＢ３５と、パス情報ＤＢ３６と、残資源ＤＢ３７とを有している。
【００４１】
現用・予備パス計算部３１は、通常時の現用パスや予備パスを計算する。現用・予備パス計算部３１は、さまざまなポリシーで計算するが、例えば、リンクやノードを共有しない現用パスと予備パスとを計算する場合には、従来技術で記載した方法が用いられる。
動的パス計算部３２は、動的に新たな予備パスを計算する。計算処理の詳細は、後述する図５で説明する。
ノード通信部３３は、ノード１０−１〜１０−１０との通信を行い、集中管理サーバ３０で計算した結果をノード１０−１〜１０−１０のいずれかに転送する。
リンク容量ＤＢ３４と、網トポロジＤＢ３５と、パス情報ＤＢ３６と、残資源ＤＢ３７とは、後述する図３（ａ）で説明する。
【００４２】
図２（ｂ）は、第１の実施形態に於けるノードを示している。
ノード１０−ｎ（ｎ＝１〜１０）は、それぞれデータ転送部１１と、プロトコル・シグナリング処理部１２と、サーバ通信部１３と、経路情報ＤＢ１４と、網トポロジＤＢ１５と、パス情報ＤＢ１６を有している。
データ転送部１１は、リンクを介して、ノード１０−ｎ相互間に於けるデータの転送処理を行う。
【００４３】
プロトコル・シグナリング処理部１２は、経路計算のための情報収集やパス開通とパス開放のためのシグナリングを行う。網使用状況情報収集にはＯＳＰＦ−ＴＥ（Open Shortest Path First-Traffic Engineering）、パス制御にはＲＳＶＰ−ＴＥ（Resource Reservation Protocol - Traffic Engineering）などが用いられる。また、故障情報の通知なども行われる。本実施形態では、ＯＳＰＦ−ＴＥによって、各リンクの残資源情報を取得する。
【００４４】
サーバ通信部１３は、集中管理サーバ３０との通信を行う。サーバ通信部１３は、集中管理サーバ３０から送信されるパス情報を受信し、パス情報ＤＢ１６に格納する。
経路情報ＤＢ１４と、網トポロジＤＢ１５と、パス情報ＤＢ１６とは、後述する図３（ｂ）で説明する。
【００４５】
図３（ａ），（ｂ）は、第１の実施形態に於ける集中管理サーバと各ノードの情報要素を示す図である。
図３（ａ）は、第１の実施形態に於ける集中管理サーバの情報要素を示している。
リンク容量ＤＢ３４には、各リンクの容量が格納されている。この各リンクの容量の情報は、網状態情報収集システム２０や、オペレータの投入によって取得される。
【００４６】
網トポロジＤＢ３５には、ノード１０−ｎとリンクの接続関係が格納されている。このノード１０−ｎとリンクの接続関係の情報は、網状態情報収集システム２０によって取得される。
パス情報ＤＢ３６には、各リンクが故障したときの新たな予備パス情報が格納されている。この予備パス情報は、動的パス計算部３２によって出力される。
残資源ＤＢ３７には、リンクの残資源情報が格納されている。このリンクの残資源情報は、網状態情報収集システム２０によって取得される。
【００４７】
図３（ｂ）は、第１の実施形態に於ける各ノードの情報要素を示している。
経路情報ＤＢ１４には、データ宛先と出力インタフェースとの対応関係が格納されている。このデータ宛先と出力インタフェースとの対応関係の情報は、パス情報やルーチングプロトコルの情報を元に作成される。
【００４８】
網トポロジＤＢ１５には、ノード１０−ｎとリンクとの接続関係が格納されている。このノード１０−ｎとリンクとの接続関係の情報は、ＯＳＰＦ（Open Shortest Path First）などのＩＧＰ（Interior Gateway Protocol）ルーチングプロトコルを用いて取得される。
【００４９】
パス情報ＤＢ１６には、故障発生時の予備パス情報が格納されている。この予備パス情報は、集中管理サーバ３０より送信され、各ノード１０−ｎが必要に応じて、このパス情報ＤＢ１６に格納する。具体的には、自ノード１０−ｎを発着点としないフローのパス情報は保持しない。これにより、各ノード１０−ｎが記憶すべきパス情報を最小限に抑えることが可能である。
【００５０】
（第１の実施形態の動作）
図４（ａ）〜（ｃ）は、第１の実施形態に於ける故障回復パス計算法を示す図である。
図４（ａ）〜（ｃ）に示す通信ネットワーク１００ｂは、ノード１０ｂ−１〜１０ｂ−７を有している。
ノード１０ｂ−１は、ノード１０ｂ−２，１０ｂ−３，１０ｂ−４と通信可能に接続されている。
ノード１０ｂ−２は、ノード１０ｂ−１，１０ｂ−４，１０ｂ−５と通信可能に接続されている。但し、ノード１０ｂ−２とノード１０ｂ−５との間は、高負荷リンクＬＫ−０である。
ノード１０ｂ−３は、ノード１０ｂ−１，１０ｂ−４，１０ｂ−６と通信可能に接続されている。
ノード１０ｂ−４は、ノード１０ｂ−２，１０ｂ−３，１０ｂ−５，１０ｂ−６と通信可能に接続されている。
【００５１】
ノード１０ｂ−５は、ノード１０ｂ−２，１０ｂ−４，１０ｂ−７と通信可能に接続されている。但し、ノード１０ｂ−５とノード１０ｂ−２との間は、高負荷リンクＬＫ−０である。
ノード１０ｂ−６は、ノード１０ｂ−３，１０ｂ−４，１０ｂ−７と通信可能に接続されている。
ノード１０ｂ−７は、ノード１０ｂ−４，１０ｂ−５，１０ｂ−６と通信可能に接続されている。
【００５２】
図４（ａ）では、ノード１０ｂ−４を通るリンクＦＴ−１の故障により、中央のパスＰＦ−０が故障し、ノード１０ｂ−３，１０ｂ−６を経由する下側の予備パスが新たな現用パスＰＰ−１として使用される例を示している。このとき、従来技術の故障回復パス計算法では、残資源を考慮しないため、故障リンクＦＴ−１と新たな現用パスＰＰ−１を構成するリンクとを除いたトポロジＴ１に対して、最小コスト経路を計算する。このとき、最小コスト経路上に高負荷リンクＬＫ−０が存在し、パスの要求帯域を満たせない。このとき、新たな最小コスト経路である新たな予備パスＰＲ−１は、高負荷リンクＬＫ−０によってブロックされる。すなわち、この故障パターンに対しては、新たな予備パスＰＲ−１は設定できない。
【００５３】
図４（ｂ）では、トポロジＴ１から高負荷リンクＬＫ−０を除いたトポロジＴ２を作成し、このトポロジＴ２に対して最短経路計算を行った結果である。要求帯域を満たさない高負荷リンクＬＫ−０を除外して最短経路を計算することにより、この高負荷リンクＬＫ−０によってパスがブロックされる現象を回避可能である。
【００５４】
図４（ｃ）では、要求帯域を満たすリンクにおいても重み付けを行う本アルゴリズムの動作例を示した。
ノード１０ｂ−４とノード１０ｂ−５との間のリンクの残資源量（未使用帯域）は、５Ｇｂｐｓである。ノード１０ｂ−５とノード１０ｂ−７との間のリンクの残資源量（未使用帯域）は、５Ｇｂｐｓである。ノード１０ｂ−４とノード１０ｂ−７との間のリンクの残資源量（未使用帯域）は、０．５Ｇｂｐｓである。
【００５５】
リンクの残資源に応じてリンクの重みを変えることで、最小コスト経路計算時の経路を制御している。例えば、図４（ｂ）ではノード１０ｂ−４とノード１０ｂ−７との間のリンクを経由する経路を選択するが、当該リンクの残資源は０．５Ｇｂｐｓと少ない。このような残資源が少ないリンクを優先的に使用すると、他のフローを計算するときに使用できる資源が限られてしまう。
【００５６】
本実施形態では、残資源が多いリンクから優先的に使用し、フロー全体の資源利用効率を高めている。具体的には、ノード１０ｂ−４とノード１０ｂ−５との間のリンクと、ノード１０ｂ−５とノード１０ｂ−７との間のリンクは、それぞれ５Ｇｂｐｓと多いため、これらのリンクを使用している。
【００５７】
図４（ａ）〜（ｃ）では故障リンクＦＴ−１を経由していた１つのフローに着目した例を示した。しかし、一つの故障箇所には、複数のフローが含まれる場合が多いため、残資源を考慮した故障回復パス計算法は、フロー全体の収容効率を高めるためには重要である。
図５は、第１の実施形態に於ける故障回復パス計算法を示すフローチャートである。
集中管理サーバ３０が故障リンクＸを発見したとき、図５の処理が開始する。
処理が開始すると、ステップＳ１０〜Ｓ１７に於いて、動的パス計算部３２は、故障リンクＸを経由する全フローに対して処理を繰り返す。
【００５８】
ステップＳ１１に於いて、動的パス計算部３２は、当該フローが予備パスを経由するか、現用パスを経由するかを判断する。当該フローが予備パスを経由するならば、ステップＳ１３の処理を行う。当該フローが現用パスを経由するならば、ステップＳ１２の処理を行う。現用パスとは、現用通信経路のことをいう。予備パスとは、予備通信経路のことをいう。
【００５９】
ステップＳ１２に於いて、動的パス計算部３２は、故障リンクＸおよび予備パスを構成するリンクのどちらも含まないトポロジＴ１を作成し、ステップＳ１４の処理を行う。
【００６０】
ステップＳ１３に於いて、動的パス計算部３２は、故障リンクＸおよび現用パスを構成するリンクのどちらも含まないトポロジＴ１を作成し、ステップＳ１４の処理を行う。
【００６１】
ステップＳ１４に於いて、動的パス計算部３２は、フローｆが要求する帯域Ｂ（ｆ）よりも残資源が少ないリンクをトポロジＴ１から除去したトポロジＴ２を作成する。ここで残資源とは、リンクの残帯域のことをいう。
【００６２】
ステップＳ１５に於いて、動的パス計算部３２は、トポロジＴ２上に存在するリンクに対し各リンクの残資源に反比例した重みを与え、この重みを与えた新たなトポロジＴ３を作成する。
具体的には、リンクｌ∈Ｌのリンク重みをｗ（ｌ）、リンクｌの残資源をＡ（ｌ）と表現したとき、以下の式１によってリンクｌの重みを決定する。
ｗ（ｌ）＝ ｉｎｔ｛ｍａｘ＿｛ｉ∈Ｌ｝Ａ（ｉ）／ Ａ（ｌ）｝・・・（式１）
ｍａｘ＿｛ｉ∈Ｌ｝Ａ（ｉ）は、全リンクの中で残資源が最大のリンクの資源量を意味する。ｉｎｔ（ｘ）は、ｘを整数値へ変換することを意味する。
【００６３】
ステップＳ１６に於いて、動的パス計算部３２は、トポロジＴ３に対して、ダイクストラ（Dijkstra）法による最小コスト経路を計算し、動的パスを出力する。
【００６４】
ステップＳ１７に於いて、動的パス計算部３２は、故障リンクＸを経由する全フローに対して処理を繰り返していないならば、ステップＳ１０の処理に戻る。故障リンクＸを経由する全フローに対して処理を繰り返したならば、図５の処理を終了する。
【００６５】
図５の処理により現用パスを構成するリンクのいずれかに故障が発生した際に、予備パスを新たな現用パスとして使用すると共に、新たな予備パスを算出する。前記予備パスを構成するリンクのいずれかに故障が発生した際に、新たな予備パスを算出する。
【００６６】
図６は、第１の実施形態と従来技術に於けるメンテナンス時間と故障発生率ＣＤＦとの関係を示す図である。
図６の横軸はメンテナンス時間であり、縦軸は故障発生率のＣＤＦ（累積分布関数：Cummulative Distribution Function）である。
【００６７】
例えば、メンテナンス時間として７２時間を確保したいモデルを考える。これは、ネットワークに週末に故障が発生しても、運用者は、土日を休み、月曜日に出社したのちにネットワークを故障から復旧させるというモデルである。
【００６８】
従来技術の動的パス設定法では、残資源が足りず動的パスを設定できないケースが多いため、早い段階でグラフが上昇する。一方で、第１の実施形態では動的パスを設定できるケースが多いためグラフの上昇が緩やかとなる。その結果として、従来技術の動的パス設定法では、メンテナンスに７２時間割り当て可能な故障パターンは６０％となる。４０％の故障パターンに於いて、運用者は、ネットワークの故障を７２時間以下で復旧する必要がある。
【００６９】
第１の実施形態の動的パス計算法では、９０％の故障パターンに対してはメンテナンスに７２時間を割り当て可能となる。第１の実施形態の動的パス計算法によれば、ネットワークを７２時間の間、９０％の割合でメンテナンスフリーとすることが可能である。完全にメンテナンスフリーとできない場合であっても、メンテナンスフリーとなるケースを確率的に増加させることが可能である。
【００７０】
図７（ａ），（ｂ）は、第１の実施形態に於ける故障発生の例を示す図である。図７（ａ）は、ネットワーク事業者の作業のガントチャートである。このガントチャートは、横方向が時間軸を示し、右横方向に時間の経過を示している。図７（ｂ）は、ネットワーク事業者が運用する通信ネットワークの概略の構成図である。
【００７１】
図７（ｂ）に示すように、通信ネットワーク１００は、ノード１０−１〜１０−１０と、これらのノード１０−ｎ（ｎ＝１〜１０）相互を接続するリンクとで構成されている。通信路の送信元はノード１０−１である。通信路の宛先は、ノード１０−１０である。現用パスＰＰは、ノード１０−１から、ノード１０−２，１０−９，１０−６を経由して、ノード１０−１０に至る経路である。ノード１０−９とノード１０−６とを接続するリンクの放射状のマークは、このリンクに故障が発生したことを示している。
【００７２】
図７（ａ）に示すように、Ｘ月２日の０時０分に、通信ノード１０−９と通信ノード１０−６とを接続するリンクに故障が発生している。しかし、第１の実施形態の通信ネットワーク１００は、Ｘ月２日の９時００分に１＋１の冗長構成に自動で復旧する。通信ネットワーク１００を管理するネットワーク事業者は、即座に復旧作業を完了する必要はない。この事例では、Ｘ月２日の２１時０分に復旧作業を完了させている。
【００７３】
本実施形態のように、新たな予備パスを自動的に設定すると、故障後においても一定のネットワーク稼働率を担保できるため、故障のメンテナンスに十分な時間を割り当てることが可能となり、ネットワーク事業者が行う保守稼動のコスト、すなわち運用コストを削減可能となる。
【００７４】
本実施形態の故障回復パス計算法は、ネットワーク運用後の故障箇所に応じて新たな予備パスを動的に設定することで、ネットワークが自律的に１＋１の冗長構成に復旧し、故障発生後においても高いネットワーク稼働率を保持する。このため、故障復旧のために十分なメンテナンス時間を確保することが可能となり、夜間メンテナンスを不要とするといった運用コスト削減を実現する。
【００７５】
本実施形態の故障回復パス計算法は更に、ネットワークの残資源を考慮して使用可能な資源を効率的に使用する方法であるため、既に運用中のネットワークへ適用可能であり、かつ、利用可能資源が制限された状況において１＋１の冗長構成に復旧できる割合を増加させることが可能である。
なお、１＋１の冗長構成に復旧できる割合が増加することは、十分なメンテナンス時間を割り当て可能な故障パターンの割合が増加することと等価である。
【００７６】
本実施形態の故障回復パス計算法は、運用後の故障箇所に応じて新たな予備パスを計算する。単一リンク故障に対しては、常に二重化された通信路を提供することが可能となる。予備パスを計算する際には残資源を考慮したパスを計算する。具体的には、パスを計算する際に必要な帯域要件を満たさないリンクを除外するとともに、帯域要件を満たすリンクであってもその残資源に応じて重み付けを行うことで、残資源の多いリンクから優先的に使用する。これにより、与えられた網資源上に収容可能な動的パスの数を最大化する。したがって、既存資源のみで１＋１の冗長構成に復旧できる割合を増加させることが可能となる。
【００７７】
（第１の実施形態の効果）
以上説明した第１の実施形態では、次の（Ａ）〜（Ｃ）のような効果がある。
（Ａ） ネットワーク運用後の故障箇所に応じて、新たな予備パスを動的に設定することで、ネットワークが自律的に１＋１の冗長構成に自動で復旧し、故障発生後においても高いネットワーク稼働率を保持する。このため、故障復旧のために十分なメンテナンス時間を確保することが可能となり、夜間メンテナンスを不要とするといった運用コスト削減を実現する。
【００７８】
（Ｂ） ネットワークの残資源を考慮して使用可能な資源を効率的に使用する方法であるため、既に運用中のネットワークへ適用可能であり、かつ、利用可能資源が制限された状況において１＋１の冗長構成に復旧できる割合を増加させることが可能である。
【００７９】
（Ｃ） １＋１の冗長構成に復旧できる割合が増加することにより、十分なメンテナンス時間を割り当て可能な故障パターンの割合が増加する。
【００８０】
（第２の実施形態の構成）
第２の実施形態の通信ネットワーク１００の構成は、図１に示す第１の実施形態の通信ネットワーク１００の構成と同様である。
【００８１】
（第２の実施形態の動作）
図８（ａ），（ｂ）は、第２の実施形態に於ける故障回復パス計算法を示す図である。図８（ａ）は、トポロジＴ２に対する最小コスト経路を示している。図８（ｂ）は、トポロジＴ３に対する最小コスト経路を示している。
【００８２】
第１の実施形態の故障回復パス計算法では、残資源の多いリンクから優先して使用する経路が計算される。一方で、残資源を考慮することでホップ数の長い経路となりトータルで要求する資源が増加する場合が存在する。
【００８３】
図８（ａ）に示すトポロジＴ２に対する最小コスト経路は、ノード１０ｃ−１からノード１０ｃ−３を経由してノード１０ｃ−７に至る経路である。トポロジＴ２に対する最小コスト経路の要求資源量は、１００Ｍｂｐｓである。
【００８４】
図８（ｂ）に示すトポロジＴ３に対する最小コスト経路は、ノード１０ｃ−１からノード１０ｃ−２〜１０ｃ−６を経由してノード１０ｃ−７に至る経路である。トポロジＴ３に対する最小コスト経路の要求資源量は、３００Ｍｂｐｓである。
【００８５】
図８（ａ）に示すトポロジＴ２に対する最小コスト経路の要求資源量１００Ｍｂｐｓが、図８（ｂ）に示すトポロジＴ３に対する最小コスト経路の要求資源量３００Ｍｂｐｓよりも、明らかに少ない場合は、トポロジＴ２に対する最小コスト経路を採用する。これにより、通信ネットワーク１００の収容効率を向上させることが可能である。
【００８６】
図９は、第２の実施形態に於ける故障回復パス計算法を示すフローチャートである。図５に示す第１の実施形態の故障回復パス計算法を示すフローチャートと同一の要素には同一の符号を付与している。
処理が開始したのち、ステップＳ１０〜Ｓ１５の処理は、図５に示す第１の実施形態の故障回復パス計算法のステップＳ１０〜Ｓ１５の処理と同様である。
【００８７】
ステップＳ２０に於いて、動的パス計算部３２は、トポロジＴ２に対する最小コスト経路と、要求資源量ＲＴ２とを計算する。トポロジＴ２とは、第２のトポロジである。要求資源量ＲＴ２は、第２の要求資源量である。
【００８８】
ステップＳ２１に於いて、動的パス計算部３２は、トポロジＴ３に対する最小コスト経路と、要求資源量ＲＴ３とを計算する。トポロジＴ３とは、第３のトポロジである。要求資源量ＲＴ３は、第３の要求資源量である。
【００８９】
ステップＳ２２に於いて、動的パス計算部３２は、ＲＴ２が（α×ＲＴ３）よりも小さいか否かを判断する。ここで、αは所定値の係数である。ＲＴ２が（α×ＲＴ３）よりも小さいならば（Ｙｅｓ）、ステップＳ２３の処理を行う。ＲＴ２が（α×ＲＴ３）以上ならば（Ｎｏ）、ステップＳ２４の処理を行う。
ステップＳ２３に於いて、動的パス計算部３２は、トポロジＴ２に対する最小コスト経路を動的パスとして採用し、ステップＳ１７の処理を行う。
ステップＳ２４に於いて、動的パス計算部３２は、トポロジＴ３に対する最小コスト経路を動的パスとして採用し、ステップＳ１７の処理を行う。
すなわち、第２の要求資源量に対する第３の要求資源量の比率が所定閾値以上のとき、第２のトポロジの最適経路を、新たな予備通信経路としている。
ステップＳ１７以降の処理は、図５に示す第１の実施形態の故障回復パス計算法のステップＳ１７以降の処理と同様である。
【００９０】
（第２の実施形態の効果）
以上説明した第２の実施形態では、次の（Ｄ）のような効果がある。
（Ｄ） トポロジＴ２に対する最小コスト経路の要求資源量が、トポロジＴ３に対する最小コスト経路の要求資源量よりも、明らかに少ない場合は、トポロジＴ２に対する最小コスト経路を採用する。これにより、通信ネットワーク１００の収容効率を向上させることが可能である。
【００９１】
（変形例）
本発明は、上記実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で、変更実施が可能である。この利用形態や変形例としては、例えば、次の（ａ）〜（ｃ）のようなものがある。
【００９２】
（ａ） 第１、第２の実施形態の故障回復パス算出法では、ダイクストラ法によって最適経路を計算している。しかし、これに限られず、ベルマン−フォード法、または、ワーシャル−フロイド法を用いても良い。
【００９３】
（ｂ） 第１、第２の実施形態の故障回復パス算出法では、網状態情報収集システム２０によって通信ネットワーク１００の状態を取得し、集中管理サーバ３０は、取得した情報に基いて各ノード１０−１〜１０−１０を管理している。しかし、これに限られず、集中管理サーバ３０が自ら通信ネットワーク１００の状態を取得しても良い。
（ｃ） 第１、第２の実施形態の故障回復パス算出法では、第２のトポロジの各リンクに、当該各リンクの残資源帯域に反比例した重みを与えた第３のトポロジを作成し、この第３のトポロジの最適経路を算出している。しかし、これに限られず、第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、この第３のトポロジの最適経路を算出しても良い。例えば、１．０から当該各リンクの残資源帯域の割合を除算した重みを、第２のトポロジの各リンクに付与して第３のトポロジを作成し、この第３のトポロジの最適経路を算出しても良い。同様に、残資源帯域の増加に対して単調減少するいずれの関数を用いても良い。
【符号の説明】
【００９４】
１０−１〜１０−１０ ノード
１０ａ−１〜１０ａ−８ ノード
１０ｂ−１〜１０ｂ−７ ノード
１０ｃ−１〜１０ｃ−７ ノード
ＬＫ−０ 高負荷リンク
Ｘ，ＦＴ−１，ＦＴ−２ 故障リンク
ＰＰ−１，ＰＰ 現用パス（現用通信経路）
ＰＦ−０，ＰＦ−１ 故障パス
ＰＲ−１〜ＰＲ−３ 新たな予備パス（新たな予備通信経路）
１１ データ転送部
１２ プロトコル・シグナリング処理部
１３ サーバ通信部
１４ 経路情報ＤＢ
１５ 網トポロジＤＢ
１６ パス情報ＤＢ
２０ 網状態情報収集システム
３０ 集中管理サーバ
３１ 現用・予備パス計算部
３２ 動的パス計算部
３３ ノード通信部
３４ リンク容量ＤＢ
３５ 網トポロジＤＢ
３６ パス情報ＤＢ
３７ 残資源ＤＢ
Ｔ１ トポロジ（第１のトポロジ）
Ｔ２ トポロジ（第２のトポロジ）
Ｔ３ トポロジ（第３のトポロジ）
ＲＴ２，ＲＴ３ 要求資源量
１００，１００ａ，１００ｂ，１００ｃ 通信ネットワーク
【技術分野】
【０００１】
本発明は、光(波長)パスやMPLS（Multi-Protocol Label Switching）を用いた伝送網に於ける故障回復パス計算方法および故障回復パス計算システムに関する。
【背景技術】
【０００２】
ネットワーク事業者は、予期しない故障の発生に対して迅速に代替の転送経路を提供し、転送品質の維持を行うことが求められる。特に重要なデータ送信を扱う基幹通信網インフラでは、高い耐障害性が要求される。
非特許文献１では、１つの始終点に対し、リンクもしくはノードを共有しない現用パスと予備パスを提供する１＋１のパス設計法が提案されている。
【０００３】
現用パスと予備パスはリンクもしくはノードを共有しないパスとして設計されるため、一方のパスの構成要素に故障が発生しても、他方のパスによる転送が可能となる。具体的には、１＋１の冗長構成では、現用パスと予備パスが同時に設定されており、データを両系に流し受信端で受信データを切り替えている。現用パスに故障を検出した場合には受信端で速やかに受信データを切り替えることで、データ損失を小さくすることが可能である。
【０００４】
しかし、現用パスが故障や工事により不通となると、一時的に予備パスのみの片肺運転となり、通信路の信頼性が低下する。このため、ネットワーク事業者は、故障が発生すると速やかに故障の復旧を行う必要がある。
【０００５】
図１１は、従来技術に於ける故障発生の例を示す図である。図１１（ａ）は、ネットワーク事業者の作業のガントチャートである。このガントチャートは、横方向が時間軸であり、右横方向に時間の経過を示している。図１１（ｂ）は、ネットワーク事業者が運用する通信ネットワークの概略の構成図である。
【０００６】
図１１（ｂ）に示すように、通信ネットワーク１００は、ノード１０−１〜１０−１０と、これらのノード１０−ｎ（ｎ＝１〜１０）相互を接続するリンクとで構成されている。通信路の送信元は、ノード１０−１である。通信路の宛先は、ノード１０−１０である。現用パスは、ノード１０−１から、ノード１０−２，１０−９，１０−６を経由して、ノード１０−１０に至る経路である。ノード１０−９とノード１０−６とを接続するリンクの放射状のマークは、このリンクに故障が発生したことを示している。
【０００７】
図１１（ａ）に示すように、Ｘ月２日の０時００分に、ノード１０−９とノード１０−６とを接続するリンクに故障が発生している。この現用パスの通信は途絶し、通信ネットワーク１００を管理するネットワーク事業者は、復旧作業が必要となる。復旧作業が完了したのはＸ月２日の１２時００分であり、この時点まで通信は途絶する。このように、故障が夜間に発生したとしてもネットワーク事業者は故障場所へ速やかに駆け付けて保守と修理とを行う必要があり、運用コストが増加する。
【０００８】
これに対し、新たな予備パスを自動的に設定すると、故障後においても一定のネットワーク稼働率を担保できるため、故障のメンテナンスに十分な時間を割り当てることが可能となり、ネットワーク事業者が行う保守稼動のコスト、すなわち運用コストを削減可能となる。
非特許文献１には、新たな予備パスを設定するため、１つの送信元と宛先の組合せに対して１＋１＋１の３ルートを事前に設計する技術が開示されている。
【０００９】
Disjointな（設備共有を行わない）３ルートを事前に設計するためにはネットワークは３辺連結グラフである必要がある。しかし、実際のネットワークモデルは３辺連結グラフでない場合が多く、３ルートを事前に設計する方法は実網への適用性が低いという課題がある。
【００１０】
非特許文献２には、１＋１の冗長構成をとる通信経路に於いて、動的にパスを算出する技術が開示されており、実際のネットワークモデルは３辺連結グラフでない場合が多い旨が記載されている。
更に、故障箇所に応じて動的にパスを設定することで、Disjoint制約を緩和して実網への適用性を高める方法が知られている。
【００１１】
図１０（ａ）〜（ｃ）は、従来技術に於ける動的パス設定の概要を示す図である。
図１０（ａ）に示す通信ネットワーク１００ａは、ノード１０ａ−１〜１０ａ−８を有している。ノード１０ａ−１は、送信元ノードである。ノード１０ａ−８は、宛先ノードである。ノード１０ａ−１〜１０ａ−８は、それぞれリンクによって通信可能に接続されている。現用パスＰＰ−０は、送信元ノードである１０ａ−１から、ノード１０ａ−２，１０ａ−５を介して、宛先ノードであるノード１０ａ−８へと至る経路である。予備パスＰＲ−０は、送信元ノードであるノード１０ａ−１から、ノード１０ａ−３，１０ａ−６，１０ａ−７を介して、宛先ノードであるノード１０ａ−８へと至る経路である。
【００１２】
図１０（ｂ）は、前述した図１０（ａ）に示す現用パスＰＰ−０の一部であったノード１０ａ−２とノード１０ａ−５とを接続するリンクが、故障リンクＦＴ−１となった場合である。このとき、前述した図１０（ａ）に示す予備パスＰＲ−０を新たな現用パスＰＰ−０とする。更に、故障リンクＦＴ−１と予備パスを構成するリンクとを使用しないパスを、新たな予備パスＰＲ−１とする。予備パスＰＲ−１は、送信元ノードである１０ａ−１から、ノード１０ａ−４，１０ａ−６，１０ａ−５を介して、宛先ノードであるノード１０ａ−８へと至る経路である。
【００１３】
図１０（ｃ）は、前述した図１０（ａ）に示す予備パスＰＲ−０の一部であったノード１０ａ−３とノード１０ａ−６とを接続するリンクが、故障リンクＦＴ−２となった場合である。このとき、故障リンクＦＴ−２と現用パスＰＰ−０を構成するリンクを使用しない経路を新たな予備パスＰＲ−２として提供する。予備パスＰＲ−２は、送信元ノードである１０ａ−１から、ノード１０ａ−３，１０ａ−４，１０ａ−６，１０ａ−７を介して、宛先ノードであるノード１０ａ−８へと至る経路である。
【００１４】
これにより、１＋１＋１冗長構成の場合と比べ、動的パスが使用できるリンク数やノード数が増加し、Disjoint制約が緩和され、完全に３辺連結ではないネットワークにおいても救済可能な（動的パスを設定可能な）故障パターン数を増加させることが可能となる。
【００１５】
しかしながら、上記の方式は始終点間の到達性のみを考慮しており運用中のネットワークの残資源を考慮していない。すなわち、利用可能な設備資源（具体的にはリンク帯域）が無限であるという前提のもとで、パスの遅延時間などを考慮したパスの計算法および必要帯域の計算法を提供している。一方で、既に１＋１冗長構成で設計されたネットワークへ動的なパス設定法を適用する場合は、すでに設定されたパスが資源を使用しているため、残資源が定義される。すなわち、既に設計済で運用中のネットワークに動的なパス設定法を適用する場合、動的パスは到達性を満たすだけではなく、残資源の制約も満たす必要がある。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】E. Mannie、 D. Papadimitriou、"Recovery (Protection and Restoration) Terminology for Generalized Multi-Protocol Label Switching (GMPLS) "、Mar. 2006.、IETF RFC4427 6.1、
【非特許文献２】S. Kamamura. et al.、“Sticky 1+1 Path Protection Method by Dynamic Disjoint Path Discovery”、2011 Feb.、Proceedings of IEEE ONDM
【発明の概要】
【発明が解決しようとする課題】
【００１７】
パス網においては、１＋１の冗長構成をとることで、信頼性を向上させることができる。一方で、片方のパスが故障や工事により不通となると、一時的な片肺運転の状態が発生し、通信路の信頼性が低下する。このためネットワーク事業者は、故障が発生すると速やかに故障の復旧を行う必要があり、よって運用コストが増加するという課題があった。
【００１８】
これに対して、事前に１＋１＋１の３ルートを設計する方法があるが、実網への適用性が低いという課題がある。１＋１の冗長構成を動的に設定する方法は、従来は、到達性のみが考慮されており、残資源の制約を満たすことは考慮されていなかった。
そこで、本発明は、１＋１の冗長構成を、ネットワークの残資源を考慮して動的に設定することを課題とする。
【課題を解決するための手段】
【００１９】
前記した課題を解決するため、請求項１に記載の発明は、ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、前記集中管理サーバは更に、前記通信ネットワークのトポロジと、送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、前記処理部は、前記現用通信経路を構成するリンクのいずれかに故障が発生した際に、前記予備通信経路を新たな現用通信経路とするように前記ノードに指示し、前記故障が発生したリンク、および、前記新たな現用通信経路を構成するリンクを含まない第１のトポロジを作成し、前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、前記第３のトポロジの最適経路を算出し、算出した最適経路を新たな予備通信経路として前記記憶部に記憶させることを特徴とする故障回復パス計算方法とした。
【００２０】
このようにすることで、本発明に係る故障回復パス計算方法によれば、１＋１の冗長構成のうち現用通信経路を構成するリンクのいずれかに故障が発生した際に、ネットワークの残資源を考慮して動的に、この１＋１冗長構成に復旧することが可能となる。
【００２１】
また、請求項２に記載の発明は、ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、前記集中管理サーバは更に、前記通信ネットワークのトポロジと、送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、前記処理部は、前記予備通信経路を構成するリンクのいずれかに故障が発生した際に、前記故障が発生したリンク、および、前記現用通信経路を構成するリンクを含まない第１のトポロジを作成し、前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、前記第３のトポロジの最適経路を算出し、算出した最適経路を新たな予備通信経路として前記記憶部に記憶させることを特徴とする故障回復パス計算方法とした。
【００２２】
このようにすることで、本発明に係る故障回復パス計算方法によれば、１＋１の冗長構成のうち予備通信経路を構成するリンクのいずれかに故障が発生した際に、ネットワークの残資源を考慮して動的に、この１＋１冗長構成に復旧することが可能となる。
【００２３】
また、請求項３に記載の発明は、前記処理部は、前記第３のトポロジの最適経路を、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出することを特徴とする請求項１または請求項２に記載の故障回復パス計算方法とした。
【００２４】
このようにすることで、本発明に係る故障回復パス計算方法によれば、上記いずれか１つの方法によって、最適経路を計算することが可能となる。
【００２５】
また、請求項４に記載の発明は、前記処理部は、前記第２のトポロジの最適経路と、前記第２のトポロジの最適経路が要求する資源量である第２の要求資源量と、前記第３のトポロジの最適経路が要求する資源量である第３の要求資源量とを算出し、前記第２の要求資源量に対する前記第３の要求資源量の比率が所定閾値以上のとき、前記第２のトポロジの最適経路を、前記新たな予備通信経路とすることを特徴とする請求項１または請求項２に記載の故障回復パス計算方法とした。
【００２６】
このようにすることで、本発明に係る故障回復パス計算方法によれば、第２のトポロジの最適経路が要求する要求資源量が、第３のトポロジの最適経路が要求する第３の要求資源量よりも、明らかに少ない場合は、第２のトポロジの最適経路を採用し、通信ネットワークの収容効率を向上させることが可能となる。
【００２７】
また、請求項５に記載の発明は、前記処理部は、前記第２のトポロジの最適経路と前記第３のトポロジの最適経路とは、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出することを特徴とする請求項４に記載の故障回復パス計算方法とした。
【００２８】
このようにすることで、本発明に係る故障回復パス計算方法によれば、上記いずれか１つの方法によって、最適経路を計算することが可能となる。
【００２９】
また、請求項６に記載の発明は、請求項１ないし請求項５のいずれか１項に記載の故障回復パス計算方法によって、冗長構成をとる通信経路を算出する集中管理サーバと、前記集中管理サーバが管理する通信ネットワークと、を備えたことを特徴とする故障回復パス計算システムとした。
【００３０】
このようにすることで、本発明に係る故障回復パス計算システムによれば、請求項１ないし請求項５のいずれか１項に記載の故障回復パス計算方法を、集中管理サーバに実行させることが可能となる。
【発明の効果】
【００３１】
本発明によれば、１＋１の冗長構成を、ネットワークの残資源を考慮して動的に設定することが可能となる。
【図面の簡単な説明】
【００３２】
【図１】第１の実施形態に於けるネットワーク構造の例を示す図である。
【図２】第１の実施形態に於ける集中管理サーバと各ノードの構成を示す図である。
【図３】第１の実施形態に於ける集中管理サーバと各ノードの情報要素を示す図である。
【図４】第１の実施形態に於ける故障回復パス計算法を示す図である。
【図５】第１の実施形態に於ける故障回復パス計算法を示すフローチャートである。
【図６】第１の実施形態と従来技術に於けるメンテナンス時間と故障発生率ＣＤＦとの関係を示す図である。
【図７】第１の実施形態に於ける故障発生の例を示す図である。
【図８】第２の実施形態に於ける故障回復パス計算法を示す図である。
【図９】第２の実施形態に於ける故障回復パス計算法を示すフローチャートである。
【図１０】従来技術に於ける動的パス設定の概要を示す図である。
【図１１】従来技術に於ける故障発生の例を示す図である。
【発明を実施するための形態】
【００３３】
以降、本発明を実施するための形態を、図面を参照して詳細に説明する。
【００３４】
（第１の実施形態の構成）
図１は、第１の実施形態に於けるネットワーク構造の例を示す図である。
通信ネットワーク１００は、複数のノード１０−１〜１０−１０と、この複数のノード１０−ｎ間を通信可能に接続するリンクと、網状態情報収集システム２０と、集中管理サーバ３０とを有している。リンクはノード１０−ｎ間を接続することで、各ノード１０−ｎ間の通信経路を提供している。通常、ノード１０−ｎ間にはトラヒックが発生しており、トラヒックはノード１０−ｎ間に設定される伝送パスを用いて転送される。伝送パスは光レイヤの波長パスや、MPLS（Multi-Protocol Label Switching）によるパケットレイヤのパスがある。
【００３５】
網状態情報収集システム２０は、通信ネットワーク１００の複数のノード１０−１〜１０−１０と接続されていると共に、集中管理サーバ３０に接続されている。集中管理サーバ３０は、通信ネットワーク１００の複数のノード１０−１〜１０−１０と接続されている。
【００３６】
網状態情報収集システム２０は、通信ネットワーク１００の網状態情報を収集して集中管理サーバ３０に通知する。集中管理サーバ３０は、パスの計算を行い、ノード１０−１〜１０−１０にパス情報を転送する。集中管理サーバ３０にはPCE（Path Computation Element）などが用いられる。
【００３７】
ノード１０−１は、送信元ノードである。ノード１０−１０は、宛先ノードである。ノード１０−１から、ノード１０−２，１０−９，１０−６を介してノード１０−１０に至る経路は、現用パスＰＰである。通信データは、ノード１０−１から、現用パスＰＰのリンクを介して、ノード１０−１０に送信される。
【００３８】
本実施形態に於いて、通信網の状態（具体的にはリンクの残資源）を考慮する必要があるため、動的なパスは故障パターンに応じてオンラインで計算される。オンラインの計算はサーバ上が必要とするデータベースを小さく設計できるが、オフラインの計算（事前の計算）と比べてリアルタイムな計算が必要であるため、サーバに計算負荷をかけないことが必要とされる。
【００３９】
図２（ａ），（ｂ）は、第１の実施形態に於ける集中管理サーバと各ノードの構成を示す図である。図２（ａ）は、第１の実施形態に於ける集中管理サーバ３０を示している。図２（ｂ）は、第１の実施形態に於けるノード１０−ｎに配置する機能とデータベースとを示している。なお、以下では、データベースをＤＢと記載している場合がある。
【００４０】
集中管理サーバ３０は、現用・予備パス計算部３１と、動的パス計算部３２と、ノード通信部３３と、リンク容量ＤＢ３４と、網トポロジＤＢ３５と、パス情報ＤＢ３６と、残資源ＤＢ３７とを有している。
【００４１】
現用・予備パス計算部３１は、通常時の現用パスや予備パスを計算する。現用・予備パス計算部３１は、さまざまなポリシーで計算するが、例えば、リンクやノードを共有しない現用パスと予備パスとを計算する場合には、従来技術で記載した方法が用いられる。
動的パス計算部３２は、動的に新たな予備パスを計算する。計算処理の詳細は、後述する図５で説明する。
ノード通信部３３は、ノード１０−１〜１０−１０との通信を行い、集中管理サーバ３０で計算した結果をノード１０−１〜１０−１０のいずれかに転送する。
リンク容量ＤＢ３４と、網トポロジＤＢ３５と、パス情報ＤＢ３６と、残資源ＤＢ３７とは、後述する図３（ａ）で説明する。
【００４２】
図２（ｂ）は、第１の実施形態に於けるノードを示している。
ノード１０−ｎ（ｎ＝１〜１０）は、それぞれデータ転送部１１と、プロトコル・シグナリング処理部１２と、サーバ通信部１３と、経路情報ＤＢ１４と、網トポロジＤＢ１５と、パス情報ＤＢ１６を有している。
データ転送部１１は、リンクを介して、ノード１０−ｎ相互間に於けるデータの転送処理を行う。
【００４３】
プロトコル・シグナリング処理部１２は、経路計算のための情報収集やパス開通とパス開放のためのシグナリングを行う。網使用状況情報収集にはＯＳＰＦ−ＴＥ（Open Shortest Path First-Traffic Engineering）、パス制御にはＲＳＶＰ−ＴＥ（Resource Reservation Protocol - Traffic Engineering）などが用いられる。また、故障情報の通知なども行われる。本実施形態では、ＯＳＰＦ−ＴＥによって、各リンクの残資源情報を取得する。
【００４４】
サーバ通信部１３は、集中管理サーバ３０との通信を行う。サーバ通信部１３は、集中管理サーバ３０から送信されるパス情報を受信し、パス情報ＤＢ１６に格納する。
経路情報ＤＢ１４と、網トポロジＤＢ１５と、パス情報ＤＢ１６とは、後述する図３（ｂ）で説明する。
【００４５】
図３（ａ），（ｂ）は、第１の実施形態に於ける集中管理サーバと各ノードの情報要素を示す図である。
図３（ａ）は、第１の実施形態に於ける集中管理サーバの情報要素を示している。
リンク容量ＤＢ３４には、各リンクの容量が格納されている。この各リンクの容量の情報は、網状態情報収集システム２０や、オペレータの投入によって取得される。
【００４６】
網トポロジＤＢ３５には、ノード１０−ｎとリンクの接続関係が格納されている。このノード１０−ｎとリンクの接続関係の情報は、網状態情報収集システム２０によって取得される。
パス情報ＤＢ３６には、各リンクが故障したときの新たな予備パス情報が格納されている。この予備パス情報は、動的パス計算部３２によって出力される。
残資源ＤＢ３７には、リンクの残資源情報が格納されている。このリンクの残資源情報は、網状態情報収集システム２０によって取得される。
【００４７】
図３（ｂ）は、第１の実施形態に於ける各ノードの情報要素を示している。
経路情報ＤＢ１４には、データ宛先と出力インタフェースとの対応関係が格納されている。このデータ宛先と出力インタフェースとの対応関係の情報は、パス情報やルーチングプロトコルの情報を元に作成される。
【００４８】
網トポロジＤＢ１５には、ノード１０−ｎとリンクとの接続関係が格納されている。このノード１０−ｎとリンクとの接続関係の情報は、ＯＳＰＦ（Open Shortest Path First）などのＩＧＰ（Interior Gateway Protocol）ルーチングプロトコルを用いて取得される。
【００４９】
パス情報ＤＢ１６には、故障発生時の予備パス情報が格納されている。この予備パス情報は、集中管理サーバ３０より送信され、各ノード１０−ｎが必要に応じて、このパス情報ＤＢ１６に格納する。具体的には、自ノード１０−ｎを発着点としないフローのパス情報は保持しない。これにより、各ノード１０−ｎが記憶すべきパス情報を最小限に抑えることが可能である。
【００５０】
（第１の実施形態の動作）
図４（ａ）〜（ｃ）は、第１の実施形態に於ける故障回復パス計算法を示す図である。
図４（ａ）〜（ｃ）に示す通信ネットワーク１００ｂは、ノード１０ｂ−１〜１０ｂ−７を有している。
ノード１０ｂ−１は、ノード１０ｂ−２，１０ｂ−３，１０ｂ−４と通信可能に接続されている。
ノード１０ｂ−２は、ノード１０ｂ−１，１０ｂ−４，１０ｂ−５と通信可能に接続されている。但し、ノード１０ｂ−２とノード１０ｂ−５との間は、高負荷リンクＬＫ−０である。
ノード１０ｂ−３は、ノード１０ｂ−１，１０ｂ−４，１０ｂ−６と通信可能に接続されている。
ノード１０ｂ−４は、ノード１０ｂ−２，１０ｂ−３，１０ｂ−５，１０ｂ−６と通信可能に接続されている。
【００５１】
ノード１０ｂ−５は、ノード１０ｂ−２，１０ｂ−４，１０ｂ−７と通信可能に接続されている。但し、ノード１０ｂ−５とノード１０ｂ−２との間は、高負荷リンクＬＫ−０である。
ノード１０ｂ−６は、ノード１０ｂ−３，１０ｂ−４，１０ｂ−７と通信可能に接続されている。
ノード１０ｂ−７は、ノード１０ｂ−４，１０ｂ−５，１０ｂ−６と通信可能に接続されている。
【００５２】
図４（ａ）では、ノード１０ｂ−４を通るリンクＦＴ−１の故障により、中央のパスＰＦ−０が故障し、ノード１０ｂ−３，１０ｂ−６を経由する下側の予備パスが新たな現用パスＰＰ−１として使用される例を示している。このとき、従来技術の故障回復パス計算法では、残資源を考慮しないため、故障リンクＦＴ−１と新たな現用パスＰＰ−１を構成するリンクとを除いたトポロジＴ１に対して、最小コスト経路を計算する。このとき、最小コスト経路上に高負荷リンクＬＫ−０が存在し、パスの要求帯域を満たせない。このとき、新たな最小コスト経路である新たな予備パスＰＲ−１は、高負荷リンクＬＫ−０によってブロックされる。すなわち、この故障パターンに対しては、新たな予備パスＰＲ−１は設定できない。
【００５３】
図４（ｂ）では、トポロジＴ１から高負荷リンクＬＫ−０を除いたトポロジＴ２を作成し、このトポロジＴ２に対して最短経路計算を行った結果である。要求帯域を満たさない高負荷リンクＬＫ−０を除外して最短経路を計算することにより、この高負荷リンクＬＫ−０によってパスがブロックされる現象を回避可能である。
【００５４】
図４（ｃ）では、要求帯域を満たすリンクにおいても重み付けを行う本アルゴリズムの動作例を示した。
ノード１０ｂ−４とノード１０ｂ−５との間のリンクの残資源量（未使用帯域）は、５Ｇｂｐｓである。ノード１０ｂ−５とノード１０ｂ−７との間のリンクの残資源量（未使用帯域）は、５Ｇｂｐｓである。ノード１０ｂ−４とノード１０ｂ−７との間のリンクの残資源量（未使用帯域）は、０．５Ｇｂｐｓである。
【００５５】
リンクの残資源に応じてリンクの重みを変えることで、最小コスト経路計算時の経路を制御している。例えば、図４（ｂ）ではノード１０ｂ−４とノード１０ｂ−７との間のリンクを経由する経路を選択するが、当該リンクの残資源は０．５Ｇｂｐｓと少ない。このような残資源が少ないリンクを優先的に使用すると、他のフローを計算するときに使用できる資源が限られてしまう。
【００５６】
本実施形態では、残資源が多いリンクから優先的に使用し、フロー全体の資源利用効率を高めている。具体的には、ノード１０ｂ−４とノード１０ｂ−５との間のリンクと、ノード１０ｂ−５とノード１０ｂ−７との間のリンクは、それぞれ５Ｇｂｐｓと多いため、これらのリンクを使用している。
【００５７】
図４（ａ）〜（ｃ）では故障リンクＦＴ−１を経由していた１つのフローに着目した例を示した。しかし、一つの故障箇所には、複数のフローが含まれる場合が多いため、残資源を考慮した故障回復パス計算法は、フロー全体の収容効率を高めるためには重要である。
図５は、第１の実施形態に於ける故障回復パス計算法を示すフローチャートである。
集中管理サーバ３０が故障リンクＸを発見したとき、図５の処理が開始する。
処理が開始すると、ステップＳ１０〜Ｓ１７に於いて、動的パス計算部３２は、故障リンクＸを経由する全フローに対して処理を繰り返す。
【００５８】
ステップＳ１１に於いて、動的パス計算部３２は、当該フローが予備パスを経由するか、現用パスを経由するかを判断する。当該フローが予備パスを経由するならば、ステップＳ１３の処理を行う。当該フローが現用パスを経由するならば、ステップＳ１２の処理を行う。現用パスとは、現用通信経路のことをいう。予備パスとは、予備通信経路のことをいう。
【００５９】
ステップＳ１２に於いて、動的パス計算部３２は、故障リンクＸおよび予備パスを構成するリンクのどちらも含まないトポロジＴ１を作成し、ステップＳ１４の処理を行う。
【００６０】
ステップＳ１３に於いて、動的パス計算部３２は、故障リンクＸおよび現用パスを構成するリンクのどちらも含まないトポロジＴ１を作成し、ステップＳ１４の処理を行う。
【００６１】
ステップＳ１４に於いて、動的パス計算部３２は、フローｆが要求する帯域Ｂ（ｆ）よりも残資源が少ないリンクをトポロジＴ１から除去したトポロジＴ２を作成する。ここで残資源とは、リンクの残帯域のことをいう。
【００６２】
ステップＳ１５に於いて、動的パス計算部３２は、トポロジＴ２上に存在するリンクに対し各リンクの残資源に反比例した重みを与え、この重みを与えた新たなトポロジＴ３を作成する。
具体的には、リンクｌ∈Ｌのリンク重みをｗ（ｌ）、リンクｌの残資源をＡ（ｌ）と表現したとき、以下の式１によってリンクｌの重みを決定する。
ｗ（ｌ）＝ ｉｎｔ｛ｍａｘ＿｛ｉ∈Ｌ｝Ａ（ｉ）／ Ａ（ｌ）｝・・・（式１）
ｍａｘ＿｛ｉ∈Ｌ｝Ａ（ｉ）は、全リンクの中で残資源が最大のリンクの資源量を意味する。ｉｎｔ（ｘ）は、ｘを整数値へ変換することを意味する。
【００６３】
ステップＳ１６に於いて、動的パス計算部３２は、トポロジＴ３に対して、ダイクストラ（Dijkstra）法による最小コスト経路を計算し、動的パスを出力する。
【００６４】
ステップＳ１７に於いて、動的パス計算部３２は、故障リンクＸを経由する全フローに対して処理を繰り返していないならば、ステップＳ１０の処理に戻る。故障リンクＸを経由する全フローに対して処理を繰り返したならば、図５の処理を終了する。
【００６５】
図５の処理により現用パスを構成するリンクのいずれかに故障が発生した際に、予備パスを新たな現用パスとして使用すると共に、新たな予備パスを算出する。前記予備パスを構成するリンクのいずれかに故障が発生した際に、新たな予備パスを算出する。
【００６６】
図６は、第１の実施形態と従来技術に於けるメンテナンス時間と故障発生率ＣＤＦとの関係を示す図である。
図６の横軸はメンテナンス時間であり、縦軸は故障発生率のＣＤＦ（累積分布関数：Cummulative Distribution Function）である。
【００６７】
例えば、メンテナンス時間として７２時間を確保したいモデルを考える。これは、ネットワークに週末に故障が発生しても、運用者は、土日を休み、月曜日に出社したのちにネットワークを故障から復旧させるというモデルである。
【００６８】
従来技術の動的パス設定法では、残資源が足りず動的パスを設定できないケースが多いため、早い段階でグラフが上昇する。一方で、第１の実施形態では動的パスを設定できるケースが多いためグラフの上昇が緩やかとなる。その結果として、従来技術の動的パス設定法では、メンテナンスに７２時間割り当て可能な故障パターンは６０％となる。４０％の故障パターンに於いて、運用者は、ネットワークの故障を７２時間以下で復旧する必要がある。
【００６９】
第１の実施形態の動的パス計算法では、９０％の故障パターンに対してはメンテナンスに７２時間を割り当て可能となる。第１の実施形態の動的パス計算法によれば、ネットワークを７２時間の間、９０％の割合でメンテナンスフリーとすることが可能である。完全にメンテナンスフリーとできない場合であっても、メンテナンスフリーとなるケースを確率的に増加させることが可能である。
【００７０】
図７（ａ），（ｂ）は、第１の実施形態に於ける故障発生の例を示す図である。図７（ａ）は、ネットワーク事業者の作業のガントチャートである。このガントチャートは、横方向が時間軸を示し、右横方向に時間の経過を示している。図７（ｂ）は、ネットワーク事業者が運用する通信ネットワークの概略の構成図である。
【００７１】
図７（ｂ）に示すように、通信ネットワーク１００は、ノード１０−１〜１０−１０と、これらのノード１０−ｎ（ｎ＝１〜１０）相互を接続するリンクとで構成されている。通信路の送信元はノード１０−１である。通信路の宛先は、ノード１０−１０である。現用パスＰＰは、ノード１０−１から、ノード１０−２，１０−９，１０−６を経由して、ノード１０−１０に至る経路である。ノード１０−９とノード１０−６とを接続するリンクの放射状のマークは、このリンクに故障が発生したことを示している。
【００７２】
図７（ａ）に示すように、Ｘ月２日の０時０分に、通信ノード１０−９と通信ノード１０−６とを接続するリンクに故障が発生している。しかし、第１の実施形態の通信ネットワーク１００は、Ｘ月２日の９時００分に１＋１の冗長構成に自動で復旧する。通信ネットワーク１００を管理するネットワーク事業者は、即座に復旧作業を完了する必要はない。この事例では、Ｘ月２日の２１時０分に復旧作業を完了させている。
【００７３】
本実施形態のように、新たな予備パスを自動的に設定すると、故障後においても一定のネットワーク稼働率を担保できるため、故障のメンテナンスに十分な時間を割り当てることが可能となり、ネットワーク事業者が行う保守稼動のコスト、すなわち運用コストを削減可能となる。
【００７４】
本実施形態の故障回復パス計算法は、ネットワーク運用後の故障箇所に応じて新たな予備パスを動的に設定することで、ネットワークが自律的に１＋１の冗長構成に復旧し、故障発生後においても高いネットワーク稼働率を保持する。このため、故障復旧のために十分なメンテナンス時間を確保することが可能となり、夜間メンテナンスを不要とするといった運用コスト削減を実現する。
【００７５】
本実施形態の故障回復パス計算法は更に、ネットワークの残資源を考慮して使用可能な資源を効率的に使用する方法であるため、既に運用中のネットワークへ適用可能であり、かつ、利用可能資源が制限された状況において１＋１の冗長構成に復旧できる割合を増加させることが可能である。
なお、１＋１の冗長構成に復旧できる割合が増加することは、十分なメンテナンス時間を割り当て可能な故障パターンの割合が増加することと等価である。
【００７６】
本実施形態の故障回復パス計算法は、運用後の故障箇所に応じて新たな予備パスを計算する。単一リンク故障に対しては、常に二重化された通信路を提供することが可能となる。予備パスを計算する際には残資源を考慮したパスを計算する。具体的には、パスを計算する際に必要な帯域要件を満たさないリンクを除外するとともに、帯域要件を満たすリンクであってもその残資源に応じて重み付けを行うことで、残資源の多いリンクから優先的に使用する。これにより、与えられた網資源上に収容可能な動的パスの数を最大化する。したがって、既存資源のみで１＋１の冗長構成に復旧できる割合を増加させることが可能となる。
【００７７】
（第１の実施形態の効果）
以上説明した第１の実施形態では、次の（Ａ）〜（Ｃ）のような効果がある。
（Ａ） ネットワーク運用後の故障箇所に応じて、新たな予備パスを動的に設定することで、ネットワークが自律的に１＋１の冗長構成に自動で復旧し、故障発生後においても高いネットワーク稼働率を保持する。このため、故障復旧のために十分なメンテナンス時間を確保することが可能となり、夜間メンテナンスを不要とするといった運用コスト削減を実現する。
【００７８】
（Ｂ） ネットワークの残資源を考慮して使用可能な資源を効率的に使用する方法であるため、既に運用中のネットワークへ適用可能であり、かつ、利用可能資源が制限された状況において１＋１の冗長構成に復旧できる割合を増加させることが可能である。
【００７９】
（Ｃ） １＋１の冗長構成に復旧できる割合が増加することにより、十分なメンテナンス時間を割り当て可能な故障パターンの割合が増加する。
【００８０】
（第２の実施形態の構成）
第２の実施形態の通信ネットワーク１００の構成は、図１に示す第１の実施形態の通信ネットワーク１００の構成と同様である。
【００８１】
（第２の実施形態の動作）
図８（ａ），（ｂ）は、第２の実施形態に於ける故障回復パス計算法を示す図である。図８（ａ）は、トポロジＴ２に対する最小コスト経路を示している。図８（ｂ）は、トポロジＴ３に対する最小コスト経路を示している。
【００８２】
第１の実施形態の故障回復パス計算法では、残資源の多いリンクから優先して使用する経路が計算される。一方で、残資源を考慮することでホップ数の長い経路となりトータルで要求する資源が増加する場合が存在する。
【００８３】
図８（ａ）に示すトポロジＴ２に対する最小コスト経路は、ノード１０ｃ−１からノード１０ｃ−３を経由してノード１０ｃ−７に至る経路である。トポロジＴ２に対する最小コスト経路の要求資源量は、１００Ｍｂｐｓである。
【００８４】
図８（ｂ）に示すトポロジＴ３に対する最小コスト経路は、ノード１０ｃ−１からノード１０ｃ−２〜１０ｃ−６を経由してノード１０ｃ−７に至る経路である。トポロジＴ３に対する最小コスト経路の要求資源量は、３００Ｍｂｐｓである。
【００８５】
図８（ａ）に示すトポロジＴ２に対する最小コスト経路の要求資源量１００Ｍｂｐｓが、図８（ｂ）に示すトポロジＴ３に対する最小コスト経路の要求資源量３００Ｍｂｐｓよりも、明らかに少ない場合は、トポロジＴ２に対する最小コスト経路を採用する。これにより、通信ネットワーク１００の収容効率を向上させることが可能である。
【００８６】
図９は、第２の実施形態に於ける故障回復パス計算法を示すフローチャートである。図５に示す第１の実施形態の故障回復パス計算法を示すフローチャートと同一の要素には同一の符号を付与している。
処理が開始したのち、ステップＳ１０〜Ｓ１５の処理は、図５に示す第１の実施形態の故障回復パス計算法のステップＳ１０〜Ｓ１５の処理と同様である。
【００８７】
ステップＳ２０に於いて、動的パス計算部３２は、トポロジＴ２に対する最小コスト経路と、要求資源量ＲＴ２とを計算する。トポロジＴ２とは、第２のトポロジである。要求資源量ＲＴ２は、第２の要求資源量である。
【００８８】
ステップＳ２１に於いて、動的パス計算部３２は、トポロジＴ３に対する最小コスト経路と、要求資源量ＲＴ３とを計算する。トポロジＴ３とは、第３のトポロジである。要求資源量ＲＴ３は、第３の要求資源量である。
【００８９】
ステップＳ２２に於いて、動的パス計算部３２は、ＲＴ２が（α×ＲＴ３）よりも小さいか否かを判断する。ここで、αは所定値の係数である。ＲＴ２が（α×ＲＴ３）よりも小さいならば（Ｙｅｓ）、ステップＳ２３の処理を行う。ＲＴ２が（α×ＲＴ３）以上ならば（Ｎｏ）、ステップＳ２４の処理を行う。
ステップＳ２３に於いて、動的パス計算部３２は、トポロジＴ２に対する最小コスト経路を動的パスとして採用し、ステップＳ１７の処理を行う。
ステップＳ２４に於いて、動的パス計算部３２は、トポロジＴ３に対する最小コスト経路を動的パスとして採用し、ステップＳ１７の処理を行う。
すなわち、第２の要求資源量に対する第３の要求資源量の比率が所定閾値以上のとき、第２のトポロジの最適経路を、新たな予備通信経路としている。
ステップＳ１７以降の処理は、図５に示す第１の実施形態の故障回復パス計算法のステップＳ１７以降の処理と同様である。
【００９０】
（第２の実施形態の効果）
以上説明した第２の実施形態では、次の（Ｄ）のような効果がある。
（Ｄ） トポロジＴ２に対する最小コスト経路の要求資源量が、トポロジＴ３に対する最小コスト経路の要求資源量よりも、明らかに少ない場合は、トポロジＴ２に対する最小コスト経路を採用する。これにより、通信ネットワーク１００の収容効率を向上させることが可能である。
【００９１】
（変形例）
本発明は、上記実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で、変更実施が可能である。この利用形態や変形例としては、例えば、次の（ａ）〜（ｃ）のようなものがある。
【００９２】
（ａ） 第１、第２の実施形態の故障回復パス算出法では、ダイクストラ法によって最適経路を計算している。しかし、これに限られず、ベルマン−フォード法、または、ワーシャル−フロイド法を用いても良い。
【００９３】
（ｂ） 第１、第２の実施形態の故障回復パス算出法では、網状態情報収集システム２０によって通信ネットワーク１００の状態を取得し、集中管理サーバ３０は、取得した情報に基いて各ノード１０−１〜１０−１０を管理している。しかし、これに限られず、集中管理サーバ３０が自ら通信ネットワーク１００の状態を取得しても良い。
（ｃ） 第１、第２の実施形態の故障回復パス算出法では、第２のトポロジの各リンクに、当該各リンクの残資源帯域に反比例した重みを与えた第３のトポロジを作成し、この第３のトポロジの最適経路を算出している。しかし、これに限られず、第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、この第３のトポロジの最適経路を算出しても良い。例えば、１．０から当該各リンクの残資源帯域の割合を除算した重みを、第２のトポロジの各リンクに付与して第３のトポロジを作成し、この第３のトポロジの最適経路を算出しても良い。同様に、残資源帯域の増加に対して単調減少するいずれの関数を用いても良い。
【符号の説明】
【００９４】
１０−１〜１０−１０ ノード
１０ａ−１〜１０ａ−８ ノード
１０ｂ−１〜１０ｂ−７ ノード
１０ｃ−１〜１０ｃ−７ ノード
ＬＫ−０ 高負荷リンク
Ｘ，ＦＴ−１，ＦＴ−２ 故障リンク
ＰＰ−１，ＰＰ 現用パス（現用通信経路）
ＰＦ−０，ＰＦ−１ 故障パス
ＰＲ−１〜ＰＲ−３ 新たな予備パス（新たな予備通信経路）
１１ データ転送部
１２ プロトコル・シグナリング処理部
１３ サーバ通信部
１４ 経路情報ＤＢ
１５ 網トポロジＤＢ
１６ パス情報ＤＢ
２０ 網状態情報収集システム
３０ 集中管理サーバ
３１ 現用・予備パス計算部
３２ 動的パス計算部
３３ ノード通信部
３４ リンク容量ＤＢ
３５ 網トポロジＤＢ
３６ パス情報ＤＢ
３７ 残資源ＤＢ
Ｔ１ トポロジ（第１のトポロジ）
Ｔ２ トポロジ（第２のトポロジ）
Ｔ３ トポロジ（第３のトポロジ）
ＲＴ２，ＲＴ３ 要求資源量
１００，１００ａ，１００ｂ，１００ｃ 通信ネットワーク
【特許請求の範囲】
【請求項１】
ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、
前記集中管理サーバは更に、
前記通信ネットワークのトポロジと、
送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、
前記処理部は、
前記現用通信経路を構成するリンクのいずれかに故障が発生した際に、前記予備通信経路を新たな現用通信経路とするように前記ノードに指示し、
前記故障が発生したリンク、および、前記新たな現用通信経路を構成するリンクを含まない第１のトポロジを作成し、
前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、
前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、
前記第３のトポロジの最適経路を算出し、
算出した最適経路を新たな予備通信経路として前記記憶部に記憶させる
ことを特徴とする故障回復パス計算方法。
【請求項２】
ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、
前記集中管理サーバは更に、
前記通信ネットワークのトポロジと、
送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、
前記処理部は、
前記予備通信経路を構成するリンクのいずれかに故障が発生した際に、前記故障が発生したリンク、および、前記現用通信経路を構成するリンクを含まない第１のトポロジを作成し、
前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、
前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、
前記第３のトポロジの最適経路を算出し、
算出した最適経路を新たな予備通信経路として前記記憶部に記憶させる
ことを特徴とする故障回復パス計算方法。
【請求項３】
前記処理部は、
前記第３のトポロジの最適経路を、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出する
ことを特徴とする請求項１または請求項２に記載の故障回復パス計算方法。
【請求項４】
前記処理部は、
前記第２のトポロジの最適経路と、前記第２のトポロジの最適経路が要求する資源量である第２の要求資源量と、前記第３のトポロジの最適経路が要求する資源量である第３の要求資源量とを算出し、
前記第２の要求資源量に対する前記第３の要求資源量の比率が所定閾値以上のとき、前記第２のトポロジの最適経路を、前記新たな予備通信経路とする
ことを特徴とする請求項１または請求項２に記載の故障回復パス計算方法。
【請求項５】
前記処理部は、
前記第２のトポロジの最適経路と前記第３のトポロジの最適経路とは、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出する
ことを特徴とする請求項４に記載の故障回復パス計算方法。
【請求項６】
請求項１ないし請求項５のいずれか１項に記載の故障回復パス計算方法によって、冗長構成をとる通信経路を算出する集中管理サーバと、前記集中管理サーバが管理する通信ネットワークと、
を備えたことを特徴とする故障回復パス計算システム。
【請求項１】
ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、
前記集中管理サーバは更に、
前記通信ネットワークのトポロジと、
送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、
前記処理部は、
前記現用通信経路を構成するリンクのいずれかに故障が発生した際に、前記予備通信経路を新たな現用通信経路とするように前記ノードに指示し、
前記故障が発生したリンク、および、前記新たな現用通信経路を構成するリンクを含まない第１のトポロジを作成し、
前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、
前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、
前記第３のトポロジの最適経路を算出し、
算出した最適経路を新たな予備通信経路として前記記憶部に記憶させる
ことを特徴とする故障回復パス計算方法。
【請求項２】
ノードと前記ノード同士のリンクとを有する通信ネットワークの集中管理サーバの処理部が実行する故障回復パス計算方法であって、
前記集中管理サーバは更に、
前記通信ネットワークのトポロジと、
送信元ノードから宛先ノードに至る現用通信経路、および、前記送信元ノードから、前記現用通信経路とは異なるノードを介して前記宛先ノードに至る予備通信経路からなる冗長構成をとる通信経路と、を記憶する記憶部を有しており、
前記処理部は、
前記予備通信経路を構成するリンクのいずれかに故障が発生した際に、前記故障が発生したリンク、および、前記現用通信経路を構成するリンクを含まない第１のトポロジを作成し、
前記第１のトポロジから、要求帯域よりも残資源帯域が少ないリンクを除去した第２のトポロジを作成し、
前記第２のトポロジの各リンクに、当該各リンクの残資源帯域に応じた重みを与えた第３のトポロジを作成し、
前記第３のトポロジの最適経路を算出し、
算出した最適経路を新たな予備通信経路として前記記憶部に記憶させる
ことを特徴とする故障回復パス計算方法。
【請求項３】
前記処理部は、
前記第３のトポロジの最適経路を、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出する
ことを特徴とする請求項１または請求項２に記載の故障回復パス計算方法。
【請求項４】
前記処理部は、
前記第２のトポロジの最適経路と、前記第２のトポロジの最適経路が要求する資源量である第２の要求資源量と、前記第３のトポロジの最適経路が要求する資源量である第３の要求資源量とを算出し、
前記第２の要求資源量に対する前記第３の要求資源量の比率が所定閾値以上のとき、前記第２のトポロジの最適経路を、前記新たな予備通信経路とする
ことを特徴とする請求項１または請求項２に記載の故障回復パス計算方法。
【請求項５】
前記処理部は、
前記第２のトポロジの最適経路と前記第３のトポロジの最適経路とは、ダイクストラ法、ベルマン−フォード法、ワーシャル−フロイド法のいずれか１つによって算出する
ことを特徴とする請求項４に記載の故障回復パス計算方法。
【請求項６】
請求項１ないし請求項５のいずれか１項に記載の故障回復パス計算方法によって、冗長構成をとる通信経路を算出する集中管理サーバと、前記集中管理サーバが管理する通信ネットワークと、
を備えたことを特徴とする故障回復パス計算システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−２５７１２８（Ｐ２０１２−２５７１２８Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１１−１２９６７１（Ｐ２０１１−１２９６７１）
【出願日】平成２３年６月１０日（２０１１．６．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２３年６月１０日（２０１１．６．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]