(57)【特許請求の範囲】
【請求項１】
複数のノードと、前記ノード間で通信を行うためのリンクから構成されるネットワーク内におけるトラヒックを監視し、輻輳の発生を未然に防ぐように通信経路の変更を行うネットワーク制御方法であって、
前記ネットワーク全体は、地理的、物理的、または論理的に複数の制御範囲に分割されるとともに、それら制御範囲を複数まとめることで上位の制御範囲が階層的に設定され、それら制御範囲のそれぞれに、当該制御範囲を制御するネットワーク制御装置が対応付けられており、
最下位層の制御範囲を制御する前記ネットワーク制御装置は、自身の制御範囲内の前記ノードのそれぞれから当該ノードに接続されている前記各リンクの負荷情報を収集して取得し、
前記ネットワーク制御装置のそれぞれは、自身の制御範囲より１つ下位の制御範囲を制御する下位のネットワーク制御装置が存在する場合は、当該下位の制御範囲内を通過する自身の制御対象の各トラヒックについて、当該トラヒックが経由する当該下位の制御範囲内のリンクのなかでリンク負荷の余裕度が最小となっているボトルネックリンクの負荷情報を、当該下位のネットワーク制御装置から取得し、
前記ネットワーク制御装置のそれぞれは、自身の制御範囲より１つ上位の制御範囲を制御する上位のネットワーク制御装置が存在する場合は、自身の制御範囲内のノードから当該上位の制御範囲に流出する各トラヒック、及び、当該上位の制御範囲から自身の制御範囲内のノード宛に流入する各トラヒックについて、当該トラヒックが経由する当該上位の制御範囲内のリンクのなかでリンク負荷の余裕度が最小となっているボトルネックリンクの負荷情報を、当該上位のネットワーク制御装置から取得し、
前記ネットワーク制御装置のそれぞれは、取得した前記ボトルネックリンクを含む各リンクの負荷情報に基づいて、自身の制御範囲内における輻輳の発生を未然に防ぐために経路制御を行うべき自身の制御範囲内のリンクを特定し、自身の制御範囲内における通信経路を変更するときに、前記ボトルネックリンクを含む各リンクの負荷情報に基づいた線形計画問題を解くことで経路変更後の前記各リンクの最大リンク使用率を算出し、いずれの最大リンク使用率も所定の閾値を超えないような経路を決定する
ことを特徴とするネットワーク制御方法。
【請求項２】
請求項１に記載のネットワーク制御方法において、
前記決定された経路にしたがう経路変更の制御は、当該経路変更の対象となるトラヒックを制御する前記ネットワーク制御装置のうち、より下位の前記ネットワーク制御装置を優先して行う
ことを特徴とするネットワーク制御方法。
【請求項３】
請求項１または請求項２に記載のネットワーク制御方法において、
ある階層の複数の前記制御範囲の境界線上に位置するノードと、それらのノード間を接続する仮想的な論理リンクによって当該階層の１つ上位の制御範囲のトポロジを構成する
ことを特徴とするネットワーク制御方法。
【請求項４】
複数のノードと、前記ノード間で通信を行うためのリンクから構成されるネットワーク内におけるトラヒックを監視し、輻輳の発生を未然に防ぐように通信経路の変更を行うネットワーク制御装置であって、
前記ネットワーク全体は、地理的、物理的、または論理的に複数の制御範囲に分割されるとともに、それら制御範囲を複数まとめることで上位の制御範囲が階層的に設定され、それら制御範囲のそれぞれに、当該制御範囲を制御する前記ネットワーク制御装置が対応付けられており、
最下位層の制御範囲を制御する前記ネットワーク制御装置は、自身の制御範囲内の前記ノードのそれぞれから当該ノードに接続されている前記各リンクの負荷情報を収集して取得する情報収集手段を備え、
前記ネットワーク制御装置のそれぞれは、
自身の制御範囲より１つ下位の制御範囲を制御する下位のネットワーク制御装置が存在する場合は、当該下位の制御範囲内を通過する自身の制御対象の各トラヒックについて、当該トラヒックが経由する当該下位の制御範囲内のリンクのなかでリンク負荷の余裕度が最小となっているボトルネックリンクの負荷情報を、当該下位のネットワーク制御装置から取得し、
自身の制御範囲より１つ上位の制御範囲を制御する上位のネットワーク制御装置が存在する場合は、自身の制御範囲内のノードから当該上位の制御範囲に流出する各トラヒック、及び、当該上位の制御範囲から自身の制御範囲内のノード宛に流入する各トラヒックについて、当該トラヒックが経由する当該上位の制御範囲内のリンクのなかでリンク負荷の余裕度が最小となっているボトルネックリンクの負荷情報を、当該上位のネットワーク制御装置から取得する情報交換手段と、
取得した前記ボトルネックリンクを含む各リンクの負荷情報に基づいて、自身の制御範囲内における輻輳の発生を未然に防ぐために経路制御を行うべき自身の制御範囲内のリンクを特定し、自身の制御範囲内における通信経路を変更するときに、前記ボトルネックリンクを含む各リンクの負荷情報に基づいた線形計画問題を解くことで経路変更後の前記各リンクの最大リンク使用率を算出し、いずれの最大リンク使用率も所定の閾値を超えないような経路を決定する経路計算手段と
を備えることを特徴とするネットワーク制御装置。
【請求項５】
請求項４に記載のネットワーク制御装置において、
前記決定された経路にしたがう経路変更の制御は、当該経路変更の対象となるトラヒックを制御する前記ネットワーク制御装置のうち、より下位の前記ネットワーク制御装置を優先して行う
ことを特徴とするネットワーク制御装置。
【請求項６】
請求項４または請求項５に記載のネットワーク制御装置において、
ある階層の複数の前記制御範囲の境界線上に位置するノードと、それらのノード間を接続する仮想的な論理リンクによって当該階層の１つ上位の制御範囲のトポロジを構成する
ことを特徴とするネットワーク制御装置。
【請求項７】
複数のノードと、前記ノード間で通信を行うためのリンクと、請求項４から請求項６のいずれか一項に記載のネットワーク制御装置と
を備えることを特徴とするネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ（Internet Protocol）、Ethernet（登録商標）、Ｐ２Ｐ（Peer-to-Peer）などを用いる通信ネットワークの監視および制御の技術に関する。
【背景技術】
【０００２】
通信ネットワークのトポロジや通信経路は、想定したトラヒックを輻輳等の品質劣化を起こさず、かつ効率的に収容できるように設計される。しかしながら、トラヒック変動が発生し、設計時に想定されたトラヒックと大きく傾向が異なるトラヒックが流れると、輻輳等が発生し、通信品質が維持できなくなることがある。
【０００３】
トラヒック変動発生時にも、輻輳の発生を回避し、適切にトラヒックを収容するための手法として、変動後のトラヒックに合わせて、動的にネットワーク内の通信経路等を再構成するトラヒックエンジニアリング（ＴＥ：Traffic Engineering）と呼ばれる手法が重要視されている。特に近年では、Ｐ２ＰやVideo-on-Demand等のアプリケーションが普及するにつれ、トラヒック変動が大きくなっており、急激なトラヒック変動が頻繁に発生する状況においても通信品質を維持するためには、トラヒック変動に合わせて短い周期でトラヒックエンジニアリングを行う必要が生じる。
【０００４】
ＴＥを行う手法として様々な手法が提案されている（例えば、非特許文献１，２，４）。このうち、非特許文献１，２では、与えられた単一のトラヒック需要行列に対して、そのトラヒック需要を収容する仮想網を設計するための、最適化にもとづく方法、およびヒューリスティックな方法が提案されている。ここでトラヒック需要行列とは、網内の任意の２ノード間のトラヒック需要を行列形式で表示したもので、ネットワーク全体のトラヒック交流を表現する。これら従来のオンライン型ＴＥ制御の多くは、ある２つの時刻におけるトラヒック需要行列が取得可能であること、もしくは、トラヒック需要が周期的かつ緩やかに変動することを仮定している。しかし、大規模な通信ネットワークにおいて正確なトラヒック需要行列を取得することは困難である（例えば、非特許文献３参照）。そこで、より取得が容易なリンク使用率のみを収集し、リンク使用率に合致した通信経路を設計する手法も提案されている（例えば、非特許文献４参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】B. Mukherjee, D. Banerjee, S. Ramamurthy, and A. Mukherjee, “Some principles for designing a wide-area WDM optical network”, IEEE/ACM Transactions on Networking, vol. 4, no. 5, pp. 684-696, 1996.
【非特許文献２】R. Ramaswami and K. N. Sivarajan, “Design of logical topologies for wavelength-routed optical networks”, IEEE Journal on Selected Areas in Communications, vol. 14, pp. 840-851, June 1996.
【非特許文献３】N. Benameur and  J. W. Roberts, “Traffic Matrix Inference in IP Networks”,  NETWORKS AND SPATIAL ECONOMICS , VOL 4; NUMBER 1, pp. 103-114, 2004.
【非特許文献４】I. Juva, “Robust load balancing”, in Proceedings of IEEE Globecom 2007,pp. 2708-2713, Nov 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、この従来の手法では、最適な通信経路を設計する際にかかる計算時間が大きく、大規模ネットワークへの適用は難しい。計算時間の問題に加えて、大規模網では全リンクのトラヒックデータを収集する処理の負荷が高く、実現することが困難である。
【０００７】
また大規模網では、各リンクの輻輳や各ノードの故障の頻度が同一であった場合でも、小規模ネットワークよりも非常に多くの頻度で、ネットワークのいずれかの箇所でトラヒックエンジニアリングによる通信経路等の再構成が行われる。そのため、再構成が必要な度にネットワーク全体で再構成を行うと、ネットワークが不安定になるという問題が生じる。
【０００８】
本発明は、トラヒックデータの収集負荷やネットワークの再構成に係る前記の問題に鑑みてなされたものであり、任意のネットワークトポロジに対して適用可能であって、かつ、制御負荷の削減と安定性の向上を実現するネットワーク制御手法を提供することを課題とする。
【課題を解決するための手段】
【０００９】
前記の課題を解決するために、本発明は、複数のノードと、前記ノード間で通信を行うためのリンクから構成されるネットワーク内におけるトラヒックを監視し、輻輳の発生を未然に防ぐように通信経路の変更を行うネットワーク制御方法であって、前記ネットワーク全体は、地理的、物理的、または論理的に複数の制御範囲に分割されるとともに、それら制御範囲を複数まとめることで上位の制御範囲が階層的に設定され、それら制御範囲のそれぞれに、当該制御範囲を制御するネットワーク制御装置が対応付けられており、最下位層の制御範囲を制御する前記ネットワーク制御装置は、自身の制御範囲内の前記ノードのそれぞれから当該ノードに接続されている前記各リンクの負荷情報を収集して取得し、前記ネットワーク制御装置のそれぞれは、自身の制御範囲より１つ下位の制御範囲を制御する下位のネットワーク制御装置が存在する場合は、当該下位の制御範囲内を通過する自身の制御対象の各トラヒックについて、当該トラヒックが経由する当該下位の制御範囲内のリンクのなかでリンク負荷の余裕度が最小となっているボトルネックリンクの負荷情報を、当該下位のネットワーク制御装置から取得し、前記ネットワーク制御装置のそれぞれは、自身の制御範囲より１つ上位の制御範囲を制御する上位のネットワーク制御装置が存在する場合は、自身の制御範囲内のノードから当該上位の制御範囲に流出する各トラヒック、及び、当該上位の制御範囲から自身の制御範囲内のノード宛に流入する各トラヒックについて、当該トラヒックが経由する当該上位の制御範囲内のリンクのなかでリンク負荷の余裕度が最小となっているボトルネックリンクの負荷情報を、当該上位のネットワーク制御装置から取得し、前記ネットワーク制御装置のそれぞれは、取得した前記ボトルネックリンクを含む各リンクの負荷情報に基づいて、自身の制御範囲内における輻輳の発生を未然に防ぐために経路制御を行うべき自身の制御範囲内のリンクを特定し、自身の制御範囲内における通信経路を変更するときに、前記ボトルネックリンクを含む各リンクの負荷情報に基づいた線形計画問題を解くことで経路変更後の前記各リンクの最大リンク使用率を算出し、いずれの最大リンク使用率も所定の閾値を超えないような経路を決定することを特徴とする。
【００１０】
こうすることにより、上位のネットワーク制御装置は、自身の制御範囲内の下位のネットワーク制御装置から取得したボトルネックリンクに関する集約された情報に基づいて、上位レベルの経路制御を行うことが可能となるため、各ネットワーク制御装置の制御負荷を削減しつつ、ネットワーク全体を通して新たな輻輳を発生させないことを保証する経路制御を実現することができる。
【００１１】
また、本発明は、前記のネットワーク制御方法において、前記決定された経路にしたがう経路変更の制御は、当該経路変更の対象となるトラヒックを制御する前記ネットワーク制御装置のうち、より下位の前記ネットワーク制御装置を優先して行うことを特徴とする。
【００１２】
こうすることにより、輻輳の発生を回避する際には、より下位の階層における経路変更を優先して実施し、可能な限り局所的な経路変更を行うので、ネットワークの安定性を向上させることができる。
【００１３】
また、本発明は、前記のネットワーク制御方法において、ある階層の複数の前記制御範囲の境界線上に位置するノードと、それらのノード間を接続する仮想的な論理リンクによって当該階層の１つ上位の制御範囲のトポロジを構成することを特徴とする。
【００１４】
こうすることにより、ある階層の制御範囲におけるボトルネックリンクに関する情報を保持しつつ、１つ上位の階層のトポロジ構造を簡略化することができ、階層のレベルに応じた粒度での制御が可能となる。
【発明の効果】
【００１５】
本発明によれば、任意のネットワークトポロジに対して適用可能であって、かつ、制御負荷の削減と安定性の向上を実現するネットワーク制御手法を提供することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態に係るネットワークの構成例である。
【図２】ネットワークトポロジと制御範囲の階層化についての説明図である。
【図３】下位と上位の制御範囲及びネットワークトポロジの関係についての説明図である。
【図４】最下位層のネットワーク制御装置の機能構成を示したブロック図である。
【図５】中位層のネットワーク制御装置の機能構成を示したブロック図である。
【図６】ネットワーク制御装置間で交換される集約情報の内容である。
【図７】下位側のネットワーク制御装置から上位側のネットワーク制御装置へ渡す集約情報の生成についての説明図である。
【図８】下位から上位へ渡す集約情報の生成結果のデータ例である。
【図９】上位側のネットワーク制御装置から下位側のネットワーク制御装置へ渡す集約情報の生成についての説明図である。
【図１０】上位から下位へ渡す集約情報の生成結果のデータ例である。
【図１１】情報集約処理の手順を示すフローチャートである。
【図１２】経路計算処理の手順を示すフローチャートである。
【図１３】下位と上位のネットワーク制御装置間の動作の連係を説明するためのシーケンスチャートである。
【図１４】輻輳の発生を回避するための経路制御の例である。
【図１５】輻輳の発生を回避するための経路制御の他の例である。
【発明を実施するための形態】
【００１７】
以下、本発明を実施するための形態を、適宜図面を参照しながら詳細に説明する。
図１は、本発明の実施形態に係るネットワークの構成例である。図１に示すように、通信ネットワーク１は、トラヒックの始点及び終点となる多数のノードＮと、それらのノード間で通信を行うためのリンクＬとから構成される。また、通信ネットワーク１のトラヒックを監視して輻輳の発生を未然に防ぐように通信経路の変更を行うネットワーク制御装置２が複数設置されている。
【００１８】
図２は、ネットワークトポロジと制御範囲の階層化についての説明図である。図２において、太い破線で示した各ネットワーク制御装置２（２Ｌ，２Ｍ，２Ｈ）が受けもつ制御範囲３（３Ｌ，３Ｍ，３Ｈ）は、境界ノードＢＮ（Boundary Node）を境界として他の制御範囲と連結されるとともに、階層的に構成されている。また、制御範囲内に含まれるそれ以外のノードをローカルノードＬＮ（Local Node）と呼ぶ。さらに、自身の制御範囲外のノードであって、自身の制御範囲との間でトラヒックが発生しているノード（図では白い丸印にて表記）を外部ノードＥＮ（External Node）と呼ぶ。
【００１９】
最下位層の制御範囲３Ｌは、通信ネットワーク全体を適度な大きさの領域に分割することによって設定される。この分割は、ノードやリンクの所在場所などの地理的条件、通信リンクの帯域などの物理的条件、設備の管理元などの論理的条件等、いずれの条件に基づくものであってもよく、最下位層の各ネットワーク制御装置２Ｌの制御負荷を概ね同等レベルとするために、制御対象のノード数やリンク数が概ね均等となるように分割するのが好ましい。
【００２０】
分割の方法としては、任意の分割方法が適用可能であるが、例えば、目標とする最下位層の制御範囲３Lの数と同数のノードを各制御範囲の代表ノードとして通信ネットワーク１内からランダムに選択し、通信ネットワーク１内の各リンクＬと選択された各代表ノードとのホップ数を計算して、最もホップ数が小さい代表ノードと同じ制御範囲３Ｌに当該リンクＬを含める、という手順で分割することが考えられる。
【００２１】
また、図２の例では、最下位層の制御範囲３Ｌを複数まとめることで中位層の制御範囲３Ｍを設定し、さらにすべての中位層の制御範囲３Ｍをまとめて通信ネットワーク全体を包含する最上位層の制御範囲３Ｈを設定している。図２の例では、３階層の制御範囲を設定しているが、ネットワークの規模が小さいときには２階層としてもよく、ネットワークの規模が大きいときには中位層を多段化して４階層以上の構成としてもよい。
【００２２】
なお、このような階層的な制御範囲の構成は、各ネットワーク制御装置２が制御する範囲を決めるためのものであり、制御対象の通信ネットワーク自体が階層的に構成されている必要はなく、任意のネットワークトポロジに対して適用することができる。
【００２３】
それぞれの制御範囲３（３Ｌ，３Ｍ，３Ｈ）には、当該制御範囲内の制御を司るネットワーク制御装置２（２Ｌ，２Ｍ，２Ｈ）が対応付けられる。これらネットワーク制御装置２は、通信機能を有するコンピュータによって構成される。なお、コンピュータの処理性能が高ければ１台のネットワーク制御装置２が複数の制御範囲３を制御するものとしてもよい。
【００２４】
図３は、下位と上位の制御範囲及びネットワークトポロジの関係についての説明図である。図３の下側のグラフは、下位層側の制御範囲３（この例では３Ｌ）に対応するトポロジ構造を示したものであり、太い破線はある制御範囲３Ｌの境界線を表している。黒い丸印で示す当該制御範囲内の制御対象ノードは、境界線の内部に位置するローカルノードＬＮと、境界線上に位置する境界ノードＢＮとに分類される。２つの制御範囲間のトラヒック転送は、すべて境界ノードＢＮを介して行われる。他の制御範囲については、自身の制御範囲との間のトラヒックが存在する他制御範囲の境界ノードＢＮを白い丸印で示す外部ノードＥＮとしてトポロジ構造に含め、また、各外部ノードＥＮと自身の境界ノードＢＮとの間には仮想的なリンクである外部リンクＥＬを設定する。
【００２５】
図３の上側のグラフは、上位層側の制御範囲３（この例では３Ｍ）に対応するトポロジ構造を示したものであり、太い破線は制御範囲３Ｍの境界線を表している。この上位層側のトポロジ構造には、下位層側の各制御範囲３Ｌにおける境界ノードＢＮを制御対象ノードとして含め、また、下位層側の同一の制御範囲３Ｌに含まれる境界ノードＢＮに対応する制御対象ノード間には仮想的なリンクである論理リンクＬＬ（Logical Link）を設定する。他の制御範囲については、自身の制御範囲との間のトラヒックが存在する他制御範囲の境界ノードＢＮを外部ノードＥＮとしてトポロジ構造に含め、各外部ノードＥＮと自身の境界ノードＢＮとの間には外部リンクＥＬを設定する。
【００２６】
このように、上位層側のトポロジ構造を、下位層側の境界ノードＢＮだけに限定して構成することにより、より広い制御範囲の制御を司る上位層側のネットワーク制御装置２が制御対象とするトポロジ構造を簡略化することができる。
【００２７】
図３の太い破線矢印は、それぞれのネットワークトポロジにおいて、経路変更を行うことを許可するトラヒックである制御対象トラヒックの例を示すものである。経路制御を行うことが不適切なトラヒックは制御対象トラヒックから除外される。制御対象トラヒックには、図３の下側のグラフに例示したような、外部ノードＥＮを始点として自身の制御範囲を経由して他の外部ノードＥＮに至るトラヒックや、図３の上側のグラフに例示したような、外部ノードＥＮと自身の制御範囲内のノードのいずれか一方を始点とし他方を終点とするトラヒックのほかに、自身の制御範囲内のノード間のトラヒックがある。
【００２８】
図４及び図５は、ネットワーク制御装置２の機能構成を示したブロック図であり、図４には最下位層のネットワーク制御装置２Ｌの機能構成を、図５には中位層のネットワーク制御装置２Ｍの機能構成を示している。
【００２９】
図４に示すように、最下位層のネットワーク制御装置２Ｌは、トラヒック情報収集部２１、集約情報生成部２２Ｌ、トラヒック情報交換部２３Ｌ、経路計算部２４Ｌ、及び経路制御部２５Ｌを備えて構成される。これらは、ネットワーク制御装置２Ｌが備える不図示のＣＰＵ（Central Processing Unit）が所定のプログラムを実行することによって具現化される。また、ネットワーク制御装置２Ｌは、ネットワークトポロジの情報を保持するトポロジＤＢ（Database）２６、トラヒック情報を保持するトラヒックＤＢ２７、及び通信経路情報を保持する経路ＤＢ２８を備える。
【００３０】
トラヒック情報収集部２１は、自身の制御範囲３L内に含まれる各リンクＬの負荷（転送トラヒック量）についての情報である収集トラヒック情報を、定期的に各ノードＮから収集する。収集対象のリンクＬには、各ノードＮに接続される端末などを始点及び終点とする入力リンク及び出力リンク（不図示）を含む。
【００３１】
集約情報生成部２２Ｌは、上位のネットワーク制御装置２Ｍまたは２Ｈに渡す集約情報を生成する。集約情報の生成方法については後記する。トラヒック情報交換部２３Ｌは、集約情報生成部２２Ｌが生成した集約情報を上位のネットワーク制御装置２Ｍまたは２Ｈに送信し、上位のネットワーク制御装置２Ｍまたは２Ｈによって生成された外部リンクＥＬの負荷についての集約情報を交換トラヒック情報として受信する。
【００３２】
経路計算部２４Ｌは、収集トラヒック情報及び交換トラヒック情報に基づいて、自身の制御範囲３Ｌ内での輻輳の発生を回避するように、自身の制御範囲３Ｌ内における代替の通信経路を算出する。このとき、上位のネットワーク制御装置２Ｍまたは２Ｈから取得した交換トラヒック情報を参照することにより、いずれの外部リンクＥＬにも輻輳を発生させないような通信経路を選定する。経路制御部２５Ｌは、経路計算部２４Ｌが算出した通信経路となるように、自身の制御範囲３Ｌ内の各ノードに指示して実際に通信経路を変更させる処理を行う。
【００３３】
図５に示すように、中位層のネットワーク制御装置２Ｍは、集約情報生成部２２Ｍ、トラヒック情報交換部２３Ｍ、経路計算部２４Ｍ、及び経路制御部２５Ｍを備えて構成される。これらは、ネットワーク制御装置２Ｍが備える不図示のＣＰＵが所定のプログラムを実行することによって具現化される。また、ネットワーク制御装置２Ｍは、ネットワークトポロジの情報を保持するトポロジＤＢ２６、トラヒック情報を保持するトラヒックＤＢ２７、及び通信経路情報を保持する経路ＤＢ２８を備える。図示は省略するが、最上位層のネットワーク制御装置２Ｈも、同様な構成を有する。
【００３４】
集約情報生成部２２Ｍは、上位のネットワーク制御装置２Ｍまたは２Ｈに渡す集約情報及び下位のネットワーク制御装置２Ｌまたは２Ｍに渡す集約情報をそれぞれ生成する。集約情報の生成方法については後記する。トラヒック情報交換部２３Ｍは、集約情報生成部２２Ｍが生成したそれぞれの集約情報を上位のネットワーク制御装置２Ｍまたは２Ｈ及び下位のネットワーク制御装置２Ｌまたは２Ｍにそれぞれ送信し、下位のネットワーク制御装置２Ｌまたは２Ｍによって生成された論理リンクＬＬの負荷についての集約情報と、上位のネットワーク制御装置２Ｍまたは２Ｈによって生成された外部リンクＥＬの負荷についての集約情報とを、それぞれ交換トラヒック情報として受信する。
【００３５】
経路計算部２４Ｍは、交換トラヒック情報に基づいて、自身の制御範囲３Ｍ内での輻輳の発生を回避するように、自身の制御範囲３Ｍ内における代替の通信経路を算出する。このとき、上位のネットワーク制御装置２Ｍまたは２Ｈから取得した交換トラヒック情報を参照することにより、いずれの外部リンクＥＬにも輻輳を発生させない通信経路を選定する。経路制御部２５Ｍは、経路計算部２４Ｍが算出した通信経路となるように、下位のネットワーク制御装置２Ｌまたは２Ｍに指示して実際に通信経路を変更させる処理を行う。
【００３６】
図６は、ネットワーク制御装置間で交換される集約情報（交換トラヒック情報）の内容である。集約情報は、情報を引き渡す各ボトルネックリンクについての以下のような情報から構成される。
・リンクの帯域：  当該リンクに流せる最大トラヒック量
・リンクの負荷：  当該リンクの現在のトラヒック量
・制御対象トラヒックのノードペアとリンクを経由する割合：  情報送信先のネットワーク制御装置の制御対象トラヒックのうち、当該リンクを経由するものの始点・終点ノードペアの集合と、当該ノードペア間のトラヒックが当該リンクを経由する割合
・制御対象トラヒック量の上限値及び下限値：  当該リンクを流れているトラヒックのうち、情報送信先のネットワーク制御装置の制御対象トラヒック量の上限値及び下限値
【００３７】
図７は、下位側のネットワーク制御装置から上位側のネットワーク制御装置へ渡す集約情報の生成についての説明図である。図７の下側のグラフは、下位側のネットワーク制御装置２Ｌまたは２Ｍが保持しているトポロジ構造とトラヒック情報を表し、図７の上側のグラフは、それが集約されて上位側のネットワーク制御装置２Ｍまたは２Ｈに引き渡されるトポロジ構造とトラヒック情報を表している。丸印はノードＮ、矢印はリンクＬを表す。各リンクＬは、送信側のノード名と受信側のノード名との組合せにより、例えばＡ→Ｂのように表すものとする。また、各リンクに付されている「１００Ｍ」などの値は、当該リンクのリンク負荷であり、「Ｍ」は、「メガビット／秒」を意味する。
【００３８】
図８は、下位から上位へ渡す集約情報の生成結果のデータ例である。図８の左上の表に示したリンク負荷情報は、図７の下側のグラフの各リンクのリンク負荷を表したものである。また、図８の右上の表に示した制御対象トラヒックと経路情報は、上位側のネットワーク制御装置２Ｍまたは２Ｈの制御対象トラヒックの下位側の制御範囲における通信経路の情報を表したものである。この例では、上位側のノードペアＡ→Ｄを経由する制御対象トラヒックは、１００％の割合で下位側のＡ→Ｂ→Ｃ→Ｄの経路を経由し、上位側のノードペアＡ→Ｃを経由する制御対象トラヒックは、１００％の割合で下位側のＡ→Ｂ→Ｃの経路を経由し、上位側のノードペアＣ→Ｄを経由する制御対象トラヒックは、１００％の割合で下位側のＣ→Ｄの経路を経由するものとなっている。
【００３９】
説明を簡単にするために、ここでは、下位側の各リンクの帯域はすべて等しいものと仮定すると、リンク負荷が大きいほど輻輳が発生するまでのトラヒックの余裕度が小さくなるので、例えば、上位側のノードペアＡ→Ｄを経由する制御対象トラヒックに対しては、そのトラヒックが経由する３つのリンクＡ→Ｂ、リンクＢ→Ｃ、リンクＣ→Ｄのうちリンク負荷が最も大きいリンクＢ→Ｃがボトルネックリンクとなる。同様に、リンクＢ→Ｃは、上位側のノードペアＡ→Ｃを経由する制御対象トラヒックに対してもボトルネックリンクとなり、上位側のノードペアＣ→Ｄを経由する制御対象トラヒックに対しては、リンクＣ→Ｄがボトルネックリンクとなる。
【００４０】
このようにして特定されるそれぞれの上位側の制御対象トラヒックに対するボトルネックリンクの情報をまとめてテーブル化したものが、図８の下側の表に示した集約情報である。なお、集約情報のうちの上限値及び下限値については、後記にて説明する。また、集約情報のうちのリンク識別情報は、リンク負荷情報との対応を示すために便宜的に付加したものであり、上位側のネットワーク制御装置２Ｍまたは２Ｈに引き渡す集約情報に含めなくてもよい。また、図８の下側の表に示した集約情報に対応するトポロジ構造は、図７の上側のグラフのように、下位側のトポロジ構造における各境界ノードＢＮ同士が、それぞれ上位側の制御対象トラヒックに対応するボトルネックリンクの属性を有する仮想的なリンクである論理リンクＬＬによって接続されているものとして表すことができる。
【００４１】
図９は、上位側のネットワーク制御装置から下位側のネットワーク制御装置へ渡す集約情報の生成についての説明図である。図９の上側のグラフは、上位側のネットワーク制御装置２Ｍまたは２Ｈが保持しているトポロジ構造とトラヒック情報を表し、図９の下側のグラフは、それが集約されて下位側のネットワーク制御装置２Ｌまたは２Ｍに引き渡されるトポロジ構造とトラヒック情報を表している。
【００４２】
図１０は、上位から下位へ渡す集約情報の情報集約結果のデータ例である。図１０の上側の表に示したトラヒック情報は、図９の上側のグラフの各論理リンクＬＬのリンク負荷等を表したものである。これらの情報は、下位側の各ネットワーク制御装置２Ｌまたは２Ｍから引き渡される集約情報を統合することによって生成される。
【００４３】
ここでは、上位側のネットワーク制御装置２Ｍまたは２Ｈから、図９の破線で示した制御範囲を受けもつ下位側のネットワーク制御装置２Ｌまたは２Ｍに引き渡す集約情報の生成方法について説明する。上位から下位へ引き渡す集約情報は、下位側の制御範囲内のノードを終点とする制御対象トラヒックに対するボトルネックリンクの情報と、下位側の制御範囲内のノードを始点とする制御対象トラヒックに対するボトルネックリンクの情報である。
【００４４】
例えば、図１０の上側の表に示したトラヒック情報において、ノードＧからノードＡに流入する制御対象トラヒックについては、制御対象ノードペアＧ→Ａが制御対象ノードペアのリストに含まれる、リンクＧ→Ｈ（リンク負荷：１００Ｍ）とリンクＨ→Ａ（リンク負荷：４００Ｍ）の２つのリンクを経由するが、そのうちリンク負荷が大きいリンクＨ→Ａの方がボトルネックリンクとなる。同様に、ノードＡ、ノードＣ、ノードＤに流入するすべての制御対象トラヒックと、ノードＡ、ノードＣ、ノードＤから流出するすべての制御対象トラヒックについて、当該トラヒックが経由するリンクのうち最もリンク負荷が大きいリンクがボトルネックリンクとなる。
【００４５】
このようにして特定されるそれぞれのボトルネックリンクの情報をまとめてテーブル化したものが、図１０の下側の表に示した集約情報である。なお、集約情報のうちの上限値及び下限値については、後記にて説明する。また、集約情報のうちのリンク識別情報は、トラヒック情報との対応を示すために便宜的に付加したものであり、下位側のネットワーク制御装置２Ｌまたは２Ｍに引き渡す集約情報に含めなくてもよい。また、図１０の下側の表に示した集約情報に対応するトポロジ構造は、図９の下側のグラフのように、上位側のトポロジ構造におけるノードが下位側の外部ノードＥＮとなり、各外部ノードＥＮと各境界ノードＢＮ（ノードＡ，ノードＣ，ノードＤ）間が、それぞれ上位側の制御対象トラヒックに対応するボトルネックリンクの属性を有する仮想的なリンクである外部リンクＥＬによって接続されているものとして表すことができる。
【００４６】
図１１は、情報集約処理の手順を示すフローチャートである。以下、図１１のフローチャートに沿って各ネットワーク制御装置２の集約情報生成部２２が実行する情報集約処理の動作を詳しく説明する。
【００４７】
トラヒック情報収集部２１やトラヒック情報交換部２３による定期的なトラヒック情報の収集が完了すると、集約情報の送信先のネットワーク制御装置２ごとに、この情報集約処理が起動される。
【００４８】
まず、ステップＳ１１では、集約の対象となる制御対象トラヒックに該当するノードペアである制御対象ノードペアを選択し、ステップＳ１２では、すべての制御対象ノードペアの選択が終了したか否かを判定する。
【００４９】
すべての制御対象ノードペアの選択が終了した場合、つまり、まだ選択していない制御対象ノードペアがなかった場合は（ステップＳ１２で「Ｙｅｓ」）、処理を終了する。制御対象ノードペアが選択された場合、つまり、まだ選択していない制御対象ノードペアがあった場合は（ステップＳ１２で「Ｎｏ」）、ステップＳ１３にて、そのノードペア間のトラヒックが自身の制御範囲を経由する通信経路のなかで、輻輳までのトラヒックの余裕度が最小となっているリンクであるボトルネックリンクを特定する。このとき、最も少ないトラヒック量の増加によって、リンクの使用率（＝リンク負荷／リンクの帯域）が所定の閾値を超えるリンクを余裕度が最小であると判定する。
【００５０】
次に、ステップＳ１４では、特定したボトルネックリンクを経由する制御対象トラヒックが当該リンクを経由する割合を経路情報（経路ＤＢ２８）から抽出し、集約情報に含める。次に、ステップＳ１５では、それら制御対象トラヒックの合計トラヒック量の上限値及び下限値を算出して、集約情報に含める。このとき、集約情報の送信先が上位側のネットワーク制御装置２である場合は、当該リンクを経由する制御対象トラヒックのうち、自身の制御範囲外が始点及び終点となる（自身の制御範囲内を通過する）トラヒックの合計トラヒック量の上限値及び下限値を、自身が取得したトラヒック情報を制約条件とする線形計画問題を解くことによって算出する。また、集約情報の送信先が下位側のネットワーク制御装置２である場合は、当該リンクを経由する制御対象トラヒックのうち、当該下位側のネットワーク制御装置２の制御範囲内のノードがそれぞれ始点及び終点となるトラヒックの合計トラヒック量の上限値及び下限値を、自身が取得したトラヒック情報を制約条件とする線形計画問題を解くことによって算出する。ステップＳ１５を実行したのち、ステップＳ１１に戻って前記の処理を繰り返す。
【００５１】
ここで、集約情報に含める前記上限値及び下限値の算出方法について説明する。この上限値及び下限値は、それぞれのボトルネックリンクを流れているトラヒックのうちの、集約情報の送信先のネットワーク制御装置２が通信経路を変更可能なトラヒックの総量の範囲を示すものである。この上限値及び下限値は、以下のような線形計画問題を解くことによって算出することができる。
【００５２】
すべての始点・終点のノードペア間の各トラヒック量（０以上の値であり、負となることはない）を変数として、自身の制御範囲内に含まれるそれぞれのリンクについて、「各ノードペア間のトラヒック量に当該リンクを経由する割合を掛けた値を総和して求められる総トラヒック量は、実際に計測された当該リンクの負荷（＝トラヒック量）に等しい」という、リンク数分の式からなる連立方程式を作成する。そして、この連立方程式が成り立つという制約条件の下で、当該ボトルネックリンクを流れているトラヒックのうちの、集約情報の送信先のネットワーク制御装置２が通信経路を変更可能なトラヒックの総量を目的関数として、その目的関数の最大化及び最小化を行う２つの線形計画問題を解く。これによって求められたトラヒックの総量の最大値及び最小値を、それぞれ前記の上限値及び下限値として集約情報に埋め込む。
【００５３】
これにより、下位側のネットワーク制御装置２Ｌまたは２Ｍは、自身の制御範囲内の境界ノードＢＮ同士の間を通過する各制御対象トラヒックについて、自身の制御範囲内を流れる経路におけるボトルネックリンクを特定し、そのボトルネックリンクを流れている他の制御対象トラヒックをも含めた制御対象トラヒックの総量の上限値及び下限値を上位側のネットワーク制御装置２Ｍまたは２Ｈに通知する。また、上位側のネットワーク制御装置２Ｍまたは２Ｈは、下位側の制御範囲内のノードを始点または終点とする各制御対象トラヒックについて、自身の制御範囲内を流れる経路におけるボトルネックリンクを特定し、そのボトルネックリンクを流れている他の制御対象トラヒックをも含めた制御対象トラヒックの総量の上限値及び下限値を下位側のネットワーク制御装置２Ｌまたは２Ｍに通知する。
【００５４】
次に、 集約情報に基づいて新たな輻輳を生じないことを保証しつつ通信経路の変更を行うための経路計算処理について説明する。この経路計算処理においては、各ネットワーク制御装置２は、自身の制御範囲内のトラヒック情報に加え、上位側のネットワーク制御装置２から取得した自身の制御範囲外についての集約されたトラヒック情報に基づいて、自身の制御範囲外においても新たな輻輳を生じさせないことを保証しつつ、自身の制御範囲内における代替の通信経路を計算する。
【００５５】
図１２は、経路計算処理の手順を示すフローチャートである。以下、図１２のフローチャートに沿って各ネットワーク制御装置２の経路計算部２４が実行する経路計算処理の動作を詳しく説明する。
【００５６】
トラヒック情報収集部２１やトラヒック情報交換部２３による定期的なトラヒック情報の収集が完了すると、この経路計算処理が起動される。
【００５７】
まず、ステップＳ２１では、取得した自身の制御範囲内のトラヒック情報から輻輳対策が必要なリンクを特定する。このとき、リンクの使用率が所定の閾値（例えば０．８）を超えているリンクは輻輳対策が必要と判定する。ここでは、輻輳対策が必要なリンクが特定されたものとして説明を続ける。
【００５８】
次に、ステップＳ２２では、特定された当該リンクを経由する制御対象トラヒックに該当するノードペアを選択し、ステップＳ２３では、すべての制御対象ノードペアの選択が終了したか否かを判定する。すべての制御対象ノードペアの選択が終了した場合、つまり、まだ選択していない制御対象ノードペアがなかった場合は（ステップＳ２３で「Ｙｅｓ」）、ステップＳ２９にて代替経路なしと判断して処理を終了する。制御対象ノードペアが選択された場合、つまり、まだ選択していない制御対象ノードペアがあった場合は（ステップＳ２３で「Ｎｏ」）、ステップＳ２４にて、そのノードペア間のトラヒックについて、ステップＳ２１で特定されたリンクを通らない他の通信経路の候補を任意の経路選択手法によって選択し、ステップＳ２５では、すべての経路の候補の選択が終了したか否かを判定する。
【００５９】
すべての経路の候補の選択が終了した場合、つまり、まだ選択していない経路の候補がなかった場合は（ステップＳ２５で「Ｙｅｓ」）、当該ノードペア間のトラヒックについては適当な候補の経路がないので、ステップＳ２２に戻って次の制御対象ノードペアを選択して前記の処理を繰り返す。他の経路の候補が選択された場合、つまり、まだ選択していない経路の候補があった場合は（ステップＳ２５で「Ｎｏ」）、ステップＳ２６にて、自身がトラヒック情報を有するすべてのリンクについて経路変更後の最大トラヒック量を算出し、ステップＳ２７にていずれかのリンクに輻輳が発生するか否か、つまり、リンクの使用率が所定の閾値を超えるリンクが生じるか否かを判定する。
【００６０】
このとき、ステップＳ２６では、収集したトラヒック情報や集約情報から、経路変更が必要なリンクを特定するとともに、自身が制御可能なトラヒックの総量の上限値及び下限値を取得したのち、前記のような各リンクの総トラヒック量についての連立方程式に加えて、当該制御対象トラヒックの総量が前記上限値と下限値との範囲内に収まるという制約条件を付加した上で、すべての始点・終点のノードペア間の各トラヒック量を変数として、経路変更後の全リンクのなかの最大リンク使用率を求めるという線形計画問題を解く。
【００６１】
いずれかのリンクに輻輳が発生する場合は（ステップＳ２７で「Ｙｅｓ」）、ステップＳ２４に戻って別の経路の候補を選択して前記の処理を繰り返す。いずれのリンクにも輻輳が発生しない場合は（ステップＳ２７で「Ｎｏ」）、ステップＳ２８にて、選択している候補の経路を代替経路として確定して処理を終了する。
【００６２】
ここで、経路変更後の各リンクの最大トラヒック量は、
（当該リンクを経由する制御対象トラヒック以外のトラヒックの最大トラヒック量）
＋（当該リンクを経由する制御対象トラヒックの最大トラヒック量）
である。このうち、（当該リンクを経由する制御対象トラヒック以外のトラヒックの最大トラヒック量）は、自身が有している当該リンクのリンク負荷と、当該リンクを経由している制御対象トラヒックの合計トラヒック量の上限値及び下限値から求めることができる。また、（当該リンクを経由する制御対象トラヒックの最大トラヒック量）は、
（各制御対象トラヒックのトラヒック量）
×（当該制御対象トラヒックが当該リンクを経由する割合）
を各制御対象トラヒックについて合計した値である。この（各制御対象トラヒックのトラヒック量）は、各制御対象トラヒックのトラヒック量を変数とし、自身が有しているトラヒック情報に含まれる、各リンク上の制御対象トラヒックの合計トラヒック量の上限値及び下限値を制約条件とする線形計画問題を解くことによって、求めることができる。
【００６３】
続いて、階層化された複数のネットワーク制御装置が連係して輻輳の発生を回避する動作について説明する。図１３は、下位と上位の２台のネットワーク制御装置間の動作の連係を説明するためのシーケンスチャートである。ここでは、最下位層のネットワーク制御装置２Ｌとその上位のネットワーク制御装置２Ｍとが連係する場合を例に説明する。
【００６４】
下位のネットワーク制御装置２Ｌは、自身の制御範囲内の各ノードから定期的にトラヒック情報を収集し（ステップＳ３１）、収集したトラヒック情報から上位のネットワーク制御装置２Ｍに送信すべき集約情報を生成する（ステップＳ３２）。次に、生成した集約情報を上位のネットワーク制御装置２Ｍに送信し（ステップＳ３３：トラヒック情報交換）、上位のネットワーク制御装置２Ｍはその集約情報を受信する（ステップＳ４１：トラヒック情報交換）。
【００６５】
上位のネットワーク制御装置２Ｍは、他の下位のネットワーク制御装置２Ｌ及び自身の上位のネットワーク制御装置２Ｍまたは２Ｈからも必要な集約情報を取得したのち、下位のネットワーク制御装置２Ｌに送信すべき集約情報を生成し（ステップＳ４２）、生成した集約情報を下位のネットワーク制御装置２Ｌに送信する（ステップＳ４３：トラヒック情報交換）。
【００６６】
下位のネットワーク制御装置２Ｌは、その集約情報を受信し（ステップＳ３４：トラヒック情報交換）、自身が収集した制御範囲内のトラヒック情報と、上位のネットワーク制御装置２Ｍから取得した集約情報に含まれるトラヒック情報とに基づいて、輻輳の発生を未然に防ぐための経路計算を行い（ステップＳ３５）、自身の制御範囲内で適切な代替経路が見つかった場合は（ステップＳ３６で「Ｙｅｓ」）、その代替経路へ移行するための経路制御を実行する（ステップＳ３８）。
【００６７】
他方、自身の制御範囲内では適切な代替経路が見つからない場合は（ステップＳ３６で「Ｎｏ」）、上位のネットワーク制御装置２Ｍから新たな経路設定情報が送信されてくるのを待ち、当該情報を受信したら（ステップＳ３７）、経路設定情報で指示された経路に切り替える経路制御を実行する（ステップＳ３８）。
【００６８】
一方、上位のネットワーク制御装置２Ｍも、自身の下位の各ネットワーク制御装置２Ｌから取得した集約情報に含まれるボトルネックリンクについてのトラヒック情報に基づいて、自身の制御範囲内での経路変更によって輻輳の発生を未然に防ぐための経路計算を行い（ステップＳ４４）、適切な代替経路が見つかった場合は（ステップＳ４５で「Ｙｅｓ」）、その代替経路へ移行するための経路設定情報を生成して該当する下位のネットワーク制御装置２Ｌに通知する（ステップＳ４６）。適切な代替経路が見つからなかった場合については（ステップＳ４５で「Ｎｏ」）図示を省略するが、さらに上位のネットワーク制御装置２Ｍまたは２Ｈがあればその指示を待ち、なければ何もしない。
【００６９】
このように、下位のネットワーク制御装置２Ｌが適切な代替経路を見つけた場合は、その代替経路への移行を優先して行い、適切な代替経路が見つからない場合に上位のネットワーク制御装置２Ｍが見つけた広範囲に亘る代替経路を採用することにより、経路変更の影響範囲をできるだけ局所化し、ネットワーク全体の安定性向上を実現することができる。 
【００７０】
最後に、輻輳の発生を未然に防ぐための経路制御の例を説明する。図１４及び図１５は、輻輳の発生を未然に防ぐための経路制御の例である。ここでは、各リンクの帯域はすべて１ギガビット／秒であり、リンク使用率が０．８以上となったリンクを経路制御の対象とするものとする。
【００７１】
図１４の上側のグラフでは、経路変更前の状態において、ノードＥからノードＦに至る４００メガビット／秒の制御対象トラヒックと、ノードＡからノードＣに至る４００メガビット／秒の制御対象トラヒックとが、いずれもリンクＡ→ＤとリンクＤ→Ｃを経由しているために、この２つのリンクのリンク使用率が０．８となっている。この場合、例えばノードＡからノードＣに至る制御対象トラヒックの経路をＡ→Ｂ→Ｃのように変更すれば、下側のグラフのように、すべてのリンクのリンク使用率を０．４とすることができる。
【００７２】
図１５の上側のグラフでは、経路変更前の状態において、ノードＧからノードＨに至る４００メガビット／秒の制御対象トラヒックと、ノードＤからノードＩに至る４００メガビット／秒の制御対象トラヒックとが、いずれもリンクＤ→Ｃを経由しているために、このリンクのリンク使用率が０．８となっている。この場合、例えばノードＧからノードＨに至る制御対象トラヒックの経路をＧ→Ａ→Ｂ→Ｈのように変更すれば、下側のグラフのように、すべてのリンクのリンク使用率を０．４以下とすることができる。
【００７３】
以上説明したように、本発明によれば、最下位層のネットワーク制御装置は、収集するトラヒック情報の範囲が局所化されるので、高速かつ頻繁に情報収集を行うことが可能となる。また、より広い範囲のトラヒック情報を把握すべき上位のネットワーク制御装置も、自身の配下や上位のネットワーク制御装置から集約された少量のトラヒック情報を収集すればよいので、収集する情報量が削減され高速かつ頻繁な情報収集が可能となる。また、輻輳の発生を未然に防ぐ際には、可能な限り下位層での局所的な経路変更を優先させることにより、ネットワークの安定性を向上することができる。
【００７４】
以上にて本発明を実施するための形態の説明を終えるが、本発明の実施の態様はこれに限られるものではなく、本発明の趣旨を逸脱しない範囲内で各種の変更が可能である。
【符号の説明】
【００７５】
１    通信ネットワーク
２（２Ｌ，２Ｍ，２Ｈ）  ネットワーク制御装置
３（３Ｌ，３Ｍ，３Ｈ）  制御範囲
Ｌ  リンク
Ｎ  ノード
ＢＮ  境界ノード
ＬＮ  ローカルノード
ＥＮ  外部ノード
ＬＬ  論理リンク
ＥＬ  外部リンク
２１  トラヒック情報収集部
２２（２２Ｌ，２２Ｍ）  集約情報生成部
２３（２３Ｌ，２３Ｍ）  トラヒック情報交換部
２４（２４Ｌ，２４Ｍ）  経路計算部
２５（２５Ｌ，２５Ｍ）  経路制御部
２６  トポロジＤＢ
２７  トラヒックＤＢ
２８  経路ＤＢ
【図１】
0005504449.tif 000002
【図２】
0005504449.tif 000003
【図３】
0005504449.tif 000004
【図４】
0005504449.tif 000005
【図５】
0005504449.tif 000006
【図６】
0005504449.tif 000007
【図７】
0005504449.tif 000008
【図８】
0005504449.tif 000009
【図９】
0005504449.tif 000010
【図１０】
0005504449.tif 000011
【図１１】
0005504449.tif 000012
【図１２】
0005504449.tif 000013
【図１３】
0005504449.tif 000014
【図１４】
0005504449.tif 000015
【図１５】
0005504449.tif 000016