(57)【要約】【課題】ネットワーク内の交流トラヒック推定値の計算精度を向上させる。【解決手段】交流トラヒック推定装置は、まず、Ｇｒａｖｉｔｙ法等により交流トラヒックの推定値の初期値を計算し、この計算した初期値を用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により交流トラヒック推定値を計算する。ここで、計算した交流トラヒック推定値に負の値が含まれていたとき、交流トラヒック推定装置は、この負の値を０に修正したものを新たな初期値ベクトルＴｉｎとして、再度交流トラヒック推定値を計算する。そして、この交流トラヒック推定値の計算結果に、負の値が含まれず、かつ、この交流トラヒック推定値の計算に用いた初期値ベクトルＴｉｎとの差が所定の閾値以下であれば、この交流トラヒック推定値ベクトルＴｏｕｔを出力する。【選択図】図６
2010283701.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内の交流トラヒックにおけるフローそれぞれが経路として用いるリンクを示したルーティング情報と、前記ネットワーク内のリンクそれぞれのリンクトラヒック量を示したリンクトラヒック情報とを用いて、前記フローそれぞれの推定値を計算する交流トラヒック推定装置であって、
前記ルーティング情報および前記リンクトラヒック情報の入力を受け付ける入力部と、
前記ルーティング情報および前記リンクトラヒック情報を記憶する記憶部と、
前記リンクトラヒック情報を参照して、前記フローそれぞれの推定値の初期値を示した初期値ベクトルＴｉｎを計算する初期値計算部と、
前記ルーティング情報、前記リンクトラヒック情報および前記初期値ベクトルＴｉｎを用いて、前記フローそれぞれの推定値を示した交流トラヒック推定値ベクトルＴｏｕｔを計算する交流トラヒック計算部と、
前記交流トラヒック計算部により計算された交流トラヒック推定値ベクトルに負の推定値が含まれているか否かを判定し、（１）前記計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれていないと判定したとき、前記交流トラヒック推定値ベクトルＴｏｕｔを出力部経由で出力し、（２）前記計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれていると判定したとき、前記交流トラヒック推定値ベクトルＴｏｕｔを初期値更新部へ出力する終了判定部と、
前記終了判定部から出力された前記交流トラヒック推定値ベクトルＴｏｕｔの推定値のうち、前記負の値となったフローの推定値を０に変更したベクトルを、新たな初期値ベクトルＴｉｎとして前記交流トラヒック計算部へ出力する初期値更新部と、
前記終了判定部から出力された交流トラヒック推定値ベクトルを出力する出力部とを備え、
前記交流トラヒック計算部は、
前記初期値更新部から出力された新たな初期値ベクトルＴｉｎを用いて、ＴｏｍｏＧｒａｖｉｔｙ法により、新たな前記交流トラヒック推定値ベクトルＴｏｕｔを計算することを特徴とする交流トラヒック推定装置。
【請求項２】
前記終了判定部は、
前記計算した交流トラヒック推定値ベクトルＴｏｕｔの中に負の推定値が含まれていないとき、その交流トラヒック推定値ベクトルＴｏｕｔの計算に用いた前記初期値ベクトルＴｉｎと、前記交流トラヒック推定値ベクトルＴｏｕｔとの差｜Ｔｉｎ−Ｔｏｕｔ｜を求め、その｜Ｔｉｎ−Ｔｏｕｔ｜が所定の閾値以下か否かを判定し、（１）前記｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値以下のとき、前記交流トラヒック推定値ベクトルＴｏｕｔを出力部経由で出力し、（２）前記｜Ｔｉｎ−Ｔｏｕｔ｜が、前記所定の閾値を超えるとき、前記交流トラヒック推定値ベクトルＴｏｕｔを前記初期値更新部へ出力し、
前記初期値更新部は、
前記終了判定部から出力された交流トラヒック推定値ベクトルＴｏｕｔを新たな初期値ベクトルＴｉｎとして、前記交流トラヒック計算部へ出力することを特徴とする請求項１に記載の交流トラヒック推定装置。
【請求項３】
前記初期値更新部は、
前記終了判定部から出力された前記交流トラヒック推定値ベクトルＴｏｕｔから、前記負の値となったフローの推定値を削除したベクトルを、新たな初期値ベクトルＴｉｎとして前記交流トラヒック計算部へ出力し、また、前記ルーティング情報から前記負の値となったフローの経路情報を削除したルーティング情報を前記交流トラヒック計算部へ出力し、
前記交流トラヒック計算部は、
前記初期値更新部から出力された前記新たな初期値ベクトルＴｉｎおよび前記ルーティング情報を用いて、新たな前記交流トラヒック推定値ベクトルＴｏｕｔを計算することを特徴とする請求項２に記載の交流トラヒック推定装置。
【請求項４】
ネットワーク内の交流トラヒックにおけるフローそれぞれが経路として用いるリンクを示したルーティング情報と、前記ネットワーク内のリンクそれぞれのリンクトラヒック量を示したリンクトラヒック情報とを用いて、前記フローそれぞれの推定値を計算する交流トラヒック推定装置による交流トラヒック推定方法であって、
前記交流トラヒック推定装置が、
前記ルーティング情報および前記リンクトラヒック情報の入力を受け付けるステップと、
前記リンクトラヒック情報を参照して、前記フローそれぞれの推定値の初期値を示した初期値ベクトルＴｉｎを計算するステップと、
前記ルーティング情報、前記リンクトラヒック情報および前記初期値ベクトルＴｉｎを用いて、前記フローそれぞれの推定値を示した交流トラヒック推定値ベクトルＴｏｕｔを計算するステップと、
（１）前記計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれていないとき、前記交流トラヒック推定値ベクトルＴｏｕｔを出力して処理を終了し、
（２）前記計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれているとき、前記交流トラヒック推定値ベクトルＴｏｕｔの推定値のうち、前記負の値となった推定値を０に変更して新たな初期値ベクトルＴｉｎを作成するステップと、
前記新たな初期値ベクトルＴｉｎを用いて、再度、前記交流トラヒック推定値ベクトルＴｏｕｔを計算するステップとを
前記計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれなくなるまで繰り返し実行することを特徴とする交流トラヒック推定方法。
【請求項５】
前記交流トラヒック推定装置は、
前記計算した交流トラヒック推定値ベクトルＴｏｕｔの中に負の推定値が含まれていないとき、
前記交流トラヒック推定値ベクトルＴｏｕｔと、その交流トラヒック推定値ベクトルＴｏｕｔの計算に用いた前記初期値ベクトルＴｉｎとの差｜Ｔｉｎ−Ｔｏｕｔ｜を計算し、
（１）前記｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値以下のとき、前記交流トラヒック推定値ベクトルＴｏｕｔを出力して処理を終了し、
（２）前記｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値を超えるとき、前記交流トラヒック推定値ベクトルＴｏｕｔの推定値を、前記新たな初期値ベクトルＴｉｎとするステップと、
前記新たな初期値ベクトルＴｉｎを用いて、再度、前記交流トラヒック推定値ベクトルＴｏｕｔを計算するステップとを
前記｜Ｔｉｎ−Ｔｏｕｔ｜が、前記所定の閾値以下となるまで繰り返し実行することを特徴とする請求項４に記載の交流トラヒック推定方法。
【請求項６】
請求項４または請求項５に記載の交流トラヒック推定方法をコンピュータである前記交流トラヒック推定装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ（Internet Protocol）網や、ＭＰＬＳ（Multiprotocol Label Switching）などのパケット交換網における交流トラヒックの推定技術に関する。
【背景技術】
【０００２】
ネットワーク事業者においては、ネットワークのトポロジおよび経路を最適化することで、ネットワーク全体の資源を有効に利用し、転送品質の維持、ネットワークコストの低減を図ることが重要である。このようにネットワークのトポロジおよび経路の設計を最適化するためには、ネットワークのトポロジや経路の情報に加えて、交流トラヒック（任意の２つのノード間のフロー）のトラヒック量の情報が必要である。一般的に、ネットワーク内に用いられる装置（ノード）には、NetFlow（登録商標）、sFlow（登録商標）（以下、XFlowと呼ぶ）等の技術が実装されており、フロー単位のトラヒック量の測定が可能である。しかし、この技術では、マイクロフロー単位の情報から交流トラヒックに加工するため、すべてのフローのトラヒック量を取得するにはスケール性に問題がある（非特許文献１参照）。この問題点を解決する方法として、交流トラヒック推定法が提案されている。この交流トラヒック推定技術では、ネットワークからの情報収集が容易なリンクトラヒック情報（ＩＦ（インタフェース）単位のトラヒック情報）に基づいて、より粒度を細かく各フローのトラヒック量を推定するため、スケール性が高い。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】N.Benameur and J.W.Roberts，“Traffic Matrix Inference in IP Networks“NETWORKS AND SPATIAL ECONOMICS，“VOL4；NUMBER 1，P.103−114，2004．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、前記した技術により推定した各フローのトラヒック量の値には、計算上は正しい値だが、実際には存在し得ない値（負の値）が含まれることがあり、推定精度が低いという問題がある。
【０００５】
このことを、図７〜図９を用いて説明する。図７は、ネットワークのトポロジとルーティング情報とを示す。トポロジは、ネットワーク内の各ノードが、どのリンクを用いてどのノードに接続されているかを示した情報である。ルーティング情報は、各トラヒック（フロー）の経由するリンクを示した情報である。各リンクのリンクトラヒック量は、すべて１００Ｍｂｐｓとする。図８，９に、図７のネットワークの交流トラヒック推定の計算例を示す。各リンクのリンクトラヒック量は、ベクトルＸとして表現され、ルーティング情報は行列Ａとして表現される。また、求めたい交流トラヒック量（交流トラヒックのフローそれぞれのトラヒック量）はベクトルＴとして表現される。
【０００６】
このとき、Ｘ＝Ａ＊Ｔの演算を連立方程式として表現したものを図８に示す。不確定の変数を含む式のみ抽出すると、４つの式と８個の変数からなる８元一次方程式が得られる。式は４つしかないため、交流トラヒック量を示すベクトルＴのＴ１、Ｔ２、Ｔ５、Ｔ６、Ｔ８、Ｔ９、Ｔ１０、Ｔ１２は複数の値を取り得る。ここで、交流トラヒック推定によって得られた値が、図９に示す推定値（１）とする。この推定値（１）は連立方程式の解となっており、計算上は正しい値が得られている。しかし、Ｔ１、Ｔ５、Ｔ９は負の値であり、実際には存在し得ない値である。また、真の値が図９に示す値であったとすると、Ｔ２、Ｔ８、Ｔ１０は過剰にトラヒック量を見積もられるため、実際のトラヒック量と比較して５０Ｍｂｐｓという大幅な推定誤差が発生していることが分かる。
【０００７】
そこで、本発明は、前記した問題を解決し、ネットワークの交流トラヒック量の推定値精度を向上させることを目的とする。
【課題を解決するための手段】
【０００８】
前記した課題を解決するため、請求項１に記載の発明は、ネットワーク内の交流トラヒックにおけるフローそれぞれが経路として用いるリンクを示したルーティング情報と、ネットワーク内のリンクそれぞれのリンクトラヒック量を示したリンクトラヒック情報とを用いて、フローそれぞれの推定値を計算する交流トラヒック推定装置であって、ルーティング情報およびリンクトラヒック情報の入力を受け付ける入力部と、ルーティング情報およびリンクトラヒック情報を記憶する記憶部と、リンクトラヒック情報を参照して、フローそれぞれの推定値の初期値を示した初期値ベクトルＴｉｎを計算する初期値計算部と、ルーティング情報、リンクトラヒック情報および初期値ベクトルＴｉｎを用いて、フローそれぞれの推定値を示した交流トラヒック推定値ベクトルＴｏｕｔを計算する交流トラヒック計算部と、交流トラヒック計算部により計算された交流トラヒック推定値ベクトルに負の推定値が含まれているか否かを判定し、（１）計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれていないと判定したとき、交流トラヒック推定値ベクトルＴｏｕｔを出力部経由で出力し、（２）計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれていると判定したとき、交流トラヒック推定値ベクトルＴｏｕｔを初期値更新部へ出力する終了判定部と、終了判定部から出力された交流トラヒック推定値ベクトルＴｏｕｔの推定値のうち、負の値となったフローの推定値を０に変更したベクトルを、新たな初期値ベクトルＴｉｎとして交流トラヒック計算部へ出力する初期値更新部と、終了判定部から出力された交流トラヒック推定値ベクトルを出力する出力部とを備え、交流トラヒック計算部は、初期値更新部から出力された新たな初期値ベクトルＴｉｎを用いて、ＴｏｍｏＧｒａｖｉｔｙ法により、新たな交流トラヒック推定値ベクトルＴｏｕｔを計算することを特徴とする。
【０００９】
請求項４に記載の発明は、ネットワーク内の交流トラヒックにおけるフローそれぞれが経路として用いるリンクを示したルーティング情報と、ネットワーク内のリンクそれぞれのリンクトラヒック量を示したリンクトラヒック情報とを用いて、フローそれぞれの推定値を計算する交流トラヒック推定装置による交流トラヒック推定方法であって、交流トラヒック推定装置が、ルーティング情報およびリンクトラヒック情報の入力を受け付けるステップと、リンクトラヒック情報を参照して、フローそれぞれの推定値の初期値を示した初期値ベクトルＴｉｎを計算するステップと、ルーティング情報、リンクトラヒック情報および初期値ベクトルＴｉｎを用いて、フローそれぞれの推定値を示した交流トラヒック推定値ベクトルＴｏｕｔを計算するステップと、（１）計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれていないとき、交流トラヒック推定値ベクトルＴｏｕｔを出力して処理を終了し、（２）計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれているとき、交流トラヒック推定値ベクトルＴｏｕｔの推定値のうち、負の値となった推定値を０に変更して新たな初期値ベクトルＴｉｎを作成するステップと、新たな初期値ベクトルＴｉｎを用いて、再度、交流トラヒック推定値ベクトルＴｏｕｔを計算するステップとを計算した交流トラヒック推定値ベクトルＴｏｕｔに負の推定値が含まれなくなるまで繰り返し実行することを特徴とする。
【００１０】
このように交流トラヒック推定装置は、交流トラヒック量の推定値（交流トラヒック推定値ベクトルＴｏｕｔ）を計算し、その値に負の値が含まれていたとき、その負の値となったフローの推定値を０に変更した初期値（初期値ベクトルＴｉｎ）を用いて、再度、交流トラヒック量の推定値を計算する処理を繰り返す。よって、交流トラヒック推定装置が最終的に出力する交流トラヒック量の推定値は負の値を含まないものとなるので、交流トラヒック量の推定精度を向上させることができる。なお、交流トラヒック量の推定値の計算は、例えば、ＴｏｍｏＧｒａｖｉｔｙ法（Yin Zhang,Matthew Roughan,Albert Greenberg,“Fast accurate computation of large-scale IP traffic matrices from link loads，”In ACM Sigmetrics,San Diego,CA,2003.）等により実行される。
【００１１】
請求項２に記載の発明は、請求項１に記載の交流トラヒック推定装置における終了判定部が、計算した交流トラヒック推定値ベクトルＴｏｕｔの中に負の推定値が含まれていないとき、その交流トラヒック推定値ベクトルＴｏｕｔの計算に用いた初期値ベクトルＴｉｎと、交流トラヒック推定値ベクトルＴｏｕｔとの差｜Ｔｉｎ−Ｔｏｕｔ｜を求め、その｜Ｔｉｎ−Ｔｏｕｔ｜が所定の閾値以下か否かを判定し、（１）｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値以下のとき、交流トラヒック推定値ベクトルＴｏｕｔを出力部経由で出力し、（２）｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値を超えるとき、交流トラヒック推定値ベクトルＴｏｕｔを初期値更新部へ出力し、初期値更新部は、終了判定部から出力された交流トラヒック推定値ベクトルＴｏｕｔを新たな初期値ベクトルＴｉｎとして、交流トラヒック計算部へ出力することを特徴とする。
【００１２】
また、請求項５に記載の発明は、請求項４に記載の交流トラヒック推定方法において、交流トラヒック推定装置が、計算した交流トラヒック推定値ベクトルＴｏｕｔの中に負の推定値が含まれていないとき、交流トラヒック推定値ベクトルＴｏｕｔと、その交流トラヒック推定値ベクトルＴｏｕｔの計算に用いた初期値ベクトルＴｉｎとの差｜Ｔｉｎ−Ｔｏｕｔ｜を計算し、（１）｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値以下のとき、交流トラヒック推定値ベクトルＴｏｕｔを出力して処理を終了し、（２）｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値を超えるとき、交流トラヒック推定値ベクトルＴｏｕｔの推定値を、新たな初期値ベクトルＴｉｎとするステップと、新たな初期値ベクトルＴｉｎを用いて、再度、交流トラヒック推定値ベクトルＴｏｕｔを計算するステップとを｜Ｔｉｎ−Ｔｏｕｔ｜が、所定の閾値以下となるまで繰り返し実行することを特徴とする。
【００１３】
このようにすることで、交流トラヒック推定装置は、交流トラヒック量の推定値に負の値が含まれず、かつ、その交流トラヒック量の計算に用いた初期値ベクトルＴｉｎとの差｜Ｔｉｎ−Ｔｏｕｔ｜が所定の閾値よりも小さいと判断したときに、交流トラヒック量の推定値を出力するので、交流トラヒック量の推定精度をより向上させることができる。
【００１４】
請求項３に記載の発明は、請求項２に記載の交流トラヒック推定装置における初期値更新部が、終了判定部から出力された交流トラヒック推定値ベクトルＴｏｕｔから、負の値となったフローの推定値を削除したベクトルを、新たな初期値ベクトルＴｉｎとして交流トラヒック計算部へ出力し、また、ルーティング情報から負の値となったフローの経路情報を削除したルーティング情報を交流トラヒック計算部へ出力し、交流トラヒック計算部は、初期値更新部から出力された新たな初期値ベクトルＴｉｎおよびルーティング情報を用いて、新たな交流トラヒック推定値ベクトルＴｏｕｔを計算することを特徴とする。
【００１５】
このようにすることで、交流トラヒック推定装置は、計算した交流トラヒック量の推定値から、その推定値が負の値となったフローの情報を削除する。つまり、交流トラヒック計算装置は、その推定値が負の値となったフローを計算対象から除外して、交流トラヒック量の推定値の計算処理を行う。よって、交流トラヒック計算装置は、必要以上に交流トラヒック量の推定値の計算処理を繰り返すことなく、精度の高い交流トラヒック量の推定値を求めることができる。
【００１６】
請求項６に記載の発明は、請求項４または請求項５に記載の交流トラヒック推定方法をコンピュータである交流トラヒック推定装置に実行させるためのプログラムとした。
【００１７】
このようなプログラムによれば、一般的なコンピュータに請求項４または請求項５に記載の交流トラヒック推定方法を実行させることができる。
【発明の効果】
【００１８】
本発明によれば、ネットワークの交流トラヒック量の推定精度を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１】本実施の形態の交流トラヒック推定装置を含むネットワークの構成例を示した図である。
【図２】図１の交流トラヒック推定装置の構成を示した図である。
【図３】図２の交流トラヒック推定装置の処理手順の概要を示した図である。
【図４】図２の交流トラヒック推定装置の計算例を示した図である。
【図５】図３の終了判定処理の具体例を示した図である。
【図６】図２の交流トラヒック推定装置の処理内容を概念的に示した図である。
【図７】ネットワークのトポロジとルーティング情報とを例示した図である。
【図８】図７のネットワークの交流トラヒック推定の計算例を示した図である。
【図９】図７のネットワークの交流トラヒック推定の計算例を示した図である。
【発明を実施するための形態】
【００２０】
以下、本発明を実施するための形態（以下、実施の形態とする）について説明する。まず、本実施の形態の交流トラヒック推定装置を含むネットワークの構成例を説明する。図１に示すように、ネットワークは、端末装置３０同士が通信を行うための通信ネットワーク４０と、通信ネットワーク４０のネットワーク情報（リンクトラヒック情報、ルーティング情報）を取得し、交流トラヒック量の推定値を計算する交流トラヒック推定装置１０とを含んで構成される。なお、通信ネットワーク４０は、端末装置３０から送信されたパケットを転送する複数のノード２０により構成される。このノード２０同士、および、ノード２０と端末装置３０とはリンクにより接続される。このノード２０は、例えば、ＩＰルータである。なお、以下の説明において、交流トラヒックとは、ネットワークにおける任意の端末装置３０間を流れるフローの集合を示すものとする。
【００２１】
次に、図２を用いて交流トラヒック推定装置１０の構成を説明する。交流トラヒック推定装置１０は、入力部１１と、ルーティング情報１３１と、リンクトラヒック情報１３２と、初期値計算部１２１と、交流トラヒック計算部１２２と、終了判定部１２３と、初期値更新部１２４と、出力部１４とを備える。
【００２２】
このうち、入力部１１は、交流トラヒック計算部１２２での交流トラヒック量の推定値計算に用いるルーティング情報１３１、リンクトラヒック情報１３２等の入力を受け付け、記憶部（図示省略）に記憶する。
【００２３】
ルーティング情報１３１は、通信ネットワーク４０内の交流トラヒックのフローごとに、そのフローが経由するリンク（またはノード２０）を示した情報である。このルーティング情報１３１は、例えば、図８の行列Ａのような情報である。
【００２４】
リンクトラヒック情報１３２は、通信ネットワーク４０内のリンクごとに、そのリンクのトラヒック量を示した情報である。このリンクトラヒック情報１３２は、例えば、図８のベクトルＸのような情報である。
【００２５】
初期値計算部１２１は、リンクトラヒック情報１３２を参照して、交流トラヒックのフローそれぞれの推定値の初期値を示した初期値ベクトルＴｉｎを計算する。なお、ここでの初期値ベクトルＴｉｎは、Ｇｒａｖｉｔｙ法等により計算される。
【００２６】
交流トラヒック計算部１２２は、初期値計算部１２１（または、初期値更新部１２４）により計算された交流トラヒック量の推定値の初期値ベクトルＴｉｎと、ルーティング情報１３１およびリンクトラヒック情報１３２とを用いて、交流トラヒック量の推定値である交流トラヒック推定値ベクトルＴｏｕｔを計算する。ここでの交流トラヒック推定値ベクトルＴは、ＴｏｍｏＧｒａｖｉｔｙ法等に基づき、以下の式（１）を満たすＴを求めることにより計算される。
リンクトラヒックベクトルＸ＝ルーティング行列Ａ×交流トラヒック推定値ベクトルＴ…式（１）
【００２７】
終了判定部１２３は、交流トラヒック計算部１２２により計算された交流トラヒック推定値ベクトルＴｏｕｔに、負の値が含まれているか否かを判定する。つまり、計算した結果、交流トラヒック推定値ベクトルＴｏｕｔの中に推定値が負の値になったフローがあるか否かを判定する。ここで、（１）交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれておらず、かつ、この交流トラヒック推定値ベクトルＴｏｕｔと、初期値ベクトルＴｉｎ（この交流トラヒック推定値ベクトルＴｏｕｔを計算するときに用いた初期値ベクトル）との差が所定の閾値以下であれば、終了判定部１２３は、この交流トラヒック推定値ベクトルＴｏｕｔを出力部１４経由で出力し、処理を終了する。一方、（２）交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていると判定したとき、または、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていないが、交流トラヒック推定値ベクトルＴｏｕｔと、初期値ベクトルＴｉｎとの差が所定の閾値を超えていると判定したとき、この交流トラヒック推定値ベクトルＴｏｕｔを初期値更新部１２４へ出力する。ここで、終了判定部１２３により、交流トラヒック推定値ベクトルＴｏｕｔと、初期値ベクトルＴｉｎとの差が所定の閾値を超えていると判定されたとき、この交流トラヒック推定値ベクトルＴｏｕｔを初期値更新部１２４へ出力することとしたのは、初期値ベクトルＴｉｎと交流トラヒック推定値ベクトルＴｏｕｔとの差が大きいということは、初期値ベクトルＴｉｎを更新して再計算すると、さらに交流トラヒック推定値ベクトルＴｏｕｔが大きく変動する可能性があるからである。つまり、交流トラヒック計算部１２２は、初期値更新部１２４により更新された初期値ベクトルＴｉｎを用いて交流トラヒック推定値ベクトルＴｏｕｔの再計算をすることで、さらに精度の高い交流トラヒック量の推定値を得られる可能性があるからである。この終了判定部１２３の判定処理の詳細は、後記する。
【００２８】
初期値更新部１２４は、終了判定部１２３から出力された交流トラヒック推定値ベクトルＴｏｕｔをもとに、この交流トラヒック計算部１２２で用いる新たな初期値ベクトルＴｉｎを作成する。具体的には、初期値更新部１２４は、終了判定部１２３から出力された交流トラヒック推定値ベクトルＴｏｕｔに負の値が存在すれば、その負の値をすべて「０」に変更した新たな初期値ベクトルＴｉｎを作成する。なお、交流トラヒック推定値ベクトルＴｏｕｔに負の値が存在しなければ、その交流トラヒック推定値ベクトルＴｏｕｔをそのまま新たな初期値ベクトルＴｉｎとする。そして、初期値更新部１２４は、この新たな初期値ベクトルＴｉｎを交流トラヒック計算部１２２へ出力する。その後、交流トラヒック計算部１２２は、この出力された新たな初期値ベクトルＴｉｎを用いて交流トラヒック推定値ベクトルＴｏｕｔを計算する。
【００２９】
例えば、最初に交流トラヒック計算部１２２が計算した交流トラヒック推定値ベクトルＴｏｕｔが、図４の推定値（１）に示す値であったとき、この交流トラヒック推定値ベクトルＴｏｕｔのＴ１，Ｔ５，Ｔ９の値は負の値であるので、初期値更新部１２４は、このＴ１，Ｔ５，Ｔ９の値を「０」とした初期値ベクトルＴｉｎを作成する。そして、交流トラヒック計算部１２２は、このＴ１，Ｔ５，Ｔ９の値を「０」とした初期値ベクトルＴｉｎを用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により交流トラヒック推定値ベクトルＴｏｕｔを計算すると、推定値（２）のような、真の値に近い交流トラヒック推定値ベクトルＴｏｕｔを得ることができる。つまり、交流トラヒックの推定精度の向上を図ることができる。
【００３０】
出力部１４は、終了判定部１２３から出力された交流トラヒック推定値ベクトルＴｏｕｔを外部装置等へ出力する。
【００３１】
この交流トラヒック計算装置１０は、コンピュータにより実現され、前記した入力部１１および出力部１４は、入出力インタフェースや通信インタフェースから構成される。また、初期値計算部１２１、交流トラヒック計算部１２２、終了判定部１２３、初期値更新部１２４は、この交流トラヒック推定装置１０の備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、この交流トラヒック推定装置１０の記憶部は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、交流トラヒック推定装置１０をプログラム実行処理により実現する場合、記憶部には、この交流トラヒック推定装置１０の機能を実現するためのプログラムが格納される。この交流トラヒック計算装置１０には、キーボードやマウス等の入力装置、液晶モニタ等の出力装置が接続されていてもよい。
【００３２】
次に、図２を参照しつつ、図３を用いて交流トラヒック推定装置１０の処理手順の概要を説明する。まず、交流トラヒック推定装置１０は入力部１１経由で、ルーティング情報１３１およびリンクトラヒック情報１３２の入力を受け付け（Ｓ１）、記憶部に記憶する。次に、初期値計算部１２１は、リンクトラヒック情報１３２を用いて、Ｇｒａｖｉｔｙ法等により交流トラヒック量の推定値の初期値を示した初期値ベクトルＴｉｎを作成する（Ｓ２：初期値計算）。そして、交流トラヒック計算部１２２は、この初期値ベクトルＴｉｎと、ルーティング情報１３１およびリンクトラヒック情報１３２とを用いて、交流トラヒック推定値ベクトルＴｏｕｔを計算する（Ｓ３：交流トラヒック推定）。次に、終了判定部１２３は、交流トラヒック計算部１２２により計算された交流トラヒック推定値ベクトルＴｏｕｔをもとに、処理を終了するか否かを判定する（Ｓ４）。ここで、終了判定部１２３は、（１）交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれておらず、かつ、この交流トラヒック推定値ベクトルＴｏｕｔと、初期値ベクトルＴｉｎ（この交流トラヒック推定値ベクトルＴｏｕｔを計算するときに用いた初期値ベクトル）との差が所定の閾値以下であれば、処理を終了すると判定し（Ｓ４の“終了”）、終了判定部１２３は、この交流トラヒック推定値ベクトルＴｏｕｔを出力部１４経由で出力し（Ｓ６：交流トラヒック推定値出力）、処理を終了する。
【００３３】
一方、Ｓ４で終了判定部１２３が、（２）交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていると判定したとき、または、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていないが、初期値ベクトルＴｉｎとの差が所定の閾値を超えていると判定したとき、まだ処理を終了しないと判定し（Ｓ４の“終了しない”）、この交流トラヒック推定値ベクトルＴｏｕｔを初期値更新部１２４へ出力する。
【００３４】
そして、初期値更新部１２４は、この終了判定部１２３から出力された交流トラヒック推定値ベクトルＴｏｕｔをもとに初期値ベクトルＴｉｎの更新処理を行う（Ｓ５：初期値更新）。つまり、初期値更新部１２４は、終了判定部１２３から出力された交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていれば、その負の値となったフローの推定値を「０」に変更し、新たな初期値ベクトルＴｉｎを作成する。また、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていなければ、その交流トラヒック推定値ベクトルＴｏｕｔをそのまま新たな初期値ベクトルＴｉｎとする。そして、初期値更新部１２４は、この新たな初期値ベクトルＴｉｎを交流トラヒック計算部１２２へ出力する。
【００３５】
この後、処理はＳ３へ戻り、交流トラヒック計算部１２２は、この更新された初期値ベクトルＴｉｎと、ルーティング情報１３１およびリンクトラヒック情報１３２とを用いて、再度、交流トラヒック推定値ベクトルＴｏｕｔを計算する。交流トラヒック推定装置１０は、以上のような処理を、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれておらず、かつ、この交流トラヒック推定値ベクトルＴｏｕｔと、初期値ベクトルＴｉｎ（この交流トラヒック推定値ベクトルＴｏｕｔを計算するときに用いた初期値ベクトル）との差が所定の閾値以下になるまで繰り返す。
【００３６】
このようにすることで、交流トラヒック推定装置１０は、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていた場合、初期値ベクトルＴｉｎを更新し、この更新した初期値ベクトルＴｉｎを用いて交流トラヒック推定値ベクトルＴｏｕｔの再計算を行う。よって、交流トラヒック量の推定値の計算精度を向上させることができる。
【００３７】
ここで、前記した処理を図６を用いて説明する。図６のグラフは、交流トラヒック推定装置１０が求める交流トラヒック推定値ベクトルＴｏｕｔの示す座標位置を示す。Ｘ＝Ａ＊Ｔ（前記した式（１）に相当）の示す解空間は、一点鎖線により規定される平面である。この交流トラヒック推定装置１０は、交流トラヒック量の推定値の初期値ベクトルＴｉｎの示す座標位置として、例えば、Ｇｒａｖｉｔｙ法の初期解Ｔｉｎ１を求める。そして、この初期解Ｔｉｎ１を用いて、ＴｏｍｏＧｒａｖｉｔｙ法等により、Ｘ＝Ａ＊Ｔを満たす１回目の推定値Ｔｏｕｔ１（交流トラヒック推定値ベクトルＴｏｕｔの座標位置）を求める。なお、ここで、１回目（Ｎ回目）の推定結果に、存在し得ない値があれば、この存在し得ない値を「０」に補正するが、その値は、その解空間（Ｘ＝Ａ＊Ｔ）からずれる。そして、交流トラヒック推定装置１０は、この補正結果を２回目（Ｎ＋１回目）の推定値の計算の初期値Ｔｉｎ２（初期値ベクトルＴｉｎの座標位置）として、Ｘ＝Ａ＊Ｔを満たす２回目の推定値Ｔｏｕｔ２（交流トラヒック推定値ベクトルＴｏｕｔの座標位置）を求める。同様に、推定値Ｔｏｕｔ２に負の値が含まれていれば、初期値Ｔｉｎ３を求め、その初期値Ｔｉｎ３を用いて、推定値Ｔｏｕｔ３を求める。このような処理を繰り返し、推定結果（推定値Ｔｏｕｔ）に存在し得ない値（負の値）が含まれず、かつ、Ｎ回目の初期値との差が所定の閾値以下になったら処理を終了する。
【００３８】
ここで、図３のＳ４における終了判定の具体例を、図５を用いて説明する。まず、終了判定部１２３は、各パラメータ（sumDiff（｜Ｔｉｎ−Ｔｏｕｔ｜の合計値、つまり、ＴｉｎとＴｏｕｔとでどれだけ変化があったか示す値）、sumTg（Ｔｉｎを構成するそれぞれの値の合計値）、diff（sumDiffをsumTgで割った値）、minus_flag(Ｔｏｕｔに負の値があるか否かを示すフラグ））を初期化する（Ｓ１１）。
【００３９】
次に、終了判定部１２３は、図３のＳ３で計算した交流トラヒック推定値（交流トラヒック推定値ベクトルＴｏｕｔ）に負の値があるか否かを判定する（Ｓ１２）。ここで、交流トラヒック推定値ベクトルＴｏｕｔに負の値がないと判定したとき（Ｓ１２のＮｏ）、minus_flag＝０（負の値なし）として、終了判定部１２３は、｜Ｔｉｎ−Ｔｏｕｔ｜の合計値（sumDiff）を計算する。そして、この｜Ｔｉｎ−Ｔｏｕｔ｜の合計値が所定の閾値以下か否かを判定する（Ｓ１３）。ここで、｜Ｔｉｎ−Ｔｏｕｔ｜の合計値が所定の閾値以下であれば（Ｓ１３のＹｅｓ）、終了すると判定し（Ｓ１４）、｜Ｔｉｎ−Ｔｏｕｔ｜の合計値が所定の閾値を超えていれば（Ｓ１３のＮｏ）、終了しないと判定する（Ｓ１５）。｜Ｔｉｎ−Ｔｏｕｔ｜の合計値が所定の閾値以下か否かの判定は、例えば、終了判定部１２３が、Ｔｉｎを構成するそれぞれの値の合計値sumTgを計算し、sumDiffをsumTgで割った値diffが所定の閾値以下か否かにより判定される。ここで、diffが所定の閾値以下のとき、終了すると判定し、sumDiffをsumTgで割った値diffが所定の閾値を超えているとき、終了しないと判定する。なお、Ｓ１２において、交流トラヒック推定値ベクトルＴｏｕｔに負の値があると判定したとき（Ｓ１２のＹｅｓ）、minus_flag＝１（負の値あり）として、Ｓ１５へ進む。
【００４０】
このようにすることで交流トラヒック推定装置１０は、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれている場合、初期値ベクトルＴｉｎを修正して再計算を行うので、交流トラヒック推定値の計算精度を向上させることができる。
【００４１】
なお、終了判定部１２３は、sumDiffをsumTgで割った値diffが所定の閾値以下か否かにより、終了判定を行うこととしたが、diffに代えてsumDiffそのものが所定の閾値以下か否かにより、終了判定を行うようにしてもよい。
【００４２】
また、終了判定部１２３が、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていると判定したとき、以下のような処理を行うようにしてもよい。すなわち、終了判定部１２３が、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていると判定したとき、初期値更新部１２４は、交流トラヒック推定値ベクトルＴｏｕｔにおける負の値のフローのトラヒック量を「０」で確定し、記憶部の所定領域に記憶しておく。そして、初期値更新部１２４は、交流トラヒック推定値ベクトルＴｏｕｔの負の値となったフロー（トラヒック量を「０」で確定したフロー）の情報を削除した初期値ベクトルＴｉｎを作成する。また、ルーティング情報１３１における、この負の値となったフローの情報も、ルーティング情報１３１から削除する。そして、交流トラヒック計算部１２２は、この更新された初期値ベクトルＴｉｎおよびルーティング情報１３１を用いて、交流トラヒック推定値ベクトルＴｏｕｔの計算をする。この後、終了判定部１２３において、交流トラヒック計算部１２２により計算された交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれていないと判定したとき、この交流トラヒック推定値ベクトルＴｏｕｔと、記憶部に記憶していおいたトラヒック量を「０」で確定したフローの情報（トラヒック量）の情報と合わせて、出力する。
【００４３】
このようにすることで、交流トラヒック計算部１２２は、前回の計算の結果、負の値となったフローについては、交流トラヒック推定値ベクトルＴｏｕｔの計算対象外とするので、交流トラヒック推定値ベクトルＴｏｕｔが決まりやすくなる。つまり、交流トラヒック計算部１２２は、少ない計算量で、精度の高い交流トラヒック推定値ベクトルＴｏｕｔを求めることができる。
【００４４】
また、前記した終了判定部１２３は、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれず、かつ、初期値ベクトルＴｉｎとの差が所定の閾値以下となったときに、交流トラヒック推定値ベクトルＴｏｕｔを出力することとしたが、これに限定されない。例えば、終了判定部１２３は、交流トラヒック推定値ベクトルＴｏｕｔに負の値が含まれなくなるか、または、初期値ベクトルＴｉｎとの差が所定の閾値以下となったときに、その交流トラヒック推定値ベクトルＴｏｕｔを出力するようにしてもよい。
【００４５】
なお、前記した実施の形態において、交流トラヒック推定装置１０は、初期値ベクトルＴｉｎと交流トラヒック推定値ベクトルＴｏｕｔとの差が所定の閾値を超えていたとき、初期値ベクトルＴｉｎの更新を行うこととしたが、前回計算した交流トラヒック推定値ベクトルＴｏｕｔとの差が所定の閾値を超えていたとき、初期値ベクトルＴｉｎの更新を行うようにしてもよい。
【００４６】
なお、交流トラヒック推定装置１０は、ネットワーク内のノード２０から各リンクのリンクトラヒック情報を収集し、リンクトラヒック情報１３２を作成する手段や、ネットワーク内のトポロジ情報を備え、各ノード２０から経路情報を取得し、ルーティング情報１３１を作成する手段を備えていてもよい。
【符号の説明】
【００４７】
１０    交流トラヒック推定装置
１１    入力部
１４    出力部
２０    ノード
３０    端末装置
４０    通信ネットワーク
１２１  初期値計算部
１２２  交流トラヒック計算部
１２３  終了判定部
１２４  初期値更新部
１３１  ルーティング情報
１３２  リンクトラヒック情報
【図１】
2010283701.tif 000003
【図２】
2010283701.tif 000004
【図３】
2010283701.tif 000005
【図４】
2010283701.tif 000006
【図５】
2010283701.tif 000007
【図６】
2010283701.tif 000008
【図７】
2010283701.tif 000009
【図８】
2010283701.tif 000010
【図９】
2010283701.tif 000011