(57)【要約】【課題】  ルータの消費電力削減のためのスリープを導入することを可能にする。【解決手段】  本発明は、ネットワークとの間で通信を行い、トラヒックフロー情報、インタフェース負荷情報を取得して記憶手段に格納し、トラヒックフロー情報からトラヒック行列を生成し、インタフェース負荷情報からトラヒック行列に基づいてリンク利用率を求め、リンク利用率に、タブーサーチを利用した局所探索法を適用して最もコストの低いリンクの重み値の組み合わせを算出する。また、リンク利用率が０以上で所定の閾値以下となるリンクの集合を生成し、該集合から選択したリンクの重み値を変更することによりコストを求める。【選択図】  図３
2012175393.tif 000002
【特許請求の範囲】
【請求項１】
OSPF(Open Shortest Path First)ルーティングプロトコルでネットワーク内の通信経路が制御されている通信ネットワークにおいて、省電力化を行うための監視制御装置であって、
ネットワーク構成情報、ネットワークトポロジ情報、トラヒックフロー情報、インタフェース負荷情報を格納する記憶手段と、
前記ネットワークとの間で通信を行い、前記トラヒックフロー情報、前記インタフェース負荷情報を取得して前記記憶手段に格納する通信インタフェース手段と、
前記トラヒックフロー情報からトラヒック行列を生成するトラヒック行列生成手段と、
前記インタフェース負荷情報から前記トラヒック行列に基づいてリンク利用率を求めるリンク利用率計算手段と、
前記リンク利用率に、タブーサーチを利用した局所探索法を適用して最もコストの低いリンクの重み値の組み合わせを算出する負荷分散計算手段と、
を有することを特徴とする監視制御装置。
【請求項２】
前記負荷分散計算手段は、
前記リンク利用率が０以上で所定の閾値以下となるリンクの集合を生成し、該集合から選択したリンクの重み値を変更することによりコストを求める重み値調整手段を含む
請求項１記載の監視制御装置。
【請求項３】
前記重み値調整手段は、
前記リンク利用率が０のときは、コストの値を０とする
請求項２記載の監視制御装置。
【請求項４】
前記重み値調整手段は、
前記リンク利用率が所定の上限閾値以上の場合は重み値を増大させ、所定の下限閾値以下の場合は重み値を低くする、または増大させる
請求項２記載の監視制御装置。
【請求項５】
OSPF(Open Shortest Path First)ルーティングプロトコルでネットワーク内の通信経路が制御されている通信ネットワークにおいて、省電力化を行うための監視制御方法であって、
通信インタフェース手段が、前記ネットワークとの間で通信を行い、前記トラヒックフロー情報、前記インタフェース負荷情報を取得して記憶手段に格納する通信ステップと、
トラヒック行列生成手段が、前記トラヒックフロー情報からトラヒック行列を生成するトラヒック行列生成ステップと、
リンク利用率計算手段が、前記インタフェース負荷情報から前記トラヒック行列に基づいてリンク利用率を求めるリンク利用率計算ステップと、
負荷分散計算手段が、前記リンク利用率に、タブーサーチを利用した局所探索法を適用して最もコストの低いリンクの重み値の組み合わせを算出する負荷分散計算ステップと、
を行うことを特徴とする監視制御方法。
【請求項６】
前記負荷分散計算ステップにおいて、
前記リンク利用率が０以上で所定の閾値以下となるリンクの集合を生成し、該集合から選択したリンクの重み値を変更することによりコストを求める
請求項５記載の監視制御方法。
【請求項７】
前記リンク利用率が０のときは、コストの値を０とする
請求項６記載の監視制御方法。
【請求項８】
前記リンク利用率が所定の上限閾値以上の場合は重み値を増大させ、所定の下限閾値以下の場合は重み値を低くする、または、増大させる
請求項６記載の監視制御方法。
【請求項９】
請求項１乃至４のいずれか１項に記載の監視制御装置を構成する各手段としてコンピュータを機能させるための監視制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、監視制御装置及び監視制御方法及びプログラムに係り、特に、管理されているIP（Internet Protocol）網で利用するルータの消費電力を削減するための監視制御装置及び監視制御方法及びプログラムに関する。
【背景技術】
【０００２】
ルータでは、サーバとは異なり、待機状態における消費電力は最大負荷時に比べ大きな差異が生じない（約７％ほどの差異となる）ため、待機電力を大きく削減するためにはスリープ状態を活用することが提示されてきた（例えば、非特許文献１参照）。
【０００３】
ネットワーク単位での通信経路制御を行うことによって特定のルータに流れるトラヒックを他のルータへ配分し、スリープを導入するような技術も発展してきている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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月．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
現在提案されている手法の殆どでは、MPLS(Multiprotocol Label Switching)を実装したルータの導入や新規のルーティングプロトコルの導入が必要となっている。そのため、MPLSを利用できるルータを持たなかったり、OSPF（Open Shortest Path First）をルーティングに用いるような現在の一般的なネットワークでは、容易にそれらの技術を用いることができない。
【０００６】
また、OSPFルーティングに適用した手法も提案されているが、OSPFルーティングでは特定の回線への負荷の集中が発生しやすい。この技術では、非特許文献１の手法に負荷を分散させるための重み値組み合わせの計算処理を加えて、特定リンクへの負荷の集中を緩和している。しかし、繰り返し処理を多く含むため計算時間が長くなってしまう上に、スリープ導入計算と負荷分散処理が独立しているため、全体としての最適性に疑問の余地がある。
【０００７】
本発明は、上記の点に鑑みなされたもので、ルータの消費電力削減のためのスリープを導入することが可能なネットワーク装置及び通信経路設定方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明は、OSPFルーティングプロトコルでネットワーク内の通信経路が制御されている通信ネットワークにおいて、省電力化を行うための監視制御装置であって、
ネットワーク構成情報、ネットワークトポロジ情報、トラヒックフロー情報、インタフェース負荷情報を格納する記憶手段と、
前記ネットワークとの間で通信を行い、前記トラヒックフロー情報、前記インタフェース負荷情報を取得して前記記憶手段に格納する通信インタフェース手段と、
前記トラヒックフロー情報からトラヒック行列を生成するトラヒック行列生成手段と、
前記インタフェース負荷情報から前記トラヒック行列に基づいてリンク利用率を求めるリンク利用率計算手段と、
前記リンク利用率に、タブーサーチを利用した局所探索法を適用して最もコストの低いリンクの重み値の組み合わせを算出する負荷分散計算手段と、を有する。
【発明の効果】
【０００９】
上述のように、本発明によれば、MPLSやRate Adaptationなどの現状では実装できていない機器も存在する手法を用いることなく、一般的なOSPFプロトコルのパラメータの変更操作のみで省電力化のためにスリープを導入することが可能となる。
【００１０】
スリープを導入していないリンクからなるネットワークにおいても、OSPFリンク重みの操作のみで負荷分散を行うことにより、高負荷リンクの負荷を緩和すると共に更なるスリープの導入を期待できるようになる。同様の手法である文献１「野村啓仁，矢田健，川原亮一，山田博司．"OSPFリンク重み最適化手法を利用したネットワーク省電力化手法の検討"電子情報通信学会 情報ネットワーク研究会，2011年1月」の技術に対して、スリープ導入リンクの選出と負荷分散を同時に行うことにより計算時間の短縮や全体最適化によるより多くの安定したスリープ導入が期待できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の一実施の形態におけるネットワークの構成図である。
【図２】本発明の一実施の形態におけるネットワーク全体の動作を示す図である。
【図３】本発明の一実施の形態における監視制御装置の構成図である。
【図４】本発明の一実施の形態におけるスリープ導入と負荷分散計算のフローチャートである。
【図５】本発明の一実施の形態におけるスリープ導入と負荷分散計算処理の詳細なフローチャートである。
【図６】本発明の一実施の形態におけるリンク１本あたりのコスト関数の例である。
【図７】本発明の一実施の形態におけるスリープ導入型近傍解の作成処理のフローチャートである。
【発明を実施するための形態】
【００１２】
以下図面と共に、本発明の実施の形態を説明する。
【００１３】
まず、本実施の形態を説明する前に、「重み値」、「経路コスト」、「コスト」について以下のように定義する。
【００１４】
・重み値：OSPFの経路計算に用いるリンクの重み；
・経路コスト：Dijkstra法で算出した２つのノード間の最短パス上のリンクの重み値の和；
・コスト：コスト関数の値；
本発明では、OSPFルーティングプロトコルで網内の通信経路が制御されている通信ネットワークにおいて、各リンクの重み値を変更することによりトラヒックの流れないリンクを作り出し、リンク両端のラインカードへスリープを導入し、消費電力を削減する。
【００１５】
具体的には、OSPF通信網の監視制御装置において、トラヒックフロー情報とトポロジ情報をもとに各リンクの利用率を算出し、スリープ導入及び負荷分散に適合したコスト関数についてタブーサーチを利用した局所探索法により、最もコストの低いリンク重み値の組み合わせを算出する。算出したリンク重み値を実ネットワークに適用する。
【００１６】
まず、本発明のための前提条件を示す。
【００１７】
（１）ルータの消費電力は、約半分をシャーシが、残りの殆どをラインカードによって構成されている。ラインカードはその処理速度が高いほど消費電力が大きくなる（非特許文献１参照）。
【００１８】
（２）ネットワークを構成する各ルータでは、その構成部品単位でのスリープを導入することができる。なお、スリープ状態では、消費電力がほぼゼロになるが、処理を行うことができなくなる。
【００１９】
（３）NetFlowやsFlow等のトラヒックフロー測定技術を用いることによって特定の装置（フローコレクタ）に各機器を流れるフローの情報を収集することができる（文献２「Cisco NetFlow v3 http://www.cisco.com/warp/public/cc/pd/nemnsw/nesv/prodlit/2033_pp.pdf」、文献３「sFlow http://sflow.org/about/index.php」参照）。
【００２０】
（４）上記の（３）で収集したフロー情報から文献４「A Gunnar, M Johansson, T Telkamp, "Traffic Matrix Estimation on a Large IP Backbone-A comparison on Real Data" http://portal.acm.org/citation.cfm?id=1208788.1028807」などの技術によりトラヒック行列を推定することが可能である。
【００２１】
（５）SNMP（Simple Network Management Protocol）などを介して、ネットワーク機器は自身のインタフェースの負荷情報を特定の監視制御装置へ通知することができる。
【００２２】
図１は、本発明の一実施の形態におけるネットワーク構成を示す。
【００２３】
対象とするネットワーク１０は、OSPFをルーティングプロトコルとした単一のASであり、冗長性を持つ構造である。
【００２４】
ルータ２０は、各ルータのラインカードでは待機電力が大きい（前述の前提条件（１））。また、自らを流れるトラヒックフロー情報を監視制御装置１００へ通知する（前述の前提条件（２））。
【００２５】
監視制御装置１００は、ネットワーク１０の構成情報を管理する。また、フローコレクタとして機能し、各ルータ２０からのフロー情報及び負荷情報を取得する。また、後述する演算部を有し、得られたフロー及び負荷情報からトラヒック状況に応じた経路を演算する。また、各ルータにTelnetまたはSSH(SecureSHell)でアクセスし、設定を変更することができる。
【００２６】
次に、図１に示すネットワークの全体の動作について説明する。
【００２７】
図２は、本発明の一実施の形態におけるネットワーク全体の動作を示す。同図では、ネットワークの通信経路を決定するための動作を示している。
【００２８】
（０）初期状態では、ネットワーク１０は、それぞれ事前に設定されているルーティングプロトコルに従い経路を決定する。
【００２９】
（１）各ルータ２０は、自身の各インタフェースに掛かる負荷情報をSNMPによって制御監視装置１００に通知する。また、エッジルータはトラヒック行列を作成するのに必要なフロー情報を収集し、一定の間隔で監視制御装置１００へと報告する。監視制御装置１００は、以下の動作により電力効率を考慮した経路決定を行う（詳細は後述する）。
【００３０】
（２）監視制御装置１００は、フロー情報からトラヒック行列を作成する。
【００３１】
（３）後述するコスト関数を利用したリンク重みの組み合わせ最適化問題を解くことによって、
・利用率が０となり、スリープを導入可能なリンクの選出；
・スリープを導入しないでリンクでの負荷分散を実現するリンク重み値を算出；
を行う。
【００３２】
（４）監視制御装置１００は、最終的なリンクコスト及びそれに基づく経路決定がなされたら、監視制御装置１００により実ネットワークへのリンクコストの設定及び非使用リンクへのスリープの導入が行われる。
【００３３】
次に、監視制御装置１００の構成について説明する。
【００３４】
図３は、本発明の一実施の形態における監視制御装置の構成を示す。
【００３５】
監視制御装置１００は、通信インタフェース部１１０、演算部１２０、記憶部１３０から構成される。監視制御装置１００では、各部間で情報のやり取りを行うことにより、ネットワークの監視及び制御を行う。
【００３６】
通信インタフェース部１１０は、IPアドレスを持ち、各管理対象機器（ルータ）２０との通信処理を行う。
【００３７】
記憶部１３０は、演算部１２０で行う処理に用いる以下の情報を記憶する。
【００３８】
・ネットワーク機器の設定情報；
・ネットワークトポロジ；
・フロー行列；
・各インタフェースの負荷情報；
演算部１２０は、定期的なネットワーク機器（ルータ）２０の管理とスリープ導入のための計算などの以下の処理を行う。記憶部１３０とのやり取りにより、演算に必要な情報の取得と、計算結果や機器情報を格納する。
【００３９】
定期的な情報取得処理としては、SNMPなどにより、定期的にネットワーク１０の各ルータ２０の負荷情報、設定情報を取得すると共に、Netflow等によりルータ２０からのフロー情報を取得する。
【００４０】
また、省電力化処理として、収集されたフロー情報からトラヒック行列を推定し、負荷分散とスリープ導入リンクの作成に必要な重み値の計算を行う。
【００４１】
以下に、演算部１２０の処理を説明する。
【００４２】
演算部１２０では、記憶部１３０から情報を取得して、Fortz. Bらのタブーサーチを利用した局所探索法「文献５「Fortz, B. Thorup, M. "Internet traffic engineering by optimizing OSPF weights", Proc. 19th IEEE Conf. computer communications (INFOCOM), pp. 519-528  http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=832225&tag=1」）」を基にして、スリープ導入リンクの算出とスリープを導入しない各リンクに利用率が平準になるようなリンク重み値の組み合わせを算出する。負荷平準化には、あるノード間に複数の経路コスト（コスト関数）が等しいパスが存在する際にトラヒックが分散されるというOSPFの性質を利用する。
【００４３】
図４は、本発明の一実施の形態におけるスリープ導入と負荷分散計算処理のフローチャートである。
【００４４】
ステップ１０１）  まず、演算部１２０は、記憶部１３０からスリープ導入計算の出力であるネットワークトポロジ（帯域幅）、リンク利用率の上限閾値θ、下限閾値ηを読み込み、初期解を生成する。具体的には、重み値の可能解の集合W={1，…，wmax}からランダムに値を取得し、各リンクの重み値として設定する。これをこのリンクに対する重み値の組み合わせの初期解とする。
【００４５】
ステップ１０２）  初期解におけるコストを算出する。
【００４６】
記憶部１３０のフロー情報に基づいて生成されたトラヒック行列とステップ１０１で求められた初期解、記憶部１３０から取得したトポロジを用いて、各リンクの利用率を算出する。算出した利用率をそれぞれコスト関数に適用して、それらの和を初期解のコストとして算出する。なお、コスト関数は、リンク利用率が０、もしくは（η，θ］以外の場合にコストが大きい値をとる性質を持つ。詳細は後述する。なお、トラヒック行列は、ネットワーク１０を流れるトラヒックの行列を作成し、メモリ（図示せず）に格納されているものとする。トラヒック行列を生成する方法としては、例えば、前述の文献３による方法を用いるものとする。
【００４７】
ステップ１０３）  次に演算部１２０は、近傍解を作成する。
【００４８】
現在の解から、前述の文献４の手法及びスリープ促進法の作成手法に従い、Ｎｎ個の近傍解を作成する。この際に、作成した近傍解がハッシュテーブル１(HT1)（タブーリスト）に存在する場合はこれを破棄する。
【００４９】
ステップ１０４）  次に、ステップ１０３で作成された近傍解のコスト評価、及び、最小コスト解の選出を行う。作成した近傍解のうち、ハッシュテーブル２（HT2）に存在しないものそれぞれに対してステップ１０２と同様にコストを算出する。近傍解の中で最もコストが低いものを次の解として選出し、解及びコスト値をHT1に登録する。
【００５０】
ステップ１０５）  Ｎｉ回になるまで、ステップ１０３、１０４の処理を繰り返す。このとき、一定の繰り返し回数毎に、現行解の幾つかの値をランダムに変動させるような摂動を与えて新規解とし、探索範囲を変更する。
【００５１】
ステップ１０６）  上記のステップ１０３〜１０５の処理をＮｉ回繰り返したら、HT1において最もコストの低かった解を最適解として出力する。
【００５２】
次に、上記の図４のフローチャートの動作を図５を用いて詳細に説明する。
【００５３】
＜ステップ１０１＞
ステップ２０１）  演算部１２０は、ネットワークトポロジ（帯域）を記憶部１３０から読み出し、トラヒック行列をメモリ（図示せず）から取得するものとする。
【００５４】
ステップ２０２）  所定の上限閾値θと下限閾値ηからコスト関数のパラメータを決定する。
【００５５】
＜ステップ１０２＞
ステップ２０３）  初期解として、コスト関数を用いて重み値を計算する。スリープ導入と負荷分散のための重み値計算に用いるコスト関数は後述する図７に示すように設定する。
【００５６】
ステップ２０４）  演算部１２０は、Shortest Pathを算出する。
【００５７】
ステップ２０５）  演算部１２０は、ステップ２０１で取得したトラヒック行列、ネットワークトポロジ（帯域）と、上記で算出された初期解を用いて負荷（リンク利用率）を計算する。
【００５８】
ステップ２０６）  次に、演算部１２０は、リンク利用率をコスト関数に適用することで初期解のコストを算出する。詳細については後述する。
【００５９】
ステップ２０７）  演算部１２０は、上記で求められた解（初期解）とコストをメモリ（図示せず）上のタブーリストとして利用されるハッシュテーブル１（HT1）に格納する。
【００６０】
＜ステップ１０３＞
ステップ２０８）  HT1に格納された現在の解から後述する方法を用いて近傍解ｗ'を作成する。
【００６１】
＜ステップ１０４＞
ステップ２０９）  求められた近傍解ｗ'がHT１に含まれるかを判定し、含まれる場合にはステップ２１０に移行し、含まれない場合はステップ２１１に移行する。
【００６２】
ステップ２１０）  近傍解ｗ'を破棄し、ステップ２０８に戻る。
【００６３】
ステップ２１１）  近傍解ｗ'の数がNnに達したかを判定し、達した場合はステップ２１２に移行し、達していない場合はステップ２０８に移行する。
【００６４】
ステップ２１２）  メモリ（図示せず）内のコスト評価済みの解とコスト値を記憶するためのハッシュテーブル２（HT2）に含まれていない近傍解を抽出する。
【００６５】
ステップ２１３）  抽出した解の近傍解のShortest Pathを算出する。
【００６６】
ステップ２１４）  ステップ２１２で抽出された解の負荷を算出する。
【００６７】
ステップ２１５）  さらに、求められた解及びコストを算出する。算出方法は、ステップ２０６と同様である。
【００６８】
ステップ２１７）  全近傍解の中で最もコストの低い解を次の解として抽出する。
【００６９】
ステップ２１８）  抽出された最低コストの解とコストをHT1に格納する。
【００７０】
＜ステップ１０５＞
ステップ２１９）  HT1の要素数がＮｉ個に達したかを判定し、達した場合にはステップ２２０に移行し、達していない場合はステップ２０８に戻る。
【００７１】
＜ステップ１０６＞
ステップ２２０）  HT1中の最低コストを持つ解を抽出し、ネットワークトポロジ（重み値）として出力する。
【００７２】
上記のステップ２０６，２１５のコスト計算で用いられるコスト関数について説明する。
【００７３】
図６は、本発明の一実施の形態におけるコスト関数の例であり、リンク容量ｃa＝１におけるコストφ（ｌa，ｃa）の値の関係を示す。
【００７４】
同図に示すように、Forzらのコスト関数（文献５）を元に、閾値θに合わせて傾斜が変動するように変更を行っている。図６において、上限閾値θ（＝０．８）より大きい場合はコスト値を増大させている。また、スリープ可能なリンクの利用率を０にするために、利用率０でのコストを０としている。また、区間（０，η］（例えば、０からη＝０．２までの区間）では、スリープを導入するために利用率を下げるか、他のトラヒックを引き受けるようにコスト値を高くしている。また、区間（０，η］では、解の探索において低利用率のリンクの利用率がより低くなるように０に向けて下がるような傾斜をつけている。
【００７５】
ネットワークのコストΦは、
【００７６】
【数１】
2012175393.tif 000003
により求められる。Aはネットワークリンクａの集合、ｌaはリンクａの負荷、ｃaはリンクａの容量である。
【００７７】
【数２】
2012175393.tif 000004
上記において、φ（ｌa,ｃa）は、リンクａのコストであり、ｌa/ｃaはリンク利用率である。
【００７８】
次に、上記のステップ１０３（ステップ２０８）の近傍解を求める方法について説明する。
【００７９】
近傍解は、Single Changeと Equal Balancing Flowと、下記に示すスリープ導入型の近傍解を求める方法により求められる。
【００８０】
図７は、本発明の一実施の形態におけるスリープ導入型近傍解の作成処理のフローチャートである。
【００８１】
ステップ３０１）  前述のステップ２０７において、HT１に格納された現在の解を取得し、ネットワークトポロジ及び各リンクの利用率行列を取得する。
【００８２】
ステップ３０２）  以下の条件を満たすリンクの集合を作成する。
【００８３】
・０＜利用率≦η
・重み値がWmax未満
ステップ３０３）  ステップ３０２のリンク集合からリンクを一つランダムに抽出する。
【００８４】
ステップ３０４）  以下の更新式により重み値を現在よりも大きい値に更新する。
【００８５】
【数３】
2012175393.tif 000005
上記のように、OSPFルーティングプロトコルで網内の通信経路が制御されている通信ネットワークにおいて、各リンクの重み値を変更することによりトラヒックの流れないリンクを作り出し、リンク両端のラインカードへスリープを導入することで、消費電力を削減することができる。
【００８６】
なお、上記の図３に示す監視制御装置１００の各構成要素の動作をプログラムとして構築し、監視制御装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００８８】
１０  ネットワーク
２０  ルータ
１００  監視制御装置
１１０  通信インタフェース
１２０  演算部
１３０  記憶部
【図１】
2012175393.tif 000006
【図２】
2012175393.tif 000007
【図３】
2012175393.tif 000008
【図４】
2012175393.tif 000009
【図５】
2012175393.tif 000010
【図６】
2012175393.tif 000011
【図７】
2012175393.tif 000012