TOP > 国内特許検索 > ネットワーク設計方法、設計装置およびそのプログラム > 明細書

明細書 :ネットワーク設計方法、設計装置およびそのプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4936544号 (P4936544)
公開番号 特開2009-053828 (P2009-053828A)
登録日 平成24年3月2日(2012.3.2)
発行日 平成24年5月23日(2012.5.23)
公開日 平成21年3月12日(2009.3.12)
発明の名称または考案の名称 ネットワーク設計方法、設計装置およびそのプログラム
国際特許分類 G06F  17/50        (2006.01)
H04L  12/56        (2006.01)
H04M   3/00        (2006.01)
H04L  12/28        (2006.01)
FI G06F 17/50 650A
H04L 12/56 400Z
H04M 3/00 E
H04L 12/28 200M
請求項の数または発明の数 5
全頁数 9
出願番号 特願2007-218461 (P2007-218461)
出願日 平成19年8月24日(2007.8.24)
審査請求日 平成22年3月23日(2010.3.23)
特許権者または実用新案権者 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
発明者または考案者 【氏名】亀井 聡
【氏名】川原 亮一
【氏名】笠原 正治
【氏名】高橋 豊
個別代理人の代理人 【識別番号】100121669、【弁理士】、【氏名又は名称】本山 泰
【識別番号】100127535、【弁理士】、【氏名又は名称】豊田 義元
審査官 【審査官】伊知地 和之
参考文献・文献 特開平10-098525(JP,A)
特開平11-008633(JP,A)
特開2000-022750(JP,A)
特開平11-215124(JP,A)
特開平09-044534(JP,A)
調査した分野 G06F 17/50
H04L 12/28
H04M 3/00
CSDB(日本国特許庁)
特許請求の範囲 【請求項1】
コンピュータ制御によるネットワーク設計装置であって、
需要予測に基づき生成されたトラヒックマトリクスを記憶する第一の記憶部と、
物理トポロジ設計と優先クラス設計に基づいて生成された論理トポロジを記憶する第二の記憶部と、
前記トラヒックマトリクスを生成した後、アプリケーションの挙動によりネットワーク内部でのトラヒック交流が変化することを想定して、ロジックを動作させ、該ロジックの変化をトラヒックマトリクスを記憶する前記第一の記憶部にフィードバックするフィードバック&ロジック部と、
前記第一記憶部から読み出されたトラヒックマトリクスおよび前記第二記憶部から読み出された論理トポロジに基づいて経路制御計算を行う経路計算部と、
該経路計算部の計算結果から評価結果を出力する評価結果出力部とを設けることを特徴とするネットワーク設計装置。
【請求項2】
需要予測に基づき生成されたトラヒックマトリクスと、物理トポロジ設計と優先クラス設計に基づいて生成された論理トポロジの構成を基に、経路制御計算を行う、コンピュータ制御によるネットワーク設計方法であって、
該コンピュータは、トラヒックマトリクスを生成した後、アプリケーションの挙動によりネットワーク内部でのトラヒック交流が変化することを想定して、ロジックを動作させ、
次に該ロジックの変化を上記トラヒックマトリクスにフィードバックさせ、
次に、フィードバックを受けたトラヒックマトリクスおよび論理トポロジに基づいて経路制御計算を行い、
経路制御計算を行った結果、評価結果を出力することを特徴とするネットワーク設計方法。
【請求項3】
前記フィードバック&ロジック部は、同じ始発点から異なる到着点d1,d2,d3に向かうトラヒックをまとめたものに、トラヒックマトリクス((始発点,到達点,利用帯域)を要素とする集合)を変換するロジックとして、
始点が同じsから発しているトラヒックをトラヒックマトリクスから抽出し、その中で不等式dist(s,d1)+dist(s,d2)+dist(s,d3)>dist(s,r)+dist(r,d1)+dist(r,d2)+dist(r,d3)(なお、distは距離を示す)に当て嵌まるような中継点rが存在する場合、トラヒックマトリクスの要素(s,d1,a),(s,d2,a),(s,d3,a)についてロジックを適用し、(s,r,3a),(r,d1,a),(r,d2,a),(r,d3,a)が要素となるようにトラヒックマトリクスを変換することを特徴とする請求項1に記載のネットワーク設計装置。
【請求項4】
前記フィードバック&ロジック部は、同じ始発点から異なる経路上にある中継点r1,r2,r3を経由して同じ到着点に向かうトラヒックをまとめたものに、トラヒックマトリクス((始発点,到達点,利用帯域)を要素とする集合)を変換するロジックとして、
始発点sと到着点dとの間で、不等式 dist(s,d)>(dist(s,r1,d)+dist(s,r2,d)+dist(s,r3,d))/3(なお、distは距離を示す)が成立するような中継点r1,r2,r3が存在する場合に、中継点r1,r2,r3をそれぞれ中継したトラヒックへと分割し、
トラヒックマトリクスの要素(s,d,a)から(s,r1,a/3),(r1,d,a/3),(s,r2,a/3),(r2,d,a/3),(s,r3,a/3),(r3,d,a/3)が要素となるようにトラヒックマトリクスを変換することを特徴とする請求項1のネットワーク設計装置。
【請求項5】
ネットワーク設計装置のコンピュータに、需要予測に基づいてトラヒックマトリクスを生成する手順、物理トポロジ設計と優先クラス設計に基づいて論理トポロジを生成する手順、アプリケーションの変化があったか否かを検出する手順、変化が検出されたときには、変化によりロジックが変化したか否かを検出する手順、変化があれば、アプリケーションの挙動によりネットワーク内部でのトラヒック交流が変化することを想定して、ロジックを動作させる手順、ロジックの変化をトラヒックマトリクスにフィードバックさせる手順、フィードバックを受けたトラヒックマトリクスと、生成された論理トポロジとを基に、経路制御計算を実行する手順、計算を実行した結果、評価結果を出力する手順を、それぞれ実行させるためのネットワーク設計プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、インターネット等のネットワークサービスを提供するに際して、ネットワークのトポロジ、経路制御法、優先制御法の設計を効率的に実施するためのネットワーク設計方法、設計装置およびそのプログラムに関する。
【背景技術】
【0002】
ネットワークサービスの提供に際しては、最初にネットワークトポロジ(ネットワークの構造)を決める必要がある。
近年は、さらに高い品質や信頼性を要求するネットワークサービスが必要とされており、このようなサービス提供のためには上記に加えて経路制御方式や優先制御のためのクラスをどのように設計するかも重要な事項となる。
トポロジの設計は、特に物理的な工事が必要となることも多いので、事前に設計を行うことが重要となる。このため、このようなネットワークをあらかじめ評価するための方法として、シミュレーション等によるネットワーク設計技術が重要となる。
【0003】
実際のネットワーク設計においては、図1に示すように、何等かの需要予測11に基づいて通信の始発点と到着点、要求トラヒック量の組からなるトラヒックマトリクス14を作成し、その需要に対してネットワークトポロジと優先制御方式から生成した論理トポロジ15に対して、経路制御アルゴリズムに基づく収容を行い、そこから得られたリンク使用率や収容効率を評価するのが一般的である。
例えば、文献WANDL,“BBDsgn”,(http://www.wandl.com/html/npat/NPAT_backbone.cfm)(非特許文献1参照)に記載の先行方式は、このようなトポロジ設計を主目的とした設計ツールで、トポロジと経路制御方式、完全に分離された優先制御等を考慮したネットワーク設計が可能となっている。
【0004】
電話やWeb等のように、定常的な需要変化が少ない通信を収容するためには、以上のような評価で充分であった。
しかし、近年ブロードバンドの急速な普及の中で、特にインターネット上では回線間の歪みのある構造を利用して回線利用率が比較的低いところを積極的に利用するP2P等の特殊なトラヒックパターンを持つアプリケーションや、コストの高いバックボーン回線を回避することにより、収益を上げるようなビジネス等が登場し、トラヒックマトリクスがネットワーク設計の変化に応じて短かいサイクルで変化するようになっている。
このため、既存のトラヒックマトリクスを固定したネットワーク設計では、このような変化に追従することが困難となっている。
【0005】

【非特許文献1】WANDL,“BBDsgn”,(http://www.wandl.com/html/npat/NPAT_backbone.cfm)
【発明の開示】
【発明が解決しようとする課題】
【0006】
前述のように、従来、シミュレーションによるネットワークトポロジ設計に関する技術は存在したが、これらは電話やWeb等の固定したアプリケーションを対象としたものであったため、例えば、CDN(ディジタルコンテンツの大量配信に対応したコンテンツデリバリーネットワーク)およびP2P(二者間通信で双方のノードが対等に通信するピアー・ツー・ピアー・ネットワーク)のようにアプリケーションの挙動が短いサイクルで変化した場合に、それに伴って生じるトラヒック交流の変化に対応できない、という問題があった。
【0007】
(目的)
本発明の目的は、上述の問題を解決し、アプリケーションの挙動が変化することでもたらされるトラヒック交流の変化を考慮して、ネットワークの構造変化に対して利用者が短期間に利用方法を変えるような環境下でも、効率的なネットワークを設計することが可能なネットワーク設計方法、設計装置およびそのプログラムを提供することにある。
【課題を解決するための手段】
【0008】
本発明は、アプリケーションの変化に伴いトラヒックロジックに生じた変化をトラヒックマトリックスにフィードバックするアルゴリズムを組み込むことで、柔軟なネットワーク設計を実現するものである。
すなわち、本発明は、トラヒックマトリクスにトポロジからのフィードバックを受ける変化アルゴリズムを組み込む部位を用意することにより、アプリケーションの利用トレンドの変化等を考慮した現実的な評価が可能である。つまり、従来のネットワーク設計ツールはアプリケーションが固定されており、変更ができないものであったのに対して、本発明では、アプリケーションをモジュールとして差し替え可能なものとし、このアプリケーションモジュールの差し替えにより変化したロジックをトラヒックマトリクスにフィードバックすることにより、柔軟なネットワーク設計を実現する。
【発明の効果】
【0009】
本発明によれば、ネットワークの構造変化に対して利用者が短期間に利用方法を変えるような環境下においても、効率的なネットワークを設計することが可能になる。
【発明を実施するための最良の形態】
【0010】
以下、図1を用いて本発明とその基本となる既存の設計装置の実施の形態について、詳細に説明する。
まず、最初に本発明の基本となる従来の設計装置について説明する。
需要予測11に基づいて生成されたトラヒックマトリクス14と、物理トポロジ設計12と優先クラス設計13に基づいて生成された論理トポロジ構成15を元に、経路制御計算部16で収容状況を計算する。また、評価結果17となる収容率やリンク利用率を計算する。
【0011】
ここで、需要予測11とは、実際に構築したネットワークにおいて、どの程度の利用者がどの程度の通信量(トラヒック)をもたらすかの予想であり、例えば、各地域毎の人口比率に基づく推計等や、利用アプリケーションの想定、待ち行列モデル等により導出される。
続いて、需要予測結果を実際の対地間のトラヒック(トラヒックマトリクス14)へ変換する。トラヒックマトリクス14は、この場合、通信の始点、終点、利用帯域の3つの値からなる組の集合を指す。
【0012】
一方で、実際にこれらのトラヒックを収容するネットワークを設計する。物理トポロジとは実際に通信回線を配線する層を指し、その上に優先クラスを設定することによって論理的なネットワークトポロジ(論理トポロジ15)が構成される。
ここで、論理トポロジ15と呼んでいるのは、ルータを頂点、ルータ間リンク(厳密には、優先クラスを考慮しているため複数)を枝としたグラフ構造を指し、始点ルータ、終点ルータ、リンク帯域の組の集合となる。
【0013】
この2つを入力として、経路制御計算部16において経路制御を計算し、トラヒックを論理トポロジ15へ収容する。経路制御としては、例えば、OSPF(Open Shortest Path First;RIP(経路情報プロトコル:Routing Information Protocol)の持つ様々な問題を改良したプロトコルで、サブネットマスクのサポートやエリアの概念を導入することにより、ネットワークを階層構造化し、経路情報の量を小さくする)等を用いてダイクストラ法(Dijkstra法)に基づく計算を実施することにより、対地間トラヒックを論理トポロジ15へ収容できる。
【0014】
収容後状態を表わすために、論理トポロジ15のリンクを表わす表記を拡張し、これを「始点ルータ、終点ルータ、リンク帯域、利用帯域等」とすることが多い。
また、評価のための関数も、様々なものが考えられるが、例えば品質の悪い部分をできるだけ減らそうと考えれば、「利用帯域÷リンク帯域」の最大値を評価関数とし、これを最小化するように、トポロジを設計し直す等が考えられる。
以上の構成は、具体的には、勿論、コンピュータにより実現される。
【0015】
次に、本発明の構成を説明する。
図2は、本発明の一実施例に係るネットワーク設計装置の構成図である。
図2においても、入力に関しては図1の既存の装置と同様である。すなわち、需要予測21に基づいて生成されたトラヒックマトリクス24と、物理トポロジ設計22と優先クラス設計23に基づいて生成された論理トポロジ構成25を元に、経路制御計算部27で収容状況を計算する。また、評価結果28となる収容率やリンク利用率を計算する。
【0016】
続いて、需要予測結果を実際の対地間のトラヒック(トラヒックマトリクス24)へ変換する。トラヒックマトリクス24は、前述のように、通信の始点、終点、利用帯域の3つの値からなる組の集合を指している。
本発明では、フィードバックが働くフィードバック部とアプリケーションのロジックが働くフィードバック&ロジック部26を設け、論理トポロジ25の情報を用いて、ここで動的にトラヒックマトリクス24を変更する。すなわち、例えば、CDN(コンテンツデリバリネットワーク)およびP2P(ピアー・ツー・ピア・ネットワーク)に変化したことにより、ロジックが変化した場合、そのロジックの変化をトラヒックマトリックス24にフィードバックする。これにより、経路制御計算部27において需要変化を反映した評価を実施して、評価結果28を出すことが可能となる。
上記の構成は、コンピュータにより実現される。
【0017】
図3および図4は、本発明のフィードバック&ロジック部26の動作例を示す図である。
図3(実施例1)では、CDN的なロジックを表わしており、同じ始発点から異なる到着点に向うトラヒックをまとめたものにマトリクスを変換するロジックを表わしている。
ここでは、実施例1として、距離(distで表記)×帯域の合計値を小さくするような中継点rが存在する場合に集約を実施するというロジックを組み込んだものである。
【0018】
図3において、始発点sと到着点d1,d2,d3の中間に位置する中継点rとの間で、下記不等式に該当するような中継点rを検出する。
If dist(s,d1)+dist(s,d2)+dist(s,d3)
>dist(s,r)+dist(r,d1)+dist(r,d2)+dist(r,d3)
Then convert
(始点、終点、帯域) (s,r,3a)
(s,d1,a) → (r,d1,a)
(s,d2,a) → (r,d2,a)
(s,d3,a) → (r,d3,a)
【0019】
実施例1では、始点が同じsから発しているトラヒックをトラヒックマトリクスから抽出し、その中で上記の不等式に当て嵌まるような中継点rが存在する(s,d1,a),(s,d2,a),(s,d3,a)についてロジックを適用し、(s,r,3a),(r,d1,a),(r,d2,a),(r,d3,a)へとトラヒックマトリクスを変換した様子を表わしている。
ここでは、一部の例を示しているに留まっているが、実際には、始点が同じくなるようなトラヒックについて全てこのロジックを適用する場合、左辺が右辺より2倍以上大きくなる場合のみ適用する場合、条件を満たした場合に1/3の確率でロジックを適用する場合等、実際のサービスの調査結果に応じてロジックを微調整することも考えられる。
【0020】
図4(実施例2)では、同様にP2P的なロジックを表わしており、1つのトラヒックを複数に分割したものにマトリクスを変換するロジックを表わしている。
この実施例2では、1/3に分割されたトラヒックが別経路で到着点に向かうというロジックを組み込んだものを表わしている。
【0021】
図4においては、始発点sと到着点dとの間で、下記の不等式が成立するような中継点r1,r2,r3が存在する場合に、中継点r1,r2,r3をそれぞれ中継したトラヒックへと分割するというロジックである。
If dist(s,d)>(dist(s,r1,d)+dist(s,r2,d)+dist(s,r3,d))/3
Then convert
(s,d,a)→(s,r1,a/3),(r1,d,a/3),(s,r2,a/3),(r2,d,a/3),(s,r3,a/3),(r3,d,a/3)
【0022】
このようなロジックを与えられた入力トラヒックマトリクスにフィードバックすることで、これまで利用者の動向の変化やアプリケーションの仕様変更により大きく影響を受けてきたネットワーク設計を柔軟に実施することが可能になる。
【0023】
図5は、本発明のネットワーク設計方法の実施例に係る動作フローチャートである。
まず、需要予測に基づいてトラヒックマトリクスを生成する(ステップ101)。
次に、物理トポロジ設計と優先クラス設計に基づいて論理トポロジを生成する(ステップ102)。このとき、アプリケーションの変化があったか否かを検出し(ステップ103)、変化が検出されたときには、変化によりロジックが変化したか否かを検出する(ステップ104)。変化があれば、アプリケーションのロジックを動作させ(ステップ105)、ロジックの変化をトラヒックマトリクスにフィードバックさせる(ステップ106)。
生成された後に、フィードバックを受けたトラヒックマトリクスと、生成された論理トポロジとを基に、経路制御計算を実行する(ステップ107)。そして、計算した結果、評価結果を出力する(ステップ108)。
【0024】
なお、図5のフローをプログラムに変換し、CD-ROM等の記録媒体に格納して、本発明のネットワーク設計装置のコンピュータに記録媒体を装着し、プログラムをコンピュータにインストールしてこれを実行させれば、本発明を容易に実現することができる。
また、上記プログラムをネットワークを介して他の端末にダウンロードすることにより、上記プログラムを汎用化することも可能である。
【図面の簡単な説明】
【0025】
【図1】既存のネットワーク設計装置の構成図である。
【図2】本発明の一実施例に係るネットワーク設計装置の構成図である。
【図3】本発明の実施例1に係るフィードバック&ロジック部の動作原理図である。
【図4】本発明の実施例2に係るフィードバック&ロジック部の動作原理図である。
【図5】本発明のネットワーク設計方法の動作フローチャートである。
【符号の説明】
【0026】
21 需要予測
22 物理トポロジ設計
23 優先クラス設計
24 トラヒックマトリクス
25 論理トポロジ
26 フィードバック&ロジック部
27 経路制御計算部
28 評価結果
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4