JP4937191B2

JP4937191B2 - パケット遅延データ処理装置、パケット遅延データ処理方法及びプログラム

Info

Publication number: JP4937191B2
Application number: JP2008151729A
Authority: JP
Inventors: 篤男立花
Original assignee: KDDI Corp
Current assignee: KDDI Corp
Priority date: 2008-06-10
Filing date: 2008-06-10
Publication date: 2012-05-23
Anticipated expiration: 2028-06-10
Also published as: JP2009302643A

Description

本発明は、パケット遅延データ処理装置、パケット遅延データ処理方法及びプログラムに関する。

従来からＩＰ（ＩｎｔｅｒｎｅｔＰｒｏｔｏｃｏｌ）網において、エンドツーエンドのパケット遅延を計測する様々な手法が提案されている。例えば非特許文献１及び２に記載された技術では、計測されたパケット遅延データから、線形計画法や区分的最小値を利用して、キューイング遅延の影響を除去し、パケット遅延の変動を抽出している。
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及びｄはＮ＋Ｍ次元ベクトル、Ｃはベクトル、ＤはＮ×Ｎ対称行列である。
制約条件：Ａｂ＝Ｃ，Ａｂ≧Ｃ
目的関数：Ｚ＝−ｄ^Ｔｂ＋（１／２）ｂ^ＴＤｂ

まず、本実施形態における制約条件について説明する。各計測端末２の時刻のずれ（真の時刻に対してずれている時間）をＸ_ｋ（ｋ＝１，２，…，Ｎ）、各パスＰ_ｊの真のパケット遅延の固定成分をＸ_Ｎ＋ｊ（ｊ＝１，２，…，Ｍ）とすると、計算された平均値ａｖｅ_ｊを用いて、以下の制約条件１が成立する。ここで、パスＰ_ｊの送信端末はＮ_Ｓ、受信端末はＮ_ｒである。制約条件１は、「（真のパケット遅延）−（送信端末の時刻のずれ）＋（受信端末の時刻のずれ）」が「（測定されたパケット遅延）」に近い値になることである。
（制約条件１）Ｘ_Ｎ＋ｊ−Ｘ_ｓ＋Ｘ_ｒ≒ａｖｅ_ｊ

また、以下の制約条件２が成立する。制約条件２は、全てのパスＰ_ｊの真のパケット遅延の固定成分Ｘ_Ｎ＋ｊは非負になることである。
（制約条件２）Ｘ_Ｎ＋ｊ（ｊ＝１，２，…，Ｍ）≧０

さらに、特定のパスＰ_ｌの真のパケット遅延の固定成分Ｘ_Ｎ＋ｌに制約がある場合は以下の制約条件３が追加される。ｄｅｌａｙ１及びｄｅｌａｙ２は予め設定された定数である。
（制約条件３）Ｘ_Ｎ＋ｌ≧ｄｅｌａｙ１，Ｘ_Ｎ＋ｌ≦ｄｅｌａｙ２

制約条件１から３は一次連立方程式／不等式で表わされるため、ＡをＮ＋Ｍ列の係数行列、Ｃ＝［ａｖｅ_１，ａｖｅ_２，…，ａｖｅ_Ｍ，０，０，…，０，ｄｅｌａｙ１，…］とおくと、Ａｂ＝Ｃ，Ａｂ≧Ｃと表現できる。

次に目的関数の算出方法について説明する。まず、パケット遅延データ補正部１４は、全てのパスのパケット遅延データの低周波数成分の分散値ｄｉｓｐ_ｊを計算し、各計測端末２の不安定度Ｉ_ｋを算出する。不安定度Ｉ_ｋは、次の式（１）で算出される。式（１）は、不安程度Ｉ_ｋがＮ_ｋをパケットの送信端末または受信端末とするパスの分散値の平均値で定義されることを表わしている。

次に、計算した不安定度Ｉ_ｋを用いて目的関数Ｚを例えば以下の式（２）で定義する。δは予め設定された定数である。

すなわち、Ｄは次の式（３）、ｄは式（４）となる。

次に、パケット遅延データ補正部１４は、制約条件下で、定義した目的関数Ｚを最小化するＸ_ｋ（ｋ＝１，２，…，Ｎ）及びＸ_Ｎ＋ｊ（ｊ＝１，２，…，Ｍ）を非線形計画法により求める。パケット遅延データ補正部１４は、代表的な解法として、例えば逐次２次計画法などを適用する。その結果、不安程度Ｉ_ｋの高い計測端末２ほど時刻のずれ（の二乗）が大きく補正される。これにより真のパケット遅延の固定成分Ｘ_Ｎ＋ｊが算出される。このパケット遅延の固定成分Ｘ_Ｎ＋ｊがパケット遅延データの平均値ａｖｅ_ｊを最適化した値である。パケット遅延データ補正部１４は、この最適化したパケット遅延データの平均値ａｖｅ_ｊに高周波成分を加算して補正済みのパケット遅延データを算出する。

このように、本実施形態によれば、パケット遅延データをウェーブレット変換又はフーリエ変換して高周波成分と低周波成分に分解し、分解した低周波成分の平均値をパス毎に算出する。この低周波成分の平均値はパケット遅延の固定成分とすることができるため、パケット遅延の固定成分を線形補正することができる。これにより、線形補正を適用して精度の良い補正を行うことができる。また、高周波成分はパケット遅延の変動とすることができるため、パケット遅延データからパケット遅延変動を計算することができる。
また、制約条件を満たすか否かを判定し、満たさない場合には、制約条件を満たすように低周波数成分の平均値を非線形計画法により最適化する。非線形計画法を用いるため、各計測端末２の時刻のずれを補正したパケット遅延データに最適化することができる。これにより、時刻同期精度の低い端末間で計測した多地点間のパケット遅延データを補正することができる。

また、図３に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、パケット遅延データ補正処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。

さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。

以上、図面を参照してこの発明の一実施形態について詳しく説明してきたが、具体的な構成は上述のものに限られることはなく、この発明の要旨を逸脱しない範囲内において様々な設計変更等をすることが可能である。

本発明の一実施形態による遅延データ処理システムのネットワーク構成を示す概略図である。本実施形態におけるパケット遅延データ処理装置の構成を示すブロック図である。本実施形態におけるパケット遅延データ補正部の処理の一例を示したフローチャートである。本実施形態における非線形計画法によるパケット遅延の平均値最適化処理の概要を示した概略図である。

符号の説明

１…パケット遅延データ処理装置２…計測端末１１…制御部１２…記憶部１３…通信部１４…パケット遅延データ補正部

Claims

ネットワークに分散配置された複数の端末間のパケット遅延データを補正するパケット遅延データ処理装置であって、
前記端末間の各パスのパケット遅延データを記憶する記憶手段と、
前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解する分解手段と、
前記分解した低周波成分の平均値をパス毎に算出する算出手段と、
前記平均値に高周波成分を加算して補正後のパケット遅延データとする加算手段と、
を備えることを特徴とするパケット遅延データ処理装置。
所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化手段を備えることを特徴とする請求項１に記載のパケット遅延データ処理装置。
前記最適化手段は、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする請求項２に記載のパケット遅延データ処理装置。
端末間のパスのパケット遅延データを記憶する記憶手段を備え、ネットワークに分散配置された複数の端末間のパケット遅延データを補正するパケット遅延データ処理方法であって、
前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解するステップと、
前記低周波成分の平均値を算出するステップと、
前記平均値に高周波成分を加算して補正後のパケット遅延データとするステップと、
を有することを特徴とするパケット遅延データ処理方法。
所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化ステップを有することを特徴とする請求項４に記載のパケット遅延データ処理方法。
前記最適化ステップは、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする請求項５に記載のパケット遅延データ処理方法。
ネットワークに分散配置された複数の端末間のパケット遅延データを補正させるためのプログラムであって、
前記端末間のパスのパケット遅延データを記憶する記憶手段を備えるコンピュータに、
前記記憶手段に記憶されたパケット遅延データをフーリエ変換又はウェーブレット変換して高周波成分と低周波成分に分解するステップと、
前記低周波成分の平均値を算出するステップと、
前記平均値に高周波成分を加算して補正後のパケット遅延データとするステップと、
を実行させるためのプログラム。
所定の制約条件を満たすように全てのパスの前記低周波数成分の平均値を非線形計画法により最適化する最適化ステップを有することを特徴とする請求項７に記載のプログラム。
前記最適化ステップは、各端末のパケット遅延データの分散値に基づく各端末の不安定度を用いて定義される目的関数を使用することを特徴とする請求項８に記載のプログラム。