(57)【要約】      （修正有）【課題】パケットサンプリングによって得られた情報から高レートフローを特定化する簡易な方法を与えること、より具体的には、与えられたパケット到着率と特定化のための許容時間とから、任意のレートのフローが特定化される確率を解析的に導出して特定化曲線を明確に、特定化に許容できる時間の上限値を満足しながら、任意の特定化曲線を与えるパラメータ設計方法を与えること。【解決手段】パケットサンプリングによって得られた情報を用いるトラヒック計測方法であって、与えられた許容時間内に高レートフローを特定化するステップを具備し、この高レートフローを特定化するステップとして、与えられた計測期間内に一つ以上のパケットがサンプリングされたフローを高レートフローとして特定化するステップを用いることを特徴とする高レートフロー特定化方法並びにこれを具体化したシステム。【選択図】図２
2006196982.tif 000002
【特許請求の範囲】
【請求項１】
パケットサンプリングによって得られた情報を用いるトラヒック計測結果に基づいて、許容時間内に高レートフローを特定化するステップを具備し、
前記高レートフローを特定化するステップとして、与えられた計測期間内に一つ以上のパケットがサンプリングされたフローを高レートフローとして特定化するステップを用いることを特徴とする高レートフロー特定化方法。
【請求項２】
前記高レートフローを特定化するステップにおいて、
パケット到着率と計測期間長が与えられたときに、任意のフローレートのフローの特定化確率を導出することを特徴とする請求項１に記載の高レートフロー特定化方法。
【請求項３】
前記高レートフローを特定化するステップにおいて、
与えられた特定化フローレートの閾値とその特定化確率を満足する特定化曲線を実現するようサンプリング周期を設計することを特徴とする請求項１または２に記載の高レートフロー特定化方法。
【請求項４】
パケットサンプリングによって得られた情報を用いるトラヒック計測結果に基づいて、許容時間内に高レートフローを特定化するステップを具備し、
前記高レートフローを特定化するステップにおいて、
与えられた計測期間内に、タイムアウト時間以内に二個以上のパケットがサンプリングされたフローを高レートフローとして特定化することを特徴とする高レートフロー特定化方法。
【請求項５】
前記高レートフローを特定化するステップにおいて、
パケット到着率と計測期間長が与えられ、タイムアウトの長さとサンプリング周期を定めたときに、任意のフローレートのフローの特定化確率を導出することを特徴とする請求項４に記載の高レートフロー特定化方法。
【請求項６】
前記高レートフローを特定化するステップにおいて、
与えられた特定化フローレートの閾値とその特定化確率を満足する特定化曲線を実現する、タイムアウト時間とサンプリング周期の組を導出することを特徴とする請求項４または５に記載の高レートフロー特定化方法。
【請求項７】
前記高レートフローを特定化するステップにおいて、
タイムアウト時間とサンプリング周期の選択可能な複数の組から、ネットワーク運用者の任意のポリシィに従って適用する組を選択することを特徴とする請求項４〜６のいずれかに記載の高レートフロー特定化方法。
【請求項８】
前記高レートフローを特定化するステップにおいて、
パケット到着率と計測期間長が与えられ、タイムアウトの長さとサンプリング周期を定めたときに、任意のフローサイズを持つ任意のフローレートの特定化確率を導出することを特徴とする請求項４に記載の高レートフロー特定化方法。
【請求項９】
前記高レートフローを特定化するステップにおいて、
着目するリンクの使用率が予め定めた値に達したときに、同じく予め定めた許容時間以内に、高レートフローを特定化することを特徴とする請求項１または４に記載の高レートフロー特定化方法。
【請求項１０】
パケットサンプリングによって得られた情報を用いるトラヒック計測結果に基づいて、許容時間内に高レートフローを特定化する高レートフロー特定化システムであって、
任意の特定化曲線を実現するタイムアウト時間とサンプリング周期を設計するパラメータ設計手段と、
測定期間中に、前記パケットサンプリング手段により着目リンクを流れるパケットをサンプリングするパケットサンプリング手段と、
前記パケットサンプリング手段によるパケットサンプリング情報並びに前記タイムアウト時間の経過したフロー情報に基づいてフロー情報を記録・管理するフローテーブルと、
この与えられた許容時間内に高レートフローを特定化するステップを具備し、
前記フローテーブルに登録されたフローから高レートフローを特定化する高レートフロー特定化手段と
を有することを特徴とする高レートフロー特定化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は高レートフロー特定化方法並びに高レートフロー特定化システムに関し、より詳細には、輻輳時に他のフローに与える影響が大きい高レートフローのパケットを選択的に廃棄するなどの方法により送出レート規制を図るための前処理として、パケットサンプリングによって得られた情報から高レートフローを迅速に特定化するに有効な、サンプリング情報を用いた高レートフロー特定化方法並びにこの方法を適用した高レートフロー特定化システムに関するものである。
【背景技術】
【０００２】
インターネットでは、ルータにおいて個々のフローを識別することなく、単一のキューによりＦＩＦＯでパケットが送出される。ネットワーク内部で個々のフローのスループットを制御する機能がなく、エンドホストのＴＣＰフロー制御機能に依存している。
しかし、ＴＣＰのフロー制御によって定まる平均パケット送出レートはＲＴＴ（Round Trip Time ）に反比例し、ＲＴＴが小さいＴＣＰフローの占有スループットが大きくなる傾向がある。
【０００３】
さらに、ＵＤＰフローや、悪意のあるユーザが生成するＴＣＰフロー制御機能に従わないフローといった非ＴＣＰフローは、輻輳によるパケット損失を検出してもエンドホストがパケット送出レートを下げないため、定常的に伝送資源の大きな部分を占有する可能性がある。
個々のフローの占有帯域はアクセス回線帯域が上限となるが、近年、ＡＤＳＬやＦＴＴＨといった高速なアクセス回線の普及が急速に進んでいるため、高レートフローの占有帯域をますます増大させる。上位１０％の高レートフローが、総転送データ量の３０％〜９０％を占めているという報告もあり、これら高レートフローの他のフローに与える影響は大きい。
【０００４】
このような、インターネットにおけるフロー間のスループットの不公平性を解決する方法として、Fair queueing に代表される、フロー単位にキューを管理しスケジューリングすることにより各フローのスループットをネットワーク内部で制御する方式が数多く検討されている。しかし、全てのフロー状態をルータにおいて管理する必要があるため、スケーラビリティに問題がある。
【０００５】
一方、全てのフロー状態を管理しないで、パケットを選択的に廃棄することによりフロー間の不公平性の是正を図るActive queue management のアプローチが、やはり数多く検討されている。本アプローチでは、リンク輻輳時に、他のフローに対する影響度の大きい高レートフローを識別し、これらフローに対して選択的に多くのパケットを廃棄することにより、フロー間の不公平性を是正しながら輻輳の緩和を図る。また、全てのフローに対するフロー状態の管理が不要であるため、実装も比較的容易である。
【０００６】
しかし、高レートフローの特定化に時間を要する場合、リンク輻輳を検出してから実際に高レートフローに対するレート規制が図られるまでのタイムラグが大きくなり、フロー間の不公平性が大きく、輻輳状態となっている時間が長くなる。また、特定化精度が低い場合、高レートフローを誤って見逃す確率や低レートフローを誤ってレート規制対象とする確率が増大し、運用上好ましくない。よって、迅速かつ高精度で高レートフローを特定化できることが重要である。
【０００７】
ところで、フローサイズやフロー時間といったフローの各種統計値を収集するための技術として、パケット流からパケットを一定周期もしくはランダムに抜き出すパケットサンプリングが注目されている。リンクの回線容量が２.５Ｇbpsや１０Ｇbpsと高速化するにつれ、回線レートで全てのパケットを判読して統計処理を行うことが困難になる。また、ネットワーク規模が増大するにつれ、全てのフロー状態を管理することが困難になる。
【０００８】
このため、パケットサンプリングにより一部のフロー状態のみを管理し、各種フロー統計値を得ることは実用上、非常に有用である。そこで、高レートフローを特定化する際にも、パケットサンプリングにより得られた情報から特定化できることが重要である。
上述の技術については、下記の非特許文献１〜３を参照されたい。
【０００９】
従来の高レートフロー特定化方法では、フローレートに対する特定化確率が定式化されておらず、特定化されるフローレートの閾値の与え方が明らかでない。全てのパケットに対して特定化のための処理を行う方法は、高速回線への適用が困難である。
【００１０】
また、ＲＥＤ（Random Early Detection ）の使用を前提とした方法は、特定化閾値となるフローレートを明示的に与えることができるが、ＲＥＤの使用が前提であるためＲＥＤを用いないルータには適用できず、やはり任意のフローレートに対する特定化確率が定式化されていないため、特定化精度が明らかでない。
【００１１】
ところで、フローサイズとフローレートには正の強い相関があることが知られているため、大サイズフローの特定化方式で高レートフロー特定化の代用を図ることが考えられるが、一般に、フローサイズとフローレートとの関連を定式化することができないため、特定化閾値となるフローレートを明示的に与えることができず、特定化曲線も得られないため、特定化精度も明らかでない。
【００１２】
また、パケットサンプリングにより高レートフローのフローレートを高精度に推定するアプローチもあるが、フローレートの推定を目的としているため、特定化の閾値となるフローレートを与えたときの任意のフローレートに対する特定化確率が定式化されておらず、やはり特定化精度が明らかでない。
【００１３】
高レートフローの特定化を行う際には、高レートと定義するフローレートの閾値f*とその特定化確率H*を設計できることが、実用上重要である。さらに、フローレートfがf＜f*のフローが誤って特定化される確率（ＦＰＲ：False Positive Ratio ）と、ｆ≧f*のフローが誤って特定化されない確率（ＦＮＲ：False Negative Ratio ）を明確にし、特定化精度を明らかにすることが重要である。そのためには、図1に示すような、f*とH*を与えたときの任意のfに対する特定化確率H（特定化曲線）を明らかにする必要がある。上述の技術については、下記の非特許文献４〜７を参照されたい。
【００１４】
【非特許文献１】S.Floyd and K.Fall，“Promoting the Use of End-to-End Congestion Control in the Internet,”IEEE/ACM Trans. on Networking, Vol.7(4),pp.458-473,August 1999
【非特許文献２】A.Demers，S.Keshav，and S.Shenker，“Analysis and simulation of a fair queueing algorithm,”SIGOMM’89,19(4),pp.1-12,September 1989
【非特許文献３】C.Estan and G.Varghese,“New Directions in Traffic Measurement and Accounting,”SIGCOMM’02,pp.323-336
【非特許文献４】W.Feng，K.G.Shin，D.D.Kandlur，and D.Saha，“The BLUE Active Queue Management Algorithms,”IEEE/ACM Trans. on Networking,Vol.10(4),pp.513-528,August 2002
【非特許文献５】R.Mahajan，S.Floyd，and D.Wetherall，“Controlling High-Bandwidth Flows at the Congested Router,”ICNP 2001
【非特許文献６】T.Mori，M.Uchida，R.Kawahara,J.Pan，and S.Goto，“Identifyning Elephant Flows Through Periodically Sampled Packets,”IMC’04
【非特許文献７】M.Kodialam，T.V.Laskman，S.Mohanty，“Runs bAsed Traffic Estimator(RATE):A Simple，Memory Efficient Scheme for Per-Flow Rate Estimation,”Infocom’04
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明は上記事情に鑑みてなされたものであり、その目的とするところは、パケットサンプリングによって得られた情報から高レートフローを特定化する簡易な技術を提供することにある。より具体的には、本発明の目的は、与えられたパケット到着率と特定化のための許容時間とから、任意のレートのフローが特定化される確率を解析的に導出して特定化曲線を明確にし、特定化に許容できる時間の上限値を満足しながら、任意の特定化曲線を与えるパラメータ設計を可能とする高レートフロー特定化方法並びにこの方法を適用した高レートフロー特定化システムを提供することにある。
【課題を解決するための手段】
【００１６】
前記目的を達成するため、本発明の請求項１に係る高レートフロー特定化方法は、パケットサンプリングによって得られた情報を用いるトラヒック計測結果に基づいて、許容時間内に高レートフローを特定化するステップを具備し、前記高レートフローを特定化するステップとして、与えられた計測期間内に一つ以上のパケットがサンプリングされたフローを高レートフローとして特定化するステップを用いることを特徴とする。
【００１７】
また、前記目的を達成するため、本発明の請求項２に係る発明では、請求項１に記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、パケット到着率と計測期間長が与えられたときに、任意のフローレートのフローの特定化確率を導出することを特徴とする。
また、前記目的を達成するため、本発明の請求項３に係る発明では、請求項１または２に記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、与えられた特定化フローレートの閾値とその特定化確率を満足する特定化曲線を実現するようサンプリング周期を設計することを特徴とする。
【００１８】
また、前記目的を達成するため、本発明の請求項４に係る高レートフロー特定化方法は、パケットサンプリングによって得られた情報を用いるトラヒック計測結果に基づいて、許容時間内に高レートフローを特定化するステップを具備し、前記高レートフローを特定化するステップにおいて、与えられた計測期間内に、タイムアウト時間以内に二個以上のパケットがサンプリングされたフローを高レートフローとして特定化することを特徴とする。
【００１９】
また、前記目的を達成するため、本発明の請求項５に係る発明では、請求項４に記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、パケット到着率と計測期間長が与えられ、タイムアウトの長さとサンプリング周期を定めたときに、任意のフローレートのフローの特定化確率を導出することを特徴とする。
また、前記目的を達成するため、本発明の請求項６に係る発明では、請求項４または５に記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、与えられた特定化フローレートの閾値とその特定化確率を満足する特定化曲線を実現する、タイムアウト時間とサンプリング周期の組を導出することを特徴とする。
【００２０】
また、前記目的を達成するため、本発明の請求項７に係る発明では、請求項４〜６のいずれかに記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、タイムアウト時間とサンプリング周期の選択可能な複数の組から、ネットワーク運用者の任意のポリシィに従って適用する組を選択することを特徴とする。
また、前記目的を達成するため、本発明の請求項８に係る発明では、請求高４に記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、パケット到着率と計測期間長が与えられ、タイムアウトの長さとサンプリング周期を定めたときに、任意のフローサイズを持つ任意のフローレートのフローの特定化確率を導出することを特徴とする。
また、前記目的を達成するため、本発明の請求項９に係る発明では、請求項１または４に記載の高レートフロー特定化方法における高レートフローを特定化するステップにおいて、着目するリンクの使用率が予め定めた値に達したときに、同じく予め定めた許容時間以内に、高レートフローと特定化することを特徴とする。
【００２１】
また、前記目的を達成するため、本発明の請求項１０に係る高レートフロー特定化システムは、パケットサンプリングによって得られた情報を用いるトラヒック計測結果に基づいて、許容時間内に高レートフローを特定化する高レートフロー特定化システムであって、任意の特定化曲線を実現するタイムアウト時間とサンプリング周期を設計するパラメータ設計手段と、測定期間中に、前記パケットサンプリング手段により着目リンクを流れるパケットをサンプリングするパケットサンプリング手段と、前記パケットサンプリング手段によるパケットサンプリング情報並びに前記タイムアウト時間の経過したフロー情報に基づいてフロー情報を記録・管理するフローテーブルと、この与えられた許容時間内に高レートフローを特定化するステップを具備し、前記フローテーブルに登録されたフローから高レートフローを特定化する高レートフロー特定化手段とを有することを特徴とする。
【発明の効果】
【００２２】
本発明によれば、与えられたパケット到着率と許容特定化時間とから、所望の特定化レート閾値とその特定化確率を満足する特定化曲線を与えるパラメータ設計を行いながら、パケットサンプリングにより簡易な方法でメモリサイズを抑えつつ、高レートフローを高い精度で特定化することが可能になるという効果が得られる。
【発明を実施するための最良の形態】
【００２３】
以下に、添付の図面に示す最適実施形態に基づいて、本発明の高レートフロー特定化方法を詳細に説明する。
【００２４】
図２は、本発明の一実施形態に係る、サンプリング情報を用いた高レートフロー特定化方法を実現するためのシステム構成図である。
図２において、１０１はパラメータ設計装置、１０２はパケットサンプリング装置、１０３はフロー情報消去装置、１０４はフローテーブル、１０５は高レートフロー特定化装置、１０６は高レートフローリストである。
【００２５】
パラメータ設計装置１０１により任意の特定化曲線を実現するタイムアウト時間とサンプリング周期が設計され、パケットサンプリング装置１０２とフロー情報消去装置１０３が設定される。測定期間中は、パケットサンプリング装置１０２により着目リンクを流れるパケットが一定周期でサンプリングされ、その情報に基づいてフローテーブル１０４が更新される。
【００２６】
一方、フロー情報消去装置１０３は、タイムアウト時間が経過したフロー情報をフローテーブル１０４より消去する。高レートフロー特定化装置１０５は、フローテーブル１０４に登録されたフローから高レートフローを特定化し、高レートフローリスト１０６に出力する。
【００２７】
以下に、本実施形態に係るサンプリング情報を用いた高レートフロー特定化方法について、（１）動作原理、（２）特定化確率の導出をそれぞれ説明する。
【００２８】
（１）動作原理
フローを、発着IPアドレス、発着ポート番号、プロトコルタイプが共通のパケットの集合と定義する。そして、特定の着目するリンクの利用率が閾値（例えば０.９）に達した際に、高レートフローを特定化限界時間φ秒以内に特定化することを考える。まず、パケットサンプリングにより特定化する最も直感的な手法（Naive sampling法：以下、単純サンプリング法ともいう）について述べ、続いて、特定化精度を向上させ得る特定化方式（Short timeout法：以下、短タイムアウト法ともいう）について述べる。
【００２９】
（１ａ）Naive Sampling法（単純サンプリング法）
パケットサンプリングでは、一定周期Ｎパケットごとに1個のパケットか、ランダムに確率１／Ｎで個々のパケットがサンプリングされる。測定期間Φ内に各フローから到着するパケット数は各々のフローレートに比例するため、高レートフローであるほどサンプリングされる確率が高くなる。
【００３０】
そのため、単純に１個以上のパケットがサンプリングされたフローを全て高レートフローとして特定化する方法、すなわち、単純サンプリング法が考えられる。測定期間Φ内に特定化閾値ｆ*のフローを確率Ｈ*で特定化する特定化曲線を与えるサンプリング周期Ｎを設計することが可能である。
【００３１】
この方法は直感的で実現も容易であるが、特定化の判断基準が大雑把であるため、高レートフローであっても、測定期間Φ以内に偶然サンプリングされなかったため特定化されない場合や、低レートフローであっても偶然サンプリングされたため特定化されてしまう場合が数多く発生し、特定化精度が低いことが予想される。
【００３２】
この状況は、図１に示すように、特定化曲線が緩やかな上昇曲線を示すことを意味し、理想的な特定化曲線（ｆ＜ｆ*でＨ＝０であり、ｆ≧ｆ*でＨ＝１となる単位ステップ関数）からの乖離が大きくなる。ｆ＜ｆ*における乖離が前述のＦＰＲに相当し、ｆ≧ｆ*における乖離がＦＮＲに相当する。
【００３３】
（１ｂ）Short Timeout法（短タイムアウト法）
パケットサンプリングを行うルータでは、フロー状態を保持するフローテーブルが用意され、パケットがサンプリングされるごとにそのパケットが属するフローのエントリがフローテーブル中に存在するか否かを調べ、存在する場合には計測パケット数カウンタを増加させるなどのフロー状態更新処理を行い、存在しない場合には新たにそのフローのエントリをフローテーブル中に作成する。
【００３４】
そして、最後にサンプリングされた時刻からタイムアウト時間Ｔ内に同一フローに属するパケットが新たにサンプリングされなかった場合に、フローテーブルに保持されたフロー状態を消去する。通常のパケットサンプリングはフローサイズやフロー時間といった統計値の収集を目的としており、Ｔは通常、１５秒や３０秒といった十分に大きな時間に設定される。
【００３５】
しかし、パケットサンプリングの目的を高レートフローの特定化に限定した場合、必ずしもＴを大きく設定する必要はない。高レートフローのパケットは短い間隔で到着することから、そのパケットがサンプリングされる間隔は短くなる傾向にある。そこでＴを数サンプリング周期〜数１０サンプリング周期という短い時間に設定し、その間に、２個以上のパケットがサンプリングされたフローを高レートフローとして特定化する方法、すなわち、短タイムアウト法が考えられる。
【００３６】
図３に、測定期間Φ内に４本のフローから合計で１２個のパケットがサンプリングされる場合の例を示す。図中、黒丸がサンプリング位置を示している。サンプリングは一定のパケット数Ｎごとに実施され、Ｔ＝２Ｎである場合、フロー（４）のみが高レートフローとして特定化される。
【００３７】
また、低レートフローのパケット到着間隔は長いことから、偶然、低レートフローのパケットがサンプリングされた場合も、短い時間に設定されたＴ以内に再度、同一のフローに属するパケットがサンプリングされる可能正は極めてまれであるため、この方法では、低レートフローが誤って特定化される確率（ＦＰＲ）が小さく抑えられ、特定化精度が向上する。
【００３８】
上述のように、短タイムアウト法の原理は非常に単純であり、実装が容易である。また、フローテーブルに作成されたフロー状態は短い時間で消去されるため、所要メモリサイズが小さくてすむという利点もある。
【００３９】
（２）特定化確率の導出
ここでは、単純サンプリング法と短タイムアウト法の特定化確率を解析的に導出し、特定化レート閾値ｆ*とその特定化確率Ｈ*を実現するためのパラメータ設定法について述べる。
【００４０】
〔前提〕
パケットは全て固定サイズＰ（bytes）とし、一定周期Ｎパケットごとに１個のパケットをサンプリングする。着目しているリンクの伝送容量がＣ（bps）で、リンク使用率がρであるときに、高レートフローの特定化を特定化許容時間φ（ｓ）以内に行う。パケットの到着率をΛ（pkts/s）とするとΛ＝ρC／8pとなるが、測定期間Φの間、Λは一定であるとする。測定期間Φの間に到着する総パケット数をＬ、総サンプリングパケット数をＤとすると、Ｌ＝Λφ、Ｄ＝Ｌ／Ｎとなる。
【００４１】
サイズがs（pkts）、継続時間がη（ｓ）のフローのフローレートｆを、
【００４２】
【数１】
2006196982.tif 000003
と定義する。さらに、フローレートがｆのフローの測定期間Φにおけるトラヒック比率pを
【００４３】
【数２】
2006196982.tif 000004
と定義する。
【００４４】
全てのフローについて、測定期間Φ中、ｆが一定であり、その結果ｐも一定であると仮定する。また、測定期間Φに対して全てのフローのηは十分に大きく、測定期間Φ中は常にアクティブであると仮定する。
【００４５】
多重されているフロー数が十分に多い場合、サンプリングされるパケットは各々独立であり、サンプリングされたパケットがトラヒック比率pのフローに属している確率は測定期間Φの間、常にｐとなる。フローレートｆはｐに比例することから、ｆの代わりにｐに対する特定化確率Ｈを導出する。また、特定化の閾値をｆ*で規定する代わりにｐ*で規定し、与えられたφとΛから、トラヒック比率がｐ*のフローを確率Ｈ*で特定化することを考える。
【００４６】
（２ａ）Naive sampling法（単純サンプリング法）
単純サンプリング法では、Ｄ個の総サンプリングパケット中、１個以上のパケットがサンプリングされたフローを高レートフローとして特定化するため、トラヒック比率がｐのフローの特定化確率Ｈ(p)は、
【００４７】
【数３】
2006196982.tif 000005
となる。
【００４８】
よって、ｐ＝ｐ*のフローの特定化確率をＨ*とするためには、Ｄを
【００４９】
【数４】
2006196982.tif 000006
とすればよい。よってサンプリング周期Ｎを、
【００５０】
【数５】
2006196982.tif 000007
と設定すればよい。フローテーブルにエントリされるフロー数の最大値はＤであり、必要メモリサイズはＤとなる。
【００５１】
（２ｂ）短タイムアウト法
タイムアウト時間Ｔを、Ｋを任意の整数をとるパラメータとしてＴ＝ＫＮで与える。そして、パラメータＫとＮを調整することにより任意の特定化曲線を実現する。以下に、トラヒック比率がｐのあるフローに着目し、その特定化確率Ｈ(p)を導出する。区間Ａ(d)を測定期間Φ内の任意の連続するｄ個のサンプリングが行われる区間と定義する。ｄ＝Ｄのとき、Ａ(d)＝Φとなる。
【００５２】
そしてｑ(p,d,j)を、区間Ａ(d)において着目フローのパケットがｊ個サンプリングされ、かつ、着目フローがこの間特定化されない確率と定義する。Ｔ以内に２個以上のパケットがサンプリングされると特定化されるため、着目フローが特定化されないためにはサンプリング位置がＫ＋１以上離れる必要がある。
【００５３】
よって、
【００５４】
【数６】
2006196982.tif 000008
と定義すると、ｊ＞Jに対してｑ(p,D,j)＝０となる。よって、Ｈ(p)は次式で与えられる。
【００５５】
【数７】
2006196982.tif 000009
【００５６】
以下では、０≦ｊ≦Ｊの各ｊに対するｑ(p,D,j)を導出する。
まず、ｊ＝０の時は必ず特定化されず、Ｄ個のサンプリングにおいて着目フローのパケットが一つもサンプリングされない確率は(1−p)Ｄとなることから、ｑ(p,D,0)は、
【００５７】
【数８】
2006196982.tif 000010
となる。
【００５８】
ｊ≧１に対するｑ(p,D,j)を算出するために、ｒ(p,d,j,v)を区間Ａ(d)において着目フローのパケットがｊ個サンプリングされ、かつ、最後(ｊ番目)のサンプリング位置が区間Ａ(d)の最後のサンプリング位置から遡ることｖ番目のサンプリング位置であり、かつ、着目フローがこの間、特定化されない確率と定義する。
【００５９】
ｊ＝１のときは必ず特定化されないことから、ｒ(p,d,1,v)はｖの値とは無関係に１≦ｄ≦Ｄの任意のdに対して
【００６０】
【数９】
2006196982.tif 000011
で与えられ、q(p,D,1)は次式で得られる。
【００６１】
【数１０】
2006196982.tif 000012
【００６２】
最後に、２≦ｊ≦Ｊの場合について考える。図4に示すように、区間Ａ(d)を、先頭から着目フローのｊ−１番目のサンプリング位置までの区間Ａ１(d１)と、残る区間Ａ２(d２)に分割して考える。但し、区間Ａ１(d１)とＡ２(d２)内のサンプリングパケット数を、各々、d１とd２とする（d１＋d２＝ｄ）。
【００６３】
区間Ａ１(d１)において着目フローが検出されない確率はｒ(p,d１,j−1,1)で与えられる。またそのとき、Ａ１(d１)において着目フローの全てのサンプリング位置は各々、Ｋ＋１以上離れる必要があることから、d１の取り得る最小値は(j−2)(K＋1)＋1となる。
【００６４】
一方、着目フローのｊ−１番目とｊ番目のサンプリング位置がＫ＋１以上離れるためには、d１がd−v−K以下である必要がある。また、区間Ａ２(d２)において、末尾からｖのサンプリング位置に唯一つ着目フローのパケットがサンプリングされる確率は
【００６５】
【数１１】
2006196982.tif 000013
で与えられる。よって、ｒ(p,d,j,v)は、
【００６６】
【数１２】
2006196982.tif 000014
で得られる。
【００６７】
ｖがｖ＞Ｄ−(j−1)(K＋1)のとき、ｒ(p,D,j,v)＝０となるため、ｑ(p,D,j)が次のように得られる。
【００６８】
【数１３】
2006196982.tif 000015
【００６９】
以下に、測定期間Φ内でトラヒック比率ｐのフローが特定化される確率Ｈ(p)の導出手順をまとめる。
（ａ）：式（５）よりq(p,D,0)を算出
（ｂ）：式（６）より、1≦v≦Dの各vに対してｒ(p,D,1,v)を算出し(ｑ(p,D,1)の算出に必要)、1≦d≦D-K-1の各dに対してｒ(p,d,1,1)を算出(ｒ(p,d,2,v)の算出に必要)
（ｃ）：式（７）よりｑ(p,D,1)を算出
【００７０】
（ｄ）：以下の手順を2≦j≦Jの各jに対してjの昇順に反復
（ｄ１）式（８）より、1≦v≦D−(j−1)(K＋1)の各ｖに対してｒ(p,D,j,v)を算出し(ｑ(p,D,j)の算出に必要)、(j−1)(K＋1)＋1≦ｄ≦D−K−1の各ｄに対してｒ(p,d,j,1)を算出(ｒ(p,d,j+1,v)の算出に必要、ただしｊ＝Ｊのときは不要)
（ｄ２）式（９）よりq(p,D,j)を算出
（ｅ）：式（４）よりＨ(p)を算出
【００７１】
Ｎ＝Ｌ／ＤであるためＬが与えられたとき、上記手順により特定化閾値ｐ*のフローを確率Ｈ*で特定化するＫとＮの組を数値的に得ることができる。また、フローテーブルには過去Ｋ個のサンプルパケットから得られたフロー状態のみが保持され、同時にテーブル上に保持されるフロー数は最大でもＫ本であるため、必要メモリサイズはＫとなる。
【００７２】
次に、本発明の数値評価結果について説明する。
〔数値評価〕
具体的な数値を用いて実現される特定化曲線を調べ、短タイムアウト法の基本特性を明らかにする。
【００７３】
パケットサイズをＰ＝1500(Bytes)とし、着目リンクの伝送容量をＣ＝10Ｇ(bps)とする。また、着目リンクの使用率がρ＝0.9の時に、特定化限界時間φ＝0.1(ｓ)以内に高レートフローを特定化する場合を考える。このとき、測定期間Φに到着する総パケット数はＬ＝75000となる。短タイムアウト法の特性はタイムアウト時間Ｋとサンプリング周期Ｎによって決まるが、Ｎ＝Ｌ／Ｄであるため、Ｋと総サンプリング数Ｄの値に応じて各種検討を行う。
【００７４】
〔設計パラメータＫとＤに関する評価〕
図５に、ＤをＤ＝100で固定しＫを1から16の範囲で変えた場合の、また、図６にＫをＫ＝4で固定しＤを10から10000の範囲で変えた場合の特定化曲線を各々示す。ＫやＤが増加するほど、２個以上のパケットが測定期間内にサンプリングされる確率が全てのフローにおいて増加するため、特定化確率が増加している。
【００７５】
しかし、ＫやＤを変えても特定化曲線の形には大きな変化はなく、ほぼ平行移動することがわかる。特定化の閾値として任意の点(ｐ*,Ｈ*)を与えることにより、設定するべきＫとＤの値の組合せと、その時の特定化曲線が決定する。
【００７６】
図7に、Ｈ*＝0.5としｐ*を0.01、0.05、0.1にした場合について、ＫとＤの取り得る可能な組合せを各々示す。ある(ｐ*,Ｈ*)を実現する可能なＫとＤの組合せは複数存在し、Ｋが増加するほど対応するＤの値は減少する。必要メモリサイズはＫであり、一方、サンプリング間隔ＮはＤに反比例することから、ＤとＮの間にはトレードオフが成立することになる。但し、特定化閾値ｐ*が増加するほど、ＫとＤをともに小さくすることができる。
【００７７】
ところで、短タイムアウト法は連続するK＋1個のパケットサンプリングにおいて同一のフローのパケットがサンプリングされるか否かを特定化の判断基準にしているため、測定期間中の総サンプリング数Ｄは、Ｄ≧Ｋ＋1を満たす必要がある。Ｋの増加に対して対応するＤは減少するが、Ｋの取り得る最大値をKmax、Ｄの取り得る最小値をDminとすると、Dmin＝Kmax＋1が成立する。
【００７８】
図7では、(Kmax,Dmin)に相当する点が示されている。なお、Kの取り得る最小値は１であり、この時に対応するＤの値がＤの取り得る最大値Ｄmaxとなる。
表１に、複数のｐ*とＨ*の組に対して各々定まるＫmaxの値を示す。ｐ*が大きなほど、もしくはＨ*が小さなほど、特定化確率を全体的に下げる(特定化曲線を右にシフトさせる)必要があるため、Ｋmaxは減少している。
【００７９】
【表１】
2006196982.tif 000016
【００８０】
〔特定化精度に関する評価〕
前述したように、ある(ｐ*,Ｈ*)を実現するＫとＤの値には複数の組合せが存在する。ここでは、これら複数の可能な組合せにより、短タイムアウト法の特定化精度がどのように変化するかを明らかにする。また、単純サンプリング法との特定化精度に関する比較を行う。
【００８１】
図8〜図１０に、ｐ*=0.01に対して、Ｈ*=0.01、0.5、0.99とした時の特定化曲線を各々示す。各図では、Ｋの値としてＫmin=１と、表１に示すＫmaxに加え、いくつかの値について短タイムアウト法を評価している。
【００８２】
全ての特定化曲線は点(ｐ*,Ｈ*)を通るが、短タイムアウト法は単純サンプリング法と比較してｐ＝ｐ*における切り分けがシャープであり、特定化精度を大きく向上することがわかる。また、短タイムアウト法はＫが小さなほど(Ｄが大きなほど)特定化曲線の傾きが急となり、特定化精度が向上することがわかる。
【００８３】
Ｈ*=0.5のとき、ＦＰＲとＦＮＲはほぼ等しくなるが、Ｈ*が小さな場合、ＦＰＲを抑えることができる反面、ＦＮＲが増大する。反対にＨ*が大きな場合、ＦＮＲを抑えることができる反面、ＦＰＲが増大する。Ｈ*をどの値に設定するかは、ＦＰＲとＦＮＲのどちらを重視するかによって決まる。位後の評価では、Ｈ*＝0.5と設定する。
【００８４】
〔フローサイズが特定化確率に及ぼす影響〕
特定化確率の導出に際して、着目フローの継続時間が十分に長く、測定期間中は常にアクティブであることを想定した。しかし、一般には、全てのフローがこの条件を満たすわけではないので、ここでは測定期間の一部においてのみアクティブなフローの特定化確率を導出し、フローサイズが特定化確率に及ぼす影響について評価する。
【００８５】
トラヒック比率がｐでサイズがｓ(pkts)で継続時間がη(ｓ)のフローが、測定期間φ(ｓ)内においてアクティブである期間の平均長をζ(ｓ)とする。便宜上、測定が開始された時刻をＴ＝ηとすると、着目フローの先頭のパケットが着目リンクに到着し始める時刻が０＜Ｔ＜η＋φであるとき、着目セッションの一部もしくは全体が測定期間内においてアクティブとなる。着目フローの開始点がランダムであると仮定すると、ζは、
【００８６】
【数１４】
2006196982.tif 000017
となる。
【００８７】
よって、このフローが計測期間Φ内にて経験するサンプリング機会の平均回数（着目フローがアクティブの間に実施されるサンプリングの平均回数)をＤ(p,s)とすると、
【００８８】
【数１５】
2006196982.tif 000018
となる。
【００８９】
サイズｓが十分に大きいときＤ(p,s)はDに漸近する。Ｄ(p,s)＜Ｄのフローに対する特定化のための計測は、実質的には総サンプリング数がＤ(p,s)となる期間実施される。よってＤ(p,s)＜Ｄのフローの平均特定化確率は、特定化確率の導出においてＤをＤ(p,s)とすることにより算出できる。
【００９０】
図１１に、(ｐ*,Ｈ*)=(0.01,0.5)を与えてＫとＤを設計したときの、ｐ＝0.05のフローについてサイズを横軸にとった平均特定化確率を示す。やはりＫmin＝１とＫmax＝166の場合を含む、Ｋのいくつかの場合について示している。図9に示すように、トラヒック比率がｐ＝５ｐ*＝0.05でサイズが十分に大きなフローの特定化確率は１に近い値を示すが、このことは図１１でも確認される。
【００９１】
しかし、同じフローレート(トラヒック比率)ｐ＝0.05のフローであっても、サイズｓが小さくなるにつれて、急激に特定化確率は減少することがわかる。このことは、短タイムアウト法は高レートでかつサイズの大きなフローを特定化することを意味する。高レートであってもサイズの小さなフローは他のフローに与える影響が小さいことから、短タイムアウト法はそのようなフローの特定化を避けることができ、より効果的な特定化が可能である。
【００９２】
図１２に、Kmin＝１とKmax＝166の各々の場合について、低レートフロー(ｐ＝0.002)、閾値に相当するフロー(ｐ＝0.01)、高レートフロー(ｐ＝0.05)の平均特定化確率をフローサイズｓに対して示す。短タイムアウト法が、高レートかつサイズの大きいフローのみを特定することが確認できる。
【００９３】
また、図１１，図１２より、Ｋが大きな(Ｄが小さな)ほど、より大きなサイズのフローのみを特定化する傾向は強くなることが確認できる。
【００９４】
〔特定化許容時間の及ぼす影響〕
これまでの評価は特定化許容時間φを0.1秒に固定して評価を行ったが、本節ではφが及ぼす影響について評価する。表２にφ＝0.01、0.1、1(s)としたときの、(ｐ*,Ｈ*)＝(0.01,0.5)におけるＫとＤの許容上限値と、サンプリング間隔Ｎの下限・上限値を各々まとめる。
【００９５】
【表２】
2006196982.tif 000019
【００９６】
φを変えても、ｐ*とＨ*が同じであればＫmaxとＤmaxは変化せず、また、Ｋの値に対応するＤの値も変化しない。そのため、特定化曲線は影響を受けない。しかし、Ｎ＝Ｌ／Ｄであり、Ｌはφによって決まるため、φが変化するとＮが変化し、Ｎの上限・下限値も変化している。φが増加するほどＮを大きく広げることができる。
【００９７】
さらに、φが変化するとＤ(p,s)が影響を受けるため、フローサイズｓに対する特定化確率が変化する。図１３に、ｐ＝0.05の平均特定化確率をｓに対して示す。あるサイズのフローが測定期間内でアクティブである時間割合はφが増加するほど低下するため、φが増加するほど大きなサイズのフローのみを特定化する傾向が増加する。
【００９８】
〔リンク使用率の及ぼす影響〕
これまでの評価は、高レートフローの特定化を開始するトリガとなる対象リンクのリンク使用率ρを0.9に固定して評価を行ったが、本節ではρが及ぼす影響について評価する。フローレートfに対して、トラヒック比率はｐ＝８Ｐ・ｆ／ρＣとなるため、ｆが同じであってもρが変わればｐも変化する。
【００９９】
そこで、Ｃ＝10Ｇ(bps)のリンクにおいて、ｆ*＝8.33×103(pkts/s)(100Ｍ(bps)に相当)のフローを0.5の確率で特定化することを考える(ｐ*=1/100ρ,H*=0.5)。表３に、いくつかのρに対して算出されたＫとＤの許容最大値と、Ｎの上限・下限値をまとめる。
【０１００】
【表３】
2006196982.tif 000020
【０１０１】
ρが増加するにつれてｐ*が減少するため、特定化確率を全体的に上げる必要がある。その結果、ＫmaxとＤmax(Ｋminに対応するＤの設定値)は共に増加する。ところで、計測期間Φ内に到着する総パケット数ＬはＬ＝ρＣφ／８Ｐであり、ρに比例して増加するが、表３よりＤmaxの増加度合いの方が大きいことがわかる。
【０１０２】
ところがＮmin=Ｌ／Ｄmaxであるため、Ｎminはρの増加に対して減少する。また、Dmin(＝Ｋmax＋1)はρに比例して増加するため、Ｎmaxはρの変化に対してほとんど一定となる。
【０１０３】
次に、ρの違いが特定化曲線に及ぼす影響について評価する。図１４に、ρ＝0.6、0.7、0.8、0.9における特定化曲線をＫ＝Ｋmin＝１とＫ＝Ｋmaxの各々の場合について示す。ただし、横軸はｐではなく、ｆでプロットしてある。K=1に対応するＤの値(Ｄmax)と、Ｋmaxおよび対応するＤの値(Ｄmin=Ｋmax＋1)は表３に示すようにρの値に応じて各々異なるが、特定化曲線はほとんど同一となる。
【０１０４】
また、図１５に、ｆ=５ｆ*のフローの平均特定化確率をフローサイズｓに対して示す。特定化曲線と同様、フローサイズに対する平均特定化確率についてもρの値とはほとんど無関係となった。以上の結果から、特定化の閾値に用いるフローレートfが同じであれば、特定化曲線やフローサイズに対する平均特定化確率は特定化を開始するリンク負荷ρの値とは無関係に定まることがわかる。
【０１０５】
〔特定化実施フロー〕
以下に、短タイムアウト法を用いた高レートフローの特定化実施フローをまとめる。
（ａ）リンク使用率ρと特定化許容時間φを設定
（ｂ）(ｐ*,Ｈ*)を設定→可能な(Ｋ,Ｎ)の組が決定
（ｃ）(Ｋ,Ｎ)をポリシィに従い選択
【０１０６】
〔パラメータ設定方法〕
ここでは、数値評価で得られた結果をもとに、短タイムアウト法のパラメータ(K,N)の設計方法に関して考察する。ある(ｐ*,Ｈ*)を実現するＫとＤ(実際にはＮを設計)の値には複数の組合せが存在するため、短タイムアウト法を実施するためには具体的にどの組合せを選ぶかが問題になる。
【０１０７】
表４に、設計パラメータＫとＮの選び方によってどのような影響が生じるかをまとめる。
【０１０８】
【表４】
2006196982.tif 000021
【０１０９】
Ｋが小さいほど、対応するＤの値が大きくなるため対応するＮの値は小さくなる。まず、Ｋが小さな(Ｎが小さな)ほど、フローテーブルに必要なメモリ量は小さくなり、サンプリング間隔も小さくなる。また、Ｋが小さな(Ｎが小さな)ほど、特定化精度は向上する。
【０１１０】
一方、高レートフローの中からさらに特定化されるフローをサイズの大きなものに限定する能力は、Ｋが大きな(Ｎが大きな)ほど向上する。このように、Ｋ(Ｎ)の大小には長所・短所があるため、どのようなＫとＮの組合せを選ぶかはネットワーク運用者のポリシィの問題となる。表５に、設計ポリシィの例をまとめて示す。
【０１１１】
【表５】
2006196982.tif 000022
【０１１２】
以上説明した記実施形態は、本発明の一例を示すものであり、本発明はこれに限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変更または改良等を行ってもよいことはいうまでもない。
【図面の簡単な説明】
【０１１３】
【図１】特定化曲線の例
【図２】本発明の実施の形態の一例を示すシステム構成図
【図３】短タイムアウト法の高レートフロー特定化例
【図４】区間分割の例
【図５】いくつかのKに対する特定化曲線
【図６】いくつかのDに対する特定化曲線
【図７】ＫとＤの関係を表す特定図
【図８】(ｐ*,Ｈ*)＝(0.01,0.01)とした時の特定化曲線
【図９】(ｐ*,Ｈ*)＝(0.01,0.5)とした時の特定化曲線
【図１０】(ｐ*,Ｈ*)＝(0.01,0.99)とした時の特定化曲線
【図１１】ｐ*＝0.05のフローのフローサイズに対する特定化確率
【図１２】三つのｐ*のフローのフローサイズに対する特定化確率
【図１３】様々なφにおけるフローサイズに対する特定化確率
【図１４】様々なρにおける特定化確率
【図１５】様々なρにおけるフローサイズに対する特定化確率
【符号の説明】
【０１１４】
１０１  パラメータ設計装置
１０２  パケットサンプリング装置
１０３  フロー情報消去装置
１０４  フローテーブル
１０５  高レートフロー特定化装置
１０６  高レートフローリスト
【図１】
2006196982.tif 000023
【図２】
2006196982.tif 000024
【図３】
2006196982.tif 000025
【図４】
2006196982.tif 000026
【図５】
2006196982.tif 000027
【図６】
2006196982.tif 000028
【図７】
2006196982.tif 000029
【図８】
2006196982.tif 000030
【図９】
2006196982.tif 000031
【図１０】
2006196982.tif 000032
【図１１】
2006196982.tif 000033
【図１２】
2006196982.tif 000034
【図１３】
2006196982.tif 000035
【図１４】
2006196982.tif 000036
【図１５】
2006196982.tif 000037