(57)【特許請求の範囲】
【請求項１】
コンピュータ制御によるネットワーク設計装置であって、
需要予測に基づき生成されたトラヒックマトリクスを記憶する第一の記憶部と、
物理トポロジ設計と優先クラス設計に基づいて生成された論理トポロジを記憶する第二の記憶部と、
前記トラヒックマトリクスを生成した後、アプリケーションの挙動によりネットワーク内部でのトラヒック交流が変化することを想定して、ロジックを動作させ、該ロジックの変化をトラヒックマトリクスを記憶する前記第一の記憶部にフィードバックするフィードバック＆ロジック部と、
前記第一記憶部から読み出されたトラヒックマトリクスおよび前記第二記憶部から読み出された論理トポロジに基づいて経路制御計算を行う経路計算部と、
該経路計算部の計算結果から評価結果を出力する評価結果出力部とを設けることを特徴とするネットワーク設計装置。
【請求項２】
需要予測に基づき生成されたトラヒックマトリクスと、物理トポロジ設計と優先クラス設計に基づいて生成された論理トポロジの構成を基に、経路制御計算を行う、コンピュータ制御によるネットワーク設計方法であって、
該コンピュータは、トラヒックマトリクスを生成した後、アプリケーションの挙動によりネットワーク内部でのトラヒック交流が変化することを想定して、ロジックを動作させ、
次に該ロジックの変化を上記トラヒックマトリクスにフィードバックさせ、
次に、フィードバックを受けたトラヒックマトリクスおよび論理トポロジに基づいて経路制御計算を行い、
経路制御計算を行った結果、評価結果を出力することを特徴とするネットワーク設計方法。
【請求項３】
前記フィードバック＆ロジック部は、同じ始発点から異なる到着点ｄ１，ｄ２，ｄ３に向かうトラヒックをまとめたものに、トラヒックマトリクス（（始発点，到達点，利用帯域）を要素とする集合）を変換するロジックとして、
始点が同じｓから発しているトラヒックをトラヒックマトリクスから抽出し、その中で不等式ｄｉｓｔ（ｓ，ｄ１）＋ｄｉｓｔ（ｓ，ｄ２）＋ｄｉｓｔ（ｓ，ｄ３）＞ｄｉｓｔ（ｓ，ｒ）＋ｄｉｓｔ（ｒ，ｄ１）＋ｄｉｓｔ（ｒ，ｄ２）＋ｄｉｓｔ（ｒ，ｄ３）（なお、ｄｉｓｔは距離を示す）に当て嵌まるような中継点ｒが存在する場合、トラヒックマトリクスの要素（ｓ，ｄ１，ａ），（ｓ，ｄ２，ａ），（ｓ，ｄ３，ａ）についてロジックを適用し、（ｓ，ｒ，３ａ），（ｒ，ｄ１，ａ），（ｒ，ｄ２，ａ），（ｒ，ｄ３，ａ）が要素となるようにトラヒックマトリクスを変換することを特徴とする請求項１に記載のネットワーク設計装置。
【請求項４】
前記フィードバック＆ロジック部は、同じ始発点から異なる経路上にある中継点ｒ１，ｒ２，ｒ３を経由して同じ到着点に向かうトラヒックをまとめたものに、トラヒックマトリクス（（始発点，到達点，利用帯域）を要素とする集合）を変換するロジックとして、
始発点ｓと到着点ｄとの間で、不等式  ｄｉｓｔ（ｓ，ｄ）＞（ｄｉｓｔ（ｓ，ｒ１，ｄ）＋ｄｉｓｔ（ｓ，ｒ２，ｄ）＋ｄｉｓｔ（ｓ，ｒ３，ｄ））／３（なお、ｄｉｓｔは距離を示す）が成立するような中継点ｒ１，ｒ２，ｒ３が存在する場合に、中継点ｒ１，ｒ２，ｒ３をそれぞれ中継したトラヒックへと分割し、
トラヒックマトリクスの要素（ｓ，ｄ，ａ）から（ｓ，ｒ１，ａ／３），（ｒ１，ｄ，ａ／３），（ｓ，ｒ２，ａ／３），（ｒ２，ｄ，ａ／３），（ｓ，ｒ３，ａ／３），（ｒ３，ｄ，ａ／３）が要素となるようにトラヒックマトリクスを変換することを特徴とする請求項１のネットワーク設計装置。
【請求項５】
ネットワーク設計装置のコンピュータに、需要予測に基づいてトラヒックマトリクスを生成する手順、物理トポロジ設計と優先クラス設計に基づいて論理トポロジを生成する手順、アプリケーションの変化があったか否かを検出する手順、変化が検出されたときには、変化によりロジックが変化したか否かを検出する手順、変化があれば、アプリケーションの挙動によりネットワーク内部でのトラヒック交流が変化することを想定して、ロジックを動作させる手順、ロジックの変化をトラヒックマトリクスにフィードバックさせる手順、フィードバックを受けたトラヒックマトリクスと、生成された論理トポロジとを基に、経路制御計算を実行する手順、計算を実行した結果、評価結果を出力する手順を、それぞれ実行させるためのネットワーク設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等のネットワークサービスを提供するに際して、ネットワークのトポロジ、経路制御法、優先制御法の設計を効率的に実施するためのネットワーク設計方法、設計装置およびそのプログラムに関する。
【背景技術】
【０００２】
ネットワークサービスの提供に際しては、最初にネットワークトポロジ（ネットワークの構造）を決める必要がある。
近年は、さらに高い品質や信頼性を要求するネットワークサービスが必要とされており、このようなサービス提供のためには上記に加えて経路制御方式や優先制御のためのクラスをどのように設計するかも重要な事項となる。
トポロジの設計は、特に物理的な工事が必要となることも多いので、事前に設計を行うことが重要となる。このため、このようなネットワークをあらかじめ評価するための方法として、シミュレーション等によるネットワーク設計技術が重要となる。
【０００３】
実際のネットワーク設計においては、図１に示すように、何等かの需要予測１１に基づいて通信の始発点と到着点、要求トラヒック量の組からなるトラヒックマトリクス１４を作成し、その需要に対してネットワークトポロジと優先制御方式から生成した論理トポロジ１５に対して、経路制御アルゴリズムに基づく収容を行い、そこから得られたリンク使用率や収容効率を評価するのが一般的である。
例えば、文献ＷＡＮＤＬ，“ＢＢＤｓｇｎ”，（http://www.wandl.com/html/npat/NPAT_backbone.cfm）（非特許文献１参照）に記載の先行方式は、このようなトポロジ設計を主目的とした設計ツールで、トポロジと経路制御方式、完全に分離された優先制御等を考慮したネットワーク設計が可能となっている。
【０００４】
電話やＷｅｂ等のように、定常的な需要変化が少ない通信を収容するためには、以上のような評価で充分であった。
しかし、近年ブロードバンドの急速な普及の中で、特にインターネット上では回線間の歪みのある構造を利用して回線利用率が比較的低いところを積極的に利用するＰ２Ｐ等の特殊なトラヒックパターンを持つアプリケーションや、コストの高いバックボーン回線を回避することにより、収益を上げるようなビジネス等が登場し、トラヒックマトリクスがネットワーク設計の変化に応じて短かいサイクルで変化するようになっている。
このため、既存のトラヒックマトリクスを固定したネットワーク設計では、このような変化に追従することが困難となっている。
【０００５】
【非特許文献１】ＷＡＮＤＬ，“ＢＢＤｓｇｎ”，（http://www.wandl.com/html/npat/NPAT_backbone.cfm）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
前述のように、従来、シミュレーションによるネットワークトポロジ設計に関する技術は存在したが、これらは電話やＷｅｂ等の固定したアプリケーションを対象としたものであったため、例えば、ＣＤＮ（ディジタルコンテンツの大量配信に対応したコンテンツデリバリーネットワーク）およびＰ２Ｐ（二者間通信で双方のノードが対等に通信するピアー・ツー・ピアー・ネットワーク）のようにアプリケーションの挙動が短いサイクルで変化した場合に、それに伴って生じるトラヒック交流の変化に対応できない、という問題があった。
【０００７】
（目的）
本発明の目的は、上述の問題を解決し、アプリケーションの挙動が変化することでもたらされるトラヒック交流の変化を考慮して、ネットワークの構造変化に対して利用者が短期間に利用方法を変えるような環境下でも、効率的なネットワークを設計することが可能なネットワーク設計方法、設計装置およびそのプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明は、アプリケーションの変化に伴いトラヒックロジックに生じた変化をトラヒックマトリックスにフィードバックするアルゴリズムを組み込むことで、柔軟なネットワーク設計を実現するものである。
すなわち、本発明は、トラヒックマトリクスにトポロジからのフィードバックを受ける変化アルゴリズムを組み込む部位を用意することにより、アプリケーションの利用トレンドの変化等を考慮した現実的な評価が可能である。つまり、従来のネットワーク設計ツールはアプリケーションが固定されており、変更ができないものであったのに対して、本発明では、アプリケーションをモジュールとして差し替え可能なものとし、このアプリケーションモジュールの差し替えにより変化したロジックをトラヒックマトリクスにフィードバックすることにより、柔軟なネットワーク設計を実現する。
【発明の効果】
【０００９】
本発明によれば、ネットワークの構造変化に対して利用者が短期間に利用方法を変えるような環境下においても、効率的なネットワークを設計することが可能になる。
【発明を実施するための最良の形態】
【００１０】
以下、図１を用いて本発明とその基本となる既存の設計装置の実施の形態について、詳細に説明する。
まず、最初に本発明の基本となる従来の設計装置について説明する。
需要予測１１に基づいて生成されたトラヒックマトリクス１４と、物理トポロジ設計１２と優先クラス設計１３に基づいて生成された論理トポロジ構成１５を元に、経路制御計算部１６で収容状況を計算する。また、評価結果１７となる収容率やリンク利用率を計算する。
【００１１】
ここで、需要予測１１とは、実際に構築したネットワークにおいて、どの程度の利用者がどの程度の通信量（トラヒック）をもたらすかの予想であり、例えば、各地域毎の人口比率に基づく推計等や、利用アプリケーションの想定、待ち行列モデル等により導出される。
続いて、需要予測結果を実際の対地間のトラヒック（トラヒックマトリクス１４）へ変換する。トラヒックマトリクス１４は、この場合、通信の始点、終点、利用帯域の３つの値からなる組の集合を指す。
【００１２】
一方で、実際にこれらのトラヒックを収容するネットワークを設計する。物理トポロジとは実際に通信回線を配線する層を指し、その上に優先クラスを設定することによって論理的なネットワークトポロジ(論理トポロジ１５）が構成される。
ここで、論理トポロジ１５と呼んでいるのは、ルータを頂点、ルータ間リンク（厳密には、優先クラスを考慮しているため複数）を枝としたグラフ構造を指し、始点ルータ、終点ルータ、リンク帯域の組の集合となる。
【００１３】
この２つを入力として、経路制御計算部１６において経路制御を計算し、トラヒックを論理トポロジ１５へ収容する。経路制御としては、例えば、ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ；ＲＩＰ（経路情報プロトコル：Ｒｏｕｔｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）の持つ様々な問題を改良したプロトコルで、サブネットマスクのサポートやエリアの概念を導入することにより、ネットワークを階層構造化し、経路情報の量を小さくする）等を用いてダイクストラ法（Ｄｉｊｋｓｔｒａ法）に基づく計算を実施することにより、対地間トラヒックを論理トポロジ１５へ収容できる。
【００１４】
収容後状態を表わすために、論理トポロジ１５のリンクを表わす表記を拡張し、これを「始点ルータ、終点ルータ、リンク帯域、利用帯域等」とすることが多い。
また、評価のための関数も、様々なものが考えられるが、例えば品質の悪い部分をできるだけ減らそうと考えれば、「利用帯域÷リンク帯域」の最大値を評価関数とし、これを最小化するように、トポロジを設計し直す等が考えられる。
以上の構成は、具体的には、勿論、コンピュータにより実現される。
【００１５】
次に、本発明の構成を説明する。
図２は、本発明の一実施例に係るネットワーク設計装置の構成図である。
図２においても、入力に関しては図１の既存の装置と同様である。すなわち、需要予測２１に基づいて生成されたトラヒックマトリクス２４と、物理トポロジ設計２２と優先クラス設計２３に基づいて生成された論理トポロジ構成２５を元に、経路制御計算部２７で収容状況を計算する。また、評価結果２８となる収容率やリンク利用率を計算する。
【００１６】
続いて、需要予測結果を実際の対地間のトラヒック（トラヒックマトリクス２４）へ変換する。トラヒックマトリクス２４は、前述のように、通信の始点、終点、利用帯域の３つの値からなる組の集合を指している。
本発明では、フィードバックが働くフィードバック部とアプリケーションのロジックが働くフィードバック＆ロジック部２６を設け、論理トポロジ２５の情報を用いて、ここで動的にトラヒックマトリクス２４を変更する。すなわち、例えば、ＣＤＮ（コンテンツデリバリネットワーク）およびＰ２Ｐ（ピアー・ツー・ピア・ネットワーク）に変化したことにより、ロジックが変化した場合、そのロジックの変化をトラヒックマトリックス２４にフィードバックする。これにより、経路制御計算部２７において需要変化を反映した評価を実施して、評価結果２８を出すことが可能となる。
上記の構成は、コンピュータにより実現される。
【００１７】
図３および図４は、本発明のフィードバック＆ロジック部２６の動作例を示す図である。
図３（実施例１）では、ＣＤＮ的なロジックを表わしており、同じ始発点から異なる到着点に向うトラヒックをまとめたものにマトリクスを変換するロジックを表わしている。
ここでは、実施例１として、距離（ｄｉｓｔで表記）×帯域の合計値を小さくするような中継点ｒが存在する場合に集約を実施するというロジックを組み込んだものである。
【００１８】
図３において、始発点ｓと到着点ｄ１，ｄ２，ｄ３の中間に位置する中継点ｒとの間で、下記不等式に該当するような中継点ｒを検出する。
Ｉｆ  ｄｉｓｔ（ｓ，ｄ１）＋ｄｉｓｔ（ｓ，ｄ２）＋ｄｉｓｔ（ｓ，ｄ３）
＞ｄｉｓｔ（ｓ，ｒ）＋ｄｉｓｔ（ｒ，ｄ１）＋ｄｉｓｔ（ｒ，ｄ２）＋ｄｉｓｔ（ｒ，ｄ３）
Ｔｈｅｎ  ｃｏｎｖｅｒｔ
（始点、終点、帯域）              （ｓ，ｒ，３ａ）
（ｓ，ｄ１，ａ）    →            （ｒ，ｄ１，ａ）
（ｓ，ｄ２，ａ）    →            （ｒ，ｄ２，ａ）
（ｓ，ｄ３，ａ）    →            （ｒ，ｄ３，ａ）
【００１９】
実施例１では、始点が同じｓから発しているトラヒックをトラヒックマトリクスから抽出し、その中で上記の不等式に当て嵌まるような中継点ｒが存在する（ｓ，ｄ１，ａ），（ｓ，ｄ２，ａ），（ｓ，ｄ３，ａ）についてロジックを適用し、（ｓ，ｒ，３ａ），（ｒ，ｄ１，ａ），（ｒ，ｄ２，ａ），（ｒ，ｄ３，ａ）へとトラヒックマトリクスを変換した様子を表わしている。
ここでは、一部の例を示しているに留まっているが、実際には、始点が同じくなるようなトラヒックについて全てこのロジックを適用する場合、左辺が右辺より２倍以上大きくなる場合のみ適用する場合、条件を満たした場合に１／３の確率でロジックを適用する場合等、実際のサービスの調査結果に応じてロジックを微調整することも考えられる。
【００２０】
図４（実施例２）では、同様にＰ２Ｐ的なロジックを表わしており、１つのトラヒックを複数に分割したものにマトリクスを変換するロジックを表わしている。
この実施例２では、１／３に分割されたトラヒックが別経路で到着点に向かうというロジックを組み込んだものを表わしている。
【００２１】
図４においては、始発点ｓと到着点ｄとの間で、下記の不等式が成立するような中継点ｒ１，ｒ２，ｒ３が存在する場合に、中継点ｒ１，ｒ２，ｒ３をそれぞれ中継したトラヒックへと分割するというロジックである。
Ｉｆ  ｄｉｓｔ（ｓ，ｄ）＞（ｄｉｓｔ（ｓ，ｒ１，ｄ）＋ｄｉｓｔ（ｓ，ｒ２，ｄ）＋ｄｉｓｔ（ｓ，ｒ３，ｄ））／３
Ｔｈｅｎ  ｃｏｎｖｅｒｔ
（ｓ，ｄ，ａ）→（ｓ，ｒ１，ａ／３），（ｒ１，ｄ，ａ／３），（ｓ，ｒ２，ａ／３），（ｒ２，ｄ，ａ／３），（ｓ，ｒ３，ａ／３），（ｒ３，ｄ，ａ／３）
【００２２】
このようなロジックを与えられた入力トラヒックマトリクスにフィードバックすることで、これまで利用者の動向の変化やアプリケーションの仕様変更により大きく影響を受けてきたネットワーク設計を柔軟に実施することが可能になる。
【００２３】
図５は、本発明のネットワーク設計方法の実施例に係る動作フローチャートである。
まず、需要予測に基づいてトラヒックマトリクスを生成する（ステップ１０１）。
次に、物理トポロジ設計と優先クラス設計に基づいて論理トポロジを生成する（ステップ１０２）。このとき、アプリケーションの変化があったか否かを検出し（ステップ１０３）、変化が検出されたときには、変化によりロジックが変化したか否かを検出する（ステップ１０４）。変化があれば、アプリケーションのロジックを動作させ（ステップ１０５）、ロジックの変化をトラヒックマトリクスにフィードバックさせる（ステップ１０６）。
生成された後に、フィードバックを受けたトラヒックマトリクスと、生成された論理トポロジとを基に、経路制御計算を実行する（ステップ１０７）。そして、計算した結果、評価結果を出力する（ステップ１０８）。
【００２４】
なお、図５のフローをプログラムに変換し、ＣＤ−ＲＯＭ等の記録媒体に格納して、本発明のネットワーク設計装置のコンピュータに記録媒体を装着し、プログラムをコンピュータにインストールしてこれを実行させれば、本発明を容易に実現することができる。
また、上記プログラムをネットワークを介して他の端末にダウンロードすることにより、上記プログラムを汎用化することも可能である。
【図面の簡単な説明】
【００２５】
【図１】既存のネットワーク設計装置の構成図である。
【図２】本発明の一実施例に係るネットワーク設計装置の構成図である。
【図３】本発明の実施例１に係るフィードバック＆ロジック部の動作原理図である。
【図４】本発明の実施例２に係るフィードバック＆ロジック部の動作原理図である。
【図５】本発明のネットワーク設計方法の動作フローチャートである。
【符号の説明】
【００２６】
２１  需要予測
２２  物理トポロジ設計
２３  優先クラス設計
２４  トラヒックマトリクス
２５  論理トポロジ
２６  フィードバック＆ロジック部
２７  経路制御計算部
２８  評価結果
【図１】
0004936544.tif 000002
【図２】
0004936544.tif 000003
【図３】
0004936544.tif 000004
【図４】
0004936544.tif 000005
【図５】
0004936544.tif 000006