(57)【要約】パケットロスの頻度を低い処理コストで計測するパケットロス頻度計測システムを提供する。パケット情報記憶手段１１２は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域１１３を複数有する。パケット情報登録手段１１１は、パケット受信時に、複数のパケット情報記憶領域１１３のうちの一つを選択し、選択したパケット情報記憶領域１１３に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させる。計数手段１１４は、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する。
2010047044.tif 000002
【特許請求の範囲】
【請求項１】
パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域を複数有するパケット情報記憶手段と、
パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段と、
予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段とを備える
ことを特徴とするパケットロス頻度計測システム。
【請求項２】
パケット内の送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤ、当該パケットロス頻度計測システムのポートの番号のうちの少なくとも一部の項目の組み合わせからパケットをグループに分類する分類手段を備え、
パケット情報登録手段は、選択したパケット情報記憶領域に受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させる処理をグループ単位で行う
請求項１に記載のパケットロス頻度計測システム。
【請求項３】
パケット情報登録手段は、選択したパケット情報記憶領域にパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるときに、前記値に応じた情報として、所定ビット数のビット列における前記値に応じたビット位置に１を記憶させる
請求項１または請求項２に記載のパケットロス頻度計測システム。
【請求項４】
パケット情報登録手段は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、選択したパケット情報記憶領域に配列として記憶させる
請求項１または請求項２に記載のパケットロス頻度計測システム。
【請求項５】
パケット情報登録手段は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、当該値をハッシュ関数を用いて変換することによって求める
請求項１から請求項４のうちのいずれか１項に記載のパケットロス頻度計測システム。
【請求項６】
パケット情報登録手段は、ブルームフィルタまたはスペースコードブルームフィルタまたはマルチレゾリューションスペースコードブルームフィルタのアルゴリズムに従って、パケット内の少なくとも確認応答番号を含むフィールドの値をハッシュ関数を用いて変換する
請求項５に記載のパケットロス頻度計測システム。
【請求項７】
パケット情報登録手段は、フラグ情報、広告ウィンドウサイズ、送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤのいずれか一つ以上と、確認応答番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる
請求項１から請求項６のうちのいずれか１項に記載のパケットロス頻度計測システム。
【請求項８】
パケット情報登録手段は、パケット内の少なくとも確認応答番号を含むフィールドの値と当該パケットロス頻度計測システムのポートの番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる
請求項１から請求項７のうちのいずれか１項に記載のパケットロス頻度計測システム。
【請求項９】
パケット情報登録手段は、ランダムに選択する方式、ラウンドロビン、あるいは、個々のパケット情報記憶領域に予め定められた選択確率に従ってパケット情報記憶領域のいずれかを選択する方式のいずれかの方式で、パケット情報記憶領域を選択する
請求項１から請求項８のうちのいずれか１項に記載のパケットロス頻度計測システム。
【請求項１０】
パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段を備える
ことを特徴とする情報登録装置。
【請求項１１】
パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域を複数有するパケット情報記憶手段を備える請求項１０に記載の情報登録装置。
【請求項１２】
パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段を備える
ことを特徴とする情報計数装置。
【請求項１３】
パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させ、
予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する
ことを特徴とするパケットロス頻度計測方法。
【請求項１４】
パケット内の送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤ、当該パケットロス頻度計測システムのポートの番号のうちの少なくとも一部の項目の組み合わせからパケットをグループに分類し、
選択したパケット情報記憶領域に受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させる処理をグループ単位で行う
請求項１３に記載のパケットロス頻度計測方法。
【請求項１５】
選択したパケット情報記憶領域にパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるときに、前記値に応じた情報として、所定ビット数のビット列における前記値に応じたビット位置に１を記憶させる
請求項１３または請求項１４に記載のパケットロス頻度計測方法。
【請求項１６】
パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、選択したパケット情報記憶領域に配列として記憶させる
請求項１３または請求項１４に記載のパケットロス頻度計測方法。
【請求項１７】
パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、当該値をハッシュ関数を用いて変換することによって求める
請求項１３から請求項１６のうちのいずれか１項に記載のパケットロス頻度計測方法。
【請求項１８】
ブルームフィルタまたはスペースコードブルームフィルタまたはマルチレゾリューションスペースコードブルームフィルタのアルゴリズムに従って、パケット内の少なくとも確認応答番号を含むフィールドの値をハッシュ関数を用いて変換する
請求項１７に記載のパケットロス頻度計測方法。
【請求項１９】
フラグ情報、広告ウィンドウサイズ、送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤのいずれか一つ以上と、確認応答番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる
請求項１３から請求項１８のうちのいずれか１項に記載のパケットロス頻度計測方法。
【請求項２０】
パケット内の少なくとも確認応答番号を含むフィールドの値と当該パケットロス頻度計測システムのポートの番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる
請求項１３から請求項１９のうちのいずれか１項に記載のパケットロス頻度計測方法。
【請求項２１】
ランダムに選択する方式、ラウンドロビン、あるいは、個々のパケット情報記憶領域に予め定められた選択確率に従ってパケット情報記憶領域のいずれかを選択する方式のいずれかの方式で、パケット情報記憶領域を選択する
請求項１３から請求項２０のうちのいずれか１項に記載のパケットロス頻度計測方法。
【請求項２２】
コンピュータに、
パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録処理、および、
予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数処理
を実行させるためのパケットロス頻度計測プログラム。
【請求項２３】
コンピュータに、
パケット内の送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤ、当該パケットロス頻度計測システムのポートの番号のうちの少なくとも一部の項目の組み合わせからパケットをグループに分類する分類処理を実行させ、
グループ単位にパケット情報登録処理を実行させる
請求項２２に記載のパケットロス頻度計測プログラム。
【請求項２４】
コンピュータに、
パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録処理
を実行させるための情報登録プログラム。
【請求項２５】
コンピュータに、
パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数処理
を実行させるための情報計数プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークの品質として、パケットロスの頻度を計測するパケットロス頻度計測システム、および、パケットロス頻度計測システムに適用される情報登録装置、情報計数装置、パケットロス頻度計測方法、パケットロス頻度計測プログラム、情報登録プログラム、情報計数プログラムに関する。
【背景技術】
【０００２】
エンドツーエンド（End-to-End）の通信におけるパケットのロスを検出する方法が非特許文献１に記載されている。例えば、非特許文献１に記載の方法は、多数の端末同士を接続させる通信ネットワークにおいて、各端末間の通信の品質を計測する装置に適用される。非特許文献１に記載された方法では、端末と端末とのパスにパケットのキャプチャ部を設け、このキャプチャ部がパスを通過するパケットをフルキャプチャする。キャプチャ部は、通過したパケットの確認応答番号を保持しておき、同じ確認応答番号のパケットが複数生じたときに（すなわち重複ＡＣＫ現象が生じたときに）、パケットロスを検出する。【０００３】
図１３は、非特許文献１に記載されている方法によりパケットのロスを検出する計測器の例を示すブロック図である。非特許文献１に記載されている方法を適用したパケットロスの計測器２１０の構成として、図１３に示すように、フロー識別手段２１１と、データベース（以下、ＤＢと記す）２１５と、カウンタ／ＤＢ読込手段２１２と、番号比較手段２１３と、カウンタ／ＤＢ書込手段２１４とを備える構成が考えられる。ＤＢ２１５は、フロー毎に、同一フローの直前のパケットにおける確認応答番号と、確認応答番号が重なった回数を示すカウント値とを記憶する。フロー識別手段２１１は、個々のパケット９１を読み込むと、そのパケットのフローを識別する。パケットのフローは、送受信それぞれのＩＰアドレス、送受信それぞれのポート番号、プロトコルＩＤ等によって識別される。なお、図１３では、実線で示した各パケットが同じフローであり、破線で示した各パケットが他のフローに属している。【０００４】
カウンタ／ＤＢ読込手段２１２は、フロー識別手段２１１が識別した新たなパケットと同じフローにおける直前のパケットの確認応答番号と、その確認応答番号が重なった数を示すカウント値をＤＢ２１５から読み込む。番号比較手段２１３は、フロー識別手段２１１が識別した新たなパケットの確認応答番号と、同一フローの直前のパケットの確認応答番号とを比較し、一致しているならば、読み出されたカウント値に１を加算し、一致していなければカウント値を変更しない。この処理の後、カウンタ／ＤＢ書込手段２１４は、新たなパケットの確認応答番号と番号比較手段２１３の処理後のカウント値を、ＤＢ２１５に記憶させる。【０００５】
パケットロスを推定する方法は、例えば、特許文献１，２にも記載されている。また、特許文献３には、過去の受信したパケットのポート番号を記憶する学習テーブルと、新たに受信したパケットのポート番号を記憶するフレーム格納メモリとを参照して、新たに受信したパケットと過去のパケットのポート番号を比較する通信装置が記載されている。また、特許文献４には、ポート番号によってパケットを分類し、パケット数をテーブルで計数するＩＰパケットカウント方法が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】再公表特許  国際公開番号ＷＯ２００６／０４３６２４（段落００２５，００４７，００５２）
【特許文献２】特開２００８−２１９１２７号公報（段落０１１０−０１１４）
【特許文献３】特開２００４−３２０２４８号公報（段落００８６，００８７）
【特許文献４】特開平１１−２０５３８６号公報（段落００２４−００２６）
【非特許文献】
【０００７】
【非特許文献１】大岸智彦、井戸上彰、長谷川亨、加藤聰彦、“片方向IPトラヒックからTCPレベルの統計情報を収集するパフォーマンスモニタの設計”、２０００年電子情報通信学会総合大会講演論文集、社団法人電子情報通信学会、ｐ．９６、２０００年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１等に記載された方法で確認応答番号の重複を検出するためには、パケット受信時に、そのパケットのフローで直前に受信したパケットを観測し、確認応答番号を確認する必要がある。受信したパケットと直前のパケットとで確認応答番号が一致していれば、確認応答番号の重複が生じたと認定し、確認応答番号が一致していなければ重複は生じていないと認定する。この動作はステート処理であるために、通信ネットワークの品質計測処理のコスト（処理時間や計算量）が増加してしまう。なお、ステート処理とは、観測対象の一パケットを参照しただけでは、何を実行すべきか判定できない処理を意味する。非特許文献１に記載された方法は、新たに受信したパケットだけでなく、直前に受信していたパケットも参照して処理を決定するので、処理時間等のコストが大きくなる。【０００９】
また、図１３に例示する構成では、確認応答番号の重複を検出するために、カウンタ／ＤＢ書込手段２１４が新たなパケットと同一フローにおける直前のパケットの確認応答番号をＤＢ２１５に書き込んだ後出なければ、新たなパケットが到着しても、カウンタ／ＤＢ読込手段２１２が直前のパケットの確認応答番号の読込処理を開始できない。このため、パケットのロスを計測するための処理速度の上限は、カウンタ／ＤＢ読込部２１２、番号比較部２１３、カウンタ／ＤＢ書込手段２１４の一連の動作速度に制限される。【００１０】
確認応答番号の重複の頻度は、パケットロスの指標となるが、確認応答番号の重複は複数のパケットにより観察される。図１３に示す構成では、新たにパケットが到着したときに直前のパケットとの比較を行うため、処理コストが大きくなっている。特許文献３に記載されたフレーム格納メモリおよび学習テーブルはポート番号を格納するが、ポート番号の代わりに確認応答番号を格納する構成としても、学習テーブルに直前のパケットの確認応答番号が格納されていなければ、新たなパケットとの比較を行えないので、図１３に示す構成と同様に、処理コストが大きくなる。また、単に、フレーム格納メモリおよび学習テーブルを比較するだけでは、重複が生じている確認応答番号がどれくらい多くあるのかを判断することができない。【００１１】
そこで、パケットロスの頻度を低い処理コストで計測するパケットロス頻度計測システム、および、そのパケットロス頻度計測システムに適用される情報登録装置、情報計数装置、パケットロス頻度計測方法、パケットロス頻度計測プログラム、情報登録プログラム、情報計数プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明によるパケットロス頻度計測システムは、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域を複数有するパケット情報記憶手段と、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段と、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段とを備えることを特徴とする。【００１３】
本発明による情報登録装置は、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段を備えることを特徴とする。【００１４】
本発明による情報計数装置は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段を備えることを特徴とする。【００１５】
本発明によるパケットロス頻度計測方法は、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録ステップと、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数ステップとを含むことを特徴とする。【００１６】
本発明によるパケットロス頻度計測プログラムは、コンピュータに、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録処理、および、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数処理を実行させることを特徴とする。【００１７】
本発明による情報登録プログラムは、コンピュータに、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録処理を実行させることを特徴とする。【００１８】
本発明による情報計数プログラムは、コンピュータに、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数処理を実行させることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、パケットロスの頻度を低い処理コストで計測することができる。
【図面の簡単な説明】
【００２０】
【図１】パケットロス頻度計測システムの配置例を示す説明図である。
【図２】本発明のパケットロス頻度計測システムの実施形態を示すブロック図である。
【図３】ビット列の例を示す説明図である。
【図４】計数手段の処理を示す説明図である。
【図５】パケット受信時の処理経過の例を示すフローチャートである。
【図６】情報読込手段および計数手段の処理の処理経過の例を示すフローチャートである。
【図７】パケットの確認応答番号に応じた情報を配列としてパケット情報記憶領域に記憶させる例を模式的に示す説明図である。
【図８】パケット受信毎に処理を実行する部分と情報の計数処理を実行する部分とが異なる装置で実現する構成例を示すブロック図である。
【図９】本発明の他の実施形態を示すブロック図である。
【図１０】本発明の概要を示すブロック図である。
【図１１】本発明の情報登録装置の最小の構成例を示すブロック図である。
【図１２】本発明の情報計数装置の最小の構成例を示すブロック図である。
【図１３】非特許文献１に記載されている方法によりパケットのロスを検出する計測器の例を示すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施形態を図面を参照して説明する。
図１は、パケットロス頻度計測システムの配置例を示す説明図である。図１に示す例では、各端末１１〜１５がそれぞれパケットを送受信することにより通信を行う。そして、通信ネットワーク内における各端末間の通信経路上に、パケットロス頻度計測システムが配置される。図１に示す例では、個々の装置２１〜２５がそれぞれパケットロス頻度計測システムに該当する。各装置２１〜２５は、それぞれパケットロスの頻度（すなわち、パケットロスの発生頻度）を計測する。また、図１に示す例では、各装置２１〜２５は、計測したパケットロスの頻度をサーバ３１に出力する。サーバ３１は、各装置２１〜２５におけるパケットロスの頻度を管理する。
【００２２】
また、各装置２１〜２５は、それぞれパケットのフロー毎にパケットロスの発生頻度を計測する。例えば、図１に示す装置２５は、端末１１，１２の通信経路上に位置し、端末１５，１２の通信経路上にも位置し、端末１３，１４の通信経路上にも位置する。従って、端末２５は、端末１１から端末１２へのフロー（以下、フローＡと記す）のパケットも、端末１５から端末１２へのフロー（以下、フローＢと記す）のパケットも、端末１３から端末１４へのフロー（以下、フローＣと記す）のパケットも通過させる。そして、端末２５は、フローＡ，Ｂ，Ｃ等の各パケットのフロー毎にパケットロスの頻度を計算する。
【００２３】
また、本発明のパケットロス頻度計測システムは、データの受信側の端末がデータの送信側の端末に向けて、受信側の端末にどのデータまで届いているかを確認する情報（確認応答番号）を送るプロトコルを対象としている。このようなプロトコルの代表例としてＴＣＰ（Transmission Control Protocol ）が挙げられるが、本発明を適用可能なプロトコルはＴＣＰに限定されない。例えば、ＳＣＴＰ（Stream Control Transmission Protocol）に本発明が適用されてもよい。また、ＵＤＰ（User Datagram Protocol）であっても、受信側の端末にどのデータまで届いているかを示すシーケンス番号をアプリケーション層でペイロードに追加する独自のプロトコルが定められていれば、本発明を適用することができる。
【００２４】
図１に示す装置２１〜２５は、通信ネットワーク内に存在するルータやスイッチ等のノードであってもよいし、ＴＡＰや装置のミラーポート等から入力された情報をもとに解析を行う装置であってもよい。
【００２５】
図２は、本発明のパケットロス頻度計測システムの実施形態を示すブロック図である。図２では、パケットロス頻度計測システムに該当する装置２１のブロック図として図示しているが、図１における各装置２１〜２５は、同様の構成である。本発明のパケットロス頻度計測システムは、フロー識別手段１と、情報書込手段２と、パケット情報保持手段３と、情報読込手段６と、計数手段７とを備える。
【００２６】
フロー識別手段１は、パケットロス頻度計測システムを通過するパケット５１を受信し、そのパケット５１のフローを識別する。フロー識別手段１は、受信したパケットの特定のフィールドが同一であるパケット群が同一フローであるとみなして、フロー毎にパケットを分類する。例えば、送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号、送信ＭＡＣアドレス、受信ＭＡＣアドレス、プロトコルＩＤ（プロトコルの識別情報）のいずれかの一つ以上の項目の組を予め定めておき、その組の各項目が複数のパケットにおいて同一であれば、フロー識別手段１は、その複数のパケットが同一のフローであるとみなす。ここでは、送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号、送信ＭＡＣアドレス、受信ＭＡＣアドレス、プロトコルＩＤを例示したが、このほかに、パケットロス頻度計測システムのポートの番号を、パケットのフローを特定するための項目の一つとして用いてもよい。すなわち、フロー識別手段１は、パケット中の、送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤ、パケットロス頻度計測システムのポートの番号のうちの少なくとも一部の項目の組を定め、その組の項目が複数のパケットで同一ならば、その複数のパケットを一つのグループとして分類すればよい。なお、パケットロス頻度計測システムのポートの番号とは、パケットロス頻度計測システムとしてパケットを送受信する装置における複数のポートのうち、パケットを受信したポート、およびそのパケットを次のノードに送信したポートの番号である。
【００２７】
なお、図２では、実線で示した各パケットが同じフローであり、破線で示した各パケットが他のフローに属している。
【００２８】
パケット情報保持手段３は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域４，５を、フロー毎に複数有する記憶装置である。ここでは、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域４，５が、予め定められたビット長のビット列を記憶する記憶領域である場合を例にして説明する。また、この場合、パケット情報記憶領域４，５をカウンタと記す。ここでは、パケットロス頻度計測システムが受信したパケット内の確認応答番号に応じた値をカウンタ４，５に記憶させる場合を例にする。
【００２９】
ここでは、一つのフローに対して二つのカウンタ４，５を用いる場合を例にして説明するが、一つのフローに対して用いられるカウンタ（パケット情報記憶領域）の数は二つに限定されず複数であればよい。以下、二つのカウンタのうち一方を第１カウンタ４と記し、他方を第２カウンタ５と記す。
【００３０】
情報書込手段２は、フロー識別手段１がパケットを受信して、そのパケットをフロー毎に分類した後に、そのパケットが分類されたグループに対応する複数のカウンタ（本例では二つのカウンタ４，５）のうちの一つのカウンタを選択し、選択したカウンタに、受信したパケットの確認応答番号に応じた情報を記憶させる。本実施形態では、第１カウンタ４および第２カウンタ５が、予め定められたビット長のビット列を記憶する記憶領域である。そして、情報書込手段２が、受信したパケットの確認応答番号に応じた情報として、予め定められたビット長のビット列における確認応答番号に応じたビット位置に１を記憶させる場合を例にして説明する。
【００３１】
情報書込手段２が複数のカウンタのうちの一つを選択する方式は、例えば、ランダムにカウンタを選択する方式であってもよい。ランダムにカウンタを選択する場合、乱数を利用してもよい。例えば、各カウンタ４，５に均等に乱数の値を割り当てておき、カウンタ選択時に乱数を発生させ、その乱数の値に対応するカウンタを選択してもよい。また、情報書込手段２は、各カウンタを順番に選択していくラウンドロビン方式でカウンタを選択してもよい。例えば、受信したパケット毎に、第１カウンタ４、第２カウンタ５、第１カウンタ４、第２カウンタ５、・・・という順番にカウンタを選択してもよい。また、各カウンタに対して、選択される確率の重みづけを予め行っておき、その確率に従ってカウンタを選択してもよい。例えば、第１カウンタ４が選択される選択確率をＰ、第２カウンタ５が選択される選択確率を１−Ｐとして予め定め、その選択確率に従って、いずれかのカウンタを選択してもよい。
【００３２】
情報書込手段２は、選択したカウンタに対して、予め定められたビット長のビット列における確認応答番号に応じたビット位置に１を記憶させる。
【００３３】
確認応答番号と、ビット列内のビット位置との対応関係を定める方法は、例えば、単純に、各確認応答番号と、ビット列内のビット位置とを直接対応づける方法であってもよい。すなわち、ビット列内の各ビット位置に確認応答番号を直接割り当てておき、パケット受信時に、情報書込手段２は、そのパケットの確認応答番号が割り当てられているビット位置に「１」を記憶させてもよい。
【００３４】
また、予めハッシュ関数を定めておき、そのハッシュ関数を用いて得られるハッシュ値と、ビット列内のビット位置とを対応づける方法であってもよい。この場合、ハッシュ関数を用いて得られる各ハッシュ値と、ビット列内の各ビット位置とを対応づけておき、情報書込手段２は、受信したパケットの確認応答番号のハッシュ値をそのハッシュ関数を用いて計算し、計算によって得られたハッシュ値に対応するビット位置に「１」を記憶させてもよい。ハッシュ関数を用いて計算した確認応答番号のハッシュ値に対応する位置に「１」を記憶させるアルゴリズムとして、例えば、ブルームフィルタ（Bloom Filter）や、その応用であるスペースコードブルームフィルタ（Space-Code Bloom Filter）やマルチレゾリューションスペースコードブルームフィルタ（Multi-Resolution Space-Code Bloom Filter）がある。情報書込手段２は、ビット列における確認応答番号に応じたビット位置に１を記憶させる処理をブルームフィルタまたはスペースコードブルームフィルタまたはマルチレゾリューションスペースコードブルームフィルタに従って行ってもよい。なお、ハッシュ値は、ハッシュ関数による確認応答番号の変換結果であるということができる。
【００３５】
図３は、各カウンタ４，５に記憶される予め定められたビット長のビット列の例を示す。情報書込手段２は、受信したパケットの確認応答番号のハッシュ値を、例えば、ブルームフィルタに従って計算する。また、情報書込手段２が、第１カウンタ４を選択していれば、第１カウンタ４のビット列における、そのハッシュ値に対応するビット位置に「１」を格納する。また、第２カウンタ５を選択していれば、第２カウンタ５のビット列における、そのハッシュ値に対応するビット位置に「１」を格納する。
【００３６】
また、予め定めておいた固定値で確認応答番号を除算したときの余りと、ビット列内のビット位置とを対応づける方法であってもよい。この場合、固定値による確認応答番号の除算で得られる余りと、ビット列内の各ビット位置とを対応づけておき、パケット受信時に、情報書込手段２は、そのパケットの確認応答番号を固定値で除算して余りを求め、その余りに対応するビット位置に「１」を記憶させてもよい。
【００３７】
フロー識別手段１および情報書込手段２は、個々のパケットを受信する毎に上記の処理を行う。すなわち、フロー識別手段１は、受信したパケット毎に、パケットのフローを識別する。また、情報書込手段２は、受信したパケット毎に、パケットのフローに対応する複数のカウンタから一つのカウンタを選択して、パケットの確認応答番号に応じた情報をそのカウンタに記憶させる処理を行う。
【００３８】
一方、以下に示す情報読込手段６および計数手段７は、パケットを受信する毎に処理を実行する必要はない。情報読込手段６は、パケットの受信とは関連なく、各カウンタからビット列を読み込む処理を実行し、情報読込手段６のビット列読込処理に続いて計数手段７が処理を行う。
【００３９】
情報読込手段６は、個々のフローに対応する複数のカウンタに記憶されたビット列を読み込み、計数手段７に渡す。上記のように、情報読込手段６は、パケットの到着とは関連なくこの処理を行ってよい。例えば、情報読込手段６は、定期的にカウンタのビット列の読み込みを行ってもよい。あるいは、外部のシステムからの命令や、外部のシステムにおけるイベントをトリガにして、不定期にビット列の読み込みを行ってもよい。
【００４０】
計数手段７は、一つのフローに対応する複数のカウンタのうち、予め定められた数以上のカウンタに共通に記憶されている情報の数を計数する。以下、この「予め定められた数」を共通数と記す。また、共通数は、一つのフローに対応する複数のカウンタの数をＮとしたときに、２以上Ｎ以下となる値から定められる。本例では、一つのフローに対応するカウンタは２個であり、共通数は２である。従って、本例では、計数手段７は、２個のカウンタに共通に記憶されている情報の数を計数する。また、本例では、確認応答情報に応じた情報は、その確認応答情報に応じたビット位置に「１」として格納される。よって、各カウンタに共通に記憶される情報とは、同じビット位置に格納された「１」である。よって、計数手段７は、第１カウンタ４と第２カウンタ５のビット列のＡＮＤ（論理積）計算を行って、その結果得られるビット列中の「１」の数を計数すればよい。
【００４１】
図４は、計数手段７の処理を示す説明図である。例えば、第１カウンタ４がビット列６１（図４参照）を記憶し、第２カウンタ５がビット列６２を記憶していて、情報読込手段６がこのビット列６１，６２を読み込んだとする。計数手段７は、このビット列６１，６２のＡＮＤ計算を行い、図４に示すビット列６３を得る。そして、計数手段７は、ＡＮＤ計算によって得たビット列６３中の「１」の数を計数する。図４に示す例において、計数結果は３となる。
【００４２】
パケットロスが生じなければ、同一フローにおいて確認応答番号が重複するパケットは送信されないため、ある確認応答番号のパケットは計測地点を一度しか通過しない。その結果、その確認応答番号に応じたビット位置の「１」は、二つのカウンタ４，５のうちの一つにしか記憶されず、第１カウンタ４と第２カウンタ５のビット列のＡＮＤ計算の結果、そのビット位置の値は０となる。一方、パケットロスが生じた場合、確認応答番号が同一の複数のパケットが送信され、その各パケットがパケットロス頻度計測システムを通過すると、各カウンタ４，５の同一のビット位置に「１」が格納されていく。従って、各カウンタ４，５のビット列のＡＮＤ計算によって得たビット列中の「１」の数は、パケットロスの頻度を表す値であり、「１」の数が多い程、パケットロスの回数が多いことになる。なお、ＡＮＤ計算によって得たビット列中の「１」は、共通数以上のカウンタに共通に記憶された情報の個数ということができる。
【００４３】
なお、ここでは、一つのフロー当たりのカウンタが２個であり、共通数を２とした場合を例に説明したが、既に説明したように、一つのフロー当たりのカウンタの数は、複数であれば２個でなくてもよい。例えば、一つのフロー当たりのカウンタ数が、３個、４個等であってもよい。また、共通数も２に限定されない。一つのフロー当たりのカウンタ数が多いほど、パラレル処理できるパケット数が多くなり、パケットロスの頻度を求める処理を高速化しやすくなる。
【００４４】
本実施形態において、フロー識別手段１、情報書込手段２、情報読込手段６、および計数手段７は、例えば、プログラム（パケットロス頻度計測プログラム）に従って動作するＣＰＵによって実現される。パケットロス頻度計測システムが備える記憶装置にプログラムが記憶され、パケットロス頻度計測システムのＣＰＵがそのプログラムを読み込み、ロー識別手段１、情報書込手段２、情報読込手段６、および計数手段７として動作してもよい。また、各手段がそれぞれ別々のユニットとして実現されていてもよい。
【００４５】
次に、動作について説明する。
図５は、パケット受信時の処理経過の例を示すフローチャートである。パケットロス頻度計測システムは端末間で送受信されるパケットを受信すると、そのパケットを次のノードに転送する。このとき受信したパケットに関して、以下の処理を実行する。
【００４６】
まず、フロー識別手段１は、受信したパケットのフローを識別する（ステップＡ１）。例えば、フロー識別手段１は、パケットのヘッダにおける送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤから、フローを識別するフローＩＤを特定すればよい。フロー識別手段１は、パケットロス頻度計測システムのポートの番号（パケットを受信した自装置のポートおよび、次のノードに向けてパケットを送信したポートの番号）も参照してパケットのフローを識別してもよい。
【００４７】
次に、書込手段２は、受信したパケットのフローに対応する複数のカウンタの中から一つのカウンタを選択する（ステップＡ２）。ここでは、図２に示すように、フロー毎に第１カウンタ４および第２カウンタ５が用いられる場合を例にする。書込手段２がカウンタを選択する態様は限定されず、例えば、ランダムにカウンタを選択しても、ラウンドロビン方式でカウンタを選択しても、各カウンタ毎に個別に定められた選択確率に従ってカウンタを選択してもよい。
【００４８】
ステップＡ２で第１カウンタ４を選択した場合、書込手段２は、第１カウンタ４に、受信したパケットの確認応答番号に応じた情報を記憶させる（ステップＡ４）。また、ステップＡ２で第２カウンタ５を選択した場合、書込手段２は、第２カウンタ５に、受信したパケットの確認応答番号に応じた情報を記憶させる（ステップＡ５）。本例では、ステップＡ４，Ａ５で、選択したカウンタのビット列における確認応答番号に応じたビット位置に１を記憶させるものとする。既に説明したように、確認応答番号とビット位置とを対応づけておいてもよい。また、確認応答番号のハッシュ値とビット位置とを対応づけておいてもよい。ビット列における確認応答番号に応じたビット位置に１を記憶させる処理をブルームフィルタまたはスペースコードブルームフィルタまたはマルチレゾリューションスペースコードブルームフィルタに従って行ってもよい。
【００４９】
続いて、パケット受信との関連なしに行う情報読込手段６および計数手段７の処理について説明する。図６は、この処理の経過の例を示すフローチャートである。ここでは、定期的に図６に示す処理を実行する場合を例にして説明する。また、情報読込手段６および計数手段７は、以下の処理をフロー毎に行う。
【００５０】
情報読込手段６は、個々のフロー毎に、フローに対応する複数のカウンタに記憶された情報（本例では、ビット列）を読み込む（ステップＢ１）。ステップＢ１の後、計数手段７は、共通数（本例では２）のカウンタに共通に記憶されている情報を計数する（ステップＢ２）。すなわち、ここでは、どちらのカウンタでも「１」が格納されたビット位置の数を計数すればよい。計数手段７は、情報読込手段６が読み込んだ２つのビット列のＡＮＤ計算を行い、ＡＮＤ計算の結果として得たビット列中の「１」の数を計数すればよい。
【００５１】
ステップＢ２の計数結果が、各フローのパケットロス頻度を表している。すなわち、ステップＢ２の計数結果の値が大きいほど、パケットロス発生回数が多いことを表し、計数結果の値が小さいほど、パケットロス発生回数が少ないことを表す。
【００５２】
パケットロス頻度計測システムは、パケットロス頻度（ステップＢ２の計数結果）を、例えば、図１に示すサーバ３１に送信してもよい。そして、サーバ３１が各パケットロス頻度計測システムから受信したパケットロス頻度を記憶しておいてもよい。
【００５３】
本例では、一つのフローに対応するカウンタが２つである場合を例示したが、一つのフローに対応するカウンタの数は３以上であってもよい。この場合も、計数手段７は、共通数以上のカウンタに共通に記憶されている情報を計数する。一つのフローに対応するカウンタの数と、共通数とが一致していれば、計数手段７は、各カウンタのビット列の論理積を求めて、その結果のビット列に含まれている「１」の数を計数すればよい。一つのフローに対応するカウンタよりも共通数が小さければ、ビット位置毎に、共通数以上のカウンタで「１」が格納されているかを確認し、共通数以上のカウンタで「１」が格納されているビット位置の数を計数すればよい。
【００５４】
本発明によれば、情報書込手段２が、複数のカウンタ（パケット情報記憶領域）の中から一つを選択し、そのカウンタに、パケットの確認応答番号に応じた情報を記憶させる。そして、各カウンタに記憶された情報を読み込んで、共通数以上のカウンタに共通に記憶されている情報の数を計数する。このような構成では、パケットを受信したときに、情報書込手段２は、カウンタの選択と、そのカウンタに対する書込を行えばよく、過去に受信したパケットと、新たに受信したパケットとの比較をする必要がない。よって、パケット受信時の処理は、ステートレス処理となり、処理時間や計算量などの処理コストを低減することができる。また、パケットの受信タイミングとは無関係に各カウンタの値を参照して計数を行うことができる。従って、計数手段７が計数を行うときには、情報書込手段２の処理完了を待つ必要がなく、情報書込手段２によって、計数手段７の処理速度が制限されることがない。さらに、カウンタが複数存在しているので、一つのパケットを受信して、選択したカウンタに対する書き込み（ステップＡ３またはステップＡ４）を実行しているときに、同一フローに属する他のパケットを受信したとしても、そのパケットに対する処理を実行することができるので、処理を高速化することができる。
【００５５】
上記の実施形態では、パケット情報記憶領域（カウンタ）４，５が、予め定められたビット長のビット列を記憶する記憶領域であり、受信したパケットの確認応答番号に応じた位置に「１」を記憶させる場合を例にして説明した。受信したパケットの確認応答番号に応じた情報を、他の態様でパケット情報記憶領域４，５に記憶させてもよい。図７は、パケットの確認応答番号に応じた情報を配列としてパケット情報記憶領域に記憶させる例を模式的に示す説明図である。図７に示す１５，３７，４５，・・・等の各値は、パケットの確認応答番号に応じた情報を表している。情報書込手段２は、複数のパケット情報記憶領域のうちの一つを選択した後、選択したパケット情報記憶領域に、確認応答番号に応じた情報自体を配列の要素として記憶させてもよい。ただし、記憶させようとする情報が、選択したパケット情報記憶領域に既に記憶されているならば、その情報は記憶させなくてよい。
【００５６】
情報読込手段６は、フロー毎に、各パケット情報記憶領域に記憶された配列を読み込む。また、計数手段７は、フロー毎に、共通数以上のパケット情報記憶領域に共通に記憶された情報の数を計数すればよい。その計数結果が、各フローのパケットロス頻度を表す。例えば、一つのフローに対して二つのパケット情報記憶領域が用いられ、共通数が２であり、図７に例示する配列が記憶されていたとする。この場合、計数手段７は、二つの配列に共通に記憶されている情報は「１５」、「４５」を計数し、計数結果として２を得る。
【００５７】
また、上記の実施形態では、受信したパケットの確認応答番号に応じた情報をパケット情報記憶領域に記憶させる場合を例にして説明したが、確認応答番号と他の情報との組み合わせに応じた情報をパケット情報記憶領域に記憶させてもよい。例えば、ＴＣＰのパケットのパケットロス頻度の計測を行う場合、パケットのヘッダに含まれる確認応答番号と、広告ウィンドウサイズと、ＡＣＫフラグの組み合わせに応じた情報をパケット情報記憶領域に記憶させてもよい。例えば、確認応答番号、広告ウィンドウサイズおよびＡＣＫフラグの組と、ビット列中のビット位置との対応関係を予め定めておき、受信したパケットの確認応答番号の値がＳ、広告ウィンドウサイズの値がＴ、ＡＣＫフラグの値がＵであれば、Ｓ，Ｔ，Ｕの組み合わせに応じたビット位置に「１」を格納してもよい。また、Ｓ，Ｔ，Ｕの組み合わせのハッシュ値をハッシュ関数を用いて求め、そのハッシュ値に応じたビット位置に「１」を格納してもよい。このとき、ブルームフィルタ、スペースコードブルームフィルタ、またはマルチレゾリューションスペースコードブルームフィルタを適用してもよい。あるいは、受信したパケット毎の確認応答番号、広告ウィンドウサイズおよびＡＣＫフラグの組を、配列として記憶させてもよい。
【００５８】
この場合、パケット同士で、確認応答番号が一致していたとしても、他の情報（上記の例では広告ウィンドウサイズ、ＡＣＫフラグ）が一致していなければ、複数のパケット情報記憶領域に共通に記憶されることにならない。
【００５９】
また、情報書込手段２は、同様に、広告ウィンドウサイズ、ＡＣＫフラグ、送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤのいずれか一つ以上と、確認応答番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させてもよい。
【００６０】
上記の実施形態では、フロー毎に、複数のパケット情報記憶領域を用いる場合を説明したが、ポート毎や、端末毎に複数のパケット情報記憶領域を用いてもよい。この場合には、そのポートを通過したフロー群全体や、端末で送受信されるパケットのフロー群全体でのパケットロスに頻度が得られる。ただし、この場合、フローが異なっていても、パケットの確認応答番号が一致する場合があり、パケットの確認応答番号と、フローを示す情報との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる。
【００６１】
例えば、送信端末および受信端末の組み合わせ毎に通信品質を計測する場合、送信端末となる端末のアドレスおよび受信端末となる端末のアドレスの組み合わせ毎に、複数のパケット情報記憶領域を用意しておく。そして、情報書込手段２は、例えば、パケット中の確認応答番号、広告ウィンドウサイズ、フラグ情報、送信ポート番号、受信ポート番号、プロトコルＩＤの組に応じた情報をパケット情報記憶領域に記憶させる。また、例えば、送信端末毎に通信品質を計測する場合、送信端末となる端末のアドレス毎に複数のパケット情報記憶領域を用意しておく。そして、情報書込手段２は、例えば、パケット中の確認応答番号、広告ウィンドウサイズ、フラグ情報、送信ポート番号、受信ポート番号、プロトコルＩＤ、受信アドレスの組に応じた情報をパケット情報記憶領域に記憶させる。また、例えば、ポート毎に通信品質を計測する場合、送信ポート番号および受信ポート番号の組み合わせ毎に、複数のパケット情報記憶領域を用意しておく。そして、情報書込手段２は、例えば、パケット中の確認応答番号、広告ウィンドウサイズ、フラグ情報、送信ポート番号、受信ポート番号、送信アドレス、受信アドレスの組に応じた情報をパケット情報記憶領域に記憶させる。
【００６２】
また、上記の実施形態では、フロー識別手段１と、情報書込手段２と、パケット情報保持手段３と、情報読込手段６と、計数手段７とが一つの装置に備えられている場合を示したが、各手段が同一の装置に備えられていなくてもよい。例えば、パケット受信毎に処理を実行する部分と、複数のパケット情報記憶領域に記憶された情報を読み込んで計数処理を実行する部分とが別々の装置で実現されていてもよい。図８は、このような実施形態の例を示すブロック図である。図８に示す例では、パケットロス頻度計測システムが情報登録装置７１と、情報計数装置７２とを備える構成である。情報登録装置７１と、情報計数装置７２とは、例えば通信ネットワークを介して接続される。情報登録手段７１は、フロー識別手段１と、情報書込手段２と、パケット情報保持手段３とを備える。また、情報計数装置７２は、情報読込手段６と、計数手段７とを備える。図２と同一の符号を付した構成要素の動作は、上記の実施形態と同様であり、説明を省略する。
【００６３】
情報登録手段７１は、例えば、図１に示す各装置２１〜２５に適用され、情報計数装置２５は、例えば、図１に示すサーバ３１に適用される。
【００６４】
また、図１に示す各装置２１〜２５にフロー時期別手段１が備えられ、図１に示すサーバ３１に情報書込手段２、パケット情報保持手段３、情報読込手段６、計数手段７が備えられる構成であってもよい。この場合、各装置２１〜２５のフロー時期別手段１は、受信したパケットのフローを識別した後、そのパケットをサーバ３１に送信する。
【００６５】
パケット情報保持手段３が通信ネットワーク内において分散データベースとして構成されていてもよい。通信ネットワーク内の個々のコンピュータが、一つのフローに対応する個々のカウンタとしての役割をはたしてもよい。例えば、図８に示す第１カウンタ４としての役割を担うコンピュータＡと、第２カウンタ５としての役割を担うコンピュータＢが情報登録装置７１および情報計数装置７２（図８参照）と接続されていてもよい。情報書込手段は、コンピュータＡ，Ｂのうちのいずれかを選択し、確認応答番号等に応じた情報を選択したコンピュータに送信して、そのコンピュータに記憶させればよい。情報計数装置７２は、その各コンピュータから情報を受信して、共通に記憶されていた情報を計数すればよい。
【００６６】
図９は、本発明の他の実施形態を示すブロック図である。図９に示す実施形態では、パケットロス頻度から、パケットロスの回数を推定する。図９に示すパケットロス頻度計測システムは、フロー識別手段１と、情報書込手段２と、パケット情報保持手段３と、情報読込手段６と、計数手段７と、Ｅ２Ｅロス計算手段８とを備える。フロー識別手段１と、情報書込手段２と、パケット情報保持手段３と、情報読込手段６と、計数手段７は、図２に示す実施形態と同様であり、説明を省略する。
【００６７】
ステップＢ２（図６参照）において、例えばＡＮＤ計算によって得たビット列中の「１」の数は、パケットロスの頻度を表す値であり、「１」の数が多い程、パケットロスの回数が多いということができる。ただし、そのビット列中の「１」の計数結果が、必ずパケットロスの発生回数を表しているとは限らない。例えば、情報書込手段２がランダムにカウンタを選択する方式を採用していて、同一の確認応答番号のパケットを複数回受信したときに、同じカウンタを選択することもある。すると、一方のカウンタでは確認応答番号に応じたビット位置に「１」が格納されず、ＡＮＤ計算によって得られるビット列中に「１」として出現しなくなる。
【００６８】
Ｅ２Ｅロス計算手段８は、パケットロスが１回生じたときに、情報書込手段２が同一フローに対応する複数のカウンタのうち共通数以上のカウンタに共通の情報を記憶させる確率を用いて、計数手段７が計数した計数結果を補正し、パケットロスの発生回数を推定する。以下、パケットロスが１回生じたときに、情報書込手段２が同一フローの複数のカウンタのうち共通数以上のカウンタに共通の情報を記憶させる確率を出現確率と記す。出現確率をＫとすると、Ｅ２Ｅロス計算手段８は、計数手段７が計数した計数結果を出現確率Ｋで除算し、その除算結果をパケットロスの発生回数の推定値とすればよい。Ｅ２Ｅロス計算手段８は、パケットロスの発生回数の推定値をサーバ３１（図１参照）に送信して、サーバ３１が個々のパケットロス頻度計測システム（図１に示す各装置２１〜２５）で推定されたパケットロスの発生回数を記憶してもよい。
【００６９】
出現確率は、以下に示す４つの要素のうち、１つ以上の要素の組み合わせによって決まる。第１の要素は、情報書込手段２が複数のカウンタ（一つのフローに対応する複数のカウンタ）の中から一つのカウンタを選択するアルゴリズムである。第２の要素は、一つのフローに対応するカウンタの数である。第３の要素は、共通数である。共通数は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じて情報書込手段２がカウンタに記憶させた個々の情報が何個以上のカウンタに共通に記憶された場合に計数手段７が計数対象とするかという計数条件である。第４の要素は、確認応答番号の送信態様を規定する通信プロトコルの種類である。
【００７０】
例えば、第１の要素が、フロー毎のラウンドロビン方式であるとする。そして、第２の要素が、数値Ｘであり、第３の要素も、数値Ｘであるとする。すなわち、第２の要素と第３の要素の値が一致しているとする。この場合、第４の要素によって例外が生じることがあるが、一般的に、計数手段７の計数結果（共通数分のカウンタに共通に記憶されている情報の数、図４に示す例では３個）は、そのままパケットロスの回数となる。計数手段７の計数結果がそのままパケットロス回数とはならない場合に、Ｅ２Ｅロス計算手段８が最ゆう推定等を行って、パケットロス回数を推定すればよい。以下、Ｅ２Ｅロス計算手段８がパケットロス回数を推定する例を挙げる。
【００７１】
第１の要素が、一つのフローに対応する複数のカウンタの中からランダムに一つのカウンタを選択する方式であるとする。また、第２の要素が２であり、第３の要素が２であるとする。すなわち、一フロー当たりのカウンタ数は２であり、共通数も２である。また、第４の要素は、受信端末側はパケットロスを検出すると送信端末側に同じ確認応答番号を２個送信するアルゴリズムであるとする。この場合、データの受信端末側から送信端末側に同一の確認応答番号が送付される回数は２回のみである。この同一の確認応答番号を含む２個のパケットをそれぞれ受信して、２個のカウンタそれぞれに確認応答番号に応じた共通の情報を記憶させれば、計数手段７はその情報を１個の情報として計数することができる。本例では、カウンタ選択アルゴリズムがランダム方式であるため、２個のカウンタにそれぞれ共通の情報が記憶されている確率は１／２である。具体的に説明すると、１回目の確認応答番号を受信したときに、確認応答番号に応じた情報を第１カウンタに記憶させる確率は１／２であり、第２カウンタに記憶させる確率は１／２である。２回目の確認応答番号を受信したときに、確認応答番号に応じた情報を第１カウンタに記憶させる確率は１／２であり、第２カウンタに記憶させる確率は１／２である。このため、この確認応答番号に応じた情報が第１カウンタおよび第２カウンタに記憶されて、ＡＮＤ計算の結果「１」となる確率（出現確率）は１／２であり、第１カウンタに重複して記憶されＡＮＤ計算の結果が「０」となる確率は１／４であり、第２カウンタに重複して記憶されＡＮＤ計算の結果が「０」となる確率は１／４である。よって、Ｅ２Ｅロス計算手段８は、計数手段７の計数結果を出現確率１／２で除算し、その除算結果をパケットロスの発生回数の推定とする。例えば、計数手段７の計数結果が５０であれば、５０／（１／２）を計算し、パケットロスの発生回数を１００と推定する。
【００７２】
また、例えば、第１の要素が、第１カウンタの選択確率が１／３であり、第２カウンタの選択確率が２／３となるようにカウンタを選択する方式であるとする。また、第２の要素が２であり、第３の要素が２であるとする。第４の要素は、受信端末側はパケットロスを検出すると送信端末側に同じ確認応答番号を２個送信するアルゴリズムであるとする。この場合、パケットロスが１回生じたことにより、２個のカウンタにそれぞれ共通の情報が記憶される確率は４／９である。具体的に説明すると、１回目の確認応答番号を受信したときに、確認応答番号に応じた情報を第１カウンタに記憶させる確率は１／３であり、第２カウンタに記憶させる確率は２／３である。２回目の確認応答番号を受信したときに、確認応答番号に応じた情報を第１カウンタに記憶させる確率は１／３であり、第２カウンタに記憶させる確率は１／３である。このため、この確認応答番号に応じた情報が第１カウンタおよび第２カウンタに記憶されて、ＡＮＤ計算の結果「１」となる確率（出現確率）は４／９であり、第１カウンタに重複して記憶されＡＮＤ計算の結果が「０」となる確率は１／９であり、第２カウンタに重複して記憶されＡＮＤ計算の結果が「０」となる確率は４／９である。よって、Ｅ２Ｅロス計算手段８は、計数手段７の計数結果を出現確率４／９で除算し、その除算結果をパケットロスの発生回数の推定とする。例えば、計数手段７の計数結果が５０であれば、５０／（４／９）を計算し、パケットロスの発生回数を１１２．５回と推定する。
【００７３】
Ｅ２Ｅロス計算手段８が出現回数を計算により求めてもよい。また、各要素の内容の組み合わせに応じた出現確率は、予め求めておき、Ｅ２Ｅロス計算手段８が、その出現確率を用いてパケットロスの発生回数を推定するように定めておけばよい。あるいは、第１から第４の要素までの少なくとも一つ以上の要素の組み合わせ、その要素の内容に応じた出現確率をそれぞれ求めておき、要素の組と出現確率とを対応づけた情報を記憶させた確率情報記憶手段（図示せず）をパケットロス頻度計測システムに設けておいてもよい。そして、Ｅ２Ｅロス計算手段８は、パケットロス頻度計測システム自身におけるカウンタの選択アルゴリズム、一つのフローに対応するカウンタの数、共通数、端末間の通信アルゴリズムに対応する出現確率を確率情報記憶手段に記憶された情報の中から検索し、その出現確率を用いてパケットロスの発生回数を推定してもよい。
【００７４】
また、要素の内容に応じた出現確率を正確に計算することができない場合には、その要素の内容が示す条件のもとで、パケットロスの回数と、計数手段７の計数対象となるデータの出現個数との関係を統計的に求めればよい。
【００７５】
ただし、第４の要素であるプロトコルのアルゴリズムによっては、第２の要素と第３の要素の数値が一致していないことによる観測確率の変化はごくわずかであり、計数手段７の計数結果に対して、Ｅ２Ｅロス計算手段８が確率的な補正を行わなくてもほとんど問題ない場合もある。例えば、第４の要素がＴＣＰである場合、第３の要素の数値は３となる。このとき、パケットロス時に発生する確認応答番号の重複回数は第３の要素「３」と比較して大きい。例えば、ネットワーク状況によっては、同じ確認応答番号が１０個や２０個連続することもある。このため、第２の要素が「２」であったり、第１の要素が装置毎のラウンドロビン方式やランダム方式であったりしても、パケットロス発生時には全てのブルームフィルタの該当ビットに「１」が格納されている可能性が高い。そのような場合には、Ｅ２Ｅロス計算手段８が補正を行わずに、計数手段７の計数結果をそのままパケットロスの発生回数としてもよい。
【００７６】
Ｅ２Ｅロス計算手段８以外の構成要素に関しては、既に説明した実施形態と同様である。
【００７７】
また、パケットロス頻度計測システムは、パケットロスの数から、パケットのロス率を推定してもよい。例えば、パケットロス頻度計測システムは、スループットを算出して、スループットをパケットロス数で除算して、パケットのロス率を計算する手段を備えていてもよい。
【００７８】
次に、本発明の概要について説明する。図１０は、本発明の概要を示すブロック図である。本発明のパケットロス頻度計測システムは、パケット情報記憶手段１１２と、パケット情報登録手段１１１と、計数手段１１４とを備える。
【００７９】
パケット情報記憶手段１１２（例えば、パケット情報保持手段３）は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域１１３（例えば、カウンタ４，５）を複数有する。
【００８０】
パケット情報登録手段１１１（例えば、情報書込手段２）は、パケット受信時に、複数のパケット情報記憶領域１１３のうちの一つを選択し、選択したパケット情報記憶領域１１３に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させる。
【００８１】
計数手段１１４は、予め定められた数（例えば、共通数）以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する。
【００８２】
そのような構成により、パケットロスの頻度を低い処理コストで計測することができる。
【００８３】
また、上記の実施形態には、パケット内の送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤ、パケットロス頻度計測システムのポートの番号のうちの少なくとも一部の項目の組み合わせからパケットをグループに分類する分類手段（例えば、フロー識別手段１）を備え、パケット情報登録手段１１１が、選択したパケット情報記憶領域１１３に受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させる処理をグループ単位で行う構成が開示されている。そのような構成によれば、フロー毎に、パケットロスの頻度を計測することができる。
【００８４】
また、上記の実施形態には、パケット情報登録手段１１１が、選択したパケット情報記憶領域１１３にパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報をさせるときに、値に応じた情報として、所定ビット数のビット列におけるその値に応じたビット位置に１を記憶させる構成が開示されている。
【００８５】
また、上記の実施形態には、パケット情報登録手段１１１が、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、選択したパケット情報記憶領域１１３に配列として記憶させる構成が開示されている。
【００８６】
また、上記の実施形態には、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、値をハッシュ関数を用いて変換することによって求める構成が開示されている。
【００８７】
また、上記の実施形態には、パケット情報登録手段１１１が、ブルームフィルタまたはスペースコードブルームフィルタまたはマルチレゾリューションスペースコードブルームフィルタのアルゴリズムに従って、パケット内の少なくとも確認応答番号を含むフィールドの値をハッシュ関数を用いて変換する構成が開示されている。
【００８８】
また、上記の実施形態には、ケット情報登録手段が、フラグ情報、広告ウィンドウサイズ、送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤのいずれか一つ以上と、確認応答番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる構成が開示されている。
【００８９】
また、上記の実施形態には、パケット情報登録手段１１１が、パケット内の少なくとも確認応答番号を含むフィールドの値とパケットロス頻度計測システムのポートの番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させる構成が開示されている。
【００９０】
また、上記の実施形態には、パケット情報登録手段１１１が、ランダムに選択する方式、ラウンドロビン、あるいは、個々のパケット情報記憶領域に予め定められた選択確率に従ってパケット情報記憶領域のいずれかを選択する方式のいずれかの方式で、パケット情報記憶領域を選択する構成が開示されている。
【００９１】
図１１は、本発明の情報登録装置の最小の構成例を示すブロック図である。本発明の情報登録装置は、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段１１１（例えば、情報書込手段２）を備える。また、上記の実施形態には、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域（例えば、カウンタ４，５）を複数有するパケット情報記憶手段（例えば、パケット情報保持手段３）を備える情報登録装置の構成も開示されている。
【００９２】
図１２は、本発明の情報計数装置の最小の構成例を示すブロック図である。本発明の情報計数は、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域（例えば、カウンタ４，５）に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段１１４（例えば、計数手段７）を備える。
【００９３】
なお、上記の実施形態では、以下の（１）〜（１０）に示すようなパケットロス頻度計測システムの特徴的構成が示されている。また、以下の（１１）〜（１３）に示すような情報登録装置の特徴的構成が示されている。また、以下の（１４）〜（１５）に示すような情報計数装置の特徴的構成が示されている。
【００９４】
（１）パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域を複数有するパケット情報記憶部と、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録部と、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数部とを備えることを特徴とするパケットロス頻度計測システム。
【００９５】
（２）パケット内の送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤ、当該パケットロス頻度計測システムのポートの番号のうちの少なくとも一部の項目の組み合わせからパケットをグループに分類する分類部を備え、パケット情報登録部が、選択したパケット情報記憶領域に受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させる処理をグループ単位で行うパケットロス頻度計測システム。
【００９６】
（３）パケット情報登録部が、選択したパケット情報記憶領域にパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるときに、その値に応じた情報として、所定ビット数のビット列におけるその値に応じたビット位置に１を記憶させるパケットロス頻度計測システム。
【００９７】
（４）パケット情報登録部が、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、選択したパケット情報記憶領域に配列として記憶させるパケットロス頻度計測システム。
【００９８】
（５）パケット情報登録部が、パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を、当該値をハッシュ関数を用いて変換することによって求めるパケットロス頻度計測システム。
【００９９】
（６）パケット情報登録部が、ブルームフィルタまたはスペースコードブルームフィルタまたはマルチレゾリューションスペースコードブルームフィルタのアルゴリズムに従って、パケット内の少なくとも確認応答番号を含むフィールドの値をハッシュ関数を用いて変換するパケットロス頻度計測システム。
【０１００】
（７）パケット情報登録部が、フラグ情報、広告ウィンドウサイズ、送信アドレス、受信アドレス、送信ポート番号、受信ポート番号、プロトコルＩＤのいずれか一つ以上と、確認応答番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させるパケットロス頻度計測システム。
【０１０１】
（８）パケット情報登録部が、パケット内の少なくとも確認応答番号を含むフィールドの値と当該パケットロス頻度計測システムのポートの番号との組み合わせに応じた情報を、選択したパケット情報記憶領域に記憶させるパケットロス頻度計測システム。
【０１０２】
（９）パケット情報登録部が、ランダムに選択する方式、ラウンドロビン、あるいは、個々のパケット情報記憶領域に予め定められた選択確率に従ってパケット情報記憶領域のいずれかを選択する方式のいずれかの方式で、パケット情報記憶領域を選択するパケットロス頻度計測システム。
【０１０３】
（１０）パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域を複数有するパケット情報記憶手段と、パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段と、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段とを備えることを特徴とするパケットロス頻度計測システム。
【０１０４】
（１１）パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録部を備えることを特徴とする情報登録装置。
【０１０５】
（１２）パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶するパケット情報記憶領域を複数有するパケット情報記憶部を備える情報登録装置。
【０１０６】
（１３）パケット受信時に、複数のパケット情報記憶領域のうちの一つを選択し、選択したパケット情報記憶領域に、受信したパケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶させるパケット情報登録手段を備えることを特徴とする情報登録装置。
【０１０７】
（１４）パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数部を備えることを特徴とする情報計数装置。
【０１０８】
（１５）パケット内の少なくとも確認応答番号を含むフィールドの値に応じた情報を記憶する複数のパケット情報記憶領域に記憶された情報を参照し、予め定められた数以上のパケット情報記憶領域に共通に記憶されている情報の数を計数する計数手段を備えることを特徴とする情報計数装置。
【０１０９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１１０】
この出願は、２００８年１０月２４日に出願された日本特許出願２００８−２７３７５０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用の可能性】
【０１１１】
本発明は、パケットロスの頻度を計測するパケットロス頻度計測システムに好適に適用される。
【符号の説明】
【０１１２】
１  フロー識別手段
２  情報書込手段
３  パケット情報保持手段
４，５  パケット情報記憶領域
６  情報読込手段
７  計数手段
【図１】
2010047044.tif 000003
【図２】
2010047044.tif 000004
【図３】
2010047044.tif 000005
【図４】
2010047044.tif 000006
【図５】
2010047044.tif 000007
【図６】
2010047044.tif 000008
【図７】
2010047044.tif 000009
【図８】
2010047044.tif 000010
【図９】
2010047044.tif 000011
【図１０】
2010047044.tif 000012
【図１１】
2010047044.tif 000013
【図１２】
2010047044.tif 000014
【図１３】
2010047044.tif 000015
【国際調査報告】
2010047044.tif 000016
2010047044.tif 000017
2010047044.tif 000018