(57)【特許請求の範囲】
【請求項１】
ネットワークに分散配置された複数の端末間のパケット遅延データを補正するパケット遅延データ処理装置であって、
前記端末間の各パスのパケット遅延データを記憶する記憶手段と、
前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解する分解手段と、
前記分解した低周波成分の平均値をパス毎に算出する算出手段と、
前記平均値に高周波成分を加算して補正後のパケット遅延データとする加算手段と、
を備えることを特徴とするパケット遅延データ処理装置。
【請求項２】
所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化手段を備えることを特徴とする請求項１に記載のパケット遅延データ処理装置。
【請求項３】
前記最適化手段は、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする請求項２に記載のパケット遅延データ処理装置。
【請求項４】
端末間のパスのパケット遅延データを記憶する記憶手段を備え、ネットワークに分散配置された複数の端末間のパケット遅延データを補正するパケット遅延データ処理方法であって、
前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解するステップと、
前記低周波成分の平均値を算出するステップと、
前記平均値に高周波成分を加算して補正後のパケット遅延データとするステップと、
を有することを特徴とするパケット遅延データ処理方法。
【請求項５】
所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化ステップを有することを特徴とする請求項４に記載のパケット遅延データ処理方法。
【請求項６】
前記最適化ステップは、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする請求項５に記載のパケット遅延データ処理方法。
【請求項７】
ネットワークに分散配置された複数の端末間のパケット遅延データを補正させるためのプログラムであって、
前記端末間のパスのパケット遅延データを記憶する記憶手段を備えるコンピュータに、
前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解するステップと、
前記低周波成分の平均値を算出するステップと、
前記平均値に高周波成分を加算して補正後のパケット遅延データとするステップと、
を実行させるためのプログラム。
【請求項８】
所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化ステップを有することを特徴とする請求項７に記載のプログラム。
【請求項９】
前記最適化ステップは、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする請求項８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット遅延データ処理装置、パケット遅延データ処理方法及びプログラムに関する。
【背景技術】
【０００２】
従来からＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）網において、エンドツーエンドのパケット遅延を計測する様々な手法が提案されている。例えば非特許文献１及び２に記載された技術では、計測されたパケット遅延データから、線形計画法や区分的最小値を利用して、キューイング遅延の影響を除去し、パケット遅延の変動を抽出している。
【非特許文献１】V. Paxson, “On Calibrating Measurements of Packet Transit Timer.” In Proc. ACM SIGMETRICS 1998, pp.11-21, 1998.
【非特許文献２】S. B. Moon, P. Skelly and D. Towsley, “Estimation and Removal of Clock Skew from Network Delay Measurements.” In Proc. IEEE INFOCOM, pp.227-234, March 1999.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、非特許文献１及び２に記載された技術では、経路変更などに伴うパケット遅延データの不連続性などにより、パケット遅延データに対して線形補正が適用できない場合がある、という問題がある。また、パケット遅延を計測するためには、パケットの送信端末と受信端末の時刻が同期している必要がある。多地点間のパケット遅延データを計測する場合には、１端末の時刻のずれが多くのパスに影響を与えるため、全ての端末が時刻同期をしていなければ精度の高いパケット遅延データを得る事ができない。
本発明は上記の点に鑑みてなされたものであり、その目的は、経路変更などに伴う不連続性を有するパケット遅延データであっても、線形補正を適用して精度の良い補正が可能なパケット遅延データ処理装置、パケット遅延データ処理方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００４】
本発明は上記の課題を解決するためになされたものであり、本発明の一態様は、ネットワークに分散配置された複数の端末間のパケット遅延データを補正するパケット遅延データ処理装置であって、前記端末間の各パスのパケット遅延データを記憶する記憶手段と、前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解する分解手段と、前記分解した低周波成分の平均値をパス毎に算出する算出手段と、前記平均値に高周波成分を加算して補正後のパケット遅延データとする加算手段と、を備えることを特徴とするパケット遅延データ処理装置である。
【０００５】
また、本発明の一態様は、上記のパケット遅延データ処理装置において、所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化手段を備えることを特徴とする。
【０００６】
また、本発明の一態様は、上記のパケット遅延データ処理装置において、前記最適化手段は、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする。
【０００７】
また、本発明の一態様は、端末間のパスのパケット遅延データを記憶する記憶手段を備え、ネットワークに分散配置された複数の端末間のパケット遅延データを補正するパケット遅延データ処理方法であって、前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解するステップと、前記低周波成分の平均値を算出するステップと、前記平均値に高周波成分を加算して補正後のパケット遅延データとするステップと、を有することを特徴とするパケット遅延データ処理方法である。
【０００８】
また、本発明の一態様は、上記のパケット遅延データ処理方法において、所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化ステップを有することを特徴とする。
【０００９】
また、本発明の一態様は、上記のパケット遅延データ処理方法において、前記最適化ステップは、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする。
【００１０】
また、本発明の一態様は、ネットワークに分散配置された複数の端末間のパケット遅延データを補正させるためのプログラムであって、前記端末間のパスのパケット遅延データを記憶する記憶手段を備えるコンピュータに、前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解するステップと、前記低周波成分の平均値を算出するステップと、前記平均値に高周波成分を加算して補正後のパケット遅延データとするステップと、を実行させるためのプログラムである。
【００１１】
また、本発明の一態様は、上記のプログラムにおいて、所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化ステップを有することを特徴とする。
【００１２】
前記最適化ステップは、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、パケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解し、分解した低周波成分の平均値をパス毎に算出する。この低周波成分の平均値はパケット遅延の固定成分とすることができるため、パケット遅延の固定成分を線形補正することができる。これにより、線形補正を適用して精度の良い補正を行うことができる。また、高周波成分はパケット遅延の変動とすることができるため、パケット遅延データからパケット遅延変動を計算することができる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照しながら本発明の実施形態について詳しく説明する。
図１は、本発明の一実施形態によるパケット遅延データ処理システムのネットワーク構成を示す概略図である。
パケット遅延データ処理システムは、パケット遅延データ処理装置１と、パケット遅延データの補正対象となるネットワークに接続されている複数の計測端末２と、を含んで構成される。複数の計測端末２はネットワークを介して相互に接続されている。また、各計測端末２とパケット遅延データ処理装置１は例えばインターネットなどを介して通信可能である。本実施形態では、Ｎ台の計測端末２間のＭ本のパスＰｊ（ｊ＝１，２，・・・，Ｍ）でパケット遅延を計測する。
【００１５】
各計測端末２は、受信したパケットのパケット遅延データを生成し、生成したパケット遅延データをパケット遅延データ処理装置１に送信する。パケット遅延データは、パケットの遅延時間を表わすデータであり、計測端末２がパケットを受信した時刻とパケットに埋め込まれた送信時刻との差から生成される。パケット遅延データ処理装置１は、各計測端末２から受信したパケット遅延データを補正する。
【００１６】
図２は、本実施形態におけるパケット遅延データ処理装置１の構成を示すブロック図である。
パケット遅延データ処理装置１は、パケット遅延データ処理装置１を統括して制御する制御部１１と、各計測端末２から受信したパケット遅延データを記憶する記憶部１２と、各計測端末２と通信を行う通信部１３と、記憶部１２に記憶されたパケット遅延データを補正するパケット遅延データ補正部１４と、を含んで構成される。
【００１７】
図３は、本実施形態におけるパケット遅延データ補正部１４の処理の一例を示したフローチャートである。
まず、ステップＳ１では、パケット遅延データ補正部１４は、記憶部１２に記憶されているパケット遅延データを取得する。
次のステップＳ２では、パケット遅延データ補正部１４は、取得したパケット遅延データをウェーブレット変換あるいはフーリエ変換により高周波成分と低周波成分に分解する。具体的には、フーリエ変換の結果得られる周波数成分の低周波域または高周波域の一方を減算処理し、逆フーリエ変換／逆ウェーブレット変換することにより、それぞれ高周波成分と低周波成分のパケット遅延データを取得する。このとき、抽出した高周波成分はパケット遅延変動として近似することができる。
次のステップＳ３では、パケット遅延データ補正部１４は、各パスＰｊの低周波成分の平均値ａｖｅｊ（ｊ＝１，２，…，Ｍ）及び分散値ｄｉｓｐｊ（ｊ＝１，２，…，Ｍ）を算出する。ここで、各計測端末２が時刻同期している場合には、十分に長時間のパケット遅延データから算出される平均値ａｖｅｊは、パケット遅延の固定成分に近似することができる。
【００１８】
なお、経路変更などに伴うパケット遅延データの不連続性などが発生する場合があるが、十分に長時間の計測を行うことにより、一時的な経路変更の影響を少なくすることができる。あるいは、短時間の計測を行う場合には、パケット遅延データの低周波成分の変化に基づいて経路変更があったパケット遅延データを補正対象から除外する。又、同一経路でグループ化して補正処理することができる。
【００１９】
次のステップＳ４では、パケット遅延データ補正部１４は、算出した全ての平均値ａｖｅｊが予め設定された制約条件を満足しているか否かを判定する。制約条件は、全てのパスにおいて、「ａｖｅｊ＞０」であることである。また、更に、特定のパスの平均値ａｖｅｌの範囲を制約条件として指定することも可能である。例えば、パスＰｌが光通信をしておりパスＰｌの両端となる計測端末２が１０００Ｋｍ離れた距離に設置されている場合には、光ファイバの伝送遅延特性などにより、「ａｖｅｌ＞２０ｍｓ」などの制約条件を追加指定する。制約条件を満足している場合には、ステップＳ６へ進む。一方、制約条件を満足していない場合には、ステップＳ５へ進む。
【００２０】
ステップＳ５では、パケット遅延データ補正部１４は、非線形計画法によりパケット遅延データの平均値ａｖｅｊを最適化する。この非線形計画法による処理の詳細については後述する。
次のステップＳ６では、パケット遅延データ補正部１４は、計算したパケット遅延データの平均値ａｖｅｊに高周波成分を加算し、その値を補正済みのパケット遅延データとして処理を終了する。
【００２１】
図４は、本実施形態における非線形計画法によるパケット遅延の平均値最適化処理の概要を示した概略図である。
非線形計画法によるパケット遅延の平均値最適化処理は、上記ステップＳ５でパケット遅延データ補正部１４により実行される。
図４には、時刻にずれがある複数の計測端末２（ノードＮ１，ノードＮ２，ノードＮ３）間のパス（Ｐ１，Ｐ２，Ｐ３）における真のパケット遅延と、各計測端末２が計測したパケット遅延の計測結果（パケット遅延データ）が示されている。真のパケット遅延とは、パケットが送信端末から送信されてから受信端末に受信されるまでの時間である。図４に示す例では、ノードＮ１からノードＮ３へのパスＰ１の真のパケット遅延は４ｍｓだが計測結果は−１２ｍｓである。また、ノードＮ２からノードＮ１へのパスＰ２の真のパケット遅延は１０ｍｓだが計測結果は９ｍｓである。また、ノードＮ２からノードＮ３へのパスＰ３の真のパケット遅延は３ｍｓだが計測結果は−８ｍｓである。これは、ノードＮ１は＋２ｍｓ、ノードＮ２は＋１ｍｓ、ノードＮ３は−１０ｍｓ、真の時刻に対して時刻がずれているためである。パスＰ１及びパスＰ３では計測結果が０より小さくなっているため、上述した制約条件「ａｖｅｊ＞０」を満たしていない。このため、パケット遅延データからノードＮ１，ノードＮ２及びノードＮ３が時刻同期していないことがわかる。そこで、パケット遅延データ補正部１４は、パケット遅延データを真のパケット遅延に近づけるための最適化を行う。
【００２２】
次に、最適化に用いる非線形計画問題について説明する。一般的に非線形計画問題は以下の制約条件下において目的関数Ｚの最小化を図る問題である。非線形計画問題には多数の解法アルゴリズムが提案されている。ここで、ＡはＮ×Ｍ行列、b及びｄはＮ＋Ｍ次元ベクトル、Ｃはベクトル、ＤはＮ×Ｎ対称行列である。
制約条件：Ａｂ＝Ｃ，Ａｂ≧Ｃ
目的関数：Ｚ＝−ｄＴｂ＋（１／２）ｂＴＤｂ
【００２３】
まず、本実施形態における制約条件について説明する。各計測端末２の時刻のずれ（真の時刻に対してずれている時間）をＸｋ（ｋ＝１，２，…，Ｎ）、各パスＰｊの真のパケット遅延の固定成分をＸＮ＋ｊ（ｊ＝１，２，…，Ｍ）とすると、計算された平均値ａｖｅｊを用いて、以下の制約条件１が成立する。ここで、パスＰｊの送信端末はＮＳ、受信端末はＮｒである。制約条件１は、「（真のパケット遅延）−（送信端末の時刻のずれ）＋（受信端末の時刻のずれ）」が「（測定されたパケット遅延）」に近い値になることである。
（制約条件１）ＸＮ＋ｊ−Ｘｓ＋Ｘｒ≒ａｖｅｊ
【００２４】
また、以下の制約条件２が成立する。制約条件２は、全てのパスＰｊの真のパケット遅延の固定成分ＸＮ＋ｊは非負になることである。
（制約条件２）ＸＮ＋ｊ（ｊ＝１，２，…，Ｍ）≧０
【００２５】
さらに、特定のパスＰｌの真のパケット遅延の固定成分ＸＮ＋ｌに制約がある場合は以下の制約条件３が追加される。ｄｅｌａｙ１及びｄｅｌａｙ２は予め設定された定数である。
（制約条件３）ＸＮ＋ｌ≧ｄｅｌａｙ１，ＸＮ＋ｌ≦ｄｅｌａｙ２
【００２６】
制約条件１から３は一次連立方程式／不等式で表わされるため、ＡをＮ＋Ｍ列の係数行列、Ｃ＝［ａｖｅ１，ａｖｅ２，…，ａｖｅＭ，０，０，…，０，ｄｅｌａｙ１，…］とおくと、Ａｂ＝Ｃ，Ａｂ≧Ｃと表現できる。
【００２７】
次に目的関数の算出方法について説明する。まず、パケット遅延データ補正部１４は、全てのパスのパケット遅延データの低周波数成分の分散値ｄｉｓｐｊを計算し、各計測端末２の不安定度Ｉｋを算出する。不安定度Ｉｋは、次の式（１）で算出される。式（１）は、不安程度ＩｋがＮｋをパケットの送信端末または受信端末とするパスの分散値の平均値で定義されることを表わしている。
【００２８】
【数１】
0004937191.tif 000002
【００２９】
次に、計算した不安定度Ｉｋを用いて目的関数Ｚを例えば以下の式（２）で定義する。δは予め設定された定数である。
【００３０】
【数２】
0004937191.tif 000003
【００３１】
すなわち、Ｄは次の式（３）、ｄは式（４）となる。
【００３２】
【数３】
0004937191.tif 000004
【００３３】
【数４】
0004937191.tif 000005
【００３４】
次に、パケット遅延データ補正部１４は、制約条件下で、定義した目的関数Ｚを最小化するＸｋ（ｋ＝１，２，…，Ｎ）及びＸＮ＋ｊ（ｊ＝１，２，…，Ｍ）を非線形計画法により求める。パケット遅延データ補正部１４は、代表的な解法として、例えば逐次２次計画法などを適用する。その結果、不安程度Ｉｋの高い計測端末２ほど時刻のずれ（の二乗）が大きく補正される。これにより真のパケット遅延の固定成分ＸＮ＋ｊが算出される。このパケット遅延の固定成分ＸＮ＋ｊがパケット遅延データの平均値ａｖｅｊを最適化した値である。パケット遅延データ補正部１４は、この最適化したパケット遅延データの平均値ａｖｅｊに高周波成分を加算して補正済みのパケット遅延データを算出する。
【００３５】
このように、本実施形態によれば、パケット遅延データをウェーブレット変換又はフーリエ変換して高周波成分と低周波成分に分解し、分解した低周波成分の平均値をパス毎に算出する。この低周波成分の平均値はパケット遅延の固定成分とすることができるため、パケット遅延の固定成分を線形補正することができる。これにより、線形補正を適用して精度の良い補正を行うことができる。また、高周波成分はパケット遅延の変動とすることができるため、パケット遅延データからパケット遅延変動を計算することができる。
また、制約条件を満たすか否かを判定し、満たさない場合には、制約条件を満たすように低周波数成分の平均値を非線形計画法により最適化する。非線形計画法を用いるため、各計測端末２の時刻のずれを補正したパケット遅延データに最適化することができる。これにより、時刻同期精度の低い端末間で計測した多地点間のパケット遅延データを補正することができる。
【００３６】
また、図３に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、パケット遅延データ補正処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００３７】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００３８】
以上、図面を参照してこの発明の一実施形態について詳しく説明してきたが、具体的な構成は上述のものに限られることはなく、この発明の要旨を逸脱しない範囲内において様々な設計変更等をすることが可能である。
【図面の簡単な説明】
【００３９】
【図１】本発明の一実施形態による遅延データ処理システムのネットワーク構成を示す概略図である。
【図２】本実施形態におけるパケット遅延データ処理装置の構成を示すブロック図である。
【図３】本実施形態におけるパケット遅延データ補正部の処理の一例を示したフローチャートである。
【図４】本実施形態における非線形計画法によるパケット遅延の平均値最適化処理の概要を示した概略図である。
【符号の説明】
【００４０】
１…パケット遅延データ処理装置  ２…計測端末  １１…制御部  １２…記憶部  １３…通信部  １４…パケット遅延データ補正部
【図１】
0004937191.tif 000006
【図２】
0004937191.tif 000007
【図３】
0004937191.tif 000008
【図４】
0004937191.tif 000009