(57)【要約】      （修正有）【課題】各フローの定義に対する頻出フローの特定を効率的に行う。【解決手段】頻出フロー特定装置１は、通信網のノード間において、パケットサンプリングを行い、サンプルしたパケットの属するフロー情報を管理して、帯域を占有する頻出フローを特定する際、パケットヘッダを解析して、「発信元IPアドレス(srcIP)」、「着信先IPアドレス(dstIP)」、「発信元ポート番号(srcPort)」、「着信先ポート番号(dstPort)」、「プロトコル(Protocol)」の５つの属性の各値を読み出し、予め定められた測定期間、予め定められた属性の組における、各属性値が同じパケット群（フロー）を抽出して、当該パケットの数を計数し、当該パケットの数が予め定められた閾値y*を超えるフローを頻出フローとして特定する。【選択図】図１
2011029986.tif 000002
【特許請求の範囲】
【請求項１】
プログラムされたコンピュータ処理によって、
通信網に流れるパケットをサンプリングし、サンプリングしたパケットの属するフローを特定し、帯域を占有するフロー（頻出フロー）を検出する方法であって、
プログラムされたコンピュータの処理実行手順として、
サンプリングしたパケットのヘッダ内の発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)の５つの属性の各値を読み出す第１の手順と、
予め定められた測定期間、予め定められた上記属性の組における、上記第１の手順で読み出した属性値が同じパケットの数を計数し、計数した各パケットの数が予め定められた閾値y*を越える属性の組からなるパケット群を上記頻出フローとして抽出する第２の手順と
を含むことを特徴とする通信網における頻出フロー検出方法。
【請求項２】
請求項１に記載の通信網における頻出フロー検出方法であって、
上記第２の手順では、
属性数の少ない属性の組から順に、当該属性の組における頻出フローを抽出すると共に、
属性数のより多い属性の組における頻出フローの抽出を行う際には、
属性数のより少ない属性の組において抽出した頻出フローの属性値を含むもののみを対象に行うことを特徴とする通信網における頻出フロー検出方法。
【請求項３】
請求項１もしくは請求項２のいずれかに記載の通信網における頻出フロー検出方法であって、
上記第２の手順で用いる閾値y*を以下の手順で決定することを特徴とする通信網における頻出フロー検出方法。
『閾値y*の決定手順』
予め定められた有限の測定期間において、全部でN個のパケットが存在したと仮定し、
上記頻出フローをある一定の割合φ（０＜φ＜１）以上のパケットを含むフローと定義し、
Xj,Yjをそれぞれ、フローjに含まれる母集団におけるパケット数、サンプルされたパケット数とし、
Wを母集団の全N個のパケットからサンプルされたパケット数とし、
母集団からW=w個のパケットがサンプルされたとし、母集団内でN個のパケットを持つフローを、予め定めた特定基準確率δidentより大きい確率で特定するための閾値y*を以下の数１に示す式で決定する。
【数１】
2011029986.tif 000005
【請求項４】
請求項１から請求項３のいずれかに記載の通信網における頻出フロー検出方法であって、
上記予め定められた属性の組は、下記に定義するフローからなることを特徴とする通信網における頻出フロー検出方法。
『属性の組の定義』
(1) srcIPを同じくするパケット群をキー番号１のフロー、
(2) dstIPを同じくするパケット群をキー番号2のフロー、
(3) ProtocolとsrcPortを同じくするパケット群をキー番号3のフロー、
(4) ProtocolとdstPortを同じくするパケット群をキー番号4のフロー、
と定義し、これらキー番号1〜4のフローを１つ組フローと呼ぶ。
(5) キー番号1と2の組み合わせからなるフロー（つまり、{srcIP, dstIP}を同じくするパケット群）をキー番号5のフロー、
(6) キー番号1と3の組み合わせからなるフロー（つまり、{srcIP, srcPort, Protocol}を同じくするパケット群）をキー番号6のフロー、
(7) キー番号1と4の組み合わせからなるフロー（つまり、{srcIP, dstPort, Protocol}を同じくするパケット群）をキー番号7のフロー、
(8) キー番号2と3の組み合わせからなるフロー（つまり、{dstIP, srcPort, Protocol}を同じくするパケット群）をキー番号8のフロー、
(9) キー番号2と4の組み合わせからなるフロー（つまり、{dstIP, dstPort, Protocol}を同じくするパケット群）をキー番号9のフロー、
(10) キー番号3と4の組み合わせからなるフロー（つまり、{srcPort, dstPort, Protocol}を同じくするパケット群）をキー番号10のフロー、
と定義し、これらキー番号5〜10のフローを２つ組フローと呼ぶ。
(11) キー番号1,2,3の組み合わせからなるフロー（つまり、{srcIP, dstIP, srcPort, protocol}を同じくするパケット群）をキー番号11のフロー
(12) キー番号1,2,4の組み合わせからなるフロー（つまり、{srcIP, dstIP, dstPort, protocol}を同じくするパケット群）をキー番号12のフロー
(13) キー番号1,3,4の組み合わせからなるフロー（つまり、{srcIP, srcPort, dstPort, protocol}を同じくするパケット群）をキー番号13のフロー
(14) キー番号2,3,4の組み合わせからなるフロー（つまり、{dstIP, srcPort, dstPort, protocol}を同じくするパケット群）をキー番号14のフロー
と定義し、これらキー番号11〜14のフローを３つ組フローと呼ぶ。
(15) キー番号1,2,3,4の組み合わせからなるフロー（つまり、{srcIP, dstIP, srcPort, dstPort, protocol}を同じくするパケット群）をキー番号15のフロー
と定義する。
【請求項５】
請求項４に記載の通信網における頻出フロー検出方法であって、
プログラムされたコンピュータの処理実行手順として、
所定のキー番号に対して上記頻出フローの候補を、以下の手順で抽出することを特徴とする通信網における頻出フロー検出方法。
『頻出フロー候補の抽出手順』
サンプリングした各パケットの当該キー番号keynumに関する属性値cを抽出する手順、
抽出した属性値cが、予め用意されたb＊個のバケツのいずれかに格納されているか否かを判別する手順、
抽出した属性値cがいずれかのバケツに格納されていれば、当該バケツに予め対応付けて設けられたカウンタECの値を１つ加算する手順、
抽出した属性値cがいずれのバケツにも格納されていなければ、空きのバケツの有無を判別する手順、
空きのバケツがあれば該バケツに当該属性値cを格納して該バケツに予め対応付けて設けられたカウンタECの値を１つ加算する手順、
空きのバケツがなければ、当該属性値cは格納せずに、全てのバケツに予め対応付けて設けられたカウンタECの値を１つ減算すると共に、予め設けられたカウンタＤＣを１つ加算して全カウンタECの値が１つ減算された回数を計数する手順、
減算したカウンタECの値が０になれば当該バケツに格納している属性値ｃを削除する手順、
母集団からサンプルされたW＝w個のパケットについて上記の手順を終えて、予め定められた測定期間が終了すると、バケツiのカウンタECiの値とカウンタＤＣの値の和を算出し、算出した和が上記閾値y*以上であれば（ECi+DC>=y*）、当該バケツiに格納されている属性値ｃを、上記頻出フローの候補として抽出する手順。
【請求項６】
請求項５に記載の通信網における頻出フロー検出方法であって、
上記バケツの数b＊個を、次の数２の式から求めることを特徴とする通信網における頻出フロー検出方法。
【数２】
2011029986.tif 000006
δbktは、予め定めるバケツ特定確率であり、数２で決まるバケツの数を用意すれば、少なくともδbktより大きな確率で、頻出フローは全てバケツに残る。
【請求項７】
請求項５もしくは請求項６のいずれかに記載の通信網における頻出フロー検出方法であって、
上記頻出フローの候補の抽出手順と並行して、上記測定期間、上記キー番号15で定義されるフローを、予め設けられた記憶装置SFDに、下記の手順Ａで格納し、
該手順Ａで記憶装置SFDに格納したキー番号15で定義されるフローの情報に基づき、各キー番号keynumに対する頻出フローを下記の手順Ｂで特定することを特徴とする通信網における頻出フロー検出方法。
『手順Ａ』
サンプリングしたパケットが到着したら、キー番号15に関する当該パケットの属性値（key={srcIP, dstIP, srcPort, dstPort, Protocol}）をパケットヘッダから読み出し、
読み出したkeyが既に上記記憶装置SFDに格納されているか新規keyのパケットかを判別し、
既に格納されていれば、当該keyに予め対応付けられたカウンタcountkeyを１つカウントアップし、
新規keyのパケットであれば、当該keyを上記記憶装置SFDに格納し、当該keyに新たなカウンタを対応付けて当該カウンタcountkeyをcountkey =1とすることで、
上記測定期間、上記記憶装置SFDに、{key, countkey }（countkeyは、key毎のサンプルパケット数）を格納する手順、
カウンタcountkey>=y*となるkeyを、キー番号15における頻出フローの集合D15とする手順。
『手順Ｂ』
サンプリングしたパケットに対して、１つ組の各キー番号１〜４に関する上記頻出フロー候補の抽出手順を実行して、各キー番号１〜４に関しての上記頻出フローの候補を抽出し、抽出した各候補フローのキー（候補キー）の集合Ckeynum(1≦keynum≦4)を生成し、
該生成した１つ組の候補キーの集合Ckeynum(1≦keynum≦4)を用いて、上記記憶装置SFDに格納したキー番号15に関する当該パケットの属性値（key={srcIP, dstIP, srcPort, dstPort, Protocol}）から、上記２つ組および３つ組の候補キーの作成と当該候補キーのカウンタの更新を行って、
上記頻出フローと特定されるフローのキー（特定キー）の集合Dkeynum(1≦keynum≦15)を取得する手順。
【請求項８】
請求項７に記載の通信網における頻出フロー検出方法であって、
上記手順Ｂでの、上記１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、上記２つ組および３つ組の候補キーの作成と候補キーのカウンタの更新を行って、上記特定キーの集合Dkeynum(1≦keynum≦15)を取得する手順は、
予め空の候補キーの集合Ckeynum(5≦keynum≦15)を生成し、
次に、１つ組のキー番号keynum (keynum=1〜4)について、上記記憶装置SFD内のkeyとkeynumからキー番号keynumのキーcを照合して、当該キーcが候補キー集合Ckeynumに含まれているか否かを判別し、
含まれているならば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
その後、keyに含まれる一つ組のキーのうち、候補キーではないものを全てkeyから取り除き、１つ組の候補キーから構成されるキーを生成し、
生成したキーに含まれる２つ組および３つ組の任意のキーcについて、上記候補キーの集合Ckeynumを探索して、当該キーcが上記候補キー集合Ckeynumに含まれているか否かを判別し、
含まれていなければ上記候補キー集合Ckeynumに当該キーcを追加して、当該キーcのカウンタ値c.countをc.count←countkeyとし、
キーcが上記候補キー集合Ckeynumに含まれているならば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
上記１つ組と２つ組および３つ組（キー番号１〜１４）に関する処理を、上記記憶装置SFDに格納されている全てのキーkeyに対して実行した後、上記候補キーの集合Ckeynum（11≦keynum≦14）の中からc.count>=y*となるキーcを抽出し、
該抽出したキーcを特定キーの集合Dkeynum(1≦keynum≦14)に格納する
ことで、上記特定キーの集合Dkeynum(1≦keynum≦15)を取得する
手順からなることを特徴とする通信網における頻出フロー検出方法。
【請求項９】
請求項５もしくは請求項６のいずれかに記載の通信網における頻出フロー検出方法であって、
上記頻出フローの候補の抽出手順と並行して、上記測定期間、上記キー番号15で定義されるフローを、予め設けられた記憶装置SFDに、下記の手順Ａで格納し、
該手順Ａで記憶装置SFDに格納したキー番号15で定義されるフローの情報に基づき、各キー番号keynumに対する頻出フローを下記の手順Ｂで特定することを特徴とする通信網における頻出フロー検出方法。
『手順Ａ』
サンプリングしたパケットが到着したら、キー番号15に関する当該パケットの属性値（key={srcIP, dstIP, srcPort, dstPort, Protocol}）をパケットヘッダから読み出し、
読み出したkeyが既に上記記憶装置SFDに格納されているか新規keyのパケットかを判別し、
既に格納されていれば、当該keyに予め対応付けられたカウンタcountkeyを１つカウントアップし、
新規keyのパケットであれば、当該keyを上記記憶装置SFDに格納し、当該keyに新たなカウンタを対応付けて当該カウンタcountkeyをcountkey =1とすることで、
上記測定期間、上記記憶装置SFDに、{key, countkey }（countkeyは、キーkey毎のサンプルパケット数）を格納する手順、
カウンタcountkey>=y*となるkeyを、キー番号15における頻出フローの集合D15とする手順。
『手順Ｂ』
空のCkeynum(1≦keynum≦15)を用意し、
サンプリングしたパケットに対して、１つ組の各キー番号１〜４に関する上記頻出フロー候補の抽出手順を実行して、各キー番号１〜４に関しての上記頻出フローの候補を抽出し、
抽出した各候補フローのキー（候補キー集合Ckeynum）が、上記記憶装置SFDに格納されているか否かを判別し、
格納されていなければ、上記記憶装置SFDに格納されている当該キー番号１〜４のキーｃを、上記抽出した各候補フローのキー（候補キー集合Ckeynum）に追加して、当該キーｃのカウンタ値c.countをc.count←countkeyと更新し、
格納されていれば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
該各キー番号１〜４に関する処理を、上記記憶装置SFDに格納されている全てのキーkeyに対して実行した後、c.count>=y*となるキーcを抽出し、
抽出したキーｃを、上記頻出フローと特定されるフローのキー（特定キー）の集合Dkeynum(1≦keynum≦4)に格納し、
２つ組のキー（keynum=5〜10）については、まず、上記記憶装置SFDから、上記１つ組のキーが上記特定キーｃでないキーkeyを取り除き、上記１つ組の特定キーから構成されるキーを生成し、
生成したキーに含まれる２つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、当該キーcが候補キーの集合Ckeynumに含まれているか否かを判別し、
含まれていなければ候補キーの集合Ckeynumに当該キーcを追加して、当該キーcのキーのカウンタ値c.countをc.count←countkeyとし、
当該キーcが候補キーの集合Ckeynumに既に含まれているならば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
該２つ組（キー番号５〜１０）に関する処理を、上記記憶装置SFDに格納されている全てのキーkeyに対して実行した後、候補キーの集合Ckeynumの中から、c.count>=y*となるキーcを抽出し、
該抽出したキーｃを特定キーの集合Dkeynum(5≦keynum≦10)に格納し、
３つ組のキー（keynum=11〜14）については、任意の部分集合が特定キーであるような候補キーの集合Ckeynum（11≦keynum≦14）を生成し、
その後、上記記憶装置SFD内の各keyについて、キー番号keynumのキーcが、上記候補キーの集合Ckeynum（11≦keynum≦14）に含まれているか否かを判別し、
含まれていなければ候補キーの集合Ckeynumに当該キーcを追加して、当該キーcのキーのカウンタ値c.countをc.count←countkeyとし、
含まれているならば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
該３つ組（キー番号１１〜１４）に関する処理を、上記記憶装置SFDに格納されている全てのキーkeyに対して実行した後、候補キーの集合Ckeynum（11≦keynum≦14）の中からc.count>=y*となるキーcを抽出し、
該抽出したキーcを特定キーの集合Dkeynum(11≦keynum≦14)に格納する
ことで、上記特定キーの集合Dkeynum(1≦keynum≦15)を取得する。
【請求項１０】
請求項５もしくは請求項６のいずれかに記載の通信網における頻出フロー検出方法であって、
上記頻出フローの候補の抽出手順と並行して、上記測定期間、上記キー番号15で定義されるフローを、予め設けられた記憶装置SFDに、下記の手順Ａで格納し、
該手順Ａで記憶装置SFDに格納したキー番号15で定義されるフローの情報に基づき、各キー番号keynumに対する頻出フローを下記の手順Ｂで特定することを特徴とする通信網における頻出フロー検出方法。
『手順Ａ』
サンプリングしたパケットが到着したら、キー番号15に関する当該パケットの属性値（key={srcIP, dstIP, srcPort, dstPort, Protocol}）をパケットヘッダから読み出し、
読み出したkeyが既に上記記憶装置SFDに格納されているか新規keyのパケットかを判別し、
既に格納されていれば、当該keyに予め対応付けられたカウンタcountkeyを１つカウントアップし、
新規keyのパケットであれば、当該keyを上記記憶装置SFDに格納し、当該keyに新たなカウンタを対応付けて当該カウンタcountkeyをcountkey =1とすることで、
上記測定期間、上記記憶装置SFDに、{key, countkey }（countkeyは、キーkey毎のサンプルパケット数）を格納する手順、
カウンタcountkey>=y*となるkeyを、キー番号15における頻出フローの集合D15とする手順。
『手順Ｂ』
空のCkeynum(1≦keynum≦15)を用意し、
サンプリングしたパケットに対して、１つ組の各キー番号１〜４に関する上記頻出フロー候補の抽出手順を実行して、各キー番号１〜４に関しての上記頻出フローの候補を抽出し、
抽出した各候補フローのキー（候補キー集合Ckeynum）が、上記記憶装置SFDに格納されているか否かを判別し、
格納されていなければ、上記記憶装置SFDに格納されている当該キー番号１〜４のキーｃを、上記抽出した各候補フローのキー（候補キー集合Ckeynum）に追加して、当該キーｃのカウンタ値c.countをc.count←countkeyと更新し、
格納されていれば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
該各キー番号１〜４に関する処理を、上記記憶装置SFDに格納されている全てのキーkeyに対して実行した後、c.count>=y*となるキーcを抽出し、
抽出したキーｃを、上記頻出フローと特定されるフローのキー（特定キー）の集合Dkeynum(1≦keynum≦4)に格納し、
上記記憶装置SFDから、上記１つ組のキーが上記特定キーｃでないキーkeyを取り除き、
上記１つ組の特定キーから構成されるキーを生成し、
生成したキーに含まれる２つ組ならびに３つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、当該キーcが候補キーの集合Ckeynumに含まれているか否かを判別し、
含まれていなければ候補キーの集合Ckeynumに当該キーcを追加して、当該キーcのキーのカウンタ値c.countをc.count←countkeyとし、
当該キーcが候補キーの集合Ckeynumに既に含まれているならば、当該キーcのカウンタ値c.countを、c.count←c.count+countkeyと更新し、
該２つ組ならびに３つ組（キー番号５〜１４）に関する処理を、上記記憶装置SFDに格納されている全てのキーkeyに対して実行した後、候補キーの集合Ckeynumの中から、c.count>=y*となるキーcを抽出し、
該抽出したキーｃを特定キーの集合Dkeynum(5≦keynum≦14)に格納する
ことで、上記特定キーの集合Dkeynum(1≦keynum≦15)を取得する。
【請求項１１】
プログラムされたコンピュータ処理によって、通信網に流れるパケットをサンプリングし、サンプリングしたパケットの属するフローを特定し、帯域を占有するフロー（頻出フロー）を検出するシステムであって、
プログラムされたコンピュータ処理を実行する手段として、
請求項１から請求項１０のいずれかに記載の通信網における頻出フロー検出方法での各手順を実行する手段を具備したことを特徴とする通信網における頻出フロー検出システム。
【請求項１２】
コンピュータに、請求項１から請求項１０のいずれかに記載の通信網における頻出フロー検出方法における各手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、IP（Internet Protocol）ネットワークにおいて、帯域を占有するトラヒックを発生するフローを特定する技術に係り、特に、当該フローの特定を効率的に行うのに好適な技術に関するものである。
【背景技術】
【０００２】
IPネットワークにおいては、広く利用されてくるに伴って、トラヒック量は年々増加しており、またユーザの利用形態やアプリケーションも多種多様となっている。それに伴い、ネットワーク・サーバリソース消費・セキュリティ上の驚異となる異常トラヒックの増大が問題となっている。
【０００３】
ここで、異常トラヒックの例として、特定のサーバへ不正なトラヒックを大量に送信するDDoS（Distributed Denial of Service）攻撃や、ネットワークをスキャンするウィルス等が挙げられる。また、異常トラヒックではないが、ごく一部のユーザが大量のトラヒックを生成してネットワークリソースを浪費するP2P（Peer-to-Peer）トラヒック等の存在も指摘されている。
【０００４】
安心・安全で快適な通信サービスを提供するためには、トラヒック測定・分析を通じて、これらトラヒックを適切に検出し、必要に応じて措置を取る仕組みを確立することが重要となってきている。
【０００５】
一方、回線の高速化に伴い、スケーラブルな測定方法として、パケットサンプリング技術が注目されている。当該技術について図６を用いて説明する。
【０００６】
図６に示すように、複数のmicroフローからのパケットが到着する場合を考える。尚、ここでは、同一の送信元IPアドレスsrcIPと着信先IPアドレスdstIPおよび送信元ポート番号と着信先ポート番号ならびにプロトコル番号を持つパケット群をmicroフローと定義する。また、図６においては、各パケットの網掛けの種別は、フロー別に分けられているものとする。
【０００７】
ここで、X(=3)個に1個のパケットをサンプルし、サンプルされたパケットの属するフローのみを管理対象とすると、管理フロー数を２本に削減できている（サンプルしないと５本であった）。このようにサンプリングにより管理フロー数を削減できる。また、X個に１個のパケットのみを処理対象とするためパケット処理負荷も削減できる。
【０００８】
非特許文献１では、パケットサンプリングを用いて、帯域を占有するフローを特定する技術を提案している。この技術では、microフロー毎にサンプルパケット数をカウントし、予め定めた閾値以上のサンプルパケット数を送出しているフローを巨大フローとして特定しているが、フローの定義としては、上述した定義（同一の送信元IPアドレスsrcIPと着信先IPアドレスdstIPおよび送信元ポート番号と着信先ポート番号ならびにプロトコル番号を持つパケット群）のmicroフローのみを対象にしている。
【０００９】
例えばmicroフローのレベルで大量トラヒックを送出している例としては、特定のエンドホスト間で特定のポート番号で大量なトラヒックを転送するP2Pトラヒックなどが考えられる。
【００１０】
しかし、例えば、個々のmicroフローでみるとトラヒック量はさほど大きくないものの、それらが集まると大量なトラヒックを転送している異常トラヒックの例もある。
【００１１】
例えば、DDoS攻撃であれば、特定のdstIP（着信先ＩＰアドレス）へ向けて、多数のsrcIP（送信元ＩＰアドレス）からトラヒックが送られる。一方、スキャンをするホストであれば、特定のsrcIPから多数のdstIPやdstPort（送信先ポート番号）に向けてトラヒックを送出する。
【００１２】
また、P2Pも、アプリケーションによっては、ある特定のdstIPに向けて、複数のsrcIPからコンテンツのピースを送るケースもある。
【００１３】
このように、監視したいトラヒック種別に応じて、microフローの組み合わせを変えてトラヒックを監視する必要がある。
【００１４】
それぞれのフローの定義（例えば、dstIPのみを同じくするパケット群をdstIPフローと定義、また、srcIPのみを同じくするパケット群をsrcIPフローと定義）に対して、非特許文献１の技術をパラレルに実施することが考えられるが、各フローの定義毎にフロー当りサンプルパケット数をカウントする必要があり、フローの定義数に比例して、フロー管理やパケット処理の負荷が増大してしまうという問題点がある。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】T. Mori, T. Takine, J. Pan, R. Kawahara, M. Uchida, and S. Goto, "Identifying heavy-hitter flows from sampled flow statistics," IEICE Trans. Commun., vol.E90-B, no.11, pp.3061-3072, Nov. 2007.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
解決しようとする問題点は、従来の技術では、大量トラヒックを検出するためには、各フローの定義毎にフロー当りサンプルパケット数をカウントする必要があり、種々のフロー定義数に比例して、フロー管理やパケット処理の負荷が増大してしまう点である。
【００１７】
本発明の目的は、これら従来技術の課題を解決し、各フローの定義に対する頻出フロー（トラヒック全体のうち、ある一定以上の割合を占めるフロー）の特定を効率的に行うことである。
【課題を解決するための手段】
【００１８】
上記目的を達成するため、本発明では、通信網のあるノードにおいてパケットサンプリングを行い、サンプルされたパケットの属するフロー情報を管理して、帯域を占有する頻出フローを特定する際、パケットヘッダ内の「発信元IPアドレス(srcIP)」、「着信先IPアドレス(dstIP)」、「発信元ポート番号(srcPort)」、「着信先ポート番号(dstPort)」、「プロトコル(Protocol)」の５つの属性を用いて、予め定めたこれら属性の組み合わせを同じくするパケット群をフローと定義し、これらフローの定義の中で予め着目するいくつかのフローの定義に対して、サンプルされたパケット数が予め定めた閾値を超えるフローを頻出フローとして特定することを特徴とする。例えば、フローの定義として、属性「発信元IPアドレス(srcIP)」のみからなる第１のフローと、その属性「発信元IPアドレス(srcIP)」と他の属性との組み合わせで定義した第２のフローを定義した場合、属性「発信元IPアドレス(srcIP)」のみからなる第１のフローでトラヒックが閾値を超えなければ、その属性との組み合わせで定義した第２のフローでは閾値を超えるトラヒックは生じ得ないことを利用し、トラヒックが閾値を超えない第１のフローの属性を含む第２のフローを、頻出フローの特定の対象から除くことにより、帯域を占有するトラヒックを発生させるフローの特定を効率的に行う。
【発明の効果】
【００１９】
本発明によれば、各フローの定義毎にフロー当りサンプルパケット数をカウントすることなく、各フローの定義に対する頻出フロー（トラヒック全体のうち、ある一定以上の割合を占めるフロー）を特定することができ、種々のフロー定義数に比例して、フロー管理やパケット処理の負荷が増大してしまうこともなく、当該頻出フローの特定を効率的に行うことが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係る頻出フロー特定システムの構成例を示すブロック図である。
【図２】図１における頻出フロー特定装置が適用されるネットワークの構成例を示す説明図である。
【図３】図１における頻出フロー特定装置による本発明に係る頻出フロー検出方法に係る第１の動作手順例を示す疑似コードを示す説明図である。
【図４】図１における頻出フロー特定装置による本発明に係る頻出フロー検出方法に係る第２の動作手順例を示す疑似コードを示す説明図である。
【図５】図１における頻出フロー特定装置による本発明に係る頻出フロー検出方法に係る第３の動作手順例を示す疑似コードを示す説明図である。
【図６】パケットサンプリングの動作例を示す説明図である。
【発明を実施するための形態】
【００２１】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１において、１は本発明に係る頻出フロー特定システムとしての頻出フロー特定装置であり、この頻出フロー特定装置１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ等を具備したコンピュータ装置からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、プログラムされたコンピュータ処理を実行する。
【００２２】
すなわち、頻出フロー特定装置１は、プログラムされたコンピュータ処理を実行する手段として、サンプリング部１ａ、パケットヘッダ解析部１ｂ、頻出フロー候補抽出部１ｃ、頻出フロー特定部１ｄ、サンプルフロー格納部１ｅを有している。
【００２３】
このような構成からなる頻出フロー特定装置１は、図２に示すように、ノード２，３間に設けられ、ノード２，３間で送受信されるパケットを読み込み、読み込んだパケットから、ノード２，３間において帯域を占有するトラヒックを発生させるフロー（頻出フロー）を特定する。
【００２４】
すなわち、本例の頻出フロー特定装置１は、例えば、図２における通信網のノード２，３において、サンプリング部１ａによるパケットサンプリングを行い、サンプルしたパケットの属するフロー情報を管理して、帯域を占有する頻出フローを特定する際、パケットヘッダ解析部１ｂにおいて、パケットヘッダを解析して、「発信元IPアドレス(srcIP)」、「着信先IPアドレス(dstIP)」、「発信元ポート番号(srcPort)」、「着信先ポート番号(dstPort)」、「プロトコル(Protocol)」の５つの属性の各値を読み出し、頻出フロー候補抽出部１ｃにおいては、予め定められた測定期間、予め定められた属性の組における、各属性値が同じパケット群（フロー）を抽出して、当該パケットの数を計数し、頻出フロー特定部１ｄにおいて、当該パケットの数が予め定められた閾値y*を超えるフローを頻出フローとして特定する。
【００２５】
頻出フロー候補抽出部１ｃおよび頻出フロー特定部１ｄにおいては、属性数の少ない属性の組から順に、当該属性の組における頻出フローを抽出すると共に、属性数のより多い属性の組における頻出フローの抽出を行う際には、属性数のより少ない属性の組において抽出した頻出フローの属性値を含むもののみを対象に行う。
【００２６】
例えば、予め定められる属性の組として、属性「発信元IPアドレス(srcIP)」のみからなる属性の組（第１のフロー）と、その属性「発信元IPアドレス(srcIP)」と他の属性との組み合わせで定義した属性の組（第２のフロー）を定義した場合、属性「発信元IPアドレス(srcIP)」のみからなる第１のフローでトラヒックが閾値を超えなければ、その属性との組み合わせで定義した第２のフローでは閾値を超えるトラヒックは生じ得ないことを利用し、トラヒックが閾値を超えない第１のフローの属性を含む第２のフローを、頻出フローの特定の対象から除く。このことにより、帯域を占有するトラヒックを発生させるフローの特定を効率的に行うことができる。
【００２７】
以下、このような頻出フロー特定装置１による、頻出フローの特定処理動作の詳細を説明する。先ず、本例の頻出フロー特定装置１による頻出フローを特定するための『第１の技術』について説明する。
【００２８】
『第１の技術』においては、読み込んだパケットヘッダ内の{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}の５つの属性を用いて、予め定めたこれら属性の組み合わせを同じくするパケット群をフローと定義する。
【００２９】
ここで、フローの定義は、以下に示す１５通りを考え、これらフローの定義の中で予め着目するいくつかのフローの定義に対して、サンプルされたパケット数が予め定めた閾値を超えるフローを頻出フローとして特定する。
【００３０】
尚、フローの定義は以下の通りとする。先ず、下記（１）〜（４）の４つのフローを定義する。
【００３１】
(1)「srcIPを同じくするパケット群をキー番号１のフローと定義」、
(2)「dstIPを同じくするパケット群をキー番号2のフローと定義」、
(3)「ProtocolとsrcPortを同じくするパケット群をキー番号3のフローと定義」、
(4)「ProtocolとdstPortを同じくするパケット群をキー番号4のフローと定義」する。
【００３２】
次に、以下の（５）〜（１０）の６つのフローを定義する。
【００３３】
(5)「キー番号1と2の組み合わせからなるフロー（つまり、{srcIP, dstIP}を同じくするパケット群）をキー番号5のフローと定義」、
(6)「キー番号1と3の組み合わせからなるフロー（つまり、{srcIP, srcPort, Protocol}を同じくするパケット群）をキー番号6のフローと定義」、
(7)「キー番号1と4の組み合わせからなるフロー（つまり、{srcIP, dstPort, Protocol}を同じくするパケット群）をキー番号7のフローと定義」、
(8)「キー番号2と3の組み合わせからなるフロー（つまり、{dstIP, srcPort, Protocol}を同じくするパケット群）をキー番号8のフローと定義」、
(9)「キー番号2と4の組み合わせからなるフロー（つまり、{dstIP, dstPort, Protocol}を同じくするパケット群）をキー番号9のフローと定義」、
(10)「キー番号3と4の組み合わせからなるフロー（つまり、{srcPort, dstPort, Protocol}を同じくするパケット群）をキー番号10のフローと定義」する。
以上のキー番号5〜10のフローを２つ組フローと呼ぶ。
【００３４】
さらに、以下の（１１）〜（１４）の４つのフローを定義する。
【００３５】
(11)「キー番号1,2,3の組み合わせからなるフロー（つまり、{srcIP, dstIP, srcPort, protocol}を同じくするパケット群）をキー番号11のフローと定義」、
(12)「キー番号1,2,4の組み合わせからなるフロー（つまり、{srcIP, dstIP, dstPort, protocol}を同じくするパケット群）をキー番号12のフローと定義」、
(13)「キー番号1,3,4の組み合わせからなるフロー（つまり、{srcIP, srcPort, dstPort, protocol}を同じくするパケット群）をキー番号13のフローと定義」、
(14)「キー番号2,3,4の組み合わせからなるフロー（つまり、{dstIP, srcPort, dstPort, protocol}を同じくするパケット群）をキー番号14のフローと定義」する。
以上のキー番号11〜14のフローを３つ組フローと呼ぶ。
【００３６】
最後に、以下の（１５）の１つのフローを定義する。
【００３７】
(15)「キー番号1,2,3,4の組み合わせからなるフロー（つまり、{srcIP, dstIP, srcPort, dstPort, protocol}を同じくするパケット群）をキー番号15のフローと定義」する。
【００３８】
次に、本例の頻出フロー特定装置１による頻出フローを特定するための『第２の技術』について説明する。
【００３９】
本『第２の技術』は、上述した『第１の技術』における、サンプルパケット数に対する閾値y*を決定する技術に関するものである。
【００４０】
ある有限の測定期間において、全部でN個のパケットが存在したと仮定し、頻出フローをある一定の割合φ（０＜φ＜１）以上のパケットを含むフローと定義する。
【００４１】
また、Xj,Yjをそれぞれ、フローjに含まれる母集団におけるパケット数、サンプルされたパケット数とする。また、Wを母集団の全N個のパケットからサンプルされたパケット数とする。
【００４２】
母集団からW=w個のパケットがサンプルされたとし、母集団内でφN個のパケットを持つフローを、予め定めた特定基準確率δidentより大きい確率で特定するための閾値y*を以下の数１で示す式で決定する。
【００４３】
【数１】
2011029986.tif 000003
【００４４】
次に、本例の頻出フロー特定装置１による頻出フローを特定するための『第３の技術』について説明する。
【００４５】
『第３の技術』は、上述の『第１の技術』における、あるキー番号keynumに対して頻出フローの候補を抽出するものである。
【００４６】
まずb*個のバケツ（Ｂｕｃｋｅｔ：バケット：バッファ、キュー）を用意し、Existence Counter（EC）と呼ばれるカウンタを、各バケツに1つ用意する。尚、b*は予め定めるバケツの数である。また、各バケツのECとは別にDeletion Counter（DC）と呼ばれるカウンタを1つ用意する。
【００４７】
サンプルパケット到着毎にキー番号keynumに関するそのパケットのキーc（例えば、keynum=1であれば、cは該サンプルパケットのsrcIPアドレス）を抽出し、cを格納しているバケツが存在すれば、そのバケツのECの値を一つ上げる。
【００４８】
もし、cがどのバケツにも格納されていなければ、cを新たに格納する。また、全てのバケツにc以外のキーが格納されているときは、cは格納せずに全バケツのECの値を一つ下げる。
【００４９】
もしECの値が0になったバケツがあれば、そのバケツが格納しているキーを削除する。また、全バケツのECの値を一つ下げた際、DCの値を一つ上げ、全バケツのECの値が一つ下げられた回数を格納しておく。
【００５０】
母集団からサンプルされたW＝w個のパケットについて上記の処理を終え、測定期間が終了したならば、バケツiのECiの値をみてECi+DC>=y*となるバケツに格納されているバケツiのキーを、頻出フローの候補として抽出する。
【００５１】
各フローのサンプルパケット数が閾値ｙ*を越えているかどうかをチェックする一般的な技術としては、フローごとにサンプルパケット数をカウントできるフローテーブルを用意し、測定期間終了後に、各フローのサンプルパケット数が閾値y*を越えているかどうかをチェックする技術が考えられるが、この技術だと、閾値未満のフローまでテーブルで管理する必要がある。
【００５２】
一般に、インターネットトラヒックにおいては、大多数のフローは少ないパケットしか出しておらず、一部のフローが多くのパケットを送出している（上述の非特許文献１参照）。従って、大多数のフローは結果的に管理する必要がなくなる。
【００５３】
それに対して、本例では、予め用意するb*個のバケツを使って、頻出フローの候補となるフローのみを抽出している。以下、b*を決める技術としての第４の技術を説明する。
【００５４】
『第４の技術』においては、上述の『第３の技術』におけるバケツのサイズb*を、以下の数２で示す式で決定する。尚、δbktは、予め定めるバケツ特定確率とよばれるものであり、数２で決まるバケツの数を用意すれば、少なくともδbktより大きな確率で、頻出フローは全てバケツに残る。また，Pbkt(b,δident)は、バケツの個数bおよび特定基準確率δidentが与えられたとき、特定キーが必ずバケツに残るのに必要なバケツの個数の下限値よりも、バケツの個数bが大きくなる、あるいは下限値と等しくなる確率を意味する。
【００５５】
【数２】
2011029986.tif 000004
【００５６】
次に、本例の頻出フロー特定装置１による頻出フローを特定するための『第５の技術』について説明する。
【００５７】
『第５の技術』においては、上述の『第３の技術』のように、サンプルパケットの系列に対して、サンプルパケット到着毎にバケツへの格納処理等を行うのと並行して、バケツとは別に、サンプルフローデータベースSFDを用意し、上述の『第１の技術』でのキー番号15で定義されるフロー情報を、SFDに、以下の手順で格納する。
【００５８】
サンプルパケットが到着したら、キー番号15に関するそのパケットのキーkey（つまり、key={srcIP, dstIP, srcPort, dstPort, Protocol}）をパケットヘッダから読み出し、既にSFDにそのkeyがエントリされていれば、そのkeyのcountkeyを１つカウントアップする。
【００５９】
未だSFDにエントリされていない新規keyからのパケットであれば、そのkeyをSFDに追加し、countkey =1とする。
【００６０】
以上を測定期間が終了するまで実施する。そうすることにより、SFDには、{key, countkey }（countkeyは、key毎のサンプルパケット数）が格納される。そして、カウンタcountkey>=y*となるkeyを、キー番号15における頻出フローの集合D15とする。
【００６１】
測定期間終了時点で生成されたSFDをもとに、上述の『第１の技術』で定義された各キー番号keynumに対する頻出フローを以下の手順で特定する。
【００６２】
尚、y*個以上のパケットがサンプルされ頻出フローと特定されるフローのキーを特定キーと呼び、キー番号がkeynumである特定キーの集合をDkeynum(1≦keynum≦15)とする。
【００６３】
また、頻出フローの候補である候補フローのキーを候補キーと呼び、キー番号がkeynumである候補キーの集合をCkeynum(1≦keynum≦15)とする。
【００６４】
１つ組のキー（キー番号1から4までのフローキー）を格納するバケツを各々のキー番号について用意する。そして、サンプルパケットの系列に対して、上述の『第３の技術』の手順で各キー番号に関するバケツへの格納処理を行う。
【００６５】
測定期間終了後、各バケツを調べ、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)を生成する。
【００６６】
次に、SFDのスキャンを行い、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、２つ組および３つ組の候補キーの作成、候補キーのカウンタの更新を行って、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【００６７】
こうすることにより、各フローの定義（１５種類）毎に、フロー当りサンプルパケット数をカウントすることを不要としている。
【００６８】
具体的には、１つ組の候補キー（キー番号1〜4）の集合だけをみれば、２つ組み（キー番号5〜10）、３つ組み（キー番号11〜14）の候補を作成できる点を利用している。
【００６９】
例えば、キー番号１の場合、すなわち、srcIPのみでフローを定義したときに、閾値を越えないフローは、それより細分化された２つ組みでフローを定義したとき（例えばキー番号５の{srcIP,dstIP}）には閾値を越えることはない。
【００７０】
次に、本例の頻出フロー特定装置１による頻出フローを特定するための『第６の技術』について説明する。
【００７１】
『第６の技術』においては、上述の『第５の技術』のように、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、２つ組および３つ組の候補キーの作成、候補キーのカウンタの更新を行って、特定キーの集合Dkeynum(1≦keynum≦15)を得る代わりに、測定期間が終了してSFD（{key,countkey}の集合）が生成された後、まず空のCkeynum(1≦keynum≦15)を用意する。
【００７２】
そして、まず、１つ組の各keynum (keynum=1〜4)に対し、SFD内の各keyについてキー番号keynumのキーcを調べる。
【００７３】
例えば、SFD内のkeyがkey={srcIP#a, dstIP#a, srcPort#a, dstPort#a, Protocol#a}だとすると、keynum=1の場合には、c=srcIP#aとなる。
【００７４】
そして、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumに、cを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【００７５】
また、Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【００７６】
この処理を、SFD内の全てのkeyに対して実施した後、c.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(1≦keynum≦4)に格納する。
【００７７】
２つ組のキー（keynum=5〜10）については、SFD内の各keyについて、まず、keyに含まれる１つ組のキーのうち、特定キーではないものを全てkeyから取り除く。
【００７８】
具体的には、例えば、key={srcIP#a, dstIP#a, srcPort#a, dstPort#a, protocol#a}とし、また、k=srcIP#aは集合D1には含まれないとすると、keyをkey={*, dstIP#a, srcPort#a, dstPort#a, protocol#a}に変更する。
【００７９】
次に、１つ組の特定キーから構成されるキーを生成し、生成したキーに含まれる２つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【００８０】
Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【００８１】
この処理をSFD内の全てのkeyに対して実施した後、Ckeynumの中からc.count>=y*となるキーcを抽出し、それを特定キーの集合Dkeynum(5≦keynum≦10)に格納する。
【００８２】
３つ組のキー（keynum=11〜14）については、SFDのスキャンを行う前に任意の部分集合が特定キーであるような候補キーの集合Ckeynum（11≦keynum≦14）を生成する。
【００８３】
その後、SFD内の各keyについて、キー番号keynumのキーcを調べる。
【００８４】
キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【００８５】
この処理をSFD内の全てのkeyに対して実施した後、Ckeynumの中からc.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(11≦keynum≦14)に格納する。
【００８６】
以上の手順によって、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【００８７】
参考として、この第６の技術の処理をコンピュータに実行させるための疑似コード（プログラム）を図３に示す。
【００８８】
次に、本例の頻出フロー特定装置１による頻出フローを特定するための『第７の技術』について説明する。
【００８９】
『第７の技術』においては、上述の第６の技術と同様の手順で１つ組のキー（keynum=1〜4）について特定キーの集合Dkeynum(1≦keynum≦4)を作成し、SFD内の各keyについて、まずkeyに含まれる１つ組のキーのうち、特定キーではないものを全てkeyから取り除く。
【００９０】
次に、１つ組の特定キーから構成されるキーを生成し、生成したキーに含まれる２つ組ならびに３つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【００９１】
キーcが候補キー集合Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【００９２】
この処理をSFD内の全てのkeyに対して実施した後、候補キー集合Ckeynumの中からc.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(5≦keynum≦14)に格納する。
【００９３】
以上の手順によって、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【００９４】
参考として、この第７の技術の処理をコンピュータに実行させるための疑似コード（プログラム）を図４に示す。
【００９５】
次に、本例の頻出フロー特定装置１による頻出フローを特定するための『第８の技術』について説明する。
【００９６】
『第８の技術』においては、上述の第５の技術において記載の、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、２つ組および３つ組の候補キーの作成、候補キーのカウンタの更新を行って、特定キーの集合Dkeynum(1≦keynum≦15)を得る処理として、まず、空のCkeynum(5≦keynum≦15)を用意する。
【００９７】
次に、１つ組のキー番号keynum (keynum=1〜4)について、SFD内のkeyとkeynumからキー番号keynumのキーcを調べる。
【００９８】
キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【００９９】
次に、keyに含まれる１つ組のキーのうち、候補キーではないものを全てkeyから取り除き、１つ組の候補キーから構成されるキーを生成し、生成したキーに含まれる２つ組および３つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【０１００】
キーcが候補キー集合Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１０１】
以上の処理をSFD内の全てのkeyに対して実施した後、候補キー集合Ckeynumの中からc.count>=y*となるキーcを抽出し、それを特定キーの集合Dkeynum(1≦keynum≦14)に格納する。
【０１０２】
以上の処理によって、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【０１０３】
参考として、この第８の技術の処理をコンピュータに実行させるための疑似コード（プログラム）を図５に示す。
【０１０４】
以下、以上に説明した第１〜第８の技術の処理動作を、図１，２における頻出フロー特定装置１を構成する図１に示す各処理部（１ａ〜１ｅ）の処理に対応付け、実施例１〜５として説明する。
【０１０５】
『実施例１』
図２においては、図１の頻出フロー特定装置１を適用するネットワークの構成例を示しており、この図２に示す例では、頻出フロー特定装置１は、ネットワーク内のノード２，３間に挿入される形で適用される。
【０１０６】
以下では、特定したい頻出フローの定義として、上述の『第１の技術』において記載した１５種類のフローの定義全てについてを対象とした場合の動作を示す。
【０１０７】
頻出フロー特定装置１は、上述の『第３の技術』に記載の処理手順で１つ組のキー(keynum=1〜4)各々について頻出フロー候補を抽出する機能、上述の『第５の技術』に記載の処理手順でサンプルフローをサンプルフローデータベースへ格納する機能、上述の『第８の技術』に記載の処理手順で１つ組の頻出フロー候補とサンプルフローデータベースを用いて２つ組および３つ組のキー（keynum=5〜15）について候補キーを作成し、最終的に各キー(keynum=1〜15)について頻出フローを特定する機能を具備している。
【０１０８】
まず、サンプリング部１ａでは、パケット到着毎に、カウンタCをカウントアップし、その後、その値を予め定めたサンプリング間隔1/f (fはサンプリングレートで例えばf=1/1000)で割った余りが０かどうかチェックする。
【０１０９】
もし余り０であれば、そのパケットをパケットヘッダ解析部１ｂへ転送する。同時に、後段ノードへもパケット転送する。もし余りが０でなければ、単に、後段ノードのみに転送する。
【０１１０】
尚、サンプリング部１ａでは、上述のように、1/fで割る代わりに、パケット到着毎に０から１の一様乱数を発生し、その値が予め定めたサンプリングレートfよりも小さければ、当該パケットをパケットヘッダ解析部１ｂへ転送する処理としても良い。
【０１１１】
パケットヘッダ解析部１ｂでは、転送されてきたパケットのヘッダ内の{発信元IPアドレス(srcIP)、着信先IPアドレス(dstIP)、発信元ポート番号(srcPort)、着信先ポート番号(dstPort)、プロトコル(Protocol)}を読み出し、それを頻出フロー候補抽出部１ｃおよびサンプルフロー管理部１ｅへ転送する。
【０１１２】
頻出フロー候補抽出部１ｃでは、上述の『第３の技術』に記載の処理手順を実行して、あるキー番号keynumに対して頻出フローの候補を抽出する。すなわち、まず、上述の『第４の技術』に記載の処理手順で数が決定される、b*個のバケツを用意し、Existence Counter（EC）と呼ばれるカウンタを、各バケツに1つ用意する。
【０１１３】
また、各バケツのECとは別にDeletion Counter（DC）と呼ばれるカウンタを1つ用意する。
【０１１４】
そして、サンプルパケット到着毎に、キー番号keynum=1〜4の各々に関するそのパケットのキーc（例えば、keynum=1であれば、キーcは該サンプルパケットのsrcIPアドレス）を抽出し、当該キーcを格納しているバケツが存在すれば、そのバケツのECの値を一つ上げる。
【０１１５】
もし、当該キーcがどのバケツにも格納されていなければ、cを新たにバケツに格納する。また、全てのバケツにc以外のキーが格納されているときは、cは格納せずに、全バケツのECの値を一つ下げる。
【０１１６】
そして、もし、ECの値が0になったバケツがあれば、そのバケツが格納しているキーを削除する。また、全バケツのECの値を一つ下げた際、DCの値を一つ上げ、全バケツのECの値が一つ下げられた回数を格納しておく。
【０１１７】
母集団からサンプルされたW＝w個のパケットについて上述の処理を終え、測定期間が終了したならば、バケツiのECiの値をみてECi+DC>=y*となるバケツに格納されているバケツiのキーを、頻出フローの候補として抽出する。
【０１１８】
尚、y*は予め定める閾値であり、上角の「第２の技術」において記載の処理手順で決定される。
【０１１９】
頻出フロー候補抽出部１ｃは、このようにして、頻出フロー候補を抽出すると、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)を頻出フロー特定部１ｄへ通知する。
【０１２０】
サンプルフロー格納部１ｅでは、サンプルフローデータベースSFDを用意し、キー番号15で定義されるフロー情報を、SFDに以下の処理手順で格納する。
【０１２１】
パケットヘッダ解析部１ｂからのサンプルパケットが到着すると、サンプルフロー格納部１ｅは、キー番号15に関するそのパケットのキーkey（つまり、key={srcIP, dstIP, srcPort, dstPort, Protocol}）が、既にSFDにそのkeyがエントリされているか否かを判定し、既にエントリされていれば、そのkeyのcountkeyを１つカウントアップする。
【０１２２】
まだ、エントリされていない新規keyからのパケットであれば、そのkeyをSFDに追加し、countkey =1とする。
【０１２３】
サンプルフロー格納部１ｅは、以上の処理を、測定期間が終了するまで実施する。そうすることにより、SFDには、{key, countkey }（countkeyは、key毎のサンプルパケット数）が格納される。
【０１２４】
頻出フロー特定部１ｄでは、頻出フロー候補抽出部１ｃから転送されてきた１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、２つ組および３つ組の候補キーの作成、候補キーのカウンタの更新を行って、特定キーの集合Dkeynum(1≦keynum≦15)を以下の手順で取得する。
【０１２５】
頻出フロー特定部１ｄは、まず、空のCkeynum(5≦keynum≦15)を用意する。
【０１２６】
次に、１つ組のキー番号keynum (keynum=1〜4)について、サンプルフロー格納部１ｅで格納しているSFD内のkeyとkeynumから、キー番号keynumのキーcを調べる。
【０１２７】
すなわち、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１２８】
次に、keyに含まれる１つ組のキーのうち、候補キーではないものを全てkeyから取り除き、１つ組の候補キーから構成されるキーを生成し、生成したキーに含まれる２つ組および３つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【０１２９】
また、キーcが候補キー集合Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１３０】
以上の処理をSFD内の全てのkeyに対して実施した後、Ckeynumの中からc.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(1≦keynum≦14)に格納する。
【０１３１】
以上のようにして、頻出フロー特定部１ｄは、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【０１３２】
以下、『実施例２』として、上述の『第６の技術』に記載の処理手順に基づく頻出フロー特定部１ｄによる頻出フローの特定技術を説明する。
【０１３３】
すなわち、本実施例２においては、頻出フロー特定部１ｄは、上述の実施例１のように、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、２つ組および３つ組の候補キーの作成、候補キーのカウンタの更新を行って、特定キーの集合Dkeynum(1≦keynum≦15)を得る代わりに、測定期間が終了してSFD（{key,countkey}の集合）が生成された後、まず空のCkeynum(1≦keynum≦15)を用意する。
【０１３４】
そして、頻出フロー特定部１ｄは、まず、各keynum (keynum=1〜4)に対し、SFD内の各keyについてキー番号keynumのキーcを調べる。例えば、SFD内のkeyがkey={srcIP#a, dstIP#a, srcPort#a, dstPort#a, Protocol#a}だとすると、keynum=1の場合には、c=srcIP#aとなる。
【０１３５】
次に、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【０１３６】
また、キーcが候補キー集合Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１３７】
以上の処理をSFD内の全てのkeyに対して実施した後、c.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(1≦keynum≦4)に格納する。
【０１３８】
次に、２つ組のキー（keynum=5〜10）については、SFD内の各keyについて、まずkeyに含まれる１つ組のキーのうち、特定キーではないものを全てkeyから取り除く。
【０１３９】
具体的には、例えば、key={srcIP#a, dstIP#a, srcPort#a, dstPort#a, protocol#a}とし、また、k=srcIP#aは特定キーの集合D1には含まれないとすると、keyをkey={*, dstIP#a, srcPort#a, dstPort#a, protocol#a}に変更する。
【０１４０】
次に、１つ組の特定キーから構成されるキーを生成し、生成したキーに含まれる２つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【０１４１】
また、キーcが候補キー集合Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１４２】
以上の処理をSFD内の全てのkeyに対して実施した後、候補キーの集合Ckeynumの中からc.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(5≦keynum≦10)に格納する。
【０１４３】
３つ組のキー（keynum=11〜14）については、SFDのスキャンを行う前に任意の部分集合が特定キーであるような候補キーの集合Ckeynum（11≦keynum≦14）を生成する。
【０１４４】
その後、SFD内の各keyについて、キー番号keynumのキーcを調べる。
【０１４５】
キーcが候補キー集合Ckeynumに含まれているかどうかを調べ、含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１４６】
この処理をSFD内の全てのkeyに対して実施した後、候補キーの集合Ckeynumの中からc.count>=y*となるcを抽出し、それを特定キーの集合Dkeynum(11≦keynum≦14)に格納する。
【０１４７】
以上のようにして、頻出フロー特定部１ｄは、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【０１４８】
次に、『実施例３』として、上述の『第７の技術』に記載の処理手順に基づく頻出フロー特定部１ｄによる頻出フローの特定技術を説明する。
【０１４９】
すなわち、本実施例３においては、頻出フロー特定部１ｄは、上述の実施例１のように、１つ組の候補キーの集合Ckeynum(1≦keynum≦4)から、２つ組および３つ組の候補キーの作成、候補キーのカウンタの更新を行って、特定キーの集合Dkeynum(1≦keynum≦15)を得る代わりに、上述の実施例２と同様の処理手順で、１つ組のキー（keynum=1〜4）について特定キーの集合Dkeynum(1≦keynum≦4)を作成し、SFD内の各keyについて、まずkeyに含まれる１つ組のキーのうち、特定キーではないものを全てkeyから取り除く。
【０１５０】
次に、頻出フロー特定部１ｄは、１つ組の特定キーから構成されるキーを生成し、生成したキーに含まれる２つ組ならびに３つ組の任意のキーcについて、候補キーの集合Ckeynumを探索し、当該キーcが候補キーの集合Ckeynumに含まれているかどうかを調べ、含まれていなければCkeynumにcを追加し、そのキーのカウンタ値c.countをc.count←countkeyとする。
【０１５１】
また、当該キーcが候補キーの集合Ckeynumに既に含まれているならば、そのキーcのカウンタ値c.countを、c.count←c.count+countkeyとする。
【０１５２】
この処理をSFD内の全てのkeyに対して実施した後、候補キーの集合Ckeynumの中からc.count>=y*となるキーcを抽出し、それを特定キーの集合Dkeynum(5≦keynum≦14)に格納する。
【０１５３】
以上のようにして、頻出フロー特定部１ｄは、特定キーの集合Dkeynum(1≦keynum≦15)を得る。
【０１５４】
以上、図１〜図５を用いて説明したように、本例では、例えば、図２における通信網のノード２，３において、サンプリング部１ａによるパケットサンプリングを行い、サンプルしたパケットの属するフロー情報を管理して、帯域を占有する頻出フローを特定する際、パケットヘッダ解析部１ｂにおいて、パケットヘッダを解析して、「発信元IPアドレス(srcIP)」、「着信先IPアドレス(dstIP)」、「発信元ポート番号(srcPort)」、「着信先ポート番号(dstPort)」、「プロトコル(Protocol)」の５つの属性の各値を読み出し、頻出フロー候補抽出部１ｃにおいては、予め定められた測定期間、予め定められた属性の組における、各属性値が同じパケット群（フロー）を抽出して、当該パケットの数を計数し、頻出フロー特定部１ｄにおいて、当該パケットの数が予め定められた閾値y*を超えるフローを頻出フローとして特定する。
【０１５５】
頻出フロー候補抽出部１ｃおよび頻出フロー特定部１ｄにおいては、属性数の少ない属性の組から順に、当該属性の組における頻出フローを抽出すると共に、属性数のより多い属性の組における頻出フローの抽出を行う際には、属性数のより少ない属性の組において抽出した頻出フローの属性値を含むもののみを対象に行う。
【０１５６】
例えば、予め定められる属性の組として、属性「発信元IPアドレス(srcIP)」のみからなる属性の組（第１のフロー）と、その属性「発信元IPアドレス(srcIP)」と他の属性との組み合わせで定義した属性の組（第２のフロー）を定義した場合、属性「発信元IPアドレス(srcIP)」のみからなる第１のフローでトラヒックが閾値を超えなければ、その属性との組み合わせで定義した第２のフローでは閾値を超えるトラヒックは生じ得ないことを利用し、トラヒックが閾値を超えない第１のフローの属性を含む第２のフローを、頻出フローの特定の対象から除く。このことにより、帯域を占有するトラヒックを発生させるフローの特定を効率的に行うことができる。
【０１５７】
このように、本例によれば、各フローの定義毎にフロー当りサンプルパケット数をカウントすることなく、各フローの定義に対する頻出フロー（トラヒック全体のうち、ある一定以上の割合を占めるフロー）を特定することができ、種々のフロー定義数に比例して、フロー管理やパケット処理の負荷が増大してしまうこともなく、当該頻出フローの特定を効率的に行うことが可能となる。
【０１５８】
尚、本発明は、図１〜図５を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、図２において示したように、図１の頻出フロー特定装置１は、ネットワーク内のノード２，３間に挿入される形で適用しているが、あるノードの空きポートへポートミラーして、その先に本装置を設置してパケットを解析することにより、頻出フローを特定する構成としても良い。
【０１５９】
また、本例のシステムを構成するコンピュータ装置の構成に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【符号の説明】
【０１６０】
１：頻出フロー特定装置、１ａ：サンプリング部、１ｂ：パケットヘッダ解析部、１ｃ：頻出フロー候補抽出部、１ｄ：頻出フロー特定部、１ｅ：サンプルフロー格納部、２，３：ノード、６１，６２：フロー特定装置。
【図１】
2011029986.tif 000007
【図２】
2011029986.tif 000008
【図３】
2011029986.tif 000009
【図４】
2011029986.tif 000010
【図５】
2011029986.tif 000011
【図６】
2011029986.tif 000012