網トポロジ・リンク容量設計処理方法とシステムおよびプログラム
【課題】単一リンク障害時の迂回トラヒックに対する品質をも考慮した、網トポロジとリンク容量の設計を可能とする。
【解決手段】ノード位置と、トラヒック交流マトリクス、ルーティング方式、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、入力処理装置１０１は、制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力し、設計処理装置１０２は、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した網トポロジとリンク容量の算出を行う。
【解決手段】ノード位置と、トラヒック交流マトリクス、ルーティング方式、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、入力処理装置１０１は、制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力し、設計処理装置１０２は、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した網トポロジとリンク容量の算出を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等における網のトポロジとリンク容量の設計技術に係り、特に、網トポロジ設計問題において、単一リンク障害時に発生する迂回トラヒックを考慮して、任意のリンクの使用率を任意に定めた上限値以下に抑えることを制約条件に、総コストを最小化することにより、最適な網トポロジとリンク容量を求める技術に関するものである。
【背景技術】
【０００２】
インターネットは個々のフローの状態を網内で管理せず、受信アドレスにのみ基づきルーティング処理が行われる。各ＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅｓ Ｐｒｏｖｉｄｅｒ）が管理する単一ＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）内では、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）により固定的に設定されたリンク重みの総和が最小となる経路上にパケットが転送される。
【０００３】
また、フローの受付制御を行わず転送レートは送信ホストが自律的に決定するため、原理的にリンク輻輳が発生し得る。そのため適切な通信品質を維持するために、網を構成する全てのリンクの利用率が適切な水準以下となるよう網を設計・管理することがＩＳＰの主要な課題の一つとなる。
【０００４】
リンク使用率は、各リンクの設計帯域と流れるトラヒック量とで決まるが、トラヒック量は、交流トラヒックデマンド量の変動や各種障害に起因する経路の変更によって常に変化する。そのため、利用率の低いリンクを積極的に利用するようパケットの流れる経路を動的に設定し、リンク負荷の分散を図るトラヒックエンジニアリング（ＴＥ）が数多く検討されている。
【０００５】
例えば、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）を用いれば発着ノードペア間に明示的にパスを設定できる。非特許文献１においては、各発着ノード間のトラヒックを設置可能な複数のパス間で平準化する設計技術が提案されており、また、非特許文献２，３においては、リンク負荷が網全体で平準化されるようＯＳＰＦの固定的なリンク重みを設定する技術が提案されている。
【０００６】
またＯＳＰＦは、リンクやノードの障害時、自律的に迂回経路を算出するが、例えば、非特許文献４においては、障害時に生成される迂回トラヒックに着目し、いくつかの障害パターンにおいてリンク負荷がうまく分散されるよう、ＯＳＰＦのリンク重みのパターンを各々用意することが検討されている。
【０００７】
これらの技術では、事前に想定した静的な交流マトリクス（発着ノードペアごとのトラヒック量を行列表現したもので、ｉ行ｊ列の要素が、ノードｉからノードｊに向かうトラヒック量となり、「交流行列」、「デマンド行列」、「トラヒック交流」等ともいう）に基づき経路の最適化を行うが、例えば、非特許文献５，６においては、リアルタイムに計測したリンク使用率に基づき、動的にパケットの流れる経路を最適化することも検討されている。
【０００８】
このようなＴＥを用いればリンク負荷を平準化することが可能であり、交流マトリクスが動的に変化する場合（非特許文献５，６）や、リンク・ノード障害により迂回トラヒックが発生する場合（非特許文献４）にも、網資源を有効に活用して輻輳の発生を最小限に抑えることが可能となる。
【０００９】
しかしながら、リンク利用率は、交流マトリクスや経路だけでなく、網トポロジやリンク容量にも依存する。
【００１０】
前述のＴＥでは、網トポロジやリンク容量が既知のものとして与えられることを前提としている。一方で、網トポロジやリンク容量は、網の構築コストや運営コストを決める大きな要因となりＩＳＰの経営に及ぼす影響が大きい。
【００１１】
従って、ＩＳＰは、自身が運営する網のトポロジやリンク容量を自由に設計することができ、これらを適切に設計することが良好な通信品質を低コストで保つためには重要となる。
【００１２】
また、ＴＥによって経路を動的に設定した場合、静的なリンク重みを用いたＯＳＰＦで定まる経路と比較して、経由するリンク数（ホップ数）が増加する。
【００１３】
そのため、網資源の消費を抑える観点からは、ＴＥを用いずに、静的なリンク重みを用いたＯＳＰＦで経路を設定することが望ましい。
【００１４】
また、ルーティングプロトコル種別（ルーティング方式）としてＯＳＰＦを想定し、通信品質を規定値以上に保つために必要なリンク容量の設計手法が、例えば、非特許文献７において検討されているが、この技術でもやはり網トポロジは、設計対象とせず、与えられることを想定している。
【００１５】
以下、ＩＳＰ自身が網を運営するにあたって、良好な通信品質を低コストで保つために重要となる、網トポロジやリンク容量の適切な設計について説明する。
【００１６】
網トポロジは、網コスト、伝送遅延、負荷の分散度合い、信頼性、といった様々な評価尺度に影響を与える。そのため、網トポロジを評価し設計する際には、これら複数の評価尺度を同時に考慮して最適性を評価する必要がある。
【００１７】
例えば、本願の発明者らによる非特許文献８，９においては、複数評価尺度を同時に考慮可能なＤＥＡ（Ｄａｔａ Ｅｎｖｅｌｏｐｍｅｎｔ Ａｎａｌｙｓｉｓ）やＡＨＰ（Ａｎａｌｙｔｉｃａｌ Ｈｉｅｒａｒｃｈｙ Ｐｒｏｃｅｓｓ）を用いて網トポロジを評価する技術が記載されている。
【００１８】
また、各リンクの利用率は、交流マトリクスが与えられ、トポロジ、リンク容量、経路の３つが定まれば決定する。従って、伝送遅延といったユーザの体感品質や、負荷の分散度合いといった各リンクの使用率に関連する品質尺度に対する制約条件を導入すれば、総コストという単一の評価尺度を最適化する整数計画問題となる。
【００１９】
すなわち、ノード位置と交流マトリクス、そしてリンク使用率（もしくはパケットの転送遅延や設計リンク容量）に関連する制約条件に対して総コストを最小化するよう、網トポロジ・リンク容量・経路を同時に最適化する問題となる。このことは、例えば、非特許文献１０において記載されている。
【００２０】
このようにトポロジ設計問題を整数計画問題とみなして解くアプローチは、既に数多く検討されている。例えば、非特許文献１１，１２においては、各ノード間の遅延時間を規定上限値以下に抑えることを制約条件に、総リンクコストを最小化する離散最適化問題を「Ｂｒａｎｃ ｈａｎｄ Ｂｏｕｎｄ法」によりヒューリスティックに解く技術、同様の問題を、多数のリンクが設置された状態からスタートし、１本ずつリンクを除去する作業を解の改善が大きな順に解の改善が見られなくなるまで繰り返す「貪欲算法」により解く技術などが検討されている。
【００２１】
しかし、これらのトポロジ設計技術では障害が考慮されていない。障害を考慮したトポロジ設計技術としては、例えば、非特許文献１３に記載のように、各ノード間にｄｉｓｊｏｉｎｔな経路が規定数以上存在することを制約条件に、総リンクコストを最小化する離散最適化問題をローカルサーチによりヒューリスティックに解く技術や、非特許文献１４に記載のように、任意の単一ノード障害においても全ノード間の接続性が維持されることを制約条件に、やはりリンクコストの総和が最小化するようタブサーチや遺伝アルゴリズムといったヒューリスティックな解法で解く技術が検討されている。
【００２２】
しかし、これらの技術は、障害時の接続性のみを考慮しており、障害時に発生する迂回トラヒックに対しても品質を規定水準内に保つことを考慮した研究は見られない。
【００２３】
【非特許文献１】Ｄ．Ｍｉｔｒａ ａｎｄ Ｋ．Ｒａｍａｋｒｉｓｈｎａ，“Ａ Ｃａｓｅ Ｓｔｕｄｙ ｏｆ Ｍｕｌｔｉｓｅｒｖｉｃｅ Ｍｕｌｔｉｐｒｉｏｒｉｔｙ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ Ｄｅｓｉｇｎ，” ＩＥＥＥ Ｇｌｏｂｅｃｏｍ ９９．
【非特許文献２】Ｂ． Ｆｏｒｔｚ ａｎｄ Ｍ． Ｔｈｏｒｕｐ，“Ｉｎｔｅｒｎｅｔ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ ｂｙ Ｏｐｔｉｍｉｚｉｎｇ ＯＳＰＦ Ｗｅｉｇｈｔｓ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２０００．
【非特許文献３】Ｂ． Ｆｏｒｔｚ ａｎｄ Ｍ． Ｔｈｏｒｕｐ，“Ｒｏｂｕｓｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ＯＳＰＦ／ＩＳ−ＩＳ ｗｅｉｇｈｔｓ，” ＩＮＯＣ ２００３．
【非特許文献４】Ａ． Ｋｖａｌｂｅｉｎ， Ａ． Ｆ． Ｈａｎｓｅｎ， Ｔ． Ｃｉｃｉｃ， Ｓ． Ｇｊｅｓｓｉｎｇ， ａｎｄ Ｏ． Ｌｙｓｎｅ，“Ｆａｓｔ ＩＰ Ｎｅｔｗｏｒｋ Ｒｅｃｏｖｅｒｙ ｕｓｉｎｇ Ｍｕｌｔｉｐｌｅ Ｒｏｕｔｉｎｇ Ｃｏｎｆｉｇｕｒａｔｉｏｎｓ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００６．
【非特許文献５】Ａ． Ｅｌｗａｌｉｄ， Ｃ． Ｊｉｎ， Ｓ． Ｌｏｗ， ａｎｄ Ｉ． Ｗｉｄｊａｊａ，“ＭＡＴＥ： ＭＰＬＳ Ａｄａｐｔｉｖｅ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００１．
【非特許文献６】Ｓ． Ｋａｎｄｕｌａ， Ｄ． Ｋａｔａｂｉ， Ｂ． Ｄａｖｉｅ， ａｎｄ Ａ． Ｃｈａｒｎｙ，“Ｗａｌｋｉｎｇ ｔｈｅ Ｔｉｇｈｔｒｏｐｅ： Ｒｅｓｐｏｎｓｉｖｅ Ｙｅｔ Ｓｔａｂｌｅ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ，” ＡＣＭ ＳＩＧＣＯＭＭ ２００５．
【非特許文献７】Ｍ． Ｍｅｎｔｈ， Ｒ． Ｍａｒｔｉｎ， Ｊ． Ｃｈａｒｚｉｎｓｋｉ，“Ｃａｐａｃｉｔｙ Ｏｖｅｒｐｒｏｖｉｓｉｏｎｉｎｇ ｆｏｒ Ｎｅｔｗｏｒｋｓ ｗｉｔｈ Ｒｅｓｉｌｉｅｎｃｅ Ｒｅｑｕｉｒｅｍｅｎｔｓ，” ＡＣＭ ＳＩＧＣＯＭＭ ２００６．
【非特許文献８】Ｎ． Ｋａｍｉｙａｍａ，“Ｎｅｔｗｏｒｋ Ｔｏｐｏｌｏｇｙ Ｄｅｓｉｇｎ ｕｓｉｎｇ Ｄａｔａ Ｅｎｖｅｌｏｐｍｅｎｔ Ａｎａｌｙｓｉｓ，” ＩＥＥＥ Ｇｌｏｂｅｃｏｍ ２００７．￥ｂｉｂｉｔｅｍ｛Ｋａｍｉｙａｍａ２｝
【非特許文献９】神山憲明，佐藤大輔，“ＡＨＰを用いた網トポロジ設計，” 信学技報ＩＮ２００６−１４５．
【非特許文献１０】Ｍ． Ｇｅｒｌａ ａｎｄ Ｌ． Ｋｌｅｉｎｒｏｃｋ，“Ｏｎ ｔｈｅ Ｔｏｐｏｌｏｇｉｃａｌ Ｄｅｓｉｇｎ ｏｆ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ，” ＩＥＥＥ Ｔｒａｎｓ． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ＣＯＭ−２５， １， ｐｐ．４８−６０， １９７７．
【非特許文献１１】Ｎ． Ｇ． Ｃｈａｔｔｏｐａｄｈｙａｙ， Ｔ． Ｗ． Ｍｏｒｇａｎ， ａｎｄ Ａ． Ｒａｇｈｕｒａｍ，“Ａｎ Ｉｎｎｏｖａｔｉｖｅ Ｔｅｃｈｎｉｑｕｅ ｆｏｒ Ｂａｃｋｂｏｎｅ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ，” ＩＥＥＥ Ｔｒａｎｓ． Ｓｙｓｔｅｍ， Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ， １９， ５， １９８９．
【非特許文献１２】Ａ． Ｇｅｒｓｈｔ ａｎｄ Ｒ． Ｗｅｉｈｍａｙｅｒ，“Ｊｏｉｎｔ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｄａｔａ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ ａｎｄ Ｆａｃｉｌｉｔｙ Ｓｅｌｅｃｔｉｏｎ，” ＩＥＥＥ Ｊ． Ｓｅｌｅｃ． Ａｒｅａｓ， Ｃｏｍｍｕｎ．， ８， ９， ｐｐ．１６６７−１６８１， １９９０．
【非特許文献１３】Ｋ． Ｓｔｅｉｇｌｉｔｚ， Ｐ． Ｗｅｉｎｅｒ， ａｎｄ Ｄ． Ｊ． Ｋｌｅｉｔｍａｎ，“Ｔｈｅ Ｄｅｓｉｇｎ ｏｆ Ｍｉｎｉｍｕｍ−Ｃｏｓｔ Ｓｕｒｖｉｖａｂｌｅ Ｎｅｔｗｏｒｋｓ，” ＩＥＥＥ Ｔｒａｎｓ． Ｃｉｒｃｕｉｔ Ｔｈｅｏｒｙ， ＣＴ−１６， ４， ｐｐ．４５５−４６０， １９６９．
【非特許文献１４】Ｅ． Ｃ． Ｇ． Ｗｉｌｌｅ， Ｍ． Ｍｅｌｌｉａ， Ｅ． Ｌｅｏｎａｒｄｉ， ａｎｄ Ｍ． Ａ． Ｍａｒｓａｎ，“Ｔｏｐｏｌｏｇｉｃａｌ Ｄｅｓｉｇｎ ｏｆ Ｓｕｒｖｉｖａｂｌｅ ＩＰ Ｎｅｔｗｏｒｋｓ Ｕｓｉｎｇ Ｍｅｔａｈｅｕｒｉｓｔｉｃ Ａｐｐｒｏａｃｈｅｓ，” Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ｐｐ．１９１−２０６， ２００５．
【発明の開示】
【発明が解決しようとする課題】
【００２４】
解決しようとする問題点は、従来の技術では、障害時の接続性のみを考慮しており、障害時に発生する迂回トラヒックに対しても品質を規定水準内に保つことを考慮していない点である。
【００２５】
本発明の目的は、これら従来技術の課題を解決し、単一リンク障害時の迂回トラヒックに対する品質をも考慮した、網トポロジとリンク容量の設計を可能とすることである。
【課題を解決するための手段】
【００２６】
上記目的を達成するため、本発明では、網のトポロジとリンク容量の設計処理を行うために、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別（ルーティング方式）が与えられたときに、正常時の任意のリンクの使用率を規定値γ以下に抑えることを制約条件に、総ネットワークコストを最小化する。この際、リンク数Ｌと、０から１の範囲の値をとる任意に定めた実数パラメタεに対して、正常時のトラヒック量が大きな順にｋ＝εＬ本のリンクの各々の単一障害時に発生する迂回トラヒックを考慮して、リンク使用率をγ以下に抑えることと、残るＬ−ｋ本のリンクの各々の単一障害時にも全ノード間の接続性が維持されることを制約条件とする。また、全ノード間にリンクを設置した状態からスタートし、リンクコストを正常時に流れるトラヒック量で除した値が大きなリンクから優先的に削除する作業を、総ネットワークコストの改善が見られなくなるまで反復する。さらに、任意のリンクを削除した際、削除したリンクを通るパスに対してのみ経路を再計算することで計算時間を抑える。
【発明の効果】
【００２７】
本発明によれば、ノードの位置と、ノード間の交流トラヒック行列と、経路設定法（ルーティングプロトコル種別）と、リンク使用率の規定上限とを少なくとも含むデータが与えられているときに、任意の単一リンク障害により生じる迂回トラヒックを考慮しながらリンク使用率を規定上限以下に抑えるという制約の範囲内で、最適な網トポロジとリンク容量を設計することが可能である。
【発明を実施するための最良の形態】
【００２８】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係る網のトポロジとリンク容量の設計を行うシステムの構成例を示すブロック図であって、本図１におけるシステムは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置からなるコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。
【００２９】
すなわち、本例の網のトポロジとリンク容量の設計を行うシステムは、プログラムされたコンピュータ処理実行手段として、入力処理装置（図中「ノート情報，交流マトリクス，経路設定法，制約条件入力装置」と記載）１０１、設計処理装置（図中「網トポロジ・リンク容量設計装置」と記載）１０２、出力処理装置（図中「最適トポロジ・最適リンク容量出力装置」と記載）１０３を具備している。
【００３０】
入力処理装置１０１は、キーボードから入力操作やファイルから読み込みにより、ノードの位置、ノード間のトラヒックデマンド量（交流マトリクス）、経路設定法（ルーティングプロトコル種別）、リンク使用率の規定上限値γと迂回トラヒックを考慮する対象のリンク数比率ε等のデータを取り込み、記憶装置に入力して記憶し、設計処理装置１０２は、入力処理装置１０１から入力されたデータを記憶装置から読み出して、これらのデータを用いて、最適な網トポロジとリンク容量を算出し、出力処理装置１０３は、入力処理装置１０１が算出した最適トポロジと最適リンク容量をＣＲＴ画面や記憶装置等に出力する。
【００３１】
このような構成のシステムにより、本例では、リンク輻輳を回避するため、リンク利用率が与えられた任意の水準以下となることを制約条件に、総コストを最小化する網のトポロジとリンク容量の設計値を算出する。より具体的には、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別（ルーティング方式）、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出するために、プログラムされたコンピュータ装置の処理実行手段として、入力処理装置１０１と、設計処理装置１０２とを具備し、入力処理装置１０１は、制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力して記憶装置に書き込み、設計処理装置１０２は、制約条件とリンク数Ｌおよびリンク数ｋとからなる情報を記憶装置から読み出し、読み出した情報を用いて、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した網トポロジとリンク容量の算出を行う。
【００３２】
トラヒックの交流マトリクスは常に変化するが、物理的な設備の設計は数ヶ月以上といった長期の時間スケールで行うため、通常、静的な交流マトリクスに基づき設計を行う必要がある。交流マトリクスは日や週といった周期的な変動を示すため、例えば最繁時のトラヒック量に基づき設計を行えば良い。
【００３３】
静的なリンク重みを用いたＯＳＰＦを用いた場合も、リンクやノードの意図しない障害によりトラヒックが流れる経路は変化し、日常的に様々なリンクで障害が発生しており（「Ａ． Ｍａｒｋｏｐｏｕｌｏｕ， Ｇ． Ｉａｎｎａｃｃｏｎｅ， Ｓ． Ｂｈａｔｔａｃｈａｒｙｙａ， Ｃ． Ｃｈｕａｈ， ａｎｄ Ｃ． Ｄｉｏｔ，“Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ ｏｆ Ｆａｉｌｕｒｅｓ ｉｎ ａｎ ＩＰ Ｂａｃｋｂｏｎｅ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００４．」参照）、リンク利用率を算出する際には、障害時の迂回トラヒックをも考慮する必要がある。
【００３４】
ＩＰバックボーンにおいて、メインテナンスに起因するものを除いた意図しない障害の約７０％は単独リンク障害であることから（「Ａ． Ｍａｒｋｏｐｏｕｌｏｕ， Ｇ． Ｉａｎｎａｃｃｏｎｅ， Ｓ． Ｂｈａｔｔａｃｈａｒｙｙａ， Ｃ． Ｃｈｕａｈ， ａｎｄ Ｃ． Ｄｉｏｔ，“Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ ｏｆ Ｆａｉｌｕｒｅｓ ｉｎ ａｎ ＩＰ Ｂａｃｋｂｏｎｅ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００４．」参照）、本例では、単一リンク障害時に発生する迂回トラヒックを考慮して、リンク使用率を規定値以下に抑える。
【００３５】
また、本例では、米国と日本のバックボーンを対象に本設計技術を用いて設計された網トポロジについて分析し、障害に伴う迂回トラヒックの収容を目的として設計される過剰帯域が、どのようなリンクに多く用意されるかについて分析する。
【００３６】
尚、本例では、単一のＩＳＰに閉じた網のうち、バックボーンの設計を対象とする。波長多重技術（ＤＷＤＭ；Ｄｅｎｓｅ Ｗａｖｅｌｅｎｇｔｈ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅｘｉｎｇ）を用いることでリンクの伝送容量の飛躍的な向上が可能であり（「Ｒ． Ｒａｍａｓｗａｍｉ ａｎｄ Ｋ． Ｎ． Ｓｉｖａｒａｊａｎ，“Ｏｐｔｉｃａｌ Ｎｅｔｗｏｒｋｓ，” Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ， ２００２．」参照）、既に、多くのＩＰバックボーンは、ルータ間に設置した伝送リンクにＤＷＤＭを用いている。
【００３７】
本例においても、リンクはＤＷＤＭにより波長多重された光心線で構成される網を想定する。また、ルーティングプロトコル種別（ルーティング方式）としてＯＳＰＦを想定する。 ＳＯＮＥＴ／ＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ Ｏｐｔｉｃａｌ ＮＥＴｗｏｒｋ／Ｓｙｎｃｈｒｏｎｏｕｓ Ｄｉｇｉｔａｌ Ｈｉｅｒａｒｃｈｙ）を用いた障害復旧は高速であるが高コストなため、近年はＩＰレイヤで障害復旧を行うＩＳＰが多い（「Ｆ． Ｇｉｒｏｉｒｅ， Ａ． Ｎｕｃｃｉ， Ｎ． Ｔａｆｔ， ａｎｄ Ｃ． Ｄｉｏｔ，“Ｉｎｃｒｅａｓｉｎｇ ｔｈｅ Ｒｏｂｕｓｔｎｅｓｓ ｏｆ ＩＰ Ｂａｃｋｂｏｎｅｓ ｉｎ ｔｈｅ Ａｂｓｅｎｃｅ ｏｆ Ｏｐｔｉｃａｌ Ｌｅｖｅｌ Ｐｒｏｔｅｃｔｉｏｎ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００３．」参照）。
【００３８】
そこで本例でもＳＯＮＥＴ／ＳＤＨは用いず、障害発生時にはＩＰレイヤでＯＳＰＦにより迂回経路が設定されることを想定する。この場合、迂回経路が安定するまでに時間を要することが問題となり、近年、事前に代替経路を計算しておくことで対処するＦＲＲ（Ｆａｓｔ ＲｅＲｏｕｔｅ）が検討されているが（「Ａ． Ａｔｌａｓ， ｅｔ ａｌ．，“Ｂａｓｉｃ ｓｐｅｃｉｆｉｃａｔｉｏｎ ｆｏｒ ＩＰ ｆａｓｔ−ｒｅｒｏｕｔｅ： ｌｏｏｐ−ｆｒｅｅ ａｌｔｅｒｎａｔｅ，” Ｉｎｔｅｒｎｅｔ ｄｒａｆｔ， ｄｒａｆｔ−ｉｅｔｆ−ｒｔｇｗｇ−ｉｐｆｒｒ−ｓｐｅｃ−ｂａｓｅ−０１．ｔｘｔ， ２００４−９．」参照）、本例では、ＯＳＰＦのみにより迂回経路が設定されることを想定する。
【００３９】
以下、本例による、リンク障害時の迂回トラヒックを考慮した網トポロジとリンク容量の設計処理技術について、詳細を説明する。
【００４０】
ＩＳＰは、リンク輻輳を避けて安定した品質をユーザに提供し続けるためには、各リンクの利用率を大雑把な規定値以下に抑えることを目標に、網を設計・運用すれば実用上は十分であると思われる。
【００４１】
すなわち、ノードｉからノードｊの間に設置されたリンク（以後、「ｅｉｊ」と表記）の使用率をｕｉｊとし、リンク使用率の規定上限をγとすると、リンクが設置された任意の組ｉ，ｊに対してｕｉｊ≦γを満たすことを制約条件とする。
【００４２】
リンクｅｉｊのリンク容量（光ネットワークにおける設計波長数）をｘｉｊとし、リンクを設置しない場合にはｘｉｊ＝０とする。リンクは双方向（ｂｉｄｉｒｅｃｔｉｏｎａｌ）とし、ｘｊｉ＝ｘｉｊとする。
【００４３】
また、交流マトリクスをＤ、ノードｓからノードｄに向かうトラヒックデマンド量をＤｓｄとし、トラヒックデマンド量Ｄｄｓ＝トラヒックデマンド量Ｄｓｄを仮定する。すなわち、交流行列（交流マトリクス）は対称形であるとし、ノードｄからノードｓに向かうパケットは、ノードｓからノードｄに向かうパケットと同一のノードとリンクを逆方向に経由する。しかし、以下に示す本例の設計手法は、交流マトリクスが非対称形であり、リンクが片方向（ｕｎｉｄｉｒｅｃｔｉｏｎａｌ）な場合にも容易に拡張可能である。
【００４４】
以下、リンク使用率制約（リンク使用率の規定上限γ）、ノードの地理的な位置、交流マトリクスＤが与えられたときに、網全体のコストＣを最小化することを目的に網トポロジとリンク容量（設計波長数ｘｉｊ）を設計する処理について説明する。
【００４５】
尚、「Ｌ． Ｌｉ， Ｄ． Ａｌｄｅｒｓｏｎ， Ｗ． Ｗｉｌｌｉｎｇｅｒ， ａｎｄ Ｊ． Ｄｏｙｌｅ，“Ａ Ｆｉｒｓｔ−Ｐｒｉｎｃｉｐｌｅｓ Ａｐｐｒｏａｃｈ ｔｏ Ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ Ｉｎｔｅｒｎｅｔ'ｓ Ｒｏｕｔｅｒ−ｌｅｖｅｌ Ｔｏｐｏｌｏｇｙ，” ＡＣＭ ＳＩＧＣＯＭＭ ２００４．」においては、実際のＩＳＰの網トポロジを調べ、トポロジを決める主要因が、「コスト」と「ルータの処理能力」から決まる制約であると分析している。
【００４６】
しかし、「ルータの処理能力」向上のペースは著しく、現在は、例えば「Ｃｉｓｃｏ ｓｙｓｔｅｍｓ， ｈｔｔｐ：／／ｗｗｗ．ｃｉｓｃｏ．ｃｏｍ．」にあるように、１．２８Ｔｂｐｓもの処理能力を備えたルータを用いることも可能であり、本例では、ルータの処理能力制約は考慮しないものとする。
【００４７】
まず、以下、網全体のコストＣについて説明する。
【００４８】
網コストＣは、ノードコストとリンクコストの総和であるが、本例では簡単のため、ルータのポートあたりのコストをＣｅｐとし、リンクの両端に必要数のルータポートが用意されると見なしてノードコストをリンクコストに含めて考える。
【００４９】
以下、リンクコストをモデル化する。本例では、ＤＷＤＭによるルータ間の波長多重リンクを想定しているため、リンクコストは、土木インフラコスト、光心線コスト、光デバイスコストから構成される。
【００５０】
土木インフラコストは、光ファイバを収容するための土管の敷設費用や、土管を保有する鉄道会社、電力会社、自治体などから土管を借りるための費用であり、１ｋｍあたりのコストをＣｃｄとする。
【００５１】
また、光心線の１ｋｍあたりのコストをＣｆｂとする。１本の光心線に多重可能な波長数には制約があることから、多重可能な波長数の上限をＷとすると、下記の数１に示す本数の光心線をリンクｅｉｊに敷設する必要がある。
【００５２】
【数１】
【００５３】
また、ＤＷＤＭ伝送を行うためには、リンクの両端において波長の多重と分離を行う波長多重分離装置と、減衰した光信号を増幅する光アンプ、そして、ｃｒｏｓｓｔａｌｋ（クロストーク ； 信号漏れ）やＡＳＥ（ａｍｐｌｉｆｉｅｄ ｓｐｏｎｔａｎｅｏｕｓ ｅｍｉｓｓｉｏｎ）やＰＭＤ（ｐｏｌａｒｉｚａｔｉｏｎ ｍｏｄｅ ｄｉｓｐｅｒｓｉｏｎ）によって劣化した光パルスを修復するリピータが必要になる（前述の「Ｒ． Ｒａｍａｓｗａｍｉ ａｎｄ Ｋ． Ｎ． Ｓｉｖａｒａｊａｎ，“Ｏｐｔｉｃａｌ Ｎｅｔｗｏｒｋｓ，” Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ， ２００２．」参照）。
【００５４】
波長多重分離装置のコストは、おおよそ波長数に比例することから、ここでは、その波長あたりのコストをＣｍｄとする。また、光アンプ１台のコストをＣａｐとする。トランスポンダ（中継機器）１台のコストをＣｔｐとすると、光パルスの整形は電気信号に変換してから行う必要があることから、１箇所のリピータで必要になるコストは（Ｃｔｐ＋２Ｃｍｄ）ｘｉｊとなる。
【００５５】
従って、距離が「ｄｉｊ」で設計波長数（設計リンク容量）が「ｘｉｊ」のリンクｅｉｊのコストｃｉｊ（ｄｉｊ，ｘｉｊ）は、下記の式となる。
【００５６】
ｃｉｊ（ｄｉｊ，ｘｉｊ）＝Ｃｃｄｄｉｊ＋｛α（ｄｉｊ）＋β（ｄｉｊ）Ｗ｝ｙｉｊ＋α（ｄｉｊ）δｉｊ（ｚｉｊ）＋β（ｄｉｊ）ｚｉｊ。
【００５７】
ただし、上記式において、「ｙｉｊ」は、上限であるＷ本の波長が多重された光心線の本数であり、「ｚｉｊ」は、Ｗに満たない本数の波長が多重された残り１本の光心線における多重波長数であり、下記の数２に示す式となる。
【００５８】
【数２】
【００５９】
また、「δｉｊ（ｚｉｊ）」を、「ｚｉｊ≧１」のとき「δｉｊ（ｚｉｊ）＝１」で、「ｚｉｊ＝０」のとき「δｉｊ（ｚｉｊ）＝１」となる関数と定義する。
【００６０】
さらに、「α（ｄｉｊ）」は、１本の光心線に必要なコストのうち距離にのみ依存した項であり、「β（ｄｉｊ）」は設計波長数（設計リンク容量）に比例する項であり、次の数３に示す式で与えられる。
【００６１】
【数３】
【００６２】
ただし、上記数３において、「Δａｐ」と「Δｒｐ」は、各々、光アンプとリピータの設置間隔である。
【００６３】
次に、「設計アルゴリズム」について説明する。
【００６４】
まず、網トポロジとリンク容量の設計問題を定式化する。
【００６５】
与えられたノード集合に対して任意に設計した網トポロジをＴとし、網トポロジＴに含まれるエッジ（リンク）の集合をＥとする。そして、網トポロジＴから、集合Ｅに含まれる任意のリンクｅｉｊを除去した網トポロジを下記の数４に示すものとする。
【００６６】
【数４】
【００６７】
各発着ノード間の、パケットが流れる経路は、固定的に定めたリンク重みを用いたＯＳＰＦにより設定されることを想定する。
【００６８】
上述の「リンクコストのモデル化」で説明したように、リンクコストは、距離（ｄｉｊ）と設計波長数（リンク容量ｘｉｊ）に依存するが、距離（ｄｉｊ）は、設計量に独立であり、固定的な重みとして用いるのが容易であることから、本例では、リンク重みとしてリンク距離ｄｉｊを用いる。
【００６９】
総コストＣは、上述の『距離が「ｄｉｊ」で設計波長数が「ｘｉｊ」のリンクｅｉｊのコストｃｉｊ（ｄｉｊ，ｘｉｊ）』を用いて次の数５に示す式で得られる。
【００７０】
【数５】
【００７１】
網トポロジＴと交流マトリクスＤに対して、正常時にリンク集合Ｅに含まれるリンクｅｉｊを流れる、下記の数６の記号で示されるトラヒック量は、下記の数７に示すようになる。
【００７２】
【数６】
【００７３】
【数７】
【００７４】
ただし、上記数７における「Ｐｓｄ（Ｔ）」は、網トポロジＴにおいて発ノードｓから着ノードｄに向かうトラヒックが経由するリンクの集合である。
【００７５】
また、下記の数８の記号で示される網トポロジにおいて同一の交流マトリクスＤを与えたときに、当該網トポロジの、下記の数９の記号で示されるエッジ集合に含まれる任意のリンクｅｉｊを流れるトラヒック量を、下記の数１０の記号で示されるものとすると、それぞれ、下記の数１１に示す関係式となる。
【００７６】
【数８】
【００７７】
【数９】
【００７８】
【数１０】
【００７９】
【数１１】
【００８０】
任意の単一リンク障害時にも、各リンクの使用率を規定上限γ以下に抑えるためには、集合Ｅの各リンク（下記の数１２参照）に対して、下記の数１３で定義される最大トラヒック量を想定し、下記の数１４の式が満たされれば良い。ただし、数１４におけるＢは波長の伝送帯域である。
【００８１】
【数１２】
【００８２】
【数１３】
【００８３】
【数１４】
【００８４】
集合Ｅに含まれるリンクの本数をＬとすると、Ｌ本全てのリンクを対象に、単一リンク障害に伴う迂回トラヒックを考慮してリンク容量を設計すると、正常時に各リンクを流れる、トラヒック量（数６参照）と比較して、非常に大きな帯域を過剰設計することが予想される。
【００８５】
そこで、リンク障害を考慮する対象のリンクをＬ本の全てではなく、下記の数１５で与えられるｋ本のリンクに限定することを考える。ただし、数１５におけるεは０≦ε≦１の範囲の値をとる設計パラメタである。
【００８６】
【数１５】
【００８７】
正常時に各リンクに流れるトラヒック量（数６参照）が大きなリンクほど、障害時に発生する迂回トラヒック量が大きいことから、正常時に各リンクに流れるトラヒック量（数６参照）が大きな上位ｋ本のリンクに対してのみ迂回トラヒックを考慮する。
【００８８】
ただし、任意の単一リンク障害時にも全ノード間の接続性を維持することを制約条件に考え、残るＬ−ｋ本のリンクに対しては、単一障害時に孤立ノードが発生するか否かの判定を行う。
【００８９】
以上のことから、本例の網トポロジとリンク容量の設計問題（設計波長数ｘｉｊの決定問題）は、以下の数１６に示す整数計画問題として表現できる。
【００９０】
【数１６】
【００９１】
ただし、数１６の制約式における、上位ｋ本に限定したリンクに対して定義される最大トラヒック量は、下記の数１７となる。
【００９２】
【数１７】
【００９３】
上記数１７において、Ｅ（ｋ）は、集合Ｅに含まれるリンクのうち、正常に流れるトラヒック量（数６参照）が大きな上位ｋ本のリンク集合である。
【００９４】
また、上記数１７の制約式における下記の数１８で示す値は、下記の数１９で示すリンク集合のリンク重みの総和であり、上記数１６の制約式におけるＥ（Ｌ−ｋ）は、集合Ｅから迂回トラヒックを考慮するｋ本のリンクを除いたリンク集合である。
【００９５】
【数１８】
【００９６】
【数１９】
【００９７】
しかし、この種の整数計画問題は、ＮＰ困難な問題（条件を満たす解の数が膨大で、最も良い解を現実的な時間で求めるのが難しい問題）であり、多項式時間で厳密な最適解を得ることができないことが知られている（前述の「非特許文献１０」参照）。
【００９８】
そのため、大規模な問題に対しても現実的な計算時間で近似最適解が得られるよう、「ローカルサーチ」、「タブサーチ」、「遺伝的アルゴリズム」、「焼きなまし法」、といった様々なヒューリスティックな解法が開発されている（「柳浦睦憲，茨木俊秀，“組合せ最適化，” 朝倉書店， ２００４．」参照）。
【００９９】
一般に、各々の近似解法には問題に対する相性があり、汎用的に優れた解法は存在しないため、本例では、近似解法の詳細な評価には立ち入らず、局所探索法と並ぶ近似アルゴリズムの基本手法の一つである「貪欲算法」を用いる。
【０１００】
この「貪欲算法」は、初期状態からスタートし、目的関数値が最も大きく改善すると思われる解の修正を、目的関数値の改善が見られなくなるまで反復する手法である。
【０１０１】
本例では、全ノード間にフルメッシュにリンクを設置した状態（完全グラフ）からスタートし、１本ずつリンクを除去するアプローチを用いる（前述の「非特許文献１２」を参照）。
【０１０２】
この手法によれば、あるリンクを除去することでそのリンクを経由していたトラヒックが他のリンクにまわるが、最小コストとなる経路が常に選択されるため、網全体としては消費されるリンク資源量が増加する。このコスト増加分に対してリンクを除去することによるコスト減少分が大きなリンクほど、除去することによる総コストの改善効果が期待できる。
【０１０３】
よって、リンクコストが大きく、流れるトラヒック量が小さいリンク、すなわち、下記の数２０に示す値が大きなリンクを優先的に除去する。
【０１０４】
【数２０】
【０１０５】
以下に、このような「貪欲算法」を用いた本発明に係る網トポロジとリンク容量の設計アルゴリズムを、図８を用いて説明する。図８は、図１におけるシステムによる本発明に係る網トポロジ・リンク容量設計処理動作例を示すフローチャートである。
【０１０６】
（１）まず、初期設定処理を行う（ステップＳ８０１）。すなわち、全ノード間にリンクを設置し、前述の数１７の式より、正常時に各リンクに流れるトラヒック量（数６参照）が大きな上位ｋ本のリンクに対して定義される最大トラヒック量（下記の数２１参照）を算出し、また、前述の数５の式より、当該網の総コストＣを算出する。
【０１０７】
【数２１】
【０１０８】
（２）次に、リンク評価値の算出を行う（ステップＳ８０２）。すなわち、下記の数２２の式で示すリンクｅｉｊの評価値ａｉｊを、全リンクに対して各々算出し、評価値ａｉｊの大きな順にソートする。また、ｊ＝１とする。
【０１０９】
【数２２】
【０１１０】
（３）さらに、リンク除去後の総コストを算出する（ステップＳ８０３）。すなわち、リンクｅｉｊの評価値ａｉｊがｊ番目に大きなリンクｅｉ’ｊ’を除去したトポロジ（下記の数２３参照）に対して、前述の数１７の式より、正常時に各リンクに流れるトラヒック量（数６参照）が大きな上位ｋ本のリンクに対して定義される最大トラヒック量を算出し、前述の数５の式より、当該網の総コストＣを算出する。また、集合Ｅ（Ｌ−ｋ）に含まれるリンクを各々除去した場合にも全ノード間の接続性が維持されるか否かを調べる。
【０１１１】
【数２３】
【０１１２】
（４）そして、リンク除去の実施判定を行う（ステップＳ８０４）。すなわち、総コストＣが減少し、かつ、集合Ｅ（Ｌ−ｋ）に含まれる任意のリンク（下記の数２４参照）の単一障害時にも全ノード間の接続性が維持される場合には、上述の「（２）リンク評価値の算出」処理に進み、そうでない場合には、該当リンクを除去しないで「ｊ」を「１」だけ増加させて、上述の「（３）リンク除去後の総コスト算出」処理に進む。「ｊ＝Ｌ」の場合には終了。
【０１１３】
【数２４】
【０１１４】
このような処理を、本例のシステムでは、ハードディスク装置等に記憶されたプログラムをＣＰＵが順次に読み込みコンピュータ処理を実行し、各処理で生成したデータを主メモリ等の記憶装置に記憶し、また、記憶したデータを読み出して次の処理で用いる動作を以下手順で順次に行うことで実現する。
【０１１５】
すなわち、入力処理装置１０１は、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力して記憶装置に書き込む第１の手順を実行し、設計処理装置１０２は、制約条件を記憶装置から読み出す第２の手順と、読み出した制約条件を用いて、全ノード間に設置される各リンクに対して、当該リンクのコストと当該リンクの使用率を規定値γ以下に抑える最大トラヒック量とを算出して記憶装置に書き込む第３の手順と、この第３の手順で算出した各リンクのコストを加算して網全体のコストである総コストを算出し記憶装置に書き込む第４の手順と、第３の手順で算出した各リンクのコストを当該リンクに正常時に流れるトラヒック量で除した値を当該リンクの評価値として算出しソートして記憶装置に書き込む第５の手順と、この第５の手順でソートした各リンクの評価値が一番大きなリンクを除去した残りの各リンクに対して、上述のコストと最大トラヒック量の算出と記憶装置への書き込みを行う６の手順と、この第６の手順で算出した各リンクのコストを加算してリンクを除去した後の網全体の総コストを算出し記憶装置に書き込む第７の手順と、この第７の手順で算出した総コストが第４の手順で算出した総コストより減少するか否か、および、残りの各リンクの各々の単一障害時にも全ノード間の接続性が維持されるか否かを判別する第８の手順と、この第８の手順で、総コストが減少することおよび全ノード間の接続性が維持されることを判別した場合は、当該リンクを除去して上述の第５の手順からの処理を繰り返す第９の手順と、上述の第８の手順で、総コストが減少せず、もしくは、全ノード間の接続性が維持されないと判別した場合は、当該リンクを除去しないで上述の第４の手順で算出した評価値が次に大きなリンクを除去して、上述の第６の手順からの処理を繰り返す第１０の手順と、この第１０の手順による第６の手順からの繰り返し処理を、予め定められたリンク数で終了する第１１の手順とを実行する。
【０１１６】
尚、前述の「（３）リンク除去後の総コスト算出」処理（図８のステップＳ８０１）において、リンクｅｉ’ｊ’を除去したことで経路に影響を受けるトラヒックは、当該リンクｅｉ’ｊ’を通るもののみであり、全ての発着ノードペアに対して経路を再計算することは非効率的である。
【０１１７】
そこで、本例では、各リンクｅｉｊに対して、リンクｅｉｊを経由する発着ノードペアの集合を管理することで、影響を受ける発着ノードペアに対してのみ経路を再計算する。
【０１１８】
同様に、単一リンク障害時の迂回トラヒック量を計算する際も、障害が生じたリンクを経由する発着ノードペアに対してのみ迂回経路を算出する。
【０１１９】
また、「（３）リンク除去後の総コスト算出」処理における「接続性の維持の判定」は、ダイクストラ法を適用した際の経路のコストが、任意の発着ノード間に対して有限値として得られるか否かで行う。
【０１２０】
すなわち、ノード数をＮとすると、ダイクストラ法の計算量はＯ（Ｎ２）となる。初期状態は、完全グラフでスタートするため、アルゴリズムの早い時点においてはＯ（Ｎ２）本のリンクが存在するが、各リンクを経由する発着ノードペア数は、全ペア数Ｎ（Ｎ−１）／２と比較して遥かに小さい。よって、「（３）リンク除去後の総コスト算出」処理における計算量は、おおよそＯ（Ｎ４）となる。よって、全体では、Ｏ（Ｎ６）程度の計算量になる。
【０１２１】
以下、本例の網トポロジとリンク容量の設計による数値評価結果を説明する。ここでは、ノード間の距離ｄｉｊは、ノードｉとノードｊ間の直線距離（ユークリッド距離）とし、リンク使用率の規定上限γ＝０．７とし、また、光心線の多重波長数の上限Ｗ＝６０、波長の伝送帯域Ｂ＝１０Ｇｂｐｓ、光アンプの設置間隔Δａｐ＝８０ｋｍ、リピータの設置間隔Δｒｐ＝２０００ｋｍとする。
【０１２２】
コストは、全て相対値で考え、現状の価格を考慮して、「光心線の１ｋｍあたりのコストＣｆｂ＝０．１」、「光アンプ１台のコストＣａｐ＝２４０」、「トランスポンダ１台のコストＣｔｐ＝７５」、「ルータのポートあたりのコストＣｅｐ＝４０」、「波長あたりのコストＣｍｄ＝３．３」と設定する。
【０１２３】
ただし、土木インフラコストは、地理的要因や契約形態に大きく依存し、適切に設定することが困難であるため考慮しないものとする（Ｃｃｄ＝０）。
【０１２４】
また、評価は、全米の大学や企業が参加するインターネット２の基盤となるバックボーンである「Ａｂｉｌｅｎｅ」を対象に実施した。「Ａｂｉｌｅｎｅ」は、全米に配置された１１のノードから構成される。
【０１２５】
ノード位置は公開されている情報を用いる（「Ａｂｉｌｅｎｅ ｔｏｐｏｌｏｇｙ ａｎｄ ｔｒａｆｆｉｃ ｄａｔａｓｅｔ． ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｕｔｅｘａｓ．ｅｄｕ／〜ｙｚｈａｎｇ／ｒｅｓｅａｒｃｈ／ＡｂｉｌｅｎｅＴＭ／」参照）。また総トラヒック量がＶとなるよう、交流マトリクスは同様に公開されている実測値に比例するよう配分する。
【０１２６】
ただし、全米の２００６年末時点の総トラヒック量が１．３９〜２．４７Ｔｂｐｓであったことから（「Ｍｉｎｎｅｓｏｔａ Ｉｎｔｅｒｎｅｔ Ｔｒａｆｆｉｃ Ｓｔｕｄｉｅｓ （ＭＩＮＴＳ）． ｈｔｔｐ：／／ｗｗｗ．ｄｔｃ．ｕｍｎ．ｅｄｕ／ｍｉｎｔｓ／ｈｏｍｅ．ｈｔｍｌ」参照）、総トラヒック量Ｖ＝１Ｔｂｐｓと１０Ｔｂｐｓの場合について各々評価する。
【０１２７】
ここでは、単一障害時の迂回トラヒックを考慮するリンク数ｋの全リンク数Ｌに対する比率εが各種性能に与える影響を評価する。
【０１２８】
図２は、図１におけるシステムによる網トポロジの設計例を示す説明図であり、本図２においては、単一障害時の迂回トラヒックを考慮するリンク数ｋの全リンク数Ｌに対する比率εの３つの値に対して、各々、設計された網トポロジを示している。
【０１２９】
まず、「総トラヒック量Ｖ＝１Ｔｂｐｓ」の場合、図２の（ａ）〜（ｃ）について見ると、比率ε＝０（迂回トラヒックを全く考慮しない）のとき、図２の（ａ）に示すように、正常時のトラヒック流量が最大のリンクは（２，５）で、次に流量の大きいリンクは（４，５）であった。
【０１３０】
比率εを小さな値に設定すると、これらトラヒック流量の大きな特定のリンクの障害時の迂回トラヒックのみが考慮される。比率ε＝０のとき、これらリンクは大きなループの一部を担っているため、これらリンクで障害が発生すると、迂回トラヒックが多数のリンクを経由するため非効率的である。
【０１３１】
そこで、例えば、比率ε＝０．１のとき、図２の（ｂ）に示すように、これらリンクの障害時の迂回トラヒックが効率的にショートカットされるリンク（３，５）が追加されることが確認できる。
【０１３２】
一方、比率εが大きく「１」に近い場合には、多数のリンクに対して単一リンク障害時の迂回トラヒックを考慮する結果、図２の（ｃ）に示すように、多数の発着ノード間の迂回トラヒックを、共通のリンクで効率よく収容できるループを組み合わせた網トポロジとなることが確認できる。
【０１３３】
また、リンクｅｉｊの設計リンク容量から、正常時に流れるトラヒック量を引いたものを過剰設計帯域Ｅｘ（ｅｉｊ）と定義すると、この過剰設計帯域Ｅｘ（ｅｉｊ）が下記の数２５のとき、リンク（１，１１）と（１，５）の過剰設計帯域Ｅｘ（ｅｉｊ）が突出して大きかった。
【０１３４】
【数２５】
【０１３５】
これは、全リンク数Ｌ＝１４で、単一障害時の迂回トラヒックを考慮するリンク数ｋ＝２となり、正常に流れるトラヒック量（前述の数６，７参照）の大きい上位二本のリンクが（５，８）と（８，１１）であり、これらのリンクと同一のループを形成するためである。
【０１３６】
「Ａｂｉｌｅｎｅ」では、東海岸に人口の大きな都市が集中しており、正常に流れるトラヒック量（前述の数６，７参照）が大きなリンクが特定の地域に集中する傾向がある。このような場合、比率εを小さく設定すると、帯域を過剰設計するリンクもそのような地域に集中する傾向が見られる。
【０１３７】
図３は、各リンクの正常時のリンク使用率を値の大きな順にプロットした例の説明図であり、比率ε＝０の場合、全リンクの使用率が、規定上限γ（＝０．７）に近い値となるが、比率ε＝０．１の場合には、少数のリンクの利用率が大きく低下し、また、比率εが０．４より大きい場合は、リンク利用率のばらつきが大きく、規定上限γ（＝０．７）に近いものから小さなものまで幅広く分布することが確認できる。
【０１３８】
一方、「総トラヒック量Ｖ＝１０Ｔｂｐｓ」の場合には、Ｖ＝１Ｔｂｐｓのときと比較して交流トラヒック量が大きく、複数の対地間でトラヒックを集約しなくても、波長帯域と比較して十分なトラヒック量が対地間で確保できるため、図２の（ｄ）〜（ｆ）に示すように、多数の対地に対してダイレクトリンクが設置される。
【０１３９】
次に、比率εの値の差異に応じて、どの程度異なった網トポロジが設計されるかを確認するため、二つのトポロジＡとトポロジＢの一致度η（Ａ，Ｂ）を、「η（Ａ，Ｂ）＝ｎ（Ａ∩Ｂ）／ｎ（Ａ∪Ｂ）」で定義する。ただし「ｎ（Ａ∩Ｂ）」と「ｎ（Ａ∪Ｂ）」は、各々、トポロジＡとトポロジＢに含まれるリンクの積集合と和集合のリンク数である。
【０１４０】
図４は、二つのトポロジの一致度例を示す説明図である。図４の（ａ）においては、比率ε＝０における設計トポロジＴ（ε＝０）との一致度を、図４の（ｂ）においては、比率ε＝１における設計トポロジＴ（ε＝１）との一致度をεに対して各々示す。
【０１４１】
図４の（ａ）においては、比率εの増加に伴い、設計トポロジＴ（ε＝０）との一致度が減少する反面、図４の（ｂ）においては、比率εの増加に伴い、設計トポロジＴ（ε＝１）との一致度が増加する。
【０１４２】
図４の（ｂ）において、設計トポロジＴ（ε＝１）との一致度は、比率εの値に関係なく７０％程度以上と高い。よって、設計されるトポロジの形に、比率εが及ぼす影響は全体としては小さいといえる。
【０１４３】
図５は、図１におけるシステムで設計したトポロジのリンク数および設計リンク容量の平均値と単一障害時の迂回トラヒックを考慮するリンク数の全リンク数に対する比率との対応関係を示す説明図であり、設計トポロジのリンク数Ｌと、設計リンク容量ｘｉｊの平均値を、比率εに対して示している。
【０１４４】
図４で示したように、単一障害時の迂回トラヒックを考慮するリンク数の全リンク数に対する比率εが、設計トポロジに及ぼす影響は小さく、この比率εの変化に対して、設計トポロジのリンク数Ｌはあまり変化しない。
【０１４５】
一方、比率εの増加に伴い、より多数の単一リンク障害パターンの迂回トラヒックを考慮するため、平均設計リンク容量は増加する。しかし、比率εが中程度より大きな領域では、比率εを増加させても、設計リンク容量はほとんど変化しない。
【０１４６】
この傾向は、図５の（ｃ）に示すように、平均過剰設計帯域（Ｅｘ（ｅｉｊ）の全リンクにわたる平均値）の、比率εに対する特性からも確認できる。これは、正常時のトラヒック量（前述の数６参照）が大きな半数程度のリンクの障害時の迂回トラヒックを考慮してリンク容量を設計すれば、残るリンクの障害時に発生する迂回トラヒックの多くも吸収できることが理由である。
【０１４７】
その結果、図５の（ｄ）に示すように、比率εが中程度以上の領域では、比率εの増加に対して総コストはほとんど増加しなくなる。
【０１４８】
次に、図６を用いて、単一リンク障害時の特性について考察する。図６は、単一リンク障害時のリンク使用率のプロット例を示す説明図であり、図６の（ａ）においては、全ての（Ｌ個の）単一リンク障害パターンにおける各リンクの使用率の平均値を降順にプロットした例を示し、また、図６の（ｂ）においては、Ｌ個の単一リンク障害パターン中の最大利用率を各リンクについて降順にプロットした例を示している。
【０１４９】
ここでは、総トラヒック量Ｖ＝１０Ｔｂｐｓの結果についてのみ示し、図６の（ａ）においては、比率εが「０」や「０．１」の場合、想定していないリンクの障害に伴う迂回トラヒックにより、多数のリンクの平均利用率が、規定上限γ＝０．７を超えている。
【０１５０】
特に、図６の（ｂ）に示すように、少数のリンクの最大リンク使用率が非常に高くなることが確認できる。特に、最大利用率が最も高いリンク（７，９）の障害時利用率が突出して高いが、このリンクの正常時のトラヒック量は、全リンク中で最小であり、比率εを「０」や「０．１」としたときの過剰設計帯域も最小となっている。
【０１５１】
このように、正常時のトラヒック量（前述の数６参照）が大きな少数のリンクのみに限定して障害時の迂回トラヒックを考慮しても不十分である。
【０１５２】
図７は、単一リンク障害時の全リンクにわたるリンク使用率の平均値と最大値の比率に対するプロット例を示す説明図であり、図７の（ａ）においては、全ての単一リンク障害パターンの全リンクにわたるリンク使用率の平均値と最大値を、比率εに対してプロットしており、また、図７の（ｂ）においては、単一リンク障害時にリンク使用率が規定値γ＝０．７を超過したリンクを経由するトラヒック量の全トラヒック量Ｖに対する比率を示している。
【０１５３】
図７の（ａ）に示すように、比率εの増加に伴い、規定上限を超過し、輻輳状態になったリンクを経由するトラヒック量は、指数的に減少することが確認できる。
【０１５４】
また、図７の（ｂ）に示すように、トラヒック量Ｖが大きな方が、同一の比率εに対するｋ（トラヒック量（前述の数６参照）が大きな上位リンクの本数）の値が大きくなるため、超過比率は低くなる。
【０１５５】
比率εが中程度より低い場合、単一リンク障害時に無視できない割合のトラヒックが輻輳リンクを経由することになるため、比率εは中程度以上に設定することが望ましい。また、全トラヒックに対して常にリンク利用率の規定上限を満たすには、比率εを「１」に近い値に設定する必要があるが、比率εが中程度以上の領域では、前述したように、比率εを増加させても総コストはほとんど増加しない。
【０１５６】
以上のことから、比率ε＝１に設定すべきであると結論できる。
【０１５７】
以上、図１〜図８を用いて説明したように、本例では、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別（ルーティング方式）、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出するために、プログラムされたコンピュータ装置の処理実行手段として、入力処理装置１０１と、設計処理装置１０２とを具備し、入力処理装置１０１は、制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力して記憶装置に書き込み、設計処理装置１０２は、制約条件とリンク数Ｌおよびリンク数ｋとからなる情報を記憶装置から読み出し、読み出した情報を用いて、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した網トポロジとリンク容量の算出を行う。
【０１５８】
また、設計処理装置１０２は、網トポロジとリンク容量の算出を、全ノード間にリンクを設置した状態からスタートし、正常時に流れるトラヒック量でリンクコストを除した値が大きなリンクから優先的に除去する処理を、総ネットワークコストの改善が見られなくなるまで反復する。
【０１５９】
より詳細には、設計処理装置１０２は、制約条件を記憶装置から読み出し、読み出した制約条件を用いて、全ノード間に設置される各リンクに対して、当該リンクのコストと当該リンクの使用率を規定値γ以下に抑える最大トラヒック量とを算出して記憶装置に書き込むと共に、算出した各リンクのコストを加算して網全体のコストである総コストを算出し記憶装置に書き込み、また、算出した各リンクのコストを当該リンクに正常時に流れるトラヒック量で除した値を当該リンクの評価値として算出しソートして記憶装置に書き込み、ソートした各リンクの評価値が一番大きなリンクを除去した残りの各リンクに対して、コストと最大トラヒック量の算出と記憶装置への書き込みを行い、さらに、ここで算出した各リンクのコストを加算してリンクを除去した後の網全体の総コストを算出し記憶装置に書き込み、この算出した総コストが先に算出した総コストより減少するか否か、および、残りの各リンクの各々の単一障害時にも全ノード間の接続性が維持されるか否かを判別し、総コストが減少することおよび全ノード間の接続性が維持されることを判別した場合は、当該リンクを除去して上記リンクの評価値の算出手順からの処理を繰り返し、総コストが減少せず、もしくは、全ノード間の接続性が維持されないと判別した場合は、当該リンクを除去しないで、評価値が次に大きなリンクを除去して、残りのリンクに対する最大トラヒックとコストの算出を繰り返し、この繰り返し処理を、予め定められたリンク数で終了する。
【０１６０】
また、設計処理装置１０２は、リンクを除去（削除）した際、除去（削除）したリンクを通るパスに対してのみ経路を再計算することで、計算時間を抑える。
【０１６１】
また、設計処理装置１０２は、接続性の維持の判定を、ダイクストラ法を適用した際の経路のコストが任意の発着間ノード間に対して有限値として得られる否かで行う。
【０１６２】
このように、本例では、ノードの位置と、ノード間の交流トラヒック行列と、経路設定法と、リンク使用率の規定上限とが与えられているときに、任意の単一リンク障害により生じる迂回トラヒックを考慮しながらリンク使用率を規定上限以下に抑えるという制約の範囲内で、最適な網トポロジとリンク容量を設計することができる。
【０１６３】
尚、本発明は、図１〜図８を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、光ネットワークを例に説明したが、これに限定されるものではない。
【０１６４】
また、本例では、単一リンクのみを考慮したが、さらに、単一ノード障害を考慮する場合にも適用できる。この場合、各ノードに接続された全リンクに障害が発生したと見なし、各リンクの最大トラヒック量を算出する際に、各ノード障害時の迂回トラヒックを同時に考慮する。
【０１６５】
また、本例のコンピュータ装置の構成に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１６６】
【図１】本発明に係る網のトポロジとリンク容量の設計を行うシステムの構成例を示すブロック図である。
【図２】図１におけるシステムによる網トポロジの設計例を示す説明図である。
【図３】各リンクの正常時のリンク使用率を値の大きな順にプロットした例の説明図である。
【図４】二つのトポロジの一致度例を示す説明図である。
【図５】図１におけるシステムで設計したトポロジのリンク数および設計リンク容量の平均値と単一障害時の迂回トラヒックを考慮するリンク数の全リンク数に対する比率との対応関係を示す説明図である。
【図６】単一リンク障害時のリンク使用率のプロット例を示す説明図である。
【図７】単一リンク障害時の全リンクにわたるリンク使用率の平均値と最大値の比率に対するプロット例を示す説明図である。
【図８】図１におけるシステムによる本発明に係る網トポロジ・リンク容量設計処理動作例を示すフローチャートである。
【符号の説明】
【０１６７】
１０１：入力処理装置（ノート情報，交流マトリクス，経路設定法，制約条件入力装置）、１０２：設計処理装置（網トポロジ・リンク容量設計装置）、１０３：出力処理装置（最適トポロジ・最適リンク容量出力装置）。
【技術分野】
【０００１】
本発明は、インターネット等における網のトポロジとリンク容量の設計技術に係り、特に、網トポロジ設計問題において、単一リンク障害時に発生する迂回トラヒックを考慮して、任意のリンクの使用率を任意に定めた上限値以下に抑えることを制約条件に、総コストを最小化することにより、最適な網トポロジとリンク容量を求める技術に関するものである。
【背景技術】
【０００２】
インターネットは個々のフローの状態を網内で管理せず、受信アドレスにのみ基づきルーティング処理が行われる。各ＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅｓ Ｐｒｏｖｉｄｅｒ）が管理する単一ＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）内では、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）により固定的に設定されたリンク重みの総和が最小となる経路上にパケットが転送される。
【０００３】
また、フローの受付制御を行わず転送レートは送信ホストが自律的に決定するため、原理的にリンク輻輳が発生し得る。そのため適切な通信品質を維持するために、網を構成する全てのリンクの利用率が適切な水準以下となるよう網を設計・管理することがＩＳＰの主要な課題の一つとなる。
【０００４】
リンク使用率は、各リンクの設計帯域と流れるトラヒック量とで決まるが、トラヒック量は、交流トラヒックデマンド量の変動や各種障害に起因する経路の変更によって常に変化する。そのため、利用率の低いリンクを積極的に利用するようパケットの流れる経路を動的に設定し、リンク負荷の分散を図るトラヒックエンジニアリング（ＴＥ）が数多く検討されている。
【０００５】
例えば、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）を用いれば発着ノードペア間に明示的にパスを設定できる。非特許文献１においては、各発着ノード間のトラヒックを設置可能な複数のパス間で平準化する設計技術が提案されており、また、非特許文献２，３においては、リンク負荷が網全体で平準化されるようＯＳＰＦの固定的なリンク重みを設定する技術が提案されている。
【０００６】
またＯＳＰＦは、リンクやノードの障害時、自律的に迂回経路を算出するが、例えば、非特許文献４においては、障害時に生成される迂回トラヒックに着目し、いくつかの障害パターンにおいてリンク負荷がうまく分散されるよう、ＯＳＰＦのリンク重みのパターンを各々用意することが検討されている。
【０００７】
これらの技術では、事前に想定した静的な交流マトリクス（発着ノードペアごとのトラヒック量を行列表現したもので、ｉ行ｊ列の要素が、ノードｉからノードｊに向かうトラヒック量となり、「交流行列」、「デマンド行列」、「トラヒック交流」等ともいう）に基づき経路の最適化を行うが、例えば、非特許文献５，６においては、リアルタイムに計測したリンク使用率に基づき、動的にパケットの流れる経路を最適化することも検討されている。
【０００８】
このようなＴＥを用いればリンク負荷を平準化することが可能であり、交流マトリクスが動的に変化する場合（非特許文献５，６）や、リンク・ノード障害により迂回トラヒックが発生する場合（非特許文献４）にも、網資源を有効に活用して輻輳の発生を最小限に抑えることが可能となる。
【０００９】
しかしながら、リンク利用率は、交流マトリクスや経路だけでなく、網トポロジやリンク容量にも依存する。
【００１０】
前述のＴＥでは、網トポロジやリンク容量が既知のものとして与えられることを前提としている。一方で、網トポロジやリンク容量は、網の構築コストや運営コストを決める大きな要因となりＩＳＰの経営に及ぼす影響が大きい。
【００１１】
従って、ＩＳＰは、自身が運営する網のトポロジやリンク容量を自由に設計することができ、これらを適切に設計することが良好な通信品質を低コストで保つためには重要となる。
【００１２】
また、ＴＥによって経路を動的に設定した場合、静的なリンク重みを用いたＯＳＰＦで定まる経路と比較して、経由するリンク数（ホップ数）が増加する。
【００１３】
そのため、網資源の消費を抑える観点からは、ＴＥを用いずに、静的なリンク重みを用いたＯＳＰＦで経路を設定することが望ましい。
【００１４】
また、ルーティングプロトコル種別（ルーティング方式）としてＯＳＰＦを想定し、通信品質を規定値以上に保つために必要なリンク容量の設計手法が、例えば、非特許文献７において検討されているが、この技術でもやはり網トポロジは、設計対象とせず、与えられることを想定している。
【００１５】
以下、ＩＳＰ自身が網を運営するにあたって、良好な通信品質を低コストで保つために重要となる、網トポロジやリンク容量の適切な設計について説明する。
【００１６】
網トポロジは、網コスト、伝送遅延、負荷の分散度合い、信頼性、といった様々な評価尺度に影響を与える。そのため、網トポロジを評価し設計する際には、これら複数の評価尺度を同時に考慮して最適性を評価する必要がある。
【００１７】
例えば、本願の発明者らによる非特許文献８，９においては、複数評価尺度を同時に考慮可能なＤＥＡ（Ｄａｔａ Ｅｎｖｅｌｏｐｍｅｎｔ Ａｎａｌｙｓｉｓ）やＡＨＰ（Ａｎａｌｙｔｉｃａｌ Ｈｉｅｒａｒｃｈｙ Ｐｒｏｃｅｓｓ）を用いて網トポロジを評価する技術が記載されている。
【００１８】
また、各リンクの利用率は、交流マトリクスが与えられ、トポロジ、リンク容量、経路の３つが定まれば決定する。従って、伝送遅延といったユーザの体感品質や、負荷の分散度合いといった各リンクの使用率に関連する品質尺度に対する制約条件を導入すれば、総コストという単一の評価尺度を最適化する整数計画問題となる。
【００１９】
すなわち、ノード位置と交流マトリクス、そしてリンク使用率（もしくはパケットの転送遅延や設計リンク容量）に関連する制約条件に対して総コストを最小化するよう、網トポロジ・リンク容量・経路を同時に最適化する問題となる。このことは、例えば、非特許文献１０において記載されている。
【００２０】
このようにトポロジ設計問題を整数計画問題とみなして解くアプローチは、既に数多く検討されている。例えば、非特許文献１１，１２においては、各ノード間の遅延時間を規定上限値以下に抑えることを制約条件に、総リンクコストを最小化する離散最適化問題を「Ｂｒａｎｃ ｈａｎｄ Ｂｏｕｎｄ法」によりヒューリスティックに解く技術、同様の問題を、多数のリンクが設置された状態からスタートし、１本ずつリンクを除去する作業を解の改善が大きな順に解の改善が見られなくなるまで繰り返す「貪欲算法」により解く技術などが検討されている。
【００２１】
しかし、これらのトポロジ設計技術では障害が考慮されていない。障害を考慮したトポロジ設計技術としては、例えば、非特許文献１３に記載のように、各ノード間にｄｉｓｊｏｉｎｔな経路が規定数以上存在することを制約条件に、総リンクコストを最小化する離散最適化問題をローカルサーチによりヒューリスティックに解く技術や、非特許文献１４に記載のように、任意の単一ノード障害においても全ノード間の接続性が維持されることを制約条件に、やはりリンクコストの総和が最小化するようタブサーチや遺伝アルゴリズムといったヒューリスティックな解法で解く技術が検討されている。
【００２２】
しかし、これらの技術は、障害時の接続性のみを考慮しており、障害時に発生する迂回トラヒックに対しても品質を規定水準内に保つことを考慮した研究は見られない。
【００２３】
【非特許文献１】Ｄ．Ｍｉｔｒａ ａｎｄ Ｋ．Ｒａｍａｋｒｉｓｈｎａ，“Ａ Ｃａｓｅ Ｓｔｕｄｙ ｏｆ Ｍｕｌｔｉｓｅｒｖｉｃｅ Ｍｕｌｔｉｐｒｉｏｒｉｔｙ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ Ｄｅｓｉｇｎ，” ＩＥＥＥ Ｇｌｏｂｅｃｏｍ ９９．
【非特許文献２】Ｂ． Ｆｏｒｔｚ ａｎｄ Ｍ． Ｔｈｏｒｕｐ，“Ｉｎｔｅｒｎｅｔ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ ｂｙ Ｏｐｔｉｍｉｚｉｎｇ ＯＳＰＦ Ｗｅｉｇｈｔｓ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２０００．
【非特許文献３】Ｂ． Ｆｏｒｔｚ ａｎｄ Ｍ． Ｔｈｏｒｕｐ，“Ｒｏｂｕｓｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ＯＳＰＦ／ＩＳ−ＩＳ ｗｅｉｇｈｔｓ，” ＩＮＯＣ ２００３．
【非特許文献４】Ａ． Ｋｖａｌｂｅｉｎ， Ａ． Ｆ． Ｈａｎｓｅｎ， Ｔ． Ｃｉｃｉｃ， Ｓ． Ｇｊｅｓｓｉｎｇ， ａｎｄ Ｏ． Ｌｙｓｎｅ，“Ｆａｓｔ ＩＰ Ｎｅｔｗｏｒｋ Ｒｅｃｏｖｅｒｙ ｕｓｉｎｇ Ｍｕｌｔｉｐｌｅ Ｒｏｕｔｉｎｇ Ｃｏｎｆｉｇｕｒａｔｉｏｎｓ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００６．
【非特許文献５】Ａ． Ｅｌｗａｌｉｄ， Ｃ． Ｊｉｎ， Ｓ． Ｌｏｗ， ａｎｄ Ｉ． Ｗｉｄｊａｊａ，“ＭＡＴＥ： ＭＰＬＳ Ａｄａｐｔｉｖｅ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００１．
【非特許文献６】Ｓ． Ｋａｎｄｕｌａ， Ｄ． Ｋａｔａｂｉ， Ｂ． Ｄａｖｉｅ， ａｎｄ Ａ． Ｃｈａｒｎｙ，“Ｗａｌｋｉｎｇ ｔｈｅ Ｔｉｇｈｔｒｏｐｅ： Ｒｅｓｐｏｎｓｉｖｅ Ｙｅｔ Ｓｔａｂｌｅ Ｔｒａｆｆｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ，” ＡＣＭ ＳＩＧＣＯＭＭ ２００５．
【非特許文献７】Ｍ． Ｍｅｎｔｈ， Ｒ． Ｍａｒｔｉｎ， Ｊ． Ｃｈａｒｚｉｎｓｋｉ，“Ｃａｐａｃｉｔｙ Ｏｖｅｒｐｒｏｖｉｓｉｏｎｉｎｇ ｆｏｒ Ｎｅｔｗｏｒｋｓ ｗｉｔｈ Ｒｅｓｉｌｉｅｎｃｅ Ｒｅｑｕｉｒｅｍｅｎｔｓ，” ＡＣＭ ＳＩＧＣＯＭＭ ２００６．
【非特許文献８】Ｎ． Ｋａｍｉｙａｍａ，“Ｎｅｔｗｏｒｋ Ｔｏｐｏｌｏｇｙ Ｄｅｓｉｇｎ ｕｓｉｎｇ Ｄａｔａ Ｅｎｖｅｌｏｐｍｅｎｔ Ａｎａｌｙｓｉｓ，” ＩＥＥＥ Ｇｌｏｂｅｃｏｍ ２００７．￥ｂｉｂｉｔｅｍ｛Ｋａｍｉｙａｍａ２｝
【非特許文献９】神山憲明，佐藤大輔，“ＡＨＰを用いた網トポロジ設計，” 信学技報ＩＮ２００６−１４５．
【非特許文献１０】Ｍ． Ｇｅｒｌａ ａｎｄ Ｌ． Ｋｌｅｉｎｒｏｃｋ，“Ｏｎ ｔｈｅ Ｔｏｐｏｌｏｇｉｃａｌ Ｄｅｓｉｇｎ ｏｆ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ，” ＩＥＥＥ Ｔｒａｎｓ． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ＣＯＭ−２５， １， ｐｐ．４８−６０， １９７７．
【非特許文献１１】Ｎ． Ｇ． Ｃｈａｔｔｏｐａｄｈｙａｙ， Ｔ． Ｗ． Ｍｏｒｇａｎ， ａｎｄ Ａ． Ｒａｇｈｕｒａｍ，“Ａｎ Ｉｎｎｏｖａｔｉｖｅ Ｔｅｃｈｎｉｑｕｅ ｆｏｒ Ｂａｃｋｂｏｎｅ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ，” ＩＥＥＥ Ｔｒａｎｓ． Ｓｙｓｔｅｍ， Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ， １９， ５， １９８９．
【非特許文献１２】Ａ． Ｇｅｒｓｈｔ ａｎｄ Ｒ． Ｗｅｉｈｍａｙｅｒ，“Ｊｏｉｎｔ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｄａｔａ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ ａｎｄ Ｆａｃｉｌｉｔｙ Ｓｅｌｅｃｔｉｏｎ，” ＩＥＥＥ Ｊ． Ｓｅｌｅｃ． Ａｒｅａｓ， Ｃｏｍｍｕｎ．， ８， ９， ｐｐ．１６６７−１６８１， １９９０．
【非特許文献１３】Ｋ． Ｓｔｅｉｇｌｉｔｚ， Ｐ． Ｗｅｉｎｅｒ， ａｎｄ Ｄ． Ｊ． Ｋｌｅｉｔｍａｎ，“Ｔｈｅ Ｄｅｓｉｇｎ ｏｆ Ｍｉｎｉｍｕｍ−Ｃｏｓｔ Ｓｕｒｖｉｖａｂｌｅ Ｎｅｔｗｏｒｋｓ，” ＩＥＥＥ Ｔｒａｎｓ． Ｃｉｒｃｕｉｔ Ｔｈｅｏｒｙ， ＣＴ−１６， ４， ｐｐ．４５５−４６０， １９６９．
【非特許文献１４】Ｅ． Ｃ． Ｇ． Ｗｉｌｌｅ， Ｍ． Ｍｅｌｌｉａ， Ｅ． Ｌｅｏｎａｒｄｉ， ａｎｄ Ｍ． Ａ． Ｍａｒｓａｎ，“Ｔｏｐｏｌｏｇｉｃａｌ Ｄｅｓｉｇｎ ｏｆ Ｓｕｒｖｉｖａｂｌｅ ＩＰ Ｎｅｔｗｏｒｋｓ Ｕｓｉｎｇ Ｍｅｔａｈｅｕｒｉｓｔｉｃ Ａｐｐｒｏａｃｈｅｓ，” Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ｐｐ．１９１−２０６， ２００５．
【発明の開示】
【発明が解決しようとする課題】
【００２４】
解決しようとする問題点は、従来の技術では、障害時の接続性のみを考慮しており、障害時に発生する迂回トラヒックに対しても品質を規定水準内に保つことを考慮していない点である。
【００２５】
本発明の目的は、これら従来技術の課題を解決し、単一リンク障害時の迂回トラヒックに対する品質をも考慮した、網トポロジとリンク容量の設計を可能とすることである。
【課題を解決するための手段】
【００２６】
上記目的を達成するため、本発明では、網のトポロジとリンク容量の設計処理を行うために、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別（ルーティング方式）が与えられたときに、正常時の任意のリンクの使用率を規定値γ以下に抑えることを制約条件に、総ネットワークコストを最小化する。この際、リンク数Ｌと、０から１の範囲の値をとる任意に定めた実数パラメタεに対して、正常時のトラヒック量が大きな順にｋ＝εＬ本のリンクの各々の単一障害時に発生する迂回トラヒックを考慮して、リンク使用率をγ以下に抑えることと、残るＬ−ｋ本のリンクの各々の単一障害時にも全ノード間の接続性が維持されることを制約条件とする。また、全ノード間にリンクを設置した状態からスタートし、リンクコストを正常時に流れるトラヒック量で除した値が大きなリンクから優先的に削除する作業を、総ネットワークコストの改善が見られなくなるまで反復する。さらに、任意のリンクを削除した際、削除したリンクを通るパスに対してのみ経路を再計算することで計算時間を抑える。
【発明の効果】
【００２７】
本発明によれば、ノードの位置と、ノード間の交流トラヒック行列と、経路設定法（ルーティングプロトコル種別）と、リンク使用率の規定上限とを少なくとも含むデータが与えられているときに、任意の単一リンク障害により生じる迂回トラヒックを考慮しながらリンク使用率を規定上限以下に抑えるという制約の範囲内で、最適な網トポロジとリンク容量を設計することが可能である。
【発明を実施するための最良の形態】
【００２８】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係る網のトポロジとリンク容量の設計を行うシステムの構成例を示すブロック図であって、本図１におけるシステムは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置からなるコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。
【００２９】
すなわち、本例の網のトポロジとリンク容量の設計を行うシステムは、プログラムされたコンピュータ処理実行手段として、入力処理装置（図中「ノート情報，交流マトリクス，経路設定法，制約条件入力装置」と記載）１０１、設計処理装置（図中「網トポロジ・リンク容量設計装置」と記載）１０２、出力処理装置（図中「最適トポロジ・最適リンク容量出力装置」と記載）１０３を具備している。
【００３０】
入力処理装置１０１は、キーボードから入力操作やファイルから読み込みにより、ノードの位置、ノード間のトラヒックデマンド量（交流マトリクス）、経路設定法（ルーティングプロトコル種別）、リンク使用率の規定上限値γと迂回トラヒックを考慮する対象のリンク数比率ε等のデータを取り込み、記憶装置に入力して記憶し、設計処理装置１０２は、入力処理装置１０１から入力されたデータを記憶装置から読み出して、これらのデータを用いて、最適な網トポロジとリンク容量を算出し、出力処理装置１０３は、入力処理装置１０１が算出した最適トポロジと最適リンク容量をＣＲＴ画面や記憶装置等に出力する。
【００３１】
このような構成のシステムにより、本例では、リンク輻輳を回避するため、リンク利用率が与えられた任意の水準以下となることを制約条件に、総コストを最小化する網のトポロジとリンク容量の設計値を算出する。より具体的には、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別（ルーティング方式）、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出するために、プログラムされたコンピュータ装置の処理実行手段として、入力処理装置１０１と、設計処理装置１０２とを具備し、入力処理装置１０１は、制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力して記憶装置に書き込み、設計処理装置１０２は、制約条件とリンク数Ｌおよびリンク数ｋとからなる情報を記憶装置から読み出し、読み出した情報を用いて、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した網トポロジとリンク容量の算出を行う。
【００３２】
トラヒックの交流マトリクスは常に変化するが、物理的な設備の設計は数ヶ月以上といった長期の時間スケールで行うため、通常、静的な交流マトリクスに基づき設計を行う必要がある。交流マトリクスは日や週といった周期的な変動を示すため、例えば最繁時のトラヒック量に基づき設計を行えば良い。
【００３３】
静的なリンク重みを用いたＯＳＰＦを用いた場合も、リンクやノードの意図しない障害によりトラヒックが流れる経路は変化し、日常的に様々なリンクで障害が発生しており（「Ａ． Ｍａｒｋｏｐｏｕｌｏｕ， Ｇ． Ｉａｎｎａｃｃｏｎｅ， Ｓ． Ｂｈａｔｔａｃｈａｒｙｙａ， Ｃ． Ｃｈｕａｈ， ａｎｄ Ｃ． Ｄｉｏｔ，“Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ ｏｆ Ｆａｉｌｕｒｅｓ ｉｎ ａｎ ＩＰ Ｂａｃｋｂｏｎｅ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００４．」参照）、リンク利用率を算出する際には、障害時の迂回トラヒックをも考慮する必要がある。
【００３４】
ＩＰバックボーンにおいて、メインテナンスに起因するものを除いた意図しない障害の約７０％は単独リンク障害であることから（「Ａ． Ｍａｒｋｏｐｏｕｌｏｕ， Ｇ． Ｉａｎｎａｃｃｏｎｅ， Ｓ． Ｂｈａｔｔａｃｈａｒｙｙａ， Ｃ． Ｃｈｕａｈ， ａｎｄ Ｃ． Ｄｉｏｔ，“Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ ｏｆ Ｆａｉｌｕｒｅｓ ｉｎ ａｎ ＩＰ Ｂａｃｋｂｏｎｅ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００４．」参照）、本例では、単一リンク障害時に発生する迂回トラヒックを考慮して、リンク使用率を規定値以下に抑える。
【００３５】
また、本例では、米国と日本のバックボーンを対象に本設計技術を用いて設計された網トポロジについて分析し、障害に伴う迂回トラヒックの収容を目的として設計される過剰帯域が、どのようなリンクに多く用意されるかについて分析する。
【００３６】
尚、本例では、単一のＩＳＰに閉じた網のうち、バックボーンの設計を対象とする。波長多重技術（ＤＷＤＭ；Ｄｅｎｓｅ Ｗａｖｅｌｅｎｇｔｈ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅｘｉｎｇ）を用いることでリンクの伝送容量の飛躍的な向上が可能であり（「Ｒ． Ｒａｍａｓｗａｍｉ ａｎｄ Ｋ． Ｎ． Ｓｉｖａｒａｊａｎ，“Ｏｐｔｉｃａｌ Ｎｅｔｗｏｒｋｓ，” Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ， ２００２．」参照）、既に、多くのＩＰバックボーンは、ルータ間に設置した伝送リンクにＤＷＤＭを用いている。
【００３７】
本例においても、リンクはＤＷＤＭにより波長多重された光心線で構成される網を想定する。また、ルーティングプロトコル種別（ルーティング方式）としてＯＳＰＦを想定する。 ＳＯＮＥＴ／ＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ Ｏｐｔｉｃａｌ ＮＥＴｗｏｒｋ／Ｓｙｎｃｈｒｏｎｏｕｓ Ｄｉｇｉｔａｌ Ｈｉｅｒａｒｃｈｙ）を用いた障害復旧は高速であるが高コストなため、近年はＩＰレイヤで障害復旧を行うＩＳＰが多い（「Ｆ． Ｇｉｒｏｉｒｅ， Ａ． Ｎｕｃｃｉ， Ｎ． Ｔａｆｔ， ａｎｄ Ｃ． Ｄｉｏｔ，“Ｉｎｃｒｅａｓｉｎｇ ｔｈｅ Ｒｏｂｕｓｔｎｅｓｓ ｏｆ ＩＰ Ｂａｃｋｂｏｎｅｓ ｉｎ ｔｈｅ Ａｂｓｅｎｃｅ ｏｆ Ｏｐｔｉｃａｌ Ｌｅｖｅｌ Ｐｒｏｔｅｃｔｉｏｎ，” ＩＥＥＥ Ｉｎｆｏｃｏｍ ２００３．」参照）。
【００３８】
そこで本例でもＳＯＮＥＴ／ＳＤＨは用いず、障害発生時にはＩＰレイヤでＯＳＰＦにより迂回経路が設定されることを想定する。この場合、迂回経路が安定するまでに時間を要することが問題となり、近年、事前に代替経路を計算しておくことで対処するＦＲＲ（Ｆａｓｔ ＲｅＲｏｕｔｅ）が検討されているが（「Ａ． Ａｔｌａｓ， ｅｔ ａｌ．，“Ｂａｓｉｃ ｓｐｅｃｉｆｉｃａｔｉｏｎ ｆｏｒ ＩＰ ｆａｓｔ−ｒｅｒｏｕｔｅ： ｌｏｏｐ−ｆｒｅｅ ａｌｔｅｒｎａｔｅ，” Ｉｎｔｅｒｎｅｔ ｄｒａｆｔ， ｄｒａｆｔ−ｉｅｔｆ−ｒｔｇｗｇ−ｉｐｆｒｒ−ｓｐｅｃ−ｂａｓｅ−０１．ｔｘｔ， ２００４−９．」参照）、本例では、ＯＳＰＦのみにより迂回経路が設定されることを想定する。
【００３９】
以下、本例による、リンク障害時の迂回トラヒックを考慮した網トポロジとリンク容量の設計処理技術について、詳細を説明する。
【００４０】
ＩＳＰは、リンク輻輳を避けて安定した品質をユーザに提供し続けるためには、各リンクの利用率を大雑把な規定値以下に抑えることを目標に、網を設計・運用すれば実用上は十分であると思われる。
【００４１】
すなわち、ノードｉからノードｊの間に設置されたリンク（以後、「ｅｉｊ」と表記）の使用率をｕｉｊとし、リンク使用率の規定上限をγとすると、リンクが設置された任意の組ｉ，ｊに対してｕｉｊ≦γを満たすことを制約条件とする。
【００４２】
リンクｅｉｊのリンク容量（光ネットワークにおける設計波長数）をｘｉｊとし、リンクを設置しない場合にはｘｉｊ＝０とする。リンクは双方向（ｂｉｄｉｒｅｃｔｉｏｎａｌ）とし、ｘｊｉ＝ｘｉｊとする。
【００４３】
また、交流マトリクスをＤ、ノードｓからノードｄに向かうトラヒックデマンド量をＤｓｄとし、トラヒックデマンド量Ｄｄｓ＝トラヒックデマンド量Ｄｓｄを仮定する。すなわち、交流行列（交流マトリクス）は対称形であるとし、ノードｄからノードｓに向かうパケットは、ノードｓからノードｄに向かうパケットと同一のノードとリンクを逆方向に経由する。しかし、以下に示す本例の設計手法は、交流マトリクスが非対称形であり、リンクが片方向（ｕｎｉｄｉｒｅｃｔｉｏｎａｌ）な場合にも容易に拡張可能である。
【００４４】
以下、リンク使用率制約（リンク使用率の規定上限γ）、ノードの地理的な位置、交流マトリクスＤが与えられたときに、網全体のコストＣを最小化することを目的に網トポロジとリンク容量（設計波長数ｘｉｊ）を設計する処理について説明する。
【００４５】
尚、「Ｌ． Ｌｉ， Ｄ． Ａｌｄｅｒｓｏｎ， Ｗ． Ｗｉｌｌｉｎｇｅｒ， ａｎｄ Ｊ． Ｄｏｙｌｅ，“Ａ Ｆｉｒｓｔ−Ｐｒｉｎｃｉｐｌｅｓ Ａｐｐｒｏａｃｈ ｔｏ Ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ Ｉｎｔｅｒｎｅｔ'ｓ Ｒｏｕｔｅｒ−ｌｅｖｅｌ Ｔｏｐｏｌｏｇｙ，” ＡＣＭ ＳＩＧＣＯＭＭ ２００４．」においては、実際のＩＳＰの網トポロジを調べ、トポロジを決める主要因が、「コスト」と「ルータの処理能力」から決まる制約であると分析している。
【００４６】
しかし、「ルータの処理能力」向上のペースは著しく、現在は、例えば「Ｃｉｓｃｏ ｓｙｓｔｅｍｓ， ｈｔｔｐ：／／ｗｗｗ．ｃｉｓｃｏ．ｃｏｍ．」にあるように、１．２８Ｔｂｐｓもの処理能力を備えたルータを用いることも可能であり、本例では、ルータの処理能力制約は考慮しないものとする。
【００４７】
まず、以下、網全体のコストＣについて説明する。
【００４８】
網コストＣは、ノードコストとリンクコストの総和であるが、本例では簡単のため、ルータのポートあたりのコストをＣｅｐとし、リンクの両端に必要数のルータポートが用意されると見なしてノードコストをリンクコストに含めて考える。
【００４９】
以下、リンクコストをモデル化する。本例では、ＤＷＤＭによるルータ間の波長多重リンクを想定しているため、リンクコストは、土木インフラコスト、光心線コスト、光デバイスコストから構成される。
【００５０】
土木インフラコストは、光ファイバを収容するための土管の敷設費用や、土管を保有する鉄道会社、電力会社、自治体などから土管を借りるための費用であり、１ｋｍあたりのコストをＣｃｄとする。
【００５１】
また、光心線の１ｋｍあたりのコストをＣｆｂとする。１本の光心線に多重可能な波長数には制約があることから、多重可能な波長数の上限をＷとすると、下記の数１に示す本数の光心線をリンクｅｉｊに敷設する必要がある。
【００５２】
【数１】
【００５３】
また、ＤＷＤＭ伝送を行うためには、リンクの両端において波長の多重と分離を行う波長多重分離装置と、減衰した光信号を増幅する光アンプ、そして、ｃｒｏｓｓｔａｌｋ（クロストーク ； 信号漏れ）やＡＳＥ（ａｍｐｌｉｆｉｅｄ ｓｐｏｎｔａｎｅｏｕｓ ｅｍｉｓｓｉｏｎ）やＰＭＤ（ｐｏｌａｒｉｚａｔｉｏｎ ｍｏｄｅ ｄｉｓｐｅｒｓｉｏｎ）によって劣化した光パルスを修復するリピータが必要になる（前述の「Ｒ． Ｒａｍａｓｗａｍｉ ａｎｄ Ｋ． Ｎ． Ｓｉｖａｒａｊａｎ，“Ｏｐｔｉｃａｌ Ｎｅｔｗｏｒｋｓ，” Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ， ２００２．」参照）。
【００５４】
波長多重分離装置のコストは、おおよそ波長数に比例することから、ここでは、その波長あたりのコストをＣｍｄとする。また、光アンプ１台のコストをＣａｐとする。トランスポンダ（中継機器）１台のコストをＣｔｐとすると、光パルスの整形は電気信号に変換してから行う必要があることから、１箇所のリピータで必要になるコストは（Ｃｔｐ＋２Ｃｍｄ）ｘｉｊとなる。
【００５５】
従って、距離が「ｄｉｊ」で設計波長数（設計リンク容量）が「ｘｉｊ」のリンクｅｉｊのコストｃｉｊ（ｄｉｊ，ｘｉｊ）は、下記の式となる。
【００５６】
ｃｉｊ（ｄｉｊ，ｘｉｊ）＝Ｃｃｄｄｉｊ＋｛α（ｄｉｊ）＋β（ｄｉｊ）Ｗ｝ｙｉｊ＋α（ｄｉｊ）δｉｊ（ｚｉｊ）＋β（ｄｉｊ）ｚｉｊ。
【００５７】
ただし、上記式において、「ｙｉｊ」は、上限であるＷ本の波長が多重された光心線の本数であり、「ｚｉｊ」は、Ｗに満たない本数の波長が多重された残り１本の光心線における多重波長数であり、下記の数２に示す式となる。
【００５８】
【数２】
【００５９】
また、「δｉｊ（ｚｉｊ）」を、「ｚｉｊ≧１」のとき「δｉｊ（ｚｉｊ）＝１」で、「ｚｉｊ＝０」のとき「δｉｊ（ｚｉｊ）＝１」となる関数と定義する。
【００６０】
さらに、「α（ｄｉｊ）」は、１本の光心線に必要なコストのうち距離にのみ依存した項であり、「β（ｄｉｊ）」は設計波長数（設計リンク容量）に比例する項であり、次の数３に示す式で与えられる。
【００６１】
【数３】
【００６２】
ただし、上記数３において、「Δａｐ」と「Δｒｐ」は、各々、光アンプとリピータの設置間隔である。
【００６３】
次に、「設計アルゴリズム」について説明する。
【００６４】
まず、網トポロジとリンク容量の設計問題を定式化する。
【００６５】
与えられたノード集合に対して任意に設計した網トポロジをＴとし、網トポロジＴに含まれるエッジ（リンク）の集合をＥとする。そして、網トポロジＴから、集合Ｅに含まれる任意のリンクｅｉｊを除去した網トポロジを下記の数４に示すものとする。
【００６６】
【数４】
【００６７】
各発着ノード間の、パケットが流れる経路は、固定的に定めたリンク重みを用いたＯＳＰＦにより設定されることを想定する。
【００６８】
上述の「リンクコストのモデル化」で説明したように、リンクコストは、距離（ｄｉｊ）と設計波長数（リンク容量ｘｉｊ）に依存するが、距離（ｄｉｊ）は、設計量に独立であり、固定的な重みとして用いるのが容易であることから、本例では、リンク重みとしてリンク距離ｄｉｊを用いる。
【００６９】
総コストＣは、上述の『距離が「ｄｉｊ」で設計波長数が「ｘｉｊ」のリンクｅｉｊのコストｃｉｊ（ｄｉｊ，ｘｉｊ）』を用いて次の数５に示す式で得られる。
【００７０】
【数５】
【００７１】
網トポロジＴと交流マトリクスＤに対して、正常時にリンク集合Ｅに含まれるリンクｅｉｊを流れる、下記の数６の記号で示されるトラヒック量は、下記の数７に示すようになる。
【００７２】
【数６】
【００７３】
【数７】
【００７４】
ただし、上記数７における「Ｐｓｄ（Ｔ）」は、網トポロジＴにおいて発ノードｓから着ノードｄに向かうトラヒックが経由するリンクの集合である。
【００７５】
また、下記の数８の記号で示される網トポロジにおいて同一の交流マトリクスＤを与えたときに、当該網トポロジの、下記の数９の記号で示されるエッジ集合に含まれる任意のリンクｅｉｊを流れるトラヒック量を、下記の数１０の記号で示されるものとすると、それぞれ、下記の数１１に示す関係式となる。
【００７６】
【数８】
【００７７】
【数９】
【００７８】
【数１０】
【００７９】
【数１１】
【００８０】
任意の単一リンク障害時にも、各リンクの使用率を規定上限γ以下に抑えるためには、集合Ｅの各リンク（下記の数１２参照）に対して、下記の数１３で定義される最大トラヒック量を想定し、下記の数１４の式が満たされれば良い。ただし、数１４におけるＢは波長の伝送帯域である。
【００８１】
【数１２】
【００８２】
【数１３】
【００８３】
【数１４】
【００８４】
集合Ｅに含まれるリンクの本数をＬとすると、Ｌ本全てのリンクを対象に、単一リンク障害に伴う迂回トラヒックを考慮してリンク容量を設計すると、正常時に各リンクを流れる、トラヒック量（数６参照）と比較して、非常に大きな帯域を過剰設計することが予想される。
【００８５】
そこで、リンク障害を考慮する対象のリンクをＬ本の全てではなく、下記の数１５で与えられるｋ本のリンクに限定することを考える。ただし、数１５におけるεは０≦ε≦１の範囲の値をとる設計パラメタである。
【００８６】
【数１５】
【００８７】
正常時に各リンクに流れるトラヒック量（数６参照）が大きなリンクほど、障害時に発生する迂回トラヒック量が大きいことから、正常時に各リンクに流れるトラヒック量（数６参照）が大きな上位ｋ本のリンクに対してのみ迂回トラヒックを考慮する。
【００８８】
ただし、任意の単一リンク障害時にも全ノード間の接続性を維持することを制約条件に考え、残るＬ−ｋ本のリンクに対しては、単一障害時に孤立ノードが発生するか否かの判定を行う。
【００８９】
以上のことから、本例の網トポロジとリンク容量の設計問題（設計波長数ｘｉｊの決定問題）は、以下の数１６に示す整数計画問題として表現できる。
【００９０】
【数１６】
【００９１】
ただし、数１６の制約式における、上位ｋ本に限定したリンクに対して定義される最大トラヒック量は、下記の数１７となる。
【００９２】
【数１７】
【００９３】
上記数１７において、Ｅ（ｋ）は、集合Ｅに含まれるリンクのうち、正常に流れるトラヒック量（数６参照）が大きな上位ｋ本のリンク集合である。
【００９４】
また、上記数１７の制約式における下記の数１８で示す値は、下記の数１９で示すリンク集合のリンク重みの総和であり、上記数１６の制約式におけるＥ（Ｌ−ｋ）は、集合Ｅから迂回トラヒックを考慮するｋ本のリンクを除いたリンク集合である。
【００９５】
【数１８】
【００９６】
【数１９】
【００９７】
しかし、この種の整数計画問題は、ＮＰ困難な問題（条件を満たす解の数が膨大で、最も良い解を現実的な時間で求めるのが難しい問題）であり、多項式時間で厳密な最適解を得ることができないことが知られている（前述の「非特許文献１０」参照）。
【００９８】
そのため、大規模な問題に対しても現実的な計算時間で近似最適解が得られるよう、「ローカルサーチ」、「タブサーチ」、「遺伝的アルゴリズム」、「焼きなまし法」、といった様々なヒューリスティックな解法が開発されている（「柳浦睦憲，茨木俊秀，“組合せ最適化，” 朝倉書店， ２００４．」参照）。
【００９９】
一般に、各々の近似解法には問題に対する相性があり、汎用的に優れた解法は存在しないため、本例では、近似解法の詳細な評価には立ち入らず、局所探索法と並ぶ近似アルゴリズムの基本手法の一つである「貪欲算法」を用いる。
【０１００】
この「貪欲算法」は、初期状態からスタートし、目的関数値が最も大きく改善すると思われる解の修正を、目的関数値の改善が見られなくなるまで反復する手法である。
【０１０１】
本例では、全ノード間にフルメッシュにリンクを設置した状態（完全グラフ）からスタートし、１本ずつリンクを除去するアプローチを用いる（前述の「非特許文献１２」を参照）。
【０１０２】
この手法によれば、あるリンクを除去することでそのリンクを経由していたトラヒックが他のリンクにまわるが、最小コストとなる経路が常に選択されるため、網全体としては消費されるリンク資源量が増加する。このコスト増加分に対してリンクを除去することによるコスト減少分が大きなリンクほど、除去することによる総コストの改善効果が期待できる。
【０１０３】
よって、リンクコストが大きく、流れるトラヒック量が小さいリンク、すなわち、下記の数２０に示す値が大きなリンクを優先的に除去する。
【０１０４】
【数２０】
【０１０５】
以下に、このような「貪欲算法」を用いた本発明に係る網トポロジとリンク容量の設計アルゴリズムを、図８を用いて説明する。図８は、図１におけるシステムによる本発明に係る網トポロジ・リンク容量設計処理動作例を示すフローチャートである。
【０１０６】
（１）まず、初期設定処理を行う（ステップＳ８０１）。すなわち、全ノード間にリンクを設置し、前述の数１７の式より、正常時に各リンクに流れるトラヒック量（数６参照）が大きな上位ｋ本のリンクに対して定義される最大トラヒック量（下記の数２１参照）を算出し、また、前述の数５の式より、当該網の総コストＣを算出する。
【０１０７】
【数２１】
【０１０８】
（２）次に、リンク評価値の算出を行う（ステップＳ８０２）。すなわち、下記の数２２の式で示すリンクｅｉｊの評価値ａｉｊを、全リンクに対して各々算出し、評価値ａｉｊの大きな順にソートする。また、ｊ＝１とする。
【０１０９】
【数２２】
【０１１０】
（３）さらに、リンク除去後の総コストを算出する（ステップＳ８０３）。すなわち、リンクｅｉｊの評価値ａｉｊがｊ番目に大きなリンクｅｉ’ｊ’を除去したトポロジ（下記の数２３参照）に対して、前述の数１７の式より、正常時に各リンクに流れるトラヒック量（数６参照）が大きな上位ｋ本のリンクに対して定義される最大トラヒック量を算出し、前述の数５の式より、当該網の総コストＣを算出する。また、集合Ｅ（Ｌ−ｋ）に含まれるリンクを各々除去した場合にも全ノード間の接続性が維持されるか否かを調べる。
【０１１１】
【数２３】
【０１１２】
（４）そして、リンク除去の実施判定を行う（ステップＳ８０４）。すなわち、総コストＣが減少し、かつ、集合Ｅ（Ｌ−ｋ）に含まれる任意のリンク（下記の数２４参照）の単一障害時にも全ノード間の接続性が維持される場合には、上述の「（２）リンク評価値の算出」処理に進み、そうでない場合には、該当リンクを除去しないで「ｊ」を「１」だけ増加させて、上述の「（３）リンク除去後の総コスト算出」処理に進む。「ｊ＝Ｌ」の場合には終了。
【０１１３】
【数２４】
【０１１４】
このような処理を、本例のシステムでは、ハードディスク装置等に記憶されたプログラムをＣＰＵが順次に読み込みコンピュータ処理を実行し、各処理で生成したデータを主メモリ等の記憶装置に記憶し、また、記憶したデータを読み出して次の処理で用いる動作を以下手順で順次に行うことで実現する。
【０１１５】
すなわち、入力処理装置１０１は、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力して記憶装置に書き込む第１の手順を実行し、設計処理装置１０２は、制約条件を記憶装置から読み出す第２の手順と、読み出した制約条件を用いて、全ノード間に設置される各リンクに対して、当該リンクのコストと当該リンクの使用率を規定値γ以下に抑える最大トラヒック量とを算出して記憶装置に書き込む第３の手順と、この第３の手順で算出した各リンクのコストを加算して網全体のコストである総コストを算出し記憶装置に書き込む第４の手順と、第３の手順で算出した各リンクのコストを当該リンクに正常時に流れるトラヒック量で除した値を当該リンクの評価値として算出しソートして記憶装置に書き込む第５の手順と、この第５の手順でソートした各リンクの評価値が一番大きなリンクを除去した残りの各リンクに対して、上述のコストと最大トラヒック量の算出と記憶装置への書き込みを行う６の手順と、この第６の手順で算出した各リンクのコストを加算してリンクを除去した後の網全体の総コストを算出し記憶装置に書き込む第７の手順と、この第７の手順で算出した総コストが第４の手順で算出した総コストより減少するか否か、および、残りの各リンクの各々の単一障害時にも全ノード間の接続性が維持されるか否かを判別する第８の手順と、この第８の手順で、総コストが減少することおよび全ノード間の接続性が維持されることを判別した場合は、当該リンクを除去して上述の第５の手順からの処理を繰り返す第９の手順と、上述の第８の手順で、総コストが減少せず、もしくは、全ノード間の接続性が維持されないと判別した場合は、当該リンクを除去しないで上述の第４の手順で算出した評価値が次に大きなリンクを除去して、上述の第６の手順からの処理を繰り返す第１０の手順と、この第１０の手順による第６の手順からの繰り返し処理を、予め定められたリンク数で終了する第１１の手順とを実行する。
【０１１６】
尚、前述の「（３）リンク除去後の総コスト算出」処理（図８のステップＳ８０１）において、リンクｅｉ’ｊ’を除去したことで経路に影響を受けるトラヒックは、当該リンクｅｉ’ｊ’を通るもののみであり、全ての発着ノードペアに対して経路を再計算することは非効率的である。
【０１１７】
そこで、本例では、各リンクｅｉｊに対して、リンクｅｉｊを経由する発着ノードペアの集合を管理することで、影響を受ける発着ノードペアに対してのみ経路を再計算する。
【０１１８】
同様に、単一リンク障害時の迂回トラヒック量を計算する際も、障害が生じたリンクを経由する発着ノードペアに対してのみ迂回経路を算出する。
【０１１９】
また、「（３）リンク除去後の総コスト算出」処理における「接続性の維持の判定」は、ダイクストラ法を適用した際の経路のコストが、任意の発着ノード間に対して有限値として得られるか否かで行う。
【０１２０】
すなわち、ノード数をＮとすると、ダイクストラ法の計算量はＯ（Ｎ２）となる。初期状態は、完全グラフでスタートするため、アルゴリズムの早い時点においてはＯ（Ｎ２）本のリンクが存在するが、各リンクを経由する発着ノードペア数は、全ペア数Ｎ（Ｎ−１）／２と比較して遥かに小さい。よって、「（３）リンク除去後の総コスト算出」処理における計算量は、おおよそＯ（Ｎ４）となる。よって、全体では、Ｏ（Ｎ６）程度の計算量になる。
【０１２１】
以下、本例の網トポロジとリンク容量の設計による数値評価結果を説明する。ここでは、ノード間の距離ｄｉｊは、ノードｉとノードｊ間の直線距離（ユークリッド距離）とし、リンク使用率の規定上限γ＝０．７とし、また、光心線の多重波長数の上限Ｗ＝６０、波長の伝送帯域Ｂ＝１０Ｇｂｐｓ、光アンプの設置間隔Δａｐ＝８０ｋｍ、リピータの設置間隔Δｒｐ＝２０００ｋｍとする。
【０１２２】
コストは、全て相対値で考え、現状の価格を考慮して、「光心線の１ｋｍあたりのコストＣｆｂ＝０．１」、「光アンプ１台のコストＣａｐ＝２４０」、「トランスポンダ１台のコストＣｔｐ＝７５」、「ルータのポートあたりのコストＣｅｐ＝４０」、「波長あたりのコストＣｍｄ＝３．３」と設定する。
【０１２３】
ただし、土木インフラコストは、地理的要因や契約形態に大きく依存し、適切に設定することが困難であるため考慮しないものとする（Ｃｃｄ＝０）。
【０１２４】
また、評価は、全米の大学や企業が参加するインターネット２の基盤となるバックボーンである「Ａｂｉｌｅｎｅ」を対象に実施した。「Ａｂｉｌｅｎｅ」は、全米に配置された１１のノードから構成される。
【０１２５】
ノード位置は公開されている情報を用いる（「Ａｂｉｌｅｎｅ ｔｏｐｏｌｏｇｙ ａｎｄ ｔｒａｆｆｉｃ ｄａｔａｓｅｔ． ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｕｔｅｘａｓ．ｅｄｕ／〜ｙｚｈａｎｇ／ｒｅｓｅａｒｃｈ／ＡｂｉｌｅｎｅＴＭ／」参照）。また総トラヒック量がＶとなるよう、交流マトリクスは同様に公開されている実測値に比例するよう配分する。
【０１２６】
ただし、全米の２００６年末時点の総トラヒック量が１．３９〜２．４７Ｔｂｐｓであったことから（「Ｍｉｎｎｅｓｏｔａ Ｉｎｔｅｒｎｅｔ Ｔｒａｆｆｉｃ Ｓｔｕｄｉｅｓ （ＭＩＮＴＳ）． ｈｔｔｐ：／／ｗｗｗ．ｄｔｃ．ｕｍｎ．ｅｄｕ／ｍｉｎｔｓ／ｈｏｍｅ．ｈｔｍｌ」参照）、総トラヒック量Ｖ＝１Ｔｂｐｓと１０Ｔｂｐｓの場合について各々評価する。
【０１２７】
ここでは、単一障害時の迂回トラヒックを考慮するリンク数ｋの全リンク数Ｌに対する比率εが各種性能に与える影響を評価する。
【０１２８】
図２は、図１におけるシステムによる網トポロジの設計例を示す説明図であり、本図２においては、単一障害時の迂回トラヒックを考慮するリンク数ｋの全リンク数Ｌに対する比率εの３つの値に対して、各々、設計された網トポロジを示している。
【０１２９】
まず、「総トラヒック量Ｖ＝１Ｔｂｐｓ」の場合、図２の（ａ）〜（ｃ）について見ると、比率ε＝０（迂回トラヒックを全く考慮しない）のとき、図２の（ａ）に示すように、正常時のトラヒック流量が最大のリンクは（２，５）で、次に流量の大きいリンクは（４，５）であった。
【０１３０】
比率εを小さな値に設定すると、これらトラヒック流量の大きな特定のリンクの障害時の迂回トラヒックのみが考慮される。比率ε＝０のとき、これらリンクは大きなループの一部を担っているため、これらリンクで障害が発生すると、迂回トラヒックが多数のリンクを経由するため非効率的である。
【０１３１】
そこで、例えば、比率ε＝０．１のとき、図２の（ｂ）に示すように、これらリンクの障害時の迂回トラヒックが効率的にショートカットされるリンク（３，５）が追加されることが確認できる。
【０１３２】
一方、比率εが大きく「１」に近い場合には、多数のリンクに対して単一リンク障害時の迂回トラヒックを考慮する結果、図２の（ｃ）に示すように、多数の発着ノード間の迂回トラヒックを、共通のリンクで効率よく収容できるループを組み合わせた網トポロジとなることが確認できる。
【０１３３】
また、リンクｅｉｊの設計リンク容量から、正常時に流れるトラヒック量を引いたものを過剰設計帯域Ｅｘ（ｅｉｊ）と定義すると、この過剰設計帯域Ｅｘ（ｅｉｊ）が下記の数２５のとき、リンク（１，１１）と（１，５）の過剰設計帯域Ｅｘ（ｅｉｊ）が突出して大きかった。
【０１３４】
【数２５】
【０１３５】
これは、全リンク数Ｌ＝１４で、単一障害時の迂回トラヒックを考慮するリンク数ｋ＝２となり、正常に流れるトラヒック量（前述の数６，７参照）の大きい上位二本のリンクが（５，８）と（８，１１）であり、これらのリンクと同一のループを形成するためである。
【０１３６】
「Ａｂｉｌｅｎｅ」では、東海岸に人口の大きな都市が集中しており、正常に流れるトラヒック量（前述の数６，７参照）が大きなリンクが特定の地域に集中する傾向がある。このような場合、比率εを小さく設定すると、帯域を過剰設計するリンクもそのような地域に集中する傾向が見られる。
【０１３７】
図３は、各リンクの正常時のリンク使用率を値の大きな順にプロットした例の説明図であり、比率ε＝０の場合、全リンクの使用率が、規定上限γ（＝０．７）に近い値となるが、比率ε＝０．１の場合には、少数のリンクの利用率が大きく低下し、また、比率εが０．４より大きい場合は、リンク利用率のばらつきが大きく、規定上限γ（＝０．７）に近いものから小さなものまで幅広く分布することが確認できる。
【０１３８】
一方、「総トラヒック量Ｖ＝１０Ｔｂｐｓ」の場合には、Ｖ＝１Ｔｂｐｓのときと比較して交流トラヒック量が大きく、複数の対地間でトラヒックを集約しなくても、波長帯域と比較して十分なトラヒック量が対地間で確保できるため、図２の（ｄ）〜（ｆ）に示すように、多数の対地に対してダイレクトリンクが設置される。
【０１３９】
次に、比率εの値の差異に応じて、どの程度異なった網トポロジが設計されるかを確認するため、二つのトポロジＡとトポロジＢの一致度η（Ａ，Ｂ）を、「η（Ａ，Ｂ）＝ｎ（Ａ∩Ｂ）／ｎ（Ａ∪Ｂ）」で定義する。ただし「ｎ（Ａ∩Ｂ）」と「ｎ（Ａ∪Ｂ）」は、各々、トポロジＡとトポロジＢに含まれるリンクの積集合と和集合のリンク数である。
【０１４０】
図４は、二つのトポロジの一致度例を示す説明図である。図４の（ａ）においては、比率ε＝０における設計トポロジＴ（ε＝０）との一致度を、図４の（ｂ）においては、比率ε＝１における設計トポロジＴ（ε＝１）との一致度をεに対して各々示す。
【０１４１】
図４の（ａ）においては、比率εの増加に伴い、設計トポロジＴ（ε＝０）との一致度が減少する反面、図４の（ｂ）においては、比率εの増加に伴い、設計トポロジＴ（ε＝１）との一致度が増加する。
【０１４２】
図４の（ｂ）において、設計トポロジＴ（ε＝１）との一致度は、比率εの値に関係なく７０％程度以上と高い。よって、設計されるトポロジの形に、比率εが及ぼす影響は全体としては小さいといえる。
【０１４３】
図５は、図１におけるシステムで設計したトポロジのリンク数および設計リンク容量の平均値と単一障害時の迂回トラヒックを考慮するリンク数の全リンク数に対する比率との対応関係を示す説明図であり、設計トポロジのリンク数Ｌと、設計リンク容量ｘｉｊの平均値を、比率εに対して示している。
【０１４４】
図４で示したように、単一障害時の迂回トラヒックを考慮するリンク数の全リンク数に対する比率εが、設計トポロジに及ぼす影響は小さく、この比率εの変化に対して、設計トポロジのリンク数Ｌはあまり変化しない。
【０１４５】
一方、比率εの増加に伴い、より多数の単一リンク障害パターンの迂回トラヒックを考慮するため、平均設計リンク容量は増加する。しかし、比率εが中程度より大きな領域では、比率εを増加させても、設計リンク容量はほとんど変化しない。
【０１４６】
この傾向は、図５の（ｃ）に示すように、平均過剰設計帯域（Ｅｘ（ｅｉｊ）の全リンクにわたる平均値）の、比率εに対する特性からも確認できる。これは、正常時のトラヒック量（前述の数６参照）が大きな半数程度のリンクの障害時の迂回トラヒックを考慮してリンク容量を設計すれば、残るリンクの障害時に発生する迂回トラヒックの多くも吸収できることが理由である。
【０１４７】
その結果、図５の（ｄ）に示すように、比率εが中程度以上の領域では、比率εの増加に対して総コストはほとんど増加しなくなる。
【０１４８】
次に、図６を用いて、単一リンク障害時の特性について考察する。図６は、単一リンク障害時のリンク使用率のプロット例を示す説明図であり、図６の（ａ）においては、全ての（Ｌ個の）単一リンク障害パターンにおける各リンクの使用率の平均値を降順にプロットした例を示し、また、図６の（ｂ）においては、Ｌ個の単一リンク障害パターン中の最大利用率を各リンクについて降順にプロットした例を示している。
【０１４９】
ここでは、総トラヒック量Ｖ＝１０Ｔｂｐｓの結果についてのみ示し、図６の（ａ）においては、比率εが「０」や「０．１」の場合、想定していないリンクの障害に伴う迂回トラヒックにより、多数のリンクの平均利用率が、規定上限γ＝０．７を超えている。
【０１５０】
特に、図６の（ｂ）に示すように、少数のリンクの最大リンク使用率が非常に高くなることが確認できる。特に、最大利用率が最も高いリンク（７，９）の障害時利用率が突出して高いが、このリンクの正常時のトラヒック量は、全リンク中で最小であり、比率εを「０」や「０．１」としたときの過剰設計帯域も最小となっている。
【０１５１】
このように、正常時のトラヒック量（前述の数６参照）が大きな少数のリンクのみに限定して障害時の迂回トラヒックを考慮しても不十分である。
【０１５２】
図７は、単一リンク障害時の全リンクにわたるリンク使用率の平均値と最大値の比率に対するプロット例を示す説明図であり、図７の（ａ）においては、全ての単一リンク障害パターンの全リンクにわたるリンク使用率の平均値と最大値を、比率εに対してプロットしており、また、図７の（ｂ）においては、単一リンク障害時にリンク使用率が規定値γ＝０．７を超過したリンクを経由するトラヒック量の全トラヒック量Ｖに対する比率を示している。
【０１５３】
図７の（ａ）に示すように、比率εの増加に伴い、規定上限を超過し、輻輳状態になったリンクを経由するトラヒック量は、指数的に減少することが確認できる。
【０１５４】
また、図７の（ｂ）に示すように、トラヒック量Ｖが大きな方が、同一の比率εに対するｋ（トラヒック量（前述の数６参照）が大きな上位リンクの本数）の値が大きくなるため、超過比率は低くなる。
【０１５５】
比率εが中程度より低い場合、単一リンク障害時に無視できない割合のトラヒックが輻輳リンクを経由することになるため、比率εは中程度以上に設定することが望ましい。また、全トラヒックに対して常にリンク利用率の規定上限を満たすには、比率εを「１」に近い値に設定する必要があるが、比率εが中程度以上の領域では、前述したように、比率εを増加させても総コストはほとんど増加しない。
【０１５６】
以上のことから、比率ε＝１に設定すべきであると結論できる。
【０１５７】
以上、図１〜図８を用いて説明したように、本例では、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別（ルーティング方式）、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出するために、プログラムされたコンピュータ装置の処理実行手段として、入力処理装置１０１と、設計処理装置１０２とを具備し、入力処理装置１０１は、制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力して記憶装置に書き込み、設計処理装置１０２は、制約条件とリンク数Ｌおよびリンク数ｋとからなる情報を記憶装置から読み出し、読み出した情報を用いて、正常時の各リンクの使用率を規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した網トポロジとリンク容量の算出を行う。
【０１５８】
また、設計処理装置１０２は、網トポロジとリンク容量の算出を、全ノード間にリンクを設置した状態からスタートし、正常時に流れるトラヒック量でリンクコストを除した値が大きなリンクから優先的に除去する処理を、総ネットワークコストの改善が見られなくなるまで反復する。
【０１５９】
より詳細には、設計処理装置１０２は、制約条件を記憶装置から読み出し、読み出した制約条件を用いて、全ノード間に設置される各リンクに対して、当該リンクのコストと当該リンクの使用率を規定値γ以下に抑える最大トラヒック量とを算出して記憶装置に書き込むと共に、算出した各リンクのコストを加算して網全体のコストである総コストを算出し記憶装置に書き込み、また、算出した各リンクのコストを当該リンクに正常時に流れるトラヒック量で除した値を当該リンクの評価値として算出しソートして記憶装置に書き込み、ソートした各リンクの評価値が一番大きなリンクを除去した残りの各リンクに対して、コストと最大トラヒック量の算出と記憶装置への書き込みを行い、さらに、ここで算出した各リンクのコストを加算してリンクを除去した後の網全体の総コストを算出し記憶装置に書き込み、この算出した総コストが先に算出した総コストより減少するか否か、および、残りの各リンクの各々の単一障害時にも全ノード間の接続性が維持されるか否かを判別し、総コストが減少することおよび全ノード間の接続性が維持されることを判別した場合は、当該リンクを除去して上記リンクの評価値の算出手順からの処理を繰り返し、総コストが減少せず、もしくは、全ノード間の接続性が維持されないと判別した場合は、当該リンクを除去しないで、評価値が次に大きなリンクを除去して、残りのリンクに対する最大トラヒックとコストの算出を繰り返し、この繰り返し処理を、予め定められたリンク数で終了する。
【０１６０】
また、設計処理装置１０２は、リンクを除去（削除）した際、除去（削除）したリンクを通るパスに対してのみ経路を再計算することで、計算時間を抑える。
【０１６１】
また、設計処理装置１０２は、接続性の維持の判定を、ダイクストラ法を適用した際の経路のコストが任意の発着間ノード間に対して有限値として得られる否かで行う。
【０１６２】
このように、本例では、ノードの位置と、ノード間の交流トラヒック行列と、経路設定法と、リンク使用率の規定上限とが与えられているときに、任意の単一リンク障害により生じる迂回トラヒックを考慮しながらリンク使用率を規定上限以下に抑えるという制約の範囲内で、最適な網トポロジとリンク容量を設計することができる。
【０１６３】
尚、本発明は、図１〜図８を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、光ネットワークを例に説明したが、これに限定されるものではない。
【０１６４】
また、本例では、単一リンクのみを考慮したが、さらに、単一ノード障害を考慮する場合にも適用できる。この場合、各ノードに接続された全リンクに障害が発生したと見なし、各リンクの最大トラヒック量を算出する際に、各ノード障害時の迂回トラヒックを同時に考慮する。
【０１６５】
また、本例のコンピュータ装置の構成に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１６６】
【図１】本発明に係る網のトポロジとリンク容量の設計を行うシステムの構成例を示すブロック図である。
【図２】図１におけるシステムによる網トポロジの設計例を示す説明図である。
【図３】各リンクの正常時のリンク使用率を値の大きな順にプロットした例の説明図である。
【図４】二つのトポロジの一致度例を示す説明図である。
【図５】図１におけるシステムで設計したトポロジのリンク数および設計リンク容量の平均値と単一障害時の迂回トラヒックを考慮するリンク数の全リンク数に対する比率との対応関係を示す説明図である。
【図６】単一リンク障害時のリンク使用率のプロット例を示す説明図である。
【図７】単一リンク障害時の全リンクにわたるリンク使用率の平均値と最大値の比率に対するプロット例を示す説明図である。
【図８】図１におけるシステムによる本発明に係る網トポロジ・リンク容量設計処理動作例を示すフローチャートである。
【符号の説明】
【０１６７】
１０１：入力処理装置（ノート情報，交流マトリクス，経路設定法，制約条件入力装置）、１０２：設計処理装置（網トポロジ・リンク容量設計装置）、１０３：出力処理装置（最適トポロジ・最適リンク容量出力装置）。
【特許請求の範囲】
【請求項１】
ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出する網トポロジ・リンク容量設計処理方法であって、
プログラムされたコンピュータ装置の処理実行手段として、入力処理手段と、設計処理手段とを具備し、
入力処理手段は、上記制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力して記憶装置に書き込む第１の手順を実行し、
上記設計処理手段は、
上記制約条件と上記リンク数Ｌおよび上記リンク数ｋとからなる情報を記憶装置から読み出し、読み出した情報を用いて、上記正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、
トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した上記網トポロジとリンク容量の算出を行う第２の手順を実行する
ことを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項２】
請求項１に記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、上記第２の手順において、
上記網トポロジとリンク容量の算出を、全ノード間にリンクを設置した状態からスタートし、正常時に流れるトラヒック量でリンクコストを除した値が大きなリンクから優先的に除去する処理を、総ネットワークコストの改善が見られなくなるまで反復する
ことを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項３】
請求項１もしくは請求項２のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、
単一ノード障害に対して、各ノードに接続された全リンクに障害が発生したと見なし、各リンクの最大トラヒック量を算出する際に、各ノード障害時の迂回トラヒックを同時に考慮することを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項４】
プログラムされたコンピュータ装置によって、網のトポロジとリンク容量の設計処理を行う方法であって、
プログラムされたコンピュータ装置の処理実行手段として、入力処理手段と、設計処理手段とを具備し、
入力処理手段は、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力して記憶装置に書き込む第１の手順を実行し、
設計処理手段は、上記制約条件を記憶装置から読み出す第２の手順と、
読み出した制約条件を用いて、全ノード間に設置される各リンクに対して、当該リンクのコストと当該リンクの使用率を上記規定値γ以下に抑える最大トラヒック量とを算出して記憶装置に書き込む第３の手順と、
該第３の手順で算出した各リンクのコストを加算して網全体のコストである総コストを算出し記憶装置に書き込む第４の手順と、
上記第３の手順で算出した各リンクのコストを当該リンクに正常時に流れるトラヒック量で除した値を当該リンクの評価値として算出しソートして記憶装置に書き込む第５の手順と、
該第５の手順でソートした各リンクの評価値が一番大きなリンクを除去した残りの各リンクに対して、上記コストと上記最大トラヒック量の算出と記憶装置への書き込みを行う６の手順と、
該第６の手順で算出した各リンクのコストを加算してリンクを除去した後の網全体の総コストを算出し記憶装置に書き込む第７の手順と、
該第７の手順で算出した総コストが上記第４の手順で算出した総コストより減少するか否か、および、上記残りの各リンクの各々の単一障害時にも全ノード間の接続性が維持されるか否かを判別する第８の手順と、
該第８の手順で、総コストが減少することおよび全ノード間の接続性が維持されることを判別した場合は、当該リンクを除去して上記第５の手順からの処理を繰り返す第９の手順と、
上記第８の手順で、総コストが減少せず、もしくは、全ノード間の接続性が維持されないと判別した場合は、当該リンクを除去しないで上記第４の手順で算出した評価値が次に大きなリンクを除去して、上記第６の手順からの処理を繰り返す第１０の手順と、
該第１０の手順による上記第６の手順からの繰り返し処理を、予め定められたリンク数で終了する第１１の手順と
を実行することを特徴とする網トポロジ・リンク容量設定処理方法。
【請求項５】
請求項２から請求項４のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、
上記リンクを除去した際、削除したリンクを通るパスに対してのみ経路を再計算する手順を実行することを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項６】
請求項１から請求項５のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、
上記接続性の維持の判定を、ダイクストラ法を適用した際の経路のコストが任意の発着間ノード間に対して有限値として得られる否かで行うことを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項７】
請求項１から請求項６のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記網は光ネットワークからなり、
上記リンク容量が波長数であることを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項８】
ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出する網トポロジ・リンク容量設計処理システムであって、
プログラムされたコンピュータ処理を実行する手段として、
請求項１から請求項７のいずれかに記載の網トポロジ・リンク容量設計処理方法における各手順を実行する処理手段を具備したことを特徴とする網トポロジ・リンク容量設計処理システム。
【請求項９】
コンピュータに、請求項１から請求項７のいずれかに記載の網トポロジ・リンク容量設計処理方法における各手順を実行させるためのプログラム。
【請求項１】
ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出する網トポロジ・リンク容量設計処理方法であって、
プログラムされたコンピュータ装置の処理実行手段として、入力処理手段と、設計処理手段とを具備し、
入力処理手段は、上記制約条件に加えて、全ノード間に設置するリンク数Ｌと、予め定められたリンク数ｋ（＜Ｌ）とを入力して記憶装置に書き込む第１の手順を実行し、
上記設計処理手段は、
上記制約条件と上記リンク数Ｌおよび上記リンク数ｋとからなる情報を記憶装置から読み出し、読み出した情報を用いて、上記正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網トポロジとリンク容量を算出する際、
トラヒック量が大きな上位ｋ本のリンクに限定し、かつ、残るＬ−ｋ本の各リンクの単一障害時にも全ノード間の接続性が維持されることを制約条件として、各リンクの単一リンク障害に伴う迂回トラヒックを考慮した上記網トポロジとリンク容量の算出を行う第２の手順を実行する
ことを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項２】
請求項１に記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、上記第２の手順において、
上記網トポロジとリンク容量の算出を、全ノード間にリンクを設置した状態からスタートし、正常時に流れるトラヒック量でリンクコストを除した値が大きなリンクから優先的に除去する処理を、総ネットワークコストの改善が見られなくなるまで反復する
ことを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項３】
請求項１もしくは請求項２のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、
単一ノード障害に対して、各ノードに接続された全リンクに障害が発生したと見なし、各リンクの最大トラヒック量を算出する際に、各ノード障害時の迂回トラヒックを同時に考慮することを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項４】
プログラムされたコンピュータ装置によって、網のトポロジとリンク容量の設計処理を行う方法であって、
プログラムされたコンピュータ装置の処理実行手段として、入力処理手段と、設計処理手段とを具備し、
入力処理手段は、ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力して記憶装置に書き込む第１の手順を実行し、
設計処理手段は、上記制約条件を記憶装置から読み出す第２の手順と、
読み出した制約条件を用いて、全ノード間に設置される各リンクに対して、当該リンクのコストと当該リンクの使用率を上記規定値γ以下に抑える最大トラヒック量とを算出して記憶装置に書き込む第３の手順と、
該第３の手順で算出した各リンクのコストを加算して網全体のコストである総コストを算出し記憶装置に書き込む第４の手順と、
上記第３の手順で算出した各リンクのコストを当該リンクに正常時に流れるトラヒック量で除した値を当該リンクの評価値として算出しソートして記憶装置に書き込む第５の手順と、
該第５の手順でソートした各リンクの評価値が一番大きなリンクを除去した残りの各リンクに対して、上記コストと上記最大トラヒック量の算出と記憶装置への書き込みを行う６の手順と、
該第６の手順で算出した各リンクのコストを加算してリンクを除去した後の網全体の総コストを算出し記憶装置に書き込む第７の手順と、
該第７の手順で算出した総コストが上記第４の手順で算出した総コストより減少するか否か、および、上記残りの各リンクの各々の単一障害時にも全ノード間の接続性が維持されるか否かを判別する第８の手順と、
該第８の手順で、総コストが減少することおよび全ノード間の接続性が維持されることを判別した場合は、当該リンクを除去して上記第５の手順からの処理を繰り返す第９の手順と、
上記第８の手順で、総コストが減少せず、もしくは、全ノード間の接続性が維持されないと判別した場合は、当該リンクを除去しないで上記第４の手順で算出した評価値が次に大きなリンクを除去して、上記第６の手順からの処理を繰り返す第１０の手順と、
該第１０の手順による上記第６の手順からの繰り返し処理を、予め定められたリンク数で終了する第１１の手順と
を実行することを特徴とする網トポロジ・リンク容量設定処理方法。
【請求項５】
請求項２から請求項４のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、
上記リンクを除去した際、削除したリンクを通るパスに対してのみ経路を再計算する手順を実行することを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項６】
請求項１から請求項５のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記設計処理手段は、
上記接続性の維持の判定を、ダイクストラ法を適用した際の経路のコストが任意の発着間ノード間に対して有限値として得られる否かで行うことを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項７】
請求項１から請求項６のいずれかに記載の網トポロジ・リンク容量設計処理方法であって、
上記網は光ネットワークからなり、
上記リンク容量が波長数であることを特徴とする網トポロジ・リンク容量設計処理方法。
【請求項８】
ノード位置と、トラヒック交流マトリクスと、ルーティングプロトコル種別、および、正常時の任意のリンクの使用率の上限を規定する値γを少なくとも含むデータを制約条件として入力し、プログラムされたコンピュータ装置によって、正常時の各リンクの使用率を上記規定値γ以下に抑え、かつ、総ネットワークコストを最小化する網のトポロジとリンク容量を算出する網トポロジ・リンク容量設計処理システムであって、
プログラムされたコンピュータ処理を実行する手段として、
請求項１から請求項７のいずれかに記載の網トポロジ・リンク容量設計処理方法における各手順を実行する処理手段を具備したことを特徴とする網トポロジ・リンク容量設計処理システム。
【請求項９】
コンピュータに、請求項１から請求項７のいずれかに記載の網トポロジ・リンク容量設計処理方法における各手順を実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００９−１１８２０１（Ｐ２００９−１１８２０１Ａ）
【公開日】平成２１年５月２８日（２００９．５．２８）
【国際特許分類】
【出願番号】特願２００７−２８９１４２（Ｐ２００７−２８９１４２）
【出願日】平成１９年１１月７日（２００７．１１．７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年５月２８日（２００９．５．２８）
【国際特許分類】
【出願日】平成１９年１１月７日（２００７．１１．７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]