以下、本発明の実施形態を図面を参照して� ��明する。
 図1は、パケットロス頻度計測システムの配 置例を示す説明図である。図1に示す例では� �各端末11~15がそれぞれパケットを送受信する ことにより通信を行う。そして、通信ネット ワーク内における各端末間の通信経路上に、 パケットロス頻度計測システムが配置される 。図1に示す例では、個々の装置21~25がそれぞ れパケットロス頻度計測システムに該当する 。各装置21~25は、それぞれパケットロスの頻� ��(すなわち、パケットロスの発生頻度)を計� �する。また、図1に示す例では、各装置21~25� �、計測したパケットロスの頻度をサーバ31に 出力する。サーバ31は、各装置21~25における� �ケットロスの頻度を管理する。

 また、各装置21~25は、それぞれパケット� �フロー毎にパケットロスの発生頻度を計測� �る。例えば、図1に示す装置25は、端末11,12の 通信経路上に位置し、端末15,12の通信経路上� ��も位置し、端末13,14の通信経路上にも位置� �る。従って、端末25は、端末11から端末12へ� �フロー(以下、フローAと記す)のパケットも� �端末15から端末12へのフロー(以下、フローB� �記す)のパケットも、端末13から端末14へのフ ロー(以下、フローCと記す)のパケットも通過 させる。そして、端末25は、フローA,B,C等の� �パケットのフロー毎にパケットロスの頻度� �計算する。

 また、本発明のパケットロス頻度計測シ� ��テムは、データの受信側の端末がデータの� ��信側の端末に向けて、受信側の端末にどの� ��ータまで届いているかを確認する情報(確認 応答番号)を送るプロトコルを対象としてい� �。このようなプロトコルの代表例としてTCP(T ransmission Control Protocol )が挙げられるが、本 発明を適用可能なプロトコルはTCPに限定され ない。例えば、SCTP(Stream Control Transmission Pro tocol)に本発明が適用されてもよい。また、UDP (User Datagram Protocol)であっても、受信側の端� ��にどのデータまで届いているかを示すシー� ��ンス番号をアプリケーション層でペイロー� ��に追加する独自のプロトコルが定められて� ��れば、本発明を適用することができる。

 図1に示す装置21~25は、通信ネットワーク� ��に存在するルータやスイッチ等のノードで� ��ってもよいし、TAPや装置のミラーポート等� ��ら入力された情報をもとに解析を行う装置� ��あってもよい。

 図2は、本発明のパケットロス頻度計測シ ステムの実施形態を示すブロック図である。 図2では、パケットロス頻度計測システムに� �当する装置21のブロック図として図示してい るが、図1における各装置21~25は、同様の構成 である。本発明のパケットロス頻度計測シス テムは、フロー識別手段1と、情報書込手段2� ��、パケット情報保持手段3と、情報読込手段 6と、計数手段7とを備える。

 フロー識別手段1は、パケットロス頻度計 測システムを通過するパケット51を受信し、� ��のパケット51のフローを識別する。フロー� �別手段1は、受信したパケットの特定のフィ� ��ルドが同一であるパケット群が同一フロー� ��あるとみなして、フロー毎にパケットを分� ��する。例えば、送信IPアドレス、受信IPアド レス、送信ポート番号、受信ポート番号、送 信MACアドレス、受信MACアドレス、プロトコル ID(プロトコルの識別情報)のいずれかの一つ� �上の項目の組を予め定めておき、その組の� �項目が複数のパケットにおいて同一であれ� �、フロー識別手段1は、その複数のパケット� ��同一のフローであるとみなす。ここでは、� ��信IPアドレス、受信IPアドレス、送信ポート 番号、受信ポート番号、送信MACアドレス、受 信MACアドレス、プロトコルIDを例示したが、� ��のほかに、パケットロス頻度計測システム� ��ポートの番号を、パケットのフローを特定� ��るための項目の一つとして用いてもよい。� ��なわち、フロー識別手段1は、パケット中の 、送信アドレス、受信アドレス、送信ポート 番号、受信ポート番号、プロトコルID、パケ� ��トロス頻度計測システムのポートの番号の� ��ちの少なくとも一部の項目の組を定め、そ� ��組の項目が複数のパケットで同一ならば、� ��の複数のパケットを一つのグループとして� ��類すればよい。なお、パケットロス頻度計� ��システムのポートの番号とは、パケットロ� ��頻度計測システムとしてパケットを送受信� ��る装置における複数のポートのうち、パケ� ��トを受信したポート、およびそのパケット� ��次のノードに送信したポートの番号である� ��

 なお、図2では、実線で示した各パケット が同じフローであり、破線で示した各パケッ トが他のフローに属している。

 パケット情報保持手段3は、パケット内の 少なくとも確認応答番号を含むフィールドの 値に応じた情報を記憶するパケット情報記憶 領域4,5を、フロー毎に複数有する記憶装置で ある。ここでは、パケット内の少なくとも確 認応答番号を含むフィールドの値に応じた情 報を記憶するパケット情報記憶領域4,5が、予 め定められたビット長のビット列を記憶する 記憶領域である場合を例にして説明する。ま た、この場合、パケット情報記憶領域4,5をカ ウンタと記す。ここでは、パケットロス頻度 計測システムが受信したパケット内の確認応 答番号に応じた値をカウンタ4,5に記憶させる 場合を例にする。

 ここでは、一つのフローに対して二つの� ��ウンタ4,5を用いる場合を例にして説明する� ��、一つのフローに対して用いられるカウン� ��(パケット情報記憶領域)の数は二つに限定� �れず複数であればよい。以下、二つのカウ� �タのうち一方を第1カウンタ4と記し、他方を 第2カウンタ5と記す。

 情報書込手段2は、フロー識別手段1がパ� �ットを受信して、そのパケットをフロー毎� �分類した後に、そのパケットが分類された� �ループに対応する複数のカウンタ(本例では� ��つのカウンタ4,5)のうちの一つのカウンタを 選択し、選択したカウンタに、受信したパケ ットの確認応答番号に応じた情報を記憶させ る。本実施形態では、第1カウンタ4および第2 カウンタ5が、予め定められたビット長のビ� �ト列を記憶する記憶領域である。そして、� �報書込手段2が、受信したパケットの確認応� ��番号に応じた情報として、予め定められた� ��ット長のビット列における確認応答番号に� ��じたビット位置に1を記憶させる場合を例に して説明する。

 情報書込手段2が複数のカウンタのうちの 一つを選択する方式は、例えば、ランダムに カウンタを選択する方式であってもよい。ラ ンダムにカウンタを選択する場合、乱数を利 用してもよい。例えば、各カウンタ4,5に均等 に乱数の値を割り当てておき、カウンタ選択 時に乱数を発生させ、その乱数の値に対応す るカウンタを選択してもよい。また、情報書 込手段2は、各カウンタを順番に選択してい� �ラウンドロビン方式でカウンタを選択して� �よい。例えば、受信したパケット毎に、第1� ��ウンタ4、第2カウンタ5、第1カウンタ4、第2� ��ウンタ5、・・・という順番にカウンタを選 択してもよい。また、各カウンタに対して、 選択される確率の重みづけを予め行っておき 、その確率に従ってカウンタを選択してもよ い。例えば、第1カウンタ4が選択される選択� ��率をP、第2カウンタ5が選択される選択確率� ��1-Pとして予め定め、その選択確率に従って� ��いずれかのカウンタを選択してもよい。

 情報書込手段2は、選択したカウンタに対 して、予め定められたビット長のビット列に おける確認応答番号に応じたビット位置に1� �記憶させる。

 確認応答番号と、ビット列内のビット位� ��との対応関係を定める方法は、例えば、単� ��に、各確認応答番号と、ビット列内のビッ� ��位置とを直接対応づける方法であってもよ� ��。すなわち、ビット列内の各ビット位置に� ��認応答番号を直接割り当てておき、パケッ� ��受信時に、情報書込手段2は、そのパケット の確認応答番号が割り当てられているビット 位置に「1」を記憶させてもよい。

 また、予めハッシュ関数を定めておき、� ��のハッシュ関数を用いて得られるハッシュ� ��と、ビット列内のビット位置とを対応づけ� ��方法であってもよい。この場合、ハッシュ� ��数を用いて得られる各ハッシュ値と、ビッ� ��列内の各ビット位置とを対応づけておき、� ��報書込手段2は、受信したパケットの確認応 答番号のハッシュ値をそのハッシュ関数を用 いて計算し、計算によって得られたハッシュ 値に対応するビット位置に「1」を記憶させ� �もよい。ハッシュ関数を用いて計算した確� �応答番号のハッシュ値に対応する位置に「1� ��を記憶させるアルゴリズムとして、例えば� ��ブルームフィルタ(Bloom Filter)や、その応用� ��あるスペースコードブルームフィルタ(Space- Code Bloom Filter)やマルチレゾリューションス� ��ースコードブルームフィルタ(Multi-Resolution  Space-Code Bloom Filter)がある。情報書込手段2は 、ビット列における確認応答番号に応じたビ ット位置に1を記憶させる処理をブルームフ� �ルタまたはスペースコードブルームフィル� �またはマルチレゾリューションスペースコ� �ドブルームフィルタに従って行ってもよい� �なお、ハッシュ値は、ハッシュ関数による� �認応答番号の変換結果であるということが� �きる。

 図3は、各カウンタ4,5に記憶される予め定 められたビット長のビット列の例を示す。情 報書込手段2は、受信したパケットの確認応� �番号のハッシュ値を、例えば、ブルームフ� �ルタに従って計算する。また、情報書込手� �2が、第1カウンタ4を選択していれば、第1カ� ��ンタ4のビット列における、そのハッシュ値 に対応するビット位置に「1」を格納する。� �た、第2カウンタ5を選択していれば、第2カ� �ンタ5のビット列における、そのハッシュ値� ��対応するビット位置に「1」を格納する。

 また、予め定めておいた固定値で確認応� ��番号を除算したときの余りと、ビット列内� ��ビット位置とを対応づける方法であっても� ��い。この場合、固定値による確認応答番号� ��除算で得られる余りと、ビット列内の各ビ� ��ト位置とを対応づけておき、パケット受信� ��に、情報書込手段2は、そのパケットの確認 応答番号を固定値で除算して余りを求め、そ の余りに対応するビット位置に「1」を記憶� �せてもよい。

 フロー識別手段1および情報書込手段2は� �個々のパケットを受信する毎に上記の処理� �行う。すなわち、フロー識別手段1は、受信� ��たパケット毎に、パケットのフローを識別� ��る。また、情報書込手段2は、受信したパケ ット毎に、パケットのフローに対応する複数 のカウンタから一つのカウンタを選択して、 パケットの確認応答番号に応じた情報をその カウンタに記憶させる処理を行う。

 一方、以下に示す情報読込手段6および計 数手段7は、パケットを受信する毎に処理を� �行する必要はない。情報読込手段6は、パケ� ��トの受信とは関連なく、各カウンタからビ� ��ト列を読み込む処理を実行し、情報読込手� ��6のビット列読込処理に続いて計数手段7が� �理を行う。

 情報読込手段6は、個々のフローに対応す る複数のカウンタに記憶されたビット列を読 み込み、計数手段7に渡す。上記のように、� �報読込手段6は、パケットの到着とは関連な� ��この処理を行ってよい。例えば、情報読込� ��段6は、定期的にカウンタのビット列の読み 込みを行ってもよい。あるいは、外部のシス テムからの命令や、外部のシステムにおける イベントをトリガにして、不定期にビット列 の読み込みを行ってもよい。

 計数手段7は、一つのフローに対応する複 数のカウンタのうち、予め定められた数以上 のカウンタに共通に記憶されている情報の数 を計数する。以下、この「予め定められた数 」を共通数と記す。また、共通数は、一つの フローに対応する複数のカウンタの数をNと� �たときに、2以上N以下となる値から定められ る。本例では、一つのフローに対応するカウ ンタは2個であり、共通数は2である。従って� ��本例では、計数手段7は、2個のカウンタに� �通に記憶されている情報の数を計数する。� �た、本例では、確認応答情報に応じた情報� �、その確認応答情報に応じたビット位置に� �1」として格納される。よって、各カウンタ� ��共通に記憶される情報とは、同じビット位� ��に格納された「1」である。よって、計数手 段7は、第1カウンタ4と第2カウンタ5のビット� ��のAND(論理積)計算を行って、その結果得ら� �るビット列中の「1」の数を計数すればよい� ��

 図4は、計数手段7の処理を示す説明図で� �る。例えば、第1カウンタ4がビット列61(図4� �照)を記憶し、第2カウンタ5がビット列62を記 憶していて、情報読込手段6がこのビット列61 ,62を読み込んだとする。計数手段7は、この� �ット列61,62のAND計算を行い、図4に示すビッ� �列63を得る。そして、計数手段7は、AND計算� �よって得たビット列63中の「1」の数を計数� �る。図4に示す例において、計数結果は3とな る。

 パケットロスが生じなければ、同一フロ� ��において確認応答番号が重複するパケット� ��送信されないため、ある確認応答番号のパ� ��ットは計測地点を一度しか通過しない。そ� ��結果、その確認応答番号に応じたビット位� ��の「1」は、二つのカウンタ4,5のうちの一つ にしか記憶されず、第1カウンタ4と第2カウン タ5のビット列のAND計算の結果、そのビット� �置の値は0となる。一方、パケットロスが生� ��た場合、確認応答番号が同一の複数のパケ� ��トが送信され、その各パケットがパケット� ��ス頻度計測システムを通過すると、各カウ� ��タ4,5の同一のビット位置に「1」が格納され ていく。従って、各カウンタ4,5のビット列の AND計算によって得たビット列中の「1」の数� �、パケットロスの頻度を表す値であり、「1� ��の数が多い程、パケットロスの回数が多い� ��とになる。なお、AND計算によって得たビッ� ��列中の「1」は、共通数以上のカウンタに共 通に記憶された情報の個数ということができ る。

 なお、ここでは、一つのフロー当たりの� ��ウンタが2個であり、共通数を2とした場合� �例に説明したが、既に説明したように、一� �のフロー当たりのカウンタの数は、複数で� �れば2個でなくてもよい。例えば、一つのフ� ��ー当たりのカウンタ数が、3個、4個等であ� �てもよい。また、共通数も2に限定されない� ��一つのフロー当たりのカウンタ数が多いほ� ��、パラレル処理できるパケット数が多くな� ��、パケットロスの頻度を求める処理を高速� ��しやすくなる。

 本実施形態において、フロー識別手段1、 情報書込手段2、情報読込手段6、および計数� ��段7は、例えば、プログラム(パケットロス� �度計測プログラム)に従って動作するCPUによ� ��て実現される。パケットロス頻度計測シス� ��ムが備える記憶装置にプログラムが記憶さ� ��、パケットロス頻度計測システムのCPUがそ� ��プログラムを読み込み、ロー識別手段1、情 報書込手段2、情報読込手段6、および計数手� ��7として動作してもよい。また、各手段がそ れぞれ別々のユニットとして実現されていて もよい。

 次に、動作について説明する。
 図5は、パケット受信時の処理経過の例を示 すフローチャートである。パケットロス頻度 計測システムは端末間で送受信されるパケッ トを受信すると、そのパケットを次のノード に転送する。このとき受信したパケットに関 して、以下の処理を実行する。

 まず、フロー識別手段1は、受信したパケ ットのフローを識別する(ステップA1)。例え� �、フロー識別手段1は、パケットのヘッダに� ��ける送信アドレス、受信アドレス、送信ポ� ��ト番号、受信ポート番号、プロトコルIDか� �、フローを識別するフローIDを特定すればよ い。フロー識別手段1は、パケットロス頻度� �測システムのポートの番号(パケットを受信� ��た自装置のポートおよび、次のノードに向� ��てパケットを送信したポートの番号)も参照 してパケットのフローを識別してもよい。

 次に、書込手段2は、受信したパケットの フローに対応する複数のカウンタの中から一 つのカウンタを選択する(ステップA2)。ここ� �は、図2に示すように、フロー毎に第1カウン タ4および第2カウンタ5が用いられる場合を例 にする。書込手段2がカウンタを選択する態� �は限定されず、例えば、ランダムにカウン� �を選択しても、ラウンドロビン方式でカウ� �タを選択しても、各カウンタ毎に個別に定� �られた選択確率に従ってカウンタを選択し� �もよい。

 ステップA2で第1カウンタ4を選択した場合 、書込手段2は、第1カウンタ4に、受信したパ ケットの確認応答番号に応じた情報を記憶さ せる(ステップA4)。また、ステップA2で第2カ� �ンタ5を選択した場合、書込手段2は、第2カ� �ンタ5に、受信したパケットの確認応答番号� ��応じた情報を記憶させる(ステップA5)。本例 では、ステップA4,A5で、選択したカウンタの� ��ット列における確認応答番号に応じたビッ� ��位置に1を記憶させるものとする。既に説明 したように、確認応答番号とビット位置とを 対応づけておいてもよい。また、確認応答番 号のハッシュ値とビット位置とを対応づけて おいてもよい。ビット列における確認応答番 号に応じたビット位置に1を記憶させる処理� �ブルームフィルタまたはスペースコードブ� �ームフィルタまたはマルチレゾリューショ� �スペースコードブルームフィルタに従って� �ってもよい。

 続いて、パケット受信との関連なしに行� ��情報読込手段6および計数手段7の処理につ� �て説明する。図6は、この処理の経過の例を� ��すフローチャートである。ここでは、定期� ��に図6に示す処理を実行する場合を例にして 説明する。また、情報読込手段6および計数� �段7は、以下の処理をフロー毎に行う。

 情報読込手段6は、個々のフロー毎に、フ ローに対応する複数のカウンタに記憶された 情報(本例では、ビット列)を読み込む(ステッ プB1)。ステップB1の後、計数手段7は、共通数 (本例では2)のカウンタに共通に記憶されてい る情報を計数する(ステップB2)。すなわち、� �こでは、どちらのカウンタでも「1」が格納� ��れたビット位置の数を計数すればよい。計� ��手段7は、情報読込手段6が読み込んだ2つの� ��ット列のAND計算を行い、AND計算の結果とし� ��得たビット列中の「1」の数を計数すればよ い。

 ステップB2の計数結果が、各フローのパ� �ットロス頻度を表している。すなわち、ス� �ップB2の計数結果の値が大きいほど、パケッ トロス発生回数が多いことを表し、計数結果 の値が小さいほど、パケットロス発生回数が 少ないことを表す。

 パケットロス頻度計測システムは、パケ� ��トロス頻度(ステップB2の計数結果)を、例え ば、図1に示すサーバ31に送信してもよい。そ して、サーバ31が各パケットロス頻度計測シ� ��テムから受信したパケットロス頻度を記憶� ��ておいてもよい。

 本例では、一つのフローに対応するカウ� ��タが2つである場合を例示したが、一つのフ ローに対応するカウンタの数は3以上であっ� �もよい。この場合も、計数手段7は、共通数� ��上のカウンタに共通に記憶されている情報� ��計数する。一つのフローに対応するカウン� ��の数と、共通数とが一致していれば、計数� ��段7は、各カウンタのビット列の論理積を求 めて、その結果のビット列に含まれている「 1」の数を計数すればよい。一つのフローに� �応するカウンタよりも共通数が小さければ� �ビット位置毎に、共通数以上のカウンタで� �1」が格納されているかを確認し、共通数以� ��のカウンタで「1」が格納されているビット 位置の数を計数すればよい。

 本発明によれば、情報書込手段2が、複数 のカウンタ(パケット情報記憶領域)の中から� ��つを選択し、そのカウンタに、パケットの� ��認応答番号に応じた情報を記憶させる。そ� ��て、各カウンタに記憶された情報を読み込� ��で、共通数以上のカウンタに共通に記憶さ� ��ている情報の数を計数する。このような構� ��では、パケットを受信したときに、情報書� ��手段2は、カウンタの選択と、そのカウンタ に対する書込を行えばよく、過去に受信した パケットと、新たに受信したパケットとの比 較をする必要がない。よって、パケット受信 時の処理は、ステートレス処理となり、処理 時間や計算量などの処理コストを低減するこ とができる。また、パケットの受信タイミン グとは無関係に各カウンタの値を参照して計 数を行うことができる。従って、計数手段7� �計数を行うときには、情報書込手段2の処理� ��了を待つ必要がなく、情報書込手段2によっ て、計数手段7の処理速度が制限されること� �ない。さらに、カウンタが複数存在してい� �ので、一つのパケットを受信して、選択し� �カウンタに対する書き込み(ステップA3また� �ステップA4)を実行しているときに、同一フ� �ーに属する他のパケットを受信したとして� �、そのパケットに対する処理を実行するこ� �ができるので、処理を高速化することがで� �る。

 上記の実施形態では、パケット情報記憶� ��域(カウンタ)4,5が、予め定められたビット� �のビット列を記憶する記憶領域であり、受� �したパケットの確認応答番号に応じた位置� �「1」を記憶させる場合を例にして説明した� ��受信したパケットの確認応答番号に応じた� ��報を、他の態様でパケット情報記憶領域4,5� ��記憶させてもよい。図7は、パケットの確認 応答番号に応じた情報を配列としてパケット 情報記憶領域に記憶させる例を模式的に示す 説明図である。図7に示す15,37,45,・・・等の� �値は、パケットの確認応答番号に応じた情� �を表している。情報書込手段2は、複数のパ� ��ット情報記憶領域のうちの一つを選択した� ��、選択したパケット情報記憶領域に、確認� ��答番号に応じた情報自体を配列の要素とし� ��記憶させてもよい。ただし、記憶させよう� ��する情報が、選択したパケット情報記憶領� ��に既に記憶されているならば、その情報は� ��憶させなくてよい。

 情報読込手段6は、フロー毎に、各パケッ ト情報記憶領域に記憶された配列を読み込む 。また、計数手段7は、フロー毎に、共通数� �上のパケット情報記憶領域に共通に記憶さ� �た情報の数を計数すればよい。その計数結� �が、各フローのパケットロス頻度を表す。� �えば、一つのフローに対して二つのパケッ� �情報記憶領域が用いられ、共通数が2であり� ��図7に例示する配列が記憶されていたとする 。この場合、計数手段7は、二つの配列に共� �に記憶されている情報は「15」、「45」を計� ��し、計数結果として2を得る。

 また、上記の実施形態では、受信したパ� ��ットの確認応答番号に応じた情報をパケッ� ��情報記憶領域に記憶させる場合を例にして� ��明したが、確認応答番号と他の情報との組� ��合わせに応じた情報をパケット情報記憶領� ��に記憶させてもよい。例えば、TCPのパケッ� ��のパケットロス頻度の計測を行う場合、パ� ��ットのヘッダに含まれる確認応答番号と、� ��告ウィンドウサイズと、ACKフラグの組み合� ��せに応じた情報をパケット情報記憶領域に� ��憶させてもよい。例えば、確認応答番号、� ��告ウィンドウサイズおよびACKフラグの組と� ��ビット列中のビット位置との対応関係を予� ��定めておき、受信したパケットの確認応答� ��号の値がS、広告ウィンドウサイズの値がT� �ACKフラグの値がUであれば、S,T,Uの組み合わ� �に応じたビット位置に「1」を格納してもよ� ��。また、S,T,Uの組み合わせのハッシュ値を� �ッシュ関数を用いて求め、そのハッシュ値� �応じたビット位置に「1」を格納してもよい� ��このとき、ブルームフィルタ、スペースコ� ��ドブルームフィルタ、またはマルチレゾリ� ��ーションスペースコードブルームフィルタ� ��適用してもよい。あるいは、受信したパケ� ��ト毎の確認応答番号、広告ウィンドウサイ� ��およびACKフラグの組を、配列として記憶さ� ��てもよい。

 この場合、パケット同士で、確認応答番� ��が一致していたとしても、他の情報(上記の 例では広告ウィンドウサイズ、ACKフラグ)が� �致していなければ、複数のパケット情報記� �領域に共通に記憶されることにならない。

 また、情報書込手段2は、同様に、広告ウ ィンドウサイズ、ACKフラグ、送信アドレス、 受信アドレス、送信ポート番号、受信ポート 番号、プロトコルIDのいずれか一つ以上と、� ��認応答番号との組み合わせに応じた情報を� ��選択したパケット情報記憶領域に記憶させ� ��もよい。

 上記の実施形態では、フロー毎に、複数� ��パケット情報記憶領域を用いる場合を説明� ��たが、ポート毎や、端末毎に複数のパケッ� ��情報記憶領域を用いてもよい。この場合に� ��、そのポートを通過したフロー群全体や、� ��末で送受信されるパケットのフロー群全体� ��のパケットロスに頻度が得られる。ただし� ��この場合、フローが異なっていても、パケ� ��トの確認応答番号が一致する場合があり、� ��ケットの確認応答番号と、フローを示す情� ��との組み合わせに応じた情報を、選択した� ��ケット情報記憶領域に記憶させる。

 例えば、送信端末および受信端末の組み� ��わせ毎に通信品質を計測する場合、送信端� ��となる端末のアドレスおよび受信端末とな� ��端末のアドレスの組み合わせ毎に、複数の� ��ケット情報記憶領域を用意しておく。そし� ��、情報書込手段2は、例えば、パケット中の 確認応答番号、広告ウィンドウサイズ、フラ グ情報、送信ポート番号、受信ポート番号、 プロトコルIDの組に応じた情報をパケット情� ��記憶領域に記憶させる。また、例えば、送� ��端末毎に通信品質を計測する場合、送信端� ��となる端末のアドレス毎に複数のパケット� ��報記憶領域を用意しておく。そして、情報� ��込手段2は、例えば、パケット中の確認応答 番号、広告ウィンドウサイズ、フラグ情報、 送信ポート番号、受信ポート番号、プロトコ ルID、受信アドレスの組に応じた情報をパケ� ��ト情報記憶領域に記憶させる。また、例え� ��、ポート毎に通信品質を計測する場合、送� ��ポート番号および受信ポート番号の組み合� ��せ毎に、複数のパケット情報記憶領域を用� ��しておく。そして、情報書込手段2は、例え ば、パケット中の確認応答番号、広告ウィン ドウサイズ、フラグ情報、送信ポート番号、 受信ポート番号、送信アドレス、受信アドレ スの組に応じた情報をパケット情報記憶領域 に記憶させる。

 また、上記の実施形態では、フロー識別� ��段1と、情報書込手段2と、パケット情報保� �手段3と、情報読込手段6と、計数手段7とが� �つの装置に備えられている場合を示したが� �各手段が同一の装置に備えられていなくて� �よい。例えば、パケット受信毎に処理を実� �する部分と、複数のパケット情報記憶領域� �記憶された情報を読み込んで計数処理を実� �する部分とが別々の装置で実現されていて� �よい。図8は、このような実施形態の例を示� ��ブロック図である。図8に示す例では、パケ ットロス頻度計測システムが情報登録装置71� ��、情報計数装置72とを備える構成である。� �報登録装置71と、情報計数装置72とは、例え� ��通信ネットワークを介して接続される。情� ��登録手段71は、フロー識別手段1と、情報書� ��手段2と、パケット情報保持手段3とを備え� �。また、情報計数装置72は、情報読込手段6� �、計数手段7とを備える。図2と同一の符号を 付した構成要素の動作は、上記の実施形態と 同様であり、説明を省略する。

 情報登録手段71は、例えば、図1に示す各� ��置21~25に適用され、情報計数装置25は、例え ば、図1に示すサーバ31に適用される。

 また、図1に示す各装置21~25にフロー時期� ��手段1が備えられ、図1に示すサーバ31に情報 書込手段2、パケット情報保持手段3、情報読� ��手段6、計数手段7が備えられる構成であっ� �もよい。この場合、各装置21~25のフロー時期 別手段1は、受信したパケットのフローを識� �した後、そのパケットをサーバ31に送信する 。

 パケット情報保持手段3が通信ネットワー ク内において分散データベースとして構成さ れていてもよい。通信ネットワーク内の個々 のコンピュータが、一つのフローに対応する 個々のカウンタとしての役割をはたしてもよ い。例えば、図8に示す第1カウンタ4としての 役割を担うコンピュータAと、第2カウンタ5と しての役割を担うコンピュータBが情報登録� �置71および情報計数装置72(図8参照)と接続さ� ��ていてもよい。情報書込手段は、コンピュ� ��タA,Bのうちのいずれかを選択し、確認応答� ��号等に応じた情報を選択したコンピュータ� ��送信して、そのコンピュータに記憶させれ� ��よい。情報計数装置72は、その各コンピュ� �タから情報を受信して、共通に記憶されて� �た情報を計数すればよい。

 図9は、本発明の他の実施形態を示すブロ ック図である。図9に示す実施形態では、パ� �ットロス頻度から、パケットロスの回数を� �定する。図9に示すパケットロス頻度計測シ� ��テムは、フロー識別手段1と、情報書込手段 2と、パケット情報保持手段3と、情報読込手� ��6と、計数手段7と、E2Eロス計算手段8とを備� ��る。フロー識別手段1と、情報書込手段2と� �パケット情報保持手段3と、情報読込手段6と 、計数手段7は、図2に示す実施形態と同様で� ��り、説明を省略する。

 ステップB2(図6参照)において、例えばAND� �算によって得たビット列中の「1」の数は、� ��ケットロスの頻度を表す値であり、「1」の 数が多い程、パケットロスの回数が多いとい うことができる。ただし、そのビット列中の 「1」の計数結果が、必ずパケットロスの発� �回数を表しているとは限らない。例えば、� �報書込手段2がランダムにカウンタを選択す� ��方式を採用していて、同一の確認応答番号� ��パケットを複数回受信したときに、同じカ� ��ンタを選択することもある。すると、一方� ��カウンタでは確認応答番号に応じたビット� ��置に「1」が格納されず、AND計算によって得 られるビット列中に「1」として出現しなく� �る。

 E2Eロス計算手段8は、パケットロスが1回� �じたときに、情報書込手段2が同一フローに� ��応する複数のカウンタのうち共通数以上の� ��ウンタに共通の情報を記憶させる確率を用� ��て、計数手段7が計数した計数結果を補正し 、パケットロスの発生回数を推定する。以下 、パケットロスが1回生じたときに、情報書� �手段2が同一フローの複数のカウンタのうち� ��通数以上のカウンタに共通の情報を記憶さ� ��る確率を出現確率と記す。出現確率をKとす ると、E2Eロス計算手段8は、計数手段7が計数� ��た計数結果を出現確率Kで除算し、その除算 結果をパケットロスの発生回数の推定値とす ればよい。E2Eロス計算手段8は、パケットロ� �の発生回数の推定値をサーバ31(図1参照)に送 信して、サーバ31が個々のパケットロス頻度� ��測システム(図1に示す各装置21~25)で推定さ� �たパケットロスの発生回数を記憶してもよ� �。

 出現確率は、以下に示す4つの要素のうち 、1つ以上の要素の組み合わせによって決ま� �。第1の要素は、情報書込手段2が複数のカウ ンタ(一つのフローに対応する複数のカウン� �)の中から一つのカウンタを選択するアルゴ� ��ズムである。第2の要素は、一つのフローに 対応するカウンタの数である。第3の要素は� �共通数である。共通数は、パケット内の少� �くとも確認応答番号を含むフィールドの値� �応じて情報書込手段2がカウンタに記憶させ� ��個々の情報が何個以上のカウンタに共通に� ��憶された場合に計数手段7が計数対象とする かという計数条件である。第4の要素は、確� �応答番号の送信態様を規定する通信プロト� �ルの種類である。

 例えば、第1の要素が、フロー毎のラウン ドロビン方式であるとする。そして、第2の� �素が、数値Xであり、第3の要素も、数値Xで� �るとする。すなわち、第2の要素と第3の要素 の値が一致しているとする。この場合、第4� �要素によって例外が生じることがあるが、� �般的に、計数手段7の計数結果(共通数分のカ ウンタに共通に記憶されている情報の数、図 4に示す例では3個)は、そのままパケットロス の回数となる。計数手段7の計数結果がその� �まパケットロス回数とはならない場合に、E2 Eロス計算手段8が最ゆう推定等を行って、パ� ��ットロス回数を推定すればよい。以下、E2E� ��ス計算手段8がパケットロス回数を推定する 例を挙げる。

 第1の要素が、一つのフローに対応する複 数のカウンタの中からランダムに一つのカウ ンタを選択する方式であるとする。また、第 2の要素が2であり、第3の要素が2であるとす� �。すなわち、一フロー当たりのカウンタ数� �2であり、共通数も2である。また、第4の要� �は、受信端末側はパケットロスを検出する� �送信端末側に同じ確認応答番号を2個送信す� ��アルゴリズムであるとする。この場合、デ� ��タの受信端末側から送信端末側に同一の確� ��応答番号が送付される回数は2回のみである 。この同一の確認応答番号を含む2個のパケ� �トをそれぞれ受信して、2個のカウンタそれ� ��れに確認応答番号に応じた共通の情報を記� ��させれば、計数手段7はその情報を1個の情� �として計数することができる。本例では、� �ウンタ選択アルゴリズムがランダム方式で� �るため、2個のカウンタにそれぞれ共通の情� ��が記憶されている確率は1/2である。具体的� ��説明すると、1回目の確認応答番号を受信し たときに、確認応答番号に応じた情報を第1� �ウンタに記憶させる確率は1/2であり、第2カ� ��ンタに記憶させる確率は1/2である。2回目の 確認応答番号を受信したときに、確認応答番 号に応じた情報を第1カウンタに記憶させる� �率は1/2であり、第2カウンタに記憶させる確� ��は1/2である。このため、この確認応答番号� ��応じた情報が第1カウンタおよび第2カウン� �に記憶されて、AND計算の結果「1」となる確� ��(出現確率)は1/2であり、第1カウンタに重複� ��て記憶されAND計算の結果が「0」となる確率 は1/4であり、第2カウンタに重複して記憶さ� �AND計算の結果が「0」となる確率は1/4である� ��よって、E2Eロス計算手段8は、計数手段7の� �数結果を出現確率1/2で除算し、その除算結� �をパケットロスの発生回数の推定とする。� �えば、計数手段7の計数結果が50であれば、50 /(1/2)を計算し、パケットロスの発生回数を100 と推定する。

 また、例えば、第1の要素が、第1カウン� �の選択確率が1/3であり、第2カウンタの選択� ��率が2/3となるようにカウンタを選択する方� ��であるとする。また、第2の要素が2であり� �第3の要素が2であるとする。第4の要素は、� �信端末側はパケットロスを検出すると送信� �末側に同じ確認応答番号を2個送信するアル� ��リズムであるとする。この場合、パケット� ��スが1回生じたことにより、2個のカウンタ� �それぞれ共通の情報が記憶される確率は4/9� �ある。具体的に説明すると、1回目の確認応� ��番号を受信したときに、確認応答番号に応� ��た情報を第1カウンタに記憶させる確率は1/3 であり、第2カウンタに記憶させる確率は2/3� �ある。2回目の確認応答番号を受信したとき� ��、確認応答番号に応じた情報を第1カウンタ に記憶させる確率は1/3であり、第2カウンタ� �記憶させる確率は1/3である。このため、こ� �確認応答番号に応じた情報が第1カウンタお� ��び第2カウンタに記憶されて、AND計算の結果 「1」となる確率(出現確率)は4/9であり、第1� �ウンタに重複して記憶されAND計算の結果が� �0」となる確率は1/9であり、第2カウンタに重 複して記憶されAND計算の結果が「0」となる� �率は4/9である。よって、E2Eロス計算手段8は� ��計数手段7の計数結果を出現確率4/9で除算し 、その除算結果をパケットロスの発生回数の 推定とする。例えば、計数手段7の計数結果� �50であれば、50/(4/9)を計算し、パケットロス� ��発生回数を112.5回と推定する。

 E2Eロス計算手段8が出現回数を計算により 求めてもよい。また、各要素の内容の組み合 わせに応じた出現確率は、予め求めておき、 E2Eロス計算手段8が、その出現確率を用いて� �ケットロスの発生回数を推定するように定� �ておけばよい。あるいは、第1から第4の要素 までの少なくとも一つ以上の要素の組み合わ せ、その要素の内容に応じた出現確率をそれ ぞれ求めておき、要素の組と出現確率とを対 応づけた情報を記憶させた確率情報記憶手段 (図示せず)をパケットロス頻度計測システム� ��設けておいてもよい。そして、E2Eロス計算� ��段8は、パケットロス頻度計測システム自身 におけるカウンタの選択アルゴリズム、一つ のフローに対応するカウンタの数、共通数、 端末間の通信アルゴリズムに対応する出現確 率を確率情報記憶手段に記憶された情報の中 から検索し、その出現確率を用いてパケット ロスの発生回数を推定してもよい。

 また、要素の内容に応じた出現確率を正� ��に計算することができない場合には、その� ��素の内容が示す条件のもとで、パケットロ� ��の回数と、計数手段7の計数対象となるデー タの出現個数との関係を統計的に求めればよ い。

 ただし、第4の要素であるプロトコルのア ルゴリズムによっては、第2の要素と第3の要� ��の数値が一致していないことによる観測確� ��の変化はごくわずかであり、計数手段7の計 数結果に対して、E2Eロス計算手段8が確率的� �補正を行わなくてもほとんど問題ない場合� �ある。例えば、第4の要素がTCPである場合、� ��3の要素の数値は3となる。このとき、パケ� �トロス時に発生する確認応答番号の重複回� �は第3の要素「3」と比較して大きい。例えば 、ネットワーク状況によっては、同じ確認応 答番号が10個や20個連続することもある。こ� �ため、第2の要素が「2」であったり、第1の� �素が装置毎のラウンドロビン方式やランダ� �方式であったりしても、パケットロス発生� �には全てのブルームフィルタの該当ビット� �「1」が格納されている可能性が高い。その� ��うな場合には、E2Eロス計算手段8が補正を行 わずに、計数手段7の計数結果をそのままパ� �ットロスの発生回数としてもよい。

 E2Eロス計算手段8以外の構成要素に関して は、既に説明した実施形態と同様である。

 また、パケットロス頻度計測システムは� ��パケットロスの数から、パケットのロス率� ��推定してもよい。例えば、パケットロス頻� ��計測システムは、スループットを算出して� ��スループットをパケットロス数で除算して� ��パケットのロス率を計算する手段を備えて� ��てもよい。

 次に、本発明の概要について説明する。� ��10は、本発明の概要を示すブロック図であ� �。本発明のパケットロス頻度計測システム� �、パケット情報記憶手段112と、パケット情� �登録手段111と、計数手段114とを備える。

 パケット情報記憶手段112(例えば、パケッ ト情報保持手段3)は、パケット内の少なくと� ��確認応答番号を含むフィールドの値に応じ� ��情報を記憶するパケット情報記憶領域113(例 えば、カウンタ4,5)を複数有する。

 パケット情報登録手段111(例えば、情報書 込手段2)は、パケット受信時に、複数のパケ� ��ト情報記憶領域113のうちの一つを選択し、� ��択したパケット情報記憶領域113に、受信し� ��パケット内の少なくとも確認応答番号を含� ��フィールドの値に応じた情報を記憶させる� ��

 計数手段114は、予め定められた数(例えば 、共通数)以上のパケット情報記憶領域に共� �に記憶されている情報の数を計数する。

 そのような構成により、パケットロスの� ��度を低い処理コストで計測することができ� ��。

 また、上記の実施形態には、パケット内� ��送信アドレス、受信アドレス、送信ポート� ��号、受信ポート番号、プロトコルID、パケ� �トロス頻度計測システムのポートの番号の� �ちの少なくとも一部の項目の組み合わせか� �パケットをグループに分類する分類手段(例� ��ば、フロー識別手段1)を備え、パケット情� �登録手段111が、選択したパケット情報記憶� �域113に受信したパケット内の少なくとも確� �応答番号を含むフィールドの値に応じた情� �を記憶させる処理をグループ単位で行う構� �が開示されている。そのような構成によれ� �、フロー毎に、パケットロスの頻度を計測� �ることができる。

 また、上記の実施形態には、パケット情� ��登録手段111が、選択したパケット情報記憶� ��域113にパケット内の少なくとも確認応答番� ��を含むフィールドの値に応じた情報をさせ� ��ときに、値に応じた情報として、所定ビッ� ��数のビット列におけるその値に応じたビッ� ��位置に1を記憶させる構成が開示されている 。

 また、上記の実施形態には、パケット情� ��登録手段111が、パケット内の少なくとも確� ��応答番号を含むフィールドの値に応じた情� ��を、選択したパケット情報記憶領域113に配� ��として記憶させる構成が開示されている。

 また、上記の実施形態には、パケット内� ��少なくとも確認応答番号を含むフィールド� ��値に応じた情報を、値をハッシュ関数を用� ��て変換することによって求める構成が開示� ��れている。

 また、上記の実施形態には、パケット情� ��登録手段111が、ブルームフィルタまたはス� ��ースコードブルームフィルタまたはマルチ� ��ゾリューションスペースコードブルームフ� ��ルタのアルゴリズムに従って、パケット内� ��少なくとも確認応答番号を含むフィールド� ��値をハッシュ関数を用いて変換する構成が� ��示されている。

 また、上記の実施形態には、ケット情報� ��録手段が、フラグ情報、広告ウィンドウサ� ��ズ、送信アドレス、受信アドレス、送信ポ� ��ト番号、受信ポート番号、プロトコルIDの� �ずれか一つ以上と、確認応答番号との組み� �わせに応じた情報を、選択したパケット情� �記憶領域に記憶させる構成が開示されてい� �。

 また、上記の実施形態には、パケット情� ��登録手段111が、パケット内の少なくとも確� ��応答番号を含むフィールドの値とパケット� ��ス頻度計測システムのポートの番号との組� ��合わせに応じた情報を、選択したパケット� ��報記憶領域に記憶させる構成が開示されて� ��る。

 また、上記の実施形態には、パケット情� ��登録手段111が、ランダムに選択する方式、� ��ウンドロビン、あるいは、個々のパケット� ��報記憶領域に予め定められた選択確率に従� ��てパケット情報記憶領域のいずれかを選択� ��る方式のいずれかの方式で、パケット情報� ��憶領域を選択する構成が開示されている。

 図11は、本発明の情報登録装置の最小の� �成例を示すブロック図である。本発明の情� �登録装置は、パケット受信時に、複数のパ� �ット情報記憶領域のうちの一つを選択し、� �択したパケット情報記憶領域に、受信した� �ケット内の少なくとも確認応答番号を含む� �ィールドの値に応じた情報を記憶させるパ� �ット情報登録手段111(例えば、情報書込手段2 )を備える。また、上記の実施形態には、パ� �ット内の少なくとも確認応答番号を含むフ� �ールドの値に応じた情報を記憶するパケッ� �情報記憶領域(例えば、カウンタ4,5)を複数有 するパケット情報記憶手段(例えば、パケッ� �情報保持手段3)を備える情報登録装置の構成 も開示されている。

 図12は、本発明の情報計数装置の最小の� �成例を示すブロック図である。本発明の情� �計数は、パケット内の少なくとも確認応答� �号を含むフィールドの値に応じた情報を記� �する複数のパケット情報記憶領域(例えば、� ��ウンタ4,5)に記憶された情報を参照し、予め 定められた数以上のパケット情報記憶領域に 共通に記憶されている情報の数を計数する計 数手段114(例えば、計数手段7)を備える。

 なお、上記の実施形態では、以下の(1)~(10 )に示すようなパケットロス頻度計測システ� �の特徴的構成が示されている。また、以下� �(11)~(13)に示すような情報登録装置の特徴的� �成が示されている。また、以下の(14)~(15)に� �すような情報計数装置の特徴的構成が示さ� �ている。

(1)パケット内の少なくとも確認応答番号を 含むフィールドの値に応じた情報を記憶する パケット情報記憶領域を複数有するパケット 情報記憶部と、パケット受信時に、複数のパ ケット情報記憶領域のうちの一つを選択し、 選択したパケット情報記憶領域に、受信した パケット内の少なくとも確認応答番号を含む フィールドの値に応じた情報を記憶させるパ ケット情報登録部と、予め定められた数以上 のパケット情報記憶領域に共通に記憶されて いる情報の数を計数する計数部とを備えるこ とを特徴とするパケットロス頻度計測システ ム。

(2)パケット内の送信アドレス、受信アドレ ス、送信ポート番号、受信ポート番号、プロ トコルID、当該パケットロス頻度計測システ� ��のポートの番号のうちの少なくとも一部の� ��目の組み合わせからパケットをグループに� ��類する分類部を備え、パケット情報登録部� ��、選択したパケット情報記憶領域に受信し� ��パケット内の少なくとも確認応答番号を含� ��フィールドの値に応じた情報を記憶させる� ��理をグループ単位で行うパケットロス頻度� ��測システム。

(3)パケット情報登録部が、選択したパケッ ト情報記憶領域にパケット内の少なくとも確 認応答番号を含むフィールドの値に応じた情 報を記憶させるときに、その値に応じた情報 として、所定ビット数のビット列におけるそ の値に応じたビット位置に1を記憶させるパ� �ットロス頻度計測システム。

(4)パケット情報登録部が、パケット内の少 なくとも確認応答番号を含むフィールドの値 に応じた情報を、選択したパケット情報記憶 領域に配列として記憶させるパケットロス頻 度計測システム。

(5)パケット情報登録部が、パケット内の少 なくとも確認応答番号を含むフィールドの値 に応じた情報を、当該値をハッシュ関数を用 いて変換することによって求めるパケットロ ス頻度計測システム。

(6)パケット情報登録部が、ブルームフィル タまたはスペースコードブルームフィルタま たはマルチレゾリューションスペースコード ブルームフィルタのアルゴリズムに従って、 パケット内の少なくとも確認応答番号を含む フィールドの値をハッシュ関数を用いて変換 するパケットロス頻度計測システム。

(7)パケット情報登録部が、フラグ情報、広 告ウィンドウサイズ、送信アドレス、受信ア ドレス、送信ポート番号、受信ポート番号、 プロトコルIDのいずれか一つ以上と、確認応� ��番号との組み合わせに応じた情報を、選択� ��たパケット情報記憶領域に記憶させるパケ� ��トロス頻度計測システム。

(8)パケット情報登録部が、パケット内の少 なくとも確認応答番号を含むフィールドの値 と当該パケットロス頻度計測システムのポー トの番号との組み合わせに応じた情報を、選 択したパケット情報記憶領域に記憶させるパ ケットロス頻度計測システム。

(9)パケット情報登録部が、ランダムに選択 する方式、ラウンドロビン、あるいは、個々 のパケット情報記憶領域に予め定められた選 択確率に従ってパケット情報記憶領域のいず れかを選択する方式のいずれかの方式で、パ ケット情報記憶領域を選択するパケットロス 頻度計測システム。

(10)パケット内の少なくとも確認応答番号� �含むフィールドの値に応じた情報を記憶す� �パケット情報記憶領域を複数有するパケッ� �情報記憶手段と、パケット受信時に、複数� �パケット情報記憶領域のうちの一つを選択� �、選択したパケット情報記憶領域に、受信� �たパケット内の少なくとも確認応答番号を� �むフィールドの値に応じた情報を記憶させ� �パケット情報登録手段と、予め定められた� �以上のパケット情報記憶領域に共通に記憶� �れている情報の数を計数する計数手段とを� �えることを特徴とするパケットロス頻度計� �システム。

(11)パケット受信時に、複数のパケット情� �記憶領域のうちの一つを選択し、選択した� �ケット情報記憶領域に、受信したパケット� �の少なくとも確認応答番号を含むフィール� �の値に応じた情報を記憶させるパケット情� �登録部を備えることを特徴とする情報登録� �置。

(12)パケット内の少なくとも確認応答番号� �含むフィールドの値に応じた情報を記憶す� �パケット情報記憶領域を複数有するパケッ� �情報記憶部を備える情報登録装置。

(13)パケット受信時に、複数のパケット情� �記憶領域のうちの一つを選択し、選択した� �ケット情報記憶領域に、受信したパケット� �の少なくとも確認応答番号を含むフィール� �の値に応じた情報を記憶させるパケット情� �登録手段を備えることを特徴とする情報登� �装置。

(14)パケット内の少なくとも確認応答番号� �含むフィールドの値に応じた情報を記憶す� �複数のパケット情報記憶領域に記憶された� �報を参照し、予め定められた数以上のパケ� �ト情報記憶領域に共通に記憶されている情� �の数を計数する計数部を備えることを特徴� �する情報計数装置。

(15)パケット内の少なくとも確認応答番号� �含むフィールドの値に応じた情報を記憶す� �複数のパケット情報記憶領域に記憶された� �報を参照し、予め定められた数以上のパケ� �ト情報記憶領域に共通に記憶されている情� �の数を計数する計数手段を備えることを特� �とする情報計数装置。

 以上、実施形態を参照して本願発明を説� ��したが、本願発明は上記実施形態に限定さ� ��るものではない。本願発明の構成や詳細に� ��、本願発明のスコープ内で当業者が理解し� ��る様々な変更をすることができる。

 この出願は、2008年10月24日に出願された� �本特許出願2008-273750を基礎とする優先権を主 張し、その開示の全てをここに取り込む。

 本発明は、パケットロスの頻度を計測す� ��パケットロス頻度計測システムに好適に適� ��される。