(57)【特許請求の範囲】
【請求項１】
ネットワークを構成するブロックごとに、当該ブロックの対地間トラヒックのトラヒック量推定値を計算し、前記計算したブロックごとの対地間トラヒックのトラヒック量推定値に基づき、前記ネットワークの対地間トラヒックのトラヒック量を推定する対地間トラヒック推定装置が、
前記ネットワークの対地間トラヒックのトラヒック量のうち、既知値の入力を受け付けるステップと、
前記入力された既知値が０である場合、
前記既知値の対地間トラヒックの経由するブロックのうち、当該対地間トラヒックの始点ノードであるノードＡが属するブロックをＺ１、当該対地間トラヒックの終点ノードであるノードＣが属するブロックをＺｎ、当該対地間トラヒックの中継ブロックをＺｉ（ｉ＝２，…，ｎ−１）、前記ブロックＺｎにおけるブロックＺｎ−１とのブロック境界ノードをノードＢとしたとき、
記憶部に記憶された、前記ブロックごとの対地間トラヒックのトラヒック量推定値を示すブロック毎対地間トラヒック量情報における前記ブロックＺｎの対地間トラヒックのトラヒック量推定値のうち、前記ノードＢから前記ノードＣへのトラヒック量推定値を０に補正するステップと、
前記ノードＡから前記ノードＣへの対地間トラヒックについて、ブロックＺｉにおいて、当該ブロックＺｉのブロック境界ノードであるノードＤに入力し、当該ブロックＺｉのブロック境界ノードであるノードＥから出力する場合において、前記ブロック毎対地間トラヒック量情報に示される当該ブロックＺｉにおけるノードＤからノードＥへの対地間トラヒックが、ブロックＺｉ＋１において、当該ブロックＺｉのブロック境界ノードであるノードＦに入力されるとしたとき、前記補正後のブロック毎対地間トラヒック量情報を参照して、当該ブロックＺｉにおける前記ノードＤから前記ノードＥへのトラヒック量推定値を、以下の式（４）により補正する処理を、当該対地間トラヒックの経由するブロックＺｎ−１からブロックＺ１まで繰り返すステップと、
当該ブロックＺｉにおける前記ノードＤから前記ノードＥへの対地間トラヒック量推定値×（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒックそれぞれのトラヒック量推定値の補正後の値の合計）／（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒックそれぞれのトラヒック量推定値の補正前の値の合計）…式（４）
前記補正したブロック毎対地間トラヒック量情報に基づき、前記既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれに対し、当該対地間トラヒックが経由するブロックＺｉにおけるトラヒック量推定値に（当該ブロックＺｉからブロックＺｉ＋１に出力されるトラヒック量推定値）／（当該ブロックＺｉから他のブロックに出力されるトラヒック量推定値の合計値）を掛ける処理をブロックＺ１からブロックＺｎまで繰り返すことで、前記既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれのトラヒック量推定値を計算するステップと、
前記補正前のブロック毎対地間トラヒック量情報から、前記計算した対地間トラヒックそれぞれのトラヒック量推定値を減算し、前記減算後のブロック毎対地間トラヒック量情報に基づき、前記既知値の対地間トラヒックと始点ノードが異なる対地間トラヒックそれぞれのトラヒック量推定値を計算するステップと、
前記計算した対地間トラヒックそれぞれのトラヒック量推定値を出力するステップとを実行することを特徴とすることを特徴とする対地間トラヒック推定方法。
【請求項２】
前記対地間トラヒック推定装置は、
ネットワークのトポロジ情報、前記ネットワークの各リンクのリンクトラヒック量を示すリンクトラヒック情報および前記対地間トラヒックごとの経由リンクを示すルーティング情報とを記憶する記憶部を備えており、
前記入力された既知値が０以外の場合、
前記リンクトラヒック情報における当該対地間トラヒックの経由する各リンクのトラヒック量を、前記入力された既知値の分、減算するステップと、
前記トポロジ情報に示されるノード群を複数のブロックに分割するステップと、
前記分割したブロックに属するノードおよびそのノードに接続されるリンクの識別情報を示すブロック間接続情報と、前記トラヒック量減算後のリンクトラヒック情報とを用いて前記ブロックごとのリンクトラヒック量推定値を示すブロック毎リンクトラヒック情報を作成するステップと、
前記ブロック間接続情報と、前記ルーティング情報とを用いて、前記ブロックごとのルーティング情報であるブロック毎ルーティング情報を作成するステップと、
前記ブロック毎リンクトラヒック情報と、前記ブロック毎ルーティング情報とを用いて、前記ブロックごとの対地間トラヒックのトラヒック量推定値を計算し、前記計算したトラヒック量推定値を前記ブロック毎対地間トラヒック量情報に記憶するステップとをさらに実行した後、
前記作成したブロック毎対地間トラヒック量情報を用いて、
前記ノードＢから前記ノードＣへのトラヒック量推定値を０に補正するステップ以降の処理を実行することを特徴とする請求項１に記載の対地間トラヒック推定方法。
【請求項３】
請求項１または請求項２に記載の対地間トラヒック推定方法を、コンピュータである対地間トラヒック推定装置に実行させるためのプログラム。
【請求項４】
ネットワークを構成するブロックごとに、当該ブロックの対地間トラヒックのトラヒック量推定値を計算し、前記計算したブロックごとの対地間トラヒックのトラヒック量推定値を統合して、前記ネットワークの対地間トラヒックのトラヒック量を推定する対地間トラヒック推定装置であって、
前記ネットワークの対地間トラヒックのトラヒック量のうち、既知値の入力を受け付ける入力部と、
前記入力された既知値が０である場合、
前記既知値の対地間トラヒックの経由するブロックのうち、当該対地間トラヒックの始点ノードであるノードＡが属するブロックをＺ１、当該対地間トラヒックの終点ノードであるノードＣが属するブロックをＺｎ、当該対地間トラヒックの中継ブロックをＺｉ（ｉ＝２，…，ｎ−１）、前記ブロックＺｎにおけるブロックＺｎ−１とのブロック境界ノードをノードＢとしたとき、記憶部に記憶された、前記ブロックごとの対地間トラヒックのトラヒック量推定値を示すブロック毎対地間トラヒック量情報における前記ブロックＺｎの対地間トラヒックのトラヒック量推定値のうち、前記ノードＢから前記ノードＣへのトラヒック量推定値を０に補正し、前記ノードＡから前記ノードＣへの対地間トラヒックについて、ブロックＺｉにおいて、当該ブロックＺｉのブロック境界ノードであるノードＤに入力し、当該ブロックＺｉのブロック境界ノードであるノードＥから出力する場合において、前記ブロック毎対地間トラヒック量情報に示される当該ブロックＺｉにおけるノードＤからノードＥへの対地間トラヒックが、ブロックＺｉ＋１において、当該ブロックＺｉのブロック境界ノードであるノードＦに入力されるとしたとき、前記補正後のブロック毎対地間トラヒック量情報を参照して、当該ブロックＺｉにおける前記ノードＤから前記ノードＥへのトラヒック量推定値を、以下の式（４）により補正する処理を、当該対地間トラヒックの経由するブロックＺｎ−１からブロックＺ１まで繰り返す補正部と、
当該ブロックＺｉにおける前記ノードＤから前記ノードＥへの対地間トラヒック量推定値×（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒックそれぞれのトラヒック量推定値の補正後の値の合計）／（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒックそれぞれのトラヒック量推定値の補正前の値の合計）…式（４）
前記補正したブロック毎対地間トラヒック量情報に基づき、前記既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれに対し、当該対地間トラヒックが経由するブロックＺｉにおけるトラヒック量推定値に（当該ブロックＺｉからブロックＺｉ＋１に出力されるトラヒック量推定値）／（当該ブロックＺｉから他のブロックに出力されるトラヒック量推定値の合計値）を掛ける処理をブロックＺ１からブロックＺｎまで繰り返すことで、前記既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれのトラヒック量推定値を計算し、前記補正前のブロック毎対地間トラヒック量情報から、前記計算した対地間トラヒックそれぞれのトラヒック量推定値を減算し、前記減算後のブロック毎対地間トラヒック量情報に基づき、前記既知値の対地間トラヒックと始点ノードが異なる対地間トラヒックそれぞれのトラヒック量推定値を計算するブロック統合部と、
前記計算した対地間トラヒックそれぞれのトラヒック量推定値を出力する出力部とを備えることを特徴とする対地間トラヒック推定装置。
【請求項５】
前記対地間トラヒック推定装置は、
ネットワークのトポロジ情報、前記ネットワークの各リンクのリンクトラヒック量を示すリンクトラヒック情報および前記対地間トラヒックごとの経由リンクを示すルーティング情報とを記憶する前記記憶部を備えており、
前記補正部は、
前記入力された既知値が０以外の場合、前記リンクトラヒック情報における当該対地間トラヒックの経由する各リンクのトラヒック量を、前記入力された既知値の分、減算し、
前記対地間トラヒック推定装置は、
前記トポロジ情報に示されるノード群を複数のブロックに分割し、前記分割したブロックに属するノードおよびそのノードに接続されるリンクの識別情報を示すブロック間接続情報を作成するブロック分割部と、
前記ブロック間接続情報と、前記トラヒック量減算後のリンクトラヒック情報とを用いて前記ブロックごとのリンクトラヒック量推定値を示すブロック毎リンクトラヒック情報を作成するブロック毎リンクトラヒック情報作成部と、
前記ブロック間接続情報と、前記ルーティング情報とを用いて、前記ブロックごとのルーティング情報であるブロック毎ルーティング情報を作成するブロック毎ルーティング情報作成部と、
前記ブロック毎リンクトラヒック情報と、前記ブロック毎ルーティング情報とを用いて、前記ブロックごとの対地間トラヒックのトラヒック量推定値を計算し、前記計算したトラヒック量推定値を前記ブロック毎対地間トラヒック量情報に記憶するブロック毎対地間トラヒック量推定部とをさらに備えることを特徴とする請求項４に記載の対地間トラヒック推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク内の各リンクのトラヒック情報を示すリンクトラヒック情報と、各対地間トラヒックがどのリンクを経由するかを示すルーティング情報を用い、対地間トラヒックのトラヒック量の推定値を計算する技術に関する。
【背景技術】
【０００２】
従来、ネットワーク内のリンクトラヒック情報と、ルーティング情報とを用い、対地間トラヒックのトラヒック量の推定値（以下、適宜、対地間トラヒック量推定値と呼ぶ）を計算する方法としては、Ｔｏｍｏ−Ｇｒａｖｉｔｙ法がある（非特許文献１参照）。
【０００３】
この方法では、以下のようにして対地間トラヒック量推定値を計算している。Ｘをリンクトラヒック情報のベクトル、Ｔを対地間トラヒック情報のベクトル、Ａを各対地間トラヒックがどのリンクを経由するかを示すルーティング情報の行列とすると、以下の式（１）が成り立つ。
Ｘ＝Ａ＊Ｔ…式（１）
ここで、ＸとＡを入力として与えることで、Ｔが求められるように思われるが、一般的にＴの要素数（対地間トラヒック数）は、Ｘの要素数（リンク数）より多いため、解が一意には求まらない。そこで、Ｔの初期値としてＴｇを求め、Ｔを以下の式（２）
Ｔ＝ｐｉｎｖ（Ａ）（Ｘ−Ａ＊Ｔｇ）＋Ｔｇ…式（２）
とすることで、推定値を求める。ここで、ｐｉｎｖ（Ａ）とは、Ａの擬似逆行列を意味する。
【０００４】
さらに、上記技術を大規模網で適用できるように、ネットワークのノードを複数のブロックに分割し、そのブロックごとに、そのブロックの対地間トラヒック量推定値を求めることで、対地間トラヒック高速化を行う方法がある（特許文献１参照）。この方法では、図２のブロック＃１〜＃５のように、ネットワークのブロック分割を行った後、図１に示すようにブロックごとに対地間トラヒック推定を行う。そして、ブロック統合を行うことで、全体の推定結果（全対地間トラヒック量推定値）を求める。この方法によれば、Ｔの計算に用いる行列のサイズを小さくできるので、対地間トラヒック量推定値の計算にかかる時間を低減できる。以下の説明において、Ｔ（ｘ，ｙ）は、対地間トラヒック量推定値を示し、ｘは、対地間トラヒックの入力リンク番号を示し、ｙは、対地間トラヒックの出力リンク番号を示す。なお、ＴＮ（ｘ，ｙ）は、ブロック＃Ｎにおける対地間トラヒック量推定値を示す。
【０００５】
例えば、図２のノード８（リンク＃１７）に入力しノード１３（リンク＃３６）から出力する対地間トラヒック量推定値Ｔ（１７，３６）は、以下の式（３）のように計算する。
【０００６】
Ｔ（１７，３６）＝Ｔ２（１７，５）＊Ｔ１（５，１０）／｛Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２）｝＊Ｔ４（１０，３６）／｛Ｔ４（１０，３４）＋Ｔ４（１０，３６）｝…式（３）
【０００７】
つまり、対地間トラヒック量推定値は、その対地間トラヒックの経由ブロックごとに、経由するブロックにおける対地間トラヒック量の比率を掛けることで求められる。すなわち、Ｔ（１７，３６）を計算する際、まず、Ｔ２（１７，５）が入力されるブロック＃１における入力ノード（ノード２）から、他のブロックまたはノードへ流出する対地間トラヒック量推定値の総量（Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２））を求める。そして、この総量に対する、対地間トラヒックの次のブロック（ブロック＃４）において、この対地間トラヒックの入力を受け付けるノード（ノード６）への対地間トラヒック量推定値（Ｔ１（５，１０））の比率を求める。つまり、Ｔ１（５，１０）／（Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２））を求める。これにより、ブロック＃１に入力された対地間トラヒックのトラヒック量のうち、どの程度のトラヒック量がブロック＃４に到達するかが分かる。そして、前記したＴ２（１７，５）に、この比率を掛けた値を求める。つまり、Ｔ２（１７，５）＊Ｔ１（５，１０）／｛Ｔ１（５，８）＋Ｔ１（５，１０）＋Ｔ１（５，１２）｝を求める。この後、このブロック＃４における対地間トラヒックの入力ノード（ノード６）から他のブロックまたはノードへ流出する総量（Ｔ４（１０，３４）＋Ｔ４（１０，３６））を求め、この総量に対する対地間トラヒックの出力ノードへの対地間トラヒック量推定値（Ｔ４（１０，３６））の比率を掛ける。これにより、Ｔ（１７，３６）を求めることができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−２８３７０３号公報
【非特許文献】
【０００９】
【非特許文献１】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
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、特許文献１に記載の技術において、いくつかの対地間トラヒック量が既知であっても、これを利用して対地間トラヒック量推定値の計算精度を向上させることは検討されていなかった。具体的には、前記したＴｏｍｏ−Ｇｒａｖｉｔｙ法では、対地間トラヒック量が既知である場合、既知である対地間トラヒック量をＴの要素から除いて計算することで、対地間トラヒック量推定値の計算精度を向上させることができる。ところが、特許文献１に記載の技術において、対地間トラヒック量が既知値であっても、ブロック毎の対地間トラヒック量は既知ではない。例えば、図２の例で、ノード８（リンク＃１７）に入力し、ノード１３（リンク＃３６）から出力する対地間トラヒック量が既知である場合、ブロック単位でみると、ブロック＃２では、ノード８（リンク＃１７）に入力し、ノード４（リンク＃５）から出力する対地間トラヒック量、ブロック＃１では、ノード２（リンク＃５）に入力し、ノード３（リンク＃１０）から出力する対地間トラヒック量、ブロック＃４では、ノード６（リンク＃１０）に入力し、ノード１３（リンク＃３６）から出力する対地間トラヒック量は既知ではない。従って、特許文献１に記載の技術において、Ｔｏｍｏ−Ｇｒａｖｉｔｙ法のように、単純にブロック毎の対地間トラヒック量推定値から既知である対地間トラヒック量をＴの要素を除くことで対地間トラヒック量推定値を計算することはできない。
【００１１】
そこで、本発明は、前記した問題を解決し、ブロック毎の対地間トラヒック量推定値に基づき対地間トラヒック量推定値を計算する場合において、ネットワークのいくつかの対地間トラヒック量が既知値であったとき、この既知値を利用して対地間トラヒック量推定値を計算すること目的とする。
【課題を解決するための手段】
【００１２】
前記した課題を解決するため、本発明は、ネットワークを構成するブロックごとに、当該ブロックの対地間トラヒックのトラヒック量推定値を計算し、計算したブロックごとの対地間トラヒックのトラヒック量推定値を統合して、ネットワークの対地間トラヒックのトラヒック量を推定する対地間トラヒック推定装置が、以下の処理を行う。
【００１３】
まず、対地間トラヒック推定装置は、対地間トラヒックのトラヒック量のうち、既知値の入力を受け付ける。そして、入力された既知値が０の場合、以下を行う。すなわち、対地間トラヒック推定装置は、既知値の入力を受け付けた対地間トラヒックの経由するブロックのうち、当該対地間トラヒックの始点ノードであるノードＡが属するブロックをＺ１、当該対地間トラヒックの終点ノードであるノードＣが属するブロックをＺｎ、当該対地間トラヒックの中継ブロックをＺｉ（ｉ＝２，…，ｎ−１）、ブロックＺｎにおけるブロックＺｎ−１とのブロック境界ノードをノードＢとしたとき、記憶部に記憶された、ブロックごとの対地間トラヒックのトラヒック量推定値を示すブロック毎対地間トラヒック量情報におけるブロックＺｎの対地間トラヒックのトラヒック量推定値のうち、ノードＢからノードＣへのトラヒック量推定値を０に補正する。つまり、対地間トラヒック推定装置は、対地間トラヒックの最終ブロックにおいてノードＢからノードＣへ流れるトラヒック量推定値を０とみなす。
【００１４】
そして、対地間トラヒック推定装置は、ノードＡからノードＣへの対地間トラヒックについて、ブロックＺｉにおいて、ブロックＺｉのブロック境界ノードであるノードＤに入力し、当該ブロックＺｉのブロック境界ノードであるノードＥから出力する場合において、ブロック毎対地間トラヒック量情報に示されるブロックＺｉにおけるノードＤからノードＥへの対地間トラヒックが、ブロックＺｉ＋１において、ブロックＺｉのブロック境界ノードであるノードＦに入力されるとしたとき、補正後のブロック毎対地間トラヒック量情報を参照して、ノードＤからノードＥへの対地間トラヒックのトラヒック量推定値を、以下の式（４）により補正する。この補正処理を、当該対地間トラヒックの経由するブロックＺｎ−１からブロックＺ１まで繰り返す。
当該ブロックＺｉにおけるノードＤからノードＥへの対地間トラヒック量推定値＊（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒックそれぞれのトラヒック量推定値の補正後の値の合計）／（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒックそれぞれのトラヒック量推定値の補正前の値の合計）…式（４）。
【００１５】
これにより、対地間トラヒック推定装置は、既知値を得た対地間トラヒックの最終ブロック（ブロックＺｎ）におけるトラヒック量推定値を０と仮定したとき、その対地間トラヒックと同じ始点ノードからの対地間トラヒックのトラヒック量推定値がどのような値になるのかを推定できる。すなわち、まず、対地間トラヒック推定装置は、既知値を得た対地間トラヒックの最終ブロックにおけるトラヒック量推定値の補正により、最終ブロックの１つ前のブロック（ブロックＺｎ−１）において、対地間トラヒック量推定値がどの程度変化するか（変化率）を計算する。そして、その計算結果を用いて、ブロックＺｎ−１の対地間トラヒック量推定値を補正する。次に、さらにその１つ前のブロック（ブロックＺｎ−２）における対地間トラヒック量推定値がどの程度変化するかを計算し、その計算結果を用いて、ブロックＺｎ−２における対地間トラヒック量推定値を補正する。このような計算処理を対地間トラヒックの始点ノードを含むブロック（ブロックＺ１）まで繰り返し、ブロック毎対地間トラヒック量情報に示される各ブロックの対地間トラヒック量推定値を補正する。
【００１６】
そして、対地間トラヒック推定装置は、補正したブロック毎対地間トラヒック量情報に基づき、既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれに対し、当該対地間トラヒックが経由するブロックＺｉにおけるトラヒック量推定値に（当該ブロックＺｉからブロックＺｉ＋１に出力されるトラヒック量推定値）／（当該ブロックＺｉから他のブロックに出力されるトラヒック量推定値の合計値）を掛ける処理をブロックＺ１からブロックＺｎまで繰り返す。これにより、対地間トラヒック推定装置は、既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれのトラヒック量推定値を計算する。つまり、対地間トラヒックの経由ブロックごとに、経由するブロックにおける対地間トラヒック量推定値の比率を掛けることで、既知値の対地間トラヒックと始点ノードが同じ対地間トラヒックのトラヒック量推定値を計算する。
【００１７】
そして、対地間トラヒック推定装置は、補正前のブロック毎対地間トラヒック量情報から、前記計算した対地間トラヒックそれぞれのトラヒック量推定値を減算し、減算後のブロック毎対地間トラヒック量情報に基づき、既知値の対地間トラヒックと始点ノードが異なる対地間トラヒックそれぞれのトラヒック量推定値を計算する。そして、対地間トラヒック推定装置は、計算した対地間トラヒックそれぞれのトラヒック量推定値を出力する。
【００１８】
このようにすることで、対地間トラヒック推定装置は、ネットワークの対地間トラヒック量が０であることが分かっていた場合に、これを利用して対地間トラヒック量推定値を計算できる。これにより、対地間トラヒック量推定値の計算精度を向上させることができる。
【００１９】
また、本発明の対地間トラヒック推定装置は、ネットワークのトポロジ情報、ネットワークの各リンクのリンクトラヒック量を示すリンクトラヒック情報および対地間トラヒックごとの経由リンクを示すルーティング情報とを記憶する記憶部を備えており、入力された既知値が０ではないとき、以下の処理を実行する。すなわち、対地間トラヒック推定装置は、リンクトラヒック情報における当該対地間トラヒックの経由する各リンクのトラヒック量を、入力された既知値の分、減算し、トポロジ情報に示されるノード群を複数のブロックに分割し、分割したブロックに属するノードおよびそのノードに接続されるリンクの識別情報を示すブロック間接続情報と、トラヒック量減算後のリンクトラヒック情報とを用いてブロックごとのリンクトラヒック量推定値を示すブロック毎リンクトラヒック情報を作成する。また、ブロック間接続情報と、ルーティング情報とを用いて、ブロックごとのルーティング情報であるブロック毎ルーティング情報を作成する。そして、ブロック毎リンクトラヒック情報と、ブロック毎ルーティング情報とを用いて、ブロックごとの対地間トラヒックのトラヒック量推定値を作成し、作成したトラヒック量推定値をブロック毎対地間トラヒック量情報に記憶する。その後、対地間トラヒック推定装置は、作成したブロック毎対地間トラヒック量情報を用いて、ノードＢからノードＣへのトラヒック量推定値を０に補正するステップ以降の処理を実行する。
【００２０】
このようにすることで、対地間トラヒック推定装置は、ネットワークのいくつかの対地間トラヒック量の既知値が０以外の場合でも、これを利用して対地間トラヒック量推定値を計算できる。これにより、対地間トラヒック量推定値の計算精度を向上させることができる。
【００２１】
また、本発明のプログラムは、本発明の対地間トラヒック推定方法を対地間トラヒック推定装置に実行させるためのプログラムである。このようなプログラムによれば、一般的なコンピュータに対地間トラヒック推定方法を実行させることができる。
【発明の効果】
【００２２】
本発明によれば、対地間トラヒック推定装置が、ブロック毎の対地間トラヒック量推定値に基づき対地間トラヒック量推定値を計算する場合において、ネットワークのいくつかの対地間トラヒック量が既知値であったとき、この既知値を利用して対地間トラヒック量推定値を計算できる。これにより、対地間トラヒック量推定値の計算にかかる時間を低減しつつ、対地間トラヒック量推定値の計算精度を向上させることができる。
【図面の簡単な説明】
【００２３】
【図１】従来の対地間トラヒック量の推定方法を概念的に説明した図である。
【図２】ネットワーク構成例およびブロック分割例を示した図である。
【図３】本実施の形態の対地間トラヒック推定装置の構成を示した図である。
【図４】（ａ）は、図３のブロック毎リンクトラヒック情報を例示した図であり、（ｂ）は、図３のブロック毎ルーティング情報を例示した図であり、（ｃ）は、ブロック間接続情報を例示した図である。
【図５】図３の対地間トラヒック量推定値を例示した図である。
【図６】対地間トラヒック量の既知値が０の場合における、図３の対地間トラヒック推定装置の処理手順を示したフローチャートである。
【図７】図６のＳ３の処理手順を示したフローチャートである。
【図８】図７のＳ３１の処理手順を示したフローチャートである。
【図９】図８のＳ３１の処理内容を説明するための図である。
【図１０】図７のＳ３２の処理手順を示したフローチャートである。
【図１１】図３のブロック毎対地間トラヒック量推定値を例示した図である。
【図１２】図３のブロック毎対地間トラヒック量推定値を例示した図である。
【図１３】対地間トラヒック量の既知値が０以外の場合における、図３の対地間トラヒック推定装置の処理手順を示したフローチャートである。
【発明を実施するための形態】
【００２４】
以下、本発明を実施するための形態（実施の形態）について説明する。以下の説明において、対地間トラヒックとは、入力ノードから出力ノードまで、各リンクを経由して流れるトラヒック（フロー）のことをいう。この対地間トラヒックのトラヒック量を、対地間トラヒック量と呼ぶ。対地間トラヒック推定装置１００（後記する図３参照）は、対地間トラヒック量の既知値の入力を受け付けると、この既知値に基づき、ネットワークの対地間トラヒックそれぞれのトラヒック量の推定値（対地間トラヒック量推定値）を計算する。
【００２５】
まず、本実施の形態で扱うネットワークの構成例を説明する。ネットワークは、図２に例示するように１以上のノード（ノード番号１〜１５）と、そのノード間を接続するリンクとにより構成される。図２において、ノード８〜１５には、他のノードと接続されていないリンクがあるが、このようなリンクを外部リンクと呼ぶ。この外部リンクは、ネットワークへのトラヒックの入力ポイント、出力ポイントとなるリンクである。この外部リンクは、例えば、別のネットワークやユーザの端末装置に接続されている。対地間トラヒックは、このような外部リンクを介して、ノードに入力され、リンクおよびノードを経由して、ネットワーク内の別のノード（または同じノード）から出力される。なお、ネットワークを構成するノードは、例えば、ＳＯＮＥＴ（Synchronous Optical NETwork）／ＳＤＨ（Synchronous Digital Hierarchy）クロスコネクトや、波長クロスコネクト等の伝送装置、ルータ、レイヤ２スイッチ等である。リンクは、ノード間に存在し、情報転送の媒体であり、例えば、光ファイバ等である。
【００２６】
次に、対地間トラヒック推定装置１００が対地間トラヒック量推定値を計算するときの手順を簡単に説明する。対地間トラヒック推定装置１００は、ネットワークのルーティング情報（各トラヒックがネットワークのどのリンクを経由するか示した情報）およびリンクトラヒック情報（ネットワーク内の各リンクのトラヒック量を示した情報）の入力を受け付けると、図２に示すように、このネットワークをいくつかのブロックに分割する。次に、入力されたルーティング情報およびリンクトラヒック情報を、このブロックごとに分割し、分割したブロックごとの対地間トラヒック量の推定（ブロック毎対地間トラヒック量推定値１３７（後記する図３参照）の計算）を行う。そして、このブロック単位の推定結果を統合し、全体の推定結果、すなわち、ネットワーク全体の対地間トラヒック量の推定結果を得る。ここで、対地間トラヒック量の既知値（例えば、０）が与えられたとき、対地間トラヒック推定装置１００は、ブロック統合処理を以下のようにして行う。
【００２７】
まず、対地間トラヒック推定装置１００は、ブロック毎対地間トラヒック量推定値１３７のうち、既知値が与えられた対地間トラヒックａ（例えば、図２におけるＴ（１７，３６））の経由する各ブロックの対地間トラヒック量推定値を補正する。このときの補正方法について詳細は後記するが、ブロック毎対地間トラヒック量推定値１３７のうち、まず、対地間トラヒックａの到達する最終ブロックＺｎ（例えば、図２のブロック＃４）における、この対地間トラヒックａの終点ノード（例えば、ノード１３（リンク＃３６））への対地間トラヒック量推定値を０に補正する。そして、この最終ノードへのトラヒック量推定値を０に補正すると、最終ブロックの１つ前のブロック（ブロックＺｎ−１。例えば、ブロック＃１）から、最終ブロックへ流入する対地間トラヒック量が補正後にどのように変化するか（変化率）を計算する。そして、その計算結果を反映して、最終ブロックの１つ前のブロックにおける対地間トラヒック量推定値を補正する。そして、その補正結果を用いて、さらにブロックＺｎ−１の１つ前のブロック（ブロックＺｎ−２。例えば、ブロック＃２）における対地間トラヒック量推定値を補正する。このような処理を対地間トラヒックａの始点ノードを含む始点ブロック（ブロックＺ１。例えば、ブロック＃２）まで繰り返し、ブロック毎対地間トラヒック量推定値１３７における、対地間トラヒックａの最終ブロックから始点ブロックまでの対地間トラヒック量推定値を補正する。そして、補正したブロック毎対地間トラヒック量推定値１３７における各ブロックの対地間トラヒック量推定値に基づき、対地間トラヒックａの始点ノードＡ（例えば、ノード８）と同じ始点ノードからの対地間トラヒックのトラヒック量推定値（例えば、Ｔ（１７，３４））を計算する。その後、ブロック毎対地間トラヒック量推定値１３７から、計算した対地間トラヒック量推定値を減算する。そして、この減算後のブロック毎対地間トラヒック量推定値１３７における各ブロックのトラヒック量推定値に基づき、始点ノードＡ以外の各ノード（例えば、ノード９，１０，１１，１２，１３，１４，１５）を始点ノードとする対地間トラヒック量推定値を計算する。このようにすることで、ネットワークの全対地間トラヒック量推定値を計算できる。
【００２８】
次に、図３を用いて、対地間トラヒック推定装置１００の構成を説明する。この対地間トラヒック推定装置１００は、前記したとおり、ネットワークの各ノードを複数のブロックに分割し、そのブロックごとの対地間トラヒック量推定値（ブロック毎対地間トラヒック量推定値１３７）を計算する。そして、このブロック毎対地間トラヒック量推定値１３７をもとに、ネットワーク全体の対地間トラヒック量推定値を計算する。このような対地間トラヒック推定装置１００は、入力部１１０と、ブロック分割部１２１と、ブロック毎ルーティング情報作成部１２２と、ブロック毎リンクトラヒック情報作成部１２３と、初期値計算部１２４と、ブロック毎対地間トラヒック量推定部１２５と、ブロック統合部１２６と、リンクトラヒック減算部１２７と、出力部１４０とを備える。入力部１１０は、トポロジ情報１３１、ルーティング情報１３２、リンクトラヒック情報１３３等の入力を受け付け、対地間トラヒック推定装置１００の記憶部（図示省略）に記憶する。また、出力部１４０は、ブロック統合部１２６による計算結果（ネットワークの各対地間トラヒック量推定値）を出力する。
【００２９】
入力部１１０および出力部１４０は、入出力インタフェースから構成される。また、ブロック分割部１２１と、ブロック毎ルーティング情報作成部１２２と、ブロック毎リンクトラヒック情報作成部１２３と、初期値計算部１２４と、ブロック毎対地間トラヒック量推定部１２５と、ブロック統合部１２６と、リンクトラヒック減算部１２７とは、この対地間トラヒック推定装置１００の備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、入力部１１０経由で入力された、トポロジ情報１３１と、ルーティング情報１３２と、リンクトラヒック情報１３３とは、この対地間トラヒック推定装置１００の記憶部（図示省略）に記憶される。この記憶部は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、対地間トラヒック推定装置１００をプログラム実行処理により実現する場合、記憶部には、この対地間トラヒック推定装置１００の機能を実現するためのプログラムが格納される。また、この記憶部には、対地間トラヒック量の推定値の計算過程で作成される、ブロック間接続情報１３４、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６、ブロック毎対地間トラヒック量推定値１３７等が記憶される。
【００３０】
トポロジ情報１３１は、ネットワークに存在するノードと、どのノード間のリンクが存在するかを示した情報である。このトポロジ情報１３１は、ＯＳＰＦ（Open Shortest Path First）において利用されるリンクコストの値を含んでいてもよい。例えば、トポロジ情報１３１には、図２に示すように、ネットワーク内に存在するノードと、そのノード間を接続するリンクの情報が示される。なお、ここでは、ノード間を接続するリンクを方向別に示している。例えば、ノード２からノード1へのリンクは「リンク＃１」であり、ノード１からノード２へのリンクは「リンク＃２」であることを示す。
【００３１】
ルーティング情報１３２は、ネットワーク内の各対地間トラヒックの経路情報を、各対地間トラヒックの経由する一連のリンクの識別情報（リンク番号）で示した情報である。なお、このルーティング情報１３２は、例えば、ネットワーク内のルーティングがＯＳＰＦにより行われる場合を想定して、シミュレーション等により求めてもよい。このルーティング情報１３２は、例えば、リンク数×フロー（対地間トラヒック）数の行列により表される。なお、このルーティング情報１３２は、各対地間トラヒックの経由するノードの識別情報で示してもよい。
【００３２】
リンクトラヒック情報１３３は、ネットワーク内のリンクごとに、そのリンクのリンクトラヒック量を示した情報である。
【００３３】
ブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内の各ノードを複数のブロックに分割する。例えば、このブロック分割部１２１は、ネットワークの各ノードを、図２に示すように、ブロック＃１〜ブロック＃５の５つのブロックに分割する。ここでのブロック分割は、ネットワークのノードをいずれかのブロックに属するようにする。また、ブロック分割の方法は、様々な方法が考えられるが、同じブロック内においてトラヒックの入力ノードと出力ノードとなるノード間の経路が他のブロックを経由しないようにするのが好ましい。例えば、図２に示すように、ブロック＃２のノード８から、ノード４への経路において、ブロック＃３やブロック＃１を経由しないようにするのが好ましい。これは、ブロック統合部１２６が、ブロック毎対地間トラヒック量推定値１３７をもとに、ネットワーク全体の対地間トラヒック量の推定値を計算するとき、対地間トラヒックの経由するブロックの数が少ない方が、推定値の計算精度を向上させることができるからである。
【００３４】
このブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内の各ノードを複数のブロックに分割すると、その分割結果をブロック間接続情報１３４として記録する。このブロック間接続情報１３４は、分割したブロックに属するノードと別のブロックに属するノードを接続するリンクを示した情報である（図４（ｃ）参照）。例えば、図４（ｃ）は、図２のブロック＃１のブロック間接続情報であり、リンク番号「リンク＃５」は、ブロック番号「ブロック＃２」に属し、このリンクはノード４に接続されるリンクであることを示す。このブロック間接続情報１３４は、ブロック統合部１２６が、ブロックごとの対地間トラヒック量の推定値（ブロック毎対地間トラヒック量推定値１３７）を統合して対地間トラヒックの推定値を計算するときに参照される。
【００３５】
図３のブロック毎ルーティング情報作成部１２２は、ブロック間接続情報１３４およびルーティング情報１３２を用いて、ルーティング情報１３２に示される対地間トラヒックそれぞれの、各ブロックにおけるルーティング情報を作成し、ブロック毎ルーティング情報１３５に記録する。例えば、このブロック毎ルーティング情報１３５には、図４（ｂ）に示すようなルーティング情報が記憶される。図４（ｂ）は、図２のブロック＃１のルーティング情報であり、対地間トラヒック番号「１」の対地間トラヒックは、「リンク＃５，＃８」を経由することを示す。このブロック毎ルーティング情報１３５は、ブロック毎対地間トラヒック量推定部１２５が、ブロック毎対地間トラヒック量推定値１３７を計算するときに参照される。
【００３６】
ブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３をブロックごとに分割して、ブロック毎リンクトラヒック情報１３６を作成する。このブロック毎リンクトラヒック情報１３６には、図４（ａ）に示すようなリンクトラヒック情報が記憶される。図４（ａ）は、図２のブロック＃１のリンクトラヒック情報であり、リンク番号「１」のリンクトラヒック量は「Ｘ１」であることを示す。このブロック毎リンクトラヒック情報１３６は、ブロック毎対地間トラヒック量推定部１２５が、ブロック毎対地間トラヒック量の推定値を計算するときに参照される。
【００３７】
図３の初期値計算部１２４は、ブロック毎リンクトラヒック情報１３６を参照して、Ｇｒａｖｉｔｙ法等により、ブロックごとに、そのブロックの対地間トラヒック量の推定値の初期値を計算する。計算した初期値は、記憶部の所定領域に記憶しておく。
【００３８】
ブロック毎対地間トラヒック量推定部１２５は、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６およびブロックごとの対地間トラヒック量の推定値の初期値を用いて、Ｔｏｍｏ−Ｇｒａｖｉｔｙ法等により、ブロックごとの対地間トラヒック量の推定値を計算する。そして、その計算結果をブロック毎対地間トラヒック量推定値（ブロック毎対地間トラヒック量情報）１３７として記憶部の所定領域に記憶する。このブロック毎対地間トラヒック量推定値１３７は、ブロック統合部１２６が、ブロックごとの対地間トラヒック量の推定値を統合して対地間トラヒックの推定値を求めるときに参照される。
【００３９】
例えば、ブロック毎対地間トラヒック量推定値１３７には、図５（ａ）〜（ｃ）に示すようにブロック＃１，＃２，＃４それぞれの、対地間トラヒック量の推定値が記録される。図５（ａ）のブロック＃１の対地間トラヒック量推定値は、ブロック＃１において入口（入力ノード）がノード２（リンク＃５）で、出口（出力ノード）がノード３（リンク＃１０）の対地間トラヒック量推定値は「Ｔ１（５，１０）」であることを示す。
【００４０】
ブロック統合部１２６は、ブロック間接続情報１３４およびブロック毎ルーティング情報１３５を参照して、対地間トラヒックごとに、その対地間トラヒックの経由するブロックと、そのブロックにおける経路を特定する。そして、この対地間トラヒックのブロックそれぞれにおける対地間トラヒック量推定値をブロック毎対地間トラヒック量推定値１３７から読み出し、この読み出した対地間トラヒック量推定値を用いて、この対地間トラヒックのトラヒック量推定値を計算する。このような処理を各対地間トラヒックに対し実行し、計算した各対地間トラヒックのトラヒック量推定値を出力部１４０経由で出力する。このときの対地間トラヒックのトラヒック量推定値の計算は、特許文献１に記載の技術に基づき実行される。
【００４１】
また、このブロック統合部１２６は、入力部１１０経由で対地間トラヒック量の既知値が入力されると、ブロック毎対地間トラヒック量推定値１３７における対地間トラヒック量推定値を補正する補正部１２８を備える。この補正部１２８による対地間トラヒック量推定値の補正処理の詳細は、フローチャートおよび具体例を用いて後記するが、ブロック統合部１２６は、補正部１２８により補正されたブロック毎対地間トラヒック量推定値１３７に基づき、対地間トラヒック量推定値を計算する。
【００４２】
リンクトラヒック減算部１２７は、対地間トラヒック量の既知値が入力されたとき、この既知値をリンクトラヒック情報１３３から減算して、ブロック毎リンクトラヒック情報作成部１２３へ出力する。その後、ブロック毎リンクトラヒック情報作成部１２３は、減算後のリンクトラヒック情報１３３からブロック毎リンクトラヒック情報１３６を作成する。
【００４３】
＜処理手順＞
次に、図３を参照しつつ、図６を用いて、対地間トラヒック推定装置１００の処理手順を説明する。対地間トラヒック推定装置１００は事前準備として、入力部１１０経由で、トポロジ情報１３１、ルーティング情報１３２、リンクトラヒック情報１３３および対地間トラヒック量の既知値の入力を受け付け、記憶部に記憶しておくものとする。なお、ここでは、対地間トラヒック量の既知値が０である場合を例に説明する。対地間トラヒック量の既知値が０以外の値である場合については、後記する。
【００４４】
まず、図３の対地間トラヒック推定装置１００の入力部１１０からの指示入力に基づき、ブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内のノード群を複数のブロックに分割する（Ｓ１：ブロック分割）。そして、その分割結果をブロック間接続情報１３４として記録する。そして、対地間トラヒック推定装置１００は、ブロック毎対地間トラヒック量の推定値を計算する（Ｓ２）。つまり、まず、対地間トラヒック推定装置１００のブロック毎リンクトラヒック情報作成部１２３は、リンクトラヒック情報１３３をブロックごとに分割して、各ブロックのリンクトラヒック情報を示したブロック毎リンクトラヒック情報１３６を作成する。また、ブロック毎ルーティング情報作成部１２２は、ブロック間接続情報１３４およびルーティング情報１３２を用いて、ブロックごとのルーティング情報を示したブロック毎ルーティング情報１３５を作成する。そして、初期値計算部１２４は、ブロック毎リンクトラヒック情報１３６を参照して、Ｇｒａｖｉｔｙ法等によりブロックごとに、当該ブロックにおける対地間トラヒック量推定値の初期値を計算する。次に、ブロック毎対地間トラヒック量推定部１２５は、ブロック毎ルーティング情報１３５、ブロック毎リンクトラヒック情報１３６およびブロックごとの対地間トラヒック量推定値の初期値を用いて、Ｔｏｍｏ−Ｇｒａｖｉｔｙ法により、ブロックそれぞれの対地間トラヒック量推定値を計算する。そして、その計算結果を、ブロック毎対地間トラヒック量推定値１３７として記憶部の所定領域に記憶する。
【００４５】
次に、ブロック統合部１２６は、補正部１２８により、入力された対地間トラヒック量の既知値に基づき、ブロック毎対地間トラヒック量推定値１３７における各ブロックの対地間トラヒック量推定値を補正する。そして、その補正したブロック毎対地間トラヒック量推定値１３７に基づき、全対地間トラヒック量推定値を計算し（Ｓ３：対地間トラヒック推定値計算）、出力部１４０経由で出力する。
【００４６】
この対地間トラヒック推定値計算処理（Ｓ３）は、図７に示すように、Ｓ３１およびＳ３２の処理からなる。つまり、図３の対地間トラヒック推定装置１００のブロック統合部１２６は、Ｓ３１で、対地間トラヒック量が既知値である対地間トラヒックのうち、ブロックまたぎになっている対地間トラヒックについて、その対地間トラヒックの始点ノードとなっているノードの集合を抽出する。そして、その抽出されたノードの集合を始点とする対地間トラヒック量推定値を求める。つまり、トラヒック量が既知値である対地間トラヒックがブロックまたぎであるとき、その対地間トラヒックと始点ノードが同じ各対地間トラヒックのトラヒック量推定値を求める。
【００４７】
次に、Ｓ３２で、ブロック統合部１２６は、Ｓ３１で計算対象とした対地間トラヒックの始点ノード以外のノードの集合を抽出し、その抽出されたノードの集合を始点とする対地間トラヒック量推定値を計算する。つまり、ブロック統合部１２６は、Ｓ３１で計算した対地間トラヒック量推定値に基づき、Ｓ３１で計算した対地間トラヒック以外の対地間トラヒックのトラヒック量推定値を求める。これにより、対地間トラヒック推定装置１００は、全対地間トラヒック推定値を求めることができる。
【００４８】
＜既知値の対地間トラヒックと始点ノードが同じ対地間トラヒックのトラヒック量推定値の計算＞
次に、図８，９を用いて、図７のＳ３１の処理を詳細に説明する。まず、図３のブロック統合部１２６の補正部１２８は、トラヒック量が既知値である対地間トラヒックのうち、ブロックまたぎになっている対地間トラヒックについて、その対地間トラヒックの始点ノードとなっているノードの集合を抽出しておく（Ｓ３１０）。そして、その抽出されたノード集合から１つのノードを選択し（Ｓ３１１）、選択されたノードが始点となっており、かつ、対地間トラヒック量が既知値である対地間トラヒックを１つ選択する（Ｓ３１２）。そして、Ｓ３１３へ進む。
【００４９】
Ｓ３１３において、補正部１２８は、選択された対地間トラヒックの始点をノードＡ、終点をノードＣ、ノードＡが属するブロックをＺ１、ノードＣが属するブロック（最終ブロック）をＺｎ、ノードＡ→ノードＢの対地間トラヒックが経由するブロックをＺｉ（ｉ＝２，…，ｎ−１）、ブロックＺｎにおけるブロック境界ノードをノードＢとした場合、ブロックＺｎにおいて、ブロック毎対地間トラヒック量推定値１３７のうち、ノードＢ→ノードＣの対地間トラヒック量推定値を０とみなすように補正する（Ｓ３１３。図９参照）。つまり、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７における、既知値の対地間トラヒックについて、ブロックＺｎの終点ノードに到達するブロック毎対地間トラヒック量推定値を０に補正する。
【００５０】
次に、補正部１２８は、ノードＡ→ノードＣの対地間トラヒックが、ブロックＺｉ（ｉ＝ｎ−１からスタート）において、ブロック境界ノードＤに入力し、ブロック境界ノードＥから出力し、ブロックＺｉ＋１において、ブロック境界ノードＦに入力する場合、ブロックＺｉにおいて、ブロック毎対地間トラヒック量推定値１３７のうち、ノードＤ→ノードＥの対地間トラヒック量推定値を以下の式（５）の値とみなすように補正する（Ｓ３１４）。
ブロックＺｉでのノードＤ→ノードＥの対地間トラヒック量推定値＊（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒック量推定値の補正後の合計）／（ブロックＺｉ＋１でのノードＦを始点とする対地間トラヒック量推定値の補正前の合計）…式（５）
つまり、補正部１２８は、ブロックＺｉ＋１での対地間トラヒック量推定値の補正前後での変化率により、ブロックＺｉ＋１の１つ前のブロック（ブロックＺｉ）における対地間トラヒック量推定値を補正する。
【００５１】
次に、補正部１２８は、Ｓ３１４のブロック毎対地間トラヒック量推定値１３７の補正処理について、ノードＡ→ノードＣの対地間トラヒックの全ブロックについて実行したか否かを判断し（Ｓ３１５）、まだＳ３１４の処理を実行していないブロックがあれば（Ｓ３１５のＮｏ）、Ｚｉのｉの値を１減らして、Ｓ３１４の処理を実行する。つまり、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７のうち、ノードＡ→ノードＣの対地間トラヒックの各ブロックの対地間トラヒック量推定値を、最終ブロック（ブロックＺｎ）から始点ブロック（ブロックＺ１）へ向かって順に補正していく。このとき、補正部１２８は、補正によるブロックＺｉ＋１の対地間トラヒック量推定値の変化率に比例して、ブロックＺｉの対地間トラヒック量推定値を補正していく。
【００５２】
Ｓ３１４の後、補正部１２８は、Ｓ３１４のブロック毎対地間トラヒック量推定値１３７の補正処理について、ノードＡ→ノードＣの対地間トラヒックの全ブロックについて実行したと判断したとき（Ｓ３１５のＹｅｓ）、補正部１２８は、Ｓ３１１で選択したノードを始点とするすべての対地間トラヒックについてＳ３１２〜Ｓ３１５の処理を実行したか否かを判断する（Ｓ３１６）。ここで、まだＳ３１２〜Ｓ３１５の処理を実行していない対地間トラヒックがあれば（Ｓ３１６のＮｏ）、Ｓ３１２へ戻る。一方、全対地間トラヒックについてＳ３１２〜Ｓ３１５の処理を実行済みであれば（Ｓ３１６のＹｅｓ）、ブロック統合部１２６は、ブロック毎対地間トラヒック量推定値１３７の補正値（補正したブロック毎対地間トラヒック量推定値１３７）に基づき、Ｓ３１１で選択されたノードを始点とする対地間トラヒック量推定値を求める（Ｓ３１７）。つまり、補正部１２８は、既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれに対し、この対地間トラヒックが経由するブロックＺｉにおけるトラヒック量推定値＊（ブロックＺｉからブロックＺｉ＋１に出力されるトラヒック量推定値）／（ブロックＺｉから他のブロックに出力されるトラヒック量推定値の合計値）を掛ける処理をブロックＺ１からブロックＺｎまで繰り返す。これにより、既知値の対地間トラヒックと始点ノードが同じである他の対地間トラヒックそれぞれのトラヒック量推定値を計算する。そして、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７の補正値を元に戻す（Ｓ３１８）。ここで、Ｓ３１０で抽出したノード集合のうち、まだＳ３１１以降の処理を実行していないノードがあれば（Ｓ３１９のＮｏ）、補正部１２８は、Ｓ３１１以降の処理を実行し、Ｓ３１０で抽出したノード集合のすべてについて、Ｓ３１１以降の処理を実行済みであれば（Ｓ３１９のＹｅｓ）、Ｓ３１の処理を終了する。
【００５３】
以上の処理により、既知値の対地間トラヒックと始点ノードが同じ対地間トラヒックのトラヒック量推定値を計算することができる。
【００５４】
＜既知値の対地間トラヒックの始点ノード以外のノードを始点とする対地間トラヒックのトラヒック量推定値の計算＞
次に、図１０を用いて、図７のＳ３２の処理を詳細に説明する。まず、ブロック統合部１２６の補正部１２８は、Ｓ３１で計算対象とした対地間トラヒックの始点ノード以外のノードを集合を抽出する（Ｓ３２０）。そして、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７のうち、Ｓ３１で計算した対地間トラヒックの経由する対地間トラヒック量推定値を、Ｓ３１で計算した対地間トラヒック量推定値の分、減算する（Ｓ３２１）。つまり、ブロック毎対地間トラヒック量推定値１３７から、Ｓ３１で計算した対地間トラヒック量推定値を減算する。
【００５５】
そして、補正部１２８は、Ｓ３２０で抽出されたノード集合から１つのノードを選択し（Ｓ３２２）、ブロック統合部１２６は、Ｓ３２１で減算したブロック毎対地間トラヒック量推定値１３７に基づき、Ｓ３２２で選択したノードを始点とする対地間トラヒック量推定値を求める（Ｓ３２３）。そして、Ｓ３２０で抽出したノード集合のうち、まだＳ３２２以降の処理を実行していないノードがあれば（Ｓ３２４でＮｏ）、Ｓ３２２へ戻り、すべてのノードについてＳ３２２以降の処理を実行済みであれば（Ｓ３２４でＹｅｓ）、Ｓ３２の処理を終了する。
【００５６】
このようにすることで対地間トラヒック推定装置１００は、既知値の対地間トラヒックと始点ノードが異なる対地間トラヒックのトラヒック量推定値を計算できる。
【００５７】
以上の処理により、対地間トラヒック推定装置１００は、対地間トラヒック量の既知値０が与えられたとき、全対地間トラヒック量推定値を計算することができる。
【００５８】
＜具体例＞
次に、対地間トラヒック量の既知値を用いた、対地間トラヒック量推定値の計算の具体例を説明する。ここでは、既知値として、図２のノード８（リンク＃１７）からノード１３（リンク＃３６）への対地間トラヒック量０が与えられている場合を例に説明する。なお、図１１，１２は、ブロック毎対地間トラヒック量推定値１３７のうち、ブロック＃１，＃２，＃４の対地間トラヒック量推定値を例示したものである。なお、図１１，１２における→の後の値は、補正後の対地間トラヒック量推定値である。
【００５９】
ここで、この既知値を有するノード８（リンク＃１７）からノード１３（リンク＃３６）の対地間トラヒックは、ブロック＃２、ブロック＃１、ブロック＃４を経由している。従って、図３の対地間トラヒック推定装置１００の補正部１２８は、図８のＳ３１３で、最終ブロックであるブロック＃４において、ブロック毎対地間トラヒック量推定値１３７のうち、ノード６（リンク＃１０）に入力しノード１３（リンク＃３６）から出力する対地間トラヒック量推定値を、図１１の（ｃ）に示すように０に補正する。
【００６０】
次に、補正部１２８は、ブロック＃１において、図８のＳ３１４で、ブロック毎対地間トラヒック量推定値１３７のうち、ノード２（リンク＃５）に入力しノード３（リンク＃１０）から出力する対地間トラヒック量推定値Ｔ１（５，１０）を、以下に示すＴ１’（５，１０）に補正する（図１１の（ａ）参照）。
Ｔ１’（５，１０）＝Ｔ１（５，１０）＊Ｔ４（１０，３４）／｛Ｔ４（１０，３４）＋Ｔ４（１０，３６）｝
【００６１】
つまり、補正部１２８は、ブロック＃１のノード２（リンク＃５）からノード３（リンク＃１０）出力する対地間トラヒック量推定値Ｔ１（５，１０）を、この対地間トラヒック量推定値Ｔ１（５，１０）に対し、ブロック＃４におけるノード６（リンク＃１０）に入力し、ノード１２（リンク＃３４）から出力する対地間トラヒック量推定値の補正前後の変化率を掛けた値（Ｔ１’（５，１０））に補正する。
【００６２】
この補正値Ｔ１’（５，１０）をもとに、ブロック統合部１２６は、ノード８を始点とする対地間トラヒック量推定値を計算する（図８のＳ３１７）。例えば、ブロック統合部１２６は、ノード８（リンク＃１７）に入力し、ノード１２（リンク＃３４）に出力する対地間トラヒック量推定値Ｔ（１７，３４）を以下のように計算する。
Ｔ（１７，３４）＝Ｔ１（１７，５）＊Ｔ１’（５，１０）／｛Ｔ１（５，８）＋Ｔ１’（５，１０）＋Ｔ１（５，１２）｝＊Ｔ４（１０，３４）／Ｔ４（１０，３４）
【００６３】
ブロック統合部１２６は、ノード８（リンク＃１７）を始点とする他の対地間トラヒック量推定値（Ｔ（１７，２０）、Ｔ（１７，２６）、Ｔ（１７，２８）、Ｔ（１７，４２）、Ｔ（１７，４４））についても同様に計算する。
【００６４】
次に、ブロック統合部１２６は、ノード８（リンク＃１７）以外を始点とする対地間トラヒック量推定値を求める。まず、補正部１２８は、ノード８（リンク＃１７）を始点とする各対地間トラヒック量推定値を、ブロック毎対地間トラヒック量推定値１３７から減算して補正する（図１０のＳ３２１）。例えば、補正部１２８は、ブロック＃１で、ノード２（リンク＃５）に入力し、ノード３（リンク＃１０）に出力する対地間トラヒック量推定値Ｔ１（５，１０）を、以下に示すＴ１’（５，１０）に補正する。
Ｔ１’（５，１０）＝Ｔ１（５，１０）−Ｔ（１７，３４）
また、ブロック＃１で、ノード２（リンク＃５）に入力し、ノード３（リンク＃８）に出力する対地間トラヒック量推定値を、以下のＴ１’（５，８）に補正する。
Ｔ１’（５，８）＝Ｔ１（５，８）−｛Ｔ（１７，２６）＋Ｔ（１７，２８）｝
さらに、ブロック＃１で、ノード２（リンク＃５）に入力し、ノード３（リンク＃１２）に出力する対地間トラヒック量推定値、以下のＴ１’（５，１２）に補正する。
Ｔ１’（５，１２）＝Ｔ１（５，１２）−｛Ｔ（１７，４２）＋Ｔ（１７，４４）｝
に補正する。
つまり、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７のうち、ブロック＃１の対地間トラヒック量推定値を図１２（ａ）に示すように補正する。
【００６５】
さらに、補正部１２８は、ブロック＃２で、ノード８（リンク＃１７）に入力し、ノード５（リンク＃５）に出力する対地間トラヒック量推定値を、以下のＴ２’（１７，５）に補正する。
Ｔ２’（１７，５）＝Ｔ２（１７，５）−｛Ｔ（１７，２６）＋Ｔ（１７，２８）＋Ｔ（１７，３４）＋Ｔ（１７，４２）＋Ｔ（１７，４４）｝
つまり、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７のうち、ブロック＃２の対地間トラヒック量推定値を図１２（ｂ）に示すように補正する。
【００６６】
また、ブロック＃４で、ノード６（リンク＃１０）に入力しノード１２（リンク＃３４）に出力する対地間トラヒック量推定値を、以下のＴ４’（１０，３４）に補正する。
Ｔ４’（１０，３４）＝Ｔ４（１０，３４）−Ｔ（１７，３４）
に補正する。
つまり、補正部１２８は、ブロック毎対地間トラヒック量推定値１３７のうち、ブロック＃４の対地間トラヒック量推定値を図１２（ｃ）に示すように補正する。
【００６７】
次に、ブロック統合部１２６は、これらの補正したブロック毎対地間トラヒック量推定値１３７に基づき、ノード８（リンク＃１７）以外を始点とする全対地間トラヒック量推定値を計算する（図１０のＳ３２３）。例えば、ブロック統合部１２６は、ノード９（リンク＃１９）に入力し、ノード１２（リンク＃３４）に出力する対地間トラヒック量推定値Ｔ（１９，３４）を、以下のように計算する。
Ｔ（１９，３４）＝Ｔ１（１９，５）＊Ｔ１’（５，１０）／｛Ｔ１’（５，８）＋Ｔ１’（５，１０）＋Ｔ１’（５，１２）｝＊Ｔ４’（１０，３４）／｛Ｔ４’（１０，３４）＋Ｔ４（１０，３６）｝
また、ブロック統合部１２６は、このノード８（リンク＃１７）以外を始点とする各対地間トラヒックについても同様に対地間トラヒック量推定値を求める。
【００６８】
このようにすることで対地間トラヒック推定装置１００は、対地間トラヒック量の既知値が０の場合、この既知値を用いてブロック毎対地間トラヒック量推定値１３７を補正し、全対地間トラヒック量推定値を計算することができる。
【００６９】
次に、対地間トラヒック量の既知値が０以外の場合の対地間トラヒック量推定値の計算方法について、図１３を用いて、説明する。
【００７０】
図３の対地間トラヒック推定装置１００が、入力部１１０経由で対地間トラヒック量の既知値Ｘの入力を受け付けると、リンクトラヒック減算部１２７は、リンクトラヒック情報１３３における、既知値の対地間トラヒックの経由する各リンクのトラヒック量をＸ減算する（Ｓ０）。例えば、図２のノード８（リンク＃１７）に入力し、ノード１３（リンク＃３６）に出力する対地間トラヒック量がＸであることが既知であるとき、リンクトラヒック減算部１２７は、リンクトラヒック情報１３３の、リンク＃１７，＃１３，＃５，＃１，＃４，＃１０，＃３２，＃３６のリンクトラヒック量からＸ減算する。
【００７１】
次に、前記したＳ１と同様に、ブロック分割部１２１は、トポロジ情報１３１に示されるネットワーク内のノード群を複数のブロックに分割する（Ｓ１：ブロック分割）。そして、対地間トラヒック推定装置１００は、Ｓ０で減算したリンクトラヒック情報１３３に基づき、Ｓ２と同様の手順により、ブロック毎対地間トラヒック量推定値１３７を計算する（Ｓ２）。そして、ブロック統合部１２６は、前記したＳ３と同様の手順により、補正部１２８により、ブロック毎対地間トラヒック量推定値１３７における、既知値の対地間トラヒックの最終ブロックにおける対地間トラヒック量推定値を０とみなして、ブロック毎対地間トラヒック量推定値１３７における各ブロックの対地間トラヒック量推定値を補正する。そして、前記したＳ３と同様の手順により、補正したブロック毎対地間トラヒック量推定値１３７に基づき、全対地間トラヒック量推定値を計算し（Ｓ３：対地間トラヒック推定値計算）、計算した全対地間トラヒック量推定値を出力部１４０経由で出力する。
【００７２】
このようにすることで、対地間トラヒック推定装置１００は、対地間トラヒック量の既知値が０以外の場合でも、ブロック毎対地間トラヒック量推定値１３７を補正し、各対地間トラヒック量推定値を計算することができる。
【００７３】
以上説明した対地間トラヒック推定装置１００によれば、ブロック毎対地間トラヒック量推定値１３７に基づき対地間トラヒック量推定値を計算する場合において、ネットワークのいくつかの対地間トラヒック量が既知値であったとき、この既知値を利用して対地間トラヒック量推定値を計算できる。これにより、対地間トラヒック量推定値の計算にかかる時間を低減しつつ、対地間トラヒック量推定値の計算精度を向上させることができる。
【符号の説明】
【００７４】
１００  対地間トラヒック推定装置
１１０  入力部
１２１  ブロック分割部
１２２  ブロック毎ルーティング情報作成部
１２３  ブロック毎リンクトラヒック情報作成部
１２４  初期値計算部
１２５  ブロック毎対地間トラヒック量推定部
１２６  ブロック統合部
１２７  リンクトラヒック減算部
１２８  補正部
１３１  トポロジ情報
１３２  ルーティング情報
１３３  リンクトラヒック情報
１３４  ブロック間接続情報
１３５  ブロック毎ルーティング情報
１３６  ブロック毎リンクトラヒック情報
１３７  ブロック毎対地間トラヒック量推定値
１４０  出力部
【図１】
0005379818.tif 000002
【図２】
0005379818.tif 000003
【図３】
0005379818.tif 000004
【図４】
0005379818.tif 000005
【図５】
0005379818.tif 000006
【図６】
0005379818.tif 000007
【図７】
0005379818.tif 000008
【図８】
0005379818.tif 000009
【図９】
0005379818.tif 000010
【図１０】
0005379818.tif 000011
【図１１】
0005379818.tif 000012
【図１２】
0005379818.tif 000013
【図１３】
0005379818.tif 000014