光ネットワーク設計装置および光ネットワーク設計方法
【課題】光ネットワークの設計において適切な経路結果を得ることができるようにする。
【解決手段】経路算出部１は、非対称光ハブのコネクション制限数に依存せずに光ネットワークにおけるトラフィックパスを仮設計する。余裕算出部２は、仮設計されたトラフィックパスのペナルティ制限に対するペナルティ余裕を算出する。追加算出部３は、非対称光ハブごとにおいてポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する。情報生成部４は、迂回経路に非対称光ハブが含まれる場合、非対称光ハブに関する非対称光ハブ情報を生成する。制約条件生成部５は、コネクション制限数、ペナルティ余裕、追加ペナルティ、および非対称光ハブ情報に基づきコネクション制限数とペナルティ制限とを満たすトラフィックパスが採用されるための制約条件を生成する。経路算出部６は、制約条件に基づき数理計画法によりトラフィックパスを算出する。
【解決手段】経路算出部１は、非対称光ハブのコネクション制限数に依存せずに光ネットワークにおけるトラフィックパスを仮設計する。余裕算出部２は、仮設計されたトラフィックパスのペナルティ制限に対するペナルティ余裕を算出する。追加算出部３は、非対称光ハブごとにおいてポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する。情報生成部４は、迂回経路に非対称光ハブが含まれる場合、非対称光ハブに関する非対称光ハブ情報を生成する。制約条件生成部５は、コネクション制限数、ペナルティ余裕、追加ペナルティ、および非対称光ハブ情報に基づきコネクション制限数とペナルティ制限とを満たすトラフィックパスが採用されるための制約条件を生成する。経路算出部６は、制約条件に基づき数理計画法によりトラフィックパスを算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、光ネットワークの経路設計を行う光ネットワーク設計装置および光ネットワーク設計方法に関する。
【背景技術】
【０００２】
近年、光ネットワーク分野では、光信号のまま波長単位で光信号の分岐挿入や経路切換えを行う光分岐挿入装置（ＯＡＤＭ：Optical Add-Drop Multiplexer）や波長クロスコネクト（ＷＸＣ：Wavelength Cross Connect）装置等が開発されている。このような光装置によって光ネットワークは、リング相互接続、メッシュ等といった複雑なトポロジを持つネットワーク構築が可能となり、ネットワーク規模の拡大化が進んでいる。
【０００３】
なお、従来、ＷＤＭ（Wavelength Division Multiplexing）方式とＡＷＧ（Arrayed Waveguide Grating）を用いて複数のノード間をＨＣＮ（HyperCube Network）接続するＨＣＮにおいて、容易かつ安価にネットワークの大規模化を可能にする波長多重ネットワークが提案されている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−６０９２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、光ネットワークの規模拡大化にともない、光ハブ局舎ではコネクション制限が生じる場合が多くなってきている。そのため、光ネットワークの経路設計を行う光ネットワーク設計装置は、光ネットワークの規模拡大化において適切な経路結果が得られない場合があるという問題点があった。
【０００６】
本件はこのような点に鑑みてなされたものであり、適切な経路結果を得ることができる光ネットワーク設計装置および光ネットワーク設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置が提供される。この光ネットワーク設計装置は、前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出部と、前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出部と、前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成部と、前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、を有する。
【０００８】
また、上記課題を解決するために、複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置が提供される。この光ネットワーク設計装置は、前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成部と、前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成部と、前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、を有する。
【発明の効果】
【０００９】
開示の装置および方法によれば、適切な経路結果を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】第１の実施の形態に係る光ネットワーク設計装置を示した図である。
【図２】第２の実施の形態に係る光ネットワーク設計装置のハードウェア構成例を示した図である。
【図３】経路設計が行われる光ネットワークの例を示した図である。
【図４】ハブ局舎を説明する図である。
【図５】非対称光ハブ局舎を説明する図である。
【図６】非対称光ハブ局舎の詳細例を示した図である。
【図７】光ネットワーク設計装置の機能ブロック図である。
【図８】ペナルティ余裕を説明する図である。
【図９】コネクションマトリクスＴＢのデータ構成例を示した図である。
【図１０】置換ポートを説明する図である。
【図１１】ポートマトリクスＴＢのデータ構成例を示した図である。
【図１２】変数を説明する図である。
【図１３】制約観点Ａに基づく制約条件を説明する図である。
【図１４】制約観点Ｂに基づく制約条件を説明する図である。
【図１５】複数のＡ−Ｈｕｂを通過する経路を優先的に採用する目的関数を説明する図である。
【図１６】光ネットワーク設計装置の処理動作を示したフローチャートである。
【図１７】削除コネクションを選定して経路算出を行う方法の経路算出イメージを示した図である。
【図１８】数理計画法による経路算出イメージを示した図である。
【図１９】第３の実施の形態に係る両ポート制約を説明する図である。
【図２０】光ネットワーク設計装置の処理動作を示したフローチャートである。
【図２１】第４の実施の形態に係る光ネットワーク設計装置の機能ブロック図である。
【図２２】ポートマトリクスの生成を説明する図である。
【図２３】ポートマトリクスＴＢのデータ構成例を示した図である。
【図２４】第５の実施の形態に係る代替経路を説明する図である。
【図２５】最短経路探索法によって経路算出する光ネットワークの例を示した図である。
【図２６】デマンドを示した図である。
【図２７】数理計画法によって経路算出する光ネットワークの例を示した図である。
【図２８】数理計画法によって経路算出した結果を示した図である。
【発明を実施するための形態】
【００１１】
以下、実施の形態を、図面を参照して詳細に説明する。
［第１の実施の形態］
図１は、第１の実施の形態に係る光ネットワーク設計装置を示した図である。図１に示すように、光ネットワーク設計装置は、経路算出部１，６、余裕算出部２、追加算出部３、情報生成部４、および制約条件生成部５を有している。
【００１２】
経路算出部１は、非対称光ハブのコネクション制限数に依存せずに光ネットワークにおけるトラフィックパスを仮設計する。
余裕算出部２は、経路算出部１によって仮設計されたトラフィックパスのペナルティ制限に対するペナルティ余裕を算出する。ペナルティ制限とは、例えば、トラフィックパスに認められるホップ数や伝送遅延量である。
【００１３】
追加算出部３は、非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する。
情報生成部４は、迂回経路に非対称光ハブが含まれる場合、迂回経路に含まれている非対称光ハブに関する非対称光ハブ情報を生成する。例えば、情報生成部４は、迂回経路に含まれている非対称光ハブの迂回経路が通過するコネクション情報を生成する。
【００１４】
制約条件生成部５は、コネクション制限数、余裕算出部２によって算出されたペナルティ余裕、追加算出部３によって算出された追加ペナルティ、および情報生成部４によって生成された非対称光ハブ情報に基づいて、コネクション制限数とペナルティ制限とを満たすトラフィックパスが採用されるための制約条件を生成する。
【００１５】
経路算出部６は、制約条件生成部５によって生成された制約条件に基づいて、数理計画法によりトラフィックパスを算出する。
このように、光ネットワーク設計装置は、コネクション制限数、ペナルティ余裕、追加ペナルティ、および非対称光ハブ情報に基づいて、コネクション制限数とペナルティ制限とを満たすトラフィックパスが採用されるための制約条件を生成する。そして、光ネットワーク設計装置は、生成した制約条件に基づいて、数理計画法により最終的なトラフィックパスを算出するようにした。これにより、光ネットワーク設計装置は、適切な経路結果を得ることができる。例えば、コネクション制限数およびペナルティ制限を満たす経路結果を得ることができる。
【００１６】
［第２の実施の形態］
次に、第２の実施の形態を、図面を参照して詳細に説明する。
図２は、第２の実施の形態に係る光ネットワーク設計装置のハードウェア構成例を示した図である。光ネットワーク設計装置１０は、ＣＰＵ（Central Processing Unit）１１によって装置全体が制御されている。ＣＰＵ１１には、バス１８を介してＲＡＭ（Random Access Memory）１２と複数の周辺機器が接続されている。
【００１７】
ＲＡＭ１２は、光ネットワーク設計装置１０の主記憶装置として使用される。ＲＡＭ１２には、ＣＰＵ１１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。例えば、ＲＡＭ１２には、光ネットワークの経路設計を行うアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１２には、ＣＰＵ１１による処理に必要な各種データが格納される。
【００１８】
バス１８に接続されている周辺機器としては、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１３、グラフィック処理装置１４、入力インタフェース１５、光学ドライブ装置１６、および通信インタフェース１７がある。
【００１９】
ＨＤＤ１３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１３は、光ネットワーク設計装置１０の二次記憶装置として使用される。ＨＤＤ１３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００２０】
グラフィック処理装置１４には、モニタ１９が接続されている。グラフィック処理装置１４は、ＣＰＵ１１からの命令に従って、画像をモニタ１９の画面に表示させる。モニタ１９としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００２１】
入力インタフェース１５には、キーボード２０とマウス２１とが接続されている。入力インタフェース１５は、キーボード２０やマウス２１から送られてくる信号をＣＰＵ１１に送信する。なお、マウス２１は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００２２】
光学ドライブ装置１６は、レーザ光などを利用して、光ディスク２２に記録されたデータの読み取りを行う。光ディスク２２は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２２には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００２３】
通信インタフェース１７は、例えば、インターネットなどのネットワークに接続されている。通信インタフェース１７は、ネットワークを介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００２４】
以上のようなハードウェア構成によって、光ネットワーク設計装置１０は光ネットワークの経路設計を行うための処理機能を実現することができる。
図３は、経路設計が行われる光ネットワークの例を示した図である。図３に示す光ネットワークは、光ハブ局舎３１，４１ａ〜４５ａ，４１ｂ〜４５ｂと、その他丸で示す複数の光ハブ局舎とによって形成されている。光ハブ局舎３１は、ポートＰ０〜Ｐ５を有し、その他の光ハブ局舎も同様にポートを有している。
【００２５】
光ネットワーク設計装置１０は、光ネットワークを形成している光ハブ局舎のトポロジ情報を記憶している。トポロジ情報は、例えば、キーボード２０、マウス２１、および光ディスク２２のいずれかによって光ネットワーク設計装置１０のＨＤＤ１３に記憶することができる。また、光ネットワーク設計装置１０は、通信インタフェース１７によって光ネットワークの光ハブ局舎と通信し、光ハブ局舎からトポロジ情報を取得してＨＤＤ１３に記憶することもできる。
【００２６】
トポロジ情報には、光ハブ局舎情報、スパン情報、およびデマンド情報が含まれている。
光ハブ局舎情報には、光ハブ局舎のポート数（光ハブ局舎から出ているスパン数）、光ハブ局舎が非対称光ハブ局舎である場合にはその旨の情報とコネクション制限数（非対称光ハブ局舎およびコネクション制限数については以下で説明する）、およびコネクションの伝送遅延やコスト等の最短経路計算に必要なパラメータが含まれている。
【００２７】
スパン情報には、スパンの両端の光ハブ局舎、およびスパンの伝送遅延やコスト等の最短経路計算に必要なパラメータが含まれている。
デマンド情報には、オペレータが経路設計要求するトラフィックパスの起点および終点の光ハブ局舎の情報が含まれている。
【００２８】
光ネットワーク設計装置１０は、オペレータからの要求に応じて、デマンド（ある光ハブ局舎からある光ハブ局舎へのトラフィックパス）を設計（算出）する。
例えば、光ネットワーク設計装置１０は、オペレータから光ハブ局舎４１ａ，４１ｂを起点および終点とするデマンド、光ハブ局舎４２ａ，４２ｂを起点および終点とするデマンド、…、光ハブ局舎４５ａ，４５ｂを起点および終点とするデマンドの経路を算出するよう要求されたとする。この場合、光ネットワーク設計装置１０は、例えば、図３に示す経路Ｄ１１〜Ｄ１５を算出する。算出された経路Ｄ１１〜Ｄ１５は、例えば、モニタ１９に表示される。
【００２９】
図４は、ハブ局舎を説明する図である。図４に示す光ハブ局舎５１は、ポートＰ０〜Ｐ５を有している。光ハブ局舎５１は、ポートＰ０〜Ｐ５にコネクション制限数がないとする。
【００３０】
この場合、光ハブ局舎５１は、図４に示すようにポートＰ０〜Ｐ５のそれぞれにおいて、他のポートＰ０〜Ｐ５とフルメッシュでコネクションを張ることが可能である。
従って、例えば、図３に示す光ハブ局舎３１にコネクション制限がないとすると、図３の光ハブ局舎３１は、ポートＰ０とポートＰ１〜Ｐ５との間にコネクションを張ることができるので、光ネットワーク設計装置１０は、図３に示す経路Ｄ１１〜Ｄ１５を算出することができる。
【００３１】
図５は、非対称光ハブ局舎を説明する図である。図５に示す光ハブ局舎５２は、ポートＰ０〜Ｐ５を有している。図５に示す光ハブ局舎５２では、コネクション制限数は４であるとする。
【００３２】
この場合、光ハブ局舎５２は、コネクション制限数が４であるので、１つのポートから４つのコネクションしか張ることができない。よって、図５に示すように、ポートＰ０と、ポートＰ１〜Ｐ４との間にコネクションが張られる場合、ポートＰ０−Ｐ５ではコネクションを張ることができない。
【００３３】
従って、例えば、図３に示す光ハブ局舎３１が非対称光ハブ局舎であり、コネクション制限４であるとすると、図３の光ハブ局舎３１は、ポートＰ０とポートＰ１〜Ｐ５との間にコネクションを張ることができない。そのため、光ネットワーク設計装置１０は、図３に示す経路Ｄ１１〜Ｄ１５を算出することができない。光ネットワーク設計装置１０は、例えば、ポートＰ０とポートＰ１〜Ｐ５との間のコネクションの１つを迂回するように設計することになる。
【００３４】
なお、コネクション数が制限されている光ハブ局舎は、非対称光ハブ局舎と呼ばれる。図５の光ハブ局舎５２は、非対称光ハブ局舎である。以下では、非対称光ハブ局舎をＡ−Ｈｕｂ（Asymmetric-Hub）と呼ぶこともある。
【００３５】
図６は、非対称光ハブ局舎の詳細例を示した図である。図６には、図５に示した光ハブ局舎５２の詳細例が示してある。光ハブ局舎５２は、ＷＳＳ（Wavelength Selective Switch）５２ａａ〜５２ａｆ，５２ｂａ〜５２ｂｆを有している。光ハブ局舎５２は、例えば、ラックを有しており、ラックのシェルフにＷＳＳ５２ａａ〜５２ａｆ，５２ｂａ〜５２ｂｆの基板を搭載している。
【００３６】
図６に示すポートＰ０〜Ｐ５は、図５で示したポートＰ０〜Ｐ５に対応する。図６では、ポートＰ０〜Ｐ５がそれぞれ２つ存在しているが、これは、図６では、ポートＰ０〜Ｐ５の入出力を別々に示しているからである。
【００３７】
図５で説明したように光ハブ局舎５２のコネクション制限数は４であるとする。この場合、光ネットワーク設計装置１０は、例えば、図６の点線で示すように、５本目のデマンドに対するコネクションを設定することができない。
【００３８】
従来の光ネットワークは規模が小さく、コネクション制限違反をするような経路設計が生じることは少なかった。しかし、光ネットワークの規模は近年拡大し、経路設計するデマンド数も増大している。そのため、デマンドの経路算出の際に設定されるコネクション数も増大し、例えば、図５の点線で示すコネクションを要する場合も生じてくる。このように、光ネットワーク規模が大きくなってトポロジ情報が複雑になり、さらにコネクション制限の光ハブ局舎が多くなると、経路計算に時間がかかる。例えば、１つのデマンドの経路を算出するごとに、コネクション制限違反を判断し、コネクション制限違反が生じれば、そのデマンドに対して再計算を行っていく方法では、経路計算に時間がかかる。
【００３９】
これに対し、ＷＳＳ５２ａａ〜５２ａｆ，５２ｂａ〜５２ａｆの出力ポート数を大きくして（コネクション制限数を大きくして）、コネクション制限違反を生じないようにすることが考えられる。しかし、ＷＳＳのコスト等を考慮すると、ＷＳＳ５２ａａ〜５２ａｆ，５２ｂａ〜５２ｂｆの出力ポート数を大きくすることは望ましくない。
【００４０】
そこで、光ネットワーク設計装置１０は、非対称光ハブ局舎を含む、規模拡大された光ネットワークにおいても、経路設計時間を短縮する。また、光ネットワーク設計装置１０は、光ネットワーク全体で最適化された（以下で述べる制約条件を満たす）経路結果を得るようにする。
【００４１】
図７は、光ネットワーク設計装置の機能ブロック図である。図７に示すように、光ネットワーク設計装置１０は、トポロジ情報記憶部６１、経路算出部６２、経路情報記憶部６３、コネクションマトリクス生成部６４、コネクションマトリクスＴＢ（ＴＢ：Table）６５、ポートマトリクス生成部６６、ポートマトリクスＴＢ６７、制約条件生成部６８、および経路算出部６９を有している。
【００４２】
トポロジ情報記憶部６１には、図３で説明したトポロジ情報が記憶されている。
経路算出部６２は、例えば、ダイクストラ法などの最短経路探索法に基づき、トポロジ情報記憶部６１に記憶されているトポロジ情報を参照して、Ａ−Ｈｕｂのコネクション制限を考慮せずにデマンドの経路を算出する。経路算出部６２は、Ａ-Ｈｕｂにコネクション制限がないものとして、オペレータのデマンドに対する経路を算出する。経路算出部６２は、算出したデマンドの経路を経路情報記憶部６３に記憶する。経路算出部６２は、例えば、図１の経路算出部１に対応する。
【００４３】
コネクションマトリクス生成部６４は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してコネクションマトリクスを生成し、コネクションマトリクスＴＢ６５に記憶する。コネクションマトリクス生成部６４は、光ネットワークに含まれている全てのＡ−Ｈｕｂにおいてコネクションマトリクスを生成し、コネクションマトリクスＴＢ６５に記憶する。コネクションマトリクス生成部６４は、例えば、図１の余裕算出部２に対応する。
【００４４】
コネクションマトリクスＴＢ６５について説明する。その前に、ペナルティ制限およびペナルティ余裕について説明する。
経路算出しようとするデマンドには、予めペナルティ制限が設定される。ペナルティ制限とは、例えば、経路算出しようとするデマンドに認められるハブ局舎のホップ数や伝送遅延量である。ペナルティ余裕とは、経路算出されたデマンドのペナルティのペナルティ制限に対する余裕値である。
【００４５】
図８は、ペナルティ余裕を説明する図である。図８には、光ネットワークを形成しているＡ−Ｈｕｂ７１ａが示してある。Ａ−Ｈｕｂ７１ａは、ポートＰ０〜Ｐ８を有している。
【００４６】
また、図８には、フルメッシュでコネクションを張ることができる通常のＨｕｂ７１ｂ，７１ｃが示してある。図８に示す丸（ポートＰ０〜Ｐ８は除く）もＨｕｂを示している。また、図８には、経路７１ｄおよび経路７１ｅが示してある。経路７１ｄは、デマンドＤ２１に対する経路、経路７１ｅは、デマンドＤ２２に対する経路とする。また、図８には、Ｈｕｂ７１ｂとポートＰ４に接続されているＨｕｂとを結ぶ経路７１ｆが示してある。
【００４７】
デマンドＤ２１，Ｄ２２のペナルティ制限は、１０であるとする。また、デマンドＤ２１の経路７１ｅのペナルティは、経路算出部６２の経路算出結果により、４であったとする。また、デマンドＤ２２の経路７１ｄのペナルティは、７であったとする。この場合、デマンドＤ２１のペナルティ余裕は、１０−４より６となる。また、デマンドＤ２２のペナルティ余裕は、１０−７より３となる。
【００４８】
すなわち、ペナルティ制限は、デマンド経路に許されるペナルティ値を示している。ペナルティ余裕は、デマンド経路のペナルティのペナルティ制限に対する余裕値を示している。
【００４９】
コネクションマトリクスは、Ａ−Ｈｕｂを通過するデマンドのペナルティ余裕を示す情報である。コネクションマトリクス生成部６４は、経路算出部６２によって経路算出が行われた後、光ネットワークを形成しているＡ−Ｈｕｂの１つに着目する。コネクションマトリクス生成部６４は、着目したＡ−Ｈｕｂのコネクションごとに、Ａ−Ｈｕｂを通過するデマンドのペナルティ余裕を算出し、コネクションマトリクスＴＢ６５に記憶する。
【００５０】
コネクションマトリクス生成部６４は、Ａ−Ｈｕｂのコネクションに、複数のデマンドの経路が通過する場合には、最も小さいペナルティ余裕をコネクションマトリクスＴＢ６５に記憶する。コネクションマトリクス生成部６４は、光ネットワークを形成している全てのＡ−Ｈｕｂにおいてペナルティ余裕を算出し、コネクションマトリクスＴＢ６５に記憶する。
【００５１】
図９は、コネクションマトリクスＴＢのデータ構成例を示した図である。図９に示すように、コネクションマトリクスＴＢ６５は、縦方向および横方向にポートの欄を有している。縦方向のポートと横方向のポートは、その２つのポートでＡ−Ｈｕｂのコネクションを示す。
【００５２】
例えば、図９のコネクションマトリクスＴＢ６５は、図８のＡ−Ｈｕｂ７１ａのコネクションマトリクスを示しているとする。図９の縦方向のポートＰ５と横方向のポートＰ１は、図８のＡ−Ｈｕｂ７１ａのポートＰ１−Ｐ５のコネクションを示す。
【００５３】
横方向のポートと縦方向のポートとの交わる欄には、そのコネクションを通過しているデマンドのペナルティ余裕が記憶される。コネクションに複数のデマンドが通過している場合には、最小のペナルティ余裕が記憶される。
【００５４】
例えば、図８の例の場合、ポートＰ１−Ｐ５のコネクションに、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅが通過している。デマンドＤ２１，Ｄ２２のそれぞれのペナルティ余裕は、上記より６，３である。従って、図９に示すように、縦方向のポートＰ５と横方向のポートＰ１の欄には、ペナルティ余裕の最も小さい３が記憶される。
【００５５】
また、コネクションマトリクスＴＢ６５には、コネクションを通過しているデマンドの共通経路端のＨｕｂ情報が記憶される。
例えば、図８では、ポートＰ１−Ｐ５のコネクションに、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅが通過している。経路７１ｄ，７１ｅの共通経路端のＨｕｂは、Ｈｕｂ７１ｂ，７１ｃである。Ｈｕｂ７１ｂ，７１ｃの識別子を、例えば、Ｓ，Ｔとすると、コネクションマトリクスＴＢ６５の縦方向のポートＰ５と横方向のポートＰ１との交わる欄には、図９に示すようにＳ，Ｔが記憶される。なお、コネクションを通過しているデマンドの経路が１つの場合、その共通経路端は、デマンドの始点と終点のＨｕｂとなる。
【００５６】
以上より、コネクションマトリクスＴＢ６５は、経路算出部６２によって算出されたデマンド経路のペナルティ制限に対する余裕値を示し、Ａ−Ｈｕｂのコネクションを通過しているデマンド経路を迂回経路に迂回させる場合の、迂回経路で許すことのできるペナルティの最大値を示している。
【００５７】
例えば、経路算出部６２が光ネットワークの経路算出を行ったとする。その結果、図８に示すように、デマンドＤ２１，Ｄ２２の経路として、経路７１ｄ，７１ｅが算出され、かつ、Ａ−Ｈｕｂ７１ａのポートＰ１がコネクション制限違反であったとする。この場合、ポートＰ１のコネクション違反は、例えば、ポートＰ１−Ｐ５のコネクションを通過しているデマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅを、経路７１ｆによってポートＰ４に迂回させ（ポートＰ１をポートＰ４に置換させ）、ポートＰ４−Ｐ５にコネクションを張ることによって回避できる。
【００５８】
ここで、ポートＰ１−Ｐ５のコネクションを通過していたデマンドＤ２１，Ｄ２２のペナルティ余裕は、コネクションマトリクスＴＢ６５を参照することにより、最大３であることが分かる。これにより、迂回経路で許されるペナルティは、最大３であることが分かる。
【００５９】
従って、経路７１ｆのペナルティが３以下であれば、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅを、経路７１ｆおよびポートＰ４−Ｐ５に迂回させることができる。つまり、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅを経路７１ｆに迂回させても、経路７１ｄ，７１ｅのペナルティ制限は守られる。
【００６０】
図７の説明に戻る。ポートマトリクス生成部６６は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してポートマトリクスを生成し、ポートマトリクスＴＢ６７に記憶する。ポートマトリクス生成部６６は、光ネットワークに含まれている全てのＡ−Ｈｕｂにおいてポートマトリクスを生成し、ポートマトリクスＴＢ６７に記憶する。
【００６１】
ポートマトリクスＴＢ６７について説明する。その前に、Ａ−Ｈｕｂのポートの置換ポートについて説明する。
ポートマトリクス生成部６６は、経路算出部６２によって経路算出が行われた後、光ネットワークを形成しているＡ−Ｈｕｂの１つに着目する。ポートマトリクス生成部６６は、着目したＡ−Ｈｕｂの各ポートにおいて、置換ポートを算出する。置換ポートとは、Ａ−Ｈｕｂを通過する経路のポートを、そのＡ−Ｈｕｂの別のポートに置き換えることができるポートをいう。ポートマトリクス生成部６６は、例えば、図１の追加算出部３および情報生成部４に対応する。
【００６２】
図１０は、置換ポートを説明する図である。図１０には、光ネットワークを形成しているＡ−Ｈｕｂ７２ａが示してある。Ａ−Ｈｕｂ７２ａは、ポートＰ０〜Ｐ８を有している。
【００６３】
また、図１０には、Ｈｕｂ７２ｂ，７２ｃ，７２ｅ，７２ｇが示してある。また、図１０には、Ａ−Ｈｕｂ７２ｄ，７２ｆが示してある。Ａ−Ｈｕｂ７２ｄ，７２ｆの識別子は、例えば、それぞれＸ，Ｙとする。
【００６４】
置換ポートを見つけるには、まず、着目しているＡ−Ｈｕｂに最も近いＨｕｂに着目する。例えば、図１０の場合、Ａ−Ｈｕｂ７２ａに着目したとすると、Ｈｕｂ７２ｂ，７２ｃ，７２ｅ，７２ｇ、Ａ−Ｈｕｂ７２ｄ，７２ｆ、ポートＰ６に接続されているＨｕｂ、およびポートＰ７，Ｐ８に接続されているＨｕｂに着目する。
【００６５】
次いで、着目したＨｕｂの間を結ぶ経路が存在するか探索する。経路探索は、例えば、ダイクストラ法などの最短経路探索法を用いる。図１０の例の場合、例えば、Ｈｕｂ７２ｂ，７２ｃ間に経路が存在する。また、Ａ−Ｈｕｂ７２ｄを介して、Ｈｕｂ７２ｃ，７２ｅ間に経路が存在する。また、Ａ−Ｈｕｂ７２ｆを介して、Ｈｕｂ７２ｅ，７２ｇ間に経路が存在する。
【００６６】
着目したＨｕｂにそれらを結ぶ経路が存在する場合、着目したＨｕｂと接続されているＡ−Ｈｕｂのポートは、互いに置換ポートとなる。図１０の例では、例えば、Ａ−Ｈｕｂ７２ａのポートＰ１を、Ａ−Ｈｕｂ７２ａの別のポートに置き換えることができるポートは、ポートＰ０，Ｐ４，Ｐ５となる。すなわち、ポートＰ１の置換ポートは、ポートＰ０，Ｐ４，Ｐ５となる。
【００６７】
Ａ−Ｈｕｂのあるポートに置換ポートが存在するということは、ポート間に迂回経路が存在することを意味する。例えば、図１０において、ポートＰ１の置換ポートは、ポートＰ０，Ｐ４，Ｐ５であるので、ポートＰ１−Ｐ０、ポートＰ１−Ｐ４、およびポートＰ１−Ｐ５には迂回経路が存在している。
【００６８】
これにより、Ａ−Ｈｕｂのポートにコネクション制限違反が生じた場合、算出したデマンド経路を迂回経路に迂回させ、置換ポートを通過させることにより、コネクション制限違反が生じたポートのコネクション制限違反を解消することができる。
【００６９】
例えば、図１０において、経路算出部６２により、Ｈｕｂ７２ｃ、Ａ−Ｈｕｂ７２ａのポートＰ１，Ｐ５、およびＨｕｂ７２ｇを通過するデマンド経路が複数算出されたとする。また、ポートＰ１は、コネクション制限違反であるとする。この場合、例えば、算出された経路の一部を、Ｈｕｂ７２ｃ、Ａ−Ｈｕｂ７２ｄ、およびＨｕｂ７２ｅの迂回経路に通過させ、さらに、Ａ−Ｈｕｂ７２ａのポートＰ４−Ｐ５にコネクションを張ることにより、ポートＰ０のコネクション制限違反を解消できる。
【００７０】
ポートマトリクス生成部６６は、次のようにして置換ポートを算出する。ポートマトリクス生成部６６は、Ａ−Ｈｕｂ７２ａの各ポートＰ０−Ｐ８から最も近い（ホップ数の最も小さい）Ｈｕｂを取得し、取得したＨｕｂ間で、例えば、ダイクストラ法などの最短経路探索法を実行する。最短経路探索法で経路が見つかれば、そのＨｕｂと接続されているポートは、互いに置換ポートとなる。
【００７１】
例えば、図１０に示すＨｕｂ７２ｂ，７２ｃは、Ａ−Ｈｕｂ７２ａから最も近いＨｕｂである。ポートマトリクス生成部６６は、最短経路探索法でＨｕｂ７２ｂ，７２ｃ間の最短経路（迂回経路）を算出する。図１０の例では、Ｈｕｂ７２ｂ，７２ｃは直接接続されており、最短経路が求まる。従って、Ｈｕｂ７２ｂと接続されているポートＰ０の置換ポートは、ポートＰ１となる。また、Ｈｕｂ７２ｃと接続されているポートＰ１の置換ポートは、ポートＰ０となる。
【００７２】
同様に、図１０に示すＨｕｂ７２ｃ，７２ｅは、Ａ−Ｈｕｂ７２ａから最も近いＨｕｂである。ポートマトリクス生成部６６は、最短経路探索法でＨｕｂ７２ｃ，７２ｅ間の最短経路を算出する。図１０の例では、Ｈｕｂ７２ｃ，７２ｅは、Ａ−Ｈｕｂ７２ｄを介して接続されており、最短経路が求まる。従って、Ｈｕｂ７２ｃと接続されているポートＰ１の置換ポートは、ポートＰ４となる。また、Ｈｕｂ７２ｅと接続されているポートＰ４の置換ポートは、ポートＰ１となる。
【００７３】
また、図１０に示すＨｕｂ７２ｃと、Ａ−Ｈｕｂ７２ａのポートＰ２に接続されているＨｕｂは、Ａ−Ｈｕｂ７２ａから最も近いＨｕｂである。ポートマトリクス生成部６６は、最短経路探索法でＨｕｂ７２ｃとポートＰ２に接続されているＨｕｂ間の最短経路を算出する。図１０の例では、Ｈｕｂ７２ｃとポートＰ２に接続されているＨｕｂ間には、経路が存在しないため、最短経路は求まらない。従って、ポートＰ１，Ｐ２は、それぞれ置換ポートとならない。
【００７４】
図１１は、ポートマトリクスＴＢのデータ構成例を示した図である。図１１に示すように、ポートマトリクスＴＢ６７は、縦方向および横方向にポートの欄を有している。縦方向のポートは、対象ポートを示し、横方向のポートは、対象ポートの置換ポートを示している。なお、図１１のポートマトリクスＴＢ６７は、図１０に示すＡ−Ｈｕｂ７２ａのポートマトリクスＴＢを示している。
【００７５】
対象ポートと置換ポートとの交わる欄には、対象ポートと置換ポートを結ぶ迂回経路のペナルティが記憶される。以下では、迂回経路のペナルティを追加ペナルティと呼ぶこともある。
【００７６】
例えば、図１０において、Ａ−Ｈｕｂ７２ａの対象ポートＰ１と置換ポートＰ４を結ぶ迂回経路のペナルティは、２である（図１０ではＨｏｐ数で示している）。従って、図１１の対象ポートＰ１と置換ポートＰ４の交わる欄には、追加ペナルティ２が記憶されている。
【００７７】
また、対象ポートと置換ポートとの交わる欄には、対象ポートと置換ポートを結ぶ迂回経路にＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂの情報が記憶される。また、迂回経路が通過するＡ−Ｈｕｂのポート（コネクション）情報が記憶される。
【００７８】
例えば、図１０において、Ａ−Ｈｕｂ７２ａの対象ポートＰ１と置換ポートＰ４を結ぶ迂回経路には、Ａ−Ｈｕｂ７２ｄが含まれる。従って、図１１の対象ポートＰ１と置換ポートＰ４の交わる欄には、Ａ−Ｈｕｂ７２ｄの情報（識別子Ｘ）が記憶されている。また、迂回経路は、Ａ−Ｈｕｂ７２ｄのポートＰ２，Ｐ３を通過している。従って、図１１の対象ポートＰ１と置換ポートＰ４の交わる欄には、ポートＰ２，Ｐ３の情報が記憶されている。
【００７９】
ポートマトリクス生成部６６は、上述した迂回経路の算出の際に、迂回経路の追加ペナルティを算出する。また、ポートマトリクス生成部６６は、上述した迂回経路の算出の際に、追加経路に含まれるＡ−Ｈｕｂの情報およびＡ−Ｈｕｂのポートの情報を算出する。そして、ポートマトリクス生成部６６は、図１１に示すようなポートマトリクスＴＢ６７を生成する。
【００８０】
以上より、ポートマトリクスＴＢ６７は、Ａ−Ｈｕｂを通過しているデマンド経路が通過しているポートを、別のポートに置き換えることができるポート（置換ポート）の情報を記憶している。また、ポートマトリクスＴＢ６７は、ポートを置換ポートに置き換えたときの迂回経路に生じるペナルティ（追加ペナルティ）を記憶している。これにより、例えば、ポートＰ０は、ポートマトリクスＴＢ６７を参照することにより、ポートＰ１，Ｐ４，Ｐ５のいずれかに置き換えることができることが分かる。また、このポート置き換えを行うには、それぞれ、ペナルティ１，３，５の迂回経路を経由することが分かる。また、ポートＰ０をポートＰ５に置き換える場合には、迂回経路に識別子Ｘ，ＹのＡ−Ｈｕｂ７２ｄ，７２ｆが含まれることが分かる。また、Ａ−Ｈｕｂ７２ｄでは、ポートＰ２，Ｐ３を通過することが分かる。Ａ−Ｈｕｂ７２ｆでは、ポートＰ１−Ｐ５を通過することが分かる。
【００８１】
図７の説明に戻る。制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、制約条件を生成する。また、制約条件生成部６８は、目的関数を生成する。制約条件生成部６８は、例えば、図１の制約条件生成部５に対応する。制約条件および目的関数については以下で詳細に説明する。
【００８２】
経路算出部６９は、制約条件生成部６８によって生成された制約条件および目的関数を満たすデマンドの経路を、数理計画法を用いて算出する。経路算出部６９は、例えば、図１の経路算出部６に対応する。
【００８３】
制約条件について説明する。制約条件生成部６８の生成する制約条件は、大きく２つに分けられる。１つ目は、各Ａ−Ｈｕｂのコネクション制限数に関する制約条件である。２つ目は、迂回経路に関する制約条件である。
【００８４】
２つ目の迂回経路に関する制約条件は、次の制約観点Ａ，Ｂに基づき生成される。
［制約観点Ａ］ポート（デマンド経路が通過しているＡ−Ｈｕｂのポート）を迂回することにより生じる追加ペナルティを考慮しても、デマンド経路のペナルティがペナルティ制限を越えない。
【００８５】
制約観点Ａは、あるデマンド経路を迂回経路に迂回させる場合（あるデマンドの経路が通過しているＡ−Ｈｕｂのポートを置換ポートに置換させる場合）、迂回経路もペナルティ制限を満たすようにするという観点から制約条件を生成することを示している。
【００８６】
［制約観点Ｂ］現在着目している迂回経路にＡ−Ｈｕｂが含まれる場合には、このＡ−Ｈｕｂで使用されるコネクションを使用する。
図１１で説明したように、ポートコネクションＴＢ６７の迂回経路にＡ−Ｈｕｂが含まれる場合の追加ペナルティは、最短経路探索法によって求められたＡ−Ｈｕｂのコネクションを通過した場合の値である。よって、ポートコネクションＴＢ６７に記憶されているＡ−Ｈｕｂのコネクションを通過しない場合、迂回経路の追加ペナルティが異なる場合が生じる。制約観点Ｂは、迂回経路にＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂで使用されるコネクションを使用するという観点から制約条件を生成することを示している。
【００８７】
以下、制約条件について具体的に説明する。制約条件生成部６８は、光ネットワークを形成しているＡ−Ｈｕｂの１つに着目する。制約条件生成部６８は、着目したＡ−Ｈｕｂ内のコネクション候補となる変数ＳAhub（ｘ，ｙ）を生成する。ｘ，ｙは、着目しているＡ−Ｈｕｂ内のポートを示し、ｘ≠ｙである。
【００８８】
変数ＳAhub（ｘ，ｙ）は、０または１の値をとり、経路算出部６９によって０，１が求まる。１は、例えば、ポートｘ，ｙ間のコネクションが採用されたことを示し、０は、ポートｘ，ｙ間のコネクションが採用されなかったことを示す。ＳAhub（ｘ，ｙ）のＡｈｕｂは、Ａ−Ｈｕｂ名を示し、どのＡ−Ｈｕｂの変数であるかを示す。
【００８９】
図１２は、変数を説明する図である。図１２に示すＡ−Ｈｕｂ７３の変数ＳAhub（ｘ，ｙ）は、経路算出部６９によって以下のように求まったとする。
ＳAhub（Ｐ０，Ｐ１）＝１
ＳAhub（Ｐ０，Ｐ２）＝１
ＳAhub（Ｐ０，Ｐ７）＝１
ＳAhub（Ｐ５，Ｐ７）＝１
ＳAhub（Ｐ２，Ｐ７）＝１
ＳAhub（Ｐ０，Ｐ３）＝０
ＳAhub（Ｐ０，Ｐ４）＝０
ＳAhub（Ｐ０，Ｐ６）＝０
ＳAhub（Ｐ６，Ｐ７）＝０
ＳAhub（Ｐ３，Ｐ７）＝０
この場合、Ａ−Ｈｕｂ７３は、図１２に示すように、コネクションが張られることになる。
【００９０】
制約条件生成部６８は、算出しようとするデマンドの経路が、Ａ−Ｈｕｂにてコネクション制限数を満たすための制約条件（１つ目の制約条件）を生成する。すなわち、制約条件生成部６８は、経路算出部６９により、コネクション制限数を満たすようにトラフィックパスが採用されるための制約条件を生成する。コネクション制限数を満たすための制約条件は、次の式（１）で示される。
【００９１】
【数１】
【００９２】
式（１）のコネクション制限数Ｌkは、トポロジ情報に含まれており、例えば、オペレータによって入力される。
式（１）の左辺は、変数ＳAhub（ｘ，ｋ）の全加算値を示している。変数ＳAhub（ｘ，ｋ）は、上記したように０，１の値をとる。従って、式（１）は、その左辺がＬk以下になるようにするということは、Ａ−Ｈｕｂがコネクション制限数Ｌkを満たすように、コネクションを張るということを示している。
【００９３】
例えば、式（１）のＬkが５の場合、図１２のＡ−Ｈｕｂのコネクションは、式（１）の制約条件を満たしていることになる（上記のＳAhub（Ｐ０，Ｐ１）〜ＳAhub（Ｐ３，Ｐ７）を加算すると１となる）。
【００９４】
制約条件生成部６８は、迂回経路に関する制約条件（２つ目の制約条件）を生成する。まず、制約観点Ａに基づく制約条件の生成について説明する。制約条件生成部６８は、あるデマンドの経路を迂回させる場合、制約観点Ａに基づき、迂回する経路もペナルティ制限を満たすようにするための制約条件を生成する。制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照して、制約観点Ａの制約条件を生成する。
【００９５】
制約観点Ａに基づく制約条件は、次の式（２）で示される。なお、式（２）では、変数ＳAhub（ｘ，ｙ）のＡｈｕｂを省略している。
【００９６】
【数２】
【００９７】
式（２）のＡk，Ａlは、ポートの代替可能候補集合を示す。ポートの代替可能候補集合とは、経路を置換ポートにより迂回させたとき、迂回経路がペナルティ制限を満たす置換ポートの集合をいう。例えば、図１１において、ポートＰ１の置換ポートは、ポートＰ０，Ｐ４，Ｐ５となる。経路のペナルティ余裕が３である場合、ポートＰ５は、迂回経路の候補となりえない。よって、この場合、ポートＰ１の代替可能候補集合は、ポートＰ０，Ｐ４となる。
【００９８】
式（２）の左辺の第１項は、元コネクション（経路算出部６２で求まったコネクション）を示している。第２項は、元コネクションの一方のポートを、代替可能候補集合のポートに置き換えた代替コネクションの集合を示している。第３項は、元コネクションの他方のポートを、代替可能候補集合のポートに置き換えた代替コネクションの集合を示している。
【００９９】
式（２）は、左辺の値が１以上になるようにコネクションを求めるよう制約していることを示している。すなわち、式（２）は、着目しているＡ−Ｈｕｂにおいて、少なくとも、元コネクションか、元コネクションの一方のポートを代替可能候補集合のポートに置き換えたコネクション集合のいずれかのコネクションか、または元コネクションの他方のポートを代替可能候補集合のポートに置き換えたコネクション集合のいずれかのコネクションかが選ばれるように制約している。
【０１００】
図１３は、制約観点Ａに基づく制約条件を説明する図である。図１３において図１０と同じものには同じ符号を付し、その説明を省略する。
経路算出部６２によって、あるデマンドの経路７４ａ，７４ｂが求まったとする。Ｈｕｂ７２ｃ，７２ｇの識別子は、Ｓ，Ｔとする。ペナルティ制限は１０とし、経路７４ａ，７４ｂのペナルティはそれぞれ７，４であったとする。この場合、図１３のＡ−Ｈｕｂ７２ａのコネクションマトリクスＴＢ６５は、図９に示すようになる。また、図１３のＡ−Ｈｕｂ７２ａのポートマトリクスＴＢ６７は、図１１に示すようになる。
【０１０１】
制約条件生成部６８は、ポートＰ１−Ｐ５のコネクションの迂回経路の１つとして、ポートマトリクスＴＢ６７を参照し、ポートＰ４を取得する。また、制約条件生成部６８は、ポートマトリクスＴＢ６７を参照し、ポートＰ１−Ｐ４の追加ペナルティ２を取得する。
【０１０２】
制約条件生成部６８は、コネクションマトリクスＴＢ６５を参照して、ポートＰ１−Ｐ５を通過する経路のペナルティ余裕３を取得する。追加ペナルティ２は、ペナルティ余裕３より小さいので、制約条件生成部６８は、ポートＰ４を代替可能候補集合Ａkとする。
【０１０３】
制約条件生成部６８は、上記と同様にして、ポートＰ１の代替候補となり得るポートを、ポートマトリクスＴＢ６７を参照して取得する。上記例の場合、ポートＰ０は、ポートＰ１の代替候補となり、ポートＰ５は、ポートＰ１の代替候補となりえない。
【０１０４】
すなわち、制約条件生成部６８は、ポートＰ１の置換ポートを取得し、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、取得した置換ポートにおける迂回経路がペナルティ制限を満たすか否か判断する。制約条件生成部６８は、置換ポートの迂回経路がペナルティ制限を満たせば、その置換ポートを代替可能候補集合Ａkとする。同様に、制約条件生成部６８は、ポートＰ５の代替可能候補集合Ａlを算出する。
【０１０５】
制約条件生成部６８は、上記のようにして代替可能候補集合Ａk，Ａlを算出し、式（２）に示す制約条件を生成する。なお、上記では、制約条件生成部６８は、ポートマトリクスＴＢ６７を参照して置換ポートを取得し、次いでコネクションマトリクスＴＢ６５を参照して代替可能候補集合を求めたが、算出順番は逆でもよい。例えば、制約条件生成部６８は、コネクションマトリクスＴＢ６５を参照してペナルティ余裕を取得し、次いでポートマトリクスＴＢ６７を参照して代替可能候補集合を求めてもよい。
【０１０６】
次に、制約観点Ｂに基づく制約条件の生成について説明する。制約条件生成部６８は、迂回経路にＡ−Ｈｕｂが含まれる場合、さらに、制約観点Ｂに基づき制約条件を生成する。例えば、図１３の例の場合、Ｈｕｂ７２ｃ，７２ｅを結ぶ迂回経路には、Ａ−Ｈｕｂ７２ｄが含まれる。そして、Ａ−Ｈｕｂ７２ｄでは、迂回経路はポートＰ２−Ｐ３のコネクションを通過する。従って、この場合、制約条件生成部６８は、Ａ−Ｈｕｂ７２ｄを通過する迂回経路が採用される場合、Ａ−Ｈｕｂ７２ｄのポートＰ２−Ｐ３を通過するように制約条件を生成する。
【０１０７】
図１４は、制約観点Ｂに基づく制約条件を説明する図である。図１４には、光ネットワークを形成しているＡ−Ｈｕｂ７５ａ〜７５ｃが示してある。Ａ−Ｈｕｂ７５ａ〜７５ｃのそれぞれは、ポートＰ０〜Ｐ８を有している。経路７５ｅは、経路７５ｄの迂回経路を示し、経路７５ｅの通過するＡ−Ｈｕｂ７５ｂでは、ポートＰ０−Ｐ４にコネクションが張られ、Ａ−Ｈｕｂ７５ｃでは、ポートＰ１−Ｐ８にコネクションが張られるものとする。
【０１０８】
図１４において、経路７５ｄの迂回経路として経路７５ｅが採用候補となる場合、経路７５ｅは、Ａ−Ｈｕｂ７５ｂのポートＰ０−Ｐ４を通過し、Ａ−Ｈｕｂ７５ｃのポートＰ１−Ｐ８を通過する必要がある。経路７５ｅは、図１０で説明したように、ダイクストラ法などの最短経路探索法によって算出され、通過するＡ−Ｈｕｂ７５ｂ，７５ｃの情報と、そのコネクションの情報とがポートマトリクスＴＢ６７に記憶され、そのコネクションを通過した場合における追加ペナルティがポートマトリクスＴＢ６７に記憶されているからである。
【０１０９】
制約条件生成部６８は、ポートマトリクスＴＢ６７を参照し、制約観点Ｂに基づく制約条件を生成する。制約条件生成部６８は、上記したように、迂回経路にＡ−Ｈｕｂが含まれる場合、ポートマトリクスＴＢ６７に記憶されているコネクションを通過する制約条件を生成する。
【０１１０】
例えば、制約条件生成部６８は、図１４の例の場合、次の式（３）に示す制約条件を生成する。
【０１１１】
【数３】
【０１１２】
式（３）の変数Ｓに示すＡ−Ｈｕｂ１，Ａ−Ｈｕｂ２，Ａ−Ｈｕｂ３は、それぞれの変数Ｓが図１４のＡ−Ｈｕｂ７５ａ〜７５ｃにおける変数であることを示している。
式（３）の第１項の変数Ｓは、図１４のＡ−Ｈｕｂ７５ａのポートＰ２−Ｐ５のコネクションの変数を示している。第１項の変数Ｓに乗算されている値２は、経路７５ｅの迂回経路に含まれるＡ−Ｈｕｂの数を示している。仮に経路７５ｅの迂回経路にＡ−Ｈｕｂが３つ含まれている場合には、第１項の変数Ｓには、３が乗算される。
【０１１３】
式（３）の第２項の変数Ｓは、図１４のＡ−Ｈｕｂ７５ｂのポートＰ０−Ｐ４のコネクションの変数を示している。式（３）の第３項の変数Ｓは、図１４のＡ−Ｈｕｂ７５ｃのポートＰ１−Ｐ８のコネクションの変数を示している。
【０１１４】
式（３）は、式（３）の左辺の値が０以下であることを制約条件としている。これは、Ａ−Ｈｕｂ７５ａのポートＰ２−Ｐ５のコネクションが採用されるならば、Ａ−Ｈｕｂ７５ｂのポートＰ０−Ｐ４のコネクションが採用され、かつ、Ａ−Ｈｕｂ７５ｃのポートＰ１−Ｐ８のコネクションが採用されることを示している。
【０１１５】
例えば、Ａ−Ｈｕｂ７５ａのポートＰ２−Ｐ５のコネクションが採用されるならば、式（３）のＳA-Hub1（Ｐ２，Ｐ５）は１となる。この場合、式（３）を満たすには、式（３）の第２項、第３項が１とならなければならい。すなわち、第２項、第３項は、次の関係を満たさなければならない。
【０１１６】
ＳA-Hub2（Ｐ０，Ｐ４）＝１
ＳA-Hub3（Ｐ１，Ｐ８）＝１
これは、Ａ−Ｈｕｂ７５ｂ（Ａ−Ｈｕｂ２）のＰ０−Ｐ４のコネクションが採用され、Ａ−Ｈｕｂ７５ｃ（Ａ−Ｈｕｂ３）のポートＰ１−Ｐ８のコネクションが採用されることを示している。
【０１１７】
制約条件生成部６８は、Ａ−Ｈｕｂを含む迂回経路に対して、上記と同様にして制約観点Ｂに基づく制約条件を生成する。
目的関数について説明する。制約条件生成部６８は、目的関数を生成する。目的関数は、例えば、次の式（４）で示される。
【０１１８】
【数４】
【０１１９】
式（４）は、光ネットワーク内の全てのコネクション候補となる変数Ｓに重み付けＣAhub,x,yを付加し、それを加算したことを示している。式（４）では、目的関数を「Maximize」として指定しているが、場合によっては、「Minimize」を指定することもできる。例えば、Ａ−Ｈｕｂにおける使用コネクション数を最小に抑えたいという場合、「Minimize」を指定することができる。なお、式（４）のＣAhub,x,yのＡｈｕｂは、Ａ−Ｈｕｂ名を示し、どのＡ−Ｈｕｂの重み付けであるかを示す。
【０１２０】
式（４）の各変数Ｓに対する重み付けの配分次第で、経路算出部６９は、様々な経路結果を得ることができる。式（５）は、重み付けの一例を示している。なお、式（５）では、ＣAhub,x,yのＡｈｕｂを省略している。
【０１２１】
【数５】
【０１２２】
式（５）のＤx,yは、最初の仮設計（経路算出部６２による経路算出）における、Ａ−Ｈｕｂの各コネクションに属しているデマンド経路の本数を示している。このパラメータを目的関数に導入することで、経路算出部６９は、デマンド経路の本数が多いＡ−Ｈｕｂのコネクションについては、なるべく現状を維持するように（デマンド経路が迂回しないように）経路算出する。
【０１２３】
Ｒx,yは、最初の仮設計で存在していたコネクションであるか否かを示すフラグである。このパラメータを目的関数に導入することで、経路算出部６９は、最初の仮設計で採用されたコネクションをなるべく優先的に採用するよう設計する。
【０１２４】
式（５）のαx,yは、最初の仮設計で全く使用されていなかったコネクションに対する値である。このパラメータを目的関数に導入することで、経路算出部６９は、最初の仮設計で使用されていないコネクションもある優先度で採用できるようにすることができる。
【０１２５】
ＨＤx,yは、最初の仮設計において複数のＡ−Ｈｕｂを通過するデマンド経路がある場合、このＡ−Ｈｕｂ間の経路を優先的に採用するためのパラメータである。このパラメータを目的関数に導入することで、経路算出部６９は、最初の仮設計において設計された複数のＡ−Ｈｕｂ間を通過する経路において、優先的に採用できるようにすることができる。
【０１２６】
図１５は、複数のＡ−Ｈｕｂを通過する経路を優先的に採用する目的関数を説明する図である。図１５には、光ネットワークを形成しているＡ−Ｈｕｂ７６ａ，７６ｂが示してある。経路７６ｃは、経路算出部６２によって算出された経路を示している。
【０１２７】
最初の仮設計で算出された経路７６ｃは、Ａ−Ｈｕｂ７６ａ，７６ｂを通過している。この場合、制約条件生成部６８は、Ａ−Ｈｕｂ７６ａ，７６ｂ間の経路については、経路算出部６９によって優先的に採用されるようにＨＤx,Yを調整する。
【０１２８】
例えば、制約条件生成部６８は、Ａ−Ｈｕｂ７６ａのポートＰ５に属するコネクションのＨＤx,Yと、Ａ−Ｈｕｂ７６ｂのポートＰ０に属するコネクションのＨＤx,yについては、２を設定する。その他のコネクションについては、ＨＤx,yについては、１を設定する。この場合、経路算出部６９は、Ａ−Ｈｕｂ７６ａのポートＰ５と、Ａ−Ｈｕｂ７６ｂのポートＰ０との間の経路が優先的に採用されるように経路設計を行う。
【０１２９】
なお、上記の目的関数の設定は一例であり、上記に限るものではない。
図１６は、光ネットワーク設計装置の処理動作を示したフローチャートである。
［ステップＳ１ａ，Ｓ１ｂ］経路算出部６２は、オペレータから要求のあったデマンドの数分、ステップＳ２の処理を行う。
【０１３０】
［ステップＳ２］経路算出部６２は、トポロジ情報記憶部６１を参照し、オペレータから要求のあったデマンドの経路探索を行う。経路算出部６２は、コネクション制限を考慮せずにデマンドの経路探索を行う。経路算出部６２は、算出したデマンド経路の結果を経路情報記憶部６３に記憶する。
【０１３１】
［ステップＳ３］経路算出部６２は、算出したデマンドの経路が通過するＡ−Ｈｕｂにおいて、コネクション制限違反があったか否か判断する。経路算出部６２は、コネクション制限違反がない場合、処理を終了する。すなわち、オペレータの要求するデマンド経路が求まったので、経路算出部６２は処理を終了する。経路算出部６２は、コネクション制限違反がある場合、ステップＳ４ａへ進む。
【０１３２】
［ステップＳ４ａ，Ｓ４ｂ］コネクションマトリクス生成部６４およびポートマトリクス生成部６６は、コネクション制限違反のあったＡ−Ｈｕｂのそれぞれにおいて、以下のステップＳ５〜Ｓ７の処理を行う。
【０１３３】
［ステップＳ５］コネクションマトリクス生成部６４は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してコネクションマトリクスを生成し、コネクションマトリクスＴＢ６５に記憶する。
【０１３４】
［ステップＳ６ａ，６ｂ］ポートマトリクス生成部６６は、Ａ−Ｈｕｂの各ポート間において、以下のステップＳ７の処理を行う。なお、この処理は、Ａ−Ｈｕｂのポート数をＰとすると、１／２＊Ｐ（Ｐ−１）回繰り返すことになる。
【０１３５】
［ステップＳ７］ポートマトリクス生成部６６は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してポートマトリクスを生成し、ポートマトリクスＴＢ６７に記憶する。
【０１３６】
［ステップＳ８］制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、数理計画モデルを生成する。すなわち、制約条件生成部６８は、制約条件と目的関数を生成する。
【０１３７】
［ステップＳ９］経路算出部６９は、制約条件生成部６８によって生成された数理計画モデルに基づき、数理計画法によって経路を算出する。
上記で説明した経路算出（数理計画法による経路算出）の計算量について説明する。経路探索法には、上記の方法以外に、例えば、Ａ−Ｈｕｂのコネクション制限を考慮せずに経路算出し、算出した経路のコネクション制限違反を判断し、違反したＡ−Ｈｕｂにて削除コネクションを選定して削除し、再度経路算出を行う方法がある。以下では、この削除コネクションを選定して経路算出を行う方法と、上記の数理計画法による経路算出法の計算量について説明する。
【０１３８】
削除コネクションを選定して経路算出を行う方法での計算量は、次の式（６）で示される。
【０１３９】
【数６】
【０１４０】
Ｎは、光ネットワーク内のＡ−Ｈｕｂの総数を示す。Ｃnewは、削除コネクションの数を示す。ＤC＿newは、削除コネクションに属しているデマンド経路の本数を示している。
ここで、上記の数理計画法による経路算出法の計算量との比較を行うために、Ｃnewの演算量をＡ−Ｈｕｂのポート数で置き換えることを考える。
【０１４１】
まず、削除コネクション数は、最も多い場合を考えると、Ｃnew＝フルメッシュコネクション組合数−設定可能コネクション数で示される。ポートのコネクション制限数を４とすると、削除コネクション数は、次の式（７）で示される。
【０１４２】
【数７】
【０１４３】
Ｐは、Ａ−Ｈｕｂのポート数を示す。すなわち、削除コネクション数Ｃnewは、ポート数の２乗に比例すると考えることができる。
従って、削除コネクションを選定して経路算出する方法の計算量は、式（６），（７）より式（８）に示すようになる。
【０１４４】
【数８】
【０１４５】
一方、上記の数理計画法による経路算出法の計算量は、図１６のステップ６ａ，６ｂで説明したように、１つのＡ−Ｈｕｂでは、１／２＊Ｐ（Ｐ−１）で示される。従って、Ａ−ＨｕｂがＮ個ある場合には、その計算量は次の式（９）で示すことができる。
【０１４６】
【数９】
【０１４７】
式（８）と式（９）を比較すると、削除コネクションを選定して経路算出を行う方法では、光ネットワーク内のデマンドの数に依存することが分かる。従って、上記の数理計画法による経路算出法の方が、計算量が少なく、経路算出時間を短縮できる。
【０１４８】
なお、Ａ−Ｈｕｂのコネクション制限を考慮せずに経路算出する部分においては、両者とも計算量は同じである。また、削除コネクションを選定して経路算出を行う方法に対し、上記の数理計画法による経路算出法では、数理計画法を用いた処理が加わる。数理計画法部分の計算量については、光ネットワーク上に３つのＡ−Ｈｕｂ（実際の光ネットワークに存在し得ると考えられる数）が存在する場合について計算したところ、０．１ｓ程度であり、十分微小と考えられる。
【０１４９】
図１７は、削除コネクションを選定して経路算出を行う方法の経路算出イメージを示した図である。図１７には、光ネットワークが示してある。削除コネクションを選定して経路算出を行う方法では、図１７に示すように、Ａ−Ｈｕｂ７７ａ，７７ｂ，７７ｃ，…と１つずつ逐次的に、コネクション制限違反を解消するようにコネクションを調整する。
【０１５０】
図１８は、数理計画法による経路算出イメージを示した図である。図１８には、光ネットワークが示してある。上記で説明した経路算出法では、図１８に示すように、光ネットワークを形成しているＡ−Ｈｕｂ７８ａ〜７８ｅの全てのコネクション制限を解消するための条件（制約条件）を出し、１回の数理計画法で経路を求める。これにより、上記の経路算出法では、ネットワーク全体で最適化された経路を算出することが可能となる。
【０１５１】
このように、光ネットワーク設計装置１０は、コネクション制限数とペナルティ制限とを満たすデマンド経路が採用されるための制約条件を生成する。そして、光ネットワーク設計装置１０は、生成した制約条件に基づいて、数理計画法により最終的なデマンド経路を算出するようにした。これにより、光ネットワーク設計装置は、適切な経路結果を得ることができる。例えば、コネクション制限数およびペナルティ制限を満たす経路結果を得ることができる。
【０１５２】
［第３の実施の形態］
次に、第３の実施の形態を、図面を参照して詳細に説明する。第２の実施の形態では、コネクションの片ポートのみを切替えるように制約条件を生成し、経路算出を行った。第３の実施の形態では、コネクションの両ポートを切替えるように制約条件を生成し、経路算出を行う。
【０１５３】
図１９は、第３の実施の形態に係る両ポート制約を説明する図である。図１９には、光ネットワークを形成しているＡ−Ｈｕｂ８１ａが示してある。Ａ−Ｈｕｂ８１ａは、ポートＰ０〜Ｐ８を有している。また、図１９には、最初の仮設計で算出された経路８１ｂと、その迂回経路を示した経路８１ｃ，８１ｄが示してある。
【０１５４】
最初に仮設計された経路８１ｂは、Ａ−Ｈｕｂ８１ａのポートＰ１−Ｐ５のコネクションを通過している。第２の実施の形態で説明した片ポート制約は、このポートＰ１−Ｐ５の一方を置換ポートに置き換え、経路８１ｂを経路８１ｃ，８１ｄに迂回させる。
【０１５５】
例えば、図１９に示すポートＰ２−Ｐ５のコネクション８１ｅは、ポートＰ１をポートＰ２の置換ポートに置き換えている。これにより、経路８１ｂは、経路８１ｃに迂回している。また、図１９に示すポートＰ１−Ｐ７のコネクション８１ｆは、ポートＰ５をポートＰ７の置換ポートに置き換えている。これにより、経路８１ｂは、経路８１ｄに迂回している。
【０１５６】
両ポート制約は、最初に仮設計された経路のコネクションのポートの両方を置換ポートに置き換える。
例えば、図１９に示す最初に仮設計された経路８１ｂのコネクションのポートＰ１−Ｐ５の両方を、ポートＰ２，Ｐ７に置き換える。すなわち、両ポート制約は、図１９に示すポートＰ２−Ｐ７のコネクション８１ｇを張るようにする。
【０１５７】
なお、第３の実施の形態に係る光ネットワーク設計装置のハードウェア構成および機能ブロックは、図２で示したハードウェア構成例および図７で示した機能ブロックと同様であり、その説明を省略する。ただし、第３の実施の形態に係る光ネットワーク設計装置１０では、機能ブロックの制約条件生成部６８の機能が一部異なる。第３の実施の形態では、制約条件生成部６８は、コネクションの両ポートを代替したコネクションも採用されるように制約条件を生成する。
【０１５８】
第３の実施の形態に係る制約条件生成部６８は、第２の実施の形態と同様に、各Ａ−Ｈｕｂのコネクション制限数に関する制約条件と、迂回経路に関する制約条件とを生成する。迂回経路に関する制約条件に関しては、制約観点Ａ，Ｂに基づいて制約条件を生成する。
【０１５９】
第２の実施の形態では、制約条件生成部６８は、あるデマンドの経路を迂回させる場合、制約観点Ａに基づき、迂回する経路もペナルティ制限を満たすようにするための制約条件を生成する。第３の実施の形態においても制約条件生成部６８は、同様に制約条件を生成するが、コネクションの両ポートを代替したコネクションも採用されるように制約条件を生成する。
【０１６０】
制約観点Ａに基づく制約条件は、次の式（１０）で示される。なお、式（１０）では、変数ＳAhub（ｘ，ｙ）のＡｈｕｂを省略している。
【０１６１】
【数１０】
【０１６２】
式（１０）では、式（２）に対し、左辺に第４項が追加されている。第４項の代替可能候補集合Ａk,lは、コネクションの両ポートの置換可能な（経路を迂回させることが可能な）置換ポート集合を示し、式（１０）は、コネクションの両ポートを代替可能候補集合Ａk,lのポートに置き換えたコネクションも採用されることを示している。制約条件生成部６８は、コネクションの両ポートにおいてコネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、第４項を含む制約条件を生成する。その他の制約条件の生成に関しては第２の実施の形態と同様であるのでその説明を省略する。
【０１６３】
図２０は、光ネットワーク設計装置の処理動作を示したフローチャートである。
図２０のステップＳ１ａ〜Ｓ７は、図１６のステップＳ１ａ〜Ｓ７と同様であり、その説明を省略する。
【０１６４】
［ステップＳ２１］制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、数理計画モデルを生成する。すなわち、制約条件生成部６８は、制約条件と目的関数を生成する。制約条件生成部６８は、式（２）に示す片ポート制約の制約条件と、式（１０）に示す両ポート制約の制約条件とを生成する。
【０１６５】
［ステップＳ２２］経路算出部６９は、制約条件生成部６８によって生成された数理計画モデルに基づき、数理計画法によって経路を算出する。経路算出部６９は、片ポート制約により、経路算出を行う。
【０１６６】
［ステップＳ２３］経路算出部６９は、経路算出を算出できたか否か判断する。すなわち、経路算出部６９は、経路設計できたか否か判断する。経路算出部６９は、経路設計できた場合、処理を終了する。経路算出部６９は、経路設計できなかった場合、ステップＳ２４へ進む。
【０１６７】
［ステップＳ２４］経路算出部６９は、制約条件生成部６８によって生成された数理計画モデルに基づき、数理計画法によって経路を算出する。経路算出部６９は、両ポート制約により、経路算出を行う。
【０１６８】
このように、光ネットワーク設計装置１０は、両ポート制約によっても経路設計することができる。
また、光ネットワーク設計装置１０は、片ポート制約によって経路設計できなかった場合に両ポート制約によって経路設計するので、片ポート制約によって経路設計できた場合、経路計算時間を短縮することができる。
【０１６９】
なお、上記では、光ネットワーク設計装置１０は、片ポート制約によって経路設計できなかった場合、両ポート制約による経路設計を行うとしたが、両ポート制約による経路設計のみを行ってもよい。例えば、図２０において、ステップＳ２２，２３の処理を省略してもよい。
【０１７０】
［第４の実施の形態］
次に、第４の実施の形態を、図面を参照して詳細に説明する。第４の実施の形態では、ポートマトリクスのみを生成して経路算出を行う場合について説明する。第４の実施の形態に係る光ネットワーク設計装置のハードウェア構成は、図２で示したハードウェア構成例と同様であり、その説明を省略する。
【０１７１】
図２１は、第４の実施の形態に係る光ネットワーク設計装置の機能ブロック図である。図２１において、図７と同じものには同じ符号を付し、その説明を省略する。
図２１に示すように、光ネットワーク設計装置１０は、ポートマトリクス生成部９１およびポートマトリクスＴＢ９２を有している。
【０１７２】
ポートマトリクス生成部９１は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してポートマトリクスを生成し、ポートマトリクスＴＢ９２に記憶する。ポートマトリクス生成部９１は、光ネットワークに含まれている全てのＡ−Ｈｕｂにおいてポートマトリクスを生成し、ポートマトリクスＴＢ９２に記憶する。
【０１７３】
図２２は、ポートマトリクスの生成を説明する図である。図２２には、光ネットワークを形成しているＡ−Ｈｕｂ１０１ａ，１０１ｄ，１０１ｅおよびＨｕｂ１０１ｂ，１０１ｃ，１０１ｆが示してある。Ａ−Ｈｕｂ１０１ｄ，１０１ｅの識別子をそれぞれＸ，Ｙとする。また、図２２には、経路１０２ａ〜１０２ｄが示してある。
【０１７４】
第２の実施の形態では、着目しているＡ−Ｈｕｂに最も近いＨｕｂに着目し、その着目したＨｕｂ間での迂回経路を探索した。第４の実施の形態では、着目しているＡ−Ｈｕｂを通過しているデマンド経路の共通経路端のＨｕｂに着目し、その着目したＨｕｂ間で迂回経路を探索する。
【０１７５】
例えば、図２２の例では、経路算出部６２によって、経路１０２ａ〜１０２ｄが算出されたとする。経路１０２ａ，１０２ｂの共通経路端のＨｕｂは、Ｈｕｂ１０１ｃ，１０１ｆである。また、経路１０２ｃ，１０２ｄの共通経路端のＨｕｂは、Ｈｕｂ１０１ｂ，１０１ｃである。ポートマトリクス生成部９１は、これら共通経路端のＨｕｂの情報を取得する。なお、コネクションを通過しているデマンド経路が１つの場合、その共通経路端は、デマンドの始点と終点のＨｕｂとなる。
【０１７６】
ポートマトリクス生成部９１は、共通経路端のＨｕｂを取得すると、その共通経路端のＨｕｂ間で迂回経路を探索する。ポートマトリクス生成部９１は、着目しているＡ−Ｈｕｂにおいて、共通経路端の経路が通過しているコネクションは通過することができないとして迂回経路を探索する。迂回経路の探索は、例えば、ダイクストラ法などの最短経路探索法で行う。
【０１７７】
例えば、図２２において、経路１０２ａ，１０２ｂの共通経路端のＨｕｂは、Ｈｕｂ１０１ｃ，１０１ｆである。また、共通経路端のＨｕｂ１０１ｃ，１０１ｆの経路が通過しているコネクションは、ポートＰ１−Ｐ５である。よってこの場合、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ１−Ｐ５のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｃ，１０１ｆ間の迂回経路をダイクストラ法によって探索する。
【０１７８】
また、図２２において、経路１０２ｃ，１０２ｄの共通経路端のＨｕｂは、Ｈｕｂ１０１ｂ，１０１ｃである。また、共通経路端のＨｕｂ１０１ｂ，１０１ｃの経路が通過しているコネクションは、ポートＰ０−Ｐ１である。よってこの場合、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ１のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｂ，１０１ｃ間の迂回経路をダイクストラ法によって探索する。
【０１７９】
ポートマトリクス生成部９１は、算出した迂回経路によっても、元の経路のペナルティ制限を越えない場合、迂回後のポート情報をポートマトリクスＴＢ９２に記憶する。また、ポートマトリクス生成部９１は、迂回経路に着目しているＡ−Ｈｕｂ以外のＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂの情報と、そのＡ−Ｈｕｂの迂回経路が通過しているコネクションの情報とをポートマトリクスＴＢ９２に記憶する。
【０１８０】
すなわち、ポートマトリクス生成部９１は、デマンド経路の共通経路端にて、デマンド経路が通過したコネクションを通過しない、ペナルティ制限を満たす迂回経路を探索し、探索した迂回経路の迂回経路情報を算出してポートマトリクスＴＢ９２に記憶する。また、ポートマトリクス生成部９１は、探索した迂回経路にＡ−Ｈｕｂが含まれる場合、Ａ−Ｈｕｂに関する情報を算出してポートマトリクスＴＢ９２に記憶する。
【０１８１】
図２３は、ポートマトリクスＴＢのデータ構成例を示した図である。図２３に示すように、ポートマトリクスＴＢ９２は、対象コネクションの欄および迂回経路の欄を有している。
【０１８２】
対象コネクションの欄には、迂回経路の対象となるコネクションの情報が記憶される。対象コネクションの欄には、例えば、着目しているＡ−Ｈｕｂが有しているポートの全組み合わせが記憶される。
【０１８３】
迂回経路の欄には、対象コネクションに対する迂回経路の情報が記憶される。例えば、迂回経路の欄には、着目しているＡ−Ｈｕｂにおいて、迂回経路が通過するコネクションの情報と、迂回経路にＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂの情報と、そのＡ−Ｈｕｂの迂回経路が通過しているコネクションの情報が記憶される。
【０１８４】
例えば、図２２の例において、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ１−Ｐ５のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｃ，１０１ｆ間の迂回経路を探索する。その結果、ポートマトリクス生成部９１は、Ｈｕｂ１０１ｃ、Ａ−Ｈｕｂ１０１ａのポートＰ１−Ｐ４のコネクション、ポートＰ４に接続されたＨｕｂ、Ａ−Ｈｕｂ１０１ｅ、およびＨｕｂ１０１ｆを通過する迂回経路を得たとする。また、迂回経路が通過したＡ−Ｈｕｂ１０１ｅでは、ポートＰ１−Ｐ５のコネクションに迂回経路が通過したとする。この迂回経路は、ペナルティ制限を越えなかったとする。
【０１８５】
この場合、ポートマトリクス生成部９１は、ポートマトリクスＴＢ９２の対象コネクションのポートＰ１−Ｐ５（迂回前に通過していたコネクション）の欄に対応する迂回経路の欄に、迂回後のポートＰ１−Ｐ４の情報を記憶する。また、算出した迂回経路には、Ａ−Ｈｕｂ１０１ａ以外のＡ−Ｈｕｂ１０１ｅが含まれているので、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ｅの情報（例えば、識別子Ｙ）と、Ａ−Ｈｕｂ１０１ｅの迂回経路が通過するコネクションの情報（ポートＰ１−Ｐ５）とをポートマトリクスＴＢ９２の迂回経路の欄に記憶する。
【０１８６】
なお、Ｈｕｂ１０１ｃ，１０１ｆ間を結ぶ迂回経路のペナルティがペナルティ制限を越えていた場合は、対象コネクションＰ１−Ｐ５に対応する迂回経路の欄には、迂回経路なしを示す情報が記憶される。
【０１８７】
また、図２２の例において、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ１のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｂ，１０１ｃ間の迂回経路を探索する。その結果、ポートマトリクス生成部９１は、Ｈｕｂ１０１ｂおよびＨｕｂ１０１ｃを通過する迂回経路を得たとする。この迂回経路は、ペナルティ制限を越えなかったとする。
【０１８８】
この場合、ポートマトリクス生成部９１は、ポートマトリクスＴＢ９２の対象コネクションのポートＰ０−Ｐ１（迂回前に通過していたコネクション）の欄に対応する迂回経路の欄に、迂回後の情報を記憶する。上記迂回経路では、Ａ−Ｈｕｂ１０１ａを通過しないので、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ通過なしという情報を記憶する。すなわち、ポートマトリクス生成部９１は、迂回経路はＡ−Ｈｕｂ１０１ａを通過しないという情報を記憶する。
【０１８９】
なお、Ｈｕｂ１０１ｂ，１０１ｃ間を結ぶ迂回経路のペナルティがペナルティ制限を越えていた場合は、対象コネクションＰ０−Ｐ１に対応する迂回経路の欄には、迂回経路なしを示す情報が記憶される。
【０１９０】
図２２の例では、ポートＰ０−Ｐ２コネクションに対する迂回経路は存在しない（図２２では、ポートＰ０−Ｐ２を通過する共通経路端の図示は省略している）。従って、対象コネクションのＰ０−Ｐ２に対応する迂回経路の欄には、迂回経路なしという情報が記憶される。
【０１９１】
制約条件生成部６８は、第２の実施の形態で説明したのと同様に目的関数を生成する。また、制約条件生成部６８は、ポートマトリクスＴＢ９２を参照して、第２の実施の形態で説明したのと同様に制約条件を生成する。すなわち、制約条件生成部６８は、各Ａ−Ｈｕｂのコネクション制限数に関する制約条件と、迂回経路に関する制約条件とを生成する。制約条件生成部６８は、迂回経路に関する制約条件については、制約観点Ａ，Ｂに基づいて生成する。
【０１９２】
例えば、ポートマトリクＴＢ９２に図２３で示した情報が記憶されているとする。制約条件生成部６８は、対象コネクション単位で制約条件を生成する。
・Ｐ０−Ｐ１の制約条件
経路１０２ｃ，１０２ｄは、Ａ−Ｈｕｂ１０１ａを通過しなくても迂回することができる。従って、例えば、オペレータから着目しているＡ−Ｈｕｂ１０１ａの迂回許可の設定がされていれば、制約条件生成部６８は、制約条件は生成しない。すなわち、変数ＳA-Hub（Ｐ０−Ｐ１）は、０でも１でもよい。なお、ＳA-HubのＡ−Ｈｕｂは、Ａ−Ｈｕｂ１０１ａを示している。
【０１９３】
一方、例えば、オペレータから着目しているＡ−Ｈｕｂ１０１ａの迂回不許可の設定がされていれば、制約条件生成部６８は、次の式（１１）に示す制約条件を生成する。
【０１９４】
【数１１】
【０１９５】
すなわち、制約条件生成部６８は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ１のコネクションが採用されるように制約条件を生成する。
・Ｐ０−Ｐ２の制約条件
図２３のポートマトリクスＴＢ９２より、ポートＰ０−Ｐ２のコネクションには、迂回経路が存在しない。従って、制約条件生成部６８は、制約観点Ａから次の式（１２）に示す制約条件を生成する。
【０１９６】
【数１２】
【０１９７】
すなわち、制約条件生成部６８は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ２のコネクションが採用されるように制約条件を生成する。
・Ｐ１−Ｐ５の制約条件
図２３のポートマトリクスＴＢ９２より、ポートＰ１−Ｐ５のコネクションには、迂回経路が存在する。従って、制約条件生成部６８は、制約観点Ａから次の式（１３）に示す制約条件を生成する。
【０１９８】
【数１３】
【０１９９】
すなわち、制約条件生成部６８は、ポートＰ１−Ｐ５のコネクションまたはポートＰ１−Ｐ４のコネクションのどちらかまたは両方が採用されるように制約条件を生成する。
また、ポートＰ１−Ｐ４の迂回経路には、識別子ＹのＡ−Ｈｕｂ（図２２のＡ−Ｈｕｂ１０１ｅ）が含まれる。迂回経路は、このＡ−Ｈｕｂ１０１ｅのポートＰ１−Ｐ５のコネクションを通過しなければならないので、制約条件生成部６８は、制約観点Ｂから次の式（１４）に示す制約条件を生成する。
【０２００】
【数１４】
【０２０１】
式（１４）の左辺第２項のＡ−ＨｕｂＹは、Ａ−Ｈｕｂ１０１ｅを示している。
すなわち、制約条件生成部６８は、ポートＰ１−Ｐ４のコネクションが採用されるならば（ＳA-Hub（Ｐ１−Ｐ４）＝１）、Ａ−Ｈｕｂ１０１ｅのポートＰ１−Ｐ５のコネクションが採用される（ＳA-HubY（Ｐ１−Ｐ５）＝１）ように制約条件を生成する。
【０２０２】
なお、経路算出部６９は、第２の実施の形態で説明したのと同様に、制約条件生成部６８が生成した制約条件と目的関数とに基づいて、数理計画法に基づき経路を算出する。
このように、光ネットワーク設計装置１０は、コネクション制限数、迂回経路情報（例えば、着目しているＡ−Ｈｕｂ１０１ａの迂回経路が通過するポート情報）、およびＡ−Ｈｕｂの情報（例えば、迂回経路に含まれるＡ−Ｈｕｂ１０１ｅの情報）に基づいて制約条件を生成する。そして、光ネットワーク設計装置１０は、生成した制約条件に基づいて、数理計画法により最終的なデマンド経路を算出するようにした。これにより、光ネットワーク設計装置１０は、適切な経路結果を得ることができる。例えば、コネクション制限数およびペナルティ制限を満たす経路結果を得ることができる。
【０２０３】
［第５の実施の形態］
次に、第５の実施の形態を、図面を参照して詳細に説明する。第２の実施の形態では、迂回経路に隣接するＡ−Ｈｕｂ（隣接するＡ−Ｈｕｂ間にＨｕｂが含まれていてもよい）が含まれる場合、そのＡ−Ｈｕｂ間の経路は固定的である。例えば、図１４に示すように、隣接するＡ−Ｈｕｂ７５ｂ，７５ｃ間の経路は固定的である。第５の実施の形態では、迂回経路に含まれる隣接するＡ−Ｈｕｂ間の代替経路を、例えば、ダイクストラ法などの最短経路探索法によって探索し、その代替経路も迂回経路として採用されるようにする。
【０２０４】
第５の実施の形態に係る光ネットワーク設計装置のハードウェア構成および機能ブロックは、図２で示したハードウェア構成例および図７で示した機能ブロックと同様であり、その説明を省略する。ただし、第５の実施の形態では、機能ブロックの制約条件生成部６８の機能が一部異なる。
【０２０５】
図２４は、第５の実施の形態に係る代替経路を説明する図である。図２４には、光ネットワークを形成しているＡ−Ｈｕｂ１１１ａ，１１１ｂが示してある。Ａ−Ｈｕｂ１１１ａ，１１１ｂは、ポートＰ０〜Ｐ８を有している。図２４に示す丸は（ポートＰ０〜Ｐ８は除く）、Ｈｕｂを示している。Ａ−Ｈｕｂ１１１ａ，１１１ｂの識別子は、それぞれＸ，Ｙとする。
【０２０６】
経路１１１ｅは、ポートマトリクス生成部６６によって算出された迂回経路を示している。経路１１１ｅに含まれるＡ−Ｈｕｂ１１１ａ，１１１ｂの情報（識別子Ｘ，Ｙ）およびコネクションの情報（ポートＰ０−Ｐ４、ポートＰ１−Ｐ４）は、ポートマトリクスＴＢ６７に記憶されている。Ａ−Ｈｕｂ１１１ａ，１１１ｂは、その間に２つのＨｕｂが含まれているがＡ−Ｈｕｂを含んでいないので隣接するＡ−Ｈｕｂである。
【０２０７】
制約条件生成部６８は、経路１１１ｅ上において、隣接するＡ−Ｈｕｂ１１１ａ，１１１ｂの最も近いＨｕｂ１１１ｃ，１１１ｄ間で代替経路を算出する。例えば、制約条件生成部６８は、ダイクストラ法などの最短経路探索法によってＨｕｂ１１１ｃ，１１１ｄ間の代替経路を算出する。ここでは、図２４に示すように、代替経路として経路１１１ｆが算出されたとする。
【０２０８】
制約条件生成部６８は、算出した代替経路のペナルティがペナルティ制限を満たす場合、迂回経路と代替経路の一方が採用されるように制約条件を生成する。制約条件は、制約観点Ｂに基づいて生成される。
【０２０９】
図２４の例の場合、制約条件生成部６８は、次の式（１５）〜（１７）に示す制約条件を生成する。
【０２１０】
【数１５】
【０２１１】
式（１５）の変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）は、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４と、Ａ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路を示す。従って、例えば、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）の値が１の場合、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４と、Ａ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路が採用されたことを示す。また、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）の値が０の場合、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４とＡ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路が採用されなかったことを示す。
【０２１２】
なお、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）のＡＨＸは、図２４のＡ−Ｈｕｂ１１１ａ（識別子Ｘ）を示し、ＡＨＹは、Ａ−Ｈｕｂ１１１ｂ（識別子Ｙ）を示す。また、式（１５）の変数ＳA-HubX，ＳA-HubYのＡ−ＨｕｂＸ，Ａ−ＨｕｂＹは、図２４のＡ−Ｈｕｂ１１１ａ，１１１ｂを示す。
【０２１３】
式（１５）は、式（１５）の左辺の値が０以下であることを制約条件としている。これは、図２４のＡ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４とＡ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路が採用されるならば、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４のコネクションとＡ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４のコネクションとが採用されることを示している。
【０２１４】
式（１６）の変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ５，ＡＨＹ＿Ｐ０Ｐ４）は、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ５と、Ａ−Ｈｕｂ１１１ｂのポートＰ０−Ｐ４とを通過する経路を示す。式（１６）は、図２４のＡ−Ｈｕｂ１１１ａのポートＰ０−Ｐ５とＡ−Ｈｕｂ１１１ｂのポートＰ０−Ｐ４とを通過する経路が採用されるならば、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ５のコネクションとＡ−Ｈｕｂ１１１ｂのポートＰ０−Ｐ４のコネクションとが採用されることを示している。
【０２１５】
式（１７）は、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）の経路と変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ５，ＡＨＹ＿Ｐ０Ｐ４）の経路の少なくとも一方が採用されることを示している。すなわち、図２４に示す経路１１１ｅか経路１１１ｆの少なくとも一方が採用されることを示している。
【０２１６】
このように、迂回経路の代替経路を採用することも可能である。これにより、経路設計できる可能性を高めることができる。
以下、上記実施の形態で説明した数理計画法による経路算出の効果の一例について説明する。
【０２１７】
図２５は、最短経路探索法によって経路算出する光ネットワークの例を示した図である。図２５に示すアルファベットは、Ｈｕｂの識別子を示している。図２５のＢ，Ｃ，Ｇ，Ｈは、Ａ−Ｈｕｂである。図２５中の数字は、ペナルティを示している。
【０２１８】
図２６は、デマンドを示した図である。図２５の経路探索は、図２６のデマンドに対して、経路探索を行ったものとする。
図２５の光ネットワークにおいて、コネクション制限違反を考慮せずに、ダイクストラ法などの最短経路探索法によって経路探索を行うと、図２５の黒丸に示すように、Ａ−ＨｕｂＢ，Ｃ，Ｇ，Ｈにて、コネクション制限違反が生じる。なお、図２５では、コネクション制限数を４としている。
【０２１９】
図２７は、数理計画法によって経路算出する光ネットワークの例を示した図である。図２７の光ネットワークは、図２５の光ネットワークと同様であり、その説明を省略する。
図２８は、数理計画法によって経路算出した結果を示した図である。図２８には、図２７の光ネットワークにおいて、コネクション制限数を４とし、ペナルティ制限を２４とした場合の経路探索結果が示してある。図２７の光ネットワークにおいて、コネクション制限違反を考慮し、制約条件を生成して数理計画法によって経路算出を行うと、図２８に示すように経路が求まる。
【０２２０】
このように、上記で説明した数理計画法によって経路算出を行うと、コネクション制限数を満たすように適切な経路結果を得ることができる。また、ペナルティ制限を満たすように適切な経路結果を得ることができる。さらに、削除コネクションを選定して経路算出を行う方法に対し、経路算出時間を短縮することができる。
【０２２１】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、光ネットワーク設計装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【０２２２】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０２２３】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０２２４】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０２２５】
以上の実施の形態に開示された技術には、以下の付記に示す技術が含まれる。
（付記１） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出部と、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出部と、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成部と、
前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【０２２６】
（付記２） 前記制約条件生成部は、
前記コネクション制限数に基づいて、前記コネクション制限数を満たすように前記トラフィックパスが採用されるための第１の制約条件と、
前記余裕算出部によって算出された前記ペナルティ余裕および前記追加算出部によって算出された前記追加ペナルティに基づいて、前記トラフィックパスの通過する前記ポートを前記置換ポートに置換しても前記ペナルティ制限を満たす前記トラフィックパスが採用されるための第２の制約条件と、
前記ポートを前記置換ポートに置換したときの前記迂回経路に前記非対称光ハブが含まれる場合、前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記迂回経路に含まれる前記非対称光ハブの所定のコネクションを通過する前記トラフィックパスが採用されるための第３の制約条件と、
を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２２７】
（付記３） 前記制約条件生成部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２２８】
（付記４） 前記制約条件生成部は、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２２９】
（付記５） 前記第２の経路算出部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出できない場合に、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３０】
（付記６） 前記制約条件生成部は、前記非対称光ハブのコネクションを通過している前記第１の経路算出部によって算出された前記トラフィックパスの数に応じて、前記非対称光ハブのコネクションが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３１】
（付記７） 前記制約条件生成部は、前記第１の経路算出部によって算出された前記トラフィックパスのコネクションが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３２】
（付記８） 前記制約条件生成部は、前記第１の経路算出部によって算出された前記トラフィックパスが複数の前記非対称光ハブを通過する場合、前記非対称光ハブ間の前記第１の経路算出部によって算出された前記トラフィックパスが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３３】
（付記９） 前記制約条件生成部は、前記迂回経路に２つの前記非対称光ハブが含まれる場合、前記迂回経路とは別の別迂回経路を探索し、探索した前記別迂回経路も前記トラフィックパスとして採用されるように前記制約条件を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３４】
（付記１０） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成部と、
前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成部と、
前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【０２３５】
（付記１１） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
仮設計した前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出し、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出し、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記ペナルティ余裕、前記追加ペナルティ、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【０２３６】
（付記１２） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
前記非対称光ハブごとにおいて、仮設計した前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成し、
探索した前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記迂回経路情報、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【０２３７】
（付記１３） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計プログラムにおいて、
コンピュータを、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出手段、
前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出手段、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出手段、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成手段、
前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成手段、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出手段、
として機能させることを特徴とする光ネットワーク設計プログラム。
【０２３８】
（付記１４） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計プログラムにおいて、
コンピュータを、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出手段、
前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成手段、
前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成手段、
前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成手段、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出手段、
として機能させることを特徴とする光ネットワーク設計プログラム。
【符号の説明】
【０２３９】
１，６ 経路算出部
２ 余裕算出部
３ 追加算出部
４ 情報生成部
５ 制約条件生成部
【技術分野】
【０００１】
本件は、光ネットワークの経路設計を行う光ネットワーク設計装置および光ネットワーク設計方法に関する。
【背景技術】
【０００２】
近年、光ネットワーク分野では、光信号のまま波長単位で光信号の分岐挿入や経路切換えを行う光分岐挿入装置（ＯＡＤＭ：Optical Add-Drop Multiplexer）や波長クロスコネクト（ＷＸＣ：Wavelength Cross Connect）装置等が開発されている。このような光装置によって光ネットワークは、リング相互接続、メッシュ等といった複雑なトポロジを持つネットワーク構築が可能となり、ネットワーク規模の拡大化が進んでいる。
【０００３】
なお、従来、ＷＤＭ（Wavelength Division Multiplexing）方式とＡＷＧ（Arrayed Waveguide Grating）を用いて複数のノード間をＨＣＮ（HyperCube Network）接続するＨＣＮにおいて、容易かつ安価にネットワークの大規模化を可能にする波長多重ネットワークが提案されている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−６０９２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、光ネットワークの規模拡大化にともない、光ハブ局舎ではコネクション制限が生じる場合が多くなってきている。そのため、光ネットワークの経路設計を行う光ネットワーク設計装置は、光ネットワークの規模拡大化において適切な経路結果が得られない場合があるという問題点があった。
【０００６】
本件はこのような点に鑑みてなされたものであり、適切な経路結果を得ることができる光ネットワーク設計装置および光ネットワーク設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置が提供される。この光ネットワーク設計装置は、前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出部と、前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出部と、前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成部と、前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、を有する。
【０００８】
また、上記課題を解決するために、複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置が提供される。この光ネットワーク設計装置は、前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成部と、前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成部と、前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、を有する。
【発明の効果】
【０００９】
開示の装置および方法によれば、適切な経路結果を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】第１の実施の形態に係る光ネットワーク設計装置を示した図である。
【図２】第２の実施の形態に係る光ネットワーク設計装置のハードウェア構成例を示した図である。
【図３】経路設計が行われる光ネットワークの例を示した図である。
【図４】ハブ局舎を説明する図である。
【図５】非対称光ハブ局舎を説明する図である。
【図６】非対称光ハブ局舎の詳細例を示した図である。
【図７】光ネットワーク設計装置の機能ブロック図である。
【図８】ペナルティ余裕を説明する図である。
【図９】コネクションマトリクスＴＢのデータ構成例を示した図である。
【図１０】置換ポートを説明する図である。
【図１１】ポートマトリクスＴＢのデータ構成例を示した図である。
【図１２】変数を説明する図である。
【図１３】制約観点Ａに基づく制約条件を説明する図である。
【図１４】制約観点Ｂに基づく制約条件を説明する図である。
【図１５】複数のＡ−Ｈｕｂを通過する経路を優先的に採用する目的関数を説明する図である。
【図１６】光ネットワーク設計装置の処理動作を示したフローチャートである。
【図１７】削除コネクションを選定して経路算出を行う方法の経路算出イメージを示した図である。
【図１８】数理計画法による経路算出イメージを示した図である。
【図１９】第３の実施の形態に係る両ポート制約を説明する図である。
【図２０】光ネットワーク設計装置の処理動作を示したフローチャートである。
【図２１】第４の実施の形態に係る光ネットワーク設計装置の機能ブロック図である。
【図２２】ポートマトリクスの生成を説明する図である。
【図２３】ポートマトリクスＴＢのデータ構成例を示した図である。
【図２４】第５の実施の形態に係る代替経路を説明する図である。
【図２５】最短経路探索法によって経路算出する光ネットワークの例を示した図である。
【図２６】デマンドを示した図である。
【図２７】数理計画法によって経路算出する光ネットワークの例を示した図である。
【図２８】数理計画法によって経路算出した結果を示した図である。
【発明を実施するための形態】
【００１１】
以下、実施の形態を、図面を参照して詳細に説明する。
［第１の実施の形態］
図１は、第１の実施の形態に係る光ネットワーク設計装置を示した図である。図１に示すように、光ネットワーク設計装置は、経路算出部１，６、余裕算出部２、追加算出部３、情報生成部４、および制約条件生成部５を有している。
【００１２】
経路算出部１は、非対称光ハブのコネクション制限数に依存せずに光ネットワークにおけるトラフィックパスを仮設計する。
余裕算出部２は、経路算出部１によって仮設計されたトラフィックパスのペナルティ制限に対するペナルティ余裕を算出する。ペナルティ制限とは、例えば、トラフィックパスに認められるホップ数や伝送遅延量である。
【００１３】
追加算出部３は、非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する。
情報生成部４は、迂回経路に非対称光ハブが含まれる場合、迂回経路に含まれている非対称光ハブに関する非対称光ハブ情報を生成する。例えば、情報生成部４は、迂回経路に含まれている非対称光ハブの迂回経路が通過するコネクション情報を生成する。
【００１４】
制約条件生成部５は、コネクション制限数、余裕算出部２によって算出されたペナルティ余裕、追加算出部３によって算出された追加ペナルティ、および情報生成部４によって生成された非対称光ハブ情報に基づいて、コネクション制限数とペナルティ制限とを満たすトラフィックパスが採用されるための制約条件を生成する。
【００１５】
経路算出部６は、制約条件生成部５によって生成された制約条件に基づいて、数理計画法によりトラフィックパスを算出する。
このように、光ネットワーク設計装置は、コネクション制限数、ペナルティ余裕、追加ペナルティ、および非対称光ハブ情報に基づいて、コネクション制限数とペナルティ制限とを満たすトラフィックパスが採用されるための制約条件を生成する。そして、光ネットワーク設計装置は、生成した制約条件に基づいて、数理計画法により最終的なトラフィックパスを算出するようにした。これにより、光ネットワーク設計装置は、適切な経路結果を得ることができる。例えば、コネクション制限数およびペナルティ制限を満たす経路結果を得ることができる。
【００１６】
［第２の実施の形態］
次に、第２の実施の形態を、図面を参照して詳細に説明する。
図２は、第２の実施の形態に係る光ネットワーク設計装置のハードウェア構成例を示した図である。光ネットワーク設計装置１０は、ＣＰＵ（Central Processing Unit）１１によって装置全体が制御されている。ＣＰＵ１１には、バス１８を介してＲＡＭ（Random Access Memory）１２と複数の周辺機器が接続されている。
【００１７】
ＲＡＭ１２は、光ネットワーク設計装置１０の主記憶装置として使用される。ＲＡＭ１２には、ＣＰＵ１１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。例えば、ＲＡＭ１２には、光ネットワークの経路設計を行うアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１２には、ＣＰＵ１１による処理に必要な各種データが格納される。
【００１８】
バス１８に接続されている周辺機器としては、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１３、グラフィック処理装置１４、入力インタフェース１５、光学ドライブ装置１６、および通信インタフェース１７がある。
【００１９】
ＨＤＤ１３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１３は、光ネットワーク設計装置１０の二次記憶装置として使用される。ＨＤＤ１３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００２０】
グラフィック処理装置１４には、モニタ１９が接続されている。グラフィック処理装置１４は、ＣＰＵ１１からの命令に従って、画像をモニタ１９の画面に表示させる。モニタ１９としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００２１】
入力インタフェース１５には、キーボード２０とマウス２１とが接続されている。入力インタフェース１５は、キーボード２０やマウス２１から送られてくる信号をＣＰＵ１１に送信する。なお、マウス２１は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００２２】
光学ドライブ装置１６は、レーザ光などを利用して、光ディスク２２に記録されたデータの読み取りを行う。光ディスク２２は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２２には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００２３】
通信インタフェース１７は、例えば、インターネットなどのネットワークに接続されている。通信インタフェース１７は、ネットワークを介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００２４】
以上のようなハードウェア構成によって、光ネットワーク設計装置１０は光ネットワークの経路設計を行うための処理機能を実現することができる。
図３は、経路設計が行われる光ネットワークの例を示した図である。図３に示す光ネットワークは、光ハブ局舎３１，４１ａ〜４５ａ，４１ｂ〜４５ｂと、その他丸で示す複数の光ハブ局舎とによって形成されている。光ハブ局舎３１は、ポートＰ０〜Ｐ５を有し、その他の光ハブ局舎も同様にポートを有している。
【００２５】
光ネットワーク設計装置１０は、光ネットワークを形成している光ハブ局舎のトポロジ情報を記憶している。トポロジ情報は、例えば、キーボード２０、マウス２１、および光ディスク２２のいずれかによって光ネットワーク設計装置１０のＨＤＤ１３に記憶することができる。また、光ネットワーク設計装置１０は、通信インタフェース１７によって光ネットワークの光ハブ局舎と通信し、光ハブ局舎からトポロジ情報を取得してＨＤＤ１３に記憶することもできる。
【００２６】
トポロジ情報には、光ハブ局舎情報、スパン情報、およびデマンド情報が含まれている。
光ハブ局舎情報には、光ハブ局舎のポート数（光ハブ局舎から出ているスパン数）、光ハブ局舎が非対称光ハブ局舎である場合にはその旨の情報とコネクション制限数（非対称光ハブ局舎およびコネクション制限数については以下で説明する）、およびコネクションの伝送遅延やコスト等の最短経路計算に必要なパラメータが含まれている。
【００２７】
スパン情報には、スパンの両端の光ハブ局舎、およびスパンの伝送遅延やコスト等の最短経路計算に必要なパラメータが含まれている。
デマンド情報には、オペレータが経路設計要求するトラフィックパスの起点および終点の光ハブ局舎の情報が含まれている。
【００２８】
光ネットワーク設計装置１０は、オペレータからの要求に応じて、デマンド（ある光ハブ局舎からある光ハブ局舎へのトラフィックパス）を設計（算出）する。
例えば、光ネットワーク設計装置１０は、オペレータから光ハブ局舎４１ａ，４１ｂを起点および終点とするデマンド、光ハブ局舎４２ａ，４２ｂを起点および終点とするデマンド、…、光ハブ局舎４５ａ，４５ｂを起点および終点とするデマンドの経路を算出するよう要求されたとする。この場合、光ネットワーク設計装置１０は、例えば、図３に示す経路Ｄ１１〜Ｄ１５を算出する。算出された経路Ｄ１１〜Ｄ１５は、例えば、モニタ１９に表示される。
【００２９】
図４は、ハブ局舎を説明する図である。図４に示す光ハブ局舎５１は、ポートＰ０〜Ｐ５を有している。光ハブ局舎５１は、ポートＰ０〜Ｐ５にコネクション制限数がないとする。
【００３０】
この場合、光ハブ局舎５１は、図４に示すようにポートＰ０〜Ｐ５のそれぞれにおいて、他のポートＰ０〜Ｐ５とフルメッシュでコネクションを張ることが可能である。
従って、例えば、図３に示す光ハブ局舎３１にコネクション制限がないとすると、図３の光ハブ局舎３１は、ポートＰ０とポートＰ１〜Ｐ５との間にコネクションを張ることができるので、光ネットワーク設計装置１０は、図３に示す経路Ｄ１１〜Ｄ１５を算出することができる。
【００３１】
図５は、非対称光ハブ局舎を説明する図である。図５に示す光ハブ局舎５２は、ポートＰ０〜Ｐ５を有している。図５に示す光ハブ局舎５２では、コネクション制限数は４であるとする。
【００３２】
この場合、光ハブ局舎５２は、コネクション制限数が４であるので、１つのポートから４つのコネクションしか張ることができない。よって、図５に示すように、ポートＰ０と、ポートＰ１〜Ｐ４との間にコネクションが張られる場合、ポートＰ０−Ｐ５ではコネクションを張ることができない。
【００３３】
従って、例えば、図３に示す光ハブ局舎３１が非対称光ハブ局舎であり、コネクション制限４であるとすると、図３の光ハブ局舎３１は、ポートＰ０とポートＰ１〜Ｐ５との間にコネクションを張ることができない。そのため、光ネットワーク設計装置１０は、図３に示す経路Ｄ１１〜Ｄ１５を算出することができない。光ネットワーク設計装置１０は、例えば、ポートＰ０とポートＰ１〜Ｐ５との間のコネクションの１つを迂回するように設計することになる。
【００３４】
なお、コネクション数が制限されている光ハブ局舎は、非対称光ハブ局舎と呼ばれる。図５の光ハブ局舎５２は、非対称光ハブ局舎である。以下では、非対称光ハブ局舎をＡ−Ｈｕｂ（Asymmetric-Hub）と呼ぶこともある。
【００３５】
図６は、非対称光ハブ局舎の詳細例を示した図である。図６には、図５に示した光ハブ局舎５２の詳細例が示してある。光ハブ局舎５２は、ＷＳＳ（Wavelength Selective Switch）５２ａａ〜５２ａｆ，５２ｂａ〜５２ｂｆを有している。光ハブ局舎５２は、例えば、ラックを有しており、ラックのシェルフにＷＳＳ５２ａａ〜５２ａｆ，５２ｂａ〜５２ｂｆの基板を搭載している。
【００３６】
図６に示すポートＰ０〜Ｐ５は、図５で示したポートＰ０〜Ｐ５に対応する。図６では、ポートＰ０〜Ｐ５がそれぞれ２つ存在しているが、これは、図６では、ポートＰ０〜Ｐ５の入出力を別々に示しているからである。
【００３７】
図５で説明したように光ハブ局舎５２のコネクション制限数は４であるとする。この場合、光ネットワーク設計装置１０は、例えば、図６の点線で示すように、５本目のデマンドに対するコネクションを設定することができない。
【００３８】
従来の光ネットワークは規模が小さく、コネクション制限違反をするような経路設計が生じることは少なかった。しかし、光ネットワークの規模は近年拡大し、経路設計するデマンド数も増大している。そのため、デマンドの経路算出の際に設定されるコネクション数も増大し、例えば、図５の点線で示すコネクションを要する場合も生じてくる。このように、光ネットワーク規模が大きくなってトポロジ情報が複雑になり、さらにコネクション制限の光ハブ局舎が多くなると、経路計算に時間がかかる。例えば、１つのデマンドの経路を算出するごとに、コネクション制限違反を判断し、コネクション制限違反が生じれば、そのデマンドに対して再計算を行っていく方法では、経路計算に時間がかかる。
【００３９】
これに対し、ＷＳＳ５２ａａ〜５２ａｆ，５２ｂａ〜５２ａｆの出力ポート数を大きくして（コネクション制限数を大きくして）、コネクション制限違反を生じないようにすることが考えられる。しかし、ＷＳＳのコスト等を考慮すると、ＷＳＳ５２ａａ〜５２ａｆ，５２ｂａ〜５２ｂｆの出力ポート数を大きくすることは望ましくない。
【００４０】
そこで、光ネットワーク設計装置１０は、非対称光ハブ局舎を含む、規模拡大された光ネットワークにおいても、経路設計時間を短縮する。また、光ネットワーク設計装置１０は、光ネットワーク全体で最適化された（以下で述べる制約条件を満たす）経路結果を得るようにする。
【００４１】
図７は、光ネットワーク設計装置の機能ブロック図である。図７に示すように、光ネットワーク設計装置１０は、トポロジ情報記憶部６１、経路算出部６２、経路情報記憶部６３、コネクションマトリクス生成部６４、コネクションマトリクスＴＢ（ＴＢ：Table）６５、ポートマトリクス生成部６６、ポートマトリクスＴＢ６７、制約条件生成部６８、および経路算出部６９を有している。
【００４２】
トポロジ情報記憶部６１には、図３で説明したトポロジ情報が記憶されている。
経路算出部６２は、例えば、ダイクストラ法などの最短経路探索法に基づき、トポロジ情報記憶部６１に記憶されているトポロジ情報を参照して、Ａ−Ｈｕｂのコネクション制限を考慮せずにデマンドの経路を算出する。経路算出部６２は、Ａ-Ｈｕｂにコネクション制限がないものとして、オペレータのデマンドに対する経路を算出する。経路算出部６２は、算出したデマンドの経路を経路情報記憶部６３に記憶する。経路算出部６２は、例えば、図１の経路算出部１に対応する。
【００４３】
コネクションマトリクス生成部６４は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してコネクションマトリクスを生成し、コネクションマトリクスＴＢ６５に記憶する。コネクションマトリクス生成部６４は、光ネットワークに含まれている全てのＡ−Ｈｕｂにおいてコネクションマトリクスを生成し、コネクションマトリクスＴＢ６５に記憶する。コネクションマトリクス生成部６４は、例えば、図１の余裕算出部２に対応する。
【００４４】
コネクションマトリクスＴＢ６５について説明する。その前に、ペナルティ制限およびペナルティ余裕について説明する。
経路算出しようとするデマンドには、予めペナルティ制限が設定される。ペナルティ制限とは、例えば、経路算出しようとするデマンドに認められるハブ局舎のホップ数や伝送遅延量である。ペナルティ余裕とは、経路算出されたデマンドのペナルティのペナルティ制限に対する余裕値である。
【００４５】
図８は、ペナルティ余裕を説明する図である。図８には、光ネットワークを形成しているＡ−Ｈｕｂ７１ａが示してある。Ａ−Ｈｕｂ７１ａは、ポートＰ０〜Ｐ８を有している。
【００４６】
また、図８には、フルメッシュでコネクションを張ることができる通常のＨｕｂ７１ｂ，７１ｃが示してある。図８に示す丸（ポートＰ０〜Ｐ８は除く）もＨｕｂを示している。また、図８には、経路７１ｄおよび経路７１ｅが示してある。経路７１ｄは、デマンドＤ２１に対する経路、経路７１ｅは、デマンドＤ２２に対する経路とする。また、図８には、Ｈｕｂ７１ｂとポートＰ４に接続されているＨｕｂとを結ぶ経路７１ｆが示してある。
【００４７】
デマンドＤ２１，Ｄ２２のペナルティ制限は、１０であるとする。また、デマンドＤ２１の経路７１ｅのペナルティは、経路算出部６２の経路算出結果により、４であったとする。また、デマンドＤ２２の経路７１ｄのペナルティは、７であったとする。この場合、デマンドＤ２１のペナルティ余裕は、１０−４より６となる。また、デマンドＤ２２のペナルティ余裕は、１０−７より３となる。
【００４８】
すなわち、ペナルティ制限は、デマンド経路に許されるペナルティ値を示している。ペナルティ余裕は、デマンド経路のペナルティのペナルティ制限に対する余裕値を示している。
【００４９】
コネクションマトリクスは、Ａ−Ｈｕｂを通過するデマンドのペナルティ余裕を示す情報である。コネクションマトリクス生成部６４は、経路算出部６２によって経路算出が行われた後、光ネットワークを形成しているＡ−Ｈｕｂの１つに着目する。コネクションマトリクス生成部６４は、着目したＡ−Ｈｕｂのコネクションごとに、Ａ−Ｈｕｂを通過するデマンドのペナルティ余裕を算出し、コネクションマトリクスＴＢ６５に記憶する。
【００５０】
コネクションマトリクス生成部６４は、Ａ−Ｈｕｂのコネクションに、複数のデマンドの経路が通過する場合には、最も小さいペナルティ余裕をコネクションマトリクスＴＢ６５に記憶する。コネクションマトリクス生成部６４は、光ネットワークを形成している全てのＡ−Ｈｕｂにおいてペナルティ余裕を算出し、コネクションマトリクスＴＢ６５に記憶する。
【００５１】
図９は、コネクションマトリクスＴＢのデータ構成例を示した図である。図９に示すように、コネクションマトリクスＴＢ６５は、縦方向および横方向にポートの欄を有している。縦方向のポートと横方向のポートは、その２つのポートでＡ−Ｈｕｂのコネクションを示す。
【００５２】
例えば、図９のコネクションマトリクスＴＢ６５は、図８のＡ−Ｈｕｂ７１ａのコネクションマトリクスを示しているとする。図９の縦方向のポートＰ５と横方向のポートＰ１は、図８のＡ−Ｈｕｂ７１ａのポートＰ１−Ｐ５のコネクションを示す。
【００５３】
横方向のポートと縦方向のポートとの交わる欄には、そのコネクションを通過しているデマンドのペナルティ余裕が記憶される。コネクションに複数のデマンドが通過している場合には、最小のペナルティ余裕が記憶される。
【００５４】
例えば、図８の例の場合、ポートＰ１−Ｐ５のコネクションに、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅが通過している。デマンドＤ２１，Ｄ２２のそれぞれのペナルティ余裕は、上記より６，３である。従って、図９に示すように、縦方向のポートＰ５と横方向のポートＰ１の欄には、ペナルティ余裕の最も小さい３が記憶される。
【００５５】
また、コネクションマトリクスＴＢ６５には、コネクションを通過しているデマンドの共通経路端のＨｕｂ情報が記憶される。
例えば、図８では、ポートＰ１−Ｐ５のコネクションに、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅが通過している。経路７１ｄ，７１ｅの共通経路端のＨｕｂは、Ｈｕｂ７１ｂ，７１ｃである。Ｈｕｂ７１ｂ，７１ｃの識別子を、例えば、Ｓ，Ｔとすると、コネクションマトリクスＴＢ６５の縦方向のポートＰ５と横方向のポートＰ１との交わる欄には、図９に示すようにＳ，Ｔが記憶される。なお、コネクションを通過しているデマンドの経路が１つの場合、その共通経路端は、デマンドの始点と終点のＨｕｂとなる。
【００５６】
以上より、コネクションマトリクスＴＢ６５は、経路算出部６２によって算出されたデマンド経路のペナルティ制限に対する余裕値を示し、Ａ−Ｈｕｂのコネクションを通過しているデマンド経路を迂回経路に迂回させる場合の、迂回経路で許すことのできるペナルティの最大値を示している。
【００５７】
例えば、経路算出部６２が光ネットワークの経路算出を行ったとする。その結果、図８に示すように、デマンドＤ２１，Ｄ２２の経路として、経路７１ｄ，７１ｅが算出され、かつ、Ａ−Ｈｕｂ７１ａのポートＰ１がコネクション制限違反であったとする。この場合、ポートＰ１のコネクション違反は、例えば、ポートＰ１−Ｐ５のコネクションを通過しているデマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅを、経路７１ｆによってポートＰ４に迂回させ（ポートＰ１をポートＰ４に置換させ）、ポートＰ４−Ｐ５にコネクションを張ることによって回避できる。
【００５８】
ここで、ポートＰ１−Ｐ５のコネクションを通過していたデマンドＤ２１，Ｄ２２のペナルティ余裕は、コネクションマトリクスＴＢ６５を参照することにより、最大３であることが分かる。これにより、迂回経路で許されるペナルティは、最大３であることが分かる。
【００５９】
従って、経路７１ｆのペナルティが３以下であれば、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅを、経路７１ｆおよびポートＰ４−Ｐ５に迂回させることができる。つまり、デマンドＤ２１，Ｄ２２の経路７１ｄ，７１ｅを経路７１ｆに迂回させても、経路７１ｄ，７１ｅのペナルティ制限は守られる。
【００６０】
図７の説明に戻る。ポートマトリクス生成部６６は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してポートマトリクスを生成し、ポートマトリクスＴＢ６７に記憶する。ポートマトリクス生成部６６は、光ネットワークに含まれている全てのＡ−Ｈｕｂにおいてポートマトリクスを生成し、ポートマトリクスＴＢ６７に記憶する。
【００６１】
ポートマトリクスＴＢ６７について説明する。その前に、Ａ−Ｈｕｂのポートの置換ポートについて説明する。
ポートマトリクス生成部６６は、経路算出部６２によって経路算出が行われた後、光ネットワークを形成しているＡ−Ｈｕｂの１つに着目する。ポートマトリクス生成部６６は、着目したＡ−Ｈｕｂの各ポートにおいて、置換ポートを算出する。置換ポートとは、Ａ−Ｈｕｂを通過する経路のポートを、そのＡ−Ｈｕｂの別のポートに置き換えることができるポートをいう。ポートマトリクス生成部６６は、例えば、図１の追加算出部３および情報生成部４に対応する。
【００６２】
図１０は、置換ポートを説明する図である。図１０には、光ネットワークを形成しているＡ−Ｈｕｂ７２ａが示してある。Ａ−Ｈｕｂ７２ａは、ポートＰ０〜Ｐ８を有している。
【００６３】
また、図１０には、Ｈｕｂ７２ｂ，７２ｃ，７２ｅ，７２ｇが示してある。また、図１０には、Ａ−Ｈｕｂ７２ｄ，７２ｆが示してある。Ａ−Ｈｕｂ７２ｄ，７２ｆの識別子は、例えば、それぞれＸ，Ｙとする。
【００６４】
置換ポートを見つけるには、まず、着目しているＡ−Ｈｕｂに最も近いＨｕｂに着目する。例えば、図１０の場合、Ａ−Ｈｕｂ７２ａに着目したとすると、Ｈｕｂ７２ｂ，７２ｃ，７２ｅ，７２ｇ、Ａ−Ｈｕｂ７２ｄ，７２ｆ、ポートＰ６に接続されているＨｕｂ、およびポートＰ７，Ｐ８に接続されているＨｕｂに着目する。
【００６５】
次いで、着目したＨｕｂの間を結ぶ経路が存在するか探索する。経路探索は、例えば、ダイクストラ法などの最短経路探索法を用いる。図１０の例の場合、例えば、Ｈｕｂ７２ｂ，７２ｃ間に経路が存在する。また、Ａ−Ｈｕｂ７２ｄを介して、Ｈｕｂ７２ｃ，７２ｅ間に経路が存在する。また、Ａ−Ｈｕｂ７２ｆを介して、Ｈｕｂ７２ｅ，７２ｇ間に経路が存在する。
【００６６】
着目したＨｕｂにそれらを結ぶ経路が存在する場合、着目したＨｕｂと接続されているＡ−Ｈｕｂのポートは、互いに置換ポートとなる。図１０の例では、例えば、Ａ−Ｈｕｂ７２ａのポートＰ１を、Ａ−Ｈｕｂ７２ａの別のポートに置き換えることができるポートは、ポートＰ０，Ｐ４，Ｐ５となる。すなわち、ポートＰ１の置換ポートは、ポートＰ０，Ｐ４，Ｐ５となる。
【００６７】
Ａ−Ｈｕｂのあるポートに置換ポートが存在するということは、ポート間に迂回経路が存在することを意味する。例えば、図１０において、ポートＰ１の置換ポートは、ポートＰ０，Ｐ４，Ｐ５であるので、ポートＰ１−Ｐ０、ポートＰ１−Ｐ４、およびポートＰ１−Ｐ５には迂回経路が存在している。
【００６８】
これにより、Ａ−Ｈｕｂのポートにコネクション制限違反が生じた場合、算出したデマンド経路を迂回経路に迂回させ、置換ポートを通過させることにより、コネクション制限違反が生じたポートのコネクション制限違反を解消することができる。
【００６９】
例えば、図１０において、経路算出部６２により、Ｈｕｂ７２ｃ、Ａ−Ｈｕｂ７２ａのポートＰ１，Ｐ５、およびＨｕｂ７２ｇを通過するデマンド経路が複数算出されたとする。また、ポートＰ１は、コネクション制限違反であるとする。この場合、例えば、算出された経路の一部を、Ｈｕｂ７２ｃ、Ａ−Ｈｕｂ７２ｄ、およびＨｕｂ７２ｅの迂回経路に通過させ、さらに、Ａ−Ｈｕｂ７２ａのポートＰ４−Ｐ５にコネクションを張ることにより、ポートＰ０のコネクション制限違反を解消できる。
【００７０】
ポートマトリクス生成部６６は、次のようにして置換ポートを算出する。ポートマトリクス生成部６６は、Ａ−Ｈｕｂ７２ａの各ポートＰ０−Ｐ８から最も近い（ホップ数の最も小さい）Ｈｕｂを取得し、取得したＨｕｂ間で、例えば、ダイクストラ法などの最短経路探索法を実行する。最短経路探索法で経路が見つかれば、そのＨｕｂと接続されているポートは、互いに置換ポートとなる。
【００７１】
例えば、図１０に示すＨｕｂ７２ｂ，７２ｃは、Ａ−Ｈｕｂ７２ａから最も近いＨｕｂである。ポートマトリクス生成部６６は、最短経路探索法でＨｕｂ７２ｂ，７２ｃ間の最短経路（迂回経路）を算出する。図１０の例では、Ｈｕｂ７２ｂ，７２ｃは直接接続されており、最短経路が求まる。従って、Ｈｕｂ７２ｂと接続されているポートＰ０の置換ポートは、ポートＰ１となる。また、Ｈｕｂ７２ｃと接続されているポートＰ１の置換ポートは、ポートＰ０となる。
【００７２】
同様に、図１０に示すＨｕｂ７２ｃ，７２ｅは、Ａ−Ｈｕｂ７２ａから最も近いＨｕｂである。ポートマトリクス生成部６６は、最短経路探索法でＨｕｂ７２ｃ，７２ｅ間の最短経路を算出する。図１０の例では、Ｈｕｂ７２ｃ，７２ｅは、Ａ−Ｈｕｂ７２ｄを介して接続されており、最短経路が求まる。従って、Ｈｕｂ７２ｃと接続されているポートＰ１の置換ポートは、ポートＰ４となる。また、Ｈｕｂ７２ｅと接続されているポートＰ４の置換ポートは、ポートＰ１となる。
【００７３】
また、図１０に示すＨｕｂ７２ｃと、Ａ−Ｈｕｂ７２ａのポートＰ２に接続されているＨｕｂは、Ａ−Ｈｕｂ７２ａから最も近いＨｕｂである。ポートマトリクス生成部６６は、最短経路探索法でＨｕｂ７２ｃとポートＰ２に接続されているＨｕｂ間の最短経路を算出する。図１０の例では、Ｈｕｂ７２ｃとポートＰ２に接続されているＨｕｂ間には、経路が存在しないため、最短経路は求まらない。従って、ポートＰ１，Ｐ２は、それぞれ置換ポートとならない。
【００７４】
図１１は、ポートマトリクスＴＢのデータ構成例を示した図である。図１１に示すように、ポートマトリクスＴＢ６７は、縦方向および横方向にポートの欄を有している。縦方向のポートは、対象ポートを示し、横方向のポートは、対象ポートの置換ポートを示している。なお、図１１のポートマトリクスＴＢ６７は、図１０に示すＡ−Ｈｕｂ７２ａのポートマトリクスＴＢを示している。
【００７５】
対象ポートと置換ポートとの交わる欄には、対象ポートと置換ポートを結ぶ迂回経路のペナルティが記憶される。以下では、迂回経路のペナルティを追加ペナルティと呼ぶこともある。
【００７６】
例えば、図１０において、Ａ−Ｈｕｂ７２ａの対象ポートＰ１と置換ポートＰ４を結ぶ迂回経路のペナルティは、２である（図１０ではＨｏｐ数で示している）。従って、図１１の対象ポートＰ１と置換ポートＰ４の交わる欄には、追加ペナルティ２が記憶されている。
【００７７】
また、対象ポートと置換ポートとの交わる欄には、対象ポートと置換ポートを結ぶ迂回経路にＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂの情報が記憶される。また、迂回経路が通過するＡ−Ｈｕｂのポート（コネクション）情報が記憶される。
【００７８】
例えば、図１０において、Ａ−Ｈｕｂ７２ａの対象ポートＰ１と置換ポートＰ４を結ぶ迂回経路には、Ａ−Ｈｕｂ７２ｄが含まれる。従って、図１１の対象ポートＰ１と置換ポートＰ４の交わる欄には、Ａ−Ｈｕｂ７２ｄの情報（識別子Ｘ）が記憶されている。また、迂回経路は、Ａ−Ｈｕｂ７２ｄのポートＰ２，Ｐ３を通過している。従って、図１１の対象ポートＰ１と置換ポートＰ４の交わる欄には、ポートＰ２，Ｐ３の情報が記憶されている。
【００７９】
ポートマトリクス生成部６６は、上述した迂回経路の算出の際に、迂回経路の追加ペナルティを算出する。また、ポートマトリクス生成部６６は、上述した迂回経路の算出の際に、追加経路に含まれるＡ−Ｈｕｂの情報およびＡ−Ｈｕｂのポートの情報を算出する。そして、ポートマトリクス生成部６６は、図１１に示すようなポートマトリクスＴＢ６７を生成する。
【００８０】
以上より、ポートマトリクスＴＢ６７は、Ａ−Ｈｕｂを通過しているデマンド経路が通過しているポートを、別のポートに置き換えることができるポート（置換ポート）の情報を記憶している。また、ポートマトリクスＴＢ６７は、ポートを置換ポートに置き換えたときの迂回経路に生じるペナルティ（追加ペナルティ）を記憶している。これにより、例えば、ポートＰ０は、ポートマトリクスＴＢ６７を参照することにより、ポートＰ１，Ｐ４，Ｐ５のいずれかに置き換えることができることが分かる。また、このポート置き換えを行うには、それぞれ、ペナルティ１，３，５の迂回経路を経由することが分かる。また、ポートＰ０をポートＰ５に置き換える場合には、迂回経路に識別子Ｘ，ＹのＡ−Ｈｕｂ７２ｄ，７２ｆが含まれることが分かる。また、Ａ−Ｈｕｂ７２ｄでは、ポートＰ２，Ｐ３を通過することが分かる。Ａ−Ｈｕｂ７２ｆでは、ポートＰ１−Ｐ５を通過することが分かる。
【００８１】
図７の説明に戻る。制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、制約条件を生成する。また、制約条件生成部６８は、目的関数を生成する。制約条件生成部６８は、例えば、図１の制約条件生成部５に対応する。制約条件および目的関数については以下で詳細に説明する。
【００８２】
経路算出部６９は、制約条件生成部６８によって生成された制約条件および目的関数を満たすデマンドの経路を、数理計画法を用いて算出する。経路算出部６９は、例えば、図１の経路算出部６に対応する。
【００８３】
制約条件について説明する。制約条件生成部６８の生成する制約条件は、大きく２つに分けられる。１つ目は、各Ａ−Ｈｕｂのコネクション制限数に関する制約条件である。２つ目は、迂回経路に関する制約条件である。
【００８４】
２つ目の迂回経路に関する制約条件は、次の制約観点Ａ，Ｂに基づき生成される。
［制約観点Ａ］ポート（デマンド経路が通過しているＡ−Ｈｕｂのポート）を迂回することにより生じる追加ペナルティを考慮しても、デマンド経路のペナルティがペナルティ制限を越えない。
【００８５】
制約観点Ａは、あるデマンド経路を迂回経路に迂回させる場合（あるデマンドの経路が通過しているＡ−Ｈｕｂのポートを置換ポートに置換させる場合）、迂回経路もペナルティ制限を満たすようにするという観点から制約条件を生成することを示している。
【００８６】
［制約観点Ｂ］現在着目している迂回経路にＡ−Ｈｕｂが含まれる場合には、このＡ−Ｈｕｂで使用されるコネクションを使用する。
図１１で説明したように、ポートコネクションＴＢ６７の迂回経路にＡ−Ｈｕｂが含まれる場合の追加ペナルティは、最短経路探索法によって求められたＡ−Ｈｕｂのコネクションを通過した場合の値である。よって、ポートコネクションＴＢ６７に記憶されているＡ−Ｈｕｂのコネクションを通過しない場合、迂回経路の追加ペナルティが異なる場合が生じる。制約観点Ｂは、迂回経路にＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂで使用されるコネクションを使用するという観点から制約条件を生成することを示している。
【００８７】
以下、制約条件について具体的に説明する。制約条件生成部６８は、光ネットワークを形成しているＡ−Ｈｕｂの１つに着目する。制約条件生成部６８は、着目したＡ−Ｈｕｂ内のコネクション候補となる変数ＳAhub（ｘ，ｙ）を生成する。ｘ，ｙは、着目しているＡ−Ｈｕｂ内のポートを示し、ｘ≠ｙである。
【００８８】
変数ＳAhub（ｘ，ｙ）は、０または１の値をとり、経路算出部６９によって０，１が求まる。１は、例えば、ポートｘ，ｙ間のコネクションが採用されたことを示し、０は、ポートｘ，ｙ間のコネクションが採用されなかったことを示す。ＳAhub（ｘ，ｙ）のＡｈｕｂは、Ａ−Ｈｕｂ名を示し、どのＡ−Ｈｕｂの変数であるかを示す。
【００８９】
図１２は、変数を説明する図である。図１２に示すＡ−Ｈｕｂ７３の変数ＳAhub（ｘ，ｙ）は、経路算出部６９によって以下のように求まったとする。
ＳAhub（Ｐ０，Ｐ１）＝１
ＳAhub（Ｐ０，Ｐ２）＝１
ＳAhub（Ｐ０，Ｐ７）＝１
ＳAhub（Ｐ５，Ｐ７）＝１
ＳAhub（Ｐ２，Ｐ７）＝１
ＳAhub（Ｐ０，Ｐ３）＝０
ＳAhub（Ｐ０，Ｐ４）＝０
ＳAhub（Ｐ０，Ｐ６）＝０
ＳAhub（Ｐ６，Ｐ７）＝０
ＳAhub（Ｐ３，Ｐ７）＝０
この場合、Ａ−Ｈｕｂ７３は、図１２に示すように、コネクションが張られることになる。
【００９０】
制約条件生成部６８は、算出しようとするデマンドの経路が、Ａ−Ｈｕｂにてコネクション制限数を満たすための制約条件（１つ目の制約条件）を生成する。すなわち、制約条件生成部６８は、経路算出部６９により、コネクション制限数を満たすようにトラフィックパスが採用されるための制約条件を生成する。コネクション制限数を満たすための制約条件は、次の式（１）で示される。
【００９１】
【数１】
【００９２】
式（１）のコネクション制限数Ｌkは、トポロジ情報に含まれており、例えば、オペレータによって入力される。
式（１）の左辺は、変数ＳAhub（ｘ，ｋ）の全加算値を示している。変数ＳAhub（ｘ，ｋ）は、上記したように０，１の値をとる。従って、式（１）は、その左辺がＬk以下になるようにするということは、Ａ−Ｈｕｂがコネクション制限数Ｌkを満たすように、コネクションを張るということを示している。
【００９３】
例えば、式（１）のＬkが５の場合、図１２のＡ−Ｈｕｂのコネクションは、式（１）の制約条件を満たしていることになる（上記のＳAhub（Ｐ０，Ｐ１）〜ＳAhub（Ｐ３，Ｐ７）を加算すると１となる）。
【００９４】
制約条件生成部６８は、迂回経路に関する制約条件（２つ目の制約条件）を生成する。まず、制約観点Ａに基づく制約条件の生成について説明する。制約条件生成部６８は、あるデマンドの経路を迂回させる場合、制約観点Ａに基づき、迂回する経路もペナルティ制限を満たすようにするための制約条件を生成する。制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照して、制約観点Ａの制約条件を生成する。
【００９５】
制約観点Ａに基づく制約条件は、次の式（２）で示される。なお、式（２）では、変数ＳAhub（ｘ，ｙ）のＡｈｕｂを省略している。
【００９６】
【数２】
【００９７】
式（２）のＡk，Ａlは、ポートの代替可能候補集合を示す。ポートの代替可能候補集合とは、経路を置換ポートにより迂回させたとき、迂回経路がペナルティ制限を満たす置換ポートの集合をいう。例えば、図１１において、ポートＰ１の置換ポートは、ポートＰ０，Ｐ４，Ｐ５となる。経路のペナルティ余裕が３である場合、ポートＰ５は、迂回経路の候補となりえない。よって、この場合、ポートＰ１の代替可能候補集合は、ポートＰ０，Ｐ４となる。
【００９８】
式（２）の左辺の第１項は、元コネクション（経路算出部６２で求まったコネクション）を示している。第２項は、元コネクションの一方のポートを、代替可能候補集合のポートに置き換えた代替コネクションの集合を示している。第３項は、元コネクションの他方のポートを、代替可能候補集合のポートに置き換えた代替コネクションの集合を示している。
【００９９】
式（２）は、左辺の値が１以上になるようにコネクションを求めるよう制約していることを示している。すなわち、式（２）は、着目しているＡ−Ｈｕｂにおいて、少なくとも、元コネクションか、元コネクションの一方のポートを代替可能候補集合のポートに置き換えたコネクション集合のいずれかのコネクションか、または元コネクションの他方のポートを代替可能候補集合のポートに置き換えたコネクション集合のいずれかのコネクションかが選ばれるように制約している。
【０１００】
図１３は、制約観点Ａに基づく制約条件を説明する図である。図１３において図１０と同じものには同じ符号を付し、その説明を省略する。
経路算出部６２によって、あるデマンドの経路７４ａ，７４ｂが求まったとする。Ｈｕｂ７２ｃ，７２ｇの識別子は、Ｓ，Ｔとする。ペナルティ制限は１０とし、経路７４ａ，７４ｂのペナルティはそれぞれ７，４であったとする。この場合、図１３のＡ−Ｈｕｂ７２ａのコネクションマトリクスＴＢ６５は、図９に示すようになる。また、図１３のＡ−Ｈｕｂ７２ａのポートマトリクスＴＢ６７は、図１１に示すようになる。
【０１０１】
制約条件生成部６８は、ポートＰ１−Ｐ５のコネクションの迂回経路の１つとして、ポートマトリクスＴＢ６７を参照し、ポートＰ４を取得する。また、制約条件生成部６８は、ポートマトリクスＴＢ６７を参照し、ポートＰ１−Ｐ４の追加ペナルティ２を取得する。
【０１０２】
制約条件生成部６８は、コネクションマトリクスＴＢ６５を参照して、ポートＰ１−Ｐ５を通過する経路のペナルティ余裕３を取得する。追加ペナルティ２は、ペナルティ余裕３より小さいので、制約条件生成部６８は、ポートＰ４を代替可能候補集合Ａkとする。
【０１０３】
制約条件生成部６８は、上記と同様にして、ポートＰ１の代替候補となり得るポートを、ポートマトリクスＴＢ６７を参照して取得する。上記例の場合、ポートＰ０は、ポートＰ１の代替候補となり、ポートＰ５は、ポートＰ１の代替候補となりえない。
【０１０４】
すなわち、制約条件生成部６８は、ポートＰ１の置換ポートを取得し、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、取得した置換ポートにおける迂回経路がペナルティ制限を満たすか否か判断する。制約条件生成部６８は、置換ポートの迂回経路がペナルティ制限を満たせば、その置換ポートを代替可能候補集合Ａkとする。同様に、制約条件生成部６８は、ポートＰ５の代替可能候補集合Ａlを算出する。
【０１０５】
制約条件生成部６８は、上記のようにして代替可能候補集合Ａk，Ａlを算出し、式（２）に示す制約条件を生成する。なお、上記では、制約条件生成部６８は、ポートマトリクスＴＢ６７を参照して置換ポートを取得し、次いでコネクションマトリクスＴＢ６５を参照して代替可能候補集合を求めたが、算出順番は逆でもよい。例えば、制約条件生成部６８は、コネクションマトリクスＴＢ６５を参照してペナルティ余裕を取得し、次いでポートマトリクスＴＢ６７を参照して代替可能候補集合を求めてもよい。
【０１０６】
次に、制約観点Ｂに基づく制約条件の生成について説明する。制約条件生成部６８は、迂回経路にＡ−Ｈｕｂが含まれる場合、さらに、制約観点Ｂに基づき制約条件を生成する。例えば、図１３の例の場合、Ｈｕｂ７２ｃ，７２ｅを結ぶ迂回経路には、Ａ−Ｈｕｂ７２ｄが含まれる。そして、Ａ−Ｈｕｂ７２ｄでは、迂回経路はポートＰ２−Ｐ３のコネクションを通過する。従って、この場合、制約条件生成部６８は、Ａ−Ｈｕｂ７２ｄを通過する迂回経路が採用される場合、Ａ−Ｈｕｂ７２ｄのポートＰ２−Ｐ３を通過するように制約条件を生成する。
【０１０７】
図１４は、制約観点Ｂに基づく制約条件を説明する図である。図１４には、光ネットワークを形成しているＡ−Ｈｕｂ７５ａ〜７５ｃが示してある。Ａ−Ｈｕｂ７５ａ〜７５ｃのそれぞれは、ポートＰ０〜Ｐ８を有している。経路７５ｅは、経路７５ｄの迂回経路を示し、経路７５ｅの通過するＡ−Ｈｕｂ７５ｂでは、ポートＰ０−Ｐ４にコネクションが張られ、Ａ−Ｈｕｂ７５ｃでは、ポートＰ１−Ｐ８にコネクションが張られるものとする。
【０１０８】
図１４において、経路７５ｄの迂回経路として経路７５ｅが採用候補となる場合、経路７５ｅは、Ａ−Ｈｕｂ７５ｂのポートＰ０−Ｐ４を通過し、Ａ−Ｈｕｂ７５ｃのポートＰ１−Ｐ８を通過する必要がある。経路７５ｅは、図１０で説明したように、ダイクストラ法などの最短経路探索法によって算出され、通過するＡ−Ｈｕｂ７５ｂ，７５ｃの情報と、そのコネクションの情報とがポートマトリクスＴＢ６７に記憶され、そのコネクションを通過した場合における追加ペナルティがポートマトリクスＴＢ６７に記憶されているからである。
【０１０９】
制約条件生成部６８は、ポートマトリクスＴＢ６７を参照し、制約観点Ｂに基づく制約条件を生成する。制約条件生成部６８は、上記したように、迂回経路にＡ−Ｈｕｂが含まれる場合、ポートマトリクスＴＢ６７に記憶されているコネクションを通過する制約条件を生成する。
【０１１０】
例えば、制約条件生成部６８は、図１４の例の場合、次の式（３）に示す制約条件を生成する。
【０１１１】
【数３】
【０１１２】
式（３）の変数Ｓに示すＡ−Ｈｕｂ１，Ａ−Ｈｕｂ２，Ａ−Ｈｕｂ３は、それぞれの変数Ｓが図１４のＡ−Ｈｕｂ７５ａ〜７５ｃにおける変数であることを示している。
式（３）の第１項の変数Ｓは、図１４のＡ−Ｈｕｂ７５ａのポートＰ２−Ｐ５のコネクションの変数を示している。第１項の変数Ｓに乗算されている値２は、経路７５ｅの迂回経路に含まれるＡ−Ｈｕｂの数を示している。仮に経路７５ｅの迂回経路にＡ−Ｈｕｂが３つ含まれている場合には、第１項の変数Ｓには、３が乗算される。
【０１１３】
式（３）の第２項の変数Ｓは、図１４のＡ−Ｈｕｂ７５ｂのポートＰ０−Ｐ４のコネクションの変数を示している。式（３）の第３項の変数Ｓは、図１４のＡ−Ｈｕｂ７５ｃのポートＰ１−Ｐ８のコネクションの変数を示している。
【０１１４】
式（３）は、式（３）の左辺の値が０以下であることを制約条件としている。これは、Ａ−Ｈｕｂ７５ａのポートＰ２−Ｐ５のコネクションが採用されるならば、Ａ−Ｈｕｂ７５ｂのポートＰ０−Ｐ４のコネクションが採用され、かつ、Ａ−Ｈｕｂ７５ｃのポートＰ１−Ｐ８のコネクションが採用されることを示している。
【０１１５】
例えば、Ａ−Ｈｕｂ７５ａのポートＰ２−Ｐ５のコネクションが採用されるならば、式（３）のＳA-Hub1（Ｐ２，Ｐ５）は１となる。この場合、式（３）を満たすには、式（３）の第２項、第３項が１とならなければならい。すなわち、第２項、第３項は、次の関係を満たさなければならない。
【０１１６】
ＳA-Hub2（Ｐ０，Ｐ４）＝１
ＳA-Hub3（Ｐ１，Ｐ８）＝１
これは、Ａ−Ｈｕｂ７５ｂ（Ａ−Ｈｕｂ２）のＰ０−Ｐ４のコネクションが採用され、Ａ−Ｈｕｂ７５ｃ（Ａ−Ｈｕｂ３）のポートＰ１−Ｐ８のコネクションが採用されることを示している。
【０１１７】
制約条件生成部６８は、Ａ−Ｈｕｂを含む迂回経路に対して、上記と同様にして制約観点Ｂに基づく制約条件を生成する。
目的関数について説明する。制約条件生成部６８は、目的関数を生成する。目的関数は、例えば、次の式（４）で示される。
【０１１８】
【数４】
【０１１９】
式（４）は、光ネットワーク内の全てのコネクション候補となる変数Ｓに重み付けＣAhub,x,yを付加し、それを加算したことを示している。式（４）では、目的関数を「Maximize」として指定しているが、場合によっては、「Minimize」を指定することもできる。例えば、Ａ−Ｈｕｂにおける使用コネクション数を最小に抑えたいという場合、「Minimize」を指定することができる。なお、式（４）のＣAhub,x,yのＡｈｕｂは、Ａ−Ｈｕｂ名を示し、どのＡ−Ｈｕｂの重み付けであるかを示す。
【０１２０】
式（４）の各変数Ｓに対する重み付けの配分次第で、経路算出部６９は、様々な経路結果を得ることができる。式（５）は、重み付けの一例を示している。なお、式（５）では、ＣAhub,x,yのＡｈｕｂを省略している。
【０１２１】
【数５】
【０１２２】
式（５）のＤx,yは、最初の仮設計（経路算出部６２による経路算出）における、Ａ−Ｈｕｂの各コネクションに属しているデマンド経路の本数を示している。このパラメータを目的関数に導入することで、経路算出部６９は、デマンド経路の本数が多いＡ−Ｈｕｂのコネクションについては、なるべく現状を維持するように（デマンド経路が迂回しないように）経路算出する。
【０１２３】
Ｒx,yは、最初の仮設計で存在していたコネクションであるか否かを示すフラグである。このパラメータを目的関数に導入することで、経路算出部６９は、最初の仮設計で採用されたコネクションをなるべく優先的に採用するよう設計する。
【０１２４】
式（５）のαx,yは、最初の仮設計で全く使用されていなかったコネクションに対する値である。このパラメータを目的関数に導入することで、経路算出部６９は、最初の仮設計で使用されていないコネクションもある優先度で採用できるようにすることができる。
【０１２５】
ＨＤx,yは、最初の仮設計において複数のＡ−Ｈｕｂを通過するデマンド経路がある場合、このＡ−Ｈｕｂ間の経路を優先的に採用するためのパラメータである。このパラメータを目的関数に導入することで、経路算出部６９は、最初の仮設計において設計された複数のＡ−Ｈｕｂ間を通過する経路において、優先的に採用できるようにすることができる。
【０１２６】
図１５は、複数のＡ−Ｈｕｂを通過する経路を優先的に採用する目的関数を説明する図である。図１５には、光ネットワークを形成しているＡ−Ｈｕｂ７６ａ，７６ｂが示してある。経路７６ｃは、経路算出部６２によって算出された経路を示している。
【０１２７】
最初の仮設計で算出された経路７６ｃは、Ａ−Ｈｕｂ７６ａ，７６ｂを通過している。この場合、制約条件生成部６８は、Ａ−Ｈｕｂ７６ａ，７６ｂ間の経路については、経路算出部６９によって優先的に採用されるようにＨＤx,Yを調整する。
【０１２８】
例えば、制約条件生成部６８は、Ａ−Ｈｕｂ７６ａのポートＰ５に属するコネクションのＨＤx,Yと、Ａ−Ｈｕｂ７６ｂのポートＰ０に属するコネクションのＨＤx,yについては、２を設定する。その他のコネクションについては、ＨＤx,yについては、１を設定する。この場合、経路算出部６９は、Ａ−Ｈｕｂ７６ａのポートＰ５と、Ａ−Ｈｕｂ７６ｂのポートＰ０との間の経路が優先的に採用されるように経路設計を行う。
【０１２９】
なお、上記の目的関数の設定は一例であり、上記に限るものではない。
図１６は、光ネットワーク設計装置の処理動作を示したフローチャートである。
［ステップＳ１ａ，Ｓ１ｂ］経路算出部６２は、オペレータから要求のあったデマンドの数分、ステップＳ２の処理を行う。
【０１３０】
［ステップＳ２］経路算出部６２は、トポロジ情報記憶部６１を参照し、オペレータから要求のあったデマンドの経路探索を行う。経路算出部６２は、コネクション制限を考慮せずにデマンドの経路探索を行う。経路算出部６２は、算出したデマンド経路の結果を経路情報記憶部６３に記憶する。
【０１３１】
［ステップＳ３］経路算出部６２は、算出したデマンドの経路が通過するＡ−Ｈｕｂにおいて、コネクション制限違反があったか否か判断する。経路算出部６２は、コネクション制限違反がない場合、処理を終了する。すなわち、オペレータの要求するデマンド経路が求まったので、経路算出部６２は処理を終了する。経路算出部６２は、コネクション制限違反がある場合、ステップＳ４ａへ進む。
【０１３２】
［ステップＳ４ａ，Ｓ４ｂ］コネクションマトリクス生成部６４およびポートマトリクス生成部６６は、コネクション制限違反のあったＡ−Ｈｕｂのそれぞれにおいて、以下のステップＳ５〜Ｓ７の処理を行う。
【０１３３】
［ステップＳ５］コネクションマトリクス生成部６４は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してコネクションマトリクスを生成し、コネクションマトリクスＴＢ６５に記憶する。
【０１３４】
［ステップＳ６ａ，６ｂ］ポートマトリクス生成部６６は、Ａ−Ｈｕｂの各ポート間において、以下のステップＳ７の処理を行う。なお、この処理は、Ａ−Ｈｕｂのポート数をＰとすると、１／２＊Ｐ（Ｐ−１）回繰り返すことになる。
【０１３５】
［ステップＳ７］ポートマトリクス生成部６６は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してポートマトリクスを生成し、ポートマトリクスＴＢ６７に記憶する。
【０１３６】
［ステップＳ８］制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、数理計画モデルを生成する。すなわち、制約条件生成部６８は、制約条件と目的関数を生成する。
【０１３７】
［ステップＳ９］経路算出部６９は、制約条件生成部６８によって生成された数理計画モデルに基づき、数理計画法によって経路を算出する。
上記で説明した経路算出（数理計画法による経路算出）の計算量について説明する。経路探索法には、上記の方法以外に、例えば、Ａ−Ｈｕｂのコネクション制限を考慮せずに経路算出し、算出した経路のコネクション制限違反を判断し、違反したＡ−Ｈｕｂにて削除コネクションを選定して削除し、再度経路算出を行う方法がある。以下では、この削除コネクションを選定して経路算出を行う方法と、上記の数理計画法による経路算出法の計算量について説明する。
【０１３８】
削除コネクションを選定して経路算出を行う方法での計算量は、次の式（６）で示される。
【０１３９】
【数６】
【０１４０】
Ｎは、光ネットワーク内のＡ−Ｈｕｂの総数を示す。Ｃnewは、削除コネクションの数を示す。ＤC＿newは、削除コネクションに属しているデマンド経路の本数を示している。
ここで、上記の数理計画法による経路算出法の計算量との比較を行うために、Ｃnewの演算量をＡ−Ｈｕｂのポート数で置き換えることを考える。
【０１４１】
まず、削除コネクション数は、最も多い場合を考えると、Ｃnew＝フルメッシュコネクション組合数−設定可能コネクション数で示される。ポートのコネクション制限数を４とすると、削除コネクション数は、次の式（７）で示される。
【０１４２】
【数７】
【０１４３】
Ｐは、Ａ−Ｈｕｂのポート数を示す。すなわち、削除コネクション数Ｃnewは、ポート数の２乗に比例すると考えることができる。
従って、削除コネクションを選定して経路算出する方法の計算量は、式（６），（７）より式（８）に示すようになる。
【０１４４】
【数８】
【０１４５】
一方、上記の数理計画法による経路算出法の計算量は、図１６のステップ６ａ，６ｂで説明したように、１つのＡ−Ｈｕｂでは、１／２＊Ｐ（Ｐ−１）で示される。従って、Ａ−ＨｕｂがＮ個ある場合には、その計算量は次の式（９）で示すことができる。
【０１４６】
【数９】
【０１４７】
式（８）と式（９）を比較すると、削除コネクションを選定して経路算出を行う方法では、光ネットワーク内のデマンドの数に依存することが分かる。従って、上記の数理計画法による経路算出法の方が、計算量が少なく、経路算出時間を短縮できる。
【０１４８】
なお、Ａ−Ｈｕｂのコネクション制限を考慮せずに経路算出する部分においては、両者とも計算量は同じである。また、削除コネクションを選定して経路算出を行う方法に対し、上記の数理計画法による経路算出法では、数理計画法を用いた処理が加わる。数理計画法部分の計算量については、光ネットワーク上に３つのＡ−Ｈｕｂ（実際の光ネットワークに存在し得ると考えられる数）が存在する場合について計算したところ、０．１ｓ程度であり、十分微小と考えられる。
【０１４９】
図１７は、削除コネクションを選定して経路算出を行う方法の経路算出イメージを示した図である。図１７には、光ネットワークが示してある。削除コネクションを選定して経路算出を行う方法では、図１７に示すように、Ａ−Ｈｕｂ７７ａ，７７ｂ，７７ｃ，…と１つずつ逐次的に、コネクション制限違反を解消するようにコネクションを調整する。
【０１５０】
図１８は、数理計画法による経路算出イメージを示した図である。図１８には、光ネットワークが示してある。上記で説明した経路算出法では、図１８に示すように、光ネットワークを形成しているＡ−Ｈｕｂ７８ａ〜７８ｅの全てのコネクション制限を解消するための条件（制約条件）を出し、１回の数理計画法で経路を求める。これにより、上記の経路算出法では、ネットワーク全体で最適化された経路を算出することが可能となる。
【０１５１】
このように、光ネットワーク設計装置１０は、コネクション制限数とペナルティ制限とを満たすデマンド経路が採用されるための制約条件を生成する。そして、光ネットワーク設計装置１０は、生成した制約条件に基づいて、数理計画法により最終的なデマンド経路を算出するようにした。これにより、光ネットワーク設計装置は、適切な経路結果を得ることができる。例えば、コネクション制限数およびペナルティ制限を満たす経路結果を得ることができる。
【０１５２】
［第３の実施の形態］
次に、第３の実施の形態を、図面を参照して詳細に説明する。第２の実施の形態では、コネクションの片ポートのみを切替えるように制約条件を生成し、経路算出を行った。第３の実施の形態では、コネクションの両ポートを切替えるように制約条件を生成し、経路算出を行う。
【０１５３】
図１９は、第３の実施の形態に係る両ポート制約を説明する図である。図１９には、光ネットワークを形成しているＡ−Ｈｕｂ８１ａが示してある。Ａ−Ｈｕｂ８１ａは、ポートＰ０〜Ｐ８を有している。また、図１９には、最初の仮設計で算出された経路８１ｂと、その迂回経路を示した経路８１ｃ，８１ｄが示してある。
【０１５４】
最初に仮設計された経路８１ｂは、Ａ−Ｈｕｂ８１ａのポートＰ１−Ｐ５のコネクションを通過している。第２の実施の形態で説明した片ポート制約は、このポートＰ１−Ｐ５の一方を置換ポートに置き換え、経路８１ｂを経路８１ｃ，８１ｄに迂回させる。
【０１５５】
例えば、図１９に示すポートＰ２−Ｐ５のコネクション８１ｅは、ポートＰ１をポートＰ２の置換ポートに置き換えている。これにより、経路８１ｂは、経路８１ｃに迂回している。また、図１９に示すポートＰ１−Ｐ７のコネクション８１ｆは、ポートＰ５をポートＰ７の置換ポートに置き換えている。これにより、経路８１ｂは、経路８１ｄに迂回している。
【０１５６】
両ポート制約は、最初に仮設計された経路のコネクションのポートの両方を置換ポートに置き換える。
例えば、図１９に示す最初に仮設計された経路８１ｂのコネクションのポートＰ１−Ｐ５の両方を、ポートＰ２，Ｐ７に置き換える。すなわち、両ポート制約は、図１９に示すポートＰ２−Ｐ７のコネクション８１ｇを張るようにする。
【０１５７】
なお、第３の実施の形態に係る光ネットワーク設計装置のハードウェア構成および機能ブロックは、図２で示したハードウェア構成例および図７で示した機能ブロックと同様であり、その説明を省略する。ただし、第３の実施の形態に係る光ネットワーク設計装置１０では、機能ブロックの制約条件生成部６８の機能が一部異なる。第３の実施の形態では、制約条件生成部６８は、コネクションの両ポートを代替したコネクションも採用されるように制約条件を生成する。
【０１５８】
第３の実施の形態に係る制約条件生成部６８は、第２の実施の形態と同様に、各Ａ−Ｈｕｂのコネクション制限数に関する制約条件と、迂回経路に関する制約条件とを生成する。迂回経路に関する制約条件に関しては、制約観点Ａ，Ｂに基づいて制約条件を生成する。
【０１５９】
第２の実施の形態では、制約条件生成部６８は、あるデマンドの経路を迂回させる場合、制約観点Ａに基づき、迂回する経路もペナルティ制限を満たすようにするための制約条件を生成する。第３の実施の形態においても制約条件生成部６８は、同様に制約条件を生成するが、コネクションの両ポートを代替したコネクションも採用されるように制約条件を生成する。
【０１６０】
制約観点Ａに基づく制約条件は、次の式（１０）で示される。なお、式（１０）では、変数ＳAhub（ｘ，ｙ）のＡｈｕｂを省略している。
【０１６１】
【数１０】
【０１６２】
式（１０）では、式（２）に対し、左辺に第４項が追加されている。第４項の代替可能候補集合Ａk,lは、コネクションの両ポートの置換可能な（経路を迂回させることが可能な）置換ポート集合を示し、式（１０）は、コネクションの両ポートを代替可能候補集合Ａk,lのポートに置き換えたコネクションも採用されることを示している。制約条件生成部６８は、コネクションの両ポートにおいてコネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、第４項を含む制約条件を生成する。その他の制約条件の生成に関しては第２の実施の形態と同様であるのでその説明を省略する。
【０１６３】
図２０は、光ネットワーク設計装置の処理動作を示したフローチャートである。
図２０のステップＳ１ａ〜Ｓ７は、図１６のステップＳ１ａ〜Ｓ７と同様であり、その説明を省略する。
【０１６４】
［ステップＳ２１］制約条件生成部６８は、コネクションマトリクスＴＢ６５およびポートマトリクスＴＢ６７を参照し、数理計画モデルを生成する。すなわち、制約条件生成部６８は、制約条件と目的関数を生成する。制約条件生成部６８は、式（２）に示す片ポート制約の制約条件と、式（１０）に示す両ポート制約の制約条件とを生成する。
【０１６５】
［ステップＳ２２］経路算出部６９は、制約条件生成部６８によって生成された数理計画モデルに基づき、数理計画法によって経路を算出する。経路算出部６９は、片ポート制約により、経路算出を行う。
【０１６６】
［ステップＳ２３］経路算出部６９は、経路算出を算出できたか否か判断する。すなわち、経路算出部６９は、経路設計できたか否か判断する。経路算出部６９は、経路設計できた場合、処理を終了する。経路算出部６９は、経路設計できなかった場合、ステップＳ２４へ進む。
【０１６７】
［ステップＳ２４］経路算出部６９は、制約条件生成部６８によって生成された数理計画モデルに基づき、数理計画法によって経路を算出する。経路算出部６９は、両ポート制約により、経路算出を行う。
【０１６８】
このように、光ネットワーク設計装置１０は、両ポート制約によっても経路設計することができる。
また、光ネットワーク設計装置１０は、片ポート制約によって経路設計できなかった場合に両ポート制約によって経路設計するので、片ポート制約によって経路設計できた場合、経路計算時間を短縮することができる。
【０１６９】
なお、上記では、光ネットワーク設計装置１０は、片ポート制約によって経路設計できなかった場合、両ポート制約による経路設計を行うとしたが、両ポート制約による経路設計のみを行ってもよい。例えば、図２０において、ステップＳ２２，２３の処理を省略してもよい。
【０１７０】
［第４の実施の形態］
次に、第４の実施の形態を、図面を参照して詳細に説明する。第４の実施の形態では、ポートマトリクスのみを生成して経路算出を行う場合について説明する。第４の実施の形態に係る光ネットワーク設計装置のハードウェア構成は、図２で示したハードウェア構成例と同様であり、その説明を省略する。
【０１７１】
図２１は、第４の実施の形態に係る光ネットワーク設計装置の機能ブロック図である。図２１において、図７と同じものには同じ符号を付し、その説明を省略する。
図２１に示すように、光ネットワーク設計装置１０は、ポートマトリクス生成部９１およびポートマトリクスＴＢ９２を有している。
【０１７２】
ポートマトリクス生成部９１は、トポロジ情報記憶部６１および経路情報記憶部６３を参照してポートマトリクスを生成し、ポートマトリクスＴＢ９２に記憶する。ポートマトリクス生成部９１は、光ネットワークに含まれている全てのＡ−Ｈｕｂにおいてポートマトリクスを生成し、ポートマトリクスＴＢ９２に記憶する。
【０１７３】
図２２は、ポートマトリクスの生成を説明する図である。図２２には、光ネットワークを形成しているＡ−Ｈｕｂ１０１ａ，１０１ｄ，１０１ｅおよびＨｕｂ１０１ｂ，１０１ｃ，１０１ｆが示してある。Ａ−Ｈｕｂ１０１ｄ，１０１ｅの識別子をそれぞれＸ，Ｙとする。また、図２２には、経路１０２ａ〜１０２ｄが示してある。
【０１７４】
第２の実施の形態では、着目しているＡ−Ｈｕｂに最も近いＨｕｂに着目し、その着目したＨｕｂ間での迂回経路を探索した。第４の実施の形態では、着目しているＡ−Ｈｕｂを通過しているデマンド経路の共通経路端のＨｕｂに着目し、その着目したＨｕｂ間で迂回経路を探索する。
【０１７５】
例えば、図２２の例では、経路算出部６２によって、経路１０２ａ〜１０２ｄが算出されたとする。経路１０２ａ，１０２ｂの共通経路端のＨｕｂは、Ｈｕｂ１０１ｃ，１０１ｆである。また、経路１０２ｃ，１０２ｄの共通経路端のＨｕｂは、Ｈｕｂ１０１ｂ，１０１ｃである。ポートマトリクス生成部９１は、これら共通経路端のＨｕｂの情報を取得する。なお、コネクションを通過しているデマンド経路が１つの場合、その共通経路端は、デマンドの始点と終点のＨｕｂとなる。
【０１７６】
ポートマトリクス生成部９１は、共通経路端のＨｕｂを取得すると、その共通経路端のＨｕｂ間で迂回経路を探索する。ポートマトリクス生成部９１は、着目しているＡ−Ｈｕｂにおいて、共通経路端の経路が通過しているコネクションは通過することができないとして迂回経路を探索する。迂回経路の探索は、例えば、ダイクストラ法などの最短経路探索法で行う。
【０１７７】
例えば、図２２において、経路１０２ａ，１０２ｂの共通経路端のＨｕｂは、Ｈｕｂ１０１ｃ，１０１ｆである。また、共通経路端のＨｕｂ１０１ｃ，１０１ｆの経路が通過しているコネクションは、ポートＰ１−Ｐ５である。よってこの場合、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ１−Ｐ５のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｃ，１０１ｆ間の迂回経路をダイクストラ法によって探索する。
【０１７８】
また、図２２において、経路１０２ｃ，１０２ｄの共通経路端のＨｕｂは、Ｈｕｂ１０１ｂ，１０１ｃである。また、共通経路端のＨｕｂ１０１ｂ，１０１ｃの経路が通過しているコネクションは、ポートＰ０−Ｐ１である。よってこの場合、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ１のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｂ，１０１ｃ間の迂回経路をダイクストラ法によって探索する。
【０１７９】
ポートマトリクス生成部９１は、算出した迂回経路によっても、元の経路のペナルティ制限を越えない場合、迂回後のポート情報をポートマトリクスＴＢ９２に記憶する。また、ポートマトリクス生成部９１は、迂回経路に着目しているＡ−Ｈｕｂ以外のＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂの情報と、そのＡ−Ｈｕｂの迂回経路が通過しているコネクションの情報とをポートマトリクスＴＢ９２に記憶する。
【０１８０】
すなわち、ポートマトリクス生成部９１は、デマンド経路の共通経路端にて、デマンド経路が通過したコネクションを通過しない、ペナルティ制限を満たす迂回経路を探索し、探索した迂回経路の迂回経路情報を算出してポートマトリクスＴＢ９２に記憶する。また、ポートマトリクス生成部９１は、探索した迂回経路にＡ−Ｈｕｂが含まれる場合、Ａ−Ｈｕｂに関する情報を算出してポートマトリクスＴＢ９２に記憶する。
【０１８１】
図２３は、ポートマトリクスＴＢのデータ構成例を示した図である。図２３に示すように、ポートマトリクスＴＢ９２は、対象コネクションの欄および迂回経路の欄を有している。
【０１８２】
対象コネクションの欄には、迂回経路の対象となるコネクションの情報が記憶される。対象コネクションの欄には、例えば、着目しているＡ−Ｈｕｂが有しているポートの全組み合わせが記憶される。
【０１８３】
迂回経路の欄には、対象コネクションに対する迂回経路の情報が記憶される。例えば、迂回経路の欄には、着目しているＡ−Ｈｕｂにおいて、迂回経路が通過するコネクションの情報と、迂回経路にＡ−Ｈｕｂが含まれる場合、そのＡ−Ｈｕｂの情報と、そのＡ−Ｈｕｂの迂回経路が通過しているコネクションの情報が記憶される。
【０１８４】
例えば、図２２の例において、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ１−Ｐ５のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｃ，１０１ｆ間の迂回経路を探索する。その結果、ポートマトリクス生成部９１は、Ｈｕｂ１０１ｃ、Ａ−Ｈｕｂ１０１ａのポートＰ１−Ｐ４のコネクション、ポートＰ４に接続されたＨｕｂ、Ａ−Ｈｕｂ１０１ｅ、およびＨｕｂ１０１ｆを通過する迂回経路を得たとする。また、迂回経路が通過したＡ−Ｈｕｂ１０１ｅでは、ポートＰ１−Ｐ５のコネクションに迂回経路が通過したとする。この迂回経路は、ペナルティ制限を越えなかったとする。
【０１８５】
この場合、ポートマトリクス生成部９１は、ポートマトリクスＴＢ９２の対象コネクションのポートＰ１−Ｐ５（迂回前に通過していたコネクション）の欄に対応する迂回経路の欄に、迂回後のポートＰ１−Ｐ４の情報を記憶する。また、算出した迂回経路には、Ａ−Ｈｕｂ１０１ａ以外のＡ−Ｈｕｂ１０１ｅが含まれているので、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ｅの情報（例えば、識別子Ｙ）と、Ａ−Ｈｕｂ１０１ｅの迂回経路が通過するコネクションの情報（ポートＰ１−Ｐ５）とをポートマトリクスＴＢ９２の迂回経路の欄に記憶する。
【０１８６】
なお、Ｈｕｂ１０１ｃ，１０１ｆ間を結ぶ迂回経路のペナルティがペナルティ制限を越えていた場合は、対象コネクションＰ１−Ｐ５に対応する迂回経路の欄には、迂回経路なしを示す情報が記憶される。
【０１８７】
また、図２２の例において、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ１のコネクションは通過できないとして、共通経路端のＨｕｂ１０１ｂ，１０１ｃ間の迂回経路を探索する。その結果、ポートマトリクス生成部９１は、Ｈｕｂ１０１ｂおよびＨｕｂ１０１ｃを通過する迂回経路を得たとする。この迂回経路は、ペナルティ制限を越えなかったとする。
【０１８８】
この場合、ポートマトリクス生成部９１は、ポートマトリクスＴＢ９２の対象コネクションのポートＰ０−Ｐ１（迂回前に通過していたコネクション）の欄に対応する迂回経路の欄に、迂回後の情報を記憶する。上記迂回経路では、Ａ−Ｈｕｂ１０１ａを通過しないので、ポートマトリクス生成部９１は、Ａ−Ｈｕｂ通過なしという情報を記憶する。すなわち、ポートマトリクス生成部９１は、迂回経路はＡ−Ｈｕｂ１０１ａを通過しないという情報を記憶する。
【０１８９】
なお、Ｈｕｂ１０１ｂ，１０１ｃ間を結ぶ迂回経路のペナルティがペナルティ制限を越えていた場合は、対象コネクションＰ０−Ｐ１に対応する迂回経路の欄には、迂回経路なしを示す情報が記憶される。
【０１９０】
図２２の例では、ポートＰ０−Ｐ２コネクションに対する迂回経路は存在しない（図２２では、ポートＰ０−Ｐ２を通過する共通経路端の図示は省略している）。従って、対象コネクションのＰ０−Ｐ２に対応する迂回経路の欄には、迂回経路なしという情報が記憶される。
【０１９１】
制約条件生成部６８は、第２の実施の形態で説明したのと同様に目的関数を生成する。また、制約条件生成部６８は、ポートマトリクスＴＢ９２を参照して、第２の実施の形態で説明したのと同様に制約条件を生成する。すなわち、制約条件生成部６８は、各Ａ−Ｈｕｂのコネクション制限数に関する制約条件と、迂回経路に関する制約条件とを生成する。制約条件生成部６８は、迂回経路に関する制約条件については、制約観点Ａ，Ｂに基づいて生成する。
【０１９２】
例えば、ポートマトリクＴＢ９２に図２３で示した情報が記憶されているとする。制約条件生成部６８は、対象コネクション単位で制約条件を生成する。
・Ｐ０−Ｐ１の制約条件
経路１０２ｃ，１０２ｄは、Ａ−Ｈｕｂ１０１ａを通過しなくても迂回することができる。従って、例えば、オペレータから着目しているＡ−Ｈｕｂ１０１ａの迂回許可の設定がされていれば、制約条件生成部６８は、制約条件は生成しない。すなわち、変数ＳA-Hub（Ｐ０−Ｐ１）は、０でも１でもよい。なお、ＳA-HubのＡ−Ｈｕｂは、Ａ−Ｈｕｂ１０１ａを示している。
【０１９３】
一方、例えば、オペレータから着目しているＡ−Ｈｕｂ１０１ａの迂回不許可の設定がされていれば、制約条件生成部６８は、次の式（１１）に示す制約条件を生成する。
【０１９４】
【数１１】
【０１９５】
すなわち、制約条件生成部６８は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ１のコネクションが採用されるように制約条件を生成する。
・Ｐ０−Ｐ２の制約条件
図２３のポートマトリクスＴＢ９２より、ポートＰ０−Ｐ２のコネクションには、迂回経路が存在しない。従って、制約条件生成部６８は、制約観点Ａから次の式（１２）に示す制約条件を生成する。
【０１９６】
【数１２】
【０１９７】
すなわち、制約条件生成部６８は、Ａ−Ｈｕｂ１０１ａのポートＰ０−Ｐ２のコネクションが採用されるように制約条件を生成する。
・Ｐ１−Ｐ５の制約条件
図２３のポートマトリクスＴＢ９２より、ポートＰ１−Ｐ５のコネクションには、迂回経路が存在する。従って、制約条件生成部６８は、制約観点Ａから次の式（１３）に示す制約条件を生成する。
【０１９８】
【数１３】
【０１９９】
すなわち、制約条件生成部６８は、ポートＰ１−Ｐ５のコネクションまたはポートＰ１−Ｐ４のコネクションのどちらかまたは両方が採用されるように制約条件を生成する。
また、ポートＰ１−Ｐ４の迂回経路には、識別子ＹのＡ−Ｈｕｂ（図２２のＡ−Ｈｕｂ１０１ｅ）が含まれる。迂回経路は、このＡ−Ｈｕｂ１０１ｅのポートＰ１−Ｐ５のコネクションを通過しなければならないので、制約条件生成部６８は、制約観点Ｂから次の式（１４）に示す制約条件を生成する。
【０２００】
【数１４】
【０２０１】
式（１４）の左辺第２項のＡ−ＨｕｂＹは、Ａ−Ｈｕｂ１０１ｅを示している。
すなわち、制約条件生成部６８は、ポートＰ１−Ｐ４のコネクションが採用されるならば（ＳA-Hub（Ｐ１−Ｐ４）＝１）、Ａ−Ｈｕｂ１０１ｅのポートＰ１−Ｐ５のコネクションが採用される（ＳA-HubY（Ｐ１−Ｐ５）＝１）ように制約条件を生成する。
【０２０２】
なお、経路算出部６９は、第２の実施の形態で説明したのと同様に、制約条件生成部６８が生成した制約条件と目的関数とに基づいて、数理計画法に基づき経路を算出する。
このように、光ネットワーク設計装置１０は、コネクション制限数、迂回経路情報（例えば、着目しているＡ−Ｈｕｂ１０１ａの迂回経路が通過するポート情報）、およびＡ−Ｈｕｂの情報（例えば、迂回経路に含まれるＡ−Ｈｕｂ１０１ｅの情報）に基づいて制約条件を生成する。そして、光ネットワーク設計装置１０は、生成した制約条件に基づいて、数理計画法により最終的なデマンド経路を算出するようにした。これにより、光ネットワーク設計装置１０は、適切な経路結果を得ることができる。例えば、コネクション制限数およびペナルティ制限を満たす経路結果を得ることができる。
【０２０３】
［第５の実施の形態］
次に、第５の実施の形態を、図面を参照して詳細に説明する。第２の実施の形態では、迂回経路に隣接するＡ−Ｈｕｂ（隣接するＡ−Ｈｕｂ間にＨｕｂが含まれていてもよい）が含まれる場合、そのＡ−Ｈｕｂ間の経路は固定的である。例えば、図１４に示すように、隣接するＡ−Ｈｕｂ７５ｂ，７５ｃ間の経路は固定的である。第５の実施の形態では、迂回経路に含まれる隣接するＡ−Ｈｕｂ間の代替経路を、例えば、ダイクストラ法などの最短経路探索法によって探索し、その代替経路も迂回経路として採用されるようにする。
【０２０４】
第５の実施の形態に係る光ネットワーク設計装置のハードウェア構成および機能ブロックは、図２で示したハードウェア構成例および図７で示した機能ブロックと同様であり、その説明を省略する。ただし、第５の実施の形態では、機能ブロックの制約条件生成部６８の機能が一部異なる。
【０２０５】
図２４は、第５の実施の形態に係る代替経路を説明する図である。図２４には、光ネットワークを形成しているＡ−Ｈｕｂ１１１ａ，１１１ｂが示してある。Ａ−Ｈｕｂ１１１ａ，１１１ｂは、ポートＰ０〜Ｐ８を有している。図２４に示す丸は（ポートＰ０〜Ｐ８は除く）、Ｈｕｂを示している。Ａ−Ｈｕｂ１１１ａ，１１１ｂの識別子は、それぞれＸ，Ｙとする。
【０２０６】
経路１１１ｅは、ポートマトリクス生成部６６によって算出された迂回経路を示している。経路１１１ｅに含まれるＡ−Ｈｕｂ１１１ａ，１１１ｂの情報（識別子Ｘ，Ｙ）およびコネクションの情報（ポートＰ０−Ｐ４、ポートＰ１−Ｐ４）は、ポートマトリクスＴＢ６７に記憶されている。Ａ−Ｈｕｂ１１１ａ，１１１ｂは、その間に２つのＨｕｂが含まれているがＡ−Ｈｕｂを含んでいないので隣接するＡ−Ｈｕｂである。
【０２０７】
制約条件生成部６８は、経路１１１ｅ上において、隣接するＡ−Ｈｕｂ１１１ａ，１１１ｂの最も近いＨｕｂ１１１ｃ，１１１ｄ間で代替経路を算出する。例えば、制約条件生成部６８は、ダイクストラ法などの最短経路探索法によってＨｕｂ１１１ｃ，１１１ｄ間の代替経路を算出する。ここでは、図２４に示すように、代替経路として経路１１１ｆが算出されたとする。
【０２０８】
制約条件生成部６８は、算出した代替経路のペナルティがペナルティ制限を満たす場合、迂回経路と代替経路の一方が採用されるように制約条件を生成する。制約条件は、制約観点Ｂに基づいて生成される。
【０２０９】
図２４の例の場合、制約条件生成部６８は、次の式（１５）〜（１７）に示す制約条件を生成する。
【０２１０】
【数１５】
【０２１１】
式（１５）の変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）は、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４と、Ａ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路を示す。従って、例えば、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）の値が１の場合、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４と、Ａ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路が採用されたことを示す。また、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）の値が０の場合、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４とＡ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路が採用されなかったことを示す。
【０２１２】
なお、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）のＡＨＸは、図２４のＡ−Ｈｕｂ１１１ａ（識別子Ｘ）を示し、ＡＨＹは、Ａ−Ｈｕｂ１１１ｂ（識別子Ｙ）を示す。また、式（１５）の変数ＳA-HubX，ＳA-HubYのＡ−ＨｕｂＸ，Ａ−ＨｕｂＹは、図２４のＡ−Ｈｕｂ１１１ａ，１１１ｂを示す。
【０２１３】
式（１５）は、式（１５）の左辺の値が０以下であることを制約条件としている。これは、図２４のＡ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４とＡ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４とを通過する経路が採用されるならば、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ４のコネクションとＡ−Ｈｕｂ１１１ｂのポートＰ１−Ｐ４のコネクションとが採用されることを示している。
【０２１４】
式（１６）の変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ５，ＡＨＹ＿Ｐ０Ｐ４）は、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ５と、Ａ−Ｈｕｂ１１１ｂのポートＰ０−Ｐ４とを通過する経路を示す。式（１６）は、図２４のＡ−Ｈｕｂ１１１ａのポートＰ０−Ｐ５とＡ−Ｈｕｂ１１１ｂのポートＰ０−Ｐ４とを通過する経路が採用されるならば、Ａ−Ｈｕｂ１１１ａのポートＰ０−Ｐ５のコネクションとＡ−Ｈｕｂ１１１ｂのポートＰ０−Ｐ４のコネクションとが採用されることを示している。
【０２１５】
式（１７）は、変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ４，ＡＨＹ＿Ｐ１Ｐ４）の経路と変数ＳＳ（ＡＨＸ＿Ｐ０Ｐ５，ＡＨＹ＿Ｐ０Ｐ４）の経路の少なくとも一方が採用されることを示している。すなわち、図２４に示す経路１１１ｅか経路１１１ｆの少なくとも一方が採用されることを示している。
【０２１６】
このように、迂回経路の代替経路を採用することも可能である。これにより、経路設計できる可能性を高めることができる。
以下、上記実施の形態で説明した数理計画法による経路算出の効果の一例について説明する。
【０２１７】
図２５は、最短経路探索法によって経路算出する光ネットワークの例を示した図である。図２５に示すアルファベットは、Ｈｕｂの識別子を示している。図２５のＢ，Ｃ，Ｇ，Ｈは、Ａ−Ｈｕｂである。図２５中の数字は、ペナルティを示している。
【０２１８】
図２６は、デマンドを示した図である。図２５の経路探索は、図２６のデマンドに対して、経路探索を行ったものとする。
図２５の光ネットワークにおいて、コネクション制限違反を考慮せずに、ダイクストラ法などの最短経路探索法によって経路探索を行うと、図２５の黒丸に示すように、Ａ−ＨｕｂＢ，Ｃ，Ｇ，Ｈにて、コネクション制限違反が生じる。なお、図２５では、コネクション制限数を４としている。
【０２１９】
図２７は、数理計画法によって経路算出する光ネットワークの例を示した図である。図２７の光ネットワークは、図２５の光ネットワークと同様であり、その説明を省略する。
図２８は、数理計画法によって経路算出した結果を示した図である。図２８には、図２７の光ネットワークにおいて、コネクション制限数を４とし、ペナルティ制限を２４とした場合の経路探索結果が示してある。図２７の光ネットワークにおいて、コネクション制限違反を考慮し、制約条件を生成して数理計画法によって経路算出を行うと、図２８に示すように経路が求まる。
【０２２０】
このように、上記で説明した数理計画法によって経路算出を行うと、コネクション制限数を満たすように適切な経路結果を得ることができる。また、ペナルティ制限を満たすように適切な経路結果を得ることができる。さらに、削除コネクションを選定して経路算出を行う方法に対し、経路算出時間を短縮することができる。
【０２２１】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、光ネットワーク設計装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【０２２２】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０２２３】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０２２４】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０２２５】
以上の実施の形態に開示された技術には、以下の付記に示す技術が含まれる。
（付記１） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出部と、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出部と、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成部と、
前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【０２２６】
（付記２） 前記制約条件生成部は、
前記コネクション制限数に基づいて、前記コネクション制限数を満たすように前記トラフィックパスが採用されるための第１の制約条件と、
前記余裕算出部によって算出された前記ペナルティ余裕および前記追加算出部によって算出された前記追加ペナルティに基づいて、前記トラフィックパスの通過する前記ポートを前記置換ポートに置換しても前記ペナルティ制限を満たす前記トラフィックパスが採用されるための第２の制約条件と、
前記ポートを前記置換ポートに置換したときの前記迂回経路に前記非対称光ハブが含まれる場合、前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記迂回経路に含まれる前記非対称光ハブの所定のコネクションを通過する前記トラフィックパスが採用されるための第３の制約条件と、
を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２２７】
（付記３） 前記制約条件生成部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２２８】
（付記４） 前記制約条件生成部は、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２２９】
（付記５） 前記第２の経路算出部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出できない場合に、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３０】
（付記６） 前記制約条件生成部は、前記非対称光ハブのコネクションを通過している前記第１の経路算出部によって算出された前記トラフィックパスの数に応じて、前記非対称光ハブのコネクションが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３１】
（付記７） 前記制約条件生成部は、前記第１の経路算出部によって算出された前記トラフィックパスのコネクションが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３２】
（付記８） 前記制約条件生成部は、前記第１の経路算出部によって算出された前記トラフィックパスが複数の前記非対称光ハブを通過する場合、前記非対称光ハブ間の前記第１の経路算出部によって算出された前記トラフィックパスが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３３】
（付記９） 前記制約条件生成部は、前記迂回経路に２つの前記非対称光ハブが含まれる場合、前記迂回経路とは別の別迂回経路を探索し、探索した前記別迂回経路も前記トラフィックパスとして採用されるように前記制約条件を生成することを特徴とする付記１記載の光ネットワーク設計装置。
【０２３４】
（付記１０） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成部と、
前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成部と、
前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【０２３５】
（付記１１） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
仮設計した前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出し、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出し、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記ペナルティ余裕、前記追加ペナルティ、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【０２３６】
（付記１２） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
前記非対称光ハブごとにおいて、仮設計した前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成し、
探索した前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記迂回経路情報、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【０２３７】
（付記１３） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計プログラムにおいて、
コンピュータを、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出手段、
前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出手段、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出手段、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成手段、
前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成手段、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出手段、
として機能させることを特徴とする光ネットワーク設計プログラム。
【０２３８】
（付記１４） 複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計プログラムにおいて、
コンピュータを、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出手段、
前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成手段、
前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成手段、
前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成手段、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出手段、
として機能させることを特徴とする光ネットワーク設計プログラム。
【符号の説明】
【０２３９】
１，６ 経路算出部
２ 余裕算出部
３ 追加算出部
４ 情報生成部
５ 制約条件生成部
【特許請求の範囲】
【請求項１】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出部と、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出部と、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成部と、
前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【請求項２】
前記制約条件生成部は、
前記コネクション制限数に基づいて、前記コネクション制限数を満たすように前記トラフィックパスが採用されるための第１の制約条件と、
前記余裕算出部によって算出された前記ペナルティ余裕および前記追加算出部によって算出された前記追加ペナルティに基づいて、前記トラフィックパスの通過する前記ポートを前記置換ポートに置換しても前記ペナルティ制限を満たす前記トラフィックパスが採用されるための第２の制約条件と、
前記ポートを前記置換ポートに置換したときの前記迂回経路に前記非対称光ハブが含まれる場合、前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記迂回経路に含まれる前記非対称光ハブの所定のコネクションを通過する前記トラフィックパスが採用されるための第３の制約条件と、
を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項３】
前記制約条件生成部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項４】
前記制約条件生成部は、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項５】
前記第２の経路算出部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出できない場合に、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項６】
前記制約条件生成部は、前記非対称光ハブのコネクションを通過している前記第１の経路算出部によって算出された前記トラフィックパスの数に応じて、前記非対称光ハブのコネクションが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項７】
前記制約条件生成部は、前記迂回経路に２つの前記非対称光ハブが含まれる場合、前記迂回経路とは別の別迂回経路を探索し、探索した前記別迂回経路も前記トラフィックパスとして採用されるように前記制約条件を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項８】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成部と、
前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成部と、
前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【請求項９】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
仮設計した前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出し、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出し、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記ペナルティ余裕、前記追加ペナルティ、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【請求項１０】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
前記非対称光ハブごとにおいて、仮設計した前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成し、
探索した前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記迂回経路情報、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【請求項１】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記第１の経路算出部によって仮設計された前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出する余裕算出部と、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出する追加算出部と、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成する情報生成部と、
前記コネクション制限数、前記余裕算出部によって算出された前記ペナルティ余裕、前記追加算出部によって算出された前記追加ペナルティ、および前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【請求項２】
前記制約条件生成部は、
前記コネクション制限数に基づいて、前記コネクション制限数を満たすように前記トラフィックパスが採用されるための第１の制約条件と、
前記余裕算出部によって算出された前記ペナルティ余裕および前記追加算出部によって算出された前記追加ペナルティに基づいて、前記トラフィックパスの通過する前記ポートを前記置換ポートに置換しても前記ペナルティ制限を満たす前記トラフィックパスが採用されるための第２の制約条件と、
前記ポートを前記置換ポートに置換したときの前記迂回経路に前記非対称光ハブが含まれる場合、前記情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記迂回経路に含まれる前記非対称光ハブの所定のコネクションを通過する前記トラフィックパスが採用されるための第３の制約条件と、
を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項３】
前記制約条件生成部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項４】
前記制約条件生成部は、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項５】
前記第２の経路算出部は、前記非対称光ハブのコネクションの片ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出できない場合に、前記非対称光ハブのコネクションの両ポートを前記置換ポートに置換した前記トラフィックパスが採用されるための前記制約条件に基づいて前記トラフィックパスを算出することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項６】
前記制約条件生成部は、前記非対称光ハブのコネクションを通過している前記第１の経路算出部によって算出された前記トラフィックパスの数に応じて、前記非対称光ハブのコネクションが優先して採用されるように目的関数を生成し、
前記第２の経路算出部は、前記制約条件と前記目的関数とによって、数理計画法により前記トラフィックパスを算出することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項７】
前記制約条件生成部は、前記迂回経路に２つの前記非対称光ハブが含まれる場合、前記迂回経路とは別の別迂回経路を探索し、探索した前記別迂回経路も前記トラフィックパスとして採用されるように前記制約条件を生成することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項８】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計する第１の経路算出部と、
前記非対称光ハブごとにおいて、前記第１の経路算出部によって仮設計された前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成する経路情報生成部と、
前記経路情報生成部によって探索された前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成する局舎情報生成部と、
前記コネクション制限数、前記経路情報生成部によって生成された前記迂回経路情報、および前記局舎情報生成部によって生成された前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成する制約条件生成部と、
前記制約条件生成部によって生成された前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する第２の経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【請求項９】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
仮設計した前記トラフィックパスにおけるペナルティ制限に対するペナルティ余裕を算出し、
前記非対称光ハブごとにおいて、ポートを置換ポートに置換したときの迂回経路で生じる追加ペナルティを算出し、
前記迂回経路に前記非対称光ハブが含まれる場合、前記迂回経路に含まれている前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記ペナルティ余裕、前記追加ペナルティ、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【請求項１０】
複数のポートを備えるとともに該ポート間のコネクション数が制限されている非対称光ハブを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブのコネクション制限数に依存せずに前記光ネットワークにおけるトラフィックパスを仮設計し、
前記非対称光ハブごとにおいて、仮設計した前記トラフィックパスの共通経路端にて前記トラフィックパスが通過したコネクションを通過しないペナルティ制限を満たす迂回経路を探索し、探索した前記迂回経路の迂回経路情報を生成し、
探索した前記迂回経路に前記非対称光ハブが含まれる場合、前記非対称光ハブに関する非対称光ハブ情報を生成し、
前記コネクション制限数、前記迂回経路情報、および前記非対称光ハブ情報に基づいて、前記コネクション制限数と前記ペナルティ制限とを満たす前記トラフィックパスが採用されるための制約条件を生成し、
生成した前記制約条件に基づいて、数理計画法により前記トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【公開番号】特開２０１２−４９９０２（Ｐ２０１２−４９９０２Ａ）
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願番号】特願２０１０−１９１１７３（Ｐ２０１０−１９１１７３）
【出願日】平成２２年８月２７日（２０１０．８．２７）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願日】平成２２年８月２７日（２０１０．８．２７）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]