(57)【要約】【課題】大規模ネットワークにおける対地間トラヒック量の推定値Ｔを求めるための計算時間を短縮する。【解決手段】対地間トラヒック推定装置は、ネットワークのノード群のうち対地間トラヒックの入出力ノードを含むサブブロックを作成し、これらのサブブロックを対地間トラヒックの経路でつないだブロックを作成する。また、ルーティング情報とリンクトラヒック情報もブロックごとに分割し、分割したブロックごとのルーティング情報およびリンクトラヒック情報をもとに対地間トラヒック量の推定値（ブロック毎対地間トラヒック量の推定値）を計算する。そして、ネットワークの各対地間トラヒックの推定値を求める場合には、このブロック毎対地間トラヒック量の推定値を出力する。【選択図】図１
2010283702.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（Ａ）の計算時間も増加するので、ネットワーク規模が大きくなるにつれ、対地間トラヒック量の推定値Ｔを求めるための計算時間が莫大になるという問題があった。
【０００６】
そこで、本発明は、前記した問題を解決し、ネットワークの対地間トラヒック量の推定値Ｔを求めるための計算時間を短縮することを目的とする。
【課題を解決するための手段】
【０００７】
前記した課題を解決するため、本発明は、複数のノードがリンクにより接続されるネットワークにおいて、ネットワークのいずれかのノードに入力され、ノードまたは他のノードに出力される対地間トラヒックのトラヒック量の推定を行う対地間トラヒック推定装置が、（１）ネットワークにおける複数のノードおよびそのノード間を接続するリンクを示したトポロジ情報と、（２）リンクそれぞれのトラヒック量を示すリンクトラヒック情報と、（３）対地間トラヒックごとに、その対地間トラヒックにおいて経由するリンクを示したルーティング情報とを記憶する記憶部を備え、ルーティング情報を参照して、トポロジ情報に示されるノード群のうち、対地間トラヒックの入力ノードまたは出力ノードを含む複数のサブブロックを作成し、その作成したサブブロックに属するノードおよびそのノードに接続されるリンクを示したサブブロック情報を作成し、記憶部に記憶する。また、サブブロック情報に示されるサブブロック群から選択した任意の２つのサブブロックの組み合わせそれぞれについて、ルーティング情報を参照して、選択した２つのサブブロックのいずれか一方のノードを入力ノードとし、選択した２つのサブブロックのいずれか一方のノードを出力ノードとする１以上の対地間トラヒックについて、対地間トラヒックそれぞれの経由するノード群を選択し、この選択したノード群からなるブロックを構成し、ブロックのノードおよびリンクを示したブロック情報を作成し、記憶部に記憶する。さらに、リンクトラヒック情報およびブロック情報を参照して、ブロックごとに、当該ブロックにおけるリンクトラヒック情報であるブロック毎リンクトラヒック情報を作成し、記憶部に記憶し、ルーティング情報を参照して、分割したブロックごとに、ルーティング情報に示される対地間トラヒックそれぞれの、ブロックそれぞれにおけるルーティング情報であるブロック毎ルーティング情報を作成し、記憶部に記憶する。そして、ブロック毎リンクトラヒック情報を参照して、ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算し、記憶部に記憶する。次に、ブロック毎リンクトラヒック情報、ブロック毎ルーティング情報および初期値を用いて、ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値を計算し、計算した推定値を示すブロック毎対地間トラヒック量推定値を出力する。
【０００８】
このようにすることで、対地間トラヒック推定装置は、対地間トラヒック量の推定値を計算するとき、ブロックごとに分割したルーティング情報（ルーティング行列）を用いて計算する。つまり、対地間トラヒック推定装置は、トラヒック量の推定値Ｔを計算するときに用いる行列サイズを小さくできるので、トラヒック量の推定値Ｔの計算時間を短縮することができる。
【０００９】
また、本発明は、対地間トラヒック推定装置が、ブロック情報を作成するとき、前記サブブロック情報に示されるサブブロックから選択した任意の２つのサブブロックの組み合わせそれぞれについて、その選択した２つのサブブロックの一方のサブブロックにおけるサブブロック境界ノードと、他方のサブブロックにおけるサブブロック境界ノードとの間の最短経路のノード群と、選択した２つのサブブロックのノード群とでブロックを構成する。
【００１０】
このようにすることで、対地間トラヒック推定装置は、ブロックを構成するとき、サブブロック情報から選択した２つのサブブロックそれぞれの間をつなぐノード群としてサブブロック境界ノード間の最短経路を用いる。ここで、通常、ルーティング情報に示される対地間トラヒックの経路は、ＯＳＰＦ（Open Shortest Path First）等によりシミュレーションされる入力ノードから出力ノードまでの最短経路であるので、構成されたブロックは、対地間トラヒックの入力ノードから出力ノードまでの経路を含む可能性が高い。よって、対地間トラヒック推定装置は、対地間トラヒックの入力ノードから出力ノードまでの経路を含む可能性が高いブロックを容易に作成できる。
【００１１】
また、本発明は、対地間トラヒック推定装置が、サブブロックを作成するとき、トポロジ情報に示されるノード群を、同じサブブロックに属する任意の２つのノードが、当該サブブロックに属するノードのみを経由して到達可能となるようにする。
【００１２】
このように対地間トラヒック推定装置が、同じサブブロックに属する任意の２つのノードを、当該サブブロックに属するノードのみを経由して到達可能としておけば、例えば、このブロックの対地間トラヒックの入力ノードおよび出力ノードを同じサブブロック内のノードＡ，Ｂとしたとき、このサブブロックの対地間トラヒックの経路として、ノードＡ→同じサブブロックのノード→ノードＢという経路をとる可能性を向上できる。これにより、作成したサブブロックをもとに、これらのサブブロックに入出力する対地間トラヒックの経由するノード群でブロックを構成するとき、ノードＡ→他のサブブロックのノード→ノードＢという経路をとることによるブロック内のノード数の増加を抑えることができる。よって、ブロック毎対地間トラヒック量推定部が、ブロックごとの対地間トラヒック量の推定値を計算するときの計算時間を低減できる。
【００１３】
また、本発明は、対地間トラヒック推定装置が、サブブロックを作成するとき、ルーティング情報を参照して、当該サブブロックに属するノードに入力し、当該サブブロックに属するノードから出力する対地間トラヒックが、当該サブブロックに属するノードのみを経由するようにする。
【００１４】
このようにすることで、対地間トラヒック推定装置は、当該ブロックに属するノードに入力し、当該ブロックに属するノードから出力する対地間トラヒックが、当該ブロックに属するノードのみを経由するようにブロックを分割する。よって、例えば、対地間トラヒックの入力ノードおよび出力ノードが、同じサブブロック内のノードＡ，Ｂであるとき、対地間トラヒックは、ノードＡ→同じサブブロックのノード→ノードＢという経路をとる。これにより、作成したサブブロックをもとに、これらのサブブロックに入出力する対地間トラヒックが経由するノード群でブロックを作成するとき、ブロック内のノードの増加を抑えることができる。よって、ブロック毎対地間トラヒック量推定部が、ブロックごとの対地間トラヒック量の推定値を計算するときの計算時間を低減できる。
【００１５】
また、本発明は、対地間トラヒック推定装置が、ブロックごとに、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定に用いる初期値を計算するとき、リンクトラヒック情報を参照して、ネットワーク全体の対地間トラヒックのトラヒック量の推定値の初期値を計算し、ブロックごとに、当該ブロックを経由する対地間トラヒックそれぞれのトラヒック量の推定値の初期値を加算することで、当該ブロックにおける対地間トラヒックそれぞれのトラヒック量の推定値の初期値を計算する。
【００１６】
このようにすることで、対地間トラヒック推定装置は、ネットワーク全体の対地間トラヒック量の推定値の初期値を計算し、その初期値をブロックごとに加算するので、ブロックごとの対地間トラヒック量の推定値の初期値の推定精度を高めることができる。これにより、ネットワーク全体の対地間トラヒック量の推定値の推定精度も高めることができる。
【００１７】
また、本発明は、対地間トラヒック推定装置が、対地間トラヒック量の推定値の計算対象となる対地間トラヒックの入力ノードおよび出力ノードの指示入力を受け付けたとき、リンクトラヒック情報およびブロック情報を参照して、計算対象の対地間トラヒックの属するブロックにおけるリンクトラヒック情報であるブロック毎リンクトラヒック情報を作成し、ルーティング情報およびブロック情報を参照して、計算対象の対地間トラヒックの属するブロックにおけるルーティング情報であるブロック毎ルーティング情報を作成し、ブロック毎対地間トラヒック量の初期値を計算する。そして、リンクトラヒック情報を参照して、当該ブロックにおける計算対象の対地間トラヒックの対地間トラヒック量の初期値を計算する。ブロック毎ルーティング情報およびブロック毎対地間トラヒック量の初期値を用いて、当該対地間トラヒック量の推定値を計算し、この計算したブロック毎対地間トラヒック量の推定値のうち、計算対象の対地間トラヒックのトラヒック量の推定値を出力する。
【００１８】
このようにすることで、対地間トラヒック推定装置は、推定値を求めたい対地間トラヒックの属するブロックを対象に、ブロック毎対地間トラヒック量の推定値の計算を行うので、地間トラヒック量の推定値を高速に求めることができる。
【００１９】
本発明は、請求項１ないし請求項６のいずれか１項に記載の対地間トラヒック推定方法を、コンピュータである対地間トラヒック推定装置に実行させるためのプログラムである。
【００２０】
このようなプログラムによれば、一般的なコンピュータに請求項１ないし請求項６のいずれか１項に記載の対地間トラヒック推定方法を実行させることができる。
【発明の効果】
【００２１】
本発明によれば、ネットワークの対地間トラヒック量の推定値Ｔを求めるための計算時間を短縮することができる。
【図面の簡単な説明】
【００２２】
【図１】本実施の形態の対地間トラヒック推定装置の動作概要を示した図である。
【図２】本実施の形態で扱うネットワークの構成例を示した図である。
【図３】対地間トラヒック推定装置が作成するサブブロックおよびブロックの概要を説明した図である。
【図４】本実施の形態の対地間トラヒック推定装置の構成を示した図である。
【図５】図４のトポロジ情報および対地間トラヒック推定装置が作成するブロックを例示した図である。
【図６】図３のブロック＃３のトポロジ情報を例示した図である。
【図７】（ａ）は、図６のブロック＃３のリンクトラヒック情報を例示した図であり、（ｂ）は、図６のブロック＃３のルーティング情報を例示した図である。
【図８】（ａ）は、図６のブロック＃３の対地間トラヒック量の推定値を例示した図であり、（ｂ）は、（ａ）の対地間トラヒック量の推定値のうち、仮想対地間トラヒックのトラヒック量の推定値を除外した推定値を示した図である。
【図９】図４の対地間トラヒック推定装置の処理手順を示した図である。
【図１０】図９のＳ１〜Ｓ４の処理の詳細を示した図である。
【図１１】（ａ）は、トポロジ情報を例示した図であり、（ｂ）〜（ｄ）は、（ａ）のトポロジ情報をもとに作成したサブブロックを例示した図である。
【発明を実施するための形態】
【００２３】
以下、本発明を実施するための形態（以下、実施の形態とする）について説明する。まず、本実施の形態の対地間トラヒック推定装置の動作概要を、図１を用いて説明する。なお、以下の説明において、対地間トラヒックとは、その入力ノードから出力ノードまで、各リンクを経由して流れるトラヒック（フロー）のことをいう。対地間トラヒック推定装置は、ネットワークの対地間トラヒックそれぞれのトラヒック量の推定値を計算する。
【００２４】
まず、対地間トラヒック推定装置は、ネットワークのルーティング情報（各トラヒックがネットワークのどのリンクを経由するか示した情報）およびリンクトラヒック情報（ネットワーク内の各リンクのトラヒック量を示した情報）の入力を受け付ける。そして、このネットワークをいくつかのブロックに分割する。次に、入力されたルーティング情報およびリンクトラヒック情報をブロックごとに分割し、分割したブロック単位の対地間トラヒックの推定（対地間トラヒック量の推定値の計算処理）を行う。そして、このブロック単位の推定結果を統合し、全体の推定結果、すなわち、ネットワーク全体の対地間トラヒック量の推定結果を得る。
【００２５】
ここで、対地間トラヒック推定装置は、対地間トラヒック量の推定値を求めるとき、ブロック単位で処理する。つまり、対地間トラヒック推定装置は、ブロック単位で、前記した式（２）に準じて行列計算を行うが、このときに用いるルーティング行列のサイズは、ブロック毎のルーティング行列のサイズである。つまり、対地間トラヒック量の推定値の計算に用いる行列のサイズを小さくできるので、計算時間を短縮できる。また、対地間トラヒック推定装置は、ネットワークを複数のブロックに分割し、そのブロック毎に対地間トラヒック量の推定値の計算を行うので、処理の並列化を図り、計算時間を短縮できる。つまり、対地間トラヒック推定装置は、対地間トラヒック量の推定値の計算にあたり、ネットワークをブロック単位に分割して処理することで、（１）対地間トラヒック量の推定値の計算時間を短縮することができる。また、（２）ブロックごとに対地間トラヒック量の推定値の計算を行うので、処理を並列化でき、大幅に計算時間を短縮できる。
【００２６】
次に、図２を用いて、本実施の形態で扱うネットワークの構成例を説明する。ネットワークは、図２に例示するように１以上のノード（ノード番号１〜１５）と、そのノード間を接続するリンクとにより構成される。図２において、ノード８〜１５には、他のノードと接続されていないリンクがあるが、このようなリンクを外部リンクと呼ぶ。この外部リンクは、ネットワークへのトラヒックの入力ポイント、出力ポイントとなるリンクである。この外部リンクは、例えば、別のネットワークやユーザの端末装置に接続されている。対地間トラヒック（例えば、対地間トラヒックＡ，Ｂ）は、このような外部リンクを介して、ノードに入力され、リンクおよびノードを経由して、ネットワーク内の別のノード（または同じノード）から出力される。なお、ネットワークを構成するノードは、例えば、ＳＯＮＥＴ（Synchronous Optical NETwork）／ＳＤＨ（Synchronous Digital Hierarchy）クロスコネクトや、波長クロスコネクト等の伝送装置、ルータ、レイヤ２スイッチ等である。リンクは、ノード間に存在し、情報転送の媒体であり、例えば、光ファイバ等である。
【００２７】
ここで、図３を用いて、本実施の形態の対地間トラヒック推定装置が作成するブロックの概要を説明する。例えば、対地間トラヒック推定装置は、ルーティング情報等から、図３のネットワーク内の対地間トラヒックの入力ノードと出力ノードとを特定する。そして、対地間トラヒックの入力ノードまたは出力ノードを含む複数のサブブロック（サブブロック＃１〜＃４）を作成する。そして、このサブブロックから任意の２つのサブブロックを選択する。次に、この選択したサブブロックに入力ノード、出力ノードを持つ対地間トラヒック群を特定し、その対地間トラヒックそれぞれが経由するノード群でブロックを作成する。例えば、サブブロック＃１，＃４を選択し、このサブブロック＃１，＃４に入力ノード、出力ノードを持つ対地間トラヒックＢ，Ｃを特定する。そして、対地間トラヒックＣの経由ノード（ノード８，４，２，１，３，７，１５）、対地間トラヒックＢの経由ノード（ノード９，４，２，１，３，７，１４）をまとめたノード群（ノード８，４，９，２，１，３，７，１４，１５）から構成されるブロック＃３を作成する。また、同様に、対地間トラヒック推定装置は、サブブロック＃１，＃２を選択し、このサブブロック＃１，＃２に入力ノード、出力ノードを持つ対地間トラヒックの経由ノードから、ブロック＃１を作成する。さらに、サブブロック＃１，＃３を選択し、このサブブロック＃１，＃３に入力ノード、出力ノードを持つ対地間トラヒックの経由ノードから、ブロック＃２を作成する。対地間トラヒック推定装置は、以上のような処理をすべてのサブブロックの組み合わせついて実行して、ブロックを作成する。このようなブロックを作成することで、そのブロック内に対地間トラヒックの入力ノードから出力ノードまでの経路上の各ノードが属することになる。そして、対地間トラヒック推定装置が、そのブロック単位で対地間トラヒック量の推定値の計算を行うことで、対地間トラヒック量の推定値の計算を実行できる。なお、対地間トラヒック推定装置が、ネットワークを複数のブロックに分けて、対地間トラヒック量の推定値の計算を行うので、対地間トラヒック量の推定値の計算に用いる行列サイズを小さくできる。これにより、対地間トラヒック量の推定値の計算時間を短縮できる。
【００２８】
次に、図４を用いて、対地間トラヒック推定装置１００の構成を説明する。この対地間トラヒック推定装置１００は、ネットワークをいくつかのブロックに分け、そのブロックごとに対地間トラヒック量の推定値を計算する。このような対地間トラヒック推定装置１００は、入力部１１０と、サブブロック作成部１２０と、ブロック作成部１２１と、ブロック毎ルーティング情報作成部１２２と、ブロック毎リンクトラヒック情報作成部１２３と、初期値計算部１２４と、ブロック毎対地間トラヒック量推定部１２５と、ブロック統合部１２６と、トポロジ情報１３１と、ルーティング情報１３２と、リンクトラヒック情報１３３と、出力部１４０とを備える。入力部１１０は、トポロジ情報１３１、ルーティング情報１３２、リンクトラヒック情報１３３等の入力を受け付ける。また、出力部１４０は、ブロック統合部１２６による計算結果（各対地間トラヒック量の推定値）を出力する。
【００２９】
入力部１１０および出力部１４０は、入出力インタフェースから構成される。また、サブブロック作成部１２０と、ブロック作成部１２１と、ブロック毎ルーティング情報作成部１２２と、初期値計算部１２４と、ブロック毎対地間トラヒック量推定部１２５と、ブロック統合部１２６とは、この対地間トラヒック推定装置１００の備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、トポロジ情報１３１と、ルーティング情報１３２と、リンクトラヒック情報１３３は、入力部１１０経由で入力され、この対地間トラヒック推定装置１００の記憶部（図示省略）に記憶される。この記憶部は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、対地間トラヒック推定装置１００をプログラム実行処理により実現する場合、記憶部には、この対地間トラヒック推定装置１００の機能を実現するためのプログラムが格納される。また、この記憶部には、対地間トラヒック量の推定値の計算過程で作成される、サブブロック情報１３０、ブロック情報１３４、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６、ブロック毎対地間トラヒック量推定値１３７が記憶される。
【００３０】
トポロジ情報１３１は、ネットワークに存在するノードと、どのノード間のリンクが存在するかを示した情報である。このトポロジ情報１３１は、ＯＳＰＦにおいて利用されるリンクコストの値を含んでいてもよい。例えば、トポロジ情報１３１は、図５に例示するように、ネットワーク内に存在するノードと、そのノード間を接続するリンクの情報とが示される。なお、ここでは、ノード間を接続するリンクを方向別に示している。例えば、ノード２からノード１へのリンクは「リンク＃１」であり、ノード１からノード２のノードへのリンクは「リンク＃２」であることを示す。なお、図５に示す仮想対地間トラヒックについては後記する。
【００３１】
図４のルーティング情報１３２は、ネットワーク内の各対地間トラヒックの経路情報を、各対地間トラヒックの経由する一連のリンクの識別情報（リンク番号）で示した情報である。なお、このルーティング情報１３２は、例えば、ルーティングがＯＳＰＦにより行われる場合を想定して、シミュレーション等により求めてもよい。このルーティング情報１３２は、例えば、リンク数×フロー（対地間トラヒック）数の行列により表される。なお、このルーティング情報１３２は、各対地間トラヒックの経由するノードの識別情報で示してもよい。
【００３２】
リンクトラヒック情報１３３は、ネットワーク内のリンクごとに、そのリンクのリンクトラヒック量を示した情報である。
【００３３】
サブブロック作成部１２０は、ルーティング情報１３２を参照して、トポロジ情報１３１に示されるノード群のうち、対地間トラヒックの入力ノードまたは出力ノードを含むサブブロックを作成する（図３参照）。そして、サブブロック作成部１２０は、その作成したサブブロックに属するノードおよびそのノードに接続されるリンクを示したサブブロック情報１３０を作成し、記憶部に記憶する。このサブブロック作成部１２０によるサブブロックの作成処理の詳細は、具体例を用いて後記する。
【００３４】
ブロック作成部１２１は、サブブロック情報１３０に示されるサブブロック群から任意の２つのサブブロックを選択する。そして、ルーティング情報１３２を参照して、選択した２つのサブブロックのいずれか一方のノードを入力ノードとし、選択した２つのサブブロックのいずれか一方のノードを出力ノードとする対地間トラヒックを特定する。そして、ルーティング情報１３２を参照して、その特定した対地間トラヒックそれぞれの経由するノード群を選択し、この選択したノード群からなるブロックを構成する。例えば、ブロック作成部１２１は、図３のサブブロック＃１，＃４を選択したとき、ブロック＃３を構成する。このような処理を、サブブロック情報１３０に示されるすべてのサブブロックの組み合わせについて実行し、作成したブロックのノードおよびリンクをブロック情報１３４として記憶する。例えば、ブロック作成部１２１は、図３のブロック＃３を作成したとき、このブロック＃３の情報として、図６に例示するようなトポロジ情報をブロック情報１３４に記録する。
【００３５】
図４のブロック毎ルーティング情報作成部１２２は、ブロック情報１３４およびルーティング情報１３２を用いて、ルーティング情報１３２に示される対地間トラヒックそれぞれの、各ブロックにおけるルーティング情報（ブロック毎ルーティング情報１３５）を作成する。例えば、ブロック毎ルーティング情報１３５のうち、図６のブロック＃３のルーティング情報は、図７（ｂ）に例示するように、ブロック＃３において、各対地間トラヒックの経由する経路（リンク）が記載される。例えば、図７（ｂ）のルーティング情報において、対地間トラヒック番号１の対地間トラヒックは、リンク＃１７，＃１３，＃１６，＃２０を経由することを示す。このブロック毎ルーティング情報１３５は、ブロック毎対地間トラヒック量推定部１２５が、ブロック毎対地間トラヒック量推定値１３７を計算するときに参照される。なお、このブロック毎ルーティング情報１３５は、当該ブロックにおける仮想対地間トラヒック（図７（ｂ）の「＊」印の対地間トラヒック参照）のルーティング情報も含む。この仮想対地間トラヒックは、例えば、図５に示す、リンク＃１７からリンク＃８までのトラヒックのように、当該ブロック内に入力ノードまたは出力ノードのどちらか一方しかない対地間トラヒックである。ブロック毎ルーティング情報作成部１２２が、ブロック毎ルーティング情報１３５を作成するとき、このような仮想対地間トラヒックのルーティング情報も含めることで、ブロック毎対地間トラヒック量推定部１２５は、ブロック内に入力ノードまたは出力ノードのどちらか一方しかない対地間トラヒックのトラヒック量も考慮して、ブロック毎対地間トラヒック量推定値１３７を計算できる。つまり、精度の高いブロック毎対地間トラヒック量推定値１３７を得ることができる。
【００３６】
ブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３をブロック情報１３４に示されるブロックごとに切り出して、ブロック毎リンクトラヒック情報１３６を作成する。このブロック毎リンクトラヒック情報１３６には、図７（ａ）に示すようなリンクトラヒック情報が記憶される。図７（ａ）は、図６のブロック＃３のリンクトラヒック情報であり、リンク番号「１」のリンクトラヒック量は「Ｘ１」であることを示す。このブロック毎リンクトラヒック情報１３６は、ブロック毎対地間トラヒック量推定部１２５が、ブロック毎対地間トラヒック量推定値１３７を計算するときに参照される。また、初期値計算部１２４が、当該ブロックの交流トラヒック量の推定値の初期値を計算するときに参照される。
【００３７】
図４の初期値計算部１２４は、ブロック毎リンクトラヒック情報１３６を参照して、Ｇｒａｖｉｔｙ法等により、ブロックごとに、そのブロックの対地間トラヒック量の推定値の初期値を計算する。計算した初期値は、記憶部の所定領域に記憶しておく。
【００３８】
ブロック毎対地間トラヒック量推定部１２５は、ブロック毎リンクトラヒック情報１３６、ブロック毎ルーティング情報１３５およびブロックごとの対地間トラヒック量の初期値を用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により、ブロックそれぞれの対地間トラヒック量の推定値を計算する。そして、その計算した推定値を、ブロック毎対地間トラヒック量推定値１３７として記憶部の所定領域に記憶する。例えば、ブロック毎対地間トラヒック量推定値１３７には、図８（ａ）に示すようなブロック＃３の対地間トラヒック量の推定値が記憶される。なお、この対地間トラヒック量の推定値には、前記した仮想対地間トラヒックのトラヒック量の推定値（図８（ａ）の「＊」印の対地間トラヒックの推定値参照）も含まれる。
【００３９】
ブロック統合部１２６は、ブロック毎対地間トラヒック量推定値１３７に示される対地間トラヒック量の推定値を出力部１４０経由で出力する。なお、前記したとおり、ブロック毎対地間トラヒック量推定値１３７には、仮想対地間トラヒックのトラヒック量の推定値が含まれる。よって、ブロック統合部１２６は、このブロック毎対地間トラヒック量推定値１３７のうち、仮想対地間トラヒック以外の対地間トラヒック量の推定値を出力する。例えば、ブロック＃３に関して言えば、ブロック統合部１２６は、図８（ｂ）に示すように、図８（ａ）の「＊」印の仮想対地間トラヒック以外の対地間トラヒック量の推定値を出力する。
【００４０】
＜処理手順＞
次に、図４を参照しつつ、図９を用いて、対地間トラヒック推定装置１００の処理手順の概要を説明する。まず、対地間トラヒック推定装置１００は事前準備として、入力部１１０経由で、トポロジ情報１３１、ルーティング情報１３２、リンクトラヒック情報１３３の入力を受け付け、記憶部に記憶しておくものとする。
【００４１】
そして、入力部１１０からの指示入力に基づき、サブブロック作成部１２０は、トポロジ情報１３１に示されるネットワーク内の各ノード群からサブブロックを作成する（Ｓ１：サブブロック作成）。そして、作成した各サブブロックのノードおよびリンクの識別情報等をサブブロック情報１３０に記録する。次に、ブロック作成部１２１は、このサブブロック情報１３０に記録される任意の２つのサブブロックすべての組み合わせについて、ブロックの作成処理を実行する（Ｓ２：ブロック作成）。そして、作成したブロックそれぞれのノードおよびリンクの識別情報等をブロック情報１３４に記憶する。
【００４２】
次に、ブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３をブロックごとに切り出して、ブロック毎リンクトラヒック情報１３６を作成する（Ｓ３：ブロック毎リンクトラヒック情報作成）。また、ブロック毎ルーティング情報作成部１２２は、ブロック情報１３４およびルーティング情報１３２を用いて、ブロックごとのルーティング情報を示したブロック毎ルーティング情報１３５を作成する（Ｓ４：ブロック毎ルーティング情報作成）。
【００４３】
そして、初期値計算部１２４は、ブロック毎リンクトラヒック情報１３６を参照して、Ｇｒａｖｉｔｙ法等によりブロックごとに、当該ブロックにおける対地間トラヒック量の推定値の初期値を計算する（Ｓ５：初期値計算）。計算した初期値を記憶部に記憶する。
【００４４】
次に、ブロック毎対地間トラヒック量推定部１２５は、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６およびブロックごとの対地間トラヒック量の推定値の初期値を用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により、ブロックそれぞれの対地間トラヒック量の推定値を計算する（Ｓ６：ブロック毎対地間トラヒック量推定）。そして、その計算結果を、ブロック毎対地間トラヒック量推定値１３７として記憶部の所定領域に記憶する。
【００４５】
次に、ブロック統合部１２６は、ブロック毎対地間トラヒック量推定値１３７に示される各対地間トラヒックの推定値を出力部１４０経由で出力する（Ｓ７：対地間トラヒック推定値出力）。ここで、ブロック毎対地間トラヒック量推定値１３７には、仮想対地間トラヒックのトラヒック量の推定値が含まれる。よって、ブロック統合部１２６は、このブロック毎対地間トラヒック量推定値１３７のうち、仮想対地間トラヒックのトラヒック量の推定値以外の推定値を出力する。
【００４６】
このように、対地間トラヒック推定装置１００は、ネットワークのブロックごとの対地間トラヒック量の推定値を計算する。よって、対地間トラヒック量の推定値の計算に用いる行列サイズを小さくできるので、対地間トラヒック量の推定値の計算時間を従来よりも短縮できる。
【００４７】
次に、図１０を用いて、図９のＳ１〜Ｓ４の処理の詳細を、具体例を交えながら説明する。なお、図１０のＳ１１の処理は、図９のＳ１の処理に相当し、図１０のＳ１２〜Ｓ１７は、図９のＳ２の処理に相当する。また、図１０のＳ１８の処理は、図９のＳ３の処理に相当し、図１０のＳ１９の処理は、図９のＳ４の処理に相当する。
【００４８】
図４のサブブロック作成部１２０がサブブロック作成処理を実行し、サブブロック情報１３０を作成した後（Ｓ１１）、ブロック作成部１２１は、サブブロック情報１３０の中から任意の２つのサブブロックを選択する（Ｓ１２）。
【００４９】
次に、ブロック作成部１２１は、ブロックを構成するノードの集合Ｎを定義し、その初期値を空とする（Ｓ１３）。そして、ブロック作成部１２１は、以下のようにしてブロックに属するノードを決定する。すなわち、ブロック作成部１２１は、Ｓ１２で選択した２つのサブブロックのいずれかのサブブロックに属するノードに外部リンクを介して入力し、この選択した２つのサブブロックのいずれかのサブブロックに属する別のノードから外部リンクを介し出力する１つの対地間トラヒックを、ルーティング情報１３２を参照して、選択する（Ｓ１４）。そして、選択した対地間トラヒックが経由するノードの集合Ｍを選択する（Ｓ１５）。
【００５０】
例えば、サブブロック作成部１２０が、Ｓ１２で、図３のサブブロック＃１とサブブロック＃４とを選択した場合、ルーティング情報１３２を参照して、以下の（１）〜（１２）に示す対地間トラヒックを選択する。
（１）ノード８に外部リンクを介し入力し、ノード９から外部リンクを介し出力する対地間トラヒック
（２）ノード８に外部リンクを介し入力し、ノード１４から外部リンクを介し出力する対地間トラヒック
（３）ノード８に外部リンクを介し入力し、ノード１５から外部リンクを介し出力する対地間トラヒック
（４）ノード９に外部リンクを介し入力し、ノード８から外部リンクを介し出力する対地間トラヒック
（５）ノード９に外部リンクを介し入力し、ノード１４から外部リンクを介し出力する対地間トラヒック
（６）ノード９に外部リンクを介し入力し、ノード１５から外部リンクを介し出力する対地間トラヒック
（７）ノード１４に外部リンクを介し入力し、ノード８から外部リンクを介し出力する対地間トラヒック
（８）ノード１４に外部リンクを介し入力し、ノード９から外部リンクを介し出力する対地間トラヒック
（９）ノード１４に外部リンクを介し入力し、ノード１５から外部リンクを介し出力する対地間トラヒック
（１０）ノード１５に外部リンクを介し入力し、ノード８から外部リンクを介し出力する対地間トラヒック
（１１）ノード１５に外部リンクを介し入力し、ノード９から外部リンクを介し出力する対地間トラヒック
（１２）ノード１５に外部リンクを介し入力し、ノード１４から外部リンクを介し出力する対地間トラヒック
【００５１】
そして、図４のブロック作成部１２１は、選択した対地間トラヒックが経由するノードの集合Ｍを選択する（Ｓ１５）。例えば、ブロック作成部１２１は、前記した（１）〜（１２）に示す対地間トラヒックそれぞれの経由するノードの集合Ｍとして、図３に示すノード群から、以下のノードを選択する。
（１）の対地間トラヒックが経由する集合Ｍ：ノード８，４，９
（２）の対地間トラヒックが経由する集合Ｍ：ノード８，４，２，１，３，７，１４
（３）の対地間トラヒックが経由する集合Ｍ：ノード８，４，２，１，３，７，１５
（４）の対地間トラヒックが経由する集合Ｍ：ノード９，４，８
（５）の対地間トラヒックが経由する集合Ｍ：ノード９，４，２，１，３，７，１４
（６）の対地間トラヒックが経由する集合Ｍ：ノード９，４，２，１，３，７，１５
（７）の対地間トラヒックが経由する集合Ｍ：ノード１４，７，３，１，２，４，８
（８）の対地間トラヒックが経由する集合Ｍ：ノード１４，７，３，１，２，４，９
（９）の対地間トラヒックが経由する集合Ｍ：ノード１４，７，１５
（１０）の対地間トラヒックが経由する集合Ｍ：ノード１５，７，３，１，２，４，８
（１１）の対地間トラヒックが経由する集合Ｍ：ノード１５，７，３，１，２，４，９
（１２）の対地間トラヒックが経由する集合Ｍ：ノード１５，７，１４
【００５２】
そして、図４のブロック作成部１２１は、ノードの集合Ｍとノードの集合Ｎとの和をとり、これを新たなノードの集合Ｎとする（Ｓ１６）。例えば、ブロック作成部１２１は、前記した（１）〜（１２）の対地間トラヒックが経由する集合Ｍと、ノードの集合Ｎ（初期値は空）との和をとり、集合Ｎ：ノード１，２，３，４，７，８，９，１４，１５を得る。
【００５３】
次に、図４のブロック作成部１２１は、まだ選択していない対地間トラヒックがあれば（Ｓ１７のＮｏ）、Ｓ１４へ戻る。一方、該当するすべての対地間トラヒックを選択済みであれば（Ｓ１７のＹｅｓ）、対地間トラヒック推定装置１００は、以下のようにして各ブロックのリンクトラヒック情報、ルーティング情報を作成する。すなわち、ブロック毎リンクトラヒック情報作成部１２３は、ノードの集合Ｎに接続されるリンクの集合（ブロック）について、リンクトラヒック情報を作成する（Ｓ１８）。つまり、リンクトラヒック情報１３３を参照して、そのブロックごとのリンクトラヒック情報を作成し、その情報をブロック毎リンクトラヒック情報１３６に記憶する。
【００５４】
また、ブロック毎ルーティング情報作成部１２２は、ルーティング情報１３２を参照して、ブロックごとのルーティング情報を作成する（Ｓ１９）。ここで、ブロック毎ルーティング情報作成部１２２は、（１）ブロックに属するノードに外部リンクを介し入力し、そのブロックに属するノードから外部リンクを介し出力する対地間トラヒックは、そのまま経路を作成する。一方、（２）前記したブロックに属するノードに外部リンクを介し入力し、ブロックに属さないノードから外部リンクを介し出力する対地間トラヒック、および、ブロックに属さないノードに外部リンクを介し入力し、ブロックに属するノードから外部リンクを介し出力する対地間トラヒックについて、この対地間トラヒックを仮想対地間トラヒックとして定義し、経路を作成する。つまり、図７（ｂ）に示すブロック＃３のルーティング情報に示す地間トラヒック番号：１，４，５，６，９，１０，２１，２２，２５，２６，２７，３０の対地間トラヒックついては、そのまま経路を作成し、対地間トラヒック番号：１，４，５，６，９，１０，２１，２２，２５，２６，２７，３０以外の対地間トラヒック（図７（ｂ）の「＊」の対地間トラヒック）については、仮想対地間トラヒックとして定義して経路を作成する。
【００５５】
そして、ブロック作成部１２１は、ブロック情報１３４におけるサブブロックすべての組み合わせを選択済みであれば（Ｓ２０のＹｅｓ）、ルーティング情報の作成処理が終了したことになるので、図９のＳ５の初期値計算処理を実行する。一方、まだ選択していないサブブロックの組み合わせがあれば（Ｓ２０のＮｏ）、Ｓ１２へ戻る。
【００５６】
このようにすることで、対地間トラヒック推定装置１００はブロックを作成し、そのブロックのブロック毎リンクトラヒック情報１３６およびブロック毎ルーティング情報１３５を作成することができる。
【００５７】
以上説明した対地間トラヒック推定装置１００によれば、ネットワークの各ノードをブロックに分け、そのブロックごとに対地間トラヒック量の推定値を計算するので、推定値計算に用いる行列サイズを小さくすることができる。これにより、ネットワーク内の各対地間トラヒックの推定値の計算時間を短縮することができる。
【００５８】
なお、前記した実施の形態において、ブロック毎ルーティング情報作成部１２２は、処理の簡略化のため、以下のようにしてブロック毎ルーティング情報１３５を作成してもよい。例えば、ブロック毎ルーティング情報作成部１２２は、ブロックに属するリンク群から、当該ブロックの外部のノードに接続する任意の２つのリンクを選択する。そして、その２つのリンクを始終点とする対地間トラヒックを定義する。そして、トポロジ情報１３１に示される各リンクのリンクコストに基づき、ＯＳＰＦ等のシミュレーションを行うことにより、そのブロックにおける対地間トラヒックそれぞれの経路を計算し、その計算結果を当該ブロックのルーティング情報としてブロック毎ルーティング情報１３５に記憶する。
【００５９】
また、対地間トラヒックの経路が、ＯＳＰＦ等により、入力ノードから出力ノードまでの最短経路が選択される場合、ブロック作成部１２１は、以下のようしてブロックを作成してもよい。例えば、ブロック作成部１２１は、Ｓ１２で選択した２つのサブブロックに属するノードの集合と、その選択した２つのサブブロックの一方のサブブロックのサブブロック境界ノードと、他方のサブブロックのサブブロック境界ノードとの間の最短経路のノードの集合とをブロックを構成するノードの集合Ｎとする。この場合、ブロック作成部１２１が、図３のサブブロック＃１，＃４を選択したとき、サブブロック境界ノードは、ノード４，７である。よって、ブロック作成部１２１は、このノード４，７間の最短経路のノードの集合（ノード２，１，３）と、サブブロック＃１のノード（ノード４，８，９）と、サブブロック＃４のノード（ノード７，１４，１５）と合わせた集合（ノード４，８，９，７，１４，１５，２，１，３）を、ブロックを構成するノード集合Ｎとして選択する。
【００６０】
また、ブロック毎対地間トラヒック量推定部１２５が、ブロックごとに対地間トラヒックそれぞれのトラヒック量の推定値を計算するとき、複数のブロックで同じ対地間トラヒックのトラヒック量の推定値が得られることがある。このような場合、それぞれのブロックにおける当該対地間トラヒックの推定値の平均値を求め、その平均値をその対地間トラヒックのトラヒック量の推定値としてもよい。例えば、図３においてブロック＃１，２，３の対地間トラヒック量の推定結果として、リンク＃１７を介してノード８に入力しリンク＃２０を介してノード９から出力する対地間トラヒックのトラヒック量の推定値Ｔ（１７，２０）が得られる。このような場合、このブロック＃１〜＃３それぞれにおける当該対地間トラヒックのトラヒック量の推定値の平均値、つまり、｛Ｔ１（１７，２０）＋Ｔ２（１７，２０）＋Ｔ３（１７，２０）｝／３を、ブロック毎対地間トラヒック量推定値１３７におけるＴ（１７，２０）の値として記録するようにしてもよい。
【００６１】
また、前記した実施の形態において、対地間トラヒック推定装置１００の初期値計算部１２４が、ブロック毎の対地間トラヒック量の推定値の初期値を計算するとき、以下のようにして計算してもよい。すなわち、初期値計算部１２４は、リンクトラヒック情報１３３を参照して、ネットワーク全体の対地間トラヒック量の推定値の初期値Ｔｇを計算する。そして、初期値計算部１２４は、ブロックごとに、そのブロックを経由する対地間トラヒックに関する初期値を加算して、そのブロックの対地間トラヒック量の推定値の初期値を計算する。例えば、初期値計算部１２４は、図５のブロック＃３におけるリンク＃１７を介しノード８に入力しリンク＃８を介しノード２から出力する対地間トラヒックのトラヒック量の初期値Ｔｇ３（１７，８）は、Ｔｇ（１７，２６）＋Ｔｇ（１７，２８）となる。このように、初期値計算部１２４は、ネットワーク全体の対地間トラヒック量の推定値の初期値をもとに計算された初期値を用いて、ブロックごとの対地間トラヒック量の推定値を計算するので、ブロックごとの対地間トラヒック量の推定値の計算精度を向上できる。
【００６２】
なお、前記した実施の形態において、対地間トラヒック推定装置１００のサブブロック作成部１２０は、以下のようにしてサブブロックを作成するようにしてもよい。
【００６３】
例えば、トポロジ情報１３１として、図１１（ａ）に示すトポロジが与えられたとき、ブロック作成部１２１は、図１１（ｂ）に示すように、単に、各ノードがいずれかのサブブロックに属するように分割してもよい。また、図１１（ｃ）に示すように、同じサブブロックに属する任意の２つのノードが、同じサブブロックのノードを経由して到達可能であるようにしてもよい。ここで、ブロック作成部１２１が、図１１（ｃ）のように同じサブブロックに属する任意の２つのノードについて、同じサブブロックのノードを経由して到達可能であるようなサブブロックを作成しておけば、これらのサブブロックに入出力する対地間トラヒックの経路が、同じサブブロック内のノードのみとする可能性を向上できる。このようにサブブロックに入出力する対地間トラヒックの経路が、同じサブブロック内のノードのみであれば、このサブブロックをもとにブロックを作成したとき、そのブロック内のノード数が多くなりづらくなる。このようにブロック内のノード数が多くならなければ、ブロック毎対地間トラヒック量推定部１２５が、ブロックごとの対地間トラヒック量の推定値を計算するときの計算量を低減できる。
【００６４】
例えば、図１１（ｂ）のサブブロック群と、図１１（ｃ）のサブブロック群とを比べると、同じサブブロック内での経路到達性を確保している図１１（ｃ）の方が、ブロックを作成したときにおけるブロック内のノード数を少なくできる可能性が高くなる。例えば、図１１（ｂ）でサブブロック＃１，＃４を選択して、ブロックを作成すると、ブロックを構成するノード群は、ノード１，３，９，４，６，８，１１，１２，１３，１４となる可能性がある。一方、図１１（ｃ）でサブブロック＃１，＃４を選択して、ブロックを作成すると、サブブロック＃１のノード３と、サブブロック＃４のノード１１とを接続するノード群として、ノード４，６が選択されれば、ブロックを構成するノード群は、ノード１，２，３，４，６，１１，１２，１３，１４となる。つまり、図１１（ｃ）の方がブロック内のノード数を少なくできる。
【００６５】
さらに、サブブロック作成部１２０は、ルーティング情報１３２を参照して、当該サブブロックに属するノードに入力し、当該サブブロックに属するノードから出力する対地間トラヒックが、当該サブブロックに属するノードのみを経由するようなサブブロックを作成してもよい。例えば、サブブロック作成部１２０が、図１１（ｄ）に示すようなサブブロックを作成すると、サブブロック＃１，＃２を選択して作成されるブロック内のノード数は、図１１（ｃ）の場合と同じであるが、サブブロック＃２，＃３を選択して作成されるブロック内のノード数は、図１１（ｃ）の場合と比べて少なくなる。よって、このようにブロック内のノード数を低減できれば、ブロック毎対地間トラヒック量推定部１２５が、ブロックごとの対地間トラヒック量の推定値を計算するときの計算量を低減できる。
【００６６】
なお、前記した実施の形態において、対地間トラヒック推定装置１００は、ネットワークにおける各対地間トラヒックのトラヒック量の推定値を計算することとしたが、所定の対地間トラヒックのトラヒック量の推定値のみを計算するようにしてもよい。この場合、対地間トラヒック推定装置１００は、この推定値の計算対象となる対地間トラヒックを指定する情報、例えば、計算対象の対地間トラヒックの入力ノードおよび出力ノードの指示入力を受け付ける。そして、ブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３を参照して、計算対象の対地間トラヒックの入力ノードと出力ノードを含むブロックのリンクトラヒック情報を作成する。また、ブロック毎ルーティング情報作成部１２２は、ルーティング情報１３２を参照して、計算対象の対地間トラヒックの属するブロックにおけるルーティング情報を作成する。さらに、初期値計算部１２４は、計算対象の対地間トラヒックの属するブロックにおけるリンクトラヒック情報を参照して、当該対地間トラヒックのトラヒック量の推定値の初期値を計算する。そして、ブロック毎対地間トラヒック量推定部１２５は、計算対象の対地間トラヒックの属するブロックにおけるリンクトラヒック情報、ルーティング情報および初期値を参照して、計算対象の対地間トラヒックのトラヒック量の推定値を計算する。このようにすることで、対地間トラヒック推定装置１００は、所定の対地間トラヒックのトラヒック量の推定値を高速に得ることができる。
【００６７】
なお、前記した実施の形態において初期値計算部１２４は、ブロックごとの対地間トラヒック量の推定値の初期値を計算するとき、ブロック毎リンクトラヒック情報１３６と、ブロック毎ルーティング情報１３５とを用いて計算してもよい。ブロック毎対地間トラヒック量推定部１２５は、このようにして計算された初期値を用いることで、ブロックごとの対地間トラヒック量の推定値の推定精度を向上させることができる。
【符号の説明】
【００６８】
１００  対地間トラヒック推定装置
１１０  入力部
１２０  サブブロック作成部
１２１  ブロック作成部
１２２  ブロック毎ルーティング情報作成部
１２３  ブロック毎リンクトラヒック情報作成部
１２４  初期値計算部
１２５  ブロック毎対地間トラヒック量推定部
１２６  ブロック統合部
１３０  サブブロック情報
１３１  トポロジ情報
１３２  ルーティング情報
１３３  リンクトラヒック情報
１３４  ブロック情報
１３５  ブロック毎ルーティング情報
１３６  ブロック毎リンクトラヒック情報
１３７  ブロック毎対地間トラヒック量推定値
１４０  出力部
【図１】
2010283702.tif 000003
【図２】
2010283702.tif 000004
【図３】
2010283702.tif 000005
【図４】
2010283702.tif 000006
【図５】
2010283702.tif 000007
【図６】
2010283702.tif 000008
【図７】
2010283702.tif 000009
【図８】
2010283702.tif 000010
【図９】
2010283702.tif 000011
【図１０】
2010283702.tif 000012
【図１１】
2010283702.tif 000013