(57)【要約】【課題】ＳＴ法を階層的に用いることにより、サンプルパケット情報を用いて効果的に大量バースト生成フローを特定する。【解決手段】パケットサンプルにより得られた統計データのみを用いて、他のフローに与える影響が大きく平滑化の効果の高い、レート変動とフローサイズの大きなフロー（大量バースト生成フローと言う）をアクセスルータにおいて特定し、特定した大量バースト生成フローを対象に、アクセスルータにおいてフロー単位のキューイングを行うことにより、長期平均レートに平滑化する。パラメータ設定装置１０１により、任意の特定曲線を実現するタイムアウト時間とサンプリング周期が設計され、大量バースト生成フロー特定装置１０４は、フローテーブル１０３に登録されたフローから高レートフローを特定し、大量バースト生成フローリスト１０５に出力する。【選択図】図１
2008053878.tif 000002
【特許請求の範囲】
【請求項１】
パケットサンプルにより得られた統計データのみを用いて、他のフローに与える影響が大きく平滑化の効果の高い、レート変動とフローサイズの大きな大量バースト生成フローをアクセスルータにおいて特定し、特定した大量バースト生成フローを対象に、該アクセスルータにおいてフロー単位のキューイングを行うことにより、長期平均レートに平滑化することを特徴とする大量バースト生成フローの特定方法。
【請求項２】
レート変動とフローサイズの大きな大量バースト生成フローを特定する特定方法において、
まず測定周期Φ１を考え、該測定周期Φ１をｋ個の測定周期Φ２に分割し、各測定周期Φ２内でサンプルされたパケット数が閾値Ｙ以上となったフローを該測定周期Φ２において特定し、ｋ個の測定周期Φ２中に特定された回数をフローごとにカウントし、特定回数がＺ回以となったフローを最終的に大量バースト生成フローとして特定することを特徴とする大量バースト生成フローの特定方法。
【請求項３】
請求項２に記載の大量バースト生成フローの特定方法において、
前記測定周期Φ１内の特定回数が閾値Ｚ’（ただし、Ｚ’＞Ｚ）を超えたフローは、特定対象から除外して、高レートで長時間パケットを送出し続けるようなフローの特定を避けることを特徴とした大量バースト生成フローの特定方法。
【請求項４】
パケットサンプルレートや特定判断閾値を設定するパラメータ設定装置と、
パケットを一定周期ごとにサンプルするパケットサンプル装置と、
サンプルされたフローのサンプルパケット数と特定回数を記憶するフローテーブルと、
該フローテーブルに記憶されているサンプル回数と特定回数に応じて大量バースト生成フローを特定する大量バースト生成フロー特定装置と、
特定された大量バースト生成フローを出力する大量バースト生成フローリストと
を有することを特徴とする大量バースト生成フロー特定システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットサンプルから得られた情報を用いて、フローサイズが大きくレート変動が大きい大量バースト生成フローを特定する方法およびそのシステムに関する。
【背景技術】
【０００２】
アクセス回線の大容量化に伴って、ユーザは短時間に大量のパケット送出が可能となる。その結果、形成されるバーストは、中継ルータにおける待ちキュー長を増大させ輻輳の大きな要因となる。これらバーストの網に与える影響を排除するためには、アクセスルータにおいてフロー単位のキューイングによるバーストの平滑化が有効である。しかし、そのための処理負荷や所要メモリ量は大きく、全てのフローに対して平滑化処理を行うことは非現実的である。
【０００３】
網には、レート変動やフローサイズの小さなフローも存在する。平滑化処理に伴うパケット損失は避けるべきであり、そのため平滑化後の転送レートは長期平均レートとなり、レート変動が小さいフローは平滑化効果が期待できない。また、フローサイズが小さく生成バースト数の少ないフローは、他のトラヒックに与える影響が小さく、平滑化の効果も限定的となる。そのため、平滑化を行う対象は、レート変動が大きくフローサイズの大きな、平滑化の効果が高いフローに限定することが望ましい。ここでは、このようなフローを大量バースト生成フローと定義する。大量バースト生成フローをフロー計測によって特定し、特定したフローのみを平滑化の対象とすれば、限られたルータ資源を効率的に用いながら平滑化処理を効果的に実現できる。
【０００４】
従来の高レートフロー特定方法では、フローレートに対する特定確率が定式化されておらず、特定されるフローレートの閾値の与え方が明らかではなかった。全てのパケットに対して特定のための処理を行う方法は、高速回線への適用が困難である。また、ＲＥＤ（Ｒａｎｄｏｍ  Ｅａｒｙ  Ｄｅｔｅｃｔｉｏｎ）の使用を前提とした方法は、特定閾値となるフローレートを明示的に与えることができるが、ＲＥＤの使用が前提であるため、ＲＥＤを用いないルータには適用できず、やはり任意のフローレートに対する特定確率が定式化されていないため、特定精度が明らかでない。
【０００５】
ところで、フローサイズとフローレートには正の強い相関があることが知られているため、大サイズフローの特定方式で高レートフロー特定の代用を図ることが考えられるが、一般に、フローサイズとフローレートとの関連を定式化することができないため、特定閾値となるフローレートを明示的に与えることができず、特定曲線も得られないため、特定精度も明らかでない。
また、パケットサンプリングにより高レートフローのフローレートを高精度に推定するアプローチもあるが、フローレートの推定を目的としているため、特定の閾値となるフローレートを与えたときの任意のフローレートに対する特定確率が定式化されておらず、やはり特定精度が明らかでない。
【０００６】
高レートフローの特定を行う際には、高レートと定義するフローレートの閾値ｆ＊とその特定確率Ｈ＊を設計できることが、実用上重要である。さらに、フローレートｆがｆ＜ｆ＊のフローが誤って特定される確率（ＦＰＲ：Ｆａｌｓｅ  Ｐｏｓｉｔｉｖｅ  Ｒａｔｉｏ）と、ｆ≧ｆ＊のフローが誤って特定されない確率（ＦＮＲ：Ｆａｌｓｅ  Ｎｇａｔｉｖｅ  Ｒａｔｉｏ）を明確にし、特定精度を明らかにすることが重要である。そのためには、ｆ＊とＨ＊を与えたときの任意のｆに対する特定確率Ｈ（特定曲線）を明らかにする必要がある。
【０００７】
そこで、本発明者は、サンプル情報から高精度で高レートフローを特定するＳｈｏｒｔ  Ｔｉｍｅｏｕｔ法（ＳＴ法と表記）を提案した（特願２００５−００３８６８号明細書及び図面）（特許文献１参照）。パケットサンプルでは、フロー統計値を収集するためにフローテーブルが作成されるが、最後にサンプルされた時刻からタイムアウト時間Ｔ内に同一フローに属するパケットが新たにサンプルされなかった場合に、フローテーブルからフローのエントリを消去する。ＳＴ法では、Ｔを数〜数１０サンプル周期という短い時間に設定し、Ｔ内に２個のパケットがサンプルされたフローを高レートフローとして特定する。ＳＴ法の原理は非常に単純であり、実装が容易であること、また、所要メモリサイズが小さいという特質がある。
【０００８】
フローを発着ＩＰアドレス、発着ポート番号、プロトコルタイプが共通のパケットの集合と定義する。大容量リンクでは、同時に流れるフロー数が膨大な数となるため、全てのフローを計測対象とすることは困難であり、一定周期で取出したパケットのみを計測の対象とするパケットサンプルが有効である。ＳＴ法は、パケットサンプルを用いて高レートフローを特定する方法である。ＳＴ法は、長さがφ（ｓ）の測定期間Φを定め、各フローに対してΦ内に到着したパケット数をｕとするとき、フローレートｆをｆ≡ｕ／φ（ｐｐｓ）と定義する。パケット到着率∧（ｐｐｓ）はΦの間一定とし、Ｎパケットごとに１個のパケットをサンプルする。フローのトラヒック比率ｐをｐ≡ｆ／∧と定義し、任意に定めた閾値ｐ＊に対してｐ≧ｐ＊のフローを高レートフローと定義し、Φ内で２個のパケットがサンプルされたフローを高レートフローとして特定する。ｐ＝ｐ＊のフローを確率Ｈ＊で特定することを考え、任意のｐ＊とＨ＊を実現するＹとＤ（すなわちＮ）の組を次式で算出する。
【０００９】
【数１】
2008053878.tif 000003
【００１０】
その後に、本発明者は、ＳＴ法を改良し、Ｙ個のパケットがタイムアウトしないてサンプルされたフローを特定する方法を提案した（特願２００５−１８１９６８号明細書及び図面）（特許文献２参照）。上記方法によれば、与えられたパケット到着率と計測時間とから、所望の特定レート閾値とその特定確率を満足する特定曲線を与えるパラメータ設計を行いながら、パケットサンプリングにより簡易な方法をメモリサイズを抑えるとともに、高レートフローを高精度で特定することができるようにしている。
上記方法の動作原理は、下記の通りである。
まず、フローを発着ＩＰアドレス、発着ポート番号、プロトコルタイプが共通のパケットの集合と定義する。そして、長さがφ（ｓ）の任意の測定期間Φを定め、各フローに対して、Φ内に到着したパケット数をｕとするとき、フローレートｆをｆ≡ｕ／φ（ｐｐｓ）と定義する。任意に定めた閾値ｆ＊に対して、ｆ≧ｆ＊のフローを高レートフローと定義し、着目リンクにおいて、高レートフローをΦ内で特定することを考える。
【００１１】
測定期間Φの時間長をφ（ｓ）とし、着目リンクのパケット到着率∧（ｐｐｓ）はΦの間一定であるとする。そして、一定周期Ｎパケットごとに１個のパケットをサンプルする。このとき、平均サンプリング間隔はＮ／∧（ｓ）となる。平均的には高レートフローであるほどサンプルされる確率が高くなる。そのため、単純に１個以上のパケットがサンプルされたフローを全て高レートフローとして特定する方法が考えられる。以後、この方法をＮａｉｖｅ  Ｓａｍｐｌｉｎｇ法（ＮＳ法と表記）と呼ぶ。この方法は、直感的で実現も容易であるが、特定の判断基準が大雑把であるため特定精度が低い。
【００１２】
パケットサンプリングを行うルータでは、最後にパケットがサンプルされてから、タイムアウト時間Ｔ内に新たにパケットがサンプルされなかった場合に、フローテーブルに保持されたフロー状態を消去する。通常のパケットサンプリングはフロー統計値の収集を目的としており、Ｔは通常、１５秒や３０秒といった大きな時間に設定される。しかし、パケットサンプルの目的を高レートフローの特定に限定した場合、必ずしもＴを大きく設定する必要はない。
【００１３】
高レートフローのパケットは短い間隔で到着することから、そのパケットがサンプルされる間隔は短くなる傾向にある。そこで、Ｔを数〜数１０サンプル周期という短い時間に設定し、タイムアウトしないでＹ個のパケットがサンプルされたフローを高レートフローとして特定することを提案する。すなわち、各々の連続するサンプル間隔がＴ以内でＹ個のパケットがサンプルされたフローを特定する。以後、パラメータＹによって規定される上記の方法をＳｈｏｒｔ  Ｔｉｍｅｏｕｔ−Ｙ法（ＳＴ−Ｙ法と表記）と呼ぶ。
ここでは、タイムアウト時間Ｔを、Ｋを任意の整数をとるパラメータとしてＫサンプル周期（Ｔ＝ＫＮ／∧）で与える。ＳＴ−Ｙ法は、パラメータＫとＮを調整することにより、任意の特定曲線を実現する。
【００１４】
【特許文献１】特願２００５−００３８６８号明細書及び図面
【特許文献２】特願２００５−１８１９６８号明細書及び図面
【発明の開示】
【発明が解決しようとする課題】
【００１５】
前述したＳＴ法は、測定期間Φの時間スケールの高レートフローを特定するため、φを例えば１０ｍｓといった短時間に設定すれば、ＳＴ法を用いてピークレートの高いバーストを有するフローを特定できる。しかしこの場合、ピークレートが高くてもフローサイズが小さく、他のトラヒックに与える影響が小さなフローも同様に特定される。一方、φを例えば１ｓといった長時間に設定すれば、やはりＳＴ法を用いてフローサイズの大きいフローを特定することができる。しかしこの場合、フローサイズが大きくてもピークレートが低く、レート変動が小さいため、平滑化の効果が期待できないフローも同様に特定される。
【００１６】
（目的）
本発明の目的は、上述のような課題を解決し、ＳＴ法を階層的に用いることにより、サンプルパケット情報を用いて効果的に大量バースト生成フローを特定することができるパケットサンプルを用いた大量バースト生成フロー特定方法およびそのシステムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明によるパケットサンプルを用いた大量バースト生成フロー特定方法は、パケットサンプルにより得られた統計データのみを用いて、他のフローに与える影響が大きく平滑化の効果の高い、レート変動とフローサイズの大きなフロー（大量バースト生成フローと言う）をアクセスルータにおいて特定し、特定した大量バースト生成フローを対象に、アクセスルータにおいてフロー単位のキューイングを行うことにより、長期平均レートに平滑化することを特徴としている。
また、本発明は、測定周期Φ１を考え、測定周期Φ１をｋ個の測定周期Φ２に分割し、各測定周期Φ２内でサンプルされたパケット数が閾値Ｙ以上となったフローをその測定周期Φ２において特定し、ｋ個の測定周期Φ２中に特定された回数をフローごとにカウントし、特定回数がＺ回以上になったフローを最終的に大量バースト生成フローとして特定することを特徴としている。すなわち、本発明は、先に提案したＳＴ法で用いる測定周期内をさらに細かな測定周期に分割し、２種の測定結果からバーストを効率良く特定する方法であ
さらに、本発明では、高レートで長時間パケットを送出し続けるようなフローを特定することを避けるため、測定周期Φ１内の特定回線が閾値Ｚ’（ただし、Ｚ’＞Ｚ）を超えたフローは特定対象から除外することも特徴としている。
【発明の効果】
【００１８】
本発明によれば、アクセスルータにおいて、パケットサンプルから得られた情報を用いてフローサイズが大きくレート変動が大きい大量バースト生成フローを特定し、特定されたフローに対して平滑化処理を行うことにより、限られたルータ資源を用いて効果的に輻輳を緩和できる、という効果がある。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施形態を図面により詳細に説明する。
図１は、本発明の一実施形態に係る大量バースト生成フロー特定装置の構成図である。
図１において、１０１はパラメータ設定装置、１０２はパケットサンプル装置、１０３はフローテーブル、１０４は大量バースト生成フロー特定装置、１０５は大量バースト生成フローリストである。メモリに内蔵された大量バースト生成フローリスト１０５以外の装置は、いずれもＣＰＵ、メモリ等を内蔵したコンピュータで構成され、プログラムを実行することにより、それぞれの機能を逐行する。
【００２０】
パラメータ設定装置１０１により、パケットサンプルレートや特定判断閾値ＹとＺが設定される。パケットサンプル装置１０２によりパケットが一定周期ごとにサンプルされる。
フローテーブル１０３によりサンプルされたフローのサンプルパケット数と特定回数が記憶される。大量バースト生成フロー特定装置１０４により、フローテーブル１０３に記憶されているサンプル回数と特定回数に応じて大量バースト生成フローが特定され、大量バースト生成フローリスト１０５に出力される。
【００２１】
（大量バースト生成フロー特定方法）
以下、本発明の大量バースト生成フロー特定方法について説明する。
まず、測定周期Φ１を考え、その長さをΦ１（ｓ）とする。そして、Φ１をｋ個の測定周期Φ２に分割する。測定周期Φ２の長さをΦ２（ｓ）とすると、ΦＩ＝ｋΦ２となる。そして、ＳＴ法をΦ２の各々の測定周期で実施し、ｋ個のΦ２中に特定された回数をフローごとにカウントし、特定回数がＺ回以上となったフローを最終的に大量バースト生成フローとして特定する。フローサイズが大きくてもレート変動が小さいフローは測定周期測定周期Φ２の時間スケールで特定されず、またレート変動が大きくてもフローサイズが小さいフローは特定回数が少ないため、共にΦ１内の特定回数が少なく、最終的に特定されない。
この結果、フローサイズとレート変動が大きい大量バースト生成フローのみを効果的に特定できる。なお、高レートで長時間パケットを送出し続けるようなフロー（レート変動が小さいため、平滑化の効果が期待できない）も特定されるため、Φ１内の特定回数が閾値Ｚ’（ただし、Ｚ’＞Ｚ）を超えたフローは特定対象から除外する。
【００２２】
（比較評価）
本発明の基本的な有効性を確認するため、計算機シミュレーションによる評価を行った。以下の三種類のフローを混在させた。
ＶＲＬＳ：ｖａｒｉａｂｌｅ−ｒａｔｅ  ｌａｒｇｅ−ｓｉｚｅ  ｆｌｏｗ：レート変動とサイズの大きなフローであり、大量バースト生成フローに相当する。ｏｎ−ｏｆｆ過程によりモデル化し、ｏｎ期間中はピークレートが１００Ｍｂｐｓになるようパケットを指数分布に従う間隔で発生させ、ｏｎ期間中はフローごとに１／２４０〜１／８０ｓの範囲でランダムに設定し、平均レートが２０Ｍｂｐｓになるようにｏｆｆ期間長を設定した。１０本のＶＲＬＳフローを多重させた。
ＣＲＬＳ：ｃｏｎｓｔａｎｔ−ｒａｔｅ  ｌａｒｇｅ−ｓｉｚｅ  ｆｌｏｗ：レートが一定でサイズの大きなフローであり、フローごとにレートを１０Ｍｂｐｓ〜３０Ｍｂｐｓの範囲でランダムに設定した。評価期間中、終始アクティブであり、パケットは指数分布に従う間隔で発生させた。やはり１０本のＣＲＬＳフローを多重させた。
ＳＳ：ｓｍａｌｌ−ｓｉｚｅ  ｆｌｏｗ：サイズの小さなフローであり、フローサイズを平均が１Ｍｂｙｔｅの指数分布で与え、平均が２ｍｓの指数分布に従う間隔でＳＳフローを多重させた。各フローのレートを１０Ｍｂｐｓ〜１００Ｍｂｐｓの範囲でランダムに設定し、各フローがアクティブである間、指数分布に従う間隔でパケットを発生させた。
【００２３】
パケット長は全て１５００ｂｙｔｅとし、φ１＝１ｓ、φ２＝１０ｍｓ、Ｙ＝８、Ｚ＝７とした。また、Ｚ’については考慮しなかった。
図２は、フローごとの散布図である。図２では、横軸をφ１＝１ｓ内の転送パケット数（長期平均レ−ト）、縦軸をφ２＝１０ｍｓ内の転送パケット数の最大値（短期ピークレート）としたときのフローを示している。
図２（ａ）は、全フローを示す。図２（ｂ）は、φ１＝１ｓとしたＳＴ法により特定されたフロ−を示す。図２（ｃ）は、φ２＝１０ｍｓとしたＳＴ法により特定されたフローを示す。図２（ｄ）は、本発明により特定されたフローを示す。φを長期に設定してＳＴ法を用いると、ＣＲＬＳフローが、またφを短期に設定してＳＴ法を用いると、ＳＳフローが、、各々誤って特定されることが分かる。しかし、本発明を用いれば、ＶＲＬＳフローを効果的に特定できることが確認できる。
【００２４】
（特定例）
図３は、本発明の特定例を示す説明図である。
ここでは、Φ内に３本のフローから合計で１２個のパケットがサンプルされた場合を示している。Ｋ＝２、Ｙ＝４とすると、フロー３のみが特定される。フロー３からは、タイムアウトしないでＹ＋１個のパケットがサンプルされているため、Ｙ番目のパケットがサンプルされた時点で特定される。フロー２からもΦ内にフロー３と同数（５）のパケットがサンプルされているが、２番目と３番目のパケットがサンプルされる間でタイムアウトするため、フロー２は特定されない。
【００２５】
任意の時点で、フローテーブルにエントリされているフロー数をｎとすると、これらｎ本の全てのフローから１個以上のパケットが過去Ｔ以内にサンプルされたはずである（さもなければ、タイムアウトするためエントリが消去される）。そのためには、少なくともｎ個のパケットサンプルが過去Ｔ内で必要であるが、Ｔ内にはＫ個のパケットがサンプルされるため、ｎ≦Ｋが成立する。すなわち、ＳＴ−Ｙ法では、最大でもＫ個のフローが同時にエントリされるだけであるため、必要メモリ量はＫで上限を抑えることができる。
【００２６】
（特定確率の導出）
以下では、Ｙ−Ｓｈｏｒｔ  ｔｉｍｅｏｕｔ法の特定確率を解析的に導出し、特定フローレート閾値ｆ＊とその特定確率Ｈ＊を実現するためのパラメータ設定法について説明する。
Φの間に到着する総パケット数をＬ、総サンプルパケット数をＤとすると、Ｌ＝∧φ、Ｄ＝Ｌ／Ｎとなる。ＤはＤ≧Ｙを満たす必要がある。フローレートｆのフローのΦ内におけるトラヒック比率ｐをｐ≡ｆ／∧と定義し、Φ中は着目フローから一定のレートｆでパケットが着目リンクに到着すると仮定する。多重フロー数が十分に多い場合、サンプルされるパケットは各々独立であり、サンプルされたパケットがトラヒック比率ｐのフローに属している確率はΦの間、常にｐとなる。ｆはｐに比例することから、ｆの代わりにｐに対する特定確率Ｈを導出する。また、特定の閾値をｆ＊で規定する代わりにｐ＊で規定し、与えられたＬから、トラヒック比率がｐ＊のフローを確率Ｈ＊で特定することを考える。
【００２７】
ｑｙ（ｐ，ｊ）を、区間Φにおいてトラヒック比率がｐの着目フローのパケットがｊ個サンプルされ、かつ着目フローが特定されない確率と定義する。そして、ｑｙ（ｐ，ｊ）＞０となるｊの最大値をＪと定義する。
図４は、ｊの最大値を実現するパケットサンプリングパターンの説明図である。
Ｔ以内にＹ個以上のパケットがサンプルされると、着目フローは特定されるため、図４に示すように、着目フローのパケットがＹ−１個連続してサンプルされる（図４中、黒丸）期間と、着目フロー以外のパケットがＫ個連続してサンプルされる（図４中、白丸）期間が交互に現われる場合に、着目フローが特定されないという条件でｊが最大となる（図４は、Ｙ＝３、Ｋ＝２の場合）。よって、Ｊは次式（２）となる。
【００２８】
【数２】
2008053878.tif 000004
このとき、トラヒック比率がｐのフローの特定確率ＨＹ（ｐ）は、次式（３）で与えられる。
【００２９】
【数３】
2008053878.tif 000005
以下では、０≦ｊ≦Ｊの各ｊに対するｑＹ（ｐ，ｊ）を導出する。
まず、０≦ｊ≦Ｙ−１のときは、着目フローは必ず特定されない。一方で、Ｄ個のサンプルにおいて着目フローのパケットがｊ個サンプルされる確率は二項分布に従うことから、ｑＹ（ｐ，ｊ）は次式（４）で得られる。
【００３０】
【数４】
2008053878.tif 000006
しかし、Ｙ≦ｊ≦Ｊのときは、着目フローのパケットがサンプルされる位置によって着目フローが特定される場合とされない場合があるため、ｑＹ（ｐ，ｊ）はこのような簡易な式で求めることはできない。Ｙ≦ｊ≦ＪにおけるｑＹ（ｐ，ｊ）を導出するため、Ａ（ｄ）、ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）、αＹ（ｊ，ｗ）を以下のように定義する。
区間Ａ（ｄ）はΦ内の任意の連続するｄ個のサンプルが行われる区間であり、ｄ＝Ｄのとき、Ａ（ｄ）＝Φとなる。ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）は、区間Ａ（ｄ）において着目フローのパケットがｊ個サンプルされ、かつ、最後（ｊ番目）のサンプル位置が区間Ａ（ｄ）の最後のサンプル位置から遡ることｖ番目のサンプル位置であり、区間Ａ（ｄ）の終了時点でフローテーブル内の着目フローのエントリのカウンタ値がｗであり（タイムアウトしないでｗ個サンプルされている）、かつ、着目フローがこの間、特定されない確率である。
【００３１】
また、与えられたｊとｗに対して、ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）＞０となるｄの最小値をαＹ（ｊ，ｗ）と定義する（ｄの最小値はｊとｗに依存するためαＹはｊとｗの関数となる）。
図５は、ｄの最小値を実現するパケットサンプリングパターンの説明図である。
ここでは、ｄの最小値αＹ（ｊ，ｗ）を与えるパケットサンプルパターンを示す（図５では、Ｙ＝３、Ｋ＝３、ｊ＝５、ｗ＝１の場合）。
ｄが最小となるのは、Ａ（ｄ）の末尾から連続してｗ個のサンプル位置で着目フローのパケットがサンプルされ、残るｊ−ｗ個の着目フローのパケットがＫのブランクを挟んでＹ−１個以下のクラスタを形成する場合であるため、αＹ（ｊ，ｗ）の値は次式（５）となる。
【００３２】
【数５】
2008053878.tif 000007
ｑＹ（ｐ，ｊ）は、ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）を全てのｖとｗについて足し合わせることにより導出できる。ｗ≧Ｙのとき、着目フローはＡ（ｄ）内で特定されるため、０≦ｗ≦Ｙ−１のｗについてのみ考えればよい。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施形態に係るパケットサンプルを用いた大量バースト生成フロー特定システムのブロック図である。
【図２】フローごとの長期平均レートと短期ピークレートに関する散布図である。
【図３】本発明の高レートフローの特定例を示す説明図である。
【図４】ｊの最大値を実現するパケットサンプリングパターンを示す図である。
【図５】ｄの最小値を実現するパケットサンプリングパターンを示す図である。
【符号の説明】
【００３４】
１０１  パラメータ設計装置
１０２  パケットサンプリング装置
１０３  フローテーブル
１０４  大量バースト生成フロー特定装置
１０５  大量バースト生成フローリスト
Ｌ  総パケット数
Ｄ  総サンプルパケット数
Ｙ  パラメータ（任意の整数）
Ｋ  パラメータ（任意の整数）
【図１】
2008053878.tif 000008
【図２】
2008053878.tif 000009
【図３】
2008053878.tif 000010
【図４】
2008053878.tif 000011
【図５】
2008053878.tif 000012