(57)【要約】      （修正有）【課題】ネットワーク全体の品質のリアルタイムでの推定を可能とする。【解決手段】フロー通信品質推定装置５１は、IPネットワークの全体の通信品質状態を管理する際、フロー管理部５１ｂにおいて、ルータ等のノード間のリンクにおいて１方向に流れるパケットストリームに関して、N個の到着パケットに対して１個のパケットを抽出し、フロー情報を読み出して蓄積管理する処理を一定期間継続し、品質推定部５１ｃにおいて、当該フロー情報を用いて測定対象リンクを通過するフローの通信品質を推定することで、能動的な測定が不要で、かつ、ネットワークの全パケットキャプチャを行うことなく、また、片方向のみのトラヒック測定によって、ネットワーク全体の品質をオンラインで推定することを可能とする。【選択図】図５
2011124750.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ装置により、通信網を構成するノードAとノードB間のリンクにおけるトラヒックを監視してフローの通信品質を算出するフロー通信品質推定方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、パケット処理手段を具備し、
該パケット処理手段は、
上記ノードAから上記ノードBの方向に流れるパケットストリームに対して、N個の到着パケット毎に1個のパケットを抽出する第１の手順と、
抽出したパケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っておりかつ予め用意したフローテーブルFTに当該パケットの発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)からなるフロー情報がエントリされていなければ、該SYNパケットのフロー情報{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}をフローキーとして該SYNパケットの到着時刻を上記フローテーブルFTに新規エントリする第２の手順と、
上記N個毎のパケット抽出とは独立に、上記ノードAから上記ノードB方向のパケットが到着する毎に、当該パケット#iのフローキー{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、該読み出したフローキーが既に上記フローテーブルFTにエントリされているか否かを調査する第３の手順と、
既にエントリされている場合、該フローテーブルFTにおいて当該フローキーに対応付けてエントリされているSYNパケットiの到着時刻Tiを読み出し、現在の時刻Tnowから上記読み出した到着時刻Tiを差し引いた値（Tnow-Ti）を当該フローiの往復遅延時間RTTiとして算出する第４の手順とを実行し、
上記第１から第４の手順を、予め定められた期間継続して繰り返すことで、測定対象リンクを通過するフローの通信品質を推定することを特徴とするフロー通信品質推定方法。
【請求項２】
コンピュータ装置により、通信網を構成するノードAとノードB間のリンクにおけるトラヒックを監視してフローの通信品質を算出するフロー通信品質推定方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、パケット処理手段を具備し、
該パケット処理手段は、
上記ノードAから上記ノードBの方向に流れるパケットストリームに対して、N個の到着パケット毎に1個のパケットを抽出する第１の手順と、
抽出したパケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っておりかつ予め用意したフローテーブルFTに当該パケットの発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)からなるフロー情報がエントリされていなければ、該SYNパケットiのフロー情報をフローキーとして該SYNパケットiの到着時刻TiおよびTCPヘッダ内のシーケンス番号SNiを上記フローテーブルFTに新規にエントリする第２の手順と、
上記N個毎に抽出されたパケットのフロー情報が上記フローテーブルFTに既にエントリされている場合、当該パケットのTCPヘッダ内のシーケンス番号SNを読み出し、上記フローテーブルFTに既にエントリされているシーケンス番号SNiと比較する第３の手順と、
比較の結果、SN-SNi<閾値であれば、当該パケットは上記フローテーブルFTにエントリされているSYNパケットの次に送信されてきたパケットであると判定して、上記フローテーブルFTにエントリされているSYNパケットの到着時刻Tiを読み出し、現在の時刻Tnowから上記到着時刻Tiを差し引いた値（Tnow-Ti）を当該フローiの往復遅延時間RTTiとして算出する第４の手順とを実行し、
上記第１から第４の手順を、予め定められた期間継続して繰り返すことで、測定対象リンクを通過するフローの通信品質を推定することを特徴とするフロー通信品質推定方法。
【請求項３】
コンピュータ装置により、通信網を構成するノードAとノードB間のリンクにおけるトラヒックを監視してフローの通信品質を算出するフロー通信品質推定方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、パケット処理手段を具備し、
該パケット処理手段は、
上記ノードAから上記ノードBの方向に流れるパケットに対して、N個の到着パケット毎に1個のパケットを抽出する第１の手順と、
抽出したパケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っていれば、該SYNパケットの発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)からなるフロー情報を読み出し、読み出したフロー情報をフローキーとして、BloomFilter(BF)のK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットすると共に、予め用意したフローテーブルFTに、上記フローキーと当該SYNパケットの到着時刻Tiをエントリする第２の手順と、
上記N個毎のパケット抽出とは独立に、上記ノードAから上記ノードB方向のパケット到着毎に当該パケットiのフロー情報{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、読み出したフロー情報をフローキーとして上記BFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べる第３の手順と、
調べた結果、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、上記パケットiが既に上記フローテーブルFTにエントリされているフローからのパケットと判断して、上記フローテーブルFTから当該SYNパケットiの到着時刻Tiを読み出し、Tnow-Ti=RTTiとして当該フローiの往復遅延時間RTTiを算出する第４の手順とを実行し、
上記第１から第４の手順を、予め定められた期間継続して繰り返すことで、測定対象リンクを通過するフローの通信品質を推定することを特徴とするフロー通信品質推定方法。
【請求項４】
コンピュータ装置により、通信網を構成するノードAとノードB間のリンクにおけるトラヒックを監視してフローの通信品質を算出するフロー通信品質推定方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、パケット処理手段を具備し、
該パケット処理手段は、
上記ノードAから上記ノードBの方向に流れるパケットに対して、N個の到着パケット毎に1個のパケットを抽出する第１の手順と、
抽出したパケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っていれば、該SYNパケットの発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)からなるフロー情報を読み出し、読み出したフロー情報をフローキーとして、BloomFilter(BF)のK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、予め用意された、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル内においてK個のハッシュ値に対応する各々の位置（Ｋ箇所）における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、上記時刻テーブル内において対応する位置に現在の時刻を、当該SYNパケットの到着時刻Tiとしてエントリする第２の手順と、
上記N個毎のパケット抽出とは独立に、上記ノードAから上記ノードB方向のパケット到着毎に当該パケットiのフロー情報{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、読み出したフロー情報をフローキーとして上記BFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べる第３の手順と、
調べた結果、上記時刻テーブル内においてK個のハッシュ値に対応する各々の位置（K箇所）における時刻情報を調べ、全てゼロ以外の値である場合には、最も古い時刻T_oldiを読み出し、現在の時刻Tnowから上記読み出した最も古い時刻T_oldiを差し引いた値（Tnow-T_oldi）を、当該フローiの往復遅延時間RTTiとして算出する第４の手順とを実行し、
上記第１から第４の手順を、予め定められた期間継続して繰り返すことで、測定対象リンクを通過するフローの通信品質を推定することを特徴とするフロー通信品質推定方法。
【請求項５】
請求項３もしくは請求項４のいずれかに記載のフロー通信品質推定方法であって、
上記パケット処理手段は、
予め定められた期間、上記BloomFilter(BF)を用いたパケット監視を実施した後、該BF内のビットを全て０にクリアする手順を実行することを特徴とするフロー通信品質推定方法。
【請求項６】
コンピュータ装置により、通信網を構成するノードAとノードB間のリンクにおけるトラヒックを監視してフローの通信品質を算出するフロー通信品質推定方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、パケット処理手段を具備し、
該パケット処理手段は、第１，第２のBloomFilter(BF)を用いた下記第１から第４の手順を、予め定められた期間継続して繰り返すことで、測定対象リンクを通過するフローの通信品質を推定することを特徴とするフロー通信品質推定方法。
第１の手順：
上記ノードAから上記ノードBの方向に流れるパケットに対して、N個の到着パケット毎に1個のパケットを抽出する。
第２の手順：
最初の期間では、上記抽出したパケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っていれば、該SYNパケットの発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)からなるフロー情報を読み出し、読み出したフロー情報をフローキーとして、第１および第２のBloomFilter(BF)それぞれ両方のK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、予め上記第１，第２のBF毎に用意された、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル内においてK個のハッシュ値に対応する各々の位置（Ｋ箇所）における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、上記各時刻テーブル内において対応する位置に現在の時刻を、当該SYNパケットの到着時刻Tiとしてエントリし、
２番目以降の偶数番目の期間では、上記第１のBFのみをクリアして、該第１のBFに対してのみ上記時刻テーブルに対する上記SYNパケットの到着時刻Tiのエントリ処理を行い、
３番目以降の奇数番目の期間では、上記第２のBFのみをクリアして、該第２のBFに対してのみ上記時刻テーブルに対する上記SYNパケットの到着時刻Tiのエントリ処理を行う。
第３の手順：
上記N個毎のパケット抽出とは独立に、上記ノードAから上記ノードB方向のパケット到着毎に当該パケットiのフロー情報{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、読み出したフロー情報をフローキーとして上記第１，第２のBFそれぞれ両方のK個のハッシュ関数に入力して得られるK個のハッシュ値を調べる。
第４の手順：
上記第３の手順で調べた結果、上記各時刻テーブル内においてK個のハッシュ値に対応する各々の位置（K箇所）における時刻情報を調べ、
奇数番目の期間では、上記第１のBFが全てゼロ以外の値である場合には、該第１のBFの中で最も古い時刻T_oldiを読み出し、該第１のBFでは１つ以上のゼロがありかつ上記第２のBFは全てゼロ以外の値であれば該第２のBFの中で最も古い時刻T_oldiを読み出し、現在の時刻Tnowから上記読み出したT_oldiを差し引いた値（Tnow-T_oldi）を、当該フローiの往復遅延時間RTTiとして算出し、
偶数番目の期間では、上記第2のBFが全てゼロ以外の値である場合には、該第2のBFの中で最も古い時刻T_oldiを読み出し、該第2のBFでは１つ以上のゼロがありかつ上記第1のBFは全てゼロ以外の値であれば該第1のBFの中で最も古い時刻T_oldiを読み出し、現在の時刻Tnowから上記読み出したT_oldiを差し引いた値（Tnow-T_oldi）を、当該フローiの往復遅延時間RTTiとして算出する。
【請求項７】
請求項１から請求項４のいずれかに記載のフロー通信品質推定方法であって、
上記パケット処理手段は、
上記フローiのフロー情報の内の発信元IPアドレスsrcIP#iと着信先IPアドレスdstIP#iを、予め用意した地理データベースを用いて、発信元IPアドレスsrcIP#iの所属するエリアArea#A、および、着信先IPアドレスdstIP#iの所属するエリアArea#Bに分けて登録すると共に、
上記エリアArea#Aおよび上記エリアArea#Bのエリアペア毎に用意した上記フローテーブルFTに上記第２の手順による新規エントリを行い、
上記エリアペア毎に、上記第３の手順と上記第４の手順によるフローiの往復遅延時間RTTiの算出を行い、
上記第１から第４の手順を、予め定められた期間継続して繰り返すことで、上記エリアArea#Aと上記エリアArea#B間のフローの通信品質d(A,B)を、
上記エリアArea#Aおよび上記エリアArea#Bに所蔵するフローの数（|srcIP#i∈A∧dstIP#i∈B|）を用いて、
d(A,B)=ΣsrcIP#i∈A∧dstIP#i∈BRTTi/|srcIP#i∈A∧dstIP#i∈B|により算出する
ことを特徴とするフロー通信品質推定方法。
【請求項８】
プログラムされたコンピュータ処理により、通信網を構成するノードAとノードB間のリンクにおけるトラヒックを監視してフローの通信品質を算出する通信品質推定装置であって、
プログラムされたコンピュータ処理を実行する手段として、
請求項１から請求項７のいずれかに記載のフロー通信品質推定方法における各手順を実行するパケット処理手段を具備したことを特徴とするフロー通信品質推定装置。
【請求項９】
コンピュータに、請求項１から請求項７のいずれかに記載のフロー通信品質推定方法におけるパケット処理手段による各手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、IP（Internet Protocol）ネットワークの通信品質状態を管理する技術に係り、特に、ネットワーク全体の通信品質状態を効率的に管理するのに好適な技術に関するものである。
【背景技術】
【０００２】
インターネットとしてIPネットワークが広く利用されてくるに伴って、IPネットワーク上での通信品質保証に対する要求が高まっている。それに伴い、ネットワークを流れるトラヒックを測定して現在の通信品質状態を把握することが重要になってきている。
【０００３】
エンドエンド遅延時間やパケット損失率、スループットといったネットワークの通信品質を把握する直接的な技術としては、エンドエンド間で試験パケットを送受信することにより品質を能動的に測定する技術（アクティブ測定）がある。
【０００４】
の
このアクティブ測定では、pingコマンドによる往復遅延測定や、例えば、非特許文献１等に記載のpathchar]等が用いられる。
【０００５】
また、例えば、非特許文献２に記載のように、着目するエンドホスト間において、試験パケットによるラウンドトリップタイムやパケット損失率の測定および経路上のボトルネック帯域の測定を実施し、かつ、実際にTCP（Transmission Control Protocol）で通信を行ってスループットを測定し、ウインドーサイズを徐々に大きくしていったときにTCPスループットが増加するかどうか等を詳細に解析する技術を提案している。
【０００６】
しかし、これらの技術は、一般に、ある特定のエンドホスト間で品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した技術であり、ネットワーク提供者が、ネットワーク内の通信を全体的に管理するのに直接適用すると、測定コストの増大およびネットワークへの測定負荷の増大が生じてしまう。
【０００７】
具体的には、監視対象となるネットワークの入り側および出側全てに試験パケット送受信機を設置して、試験パケットを送信することによって品質測定を能動的に行う必要があり、測定装置コストが増大してしまう。
【０００８】
さらに、試験パケットをネットワークへ付加するため、ネットワークへ余分なトラヒックが加わるという問題と、その結果、試験トラヒックによってネットワークの品質自体が劣化してしまうという問題があった。
【０００９】
このような能動的測定以外の技術として、着目するエンドエンド間トラヒックの流れる箇所において、そこを通過するパケットをキャプチャして解析し、ネットワークの状態を把握する技術（パッシブ測定）がある。
【００１０】
例えば、非特許文献３等に記載のACEと呼ばれるツールでは、パケットキャプチャデータから、エンド間のレスポンス時間や、その内訳（ネットワーク内での遅延とサーバでの遅延）を分析することができる。また、非特許文献４に記載のツールでも往復遅延等を分析することが可能である。
【００１１】
しかし、これらの技術は、一般に、ある特定のエンドホスト間で品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した技術であり、ネットワーク全体でのユーザフロー通信品質を測定するためには、回線を流れるパケットを全てキャプチャしてパケットヘッダ情報の解析、およびフロー情報の解析が必要となり、回線速度が高速になるにつれて、全てのパケットをキャプチャして処理することが困難となる。
【００１２】
そこで、本発明者らは、非特許文献５に記載のように、双方向に流れるパケットストリームに対して、パケットサンプリングを行って必要なTCPパケットを蓄積した後、オフラインで蓄積パケットを処理することで、ネットワーク全体の品質を推定する技術を提案している。
【００１３】
この技術では、能動的な測定を行うことなく、かつ、ネットワークの全パケットのキャプチャを行うことなく、ネットワーク全体の品質を推定することを可能にしている。
【００１４】
しかしながら、この技術は、双方向のパケットをキャプチャする必要があり、インターネットルーチングでは非対称になるケースもあるため、必ずしも監視ポイントで双方向パケットをキャプチャできるとは限らない。
【００１５】
また、一旦パケットを蓄積した後で、オフライン処理を行う必要があるため、リアルタイムに品質を推定できないという問題点がある。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】「Pathchar」、［online］、［平成２１年１２月０３日検索］、インターネット＜ＵＲＬ：http://www.caida.org/tools/utilities/others/pathchar/＞.
【非特許文献２】的場 一峰, 阿多 信吾, 村田 正幸, "インターネットにおける計測に基づいたボトルネック特定手法," 電子情報通信学会 テレコミュニケーションマネジメント研究会, pp. 65 - 70, November 2000.
【非特許文献３】「Application Performance Analysis | Application Troubleshooting」、［ｏｎｌｉｎｅ］、［平成２１年１２月０３日検索］、インターネット＜ＵＲＬ：http://www.opnet.com/solutions/application_performance/ace.html＞.
【非特許文献４】「tcptrace - Official Homepage」、［ｏｎｌｉｎｅ］、［平成２１年１２月０３日検索］、インターネット＜ＵＲＬ：http://www.tcptrace.org/＞.
【非特許文献５】川原他, "フローサンプリングによるフロー品質推定方法, " 電子情報通信学会2009年ソサイエティ大会, B-7, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
解決しようとする問題点は、従来のアクティブ測定技術では、ネットワーク全体でのユーザフロー通信品質を測定するのは困難である点と、従来のパッシブ測定技術では、必ずしも監視ポイントで双方向パケットをキャプチャできるとは限らない点と、リアルタイムに品質を推定できない点である。
【００１８】
本発明の目的は、これら従来技術の課題を解決し、ネットワーク全体の品質のリアルタイムでの推定を可能とすることである。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、本発明では、IPネットワークの全体の通信品質状態を管理する際、ルータ間のリンクにおいて１方向に流れるパケットストリームに関して、N個の到着パケットに対して１個のパケットを抽出し、フロー情報を読み出して蓄積管理する処理を一定期間継続し、当該フロー情報を用いて測定対象リンクを通過するフローの通信品質を推定する。
【発明の効果】
【００２０】
本発明によれば、ネットワークへの余分な負荷を加えてしまう能動的な測定が不要で、かつ、ネットワークの全パケットキャプチャを行うことなく、また、片方向のみのトラヒック測定によって、ネットワーク全体の品質をオンラインで推定することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明に係るフロー通信品質推定方法の第１の手順例を示す説明図である。
【図２】本発明に係るフロー通信品質推定方法の第２の手順例を示す説明図である。
【図３】本発明に係るフロー通信品質推定方法の第３の手順例を示す説明図である。
【図４】本発明に係るフロー通信品質推定装置の設置例を示すブロック図である。
【図５】本発明に係るフロー通信品質推定装置の内部構成例を示すブロック図である。
【発明を実施するための形態】
【００２２】
以下、図を用いて本発明を実施するための形態例を説明する。図５に示す本例のフロー通信品質推定装置（図中「フロー品質推定装置」と記載）５１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置等を具備したコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。
【００２３】
すなわち、フロー通信品質推定装置５１は、プログラムされたコンピュータ処理を実行する手段として、パケットヘッダ解析部５１ａ、フロー管理部５１ｂ、品質推定部５１ｃ、パケットカウント部５１ｄ、サンプリング部５１ｅを有し、IPネットワークの通信品質の推定処理を行う。
【００２４】
このような構成からなるフロー通信品質推定装置５１による本発明に係るネットワーク全体の通信品質の推定技術について説明する。
【００２５】
フロー通信品質推定装置５１は、図４においてフロー通信品質推定装置４２として示すように、IPネットワークを構成するスイッチやルータ等のノードＡ４１とノードＢ４３間のリンクに挿入される形態で利用される。あるいは、ノードにおいてパケットをポートへミラーして、そのポートの先にフロー通信品質推定装置４２を設置する構成としても良い。
【００２６】
図５において、フロー通信品質推定装置５１は、前段ノードからパケットが到着したら、パケットヘッダ解析部５１ａにおいて、そのパケットのフローキー＝{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を読み出し、フロー管理部５１ｂにフローキーを通知する。
【００２７】
その後、フロー通信品質推定装置５１は、パケットをパケットカウント部５１ｄに転送する。
【００２８】
フロー管理部５１ｂは、パケット解析部５１ａから受信したフローキーが、フロー管理部５１ｂ内に存在するフローテーブルFT５０にエントリされているフローからのパケットであるか否かを調べ、もしそうであれば、フローテーブルFT５０内の到着時刻Tiを読み出して、その値を品質推定部５１ｃに通知する。
【００２９】
品質推定部５１ｃは、フロー管理部５１ｂから到着時刻Tiを受け取ったら、フロー通信品質推定装置５１自体が測定している現在の時刻Tnowから到着時刻Tiを差し引いた値RTTi=Tnow-Tiを算出し、算出したRTTiを、当該フローiの往復遅延時間の推定値として出力する。
【００３０】
パケットカウント部５１ｄでは、パケット到着数Cをカウントしており、パケット到着毎にその方向をみて、該当する方向のカウンタをカウントアップする。そして、その後、カウンタ値をN（Nは予め定めたサンプリング周期）で割った余りが０と等しいか否かをチェックする。
【００３１】
もし余りが０であれば、パケットカウント部５１ｄは、当該パケットをサンプリング部５１ｅに転送し、同時に当該パケットを後段ノードに転送する。もし余りが０でなければ、パケットカウント部５１ｄは、単に後段ノードへのみ該パケットを転送する。
【００３２】
サンプリング部５１ｅでは、到着パケットのヘッダを読み込み、TCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部５１ａへ転送する。
【００３３】
あるいは、パケットカウント部５１ｄにおいて、パケット到着毎に０から1の範囲で乱数を発生させ、その結果が1/N以下であれば、当該パケットをパケットヘッダ解析部５１ａに転送した後に後段ノードにも該パケットを転送し、発生させた乱数が1/N以下でなければ、単に後段ノードへのみ当該パケットを転送するとしても良い。
【００３４】
パケットヘッダ解析部５１ａでは、サンプリング部５１ｅからSYNパケットが転送されてきたならば、当該パケットのフローキーを読み出し、その旨をフロー管理部５１ｂに通知する。
【００３５】
フロー管理部５１ｂは、SYNパケットをパケットヘッダ解析部５１ａから受け取ると、そのフローキーをフローテーブルFT５０に新規エントリし、同時に現在の時刻を、フローテーブルFT５０内の到着時刻Tiに書き込む。もし、例えばSYNパケットが２回送信されている場合等により、既にフローテーブルFT５０にエントリされていた場合には、フローテーブルFT５０内の到着時刻Ti現在の時刻に更新する。
【００３６】
このようなフロー通信品質推定装置５１による処理動作の＜第１の実施例＞を、図２を用いて説明する。
【００３７】
図５に示すフロー通信品質推定装置５１は、図２（ａ）において、ルータＡ２２とルータＢ２４の間に位置する監視点２３（監視ポイント）に設置され、エンドホストａ２１とエンドホストｂ２５間で送受信されるパケットを監視することで、エンドホストａ２１とエンドホストｂ２５、ルータＡ２２とルータＢ２４を含むネットワークにおける通信品質を推定する。
【００３８】
監視点２３では、図２（ｂ）に示すフローテーブル（FT）２０を保持している。この例では、上述のSYNサンプリングによって、時刻10:00:01に、エンドホストa２１とb２５の間で通信しているフロー（フローキー{192.168.1.1,192.168.1.2,80,1024,6}）のSYNパケットがサンプルされた状態を示しており、フローテーブル（FT）２０内のSYNパケット到着時刻Tiに、10:00:01が記録されている。
【００３９】
その後、図２（ａ）のシーケンス図で示すように、10:00:05に同フローiからパケット（Ack）が到着すると、フローテーブル（FT）２０においてフローiがエントリされているか否かをチェックし、エントリされていれば、当該SYNパケット到着時刻Tiを読み出し、RTTi=Tnow-Ti=4sと推定する。
【００４０】
この例から分かるように、ルータB２４からルータA２２方向のSYNACKパケットをサンプルすることなく、ルータA２２からルータB２４方向の、SYNパケット、および（SYN-ACKに対する）Ackパケットさえキャプチャできれば、ネットワーク通信品質の推定を行うのに十分である。
【００４１】
また、AckパケットとSYNパケットの到着時刻の差がRTTそのものであるため、Ackパケット到着時に、オンラインで、リアルタイムでRTTを算出することが可能である。
【００４２】
このような第１の実施例におけるフロー通信品質推定装置５１の処理動作を、図１を用いて説明する。
【００４３】
図２のルータA２２とルータB２４をつなぐリンクにおいて、ルータA２２からルータB２４の方向に流れるパケットストリームに対して、N個の到着パケットに対し1個のパケットを抽出し（ステップＳ１０３）、当該パケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っておりかつ予め用意したフローテーブル（以下、フローテーブルFTとよぶ）に該フローの情報がエントリされていなければ（ステップＳ１０４）、当該パケットのフローキー＝{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}をフローテーブルFT１００に新規エントリする（ステップＳ１０５）。同時に、当該フローiからのSYNパケット到着時刻TiをフローテーブルFT１００にエントリする。
【００４４】
ステップＳ１０３におけるN個に1個のパケット抽出とは独立に、ルータA２２からルータB２４方向のパケット到着毎に、当該パケットのフローキー{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、この５つ組のキーが既にフローテーブルFT１００にエントリされているか否かを調査し（ステップＳ１０１）、既にエントリされている場合、該当するSYNパケットの到着時刻TiをフローテーブルFT１００から読み出し、現在の時刻Tnowから到着時刻Tiを差し引いた値Tnow-Tiを当該フローiの往復遅延時間RTTiとして推定し（ステップＳ１０２）、これを一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。
【００４５】
次に、図３を用いて、＜第２の実施例＞について説明する。この第２の実施例では、上述の第１の実施例のように、パケット到着毎にパケットヘッダを解析する代わりに、N個に1個の頻度で抽出された当該パケットのフローキー{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}が既にフローテーブルFT３０にエントリされている場合、当該パケットのTCPヘッダ内のシーケンス番号SNを読み出し、フローテーブルFT３０にエントリされているシーケンス番号SNiと比較して、SN-SNi<閾値であれば、当該パケットはフローテーブルFT３０にエントリされているSYNパケットの次に送信されてきたパケットであると判定し、フローテーブルFT３０内の当該SYNパケットの到着時刻Tiを読み出し、現在の時刻Tnowから到着時刻Tiを差し引いた値（Tnow-Ti）を当該フローiの往復遅延時間RTTiとして推定する。
【００４６】
すなわち、図３（ａ）に示すように、まず、図２のルータA２２からルータB２４の方向に流れるパケットストリームに対して、N個の到着パケットに対し1個のパケットを抽出する（ステップＳ３０１）。
【００４７】
その後、当該パケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っているか否かを判別する（ステップＳ３０２）。SYNフラグが立っており、かつ予め用意したフローテーブルFT３０に該フローの情報がエントリされていなければ（ステップＳ３０４）、当該パケットのフローキー＝{srcIP、dstIP、srcPort、dstPort、Protocol}をフローテーブルFT３０に新規エントリする（ステップＳ３０３）。
【００４８】
この際、同時に、当該フローiからのSYNパケットの到着時刻Tiおよび当該パケットのTCPヘッダ内のシーケンス番号SNiをフローテーブルFT３０にエントリする。
【００４９】
N個に1個のパケット抽出された当該パケットのフローキー{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}が既にフローテーブルFT３０に既にエントリされている場合（ステップＳ３０４）、当該パケットのTCPヘッダ内のシーケンス番号SNを読み出し、フローテーブルFT３０にエントリされているSNiと比較して、SN-SNi<閾値であれば（ステップＳ３０５）、当該パケットはフローテーブルFT３０にエントリされているSYNパケットの次に送信されてきたパケットであると判定し、フローテーブルFT３０内のSYNパケット到着時刻Tiを読み出し、現在の時刻TnowからTiを差し引いた値Tnow-Tiを当該フローiの往復遅延時間RTTiとして推定し（ステップＳ３０６）、これを一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。
【００５０】
この第２の実施例では、第１の実施例のようにパケット到着毎にフローIDがFTにエントリされているかのチェックを行わず、パケットサンプルされたパケットのみの情報を用いている。その際、SYNパケットの次にサンプルされたパケットが、本当にSYNパケットの次のパケットであるかどうかをチェックする必要がある。そこで、シーケンス番号の差をみることで、その判断を行っている。
【００５１】
次に＜第３の実施例＞について説明する。この第３の実施例では、上述の第１の実施例のように{srcIP、dstIP、srcPort、dstPort、Protocol}をキーとしたフローテーブルを、出現した全てのフローを収容できるように作成する代わりに、BloomFilter(BF)を用いる。
【００５２】
このBFでは、異なるK個のハッシュ関数（それぞれがキー値をサイズbの範囲内でハッシュ値を返す）と、サイズbのビットマップ（初期状態では全てをゼロにリセットされる）を用意する。
【００５３】
N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする。
【００５４】
また、別途用意したフローテーブルFTにフローIDと当該SYNパケット到着時刻Tiをエントリする。
【００５５】
N個に1個のパケット抽出とは独立に、パケット到着毎に、当該パケットiのフロー情報{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断して、フローテーブルFTから当該フローIDの到着時刻Tiを読み出し、現在時刻Tnowを用いて、Tnow-Ti=RTTiとして、当該フローiの往復遅延時間RTTiを推定する。そして、この処理を一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。
【００５６】
このように、BFを使うことにより、全てのサンプルフローを管理することなく、必要なパケット収集を可能としている。
【００５７】
尚、BloomFilter(BF)を用いる場合に、一定期間BFによるパケット監視を実施した後、BF内のビットを全て０にクリアする。
【００５８】
次に＜第４の実施例＞について説明する。この第４の実施例では、上述の第３の実施例のように、BFを用いて0か1のビット情報を管理する代わりに、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル（初期状態では全てをゼロにリセットされる）を用意する。このメモリは、パケットの到着時刻を記憶するために用いる。
【００５９】
例えば図２におけるルータA２２からルータB２４方向のパケットに関して、N個の到着パケットに対し1個のパケットを抽出し、このパケットのヘッダ情報を読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットのフロー情報{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置（K箇所）における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、対応する位置に現在の時刻を書き込む。
【００６０】
N個に1個のパケット抽出とは独立に、ルータA２２からルータB２４方向のパケット到着毎にこのパケットiのフロー情報{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置（K箇所）における時刻情報を調べ、全てゼロ以外の値である場合には、その中で最も古い時刻T_oldiを読み出し、現在の時刻Tnowからその最も古い時刻T_oldiを差し引いた値Tnow-T_oldiを、当該フローの往復遅延時間RTTiとして推定する。
【００６１】
そして、この処理を一定期間継続して測定対象リンクを通過するフローの通信品質を推定する。尚、BloomFilter(BF)を用いる場合に、一定期間BFによるパケット監視を実施した後、BF内のビットを全て０にクリアする。
【００６２】
通常のBFでは、ビットマップを用意するのに対し、ここでは、ビット情報ではなく、パケット到着時刻情報を管理するようにすることにより、第３の実施例のように、別途フローテーブルFTを用意して時刻情報を管理することを不要としている。
【００６３】
ビットマップ上の時刻情報のうち、他のフローのSYN到着時にいくつかの時刻情報は上書きされるが、全部が上書きはされないであろうとみなして、最も古い時刻情報を、当該フローのSYNパケット到着時刻とみなし、往復遅延時間RTTを推定している。
【００６４】
尚、BloomFilter(BF)は、定期的にクリアしないで長時間継続的に利用すると、全てのビットが１で埋まってしまい、適切な新規フロー判定が困難になるため、上述の第３，第４の実施例のように、一定期間BFによるパケット監視を実施した後、BF内のビットを全て０にクリアする。
【００６５】
次に＜第５の実施例＞について説明する。上述の第３，第４の実施例において、一定期間BFによるパケット監視を実施したらBF内のビットを全て０にクリアしていたが、以下のようにしてもよい。
【００６６】
BFを２つ用意し（BF1とBF2とする）、最初の測定期間は、いずれのBFにも同じ処理を施し、2番目以降（偶数番目）の測定期間においては、BF1のみをクリアし、BloomFilterへの書き込み処理、すなわち、上述の第４の実施例における処理のうち、N個に1個サンプルしてSYNがたっていればBFへ入力する処理は、BF1に対してのみ実施する。
【００６７】
一方、BloomFilterからの読み出し処理、すなわち、上述の第４の実施例における処理のうち、N個に1個のパケット抽出とは独立にパケット到着毎に到着時刻T_oldiを読み出す処理）は、BF1,2両方に対して実施する。
【００６８】
BF2テーブル内の到着時刻T_iが全てゼロ（０）以外の値である場合には、BF2の中で最も古い時刻T_oldiを読み出し、BF2では１つ以上のゼロがありかつBF1は全てゼロ以外の値であればBF1の中で最も古い時刻T_oldiを読み出し、現在の時刻Tnowから上記読み出したT_oldiを差し引いた値（Tnow-T_oldi）を、当該フローiの往復遅延時間RTTiとして算出する。
【００６９】
3番目以降（奇数番目）の測定期間では、BF2をクリアし、BloomFilterへの書き込み処理はBF2に対してのみ行う。
【００７０】
一方、BloomFilterからの読み出し処理はBF1,2両方に対して実施する。
【００７１】
BF1テーブル内の到着時刻T_iが全てゼロ（０）以外の値である場合には、BF1の中で最も古い時刻T_oldiを読み出し、BF1では１つ以上のゼロがありかつBF2は全てゼロ以外の値であればBF2の中で最も古い時刻T_oldiを読み出し、現在の時刻Tnowから上記読み出したT_oldiを差し引いた値（Tnow-T_oldi）を、当該フローiの往復遅延時間RTTiとして算出する。この処理を交互に繰り返す。
【００７２】
以下、このように、BFを２つ用意する理由を述べる。
【００７３】
フローによっては、遅延時間RTTが非常に大きいものもあるため、SYNパケットを観測してから、その次のAckパケットを検出するのに時間を要する場合がある。対処法としては、BFクリアの周期を長めに設定することが考えられるが、第３，４の実施例でも述べたように、測定周期が長くなると、BFが正しく新規フローの検出をできない可能性がある。
【００７４】
そこで、BFを２つ用意して、新規フロー検出（つまりSYNパケット検出）についてはBF1とBF2を交互に使うことにより適切に検出し、その次のAckパケットについては、BF1,2の両方に対して入力し、いずれかのBFに該当するエントリがあるかどうかをみることで、遅延時間RTTの長いAckに対しても対応できるようにしている。
【００７５】
次に＜第６の実施例＞について説明する。上述の第１〜第４の実施例のいずれかによりフローiのRTTiを推定する処理を実行する前に、フローiの{発信元IPアドレスsrcIP#i,着信先IPアドレスdstIP#i}を、予め用意した地理データベースを用いてsrcIP#iの所属するエリアArea#A,およびdstIP#iの所属するエリアArea#Bへマップし、エリアAとエリアBのペア毎に用意したフローテーブルFTにエントリさせる。
【００７６】
エリアペア毎に、第１〜第４の実施例のいずれかの処理でフローiの往復遅延時間RTTiを推定し、その処理を一定期間実施して、エリアAとエリアBの間の品質d(A,B)をd(A,B)=ΣsrcIP#i∈A∧dstIP#i∈BRTTi/|srcIP#i∈A∧dstIP#i∈B|により推定する。
【００７７】
尚、|srcIP#i∈A∧dstIP#i∈B|は、srcIP#iがエリアAに所属し、かつdstIP#iがエリアBに所属した、フローの数を意味する。
【００７８】
このようにすることにより、例えば、県別の品質がどのようになっているかを把握可能である。
【００７９】
以上、図１〜図５を用いて説明したように、本例のフロー通信品質推定装置５１は、IPネットワークの全体の通信品質状態を管理する際、フロー管理部５１ｂにおいて、ルータ等のノード間のリンクにおいて１方向に流れるパケットストリームに関して、N個の到着パケットに対して１個のパケットを抽出し、フロー情報を読み出して蓄積管理する処理を一定期間継続し、品質推定部５１ｃにおいて、当該フロー情報を用いて測定対象リンクを通過するフローの通信品質を推定する。
【００８０】
このように、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、また、片方向のみのトラヒック測定によって、ネットワーク全体の品質をオンラインで推定することが可能である。
【００８１】
尚、本発明は、図１〜図５を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、図２の例では、監視点の設置個所としてルータＡ，Ｂ間を例示しているが、スイッチ間であっても良い。
【００８２】
また、本例のコンピュータ構成に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【符号の説明】
【００８３】
２２，３０，５０，１００：フローテーブルFT、２１：エンドホストａ、２２：ルータＡ、２３：監視点、２４：ルータＢ、２５：エンドホストｂ、４１：ノードＡ、４２：フロー通信品質推定装置、４３：ノードＢ、５１：フロー通信品質推定装置、５１ａ：パケットヘッダ解析部、５１ｂ：フロー管理部、５１ｃ：品質推定部、５１ｄ：パケットカウント部、５１ｅ：サンプリング部。
【図１】
2011124750.tif 000003
【図２】
2011124750.tif 000004
【図３】
2011124750.tif 000005
【図４】
2011124750.tif 000006
【図５】
2011124750.tif 000007