(57)【要約】【課題】処理リソースおよび処理時間が短縮された、サンプル・サイズで、メモリ要件の小さいトラフィック推定方法を提供する。【解決手段】リンクによって相互接続されたノードのネットワークにおけるフロー単位トラフィックを推定する方法は、ノードへの着信トラフィック・ストリームをハッシュ関数を用いたフロー割当てによって多数の平行なサブストリームに分割する。着信トラフィック・ストリームのフローの各々はそのサブストリームにおいてトラフィックの大きな断片を構成しているので、２個のランを取得する確率は高くなる。次に、フロー当たりの２個のランの数を用いてフローのトラフィックの推定値が生成される。【選択図】図３
2005348415.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク・ノードにおけるフローに対するトラフィックの比率を生成する方法であって、該方法は、
（ａ）ハッシング関数に基づいて、入力されたパケット・ストリームのあるフローのパケットのどのサブストリームにパケットが属しているかを決定する工程と、
（ｂ）各フローについて、ｉ）サンプル・カウントの総数、ｉｉ）各サンプル・ストリームに対するサブストリーム・サンプル・カウント、およびｉｉｉ）サンプリング間隔を更新する工程と、
（ｃ）各フローに対するランの数を測定する工程と、
（ｄ）前記サンプリング間隔が所定の精度レベルを満たすかどうかをテストする工程と、
（ｅ）前記サンプリング間隔が所定の精度レベルを満たす場合には、前記対応するランの数に基づいて各フローに対する入力されたパケット・ストリーム内のフローの比率を生成する工程とを含む方法。
【請求項２】
フローの各比率についての分散を生成する工程をさらに含む請求項１に記載の発明。
【請求項３】
前記工程は各フローｆの各比率ｐ（ｆ）について前記分散δ（ｆ）を次式のように生成する請求項２に記載の発明：
【数１】
2005348415.tif 000052
上式中、ｒ［ｈ（ｆ）］は前記サンプリング間隔に対するＴ［ｈ（ｆ）］の比率であり、ｈ（・）は前記ハッシング関数であり、Ｔ［ｈ（ｆ）］は第ｈ（ｆ）番目のサブストリ−ムについてのサブストリーム・サンプリング・カウントである。
【請求項４】
各フローについて信頼区間を生成する工程をさらに含む請求項１に記載の発明。
【請求項５】
工程（ｃ）は対応するランＮ２（ｆ）の数から各フローｆの各比率ｐ（ｆ）を次式のように生成する請求項１に記載の発明：
【数２】
2005348415.tif 000053
上式中、ｒ［ｈ（ｆ）］は前記サンプリング間隔に対するＴ［ｈ（ｆ）］の比率であり、ｈ（・）は前記ハッシング関数であり、Ｎ２（ｆ）はフローｆのランの数であり、Ｔ［ｈ（ｆ）］は第ｈ（ｆ）番目のサブストリ−ムについてのサブストリーム・サンプリング・カウントである。
【請求項６】
工程（ｂ）に関し、ランの数はＮ個のランの数であり、Ｎは１より大きい正の整数である請求項１に記載の発明。
【請求項７】
Ｎは２である請求項６に記載の発明。
【請求項８】
工程（ｂ）はフローがサブストリームｈ（ｆ）にハッシュされる毎に前記サンプリング間隔を更新し、ｈ（・）は前記ハッシング関数である請求項１に記載の発明。
【請求項９】
工程（ｄ）は次式に基づいて前記サンプリング間隔をテストする請求項８に記載の発明：
【数３】
2005348415.tif 000054
ＴＲは前記所定の精度レベルについての間隔をサンプリングする比率法であり、Ｔはサンプリングの総数であり、Ｔｍａｘは前記サンプリング間隔である。
【請求項１０】
前記方法は前記２つ以上のノードに結合されたネットワーク・コントローラのプロセッサ内で実施される請求項１に記載の発明。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワークにおけるノード間のデータ転送に関し、より特には、該ネットワークを介するフロー単位のトラフィックの推定値の生成に関する。
【背景技術】
【０００２】
本出願は利益を代理人整理番号Ｈａｏ３−３２−３２ＰＲＯＶとして２００４年６月４日に出願された米国特許仮出願第６０／５７７２７９号の出願日の恩恵を主張するものである。
【０００３】
この出願は代理人整理番号Ｋｏｄｉａｌａｍ３３−３３としてこの出願の提出と同日の２００４年９月２２日に出願された米国特許出願第０８／ｘｘｘｘｘｘ号に関連し、その教示を参照により本願明細書に組み入れた。
【０００４】
パケット網におけるトラフィックの正確な測定は、トラフィック管理、アカウンティングサービス妨害（ＤｏＳ）の検出、およびトラフィック工学の重要な要素である。トラフィック測定はフロー単位で実行されるので、パケット網のトラフィックはネットワーク・フローに分類されるかもしれない。ネットワーク・フローの定義は用途に応じて変わる。例えば、フローはＩＰパケット・ヘッダ（例えば、ソース／デスティネーション・ポート／アドレス）における５タプル、特定のデスティネーション（例えば、デスティネーション・アドレス・プレフィックスによって特徴付けられるノードまたはネットワーク）、あるいはソース・セットワークによって特徴付けられる。ウイルスまたはワームの検出に関しては、フローは特定のワーム・シグネチャを含んだパケットとしても定義されるかもしれない。フローのこの広い定義に関し、パケットが特定のフローに属しているかどうかのチェックは、ネットワーク・リソースの点では費用のかかるオペレーションである。したがって、パケット単位のフローレート測定のためにこのオペレーションを実行することを回避することが好ましい。
【０００５】
トラフィックを測定するのに用いられるある先行技術のアプローチは、ノード（例えば、ノードのルータ）に到着するトラフィックをサンプリングし、フロー単位でトラフィック到着のカウントを保持し、次にこのトラフィック到着カウントに基づいてフロー単位のトラフィックを推定することである。しかし、多数のフローについては、この先行技術のアプローチはフロー単位のトラフィック到着カウントを保持するためにかなりのメモリおよび処理リソースを必要とする。いくつかの場合、５０万〜１００万ものフローがバックボーン・パケット・ネットワーク内に存在するかもしれない。フロー単位トラフィックの測定はリアルタイムのトラフィック管理、課金、およびネットワーク・セキュリティにおいていくつかの用途があるので、ルータまたはネットワーク・リンクを横断するすべてのフローについてフロー単位の状態を維持することなく、正確なフロー単位の情報が十分に取得されるべきである。
【０００６】
いくつかの特定の重要な測定用途は、ＤｏＳ、アクティブ・キュー管理、およびウイルス／ワーム検出である。ＤｏＳ用途のために、所与のデスティネーションに向かうトラフィック・フローが突然増加すると、ＤｏＳ攻撃の開始をシグナリングする。ネットワーク・ノードにおけるトラフィックが異常であることを決定するとともに、アラームをトリガし、かつ疑わしいフロー（トラフィック・ストリーム）のより詳細な監視を起動するために、ある推定値が用いられるかもしれない。アクティブ・キュー管理のために、フロー単位測定はネットワークの公平性をキューイングすることを可能にする。特に、往復時間遅延の大きな差を呈する、開ループのユーザ・データ・プロトコル（ＵＤＰ）ソースまたは通信制御プロトコル（ＴＣＰ）ソースの制御されていないフローのために、不正なソースの大きなフローを分離すれば、フローの残りの部分にそれが及ぼす影響が低減される。しかし、不正ソースから比較的少数のフローを識別かつ追跡することは、同様に多数（数万〜数十万）の小さなソースを追跡することを必要とするので好ましくない。
【０００７】
ウイルス／ワーム検出用途については、パケット・ペイロードはネットワークにおけるウイルス／ワーム攻撃を検出するためのフローと考えられるかもしれない。同じペイロードを有するいくつかのパケットはネットワークを介するウイルス／ワームの拡大の開始を示すかもしれない。一般的なウェブ・サイトを含んでいるような共通のペイロードはアラームをトリガすべきではないが、類似しているが同一ではないペイロードを有する多様な形態のワームは識別されるべきである。同一または類似するペイロードを有するパケットを測定することにより、所望なパケット・ペイロードと不所望のパケット・ペイロードとのそのような識別が可能となるかもしれない。
【０００８】
他の用途には、過剰なメモリまたは処理リソース（「ヘビー・ヒッター」）を消費するフローの追跡がある。このようなヘビー・ヒッターを識別かつ追跡する１つの方法は、仮定した確率密度を有するフローをサンプリングすることであり、パケットが属するフローがまだメモリ内にない場合、そのフローはメモリに加えられる。この時点から、ノードに到着し、かつこのフローに属するパケットのすべてが計数される。すべてのパケットが計数されるので、サンプリングされたフローはハッシュ・テーブル内に保持され、適切なカウンタを増分するために、パケット到着毎にパケットのフローＩＤがハッシュ・テーブルにハッシュされる。したがって、各パケット到着毎の処理が無作為サンプリングに比して増大されるが、メモリのサイズが縮小されるのでこの方法は比較的実施し易い。
【特許文献１】米国特許仮出願第６０／５７７２７９号
【特許文献２】米国特許出願第０８／ｘｘｘｘｘｘ号
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、フロー推定のための先行技術の方法の大半は依然として大きなサンプル・サイズを必要とし、それに応じてメモリ要件は大きくなる。さらに、そのような処理にはかなりの処理リソース、および完了のためにかなりの時間を必要とするかもしれない。
【課題を解決するための手段】
【００１０】
［９９０．５２４］リンクによって相互接続されたノードのネットワークにおいてフロー単位のトラフィックを推定する方法は、ハッシュ関数を用いたフロー割当てによってあるノードへの着信トラフィックを多数の平行するサブストリームに分割する。着信トラフィック・ストリームのフローの各々はそのサブストリームにおいてトラフィックの大きな断片を構成しているので、Ｎ−ラン（Ｎ個の連続する同じフローの到着）を取得する確率はそのサブストリーム内で増大する。次に、フロー当たりのＮ−ランの数を用いてフローのトラフィックの推定値が生成される。
【００１１】
本発明の例示的実施形態によれば（ｉ）ハッシュ関数に基づいて、入力されたパケット・ストリームのあるフローのパケットのどのサブストリームにパケットが属しているかを決定することによって、（ｉｉ）各フローについて、１）サンプル・カウントの総数、２）各サンプル・ストリームに対するサブストリーム・サンプル・カウント、および３）サンプリング間隔を更新することによって、（ｉｉｉ）各フローに対するランの数を測定することによって、（ｉｖ）サンプリング間隔が所定の精度レベルを満たすかどうかをテストすることによって、および（ｖ）サンプリング間隔が所定の精度レベルを満たす場合には、対応するランの数に基づいて各フローに対する入力されたパケット・ストリーム内のフローの比率を生成することによって、ネットワーク・ノード内のフローに対するトラフィックの比率が提供される。
【００１２】
本発明の他の態様、特徴、および利点は以下の詳細な説明、添付の特許請求の範囲、および添付図面からより完全に明白となろう。
本発明を分かり易くするために、以下の定義を記載する。本発明はネットワーク・フローの測定を用いたトラフィック測定に関し、フローはトラフィック測定用途に基づいて予め定義される。フローのセットＦがルータなどのノードで発生する。各パケット（到着とも呼ばれる）はセットＦの１つのフローｆに属する（すなわち、ｆ∈Ｆ）。フローｆ∈Ｆへの到着率はａ（ｆ）で表し、ノードへの全体の到着率（パケット／秒）はλで表す。ここでλ＝Σｆ∈Ｆａ（ｆ）である。トラフィック対フローｆ∈Ｆに属するノードの比率をｐ（ｆ）で表し、ｐ（ｆ）＝（ａ（ｆ）／λ）である。
本発明の例示的実施形態によれば、ａ（ｆ）の推定値
【数１】
2005348415.tif 000003
が各ｆ∈Ｆに対して生成される。特に、λの測定は比較的容易に達成されるかもしれないので、推定値
【数２】
2005348415.tif 000004
が各ｆ∈Ｆのｐ（ｆ）に対して生成され、次に、この推定値
【数３】
2005348415.tif 000005
を用いてａ（ｆ）に対する推定値
【数４】
2005348415.tif 000006
が生成される。ｐ（ｆ）の値は到着するパケットがフローｆに属している確率に関連しており、ｐ（ｆ）は推定が実行される時間間隔（推定またはサンプリング周期）にわたって比較的不変であるかもしれない。到着するパケットが所与のフローｆに属している確率は、他のすべてのパケットの到着の確率と独立しているかもしれない。所与のノードへの到着が依存的（すなわち、ノードに到着する次のパケットのフローＩＤが現在のパケットのフローＩＤに依存している）であっても、到着するストリームの無作為抽出がこの依存を除去するか、または緩和する。
【００１３】
このサンプリング方法は、任意の所与のフローｆ∈Ｆについて、式（１）がαを超える確率に当てはまるようにｐ（ｆ）の推定値
【数５】
2005348415.tif 000007
を決定する：
【数６】
2005348415.tif 000008
故に、
【数７】
2005348415.tif 000009
の誤差はα未満の確率を許容するかもしれない。
【００１４】
例えば、サンプリングの要件は次のようになる：サンプリング周期の終わりでは、任意のフローｆの場合、誤差
【数８】
2005348415.tif 000010
±０．００００５以内、および９９．９９％を超える確率αでｐ（ｆ）を決定する。この要件はβ＝０．０００１およびα＝０．９９９９に変換される。Ｎ（ａ，ｂ）は平均値ａおよび分散ｂの正規分布を表し、Ｚαはその単位正規分布のαパーセント点を意味する。α＝９９．９９％の場合、Ｚα＝４．０となる。
【００１５】
所望のレベルの精度でフローのすべてを推定するのに要する時間の量は、サンプリング間隔とも呼ばれる推定時間である。本願明細書に記載の実施形態に関し、この推定時間は所望のレベルの精度のためのサンプリングの数の点で与えられ、これは一定のパケット到着レートについて、ある時間測定単位に直接変換される。
【００１６】
第１の実施形態によれば、ラン・ベースのトラフィック推定（ＲＡＴＥ）法は各フローによって送信されるトラフィックの比率を決定する。このＲＡＴＥ法ノードにおける到着トラフィックのサブセットをサンプリングするだけでなく、大きな比率のトラフィックを送信するフローがより高頻度でサンプリングされるようにこのサブセットを選択する。このような選択的なサンプリングは２個のラン・サンプリングを用いて可能となる。連続する２つのサンプルが同じフローｆに属する場合、フローｆ∈Ｆが２個のランを有するように定められる。比較的僅かのパケットを生成するフロー・ソースが非常に低い確率でサンプリングされるので、２個のラン・サンプリングを用いて検出されるフロー・ソースのリストは比較的小さくなるかもしれない。このリストが小さいので、ＲＡＴＥの所与の実施は比較的高いメモリ効率を呈するかもしれない。
【００１７】
ＲＡＴＥは以下の情報を保持することによって２個のランを検出かつ測定する。２個のラン（検出）レジスタ（ＴＲＲ）は典型的には最後に受け取られたサンプルのフローＩＤである１つのフロー識別子（フローＩＤ）のみを保持する。現在のフローのサンプルのフローＩＤはレジスタ内容（値）と同じであり、次に２個のランが検出される。（以下に記載の）２個のラン・カウント・テーブルが更新され、ＴＲＲの値がヌルに設定される。現在のサンプルのフローＩＤがＴＲＲの値と異なる場合、ＴＲＲは現在のサンプルのフローＩＤに設定される。
【００１８】
２個のラン・カウント・テーブル（ＴＣＴ）は検出された２個のランを有していた各フローの２個のランの数のカウントを保持する。特定のフローについて２個のランが検出されたときに、そのフローがＴＣＴに含まれている場合、そのフローの２個のラン・カウントは１だけ増分される。２個のランが検出されたフローがＴＣＴに含まれていない場合、そのフローＩＤはＴＣＴに加えられ、そのカウントは１に初期化される。
【００１９】
本願明細書においては２個のラン・カウントについての実施形態を記載しているが、実施形態はそのように限定されるものではない。当業者であれば本願明細書の教示を、Ｎは２より大きい正の整数（例えば、３−ラン）であるＮ−ラン・カウントなどの、より長いランに拡大できる。したがって、本願明細書で用いられるように、ランという用語はそのような変形物のすべてを包含する。
【発明を実施するための最良の形態】
【００２０】
図１はフロー単位推定のＲＡＴＥ法の第１の例示的実施形態のフローチャートを示している。このＲＡＴＥ法は以下のような方法でフローｆに起因するトラフィックの比率を推定する。工程１０１では、所望の推定精度を信頼区間（誤差）パラメータβおよび確率αと仮定した場合、ＲＡＴＥ法はまずサンプルＴＲの数を決定する（上付き文字「Ｒ」はこれがＲＡＴＥ法に必要な間隔におけるサンプル数であることを示している）。工程１０２では、サンプリング間隔ＴＲ中に、ＲＡＴＥ法は各フローｆ∈Ｆに関する２個のランＮ２（ｆ）の数を測定する。工程１０３では、各フローｆに起因するトラフィックの比率がＮ２（ｆ）から推定される。
【００２１】
工程１０１および１０３に関し、標準正規分布についての以下の例はサンプリング間隔の生成方法およびサンプリング間隔中に２個のランの数からトラフィックの比率を推定する方法を示している。変数Ｎ２（ｆ）はサンプルＴＲ中のフローｆについての２個のランの数および関数
【数９】
2005348415.tif 000011
である。次に式（２）が当てはまる：
【数１０】
2005348415.tif 000012
したがって、推定値
【数１１】
2005348415.tif 000013
は式（３）で与えられるようになる：
【数１２】
2005348415.tif 000014
式（２）および（３）について、ｐ（ｆ）の分散σ（ｆ）（または、推定された比率
【数１３】
2005348415.tif 000015
が使用される場合には、その推定値
【数１４】
2005348415.tif 000016
）は式（４）で与えられるようになる：
【数１５】
2005348415.tif 000017
推定値
【数１６】
2005348415.tif 000018
のα−パーセント点の信頼区間は以下のように算出される：Ｚαが標準正規分布Ｎ［０，σ］のα−パーセント点を表す場合、ｐ（ｆ）の推定値についてのα−パーセント点の信頼区間は式（５）で与えられる：
【数１７】
2005348415.tif 000019
α−パーセント点の信頼区間がβより広くならない場合、ｐ（ｆ）のすべての値についてσ（ｆ）≦０．３４５となる。故に、信頼区間は式（６）の数量以下である：
【数１８】
2005348415.tif 000020
式（６）の数量はβ未満になるように設定され、この不等式をＴＲについて解いて、α−パーセント点の信頼区間がβ未満であるという目的を達成するためにサンプリングする時間の長さを決定する。最小のサンプリング時間
【数１９】
2005348415.tif 000021
は式（７）で与えられる：
【数２０】
2005348415.tif 000022
以下の説明に関し、フローＩＤ  ｉ（例えば、ｐ（ｉ）またはａ（ｉ））の関数である所与の変数「ν」について、記号νｉも使用され、これはν（ｉ）に等しい。
【００２２】
図２は図１の方法の例示的実施のブロック図を示している。工程２０１では、入力された信頼水準が入力された信頼区間幅βおよび誤差確率αとして定められる。工程２０２では、式（７）で与えられるようなサンプリング間隔ＴＲが算出され、Ｔはゼロに設定される。ここでＴは受け取られたサンプルの総数のカウンタである。工程２０３では、２個のラン・カウント・テーブルＴＣＴは空集合に初期化され、２個のラン・レジスタＴ２個のラン・レジスタＴＲＲはヌルに初期化される。
【００２３】
工程２０４では、到着の各々について反復プロセスが始まる。工程２０４では、現在の到着のフローＩＤ  ｉが検索され、Ｔが増分される。工程２０５では、テストがフローＩＤ  ｉがＴＲＲの値に等しいかどうかを決定する。工程２０５のテストがフローＩＤ  ｉＴＲＲの値に等しいと決定した場合、工程２０６においてＴＲＲがヌルに設定される。
【００２４】
工程２０７では、テストがｉがＴＣＴの成分であるかどうか（すなわち、フローＩＤ  ｉが現在２個のラン・カウント・テーブルＴＣＴ内のエントリであるかどうか）を決定する。工程２０７のテストがフローＩＤ  ｉがＴＣＴＹの成分ではないと決定した場合、工程２０８においてフローＩＤ  ｉがＴＣＴに加えられる。工程２０７のテストがフローＩＤ  ｉがＴＣＴの成分であると決定した場合、この方法は工程２０９に進む。工程２０９では、フローＩＤ  ｉについてのＴＣＴのカウント値が１だけ増分される。この方法は工程２０９から工程２１１に進む。
【００２５】
工程２０５のテストがフローＩＤ  ｉがＴＲＲの値に等しくないと決定した場合、工程２１０でＴＲＲの値は現在のフローＩＤ  ｉに設定される。この方法は工程２１０から工程２１１に進む。工程２１１では、この方法はサンプリング間隔ＴＲに達したかどうかを決定する。工程２１１のテストがサンプリング間隔ＴＲに達していないと決定した場合、この方法は次の到着のために工程２０４に戻る。
【００２６】
工程２１１のテストがサンプリング間隔ＴＲに達したと決定した場合、工程２１２では、各ｉに関して、この方法はノードに対するフローＩＤ  ｉのトラフィックの比率ｐｉの推定値
【数２１】
2005348415.tif 000023
を算出する。例示的な正規分布に関し、工程２１２では、この方法は式（３）に従って推定値
【数２２】
2005348415.tif 000024
を算出する。工程２１３では、各ｉに関して、この方法はノードに対するフローＩＤ  ｉのトラフィックの分散σｉの推定値
【数２３】
2005348415.tif 000025
を算出する。例示的な正規分布に関し、工程２１３では、この方法は式（４）に従って推定値
【数２４】
2005348415.tif 000026
を算出する。工程２１４では、各ｉに関して、この方法はフローＩＤ  ｉの信頼区間を算出する。例示的な正規分布に関し、工程２１４では、この方法は式（５）に従ってフローＩＤ  ｉの信頼区間を算出する。
【００２７】
第２の例示的実施形態によれば、加速されたＲＡＴＥ（ＡＣＣＥＬ−ＲＡＴＥ）と呼ばれるフロー単位のトラフィック推定の方法は、着信ストリームをｋ個のサブストリーム、すなわちバケットに均一にハッシュし、各バケットに割り当てられた各フローＩＤ  ｉについての２個のラン・カウントを保持する。このようなＡＣＣＥＬ−ＲＡＴＥ法は、例えばシミュレーションまたは実験を通してｋの値を適切に選択することによりＲＡＴＥ法の推定時間を短縮するかもしれない。図３はＡＣＣＥＬ−ＲＡＴＥ法によるパケット・ストリーム処理のブロック図を示している。
【００２８】
図３に示すように、ＡＣＣＥＬ−ＲＡＴＥ法のためのパケット・ストリーム処理は、ハッシュ関数を着信トラフィック・ストリームに適用するハッシング・モジュール３０１を含む。ハッシュ関数を着信トラフィック・ストリームに適用すれば、フローＩＤをサブストリームに割り当てることによってトラフィックは３０２（ｋ）を介してｋ個のサブストリーム３０２（１）に分割される。サブストリーム３０２（１）〜３０２（ｋ）の各々は対応する２個のラン・レジスタＴＲＲ３０３（ｊ）を有する。ここでは１≦ｊ≦ｋであり、該レジスタはＲＡＴＥ法について記載した様式と同様に動作する。２個のラン・カウント・テーブル（ＴＣＴ）３０４はフローＩＤの各々について検出された２個のラン事象のカウントを保持する。
【００２９】
着信トラフィック・ストリームを分割すれば以下の利点が得られる。サブストリームに関連する各フローはサブストリーム・トラフィック全体のより大きな断片を構成する。故に、２個のランを得る確率は、ＲＡＴＥ法の元の分割されていない着信トラフィック・ストリームの場合よりも高くなる。
【００３０】
着信ストリームのフローＩＤ（または恐らくはウイルス／ワーム検出のためのペイロード）が最初にハッシュされる。セットＦはあるフローの確率のセットであり、パケットはｆ∈ＦのフローＩＤｆを有し、ｈ（ｆ）はフローＩＤ「ｆ」をセット｛１、２、…、ｋ｝に割り当てるハッシュ関数を表す（すなわち、ハッシュ関数ｈ（ｆ）はフローＩＤ  ｆを有するパケットをサブストリーム（ｈ（ｆ））に送る）。所望のレベルの精度を得るためのサンプリング間隔にわたるパケットの数はＴＡによって与えられる。ここで上付き文字「Ａ」はＡＣＣＥＬ−ＲＡＴＥ法を表している。このサンプリング間隔ＴＡ中、ハッシュ関数はＴ［ｊ］パケットをサブストリームｊに割り当てる。故に、
【数２５】
2005348415.tif 000027
となる。サブストリームｊにわたる総トラフィックとトラフィックの総量との比率ｒ［ｊ］は式（８）により与えられる：
【数２６】
2005348415.tif 000028
変数φ（ｆ）はフローｆに属するサブストリーム（ｈ（ｆ））内のトラフィックの断片を表す。したがって、ノードに到着するフローｆに対するトラフィックの比率ｐ（ｆ）は式（９）によって与えられる：
【数２７】
2005348415.tif 000029
ＲＡＴＥ法について記載した様式と同様に、導かれかつ推定された比率、および該比率に対して導かれかつ推定された分散、およびフローｆに対するトラフィックの推定された比率の信頼区間は次のようになる。関係
【数２８】
2005348415.tif 000030
およびＴ［ｈ（ｆ）］パケットにおけるフローｆに対する２個のランの数であるＮ２（ｆ）を用いれば、式（１０）が当てはまる：
【数２９】
2005348415.tif 000031
故に、推定値
【数３０】
2005348415.tif 000032
は式（１１）で与えられるようになる：
【数３１】
2005348415.tif 000033
式（９）および（１０）に関し、ｐ（ｆ）の分散δ（ｆ）は式（１２）で与えられるようになる：
【数３２】
2005348415.tif 000034
推定された比率
【数３３】
2005348415.tif 000035
を用いる場合、推定された分散
【数３４】
2005348415.tif 000036
は式（１３）で与えられるようになる：
【数３５】
2005348415.tif 000037
推定値に対するα−パーセント点の信頼区間は次のように算出される：Ｚαが標準正規分布Ｎ［０，δ］のα−パーセント点を表す場合、ｐ（ｆ）の推定値に対するα−パーセント点の信頼区間は式（１４）で与えられる：
【数３６】
2005348415.tif 000038
ＲＡＴＥ法と異なり、ＡＣＣＥＬ−ＲＡＴＥ法のための（サンプリング間隔、サンプリング・サイズ、およびサンプリング周期のような）推定時間は動的に決定される。式（１４）のα−パーセント点の信頼区間によって与えられる例示的な正規分布に関し、α−パーセント点の信頼区間がβ以下の場合、
【数３７】
2005348415.tif 000039
および式（１５）が暗示される：
【数３８】
2005348415.tif 000040
上式はそれがハッシュされるサブストリームと無関係の任意のフローｆに当てはまる。ｒｍａｘを式（１６）のように定める：
ｒｍａｘ＝ｍａｘ１≦ｊ≦ｋｒ［ｈ（ｆ）＝ｊ］、ｊ＝１、２、…、ｋ    （１６）
式（１５）は式（１７）に書き換えられてよい：
【数３９】
2005348415.tif 000041
ハッシュ関数が均一である場合、ｒｍａｘ＝（１／ｋ）および式（１７）は式（１８）に書き換えられてよい：
【数４０】
2005348415.tif 000042
上式中
【数４１】
2005348415.tif 000043
である。
【００３１】
したがって、αおよびβを保持する最小のサンプリング間隔ＴＡはＴＡ＝ＴＲｒｍａｘになる。このサンプリング間隔はｒｍａｘに依存するため、ｒｍａｘはＡＣＣＥＬ−ＲＡＴＥ法によって動的に見付けられる。しかし、別の実施形態はＴｍａｘとして表される最大量のトラフィックを受け取るサブストリームを見付けてよい。ここで、ｒｍａｘ＝（Ｔｍａｘ／Ｔ）であり、Ｔは処理されたパケットの総数である。ＡＣＣＥＬ−ＲＡＴＥ法は第ｊ番目（１≦ｊ≦ｋ）のストリームにハッシュされたパケットの数Ｔ［ｊ］を見付ける。ＡＣＣＥＬ−ＲＡＴＥ法はこの変数をＴｍａｘをゼロに初期化しパケットが第ｉ番目のサブストリームにハッシュされる毎に、Ｔ［ｊ］を増分し、Ｔ［ｊ］をＴｍａｘと比較し、Ｔ［ｊ］がＴｍａｘよりも大きい場合にはＴｍａｘを増分する。次に、量
【数４２】
2005348415.tif 000044
が算出され、Ｔがこの量よりも大きい場合にはサンプリング間隔が完全なものとなる。
【００３２】
図４はＡＣＣＥＬ−ＲＡＴＥ法によるフロー単位推定の例示的実施形態を示している。工程４０１では、２個のラン・カウント・テーブル（ＴＣＴ）のエントリおよび２個のラン・レジスタＴＲＲ［ｊ］（１≦ｊ≦ｋ）はヌルに設定される。ｉ）サブストリームｊへの到着の数Ｔ［ｊ］、ｉｉ）処理されたパケットの総数Ｔ、およびｉｉｉ）任意の単一のサブストリームに送られたパケットの最大数Ｔｍａｘの変数は、ゼロに初期化される。
工程４０２では、現在の到着のフローＩＤ  ｆが１だけ増分される。工程４０３では、サブストリーム数ｈ（ｆ）を生成するためにハッシュ関数がｆに適用される。工程４０４では、値Ｔ［ｈ（ｆ）］は１だけ増分される。工程４０５では、テストがＴ［ｈ（ｆ）］がＴｍａｘよりも大きいかどうかを決定する。工程４０５のテストがＴ［ｈ（ｆ）］がＴｍａｘよりも大きいと決定した場合、工程４０６において、Ｔｍａｘは１だけ増分され、この方法は工程４０７に進む。工程４０５のテストがＴ［ｈ（ｆ）］がＴｍａｘ以下であると決定した場合、この方法は直接工程４０７に進む。
【００３３】
工程４０７では、テストが現在のパケットのフローＩＤ  ｆをＴＲＲ［ｈ（ｆ）］に格納された値と比較する。工程４０７のテストが現在のパケットのフローＩＤ  ｆがＴＲＲ［ｈ（ｆ）］に格納された値と等しいと決定すると、工程４０８において、ＴＲＲ［ｈ（ｆ）］はヌルに設定される。工程４０９では、テストがフローＩＤ  ｆがＴＣＴの成分かどうかを決定する。工程４０９のテストがフローＩＤ  ｆがＴＣＴの成分ではないと決定した場合、工程４１０において、フローＩＤ  ｆがＴＣＴに加えられ、これに対応するカウンタ（Ｎ２（ｆ））が初期化される。工程４１１では、この対応するカウンタ（Ｎ２（ｆ））は増分される。工程４０９のテストがフローＩＤ  ｆがＴＣＴの成分であると決定した場合、工程４１１において、これに対応するＴＣＴのカウンタ（Ｎ２（ｆ））が１だけ増分される。この方法は工程４１１から工程４１３に進む。
【００３４】
工程４０７のテストが現在のパケットのフローＩＤ  ｆがＴＲＲ［ｈ（ｆ）］に格納された値と等しくないと決定した場合、工程４１２において、ＴＲＲ［ｈ（ｆ）］はフローＩＤ  ｆに設定される。この方法は工程４１２から工程４１３に進む。
工程４１３では、量
【数４３】
2005348415.tif 000045
が算出される。工程４１４では、テストがＴが
【数４４】
2005348415.tif 000046
未満かどうかを決定する。工程４１４のテストがＴが
【数４５】
2005348415.tif 000047
未満であると決定した場合、次のパケット到着のためにこの方法は工程４０２に戻る。工程４１４のテストがＴが
【数４６】
2005348415.tif 000048
未満ではないと決定した場合、この方法はサンプリングを終了する。
【００３５】
工程４１５では、この方法は各サブストリームについて、ｒ［ｈ（ｆ）］＝Ｔ［ｈ（ｆ）］／Ｔを算出する。工程４１６では、この方法は各フローｆについて、フローｆに対するトラフィックの推定された比率
【数４７】
2005348415.tif 000049
、
【数４８】
2005348415.tif 000050
の推定された分散
【数４９】
2005348415.tif 000051
、およびその推定のための信頼区間を算出する。いくつかの実施形態に関し、この方法は工程４１６において式（１１）、（１３）、および（１４）の関係を用いてよい。
【００３６】
１つまたは複数の実施形態によるフロー単位のトラフィック推定は、以下の利点を提供するかもしれない。ノードにおけるフローに対するトラフィックの比率を推定することにより、比較的大きなメモリを必要とすることなく、比較的高速の推定時間が可能となる。また、ウイルス／ワーム検出の増強、または公正さをキューするためのトラフィック工学の介入および不正なフローの分離を可能にしながらトラフィックの一時的な速い増大が追跡されるかもしれない。
【００３７】
本発明は、ネットワーク・コントローラ、ルータ、またはコンピュータなどのプロセッサ内で具現化されてよく、本願明細書に記載の方法によって用いられるネットワーク情報を受け取るために該プロセッサはネットワークまたはネットワーク・データベースに結合されてよい。また、本発明は有線、無線、光、または非光ネットワークのために使用されてよく、同期または非同期ネットワークのいずれかのために使用されてよい。
【００３８】
当業者には明白であるように、フロー単位のトラフィック推定の種々の機能は回路要素に対して実施されてよいか、またはソフトウェア・プログラムにおける処理工程としてのデジタル・ドメインにおいて実施されてもよい。このようなソフトウェアは、例えば、デジタル信号プロセッサ、マイクロコントローラ、または汎用コンピュータにおいて使用されてよい。したがって、フロー単位のトラフィック推定の種々の機能は、プロセッサの種々のモジュールとして実施され、各モジュールが当該分野で知られている任意の数の実施形態で具現化されてよい。
【００３９】
本発明はそれらの方法を実施するための方法および装置の形態で具現化され得る。本発明はまた、フロッピー（登録商標）・ディスク、ＣＤ−ＲＯＭ、ハード・ディスク・ドライブ、または他の機械判読可能な記憶媒体などの具体的な媒体においてプログラム・コードの形態で具現化され得る。この場合、プログラム・コードがコンピュータなどのマシンによってロードかつ実行されるとき、このマシンは本発明を実施する装置となる。本発明はまた、例えば、記憶媒体に格納されたか、マシンによってロードかつ／または実行されるか、あるいは、光ファイバを介するか、または電磁放射を介して電線またはケーブルなどのいくつかの伝送媒体上で送信されるかに関係なく、プログラム・コードの形態で具現化され得る。この場合、プログラム・コードがコンピュータなどのマシンによってロードかつ実行されるとき、このマシンは本発明を実施する装置となる。汎用プロセッサ上で実施されるとき、このプログラム・コードのセグメントはプロセットと組み合わされて、特定の論理回路と同様に動作する固有のデバイスを提供する。
【００４０】
本発明の性質を説明するために記載かつ示してきたパーツの詳細、材料、および構成の変更が、添付の特許請求の範囲に明示したような本発明の原理および範囲から逸脱することなく当業者によってなされてよいことがさらに理解されよう。
【図面の簡単な説明】
【００４１】
【図１】フロー単位推定の第１の例示的実施形態を示すフローチャートである。
【図２】図１のフロー単位推定の例示的実施を示すブロック図である。
【図３】フロー単位推定の第２の例示的実施形態のパケット・ストリーム処理を示すフローチャートである。
【図４】第２の例示的実施形態のフロー単位推定の例示的実施を示すブロック図である。
【図１】
2005348415.tif 000055
【図２】
2005348415.tif 000056
【図３】
2005348415.tif 000057
【図４】
2005348415.tif 000058