光ネットワークのエネルギー効率のよい再最適化のための方法
【課題】光ネットワークにおいて、ネットワークの増大するトラフィック需要を満たす新たなリンクが経時的にノード間に加えられる。既存のリンクは通常変更されず、その結果、最低エネルギー消費を有しないネットワークが生じる。
【解決手段】すべての時点において必要とされるトラフィック需要をサポートしながら、全体ネットワークのエネルギー消費を低減する方法を提供する。ネットワークは、複数のソースノードと、複数の宛先ノードとを含む。ネットワークは、エッジによって接続されたノードのグラフによって表される。各ノードは光ネットワーク要素を表し、各エッジは２つの光ネットワーク要素を接続するパスを表す。各エッジは需要でラベル付けされる。最も低い需要を有する非ブリッジエッジがグラフから除去され、最も高い需要を有する非ブリッジエッジにその最も低い需要が加えられる。これらのステップは終了条件に達するまで繰り返される。
【解決手段】すべての時点において必要とされるトラフィック需要をサポートしながら、全体ネットワークのエネルギー消費を低減する方法を提供する。ネットワークは、複数のソースノードと、複数の宛先ノードとを含む。ネットワークは、エッジによって接続されたノードのグラフによって表される。各ノードは光ネットワーク要素を表し、各エッジは２つの光ネットワーク要素を接続するパスを表す。各エッジは需要でラベル付けされる。最も低い需要を有する非ブリッジエッジがグラフから除去され、最も高い需要を有する非ブリッジエッジにその最も低い需要が加えられる。これらのステップは終了条件に達するまで繰り返される。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には光ネットワークに関し、より詳細には、光ネットワークにおけるリンクをエネルギー効率のよい方式で再最適化することに関する。
【背景技術】
【０００２】
光ネットワークは、インタネットの規模の増大を受け、高速に拡大を続けている。光ネットワークの拡大とともに、光ネットワークのエネルギー消費が増大し、それによって、データネットワークのエネルギー消費を合わせると、一国の総エネルギー消費のかなりの割合となっている。たとえば、２００５年のＴｅｌｅｃｏｍ Ｉｔａｌｉａ社のネットワークの消費は、２ＴＷｈを超え、これはイタリアの総エネルギー需要のほぼ１％である。したがって、光ネットワークのエネルギー消費を低減する方法を見つけることが重要である。
【０００３】
光ネットワークは、完全に計画されて一度に構築されるのではなく、新たなリンクを追加して容量を増大させることによって拡大する傾向があり、混乱を最小限にするために、現在のリンクへの変更は最小にされる。光トランスポートネットワーク（ＯＴＮ）において、より小さな光データユニット（ＯＤＵ）と比べてはるかに低いエネルギーを用いて、より大きなＯＤＵをトランスポートしスイッチングすることができることが知られている。したがって、大量のトラフィックを有する光リンクは、より小量のトラフィックを有するリンクよりもビット当たりに消費するエネルギーが小さい。これは、元の設計が最適に近いエネルギー消費を有していた場合であっても、経時的に、光ネットワークのエネルギー効率が最適から離れていくことを意味する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
リンクが追加または除去されるとともに、ネットワークトポロジを部分的にまたは全体的に変更することによって、ネットワークのエネルギー消費を低減することが可能である。しかしながら、これは、ネットワーク機器の変更をともなうのでコストが高く、また、ネットワーク動作がインタラプトされるので混乱が生じる（ｄｉｓｒｕｐｔｉｖｅ）。ほとんどの場合、エネルギー消費に対し最も大きな影響を有するリンクのみを変更することによってトラフィックにおける混乱を最小限にすることが重要である。トラフィック再分配の量を最小にしてネットワークエネルギー消費を低減する方法を教示する。
【課題を解決するための手段】
【０００５】
この発明の実施の形態は、光ネットワークの全体エネルギー消費を改善するために、光ネットワークを再最適化する方法を提供する。この発明の実施の形態は、ネットワーク内のリンク上の大きなトラフィック束を優先して選ぶ（ｆａｖｏｒ）ことによって、わずかな数の変更のみでエネルギー効率の良好な改善を提供する、ネットワークに対する変更を確定する。
【発明の効果】
【０００６】
このようにして、エネルギー効率は、現在のトラフィックに対する混乱を最小にして大幅に改善することができる。
【図面の簡単な説明】
【０００７】
【図１】データレートの関数としてのエネルギーおよびエネルギーの導関数のグラフである。
【図２】トラフィック需要の例を有する１５個のノード間のネットワーク接続のグラフの概略図である。
【図３】図２のネットワークにおけるエッジ需要の例の概略図である。
【図４】この発明の実施の形態によるネットワークのエネルギー効率を再最適化する方法の流れ図である。
【図５】この方法の第１のステップ後のネットワークグラフの概略図である。
【図６】この方法の第２のステップ後のネットワークグラフの概略図である。
【図７】この方法の第３のステップ後のネットワークグラフの概略図である。
【図８】この方法が完了した後のネットワークグラフの概略図である。
【発明を実施するための形態】
【０００８】
実施の形態１．
概して、ネットワークのエネルギー消費は、スイッチング機能およびルーティング機能が大半を占める。ＯＤＵクロスコネクト（ＸＣ）は、レイヤ３（Ｌ３）ルータ、イーサネットスイッチ、またはＳＯＮＥＴ／ＳＤＨ ＸＣと比較して、ビット当たり低減したエネルギー消費を有する。加えて、より大きなＯＤＵサイズは、より小さなＯＤＵサイズよりも、スイッチングおよびトランスポートに必要とするエネルギーが少ない。ＯＤＵサイズは連続的に調整可能ではなく、現在規定されているサイズは、１．２５Ｇｂｐｓ（ＯＤＵ０）、２．５Ｇｂｐｓ（ＯＤＵ１）、１０Ｇｂｐｓ（ＯＤＵ２）、４０Ｇｂｐｓ（ＯＤＵ３）、および１００Ｇｂｐｓ（ＯＤＵ４）である。しかしながら、この方法の説明のために、データレートＲの関数としてのエネルギー消費ＥＳが、図１に示すように、勾配が減少していく連続した凹関数であると仮定する。特に、提示される値について、ＥＳ（Ｒ）＝２＊ｓｑｒｔ（Ｒ）を仮定する。すべてのリンクが最大容量を有することに留意されたい。
【０００９】
ＥＳは勾配が減少していく凹関数であるので、限界エネルギー消費（ｍａｒｇｉｎａｌ ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ）Ｅ’Ｓ（ここで、シンボルＥ’Ｓは、ＥＳの導関数を表す）は、連続減少関数（ｃｏｎｔｉｎｕｏｕｓｌｙ ｒｅｄｕｃｉｎｇ ｆｕｎｃｔｉｏｎ）となる。このため、提示される値について、Ｅ’Ｓ（Ｒ）＝１／ｓｑｒｔ（Ｒ）を仮定する。
【００１０】
次に、図２に示す、１，２，・・・１５をラベル付けされた１５個のノードと、ノード間を接続する線によって表される光リンクとを含むネットワーク例を検討する。ノードは、光ネットワーク要素、たとえばルータ、スイッチ、およびクロスコネクト（ｃｒｏｓｓ−ｃｏｎｎｅｃｔ）を表す。概して、ネットワークのエネルギー消費は、スイッチング機能およびルーティング機能が大半を占める。ＯＤＵクロスコネクト（ＸＣ）は、レイヤ３（Ｌ３）ルータ、イーサネットスイッチ、またはＳＯＮＥＴ／ＳＤＨ ＸＣと比較して、ビット当たり低減したエネルギー消費を有する。加えて、より大きなＯＤＵサイズは、より小さなＯＤＵサイズよりも、スイッチングおよびトランスポートに必要とするエネルギーが少ない。２つの隣接ノード間の光リンクは「エッジ」と呼ばれる。「パス」を、２つのノードをリンクする一連の接続されたエッジとして定義する。ソースノードｉと所与の宛先ノードｊとの間のトラフィック需要は「需要」と呼ばれ、Ｄ（ｉ，ｊ）によって表される。
【００１１】
エネルギー低減方法を説明するために、１４個の宛先ノードｊ、２，・・・１５を有する単一のソースノードｉ＝１を有する図２のネットワークを仮定する。需要Ｄ（１，ｊ）は、ノードの隣の値によって与えられる。たとえば、需要Ｄ（１，２）は、２２のトラフィックユニットに等しく、Ｄ（１，３）は、１２のトラフィックユニットに等しく、Ｄ（１，４）は、８のトラフィックユニットに等しい。
【００１２】
一般的な場合、２つのノードをリンクする２つ以上のパスが存在する場合があり、このため、需要は各パスにわたって共有される（ｉｓ ｓｈａｒｅｄ）。ノードｉとノードｊとの間で定義されるＭ個のパスが存在する場合、パスｋ（ここで、ｋ＝１，・・・，Ｍ）に対するトラフィック需要は「パス需要」と呼ばれ、ＰＤ（ｉ，ｊ，ｋ）によって表される。需要はパス需要の和に等しく、すなわち、以下であることに留意されたい。
【００１３】
【数１】
【００１４】
多くのソースノードおよび宛先ノードが存在するので、所与のエッジは、複数の異なるパスと関連付けられたトラフィックを有する。エッジにおけるトラフィック需要は「エッジ需要」と呼ばれる。
【００１５】
以下で例として説明するように、任意の特定のリンク（ｉ，ｊ）におけるエッジ需要は、すべてのソースと宛先との間の総需要と、エッジ（ｉ，ｊ）を含むソース間のパス数との関数である。需要の任意の部分を搬送する各エッジの容量は、最初に、基本制約が満たされるように、すなわちすべての需要が満たされ、エッジが該エッジの容量を超えた需要を割り当てられないように、割り当てる（ｂｅ ａｌｌｏｃａｔｅｄ）ことができる。このため、需要は複数の方法で割り当てることができる。エッジ需要を図３に示すように仮定し、初期エッジ需要割当てに対し、エネルギー消費を下げる新たな割当てをどのように見つけることができるかを説明する。
【００１６】
ほとんどのノードの場合、ノードｊからノード１へ到達し需要を満たす、ネットワークを通じた複数の可能なパスが存在する。たとえば、ノード１１から、（他の選択肢の中でも）ノード１１⇔８⇔６⇔５⇔４⇔２⇔１を用いた、ノード１への１つの可能なパスが存在する。ここで、「⇔」はエッジを示す。エッジは一方向とすることもできるし、各方向に異なるエッジ需要を有して双方向とすることもできるし、各方向に等しいエッジ需要を有して双方向とすることもできることに留意されたい。簡単にするために、等しいエッジ需要を有する双方向エッジが示されている。
【００１７】
図３において、説明の目的のために、ノード１からノードＮ（Ｎ＝２，３，・・・，１５）への需要が、１⇔７および１⇔５を除いて、１つのパスのみによってサポートされていると仮定する。１⇔７および１⇔５の需要はそれぞれ３つのパス間で分割されている。需要は以下のパスにわたって分割される。すなわち、１⇔７需要は、パス需要１を有するパス１⇔３⇔７と、パス需要２を有するパス１⇔２⇔４⇔５⇔７と、パス需要２を有するパス１⇔８⇔６⇔５⇔７とに分割され（合計５であり、これが１⇔７需要となる）、１⇔５需要は、パス需要７を有するパス１⇔３⇔７⇔５と、パス需要１２を有するパス１⇔２⇔４⇔５と、パス需要４を有するパス１⇔８⇔６⇔５とに分割される（合計２３であり、これが１⇔５需要となる）。上記で提供した仮定を用いるネットワークによって消費される総エネルギーは、２√（エッジ需要）によって与えられるすべてのエッジエネルギーの和である。この場合、消費される総エネルギーは、１６３．２のエネルギーユニットである。
【００１８】
図４は、この発明の実施の形態による、各ステップにおいてすべての需要を満たしながら、光ネットワークにおけるエネルギー効率を改善するための方法を示している。この方法のステップ、および本明細書に記載される任意の他のプロセスは、当該技術分野において既知のメモリおよび入出力インタフェースに接続されたプロセッサにおいて実行することができる。
【００１９】
第１に、ネットワークを表すグラフを構築する（４１０）。ネットワークは、エッジによって接続されたノードを含む。エッジは、ノード間のトラフィック需要と関連付けられる（ａｒｅ ａｓｓｏｃｉａｔｅｄ ｗｉｔｈ）。
【００２０】
グラフを用いてネットワークにけるブリッジエッジを特定し排除する（４２０）。ここで、「ブリッジエッジ」は、除去された場合、結果として接続されていないネットワークとなるエッジである。これは既知の手順を用いて実行することができる。
【００２１】
次に、残りのエッジのうちのいずれが最も高い限界エネルギー（最も低い需要）を有するかを特定し、除去する（４３０）。このエッジはネットワークから除去され、この最も低い需要は、以下の条件、すなわち必要とされる需要をサポートし、かつ変更されたネットワークにおいていかなる所与のエッジの容量も超えない、を満たす最も低い限界エネルギーを有するエッジに加えられる（４４０）。２つ以上のエッジが同じ最も低い限界エネルギーを有する場合、１つが任意に選択される。
【００２２】
次に、ネットワーク内のすべての残りのエッジがブリッジエッジであるか否かを知るために検査し（４５０）、ｙｅｓである場合、終了する（４５５）。ｎｏである場合、許容される最大反復数を超えたか否かを検査し（４６０）、ｙｅｓである場合、終了する（４６５）。そうでない場合、ステップ４２０において開始を繰り返す。
【００２３】
図５は、ステップ４２０および４３０におけるネットワークグラフを示している。ステップ４２０において求められたブリッジエッジが破線によって示されている。ステップ４３０において最も高い限界エネルギー（最も低い需要）を有するとして特定されたエッジは、５⇔６（５１０）である。
【００２４】
図６は、ステップ４３０および４４０におけるネットワークグラフを示している。５⇔６エッジはネットワークから除去され、ノード５を用いるパスをサポートする最も低い限界エネルギーエッジは５⇔４エッジであるので、除去されたエッジ需要（６）がエッジ５⇔４、４⇔２、２⇔１に加えられる。エッジ需要（６）はまた、６⇔８エッジおよび８⇔１エッジから除去される。なぜなら、もはやこれらのノードを用いるパスをサポートする必要がないためである。すべてのエッジがブリッジエッジではないので、この方法は継続する。次の反復において、除去されることになるエッジ６１０は３⇔７である。
【００２５】
図７は、第２の反復のステップ４２０および４３０の後のネットワークグラフを示している。エッジ７１０および７２０は、ブリッジエッジとして特定され、検討から外されている。３⇔７エッジも除去され、該エッジの需要は上述したように他のエッジに加えられている。この段階において、すべてのエッジがブリッジエッジであり、このため、この方法は終了する。
【００２６】
図８は、この方法が完了した後のネットワークグラフを示している。新たなネットワークについて、上述したように総エネルギーが計算され、１５４．２であると分かり、この例では（１６３．２−１５４．２）／１６３．２＝５．５％の節減である。
【００２７】
複数のソースで複数の宛先の場合、アルゴリズムは単一ソースの場合と類似している。上述したようにエッジ需要が求められるが、ルートノードからの需要、すなわち提示された例ではＤ（１，ｊ）のみでなく、Ｎ個のノード間のすべての需要Ｄ（ｉ，ｊ）を検討する。ブリッジエッジが除去され、説明した２つの条件をサポートする最も高い限界エネルギーを有するエッジが見つけられる。次にこのエッジは除去され、該エッジのエッジ要求が、このエッジによってサポートされているパスのそれぞれについて、他のエッジに再分配される。この手順は、最大反復数に達するか、またはブリッジエッジがこれ以上なくなるまで、上述したように継続する。
【００２８】
他のプロトコルへの拡張
上記の説明は、ＯＴＮのみを扱ったが、同じアルゴリズムを、ＯＴＮによってトランスポートされるプロトコルを含む他のプロトコルに適用することができることに留意することが重要である。例として、ＭＰＬＳ（マルチプロトコルラベルスイッチング）におけるラベルスイッチパス（ＬＳＰ）を検討する。ＬＳＰはＯＴＮが保有することができ、本質的に準静的とすることができる。したがって、ＬＳＰは再最適化することができ、それによって、ＬＳＰはより高いレートのＯＤＵによって保有され、このため、より低いレートのＯＤＵを解放し、エネルギー効率を改善する。これは説明したのと同じアルゴリズムを用いる。
【技術分野】
【０００１】
この発明は、包括的には光ネットワークに関し、より詳細には、光ネットワークにおけるリンクをエネルギー効率のよい方式で再最適化することに関する。
【背景技術】
【０００２】
光ネットワークは、インタネットの規模の増大を受け、高速に拡大を続けている。光ネットワークの拡大とともに、光ネットワークのエネルギー消費が増大し、それによって、データネットワークのエネルギー消費を合わせると、一国の総エネルギー消費のかなりの割合となっている。たとえば、２００５年のＴｅｌｅｃｏｍ Ｉｔａｌｉａ社のネットワークの消費は、２ＴＷｈを超え、これはイタリアの総エネルギー需要のほぼ１％である。したがって、光ネットワークのエネルギー消費を低減する方法を見つけることが重要である。
【０００３】
光ネットワークは、完全に計画されて一度に構築されるのではなく、新たなリンクを追加して容量を増大させることによって拡大する傾向があり、混乱を最小限にするために、現在のリンクへの変更は最小にされる。光トランスポートネットワーク（ＯＴＮ）において、より小さな光データユニット（ＯＤＵ）と比べてはるかに低いエネルギーを用いて、より大きなＯＤＵをトランスポートしスイッチングすることができることが知られている。したがって、大量のトラフィックを有する光リンクは、より小量のトラフィックを有するリンクよりもビット当たりに消費するエネルギーが小さい。これは、元の設計が最適に近いエネルギー消費を有していた場合であっても、経時的に、光ネットワークのエネルギー効率が最適から離れていくことを意味する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
リンクが追加または除去されるとともに、ネットワークトポロジを部分的にまたは全体的に変更することによって、ネットワークのエネルギー消費を低減することが可能である。しかしながら、これは、ネットワーク機器の変更をともなうのでコストが高く、また、ネットワーク動作がインタラプトされるので混乱が生じる（ｄｉｓｒｕｐｔｉｖｅ）。ほとんどの場合、エネルギー消費に対し最も大きな影響を有するリンクのみを変更することによってトラフィックにおける混乱を最小限にすることが重要である。トラフィック再分配の量を最小にしてネットワークエネルギー消費を低減する方法を教示する。
【課題を解決するための手段】
【０００５】
この発明の実施の形態は、光ネットワークの全体エネルギー消費を改善するために、光ネットワークを再最適化する方法を提供する。この発明の実施の形態は、ネットワーク内のリンク上の大きなトラフィック束を優先して選ぶ（ｆａｖｏｒ）ことによって、わずかな数の変更のみでエネルギー効率の良好な改善を提供する、ネットワークに対する変更を確定する。
【発明の効果】
【０００６】
このようにして、エネルギー効率は、現在のトラフィックに対する混乱を最小にして大幅に改善することができる。
【図面の簡単な説明】
【０００７】
【図１】データレートの関数としてのエネルギーおよびエネルギーの導関数のグラフである。
【図２】トラフィック需要の例を有する１５個のノード間のネットワーク接続のグラフの概略図である。
【図３】図２のネットワークにおけるエッジ需要の例の概略図である。
【図４】この発明の実施の形態によるネットワークのエネルギー効率を再最適化する方法の流れ図である。
【図５】この方法の第１のステップ後のネットワークグラフの概略図である。
【図６】この方法の第２のステップ後のネットワークグラフの概略図である。
【図７】この方法の第３のステップ後のネットワークグラフの概略図である。
【図８】この方法が完了した後のネットワークグラフの概略図である。
【発明を実施するための形態】
【０００８】
実施の形態１．
概して、ネットワークのエネルギー消費は、スイッチング機能およびルーティング機能が大半を占める。ＯＤＵクロスコネクト（ＸＣ）は、レイヤ３（Ｌ３）ルータ、イーサネットスイッチ、またはＳＯＮＥＴ／ＳＤＨ ＸＣと比較して、ビット当たり低減したエネルギー消費を有する。加えて、より大きなＯＤＵサイズは、より小さなＯＤＵサイズよりも、スイッチングおよびトランスポートに必要とするエネルギーが少ない。ＯＤＵサイズは連続的に調整可能ではなく、現在規定されているサイズは、１．２５Ｇｂｐｓ（ＯＤＵ０）、２．５Ｇｂｐｓ（ＯＤＵ１）、１０Ｇｂｐｓ（ＯＤＵ２）、４０Ｇｂｐｓ（ＯＤＵ３）、および１００Ｇｂｐｓ（ＯＤＵ４）である。しかしながら、この方法の説明のために、データレートＲの関数としてのエネルギー消費ＥＳが、図１に示すように、勾配が減少していく連続した凹関数であると仮定する。特に、提示される値について、ＥＳ（Ｒ）＝２＊ｓｑｒｔ（Ｒ）を仮定する。すべてのリンクが最大容量を有することに留意されたい。
【０００９】
ＥＳは勾配が減少していく凹関数であるので、限界エネルギー消費（ｍａｒｇｉｎａｌ ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ）Ｅ’Ｓ（ここで、シンボルＥ’Ｓは、ＥＳの導関数を表す）は、連続減少関数（ｃｏｎｔｉｎｕｏｕｓｌｙ ｒｅｄｕｃｉｎｇ ｆｕｎｃｔｉｏｎ）となる。このため、提示される値について、Ｅ’Ｓ（Ｒ）＝１／ｓｑｒｔ（Ｒ）を仮定する。
【００１０】
次に、図２に示す、１，２，・・・１５をラベル付けされた１５個のノードと、ノード間を接続する線によって表される光リンクとを含むネットワーク例を検討する。ノードは、光ネットワーク要素、たとえばルータ、スイッチ、およびクロスコネクト（ｃｒｏｓｓ−ｃｏｎｎｅｃｔ）を表す。概して、ネットワークのエネルギー消費は、スイッチング機能およびルーティング機能が大半を占める。ＯＤＵクロスコネクト（ＸＣ）は、レイヤ３（Ｌ３）ルータ、イーサネットスイッチ、またはＳＯＮＥＴ／ＳＤＨ ＸＣと比較して、ビット当たり低減したエネルギー消費を有する。加えて、より大きなＯＤＵサイズは、より小さなＯＤＵサイズよりも、スイッチングおよびトランスポートに必要とするエネルギーが少ない。２つの隣接ノード間の光リンクは「エッジ」と呼ばれる。「パス」を、２つのノードをリンクする一連の接続されたエッジとして定義する。ソースノードｉと所与の宛先ノードｊとの間のトラフィック需要は「需要」と呼ばれ、Ｄ（ｉ，ｊ）によって表される。
【００１１】
エネルギー低減方法を説明するために、１４個の宛先ノードｊ、２，・・・１５を有する単一のソースノードｉ＝１を有する図２のネットワークを仮定する。需要Ｄ（１，ｊ）は、ノードの隣の値によって与えられる。たとえば、需要Ｄ（１，２）は、２２のトラフィックユニットに等しく、Ｄ（１，３）は、１２のトラフィックユニットに等しく、Ｄ（１，４）は、８のトラフィックユニットに等しい。
【００１２】
一般的な場合、２つのノードをリンクする２つ以上のパスが存在する場合があり、このため、需要は各パスにわたって共有される（ｉｓ ｓｈａｒｅｄ）。ノードｉとノードｊとの間で定義されるＭ個のパスが存在する場合、パスｋ（ここで、ｋ＝１，・・・，Ｍ）に対するトラフィック需要は「パス需要」と呼ばれ、ＰＤ（ｉ，ｊ，ｋ）によって表される。需要はパス需要の和に等しく、すなわち、以下であることに留意されたい。
【００１３】
【数１】
【００１４】
多くのソースノードおよび宛先ノードが存在するので、所与のエッジは、複数の異なるパスと関連付けられたトラフィックを有する。エッジにおけるトラフィック需要は「エッジ需要」と呼ばれる。
【００１５】
以下で例として説明するように、任意の特定のリンク（ｉ，ｊ）におけるエッジ需要は、すべてのソースと宛先との間の総需要と、エッジ（ｉ，ｊ）を含むソース間のパス数との関数である。需要の任意の部分を搬送する各エッジの容量は、最初に、基本制約が満たされるように、すなわちすべての需要が満たされ、エッジが該エッジの容量を超えた需要を割り当てられないように、割り当てる（ｂｅ ａｌｌｏｃａｔｅｄ）ことができる。このため、需要は複数の方法で割り当てることができる。エッジ需要を図３に示すように仮定し、初期エッジ需要割当てに対し、エネルギー消費を下げる新たな割当てをどのように見つけることができるかを説明する。
【００１６】
ほとんどのノードの場合、ノードｊからノード１へ到達し需要を満たす、ネットワークを通じた複数の可能なパスが存在する。たとえば、ノード１１から、（他の選択肢の中でも）ノード１１⇔８⇔６⇔５⇔４⇔２⇔１を用いた、ノード１への１つの可能なパスが存在する。ここで、「⇔」はエッジを示す。エッジは一方向とすることもできるし、各方向に異なるエッジ需要を有して双方向とすることもできるし、各方向に等しいエッジ需要を有して双方向とすることもできることに留意されたい。簡単にするために、等しいエッジ需要を有する双方向エッジが示されている。
【００１７】
図３において、説明の目的のために、ノード１からノードＮ（Ｎ＝２，３，・・・，１５）への需要が、１⇔７および１⇔５を除いて、１つのパスのみによってサポートされていると仮定する。１⇔７および１⇔５の需要はそれぞれ３つのパス間で分割されている。需要は以下のパスにわたって分割される。すなわち、１⇔７需要は、パス需要１を有するパス１⇔３⇔７と、パス需要２を有するパス１⇔２⇔４⇔５⇔７と、パス需要２を有するパス１⇔８⇔６⇔５⇔７とに分割され（合計５であり、これが１⇔７需要となる）、１⇔５需要は、パス需要７を有するパス１⇔３⇔７⇔５と、パス需要１２を有するパス１⇔２⇔４⇔５と、パス需要４を有するパス１⇔８⇔６⇔５とに分割される（合計２３であり、これが１⇔５需要となる）。上記で提供した仮定を用いるネットワークによって消費される総エネルギーは、２√（エッジ需要）によって与えられるすべてのエッジエネルギーの和である。この場合、消費される総エネルギーは、１６３．２のエネルギーユニットである。
【００１８】
図４は、この発明の実施の形態による、各ステップにおいてすべての需要を満たしながら、光ネットワークにおけるエネルギー効率を改善するための方法を示している。この方法のステップ、および本明細書に記載される任意の他のプロセスは、当該技術分野において既知のメモリおよび入出力インタフェースに接続されたプロセッサにおいて実行することができる。
【００１９】
第１に、ネットワークを表すグラフを構築する（４１０）。ネットワークは、エッジによって接続されたノードを含む。エッジは、ノード間のトラフィック需要と関連付けられる（ａｒｅ ａｓｓｏｃｉａｔｅｄ ｗｉｔｈ）。
【００２０】
グラフを用いてネットワークにけるブリッジエッジを特定し排除する（４２０）。ここで、「ブリッジエッジ」は、除去された場合、結果として接続されていないネットワークとなるエッジである。これは既知の手順を用いて実行することができる。
【００２１】
次に、残りのエッジのうちのいずれが最も高い限界エネルギー（最も低い需要）を有するかを特定し、除去する（４３０）。このエッジはネットワークから除去され、この最も低い需要は、以下の条件、すなわち必要とされる需要をサポートし、かつ変更されたネットワークにおいていかなる所与のエッジの容量も超えない、を満たす最も低い限界エネルギーを有するエッジに加えられる（４４０）。２つ以上のエッジが同じ最も低い限界エネルギーを有する場合、１つが任意に選択される。
【００２２】
次に、ネットワーク内のすべての残りのエッジがブリッジエッジであるか否かを知るために検査し（４５０）、ｙｅｓである場合、終了する（４５５）。ｎｏである場合、許容される最大反復数を超えたか否かを検査し（４６０）、ｙｅｓである場合、終了する（４６５）。そうでない場合、ステップ４２０において開始を繰り返す。
【００２３】
図５は、ステップ４２０および４３０におけるネットワークグラフを示している。ステップ４２０において求められたブリッジエッジが破線によって示されている。ステップ４３０において最も高い限界エネルギー（最も低い需要）を有するとして特定されたエッジは、５⇔６（５１０）である。
【００２４】
図６は、ステップ４３０および４４０におけるネットワークグラフを示している。５⇔６エッジはネットワークから除去され、ノード５を用いるパスをサポートする最も低い限界エネルギーエッジは５⇔４エッジであるので、除去されたエッジ需要（６）がエッジ５⇔４、４⇔２、２⇔１に加えられる。エッジ需要（６）はまた、６⇔８エッジおよび８⇔１エッジから除去される。なぜなら、もはやこれらのノードを用いるパスをサポートする必要がないためである。すべてのエッジがブリッジエッジではないので、この方法は継続する。次の反復において、除去されることになるエッジ６１０は３⇔７である。
【００２５】
図７は、第２の反復のステップ４２０および４３０の後のネットワークグラフを示している。エッジ７１０および７２０は、ブリッジエッジとして特定され、検討から外されている。３⇔７エッジも除去され、該エッジの需要は上述したように他のエッジに加えられている。この段階において、すべてのエッジがブリッジエッジであり、このため、この方法は終了する。
【００２６】
図８は、この方法が完了した後のネットワークグラフを示している。新たなネットワークについて、上述したように総エネルギーが計算され、１５４．２であると分かり、この例では（１６３．２−１５４．２）／１６３．２＝５．５％の節減である。
【００２７】
複数のソースで複数の宛先の場合、アルゴリズムは単一ソースの場合と類似している。上述したようにエッジ需要が求められるが、ルートノードからの需要、すなわち提示された例ではＤ（１，ｊ）のみでなく、Ｎ個のノード間のすべての需要Ｄ（ｉ，ｊ）を検討する。ブリッジエッジが除去され、説明した２つの条件をサポートする最も高い限界エネルギーを有するエッジが見つけられる。次にこのエッジは除去され、該エッジのエッジ要求が、このエッジによってサポートされているパスのそれぞれについて、他のエッジに再分配される。この手順は、最大反復数に達するか、またはブリッジエッジがこれ以上なくなるまで、上述したように継続する。
【００２８】
他のプロトコルへの拡張
上記の説明は、ＯＴＮのみを扱ったが、同じアルゴリズムを、ＯＴＮによってトランスポートされるプロトコルを含む他のプロトコルに適用することができることに留意することが重要である。例として、ＭＰＬＳ（マルチプロトコルラベルスイッチング）におけるラベルスイッチパス（ＬＳＰ）を検討する。ＬＳＰはＯＴＮが保有することができ、本質的に準静的とすることができる。したがって、ＬＳＰは再最適化することができ、それによって、ＬＳＰはより高いレートのＯＤＵによって保有され、このため、より低いレートのＯＤＵを解放し、エネルギー効率を改善する。これは説明したのと同じアルゴリズムを用いる。
【特許請求の範囲】
【請求項１】
複数のソースノードと、複数の宛先ノードとを含む光ネットワークにおいてエネルギー転送効率を改善するための方法であって、
前記ネットワークを、エッジによって接続されたノードのグラフとして表すステップであって、各ノードは光ネットワーク要素を表し、各エッジは２つの光ネットワーク要素を接続するパスを表す、表すステップと、
前記各エッジを需要でラベル付けするステップと、
非ブリッジエッジを特定するステップと、
前記グラフから、最も低い需要を有する前記非ブリッジエッジを除去するステップと、
前記最も低い需要を、最も高い需要を有する前記非ブリッジエッジに加えるステップと、
前記ラベル付けするステップと、前記特定するステップと、前記除去するステップと、前記加えるステップとを、終了条件に達するまで繰り返すステップと、
を含む、複数のソースノードと、複数の宛先ノードとを含む光ネットワークにおいてエネルギー転送効率を改善するための方法。
【請求項２】
前記最も低い需要は最も高い限界エネルギーに対応し、前記最も高い需要は最も低い限界エネルギーに対応する、請求項１に記載の方法。
【請求項３】
前記限界エネルギーはエネルギー消費の導関数である、請求項２に記載の方法。
【請求項４】
前記最も低い需要は、前記非ブリッジエッジの容量を超えない場合にのみ加えられる、請求項１に記載の方法。
【請求項５】
複数のエッジが前記最も高い需要を有し、該複数のエッジのうちの１つに前記最も低い需要が任意で加えられる、請求項１に記載の方法。
【請求項６】
前記終了条件は、すべてのエッジが非ブリッジエッジであることである、請求項１に記載の方法。
【請求項７】
前記終了条件は、最大反復回数である、請求項１に記載の方法。
【請求項１】
複数のソースノードと、複数の宛先ノードとを含む光ネットワークにおいてエネルギー転送効率を改善するための方法であって、
前記ネットワークを、エッジによって接続されたノードのグラフとして表すステップであって、各ノードは光ネットワーク要素を表し、各エッジは２つの光ネットワーク要素を接続するパスを表す、表すステップと、
前記各エッジを需要でラベル付けするステップと、
非ブリッジエッジを特定するステップと、
前記グラフから、最も低い需要を有する前記非ブリッジエッジを除去するステップと、
前記最も低い需要を、最も高い需要を有する前記非ブリッジエッジに加えるステップと、
前記ラベル付けするステップと、前記特定するステップと、前記除去するステップと、前記加えるステップとを、終了条件に達するまで繰り返すステップと、
を含む、複数のソースノードと、複数の宛先ノードとを含む光ネットワークにおいてエネルギー転送効率を改善するための方法。
【請求項２】
前記最も低い需要は最も高い限界エネルギーに対応し、前記最も高い需要は最も低い限界エネルギーに対応する、請求項１に記載の方法。
【請求項３】
前記限界エネルギーはエネルギー消費の導関数である、請求項２に記載の方法。
【請求項４】
前記最も低い需要は、前記非ブリッジエッジの容量を超えない場合にのみ加えられる、請求項１に記載の方法。
【請求項５】
複数のエッジが前記最も高い需要を有し、該複数のエッジのうちの１つに前記最も低い需要が任意で加えられる、請求項１に記載の方法。
【請求項６】
前記終了条件は、すべてのエッジが非ブリッジエッジであることである、請求項１に記載の方法。
【請求項７】
前記終了条件は、最大反復回数である、請求項１に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−４６４１４（Ｐ２０１３−４６４１４Ａ）
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１５１５５１（Ｐ２０１２−１５１５５１）
【出願日】平成２４年７月５日（２０１２．７．５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願番号】特願２０１２−１５１５５１（Ｐ２０１２−１５１５５１）
【出願日】平成２４年７月５日（２０１２．７．５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]