(57)【要約】【課題】  データ転送の需要に対応するために設備を増設する際、通過するパスによっては設備の新設に要する費用が必要以上に増大するという問題があった。【解決手段】  データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計方法であって、複数の需要のそれぞれに対して、送信元のノードと宛先のノードとを結ぶパスを選択し、パスを実現するために必要となる設備の新設に要する設備新設コストをそれぞれのノードについて算出し、それぞれのノードについての設備新設コストに応じて、上述のパスの少なくともいずれかに含まれる区間であって、そのパスより設備新設コストが低い他のパスによって置き換える対象となる区間を抽出し、複数の需要のうち、他のパスを用いても要求品質を満足する需要について、抽出された区間のパスをそのパスに置き換える。【選択図】  図６
2013238989.tif 000002
【特許請求の範囲】
【請求項１】
データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計方法であって、
選択手段が、前記複数の需要のそれぞれに対して、送信元のノードと宛先のノードとを結ぶパスを選択する選択工程と、
算出手段が、前記複数の需要に対する前記パスを実現するために必要となる設備の新設に要する設備新設コストをそれぞれのノードについて算出する算出工程と、
抽出手段が、それぞれのノードについての前記設備新設コストに応じて、前記パスの少なくともいずれかに含まれる区間であって、前記パスより設備新設コストが低い他のパスによって置き換える対象となる区間を抽出する抽出工程と、
置換手段が、前記複数の需要のうち、前記他のパスを用いても要求品質を満足する需要について、抽出された前記区間の前記パスを当該他のパスに置き換える置換工程と、
出力手段が、置換後のパスにおける設備を新設すべきノードと置換後のパスを実現するために必要となる設備の新設に要する設備新設コストの総和とを出力する出力工程と、
を有することを特徴とするネットワーク設計方法。
【請求項２】
前記選択工程では、前記複数の需要のそれぞれについて、遅延時間が最短となるパスと遅延時間が所定値より小さいパスのうち１つとのいずれかを選択する、
ことを特徴とする請求項１に記載のネットワーク設計方法。
【請求項３】
判定手段が、前記他のパスを用いても要求品質を満足する需要の数が所定数以上であるかを判定する判定工程をさらに有し、
前記置換工程では、前記他のパスを用いても要求品質を満足する需要の数が所定数以上である場合、または前記区間を含むパスが選択されている需要のうち前記他のパスを用いても要求品質を満足する需要の割合が所定値以上である場合に、当該要求品質を満足する需要について、抽出された前記区間の前記パスを前記他のパスに置き換える、
ことを特徴とする請求項１又は２に記載のネットワーク設計方法。
【請求項４】
前記抽出工程では、２つ以上のリンクを含む区間であって、当該区間に含まれるノードにおける設備新設コストの和、または当該区間に含まれるリンクの数あたりの当該設備新設コストの和が、所定値を超える区間を抽出する、
ことを特徴とする請求項１から３のいずれか１項に記載のネットワーク設計方法。
【請求項５】
前記算出工程では、それぞれのノードにおいて使用されていない設備の量と、当該ノードを通過するパスに対応する需要の量とに応じて、前記設備新設コストを算出する、
ことを特徴とする請求項１から４のいずれか１項に記載のネットワーク設計方法。
【請求項６】
更新手段が、前記パスを前記他のパスにより置き換えた場合の前記設備新設コストを更新する更新工程と、
比較手段が、前記パスを前記他のパスにより置き換えることによる前記設備新設コストの低減率を、所定の閾値と比較する比較工程と、をさらに有し、
所定回数連続して前記低減率が前記所定の閾値以下となるまで、少なくとも前記抽出工程、前記置換工程、前記更新工程および前記比較工程を繰り返し、所定回数連続して前記低減率が前記所定の閾値以下となった場合に、前記出力工程において、置換後のパスにおける設備を新設すべきノードを出力する、
ことを特徴とする請求項１から５のいずれか１項に記載のネットワーク設計方法。
【請求項７】
前記出力工程は、前記所定の閾値を変数として、複数の前記所定の閾値について得られた前記設備新設コストの総和のうち、最小の総和を与える前記所定の閾値についての、当該総和と設備を新設すべきノードとを出力する、
ことを特徴とする請求項６に記載のネットワーク設計方法。
【請求項８】
データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計装置であって、
前記複数の需要のそれぞれに対して、送信元のノードと宛先のノードとを結ぶパスを選択する選択手段と、
前記複数の需要に対する前記パスを実現するために必要となる設備の新設に要する設備新設コストをそれぞれのノードについて算出する算出手段と、
それぞれのノードについての前記設備新設コストに応じて、前記パスの少なくともいずれかに含まれる区間であって、前記パスより設備新設コストが低い他のパスによって置き換える対象となる区間を抽出する抽出手段と、
前記複数の需要のうち、前記他のパスを用いても要求品質を満足する需要について、抽出された前記区間の前記パスを当該他のパスに置き換える置換手段と、
置換後のパスにおける設備を新設すべきノードと置換後のパスを実現するために必要となる設備の新設に要する設備新設コストの総和とを出力する出力手段と、
を有することを特徴とするネットワーク設計装置。
【請求項９】
請求項１から７のいずれか１項に記載のネットワーク設計方法における各工程をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、需要に応じてネットワークの設備を増設する際に、コストの低減を図る技術に関する。
【背景技術】
【０００２】
近年、ネットワーク上を流れるデータの量が増加しており、ネットワークはこのデータ量の増加に対応することを要求されている。データ量の増加に対しては、ネットワーク設備の新設により対応することが可能である。すなわち、データ転送の需要に対して、そのデータが発生するノードから、そのデータの宛先のノードまでのパスを確保するために、そのパスが通過するネットワーク内の中継ノードにおける設備を増強することにより、データの増大に対応することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、ネットワーク内のノードには、例えば、空きポートを有するがケーブルが接続されていないもの、ケーブルが挿入されている空きポートを有するもの、そして、空きポートを有さないものが存在する。このため、通過するパスによっては、設備の新設に要する費用が必要以上に増大するという問題があった。
【０００４】
本発明は上記課題に鑑みなされたものであり、データ転送の需要を処理するために必要な設備を最低限のコストで増設するためのネットワーク設計技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するため、本発明によるネットワーク設計方法は、データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計方法であって、選択手段が、前記複数の需要のそれぞれに対して、送信元のノードと宛先のノードとを結ぶパスを選択する選択工程と、算出手段が、前記複数の需要に対する前記パスを実現するために必要となる設備の新設に要する設備新設コストをそれぞれのノードについて算出する算出工程と、抽出手段が、それぞれのノードについての前記設備新設コストに応じて、前記パスの区間であって、前記パスより設備新設コストが低い他のパスによって置き換える対象となる区間を抽出する抽出工程と、置換手段が、前記他のパスを用いても要求品質を満足する需要について、抽出された前記区間の前記パスを当該他のパスに置き換える置換工程と、出力手段が、置換後のパスにおける設備を新設すべきノードと置換後のパスを実現するために必要となる設備の新設に要する設備新設コストの総和とを出力する出力工程と、を有する。
【発明の効果】
【０００６】
本発明によれば、最低限のコストで設備を増設すべきネットワークノードを特定することができる。
【図面の簡単な説明】
【０００７】
【図１】ネットワーク設計装置のハードウェア構成例を示す図。
【図２】増設すべき設備とそのコストを算出する処理を示すフローチャート。
【図３】初期パスの設定処理を示すフローチャート。
【図４】複数のノードを含むネットワークの構成例。
【図５】初期パスの選択例を示す図。
【図６】ある閾値ｘに対するパスの置き換え処理を示すフローチャート。
【図７】初期パス設定後のネットワークの一区間の状態の例を示す図。
【図８】代替パスの選択例を示す図。
【図９】設備量と設備新設コストの更新の例を示す図。
【発明を実施するための形態】
【０００８】
以下、添付図面を参照して本発明の実施の形態を詳細に説明する。
【０００９】
本実施形態に係るネットワーク設計装置は、まず、データ転送の各需要に対して、新規設備を増設するのに要する設備新設コストについて考慮せずに、遅延時間が最小のパスまたは遅延時間が所定値より小さいパスのうち１つを仮に選択する。そして、その選択したパスの実現に要する設備新設コストを算出する。その後、例えば、遅延時間などの予め定められた通信品質を満足すると共に設備新設コストが低い他のパスにより、選択されたパスの一部区間を置き換え、ネットワーク全体としての設備新設コストを削減する。これにより、より低い設備増設コストで、予め定められた通信品質を満足するパスを各需要に対して構築することが可能となる。また、データ転送の各需要に対して、遅延時間が最初に十分に小さいパスを最初に選択することにより、各需要に対して遅延の要求を満足させながら代替可能な他のパスを発見できる確率を高めることが可能となる。そして、この結果を用いて、最低限のコストで効果的に設備の増強を行うことが可能となる。
【００１０】
（ネットワーク設計装置の構成）
以下、具体的に本実施形態に係るネットワーク設計装置について説明する。なお、本ネットワーク設計装置は、例えば、図１に示すような、ＣＰＵ１０１、ＲＯＭ１０２、ＲＡＭ１０３、外部記憶装置１０４を備えるコンピュータ１００により実現される。コンピュータ１００においては、ＲＯＭ１０２に記録された本方法に係るプログラムをＣＰＵ１０１により実行する。そして、例えば、各需要に対応する初期パスや各ノードにおける余剰設備量などの中間生成物をＲＡＭ１０３に記憶させ、最終的な結果を外部記憶装置１０４へ格納する。なお、ネットワーク設計装置は、以下に説明する各機能を実行する専用のハードウェアを備えてもよいし、一部をハードウェアで実行し、その他の部分をコンピュータ１００により実行させてもよい。
【００１１】
（ネットワーク設計装置の処理）
本実施形態に係るネットワーク設計装置の動作について、図２を用いて説明する。ネットワーク設計装置は、処理を開始すると、まず初期化処理を行う（Ｓ２０１）。具体的には、パラメータｉを０に設定する。パラメータｉは、後述の閾値候補ｘiの中から処理に用いるものを特定するためのインデックスである。なお、閾値候補ｘiは、ｉmax個存在するものとする。
【００１２】
続いて、データ転送の各需要に対して初期パスの選択と、その初期パスの構築に要求される新設設備と設備新設コスト（Ｃmax）の決定とを実行し、その結果を記録する（Ｓ２０２）。ここで記録された初期パス、新設設備及びコストは後述する各処理において使用されるため、例えば、処理が完了するまでＲＡＭ１０３に保持される。Ｓ２０２の動作の詳細については、図３を参照して後述する。
【００１３】
その後、後述するＳ２０４の処理で使用する閾値ｘをｉ番目の閾値候補であるｘiに設定する（Ｓ２０３）。そして、閾値ｘの場合について、Ｓ２０２で設定された初期パスからのパスの置換の試行、置換後に設備の新設が要求されるノードの決定と記録、及び要求されるコスト（Ｃi）の決定と記録が実行される（Ｓ２０４）。Ｓ２０４の動作の詳細については、図６を参照して後述する。
【００１４】
そして、ｉを１だけ増加させ（Ｓ２０５）、全ての閾値候補ｘiについての処理が完了したかを判定する（Ｓ２０６）。全ての閾値候補ｘiについての処理が完了した場合（Ｓ２０６でＹｅｓ）、最小の設備新設コストＣiを与える閾値ｘiを特定する。そして、その閾値ｘiに対応してＳ２０４で決定された設備の新設が要求されるノードを出力する（Ｓ２０７）。一方、全ての閾値候補ｘiについての処理が完了していない場合（Ｓ２０６でＮｏ）、処理をＳ２０３へ戻し、次の閾値候補を用いて、Ｓ２０４の処理を行う。このようにして設備の増設対象となるノードを特定することにより、最低限のコストでデータ転送の需要を処理するとともに、各需要に対する要求品質を満足させることが可能となる。
【００１５】
（初期パスの設定処理）
上述のＳ２０２における初期パス設定等の処理について、図３を用いて説明する。処理においては、まず、複数のデータ転送の需要に対して、どの需要からパスの検索及び選択を実行するかを決定する（Ｓ３０１）。すなわち、複数の需要の送信元のノードと宛先のノードとの間を結ぶパスを検索する際に、どの送信元と宛先のノードの組み合わせからパスの検索を行うかを決定する。例えば、遅延制約の厳しい需要から順に、パスの検索を実行するように順序を決定する。続いて、実際の処理の開始に先立って、パラメータの初期化を行う（Ｓ３０２）。例えば、まず、検索すべき全パス数、すなわちデータ転送の需要の数をＮmaxに設定し、パス検索対象の需要を指定するパラメータＮを０に設定する。
【００１６】
そして、Ｎ＋１番目の需要に対する初期パスを選択して記憶する（Ｓ３０３）。ここで、初期パスは、例えば、ある需要の送信元ノードと宛先ノードを結ぶパスであって、伝送遅延が最小となるものが選択される。また、遅延時間が最小でなくとも、遅延時間が所定値より小さいパスのうち１つを初期パスとしてもよい。なお、遅延時間が最小または所定値より小さいパスを初期パスとして選択することにより、図２のＳ２０４の処理における置き換えパスの探索を容易にすることが可能となる。すなわち、遅延時間が最小または所定値より小さいパスを初期パスとすると、そのパスについて一部のパスを置き換えても遅延時間の制約を満足できる確率が高い。したがって、そのような初期パスを基準として、一部の区間をコストの低いパスに置き換えることで、低コストかつ低遅延なパスを発見することができる確率を高めることができる。
【００１７】
その後、Ｓ３０３で選択された初期パスに応じて、ノード毎の設備増設コストを計算して記録する（Ｓ３０４）。ここで、例えば、あるノードにおいて１００個の新規設備が必要である場合、その１００個の新規設備を構築するのに最も費用が少なくなるように増設すべき設備を決定して、設備増設コストを計算する。より具体的には、ノードには、空きポートが存在しそこにケーブルが接続されているものと、そのいずれかがないもの、又は双方ともにないものが存在しうる。ここで、ノードにケーブルが接続された空きポートが１００個存在すれば、コストはかからないため、そのケーブルが接続された空きポートを利用するようにする。これに対し、例えば、ケーブルが接続された空きポートが５０個しかない場合、残りの５０個の設備については、空きポートの増設とケーブルの接続の少なくともいずれかを行うことにより賄う。このとき、空きポートを増設してケーブルを接続する場合が最もコストがかかる。このため、例えば、ケーブルが接続されていない空きポートが存在する場合は可能な限りそれを用い、それでも賄いきれない場合に空きポートの増設とケーブルの接続の両方を伴うパッケージの増設を行うようにする。そして、これらを実行するために要する費用が設備増設コストとなる。
【００１８】
ここで、図４及び図５を用いて、初期パスの選択とコストの算出について説明する。図４は、送信元ノード４０１と宛先ノード４０２とを含むネットワークの構成例を示す図である。図４の例は、送信元ノード４０１と宛先ノード４０２との間に４つのノード４０３〜４０６が存在し、それぞれのノードが図の点線で示されるリンクで接続される例を示している。また、各ノードの丸の中に示す数字は、新たに単位量のデータ転送を行うリンクを形成するために要するコストを示し、数字が０のノードは余剰設備が存在するためコストを要さないことを示す。各リンクに付された数字は遅延時間であり数が大きいほど遅延時間が大きいことを示す。例えば、ノード４０１からノード４０５へは、必要な遅延時間は３であるが、コストは要さずに１単位量の需要を転送することが可能である。一方、ノード４０１からノード４０３へは、必要な遅延時間が１となるが、１単位量の需要を転送するのにコストは３だけかかる。
【００１９】
初期パスの選択においては、コストを度外視して、遅延時間が最小のパスまたは遅延時間が所定値より小さいパスのうち１つを初期パスとして抽出する。ここでは遅延時間が最少のパスを選択すると、図５に矢印として示すノード４０３とノード４０６とを通過するパスが、送信元ノード４０１から宛先ノード４０２までの最小の遅延時間「３」を与えるパスとなる。したがって、このパスを初期パスとして選択する。Ｓ３０３とＳ３０４において、選択された初期パスと、ノード４０３及びノード４０６でそれぞれ設備新設コスト「３」を要することを記録する。なお、設備新設コストは累積され、例えば、複数の初期パスがノード４０３を含む場合は、その初期パスの設定にそれぞれ要する設備新設コストを累積した値が、ノード４０３における設備新設コストとして記録される。また、１つの需要で転送すべきデータ量が多く、複数のケーブルが必要となる場合などは、その分コストが増加する。
【００２０】
なお、「パッケージの増設」や「ケーブルの接続」など、複数種類の設備の増設の仕方が存在する場合は、それぞれの方法が何回選択されたかを記憶させてもよい。また、上述の通り、コストの低い設備の増設方法がコストの高い設備の増設方法より優先して選択される。すなわち、例えば、ケーブルが接続されていないポートをあるノードが有する場合は、パスがそのノードを含んで選択されるごとに、まずケーブル接続による設備の増設が選択される。そして、ケーブルが接続されていない全てのポートがいずれかのパスに割り当てられると、その後はパッケージの増設による設備の増設が選択される。
【００２１】
また、初期パスの選択においては、それまでに存在しない経路を新設することを考えてもよい。例えば、図４においては、ノード４０３からノード４０２への経路は、ノード４０４又はノード４０６を経由するが、ノード４０３からノード４０２へ直接接続されるリンクを仮定してもよい。例えば、ノード４０３からノード４０２へ直接リンクすることにより遅延時間を最短とすることができる場合は、そのリンクを新規に開通させることを仮定して初期パスを選択してもよい。
【００２２】
初期パスの選択と記録（Ｓ３０３）及び設備増設コストの計算と記録（Ｓ３０４）が終了すると、続いて、ノード毎の設備量を更新する。すなわち、例えば初期パスによりケーブルが接続されたポートが使用されることなどを仮定して、各ノードにおける空き設備の残量を更新する（Ｓ３０５）。これにより、一定量の初期パスにより空き設備が消費された後には、設備新設コストが要求されるようになる。
【００２３】
例えば、図５において、ノード４０１とノード４０２は、それぞれノード４０３及びノード４０６との間で新たなデータ転送を行うことが仮定される。このため、ノード４０１とノード４０２においては、現時点で存在する余剰設備のうち、単位量のデータ転送を行う新たなリンクを形成するのに要する設備を消費したことを仮定して設備量を更新する。また、例えば、ノード４０３とノード４０６において、ケーブルが接続されていないポートを有していた場合に、新たなリンクの確立によってそれが消費される場合は、それに応じて設備量を更新する。なお、ケーブルが接続されていないポートが消費しつくされると、新たなリンクの確立のためにパッケージの増設が必要となる。なお、パッケージの増設に必要な設備新設コストは、一般に、ケーブルが接続されていない空きポートを用いるよりも高くなる。また、例えばノード４０３とノード４０２とを直接接続する新たなリンクを仮定する場合は、そのリンクの端点であるノード４０３とノード４０２とに対して、リンク新設のためのコストを加えるようにする。
【００２４】
そして、パス検索対象の需要を指定するパラメータＮを１だけ増加させ（Ｓ３０６）、全ての需要に対してパス検索が完了したかを判定する（Ｓ３０７）。すべての需要に対してパス検索が完了していない場合（Ｓ３０７でＮｏ）は、処理をＳ３０３へ戻し、更新した各ノードの設備量を用いて、初期パスの選択から再度処理を開始する。一方、全ての需要に対してパス検索が完了した場合（Ｓ３０７でＹｅｓ）は処理を終了する。この時点で、各需要に対する初期パスと、そのパスを新規に確立するために必要となる各ノードにおける新設設備コストとが記録されることとなる。
【００２５】
（パスの置き換え処理）
上述のＳ２０４におけるパスの置き換え等の処理について、図６を用いて説明する。処理が開始されると、まず、タブーリストを空集合φとするとともに、カウント値ｃｎｔを０として、初期化を実行する（Ｓ６０１）。タブーリストは、例えば、ある区間に対して代替パスでの置換を試行した結果として通信品質などを満足できなかった場合に、その区間と代替パスとを記憶しておくリストである。ある区間とその代替パスがタブーリストに含まれる場合、その区間を当該代替パスで代替しても通信品質を満足できないことが分かっているため、タブーリストに含まれる代替パスは、対応する区間の置換候補のパス（候補パス）とはしない。これにより、不要な試行を削減することができる。カウント値ｃｎｔは、後述するコストの低減率ｒが連続して閾値ｘ以下である場合にその連続した回数を示す変数であり、ｒがｘより大きいと判定されると０にクリアされる。
【００２６】
続いて、置換対象の区間を検索する（Ｓ６０２）。置換対象の区間は設備新設コストが大きい区間が選ばれる。例えば、それぞれが２つのノードを接続する２つ以上のリンクを含む区間における設備新設コストが基準値Ｔを超える場合に、その区間を置換対象の区間とする。なお、設備新設コストはリンク数で平均したリンクあたりの設備新設コストであってもよい。また、リンクあたりの設備新設コストが最も高い区間を１つだけ置換対象区間として抽出してもよく、また、リンクあたりの設備新設コストが高い方から所定数だけの区間を置換対象区間として抽出してもよい。
【００２７】
例えば、図７に示すようなノード７０１とノード７０５とを接続する区間が存在するとする。ここで、各ノードを示す円の中に記載された数字は、パスの割り当てにより生じる、各ノードにおける設備新設コストである。また、各ノードの円の上に示される数字はパスの割り当て前の余剰設備量であり、円の下に示される数字はパスの割り当て後の余剰設備量である。また、各リンク（点線）に付された数字は、当該リンクの遅延量である。この例では、１００単位のデータがノード７０１とノード７０５との間を転送され、それらの転送のために、遅延時間が最小となる区間としてノード７０４を通過するパスが割り当てられているものとする。また、簡単のため、以下においては、新設する設備の種類、例えばケーブルの接続だけであるか、パッケージの増設が必要であるかは考慮せず、１単位のデータ転送のために設備を新設する場合、コストを１だけ要するものとする。
【００２８】
この場合、ノード７０１、ノード７０４、ノード７０５の３つのノードを接続する２つの連続するリンクにおいて、必要となる設備新設コストは１１０である。すなわち、ノード７０５では設備新設コストは不要であるが、ノード７０１とノード７０４において、それぞれ設備新設コスト１０と１００とを必要とする。この場合、リンクあたりのコストは５５となる。ここで、基準値Ｔを３０とすると、ノード７０４を経るノード７０１からノード７０５への区間は置換対象の区間として抽出される。
【００２９】
続いて、抽出した置換対象区間に対して、候補パスを探索する（Ｓ６０３）。ここで、候補パスは、置換対象の区間の始点と終点のノードが共通で、異なるリンクを経て始点のノードから終点のノードに至るパスである。なお、候補パスは、置換対象の区間において置換前に設定されたパスと一部の区間で異なればよく、一部の区間では共通していてもよい。ただし、２つのノードを直接接続する１つのリンクを２つ以上のリンクで置き換えるパスは、候補パスとして含めない。これは、１つのリンクを２つ以上のリンクで置き換えても、その１つのリンクの端点のノードはデータ転送の処理を行う必要があり、結果として新設すべき設備の量を減らすことができず、コスト低減効果を得られないためである。また、置換前のパスにおける置換対象区間での遅延時間の総和をｔとした場合に、当該置換対象区間における遅延時間がｔ＋τより大きいパスは候補パスから除外してもよい。なお、τは所定値であり、例えば、置換対象区間に含まれるリンクの数に応じて増減してもよい。また、置換対象区間が複数存在する場合は、例えば、その複数の置換対象区間に対してそれぞれ候補パスを探索する。
【００３０】
ここで、図８を用いて候補パスの探索について説明する。ここでは、パスが図８のようにノードＡ→ノードＢ→ノードＤ→ノードＦ（以下では「Ａ→Ｂ→Ｄ→Ｆ」のように表す）からなる区間を含む場合で、ノードＡからノードＦまでの区間が置換対象区間として抽出された場合について説明する。ここで、上述のように、例えばノードＡからノードＢまでのリンクは、Ａ→Ｃ→Ｅ→Ｂなどのように置換することは可能であるが、このようにしてもノードＡとノードＢとの新設設備量には変化がないため、このようなパスは考慮しない。
【００３１】
したがって、始点であるノードＡと終点であるノードＦとが置換前のパスと共通する候補パスは、（１）Ａ→Ｃ→Ｅ→Ｆ、（２）Ａ→Ｂ→Ｅ→Ｆ、（３）Ａ→Ｃ→Ｄ→Ｆの３つとなる。この例では、（１）は、置換前のパスと共通するリンクは存在しないが、（２）ではＡ→Ｂのリンクが、（３）ではＤ→Ｆのリンクがそれぞれ置換前のパスと共通する。これらの候補パスのうち、（１）は、例えば、ノードＢ及びノードＤの設備新設コストが高く、ノードＣ及びノードＥに余剰設備がある場合にコスト削減を期待できる。同様に、（２）は、ノードＤにおける設備新設コストが高くノードＥに余剰設備がある場合、（３）は、ノードＢにおける設備新設コストが高くノードＣに余剰設備がある場合に、コスト削減を期待できる候補パスである。ここで、置換前の総遅延時間は３であるところ、上述の候補パス（１）（２）及び（３）の総遅延時間はそれぞれ４、６、５である。したがって、上述のτが２である場合、置換前の３にτ＝２を加えた５より大きい総遅延時間を有するパス（２）は候補パスから除外されてもよい。
【００３２】
候補パスの探索（Ｓ６０３）の後、それらの候補パスの中から実際に置換を仮定するパスを選択し、置換を実行する処理を行う。まず、変数Ｍmaxを候補パスの数とし、変数ｍを０として、初期化を実行する（Ｓ６０４）。そして、ｍ＋１番目にコスト削減量が大きい候補パスを、置換対象区間を置換するパスとして仮定する（Ｓ６０５）。なお、複数の置換対象区間が存在する場合は、それぞれの置換対象区間に対して探索された候補パスの全体の中でｍ＋１番目にコスト削減量が大きい候補パスを、実際に置換するパスとして仮定する。図７の例では、ノード７０１とノード７０５とをそれぞれ始点及び終点とする区間に関して、代替パス候補は、ノード７０２を経るパスとノード７０３を経るパスが存在する。このとき、ノード７０２には余剰設備量が９０だけ存在し、ノード７０３には余剰設備量が５０だけ存在する。この場合、余剰設備量が多いノード７０２を通過する候補パスの方が、コスト削減量が大きい。すなわち、ノード７０４を経るパスでは設備新設コストが１１０であるのに対し、ノード７０２とノード７０３をそれぞれ経るパスでは、それぞれ設備新設コストは２０、６０であり、コスト削減量はそれぞれ９０、５０となる。このため、図７の例では、まずノード７０２を経る候補パスが置換の対象として仮定される。
【００３３】
次に、置換の対象として仮定した候補パスにより、その区間を通る需要のそれぞれが要求品質を満足するかを確認し、要求品質を満足する需要の数が所定数以上であるかを判定する（Ｓ６０６）。なお、Ｓ６０６の判定では、例えば、置換対象区間を含むパスが選択されている需要のうち、候補パスを用いても要求品質を満足する需要の割合が所定値以上であるかを判定してもよい。すなわち、候補パスへの置換によっても通信品質を満足する需要の数を、置換対象区間を通過する需要の数で除算した結果が所定値以上であるかを判定してもよい。需要の数に基づいて判定を行うことにより、絶対的に多くの数の需要に対して選択されたパスに含まれる区間、すなわち、新設設備数を抑えた候補パスによって新設設備数が多い区間を置換することとなり、設備新設コストを効率的に低減することが可能となる。一方、割合を用いて判定を行うことにより、置換対象区間を含むパスが選択された需要の絶対数が少ない場合であっても、設備新設コストが高い区間については置換を実行することが可能となる。
【００３４】
なお、要求品質を満足するかの確認においては、需要ごとに、遅延の制約や通過可能エリアの制約、光信号品質の制約などの制約を満足できるかが確認され、それらの制約を満足できた場合に通信品質を満足すると判定される。例えば、図７の例において、ノード７０２を通過するパスに置換することでこの区間の遅延時間が２だけ増加するが、各需要の送信元ノードから宛先ノードまでに要する総遅延時間が、遅延時間の増加後にも制約条件を満たすかが確認される。
【００３５】
その結果、所定数以上の需要において要求品質を満足することができると判定されると（Ｓ６０６でＹｅｓ）、置換対象区間のパスを、仮定した候補パスに置換する（Ｓ６０７）。ただし、ここでは、置換対象区間を通過するパスに対応する需要のうち、Ｓ６０６の判定において制約を満足できるとされた需要のみに対して候補パスを適用する。すなわち、図７の例において、ノード７０２を通過するパスにより要求品質を満足する需要については、パスを、ノード７０２を通過するパスに置換するとともに、要求品質を満足しない需要についてはノード７０４を通過するパスから変更しない。
【００３６】
パスの置換の後、置換したことによる各ノードの設備量と設備新設コストを更新する（Ｓ６０８）。図９に、図７の例においてノード７０４を通過するパスからノード７０２を通過するパスに８０単位分の需要を置換した場合の、更新した設備量と設備新設コストの例を示す。図９の例では、ノード７０２の余剰設備量が８０減少して１０となる。しかしながら、まだ余剰設備が残っているため設備新設コストは発生せずに「０」のままである。一方、ノード７０４は、元々余剰設備量は０であるため余剰設備量は変化しない。しかしながら、新設すべき設備の量は８０単位分だけ減少するため、設備新設コストは１００から２０へと８０だけ減少する。これにより、この区間では、初期パスによれば１１０の設備新設コストが必要であったところ、パスの置換によってこの時点で設備新設コストを３０まで減らすことが可能となる。
【００３７】
各ノードの設備量と設備新設コストとの更新の後に、設備新設コストの総和が、置換によりどの程度低減したかを示す低減率ｒを算出し（Ｓ６０９）、低減率ｒと閾値ｘとを比較する（Ｓ６１０）。そして、低減率ｒが閾値ｘより大きい場合（Ｓ６１０でＹｅｓ）、変数ｃｎｔを０にクリアして（Ｓ６１４）、Ｓ６０２へ処理を戻す。一方、低減率ｒが閾値ｘ以下である場合（Ｓ６１０でＮｏ）は、変数ｃｎｔをインクリメントして（Ｓ６１１）、インクリメントによりｃｎｔが所定数ｋに達したかを判定する（Ｓ６１２）。そして変数ｃｎｔが所定数ｋに達していた場合（Ｓ６１２でＹｅｓ）、設備を新設すべきノードと各ノードの設備新設コストの総和とを出力して（Ｓ６１３）、処理を終了する。一方、変数ｃｎｔが所定数ｋに達していない場合（Ｓ６１２でＮｏ）は、処理をＳ６０２へ戻す。
【００３８】
これらのＳ６１０からＳ６１４までの処理は、コストの低減率が鈍化し、定常状態になったかを判定する処理である。すなわち、パスの置換によるコスト低減率ｒが閾値ｘ以下である場合が所定回数連続した場合は、これ以上大きくコストを低減することができないと判断し、処理を終了する。一方、パスの置換によるコスト低減率ｒが閾値ｘより大きい場合は、まだ大きくコストを削減することができる可能性が残っていると判断し、処理を続行する。これにより、演算量を抑制しながら十分にコストを低減できる適切な解を出力することが可能となる。
【００３９】
一方、Ｓ６０６において、所定数より少ない需要においてしか要求品質を満足することができないと判定されると（Ｓ６０６でＮｏ）、その候補パスを、置換対象区間と関連付けてタブーリストに登録する（Ｓ６１５）。これは、置換対象区間を置換してもＳ６０６の判定基準を満たすことができないことが分かった候補パスについて、タブーリストに登録することにより後に再度候補パスとなることを防ぐためのものである。これにより、実際に置換されることのないパスを候補パスとして抽出することを防ぐことができ、演算量を低減することが可能となる。なお、例えば図８において、候補パス（３）がノードＡからノードＦまでの区間と関連してタブーリストに登録された場合でも、例えばノードＡからノードＤまでの区間に対するＡ→Ｃ→Ｄのパスは、タブーリストに登録されていないものとして取り扱われる。ただし、Ａ→Ｃ→Ｄのパスが原因で要求品質を満足できないと判断できる場合などは、タブーリストに登録されているものとして取り扱ってもよい。
【００４０】
タブーリストへの登録後、変数ｍに１を加算し（Ｓ６１６）、Ｓ６０３で抽出した全ての候補パスについて置換を試行したかを判定する（Ｓ６１７）。全ての候補パスについて置換を試行していない場合（Ｓ６１７でＮｏ）は、次にコスト削減量が大きい候補パスを仮定して（Ｓ６０５）、Ｓ６０６の判定を再度行う。例えば、図７の例において、ノード７０２を経るパスで置換しても所定数より少ない需要しか要求品質を満足しない場合（Ｓ６０６でＮｏ）、ノード７０２を経るパスをタブーリストに登録する（Ｓ６１５）。そして、次にコスト削減量が大きい候補パスとしてノード７０３を経るパスへの置換を試行する（Ｓ６０５）。
【００４１】
一方、全ての候補パスについて置換を試行した場合（Ｓ６１７でＹｅｓ）、抽出した置換対象区間に対して実際には置換できるパスは存在しなかったと判定し、コストの基準値ＴをＴ−ΔＴまで下げ（Ｓ６１８）、置換対象区間の再抽出を行う（Ｓ６０２）。なお、ここで、基準値Ｔが所定の閾値以下となった場合、これ以上のコスト低減が不能と判定して処理を終了させてもよい。
【００４２】
このようにして、最低限のコストで各需要に対する要求品質を満足するための、設備を増設すべきノードを特定することができる。なお、図２のＳ２０３で設定されるように、本処理は、閾値ｘをパラメータとして複数の閾値ｘに対して同様の処理を行うことで、より高いコスト効率で、設備を増強すべきノードを特定することが可能となる。
【図１】
2013238989.tif 000003
【図２】
2013238989.tif 000004
【図３】
2013238989.tif 000005
【図４】
2013238989.tif 000006
【図５】
2013238989.tif 000007
【図６】
2013238989.tif 000008
【図７】
2013238989.tif 000009
【図８】
2013238989.tif 000010
【図９】
2013238989.tif 000011