トランスポート回線設計方法およびプログラム
【課題】許容遅延量を考慮した波長数最小化のための効率的な回線設計方法およびプログラムを提供する。
【解決手段】全ての需要に対して、始点ノードと終点ノード間の直線距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する。次に、前記遅延制約量が一定値以下である需要を、前記で設定されたパスに集約した時、許容遅延時間を満たす場合、該パスに集約する。最後に、ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記で集約できなかった需要を集約する。
【解決手段】全ての需要に対して、始点ノードと終点ノード間の直線距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する。次に、前記遅延制約量が一定値以下である需要を、前記で設定されたパスに集約した時、許容遅延時間を満たす場合、該パスに集約する。最後に、ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記で集約できなかった需要を集約する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、顧客の要求する最大許容遅延を考慮した波長数最小化のための効率的な回線設計方法およびプログラムに関し、ＯＴＮ(Optical Transport Network)やＭＰＬＳ−ＴＰ(Multi Protocol Label Switching-Transport Profile)等の回線を収容・集約可能なノードで構成されるトランスポートネットワークを対象としている。
【背景技術】
【０００２】
従来、波長の有効活用のため、複数パスを単一波長に集約する技術が提案されてきた（非特許文献１−５）。非特許文献２−５は、トポロジーがリング型のネットワークに限定されたものである。非特許文献１は、メッシュ型ネットワークにもフレキシブルに適用可能な方式である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】I.Yagyu et.al., "An EfficientHierarchical Optical Path Network Design Algorithm based on a Traffic DemandExpression in a Cartesian Product Space," IEEE Journalon Selected Areas In Communications, Vol.26, No.6, pp.22-31, August 2008.
【非特許文献２】A..L.Chiu et al., "TrafficGrooming Algorithm for Reducing Electronic Multiplexing Costs in WDM RingNetworks," Journal of Lightwave Technology, Vol.18, No.1, pp.2-12, January2000.
【非特許文献３】O.Gerstel,et.al.,"Cost-Effective Traffic Grooming in WDM Rings," IEEE/ACM Transactionon Networking, Vol.8, No.5, pp.618-630, October 2000.
【非特許文献４】X.Zhang et.al., "An Effectiveand Comprehensive Approach for Traffic Grooming and Wavelength Assignment inSONET/WDM Rings," Vol.8, No.5, pp.608-617, October 2000.
【非特許文献５】J. M.Simmons et al.,"Quantifying the Benefit of Wavelength Add-Drop in WDM Rings withDistance-Independent and Dependent Traffic," Journal of LightwaveTechnol.Vol.17, No.1, January 1999.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これらの方式では各トラヒック需要における許容遅延量を考慮していないといった問題点がある。
【０００５】
したがって、本発明は、許容遅延量を考慮した波長数最小化のための効率的な回線設計方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を実現するため本発明による回線設計方法は、許容遅延時間を有する需要に対する回線設計方法において、全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する第１のステップと、前記遅延制約量が一定値以下である需要を、前記第１のステップで設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する第２のステップと、ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記第２のステップで集約できなかった需要を集約する第３のステップとを有する。
【０００７】
また、前記第１のステップは、全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要をリスト１に登録する第１のサブステップと、前記リスト１に登録された需要の中から、最も遅延制約が厳しい需要を求め、該需要について、最短パスを設定する第２のサブステップと、前記リスト１に登録された需要の中で、前記設定されたパスの通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、前記設定された遅延制約の最も厳しいパスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、前記設定された遅延制約の最も厳しいパスに集約する第３のサブステップと、前記第３のサブステップで集約されなかった前記リスト１に登録された需要を新たにリスト１として、前記第２のサブステップと前記第３のサブステップを集約関係が発生しなくなるまで繰り返す第４のサブステップとを有し、
前記第２のステップは、前記遅延制約量が一定値以下である需要の中で、前記第１のステップで設定されたパスの始終点を含む通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、該パスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約し、集約できない需要をリスト２に登録する第５のサブステップであり、
前記第３のステップは、前記リスト２に登録された需要の始点ノードと終点ノード間を結ぶ線を可能な限り多く通過するようにネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第６のサブステップと、前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を１本引き、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、前記第７のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を引き直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップとを有することも好ましい。
【０００８】
また、前記第５のサブステップは、該需要の始点または終点から一定距離以内にＯＴＮノードが存在し、該ＯＴＮノードに該需要の始点または終点を収容した場合、許容遅延時間を満たすか否か確認し、満たす場合は、該需要の始点または終点を該ＯＴＮノードに集約することをさらに備えることも好ましい。
【０００９】
また、前記第７のサブステップと前記第８のサブステップで、それぞれの新しい区画でノード数が可能な限り均等になるように分割することも好ましい。
【００１０】
また、前記第３のステップの別の方式としては、前記リスト２に登録された需要のなかで、始点ノードと終点ノード間の距離が最長となる需要を抽出し、当該需要の始点ノードを集合Ａ、終点ノードを集合Ｂに含め、他の需要は、当該需要の始点ノードからより距離の近い端点（始点ノードまたは終点ノード）を集合Ａ、他方をＢに属するように、ネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否かを確認し、満たす場合は、該パスに集約する第６のサブステップと、前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの集合Ａ、Ｂを、同一集合に属する始点ノードの終点ノード、および終点ノードの始点ノードが、別の同一集合に属する条件を満たすように、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、前記第７のサブステップまでに全ての需要が集約できない場合または前記条件を満たすように分割できない場合、前記第６のサブステップの条件を満たす区画に分割し直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップとであることも好ましい。
【００１１】
また、前記遅延制約量は、始点ノードと終点ノード間の直線距離を許容遅延時間で割った値であることも好ましい。
【００１２】
また、前記最短パスは、遅延時間をパスコストとして、ダイクストラ法で決定されることも好ましい。
【００１３】
また、前記起点となるノードは、前記区画の中にあり、前記リスト２に登録された需要の起点ノードと終点ノードからの直線距離の総和が最小となる、もしくはホップ数の総和が最小となるノードであることも好ましい。
【００１４】
また、前記第７のサブステップと前記第８のサブステップで、集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数となった場合、集約できなかったパスについては単独に波長を割り当てることも好ましい。
【００１５】
また、前記第３のステップ終了後、パス集約後の総和の帯域が、１インタフェースが有する帯域以上になった場合、
集約予定としていた全需要の中で、前記遅延制約量が一定値以下である需要の中から、該需要の始点および終点から一定距離以内に同一既存波長の通過ノードが存在し、該通過ノードのパスに収容した場合、許容遅延時間を満たす需要を、該通過ノードのパスに収容することで、パス集約後の総和の帯域を１インタフェースの帯域未満にすることも好ましい。
【００１６】
また、前記収容は、前記遅延制約量が一定値以下である需要の中で遅延制約量が大きい需要から順に、パス集約後の総和の帯域を１インタフェースの帯域未満になるまで、行うことも好ましい。
【００１７】
上記目的を実現するため本発明によるプログラムは、許容遅延時間を有する需要に対する回線を設計するためのコンピュータを、全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する手段と、前記遅延制約量が一定値以下である需要を、前記手段で設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する手段と、ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記手段で集約できなかった需要を集約する手段として機能させる。
【発明の効果】
【００１８】
本発明のパス集約方法を適用することで、メトロ・コア光ネットワークの設計時に、サービスごとの許容遅延量を最大限に考慮した設計が可能となり、かつ波長数の最小化が実現できるため、ネットワークにおける設備コストの削減に寄与する。
【００１９】
また、本発明で、需要パスの始点、終点にて複数需要が合流するようにルート設計することで、ＯＴＮノード数の増加を抑えて、コストの増加を抑えることが可能になる。さらに、パス集約後の総和の帯域が、１インタフェースの帯域以上になった場合、他の波長に需要を集約することにより波長数を低減させることも可能になる。
【図面の簡単な説明】
【００２０】
【図１】本発明によるフローチャートを示す。
【図２】ステップ１の実施の例を示す。
【図３】ステップ２の実施の例を示す。
【図４】ステップ３の実施の例を示す。
【図５】ステップ４の実施の例を示す。
【図６】ステップ５−１の実施の例を示す。
【図７】ステップ５−２の実施の例を示す。
【図８】ステップ５−３の実施の例を示す。
【図９】ステップ６の実施の例を示す。
【図１０】ステップ７−１の実施の例を示す。
【図１１】ステップ７−２の実施の例を示す。
【図１２】ステップ７−３の実施の例を示す。
【図１３】ステップ６の実施の他の例を示す。
【図１４】ステップ７−１の実施の他の例を示す。
【図１５】ステップ７−２の実施の他の例を示す。
【図１６】ステップ７−３の実施の他の例を示す。
【図１７】ＯＴＮノード数の増加を抑える方法のフローチャートを示す。
【図１８】ＯＴＮノード数の増加を抑える方法の実施例を示す。
【図１９】波長数を低減する方法のフローチャートを示す。
【図２０】波長数を低減する方法の実施例を示す。
【発明を実施するための形態】
【００２１】
本発明を実施するための最良の実施形態について、以下では図面を用いて詳細に説明する。図１は、本発明によるフローチャートを示す。以下、本フローチャートに基づいて説明する。
【００２２】
ステップ１：全ての需要の中で、遅延制約が厳しいものを選択する。その際、まずは全ての需要ｎｎに対して、始点ノード（Ｓ：Source）と終点ノード（Ｄ：Destination）間の直線距離（ｄ（Ｓｎ，Ｄｎ））を求め、この直線距離を最大許容遅延ｌｎで割った値である遅延制約量（ｘｎ）を算出する。当該値が一定レベルαを超えていれば、該当するパスは遅延制約の厳しいパスとしてリスト１−１に登録する。
【００２３】
図２は、ステップ１の実施の例を示す。本例では、需要が、需要ｎ１から需要ｎ１３まで１３本あると仮定する。全需要に対して、
ｘｎ＝（ｄ（Ｓｎ，Ｄｎ））／ｌｎ （ｎ＝１〜１３）
を算出する。本例では、ｘ１からｘ５が一定レベルαを超えているため、これらの需要をリスト１−１に登録する。また、図２に、これらの需要の直線距離を示す。
【００２４】
ステップ２：リスト１−１の中で、ｘｎが最大となる需要を選択し、該需要に対してダイクストラ法でパスを決定する。その時のパスコストは遅延量とする。
【００２５】
図３は、ステップ２の実施の例を示す。本例では、リスト１−１の需要で、ｘｎの最大のものがｘ１であったとする。つまり、
ｘ１＝ｍａｘ（ｘ１、ｘ２、ｘ３、ｘ４、ｘ５）
とする。この場合、需要ｎ１に対して、ダイクストラ法でパスを決定する。決定されたＳ１からＤ１のパスを図３に示す。
【００２６】
ステップ３：ステップ１で登録された需要ｎｉの中で、ステップ２でパス設定した需要のｎｍについて、ｋを一定の閾値として、
ｄ（Ｓｉ，Ｓｍ）＜ｋかつｄ（Ｄｉ，Ｄｍ）＜ｋ、
もしくは
ｄ（Ｓｉ，Ｄｍ）＜ｋかつｄ（Ｄｉ，Ｓｍ）＜ｋ
となる需要ｎｉを選び、ステップ２で決定したパスに集約した時に各々の許容遅延時間を満足できるか否かを確認する。
【００２７】
許容遅延時間を満足できる需要は、ステップ２で決定したパスに集約するものとし、許容遅延時間を満足できないもの、ならびにｄ（Ｓｉ，Ｓｍ）＜ｋかつｄ（Ｄｉ，Ｄｍ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｍ）＜ｋかつｄ（Ｄｉ，Ｓｍ）＜ｋのいずれにも該当しない需要については保留として、これらの需要をリスト１−２に登録する。
【００２８】
ただし、ｄ（Ｓｉ，Ｓｍ）＜ｋかつｄ（Ｄｉ，Ｄｍ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｍ）＜ｋかつｄ（Ｄｉ，Ｓｍ）＜ｋに該当しなくても、Ｓｉ，Ｄｉがステップ２で決定したパス上に存在し、許容遅延時間を満足できる需要は、集約可能とする。
【００２９】
図４は、ステップ３の実施の例を示す。ステップ２でパス設定した需要は、需要n１に相当する。リスト１−１の需要n２から需要n５のなかで、需要n２は、ｄ（Ｓ２，Ｓ１）＜ｋかつｄ（Ｄ２，Ｄ１）＜ｋであり、許容遅延時間を満足できるものとして、需要n１のパスに収容する。また、需要n５は、Ｓ５，Ｄ５ともに需要n１のパス上に存在する。許容遅延時間を満足できるものとして、需要n１のパスに収容する。需要n３と需要n４は、保留とされ、リスト１−２に登録される。
【００３０】
ステップ４：リスト１−２の需要をステップ２のリスト１−１として、ステップ２からステップ３の手順を繰り返す。これらを繰り返して、これ以上集約関係が発生しなくなるまで、繰り返す。
【００３１】
図５は、ステップ４の実施の例を示す。リスト１−２がステップ２に入力され、
ｘ４＝ｍａｘ（ｘ３、ｘ４）
であるとし、需要n４に対して、ステップ２で図５のようにパスが決定される。この後、ステップ３において、ｄ（Ｓ４，Ｓ３）＜ｋかつｄ（Ｄ４，Ｄ３）＜ｋであり、許容遅延時間を満足できるものとして、需要n３は需要n４のパスに収容する最終的に、需要n１、n２、n５は、同一波長λ１に集約され、需要n３、n４は、同一波長λ２に集約される。本例では、これ以上集約関係が発生しなくなるため、次のステップ５に進む。
【００３２】
ステップ５：ステップ１でｘｉ≦αであった需要について、ステップ４までで決定したパスの中に集約可能か否かを検討する。まず第一に、始終点がステップ４までに決定したパスの通過ノードに該当する場合は集約を行なうものとする。次に、ｘｉ≦αとなる需要のＳｉ，Ｄｉがステップ２で決定したパスの始終点を含む通過ノード（Ｓｎ，Ｄｎ）からｄ（Ｓｉ，Ｓｎ）＜ｋかつｄ（Ｄｉ，Ｄｎ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｎ）＜ｋかつｄ（Ｄｉ，Ｓｎ）＜ｋとなるか否かで判断する。上記条件に該当しないもの、もしくは該当しても許容遅延時間で既存パスに集約できないものについてはリスト２に登録する。
【００３３】
図６、図７および図８は、ステップ５の実施の例を示す。需要ｎ１から需要ｎ１３まで１３本のうち、ｘｉ≦αであった需要は、需要ｎ６から需要ｎ１３であった。図６に示すように、需要ｎ６は、始終点（Ｓ６、Ｄ６）が波長λ１のパス上の通過ノードであるため、許容遅延時間を満たせば、波長λ１に集約される。また、図７に示すように、需要ｎ７は、波長λ１のパスの通過ノードからｋ以内に位置しているため、許容遅延時間を満たせば、波長λ１に集約される。
【００３４】
しかし、需要ｎ８から需要ｎ１３は、図８に示すように、波長λ１のパスおよび波長λ２のパスの通過ノードでなく、さらに波長λ１のパスおよび波長λ２のパスの通過ノードからｋ以内に位置していないため、これらはリスト２に登録される。
【００３５】
ステップ６：リスト２に挙げられた需要のＳ／Ｄノードを結ぶ直線を可能な限り多く通過するようにネットワークのグラフを分割する。ただし、グラフを分割する線（以下分割線と呼ぶ）は、分割線が交差しないように、一意に下方向（もしくは上方向）に引く。ここで、ネットワーク全体を２分割した分割線は、各需要のＳ、Ｄがそれぞれ異なる集合に属するように分離するものである。分割した区画の中で集約の起点となるノードを決定する。起点となるノードは、それぞれの区画の中にあるリスト２の需要のＳ／Ｄノードからの直線距離の総和が最小となる、もしくはホップ数の総和が最小となるノードとする。この起点のノード間にパスを設定し、このパスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たせば、このパスに集約する。集約した結果、全てのパスが遅延などの制約を満たせるようであれば、ここで処理を終了する。
【００３６】
図９は、ステップ６の実施の例を示す。本例では、点線の分割線でグラフを分割する。ここでは、需要ｎ８から需要ｎ１３のＳ／Ｄノードを結ぶ直線を全て通過するように分割している。ただし、本例では、２分割しただけでは、同一区画内でパスを１波長に集約することは不可能である。
【００３７】
ステップ７：ステップ６で、全てのパスが遅延などの制約を満たせなかった場合、ステップ６の分割線と交差する方向（つまり決してステップ６の分割線と平行にはならない方向）で２本目の分割線を引き、グラフを４分割する。４分割する時には、それぞれの新しい区画でノード数が可能な限り均等になるように分割する。新しく出来た４区画の中でステップ６と同様の方法で起点となるノードを探索し、集約を行なう。それでも、全てのパスが制約を満たさないようであれば、１本目の分割線と交差する分割線を引き直し、グラフ全体が６分割、８分割・・・となるように分割数を増加させ、同様の処理を全てのパスが集約できるまで繰り返す。ただし、ステップ６からステップ７の中で"集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数"となった場合には、これ以上波長数が減少することはないため、例外なく直ちに処理を止め、集約できなかったパスについては単独に波長を割り当てる。
【００３８】
図１０、図１１、および図１２は、ステップ７の実施の例を示す。図１０では、１本目の分割線に交わる形で２本目の分割線を引く。本例では、４区画に分割しても、同一区画の中の需要のＳ，Ｄが離れすぎているので、互いの許容遅延時間を満たしながら集約できない。このため、図１１のように、１本目の分割線と交差する分割線を２本引き直し、６区画に分割する。６区画に分割すると、図１２に示すように全ての需要の許容遅延時間を満たしながら、複数需要を同一波長に集約可能となる。
【００３９】
具体的には、図１２の黒点で示されるノードが各区画での起点ノードになる。区画１の起点ノードと区画２の起点ノードに設定されたパスが、需要ｎ９と需要ｎ１１を集約し、区画３の起点ノードと区画４の起点ノードに設定されたパスが、需要ｎ１０と需要ｎ１２を集約し、区画５の起点ノードと区画６の起点ノードに設定されたパスが需要ｎ８と需要ｎ１３を集約する。
【００４０】
ステップ６およびステップ７について、グラフを他の方法で分割して、需要を集約することも可能である。以下に他の方法によるステップ６およびステップ７を示す。
【００４１】
ステップ６：リスト２に挙げられた需要のＳ／Ｄ間の距離が最長となる需要を抽出する。当該需要の始点ノードを集合Ａ、終点ノードを集合Ｂに含めるとすると、その他の需要については、当該需要の始点ノードからより距離の近い端点（始点ノードもしくは終点ノード）を集合Ａ、他方をＢに属するものとする。また、仮に集約した需要同士が完全に同じパス上を通る場合には、最長のパスの始終点のノードを起点とする。
【００４２】
例外として、ＳからもＤからも誤差Ａの範囲内でほぼ距離が同じものについては、集約の対象から外すものとする。これらについては、各々について単独で波長を割り当てるか、もしくはこれらを纏めて上記のように集約するか、波長数が少なくなる方を適用するものとする。
【００４３】
それぞれの集合Ａ，Ｂにおいて、集約するパスの起点となるノードを定めるが、起点となるノードは、それぞれの集合に属するノードからの距離の総和が最小、もしくはホップ数が最小となるノードを選ぶものとする。このパスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たせば、このパスに集約する。集約した結果、全てのパスが遅延などの制約を満たせるようであれば、ここで処理を終了する。
【００４４】
図１３はステップ６の実施の例を示す。本例では、区画１と区画２のように、最も始終点間の距離の離れた需要ｎ１２の始点を集合Ａ（区画１）、終点を集合Ｂ（区画２）に分割し、需要ｎ８〜需要ｎ１３の上記以外の需要についても始終点を区画１，２に分割することで、集合Ａ，Ｂを構成するものとする。
【００４５】
ステップ７：ステップ６の２区画に分割、集約した場合に全てのパスについて遅延などの制約条件を満たせなかった場合、ステップ６の集合Ａ，Ｂをそれぞれ分割し、ｎ個のノード集合を構成する（ｎ：偶数）。このとき、同一集合に属する始点（終点）ノードの終点（始点）ノードは、別の同一集合に属することを条件とする。つまり、図１４のような例では、需要ｎ１０ならびにｎ１２の始終点が異なる集合に属しているため、不適当であり、かつ需要同士の距離が離れているため、集約が困難である。一方、図１５では、上述の条件を満たした区分けとなっている。図１５の区分けに基づき、図１６にようにそれぞれの区画（集合）における起点のノードを決定し、パスの集約を行なう。ここで、全ての需要が遅延制約を満たせば、パスが設定完了となる。図１４〜１６の例のように仮に４区画に分割しても条件を満たさない場合、また遅延制約を満たさない場合については、６区画、８区画・・・となるように区画数を増加させ、全てのパスが集約できるまで繰り返す。ただし、ステップ６からステップ７の中で“集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数”となった場合には、これ以上波長数が減少することはないため、例外なく直ちに処理を止め、集約できなかったパスについては単独に波長を割り当てる。
【００４６】
具体的には、図１６の黒点で示されるノードが各区画での起点ノードになる。区画１の起点ノードと区画２の起点ノードに設定されたパスが、需要ｎ９と需要ｎ１１を集約し、区画３の起点ノードと区画４の起点ノードに設定されたパスが、需要ｎ１０と需要ｎ１２を集約し、区画５の起点ノードと区画６の起点ノードに設定されたパスが需要ｎ８と需要ｎ１３を集約する。
【００４７】
なお、前記ステップで、全てのパスの始終点にはＯＴＮクロスコネクト、もしくはより低速の回線を高速回線に集約可能な上記に類するネットワーク装置が挿入されるものとする。また、レイヤ０の光スイッチングノードとしては、ＲＯＡＤＭもしくはＷＸＣが適用することができるが、４方路以上の方路を有する光スイッチングノードについては、ＷＸＣを優先的に使うものとする。
【００４８】
また、前記ステップでパスを集約する場合、リンク当たりの波長数の上限を考慮して集約する。例として、λｎの上限を超えた需要同士を集約して、別の波長λｍを割り振るものとする。このとき、λｍのパスはλｎと全く同一のパスを通っても良いが、λｍに集約される需要同士でステップ６および７のように起点のノードを定めてパスを設定しても良い。
【００４９】
また、前記ステップでパスを集約した後、ＯＳＮＲ（Optical Signal to Noise Ratio）の制約条件を満たさない需要が存在した場合には、３ＲもしくはＯＴＮ−ＸＣ（ユニバーサルスイッチ）を始終点にあたらないノードに挿入して、パスがＯＳＮＲの制約条件を満たすようにする。
【００５０】
なお、上記の実施例では、各需要に対して１本のパスのみ表示しているが、単一の需要に対して現用パス／予備回線の双方を設定する必要がある場合には、現用回線が通過したリンクおよび中継ノード（始終点は含まない）は勿論のこと、中継ノードに接続されたリンクを通らないように（計算上はパスコストを無限大とする）予備回線の経路を定めることとする。
【００５１】
なお、上記の実施形態のステップ５で需要を単一ルートに合流・同一波長へ集約する際に、波長ごとにＯＴＮノードをいずれの局に設置すべきかを検討する必要がある。しかしながら、本来ＯＴＮノードは複数波長間で共用可能にもかかわらず、波長ごとにＯＴＮを設置したことにより、結果としてＯＴＮノード数が増大し、結果としてコスト増大を招いていた。
【００５２】
前述のように、需要パスの始点、終点に相当するノードについては、全てＯＴＮノードが設置されるため、需要パスの始点、終点にて需要が合流するようにルート設計することで、ＯＴＮノード数の増加を抑えて、コストの増加を抑えることが可能になる。図１７は、ＯＴＮノード数の増加を抑える方法のフローチャートを示す。
【００５３】
ここで、ｘｉ≦αとなる需要ｎｉのＳｉ，Ｄｉがステップ２で決定したパスの始終点を含む通過ノード（Ｓｎ，Ｄｎ）からｄ（Ｓｉ，Ｓｎ）＜ｋかつｄ（Ｄｉ，Ｄｎ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｎ）＜ｋかつｄ（Ｄｉ，Ｓｎ）＜ｋであったとする。
【００５４】
ステップ５１：ＯＴＮが存在するノードを把握するためＯＴＮノードリスト（Ｏｉ：ｉ＝１〜ｎ、ｎはＯＴＮノード数）を作成する。最初は、少なくとも全需要の始点ノードと終点ノードがＯＴＮノードリストに含まれる。
ステップ５２：集約する需要ｎｉの始点Ｓｉから、ｋ’を一定の閾値として、ｄ（Ｓｉ、Ｏｊ）＜ｋ’を満たすＯＴＮノードＯｊが存在するか確認する。存在する場合、ステップ５３に進む、存在しない場合、ステップ５４に進む。
ステップ５３：前記ＯＴＮノードＯｊに需要ｎｉの始点を集約する。
ステップ５４：もっとも近傍の通過ノードをＯＴＮノードに変換して、該ノードをＯＴＮノードリストに含める。
ステップ５５：集約する需要ｎｉの終点Ｄｉから、ｋ’を一定の閾値として、ｄ（Ｄｉ、Ｏｊ）＜ｋ’を満たすＯＴＮノードＯｊが存在するか確認する。存在する場合、ステップ５６に進む、存在しない場合、ステップ５７に進む。
ステップ５６：前記ＯＴＮノードＯｊに需要ｎｉの終点を集約する。
ステップ５７：もっとも近傍の通過ノードをＯＴＮノードに変換して、該ノードをＯＴＮノードリストに含める。
【００５５】
図１８は、ＯＴＮノード数の増加を抑える方法の実施例を示す。需要ｎｉのＳｉがｄ（Ｓｉ，Ｓｎ）＜ｋであったとする。始点Ｓｉにおいて、ｄ（Ｓｉ、Ｏｊ）＜ｋ’を満たすＯＴＮノードＯｊが存在する。このため、ＳｉはＳｎではなくＯｊに収容する。
【００５６】
また、上記の実施形態のステップ６、７で需要パスを集約した後、パス集約後の総和の帯域が、１インタフェースが有する帯域以上になった場合、同一ルートにおいて、別波長を割り当てていた。しかしながら、上記とは関連の無い異なる波長においては、集約後の帯域の総和が１インタフェースが有する帯域以下であり、他の需要を集約できる可能性があるものも存在する。
【００５７】
このため、集約予定としていた全需要の中で、遅延制約の緩い需要（ステップ１でｘｉ≦αであった需要）の数量を把握し、これらすべてを別波長に割り当てた場合、１波長当たりの帯域の総和が１インタフェースが有する帯域未満となるか否かについて確認する。１インタフェースの帯域未満となるようであれば、その中で遅延制約の厳しいものから順に当該需要の始点／終点から所定の距離Ｐ以内に通過ノードが存在する波長へ集約される。
【００５８】
図１９は、波長数を低減する方法のフローチャートを示す。本方法は、ステップ６、７が行われ、全需要が集約した後に全ての需要パスに対して行われる。
ステップ７１：集約を予定していた需要の帯域の総和が１インタフェースが有する帯域を上回るか否かについて確認する。当該帯域未満である場合、波長再割り当ての必要がないため終了する。
ステップ７２：集約を予定していた需要の中で、遅延制約の緩い需要のみを異波長に割り当てた場合、残りの需要の帯域の総和が、１インタフェースが有する帯域を下回るか否かについて確認する。下回る場合、他の波長への再割り当てが不可能であるため終了する。
ステップ７３：上記ステップの遅延制約の緩い需要を、遅延制約の厳しい順に番号（昇順）を付与する。
ステップ７４：上記ステップで割り振った番号の小さい方（つまり、遅延制約の厳しい需要パス）から順に当該需要の始点および終点から所定の半径Ｐ以内に同一既存波長の通過ノードが存在するか確認する。１つも存在しない場合、他の波長への再割り当てが不可能であるため終了する。
ステップ７５：上記ステップで確認した需要を前記通過ノードの需要パスに収容した場合、許容遅延時間を満足できるか否かを確認する（複数波長に該当する場合は全てチェックし、空き帯域の多い波長に収容）。許容遅延時間を満足できるルートがない１つもない場合は、他の波長への再割り当てが不可能であるため終了する。
ステップ７６：上記ステップで確認した需要を割り振った番号の小さい方から、全需要の帯域の総和が１インタフェースが有する帯域未満になるまで取り除き、波長の再割り当てが完了し、終了する。
【００５９】
図２０は、波長数を低減する方法の実施例を示す。ステップ６、７では需要ｄ（Ｓｎ，Ｄｎ）は、需要パスλ１に集約される。しかし、需要ｄを集約した場合、１波長当たりの帯域の総和が１インタフェースの帯域以上になる。需要ｄが遅延制約の緩い需要であり、需要ｄの始点および終点から所定の半径Ｐ以内に同一既存波長λｎの通過ノードが存在する。さらに、λｎに収容した場合、需要ｄの許容遅延時間を満足できる場合、需要ｄをλｎに収容することにより、需要パスλ１を波長数を低減することが可能になる。
【００６０】
本発明によるトランスポート回線設計方法は、コンピュータを、上述した各ステップを機能させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。さらに、本発明は、ハードウェア及びソフトウェアの組合せによっても実現可能である。
【００６１】
また、以上述べた実施形態は全て本発明を例示的に示すものであって限定的に示すものではなく、本発明は他の種々の変形態様および変更態様で実施することができる。従って本発明の範囲は特許請求の範囲およびその均等範囲によってのみ規定されるものである。
【技術分野】
【０００１】
本発明は、顧客の要求する最大許容遅延を考慮した波長数最小化のための効率的な回線設計方法およびプログラムに関し、ＯＴＮ(Optical Transport Network)やＭＰＬＳ−ＴＰ(Multi Protocol Label Switching-Transport Profile)等の回線を収容・集約可能なノードで構成されるトランスポートネットワークを対象としている。
【背景技術】
【０００２】
従来、波長の有効活用のため、複数パスを単一波長に集約する技術が提案されてきた（非特許文献１−５）。非特許文献２−５は、トポロジーがリング型のネットワークに限定されたものである。非特許文献１は、メッシュ型ネットワークにもフレキシブルに適用可能な方式である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】I.Yagyu et.al., "An EfficientHierarchical Optical Path Network Design Algorithm based on a Traffic DemandExpression in a Cartesian Product Space," IEEE Journalon Selected Areas In Communications, Vol.26, No.6, pp.22-31, August 2008.
【非特許文献２】A..L.Chiu et al., "TrafficGrooming Algorithm for Reducing Electronic Multiplexing Costs in WDM RingNetworks," Journal of Lightwave Technology, Vol.18, No.1, pp.2-12, January2000.
【非特許文献３】O.Gerstel,et.al.,"Cost-Effective Traffic Grooming in WDM Rings," IEEE/ACM Transactionon Networking, Vol.8, No.5, pp.618-630, October 2000.
【非特許文献４】X.Zhang et.al., "An Effectiveand Comprehensive Approach for Traffic Grooming and Wavelength Assignment inSONET/WDM Rings," Vol.8, No.5, pp.608-617, October 2000.
【非特許文献５】J. M.Simmons et al.,"Quantifying the Benefit of Wavelength Add-Drop in WDM Rings withDistance-Independent and Dependent Traffic," Journal of LightwaveTechnol.Vol.17, No.1, January 1999.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これらの方式では各トラヒック需要における許容遅延量を考慮していないといった問題点がある。
【０００５】
したがって、本発明は、許容遅延量を考慮した波長数最小化のための効率的な回線設計方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を実現するため本発明による回線設計方法は、許容遅延時間を有する需要に対する回線設計方法において、全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する第１のステップと、前記遅延制約量が一定値以下である需要を、前記第１のステップで設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する第２のステップと、ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記第２のステップで集約できなかった需要を集約する第３のステップとを有する。
【０００７】
また、前記第１のステップは、全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要をリスト１に登録する第１のサブステップと、前記リスト１に登録された需要の中から、最も遅延制約が厳しい需要を求め、該需要について、最短パスを設定する第２のサブステップと、前記リスト１に登録された需要の中で、前記設定されたパスの通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、前記設定された遅延制約の最も厳しいパスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、前記設定された遅延制約の最も厳しいパスに集約する第３のサブステップと、前記第３のサブステップで集約されなかった前記リスト１に登録された需要を新たにリスト１として、前記第２のサブステップと前記第３のサブステップを集約関係が発生しなくなるまで繰り返す第４のサブステップとを有し、
前記第２のステップは、前記遅延制約量が一定値以下である需要の中で、前記第１のステップで設定されたパスの始終点を含む通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、該パスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約し、集約できない需要をリスト２に登録する第５のサブステップであり、
前記第３のステップは、前記リスト２に登録された需要の始点ノードと終点ノード間を結ぶ線を可能な限り多く通過するようにネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第６のサブステップと、前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を１本引き、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、前記第７のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を引き直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップとを有することも好ましい。
【０００８】
また、前記第５のサブステップは、該需要の始点または終点から一定距離以内にＯＴＮノードが存在し、該ＯＴＮノードに該需要の始点または終点を収容した場合、許容遅延時間を満たすか否か確認し、満たす場合は、該需要の始点または終点を該ＯＴＮノードに集約することをさらに備えることも好ましい。
【０００９】
また、前記第７のサブステップと前記第８のサブステップで、それぞれの新しい区画でノード数が可能な限り均等になるように分割することも好ましい。
【００１０】
また、前記第３のステップの別の方式としては、前記リスト２に登録された需要のなかで、始点ノードと終点ノード間の距離が最長となる需要を抽出し、当該需要の始点ノードを集合Ａ、終点ノードを集合Ｂに含め、他の需要は、当該需要の始点ノードからより距離の近い端点（始点ノードまたは終点ノード）を集合Ａ、他方をＢに属するように、ネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否かを確認し、満たす場合は、該パスに集約する第６のサブステップと、前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの集合Ａ、Ｂを、同一集合に属する始点ノードの終点ノード、および終点ノードの始点ノードが、別の同一集合に属する条件を満たすように、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、前記第７のサブステップまでに全ての需要が集約できない場合または前記条件を満たすように分割できない場合、前記第６のサブステップの条件を満たす区画に分割し直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップとであることも好ましい。
【００１１】
また、前記遅延制約量は、始点ノードと終点ノード間の直線距離を許容遅延時間で割った値であることも好ましい。
【００１２】
また、前記最短パスは、遅延時間をパスコストとして、ダイクストラ法で決定されることも好ましい。
【００１３】
また、前記起点となるノードは、前記区画の中にあり、前記リスト２に登録された需要の起点ノードと終点ノードからの直線距離の総和が最小となる、もしくはホップ数の総和が最小となるノードであることも好ましい。
【００１４】
また、前記第７のサブステップと前記第８のサブステップで、集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数となった場合、集約できなかったパスについては単独に波長を割り当てることも好ましい。
【００１５】
また、前記第３のステップ終了後、パス集約後の総和の帯域が、１インタフェースが有する帯域以上になった場合、
集約予定としていた全需要の中で、前記遅延制約量が一定値以下である需要の中から、該需要の始点および終点から一定距離以内に同一既存波長の通過ノードが存在し、該通過ノードのパスに収容した場合、許容遅延時間を満たす需要を、該通過ノードのパスに収容することで、パス集約後の総和の帯域を１インタフェースの帯域未満にすることも好ましい。
【００１６】
また、前記収容は、前記遅延制約量が一定値以下である需要の中で遅延制約量が大きい需要から順に、パス集約後の総和の帯域を１インタフェースの帯域未満になるまで、行うことも好ましい。
【００１７】
上記目的を実現するため本発明によるプログラムは、許容遅延時間を有する需要に対する回線を設計するためのコンピュータを、全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する手段と、前記遅延制約量が一定値以下である需要を、前記手段で設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する手段と、ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記手段で集約できなかった需要を集約する手段として機能させる。
【発明の効果】
【００１８】
本発明のパス集約方法を適用することで、メトロ・コア光ネットワークの設計時に、サービスごとの許容遅延量を最大限に考慮した設計が可能となり、かつ波長数の最小化が実現できるため、ネットワークにおける設備コストの削減に寄与する。
【００１９】
また、本発明で、需要パスの始点、終点にて複数需要が合流するようにルート設計することで、ＯＴＮノード数の増加を抑えて、コストの増加を抑えることが可能になる。さらに、パス集約後の総和の帯域が、１インタフェースの帯域以上になった場合、他の波長に需要を集約することにより波長数を低減させることも可能になる。
【図面の簡単な説明】
【００２０】
【図１】本発明によるフローチャートを示す。
【図２】ステップ１の実施の例を示す。
【図３】ステップ２の実施の例を示す。
【図４】ステップ３の実施の例を示す。
【図５】ステップ４の実施の例を示す。
【図６】ステップ５−１の実施の例を示す。
【図７】ステップ５−２の実施の例を示す。
【図８】ステップ５−３の実施の例を示す。
【図９】ステップ６の実施の例を示す。
【図１０】ステップ７−１の実施の例を示す。
【図１１】ステップ７−２の実施の例を示す。
【図１２】ステップ７−３の実施の例を示す。
【図１３】ステップ６の実施の他の例を示す。
【図１４】ステップ７−１の実施の他の例を示す。
【図１５】ステップ７−２の実施の他の例を示す。
【図１６】ステップ７−３の実施の他の例を示す。
【図１７】ＯＴＮノード数の増加を抑える方法のフローチャートを示す。
【図１８】ＯＴＮノード数の増加を抑える方法の実施例を示す。
【図１９】波長数を低減する方法のフローチャートを示す。
【図２０】波長数を低減する方法の実施例を示す。
【発明を実施するための形態】
【００２１】
本発明を実施するための最良の実施形態について、以下では図面を用いて詳細に説明する。図１は、本発明によるフローチャートを示す。以下、本フローチャートに基づいて説明する。
【００２２】
ステップ１：全ての需要の中で、遅延制約が厳しいものを選択する。その際、まずは全ての需要ｎｎに対して、始点ノード（Ｓ：Source）と終点ノード（Ｄ：Destination）間の直線距離（ｄ（Ｓｎ，Ｄｎ））を求め、この直線距離を最大許容遅延ｌｎで割った値である遅延制約量（ｘｎ）を算出する。当該値が一定レベルαを超えていれば、該当するパスは遅延制約の厳しいパスとしてリスト１−１に登録する。
【００２３】
図２は、ステップ１の実施の例を示す。本例では、需要が、需要ｎ１から需要ｎ１３まで１３本あると仮定する。全需要に対して、
ｘｎ＝（ｄ（Ｓｎ，Ｄｎ））／ｌｎ （ｎ＝１〜１３）
を算出する。本例では、ｘ１からｘ５が一定レベルαを超えているため、これらの需要をリスト１−１に登録する。また、図２に、これらの需要の直線距離を示す。
【００２４】
ステップ２：リスト１−１の中で、ｘｎが最大となる需要を選択し、該需要に対してダイクストラ法でパスを決定する。その時のパスコストは遅延量とする。
【００２５】
図３は、ステップ２の実施の例を示す。本例では、リスト１−１の需要で、ｘｎの最大のものがｘ１であったとする。つまり、
ｘ１＝ｍａｘ（ｘ１、ｘ２、ｘ３、ｘ４、ｘ５）
とする。この場合、需要ｎ１に対して、ダイクストラ法でパスを決定する。決定されたＳ１からＤ１のパスを図３に示す。
【００２６】
ステップ３：ステップ１で登録された需要ｎｉの中で、ステップ２でパス設定した需要のｎｍについて、ｋを一定の閾値として、
ｄ（Ｓｉ，Ｓｍ）＜ｋかつｄ（Ｄｉ，Ｄｍ）＜ｋ、
もしくは
ｄ（Ｓｉ，Ｄｍ）＜ｋかつｄ（Ｄｉ，Ｓｍ）＜ｋ
となる需要ｎｉを選び、ステップ２で決定したパスに集約した時に各々の許容遅延時間を満足できるか否かを確認する。
【００２７】
許容遅延時間を満足できる需要は、ステップ２で決定したパスに集約するものとし、許容遅延時間を満足できないもの、ならびにｄ（Ｓｉ，Ｓｍ）＜ｋかつｄ（Ｄｉ，Ｄｍ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｍ）＜ｋかつｄ（Ｄｉ，Ｓｍ）＜ｋのいずれにも該当しない需要については保留として、これらの需要をリスト１−２に登録する。
【００２８】
ただし、ｄ（Ｓｉ，Ｓｍ）＜ｋかつｄ（Ｄｉ，Ｄｍ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｍ）＜ｋかつｄ（Ｄｉ，Ｓｍ）＜ｋに該当しなくても、Ｓｉ，Ｄｉがステップ２で決定したパス上に存在し、許容遅延時間を満足できる需要は、集約可能とする。
【００２９】
図４は、ステップ３の実施の例を示す。ステップ２でパス設定した需要は、需要n１に相当する。リスト１−１の需要n２から需要n５のなかで、需要n２は、ｄ（Ｓ２，Ｓ１）＜ｋかつｄ（Ｄ２，Ｄ１）＜ｋであり、許容遅延時間を満足できるものとして、需要n１のパスに収容する。また、需要n５は、Ｓ５，Ｄ５ともに需要n１のパス上に存在する。許容遅延時間を満足できるものとして、需要n１のパスに収容する。需要n３と需要n４は、保留とされ、リスト１−２に登録される。
【００３０】
ステップ４：リスト１−２の需要をステップ２のリスト１−１として、ステップ２からステップ３の手順を繰り返す。これらを繰り返して、これ以上集約関係が発生しなくなるまで、繰り返す。
【００３１】
図５は、ステップ４の実施の例を示す。リスト１−２がステップ２に入力され、
ｘ４＝ｍａｘ（ｘ３、ｘ４）
であるとし、需要n４に対して、ステップ２で図５のようにパスが決定される。この後、ステップ３において、ｄ（Ｓ４，Ｓ３）＜ｋかつｄ（Ｄ４，Ｄ３）＜ｋであり、許容遅延時間を満足できるものとして、需要n３は需要n４のパスに収容する最終的に、需要n１、n２、n５は、同一波長λ１に集約され、需要n３、n４は、同一波長λ２に集約される。本例では、これ以上集約関係が発生しなくなるため、次のステップ５に進む。
【００３２】
ステップ５：ステップ１でｘｉ≦αであった需要について、ステップ４までで決定したパスの中に集約可能か否かを検討する。まず第一に、始終点がステップ４までに決定したパスの通過ノードに該当する場合は集約を行なうものとする。次に、ｘｉ≦αとなる需要のＳｉ，Ｄｉがステップ２で決定したパスの始終点を含む通過ノード（Ｓｎ，Ｄｎ）からｄ（Ｓｉ，Ｓｎ）＜ｋかつｄ（Ｄｉ，Ｄｎ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｎ）＜ｋかつｄ（Ｄｉ，Ｓｎ）＜ｋとなるか否かで判断する。上記条件に該当しないもの、もしくは該当しても許容遅延時間で既存パスに集約できないものについてはリスト２に登録する。
【００３３】
図６、図７および図８は、ステップ５の実施の例を示す。需要ｎ１から需要ｎ１３まで１３本のうち、ｘｉ≦αであった需要は、需要ｎ６から需要ｎ１３であった。図６に示すように、需要ｎ６は、始終点（Ｓ６、Ｄ６）が波長λ１のパス上の通過ノードであるため、許容遅延時間を満たせば、波長λ１に集約される。また、図７に示すように、需要ｎ７は、波長λ１のパスの通過ノードからｋ以内に位置しているため、許容遅延時間を満たせば、波長λ１に集約される。
【００３４】
しかし、需要ｎ８から需要ｎ１３は、図８に示すように、波長λ１のパスおよび波長λ２のパスの通過ノードでなく、さらに波長λ１のパスおよび波長λ２のパスの通過ノードからｋ以内に位置していないため、これらはリスト２に登録される。
【００３５】
ステップ６：リスト２に挙げられた需要のＳ／Ｄノードを結ぶ直線を可能な限り多く通過するようにネットワークのグラフを分割する。ただし、グラフを分割する線（以下分割線と呼ぶ）は、分割線が交差しないように、一意に下方向（もしくは上方向）に引く。ここで、ネットワーク全体を２分割した分割線は、各需要のＳ、Ｄがそれぞれ異なる集合に属するように分離するものである。分割した区画の中で集約の起点となるノードを決定する。起点となるノードは、それぞれの区画の中にあるリスト２の需要のＳ／Ｄノードからの直線距離の総和が最小となる、もしくはホップ数の総和が最小となるノードとする。この起点のノード間にパスを設定し、このパスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たせば、このパスに集約する。集約した結果、全てのパスが遅延などの制約を満たせるようであれば、ここで処理を終了する。
【００３６】
図９は、ステップ６の実施の例を示す。本例では、点線の分割線でグラフを分割する。ここでは、需要ｎ８から需要ｎ１３のＳ／Ｄノードを結ぶ直線を全て通過するように分割している。ただし、本例では、２分割しただけでは、同一区画内でパスを１波長に集約することは不可能である。
【００３７】
ステップ７：ステップ６で、全てのパスが遅延などの制約を満たせなかった場合、ステップ６の分割線と交差する方向（つまり決してステップ６の分割線と平行にはならない方向）で２本目の分割線を引き、グラフを４分割する。４分割する時には、それぞれの新しい区画でノード数が可能な限り均等になるように分割する。新しく出来た４区画の中でステップ６と同様の方法で起点となるノードを探索し、集約を行なう。それでも、全てのパスが制約を満たさないようであれば、１本目の分割線と交差する分割線を引き直し、グラフ全体が６分割、８分割・・・となるように分割数を増加させ、同様の処理を全てのパスが集約できるまで繰り返す。ただし、ステップ６からステップ７の中で"集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数"となった場合には、これ以上波長数が減少することはないため、例外なく直ちに処理を止め、集約できなかったパスについては単独に波長を割り当てる。
【００３８】
図１０、図１１、および図１２は、ステップ７の実施の例を示す。図１０では、１本目の分割線に交わる形で２本目の分割線を引く。本例では、４区画に分割しても、同一区画の中の需要のＳ，Ｄが離れすぎているので、互いの許容遅延時間を満たしながら集約できない。このため、図１１のように、１本目の分割線と交差する分割線を２本引き直し、６区画に分割する。６区画に分割すると、図１２に示すように全ての需要の許容遅延時間を満たしながら、複数需要を同一波長に集約可能となる。
【００３９】
具体的には、図１２の黒点で示されるノードが各区画での起点ノードになる。区画１の起点ノードと区画２の起点ノードに設定されたパスが、需要ｎ９と需要ｎ１１を集約し、区画３の起点ノードと区画４の起点ノードに設定されたパスが、需要ｎ１０と需要ｎ１２を集約し、区画５の起点ノードと区画６の起点ノードに設定されたパスが需要ｎ８と需要ｎ１３を集約する。
【００４０】
ステップ６およびステップ７について、グラフを他の方法で分割して、需要を集約することも可能である。以下に他の方法によるステップ６およびステップ７を示す。
【００４１】
ステップ６：リスト２に挙げられた需要のＳ／Ｄ間の距離が最長となる需要を抽出する。当該需要の始点ノードを集合Ａ、終点ノードを集合Ｂに含めるとすると、その他の需要については、当該需要の始点ノードからより距離の近い端点（始点ノードもしくは終点ノード）を集合Ａ、他方をＢに属するものとする。また、仮に集約した需要同士が完全に同じパス上を通る場合には、最長のパスの始終点のノードを起点とする。
【００４２】
例外として、ＳからもＤからも誤差Ａの範囲内でほぼ距離が同じものについては、集約の対象から外すものとする。これらについては、各々について単独で波長を割り当てるか、もしくはこれらを纏めて上記のように集約するか、波長数が少なくなる方を適用するものとする。
【００４３】
それぞれの集合Ａ，Ｂにおいて、集約するパスの起点となるノードを定めるが、起点となるノードは、それぞれの集合に属するノードからの距離の総和が最小、もしくはホップ数が最小となるノードを選ぶものとする。このパスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たせば、このパスに集約する。集約した結果、全てのパスが遅延などの制約を満たせるようであれば、ここで処理を終了する。
【００４４】
図１３はステップ６の実施の例を示す。本例では、区画１と区画２のように、最も始終点間の距離の離れた需要ｎ１２の始点を集合Ａ（区画１）、終点を集合Ｂ（区画２）に分割し、需要ｎ８〜需要ｎ１３の上記以外の需要についても始終点を区画１，２に分割することで、集合Ａ，Ｂを構成するものとする。
【００４５】
ステップ７：ステップ６の２区画に分割、集約した場合に全てのパスについて遅延などの制約条件を満たせなかった場合、ステップ６の集合Ａ，Ｂをそれぞれ分割し、ｎ個のノード集合を構成する（ｎ：偶数）。このとき、同一集合に属する始点（終点）ノードの終点（始点）ノードは、別の同一集合に属することを条件とする。つまり、図１４のような例では、需要ｎ１０ならびにｎ１２の始終点が異なる集合に属しているため、不適当であり、かつ需要同士の距離が離れているため、集約が困難である。一方、図１５では、上述の条件を満たした区分けとなっている。図１５の区分けに基づき、図１６にようにそれぞれの区画（集合）における起点のノードを決定し、パスの集約を行なう。ここで、全ての需要が遅延制約を満たせば、パスが設定完了となる。図１４〜１６の例のように仮に４区画に分割しても条件を満たさない場合、また遅延制約を満たさない場合については、６区画、８区画・・・となるように区画数を増加させ、全てのパスが集約できるまで繰り返す。ただし、ステップ６からステップ７の中で“集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数”となった場合には、これ以上波長数が減少することはないため、例外なく直ちに処理を止め、集約できなかったパスについては単独に波長を割り当てる。
【００４６】
具体的には、図１６の黒点で示されるノードが各区画での起点ノードになる。区画１の起点ノードと区画２の起点ノードに設定されたパスが、需要ｎ９と需要ｎ１１を集約し、区画３の起点ノードと区画４の起点ノードに設定されたパスが、需要ｎ１０と需要ｎ１２を集約し、区画５の起点ノードと区画６の起点ノードに設定されたパスが需要ｎ８と需要ｎ１３を集約する。
【００４７】
なお、前記ステップで、全てのパスの始終点にはＯＴＮクロスコネクト、もしくはより低速の回線を高速回線に集約可能な上記に類するネットワーク装置が挿入されるものとする。また、レイヤ０の光スイッチングノードとしては、ＲＯＡＤＭもしくはＷＸＣが適用することができるが、４方路以上の方路を有する光スイッチングノードについては、ＷＸＣを優先的に使うものとする。
【００４８】
また、前記ステップでパスを集約する場合、リンク当たりの波長数の上限を考慮して集約する。例として、λｎの上限を超えた需要同士を集約して、別の波長λｍを割り振るものとする。このとき、λｍのパスはλｎと全く同一のパスを通っても良いが、λｍに集約される需要同士でステップ６および７のように起点のノードを定めてパスを設定しても良い。
【００４９】
また、前記ステップでパスを集約した後、ＯＳＮＲ（Optical Signal to Noise Ratio）の制約条件を満たさない需要が存在した場合には、３ＲもしくはＯＴＮ−ＸＣ（ユニバーサルスイッチ）を始終点にあたらないノードに挿入して、パスがＯＳＮＲの制約条件を満たすようにする。
【００５０】
なお、上記の実施例では、各需要に対して１本のパスのみ表示しているが、単一の需要に対して現用パス／予備回線の双方を設定する必要がある場合には、現用回線が通過したリンクおよび中継ノード（始終点は含まない）は勿論のこと、中継ノードに接続されたリンクを通らないように（計算上はパスコストを無限大とする）予備回線の経路を定めることとする。
【００５１】
なお、上記の実施形態のステップ５で需要を単一ルートに合流・同一波長へ集約する際に、波長ごとにＯＴＮノードをいずれの局に設置すべきかを検討する必要がある。しかしながら、本来ＯＴＮノードは複数波長間で共用可能にもかかわらず、波長ごとにＯＴＮを設置したことにより、結果としてＯＴＮノード数が増大し、結果としてコスト増大を招いていた。
【００５２】
前述のように、需要パスの始点、終点に相当するノードについては、全てＯＴＮノードが設置されるため、需要パスの始点、終点にて需要が合流するようにルート設計することで、ＯＴＮノード数の増加を抑えて、コストの増加を抑えることが可能になる。図１７は、ＯＴＮノード数の増加を抑える方法のフローチャートを示す。
【００５３】
ここで、ｘｉ≦αとなる需要ｎｉのＳｉ，Ｄｉがステップ２で決定したパスの始終点を含む通過ノード（Ｓｎ，Ｄｎ）からｄ（Ｓｉ，Ｓｎ）＜ｋかつｄ（Ｄｉ，Ｄｎ）＜ｋ、もしくはｄ（Ｓｉ，Ｄｎ）＜ｋかつｄ（Ｄｉ，Ｓｎ）＜ｋであったとする。
【００５４】
ステップ５１：ＯＴＮが存在するノードを把握するためＯＴＮノードリスト（Ｏｉ：ｉ＝１〜ｎ、ｎはＯＴＮノード数）を作成する。最初は、少なくとも全需要の始点ノードと終点ノードがＯＴＮノードリストに含まれる。
ステップ５２：集約する需要ｎｉの始点Ｓｉから、ｋ’を一定の閾値として、ｄ（Ｓｉ、Ｏｊ）＜ｋ’を満たすＯＴＮノードＯｊが存在するか確認する。存在する場合、ステップ５３に進む、存在しない場合、ステップ５４に進む。
ステップ５３：前記ＯＴＮノードＯｊに需要ｎｉの始点を集約する。
ステップ５４：もっとも近傍の通過ノードをＯＴＮノードに変換して、該ノードをＯＴＮノードリストに含める。
ステップ５５：集約する需要ｎｉの終点Ｄｉから、ｋ’を一定の閾値として、ｄ（Ｄｉ、Ｏｊ）＜ｋ’を満たすＯＴＮノードＯｊが存在するか確認する。存在する場合、ステップ５６に進む、存在しない場合、ステップ５７に進む。
ステップ５６：前記ＯＴＮノードＯｊに需要ｎｉの終点を集約する。
ステップ５７：もっとも近傍の通過ノードをＯＴＮノードに変換して、該ノードをＯＴＮノードリストに含める。
【００５５】
図１８は、ＯＴＮノード数の増加を抑える方法の実施例を示す。需要ｎｉのＳｉがｄ（Ｓｉ，Ｓｎ）＜ｋであったとする。始点Ｓｉにおいて、ｄ（Ｓｉ、Ｏｊ）＜ｋ’を満たすＯＴＮノードＯｊが存在する。このため、ＳｉはＳｎではなくＯｊに収容する。
【００５６】
また、上記の実施形態のステップ６、７で需要パスを集約した後、パス集約後の総和の帯域が、１インタフェースが有する帯域以上になった場合、同一ルートにおいて、別波長を割り当てていた。しかしながら、上記とは関連の無い異なる波長においては、集約後の帯域の総和が１インタフェースが有する帯域以下であり、他の需要を集約できる可能性があるものも存在する。
【００５７】
このため、集約予定としていた全需要の中で、遅延制約の緩い需要（ステップ１でｘｉ≦αであった需要）の数量を把握し、これらすべてを別波長に割り当てた場合、１波長当たりの帯域の総和が１インタフェースが有する帯域未満となるか否かについて確認する。１インタフェースの帯域未満となるようであれば、その中で遅延制約の厳しいものから順に当該需要の始点／終点から所定の距離Ｐ以内に通過ノードが存在する波長へ集約される。
【００５８】
図１９は、波長数を低減する方法のフローチャートを示す。本方法は、ステップ６、７が行われ、全需要が集約した後に全ての需要パスに対して行われる。
ステップ７１：集約を予定していた需要の帯域の総和が１インタフェースが有する帯域を上回るか否かについて確認する。当該帯域未満である場合、波長再割り当ての必要がないため終了する。
ステップ７２：集約を予定していた需要の中で、遅延制約の緩い需要のみを異波長に割り当てた場合、残りの需要の帯域の総和が、１インタフェースが有する帯域を下回るか否かについて確認する。下回る場合、他の波長への再割り当てが不可能であるため終了する。
ステップ７３：上記ステップの遅延制約の緩い需要を、遅延制約の厳しい順に番号（昇順）を付与する。
ステップ７４：上記ステップで割り振った番号の小さい方（つまり、遅延制約の厳しい需要パス）から順に当該需要の始点および終点から所定の半径Ｐ以内に同一既存波長の通過ノードが存在するか確認する。１つも存在しない場合、他の波長への再割り当てが不可能であるため終了する。
ステップ７５：上記ステップで確認した需要を前記通過ノードの需要パスに収容した場合、許容遅延時間を満足できるか否かを確認する（複数波長に該当する場合は全てチェックし、空き帯域の多い波長に収容）。許容遅延時間を満足できるルートがない１つもない場合は、他の波長への再割り当てが不可能であるため終了する。
ステップ７６：上記ステップで確認した需要を割り振った番号の小さい方から、全需要の帯域の総和が１インタフェースが有する帯域未満になるまで取り除き、波長の再割り当てが完了し、終了する。
【００５９】
図２０は、波長数を低減する方法の実施例を示す。ステップ６、７では需要ｄ（Ｓｎ，Ｄｎ）は、需要パスλ１に集約される。しかし、需要ｄを集約した場合、１波長当たりの帯域の総和が１インタフェースの帯域以上になる。需要ｄが遅延制約の緩い需要であり、需要ｄの始点および終点から所定の半径Ｐ以内に同一既存波長λｎの通過ノードが存在する。さらに、λｎに収容した場合、需要ｄの許容遅延時間を満足できる場合、需要ｄをλｎに収容することにより、需要パスλ１を波長数を低減することが可能になる。
【００６０】
本発明によるトランスポート回線設計方法は、コンピュータを、上述した各ステップを機能させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。さらに、本発明は、ハードウェア及びソフトウェアの組合せによっても実現可能である。
【００６１】
また、以上述べた実施形態は全て本発明を例示的に示すものであって限定的に示すものではなく、本発明は他の種々の変形態様および変更態様で実施することができる。従って本発明の範囲は特許請求の範囲およびその均等範囲によってのみ規定されるものである。
【特許請求の範囲】
【請求項１】
許容遅延時間を有する需要に対する回線設計方法において、
全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する第１のステップと、
前記遅延制約量が一定値以下である需要を、前記第１のステップで設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する第２のステップと、
ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記第２のステップで集約できなかった需要を集約する第３のステップと、
を有することを特徴とする回線設計方法。
【請求項２】
前記第１のステップは、
全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要をリスト１に登録する第１のサブステップと、
前記リスト１に登録された需要の中から、最も遅延制約が厳しい需要を求め、該需要について、最短パスを設定する第２のサブステップと、
前記リスト１に登録された需要の中で、前記設定されたパスの通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、前記設定された遅延制約の最も厳しいパスパスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、前記設定された遅延制約の最も厳しいパスパスに集約する第３のサブステップと、
前記第３のサブステップで集約されなかった前記リスト１に登録された需要を新たにリスト１として、前記第２のサブステップと前記第３のサブステップを集約関係が発生しなくなるまで繰り返す第４のサブステップと、
を有し、
前記第２のステップは、
前記遅延制約量が一定値以下である需要の中で、前記第１のステップで設定されたパスの始終点を含む通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、該パスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約し、集約できない需要をリスト２に登録する第５のサブステップであり、
前記第３のステップは、
前記リスト２に登録された需要の始点ノードと終点ノード間を結ぶ線を可能な限り多く通過するようにネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否かを確認し、満たす場合は、該パスに集約する第６のサブステップと、
前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を１本引き、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、
前記第７のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を引き直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップと、
を有することを特徴とする請求項１に記載の回線設計方法。
【請求項３】
前記第５のサブステップは、該需要の始点または終点から一定距離以内にＯＴＮノードが存在し、該ＯＴＮノードに該需要の始点または終点を収容した場合、許容遅延時間を満たすか否か確認し、満たす場合は、該需要の始点または終点を該ＯＴＮノードに集約することをさらに備えることを特徴とする請求項２に記載の回線設計方法。
【請求項４】
前記第７のサブステップと前記第８のサブステップで、それぞれの新しい区画でノード数が可能な限り均等になるように分割することを特徴とする請求項２に記載の回線設計方法。
【請求項５】
前記第３のステップの別の方式としては、
前記リスト２に登録された需要のなかで、始点ノードと終点ノード間の距離が最長となる需要を抽出し、当該需要の始点ノードを集合Ａ、終点ノードを集合Ｂに含め、他の需要は、当該需要の始点ノードからより距離の近い端点（始点ノードまたは終点ノード）を集合Ａ、他方をＢに属するように、ネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否かを確認し、満たす場合は、該パスに集約する第６のサブステップと、
前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの集合Ａ、Ｂを、同一集合に属する始点ノードの終点ノード、および終点ノードの始点ノードが、別の同一集合に属する条件を満たすように、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、
前記第７のサブステップまでに全ての需要が集約できない場合または前記条件を満たすように分割できない場合、前記第６のサブステップの条件を満たす区画に分割し直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップと、
であることを特徴とする請求項２に記載の回線設計方法。
【請求項６】
前記遅延制約量は、始点ノードと終点ノード間の直線距離を許容遅延時間で割った値であることを特徴とする請求項２から５のいずれか１項に記載の回線設計方法。
【請求項７】
前記最短パスは、遅延時間をパスコストとして、ダイクストラ法で決定されることを特徴とする請求項２から６のいずれか１項に記載の回線設計方法。
【請求項８】
前記起点となるノードは、前記区画の中にあり、前記リスト２に登録された需要の始点ノードと終点ノードからの直線距離の総和が最小となる、もしくはホップ数の総和が最小となるノードであることを特徴とする請求項２から７のいずれか１項に記載の回線設計方法。
【請求項９】
前記第７のサブステップと前記第８のサブステップで、集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数となった場合、集約できなかったパスについては単独に波長を割り当てることを特徴とする請求項２から８のいずれか１項に記載の回線設計方法。
【請求項１０】
前記第３のステップ終了後、パス集約後の総和の帯域が、１インタフェースが有する帯域以上になった場合、
集約予定としていた全需要の中で、前記遅延制約量が一定値以下である需要の中から、該需要の始点および終点から一定距離以内に同一既存波長の通過ノードが存在し、該通過ノードのパスに収容した場合、許容遅延時間を満たす需要を、該通過ノードの波長に収容することで、パス集約後の総和の帯域を１インタフェースの帯域未満にすることを特徴とする請求項１から８のいずれか１項に記載の回線設計方法。
【請求項１１】
前記収容は、前記遅延制約量が一定値以下である需要の中で遅延制約量が大きい需要から順に、パス集約後の総和の帯域を１インタフェースの帯域未満になるまで、行うことを特徴とする請求項１０に記載の回線設計方法。
【請求項１２】
許容遅延時間を有する需要に対する回線を設計するためのコンピュータを、
全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する手段と、
前記遅延制約量が一定値以下である需要を、前記手段で設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する手段と、
ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記手段で集約できなかった需要を集約する手段と、
して機能させ、回線を設計することを特徴とするプログラム。
【請求項１】
許容遅延時間を有する需要に対する回線設計方法において、
全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する第１のステップと、
前記遅延制約量が一定値以下である需要を、前記第１のステップで設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する第２のステップと、
ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記第２のステップで集約できなかった需要を集約する第３のステップと、
を有することを特徴とする回線設計方法。
【請求項２】
前記第１のステップは、
全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要をリスト１に登録する第１のサブステップと、
前記リスト１に登録された需要の中から、最も遅延制約が厳しい需要を求め、該需要について、最短パスを設定する第２のサブステップと、
前記リスト１に登録された需要の中で、前記設定されたパスの通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、前記設定された遅延制約の最も厳しいパスパスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、前記設定された遅延制約の最も厳しいパスパスに集約する第３のサブステップと、
前記第３のサブステップで集約されなかった前記リスト１に登録された需要を新たにリスト１として、前記第２のサブステップと前記第３のサブステップを集約関係が発生しなくなるまで繰り返す第４のサブステップと、
を有し、
前記第２のステップは、
前記遅延制約量が一定値以下である需要の中で、前記第１のステップで設定されたパスの始終点を含む通過ノードから一定距離以内に始点ノードと終点ノードが存在する需要について、該パスに集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約し、集約できない需要をリスト２に登録する第５のサブステップであり、
前記第３のステップは、
前記リスト２に登録された需要の始点ノードと終点ノード間を結ぶ線を可能な限り多く通過するようにネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否かを確認し、満たす場合は、該パスに集約する第６のサブステップと、
前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を１本引き、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、
前記第７のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの線と交差する分割線を引き直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップと、
を有することを特徴とする請求項１に記載の回線設計方法。
【請求項３】
前記第５のサブステップは、該需要の始点または終点から一定距離以内にＯＴＮノードが存在し、該ＯＴＮノードに該需要の始点または終点を収容した場合、許容遅延時間を満たすか否か確認し、満たす場合は、該需要の始点または終点を該ＯＴＮノードに集約することをさらに備えることを特徴とする請求項２に記載の回線設計方法。
【請求項４】
前記第７のサブステップと前記第８のサブステップで、それぞれの新しい区画でノード数が可能な限り均等になるように分割することを特徴とする請求項２に記載の回線設計方法。
【請求項５】
前記第３のステップの別の方式としては、
前記リスト２に登録された需要のなかで、始点ノードと終点ノード間の距離が最長となる需要を抽出し、当該需要の始点ノードを集合Ａ、終点ノードを集合Ｂに含め、他の需要は、当該需要の始点ノードからより距離の近い端点（始点ノードまたは終点ノード）を集合Ａ、他方をＢに属するように、ネットワークを分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否かを確認し、満たす場合は、該パスに集約する第６のサブステップと、
前記第６のサブステップまでに全ての需要が集約できない場合、前記第６のサブステップの集合Ａ、Ｂを、同一集合に属する始点ノードの終点ノード、および終点ノードの始点ノードが、別の同一集合に属する条件を満たすように、ネットワークを４分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに需要を集約し、同一波長を用いた場合、許容遅延時間を満たすか否か確認し、満たす場合は、該パスに集約する第７のサブステップと、
前記第７のサブステップまでに全ての需要が集約できない場合または前記条件を満たすように分割できない場合、前記第６のサブステップの条件を満たす区画に分割し直し、６分割、８分割と分割数を増やしながら、前記第７のサブステップの処理を繰り返す第８のサブステップと、
であることを特徴とする請求項２に記載の回線設計方法。
【請求項６】
前記遅延制約量は、始点ノードと終点ノード間の直線距離を許容遅延時間で割った値であることを特徴とする請求項２から５のいずれか１項に記載の回線設計方法。
【請求項７】
前記最短パスは、遅延時間をパスコストとして、ダイクストラ法で決定されることを特徴とする請求項２から６のいずれか１項に記載の回線設計方法。
【請求項８】
前記起点となるノードは、前記区画の中にあり、前記リスト２に登録された需要の始点ノードと終点ノードからの直線距離の総和が最小となる、もしくはホップ数の総和が最小となるノードであることを特徴とする請求項２から７のいずれか１項に記載の回線設計方法。
【請求項９】
前記第７のサブステップと前記第８のサブステップで、集約後の波長数＋集約できなかった波長数＜全てのパスを集約した場合の波長数となった場合、集約できなかったパスについては単独に波長を割り当てることを特徴とする請求項２から８のいずれか１項に記載の回線設計方法。
【請求項１０】
前記第３のステップ終了後、パス集約後の総和の帯域が、１インタフェースが有する帯域以上になった場合、
集約予定としていた全需要の中で、前記遅延制約量が一定値以下である需要の中から、該需要の始点および終点から一定距離以内に同一既存波長の通過ノードが存在し、該通過ノードのパスに収容した場合、許容遅延時間を満たす需要を、該通過ノードの波長に収容することで、パス集約後の総和の帯域を１インタフェースの帯域未満にすることを特徴とする請求項１から８のいずれか１項に記載の回線設計方法。
【請求項１１】
前記収容は、前記遅延制約量が一定値以下である需要の中で遅延制約量が大きい需要から順に、パス集約後の総和の帯域を１インタフェースの帯域未満になるまで、行うことを特徴とする請求項１０に記載の回線設計方法。
【請求項１２】
許容遅延時間を有する需要に対する回線を設計するためのコンピュータを、
全ての需要に対して、始点ノードと終点ノード間の距離および許容遅延時間から遅延制約量を求め、該遅延制約量が一定値を超える需要に対してパスを設定する手段と、
前記遅延制約量が一定値以下である需要を、前記手段で設定されたパスに集約し、同一波長を用いた時、許容遅延時間を満たす場合、該パスに集約する手段と、
ネットワークを複数の区画に分割し、分割した各区画に起点となるノードを決定し、該起点ノード間にパスを設定し、該パスに前記手段で集約できなかった需要を集約する手段と、
して機能させ、回線を設計することを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１３−２１６７８（Ｐ２０１３−２１６７８Ａ）
【公開日】平成２５年１月３１日（２０１３．１．３１）
【国際特許分類】
【出願番号】特願２０１２−１１２３５６（Ｐ２０１２−１１２３５６）
【出願日】平成２４年５月１６日（２０１２．５．１６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２５年１月３１日（２０１３．１．３１）
【国際特許分類】
【出願日】平成２４年５月１６日（２０１２．５．１６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]