JP2008054190A - フロー情報処理装置および方法 - Google Patents

Abstract

【課題】送信情報自由選択方式のフロー情報を高速で処理することのできるフロー情報処理装置および方法を提供する。
【解決手段】フロー情報処理装置１０は、ネットワーク上を流れるパケットから収集装置で取得されたフロー毎の複数の要素情報を含むフロー情報を収集装置から受信して処理するために、要素情報分割部１３と処理エレメント群１４とを有している。処理エレメント群１４はデータフロー型プロセッサの複数の処理エレメント１６を備えている。要素情報分割部１３は、受信したフロー情報から複数の要素情報を取得する。処理エレメント群１４は要素情報分割部１３で取得された複数の要素情報の各々を複数の処理エレメント１６によって並列処理する。
【選択図】図１

Description

本発明は、ネットワーク上を流れるフローを計測するフロー情報計測装置および方法に関する。

インターネットで用いられるＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）では、パケットにプロトコル情報、ソースＩＰアドレス、宛先ＩＰアドレスが含まれている。また、一部のトランスポートプロトコルでは、パケットにソースポート、宛先ポートの情報が含まれている。

これらのパケットの持つ情報を元に通信を分類し、通信毎に所定の情報を計測する方法をフロー計測という。フロー計測では、例えばプロトコル情報、ソースＩＰアドレス、宛先ＩＰアドレス、ソースポート、宛先ポートなど共通の情報を持つパケットを同一の通信に属するパケットと見なす。この同一の通信に属するパケットの集合をフローといい、フロー計測で計測される情報をフロー情報という。

フロー毎のデータ量やパケット量などのフロー情報を計測して解析することで、様々な地点間の複数の通信サービスを監視することができる。例えば、フロー計測の結果から、通信量（データ量あるいはパケット量）が異常に多い地点間を特定したり、通信量が異常に多い通信サービスを特定したりできる。また、トラフィックの傾向を把握することができる。

ところで、インターネット上ではルータが経路の制御を行っている。送信元からのパケットは複数のルータを経由して送信先に到達する。ルータは、この経路制御のために、パケットのＩＰヘッダ（あるいはトランスポートレイヤーのヘッダ）を参照する機能を元来的に有している。そのためルータはフローの計測に適しており、フロー計測はルータで行われる場合が多い。ルータは、取得したフロー情報をコレクタに送信する。コレクタはフロー情報を収集する装置である。

ルータ等がフロー情報送信装置として経路制御等の処理対象となるパケットから各フローのフロー情報を計測し、コレクタ（フロー情報受信装置）に通知する技術がＮｅｔＦｌｏｗ（非特許文献１参照）や標準化提案されているＩＰＦＩＸである。

これらによれば、フロー情報送信装置はフローの持つ情報から通知すべき要素情報を選択し、その要素情報を計測し、得られた要素情報の集合をパケット化してフロー情報受信装置に通知する。要素情報はフロー情報の一部を構成する情報であり、例えばソースＩＰアドレス、宛先ポート等である。上述したような一般的なプロトコルでは、これらの要素情報に識別用の固有番号が付与されている。ここではその固有番号を要素情報番号という。

フロー情報送信装置が取得する要素情報を選択する方法には２つの方式がある。一方が送信情報固定方式で、他方が送信情報自由選択方式である。送信情報固定方式では、フロー情報送信装置からフロー情報受信装置に通知されるフロー情報において、選択される要素情報が固定され、かつ要素情報の並び方が一定である。そのため、フロー情報受信装置におけるフロー情報に対する処理は固定的となり、比較的容易に高速化することができる。一方、送信情報自由選択方式では、利用者が要素情報の並び方や選択すべき要素情報を変更することができる。

Ｖｅｒｓｉｏｎ９以降のＮｅｔＦｌｏｗやＩＰＦＩＸでは送信情報自由選択方式が採用されている。ＩＰＦＩＸは、ＮｅｔＦｌｏｗ Ｖｅｒｓｉｏｎ９を拡張したプロトコルである。このＩＰＦＩＸでは、要素情報は１２グループに分類されている（非特許文献２参照）。ＮｅｔＦｌｏｗ Ｖｅｒｓｉｏｎ９でもこれと同様の分類を適用することができる。

送信情報自由選択方式では、フロー情報の通知を受けるフロー情報受信装置は、通知されるフロー情報のデータフォーマットを予め知っておくことができない。そのため、フロー情報送信装置がフロー情報受信装置にデータフォーマットの定義情報を通知してから、その定義情報に従ったデータフォーマットのフロー情報データを送信する。定義情報とフロー情報データは互いに別個のパケットで送られてもよく、また１つのパケットに混在してもよい。

フロー情報データには少なくとも１つのフローのフロー情報が含まれている。フロー情報データに複数のフローのフロー情報を含める場合、定義情報に従ったデータフォーマットが繰り返し配置される。

通常、ソフトウェアで動作するパーソナルコンピュータがフロー情報受信装置として用いられる（非特許文献３参照）。このフロー情報受信装置は、受信パケットに含まれる要素情報の種類や並び方を予め知っていないため、ソフトウェアによりフロー情報データをデコードするとき、パケット内のフロー情報から要素情報を検索する必要がある。

フロー情報受信装置における、要素情報の検索の一方法では、予め、デコード対象となる要素情報の要素情報番号と、その要素情報に対する処理内容が格納されている部分へのポインタとを対にしてメモリ空間上に保持しておく。そして、フロー情報データをデコードするとき、フロー情報受信装置はデコード対象の要素情報番号をメモリ上の一覧から検索し、その要素情報番号に対応するポインタで示された部分から処理内容を取得し、デコード対象の要素情報をその処理内容でデコードする。
Ｂ．Ｃｌａｉｓｅ，Ｅｄ． Ｃｉｓｃｏ Ｓｙｔｅｍｓ，"Ｃｉｓｃｏ Ｓｙｓｔｅｍｓ ＮｅｔＦｌｏｗ Ｓｅｒｖｉｃｅｓ Ｅｘｐｏｒｔ Ｖｅｒｓｉｏｎ ９"，［Ｏｎｌｉｎｅ］，Ｏｃｔｏｂｅｒ ２００４，［平成１８年６月２６日閲覧］，インターネット＜ＵＲＬ ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ３９５４．ｔｘｔ ＞ Ｊ．Ｑｕｉｔｔｅｋ（ＮＥＣ），Ｓ．Ｂｒｙａｎｔ（Ｃｉｓｃｏ Ｓｙｓｔｅｍｓ），Ｂ．Ｃｌａｉｓｅ（Ｃｉｓｃｏ Ｓｙｓｔｅｍｓ），Ｊ．Ｍｅｙｅｒ（ＰａｙＰａｌ），"Ｉｎｆｏｒｍａｔｉｏｎ Ｍｏｄｅｌ ｆｏｒ ＩＰ Ｆｌｏｗ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｘｐｏｒｔ ｄｒａｆｔ−ｉｅｔｆ−ｉｐｆｉｘ−ｉｎｆｏ−１２"，［Ｏｎｌｉｎｅ］，［平成１８年６月２６日閲覧］，インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｉｎｔｅｒｎｅｔ−ｄｒａｆｔｓ／ｄｒａｆｔ−ｉｅｔｆ−ｉｐｆｉｘ−ｉｎｆｏ−１２．ｔｘｔ＞ Ｆ．Ｒａｓｐａｌｌ，Ｓ．Ｔａｒｔａｒｅｌｌｉ，Ｊ．Ｑｕｉｔｔｅｋ ＮＥＣ Ｅｕｒｏｐｅ Ｌｔｄ，Ｎｅｔｗｏｒｋ Ｌａｂｏｒａｔｏｒｉｅｓ，"Ｉｍｐｌｅｍｅｎｔｉｎｇ ａｎ ＩＥＴＦ ＩＰＦＩＸ Ｍｅｔｅｒ"，［Ｏｎｌｉｎｅ］，［平成１８年６月２６日閲覧］，インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｉｓｔ−ｉｎｔｅｒｍｏｎ．ｏｒｇ／ｗｏｒｋｓｈｏｐ／ｐａｐｅｒｓ／０３＿０１＿ｉｐｓ−ｎｅｃ−ｅａ．ｐｄｆ＞

上述したように、メモリ上に格納されている要素情報番号とポインタの一覧を検索することで処理内容を取得し、その処理内容に従って要素情報をデコードする場合、一般的なノイマン型コンピュータではフロー情報データを逐次的に処理しなければならない。また、それら一連の処理を実行するとメモリへのアクセス回数が多くなる。そのためフロー情報に対する処理の高速化が困難となっていた。

一方、近年ではインターネット上のトラフィックが増加している。また、それに伴ってルータを疎通するパケット量も増加し、フロー情報送信装置としてのルータから送出されるフロー情報データも増加する傾向にある。そのため、フロー情報受信装置ではフロー情報データに対する高速な処理が望まれている。

本発明の目的は、送信情報自由選択方式のフロー情報を高速で処理することのできるフロー情報処理装置および方法を提供することである。

上記目的を達成するために、本発明のフロー情報処理装置は、ネットワーク上を流れるパケットから収集装置で取得されたフロー毎の複数の要素情報を含むフロー情報を前記収集装置から受信して処理するフロー情報処理装置であって、
受信した前記フロー情報から複数の前記要素情報を取得する要素情報分割部と、
データフロー型プロセッサの複数の処理エレメントを備えており、前記要素情報分割部で取得された複数の前記要素情報の各々を複数の前記処理エレメントによって並列処理する処理エレメント群と、を有している。

本発明によれば、要素情報分割部がフロー情報を要素情報に分割し、処理エレメント群がデータフロー型の並列処理を行うので、フロー情報データを逐次処理によることなくデータフロー型で処理でき、フロー情報データを高速で処理することができる。

また、前記収集装置から前記フロー情報のフォーマットを定義した定義情報が受信されると、前記処理エレメント群は、前記定義情報に従って前記処理エレメントの組み合わせを構成し、前記要素情報分割部によって前記定義情報を参照して取得された前記要素情報を、前記処理エレメントで処理することにしてもよい。

これによれば、処理エレメント群は、定義情報に従って処理エレメントの組み合わせを構成し、要素情報分割部によって取得された要素情報をその処理エレメントで処理するので、フロー情報のフォーマットが変更されても、それに応じて再構成した処理エレメントで処理を実行することができる。

また、前記処理エレメント群の前記処理エレメントからアクセスが可能なレジスタを更に有し、
前記処理エレメント群は、前記要素情報に対する並列処理に割り当てた前記処理エレメント以外の処理エレメントにより、処理の対象となる要素情報に関する定義情報の少なくとも一部を前記レジスタに格納し、該レジスタに格納した情報から、処理すべき前記要素情報と該要素情報を処理する処理エレメントとを特定することにしてもよい。

これによれば、レジスタに要素情報の定義情報を格納し、レジスタに格納された値を用いて要素情報とそれを処理する処理エレメントを特定するので、メモリへのアクセス回数を低減することができる。

また、前記フロー情報における前記要素情報の配列には所定の条件が課されており、
前記処理エレメント群は、前記要素情報分割部で取得された複数の前記要素情報の中から、処理すべき要素情報を、前記条件を前提とした手順で探索することにしてもよい。

これによれば、予め定められた条件を前提とした探索を行うことで探索回数を削減することができ、探索時間を短縮することもできる。

また、前記条件として、複数の前記要素情報を複数のグループに分類し、前記グループに順序を規定しておき、
前記処理エレメント群は、処理すべき前記所定の要素情報を探索するとき、該要素情報の属するグループと、前回までに探索済の要素情報の属するグループとの順序関係から探索範囲を限定することにしてもよい。

本発明によれば、フロー情報データを逐次処理によることなくデータフロー型で処理でき、フロー情報データを高速で処理することができる。

本発明を実施するための形態について図面を参照して詳細に説明する。本実施形態ではフロー情報送信装置は送信情報自由選択方式を採用しているものとする。そのため、フロー情報受信装置は、フロー情報送信装置から通知されるフロー情報のデータフォーマットを知らない。そこでフロー情報送信装置はフロー情報受信装置にデータフォーマットの定義情報を通知してから、その定義情報に従ったデータフォーマットのフロー情報データを送信する。

また、本実施形態ではフロー情報受信装置にはデータフロー型プロセッサを利用する。データフロー型プロセッサは複数の処理エレメントを有している。複数の処理エレメントの各々はＡＬＵ（Ａｒｉｔｈｍｅｔｉｃ ａｎｄ Ｌｏｇｉｃ Ｕｎｉｔ）を有しており、ＡＬＵによって比較、論理、算術など各種演算を行う。また、処理エレメントは、ＡＬＵ以外に記録素子など他の構成要素を含んでも構わない。これら複数の処理エレメントを２次元に配置し、処理エレメントを自由に組合せて利用することにより、プロセッサは並列処理を可能にしている。本実施形態のデータフロー型プロセッサは、定義情報に従って処理エレメントの組み合わせを再構成し、フロー情報データを並列処理する。

このようなデータフロー型プロセッサで構成されたフロー情報受信装置は、フロー情報送信装置からの定義情報に応じて処理エレメントの組み合わせを決定すればよい。例えば、フロー情報受信装置は、フロー情報送信装置から送られてくる定義情報の種類が変わったとき、処理エレメントの組み合わせを変化（再構成）させればよい。また、処理エレメントを高速で再構成できるプロセッサであれば、定義用パケットの種類が変わったか否かによらず定義用パケット毎に処理エレメントの組み合わせを変化させてもよい。

図１は、本実施形態によるフロー情報受信装置の構成を示すブロック図である。図１を参照すると、フロー情報受信装置１０は、ネットワークインタフェース１１、フロー分割部１２、要素情報分割部１３、処理エレメント群１４、およびＲＡＭ１５を有している。処理エレメント群１４は二次元の平面にマトリクス状に配置された複数の処理エレメント１６を有している。

ネットワークインタフェース１１は、不図示のフロー情報送信装置から定義情報やフロー情報を含むパケットを受信し、フロー分割部１２に与える。図２Ａ〜図２Ｃは、フロー情報プロトコルのパケットの例を示す図である。

フロー情報プロトコルではフロー情報送信装置からフロー情報受信装置へ定義情報とフロー情報が通知される。フロー情報は、フロー情報送信装置で取得された要素情報のデータである。定義情報は、フロー情報に含まれる要素情報の種類と並びを定義するデータフォーマットの情報である。

パケットは、ＩＰヘッダ、トランスポート層ヘッダ、およびフロー情報プロトコルヘッダを含み、更に、定義情報とフロー情報データの少なくとも一方を含んでいる。フロー情報データは要素情報毎のフロー情報を示すデータである。１つのパケットに複数のフロー情報データが含まれていてもよい。

図２Ａには、定義情報とフロー情報データが混在したパケットが示されている。図２Ｂには、定義情報のみを搭載したパケットが示されている。図２Ｃには、フロー情報データのみを搭載したパケットが示されている。定義情報とフロー情報データは図２Ａに示したように１つのパケットに混在してもよく、また図２Ｂ、図２Ｃに示したように、それぞれが別個のパケットに搭載されてもよい。

図３は、図２Ａおよび図２Ｃに示されたパケットに含まれるフロー情報データの構成例を示す図である。ここではＮｅｔＦｌｏｗ Ｖｅｒｓｉｏｎ９の例が示されている。図３を参照すると、３２ビット（４バイト）幅のフロー情報データにフローセットＩＤ、長さ、およびレコードが含まれている。

フローセットＩＤは、そのフロー情報データで通知されるフローを識別するための識別情報である。長さは、そのフロー情報データに含まれているレコードの長さを示す情報である。レコードは、フロー情報データにおいて要素情報を搭載した部分であり、定義情報で定められたフォーマットにて構成されている。

レコードには、要素情報として、ＩＰｖ４ソースアドレス（ＩＰＶ４＿ＳＲＣ＿ＡＤＤＲ）、ＩＰｖ４宛先アドレス（ＩＰＶ４＿ＤＳＴ＿ＡＤＤＲ）、ＩＰｖ４ソースアドレスのネットマスク（ＳＲＣ＿ＭＡＳＫ）、ＩＰｖ４宛先アドレスのネットマスク（ＤＳＴ＿ＭＡＳＫ）、ＩＰのＴＯＳ値（ＴＯＳ）、トランスポート層プロトコル（ＰＲＯＴＯＣＯＬ）、トランスポート層ソースポート番号（Ｌ４＿ＳＲＣ＿ＰＯＲＴ）、トランクポート層宛先ポート番号（Ｌ４＿ＤＳＴ＿ＰＯＲＴ）、パケット量（ＩＮ＿ＰＫＴＳ）、バイト量（ＩＮ＿ＢＹＴＥＳ）、フロー開始時間（ＦＩＲＳＴ＿ＳＷＩＴＣＨＥＤ）、フロー終了時間（ＬＳＴ＿ＳＷＩＴＣＨＥＤ）が含まれている。

図４は、図３に示したフロー情報データのフォーマットを示す定義情報を示す図である。定義情報には、２バイトの要素情報番号と２バイトの要素情報長とが対となって記述されている。フロー情報データには、定義情報に記述された順序で要素情報が配置される。

図４を参照すると、定義情報にはフローセットＩＤと長さが含まれている。フローセットＩＤはフロー情報データに含まれるものと同じ意味を持った値であり、定義情報の場合は必ず０になる。長さは、定義情報の長さを示す情報である。この例では長さ＝５６バイトである。

また、定義情報にはテンプレートＩＤとフィールド数が含まれている。テンプレートＩＤは、この定義情報を識別する識別情報であり、対応するフロー情報データのフローセットＩＤと同値になる。フィールド数は、この定義情報に含まれる要素情報番号と要素情報長の対の数を示している。ここではフィールド数＝１２なので、定義情報に１２対のフィールドが含まれていることを示している。

各フィールドには要素情報番号と要素情報長の対が搭載されている。例えば、先頭には、情報要素番号＝８のＩＰｖ４ソースアドレス（ＩＰＶ４＿ＳＲＣ＿ＡＤＤＲ）があり、情報要素長＝４バイトである。続いて、情報要素番号＝１２のＩＰｖ４宛先アドレス（ＩＰＶ４＿ＤＳＴ＿ＡＤＤＲ）があり、情報要素長＝４バイトである。

フロー分割部１２は、ネットワークインタフェース１１からのパケットからフロー情報データを３２バイトのレコード毎に分割し、フロー情報データの各々を要素情報分割部１３に与える。また、フロー分割部１２は、ネットワークインタフェース１１からのパケットから定義情報を取得し、要素情報分割部１３と処理エレメント群１４に与える。

要素情報分割部１３は、フロー分割部１２からの定義情報に従って、フロー分割部１２で取り出されたレコードを分割して要素情報を取得する。なお、ここではフロー情報データに含まれている全ての要素情報を取得する必要はなく、その中から所定の要素情報を取得すればよい。

ここでは、ＩＰｖ４ソースアドレス、ＩＰｖ４宛先アドレス、トランスポート層プロトコル、トランスポート層ソースポート番号、トランスポート層宛先ポート番号、パケット量、バイト量、フロー開始時間、およびフロー終了時間を取得することにする。

その場合、図４の定義情報を見て分かるように、取得すべき要素情報の要素情報番号は８、１２、４、７、１１、２、１、２２、２１である。また、各要素情報の長さは、４バイト、４バイト、１バイト、２バイト、２バイト、４バイト、４バイト、４バイト、４バイトである。各要素情報のフロー情報データの先頭からのオフセットは０バイト目、４バイト目、１１バイト目、１２バイト目、１４バイト目、１６バイト目、２０バイト目、２４バイト目、２８バイト目である。

そこで、要素情報分割部１３は、フロー情報データを０バイト目、４バイト目、１１バイト目、１２バイト目、１４バイト目、１６バイト目、２０バイト目、２４バイト目、２８バイト目で分割する。

処理エレメント群１４は、フロー分割部１２から与えられた定義情報に従って処理エレメント１６の組み合わせを再構成し、再構成された複数の処理エレメント１６で、各処理エレメント１６に割り当てられた処理を実行する。

例えば、フロー情報受信装置１０はフロー情報データに含まれている所定の要素情報を収集したり、ログとして記録したりといった処理を行う。また、収集した要素情報を集計して解析し、解析結果からネットワークの状態を判定するという処理を行ってもよい。処理エレメント群１４は、データフロー型の処理によって、それらのフロー情報受信装置１０全体としての処理を実現するように、定義情報に基づいて複数の処理エレメント１６の組み合わせを再構成する。そして、処理エレメント群１４は、複数の処理エレメント１６が再構成により各々に割り当てられた処理を並列で実行することで、フロー情報受信装置１０全体としての処理をデータフロー型で実行する。これにより、処理エレメント群１４は、フロー情報データを逐次的処理によらず、並列処理することができる。

処理エレメント群１４の再構成における処理エレメント１６への処理の割り当てには２通りの方法がある。

１つ目の方法として、利用されているプロセッサがフロー情報のパケット到着間隔以内に処理エレメントの組み合わせを動的に再構成できるのであれば、処理エレメント群１４は、収集すべき各要素情報に対する処理のみを処理エレメント１６に割り当てるように再構成すればよい。図３および図４の例では、要素情報番号が８、１２、４、７、１１、２、１、２２、２１の情報要素を収集する処理を処理エレメント１６に割り当てればよい。

一方、利用されているプロセッサがフロー情報のパケット到着間隔以内に処理エレメントの組み合わせを動的に再構成できない場合、定義情報に応じて再構成していたのでは処理が間に合わない可能性がある。その場合には２つ目の方法を用いればよい。２つ目の方法として、処理が必要となる可能性のある全ての要素情報に対する処理を予め処理エレメント１６に割り当てておけばよい。そして、それらの処理エレメント１６とは別の処理エレメント１６にて処理対象となる要素情報を探索し、その要素情報に対する処理が割り当てられている処理エレメント１６へ要素情報を振り分けることにすればよい。探索は要素情報番号の一致により行われる。その探索方法として様々な方法を適用することができる。例えば逐次探索や二分探索が適用できる。

図５は、二分探索を適用して要素情報を探索して振り分ける処理フローの一例を説明するための図である。図５の例では探索用に４つの処理エレメント１６が使用されている。

図５を参照すると、まず要素情報番号を所定値と二値比較する。その結果、要素情報番号が所定値と等しいか、所定値より大きいか、所定値より小さいかに分岐する。要素情報番号が所定値と等しければ、その要素情報を該当する処理エレメント１６に振り分ける。要素情報番号が所定値より大きければ、より大きい値との比較を行なう二分探索の処理エレメント１６に分岐し、二分探索が繰り返される。ただし、所定値より大きいことで要素情報番号が一意に特定できるのであれば、その要素情報を該当する処理エレメント１６に振り分ける。要素情報番号が所定値より小さければ、より小さい値との比較を行なう二分探索の処理エレメント１６に分岐し、二分探索が繰り返される。ただし、所定値より小さいことで要素情報番号が一意に特定できるのであれば、その要素情報を該当する処理エレメント１６に振り分ける。

図６は、二分探索を複数回行ったときの各処理エレメント１６の処理状態を説明するための図である。ハッチングのある□（四角形）は、探索に使用されている処理エレメント１６を示す。処理エレメントの□（四角形）の中の数字は探索回数を示す。ここでは要素情報に対する処理を行う処理エレメント１６は図示されていない。２値比較とその結果に応じた分岐によって、右に進むに従って徐々に探索用の処理エレメント１６の数が増えている。

このような要素情報の探索では、要素情報の配列に条件を課しておき、定義情報をその条件に従って定義し、フロー情報受信装置１０がその配列方法を前提とした探索を行うことで探索回数を削減することができ、探索時間を短縮することもできる。例えば、パケットに含まれる要素情報を、順序を付けた複数のグループに分け、属するグループの順序に応じた順序で要素情報を配列することにすればよい。これにより、あるグループに属する要素情報より後ろには、そのグループ以降のグループに属する要素情報しか登場しないように規定される。

図７は、要素情報を分類する複数のグループを定義した一例のパケットを示す図である。図７では、１２個のグループ１〜１２が定義されている。パケットにはグループ１からグループ１２の順に各グループに属する要素情報が配列される。

図８は、グループ１に属する要素情報が受信された場合について説明するための図である。図９は、グループ１２に属する要素情報が受信された場合について説明するための図である。図８に示したように、グループ１に属する要素情報を受信した場合、次に続く要素情報の属するグループとしてはグループ１〜１２の全てに可能性がある。なお、図８、図９におけるＰ１、Ｐ２はパケットの順番を指しており、Ｐ１がＰ２より先にくることを示している。

しかし、図９に示したように、グループ１２に属する要素情報を受信した場合、次に続く要素情報の属するグループとしてはグループ１２しか有りえない。

この条件を利用すれば、ある要素情報番号の要素情報を探索するとき、その要素情報の属するグループと、既に探索済で要素情報番号の判明している要素情報の属するグループとの順序関係から探索範囲を限定することができる。例えば、前回までに探索済の要素情報がグループ１２に属していたとすれば、その要素情報以降にはグループ１２に属する要素情報しか存在しえないので、他のグループに属する要素情報を探索するとき、その探索済の要素情報以降を探索しなくてよいことになる。このように配列方法を予め条件付けしておき、フロー情報受信装置１０でその条件を前提として探索を行えば分岐を削減して探索回数を減らすことができる。

図１０、図１１は、二分探索において各処理エレメント１６の処理状態を示す図である。図中のＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７はパケット番号を表している。数字は到着順序を示し、数字の小さい方が先に到着したことを意味する。

フロー情報受信装置１０に用いられているデータフロー型プロセッサでは１クロック毎に１ステージずつ処理が進行する。図１０の示した状態から１クロック後には図１１に示した状態に遷移する。

なお、パケットの到着する間隔がデータフロー型プロセッサの動作クロックの周期以下の場合、パケットを処理する処理エレメントの間に空いたステージを存在させてもよい。そうすれば、１つ前のパケットの処理が完了する前に次のパケットが到着してしまっても正常に処理することができる。

また、本実施形態では、図１に示したように処理エレメント群１４とは別にフロー分割部１２および要素情報分割部１３が存在する例を示したが、本発明はこれに限定されるものではない。他の例として、処理エレメント群１４の一部の処理エレメント１６によってフロー分割部１２および要素情報分割部１３の機能を実現する構成であってもよい。

その場合、図４に示した定義情報に従って、各要素情報の要素情報番号、長さ、オフセット値を記憶領域（例えばＲＡＭ１５）に一旦保持し、一定時間間隔で、処理エレメント１６の利用できる汎用レジスタにコピーする。この時間間隔と汎用レジスタ上の情報の保持数は汎用レジスタの記憶容量に応じて設定すればよい。続いて、汎用レジスタの情報を利用して要素情報とそれを処理する処理エレメント１６を定め、その処理エレメント１６によって要素情報に対する処理を実行する。

図１２は汎用レジスタの使用例を示す図である。図１２の例では、汎用レジスタには、比較用レジスタ２１、オフセット保持用レジスタ２２、オフセットベース保持用レジスタ２３、レコード全長保持用レジスタ２４、先頭要素情報番号保持用レジスタ２５、要素情報番号用レジスタ２６、要素情報の長さ用レジスタ２７、要素情報のオフセット用レジスタ２８が存在する。

比較用レジスタ２１は、次に処理すべき要素情報の要素情報番号を格納するレジスタである。この要素情報番号から次に行うべき処理内容が定まる。オフセット保持用レジスタ２２は、次に処理すべき要素情報の位置を示す値を格納するレジスタである。このレジスタを参照することで、次に処理すべき要素情報の取得が可能となる。オフセットベース保持用レジスタ２３は、次に処理すべき要素情報を含むレコードの先頭位置を示す値を格納するレジスタである。レコード全長保持用レジスタ２４は、レコードの全長を示す値を格納するレジスタである。先頭要素情報番号保持用レジスタ２５は、レコードの先頭に配置される要素情報の要素情報番号を格納するレジスタである。

そして、要素情報番号用レジスタ２６、要素情報の長さ用レジスタ２７、要素情報のオフセット用レジスタ２８は、ＲＡＭ１５等の記憶領域から要素情報の要素情報番号、長さ、オフセット値をコピーするための領域である。この領域に一定時間間隔で各情報がコピーされる。これら情報の汎用レジスタ上の保持数は上述したように汎用レジスタの記憶容量によるが、図１２では、一例として保持数が３となっている。

図１３は、汎用レジスタの情報を利用して要素情報と処理エレメント１６を決定し処理を実行する動作を示すフローチャートである。ここでは汎用レジスタの要素情報番号用レジスタ２６、要素情報の長さ用レジスタ２７、要素情報のオフセット用レジスタ２８には、処理すべき要素情報の要素情報番号、長さ、オフセット値が格納された状態にあるものとする。

図１３を参照すると、まず、フロー情報受信装置１０は、次に処理すべき要素情報の要素情報番号を比較用レジスタ２１にコピーする（ステップ１０１）。続いて、フロー情報受信装置１０は、先頭要素情報番号保持用レジスタ２５の値と比較用レジスタ２１の値が等しいか否か判定する（ステップ１０２）。先頭要素情報番号保持用レジスタ２５の値と比較用レジスタ２１の値が等しいことは、現在の処理対象がそれまでに比較していた処理対象の位置の次のレコードに到達したことを意味する。

先頭要素情報番号保持用レジスタ２５の値と比較用レジスタ２１の値が等しければ、フロー情報受信装置１０は、オフセットベース保持用レジスタ２３にフローレコード全長を加算する（ステップ１０３）。これにより処理対象が次のレコードに移行する。

先頭要素情報番号保持用レジスタ２５の値と比較用レジスタ２１の値が等しくなければ、処理対象は次のレコードに到達していないので、フロー情報受信装置１０はオフセットベース保持用レジスタ２３をそのままにしておく。

続いて、フロー情報受信装置１０は、オフセットベース保持用レジスタ２３に保持されているオフセットベースと、要素情報のオフセット用レジスタ２８に保持されている次に処理すべき要素情報のオフセット値とを加算し、オフセット保持用レジスタ２２に代入する（ステップ１０４）。これにより次に処理すべき要素情報の位置がオフセット保持用レジスタ２２に格納される。

続いて、フロー情報受信装置１０は、比較用レジスタ２１に格納されている要素情報番号から、その番号の示す要素情報を処理するための処理エレメント１６を検索する（ステップ１０５）。さらに、フロー情報受信装置１０は、オフセット保持用レジスタ２２によって示される要素情報の位置から要素情報の長さだけパケットデータを読み出す（ステップ１０６）。これにより処理すべき要素情報が取得される。

最後に、フロー情報受信装置１０は、ステップ１０６で取得された処理すべき要素情報に対して、ステップ１０５で定まった処理エレメント１６による処理を実行する（ステップ１０７）。

以上説明したように、フロー情報送信装置からフロー情報受信装置１０へ定義情報とフロー情報データが送られてくる。フロー情報受信装置１０では、フロー分割部１２が、フロー情報データを含むパケットから要素情報の部分をレコード毎に分割して取り出す。要素情報分割部１３は、フロー分割部１２で取り出されたレコードを定義情報に基づいて分割し、要素情報を収集する。処理エレメント群１４は、データフロー型プロセッサの複数の処理エレメントを備えており、定義情報に従って処理エレメントの組み合わせを構成する。そして、処理エレメント群１４は、要素情報分割部１３で収集された各要素情報に対して並列の各処理エレメントで所定の処理を実行する。

一般にフロー情報に対する処理において複数の要素情報は相互に依存性が無いので、フロー情報を要素情報に分割することによりフロー情報はデータフロー型の並列処理に適したものとなる。

本実施形態によれば、要素情報分割部１３がフロー情報をデータフロー型の並列処理に適した要素情報に分割し、処理エレメント群１４がデータフロー型の並列処理を行うので、フロー情報データを逐次処理によることなくデータフロー型で処理でき、フロー情報データを高速で処理することができる。そして、高速処理が可能な本実施形態のフロー情報受信装置１０を用いることで広帯域で高速なネットワーク環境の大きなトラフィックを計測することができる。

また、処理エレメント群がデータフロー型プロセッサで構成されているため、一般的なノイマン型コンピュータではソフトウェアによって行う処理をハードウェアで行うことができ、更に処理が高速化される。

また、処理エレメント群１４は、定義情報に従って処理エレメント１６の組み合わせを構成し、要素情報分割部１３によって取得された要素情報をその処理エレメント１６で処理するので、フロー情報データのフォーマットが変更されても、それに応じて再構成した処理エレメント１６で処理を実行することができる。

また、汎用レジスタに要素情報の要素情報番号、長さ、およびオフセット値を格納し、汎用レジスタに格納された値を用いて要素情報とそれを処理する処理エレメントを特定するので、メモリへのアクセス回数が減り、フロー情報を高速で処理することができる。

本実施形態によるフロー情報受信装置の構成を示すブロック図である。 フロー情報プロトコルのパケットの一例を示す図である。 フロー情報プロトコルのパケットの他の例を示す図である。 フロー情報プロトコルのパケットの更に他の例を示す図である。 図２Ａおよび図２Ｃに示されたパケットに含まれるフロー情報データの構成例を示す図である。 図３に示したフロー情報データのフォーマットを示す定義情報を示す図である。 二分探索を適用して要素情報を探索して振り分ける処理フローの一例を説明するための図である。 二分探索を複数回行ったときの各処理エレメント１６の処理状態を説明するための図である。 要素情報を分類する複数のグループを定義した一例のパケットを示す図である。 グループ１に属する要素情報が受信された場合について説明するための図である。 グループ１２に属する要素情報が受信された場合について説明するための図である。 二分探索において各処理エレメント１６の第１の処理状態を示す図である。 二分探索において各処理エレメント１６の第２の処理状態を示す図である。 汎用レジスタの使用例を示す図である。 汎用レジスタの情報を利用して要素情報と処理エレメント１６を決定し処理を実行する動作を示すフローチャートである。

符号の説明

１０ フロー情報受信装置
１１ ネットワークインタフェース
１２ フロー分割部
１３ 要素情報分割部
１４ 処理エレメント群
１５ ＲＡＭ
１６ 処理エレメント
２１ 比較用レジスタ
２２ オフセット保持用レジスタ
２３ オフセットベース保持用レジスタ
２４ レコード全長保持用レジスタ
２５ 先頭要素情報番号保持用レジスタ
２６ 要素情報番号用レジスタ
２７ 要素情報の長さ用レジスタ
２８ 要素情報のオフセット用レジスタ
１０１〜１０７ ステップ

Claims (10)

1. ネットワーク上を流れるパケットから収集装置で取得されたフロー毎の複数の要素情報を含むフロー情報を前記収集装置から受信して処理するフロー情報処理装置であって、
   受信した前記フロー情報から複数の前記要素情報を取得する要素情報分割部と、
   データフロー型プロセッサの複数の処理エレメントを備えており、前記要素情報分割部で取得された複数の前記要素情報の各々を複数の前記処理エレメントによって並列処理する処理エレメント群と、を有するフロー情報処理装置。
2. 前記収集装置から前記フロー情報のフォーマットを定義した定義情報が受信されると、前記処理エレメント群は、前記定義情報に従って前記処理エレメントの組み合わせを構成し、前記要素情報分割部によって前記定義情報を参照して取得された前記要素情報を、前記処理エレメントで処理する、請求項１に記載のフロー情報処理装置。
3. 前記処理エレメント群の前記処理エレメントからアクセスが可能なレジスタを更に有し、
   前記処理エレメント群は、前記要素情報に対する並列処理に割り当てた前記処理エレメント以外の処理エレメントにより、処理の対象となる要素情報に関する定義情報の少なくとも一部を前記レジスタに格納し、該レジスタに格納した情報から、処理すべき前記要素情報と該要素情報を処理する処理エレメントとを特定する、請求項２に記載のフロー情報処理装置。
4. 前記フロー情報における前記要素情報の配列には所定の条件が課されており、
   前記処理エレメント群は、前記要素情報分割部で取得された複数の前記要素情報の中から、処理すべき要素情報を、前記条件を前提とした手順で探索する、請求項１から３のいずれか１項に記載のフロー情報処理装置。
5. 前記条件として、複数の前記要素情報を複数のグループに分類し、前記グループに順序を規定しておき、
   前記処理エレメント群は、処理すべき前記所定の要素情報を探索するとき、該要素情報の属するグループと、前回までに探索済の要素情報の属するグループとの順序関係から探索範囲を限定する、請求項４に記載のフロー情報処理装置。
6. 収集装置にてネットワーク上を流れるパケットから取得されたフロー毎の複数の要素情報を含むフロー情報を前記収集装置から受信して処理するためのフロー情報処理方法であって、
   受信した前記フロー情報から複数の前記要素情報を取得し、
   取得した複数の前記要素情報の各々を、データフロー型プロセッサの複数の処理エレメントによって並列処理する、フロー情報処理方法。
7. 前記収集装置から前記フロー情報のフォーマットを定義した定義情報を受信すると、
   前記定義情報に従って前記処理エレメントの組み合わせを構成し、
   前記定義情報を参照して前記フロー情報から前記要素情報を取得し、
   前記定義情報を参照して取得した前記要素情報を、前記定義情報に従って構成した前記処理エレメントで処理する、請求項６に記載のフロー情報処理方法。
8. 前記要素情報に対する並列処理に割り当てた前記処理エレメント以外の処理エレメントにより、処理の対象となる要素情報に関する定義情報の少なくとも一部をレジスタに格納し、該レジスタに格納した情報から、処理すべき前記要素情報と該要素情報を処理する処理エレメントとを特定する、請求項７に記載のフロー情報処理方法。
9. 前記フロー情報における前記要素情報の配列には所定の条件が課されており、
   取得した複数の前記要素情報の中から、処理すべき要素情報を、前記条件を前提とした手順で探索する、請求項６から８のいずれか１項に記載のフロー情報処理方法。
10. 前記条件として、複数の前記要素情報を複数のグループに分類し、前記グループに順序を規定しておき、
    処理すべき前記所定の要素情報を探索するとき、該要素情報の属するグループと、前回までに探索済の要素情報の属するグループとの順序関係から探索範囲を限定する、請求項９に記載のフロー情報処理方法。

Images