JP5815376B2 - 遅延推定装置、遅延推定方法、及び遅延推定プログラム - Google Patents

Description

本発明は、遅延推定装置、遅延推定方法、及び遅延推定プログラムに関する。

ＮＧＮ（Ｎｅｘｔ Ｇｅｎｅｒａｔｉｏｎ Ｎｅｔｗｏｒｋ；次世代ネットワーク）におけるＩＰ電話サービスや地上波デジタル放送のＩＰネットワークにおける再放送（映像配信サービス）等、ＩＰネットワークにおいて様々なサービスが提供されている。ＩＰネットワークの通信品質の低下は、音声や画像の乱れ等を引き起こし、サービス品質の低下をもたらすことから、ネットワーク全体の通信品質を把握し、管理することが重要となる。
ＩＰネットワークの通信品質を示すパラメータの１つとして、例えば、非特許文献１に記載のパケットの遅延時間がある。遅延時間を測定するためには、例えば非特許文献２のようなプローブ装置をＩＰネットワーク内に複数配置し、各プローブ装置においてパケットの通過時刻を測定し、通過時刻の差を計算することでプローブ間の通信品質の遅延を測定することが一般的である。

ITU-T Recommendation Y.1540, [online],[2011/06/06 検索], インターネット＜URL：http://www.itu.int/itu-t/recommendations/rec.aspx?id=9270＞ QoS モニタシステム Gigabit QoS プローブ IQ2000, 横河技報 Vol.49 No.2（ 2005 ）, [online], [2011/07/21 検索], インターネット＜ URL ： http://www.yokogawa.co.jp/rd/pdf/tr/rd-tr-r04902-007.pdf＞

しかしながら、このような装置を利用して測定する場合、測定したい区間の両端にプローブ装置を配置する必要がある。ネットワーク内の任意の区間を測定するためには非常に多くの装置を配置する必要があった。

本発明は上記の点に鑑みてなされたものであり、プローブ装置を配置することなく、ネットワーク内の任意のパケット転送装置間の往復遅延時間を測定することができる遅延推定装置、遅延推定方法、及び遅延推定プログラムを提供する。

（１）本発明は上記の課題を解決するためになされたものであり、本発明の一態様は、第１のパケット転送装置から第２のパケット転送装置へ伝送される第１のフローのうち第ｉ個目（ただしｉは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−１の時刻と、前記第１のフローのうち第ｊ個目（ただしｊは、２以上の整数でｉより大きい）のパケットが前記第２のパケット転送装置を通過する第２−１の時刻と、前記第１のフローのうち第ｋ個目（ただしｋは、３以上の整数でｉ及びｊより大きい）のパケットが前記第１のパケット転送装置を通過する第３−１の時刻と、前記第１のフローのうち第ｌ個目（ただしｌは、４以上の整数でｉ、ｊ、及びｋより大きい）のパケットが前記第２のパケット転送装置を通過する第４−１の時刻とを用いて、前記第１のパケット転送装置を前記第ｊ個目のパケットが通過した前記第１のフローの第１の基準時刻を第１−１の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｋ個目のパケットが通過した前記第１のフローの第２の基準時刻を第２−１の基準時刻として算出し、前記第２のパケット転送装置から前記第１のパケット転送装置へ伝送される第２のフローのうち第ｍ個目（ただしｍは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−２の時刻と、前記第２のフローのうち第ｎ個目（ただしｎは、２以上の整数でｍより大きい）のパケットが前記第２のパケット転送装置を通過する第２−２の時刻と、前記第２のフローのうち第ｏ個目（ただしｏは、３以上の整数でｍ及びｎより大きい）のパケットが前記第１のパケット転送装置を通過する第３−２の時刻と、前記第２のフローのうち第ｐ個目（ただしｐは、４以上の整数でｍ、ｎ、及びｏより大きい）のパケットが前記第２のパケット転送装置を通過する第４−２の時刻とを用いて、前記第１のパケット転送装置を前記第ｎ個目のパケットが通過した前記第２のフローの前記第１の基準時刻を第１−２の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｏ個目のパケットが通過した前記第２のフローの前記第２の基準時刻を第２−２の基準時刻として算出する時刻算出部と、算出された前記第１−１の基準時刻と、前記第１−２の基準時刻と、前記第２−１の基準時刻と、前記第２−２の基準時刻とともに、前記第２−１の時刻と、前記第２−２の時刻と、前記第３−１の時刻と、前記第３−２の時刻と、を用いて、前記第１のパケット転送装置と前記第２のパケット転送装置の間の往復遅延を推定する往復遅延算出部と、を備えることを特徴とする遅延推定装置である。

（２）また、本発明の一態様は、上記の往復遅延推定装置において、前記時刻算出部は、前記第２のパケット転送装置を前記第２−１の時刻に通過した前記第１のフローのパケット数から、前記第１のパケット転送装置を前記第１−１の時刻に通過した前記第１のフローのパケット数を減算した値を、前記第１のパケット転送装置を前記第１−１の時刻から前記第３−１の時刻の間に通過した前記第１のフローのパケット数で除算した値に、前記第１−１の時刻と前記第３−１の時刻との差を乗じて、当該乗算を行った結果に前記第１−１の時刻を加算して前記第１−１の基準時刻を算出し、前記第１のパケット転送装置を前記第３−１の時刻に通過した前記第１のフローのパケット数から、前記第２のパケット転送装置を前記第２−１の時刻に通過した前記第１のフローのパケット数を減算した値を、前記第２のパケット転送装置を前記第２−１の時刻から前記第４−１の時刻の間に通過した前記第１のフローのパケット数で除算した値に、前記第２−１の時刻と前記第４−１の時刻との差を乗じて、当該乗算を行った結果に前記第２−１の時刻を加算して前記第２−１の基準時刻を算出し、前記第２のパケット転送装置を前記第２−２の時刻に通過した前記第２のフローのパケット数から、前記第１のパケット転送装置を前記第１−２の時刻に通過した前記第２のフローのパケット数を減算した値を、前記第１のパケット転送装置を前記第１−２の時刻から前記第３−２の時刻の間に通過した前記第２のフローのパケット数で除算した値に、前記第１−２の時刻と前記第３−２の時刻との差を乗じて、当該乗算を行った結果に前記第１−２の時刻を加算して前記第１−２の基準時刻を算出し、前記第１のパケット転送装置を前記第３−２の時刻に通過した前記第２のフローのパケット数から、前記第２のパケット転送装置を前記第２−２の時刻に通過した前記第２のフローのパケット数を減算した値を、前記第２のパケット転送装置を前記第２−２の時刻から前記第４−２の時刻の間に通過した前記第２のフローのパケット数で除算した値に、前記第２−２の時刻と前記第４−２の時刻との差を乗じて、当該乗算を行った結果に前記第２−２の時刻を加算して前記第２−２の基準時刻を算出することを特徴とする。

（３）また、本発明の一態様は、往復遅延推定装置における方法において、遅延推定装置における方法において、時刻算出部が、第１のパケット転送装置から第２のパケット転送装置へ伝送される第１のフローうち第ｉ個目（ただしｉは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−１の時刻と、前記第１のフローのうち第ｊ個目（ただしｊは、２以上の整数でｉより大きい）のパケットが前記第２のパケット転送装置を通過する第２−１の時刻と、前記第１のフローのうち第ｋ個目（ただしｋは、３以上の整数でｉ及びｊより大きい）のパケットが前記第１のパケット転送装置を通過する第３−１の時刻と、前記第１のフローのうち第ｌ個目（ただしｌは、４以上の整数でｉ、ｊ、及びｋより大きい）のパケットが前記第２のパケット転送装置を通過する第４−１の時刻とを用いて、前記第１のパケット転送装置を前記第ｊ個目のパケットが通過した前記第１のフローの第１の基準時刻を第１−１の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｋ個目のパケットが通過した前記第１のフローの第２の基準時刻を第２−１の基準時刻として算出し、前記第２のパケット転送装置から前記第１のパケット転送装置へ伝送される第２のフローのうち第ｍ個目（ただしｍは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−２の時刻と、前記第２のフローのうち第ｎ個目（ただしｎは、２以上の整数でｍより大きい）のパケットが前記第２のパケット転送装置を通過する第２−２の時刻と、前記第２のフローのうち第ｏ個目（ただしｏは、３以上の整数でｍ及びｎより大きい）のパケットが前記第１のパケット転送装置を通過する第３−２の時刻と、前記第２のフローのうち第ｐ個目（ただしｐは、４以上の整数でｍ、ｎ、及びｏより大きい）のパケットが前記第２のパケット転送装置を通過する第４−２の時刻とを用いて、前記第１のパケット転送装置を前記第ｎ個目のパケットが通過した前記第２のフローの前記第１の基準時刻を第１−２の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｏ個目のパケットが通過した前記第２のフローの前記第２の基準時刻を第２−２の基準時刻として算出する時刻算出手順と、往復遅延算出部が、前記時刻算出手順によって算出された前記第１−１の基準時刻と、前記第１−２の基準時刻と、前記第２−１の基準時刻と、前記第２−２の基準時刻とともに、前記第２−１の時刻と、前記第２−２の時刻と、前記第３−１の時刻と、前記第３−２の時刻と、を用いて、前記第１のパケット転送装置と前記第２のパケット転送装置の間の往復遅延を推定する往復遅延算出手順と、を含むことを特徴とする遅延推定方法である。

（４）また、本発明の一態様は、往復遅延推定装置のコンピュータに、第１のパケット転送装置から第２のパケット転送装置へ伝送される第１のフローうち第ｉ個目（ただしｉは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−１の時刻と、前記第１のフローのうち第ｊ個目（ただしｊは、２以上の整数でｉより大きい）のパケット転送装置を通過する第２−１の時刻と、前記第１のフローのうち第ｋ個目（ただしｋは、３以上の整数でｉ及びｊより大きい）のパケットが前記第１のパケット転送装置を通過する第３−１の時刻と、前記第１のフローのうち第ｌ個目（ただしｌは、４以上の整数でｉ、ｊ、及びｋより大きい）のパケットが前記第２のパケット転送装置を通過する第４−１の時刻とを用いて、前記第１のパケット転送装置を前記第ｊ個目のパケットが通過した前記第１のフローの第１の基準時刻を第１−１の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｋ個目のパケットが通過した前記第１のフローの第２の基準時刻を第２−１の基準時刻として算出する時刻算出し、前記第２のパケット転送装置から前記第１のパケット転送装置へ伝送される第２のフローのうち第ｍ個目（ただしｍは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−２の時刻と、前記第２のフローのうち第ｎ個目（ただしｎは、２以上の整数でｍより大きい）のパケットが前記第２のパケット転送装置を通過する第２−２の時刻と、前記第２のフローのうち第ｏ個目（ただしｏは、３以上の整数でｍ及びｎより大きい）のパケットが前記第１のパケット転送装置を通過する第３−２の時刻と、前記第２のフローのうち第ｐ個目（ただしｐは、４以上の整数でｍ、ｎ、及びｏより大きい）のパケットが前記第２のパケット転送装置を通過する第４−２の時刻とを用いて、前記第１のパケット転送装置を前記第ｎ個目のパケットが通過した前記第２のフローの前記第１の基準時刻を第１−２の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｏ個目のパケットが通過した前記第２のフローの前記第２の基準時刻を第２−２の基準時刻として算出する時刻算出手順と、前記時刻算出手順によって算出された前記第１−１の基準時刻と、前記第１−２の基準時刻と、前記第２−１の基準時刻と、前記第２−２の基準時刻とともに、前記第２−１の時刻と、前記第２−２の時刻と、前記第３−１の時刻と、前記第３−２の時刻と、を用いて、前記第１のパケット転送装置と前記第２のパケット転送装置の間の往復遅延を推定する往復遅延算出手順と、を実行させるための遅延推定プログラムである。

本発明によれば、プローブ装置を配置することなく、ネットワーク内の任意のパケット転送装置間の往復遅延時間を測定することができる。

本発明の実施形態に係る往復遅延推定システムの概略構成図である。 本実施形態に係るフロー情報について説明する説明図である。 本実施形態に係る往復遅延推定装置の構成の一例を示す概略構成図である。 本実施形態に係る取得情報テーブルの要素を示す図である。 本実施形態に係る往復遅延推定装置の処理を示すフローチャートである。 本実施形態に係る情報収集処理を示すフローチャートである。 本実施形態に係る往復遅延推定処理を示すフローチャートである。 本実施形態に係るフロー情報テーブルの一例を示す図である。 本実施形態に係る取得情報テーブルの一例を示す図である。 本実施形態に係るフロー情報テーブルの一例を示す図である。 本実施形態に係る取得情報テーブルの一例を示す図である。 本実施形態に係る取得情報テーブルの別の一例を示す図である。 本実施形態に係る遅延算出テーブルの別の一例を示す図である。 本実施形態に係る遅延算出テーブルの別の一例を示す図である。 本実施形態に係るフロー時刻情報およびパケット数情報を示す図である。 本実施形態に係るパケット数情報と基準時刻情報の関係を示す図である。 本実施形態に係る非測定対象フローの情報を示す図である。 本実施形態に係るフロー時刻情報およびパケット数情報を示す図である。 本実施形態に係るパケット数情報と基準時刻情報の関係を示す図である。 本実施形態に係る非測定対象フローの情報を示す図である。 本実施形態に係るフロー時刻情報およびパケット数情報を示す図である。 本実施形態に係る非測定対象フローに関する情報を示す図である。 本実施形態に係る取得情報テーブルである。 本実施形態に係る取得情報テーブルの別の一例である。 本実施形態に係る遅延算出テーブルを示す図である。 本実施形態に係る遅延算出テーブルの別の一例を示す図である。 本実施形態に係る遅延算出テーブルの別の一例を示す図である。 本実施形態に係る取得情報テーブルを示す図である。 本実施形態に係る生成した遅延算出テーブルの一例を示す図である。 本実施形態に係る生成した遅延算出テーブルの別の一例を示す図である。

以下、図面を参照しながら本発明の実施形態について詳しく説明する。図１は、本発明の往復遅延推定システム１の概略構成図である。
図示する例では、往復遅延推定システム１は、往復遅延推定装置１０、５個のパケット転送装置２０−１〜２０−５を含むネットワークを含んで構成される。以下、パケット転送装置２０−１〜２０−５を総称して、パケット転送装置２０という。

往復遅延推定装置１０は、測定区間の両端にある２台の選択したパケット転送装置２０（それぞれ、パケット転送装置ＩＤ−１、ＩＤ−２と呼ぶ）から、２台のパケット転送装置の両方を通過するパケットのフロー情報（以下、測定対象フロー情報と呼ぶ）を取得する。また、往復遅延推定装置１０は、パケット転送装置ＩＤ−１、ＩＤ−２を通過する測定対象以外のフロー情報（以下、非測定対象フロー情報と呼ぶ）を取得する。
往復遅延推定装置１０は、取得した測定対象フロー情報、及び非測定対象フロー情報に基づいて、後述する基準時刻情報を生成する。往復遅延推定装置１０は、生成したパケット転送装置ＩＤ−１、ＩＤ−２の基準時刻情報に基づいてＲＴＴ（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ；往復時間）を計算する。

パケット転送装置２０は、ルータやスイッチなどであり、パケットを転送する装置である。パケット転送装置２０は、装置内を通過するパケットをフローとして認識し、フロー単位の情報を、ネットワークを介して往復遅延推定装置１０に出力する機能を有する。出力される情報には、各フローが流れ始めてからのフローの生存時間を示すフロー時刻情報、および各フローが流れ始めてからフロー情報を出力するまでに転送処理されたパケット数情報が含まれている。

パケット転送装置２０からのフロー情報は、パケット転送装置２０から往復遅延推定装置１０に対して、設定された間隔で自動的に送信するようにしてもよい。これは、IPFIXまたはNetFlow等のプロトコルを用いる場合に相当する。 あるいは、往復遅延推定装置１０からの取得要求に応じて、パケット転送装置２０が情報を送信するようにしてもよい。この場合、例えば、ＯｐｅｎＦｌｏｗ等のプロトコルを用いる。

なお、フロー情報の取得方法は、後述するように、パケット転送装置２０に対して抽出したいフローの条件を指定することで、その情報のみを往復遅延推定装置１０に出力するようにしてもよい。また、取得したフロー情報内に各フローを判別できる情報が含まれているので、往復遅延推定装置１０は、各フローを判別できる情報を利用して特定のフローのみを抽出するようにしてもよい。なお、フローとは、送信元ＩＰアドレス、送信先ＩＰアドレス、送信先ポート番号、送信元ポート番号、及びプロトコル等により決まる。

図２は、フロー情報について説明する説明図である。以下では、測定を行う対象区間の両端にあるパケット転送装置をパケット転送装置ＩＤ−１（第１のパケット転送装置）、ＩＤ−２（第２のパケット転送装置）と呼ぶ。パケット転送装置ＩＤ−１からパケット転送装置ＩＤ−２へ向かうパケット（第１のパケット）に対応するフローのＩＤ（測定対象フロー）をＦｌｏｗＩＤ−１（第１のフロー）と呼ぶ。ＦｌｏｗＩＤ−２、３は、パケット転送装置ＩＤ１を通過するパケットに対応するフロー（非測定対象フロー）情報である。ＦｌｏｗＩＤ−４及びＦｌｏｗＩＤ−は、パケット転送装置ＩＤ−２を通過するパケットに対応するフロー（非測定対象フロー）情報である。なお、測定対象フロー以外であれば、パケット転送装置ＩＤ−１、ＩＤ−２の両方を通過するフローを非測定対象フローとしてもよい。

図３は、往復遅延推定装置１０の構成の一例を示す概略構成図である。往復遅延推定装置１０は、フロー情報取得部１０１、時刻算出部１０２、往復遅延算出部１０３及びＤＢ（データベース）１０４を含んで構成される。

フロー情報取得部１０１は、パケット転送装置２０からフロー情報を取得する。ここでフロー情報とは、当該フロー情報を生成するまでに該パケット転送装置を通過した該フローのパケット数と、該フローの最初のパケットを転送してから当該フロー情報を生成するまでの経過時間であるフロー時刻情報とを含む情報である。フロー情報取得部１０１は、取得したフロー情報各々のフロー時刻情報を、パケット転送装置２０毎に特定のフローのフロー時刻情報（基準時刻情報）に置き換え、パケット数と基準時刻情報とを対応付けて取得情報テーブルに記憶させる。このとき、置き換えるフロー時刻情報として、該フロー情報と同時に取得したフロー情報のうち、特定のフローのフロー時刻情報を用いる。

時刻算出部１０２は、フロー情報所得部がＤＢに記憶させた取得情報テーブルを参照して、特定のパケットのパケット転送装置ＩＤ−１とパケット転送装置ＩＤ−２との通過時刻を算出する。例えば、時刻算出部１０２は、パケット転送装置ＩＤ−１のパケット数Ｐ１（一の第１パケット数）と基準時刻情報Ｔ１とを、取得情報テーブルから取得し、該パケット数Ｐ１に対応するパケットＡ１（該フローのパケットのうち、パケット数番目のパケット）のパケット転送装置ＩＤ−１の通過時刻を、該基準時刻情報Ｔ１とする。さらに、時刻算出部１０２は、このパケット数Ｐ１に加えて、パケット転送装置ＩＤ−２のパケット数と基準時刻情報との複数の組（パケット数Ｐ２、Ｐ３、基準時刻情報Ｔ２、Ｔ３）を取得情報テーブルから取得し、これらを用いて、さきのパケットＡ１のパケット転送装置ＩＤ−２の通過時刻（第１推定値）を算出する。
この算出には、パケット転送装置ＩＤ−１のパケット数Ｐ１とパケット転送装置ＩＤ−２のパケット数Ｐ２との差と、パケット転送装置ＩＤ−２のパケット数Ｐ２とＰ３（複数の第２パケット数）との差との比を用いて、基準時刻情報Ｔ２とＴ３（第２の修訂の時刻）との差を比例配分して、パケットＡ１がパケット転送装置ＩＤ−２を通過した時刻を算出する。時刻算出部１０２は、これら算出した時刻を、パケット数と対応付けて、遅延算出テーブルに記憶させる。時刻算出部１０２は、同様にしてパケット転送装置ＩＤ−２のパケット数Ｐ４に対応するパケットがパケット転送装置ＩＤ−１を通過した時刻を算出する。これらを、パケット転送装置ＩＤ−１からＤ−２へのフローと、逆のパケット転送装置ＩＤ−２からＩＤ−１へのフローとについて行う。

往復遅延算出部１０３は、遅延算出テーブルを参照して、パケット転送装置ＩＤ−１、ＩＤ−２間の往復の遅延を算出する。例えば、往復遅延算出部１０３は、遅延算出テーブルを参照して、パケット転送装置ＩＤ−１からＩＤ−２へのフロー（第１のフロー）のパケットＡ２（第１のパケット）が、パケット転送装置ＩＤ−２を通過した時刻（第２の時刻）とパケット転送装置ＩＤ−１を通過した時刻（第１の時刻）との差と、パケット転送装置ＩＤ−２からＩＤ−１へのフロー（第２のフロー）のパケットＡ３（第２のパケット）が、パケット転送装置ＩＤ−１を通過した時刻（第３の時刻）とパケット転送装置ＩＤ−２を通過した時刻（第４の時刻）との差との和をとり、パケット転送装置ＩＤ−１、ＩＤ−２間の往復の遅延を算出する。

ＤＢ１０４には、フロー情報取得部１０１から入力されたフロー情報テーブル及び取得情報テーブル格納されている。ＤＢ１０４には、時刻算出部１０２から入力された遅延算出テーブルが格納されている。

図４は、本実施形態に係る取得情報テーブルの要素を示す図である。図示するように、取得情報テーブルは、パケット転送装置２０に一意に定められた転送装置ＩＤ、フロー情報に一意に定められたフローＩＤ、フロー情報から抽出したパケット数情報、及び基準時刻情報の各要素からなるテーブルである。

図５は、本実施形態に係る往復遅延推定装置１０の処理を示すフローチャートである。
（ステップＳ１）フロー情報取得部１０１は、ネットワークからフロー情報を取得する。フロー情報取得部１０１は、フロー情報から、パケット数情報、及び基準時刻情報を紐付けた取得情報を生成し、取得情報テーブルに記録する（フロー情報取得処理）。フロー情報取得部１０１は、予め定めた一定の時間おきに、予め定めた回数のフロー情報取得動作を行う。その後ステップＳ２に進む。
（ステップＳ２）時刻算出部１０２は、取得情報テーブルに基づいて、遅延算出テーブルを生成する。往復遅延算出部１０３は、遅延算出テーブルに基づいて、ＲＴＴの推定を行う。
なお、ステップＳ１とステップＳ２は同時に行ってもよい。

図６は、本実施形態に係るステップＳ１の処理を示すフローチャートである。
（ステップＳ１０１）フロー情報取得部１０１は、指定回数もしくは指定時間に達するまでステップＳ１０２〜Ｓ１０９の処理を繰り返す。
（ステップＳ１０２）フロー情報取得部１０１は、ネットワークから、往復遅延を測定したい区間の両端に位置するパケット転送装置（つまり、パケット転送装置ＩＤ−１、ＩＤ−２）から測定対象フロー情報及び非測定対象フロー情報を取得する。その後ステップＳ１０３に進む。
（ステップＳ１０３）フロー情報取得部１０１は、測定対象フロー情報からパケット数情報を、非測定対象フロー情報からフロー時刻情報を抽出する。その後ステップＳ１０４に進む。

（ステップＳ１０４）フロー情報取得部１０１は、基準時刻情報を取得するために用いる非測定対象フロー情報を選定済みであるか否かを判定する。選定済みであると判定された場合（Ｙｅｓ）は、ステップＳ１０７に進む。選定済みでないと判定された場合（Ｎｏ）はステップＳ１０５に進む。
（ステップＳ１０５）フロー情報取得部１０１は、パケット転送装置ＩＤ−１、ＩＤ−２における基準時刻情報として利用する基準時刻フロー情報を選定する。その後ステップＳ１０６に進む。
（ステップＳ１０６）フロー情報取得部１０１は、基準時刻情報として利用するフロー情報からフロー時刻情報を抽出し、抽出したフロー時刻情報を基準時刻情報とする。その後ステップＳ１０９に進む。

（ステップＳ１０７）フロー情報取得部１０１は、前回に選定済みのフロー情報が今回も取得できたか否かを判定する。取得できたと判定された場合（Ｙｅｓ）は、ステップＳ１０６に進む。取得できなかったと判定された場合（Ｎｏ）は、ステップＳ１０８に進む。
（ステップＳ１０８）フロー情報取得部１０１は、新たな基準時刻情報として利用する非測定対象フロー情報を選定し、前回に基準時刻情報として利用していたフロー情報を用いて後述するように補正処理を行い、基準時刻情報を生成する。その後ステップＳ１０９に進む。
（ステップＳ１０９）フロー情報取得部１０１は、転送装置ＩＤ、フローＩＤ、パケット数情報、及び基準時刻情報を取得情報テーブルとしてＤＢ１０４に格納する。

図７は、本実施形態に係るステップＳ２の処理を示すフローチャートである。
（ステップＳ２０１）時刻算出部１０２は、測定区間を通過する両方向の測定対象フロー情報に対してステップＳ２０２〜Ｓ２０６の処理を行う。
（ステップＳ２０２）時刻算出部１０２は、取得情報テーブル内のパケット数情報が小さい順にステップＳ２０３〜Ｓ２０６の処理を行う。
（ステップＳ２０３）時刻算出部１０２は、取得情報テーブルから、処理対象となっていない情報の中で、パケット数が最も小さい情報を抽出し、これを処理対象情報とする。

（ステップＳ２０４）時刻算出部１０２は、ステップＳ２０３で抽出した処理対象情報の示す転送装置ＩＤと異なる転送装置ＩＤを持つ情報であって、処理対象情報のパケット数情報より小さく且つ最も処理対象情報のパケット数情報に近いパケット数情報を持つ情報（情報Ａと呼ぶ）、及びステップＳ２０３で抽出した処理対象情報の示す転送装置ＩＤと異なる転送装置ＩＤを持つ情報であって、処理対象情報のパケット数情報より大きく且つ最も処理対象情報のパケット数情報に近いパケット数情報を持つ情報（情報Ｂと呼ぶ）を抽出する。その後ステップＳ２０５に進む。
（ステップＳ２０５）時刻算出部１０２は、情報Ａ及び情報Ｂの２つの情報が抽出できたか否かを判定する。２つの情報が共に抽出できたと判定された場合（Ｙｅｓ）はステップＳ２０６に進む。２つの情報のうちどちらか一方でも抽出できなかったと判定した場合（Ｎｏ）はステップＳ２０３に戻る。

（ステップＳ２０６）時刻算出部１０２は、抽出した情報Ａ及び情報Ｂに基づいて、後述するようにパケット数情報と同一のパケット数情報に対する処理対象情報の基準時刻を推定し、遅延算出テーブルに格納する。
（ステップＳ２０７）往復遅延算出部１０３は、ＲＴＴ推定の処理でパケット転送装置ＩＤ−１、ＩＤ−２のどちらの基準時刻情報を利用するかを選択する。その後ステップＳ２０８に進む。
（ステップＳ２０８）往復遅延算出部１０３は、ステップＳ２０７で選択した基準時刻情報に対応する遅延算出テーブル内の基準時刻情報を小さい順に並べ替え、ステップＳ２０９からステップＳ２１３の処理を繰り返す。

（ステップＳ２０９）往復遅延算出部１０３は、遅延算出テーブル内から処理対象となっていない情報の中で、最も基準時刻情報が小さい情報を抽出し、これ処理対象情報とする。その後ステップＳ２１０に進む。
（ステップＳ２１０）往復遅延算出部１０３は、遅延算出テーブル内から、処理対象情報の基準時刻情報より大きく且つ差が最も小さい情報、及び処理対象情報の基準時刻情報より小さく且つ差が最も小さい情報を抽出する。往復遅延算出部１０３は、抽出した情報の中で、処理対象情報のフローＩＤと異なるフローＩＤを持つ情報を抽出する。ただし、上記の条件を満たす情報が２つ抽出できた場合は、最も差が小さい情報のみを抽出する。
（ステップＳ２１１）往復遅延算出部１０３は、ステップＳ２１０で情報を抽出できたか否かを判定する。抽出できたと判定された場合（Ｙｅｓ）はステップＳ２１２に進む。抽出できたと判定されなかった場合（Ｎｏ）は、ステップＳ２０９に戻る。

（ステップＳ２１２）往復遅延算出部１０３は、処理対象情報と、ステップＳ２１０で抽出した情報（抽出情報と呼ぶ）とを用いてすでにＲＴＴを推定したか否かを判定する。ＲＴＴを推定したと判定された場合（Ｙｅｓ）は、ステップＳ２０９に戻る。ＲＴＴを推定しなかったと判定された場合（Ｎｏ）は、ステップＳ２１３に進む。
（ステップＳ２１３）往復遅延算出部１０３は、後述するように、処理対象情報及び抽出情報からＲＴＴを推定する。

（フロー情報テーブルを用いた取得情報テーブルの生成）
図８は、本実施形態に係るフロー情報テーブルの一例を示す図である。図示する例では、フロー情報テーブルは、転送装置ＩＤ、フローＩＤ、フロー時刻情報、及びパケット数情報の各要素からなる２次元形式のテーブルである。図８で示すフロー情報テーブルは、ステップＳ１０１で表される繰返し処理をＮ回行った後のテーブルである。符号８ａを付したデータは、転送装置ＩＤがＩＤ−１、フローＩＤがＦｌｏｗＩＤ−１、パケット数情報はＰ_１（Ｎ）であることを示している。符号８ｂを付したデータは、転送装置ＩＤがＩＤ−１、フローＩＤがＦｌｏｗＩＤ−２、フロー時刻情報がＴ_{ｆ２（Ｎ）}であることを示している。符号８ｃを付したデータは、転送装置ＩＤがＩＤ−１、フローＩＤがＦｌｏｗＩＤ−３、フロー時刻情報がＴ_{ｆ３（Ｎ）}であることを示している。

符号８ｄを付したデータは、転送装置ＩＤがＩＤ−２、フローＩＤがＦｌｏｗＩＤ−１，パケット数情報はＰ_２（Ｎ）であることを示している。符号８ｅを付したデータは、転送装置ＩＤがＩＤ−２、フローＩＤがＦｌｏｗＩＤ−４、フロー時刻情報がＴ_{ｆ４（Ｎ）}であることを示している。符号８ｃを付したデータは、転送装置ＩＤがＩＤ−２、フローＩＤがＦｌｏｗＩＤ−５、フロー時刻情報がＴ_{ｆ５（Ｎ）}であることを示している。
このように、フロー情報テーブルには、測定対象フロー情報に対しては転送装置ＩＤ、フローＩＤ、及びパケット数情報が格納される。また、非測定対象フロー情報に対しては転送装置ＩＤ、フローＩＤ、及びフロー時刻情報が格納される。

図９は、本実施形態に係る取得情報テーブルの一例を示す図である。図示する例では、取得情報テーブルは、転送装置ＩＤ、フローＩＤ、パケット数情報、及び基準時刻情報の各要素からなる２次元形式のテーブルである。符号９ａを付したデータは、転送装置ＩＤがＩＤ−１、フローＩＤがＦｌｏｗＩＤ−１，パケット数情報はＰ_{１（Ｎ）、}基準時刻情報はＴ_{ｆ２（Ｎ）}であることを示している。符号９ｂを付したデータは、転送装置ＩＤがＩＤ−２、フローＩＤがＦｌｏｗＩＤ−１、パケット数情報はＰ_{２（Ｎ）、}基準時刻情報はＴ_{ｆ４（Ｎ）}であることを示している。

図１０は、本実施形態に係るフロー情報テーブルの一例を示す図である。図１０で示すフロー情報テーブルは、ステップＳ１０１で繰返し処理がＮ＋１回行われた後のテーブルである。
図１０では、図８で示したＮ回目の繰返し処理におけるフロー情報テーブルと比較して、フローＩＤがＦｌｏｗＩＤ−４の情報が失われている。これは、このフローが終了したことを示している。図９で示したように、フローＩＤがＦｌｏｗＩＤ−４のフロー情報を基準時刻フロー情報として選択していたが、ＦｌｏｗＩＤ−４のフロー時刻情報をＮ＋１回目の基準時刻情報として利用することができない。そこで、Ｎ回目におけるＦｌｏｗＩＤ−４とＦｌｏｗＩＤ−５におけるフロー時刻情報の差を求め、この差を用いてＦｌｏｗＩＤ−５におけるフロー時刻情報をこれまで利用していたＦｌｏｗＩＤ−４のフロー時刻情報に換算する。
Ｎ回目におけるＦｌｏｗＩＤ−４とＦｌｏｗＩＤ−５におけるフロー時刻情報の差は、「Ｔ_{ｆ５（Ｎ）}−Ｔ_{ｆ４（Ｎ）}」であることを利用すると、Ｎ＋１回目における換算後の基準時刻情報は、「Ｔ_{ｆ５（Ｎ＋１）}−（Ｔ_{ｆ５（Ｎ）}−Ｔ_{ｆ４（Ｎ）}）」と表すことができる。

図１１は、本実施形態に係るＮ＋１回目の繰返し処理において生成される取得情報テーブルの一例を示す図である。図示するように、符号１１ａを付したデータでは、フローＩＤがＦｌｏｗＩＤ−２のフロー情報が存在するため、そのフロー時刻情報であるＴ_{ｆ２（Ｎ＋１）}が基準時刻情報となる。一方、符号１１ａを付したデータでは、フローＩＤがＦｌｏｗＩＤ−４のフロー情報がなくなったため、第Ｎ回目の繰返し処理で取得したＴ_{ｆ４（Ｎ）}、Ｔ_{ｆ５（Ｎ）}と、第Ｎ＋１回目の繰返し処理で取得したＴ_{ｆ５（Ｎ＋１）}とを用いて基準時刻情報を生成している。

図１２は、本実施形態に係る取得情報テーブルの一例を示す図である。この図では、フローＩＤが同一である情報のみを抽出し、パケット数情報が小さい順に並べ替えられている。このとき、処理対象となっていない情報の中で、最もパケット数情報の小さい情報を処理対象情報とする。つまり、符号１２ａを付した情報が処理対象情報となる。
処理対象情報が符号１２ａを付した情報であるとき、パケット数情報Ｐ_１より小さいパケット数情報を持つ情報が存在しない。つまり、ステップＳ２０５において２つの情報が抽出できなかったため、次に小さいパケット数情報を持つ符号１２ｂを付した情報を処理対象情報とする。

符号１２ｂを付した情報が処理対象情報であるとき、これよりパケット数情報が小さい情報が存在するが、この情報の転送装置ＩＤは、処理対象情報の転送装置ＩＤと同一であるため、異なる転送装置ＩＤを持つ情報が存在しない。つまり、ステップＳ２０５において２つの情報が抽出できなかったため、次に小さいパケット数情報を持つ符号１２ｃを付した情報を処理対象情報とする。
符号１２ｃを付した情報が処理対象情報であるとき、転送装置ＩＤが異なり、且つパケット数情報が小さい情報（符号１２ｂを付した情報）及び転送装置ＩＤが異なり、且つパケット数情報が大きい情報（符号１２ｄを付した情報）が存在する。つまり、ステップＳ２０５において２つの情報が抽出できた。従って、ステップＳ２０６に進み、基準時刻情報を推定する。

基準時刻情報がＴ_２のときのパケット数情報はＰ_２、基準時刻情報がＴ_４のときのパケット数情報はＰ_４であることから、時間（Ｔ_４−Ｔ_２）に（Ｐ_４−Ｐ_２）個のパケットが転送装置ＩＤがＩＤ−１をもつパケット転送装置ＩＤ−１を通過したことになる。つまり、パケット１個当たりの経過時間は、「（Ｔ_４−Ｔ_２）／（Ｐ_４−Ｐ_２）」で表される。したがって、転送装置ＩＤがＩＤ−１をもつパケット転送装置ＩＤ−１においてＰ_３個目のパケットが通過した基準時刻Ｔ_Ｐ３は式１を用いて求めることができる。

続いて符号１２ｄを付した情報が処理対象情報となる。符号１２ｄを付した情報に対しては、符号１２ｃを付した情報及び符号１２ｅを付した情報がステップＳ２０４における条件を満たし、ステップＳ２０５の条件を満たす。従って、ステップＳ２０６に進み、パケット転送装置ＩＤ−２においてＰ_４個目のパケットが通過した基準時刻Ｔ_ｐ４を式２を用いて求めることができる。

（遅延算出テーブルの生成）
図１３は、本実施形態に係る遅延算出テーブルの一例を示す図である。図示する例では、遅延算出テーブルは、フローＩＤ、パケット数情報、転送装置ＩＤがＩＤ１をもつパケット転送装置ＩＤ−１の基準時刻情報、及び転送装置ＩＤがＩＤ２をもつパケット転送装置ＩＤ−２の基準時刻情報の各要素からなる２次元形式のテーブルである。
符号１３ａを付した情報は、フローＩＤがＦｌｏｗＩＤ−１でパケット数情報がＰ_３であるときのパケット転送装置ＩＤ−１の基準時刻情報がＴ_ｐ３と推定され、パケット転送装置ＩＤ−２の基準時刻情報がＴ_３であることを示している。
符号１３ｂを付した情報は、フローＩＤがＦｌｏｗＩＤ−１でパケット数情報がＰ_４であるときのパケット転送装置ＩＤ−１の基準時刻情報がＴ_４であり、パケット転送装置ＩＤ−２の基準時刻情報がＴ_ｐ４と推定されることを示している。

（遅延算出テーブルを用いたＲＴＴの推定）
図１４は、本実施形態に係る遅延算出テーブルの一例を示す図である。本図では、ＦｌｏｗＩＤ−１は、転送装置ＩＤが、ＩＤ−１からＩＤ−２のパケット転送装置２０へ向けたフローを示す。また、ＦｌｏｗＩＤ−２は、転送装置ＩＤが、ＩＤ−２からＩＤ−１のパケット転送装置２０へ向けたフローを示す。本遅延算出テーブルは、ステップ２０８においてパケット転送装置ＩＤ−１の基準時刻情報の小さなものから順に並べ替えを行った後の遅延算出テーブルである。以下では、特に記載のない場合は、パケット転送装置ＩＤ−１の基準時刻情報を単に基準時刻情報と呼ぶ。
まず、ステップＳ２０９において、符号１４ａを付した情報が処理対象情報として選択される。この処理対象情報より基準時刻情報が小さな情報はなく、この処理対象情報より大きい基準時刻情報を持ち且つその差が最も小さい情報は符号１４ｂを付した情報となる。符号１４ｂを付した情報のフローＩＤは、処理対象情報のフローＩＤと異なるため、抽出されることとなる。
処理対象情報（符号１４ａを付した情報）と符号１４ｂを付した情報とでは、ＲＴＴ推定処理は行われていないことから、この２つの情報を用いて、式３によりＲＴＴを計算する。

次に処理対象情報となるのは、符号１４ｂを付した情報である。このとき、処理基準時刻情報より大きく且つ差が最も小さい情報は符号１４ｃを付した情報であるが、フローＩＤが同一であるため抽出されない。処理対象情報の基準時刻情報より小さく且つ差が最も小さい情報は符号１４ａを付した情報である。これはフローＩＤが異なるため抽出されることになる。しかしながら、処理対象情報と符号１４ａを付した情報を利用したＲＴＴ推定処理は既に実施済みであることから、ＲＴＴ推定処理は行われない。次に、符号１４ｃを付した情報が処理対象情報となる。このとき、符号１４ｄを付した情報は、処理対象情報より大きく、且つ最も差が小さく、フローＩＤも異なる。また、処理対象情報と符号１４ｄを付した情報とを利用してＲＴＴ推定処理は行われていないため、以下の式４によりＲＴＴを算出する。

以下同様にしてテーブル内の全ての情報に基づいてＲＴＴを計算する。

[具体例]
次に、具体的な実施例を図面を参照しながら説明する。
ここでは、測定区間の両端に位置するパケット転送装置２０を識別する転送装置ＩＤをそれぞれ「ＩＤ−１」「ＩＤ−２」とし、この２つのパケット転送装置２０の両方を通過する測定対象フローのフローＩＤ を「ＦｌｏｗＩＤ−１」とする。また、パケット転送装置「ＩＤ−１」を通過する非測定対象フローのフローＩＤを「ＦｌｏｗＩＤ−２」、パケット転送装置「ＩＤ−２」を通過する非測定対象フローのフローＩＤを「ＦｌｏｗＩＤ−３」および「ＦｌｏｗＩＤ−４」とする。

（第１回目の情報収集）
フロー情報取得部１０１は、測定区間の両端のパケット転送装置２０から、ＦｌｏｗＩＤ−１からＦｌｏｗＩＤ−４までの全てのフローに関するフロー時刻情報およびパケット数情報を取得する。
図１５は、第１回目に取得したフロー毎のフロー時刻情報およびパケット数情報を示す図である。なお、括弧で示した情報は、取得情報テーブルへの情報追加に関係のない情報（処理の説明においては「−」で示した情報）であることを示している。
図１６は、パケット数情報と基準時刻情報の関係を示す図である。また、図１７は、非測定対象フローの情報を示す図である。

ここで、パケット転送装置ＩＤ−１における基準時刻情報として利用するフローをＦｌｏｗＩＤ−２、パケット転送装置ＩＤ−２における基準時刻情報として利用するフローをＦｌｏｗＩＤ−３とする。このとき、取得情報テーブルには転送装置毎に測定対象フローであるＦｌｏｗＩＤ−１に関するフロー時刻情報およびパケット数情報と、各転送装置における基準時刻情報として転送装置毎に決めた非測定対象フローのフロー時刻情報を格納する。
つまり、転送装置ＩＤ−１については、測定対象フローＦｌｏｗＩＤ−１のパケット数情報「２７８０」と、基準時刻情報として利用する非測定対象フローＦｌｏｗＩＤ−２のフロー時刻情報「６２７」を格納する。また、転送装置ＩＤ−２については、測定対象フローＦｌｏｗＩＤ−２のパケット数情報「２４２０」と、基準時刻情報として利用する非測定対象フローＦｌｏｗＩＤ−３のフロー時刻情報「２３２」を格納する。

（第２回目の情報収集）
図１８は、第２回目に取得したフロー毎のフロー時刻情報およびパケット数情報を示す図である。１回目と同様にしてＦｌｏｗＩＤ−１からＦｌｏｗＩＤ−４までの全てのフローに関するフロー時刻情報およびパケット数情報を取得したところ、各パケット転送装置２０における基準時刻情報として利用しているＦｌｏｗＩＤ−２及びＦｌｏｗＩＤ−３が共に存在していることから、引き続きこの情報を基準情報として利用する。
図１９は、第２回目の情報収集後のパケット数情報と基準時刻情報の関係を示す図である。また、図２０は、第２回目の情報収集後の非測定対象フローの情報を示す図である。
このとき、各パケット転送装置における基準時刻情報として利用しているフローＦｌｏｗＩＤ−２およびＦｌｏｗＩＤ−３が共に存在していることから、引き続きこの情報を基準時刻情報として利用する。このとき、1 回目と同様にして取得情報テーブルに情報追加を行う。
また、転送装置毎に非測定対象フロー全てのフロー時刻情報を保持する。

（第３回目の情報収集）
図２１は本実施形態に係る第３回目に取得したフロー毎のフロー時刻情報およびパケット数情報を示す図である。第３回目に取得したデータにはパケット転送装置ＩＤ−２が使用していた非測定対象フローＦｌｏｗＩＤ−３が存在しなくなったため、パケット転送装置ＩＤ−２に対する基準時刻情報として利用するフローをＦｌｏｗＩＤ−３からＦｌｏｗＩＤ−４へと変更する。

利用するフローを変更した場合、新たなフローの基準時刻情報を、これまで取得情報テーブルに格納してきた基準時刻情報に合わせるための補正処理が必要となる。補正処理は保持していた転送装置毎に非測定対象フローの情報を利用する。
図２２は、パケット転送装置ＩＤ−２の非測定対象フローについて保持していた情報を示す図である。
つまり、ＦｌｏｗＩＤ−３におけるフロー時刻情報「２８３」とＦｌｏｗＩＤ−４におけるフロー時刻情報「６７」が同じ時刻であることから、このフロー時刻情報の差を利用して補正処理を行う。つまり、３回目におけるパケット転送装置の基準時刻情報は以下のようになる。
１００−（６７−２８３）＝３１６
この計算によりＦｌｏｗＩＤ−３が存在していたとしたときにＦｌｏｗＩＤ−３から得られるであろうフロー時刻情報を求めたことになる。
図２３は、この補正結果を利用してパケット転送装置ＩＤ−２に対する取得情報テーブルを追加した図である。
本例では、情報取得回数を３回としていたため、これで情報取得処理は終了する。

（遅延算出テーブルの生成）
ここでは、転送装置ＩＤがＩＤ−１のパケット転送装置と、転送装置ＩＤがＩＤ−２のパケット転送装置の間のＲＴＴを推定する。往復遅延算出部１０３は、「ＩＤ−１→ＩＤ−２」の向きに流れるＦｌｏｗＩＤ−１のフローと、「ＩＤ−２→ＩＤ−１」の向きに流れるＦｌｏｗＩＤ−２のフローからＲＴＴを推定する。
図２４は、取得情報テーブルからＦｌｏｗＩＤ−１のフローのみを選択し、パケット数情報が示すパケット数について上り順となるよう並び替えた図である。処理対象となっていないパケット数情報が最小の情報は、符号２４ａを付した情報であり、これが最初に処理対象情報となる。

処理対象となっていないパケット数情報が最小の情報は符号２４ａを付した情報であり、これが最初の処理対象情報となる。このとき、処理対象情報のパケット数情報より小さな値を持つ情報は存在しないため、次にパケット数情報が小さい符号２４ｂを付した情報が処理対象情報となる。
符号２４ｂを付した情報が処理対象情報であるとき、転送装置ＩＤが異なり、かつ処理対象情報のパケット数情報より小さなパケット数情報を持つ情報（符号２４ａを付した情報）、および転送装置ＩＤが異なり、かつ処理対象情報のパケット数情報より大きなパケット数情報を持つ情報（符号２４ｃを付した情報）が抽出できる。処理対象情報は転送装置ＩＤがＩＤ−１の情報であり、またパケット数情報は「３２５」であるため、ここではＩＤ−２の転送装置におけるパケット数が「３２５」のときの基準時刻情報Ｔ_325(ID-2)を先に示した式１により推定する。

図２５は、パケット数情報とパケット転送装置ＩＤ−１、ＩＤ−２における基準時刻情報を示す遅延算出テーブルである。時刻算出部１０２は、得られたパケット転送装置ＩＤ−２におけるパケット転送装置ＩＤ−１と同数のパケット数における基準時刻情報を遅延算出テーブルに格納する。

次の処理対象情報は符号２４ｃを付した番目の情報となる。このとき、同様にして符号２３ｂを付した情報および符号２４ｃを付した情報が抽出できる。処理対象情報は転送装置ＩＤがＩＤ−２の情報であり、またパケット数情報は「４１８」であるため、ここではＩＤ−１の転送装置におけるパケット数が「４１８」のときの基準時刻情報Ｔ_{４１８（ＩＤ−１）}を先に示した式１により推定する。

図２６は、パケット数情報とパケット転送装置ＩＤ−１、ＩＤ−２における基準時刻情報を示す遅延算出テーブルである。パケット数情報が「４１８」のときの基準時刻情報が追加されている。
次に、符号２４ｄを付した情報が処理対象となる。これまでと同様に、符号２３ｄを付した情報の基準時刻情報が計算され、Ｔ_{５１１（ＩＤ−２）}＝１２６と求まる。
図２７は、パケット数情報とパケット転送装置ＩＤ−１、ＩＤ−２における基準時刻情報を示す遅延算出テーブルである。パケット数情報が「５１１」のときの基準時刻情報が追加されている。
次の処理対象情報は、符号２４ｅを付した情報であるが、処理対象情報のパケット数情報より大きなパケット数情報を持つ情報が存在しないため、遅延算出テーブルの生成処理は終了となる。

次に、ＦｌｏｗＩＤ−１と逆方向のフローであるＦｌｏｗＩＤ−２のフローについて、ＦｌｏｗＩＤ−１と同様の処理を行う。
図２８は、取得情報テーブルからＦｌｏｗＩＤ−２を含むフローのみを選択し、パケット数情報が示すパケット数が上り順となるよう並び替えた図である。ＦｌｏｗＩＤ−１のときと同様に、パケット数情報が最小である符号２８ａを付した情報は、これより小さな値を持つ情報は存在しないため、次にパケット数情報が小さい符号２８ｂを付した情報が処理対象情報となる。以下同様にして、符号２８ｂの情報が処理対象情報であるときは、ＩＤ−１におけるパケット数「１０７」に対する基準時刻情報を算出し、遅延時間テーブルに格納する。また、符号２８ｃを付した情報が処理対象情報のときは、ＩＤ−２におけるパケット数「２１７」に対する基準時刻情報を算出し、遅延算出テーブルに格納する。

符号２８ｄを付した情報が処理対象情報のときは、これより大きいパケット数情報を持つ情報が存在しないため、遅延算出テーブルの生成は終了となる。
図２９は生成した遅延算出テーブルを示す図である。本図では、ＦｌｏｗＩＤ−２を含むフローのみについて記載しているが、実際は、遅延算出テーブルにはＦｌｏｗＩＤ−１について生成した基準時刻情報も同様に記載されている。

（ＲＴＴの算出）
図３０は、「ＩＤ−１→ＩＤ−２」の向きに流れるＦｌｏｗＩＤ−１のフローと、「ＩＤ−２→ＩＤ−１」の向きに流れるＦｌｏｗＩＤ−２のフローから生成した遅延算出テーブル（図２７、図２９参照）を、ＩＤ−１に対する基準時刻情報について、値の小さい順に並べ替えた図である。
最初は、符号３０ａを付した情報が処理対象情報となる。このとき、処理対象情報より基準時刻情報が小さい情報は無く、処理対象情報より大きくかつその差が最も小さい情報は符号３０ｂを付した情報であり、これは処理対象情報とフローＩＤが同一である。つまり、符号３０ａを付した情報に対してＲＴＴを推定するための情報が抽出できなかったこととなるため、次に基準時刻情報が小さい符号３０ｂを付した情報が処理対象情報となる。符号３０ｂを付した情報が処理対象情報であるとき、これより小さくかつフローＩＤが異なる基準時刻情報を持つ情報は存在しないが、処理対象情報の基準時刻情報より大きく差が最も小さい情報はフローＩＤが異なっていることから、符号３０ｃを付した情報が抽出される。符号３０ｃを付した情報は処理対象情報（符号３０ｂを付した情報）とＲＴＴ算出を実施していないことから、この２つの情報を利用して、先に示した式によりＲＴＴの推定を行う。
ＲＴＴ＝（１２３−１３）＋（１４−９４）＝３０

つまり、ここでは、ＲＴＴ＝３０であると推定できる。
次は３番目の情報が処理対象情報となる。処理対象情報の基準時刻情報より大きくかつ差が最も小さい情報は４番目の情報であり、これはフローＩＤが異なるため抽出される。また、処理対象情報の基準時刻情報より小さくかつ差が最も小さい情報は２番目の情報であり、これもフローＩＤが異なるため抽出される。つまり、この場合は２つの情報が抽出されたため、この２つの情報の中で基準時刻情報の差が小さい方である２番目の情報が最終的に抽出されることになる。３番目の情報が処理対象情報のとき、２番目の情報が抽出情報であり、この組み合わせで既にＲＴＴ推定を実施済みであることから、ここではＲＴＴ推定処理は実施せず、４番目の情報が処理対象情報となる。４番目の情報が処理対象情報であるとき、３番目と５番目の情報が共にフローＩＤが異なっていることから、２つとも抽出されるが、基準時刻情報の差から最終的には３番目の情報が抽出され、３番目の情報と４番目の情報を利用してＲＴＴ推定を実施していないことから、推定処理を行う。
ＲＴＴ = (１４−９４) + (１２６−１６) =３０

つまり、ここでは「ＲＴＴ=３０」であると推定できる。
次は５番目の情報が処理対象情報となる。以下同様にして、４番目の情報が抽出され、この間でのＲＴＴ推定は行われていないことから推定処理を実施し「ＲＴＴ＝３０」であると推定できる。
ここでは、遅延の変化（ゆらぎ）やロスがない理想的な状態を例にＲＴＴ推定方法を示したが、実際はゆらぎ等が発生し、各推定計算において異なるＲＴＴ推定値が得られる可能性がある。そのときは、複数回のＲＴＴ推定値の平均を取ってＲＴＴ推定値としてもよい。

このように、本実施形態によれば、往復遅延算出部１０３は、第１のパケット転送装置２０−１と第２のパケット転送装置２０−２との往路の遅延時間と復路の遅延時間との和をとって、往復の時間を算出する。これにより、第１のパケット転送装置と第２のパケット転送装置の時計が同期していないなど時間の基準が異なっていても、その時間のずれを相殺することができるため、往復遅延を測定することができる。

また、本実施形態によれば、時刻算出部１０２は、取得情報テーブルを参照して、特定のパケットの第１のパケット転送装置と第２のパケット転送装置との通過時刻を算出する。
これにより、パケット転送装置２０が、個々のパケットの通過時間を出力することはできなくても、フロー情報取得部１０１が取得したパケット数とそれに対応するフロー時刻から、特定のパケットの通過時刻を推定して転送の遅延時間を算出できる。

また、本実施形態によれば、フロー情報取得部１０１は、各パケット転送装置から取得したフロー情報のフロー時刻情報に代えて、特定のフローのフロー時刻情報を用いて基準時刻情報としている。これにより、往復遅延算出部１０３は、往復遅延をなるべく近い時刻における往路と復路の合計値とすることができる。

なお、上述した実施形態における往復遅延推定装置の一部、例えば、フロー情報取得部、時刻算出部、及び往復遅延算出部をコンピュータで実現するようにしても良い。その場合、この制御機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、往復遅延推定装置に内蔵されたコンピュータシステムであって、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。

また、上述した実施形態における往復遅延推定装置の一部、または全部を、ＬＳＩ（Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｉｏｎ）等の集積回路として実現しても良い。往復遅延推定装置及び往復遅延推定装置の各機能ブロックは個別にプロセッサ化してもよいし、一部、または全部を集積してプロセッサ化しても良い。また、集積回路化の手法はＬＳＩに限らず専用回路、または汎用プロセッサで実現しても良い。また、半導体技術の進歩によりＬＳＩに代替する集積回路化の技術が出現した場合、当該技術による集積回路を用いても良い。

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

１・・・往復遅延推定システム、１０・・・往復遅延推定装置、２０、２０−１〜２０−５・・・パケット転送装置、１０１・・・フロー情報取得部、１０２・・・時刻算出部、１０３・・・往復遅延算出部、１０４・・・ＤＢ（データベース）

Claims (4)

1. 第１のパケット転送装置から第２のパケット転送装置へ伝送される第１のフローのうち第ｉ個目（ただしｉは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−１の時刻と、前記第１のフローのうち第ｊ個目（ただしｊは、２以上の整数でｉより大きい）のパケットが前記第２のパケット転送装置を通過する第２−１の時刻と、前記第１のフローのうち第ｋ個目（ただしｋは、３以上の整数でｉ及びｊより大きい）のパケットが前記第１のパケット転送装置を通過する第３−１の時刻と、前記第１のフローのうち第ｌ個目（ただしｌは、４以上の整数でｉ、ｊ、及びｋより大きい）のパケットが前記第２のパケット転送装置を通過する第４−１の時刻とを用いて、前記第１のパケット転送装置を前記第ｊ個目のパケットが通過した前記第１のフローの第１の基準時刻を第１−１の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｋ個目のパケットが通過した前記第１のフローの第２の基準時刻を第２−１の基準時刻として算出し、
   前記第２のパケット転送装置から前記第１のパケット転送装置へ伝送される第２のフローのうち第ｍ個目（ただしｍは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−２の時刻と、前記第２のフローのうち第ｎ個目（ただしｎは、２以上の整数でｍより大きい）のパケットが前記第２のパケット転送装置を通過する第２−２の時刻と、前記第２のフローのうち第ｏ個目（ただしｏは、３以上の整数でｍ及びｎより大きい）のパケットが前記第１のパケット転送装置を通過する第３−２の時刻と、前記第２のフローのうち第ｐ個目（ただしｐは、４以上の整数でｍ、ｎ、及びｏより大きい）のパケットが前記第２のパケット転送装置を通過する第４−２の時刻とを用いて、前記第１のパケット転送装置を前記第ｎ個目のパケットが通過した前記第２のフローの前記第１の基準時刻を第１−２の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｏ個目のパケットが通過した前記第２のフローの前記第２の基準時刻を第２−２の基準時刻として算出する時刻算出部と、
   算出された前記第１−１の基準時刻と、前記第１−２の基準時刻と、前記第２−１の基準時刻と、前記第２−２の基準時刻とともに、前記第２−１の時刻と、前記第２−２の時刻と、前記第３−１の時刻と、前記第３−２の時刻と、を用いて、前記第１のパケット転送装置と前記第２のパケット転送装置の間の往復遅延を推定する往復遅延算出部と、
   を備えることを特徴とする遅延推定装置。
2. 前記時刻算出部は、
   前記第２のパケット転送装置を前記第２−１の時刻に通過した前記第１のフローのパケット数から、前記第１のパケット転送装置を前記第１−１の時刻に通過した前記第１のフローのパケット数を減算した値を、前記第１のパケット転送装置を前記第１−１の時刻から前記第３−１の時刻の間に通過した前記第１のフローのパケット数で除算した値に、前記第１−１の時刻と前記第３−１の時刻との差を乗じて、当該乗算を行った結果に前記第１−１の時刻を加算して前記第１−１の基準時刻を算出し、
   前記第１のパケット転送装置を前記第３−１の時刻に通過した前記第１のフローのパケット数から、前記第２のパケット転送装置を前記第２−１の時刻に通過した前記第１のフローのパケット数を減算した値を、前記第２のパケット転送装置を前記第２−１の時刻から前記第４−１の時刻の間に通過した前記第１のフローのパケット数で除算した値に、前記第２−１の時刻と前記第４−１の時刻との差を乗じて、当該乗算を行った結果に前記第２−１の時刻を加算して前記第２−１の基準時刻を算出し、
   前記第２のパケット転送装置を前記第２−２の時刻に通過した前記第２のフローのパケット数から、前記第１のパケット転送装置を前記第１−２の時刻に通過した前記第２のフローのパケット数を減算した値を、前記第１のパケット転送装置を前記第１−２の時刻から前記第３−２の時刻の間に通過した前記第２のフローのパケット数で除算した値に、前記第１−２の時刻と前記第３−２の時刻との差を乗じて、当該乗算を行った結果に前記第１−２の時刻を加算して前記第１−２の基準時刻を算出し、
   前記第１のパケット転送装置を前記第３−２の時刻に通過した前記第２のフローのパケット数から、前記第２のパケット転送装置を前記第２−２の時刻に通過した前記第２のフローのパケット数を減算した値を、前記第２のパケット転送装置を前記第２−２の時刻から前記第４−２の時刻の間に通過した前記第２のフローのパケット数で除算した値に、前記第２−２の時刻と前記第４−２の時刻との差を乗じて、当該乗算を行った結果に前記第２−２の時刻を加算して前記第２−２の基準時刻を算出する
   ことを特徴とする請求項１に記載の遅延推定装置。
3. 遅延推定装置における方法において、
   時刻算出部が、第１のパケット転送装置から第２のパケット転送装置へ伝送される第１のフローうち第ｉ個目（ただしｉは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−１の時刻と、前記第１のフローのうち第ｊ個目（ただしｊは、２以上の整数でｉより大きい）のパケットが前記第２のパケット転送装置を通過する第２−１の時刻と、前記第１のフローのうち第ｋ個目（ただしｋは、３以上の整数でｉ及びｊより大きい）のパケットが前記第１のパケット転送装置を通過する第３−１の時刻と、前記第１のフローのうち第ｌ個目（ただしｌは、４以上の整数でｉ、ｊ、及びｋより大きい）のパケットが前記第２のパケット転送装置を通過する第４−１の時刻とを用いて、前記第１のパケット転送装置を前記第ｊ個目のパケットが通過した前記第１のフローの第１の基準時刻を第１−１の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｋ個目のパケットが通過した前記第１のフローの第２の基準時刻を第２−１の基準時刻として算出し、
   前記第２のパケット転送装置から前記第１のパケット転送装置へ伝送される第２のフローのうち第ｍ個目（ただしｍは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−２の時刻と、前記第２のフローのうち第ｎ個目（ただしｎは、２以上の整数でｍより大きい）のパケットが前記第２のパケット転送装置を通過する第２−２の時刻と、前記第２のフローのうち第ｏ個目（ただしｏは、３以上の整数でｍ及びｎより大きい）のパケットが前記第１のパケット転送装置を通過する第３−２の時刻と、前記第２のフローのうち第ｐ個目（ただしｐは、４以上の整数でｍ、ｎ、及びｏより大きい）のパケットが前記第２のパケット転送装置を通過する第４−２の時刻とを用いて、前記第１のパケット転送装置を前記第ｎ個目のパケットが通過した前記第２のフローの前記第１の基準時刻を第１−２の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｏ個目のパケットが通過した前記第２のフローの前記第２の基準時刻を第２−２の基準時刻として算出する時刻算出手順と、
   往復遅延算出部が、前記時刻算出手順によって算出された前記第１−１の基準時刻と、前記第１−２の基準時刻と、前記第２−１の基準時刻と、前記第２−２の基準時刻とともに、前記第２−１の時刻と、前記第２−２の時刻と、前記第３−１の時刻と、前記第３−２の時刻と、を用いて、前記第１のパケット転送装置と前記第２のパケット転送装置の間の往復遅延を推定する往復遅延算出手順と、
   を含むことを特徴とする遅延推定方法。
4. 往復遅延推定装置のコンピュータに、
   第１のパケット転送装置から第２のパケット転送装置へ伝送される第１のフローうち第ｉ個目（ただしｉは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−１の時刻と、前記第１のフローのうち第ｊ個目（ただしｊは、２以上の整数でｉより大きい）のパケット転送装置を通過する第２−１の時刻と、前記第１のフローのうち第ｋ個目（ただしｋは、３以上の整数でｉ及びｊより大きい）のパケットが前記第１のパケット転送装置を通過する第３−１の時刻と、前記第１のフローのうち第ｌ個目（ただしｌは、４以上の整数でｉ、ｊ、及びｋより大きい）のパケットが前記第２のパケット転送装置を通過する第４−１の時刻とを用いて、前記第１のパケット転送装置を前記第ｊ個目のパケットが通過した前記第１のフローの第１の基準時刻を第１−１の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｋ個目のパケットが通過した前記第１のフローの第２の基準時刻を第２−１の基準時刻として算出する時刻算出し、
   前記第２のパケット転送装置から前記第１のパケット転送装置へ伝送される第２のフローのうち第ｍ個目（ただしｍは、１以上の整数）のパケットが前記第１のパケット転送装置を通過する第１−２の時刻と、前記第２のフローのうち第ｎ個目（ただしｎは、２以上の整数でｍより大きい）のパケットが前記第２のパケット転送装置を通過する第２−２の時刻と、前記第２のフローのうち第ｏ個目（ただしｏは、３以上の整数でｍ及びｎより大きい）のパケットが前記第１のパケット転送装置を通過する第３−２の時刻と、前記第２のフローのうち第ｐ個目（ただしｐは、４以上の整数でｍ、ｎ、及びｏより大きい）のパケットが前記第２のパケット転送装置を通過する第４−２の時刻とを用いて、前記第１のパケット転送装置を前記第ｎ個目のパケットが通過した前記第２のフローの前記第１の基準時刻を第１−２の基準時刻として算出し、及び前記第２のパケット転送装置を前記第ｏ個目のパケットが通過した前記第２のフローの前記第２の基準時刻を第２−２の基準時刻として算出する時刻算出手順と、
   前記時刻算出手順によって算出された前記第１−１の基準時刻と、前記第１−２の基準時刻と、前記第２−１の基準時刻と、前記第２−２の基準時刻とともに、前記第２−１の時刻と、前記第２−２の時刻と、前記第３−１の時刻と、前記第３−２の時刻と、を用いて、前記第１のパケット転送装置と前記第２のパケット転送装置の間の往復遅延を推定する往復遅延算出手順と、
   を実行させるための遅延推定プログラム。

Images