デマンド収容設計方法及びデマンド収容設計システム
【課題】デマンド収容設計システムにおいて、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することを目的とする。
【解決手段】光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、を有する。
【解決手段】光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、を有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、デマンド収容設計方法及びデマンド収容設計システムに関する。
【背景技術】
【0002】
近年、インターネットトラヒックの爆発的増大に対応可能である波長多重伝送(WDM)方式を前提とし、SDH(Synchronous Optical Network)又はSONET(Synchronous Digital Hierarchy)等の同期網のみならずIP(Internet Protocol)又はイーサネット(登録商標)系の非同期網のクライアント信号を、エンド・エンドで通信をする際に、上位レイヤーが下位レイヤーを一切意識しなくて済む、所謂トランスペアレントに伝送するプラットフォームとして、OTN(Optical Transport Network:光転送ネットワーク)がITU−Tにおいて勧告化されている。そのインタフェースやフレームフォーマットはITU−Tの勧告G.709により標準化されており、商用システムへの導入が急速に進んでいる。今後は、OTNクロスコネクト(XC:Cross−connect)装置を用いてOTN信号パスを柔軟に運用する光ネットワークの構築手法が重要となる。
【0003】
図1(A),(B)を用いてデマンドの光パスへの収容について説明する。なお、クライアント信号を収容する低速の信号転送用フレームであるODU(Optical channel Data Unit)フレームをLower Order ODU(LOODU)と呼び、この低速のODUフレームを複数多重収容するODUフレームをHigher Order ODU(HOODU)と呼ぶ。OTNにおいては、始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを発行することで、クライアント信号を収容したLOODUを光パスであるHOODUに収容する。
【0004】
図1(A)において、例えばデマンドD1はノード1,2,3の経路(始点ノードはノード1、終点ノードはノード3)の光パスを指定している。また、デマンドD2はノード4,3,5,6の経路の光パスを指定している。
【0005】
光パスはHOODUにより実現される。図1(B)において、例えばノード4,3間及びノード3,5の間にはHOODUの光パスP1が設定され、また、ノード5,6間には光パスP2が設定されている。上記のノード4,3,5,6の経路を指定するデマンドD2は光パスP1,P2によって実現される。
【0006】
ところで、数理計画法による光ネットワーク内のパス設計で「解空間の絞込み」という考えを導入し、経路設計における計算時間の増加を押さえることが提案されている(例えば特許文献1,2参照)。
【0007】
また、確率的デマンドパターンに対しリンク及びノードに関するコストを数理計画法に基づき最小化設計を行うことが提案されている(例えば特許文献3参照)。
【先行技術文献】
【特許文献】
【0008】
【特許文献1】特開2007−311900号公報
【特許文献2】特開2004−80666号公報
【特許文献3】特開平11−215124号公報
【発明の概要】
【発明が解決しようとする課題】
【0009】
デマンドを光パスに収容する設計には、アグリゲーションとグルーミングがある。アグリゲーションは、図2(A)に示すように、始点と終点及び経路が同一のデマンド同士を集約して1つの光パスであるHOODUに収容する設計である。図2(A)において、丸印がノードを表し、両端が矢頭の線分がデマンドを表し、複数のデマンドを包含する実線でHOODUを表している。例えばノードN1,N2,N3の経路を指定したデマンドD3,D4はHOODU11に収容されている。
いる。
【0010】
グルーミングは、図2(B)に示すように、ノードN1,N2間にHOODU12を設定し、ノードN1,N2間を経路に含む複数のデマンド(図では全てのデマンド)をHOODU12に収容する。同様に、ノードN2,N3間を経路に含む複数のデマンドをHOODU13に収容し、ノードN2,N4間を経路に含む複数のデマンドをHOODU14に収容している。
【0011】
アグリゲーションとグルーミングを用いれば、ノードN1〜N4間でデマンドを収容する方法は、図3(A)〜(D)に示すように各種の収容形態がある。なお、図3(A),(B)は図2(A),(B)と同一である。図3(C)ではノードN2,N3間にHOODU15,16,17を設けており、図3(D)ではノードN2,N3間にHOODU18,19を設けている。
【0012】
複数のデマンドが与えられた場合に、アグリゲーションとグルーミングを用いた図3(A)〜(D)に示すような各種の収容形態から、どの収容形態を選択すれば最もコストが小さく効率が良くなるかを設計することは、従来行われていなかった。
【0013】
開示のデマンド収容設計システムは、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することを目的とする。
【課題を解決するための手段】
【0014】
開示の一実施形態によるデマンド収容設計システムは、光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、を有する。
【発明の効果】
【0015】
本実施形態によれば、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することができる。
【図面の簡単な説明】
【0016】
【図1】デマンドの光パスへの収容について説明するための図である。
【図2】アグリゲーションとグルーミングを説明するための図である。
【図3】デマンドの収容形態を示す図である。
【図4】デマンド収容設計システムの一実施形態のハードウェア構成図である。
【図5】デマンド収容設計処理の一実施形態のフローチャートである。
【図6】HOODUルート候補とデマンドHOODUルートパターン候補を説明するための図である。
【図7】ステップS15,S16の解析結果を説明するための図である。
【図8】HOODUルート候補の抽出を説明するための図である。
【図9】混合整数計画モデルで使用する変数の一覧を示す図である。
【図10】ビンパッキングモデルで使用する変数の一覧を示す図である。
【図11】ヒューイスティック手法と本実施形態の手法を比較した結果を示す図である。
【図12】比較のために使用した光ネットワークの構成を示す図である。
【発明を実施するための形態】
【0017】
以下、図面に基づいて実施形態を説明する。
【0018】
<デマンド収容設計システムの構成>
図4はデマンド収容設計システムの一実施形態のハードウェア構成図を示す。図4において、デマンド収容設計システムは、入力装置21と、出力装置22と、ドライブ装置23と、補助記憶装置24と、メモリ装置25と、演算処理装置26と、データベース27を有しており、これらはシステムバス28で相互に接続されている。このデマンド収容設計システムは、専用の装置構成とすることもできるが、例えば、汎用のパーソナルコンピュータやワークステーション等を適用することが可能である。
【0019】
入力装置21は使用者が操作するキーボード及びマウス等を有しており、各種データを入力する。出力装置22はデマンド収容設計システムのプログラムを操作するのに必要な各種ウィンドウやデータ等を表示するディスプレイを有し、実行プログラムに基づいて表示される。実行プログラムは、例えばCD−ROM等の記録媒体29により提供される。プログラムを記緑した記録媒体29はドライブ装置23に装着され、記憶媒体29に格納された実行プログラムが記録媒体29からドライブ装置23を介してメモリ装置25にインストールされる。
【0020】
演算処理装置26はメモリ装置25から読み出された実行プログラムに基づいて、各種演算や後述する各処理を含むデマンド収容設計システム全体の処理を制御する。また、プログラムの実行中に必要な各種情報は、データベース27から取得することができ、また格納することもできる。
【0021】
<デマンド収容設計処理の一実施形態のフローチャート>
図5はデマンド収容設計処理の一実施形態のフローチャートを示す。図5において、ステップS11で光ネットワークのネットワーク基本情報であるネットワークトポロジを取得する。また、ステップS12で上記光ネットワークに対する全てのデマンドそれぞれの経路情報を取得する。各デマンドはクライアント信号を収容したLOODU単位で、始点ノードから経由する各ノードを含め終点ノードまでの経路を含んでいる。なお、各LOODU(例えばODU1,ODU2等)の帯域は決まっている。
【0022】
次に、ステップS13,S14で前準備処理を実行する。ステップS13で各デマンドにおいて使用可能性のある光パス候補としてのHOODUルート候補を抽出する。なお、デマンドが取得されていない経路についてはHOODUルート候補を抽出することはない。
【0023】
ここで、図6(A)に示すように始点ノード31から4つのノード32,33,34,35を経由して終点ノード36に至るデマンドについて考える。この場合、図6(A)に示すように、ノード31,33間を結ぶ光パス候補としてのHOODUルート候補1、ノード33,34間を結ぶHOODUルート候補2、ノード34,36間を結ぶHOODUルート候補3がある。この他にも、ノード33,35間を結ぶHOODUルート候補4がある。また、ノード31,32間を結ぶHOODUルート候補6、ノード32,35間を結ぶHOODUルート候補7、ノード35,36間を結ぶHOODUルート候補5がある。また、ノード31,36間を結ぶHOODUルート候補8があり、ノード31,34間を結ぶHOODUルート候補9がある。
【0024】
更に、ステップS14で各デマンドにおいて光パス候補を組み合わせてデマンドの始点ノードと終点ノードを結ぶ光パスパターン候補としてのデマンドHOODUルートパターン候補を抽出する。なお、デマンドが取得されていない経路についてはデマンドHOODUルートパターン候補を抽出することはない。
【0025】
図6(A)に示すデマンドとHOODUルート候補に対しては、図6(B)に示すように、HOODUルート候補1,HOODUルート候補2,HOODUルート候補3で構成されるデマンドHOODUルートパターン候補1がある。この他にも、HOODUルート候補1,HOODUルート候補4,HOODUルート候補5で構成されるデマンドHOODUルートパターン候補2があり、HOODUルート候補6,HOODUルート候補7,HOODUルート候補5で構成されるデマンドHOODUルートパターン候補3がある。更に、HOODUルート候補8で構成されるデマンドHOODUルートパターン候補4があり、HOODUルート候補9,HOODUルート候補3で構成されるデマンドHOODUルートパターン候補5がある。
【0026】
次に、ステップS15で主問題(Main Problem)である混合整数計画モデルを生成し、この主問題を解析する。ここでは、目的関数と制約条件を設定した混合整数計画モデルを用い数理計画法にて解析を行う。目的関数は、帯域別に生成されるHOODUの全体のコストが最小となることである。この場合の制約条件は第1に各デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数であることである。制約条件の第2は各HOODUルート候補において、このHOODUルート候補を通るデマンドHOODUルートパターン候補の帯域の総量が、帯域別に割当てられているHOODUの個数とHOODUの帯域との積和以下であることである。制約条件の第3は各リンクにおいて、HOODUの数が波長数制限値以下であることである。
【0027】
ステップS15の解析で得られる情報は、各HOODUルート候補について、各HOODU帯域(例えば10Gbps,100Gbps)のそれぞれに必要とされるHOODUの本数と、各HOODUルート候補に格納されるデマンドの数である。
【0028】
これにより、例えば図7の上部に示すように、ノード31,33間を結ぶHOODUルート候補1について、帯域100GbpsのHOODUが2本と、帯域10GbpsのHOODUが5本とが必要とされ、この合計7本のHOODUにより帯域BW8のデマンド#1と帯域BW2のデマンド#2と帯域BW1のデマンド#3〜#60を収容することが決定される。なお、帯域BW1はLOODU0の1トリビュータリスロット当たりの帯域(例えば1.25Gbps)を表しており、帯域BW2はLOODU1のトリビュータリスロット数が2で帯域2.5Gbpsを表し、帯域BW8はLOODU2のトリビュータリスロット数が8で帯域10Gbpsを表し、帯域BW80はLOODU4のトリビュータリスロット数が80で帯域80Gbpsを表している。
【0029】
次に、ステップS16でどのHOODUにどのデマンドを割当てて収容するかを具体的に決定する。ステップS16ではビンパッキングモデルを用いた数理計画法にて解析を行う。ビンビンパッキング問題は、各HOODUルート候補について、ステップS15で算出された主問題の解析結果を基に実行する。図7に示す例では、ステップS15において、帯域100GbpsのHOODUが2本と、帯域10GbpsのHOODUが5本とを用いて、帯域BW8のデマンド#1と帯域BW2のデマンド#2と帯域BW1のデマンド#3〜#60を収容することが決定されている。
【0030】
この場合、ステップS16の実行により、図7の下部に示すように、例えば1番目の帯域100GbpsのHOODUにデマンド#1,#8,…,#55を収容し、2番目の帯域100GbpsのHOODUにデマンド#2,#6,…,#60を収容する。そして、1番目の帯域10GbpsのHOODUにデマンド#7を収容し、2番目の帯域10GbpsのHOODUにデマンド#11,#18を収容し、3番目の帯域10GbpsのHOODUにデマンド#5,#23を収容し、4番目の帯域10GbpsのHOODUにデマンド#19,#38を収容し、5番目の帯域10GbpsのHOODUにデマンド#32,#36を収容することが決定される。
【0031】
こののち、ステップS17で各デマンドを収容した各HOODUの波長割当と使用する送受信カードを決定するなどの阿路処理を行って設計を終了する。
【0032】
<HOODUルート候補抽出処理>
ステップS13で実行するHOODUルート候補抽出処理について詳しく説明する。本実施形態では光ネットワークを構成するノードの中で、3本以上のリンクを有するノードをハブサイトと呼ぶ。なお、リンクは隣接するノードを連結する光伝送路であり、スパンとも呼ぶ。
【0033】
デマンドが図8(A)に示す始点ノード(src)41、終点ノード(dst)49で、ノード41,42,43,44,45,46,47,48,49の経路を持ち、このうち、ノード42,44,46,48がハブサイト(hub)であるとする。
【0034】
まず第1に、図8(A)に示すように、始点ノード41と終点ノード49を直結するルートをHOODUルート候補50aとして抽出する。
【0035】
第2に、図8(B)に示すように、デマンド経路内の始点ノード41又は終点ノード49とハブサイト間、及びハブサイト間を連結するルートをHOODUルート候補50b,50c,50d、50e,50fとして抽出する。
【0036】
第3に、図8(C)に示すように、始点ノード41と終点ノード49それぞれに最も近いハブサイト42,48間を連結するルートをHOODUルート候補50gとして抽出する。
【0037】
上記が代表的なHOODUルート候補の抽出方法であるが、これ以外にも以下の第4から第6の抽出を行っても良い。
【0038】
第4に、隣接サイト間を連結するルートをHOODUルート候補として抽出する。
【0039】
第5に、デマンド経路内のハブサイトを任意に2つ選択し、選択した2つのハブサイトを連結するルートをHOODUルート候補として抽出する。
【0040】
第6に、上記の第1〜第5の方法それぞれで抽出したHOODUルート候補のうち、HOODUルート候補内でのホップ数又はHOODUルート候補を構成するノード数を予め定められた上限値及び/又は下限値と比較し、上限値以上又は以下、下限値以上又は以下、等の条件を満たすものだけをHOODUルート候補として再び抽出する。
【0041】
<デマンドHOODUルートパターン候補抽出処理>
ステップS14で実行するデマンドHOODUルートパターン候補抽出処理について詳しく説明する。基本的に、デマンドHOODUルートパターン候補は抽出されたHOODUルート候補から各デマンドにおいて抽出可能なデマンドHOODUルートパターン候補を全て列挙するという方法を用いる。つまり、デマンドから抽出されたHOODUルート候補そのもの又は抽出されたHOODUルート候補を組み合わせて、デマンドの始点ノードから終点ノードを結ぶパターンをデマンドHOODUルートパターン候補として抽出する。
【0042】
例えば図6(A)に示すデマンドとHOODUルート候補については、図6(B)に示すデマンドHOODUルートパターン候補1〜デマンドHOODUルートパターン候補5を抽出する。
【0043】
ただし、場合によっては、各デマンドにおけるHOODUの乗換回数を一定回数以下に制限する、という制約を設けても良い。図6(A)に示すデマンドとHOODUルート候補について、HOODUの乗換回数を1回以内に抑えるという制約条件を付加した場合には、図6(B)に示すデマンドHOODUルートパターン候補1〜デマンドHOODUルートパターン候補5のうち、制約条件に該当するデマンドHOODUルートパターン候補4、及びデマンドHOODUルートパターン候補5のみを抽出する。なお、制約条件の付加方法については、これに限るものではない。
【0044】
<主問題作成及び解析処理>
ステップS15で実行する主問題作成及び解析処理について詳しく説明する。なお、以下の具体例においては、HOODUの帯域として10Gbps、100Gbpsの2種類が設定可能である場合を想定する。また、混合整数計画モデルで使用する変数の一覧を図9に示す。
【0045】
図9において、tはデマンドHOODUルートパターン候補の番号、hはHOODUルート候補の番号、sは光ネットワーク内のリンク(又はスパン)の番号、lはデマンドの番号である。d(t)はデマンドHOODUルートパターン候補tをいくつ採用するかの変数、xh10(h)はHOODUルート候補hにおける10GbpsのHOODUの使用個数、xh100(h)はHOODUルート候補hにおける100GbpsのHOODUの使用個数である。
【0046】
Demand_Cap(t)はデマンドHOODUルートパターン候補tの1本当たりの帯域、I(h,t)はデマンドHOODUルートパターン候補tにHOODUルート候補hが含まれるか否かの識別子(値1は含む、値0は含まない)、T(l,t)はデマンドHOODUルートパターン候補tがデマンドlに属するか否かの識別子(値1は属する、値0は属さない)である。
【0047】
Total Demand Numはデマンドの合計本数、Wavelength Limit(s)はリンクsにおける波長数の上限値、Link(s,h)はHOODUルート候補hにリンクsを含むか否かの識別子(値1は含む、値0は含まない)である。また、xh10(h)の係数となる「8」は10GbpsのHOODUのトリビュータリスロット数つまり8×1.25Gbpsの帯域を表し、xh100(h)の係数となる80は100GbpsのHOODUのトリビュータリスロット数つまり80×1.25Gbpsの帯域を表している。
【0048】
この場合、目的関数は(1)式で表される。(1)式で、COSTh10は10GbpsのHOODUを使用するコスト、COSTh100は100GbpsのHOODUを使用するコストである。コストとはHOODUを使用するための費用であり、例えばCOSTh100はCOSTh10の数倍に設定される。また、定数であるCOSTh100,COSTh10は設計を行うときの状況により、どのように設定することも可能である。
【0049】
(1)式は、生成される10GbpsのHOODUと100GbpsのHOODUの全体のコストが最小となることを表している。
【0050】
【数1】
【0051】
制約条件は(2)式、(3)式、(4)式で表される。(2)式は各デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数であることを表す。(3)式は各HOODUルート候補において、このHOODUルート候補を通る(もしくはHOODUルート候補に含まれる)デマンドHOODUルートパターン候補の帯域の総量が、帯域別に割当てられているHOODUの個数とHOODUの帯域との積和以下であることを表す。(4)式は各リンクにおいて、HOODUの数がリンクの波長数制限値以下であることを表す。
【0052】
【数2】
【0053】
なお、上記(1)〜(4)式では、HOODUの帯域として10Gbps、100Gbpsの2種類を設定しているが、HOODUの帯域はこれに限られるものではなく、1種類又は3種類以上であっても良い。
【0054】
<ビンパッキング作成及び解析処理>
ステップS16で実行する割当収容処理について説明する。ここで、簡単な例えとして、100GbpsのHOODUは大きな籠、10GbpsのHOODUは小さな籠、デマンドがリンゴだとした場合、限られた籠の容積の中に、どのようにうまくリンゴを収納するかを決定する。これは単純なビンパッキング問題であるため、これを解くための既存の手法、すなわち、数理計画法を用いても対応可能であるし、既存のヒューリスチックな手法(貪欲法等)で対応することも対応可能である。
【0055】
ビンパッキングにおける目的関数と制約条件を以下に示す。また、ビンパッキングモデルで使用する変数の一覧を図10に示す。図10において、xはデマンドの番号、yはHOODUの番号、s(x,y)はデマンドxがHOODUyに格納されるか否かの識別子(値1は格納される、値0は格納されない)、HOODU(y)はHOODUyが使用されるか否かの識別子(値1は使用される、値0は使用されない)、Demand_Cap(x)はデマンドxの帯域、Demand_Num(x)は現在のHOODUルート候補に割当てられたデマンドxの本数、HOODU_Cap(y)はHOODUyの容量、Mは例えば10000等の十分に大きな数である。
【0056】
この場合、目的関数は(5)式で表される。(5)式は、使用するHOODUの数が最小となることを表している。制約条件は(6)式、(7)式、(8)式で表される。(6)式はデマンドxがいずれかのHOODUyに収容されることを表す。(7)式はHOODUに格納されるデマンドの総帯域がHOODUの容量以下であることを表す。(8)式はどれか1つでもデマンドが収容されるHOODUは、そのHOODUを「使用する」とみなすことを表す。
【0057】
【数3】
【0058】
本実施形態では、デマンド収容設計をデマンド分布から各HOODUルートの各帯域のHOODU数を見積るステップS15と、デマンドを具体的なHOODUに配置するステップS16に分離している。更に、ステップS15の前処理において候補取得の際に工夫することで、余計な変数を抑制しつつ数理計画モデルを生成することを可能としている。このため、計算時間を従来方法に比べて削減でき、また、光ネットワーク全体におけるコストが最小となる最適な解を取得できる。
【0059】
なお前述の既知の手法を基にしたヒューイスティック手法と、本実施形態の手法を比較した結果を図11に示す。また、この比較のために使用した光ネットワークの構成を図12に示す。なお、ヒューイスティック手法とは、複数のデマンドのうち、始点と終点が同一のデマンドをまとめてHOODUを生成する。その後、残りのデマンドを短いデマンドから順に、帯域に余裕のあるHOODUに収容し、帯域に余裕のあるHOODUがなければ新たにHOODUを生成して収容する方法である。
【0060】
図12において、光ネットワークはノードN1〜N28で構成されている。ノード間を結ぶ直線で示すリンクに付した数字はノード間距離[km]を示している。図11において、横軸はデマンドの始終点対の数で、縦軸はHOODUの数である。破線Iaはヒューイスティック手法によるHOODUの数の変化を示し、実線Ibは本実施形態によるHOODUの数の変化を示している。本実施形態ではヒューイスティック手法に対し、デマンドの始終点対の数が多くなるほどHOODUの数を減少することができ、デマンドの始終点対の数が350付近では本実施形態はヒューイスティック手法に対しHOODUの数を30%以上削減でき、その分だけHOODUのコストを削減することができる。
(付記1)
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
を有することを特徴とするデマンド収容設計システム。
(付記2)
付記1記載のデマンド収容設計システムにおいて、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段を
有することを特徴とするデマンド収容設計システム。
(付記3)
付記2記載のデマンド収容設計システムであって、
前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計システム。
(付記4)
付記3記載のデマンド収容設計システムであって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計システム。
(付記5)
付記4記載のデマンド収容設計システムであって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計システム。
(付記6)
付記5記載のデマンド収容設計システムであって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計システム。
(付記7)
付記2乃至6のいずれか1項記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記8)
付記7記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記デマンドの経路上に3本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記9)
付記8記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記10)
付記9記載のデマンド収容設計システムであって、
前記抽出手段は、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記11)
付記10記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記12)
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計方法であって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得し、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する、
ことを特徴とするデマンド収容設計方法。
(付記13)
付記12記載のデマンド収容設計方法において、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する
ことを特徴とするデマンド収容設計方法。
(付記14)
付記13記載のデマンド収容設計方法であって、
前記目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計方法。
(付記15)
付記14記載のデマンド収容設計方法であって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計方法。
(付記16)
付記15記載のデマンド収容設計方法であって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計方法。
(付記17)
付記16記載のデマンド収容設計方法であって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計方法。
(付記18)
付記13乃至17のいずれか1項記載のデマンド収容設計方法であって、
前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記19)
付記18記載のデマンド収容設計方法であって、
更に、前記デマンドの経路上に3本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記20)
付記19記載のデマンド収容設計方法であって、
更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記21)
付記20記載のデマンド収容設計方法であって、
更に、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記22)
付記21記載のデマンド収容設計方法であって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計方法。
【符号の説明】
【0061】
11 入力装置
12 出力装置
13 ドライブ装置
14 補助記憶装置
15 メモリ装置
16 演算処理装置
17 データベース
18 システムバス
19 記憶媒体
【技術分野】
【0001】
本発明は、デマンド収容設計方法及びデマンド収容設計システムに関する。
【背景技術】
【0002】
近年、インターネットトラヒックの爆発的増大に対応可能である波長多重伝送(WDM)方式を前提とし、SDH(Synchronous Optical Network)又はSONET(Synchronous Digital Hierarchy)等の同期網のみならずIP(Internet Protocol)又はイーサネット(登録商標)系の非同期網のクライアント信号を、エンド・エンドで通信をする際に、上位レイヤーが下位レイヤーを一切意識しなくて済む、所謂トランスペアレントに伝送するプラットフォームとして、OTN(Optical Transport Network:光転送ネットワーク)がITU−Tにおいて勧告化されている。そのインタフェースやフレームフォーマットはITU−Tの勧告G.709により標準化されており、商用システムへの導入が急速に進んでいる。今後は、OTNクロスコネクト(XC:Cross−connect)装置を用いてOTN信号パスを柔軟に運用する光ネットワークの構築手法が重要となる。
【0003】
図1(A),(B)を用いてデマンドの光パスへの収容について説明する。なお、クライアント信号を収容する低速の信号転送用フレームであるODU(Optical channel Data Unit)フレームをLower Order ODU(LOODU)と呼び、この低速のODUフレームを複数多重収容するODUフレームをHigher Order ODU(HOODU)と呼ぶ。OTNにおいては、始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを発行することで、クライアント信号を収容したLOODUを光パスであるHOODUに収容する。
【0004】
図1(A)において、例えばデマンドD1はノード1,2,3の経路(始点ノードはノード1、終点ノードはノード3)の光パスを指定している。また、デマンドD2はノード4,3,5,6の経路の光パスを指定している。
【0005】
光パスはHOODUにより実現される。図1(B)において、例えばノード4,3間及びノード3,5の間にはHOODUの光パスP1が設定され、また、ノード5,6間には光パスP2が設定されている。上記のノード4,3,5,6の経路を指定するデマンドD2は光パスP1,P2によって実現される。
【0006】
ところで、数理計画法による光ネットワーク内のパス設計で「解空間の絞込み」という考えを導入し、経路設計における計算時間の増加を押さえることが提案されている(例えば特許文献1,2参照)。
【0007】
また、確率的デマンドパターンに対しリンク及びノードに関するコストを数理計画法に基づき最小化設計を行うことが提案されている(例えば特許文献3参照)。
【先行技術文献】
【特許文献】
【0008】
【特許文献1】特開2007−311900号公報
【特許文献2】特開2004−80666号公報
【特許文献3】特開平11−215124号公報
【発明の概要】
【発明が解決しようとする課題】
【0009】
デマンドを光パスに収容する設計には、アグリゲーションとグルーミングがある。アグリゲーションは、図2(A)に示すように、始点と終点及び経路が同一のデマンド同士を集約して1つの光パスであるHOODUに収容する設計である。図2(A)において、丸印がノードを表し、両端が矢頭の線分がデマンドを表し、複数のデマンドを包含する実線でHOODUを表している。例えばノードN1,N2,N3の経路を指定したデマンドD3,D4はHOODU11に収容されている。
いる。
【0010】
グルーミングは、図2(B)に示すように、ノードN1,N2間にHOODU12を設定し、ノードN1,N2間を経路に含む複数のデマンド(図では全てのデマンド)をHOODU12に収容する。同様に、ノードN2,N3間を経路に含む複数のデマンドをHOODU13に収容し、ノードN2,N4間を経路に含む複数のデマンドをHOODU14に収容している。
【0011】
アグリゲーションとグルーミングを用いれば、ノードN1〜N4間でデマンドを収容する方法は、図3(A)〜(D)に示すように各種の収容形態がある。なお、図3(A),(B)は図2(A),(B)と同一である。図3(C)ではノードN2,N3間にHOODU15,16,17を設けており、図3(D)ではノードN2,N3間にHOODU18,19を設けている。
【0012】
複数のデマンドが与えられた場合に、アグリゲーションとグルーミングを用いた図3(A)〜(D)に示すような各種の収容形態から、どの収容形態を選択すれば最もコストが小さく効率が良くなるかを設計することは、従来行われていなかった。
【0013】
開示のデマンド収容設計システムは、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することを目的とする。
【課題を解決するための手段】
【0014】
開示の一実施形態によるデマンド収容設計システムは、光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、を有する。
【発明の効果】
【0015】
本実施形態によれば、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することができる。
【図面の簡単な説明】
【0016】
【図1】デマンドの光パスへの収容について説明するための図である。
【図2】アグリゲーションとグルーミングを説明するための図である。
【図3】デマンドの収容形態を示す図である。
【図4】デマンド収容設計システムの一実施形態のハードウェア構成図である。
【図5】デマンド収容設計処理の一実施形態のフローチャートである。
【図6】HOODUルート候補とデマンドHOODUルートパターン候補を説明するための図である。
【図7】ステップS15,S16の解析結果を説明するための図である。
【図8】HOODUルート候補の抽出を説明するための図である。
【図9】混合整数計画モデルで使用する変数の一覧を示す図である。
【図10】ビンパッキングモデルで使用する変数の一覧を示す図である。
【図11】ヒューイスティック手法と本実施形態の手法を比較した結果を示す図である。
【図12】比較のために使用した光ネットワークの構成を示す図である。
【発明を実施するための形態】
【0017】
以下、図面に基づいて実施形態を説明する。
【0018】
<デマンド収容設計システムの構成>
図4はデマンド収容設計システムの一実施形態のハードウェア構成図を示す。図4において、デマンド収容設計システムは、入力装置21と、出力装置22と、ドライブ装置23と、補助記憶装置24と、メモリ装置25と、演算処理装置26と、データベース27を有しており、これらはシステムバス28で相互に接続されている。このデマンド収容設計システムは、専用の装置構成とすることもできるが、例えば、汎用のパーソナルコンピュータやワークステーション等を適用することが可能である。
【0019】
入力装置21は使用者が操作するキーボード及びマウス等を有しており、各種データを入力する。出力装置22はデマンド収容設計システムのプログラムを操作するのに必要な各種ウィンドウやデータ等を表示するディスプレイを有し、実行プログラムに基づいて表示される。実行プログラムは、例えばCD−ROM等の記録媒体29により提供される。プログラムを記緑した記録媒体29はドライブ装置23に装着され、記憶媒体29に格納された実行プログラムが記録媒体29からドライブ装置23を介してメモリ装置25にインストールされる。
【0020】
演算処理装置26はメモリ装置25から読み出された実行プログラムに基づいて、各種演算や後述する各処理を含むデマンド収容設計システム全体の処理を制御する。また、プログラムの実行中に必要な各種情報は、データベース27から取得することができ、また格納することもできる。
【0021】
<デマンド収容設計処理の一実施形態のフローチャート>
図5はデマンド収容設計処理の一実施形態のフローチャートを示す。図5において、ステップS11で光ネットワークのネットワーク基本情報であるネットワークトポロジを取得する。また、ステップS12で上記光ネットワークに対する全てのデマンドそれぞれの経路情報を取得する。各デマンドはクライアント信号を収容したLOODU単位で、始点ノードから経由する各ノードを含め終点ノードまでの経路を含んでいる。なお、各LOODU(例えばODU1,ODU2等)の帯域は決まっている。
【0022】
次に、ステップS13,S14で前準備処理を実行する。ステップS13で各デマンドにおいて使用可能性のある光パス候補としてのHOODUルート候補を抽出する。なお、デマンドが取得されていない経路についてはHOODUルート候補を抽出することはない。
【0023】
ここで、図6(A)に示すように始点ノード31から4つのノード32,33,34,35を経由して終点ノード36に至るデマンドについて考える。この場合、図6(A)に示すように、ノード31,33間を結ぶ光パス候補としてのHOODUルート候補1、ノード33,34間を結ぶHOODUルート候補2、ノード34,36間を結ぶHOODUルート候補3がある。この他にも、ノード33,35間を結ぶHOODUルート候補4がある。また、ノード31,32間を結ぶHOODUルート候補6、ノード32,35間を結ぶHOODUルート候補7、ノード35,36間を結ぶHOODUルート候補5がある。また、ノード31,36間を結ぶHOODUルート候補8があり、ノード31,34間を結ぶHOODUルート候補9がある。
【0024】
更に、ステップS14で各デマンドにおいて光パス候補を組み合わせてデマンドの始点ノードと終点ノードを結ぶ光パスパターン候補としてのデマンドHOODUルートパターン候補を抽出する。なお、デマンドが取得されていない経路についてはデマンドHOODUルートパターン候補を抽出することはない。
【0025】
図6(A)に示すデマンドとHOODUルート候補に対しては、図6(B)に示すように、HOODUルート候補1,HOODUルート候補2,HOODUルート候補3で構成されるデマンドHOODUルートパターン候補1がある。この他にも、HOODUルート候補1,HOODUルート候補4,HOODUルート候補5で構成されるデマンドHOODUルートパターン候補2があり、HOODUルート候補6,HOODUルート候補7,HOODUルート候補5で構成されるデマンドHOODUルートパターン候補3がある。更に、HOODUルート候補8で構成されるデマンドHOODUルートパターン候補4があり、HOODUルート候補9,HOODUルート候補3で構成されるデマンドHOODUルートパターン候補5がある。
【0026】
次に、ステップS15で主問題(Main Problem)である混合整数計画モデルを生成し、この主問題を解析する。ここでは、目的関数と制約条件を設定した混合整数計画モデルを用い数理計画法にて解析を行う。目的関数は、帯域別に生成されるHOODUの全体のコストが最小となることである。この場合の制約条件は第1に各デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数であることである。制約条件の第2は各HOODUルート候補において、このHOODUルート候補を通るデマンドHOODUルートパターン候補の帯域の総量が、帯域別に割当てられているHOODUの個数とHOODUの帯域との積和以下であることである。制約条件の第3は各リンクにおいて、HOODUの数が波長数制限値以下であることである。
【0027】
ステップS15の解析で得られる情報は、各HOODUルート候補について、各HOODU帯域(例えば10Gbps,100Gbps)のそれぞれに必要とされるHOODUの本数と、各HOODUルート候補に格納されるデマンドの数である。
【0028】
これにより、例えば図7の上部に示すように、ノード31,33間を結ぶHOODUルート候補1について、帯域100GbpsのHOODUが2本と、帯域10GbpsのHOODUが5本とが必要とされ、この合計7本のHOODUにより帯域BW8のデマンド#1と帯域BW2のデマンド#2と帯域BW1のデマンド#3〜#60を収容することが決定される。なお、帯域BW1はLOODU0の1トリビュータリスロット当たりの帯域(例えば1.25Gbps)を表しており、帯域BW2はLOODU1のトリビュータリスロット数が2で帯域2.5Gbpsを表し、帯域BW8はLOODU2のトリビュータリスロット数が8で帯域10Gbpsを表し、帯域BW80はLOODU4のトリビュータリスロット数が80で帯域80Gbpsを表している。
【0029】
次に、ステップS16でどのHOODUにどのデマンドを割当てて収容するかを具体的に決定する。ステップS16ではビンパッキングモデルを用いた数理計画法にて解析を行う。ビンビンパッキング問題は、各HOODUルート候補について、ステップS15で算出された主問題の解析結果を基に実行する。図7に示す例では、ステップS15において、帯域100GbpsのHOODUが2本と、帯域10GbpsのHOODUが5本とを用いて、帯域BW8のデマンド#1と帯域BW2のデマンド#2と帯域BW1のデマンド#3〜#60を収容することが決定されている。
【0030】
この場合、ステップS16の実行により、図7の下部に示すように、例えば1番目の帯域100GbpsのHOODUにデマンド#1,#8,…,#55を収容し、2番目の帯域100GbpsのHOODUにデマンド#2,#6,…,#60を収容する。そして、1番目の帯域10GbpsのHOODUにデマンド#7を収容し、2番目の帯域10GbpsのHOODUにデマンド#11,#18を収容し、3番目の帯域10GbpsのHOODUにデマンド#5,#23を収容し、4番目の帯域10GbpsのHOODUにデマンド#19,#38を収容し、5番目の帯域10GbpsのHOODUにデマンド#32,#36を収容することが決定される。
【0031】
こののち、ステップS17で各デマンドを収容した各HOODUの波長割当と使用する送受信カードを決定するなどの阿路処理を行って設計を終了する。
【0032】
<HOODUルート候補抽出処理>
ステップS13で実行するHOODUルート候補抽出処理について詳しく説明する。本実施形態では光ネットワークを構成するノードの中で、3本以上のリンクを有するノードをハブサイトと呼ぶ。なお、リンクは隣接するノードを連結する光伝送路であり、スパンとも呼ぶ。
【0033】
デマンドが図8(A)に示す始点ノード(src)41、終点ノード(dst)49で、ノード41,42,43,44,45,46,47,48,49の経路を持ち、このうち、ノード42,44,46,48がハブサイト(hub)であるとする。
【0034】
まず第1に、図8(A)に示すように、始点ノード41と終点ノード49を直結するルートをHOODUルート候補50aとして抽出する。
【0035】
第2に、図8(B)に示すように、デマンド経路内の始点ノード41又は終点ノード49とハブサイト間、及びハブサイト間を連結するルートをHOODUルート候補50b,50c,50d、50e,50fとして抽出する。
【0036】
第3に、図8(C)に示すように、始点ノード41と終点ノード49それぞれに最も近いハブサイト42,48間を連結するルートをHOODUルート候補50gとして抽出する。
【0037】
上記が代表的なHOODUルート候補の抽出方法であるが、これ以外にも以下の第4から第6の抽出を行っても良い。
【0038】
第4に、隣接サイト間を連結するルートをHOODUルート候補として抽出する。
【0039】
第5に、デマンド経路内のハブサイトを任意に2つ選択し、選択した2つのハブサイトを連結するルートをHOODUルート候補として抽出する。
【0040】
第6に、上記の第1〜第5の方法それぞれで抽出したHOODUルート候補のうち、HOODUルート候補内でのホップ数又はHOODUルート候補を構成するノード数を予め定められた上限値及び/又は下限値と比較し、上限値以上又は以下、下限値以上又は以下、等の条件を満たすものだけをHOODUルート候補として再び抽出する。
【0041】
<デマンドHOODUルートパターン候補抽出処理>
ステップS14で実行するデマンドHOODUルートパターン候補抽出処理について詳しく説明する。基本的に、デマンドHOODUルートパターン候補は抽出されたHOODUルート候補から各デマンドにおいて抽出可能なデマンドHOODUルートパターン候補を全て列挙するという方法を用いる。つまり、デマンドから抽出されたHOODUルート候補そのもの又は抽出されたHOODUルート候補を組み合わせて、デマンドの始点ノードから終点ノードを結ぶパターンをデマンドHOODUルートパターン候補として抽出する。
【0042】
例えば図6(A)に示すデマンドとHOODUルート候補については、図6(B)に示すデマンドHOODUルートパターン候補1〜デマンドHOODUルートパターン候補5を抽出する。
【0043】
ただし、場合によっては、各デマンドにおけるHOODUの乗換回数を一定回数以下に制限する、という制約を設けても良い。図6(A)に示すデマンドとHOODUルート候補について、HOODUの乗換回数を1回以内に抑えるという制約条件を付加した場合には、図6(B)に示すデマンドHOODUルートパターン候補1〜デマンドHOODUルートパターン候補5のうち、制約条件に該当するデマンドHOODUルートパターン候補4、及びデマンドHOODUルートパターン候補5のみを抽出する。なお、制約条件の付加方法については、これに限るものではない。
【0044】
<主問題作成及び解析処理>
ステップS15で実行する主問題作成及び解析処理について詳しく説明する。なお、以下の具体例においては、HOODUの帯域として10Gbps、100Gbpsの2種類が設定可能である場合を想定する。また、混合整数計画モデルで使用する変数の一覧を図9に示す。
【0045】
図9において、tはデマンドHOODUルートパターン候補の番号、hはHOODUルート候補の番号、sは光ネットワーク内のリンク(又はスパン)の番号、lはデマンドの番号である。d(t)はデマンドHOODUルートパターン候補tをいくつ採用するかの変数、xh10(h)はHOODUルート候補hにおける10GbpsのHOODUの使用個数、xh100(h)はHOODUルート候補hにおける100GbpsのHOODUの使用個数である。
【0046】
Demand_Cap(t)はデマンドHOODUルートパターン候補tの1本当たりの帯域、I(h,t)はデマンドHOODUルートパターン候補tにHOODUルート候補hが含まれるか否かの識別子(値1は含む、値0は含まない)、T(l,t)はデマンドHOODUルートパターン候補tがデマンドlに属するか否かの識別子(値1は属する、値0は属さない)である。
【0047】
Total Demand Numはデマンドの合計本数、Wavelength Limit(s)はリンクsにおける波長数の上限値、Link(s,h)はHOODUルート候補hにリンクsを含むか否かの識別子(値1は含む、値0は含まない)である。また、xh10(h)の係数となる「8」は10GbpsのHOODUのトリビュータリスロット数つまり8×1.25Gbpsの帯域を表し、xh100(h)の係数となる80は100GbpsのHOODUのトリビュータリスロット数つまり80×1.25Gbpsの帯域を表している。
【0048】
この場合、目的関数は(1)式で表される。(1)式で、COSTh10は10GbpsのHOODUを使用するコスト、COSTh100は100GbpsのHOODUを使用するコストである。コストとはHOODUを使用するための費用であり、例えばCOSTh100はCOSTh10の数倍に設定される。また、定数であるCOSTh100,COSTh10は設計を行うときの状況により、どのように設定することも可能である。
【0049】
(1)式は、生成される10GbpsのHOODUと100GbpsのHOODUの全体のコストが最小となることを表している。
【0050】
【数1】
【0051】
制約条件は(2)式、(3)式、(4)式で表される。(2)式は各デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数であることを表す。(3)式は各HOODUルート候補において、このHOODUルート候補を通る(もしくはHOODUルート候補に含まれる)デマンドHOODUルートパターン候補の帯域の総量が、帯域別に割当てられているHOODUの個数とHOODUの帯域との積和以下であることを表す。(4)式は各リンクにおいて、HOODUの数がリンクの波長数制限値以下であることを表す。
【0052】
【数2】
【0053】
なお、上記(1)〜(4)式では、HOODUの帯域として10Gbps、100Gbpsの2種類を設定しているが、HOODUの帯域はこれに限られるものではなく、1種類又は3種類以上であっても良い。
【0054】
<ビンパッキング作成及び解析処理>
ステップS16で実行する割当収容処理について説明する。ここで、簡単な例えとして、100GbpsのHOODUは大きな籠、10GbpsのHOODUは小さな籠、デマンドがリンゴだとした場合、限られた籠の容積の中に、どのようにうまくリンゴを収納するかを決定する。これは単純なビンパッキング問題であるため、これを解くための既存の手法、すなわち、数理計画法を用いても対応可能であるし、既存のヒューリスチックな手法(貪欲法等)で対応することも対応可能である。
【0055】
ビンパッキングにおける目的関数と制約条件を以下に示す。また、ビンパッキングモデルで使用する変数の一覧を図10に示す。図10において、xはデマンドの番号、yはHOODUの番号、s(x,y)はデマンドxがHOODUyに格納されるか否かの識別子(値1は格納される、値0は格納されない)、HOODU(y)はHOODUyが使用されるか否かの識別子(値1は使用される、値0は使用されない)、Demand_Cap(x)はデマンドxの帯域、Demand_Num(x)は現在のHOODUルート候補に割当てられたデマンドxの本数、HOODU_Cap(y)はHOODUyの容量、Mは例えば10000等の十分に大きな数である。
【0056】
この場合、目的関数は(5)式で表される。(5)式は、使用するHOODUの数が最小となることを表している。制約条件は(6)式、(7)式、(8)式で表される。(6)式はデマンドxがいずれかのHOODUyに収容されることを表す。(7)式はHOODUに格納されるデマンドの総帯域がHOODUの容量以下であることを表す。(8)式はどれか1つでもデマンドが収容されるHOODUは、そのHOODUを「使用する」とみなすことを表す。
【0057】
【数3】
【0058】
本実施形態では、デマンド収容設計をデマンド分布から各HOODUルートの各帯域のHOODU数を見積るステップS15と、デマンドを具体的なHOODUに配置するステップS16に分離している。更に、ステップS15の前処理において候補取得の際に工夫することで、余計な変数を抑制しつつ数理計画モデルを生成することを可能としている。このため、計算時間を従来方法に比べて削減でき、また、光ネットワーク全体におけるコストが最小となる最適な解を取得できる。
【0059】
なお前述の既知の手法を基にしたヒューイスティック手法と、本実施形態の手法を比較した結果を図11に示す。また、この比較のために使用した光ネットワークの構成を図12に示す。なお、ヒューイスティック手法とは、複数のデマンドのうち、始点と終点が同一のデマンドをまとめてHOODUを生成する。その後、残りのデマンドを短いデマンドから順に、帯域に余裕のあるHOODUに収容し、帯域に余裕のあるHOODUがなければ新たにHOODUを生成して収容する方法である。
【0060】
図12において、光ネットワークはノードN1〜N28で構成されている。ノード間を結ぶ直線で示すリンクに付した数字はノード間距離[km]を示している。図11において、横軸はデマンドの始終点対の数で、縦軸はHOODUの数である。破線Iaはヒューイスティック手法によるHOODUの数の変化を示し、実線Ibは本実施形態によるHOODUの数の変化を示している。本実施形態ではヒューイスティック手法に対し、デマンドの始終点対の数が多くなるほどHOODUの数を減少することができ、デマンドの始終点対の数が350付近では本実施形態はヒューイスティック手法に対しHOODUの数を30%以上削減でき、その分だけHOODUのコストを削減することができる。
(付記1)
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
を有することを特徴とするデマンド収容設計システム。
(付記2)
付記1記載のデマンド収容設計システムにおいて、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段を
有することを特徴とするデマンド収容設計システム。
(付記3)
付記2記載のデマンド収容設計システムであって、
前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計システム。
(付記4)
付記3記載のデマンド収容設計システムであって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計システム。
(付記5)
付記4記載のデマンド収容設計システムであって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計システム。
(付記6)
付記5記載のデマンド収容設計システムであって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計システム。
(付記7)
付記2乃至6のいずれか1項記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記8)
付記7記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記デマンドの経路上に3本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記9)
付記8記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記10)
付記9記載のデマンド収容設計システムであって、
前記抽出手段は、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記11)
付記10記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
(付記12)
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計方法であって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得し、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する、
ことを特徴とするデマンド収容設計方法。
(付記13)
付記12記載のデマンド収容設計方法において、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する
ことを特徴とするデマンド収容設計方法。
(付記14)
付記13記載のデマンド収容設計方法であって、
前記目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計方法。
(付記15)
付記14記載のデマンド収容設計方法であって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計方法。
(付記16)
付記15記載のデマンド収容設計方法であって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計方法。
(付記17)
付記16記載のデマンド収容設計方法であって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計方法。
(付記18)
付記13乃至17のいずれか1項記載のデマンド収容設計方法であって、
前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記19)
付記18記載のデマンド収容設計方法であって、
更に、前記デマンドの経路上に3本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記20)
付記19記載のデマンド収容設計方法であって、
更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記21)
付記20記載のデマンド収容設計方法であって、
更に、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計方法。
(付記22)
付記21記載のデマンド収容設計方法であって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計方法。
【符号の説明】
【0061】
11 入力装置
12 出力装置
13 ドライブ装置
14 補助記憶装置
15 メモリ装置
16 演算処理装置
17 データベース
18 システムバス
19 記憶媒体
【特許請求の範囲】
【請求項1】
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
を有することを特徴とするデマンド収容設計システム。
【請求項2】
請求項1記載のデマンド収容設計システムにおいて、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段を
有することを特徴とするデマンド収容設計システム。
【請求項3】
請求項2記載のデマンド収容設計システムであって、
前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計システム。
【請求項4】
請求項3記載のデマンド収容設計システムであって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計システム。
【請求項5】
請求項4記載のデマンド収容設計システムであって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計システム。
【請求項6】
請求項5記載のデマンド収容設計システムであって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計システム。
【請求項7】
請求項2乃至6のいずれか1項記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項8】
請求項7記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記デマンドの経路上に3本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項9】
請求項8記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項10】
請求項9記載のデマンド収容設計システムであって、
前記抽出手段は、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項11】
請求項10記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項12】
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計方法であって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得し、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する、
ことを特徴とするデマンド収容設計方法。
【請求項13】
請求項12記載のデマンド収容設計方法において、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する
ことを特徴とするデマンド収容設計方法。
【請求項14】
請求項13記載のデマンド収容設計方法であって、
前記目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計方法。
【請求項15】
請求項14記載のデマンド収容設計方法であって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計方法。
【請求項16】
請求項15記載のデマンド収容設計方法であって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計方法。
【請求項17】
請求項16記載のデマンド収容設計方法であって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計方法。
【請求項1】
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
を有することを特徴とするデマンド収容設計システム。
【請求項2】
請求項1記載のデマンド収容設計システムにおいて、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段を
有することを特徴とするデマンド収容設計システム。
【請求項3】
請求項2記載のデマンド収容設計システムであって、
前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計システム。
【請求項4】
請求項3記載のデマンド収容設計システムであって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計システム。
【請求項5】
請求項4記載のデマンド収容設計システムであって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計システム。
【請求項6】
請求項5記載のデマンド収容設計システムであって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計システム。
【請求項7】
請求項2乃至6のいずれか1項記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項8】
請求項7記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記デマンドの経路上に3本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項9】
請求項8記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項10】
請求項9記載のデマンド収容設計システムであって、
前記抽出手段は、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項11】
請求項10記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
【請求項12】
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計方法であって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得し、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する、
ことを特徴とするデマンド収容設計方法。
【請求項13】
請求項12記載のデマンド収容設計方法において、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する
ことを特徴とするデマンド収容設計方法。
【請求項14】
請求項13記載のデマンド収容設計方法であって、
前記目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計方法。
【請求項15】
請求項14記載のデマンド収容設計方法であって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計方法。
【請求項16】
請求項15記載のデマンド収容設計方法であって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計方法。
【請求項17】
請求項16記載のデマンド収容設計方法であって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2013−90297(P2013−90297A)
【公開日】平成25年5月13日(2013.5.13)
【国際特許分類】
【出願番号】特願2011−232251(P2011−232251)
【出願日】平成23年10月21日(2011.10.21)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
【公開日】平成25年5月13日(2013.5.13)
【国際特許分類】
【出願日】平成23年10月21日(2011.10.21)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
[ Back to top ]