JP5779557B2

JP5779557B2 - 経路制御装置及び方法及びプログラム

Info

Publication number: JP5779557B2
Application number: JP2012178413A
Authority: JP
Inventors: 裕之北田; 雅之辻野
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2012-08-10
Filing date: 2012-08-10
Publication date: 2015-09-16
Anticipated expiration: 2032-08-10
Also published as: JP2014036423A

Description

本発明は、経路制御装置及び方法及びプログラムに係り、特に、通信ネットワークのトポロジ・帯域容量、交流トラヒック（端点間トラヒック）、通信ネットワークを構成する各通信装置の消費電力量、及び、予備経路の設計ポリシを条件として、消費電力が少ない現用経路、及び予備経路を算出するための通信ネットワークの経路制御装置及び方法及びプログラムに関する。

低電力状態に移行可能な通信装置を増やすには、通信ネットワークのトラヒックができるだけ少ない通信装置を流れるように集約することが有効である。このようにトラヒックを集約して一部の通信装置のみで通信を維持しようという考えを"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に対して、そのリンクの帯域容量を残余帯域容量U_jとして設定する。図６（ａ）において、リンク上の数字が帯域容量を示す。

ステップ２０３）削減効果算出部１０は、情報記憶部30の端点間トラヒックを読み込み、端点間トラヒックｋ（トラヒック量D_k）を選択する。端点間トラヒックの選択方法としては、例えば、kの昇順や、D_kの降順（トラヒック量が多いトラヒックから選択）等が考えられるが、これに限定されるものではない。図６（ａ）の例では、端点間トラヒック１（ノード１−ノード５）の端点間トラヒック量D_１＝２であり、端点間トラヒック２（ノード１−ノード６）の端点間トラヒック量D₂＝３であるとする。

ステップ２０４）削減効果算出部１０は、残余帯域容量U_jが端点間トラヒック量D_kより小さい（U_j＜D_k）リンクを選択経路記憶部５０に格納されている経路上から削除する。なお、初回の処理の場合は、ステップ２０１〜２０３の処理を経た経路を対象とする。図６（ｂ）の例では、ノード２を削除している。同図のリンク上の数字は残余帯域容量U_jを示している。

ステップ２０５）端点間において、２経路選択することが可能かを判定し、可能である場合はステップ２０６に移行し、不可能である場合は、ステップ２１０に移行する。

ステップ２０６）削除されていない全てのリンクjに対して、そのリンクの距離（端点間トラヒックでの利用により追加で発生する消費電力）を以下のように設定する。但し、ｆ_jはリンクONに伴う消費電力、ｇ_jはリンクを流れるトラヒック比例の消費電力である。なお、ｆ_j、ｇ_jは予め情報記憶部３０に格納されているものとする。

・以前に選択した端点間トラヒックｋが当該リンクを経由しないとき：
C_j: = ｆ_j+ ｇ_j× D_k
・以前に選択したｋが当該リンクを経由するとき：
C_j:= ｇ_j × D_k
図６（ｃ）の例では、ｘ/ｙ(ｘ：ｆ_j,ｙ：ｇ_j)とすると、ノード1−ノード４のｘ/ｙは、３０／３となる。

ステップ２０７）設計ポリシに応じた最短の現用・予備経路を算出する。最短経路は、上記のU_j≧０として、経路上のC_jの和が最小になる経路を求める。具体的には、非特許文献４「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）を用いて算出することが可能である。

図６（ｄ）は、端点間トラヒック１を選択した場合の例である。リンク上の数字はU_j/C_jを示す。当該U_j/C_jの値が最も小さい経路（ノード１→４→５）を現用経路とし、当該現用経路を含まず、次にU_j/C_jの値が小さい経路（ノード１→３→６→５）を予備経路とし、選択経路記憶部５０に格納する。また、同図（ｅ）は、端点間トラヒック２を選択した場合の例である。同図では、ノード１→４→６のリンクはどの端点間トラヒックも経由しないので、未使用リンクとして当該リンクを削除（電源OFF）としている例である。

ステップ２０８）ステップ２０７で算出した現用・予備経路で経由するリンクの帯域容量を以下のように、端点間トラヒックｋのトラヒック量D_k分小さくする。

U_j: = U_j − D_k
ステップ２０９）他に端点間トラヒックがあるかを判定し、ある場合には、ステップ２０４で削除したリンクを戻し、ステップ２０３に戻り、ない場合は処理を終了する。

ステップ２１０）ステップ２０５において、端点間に２経路選択することができない場合は、削減効果なしと判定し、処理を終了する。

なお、どの端点間トラヒックも経由しないリンクは電源OFFとして消費電力の削減効果を算出する。

上記の図２に示す構成要素の各動作をプログラムとして構築し、経路制御装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

１０削減効果算出部
３０トポロジ情報記憶部
５０選択経路記憶部

Claims

トラヒックが流れる通信ネットワークにおいて、当該通信ネットワーク全体での電力消費量を削減することが可能となるように経路算出を行う経路制御装置であって、
前記通信ネットワークのトポロジ、当該通信ネットワークの帯域容量、端点間トラヒック、当該通信ネットワークを構成する各ノードの消費電力量及び予備経路の設計ポリシを受け付ける入力手段と、
前記通信ネットワークにおける通常状態のノードを低電力状態に移行させ、当該ノードを低電力状態に移行した状況の下で、与えられた端点間トラヒックを収容する現用経路、及び当該現用経路と同一でない予備経路を、経路上の各リンクの消費電力量の和が最小になるように算出し、前記ノードを低電力状態に移行させたことによる前記通信ネットワークの消費電力の削減効果を算出する削減効果算出処理を実行する削減効果算出手段と、を備え、
前記削減効果算出手段は、
前記削減効果算出処理を通常状態の各ノードについて実行し、削減効果が最大となるノードを低電力状態に移行させることを決定し、当該ノードを削除した経路を前記通信ネットワークの経路として経路記憶手段に格納する処理を、消費電力の削減効果のあるノードがなくなるまで繰り返し実行し、最終的に前記経路記憶手段に格納されている経路を出力する
ことを特徴とする経路制御装置。
前記削減効果算出手段は、前記通信ネットワークの帯域容量、前記通信ネットワークを構成する各ノードの消費電力量に基づいて、前記現用経路及び前記予備経路を、MIP（Mixed Integer Programming）を用いて算出する手段を含む
請求項１に記載の経路制御装置。
トラヒックが流れる通信ネットワークにおいて、当該通信ネットワーク全体での電力消費量を削減することが可能となるように経路算出を行う経路制御方法であって、
入力手段、削減効果算出手段、経路記憶手段を有する装置において、
前記入力手段が、前記通信ネットワークのトポロジ、当該通信ネットワークの帯域容量、端点間トラヒック、当該通信ネットワークを構成する各ノードの消費電力量及び予備経路の設計ポリシを受け付ける入力ステップと、
前記削減効果算出手段が、前記通信ネットワークにおける通常状態のノードを低電力状態に移行させ、当該ノードを低電力状態に移行した状況の下で、与えられた端点間トラヒックを収容する現用経路、及び当該現用経路と同一でない予備経路を、経路上の各リンクの消費電力量の和が最小になるように算出し、前記ノードを低電力状態に移行させたことによる前記通信ネットワークの消費電力の削減効果を算出する削減効果算出処理を実行する削減効果算出ステップと、を備え、
前記削減効果算出ステップにおいて、前記削減効果算出手段は、
前記削減効果算出処理を通常状態の各ノードについて実行し、削減効果が最大となるノードを低電力状態に移行させることを決定し、当該ノードを削除した経路を前記通信ネットワークの経路として前記経路記憶手段に格納する処理を、消費電力の削減効果のあるノードがなくなるまで繰り返し実行し、最終的に前記経路記憶手段に格納されている経路を出力する
ことを特徴とする経路制御方法。
コンピュータを、
請求項１又は２に記載の経路制御装置の各手段として機能させるための経路制御プログラム。