(57)【要約】  ＳＬＡを満足する、適切なコスト・品質の通信ネットワークを設計することができるネットワーク設計システムを提供する。選択手段９２は、変更コスト性能テーブルから一定数のレコード毎にレコードを選択する。親トポロジ検索手段９３は、トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索する。トポロジ導出手段９４は、選択されたレコードのコストに応じたトポロジ群を作成する。性能推定手段９５は、トポロジの通信性能を推定する。トポロジ導出手段９４は、トポロジ群のうち通信性能が最も高いトポロジを、選択されたレコードのトポロジとして登録する。そして、性能推定手段９５は、そのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定する。
2015510281.tif 000002
【特許請求の範囲】
【請求項１】
トポロジ変更量を含む複数のレコードを有するテーブルを記憶する記憶手段と、
前記テーブルから所定のレコードを選択する選択手段と、
前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成するトポロジ導出手段と、
前記トポロジが示す通信ネットワークの通信性能を推定する性能推定手段とを備え、
性能推定手段は、前記トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定し、
選択手段は、前記トポロジの通信性能が前記範囲に属していない場合に、再度、前記テーブルからレコードを選択する
ことを特徴とするネットワーク設計システム。
【請求項２】
初期トポロジからのトポロジ変更量を示すフィールドと、前記トポロジ変更量に応じた変更を前記初期トポロジに施したトポロジを登録可能なフィールドとを含む複数のレコードを有するテーブルを作成するテーブル作成手段と、
トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索する親トポロジ検索手段とを備え、
トポロジ導出手段は、親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成する
請求項１に記載のネットワーク設計システム。
【請求項３】
テーブル作成手段は、初期トポロジからのトポロジ変更に要するコストを各レコードに昇順に並べたテーブルであって、前記コストに応じたトポロジ変更量を示すフィールドと、前記コストに応じたトポロジ変更を前記初期トポロジに施したトポロジを登録可能なフィールドとを含むテーブルを作成し、
選択手段は、前記テーブルから一定数のレコード毎にレコードを選択し、
親トポロジ検索手段は、トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索し、
トポロジ導出手段は、親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択されたレコードのコストに応じたトポロジ群を作成し、
前記トポロジ群のうち前記通信性能が最も高いトポロジを、選択されたレコードのトポロジとして登録する
請求項２に記載のネットワーク設計システム。
【請求項４】
選択されたレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属している場合に、前記トポロジが示す通信ネットワークを特定可能な情報を出力する出力手段を備える
請求項３に記載のネットワーク設計システム。
【請求項５】
選択手段は、
選択したレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲を超過している場合に、前記レコードよりもコストが低いレコードを選択し、前記一定数の値を減少させる
請求項３または請求項４に記載のネットワーク設計システム。
【請求項６】
トポロジ導出手段は、
親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定し、
当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加することで、選択されたレコードのコストに応じたトポロジ群を作成する
請求項３から請求項５のうちいずれか１項に記載のネットワーク設計システム。
【請求項７】
トポロジ導出手段は、
親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定し、
当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加し、
トポロジ変更量を示すフィールドにおいて、ノード間のケーブルの差し替えが規定されている場合に、リンク追加後のトポロジから、リンクを削除すべきノードのペア群を特定し、当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアからリンクを削除することで、選択されたレコードのコストに応じたトポロジ群を作成する
請求項３から請求項５のうちいずれか１項に記載のネットワーク設計システム。
【請求項８】
トポロジ変更量を含む複数のレコードを有するテーブルを記憶し、
前記テーブルから所定のレコードを選択し、
前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成し、
前記トポロジが示す通信ネットワークの通信性能を推定し、
前記トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定し、
前記トポロジの通信性能が前記範囲に属していない場合に、再度、前記テーブルからレコードを選択する
ことを特徴とするネットワーク設計方法。
【請求項９】
初期トポロジからのトポロジ変更量を示すフィールドと、前記トポロジ変更量に応じた変更を前記初期トポロジに施したトポロジを登録可能なフィールドとを含む複数のレコードを有するテーブルを作成し、
トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索し、
親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成する
請求項８に記載のネットワーク設計方法。
【請求項１０】
初期トポロジからのトポロジ変更に要するコストを各レコードに昇順に並べたテーブルであって、前記コストに応じたトポロジ変更量を示すフィールドと、前記コストに応じたトポロジ変更を前記初期トポロジに施したトポロジを登録可能なフィールドとを含むテーブルを作成し、
前記テーブルから一定数のレコード毎にレコードを選択し、
トポロジ変更量が、選択したレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索し、
親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択したレコードのコストに応じたトポロジ群を作成し、前記トポロジ群のうち前記通信性能が最も高いトポロジを、選択されたレコードのトポロジとして登録する
請求項９に記載のネットワーク設計方法。
【請求項１１】
選択したレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属している場合に、前記トポロジが示す通信ネットワークを特定可能な情報を出力する
請求項１０に記載のネットワーク設計方法。
【請求項１２】
選択したレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲を超過している場合に、前記レコードよりもコストが低いレコードを選択し、前記一定数の値を減少させる
請求項１０または請求項１１に記載のネットワーク設計方法。
【請求項１３】
親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定し、
当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加することで、選択されたレコードのコストに応じたトポロジ群を作成する
請求項１０から請求項１２のうちのいずれか１項に記載のネットワーク設計方法。
【請求項１４】
親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定し、
当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加し、
トポロジ変更量を示すフィールドにおいて、ノード間のケーブルの差し替えが規定されている場合に、リンク追加後のトポロジから、リンクを削除すべきノードのペア群を特定し、当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアからリンクを削除することで、選択されたレコードのコストに応じたトポロジ群を作成する
請求項１０から請求項１２のうちのいずれか１項に記載のネットワーク設計方法。
【請求項１５】
コンピュータに、
トポロジ変更量を含む複数のレコードを有するテーブルを記憶する記憶処理、
前記テーブルから所定のレコードを選択する選択処理、
前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成するトポロジ導出処理、
トポロジが示す通信ネットワークの通信性能を推定する性能推定処理、および、
前記トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定する性能評価処理を実行させ、
前記トポロジの通信性能が前記範囲に属していない場合に、選択処理で次のレコードを選択させる
ためのネットワーク設計プログラム。
【請求項１６】
コンピュータに、
初期トポロジからのトポロジ変更量を示すフィールドと、前記トポロジ変更量に応じた変更を前記初期トポロジに施したトポロジを登録可能なフィールドとを含む複数のレコードを有するテーブルを作成するテーブル作成処理、
トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索する親トポロジ検索処理を実行させ、
トポロジ導出処理で、
親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成させる
請求項１５に記載のネットワーク設計プログラム。
【請求項１７】
コンピュータに、
初期トポロジからのトポロジ変更に要するコストを各レコードに昇順に並べたテーブルであって、前記コストに応じたトポロジ変更量を示すフィールドと、前記コストに応じたトポロジ変更を前記初期トポロジに施したトポロジを登録可能なフィールドとを含むテーブルを作成するテーブル作成処理を実行させ、
選択処理で、前記テーブルから一定数のレコード毎にレコードを選択させ、
親トポロジ検索処理で、
トポロジ変更量が、選択したレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索させ、
トポロジ導出処理で、
親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択したレコードのコストに応じたトポロジ群を作成させ、
前記トポロジ群のうち前記通信性能が最も高いトポロジを、選択したレコードのトポロジとして登録させる
請求項１６に記載のネットワーク設計プログラム。
【請求項１８】
コンピュータに、
選択したレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属している場合に、前記トポロジが示す通信ネットワークを特定可能な情報を出力する出力処理を実行させる
請求項１７に記載のネットワーク設計プログラム。
【請求項１９】
コンピュータに、
選択したレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲を超過している場合に、選択処理で、前記レコードよりもコストが低いレコードを次のレコードとして選択させ、前記一定数の値を減少させる
請求項１７または請求項１８に記載のネットワーク設計プログラム。
【請求項２０】
コンピュータに、
トポロジ導出処理で、
親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定する特定処理、および、
当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加することで、選択されたレコードのコストに応じたトポロジ群を作成する追加処理
を実行させる請求項１７から請求項１９のうちのいずれか１項に記載のネットワーク設計プログラム。
【請求項２１】
コンピュータに、
トポロジ導出処理で、
親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定する特定処理、
当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加する追加処理、
トポロジ変更量を示すフィールドにおいて、ノード間のケーブルの差し替えが規定されている場合に、リンク追加後のトポロジから、リンクを削除すべきノードのペア群を特定し、当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアからリンクを削除することで、選択されたレコードのコストに応じたトポロジ群を作成する削除処理
を実行させる請求項１７から請求項１９のうちのいずれか１項に記載のネットワーク設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＳＬＡ（Service Level Agreement ）を満足する通信ネットワークを設計するネットワーク設計システム、ネットワーク設計方法およびネットワーク設計プログラムに関する。
【背景技術】
【０００２】
ＳＬＡを満足する通信ネットワークの設計が求められている。
【０００３】
また、ネットワーク設計方法として、将来のトラヒック予測に基づいて通信ネットワークを設計する方法が特許文献１に記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−６６１４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
将来のトラヒック予測に基づいて、ＳＬＡを満足する通信ネットワークを設計することが考えられる。しかし、この場合、ＳＬＡを満足させるために将来のトラヒック量を多めに見積もる傾向が生じる。すると、通信ネットワークの構築に要するコストを高めに設定することになる。その結果、ＳＬＡを満足するが、通信ネットワークの構築に要するコストが高くなり、通信性能も必要以上に高い通信ネットワークが設計されることになる。すなわち、将来のトラヒック予測に基づいて通信ネットワークを設計する場合、過大投資により過剰品質の通信ネットワークを設計することになる。
【０００６】
本発明は、ＳＬＡを満足する、適切なコスト・品質の通信ネットワークを設計することができるネットワーク設計システム、ネットワーク設計方法およびネットワーク設計プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明によるネットワーク設計システムは、トポロジ変更量を含む複数のレコードを有するテーブルを記憶する記憶手段と、前記テーブルから所定のレコードを選択する選択手段と、前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成するトポロジ導出手段と、前記トポロジが示す通信ネットワークの通信性能を推定する性能推定手段とを備え、性能推定手段は、前記トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定し、選択手段は、前記トポロジの通信性能が前記範囲に属していない場合に、再度、前記テーブルからレコードを選択することを特徴とする。
【０００８】
また、本発明によるネットワーク設計方法は、トポロジ変更量を含む複数のレコードを有するテーブルを記憶し、前記テーブルから所定のレコードを選択し、前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成し、前記トポロジが示す通信ネットワークの通信性能を推定し、前記トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定し、前記トポロジの通信性能が前記範囲に属していない場合に、再度、前記テーブルからレコードを選択することを特徴とする。
【０００９】
また、本発明によるネットワーク設計プログラムは、コンピュータに、トポロジ変更量を含む複数のレコードを有するテーブルを記憶する記憶処理、前記テーブルから所定のレコードを選択する選択処理、前記選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成するトポロジ導出処理、トポロジが示す通信ネットワークの通信性能を推定する性能推定処理、および、前記トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定する性能評価処理を実行させ、前記トポロジの通信性能が前記範囲に属していない場合に、選択処理で次のレコードを選択させることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、ＳＬＡを満足する、適切なコスト・品質の通信ネットワークを設計することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明のネットワーク設計システムの処理を示す概念図である。
【図２】変更コスト性能テーブルの例を示す説明図である。
【図３】通信ネットワークの例を示す模式図である。
【図４】転送確率の例を示す模式図である。
【図５】リンク利用率の例を表す模式図である。
【図６】本発明のネットワーク設計システムの例を示すブロック図である。
【図７】性能評価手段２０の構成例を示すブロック図である。
【図８】本実施形態の処理経過の例を示すフローチャートである。
【図９】ステップＡ２の処理経過の例を示すフローチャートである。
【図１０】ステップＡ６，Ａ７の処理経過の例を示すフローチャートである。
【図１１】ステップＣ１の処理経過の例を示すフローチャートである。
【図１２】ステップＣ５の処理経過の例を示すフローチャートである。
【図１３】本発明の実施形態の変形例を示すブロック図である。
【図１４】本発明の概要を示すブロック図である。
【図１５】本発明の概要を示すブロック図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態を図面を参照して説明する。本発明は、ＭＬＢ（Multinomial Logit Based ）ルーティングを行う通信ネットワークの設計に適用される。ＭＬＢルーティングは、個々のノードが、次にどのノードにトラヒックを転送するのかを各リンクに定められた転送確率に従って決定するルーティング方式である。
【００１３】
図１は、本発明のネットワーク設計システムの処理を示す概念図である。本発明では、初期トポロジが与えられる。図１の横軸は、初期トポロジからのトポロジ変更に要するコストを表している。また、図１の縦軸は、通信ネットワークの通信性能を表している。トポロジ変更に要するコストの例として、例えば、ノードとなるスイッチの追加に要するコストや、ノード間のケーブルの追加、削除、変更（別の場所へのケーブルの差し替え）に要するコスト等が挙げられる。ＣＡＰＥＸ（設備投資）だけでなく、人件費等のＯＰＥＸもコストとする。例えば、ケーブルを１本差し替える場合、ケーブルを購入する必要はないのでＣＡＰＥＸは生じないが、ケーブル差し替えに要する人件費が生じる。
【００１４】
本発明のネットワーク設計システム（以下、単にネットワーク設計システムと記す。）は、トポロジの変更に要するコストを上昇させたときのトポロジ候補を導出し、それらのトポロジ候補のうち、通信性能が最高のトポロジを選択する。図１に示す例では、ネットワーク設計システムは、コストＶ１で初期トポロジを変更して得られるトポロジ候補の中から、通信性能が最高のトポロジＱ１を選択する。選択したトポロジの通信性能が、予め定められたＳＬＡの下限に達していなければ、ネットワーク設計システムは、さらにコストを上昇させたときのトポロジ候補を、選択済みのトポロジまたは初期トポロジから導出し、それらのトポロジ候補のうち、通信性能が最高のトポロジを選択することを繰り返す。図１に示す例では、トポロジＱ１の通信性能がＳＬＡの下限に達していないので、ネットワーク設計システムがコストＶ２におけるトポロジ候補をトポロジＱ１から導出する場合を示している。
【００１５】
また、選択したトポロジの通信性能が、予め定められたＳＬＡの上限を越えているということは、通信性能が過剰品質になっているということである。この場合、ネットワーク設計システムは、コストを下げた状態におけるトポロジから、コストを上昇させたときのトポロジ候補を導出し、それらのトポロジ候補のうち、通信性能が最高のものを選ぶことを繰り返す。ただし、このとき、コストを上昇させる際に、より細かにコストを上昇させる。例えば、図１に示す例において、トポロジＱ２の通信性能がＳＬＡの上限よりも高い。この場合、ネットワーク設計システムは、コストの上昇幅をより小さくして、例えば、トポロジ候補Ｑ１に変更を加えた場合のトポロジ候補を導出すればよい。
【００１６】
以上のような処理において、選択したトポロジの通信性能がＳＬＡの下限から上限までの範囲に収まっていれば、ネットワーク設計システムは、そのトポロジが表す通信ネットワークが最適なコストおよび最適な通信品質の通信ネットワークであると判定する。
【００１７】
なお、図１に示すＸについては、後述の図２とともに説明する。
【００１８】
ノード同士を結ぶケーブルには単価がある。また、ケーブルの抜き差しに要する人件費にも、１つの作業当たりの単価がある。従って、トポロジ変更に要するコストは離散的に変化する。このようなコストを昇順に並べたテーブルを変更コスト性能テーブルと記す。変更コスト性能テーブルには、トポロジを表す情報を示すフィールドおよびそのトポロジの通信性能を示すフィールドも含まれる。ただし、全てのコストに対してトポロジや通信性能が導出されなくてもよい。
【００１９】
図２は、変更コスト性能テーブルの例を示す説明図である。図２に示す変更コスト性能テーブルは、コスト識別番号、スイッチ追加数、新規ケーブル追加数、ケーブル変更数、コスト、性能、トポロジを表す各フィールドを含む。以下、コスト識別番号を変数“ｍ”で表す。スイッチ追加数を変数“ａ”で表す。新規ケーブル追加数を変数“ｂ”で表す。ケーブル変更数を変数“ｃ”で表す。ただし、ａは、初期トポロジに対するスイッチの追加数である。ｂは、初期トポロジに対するケーブルの追加数である。また、ｃは、初期トポロジに対するケーブルの変更数である。変更コスト性能テーブルに登録されているコストは、初期トポロジからのトポロジ変更に要するコストである。図２に例示する個々のレコード（行）は、ａ，ｂ，ｃに応じたコストを示している。各行のコストＶは、以下の式（１）で表される。
【００２０】
Ｖ＝Ｓａ＋Ｌｂ＋Ｃ（ｂ＋２ｃ）          式（１）
【００２１】
式（１）においてＳは、スイッチ１台の価格である。ただし、本実施形態では、トポロジ変更の際、スイッチの追加は行わないものとする。従って、ａ＝０であるものとする。また、Ｌは１本のケーブルの価格であり、本実施形態では、Ｌ＝１０００円であるものとする。また、Ｃは、１本のケーブルを一対のノードから抜く作業１回分のコスト、および、１本のケーブルを一対のノードに挿す作業１回分のコストであり、本実施形態ではＣ＝３００円であるとする。
【００２２】
例えば、図２に示すｍ＝１の行のように、ａ＝ｂ＝０，ｃ＝１である場合、Ｖ＝２Ｃ＝６００円となる。ｃ＝１であると言うことは、１本のケーブルの場所を変更するということであり、１本のケーブルをノードから抜く作業と、そのケーブルを新たに他のノードに挿す作業とがそれぞれ発生する。従って、上記のように、ケーブル変更数“１”を２倍した値に作業単価のＣ（３００円）を乗じた値がコストとなる。
【００２３】
同様に、図２に示すｍ＝２の行のように、ａ＝ｂ＝０，ｃ＝２である場合、コストはＶ＝４Ｃ＝１２００円となる。
【００２４】
また、図２に示すｍ＝３の行のように、ａ＝ｃ＝０、ｂ＝１の場合、コストはＶ＝Ｌ＋Ｃ＝１３００円となる。すなわち、ｂ＝１の場合、新たに１本のケーブルを用意し、そのケーブルをノードに挿す作業が発生する。従って、新規の１本分のケーブルの価格と、１回分の作業単価の和がコストとなる。
【００２５】
このように、ａ，ｂ，ｃの値を式（１）に代入することよって、ａ，ｂ，ｃの値に応じたコストを算出することができる。
【００２６】
また、ａ＝ｂ＝ｃ＝０は、初期トポロジに変更を加えないということであり、初期トポロジ自体を表す。
【００２７】
ｍは、個々の行（換言すれば、個々のコスト）を識別するための番号である。具体的には、ｂ，ｃをそれぞれ変化させた場合の各コストを昇順にならべたときに、最初の行から０，１，２，・・・の順に各行に割り当てた値である（図２参照）。なお、前述のように、本実施形態では、トポロジ変更の際、スイッチの追加は行わないものとし、ａ＝０とする。この場合、変更コスト性能テーブルにおいて“ａ”のフィールドが設けられていなくてもよい。
【００２８】
ネットワーク設計システムは、変更コスト性能テーブルにおいてＸ行毎に行を選択し、その行が示すａ，ｂ，ｃの値に応じてトポロジ候補を導出する。図１に示すＸは、変更コスト性能テーブルにおいてＸ行毎に行を選択することを表している。
【００２９】
また、選択したトポロジの通信性能がＳＬＡの上限を越える場合、ネットワーク設計システムは、Ｘの値をＸ／ｔで更新してからＸ行毎に行を選択する。ここで、ｔはＸより小さな２以上の整数である。このことは、更新前のＸの値を用いてＸ行毎に行を選択する場合よりも、細かに行を選択していくことを意味する。
【００３０】
変更コスト性能テーブルのトポロジのフィールドには、ａ，ｂ，ｃで規定されるコストに応じたトポロジ候補のうち、通信性能が最も高いトポロジが登録される。また、変更コスト性能テーブルの性能のフィールドには、そのトポロジの通信性能が登録される。
【００３１】
次に、本実施形態で用いられる各データの例について説明する。
本実施形態では、トポロジを、行列で表す場合を例にして説明する。この行列をトポロジ行列と記すことにする。通信ネットワーク内のノードの数をｎとすると、トポロジ行列はｎ行ｎ列の行列で表すことができる。本実施形態では、ノードとなるスイッチの追加を行わないので、ノード数はｎ個で一定であるものとする。トポロジ行列の任意のｉ行ｊ列の要素をＮｏｕｔｉｊと記すこととする。個々の行および個々の列は、それぞれ個々のノードに一対一に対応する。そして、トポロジ行列の要素は、その要素が存在する行および列によって特定される２つのノード間のリンクの有無を表す。例えば、ノードｉとノードｊとの間にリンクが存在している場合、トポロジ行列のｉ行ｊ列の要素Ｎｏｕｔｉｊ、およびｊ行ｉ列の要素Ｎｏｕｔｊｉは、定数Ｅとする。また、ノードｉとノードｊとの間にリンクが存在しない場合、ＮｏｕｔｉｊおよびＮｏｕｔｊｉは、いずれも０であるとする。すなわち、トポロジ行列において、以下の式（２）が成立する。なお、リンクは、全２重リンクであるものとする。
【００３２】
【数１】
2015510281.tif 000003
【００３３】
ただし、１つのノードに着目した場合、そのノードの使用可能なポート数を超える数のリンクを他のノードとの間に設けることができない。従って、任意のノードｉの使用可能なポート数をＰｏｒｔｉとすると、トポロジ行列において、そのノードに対応する第ｉ行に関し、以下の式（３）が成立する。
【００３４】
【数２】
2015510281.tif 000004
【００３５】
また、本実施形態では、通信ネットワークにおける個々のＯＤペア（Origin and Destination pair ）での単位時間当たりのトラヒック発生量を行列で表す。この行列をトラヒック行列と記す。ＯＤペアとは、通信ネットワーク内のノードのうち、トラヒックの送信元ノードと、トラヒックの宛先ノードの組み合わせである。通信ネットワーク内のノードの数をｎとすると、トラヒック行列もｎ行ｎ列の行列として表される。トラヒック行列における行および列のいずれか一方が送信元ノードを表し、他方が宛先ノードを表す。以下、行が送信元ノードを表し、列が宛先ノードを表す場合を例にして説明する。トラヒック行列の個々の要素は、その要素が存在する行および列によって特定されるＯＤペアでの単位時間当たりのトラヒック発生量である。すなわち、トラヒック行列における任意のｉ行ｊ列の要素をＴｉｊとすると、Ｔｉｊは、送信元ノードｉから宛先ノードｊへの単位時間当たりのトラヒック発生量である。
【００３６】
図３は、通信ネットワークの例を示す模式図である。図３に示す例では、ノードが６個存在し、各ノードを“１”から“６”の番号で識別するものする。この場合、トラヒック行列は６行６列の行列で表される。例えば、ノード１を送信元ノードとし、ノード６を宛先ノードとするＯＤペアにおける単位時間当たりのトラヒック発生量が１００Ｍｂｐｓである場合、Ｔ１６＝１００とすればよい。同様に、ノード２を送信元ノードとし、ノード３を宛先ノードとするＯＤペアにおける単位時間当たりのトラヒック発生量が１０Ｍｂｐｓである場合、Ｔ２３＝１０とすればよい。このように、個々のＯＤペア毎の単位時間当たりのトラヒック発生量をトラヒック行列の要素として定めればよい。また、トラヒックが生じないＯＤペアに対応する要素の値は０として定めればよい。また、トラヒック行列の対角要素も０として定めればよい。
【００３７】
また、本発明では、転送確率を用いる。転送確率は、ＯＤペアにおける送信元ノードから宛先ノードに送られるトラヒックが個々のリンクを通過する確率である。転送確率は、それぞれのＯＤペアについて、リンク毎に予め定められる。送信元ノードを変数ｏで表し、宛先ノードを変数ｄで表す。この場合、送信元ノードｏと宛先ノードｄのＯＤペアにおける、ノードｉからノードｊへのリンクの転送確率をｐｏｄｉｊと表すこととする。
【００３８】
図４は、転送確率の例を示す模式図である。図４では、ノード１を送信元ノードとし、ノード６を宛先ノードとするＯＤペア（以下、ＯＤペア１６と記す。）の転送確率を括弧を付さずに示している。また、ノード２を送信元ノードとし、ノード３を宛先ノードとするＯＤペア（以下、ＯＤペア２３と記す。）転送確率を括弧を付して示している。また、ノードｉからノードｊへのリンクをＬｉｊと記す。図４に示す例では、例えば、ＯＤペア１６について、リンクＬ１２の転送確率ｐ１６１２は６０％であり、リンクＬ１４の転送確率ｐ１６１４は４０％であり、リンクＬ２３の転送確率ｐ１６２３は３５％である（図４参照）。また、ＯＤペア２３について、リンクＬ２３の転送確率ｐ２３２３は８０％であり、リンクＬ２５の転送確率ｐ２３２５は２０％であり、リンクＬ５３の転送確率ｐ２３５３は２０％である。なお、図４では、１つのＯＤペアに関して、全てのリンクの転送確率を示しているわけではなく、一部の転送確率については図示を省略している。例えば、ノード４からノード２へのリンクＬ４２の転送確率は図４で示しているが、その逆向きのリンクＬ２４の転送確率の図示は省略している。
【００３９】
なお、２つのノード間のリンクは、トラヒックの流れる向きによって区別される。すなわち、その２つのノードのどちらが始点になるかによって区別される。
【００４０】
図４の説明では、ＯＤペア１６およびＯＤペア２３に着目して転送確率の例を示したが、本発明は、全てのＯＤペアについての転送確率を算出する。
【００４１】
また、ＯＤペア毎に決定した各リンクの転送確率は行列の形式で表せばよい。以下、この行列を転送確率行列と記す。転送確率行列において、行および列のいずれか一方がリンクの始点となるノードを表し、他方がリンクの終点を表す。以下、行がリンクの始点を表し、列がリンクの終点を表す場合を例にして説明する。通信ネットワーク内のノード数をｎとした場合、転送確率行列もｎ行ｎ列の行列として表される。そして、任意のリンクＬｉｊの転送確率を、転送確率行列におけるｉ行ｊ列の要素として表現すればよい。
【００４２】
転送確率行列は、ＯＤペア毎に算出される。任意のＯＤペアｏｄに対応する転送確率行列をＦｗｏｄと記す。そして、そのＯＤペアｏｄに関して算出した個々のリンクの転送確率をＦｗｏｄの各要素として表現すればよい。ＯＤペアｏｄに関して算出したリンクＬｉｊの転送確率ｐｏｄｉｊは、転送確率行列Ｆｗｏｄにおけるｉ行ｊ列の要素である。なお、任意のＯＤペアにおける転送確率行列の対角要素は０とする。
【００４３】
また、本発明では、リンク利用率を用いる。リンク利用率は、リンクの帯域に対するその帯域の使用分の割合であり、リンクを通過するトラヒック量をそのリンクの帯域で除算することで得られる。すなわち、リンクの帯域に対する、そのリンクを通過するトラヒック量の割合であると言うことができる。なお、本発明では、各リンクの帯域は共通であるものと仮定する。すなわち、新たにリンクを追加した場合に、そのリンクの帯域は他の各リンクの帯域と共通であるものとする。
【００４４】
図４に例示するように転送確率が定められている場合におけるリンク利用率の具体例を示す。ただし、ここでは説明を簡単にするために、図４に示す例において、ＯＤペア１６およびＯＤペア２３以外のＯＤペアについては、単位時間当たりのトラヒック発生量が０Ｍｂｐｓであるものとする。また、ＯＤペア１６における単位時間当たりのトラヒック発生量は１００Ｍｂｐｓであり、ＯＤペア２３における単位時間当たりのトラヒック発生量は１０Ｍｂｐｓであるものとする。さらに、全てのリンクの帯域は１Ｇｂｐｓであるものとする。
【００４５】
リンクＬ２３に着目すると、ＯＤペア１６に関してリンクＬ２３の転送確率ｐ１６２３は３５％である（図４参照）。従って、ＯＤペア１６で生じるトラヒックのうち、リンクＬ２３を通過するトラヒックは１００Ｍｂｐｓの３５％＝３５Ｍｂｐｓである。同様に、ＯＤペア２３に関してリンクＬ２３の転送確率ｐ２３２３は８０％である（図４参照）。従って、ＯＤペア２３で生じるトラヒックのうち、リンクＬ２３を通過するトラヒックは１０Ｍｂｐｓの８０％＝８Ｍｂｐｓである。従って、リンクＬ２３を通過するトラヒックは４３Ｍｂｐｓである。リンクＬ２３の帯域は１Ｇｂｐｓであるので、リンクＬ２３のリンク利用率は４．３％となる。図５は、同様に算出したリンク利用率の例を表す模式図である。図５において、矩形で囲んで示した値が、リンク利用率である。以下、任意のリンクＬｉｊのリンク利用率をutilijと記す。
【００４６】
また、本発明では、抵抗行列を用いる。抵抗行列は、各リンクの効用を要素として持つ行列である。リンクの効用は、換言すれば、そのリンクを用いることによる通信性能向上への貢献度ということができる。本実施形態では、リンク利用率の低いほど（すなわち、空いているリンクほど）効用が高いという基準に基づいて、効用の値を定める場合を例にする。ただし、効用を定める基準は、リンク利用率に限定されず、例えば、ノード間の距離が近いリンクほど効用が高いという基準に基づいて効用の値を定めてもよい。
【００４７】
抵抗行列において、行および列のいずれか一方がリンクの始点となるノードを表し、他方がリンクの終点を表す。以下、行がリンクの始点を表し、列がリンクの終点を表す場合を例にして説明する。通信ネットワーク内のノード数をｎとした場合、抵抗行列もｎ行ｎ列の行列として表される。
【００４８】
抵抗行列の任意の要素ａｉｊは、以下のように算出することができる。すなわち、ノードｉ，ｊ間にリンクＬｉｊが存在する場合、リンクＬｉｊの効用ａｉｊは、以下に示す式（４）によって算出することができる。ただし、式（４）におけるＨおよびＢの値は、予め定数として定めておけばよい。
【００４９】
【数３】
2015510281.tif 000005
【００５０】
また、ノードｉ，ｊ間にリンクＬｉｊが存在しない場合には、リンクＬｉｊの効用の値は、ａｉｊ＝０とする。このように、各ノード間に関して、リンクの有無、およびリンクがある場合におけるそのリンクの利用率を用いて各リンクの効用を算出し、それらの効用を要素とする行列を定めることで抵抗行列が得られる。リンクＬｉｊについて求めた効用の値は、抵抗行列のｉ行ｊ列の要素とすればよい。なお、抵抗行列の対角要素は０である。
【００５１】
また、本発明では、重み行列を用いる。重み行列は、任意の２つのノードの一方を始点とし、他方を終点としたときに、始点から終点までのトラヒックの辿り着き易さを表す値を要素として持つ行列である。抵抗行列において、行および列のいずれか一方が始点となるノードを表し、他方が終点となるノードを表す。以下、行が始点となるノードを表し、列が終点となるノードを表す場合を例にして説明する。通信ネットワーク内のノード数をｎとした場合、抵抗行列もｎ行ｎ列の行列として表される。重み行列をＷと表し、上記の抵抗行列をＡと表すと、重み行列Ｗは、以下の式（５）で表すことができる。
【００５２】
Ｗ＝（Ｉ−Ａ）−１−Ｉ          式（５）
【００５３】
ただし、式（５）において、Ｉは単位行列である。
【００５４】
重み行列Ｗのｉ行ｊ列の要素をｗｉｊと表す。ｗｉｊは、ノードｉからノードｊへのトラヒックの辿り着き易さを表す値である。また、前述のように、抵抗行列Ａのｉ行ｊ列の要素をａｉｊと表す。
【００５５】
抵抗行列Ａおよび重み行列Ｗから、任意のＯＤペアｏｄおよび任意のリンクＬｉｊに応じた各転送確率ｐｏｄｉｊを求めることができる。この場合、任意の転送確率ｐｏｄｉｊは、以下の式（６）によって算出することができる。
【００５６】
【数４】
2015510281.tif 000006
【００５７】
また、任意のＯＤペアｏｄにおいて、送信元ノードｏから宛先ノードｄまでトラヒックを送信する場合、任意のノードｉを使用する確率（ｐｏｄｉと記す。）は、以下の式（７）によって算出することができる。
【００５８】
【数５】
2015510281.tif 000007
【００５９】
なお、本実施形態で用いられる各データは、前述のトポロジ行列、トラヒック行列、転送確率行列、リンク利用率、抵抗行列、重み行列に限定されるわけではない。他のデータについては、適宜、本発明の説明とともに適宜説明する。
【００６０】
図６は、本発明のネットワーク設計システムの例を示すブロック図である。本発明のネットワーク設計システム１は、ネットワーク再設計手段１０と、性能評価手段２０とを備える。ネットワーク再設計手段１０は、テーブル管理手段１１と、テーブル記憶手段１２と、親トポロジ検索手段１３と、トポロジ導出手段１４とを含む。さらに、トポロジ導出手段１４は、トポロジ作成手段１５と、リンク追加ペア算出手段１６と、リンク削除ペア算出手段１７とを有する。
【００６１】
ネットワーク再設計手段１０は、初期トポロジに基づいて、ＳＬＡを満足する適切なコスト・品質の通信ネットワークを特定する。
【００６２】
テーブル管理手段１１は、変更コスト性能テーブルを作成する。そして、テーブル管理手段１１は、変更コスト性能テーブルの行（レコード）を選択する。テーブル管理手段１１が選択した変更コスト性能テーブルの行を、以下、選択行と記す。
【００６３】
テーブル記憶手段１２は、変更コスト性能テーブルを記憶する記憶装置である。
【００６４】
親トポロジ検索手段１３は、選択行に対する親トポロジを検索する。親トポロジとは、ａの値が選択行のａの値と等しく、ｂの値が選択行のｂの値以下であり、ｃの値も選択行のｃの値以下である行のうち、トポロジ候補が算出され、そのトポロジ候補の中から性能が最高のトポロジが特定された行であって、選択行に最も近い行に対応するトポロジである。
【００６５】
例えば、図２に示す例において、ｍ＝３，ｍ＝４の行に関して、それぞれ、複数のトポロジ候補が算出されていて、性能が最高となるトポロジが特定されているとする。そして、ｍ＝５の行が選択行であるとする。ｍ＝５の行とｍ＝４の行とでａ，ｂ，ｃを比較すると、ａは等しい。また、ｍ＝４の行のｂの値は、ｍ＝５の行のｂの値よりも小さい。しかし、ｍ＝４の行のｃの値は、ｍ＝５の行のｃの値よりも大きい。従って、ｍ＝４の行に関して特定されたトポロジは、ｍ＝５の行の親トポロジにはならない。
【００６６】
一方、ｍ＝５の行とｍ＝３の行とでａ，ｂ，ｃを比較すると、ａの値は等しい。また、ｍ＝３の行のｂの値は、ｍ＝５の行のｂの値と等しく、ｍ＝３の行のｃの値は、ｍ＝５の行のｃの値よりも小さい。また、ｍ＝３の行に関しては、トポロジが特定されている。従って、ｍ＝３の行は、ａの値が選択行のａの値と等しく、ｂの値が選択行のｂの値以下であり、ｃの値も選択行のｃの値以下である行のうち、トポロジ候補が算出され、そのトポロジ候補の中から性能が最高のトポロジが特定された行であって、選択行に最も近い行に該当する。よって、ｍ＝５の行が選択行である場合、ｍ＝３の行に関して定められたトポロジが親トポロジとなる。なお、ａの値が選択行のａの値と等しく、ｂの値が選択行のｂの値以下であり、ｃの値も選択行のｃの値以下である行であって、トポロジが特定されている行が、ｍ＝１，２の行の中に存在していても、ｍ＝３の行の方が選択行に近い。よって、本例において、ｍ＝１やｍ＝２の行のトポロジは親トポロジにならない。
【００６７】
トポロジ導出手段１４は、親トポロジまたは初期トポロジに基づいて、選択行のコストに応じたトポロジ候補を作成し、そのトポロジ候補の中から最も通信性能が高いトポロジを特定する。
【００６８】
リンク追加ペア算出手段１６は、親トポロジまたは初期トポロジにおいてリンクを追加するノードのペアを算出する。
【００６９】
リンク削除ペア算出手段１７は、リンク追加ペア算出手段１６が算出したノードのペアにリンクを追加したトポロジの中から、リンクを削除するノードのペア群を算出する。
【００７０】
トポロジ作成手段１５は、親トポロジまたは初期トポロジに対して、リンク追加ペア算出手段１６が算出したノードのペアにリンクを追加したり、また、そのリンク追加後のトポロジから、リンク削除ペア算出手段１７算出したペアのリンクを削除したりすることによって、新たなトポロジ候補を作成する。さらに、そのトポロジ候補の中から通信性能が最も高いトポロジを特定する。
【００７１】
性能評価手段２０は、トポロジの抵抗行列および重み行列を算出する。また、性能評価手段２０は、トポロジ導出手段１４に指定されたトポロジの通信性能を推定する。また、トポロジ導出手段１４に指定されたトポロジがＳＬＡを満たしているか否かを判定する。
【００７２】
図７は、性能評価手段２０の構成例を示すブロック図である。性能評価手段２０は、抵抗行列算出手段２１と、重み行列算出手段２２と、転送確率行列算出手段２３と、リンク利用率算出手段２４と、性能推定手段２５と、ＳＬＡ判定手段２９とを備える。
【００７３】
抵抗行列算出手段２１は、リンク利用率を用いて、抵抗行列を算出する。ただし、リンク利用率が求められていない場合には、全てのリンクのリンク利用率を０として抵抗行列を算出する。
【００７４】
重み行列算出手段２２は、抵抗行列Ａを用いて重み行列を算出する。
【００７５】
転送確率行列算出手段２３は、抵抗行列および重み行列を用いて、個々のＯＤペアについてそれぞれ転送確率行列を算出する。
【００７６】
リンク利用率算出手段２４は、トラヒック行列、各ＯＤペアの転送確率行列および各リンクの帯域に基づいて、リンク毎にリンク利用率を算出する。
【００７７】
性能推定手段２５は、リンク利用率に基づいて個々のＯＤペアの通信性能を推定する。ただし、通信性能の項目のうち、リンク利用率を用いずに推定されるものがあってもよい。本実施形態では、性能推定手段２５は、遅延算出手段２６と、ロス率算出手段２７と、スループット算出手段２８とを備える。そして、性能推定手段２５は、通信性能として、平均遅延、トラヒックの平均ロス率、およびスループットを推定する。以下の説明では、トラヒックの平均ロス率を単に平均ロス率と記す。
【００７８】
遅延算出手段２６は、リンク利用率、転送確率、各リンクの帯域、各ノードのバッファ容量を用いて、個々のＯＤペアの平均遅延を推定する。
【００７９】
ロス率算出手段２７は、リンク利用率、転送確率、各ノードのバッファ容量を用いて、個々のＯＤペアの平均ロス率を推定する。
【００８０】
スループット算出手段２８は、要求スループットと転送確率とを用いて、各リンクのスループットを推定する。要求スループットは、送信元ノードから宛先ノードに対して最低限流すことができなければならないトラヒック量であり、ＯＤペア毎に定められている。
【００８１】
ＳＬＡ判定手段２９は、その各通信性能（平均遅延、平均ロス率、スループット）がＳＬＡを満たしているか否かを判定する。
【００８２】
テーブル管理手段１１、親トポロジ検索手段１３、トポロジ導出手段１４（トポロジ作成手段１５、リンク追加ペア算出手段１６、リンク削除ペア算出手段１７）、抵抗行列算出手段２１、重み行列算出手段２２、転送確率行列算出手段２３、リンク利用率算出手段２４、性能推定手段２５（遅延算出手段２６、ロス率算出手段２７、スループット算出手段２８）、およびＳＬＡ判定手段２９は、例えば、ネットワーク設計プログラムに従って動作するコンピュータのＣＰＵによって実現される。この場合、ＣＰＵがネットワーク設計プログラムを読み込み、そのプログラムに従って、上記の各手段として動作すればよい。ネットワーク設計プログラムは、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。また、上記の各手段が別々のハードウェアによって実現されていてもよい。
【００８３】
次に、動作について説明する。図８は、本実施形態の処理経過の例を示すフローチャートである。
【００８４】
最初に、初期入力として、初期トポロジ、トラヒック行列、リンクの帯域および各ノードのバッファ容量、各ＯＤペアに定められている要求スループット、ＳＬＡを満たす通信性能の範囲がネットワーク設計システムに入力される（ステップＡ１）。ＳＬＡを満たす通信性能の範囲（以下、ＳＬＡの範囲と記す。）は、例えば、ＯＤペアの通信遅延、ＯＤペアのトラヒックの平均ロス率（以下、単に平均ロス率と記す。）、リンクのスループット等の性能の項目毎に定められる。本実施形態では、これらの３項目についてＳＬＡの範囲が定められているものとする。ＳＬＡの範囲よりも通信性能が低ければ、ＳＬＡを満足していないことになる。また、ＳＬＡの範囲よりも通信性能が超過していれば、過剰性能となっていることになる。
【００８５】
なお、初期トポロジは、トポロジ行列で表される。初期トポロジ以外のトポロジに関しても同様である。
【００８６】
続いて、性能評価手段２０は、初期トポロジの通信性能を推定し、その通信性能がＳＬＡの範囲に収まっているか、ＳＬＡの範囲よりも高いか、あるいは、ＳＬＡの範囲よりも低いかを判定する（ステップＡ２）。
【００８７】
図９は、ステップＡ２の処理経過の例を示すフローチャートである。まず、抵抗行列算出手段２１は、ステップＡ２の判定対象となるトポロジ（すなわち、初期トポロジ）の全てのリンクのリンク利用率を０として、抵抗行列Ａを算出する（ステップＢ１）。すなわち、抵抗行列算出手段２１は、初期トポロジに属する２つのノードｉ，ｊの組を選択し、その２つのノードｉ，ｊ間にリンクが存在していれば、抵抗行列のｉ行ｊ列の要素ａｉｊを式（４）の計算により求める。ただし、ステップＢ１では、式（４）において全てのリンク利用率を０とする。また、２つのノードｉ，ｊ間にリンクが存在していなければ、抵抗行列算出手段２１は、抵抗行列のｉ行ｊ列の要素ａｉｊを０とする。抵抗行列算出手段２１は、ノード間のリンクの有無の判定を、トポロジ行列を参照することによって行えばよい。抵抗行列算出手段２１は、同様に各要素の値を計算することによって抵抗行列Ａを算出する。ただし、抵抗行列の対角要素は０とする。
【００８８】
次に、重み行列算出手段２２が、上記の抵抗行列Ａを用いて、前述の式（５）の計算を行うことによって重み行列Ｗを算出する（ステップＢ２）。
【００８９】
次に、転送確率行列算出手段２３が、抵抗行列Ａおよび重み行列Ｗを用いて、全ＯＤペアに関して、それぞれ転送確率行列を算出する（ステップＢ３）。ステップＢ３において、転送確率行列算出手段２３は、ＯＤペアを１つ選択する。このＯＤペアにおいて、送信元ノードをノードｏとし、宛先ノードをノードｄとする。このＯＤペアについて、任意のリンクＬｉｊの転送確率Ｐｏｄｉｊは、抵抗行列Ａおよび重み行列Ｗの要素を用いて、前述の式（６）の計算で求めることができる。転送確率行列算出手段２３は、この転送確率Ｐｏｄｉｊを、選択したＯＤペアに対応する転送確率行列Ｆｗｏｄのｉ行ｊ列の要素とする。転送確率行列算出手段２３は、転送確率行列Ｆｗｏｄの各要素の値を同様に計算することで、転送確率行列Ｆｗｏｄを算出する。転送確率行列算出手段２３は、ＯＤペア毎に同様の計算を行い、各ＯＤペアについて転送確率行列Ｆｗｏｄを算出する。
【００９０】
次に、リンク利用率算出手段２４は、トラヒック行列、各ＯＤペアの転送確率行列および各リンクの帯域に基づいて、リンク毎にリンク利用率を算出する（ステップＢ４）。ステップＢ４において、リンク利用率算出手段２４は、まず、個々のリンクを通過するトラヒック量を計算する。具体的には、リンク利用率算出手段２４は、以下の式（８）の計算を行えばよい。
【００９１】
【数６】
2015510281.tif 000008
【００９２】
式（８）において、Ｔｏｄは、送信元ノードｏから宛先ノードｄへの単位時間当たりのトラヒック発生量であり、トラヒック行列のｏ行ｄ列の要素である。式（８）は、ＯＤペア毎に計算したＴｏｄとＦｗｏｄとの積の総和である。そして、式（８）によって得られる行列は、トラヒック行列で定められたトラヒック量が発生したときに、個々のリンクを通過するトラヒック量を表す。例えば、式（８）によって得られる行列のｉ行ｊ列の要素は、リンクＬｉｊを通過するトラヒック量を表す。
【００９３】
リンク利用率算出手段２４は、式（８）で得た行列の要素を、リンクの帯域で除算することによって、その要素に対応するリンクのリンク利用率を算出する。リンク利用率算出手段２４は、この除算を、式（８）で得た行列の要素毎に行えばよい。式（８）で得た行列のｉ行ｊ列の要素から、リンクＬｉｊのリンク利用率utilijが求められる。
【００９４】
ステップＢ４の後、遅延算出手段２６は、各リンクの平均遅延を算出する（ステップＢ５）。任意のリンクＬｉｊの平均遅延をlink_delayijと記す。link_delayijは、以下の式（９）の計算により求めることができる。
【００９５】
【数７】
2015510281.tif 000009
【００９６】
遅延算出手段２６は、リンク毎に式（９）の計算を行うことで、各リンクの平均遅延を算出する。なお、ｋは、各ノードのバッファ容量である。ここでは、各ノードのバッファ容量が共通である場合を例に説明しているが、各ノードのバッファ容量が異なっている場合には、ｋとして、着目しているリンクにおける始点のノードのバッファ容量を用いればよい。Ｂｗは、各リンクの帯域である。
【００９７】
ステップＢ５の後、遅延算出手段２６は、各リンクの平均遅延を用いて、ＯＤペア毎に、ＯＤペアの平均遅延を算出する（ステップＢ６）。任意のＯＤペアの平均遅延をaverage_delayodと記す。average_delayodは、以下の式（１０）の計算により求めることができる。
【００９８】
【数８】
2015510281.tif 000010
【００９９】
遅延算出手段２６は、ＯＤペア毎に式（１０）の計算を行うことで、各ＯＤペアの平均遅延を算出する。
【０１００】
次に、ロス率算出手段２７が、各リンクの平均ロス率を算出する（ステップＢ７）。任意のリンクＬｉｊの平均ロス率をlink_lossijと記す。link_lossijは、以下の式（１１）の計算により求めることができる。
【０１０１】
【数９】
2015510281.tif 000011
【０１０２】
ロス率算出手段２７は、リンク毎に式（１１）の計算を行うことで、各リンクの平均ロス率を算出する。
【０１０３】
ステップＢ７の後、ロス率算出手段２７は、リンク毎の平均ロス率を用いて、ＯＤペア毎に、ＯＤペアの平均ロス率を算出する（ステップＢ８）。任意のＯＤペアの平均ロス率をaverage_lossodと記す。average_lossodは、以下の式（１２）の計算により求めることができる。
【０１０４】
【数１０】
2015510281.tif 000012
【０１０５】
ロス率算出手段２７は、ＯＤペア毎に式（１２）の計算を行うことで、各ＯＤペアの平均ロス率を算出する。
【０１０６】
次に、スループット算出手段２８は、入力データとして与えられた要求スループットと転送確率を用いて、各リンクのスループットを算出する（ステップＢ９）。ＯＤペアｏｄの要求スループットをsla_throughputodと記す。また、任意のリンクＬｉｊのスループットを、link_throughputijと記す。link_throughputijは、以下の式（１３）の計算により求めることができる。
【０１０７】
【数１１】
2015510281.tif 000013
【０１０８】
スループット算出手段２８は、リンクＬｉｊのlink_throughputijを算出する場合、式（１３）に示すように、ＯＤペア毎にsla_throughputodとｐｏｄｉｊの積を計算し、その積の総和をlink_throughputijとすればよい。スループット算出手段２８は、リンク毎に式（１３）の計算を行うことで、各リンクのスループットを算出する。
【０１０９】
次に、ＳＬＡ判定手段２９は、ＯＤペア毎の平均遅延、ＯＤペア毎の平均ロス率、リンク毎のスループットに関して、ＳＬＡで定められた範囲に収まっているか、ＳＬＡで定められた範囲よりも低い性能になっているか、あるいは、ＳＬＡで定められた範囲よりも超過した性能になっているかを判定する（ステップＢ１０）。通信性能として、平均遅延および平均ロス率はＯＤペア毎に算出され、スループットはリンク毎に算出されているので、性能を表す値は１つだけではない。従って、ステップＢ１０における判定基準を予め定めておき、その基準に従って、ステップＢ１０の判定を行えばよい。例えば、算出した全ての平均遅延、平均ロス率、スループットが全て、それぞれのＳＬＡの範囲に収まっている場合に、通信性能がＳＬＡで定められた範囲に収まっていると判定してもよい。そして、いずれかの１つの値でもＳＬＡの範囲より低い性能になっていれば、通信性能がＳＬＡで定められた範囲よりも低いと判定してもよい。また、いずれかの１つの値でもＳＬＡの範囲より高い性能になっていれば、通信性能がＳＬＡで定められた範囲を超過していると判定してもよい。ただし、ステップＢ１０における判定基準は、上記の例に限定されない。ステップＢ１０では、算出した平均遅延、平均ロス率、スループットの各値と、ＳＬＡの範囲とを比較して、予め定められた判定基準に従って、通信性能がＳＬＡの範囲に収まっているか、ＳＬＡの範囲よりも低い性能か、ＳＬＡの範囲を超過した性能かを判定すればよい。
【０１１０】
以上の処理でステップＡ２（図８参照）を終了する。
【０１１１】
初期トポロジの通信性能がＳＬＡの範囲に収まっている場合、または、初期トポロジの通信性能がＳＬＡの範囲を超過している場合には、処理を終了する。初期トポロジの通信性能がＳＬＡの範囲に収まっている場合、初期トポロジは適切な通信ネットワークであると言える。
【０１１２】
初期トポロジの通信性能がＳＬＡの範囲よりも低い場合、テーブル管理手段１１は、変更コスト性能テーブルを作成する（ステップＡ３）。テーブル管理手段１１は、式（１）の変数ｂ，ｃに０から整数を昇順に入力していき、ａ，ｂ，ｃの組み合わせ毎にコストを算出する。なお、本実施形態では、ノードとなるスイッチの追加は行わないのでａ＝０とする。また、式（１）の定数Ｓ，Ｌ，Ｃは予め入力データとして与えておけばよい。テーブル管理手段１１は、ａ，ｂ、ｃおよび算出したコストの組み合わせを、コストが昇順になるようにソートし、トポロジを表すフィールドおよびそのトポロジの性能を表すフィールドを追加すればよい。また、テーブル管理手段１１は、昇順に並べた各組合せに対して、コスト識別番号ｍを０，１，２，・・・の順に順番に割り当てる。この結果、図２に例示する変更コスト性能テーブルが得られる。テーブル管理手段１１は、作成した変更コスト性能テーブルをテーブル記憶手段１２に記憶させる。また、ｍ＝０の行のトポロジとして、初期トポロジを表すデータを登録する。
【０１１３】
次に、テーブル管理手段１１は、変更コスト性能テーブルから、ｍ＝Ｘの行を選択行として選択する（ステップＡ４）。なお、Ｘの初期値は、予め定めておく。ステップＡ４ではＸの初期値を用いる。
【０１１４】
続いて、テーブル管理手段１１は、選択行（ｍの値が示す行）に対する親トポロジを検索し、選択行に対する親トポロジが存在しているか否かを判定する（ステップＡ５）。すなわち、テーブル管理手段１１は、ａの値が選択行のａの値と等しく、ｂの値が選択行のｂの値以下であり、ｃの値も選択行のｃの値以下である行のうち、トポロジ候補が算出され、そのトポロジ候補の中から性能が最高のトポロジが特定された行であって、選択行に最も近い行に対応するトポロジを検索する。検索に成功すれば、そのトポロジが親トポロジに該当する。また、検索に失敗すれば、親トポロジはないと判定する。
【０１１５】
選択行に対する親トポロジが存在しない場合（ステップＡ５におけるＮｏ）、トポロジ導出手段１４は、初期トポロジに基づいて、選択行のコストに応じたトポロジであって、最も通信性能が高いトポロジを作成する（ステップＡ６）。
【０１１６】
選択行に対する親トポロジが存在する場合（ステップＡ５におけるＹｅｓ）、トポロジ導出手段１４は、その親トポロジに基づいて、選択行のコストに応じたトポロジであって、最も通信性能が高いトポロジを作成する（ステップＡ７）。
【０１１７】
ステップＡ６，Ａ７の処理は、選択行のコストに応じたトポロジを作成する際に、初期トポロジに基づいて作成するか、親トポロジに基づいて作成するかが異なる点以外は、同様の処理である。ステップＡ６，Ａ７の処理経過は、図１０に示すフローチャートで表すことができる。以下、ステップＡ７を例にして、選択行のコストに応じたトポロジであって、最も通信性能が高いトポロジを作成する処理を説明する。
【０１１８】
ステップＡ７では、リンク追加ペア算出手段１６が、親トポロジ内のリンクで接続されていないノードのペアの中から、リンクを追加すべきノードのペア（以下、リンク追加ペアと記す。）の候補を算出する（ステップＣ１）。リンク追加ペア算出手段１６は、リンク追加ペアの候補を、予め定められた個数算出する。この個数をｑ個とする。
【０１１９】
図１１は、ステップＣ１の処理経過の例を示すフローチャートである。ステップＣ１において、リンク追加ペア算出手段１６は、親トポロジ内のＳＬＡを満足していないＯＤペアを性能評価手段２０に算出させる（ステップＤ１）。性能評価手段２０は、リンク追加ペア算出手段１６からの要求に応じて、親トポロジを対象にして前述のステップＢ１〜Ｂ８（図９参照）の処理を行う。そして、ステップＢ８の後、ＳＬＡ判定手段２９が、ステップＢ６で算出された通信遅延とステップＢ８で算出された平均ロス率のうち少なくとも一方がＳＬＡの範囲に含まれないＯＤペア（すなわち、ＳＬＡを満足しないＯＤペア）を全て特定し、そのＯＤペアをリンク追加ペア算出手段１６に通知する。
【０１２０】
なお、ステップＤ１で上記のようにステップＢ１〜Ｂ８の処理を行う場合、ステップＢ４の後、抵抗行列算出手段２１が、ステップＢ４で得られたリンク利用率を用いて抵抗行列Ａを再計算する。この抵抗行列Ａの計算は、ステップＢ４で得られたリンク利用率を用いる点以外は、ステップＢ１における計算と同様である。また、抵抗行列Ａを再計算した後、重み行列算出手段２２は、その抵抗行列Ａを用いて重み行列Ｗを再計算する。この重み行列Ｗの計算は、ステップＢ２と同様に式（５）の計算である。
【０１２１】
ステップＤ１の後、リンク追加ペア算出手段１６は、親トポロジ内の任意のノードｉ，ｊのペアを選択し、ＳＬＡを満足していないＯＤペア毎にトラヒックがノードｉを通過する確率、およびノードｊを通過する確率を計算し、それらの確率の総和を計算する。ノードｉ，ｊのペアについてのこの計算結果をconnect_degreeijと記す。リンク追加ペア算出手段１６は、以下の式（１４）によりconnect_degreeijを計算すればよい。
【０１２２】
【数１２】
2015510281.tif 000014
【０１２３】
ｗｏｉ，ｗｉｄ，ｗｏｄ，ｗｏｊ，ｗｊｄは、ステップＤ１でリンク利用率算出後に再計算された重み行列の要素である。式（１４）において、ｗｏｉｗｉｄ／ｗｏｄは、ＯＤペアｏｄのトラヒックがノードｉを通過する確率である。また、ｗｏｊｗｊｄ／ｗｏｄは、ＯＤペアｏｄのトラヒックがノードｊを通過する確率である。また、式（１４）において、“ｏｄin breached SLA”はＳＬＡを満足していないＯＤペアを意味する。
【０１２４】
リンク追加ペア算出手段１６は、親トポロジ内の全てのノードのペアについて、式（１４）の計算を行う（ステップＤ２）。connect_degreeijの値が大きいノードのペアは、トラヒックが通過する確率が高いノードのペアであるので、そのノード間にリンクを設けることが好ましいと言える。
【０１２５】
ステップＤ２の後、リンク追加ペア算出手段１６は、親トポロジの中からノード間にリンクが存在していないノードのペアを全て列挙する（ステップＤ３）。リンク追加ペア算出手段１６は、リンクの有無を、親トポロジのトポロジ行列から判定すればよい。
【０１２６】
次に、リンク追加ペア算出手段１６は、ステップＤ３で列挙したノードのペアを、ステップＤ２で計算したconnect_degreeijを基にして降順にソートする（ステップＤ４）。
【０１２７】
リンク追加ペア算出手段１６は、ソートしたノードのペアのうち、上位ｑ個のノードのペアをリンク追加ペアの候補として決定する（ステップＤ５）。以上の処理で、ノード間にリンクを設けることが好ましい順にｑ個のリンク追加ペアの候補が得られる。ステップＤ５で、ステップＣ１の処理を終了する。
【０１２８】
ステップＣ１の後、トポロジ作成手段１５は、リンク追加ペアの候補の組み合わせのうち、ステップＣ３で選択していない組み合わせが存在しているか否かを判定する（ステップＣ２）。
【０１２９】
ここで、リンク追加ペアの候補の組み合わせについて説明する。選択行におけるｂ，ｃの値をsun_b，sun_cとする。また、親トポロジに対応する行におけるｂ，ｃの値をparent_b，parent_cとする。このとき、選択行のトポロジに追加すべきケーブルの本数は、（sun_b−parent_b）＋（sun_c−parent_c）となる。上記のリンク追加ペアの候補の組み合わせは、（sun_b−parent_b）＋（sun_c−parent_c）個のリンク追加ペアの組み合わせである。
【０１３０】
ステップＣ３で選択していないリンク追加ペアの候補の組み合わせが存在しなければ（ステップＣ２におけるＮｏ）、ステップＡ７の処理を終了する。
【０１３１】
ステップＣ３で選択していないリンク追加ペアの候補の組み合わせが存在する場合（ステップＣ２におけるＹｅｓ）、トポロジ作成手段１５は、その組み合わせの中から１つの組み合わせを選択する。そして、トポロジ作成手段１５は、親トポロジに対して、リンクを追加して新たなトポロジを作成する（ステップＣ３）。具体的には、トポロジ作成手段１５は、選択した組み合わせに属するリンク追加ペア毎に、リンク追加ペアに該当する２つのノード間にリンクを追加する。
【０１３２】
続いて、トポロジ作成手段１５は、ケーブルの差し替えによってリンクを変更するか否かを判定する（ステップＣ４）。換言すれば、トポロジ作成手段１５は、選択行において、ケーブルを変更することが定められているか否かを判定する。トポロジ作成手段１５は、選択行においてｃ＞０であれば、ケーブルの差し替えによるリンクの変更があると判定し、ｃ＝０であれば、ケーブルの差し替えによるリンクの変更はないと判定する。
【０１３３】
リンクの変更がないと判定した場合（ステップＣ４におけるＮｏ）、ステップＣ８に移行する。
【０１３４】
リンクの変更があると判定した場合（ステップＣ４におけるＹｅｓ）、リンク削除ペア算出手段１７は、直近のステップＣ３で作成されたトポロジ内のリンクで接続されているノードのペアの中から、リンクを削除すべきノードのペア（以下、リンク削除ペアと記す。）の候補を算出する（ステップＣ５）。リンク削除ペア算出手段１７は、リンク削除ペアの候補を、予め定められた個数算出する。この個数をｒ個とする。
【０１３５】
図１２は、ステップＣ５の処理経過の例を示すフローチャートである。ステップＣ５において、リンク削除ペア算出手段１７は、直近のステップＣ３で作成されたトポロジの抵抗行列および重み行列を性能評価手段２０に算出させる（ステップＥ１）。性能評価手段２０は、リンク追加ペア算出手段１６からの要求に応じて、そのトポロジに対して前述のステップＢ１〜Ｂ４の処理を行う。さらに、抵抗行列算出手段２１がステップＢ４で得られたリンク利用率を用いて抵抗行列Ａを再計算する。この抵抗行列Ａの計算は、ステップＢ４で得られたリンク利用率を用いる点以外は、ステップＢ１における計算と同様である。また、抵抗行列Ａを再計算した後、重み行列算出手段２２は、その抵抗行列Ａを用いて重み行列Ｗを再計算する。この重み行列Ｗの計算は、ステップＢ２と同様に式（５）の計算である。この抵抗行列Ａおよび重み行列Ｗが、直近のステップＣ３で作成されたトポロジの抵抗行列および重み行列である。
【０１３６】
リンク削除ペア算出手段１７は、直近のステップＣ３で作成されたトポロジに含まれるノードのペアのうち、ノード同士がリンクで結ばれている全てのペアについて、リンク重要度を算出する。リンク重要度は、ペアを構成するノードをｉ，ｊとしたときに、ＯＤペア毎のリンクＬｉｊの転送確率とリンクＬｊｉの転送確率の総和である。リンク重要度に関してはペアを構成するノードの順番は問わない。ノードｉ，ｊのペアのリンク重要度をimportance_degreei<->jと記す。importance_degreei<->jは、以下の式（１５）で表すことができる。
【０１３７】
【数１３】
2015510281.tif 000015
【０１３８】
式（１５）において、ｗｏｄ，ｗｏｉ，ｗｊｄ，ｗｏｊ，ｗｉｄは、ステップＥ１で算出した重み行列Ｗの要素である。また、ａｉｊ，ａｊｉは、ステップＥ１で算出した抵抗行列の要素である。式（１５）において、（ｗｏｉａｉｊｗｊｄ）／ｗｏｄは、ＯＤペアｏｄにおけるリンクＬｉｊの転送確率である。また、（ｗｏｊａｊｉｗｉｄ）／ｗｏｄは、ＯＤペアｏｄにおけるリンクＬｊｉの転送確率である。
【０１３９】
リンク削除ペア算出手段１７は、ノード同士がリンクで結ばれている全てのペアについて、式（１５）の計算を行う（ステップＥ２）。importance_degreei<->jの低いノードのペアほど、ノード間のリンクの重要度が低いと言える。
【０１４０】
ステップＥ２の後、リンク削除ペア算出手段１７は、リンク重要度を基にして、ノード同士がリンクで結ばれている全てのペアを昇順にソートする（ステップＥ３）。
【０１４１】
ステップＥ２の後、リンク削除ペア算出手段１７は、ソートしたノードのペアのうち、上位ｒ個のノードのペアをリンク削除ペアの候補として決定する（ステップＥ４）。以上の処理で、ノード間のリンクを削除することが好ましい順にｒ個のリンク削除ペアが得られる。ステップＥ４で、ステップＣ５の処理を終了する。
【０１４２】
ステップＣ５の後、トポロジ作成手段１５は、リンク削除ペアの候補の組み合わせのうち、ステップＣ７で選択していない組み合わせが存在しているか否かを判定する（ステップＣ６）。
【０１４３】
ここで、リンク削除ペアの候補の組み合わせについて説明する。前述のように、選択行におけるｃの値をsun_c とする。また、親トポロジに対応する行におけるｃの値をparent_cとする。このとき、直近のステップＣ３で作成されたトポロジから削除すべきケーブルの本数は、sun_c−parent_c となる。上記のリンク削除ペアの候補の組み合わせは、sun_c−parent_c 個のリンク削除ペアの組み合わせである。
【０１４４】
ステップＣ７で選択していないリンク削除ペアの候補の組み合わせが存在しなければ（ステップＣ６におけるＮｏ）、ステップＣ２以降の処理を繰り返す。
【０１４５】
ステップＣ７で選択していないリンク削除ペアの候補の組み合わせが存在する場合（ステップＣ６におけるＹｅｓ）、トポロジ作成手段１５は、その組み合わせの中から１つの組み合わせを選択する。そして、トポロジ作成手段１５は、直近のステップＣ３で作成したトポロジからリンクを削除して新たなトポロジを作成する（ステップＣ７）。具体的には、トポロジ作成手段１５は、選択した組み合わせに属するリンク削除ペア毎に、リンク削除ペアに該当する２つのノード間のリンクを削除する。ステップＣ７の終了後、ステップＣ８に移行する。
【０１４６】
ステップＣ８では、トポロジ作成手段１５は、作成したトポロジの通信性能を性能評価手段２０に推定させる。なお、トポロジ作成手段１５は、リンクの変更がないと判定してステップＣ４からステップＣ８に移行した場合、直近のステップＣ３で作成したトポロジの通信性能を性能評価手段２０に推定させる。一方、ステップＣ７からステップＣ８に移行した場合、トポロジ作成手段１５は、ステップＣ７で作成したトポロジの通信性能を性能評価手段２０に推定させる。
【０１４７】
そして、トポロジ作成手段１５は、トポロジの通信性能が、選択行に関してそれまでに作成したトポロジの通信性能のうち最高の通信性能（以下、単に最高性能と記す。）を超えているか否かを判定する。
【０１４８】
ステップＣ８では、例えば、平均遅延がＳＬＡの範囲から外れているＯＤペアの数と平均ロス率がＳＬＡの範囲から外れているＯＤペアの数の和で、通信性能を表してもよい。以下、ステップＣ８で、このように通信性能を表す場合を例にして説明する。この場合、そのようなＯＤペアの数が少ないほど、通信性能がよい。
【０１４９】
本例の場合、トポロジ作成手段１５は、作成したトポロジについて、平均遅延がＳＬＡの範囲から外れているＯＤペアの数と平均ロス率がＳＬＡの範囲から外れているＯＤペアの数の和を性能評価手段２０に算出させればよい。性能評価手段２０は、トポロジ作成手段１５の要求に従って、ステップＢ１〜ステップＢ８の処理を行う。そして、ＳＬＡ判定手段２９は、ステップＢ６で算出された平均遅延がＳＬＡの範囲から外れているＯＤペアの数と、ステップＢ８で算出された平均ロス率がＳＬＡの範囲から外れているＯＤペアの数をそれぞれカウントし、その結果の和を計算する。
【０１５０】
トポロジ作成手段１５は、平均遅延や平均ロス率がＳＬＡから外れているＯＤペアの数がその最小値を更新すれば、それまでの最高性能を超えていると判定する（ステップＣ８におけるＹｅｓ）。この場合、トポロジ作成手段１５は、着目しているトポロジを、選択行における最高性能のトポロジとして記憶し（ステップＣ９）、ステップＣ６以降の処理を繰り返す。一方、平均遅延や平均ロス率がＳＬＡから外れているＯＤペアの数がその最小値を更新していなければ（ステップＣ８におけるＮｏ）、ステップＣ６以降の処理を繰り返す。
【０１５１】
なお、ステップＡ７（図８参照）を開始後、最初にステップＣ８に移行したときには、その時点で得られる性能が最高性能となるので、トポロジ作成手段１５は、その時点で得られているトポロジを記憶すればよい。
【０１５２】
図１０に示すフローチャートでは、ステップＣ３あるいはステップＣ７で、選択行のトポロジの候補が作成される。そして、それらのトポロジ候補のうち、通信性能が最高となるトポロジが得られると、トポロジ作成手段１５は、ステップＣ９でそのトポロジを記憶することで、最高性能のトポロジを更新する。この結果、ステップＡ７の終了時に、選択行のコストに応じたトポロジの候補のうち、最高性能のトポロジが得られることになる。
【０１５３】
以上の図１０の説明ではステップＡ７を例にして説明したが、ステップＡ６の処理も同様に行えばよい。ステップＡ６では親トポロジの代わりに初期トポロジを用いればよい。
【０１５４】
ステップＡ６またはステップＡ７の後、テーブル管理手段１１は、ステップＡ６またはステップＡ７で得られた最高性能のトポロジ、およびその性能を、変更コスト性能テーブルの選択行に登録する（ステップＡ８）。
【０１５５】
次に、トポロジ作成手段１５は、選択行のトポロジの通信性能がＳＬＡの範囲に収まっているか、ＳＬＡの範囲よりも高いか、あるいは、ＳＬＡの範囲よりも低いかを判定する処理を性能評価手段２０に実行させる（ステップＡ９）。
【０１５６】
ステップＡ９における性能評価手段２０の動作は、ステップＡ２における動作と同様である。すなわち、性能評価手段２０は、ステップＡ９では、選択行のトポロジを性能評価の対象として、ステップＢ１〜Ｂ１０の処理を行えばよい。
【０１５７】
選択行のトポロジの通信性能がＳＬＡの範囲に収まっている場合、処理を終了する。その時点における選択行のトポロジは適切な通信品質の通信ネットワークを表していると言える。
【０１５８】
また、選択行のトポロジの通信性能がＳＬＡの範囲よりも低い場合、テーブル管理手段１１は、その時点におけるｍの値にＸを加算した値で、ｍの値を更新する（ステップＡ１０）。ステップＡ１０の処理は、よりコストの高い行を選択する処理であるということができる。すなわち、直前の選択行における最高性能のトポロジがＳＬＡの範囲よりも低かったので、テーブル管理手段１１は、ステップＡ１０の演算によって、よりコストの高い行を選択する。そして、新たな選択行（ｍの値が示す行）についてステップＡ５以降の処理を繰り返す。
【０１５９】
また、ステップＡ９において、選択行のトポロジの通信性能がＳＬＡの範囲を超過している場合、テーブル管理手段１１は、その時点におけるｍの値からＸ（ｔ−１）／ｔを減算した値で、ｍの値を更新する（ステップＡ１１）。ステップＡ１１の処理は、選択行よりもコストの低い行を選択する処理であるということができる。すなわち、直前の選択行における最高性能のトポロジがＳＬＡの範囲を超過していたので、テーブル管理手段１１は、ステップＡ１１の演算によって、よりコストの低い行を選択する。なお、ステップＡ１１において、更新後のｍの値が整数でない場合、テーブル管理手段１１は、例えば、四捨五入、切り捨てまたは切り上げによって更新後のｍの値を整数にする。
【０１６０】
続いて、テーブル管理手段１１は、Ｘをｔで除算した値で、Ｘの値を更新する（ステップＡ１２）。なお、Ｘをｔで除算した値が整数でない場合、テーブル管理手段１１は、四捨五入、切り捨てまたは切り上げによって更新後のＸの値を整数にする。
【０１６１】
前述のステップＡ１０の処理によって、テーブル管理手段１１は、Ｘ行毎に変更コスト性能テーブルから行を選択することになる。選択行のトポロジの通信性能がＳＬＡの範囲を超過している場合、上記のステップＡ１２の処理を行って、Ｘの値をより小さな値に変更する。従って、ステップＡ１２以降の処理では、より細かに行を選択していくことになる。
【０１６２】
本実施形態によれば、ネットワーク設計システムは、トポロジ変更に要するコストを上げたときのトポロジ候補の中から最高性能のトポロジを選択し、そのトポロジの通信性能がＳＬＡの範囲よりも低い場合に、さらにコストを上げて、同様の処理を繰り返す。そして、得られたトポロジの性能がＳＬＡの範囲に収まれば処理を終了する。従って、将来のトラヒック量を多めに見積もってネットワーク構築に要するコストを必要以上に高くし、過剰品質の通信ネットワークを設計することを防止することができる。すなわち、適切なコスト・品質の通信ネットワークを設計することができる。
【０１６３】
また、ネットワーク設計システムは、トポロジ変更に要するコストを上げて得られた最高性能のトポロジがＳＬＡの範囲を超過している場合、トポロジ変更に要するコストを下げ（ステップＡ１１）、また、選択行の選択をより細かに行う。従って、トポロジがＳＬＡの範囲を超過した場合であっても、適切なコスト・品質の通信ネットワークを設計することができる。
【０１６４】
次に、上記の実施形態の変形例について説明する。
上記の実施形態においてＸ＝１としてもよい。この場合、テーブル管理手段１１は、変更コスト性能テーブルの各行を順次選択する。また、この場合、ステップＡ１１，Ａ１２の処理は行わなくてよい。ステップＡ９において、トポロジの性能がＳＬＡの範囲を超過した場合、その時点で処理を終了すればよい。
【０１６５】
また、本発明のネットワーク設計システムは、図１３に例示するように、出力手段１９を備えていてもよい。図１３は、本発明の実施形態の変形例を示すブロック図である。既に説明した要素と同一の要素については、図６と同一の符号を付し、説明を省略する。出力手段１９は、適切なコスト・品質の通信ネットワークを特定可能な情報を出力する。適切なコスト・品質の通信ネットワークとは、ステップＡ９において、通信性能がＳＬＡの範囲に収まっていると判定されたトポロジに対応する通信ネットワークである。
【０１６６】
出力手段１９は、例えば、通信性能がＳＬＡの範囲に収まっているとステップＡ９で判定されたトポロジを直接表示してもよい。
【０１６７】
あるいは、出力手段１９は、そのトポロジと、初期トポロジとの差分を表示してもよい。例えば、出力手段１９は、通信性能がＳＬＡの範囲に収まっているとステップＡ９で判定されたトポロジにおいて、初期トポロジに対して追加されたリンクおよび初期トポロジから削除されたリンクを表示してもよい。
【０１６８】
また、上記の例では、出力手段１９が表示を行う場合を例示したが、出力手段１９による情報の出力態様は表示に限定されない。
【０１６９】
次に、本発明の概要について説明する。図１４は、本発明の概要を示すブロック図である。本発明のネットワーク設計システムは、テーブル作成手段９１と、選択手段９２と、親トポロジ検索手段９３と、トポロジ導出手段９４と、性能推定手段９５とを備える。
【０１７０】
テーブル作成手段９１（例えば、テーブル管理手段１１）は、初期トポロジからのトポロジ変更に要するコストを各レコード（例えば、変更コスト性能テーブルにおける各行）に昇順に並べたテーブルであって、コストに応じたトポロジ変更量（例えば、実施形態における“ｂ”，“ｃ”等）を示すフィールドと、コストに応じたトポロジ変更を初期トポロジに施したトポロジを登録可能なフィールドとを含むテーブル（例えば、変更コスト性能テーブル）を作成する。
【０１７１】
選択手段９２（例えば、テーブル管理手段１１）は、テーブルから一定数のレコード毎にレコードを選択する。
【０１７２】
親トポロジ検索手段９３（例えば、親トポロジ検索手段１３）は、トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索する。
【０１７３】
トポロジ導出手段９４（例えば、トポロジ導出手段１４）は、親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択されたレコードのコストに応じたトポロジ群を作成する。
【０１７４】
性能推定手段９５（例えば、性能評価手段２０）は、トポロジが示す通信ネットワークの通信性能を推定する。
【０１７５】
また、トポロジ導出手段９４は、トポロジ群のうち通信性能が最も高いトポロジを、選択されたレコードのトポロジとして登録する。そして、性能推定手段９５は、そのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定する。
【０１７６】
また、選択手段９２は、そのトポロジの通信性能が、その範囲よりも低い場合に、再度、テーブルからレコードを選択する。
【０１７７】
以上のような構成により、ＳＬＡを満足する、適切なコスト・品質の通信ネットワークを設計することができる。
【０１７８】
また、選択されたレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属している場合に、そのトポロジが示す通信ネットワークを特定可能な情報を出力する出力手段（例えば、出力手段１９）を備える構成であってもよい。
【０１７９】
また、選択手段９２が、選択したレコードのトポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲を超過している場合に、そのレコードよりもコストが低いレコードを選択し、一定数の値を減少させてもよい。
【０１８０】
また、トポロジ導出手段９４が、親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定し、当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加することで、選択されたレコードのコストに応じたトポロジ群を作成してもよい。
【０１８１】
また、トポロジ導出手段９４が、親トポロジの検索に成功した場合には親トポロジから、リンクを追加すべきノードのペア群を特定し、親トポロジの検索に失敗した場合には初期トポロジから、リンクを追加すべきノードのペア群を特定し、当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアにリンクを追加し、トポロジ変更量を示すフィールドにおいて、ノード間のケーブルの差し替えが規定されている場合に、リンク追加後のトポロジから、リンクを削除すべきノードのペア群を特定し、当該ノードのペア群から、ノードのペアを順次選択し、選択したノードのペアからリンクを削除することで、選択されたレコードのコストに応じたトポロジ群を作成する構成であってもよい。
【０１８２】
また、本発明は、図１５に例示するブロック図のように表すこともできる。本発明のネットワーク設計システムは、記憶手段９６と、選択手段９２と、トポロジ導出手段９４と、性能推定手段９５とを備える。
【０１８３】
記憶手段９６は、トポロジ変更量を含む複数のレコードを有するテーブルを記憶する。
【０１８４】
選択手段９２は、テーブルから所定のレコードを選択する。
【０１８５】
トポロジ導出手段９４は、選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成する。
【０１８６】
性能推定手段９５は、トポロジが示す通信ネットワークの通信性能を推定する。そして、性能推定手段９５は、トポロジの通信性能が、適切な通信性能の範囲として予め定められた範囲に属しているか否かを判定する。
【０１８７】
選択手段９２は、トポロジの通信性能がその範囲に属していない場合に、再度、テーブルからレコードを選択する。
【０１８８】
そして、初期トポロジからのトポロジ変更量を示すフィールドと、そのトポロジ変更量に応じた変更を初期トポロジに施したトポロジを登録可能なフィールドとを含む複数のレコードを有するテーブルを作成するテーブル作成手段と、トポロジ変更量が、選択されたレコードのトポロジ変更量以下であり、トポロジが登録済みのレコードのトポロジである親トポロジを検索する親トポロジ検索手段とを備え、トポロジ導出手段９４が、親トポロジの検索に成功した場合には親トポロジを用い、親トポロジの検索に失敗した場合には初期トポロジを用いて、選択されたレコードに含まれるトポロジ変更量に基づいてトポロジを作成する構成であってもよい。
【０１８９】
この出願は、２０１２年３月１６日に出願された日本特許出願２０１２−６１０９９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【０１９０】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記の実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１９１】
本発明は、通信ネットワークの設計に好適に適用可能である。
【符号の説明】
【０１９２】
１  ネットワーク設計システム
１０  ネットワーク再設計手段
１１  テーブル管理手段
１２  テーブル記憶手段
１３  親トポロジ検索手段
１４  トポロジ導出手段
１５  トポロジ作成手段
１６  リンク追加ペア算出手段
１７  リンク削除ペア算出手段
１９  出力手段
２０  性能評価手段
２１  抵抗行列算出手段
２２  重み行列算出手段
２３  転送確率行列算出手段
２４  リンク利用率算出手段
２５  性能推定手段
２６  遅延算出手段
２７  ロス率算出手段
２８  スループット算出手段
２９  ＳＬＡ判定手段
【図１】
2015510281.tif 000016
【図２】
2015510281.tif 000017
【図３】
2015510281.tif 000018
【図４】
2015510281.tif 000019
【図５】
2015510281.tif 000020
【図６】
2015510281.tif 000021
【図７】
2015510281.tif 000022
【図８】
2015510281.tif 000023
【図９】
2015510281.tif 000024
【図１０】
2015510281.tif 000025
【図１１】
2015510281.tif 000026
【図１２】
2015510281.tif 000027
【図１３】
2015510281.tif 000028
【図１４】
2015510281.tif 000029
【図１５】
2015510281.tif 000030
【国際調査報告】
2015510281.tif 000031