(57)【要約】【課題】大規模ネットワークであっても、対地間トラヒック量の推定値Ｔを求めるための計算時間を短縮する。【解決手段】対地間トラヒック推定装置は、ネットワークのトポロジを複数のブロックに分割する。また、ルーティング情報とリンクトラヒック情報もブロックごとに分割し、分割したブロックごとのルーティング情報およびリンクトラヒック情報をもとに対地間トラヒック量の推定値（ブロック毎対地間トラヒック量の推定値）を計算する。そして、ネットワークの各対地間トラヒックの推定値を求める場合には、このブロック毎対地間トラヒック量の推定値を統合する。【選択図】図１
2010283703.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがリンクにより接続されるネットワークにおいて、前記ネットワークのいずれかのノードに入力され、前記ノードまたは他のノードに出力される対地間トラヒックのトラヒック量の推定方法であって、
（１）前記ネットワークにおける前記複数のノードおよびそのノード間を接続するリンクを示したトポロジ情報と、（２）前記リンクそれぞれのトラヒック量を示すリンクトラヒック情報と、（３）前記対地間トラヒックごとに、その対地間トラヒックにおいて経由するリンクを示したルーティング情報とを記憶する記憶部を備える対地間トラヒック推定装置が、
前記トポロジ情報に示されるノード群を、複数のブロックに分割し、その分割したブロックに属するノードと別のブロックに属するノードを接続するリンクを示したブロック間接続情報を作成し、前記記憶部に記憶するステップと、
前記リンクトラヒック情報および前記ブロック間接続情報を参照して、前記ブロックごとに、当該ブロックにおけるリンクトラヒック情報であるブロック毎リンクトラヒック情報を作成し、前記記憶部に記憶するステップと、
前記ルーティング情報を参照して、前記分割したブロックごとに、前記ルーティング情報に示される対地間トラヒックそれぞれの、前記ブロックそれぞれにおけるルーティング情報であるブロック毎ルーティング情報を作成し、前記記憶部に記憶するステップと、
前記ブロック毎リンクトラヒック情報を参照して、前記ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算し、前記記憶部に記憶するステップと、
前記ブロック毎リンクトラヒック情報、前記ブロック毎ルーティング情報および前記初期値を用いて、前記ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値を計算し、前記計算した推定値を示すブロック毎対地間トラヒック量推定値を前記記憶部に記憶するステップと、
前記ブロック間接続情報を参照して、前記対地間トラヒックごとに、その対地間トラヒックの経由する１以上の前記ブロックを特定し、前記ブロック毎対地間トラヒック量推定値から、その特定したブロックそれぞれにおける対地間トラヒックのトラヒック量の推定値を読み出し、その読み出したトラヒック量の推定値をもとに、当該対地間トラヒックのトラヒック量の推定値を計算するステップとを実行することを特徴とする対地間トラヒック推定方法。
【請求項２】
前記対地間トラヒック推定装置が、
前記ブロック間接続情報を作成するステップにおいて、前記トポロジ情報に示されるノード群を、複数のブロックに分割するとき、同じブロックに属する任意の２つのノードが、当該ブロックに属するノードのみを経由して到達可能となるように分割することを特徴とする請求項１に記載の対地間トラヒック推定方法。
【請求項３】
前記対地間トラヒック推定装置が、
前記ブロック間接続情報を作成するステップにおいて、前記トポロジ情報に示されるノード群を、複数のブロックに分割するとき、前記ルーティング情報を参照して、当該ブロックに属するノードに入力し、当該ブロックに属するノードから出力する対地間トラヒックが、当該ブロックに属するノードのみを経由するようにブロックを分割することを特徴とする請求項１または請求項２に記載の対地間トラヒック推定方法。
【請求項４】
前記対地間トラヒック推定装置が、前記ブロック毎対地間トラヒック量推定値から、前記対地間トラヒックの経由するブロックそれぞれにおける対地間トラヒックのトラヒック量の推定値を読み出し、その読み出したトラヒック量の推定値をもとに、当該対地間トラヒックのトラヒック量の推定値を計算するとき、
（１）当該対地間トラヒックの経由するブロックが１つの場合、当該ブロックにおける当該対地間トラヒックのトラヒック量の推定値を出力し、
（２）当該対地間トラヒックの経由するブロックが複数の場合、当該対地間トラヒックが入力されるブロックへのトラヒック量の推定値に、当該ブロックから出力されるすべてのトラヒック量の推定値の合計値に対する、当該対地間トラヒックが当該ブロックから次の経由ブロックに出力されるトラヒック量の推定値の比率を掛ける処理を、前記経由するブロックそれぞれに対し実行することで、当該対地間トラヒックのトラヒック量の推定値を計算することを特徴とする請求項１ないし請求項３のいずれか１項に記載の対地間トラヒック推定方法。
【請求項５】
前記対地間トラヒック推定装置が、
前記ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算するとき、前記リンクトラヒック情報を参照して、前記ネットワーク全体の対地間トラヒックのトラヒック量の推定値の初期値を計算し、前記ブロックごとに、当該ブロックを経由する対地間トラヒックそれぞれのトラヒック量の推定値の初期値を加算することで、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値の初期値を計算することを特徴とする請求項１ないし請求項４のいずれか１項に記載の対地間トラヒック推定方法。
【請求項６】
複数のノードがリンクにより接続されるネットワークにおいて、前記ネットワークのいずれかのノードに入力され、前記ノードまたは他のノードに出力される対地間トラヒックのトラヒック量の推定値を計算する対地間トラヒック推定装置であって、
（１）前記ネットワークにおける前記複数のノードおよびそのノード間を接続するリンクを示したトポロジ情報と、（２）前記リンクそれぞれのトラヒック量を示すリンクトラヒック情報と、（３）前記対地間トラヒックごとに、その対地間トラヒックにおいて経由するリンクを示したルーティング情報とを記憶する記憶部と、
前記トポロジ情報に示されるノード群を、複数のブロックに分割し、その分割したブロックに属するノードと別のブロックに属するノードを接続するリンクを示したブロック間接続情報を作成し、前記記憶部に記憶するブロック分割部と、
前記リンクトラヒック情報および前記ブロック間接続情報を参照して、前記ブロックごとに、当該ブロックにおけるリンクトラヒック情報であるブロック毎リンクトラヒック情報を作成し、前記記憶部に記憶するブロック毎リンクトラヒック情報作成部と、
前記ルーティング情報を参照して、前記分割したブロックごとに、前記ルーティング情報に示される対地間トラヒックそれぞれの、前記ブロックそれぞれにおけるルーティング情報であるブロック毎ルーティング情報を作成し、前記記憶部に記憶するブロック毎ルーティング情報作成部と、
前記ブロック毎リンクトラヒック情報を参照して、前記ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算し、前記記憶部に記憶する初期値計算部と、
前記ブロック毎リンクトラヒック情報、前記ブロック毎ルーティング情報および前記初期値を用いて、前記ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値を計算し、前記計算した推定値を示すブロック毎対地間トラヒック量推定値を前記記憶部に記憶するブロック毎対地間トラヒック量推定部と、
前記ブロック間接続情報を参照して、前記対地間トラヒックごとに、その対地間トラヒックの経由する１以上の前記ブロックを特定し、前記ブロック毎対地間トラヒック量推定値から、その特定したブロックそれぞれにおける対地間トラヒックのトラヒック量の推定値を読み出し、その読み出したトラヒック量の推定値をもとに、当該対地間トラヒックのトラヒック量の推定値を計算するブロック統合部とを備えることを特徴とする対地間トラヒック推定装置。
【請求項７】
請求項１ないし請求項５のいずれか１項に記載の対地間トラヒック推定方法を、コンピュータである前記対地間トラヒック推定装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを構成する各ノード間を接続するリンクそれぞれのリンクトラヒック情報と、ネットワーク内の各対地間トラヒックのルーティング情報とを用いて対地間トラヒックのトラヒック量（対地間トラヒック量）を推定する技術に関する。
【背景技術】
【０００２】
従来、ネットワークを構成する各ノード間を接続するリンクそれぞれのリンクトラヒック情報と、ネットワーク内のトラヒックのルーティング情報（トラヒックの入力ノードから出力ノードまでの間でどのリンクを経由するか示した情報）とを用いて対地間トラヒック量を推定する技術として、ＴｏｍｏＧｒａｖｉｔｙ法がある（非特許文献１参照）。このＴｏｍｏＧｒａｖｉｔｙ法では、以下のようにして対地間トラヒックのトラヒック量を推定する。
【０００３】
まず、リンクトラヒック量を示すベクトルＸ、対地間トラヒック量を示すベクトルＴ、各対地間トラヒックのルーティング情報を示す行列（ルーティング行列）Ａとの間には以下の式（１）に示す関係が成り立つ。
Ｘ＝Ａ＊Ｔ…式（１）
ここで、ＸとＡとを入力として与えることで、Ｔが求められるように思われるが、一般的にＴの要素数（対地間トラヒックの数）は、Ｘの要素数（リンク数）よりも多いため、解が一意に求まらない。そこで、まず、Ｇｒａｖｉｔｙ法等によりＴの初期値Ｔｇを求め、この初期値Ｔｇと、行列Ａの擬似逆行列pinv（Ａ）とを用いて、式（２）により、Ｔを推定する。
Ｔ＝ｐｉｎｖ（Ａ）（Ｘ−Ａ＊Ｔｇ）＋Ｔｇ…式（２）
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Y．Zhang，M．Roughan，N．Duffield，A．Greenberg，“Fast Accurate Computation of large-Scale IP Traffic Matrices from Link Loads”ACM SIGMETRICS Performance Evaluation Review，2003
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、式（２）におけるルーティング行列Ａは、リンク数×フロー数（対地間トラヒック数）であり、ネットワーク内のノード数Ｎが多くなると、リンク数はＮにほぼ比例して増加する。また、各ノードがフルメッシュで接続される場合を考えると、フロー数は、Ｎの二乗にほぼ比例して増加する。よって、ルーティング行列Ａのサイズは、Ｎの三乗にほぼ比例して増加することになる。従って、このルーティング行列Ａの擬似逆行列pinv（Ａ）の計算時間も増加するので、ネットワーク規模が大きくなるにつれ、対地間トラヒック量の推定値Ｔを求めるための計算時間が莫大になるという問題があった。
【０００６】
そこで、本発明は、前記した問題を解決し、ネットワークの対地間トラヒック量の推定値Ｔを求めるための計算時間を短縮することを目的とする。
【課題を解決するための手段】
【０００７】
前記した課題を解決するため、本発明は、複数のノードがリンクにより接続されるネットワークにおいて、ネットワークのいずれかのノードに入力され、ノードまたは他のノードに出力される対地間トラヒックのトラヒック量の推定を行う対地間トラヒック推定装置が、（１）ネットワークにおける複数のノードおよびそのノード間を接続するリンクを示したトポロジ情報と、（２）リンクそれぞれのトラヒック量を示すリンクトラヒック情報と、（３）対地間トラヒックごとに、その対地間トラヒックにおいて経由するリンクを示したルーティング情報とを記憶する記憶部を備え、トポロジ情報に示されるノード群を、複数のブロックに分割し、その分割したブロックに属するノードと別のブロックに属するノードを接続するリンクを示したブロック間接続情報を作成し、記憶部に記憶する。また、この対地間トラヒック推定装置は、リンクトラヒック情報およびブロック間接続情報を参照して、ブロックごとに、当該ブロックにおけるリンクトラヒック情報であるブロック毎リンクトラヒック情報を作成し、記憶部に記憶する。さらに、この対地間トラヒック推定装置は、ルーティング情報を参照して、分割したブロックごとに、ルーティング情報に示される対地間トラヒックそれぞれの、ブロックそれぞれにおけるルーティング情報であるブロック毎ルーティング情報を作成し、記憶部に記憶する。その後、この対地間トラヒック推定装置は、ブロック毎リンクトラヒック情報を参照して、ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算し、記憶部に記憶する。そして、この対地間トラヒック推定装置は、ブロック毎リンクトラヒック情報、ブロック毎ルーティング情報および初期値を用いて、ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値を計算し、計算した推定値を示すブロック毎対地間トラヒック量推定値を記憶部に記憶する。その後、この対地間トラヒック推定装置は、ブロック間接続情報を参照して、対地間トラヒックごとに、その対地間トラヒックの経由する１以上のブロックを特定し、ブロック毎対地間トラヒック量推定値から、その特定したブロックそれぞれにおける対地間トラヒックのトラヒック量の推定値を読み出し、その読み出したトラヒック量の推定値をもとに、当該対地間トラヒックのトラヒック量の推定値を計算する。
【０００８】
このようにすることで、対地間トラヒック推定装置は、対地間トラヒックのトラヒック量（対地間トラヒック量）の推定値を計算するとき、ブロックごとに分割したルーティング情報（ルーティング行列）を用いて計算する。つまり、対地間トラヒック推定装置は、対地間トラヒック量の推定値Ｔを計算するとき、ネットワーク全体のルーティング行列を用いて計算するよりも、行列サイズを小さくできるので、対地間トラヒック量の推定値Ｔを計算するときの計算時間を短縮することができる。
【０００９】
また、本発明は、対地間トラヒック推定装置が、ブロック間接続情報を作成するステップにおいて、トポロジ情報に示されるノード群を、複数のブロックに分割するとき、同じブロックに属する任意の２つのノードが、当該ブロックに属するノードのみを経由して到達可能となるように分割する。
【００１０】
このように対地間トラヒック推定装置が、同じブロックに属する任意の２つのノードを、当該ブロックに属するノードのみを経由して到達可能とするブロック分割を行えば、例えば、このブロックの対地間トラヒックの入力ノードおよび出力ノードを同じブロック内のノードＡ，Ｂとしたとき、このブロックの対地間トラヒックの経路として、ノードＡ→同じブロックのノード→ノードＢという経路をとる可能性を向上できる。ここで、ノードＡ→同じブロックのノード→ノードＢという経路の場合、対地間トラヒックが複数のブロックにまたがることに伴う対地間トラヒック量の補正を行う必要がなくなるので、対地間トラヒック量を推定するときの推定精度の低下を防止できる。また、このように経路の到達性のあるブロック分割は比較的容易であるので、ブロック分割を容易なものとすることができる。
【００１１】
また、本発明は、対地間トラヒック推定装置が、ブロック間接続情報を作成するステップにおいて、トポロジ情報に示されるノード群を、複数のブロックに分割するとき、ルーティング情報を参照して、当該ブロックに属するノードに入力し、当該ブロックに属するノードから出力する対地間トラヒックが、当該ブロックに属するノードのみを経由するようにブロックを分割することを特徴とする。
【００１２】
このようにすることで、対地間トラヒック推定装置は、当該ブロックに属するノードに入力し、当該ブロックに属するノードから出力する対地間トラヒックが、当該ブロックに属するノードのみを経由するようにブロックを分割する。よって、例えば、対地間トラヒックの入力ノードおよび出力ノードが、同じブロック内のノードＡ，Ｂであるとき、対地間トラヒックは、ノードＡ→同じブロックのノード→ノードＢという経路をとる。つまり、対地間トラヒックは、他のブロックのノードを経由しない。これにより、対地間トラヒックの経路が必要以上にブロックを経由することによる対地間トラヒック量の推定精度の低下が発生しない。
【００１３】
また、本発明は、対地間トラヒック推定装置が、ブロック毎対地間トラヒック量推定値から、対地間トラヒックの経由するブロックそれぞれにおける対地間トラヒックのトラヒック量の推定値を読み出し、その読み出したトラヒック量の推定値をもとに、当該対地間トラヒックのトラヒック量の推定値を計算するとき、（１）当該対地間トラヒックの経由するブロックが１つの場合、当該ブロックにおける当該対地間トラヒックのトラヒック量の推定値を出力し、（２）当該対地間トラヒックの経由するブロックが複数の場合、当該対地間トラヒックが入力されるブロックへのトラヒック量の推定値に、当該ブロックから出力されるすべてのトラヒック量の推定値の合計値に対する、当該対地間トラヒックが当該ブロックから次の経由ブロックに出力されるトラヒック量の推定値の比率を掛ける処理を、経由するブロックそれぞれに対し実行することで、当該対地間トラヒックのトラヒック量の推定値を計算する。
【００１４】
このようにすることで、対地間トラヒック推定装置は、対地間トラヒックの入力ノードと出力ノードとが異なるブロックに属する場合、つまり対地間トラヒックの経路が複数のブロックを経由する場合でも、そのそれぞれのブロックの対地間トラヒック量の推定値を用いて、対地間トラヒックのトラヒック量の推定値を計算できる。例えば、対地間トラヒックがブロック＃２の入力ノードから、ブロック＃２→ブロック＃１→ブロック＃３という経路で、このブロック＃３内の出力ノードに到達するとき、対地間トラヒック推定装置は、ブロック＃２，＃１，＃３における対地間トラヒック量の推定値を用いて、以下のような計算を行う。すなわち、対地間トラヒック推定装置は、（ブロック＃２における対地間トラヒックの入力ノードから、ブロック＃１におけるこの対地間トラヒックの入力ノードへのトラヒック量の推定値）＊（ブロック＃２における対地間トラヒックの出力ノードから、ブロック＃３における対地間トラヒックの入力ノードへのトラヒック量の推定値）÷（ブロック＃２における対地間トラヒックの出力ノードから、他の各ブロックへ出力されるトラヒック量の推定値の総量）を計算する。これにより、対地間トラヒックがブロック＃２からブロック＃１を経由して、ブロック＃３に入力されるトラヒック量の推定値を求めることができる。そして、その後、（ブロック＃３に入力されるトラヒック量の推定値）＊（対地間トラヒックのブロック＃３における入力ノードから出力ノードまでのトラヒック量の推定値）÷（ブロック＃３から出力されるトラヒック量の推定値の総量）を計算することで、対地間トラヒックのブロック＃２の入力ノードからブロック＃３の出力ノードまでの対地間トラヒック全体の推定値を計算することができる。つまり、対地間トラヒック推定装置は、対地間トラヒックが複数のブロックを経由するとき、ブロック毎対地間トラヒックを用いて、そのブロックからの各ブロックへのトラヒック量の総量に対する、次のブロックへのトラヒック量の割合を掛ける。この処理を対地間トラヒックがブロックを経由するたびに繰り返すことで、対地間トラヒックの推定値を計算することができる。
【００１５】
また、本発明は、対地間トラヒック推定装置が、ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算するとき、リンクトラヒック情報を参照して、ネットワーク全体の対地間トラヒックのトラヒック量の推定値の初期値を計算し、ブロックごとに、当該ブロックを経由する対地間トラヒックそれぞれのトラヒック量の推定値の初期値を加算することで、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値の初期値を計算する。
【００１６】
このようにすることで、対地間トラヒック推定装置は、ネットワーク全体の対地間トラヒック量の推定値の初期値を計算し、その初期値をブロックごとに加算するので、ブロック毎対地間トラヒック量の推定値の初期値の推定精度を高めることができる。これにより、対地間トラヒック量の推定値の推定精度も高めることができる。
【００１７】
また、本発明は、請求項１ないし請求項５のいずれか１項に記載の対地間トラヒック推定方法を、コンピュータである対地間トラヒック推定装置に実行させるためのプログラムである。
【００１８】
このようなプログラムによれば、一般的なコンピュータに、請求項１ないし請求項５のいずれか１項に記載の対地間トラヒック推定方法を実行させることができる。
【発明の効果】
【００１９】
本発明によれば、ネットワークの対地間トラヒック量の推定値Ｔを求めるための計算時間を短縮することができる。
【図面の簡単な説明】
【００２０】
【図１】本実施の形態の対地間トラヒック推定装置の動作概要を示した図である。
【図２】本実施の形態で扱うネットワークの構成例を示した図である。
【図３】本実施の形態の対地間トラヒック推定装置の構成例を示した図である。
【図４】図３の対地間トラヒック推定装置によるネットワークのブロック分割を例示した図である。
【図５】図３の対地間トラヒック推定装置によるネットワークのブロック分割を例示した図である。
【図６】図５のネットワークのブロック＃１のトポロジ情報を示した図である。
【図７】図３の対地間トラヒック推定装置による対地間トラヒックの計算処理例を説明するために引用した図である。
【図８】（ａ）は、ブロック毎リンクトラヒック情報を例示した図であり、（ｂ）は、ブロック毎ルーティング情報を例示した図であり、（ｃ）は、ブロック間接続情報を例示した図である。
【図９】（ａ）は、図５のブロック＃１の対地間トラヒック量推定値を例示した図であり、（ｂ）は、図５のブロック＃２の対地間トラヒック量推定値を例示した図であり、（ｃ）は、ブロック＃３の対地間トラヒック量推定値を例示した図である。
【図１０】図３の対地間トラヒック推定装置の処理手順を示したフローチャートである。
【図１１】（ａ）は、本実施の形態のトポロジ情報の例であり、（ｂ）〜（ｄ）は、図３の対地間トラヒック推定装置による（ａ）のトポロジ情報の各ノードのブロック分割例を示した図である。
【図１２】図１１の（ｂ）に示すブロック分割をした場合の対地間トラヒックの計算例を説明するために引用した図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態とする）について説明する。まず、本実施の形態の対地間トラヒック推定装置の動作概要を、図１を用いて説明する。なお、以下の説明において、対地間トラヒックとは、入力ノードから出力ノードまで、各リンクを経由して流れるトラヒック（フロー）のことをいう。対地間トラヒック推定装置は、ネットワークの対地間トラヒックそれぞれのトラヒック量（対地間トラヒック量）の推定値を計算する。
【００２２】
まず、対地間トラヒック推定装置は、ネットワークのルーティング情報（各トラヒックがネットワークのどのリンクを経由するか示した情報）およびリンクトラヒック情報（ネットワーク内の各リンクのトラヒック量を示した情報）の入力を受け付ける。そして、このネットワークをいくつかのブロックに分割する。次に、入力されたルーティング情報およびリンクトラヒック情報をブロックごとに分割し、分割したブロック単位の対地間トラヒックの推定（対置間トラヒック量の推定値の計算処理）を行う。そして、このブロック単位の推定結果を統合し、全体の推定結果、すなわち、ネットワーク全体の対地間トラヒック量の推定結果を得る。
【００２３】
ここで、対地間トラヒック推定装置は、対置間トラヒック量の推定値を求めるとき、ブロック単位で処理する。つまり、対地間トラヒック推定装置は、ブロック単位で、前記した式（２）に準じて行列計算を行うが、このときに用いるルーティング行列のサイズは、ブロック毎のルーティング行列のサイズである。つまり、対地間トラヒック量の推定値の計算に用いる行列のサイズを小さくできるので、計算時間を短縮できる。また、対地間トラヒック推定装置は、ネットワークを複数のブロックに分割し、そのブロック毎に対地間トラヒック量の推定値の計算を行うので、処理の並列化を図り、計算時間を短縮できる。つまり、対地間トラヒック推定装置は、対地間トラヒック量の推定値の計算にあたり、ネットワークをブロック単位に分割して処理することで、（１）対地間トラヒック量の推定値の計算時間を短縮することができる。また、（２）ブロックごとに対地間トラヒック量の推定値の計算を行うので、処理を並列化でき、大幅に計算時間を短縮できる。
【００２４】
次に、図２を用いて、本実施の形態で扱うネットワークの構成例を説明する。ネットワークは、図２に例示するように１以上のノード（ノード番号１〜１５）と、そのノード間を接続するリンクとにより構成される。図２において、ノード８〜１５には、他のノードと接続されていないリンクがあるが、このようなリンクを外部リンクと呼ぶ。この外部リンクは、ネットワークへのトラヒックの入力ポイント、出力ポイントとなるリンクである。この外部リンクは、例えば、別のネットワークやユーザの端末装置に接続されている。対地間トラヒック（例えば、対地間トラヒックＡ，Ｂ）は、このような外部リンクを介して、ノードに入力され、リンクおよびノードを経由して、ネットワーク内の別のノード（または同じノード）から出力される。なお、ネットワークを構成するノードは、例えば、ＳＯＮＥＴ（Synchronous Optical NETwork）／ＳＤＨ（Synchronous Digital Hierarchy）クロスコネクトや、波長クロスコネクト等の伝送装置、ルータ、レイヤ２スイッチ等である。リンクは、ノード間に存在し、情報転送の媒体であり、例えば、光ファイバ等である。
【００２５】
次に、図３を用いて、対地間トラヒック推定装置１００の構成を説明する。この対地間トラヒック推定装置１００は、前記したとおり、ネットワークの各ノードを複数のブロックに分割し、そのブロックごとの対地間トラヒック量の推定値をもとに、ネットワーク全体の対地間トラヒック量の推定値を計算する。このような対地間トラヒック推定装置１００は、入力部１１０と、ブロック分割部１２１と、ブロック毎ルーティング情報作成部１２２と、ブロック毎リンクトラヒック情報作成部１２３と、初期値計算部１２４と、ブロック毎対地間トラヒック量推定部１２５と、ブロック統合部１２６と、トポロジ情報１３１と、ルーティング情報１３２と、リンクトラヒック情報１３３と、出力部１４０とを備える。入力部１１０は、トポロジ情報１３１、ルーティング情報１３２、リンクトラヒック情報１３３等の入力を受け付ける。また、出力部１４０は、ブロック統合部１２６による計算結果（各対地間トラヒック量の推定値）を出力する。
【００２６】
入力部１１０および出力部１４０は、入出力インタフェースから構成される。また、ブロック分割部１２１と、ブロック毎ルーティング情報作成部１２２と、ブロック毎リンクトラヒック情報作成部１２３と、初期値計算部１２４と、ブロック毎対地間トラヒック量推定部１２５と、ブロック統合部１２６とは、この対地間トラヒック推定装置１００の備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、入力部１１０経由で入力された、トポロジ情報１３１と、ルーティング情報１３２と、リンクトラヒック情報１３３とは、この対地間トラヒック推定装置１００の記憶部（図示省略）に記憶される。この記憶部は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、対地間トラヒック推定装置１００をプログラム実行処理により実現する場合、記憶部には、この対地間トラヒック推定装置１００の機能を実現するためのプログラムが格納される。また、この記憶部には、対地間トラヒック量の推定値の計算過程で作成される、ブロック間接続情報１３４、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６、ブロック毎対地間トラヒック量推定値１３７等が記憶される。
【００２７】
トポロジ情報１３１は、ネットワークに存在するノードと、どのノード間のリンクが存在するかを示した情報である。このトポロジ情報１３１は、ＯＳＰＦ（Open Shortest Path First）において利用されるリンクコストの値を含んでいてもよい。例えば、トポロジ情報１３１には、図４に例示するように、ネットワーク内に存在するノードと、そのノード間を接続するリンクの情報が示される。なお、ここでは、ノード間を接続するリンクを方向別に示している。例えば、ノード２からノード１へのリンクは「リンク＃１」であり、ノード１からノード２へのリンクは「リンク＃２」であることを示す。
【００２８】
ルーティング情報１３２は、ネットワーク内の各対地間トラヒックの経路情報を、各対地間トラヒックの経由する一連のリンクの識別情報（リンク番号）で示した情報である。なお、このルーティング情報１３２は、例えば、ネットワーク内のルーティングがＯＳＰＦにより行われる場合を想定して、シミュレーション等により求めてもよい。このルーティング情報１３２は、例えば、リンク数×フロー（対地間トラヒック）数の行列により表される。なお、このルーティング情報１３２は、各対地間トラヒックの経由するノードの識別情報で示してもよい。
【００２９】
リンクトラヒック情報１３３は、ネットワーク内のリンクごとに、そのリンクのリンクトラヒック量を示した情報である。
【００３０】
ブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内の各ノードを複数のブロックに分割する。例えば、このブロック分割部１２１は、図２に例示したネットワークの各ノードを、図５に示すように、ブロック＃１〜ブロック＃５の５つのブロックに分割する。ここでのブロック分割は、ネットワークのノードをいずれかのブロックに属するようにする。なお、図５のブロック＃１のトポロジ情報は、例えば、図６に例示するようになる。ここでのブロック分割の方法は、様々な方法が考えられるが、同じブロック内においてトラヒックの入力ノードと出力ノードとなるノード間の経路が他のブロックを経由しないようにするのが好ましい。例えば、図４に示すように、ブロック＃２のノード８から、ノード４への経路において、ブロック＃３やブロック＃１を経由しないようにするのが好ましい。この理由については詳細は後記するが、ブロック統合部１２６が、ブロック毎対地間トラヒック量推定値１３７をもとに、ネットワーク全体の対地間トラヒック量の推定値を計算するとき、対地間トラヒックの経由するブロックの数が少ない方が、推定値の計算精度を向上させることができるからである。
【００３１】
このブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内の各ノードを複数のブロックに分割すると、その分割結果をブロック間接続情報１３４として記録する。このブロック間接続情報１３４は、分割したブロックに属するノードと別のブロックに属するノードを接続するリンクを示した情報である（図８（ｃ）参照）。例えば、図８（ｃ）に示すブロック間接続情報１３４には、リンク番号「リンク＃５」は、ブロック番号「ブロック＃２」に属し、このリンクはノード４に接続されるリンクであることを示す。
【００３２】
図３のブロック毎ルーティング情報作成部１２２は、ブロック間接続情報１３４およびルーティング情報１３２を用いて、ルーティング情報１３２に示される対地間トラヒックそれぞれの、各ブロックにおけるルーティング情報を作成し、ブロック毎ルーティング情報１３５に記録する。例えば、このブロック毎ルーティング情報１３５には、図８（ｂ）に示すようなルーティング情報が記憶される。図８（ｂ）は、図６のブロック＃１のルーティング情報であり、対地間トラヒック番号「１」の対地間トラヒックは、「リンク＃５，＃８」を経由することを示す。このブロック毎ルーティング情報１３５は、ブロック毎対地間トラヒック量推定部１２５が、ブロック毎対地間トラヒック量の推定値を計算するときに参照される。
【００３３】
ブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３をブロックごとに分割して、ブロック毎リンクトラヒック情報１３６を作成する。このブロック毎リンクトラヒック情報１３６には、図８（ａ）に示すようなリンクトラヒック情報が記憶される。図８（ａ）は、図６のブロック＃１のリンクトラヒック情報であり、リンク番号「１」のリンクトラヒック量は「Ｘ１」であることを示す。このブロック毎リンクトラヒック情報１３６は、ブロック毎対地間トラヒック量推定部１２５が、ブロック毎対地間トラヒック量の推定値を計算するときに参照される。また、初期値計算部１２４が、ブロックごとの交流トラヒック量の推定値の初期値を計算するときに参照される。
【００３４】
図３の初期値計算部１２４は、ブロック毎リンクトラヒック情報１３６を参照して、Ｇｒａｖｉｔｙ法等により、ブロックごとに、そのブロックの対地間トラヒック量の推定値の初期値を計算する。計算した初期値は、記憶部の所定領域に記憶しておく。
【００３５】
ブロック毎対地間トラヒック量推定部１２５は、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６およびブロックごとの対地間トラヒック量の推定値の初期値を用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により、ブロックごとの対地間トラヒック量の推定値を計算する。そして、その計算結果をブロック毎対地間トラヒック量推定値１３７として記憶部の所定領域に記憶する。このブロック毎対地間トラヒック量推定値１３７は、ブロック統合部１２６が、ブロックごとの対地間トラヒック量の推定値を統合して対地間トラヒックの推定値を求めるときに参照される。
【００３６】
例えば、ブロック毎対地間トラヒック量推定値１３７には、図９（ａ）〜（ｃ）に示すようにブロック＃１〜＃３それぞれの、対地間トラヒック量の推定値が記録される。図９（ａ）のブロック＃１の対地間トラヒック量の推定値は、ブロック＃１において入口（入力ノード）がノード２（リンク＃５）で、出口（出力ノード）がノード３（リンク＃１０）の対地間トラヒックのトラヒック量の推定値は「Ｔ１（５，１０）」であることを示す。
【００３７】
ブロック統合部１２６は、ブロック間接続情報１３４およびブロック毎ルーティング情報１３５を参照して、対地間トラヒックごとに、その対地間トラヒックの経由するブロックと、そのブロックにおける経路を特定する。そして、この対地間トラヒックのブロックそれぞれにおける対地間トラヒック量の推定値をブロック毎対地間トラヒック量推定値１３７から読み出し、この読み出した対地間トラヒック量の推定値を用いて、この対地間トラヒックのトラヒック量の推定値を計算する。このような処理を各対地間トラヒックに対し実行し、計算した各対地間トラヒックのトラヒック量の推定値を出力部１４０経由で出力する。
【００３８】
ここで、例えば、ブロック統合部１２６は、図７のブロック＃２のノードに入力される対地間トラヒックの推定値の計算に関し、以下の処理を行う。なお、以下の説明において、Ｔ（ｘ，ｙ）は対地間トラヒック量の推定値を示し、ｘは、対地間トラヒックの入力リンク番号を示し、ｙは、出力リンク番号を示す。なお、ＴＮ（ｘ，ｙ）は、ブロック＃Ｎにおける対地間トラヒック量の推定値を示す。
（１）対地間トラヒックの経由するブロックが、１つの場合
例えば、推定値の計算対象の対地間トラヒックが、図７におけるＴ（１７，２０）や、Ｔ（１９，１８）の場合、これらの対地間トラヒックは、ブロック＃２のみを経由する。よって、ブロック統合部１２６は、ブロック毎対地間トラヒック量推定値１３７に示される、ブロック＃２のＴ２（１７，２０）や、Ｔ２（１９，１８）をそのまま用いる。つまり、Ｔ（１７，２０）＝Ｔ２（１７，２０）、Ｔ（１９，１８）＝Ｔ２（１９，１８）とする。つまり、ブロック統合部１２６は、対地間トラヒックの経由するブロックが１つの場合、ブロック毎対地間トラヒック量推定値１３７の、そのブロックにおける対地間トラヒック量の推定値をそのまま出力する。
【００３９】
（２）対地間トラヒックの経由するブロックが、複数の場合
例えば、求める対地間トラヒックが、図７におけるＴ（１７，２６）やＴ（１７，２８）の場合、これらの対地間トラヒックは、ブロック＃２，＃１，＃３を経由する。この場合、対地間トラヒックは複数のブロックを経由するので、ブロック統合部１２６は、ブロックを経由するたび、そのブロックから流出する対地間トラヒック量の推定値の合計に対する、そのブロックの次のブロックへ入力される対地間トラヒック量の推定値の比率を掛け算することで対地間トラヒックのトラヒック量の推定値を計算する。
【００４０】
例えば、ブロック統合部１２６が、図７のＴ（１７，２６）を計算する場合、まず、ブロック統合部１２６は、ブロック毎対地間トラヒック量推定値１３７から、ブロック＃２，＃１，＃３の対地間トラヒックの推定値を読み出す。そして、この中から、ブロック＃２におけるＴ（１７，２６）の対地間トラヒック量の推定値（Ｔ２（１７，５））を抽出する。次に、このＴ２（１７，５）が入力されるブロック＃１における入力ノード（ノード２）から、他のブロックまたはノードへ流出する対地間トラヒック量の推定値の総量（Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２））を求める。そして、この総量に対する、対地間トラヒックの次のブロック（ブロック＃３）において、この対地間トラヒックの入力を受け付けるノード（ノード５）への対地間トラヒック量の推定値（Ｔ１（５，８））の比率を求める。つまり、Ｔ１（５，８）／（Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２））を求める。これにより、ブロック＃１に入力された対地間トラヒックのトラヒック量のうち、どの程度のトラヒック量がブロック＃３に到達するかが分かる。そして、前記したＴ２（１７，５）に、この比率を掛けた値を求める。つまり、Ｔ２（１７，５）＊Ｔ１（５，８）／｛Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２）｝を求める。この後、このブロック＃３における対地間トラヒックの入力ノード（ノード５）から他のブロックまたはノードへ流出する総量（Ｔ３（８，２６）＋Ｔ３（８，２８））を求め、この総量に対する対地間トラヒックの出力ノードへの地間トラヒック量の推定値（Ｔ３（８，２６））の比率を掛ける。
以上をまとめると、Ｔ（１７，２６）＝Ｔ２（１７，５）＊｛Ｔ１（５，８）／（Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２））｝＊Ｔ３（８，２６）／｛Ｔ３（８，２６）＋Ｔ３（８，２８）｝として求めることができる。
【００４１】
＜処理手順＞
次に、図３を参照しつつ、図１０を用いて、対地間トラヒック推定装置１００の処理手順を説明する。まず、対地間トラヒック推定装置１００は事前準備として、入力部１１０経由で、トポロジ情報１３１、ルーティング情報１３２、リンクトラヒック情報１３３の入力を受け付け、記憶部に記憶しておくものとする。
【００４２】
そして、入力部１１０からの指示入力に基づき、ブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内のノード群を複数のブロックに分割する（Ｓ１：ブロック分割）。そして、その分割結果をブロック間接続情報１３４として記録する。また、ブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３をブロックごとに分割して、各ブロックのリンクトラヒック情報を示したブロック毎リンクトラヒック情報１３６を作成する（Ｓ２：ブロック毎リンクトラヒック情報作成）。作成したブロック毎リンクトラヒック情報１３６を記憶部に記憶する。さらに、ブロック毎ルーティング情報作成部１２２は、ブロック間接続情報１３４およびルーティング情報１３２を用いて、ブロックごとのルーティング情報を示したブロック毎ルーティング情報１３５を作成する（Ｓ３：ブロック毎ルーティング情報作成）。作成したブロック毎ルーティング情報１３５を記憶部に記憶する。
【００４３】
そして、初期値計算部１２４は、ブロック毎リンクトラヒック情報１３６を参照して、Ｇｒａｖｉｔｙ法等によりブロックごとに、当該ブロックにおける対地間トラヒック量の推定値の初期値を計算する（Ｓ４：初期値計算）。計算した初期値を記憶部に記憶する。
【００４４】
次に、ブロック毎対地間トラヒック量推定部１２５は、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６およびブロックごとの対地間トラヒック量の推定値の初期値を用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により、ブロックそれぞれの対地間トラヒック量の推定値を計算する（Ｓ５：ブロック毎対地間トラヒック量推定）。そして、その計算結果を、ブロック毎対地間トラヒック量推定値１３７として記憶部の所定領域に記憶する。
【００４５】
次に、ブロック統合部１２６は、ブロック間接続情報１３４およびブロック毎ルーティング情報１３５を参照して、対地間トラヒックそれぞれの経由するブロックと、そのブロックそれぞれにおける経路を特定する。そして、ブロック毎対地間トラヒック量推定値１３７から、この特定した１以上のブロックそれぞれにおける対地間トラヒック量の推定値を読み出し、読み出した対地間トラヒック量の推定値を統合して、対地間トラヒックそれぞれのトラヒック量の推定値を計算し（Ｓ６：対地間トラヒック推定値計算）、出力部１４０経由で出力する。
【００４６】
このように、対地間トラヒック推定装置１００は、ネットワークのトポロジを複数のブロックに分割し、そのブロックごとの対地間トラヒック量の推定値を統合することで対地間トラヒック量の推定値を計算する。よって、対地間トラヒック量の推定値の計算に用いる行列サイズを小さくできるので、対地間トラヒック量の推定値の計算時間を従来よりも短縮できる。
【００４７】
なお、前記した実施の形態において、図３の対地間トラヒック推定装置１００のブロック分割部１２１は、トポロジ情報１３１に示される各ノードを以下のようにしてブロック分割してもよい。例えば、図１１（ａ）に示すトポロジ情報１３１が与えられたとき、ブロック分割部１２１は、図１１（ｂ）に示すように、単に、各ノードがいずれかのブロックに属するように分割してもよい。また、図１１（ｃ）に示すように、各ノードをいずれかのブロックに属し、かつ、同じブロックに属する任意の２つのノードが、同じブロックのノードのみを経由して到達可能であるようにブロック分割してもよい。このように、ブロック分割部１２１が、同じブロックに属する任意の２つのノードについて、同じブロックのノードのみを経由して到達可能であるようにブロック分割しておけば、対地間トラヒックの経路が同じブロックのみを経由する可能性を高くすることができる。よって、対地間トラヒック量の推定値を求めるにあたり、対地間トラヒックが異なるブロックをまたぐことによるトラヒック量の推定値の補正を行う可能性を低くできるので、トラヒック量の推定精度が低下しにくくなる。また、このように経路の到達性を確保するようなブロック分割は比較的容易であるので、ブロック分割を容易なものとすることができる。
【００４８】
さらに、ブロック分割部１２１は、ルーティング情報１３２を参照して、図１１（ｄ）に示すように、当該ブロックに属するノードに入力し、当該ブロックに属するノードから出力する対地間トラヒックが、当該ブロックに属するノードのみを経由するようにブロックを分割してもよい。このようにすることで、対地間トラヒックの経路が必要以上にブロックをまたぐことによるトラヒック量の推定精度の低下が発生しにくくなる。
【００４９】
なお、例えば、ブロック分割部１２１は、図１１（ｂ）に示すようなブロック分割をした場合、ノード５からノード６へは、ブロック＃３またはブロック＃１を経由するので、ブロックをまたぐ場合の対地間トラヒック量の計算処理が必要となるが、図１１（ｂ）に示すようなブロック分割は容易である。
【００５０】
一方、図１１（ｃ）に示すようなブロック分割をした場合、ノード５からノード６へのトラヒックは、ブロック＃２のノード７を経由することも考えられる、よって、ブロック毎ルーティング情報１３５を参照して、ノード５からノード６へのトラヒックが、ブロック＃２のノード７を経由するのであれば、前記したブロックをまたぐ場合の対地間トラヒック量の計算処理が必要となる。なお、この図１１（ｃ）に示すようなブロック分割の場合もブロック内のノード間の経路到達性が確保できればよいので、ブロック分割は比較的容易である。
【００５１】
さらに、図１１（ｄ）に示すようなブロック分割をした場合、このブロック分割は、ルーティング情報１３２に従い、ノード５からノード６へのトラヒックは、同じブロック＃２内のノード７を経由することを確認して行ったものなので、前記したブロックをまたぐ場合の対地間トラヒック量の計算処理は必要ない。
【００５２】
なお、ブロック分割部１２１が、図１１（ｂ）に示すようなブロック分割を行った場合において、各ノードが図１２に例示するようなリンクにより接続されていたとき、ブロック＃２のノード５に入力され、ノード７を経由してノード６から出力される対地間トラヒックのトラヒック量の推定値（Ｔ（１６，１３））は以下のようにして計算する。
Ｔ（１６，１３）＝Ｔ２（１６，１）＊Ｔ３（１，８）／｛Ｔ３（１，８）＋Ｔ３（１，９）＋Ｔ３（１，１１）｝＊Ｔ２（８，１３）／｛Ｔ２（８，１３）＋Ｔ２（８，１７）｝
【００５３】
また、前記した実施の形態において、対地間トラヒック推定装置１００の初期値計算部１２４は、以下のようにしてブロックごとの対地間トラヒック量の推定値の初期値を計算してもよい。すなわち、初期値計算部１２４は、リンクトラヒック情報１３３を参照して、ネットワーク全体の対地間トラヒック量の推定値の初期値Ｔｇを計算する。そして、初期値計算部１２４は、この対地間トラヒック量の推定値の初期値Ｔｇを加算して、そのブロックにおける対地間トラヒックの推定値の初期値を計算する。例えば、初期値計算部１２４は、図７のブロック＃１における、ノード２のリンク＃５からノード２のリンク＃８までの対地間トラヒックの推定値の初期値Ｔｇ１（５，８）を以下のようにして計算する。
Ｔｇ１（５，８）＝Ｔｇ（１７，２６）＋Ｔｇ（１７，２８）＋Ｔｇ（１９，２６）＋Ｔｇ（１９，２８）
【００５４】
このようにすることで、初期値計算部１２４は、ブロックごとの対地間トラヒック量の推定値の初期値の計算精度を向上できる。これにより、対地間トラヒック量の推定精度も向上できる。
【００５５】
なお、前記した実施の形態において初期値計算部１２４は、ブロックごとの対地間トラヒック量の推定値の初期値を計算するとき、ブロック毎リンクトラヒック情報１３６と、ブロック毎ルーティング情報１３５とを用いて計算してもよい。ブロック毎対地間トラヒック量推定部１２５は、このようにして計算された初期値を用いることで、ブロックごとの対地間トラヒック量の推定値の推定精度を向上させることができる。
【符号の説明】
【００５６】
１００  対地間トラヒック推定装置
１１０  入力部
１２１  ブロック分割部
１２２  ブロック毎ルーティング情報作成部
１２３  ブロック毎リンクトラヒック情報作成部
１２４  初期値計算部
１２５  ブロック毎対地間トラヒック量推定部
１２６  ブロック統合部
１３１  トポロジ情報
１３２  ルーティング情報
１３３  リンクトラヒック情報
１３４  ブロック間接続情報
１３５  ブロック毎ルーティング情報
１３６  ブロック毎リンクトラヒック情報
１３７  ブロック毎対地間トラヒック量推定値
１４０  出力部
【図１】
2010283703.tif 000003
【図２】
2010283703.tif 000004
【図３】
2010283703.tif 000005
【図４】
2010283703.tif 000006
【図５】
2010283703.tif 000007
【図６】
2010283703.tif 000008
【図７】
2010283703.tif 000009
【図８】
2010283703.tif 000010
【図９】
2010283703.tif 000011
【図１０】
2010283703.tif 000012
【図１１】
2010283703.tif 000013
【図１２】
2010283703.tif 000014