(57)【特許請求の範囲】
【請求項１】
ノード間を接続する物理的な通信路である下位レイヤリンク、前記下位レイヤリンクを接続することにより構成される下位レイヤパス、および、前記下位レイヤパスを利用することにより構成されてトラヒックを通信する上位レイヤパスが設定されるネットワークシステムにおいて、前記下位レイヤパスおよび前記上位レイヤパスの構成を設計する網設計方法であって、
網設計装置は、記憶手段および経路計算手段を有し、
前記記憶手段は、前記下位レイヤリンク、前記下位レイヤパス、および、前記上位レイヤパスに関する情報、ならびに、トラヒックの通信量上限を規定するトラヒック条件を格納し、
前記経路計算手段は、置き換え対象の前記上位レイヤパスを選択し、前記トラヒック条件を満足するように前記上位レイヤパスの経路の置き換えを試行し、置き換え前の前記上位レイヤパスの経路の評価値から、置き換え後の前記上位レイヤパスの経路の評価値への変化をもとに、置き換えを実施するか否かを判断する手順を繰り返し実行し、
前記経路計算手段は、置き換え対象の前記上位レイヤパスを選択するときに、削除対象の前記下位レイヤパスを設定し、削除対象の前記下位レイヤパスに収容される前記上位レイヤパスから選択すること
を特徴とする網設計方法。
【請求項２】
前記経路計算手段は、置き換えを実施すると判断する前記上位レイヤパスの経路を置き換えることを特徴とする請求項１に記載の網設計方法。
【請求項３】
前記記憶手段は、前記トラヒック条件として、各上位レイヤノードヘの流入／流出トラヒック量上限、および、各上位レイヤノード間のトラヒック量上限を規定することを特徴とする請求項１または請求項２に記載の網設計方法。
【請求項４】
網設計装置は、前記ネットワークシステムのトラヒック交流を観測し、観測するトラヒック交流をもとに、前記トラヒック条件を決定することを特徴とする請求項１ないし請求項３のいずれか１項に記載の網設計方法。
【請求項５】
前記経路計算手段は、前記上位レイヤパスの置き換えを繰り返すときに、置き換え対象の前記上位レイヤパスの評価値を元に、Ｇｒｅｅｄｙアルゴリズムにより置き換えを実施するか否かを決定することを特徴とする請求項１ないし請求項４のいずれか１項に記載の網設計方法。
【請求項６】
前記経路計算手段は、前記上位レイヤパスの置き換えを繰り返すときに、置き換え対象の前記上位レイヤパスの評価値を元に、Ｈｅｕｒｉｓｔｉｃアルゴリズムにより置き換えを実施するか否かを決定することを特徴とする請求項１ないし請求項４のいずれか１項に記載の網設計方法。
【請求項７】
前記経路計算手段は、ある上位レイヤノードをルートとして選択し、最短経路木を構成するように前記下位レイヤパスを選択した上で、前記上位レイヤパスの経路を選択し、全ての上位レイヤノードをルートとして選択した場合の評価値を比較して、最もよい評価値となる経路を置き換える後の経路とすることを特徴とする請求項１ないし請求項４のいずれか１項に記載の網設計方法。
【請求項８】
ノード間を接続する物理的な通信路である下位レイヤリンク、前記下位レイヤリンクを接続することにより構成される下位レイヤパス、および、前記下位レイヤパスを利用することにより構成されてトラヒックを通信する上位レイヤパスが設定されるネットワークシステムにおいて、前記下位レイヤパスおよび前記上位レイヤパスの構成を設計する網設計装置であって、
前記下位レイヤリンク、前記下位レイヤパス、および、前記上位レイヤパスに関する情報、ならびに、トラヒックの通信量上限を規定するトラヒック条件を格納する記憶手段と、
置き換え対象の前記上位レイヤパスを選択し、前記トラヒック条件を満足するように前記上位レイヤパスの経路の置き換えを試行し、置き換え前の前記上位レイヤパスの経路の評価値から、置き換え後の前記上位レイヤパスの経路の評価値への変化をもとに、置き換えを実施するか否かを判断する手順を繰り返し実行する経路計算手段と、を有し、
前記経路計算手段は、置き換え対象の前記上位レイヤパスを選択するときに、削除対象の前記下位レイヤパスを設定し、削除対象の前記下位レイヤパスに収容される前記上位レイヤパスから選択すること
を特徴とする網設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、網設計方法および網設計装置に関する。
【背景技術】
【０００２】
従来、複数レイヤをまたがる網設計方法に関して、静的なトラヒックパターンを前提に、上位レイヤノード間のトラヒック量の上限のみをトラヒック条件として与え、これを満足するように網設計を行う方法がある。
【０００３】
この時の網設計の目的関数としては、例えば、網コストの最小化があり、網コストとは、上位レイヤノードのインタフェース数、下位レイヤノードのインタフェース数、下位レイヤリンクの距離、などにより決定される（非特許文献１、非特許文献２）。
【０００４】
また、トラヒックパターンが変動することを前提に、上位レイヤノードヘの流入／流出トラヒック量の上限をトラヒック条件として与え、これを満足するような網設計を行う方法もある。トラヒックパターンが変動することを前提とすると、下位レイヤリンクの接続構成により定義される物理的な網構成が、リングトポロジに限定される（非特許文献３、非特許文献４）。
【非特許文献１】K. Zhu and B. Mukherjee,“Traffic grooming in optical WDM mesh network,”IEEE J.Sel. Areas Commun.,vol.20,no.1,pp.122-133,Jan.~2002.
【非特許文献２】I. Cerutti and A. Fumagalli,“Multi-rate and multi-hop hybrid optical networks with arbitrary topology,”HPSR2003,pp.239-244,June 2003.
【非特許文献３】R.Berry and E.Modiano,“Reducing electric multiplexing costs in SONET/WDM rings with dynamically changing traffic,”IEEE J. Sel. Areas Commun.,vol.18,no.10,Oct.2000.
【非特許文献４】O. Gerstel,R. Ramaswami and G. Sasaki,“Cost-effective traffic grooming in WDM rings,”IEEE/ACM Trans.Networking,vol8,no.5,0ct.2000.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来手法では、トラヒックを伝送するパスの経路について、ネットワークのコストを低減するような最適化が充分に行われていなかった。そのため、トラヒック条件を満たすことはできても、ネットワークの利用効率がよくなかった。
【０００６】
そこで本発明では、トラヒックパターンが変動するような網設計方法の確立において、トラヒック条件を満足し、かつ、ネットワークの利用効率を向上するように下位レイヤパスと上位レイヤパスの経路を計算することを、主な目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、本発明は、ノード間を接続する物理的な通信路である下位レイヤリンク、前記下位レイヤリンクを接続することにより構成される下位レイヤパス、および、前記下位レイヤパスを利用することにより構成されてトラヒックを通信する上位レイヤパスが設定されるネットワークシステムにおいて、前記下位レイヤパスおよび前記上位レイヤパスの構成を設計する網設計方法であって、網設計装置が、記憶手段および経路計算手段を有し、前記記憶手段が、前記下位レイヤリンク、前記下位レイヤパス、および、前記上位レイヤパスに関する情報、ならびに、トラヒックの通信量上限を規定するトラヒック条件を格納し、前記経路計算手段が、置き換え対象の前記上位レイヤパスを選択し、前記トラヒック条件を満足するように前記上位レイヤパスの経路の置き換えを試行し、置き換え前の前記上位レイヤパスの経路の評価値から、置き換え後の前記上位レイヤパスの経路の評価値への変化をもとに、置き換えを実施するか否かを判断する手順を繰り返し実行し、前記経路計算手段は、置き換え対象の前記上位レイヤパスを選択するときに、削除対象の前記下位レイヤパスを設定し、削除対象の前記下位レイヤパスに収容される前記上位レイヤパスから選択することを特徴とする。
さらに、本発明は、前記網設計方法を実行する網設計装置である。
【０００８】
これにより、トラヒック条件を満足しつつ、網コストをなるべく少なくすることができ、経済的な網構築が可能となる。さらに、下位レイヤパス単位での最適処理を行うことができる。
【０００９】
本発明は、前記経路計算手段が、置き換えを実施すると判断する前記上位レイヤパスの経路を置き換えることを特徴とする。
【００１０】
これにより、網設計の結果に従って、ネットワークを運用できる。
【００１１】
本発明は、前記記憶手段が、前記トラヒック条件として、各上位レイヤノードヘの流入／流出トラヒック量上限、および、各上位レイヤノード間のトラヒック量上限を規定することを特徴とする。
【００１２】
これにより、実際のトラヒックパターンを考慮してトラヒック条件を与えることができ、利用状況に応じた網設計が可能となる。
【００１３】
本発明は、網設計装置が、前記ネットワークシステムのトラヒック交流を観測し、観測するトラヒック交流をもとに、前記トラヒック条件を決定することを特徴とする。
【００１４】
これにより、トラヒックパターンの変動を考慮したトラヒック条件を与えることができ、より現実的なトラヒック条件を与えることができる。
【００１９】
本発明は、前記経路計算手段が、前記上位レイヤパスの置き換えを繰り返すときに、置き換え対象の前記上位レイヤパスの評価値を元に、Ｇｒｅｅｄｙアルゴリズムにより置き換えを実施するか否かを決定することを特徴とする。
【００２０】
これにより、現在の解より最適な解を求めていくことにより、更なるコスト削減を期待できる。
【００２１】
本発明は、前記経路計算手段が、前記上位レイヤパスの置き換えを繰り返すときに、置き換え対象の前記上位レイヤパスの評価値を元に、Ｈｅｕｒｉｓｔｉｃアルゴリズムにより置き換えを実施するか否かを決定することを特徴とする。
【００２２】
これにより、局所解を避けて経路計算を行うことができ、更なるコスト削減を期待できる。
【００２３】
本発明は、前記経路計算手段が、ある上位レイヤノードをルートとして選択し、最短経路木を構成するように前記下位レイヤパスを選択した上で、前記上位レイヤパスの経路を選択し、全ての上位レイヤノードをルートとして選択した場合の評価値を比較して、最もよい評価値となる経路を置き換える後の経路とすることを特徴とする。
【００２４】
これにより、比較的少ない計算量で経路計算を行うことができる。
【発明の効果】
【００２７】
本発明では、パスの経路計算を繰り返すことにより、ネットワークのコスト面でのボトルネックを継続的に解消する。これにより、従来手法では実現できなかった、トラヒックパターンが変動する網の設計を効率的に実現できる。よって、トラヒック条件を満足しつつ、網コストをなるべく少なくすることでネットワークの利用効率を向上でき、経済的な網構築が可能となる。
【発明を実施するための最良の形態】
【００２８】
次に、本発明の実施の形態について図面を参照して説明する。
【００２９】
図１は、本発明の一実施形態であるネットワークシステムの構成図である。このネットワークシステムの形態は、例えば、メッシュトポロジである。
【００３０】
ネットワークシステムは、ノードを接続することにより構成される。ノード間には、ノード間で制御情報を交換するための媒体である制御リンクがあっても構わない。ノードは、上位レイヤノード１０または下位レイヤノード１２に分類される。なお、上位レイヤと下位レイヤとは異なるレイヤであり、上位レイヤは下位レイヤを利用して構成される。
【００３１】
上位レイヤノード１０は、上位レイヤにおけるデータ交換手段（図示省略）を有する。上位レイヤノード１０のデータ交換手段としては、ＭＰＬＳ（Multi Protocol Label Switching）のＬＳＲ（Label Switching Router）などが相当する。
【００３２】
下位レイヤノード１２は、下位レイヤにおけるデータ交換手段（図示省略）を有する。下位レイヤノード１２のデータ交換手段としては、ＯＸＣ（Optical Cross Connect）などが相当する。
【００３３】
なお、ネットワークシステムには、３種類以上のレイヤにおけるデータ交換手段を有するノードが混在していても構わない。３種類以上のレイヤは、下位レイヤパス１６が属するレイヤ、上位レイヤパス１８が属するレイヤに加え、前記２つのレイヤ以外のレイヤである。
【００３４】
外部のネットワーク（例：ユーザネットワーク）と接続し、トラヒックの交流がある上位レイヤノード１０を、境界ノードと呼ぶ。図１の例では、例えば、上位レイヤノード１０ａおよび上位レイヤノード１０ｃが外部のネットワークと接続され、上位レイヤノード１０ａに流入したトラヒックが、上位レイヤノード１０ｃから流出していると仮定すると、上位レイヤノード１０ａ、上位レイヤノード１０ｃを境界ノードと呼ぶ。
【００３５】
下位レイヤリンク１４は、隣接するノード間を物理的な接続パスで接続する。
【００３６】
下位レイヤパス１６は、下位レイヤリンク１４を直接接続することによって構成される物理的な経路である。例えば、下位レイヤパス１６ａは、下位レイヤリンク１４ａ、下位レイヤリンク１４ｂ、下位レイヤリンク１４ｅ上に張られる。
【００３７】
上位レイヤパス１８は、下位レイヤパス１６の上に構成される、データ転送のための通信接続の単位である。例えば、上位レイヤパス１８は、下位レイヤパス１６ａ、下位レイヤパス１６ｂ上に張られている。
【００３８】
網設計装置１は、複数レイヤをまたがって、各ノード間に複数のレイヤにおける接続パスの構成を計算する。網設計装置１は、ノードの中にあってもよいし、ノードとは独立のサーバなどにあってもよい。
【００３９】
なお、網設計装置１は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成される。演算処理は、ＣＰＵ（Central Processing Unit）によって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。本実施形態は、網設計装置１に加え、網設計装置１に演算処理を実行させるためのプログラム、および、そのプログラムを記録したコンピュータ読み取り可能な記録媒体を含む。
【００４０】
図２は、網設計装置１の構成図である。
【００４１】
トポロジ管理手段２０は、ノードおよび下位レイヤリンク１４の物理的な接続構成を管理しており、トポロジＤＢ２６の追加、削除、修正、および、検索を行う。トポロジ管理手段２０の実現方法としては、例えば、ＩＥＴＦ（Internet Engineering Task Force）が発行するＲＦＣ４２０３（OSPF Extensions in Support of Generalized Multi-Protocol Label Switching（ＧＭＰＬＳ））に規定されている。
【００４２】
トラヒック条件管理手段２２は、網設計において満足すべきトラヒック条件を管理し、トラヒック条件ＤＢ２８の追加、削除、修正、および、検索を行う。トラヒック条件管理手段２２は、トラヒック交流を観測し、トラヒック条件を決定してもよい。トラヒック条件を決定する手法としては、例えば、トラヒック交流の観測値の中で、各境界ノードへの流入トラヒック量／流出トラヒック量（流入トラヒック量および流出トラヒック量のうち、少なくとも１つのトラヒック量）、および、各境界ノード間のトラヒック量のうち、最大値をトラヒック条件として決定する手法が挙げられる。
【００４３】
経路計算手段２４は、トポロジＤＢ２６、トラヒック条件ＤＢ２８を入力とし、上位レイヤパス１８および下位レイヤパス１６の経路計算を行い、パスＤＢ３０に格納する。網設計装置１は、経路計算手段２４の計算結果に従って、下位レイヤパス１６および上位レイヤパス１８を設定するパス設定手段（図示省略）を有していてもよい。
【００４４】
トポロジＤＢ２６は、ノードおよび下位レイヤリンク１４の物理的な接続関係を格納する。トポロジＤＢ２６は、以下の情報（リンクＩＤ、上流ノードＩＤ、上流ノード種別、下流ノードＩＤ、下流ノード種別、および、コスト）を、リンク１本ごとに有する。リンクＩＤは、下位レイヤリンク１４を一意に識別する情報である。上流ノードＩＤは、前記リンクの上流ノードのノードＩＤである。上流ノード種別は、上流ノードの交換手段のレイヤ（上位レイヤノード１０であるか下位レイヤノード１２であるか）である。
【００４５】
下流ノードＩＤは、前記リンクの下流ノードのノードＩＤである。下流ノード種別は、下流ノードの交換手段のレイヤ（上位レイヤノード１０であるか下位レイヤノード１２であるか）である。コストは、前記リンクを使って下位レイヤパス１６を設定する際の前記リンク区間のコストを意味する。ノードＩＤとしては、例えば、ＩＰアドレスが相当する。
【００４６】
トラヒック条件ＤＢ２８は、網設計において満足すべきトラヒック条件を格納する。トラヒック条件は、境界ノードＩＤ、流入トラヒック量上限、流出トラヒック量上限、境界ノードＩＤ→境界ノードＩＤ、および、ノード間トラヒック量上限から構成される。境界ノードＩＤは、外部とトラヒックの出入り口になっているノードのノードＩＤであり、これは上位レイヤノード１０のどれかとなる。流入トラヒック量上限は、前記ノードヘの外部からの流入トラヒック量の上限を示す。流出トラヒック量上限は、前記ノードから外部への流出トラヒック量の上限を示す。境界ノードＩＤ→境界ノードＩＤは、その間にリソースを確保すべき境界ノードのペアを示し、→はトラヒックの流れる方向を示す。例えば、Ａ→Ｂとなっている場合、ＡからＢにトラヒックが流れる。以下、ｓｒｃ→ｄｓｔは、ｓｒｃからｄｓｔにトラヒックが流れることを意味する。ノード間トラヒック量上限は、前記境界ノード間のトラヒック量の上限を示す。
【００４７】
パスＤＢ３０は、経路計算の結果である経路を含め、下位レイヤパス１６と上位レイヤパス１８の情報を格納する。パスＤＢ３０は、以下の情報（始点ノードＩＤ、終点ノードＩＤ、パス種別、および、経路）を、パス１本ごとに有する。始点ノードＩＤは、パスの始点となるノードのノードＩＤである。終点ノードＩＤは、パスの終点となるノードのノードＩＤである。パス種別は、下位レイヤパス１６か上位レイヤパス１８かを示す情報である。経路は、パスが経由するリンクのリストである。
【００４８】
本数は、パス種別が下位レイヤパス１６であり、同じノード間の同じ経路上に複数本を設定する必要がある場合に、その下位レイヤパス１６の本数を示したものある。なお、パス種別が上位レイヤパス１８である場合、経路に格納されるリンクのリストは、下位レイヤパス１６のリストとなる。
【００４９】
図３は、経路計算手段２４の処理手順を示している。この処理は、上位レイヤパス単位の経路計算を行い、計算した経路の評価値を元に、Ｇｒｅｅｄｙアルゴリズムにより、置き換える上位レイヤパス１８を決定することを特徴とする。
【００５０】
Ｇｒｅｅｄｙアルゴリズムは、置き換え侯補の上位レイヤパス１８の評価値が前回（置き換え前）の評価値を上回る場合、その侯補を今回（置き換え後）の評価値となる経路として採用する処理を繰り返し、前回の評価値と今回の評価値とを比較して評価値が上昇しなくなると繰り返しを終了する手法である。
【００５１】
経路計算手段２４は、トラヒック条件を満足するような、パスの経路計算を行う。本フローチャートの開始時では、初期解が与えられているものとする。初期解の決定方法としては、例えば、後記する図１０に示す方法があるが、別の方法であっても構わない。
【００５２】
Ｓ１０１は、現在のネットワークコスト（評価値）を計算し、その計算結果をCurrentCostとする処理である。CurrentCostは、各下位レイヤパス１６のコストの総和で求められる。各下位レイヤパス「LowPath」のコストは、自身が経由するリンクのコストの総和「Cost（LowPath）」で求められる。
【００５３】
Ｓ１０２は、Minimumに初期値として大きな値（例えば、無限大）を代入する処理である。Ｓ１０３は、境界ノード間を１つ選択し、ｓｒｃ→ｄｓｔで表現する処理である。トラヒック条件管理手段２２は、トラヒック条件ＤＢ２８を検索し、境界ノード間トラヒック量上限が０より大きく、かつ、選択されていない境界ノード間を１つ選択する。
【００５４】
Ｓ１０４は、サブルーチン「パスの経路計算（Ｓ２００）」を呼び出す処理である。Ｓ１０５は、サブルーチン「パスの経路計算」で求めた経路に置き換えたことを想定して、ネットワークコストを計算し、その計算結果をCurrentCostDashとする処理である。
【００５５】
Ｓ１０６は、分岐条件「CurrentCostDash−CurrentCost＜０、かつ、CurrentCostDash＜Minimum」を満たすか否かを判定する処理であり、満たすとき（Ｓ１０６，Ｙｅｓ）にはＳ１０７を実行し、満たさないとき（Ｓ１０６，Ｎｏ）にはＳ１０８を実行する。
【００５６】
Ｓ１０７は、Minimum＝CurrentCostDashとする処理である。Ｓ１０８は、分岐条件「全境界ノード間について計算が終了」を満たすか否かを判定する処理であり、満たすとき（Ｓ１０８，Ｙｅｓ）にはＳ１０９を実行し、満たさないとき（Ｓ１０８，Ｎｏ）にはＳ１０３を実行する。Ｓ１０９は、分岐条件「Minimumが初期値のままである」を満たすか否かを判定する処理であり、満たすとき（Ｓ１０９，Ｙｅｓ）には終了し、満たさないとき（Ｓ１０９，Ｎｏ）にはＳ１１０を実行する。
【００５７】
Ｓ１１０は、Minimumとなる境界ノード間について経路を置き換える処理である。この計算の結果、帯域が０となることにより不要となる下位レイヤパス１６は削除し、既存の下位レイヤパス１６では帯域が不足する場合は下位レイヤパス１６を新設する。そして、処理をＳ１０１に戻す。
【００５８】
図４は、経路計算手段２４の処理手順を示している。この処理は、サブルーチン「パスの経路計算（Ｓ２００）」である。
【００５９】
Ｓ２０１は、ｓｒｃ→ｄｓｔ間のトラヒック転送のために設定される上位レイヤパス１８が、下位レイヤパス「LowPath」を経由すると仮定して、下位レイヤパス「LowPath」で上位レイヤパス１８を収容するのに必要な帯域「Bandwidth（LowPath）」を計算する処理である。なお、上位レイヤパス１８が経由すると仮定する下位レイヤパス１６は、全ての上位レイヤノード間に存在する。Bandwidth（LowPath）の計算方法としては、既存の方法を用いることができる（特開２００６−５４７２２号公報に記述されているリンクリソース計算手段を参照）。
【００６０】
Ｓ２０２は、Bandwidth（LowPath）を収容するのに必要な下位レイヤパス１６の本数「NumPaths（LowPath）」を計算する処理である。NumPaths（LowPath）の計算結果は、Bandwidth（LowPath）をLowPathBandwidth（下位レイヤパス「LowPath」の帯域）で割り、小数点を切り上げた整数となる。
【００６１】
Ｓ２０３は、ｓｒｃ→ｄｓｔ間のトラヒック転送のために設定される上位レイヤパス１８が、下位レイヤパス「LowPath」を経由しないと仮定して、下位レイヤパス「LowPath」で上位レイヤパス１８を収容するのに必要な帯域「BandwidthDash（LowPath）」を計算する処理である。なお、上位レイヤパス１８が経由しないと仮定する下位レイヤパス１６は、全ての上位レイヤノード間に存在する。BandwidthDash（LowPath）の計算方法も、Bandwidth（LowPath）と同様になる。
【００６２】
Ｓ２０４は、BandwidthDash（LowPath）を収容するのに必要な下位レイヤパス１６の本数「NumPathsDash（LowPath）」を計算する処理である。NumPathsDash（LowPath）の計算方法も、NumPaths（LowPath）と同様になる。
【００６３】
Ｓ２０５は、下位レイヤパス１６をリンクとみなし、各リンクのコスト「LowPathCost」を計算する処理である。各リンクのコスト「LowPathCost」は、NumPaths（LowPath）≠NumPathsDash（LowPath）のときには（式１）の計算結果となり、NumPaths（LowPath）＝NumPathsDash（LowPath）のときには（式２）の計算結果となる。なお、Cost（LowPath）は、下位レイヤパス「LowPath」が経由するリンクのコストの総和である。また、βは、定数（小さい値）であり、Bandwidth（LowPath）−BandwidthDash（LowPath）が０となるときに、（式２）の計算結果が０となることを防ぐための修正値である。
Cost（LowPath）×（NumPaths（LowPath）−NumPathsDash（LowPath））×LowPathBandwidth…（式１）
Cost（LowPath）×（Bandwidth（LowPath）−BandwidthDash（LowPath）＋β〉…（式２）
【００６４】
なお、現在は下位レイヤパス１６が存在しない区間については、Cost（LowPath）は、下位レイヤパス１６がとりうる経路のうち、最小コストのものを選択する。最小コストの選択には、既存のＤｉｊｋｓｔｒａ法などを用いることができる。
【００６５】
Ｓ２０６は、LowPathCostに基づき、ｓｒｃ→ｄｓｔへ最小コスト経路を求める処理である。この計算には、既存のＤｉｊｋｓｔｒａ法などを用いることができる。そして、処理をサブルーチンの呼び出し元に戻す。
【００６６】
図５は、経路計算手段２４の処理手順を示している。この処理は、上位レイヤパス単位の経路計算を行い、計算した経路の評価値を元に、Ｈｅｕｒｉｓｔｉｃアルゴリズムにより、置き換える上位レイヤパス１８を決定することを特徴とする。
【００６７】
Ｈｅｕｒｉｓｔｉｃアルゴリズムは、置き換え侯補の上位レイヤパス１８の評価値が前回の評価値を上回る場合、その候補を今回の評価値となる経路として採用し、前回の評価値を上回らない場合、その候補を今回の評価値となる経路として採用するか否かは所定の確率によって決定される処理を繰り返し、評価値となる経路が所定の回数だけ連続して変更されない場合には、これ以上評価値を改善する余地がないとして、繰り返しを終了する手法である。なお、所定の回数は、後記する定数「ＣＳ」または定数「ＣＲ」である。
【００６８】
Ｓ３０１は、サブルーチン「Ｈｅｕｒｉｓｔｉｃアルゴリズムによるパスの選択（Ｓ４００）」のための初期値設定を実行する処理である。具体的には、ループ用変数ｃａ＝０、ｃｒ＝０、ｃｃ＝０、ｃｓ＝０、および、Ｔ＝Ｔ０（Ｔ０：定数）とする初期化処理を実行する。
【００６９】
Ｓ３０２は、前記したＳ１０１と同じ処理である。Ｓ３０３は、前記したＳ１０３と同じ処理である。
【００７０】
Ｓ３０４は、サブルーチン「パスの経路計算（Ｓ２００）」を呼び出す処理である。なお、リンクコストの計算（Ｓ２０５）として、上位レイヤパス１８が通る下位レイヤパス１６のうち、任意の１つを選択し、このリンクコストを無限大として、削除対象の下位レイヤパス１６とする処理を追加する。
【００７１】
Ｓ３０５は、前記したＳ１０５と同じ処理である。Ｓ３０６は、ｃｃを１増やす処理である。Ｓ３０７は、サブルーチン「Ｈｅｕｒｉｓｔｉｃアルゴリズムによるパスの選択（Ｓ４００）」を呼び出す処理である。そして、処理をＳ３０２に戻す。
【００７２】
図６は、経路計算手段２４の処理手順を示している。この処理は、サブルーチン「Ｈｅｕｒｉｓｔｉｃアルゴリズムによるパスの選択（Ｓ４００）」である。
【００７３】
Ｓ４０１は、分岐条件「CurrentCostDash−CurrentCost＜０」を満たすか否かを判定する処理であり、満たすとき（Ｓ４０１，Ｙｅｓ）にはＳ４０２を実行し、満たさないとき（Ｓ４０１，Ｎｏ）にはＳ４０３を実行する。Ｓ４０２は、経路を置き換え、ｃａの値を１増やし、ｃｓ、ｃｒの値を０にする処理である。そして、処理をＳ４０８に移行する。
【００７４】
Ｓ４０３は、分岐条件「CurrentCostDash−CurrentCost＝０」を満たすか否かを判定する処理であり、満たすとき（Ｓ４０３，Ｙｅｓ）にはＳ４０４を実行し、満たさないとき（Ｓ４０３，Ｎｏ）にはＳ４０５を実行する。Ｓ４０４は、経路を置き換え、ｃａの値とｃｓの値を１増やし、ｃｒの値を０にする処理である。そして、処理をＳ４０８に移行する。
【００７５】
Ｓ４０５は、所定確率により分岐先を決定する処理であり、分岐先としてＳ４０６またはＳ４０７へと移行する。所定確率により分岐先を決定する処理は、次の通りである。まず、乱数値Ａを０から１までの範囲で計算する。次に、乱数値Ａが、（式３）の条件式を満たすか否かを判定し、条件を満たすときにはＳ４０６へ、条件を満たさないときにはＳ４０７へ、移行する。
【数１】
0004630223.tif 000002
【００７６】
Ｓ４０６は、経路を置き換え、ｃａの値を１増やし、ｃｓ、ｃｒの値を０にする処理である。そして、処理をＳ４０８に移行する。Ｓ４０７は、ｃｒを１増やす処理である。
【００７７】
Ｓ４０８は、分岐条件「ｃａ＝ＣＡ（ＣＡ：定数）、または、ｃｃ＝ＣＣ（ＣＣ：定数）である」を満たすか否かを判定する処理であり、満たすとき（Ｓ４０８，Ｙｅｓ）にはＳ４０９を実行し、満たさないとき（Ｓ４０８，Ｎｏ）にはＳ４１０を実行する。Ｓ４０９は、Ｔ＝α×Ｔ（α：定数）とし、ｃａ＝０、ｃｃ＝０とする処理である。そして、処理をＳ４１０に移行する。
【００７８】
Ｓ４１０は、分岐条件「ｃｒ＝ＣＲ（ＣＲ：定数）、または、ｃｓ＝ＣＳ（ＣＳ：定数）である」を満たすか否かを判定する処理であり、満たすとき（Ｓ４１０，Ｙｅｓ）には終了し、満たさないとき（Ｓ４１０，Ｎｏ）には呼び出し元に戻る。
【００７９】
図７は、経路計算手段２４の処理手順を示している。この処理は、下位レイヤパス単位の経路計算を行い、計算した経路の評価値を元に、Ｇｒｅｅｄｙアルゴリズムにより、置き換える上位レイヤパス１８を決定することを特徴とする。
【００８０】
Ｓ５０１は、前記したＳ１０１と同じ処理である。Ｓ５０２は、前記したＳ１０２と同じ処理である。
【００８１】
Ｓ５０３は、選択されていない下位レイヤパス１６を１本選択し、その始点ノードをｉ、終点ノードをｊとする処理である。Ｓ５０４は、サブルーチン「選択した下位レイヤパス１６を通る上位レイヤパス１８の集合をＲとする（Ｓ６００）」を呼び出す処理である。Ｓ５０５は、Ｒから１つの上位レイヤパス１８を取り出し、その始点ノードをｓｒｃ、終点ノードをｄｓｔとする処理である。取り出し方としては、ランダムでもよいし、境界ノード間トラヒック量上限が大きいものから取り出してもよい。
【００８２】
Ｓ５０６は、サブルーチン「パスの経路計算（Ｓ２００）」を呼び出す処理である。なお、リンクコストの計算（Ｓ２０５）として、Ｓ５０３で選択された下位レイヤパス１６（始点ノードｉ、終点ノードｊ）について、このリンクコストを無限大とする処理を追加する。
【００８３】
Ｓ５０７は、分岐条件「Ｒは空」を満たすか否かを判定する処理であり、満たすとき（Ｓ５０７，Ｙｅｓ）にはＳ５０８を実行し、満たさないとき（Ｓ５０７，Ｎｏ）にはＳ５０５を実行する。Ｓ５０８は、Ｒに含まれた全ての上位レイヤパス１８について、計算したパスの経路に置き換えた場合を想定して、ネットワークコストを計算し、CurrentCostDashとする処理である。
【００８４】
Ｓ５０９は、前記したＳ１０６と同じ処理である。Ｓ５１０は、前記したＳ１０７と同じ処理である。
【００８５】
Ｓ５１１は、分岐条件「全下位レイヤリンク１４について計算が終了」を満たすか否かを判定する処理であり、満たすとき（Ｓ５１１，Ｙｅｓ）にはＳ５１２を実行し、満たさないとき（Ｓ５１１，Ｎｏ）にはＳ５０３を実行する。Ｓ５１２は、前記したＳ１０９と同じ処理である。Ｓ５１３は、前記したＳ１１０と同じ処理である。処理をＳ５０１に戻す。
【００８６】
図８は、経路計算手段２４の処理手順を示している。この処理は、サブルーチン「選択した下位レイヤパス１６を通る上位レイヤパス１８の集合をＲとする（Ｓ６００）」である。
【００８７】
Ｓ６０１は、分岐条件「下位レイヤパス１６の本数が１」を満たすか否かを判定する処理であり、満たすとき（Ｓ６０１，Ｙｅｓ）にはＳ６０２を実行し、満たさないとき（Ｓ６０１，Ｎｏ）にはＳ６０３を実行する。Ｓ６０２は、下位レイヤパス１６を通る全ての上位レイヤパス１８をＲに入れる処理である。処理をサブルーチンの呼び出し元に戻す。
【００８８】
Ｓ６０３は、Ｓを空集合とし、ＲをＮ本の下位レイヤパス１６を通る上位レイヤパス１８の集合とし、上位レイヤパス１８の総数をＴＯＴＡＬとする処理である。
【００８９】
Ｓ６０４は、Ｒに含まれる上位レイヤパス１８の本数をＵとする処理である。Ｓ６０５は、Ｒから１つの上位レイヤパス１８を取り出してＰとする処理である。取り出し方としては、ランダムでもよいし、境界ノード間のトラヒック量上限が最も大きいものでもよい。
【００９０】
Ｓ６０６は、Ｓに含まれる全上位レイヤパスと、Ｓ６０５で選択された１つのパスＰとを収容するのに必要なリンクの帯域を計算する処理である。計算方法としては、既存の方法を用いることができる（特開２００６−５４７２２号公報、リンクリソース計算手段）。Ｓ６０７は、リンクの帯域を収容するのに必要な下位レイヤパス１６の本数を計算し、Ｎｄとする処理である。なお、Ｎｄは、計算したリンクの帯域を、前記リンクの帯域を収容するのに必要な下位レイヤパス１６の帯域で割り、小数点以下を切り上げた値となる。
【００９１】
Ｓ６０８は、分岐条件「Ｎｄ≦Ｎ−１？」を満たすか否かを判定する処理であり、満たすとき（Ｓ６０８，Ｙｅｓ）にはＳ６０９を実行し、満たさないとき（Ｓ６０８，Ｎｏ）にはＳ６１０を実行する。Ｓ６０９は、ＰをＳに入れる処理である。Ｓ６１０は、分岐条件「Ｒは空」を満たすか否かを判定する処理であり、満たすとき（Ｓ６１０，Ｙｅｓ）にはＳ６１１を実行し、満たさないとき（Ｓ６１０，Ｎｏ）にはＳ６０５を実行する。
【００９２】
Ｓ６１１は、ＴＯＴＡＬからＳに含まれる上位レイヤパス１８の本数を引いた値を計算し、Ｕｄとする処理である。Ｓ６１２は、分岐条件「Ｕ＝Ｕｄ」を満たすか否かを判定する処理であり、満たすとき（Ｓ６１２，Ｙｅｓ）には処理をサブルーチンの呼び出し元に戻し、満たさないとき（Ｓ６１２，Ｎｏ）にはＳ６１３を実行する。Ｓ６１３は、Ｓに含まれない全ての上位レイヤパス１８を再びＲに入れる処理である。そして、処理をＳ６０４に戻す。
【００９３】
図９は、経路計算手段２４の処理手順を示している。この処理は、下位レイヤパス単位の経路計算を行い、計算した経路の評価値を元に、Ｈｅｕｒｉｓｔｉｃアルゴリズムにより、置き換える上位レイヤパス１８を決定することを特徴とする。
【００９４】
Ｓ７０１は、サブルーチン「Ｈｅｕｒｉｓｔｉｃアルゴリズムによるパスの選択（Ｓ４００）」のための初期値設定を実行する処理である。具体的には、ｃａ＝０、ｃｒ＝０、ｃｃ＝０、ｃｓ＝０、Ｔ＝Ｔ０（Ｔ０：定数）とする初期化処理を実行する。
【００９５】
Ｓ７０２は、前記したＳ１０１と同じ処理である。Ｓ７０３は、ランダムに下位レイヤパス１６を選択し、その始点ノードをｉ、終点ノードをｊとする処理である。Ｓ７０４は、前記したＳ５０４と同じ処理である。Ｓ７０５は、前記したＳ５０５と同じ処理である。
【００９６】
Ｓ７０６は、サブルーチン「パスの経路計算（Ｓ２００）」を呼び出す処理である。Ｓ７０７は、前記したＳ５０７と同じ処理である。Ｓ７０８は、前記したＳ５０８と同じ処理である。Ｓ７０９は、ｃｃの値を１つ増やす処理である。
【００９７】
Ｓ７１０は、サブルーチン「Ｈｅｕｒｉｓｔｉｃアルゴリズムによるパスの選択（Ｓ４００）」を呼び出す処理である。ただし、Ｓ４０２、Ｓ４０４、Ｓ４０６にて、全経路を置き換えるように処理を修正する。そして、処理をＳ７０２に戻す。
【００９８】
図１０は、経路計算手段２４の処理手順を示している。このフローチャートは、ある上位レイヤノード１０をルートとして選択し、最短経路木を構成するように下位レイヤパス１６を選択した上で、上位レイヤパス１８の経路を選択し、全ての上位レイヤノード１０をルートとして選択した場合の評価値を比較して、最もよい評価値となる経路を置き換える後の経路とすることを特徴とする。
【００９９】
Ｓ８０１は、前記したＳ１０２と同じ処理である。Ｓ８０２は、上位レイヤノード１０を１つ選択する処理である。
【０１００】
Ｓ８０３は、選択した上位レイヤノード１０をルートとして、全ての境界ノードを結ぶように、下位レイヤパス１６をリンクとみなし、最短経路木を作成する処理である。このときの下位レイヤパス１６のリンクコストは、下位レイヤパス１６がとりうる経路のうち、最小コストのもの、で与えられる。また、最短経路木を作成するアルゴリズムとしては、既存のＤｉｊｋｓｔｒａ法などを用いることができる。
【０１０１】
Ｓ８０４は、計算した最短経路木上に、上位レイヤパス１８の経路計算を行う処理である。既存のＤｉｊｋｓｔｒａ法などを用いることができる。なお、上位レイヤパス１８は一意に決定される。
【０１０２】
Ｓ８０５は、ネットワークコスト（評価値）を計算し、計算結果を「CurrentCost」とする処理である。具体的には、各下位レイヤパス１６を通る全ての上位レイヤパス１８を収容するのに必要な下位レイヤパス１６の本数を計算する。そのため、まず、各下位レイヤパス１６を通る全ての上位レイヤパス１８を収容するのに必要な帯域を計算する。
【０１０３】
必要な帯域の計算方法としては、既存の方法を用いることができる（特開２００６−５４７２２号公報、リンクリソース計算手段）。続いて、前記必要な帯域を収容するのに必要な下位レイヤパス１６の本数を求める。この計算方法としては、前記必要な帯域を、下位レイヤパス１６の帯域「LowPathBandwidth」で割り、小数点以下を切り上げた整数を求める。これにより、ネットワークコストを計算できる。
【０１０４】
Ｓ８０６は、分岐条件「CurrentCost＜Minimum」を満たすか否かを判定する処理であり、満たすとき（Ｓ８０６，Ｙｅｓ）にはＳ８０７を実行し、満たさないとき（Ｓ８０６，Ｎｏ）にはＳ８０８を実行する。Ｓ８０７は、Minimumの値をCurrentCostに代入する処理である。Ｓ８０８は、分岐条件「全上位レイヤノード１０を選択」を満たすか否かを判定する処理であり、満たすとき（Ｓ８０８，Ｙｅｓ）にはＳ８０９を実行し、満たさないとき（Ｓ８０８，Ｎｏ）にはＳ８０２を実行する。Ｓ８０９は、Minimumとなった最短経路木および上位レイヤパス１８の経路を解とする処理である。
【図面の簡単な説明】
【０１０５】
【図１】本発明の一実施形態に関するネットワークシステムを示す構成図である。
【図２】本発明の一実施形態に関する網設計装置を示す構成図である。
【図３】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図４】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図５】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図６】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図７】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図８】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図９】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【図１０】本発明の一実施形態に関する経路計算手段の処理手順を示すフローチャートである。
【符号の説明】
【０１０６】
１      網設計装置
１０    上位レイヤノード
１２    下位レイヤノード
１４    下位レイヤリンク
１６    下位レイヤパス
１８    上位レイヤパス
２０    トポロジ管理手段
２２    トラヒック条件管理手段
２４    経路計算手段
２６    トポロジＤＢ
２８    トラヒック条件ＤＢ
３０    パスＤＢ
【図１】
0004630223.tif 000003
【図２】
0004630223.tif 000004
【図３】
0004630223.tif 000005
【図４】
0004630223.tif 000006
【図５】
0004630223.tif 000007
【図６】
0004630223.tif 000008
【図７】
0004630223.tif 000009
【図８】
0004630223.tif 000010
【図９】
0004630223.tif 000011
【図１０】
0004630223.tif 000012