JP5811764B2 - デマンド収容設計方法及びデマンド収容設計システム - Google Patents

Description

本発明は、デマンド収容設計方法及びデマンド収容設計システムに関する。

近年、インターネットトラヒックの爆発的増大に対応可能である波長多重伝送（ＷＤＭ）方式を前提とし、ＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ Ｏｐｔｉｃａｌ Ｎｅｔｗｏｒｋ）又はＳＯＮＥＴ（Ｓｙｎｃｈｒｏｎｏｕｓ Ｄｉｇｉｔａｌ Ｈｉｅｒａｒｃｈｙ）等の同期網のみならずＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）又はイーサネット（登録商標）系の非同期網のクライアント信号を、エンド・エンドで通信をする際に、上位レイヤーが下位レイヤーを一切意識しなくて済む、所謂トランスペアレントに伝送するプラットフォームとして、ＯＴＮ（Ｏｐｔｉｃａｌ Ｔｒａｎｓｐｏｒｔ Ｎｅｔｗｏｒｋ：光転送ネットワーク）がＩＴＵ−Ｔにおいて勧告化されている。そのインタフェースやフレームフォーマットはＩＴＵ−Ｔの勧告Ｇ．７０９により標準化されており、商用システムへの導入が急速に進んでいる。今後は、ＯＴＮクロスコネクト（ＸＣ：Ｃｒｏｓｓ−ｃｏｎｎｅｃｔ）装置を用いてＯＴＮ信号パスを柔軟に運用する光ネットワークの構築手法が重要となる。

図１（Ａ），（Ｂ）を用いてデマンドの光パスへの収容について説明する。なお、クライアント信号を収容する低速の信号転送用フレームであるＯＤＵ（Ｏｐｔｉｃａｌ ｃｈａｎｎｅｌ Ｄａｔａ Ｕｎｉｔ）フレームをＬｏｗｅｒ Ｏｒｄｅｒ ＯＤＵ（ＬＯＯＤＵ）と呼び、この低速のＯＤＵフレームを複数多重収容するＯＤＵフレームをＨｉｇｈｅｒ Ｏｒｄｅｒ ＯＤＵ（ＨＯＯＤＵ）と呼ぶ。ＯＴＮにおいては、始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを発行することで、クライアント信号を収容したＬＯＯＤＵを光パスであるＨＯＯＤＵに収容する。

図１（Ａ）において、例えばデマンドＤ１はノード１，２，３の経路（始点ノードはノード１、終点ノードはノード３）の光パスを指定している。また、デマンドＤ２はノード４，３，５，６の経路の光パスを指定している。

光パスはＨＯＯＤＵにより実現される。図１（Ｂ）において、例えばノード４，３間及びノード３，５の間にはＨＯＯＤＵの光パスＰ１が設定され、また、ノード５，６間には光パスＰ２が設定されている。上記のノード４，３，５，６の経路を指定するデマンドＤ２は光パスＰ１，Ｐ２によって実現される。

ところで、数理計画法による光ネットワーク内のパス設計で「解空間の絞込み」という考えを導入し、経路設計における計算時間の増加を押さえることが提案されている（例えば特許文献１，２参照）。

また、確率的デマンドパターンに対しリンク及びノードに関するコストを数理計画法に基づき最小化設計を行うことが提案されている（例えば特許文献３参照）。

特開２００７−３１１９００号公報 特開２００４−８０６６６号公報 特開平１１−２１５１２４号公報

デマンドを光パスに収容する設計には、アグリゲーションとグルーミングがある。アグリゲーションは、図２（Ａ）に示すように、始点と終点及び経路が同一のデマンド同士を集約して１つの光パスであるＨＯＯＤＵに収容する設計である。図２（Ａ）において、丸印がノードを表し、両端が矢頭の線分がデマンドを表し、複数のデマンドを包含する実線でＨＯＯＤＵを表している。例えばノードＮ１，Ｎ２，Ｎ３の経路を指定したデマンドＤ３，Ｄ４はＨＯＯＤＵ１１に収容されている。
いる。

グルーミングは、図２（Ｂ）に示すように、ノードＮ１，Ｎ２間にＨＯＯＤＵ１２を設定し、ノードＮ１，Ｎ２間を経路に含む複数のデマンド（図では全てのデマンド）をＨＯＯＤＵ１２に収容する。同様に、ノードＮ２，Ｎ３間を経路に含む複数のデマンドをＨＯＯＤＵ１３に収容し、ノードＮ２，Ｎ４間を経路に含む複数のデマンドをＨＯＯＤＵ１４に収容している。

アグリゲーションとグルーミングを用いれば、ノードＮ１〜Ｎ４間でデマンドを収容する方法は、図３（Ａ）〜（Ｄ）に示すように各種の収容形態がある。なお、図３（Ａ），（Ｂ）は図２（Ａ），（Ｂ）と同一である。図３（Ｃ）ではノードＮ２，Ｎ３間にＨＯＯＤＵ１５，１６，１７を設けており、図３（Ｄ）ではノードＮ２，Ｎ３間にＨＯＯＤＵ１８，１９を設けている。

複数のデマンドが与えられた場合に、アグリゲーションとグルーミングを用いた図３（Ａ）〜（Ｄ）に示すような各種の収容形態から、どの収容形態を選択すれば最もコストが小さく効率が良くなるかを設計することは、従来行われていなかった。

開示のデマンド収容設計システムは、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することを目的とする。

開示の一実施形態によるデマンド収容設計システムは、光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、少なくとも前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ条件を制約条件として採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段と、
を有し、
前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の信号転送用フレームの使用個数との積を加算した値の前記抽出手段で抽出された光パス候補の数分の総和を最小化することである。

本実施形態によれば、グルーミングを考慮してコストが最小になるようにデマンドを光パスに収容することができる。

デマンドの光パスへの収容について説明するための図である。 アグリゲーションとグルーミングを説明するための図である。 デマンドの収容形態を示す図である。 デマンド収容設計システムの一実施形態のハードウェア構成図である。 デマンド収容設計処理の一実施形態のフローチャートである。 ＨＯＯＤＵルート候補とデマンドＨＯＯＤＵルートパターン候補を説明するための図である。 ステップＳ１５，Ｓ１６の解析結果を説明するための図である。 ＨＯＯＤＵルート候補の抽出を説明するための図である。 混合整数計画モデルで使用する変数の一覧を示す図である。 ビンパッキングモデルで使用する変数の一覧を示す図である。 ヒューイスティック手法と本実施形態の手法を比較した結果を示す図である。 比較のために使用した光ネットワークの構成を示す図である。

以下、図面に基づいて実施形態を説明する。

＜デマンド収容設計システムの構成＞
図４はデマンド収容設計システムの一実施形態のハードウェア構成図を示す。図４において、デマンド収容設計システムは、入力装置２１と、出力装置２２と、ドライブ装置２３と、補助記憶装置２４と、メモリ装置２５と、演算処理装置２６と、データベース２７を有しており、これらはシステムバス２８で相互に接続されている。このデマンド収容設計システムは、専用の装置構成とすることもできるが、例えば、汎用のパーソナルコンピュータやワークステーション等を適用することが可能である。

入力装置２１は使用者が操作するキーボード及びマウス等を有しており、各種データを入力する。出力装置２２はデマンド収容設計システムのプログラムを操作するのに必要な各種ウィンドウやデータ等を表示するディスプレイを有し、実行プログラムに基づいて表示される。実行プログラムは、例えばＣＤ−ＲＯＭ等の記録媒体２９により提供される。プログラムを記緑した記録媒体２９はドライブ装置２３に装着され、記憶媒体２９に格納された実行プログラムが記録媒体２９からドライブ装置２３を介してメモリ装置２５にインストールされる。

演算処理装置２６はメモリ装置２５から読み出された実行プログラムに基づいて、各種演算や後述する各処理を含むデマンド収容設計システム全体の処理を制御する。また、プログラムの実行中に必要な各種情報は、データベース２７から取得することができ、また格納することもできる。

＜デマンド収容設計処理の一実施形態のフローチャート＞
図５はデマンド収容設計処理の一実施形態のフローチャートを示す。図５において、ステップＳ１１で光ネットワークのネットワーク基本情報であるネットワークトポロジを取得する。また、ステップＳ１２で上記光ネットワークに対する全てのデマンドそれぞれの経路情報を取得する。各デマンドはクライアント信号を収容したＬＯＯＤＵ単位で、始点ノードから経由する各ノードを含め終点ノードまでの経路を含んでいる。なお、各ＬＯＯＤＵ（例えばＯＤＵ１，ＯＤＵ２等）の帯域は決まっている。

次に、ステップＳ１３，Ｓ１４で前準備処理を実行する。ステップＳ１３で各デマンドにおいて使用可能性のある光パス候補としてのＨＯＯＤＵルート候補を抽出する。なお、デマンドが取得されていない経路についてはＨＯＯＤＵルート候補を抽出することはない。

ここで、図６（Ａ）に示すように始点ノード３１から４つのノード３２，３３，３４，３５を経由して終点ノード３６に至るデマンドについて考える。この場合、図６（Ａ）に示すように、ノード３１，３３間を結ぶ光パス候補としてのＨＯＯＤＵルート候補１、ノード３３，３４間を結ぶＨＯＯＤＵルート候補２、ノード３４，３６間を結ぶＨＯＯＤＵルート候補３がある。この他にも、ノード３３，３５間を結ぶＨＯＯＤＵルート候補４がある。また、ノード３１，３２間を結ぶＨＯＯＤＵルート候補６、ノード３２，３５間を結ぶＨＯＯＤＵルート候補７、ノード３５，３６間を結ぶＨＯＯＤＵルート候補５がある。また、ノード３１，３６間を結ぶＨＯＯＤＵルート候補８があり、ノード３１，３４間を結ぶＨＯＯＤＵルート候補９がある。

更に、ステップＳ１４で各デマンドにおいて光パス候補を組み合わせてデマンドの始点ノードと終点ノードを結ぶ光パスパターン候補としてのデマンドＨＯＯＤＵルートパターン候補を抽出する。なお、デマンドが取得されていない経路についてはデマンドＨＯＯＤＵルートパターン候補を抽出することはない。

図６（Ａ）に示すデマンドとＨＯＯＤＵルート候補に対しては、図６（Ｂ）に示すように、ＨＯＯＤＵルート候補１，ＨＯＯＤＵルート候補２，ＨＯＯＤＵルート候補３で構成されるデマンドＨＯＯＤＵルートパターン候補１がある。この他にも、ＨＯＯＤＵルート候補１，ＨＯＯＤＵルート候補４，ＨＯＯＤＵルート候補５で構成されるデマンドＨＯＯＤＵルートパターン候補２があり、ＨＯＯＤＵルート候補６，ＨＯＯＤＵルート候補７，ＨＯＯＤＵルート候補５で構成されるデマンドＨＯＯＤＵルートパターン候補３がある。更に、ＨＯＯＤＵルート候補８で構成されるデマンドＨＯＯＤＵルートパターン候補４があり、ＨＯＯＤＵルート候補９，ＨＯＯＤＵルート候補３で構成されるデマンドＨＯＯＤＵルートパターン候補５がある。

次に、ステップＳ１５で主問題（Ｍａｉｎ Ｐｒｏｂｌｅｍ）である混合整数計画モデルを生成し、この主問題を解析する。ここでは、目的関数と制約条件を設定した混合整数計画モデルを用い数理計画法にて解析を行う。目的関数は、帯域別に生成されるＨＯＯＤＵの全体のコストが最小となることである。この場合の制約条件は第１に各デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数であることである。制約条件の第２は各ＨＯＯＤＵルート候補において、このＨＯＯＤＵルート候補を通るデマンドＨＯＯＤＵルートパターン候補の帯域の総量が、帯域別に割当てられているＨＯＯＤＵの個数とＨＯＯＤＵの帯域との積和以下であることである。制約条件の第３は各リンクにおいて、ＨＯＯＤＵの数が波長数制限値以下であることである。

ステップＳ１５の解析で得られる情報は、各ＨＯＯＤＵルート候補について、各ＨＯＯＤＵ帯域（例えば１０Ｇｂｐｓ，１００Ｇｂｐｓ）のそれぞれに必要とされるＨＯＯＤＵの本数と、各ＨＯＯＤＵルート候補に格納されるデマンドの数である。

これにより、例えば図７の上部に示すように、ノード３１，３３間を結ぶＨＯＯＤＵルート候補１について、帯域１００ＧｂｐｓのＨＯＯＤＵが２本と、帯域１０ＧｂｐｓのＨＯＯＤＵが５本とが必要とされ、この合計７本のＨＯＯＤＵにより帯域ＢＷ８のデマンド＃１と帯域ＢＷ２のデマンド＃２と帯域ＢＷ１のデマンド＃３〜＃６０を収容することが決定される。なお、帯域ＢＷ１はＬＯＯＤＵ０の１トリビュータリスロット当たりの帯域（例えば１．２５Ｇｂｐｓ）を表しており、帯域ＢＷ２はＬＯＯＤＵ１のトリビュータリスロット数が２で帯域２．５Ｇｂｐｓを表し、帯域ＢＷ８はＬＯＯＤＵ２のトリビュータリスロット数が８で帯域１０Ｇｂｐｓを表し、帯域ＢＷ８０はＬＯＯＤＵ４のトリビュータリスロット数が８０で帯域８０Ｇｂｐｓを表している。

次に、ステップＳ１６でどのＨＯＯＤＵにどのデマンドを割当てて収容するかを具体的に決定する。ステップＳ１６ではビンパッキングモデルを用いた数理計画法にて解析を行う。ビンビンパッキング問題は、各ＨＯＯＤＵルート候補について、ステップＳ１５で算出された主問題の解析結果を基に実行する。図７に示す例では、ステップＳ１５において、帯域１００ＧｂｐｓのＨＯＯＤＵが２本と、帯域１０ＧｂｐｓのＨＯＯＤＵが５本とを用いて、帯域ＢＷ８のデマンド＃１と帯域ＢＷ２のデマンド＃２と帯域ＢＷ１のデマンド＃３〜＃６０を収容することが決定されている。

この場合、ステップＳ１６の実行により、図７の下部に示すように、例えば１番目の帯域１００ＧｂｐｓのＨＯＯＤＵにデマンド＃１，＃８，…，＃５５を収容し、２番目の帯域１００ＧｂｐｓのＨＯＯＤＵにデマンド＃２，＃６，…，＃６０を収容する。そして、１番目の帯域１０ＧｂｐｓのＨＯＯＤＵにデマンド＃７を収容し、２番目の帯域１０ＧｂｐｓのＨＯＯＤＵにデマンド＃１１，＃１８を収容し、３番目の帯域１０ＧｂｐｓのＨＯＯＤＵにデマンド＃５，＃２３を収容し、４番目の帯域１０ＧｂｐｓのＨＯＯＤＵにデマンド＃１９，＃３８を収容し、５番目の帯域１０ＧｂｐｓのＨＯＯＤＵにデマンド＃３２，＃３６を収容することが決定される。

こののち、ステップＳ１７で各デマンドを収容した各ＨＯＯＤＵの波長割当と使用する送受信カードを決定するなどの阿路処理を行って設計を終了する。

＜ＨＯＯＤＵルート候補抽出処理＞
ステップＳ１３で実行するＨＯＯＤＵルート候補抽出処理について詳しく説明する。本実施形態では光ネットワークを構成するノードの中で、３本以上のリンクを有するノードをハブサイトと呼ぶ。なお、リンクは隣接するノードを連結する光伝送路であり、スパンとも呼ぶ。

デマンドが図８（Ａ）に示す始点ノード（ｓｒｃ）４１、終点ノード（ｄｓｔ）４９で、ノード４１，４２，４３，４４，４５，４６，４７，４８，４９の経路を持ち、このうち、ノード４２，４４，４６，４８がハブサイト（ｈｕｂ）であるとする。

まず第１に、図８（Ａ）に示すように、始点ノード４１と終点ノード４９を直結するルートをＨＯＯＤＵルート候補５０ａとして抽出する。

第２に、図８（Ｂ）に示すように、デマンド経路内の始点ノード４１又は終点ノード４９とハブサイト間、及びハブサイト間を連結するルートをＨＯＯＤＵルート候補５０ｂ，５０ｃ，５０ｄ、５０ｅ，５０ｆとして抽出する。

第３に、図８（Ｃ）に示すように、始点ノード４１と終点ノード４９それぞれに最も近いハブサイト４２，４８間を連結するルートをＨＯＯＤＵルート候補５０ｇとして抽出する。

上記が代表的なＨＯＯＤＵルート候補の抽出方法であるが、これ以外にも以下の第４から第６の抽出を行っても良い。

第４に、隣接サイト間を連結するルートをＨＯＯＤＵルート候補として抽出する。

第５に、デマンド経路内のハブサイトを任意に２つ選択し、選択した２つのハブサイトを連結するルートをＨＯＯＤＵルート候補として抽出する。

第６に、上記の第１〜第５の方法それぞれで抽出したＨＯＯＤＵルート候補のうち、ＨＯＯＤＵルート候補内でのホップ数又はＨＯＯＤＵルート候補を構成するノード数を予め定められた上限値及び／又は下限値と比較し、上限値以上又は以下、下限値以上又は以下、等の条件を満たすものだけをＨＯＯＤＵルート候補として再び抽出する。

＜デマンドＨＯＯＤＵルートパターン候補抽出処理＞
ステップＳ１４で実行するデマンドＨＯＯＤＵルートパターン候補抽出処理について詳しく説明する。基本的に、デマンドＨＯＯＤＵルートパターン候補は抽出されたＨＯＯＤＵルート候補から各デマンドにおいて抽出可能なデマンドＨＯＯＤＵルートパターン候補を全て列挙するという方法を用いる。つまり、デマンドから抽出されたＨＯＯＤＵルート候補そのもの又は抽出されたＨＯＯＤＵルート候補を組み合わせて、デマンドの始点ノードから終点ノードを結ぶパターンをデマンドＨＯＯＤＵルートパターン候補として抽出する。

例えば図６（Ａ）に示すデマンドとＨＯＯＤＵルート候補については、図６（Ｂ）に示すデマンドＨＯＯＤＵルートパターン候補１〜デマンドＨＯＯＤＵルートパターン候補５を抽出する。

ただし、場合によっては、各デマンドにおけるＨＯＯＤＵの乗換回数を一定回数以下に制限する、という制約を設けても良い。図６（Ａ）に示すデマンドとＨＯＯＤＵルート候補について、ＨＯＯＤＵの乗換回数を１回以内に抑えるという制約条件を付加した場合には、図６（Ｂ）に示すデマンドＨＯＯＤＵルートパターン候補１〜デマンドＨＯＯＤＵルートパターン候補５のうち、制約条件に該当するデマンドＨＯＯＤＵルートパターン候補４、及びデマンドＨＯＯＤＵルートパターン候補５のみを抽出する。なお、制約条件の付加方法については、これに限るものではない。

＜主問題作成及び解析処理＞
ステップＳ１５で実行する主問題作成及び解析処理について詳しく説明する。なお、以下の具体例においては、ＨＯＯＤＵの帯域として１０Ｇｂｐｓ、１００Ｇｂｐｓの２種類が設定可能である場合を想定する。また、混合整数計画モデルで使用する変数の一覧を図９に示す。

図９において、ｔはデマンドＨＯＯＤＵルートパターン候補の番号、ｈはＨＯＯＤＵルート候補の番号、ｓは光ネットワーク内のリンク（又はスパン）の番号、ｌはデマンドの番号である。ｄ（ｔ）はデマンドＨＯＯＤＵルートパターン候補ｔをいくつ採用するかの変数、ｘ_ｈ１０（ｈ）はＨＯＯＤＵルート候補ｈにおける１０ＧｂｐｓのＨＯＯＤＵの使用個数、ｘ_ｈ１００（ｈ）はＨＯＯＤＵルート候補ｈにおける１００ＧｂｐｓのＨＯＯＤＵの使用個数である。

Ｄｅｍａｎｄ＿Ｃａｐ（ｔ）はデマンドＨＯＯＤＵルートパターン候補ｔの１本当たりの帯域、Ｉ（ｈ，ｔ）はデマンドＨＯＯＤＵルートパターン候補ｔにＨＯＯＤＵルート候補ｈが含まれるか否かの識別子（値１は含む、値０は含まない）、Ｔ（ｌ，ｔ）はデマンドＨＯＯＤＵルートパターン候補ｔがデマンドｌに属するか否かの識別子（値１は属する、値０は属さない）である。

Ｔｏｔａｌ Ｄｅｍａｎｄ Ｎｕｍはデマンドの合計本数、Ｗａｖｅｌｅｎｇｔｈ Ｌｉｍｉｔ（ｓ）はリンクｓにおける波長数の上限値、Ｌｉｎｋ（ｓ，ｈ）はＨＯＯＤＵルート候補ｈにリンクｓを含むか否かの識別子（値１は含む、値０は含まない）である。また、ｘ_ｈ１０（ｈ）の係数となる「８」は１０ＧｂｐｓのＨＯＯＤＵのトリビュータリスロット数つまり８×１．２５Ｇｂｐｓの帯域を表し、ｘ_ｈ１００（ｈ）の係数となる８０は１００ＧｂｐｓのＨＯＯＤＵのトリビュータリスロット数つまり８０×１．２５Ｇｂｐｓの帯域を表している。

この場合、目的関数は（１）式で表される。（１）式で、ＣＯＳＴ_ｈ１０は１０ＧｂｐｓのＨＯＯＤＵを使用するコスト、ＣＯＳＴ_ｈ１００は１００ＧｂｐｓのＨＯＯＤＵを使用するコストである。コストとはＨＯＯＤＵを使用するための費用であり、例えばＣＯＳＴ_ｈ１００はＣＯＳＴ_ｈ１０の数倍に設定される。また、定数であるＣＯＳＴ_ｈ１００，ＣＯＳＴ_ｈ１０は設計を行うときの状況により、どのように設定することも可能である。

（１）式は、生成される１０ＧｂｐｓのＨＯＯＤＵと１００ＧｂｐｓのＨＯＯＤＵの全体のコストが最小となることを表している。

制約条件は（２）式、（３）式、（４）式で表される。（２）式は各デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数であることを表す。（３）式は各ＨＯＯＤＵルート候補において、このＨＯＯＤＵルート候補を通る（もしくはＨＯＯＤＵルート候補に含まれる）デマンドＨＯＯＤＵルートパターン候補の帯域の総量が、帯域別に割当てられているＨＯＯＤＵの個数とＨＯＯＤＵの帯域との積和以下であることを表す。（４）式は各リンクにおいて、ＨＯＯＤＵの数がリンクの波長数制限値以下であることを表す。

なお、上記（１）〜（４）式では、ＨＯＯＤＵの帯域として１０Ｇｂｐｓ、１００Ｇｂｐｓの２種類を設定しているが、ＨＯＯＤＵの帯域はこれに限られるものではなく、１種類又は３種類以上であっても良い。

＜ビンパッキング作成及び解析処理＞
ステップＳ１６で実行する割当収容処理について説明する。ここで、簡単な例えとして、１００ＧｂｐｓのＨＯＯＤＵは大きな籠、１０ＧｂｐｓのＨＯＯＤＵは小さな籠、デマンドがリンゴだとした場合、限られた籠の容積の中に、どのようにうまくリンゴを収納するかを決定する。これは単純なビンパッキング問題であるため、これを解くための既存の手法、すなわち、数理計画法を用いても対応可能であるし、既存のヒューリスチックな手法（貪欲法等）で対応することも対応可能である。

ビンパッキングにおける目的関数と制約条件を以下に示す。また、ビンパッキングモデルで使用する変数の一覧を図１０に示す。図１０において、ｘはデマンドの番号、ｙはＨＯＯＤＵの番号、ｓ（ｘ，ｙ）はデマンドｘがＨＯＯＤＵｙに格納されるか否かの識別子（値１は格納される、値０は格納されない）、ＨＯＯＤＵ（ｙ）はＨＯＯＤＵｙが使用されるか否かの識別子（値１は使用される、値０は使用されない）、Ｄｅｍａｎｄ＿Ｃａｐ（ｘ）はデマンドｘの帯域、Ｄｅｍａｎｄ＿Ｎｕｍ（ｘ）は現在のＨＯＯＤＵルート候補に割当てられたデマンドｘの本数、ＨＯＯＤＵ＿Ｃａｐ（ｙ）はＨＯＯＤＵｙの容量、Ｍは例えば１００００等の十分に大きな数である。

この場合、目的関数は（５）式で表される。（５）式は、使用するＨＯＯＤＵの数が最小となることを表している。制約条件は（６）式、（７）式、（８）式で表される。（６）式はデマンドｘがいずれかのＨＯＯＤＵｙに収容されることを表す。（７）式はＨＯＯＤＵに格納されるデマンドの総帯域がＨＯＯＤＵの容量以下であることを表す。（８）式はどれか１つでもデマンドが収容されるＨＯＯＤＵは、そのＨＯＯＤＵを「使用する」とみなすことを表す。

本実施形態では、デマンド収容設計をデマンド分布から各ＨＯＯＤＵルートの各帯域のＨＯＯＤＵ数を見積るステップＳ１５と、デマンドを具体的なＨＯＯＤＵに配置するステップＳ１６に分離している。更に、ステップＳ１５の前処理において候補取得の際に工夫することで、余計な変数を抑制しつつ数理計画モデルを生成することを可能としている。このため、計算時間を従来方法に比べて削減でき、また、光ネットワーク全体におけるコストが最小となる最適な解を取得できる。

なお前述の既知の手法を基にしたヒューイスティック手法と、本実施形態の手法を比較した結果を図１１に示す。また、この比較のために使用した光ネットワークの構成を図１２に示す。なお、ヒューイスティック手法とは、複数のデマンドのうち、始点と終点が同一のデマンドをまとめてＨＯＯＤＵを生成する。その後、残りのデマンドを短いデマンドから順に、帯域に余裕のあるＨＯＯＤＵに収容し、帯域に余裕のあるＨＯＯＤＵがなければ新たにＨＯＯＤＵを生成して収容する方法である。

図１２において、光ネットワークはノードＮ１〜Ｎ２８で構成されている。ノード間を結ぶ直線で示すリンクに付した数字はノード間距離［ｋｍ］を示している。図１１において、横軸はデマンドの始終点対の数で、縦軸はＨＯＯＤＵの数である。破線Ｉａはヒューイスティック手法によるＨＯＯＤＵの数の変化を示し、実線Ｉｂは本実施形態によるＨＯＯＤＵの数の変化を示している。本実施形態ではヒューイスティック手法に対し、デマンドの始終点対の数が多くなるほどＨＯＯＤＵの数を減少することができ、デマンドの始終点対の数が３５０付近では本実施形態はヒューイスティック手法に対しＨＯＯＤＵの数を３０％以上削減でき、その分だけＨＯＯＤＵのコストを削減することができる。
（付記１）
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
を有することを特徴とするデマンド収容設計システム。
（付記２）
付記１記載のデマンド収容設計システムにおいて、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段を
有することを特徴とするデマンド収容設計システム。
（付記３）
付記２記載のデマンド収容設計システムであって、
前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計システム。
（付記４）
付記３記載のデマンド収容設計システムであって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計システム。
（付記５）
付記４記載のデマンド収容設計システムであって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計システム。
（付記６）
付記５記載のデマンド収容設計システムであって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計システム。
（付記７）
付記２乃至６のいずれか１項記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
（付記８）
付記７記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記デマンドの経路上に３本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
（付記９）
付記８記載のデマンド収容設計システムであって、
前記抽出手段は、更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計システム。
（付記１０）
付記９記載のデマンド収容設計システムであって、
前記抽出手段は、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
（付記１１）
付記１０記載のデマンド収容設計システムであって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計システム。
（付記１２）
光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計方法であって、
前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ制約条件を採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得し、
取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する、
ことを特徴とするデマンド収容設計方法。
（付記１３）
付記１２記載のデマンド収容設計方法において、
前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する
ことを特徴とするデマンド収容設計方法。
（付記１４）
付記１３記載のデマンド収容設計方法であって、
前記目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の数との積を加算した値の前記光パス候補数分の総和を最小化することである
ことを特徴とするデマンド収容設計方法。
（付記１５）
付記１４記載のデマンド収容設計方法であって、
前記制約条件は、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である
ことを特徴とするデマンド収容設計方法。
（付記１６）
付記１５記載のデマンド収容設計方法であって、
前記制約条件は、更に、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の光パスの個数と光パスの帯域との積和以下である
ことを特徴とするデマンド収容設計方法。
（付記１７）
付記１６記載のデマンド収容設計方法であって、
前記制約条件は、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である
ことを特徴とするデマンド収容設計方法。
（付記１８）
付記１３乃至１７のいずれか１項記載のデマンド収容設計方法であって、
前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
（付記１９）
付記１８記載のデマンド収容設計方法であって、
更に、前記デマンドの経路上に３本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
（付記２０）
付記１９記載のデマンド収容設計方法であって、
更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
ことを特徴とするデマンド収容設計方法。
（付記２１）
付記２０記載のデマンド収容設計方法であって、
更に、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計方法。
（付記２２）
付記２１記載のデマンド収容設計方法であって、
前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
ことを特徴とするデマンド収容設計方法。

１１ 入力装置
１２ 出力装置
１３ ドライブ装置
１４ 補助記憶装置
１５ メモリ装置
１６ 演算処理装置
１７ データベース
１８ システムバス
１９ 記憶媒体

Claims (13)

1. 光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計システムであって、
   前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、少なくとも前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ条件を制約条件として採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得する解析手段と、
   取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容する割当手段と、
   前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出する抽出手段と、
   を有し、
   前記解析手段における目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の信号転送用フレームの使用個数との積を加算した値の前記抽出手段で抽出された光パス候補の数分の総和を最小化することである
   ことを特徴とするデマンド収容設計システム。
2. 請求項１記載のデマンド収容設計システムであって、
   前記制約条件は、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の前記光パス候補の信号転送用フレームの個数と前記光パス候補の帯域との積和以下である条件である
   ことを特徴とするデマンド収容設計システム。
3. 請求項２記載のデマンド収容設計システムであって、
   前記制約条件として、更に、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である条件を加える
   ことを特徴とするデマンド収容設計システム。
4. 請求項３記載のデマンド収容設計システムであって、
   前記制約条件として、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である条件を加える
   ことを特徴とするデマンド収容設計システム。
5. 請求項１乃至４のいずれか１項記載のデマンド収容設計システムであって、
   前記抽出手段は、前記デマンドの始点ノードから終点ノードまでの信号伝送の経路を前記光パス候補として抽出する
   ことを特徴とするデマンド収容設計システム。
6. 請求項５記載のデマンド収容設計システムであって、
   前記抽出手段は、更に、前記デマンドの経路上に３本以上のリンクを有するノードであるハブサイトが存在する場合、前記始点ノード又は前記終点ノードと前記ハブサイト間、及び前記ハブサイト間を連結するルートを前記光パス候補として抽出する
   ことを特徴とするデマンド収容設計システム。
7. 請求項６記載のデマンド収容設計システムであって、
   前記抽出手段は、更に、前記始点ノードと前記終点ノードそれぞれに最も近いハブサイト間を連結するルートを前記光パス候補として抽出する
   ことを特徴とするデマンド収容設計システム。
8. 請求項７記載のデマンド収容設計システムであって、
   前記抽出手段は、抽出された前記光パス候補又は前記抽出された前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶパターンを前記光パスパターン候補として抽出する
   ことを特徴とするデマンド収容設計システム。
9. 請求項８記載のデマンド収容設計システムであって、
   前記抽出手段は、前記デマンドの始点ノードと終点ノードを結ぶパターンのうち前記光パス候補を乗換える回数が予め決められた一定回数以下である場合に前記光パスパターン候補として抽出する
   ことを特徴とするデマンド収容設計システム。
10. 光ネットワーク内で始点ノードから終点ノードまでの信号伝送の経路を指定するデマンドを光パスに収容するデマンド収容設計方法であって、
    前記デマンドを構成する光パスの候補である光パス候補の帯域別のコストを組み込んだ目的関数と、少なくとも前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補の帯域と前記光パス候補の帯域を組み込んだ条件を制約条件として採用した数理計画問題を解くことで、コストを最小化する光パス候補を取得し、
    取得された前記コストを最小化する光パス候補に前記デマンドを割当てて収容し、
    前記デマンドから、前記デマンドを構成する光パスの候補である光パス候補と、前記光パス候補を組み合わせて前記デマンドの始点ノードと終点ノードを結ぶ光パスパターン候補を抽出し、
    前記目的関数は、前記光パス候補の帯域毎に前記光パス候補のコストと前記光パス候補の信号転送用フレームの使用個数との積を加算した値の前記デマンドから抽出された光パス候補の数分の総和を最小化することである
    ことを特徴とするデマンド収容設計方法。
11. 請求項１０記載のデマンド収容設計方法であって、
    前記制約条件は、前記光パス候補を通る光パスパターン候補の帯域の総量が、帯域別の前記光パス候補の信号転送用フレームの個数と前記光パス候補の帯域との積和以下である条件である
    ことを特徴とするデマンド収容設計方法。
12. 請求項１１記載のデマンド収容設計方法であって、
    前記制約条件として、更に、前記デマンドで選択される光パスパターン候補の総数がデマンドの総数と同数である条件を加える
    ことを特徴とするデマンド収容設計方法。
13. 請求項１２記載のデマンド収容設計方法であって、
    前記制約条件として、更に、各リンクにおける前記光パス候補の数が波長数制限値以下である条件を加える
    ことを特徴とするデマンド収容設計方法。

Images