(57)【要約】【課題】ＳＴ法を改良し、Ｙ個以上のパケットが連続して（タイムアウトしないで）サンプルされたフローを特定する方法を考え、特定精度の向上を図る。【解決手段】パラメータ設計装置１０１は、任意の特定曲線を描くように各点を実現するタイムアウト時間とサンプリング周期を設計し、測定期間中に、パケットサンプリング装置１０２が着目リンクを流れるパケットを予め定めた周期でサンプリングを行い、サンプリング装置１０２は、サンプリング情報に基づいてフローを登録したフローテーブル１０４の内容を更新し、フロー情報消去装置１０３は、タイムアウト時間が経過したフロー情報をフローテーブル１０４から消去し、高レートフロー特定装置１０５はフローテーブル１０４に登録されたフローから高レートフローを特定し、高レートフローリスト１０６に出力する。【選択図】図２
2007005994.tif 000002
【特許請求の範囲】
【請求項１】
パケットサンプリングによって得られた情報を用いてトラヒックを計測し、与えられた計測期間内にタイムアウトすることなく予定数のパケットがサンプリングされた高レートフローを特定する方法において、
パラメータ設計装置は、プログラムを実行することにより、任意の特定曲線を描くように各点を実現するタイムアウト時間とサンプリング周期を設計し、
測定期間中に、パケットサンプリング装置が着目リンクを流れるパケットを予め定めた周期でサンプリングを行い、
前記サンプリング装置は、サンプリング情報に基づいてフローを登録したメモリのフローテーブルにアクセスして、該フローテーブルの内容を更新し、
フロー情報消去装置は、該フローテーブルにアクセスして前記タイムアウト時間が経過したフロー情報を該フローテーブルから消去し、
高レートフロー特定装置は該フローテーブルに登録されたフローから高レートフローを特定し、該高レートフローを高レートフローリスト・メモリに出力する
ことを特徴とする高レートフロー特定方法。
【請求項２】
パケットサンプリングによって得られた情報を用いてトラヒックを計測し、与えられた計測期間内にタイムアウトすることなく予定数のパケットがサンプリングされた高レートフローを特定する方法において、
コンピュータ制御の描画装置により、与えられた特定フローレートの閾値と、該特定フローレートの閾値の特定確率を満足する特定曲線を描き、該特定曲線を実現するタイムアウト時間とサンプリング周期の組を導出することを特徴とする高レートフロー特定方法。
【請求項３】
パケットサンプリングによって得られた情報を用いてトラヒックを計測し、与えられた計測期間内にタイムアウトすることなく予定数のパケットがサンプリングされた高レートフローを特定する方法において、
コンピュータ制御の描画装置により、与えられた特定フローレートの閾値と、該特定フローレートの閾値の特定確率を満足する特定曲線を描き、該特定曲線を実現するタイムアウト時間とサンプリング周期の選択可能な複数の組から、ネットワークの運用方針に基づいて適用する組を選択することを特徴とする高レートフロー特定方法。
【請求項４】
パケットサンプリングによって得られた情報を用いてトラヒックを計測し、与えられた計測期間内にタイムアウトすることなく予定数Ｙのパケットがサンプリングされた高レートフローを特定する方法において、
サンプルパケット数をｊ、ｊの最大値をＪ、総サンプルパケット数をＤ、サンプルされたパケットのトラヒック比率をｐ、ｑＹ（ｐ，ｊ）をｐの着目フローのパケットがｊ個サンプルされ、かつ着目フローが特定されない確率とした時、ｊの最大値は次式で与えられ、
【数１】
2007005994.tif 000022
トラヒック比率がｐのフローの特定確率ＨＹ（ｐ）は、次式で与えられることを特徴とする高レートフロー特定方法。
【数２】
2007005994.tif 000023
【請求項５】
任意の特定曲線を実現するタイムアウト時間とサンプリング周期を設計するためのパラメータ設計装置と、設計されたタイムアウト時間によりフロー情報の消去を行うフロー情報消去装置と、設計されたサンプリング周期によりパケットのサンプリングを行うパケットサンプリング装置と、測定期間中に該パケットサンプリング装置により着目リンクを流れるパケットが一定周期でサンプリングされ、その情報に基づいて更新されるフローテーブルと、該フローテーブルに登録されたフローから高レートフローを特定する高レートフロー特定装置と、該高レートフロー特定装置により高レートフローが特定されると、該フローが入力される高レートフローリストとを具備することを特徴とする高レートフロー特定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高レートフローを迅速に特定する高レートフロー特定方法およびその特定装置に関し、詳しくは、輻輳時に他のフローに与える影響が大きい高レートフローのパケットを選択的に廃棄する等の方法により、送出レート規制を図るための前処理として、パケットサンプリングによって得られた情報から、高レートフローを迅速に特定する方法および装置に関する。
【背景技術】
【０００２】
インターネットでは、ルータにおいて個々のフローを識別することなく、単一のキューによりＦＩＦＯでパケットを送出している。ネットワーク内部で個々のフローのスループットを制御する機能がなく、エンドホストのＴＣＰフロー制御機能に依存している。
しかし、ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）のフロー制御によって定まる平均パケット送出レートはＲＴＴ（Ｒｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ）に反比例し、ＲＴＴが小さいＴＣＰフローの占有スループットが大きくなる傾向がある。
【０００３】
さらに、ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）フローや悪意のあるユーザが生成するＴＣＰフロー制御機能に従わないフローといった非ＴＣＰフローは、輻輳によるパケット損失を検出してもエンドホストがパケット送出レートを下げないため、定常的に伝送資源の大きな部分を占有する可能性がある。個々のフローの占有帯域はアクセス回線帯域が上限となるが、近年、ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）やＦＴＴＨ（Ｆｉｂｅｒ−ｔｏ−ｔｈｅ−Ｈｏｍｅ）といった高速なアクセス回線の普及が急速に進んでいるため、高レートフローの占有帯域を益々増大させる。上位１０％の高レートフローが、総転送データ量の３０％〜９０％を占めているという報告もあり、これらの高レートフローの他のフローに与える影響は極めて大である。
【０００４】
このような，インターネットにおけるフロー間のスループットの不公平性を解決する方法として、Ｆａｉｒ  ｑｕｅｕｅｉｎｇに代表される，フロー単位にキューを管理しスケジューリングすることにより各フローのスループットをネットワーク内部で制御する方式が数多く検討されている。しかし、全てのフロー状態をルータにおいて管理する必要があるため、スケーラビリティに問題が生じる。
【０００５】
一方、全てのフロー状態を管理しないで、パケットを選択的に廃棄することによりフロー間の不公平性の是正を図るＡｃｔｉｖｅ  ｑｕｅｕｅ  ｍａｎａｇｅｍｅｎｔのアプローチが、やはり数多く検討されている。このアプローチでは、リンク輻輳時に、他のフローに対する影響度の大きい高レートフローを識別し、これらのフローに対して選択的に多くのパケットを廃棄することにより、フロー間の不公平性を是正しながら輻輳の緩和を図る。また、全てのフローに対するフロー状態の管理が不要であるため、実装も比較的容易である。
【０００６】
しかし、高レートフローの特定に時間を要する場合、リンク輻輳を検出してから実際に高レートフローに対するレート規制が図られるまでのタイムラグが大きくなり、フロー間の不公平性が大きく、輻輳状態となっている時間が長くなる。また、特定精度が低い場合、高レートフローを誤って見逃す確率や低レートフローを誤ってレート規制対象となる確率が増大し、運用上好ましくない。従って、迅速かつ高精度で高レートフローを特定できることが重要である。
【０００７】
ところで、フローサイズやフロー時間といったフローの各種統計値を収集するための技術として、パケット流からパケットを一定周期もしくはランダムに抜き出すパケットサンプリングが注目されている。リンクの回線容量が２．５Ｇｂｐｓや１０Ｇｂｐｓと高速化するに伴い、回線レートで全てのパケットを判読して統計処理を行うことが困難となる。
また、ネットワークの規模が増大するに伴い、全てのフロー状態を管理することが困難となる。従って、パケットサンプリングにより一部のフロー状態のみを管理し、各種フロー統計値を得ることは、実用上でも非常に有用である。そこで、高レートフローを特定する際にも、パケットサンプリングにより得られた情報から特定できることが重要である。
以上の背景技術については、下記非特許文献１〜３を参照されたい。
【０００８】
【非特許文献１】Ｓ．Ｆｌｏｉｄ  ａｎｄ  Ｋ．Ｆａｌｌ，“Ｐｒｏｍｏｔｉｎｇ  ｔｈｅ  Ｕｓｅ  ｏｆ  Ｅｎｄ−ｔｏ−Ｅｎｄ  Ｃｏｎｇｅｓｔｉｏｎ  Ｃｏｎｔｒｏｌ  ｉｎ  ｔｈｅ  Ｉｎｔｅｒｎｅｔ，”ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，Ｖｏｌ．７（４），ｐｐ．４５８−４７３，Ａｕｇｕｓｔ  １９９９．
【非特許文献２】Ａ．Ｄｅｍｅｒｓ，Ｓ．Ｋｅｓｈａｖ，ａｎｄ  Ｓ．Ｓｈｅｎｋｅｒ，“Ａｎａｌｙｓｉｓ  ａｎｄ  ｓｉｍｕｌａｔｉｏｎ  ｏｆ  ａ  ｆａｉｒ  ｑｕｅｕｅｉｎｇ  ａｌｇｏｒｉｔｈｍ，”ＳＩＧＣＯＭＭ’８９，１９（４），ｐｐ．１−１２，Ｓｅｐｔｅｍｂｅｒ  １９８９．
【非特許文献３】Ｃ．Ｅｓｔａｎ  ａｎｄ  Ｇ．Ｖａｒｇｈｅｓｅ，“Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｔｒａｆｆｉｃ  Ｍｅａｓｕｒｅｍｅｎｔ  ａｎｄ  Ａｃｃｏｕｎｔｉｎｇ，”ＳＩＧＣＯＭＭ’０２，ｐｐ．３２３−３３６．
【非特許文献４】Ｗ．Ｆｅｎｇ，Ｋ．Ｇ．Ｓｈｉｎ，Ｄ．Ｄ．Ｋａｎｄｌｕｒ，ａｎｄ  Ｄ．Ｓａｈａ，“Ｔｈｅ  ＢＬＵＥ  Ａｃｔｉｖｅ  Ｑｕｅｕｅ  Ｍａｎａｇｅｍｅｎｔ  Ａｌｇｏｒｉｔｈｍｓ，”ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，Ｖｏｌ．１０（４），ｐｐ．５１３−５２８，Ａｕｇｕｓｔ  ２００２．
【非特許文献５】Ｒ．Ｍａｈａｊａｎ，Ｓ．Ｆｌｏｉｄ，ａｎｄ  Ｄ．Ｗｅｔｈｅｒａｌｌ，“Ｃｏｎｔｒｏｌｌｉｎｇ  Ｈｉｇｈ−Ｂａｎｄｗｉｄｔｈ  Ｆｌｏｗｓ  ａｔ  ｔｈｅ  Ｃｏｎｇｅｓｔｅｄ  Ｒｏｕｔｅｒ，”ＩＣＮＰ  ２００１．
【非特許文献６】Ｔ．Ｍｏｒｉ，Ｍ．Ｕｃｈｉｄａ，Ｒ．Ｋａｗａｈａｒａ，Ｊ．Ｐａｎ，ａｎｄ  Ｓ．Ｇｏｔｏ，“Ｉｄｅｎｔｉｆｙｉｎｇ  Ｅｌｅｐｈａｎｔ  Ｆｌｏｗｓ  Ｔｈｒｏｕｇｈ  Ｐｅｒｉｏｄｉｃａｌｌｙ  Ｓａｍｐｌｅｄ  Ｐａｃｋｅｔｓ，”ＩＭＣ’０４．
【非特許文献７】Ｍ．Ｋｏｄｉａｌａｍ，Ｔ．Ｖ．Ｌａｋｓｈｍａｎ，Ｓ．Ｍｏｈａｎｔｙ，“Ｒｕｎｓ  ｂＡｓｅｄ  Ｔｒａｆｆｉｃ  Ｅｓｔｉｍａｔｏｒ（ＲＡＴＥ）：Ａ  Ｓｉｍｐｌｅ，Ｍｅｍｏｒｙ  Ｅｆｆｉｃｉｅｎｔ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｐｅｒ−Ｆｌｏｗ  Ｒａｔｅ  Ｅｓｔｉｍａｔｉｏｎ，”Ｉｎｆｏｃｏｍ’０４．
【非特許文献８】Ｎ．Ｋａｍｉｙａｍａ，“Ｉｄｅｎｔｉｆｙｉｎｇ  Ｈｉｇｈ−Ｒａｔｅ  Ｆｌｏｗｓ  ｗｉｔｈ  Ｌｅｓｓ  Ｍｅｍｏｒｙ，”Ｇｌｏｂａｌ  Ｉｎｔｅｒｎｅｔ  Ｓｙｍｐｏｓｉｕｍ  ２００５．
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来の高レートフロー特定方法では、フローレートに対する特定確率が定式化されておらず、特定されるフローレートの閾値の与え方が明らかでない。全てのパケットに対して特定のための処理を行う方法は、高速回線への適用が困難である。また、ＲＥＤ（Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ）の使用を前提とした方法は、特定閾値となるフローレートを明示的に与えることができるが、ＲＥＤの使用が前提であるため、ＲＥＤを用いないルータには適用できず、やはり任意のフローレートに対する特定確率が定式化されていないため、特定精度が明らかでない。
【００１０】
ところで、フローサイズとフローレートには正の強い相関があることが知られているため、大サイズフローの特定方式で高レートフロー特定の代用を図ることが考えられるが、一般に、フローサイズとフローレートとの関連を定式化することができないため、特定閾値となるフローレートを明示的に与えることができず、特定曲線も得られないため、特定精度も明らかでない。
また、パケットサンプリングにより高レートフローのフローレートを高精度に推定するアプローチもあるが、フローレートの推定を目的としているため、特定の閾値となるフローレートを与えたときの任意のフローレートに対する特定確率が定式化されておらず、やはり特定精度が明らかでない。
【００１１】
高レートフローの特定を行う際には、高レートと定義するフローレートの閾値ｆ＊とその特定確率Ｈ＊を設計できることが、実用上重要である。さらに、フローレートｆがｆ＜ｆ＊のフローが誤って特定される確率（ＦＰＲ：Ｆａｌｓｅ  Ｐｏｓｉｔｉｖｅ  Ｒａｔｉｏ）と、ｆ≧ｆ＊のフローが誤って特定されない確率（ＦＮＲ：Ｆａｌｓｅ  Ｎｅｇａｔｉｖｅ  Ｒａｔｉｏ）を明確にし、特定精度を明らかにすることが重要である。そのためには、図１に示すような，ｆ＊とＨ＊を与えたときの任意のｆに対する特定確率Ｈ（特定曲線）を明らかにする必要がある。
【００１２】
そこで、本発明者は、以前、サンプル情報から高精度で高レートフローを特定するＳｈｏｒｔ  ｔｉｍｅｏｕｔ法（ＳＴ法と表記）を提案した。パケットサンプルでは、フロー統計値を収集するためにフローテーブルが作成されるが、最後にサンプルされた時刻からタイムアウト時間Ｔ内に同一フローに属するパケットが新たにサンプルされなかった場合に、フローテーブルからフローのエントリを消去する。ＳＴ法では、Ｔを数〜数１０サンプル周期という短い時間に設定し、Ｔ内に２個のパケットがサンプルされたフローを高レートフローとして特定する。ＳＴ法の原理は非常に単純であり、実装が容易であること、また、所要メモリサイズが小さいという特徴がある。
【００１３】
また、与えられたパケット到着率と特定のための許容時間とから、任意のレートのフローが特定される確率を解析的に導出して特定曲線を明確化し、任意の特定曲線を与えるパラメータ設計方法を与えることができる。しかし、特定の判断基準を２個のパケットがサンプルされたか否かとしているため、単に一つ以上のパケットがサンプルされたフローを特定する場合（Ｎａｉｖｅ  ｓａｍｐｌｉｎｇ法（ＮＳ法と表記））と比較して、ＦＮＲの改善度合いが小さい。
【００１４】
（目的）
本発明の目的は、上記ＳＴ法を改良し、Ｙ個のパケットがタイムアウトしないでサンプルされたフローを特定する方法を考え、特定精度の向上を図ることが可能な高特定精度による高レートフロー特定方法および特定装置を提供することにある。
【課題を解決するための手段】
【００１５】
前記目的を達成するため、本発明の高レートフロー特定方法は、１）パケットサンプリングによって得られた情報を用いるトラヒック計測方法において、計測期間内に高レートフローを特定する方法を与える。
また、２）上記１）の方法において、与えられた計測期間内に、タイムアウトすることなくＹ個のパケットがサンプリングされたフローを高レートフローとして特定することを特徴としている。
【００１６】
また、３）上記２）の方法において、パケット到着率と計測期間長が与えられ、識別個数Ｙとタイムアウトの長さとサンプリング周期を定めたときに、任意のフローレートのフローの特定確率を導出することを特徴としている。
また、４）上記２）と３）に記載の方法において、与えられた特定フローレートの閾値とその特定確率を満足する特定曲線を実現する，タイムアウト時間とサンプリング周期の組を導出することを特徴としている。
また、５）上記２）〜４）に記載の方法において、タイムアウト時間とサンプリング周期の選択可能な複数の組から、ネットワーク運用者の任意のポリシィに従って適用する組を選択することを特徴としている。
【００１７】
前記目的を達成するため、本発明の高レートフロー特定装置は、任意の特定曲線を実現するタイムアウト時間とサンプリング周期を設計するためのパラメータ設計装置と、設計されたタイムアウト時間によりフロー情報の消去を行うフロー情報消去装置と、設計されたサンプリング周期によりパケットのサンプリングを行うパケットサンプリング装置と、測定期間中に該パケットサンプリング装置により着目リンクを流れるパケットが一定周期でサンプリングされ、その情報に基づいて更新されるフローテーブルと、該フローテーブルに登録されたフローから高レートフローを特定する高レートフロー特定装置と、該高レートフロー特定装置により高レートフローが特定されると、該フローが入力される高レートフローリストとを具備することを特徴としている。
【発明の効果】
【００１８】
本発明によれば、与えられたパケット到着率と計測時間とから、所望の特定レート閾値とその特定確率を満足する特定曲線を与えるパラメータ設計を行いながら、パケットサンプリングにより簡易な方法でメモリサイズを抑えるとともに、高レートフローを高精度で特定することができる、という効果を奏する。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の原理および実施例を、図面を用いて詳細に説明する。
（装置の構成）
図２は、本発明の実施例に係る高レートフロー特定装置の構成図である。
図２において、１０１はパラメータ設計装置、１０２はパケットサンプリング装置、１０３はフロー情報消去装置、１０４はフローテーブル、１０５は高レートフロー特定装置、１０６は高レートフローリストである。メモリに内蔵されたフローテーブル１０４と高レートフローリスト１０６以外の装置は、いずれもＣＰＵ、メモリ等を内蔵したコンピュータで構成され、プログラムを実行することによりそれぞれの機能を逐行する。
【００２０】
パラメータ設計装置１０１により、任意の特定曲線を実現するタイムアウト時間とサンプリング周期が設計され、パケットサンプリング装置１０２とフロー情報消去装置１０３が設定される。パラメータ設計装置１０１は、予め入力された特定曲線に基づいて自動的にタイムアウト時間とサンプリング周期が設計される。設計されたタイムアウト時間はフロー情報消去装置１０３に出力され、サンプリング周期はパケットサンプリング装置１０２に出力される。
【００２１】
測定期間中は、パケットサンプリング装置１０２により着目リンクを流れるパケットが一定周期でサンプリングされ、その情報に基づいてフローテーブル１０４が更新される。
一方、フロー情報消去装置１０３は、入力されたタイムアウト時間が経過したフロー情報をフローテーブル１０４より消去する。
高レートフロー特定装置１０５は、フローテーブル１０４のメモリにアクセスして、フローテーブル１０４に登録されたフローから高レートフローを特定し、高レートフローリスト１０６に出力する。高レートフローリスト１０６は、高レートフロー特定装置１０５に特定されたフローが入力されると、それらをリストに書き込み、メモリに記憶する。
【００２２】
次に、本発明の実施例に係るサンプリング情報を用いた高レートフロー特定方法について、１）動作原理、２）特定確率の導出、についてそれぞれ説明する。
（動作原理）
まず、フローを、発着ＩＰアドレス、発着ポート番号、プロトコルタイプが共通のパケットの集合と定義する。そして、長さがφ（ｓ）の任意の測定期間Φを定め、各フローに対して、Φ内に到着したパケット数をｕとするとき、フローレートｆをｆ≡ｕ／φ（ｐｐｓ）と定義する。任意に定めた閾値ｆ＊に対して、ｆ≧ｆ＊のフローを高レートフローと定義し、着目リンクにおいて、高レートフローをΦ内で特定することを考える。
【００２３】
測定期間Φの時間長をφ（ｓ）とし、着目リンクのパケット到着率∧（ｐｐｓ）はΦの間一定であるとする。そして、一定周期Ｎパケットごとに１個のパケットをサンプルする。このとき、平均サンプリング間隔はＮ／∧（ｓ）となる。平均的には高レートフローであるほどサンプルされる確率が高くなる。そのため、単純に１個以上のパケットがサンプルされたフローを全て高レートフローとして特定する方法が考えられる。以後、この方法をＮａｉｖｅ  ｓａｍｐｌｉｎｇ法（ＮＳ法と表記）と呼ぶ。この方法は、直感的で実現も容易であるが、特定の判断基準が大雑把であるため特定精度が低い。
【００２４】
パケットサンプリングを行うルータでは、最後にパケットがサンプルされてから、タイムアウト時間Ｔ内に新たにパケットがサンプルされなかった場合に、フローテーブルに保持されたフロー状態を消去する。通常のパケットサンプリングはフロー統計値の収集を目的としており、Ｔは通常、１５秒や３０秒といった大きな時間に設定される。しかし、パケットサンプルの目的を高レートフローの特定に限定した場合、必ずしもＴを大きく設定する必要はない。
【００２５】
高レートフローのパケットは短い間隔で到着することから、そのパケットがサンプルされる間隔は短くなる傾向にある。そこで、Ｔを数〜数１０サンプル周期という短い時間に設定し、タイムアウトしないでＹ個のパケットがサンプルされたフローを高レートフローとして特定することを提案する。すなわち、各々の連続するサンプル間隔がＴ以内でＹ個のパケットがサンプルされたフローを特定する。以後、パラメータＹによって規定される本発明をＳｈｏｒｔ  ｔｉｍｅｏｕｔ−Ｙ法（ＳＴ−Ｙ法と表記）と呼ぶ。
ここでは、タイムアウト時間Ｔを、Ｋを任意の整数をとるパラメータとしてＫサンプル周期（Ｔ＝ＫＮ／∧）で与える。ＳＴ−Ｙ法は、パラメータＫとＮを調整することにより、任意の特定曲線を実現する。
【００２６】
図３は、本発明の特定例を示す説明図である。
ここでは、Φ内に３本のフローから合計で１２個のパケットがサンプルされた場合を示している。Ｋ＝２，Ｙ＝４とすると、フロー３のみが特定される。フロー３からは、タイムアウトしないでＹ＋１個のパケットがサンプルされているため、Ｙ番目のパケットがサンプルされた時点で特定される。フロー２からもΦ内にフロー３と同数（５）のパケットがサンプルされているが、２番目と３番目のパケットがサンプルされる間でタイムアウトするため、フロー２は特定されない。
【００２７】
任意の時点で、フローテーブルにエントリされているフロー数をｎとすると、これらｎ本の全てのフローから１個以上のパケットが過去Ｔ以内にサンプルされたはずである（さもなければタイムアウトするためエントリが消去される）。そのためには少なくともｎ個のパケットサンプルが過去Ｔ内で必要であるが、Ｔ内にはＫ個のパケットがサンプルされるため、ｎ≦Ｋが成立する。すなわち、ＳＴ−Ｙ法では、最大でもＫ個のフローが同時にエントリされるだけであるため、必要メモリ量はＫで上限を抑えることができる。
【００２８】
（特定確率の導出）
以下では、Ｙ−Ｓｈｏｒｔ  ｔｉｍｅｏｕｔ法の特定確率を解析的に導出し、特定フローレート閾値ｆ＊とその特定確率Ｈ＊を実現するためのパラメータ設定法について説明する。
Φの間に到着する総パケット数をＬ，総サンプルパケット数をＤとすると、Ｌ＝∧φ、Ｄ＝Ｌ／Ｎとなる。ＤはＤ≧Ｙを満たす必要がある。フローレートｆのフローのΦ内におけるトラヒック比率ｐをｐ≡ｆ／∧と定義し、Φ中は着目フローから一定のレートｆでパケットが着目リンクに到着すると仮定する。多重フロー数が十分に多い場合、サンプルされるパケットは各々独立であり、サンプルされたパケットがトラヒック比率ｐのフローに属している確率はΦの間、常にｐとなる。ｆはｐに比例することから、ｆの代わりにｐに対する特定確率Ｈを導出する。また、特定の閾値をｆ＊で規定する代わりにｐ＊で規定し、与えられたＬから、トラヒック比率がｐ＊のフローを確率Ｈ＊で特定することを考える。
【００２９】
ｑＹ（ｐ，ｊ）を、区間Φにおいてトラヒック比率がｐの着目フローのパケットがｊ個サンプルされ、かつ着目フローが特定されない確率と定義する。そして、ｑＹ（ｐ，ｊ）＞０となるｊの最大値をＪと定義する。
図４は、ｊの最大値を実現するパケットサンプリングパターンの説明図である。
Ｔ以内にＹ個以上のパケットがサンプルされると着目フローは特定されるため、図４に示すように、着目フローのパケットがＹ−１個連続してサンプルされる（図４中、黒丸）期間と、着目フロー以外のパケットがＫ個連続してサンプルされる（図４中、白丸）期間が交互に現われる場合に、着目フローが特定されないという条件でｊが最大となる（図４は、Ｙ＝３，Ｋ＝２の場合）。よって、Ｊは次式（１）となる。
【００３０】
【数１】
2007005994.tif 000003
このとき、トラヒック比率がｐのフローの特定確率ＨＹ（ｐ）は、次式（２）で与えられる。
【００３１】
【数２】
2007005994.tif 000004
以下では、０≦ｊ≦Ｊの各ｊに対するｑＹ（ｐ，ｊ）を導出する。
まず、０≦ｊ≦Ｙ−１のときは、着目フローは必ず特定されない。一方で、Ｄ個のサンプルにおいて着目フローのパケットがｊ個サンプルされる確率は二項分布に従うことから、ｑＹ（ｐ，ｊ）は次式（３）で得られる。
【００３２】
【数３】
2007005994.tif 000005
しかし、Ｙ≦ｊ≦Ｊのときは、着目フローのパケットがサンプルされる位置によって着目フローが特定される場合とされない場合があるため、ｑＹ（ｐ，ｊ）はこのような簡易な式で求めることはできない。Ｙ≦ｊ≦ＪにおけるｑＹ（ｐ，ｊ）を導出するため、Ａ（ｄ），ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ），αＹ（ｊ，ｗ）を以下のように定義する。
【００３３】
区間Ａ（ｄ）はΦ内の任意の連続するｄ個のサンプルが行われる区間であり、ｄ＝Ｄのとき、Ａ（ｄ）＝Φとなる。ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）は、区間Ａ（ｄ）において着目フローのパケットがｊ個サンプルされ、かつ、最後（ｊ番目）のサンプル位置が区間Ａ（ｄ）の最後のサンプル位置から遡ることｖ番目のサンプル位置であり、区間Ａ（ｄ）の終了時点でフローテーブル内の着目フローのエントリのカウンタ値がｗであり（タイムアウトしないでｗ個サンプルされている）、かつ、着目フローがこの間、特定されない確率である。
【００３４】
また、予えられたｊとｗに対して、ｒＹ（ｐ，ｄ，ｊ，１，ｗ）＞０となるｄの最小値をαＹ（ｊ，ｗ）と定義する（ｄの最小値はｊとｗに依存するためαＹはｊとｗの関数となる）。
図５は、ｄの最小値を実現するパケットサンプリングパターンの説明図である。
ここでは、ｄの最小値αＹ（ｊ，ｗ）を与えるパケットサンプルパターンを示す（図５では、Ｙ＝３，Ｋ＝３，ｊ＝５，ｗ＝１の場合）。
ｄが最小となるのは、Ａ（ｄ）の末尾から連続してｗ個のサンプル位置で着目フローのパケットがサンプルされ、残るｊ−ｗ個の着目フローのパケットがＫのブランクを挟んでＹ−１個以下のクラスタを形成する場合であるため、αＹ（ｊ，ｗ）の値は次式（４）となる。
【００３５】
【数４】
2007005994.tif 000006
ｑＹ（ｐ，ｊ）は、ｒＹ（ｐ，Ｄ，ｊ，ｖ，ｗ）を全てのｖとｗについて足し合わせることにより導出できる。ｗ≧Ｙのとき、着目フローはＡ（ｄ）内で特定されるため、０≦ｗ≦Ｙ−１のｗについてのみ考えればよい。
【００３６】
次に、ｖの範囲について考える。
図６は、区間分割の例を示す説明図である。
図６に示すように、区間Ａ（ｄ）を、先頭から着目フローのｊ−１番目のサンプル位置までの区間Ａ１（ｄ１）と、残る区間Ａ２（ｄ２）に分割して考える。ただし、区間Ａ１（ｄ１）とＡ２（ｄ２）内のサンプルパケット数を各々、ｄ１とｄ２とする（ｄ１＋ｄ２＝ｄ）。区間Ａ１（ｄ１）の終了時点における着目フローのカウンタ値をｗ１とすると、ｄ１＜αＹ（ｊ−１，ｗ１）であるとき着目フローは区間Ａ１（ｄ１）内で必ず特定される。前式（４）より、ｗ１＝Ｙ−２のときαＹ（ｊ−１，ｗ１）は最小値をとるため、ｖ＞ｄ−αＹ（ｊ−１，Ｙ−２）のときｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）＝０となる。よって、１≦ｖ≦ｄ−αＹ（ｊ−１，Ｙ−２）のｖについてのみ考えればよい。さらに、１≦ｖ≦Ｋのとき、区間Ａ（ｄ）の終了時点で着目フローはタイムアウトしていないため、ｒＹ（ｐ，ｄ，ｊ，ｖ，０）＝０となる。
【００３７】
また、Ｋ＋１≦ｖ≦ｄ−αＹ（ｊ−１，Ｙ−２）のとき、区間Ａ（ｄ）の終了時点で着目フローはタイムアウトしているため、１≦ｗ≦Ｙ−１に対してｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）＝０となる。よって、Ｙ≦ｊ≦Ｊのｊに対してｑＹ（ｐ，ｊ）が次式（５）で求まる。
【００３８】
【数５】
2007005994.tif 000007
【００３９】
次に、ｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）を導出する。
ｊ＝１の場合
区間Ａ（ｄ）内で着目フローはサンプル位置に関係なく特定されないため、ｖのとり得る最大値はｄとなる。また、ｊ＝１のとき、ｗは０≦ｗ≦１の範囲の値をとる。区間Ａ（ｄ）において、末尾からｖのサンプル位置に唯一つ着目フローのパケットがサンプルされる確率は（１−ｐ）ｄ−１ｐで与えられることから、ｒＹ（ｐ，ｄ，１，ｖ，ｗ）は次式（６）のようになる。
【００４０】
【数６】
2007005994.tif 000008
【００４１】
２≦ｊ≦Ｙ−１の場合
やはり、区間Ａ（ｄ）内で着目フローはサンプル位置に関係なく特定されないため、１≦ｖ≦ｄ−ｊ＋１であり、０≦ｗ≦ｊである。区間Ａ１（ｄ１）において着目フローが特定されず、区間Ａ１（ｄ１）の終了時点で着目フローのカウンタ値がｗ１である確率はｒＹ（ｐ，ｄ１，ｊ−１，１，ｗ１）で与えられる。以下、ｗの値に応じて考える。
まず、ｗ＝０のときについて考える。Ａ（ｄ）の終了時点でタイムアウトしている必要があることから、１≦ｖ≦ＫのときはｒＹ（ｐ，ｄ，ｊ，ｖ，０）＝０となる。区間Ａ１（ｄ１）の定義より、区間Ａ１（ｄ１）の最終サンプル位置で着目フローのパケットがサンプルされるため、ｗ１は１≦ｗ１≦ｊ−１を満たす。よって、Ｋ＋１≦ｖ≦ｄ−ｊ＋１に対して次式（７）が得られる。
【００４２】
【数７】
2007005994.tif 000009
【００４３】
次に、ｗ＝１のときについて考える。区間Ａ（ｄ）の終了時点でタイムアウトしてはならないため、Ｋ＋１≦ｖ≦ｄ−ｊ＋１に対してｒＹ（ｐ，ｄ，ｊ，ｖ，１）＝０となる。
ここで、ｔｊを着目フローの区間Ａ（ｄ）におけるｊ番目のサンプル時刻とする。ｔｊ−１とｔｊの間でタイムアウトする必要があることから、１≦ｖ≦Ｋに対して次式（８）が得られる。
【００４４】
【数８】
2007005994.tif 000010
【００４５】
最後に、２≦ｗ≦ｊの場合について考える。
やはり、区間Ａ（ｄ）の終了時点でタイムアウトしてはならないため、Ｋ＋１≦ｖ≦ｄ−ｊ＋１に対してｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）＝０となる。さらに、ｔｊ−１とｔｊの間でもタイムアウトしてはならないため、１≦ｖ≦Ｋに対して、次式（９）となる。
【００４６】
【数９】
2007005994.tif 000011
なお、Ｋ＋１≦ｖ≦ｄ−ｊ＋１に対してはｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）＝０である。
【００４７】
Ｙ≦ｊ≦Ｊの場合
やはり、ｗの値に応じて考える。まず、ｗ＝０の場合、区間Ａ（ｄ）の終了時点でやはりタイムアウトしている必要があることから、１≦ｖ≦ＫのときはｒＹ（ｐ，ｄ，ｊ，ｖ，０）＝０となる。ｗ１は１≦ｗ１≦Ｙ−１の範囲の値をとるが、１≦ｗ１≦Ｙ−２のとき、ｔｊ−１とｔｊの間でタイムアウトしてもしなくてもよく、ｄ１はαＹ（ｊ−１，ｗ１）≦ｄ１≦ｄ−ｖの範囲の値を取り得る。ｗ１＝Ｙ−１のときは、ｔｊ−１とｔｊの間でタイムアウトする必要があるため（さもなければ着目フローは特定される）、ｄ１はαＹ（ｊ−１，Ｙ−１）≦ｄ１≦ｄ−ｖ−Ｋの範囲の値を取り得る。よって、Ｋ＋１≦ｖ≦αＹ（ｊ−１，Ｙ−２）に対して次式（１０）が得られる。
【００４８】
【数１０】
2007005994.tif 000012
ｗ＝１の場合、ｗ１は１≦ｗ１≦Ｙ−１の範囲の値を取り得、ｔｊ−１とｔｊの間でタイムアウトする必要があることから、１≦ｖ≦Ｋに対して、次式（１１）を得る。
【００４９】
【数１１】
2007005994.tif 000013
なお、Ｋ＋１≦ｖ≦αＹ（ｊ−１，Ｙ−２）に対してはｒＹ（ｐ，ｄ，ｊ，ｖ，１）＝０となる。
【００５０】
最後に、２≦ｗ≦Ｙ−１の場合について考える。
このとき、ｗ１＝ｗ−１であり、ｔｊ−１とｔｊの間でタイムアウトしてはならないため、１≦ｖ≦Ｋに対して、次式（１２）となる。
【００５１】
【数１２】
2007005994.tif 000014
なお、Ｋ＋１≦ｖ≦αＹ（ｊ−１，Ｙ−２）に対してはｒＹ（ｐ，ｄ，ｊ，ｖ，ｗ）＝０となる。
【００５２】
以下に、測定期間Φ内でトラヒック比率ｐのフローが特定される確率ＨＹ（ｐ）の導出手順をまとめる。
（Ｉ）前式（３）より、０≦ｊ≦Ｙ−１に対してｑＹ（ｐ，ｊ）を算出する。
（II）前式（６）より、１≦ｄ≦Ｄ−１の各ｄに対してｒＹ（ｐ，ｄ，１，１，１）を算出する（ｒＹ（ｐ，ｄ，２，１，ｗ）の算出に必要）。
（III）以下の手順を２≦ｊ≦Ｙ−１の各ｊに対してｊの昇順に反復する。
（III−１）前式（８），（９）より、ｗ＝１，αＹ（ｊ，１）≦ｄ≦Ｄ−Ｋ−１の各ｄと、２≦ｗ≦ｊ，αＹ（ｊ，ｗ）≦ｄ≦Ｄ−１の各ｗ，ｄに対してｒＹ（ｐ，ｄ，ｊ，１，ｗ）を算出する（ｒＹ（ｐ，ｄ，ｊ＋１，１，ｗ）の算出に必要）。
【００５３】
（IV）以下の手順をＹ≦ｊ≦Ｊの各ｊに対してｊの昇順に反復する。
（IV−１）前式（１１），（１２）より、１≦ｗ≦Ｙ−１，１≦ｖ≦Ｋの各ｗ，ｖに対してｒＹ（ｐ，Ｄ，ｊ，ｖ，ｗ）を算出し、前式（１０）より、Ｋ＋１≦ｖ≦Ｄ−αＹ（ｊ−１，Ｙ−２）の各ｖに対してｒＹ（ｐ，Ｄ，ｊ，ｖ，０）を算出する（ｑ（ｐ，ｊ）の算出に必要）。
（IV−２）前式（５）よりｑＹ（ｐ，ｊ）を算出する。
（IV−３）前式（１１），（１２）より、１≦ｗ≦Ｙ−１，αＹ（ｊ，ｗ）≦ｄ≦βＹの各ｗ，ｄに対してｒＹ（ｐ，ｄ，ｊ，１，ｗ）を算出する（ｒＹ（ｐ，ｄ，ｊ＋１，ｖ，ｗ）の算出に必要，ただしｊ＝Ｊのときは不要であり、Ｙ＝２のときβＹ＝Ｄ−Ｋ−１で、Ｙ≧３のときβＹ＝Ｄ−１）。
（Ｖ）前式（２）よりＨ（ｐ）を算出する。
【００５４】
ところで、手順（III）と（Ｖ）の計算にはＯ（ＹＤ３）の計算量が必要であるため、Ｄの増加に伴いＨＹ（ｐ）の計算に要する時間が急増する。しかし、前式（８）〜（１２）を、２ｊＹ−１のｊに対して漸化式（１３），（１４）に変形し、
【００５５】
【数１３】
2007005994.tif 000015
【００５６】
【数１４】
2007005994.tif 000016
に、Ｙ≦ｊ≦Ｊのｊに対して漸化式（１５）〜（１９）に変形し、
【００５７】
【数１５】
2007005994.tif 000017
【００５８】
【数１６】
2007005994.tif 000018
【００５９】
【数１７】
2007005994.tif 000019
【００６０】
【数１８】
2007005994.tif 000020
【００６１】
【数１９】
2007005994.tif 000021
これにより、計算量をＯ（ＹＤ２）に抑えることが可能である。
【００６２】
（数値評価）
次に、本発明の数値評価結果について説明する。
以下の説明では、具体的な数値を用いて特定曲線を示し、ＳＴ−Ｙ法の基本特性を明らかにする。提案方法の特性は、特定判断値Ｙ、タイムアウト係数Ｋ、そしてサンプリング周期Ｎによって決まるが、Ｎ＝Ｌ／Ｄであるため、Ｙ，Ｋと総サンプリング数Ｄの値に対して各種検討を行う。
【００６３】
設計パラメータＫとＤに関する評価
図７は、いくつかのＹに対する特定曲線を示す図である。
ここでは、Ｋ＝１０，Ｄ＝１０００としたときの，トラヒック比率ｐに対する特定確率Ｈ（ｐ）をいくつかのＹ（Ｙ＝２，４，８）に対して示している。特定曲線は、ｐの増加に対して単調に増加する曲線となるが、Ｙが大きな場合ほど特定曲線は急勾配となる。
【００６４】
図８は、ＫとＤの関係を表す特性図である。
ここでは、ｐ＊＝０．１、Ｈ＊＝０．５とし、Ｙを２，３，４，５にした場合について、タイムアウト係数Ｋと総サンプリング数Ｄの取り得る可能な組合せを各々示す。ある（ｐ＊，Ｈ＊）を実現する可能なＫとＤの組合せは複数存在し、Ｋが増加するほど対応するＤの値は減少する。ただし、Ｙが増加するほど、同一の（ｐ＊，Ｈ＊）を実現するのに必要なサンプルパケット数は増大することから、ＫとＤは共に増加する。
【００６５】
特定曲線と特定精度
図９は、（ｐ＊，Ｈ＊）＝（０．０１，０．５）を実現する特定曲線を示す図である。
ここでは、ｐ＊＝０．０１、Ｈ＊＝０．５としたときのＮＳ法とＳＴ−Ｙ法の特定曲線を各々示している。Ｄの取り得る最小値をＤｍｉｎ，Ｋの取り得る最大値をＫｍａｘとすると、
Ｄｍｉｎ＝Ｋｍａｘ＋１の関係が成立する。図９では、Ｋ＝Ｋｍａｘとし、Ｙのいくつかの値について示している。全ての特定曲線は点（ｐ＊，Ｈ＊）＝（０．０１，０．５）を通るが、ＳＴ−Ｙ法の特定曲線はＮＳ法と比較してｐ＝ｐ＊付近の傾きが急勾配であり、特定閾値における切り分けがシャープであり、特定精度が向上する。
【００６６】
また、Ｙの値が大きなほど特定曲線は急勾配となることから、特定精度が向上する。タイムアウトしないで低フローレートのフローからＹ個のパケットがサンプルされる確率はＹが大きなほど小さくなるため、ＳＴ−Ｙ法の高レートフロー判別能力はＹが大きなほど増加する。ただし、図８に示すように、Ｙが増加するほど同一のＫに対応するＤの値は増加するため、サンプリング間隔Ｎが減少する。
【００６７】
コンピュータ制御の描画装置により、与えられた特定フローレートの閾値と、該特定フローレートの閾値の特定確率を満足する特定曲線を描き、該特定曲線を実現するタイムアウト時間とサンプリング周期の選択可能な複数の組から、ネットワークの運用方針に基づいて適用する組を選択する
【００６８】
図１０は、計測時間に対するサンプリング間隔の特性図である。
ここでは、測定間隔φに対するＮをＮＳ法とＳＴ−Ｙ法について示している。ただし、Ｎ＝Ｌ／Ｄ＝ρＣφ／Ｄであるが（ρはリンク使用率で、Ｃ（ｐａｃｋｅｔｓ／ｓ）はリンク伝送容量）、ここではＣ＝１０Ｇｂｐｓ，ρ＝０．９とした。全てのφの領域において、ＳＴ−Ｙ法のＮはＮＳ法と比較して小さく、またＹが増加するほどＮは大きく減少することが確認できる。そのため、特定精度と特定処理負荷の間には、トレードオフの関係が成立する。
【図面の簡単な説明】
【００６９】
【図１】特定曲線の例を示す図である。
【図２】本発明の一実施例に係る高レートフロー特定装置の構成図である。
【図３】本発明の高レートフローの特定例を示す説明図である。
【図４】ｊの最大値を実現するパケットサンプリングパターンを示す図である。
【図５】ｄの最小値を実現するパケットサンプリングパターンを示す図である。
【図６】区分分割の例を示す説明図である。
【図７】いくつかのＹに対する特定曲線を示す図である。
【図８】ＫとＤの関係を表す特性図である。
【図９】（ｐ＊，Ｈ＊）＝（０．０１，０．５）を実現する特定曲線を示す図である。
【図１０】計測時間に対するサンプリング間隔の特性図である。
【符号の説明】
【００７０】
１０１：パラメータ設計装置
１０２：パケットサンプリング装置
１０３：フロー情報消去装置
１０４：フローテーブル
１０５：高レートフロー特定装置
１０６：高レートフローリスト
【図１】
2007005994.tif 000024
【図２】
2007005994.tif 000025
【図３】
2007005994.tif 000026
【図４】
2007005994.tif 000027
【図５】
2007005994.tif 000028
【図６】
2007005994.tif 000029
【図７】
2007005994.tif 000030
【図８】
2007005994.tif 000031
【図９】
2007005994.tif 000032
【図１０】
2007005994.tif 000033