(57)【要約】【課題】  リンク両端のラインカードへスリープを導入し、消費電力を削減する。【解決手段】  本発明は、ネットワークから収集した負荷情報からネットワーク上のリンクの利用率を求め、最大利用率が上限・下限の閾値の範囲を超えた場合に、フロー情報から生成されたトラヒック行列と負荷情報、ネットワーク構成情報からダイクストラ方を利用した計算を行い、最も負荷の大きいリンクの利用率が閾値を超えるまで順次スリープ導入可能なリンクを抽出する。抽出されたリンクをスリープしたトポロジに対してOSPFプロトコルで最も負荷が分散されるようなリンクの重み値の組み合わせを計算し、閾値を超えた場合は、閾値を超える前のリンクトポロジを獲得しリンクコストとし、最終的なリンクコストと当該リンクコストに基づく経路を決定し、実ネットワークへのリンクコストの設定及び使用しないリンクへのスリープの導入を行う。【選択図】  図１
2012147271.tif 000002
【特許請求の範囲】
【請求項１】
OSPF(Open shortest Path First)ルーティングプロトコルでネットワーク内の通信経路が制御されている通信ネットワークにおいて省電力化を行うための監視制御装置であって、
ネットワーク構成情報、ネットワークトポロジ、トラヒックフロー情報、インタフェース負荷情報を格納する記憶手段と、
前記ネットワークとの間で通信を行い、前記トラヒックフロー情報、インタフェース負荷情報を取得して前記記憶手段に格納する通信インタフェース手段と、
前記トラヒックフロー情報からトラヒック行列を生成するトラヒック行列生成手段と、
前記インタフェース負荷情報から前記トラヒック行列に基づいてリンク利用率を求めるリンク利用率計算手段と、
前記リンク利用率が所定の上限及び下限の閾値を越えた場合に、各リンクの重み値を変更することによりトラヒックの流れないスリープ対象のリンクを前記記憶手段のネットワークトポロジから除外してスリープ対象のリンクを除いた新たなトポロジを作成するスリープ導入計算手段と、
前記スリープ導入計算手段で作成された前記新たなトポロジに対してトラヒックを平準化するリンクの重み値の組み合わせを算出する組み合わせ算出手段と、
前記最大リンク利用率が所定の閾値を超えるまで前記スリープ導入計算手段及び前記組み合わせ算出手段を行い、該閾値を超えた場合は、該閾値を超える直前のトポロジを取得して、該トポロジに対してリンクコストを計算し、該リンクコストから前記OSPFルーティングプロトコルで最も負荷が分散されるようなリンクの重み値の組み合わせを計算する負荷分散手段と、
前記重み値の組み合わせ及びスリープ可能なリンク情報に基づいて、スリープ対象のリンクを除いたトポロジを前記ネットワークに適用する適用・導入手段と、
を有することを特徴とする監視制御装置。
【請求項２】
前記スリープ導入計算手段は、
全てのリンクから前記リンク利用率が所定の閾値より低いが代替経路が存在しないリンクをスリープ導入対象から外したリンクリストを生成し、該リンクリストにおいて所定の閾値未満でかつ最小の利用率のリンクの重み値を増大する第１の手段と、
前記トラヒック行列と前記ネットワーク構成情報に基づいて動的計画法を用いて各リンク利用率を求め、所定の閾値を超える利用率のリンクが無い場合は、直前のリンクの利用率が０であるかを判定し、０であれば該リンクを前記リンクリストから除き、該利用率が０よりも大きければスリープ対象とはせず、該所定の閾値を超える利用率のリンクがある場合は、該リンクの現在のリンク重み値または直前の重み値を前記組み合わせ算出手段に出力する第２の手段と、
を含む請求項１記載の監視制御装置。
【請求項３】
前記第２の手段は、
最大リンク利用率が前記所定の閾値を超えている場合は、最大リンク利用率が閾値を超過する直前のリンク重み値を、それ以外の場合は、最大リンク利用率が閾値を超過した直後のリンク重み値を前記組み合わせ算出手段に出力する
請求項２記載の監視制御装置。
【請求項４】
前記負荷分散手段は、
前記リンクの重み値の組み合わせの最大リンク利用率が、所定の閾値を超えた場合には、該閾値を超える直前のリンクトポロジを取得し、リンク利用率が大きいほどコストが増大するコスト関数を用いて最終的なリンクコストを計算し、最もリンクコストが低いリンクの重み値を求める手段を含む
請求項１記載の監視制御装置。
【請求項５】
OSPFルーティングプロトコルでネットワーク内の通信経路が制御されている通信ネットワークにおいて省電力化を行うための監視制御方法であって、
装置内の記憶手段にネットワーク構成情報、ネットワークトポロジを格納しておき、
通信インタフェース手段が、前記ネットワークとの間で通信を行い、前記記憶手段から前記トラヒックフロー情報、インタフェース負荷情報を取得して前記記憶手段に格納する通信インタフェースステップと、
トラヒック行列生成手段が、前記トラヒックフロー情報からトラヒック行列を生成するトラヒック行列生成ステップと、
リンク利用率計算手段が、前記インタフェース負荷情報から前記トラヒック行列に基づいてリンク利用率を求めるリンク利用率計算ステップと、
スリープ導入計算手段が、前記リンク利用率が所定の上限及び下限の閾値を越えた場合に、各リンクの重み値を変更することによりトラヒックの流れないスリープ対象のリンクを前記記憶手段のネットワークトポロジから除外してスリープ対象のリンクを除いた新たなトポロジを作成するスリープ導入計算ステップと、
負荷分散手段が、前記スリープ導入計算ステップで作成された前記新たなトポロジに対してトラヒックを平準化するリンクの重み値の組み合わせを算出する組み合わせ算出ステップと、
前記負荷分散手段が、前記最大リンク利用率が所定の閾値を超えるまで前記スリープ導入計算ステップ及び前記組み合わせ算出ステップを行い、該閾値を超えた場合は、該閾値を超える直前のトポロジを取得して、該トポロジに対してリンクコストを計算し、該リンクコストから前記OSPFルーティングプロトコルで最も負荷が分散されるようなリンクの重み値の組み合わせを計算する負荷分散ステップと、
適用・導入手段が、前記重み値の組み合わせ及びスリープ可能なリンク情報に基づいて、スリープ対象のリンクを除いたトポロジを前記ネットワークに適用する適用・導入ステップと、
を行うことを特徴とする監視制御方法。
【請求項６】
前記スリープ導入計算ステップにおいて、
全てのリンクから前記リンク利用率が所定の閾値より低いが代替経路が存在しないリンクをスリープ導入対象から外したリンクリストを生成し、該リンクリストにおいて所定の閾値未満でかつ最小の利用率のリンクの重み値を増大させる第１のステップと、
前記トラヒック行列と前記ネットワーク構成情報に基づいて動的計画法を用いて各リンク利用率を求め、所定の閾値を超える利用率のリンクが無い場合は、直前のリンクの利用率が０であるかを判定し、０であれば該リンクを前記リンクリストから除き、該利用率が０よりも大きければスリープ対象とはせず、該所定の閾値を超える利用率のリンクがある場合は、該リンクの現在のリンク重み値または直前の重み値を出力する第２のステップと、
を含む請求項５記載の監視制御方法。
【請求項７】
前記第２のステップにおいて、
最大リンク利用率が前記所定の閾値を超えている場合は、最大リンク利用率が閾値を超過する直前のリンク重み値を、それ以外の場合は、最大リンク利用率が閾値を超過した直後のリンク重み値を出力する
請求項６記載の監視制御方法。
【請求項８】
前記負荷分散ステップにおいて、
前記リンクの重み値の組み合わせの最大リンク利用率が、所定の閾値を超えた場合には、該閾値を超える直前のリンクトポロジを取得し、リンク利用率が大きいほどコストが増大するコスト関数を用いて最終的なリンクコストを計算し、最もリンクコストが低いリンクの重み値を求める
請求項５記載の監視制御方法。
【請求項９】
請求項１乃至４のいずれか１項に記載の監視制御装置を構成する各手段としてコンピュータを機能させるための監視制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、監視制御装置及び通信経路設定方法及びプログラムに係り、特に、管理されているIP（Internet Protocol）中継網において、ルータの消費電力を削減するためのネットワーク装置及び通信経路設定方法及びプログラムに関する。
【背景技術】
【０００２】
ルータでは、サーバとは異なり、待機状態における消費電力は最大負荷時に比べ大きな差異が生じない（約７％ほどの差異となる）ため、待機電力を大きく削減するためにはスリープ状態を活用することが提示されてきた（例えば、非特許文献１参照）。
【０００３】
ネットワーク単位での通信経路制御を行うことによって特定のルータに流れるトラヒックを他のルータへ配分し、スリープを導入するような技術も発展してきている（例えば、非特許文献２参照）。
【０００４】
また、ルータ単位では、ラインカードバッファを利用してノード稼動中に小規模のスリープを導入することにより待機電力を削減するRate Adaptation（例えば、非特許文献３参照）も注目されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Joseph Chabarek, Joel Sommers, Paul Barford, et.al "Power Awareness in Network Design and Routing" In Proc. IEEE INFOCOM, 2008. http://pages.cs.wisc.edu/~pb/infocom08a_final.pdf
【非特許文献２】野村啓仁、矢田健、山田博司、"機器の電力特性を考慮したネットワーク省電力化に関する一考察"、電子情報通信学会、ソサエティ大会、2010年9月.
【非特許文献３】Serigiu Nedvschi, Lucian Popa, et. al, "Reducing Network Energy consumption via Rate-Adaptation and Sleeping", 2008 http://www.eecs.berkeley.edu/Pubs/TechRps/2007/EECS-2007-128.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、現在提案されているルータの消費電力を削減するための手法のほとんどでは、MPLS(Multi-Protocol Label Switching)やRoute Adaptation(非特許文献３）などを実装したルータの導入などが必要となっている。
【０００７】
そのため、MPLSを利用できるルータを持たなかったり、OSPF(Open Shortest Path First)をルーティングに用いるような現在の一般的なネットワークでは、スリープ状態になったルータは電源ＯＦＦと判断されて経路から削除されてしまうこととなり、容易にこれらのルータのスリープを導入する技術を用いることができない。
【０００８】
また、OSPFルーティングに適応した手法も提案されているが（非特許文献２）、最大リンク利用率を終了条件としたアルゴリズムであるため、特定の回線への負荷の集中が発生すると、スリープ導入の余地があっても導入を終了してしまうという問題がある。
【０００９】
本発明は、上記の点に鑑みなされたもので、OSPFルーティングプロトコルで網内の通信経路が制御されている通信ネットワークにおいて、リンク両端のラインカードへスリープを導入し、消費電力を削減することが可能なネットワーク装置及び通信経路設定方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明（請求項１）は、OSPFルーティングプロトコルでネットワーク内の通信経路が制御されている通信ネットワークにおいて省電力化を行うための監視制御装置であって、
ネットワーク構成情報、ネットワークトポロジ、トラヒックフロー情報、インタフェース負荷情報を格納する記憶手段と、
前記ネットワークとの間で通信を行い、前記トラヒックフロー情報、インタフェース負荷情報を取得して前記記憶手段に格納する通信インタフェース手段と、
前記トラヒックフロー情報からトラヒック行列を生成するトラヒック行列生成手段と、
前記インタフェース負荷情報から前記トラヒック行列に基づいてリンク利用率を求めるリンク利用率計算手段と、
前記リンク利用率が所定の上限及び下限の閾値を越えた場合に、各リンクの重み値を変更することによりトラヒックの流れないスリープ対象のリンクを前記記憶手段のネットワークトポロジから除外してスリープ対象のリンクを除いた新たなトポロジを作成するスリープ導入計算手段と、
前記スリープ導入計算手段で作成された前記新たなトポロジに対してトラヒックを平準化するリンクの重み値の組み合わせを算出する組み合わせ算出手段と、
前記最大リンク利用率が所定の閾値を超えるまで前記スリープ導入計算手段及び前記組み合わせ算出手段を行い、該閾値を超えた場合は、該閾値を超える直前のトポロジを取得して、該トポロジに対してリンクコストを計算し、該リンクコストから前記OSPFルーティングプロトコルで最も負荷が分散されるようなリンクの重み値の組み合わせを計算する負荷分散手段と、
前記重み値の組み合わせ及びスリープ可能なリンク情報に基づいて、スリープ対象のリンクを除いたトポロジを前記ネットワークに適用する適用・導入手段と、を有する。
【発明の効果】
【００１１】
上記のように、本発明はMPLSやRate Adaptationなどの、現状では実装できていない機器が存在する手法を用いることなく、一般的なOSPFプロトコルのネットワークにおいて、各ルータで設定しているOSPFのリンク重み値（リンクの重み）の変更操作のみで、スリープを導入した通信経路の再設定を可能とし、ルータの省電力化を実現することが可能となる。
【００１２】
また、スリープを導入していないリンクからなるネットワークにおいても、OSPFリンクの重み値の操作のみで負荷分散を行うことにより、特定リンクへの高負荷を緩和すると共に、更なるスリープの導入も期待できるようになる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施の形態におけるネットワーク構成図である。
【図２】本発明の一実施の形態における監視制御装置の構成図である。
【図３】本発明の一実施の形態における演算部の構成図である。
【図４】本発明の一実施の形態におけるネットワーク全体の概要動作を示す図である。
【図５】本発明の一実施の形態におけるスリープ導入計算処理のフローチャートである。
【図６】本発明の一実施の形態における負荷分散計算処理のフローチャートである。
【図７】本発明の一実施の形態における演算部で求められるｃa＝1におけるφ(la,caa)の値の例である。
【図８】本発明の一実施の形態における監視制御装置の全体動作のフローチャートである。
【発明を実施するための形態】
【００１４】
以下図面と共に、本発明の実施の形態を説明する。
【００１５】
まず、最初に本明細書で用いる用語について説明する。
【００１６】
・重み値：ネットワーク管理者が個別のルータ毎に設定する、OSPFの経路計算に用いるリンクの重み。
【００１７】
・経路コスト：ダイクストラ法で算出した２つのノード間の最短パス上のリンクの重み値の和。
【００１８】
・コスト：負荷分散計算で用いるコスト関数の値。
【００１９】
次に、本発明の前提条件について説明する。
【００２０】
１．ルータの消費電力は、約半分をシャーシが、残りの殆どをラインカードによって構成されている。ラインカードはその処理速度が高いほど消費電力が大きくなる（非特許文献１参照）。
【００２１】
２．ネットワークを構成する各ルータでは、その構成部品単位でのスリープを導入することができる。なお、スリープ状態では、消費電力がほぼゼロになるが、処理を行うことができなくなる。
【００２２】
３．NetFlowやsFlowなどのトラヒックフロー測定技術を用いることよって、特定の装置（フローコレクタ）に各機器を流れるフローの情報を収集することができる（例えば、「文献１："Cisco NetFlow v3" http://www.cisco.com/warp/public/cc/pd/nemnsw/nesv/prodlit/2033_pp.pdf」、「文献２：sFlow http://www.sflow.org/about/index.php」参照）。
【００２３】
４．上記の３．で収集したフロー情報から文献３（田中喜明、立花大祐、内田真人ら、"実ネットワークにおける集約フロー流量からのフロー毎流量統計の推定"）などの技術によりトラヒック行列を推定することが可能である。
【００２４】
５．SNMPなどを介して、ネットワーク機器は自身のインタフェースの負荷情報を特定の監視装置へ通知することができる。
【００２５】
まず、本発明のネットワーク構成について説明する。
【００２６】
図１は、本発明の一実施の形態におけるネットワークの構成を示す。
【００２７】
本発明が対象とするネットワーク１は、OSPFをルーティングプロトコルとした単一のAS（Autonomous System）であり、冗長性を持つ構造である。ネットワーク１を流れるトラヒックは、昼夜や平日または休日などで各対地毎、及び、全体の流量が大きく変動する。
【００２８】
ネットワーク１には、複数のAS境界ルータ１０があり、これらのルータ１０のラインカードでは待機電力が大きいものとする。また、各ルータ１０は、自らを流れるトラヒックフロー情報を監視制御装置２０へ通知するものとする。
【００２９】
監視制御装置２０は、ネットワーク１に接続され、ネットワーク１の構成情報を管理する装置であり、フローコレクタとして働き、各ルータ１０からのフロー情報及び負荷情報を取得し、トラヒック状況に応じた経路を演算する。また、各ルータ１０にTelnetまたはSSH(Secure SHell)でアクセスし、設定を変更することができる。
【００３０】
図２は、本発明の一実施の形態における監視制御装置の構成を示す。監視制御装置２０は、通信インタフェース部２１、記憶部２２、演算部２３から構成される。
【００３１】
通信インタフェース部２１は、ネットワーク１に接続され、ＩＰアドレスを持ち、各管理対象機器との通信処理を行う。
【００３２】
記憶部２２は、ネットワーク機器の設定情報、スリープ導入前、スリープ導入後、閾値超え、スリープ導入後、閾値直前等のネットワークトポロジ、フロー行列、各インタフェースの負荷情報等を格納する。
【００３３】
演算部２３は、定期的なネットワーク機器の管理とスリープ導入のための計算や、記憶部２２とのやり取りにより、演算に必要な情報の取得、計算結果や機器情報の格納を行う。具体的には、定期的な情報取得処理と省電力化処理を行う。
【００３４】
定期的な情報取得処理としては、SNMPなどにより、定期的にネットワークの各機器の負荷情報、設定情報を取得する処理や、NetFlow等によりルータ１０からのフロー情報を取得して、記憶部２２に格納する。
【００３５】
省電力化処理としては、フロー情報からのトラヒック行列の推定、スリープ可能リンクの算出、負荷分散計算によって負荷を分散させる重み値の組み合わせの算出、スリープ導入計算と負荷分散計算の組み合わせ処理、算出した設定の実ネットワークへの適用及びスリープ導入処理等を行う。
【００３６】
図３は、本発明の一実施の形態における演算部の構成を示す。
【００３７】
演算部２３は、上記の定期的な情報取得処理を行う情報管理部２３１、リンク利用率（負荷）を計算するリンク利用率計算部２３２、記憶部２２から取得したフロー情報から、前述の文献３に示す手法によりトラヒック行列を生成するトラヒック行列作成部２３３、スリープ導入計算を行うスリープ導入計算部２３４、リンク利用率に基づいて負荷を分散させる計算を行う負荷分散部２３５、実ネットワークへの適用及びスリープ導入を行う適用・導入部２３６、演算部２３内で計算された計算結果等を格納するメモリ２３７から構成される。
【００３８】
次に、上記の構成における動作の概要を説明する。
【００３９】
図４は、本発明の一実施の形態におけるネットワーク全体の概要動作を示す。
【００４０】
ステップ０）  初期状態では、ネットワーク１は、それぞれ事前に設定されているルーティングプロトコルに従い経路を決定する。
【００４１】
ステップ１）  各ルータ１０は、自身の各インタフェースに掛かる負荷情報をSNMPによって監視制御装置２０通知する。また、エッジルータは、トラヒック行列を作成するのに必要なフロー情報を収集し、一定の間隔で監視制御装置２０へと送信する。
【００４２】
ステップ２）  監視制御装置２０の通信インタフェース部２１は、各ルータ１０から通知された負荷情報、フロー情報を取得して記憶部２２に格納する。演算部２３のリンク利用率計算部２３２は、記憶部２２から負荷情報を取得し、ネットワーク１上のリンクの利用率を求める。演算部２３は、最大利用率が所定の閾値によって定められた範囲（上限値と下限値の間）を超えた場合に、以下の動作により電力効率を考慮した経路決定を行う。詳細については後述する。
【００４３】
ステップ３）  演算部２３は、トラヒック行列作成部２３３において、記憶部２２からフロー情報を読み出してトラヒック行列を作成する。
【００４４】
ステップ４）  演算部２３は、スリープ導入計算部２３４において、ステップ３で作成したトラヒック行列と負荷情報、及びネットワーク構成情報からダイクストラ法を利用した計算を行い、最も負荷の大きいリンクの利用率が閾値θを超えるまで、順次スリープ導入可能なリンクを選別する。詳細については後述する。
【００４５】
ステップ５）  演算部２３は、負荷分散部２３５において、上記のステップ４で算出されたリンクをスリープしたトポロジに対して、OSPFプロトコルで最も負荷が分散されるようなリンクの重み値の組み合わせを計算する。
【００４６】
ステップ６）  上記のステップ５の計算によって最大リンク利用率が閾値θを下回る間は、上記のステップ４，５を繰り返す。
【００４７】
ステップ７）  負荷分散部２３５は、閾値θを超えた場合は、ステップ４において閾値θを超える直前のリンクトポロジを取得し、ステップ５における負荷分散を用いて最終的なリンクコストとする。
【００４８】
ステップ８）  最終的なリンクコスト及びそれに基づく経路決定がなされたら、監視制御装置２０の通信インタフェース部２１を介して実ネットワーク１へのリンクコストの設定及び非使用リンクへのスリープの導入が行われる。詳細については後述する。
【００４９】
次に、上記のステップ４におけるスリープ導入計算処理について説明する。
【００５０】
図５は、本発明の一実施の形態におけるスリープ導入計算処理のフローチャートである。
【００５１】
スリープ導入計算処理の前に、演算部２３のトラヒック行列作成部２３３は、通信インタフェース部２１を介して記憶部２２に格納されたトラヒックフロー情報に基づいて、ネットワーク１を流れるトラヒックの行列を作成し、当該演算部２３内部のメモリ２３７に格納する。当該トラヒックの行列を作成する方法としては、例えば、文献４「sFlow http://www.sflow.org/about /index.php」による方法を用いるものとする。この際に、全エッジ間の疎通性を確保するために、フローが観測されなかったエッジ対地には最低トラヒック量よりも低い値のトラヒックを与えるものとする。
【００５２】
また、通信インタフェース部２１では、SNMPによって取得したネットワークの全リンクの負荷情報を記憶部２２に格納しておき、演算部２３では、当該全リンクの負荷情報を基に、利用率が閾値θを超えるリンクが存在するかを判断する。閾値θを超えるリンクが存在しなければ、図５に示す処理を行い、閾値θを超えるリンクが存在する場合は図５に示す処理は行わず、ステップ５の負荷分散処理に移行する。
【００５３】
ステップ４０１）  演算部２３の情報管理部２３１は、ステップ３で生成されたトラヒック行列、及び、記憶部２２から帯域、重み値を含むネットワークトポロジ、各リンクの負荷情報を取得する。
【００５４】
ステップ４０２）  スリープ導入計算部２３４は、予め設定された閾値θを超える利用率のリンクがある場合、または、全リンクのスリープ導入の検証が終了した場合は、現在のリンク重み値の設定及び閾値を超えないリンク重み値設定を持つ、前回のステップ４０３〜４０８の処理でメモリ２３７に記憶したリンク重み値設定を読み込み、負荷分散部２３５に出力する。閾値θを超えるリンクが無い場合は、ステップ４０３に移行する。
【００５５】
ステップ４０３）  スリープ導入計算部２３４は、現在の全リンクの重み値をメモリ２３７に格納する。
【００５６】
ステップ４０４）  利用率が低いが代替経路が存在しないリンクをスリープ導入対象から外すために、後述するスリープフラグを設定したリンクを除いたリンク情報リストを作成し、内部のメモリ２３７に格納する。
【００５７】
ステップ４０５）  スリープ導入計算部２３４は、作成したリンクリストにおいて、閾値θ未満で最小の利用率を持つリンクを特定し、スリープフラグ"１"を立てる。
【００５８】
ステップ４０６）  さらに、スリープフラグを立てたリンクのコストを増大させ、トラヒックが流れないようにする。例えば、設定コストを全リンクの重みの和＋１とする。
【００５９】
ステップ４０７）  メモリ２３７内のトラヒック行列と記憶部２２から読み出したネットワーク構成情報に基づいてダイクストラ法に基づいた計算を行い、各リンクの利用率を算出し、メモリ２３７に格納する。
【００６０】
ステップ４０８）  スリープ導入計算部２３４は、ステップ４０７で算出した全リンクの利用率に対して、まず、閾値θを超える利用率のリンクが存在するかを判断し、閾値θを超える利用率のリンクがあれば、スリープを導入した場合のネットワークトポロジ（閾値を超えたもの／超えないもの）を負荷分散部２３５に出力する。一方、閾値θを超える利用率のリンクがなければ、ステップ４０９に移行する。
【００６１】
ステップ４０９）  直前にスリープフラグを立てたリンクの利用率が０であるかを判断し、利用率が０であればステップ４１０に移行し、利用率が０よりも大きければ当該リンクにスリープを導入すると疎通性が失われる対地間が発生するため、スリープを導入せずにステップ４０２に移行する。
【００６２】
ステップ４１０）  ステップ４０９において、利用率が０であれば、当該リンクをネットワークから除き、ステップ４０２に移行し、利用率が閾値θを超えるか、スリープフラグリストに全リンクが登録されることによりリンク情報リストが作成できなくなるまで、上記の処理を繰り返す。
【００６３】
次に、上記のステップ５の負荷分散計算処理について説明する。
【００６４】
演算部２３の負荷分散部２３５は、ステップ５における負荷分散計算として、文献５「Fortz, B. Thorup, M. "Internet traffic engineering by optimizing OSPF weights", Proc. 19th IEEE Conf. Computer Communications (INFOCOM),pp. 519-528 http://ieee.org/xpls/abs_all.jsp?arnumber=832225&tag=1」に記載の方法に基づいて、タブーサーチを利用した局所探索法に基づいて、各リンクの利用率が平準化されるようなリンク重み値の組み合わせを算出する。この負荷平準化には、あるノード間に複数の経路コストが等しいパスが存在する際に、トラヒックが分散されるというOSPFの性質を利用し、閾値θに合わせてコスト関数の傾斜が変動するように変更を行っている。
【００６５】
図６は、本発明の一実施の形態における負荷分散計算処理のフローチャートである。
【００６６】
以下に示す負荷分散部２３５による負荷分散計算では、各リンクの利用率が閾θ未満となるように、図７に示す形状をとる、以下に示すコスト関数を用いる。ネットワークのコストΦは、コスト関数φ（ｌa，ｃa）、ネットワークのリンクａの集合Ａ，リンクａの負荷ｌａ、リンクａの容量ｃａとして、以下の式により求められる。
【００６７】
【数１】
2012147271.tif 000003
ステップ５０１）  前述のスリープ導入計算部２３４から出力されたネットワークトポロジとメモリ２３７からトラヒック行列、及び閾値θを取得し、上記のコスト関数のパラメータを決定する。
【００６８】
ステップ５０２）  負荷分散部２３５は、初期解として、Ｗ＝｛１，…，ｗmax｝からランダムに値を取得し、各リンクの重み値として設定する（このリンクに対する重み値の組み合わせを初期解とする）。
【００６９】
ステップ５０３）  負荷分散部２３５は、Shortest Pathを算出する。
【００７０】
ステップ５０４）  リンク利用率計算部２３２は、トラヒック行列と初期解、ネットワークトポロジを用いて各リンクの利用率を算出する。
【００７１】
ステップ５０５）  負荷分散部２３５は、リンク利用率計算部２３２で算出された利用率を上記のコスト関数に適用し、初期解のコストを算出する。なお、コスト関数はリンク利用率が大きいほどコストが増大する性質を持つ。
【００７２】
ステップ５０６）  負荷分散部２３５は、現在の解とコストをメモリ２３７上のハッシュテーブル１（ＨＴ１）に格納し、これをタブーリストとして利用する。
【００７３】
ステップ５０７）  ＨＴ１に格納された現在の解から上記の文献５の手法に従いＮｎ個の近傍解ｗ'を作成する。
【００７４】
ステップ５０８）  求められた近傍解ｗ'がＨＴ１に含まれるかを判定し、含まれる場合にはステップ５０９に移行し、含まれない場合はステップ５１０に移行する。
【００７５】
ステップ５０９）  近傍解ｗ'を破棄し、ステップ５０７に移行する。
【００７６】
ステップ５１０）  近傍解w'がNnに達したかを判定し、達した場合はステップ５１１に移行し、達していない場合はステップ５０７に移行する。
【００７７】
ステップ５１１）  コスト評価済みの解とコスト値を格納するハッシュテーブル２（ＨＴ２）に含まれていない近傍解を抽出する。
【００７８】
ステップ５１２）  ステップ５１１で抽出した近傍解のShortest Pathを算出する。
【００７９】
ステップ５１３）  リンク利用率計算部２３２は、抽出された解の負荷を算出する。
【００８０】
ステップ５１４）  負荷分散部２３５は、抽出した解のコストを算出する。算出方法はステップ５０５と同様である。
【００８１】
ステップ５１５）  抽出した解及びそのコストをメモリ２３７上のＨＴ２に格納する。
【００８２】
ステップ５１６）  負荷分散部２３５は、近傍解のうち、最もコストが低いものを次の解として抽出する。
【００８３】
ステップ５１７）  抽出された最低コストの解とコスト値をＨＴ１に格納する。
【００８４】
ステップ５１８）  ＨＴ１の要素数がＮｉに達したかを判定し、達していない場合はステップ５０７に移行し、達した場合はステップ５１９に移行する。
【００８５】
ステップ５１９）  上記のステップ５０７〜５１８の処理をＮｉ回繰り返し、ＨＴ１において最もコストが低かった解を最適解（重み値の組み合わせ）として適用・導入部２３６に出力する。なお、一定の繰り返し回数毎に、解の要素の一部に摂動を与えて新規解とし、探索範囲を変更する。
【００８６】
次に、監視制御装置２３における全体動作を説明する。
【００８７】
図８は、本発明の一実施の形態における監視制御装置の全体動作のフローチャートである。以下の処理の前提として、演算部２３の情報管理部２３１では、常に一定の時間間隔で通信インタフェース２１を介してネットワーク１の各機器の負荷情報を収集し、記憶部２２に格納しているものとする。
【００８８】
ステップ７０１）  演算部２３のリンク利用率計算部２３２において、計算されたネットワーク１の各機器のインタフェースの負荷情報を計算し、最も利用率の大きいリンクの利用率が所定の上限閾値α以上、または、下限閾値β未満である場合はステップ７０２に移行し、β以上α未満の場合は何もせず待機する。
【００８９】
ステップ７０２）  演算部２３のトラヒック行列作成部２３３は、ネットワーク１のルータ１０から得られたフロー情報を記憶部２２から読み出して、トラヒック行列を作成し、メモリ２３７に格納する。
【００９０】
ステップ７０３）  演算部２３のスリープ導入計算部２３４は、メモリ２３７からトラヒック行列を、記憶部２２からトポロジ情報を読み出して、スリープ導入処理を行い、スリープ導入可能なリンクを特定する。この際、以下の２つの条件によりスリープ導入後のトポロジを記憶する。
【００９１】
条件ａ：最大リンク利用率が閾値θを超過した直後のトポロジ；
条件ｂ：最大リンク利用率が閾値θを超過する直前のトポロジ；
上記の条件ａは、負荷分散処理により最大リンク利用率低下を起し、更なるスリープを導入するために利用する。条件ｂは、負荷分散処理による抑制後の最大リンク利用率がθを超過した場合に利用する。
【００９２】
ステップ７０４）  スリープ導入計算部２３４は、分散処理後の最大リンク利用率が閾値θを超過しているかを判定し、超過していた場合（over flag＝1）は、ステップ７０６に移行し、それ以外の場合はステップ７０５に移行する。
【００９３】
ステップ７０５）  入力トポロジとして、条件ａを選択し、ステップ７０７に移行する。
【００９４】
ステップ７０６）  入力トポロジとして、条件ｂを選択し、ステップ７０７に移行する。
【００９５】
ステップ７０７）  負荷分散部２３５は、スリープ導入後のトポロジでリンク利用率が平準化するような重み値の組み合わせを算出する。
【００９６】
ステップ７０８）  リンク利用率計算部２３２において、各リンクの利用率を算出し、負荷分散部２３５は、当該リンクの利用率を取得して、最大リンク利用率が閾値θを上回っているかを判定する。上回っている場合はステップ７０９に移行し、そうでない場合はステップ７１０に移行する。
【００９７】
ステップ７０９）  最大リンク利用率＞θであればover_flag＝１とし、ステップ７０４に移行し、条件ｂでのトポロジでの負荷分散計算処理を開始する（ステップ７０６，７０７）。
【００９８】
ステップ７１０）  最大リンク利用率≦θであれば、over_flag=1であるかを判定し、over_flag=1である場合はステップ７１１に移行し、over_flag＝０（初期値）である場合はステップ７０３に移行し、出力した重み値でのトポロジを入力としてスリープ導入処理を行う。
【００９９】
ステップ７１１）  負荷分散部２３５は、スリープリンクの重み値を設定する。このとき、スリープ扱いとなっているリンクの重み値を、他のリンクの和よりも大きい値に設定する。
【０１００】
ステップ７１２）  適用・導入部２３６は、通信インタフェース２１を介してTelnetやSSHを用いて実際のネットワーク１の各ルータ１０にアクセスし、最終的なリンクの重み値を設定する。
【０１０１】
ステップ７１３）  適用・導入部２３６は、ルート再設定によりスリープ対象のリンクにトラヒックが流れなくなったらこれらの両端のインタフェースをスリープし、消費電力を削減する。
【０１０２】
本発明は、上記の実施の形態における図２、図３に示す監視制御装置２０の構成要素の動作をプログラムとして構築し、監視制御装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１０３】
なお、本発明は上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０４】
１  ネットワーク
１０  ＡＳ境界ルータ
２０  監視制御装置
２１  通信インタフェース部
２２  記憶部
２３  演算部
２３１  情報管理部
２３２  リンク利用率計算部
２３３  トラヒック行列作成部
２３４  スリープ導入計算部
２３５  負荷分散部
２３６  適用・導入部
【図１】
2012147271.tif 000004
【図２】
2012147271.tif 000005
【図３】
2012147271.tif 000006
【図４】
2012147271.tif 000007
【図５】
2012147271.tif 000008
【図６】
2012147271.tif 000009
【図７】
2012147271.tif 000010
【図８】
2012147271.tif 000011