ネットワーク品質算出システムと方法およびプログラム
【課題】試験パケットを使わずにネットワークの通信品質を把握できるようにした。
【解決手段】パケットカウント部は、ノードA−B方向のパケットを予め定められた間隔でサンプリングし、サンプリング部は、サンプリングしたパケットにSYNフラグが立っているか否かを判別し、立っており、かつ、新規のフローであれば、パケットヘッダ解析部は、このパケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報を、フロー管理テーブルに新規登録し、パケット情報蓄積・分析部は、新規登録したパケットの到着時刻とヘッダ情報、および、ノードA−B方向とノードB−A方向のそれぞれ同じフローである各到着パケットの到着時刻とヘッダ情報パケット情報蓄積テーブルに格納し、予め定められた期間毎に、パケットの到着時刻とヘッダ情報を用いて測定点とノードB間の通信品質を算出する。
【解決手段】パケットカウント部は、ノードA−B方向のパケットを予め定められた間隔でサンプリングし、サンプリング部は、サンプリングしたパケットにSYNフラグが立っているか否かを判別し、立っており、かつ、新規のフローであれば、パケットヘッダ解析部は、このパケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報を、フロー管理テーブルに新規登録し、パケット情報蓄積・分析部は、新規登録したパケットの到着時刻とヘッダ情報、および、ノードA−B方向とノードB−A方向のそれぞれ同じフローである各到着パケットの到着時刻とヘッダ情報パケット情報蓄積テーブルに格納し、予め定められた期間毎に、パケットの到着時刻とヘッダ情報を用いて測定点とノードB間の通信品質を算出する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ネットワークの通信品質状態を管理する技術に係り、特に、IPネットワーク全体の通信品質状態を効率よくかつ高精度に把握するのに好適な技術に関するものである。
【背景技術】
【0002】
IPネットワークが広く利用されてくるに伴って、IPネットワーク上での通信品質保証に対する要求が高まっている。それに伴い、ネットワークを流れるトラヒックを測定して現在の通信品質状態を把握することが重要になってきている。
【0003】
エンドエンド遅延時間やパケット損失率、スループットといったネットワークの通信品質を把握する直接的な技術としては、エンドエンド間で試験パケットを送受信することにより品質を能動的に測定する技術がある。
【0004】
例えば、pingコマンドにより往復遅延を測定する技術や、非特許文献1にあるpathcharを用いる技術等がある。また、例えば非特許文献2の技術では、着目するエンドホスト間において、試験パケットによるラウンドトリップタイムやパケット損失率の測定および経路上のボトルネック帯域の測定を実施し、かつ、実際にTCP(Transmission Control Protocol)で通信を行ってスループットを測定し、ウインドーサイズを徐々に大きくしていったときにTCPスループットが増加するかどうか等を詳細に解析する技術が提案されている。
【0005】
しかし、これらの技術は、ある特定のエンドホスト間で、品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した技術であり、このような技術を、ネットワーク提供者がネットワーク内の通信を全体的に管理するのに直接適用すると、測定コストの増大およびネットワークへの測定負荷の増大が生じてしまう。
【0006】
具体的には、監視対象となるネットワークの入り側および出側の全てにおいて、試験パケット送受信機を設置して、試験パケットを送信することによって品質測定を能動的に行う必要があり、測定装置の設置に要するコストが増大してしまう。
【0007】
さらに、試験パケットをネットワークへ付加するため、ネットワークへ余分なトラヒックが加わるという問題と、その結果、試験トラヒックによってネットワークの品質自体が劣化してしまうという問題があった。
【0008】
このような能動的に測定を行う技術以外に、着目するエンドエンド間トラヒックの流れる箇所において、そこを通過するパケットをキャプチャして解析し、ネットワークの通信状態を把握する技術がある。
【0009】
例えば、非特許文献3における「ACE」(商標)と呼ばれるツールでは、パケットキャプチャデータから、エンド間のレスポンス時間や、その内訳(ネットワーク内での遅延とサーバでの遅延)が分析可能である。また、非特許文献4におけるツール(「tcptrace」)でも往復遅延等を分析することが可能である。
【0010】
しかし、これらの技術は、ある特定のエンドホスト間で、品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した技術であり、ネットワーク全体でのユーザフロー通信品質を測定するためには、回線を流れるパケットを全てキャプチャして、パケットヘッダ情報の解析、およびフロー情報の解析が必要であり、回線速度が高速になるにつれて全てのパケットをキャプチャして処理することが困難になる。
【0011】
一方、近年、例えば非特許文献5に記載の技術のように、パケットサンプリングを実施することによって、フロー管理に必要とされる処理を軽減する技術が注目されている。
【0012】
例えば、N個に1個のパケットを周期的に参照し、サンプルされたパケットから元のフロー統計情報を推定する技術である。非特許文献6では、パケットサンプリングを用いてリンク帯域の占有率が高いフローを特定する技術を提案している。また、非特許文献7では、フローサイズが大きいフローの統計を精度よく得る技術を提案している。
【0013】
しかし、非特許文献6,7の技術は、サイズの大きい、あるいは帯域の占有率が高いフローを特定し、それらフローを過剰に発生するユーザを迅速に切り分けることを目的としており、品質把握を可能にするものではない。
【0014】
一方、本願の発明者らは非特許文献8において、サンプルパケット情報からTCPのフロースループットを推定する技術を提案している。しかし、この技術では、N個に1個のパケットを抽出するといった通常のパケットサンプリングを行っているため、サイズの大きいフローがサンプルされやすく、サイズの小さいフローが無視されて、サイズの大きいフローのスループットのみを把握可能とするものであった。また、遅延やパケット損失率といった品質の把握は不可能であった。
【先行技術文献】
【非特許文献】
【0015】
【非特許文献1】「pathchar」,[平成21年5月14日検索],インターネット<URL : http://www.caida.org/tools/utilities/others/pathchar/>.
【非特許文献2】的場一峰,阿多信吾,村田正幸,“インターネットにおける計測に基づいたボトルネック特定手法”,電子情報通信学会 テレコミュニケーションマネジメント研究会,pp.65−70,November 2000.
【非特許文献3】「Applicatin Performance Troubleshooting ACEAnlyst」,[平成21年5月14日検索],インターネット<URL : http://www.opnet.com/solutions/application_performance/ace.html>.
【非特許文献4】「tcptrace−Official Homepage tcptrace」,[平成21年5月14日検索],インターネット<URL : http://www.tcptrace.org/>.
【非特許文献5】「IETF Packet Sampling (psamp) Working Group」,[平成21年5月14日検索],インターネット<URL : http://www.ietf.org/html.charters/psamp−charter.html>.
【非特許文献6】森,内田,川原,後藤,“サンプルされたパケットからエレファントフローを特定する手法”,電子情報通信学会技術研究報告 NS2004−13,pp.17−20,2004−04.
【非特許文献7】C.Estan and G.Varghese,”New Directions in Traffic Measurement and Accounting,”ACM SIGCOMM 2002,Aug.2002.
【非特許文献8】R.Kawahara,T.Mori,K.Ishibashi,N.Kamiyama and H.Yoshino,“Packet sampling TCP flow rate estimation and performance degradation detection method”,IEICE Trans. Commun.,Vol.E91−B,No.5,pp.1309−1319,May 2008.
【発明の概要】
【発明が解決しようとする課題】
【0016】
解決しようとする問題点は、(1)従来の能動的な測定によりネットワーク品質を把握する技術では、測定装置コストが増大してしまうと共に、測定用の試験トラヒックによってネットワークの品質自体が劣化してしまう点と、(2)特定のエンドホスト間で品質の把握を行う従来技術では、回線を流れるパケットを全てキャップチャする必要があり高速な回線での適用が困難である点、および、(3)サンプルパケット情報からTCPのフロースループットを推定する従来技術では、サイズの大きいフローのスループットのみを把握可能とするだけであり、また、遅延やパケット損失率といった品質を把握することができない点である。
【0017】
本発明の目的は、これら従来技術の課題を解決し、能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の通信品質(遅延、パケット損失率、スループット)を、効率よく且つ高精度に推定することを可能とすることである。
【課題を解決するための手段】
【0018】
上記目的を達成するため、本発明では、ノードAからノードB方向のパケットを予め定められた間隔でサンプリングし、サンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っているか否かを判別し、立っていれば、このパケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報が、予め記憶装置に記憶されたフロー管理テーブルに登録されているか否かを判別し、登録されていなければ、このパケットのフロー情報を、フロー管理テーブル61に新規登録し、かつ、新規登録したパケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに格納すると共に、ノードAからノードB方向のパケットが到着する度に、当該パケットのフロー情報を読み出し、当該パケットのフロー情報が既にフロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに格納し、また、ノードBからノードA方向のパケットが到着する度に、このパケットのフロー情報を読み出し、このフロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報がフロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに格納する。そして、予め定められた期間毎に、パケット情報蓄積テーブルに格納されたパケットの到着時刻とヘッダ情報を用いて、観測点とノードB間の通信品質を算出する。また、ノードAからノードB方向のパケットに対する処理を、ノードBからノードA方向のパケットに対しても実行すると共に、ノードBからノードA方向のパケットに対する処理を、ノードAからノードB方向のパケットに対して実行し、観測点とノードB間の通信品質の算出と共に、観測点とノードA間の通信品質の算出も行い、その結果を用いて、ノードAとノードB間のリンクを通過するフローの通信品質を算出する。
【発明の効果】
【0019】
本発明によれば、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質(遅延、パケット損失率、スループット)を効率よく且つ高精度に推定することが可能となる。
【図面の簡単な説明】
【0020】
【図1】本発明に係るネットワーク品質算出システムの第1の設置構成例を示すブロック図である。
【図2】本発明に係るネットワーク品質算出システムの第2の設置構成例を示すブロック図である。
【図3】本発明に係るネットワーク品質算出システムによる第1の品質推定結果例を示す説明図である。
【図4】本発明に係るネットワーク品質算出システムの第3の設置構成例を示すブロック図である。
【図5】本発明に係るネットワーク品質算出システムの内部構成例を示すブロック図である。
【図6】図5におけるフロー管理部で保持・管理するフロー管理テーブルの構成例を示す説明図である。
【図7】図5におけるパケット情報蓄積・分析部で保持・管理するパケット蓄積情報の構成例を示す説明図である。
【図8】本発明に係るネットワーク品質算出システムの第4の設置構成例を示すブロック図である。
【図9】本発明に係るネットワーク品質算出システムによる第2の品質推定結果例を示す説明図である。
【図10】図5におけるネットワーク品質算出システムの本発明に係る第1のネットワーク品質算出手順例を示すフローチャートである。
【図11】図5におけるネットワーク品質算出システムの本発明に係る第2のネットワーク品質算出手順例を示すフローチャートである。
【図12】図5におけるネットワーク品質算出システムの本発明に係る第3のネットワーク品質算出手順例を示すフローチャートである。
【発明を実施するための形態】
【0021】
以下、図を用いて本発明を実施するための最良の形態例を説明する。先ず、図4〜図7を用いて、本発明に係るネットワーク品質算出システムの構成と動作について説明する。
【0022】
図4において、フロー品質推定装置43は、本発明に係るネットワーク品質算出システムを実装したコンピュータ装置であり、図5に示すように、プログラムされたコンピュータ処理を実行する手段として、パケットヘッダ解析部43a、フロー管理部43b、パケット情報蓄積・分析部43c、パケットカウント部43d、サンプリング部43eを有している。
【0023】
すなわち、本例のネットワーク品質算出システムを構成するコンピュータ装置(フロー品質推定装置43)は、CPUと主メモリの他に、表示装置、入力装置、外部記憶装置等を具備し、光ディスク駆動装置等を介してCD−ROM等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みCPUで処理することにより、パケットヘッダ解析部43a、フロー管理部43b、パケット情報蓄積・分析部43c、パケットカウント部43d、サンプリング部43eの機能を実行する。このような構成により、本例のネットワーク品質算出システムを構成するコンピュータ装置(フロー品質推定装置43)は、プログラムされたコンピュータ処理によって、図4におけるノードA41とノードB42間に流れるパケットを収集して、ノードA41とノードB42間のリンクの通信品質を求める。
【0024】
すなわち、パケットカウント部43dは、ノードA41からノードB42方向のパケットを予め定められた間隔でサンプリングし、サンプリング部43eは、サンプリング部43eがサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っているか否かを判別し、立っていれば、パケットヘッダ解析部43aは、このパケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報が、図6に示す予め記憶装置に記憶されたフロー管理テーブル61に登録されているか否かを判別し、登録されていなければ、フロー管理部43bを介して、このパケットのフロー情報を、フロー管理テーブル61に新規登録する。
【0025】
パケット情報蓄積・分析部43cは、フロー管理部43bがフロー管理テーブル61に新規登録したパケットの到着時刻とヘッダ情報を、図7に示す、予め記憶装置に記憶されたパケット情報蓄積テーブル71に格納すると共に、図4におけるノードA41からノードB42方向のパケットが到着する度に、当該パケットのフロー情報を読み出し、当該パケットのフロー情報が既にフロー管理テーブル61に登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブル71に格納する。
【0026】
また、パケット情報蓄積・分析部43cは、図4におけるノードB42からノードA41方向のパケットが到着する度に、このパケットのフロー情報を読み出し、このフロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報がフロー管理テーブル61に登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブル71に格納する。
【0027】
さらに、パケット情報蓄積・分析部43cは、予め定められた期間毎に、パケット情報蓄積テーブル71に格納されたパケットの到着時刻とヘッダ情報を用いて、フロー品質推定装置43(ネットワーク品質算出システム)とノードB42間の通信品質を算出する。
【0028】
また、サンプリング部43eとパケットヘッダ解析部43aおよびフロー管理部43bによる、図4におけるノードA41からノードB42方向のパケットに対する処理を、ノードB42からノードA41方向のパケットに対しても実行すると共に、パケット情報蓄積・分析部43cによる、図4におけるノードB42からノードA41方向のパケットに対する処理を、ノードA41からノードB42方向のパケットに対して実行し、パケット情報蓄積・分析部43cは、フロー品質推定装置43(ネットワーク品質算出システム)とノードB42間の通信品質の算出と共に、フロー品質推定装置43(ネットワーク品質算出システム)とノードA41間の通信品質の算出も行い、結果として、ノードA41とノードB42間のリンクを通過するフローの通信品質を算出する。
【0029】
以下、パケット情報蓄積・分析部43cによる通信品質の算出の詳細を含め、図4〜図7を用いて、本発明に係るネットワーク品質算出技術の実施例について説明する。
【0030】
[実施例1]
図4においては、本発明が適用されるIPネットワークの基本構成の一例を示しており、この図4に示すように、フロー通信品質推定装置43は、ノード(スイッチやルータ)A41,B42間のリンクに挿入される形態で利用される。あるいは、ノードA41,B42において、パケットをポートへミラーして、そのポートの先にフロー通信品質推定装置43を設置する構成としてもよい。
【0031】
図5において、前段ノードA41,B42からパケットが到着すると、パケットヘッダ解析部43aは、ノードA41からノードB42方向のパケットか、ノードB42からノードA41方向のパケットかを判別する。
【0032】
ノードA41からノードB42方向である場合、パケットヘッダ解析部43aは、当該パケットから、「発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)」からなるフロー情報を読み出し、フロー管理部43bが記憶装置に記憶しているフロー管理テーブル61(FT_AtoB)に既にエントリされているフローからのパケットかどうか調べ、もしそうであれば、フロー管理部43bにヘッダ情報を通知する。
【0033】
図6において、このフロー管理テーブル61の例を示す。フロー管理テーブル61では、{srcIP,dstIP,srcPort,dstPort,Protocol}の5つ組をキーとして管理している。
【0034】
その後、パケットヘッダ解析部43aは、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP、srcIP、dstPort、srcPort、Protocol}が、フロー管理部43b内のフロー管理テーブル61(FT_BtoA)にエントリされているか否かを調査し、既にエントリされている場合、フロー管理部43bにヘッダ情報を通知する。
【0035】
また、ノードB42からノードA41方向である場合、パケットヘッダ解析部43aは、当該パケットから、{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を読み出し、フロー管理部43b内に存在するフロー管理テーブル61(FT_BtoA)に既にエントリされているフローからのパケットかどうか調べ、もしそうであれば、フロー管理部43bにヘッダ情報を通知する。
【0036】
その後、パケットヘッダ解析部43aは、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP、srcIP、dstPort、srcPort、Protocol}が、フロー管理部43b内のフロー管理テーブル61(FT_AtoB)に既にエントリされているか否かを調査し、既にエントリされている場合、フロー管理部43bにヘッダ情報を通知する。
【0037】
その後、パケットヘッダ解析部43aは、パケットをパケットカウント部43dに転送する。
【0038】
パケットカウント部43dでは、ノードA41からノードB42方向、ノードB42からノードA41方向の各々を区別して、ノードA41からノードB42方向のパケット到着数C_AtoBと、ノードB42からノードA41方向のパケット到着数C_BtoAをカウントしている。
【0039】
また、パケットカウント部43dは、パケット到着毎にその方向をみて、該当する方向のカウンタをカウントアップする。その後、カウンタ値をN(Nは予め定めたサンプリング周期)で割った余りが「0」と等しいかチェックする。
【0040】
もし、余りが「0」であれば、パケットカウント部43dは、当該パケットをサンプリング部43eに転送し、同時に、当該パケットを後段ノードA41,B42に転送する。
【0041】
余りが「0」でなければ、パケットカウント部43dは、単に、後段ノードA41,B42への当該パケットの転送を行う。
【0042】
あるいは、パケットカウント部43dは、パケット到着毎に「0」から「1」の範囲で乱数を発生させ、その結果が「1/N」以下であれば、当該パケットをパケットヘッダ解析部43aに転送してから後段ノードA41,B42に、当該パケットを転送し、「1/N」以下でなければ、単に、後段ノードA41,B42へ当該パケットを転送するのみ、としてもよい。
【0043】
サンプリング部43eでは、到着パケットのヘッダを読み込み、TCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aへ転送する。
【0044】
パケットヘッダ解析部43aでは、サンプリング部43eからパケットが転送されてきたら、そのパケットの方向に応じたフロー管理テーブルを読み出し(もし、ノードA41からノードB42方向であれば、FT_AtoBを読み出す)、そのパケットの{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}がフロー管理テーブル61にエントリされているか否かを判定し、エントリされていなければ、当該パケットがどのフローからのパケットかを定める5つの属性である{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を、フロー管理部43bを介してフロー管理テーブル61に新規エントリする。
【0045】
フロー管理部43bは、パケットヘッダ解析部43aからパケットを受信すると、当該パケットをパケット情報蓄積・分析部43cへ転送する。
【0046】
パケット情報蓄積・分析部43cにおいては、一定期間収集されたパケットヘッダ情報とパケットが観測されたタイムスタンプ情報を管理している。
【0047】
図7においては、パケット情報蓄積・分析部43cが管理しているパケット情報の例を示しており、パケットヘッダの情報として、srcIP.srcPort,dstIP.dstPort,Protocol,パケットサイズ,シーケンス番号,Ack番号を保持する。
【0048】
このようなパケット蓄積テーブル71においてヘッダ情報(フロー情報)や到着時刻(タイムスタンプ)等の情報が蓄積されたパケットに対して、パケット情報蓄積・分析部43cは、ノードA41からノードB42の方向に流れていたパケットのうち、{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}の5つ組を同じくするパケット群(これをフローiとよぶ)、ならびに、ノードB42からノードA41の方向に流れていたパケットのうち、フローiの通信に該当するパケット群、つまり、ノードA41からノードB42のフローiにおける発着IPアドレスおよび発着ポート番号を入れ替えた{dstIP#i、srcIP#i、dstPort#i、srcPort#i、Protocol#i}の5つ組を同じくするパケット群、を抽出する。尚、このようにして、抽出された双方向のパケット群を双方向フローiとよぶ。
【0049】
また、パケット情報蓄積・分析部43cは、抽出したパケット群を到着順に並び替える。
【0050】
そして、パケット情報蓄積・分析部43cは、ノードA41からノードB42の方向に流れる各パケットkに対して、ノードB42からノードA41の方向の確認応答パケット(Ackパケットk)をみつけ、後者の該Ackパケットkの到着時刻T_AB_ack(k,i)から前者のパケットkの到着時刻T_AB(k,i)を差し引いたRTT_AB(k,i)=T_AB_ack(k,i)−T_AB(k,i)を計算する。
【0051】
例えば、図7に示す例においては、1番目のパケットに対するAckパケットが7番目のパケットとなる。すなわち、7番目のパケットにおけるどのパケットのsrcIP.srcPortとdstIP.dstPortを入れ替えたものが1番目のパケットに対応していることと、1番目のパケットのシーケンス番号1256139556に該パケットサイズ1460byteを加算した値1256141016が7番目のパケットのAck番号と一致していることから、7番目のパケットが1番目のパケットのAckパケットであると判別している。
【0052】
パケット情報蓄積・分析部43cは、このような動作を、双方向フローiの各パケットについて実施し、「RTT_AB_avg(i)=ΣRTT_AB(k,i)/n(i)」 (・・・ここでn(i)は観測されたパケットkとそのackパケットkのペアの数)と、「RTT_AB_min(i)=min{RTT_AB(k,i)}」を計算する。
【0053】
さらに、パケット情報蓄積・分析部43cは、ノードB42からノードA41の方向に流れるパケットk’に対して、ノードA41からノードB42の方向のAckパケットk’をみつけ、上記と同様の手順で、RTT_BA(k’,i)を求め、「RTT_BA_avg(i)=ΣRTT_BA(k’,i)/n’(i)」 (・・・ここでn’(i)は観測されたパケットk’とそのackパケットk’のペアの数)と、「RTT_BA_min(i)=min{RTT_BA(k’,i)}を計算する。
【0054】
そして、パケット情報蓄積・分析部43cは、「RTT_avg(i)=RTT_AB_avg(i)+RTT_BA_avg(i)」と、
「RTT_min(i)=RTT_AB_min(i)+RTT_BA_,min(i)」と、
を計算し、双方向フローiのエンドエンドでの往復伝播遅延時間の平均をRTT_avg(i)、最小値をRTT_min(i)として推定する。
【0055】
尚、フロー管理テーブル61は、一定期間経過したら、クリアする。
【0056】
[実施例2]
実施例1において蓄積した双方向フローi内のパケットについて、パケット情報蓄積・分析部43cは、ノードA41からノードB42方向のパケットk(その到着時刻をT_AB(k,i)とする)に対応する、ノードB42からノードA41方向のAckパケットkをみつけ、かつ、そのAckパケットkに対する、ノードA41からノードB42方向のAckパケットkと、その到着時刻をT_AB_ack(k,i)とする)をみつけたら、「RTT(k,i)=T_AB_ack(k,i)−T_AB(k,i)」とし、双方向フローiのエンドエンドでの往復伝播遅延時間の平均を、「RTT_avg(i)=ΣRTT(k,i)/n’’(i)」 ・・・(n’’(i)は上記パケット−Ack−AckのAckの組の数)により算出し、また、最小値を、「RTT_min(i)=min{RTT(k,i)}」により算出し、そして、最大値を、「RTT_max(i)=max{RTT(k,i)}」により算出する。
【0057】
[実施例3]
また、パケット情報蓄積・分析部43cは、双方向フローiを構成するパケットのうち、ノードA41からノードB42方向の再送パケット数n_ret_AB(i)、および、逆方向の再送パケット数n_ret_BA(i)をカウントし、また、ノードA41からノードB42方向のパケット数n_AB(i)、および、逆方向のパケット数n_BA(i)をカウントし、ノードA41からノードB42方向のパケット再送率R_ret_AB(i)を、「R_ret_AB(i)=n_ret_AB(i)/n_AB(i)」により算出し、また、逆方向のパケット再送率R_ret_BA(i)を、「R_ret_BA(i)=n_ret_BA(i)/n_BA(i)」により算出する。
【0058】
[実施例4]
また、パケット情報蓄積・分析部43cは、予め用意した、再送率R_retとパケット損失率R_lossの関係式R_loss=f(R_ret)を用いて、双方向フローiのエンドエンド間でのパケット損失率R_loss(i)を、「R_loss(i)=1−{1−f(R_ret_AB(i)}{1−f(R_ret_BA(i)}」により算出する。
【0059】
[実施例5]
また、パケット情報蓄積・分析部43cは、双方向フローiにおいて、ノードA41からノードB42の方向へ流れるパケットのバイト数の総和を、ノードA41からノードB42へ流れるパケットのうち、最後に到着したパケットの到着時刻と最初に到着したパケットの到着時刻の差で割ったものを、ノードA41からノードB42方向のスループットTh_AB(i)とし、スループットを算出する。
【0060】
また、パケット情報蓄積・分析部43cは、実施例1または実施例2で得られるRTT_avg(i)を用いて、予め用意したスループットThとパケット損失率R_lossとRTTの関係式Th=g(R_loss,RTT)より、パケット損失率R_loss(i)を算出する。
【0061】
尚、スループットThとパケット損失率R_lossとRTTの関係式Th=g(R_loss,RTT)として、例えば、公知文献である「J.Padhye et al.,“Modeling TCP Reno performance: a simple model and its empirical validation”,IEEE/ACM Tansactions on Netwoking,2000.」に記載の技術に基づく、Th=MSS/{RTT×(R_loss)1/2}を用いる。
【0062】
[実施例6]
また、パケット情報蓄積・分析部43cは、実施例1から実施例5のいずれかの技術で双方向フローiについて品質d(i)を算出し、フローiの{発信元IPアドレスsrcIP#i,着信先IPアドレスdstIP#i}を、予め記憶装置に記憶された地理データベースを用いてsrcIP#iの所属するエリアArea#A,およびdstIP#iの所属するエリアArea#Bへマップし、それを、観測された全ての双方向フローi(i=1〜全フロー数)について実施して、エリアAとエリアBの間の品質d(A,B)を、「d(A,B)=ΣsrcIP#i∈A ∧ dstIP#i∈Bd(i)/|srcIP#i∈A ∧ dstIP#i∈B|」により算出する。
【0063】
尚、|srcIP#i∈A ∧ dstIP#i∈B|は、srcIP#iがエリアAに所属し、かつdstIP#iがエリアBに所属した、フローの数を意味する。
【0064】
[実施例7]
実施例7では、実施例1のように、{srcIP、dstIP、srcPort、dstPort、Protocol}をキーとしたフロー管理テーブル61を、出現した全てのフローを収容できるように作成する代わりに、Bloom filter(BF)を用いる。
【0065】
BFでは、異なるK個のハッシュ関数(それぞれがキー値をサイズbの範囲内でハッシュ値を返す)と、サイズbのビットマップ(初期状態では全てをゼロにリセットされる)を用意する。
【0066】
パケットカウント部43dは、ノードA41からノードB42方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、サンプリング部43eは、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aに通知し、パケットヘッダ解析部43aは、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積・分析部43cに収集させる。
【0067】
そして、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする。
【0068】
また、パケットヘッダ解析部43aは、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、当該パケットをパケット情報蓄積・分析部43cに収集させる。
【0069】
パケットヘッダ解析部43aおよびパケット情報蓄積・分析部43cは、上記ノードA41からノードB42の方向に流れるパケットストリームに対するパケット収集とは別に、ノードB42からノードA41の方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0070】
パケットヘッダ解析部43aは、ノードB42からノードA41方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0071】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断して、パケット情報蓄積・分析部43cに収集させる。
【0072】
尚、パケットヘッダ解析部43aは、一定期間BFによるパケット監視を実施したら、BF内のビットを全て0にクリアする。
【0073】
[実施例8]
実施例7におけるパケット収集処理に加えて、パケットカウント部43dにおいて、ノードB42からノードA41の方向のパケットストリームに対して、N個の到着パケットに対し1個のパケットを抽出し、サンプリング部43eにおいて、当該パケットのヘッダ情報を読み込んで、TCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aに通知し、パケットヘッダ解析部43aにおいて、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積・分析部43cにおいて収集させる。
【0074】
また、パケットヘッダ解析部43aにおいて、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断し、パケット情報蓄積・分析部43cにおいて収集させる。
【0075】
パケットヘッダ解析部43aとパケット情報蓄積・分析部43cにおいて、上記ノードB42からノードA41の方向に流れるパケットストリームに対するパケット収集とは別に、ノードA41からノードB42の方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0076】
パケットヘッダ解析部43aにおいて、ノードA41からノードB42方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}を用いて、BFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断して、パパケット情報蓄積・分析部43cにおいて収集させる。
【0077】
[実施例9]
実施例9においては、実施例1から実施例5のように、一定期間パケット収集してから品質を推定する代わりに、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル(初期状態では全てをゼロにリセットされる)を予め記憶装置上に用意する。この時刻テーブルは、パケットの到着時刻を記憶するために用いる。
【0078】
パケットカウント部43dにおいて、ノードA41からノードB42方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、サンプリング部43eは、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aに通知し、パケットヘッダ解析部43aにおいては、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、対応する位置に現在の時刻を書き込む。
【0079】
また、パケットヘッダ解析部43aは、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、全てゼロ以外の値である場合には、そこに既に現在の時刻を書き込む。
【0080】
さらに、パケットヘッダ解析部43aは、上記ノードA41からノードB42の方向に流れるパケットストリームに対する処理とは別に、ノードB42からノードA41の方向のパケットストリームに対しても以下の手順でパケットを処理する。
【0081】
ノードB42からノードA41方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0082】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、K個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、その中で最も古い時刻を読み出し、現在の時刻からその最も古い時刻を差し引いた値を、そのパケットjの属するフローの、ノードA41からノードB42方向へのパケットに対するAckパケットが返ってくるまでの遅延時間RTTとして推定する。
【0083】
[実施例10]
実施例10においては、BFを2つ用意し(BF1とBF2とする)、最初の測定期間は、いずれのBFにも同じ処理を施し、2番目の測定期間においては、BF1のみをクリアし、ノードA41からノードB42方向のパケットに対する処理(N個に1個サンプルしてSYNがたっていればBFへ入力、またはそれと独立して各パケットをBFへ入力する処理)はBF1に対してのみ実施し、ノードB42からノードA41方向のパケットに対する処理(発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキーをBFへ入力する処理)はBF1,2両方に対して実施する。
【0084】
3番目の測定期間では、BF2をクリアして上記と同様の手順を行い、これを交互に繰り返す。
【0085】
[実施例11]
実施例11においては、実施例1のようにSYNをみてサンプリングする代わりに、パケット到着毎に{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとして、予め用意したハッシュ関数に入力し、ハッシュ値を得、その値をハッシュ値の取りうる値の最大値で割った値が、「1/N」よりも小さければ、そのパケットをサンプリングする。
【0086】
[実施例12]
実施例1では、ノード間に挿入する形で帯域管理装置を実現しているが、そうする代わりに、図8に示すように、品質推定装置81において、IPネットワーク83上の各ノード82a〜82gからサンプルパケット情報を収集し、ネットワーク全体に対して同様の管理を実行する構成としても良い。
【0087】
以上説明したように、本例によれば、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質(遅延、パケット損失率、スループット)を推定することが可能となる。
【0088】
実際に、本例の動作を、実測データを用いて検証した結果を図9の品質推定結果テーブル(図中「品質推定結果」と記載)91に示す。これは、国内トラヒックに対して、サンプリングしなかった場合と、N=10(1/10サンプリング)の場合における、品質推定結果である。これより、サンプル後もサンプル前の品質の傾向を把握できていることが分かる。
【0089】
次に、図1から図3および図10から図12を用いて、図5におけるネットワーク品質算出システム(フロー品質推定装置43)の本発明に係る処理手順例(ネットワーク品質算出方法)を説明する。
【0090】
図1,2においては、エンドホストa1a,21aが接続されたルータA2a,22aと、エンドホストb1b,21bが接続されたルータB2b,22bとの間にある監視点3,23に図5におけるネットワーク品質算出システム(フロー品質推定装置43)が設けられている。
【0091】
図10を用いて、本例の第1の処理手順方法を説明する。本第1の方法では、通信網において、ルータAとルータBをつなぐリンクにおいて、トラヒックをルータAからルータBの方向、およびルータBからルータAの双方向で監視し、ルータAからルータBの方向に流れるパケットストリームにおいて(ステップS1001,S1002)、N個の到着パケットに対し1個のパケットを抽出し(ステップS1003)、抽出したパケットのヘッダ情報を読み込んで、TCPの通信開始を表すSYNフラグが立っており(ステップS1004)、かつ、予め記憶装置に記憶されたフロー管理テーブル(以下、フロー管理テーブルFT_AtoBとよぶ)に該フローの情報がエントリされていなければ(ステップS1005)、該パケットがどのフローからのパケットかを定める5つの属性である{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を、フロー管理テーブルFT_AtoBに新規エントリする(ステップS1006)。同時に、該パケットの到着時刻および該パケットヘッダ情報を、予め記憶装置に記憶されたパケット情報蓄積テーブルに収集する(ステップS1007)。
【0092】
また、N個に1個のパケット抽出とは独立に(ステップS1003)、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、この5つ組のキーが既にフロー管理テーブルFT_AtoBにエントリされているか否かを調査し(ステップS1008)、既にエントリされている場合、該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1009)。
【0093】
上記ルータAからルータBの方向に流れるパケットストリームに対するパケット収集とは別に、ルータBからルータAの方向のパケットストリームに対しても、以下の手順でパケットを収集する。
【0094】
ルータBからルータA方向のパケットが到着したら(ステップS1002)、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出し、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}が(ステップS1010)、フロー管理テーブルFT_AtoBにエントリされているか否かを調査し(ステップS1011)、既にエントリされている場合、該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1012)。
【0095】
これを一定期間継続し(ステップS1013)、パケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を推定する(ステップS1014)。
【0096】
ここで、単純なN個に1個のパケットサンプリングではなく、SYNの有無をみてサンプリングする理由を述べる。
【0097】
単純な1/N個のサンプリングでは、たくさんのパケットを送出しているフローからのパケットがサンプルされやすくなるが、SYNパケットベースのサンプリングであれば、SYNパケット(TCP通信の開始を表す)は、通常、どのフローも一つであるため、フローの大きさ(パケット数)に依らず同じ確率でサンプリングすることが可能となるからである。
【0098】
こうすることによって、特定のフローに偏ることなく、ネットワーク全体を流れるフローの品質を満遍なく把握可能としている。
【0099】
また、エンドエンド間の往復遅延の推定を可能とするために、ルータAからルータB方向だけでなく、ルータBからルータA方向のパケットも収集している。つまり、図1に示すように、両方向のパケットを収集して、監視点3とエンドホストb1b間の品質(往復遅延)が把握可能となる。詳細な遅延推定手順は、以下の第3の方法以降で説明する。
【0100】
第2の方法においては、第1の方法と同様の手順を、ルータBからルータAの方向のパケットストリームに対しても実施する。
【0101】
具体的には、図11に示すように、ルータBからルータAの方向のパケットストリームに対して(ステップS1101,S1102)、N個の到着パケットに対し1個のパケットを抽出し(ステップS1103)、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っており(ステップS1104)、かつ、予め用意したフロー管理テーブル(以下、フロー管理テーブルFT_BtoAとよぶ)に該フローの情報がエントリされていなければ(ステップS1105)、該パケットの{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}をフロー管理テーブルFT_BtoAに新規エントリする(ステップS1106)。同時に、該パケットの到着時刻および該パケットのヘッダを、予め用意したパケット情報蓄積テーブルに収集する(ステップS1107)。
【0102】
N個に1個のパケット抽出とは独立に(ステップS1103)、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、この5つ組のキーが既にフロー管理テーブルFT_BtoAにエントリされているか否かを調査し(ステップS1108)、既にエントリされている場合、該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1109)。
【0103】
上記ルータBからルータAの方向に流れるパケットストリームに対するパケット収集とは別に(ステップS1102)、ルータAからルータBの方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0104】
ルータAからルータB方向のパケットが到着したら(ステップS1102)、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出し、発着IPアドレスおよび発着ポート番号を入れ替えて(ステップS1110)構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}がフロー管理テーブルFT_BtoAにエントリされているか否かを調査し(ステップS1111)、既にエントリされている場合、該パケットヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1112)。
【0105】
これを一定期間継続し(ステップS1113)、第1の方法の手順でパケット情報蓄積テーブルに収集されたパケットヘッダ情報に加え、本第2の方法の手順でパケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を推定する。
【0106】
このようにルータBからルータA方向についてもパケット収集することにより、図2に示すように、監視点とエンドホストa21a(ルータA22a側のホスト)との品質が把握可能となる。これと、第1の方法での品質(監視点3,23とエンドホストb1b,21b間)を合わせて、エンドホストa21a−b21b間の品質を把握可能としている。
【0107】
本例の第3の方法においては、図12に示すように、第1の方法または第2の方法で収集されたパケットヘッダに対して、ルータAからルータBの方向に流れていたパケットのうち、{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}の5つ組を同じくするパケット群(これをフローiとよぶ)、ならびに、ルータBからルータAの方向に流れていたパケットのうち上記フローiの通信に該当するパケット群、つまり、ルータAからルータBのフローiにおける発着IPアドレスおよび発着ポート番号を入れ替えた{dstIP#i、srcIP#i、dstPort#i、srcPort#i、Protocol#i}の5つ組を同じくするパケット群、を抽出する(ステップS1201)。抽出した双方向のパケット群を双方向フローiとよぶ。
【0108】
これらパケット群を到着順に並び替え(ステップS1202)、ルータAからルータBの方向に流れる各パケットkに対して(ステップS1203のY)、ルータBからルータAの方向の確認応答パケット(Ackパケットk)をみつけ(ステップS1204)、後者のAckパケットkの到着時刻T_AB_ack(k,i)から前者のパケットkの到着時刻T_AB(k,i)を差し引いたRTT_AB(k,i)=T_AB_ack(k,i)−T_AB(k,i)を計算する(ステップS1205)。
【0109】
これを双方向フローiの各パケットについて実施し(ステップS1206)、「RTT_AB_avg(i)=ΣRTT_AB(k,i)/n(i)」 (・・・ここでn(i)は観測されたパケットkとそのackパケットkのペアの数)による平均値RTT_AB_avg(i)と、「RTT_AB_min(i)=min{RTT_AB(k,i)}」による最小値RTT_AB_min(i)を計算する(ステップS1207)。これが図1における「監視点−エンドホストb(ルータB側)」の品質に相当する。
【0110】
次に、ルータBからルータAの方向に流れるパケットk’に対して(ステップS1203のN)、ルータAからルータBの方向のAckパケットk’をみつけ(ステップS1208)、上記と同様の手順で、平均値RTT_BA_avg(i)と最小値RTT_BA_min(i)を求め(ステップS1209〜S1211)、ステップS1207とステップS1211で求めたそれぞれの平均値と最小値をそれぞれ加算して、双方向フローiのエンドエンドの往復伝播遅延時間の平均と最小値を求める。
【0111】
すなわち、ステップS1211において、「RTT_BA_avg(i)=ΣRTT_BA(k’,i)/n’(i)」 (…ここでn’(i)は観測されたパケットk’とそのackパケットk’のペアの数)と、「RTT_BA_min(i)=min{RTT_BA(k’,i)}」を計算する。これが図2における「監視点43−エンドホストb21b(ルータB22b側)」の品質に相当する。
【0112】
そして、ステップS1212において、「RTT_avg(i)=RTT_AB_avg(i)+RTT_BA_avg(i)」、および、「RTT_min(i)=RTT_AB_min(i)+RTT_BA_,min(i)」、を計算し、双方向フローiのエンドエンドでの往復伝播遅延時間の平均をRTT_avg(i)、最小値をRTT_min(i)として求める。
【0113】
本例の第4の方法においては、第3の方法における双方向フローi内のパケットについて、ルータAからルータB方向のパケットk(その到着時刻をT_AB(k,i)とする)に対応するルータBからルータA方向のAckパケットkをみつけ、かつそのAckパケットkに対するルータAからルータB方向のAckパケットkその到着時刻をT_AB_ack(k,i)とする)をみつけたら、「RTT(k,i)=T_AB_ack(k,i)−T_AB(k,i)」とし、双方向フローiのエンドエンドでの往復伝播遅延時間の平均を、「RTT_avg(i)=ΣRTT(k,i)/n’’(i)」 (…尚、n’’(i)は上記パケット−Ack−AckのAckの組の数)、により推定し、最小値を、「RTT_min(i)=min{RTT(k,i)}」、により推定し、最大値を、「RTT_max(i)=max{RTT(k,i)}」により推定する。
【0114】
本例の第5の方法においては、双方向フローiを構成するパケットのうち、ルータAからルータB方向の再送パケット数n_ret_AB(i)および逆方向の再送パケット数n_ret_BA(i)をカウントし、また、ルータAからルータB方向のパケット数n_AB(i)および逆方向のパケット数n_BA(i)をカウントし、ルータAからルータB方向および逆方向のパケット再送率を、「R_ret_AB(i)=n_ret_AB(i)/n_AB(i)」および「R_ret_BA(i)=n_ret_BA(i)/n_BA(i)」により算出する。
【0115】
本例の第6の方法においては、予め用意した、再送率R_retとパケット損失率R_lossの関係式R_loss=f×(R_ret)を用いて、双方向フローiのエンドエンド間でのパケット損失率R_loss(i)を、「R_loss(i)=1−{1−f×(R_ret_AB(i)}×{1−f×(R_ret_BA(i)})により算出する。
【0116】
TCPでは、パケット損失が発生するとパケットを再送するため、一般に再送数とパケット損失率は相関がある。もっとも単純な例としては、再送率とパケット損失率を近似的に等しいとすることが考えられる。
【0117】
尚、エンドエンド間でのパケット損失率を、「R_loss(i)=1−{1−f×(R_ret_AB(i)}×{1−f×(R_ret_BA(i)})で推定している理由を述べる。
【0118】
f×(R_ret_AB(i))は、図1での監視点−エンドホストb間のパケット損失率となり、f×(R_ret_BA(i))は、図2での監視点−エンドホストa間のパケット損失率となる。
【0119】
前者と後者のパケット損失が独立に発生すると仮定すれば、エンドエンドでのパケット損失率は、「1−{1−f×(R_ret_AB(i)}×{1−f×(R_ret_BA(i)}」となる。
【0120】
本例の第7の方法においては、双方向フローiにおいて、ルータAからルータBの方向へ流れるパケットのバイト数の総和を、ルータAからルータBへ流れるパケットのうち、最後に到着したパケットの到着時刻と最初に到着したパケットの到着時刻の差で割ったものを、ルータAからルータB方向のスループットTh_AB(i)とし、スループットを求める。
【0121】
また、第3の方法または第4の方法で得られるRTT_avg(i)を用いて、予め用意したスループットThとパケット損失率R_lossとRTTの関係式「Th=g×(R_loss,RTT)」より、パケット損失率R_loss(i)を算出する。尚、関数g()については、次の第8の方法に示す。
【0122】
本例の第8の方法においては、第7の方法におけるスループットThとパケット損失率R_lossとRTTの関係式「Th=g×(R_loss,RTT)」として、「Th=MSS/{RTT×(R_loss)1/2}を用いる。これは、上述の公知文献(「J.Padhye et al.,“Modeling TCP Reno performance: a simple model and its empirical validation”,IEEE/ACM Tansactions on Netwoking,2000.」)に記載の技術に基づく。
【0123】
本例の第9の方法においては、第3の方法から第8の方法のいずれかの方法で双方向フローiについて品質d(i)を推定し、フローiの{発信元IPアドレスsrcIP#i,着信先IPアドレスdstIP#i}を、予め用意した地理データベースを用いて、srcIP#iの所属するエリアArea#A、および、dstIP#iの所属するエリアArea#Bへマップし、それを、観測された全ての双方向フローi(i=1〜全フロー数)について実施して、エリアAとエリアBの間の品質d(A,B)を、「d(A,B)=ΣsrcIP#i∈A ∧ dstIP#i∈Bd(i)/|srcIP#i∈A ∧ dstIP#i∈B|」により求める。
【0124】
尚、上述したように、|srcIP#i∈A ∧ dstIP#i∈B|は、srcIP#iがエリアAに所属し、かつ、dstIP#iがエリアBに所属した、フローの数を意味する。
【0125】
こうすることにより、例えば、県別の品質がどのようになっているかを把握可能である。例として、ある測定点でのトラヒックデータを対象に分析した結果を図3に示す。
【0126】
本例の第10の方法においては、第1の方法または第2の方法のように、{srcIP、dstIP、srcPort、dstPort、Protocol}をキーとしたフローテーブルを、出現した全てのフローを収容できるように作成する代わりに、BloomFilter(BF)を用いる。
【0127】
BFでは、異なるK個のハッシュ関数(それぞれがキー値をサイズbの範囲内でハッシュ値を返す)と、サイズbのビットマップ(初期状態では全てをゼロにリセットされる)を用意する。
【0128】
ルータAからルータB方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積テーブルに収集する。
【0129】
そして、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする。N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断してパケット情報蓄積テーブルに収集する。
【0130】
上記ルータAからルータBの方向に流れるパケットストリームに対するパケット収集とは別に、ルータBからルータAの方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0131】
ルータBからルータA方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0132】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、パケット情報蓄積テーブルに収集する。
【0133】
これを一定期間継続し、パケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を求める。
【0134】
上記のように、BFを使うことにより、全てのサンプルフローを管理することなく、必要なパケット収集を可能としている。
【0135】
本例の第11の方法においては、第10の方法のパケット収集処理に加えて、ルータBからルータAの方向のパケットストリームに対して、N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積テーブルに収集する。
【0136】
また、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断してパケット情報蓄積テーブルに収集する。
【0137】
さらに、上記ルータBからルータAの方向に流れるパケットストリームに対するパケット収集とは別に、ルータAからルータBの方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0138】
ルータAからルータB方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0139】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}を用いて、BFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、パケット情報蓄積テーブルに収集する。
【0140】
これを一定期間継続し、パケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を推定する。
【0141】
本例の第12の方法においては、第3の方法から第8の方法のように、一定期間パケット収集してから品質を推定する代わりに、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル(初期状態では全てをゼロにリセットされる)を記憶装置上に用意する。この時刻テーブルは、パケットの到着時刻を記憶するために用いる。
【0142】
そして、ルータAからルータB方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、対応する位置に現在の時刻を書き込む。
【0143】
さらに、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、全てゼロ以外の値である場合には、そこに既に現在の時刻を書き込む。
【0144】
また、上記ルータAからルータBの方向に流れるパケットストリームに対する処理とは別に、ルータBからルータAの方向のパケットストリームに対しても以下の手順でパケットを処理する。
【0145】
ルータBからルータA方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0146】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、K個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、その中で最も古い時刻を読み出し、現在の時刻からその最も古い時刻を差し引いた値を、そのパケットjの属するフローの、ルータAからルータB方向へのパケットに対するAckパケットが返ってくるまでの遅延時間RTTとして求める。
【0147】
通常のBFでは、ビットマップを用意するのに対し、ここでは、ビット情報ではなく、パケット到着時刻情報を管理するようにすることにより、パケットを一旦蓄積することなく、オンラインでRTTの推定を可能としている。
【0148】
本例の第13の方法においては、第10の方法から第12の方法のようにBloom Filter(BF)を用いる場合に、一定期間BFによるパケット監視を実施したら、BF内のビットを全て0にクリアする。
【0149】
BFは、定期的にクリアしないで長時間継続的に利用すると、全てのビットが1で埋まってしまい、適切な新規フロー判定が困難になるため、ここでは一定周期ごとにクリアする。
【0150】
本例の第14の方法においては、BFを2つ用意し(BF1とBF2とする)、最初の測定期間は、いずれのBFにも同じ処理を施し、2番目の測定期間においては、BF1のみをクリアし、ノードA41からノードB42方向のパケットに対する処理(N個に1個サンプルしてSYNがたっていればBFへ入力、またはそれと独立して各パケットをBFへ入力する処理)はBF1に対してのみ実施し、ルータBからルータA方向のパケットに対する処理(発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキーをBFへ入力する処理)はBF1,2両方に対して実施する。
【0151】
そして、3番目の測定期間では、BF2をクリアして上記と同様の手順を行い、これを交互に繰り返す。
【0152】
このように、BFを2つ用意する理由を述べる。フローによっては、RTTが非常に大きいものもあるため、ルータAからルータB方向のパケットを観測してから、そのAckパケットをルータBからルータA方向で検出するのに時間を要する場合がある。
【0153】
対処法としては、BFクリアの周期を長めに設定することが考えられるが、第13の方法でも述べたように、測定周期が長くなると、BFが正しく新規フローの検出をできない可能性がある。
【0154】
そこで、BFを2つ用意して、ルータAからルータB方向の新規フロー検出についてはBF1と2を交互に使うことにより適切に検出し、ルータBからルータA方向のAckパケットについては、BF1,2の両方に対して入力し、いずれかのBFに該当するエントリがあるかどうかをみることで、RTTの長いAckに対しても対応できるようにしている。
【0155】
本例の第15の方法においては、第1の方法または第2の方法のように、SYNをみてサンプリングする代わりに、パケット到着毎に{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとして、予め用意したハッシュ関数に入力し、ハッシュ値を得、その値をハッシュ値の取りうる値の最大値で割った値が、1/Nよりも小さければ、そのパケットをサンプリングする。
【0156】
第1の方法で述べたように、SYNをみてサンプリングする理由は、特定のフローに偏ることなく、ネットワーク全体を流れるフローの品質を満遍なく把握するためであった。この同じ目的を達成する別の方法をここでは述べている。すなわち、フローを特定する{srcIP、dstIP、srcPort、dstPort、Protocol}をキーにしてハッシュにかけてサンプリングすることで、フロー単位での均等なサンプリングを行うことが可能となっている。
【0157】
以上、図1〜図12を用いて説明したように、本例のネットワーク品質算出技術では、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質(遅延、パケット損失率、スループット)を推定することが可能である。
【0158】
尚、本発明は、図1〜図12を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例のネットワーク品質算出システムを実装するコンピュータ装置における、本発明に係る処理を実行するためのプログラムのインストール技術に関しても、記録媒体として、FD(Flexible Disk)等を用いることでも良い。また、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【符号の説明】
【0159】
1a,21a:エンドホストa、1b,21b:エンドホストb、2a,22a:ルータA、2b,22b:ルータB、3,23:監視点、41:ノードA、42:ノードB、43:フロー品質推定装置(ネットワーク品質算出システム)、43a:パケットヘッダ解析部、43b:フロー管理部、43c:パケット情報蓄積・分析部、43d:パケットカウント部、43e:サンプリング部、61:フロー管理テーブル、71:パケット情報蓄積テーブル、81:品質推定装置、82a〜82g:ノード(スイッチ、ルータ)、83:IPネットワーク、91:品質推定結果テーブル。
【技術分野】
【0001】
本発明は、ネットワークの通信品質状態を管理する技術に係り、特に、IPネットワーク全体の通信品質状態を効率よくかつ高精度に把握するのに好適な技術に関するものである。
【背景技術】
【0002】
IPネットワークが広く利用されてくるに伴って、IPネットワーク上での通信品質保証に対する要求が高まっている。それに伴い、ネットワークを流れるトラヒックを測定して現在の通信品質状態を把握することが重要になってきている。
【0003】
エンドエンド遅延時間やパケット損失率、スループットといったネットワークの通信品質を把握する直接的な技術としては、エンドエンド間で試験パケットを送受信することにより品質を能動的に測定する技術がある。
【0004】
例えば、pingコマンドにより往復遅延を測定する技術や、非特許文献1にあるpathcharを用いる技術等がある。また、例えば非特許文献2の技術では、着目するエンドホスト間において、試験パケットによるラウンドトリップタイムやパケット損失率の測定および経路上のボトルネック帯域の測定を実施し、かつ、実際にTCP(Transmission Control Protocol)で通信を行ってスループットを測定し、ウインドーサイズを徐々に大きくしていったときにTCPスループットが増加するかどうか等を詳細に解析する技術が提案されている。
【0005】
しかし、これらの技術は、ある特定のエンドホスト間で、品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した技術であり、このような技術を、ネットワーク提供者がネットワーク内の通信を全体的に管理するのに直接適用すると、測定コストの増大およびネットワークへの測定負荷の増大が生じてしまう。
【0006】
具体的には、監視対象となるネットワークの入り側および出側の全てにおいて、試験パケット送受信機を設置して、試験パケットを送信することによって品質測定を能動的に行う必要があり、測定装置の設置に要するコストが増大してしまう。
【0007】
さらに、試験パケットをネットワークへ付加するため、ネットワークへ余分なトラヒックが加わるという問題と、その結果、試験トラヒックによってネットワークの品質自体が劣化してしまうという問題があった。
【0008】
このような能動的に測定を行う技術以外に、着目するエンドエンド間トラヒックの流れる箇所において、そこを通過するパケットをキャプチャして解析し、ネットワークの通信状態を把握する技術がある。
【0009】
例えば、非特許文献3における「ACE」(商標)と呼ばれるツールでは、パケットキャプチャデータから、エンド間のレスポンス時間や、その内訳(ネットワーク内での遅延とサーバでの遅延)が分析可能である。また、非特許文献4におけるツール(「tcptrace」)でも往復遅延等を分析することが可能である。
【0010】
しかし、これらの技術は、ある特定のエンドホスト間で、品質の把握やトラブルシューティング的に品質劣化要因を特定するのに適した技術であり、ネットワーク全体でのユーザフロー通信品質を測定するためには、回線を流れるパケットを全てキャプチャして、パケットヘッダ情報の解析、およびフロー情報の解析が必要であり、回線速度が高速になるにつれて全てのパケットをキャプチャして処理することが困難になる。
【0011】
一方、近年、例えば非特許文献5に記載の技術のように、パケットサンプリングを実施することによって、フロー管理に必要とされる処理を軽減する技術が注目されている。
【0012】
例えば、N個に1個のパケットを周期的に参照し、サンプルされたパケットから元のフロー統計情報を推定する技術である。非特許文献6では、パケットサンプリングを用いてリンク帯域の占有率が高いフローを特定する技術を提案している。また、非特許文献7では、フローサイズが大きいフローの統計を精度よく得る技術を提案している。
【0013】
しかし、非特許文献6,7の技術は、サイズの大きい、あるいは帯域の占有率が高いフローを特定し、それらフローを過剰に発生するユーザを迅速に切り分けることを目的としており、品質把握を可能にするものではない。
【0014】
一方、本願の発明者らは非特許文献8において、サンプルパケット情報からTCPのフロースループットを推定する技術を提案している。しかし、この技術では、N個に1個のパケットを抽出するといった通常のパケットサンプリングを行っているため、サイズの大きいフローがサンプルされやすく、サイズの小さいフローが無視されて、サイズの大きいフローのスループットのみを把握可能とするものであった。また、遅延やパケット損失率といった品質の把握は不可能であった。
【先行技術文献】
【非特許文献】
【0015】
【非特許文献1】「pathchar」,[平成21年5月14日検索],インターネット<URL : http://www.caida.org/tools/utilities/others/pathchar/>.
【非特許文献2】的場一峰,阿多信吾,村田正幸,“インターネットにおける計測に基づいたボトルネック特定手法”,電子情報通信学会 テレコミュニケーションマネジメント研究会,pp.65−70,November 2000.
【非特許文献3】「Applicatin Performance Troubleshooting ACEAnlyst」,[平成21年5月14日検索],インターネット<URL : http://www.opnet.com/solutions/application_performance/ace.html>.
【非特許文献4】「tcptrace−Official Homepage tcptrace」,[平成21年5月14日検索],インターネット<URL : http://www.tcptrace.org/>.
【非特許文献5】「IETF Packet Sampling (psamp) Working Group」,[平成21年5月14日検索],インターネット<URL : http://www.ietf.org/html.charters/psamp−charter.html>.
【非特許文献6】森,内田,川原,後藤,“サンプルされたパケットからエレファントフローを特定する手法”,電子情報通信学会技術研究報告 NS2004−13,pp.17−20,2004−04.
【非特許文献7】C.Estan and G.Varghese,”New Directions in Traffic Measurement and Accounting,”ACM SIGCOMM 2002,Aug.2002.
【非特許文献8】R.Kawahara,T.Mori,K.Ishibashi,N.Kamiyama and H.Yoshino,“Packet sampling TCP flow rate estimation and performance degradation detection method”,IEICE Trans. Commun.,Vol.E91−B,No.5,pp.1309−1319,May 2008.
【発明の概要】
【発明が解決しようとする課題】
【0016】
解決しようとする問題点は、(1)従来の能動的な測定によりネットワーク品質を把握する技術では、測定装置コストが増大してしまうと共に、測定用の試験トラヒックによってネットワークの品質自体が劣化してしまう点と、(2)特定のエンドホスト間で品質の把握を行う従来技術では、回線を流れるパケットを全てキャップチャする必要があり高速な回線での適用が困難である点、および、(3)サンプルパケット情報からTCPのフロースループットを推定する従来技術では、サイズの大きいフローのスループットのみを把握可能とするだけであり、また、遅延やパケット損失率といった品質を把握することができない点である。
【0017】
本発明の目的は、これら従来技術の課題を解決し、能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の通信品質(遅延、パケット損失率、スループット)を、効率よく且つ高精度に推定することを可能とすることである。
【課題を解決するための手段】
【0018】
上記目的を達成するため、本発明では、ノードAからノードB方向のパケットを予め定められた間隔でサンプリングし、サンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っているか否かを判別し、立っていれば、このパケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報が、予め記憶装置に記憶されたフロー管理テーブルに登録されているか否かを判別し、登録されていなければ、このパケットのフロー情報を、フロー管理テーブル61に新規登録し、かつ、新規登録したパケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに格納すると共に、ノードAからノードB方向のパケットが到着する度に、当該パケットのフロー情報を読み出し、当該パケットのフロー情報が既にフロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに格納し、また、ノードBからノードA方向のパケットが到着する度に、このパケットのフロー情報を読み出し、このフロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報がフロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに格納する。そして、予め定められた期間毎に、パケット情報蓄積テーブルに格納されたパケットの到着時刻とヘッダ情報を用いて、観測点とノードB間の通信品質を算出する。また、ノードAからノードB方向のパケットに対する処理を、ノードBからノードA方向のパケットに対しても実行すると共に、ノードBからノードA方向のパケットに対する処理を、ノードAからノードB方向のパケットに対して実行し、観測点とノードB間の通信品質の算出と共に、観測点とノードA間の通信品質の算出も行い、その結果を用いて、ノードAとノードB間のリンクを通過するフローの通信品質を算出する。
【発明の効果】
【0019】
本発明によれば、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質(遅延、パケット損失率、スループット)を効率よく且つ高精度に推定することが可能となる。
【図面の簡単な説明】
【0020】
【図1】本発明に係るネットワーク品質算出システムの第1の設置構成例を示すブロック図である。
【図2】本発明に係るネットワーク品質算出システムの第2の設置構成例を示すブロック図である。
【図3】本発明に係るネットワーク品質算出システムによる第1の品質推定結果例を示す説明図である。
【図4】本発明に係るネットワーク品質算出システムの第3の設置構成例を示すブロック図である。
【図5】本発明に係るネットワーク品質算出システムの内部構成例を示すブロック図である。
【図6】図5におけるフロー管理部で保持・管理するフロー管理テーブルの構成例を示す説明図である。
【図7】図5におけるパケット情報蓄積・分析部で保持・管理するパケット蓄積情報の構成例を示す説明図である。
【図8】本発明に係るネットワーク品質算出システムの第4の設置構成例を示すブロック図である。
【図9】本発明に係るネットワーク品質算出システムによる第2の品質推定結果例を示す説明図である。
【図10】図5におけるネットワーク品質算出システムの本発明に係る第1のネットワーク品質算出手順例を示すフローチャートである。
【図11】図5におけるネットワーク品質算出システムの本発明に係る第2のネットワーク品質算出手順例を示すフローチャートである。
【図12】図5におけるネットワーク品質算出システムの本発明に係る第3のネットワーク品質算出手順例を示すフローチャートである。
【発明を実施するための形態】
【0021】
以下、図を用いて本発明を実施するための最良の形態例を説明する。先ず、図4〜図7を用いて、本発明に係るネットワーク品質算出システムの構成と動作について説明する。
【0022】
図4において、フロー品質推定装置43は、本発明に係るネットワーク品質算出システムを実装したコンピュータ装置であり、図5に示すように、プログラムされたコンピュータ処理を実行する手段として、パケットヘッダ解析部43a、フロー管理部43b、パケット情報蓄積・分析部43c、パケットカウント部43d、サンプリング部43eを有している。
【0023】
すなわち、本例のネットワーク品質算出システムを構成するコンピュータ装置(フロー品質推定装置43)は、CPUと主メモリの他に、表示装置、入力装置、外部記憶装置等を具備し、光ディスク駆動装置等を介してCD−ROM等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みCPUで処理することにより、パケットヘッダ解析部43a、フロー管理部43b、パケット情報蓄積・分析部43c、パケットカウント部43d、サンプリング部43eの機能を実行する。このような構成により、本例のネットワーク品質算出システムを構成するコンピュータ装置(フロー品質推定装置43)は、プログラムされたコンピュータ処理によって、図4におけるノードA41とノードB42間に流れるパケットを収集して、ノードA41とノードB42間のリンクの通信品質を求める。
【0024】
すなわち、パケットカウント部43dは、ノードA41からノードB42方向のパケットを予め定められた間隔でサンプリングし、サンプリング部43eは、サンプリング部43eがサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っているか否かを判別し、立っていれば、パケットヘッダ解析部43aは、このパケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報が、図6に示す予め記憶装置に記憶されたフロー管理テーブル61に登録されているか否かを判別し、登録されていなければ、フロー管理部43bを介して、このパケットのフロー情報を、フロー管理テーブル61に新規登録する。
【0025】
パケット情報蓄積・分析部43cは、フロー管理部43bがフロー管理テーブル61に新規登録したパケットの到着時刻とヘッダ情報を、図7に示す、予め記憶装置に記憶されたパケット情報蓄積テーブル71に格納すると共に、図4におけるノードA41からノードB42方向のパケットが到着する度に、当該パケットのフロー情報を読み出し、当該パケットのフロー情報が既にフロー管理テーブル61に登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブル71に格納する。
【0026】
また、パケット情報蓄積・分析部43cは、図4におけるノードB42からノードA41方向のパケットが到着する度に、このパケットのフロー情報を読み出し、このフロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報がフロー管理テーブル61に登録されているか否かを判別し、既に登録されている場合、当該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブル71に格納する。
【0027】
さらに、パケット情報蓄積・分析部43cは、予め定められた期間毎に、パケット情報蓄積テーブル71に格納されたパケットの到着時刻とヘッダ情報を用いて、フロー品質推定装置43(ネットワーク品質算出システム)とノードB42間の通信品質を算出する。
【0028】
また、サンプリング部43eとパケットヘッダ解析部43aおよびフロー管理部43bによる、図4におけるノードA41からノードB42方向のパケットに対する処理を、ノードB42からノードA41方向のパケットに対しても実行すると共に、パケット情報蓄積・分析部43cによる、図4におけるノードB42からノードA41方向のパケットに対する処理を、ノードA41からノードB42方向のパケットに対して実行し、パケット情報蓄積・分析部43cは、フロー品質推定装置43(ネットワーク品質算出システム)とノードB42間の通信品質の算出と共に、フロー品質推定装置43(ネットワーク品質算出システム)とノードA41間の通信品質の算出も行い、結果として、ノードA41とノードB42間のリンクを通過するフローの通信品質を算出する。
【0029】
以下、パケット情報蓄積・分析部43cによる通信品質の算出の詳細を含め、図4〜図7を用いて、本発明に係るネットワーク品質算出技術の実施例について説明する。
【0030】
[実施例1]
図4においては、本発明が適用されるIPネットワークの基本構成の一例を示しており、この図4に示すように、フロー通信品質推定装置43は、ノード(スイッチやルータ)A41,B42間のリンクに挿入される形態で利用される。あるいは、ノードA41,B42において、パケットをポートへミラーして、そのポートの先にフロー通信品質推定装置43を設置する構成としてもよい。
【0031】
図5において、前段ノードA41,B42からパケットが到着すると、パケットヘッダ解析部43aは、ノードA41からノードB42方向のパケットか、ノードB42からノードA41方向のパケットかを判別する。
【0032】
ノードA41からノードB42方向である場合、パケットヘッダ解析部43aは、当該パケットから、「発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)」からなるフロー情報を読み出し、フロー管理部43bが記憶装置に記憶しているフロー管理テーブル61(FT_AtoB)に既にエントリされているフローからのパケットかどうか調べ、もしそうであれば、フロー管理部43bにヘッダ情報を通知する。
【0033】
図6において、このフロー管理テーブル61の例を示す。フロー管理テーブル61では、{srcIP,dstIP,srcPort,dstPort,Protocol}の5つ組をキーとして管理している。
【0034】
その後、パケットヘッダ解析部43aは、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP、srcIP、dstPort、srcPort、Protocol}が、フロー管理部43b内のフロー管理テーブル61(FT_BtoA)にエントリされているか否かを調査し、既にエントリされている場合、フロー管理部43bにヘッダ情報を通知する。
【0035】
また、ノードB42からノードA41方向である場合、パケットヘッダ解析部43aは、当該パケットから、{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を読み出し、フロー管理部43b内に存在するフロー管理テーブル61(FT_BtoA)に既にエントリされているフローからのパケットかどうか調べ、もしそうであれば、フロー管理部43bにヘッダ情報を通知する。
【0036】
その後、パケットヘッダ解析部43aは、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP、srcIP、dstPort、srcPort、Protocol}が、フロー管理部43b内のフロー管理テーブル61(FT_AtoB)に既にエントリされているか否かを調査し、既にエントリされている場合、フロー管理部43bにヘッダ情報を通知する。
【0037】
その後、パケットヘッダ解析部43aは、パケットをパケットカウント部43dに転送する。
【0038】
パケットカウント部43dでは、ノードA41からノードB42方向、ノードB42からノードA41方向の各々を区別して、ノードA41からノードB42方向のパケット到着数C_AtoBと、ノードB42からノードA41方向のパケット到着数C_BtoAをカウントしている。
【0039】
また、パケットカウント部43dは、パケット到着毎にその方向をみて、該当する方向のカウンタをカウントアップする。その後、カウンタ値をN(Nは予め定めたサンプリング周期)で割った余りが「0」と等しいかチェックする。
【0040】
もし、余りが「0」であれば、パケットカウント部43dは、当該パケットをサンプリング部43eに転送し、同時に、当該パケットを後段ノードA41,B42に転送する。
【0041】
余りが「0」でなければ、パケットカウント部43dは、単に、後段ノードA41,B42への当該パケットの転送を行う。
【0042】
あるいは、パケットカウント部43dは、パケット到着毎に「0」から「1」の範囲で乱数を発生させ、その結果が「1/N」以下であれば、当該パケットをパケットヘッダ解析部43aに転送してから後段ノードA41,B42に、当該パケットを転送し、「1/N」以下でなければ、単に、後段ノードA41,B42へ当該パケットを転送するのみ、としてもよい。
【0043】
サンプリング部43eでは、到着パケットのヘッダを読み込み、TCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aへ転送する。
【0044】
パケットヘッダ解析部43aでは、サンプリング部43eからパケットが転送されてきたら、そのパケットの方向に応じたフロー管理テーブルを読み出し(もし、ノードA41からノードB42方向であれば、FT_AtoBを読み出す)、そのパケットの{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}がフロー管理テーブル61にエントリされているか否かを判定し、エントリされていなければ、当該パケットがどのフローからのパケットかを定める5つの属性である{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を、フロー管理部43bを介してフロー管理テーブル61に新規エントリする。
【0045】
フロー管理部43bは、パケットヘッダ解析部43aからパケットを受信すると、当該パケットをパケット情報蓄積・分析部43cへ転送する。
【0046】
パケット情報蓄積・分析部43cにおいては、一定期間収集されたパケットヘッダ情報とパケットが観測されたタイムスタンプ情報を管理している。
【0047】
図7においては、パケット情報蓄積・分析部43cが管理しているパケット情報の例を示しており、パケットヘッダの情報として、srcIP.srcPort,dstIP.dstPort,Protocol,パケットサイズ,シーケンス番号,Ack番号を保持する。
【0048】
このようなパケット蓄積テーブル71においてヘッダ情報(フロー情報)や到着時刻(タイムスタンプ)等の情報が蓄積されたパケットに対して、パケット情報蓄積・分析部43cは、ノードA41からノードB42の方向に流れていたパケットのうち、{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}の5つ組を同じくするパケット群(これをフローiとよぶ)、ならびに、ノードB42からノードA41の方向に流れていたパケットのうち、フローiの通信に該当するパケット群、つまり、ノードA41からノードB42のフローiにおける発着IPアドレスおよび発着ポート番号を入れ替えた{dstIP#i、srcIP#i、dstPort#i、srcPort#i、Protocol#i}の5つ組を同じくするパケット群、を抽出する。尚、このようにして、抽出された双方向のパケット群を双方向フローiとよぶ。
【0049】
また、パケット情報蓄積・分析部43cは、抽出したパケット群を到着順に並び替える。
【0050】
そして、パケット情報蓄積・分析部43cは、ノードA41からノードB42の方向に流れる各パケットkに対して、ノードB42からノードA41の方向の確認応答パケット(Ackパケットk)をみつけ、後者の該Ackパケットkの到着時刻T_AB_ack(k,i)から前者のパケットkの到着時刻T_AB(k,i)を差し引いたRTT_AB(k,i)=T_AB_ack(k,i)−T_AB(k,i)を計算する。
【0051】
例えば、図7に示す例においては、1番目のパケットに対するAckパケットが7番目のパケットとなる。すなわち、7番目のパケットにおけるどのパケットのsrcIP.srcPortとdstIP.dstPortを入れ替えたものが1番目のパケットに対応していることと、1番目のパケットのシーケンス番号1256139556に該パケットサイズ1460byteを加算した値1256141016が7番目のパケットのAck番号と一致していることから、7番目のパケットが1番目のパケットのAckパケットであると判別している。
【0052】
パケット情報蓄積・分析部43cは、このような動作を、双方向フローiの各パケットについて実施し、「RTT_AB_avg(i)=ΣRTT_AB(k,i)/n(i)」 (・・・ここでn(i)は観測されたパケットkとそのackパケットkのペアの数)と、「RTT_AB_min(i)=min{RTT_AB(k,i)}」を計算する。
【0053】
さらに、パケット情報蓄積・分析部43cは、ノードB42からノードA41の方向に流れるパケットk’に対して、ノードA41からノードB42の方向のAckパケットk’をみつけ、上記と同様の手順で、RTT_BA(k’,i)を求め、「RTT_BA_avg(i)=ΣRTT_BA(k’,i)/n’(i)」 (・・・ここでn’(i)は観測されたパケットk’とそのackパケットk’のペアの数)と、「RTT_BA_min(i)=min{RTT_BA(k’,i)}を計算する。
【0054】
そして、パケット情報蓄積・分析部43cは、「RTT_avg(i)=RTT_AB_avg(i)+RTT_BA_avg(i)」と、
「RTT_min(i)=RTT_AB_min(i)+RTT_BA_,min(i)」と、
を計算し、双方向フローiのエンドエンドでの往復伝播遅延時間の平均をRTT_avg(i)、最小値をRTT_min(i)として推定する。
【0055】
尚、フロー管理テーブル61は、一定期間経過したら、クリアする。
【0056】
[実施例2]
実施例1において蓄積した双方向フローi内のパケットについて、パケット情報蓄積・分析部43cは、ノードA41からノードB42方向のパケットk(その到着時刻をT_AB(k,i)とする)に対応する、ノードB42からノードA41方向のAckパケットkをみつけ、かつ、そのAckパケットkに対する、ノードA41からノードB42方向のAckパケットkと、その到着時刻をT_AB_ack(k,i)とする)をみつけたら、「RTT(k,i)=T_AB_ack(k,i)−T_AB(k,i)」とし、双方向フローiのエンドエンドでの往復伝播遅延時間の平均を、「RTT_avg(i)=ΣRTT(k,i)/n’’(i)」 ・・・(n’’(i)は上記パケット−Ack−AckのAckの組の数)により算出し、また、最小値を、「RTT_min(i)=min{RTT(k,i)}」により算出し、そして、最大値を、「RTT_max(i)=max{RTT(k,i)}」により算出する。
【0057】
[実施例3]
また、パケット情報蓄積・分析部43cは、双方向フローiを構成するパケットのうち、ノードA41からノードB42方向の再送パケット数n_ret_AB(i)、および、逆方向の再送パケット数n_ret_BA(i)をカウントし、また、ノードA41からノードB42方向のパケット数n_AB(i)、および、逆方向のパケット数n_BA(i)をカウントし、ノードA41からノードB42方向のパケット再送率R_ret_AB(i)を、「R_ret_AB(i)=n_ret_AB(i)/n_AB(i)」により算出し、また、逆方向のパケット再送率R_ret_BA(i)を、「R_ret_BA(i)=n_ret_BA(i)/n_BA(i)」により算出する。
【0058】
[実施例4]
また、パケット情報蓄積・分析部43cは、予め用意した、再送率R_retとパケット損失率R_lossの関係式R_loss=f(R_ret)を用いて、双方向フローiのエンドエンド間でのパケット損失率R_loss(i)を、「R_loss(i)=1−{1−f(R_ret_AB(i)}{1−f(R_ret_BA(i)}」により算出する。
【0059】
[実施例5]
また、パケット情報蓄積・分析部43cは、双方向フローiにおいて、ノードA41からノードB42の方向へ流れるパケットのバイト数の総和を、ノードA41からノードB42へ流れるパケットのうち、最後に到着したパケットの到着時刻と最初に到着したパケットの到着時刻の差で割ったものを、ノードA41からノードB42方向のスループットTh_AB(i)とし、スループットを算出する。
【0060】
また、パケット情報蓄積・分析部43cは、実施例1または実施例2で得られるRTT_avg(i)を用いて、予め用意したスループットThとパケット損失率R_lossとRTTの関係式Th=g(R_loss,RTT)より、パケット損失率R_loss(i)を算出する。
【0061】
尚、スループットThとパケット損失率R_lossとRTTの関係式Th=g(R_loss,RTT)として、例えば、公知文献である「J.Padhye et al.,“Modeling TCP Reno performance: a simple model and its empirical validation”,IEEE/ACM Tansactions on Netwoking,2000.」に記載の技術に基づく、Th=MSS/{RTT×(R_loss)1/2}を用いる。
【0062】
[実施例6]
また、パケット情報蓄積・分析部43cは、実施例1から実施例5のいずれかの技術で双方向フローiについて品質d(i)を算出し、フローiの{発信元IPアドレスsrcIP#i,着信先IPアドレスdstIP#i}を、予め記憶装置に記憶された地理データベースを用いてsrcIP#iの所属するエリアArea#A,およびdstIP#iの所属するエリアArea#Bへマップし、それを、観測された全ての双方向フローi(i=1〜全フロー数)について実施して、エリアAとエリアBの間の品質d(A,B)を、「d(A,B)=ΣsrcIP#i∈A ∧ dstIP#i∈Bd(i)/|srcIP#i∈A ∧ dstIP#i∈B|」により算出する。
【0063】
尚、|srcIP#i∈A ∧ dstIP#i∈B|は、srcIP#iがエリアAに所属し、かつdstIP#iがエリアBに所属した、フローの数を意味する。
【0064】
[実施例7]
実施例7では、実施例1のように、{srcIP、dstIP、srcPort、dstPort、Protocol}をキーとしたフロー管理テーブル61を、出現した全てのフローを収容できるように作成する代わりに、Bloom filter(BF)を用いる。
【0065】
BFでは、異なるK個のハッシュ関数(それぞれがキー値をサイズbの範囲内でハッシュ値を返す)と、サイズbのビットマップ(初期状態では全てをゼロにリセットされる)を用意する。
【0066】
パケットカウント部43dは、ノードA41からノードB42方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、サンプリング部43eは、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aに通知し、パケットヘッダ解析部43aは、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積・分析部43cに収集させる。
【0067】
そして、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする。
【0068】
また、パケットヘッダ解析部43aは、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、当該パケットをパケット情報蓄積・分析部43cに収集させる。
【0069】
パケットヘッダ解析部43aおよびパケット情報蓄積・分析部43cは、上記ノードA41からノードB42の方向に流れるパケットストリームに対するパケット収集とは別に、ノードB42からノードA41の方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0070】
パケットヘッダ解析部43aは、ノードB42からノードA41方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0071】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断して、パケット情報蓄積・分析部43cに収集させる。
【0072】
尚、パケットヘッダ解析部43aは、一定期間BFによるパケット監視を実施したら、BF内のビットを全て0にクリアする。
【0073】
[実施例8]
実施例7におけるパケット収集処理に加えて、パケットカウント部43dにおいて、ノードB42からノードA41の方向のパケットストリームに対して、N個の到着パケットに対し1個のパケットを抽出し、サンプリング部43eにおいて、当該パケットのヘッダ情報を読み込んで、TCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aに通知し、パケットヘッダ解析部43aにおいて、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積・分析部43cにおいて収集させる。
【0074】
また、パケットヘッダ解析部43aにおいて、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断し、パケット情報蓄積・分析部43cにおいて収集させる。
【0075】
パケットヘッダ解析部43aとパケット情報蓄積・分析部43cにおいて、上記ノードB42からノードA41の方向に流れるパケットストリームに対するパケット収集とは別に、ノードA41からノードB42の方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0076】
パケットヘッダ解析部43aにおいて、ノードA41からノードB42方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}を用いて、BFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、既にエントリされているフローからのパケットと判断して、パパケット情報蓄積・分析部43cにおいて収集させる。
【0077】
[実施例9]
実施例9においては、実施例1から実施例5のように、一定期間パケット収集してから品質を推定する代わりに、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル(初期状態では全てをゼロにリセットされる)を予め記憶装置上に用意する。この時刻テーブルは、パケットの到着時刻を記憶するために用いる。
【0078】
パケットカウント部43dにおいて、ノードA41からノードB42方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、サンプリング部43eは、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、パケットヘッダ解析部43aに通知し、パケットヘッダ解析部43aにおいては、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、対応する位置に現在の時刻を書き込む。
【0079】
また、パケットヘッダ解析部43aは、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、全てゼロ以外の値である場合には、そこに既に現在の時刻を書き込む。
【0080】
さらに、パケットヘッダ解析部43aは、上記ノードA41からノードB42の方向に流れるパケットストリームに対する処理とは別に、ノードB42からノードA41の方向のパケットストリームに対しても以下の手順でパケットを処理する。
【0081】
ノードB42からノードA41方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0082】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、K個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、その中で最も古い時刻を読み出し、現在の時刻からその最も古い時刻を差し引いた値を、そのパケットjの属するフローの、ノードA41からノードB42方向へのパケットに対するAckパケットが返ってくるまでの遅延時間RTTとして推定する。
【0083】
[実施例10]
実施例10においては、BFを2つ用意し(BF1とBF2とする)、最初の測定期間は、いずれのBFにも同じ処理を施し、2番目の測定期間においては、BF1のみをクリアし、ノードA41からノードB42方向のパケットに対する処理(N個に1個サンプルしてSYNがたっていればBFへ入力、またはそれと独立して各パケットをBFへ入力する処理)はBF1に対してのみ実施し、ノードB42からノードA41方向のパケットに対する処理(発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキーをBFへ入力する処理)はBF1,2両方に対して実施する。
【0084】
3番目の測定期間では、BF2をクリアして上記と同様の手順を行い、これを交互に繰り返す。
【0085】
[実施例11]
実施例11においては、実施例1のようにSYNをみてサンプリングする代わりに、パケット到着毎に{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとして、予め用意したハッシュ関数に入力し、ハッシュ値を得、その値をハッシュ値の取りうる値の最大値で割った値が、「1/N」よりも小さければ、そのパケットをサンプリングする。
【0086】
[実施例12]
実施例1では、ノード間に挿入する形で帯域管理装置を実現しているが、そうする代わりに、図8に示すように、品質推定装置81において、IPネットワーク83上の各ノード82a〜82gからサンプルパケット情報を収集し、ネットワーク全体に対して同様の管理を実行する構成としても良い。
【0087】
以上説明したように、本例によれば、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質(遅延、パケット損失率、スループット)を推定することが可能となる。
【0088】
実際に、本例の動作を、実測データを用いて検証した結果を図9の品質推定結果テーブル(図中「品質推定結果」と記載)91に示す。これは、国内トラヒックに対して、サンプリングしなかった場合と、N=10(1/10サンプリング)の場合における、品質推定結果である。これより、サンプル後もサンプル前の品質の傾向を把握できていることが分かる。
【0089】
次に、図1から図3および図10から図12を用いて、図5におけるネットワーク品質算出システム(フロー品質推定装置43)の本発明に係る処理手順例(ネットワーク品質算出方法)を説明する。
【0090】
図1,2においては、エンドホストa1a,21aが接続されたルータA2a,22aと、エンドホストb1b,21bが接続されたルータB2b,22bとの間にある監視点3,23に図5におけるネットワーク品質算出システム(フロー品質推定装置43)が設けられている。
【0091】
図10を用いて、本例の第1の処理手順方法を説明する。本第1の方法では、通信網において、ルータAとルータBをつなぐリンクにおいて、トラヒックをルータAからルータBの方向、およびルータBからルータAの双方向で監視し、ルータAからルータBの方向に流れるパケットストリームにおいて(ステップS1001,S1002)、N個の到着パケットに対し1個のパケットを抽出し(ステップS1003)、抽出したパケットのヘッダ情報を読み込んで、TCPの通信開始を表すSYNフラグが立っており(ステップS1004)、かつ、予め記憶装置に記憶されたフロー管理テーブル(以下、フロー管理テーブルFT_AtoBとよぶ)に該フローの情報がエントリされていなければ(ステップS1005)、該パケットがどのフローからのパケットかを定める5つの属性である{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を、フロー管理テーブルFT_AtoBに新規エントリする(ステップS1006)。同時に、該パケットの到着時刻および該パケットヘッダ情報を、予め記憶装置に記憶されたパケット情報蓄積テーブルに収集する(ステップS1007)。
【0092】
また、N個に1個のパケット抽出とは独立に(ステップS1003)、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、この5つ組のキーが既にフロー管理テーブルFT_AtoBにエントリされているか否かを調査し(ステップS1008)、既にエントリされている場合、該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1009)。
【0093】
上記ルータAからルータBの方向に流れるパケットストリームに対するパケット収集とは別に、ルータBからルータAの方向のパケットストリームに対しても、以下の手順でパケットを収集する。
【0094】
ルータBからルータA方向のパケットが到着したら(ステップS1002)、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出し、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}が(ステップS1010)、フロー管理テーブルFT_AtoBにエントリされているか否かを調査し(ステップS1011)、既にエントリされている場合、該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1012)。
【0095】
これを一定期間継続し(ステップS1013)、パケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を推定する(ステップS1014)。
【0096】
ここで、単純なN個に1個のパケットサンプリングではなく、SYNの有無をみてサンプリングする理由を述べる。
【0097】
単純な1/N個のサンプリングでは、たくさんのパケットを送出しているフローからのパケットがサンプルされやすくなるが、SYNパケットベースのサンプリングであれば、SYNパケット(TCP通信の開始を表す)は、通常、どのフローも一つであるため、フローの大きさ(パケット数)に依らず同じ確率でサンプリングすることが可能となるからである。
【0098】
こうすることによって、特定のフローに偏ることなく、ネットワーク全体を流れるフローの品質を満遍なく把握可能としている。
【0099】
また、エンドエンド間の往復遅延の推定を可能とするために、ルータAからルータB方向だけでなく、ルータBからルータA方向のパケットも収集している。つまり、図1に示すように、両方向のパケットを収集して、監視点3とエンドホストb1b間の品質(往復遅延)が把握可能となる。詳細な遅延推定手順は、以下の第3の方法以降で説明する。
【0100】
第2の方法においては、第1の方法と同様の手順を、ルータBからルータAの方向のパケットストリームに対しても実施する。
【0101】
具体的には、図11に示すように、ルータBからルータAの方向のパケットストリームに対して(ステップS1101,S1102)、N個の到着パケットに対し1個のパケットを抽出し(ステップS1103)、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っており(ステップS1104)、かつ、予め用意したフロー管理テーブル(以下、フロー管理テーブルFT_BtoAとよぶ)に該フローの情報がエントリされていなければ(ステップS1105)、該パケットの{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}をフロー管理テーブルFT_BtoAに新規エントリする(ステップS1106)。同時に、該パケットの到着時刻および該パケットのヘッダを、予め用意したパケット情報蓄積テーブルに収集する(ステップS1107)。
【0102】
N個に1個のパケット抽出とは独立に(ステップS1103)、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、この5つ組のキーが既にフロー管理テーブルFT_BtoAにエントリされているか否かを調査し(ステップS1108)、既にエントリされている場合、該パケットの到着時刻とヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1109)。
【0103】
上記ルータBからルータAの方向に流れるパケットストリームに対するパケット収集とは別に(ステップS1102)、ルータAからルータBの方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0104】
ルータAからルータB方向のパケットが到着したら(ステップS1102)、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出し、発着IPアドレスおよび発着ポート番号を入れ替えて(ステップS1110)構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}がフロー管理テーブルFT_BtoAにエントリされているか否かを調査し(ステップS1111)、既にエントリされている場合、該パケットヘッダ情報をパケット情報蓄積テーブルに収集する(ステップS1112)。
【0105】
これを一定期間継続し(ステップS1113)、第1の方法の手順でパケット情報蓄積テーブルに収集されたパケットヘッダ情報に加え、本第2の方法の手順でパケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を推定する。
【0106】
このようにルータBからルータA方向についてもパケット収集することにより、図2に示すように、監視点とエンドホストa21a(ルータA22a側のホスト)との品質が把握可能となる。これと、第1の方法での品質(監視点3,23とエンドホストb1b,21b間)を合わせて、エンドホストa21a−b21b間の品質を把握可能としている。
【0107】
本例の第3の方法においては、図12に示すように、第1の方法または第2の方法で収集されたパケットヘッダに対して、ルータAからルータBの方向に流れていたパケットのうち、{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}の5つ組を同じくするパケット群(これをフローiとよぶ)、ならびに、ルータBからルータAの方向に流れていたパケットのうち上記フローiの通信に該当するパケット群、つまり、ルータAからルータBのフローiにおける発着IPアドレスおよび発着ポート番号を入れ替えた{dstIP#i、srcIP#i、dstPort#i、srcPort#i、Protocol#i}の5つ組を同じくするパケット群、を抽出する(ステップS1201)。抽出した双方向のパケット群を双方向フローiとよぶ。
【0108】
これらパケット群を到着順に並び替え(ステップS1202)、ルータAからルータBの方向に流れる各パケットkに対して(ステップS1203のY)、ルータBからルータAの方向の確認応答パケット(Ackパケットk)をみつけ(ステップS1204)、後者のAckパケットkの到着時刻T_AB_ack(k,i)から前者のパケットkの到着時刻T_AB(k,i)を差し引いたRTT_AB(k,i)=T_AB_ack(k,i)−T_AB(k,i)を計算する(ステップS1205)。
【0109】
これを双方向フローiの各パケットについて実施し(ステップS1206)、「RTT_AB_avg(i)=ΣRTT_AB(k,i)/n(i)」 (・・・ここでn(i)は観測されたパケットkとそのackパケットkのペアの数)による平均値RTT_AB_avg(i)と、「RTT_AB_min(i)=min{RTT_AB(k,i)}」による最小値RTT_AB_min(i)を計算する(ステップS1207)。これが図1における「監視点−エンドホストb(ルータB側)」の品質に相当する。
【0110】
次に、ルータBからルータAの方向に流れるパケットk’に対して(ステップS1203のN)、ルータAからルータBの方向のAckパケットk’をみつけ(ステップS1208)、上記と同様の手順で、平均値RTT_BA_avg(i)と最小値RTT_BA_min(i)を求め(ステップS1209〜S1211)、ステップS1207とステップS1211で求めたそれぞれの平均値と最小値をそれぞれ加算して、双方向フローiのエンドエンドの往復伝播遅延時間の平均と最小値を求める。
【0111】
すなわち、ステップS1211において、「RTT_BA_avg(i)=ΣRTT_BA(k’,i)/n’(i)」 (…ここでn’(i)は観測されたパケットk’とそのackパケットk’のペアの数)と、「RTT_BA_min(i)=min{RTT_BA(k’,i)}」を計算する。これが図2における「監視点43−エンドホストb21b(ルータB22b側)」の品質に相当する。
【0112】
そして、ステップS1212において、「RTT_avg(i)=RTT_AB_avg(i)+RTT_BA_avg(i)」、および、「RTT_min(i)=RTT_AB_min(i)+RTT_BA_,min(i)」、を計算し、双方向フローiのエンドエンドでの往復伝播遅延時間の平均をRTT_avg(i)、最小値をRTT_min(i)として求める。
【0113】
本例の第4の方法においては、第3の方法における双方向フローi内のパケットについて、ルータAからルータB方向のパケットk(その到着時刻をT_AB(k,i)とする)に対応するルータBからルータA方向のAckパケットkをみつけ、かつそのAckパケットkに対するルータAからルータB方向のAckパケットkその到着時刻をT_AB_ack(k,i)とする)をみつけたら、「RTT(k,i)=T_AB_ack(k,i)−T_AB(k,i)」とし、双方向フローiのエンドエンドでの往復伝播遅延時間の平均を、「RTT_avg(i)=ΣRTT(k,i)/n’’(i)」 (…尚、n’’(i)は上記パケット−Ack−AckのAckの組の数)、により推定し、最小値を、「RTT_min(i)=min{RTT(k,i)}」、により推定し、最大値を、「RTT_max(i)=max{RTT(k,i)}」により推定する。
【0114】
本例の第5の方法においては、双方向フローiを構成するパケットのうち、ルータAからルータB方向の再送パケット数n_ret_AB(i)および逆方向の再送パケット数n_ret_BA(i)をカウントし、また、ルータAからルータB方向のパケット数n_AB(i)および逆方向のパケット数n_BA(i)をカウントし、ルータAからルータB方向および逆方向のパケット再送率を、「R_ret_AB(i)=n_ret_AB(i)/n_AB(i)」および「R_ret_BA(i)=n_ret_BA(i)/n_BA(i)」により算出する。
【0115】
本例の第6の方法においては、予め用意した、再送率R_retとパケット損失率R_lossの関係式R_loss=f×(R_ret)を用いて、双方向フローiのエンドエンド間でのパケット損失率R_loss(i)を、「R_loss(i)=1−{1−f×(R_ret_AB(i)}×{1−f×(R_ret_BA(i)})により算出する。
【0116】
TCPでは、パケット損失が発生するとパケットを再送するため、一般に再送数とパケット損失率は相関がある。もっとも単純な例としては、再送率とパケット損失率を近似的に等しいとすることが考えられる。
【0117】
尚、エンドエンド間でのパケット損失率を、「R_loss(i)=1−{1−f×(R_ret_AB(i)}×{1−f×(R_ret_BA(i)})で推定している理由を述べる。
【0118】
f×(R_ret_AB(i))は、図1での監視点−エンドホストb間のパケット損失率となり、f×(R_ret_BA(i))は、図2での監視点−エンドホストa間のパケット損失率となる。
【0119】
前者と後者のパケット損失が独立に発生すると仮定すれば、エンドエンドでのパケット損失率は、「1−{1−f×(R_ret_AB(i)}×{1−f×(R_ret_BA(i)}」となる。
【0120】
本例の第7の方法においては、双方向フローiにおいて、ルータAからルータBの方向へ流れるパケットのバイト数の総和を、ルータAからルータBへ流れるパケットのうち、最後に到着したパケットの到着時刻と最初に到着したパケットの到着時刻の差で割ったものを、ルータAからルータB方向のスループットTh_AB(i)とし、スループットを求める。
【0121】
また、第3の方法または第4の方法で得られるRTT_avg(i)を用いて、予め用意したスループットThとパケット損失率R_lossとRTTの関係式「Th=g×(R_loss,RTT)」より、パケット損失率R_loss(i)を算出する。尚、関数g()については、次の第8の方法に示す。
【0122】
本例の第8の方法においては、第7の方法におけるスループットThとパケット損失率R_lossとRTTの関係式「Th=g×(R_loss,RTT)」として、「Th=MSS/{RTT×(R_loss)1/2}を用いる。これは、上述の公知文献(「J.Padhye et al.,“Modeling TCP Reno performance: a simple model and its empirical validation”,IEEE/ACM Tansactions on Netwoking,2000.」)に記載の技術に基づく。
【0123】
本例の第9の方法においては、第3の方法から第8の方法のいずれかの方法で双方向フローiについて品質d(i)を推定し、フローiの{発信元IPアドレスsrcIP#i,着信先IPアドレスdstIP#i}を、予め用意した地理データベースを用いて、srcIP#iの所属するエリアArea#A、および、dstIP#iの所属するエリアArea#Bへマップし、それを、観測された全ての双方向フローi(i=1〜全フロー数)について実施して、エリアAとエリアBの間の品質d(A,B)を、「d(A,B)=ΣsrcIP#i∈A ∧ dstIP#i∈Bd(i)/|srcIP#i∈A ∧ dstIP#i∈B|」により求める。
【0124】
尚、上述したように、|srcIP#i∈A ∧ dstIP#i∈B|は、srcIP#iがエリアAに所属し、かつ、dstIP#iがエリアBに所属した、フローの数を意味する。
【0125】
こうすることにより、例えば、県別の品質がどのようになっているかを把握可能である。例として、ある測定点でのトラヒックデータを対象に分析した結果を図3に示す。
【0126】
本例の第10の方法においては、第1の方法または第2の方法のように、{srcIP、dstIP、srcPort、dstPort、Protocol}をキーとしたフローテーブルを、出現した全てのフローを収容できるように作成する代わりに、BloomFilter(BF)を用いる。
【0127】
BFでは、異なるK個のハッシュ関数(それぞれがキー値をサイズbの範囲内でハッシュ値を返す)と、サイズbのビットマップ(初期状態では全てをゼロにリセットされる)を用意する。
【0128】
ルータAからルータB方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積テーブルに収集する。
【0129】
そして、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする。N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断してパケット情報蓄積テーブルに収集する。
【0130】
上記ルータAからルータBの方向に流れるパケットストリームに対するパケット収集とは別に、ルータBからルータAの方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0131】
ルータBからルータA方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0132】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、パケット情報蓄積テーブルに収集する。
【0133】
これを一定期間継続し、パケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を求める。
【0134】
上記のように、BFを使うことにより、全てのサンプルフローを管理することなく、必要なパケット収集を可能としている。
【0135】
本例の第11の方法においては、第10の方法のパケット収集処理に加えて、ルータBからルータAの方向のパケットストリームに対して、N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットのうち1つ以上がゼロである場合には、新規フローからのパケットだと判断し、そのパケットをパケット情報蓄積テーブルに収集する。
【0136】
また、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断してパケット情報蓄積テーブルに収集する。
【0137】
さらに、上記ルータBからルータAの方向に流れるパケットストリームに対するパケット収集とは別に、ルータAからルータBの方向のパケットストリームに対しても以下の手順でパケットを収集する。
【0138】
ルータAからルータB方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0139】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}を用いて、BFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には既にエントリされているフローからのパケットと判断して、パケット情報蓄積テーブルに収集する。
【0140】
これを一定期間継続し、パケット情報蓄積テーブルに収集されたパケットヘッダ情報を分析して、測定対象リンクを通過するフローの通信品質を推定する。
【0141】
本例の第12の方法においては、第3の方法から第8の方法のように、一定期間パケット収集してから品質を推定する代わりに、K個のハッシュ関数およびb個の時刻情報をエントリする時刻テーブル(初期状態では全てをゼロにリセットされる)を記憶装置上に用意する。この時刻テーブルは、パケットの到着時刻を記憶するために用いる。
【0142】
そして、ルータAからルータB方向のパケットに対して、N個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでTCPの通信開始を表すSYNフラグが立っていれば、そのパケットの{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットだと判断し、対応する位置に現在の時刻を書き込む。
【0143】
さらに、N個に1個のパケット抽出とは独立に、パケット到着毎に該パケットiの{srcIP#i、dstIP#i、srcPort#i、dstPort#i、Protocol#i}を読み出し、これをキーとしてBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、全てゼロ以外の値である場合には、そこに既に現在の時刻を書き込む。
【0144】
また、上記ルータAからルータBの方向に流れるパケットストリームに対する処理とは別に、ルータBからルータAの方向のパケットストリームに対しても以下の手順でパケットを処理する。
【0145】
ルータBからルータA方向のパケットが到着したら、そのパケットjの{srcIP#j、dstIP#j、srcPort#j、dstPort#j、Protocol#j}を読み出す。
【0146】
そして、発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキー{dstIP#j、srcIP#j、dstPort#j、srcPort#j、Protocol#j}をBFのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、K個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、その中で最も古い時刻を読み出し、現在の時刻からその最も古い時刻を差し引いた値を、そのパケットjの属するフローの、ルータAからルータB方向へのパケットに対するAckパケットが返ってくるまでの遅延時間RTTとして求める。
【0147】
通常のBFでは、ビットマップを用意するのに対し、ここでは、ビット情報ではなく、パケット到着時刻情報を管理するようにすることにより、パケットを一旦蓄積することなく、オンラインでRTTの推定を可能としている。
【0148】
本例の第13の方法においては、第10の方法から第12の方法のようにBloom Filter(BF)を用いる場合に、一定期間BFによるパケット監視を実施したら、BF内のビットを全て0にクリアする。
【0149】
BFは、定期的にクリアしないで長時間継続的に利用すると、全てのビットが1で埋まってしまい、適切な新規フロー判定が困難になるため、ここでは一定周期ごとにクリアする。
【0150】
本例の第14の方法においては、BFを2つ用意し(BF1とBF2とする)、最初の測定期間は、いずれのBFにも同じ処理を施し、2番目の測定期間においては、BF1のみをクリアし、ノードA41からノードB42方向のパケットに対する処理(N個に1個サンプルしてSYNがたっていればBFへ入力、またはそれと独立して各パケットをBFへ入力する処理)はBF1に対してのみ実施し、ルータBからルータA方向のパケットに対する処理(発着IPアドレスおよび発着ポート番号を入れ替えて構成されるキーをBFへ入力する処理)はBF1,2両方に対して実施する。
【0151】
そして、3番目の測定期間では、BF2をクリアして上記と同様の手順を行い、これを交互に繰り返す。
【0152】
このように、BFを2つ用意する理由を述べる。フローによっては、RTTが非常に大きいものもあるため、ルータAからルータB方向のパケットを観測してから、そのAckパケットをルータBからルータA方向で検出するのに時間を要する場合がある。
【0153】
対処法としては、BFクリアの周期を長めに設定することが考えられるが、第13の方法でも述べたように、測定周期が長くなると、BFが正しく新規フローの検出をできない可能性がある。
【0154】
そこで、BFを2つ用意して、ルータAからルータB方向の新規フロー検出についてはBF1と2を交互に使うことにより適切に検出し、ルータBからルータA方向のAckパケットについては、BF1,2の両方に対して入力し、いずれかのBFに該当するエントリがあるかどうかをみることで、RTTの長いAckに対しても対応できるようにしている。
【0155】
本例の第15の方法においては、第1の方法または第2の方法のように、SYNをみてサンプリングする代わりに、パケット到着毎に{srcIP、dstIP、srcPort、dstPort、Protocol}を読み出し、それをキーとして、予め用意したハッシュ関数に入力し、ハッシュ値を得、その値をハッシュ値の取りうる値の最大値で割った値が、1/Nよりも小さければ、そのパケットをサンプリングする。
【0156】
第1の方法で述べたように、SYNをみてサンプリングする理由は、特定のフローに偏ることなく、ネットワーク全体を流れるフローの品質を満遍なく把握するためであった。この同じ目的を達成する別の方法をここでは述べている。すなわち、フローを特定する{srcIP、dstIP、srcPort、dstPort、Protocol}をキーにしてハッシュにかけてサンプリングすることで、フロー単位での均等なサンプリングを行うことが可能となっている。
【0157】
以上、図1〜図12を用いて説明したように、本例のネットワーク品質算出技術では、ネットワークへの余分な負荷を加えてしまう能動的な測定を行わず、かつ、ネットワークの全パケットキャプチャを行うことなく、ネットワーク全体の品質(遅延、パケット損失率、スループット)を推定することが可能である。
【0158】
尚、本発明は、図1〜図12を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例のネットワーク品質算出システムを実装するコンピュータ装置における、本発明に係る処理を実行するためのプログラムのインストール技術に関しても、記録媒体として、FD(Flexible Disk)等を用いることでも良い。また、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【符号の説明】
【0159】
1a,21a:エンドホストa、1b,21b:エンドホストb、2a,22a:ルータA、2b,22b:ルータB、3,23:監視点、41:ノードA、42:ノードB、43:フロー品質推定装置(ネットワーク品質算出システム)、43a:パケットヘッダ解析部、43b:フロー管理部、43c:パケット情報蓄積・分析部、43d:パケットカウント部、43e:サンプリング部、61:フロー管理テーブル、71:パケット情報蓄積テーブル、81:品質推定装置、82a〜82g:ノード(スイッチ、ルータ)、83:IPネットワーク、91:品質推定結果テーブル。
【特許請求の範囲】
【請求項1】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
第1のノードから第2のノード方向のパケットを予め定められた間隔でサンプリングする第1の手段と、
該第1の手段がサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っており、かつ、該パケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報が、予め記憶装置に記憶されたフロー管理テーブルに登録されていなければ、該パケットの上記フロー情報を、上記フロー管理テーブルに新規登録する第2の手段と、
上記新規登録したパケットの到着時刻および該パケットのヘッダ情報を、予め記憶装置に記憶されたパケット情報蓄積テーブルに格納すると共に、上記第1のノードから上記第2のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該パケットの上記フロー情報が既に上記フロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに格納する第3の手段と、
上記第2のノードから上記第1のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が上記フロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに格納する第4の手段と、
予め定められた期間毎に、上記パケット情報蓄積テーブルに格納されたパケットの到着時刻とヘッダ情報を用いて、ネットワーク品質算出システムと上記第2のノード間の通信品質を算出する分析手段と
を有することを特徴とするネットワーク品質算出システム。
【請求項2】
請求項1に記載のネットワーク品質算出システムであって、
上記第1の手段と上記第2の手段および上記第3の手段による処理を、上記第2のノードから上記第1のノード方向のパケットに対して実行し、
上記第4の手段による処理を、上記第1のノードから上記第2のノード方向のパケットに対して実行し、
上記分析手段により、ネットワーク品質算出システムと上記第1のノード間の通信品質を算出して、上記第1のノードと上記第2のノード間のリンクを通過するフローの通信品質を算出することを特徴とするネットワーク品質算出システム。
【請求項3】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
第1のノードから第2のノード方向のパケットを予め定められた間隔でサンプリングする第1の手段と、
該第1の手段がサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っていれば、該パケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報を読み出し、該フロー情報をキーとしてBloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットの内1つ以上がゼロである場合には、当該パケットの到着時刻とヘッダ情報を、予め記憶装置に記憶されたパケット情報蓄積テーブルに新規登録すると共に、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする第2の手段と、
上記第1のノードから上記第2のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、当該パケットのフロー情報が上記パケット情報蓄積テーブルに既に登録されていると判断して当該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに登録する第3の手段と、
上記第2のノードから上記第1のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、当該パケットのフロー情報が上記パケット情報蓄積テーブルに既に登録されていると判断して当該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに登録する第4の手段と、
予め定められた期間毎に、上記パケット情報蓄積テーブルに格納されたパケットの到着時刻とヘッダ情報を用いて、ネットワーク品質算出システムと上記第2のノード間の通信品質を算出する分析手段と
を有することを特徴とするネットワーク品質算出システム。
【請求項4】
請求項3に記載のネットワーク品質算出システムであって、
上記第1の手段と上記第2の手段および上記第3の手段による処理を、上記第2のノードから上記第1のノード方向のパケットに対して実行し、
上記第4の手段による処理を、上記第1のノードから上記第2のノード方向のパケットに対して実行し、
上記分析手段により、ネットワーク品質算出システムと上記第1のノード間の通信品質を算出して、上記第1のノードと上記第2のノード間のリンクを通過するフローの通信品質を算出することを特徴とするネットワーク品質算出システム。
【請求項5】
請求項1から請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記パケット情報蓄積テーブルに格納されたフロー情報が同じ、ならびに、発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が同じパケットを抽出し、
抽出したパケットを到着順に並び替え、
上記第1のノードから上記第2のノード方向の各パケットkに対応した上記第2のノードから上記第1ノード方向の各確認応答パケットkを特定して、各確認応答パケットkの到着時刻と各パケットkの到着時刻との差を求め、求めた差の平均値と最小値を、ネットワーク品質算出システムと上記第2のノード間の通信品質として算出する
ことを特徴とするネットワーク品質算出システム。
【請求項6】
請求項2もしくは請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記パケット情報蓄積テーブルに格納されたフロー情報が同じ、ならびに、発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が同じパケットを抽出し、
抽出したパケットを到着順に並び替え、
上記第1のノードから上記第2のノード方向の各パケットkに対応した上記第2のノードから上記第1ノード方向の各確認応答パケットkを特定して、各確認応答パケットkの到着時刻と各パケットkの到着時刻との差を求め、求めた差の平均値RTT_AB_avgと最小値RTT_AB_minを、ネットワーク品質算出システムと上記第2のノード間の通信品質として算出すると共に、
上記第2のノードから上記第1ノード方向の各パケットk’に対応した上記第1のノードから上記第2のノード方向の各確認応答パケットk’を特定して、各確認応答パケットk’の到着時刻と各パケットk’の到着時刻との差を求め、求めた差の平均値RTT_BA_avgと最小値RTT_BA_minを、ネットワーク品質算出システムと上記第1のノード間の通信品質として算出し、
かつ、
上記平均値RTT_AB_avgと上記平均値RTT_BA_avgとを加算して、上記第1のノードと上記第2のノード間での双方向フローの往復伝播遅延時間の平均値RTT_avgを求めると共に、
上記最小値RTT_AB_minと上記最小値RTT_BA_minとを加算して、上記第1のノードと上記第2のノード間での双方向フローの往復伝播遅延時間の最小値RTT_minを求める
ことを特徴とするネットワーク品質算出システム。
【請求項7】
請求項2もしくは請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記パケット情報蓄積テーブルに格納されたフロー情報が同じ、ならびに、発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が同じパケットを抽出し、
抽出した各パケットを到着順に並び替え、
上記第1のノードから上記第2のノード方向の各パケットkに対応した上記第2のノードから上記第1ノード方向の各確認応答パケットkを特定すると共に、
特定した各確認応答パケットkに対応した上記第1のノードから上記第2のノード方向の各確認応答パケットk*を特定し、
各確認応答パケットk*の到着時刻と各パケットkの到着時刻との差を求め、求めた差の平均値RTT_avgと最小値RTT_minおよび最大値RTT_maxを、上記第1のノードと上記第2のノード間での双方向フローの往復伝播遅延時間の平均値と最小値および最大値として算出する
ことを特徴とするネットワーク品質算出システム。
【請求項8】
請求項1から請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記第1のノードから上記第2のノード方向の再送パケットの数n_ret_ABと上記第2のノードから上記第1ノード方向の再送パケットの数n_ret_BAとを計数すると共に、
上記第1のノードから上記第2のノード方向のパケットの数n_ABと上記第2のノードから上記第1ノード方向の再送パケットの数n_BAとを計数し、
上記第1のノードから上記第2のノード方向のパケットの再送率を、n_ret_AB÷n_ABにより算出すると共に、
上記第2のノードから上記第1ノード方向のパケットの再送率を、n_ret_BA÷n_BAにより算出する
ことを特徴とするネットワーク品質算出システム。
【請求項9】
請求項8に記載のネットワーク品質算出システムであって、
上記分析手段は、
予め定められた上記再送率とパケット損失率の関係式(パケット損失率=f×(再送率))を用いて、上記第1のノードと上記第2のノード間でのパケット損失率R_lossを、
「R_loss=1−{1−f×(R_ret_AB)}×{1−f×(R_ret_BA)}」により算出する
ことを特徴とするネットワーク品質算出システム。
【請求項10】
請求項1から請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記第1のノードから上記第2のノード方向のパケットのバイト数の総和を算出すると共に、
上記第1のノードから上記第2のノード方向の最後に到着したパケットの到着時刻と、最初に到着したパケットの到着時刻との差を算出し、
上記バイト数の総和を上記到着時刻の差で除した値を、上記第1のノードから上記第2のノード方向のスループットTh_ABとして算出する
ことを特徴とするネットワーク品質算出システム。
【請求項11】
請求項6もしくは請求項7のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記第1のノードから上記第2のノード方向のパケットのバイト数の総和を算出すると共に、
上記第1のノードから上記第2のノード方向の最後に到着したパケットの到着時刻と、最初に到着したパケットの到着時刻との差を算出し、
上記バイト数の総和を上記到着時刻の差で除した値を、上記第1のノードから上記第2のノード方向のスループットTh_ABとして算出し、
上記第2のノードから上記第1ノード方向のパケットのバイト数の総和を算出すると共に、
上記第2のノードから上記第1ノード方向の最後に到着したパケットの到着時刻と、最初に到着したパケットの到着時刻との差を算出し、
上記バイト数の総和を上記到着時刻の差で除した値を、上記第2のノードから上記第1のノード方向のスループットTh_BAとして算出し、
上記第1のノードと上記第2のノード間のスループットThを、「Th=(Th_BA+Th_AB)÷2」により算出すると共に、
予め定められたスループットThとパケット損失率R_lossおよび上記平均値RTT_avgの関係式である「Th=g×(R_loss,RTT_avg)」により、
上記第1のノードから上記第2のノード間のパケット損失率R_lossを算出する
ことを特徴とするネットワーク品質算出システム。
【請求項12】
請求項11に記載のネットワーク品質算出システムであって、
上記分析手段は、
上記関係式「Th=g×(R_loss,RTT_avg)」として、
「Th=MSS÷{RTT×(R_loss)1/2}を用いる
ことを特徴とするネットワーク品質算出システム。
【請求項13】
請求項1から請求項12のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
予め記憶装置に格納された地理データベースを用いて、各パケットの上記フロー情報を構成する発信元IPアドレスsrcIPの所属するエリアA、および、着信先IPアドレスdstIPの所属するエリアBをマップし、
発信元IPアドレスsrcIPがエリアAに所属し、かつ、着信先IPアドレスdstIPがエリアBに所属したフローの数(srcIP∈A ∧ dstIP∈B|)を用いて、
エリアAとエリアBの間の通信品質d(A,B)を、
「d(A,B)=ΣsrcIP∈A ∧ dstIP∈Bd(i)÷|srcIP∈A ∧ dstIP∈B|」により算出する
ことを特徴とするネットワーク品質算出システム。
【請求項14】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
第1のノードから第2のノード方向のパケットを予め定められた間隔でサンプリングする第1の手段と、
該第1の手段がサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っていれば、該パケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報を読み出し、該フロー情報をキーとしてBloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、予め記憶装置に記憶された、K個のハッシュ関数およびb個の時刻情報を登録する時刻テーブル内において、K個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットと判断して、対応する位置に現在の時刻を書き込む第2の手段と、
上記第1のノードから上記第2のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、上記時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、全てゼロ以外の値である場合には、当該位置に現在の時刻を書き込む第3の手段と、
上記第2のノードから上記第1のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、当該位置における最も古い時刻を読み出し、該最も古い時刻を現在の時刻から差し引いた値を、当該パケットの属するフローの、上記第1のノードから上記第2のノード方向へのパケットに対するAckパケットが帰ってくるまでの往復伝播遅延時間RTTとして算出する分析手段と
を有することを特徴とするネットワーク品質算出システム。
【請求項15】
請求項3,4もしくは請求項14のいずれかに記載のネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記分析手段による通信品質の算出を実行するたびに、上記BloomFilter内のビットを全て0にクリアする手段
を有することを特徴とするネットワーク品質算出システム。
【請求項16】
請求項3もしくは請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記BloomFilterは第1,第2の2つのBloomFilterからなり、
上記分析手段により最初に通信品質の算出を実行するまでの期間は、上記第2,3,4の手段は、上記第1,第2のBloomFilterの双方を用いて入力し、
上記分析手段により2番目を含む偶数番目に通信品質の算出を実行するまでの期間は、上記第2,第3の手段は、上記第1のBloomFilter内のビットを全て0にクリアした後、上記第1のノードから上記第2のノード方向のパケットに対する処理を、上記第1のBloomFilterに対してのみ実行すると共に、上記第4の手段は、上記第2のノードから上記第1のノード方向のパケットに対する処理を、上記第1,第2のBloomFilterの双方に対して実行し、
上記分析手段により3番目を含む奇数番目に通信品質の算出を実行するまでの期間は、上記第2,第3の手段は、上記第2のBloomFilter内のビットを全て0にクリアした後、上記第1のノードから上記第2のノード方向のパケットに対する処理を、上記第2のBloomFilterに対してのみ実行すると共に、上記第4の手段は、上記第2のノードから上記第1のノード方向のパケットに対する処理を、上記第1,第2のBloomFilterの双方に対して実行する
ことを特徴とするネットワーク品質算出システム。
【請求項17】
請求項1から請求項16のいずれかに記載のネットワーク品質算出システムであって、
上記第1の手段は、N個の到着パケットに対して1個のパケットをサンプリングし、
上記第2の手段は、
上記SYNフラグが立っているパケットを処理の対象とする代わりに、
サンプリングされたパケットの上記フロー情報を読み出し、該フロー情報をキーとして、予め記憶装置に記憶されたハッシュ関数に入力して、ハッシュ値を得、該ハッシュ値を、ハッシュ値の取りうる値の最大値で割った値が、1/Nよりも小さければ、当該パケットを処理の対象とする
ことを特徴とするネットワーク品質算出システム。
【請求項18】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるコンピュータ装置によるネットワーク品質算出方法であって、
コンピュータ装置のプログラムされたコンピュータ処理実行手順として、
請求項1から請求項17のいずれかに記載のネットワーク品質算出システムにおける各手順を含むことを特徴とするネットワーク品質算出方法。
【請求項19】
コンピュータを、請求項1から請求項17のいずれかに記載のネットワーク品質算出システムにおける各手段として機能させるためのプログラム。
【請求項1】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
第1のノードから第2のノード方向のパケットを予め定められた間隔でサンプリングする第1の手段と、
該第1の手段がサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っており、かつ、該パケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報が、予め記憶装置に記憶されたフロー管理テーブルに登録されていなければ、該パケットの上記フロー情報を、上記フロー管理テーブルに新規登録する第2の手段と、
上記新規登録したパケットの到着時刻および該パケットのヘッダ情報を、予め記憶装置に記憶されたパケット情報蓄積テーブルに格納すると共に、上記第1のノードから上記第2のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該パケットの上記フロー情報が既に上記フロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに格納する第3の手段と、
上記第2のノードから上記第1のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が上記フロー管理テーブルに登録されているか否かを判別し、既に登録されている場合、該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに格納する第4の手段と、
予め定められた期間毎に、上記パケット情報蓄積テーブルに格納されたパケットの到着時刻とヘッダ情報を用いて、ネットワーク品質算出システムと上記第2のノード間の通信品質を算出する分析手段と
を有することを特徴とするネットワーク品質算出システム。
【請求項2】
請求項1に記載のネットワーク品質算出システムであって、
上記第1の手段と上記第2の手段および上記第3の手段による処理を、上記第2のノードから上記第1のノード方向のパケットに対して実行し、
上記第4の手段による処理を、上記第1のノードから上記第2のノード方向のパケットに対して実行し、
上記分析手段により、ネットワーク品質算出システムと上記第1のノード間の通信品質を算出して、上記第1のノードと上記第2のノード間のリンクを通過するフローの通信品質を算出することを特徴とするネットワーク品質算出システム。
【請求項3】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
第1のノードから第2のノード方向のパケットを予め定められた間隔でサンプリングする第1の手段と、
該第1の手段がサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っていれば、該パケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報を読み出し、該フロー情報をキーとしてBloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットの内1つ以上がゼロである場合には、当該パケットの到着時刻とヘッダ情報を、予め記憶装置に記憶されたパケット情報蓄積テーブルに新規登録すると共に、K個の各ハッシュ値に対応するビットマップ上のビットに1をセットする第2の手段と、
上記第1のノードから上記第2のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、当該パケットのフロー情報が上記パケット情報蓄積テーブルに既に登録されていると判断して当該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに登録する第3の手段と、
上記第2のノードから上記第1のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応するビットマップ上のビットが全て1である場合には、当該パケットのフロー情報が上記パケット情報蓄積テーブルに既に登録されていると判断して当該パケットの到着時刻とヘッダ情報を上記パケット情報蓄積テーブルに登録する第4の手段と、
予め定められた期間毎に、上記パケット情報蓄積テーブルに格納されたパケットの到着時刻とヘッダ情報を用いて、ネットワーク品質算出システムと上記第2のノード間の通信品質を算出する分析手段と
を有することを特徴とするネットワーク品質算出システム。
【請求項4】
請求項3に記載のネットワーク品質算出システムであって、
上記第1の手段と上記第2の手段および上記第3の手段による処理を、上記第2のノードから上記第1のノード方向のパケットに対して実行し、
上記第4の手段による処理を、上記第1のノードから上記第2のノード方向のパケットに対して実行し、
上記分析手段により、ネットワーク品質算出システムと上記第1のノード間の通信品質を算出して、上記第1のノードと上記第2のノード間のリンクを通過するフローの通信品質を算出することを特徴とするネットワーク品質算出システム。
【請求項5】
請求項1から請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記パケット情報蓄積テーブルに格納されたフロー情報が同じ、ならびに、発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が同じパケットを抽出し、
抽出したパケットを到着順に並び替え、
上記第1のノードから上記第2のノード方向の各パケットkに対応した上記第2のノードから上記第1ノード方向の各確認応答パケットkを特定して、各確認応答パケットkの到着時刻と各パケットkの到着時刻との差を求め、求めた差の平均値と最小値を、ネットワーク品質算出システムと上記第2のノード間の通信品質として算出する
ことを特徴とするネットワーク品質算出システム。
【請求項6】
請求項2もしくは請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記パケット情報蓄積テーブルに格納されたフロー情報が同じ、ならびに、発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が同じパケットを抽出し、
抽出したパケットを到着順に並び替え、
上記第1のノードから上記第2のノード方向の各パケットkに対応した上記第2のノードから上記第1ノード方向の各確認応答パケットkを特定して、各確認応答パケットkの到着時刻と各パケットkの到着時刻との差を求め、求めた差の平均値RTT_AB_avgと最小値RTT_AB_minを、ネットワーク品質算出システムと上記第2のノード間の通信品質として算出すると共に、
上記第2のノードから上記第1ノード方向の各パケットk’に対応した上記第1のノードから上記第2のノード方向の各確認応答パケットk’を特定して、各確認応答パケットk’の到着時刻と各パケットk’の到着時刻との差を求め、求めた差の平均値RTT_BA_avgと最小値RTT_BA_minを、ネットワーク品質算出システムと上記第1のノード間の通信品質として算出し、
かつ、
上記平均値RTT_AB_avgと上記平均値RTT_BA_avgとを加算して、上記第1のノードと上記第2のノード間での双方向フローの往復伝播遅延時間の平均値RTT_avgを求めると共に、
上記最小値RTT_AB_minと上記最小値RTT_BA_minとを加算して、上記第1のノードと上記第2のノード間での双方向フローの往復伝播遅延時間の最小値RTT_minを求める
ことを特徴とするネットワーク品質算出システム。
【請求項7】
請求項2もしくは請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記パケット情報蓄積テーブルに格納されたフロー情報が同じ、ならびに、発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報が同じパケットを抽出し、
抽出した各パケットを到着順に並び替え、
上記第1のノードから上記第2のノード方向の各パケットkに対応した上記第2のノードから上記第1ノード方向の各確認応答パケットkを特定すると共に、
特定した各確認応答パケットkに対応した上記第1のノードから上記第2のノード方向の各確認応答パケットk*を特定し、
各確認応答パケットk*の到着時刻と各パケットkの到着時刻との差を求め、求めた差の平均値RTT_avgと最小値RTT_minおよび最大値RTT_maxを、上記第1のノードと上記第2のノード間での双方向フローの往復伝播遅延時間の平均値と最小値および最大値として算出する
ことを特徴とするネットワーク品質算出システム。
【請求項8】
請求項1から請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記第1のノードから上記第2のノード方向の再送パケットの数n_ret_ABと上記第2のノードから上記第1ノード方向の再送パケットの数n_ret_BAとを計数すると共に、
上記第1のノードから上記第2のノード方向のパケットの数n_ABと上記第2のノードから上記第1ノード方向の再送パケットの数n_BAとを計数し、
上記第1のノードから上記第2のノード方向のパケットの再送率を、n_ret_AB÷n_ABにより算出すると共に、
上記第2のノードから上記第1ノード方向のパケットの再送率を、n_ret_BA÷n_BAにより算出する
ことを特徴とするネットワーク品質算出システム。
【請求項9】
請求項8に記載のネットワーク品質算出システムであって、
上記分析手段は、
予め定められた上記再送率とパケット損失率の関係式(パケット損失率=f×(再送率))を用いて、上記第1のノードと上記第2のノード間でのパケット損失率R_lossを、
「R_loss=1−{1−f×(R_ret_AB)}×{1−f×(R_ret_BA)}」により算出する
ことを特徴とするネットワーク品質算出システム。
【請求項10】
請求項1から請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記第1のノードから上記第2のノード方向のパケットのバイト数の総和を算出すると共に、
上記第1のノードから上記第2のノード方向の最後に到着したパケットの到着時刻と、最初に到着したパケットの到着時刻との差を算出し、
上記バイト数の総和を上記到着時刻の差で除した値を、上記第1のノードから上記第2のノード方向のスループットTh_ABとして算出する
ことを特徴とするネットワーク品質算出システム。
【請求項11】
請求項6もしくは請求項7のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
上記第1のノードから上記第2のノード方向のパケットのバイト数の総和を算出すると共に、
上記第1のノードから上記第2のノード方向の最後に到着したパケットの到着時刻と、最初に到着したパケットの到着時刻との差を算出し、
上記バイト数の総和を上記到着時刻の差で除した値を、上記第1のノードから上記第2のノード方向のスループットTh_ABとして算出し、
上記第2のノードから上記第1ノード方向のパケットのバイト数の総和を算出すると共に、
上記第2のノードから上記第1ノード方向の最後に到着したパケットの到着時刻と、最初に到着したパケットの到着時刻との差を算出し、
上記バイト数の総和を上記到着時刻の差で除した値を、上記第2のノードから上記第1のノード方向のスループットTh_BAとして算出し、
上記第1のノードと上記第2のノード間のスループットThを、「Th=(Th_BA+Th_AB)÷2」により算出すると共に、
予め定められたスループットThとパケット損失率R_lossおよび上記平均値RTT_avgの関係式である「Th=g×(R_loss,RTT_avg)」により、
上記第1のノードから上記第2のノード間のパケット損失率R_lossを算出する
ことを特徴とするネットワーク品質算出システム。
【請求項12】
請求項11に記載のネットワーク品質算出システムであって、
上記分析手段は、
上記関係式「Th=g×(R_loss,RTT_avg)」として、
「Th=MSS÷{RTT×(R_loss)1/2}を用いる
ことを特徴とするネットワーク品質算出システム。
【請求項13】
請求項1から請求項12のいずれかに記載のネットワーク品質算出システムであって、
上記分析手段は、
予め記憶装置に格納された地理データベースを用いて、各パケットの上記フロー情報を構成する発信元IPアドレスsrcIPの所属するエリアA、および、着信先IPアドレスdstIPの所属するエリアBをマップし、
発信元IPアドレスsrcIPがエリアAに所属し、かつ、着信先IPアドレスdstIPがエリアBに所属したフローの数(srcIP∈A ∧ dstIP∈B|)を用いて、
エリアAとエリアBの間の通信品質d(A,B)を、
「d(A,B)=ΣsrcIP∈A ∧ dstIP∈Bd(i)÷|srcIP∈A ∧ dstIP∈B|」により算出する
ことを特徴とするネットワーク品質算出システム。
【請求項14】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
第1のノードから第2のノード方向のパケットを予め定められた間隔でサンプリングする第1の手段と、
該第1の手段がサンプリングしたパケットのヘッダ情報を解析して、SYNフラグが立っていれば、該パケットの発信元IPアドレス、着信先IPアドレス、発信元ポート番号、着信先ポート番号、プロトコルからなるフロー情報を読み出し、該フロー情報をキーとしてBloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、予め記憶装置に記憶された、K個のハッシュ関数およびb個の時刻情報を登録する時刻テーブル内において、K個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、1つ以上がゼロである場合には、新規フローからのパケットと判断して、対応する位置に現在の時刻を書き込む第2の手段と、
上記第1のノードから上記第2のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、上記時刻テーブル内においてK個のハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、全てゼロ以外の値である場合には、当該位置に現在の時刻を書き込む第3の手段と、
上記第2のノードから上記第1のノード方向のパケットが到着する度に、該パケットの上記フロー情報を読み出し、該フロー情報における発信元IPアドレスと着信先IPアドレスのそれぞれおよび発信元ポート番号と着信先ポート番号のそれぞれを入れ替えたフロー情報をキーとして上記BloomFilterのK個のハッシュ関数に入力して得られるK個のハッシュ値を調べ、各ハッシュ値に対応する各々の位置(K箇所)における時刻情報を調べ、当該位置における最も古い時刻を読み出し、該最も古い時刻を現在の時刻から差し引いた値を、当該パケットの属するフローの、上記第1のノードから上記第2のノード方向へのパケットに対するAckパケットが帰ってくるまでの往復伝播遅延時間RTTとして算出する分析手段と
を有することを特徴とするネットワーク品質算出システム。
【請求項15】
請求項3,4もしくは請求項14のいずれかに記載のネットワーク品質算出システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記分析手段による通信品質の算出を実行するたびに、上記BloomFilter内のビットを全て0にクリアする手段
を有することを特徴とするネットワーク品質算出システム。
【請求項16】
請求項3もしくは請求項4のいずれかに記載のネットワーク品質算出システムであって、
上記BloomFilterは第1,第2の2つのBloomFilterからなり、
上記分析手段により最初に通信品質の算出を実行するまでの期間は、上記第2,3,4の手段は、上記第1,第2のBloomFilterの双方を用いて入力し、
上記分析手段により2番目を含む偶数番目に通信品質の算出を実行するまでの期間は、上記第2,第3の手段は、上記第1のBloomFilter内のビットを全て0にクリアした後、上記第1のノードから上記第2のノード方向のパケットに対する処理を、上記第1のBloomFilterに対してのみ実行すると共に、上記第4の手段は、上記第2のノードから上記第1のノード方向のパケットに対する処理を、上記第1,第2のBloomFilterの双方に対して実行し、
上記分析手段により3番目を含む奇数番目に通信品質の算出を実行するまでの期間は、上記第2,第3の手段は、上記第2のBloomFilter内のビットを全て0にクリアした後、上記第1のノードから上記第2のノード方向のパケットに対する処理を、上記第2のBloomFilterに対してのみ実行すると共に、上記第4の手段は、上記第2のノードから上記第1のノード方向のパケットに対する処理を、上記第1,第2のBloomFilterの双方に対して実行する
ことを特徴とするネットワーク品質算出システム。
【請求項17】
請求項1から請求項16のいずれかに記載のネットワーク品質算出システムであって、
上記第1の手段は、N個の到着パケットに対して1個のパケットをサンプリングし、
上記第2の手段は、
上記SYNフラグが立っているパケットを処理の対象とする代わりに、
サンプリングされたパケットの上記フロー情報を読み出し、該フロー情報をキーとして、予め記憶装置に記憶されたハッシュ関数に入力して、ハッシュ値を得、該ハッシュ値を、ハッシュ値の取りうる値の最大値で割った値が、1/Nよりも小さければ、当該パケットを処理の対象とする
ことを特徴とするネットワーク品質算出システム。
【請求項18】
プログラムされたコンピュータ処理により、IPネットワークの通信品質を求めるコンピュータ装置によるネットワーク品質算出方法であって、
コンピュータ装置のプログラムされたコンピュータ処理実行手順として、
請求項1から請求項17のいずれかに記載のネットワーク品質算出システムにおける各手順を含むことを特徴とするネットワーク品質算出方法。
【請求項19】
コンピュータを、請求項1から請求項17のいずれかに記載のネットワーク品質算出システムにおける各手段として機能させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2011−4333(P2011−4333A)
【公開日】平成23年1月6日(2011.1.6)
【国際特許分類】
【出願番号】特願2009−147697(P2009−147697)
【出願日】平成21年6月22日(2009.6.22)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成23年1月6日(2011.1.6)
【国際特許分類】
【出願日】平成21年6月22日(2009.6.22)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]