(57)【要約】【課題】小サイズメモリで指定項目に対する上位Ｎキーを抽出し、同キーに対する異なり数を推定する技術を提供する。【解決手段】トラヒック取得部１０１がトラヒックデータを取得し、監視キー、異なり数カウント対象項目指定部１０２が監視対象となるキー、および異なり数をカウントする対象項目を指定する。異なり数情報算出部１０３がキー情報を分割した分割キー毎に異なり数情報を保持し、取得したパケット毎に当該パケットのキー情報を分割した分割キーに対する異なり数情報を更新する。上位Ｎキー情報算出部１０４が上位Ｎ個のキーおよび当該キーに対する、異なり数情報算出部１０３が保持する異なり数情報から推定した異なり数を保持し、パケット取得時に異なり数情報算出部１０３が異なり数情報を更新した結果、異なり数情報が変化した場合は新規異なり数カウント対象指定項目値と判断し、当該キーの異なり数推定値、および上位Ｎキー情報を更新する。【選択図】図１
2007243371.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワーク上を転送されるパケットデータについて、指定された項目の異なり数に関する上位Ｎ（Ｎ≧２）個のキーおよび同キーの異なり数を推定する推定システムにおける異なり数上位Ｎキーの推定方法であって、
前記推定システムは、トラヒック取得部と、監視キー、異なり数カウント対象項目指定部と、異なり数情報算出部と、上位Ｎキー情報算出部と、を備え、
前記トラヒック取得部が、トラヒックデータを取得する第１のステップと、
前記監視キー、異なり数カウント対象項目指定部が、監視対象となる少なくとも一つのキー、および異なり数をカウントする対象項目を指定する第２のステップと、
前記異なり数情報算出部が、キー情報を分割した分割キー毎に異なり数情報を保持し、取得したパケット毎に当該パケットのキー情報を分割した分割キーに対する異なり数情報を更新する第３のステップと、
前記上位Ｎキー情報算出部が、上位Ｎ個のキーおよび当該キーに対する、前記第３のステップにおける異なり数情報から推定した異なり数を保持し、パケット取得時に前記第３のステップにおいて異なり数情報を更新した結果、異なり数情報が変化した場合は新規異なり数カウント対象指定項目値と判断して、当該キーの異なり数推定値、および上位Ｎキー情報を更新する第４のステップと、
を含むことを特徴とする異なり数上位Ｎキーの推定方法。
【請求項２】
請求項１に記載の異なり数上位Ｎキーの推定方法において、前記第３のステップにおいて、キー情報を分割する前にハッシュ化することを特徴とする異なり数上位Ｎキーの推定方法。
【請求項３】
請求項１に記載の異なり数上位Ｎキーの推定方法において、前記第３のステップにおいて、異なり数情報として、異なり数カウント対象指定項目をハッシュ化した｛０，１｝ビット列のうち、最も左側の“１”ビットの位置の最大値を利用することを特徴とする異なり数上位Ｎキーの推定方法。
【請求項４】
請求項３に記載の異なり数上位Ｎキーの推定方法において、異なり数情報として、異なり数カウント対象指定項目をハッシュ化したビット列の一部を異なり情報識別子として利用し、残りのビット列を異なり数情報算出に利用することによって、単一分割キーに対して識別子別の複数の異なり数情報を保持することを特徴とする異なり数上位Ｎキーの推定方法。
【請求項５】
請求項４に記載の異なり数上位Ｎキーの推定方法において、前記第４のステップにおける与えられたキーに対する異なり数を推定する際に、キーｈの分割キー毎に保持した異なり数情報識別子ｉの異なり数情報の分割キーに関する最小値ｍ＊ｉ（ｈ）に対して異なり数を数式１で推定することを特徴とする異なり数上位Ｎキーの推定方法。
【数１】
2007243371.tif 000009
ここでｋは異なり数情報識別子の総数であり、αｋは数式２で表される補正パラメータである（Γ（・）はＧａｍｍａ関数）。
【数２】
2007243371.tif 000010
【請求項６】
請求項１に記載の異なり数上位Ｎキーの推定方法において、前記第４のステップにおいて、予め定められた更新回数後、新規監視キーが予め定められた順位Ｍ（Ｍ≦Ｎ）未満の順位として現れた場合は、異なり数誤推定と判断して更新を行わないことを特徴とする異なり数上位Ｎキーの推定方法。
【請求項７】
コンピュータネットワーク上を転送されるパケットデータについて、指定された項目の異なり数に関する上位Ｎ（Ｎ≧２）個のキーおよび同キーの異なり数を推定する推定システムであって、
トラヒックデータを取得するトラヒック取得部と、
監視対象となる少なくとも一つのキー、および異なり数をカウントする対象項目を指定する監視キー、異なり数カウント対象項目指定部と、
キー情報を分割した分割キー毎に異なり数情報を保持し、取得したパケット毎に当該パケットのキー情報を分割した分割キーに対する異なり数情報を更新する異なり数情報算出部と、
上位Ｎ個のキーおよび当該キーに対する、前記異なり数情報算出部が保持する異なり数情報から推定した異なり数を保持し、パケット取得時に前記異なり数情報算出部が異なり数情報を更新した結果、異なり数情報が変化した場合は新規異なり数カウント対象指定項目値と判断して、当該キーの異なり数推定値、および上位Ｎキー情報を更新する上位Ｎキー情報算出部と、
を備えることを特徴とする異なり数上位Ｎキーの推定システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はインターネット上を転送されるトラヒック等大容量データの分析技術に関する。
【背景技術】
【０００２】
インターネットにおける特定サーバに対する攻撃などの異常トラヒックの増加に伴い、トラヒックの監視に対する要求が高まっている。トラヒックの監視対象としては、ＭＩＢなどによるパケット数などの総トラヒック流量に基づくものが一般的であるが、総トラヒック量監視では、総トラヒックの変化として現れないようなトラヒックデータ中の一部の変化による異常検出が困難、また異常検出した後の異常原因特定が困難という問題がある。一方、総トラヒック量監視ではなく、指定キー（例えば、送信ＩＰアドレス）毎の指定カウンタ値（例えば、送信ＩＰアドレス毎のパケット数、フロー数、受信ＩＰアドレス数）を保持し、このカウンタ値の統計情報から異常検出する手法では、一部のキーのカウンタ値の変化の検出、また変化を起こしたキーの特定が可能である。しかしながら、この方式では観測される監視キーの数と同じ数のカウンタを必要とし、多数のキーが発生するトラヒックにこの方式を適用するためには、膨大なメモリを必要とするため、実現が困難である。なお、フローとは（送受信ＩＰアドレス、送受信ポート番号、トランスポートプロトコル）の組を同じとするパケット群のことである。
【０００３】
ここで、監視すべきキー値は主にカウンタ値が大きいものであるという前提に基づき、カウンタ値の大きい上位Ｎ個の監視キーのみ、もしくはカウンタ値が総カウンタ合計値の一定比率以上の監視キーのみを推定する手法が特許文献１で提案されている。しかしながらこれらの方式は、カウント対象指定項目が、パケットデータ分析時におけるパケット数などのように、新規データ到着時に必ず当該データのキーのカウンタ値が増加する場合に適用が限られるという問題がある。即ちカウンタ対照指定項目がフロー数、通信相手ホスト数等のように、新規パケット到着時に常にカウンタが増加するわけではなく、過去のパケットで既にそのフロー、通信相手ホストが現れていない場合のみ増加する異なり数の場合、カウンタ値のみならず既出項目値情報をキー毎に保持し、新規パケットに対して、カウント対象項目の値が既出か否かを判断する必要があり、必要メモリサイズがさらに増加するという問題がある。
【０００４】
一方、非特許文献１では、キーとして送信ＩＰアドレスを、カウンタ対象指定項目としてフローを指定した場合の異なり数推定方式を提案している。同方式においては到着パケット毎に、フローに対するＢｌｏｏｍ  Ｆｉｌｔｅｒと呼ばれる、フローが新規か否かを高精度に推定するフィルターを適用し、同フィルターを経由したパケットに対してのみ同パケットの送信ＩＰアドレスのフロー数カウンタを増加させている。同方式によればキー毎に既出フロー情報を保持する必要は無い。しかし、同方式が適用できるのはキー情報がカウンタ対象指定項目情報に含まれている場合のみである。即ち、同方式ではキーである送信ＩＰアドレスがカウンタ対象項目のフロー情報に含まれているので、あるパケットのフロー情報がＢｌｏｏｍ  ｆｉｌｔｅｒによって既出であると判定された場合は、当該パケットの送信ＩＰアドレスにとっても同フローは既出であると判断できる。しかしながら例えばキーがカウンタ対象指定項目に含まれない、キーとして送信ＩＰアドレス、指定項目として受信ＩＰアドレス数の場合を考えると、Ｂｌｏｏｍ  Ｆｉｌｔｅｒにおいてあるパケットの受信ＩＰアドレスが既出であると判断されたとしても、同パケットの送信ＩＰアドレスにとっては新規受信ＩＰアドレスである可能性があるため、同方式を適用したカウンタはできない。
【０００５】
これらデータ中の出現回数でなく異なり数を算出する際に、既出値の情報をすべて保持することなく、異なり数を推定する手法が提案されている（非特許文献２、３）。これらの推定手法では全既出情報を保持する必要がなく、小サイズの異なり数情報を保持するだけで異なり数を推定することができる。異なり数情報および異なり数の推定方法として、例えば非特許文献３では出現値の出現確率の最小値を異なり数情報として保持しておき、その最小出現確率から異なり数を推定する。出現確率として出現値をハッシュ化したビット列の内、最も左側に位置する“１”ビットの位置（ＰＦＯＢ：Position of First One Bit）を用いる。ハッシュ関数が出現値をランダムにハッシュ化するという仮定の元に、あるＰＦＯＢ値ｐの出現確率は１／２Ｐであるため、全出現値のＰＦＯＢ値中の最大値（ＭＰＦＯＢ：Maximum of PFOB）を保持していれば、異なり数はＭＰＦＯＢ値ｍを用いて、２ｍで近似できると期待される。非特許文献３では精度を高めるために出現値のハッシュビット列の内、一部をＭＰＦＯＢ値識別子、残りのビット列からＰＦＯＢ値を算出して、複数の異なり数情報を保持し、識別子ｉに関する異なり数情報ｍｉに関する平均を用いて数式３で異なり数を推定している。
【０００６】
【数３】
2007243371.tif 000003
【０００７】
ここでｋは異なり数情報識別子の総数であり、αｋは数式４で表される補正パラメータである（Γ（・）はＧａｍｍａ関数）。
【０００８】
【数４】
2007243371.tif 000004
【０００９】
キー毎の異なり数の推定に本手法を提案すれば、キー毎に全既出値情報を保持する必要がなくなるが、依然、キー毎にその異なり数情報を保持する必要があるという問題がある。
【００１０】
また、非特許文献４では、キー毎の異なり数の推定を、キーを複数のハッシュ関数でハッシュ化した値毎に、非特許文献２で提案された異なり数推定方法を適用することによって行う手法を提案している。本手法によればハッシュ関数の値域によっては管理すべき異なり数情報数を削減できるものの、非特許文献２自体が大きい異なり数をそのままでは推定できないため、非特許文献４の方式もそのままでは大きい異なり数をもつキーを推定できないという問題がある。
【００１１】
【特許文献１】特許３６４９４５１号公報
【非特許文献１】Ken Keys, David Moore, Cristian Estan, "A Robust System for Accurate Real-time Summaries of Internet Traffic," in Proceedings of the ACM SIGMETRICS, June 2005
【非特許文献２】C. Estan, G. Varghese, and M.Fisk, "Bitmap algorithms for counting active flows on high speed links," in Proc. Internet Measurement Conference 2003 (IMC'03)}, October 2003.
【非特許文献３】M. Durand and P. Flajolet, "loglog counting of large cardinalities,'' in Proc. Engineering and Applications Track" of the 11th Annual European Symposium on Algorithms (ESA03)}, Sptember 2003.
【非特許文献４】Qi Zhao, Abhishek Kumar, and Jun Xu, "Joint Data Streaming and Smpling Techniques for detection of Super Sources and Dextinations," Proc. ACM IMC 2005, October 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、小サイズメモリで指定項目に対する上位Ｎキーを抽出し、かつ同キーに対する異なり数を推定することを目的とする。
【課題を解決するための手段】
【００１３】
上述の目的を達成するため、本発明で提案する手法ではキー毎に異なり数情報を保持することなく、キーもしくはハッシュ化したキーを分割した分割キー毎に異なり数情報を保持する。例えばキーもしくはハッシュ化した監視キーがｍ ｂｉｔで表現されるとき、監視キーは２ｍ個存在しうるため、最大で異なり数情報を２ｍ個保持しなくてはならない。ここでｍ ｂｉｔをｋ等分した分割監視キー毎に異なり数情報を保持する場合、必要となる異なり数情報は２ｍ／ｋ×ｋ個と２ｋ／ｋ分の１に減少する。しかしながら、監視キーそのものでなく分割監視キーに対して異なり数情報を持つことにより、複数の監視キーが同一の分割監視キーに対応する衝突が発生する可能性がある。衝突が発生した場合、本発明では同一分割キーに対応する監視キーの異なり数のうち、最大値を異なり数として推定するため、小さい異なり数をもつ監視キーに対しては過大評価となる可能性が高い。しかしながら異なり数上位Ｎ個の監視キーに関しては、同一分割アドレスの監視キーの異なり数のうち最大値である可能性が高いため、精度よく推定できると期待される。
【００１４】
本明細書において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下のとおりである。
【００１５】
第１の発明は、コンピュータネットワーク上を転送されるパケットデータについて、指定された項目の異なり数に関する上位Ｎ（Ｎ≧２）個のキーおよび同キーの異なり数を推定する推定システムにおける異なり数上位Ｎキーの推定方法であって、前記推定システムは、トラヒック取得部と、監視キー、異なり数カウント対象項目指定部と、異なり数情報算出部と、上位Ｎキー情報算出部と、を備え、前記トラヒック取得部が、トラヒックデータを取得する第１のステップと、前記監視キー、異なり数カウント対象項目指定部が、監視対象となる少なくとも一つのキー、および異なり数をカウントする対象項目を指定する第２のステップと、前記異なり数情報算出部が、キー情報を分割した分割キー毎に異なり数情報を保持し、取得したパケット毎に当該パケットのキー情報を分割した分割キーに対する異なり数情報を更新する第３のステップと、前記上位Ｎキー情報算出部が、上位Ｎ個のキーおよび当該キーに対する、前記第３のステップにおける異なり数情報から推定した異なり数を保持し、パケット取得時に前記第３のステップにおいて異なり数情報を更新した結果、異なり数情報が変化した場合は新規異なり数カウント対象指定項目値と判断して、当該キーの異なり数推定値、および上位Ｎキー情報を更新する第４のステップと、を含むことを特徴とする。
【００１６】
第２の発明は、前記第１の発明において、前記第３のステップにおいて、キー情報を分割する前にハッシュ化することを特徴とする。
【００１７】
第３の発明は、前記第１の発明において、前記第３のステップにおいて、異なり数情報として、異なり数カウント対象指定項目をハッシュ化した｛０，１｝ビット列のうち、最も左側の“１”ビットの位置の最大値を利用することを特徴とする。
【００１８】
第４の発明は、前記第３の発明において、異なり数情報として、異なり数カウント対象指定項目をハッシュ化したビット列の一部を異なり情報識別子として利用し、残りのビット列を異なり数情報算出に利用することによって、単一分割キーに対して識別子別の複数の異なり数情報を保持することを特徴とする。
【００１９】
第５の発明は、前記第４の発明において、前記第４のステップにおける与えられたキーに対する異なり数を推定する際に、キーｈの分割キー毎に保持した異なり数情報識別子ｉの異なり数情報の分割キーに関する最小値ｍ＊ｉ（ｈ）に対して異なり数を数式１で推定することを特徴とする。
【００２０】
【数５】
2007243371.tif 000005
【００２１】
ここでｋは異なり数情報識別子の総数であり、αｋは数式２で表される補正パラメータであり、Γ（・）はＧａｍｍａ関数である。
【００２２】
【数６】
2007243371.tif 000006
【００２３】
第６の発明は、前記第１の発明において、前記第４のステップにおいて、予め定められた更新回数後、新規監視キーが予め定められた順位Ｍ（Ｍ≦Ｎ）未満の順位として現れた場合は、異なり数誤推定と判断して更新を行わないことを特徴とする。
【発明の効果】
【００２４】
本発明によれば分割監視キー毎に異なり数情報を保持することで、少ないメモリ容量で効率よく異なり数に関する上位Ｎ個の監視キーおよび当該監視キーの異なり数を推定することが出来る。
【発明を実施するための最良の形態】
【００２５】
以下、図面を用いて本発明の実施例を説明する。
図１は本発明の推定システムの基本構成の一実施例を示す図である。本実施例の推定システムは、コンピュータネットワーク上を転送されるパケットデータについて、指定された項目の異なり数に関する上位Ｎ（Ｎ≧２）個のキーおよび同キーの異なり数を推定するシステムである。「異なり数」とは、例えば発ホスト毎の異なる宛先ホストの数や、異なる着ポート番号の数といった数であり、一般的には、ある集合に含まれる要素の内、互いに異なる要素の数である。英語ではcardinality（= number of distinct elements）である。
【００２６】
図１に示すように、推定システムは、トラヒックデータを取得するトラヒック取得部１０１と、監視対象となる少なくとも一つのキー、および異なり数をカウントする対象項目を指定する監視キー、異なり数カウント対象項目指定部１０２と、キー情報を分割した分割キー毎に異なり数情報を保持し、取得したパケット毎に当該パケットのキー情報を分割した分割キーに対する異なり数情報を更新する異なり数情報算出部１０３と、上位Ｎ個のキーおよび当該キーに対する、異なり数情報算出部１０３が保持する異なり数情報から推定した異なり数を保持し、パケット取得時に異なり数情報算出部１０３が異なり数情報を更新した結果、異なり数情報が変化した場合は新規異なり数カウント対象指定項目値と判断して、当該キーの異なり数推定値、および上位Ｎキー情報を更新する上位Ｎキー情報算出部１０４と、を備える。
【００２７】
以下、推定システムの動作を説明する。
トラヒック取得部１０１は、ネットワーク内のリンク上、およびネットワーク内部のノード内で転送されるトラヒック情報を取得し、取得トラヒック情報を異なり数情報算出部１０３に転送する。
【００２８】
監視キー、異なり数カウント対象項目指定部１０２は、監視対象となる少なくとも一つのキー、および異なり数をカウントする対象項目を指定する。
【００２９】
以下、監視キー、異なり数カウント対象項目指定部１０２が、監視キーとして送信ＩＰアドレス、異なり数カウンタ項目として送信ＩＰアドレス毎の送信フロー数を指定した場合を図２を用いて説明する。
【００３０】
異なり数情報算出部１０３では、図２の上部に示すパケットデータから監視キーである送信ＩＰアドレス“１９２．１６８．０．１”を抽出し、ハッシュ化した後、ハッシュ化したビット列を予め指定された数に等分する。図２においては、４分割し、｛ａ１，ａ２，ａ３，ａ４｝の４つの分割ハッシュアドレスを得ている。さらに異なり数カウンタ項目であるフロー情報（送受信ＩＰアドレス、送受信ポート番号、トランスポートプロトコル情報）をハッシュ化し、その一部（図２では上位３ビット）を異なり数情報識別子“００１”として利用し、残りのビット列“００１０００…”の内、最も左側に位置する“１”ビットの位置“３”（一番上の桁から数えて３番目）を同識別子に対応する異なり数情報への入力情報とする。同情報を用いて、各分割アドレス、異なり数情報識別子毎に保持された異なり数情報を、到着パケットデータから得られた最も左側に位置する“１”ビットの位置“３”と更新前の値との最大値をとることによって更新する。図２の下部に示すテーブルは、１列目が分割ハッシュアドレス、２列目が識別子００１の更新前の異なり数情報、３列目が識別子００１の更新後の異なり数情報を示している。図２には、更新前は、分割ハッシュアドレスａ１、ａ２、ａ３、ａ４に対応する識別子００１の異なり数情報がそれぞれ０、１、５、３であり、今、図２の上部に示すパケットデータがトラヒック取得部１０１から異なり数情報算出部１０３に転送されてきた例が示されている。前述のように、このパケットデータにおける識別子は００１であり、最も左側に位置する“１”ビットの位置は３である。分割ハッシュアドレスａ１、ａ２の更新前の識別子００１の異なり数情報０、１は３より小さいから、３、３に更新される。一方、分割ハッシュアドレスのａ３、ａ４の更新前の識別子００１の異なり数情報５、３は３以上であるから更新されない。
【００３１】
上位Ｎキー情報算出部１０４では異なり数情報算出部１０３において異なり数情報の更新があった場合、そのフローが当該送信ＩＰアドレスにとって新しいフローであったと判断して、上位Ｎキー情報を更新する。図３に上位Ｎキー情報を更新する手続きを示す。ここでは、分割アドレスａ１、ａ２において異なり数情報の更新があったため、上位Ｎキー情報を更新している。送信ＩＰアドレスｈ＝“１９２．１６８．０．１”、異なり数情報識別子ｉ＝“００１”の分割アドレスに対する更新後の異なり数情報｛３，３，５，３｝の最小値ｍｉ＊（ｈ）は３となる。その他の異なり数情報識別子を含めて、総数ｋ個の異なり数情報識別子に対して分割アドレス間の異なり数情報最小値を算出し、数式１を用いてフロー数を推定する。
【００３２】
【数７】
2007243371.tif 000007
【００３３】
ここでｋは異なり数情報識別子の総数であり、αｋは数式２で表される補正パラメータである（Γ（・）はＧａｍｍａ関数）。
【００３４】
【数８】
2007243371.tif 000008
【００３５】
上記の異なり数情報識別子の総数ｋは、図２のように上位３ビットを識別子に利用する場合は異なり数情報識別子は０００、００１、０１０、０１１、１００、１０１、１１０、１１１の８種類であるから、ｋ＝８となる。図２に示すパケットの例では異なり数情報識別子は００１であるが、観測期間中に取得する同一監視キー（送信ＩＰアドレスｈ＝“１９２．１６８．０．１”）のパケットの異なり数情報識別子ｉは上記の８種類のいずれかであるから、数式１に示すように、ｉ＝１からｋまでの加算を行い、フロー数を推定する。図３では例として推定フロー数が１５０になった場合を示している。
【００３６】
図４に、あるトラヒックデータにおいて送信ＩＰアドレス毎のフロー数について真のフロー数と数式１で推定したフロー数の散布図を示す。直線は真の異なり数と推定異なり数が一致する場合である。フロー数が少ない送信ＩＰアドレスに関しては過大評価している一方、フロー数が大きい領域では精度良くフロー数を推定していることがわかる。従って数式１による推定方式は異なり数上位Ｎ個のキーに関する異なり数を精度良く推定できると期待される。
【００３７】
上位Ｎキー情報算出部１０４では推定した異なり数が、更新前の上位Ｎ送信ＩＰアドレスのフロー数未満であれば、上位Ｎ送信ＩＰアドレス情報は更新しない。一方、推定フロー数が上位Ｎ送信ＩＰアドレスのフロー数以上であれば、図３に示すとおりに更新処理を実施する。当該パケットの送信アドレスが既に上位Ｎ送信ＩＰアドレステーブルに存在すれば、フロー数のみを更新する。上位Ｎ送信ＩＰアドレステーブルに無ければ、最もフロー数が少ない送信ＩＰアドレスをテーブルから削除し、新規送信ＩＰアドレスを上位Ｎ送信ＩＰアドレステーブル中のフロー数に関して降順となる位置に挿入する。
【００３８】
このとき、これら更新処理はパケット毎に実施するため、ある送信ＩＰアドレスは新規に上位Ｎ送信ＩＰアドレステーブルに現れる際はＮ番目の位置に挿入されるはずであり、最大フロー数となる１番目に現れることはありえない。異なり数推定の誤差を考慮してＭ（≦Ｎ）位未満の順位に新規送信ＩＰアドレスが出現した場合、分割監視キーが上位の監視キーと衝突したと判断し、上位Ｎ送信ＩＰアドレステーブルの更新を行わないようして誤推定を回避することができる。なぜなら、到着パケットは、既出フローか新規フローかどちらであるが、どちらにせよ、１つのパケット到着時にフロー数はたかだか１フローしか増加しない。したがって、フロー数に関する上位Ｎ個のＩＰアドレスランキングをパケット到着時に更新している場合、ランキング外から新規にＩＰアドレスが登場する場合は、前述のようにＮ位から登場するはずであり、いきなり上位に登場することはありえない。したがって、いきなり上位に登場した場合は、アドレスをハッシュ化し、分割した際に、他の（フロー数が多い）アドレスと衝突した可能性が高いと考えられるからである。
【００３９】
以上に説明した実施例では監視キーをハッシュ化した後、分割しているが、ハッシュ化せずに分割してもよい。また、識別子として利用するビット数は任意である。実施例のように識別子を利用する方が好適であるが、識別子を利用しなくてもよい。
【００４０】
実施例の推定システムはコンピュータとプログラムで構成できる。また、そのプログラムの一部または全部に代えてハードウェアを用いて構成してもよい。
【００４１】
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施例の推定システムの構成例を示すブロック図である。
【図２】分割アドレスに対する異なり数情報の更新処理を示す。
【図３】上位Ｎ監視キーおよびその推定異なり数の更新処理を示す。
【図４】送信ＩＰアドレス毎のフロー数とその推定値の散布図の例である。
【符号の説明】
【００４３】
１０１…トラヒック取得部、１０２…監視キー、異なり数カウント対象項目指定部、１０３…異なり数情報算出部、１０４…上位Ｎキー情報算出部
【図１】
2007243371.tif 000011
【図２】
2007243371.tif 000012
【図３】
2007243371.tif 000013
【図４】
2007243371.tif 000014