(57)【要約】【課題】  データ転送の需要に対応するために設備を増設する際、通過するパスによっては設備の新設に要する費用が必要以上に増大するという問題があった。【解決手段】  ネットワークにおけるデータ転送の複数の需要に対して、設備を新設すべきノードを特定して出力するネットワーク設計方法であって、ネットワークに含まれるノードの中から、データ転送に用いられていない余剰設備量が閾値を超えるノードをポジティブノードとして抽出し、複数の需要のそれぞれに対して送信元と宛先のノードとを結ぶパスを、そのパスに含まれるポジティブノードではないノードである非ポジティブノードの数が最少となるように選択し、非ポジティブノードのそれぞれが、複数の需要に対して選択された複数のパスのうち、いくつに含まれるかを示す値を取得し、その値に応じて、設備を新設すべきノードを特定し、特定されたノードを出力する。【選択図】  図３
2013207416.tif 000002
【特許請求の範囲】
【請求項１】
データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計方法であって、
抽出手段が、前記ネットワークに含まれるノードの中から、データ転送に用いられていない余剰設備量が閾値を超えるノードをポジティブノードとして抽出する抽出工程と、
選択手段が、前記複数の需要のそれぞれに対して送信元のノードと宛先のノードとを結ぶパスを、そのパスに含まれる前記ポジティブノードではないノードである非ポジティブノードの数が最少となるように選択する選択工程と、
取得手段が、前記非ポジティブノードのそれぞれが、前記複数の需要に対する複数の前記パスのうち、いくつに含まれるかを示す値を取得する取得工程と、
特定手段が、前記値に応じて、設備を新設すべきノードを特定する特定工程と、
出力手段が、前記特定されたノードを出力する出力工程と、
を有することを特徴とするネットワーク設計方法。
【請求項２】
決定手段が、前記パスの選択を実行する前記複数の需要の順序を決定する決定工程と、
更新手段が、１つの需要に対するパスの選択を実行するごとに、前記ネットワークにおける前記ノードの前記余剰設備量を更新する更新工程と、をさらに有し、
前記抽出工程において、１つのパスの選択が実行されるごとに、更新された余剰設備量に応じて、前記抽出工程、前記選択工程、前記取得工程、前記特定工程および前記出力工程が実行される、
ことを特徴とする請求項１に記載のネットワーク設計方法。
【請求項３】
１つの前記需要に対して選択されたパスに含まれる前記非ポジティブノードの数が所定数以下である場合に、前記更新工程において、そのパスが通過するノードに応じて前記余剰設備量を更新する、
ことを特徴とする請求項２に記載のネットワーク設計方法。
【請求項４】
１つの前記需要に対して選択されたパスに含まれる前記非ポジティブノードの数が所定数より多い場合には、前記更新工程において当該需要に対する前記余剰設備量を更新しない、
ことを特徴とする請求項２又は３に記載のネットワーク設計方法。
【請求項５】
前記特定工程において設備が新設されるべきノードが特定されると、前記更新工程において、当該ノードに設備が新設されたと仮定して前記余剰設備量を更新し、
選択されたパスに含まれる前記非ポジティブノードの数が所定数より多かった需要に対しては、前記新設があったと仮定した場合のネットワークにおいて、前記抽出工程、前記選択工程、前記取得工程、前記特定工程および前記出力工程が再度実行される、
ことを特徴とする請求項２から４のいずれか１項に記載のネットワーク設計方法。
【請求項６】
全ての前記需要に対するパスの選択がなされた後に、前記特定工程において設備を新設すべきノードを特定する、
ことを特徴とする請求項１から５のいずれか１項に記載のネットワーク設計方法。
【請求項７】
その中に含まれる前記非ポジティブノードの数が所定数以上であったパスが選択されるごとに、前記特定工程において設備を新設すべきノードを特定する、
ことを特徴とする請求項１から５のいずれか１項に記載のネットワーク設計方法。
【請求項８】
前記抽出工程において、前記余剰設備が第２の閾値より少ないノードをネガティブノードとしてさらに抽出し、
前記選択工程において、前記ネガティブノードを含まないように、前記パスを選択する、
ことを特徴とする請求項１から７のいずれか１項に記載のネットワーク設計方法。
【請求項９】
記録手段が、複数の前記閾値のそれぞれに対して前記設備の新設に要するコストを記録する記録工程をさらに有し、
複数の前記閾値のうち、前記コストが最低となる前記閾値に対して前記特定工程で特定されたノードを、設備を新設すべきノードとして前記出力工程において出力する、
ことを特徴とする請求項１から８のいずれか１項に記載のネットワーク設計方法。
【請求項１０】
データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計装置であって、
前記ネットワークに含まれるノードの中から、データ転送に用いられていない余剰設備量が閾値を超えるノードをポジティブノードとして抽出する抽出手段と、
前記複数の需要のそれぞれに対して送信元のノードと宛先のノードとを結ぶパスを、そのパスに含まれる前記ポジティブノードではないノードである非ポジティブノードの数が最少となるように選択する選択手段と、
前記非ポジティブノードのそれぞれが、前記複数の需要に対する複数の前記パスのうち、いくつに含まれるかを示す値を取得する取得手段と、
前記値に応じて、設備を新設すべきノードを特定する特定手段と、
前記特定されたノードを出力する出力手段と、
を有することを特徴とするネットワーク設計装置。
【請求項１１】
請求項１から９のいずれか１項に記載のネットワーク設計方法における各工程をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、需要に応じてネットワークの設備を増設する際に、コストの低減を図る技術に関する。
【背景技術】
【０００２】
近年、ネットワーク上を流れるデータの量が増加しており、ネットワークはこのデータ量の増加に対応することを要求されている。データ量の増加に対しては、ネットワーク設備の新設により対応することが可能である。すなわち、データ転送の需要に対して、そのデータが発生するノードから、そのデータの宛先のノードまでのパスを確保するために、そのパスが通過するネットワーク内の中継ノードにおける設備を増強することにより、データの増大に対応することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、ネットワーク内のノードには、例えば、空きポートを有するがケーブルが接続されていないもの、ケーブルが挿入されている空きポートを有するもの、そして、空きポートを有さないものが存在する。このため、通過するパスによっては、設備の新設に要する費用が必要以上に増大するという問題があった。
【０００４】
本発明は上記課題に鑑みなされたものであり、データ転送の需要を処理するために必要な設備を最低限のコストで増設するためのネットワーク設計技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するため、本発明によるネットワーク設計方法は、データ転送の複数の需要に対して、設備を新設すべきネットワークのノードを特定して出力するネットワーク設計方法であって、抽出手段が、前記ネットワークに含まれるノードの中から、データ転送に用いられていない余剰設備量が閾値を超えるノードをポジティブノードとして抽出する抽出工程と、選択手段が、前記複数の需要のそれぞれに対して送信元のノードと宛先のノードとを結ぶパスを、そのパスに含まれる前記ポジティブノードではないノードである非ポジティブノードの数が最少となるように選択する選択工程と、取得手段が、前記非ポジティブノードのそれぞれが、前記複数の需要に対する複数の前記パスのうち、いくつに含まれるかを示す値を取得する取得工程と、特定手段が、前記値に応じて、設備を新設すべきノードを特定する特定工程と、出力手段が、前記特定されたノードを出力する出力工程とを有する。
【発明の効果】
【０００６】
本発明によれば、最低限のコストで設備を増設すべきネットワークノードを特定することができる。
【図面の簡単な説明】
【０００７】
【図１】ネットワーク設計装置のハードウェア構成例を示す図。
【図２】閾値αをパラメータとして増設すべき設備とそのコストを演算する処理を示すフローチャート。
【図３】ある閾値αに対する増設すべき設備とそのコストを演算する処理を示すフローチャート。
【図４】代表パスの選択方法の例を示す図。
【図５】代表パスの選択方法の例を示す図。
【図６】ある閾値αに対する増設すべき設備とそのコストを演算するもう１つの処理を示すフローチャート。
【図７Ａ】パスの設定、ノードのマーキング及び設備の増設の概念を示す概略図。
【図７Ｂ】パスの設定、ノードのマーキング及び設備の増設の概念を示す概略図。
【図７Ｃ】パスの設定、ノードのマーキング及び設備の増設の概念を示す概略図。
【図７Ｄ】パスの設定、ノードのマーキング及び設備の増設の概念を示す概略図。
【図７Ｅ】パスの設定、ノードのマーキング及び設備の増設の概念を示す概略図。
【図７Ｆ】パスの設定、ノードのマーキング及び設備の増設の概念を示す概略図。
【発明を実施するための形態】
【０００８】
以下、添付図面を参照して本発明の実施の形態を詳細に説明する。
【０００９】
本実施形態に係るネットワーク設計装置は、あるノードから別のノードに対するデータ転送の需要に対して、例えば、接続工事が完了している空きポートを所定数以上有するノードを抽出してポジティブノードリストとして保持する。そして、データ転送の需要ごとに、可能な限りポジティブノードリストに含まれるノード（ポジティブノード）を通過するパスを形成する。そして、形成したパスに含まれるポジティブノード以外のノード（非ポジティブノード）をマーキングしておき、多くのパスに含まれる非ポジティブノードに対してポートを増設すべきであると判定する。すなわち、新規の需要に対応するためのパスに含まれる蓋然性の高い非ポジティブノードを選択し、その非ポジティブノードに対して新規設備を増設するようにする。このとき、最低限の新規設備の増設数の条件を満たしながら、コストを最小化するようにする。これにより、パス選択時に可能な限りポジティブノードを選択してパスを形成すると共に、新規設備を増設することが効果的である非ポジティブノードを抽出することができる。また、この結果を用いて、最低限のコストで効果的に設備の増強を行うことが可能となる。
【００１０】
（ネットワーク設計装置の構成）
以下、具体的に本実施形態に係るネットワーク設計装置について説明する。なお、本ネットワーク設計装置は、例えば、図１に示すような、ＣＰＵ１０１、ＲＯＭ１０２、ＲＡＭ１０３、外部記憶装置１０４を備えるコンピュータ１００により実現される。コンピュータ１００においては、ＲＯＭ１０２に記録された本方法に係るプログラムをＣＰＵ１０１により実行する。そして、例えば、ポジティブリストなどの中間生成物をＲＡＭ１０３に記憶させ、最終的な結果を外部記憶装置１０４へ格納する。なお、ネットワーク設計装置は、以下に説明する各機能を実行する専用のハードウェアを備えてもよいし、一部をハードウェアで実行し、その他の部分をコンピュータ１００により実行させてもよい。
【００１１】
（ネットワーク設計装置の処理）
本実施形態に係るネットワーク設計装置の動作について、図２及び図３を用いて説明する。ネットワーク設計装置は、処理が開始に先立ち初期化処理を行う（Ｓ２０１）。具体的には、パラメータｉを０に設定する。パラメータｉは、後述の閾値候補αiの中から処理に用いるものを特定するためのインデックスである。なお、閾値候補αiは、ｉmax個存在するものとする。
【００１２】
続いて、後述するＳ２０３の処理で使用する閾値αをｉ番目の閾値候補であるαiに設定する（Ｓ２０２）。そして、閾値αの場合について、各データ転送の需要に対するパスの割り当て、要求される新設設備、及び要求されるコスト（Ｃi）が決定され、記録される（Ｓ２０３）。Ｓ２０３の動作の詳細については、図３の説明で後述する。
【００１３】
そして、ｉを１だけ増加させ（Ｓ２０４）、全ての閾値候補αiについての処理が完了したかを判定する（Ｓ２０５）。全ての閾値候補αiについての処理が完了した場合（Ｓ２０５でＹｅｓ）、コストＣiが最小となるαiを特定する。そして、その閾値に対してＳ２０３で決定された要求される新設設備を、増設すべき新設設備として出力する（Ｓ２０６）。一方、全ての閾値候補αiについての処理が完了していない場合（Ｓ２０５でＮｏ）、処理をＳ２０３へ戻し、次の閾値候補を用いて、Ｓ２０３の処理を行う。これにより、最低限のコストで、データ転送の需要を満足させることを可能とする、新設すべき設備を特定することが可能となる。
【００１４】
なお、増設すべき新設設備は、どのノードにどのような設備の新設が必要であるかの情報となる。なお、最終的な増設すべき新設設備が決定されたのちに、この増設を実行するための設備資材の移送手配のスケジューリングについて、線形計画法の輸送問題として解くことにより、移送コストを最小化することもできる。
【００１５】
続いて、上述のＳ２０３の処理について、図３を用いて説明する。処理においては、まず、複数のデータ転送の需要に対して、どの需要からパスの検索及び割り当てを実行するかを決定する（Ｓ３０１）。すなわち、複数の需要の送信元のノードと宛先のノードとの間を結ぶパスを検索する際に、どの送信元と宛先のノードの組み合わせからパスの検索を行うかを決定する。例えば、遅延制約の厳しい需要から順に、パスの検索を実行するように順序を決定する。
【００１６】
続いて、実際の処理の開始に先立って、パラメータの初期化を行う（Ｓ３０２）。例えば、まず、検索すべき全パス数、すなわちデータ転送の需要の数をＮmaxに設定し、パス検索対象の需要を指定するパラメータＮを０に設定する。そして、Ｓ２０２で定めた閾値αを用いて、パスを形成する際に中継点となりうるすべてのノードから、余剰設備（余剰リソース）の量がαを超えるノードを抽出し、ポジティブノードリストを生成する（Ｓ３０３）。ここで、ネットワーク設計装置は、各ノードが有するポートなどのリソースの情報とその利用状況の情報とを記憶しておき、その情報に基づいて余剰設備量を特定する。なお、余剰設備とは、例えば、各ネットワークノードにおける、所望のインタフェースのポートのうち、データ転送に用いられていないものであり、ケーブルがすでに接続され、利用可能な状況にあるものを言う。すなわち、特段の工事などを要することなく利用可能な空きポートの量が、閾値αを超えているノードを、ポジティブノードとして抽出し、リスト化する。
【００１７】
続いて、Ｎ＋１番目の需要に対する代表パスを決定する（Ｓ３０４）。ここで、代表パスは、可能な限り非ポジティブノードを通過しないようなパスとして与えられる。例えば、図４の例では、データ転送の需要の送信元ノードは「Ｓ」で表されるノード４０１で、宛先ノードは「Ｄ」で表されるノード４０２であるとする。そして、この送信元ノード４０１と宛先ノード４０２との間に、中継ノードとして４０３〜４０６の４つのノードが存在するものとし、「Ｐ」で表されるノード、すなわち、ノード４０３及び４０６がポジティブノードであるとする。なお、２つのノード間が接続されていることを破線で表している。この場合、ＳからＤへデータ転送するためのパスは、例えば、ノード４０３とノード４０４を介するパスや、ノード４０５とノード４０６を介するパスなど、複数存在する。しかし、ここでは、非ポジティブノードを可能な限り通過しないパスとして、ポジティブノードであるノード４０３とノード４０６とだけを通過するパスが代表パスとして選択される。同様に、図５の例では、送信元ノード５０１から宛先ノード５０２までの間で、非ポジティブノードの数が最少（１つ）となるパスとして、ノード５０３、ノード５０６、及びノード５０７を通過するパスを、代表パスとして選択する。なお、代表パスの決定方法においては、分枝限定法を用いることができる。
【００１８】
続いて、決定した代表パスについて、非ポジティブノードにマーキングする（Ｓ３０５）。例えば、図５の例の場合、ノード５０７がマーキングされる。一方、ノード５０４やノード５０５は、非ポジティブノードであるが、代表パスに含まれないため、マーキングされない。ここで、ネットワーク設計装置は、各ノードがいくつの代表パスに対してマーキングされたかの値を取得し、記憶しておく。
【００１９】
次に、代表パスにいくつの非ポジティブノードが含まれているかをカウントし、その数が、所定数以下であるかを判定する（Ｓ３０６）。所定数は例えば３である。また、図５の例では、代表パスに含まれる非ポジティブノード数は１である。そして、非ポジティブノード数が所定数以下である場合（Ｓ３０６でＹｅｓ）、そのパスが品質の制約条件を満たすかを判定する（Ｓ３０７）。品質の制約条件とは、例えば、光ケーブルを用いる場合は波長リソースを考慮したうえでの許容遅延や信号品質である。代表パスが品質の制約条件を満たす場合（Ｓ３０７でＹｅｓ）、処理はＳ３０８へ移る。一方、代表パスに所定数より多くの非ポジティブノードが含まれる場合（Ｓ３０６でＮｏ）や、パスが品質の制約条件を満足しない場合（Ｓ３０７でＮｏ）、処理をＳ３０９へ移す。
【００２０】
ネットワーク設計装置は、Ｓ３０８において、代表パスをその需要へのパスとして割り当てると共に、その割り当てで消費されるリソースに基づいて、各ノードが有するポートなどのリソースの情報とその利用状況の情報について、記憶していた情報を更新する。すなわち、代表パスの割り当てにより、そのパスに含まれるノードではポートが使用されるため、空きポートの量が減少する。このため、Ｓ３０８では、このような状況をネットワーク設計装置が記憶する情報に反映する。一方、Ｓ３０９では、代表パスが割り当てできないものとして、その需要を割当不能リストに登録する。なお、割当不能リストに登録された需要に対してはパスの割り当てを保留し、後述するＳ３１２により設備の新設が仮定された後に、仮定された新設設備があるものとして、再度代表パスの決定やマーキングなどを試行する。
【００２１】
そして、パス検索対象の需要を指定するパラメータＮを１だけ増加させ（Ｓ３１０）、全ての需要に対してパス検索が完了したかを判定する（Ｓ３１１）。すべての需要に対してパス検索が完了していない場合（Ｓ３１１でＮｏ）は、処理をＳ３０３へ戻し、更新した情報に基づいてポジティブノードリストの更新（Ｓ３０３）から再度処理を開始する。
【００２２】
一方、全ての需要に対してパス検索が完了した場合（Ｓ３１１でＹｅｓ）、それまでの各需要に対しての代表パスに対して、マーキングされた回数に応じて、新設すべき設備の最少台数を制約条件として最小コストでの設備の新設を仮定する（Ｓ３１２）。なお、新設すべき設備の最少台数は、マーキングの回数に応じて決定される。例えば、そのノードを含む全ての代表パスを収容できる最小限の台数であってもよいし、次回の割り当て時にポジティブノードとなるように最小限の台数に所定の台数を加算した台数であってもよい。
【００２３】
また、設備を新設するノードは、マーキングされた全ノードであってもよいし、マーキングされたノードの中から所定数（例えば１つ）を選んでもよい。なお、所定数のノードを選択する際には、例えば、Ｓ３０５でマーキングされた回数が最も多いノードから順に所定数のノードが選択されてもよい。すなわち、ポジティブノードでないにも関わらず、多くの代表パスに含まれるノードが選択されてもよい。なお、マーキングされた回数が所定回数より多いノードの中から、設備を新設するノードをランダムに選択してもよい。
【００２４】
マーキングされた全ノードにおいて設備の新設を仮定すると、全ての需要に対してパスが決定されるまでの処理の収束速度が速くなるという利点を有する。一方、所定数のノードのみに設備の新設を仮定すると、必要最低限の数のノードにおいて必要最低限の設備の新設を仮定することができるという利点を有する。このように、どちらの手法を用いるかについては、状況に応じて切り替えられてもよい。
【００２５】
Ｓ３１２では、例えば、あるノードにおいて、１００個の新規設備が必要である場合、その１００個の新規設備を構築するのに最も費用が少なくなるように、増設すべき設備を決定する。より具体的には、ノードには、空きポートが存在し、そこにケーブルが接続されているものと、そのいずれかがないものが存在しうる。ここで、ノードにケーブルが接続された空きポートが１００個存在すれば、コストはかからないため、そのケーブルが接続された空きポートを利用するようにする。これに対し、例えば、ケーブルが接続された空きポートが５０個しかない場合、残りの５０個の設備については、空きポートの増設、ケーブルの接続又はその両方を行うことにより賄う。このとき、空きポートの増設とケーブルの接続との両方を行う場合が最もコストがかかる。このため、空きポートまたはケーブルが存在する場合は可能な限りそれを用い、それでも賄いきれない場合に空きポートとケーブルの両方の増設を伴うパッケージの増設を行うようにする。
【００２６】
そして、最小コストでの設備の新設の仮定が完了すると、マーキングをすべて削除する（Ｓ３１３）。そして、過去にＳ３１２で仮定した新設設備のうち、直前のＳ３０３〜Ｓ３１１までの処理において、使用されなかったものを仮定から削除する（Ｓ３１４）。これは、Ｓ３１２において新設設備を仮定した後に割当不能リストに含まれた需要の再割り当てを試行するところ、新設設備の仮定の前後で、設備状況の変化に応じて、代表パスがその新設設備を仮定したノードを通過しなくなることがあるからである。このため、Ｓ３１４では、設備状況の変化により使用されなくなった新設設備を仮定から削除する。
【００２７】
Ｓ３１２とＳ３１４における新設設備の仮定と削除が完了すると、その時点で仮定される新設設備と、それに要するコストとが記録される（Ｓ３１５）。そして、割当不能リストに需要が含まれているかを判定する（Ｓ３１６）。割当不能リストに需要が含まれていない場合は（Ｓ３１６でＮｏ）、全ての需要に対するパスの割り当てが完了したこととなるため、処理を終了する。
【００２８】
一方、割当不能リストに需要が含まれている場合（Ｓ３１６でＹｅｓ）は、パスの割り当てが完了していない需要が存在するため、それらの需要に対するパスの検索を再度実行する。このため、まず、割当不能リストに含まれる需要についてパス検索を実行する順序を決定し（Ｓ３１７）、そのリストに含まれる需要の数により、Ｎmaxを更新する（Ｓ３１８）。そして、パラメータＮを０に戻し（Ｓ３１９）、処理をＳ３０３に戻す。なお、Ｓ３１７の処理は、Ｓ３０１で決定した順序を再利用してもよい。
【００２９】
上述の処理では、全ての需要に対してパス検索が完了後に、新設設備の増設についての処理を実行したが、これに限られない。例えば、ある代表パスに所定数より多くの非ポジティブノードが含まれていることを検出するごとに、新設設備の増設に関する処理を実行してもよい。すなわち、図６に示すように、Ｓ３０６又はＳ３０７でＮｏであった場合、需要を割当不能リストに登録すると共に、新設設備に関する処理を行うようにする。そして、新設設備と総コストを記録する（Ｓ３１５）と、処理をＳ３１０へ移行させてもよい。なお、この場合、全パスに対する処理が完了したと判定された場合（Ｓ３１１でＹｅｓ）には、Ｓ３１６へ処理を移すようにする。また、Ｓ３１４の処理は、Ｓ３１３の後だけでなく、全ての需要へのパスの割り当てが完了後（Ｓ３１６でＮｏ）に行われてもよい。また、Ｓ３１４の処理は、全需要へのパスの割り当て後のみ行われてもよい。なお、全需要へのパスの割り当て後に不要新設設備の削除を行う場合は、その処理に伴って、Ｓ３１５の処理が続いて実行される。
【００３０】
なお、すべての需要に対してパス検索を終了してから新設設備の増設に関する処理を行う場合は、あるノードに対して十分な量の設備の新設がされることにより、各需要がとりうるパスの自由度が高まり、最適な結果を得やすいという効果がある。一方、代表パスに非ポジティブノードが所定数より多く含まれることを検出するごとに新設設備の増設に関する処理を実行する場合は、その後にパス検索を行う需要の代表パスに対して非ポジティブノードが含まれる確率を低減できる。このため、全体の演算が完了するまでの処理時間や処理量を抑えることが可能となる。
【００３１】
続いて、本処理について、図７Ａ〜図７Ｆを用いて説明する。図７Ａは、パスの割り当て及び新設設備の増加を実行する前のネットワークの状態を示す図である。図において、Ｓ１、Ｓ２並びにＳ３及びＤ１、Ｄ２並びにＤ３は、それぞれ１〜３番目の需要を示す。また、丸はノードを示し、破線は、２つのノード間が接続される関係にあることを示す。ノードの右下の数字は、余剰設備量を示す。以下の説明では、α＝２とし、Ｓ３０６の所定数を２とする。α＝２であるため、余剰設備量が３以上のノードはポジティブノードであり、図では、これを二重丸で示す。
【００３２】
まず、処理が開始されると、需要に対するパス検索を実行する順序を決定する（Ｓ３０１）。本例では、Ｓ１からＤ１へのデータ転送に関する第１の需要、Ｓ２からＤ２へのデータ転送に関する第２の需要、そしてＳ３からＤ３へのデータ転送に関する第３の需要の順でパス検索を実行するものとする。そして、余剰設備量が３以上のノードとして、図の二重丸で示すノードを抽出し、ポジティブノードリストを生成する（Ｓ３０３）。そして、まず、第１番目の需要に対してパス検索を行う。第１番目の需要に対しては、図７Ｂの太線の矢印で示すような経路であれば、非ポジティブノードの数が１つのみとなる。なお、これ以外の経路でも非ポジティブノード数を１つとすることはできるが、例えば、遅延などの基準により、図のような経路が代表パスとして選択されるものとする（Ｓ３０４）。
【００３３】
そして、代表パスに含まれる非ポジティブノードにマーキングする（Ｓ３０５）。図７Ｂにおいて、グレーで塗りつぶされた円で表されるのが、代表パスに含まれる非ポジティブノードである。そして、非ポジティブノードの左下に示す四角で囲まれた数字は、マーキングされた回数を示す。このように、第１の需要に対しては、図７Ｂで示すように、１つのノードがマーキングされる。ここで、この代表パスに含まれる非ポジティブノードは１つであるため、所定数である２以下である。また、この代表パスは、品質の制約条件を満たすものとする。すると、この代表パスは割り当てられると共に、このパスに含まれるノードの剰余リソース量から、この割り当てにより消費された分だけ、リソース数を減算し、ネットワークの状態の情報を更新する（Ｓ３０８）。なお、本実施形態では、簡単のため、各パスがリソースを１つのみ消費するとしたが、これに限られない。例えば、同一の送信元および宛先を有する複数の需要の経路を一度に設計するために、複数のリソースを消費してもよく、その場合、剰余リソースからその消費分だけ減算した結果を記録するようにしてもよい。
【００３４】
続いて、更新したネットワークにおいて、第２の需要に対するパス検索を行う。この場合検索されて抽出される代表パスは、図７Ｃのようになる。この場合も、代表パスに含まれる非ポジティブノード数は１である。このため、代表パスを第２の需要へのパスとして割り当てると共に、ネットワークの状態の情報を更新する。なお、更新後の各ノードの剰余リソース量は、図７Ｃの各ノードの右下に示す数字の通りである。
【００３５】
そして、第３の需要に対するパス検索を行う。この場合、図７Ｄに示す通り、Ｓ３からＤ３までのパスには、最低でも３つの非ポジティブノードが含まれることとなる。この場合、所定数である２より多くの非ポジティブノードが含まれているため（Ｓ３０６でＮｏ）、パスの割り当てを行わず、この需要を割当不能リストに登録する。ここで、全ての需要に対するパス検索が終了したため（Ｓ３１１でＹｅｓ）、マーキング結果に応じた、設備の新設に関する処理に移る（Ｓ３１２）。ここで、マーキングされたノードは、図７Ｄに示すように、３つ存在する。このため、この時点でマーキングされた回数に応じた設備の増設の仮定を実行する。この場合、マーキングされたノードは、Ｓ３からＤ３へ向かうパス上の３つのノードであり、そのマーキング回数は、それぞれ１回、１回、３回である。このため、これらのノードに対して、そのマーキング回数に応じて、それぞれ、例えば１つ、１つ、３つのポート増設を仮定する。そして、全局のマーキングをクリアし（Ｓ３１３）、新設設備とそのコストを記録する（Ｓ３１５）。なお、図７Ｄでは、第３のパスを割り当てた場合の設備量を各ノードの右下に記載しているが、実際は第３のパスは割り当てられないため、この設備量は記録されない。
【００３６】
これらの処理の結果として得られるネットワークの状態を図７Ｅに示す。この状態は、第３の需要にパスを割り当てる前の状態である。このように、設備の増設を仮定することにより、第１から第３の需要を処理するのに十分な設備が備わることとなる。すなわち、設備の増設の仮定後には、図７Ｆに示すように、Ｓ３からＤ３への需要に対しても、非ポジティブノードを３つ以上通過することなく代表パスを設定することができる。
【００３７】
なお、Ｓ３からＤ３への需要に対するパスの設定後は、マーキングされたノードに対する設備の新設の仮定（Ｓ３１２）とマーキングのクリア（Ｓ３１３）が行われる。このとき、図７Ｆに示すマーキングされた１つのノードに１つの設備の増設が仮定される。そして、余剰に仮定した設備が削除される（Ｓ３１４）。この場合、図７Ｆに示す余剰設備数に加えてマーキングされたノードに１つの設備の新設が追加で仮定されているため、設備の増設を仮定した３つのノードで、それぞれ設備が２つずつ余っている。そして、これらのノードに仮定された設備の数はそれぞれ１つ、１つ、４つである。このため、この数に応じて各ノードに仮定した新設設備から、それぞれ１つ、１つ、２つの設備数を減じる。この結果、最終的に仮定される、これらの３つのノードで増設されるべき設備数は、それぞれ０個、０個、２個となる。なお、Ｓ３１４の不要新設設備の削除処理においては、Ｓ３１２で新設が仮定されたばかりの設備については削除の対象外としてもよい。この場合、本例では、図７Ｆでマーキングされたノードについての不要新設設備の削除が行われなくなる。この場合は、例えば、割当不能リストに需要がなくなった（Ｓ３１６でＮｏ）後に、再度不要新設設備の削除を行うことにより、このノードについても不要な新設設備を削除することができる。このようにして、図７の場合、最終的に、ネットワーク全体で２つの設備を新設すればよい、という結果が得られる。
【００３８】
なお、上述の例では、マーキングされたすべてのノードに対して設備の増設を仮定したが、上述のように、マーキングされたノードの中から設備の増設の対象とする所定数のノードを選択してもよい。例えば、所定数を１としたときに、マーキング回数が最大のノードを設備の増設の対象として選択してもよい。例えば、図７Ｄの例の場合、３回マーキングされたノードを設備の増設の対象として選択する。そして、そのマーキング回数に応じて、例えば３つのポート増設を仮定する。
【００３９】
さらに、上述の例では、１回マーキングされたノードへは１つの設備の増設を仮定するなど、マーキングされた回数分の設備の増設を仮定したが、これに限られない。例えば、もともとの剰余リソース量をも考慮してもよい。例えば、３回マーキングされたとしても、もともとの剰余リソース量が１である場合、設備を２つ増設することにより、全ての需要に対応することは可能となる。このため、この場合は、設備を２つ増設するようにしてもよい。
【００４０】
また、割当不能リストに含まれる需要の数や量に応じて、仮定する設備の増設数を調節するようにしてもよい。例えば、割当不能リストに含まれる需要で消費されうる最大量以上の設備を増設しても、使用される見込みはない。このため、割当不能リストに含まれる需要で消費されうる最大量に対処できる最低限度の設備の増設を仮定するようにしてもよい。また、これに伴って、需要へのパスの割り当て可否の基準となるＳ３０６の所定数を変化させてもよい。
【００４１】
このようにして、ある閾値αに対して、どのように設備を新設すれば、最低限のコストで、データ転送の需要を満足することが可能となるかを特定することが可能となる。そして、閾値αをパラメータとしてこの処理を複数回繰り返すことにより、より低いコストでデータ転送の需要に対処可能となる設備の増設箇所を特定することが可能となる。
【００４２】
上述の実施形態では、閾値αを超える余剰設備を有するノードをポジティブノードとしてポジティブノードリストを生成したが、これに加えて、第２の閾値より少ない余剰設備しか有さないノードをネガティブノードとしてリスト化してもよい。この場合、例えば、Ｓ３０４において、可能な限りポジティブノードを通過するようにすると共に、そのパスがネガティブノードを通過しないようにして代表パスを決定する。そして、例えば、ネガティブノードを通過しないパスが存在しない場合、通過するネガティブノード数が最少で、かつ、非ポジティブノードの数も最少となるように代表パスを決定してもよい。さらに、例えば、ある需要に対して、ネガティブノードを通過しないパスが存在しない場合には、パスに含まれる非ポジティブノード数が所定数以下であったとしても、その需要を割当不能リストに登録するようにしてもよい。これにより、例えば最初から余剰設備が少なく、設備を増設するのにコストが多大に発生しうるノードについて新設設備を仮定する確率が低くなる。
【００４３】
なお、余剰設備を有するノードも、多数のパスに含まれることにより、Ｓ３０８の情報更新によってネガティブノードリストに含まれる場合がある。しかしながら、この場合は、Ｓ３０５において、非ポジティブリストからネガティブノードとなるまでに複数回マーキングされることとなる。このため、最初からネガティブノードでないのであれば、マーキング回数が累積することにより、Ｓ３１２で設備が新設されるノードとして選択されうる。このように、ネガティブノードリストを用いることにより、最初から余剰設備が少ないノードについては、設備を増設するノードとして選択されにくくすることができ、結果として、増設にかかるコストを低減することができる。
【図１】
2013207416.tif 000003
【図２】
2013207416.tif 000004
【図３】
2013207416.tif 000005
【図４】
2013207416.tif 000006
【図５】
2013207416.tif 000007
【図６】
2013207416.tif 000008
【図７Ａ】
2013207416.tif 000009
【図７Ｂ】
2013207416.tif 000010
【図７Ｃ】
2013207416.tif 000011
【図７Ｄ】
2013207416.tif 000012
【図７Ｅ】
2013207416.tif 000013
【図７Ｆ】
2013207416.tif 000014