(57)【特許請求の範囲】
【請求項１】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom  Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する該BFとは別のBF’と、を格納し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF’のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNにのみフラグが立っているか（つまりSYNにのみフラグが立っており、他のTCPフラグは立っていないか）を判定し、
もしSYNのみであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでなければ、前記品質推定手段に通知し、
前記品質推定手段において、パケットにACKフラグがたっており、かつ、SYN及びRSTにはフラグが立っていないかを確認し、もしそうでなければそれ以上の処理は行わず、そうである場合には、K個のビット位置に対応する前記時刻管理テーブルの時刻情報を読み出し、その中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力し、
その後、前記フロー管理手段が、前記BF’の該当するK箇所にビットを立て、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグのみが立っていれば、該BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する、
以上の手順を一定期間継続する
ことを特徴とするフロー通信品質推定方法。
【請求項２】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
逆転フローキー抽出手段と、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom  Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する該BFとは別のBF’と、を格納し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF’のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNが立っているかを判定し、
もしSYNであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
前記逆転フローキー抽出手段が、
前記ノードＢから前記ノードＡ方向のパケットストリームの到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていなければ、そのパケットのフローキーを抽出し、逆転フローキーを生成し、前記メモリのBF’へ入力し、Ｋ個のハッシュ値に対応するビットの位置が全て１であれば、何も行わず、１つでも０があれば、前記品質推定手段に通知し、
前記品質推定手段において、Ｋ個のビット位置に対応する前記時刻管理テーブルの時刻情報を読み出し、その中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力し、
その後、前記逆転フローキー抽出手段が、前記逆転フローキー抽出手段において、前記BF’の該当するK箇所にビットを立てる
以上の手順を一定期間継続する
ことを特徴とするフロー通信品質推定方法。
【請求項３】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom  Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BF1,BF2と同様の構成を有する該BFとは別のBF’と、該BF’に対するBF1’、BF2’と、を格納し、
奇数番目の測定期間では測定開始時に前記BF1,BF1’をクリアし、書き込み対象となるBloom  FilterをBF=BF1、BF’=BF1’と設定し、偶数番目の測定期間では測定開始時に前記BF2,BF2’をクリアし、書き込み対象となるBloom  FilterをBF=BF2,BF’=BF2’と設定し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1’とBF2’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記BF1’においてハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合、またはBF2’においてハッシュ値が全て１である場合には、既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記BF1’かつBF2’においてハッシュ値が全て１でない場合は、
前記BF1においてハッシュ値が全て１、または、BF2においてハッシュ値が全て１の場合、前記到着したパケットにTCPの通信開始フラグSYNのみにフラグが立っているかを判定し、
もしSYNのみであれば、前記BFのK個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでない場合、ACKにフラグが立っており、かつ、SYN及びRSTにはフラグが立っていないのであれば、前記BF1,BF2の両方においてハッシュ値が全て１の場合は、該BFの管理時刻テーブルの時刻情報を読み出して、前記品質推定手段に通知する往復伝播遅延時間算出処理を行い、その後、前記BF’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF1においてハッシュ値が全て１であり、前記BF1’においてハッシュ値が全て１ではない場合は、該BF1の時刻管理テーブルの時刻を読み出し、前記品質推定手段に通知する往復伝播遅延時間算出処理を行い、その後、前記BF1’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF2においてハッシュ値が全て１であり、前記BF2’においてハッシュ値が全て１ではない場合は、該BF2の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知する往復伝播遅延時間算出処理を行い、その後、前記BF2’において該当するＫ箇所にビットを立て、
前記BF1,BF2のどちらか一方においても、ハッシュ値が全て１ではない場合は、前記到着したパケットを確率１／Ｎ（Ｎは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合は、該パケットのパケットヘッダを読み込んで、TCP通信開始を表すSYNフラグのみが立っていれば、前記BFのＫ個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのＫ個の時刻エントリ情報を現在の時刻に更新する、
以上の手順を一定期間継続し、
前記往復伝播遅延時間算出処理は、
前記品質推定手段が、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力する
ことを特徴とするフロー通信品質推定方法。
【請求項４】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
逆転フローキー抽出手段、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom  Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BFと同様の構成を有する該BFとは別のBF’と、該BF’に対するBF1’、BF2’を格納し、
奇数番目の測定期間では測定開始時に前記BF1、BF1’をクリアし、書き込み対象となるBloom  FilterをBF=BF1、BF’=BF1’と設定し、偶数番目の測定期間では測定開始時に前記BF2、BF2’をクリアし、書き込み対象となるBloom  FilterをBF=BF2、BF’=BF2’と設定し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1’とBF2’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記BF1’のハッシュ値が全て１である場合、または、BF2’のハッシュ値が全て１である場合は、それ以上の処理は行わず、
前記BF1’かつBF2’においてハッシュ値が全て１ではない場合で、
かつ、前記BF1においてハッシュ値が全て１またはBF2においてハッシュ値が全て１の場合は、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックし、
もしSYNであれば、前記BFにおいてK個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記BF1においてハッシュ値が全て１でなく、BF2においても全て１でない場合は、
前記到着したパケットを確率1/Nでサンプリングするか決定し、サンプリングする場合は、該パケットにSYNフラグが立っていれば、前記BFにビットを立て、その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
一方、前記逆転フローキー抽出手段が、前記ノードBからノードA方向のパケットストリームに対し、到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていない場合にはそのパケットのフローキーを読み出し、逆転フローキーを作成し、前記BF’へ入力し、
前記BF1’においてハッシュ値が全て１ではなく、BF2’においてもハッシュ値が全て１ではない場合で、
前記BF1、BF2の両方においてハッシュ値が全て１の場合（条件Ａ）は、前記BFの時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、前記BF’にビットを立て、
前記条件Ａを満たさず、該BF１においてハッシュ値が全て１であり、前記BF1’  においてハッシュ値が全て１でない場合(条件Ｂ)は、該BF1の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、往復伝播遅延時間推定処理を行いその後、前記フロー管理手段が、該BF1’にビットを立て、
前記条件Ｂを満たさず、前記BF2においてハッシュ値が全て１であり、前記BF2’  においてハッシュ値が全て１でない場合（条件Ｃ）は、該BF2の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、BF2’にビットを立て、
前記条件Ｃを満たさない場合は何もしない、
以上の手順を一定期間継続し、
前記往復伝播遅延時間推定処理は、
前記品質推定手段が、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定する
ことを特徴とするフロー通信品質推定方法。
【請求項５】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom  Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する、該BFとは別のBF’と、を格納するメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出すると共に、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定して出力する品質推定手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、前記ルータＡと前記ルータＢ間のフローの通信品質を推定するフロー管理手段と、
を有し、
前記フロー管理手段は、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF’のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNにのみフラグが立っているか（つまり、SYNにのみフラグが立っており、他のTCPフラグは立っていないか）を判定し、
もしSYNのみであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでなければ、前記品質推定手段に前記往復伝播遅延時間を求めさせ、その後、前記フロー管理手段が、前記BF’の該当するK箇所にビットを立て、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグのみが立っていれば、該BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する、手段を含み、
前記品質推定手段は、
パケットにACKフラグが立っておりかつSYNおよびRSTにはフラグが立っていないかを確認し、もしそうでなければそれ以上の処理は行わず、そうである場合には、K個のビット位置に対応する前記時刻管理テーブルの時刻情報を読み出し、その中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力する手段を含む、
ことを特徴とするフロー通信品質推定装置。
【請求項６】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
フロー管理手段、
逆転フローキー抽出手段と、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom  Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する該BFとは別のBF’と、を格納するメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、前記ルータＡと前記ルータＢ間のフローの通信品質を推定するフロー管理手段と、
前記ノードＢから前記ノードＡ方向のパケットストリームが到着すると、到着パケットのフローキーを抽出し、逆転フローキーを生成し、前記メモリのBF’へ入力する逆転フローキー抽出手段と、
前記フロー管理手段、または、前記逆転フローキー抽出手段の通知により、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定して出力する品質推定手段と、
を有し、
前記フロー管理手段は、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF’のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNが立っているかを判定し、
もしSYNであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する手段を含み、
前記逆転フローキー抽出手段は、
前記ノードＢから前記ノードＡ方向のパケットストリームの到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていなければ、該パケットのフローキーを抽出し、逆転フローキーを生成し、前記メモリのBF’へ入力する手段と、
前記BF’のＫ個のハッシュ値に対応するビットの位置が全て１であれば、何も行わず、１つでも０があれば、前記品質推定手段に通知し、該品質推定手段により前記往復伝播遅延時間が求められた後に、前記BF’の該当するK箇所にビットを立てる手段と、を含む、
ことを特徴とするフロー通信品質推定装置。
【請求項７】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom  Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BF1,BF2と同様の構成を有する該BFとは別のBF’と、該BF’に対するBF1’、BF2’と、を格納し、奇数番目の測定期間では測定開始時に前記BF1,BF1’をクリアし、書き込み対象となるBloom  FilterをBF=BF1、BF’=BF1’と設定し、偶数番目の測定期間では測定開始時に前記BF2,BF2’をクリアし、書き込み対象となるBloom  FilterをBF=BF2,BF’=BF2’と設定されるメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出すると共に、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定する品質推定手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1’とBF2’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、前記品質推定手段と共にフロー通信品質推定処理を行うフロー管理手段と、
を有し、
前記フロー管理手段は、
前記BF1’においてハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合、またはBF2’においてハッシュ値が全て１である場合には、既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記BF1’かつBF2’においてハッシュ値が全て１でない場合は、
前記BF1においてハッシュ値が全て１、または、BF2においてハッシュ値が全て１の場合、前記到着したパケットにTCPの通信開始フラグSYNのみにフラグが立っているかを判定し、
もしSYNのみであれば、前記BFのK個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでない場合、ACKフラグが立っており、かつ、SYN及びRSTにはフラグが立っていないのであれば、前記BF1,BF2の両方においてハッシュ値が全て１の場合は、該BFの管理時刻テーブルの時刻情報を読み出して、前記品質推定手段に通知し、前記BF’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF1においてハッシュ値が全て１であり、前記BF1’においてハッシュ値が全て１ではない場合は、該BF1の時刻管理テーブルの時刻を読み出して、前記品質推定手段に通知し、その後、前記フロー管理手段において、前記BF1’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF2においてハッシュ値が全て１であり、前記BF2’においてハッシュ値が全て１ではない場合は、該BF2の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、その後、前記BF2’において該当するＫ箇所にビットを立て、
前記BF1,BF2のどちらか一方においても、ハッシュ値が全て１ではない場合は、前記到着したパケットを確率１／Ｎ（Ｎは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合は、該パケットのパケットヘッダを読み込んで、TCP通信開始を表すSYNフラグのみが立っていれば、前記BFのＫ個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのＫ個の時刻エントリ情報を現在の時刻に更新する、手段を含む
ことを特徴とするフロー通信品質推定装置。
【請求項８】
通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
逆転フローキー抽出手段と、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom  Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BFと同様の構成を有する該BFとは別のBF’と、該BF’に対するBF1’、BF2’を格納し、奇数番目の測定期間では測定開始時に前記BF1、BF1’をクリアし、書き込み対象となるBloom  FilterをBF=BF1、BF’=BF1’と設定し、偶数番目の測定期間では測定開始時に前記BF2、BF2’をクリアし、書き込み対象となるBloom  FilterをBF=BF2、BF’=BF2’と設定されるメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1’とBF2’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行うフロー管理手段と、
前記ノードBからノードA方向のパケットストリームに対し、到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていない場合には、該パケットのフローキーを読み出し、逆転フローキーを作成し、前記BF’へ入力する逆転フローキー抽出手段と、
を有し、
前記フロー管理手段の通知により、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定する品質推定手段と、
を有し、
前記フロー管理手段は、
前記BF1’のハッシュ値が全て１である場合、または、BF2’のハッシュ値が全て１である場合は、それ以上の処理は行わず、
前記BF1’  かつBF2’においてハッシュ値が全て１ではない場合で、
かつ、前記BF1においてハッシュ値が全て１またはBF2においてハッシュ値が全て１の場合は、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックし、
もしSYNであれば、前記BFにおいてK個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記BF1においてハッシュ値が全て１でなく、BF2においても全て１でない場合は、
前記到着したパケットを確率1/Nでサンプリングするか決定し、サンプリングする場合は、該パケットにSYNフラグが立っていれば、前記BFにビットを立て、その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する手段を含み、
前記逆転フローキー抽出手段は、
前記BF1’においてハッシュ値が全て１ではなく、BF2’においてもハッシュ値が全て１ではない場合で、
前記BF1、BF2の両方においてハッシュ値が全て１の場合（条件Ａ）は、前記品質推定手段に通知し、
前記品質推定手段が、前記BFの時刻管理テーブルの時刻情報を読み出して、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、前記BF’にビットを立て、
前記条件Ａを満たさず、該BF１においてハッシュ値が全て１であり、BF1’  においてハッシュ値が全て１でない場合(条件Ｂ)は、前記品質推定手段に通知し、該品質推定手段が、該BF1の時刻管理テーブルの時刻情報を読み出して、往復伝播遅延時間推定処理を行いその後、前記フロー管理手段が、該BF1’にビットを立て、
前記条件Ｂを満たさず、前記BF2においてハッシュ値が全て１であり、前記BF2’  においてハッシュ値が全て１でない場合（条件Ｃ）は、前記品質推定手段に通知し、該品質推定手段が、前記BF2の時刻管理テーブルの時刻情報を読み出して、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、BF2’にビットを立て、
前記条件Ｃを満たさない場合は何もしない、手段を含む
ことを特徴とするフロー通信品質推定装置。
【請求項９】
請求項５乃至８のいずれか１項に記載のフロー通信品質推定装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フロー通信品質推定方法及び装置及びプログラムに係り、特に、ＩＰ(Internet Protocol)ネットワークの通信品質状態を管理するためのフロー通信品質推定方法及び装置及びプログラムに関する。詳しくは、ＩＰネットワークの通信品質を、トラヒックの能動的な測定は行わず、かつ、ネットワークの全パケットキャプチャを行うことなく推定するためのフロー通信品質推定方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
IPネットワークが広く利用されてくるに伴って、IPネットワーク上での通信品質保証に対する要求が高まっている。それに伴い、ネットワークを流れるトラヒックを測定して現在の通信品質状態を把握することが重要になってきている。エンドエンド遅延時間やパケット損失率、スループットといった品質を把握する直接的な方法としては、エンドエンド間で試験パケットを送受信することにより品質を能動的に測定する方法がある。pingコマンドによる往復遅延測定や、他pathchar（非特許文献１参照）等がある。他には、例えば、着目するエンドホスト間において、試験パケットによるラウンドトリップタイムやパケット損失率の測定および経路上のボトルネック帯域の測定を実施し、かつ、実際にTCPで通信を行ってスループットを測定し、ウインドーサイズを徐々に大きくしていったときにTCPスループットが増加するかどうか等を詳細に解析する方法がある（例えば、非特許文献２参照）。
【０００３】
しかし、一般にこれらの方法は、ある特定のエンドホスト間で品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した方法であり、ネットワーク提供者がネットワーク内の通信を全体的に管理するのに直接適用すると測定コストの増大およびネットワークへの測定負荷の増大が生じてしまう。具体的には、監視対象となるネットワークの入り側および出側全てに試験パケット送受信機を設置して、試験パケットを送信することによって品質測定を能動的に行う必要があり、測定装置コストが増大してしまう。さらに、試験パケットをネットワークへ付加するため、ネットワークへ余分なトラヒックが加わるという問題と、その結果、試験トラヒックによってネットワークの品質自体が劣化してしまうという問題があった。
【０００４】
上記能動的測定以外の方法として、着目するエンドエンド間トラヒックの流れる箇所において、そこを通過するパケットをキャプチャして解析し、ネットワークの状態を把握する方法がある。例えば、ACEと呼ばれるツールでは、パケットキャプチャデータから、エンド間のレスポンス時間や、その内訳（ネットワーク内での遅延とサーバでの遅延）を分析可能とする方法がある（例えば、非特許文献３参照）。また、往復遅延等を分析可能なツールもある（例えば、非特許文献４参照）。
【０００５】
しかし、一般に、ある特定のエンドホスト間で品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した方法であり、ネットワーク全体でのユーザフロー通信品質を測定するためには、回線を流れるパケットを全てキャプチャしてパケットヘッダ情報の解析、およびフロー情報の解析が必要だが、回線速度が高速になるにつれて全てのパケットをキャプチャして処理することが困難になってきている。
【０００６】
そこで、本発明者らは、双方向に流れるパケットストリームに対して、パケットサンプリングを行って必要なTCPパケットを蓄積した後、オフラインで蓄積パケットを処理することで、ネットワーク全体の品質を推定する方法を提案した（非特許文献５参照）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】http://www.caida.org/tools/utilities/others/pathchar/
【非特許文献２】的場 一峰, 阿多 信吾, 村田 正幸, "インターネットにおける計測に基づいたボトルネック特定手法," 電子情報通信学会 テレコミュニケーションマネジメント研究会, pp. 65 - 70, November 2000.
【非特許文献３】http://www.opnet.com/solutions/application_performance/ace.html
【非特許文献４】http://www.tcptrace.org/
【非特許文献５】川原他, ``フローサンプリングによるフロー品質推定方法,'' 電子情報通信学会2009年ソサイエティ大会, B-7, 2009.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の非特許文献５に示す方式では、能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質を推定することを可能にしている。しかしながら、リアルタイムに品質を推定できないという問題点があった。
【０００９】
本発明は、上記の点に鑑みなされたもので、能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、オンラインで品質を推定する方法およびその装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明（請求項１）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する該BFとは別のBF'と、を格納し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF'のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF'のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNにのみフラグが立っているか（つまりSYNにのみフラグが立っており、他のTCPフラグは立っていないか）を判定し、
もしSYNのみであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでなければ、前記品質推定手段に通知し、
前記品質推定手段において、パケットにACKフラグがたっており、かつ、SYN及びRSTにはフラグが立っていないかを確認し、もしそうでなければそれ以上の処理は行わず、そうである場合には、K個のビット位置に対応する前記時刻管理テーブルの時刻情報を読み出し、その中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力し、
その後、前記フロー管理手段が、前記BF'の該当するK箇所にビットを立て、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグのみが立っていれば、該BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する、
以上の手順を一定期間継続することを特徴とする。
【００１１】
また、本発明（請求項２）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
逆転フローキー抽出手段と、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する該BFとは別のBF'と、を格納し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF'のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF'のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNが立っているかを判定し、
もしSYNであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
前記逆転フローキー抽出手段が、
前記ノードＢから前記ノードＡ方向のパケットストリームの到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていなければ、そのパケットのフローキーを抽出し、逆転フローキーを生成し、前記メモリのBF'へ入力し、Ｋ個のハッシュ値に対応するビットの位置が全て１であれば、何も行わず、１つでも０があれば、前記品質推定手段に通知し、
前記品質推定手段において、Ｋ個のビット位置に対応する前記時刻管理テーブルの時刻情報を読み出し、その中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力し、
その後、前記逆転フローキー抽出手段が、前記逆転フローキー抽出手段において、前記BF'の該当するK箇所にビットを立てる
以上の手順を一定期間継続することを特徴とする。
【００１２】
また、本発明（請求項３）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom  Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BF1,BF2と同様の構成を有する該BFとは別のBF’と、該BF’に対するBF1’、BF2’と、を格納し、
奇数番目の測定期間では測定開始時に前記BF1,BF1’をクリアし、書き込み対象となるBloom  FilterをBF=BF1、BF’=BF1’と設定し、偶数番目の測定期間では測定開始時に前記BF2,BF2’をクリアし、書き込み対象となるBloom  FilterをBF=BF2,BF’=BF2’と設定し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1’とBF2’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記BF1’においてハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合、またはBF2’においてハッシュ値が全て１である場合には、既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記BF1’かつBF2’においてハッシュ値が全て１でない場合は、
前記BF1においてハッシュ値が全て１、または、BF2においてハッシュ値が全て１の場合、前記到着したパケットにTCPの通信開始フラグSYNのみにフラグが立っているかを判定し、
もしSYNのみであれば、前記BFのK個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでない場合、ACKにフラグが立っており、かつ、SYN及びRSTにはフラグが立っていないのであれば、前記BF1,BF2の両方においてハッシュ値が全て１の場合は、該BFの管理時刻テーブルの時刻情報を読み出して、前記品質推定手段に通知する往復伝播遅延時間算出処理を行い、その後、前記BF’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF1においてハッシュ値が全て１であり、前記BF1’においてハッシュ値が全て１ではない場合は、該BF1の時刻管理テーブルの時刻を読み出し、前記品質推定手段に通知する往復伝播遅延時間算出処理を行い、その後、前記BF1’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF2においてハッシュ値が全て１であり、前記BF2’においてハッシュ値が全て１ではない場合は、該BF2の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知する往復伝播遅延時間算出処理を行い、その後、前記BF2’において該当するＫ箇所にビットを立て、
前記BF1,BF2のどちらか一方においても、ハッシュ値が全て１ではない場合は、前記到着したパケットを確率１／Ｎ（Ｎは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合は、該パケットのパケットヘッダを読み込んで、TCP通信開始を表すSYNフラグのみが立っていれば、前記BFのＫ個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのＫ個の時刻エントリ情報を現在の時刻に更新する、
以上の手順を一定期間継続し、
前記往復伝播遅延時間算出処理は、
前記品質推定手段が、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力する
ことを特徴とする。
【００１３】
また、本発明（請求項４）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置における通信品質推定方法において、
前記フロー通信品質推定装置は、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
逆転フローキー抽出手段、
フローの通信状態を管理するためのメモリを有し、
前記メモリに、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BFと同様の構成を有する該BFとは別のBF'と、該BF'に対するBF1'、BF2'を格納し、
奇数番目の測定期間では測定開始時に前記BF1、BF1'をクリアし、書き込み対象となるBloom FilterをBF=BF1、BF'=BF1'と設定し、偶数番目の測定期間では測定開始時に前記BF2、BF2'をクリアし、書き込み対象となるBloom FilterをBF=BF2、BF'=BF2'と設定し、
前記パケットヘッダ解析手段が、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析ステップと、
前記フロー管理手段において、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1'とBF2'のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行う品質推定ステップを行い、
前記品質推定ステップは、
前記BF1'のハッシュ値が全て１である場合、または、BF2'のハッシュ値が全て１である場合は、それ以上の処理は行わず、
前記BF1'かつBF2'においてハッシュ値が全て１ではない場合で、
かつ、前記BF1においてハッシュ値が全て１またはBF2においてハッシュ値が全て１の場合は、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックし、
もしSYNであれば、前記BFにおいてK個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記BF1においてハッシュ値が全て１でなく、BF2においても全て１でない場合は、
前記到着したパケットを確率1/Nでサンプリングするか決定し、サンプリングする場合は、該パケットにSYNフラグが立っていれば、前記BFにビットを立て、その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
一方、前記逆転フローキー抽出手段が、前記ノードBからノードA方向のパケットストリームに対し、到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていない場合にはそのパケットのフローキーを読み出し、逆転フローキーを作成し、前記BF'へ入力し、
前記BF1'においてハッシュ値が全て１ではなく、BF2'においてもハッシュ値が全て１ではない場合で、
前記BF1、BF2の両方においてハッシュ値が全て１の場合（条件Ａ）は、前記BFの時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、前記BF'にビットを立て、
前記条件Ａを満たさず、該BF１においてハッシュ値が全て１であり、前記BF1' においてハッシュ値が全て１でない場合(条件Ｂ)は、該BF1の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、往復伝播遅延時間推定処理を行いその後、前記フロー管理手段が、該BF1'にビットを立て、
前記条件Ｂを満たさず、前記BF2においてハッシュ値が全て１であり、前記BF2' においてハッシュ値が全て１でない場合（条件Ｃ）は、該BF2の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、BF2'にビットを立て、
前記条件Ｃを満たさない場合は何もしない、
以上の手順を一定期間継続し、
前記往復伝播遅延時間推定処理は、
前記品質推定手段が、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定することを特徴とする。
【００１４】
また、本発明（請求項５）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する、該BFとは別のBF'と、を格納するメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出すると共に、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定して出力する品質推定手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF'のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、前記ルータＡと前記ルータＢ間のフローの通信品質を推定するフロー管理手段と、
を有し、
前記フロー管理手段は、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF'のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNにのみフラグが立っているか（つまり、SYNにのみフラグが立っており、他のTCPフラグは立っていないか）を判定し、
もしSYNのみであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでなければ、前記品質推定手段に前記往復伝播遅延時間を求めさせ、その後、前記フロー管理手段が、前記BF'の該当するK箇所にビットを立て、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグのみが立っていれば、該BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する、手段を含み、
前記品質推定手段は、
パケットにACKフラグが立っておりかつSYNおよびRSTにはフラグが立っていないかを確認し、もしそうでなければそれ以上の処理は行わず、そうである場合には、K個のビット位置に対応する前記時刻管理テーブルの時刻情報を読み出し、その中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定し、該RTTiを出力する手段を含む、ことを特徴とする。
【００１５】
また、本発明（請求項６）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
フロー管理手段、
逆転フローキー抽出手段と、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom Filter(以下、「BF」と記す)と、
前記BFと同様の構成を有する該BFとは別のBF'と、を格納するメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、前記フロー管理手段に出力すると共に、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF'のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、前記ルータＡと前記ルータＢ間のフローの通信品質を推定するフロー管理手段と、
前記ノードＢから前記ノードＡ方向のパケットストリームが到着すると、到着パケットのフローキーを抽出し、逆転フローキーを生成し、前記メモリのBF'へ入力する逆転フローキー抽出手段と、
前記フロー管理手段、または、前記逆転フローキー抽出手段の通知により、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定して出力する品質推定手段と、
を有し、
前記フロー管理手段は、
前記ハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記ハッシュ関数から得られる前記BF'のK個のハッシュ値に対応するビットマップ上でいずれかのビットが０である場合は、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、前記到着したパケットにTCPの通信開始フラグSYNが立っているかを判定し、
もしSYNであれば、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記フローキーを前記BFのK個のハッシュ関数に入力した結果、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがある場合は、前記到着したパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合、該パケットのパケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する手段を含み、
前記逆転フローキー抽出手段は、
前記ノードＢから前記ノードＡ方向のパケットストリームの到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていなければ、該パケットのフローキーを抽出し、逆転フローキーを生成し、前記メモリのBF'へ入力する手段と、
前記BF'のＫ個のハッシュ値に対応するビットの位置が全て１であれば、何も行わず、１つでも０があれば、前記品質推定手段に通知し、該品質推定手段により前記往復伝播遅延時間が求められた後に、前記BF'の該当するK箇所にビットを立てる手段と、を含む、
ことを特徴とする。
【００１６】
また、本発明（請求項７）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom  Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BF1,BF2と同様の構成を有する該BFとは別のBF’と、該BF’に対するBF1’、BF2’と、を格納し、奇数番目の測定期間では測定開始時に前記BF1,BF1’をクリアし、書き込み対象となるBloom  FilterをBF=BF1、BF’=BF1’と設定し、偶数番目の測定期間では測定開始時に前記BF2,BF2’をクリアし、書き込み対象となるBloom  FilterをBF=BF2,BF’=BF2’と設定されるメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出すると共に、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old  iを読み出し、現在の時刻Tnowからその最も古い時刻T_old  iを差し引いた値Tnow  −  Told  iを該フローの往復伝播遅延時間RTTiとして推定する品質推定手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1’とBF2’のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、前記品質推定手段と共にフロー通信品質推定処理を行うフロー管理手段と、
を有し、
前記フロー管理手段は、
前記BF1’においてハッシュ関数から得られる各ハッシュ値に対応するビットマップ上のビットが全て1である場合、またはBF2’においてハッシュ値が全て１である場合には、既にエントリされているフローからのパケットと判断して、それ以上のフロー通信品質推定処理は行わず、
前記BF1’かつBF2’においてハッシュ値が全て１でない場合は、
前記BF1においてハッシュ値が全て１、または、BF2においてハッシュ値が全て１の場合、前記到着したパケットにTCPの通信開始フラグSYNのみにフラグが立っているかを判定し、
もしSYNのみであれば、前記BFのK個のビット位置に対応する前記時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNのみでない場合、ACKフラグが立っており、かつ、SYN及びRSTにはフラグが立っていないのであれば、前記BF1,BF2の両方においてハッシュ値が全て１の場合は、該BFの管理時刻テーブルの時刻情報を読み出して、前記品質推定手段に通知し、前記BF’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF1においてハッシュ値が全て１であり、前記BF1’においてハッシュ値が全て１ではない場合は、該BF1の時刻管理テーブルの時刻を読み出して、前記品質推定手段に通知し、その後、前記フロー管理手段において、前記BF1’において該当するＫ箇所にビットを立て、
前記BF1,BF2の両方においてハッシュ値が全て１ではなく、前記BF2においてハッシュ値が全て１であり、前記BF2’においてハッシュ値が全て１ではない場合は、該BF2の時刻管理テーブルの時刻情報を読み出して、前記品質推定手段に通知し、その後、前記BF2’において該当するＫ箇所にビットを立て、
前記BF1,BF2のどちらか一方においても、ハッシュ値が全て１ではない場合は、前記到着したパケットを確率１／Ｎ（Ｎは予め定める正の整数）でサンプリングするか決定し、サンプリングする場合は、該パケットのパケットヘッダを読み込んで、TCP通信開始を表すSYNフラグのみが立っていれば、前記BFのＫ個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立て、その後、K個のビット位置に対応する前記時刻管理テーブルのＫ個の時刻エントリ情報を現在の時刻に更新する、手段を含む
ことを特徴とする。
【００１７】
また、本発明（請求項８）は、通信網において、始点となるルータＡと終点となるルータＢをつなぐリンクのトラヒックを監視してフローの通信品質を推定するフロー通信品質推定装置であって、
パケットヘッダ解析手段、
フロー管理手段、
品質推定手段、
逆転フローキー抽出手段と、
ｂ個のパケットの到着時刻情報を格納する時刻テーブルと、
前記時刻テーブルと関連付けられ、入力キーに対してサイズｂの範囲内でハッシュ値を返す異なるＫ個のハッシュ関数と、サイズｂのビットマップを格納するBloom Filter(以下、「BF」と記す)と、該BFに対するBF1、BF2と、
前記BFと同様の構成を有する該BFとは別のBF'と、該BF'に対するBF1'、BF2'を格納し、奇数番目の測定期間では測定開始時に前記BF1、BF1'をクリアし、書き込み対象となるBloom FilterをBF=BF1、BF'=BF1'と設定し、偶数番目の測定期間では測定開始時に前記BF2、BF2'をクリアし、書き込み対象となるBloom FilterをBF=BF2、BF'=BF2'と設定されるメモリと、
到着したパケットのパケットヘッダからパケットのフローキーを抽出し、該パケットを後段のノードに送信するパケットヘッダ解析手段と、
前記パケットヘッダ解析手段から前記パケットのフローキーを前記メモリの前記BF1'とBF2'のＫ個のハッシュ関数に入力し、該ハッシュ関数から得られる各ハッシュ値に応じて、フロー通信品質推定処理を行うフロー管理手段と、
前記ノードBからノードA方向のパケットストリームに対し、到着パケットにACKフラグが立っており、かつ、RSTフラグが立っていない場合には、該パケットのフローキーを読み出し、逆転フローキーを作成し、前記BF'へ入力する逆転フローキー抽出手段と、
を有し、
前記フロー管理手段の通知により、前記時刻管理テーブルから読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの往復伝播遅延時間RTTiとして推定する品質推定手段と、
を有し、
前記フロー管理手段は、
前記BF1'のハッシュ値が全て１である場合、または、BF2'のハッシュ値が全て１である場合は、それ以上の処理は行わず、
前記BF1' かつBF2'においてハッシュ値が全て１ではない場合で、
かつ、前記BF1においてハッシュ値が全て１またはBF2においてハッシュ値が全て１の場合は、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックし、
もしSYNであれば、前記BFにおいてK個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新し、
もしSYNでなければ、何も行わず、
前記BF1においてハッシュ値が全て１でなく、BF2においても全て１でない場合は、
前記到着したパケットを確率1/Nでサンプリングするか決定し、サンプリングする場合は、該パケットにSYNフラグが立っていれば、前記BFにビットを立て、その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する手段を含み、
前記逆転フローキー抽出手段は、
前記BF'においてハッシュ値が全て１ではなく、BF2'においてもハッシュ値が全て１ではない場合で、
前記BF1、BF2の両方においてハッシュ値が全て１の場合（条件Ａ）は、前記品質推定手段に通知し、
前記品質推定手段が、前記BFの時刻管理テーブルの時刻情報を読み出して、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、前記BF'にビットを立て、
前記条件Ａを満たさず、該BF１においてハッシュ値が全て１であり、BF1' においてハッシュ値が全て１でない場合(条件Ｂ)は、前記品質推定手段に通知し、該品質推定手段が、該BF1の時刻管理テーブルの時刻情報を読み出して、往復伝播遅延時間推定処理を行いその後、前記フロー管理手段が、該BF1'にビットを立て、
前記条件Ｂを満たさず、前記BF2においてハッシュ値が全て１であり、前記BF2' においてハッシュ値が全て１でない場合（条件Ｃ）は、前記品質推定手段に通知し、該品質推定手段が、前記BF2の時刻管理テーブルの時刻情報を読み出して、往復伝播遅延時間推定処理を行い、その後、前記フロー管理手段が、BF2'にビットを立て、
前記条件Ｃを満たさない場合は何もしない、手段を含む
ことを特徴とする。
【００１８】
また、本発明（請求項９）は、請求項５乃至８のいずれか１項に記載のフロー通信品質推定装置を構成する各手段としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００１９】
上述のように、本発明によれば、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質をオンラインで推定することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明の基本概念を示す図である。
【図２】本発明が適用されるＩＰネットワークの基本構成の一例である。
【図３】本発明の第１の実施の形態におけるフロー通信品質推定装置の構成図である。
【図４】本発明の第１の実施の形態におけるフロー通信推定装置の品質推定動作のフローチャートである。
【図５】本発明の第２の実施の形態におけるフロー通信品質推定装置の構成図である。
【図６】本発明の第２の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【図７】本発明の第３の実施の形態におけるフロー通信品質推定装置の構成図である。
【図８】本発明の第３の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【図９】本発明の第４の実施の形態におけるフロー通信品質推定装置の構成図である。
【図１０】本発明の第４の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【発明を実施するための形態】
【００２１】
以下図面と共に、本発明の実施の形態を説明する。
【００２２】
まず、図１を用いて、本発明における基本的な考え方について述べる。
【００２３】
ルータＡとＢの間の監視点（後述する「フロー品質推定装置」）において、ルータＡからＢ方向及びルータＢからＡ方向のパケットを監視しているとする。図１のように、エンドホストaとbの間のフローiからSYNパケットが監視点に時刻Ti=10:00:01に到着したとし、それを時刻管理テーブルに記憶しておく。それに対する応答SYN-Ackが時刻Tnow=10:00:03に観測されたら、監視点からエンドホストbまでの往復遅延時間RTT_SAiをRTT_SAi=Tnow-Ti= 2秒、と推定できる。さらに、SYN-Ackに対するAckがTnow=10:00:05に観測されたら、エンドホストa-b間のRTTi=Tnow-Ti= 4秒と推定できる。（RTT_AiもRTT_SAi推定と同様に、RTT_Ai={SYN-Ack到着時刻-Ack到着時刻}により推定できる。）
本発明では、上記のRTT推定の動作をベースにしている。なお、フロー毎にTiを管理する代わりに、フローの通信状態を管理するためのメモリとしてBloom Filter(BF)を利用する。そうすることで、全フローの状態に要するフローテーブルメモリコストを削減する。BFでは、異なるK個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom Filter(以下、「BF」と記す)を用意する。また、b個の時刻情報をエントリする時刻テーブル（初期状態では全てをゼロにリセットされる）を用意する。このメモリは、パケットの到着時刻を記憶するために用いられ、BFにおけるビットマップのi番目のビット位置にビットが立つ場合に、本時刻管理テーブルのi番目のエントリにそのときの時刻をエントリする。
【００２４】
さらに、上述の時刻管理テーブルと関連付けられたBFの他に、BF'という別のBloom Filterも用意しておく。BFがフローの最初のパケット（SYNパケット）の到着情報を管理するために用いるのに対して、BF'ではSYNパケットの次のパケット（図１の例だとSYN-Ack）の到着有無の管理に用いる。
【００２５】
ここで、BFとBF'の２つのBFを用いるが、これは、初期状態ではビットマップの各ビットは全て０になっているが、以下に示す処理を行うことで、当該ビットマップが１で埋まっていくことになる。全て１になってしまうと、新規エントリの検出（ビットマップ上でビットが０となるところがある）が正しく動作しないため、一定期間毎にビットを０でクリアする必要がある。一方、RTTが非常に大きなものになると、TCP通信開始を表すSYNパケットを観測してから、その次のAckパケットを検出するのに時間を要する場合がある。そのための対処法として、BFクリアの周期を長めに設定することも考えられるが、測定周期が長くなると、BFのビットマップが１で埋まってしまい、正しく新規フローの検出ができない可能性がある。そこで、BFを２つ用意して、新規フローの検出（つまり、SYNパケット検出）について、BF1とBF2を交互に使用することで適切に検出し、RTT計算時には、BF１,BF2のいずれかに該当するエントリがあるかどうかを参照することで、RTTの長いAckに対しても対応できるようにする。
【００２６】
［第１の実施の形態］
図２は、本発明が適用されるIPネットワークの基本構成の一例を示す。図２に示すようにフロー通信品質推定装置１００はノード間のリンクに挿入される形態で利用される。あるいは、ノード（スイッチやルータ）において、パケットをポートへミラーして、そのポートの先にフロー通信品質推定装置を設置してもよい。
【００２７】
図３は、本発明の第１の実施の形態におけるフロー通信品質推定装置の構成を示す。
【００２８】
同図に示すフロー通信品質推定装置１００は、パケットヘッダ解析部１１０、フロー管理部１２０、品質推定部１３０、ブルームフィルタ（BF: Bloom Filter）１４１，１４２と時刻管理テーブル１４３を格納するメモリ１４０から構成される。
【００２９】
パケットヘッダ解析部１１０は、前段に位置するノードからパケットが到着すると、メモリ１４０の時刻管理テーブル１４３に登録し、パケットからフローキーを抽出し、フロー管理部１２０に出力すると共に、パケットを後段のノードに転送する。
【００３０】
フロー管理部１２０は、メモリ１４０のBF１４１、BF'１４２から各ハッシュ値に対応するビットマップ上のビットがヒット（全てのビットが１である状態）したかを判定し、その結果に基づいて時刻管理テーブル１４０を参照して、当該フロー通信品質推定装置１００からエンドホストまでの往復遅延時間RTTを推定する。
【００３１】
メモリ１４０のBF１４１は、異なるＫ個のハッシュ関数（それぞれが入力キーに対してｂ個の配列位置のいずれかにマッピングする）と、サイズｂのビットマップ（初期状態では全てをゼロにリセットされる）を格納するBloom Filter(以下、「BF」と記す)を用意する。また、時刻管理テーブル１４３と関連付けられたBF１４１の他にBF'１４２という別のブルームフィルタも用意しておく。
【００３２】
時刻管理テーブル１４３は、ｂ個の時刻情報を登録するテーブルであり、パケットの到着時刻を記憶するために用いられ、BF１４１におけるビットマップのｉ番目のビット位置にビットが立つ場合に、当該時刻管理テーブル１４３のｉ番目のエントリにそのときの時刻を登録する。
【００３３】
以下に、上記のフロー通信品質推定装置の動作を説明する。
【００３４】
以下では、ノードＡからノードＢの方向に流れるパケットストリームを対象とする。
【００３５】
図３において、前段ノードからパケットが到着したら、パケットヘッダ解析部１１０において、そのパケットのフローキー＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}を読み出し、フロー管理部１３０にフローキーを通知する。その後、パケットを後段ノードに転送する。また、パケットヘッダ解析部１１０は、メモリ１４０の時刻管理テーブル１４３にパケット到着時の時刻を格納する。
【００３６】
フロー管理部１３０は、パケットヘッダ解析部１２０から受信したフローキーをメモリ１４０のブルームフィルタBF'のK個のハッシュ関数に入力し、各ハッシュ値に対応するビットマップ上のビットが全て１かどうか（つまり、ハッシュ値がヒットしたかどうか）チェックし、以下の手順を実施する。
【００３７】
図４は、本発明の第１の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【００３８】
（１）各ハッシュ値に対応するビットマップ上のビットが全て１である場合、つまり、メモリ１４０のBF'においてハッシュ値がヒットした場合（ステップ１００、Ｙ）、既にエントリされているフローからのパケットと判断して、それ以上の処理は行わない。
【００３９】
（２）BF'のＫ個のハッシュ値に対応するビットマップ上いずれかのビットが０である場合、つまり、BF'においてハッシュ値がヒットしなかった場合（ステップ１００、Ｎ）、以下の手順を実施する。
【００４０】
（２−１）メモリ１４０の時刻管理テーブル１４０と関連付けられたBFのＫ個のハッシュ関数に入力し、各ハッシュ値に対応するビットマップ上のビットが全て１である場合（BFにおいてハッシュ値がヒットした場合）には（ステップ２００、Ｙ）、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックする（ステップ２１０）。
【００４１】
（２−１−１）もし、SYNフラグのみが立っている場合であれば（ステップ２１０，Ｙ）、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する（ステップ２１１）。
【００４２】
（２−１−２）もしSYNフラグのみにフラグが立っているのでなければ（ステップ２１０，Ｎ）、品質推定部１３０へ通知する。品質推定部１３０では、パケットにACKフラグが立っており、かつ、SYN及びRST(TCPコネクションを強制的に切断するときのフラグ)にフラグが立っていなければ（ステップ２２１、Ｙ）、K個のビット位置に対応する時刻管理テーブル１４３の時刻情報を読み出し、その中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - T_old iを該フローの往復伝播遅延時間RTTiとして推定する（ステップ２２２）。その後、BF'１４２を更新する（該当するK箇所にビットを立てる）（ステップ２２３）。
【００４３】
（２−２）BF１４１にＫ個のハッシュ関数を入力し、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがあれば、つまり、はじめてこのフローからパケットが到着したと判断されれば（BFにおいてハッシュ値がヒットしなかった場合）（ステップ２００、Ｎ）、そのパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定する（ステップ２３０）。サンプリングする場合（ステップ２３０、Ｙ）、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグのみが立っていれば（ステップ２３１、Ｙ）、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立てる（ステップ２３２）。その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する（ステップ２３３）。
【００４４】
フロー管理部１２０と品質推定部１３０により、上記の手順を一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。
【００４５】
また、ビットマップ上の時刻情報のうち、他のフローのSYN到着時にいくつかの時刻情報は上書きされるが、全部が上書きはされないであろうとみなして、最も古い時刻情報を当該フローのSYNパケット到着時刻とみなし、RTTを推定している。
【００４６】
なお、ステップ２３０でサンプリングを行う代わりに、ステップ１００への入力（パケット到着）時に、フローキーをハッシュ関数に入力し、その出力がi番目（０≦i≦b）の配列位置にマッピングされたとし、i/bの値があらかじめ定めたサンプリングレートp(0<p<1)よりも小さいときのみ、ステップ１００へ入力する、としてもよい。
【００４７】
［第２の実施の形態］
図５は、本発明の第２の実施の形態におけるフロー通信品質推定装置の構成を示す。
【００４８】
同図において、図１と同一構成部分には同一符号を付し、その説明を省略する。
【００４９】
同図に示すフロー通信品質推定装置２００は、図１の構成に逆転フローキー抽出部２５０を追加した構成である。
【００５０】
前述の第１の実施の形態では、ノードＡからノードＢ方向への片方向パケットのみを用いてRTTを推定したが、本実施の形態では、双方向パケットを用いてRTTを推定する。
【００５１】
このため、逆転フローキー抽出部２５０を設け、当該逆転フローキー抽出部２５０において、ノードＢからノードＡへのパケットからフローキーを抽出し、フロー管理部１２０に出力すると共に、ノードＢからノードＡへのパケットをノードＡ方向のノードに転送する。
【００５２】
図５において、ノードAからノードB方向にパケットが到着したら、パケットヘッダ解析部１１０は、そのパケットのフローキー＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}を読み出し、フロー管理部１２０にフローキーを通知する。その後、パケットをノードBに転送する。また、パケットヘッダ解析部１１０は、メモリ１４０の時刻管理テーブル１４３にパケット到着時の時刻を格納する。
【００５３】
フロー管理部１２０は、パケットヘッダ解析部１１０から取得したフローキーをBF'のK個のハッシュ関数に入力し、以下の手順を実施する。
【００５４】
図６は、本発明の第２の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【００５５】
（１）各ハッシュ値に対応するビットマップ上のビットが全て１である場合、つまり、メモリ１４０のBF'においてハッシュ値がヒットした場合（ステップ３００）、既にエントリされているフローからのパケットと判断して、それ以上の処理は行わない。
【００５６】
（２）メモリ１４０内のBF'においてハッシュ値がヒットしなかった場合（ビットマップ上でいずれかのビットが０である場合）（ステップ４００）、以下の手順を実施する。
【００５７】
（２−１）メモリ１４０内のBFのＫ個のハッシュ関数を入力し、各ハッシュ値に対応するビットマップ上のビットが全て１である場合（BFにおいてハッシュ値がヒットした場合）には（ステップ４００、Ｙ）、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックする（ステップ４１０）。
【００５８】
（２−１−１）もしSYNであれば（ステップ４１０、Ｙ）、K個のビット位置に対応する時刻管理テーブル１４３のK個の時刻エントリ情報を現在の時刻に更新する（ステップ４１１）。
【００５９】
（２−１−２）もしSYNでなければ（ステップ４１０、Ｎ）、何もしない。
【００６０】
（２−２）メモリ１４０のBFにＫ個のハッシュ関数に入力し、各ハッシュ値に対応するビットマップ上のビットのうち０であるものがあれば（BFにおいてハッシュ値がヒットしなかった場合）（ステップ４００、Ｎ）、そのパケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定する（ステップ４２０）。サンプリングする場合（ステップ４２０、Ｙ）、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば（ステップ４２１、Ｙ）、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立てる（ステップ４２２）。その後、K個のビット位置に対応する時刻管理テーブル１４３のK個の時刻エントリ情報を現在の時刻に更新する（ステップ４２３）。
【００６１】
一方、ノードBからノードA方向のパケットが到着したら、逆転フローキー抽出部２５０は、そのパケットにACKフラグが立っており、かつ、RSTにフラグが立っていなければ（ステップ４９０、Ｙ）、当該到着パケットのフローキーi（＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}を読み出し、逆転フローキー={dstIP#i，srcIP#i，dstPort#i，srcPort#i，Protocol#i}を作成する。これを、フロー管理部１２０へ通知する。同時に、パケットをノードAへ転送する。ここで、逆転フローキーとはsrcとdstを入れ替えたキーを指す。
【００６２】
フロー管理部１２０では、逆転フローキーをBF'への入力として、Ｋ個のハッシュ値に対するビット位置が全て１であれば（ステップ５００）。１つでも０があれば、Ｋ個のビット位置に対応する時刻管理テーブル１４３の時刻情報を読み出し、品質管理部１３０へ通知する。
【００６３】
品質管理部１３０は、 K個のビット位置に対応する時刻管理テーブル１４３から読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの測定ポイントと受信端末間の往復遅延時間RTTiとして推定する（ステップ５１０）。その後、フロー管理部１２０は、BF'を更新する（該当するK箇所にビットを立てる）（ステップ５１１）。
【００６４】
以上の手順を一定期間実施することで、監視点とルータＢ側にあるホスト間のフローの通信品質RTT（図１のRR_SAに相当）を推定することができる。
【００６５】
なお、ステップ６３０でサンプリングを行う代わりに、ステップ６００への入力（パケット到着）時に、フローキーをハッシュ関数に入力し、その出力がi番目（０≦i≦b）の配列位置にマッピングされたとし、i/bの値があらかじめ定めたサンプリングレートp(0<p<1)よりも小さいときのみ、ステップ６００へ入力する、としてもよい。
【００６６】
［第３の実施の形態］
前述の第１の実施の形態では、メモリ１４０内のBFとBF'を利用していたが、本実施の形態では、メモリ１４０内にBF1,BF2, BF1', BF2'を設け、品質推定部においてこれらを用いてRTTを推定する例を説明する。
【００６７】
図７は、本発明の第３の実施の形態におけるフロー通信品質推定装置の構成を示す。同図において、図３と同一構成部分には同一符号を付し、その説明を省略する。
【００６８】
本実施の形態では、メモリ３４０内のBFに対してBF1とBF2を２つ用意し、BF'についてもBF1'と    BF2'の２つを用意する。奇数番目の測定期間では、その開始時にBF1，BF1'をクリアし、書き込み処理の対象となるBloom FilterをBF=BF1, BF'=BF1'に設定する。偶数番目の測定期間では、その開始時にBF2，BF2'をクリアし、書き込み処理の対象となるBloom FilterをBF=BF2, BF'=BF2'に設定する。例えば、測定期間１，３，５，…番目に、BF1をクリアし、測定期間２，４，６，…番目にBF2をクリアすることで、RTT測定のタイミングには、BF1もBF2の両方をチェックしてBF1にはなくても、BF2にエントリがあれば、その情報を用いてRTTを計算するようにする。
【００６９】
このように、BFを２つ用意する理由を述べる。フローによっては、RTTが非常に大きいものもあるため、SYNパケットを観測してから、その次のAckパケットを検出するのに時間を要する場合がある。対処法としては、BFクリアの周期を長めに設定することが考えられるが、測定周期が長くなると、BFのビットマップが１で埋まってしまい正しく新規フローの検出をできない可能性がある。そこで、BFを２つ用意して、新規フロー検出（つまりSYNパケット検出）についてはBF1とBF2を交互に使うことにより適切に検出し、RTT計算時には BF1,BF2のいずれかに該当するエントリがあるかどうかをみることで、RTTの長いAckに対しても対応できるようにしている。
【００７０】
上記のような構成において、ノードAからノードBの方向に流れるパケットストリームに対して、パケットヘッダ解析部１１０は、パケット到着毎に該パケットのフローキーi＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}を読み出し、フロー管理部１２０に出力すると共に、到着パケットをノードＢへ送信する。また、パケットヘッダ解析部１１０は、パケットが到着した時刻をメモリ３４０の時刻管理テーブル３４３に格納する。フロー管理部１２０は、パケットヘッダ解析部１１０において読み出されたフローキーをキーとして、メモリ３４０内のBF'のK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、その結果に応じて以下の手順を実施する。
【００７１】
図８は、本発明の第３の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【００７２】
（１）各ハッシュ値に対応するビットマップ上のビットが全て1である場合（以下では、この条件を満たすことを「ハッシュ値がヒットした」と呼ぶことにする）には（ステップ６００、Ｙ）既にエントリされているフローからのパケットと判断して、それ以上の処理は行わない。
【００７３】
（２）BF1'においてハッシュ値がヒットせず、BF2'においてもハッシュ値がヒットしなかった場合（ステップ６００，Ｎ）、以下の手順を実施する。
【００７４】
（２−１）BF1においてハッシュ値がヒットする、あるいはBF2においてハッシュ値ヒットする場合（ステップ６１０、Ｙ）、到着パケットにTCPの通信開始フラグSYNが立っているかをチェックする（ステップ６１１）。
【００７５】
（２−１−１）もしSYNフラグのみ立っていれば（ステップ６１１，Ｙ）、BFのK個のビット位置に対応する時刻管理テーブル３４３のK個の時刻エントリ情報を現在の時刻に更新する（ステップ６１２）。
【００７６】
（２−１−２）もしSYNフラグのみ立っているのではなく（ステップ６１１，Ｎ）、そのパケットにACKフラグが立っており、かつ、RSTにフラグが立っていなければ（ステップ６１３、Ｙｅｓ）以下の(Ａ)から(Ｄ)を実施する。
【００７７】
(Ａ)  BF1,BF2両方においてハッシュ値ヒットした場合(ステップ６１４，Ｙ)：品質推定部１３０は、BFの時刻管理テーブル３４３の時刻情報を読み出してRTTを推定する（ステップ６１５）。その後、BF'において該当するK箇所にビットを立てる（以下，「BF'を更新する」と呼ぶ）(ステップ６１６)。なお、BF1,BF2の両方にハッシュが存在する場合は、新しい方のテーブル（直近にクリアされた方）を優先して参照するものとする。
【００７８】
（Ｂ）  上記（Ａ）の条件を満たさず、BF１においてハッシュ値がヒットしBF1' においてハッシュ値がヒットしない場合(ステップ６１７，Ｙ)：フロー管理部１２０は、BF1の時刻管理テーブル３４３の時刻情報を読み出して品質推定部１３０に通知する。これにより、品質推定部１３０は、読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの測定ポイントと受信端末間の往復遅延時間RTTiとして推定し、出力する（ステップ６１８)。その後、フロー管理部１２０は、BF1'を更新する(ステップ６１９)。
【００７９】
（Ｃ）（B）を満たさず、BF2においてハッシュ値ヒットしBF2' においてハッシュヒットしない場合(ステップ６２０、Ｙ)：フロー管理部１２０は、BF2の時刻管理テーブルの時刻情報を読み出して、品質推定部１３０に通知する。品質推定部１３０は、上記の（Ｂ）と同様の方法によりRTTを推定し、出力する(ステップ６２１)。その後、フロー管理部１２０は、BF2'を更新する(ステップ６２２)。
【００８０】
（Ｄ）（C）を満たさない場合（ステップ６２０，Ｎ）、何もしない。
【００８１】
（２−２）（２−１）が満たされない場合(ステップ６１０，Ｎ)、到着パケットを確率1/N（Nは予め定める正の整数）でサンプリングするか決定する(ステップ６３０)。サンプリングする場合(ステップ６３０，Ｙ)、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグのみが立っていれば(ステップ６３１，Ｙ)、BFのK個のハッシュ関数に入力して得られたハッシュ値に対応する位置にビットを立てる（ステップ６３２）。その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する。
【００８２】
以上の手順を一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。
【００８３】
なお、ステップ６３０でサンプリングを行う代わりに、ステップ６００への入力（パケット到着）時に，フローキーをハッシュ関数に入力し、その出力がi番目（０≦i≦b）の配列位置にマッピングされたとし、i/bの値があらかじめ定めたサンプリングレートp(0<p<1)よりも小さいときのみ、ステップ６００へ入力する、としてもよい。
【００８４】
［第４の実施の形態］
前述の第２の実施の形態では、メモリ３４０内のBFとBF'を利用していたが、本実施の形態では、メモリ３４０内にBF1,BF2, BF1', BF2'を設け、品質推定部においてこれらを用いてRTTを推定する例を説明する。
【００８５】
図９は、本発明の第４の実施の形態におけるフロー通信品質推定装置の構成を示す。同図において、図５と同一構成部分には同一符号を付し、その説明を省略する。
【００８６】
本実施の形態では、メモリ３４０内のBFに対してBF1とBF2を２つ用意し、BF'についてもBF1'と    BF2'の２つを用意する。奇数番目の測定期間では、その開始時にBF1，BF1'をクリアし、書き込み処理の対象となるBloom FilterをBF=BF1, BF'=BF1'に設定する。偶数番目の測定期間では、その開始時にBF2，BF2'をクリアし、書き込み処理の対象となるBloom FilterをBF=BF2, BF'=BF2'に設定する。ここで、BFを２つ用意するのは前述の第３の実施の形態と同様の理由からである。
【００８７】
上記のような構成において、ノードAからノードBの方向に流れるパケットストリームに対して、パケットヘッダ解析部１１０において、パケット到着毎に該パケットのフローキーiを読み出す。また、パケットヘッダ解析部１１０は、パケットが到着した時刻をメモリ３４０の時刻管理テーブル３４３に格納する。フロー管理部１２０がこれをメモリ３４０内のBF'のK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、その結果に応じて以下の手順を実施する。
【００８８】
図１０は、本発明の第４の実施の形態におけるフロー通信品質推定装置の品質推定動作のフローチャートである。
【００８９】
（１）フロー管理部１２０は、BF1'またはBF2'において、ハッシュ値がヒットした場合(ステップ７００，Ｙ)、既にエントリされているフローからのパケットと判断して、それ以上の処理は行わない。
【００９０】
（２）BF1',BF2'の両方においてハッシュ値がヒットしなかった場合（ステップ７００，Ｎ）以下の手順を実施する。
【００９１】
（２−１）フロー管理部１２０は、BFにおいてハッシュ値がヒットした場合(ステップ７１０，Ｙ)、そのパケットにTCPの通信開始フラグSYNが立っているかをチェックする(ステップ７１１)。
【００９２】
（２−１−１）もしSYNであれば（ステップ７１１，Ｙ）、K個のビット位置に対応する時刻管理テーブル３４３のK個の時刻エントリ情報を現在の時刻に更新する(ステップ７１２)。
【００９３】
（２−１−２）もしSYNでなければ（ステップ７１１，Ｎ）、なにもしない。
【００９４】
（２−２）BFにおいてハッシュ値がヒットしない場合（ステップ７１０，Ｎ）、そのパケットを確率1/Nでサンプリングするか決定する(ステップ７２０)。サンプリングする場合（ステップ７２０，Ｙ）、そのパケットにSYNフラグが立っていれば(ステップ７３０，Ｙ)、BFを更新する(ステップ７３１)。その後、K個のビット位置に対応する時刻管理テーブルのK個の時刻エントリ情報を現在の時刻に更新する。
一方、ノードBからノードA方向のパケットストリームに対し、逆転フローキー抽出部２５０は、パケットにACKフラグが立っており、かつ、RSTフラグが立っていなければ（ステップ８００、Ｙ）到着パケットのフローキーi＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}を読み出し、逆転フローキー={dstIP#i，srcIP#i，dstPort#i，srcPort#i，Protocol#i}を作成し、フロー管理部１２０に出力する。フロー管理部１２０は、これを、メモリ３４０のBF1'とBF2'への入力として、BF1'及びBF2'においてハッシュ値がヒットしなかった場合（ステップ８１０，Ｎ）、以下の(Ａ)から(Ｄ)を実施する。
【００９５】
（Ａ）BF1,2両方においてハッシュ値ヒットした場合（ステップ８２０）：フロー管理部１２０は、BFの時刻管理テーブル３４３の時刻情報を読み出して、品質管理部１３０に通知する。品質管理部１３０は、読み出された時刻情報の中で最も古い時刻T_old iを読み出し、現在の時刻Tnowからその最も古い時刻T_old iを差し引いた値Tnow - Told iを該フローの測定ポイントと受信端末間の往復遅延時間RTTiとして推定し、出力する(ステップ８２１)。その後、フロー管理部１２０は、BF'を更新する(ステップ８２２)。なお、BF1,BF2の両方にハッシュが存在する場合は、新しい方のテーブル(直近にクリアされた方)を優先して参照するものとする。
【００９６】
（Ｂ）（Ａ）の条件を満たさず、BF１においてハッシュ値ヒットしBF1' においてハッシュヒットしない場合(ステップ８３０，Ｙ)：フロー管理部１２０は、メモリ３４０のBF1の時刻管理テーブル３４３の時刻情報を読み出して、品質推定部１３０に通知する。品質推定部１３０は、上記と同様の方法によりRTTを推定して、出力する(ステップ８３１)。その後、フロー管理部１２０は、BF1'を更新する（ステップ８３２）。
【００９７】
（Ｃ）（B）を満たさず、BF2においてハッシュ値ヒットしBF2' においてハッシュヒットしない場合(ステップ８４０，Ｙ)：フロー管理部１２０は、メモリ３４０のBF2の時刻管理テーブル３４３の時刻情報を読み出して、品質推定部１３０に通知する。品質推定部１３０は、上記と同様の方法によりRTTを推定して、出力する (ステップ８４１)。その後、フロー管理部１２０は、BF2'を更新する(ステップ８４２)。
【００９８】
（Ｄ）（C）を満たさない場合（ステップ８４０，Ｎ）、何もしない。
【００９９】
以上の手順を一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。
【０１００】
なお、ステップ４２０でサンプリングを行う代わりに、ステップ３００への入力（パケット到着）時に、フローキーをハッシュ関数に入力し、その出力がi番目（０≦i≦b）の配列位置にマッピングされたとし、i/bの値があらかじめ定めたサンプリングレートp(0<p<1)よりも小さいときのみ、ステップ１００へ入力し、同様に、ステップ５００への入力時に、逆転フローキーのハッシュ出力結果iがi/b<pのときのみ、ステップ５００への入力、としてもよい。
【０１０１】
上記の第１〜第４の実施の形態におけるフロー通信品質推定装置の図３、図５、図７、図９に示す各構成要素の動作をプログラムとして構築し、フロー通信品質推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１０２】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１０３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０４】
１００，２００，３００，４００  フロー通信品質推定装置
１１０  パケットヘッダ解析部
１２０  フロー管理部
１３０  品質推定部
１４０  メモリ
１４１  BF
１４２  BF'
１４３  時刻管理テーブル
２５０  逆転フローキー抽出部
３４０  メモリ
３４３  時刻管理テーブル
【図１】
0005437194.tif 000002
【図２】
0005437194.tif 000003
【図３】
0005437194.tif 000004
【図４】
0005437194.tif 000005
【図５】
0005437194.tif 000006
【図６】
0005437194.tif 000007
【図７】
0005437194.tif 000008
【図８】
0005437194.tif 000009
【図９】
0005437194.tif 000010
【図１０】
0005437194.tif 000011