(57)【特許請求の範囲】
【請求項１】
非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出する経路算出部と、
前記経路算出部の算出したトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する違反判断部と、
前記違反判断部によってコネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定する削除選定部と、
前記削除選定部によって選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出する再経路算出部と、
を有し、
前記削除選定部は、前記非対称光ハブサイトのコネクションの両ポートともコネクション制限数を超えているコネクションを優先して前記削除コネクションに選定することを特徴とする光ネットワーク設計装置。
【請求項２】
前記削除選定部は、優先して選定した前記削除コネクションが複数存在する場合、コネクションの両ポートのコネクション超過数の合計が大きい前記削除コネクションを優先して選定することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項３】
前記削除選定部は、前記コネクション超過数の合計が同じ前記削除コネクションが複数存在する場合、前記削除コネクションに属するトラフィックパスが少ない前記削除コネクションを優先して選定することを特徴とする請求項２記載の光ネットワーク設計装置。
【請求項４】
前記削除選定部は、前記非対称光ハブサイトのコネクションの両ポートともコネクション制限数を超えているコネクションが存在しない場合、コネクション制限数を超えているポートと反対側のポートにおけるコネクション設定余裕数の小さいコネクションを優先して前記削除コネクションに選定することを特徴とする請求項１記載の光ネットワーク設計装置。
【請求項５】
前記削除選定部は、前記コネクション設定余裕数の同じ前記削除コネクションが複数存在する場合、前記削除コネクションに属するトラフィックパスが少ない前記削除コネクションを優先して選定することを特徴とする請求項４記載の光ネットワーク設計装置。
【請求項６】
前記再経路算出部は、前記非対称光ハブサイトにおいて前記削除コネクションを削除した残りのコネクションに重み付けを行って再度トラフィックパスを算出することを特徴とする請求項１乃至５のいずれかに記載の光ネットワーク設計装置。
【請求項７】
前記再経路算出部は、前記経路算出部で算出されたトラフィックパスですでに使用されている使用コネクションに対し、コネクション制限違反とならない未使用の使用可能コネクションが優先してトラフィックパスに選ばれるよう前記重み付けを行うことを特徴とする請求項６記載の光ネットワーク設計装置。
【請求項８】
非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出し、
算出したトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断し、
コネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定し、
選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出し、
前記削除コネクションを選定する処理において、前記非対称光ハブサイトのコネクションの両ポートともコネクション制限数を超えているコネクションを優先して前記削除コネクションに選定する、
ことを特徴とする光ネットワーク設計方法。
【請求項９】
非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計プログラムにおいて、
コンピュータを、
前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出して経路情報記憶部に記憶する経路算出手段、
前記経路情報記憶部に記憶されたトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する違反判断手段、
前記違反判断手段によってコネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定する削除選定手段、
前記削除選定手段によって選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出する再経路算出手段、
として機能させ、
前記削除選定手段は、前記非対称光ハブサイトのコネクションの両ポートともコネクション制限数を超えているコネクションを優先して前記削除コネクションに選定することを特徴とする光ネットワーク設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、光ネットワークの経路設計を行う光ネットワーク設計装置、光ネットワーク設計方法、および光ネットワーク設計プログラムに関する。
【背景技術】
【０００２】
近年、光ネットワーク分野では、光信号のまま波長単位で光信号の分岐挿入や経路切換えを行う光分岐挿入装置（ＯＡＤＭ：Optical Add-Drop Multiplexer）や波長クロスコネクト（ＷＸＣ：Wavelength Cross Connect）装置等の光ハブサイトが開発されている。このような光ハブサイトによって光ネットワークは、リング相互接続、メッシュ等といった複雑なトポロジを持つネットワーク構築が可能となり、ネットワーク規模の拡大化が進んでいる。
【０００３】
なお、従来、複数の光伝送リンクが１つの光伝送装置を共用する光ネットワークにおいて、ネットワークコストを最小化する現用光パスと予備光パスの配備を高速かつ確実に求められるようにする光ネットワーク設計法が提案されている（例えば、特許文献１参照）。
【０００４】
また、従来、トラヒック変動に耐えられるネットワーク設備設計を行うことが可能な光ネットワーク設計方法が提案されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−６７０６７号公報
【特許文献２】特開２００５−８６６７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、光ネットワークを形成する光ハブサイトのポート間のコネクション数には、光ハブサイトの製造コスト等によって制限がある場合がある。そのため、光ネットワークの経路設計を行う光ネットワーク設計装置は、光ネットワークの規模拡大化おいて経路設計に支障が生じ、設計結果が得られない場合があるという問題点があった。
【０００７】
図１６は、光ネットワーク設計装置の経路設計を説明する図のその１である。図１６には、光ネットワークが示してある。光ネットワークは、光ハブサイト１０１，１１１ａ〜１１５ａ，１１１ｂ〜１１５ｂと、その他丸で示す複数の光ハブサイトとによって形成されている。光ハブサイト１０１は、ポートＰ０〜Ｐ５を有し、その他の光ハブサイトもポートを有している。
【０００８】
光ネットワーク設計装置は、光ネットワークを形成している光ハブサイトのトポロジ情報を記憶している。例えば、光ネットワーク設計装置は、図１６に示す光ハブサイトのトポロジを記憶している。
【０００９】
光ネットワーク設計装置は、オペレータの要求に応じて、ダイクストラ法などの経路探索方法に基づきトポロジ情報を参照して、ある光ハブサイトからある光ハブサイトへのトラフィックパス（以下、デマンドと呼ぶ場合もある）を設計（算出）する。
【００１０】
例えば、光ネットワーク設計装置は、オペレータから光ハブサイト１１１ａ，１１１ｂを起点および終点とするデマンド、光ハブサイト１１２ａ，１１２ｂを起点および終点とするデマンド、…、光ハブサイト１１５ａ，１１５ｂを起点および終点とするデマンドの経路を算出するよう要求されたとする。この場合例えば、光ネットワーク設計装置は、図１６に示す経路Ｄ１０１〜Ｄ１０５を算出する。
【００１１】
図１７は、光ネットワーク設計装置の経路設計を説明する図のその２である。図１７には、図１６で示した光ハブサイト１０１が示してある。図１７に示す光ハブサイト１０１は、ポートＰ０〜Ｐ５にコネクション制限数がなくコネクション制限がない。すなわち、ポートＰ０〜Ｐ５のそれぞれは、図１７に示すように他のポートＰ０〜Ｐ５とフルメッシュでコネクションを張ることが可能である。
【００１２】
光ネットワーク設計装置は、図１６で説明したのと同じデマンドの経路を算出するとする。光ネットワーク設計装置は、光ハブサイト１０１における経路を算出する際、光ハブサイト１０１にコネクション制限がないので、ポートＰ０とポートＰ１〜Ｐ５のそれぞれのコネクションを設定でき、オペレータから要求されたデマンドの経路を算出することができる。
【００１３】
図１８は、光ネットワーク設計装置の経路設計を説明する図のその３である。図１８には、図１６で示した光ハブサイト１０１が示してある。図１８に示す光ハブサイト１０１では、コネクション制限数は４であるとする。なお、ポート間のコネクション数が制限されている光ハブサイトは、非対称光ハブサイトと呼ばれる。図１８の光ハブサイト１０１は、非対称光ハブサイトである。
【００１４】
光ネットワーク設計装置は、図１６で説明したのと同じデマンドの経路を算出するとする。光ネットワーク設計装置は、光ハブサイト１０１における経路を算出する際、光ハブサイト１０１のコネクション制限数は４であるので、ポートＰ０とポートＰ１〜Ｐ５のコネクションのうち１つを設定することができず、オペレータから要求されたデマンドの経路を算出することができない。
【００１５】
例えば、光ネットワーク設計装置は、光ハブサイト１１１ａ，１１１ｂのデマンドの経路を算出する。このとき、光ネットワーク設計装置は、光ハブサイト１０１においてポートＰ０−Ｐ１のコネクションを設定したとする。以下同様にして、光ネットワーク設計装置は、光ハブサイト１１４ａ，１１４ｂのデマンドの経路を算出する。このとき、光ネットワーク設計装置は、光ハブサイト１０１においてポートＰ０−Ｐ４のコネクションを設定したとする。
【００１６】
次いで、光ネットワーク設計装置は、光ハブサイト１１５ａ，１１５ｂのデマンドの経路を算出する。このとき、光ネットワーク設計装置は、光ハブサイト１０１においてポートＰ０−Ｐ５のコネクションを設定しようとするが、ポートＰ０のコネクション数は、コネクション制限数４を超えるので、ポートＰ０−Ｐ５のコネクションを設定することができない。このため、光ネットワーク設計装置は、オペレータから要求されたデマンドの経路を算出することができない。
【００１７】
図１９は、光ハブサイトの詳細例を示した図である。図１９に示すように、光ハブサイト１０１は、ＷＳＳ（Wavelength Selective Switch）１１１ａ〜１１１ｆ，１１２ａ〜１１２ｆを有している。光ハブサイト１０１は、例えば、ラックで形成されており、ラックのシェルフにＷＳＳ１１１ａ〜１１１ｆ，１１２ａ〜１１２ｆの基板を搭載している。
【００１８】
図１９に示すポートＰ０〜Ｐ５は、図１６〜図１８で示したポートＰ０〜Ｐ５に対応する。図１９では、ポートＰ０〜Ｐ５がそれぞれ２つ存在しているが、これは、図１９では、ポートＰ０〜Ｐ５の入出力を別々に示しているからである。
【００１９】
図１８で説明したように光ハブサイト１０１のコネクション制限数は４であるとする。この場合、光ネットワーク設計装置は、例えば、図１９の点線で示すように、５本目のデマンドに対するコネクションを設定することができない。
【００２０】
すなわち、光ネットワーク設計装置は、図１７で説明したように、コネクション制限のない光ハブサイトにおいてはオペレータから要求されたデマンドの経路を設計することができる。
【００２１】
一方、光ネットワーク設計装置は、非対称光ハブサイトにおいては、例えば、トポロジ情報では６個のポートＰ０〜Ｐ５を有しているのに（ポートＰ０〜Ｐ５のそれぞれにおいて５個のコネクションが設定可能なのに）、４個のコネクションしか設定できない。そのため、図１８、図１９で説明したようにオペレータから要求されたデマンドの経路を算出することができない場合が生じる。
【００２２】
従来においては、光ネットワークの規模は小さく、コネクション制限違反をするような経路設計が生じることは少なかった。しかし、光ネットワークの規模は近年拡大化し、経路設計するデマンド数も増大する。そのため、デマンドの経路算出の際に設定されるコネクション数も増大し、例えば、上記したように図１９の点線で示すコネクションを要する場合が生じてくる。
【００２３】
これに対し、ＷＳＳ１１１ａ〜１１１ｆ，１１２ａ〜１１２ｆの出力ポート数を大きくして（コネクション制限数を大きくして）、コネクション制限違反を生じないようにすることが考えられる。しかし、光ハブサイトの製造コスト等を考慮すると、ＷＳＳ１１１ａ〜１１１ｆ，１１２ａ〜１１２ｆの出力ポート数を大きくすることは望ましくない。そのため、光ネットワーク設計装置は、光ネットワークの規模拡大化において、経路設計を行うことができない場合が生じる。
【００２４】
本件はこのような点に鑑みてなされたものであり、光ネットワークの規模が拡大しても光ネットワークの経路設計を行うことができる光ネットワーク設計装置、光ネットワーク設計方法、および光ネットワーク設計プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２５】
上記課題を解決するために、非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計装置が提供される。この光ネットワーク設計装置は、前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出する経路算出部と、前記経路算出部の算出したトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する違反判断部と、前記違反判断部によってコネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定する削除選定部と、前記削除選定部によって選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出する再経路算出部と、を有する。
【発明の効果】
【００２６】
開示の装置、方法、およびプログラムによれば、光ネットワークの規模が拡大しても光ネットワークの経路設計を行うことができる。
【図面の簡単な説明】
【００２７】
【図１】第１の実施の形態に係る光ネットワーク設計装置を示した図である。
【図２】第２の実施の形態に係る光ネットワーク設計装置のハードウェア構成例を示した図である。
【図３】光ネットワーク設計装置によって経路設計される光ネットワークの一例を示した図である。
【図４】光ネットワーク設計装置の機能ブロック図である。
【図５】Ａ−Ｈｕｂ情報を説明するためのＡ−Ｈｕｂを示した図である。
【図６】Ａ−Ｈｕｂ情報記憶部のデータ構成例を示した図である。
【図７】削除するコネクションの選定方法を説明する図である。
【図８】インポータントコネクションが２以上存在する場合の削除コネクションの選定を説明する図である。
【図９】インポータントコネクションが存在しない場合の削除コネクションの選定を説明する図である。
【図１０】コネクションの重み付けを説明する図である。
【図１１】光ネットワーク設計装置のフローチャートである。
【図１２】光ネットワーク設計装置の動作の一例を説明する図である。
【図１３】コネクション制限を考慮せずに経路設計した場合の光ハブサイトのコネクションを示した図である。
【図１４】光ネットワーク設計装置の他の動作例を示したフローチャートである。
【図１５】経路探索の計算回数の比較を説明する図である。
【図１６】光ネットワーク設計装置の経路設計を説明する図のその１である。
【図１７】光ネットワーク設計装置の経路設計を説明する図のその２である。
【図１８】光ネットワーク設計装置の経路設計を説明する図のその３である。
【図１９】光ハブサイトの詳細例を示した図である。
【発明を実施するための形態】
【００２８】
以下、第１の実施の形態を、図面を参照して詳細に説明する。
図１は、第１の実施の形態に係る光ネットワーク設計装置を示した図である。図１に示す光ネットワーク設計装置１は、非対称光ハブサイトを有する光ネットワークの経路設計を行う。光ネットワーク設計装置１は、経路算出部１ａ、違反判断部１ｂ、削除選定部１ｃ、および再経路算出部１ｄを有している。
【００２９】
経路算出部１ａは、非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出する。すなわち、経路算出部１ａは、非対称光ハブサイトの各ポートにはコネクション制限数がないものとしてコネクションを設定し、オペレータの要求するトラフィックパスを算出する。
【００３０】
違反判断部１ｂは、経路算出部１ａの算出したトラフィックパスが通過する非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する。
削除選定部１ｃは、違反判断部１ｂによってコネクション制限違反があると判断された場合、コネクション制限違反と判断された非対称光ハブサイトから、削除する削除コネクションを選定する。
【００３１】
再経路算出部１ｄは、削除選定部１ｃによって選定された削除コネクションを削除した非対称光ハブサイトにおいて再度トラフィックパスを算出する。すなわち、削除選定部１ｃは、コネクション制限違反の非対称光ハブサイトから削除コネクションを選定し、再経路算出部１ｄは、削除コネクションを削除した非対称光ハブサイトにおいて再度トラフィックパスを算出して、コネクション制限違反を解消するようにする。
【００３２】
このように、光ネットワーク設計装置１は、非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するデマンドの経路を算出してから、算出した経路を通過する非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する。そして、光ネットワーク設計装置１は、非対称光ハブサイトから削除する削除コネクションを選定して、再度トラフィックパスの経路を算出するようにした。これにより、光ネットワークの規模が拡大しても光ネットワークの経路設計を行うことができる。
【００３３】
次に、第２の実施の形態を、図面を参照して詳細に説明する。
図２は、第２の実施の形態に係る光ネットワーク設計装置のハードウェア構成例を示した図である。光ネットワーク設計装置１０は、ＣＰＵ（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）と呼ぶこともある。
【００４２】
光ネットワーク設計装置１０は、光ネットワークのトポロジ情報を記憶している。トポロジ情報は、例えば、キーボード２０、マウス２１、および光ディスク２２のいずれかによって光ネットワーク設計装置１０のＨＤＤ１３に記憶することができる。また、光ネットワーク設計装置１０は、通信インタフェース１７によって光ネットワークの光ハブサイトと通信し、光ハブサイトからトポロジ情報を取得してＨＤＤ１３に記憶することもできる。トポロジ情報には、光ハブサイト情報、スパン情報、およびデマンド情報が含まれている。
【００４３】
光ハブサイト情報には、光ハブサイトのポート数（光ハブサイトから出ているスパン数）、光ハブサイトがＡ−Ｈｕｂである場合にはそのコネクション制限数、およびコネクションの伝送遅延やコスト等の最短経路計算に必要なパラメータが含まれている。
【００４４】
スパン情報には、スパンの両端の光ハブサイト、およびスパンの伝送遅延やコスト等の最短経路計算に必要なパラメータが含まれている。
デマンド情報には、オペレータの要求するデマンドの起点および終点の光ハブサイトの情報が含まれている。
【００４５】
光ネットワーク設計装置１０は、コネクション制限数を考慮せずに所定の経路探索方法に基づきトポロジ情報を参照して、オペレータの要求するデマンドの経路を設計（算出）する。経路探索方法には、例えば、ダイクストラ法がある。以下では光ネットワーク設計装置１０は、ダイクストラ法を用いてデマンドの経路を算出するとする。
【００４６】
図４は、光ネットワーク設計装置の機能ブロック図である。図４に示すように、光ネットワーク設計装置１０は、経路算出部４１、Ａ−Ｈｕｂ情報生成部４２、違反判断部４３、削除選定部４４、再経路算出部４５、トポロジ情報記憶部４６、経路情報記憶部４７、およびＡ−Ｈｕｂ情報記憶部４８を有している。
【００４７】
経路算出部４１は、ダイクストラ法に基づきトポロジ情報記憶部４６に記憶されているトポロジ情報を参照して、Ａ−Ｈｕｂのコネクション制限を考慮せずにデマンドの経路を算出する。経路算出部４１は、算出したデマンドの経路を経路情報記憶部４７に記憶する。
【００４８】
Ａ−Ｈｕｂ情報生成部４２は、トポロジ情報記憶部４６と経路情報記憶部４７とを参照して、光ネットワークのＡ−ＨｕｂのそれぞれにおけるＡ−Ｈｕｂ情報を生成する。Ａ−Ｈｕｂ情報には、光ネットワークを形成している各Ａ−Ｈｕｂの各ポートに関するコネクション情報が含まれている。Ａ−Ｈｕｂ情報生成部４２は、生成したＡ−Ｈｕｂ情報をＡ−Ｈｕｂ情報記憶部４８に記憶する。
【００４９】
図５は、Ａ−Ｈｕｂ情報を説明するためのＡ−Ｈｕｂを示した図である。図５には、ポートＰ０〜Ｐ７を備えたＡ−Ｈｕｂの光ハブサイト５１が示してある。光ハブサイト５１のコネクション制限数は４であるとする。すなわち、光ハブサイト５１は、ポートＰ０〜Ｐ７のそれぞれにおいて最大４個のコネクションを張ることができる。
【００５０】
上記したように、経路算出部４１は、Ａ−Ｈｕｂのコネクション制限を考慮せずにデマンドの経路を算出する。これにより、光ハブサイト５１では、図５に示すように、各ポートＰ０〜Ｐ７にコネクションが張られたとする。
【００５１】
図６は、Ａ−Ｈｕｂ情報記憶部のデータ構成例を示した図である。図６には、Ａ−Ｈｕｂ情報記憶部４８が示してある。図６に示すように、Ａ−Ｈｕｂ情報記憶部４８は、ポート、ポート接続数、コネクション増加フラグ、Ｐｘ＿ａｄｄ、コネクションオーバフラグ、およびＰｘ＿ｏｖｅｒの欄を有している。
【００５２】
ポートの欄には、Ａ−Ｈｕｂの有しているポートの識別子が格納される。ポート接続数の欄には、各ポートから張られているコネクションの数が格納されている。コネクション増加フラグの欄には、各ポートからコネクションを増加することができるか否かの情報が格納される。図６の‘Ｙｅｓ’は、ポートからコネクションを増加させることができることを示し、‘Ｎｏ’は、ポートからコネクションを増加させることができないことを示す。
【００５３】
Ｐｘ＿ａｄｄの欄には、ポートからコネクションを新たに張ることができる数が格納される。コネクションオーバフラグの欄には、各ポートにおいてコネクションがコネクション制限をオーバしているか否かを示す情報が格納される。図６の‘Ｏｖｅｒ’は、ポートに張られたコネクションがコネクションオーバしていることを示し、‘Ｎｏ’は、ポートに張られたコネクションがコネクションオーバしていないことを示している。Ｐｘ＿ｏｖｅｒの欄には、各ポートにおいてコネクション制限数を超えているコネクション数が格納される。
【００５４】
図６に示すＡ−Ｈｕｂ情報は、図５に示した光ハブサイト５１のＡ−Ｈｕｂ情報を示している。例えば、光ハブサイト５１のポートＰ０からは、図５に示すようにコネクションが６個張られている。従って、図６に示すポート接続数の欄には、６が記憶されている。また、光ハブサイト５１のコネクション制限数は４である。従って、コネクション増加フラグの欄には、Ｎｏが記憶され、Ｐｘ＿ａｄｄの欄には０が記憶されている。また、コネクションオーバフラグの欄には、Ｏｖｅｒが記憶され、Ｐｘ＿ｏｖｅｒの欄には、２が記憶されている。
【００５５】
また、例えば、光ハブサイト５１のポートＰ１からは、図５に示すようにコネクションが１個張られている。従って、図６に示すポート接続数の欄には、１が記憶されている。また、光ハブサイト５１のコネクション制限数は４である。従って、コネクション増加フラグの欄には、Ｙｅｓが記憶され、Ｐｘ＿ａｄｄの欄には３が記憶されている。また、コネクションオーバフラグの欄には、Ｎｏが記憶され、Ｐｘ＿ｏｖｅｒの欄には、０が記憶されている。
【００５６】
Ａ−Ｈｕｂ情報生成部４２は、経路情報記憶部４７を参照して、図５に示すようなＡ−Ｈｕｂのコネクションを認識することができる。また、Ａ−Ｈｕｂ情報生成部４２は、トポロジ情報記憶部４６を参照して、コネクション制限数を認識することができる。これにより、Ａ−Ｈｕｂ情報生成部４２は、トポロジ情報記憶部４６と経路情報記憶部４７とを参照して、図６の各欄に示すようなＡ−Ｈｕｂ情報を生成することができる。そして、Ａ−Ｈｕｂ情報生成部４２は、生成したＡ−Ｈｕｂ情報をＡ−Ｈｕｂ情報記憶部４８に記憶することができる。
【００５７】
なお、図６では、光ハブサイト５１のＡ−Ｈｕｂ情報しか示していないが、Ａ−Ｈｕｂ情報生成部４２は、光ネットワークを形成している各Ａ−ＨｕｂのＡ−Ｈｕｂ情報を生成し、Ａ−Ｈｕｂ情報記憶部４８に記憶する。
【００５８】
図４の説明に戻る。違反判断部４３は、Ａ−Ｈｕｂ情報記憶部４８を参照し、経路算出部４１の算出したデマンドの経路が通過するＡ−Ｈｕｂのそれぞれにおいて、コネクション制限違反を判断する。例えば、違反判断部４３は、Ａ−Ｈｕｂ情報記憶部４８のコネクションオーバフラグを参照して、光ハブサイト５１はコネクション制限違反であると判断することができる。
【００５９】
削除選定部４４は、違反判断部４３によってコネクション制限違反があると判断された場合、Ａ−Ｈｕｂ情報記憶部４８を参照して、その制限違反と判断されたＡ−Ｈｕｂから削除するコネクションを選定する。例えば、削除選定部４４は、図５において、削除するコネクションとしてポートＰ０−Ｐ５間のコネクションを選定する。削除するコネクションの選定方法については、以下で詳細に述べる。
【００６０】
再経路算出部４５は、削除選定部４４によって選定されたコネクションをＡ−Ｈｕｂから削除して、再度デマンドの経路を算出する。デマンドの再計算については、以下で詳細に述べる。
【００６１】
削除するコネクションの選定方法について説明する。以下では、削除するコネクションを削除コネクションと呼ぶこともある。
図７は、削除するコネクションの選定方法を説明する図である。図７には、ポートＰ０〜Ｐ７を備えたＡ−Ｈｕｂの光ハブサイト５２が示してある。光ハブサイト５２のコネクション制限数は４であるとする。光ハブサイト５２は、経路算出部４１によって、図７に示すようにコネクションが張られたとする。
【００６２】
削除選定部４４は、Ａ−Ｈｕｂ情報記憶部４８を参照し、コネクションの両ポートともコネクション制限数を超えているコネクションを優先して削除コネクションに選定する。
図７の例の場合、ポートＰ０とポートＰ５の両方がコネクションオーバとなっている。従って、削除選定部４４は、コネクション５２ａを他のコネクションに優先して削除コネクションとして選定する。以下では、コネクションの両ポートともコネクション制限数を超えているコネクションをインポータントコネクションと呼ぶこともある。
【００６３】
インポータントコネクションを優先して削除コネクションとするのは、インポータントコネクションを削除することにより、２つのポートにおけるコネクション制限違反を解消できるからである。図７の例では、インポータントコネクションであるコネクション５２ａを削除コネクションに選定することにより、ポートＰ０，Ｐ５の２つのコネクション制限違反を解消できる。
【００６４】
次に、インポータントコネクションが複数存在する場合について説明する。
図８は、インポータントコネクションが２以上存在する場合の削除コネクションの選定を説明する図である。図８には、ポートＰ０〜Ｐ７を備えたＡ−Ｈｕｂの光ハブサイト５３が示してある。光ハブサイト５３のコネクション制限数は４であるとする。光ハブサイト５３は、経路算出部４１によって、図８に示すようにコネクションが張られたとする。
【００６５】
削除選定部４４は、Ａ−Ｈｕｂ情報記憶部４８を参照し、コネクションの両ポートともコネクション制限数を超えているインポータントコネクションを優先して削除コネクションに選定する。削除選定部４４は、その選定によりインポータントコネクションが複数存在する場合、コネクションの両ポートのコネクション超過数の合計が大きいインポータントコネクションを削除コネクションとして優先して選定する。コネクション超過数とは、ポートのコネクション制限数を超えているコネクション数である。
【００６６】
図８の例の場合、コネクション５３ａ〜５３ｃの３個のインポータントコネクションが存在する。コネクション５３ａのポートＰ０のコネクション超過数Ｐ０＿ｏｖｅｒは３であり、ポートＰ２のコネクション超過数Ｐ２＿ｏｖｅｒは２である。従って、コネクション５３ａの両ポートのコネクション超過数の合計は５である。また、コネクション５３ｂのポートＰ０のコネクション超過数Ｐ０＿ｏｖｅｒは３であり、ポートＰ５のコネクション超過数Ｐ５＿ｏｖｅｒは１である。従って、コネクション５３ｂの両ポートのコネクション超過数の合計は４である。また、コネクション５３ｃのポートＰ２のコネクション超過数Ｐ２＿ｏｖｅｒは２であり、ポートＰ５のコネクション超過数Ｐ５＿ｏｖｅｒは１である。従って、コネクション５３ｂの両ポートのコネクション超過数の合計は３である。従って、図８の例の場合、削除選定部４４は、コネクション超過数の合計が最も大きいコネクション５３ａを削除コネクションとして選定する。
【００６７】
このように、削除選定部４４は、インポータントコネクションが複数存在する場合、コネクション制限違反の要因（コネクション超過数）の大きいものから削除コネクションを優先して選定する。これにより、コネクション制限違反を早く解消することが可能となる。
【００６８】
なお、削除選定部４４は、コネクション超過数の合計が同じインポータントコネクションが複数存在する場合、コネクションに属するデマンドの経路本数の少ないコネクションを優先して削除コネクションとして選定する。コネクションに属するデマンドの経路本数は、経路情報記憶部４７を参照することにより取得することができる。これにより、再経路算出部４５によるデマンドの再計算において、コネクション変更するデマンドの数を少なくでき、光ネットワーク設計装置１０の処理負荷を低減することができる。
【００６９】
さらに、削除選定部４４は、デマンドの本数が同じ削除コネクションが複数存在する場合、その中からランダムに削除コネクションを選定する。
次に、インポータントコネクションが存在しない場合の削除コネクションの選定について説明する。
【００７０】
図９は、インポータントコネクションが存在しない場合の削除コネクションの選定を説明する図である。図９には、ポートＰ０〜Ｐ７を備えたＡ−Ｈｕｂの光ハブサイト５４が示してある。光ハブサイト５４のコネクション制限数は４であるとする。光ハブサイト５４は、経路算出部４１によって、図９に示すようにコネクションが張られたとする。
【００７１】
削除選定部４４は、Ａ−Ｈｕｂ情報記憶部４８を参照し、コネクションの両ポートともコネクション制限数を超えているインポータントコネクションを優先して削除コネクションに選定する。削除選定部４４は、コネクションの両ポートともコネクション制限数を超えているインポータントコネクションが存在しない場合、コネクション制限数を超えているポートと反対側のポートにおけるコネクション設定余裕数の小さいコネクションを優先して削除コネクションに選定する。コネクション設定余裕数とは、ポートからコネクション制限数の範囲内にてコネクションを新たに張ることができる数である。ただし、削除選定部４４は、選定した削除コネクションに２以上のデマンドが属している場合、その削除コネクションは選定から外し、次にコネクション設定余裕数の小さいコネクションを優先して削除コネクションに選定する。
【００７２】
例えば、図９の例の場合、コネクションの両ポートともコネクション制限数を超えているインポータントコネクションが存在せず、ポートＰ０がコネクション制限違反となっている。この場合、削除選定部４４は、Ａ−Ｈｕｂ情報記憶部４８を参照して、ポートＰ０と反対側のポートＰ２〜Ｐ７のコネクション設定余裕数を取得する。図９の例の場合、ポートＰ２〜Ｐ７のコネクション設定余裕数Ｐ２＿ａｄｄ〜Ｐ７＿ａｄｄはそれぞれ、２，１，３，２，２，２である。従って、削除選定部４４は、ポートＰ０と、コネクション設定余裕数の最も小さいポートＰ３のコネクション５４ａを削除コネクションとして選定する。
【００７３】
このように、削除選定部４４は、インポータントコネクションが存在しない場合、コネクション制限違反したポートとコネクション制限違反に近いポートとのコネクションを削除コネクションとして選定する。これにより、Ａ−Ｈｕｂの各ポートは、コネクション制限違反に対し、余裕を持つことができる。
【００７４】
なお、削除選定部４４は、コネクション余裕数の小さい削除コネクションが複数存在する場合、そのコネクションに属するデマンドの本数の少ないコネクションを優先して削除コネクションとして選定する。コネクションに属するデマンドの本数は、経路情報記憶部４７を参照することにより取得することができる。これにより、再経路算出部４５によるデマンドの再計算において、コネクション変更するデマンドの数を少なくでき、光ネットワーク設計装置１０の処理負荷を低減することができる。
【００７５】
さらに、削除選定部４４は、デマンドの本数が同じ削除コネクションが複数存在する場合、その中からランダムに削除コネクションを選定する。
次に、デマンドの再計算について説明する。
【００７６】
再経路算出部４５は、削除選定部４４によって選定された削除コネクションをＡ−Ｈｕｂから削除し、ダイクストラ法に基づき再度デマンドの経路を算出する。再経路算出部４５は、選定された削除コネクションに属していた全てのデマンドについて１つずつ代替コネクションを探索する。すなわち、再経路算出部４５は、削除コネクションに属していたデマンドの迂回可能な代替コネクションを探索する。
【００７７】
再経路算出部４５は、代替コネクションが見つからないデマンドが存在した場合には、削除選定部４４によって選定された削除コネクションは削除できないと判断する。この場合、削除選定部４４は、選定した削除コネクションを除いたコネクションから、再度上記で説明した選定方法に基づいて削除コネクションの選定を行う。そして、再経路算出部４５は、再度デマンドの経路を算出する。
【００７８】
再経路算出部４５は、ダイクストラ法に基づく代替コネクションの探索の際、Ａ−Ｈｕｂにおいて削除コネクションを削除した残りのコネクションに重み付けを行って、代替コネクションの探索を行う。
【００７９】
図１０は、コネクションの重み付けを説明する図である。図１０には、ポートＰ０〜Ｐ７を備えたＡ−Ｈｕｂの光ハブサイト５４が示してある。光ハブサイト５４のコネクション制限数は４であるとする。光ハブサイト５４は、経路算出部４１によって、図１０の実線に示すようにコネクションが張られたとする。そして、削除選定部４４は、コネクション５４ａを削除コネクションとして選定したとする。
【００８０】
図１０の点線で示すコネクションは、デマンドの経路の再算出において、コネクション制限違反とならないよう、コネクションを張ることができるコネクションを示している。以下では、経路算出部４１によって張られたコネクションを使用コネクション、コネクション制限違反とならないようにコネクションを張ることができる使用コネクション以外のコネクションを使用可能コネクションと呼ぶこともある。
【００８１】
再経路算出部４５は、光ハブサイト５４から削除コネクションであるコネクション５４ａを削除し、使用コネクションと使用可能コネクションとに重み付けを行って、削除コネクションに属していたデマンドの算出を行う。このとき、再経路算出部４５は、デマンドの経路決定において、使用可能コネクションが使用コネクションより優先して選ばれるように重み付けを行う。
【００８２】
また、再経路算出部４５は、使用可能コネクション同士においては、使用可能コネクションの両ポートのコネクション設定余裕数の大きいものが優先して選ばれるように重み付けを行う。例えば、使用可能コネクションの両ポートのコネクション設定余裕数の合計値の大きいものが優先して選ばれるように重み付けを行う。すなわち、再経路算出部４５は、コネクション制限違反に対して余裕のある使用可能コネクションが選ばれるように重み付けを行う。
【００８３】
また、再経路算出部４５は、使用コネクション同士においては、使用コネクションに属しているデマンドの本数の少ないものが経路決定において優先して選ばれるように重み付けを行う。
【００８４】
フローチャートを用いて光ネットワーク設計装置１０の動作を説明する。
図１１は、光ネットワーク設計装置のフローチャートである。
［ステップＳ１ａ，Ｓ１ｂ］経路算出部４１は、オペレータから要求のあったデマンドの数分、ステップＳ２の処理を行う。
【００８５】
［ステップＳ２］経路算出部４１は、オペレータから要求のあったデマンドの経路探索を行う。なお、経路算出部４１は、コネクション制限を考慮せずにデマンドの経路探索を行う。
【００８６】
［ステップＳ３］違反判断部４３は、経路算出部４１の算出したデマンドの経路が通過するＡ−Ｈｕｂにおいて、コネクション制限違反があったか否か判断する。違反判断部４３は、コネクション制限違反がない場合、処理を終了する。違反判断部４３は、コネクション制限違反がある場合、ステップＳ４ａへ進む。
【００８７】
［ステップＳ４ａ，Ｓ４ｂ］削除選定部４４と再経路算出部４５は、コネクション制限違反のあったＡ−Ｈｕｂのそれぞれにおいて、以下のステップＳ５〜Ｓ７の処理を行う。
［ステップＳ５ａ，Ｓ５ｂ］削除選定部４４は、Ａ−Ｈｕｂから削除する削除コネクションを選定する。削除コネクションの選定は、上述したようにインポータントコネクションを考慮して行う。
【００８８】
［ステップＳ６ａ，Ｓ６ｂ］再経路算出部４５は、選定された削除コネクションに属するデマンドの１つずつにおいて、ステップＳ７の処理を行う。
［ステップＳ７］再経路算出部４５は、削除コネクションを削除した状態で、再度デマンドの経路を探索する。このとき、再経路算出部４５は、上述したようにコネクションの重み付けを行う。
【００８９】
再経路算出部４５は、削除コネクションに属している全てのデマンドにおいて経路探索をするまで、ステップＳ６ａに進む。
再経路算出部４５は、削除コネクションに属していた全てまたは一部のデマンドにおいて、経路探索することができなかった場合、すなわち、代替のコネクションが存在しなかた場合、その削除コネクションは削除できないと判断し、ステップＳ５ａへ進む。
【００９０】
また、再経路算出部４５は、全てのデマンドの経路探索ができた場合でも、コネクション制限違反がまだ存在する場合にはステップＳ５ａに進む。
再経路算出部４５は、考慮しているＡ−Ｈｕｂにおいてコネクション制限違反がなくなった場合には、次のコネクション制限違反を有するＡ−Ｈｕｂの経路探索を行うため、ステップＳ４ａに進む。再経路算出部４５は、コネクション制限違反を有するＡ−Ｈｕｂが存在しなくなると、処理を終了する。
【００９１】
光ネットワーク設計装置１０の動作の一例について説明する。
図１２は、光ネットワーク設計装置の動作の一例を説明する図である。図１２には、ポートＰ０〜Ｐ９を備えたＡ−Ｈｕｂの光ハブサイト５５が示してある。また、図１２は、光ハブサイトＡ〜Ｊが示してある。
【００９２】
図１２に示す枠は、オペレータから経路設計の要求のあったデマンドが示してある。光ハブサイト５５のコネクション制限数は４であるとする。光ハブサイトＩ，Ｈは、図１２の点線に示すように、接続関係があるとする。
【００９３】
光ネットワーク設計装置１０は、コネクション制限を考慮せず、ダイクストラ法に基づき各デマンドの経路を算出する。光ネットワーク設計装置１０は、光ハブサイト５５においては以下のようにコネクションの経路設計をしたとする。なお、ダイクストラ法は、以下の番号ごとに１回実行されることになる。
【００９４】
１．デマンドＡ−Ｂ：ポートＰ０−Ｐ１のコネクションで経路設計
２．デマンドＡ−Ｃ：ポートＰ０−Ｐ２のコネクションで経路設計
３．デマンドＡ−Ｈ：ポートＰ０−Ｐ７のコネクションで経路設計
４．デマンドＡ−Ｉ：ポートＰ０−Ｐ８のコネクションで経路設計
５．デマンドＡ−Ｊ：ポートＰ０−Ｐ９のコネクションで経路設計
６．デマンドＤ−Ｈ：ポートＰ３−Ｐ７のコネクションで経路設計
７．デマンドＥ−Ｈ：ポートＰ４−Ｐ７のコネクションで経路設計
８．デマンドＧ−Ｈ：ポートＰ６−Ｐ７のコネクションで経路設計
９．デマンドＪ−Ｈ：ポートＰ９−Ｐ７のコネクションで経路設計
１０．デマンドＢ−Ｉ：ポートＰ１−Ｐ８のコネクションで経路設計
１１．デマンドＣ−Ｉ：ポートＰ２−Ｐ８のコネクションで経路設計
１２．デマンドＥ−Ｉ：ポートＰ４−Ｐ８のコネクションで経路設計
１３．デマンドＦ−Ｉ：ポートＰ５−Ｐ８のコネクションで経路設計
図１３は、コネクション制限を考慮せずに経路設計した場合の光ハブサイトのコネクションを示した図である。光ハブサイト５５は、上記の１〜１３の経路設計により、図１３に示すように、コネクションが張られる。図１３に示すように、ポートＰ０−Ｐ７のコネクションとポートＰ０−Ｐ８のコネクションがインポータントコネクションとなる。
【００９５】
図１２の説明に戻る。
１４．上記の経路設計では、光ハブサイト５５にポートＰ０，Ｐ７，Ｐ８の３個のポートにコネクション制限違反が生じている。この中でインポータントコネクションは、図１３に示すようにポートＰ０−Ｐ７のコネクションと、ポートＰ０−Ｐ８のコネクションの２個である。
【００９６】
ここでは、光ネットワーク設計装置１０は、ポートＰ０−Ｐ８のコネクションを削除コネクションとして選定したとする。そして、光ネットワーク設計装置１０は、ポートＰ０−Ｐ８の削除コネクションを削除し、この削除コネクションに属していたデマンドＡ−Ｉの再経路設計を行う。
【００９７】
図１２の例では、光ハブサイトＩ，Ｈに接続関係がある。これにより、光ネットワーク設計装置１０は、例えば、デマンドＡ−Ｉの経路として、ポートＰ０−Ｐ７のコネクションを算出する。
【００９８】
１５．この時点で、光ハブサイト５５は、ポートＰ７のみがコネクション制限違反となっている。なお、インポータントコネクションは存在しない。
光ネットワーク設計装置１０は、上記で説明した優先度に従って、ポートＰ７を使用しているコネクションで削除可能なコネクションを選定する。すなわち、光ネットワーク設計装置１０は、ポートＰ７の反対側のポートＰ０，Ｐ３，Ｐ４，Ｐ６，Ｐ９のうち、コネクション設定余裕数の小さいコネクションを削除コネクションとして選定する。
【００９９】
ａ．光ネットワーク設計装置１０は、コネクション設定余裕数の最も小さいポートＰ０を有するポートＰ７−Ｐ０のコネクションを削除コネクションとして選定する。この削除コネクションには、２つのデマンドＡ−Ｈ，Ａ−Ｉが属しているので、削除コネクションから除外する。
【０１００】
ｂ．光ネットワーク設計装置１０は、次にコネクション設定余裕数の小さいポートＰ４，Ｐ９のうち、ポートＰ７−Ｐ４のコネクションを削除コネクションとして選定する。
１６．光ネットワーク設計装置１０は、ポートＰ７−Ｐ４の削除コネクションを削除し、この削除コネクションに属していたデマンドＥ−Ｈの再経路計算を行う。
【０１０１】
図１２の例では、光ハブサイトＩ，Ｈに接続関係がある。これにより、光ネットワーク設計装置１０は、例えば、デマンドＥ−Ｈの経路として、ポートＰ４−Ｐ８のコネクションを算出する。
【０１０２】
このように、光ネットワーク設計装置１０は、図１２の例では、１６回のダイクストラ計算によってデマンドの経路設計を行うことができる。
上記で説明した光ネットワーク設計装置１０は、コネクション制限違反を考慮せずデマンドの経路を算出し、その後、削除すべきコネクションを選定して、再度デマンド経路を算出する。
【０１０３】
これに対し、１つのデマンドの経路を算出するごとに、コネクション制限違反を判断し、コネクション制限違反があれば、これを解消するように新たな経路探索を行っていく方法もある。以下では、このデマンドの経路計算ごとにコネクション制限違反を判断する例について説明する。
【０１０４】
図１４は、光ネットワーク設計装置の他の動作例を示したフローチャートである。
［ステップＳ１１ａ，Ｓ１１ｂ］光ネットワーク設計装置は、オペレータから要求のあったデマンドの１つずつについて以下のステップの処理を行う。
【０１０５】
［ステップＳ１２］光ネットワーク設計装置は、ダイクストラ法に基づきデマンドの経路探索を行う。
［ステップＳ１３］光ネットワーク設計装置は、ステップＳ１２で探索した経路により、コネクション制限違反が生じたか否か判断する。光ネットワーク設計装置は、コネクション制限違反が生じた場合、ステップＳ１４へ進む。光ネットワーク設計装置は、コネクション制限違反が生じてない場合、次のデマンドの経路探索を行うためステップＳ１１ａへ進む。
【０１０６】
［ステップＳ１４］光ネットワーク設計装置は、現在設定されているコネクションで、コネクション制限違反の生じたデマンドの経路探索を行う。
［ステップＳ１５］光ネットワーク設計装置は、現在設定されているコネクションで、コネクション制限違反の生じたデマンドの経路設計ができたか否か判断する。光ネットワーク設計装置は、現在設定されているコネクションで、コネクション制限違反の生じたデマンドの経路設計ができた場合、次のデマンドの経路探索を行うためステップＳ１１ａへ進む。光ネットワーク設計装置は、現在設定されているコネクションで、コネクション制限違反の生じたデマンドの経路設計ができなかった場合、ステップＳ１６へ進む。
【０１０７】
［ステップＳ１６］光ネットワーク設計装置は、現在設定されていないコネクションで、コネクション制限違反の生じたデマンドの経路探索を行う。
［ステップＳ１７］光ネットワーク設計装置は、現在設定されていないコネクションで、コネクション制限違反の生じたデマンドの経路設計ができたか否か判断する。光ネットワーク設計装置は、現在設定されていないコネクションで、コネクション制限違反の生じたデマンドの経路設計ができなかった場合、設計不可として処理を終了する。光ネットワーク設計装置は、現在設定されていないコネクションで、コネクション制限違反の生じたデマンドの経路設計ができた場合、ステップＳ１８ａへ進む。
【０１０８】
［ステップＳ１８ａ，Ｓ１８ｂ］光ネットワーク設計装置は、考慮しているＡ−Ｈｕｂ（現在コネクション制限違反の処理を行っているＡ−Ｈｕｂ）について以下のステップの処理を行う。
【０１０９】
［ステップＳ１９ａ，Ｓ１９ｂ］光ネットワーク設計装置は、削除コネクションの選定を行う。
［ステップＳ２０ａ，Ｓ２０ｂ］光ネットワーク設計装置は、選定された削除コネクションに属するデマンドの１つずつにおいて、ステップＳ２１の処理を行う。
【０１１０】
［ステップＳ２１］光ネットワーク設計装置は、削除コネクションを削除した状態で、再度デマンドの経路を探索する。
光ネットワーク設計装置は、削除コネクションに属している全てのデマンドにおいて経路算出をするまで、ステップＳ２０ａに進む。
【０１１１】
光ネットワーク設計装置は、削除コネクションに属していた全てまたは一部のデマンドにおいて、経路算出をすることができなかった場合、すなわち、代替のコネクションが存在しなかった場合、選定された削除コネクションは削除できないとしてステップＳ１９ａに進む。
【０１１２】
光ネットワーク設計装置は、考慮しているＡ−Ｈｕｂにおいてコネクション制限違反が解消されれば、次のＡ−Ｈｕｂでのコネクション制限違反を解消するためにステップＳ１８ａに進む。
【０１１３】
光ネットワーク設計装置は、デマンドのコネクション制限違反が解消すると、次のデマンドの経路探索を行うために、ステップＳ１１ａへ進む。
図１４で説明した光ネットワーク設計装置の動作の一例について、図１２を用いて説明する。図１４の光ネットワーク設計装置は、図１２の光ネットワークにおけるデマンドに対し、以下のようにして経路設計を行う。なお、ダイクストラ法は、以下の番号ごとに１回実行されることになる。
【０１１４】
１．デマンドＡ−Ｂ：ポートＰ０−Ｐ１のコネクションで経路設計
２．デマンドＡ−Ｃ：ポートＰ０−Ｐ２のコネクションで経路設計
３．デマンドＡ−Ｈ：ポートＰ０−Ｐ７のコネクションで経路設計
４．デマンドＡ−Ｉ：ポートＰ０−Ｐ８のコネクションで経路設計
５．デマンドＡ−Ｊ：ポートＰ０のコネクション制限違反により経路設計不可
６．光ネットワーク設計装置は、上記１〜５の現在既に設定されている既存コネクションにおいて、デマンドＡ−Ｊの経路を算出する。図１２における上記の既存コネクションでは、デマンドＡ−Ｊの経路（迂回経路）は存在しないので、光ネットワーク設計装置は経路設計不可と判断する。
【０１１５】
７．光ネットワーク設計装置は、既存コネクション以外のコネクションでデマンドＡ−Ｊの経路探索を行う。光ネットワーク設計装置は、デマンドＡ−Ｊの光ハブサイト５５における経路として、ポートＰ０−Ｐ９のコネクションを算出する。
【０１１６】
８．ポートＰ０−Ｐ９のコネクションを設定することにより、ポートＰ０はコネクション制限違反となる。そこで、光ネットワーク設計装置は、デマンドＡ−Ｂの既存コネクションが削除可能か判断する。光ネットワーク設計装置は、デマンドＡ−Ｂには迂回経路がないため、削除不可と判断する。
【０１１７】
９．光ネットワーク設計装置は、デマンドＡ−Ｃの既存コネクションが削除可能か判断する。光ネットワーク設計装置は、デマンドＡ−Ｃには迂回経路がないため、削除不可と判断する。
【０１１８】
１０．光ネットワーク設計装置は、デマンドＡ−Ｈの既存コネクションが削除可能か判断する。光ハブサイトＩ，Ｈには接続関係があるので、デマンドＡ−ＨのコネクションはデマンドＡ−Ｉのコネクションで代替できる。これにより、光ハブサイト５５では、デマンドＡ−Ｈのコネクションが削除されてデマンドＡ−Ｊのコネクションが設定され、ポートＰ０のコネクション制限違反が解消される。
【０１１９】
１１．デマンドＤ−Ｈ：ポートＰ３−Ｐ７のコネクションで経路設計
１２．デマンドＥ−Ｈ：ポートＰ４−Ｐ７のコネクションで経路設計
１３．デマンドＧ−Ｈ：ポートＰ６−Ｐ７のコネクションで経路設計
１４．デマンドＪ−Ｈ：ポートＰ９−Ｐ７のコネクションで経路設計
１５．デマンドＢ−Ｉ：ポートＰ１−Ｐ８のコネクションで経路設計
１６．デマンドＣ−Ｉ：ポートＰ２−Ｐ８のコネクションで経路設計
１７．デマンドＥ−Ｉ：ポートＰ４−Ｐ８のコネクションで経路設計
１８．デマンドＦ−Ｉ：ポートＰ８のコネクション制限違反により経路設計不可
１９．光ネットワーク設計装置は、上記１〜１８の既存コネクションにおいて、デマンドＦ−Ｉの経路を算出する。図１２における上記の既存コネクションでは、デマンドＦ−Ｉの経路（迂回経路）は存在しないので、光ネットワーク設計装置は経路設計不可と判断する。
【０１２０】
２０．光ネットワーク設計装置は、既存コネクション以外のコネクションでデマンドＦ−Ｉの経路探索を行う。光ネットワーク設計装置は、デマンドＦ−Ｉの光ハブサイト５５における経路として、ポートＰ５−Ｐ８のコネクションを算出する。
【０１２１】
２１．ポートＰ５−Ｐ８のコネクションを設定することにより、ポートＰ８はコネクション制限違反となる。そこで、光ネットワーク設計装置は、デマンドＡ−Ｉの既存コネクションが削除可能か判断する。光ネットワーク設計装置は、デマンドＡ−ＩはすでにデマンドＡ−Ｈの迂回経路として設定されているので、削除不可と判断する。
【０１２２】
２２．光ネットワーク設計装置は、デマンドＢ−Ｉの既存コネクションが削除可能か判断する。光ネットワーク設計装置は、デマンドＢ−Ｉには迂回経路がないため、削除不可と判断する。
【０１２３】
２３．光ネットワーク設計装置は、デマンドＣ−Ｉの既存コネクションが削除可能か判断する。光ネットワーク設計装置は、デマンドＣ−Ｉには迂回経路がないため、削除不可と判断する。
【０１２４】
２４．光ネットワーク設計装置は、デマンドＥ−Ｉの既存コネクションが削除可能か判断する。光ハブサイトＩ，Ｈには接続関係があるので、デマンドＥ−ＩのコネクションはデマンドＥ−Ｈのコネクションで代替できる。これにより、光ハブサイト５５では、デマンドＥ−Ｉのコネクションが削除されてデマンドＦ−Ｉのコネクションが設定され、ポートＰ８のコネクション制限違反が解消される。
【０１２５】
このように、１つのデマンドの経路を算出するごとに、コネクション制限違反を判断する方法では、図１２の例では、２４回のダイクストラ計算を行うことになる。
これに対し、コネクション制限違反を考慮せずデマンドの経路設計を行い、その後、削除すべきコネクションを選定する光ネットワーク設計装置１０では、上記したように１６回のダイクストラ計算によってデマンドの経路設計を行う。すなわち、光ネットワーク設計装置１０では、計算時間を短縮することができる。
【０１２６】
図１５は、経路探索の計算回数の比較を説明する図である。図１５には、図１１等で説明したコネクション制限違反を考慮せずに経路設計を行い、削除コネクションを選定して経路探索を行う場合の計算回数と、図１４で説明したデマンドごとにコネクション制限違反を考慮して経路探索を行う場合の計算回数とが示してある。図１５の経路探索の計算回数は、ダイクストラ法を実行した回数を示す。
【０１２７】
図１５に示す‘デマンド設定での回数’は、図１１のＳ２で行われるダイクストラ法の計算回数と、図１４のステップＳ１２，Ｓ１４，Ｓ１６で行われるダイクストラ法の計算回数とを示している。
【０１２８】
図１５のＤは、デマンドの総数を示している。図１１等の経路算出方法では、コネクション制限違反を考慮せずにデマンドの経路を行うので、‘デマンド設定での回数’はＤとなる。一方、図１４の経路算出方法では、ステップＳ１２，Ｓ１４，Ｓ１６の３ステップでダイクストラ法が実行されるので、‘デマンド設定での回数’は３×Ｄとなる。
【０１２９】
図１５に示す‘コネクション調整での回数’は、図１１のステップＳ７で行われるダイクストラ法の計算回数と、図１４のステップＳ２１で行われるダイクストラ法の計算回数を示している。
【０１３０】
図１５のＮは、光ネットワークを形成しているＡ−Ｈｕｂの総数を示している。Ｃnewは、図１１の削除コネクションの数を示している。すなわち、Ｃnewは、図１１のステップＳ５ａ，Ｓ５ｂで繰り返されるステップＳ７のダイクストラ法の計算回数を示している。ＣCnewは、図１１の削除コネクションに属しているデマンドの数を示している。すなわち、ＣCnewは、図１１のステップＳ６ａ，Ｓ６ｂで繰り返されるステップＳ７のダイクストラ法の計算回数を示している。これにより、‘コネクション調整での回数’はＮ×Ｃnew×ＣCnewとなる。
【０１３１】
図１５のＣoldは、図１４の削除コネクションの数を示している。すなわち、Ｃoldは、図１４のステップＳ１９ａ，Ｓ１９ｂで繰り返されるステップＳ２１のダイクストラ法の計算回数を示している。ＣColdは、図１４の削除コネクションに属しているデマンドの数を示している。すなわち、ＣColdは、図１４のステップＳ２０ａ，Ｓ２０ｂで繰り返されるステップＳ２１のダイクストラ法の計算回数を示している。これにより、‘コネクション調整での回数’はＤ×Ｎ×Ｃold×ＣColdとなる。
【０１３２】
図１５の‘デマンド設定での回数’に示すように、図１１等で説明した光ネットワーク設計装置１０の計算回数は、図１４で説明した経路探索方法の計算回数に対し、１／３となる。
【０１３３】
また、ＣnewとＣoldは、ともに削除コネクションの数を示し同じである。ＣCnewとＣColdはともに削除コネクションに属しているデマンドの数を示し同じである。従って、図１５の‘コネクション調整での回数’に示すように、図１１等で説明した光ネットワーク設計装置１０の計算回数は、図１４で説明した経路探索方法の計算回数に対し、１／Ｄとなる。すなわち、光ネットワーク設計装置１０では、１つのデマンドの経路を算出するごとに、コネクション制限違反を判断する方法に対し、計算時間を短縮することができる。
【０１３４】
このように、光ネットワーク設計装置１０は、Ａ−Ｈｕｂのコネクション制限を考慮せずにオペレータの要求するデマンドの経路を算出してから、算出した経路を通過するＡ−Ｈｕｂのそれぞれにおいてコネクション制限違反を判断する。そして、Ａ−Ｈｕｂから削除する削除コネクションを選定してから、再度デマンドの経路を算出するようにした。これにより、光ネットワークの規模が拡大しても光ネットワークの経路設計を行うことができる。また、光ネットワーク設計装置１０は、１つのデマンドの経路を算出するごとに、コネクション制限違反を判断する方法に対し、経路計算時間を短縮することができる。
【０１３５】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、光ネットワーク設計装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【０１３６】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１３７】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１３８】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０１３９】
以上の実施の形態に開示された技術には、以下の付記に示す技術が含まれる。
（付記１）  非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計装置において、
前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出する経路算出部と、
前記経路算出部の算出したトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する違反判断部と、
前記違反判断部によってコネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定する削除選定部と、
前記削除選定部によって選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出する再経路算出部と、
を有することを特徴とする光ネットワーク設計装置。
【０１４０】
（付記２）  前記削除選定部は、前記非対称光ハブサイトのコネクションの両ポートともコネクション制限数を超えているコネクションを優先して前記削除コネクションに選定することを特徴とする付記１記載の光ネットワーク設計装置。
【０１４１】
（付記３）  前記削除選定部は、優先して選定した前記削除コネクションが複数存在する場合、コネクションの両ポートのコネクション超過数の合計が大きい前記削除コネクションを優先して選定することを特徴とする付記２記載の光ネットワーク設計装置。
【０１４２】
（付記４）  前記削除選定部は、前記コネクション超過数の合計が同じ前記削除コネクションが複数存在する場合、前記削除コネクションに属するトラフィックパスが少ない前記削除コネクションを優先して選定することを特徴とする付記３記載の光ネットワーク設計装置。
【０１４３】
（付記５）  前記削除選定部は、前記非対称光ハブサイトのコネクションの両ポートともコネクション制限数を超えているコネクションが存在しない場合、コネクション制限数を超えているポートと反対側のポートにおけるコネクション設定余裕数の小さいコネクションを優先して前記削除コネクションに選定することを特徴とする付記２記載の光ネットワーク設計装置。
【０１４４】
（付記６）  前記削除選定部は、前記コネクション設定余裕数の同じ前記削除コネクションが複数存在する場合、前記削除コネクションに属するトラフィックパスが少ない前記削除コネクションを優先して選定することを特徴とする付記５記載の光ネットワーク設計装置。
【０１４５】
（付記７）  前記再経路算出部は、前記非対称光ハブサイトにおいて前記削除コネクションを削除した残りのコネクションに重み付けを行って再度トラフィックパスを算出することを特徴とする付記１乃至６のいずれかに記載の光ネットワーク設計装置。
【０１４６】
（付記８）  前記再経路算出部は、前記経路算出部で算出されたトラフィックパスですでに使用されている使用コネクションに対し、コネクション制限違反とならない未使用の使用可能コネクションが優先してトラフィックパスに選ばれるよう前記重み付けを行うことを特徴とする付記７記載の光ネットワーク設計装置。
【０１４７】
（付記９）  前記再経路算出部は、前記使用可能コネクションにおいては、前記使用可能コネクションのポートのコネクション設定余裕数に基づいて前記重み付けを行うことを特徴とする付記８記載の光ネットワーク設計装置。
【０１４８】
（付記１０）  前記再経路算出部は、前記使用コネクションにおいては、前記使用コネクションに属するトラフィックパスの少ないものが優先して選定されるように前記重み付けを行うことを特徴とする付記８記載の光ネットワーク設計装置。
【０１４９】
（付記１１）  非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計装置の光ネットワーク設計方法において、
前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出し、
算出したトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断し、
コネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定し、
選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出する、
ことを特徴とする光ネットワーク設計方法。
【０１５０】
（付記１２）  非対称光ハブサイトを有する光ネットワークの経路設計を行う光ネットワーク設計プログラムにおいて、
コンピュータを、
前記非対称光ハブサイトのコネクション制限を考慮せずにオペレータの要求するトラフィックパスを算出して経路情報記憶部に記憶する経路算出手段、
前記経路情報記憶部に記憶されたトラフィックパスが通過する前記非対称光ハブサイトのそれぞれにおいてコネクション制限違反を判断する違反判断手段、
前記違反判断手段によってコネクション制限違反があると判断された場合、その判断された前記非対称光ハブサイトから削除する削除コネクションを選定する削除選定手段、
前記削除選定手段によって選定された前記削除コネクションを削除した前記非対称光ハブサイトにおいて再度トラフィックパスを算出する再経路算出手段、
として機能させることを特徴とする光ネットワーク設計プログラム。
【符号の説明】
【０１５１】
１  光ネットワーク設計装置
１ａ  経路算出部
１ｂ  違反判断部
１ｃ  削除選定部
１ｄ  再経路算出部
【図１】
0005447046.tif 000002
【図２】
0005447046.tif 000003
【図３】
0005447046.tif 000004
【図４】
0005447046.tif 000005
【図５】
0005447046.tif 000006
【図６】
0005447046.tif 000007
【図７】
0005447046.tif 000008
【図８】
0005447046.tif 000009
【図９】
0005447046.tif 000010
【図１０】
0005447046.tif 000011
【図１１】
0005447046.tif 000012
【図１２】
0005447046.tif 000013
【図１３】
0005447046.tif 000014
【図１４】
0005447046.tif 000015
【図１５】
0005447046.tif 000016
【図１６】
0005447046.tif 000017
【図１７】
0005447046.tif 000018
【図１８】
0005447046.tif 000019
【図１９】
0005447046.tif 000020