(57)【要約】【課題】  トラヒックが流れない通信装置を作り出し、通信装置を低電力状態に移行し、通信ネットワーク全体での電力消費量を削減する。【解決手段】  本発明は、通信ネットワークのトポロジ、該通信ネットワークの帯域容量、端点間トラヒック、該通信ネットワークを構成する各ノードの消費電力量及び予備経路の設計ポリシを受け付け、各ノードの消費電力量に基づいて、低電力状態に移行した場合の消費電力削減効果が高い順に、低電力状態に移行するノードを選択し、選択されたノードからなる経路を経路記憶手段に格納し、消費電力の効果がなくなるまで処理を繰り返す。【選択図】  図２
2014036423.tif 000002
【特許請求の範囲】
【請求項１】
トラヒックが流れる通信ネットワークにおいて、該通信ネットワーク全体での電力消費量を削減することが可能となるように経路を行う経路制御装置であって、
前記通信ネットワークのトポロジ、該通信ネットワークの帯域容量、端点間トラヒック、該通信ネットワークを構成する各ノードの消費電力量及び予備経路の設計ポリシを受け付ける入力手段と、
前記各ノードの消費電力量に基づいて、低電力状態に移行した場合の消費電力削減効果が高い順に、低電力状態に移行するノードを選択し、選択されたノードからなる経路を経路記憶手段に格納し、消費電力の効果がなくなるまで処理を繰り返す削減効果算出手段と、
を有することを特徴とする経路制御装置。
【請求項２】
前記削減効果算出手段は、
前記低電力状態に移行するノードが選択される毎に、該ノードを低電力状態に移行した状況の下で、現用経路及び該現用経路と同一でない予備経路を構築した際の消費電力の削減効果を算出する手段を含む
請求項1記載の経路制御装置。
【請求項３】
前記通信ネットワークのトポロジ、前記通信ネットワークの帯域容量、前記端点間トラヒック、前記通信ネットワークを構成する各ノードの消費電力量及び前記予備経路の設計ポリシを条件として、消費電力が少ない現用経路及び予備経路を算出する手段を含む
請求項２記載の経路制御装置。
【請求項４】
前記通信ネットワークの帯域容量、前記通信ネットワークを構成する各ノードの消費電力量に基づいて、消費電力量を最小とする現用経路及び予備経路を、MIP（Mixed Integer Programming）を用いて算出する手段を含む
請求項３記載の経路制御装置。
【請求項５】
前記端点間トラヒックで選択可能な現用経路と予備経路の組み合わせのうち、前記設計ポリシを守る最も消費電力が少ない経路を選択する手段を含む
請求項３または４記載の経路制御装置。
【請求項６】
トラヒックが流れる通信ネットワークにおいて、該通信ネットワーク全体での電力消費量を削減することが可能となるように経路を行う経路制御方法であって、
入力手段、削減効果算出手段、経路記憶手段を有する装置において、
前記入力手段が、前記通信ネットワークのトポロジ、該通信ネットワークの帯域容量、端点間トラヒック、該通信ネットワークを構成する各ノードの消費電力量及び予備経路の設計ポリシを受け付ける入力ステップと、
前記削減効果算出手段が、前記各ノードの消費電力量に基づいて、低電力状態に移行した場合の消費電力削減効果が高い順に、低電力状態に移行するノードを選択し、選択されたノードからなる経路を前記経路記憶手段に格納し、消費電力の効果がなくなるまで処理を繰り返す削減効果算出ステップと、
を行うことを特徴とする経路制御方法。
【請求項７】
前記削減効果算出ステップにおいて、
前記低電力状態に移行するノードが選択される毎に、該ノードを低電力状態に移行した状況の下で、現用経路及び該現用経路と同一でない予備経路を構築した際の消費電力の削減効果を算出し、
前記通信ネットワークのトポロジ、前記通信ネットワークの帯域容量、前記端点間トラヒック、前記通信ネットワークを構成する各ノードの消費電力量及び前記予備経路の設計ポリシを条件として、消費電力が少ない現用経路及び予備経路を算出する
請求項６記載の経路制御方法。
【請求項８】
コンピュータを、
請求項1乃至５のいずれか1項に記載の経路制御装置の各手段として機能させるための経路制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路制御装置及び方法及びプログラムに係り、特に、通信ネットワークのトポロジ・帯域容量、交流トラヒック（端点間トラヒック）、通信ネットワークを構成する各通信装置の消費電力量、及び、予備経路の設計ポリシを条件として、消費電力が少ない現用経路、及び予備経路を算出するための通信ネットワークの経路制御装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
低電力状態に移行可能な通信装置を増やすには、通信ネットワークのトラヒックができるだけ少ない通信装置を流れるように集約することが有効である。このようにトラヒックを集約して一部の通信装置のみで通信を維持しようという考えを"resource consolidation"という。電力消費量削減を目標とし、この"resource consolidation"の考えに基づき、トラヒックを流す経路を決定する、"energy-aware routing"と呼ばれる技術がある（例えば、非特許文献1、２参照）。
【０００３】
第1の従来技術は、通信ネットワークのトポロジ・帯域容量、交流トラヒック（端点間トラヒック）、通信ネットワークを構成する各通信装置の消費電力量を条件として与え、通信ネットワーク全体での消費電力量を少なくするような経路を算出するものである。
【０００４】
非特許文献１は、発見的な手法により経路を数理的に求める技術である。非特許文献１の技術は、非特許文献２の技術に対して、経路を求めるのにかかる計算負荷が小さいという利点がある反面、消費電力の削減効果が限定的であるという欠点がある。
【０００５】
第２の従来技術は、予備経路も含めてトラヒックを流す経路を算出する技術として、"resilient network design"と呼ばれる分野で検討されている技術がある（例えば、非特許文献3参照）。
【０００６】
第２の従来技術は、通信ネットワークのトポロジ・帯域容量、予備経路の選択条件、交流トラヒック（端点間トラヒック）、通信ネットワークを構成する各通信装置の費用を条件として与え、通信ネットワーク全体の総費用を小さくするような経路を算出するものである。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】L. Chiaraviglio, M. Mellia, and F. Neri, "Reducing Power Consumption in Backbone Networks," in 2009 IEEE International Conference on Communications, 2009, pp. 1-6.
【非特許文献２】A. P. Bianzino, C. Chaudet, F. Larroca, D. Rossi, and J. L. Rougier, "Energy-aware routing: A reality check," in 2010 IEEE Globecom Workshops, 2010, pp. 1422-1427.
【非特許文献３】M. Pioro, and D. Medhi, "Routing, Flow, and Capacity Design in Communication and computer Networks," Morgan Kaufmann, 2004, pp. 353-401 (Chapter 9 "Restoration and Protection Design of Resilient Networks".
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記第1の従来技術は、いずれも各端点間トラヒックに対して単一の経路を求めるものであり、通信ネットワーク上の通信装置が故障した場合の予備経路での通信リソースの確保を保証するものではない。低電力状態に移行した通信装置を通常状態に復旧するには、一定の時間を要する（現状の技術レベルからの目安としては、ノードで数分程度、リンクで数十秒程度の時間を要する）ため、所謂キャリアクラスと呼ばれる可用性の高い通信サービスを提供する際には、低電力状態の通信装置を予備経路の通信リソースとして活用できない。このため、通信事業者が運用する通信ネットワークで低電力状態とする通信装置を決定する際には、（トラヒックの転送が可能な通常状態の通信装置による）予備経路についても考慮に含めることが重要である。
【０００９】
第２の従来技術は、予備経路についての考慮に含めて経路を算出するものであるが、総費用の削減を目的（概して最短パスの選択を指向）するものであり、"resource consolidation"の考えに基づき、低電力状態に移行可能な通信装置を増やせるような経路を算出するものではない。
【００１０】
本発明は上記の点に鑑みなされたもので、トラヒックが流れない通信装置を作り出し、通信装置を低電力状態に移行し、通信ネットワーク全体での電力消費量を削減することが可能な通信ネットワークの経路制御装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するため、本発明（請求項１）は、トラヒックが流れる通信ネットワークにおいて、該通信ネットワーク全体での電力消費量を削減することが可能となるように経路を行う経路制御装置であって、
前記通信ネットワークのトポロジ、該通信ネットワークの帯域容量、端点間トラヒック、該通信ネットワークを構成する各ノードの消費電力量及び予備経路の設計ポリシを受け付ける入力手段と、
前記各ノードの消費電力量に基づいて、低電力状態に移行した場合の消費電力削減効果が高い順に、低電力状態に移行するノードを選択し、選択されたノードからなる経路を経路記憶手段に格納し、消費電力の効果がなくなるまで処理を繰り返す削減効果算出手段と、を有する。
【００１２】
また、本発明（請求項２）は、前記削減効果算出手段において、
前記低電力状態に移行するノードが選択される毎に、該ノードを低電力状態に移行した状況の下で、現用経路及び該現用経路と同一でない予備経路を構築した際の消費電力の削減効果を算出する手段を含む。
【００１３】
また、本発明（請求項３）は、前記通信ネットワークのトポロジ、前記通信ネットワークの帯域容量、前記端点間トラヒック、前記通信ネットワークを構成する各ノードの消費電力量及び前記予備経路の設計ポリシを条件として、消費電力が少ない現用経路及び予備経路を算出する手段を含む。
【００１４】
また、本発明（請求項４）は、前記通信ネットワークの帯域容量、前記通信ネットワークを構成する各ノードの消費電力量に基づいて、消費電力量を最小とする現用経路及び予備経路を、MIP（Mixed Integer Programming）を用いて算出する手段を含む。
【００１５】
また、本発明（請求項５）は、前記端点間トラヒックで選択可能な現用経路と予備経路の組み合わせのうち、前記設計ポリシを守る最も消費電力が少ない経路を選択する手段を含む。
【発明の効果】
【００１６】
上記のように、本発明によれば、通信ネットワークにおいて、予備経路を含めた経路選定を行うことで、通信ネットワークの信頼性を担保する、通信ネットワーク全体の消費電力削減に繋がる経路制御が可能になる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態における経路制御装置の構成図である。
【図３】本発明の一実施の形態における削減効果算出部の概要動作のフローチャートである。
【図４】本発明の一実施の形態における削減効果算出部の処理イメージである。
【図５】本発明の一実施の形態におけるノードOFF効果算出処理のフローチャートである。
【図６】本発明の一実施の形態におけるノードOFF効果算出処理のイメージである。
【発明を実施するための形態】
【００１８】
以下、図面と共に本発明の実施の形態を説明する。
【００１９】
図１は、本発明の一実施の形態におけるシステム構成図である。
【００２０】
同図に示すように、本発明の経路制御装置は、通信装置の消費電力を考慮し、ネットワーク全体の消費電力を最小する経路を算出する。また、現用経路及び現用経路と同一でない予備経路を同時に算出する。
【００２１】
図２は、本発明の一実施の形態における経路制御装置の構成を示す。
【００２２】
同図に示す経路制御装置は、削減効果算出部１０、入力部２０、情報記憶部３０、選択経路記憶部５０を有する。情報記憶部３０には、通信ネットワークのトポロジ情報、通信ネットワークの帯域容量、端点間トラヒック（トラヒック量を含む）、通信ネットワークを構成する各通信装置の各通信装置の消費電力量が格納されている。本実施の形態では、これらの情報を１つの情報記憶部３０に格納しているがこの例に限定されることなく、情報の種類毎に記憶してもよいし、動的な情報、静的な情報に分けて格納するようにしてもよい。選択経路記憶部５０は、削減効果算出部３０で算出された現用経路、予備経路を格納する。
【００２３】
入力部２０は、情報記憶部３０から蓄積されている情報を読み出して削減効果算出部１０に出力する。
【００２４】
削減効果算出部１０は、情報記憶部３０からトポロジ情報、通信ネットワークの帯域容量、端点間トラヒック、各通信装置の消費電力量を読み込み、通信装置を電源ON状態からOFＦ状態にしたときのノードの消費電力の削減効果を算出し、各回の経路情報を選択経路記憶部５０に格納する。消費電力の削減効果は、全ての通信装置の電源をONとする通信ネットワーク（初期状態）から始め、消費電力の削減効果の大きいノードから削減効果がなくなるまで順次ノードを削減して選択経路記憶部５０に格納していくものである。低電力状態への移行可能性を（消費電力の削減効果の大きい）ノードについてリンクよりも優先的に考慮する手法である。つまり、消費電力が最小の経路に対する近似解を求めるものである。但し、最小であることは保証されない。
【００２５】
なお、通信装置の電源をON/OFFするとは、実際に電源をON/OFFするのではなく、通信装置（ノード）を経路として選択できるか否かを示すものである。電源をONにするとは、通信装置（ノード、リンク）を通常状態にすること、つまり、経路として選択可能であることを指し、電源をOFFにするとは、通信装置を低電力状態（シャットダウンまたはスリープ状態）にすること、つまり、経路として選択できない扱いにすることを指す。
【００２６】
図３は、本発明の一実施の形態の削減効果算出部の処理のフローチャートを示し、図４にその処理イメージを示す。
【００２７】
ステップ１００）  まず、削減効果算出部１０は、情報記憶部３０から読み込んだ通信ネットワークの全ノードをON（選択可能状態）にする。図４（ａ）は、端点間トラヒック１⇒５、1⇒６が全ノードON時の消費電力最小経路である。
【００２８】
ステップ２００）  削減効果算出部１０は、電源ONのノードに対し、情報記憶部３０から各通信装置の消費電力を読み出して、電源をOFFにすることによる消費電力の削減効果を算出し、メモリ（図示せず）に格納する。図４（ｂ）の例において、ノード2をOFFにした場合（経路として選択しない場合）は、ノードOFF効果として500kWが削減され、ノード3をOFFにした場合は、300kWが削減され、ノード4をOFFにした場合は削減効果がなかったことを示す。
【００２９】
ステップ３００）  メモリ（図示せず）に格納されているノードとその消費電力量を参照し、低消費電力の削減効果がある（プラスになる）ノードが存在するかを判定する。上記のステップ２００の例では、ノード2と、ノード3をOFFした場合に効果があるので、ステップ４００に移行する。
【００３０】
ステップ４００）  最も消費電力の削減効果が高いノードをOFFにし、図４（ｄ）の経路（ノード2が削除された経路）で選択経路記憶部５０を更新し、ステップ２００に戻る。
【００３１】
上記のステップ２００以降の処理を、消費電力の削減効果があるノードがなくなるまで繰り返し、最終的に選択経路記憶部５０に格納されている経路を出力する。
【００３２】
上記のステップ２００のノードOFF効果算出処理を詳細に説明する。
【００３３】
図５は、本発明の一実施の形態におけるノードOFF効果算出処理のフローチャートであり、図６は、そのイメージを示す。
【００３４】
ステップ２０１）  削減効果算出部１０は、電源OFF時の消費電力の削減効果の算出対象とするノードの電源をOFFにする。
【００３５】
ステップ２０２）  削減効果算出部１０は、トポロジ情報記憶部３０の帯域容量を参照して、ONになっている全てのリンクjに対して、そのリンクの帯域容量を残余帯域容量Ujとして設定する。図６（ａ）において、リンク上の数字が帯域容量を示す。
【００３６】
ステップ２０３）  削減効果算出部１０は、情報記憶部30の端点間トラヒックを読み込み、端点間トラヒックｋ（トラヒック量Dk）を選択する。端点間トラヒックの選択方法としては、例えば、kの昇順や、Dkの降順（トラヒック量が多いトラヒックから選択）等が考えられるが、これに限定されるものではない。図６（ａ）の例では、端点間トラヒック１（ノード１−ノード５）の端点間トラヒック量D１＝２であり、端点間トラヒック２（ノード１−ノード６）の端点間トラヒック量D2＝３であるとする。
【００３７】
ステップ２０４）  削減効果算出部１０は、残余帯域容量Ujが端点間トラヒック量Dkより小さい（Uj＜Dk）リンクを選択経路記憶部５０に格納されている経路上から削除する。なお、初回の処理の場合は、ステップ２０１〜２０３の処理を経た経路を対象とする。図６（ｂ）の例では、ノード２を削除している。同図のリンク上の数字は残余帯域容量Ujを示している。
【００３８】
ステップ２０５）  端点間において、２経路選択することが可能かを判定し、可能である場合はステップ２０６に移行し、不可能である場合は、ステップ２１０に移行する。
【００３９】
ステップ２０６）  削除されていない全てのリンクjに対して、そのリンクの距離（端点間トラヒックでの利用により追加で発生する消費電力）を以下のように設定する。但し、ｆjはリンクONに伴う消費電力、ｇjはリンクを流れるトラヒック比例の消費電力である。なお、ｆj、ｇjは予め情報記憶部３０に格納されているものとする。
【００４０】
・以前に選択した端点間トラヒックｋが当該リンクを経由しないとき：
Cj: = ｆj+ ｇj× Dk
・以前に選択したｋが当該リンクを経由するとき：
Cj:= ｇj × Dk
図６（ｃ）の例では、ｘ/ｙ(ｘ：ｆj,ｙ：ｇj)とすると、ノード1−ノード４のｘ/ｙは、３０／３となる。
【００４１】
ステップ２０７）  設計ポリシに応じた最短の現用・予備経路を算出する。最短経路は、上記のUj≧０として、経路上のCjの和が最小になる経路を求める。具体的には、非特許文献４「J. W. Surballe and R. E. Tarian.  A quick method of finding shortest pairs of disjoint paths.  Networks, 14, 1984.」のalgorithm"等の既存の技術を用いることにより実現可能である。例えば、消費電力量を最小とする現用経路及び予備経路を、通信ネットワークの帯域容量、前記通信ネットワークを構成する各ノードの消費電力量に基づいて、MIP（Mixed Integer Programming）を用いて算出することが可能である。
【００４２】
図６（ｄ）は、端点間トラヒック１を選択した場合の例である。リンク上の数字はUj/Cjを示す。当該Uj/Cjの値が最も小さい経路（ノード１→４→５）を現用経路とし、当該現用経路を含まず、次にUj/Cjの値が小さい経路（ノード１→３→６→５）を予備経路とし、選択経路記憶部５０に格納する。また、同図（ｅ）は、端点間トラヒック２を選択した場合の例である。同図では、ノード１→４→６のリンクはどの端点間トラヒックも経由しないので、未使用リンクとして当該リンクを削除（電源OFF）としている例である。
【００４３】
ステップ２０８）  ステップ２０７で算出した現用・予備経路で経由するリンクの帯域容量を以下のように、端点間トラヒックｋのトラヒック量D k分小さくする。
【００４４】
U j: = U j − D k
ステップ２０９）  他に端点間トラヒックがあるかを判定し、ある場合には、ステップ２０４で削除したリンクを戻し、ステップ２０３に戻り、ない場合は処理を終了する。
【００４５】
ステップ２１０）  ステップ２０５において、端点間に２経路選択することができない場合は、削減効果なしと判定し、処理を終了する。
【００４６】
なお、どの端点間トラヒックも経由しないリンクは電源OFFとして消費電力の削減効果を算出する。
【００４７】
上記の図２に示す構成要素の各動作をプログラムとして構築し、経路制御装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４８】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４９】
１０  削減効果算出部
３０  トポロジ情報記憶部
５０  選択経路記憶部
【図１】
2014036423.tif 000003
【図２】
2014036423.tif 000004
【図３】
2014036423.tif 000005
【図４】
2014036423.tif 000006
【図５】
2014036423.tif 000007
【図６】
2014036423.tif 000008