JP4453838B2 - タイムアウト処理方法とシステムおよびプログラム - Google Patents

Description

本発明は、ネットワークの例えばフロー計測において、フローテーブルに保存されるフロー状態エントリ数が無限に増加することを避けるためのタイムアウト処理に係り、特に、少ないメモリアクセス回数でのタイムアウト処理でも、フローテーブルにおける所要メモリ量の増加を抑えることができる技術に関するものである。

インターネットにおいて、フロー計測、すなわち、同一の発ＩＰアドレス、同一の着ＩＰアドレス、同一の発ポート番号、同一の着ポート番号、同一のプロトコルタイプを有するパケットの集合から定義されるフローを計測することは、効率的なネットワーク管理や制御を行う上で重要である。例えば、フロー計測により、フローサイズやフロー時間といったフローの各種統計値の収集が可能となる。

しかし、リンクの回線容量が２．５Ｇbpsや１０Ｇbpsと高速化するにつれ、リンクを流れるフロー数が膨大な数となるため、パケット流からパケットを一定周期もしくはランダムに抜き出すパケットサンプリングが注目されている。

このパケットサンプリングにより、一部のフロー状態のみを管理し、各種フロー統計値を得ることは実用上、非常に有用である。フローの状態はフローテーブルとしてメモリ（記憶装置）に保存され、パケットがサンプリングされるごとにフローテーブルに保存されたフローエントリが更新される。

フローの末尾のパケットにはＦＩＮビットがセットされるため、ＦＩＮビットがセットされたパケットがサンプルされた場合には、そのフローが終了したと判断できるので該当エントリをフローテーブルより消去することができる。

しかしパケットサンプリングでは全パケットが処理の対象とはならないため、ＦＩＮビットがセットされたパケットの大部分は見逃される。そのためパケットサンプリングでは、一定時間（タイムアウト時間）、新たにパケットがサンプルされなかったフローを終了したものと見なし、フローテーブルより消去するタイムアウト処理を行う。

フローエントリがタイムアウトしたか否かを判断する最も一般的な技術（タイムアウト評価）としては、例えば、非特許文献１に記載のものがある。この技術は、エントリごとに最後にパケットがサンプルされた時刻を保存しておき、一定周期で、フローテーブル内の全エントリを対象に、現在時刻と、保存されている最終サンプリング時刻との差分が、タイムアウト時間を越えたか否かを調べるものである。

このようにタイムアウトの有無を全フローエントリに対して調査する技術では、タイムアウト処理におけるメモリアクセス回数（フローテーブルアクセス回数）がフローテーブル内のエントリ数に比例して増加する。

また、タイムアウト処理中はフローテーブルが更新されないようロックする必要がある。そのため、例えば一定周期でパケットがサンプルされる場合には、タイムアウト処理はサンプリング間隔内で完了する必要がある。また、ランダムにパケットがサンプルされる場合には、二つのパケットが連続してサンプルされる可能性があるため、タイムアウト処理は回線レートにおけるパケット到着間隔以内で終了する必要がある。

そのため、タイムアウト処理におけるメモリアクセス回数を低減する必要がある。しかし、このようなタイムアウト処理におけるメモリアクセス回数の低減に関しての従来技術はない。

N. Duffield, C. Lund, and M. Thorup, "Properties and Prediction of Flow Statistics from Sampled Packet Streams," SIGCOMM IMW 2002.

解決しようとする問題点は、従来の技術では、フロー計測においてフローテーブルに保存されるフロー状態を消去するためのタイムアウト処理におけるメモリアクセス回数を低減することができない点である。

本発明の目的は、これら従来技術の課題を解決し、フロー計測におけるタイムアウト処理を効率的に行うことを可能とすることである。

上記目的を達成するため、本発明は、例えばフロー計測でフローテーブルに保存されるフロー状態数が無限に増加することを避けるためのタイムアウト処理を、限られたメモリアクセス回数で実現するものであり、着目リンクを流れるパケットを一定周期もしくはランダムにサンプリングしてフローテーブルに更新・登録された各フローエントリから、予め定められた数（Ｖ）だけランダムに選択して読み出し、選択したフローエントリのみを対象にタイムアウト（Ｋ）評価を行い、タイムアウトと判定したフローエントリをフローテーブルから消去することを特徴としている。尚、このようにメモリアクセス回数が制限されることによりフローテーブルから消去されるフローエントリ数が減るので、フローテーブルに用いるメモリ量が増加するため、そのフローテーブルサイズ（メモリ量）を予め求めておくことが必要となり、そのため、本発明では、タイムアウト評価の基準となるタイムアウト時間として、サンプリング時における通し番号等を用いることにより、最大エントリサイズを定式化して必要メモリ量Ｍを導出し（Ｍ＝｛（ＶＫ＋１）÷（Ｖ−１）｝＋｛１÷（２α）^１/２｝×｛（ＶＫ＋Ｖ）^１/２÷（Ｖ−１）｝）、フローテーブルを設計することを特徴とする。

本発明によれば、フロー計測等におけるパケットサンプリングにおいて、メモリ量の増加を抑えながら、タイムアウト処理に必要なメモリアクセス回数を大幅に低減することが可能である。

以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係るタイムアウト処理システムの構成例を示すブロック図であり、図２は、図１におけるタイムアウト処理システムによるタイムアウト処理動作例を示すフローチャート、図３は、図１におけるタイムアウト処理システムの第１の評価例を示す説明図、図４は、図１におけるタイムアウト処理システムの第２の評価例を示す説明図、図５は、図１におけるタイムアウト処理システムの第３の評価例を示す説明図、図６は、図１におけるタイムアウト処理システムの第４の評価例を示す説明図、図７は、図１におけるタイムアウト処理システムの第５の評価例を示す説明図である。

図１におけるタイムアウト処理システムは、ネットワークのフロー計測におけるタイムアウト処理を行うものであり、ＣＰＵ（Central Processing Unit）や主メモリ、表示装置、入力装置、外部記憶装置等を有するコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理装置としての機能を実行する。

図１において、１０１はメモリサイズ設計装置、１０２はパケットサンプリング装置、１０３はフロー情報消去装置、１０４はフローテーブルであり、これらを具備したタイムアウト処理システムは、例えばインターネット等のネットワークを構成するルータ等に設けられる。

このような構成により、図１に示すタイムアウト処理システムは、図示していないネットワークにおけるフロー計測に係るタイムアウト処理を行い、その際、図２に示すように、フローテーブル１０４に登録された各フローエントリの内、予め定められた数だけランダムに選択したフローエントリのみを対象にタイムアウト評価を行う（ステップＳ２０１）。

すなわち、パケットサンプリング装置１０２が、ネットワーク上の着目リンクを流れるパケットを一定周期でサンプリングし、フローエントリを生成してフローテーブル１０４に登録・更新する（ステップＳ２０１ａ）。

そして、フロー情報消去装置１０３が、フローテーブル１０４からランダムに予め定められた数だけフローエントリを選択して読み出し（ステップＳ２０１ｂ）、選択したフローエントリのみを対象にタイムアウトの有無を調査して、タイムアウトと判定したエントリをフローテーブル１０４から消去する（ステップＳ２０１ｃ）。

尚、本例のタイムアウト処理システムは、例えばインターネット上のＷＷＷ（World Wide Web）サーバにおけるＴＣＰセッションのタイムアウト処理に適用して、予め定められた数だけランダムに選択したセッションのみを対象にタイムアウト評価を行うこともでき、タイムアウトの有無を多数の対象に対して調査する必要がある場合に、広く用いることが可能である。

このように、本例では、タイムアウト評価の対象を、フローテーブル１０４にある全てのエントリに対して行うのではなく、所定の数のエントリのみに対して行う。このことにより、タイムアウト処理のためのメモリアクセス回数を、全てのエントリに対してタイムアウトの有無を調査する場合と比較して、大幅に低減することができる。

しかし、このようにタイムアウト評価の対象エントリを制限した場合、フローテーブル１０４内において、タイムアウトしたエントリが全て必ず消去されるとは限らないため、所要メモリ量の増加が問題となる。

この問題に対処するために、本例ではメモリサイズ設計装置１０１を設けており、このメモリサイズ設計装置１０１は、フローテーブル１０４の構成に必要なメモリサイズを導出する。

特に、本例では、メモリサイズ設計装置１０１は、フローテーブル１０４に登録するフローエントリの最大サイズを定式化することにより、当該フローテーブル１０４の構成に必要なメモリ量を導出して、メモリ量の設計を行う。

このような本例のタイムアウト処理システムにおけるタイムアウト動作原理とメモリ量の設計に関して、その詳細を以下に説明する。

（１）タイムアウト動作原理：フローテーブル１０４には、エントリが収容されるアドレスが付与されているものとし、サンプルパケット数といったフローに関する情報と最終サンプル時刻（サンプル番号で離散化された値：ここでは、パケットサンプリング装置１０２が一定周期でサンプリングする際に順次に付与する通し番号＝サンプリング周期の回数）が記憶される。そして、エントリが収容されているフローテーブル１０４におけるアドレスを管理するための（図示していない）エントリリスト（ＥＬ）を用意する。

このエントリリスト（ＥＬ）の要素ｉにはｉ番目のエントリが収容されているフローテーブル１０４のアドレスが記憶される。

フローテーブル１０４内にｋ個のエントリが存在するときに、パケットサンプリング装置１０２によりパケットがサンプルされた際、そのパケットが属するフローのエントリが、フローテーブル１０４内に存在する場合には該当するエントリが更新されるが、存在しない場合には、フローテーブル１０４の空きエントリの一つに該当フローのエントリが作成され、エントリリスト（ＥＬ）のｋ＋１番目に、作成したエントリのアドレスが記憶される。エントリの更新・作成処理の終了後のエントリ数をｋ’とする。

パケットサンプリング装置１０２が周期的にパケットをサンプリングする度に、フロー情報消去装置１０３は、フローテーブル１０４からの１つのエントリの選択と選択したエントリに対するタイムアウト評価を所定回数（Ｖ）繰り返し行う。

すなわち、フロー情報消去装置１０３は、ｋ’個のエントリリスト（ＥＬ）の要素からアドレスをランダムに１つ選択し、フローテーブル１０４の、選択したアドレスに収容されているエントリの最終サンプル時刻と、現在時刻（サンプル番号で離散化された値：ここでは、フローテーブル１０４内の最新のエントリに付与された通し番号）、との差分が、タイムアウト時間（Ｋ）より大きい場合には、該当エントリがタイムアウトしたものと判断し、該当エントリをフローテーブル１０４より消去し、ＥＬの該当要素にＥＬの末尾の要素をコピーする。そして、このランダムにエントリを選択する処理をＶ回、反復する。

この結果、フローテーブル１０４テーブルにエントリされているｋ’個のエントリからランダムにＶ個のエントリを選択し、選択したエントリに対してのみタイムアウトの有無を調査し、タイムアウトしている場合には該当エントリが消去される。これにより、１サンプリング間隔内のメモリアクセス回数をＶ回に抑えることができる。

本例では、タイムアウト時間（Ｋ）を、連続するサンプリング周期の回数（サンプリング通し番号）で定義しており、従来の全てのエントリに対してタイムアウトの有無を調査する場合には、Ｋ＋１回のメモリアクセスが最大で必要となる。

これに対して、本例では、１サンプリング間隔内のメモリアクセス回数をＶ回に抑えることができるため、従来の全てのエントリに対してタイムアウトの有無を調査する場合（Ｋ＋１回）と比較して、大幅に最大メモリアクセス回数を低減することが可能であり、処理量を大きく低減することが可能となる。

しかし、本例では、タイムアウトしたエントリが全て必ず消去されるとは限らないため、上述したように、所要メモリ量の増加が問題となり、メモリサイズ設計装置１０１により、以下のようにして、（２）所要メモリ量の設計を行う。

（２）所要メモリ量の導出：所要メモリ量は、本来、フローの分布やパケットの到着パターンに依存する。ここでは、所要メモリ量の上限を得るため、まず、従来の全てのエントリに対してタイムアウト（Ｋ）の有無を調査する場合において、所要メモリ量が最大となるパケットの到着パターン（過去Ｋ回のサンプリングにおいて、全て異なるフローに属するパケットがサンプルされる）を想定する。これは、サンプルされたパケットが全て新規のエントリである場合に相当する。

尚、本例におけるランダムに選択するエントリの数Ｖが１つの場合（「Ｖ＝１」）、フローテーブル１０４内のエントリ数は無限に増加するため、以下では、「Ｖ＞１」を想定する。

フローテーブル１０４内のエントリ数の定常状態確率を厳密に陽な式で導出することは困難なので、１回のタイムアウト処理におけるＶ回のエントリ調査の各々を観測点と考え、各観測点において確率（１／Ｖ＝１÷Ｖ）でエントリが１つ増加すると考える。

これにより、実際よりもエントリ増加過程の分散が大きくなるため、この近似は分散を大きく見積もることとなり、所要メモリ量の安全側の近似を与えることとなる。

このように想定したモデルにおいて、エントリ数ｋ個の定常状態確率Ｐｋは、「Ｋ＋１≦ｋ」の任意のｋに対して、下記の式（１）が成立する。

Ｐｋ＝Ｐ_ｋ−１×｛ｋ÷Ｖ（ｋ−Ｋ）｝ …（１）

この定常状態確率Ｐｋの母関数をＦ（ｚ）とし、さらに、「Ｆ^(１)(１)＝ｄＦ(ｚ)/ｄｚ|ｚ＝１」、「Ｆ^(２)(１)＝ｄ^２Ｆ(ｚ)/ｄｚ^２|ｚ＝１」と定義すると、次の式（２）、（３）が得られる。

Ｆ^(１)(１)＝（ＶＫ＋１）÷（Ｖ−１） …（２）

Ｆ^(２)(１)＝［｛（ＶＫ―Ｖ＋３）・（ＶＫ＋１）｝÷（Ｖ−１）^２］＋｛１÷（Ｖ−１）｝ …（３）

これらの式（２）、（３）を用いて、エントリ数ｋの平均Ｅ(ｋ)と分散Ｖar(ｋ)は、次の式（４）、（５）で得られる。

Ｅ(ｋ)＝（ＶＫ＋１）÷（Ｖ−１） …（４）

Ｖar(ｋ)＝（ＶＫ＋Ｖ）÷（Ｖ−１）^２ …（５）

図３においては、エントリ数ｋの平均値と標準偏差の、解析値とシミュレーション値の比較結果を示している。すなわち、この図３においては、上記式（４）と式（５）により算出したエントリ数ｋの平均値（Ｅ(ｋ)(ｔｈ.)）と、標準偏差（Sｔd(ｋ)(ｔｈ.)）を、タイムアウト時間（Ｋ）に対してプロットした例を示している。

ただし、図３においては、ランダムに選択するエントリ数Ｖ＝８とした。また、比較のため、計算機シミュレーションによって算出されたエントリ数ｋの平均値（Ｅ(ｋ)(ｓｉｍ.)）と標準偏差（Ｓｔｄ(ｋ)(ｓｉｍ.)）についても図３において示している。

この図３に示すように、平均値については、解析値とシミュレーション値は、全てのＫの範囲にわたってよく一致している。一方、標準偏差については、全てのＫの範囲にわたり、解析値はシミュレーション値と比較して大きくなっている。

このことから、式（５）で得られるエントリ数ｋの分散を用いて所要メモリ量を設計すれば、安全側の設計となることが確認できる。

一般に、平均がμで標準偏差がσの任意の確率変数Ｘに対して、チェビシェフの不等式より、「Ｐ(|Ｘ−μ|≧ｋσ)≦１/ｋ^２」が成立する。よって、メモリサイズＭを、下記の式（６）と設計すれば、連続するＫ回のサンプルされたパケットが全て異なるフローに属する場合であっても、フローテーブル１０４でのメモリ溢れが生じる確率（本例のシステムを具備したルータのベンダーが自由に設計するパラメータ）をα以下で抑えることができる。

Ｍ＝｛（ＶＫ＋１）÷（Ｖ−１）｝＋｛１÷（２α）^１/２｝×｛（ＶＫ＋Ｖ）^１/２÷（Ｖ−１）｝ …（６）

ここで、ランダムに選択するエントリの数Ｖ→∞とすると、本例は、従来の全エントリを調査する場合と同じになるが、式（６）においても、Ｍ→Ｋとなることが確認できる。

次に、このような本例の数値評価結果について図４〜図７を用いて説明する。数値評価としては、具体的な数値を用いて本例の有効性を確認する。

図４は、ランダムに選択するエントリの数Ｖに対する設計メモリ量と観測平均エントリ数と観測最大エントリ数の特性を示している。すなわち、図４においては、式（６）から算出されたメモリサイズＭと、実際の計測によって得られたパケットトレースに本例を適用したときの、平均エントリ数Ｅ(ｋ)と最大エントリ数Ｍax(Ｋ)を、ランダムに選択するエントリの数Ｖに対して各々プロットした例を示している。

ただし、図４においては、タイムアウト時間「Ｋ＝１００」とし、パケットトレースにはhttp://pma.nlanr.net/で公開されているデータのうち、IndianapolisからKansas City方向の、最初の「２．０×１０^７」パケット（約１４７秒に相当）を用い、パケットサンプリング周期Ｎは１００とした。

この図４においては、全てのランダム選択エントリ数（Ｖ）の範囲において、式（６）により設計したメモリサイズは、観測された最大エントリ数を抑えていることが確認できる。

また、図５は、タイムアウト時間Ｋに対する本例による設計メモリ量と従来の全エントリ調査による観測最大エントリ数との特性を示している。すなわち、本図５においては、本例のランダムエントリ選択（ＲＣ：Random Check）と従来の全エントリ調査（ＦＣ：Full Check）とにおける設計メモリ量Ｍ（ＦＣの場合はＭ＝Ｋ）と、観測された最大エントリ数Ｍax(ｋ)を、各々、タイムアウト時間（Ｋ）に対してプロットした例を示す。ただし、本例では、ランダム選択エントリ数Ｖ＝８とした。

この図５からも、やはり全てのタイムアウト時間Ｋの領域において、設計メモリ量Ｍは、観測された最大エントリ数Ｍax(ｋ)を抑えていることが確認できる。タイムアウト時間Ｋが大きな領域では、連続するＫ回のサンプリングにおいて、サンプルされるフロー数はＫよりも小さくなるため、設計メモリ量Ｍと観測された最大エントリ数Ｍax(ｋ)が大きく乖離する。そのため、タイムアウト時間Ｋが大きなときには設計メモリ量Ｍは過剰設計となる。

次に図６は、メモリアクセス回数低減比率を一定にしたときの、本例によるメモリ量増加比率の特性例を示しており、本図６においては、εを「０＜ε＜１」の実数パラメータとして「Ｖ＝εＫ」としたときの、従来の全エントリ調査法の所要メモリ量（Ｋ）に対する本例での所要メモリ量（Ｍ）の比率（Ｍ／Ｋ）をＫに対してプロットした例を示している。ただし、「α（フローテーブルメモリ溢れが生じる確率）＝０．０１」とし、また、パラメータεの設定値として、「０．１」、「０．０１」、「０．００１」の３つを評価した。

この図６に示すように、タイムアウト時間Ｋの増加に伴い、「Ｍ/Ｋ」の値は減少し、１に漸近する。すなわち、本例におけるメモリ量は、従来の全エントリ調査の場合とほとんど同じとなる。

また、タイムアウト時間Ｋが小さな場合、本例では、従来の全エントリを調査する場合と比較して所要メモリ量が増加するが、このようなタイムアウト時間Ｋの領域では、所要メモリ量そのものが小さいため、本例によるメモリ量の増加は、ほとんど問題にならない。

図７は、メモリ量増加比率を与えたときの、本例のメモリアクセス回数低減比率の特性例を示しており、この図７においては、κ（カッパ）を１以上の実数パラメータとして、本例における所要メモリ量Ｍが「Ｍ≦κＫ」を満たすεの最小値をＫ（タイムアウト時間）に対してプロットした例を示している。

通常、パケットサンプリングでは、タイムアウト時間を１５秒に設定するが、この場合、タイムアウト時間Ｋ＝２．０×１０^４に相当する。このとき、本例の技術を用いることにより、図７に示すように、例えば１割のメモリ増加で、タイムアウト処理のメモリアクセス回数を「１／１０００」に低減することが可能となる。

以上、図１〜図７を用いて説明したように、本例では、フロー計測でフローテーブルに保存されるフロー状態数が無限に増加することを避けるためのタイムアウト処理を、限られたメモリアクセス回数で実現することを目的に、着目リンクを流れるパケットを一定周期にサンプリングしてフローエントリを生成しフローテーブルに更新・登録すると共に、フローテーブルからランダムに予め定められた数（Ｖ個）だけ選択したフローエントリのみを対象にタイムアウト評価を行い、タイムアウトと判定したフローエントリをフローテーブルから消去する。これにより、フロー計測におけるタイムアウト処理において、メモリアクセス回数を大幅に低減することができる。

また、このようにタイムアウト評価の対象エントリを制限した場合、フローテーブル１０４内において、タイムアウトしたエントリが全て必ず消去されるとは限らないため、所要メモリ量の増加が問題となる。この問題に対処するために、本例ではメモリサイズ設計装置１０１を設け、このメモリサイズ設計装置１０１により、フローテーブル１０４の構成に必要なメモリサイズを予め導出し、当該メモリサイズでフローテーブルを生成する。特に、本例では、最大エントリサイズを定式化することにより必要メモリ量を導出し、メモリ量の設計を可能としている。

これにより、パケットサンプリングにおいて、メモリ量の増加を抑えながら、タイムアウト処理に必要なメモリアクセス回数を大幅に低減することができる。

尚、本発明は、図１〜図７を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、パケットサンプリング装置１０２が、ネットワーク上の着目リンクを流れるパケットを一定周期でサンプリングし、フローエントリを生成してフローテーブル１０４に登録・更新するものとしているが、パケットサンプリング装置１０２が、ネットワーク上の着目リンクを流れるパケットをランダムにサンプリングすることでも良い。

また、本例のシステムを形成するコンピュータ構成例として、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Flexible Disk）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。

本発明に係るタイムアウト処理システムの構成例を示すブロック図である。 図１におけるタイムアウト処理システムによるタイムアウト処理動作例を示すフローチャートである。 図１におけるタイムアウト処理システムの第１の評価例を示す説明図である。 図１におけるタイムアウト処理システムの第２の評価例を示す説明図である。 図１におけるタイムアウト処理システムの第３の評価例を示す説明図である。 図１におけるタイムアウト処理システムの第４の評価例を示す説明図である。 図１におけるタイムアウト処理システムの第５の評価例を示す説明図である。

符号の説明

１０１：メモリサイズ設計装置、１０２：パケットサンプリング装置、１０３：フロー情報消去装置、１０４：フローテーブル。

Claims (8)

1. ネットワークのフロー計測におけるタイムアウト処理方法であって、
   予め定められた数だけランダムに選択したフローエントリのみを対象にタイムアウト評価を行う手順を有することを特徴とするタイムアウト処理方法。
2. ネットワークのフロー計測におけるタイムアウト処理方法であって、
   フロー計測対象のパケットをサンプリングしフローエントリを生成してフローテーブルに登録する手順と、
   上記フローテーブルから予め定められた数だけフローエントリをランダムに選択する手順と、
   選択したフローエントリのみを対象にタイムアウト評価を行う手順と
   を有することを特徴とするタイムアウト処理方法。
3. 請求項１もしくは請求項２のいずれかに記載のタイムアウト処理方法であって、
   上記フローエントリを登録するフローテーブルの最大サイズを定式化することにより、当該フローテーブルの構成に必要なメモリ量を導出して、メモリ量の設計を行う手順
   を有することを特徴とするタイムアウト処理方法。
4. ＷＷＷサーバにおけるセッションのタイムアウト処理方法であって、
   予め定められた数だけランダムに選択したセッションのみを対象にタイムアウト評価を行う手順を有することを特徴とするタイムアウト処理方法。
5. コンピュータに、請求項１から請求項４のいずれかに記載のタイムアウト処理方法における各手順を実行させるためのプログラム。
6. ネットワークのフロー計測におけるタイムアウト処理を行うシステムであって、
   フロー計測対象のパケットをサンプリングしフローエントリを生成してフローテーブルに登録する手段と、
   上記フローテーブルから予め定められた数だけフローエントリをランダムに選択し、選択したフローエントリのみを対象にタイムアウト評価を行う手段と
   を有することを特徴とするタイムアウト処理システム。
7. ネットワークのフロー計測で用いるフローテーブルにおけるフローエントリに対するタイムアウト処理を行うシステムであって、
   フロー計測対象のパケットをサンプリングして当該パケットにサンプリング通し番号を付与し、上記フローテーブルにおける当該フローエントリを更新する手段と、
   上記フローテーブルから予め定められた２以上の数（Ｖ）のフローエントリをランダムに選択し、選択したフローエントリにおけるサンプリング通し番号と最新のサンプリング通し番号とを比較し、差分が予め定められたタイムアウト値（Ｋ）より大きい場合に、当該フローエントリを上記フローテーブルから消去する手段と
   を有することを特徴とするタイムアウト処理システム。
8. 請求項７に記載のタイムアウト処理システムであって、
   上記フローテーブルでのメモリ溢れが生じる確率をα以下で抑えるために当該フローテーブルに必要なメモリＭ量を、Ｍ＝｛（ＶＫ＋１）÷（Ｖ−１）｝＋｛１÷（２α）^１/２｝×｛（ＶＫ＋Ｖ）^１/２÷（Ｖ−１）｝の式を用いて求める手段
   を有することを特徴とするタイムアウト処理システム。

Images