図面 (/)

技術 交流トラヒック計算装置、交流トラヒック計算システム、交流トラヒック計算方法およびそのプログラム

出願人 日本電信電話株式会社
発明者 宮村崇塩本公平井上一郎
出願日 2008年11月28日 (12年1ヶ月経過) 出願番号 2008-304261
公開日 2010年6月10日 (10年6ヶ月経過) 公開番号 2010-130467
状態 特許登録済
技術分野 広域データ交換
主要キーワード 計算指示 出力トラヒック 収集タイミング 発側ノード 転送品質 ネットワークコスト 種指示入力 擬似逆行列
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2010年6月10日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (6)

課題

TomoGravity法により通信ネットワーク内交流トラヒック量推定値を計算するときの、計算時間を短縮する。

解決手段

交流トラヒック計算装置10は、通信ネットワーク40内のIF単位トラヒック情報131および経路情報132を収集し、経路情報132を示す行列Aの擬似逆行列pinv(A)を計算しておく。ここで、経路情報132の変更がないとき(つまり、通信ネットワークのトポロジに変更がないとき)、予め計算しておいた擬似逆行列pinv(A)を用いて交流トラヒック量の推定値tを計算する。一方、経路情報132の変更があったとき(つまり、通信ネットワークのトポロジに変更があったとき)、この変更された経路情報132をもとに擬似逆行列pinv(A)を再計算し、交流トラヒック計算装置10は、この再計算された擬似逆行列pinv(A)を用いて交流トラヒック量の推定値tを計算する。

概要

背景

ネットワークにおいて、ネットワークトポロジおよび経路を最適化することで、ネットワーク全体の資源を有効活用し、転送品質の維持、ネットワークコストの低減を図ることが重要である。このようなネットワークのトポロジおよび経路を最適化するためには、ネットワークのトポロジや経路の情報に加えて、任意の2つのノード間のトラヒック量である交流トラヒック量の情報が必要である。従来、ネットワーク内のノードにNetFlow(登録商標)や、sFLOW(登録商標)等のxFlowを実装することで、フロー(ネットワーク内の任意の2つのノードを始点・終点とするフロー)単位のトラヒック量の測定が可能である。しかし、このフロー単位のトラヒック量をネットワーク内のすべてのノード間について計測しようとすると、長時間を要し、実用的ではない(非特許文献1参照)。

このような問題点を解決する方法として、ネットワークからの情報収集負荷が比較的低い各ノードのインタフェース単位の入出力トラヒック量(IF単位トラヒック量)をもとに、重力モデル等を用いて交流トラヒック量(各ノード間の往復のトラヒック量)を推定する交流トラヒック推定法が提案されている(非特許文献2参照)。

この交流トラヒック推定法において、交流トラヒック量の推定値は、以下の式(1)に示すベクトルtを計算することで求められる。なお、式(1)におけるxは、インタフェース単位トラヒック情報に示される各インタフェース(IF)のトラヒック量を示すベクトルであり、Aは、経路情報を示す行列ルーティング行列)である。式(4)は、IFの数が3、フローの数も3である場合の式(1)の例を示した式である。

ここで、一般的な通信ネットワークでは、インタフェースの数よりもフロー数の方が多いため、前記した式(1)の方程式の解を一意に決定できない。そこで、まず、IF単位トラヒック情報から、重力モデルに従って、交流トラヒック量の推定値の初期値tgを計算する。そして、この初期値tgと、前記した式(1)の交流トラヒック量の推定値tとの最小二乗誤差が最小となる交流トラヒック量の推定値tを見つけ、その推定値tを交流トラヒック量の推定値とするTomoGravity法が提案されている(非特許文献3参照)。

この交流トラヒック量の推定値tを求めるためには、この推定値tと、交流トラヒック量の推定値の初期値tgとの最小二乗誤差の最小化するような、式(1)のルーティング行列Aの擬似逆行列pinv(A)を計算し、この擬似逆行列pinv(A)とIF単位トラヒック量xとを乗算する必要がある。つまり、交流トラヒック量の推定値tを求める以下の式(2)を計算する必要がある。
t=pinv(A)x…式(2)
N.Benameur and J.W.Roberts,"Traffic Matrix Inference in IP Networks ," Networks and Spatial Economics Volume 4, Number 1 ,p103-114 ,2004年3月
Y.Ohsita,et al. ,"Estimation of current traffic matrices from long-term traffic variations,"Broadnets2008, 2008年9月
Y.Zhang et al.,"Fast,accurate computation of large-scale IP traffic matrics from link measurements",ACMSGMETRICS 2003年

概要

TomoGravity法により通信ネットワーク内の交流トラヒック量の推定値を計算するときの、計算時間を短縮する。交流トラヒック計算装置10は、通信ネットワーク40内のIF単位トラヒック情報131および経路情報132を収集し、経路情報132を示す行列Aの擬似逆行列pinv(A)を計算しておく。ここで、経路情報132の変更がないとき(つまり、通信ネットワークのトポロジに変更がないとき)、予め計算しておいた擬似逆行列pinv(A)を用いて交流トラヒック量の推定値tを計算する。一方、経路情報132の変更があったとき(つまり、通信ネットワークのトポロジに変更があったとき)、この変更された経路情報132をもとに擬似逆行列pinv(A)を再計算し、交流トラヒック計算装置10は、この再計算された擬似逆行列pinv(A)を用いて交流トラヒック量の推定値tを計算する。

目的

しかし、前記したTomoGravity法による交流トラヒック量の推定における経路情報を示す行列Aの擬似逆行列pinv(A)の計算には、この行列Aの特異値分解等を行う必要がある。この行列の特異値分解は、行列のサイズが大きくなると、計算時間が莫大になり、計算負荷が大きい。一般的には、交流トラヒック量の計算装置は、ネットワーク内のIF単位トラヒック量および経路情報を収集し、その収集したIF単位トラヒック量および経路情報をもとに交流トラヒック量の推定値を計算する。ここで、IF単位トラヒック情報はネットワーク内のトラヒック量の変化に応じて、頻繁に変更される可能性がある。よって、IF単位トラヒック情報の変更のたびに、計算装置が、行列Aの擬似逆行列pinv(A)を計算し、交流トラヒック量の推定値を計算したのでは、推定値の計算に時間を要する。そこで、本発明は、前記した課題を解決し、通信ネットワーク内の交流トラヒック量の推定値の計算時間を短縮することを目的とする。

効果

実績

技術文献被引用数
2件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

TomoGravity法により、ネットワークの任意の2つのノード間におけるフロートラヒック量である交流トラヒック量推定値を計算する交流トラヒック計算装置であって、前記ネットワークを構成する各ノードのインタフェース識別情報ごとに、そのインタフェースへの入力トラヒックまたは出力トラヒックのトラヒック量を示したインタフェース単位トラヒック情報と、前記ネットワークを流れるフローごとに、そのフローの始点ノードおよび終点ノードの識別情報と、そのフローにおける始点ノードおよび終点ノード間において経由するインタフェースの識別情報とを示した経路情報とを前記ネットワークのノードから収集し、記憶部へ記憶する情報収集部と、前記インタフェース単位トラヒック情報と、前記経路情報と、予め計算された以下の式(1)を満たす行列Aの擬似逆行列pinv(A)を記憶する記憶部と、x=At…式(1)x:前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルA:前記経路情報を示される各フローの経由するインタフェースの情報を示す行列t:交流トラヒック量の推定値を示すベクトル前記記憶部から読み出した前記擬似逆行列pinv(A)と、前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxを、以下の式(2)に代入し、前記交流トラヒック量の推定値であるベクトルtを計算する交流トラヒック量計算部とを備えることを特徴とする交流トラヒック計算装置。t=pinv(A)x…式(2)

請求項2

前記交流トラヒック計算装置は、前記記憶部における経路情報を参照して、この経路情報に変更があったか否かを判断する再計算判定部と、前記再計算判定部により、前記経路情報に変更があったと判断されたとき、この変更された経路情報の行列Aを用いて、前記式(1)を満たす、前記擬似逆行列pinv(A)を再計算し、この再計算した擬似逆行列pinv(A)を前記記憶部に記憶する擬似逆行列計算部とを備え、前記交流トラヒック量計算部は、前記再計算された擬似逆行列pinv(A)と、前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、前記式(2)に代入し、前記交流トラヒック量の推定値であるベクトルtを計算することを特徴とする請求項1に記載のトラヒック計算装置

請求項3

前記交流トラヒック量計算部は、前記経路情報および前記インタフェース単位トラヒック情報を用いて、Gravity法により、前記交流トラヒック量の推定値の初期値tgを計算し、この計算した初期値tgと、前記再計算された擬似逆行列pinv(A)と、前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、以下の式(3)に代入し、前記交流トラヒック量の推定値であるベクトルtを計算することを特徴とする請求項1または請求項2に記載のトラヒック計算装置。t=pinv(A)(x−Atg)+tg…式(3)

請求項4

請求項1ないし請求項3のいずれか1項に記載の交流トラヒック計算装置と、前記通信ネットワーク内の経路情報およびインタフェース単位トラヒック情報を収集し、この収集した経路情報およびインタフェース単位トラヒック情報を、前記交流トラヒック計算装置からの要求に応じて、送信するノードとを含むことを特徴とする交流トラヒック計算システム

請求項5

TomoGravity法により、ネットワークの任意の2つのノード間におけるフローのトラヒック量である交流トラヒック量の推定値を計算する交流トラヒック計算装置が、前記ネットワークを構成する各ノードのインタフェースの識別情報ごとに、そのインタフェースへの入力トラヒックまたは出力トラヒックのトラヒック量を示したインタフェース単位トラヒック情報と、前記ネットワークを流れるフローごとに、そのフローの始点ノードおよび終点ノードの識別情報と、そのフローにおける始点ノードおよび終点ノード間において経由するインタフェースの識別情報とを示した経路情報とを前記ネットワークのノードから収集し、記憶部へ記憶するステップと、前記経路情報を参照して、この経路情報に変更がなかったと判断したとき、前記記憶部から、予め計算された以下の式(1)を満たす行列Aの擬似逆行列pinv(A)と、前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、以下の式(2)に代入し、前記交流トラヒック量の推定値であるベクトルtを計算するステップとを実行する交流トラヒック計算方法。x=At…式(1)t=pinv(A)x…式(2)x:前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルA:前記経路情報を示される各フローの経由するインタフェースの情報を示す行列t:交流トラヒック量の推定値を示すベクトル

請求項6

前記交流トラヒック計算装置は、前記経路情報を参照して、この経路情報に変更があったと判断したとき、この変更された経路情報の行列Aを用いて、前記式(1)を満たす、前記擬似逆行列pinv(A)を再計算するステップと、この再計算した擬似逆行列pinv(A)と、前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、前記式(2)に代入し、前記交流トラヒック量の推定値であるベクトルtを計算するステップとを実行する請求項5に記載の交流トラヒック計算方法。

請求項7

前記交流トラヒック計算装置は、前記交流トラヒック量の推定値であるベクトルtを計算するステップにおいて、前記経路情報および前記インタフェース単位トラヒック情報を用いて、Gravity法により、前記交流トラヒック量の推定値の初期値tgを計算し、この計算した初期値tgと、前記再計算された擬似逆行列pinv(A)と、前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、以下の式(3)に代入し、前記交流トラヒック量の推定値であるベクトルtを計算することを特徴とする請求項5または請求項6に記載の交流トラヒック計算方法。t=pinv(A)(x−Atg)+tg…式(3)

請求項8

請求項5ないし請求項7のいずれか1項に記載の交流トラヒック計算方法を、コンピュータである前記交流トラヒック計算装置に実行させるためのプログラム

技術分野

0001

本発明は、IP(Internet Protocol)やMPLS(Multi-Protocol Label Switching)等の通信ネットワークにおける交流トラヒック量の計算技術に関する。

背景技術

0002

ネットワークにおいて、ネットワークトポロジおよび経路を最適化することで、ネットワーク全体の資源を有効活用し、転送品質の維持、ネットワークコストの低減を図ることが重要である。このようなネットワークのトポロジおよび経路を最適化するためには、ネットワークのトポロジや経路の情報に加えて、任意の2つのノード間のトラヒック量である交流トラヒック量の情報が必要である。従来、ネットワーク内のノードにNetFlow(登録商標)や、sFLOW(登録商標)等のxFlowを実装することで、フロー(ネットワーク内の任意の2つのノードを始点・終点とするフロー)単位のトラヒック量の測定が可能である。しかし、このフロー単位のトラヒック量をネットワーク内のすべてのノード間について計測しようとすると、長時間を要し、実用的ではない(非特許文献1参照)。

0003

このような問題点を解決する方法として、ネットワークからの情報収集負荷が比較的低い各ノードのインタフェース単位の入出力トラヒック量(IF単位トラヒック量)をもとに、重力モデル等を用いて交流トラヒック量(各ノード間の往復のトラヒック量)を推定する交流トラヒック推定法が提案されている(非特許文献2参照)。

0004

この交流トラヒック推定法において、交流トラヒック量の推定値は、以下の式(1)に示すベクトルtを計算することで求められる。なお、式(1)におけるxは、インタフェース単位トラヒック情報に示される各インタフェース(IF)のトラヒック量を示すベクトルであり、Aは、経路情報を示す行列ルーティング行列)である。式(4)は、IFの数が3、フローの数も3である場合の式(1)の例を示した式である。

0005

ここで、一般的な通信ネットワークでは、インタフェースの数よりもフロー数の方が多いため、前記した式(1)の方程式の解を一意に決定できない。そこで、まず、IF単位トラヒック情報から、重力モデルに従って、交流トラヒック量の推定値の初期値tgを計算する。そして、この初期値tgと、前記した式(1)の交流トラヒック量の推定値tとの最小二乗誤差が最小となる交流トラヒック量の推定値tを見つけ、その推定値tを交流トラヒック量の推定値とするTomoGravity法が提案されている(非特許文献3参照)。

0006

この交流トラヒック量の推定値tを求めるためには、この推定値tと、交流トラヒック量の推定値の初期値tgとの最小二乗誤差の最小化するような、式(1)のルーティング行列Aの擬似逆行列pinv(A)を計算し、この擬似逆行列pinv(A)とIF単位トラヒック量xとを乗算する必要がある。つまり、交流トラヒック量の推定値tを求める以下の式(2)を計算する必要がある。
t=pinv(A)x…式(2)
N.Benameur and J.W.Roberts,"Traffic Matrix Inference in IP Networks ," Networks and Spatial Economics Volume 4, Number 1 ,p103-114 ,2004年3月
Y.Ohsita,et al. ,"Estimation of current traffic matrices from long-term traffic variations,"Broadnets2008, 2008年9月
Y.Zhang et al.,"Fast,accurate computation of large-scale IP traffic matrics from link measurements",ACMSGMETRICS 2003年

発明が解決しようとする課題

0007

しかし、前記したTomoGravity法による交流トラヒック量の推定における経路情報を示す行列Aの擬似逆行列pinv(A)の計算には、この行列Aの特異値分解等を行う必要がある。この行列の特異値分解は、行列のサイズが大きくなると、計算時間が莫大になり、計算負荷が大きい。一般的には、交流トラヒック量の計算装置は、ネットワーク内のIF単位トラヒック量および経路情報を収集し、その収集したIF単位トラヒック量および経路情報をもとに交流トラヒック量の推定値を計算する。ここで、IF単位トラヒック情報はネットワーク内のトラヒック量の変化に応じて、頻繁に変更される可能性がある。よって、IF単位トラヒック情報の変更のたびに、計算装置が、行列Aの擬似逆行列pinv(A)を計算し、交流トラヒック量の推定値を計算したのでは、推定値の計算に時間を要する。そこで、本発明は、前記した課題を解決し、通信ネットワーク内の交流トラヒック量の推定値の計算時間を短縮することを目的とする。

課題を解決するための手段

0008

前記した課題を解決するため請求項1に記載の発明は、TomoGravity法により、ネットワークの任意の2つのノード間におけるフローのトラヒック量である交流トラヒック量の推定値を計算する交流トラヒック計算装置であって、ネットワークを構成する各ノードのインタフェースの識別情報ごとに、そのインタフェースの入出力トラヒック量を示したインタフェース単位トラヒック情報と、ネットワークを流れるフローごとに、そのフローの始点ノードおよび終点ノードの識別情報と、そのフローにおける始点ノードおよび終点ノード間において経由するインタフェースの識別情報とを示した経路情報とをネットワークのノードから収集し、記憶部へ記憶する情報収集部と、インタフェース単位トラヒック情報と、経路情報と、予め計算された以下の式(1)を満たす行列Aの擬似逆行列pinv(A)を記憶する記憶部と、
x=At…式(1)
x:インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトル
A:経路情報を示される各フローの経由するインタフェースの情報を示す行列
t:交流トラヒック量の推定値を示すベクトル
記憶部から読み出した擬似逆行列pinv(A)と、インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxを、以下の式(2)に代入し、交流トラヒック量の推定値であるベクトルtを計算する交流トラヒック量計算部とを備えることを特徴とする。
t=pinv(A)x…式(2)

0009

請求項5に記載の発明は、TomoGravity法により、ネットワークの任意の2つのノード間におけるフローのトラヒック量である交流トラヒック量の推定値を計算する交流トラヒック計算装置が、ネットワークを構成する各ノードのインタフェースの識別情報ごとに、そのインタフェースの入出力トラヒック量を示したインタフェース単位トラヒック情報と、ネットワークを流れるフローごとに、そのフローの始点ノードおよび終点ノードの識別情報と、そのフローにおける始点ノードおよび終点ノード間において経由するインタフェースの識別情報とを示した経路情報とをネットワークのノードから収集し、記憶部へ記憶するステップと、経路情報を参照して、この経路情報に変更がなかったと判断したとき、記憶部から、予め計算された以下の式(1)を満たす行列Aの擬似逆行列pinv(A)と、インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、以下の式(2)に代入し、交流トラヒック量の推定値であるベクトルtを計算するステップを実行する交流トラヒック計算方法とした。
x=At…式(1)
t=pinv(A)x…式(2)
x:前記インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトル
A:前記経路情報を示される各フローの経由するインタフェースの情報を示す行列
t:交流トラヒック量の推定値を示すベクトル

0010

このようにすることで、交流トラヒック計算装置は、TomoGravity法により通信ネットワークの交流トラヒック量の推定値を計算するとき、予め計算しておいた行列A(経路情報を示す行列)の擬似逆行列pinv(A)を用いて計算するので、計算時間を短縮することができる。

0011

請求項2に記載の発明は、請求項1に記載のトラヒック計算装置における交流トラヒック計算装置が、記憶部における経路情報を参照して、この経路情報に変更があったか否かを判断する再計算判定部と、再計算判定部により、経路情報に変更があったと判断されたとき、この変更された経路情報の行列Aを用いて、式(1)を満たす、擬似逆行列pinv(A)を再計算し、この再計算した擬似逆行列pinv(A)を記憶部に記憶する擬似逆行列計算部とを備え、交流トラヒック量計算部は、再計算された擬似逆行列pinv(A)と、インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、式(2)に代入し、交流トラヒック量の推定値であるベクトルtを計算することを特徴とする。

0012

請求項6に記載の発明は、請求項5に記載の交流トラヒック計算方法において、交流トラヒック計算装置が、経路情報を参照して、この経路情報に変更があったと判断したとき、この変更された経路情報の行列Aを用いて、式(1)を満たす、擬似逆行列pinv(A)を再計算するステップと、この再計算した擬似逆行列pinv(A)と、インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、式(2)に代入し、交流トラヒック量の推定値であるベクトルtを計算するステップとを実行することを特徴とする。

0013

このようにすることで、交流トラヒック計算装置は、通信ネットワークの設定変更やノードやリンク故障により経路情報の変更があった場合、この変更された経路情報の行列Aの擬似逆行列pinv(A)を再計算する。そして、この再計算された擬似逆行列pinv(A)を用いて交流トラヒック量の推定値を計算する。よって、交流トラヒック計算装置は、経路情報が変更された場合でも、正確に交流トラヒック量の推定値を計算できる。つまり、交流トラヒック計算装置は、経路情報が変更されていないときは、予め計算しておいた擬似逆行列pinv(A)を用いて交流トラヒック量の推定値を計算し、経路情報が変更されていたときには、この擬似逆行列pinv(A)を再計算して交流トラヒック量の推定値を計算する。よって、交流トラヒック量の推定値の計算のたびに、擬似逆行列pinv(A)を計算する必要がなくなるので、交流トラヒック量の推定値を正確に計算しつつ、全体として計算時間を短縮できる。なお、インタフェース単位トラヒック情報に比べ、経路情報の更新頻度は極めて少ないと考えられるので、本発明の適用効果は高いと考えられる。

0014

請求項3に記載の発明は、請求項1または請求項2に記載のトラヒック計算装置において、交流トラヒック量計算部が、経路情報およびインタフェース単位トラヒック情報を用いて、Gravity法により、交流トラヒック量の推定値の初期値tgを計算し、この計算した初期値tgと、再計算された擬似逆行列pinv(A)と、インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、以下の式(3)に代入し、交流トラヒック量の推定値であるベクトルtを計算することを特徴とする。
t=pinv(A)(x−Atg)+tg…式(3)

0015

請求項7に記載の発明は、請求項5または請求項6に記載の交流トラヒック計算方法において、交流トラヒック計算装置が、交流トラヒック量の推定値であるベクトルtを計算するステップにおいて、経路情報およびインタフェース単位トラヒック情報を用いて、Gravity法により、交流トラヒック量の推定値の初期値tgを計算し、この計算した初期値tgと、再計算された擬似逆行列pinv(A)と、インタフェース単位トラヒック情報に示される各インタフェースのトラヒック量を示すベクトルxとを、以下の式(3)に代入し、交流トラヒック量の推定値であるベクトルtを計算することを特徴とする。
t=pinv(A)(x−Atg)+tg…式(3)

0016

このようにすることで、交流トラヒック計算装置は、交流トラヒック量の推定値を計算するとき、Gravity法により計算した交流トラヒック量の初期値tgを用いて計算するので、推定精度を向上させることができる。

0017

請求項4に記載の発明は、請求項1ないし請求項3のいずれか1項に記載の交流トラヒック計算装置と、通信ネットワーク内の経路情報およびインタフェース単位トラヒック情報を収集し、この収集した経路情報およびインタフェース単位トラヒック情報を、交流トラヒック計算装置からの要求に応じて、送信するノードとを含むことを特徴とする交流トラヒック計算システムとした。

0018

このようにすることで、請求項1ないし請求項3のいずれか1項に記載された交流トラヒック計算装置を含むシステムを実現できる。

0019

請求項8に記載の発明は、請求項5ないし請求項7のいずれか1項に記載の交流トラヒック計算方法を、コンピュータである前記交流トラヒック計算装置に実行させるためのプログラムとした。

0020

このようなプログラムによれば、請求項5ないし請求項7のいずれか1項に記載の交流トラヒック計算方法を、一般的なコンピュータに実行させることができる。

発明の効果

0021

本発明によれば、通信ネットワーク内の交流トラヒック量の計算時間を低減することができる。

発明を実施するための最良の形態

0022

概要
以下、本発明を実施するための最良の形態(以下、実施の形態という)について説明する。まず、図1および図2を用いて、本実施の形態の交流トラヒック計算装置による交流トラヒック量の推定値の計算処理の概要を説明する。図1および図2は、本実施の形態の交流トラヒック計算装置による交流トラヒック量の推定値の計算処理の概要を概念的に説明した図である。

0023

ここで、交流トラヒック計算装置は、前記したTomoGravity法により、図1に示す通信ネットワーク(ネットワーク)40内の任意の2つのノード20(20A,20B,20C,20D)間の交流トラヒック量の推定値tを計算する場合を例に説明する。この推定値tは、通信ネットワーク40のフローごとの交流トラヒック量の推定値tmの集合であり、ベクトルとして表現される。IF(インタフェース)単位トラヒック情報131は、通信ネットワーク40内の各ノード20のインタフェース単位の入出力トラヒック量を示した情報である。経路情報132は、通信ネットワーク40内のフローごとに、そのフローの発側(始点)ノードおよび着側(終点)ノードの識別情報、そのフローにおいて経由するノード20のインタフェースの識別情報をその経由順に示した情報である。つまり、経路情報132は、通信ネットワーク40におけるトポロジと、そのトポロジ上の各フローについて、そのフローが経由するリンクを、そのリンクの両端となるインタフェースの識別情報により記述した情報である。

0024

ここで交流トラヒック計算装置は、前記した交流トラヒック量の推定値tを求める場合、以下の式(1)を満たす、推定値tを求めればよい。
x=At…式(1)
A:経路情報132を示される各フローの経由するインタフェースの情報を示す行列(ルーティング行列)
t:交流トラヒック量の推定値を示すベクトル
x:IF単位トラヒック情報131に示される各インタフェースのトラヒック量を示すベクトル

0025

よって、交流トラヒック計算装置は、図2に示すように、TomoGravity法により、この交流トラヒック量の推定値tを求めるため、以下の式(2)を満たす擬似逆行列pinv(A)を計算すればよい。
t=pinv(A)x…式(2)

0026

ここで、IF単位トラヒック量xは、比較的常時変化するが、擬似逆行列pinv(A)のもととなる行列A(ルーティング行列A)は、ルーティングが変化したときに変化するものである。よって、交流トラヒック計算装置は、図2に示すように、(1)ルーティング行列Aに変化がないときには、予め計算しておいた擬似逆行列pinv(A)を用いて、式(2)に基づく交流トラヒック量の推定値tの計算を行う。一方、(2)ルーティング行列Aに変化があったときには、その変化を反映したルーティング行列(変更されたルーティング行列A)を用いて、擬似逆行列pinv(A)を計算する。そして、この計算した擬似逆行列pinv(A)を用いて交流トラヒック量の推定値tの計算を行う。

0027

このようにすることで、交流トラヒック計算装置は、この交流トラヒック量の推定値tを計算するとき、ルーティングの変化がないときには擬似逆行列pinv(A)を計算する必要がなくなるので、計算時間を短縮できる。

0028

<構成>
ここで、交流トラヒック計算装置を含むシステム(交流トラヒック計算システム)の構成例を説明する。図3は、本実施の形態の交流トラヒック計算装置を含むシステムの構成例を示した図である。

0029

図3に示すように、通信ネットワーク40は端末装置30同士のデータ通信を行うためのネットワークであり、複数のノード20を含んで構成される。この通信ネットワーク40は、例えば、IP(Internet Protocol)網やMPLS(Multi-Protocol Label Switching)網であり、ノード20はIPルータやMPLS用のルータである。交流トラヒック計算装置10は、ノード20から通信ネットワーク40内の経路情報132やIF単位トラヒック情報131を取得し、通信ネットワーク40の任意の2つのノード20間の交流トラヒック量の推定値を計算する。

0030

このような交流トラヒック計算装置10の構成を、図4を用いて説明する。図4は、図3の交流トラヒック計算装置の構成を示した図である。

0031

図4に示すように、交流トラヒック計算装置10の機能は大きく、入出力部11、処理部12および記憶部13に分けられる。入出力部11は、通信ネットワーク40のIF単位トラヒック情報131や経路情報132等の入力を受け付ける。処理部12は、この交流トラヒック計算装置10全体の制御を司り、ここでは主に交流トラヒック量の推定値の計算を行う。記憶部13は、交流トラヒック量の推定値の計算処理時に参照される、IF単位トラヒック情報131や経路情報132等を記憶する。入出力部11は、通信ネットワーク40との通信インタフェースや、外部装置とのデータ入出力を行うため入出力インタフェースから構成される。また、処理部12は、この交流トラヒック計算装置10が備えるCPU(Central Processing Unit)によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部13は、RAM(Random Access Memory)、ROM(Read Only Memory)、HDD(Hard Disk Drive)、フラッシュメモリ等の記憶媒体から構成される。なお、交流トラヒック計算装置10をプログラム実行処理により実現する場合、記憶部13には、この交流トラヒック計算装置10の機能を実現するためのプログラムが格納される。なお、この交流トラヒック計算装置10には、この交流トラヒック計算装置10へ各種指示入力を行うためのキーボードマウス等の入力装置や、交流トラヒック計算装置10の記憶部13に記憶された各種情報を出力する液晶モニタ等の出力装置等が接続されていてもよい。

0032

処理部12は、情報収集部121と、交流トラヒック計算部122と、再計算判定部123と、擬似逆行列計算部124と、交流トラヒック出力部125とを備える。

0033

情報収集部121は、入出力部11経由で図3の通信ネットワーク40のノード20から、各ノード20のIF単位トラヒック情報131および通信ネットワーク40の経路情報132を収集する。収集したIF単位トラヒック情報131および経路情報132は記憶部13に記憶する。なお、このIF単位トラヒック情報131および経路情報132の収集は、定期的に行ってもよいし、不定期に行ってもよい。また、IF単位トラヒック情報131および経路情報132の収集タイミングは、同じでもよいし、異なっていてもよい。

0034

交流トラヒック計算部122は、記憶部13から読み出した擬似逆行列133(擬似逆行列pinv(A))と、IF単位トラヒック情報131に示される各インタフェースのトラヒック量を示すベクトルxを、前記した式(2)に代入し、交流トラヒック量の推定値であるベクトルtを計算する。

0035

ここで交流トラヒック計算部122は、経路情報132が変更されていた場合には、式(2)に、この変更された経路情報132をもとに計算された擬似逆行列pinv(A)を用いて交流トラヒック量の推定値であるベクトルtを計算する。一方、経路情報132が変更されていなかった場合には、交流トラヒック計算部122は、式(2)に、記憶部13に記憶された擬似逆行列133(擬似逆行列pinv(A))を代入して交流トラヒック量の推定値であるベクトルtを計算する。

0036

再計算判定部123は、記憶部13の経路情報132の変更の有無を監視し、経路情報132に変更があったとき、擬似逆行列計算部124による擬似逆行列pinv(A)の再計算が必要と判断する。一方、記憶部13の経路情報132に変更がなかった場合、擬似逆行列計算部124による擬似逆行列pinv(A)の再計算は不要と判断する。

0037

擬似逆行列計算部124は、再計算判定部123により、擬似逆行列pinv(A)の再計算が必要と判断されたとき(つまり、経路情報132に変更があったとき)、前記した式(1)に示す方程式を満たす行列Aの特異値分解等を行い、擬似逆行列pinv(A)を求める。求めた擬似逆行列pinv(A)は、記憶部13の擬似逆行列133として記憶しておく。

0038

交流トラヒック出力部125は、交流トラヒック計算部122により計算された交流トラヒック量の推定値tを記憶部13へ出力したり、入出力部11経由で外部装置へ出力したりする。

0039

記憶部13は、IF単位トラヒック情報131と、経路情報132と、擬似逆行列133と、交流トラヒック情報134とを記憶する。

0040

IF単位トラヒック情報131(図1参照)は、前記したとおり、通信ネットワーク40内の各ノード20のインタフェース単位の入出力トラヒック量を示した情報である。また、経路情報132(図1参照)は、通信ネットワーク40内のフローごとに、そのフローの発側ノードおよび着側ノードの識別情報、そのフローにおいて経由するノード20のインタフェースの識別情報をその経由順に示した情報である。これらの情報は、情報収集部121により収集される。なお、経路情報132は、過去に収集した経路情報132も記憶し、再計算判定部123は、最新の経路情報132と過去(前回)収集された経路情報132とを比較して、その経路情報132に変更があったか否かを判断する。

0041

擬似逆行列133は、擬似逆行列計算部124により計算された擬似逆行列pinv(A)である。この擬似逆行列pinv(A)は、交流トラヒック計算部122が、前記した式(2)に基づき、交流トラヒック量の推定値tを計算するときに用いられる。この擬似逆行列133は、擬似逆行列計算部124が計算を行うたびに最新の値に書き換えられる。

0042

処理手順
次に、図4を参照しつつ、図5を用いて、交流トラヒック計算装置10の処理手順を説明する。図5は、図4の交流トラヒック計算装置の処理手順を示したフローチャートである。

0043

まず、交流トラヒック計算装置10の情報収集部121は、所定期間ごとに通信ネットワーク40(図1参照)のIF単位トラヒック情報131と経路情報132とを収集する(S11)。収集したIF単位トラヒック情報131と経路情報132は記憶部13に記憶しておく。

0044

ここで、擬似逆行列計算部124は、情報収集部121により最初に収集された経路情報132について、1回目の擬似逆行列pinv(A)の計算を行う(S12)。そして、その計算結果(擬似逆行列pinv(A))を、擬似逆行列133として記憶部13に記憶しておく。

0045

この後、交流トラヒック計算装置10は、外部装置等からの交流トラヒック量の推定値tの計算指示の入力を受け付けると(S13のYes)、再計算判定部123は、記憶部13の経路情報132に変更があるか否かを判断する(S14)。一方、交流トラヒック量の推定値tの計算指示の入力を受け付けがなければ(S13のNo)、計算指示の入力を待つ。ここで、経路情報132に変更があれば(S14のYes)、再計算判定部123は、擬似逆行列計算部124による擬似逆行列pinv(A)の再計算が必要と判断する。そして、擬似逆行列計算部124は、この変更された経路情報132に基づき、擬似逆行列pinv(A)の再計算を行う(S15)。そして、この擬似逆行列pinv(A)を擬似逆行列133として記憶部13に記憶し、S16へ進む。一方、記憶部13の経路情報132に変更がなければ(S14のNo)、そのままS16へ進む。

0046

交流トラヒック計算部122は、記憶部13に記憶された擬似逆行列133と、記憶部13に記憶された最新のIF単位トラヒック情報131とを用いて交流トラヒック量の推定値tを計算する(S16)。そして、交流トラヒック出力部125は、この計算した交流トラヒック量の推定値tを出力する(S17)。例えば、交流トラヒック出力部125は、この計算した交流トラヒック量の推定値tを記憶部13の交流トラヒック情報134として記憶する。そして、S13へ戻り、再度交流トラヒック量の推定値tの計算指示が入力されるのを待つ。

0047

このようにすることで交流トラヒック計算装置10は、交流トラヒック量の推定値tの計算のたびに、行列A(経路情報132を示す行列)擬似逆行列pinv(A)を計算する必要がなくなるので、全体として交流トラヒック量の推定値tの計算時間を短縮できる。

0048

なお、前記した実施の形態において、交流トラヒック計算装置10の交流トラヒック計算部122は、通信ネットワーク40の交流トラヒック量の推定値であるベクトルtを計算するとき、経路情報132およびIF単位トラヒック情報131を用いて、Gravity法(非特許文献2参照)により、交流トラヒック量の推定値の初期値tgを計算する。そして、この初期値tgを用いて以下の式(3)により、交流トラヒック量の推定値であるベクトルtを計算するようにしてもよい。
t=pinv(A)(x−Atg)+tg…式(3)
このようにすることで、交流トラヒック計算装置10は、交流トラヒック量の推定精度を向上させることができる。

0049

本実施の形態に係る交流トラヒック計算装置10は、前記したような処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体CD−ROM等)に記憶して提供することが可能である。

図面の簡単な説明

0050

本実施の形態の交流トラヒック計算装置による交流トラヒック量の推定値の計算処理の概要を概念的に説明した図である。
本実施の形態の交流トラヒック計算装置による交流トラヒック量の推定値の計算処理の概要を概念的に説明した図である。
本実施の形態の交流トラヒック計算装置を含むシステムの構成例を示した図である。
図3の交流トラヒック計算装置の構成を示した図である。
図4の交流トラヒック計算装置の処理手順を示したフローチャートである。

符号の説明

0051

10交流トラヒック計算装置
11入出力部
12 処理部
13 記憶部
20ノード
30端末装置
40通信ネットワーク
121情報収集部
122交流トラヒック計算部
123 再計算判定部
124擬似逆行列計算部
125 交流トラヒック出力部
131 IF(インタフェース)単位トラヒック情報
132経路情報
133 擬似逆行列
134 交流トラヒック情報

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ