(57)【特許請求の範囲】
【請求項１】
ワード長又はワード長の整数倍のビット配列を複数連ねたデータ構造で記憶する記憶手段と、
入力されたデータ列に基づいて第１の一意な値を求めると共に、上記入力されたデータ列に基づいて、複数個の第２の一意な値を求める一意値演算手段と、
上記入力されたデータ列の追加又は判定の際に、上記第１の一意な値をインデックス値として、当該インデックス値に対応する記憶領域に記憶されるビット配列を選択して、選択されたビット配列をプロセッサのレジスタに読み込む対象選択手段と、
上記プロセッサのレジスタ上に読み込まれている上記ビット配列の中で、上記入力されたビット列から求めた複数個の第２の一意な値に対応するビットに対して書き込み又は読み込みを行なうアクセス実行手段と、
上記アクセス実行手段による書き込み又は読み込み終了後、上記プロセッサのレジスタ上の上記データ配列を、元の記憶領域に書き込む対象書込手段と
を備えることを特徴とする記憶制御装置。
【請求項２】
上記アクセス実行手段が、上記プロセッサのレジスタ上の上記ビット配列の中の、上記入力されたビット列の上記複数個の第２の一意な値に対応する各ビットの同一性を判断して上記入力されたビット列の判定処理を行なう要素判定処理部を有することを特徴とする請求項１に記載の記憶制御装置。
【請求項３】
ワード長又はワード長の整数倍のビット配列を複数連ねたデータ構造で記憶する記憶手段を用いる記憶制御装置の記憶制御方法であって、
上記記憶制御装置が、一意値演算手段、対象選択手段、アクセス実行手段、対象書込手段を備え、
上記一意値演算手段が、入力されたデータ列に基づいて第１の一意な値を求めると共に、上記入力されたデータ列に基づいて、複数個の第２の一意な値を求める一意値演算工程と、
上記対象選択手段が、上記入力されたデータ列の追加又は判定の際に、上記第１の一意な値をインデックス値として、当該インデックス値に対応する記憶領域に記憶されるビット配列を選択して、選択されたビット配列をプロセッサのレジスタに読み込む対象選択工程と、
上記アクセス実行手段が、上記プロセッサのレジスタ上に読み込まれている上記ビット配列の中で、上記入力されたビット列から求めた複数個の第２の一意な値に対応するビットに対して書き込み又は読み込みを行なうアクセス実行工程と、
上記対象書込手段が、上記アクセス実行手段による書き込み又は読み込み終了後、上記プロセッサのレジスタ上の上記データ配列を、元の記憶領域に書き込む対象書込工程と
を有することを特徴とする記憶制御方法。
【請求項４】
ワード長又はワード長の整数倍のビット配列を複数連ねたデータ構造で記憶する記憶手段を用いる記憶制御装置を、
入力されたデータ列に基づいて第１の一意な値を求めると共に、上記入力されたデータ列に基づいて、複数個の第２の一意な値を求める一意値演算手段、
上記入力されたデータ列の追加又は判定の際に、上記第１の一意な値をインデックス値として、当該インデックス値に対応する記憶領域に記憶されるビット配列を選択して、選択されたビット配列をプロセッサのレジスタに読み込む対象選択手段、
上記プロセッサのレジスタ上に読み込まれている上記ビット配列の中で、上記入力されたビット列から求めた複数個の第２の一意な値に対応するビットに対して書き込み又は読み込みを行なうアクセス実行手段、
上記アクセス実行手段による書き込み又は読み込み終了後、上記プロセッサのレジスタ上の上記データ配列を、元の記憶領域に書き込む対象書込手段
として機能させる記憶制御プログラム。
【請求項５】
監視ネットワークを通過する信号の信号情報を監視する情報監視装置において、
上記監視ネットワーク上を流れる信号の信号情報を、上記入力されたデータ列として記憶する記憶制御手段が、請求項１又は２に記載の記憶制御装置に対応するものであることを特徴とする情報監視装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶制御装置、方法及びプログラム、並びに、情報監視装置に関し、例えば、情報通信ネットワークにおいて、監視ネットワーク上を流れるパケット情報を監視する情報監視装置が備える記憶装置、方法及びプログラムに適用し得るものである。
【背景技術】
【０００２】
例えば、ブルームフィルタ（Bloom  Filter）は、１９７０年にBurton  H．Bloomが考案した記録方式であり、空間効率の良い確率的データ構造で、ある要素が集合のメンバーであるか否かを判定するために使用されるものである。
【０００３】
まず、データ構造として２ｎビットのビット配列を記憶装置５（例えば、ＤＲＡＭやストレージ等）上に用意する。そして、各ビットの初期値は０であり、ｎビットの長さの値（０〜２ｎ−１の値を取る）をインデックスとしてアクセス可能であるとする。
【０００４】
図２は、記憶装置５へのアクセス方法を例示する図である。図２において、ｎビット値に対して、ビット配列の先頭アドレスを加算することによって、対象とするビット値が属する記憶装置５上のアドレスを特定することができる。
【０００５】
図３は、記憶装置５に対して要素の追加を説明する図である。また、図４は、要素の追加処理手順を示すフローチャートである。
【０００６】
図３において、まず、追加要素を入力とし、この要素にハッシュ関数を用いてハッシュ演算を行ない、ｎビットのハッシュ値を複数種類（図３ではｋ個）生成する（ステップＳ５１）。そして、各ハッシュ値をインデックスとし、各ハッシュ値から記憶装置５上のアドレスを算出し（ステップＳ５２）、そのアドレスから１ワード分のビット列を読み込み（ステップＳ５３）、ビット配列上のビット値に１を書き込む（ステップＳ５４）。そして、元のアドレスへの書き込みを行なうことで要素の追加を行なう（ステップＳ５５）。
【０００７】
図５は、記憶装置５から要素が集合に属しているか否かを判定する方法を説明する図である。また、図６は、要素の判定処理手順を示すフローチャートである。
【０００８】
図５において、まず、追加時と同様に、判定要素にハッシュ関数を用いてハッシュ演算を行ない、ｎビットのハッシュ値を複数種類（図５ではｋ個）生成する（ステップＳ６１）。そして、各ハッシュ値をインデックスとして、記憶装置５上のアドレスを算出し（ステップＳ６２）そのアドレスから１ワード分のビット列を読み込む（ステップＳ６３）。そして、ビット配列上の対応するビットが１であるか否かを判断し（ステップＳ６４）、ｋ個のハッシュ値全てについて読み込んだビットが１であれば、要素が集合のメンバーであると判定（ＴＲＵＥ判定）し（ステップＳ６５、Ｓ６６）、１つでも０があれば、要素は集合のメンバーではないと判定（ＦＡＬＳＥ判定）する（ステップＳ６７）。
【０００９】
ここで、ブルームフィルタの特徴である判定誤りについて説明する。ブルームフィルタは、判定結果の１００％の確実性を保証するものではない。つまり、要素が集合のメンバーでないにも拘わらずメンバーであると判定してしまうこともある。この要素が集合のメンバーであるとの判定してしまう可能性を誤り率（False  Positive  Rate）といい、式（１）で示される
【数１】
0004872857.tif 000002
【００１０】
式（１）は、使用する記憶領域を２ｎビット、ハッシュ値の個数をｋ個、追加した要素の個数をＮ個（互いに異なる要素とする）としたときの誤り率の算出式である。
【００１１】
図７は、式（１）に基づいて、ハッシュ値の数ｋを増加させたときの誤り率の変化の一例を示す図である。図７に示す誤り率の変化結果より、ハッシュ値の種類を複数（ｋ個）とることで誤り率を最適な値へとすることができる。
【００１２】
【特許文献１】特開２００３−２９８６５１号公報
【非特許文献１】ウィキメディア財団，フリー百科事典「ウィキペディア」出展，「ブルームフィルタ」，最終更新日2007年6月28日，インターネット，検索日2007年8月28日，ｈｔｔｐ：／／ｊａ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／％Ｅ３％８３％９６％Ｅ３％８３％ＡＢ％Ｅ３％８３％ＢＣ％Ｅ３％８３％Ａ０％Ｅ３％８３％９５％Ｅ３％８２％Ａ３％Ｅ３％８３％ＡＢ％Ｅ３％８２％ＢＦ
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した従来のブルームフィルタによる要素の追加・判定処理は、ハッシュ値の種類数（ｋ個）に応じた回数だけ、記憶装置にアクセスする必要がある。そのため、高速処理が要求される場合には、この記憶装置へのアクセスに要する時間がボトルネックとなり性能が発揮できないことがある。
【００１４】
そこで、本発明は、記憶装置への要素の追加又は判定処理において、記憶装置へのアクセス時間を低減することができる記憶装置、方法及びプログラム、さらにこの記憶装置等を有する情報監視装置を提供する。
【課題を解決するための手段】
【００１５】
かかる課題を解決するために、第１の本発明の記憶制御装置は、（１）ワード長又はワード長の整数倍のビット配列を複数連ねたデータ構造で記憶する記憶手段と、（２）入力されたデータ列に基づいて第１の一意な値を求めると共に、入力されたデータ列に基づいて、複数個の第２の一意な値を求める一意値演算手段と、（３）入力されたデータ列の追加又は判定の際に、第１の一意な値をインデックス値として、当該インデックス値に対応する記憶領域に記憶されるビット配列を選択して、選択されたビット配列をプロセッサのレジスタに読み込む対象選択手段と、（４）プロセッサのレジスタ上に読み込まれているビット配列の中で、入力されたビット列から求めた複数個の第２の一意な値に対応するビットに対して書き込み又は読み込みを行なうアクセス実行手段と、（５）アクセス実行手段による書き込み又は読み込み終了後、プロセッサのレジスタ上のデータ配列を、元の記憶領域に書き込む対象書込手段とを備えることを特徴とする。
【００１６】
第２の本発明の記憶制御方法は、ワード長又はワード長の整数倍のビット配列を複数連ねたデータ構造で記憶する記憶手段を用いる記憶制御装置の記憶制御方法であって、記憶制御装置が、一意値演算手段、対象選択手段、アクセス実行手段、対象書込手段を備え、（１）一意値演算手段が、入力されたデータ列に基づいて第１の一意な値を求めると共に、入力されたデータ列に基づいて、複数個の第２の一意な値を求める一意値演算工程と、（２）対象選択手段が、入力されたデータ列の追加又は判定の際に、第１の一意な値をインデックス値として、当該インデックス値に対応する記憶領域に記憶されるビット配列を選択して、選択されたビット配列をプロセッサのレジスタに読み込む対象選択工程と、（３）アクセス実行手段が、プロセッサのレジスタ上に読み込まれているビット配列の中で、入力されたビット列から求めた複数個の第２の一意な値に対応するビットに対して書き込み又は読み込みを行なうアクセス実行工程と、（４）対象書込手段が、アクセス実行手段による書き込み又は読み込み終了後、上記プロセッサのレジスタ上のデータ配列を、元の記憶領域に書き込む対象書込工程とを有することを特徴とする。
【００１７】
第３の本発明の記憶制御プログラムは、ワード長又はワード長の整数倍のビット配列を複数連ねたデータ構造で記憶する記憶手段を用いる記憶制御装置を、（１）入力されたデータ列に基づいて第１の一意な値を求めると共に、入力されたデータ列に基づいて、複数個の第２の一意な値を求める一意値演算手段、（２）入力されたデータ列の追加又は判定の際に、第１の一意な値をインデックス値として、当該インデックス値に対応する記憶領域に記憶されるビット配列を選択して、選択されたビット配列をプロセッサのレジスタに読み込む対象選択手段、（３）プロセッサのレジスタ上に読み込まれているビット配列の中で、入力されたビット列から求めた複数個の第２の一意な値に対応するビットに対して書き込み又は読み込みを行なうアクセス実行手段、（４）アクセス実行手段による書き込み又は読み込み終了後、プロセッサのレジスタ上のデータ配列を、元の記憶領域に書き込む対象書込手段として機能させるものである。
【００１８】
第４の本発明の情報監視装置は、監視ネットワークを通過する信号の信号情報を監視する情報監視装置において、監視ネットワーク上を流れる信号の信号情報を、入力されたデータ列として記憶する記憶制御手段が、第１の本発明の記憶制御装置に対応するものであることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、記憶装置への要素の追加又は判定処理において、記憶装置へのアクセス時間を低減することができる。
【発明を実施するための最良の形態】
【００２０】
（Ａ）第１の実施形態
以下、本発明の記憶制御装置、方法及びプログラム、並びに、情報監視装置の第１の実施形態を図面を参照しながら説明する。
【００２１】
第１の実施形態は、例えば、監視ネットワーク上を通過するパケット情報を監視するシステムで用いる記憶装置及び記憶方法に本発明を適用する場合を例示して説明する。
【００２２】
（Ａ−１）第１の実施形態の構成
図８は、第１の実施形態の監視ネットワーク上を通過するパケット通過監視システム１０の概略的な構成を示す構成図である。
【００２３】
図８において、第１の実施形態のパケット通過監視システム１０は、高速回線４を通過するパケットを監視する監視プローブ装置１、管理回線３を通じて監視プローブ装置１と接続するマネージャ装置２、タップ５を有する。
【００２４】
高速回線４は、例えば、ＩＰ（Internet  Protocol）ネットワークなどの高速回線であり、監視プローブ装置１の監視対象回線である。
【００２５】
タップ５は、高速回線４を流れるパケットを複製し、その複製したパケットを監視プローブ装置１に与えるものである。タップ５は、高速回線４を流れる双方向のパケットを複製可能に構成されるものである。なお、図８では、タップ５を例示したが、通信パケットを観測プローブ装置１に与えることができれば、タップ装置に限定されず転送装置のミラー回線などとしてもよい。
【００２６】
マネージャ装置２は、監視プローブ装置１を管理するものである。マネージャ装置２は、管理回線３を通じて監視プローブ装置１に対して監視対象の問い合わせを行なうものである。
【００２７】
監視プローブ装置１は、高速回線４を通過するパケットのパケット情報を監視するものである。監視プローブ装置１は、タップ５を介して受信したパケットをパケットのパケット情報を記憶するものである。また、監視プローブ装置１は、管理回線３を通じてマネージャ装置２と接続しており、マネージャ装置３から監視対象の問い合わせがなされると、その監視対象のパケット通過を判定し、その判定結果をマネージャ装置１に与えるものである。
【００２８】
また、監視プローブ装置１は、通信パケットの記憶処理やパケット通過判定処理などの監視プローブ装置１の処理を司るプロセッサ１２と、例えばＤＲＡＭなどの記憶装置１１とを有する。
【００２９】
図１は、監視プローブ装置１が有する記憶装置１１上に確保されるデータ構造を示すデータ構造図である。
【００３０】
図１に示すように、記憶装置１１上に確保されるデータ構造は、記憶領域において、１ワードを１つのビット配列として、複数個のビット配列１１２−１〜１１２−ｎを連なった構造をしている。また、ビット配列１１２−１〜１１２−ｎにはそれぞれ先頭アドレス１１１が付与されている。
【００３１】
つまり、従来は、記憶装置１１上の記憶領域の全てを１つのビット配列として使用していたが、第１の実施形態では、記憶領域において１ワードを１つのビット配列として複数個連ねた形で記憶させる。
【００３２】
なお、第１の実施形態では、１ワードが３２ビットの場合を示したが、１ワードのビット数は特に限定されるものではない。また、記憶装置１１上のビット配列が１ワードのワード長である必要なく、１ワードのワード長の整数倍のワード長としてもよい。
【００３３】
（Ａ−２）第１の実施形態の動作
次に、第１の実施形態の監視プローブ装置１における要素の追加・判定処理の動作を図面を参照しながら説明する。
【００３４】
まず、監視プローブ装置１における要素の追加処理について、図９及び図１０を参照して説明する。図９は、監視プローブ装置１における要素の追加処理を説明する説明図である。また、図１０は、監視プローブ装置１における要素の追加処理を示すフローチャートである。
【００３５】
高速回線４上を流れるパケットは、タップ５を介して監視プローブ装置１に与えられる。監視プローブ装置１にパケットが与えられると、入力されたパケットは追加要素として監視プローブ装置１の記憶装置１１に記憶される。
【００３６】
監視プローブ装置１において、追加要素はハッシュ関数によりハッシュ演算が行なわれ、インデックス値２２となるハッシュ値が生成される（ステップＳ１１）。
【００３７】
次に、生成したインデックス値２２に基づいて、記憶装置１１から対応するアドレス領域１１２−ｍを割り出し（ステップＳ１２）、記憶装置１１上のアドレス領域１１２−ｍから１ワード（３２ビット）のデータをプロセッサ１２のレジスタ１１３上に読み込む（ステップＳ１３）。
【００３８】
このとき、プロセッサ１２は、インデックス値２２とするハッシュ値に基づいてアドレス変換処理を行ない、記憶装置１１における記憶領域を選択する。例えば、プロセッサ１２が、インデックス値２２とするハッシュ値と記憶装置１１の記憶領域とを対応付けたアドレス変換テーブル（図示しない）を有し、プロセッサ１２がこのアドレス変換テーブルを参照して、インデックス値２２とするハッシュ値に対応する記憶領域を選択することができる。
【００３９】
１ワード（３２ビット）のデータがプロセッサ１２のレジスタ１１３上に読み込まれると、入力された追加要素に対してハッシュ関数によるハッシュ演算を行ない、複数（ｋ）個のハッシュ値１〜ｋが生成される（ステップＳ１４）。
【００４０】
そして、これらハッシュ値１〜ｋのそれぞれに対してレジスタ１１３上のビット配列の対応するビット値に「１」を書き込む（ステップＳ１５）。
【００４１】
このとき、プロセッサ１２は、各ハッシュ値に基づいてレジスタ１１３上のビット配列のビット位置を指定する。例えば、プロセッサ１２は、各ハッシュ値とビット配列のビット位置とを対応付けるビット位置対応テーブル（図示しない）を有し、プロセッサ１２が、このビット位置対応テーブルを参照して、各ハッシュ値に対応するビット位置を指定することができる。
【００４２】
その後、レジスタ１１３上のビット配列が元のアドレス領域１１２−ｍに対して書き込まれる（ステップＳ１６）。
【００４３】
続いて、監視プローブ装置１における要素の判定処理について図１１及び図１２を参照して説明する。図１１は、監視プローブ装置１における要素の判定処理を説明する説明図である。また、図１２は、監視プローブ装置１における要素の判定処理を示すフローチャートである。
【００４４】
監視プローブ装置１は、マネージャ装置２から監視対象の問い合わせを受ける。このマネージャ装置２からの問い合わせに係る監視対象が判定要素３１として監視プローブ装置１に入力され、監視プローブ装置１において要素判定処理が行なわれる。
【００４５】
まず、監視プローブ装置１において、判定要素３１からインデックス値３２となるハッシュ値が生成される（ステップＳ２１）。次に、生成されたインデックス値３２に基づいて記憶装置１１から対応するアドレス領域１１２−ｍが割り出される（ステップＳ２２）。
【００４６】
このとき、プロセッサ１２が、インデックス値３２とするハッシュ値に基づいて、アドレス変換テーブルを参照して、記憶装置１１上の記憶領域を割り出す。
【００４７】
そして、アドレス領域１１２−ｍから１ワード（３２ビット）のデータがプロセッサ１２のレジスタ１１３に読み込まれる（ステップＳ２３）。
【００４８】
１ワード（３２ビット）のデータがプロセッサ１２のレジスタ１１３に読み込まれると、判定要素に対してハッシュ関数によるハッシュ演算を行ない、ハッシュ値１〜ｋが生成される（ステップＳ２４）。
【００４９】
ハッシュ値１〜ｋが生成されると、レジスタ１１３上に読み込まれているビット配列のうち、ハッシュ値１〜ｋのそれぞれに対応するビット値を見て（ステップＳ２５）、各ハッシュ値１〜ｋに対応する全てのビット値が「１」である場合、当該判定要素が集合のメンバーであると判定（ＴＲＵＥ判定）し（ステップＳ２７）、１つでも「０」のビットがある場合、当該判定要素が集合のメンバーでないと判定する（ＦＡＬＳＥ判定）。
【００５０】
なお、ビット値を見る際、プロセッサ１２は、各ハッシュ値に基づいてビット位置対応テーブルを参照して、各ハッシュ値に対応するビット位置のビット値を判断する。
【００５１】
続いて、第１の実施形態の要素判定処理の誤り率について説明する。下記式（２）は、第１の実施形態の要素判定処理の誤り率を算出する算出式である。
【数２】
0004872857.tif 000003
【００５２】
式（２）は、記憶装置１２の領域を２ｎビット、ワード長を２ｗビット、ハッシュ値の個数をｋ個、追加した要素の個数をＮ個（互いに異なる要素とする）としたときの誤り率の算出式である。
【００５３】
第１の実施形態の要素判定処理では、１ワードのワード長が２ｗであるから、記憶装置１２の記憶領域に構造されるビット配列は、２ｎ−ｗ（＝２ｎ／２ｗ）個だけ確保することができる。
【００５４】
追加要素２１を追加する際、図１０のステップＳ１２及びＳ１３に示すように、インデックス値２１に基づいて、２ｎ−ｗ個のビット配列から１個のビット配列を選択する。このインデックス値２１は、追加要素２１に対してハッシュ演算を施した結果求められるものであるから、それぞれのビット配列は一様な確率で選択される。そのため、例えばＮ個の互いに異なる要素を追加するときには、それぞれのビット配列が選択される回数は、平均値にみればＮ／２ｎ−ｗ回となる。
【００５５】
また、記憶領域の１ワードのワード長が２ｗビットであるから、それぞれのビット配列が２ｗビットの大きさの従来方式のブルームフィルタと同等である。そこで、第１の実施形態の要素判定に係る誤り率は、それぞれのビット配列が２ｗビットの大きさをもつ従来のブルームフィルタにおいて、Ｎ／２ｎ−ｗの要素の入力があった場合を考えればよい。
【００５６】
そこで、第１の実施形態の要素判定に係る誤り率を算出する算出式は、上述した式（１）において、記憶装置１２で使用する記憶領域を２ｗビット、ハッシュ値の個数をｋ個、追加した要素の個数をＮ／２ｎ−ｗ個（互いに異なる要素とする）としたときに等しい。これにより、第１の実施形態の要素判定処理に係る誤り率を算出する算出式として、式（２）を得る。
【００５７】
図１３は、第１の実施形態の要素判定処理に誤り率の算出式（式（２））と、従来の要素判定処理に係る誤り率の算出式（式（１））とにより求めた誤り率について、ハッシュ値の種類数の違いに応じたシミュレーション結果を示す図である。
【００５８】
図１３に示すように、第１の実施形態の式（２）による誤り率と、従来方式の式（１）による誤り率とを比較すると、ハッシュ値の種類数が１〜８個程度の場合には、第１の実施形態の要素判定処理の誤り率は従来方式のそれと同等であり、ハッシュ値の種類数が多くなるについて、従来方式に比べて軽微な劣化があるが、第１の実施形態の誤り率は従来方式のそれとほぼ同等である。
【００５９】
（Ａ−３）第１の実施形態の効果
以上のように、第１の実施形態によれば、１ワードのビット配列を複数個連ねたデータ構造とし、プロセッサのレジスタ上に読み込んだ１ワードのビット配列を用いて、要素の追加・判定処理を行なうことにより、従来よりも記憶装置の記憶領域へのアクセス回数を低減させることができる。その結果、要素の追加・判定処理に要する時間を低減させ、高速処理を実現することができる。
【００６０】
（Ｂ）他の実施形態
第１の実施形態では、監視対象ネットワーク上を流れるパケットのパケット情報を監視する監視プローブ装置における要素の追加・判定処理に本発明を適用した場合を例示したが、本発明はパケット情報の監視システムに限定されるものではなく、要素が集合のメンバーであるか否かを判定する要素判定技術に広く適用することができる。
【００６１】
また、第１の実施形態では、記憶装置の例として、主記憶装置（例えばＤＲＡＭ）を例示して説明したが、記憶装置であれば、例えば、ハードディスク、フロッピー（登録商標）ディスクなどの外部記憶装置にも適用することができる。
【００６２】
第１の実施形態では、１ワードが３２ビットの場合を例示して説明したが、１ワードのビット数は、特に限定されるものではなく、使用するプロットフォームに応じて変更することができる。
【００６３】
また、第１の実施形態では、記憶装置の記憶領域にアクセスするアクセス単位を１ワードとする場合を例示して説明したが、アクセス単位を２ワード以上であってもよい。これにより、プラットフォーム（例えば、プロセッサ、メモリ方式など）に応じて、適切にアクセス単位を調整することができる。この場合、アクセス対象とする２ワード、３ワード…のそれぞれと、インデックス値とを対応付けるテーブルをプロセッサが備えることで実現することができる。
【図面の簡単な説明】
【００６４】
【図１】第１の実施形態の記憶領域に確保されるデータ構造を示すデータ構造図である。
【図２】従来の記憶装置へのアクセス方法を説明する説明図である。
【図３】従来の要素の追加処理を説明する説明図である。
【図４】従来の要素の追加処理を示すフローチャートである。
【図５】従来の要素の判定処理を説明する説明図である。
【図６】従来の要素の判定処理を示すフローチャートである。
【図７】従来の要素判定処理に係る誤り率の変化とハッシュ値の種類数の変化との関係を示す図である。
【図８】第１の実施形態のパケット通過監視システムの構成を示す構成図である。
【図９】第１の実施形態の追加処理を説明する説明図である。
【図１０】第１の実施形態の追加処理を示すフローチャートである。
【図１１】第１の実施形態の判定処理を説明する説明図である。
【図１２】第１の実施形態の判定処理を示すフローチャートである。
【図１３】第１の実施形態の要素判定処理の誤り率の変化とハッシュ値の種類数の変化との関係を示す図である。
【符号の説明】
【００６５】
１…観測プローブ装置、１１…記憶装置、１２…プロセッサ、１１１…先頭アドレス、１１２−１〜１１２−ｎ…ビット配列、２…マネージャ装置、３…管理回線、４…高速回線、５…タップ、１０…パケット通過監視システム。
【図１】
0004872857.tif 000004
【図２】
0004872857.tif 000005
【図３】
0004872857.tif 000006
【図４】
0004872857.tif 000007
【図５】
0004872857.tif 000008
【図６】
0004872857.tif 000009
【図７】
0004872857.tif 000010
【図８】
0004872857.tif 000011
【図９】
0004872857.tif 000012
【図１０】
0004872857.tif 000013
【図１１】
0004872857.tif 000014
【図１２】
0004872857.tif 000015
【図１３】
0004872857.tif 000016