(57)【要約】【課題】大量のフロー情報を蓄積する場合であっても検索処理を迅速に行う。【解決手段】フロー情報または検索要求を受信する受信部と、受信したフロー情報を格納する記憶装置と、受信した検索要求に基づいて記憶装置に格納されたフロー情報を検索する検索部と、検索部が検索した結果を送信する送信部と、受信部が受信した前記フロー情報を一時的に格納するフロー情報記憶部と、所定の条件が成立したときに、前記フロー情報記憶部に格納されたフロー情報から検索用情報を生成する検索用情報生成部と、を備え、前記検索部は、前記検索要求を受け付けると当該検索要求に含まれる検索条件で前記検索用情報を検索し、前記検索条件に合致する検索用情報から前記フロー情報を取得する。【選択図】図２
2010068279.tif 000002
【特許請求の範囲】
【請求項１】
フロー情報または検索要求を受信する受信部と、
前記受信したフロー情報を格納する記憶装置と、
前記受信した検索要求に基づいて前記記憶装置に格納されたフロー情報を検索する検索部と、
前記検索部が検索した結果を送信する送信部と、
を備えたフロー情報処理装置において、
前記受信部が受信した前記フロー情報を一時的に格納するフロー情報記憶部と、
所定の条件が成立したときに、前記フロー情報記憶部に格納されたフロー情報から検索用情報を生成する検索用情報生成部と、を備え、
前記検索部は、
前記検索要求を受け付けると当該検索要求に含まれる検索条件で前記検索用情報を検索し、前記検索条件に合致する検索用情報から前記フロー情報を取得することを特徴とするフロー情報処理装置。
【請求項２】
請求項１に記載のフロー情報処理装置であって、
前記検索用情報生成部は、
前記フロー情報記憶部に格納されたフロー情報に含まれる項目からフロー情報の内容を抽出し、前記抽出した項目の内容を含む情報を検索用情報として生成することを特徴とするフロー情報処理装置。
【請求項３】
請求項２に記載のフロー情報処理装置であって、
前記検索用情報生成部は、
前記フロー情報記憶部に格納されたフロー情報に含まれる項目の内容を抽出し、
前記抽出した内容の出現頻度を演算し、
前記フロー情報にインデックスを付与し、
前記演算した出現頻度の順に前記項目の内容を設定し、前記インデックスが指し示すフロー情報の関係からビット情報を前記検索用情報として生成することを特徴とするフロー情報処理装置。
【請求項４】
請求項３に記載のフロー情報処理装置であって、
前記検索用情報生成部は、
前記ビット情報の内、前記出現頻度の順位が予め設定した順位以降の項目の内容については、複数の項目の内容を予め設定した内容に設定し、予め設定した順位以降の項目の内容に対応する複数のインデックスを前記予め設定した内容にまとめることを特徴とするフロー情報処理装置。
【請求項５】
請求項１に記載のフロー情報処理装置であって、
前記検索用情報生成部は、
前記所定の条件が成立する度に、前記フロー情報に含まれる項目毎に前記検索用情報を生成することを特徴とするフロー情報処理装置。
【請求項６】
請求項３に記載のフロー情報処理装置であって、
前記検索部は、
前記検索要求を受け付けると当該検索要求に含まれる検索条件で前記ビット情報を検索し、
前記検索条件に合致するビット情報からインデックスを取得し、
前記インデックスから前記フロー情報を取得することを特徴とするフロー情報処理装置。
【請求項７】
請求項４に記載のフロー情報処理装置であって、
前記検索部は、
前記検索要求を受け付けると当該検索要求に含まれる検索条件で前記ビット情報を検索し、
前記検索条件に合致する項目の内容が前記予め設定した内容の場合には、前記検索条件に合致するフロー情報を前記記憶装置から検索することを特徴とするフロー情報処理装置。
【請求項８】
請求項１に記載のフロー情報処理装置であって、
前記検索用情報生成部は、
予め設定した周期が経過する度に所定の条件の成立を判定することを特徴とするフロー情報処理装置。
【請求項９】
請求項１に記載のフロー情報処理装置であって、
前記検索用情報生成部は、
前記フロー情報記憶部の空き容量が所定の値に達したときに所定の条件の成立を判定することを特徴とするフロー情報処理装置。
【請求項１０】
請求項１に記載のフロー情報処理装置であって、
前記フロー情報は、ＮｅｔＦｌｏｗまたはＩＰＦＩＸのプロトコルを用いることを特徴とするフロー情報処理装置。
【請求項１１】
フロー情報を送信する通信装置と、
検索要求を送信する計算機と、
前記フロー情報または検索要求を受信する受信部と、前記受信したフロー情報を格納する記憶装置と、前記受信した検索要求に基づいて前記記憶装置に格納されたフロー情報を検索する検索部と、前記検索部が検索した結果を前記サーバ装置に送信する送信部と、を有するフロー情報処理装置と、
を備えたネットワークシステムにおいて、
前記フロー情報処理装置は、
前記受信部が受信した前記フロー情報を一時的に格納するフロー情報記憶部と、
所定の条件が成立したときに、前記フロー情報記憶部に格納されたフロー情報から検索用情報を生成する検索用情報生成部と、を備え、
前記検索部は、
前記検索要求を受け付けると当該検索要求に含まれる検索条件で前記検索用情報を検索し、前記検索条件に合致する検索用情報からフロー情報を取得することを特徴とするネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルータ装置が行った処理内容のログであるフロー情報の処理に係わり、特に、フロー情報を収集するフロー情報処理装置及びフロー情報処理装置を備えたネットワークシステムに関するものである。
【背景技術】
【０００２】
ネットワークシステムを構成するルータ装置では、ルータ装置が処理した内容をフロー情報として外部の装置へ通知しており、フロー情報を通知するプロトコルとしてＮｅｔＦｌｏｗが知られている（例えば、非特許文献１）。ルータ装置にはフロー情報の通知内容や通知対象、送信周期が予め設定され、設定された内容に従ってフロー情報としてのＮｅｔＦｌｏｗパケットを作成し、外部の装置へ送信する。なお、フロー情報は、パケットの転送内容を通知する情報であり、例えば、IPｖ４の場合では、送信元ＩＰアドレス、送信先IPアドレス、送信元ポート番号、送信先ポート番号及びプロトコルが含まれる。
【０００３】
また上記ＮｅｔＦｌｏｗの後継技術としてＩＰＦＩＸ(IP Flow Information eXport)の標準化がＩＥＴＦ（Internet Engineering Task Force）で進められている（例えば、非特許文献２）。ＩＰＦＩＸはＮｅｔＦｌｏｗ技術を受けて策定されたため、ＮｅｔＦｌｏｗの技術をＩＰＦＩＸにも適用することができる。
【０００４】
上述のフロー情報を収集し、ネットワークシステムを監視するサーバからの検索要求に応じてフロー情報を提供する装置としてフロー情報処理装置が知られている（例えば、特許文献１）。
【特許文献１】特開２００７−２２８５１３号公報
【非特許文献１】RFC 3954 Cisco Systems NetFlow Services Export Version 9. B. Claise、October 2004、[online]、平成２０年６月１０日検索、 インターネット＜ＵＲＬ＜http://www.faqs.org/rfcs/rfc3954.html＞
【非特許文献２】RFC 5101 Specification of the IP Flow Information Export (IPFIX) Protocol for the Exchange of IP Traffic Flow Information、[online]、平成２０年６月１０日検索、 インターネット＜http://tools.ietf.org/html/rfc5101＞
【特許文献２】特開平８−１９１９５５号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記従来のフロー情報処理装置は、受信したフロー情報をデータベースなどに蓄え、サーバからのクエリに対して統計処理などを行っていた。フロー情報処理装置を多数のルータ装置を備えた大規模ネットワークで運用する場合では、大量のフロー情報を受信してデータベースへ蓄積することになる。そして、ネットワークシステムを監視するサーバからフロー情報の提供を要求されたときには、フロー情報処理装置は大量のフロー情報の中から従来のデータベース処理によって、要求されたフロー情報を検索し、サーバへ応答する。ネットワークシステムの規模が拡大するにつれて、データベースに格納するフロー情報の量も増大するため、サーバからの検索要求を受け付けてから応答するまでの時間が増大する、という問題があった。特に、フロー情報をハードディスク装置等の記憶装置にデータベースとして格納する場合では、大量のフロー情報から検索条件を満たすフロー情報を抽出する際に時間を要し、ハードディスク装置のアクセス時間がフロー情報の増大に伴って遅延し、さらに、フロー情報処理装置の処理負荷も増大する。
【０００６】
そこで本発明は、上記問題点に鑑みてなされたものであって、フロー情報処理装置を大規模ネットワークに適用して大量のフロー情報を蓄積する場合であっても検索処理を迅速に行うことを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、フロー情報または検索要求を受信する受信部と、前記受信したフロー情報を格納する記憶装置と、前記受信した検索要求に基づいて前記記憶装置に格納されたフロー情報を検索する検索部と、前記検索部が検索した結果を送信する送信部と、を備えたフロー情報処理装置において、前記受信部が受信した前記フロー情報を一時的に格納するフロー情報記憶部と、所定の条件が成立したときに、前記フロー情報記憶部に格納されたフロー情報から検索用情報を生成する検索用情報生成部と、を備え、前記検索部は、前記検索要求を受け付けると当該検索要求に含まれる検索条件で前記検索用情報を検索し、前記検索条件に合致する検索用情報から前記フロー情報を取得する。
【０００８】
また、前記検索用情報生成部は、前記フロー情報記憶部に格納されたフロー情報に含まれる項目の内容を抽出し、前記抽出した内容の出現頻度を演算し、前記フロー情報にインデックスを付与し、前記演算した出現頻度の順に前記項目の内容を設定し、前記インデックスが指し示すフロー情報の関係からビット情報を前記検索用情報として生成する。
【発明の効果】
【０００９】
したがって、本発明は、大量のフロー情報を蓄積した場合であっても記憶装置へのアクセスを削減することが可能となって、検索処理の速度を向上させることができる。また、記憶装置からフロー情報を取得する処理時間は従来例のように全てのフロー情報を検索する必要がないので、極めて短時間で処理を行うことができ、高速な検索が可能となる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の一実施形態を添付図面に基づいて説明する。
【００１１】
図１は、本発明の実施の形態を示し、フロー情報処理装置１０１を備えたネットワークシステムのブロック図である。
【００１２】
フロー情報処理装置１０１は、ＣＰＵ（プロセッサ）２、メモリ３、記憶装置（ストレージ装置）４、インタフェース５及び通信インターフェース１０４を備えた計算機を主体として構成される。
【００１３】
ＣＰＵ２は、メモリ３に格納されたプログラム（フロー処理部１０６）を実行することによって、後述するようにフロー情報２００の格納と検索用情報の生成と格納及び検索処理を行う。ＣＰＵ２は、メモリ３にロードされたフロー処理部１０６を実行し、受信したフロー情報２００を一旦メモリ３に設定したキャッシュ領域３０に格納し、所定の条件が成立したときに検索用情報であるランク付きビットマップインデックス７００を作成し、このランク付きビットマップインデックス７００とフロー情報２００を後述するようにファイルにまとめたフロー情報２００Ａを記憶装置１０９に格納する。なお、フロー処理部１０６は、ランク付きビットマップインデックス７００を生成する際に、メモリ３上に設定された設定テーブル３１に格納された生成条件を参照する。
【００１４】
記憶装置１０９は、ディスク装置等を含んで構成され、メモリ３のキャッシュ領域３０から転送されたファイル形式のフロー情報２００Ａと、フロー処理部１０６が生成したランク付きビットマップインデックス７００及びフロー処理部１０６等のプログラムを格納する。なお、フロー処理部１０６等のプログラムを格納する記憶媒体としてはＨＤＤ等で構成された記憶装置１０９に限定されるものではなく、光学ディスクや不揮発性半導体メモリ等に格納することができる。
【００１５】
インタフェース５は、記憶装置１０９、入力装置６、ディスプレイ７及通信インターフェース１０４などに接続される。入力装置１５は、担当者によって入力された情報を、インタフェース５を介してＣＰＵ２に送信する。ディスプレイ７は、ＣＰＵ２によって指示された情報を表示する。通信インターフェース１０４は、ＬＡＮなどのネットワーク８に接続されて信号（パケット）の送受信を行う。
【００１６】
ネットワーク８には、複数のルータ装置１０２と、複数のサーバ装置１０３が接続される。ルータ装置１０２は、サーバ装置１０３と外部のネットワークの通信を行い、ルータ装置１０２が処理した内容をフロー情報２００としてフロー情報処理装置１０１に送信する。また、複数のサーバ装置１０３のうちの何れかがネットワークシステムの監視を行い、フロー情報処理装置１０１に対してフロー情報２００を要求するクエリを発行する。
【００１７】
図２は、本発明に係わるネットワークシステムの機能ブロック図である。
【００１８】
フロー情報処理装置１０１は１台以上のルータ装置１０２と接続される。ルータ装置１０２は、パケットの転送を行うとフロー情報２００をフロー情報処理装置１０１に送信する。フロー情報処理装置１０１では、ルータ装置１０２からのフロー情報２００を通信インターフェース１０４で受信し、プロトコル処理部１０５によってプロトコルごとの前処理を行い、フロー処理部１０６にてフロー情報２００の蓄積とランク付きビットマップインデックス７００の生成と検索処理を実行する。プロトコル処理部１０５は、フロー情報処理装置１０１のＣＰＵ２で実行されるＯＳに含まれ、例えば、トランスポート層の処理を行う。プロトコル処理部１０５は、通信インターフェース１０４が受信した情報（パケット）のプロトコルから、受信した情報がフロー情報２００、クエリ及びその他の情報のいずれであるかを判定し、フロー情報２００であれば受信した情報に予め設定した処理を施してからフロー処理部１０６のフロー情報受信部１０７に転送し、クエリであれば受信したクエリに予め設定した処理を施してからフロー処理部１０６のクエリ受信部１１１に送信する。
【００１９】
ルータ装置１０２が発行したフロー情報２００はまずフロー情報受信部１０７に送られる。受信したフロー情報２００はフロー情報記憶部１０８を通じて記憶装置１０９にて記憶する。
【００２０】
フロー情報記憶部１０８は、図１に示したメモリ３のキャッシュ領域３０に設定され、受信したフロー情報２００を一時的に格納する。検索用情報生成部１１０は、所定の条件が成立する度に、キャッシュ領域３０のフロー情報記憶部１０８に格納されたフロー情報２００からランク付きビットマップインデックス７００を生成し、フロー情報記憶部１０８のフロー情報２００をファイル形式にしたフロー情報２００Ａと、ランク付きビットマップインデックス７００を記憶装置１０９に格納する。なお、フロー情報記憶部１０８は、キャッシュ領域３０のフロー情報２００が記憶装置１０９に書き込まれると、キャッシュ領域３０のフロー情報２００をクリアする。
【００２１】
検索用情報生成部１１０は、検索用情報の生成を開始する所定の条件として、例えば、予め設定した周期となったとき、またはキャッシュ領域３０がフロー情報２００で満たされて空き容量がなくなったとき（キャッシュ領域３０の空き容量が所定値＝０％）等を所定の条件の成立とすることができる。
【００２２】
所定の条件を予め設定した周期とした場合、検索用情報生成部１１０は、図示しないタイマなどで時間を監視し、所定の周期になるとキャッシュ領域３０のフロー情報記憶部１０８の全てのフロー情報２００を取得する。そして、検索用情報生成部１１０は、フロー情報２００から後述するようにランク付きビットマップインデックス７００を生成して記憶装置１０９に格納し、さらに取得したフロー情報２００をひとつのファイルにまとめてフロー情報２００Ａとして記憶装置１０９に格納する。すなわち、所定の周期毎に、ランク付きビットマップインデックス７００とフロー情報２００を含むファイルとしてのフロー情報２００Ａが記憶装置１０９に書き込まれていく。
【００２３】
フロー情報処理装置１０１は上述のように一台以上のサーバ装置１０３と接続されており、サーバ装置１０３は、フロー情報処理装置１０１が記憶するフロー情報２００を参照する際に、検索条件を記した要求（以下クエリ）をフロー情報処理装置１０１に対して送信する。
【００２４】
フロー情報処理装置１０１は、サーバ装置１０３からのクエリを通信インターフェース１０４で受信し、プロトコル処理部１０５によってプロトコルごとの前処理を行ってから、クエリ受信部１１１に送信する。
【００２５】
クエリ処理部１１２は、受信したクエリから検索条件を抽出して検索部１１３に転送する。検索部１１３は、検索条件に応じて記憶装置１０９から検索用情報を取り出し、検索処理を行う。
【００２６】
検索部１１３は、検索用情報であるランク付きビットマップインデックス７００を用いてクエリで要求されたフロー情報２００の検索を行って、検索処理の結果に応じたフロー情報を記憶装置１０９から取り出す。この際、ランク付きビットマップインデックス７００で検索した結果に加えて、フロー情報２００が検索要求に合致しているかどうかを記憶装置１０９のフロー情報２００で検索処理を行ってもよい。
【００２７】
検索部１１３で記憶装置１０９から取り出したフロー情報２００はクエリ処理部１１２を介して送信部１１４へ送られる。
【００２８】
検索結果であるフロー情報２００は送信部１１４からプロトコル処理部１０５を介して所定のプロトコルに整形された後、通信インターフェース１０４からネットワーク８を介してサーバ装置１０３へ送信される。
【００２９】
この送信処理は、検索結果が生成される度に実行しても良いし、一定期間または一定量の検索結果を蓄積してからサーバ装置１０３へ送信してもよい。
【００３０】
これら一連の処理における設定値（例えば、検索用情報の作成開始を判定する所定の条件や、ランク付きビットマップインデックス７００を作成するためのパラメータ等）は、管理者またはユーザが、後述するようなユーザインターフェース１１５を通じて入力装置６等から設定する。
【００３１】
図３は、フロー情報２００の一例を示す説明図である。
【００３２】
ルータ装置１０２から受信したフロー情報２００は上記従来例で述べたようにＮｅｔＦｌｏｗやＩＰＦＩＸによって定められた形式に則り、ルータ装置１０２が処理したパケットの情報が含まれる。フロー情報２００の一例としては、ＩＰパケットにおける送信元のＩＰアドレス２０１や送信先のＩＰアドレス２０２、プロトコル番号２０３に加え、ＩＰアドレス間で送受信されたパケットの個数２０４や合計のバイト数（２０５）等のフィールドを各エントリに備えた例を示す。
【００３３】
図４はサーバ装置１０３からフロー情報処理装置１０１に対して送信されるクエリに含まれる検索条件の一例である。
【００３４】
検索条件には、図２に存在したプロトコル番号３０１や、ＩＰアドレスにプレフィックス指定を加えたもの３０２の他に、フロー情報処理装置１０１がルータ装置１０２からフロー情報２００を受信した時刻の最小値３０３や時刻の最大値３０４を指定することもできる。この検索条件を受け付けた検索部１１３は、指定された時刻範囲（時刻最小値３０３や時刻最大値３０４の間）で、指定されたＩＰアドレス＋プレフィックス３０２で、指定されたプロトコル番号３０１を含むフロー情報２００をランク付きビットマップインデックス７００から検索することになる。
【００３５】
図５は、従来例による検索処理の一例を示すフローチャートである。
【００３６】
処理対象となるフロー情報２００は、フロー情報処理装置１０１が受信した全てのフロー情報２００である。この際、例として、フロー情報２００が記憶装置１０９を構成するハードディスク装置上に記録されており、記録を行った時間がファイル名に記されているために予め絞り込みが行える場合は、対象とするファイルの絞り込みを行ってもよい。
【００３７】
検索を行う際には、記憶装置１０９が記録している全フロー情報２００に対して（４０１）一件ずつ取り出し（４０２）、抽出したフロー情報２００が図３に示すような条件（クエリに含まれる検索条件）を満たしているか検査する（４０３）。検索条件を満たすフロー情報２００であると判定した場合は、当該フロー情報２００をサーバ装置１０３に送信する処理（４０４）を行い、検索条件が満たされない場合は次のフロー情報２００に移る。
【００３８】
このような従来例による検索手法においてフロー情報２００が、ハードディスク装置のような入出力によるオーバヘッドが大きいメディアに記録されている場合は、検索開始から検索結果の出力までの待ち時間が増大し、クエリの結果を返信するまでの時間が増大するだけでなく、フロー情報処理装置１０１全体の性能も低下する。
【００３９】
このような総当り的な検索方法に対する解決方法として、検索用情報を用いる方式がある。本発明では検索用情報として、ビットマップインデックスを用いる。
【００４０】
図６はビットマップインデックスの一例を示す説明図である。このビットマップインデックス５０１、５０２は、検索用情報生成部１１０がランク付きビットマップインデックス７００を生成する過程で作成するものである。
【００４１】
検索用情報生成部１１０は、所定の周期になると、図３に示したキャッシュ領域３０のフロー情報記憶部１０８に格納された複数のフロー情報２００から、図６に示すようにひとつのファイルで構成されるフロー情報２００Ａを生成する。
【００４２】
検索用情報生成部１１０は、フロー情報２００を特定するインデックスを行２１１を付加し、フロー情報２００のフィールドの項目名（要素）格納した列２１０と、各フロー情報２００の内容を格納する列２１２を含むファイルを生成する。例えば、図６の要素Ａは、図３に示したプロトコル番号に割り当て、各フロー情報２００に含まれるプロトコル番号を行方向に「４」、「１７」、「６」と順次格納する。同様に、要素Ｂには図３に示した送信元ＩＰアドレス２０１を割り当てて、行方向に各フロー情報２００の内容を格納し、要素Ｃには図３に示した送信先ＩＰアドレス２０２を割り当てて、行方向に各フロー情報２００の内容を格納してフロー情報２００Ａを生成する。
【００４３】
検索用情報生成部１１０は、フロー情報２００Ａのファイル名にフロー情報２００を受信した時刻を含める。この時刻は、例えば、フロー情報２００の受信時刻は、キャッシュ領域３０のフロー情報記憶部１０８に格納された複数のフロー情報２００のうち、最新の時刻と最も古い時刻を対にしたものを用いることができる。
【００４４】
フロー情報２００Ａは、このように、フロー情報２００を識別するインデックスを行２１１を行方向に設定し、フロー情報２００の要素（ＩＰアドレスやプロトコル番号、バイト数あるいはパケット数）を列２１０方向に設定し、インデックス行２１１に対応するフロー情報２００の要素の値を列２１２に格納する。
【００４５】
次に、検索用情報生成部１１０はフロー情報２００の要素（項目名）毎に、ビットマップインデックス５０１、５０２をそれぞれ生成する。ビットマップインデックス５０１は、フロー情報２００Ａの要素Ａに関するビットマップインデックスであり、検索用情報生成部１１０は列５１０にフロー情報２００Ａの要素Ａが取り得る値を設定し、行５１１にフロー情報２００Ａの行２１１に設定したインデックスを識別子として格納する。なお、インデックスとして行２１１に付与する識別子はユニークなシリアル値などを用いることができる。検索用情報生成部１１０は、行５１１の識別子毎に列５１２を設定して該当する要素Ａの値の行に「１」（ビット情報をオン）を設定する。例えば、フロー情報２００Ａのインデックス＝０のフロー情報は、要素Ａの値が「４」であるので、ビットマップインデックス５０１の識別子＝０の列５１２で要素Ａの値が「４」となる行に「１」を設定し、他の行に「０」（ビット情報をオフ）をセットする。検索用情報生成部１１０は、フロー情報２００Ａの各インデックスについて要素Ａの値に対応するビットマップインデックス５０１を作成する。
【００４６】
同様に、検索用情報生成部１１０は、列５２０にフロー情報２００Ａの要素Ｂが取り得る値を設定し、行５２１にフロー情報２００Ａの行２１１に設定したインデックスを識別子として格納する。検索用情報生成部１１０は、行５２１の識別子毎に列５２２を設定して該当する要素Ａの値の行に「１」を設定する。
【００４７】
以上の処理により検索用情報生成部１１０はフロー情報２００の要素毎にビットマップインデックス５０１、５０２を設定する。なお、上記ではフロー情報２００Ａの要素Ａ、Ｂのビットマップインデックスを作成する例を示したが、ビットマップインデックスを作成する要素は予め設定された要素についてのみ作成するようにしてもよい。また、この時点ではビットマップインデックス５０１、５０２はメモリ３上に保持される。
【００４８】
図１０のビットマップインデックス５０１Ａでは、フロー情報２００Ａの要素の値Ａについて、要素の識別子が０から９９まで存在し、各要素が０から４の値を取る場合は、５×１００の二値のテーブルを作成する。これがビットマップインデックスである。このビットマップインデックスに対して、行５１１の識別子１の値が１であるならば、値が１、識別子が１の行の値を１とし、識別子１におけるそれ以外の値は０とする。これを全要素に対して行う。
【００４９】
これらの要素について、値ＡがＸである要素を検索したい場合は、ビットマップインデックスにおける列５１０の値がＸの行を調べ、値が１であるものが該当するものとなる。
【００５０】
図６のビットマップインデックス５０１，５０２を利用する際には、検索部１１３が図７、図８に示すように、検索条件が複数のビットマップインデックス５０１、５０２を利用する場合は、検索部１１３が検索条件に応じて演算用テーブル５０３、５０４をメモリ３上に作成することができる。例として、フロー情報２００Ａの各要素の持つ値Ａと値Ｂに対してビットマップインデックス５０１、５０２が作成されている場合に、値Ａが１もしくは値Ｂが２の要素の識別子を検索したい場合は、ビットマップインデックス５０１、５０２における値Ａの列１と値Ｂの列２の値をＯＲ演算し、結果が１である識別子の情報を取り出せばよい。これを図７に示すように、演算用テーブル５０３としてメモリ３上に保持する。
【００５１】
同様に、値Ａが１かつ値Ｂが２の要素の識別子を検索したい場合は、ビットマップインデックス５０１、５０２における値Ａの列１と値Ｂの列２の値をＡＮＤ演算し、結果が１である識別子の情報を取り出せばよい。この演算結果を図８で示すように、演算用テーブル５０４としてメモリ３上に保持する。
【００５２】
そして、検索部１１３は、複数の検索条件について図７または図８の演算用テーブル５０３、５０４を用いてビットマップの検索を実行することができる。
【００５３】
図９は、本発明のランク付きビットマップインデックスと比較するため、ビットマップインデックス５０１，５０２を用いた検索の一例を示すフローチャートである。このフローチャートは、フロー処理部１０６の検索部１１３で実行することができる。
【００５４】
検索部１１３は、クエリ処理部１１２から受信した検索条件を取得する（６０１）。そして、検索用情報生成部１１０は、検索条件に含まれる期間（時刻範囲）から記憶装置１０９に格納されたビットマップインデックス５０１、５０２をメモリ３上に読み込んで。ビットマップインデックス５０１、５０２上で検索条件を満たす要素の値とビット（行）を検索する。検索部１１３は、ビットマップインデックス５０１、５０２で検索条件を満たす行があれば、当該行の値が１となっている識別子をフロー情報２００Ａのインデックスとして取得する（６０２）。このビットマップインデックス５０１の検索の際に、検索部１１３は上記図７、図８で示したような演算用テーブル５０３，５０４を作成し、これらのテーブルで検索を行っても良い。
【００５５】
次に、検索部１１３は、上記検索条件に含まれる期間に該当するフロー情報２００Ａを記憶装置１０９から取得し、上記インデックスに該当する列２１２からフロー情報２００を取得する（６０４、６０５）。そして、取得したフロー情報２００をクエリ処理部１１２及び送信部１１４を介してサーバ装置１０３に応答する（６０５）。なお、上記ステップ６０３〜６０５の処理は、上記ステップ６０２で取得した識別子の数だけ繰り返す。
【００５６】
この図９に示したビットマップインデックスを利用する処理と、上記図５に示した検索用情報を利用しない従来例の処理との違いは、検索用情報であるビットマップインデックス５０１，５０２を用いて予め検索条件に合致するフロー情報２００Ａを算出し（６０１）、該当するフロー情報２００Ａのみを取り出す（６０２）点である。これによりフロー情報２００Ａの全体を記憶装置１０９から読み込む回数が大幅に削減され、クエリの応答時間の短縮およびフロー情報処理装置１０１の高速化が期待できる。
【００５７】
このビットマップインデックス５０１、５０２の長所は、演算用テーブル５０３，５０４を生成することで、複数のビットマップインデックス間でＡＮＤやＯＲといった演算の容易性と高速性である。短所は、新たなデータ挿入の煩雑性と、検索用データの大型化である。
【００５８】
ただし、ビットマップインデックスに新たにデータを挿入する場合、新たに挿入したデータよりも後方のデータを１ビットずつシフトさせなければならない。また、検索用情報のサイズは要素一つにつき「要素が取る値の範囲×フロー情報数」となり、全要素に対してビットマップインデックスを適用した場合は、受信したフロー情報２００と同等の容量が検索用情報に必要となる。
【００５９】
本発明では、ビットマップインデックスの長所を生かし、短所を低減させたものとして「ランク付きビットマップインデックス」を提案する。
【００６０】
図１０に、値の取る範囲が０から２５５、フロー数が０から９９のランク付きビットマップインデックス７００の例を示す。図６に示したビットマップインデックス５０１，５０２では、フロー情報２００Ａの要素が取る値とビットマップインデックスの行が一対一で対応していたのに対し、図１０に示すランク付きビットマップインデックス７００では、新たに「その他」行（７０３）を追加し、出現頻度が低い（出現頻度が所定値未満）の要素をひとつの行にまとめることで、インデックスのデータ量を大幅に削減し、検索部１１３による検索を高速に行うようにしたものである。
【００６１】
検索用情報生成部１１０は、上記図６に示したと同様のビットマップインデックス５０１Ａを作成した後、フロー情報２００Ａの統計や設定値から「ランク数」と「ランキング」を算出する。そして、「ランキング」の上位「ランク数」までをランク付きビットマップインデックス７００に格納し、残りを「その他」列に格納する。
【００６２】
図１０のビットマップインデックス５０１Ａは、１００（０〜９９）のフロー情報２００が要素の値を１００（０〜９９）ある場合を示す。ビットマップインデックス５０１Ａは、１００個の要素の値を格納する列５１２と、フロー情報２００Ａのインデックスを識別子と格納する行５１１を備え、識別子に対応する列５１２に上記図６と同様に、フロー情報２００Ａの要素の値が該当する行に「１」を設定する。
【００６３】
次に、検索用情報生成部１１０は、列５１０の要素の値について「１」が設定されている数が大きい順に行方向でソートする。そして、検索用情報生成部１１０は、予め設定されたランク数Ｒまでの順位となる行を、ランク付きビットマップインデックス７００に加える。つまり、要素の値の出現頻度の高い順にランク数Ｒまでを、ビットマップインデックスとして利用する。
【００６４】
次に、ランク数Ｒから最下位の行までのビットを、ひとつの行にまとめ、この行をランク付きビットマップインデックス７００のその他７０３として加える。これにより、ランク付きビットマップインデックス７００のデータ量は（ランク数Ｒ＋１）×フロー情報２００の数となり、この例では「１」を設定するビットの領域を５×１００のビットで表現することができる。これに対してビットマップインデックス５０１Ａでは、「１」を設定するビットの領域は、要素の値の数×フロー情報２００の数となり、この例では、１００×１００のビット数が必要となる。
【００６５】
このように、ランク付きビットマップインデックス７００では、ビットマップインデックス５０１Ａに比して大幅にデータ量を削減でき、さらに、検索対象となる要素の値を格納する行は、ランク数Ｒとなって検索処理を大幅に高速化することができる。
【００６６】
ここで、フロー情報２００の要素となる、プロトコル番号やポート番号やＩＰアドレスなどは、要素の値が取り得る範囲は０ｈ〜ＦＦｈ、あるいは０ｈ〜ＦＦＦＦｈ等の広い範囲となる。そして、フロー情報２００の要素の値は、均等に出現することはほとんどなく、例えば、ネットワーク８内で出現するプロトコル番号は、常用されるプロトコルと、極めて希なプロトコルが存在する。さらに、フロー情報２００をサーバ装置１０３から検索する場合は、ネットワーク８やルータ装置１０２に障害などが発生した場合であるので、リトライなどによって特定のプロトコルの出現頻度が高くなる傾向がある。
【００６７】
そこで、出現頻度の高い要素の値についてはビットマップインデックス５０１Ａとして使用し、出現頻度の低い要素の値についてはその他７０３としてランク付きビットマップインデックス７００を生成する。
【００６８】
サーバ装置１０３からのクエリを検索部１１３が実行し、検索条件がその他７０３に該当する場合（要素の値の出現頻度が低い）は、上記図５に示したように、記憶装置１０９のフロー情報２００Ａから検索するため、検索処理に要する時間は従来例と変わらない。しかし、サーバ装置１０３からのクエリを検索部１１３が実行し、検索条件がランク数Ｒの順位の要素の値と一致すれば、ランク付きビットマップインデックス７００からフロー情報２００Ａのインデックスを取得できるので、このインデックスで目的のフロー情報２００Ａを記憶装置１０９から取得することで、前記従来例に比して極めて高速にアクセスすることが可能となる。
【００６９】
そして、上述したように、フロー情報２００Ａの要素Ａの値は、一般的に均一ではなく偏りを持つものであるから、検索条件がその他７０３となることは頻繁に発生せず、ほとんどの検索条件がランク数Ｒの範囲で一致するので、検索処理を極めて高速に行うことができるのである。
【００７０】
さらに、ビットマップインデックス５０１Ａは、フロー情報２００Ａの要素毎に生成する必要があるため、要素の値の数が大きく、フロー情報２００が大量にある場合では、ひとつのフロー情報２００Ａに対するビットマップインデックス５０１Ａの数が増大してデータ量が大きくなるため、検索部１１３が記憶装置１０９からビットマップインデックス５０１Ａを読み込む際の時間も増大してしまう。
【００７１】
これに対して、要素の値の数を制限したランク付きビットマップインデックス７００では、要素の値の数が大きく、フロー情報２００が大量にある場合でも、行の数は所定のランク数Ｒ＋１を維持できるので、データ量が過大になるのを防いで、検索部１１３が記憶装置１０９からランク付きビットマップインデックス７００を読み込む際の時間が増大するのを防止して、検索処理の高速化に寄与することができるのである。
【００７２】
図１１は、図２に示したユーザインターフェース１１５の一例を示し、ランク付きビットマップインデックス７００を生成する条件を設定するユーザインターフェースで、ディスプレイ７に表示される画面イメージである。
【００７３】
ユーザインターフェース１１５で、フロー情報２００に含まれる要素のうちランク付きビットマップインデックス７００を生成する要素（図中蓄積項目）１４００を決定するビットマップインデックス作成１４０１と、要素の出現頻度の順位または比率での何れかを指定するランク設定１４０２とを含む。
【００７４】
図示の例では、フロー情報２００の要素の内、送信元ＩＰアドレス、送信先ＩＰアドレス、プロトコル番号及び送信先ポート番号の要素についてビットマップインデックス作成１４０１が丸印に設定されて、ビットマップインデックスの生成を選択している。そして、信元ＩＰアドレス、送信先ＩＰアドレスについてはランク設定１４０２のランク数Ｒを「５」に設定し、出現頻度が上位４位までの要素をビットマップインデックスに格納し、５位以下をその他７０３にまとめることを示す。また、プロトコル番号については、フロー情報２００の要素のうち、出現頻度の上位９５％までの要素についてビットマップインデックスに格納し、残りの５％の出現頻度となる要素は、その他７０３に格納することを示す。送信先ポート番号も同様であり、出現頻度の上位９０％をビットマップインデックスに格納することを示す。これらの設定は、管理者などが入力装置６を構成するマウスやキーボードにより入力する。
【００７５】
フロー処理部１０６は、ユーザインターフェース１１５で設定されたランク付きビットマップインデックス７００の生成条件をメモリ３上の設定テーブル３１に格納し、検索用情報生成部１１０を実行するときに設定テーブル３１に設定された生成条件を参照し、ランク付きビットマップインデックス７００を生成する。
【００７６】
図１２は、ランク付きビットマップインデックス７００を生成する処理の一例を示すフローチャートである。この処理は、フロー処理部１０６の検索用情報生成部１１０が所定の条件を満たしたときに実行されるプログラムである。なお、検索用情報生成部１１０は、上述したように、所定の周期（時間）となったとき、またはキャッシュ領域３０の空き容量がなくなったときに、所定の条件を満たしたと判定し、図１２の処理を開始する。
【００７７】
まず、ステップ１００１では、検索用情報生成部１１０がキャッシュ領域３０のフロー情報記憶部１０８に格納されている全てのフロー情報２００を処理対象としてステップ１００４までのループ処理を開始する。
【００７８】
ステップ１００２では、検索用情報生成部１１０がメモリ３上の設定テーブル３１を読み込んで、図３に示したフロー情報２００のフィールド２０１〜２０５のうち、図１１のユーザインターフェース１１５のビットマップインデックス作成１４０１が選択されている項目を取得する。検索用情報生成部１１０は、取得した項目をランク付きビットマップインデックス７００の作成対象の要素とする。
【００７９】
ステップ１００３では、検索用情報生成部１１０がひとつのフロー情報２００を読み込んで、上記ステップ１００２で取得した作成対象の要素のフィールド２０１〜２０５の値を抽出する。
【００８０】
次に、ステップ１００４では、検索用情報生成部１１０が上記ステップ１００３で抽出したフィールドの値の出現頻度（出現回数）に１を加算する。すなわち、図６のビットマップインデックス５０１の値を格納する列５１０に対応するフロー情報２００の識別子ごとに列５１２の値に「１」を設定する。
【００８１】
検索用情報生成部１１０は、上記ステップ１００２〜１００４のループ処理で、ひとつのフロー情報２００の作成対象の要素の出現頻度を求めると、ステップ１００１に戻って次のフロー情報２００について同様の処理を行う。そして、フロー情報記憶部１０８の全てのフロー情報２００について、ランク付きビットマップインデックス７００を作成する対象となっている各要素の値の出現頻度の演算が完了すると、ステップ１００５の処理に進む。
【００８２】
ステップ１００５では、検索用情報生成部１１０が、ランク付きビットマップインデックス７００の作成対象の各フィールド（要素）について、ステップ１００６、１００７のループ処理を行う。なお、ステップ１００５では、ランク付きビットマップインデックス７００の作成対象の要素毎に図６で示したビットマップインデックス５０１、５０２を生成しておく。
【００８３】
ステップ１００６では、検索用情報生成部１１０がフィールド２０１〜２０５の項目毎に上記ステップ１００４で求めた値の出現頻度からビットマップインデックスを作成する。すなわち、上記ステップ１００４では、検索用情報生成部１１０が、フロー情報２００のインデックス（識別子）毎に図６に示す列５１２を作成したので、要素毎のビットマップインデックス５０１に対して、フロー情報２００の識別子毎の列５１２を加える。この処理によって、現在着目しているフィールド（要素）のビットマップインデックス５０１が生成される。
【００８４】
次に、ステップ１００７では、検索用情報生成部１１０が設定テーブル３１からランク数Ｒを読み込んで、上記図１０で示したように、出現頻度の高い値の順にビットマップインデックス５０１Ａを列方向にソートし、出現頻度の上位「ランク数Ｒ」までのビットマップインデックス５０１Ａを保持し、出現頻度の順位がランク数Ｒ＋１以降の行の値を、その他７０３の行にまとめて要素毎のランク付きビットマップインデックス７００を生成する。
【００８５】
検索用情報生成部１１０は、ひとつのフィールドについてランク付きビットマップインデックス７００を生成すると、ステップ１００５に戻って、次のフィールドについてランク付きビットマップインデックス７００を生成する処理を繰り返し、全てのフィールドにいついてランク付きビットマップインデックス７００を生成する。
【００８６】
上記処理により、図３に示したフロー情報２００のフィールド２０１〜２０５のうち、図１１のユーザインターフェース１１５でビットマップインデックス作成１４０１が選択されたフィールド毎に、指定されたランク数Ｒ＋１の行を備えるランク付きビットマップインデックス７００が生成される。なお、上記ではランク数Ｒで指定された場合を示したが、ランク数が上位からの比率で指示された場合については後述する。
【００８７】
検索用情報生成部１１０は、全てのフィールド（要素）毎のランク付きビットマップインデックス７００の作成が完了すると、ステップ１００８で、メモリ３上に保持していた各要素のビットマップインデックス７００を記憶措置１０９に書き出す。このとき、検索用情報生成部１１０は、キャッシュ領域３０のフロー情報記憶部１０８のフロー情報２００にインデックス２１１を付加してから、上述したようにタイムスタンプをファイル名とする一つのファイルにまとめ、このファイルをフロー情報２００Ａとして記憶装置１０９に格納する。
【００８８】
さらに、検索用情報生成部１１０は、検索処理の高速化を図るため、インデックス情報１２００を生成して記憶装置１０９に格納する。インデックス情報１２００は、図１３で示すように、一つのエントリ１２０１にフロー情報２００の収集範囲の開始時刻を示す開始時間１２０２と、フロー情報２００Ａに含まれるフロー情報の数を示すフロー数１２０３と、フロー情報２００Ａに対応するランク付きビットマップインデックス７００Ａ，７００Ｂのランク数Ｒと、ビットマップインデックス７００Ａ、７００Ｂの格納位置を示すインデックス１２０５を含む。
【００８９】
以上の処理によって、フロー情報処理装置１０１がルータ装置１０２から受信したフロー情報２００を収集し、所定の条件が成立すると、検索用情報生成部１１０は、ユーザインターフェース１１５で指定された要素（フィールド）毎にランク付きビットマップインデックス７００を生成する。そして、検索用情報生成部１１０は、図１３で示すように、フロー情報２００をひとつのファイルにまとめたフロー情報２００Ａと、ランク付きビットマップインデックス７００のインデックスとするインデックス情報１２００を生成して記憶装置１０９に格納する。
【００９０】
次に、ランク付きビットマップインデックス７００を利用する検索処理について説明する。
【００９１】
図１４にランク付きビットマップインデックスを用いる検索処理のフローチャートの一例を示す。この処理は、クエリ受信部１１１が検索条件を含むクエリを受け付けて、クエリ処理部１１２が検索部１１３に検索条件を通知し、検索部１１３が処理を実行する。
【００９２】
まず、ステップ８０１で検索部１１３は、サーバ装置１０３からのクエリを受け取るとその中から検索条件を取り出す。なお、検索条件には、時刻と、要素及び要素の値が含まれる。
【００９３】
ステップ８０２では、検索部１１３が記憶装置１０９に格納されたインデックス情報１２００を参照し、開始時間１２０２から所定時間以内に検索条件の時刻が含まれるエントリを特定する。そして、特定したエントリについて、検索条件に含まれる要素からインデックス１２０５を検索し、検索対象のランク付きビットマップインデックス７００をメモリ３に読み込む。次に、検索部１１３は、後述する図１５のように、検索条件に合致するフロー情報をランク付きビットマップインデックス７００によって検索し、検索条件に一致するビットがランク数Ｒ内の行にあれば、フロー情報２００Ａのインデックスに対応する識別子を取得する。一方、検索条件に一致するビットが「その他」であれば、検索結果は「その他」として記憶する。この処理は、検索条件に含まれるフロー情報２００の要素毎のランク付きビットマップインデックス７００で行われる。
【００９４】
検索部１１３は、上記ステップ８０２で取得した識別子の数（取得するフロー情報の数）だけステップ８０３〜８０７の処理を繰り返す。
【００９５】
まず、ステップ８０４では、記憶装置１０９から検索条件に含まれる時刻を含むフロー情報２００Ａを特定し、取得した識別子に対応するフロー情報２００Ａをメモリ３に読み込む。
【００９６】
ステップ８０５では、検索部１１３がメモリ３に読み込んだフロー情報２００Ａについてランク付きビットマップインデックス７００の「その他」に該当しているかどうか判定する。読み込んだフロー情報２００Ａが「その他」に該当していない場合はステップ８０７の送信処理へ移行する。一方、上記ステップ８０２のランク付きビットマップインデックス７００の検索の結果が「その他」に該当している場合は対象のフロー情報２００Ａが検索条件に合致している保障がないためステップ８０６の確認処理を行う。
【００９７】
ステップ８０６では、上記図５に示した従来の検索処理によって、検索部１１３は検索条件に一致するフロー情報２００Ａを記憶装置１０９に格納されているフロー情報２００Ａから検索する。そして、検索条件に一致するフロー情報２００Ａがあればステップ８０７へ進む。検索条件に一致するフロー情報２００Ａがない場合には、ステップ８０３へ戻って次の識別子について上記処理を繰り返す。
【００９８】
ステップ８０７では、ステップ８０４またはステップ８０６で読み込んだ、フロー情報２００Ａをクエリに対する応答としてサーバ装置１０３に返信する。
【００９９】
以上の検索処理により、メモリ３上に読み込んだランク付きビットマップインデックス７００で、検索条件に一致するビットがあれば識別子を取得することでフロー情報２００Ａ内のインデックスを得ることができるので、ステップ８０４で行う記憶装置１０９からフロー情報２００Ａを取得する処理時間は上記従来例のように全てのフロー情報２００Ａを検索する必要がないので、極めて短時間で処理を行うことが可能となる。そして、ランク付きビットマップインデックス７００の検索結果が「その他」の場合のみ、従来例と同様に記憶装置１０９のフロー情報２００Ａを検索することになる。しかしながら、上述したようにフロー情報２００Ａの特性から、ランク付きビットマップインデックス７００の検索結果が「その他」となる機会は少ないため、検索処理全体としては従来例に比して極めて高速に処理することが可能となるのである。
【０１００】
図１５は上記図１３のステップ８０２で示したランク付きビットマップインデックス７００を用いる検索処理のフローチャートを示す。
【０１０１】
ステップ９０１では、検索部１１３は、まず上記図７に示した演算用テーブル５０３と同様にして検索条件に応じた演算用テーブルをメモリ３上に作成する。この演算用テーブルは、なお、演算用テーブルは、検索条件が単一の要素に対して単一の検索条件の場合は、図７に示したランク付きビットマップインデックス７００のランク数Ｒに対応する部分となる。
【０１０２】
次に、ステップ９０２では、検索部１１３がその他用テーブルをメモリ３上に作成する。その他用テーブルは、ランク付きビットマップインデックス７００の検索結果を管理するため、検索条件がランク数Ｒの要素の値に一致しなかった回数を計数するもので、検索する要素の値に対する検索回数を格納可能なテーブルであればよい。
【０１０３】
次に、ステップ９０３〜９０６では、検索条件のパラメータ（例えば、要素）の数だけランク付きビットマップインデックス７００を用いた演算を繰り返す。ステップ９０４では、検索部１１３が検索条件のパラメータに一致するビット列（図１０の列７１０でヒットした要素の値に一致する行）を抽出する。次に、ステップ９０５では、抽出したビット列をステップ９０１で生成した演算用テーブルに格納し、検索条件のパラメータと比較を行う。この比較演算の結果である要素の値に対応する識別子を演算用テーブルに格納する。
【０１０４】
次に、ステップ９０６では、上記ステップ９０４の処理で、要素の値としてヒットした行が「その他」であるか否かを判定し、「その他」であればステップ９０７に進み、ランク数Ｒ内の要素にヒットした場合は、ステップ９０３に戻って次のパラメータに関して検索を実施する。
【０１０５】
ステップ９０７では、上記ステップ９０２で作成したその他用テーブルに「１」を加算して更新する。
【０１０６】
本発明では、検索部１１３が記憶装置１０９から取り出したフロー情報２００（ランク付きビットマップインデックス７００）に占める「その他」以外の割合を「ヒット率」、「その他」の割合を「ミス率」と呼ぶ。ヒット率が高いほど記憶装置１０９からフロー情報２００Ａを読み込むオーバヘッドが減り、フロー情報処理装置１０１全体の性能が向上する。
【０１０７】
以上の処理により、検索条件のパラメータの数だけランク付きビットマップインデックス７００を用いて検索を行うことで、検索条件に一致したビット列が演算用テーブルに格納され、ランク数Ｒ内の要素の値でヒットしなかった回数がその他用テーブルに記録される。検索部１１３は、演算用テーブルに格納された要素の値の数と、その他用テーブルの値の和で、演算用テーブルに格納された要素の値の数を除してヒット率を求めることができる。また、検索部１１３は、演算用テーブルに格納された要素の値の数と、その他用テーブルの値の和で、その他用テーブルの値を除してミス率を求めることができる。
【０１０８】
さらに、「その他」の行を参照したかどうか記録することでステップ９０４の段階で追加の処理である記憶装置１０９からの識別子の検索が必要か否かを知ることができる。
【０１０９】
図１６は、フロー情報処理装置１０１に入力されたクエリの一例を示し、図１７は、図１６のクエリに対する検索処理の結果の一例を示す説明図である。
【０１１０】
図１６では、サーバ装置１０３がフロー情報処理装置１０１に要求したクエリ１３０１を示す。クエリ１３０１には、サーバ装置１０３が要求する情報（抽出情報）として、送信元ＩＰアドレスと、送信先ＩＰアドレスが設定される。抽出情報の読み出し先として、フロー情報２００Ａが指定される。抽出情報の検索条件（検索情報）としては、開始時刻と終了時刻及び要素の値としてプロトコル番号が指定される。
【０１１１】
上記クエリ１３０１を受け付けたフロー情報処理装置１０１が、上記図１４、図１５の検索処理を行ってサーバ装置１０３へ出力した結果が図１７に示すクエリ出力１３０２となる。図１７のクエリ出力は、検索条件の開始時刻と終了時刻の期間で、要素の値がプロトコル番号＝６のフロー情報２００Ａから送信先ＩＰアドレスと送信元ＩＰアドレスが識別子（フローＩＤ）毎に出力される。
【０１１２】
上記図１６，図１７の例では、要素（プロトコル番号）の値（＝６）は、図１０のランク付きビットマップインデックス７００の最初の行でヒットする。検索部１１３は、ヒットした行の識別子（＝１，２，４）を取得する。検索部１１３は、取得した識別子に対応するフロー情報２００Ａのインデックスから抽出情報を読み込んでサーバ装置１０３に応答する。
【０１１３】
以上により、メモリ３上に読み込んだランク付きビットマップインデックス７００で、検索条件に一致するビットがあれば識別子を取得し、この識別子からフロー情報２００Ａ内のインデックスを得ることができるので、記憶装置１０９からフロー情報２００Ａを取得する処理時間は上記従来例のように全てのフロー情報２００Ａを検索する必要がないので、極めて短時間で処理を行うことが可能となり、フロー情報処理装置１０１が大量のフロー情報２００Ａを管理する場合であっても、高速な検索が可能となる。
【０１１４】
図１８は、上記図１１に示したユーザーインターフェース１１５でランク設定を比率で指定した場合に「ランク数」または「ランキング」をフロー情報２００内の各要素の出現頻度から決定するようにしたものである。
【０１１５】
ランク付きビットマップインデックス７００における「ランク数」「ランキング」はフロー情報２００内の各要素の出現頻度の統計は、フロー情報２００を受信するたびに行ってもよく、特定時間や特定個数ごとに一括して行ってもよい。
【０１１６】
以下に「ランク数」または「ランキング」を予め設定された比率に基づいて決定する例を示す。
【０１１７】
図１８は、ランク付きビットマップインデックス７００を生成する処理の一例を示すフローチャートである。この処理は、図１２と同様に、フロー処理部１０６の検索用情報生成部１１０が所定の条件を満たしたときに実行されるプログラムである。なお、検索用情報生成部１１０は、上述したように、所定の周期（時間）となったとき、またはキャッシュ領域３０の空き容量がなくなったときに、所定の条件を満たしたと判定し、図１８の処理を開始する。
【０１１８】
まず、ステップ１１０１では、検索用情報生成部１１０がキャッシュ領域３０のフロー情報記憶部１０８に格納されている全てのフロー情報２００を処理対象としてステップ１１０４までのループ処理を開始する。
【０１１９】
ステップ１１０２では、検索用情報生成部１１０がメモリ３上の設定テーブル３１を読み込んで、図３に示したフロー情報２００のフィールド２０１〜２０５のうち、図１１のユーザインターフェース１１５のビットマップインデックス作成１４０１が選択され、かつ、ランク設定１４０２が上位からの比率で指定された項目を取得する。検索用情報生成部１１０は、取得した項目をランク付きビットマップインデックス７００の作成対象の要素とする。
【０１２０】
ステップ１１０３では、検索用情報生成部１１０がキャッシュ領域３０からひとつのフロー情報２００を読み込んで、上記ステップ１１０２で取得した作成対象の要素のフィールド２０１〜２０５の値を抽出する。
【０１２１】
次に、ステップ１１０４では、検索用情報生成部１１０が上記ステップ１１０３で抽出したフィールドの値の出現頻度（出現回数）に１を加算する。すなわち、図６のビットマップインデックス５０１の値を格納する列５１０に対応するフロー情報２００の識別子ごとに列５１２の値に「１」を設定する。
【０１２２】
検索用情報生成部１１０は、上記ステップ１１０２〜１００４のループ処理で、ひとつのフロー情報２００の作成対象の要素の出現頻度を求めると、ステップ１１０１に戻って次のフロー情報２００について同様の処理を行う。そして、フロー情報記憶部１０８の全てのフロー情報２００について、ランク付きビットマップインデックス７００を作成する対象となっている各要素の値の出現頻度の演算が完了すると、ステップ１１０５の処理に進む。
【０１２３】
ステップ１１０５では、ランクの順位（ランキング）を示す変数Ｎに初期値として「１」を設定する。
【０１２４】
ステップ１１０６では、検索用情報生成部１１０がフィールド２０１〜２０５の項目毎に上記ステップ１１０４で求めた値の出現頻度の高い順にソートを行って、出現順位の最も高いフィールドの値に変数Ｎを設定し、上記図１２のステップ１００６と同様に、現在着目しているフィールド（要素）のビットマップインデックス５０１を生成する。
【０１２５】
次に、ステップ１１０７では、現在着目しているフィールドの値の変数Ｎの値が１〜Ｎの数と、作成対象のフロー情報２００の全体の数の比率から出現頻度が第１位から第Ｎ位までの値の数の割合を求める。
【０１２６】
ステップ１１０８では、ユーザーインターフェース１１５で指定された比率と、ステップ１１０７で求めた割合を比較して、この割合が指定された比率を超えたか否かを判定する。割合が指定された比率を超えていれば、ステップ１１０９に進みランク付きビットマップインデックス７００を生成し、割合が指定された比率以下であれば、ステップ１１１０に進んで変数Ｎに１を加えてから、上記ステップ１１０６に戻って次の順位Ｎのビットマップインデックスを作成する。
【０１２７】
ステップ１１０９では、作成対象のフロー情報２００の全体の数に対するフィールドの値の変数Ｎの値が１〜Ｎの数の割合が、指定された比率に達したので、変数Ｎ＝１〜Ｎまでのランク数の要素の値についてランク付きビットマップインデックス７００を生成し、変数Ｎ＝Ｎ＋１以降の順位の要素の値についてはその他の行７０３にまとめてランク付きビットマップインデックス７００を完成させる。
【０１２８】
以上のように、ユーザーインターフェース１１５にてランク設定１４０２が上位からの比率の場合には、作成対象のフロー情報２００の全体の数に対するフィールドの値の変数Ｎの値が１〜Ｎの数の割合が指定された比率となるランク数Ｒが自動的に決定されるのである。これにより、検索処理を行ったときには、検索条件が出現頻度の高い要素の値で一致する確率が向上し、検索のミスヒットによってフロー情報２００Ａのインデックスを記憶装置１０９から検索する機会を低減することができる。したがって、フロー情報処理装置１０１を大規模なネットワークに設置して、大量のフロー情報２００を収集する場合でも、検索処理の速度が低下するのを防ぎ、フロー情報処理装置１０１の負荷が過大になるのを防ぐことができる。
【０１２９】
なお、上記実施形態ではフロー情報を送信する装置としてルーター装置を用いる例を示したが、パケットを転送して、転送した結果をフロー情報として出力可能な装置であればよく、例えば、Ｌ３（Layer 3）スイッチやロードバランサ等の通信装置を用いることができる。
【産業上の利用可能性】
【０１３０】
以上のように、本発明は、ネットワークシステムに設置されてフロー情報を収集し、収集したフロー情報を検索する管理装置に適用することができる。また、フロー情報の記憶や検索のみならず、時間ごとに大量のログ情報などを処理する装置全般において、記憶装置の容量削減と、検索の高速化を実現できる。
【図面の簡単な説明】
【０１３１】
【図１】本発明のフロー情報処理装置を備えたネットワークシステムのブロック図。
【図２】本発明に係わるフロー情報処理装置とネットワークシステムの機能要素を示すブロック図。
【図３】本発明に係わるフロー情報の一例を示す説明図。
【図４】サーバ装置から送信されるクエリの一例を示す説明図。
【図５】従来例による検索処理の一例を示すフローチャート。
【図６】フロー情報からビットマップインデックスを生成する過程を示す説明図。
【図７】ビットマップインデックスから検索条件に応じて生成された演算用テーブルの一例を示す説明図。
【図８】ビットマップインデックスから検索条件に応じて生成された演算用テーブルの一例を示す説明図。
【図９】ビットマップインデックスを用いた検索処理の一例を示すフローチャート。
【図１０】ビットマップインデックスからランク付きビットマップインデックスを生成する過程を示す説明図。
【図１１】ユーザーインターフェースの一例を示す画面イメージ。
【図１２】ランク付きビットマップインデックスの生成処理の一例を示すフローチャート。
【図１３】フロー情報からランク付きビットマップインデックスを生成し、さらにインデックス情報を生成する過程を示す説明図。
【図１４】ランク付きビットマップインデックスを用いた検索処理の一例を示すフローチャート。
【図１５】図１４のステップ８０２で行われるランク付きビットマップインデックスの検索処理の一例を示すサブルーチン。
【図１６】フロー情報処理装置に入力されたクエリの一例を示す説明図。
【図１７】フロー情報処理装置から出力されたクエリに対する応答の一例を示す説明図。
【図１８】ユーザーインターフェースのランク設定が比率の場合のランク付きビットマップインデックスの生成処理を示すフローチャート。
【符号の説明】
【０１３２】
１０１  フロー処理装置
１０２  ルータ装置
１０３  サーバ装置
１０４  通信インターフェース
１０５  プロトコル処理部
１０６  フロー処理部
１０７  フロー情報受信部
１０８  フロー情報記憶部
１０９  記憶装置
１１０  検索用情報生成部
１１１  クエリ受信部
１１２  クエリ処理部
１１３  検索部
１１４  送信部
１１５  ユーザインタフェース
１２００  インデックス情報
２００、２００Ａ  フロー情報
５０１  ビットマップインデックス
７００  ランク付きビットマップインデックス
【図３】
2010068279.tif 000003
【図４】
2010068279.tif 000004
【図５】
2010068279.tif 000005
【図６】
2010068279.tif 000006
【図７】
2010068279.tif 000007
【図８】
2010068279.tif 000008
【図９】
2010068279.tif 000009
【図１０】
2010068279.tif 000010
【図１１】
2010068279.tif 000011
【図１２】
2010068279.tif 000012
【図１３】
2010068279.tif 000013
【図１４】
2010068279.tif 000014
【図１５】
2010068279.tif 000015
【図１６】
2010068279.tif 000016
【図１７】
2010068279.tif 000017
【図１８】
2010068279.tif 000018
【図１】
2010068279.tif 000019
【図２】
2010068279.tif 000020