(57)【特許請求の範囲】
【請求項１】
ネットフローデータを収集するためのシステムであって、
複数のフローレコードを受け取る手段（２２）と、
定義されたフィルタパラメータに基づいて、前記複数のフローレコードに含まれた情報をフィルタリングする手段（２３）と、
フィルタリングされたフローレコードに含まれた前記情報からキー及び該キーに対応する値を抽出する手段（２３）と、
所定の数のキーを格納するためのキーデータ構造（３１）と、
前記キーデータ構造（３１）が追加のキーを格納する容量を有するかどうか決定する手段（２４）と、
前記キーデータ構造（３１）が追加のキーを格納する容量を有すると決定される場合は、前記抽出されたキーを前記キーデータ構造（３１）に追加する手段（２４）と、
前記キーデータ構造（３１）が追加のキーを格納する容量を有さないと決定される場合は、前記キーデータ構造（３１）内に格納された前記抽出されたキーを統計的に解析して、前記格納された抽出されたキーのうちの少なくとも１つを削除する手段（２４）とを備えるシステム。
【請求項２】
前記キーに対応する値を格納する値データ構造（３５）と、
前記抽出された値を前記値データ構造（３５）に追加する手段（２４）と
をさらに備える、請求項１に記載のシステム。
【請求項３】
前記複数のフローレコードに含まれた情報をフィルタリングする手段（２３）が、フローレコードのフィールドからの少なくとも１つの値を、該フローレコードのフィールドについて定義されたフィルタパラメータと比較するように構成されている、請求項１又は２に記載のシステム。
【請求項４】
前記キーデータ構造（３１）に格納される複数のキーを格納するハッシュテーブル（３４）と、
前記ハッシュテーブル（３４）を使用して前記キーの探索を実施することによって、抽出されたキーが前記キーデータ構造（３１）内に格納されているかどうか決定する手段（２４）と
をさらに備える、請求項１〜３のいずれか一項に記載のシステム。
【請求項５】
抽出されたキーが前記キーデータ構造（３１）に格納されていると決定される場合は、前記キーに対応して前記格納された値を増やす手段（２４）をさらに備える、請求項４に記載のシステム。
【請求項６】
前記フローレコードからの前記それぞれの抽出された値で前記格納された値が増やされる、請求項５に記載のシステム。
【請求項７】
前記キーデータ構造（３１）はリンクされたリストのデータ構造であり、前記キーデータ構造の空の要素がフリーリスト（３３）として互いにリンクされる、請求項１〜６のいずれか一項に記載のシステム。
【請求項８】
前記フリーリスト（３３）の始まりが、前記キーデータ構造（３１）内で第１の空の要素へのポインタ（３２）として格納されている、請求項７に記載のシステム。
【請求項９】
前記抽出されたキーを統計的に解析する手段（２４）が、前記格納されたキーに対応する前記値の統計的解析を実施し、前記統計的解析に基づいて前記格納されたキーのうちの少なくとも１つを削除するように構成される、請求項１〜８のいずれか一項に記載のシステム。
【請求項１０】
前記統計的解析が、前記格納されたキーに対応する各値の中央値の計算、及び前記計算された中央値より小さい関連する値を有する前記格納されたキーの削除を含む、請求項９に記載のシステム。
【請求項１１】
前記定義されたフィルタパラメータが、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ＩＰポート、宛先ＩＰポート、ＩＰプロトコルバージョン、フロー内のオクテットの数、フロー内のパケット数、及びサービスタイプのうちの１つ又は複数を備える、請求項１〜１０のいずれか一項に記載のシステム。
【請求項１２】
前記キーデータ構造（３１）内の要素をソートする手段（２４）と、
前記ソートされたキーデータ構造（３１）からの所定数の格納されたキーを識別する手段（２４）と
をさらに備える、請求項１〜１１のいずれか一項に記載のシステム。
【請求項１３】
前記識別された所定数の格納されたキーに基づいてチャートを作成する手段（２６）と、前記フローレコードが前記システムによって処理される間、前記値で前記チャートを繰り返し更新する手段（２７）とをさらに備える、請求項１２に記載のシステム。
【請求項１４】
ネットフローデータを収集するための方法であって、
複数のフローレコードを受け取るステップと、
定義されたフィルタパラメータに基づいて前記複数のフローレコードに含まれた情報をフィルタリングするステップと、
フィルタリングされたフローレコードに含まれた情報からキー及び該キーに対応する値を抽出するステップ（４１）と、
所定の数のキーを格納するためのキーデータ構造を用意するステップと、
それぞれの抽出されたキーについて、前記キーデータ構造が追加のキーを格納する容量を有するかどうか決定するステップ（４５）と、
前記キーデータ構造が追加のキーを格納する容量を有すると決定される場合は、前記抽出されたキーを前記所定の数のキーを格納するためのキーデータ構造に追加するステップ（４６）と、
前記キーデータ構造が追加のキーを格納する容量を有さないと決定される場合は、前記抽出されたキーを前記データ構造に追加する前に、前記キーデータ構造に格納された前記抽出されたキーを統計的に解析して、前記格納された抽出されたキーのうちの少なくとも１つを削除するステップ（４７〜４９）とを含む方法。
【請求項１５】
請求項１〜１３のいずれか一項に記載のシステムとして構成されるように、又は請求項１４に記載の方法を実施するようにプログラマブル装置を構成するためのコンピュータ判読可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク通信及び使用解析に関し、詳細には、ネットフローデータを収集し処理するための方法及び装置に関する。
【背景技術】
【０００２】
世界中でデータを移送するパケット式データネットワークが普及している。パケット式データネットワークは、典型的に、あるコンピュータと別のコンピュータの間で伝送するためにデータをパケットにフォーマットする。これらのパケットは、パケットデータ及びルーティングに関する情報を含むヘッダを含む。データネットワークは、ルータを使用して発信元コンピュータから宛先コンピュータにこれらのパケットを送り、このルータは、パケットヘッダ内のルーティング情報を使用して宛先コンピュータにパケットを送る。パケットのフローは、特定の送信元ネットワークアドレス及びポートから宛先ネットワーク
アドレス及びポートに送られたパケットである。
【０００３】
これらのネットワークが拡張されるにつれて、それらを使用する利点が増している。ネットワークがどのように使用されているか、特にどのホスト及びネットワークがネットワークリソースを消費しているかをユーザが効率的に識別することを可能にするシステム及びツールを提供することが望ましい。
【０００４】
最も知られているネットフロー解析エンジンは、ＩＰアドレスに関連するデータ量に基づいて、複数の送信元及び／又は宛先ＩＰアドレスを識別する。換言すると、従来の技法は、フローレコードデータを全体的に見て考慮するものではない。これは、特定の情報について問い合わせるユーザの柔軟性が制限されるので不利である。
【発明の概要】
【０００５】
本発明の目的は、ネットフローデータを効率的に処理し解析するための方法及び装置を提供することであり、この方法及び装置は、ユーザ定義による問合せの柔軟性の向上を可能にする。
【０００６】
本発明の態様については、添付の特許請求の範囲で述べられる。
【０００７】
本発明の一態様によれば、フローレコードは、その全体がデータベースに格納されており、ユーザによって場当たり的に（ｉｎ  ａｎ  ａｄ  ｈｏｃ  ｆａｓｈｉｏｎ）問い合わせることができる。ユーザは、フィールドと値の様々な組合せを選択して、キーを定義し、フィールドのいずれかに基づいてフローをフィルタリングすることができる。問合せ可能なフローの数、及びフィールドの組合せは、典型的に、問合せの迅速化のために単にインデックスを使用することが不可能であるほど著しく多い。したがって、本発明の別の態様によれば、この方法及び装置は、各フローレコードを読み出し、各フローレコードを
フィルタリングし、フローレコードのフィールドに対応するキー、及びキーの関連する値を抽出し、それぞれの別個のキーの値を増分し、ユーザに結果を提示する。
【０００８】
本発明のさらなる態様によれば、ユーザに時系列チャートが提示されてもよく、各タイムスロットが、そのタイムスロットの事前定義された又は所望の数の上位Ｎ個のキーを含む。たとえば、Ｎは１０であってよく、上位Ｎ個は、定義されたキーに基づいてフィルタリングされたフロー内のオクテットの数に基づいて識別することができる。たとえばオクテットの数、及び／又はパケットの数に対応する各値について、１つ又は複数のチャートが提示されてもよい。
【０００９】
典型的な問合せでは、こうした問合せを完了するのに必要な時間とリソースの両方のせいでこの技法を実行不可能なものにする何百万ものキー及び大量のデータが存在し得るので、本発明による方法は、すべてのキーを値でソートして、次いでこれをユーザに提示するとは限らない。こうした問合せはこのように長い時間を要するため、ユーザは、最終的に完了するまで、問合せの進捗についてのフィードバックが与えられない。
【００１０】
本発明は、以下の２つの観測を適用することによりこの問題に対処する。１）ユーザは一般に、およそ数百万ではなく、上位１０個のキーにしか関心がなく、２）値が発見されている間に、すなわちリアルタイムに上位１０個の値を示すことが有用であり、その理由は、これにより、すべてのデータが処理される前にデータのサンプルに基づいてフィードバック及び有用な情報がユーザに提供されるからである。
【００１１】
好ましい一実施形態では、この方法及び装置は、最も関連性のある情報だけを決定し、ユーザに提供する。さらに、計算が完了するとすぐに上位Ｎ個の値を繰り返し更新することによって、提供される情報が現在のものであることが保証される。それによって、本発明のシステム及び方法は、収集されたネットフローデータの効率的な取出しを容易にするために、連続的に維持される固定サイズのデータ構造を使用してネットフローデータを漸次、効率的にフィルタリングし収集する。
【００１２】
本発明を具現化する構成について、例を挙げるため、添付の図面を参照して次に述べられる。
【図面の簡単な説明】
【００１３】
【図１】機能コンポーネント、及び問合せを処理してネットフローデータをフィルタリングし、ユーザに解析結果を出力するときに本発明のシステムによって実施される操作を示すブロック図である。
【図２】本発明によるキーの定義で使用できる各フローレコードのフィールドを示すブロック図である。
【図３】本発明の上位Ｎ計算器によって使用される主要データ構造を概略的に示す図である。
【図４】本発明の一実施形態によるフローレコードを処理する操作のフローチャートである。
【発明を実施するための形態】
【００１４】
図１は、ネットフローデータ解析システムの機能コンポーネント、及び本発明の一実施形態による方法の例示的な実施の操作を示すブロックフローチャートである。フローレコード２１が受け取られ、たとえばディスク（図示せず）から取り出され、フィルタパラメータに基づいてフィルタリングされる（２３）。フィルタパラメータは、ユーザによって事前定義されてもよいし、ユーザ問合せによって入力として受け取られてもよいし、またネットフローレコード内のフィールドの任意の組合せとすることができる。フィルタリングされたフローレコード、たとえば定義されたフィルタパラメータを満たす各々のフィールド値を有するフローレコードを処理して、フィルタリングされたフローレコードを表すキー、及びフローレコードからの関連する値を抽出する。この実施形態では、抽出されたキーは、フィルタパラメータに関連する１つ又は複数のフィールドを表すインジケータである。たとえば、特定のＩＰアドレス対について最もアクティブな上位１０個のネットフローを探すユーザベースの問合せでは、抽出されたキーは、１つの整数が送信元ＩＰアドレスを表し、もう一方の整数が宛先ＩＰアドレスを表す２つの整数の組合せであってよい。このように、抽出されたキーは、異なるアドレス対に関連する受け取られた各フローレコードに一意である。さらに、この例示的なユーザベースの問合せでは、抽出された値は、ネットフロー内のパケットサイズ及び／またのパケット数であってもよい。
【００１５】
一実施形態では、効率的で正確な処理を保証するために、問合せのタイムスパンは、事前定義された複数のタイムスロット、たとえば１秒のタイムスロットに分割されてもよく、各タイムスロットについて上位Ｎストリーミング計算器２４が作成される。それぞれの上位Ｎストリーミング計算器２４は、下記により詳細に述べられるように、フィルタリングされたストリーミングネットフロー使用データをプロセッサ効率のよいやり方で収集し、収集されたデータをメモリ効率のよいやり方で格納して、後に続く効率的なソート及び解析を容易にするために、フローレコードから抽出されたキー及び値を処理する。
【００１６】
クライアントソフトウェアは、チャートの現在の状態を規則的な時間間隔で、すなわち毎秒、要求してもよい（２５）。その後、ソフトウェアコンポーネント２６は、それぞれの上位Ｎ計算器に問い合わせ、返された中間状態に基づいて情報を編纂し、チャートを作成する。チャートは、クライアントソフトウェア２７に返され、このクライアントソフトウェア２７は、ユーザにチャートをレンダリングする。タイムスロットのそれぞれについて進捗率（ｐｅｒｃｅｎｔ  ｏｆ  ｃｏｍｐｌｅｔｉｏｎ）が返され、それらが完了していない場合、クライアントソフトウェアは、更新を得るために新しい要求を送る。このプロセスは、すべての計算器が終了され、チャートが完了するまで継続する。
【００１７】
図２は、関連するネットフロー内のパケットのフローに関する関連情報を含む例示的なネットフローレコードの内容を概略的に示している。一実施形態では、フローレコードのフィールドは以下を含んでよい。
送信元ＩＰアドレス
宛先ＩＰアドレス
送信元ＩＰポート
宛先ＩＰポート
ＩＰプロトコル
フロー内のオクテット数
フロー内のパケット数
サービスタイプ
【００１８】
上記に論じられたように、本発明の抽出されたキーについて、フローレコードからのフィールドの任意の組合せを使用してもよい。当業者は、上記にリストされたフィールドの代わりに、又はそれに加えて、別個のホスト又は接続の数、ネットフローの継続時間、並びに逆フローのパケットのサイズ及び／又は数など、フローレコード内で使用可能な他のフィールドを使用してもよいことが当業者には理解されよう。
【００１９】
キーのフィルタパラメータは、関連するフィールドの値又は値範囲によって定義することができる。フローレコード内で使用可能な各フィールドについて多くのフィルタパラメータが可能であることが当業者には理解されよう。たとえば、ＩＰアドレス値の範囲は、たとえばネットマスクとして定義することができ、ポート範囲は、開始値から終了値まで定義してもよい。
【００２０】
フローレコードは、各フローについて、ルータによって、規則的な時間間隔、たとえば毎分に発行される。たとえば、長く持続したフローは、多くのフローレコードを生成することができる。
【００２１】
本発明によるフローレコードを処理する操作について、上位Ｎ計算器によって使用される主要データ構造を概略的に示す図である図３、及びこの実施形態によるフローチャートである図４を参照して次に述べられる。
【００２２】
図３に示されたように、この実施形態は、ストリーミングネットフローデータの効率的な収集を容易にするためのデータ構造を提供し、データ構造が、キー配列３１と値配列３５とを含む。キー配列３１は、事前定義された数の要素を備え、それぞれの要素が、受け取られたフローレコードの抽出されたキーを格納するためのものである。受け取られたフローレコードからやはり抽出される、キーに関連する値は、別個の長い配列３５に格納してもよい。
【００２３】
好ましい実施形態では、キー配列３１のサイズは、ソートされたキー配列から返される所定の数の上位Ｎ個のネットフローに基づいて決定され、したがって、受け取られ処理されたネットフローデータの代表的な数に基づいてソートが行われることを可能にするのに十分な数の一意の抽出されたキーがキー配列に格納される。たとえば、キー配列３１内の要素の数は、所望の上位ｎ個の数Ｎ×定義されたキー内の値の数Ｍ×所定の整数（４など）と計算することができる。
【００２４】
フリーリストデータ構造３３は、フローレコードリーダ２２及びフィルタ２３によって受け取られ処理された新しい抽出されたキーの格納に使用可能なキー配列３１の要素のリストを格納するために提供される。この実施形態では、フリーリストは、リンクされたリストのデータ構造であり、フリーリスト３３の開始は、キー配列３１内の第１の空き要素へのポインタとして格納される。最初に、すべてのキー配列要素が、フリーリストのリンクされたリスト内に置かれ、それぞれの要素が、リンクされたリスト３３内の次の空き要素へのポインタ３２を含む。キー配列３１内にキーが埋められるとき、フリーリスト３３
の開始によって示された位置を使用して、新しいキーに追加するためのキー配列３１内の位置が決定される。その位置に要素が追加された後、フリーリストの開始のポインタは、新しく埋められた要素からのポインタで更新される。
【００２５】
迅速な探索を可能にするために、キーは、ハッシュされ、ハッシュテーブル３４で示されたリスト内に置かれてもよい。
【００２６】
次に図４を参照すると、図３に示されたデータ構造にフローレコードを追加するプロセスが、新しいフローレコードがフローレコードリーダ２２によって受け取られ、たとえばユーザの問合せで定義されたキーに基づいて処理するためにフィルタ２３に渡されることから開始している。ステップ４１で、フローレコードのキー及び値（たとえばオクテットの数、及びパケットの数）が、フローレコードから抽出される。ステップ４２で、抽出されたキーが、ハッシュテーブルを使用し探索される。ステップ４３で、抽出されたキーがデータ構造内に既にあると決定される場合は、ハッシュテーブルは、キー配列３１内でそ
のキーの位置を効率的に識別し、ステップ４４で、キーに関連する値が増分される。しかし、ステップ４３で、データ構造内にキーが存在しないと決定される場合は、ステップ４５で、フリーリストをチェックして、キー配列３１に空きエントリが残っているかどうか決定する。この実施形態では、フリーリスト３３の開始としてのポインタが存在することは、キー配列３１内に少なくとも１つの空きエントリがあることを示す。フリーリスト内に空きエントリがあると決定される場合は、ステップ４６で、開始ポインタによって識別された位置で、抽出されたキーが、キー配列３１に追加される。ステップ４６で、抽出さ
れた値は、値配列内の対応する位置にも追加される。
【００２７】
しかし、ステップ４５で、キー配列３１内に空きのエントリがないと決定される場合は、このプロセスはしたがって、新しいフローレコードを追加できるようにするためにエントリを削除する必要がある。これは、この実施形態では、キー配列３１内の各キーの特定のフィールドの格納された値を取り出し、ステップ４７で、そのフィールドの格納された値の中央値を決定することによって達成される。次いで、ステップ４８で、キー配列３１内のすべてのエントリが処理され、キーに関連する値が、対応する中央値より小さいと決定される場合にマーキングされる。フローレコードのフィールドに対応する抽出された値
のそれぞれについてステップ４７及び４８を繰り返してもよいことが当業者には理解されよう。次いで、ステップ４９で、マーキングされるキーが、キー配列から削除される。
【００２８】
その関連する値が中央値などの所定の閾値より小さいキーのエントリを削除することにより、絶対に必要でない限りは、多くのエントリのソートを回避することができる。これによって、さもなければソート手順を実施するのに使用されるリソースの望ましくない浪費が防止される。
【００２９】
上位Ｎストリーミング計算器がデータ構造内の各値位置の上位Ｎ個のキーを計算している間、クライアントコード１６は、上位Ｎ個の値（図１参照）を求めてもよい。これを可能にするために、図３に例証されたデータ構造へのアクセスは、マルチスレッドアクセスを可能にするロックによって保護することができる。
【００３０】
上記説明では、ネットフローデータ解析システムは、上述された方法を実施するように操作を制御するソフトウェアを格納し実行するように構成される。当業者には理解されるように、上記方法を実施するよう動作可能になるようにプログラマブルデバイスを構成するためのコンピュータプログラムは、キャリアに格納され、システムのフラッシュメモリなどのメモリにロードされてもよい。プログラムは、信号としてダウンロードされてもよいし、及び／又はシステム上に既に常駐するソフトウェアへのパッチ又は更新として適用されてもよい。本発明の範囲は、プログラム、プログラムを運ぶキャリア、及びブロード
キャスト信号を含む。
【００３１】
（代替実施形態）
諸実施形態について単に例示するために上記に述べられており、この説明を読むと様々な変形形態が当業者には考えられようが、その変形形態は、特許請求の範囲に定義された本発明の範囲内に含まれるものである。
【００３２】
たとえば、上述された実施形態では、上位Ｎストリーミング計算器は、キー配列に格納されたキーに関連する値の統計的解析を実施し、統計的解析に基づいて、格納されたインジケータの少なくとも１つを削除するように構成される。例示的な実施形態では、統計的解析は、格納されたキーに関連する値の中央値を計算し、計算された中央値より小さい関連する値を有するキーを削除することを伴う。統計的解析に中央値を使用することは、エントリが後にキー配列から削除されることが、全体的なネットワーク使用を表すための情報の大きい損失にはつながらないので特に有利である。しかし、平均、モード又は他の形
の統計的平均の計算など、中央値を使用するのではなく、他の形の統計的解析を使用してもよいことが当業者には理解されよう。
【００３３】
本発明の実施形態は、ハードウェア、ソフトウェア又はその組合せを使用して実施されてよく、１つ又は複数のコンピューティングシステム又は他の処理システムで実施されてもよい。
【符号の説明】
【００３４】
１６…クライアントコード、２１…フローレコード、２２…フローレコードリーダ、２３…フィルタ、２４…上位Ｎストリーミング計算器、２５…要求、２６…ソフトウェアコンポーネント、２７…クライアントソフトウェア、３１…キー配列／インジケータデータ構造、３２…インジケータデータ構造、３３…インジケータデータ構造、３４…ハッシュテーブル、３５…値配列／値データ構造。
【図１】
0005956049.tif 000002
【図２】
0005956049.tif 000003
【図３】
0005956049.tif 000004
【図４】
0005956049.tif 000005