(57)【特許請求の範囲】
【請求項１】
パケット通信ネットワークの１つ又は複数のノードで１つ又は複数のプロセッサで実行される、前記パケット通信ネットワーク内のトラヒックの解析を実行する方法であって、
前記パケット通信ネットワーク内の選択されたノードから、パケット・セットのメンバーシップの決定に基づいて、複数のトラヒック・ダイジェストベースの集合体を抽出する工程であって、前記複数のトラヒック・ダイジェストは複数のローカル・トラヒック・ダイジェスト及び複数のリモート・トラヒック・ダイジェストを含み、前記トラヒック・ダイジェストの各々はパケット・セットＬｉ，ｊの情報を要約して複数のＯ（ｌｏｇｌｏｇＮｍａｘ）のビットであり、前記Ｎｍａｘは、Ｌｉ，ｊ内の個別サンプルの最大数である工程と、
前記パケット通信ネットワーク内の前記選択されたノードのいくつかに、複数の関連するローカル・トラヒック・ダイジェストを分散する工程と、
前記パケット通信ネットワーク内の前記選択されたノードのいくつかから、複数の関連するリモート・トラヒック・ダイジェストを受信する工程と、
前記ローカル・トラヒック・ダイジェストと前記リモート・トラヒック・ダイジェストに基づいてローカル・トラヒック・フローの推定を発生して、前記選択されたノードのいくつかに前記発生したローカル・トラヒック・フローの推定を提供する工程と、
前記選択されたノードのいくつかから、リモート・トラヒック・フローの推定を受信する工程と、
前記ローカル・トラヒック・フローの推定及び前記リモート・トラヒック・フローの推定に基づいて、前記パケット通信ネットワークの測定されるべきパラメータの一連の交差セット濃度決定問題としてトラヒック測定の解析を定式化する工程と、
前記一連の交差セット濃度決定問題を解く工程とを含む方法。
【請求項２】
前記トラヒック・ダイジェストは、標準のルーティングプロトコルの制御メッセージ内のオペイク・データ・オブジェクトとして通信される、請求項１に記載の方法。
【請求項３】
前記ルーティングプロトコルは、オープン・ショーテスト・パス・ファースト（ＯＳＰＦ）である、請求項２に記載の方法。
【請求項４】
前記制御メッセージはリンク状態の制御メッセージである、請求項２又は３に記載の方法。
【請求項５】
前記制御メッセージはインターナル・ボーダ・ゲートウェイ・プロトコル（Ｉ−ＢＧＰ）制御メッセージである、請求項２乃至４のいずれかに記載の方法。
【請求項６】
前記交差セット濃度決定問題を一連の連合セット濃度決定問題に定式化する工程をさらに含む、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記連合セット濃度決定問題を分散方式で解くために、１つまたは複数のＯ（ｌｏｇｌｏｇ｜Ａ｜）個別サンプル計量アルゴリズムを適用する工程をさらに含む、請求項６に記載の方法。
【請求項８】
前記トラヒックの解析は、トラヒック経路パターンの解析、トラヒック・フロー・パターンの解析、並びに起点、終点及び与えられた関心のあるパケットのグループが移動する中間のノードとリンクを追跡することからなるグループから選択される、請求項１乃至７のいずれかに記載の方法。
【請求項９】
前記トラヒック・ダイジェストを抽出する工程が、
ある特定のパケット・セットに属する各々のパケットから、パケット識別子を抽出する工程と、
Ｒｍａｘビットのハッシュ出力を受信するために、各々のパケット識別子をハッシュ関数に入力し、前記Ｒｍａｘビットのハッシュ出力のｌｏｇ２ｍビットがバケット指標を決定するために用いられる工程と、
前記バケット指標に基づいて前記ハッシュ出力をｍのバケットに分割する工程と、
前記ｍのバケットの各バケットｉについて、ｒ（）を用いることによって、ｉ番目のバケットに割り当てられたすべてのハッシュ出力ｈ（ＰＩＤ）の最初の（Ｒｍａｘ−ｌｏｇ２ｍ）ビットにおける連続する先行ゼロの最大数たる、Ｒｉを追跡する工程と、
前記特定されたパケット・セットに対するトラヒック・ダイジェストとして、Ｒ１からＲｍを用いる工程とを含む、請求項１乃至８のいずれかに記載の方法。
【請求項１０】
請求項１乃至９のいずれかに記載の方法を実行するように構成された装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は一般に通信ネットワークに関し、特に通信ネットワークのデータ・パケットの測定と解析に関する。
【背景技術】
【０００２】
本出願は、２００４年３月３１日に出願され、本出願に参考として添付された出願番号第６０／５５８２３０号の仮出願の優先権を主張する。
近年世界は、高速データ・ネットワークの急増およびこれらのネットワークをサポートするプロトコル／サービスの組の急速な拡張を目撃している。ネットワークの監視およびトラヒック測定の技術の進展は、これまでのところこれらのネットワークの膨大な発展と共にその動作速度に追いついていない。この欠点のために、ネットワークのオペレータはこれらのネットワークで何が起こっているか正確に把握することがずっとできないでいる。これはしたがって、ネットワークを適切かつ効率的に動作させ管理する能力を危うくしている。大規模高速ネットワークに対する、包括的で展開可能なネットワークの監視および端末間のトラヒック解析の、インフラストラクチャの緊急な必要性が生じている。そのようなインフラストラクチュアは、通信フローの経路が異なる型式の、予期できるまたは予期できないイベントのためにセッションの途中で動的かつ予測不可能に変更される、インターネットのような無接続データ・ネットワークについて特に重要である。そのようなイベントは、ネットワーク要素の故障、非決定論的負荷平衡スキーム（例えば等費用多重経路（ＥＣＭＰ））、ソフトウェア／ハードウェアのバグ、プロトコルの誤構成を含む。現在のところ、多くのネットワーク・オペレータは、ネットワーク内の個々の通信フローの端末から端末までの経路のまったく不適切なサンプリングを得る、「トレースルート」のような原始的な診断ツールにのみ頼らざるを得ない。
【０００３】
トラヒック測定／解析の方法論およびインフラストラクチュアの最近の研究は、大規模ＩＳＰ用の起点−終点（ＯＤペア）トラヒック・マトリックス推定や、欺瞞ＤＤｏＳの攻撃と取り組むためのＩＰ−ベースのネットワークにおける、トレース・バックサービスのサポートのような、多数の重要な実生活のアプリケーションの要求により強く駆動されてきた。Ａ．Ｍｅｄｉｎａ、Ｎ．Ｔａｆｔ、Ｋ．Ｓａｌａｍａｔｉａｎ、Ｓ．Ｂｈａｔｔａｃｈａｒｙｙａ、Ｃ．Ｄｉｏｔ、「Ｔｒａｆｆｉｃ  Ｍａｔｒｉｘ  ｅｓｔｉｍａｔｉｏｎ：Ｅｘｉｓｔｉｎｇ  Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  ｎｅｗ  ｄｉｒｅｃｔｉｏｎｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００２年８月［Ｍｅｄｉ  ０２］、Ｙ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈａｎ、Ｎ．Ｄｕｆｆｉｅｌｄ、Ａ．Ｇｒｅｅｎｂｅｒｇ、「Ｆａｓｔ  Ａｃｃｕｒａｔｅ  Ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  Ｌａｒｇｅ−Ｓｃａｌｅ  ＩＰ  Ｔｒａｆｆｉｃ  Ｍａｔｒｉｃｅｓ  ｆｒｏｍ  Ｌｉｎｋ  Ｌｏａｄｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｍｅｔｒｉｃｓ、２００３年６月［Ｚｈａｎｇ  ０３ａ］およびＹ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈ、Ｃ．Ｌｕｎｄ、Ｄ．Ｄｏｎｏｈｏ、「Ａｎ  Ｉｎｆｏｒｍａｔｉｏｎ−Ｔｈｅｏｒｅｔｉｃ  Ａｐｐｒｏａｃｈ  ｉｎ  Ｔｒａｆｆｉｃ  Ｍａｔｒｉｘ  Ｅｓｔｉｍａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００３年８月［Ｚｈａｎｇ  ０３ｂ］で論じられたトラヒック・マトリックス推定問題では、その目的は大規模ＩＰネットワークのＯ−Ｄノード・ペアの間のトラヒック要求を、リンク−ロード測定のみを用いて推定することである。この問題の起源は、マーケットの最も営利的なギガビット・ルータによる、安価なスケーラブル・パーフロー・カウンタのサポートがないことから来ている。例えば、シスコネット・フロー・テクノロジー、シスコ、ＩＯＳネット・フローｈｔｔｐ：／／ｗｗｗ．ｃｉｓｃｏ．ｃｏｍ／ｗａｒｐ／ｐｕｂｌｉｃ／７３２／Ｔｅｃｈ／ｎｍｐ／ｎｅｔｆｌｏｗ／ｉｎｄｅｘ．ｓｈｔｍｌは、精密なパーフロー・トラヒック統計を集めるのに使用できる一方で、その恐ろしい記録および帯域幅の要求は、１０Ｇｂｐｓのネットワークでの使用を不適当にする。測定インフラストラクチュアにおけるそのような不適切／欠陥と取り組むために、必要とされるＯ−Ｄペア・トラヒック・マトリックスを推定するために、研究者はリンク−ロード測定をＯ−Ｄペア・トラヒック分布の追加の仮定と組合せる手段を用いてきた。例えば、［Ｍｅｄｉ  ０２、Ｚｈａｎｇ  ０３ａ、Ｚｈａｎｇ  ０３ｂ］では、重力モデルの異なる変異体が、すべてのＯ−Ｄペアの間のネットワーク・トラヒック分布をモデル化するために、輸送分野から適用されており、［Ｖａｒｄ  ９６］Ｙ．Ｖａｒｄｉ、「Ｎｅｔｗｏｒｋ  Ｔｏｍｏｇｒａｐｈｙ：ｅｓｔｉｍａｔｉｎｇ  ｓｏｕｒｃｅ−ｄｅｓｔｉｎａｔｉｏｎ  ｔｒａｆｆｉｃ  ｉｎｔｅｎｓｉｔｉｅｓ  ｆｒｏｍ  ｌｉｎｋ  ｄａｔａ」、Ｊｏｕｒｎａｌ  ｏｆ  Ａｍｅｒｉｃａｎ  Ｓｔａｔｉｓｔｉｃｓ  Ａｓｓｏｃｉａｔｉｏｎ、９１、ｐｐ．３６５−３７７、１９９６年、［Ｖａｒｄ  ９５］では、２次のリンク−ロード統計をＯ−Ｄペア・トラヒック分布と��連づけるためにポアソン仮定が用いられている。同様のガウス仮定が、Ｊ．Ｃａｏ、Ｄ．Ｄａｖｉｓ、Ｓ．Ｖ．Ｗｉｅｌ、Ｂ．Ｙｕ、「Ｔｉｍｅ−ｖａｒｙｉｎｇ  ｎｅｔｗｏｒｋ  ｔｏｍｏｇｒａｐｈｙ」、Ｊｏｕｒｎａｌ  ｏｆ  Ａｍｅｒｉｃａｎ  Ｓｔａｔｉｓｔｉｃｓ  Ａｓｓｏｃｉａｔｉｏｎ、９５、ｐｐ．１０６３−１０７５、２０００年［Ｃａｏ  ００］でなされている。実のところ、リンク−ロード測定のみで与えられるＯ−Ｄトラヒック・マトリックス推定の問題は、「ネットワーク・トモグラフィ」と呼ばれる新しいフィールド・リサーチの形成につながっていた。不幸なことに現在までに提案されたネットワーク・トモグラフィベースのほとんどの解は、それらのトラヒック分布の仮定の有効性に関して高度に敏感であり、すなわち頑丈でなかった。このトモグラフィベースのアプローチはまた、それから測定／構成情報が抽出されて対照される、多重動作データベースの間の正確性、同期および一貫性に強く依存する。（そのようなデータベースは、リンク−ロード用のＳＮＭＰＭＩＢと同様に、ルータのフォワーディング・テーブル、ルータ構成ファイルを含む。）上記のモデル化と動作の仮定はまた、トモグラフィベースのトラヒック測定／推定のスキームを、ネットワーク要素／データベースの適切な機能もトラヒック分布の正規性も仮定されないネットワーク故障検出／診断に対して、ほとんど役に立たないものにならしめる。
【０００４】
最近、代案のパケット・トラジェクトリ・ベーストラヒック監視／解析アプローチが、Ｎ．Ｇ．Ｄｕｆｆｉｅｌｄ、Ｍ．Ｇｒｏｓｓｇｌａｕｓｅｒ、「Ｔｒａｊｅｃｔｏｒｙ  Ｓａｍｐｌｉｎｇ  ｆｏｒ  Ｄｉｒｅｃｔ  Ｔｒａｆｆｉｃ  Ｏｂｓｅｒｖａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２０００年８月、ｐｐ．２７１−２８２［Ｄｕｆｆ  ００］およびＡ．Ｃ．Ｓｎｏｅｒｅｎ、Ｃ．Ｐａｒｔｒｉｄｇｅ、Ｌ．Ａ．Ｓａｎｃｈｅｚ、Ｃ．Ｅ．Ｊｏｎｅｓ、Ｆ．Ｔｃｈａｋｏｕｎｔｉｏ、Ｓ．Ｔ．Ｋｅｎｔ、Ｗ．Ｔ．Ｓｔｒａｙｅｒ、「Ｈａｓｈ−ｂａｓｅｄ  ＩＰ  Ｔｒａｃｅｂａｃｋ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００１年８月、ｐｇ３−１４［Ｓｎｏｅ  ０１］により提案され、それらでは各々のノード（ルータ）が最近取り扱ったすべてのパケットの圧縮された要約またはダイジェストを保持する。［Ｄｕｆｆ  ００］、［Ｓｎｏｅ  ０１］の双方で、ダイジェストはブルーム・フィルタの形式である。例えばＢ．Ｂｌｏｏｍ、「Ｓｐａｃｅ／Ｔｉｍｅ  ｔｒａｄｅ−ｏｆｆｓ  ｉｎ  ｈａｓｈ  ｃｏｄｉｎｇ  ｗｉｔｈ  ａｌｌｏｗａｂｌｅ  ｅｒｒｏｒｓ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ  １３、１９７０年７月１３日ｐｐ．４２２−４２６［Ｂｌｏｏ  ７０］およびＡ．Ｂｒｏｄｅｒ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｎｅｔｗｏｒｋ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒｓ：Ａ  Ｓｕｒｖｅｙ」、Ａｌｌｅｒｔｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、２００２、ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｓ．ｈａｒｖａｒｄ．ｅｄｕ／〜ｍｉｃｈａｅｌｍで入手可能、［Ｂｒｏｄ  ０２］では、ノードに到着するすべてのパケットを更新し、文書記録の目的と同様に、将来のオフラインのトラヒック解析をサポートするために、中央のサーバに周期的にアップロードする。これらの大変有用なノード・トラヒック・ダイジェストで武装して、中央サーバはトラヒック・フロー・パターンとネットワーク・レベルのフロー毎／商品測定を構築できるばかりではなく、（近い）過去にネットワークを通った任意の与えられたパケットの、端末から端末までの経路、またはいわゆるトラジェクトリについての質問に答えることもできる。任意の与えられた個々のパケットに対するトラジェクトリの質問に回答できる能力には、多大な費用がかかる。すべての個々の到来するパケットの十分な情報を記録するために、ブルーム・フィルタは十分大きくなければならない。効率的なメモリ対ブルーム・フィルタの偽陽性トレードオフを備えていても、高い蓋然性でＮの異なるパケットの署名を捕らえて正しく区別するために、Ｏ（Ｎ）ビットのメモリを必要とする。［Ｓｎｏｅ  ０１］では、そのようなシステムは、記憶装置内に単位時間当たりノードのリンク能力の約０．５％を必要とすると見積もっている。１０Ｇｂｐｓのリンクでは、これは監視時間の１秒毎に５０Ｍビットの記憶と換算される。そのような重量級のトラヒック・ダイジェストのアプローチは、システムのメモリ記録と通信の要求にストレスを与えるばかりでなく、リンク速度および／または監視期間の増加として悪い方向に作用する。
【特許文献１】米国仮出願第６０／５５８２３０号
【非特許文献１】Ａ．Ｍｅｄｉｎａ、Ｎ．Ｔａｆｔ、Ｋ．Ｓａｌａｍａｔｉａｎ、Ｓ．Ｂｈａｔｔａｃｈａｒｙｙａ、Ｃ．Ｄｉｏｔ、「Ｔｒａｆｆｉｃ  Ｍａｔｒｉｘ  ｅｓｔｉｍａｔｉｏｎ：Ｅｘｉｓｔｉｎｇ  Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  ｎｅｗ  ｄｉｒｅｃｔｉｏｎｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００２年８月［Ｍｅｄｉ  ０２］
【非特許文献２】Ｙ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈａｎ、Ｎ．Ｄｕｆｆｉｅｌｄ、Ａ．Ｇｒｅｅｎｂｅｒｇ、「Ｆａｓｔ  Ａｃｃｕｒａｔｅ  Ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  Ｌａｒｇｅ−Ｓｃａｌｅ  ＩＰ  Ｔｒａｆｆｉｃ  Ｍａｔｒｉｃｅｓ  ｆｒｏｍ  Ｌｉｎｋ  Ｌｏａｄｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｍｅｔｒｉｃｓ、２００３年６月［Ｚｈａｎｇ  ０３ａ］
【非特許文献３】Ｙ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈ、Ｃ．Ｌｕｎｄ、Ｄ．Ｄｏｎｏｈｏ、「Ａｎ  Ｉｎｆｏｒｍａｔｉｏｎ−Ｔｈｅｏｒｅｔｉｃ  Ａｐｐｒｏａｃｈ  ｉｎ  Ｔｒａｆｆｉｃ  Ｍａｔｒｉｘ  Ｅｓｔｉｍａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００３年８月［Ｚｈａｎｇ  ０３ｂ］
【非特許文献４】［Ｖａｒｄ  ９６］Ｙ．Ｖａｒｄｉ、「Ｎｅｔｗｏｒｋ  Ｔｏｍｏｇｒａｐｈｙ：ｅｓｔｉｍａｔｉｎｇ  ｓｏｕｒｃｅ−ｄｅｓｔｉｎａｔｉｏｎ  ｔｒａｆｆｉｃ  ｉｎｔｅｎｓｉｔｉｅｓ  ｆｒｏｍ  ｌｉｎｋ  ｄａｔａ」、Ｊｏｕｒｎａｌ  ｏｆ  Ａｍｅｒｉｃａｎ  Ｓｔａｔｉｓｔｉｃｓ  Ａｓｓｏｃｉａｔｉｏｎ、９１、ｐｐ．３６５−３７７、１９９６年、［Ｖａｒｄ  ９５］
【非特許文献５】Ｊ．Ｃａｏ、Ｄ．Ｄａｖｉｓ、Ｓ．Ｖ．Ｗｉｅｌ、Ｂ．Ｙｕ、「Ｔｉｍｅ−ｖａｒｙｉｎｇ  ｎｅｔｗｏｒｋ  ｔｏｍｏｇｒａｐｈｙ」、Ｊｏｕｒｎａｌ  ｏｆ  Ａｍｅｒｉｃａｎ  Ｓｔａｔｉｓｔｉｃｓ  Ａｓｓｏｃｉａｔｉｏｎ、９５、ｐｐ．１０６３−１０７５、２０００年［Ｃａｏ  ００］
【非特許文献６】Ｎ．Ｇ．Ｄｕｆｆｉｅｌｄ、Ｍ．Ｇｒｏｓｓｇｌａｕｓｅｒ、「Ｔｒａｊｅｃｔｏｒｙ  Ｓａｍｐｌｉｎｇ  ｆｏｒ  Ｄｉｒｅｃｔ  Ｔｒａｆｆｉｃ  Ｏｂｓｅｒｖａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２０００年８月、ｐｐ．２７１−２８２［Ｄｕｆｆ  ００］
【非特許文献７】Ａ．Ｃ．Ｓｎｏｅｒｅｎ、Ｃ．Ｐａｒｔｒｉｄｇｅ、Ｌ．Ａ．Ｓａｎｃｈｅｚ、Ｃ．Ｅ．Ｊｏｎｅｓ、Ｆ．Ｔｃｈａｋｏｕｎｔｉｏ、Ｓ．Ｔ．Ｋｅｎｔ、Ｗ．Ｔ．Ｓｔｒａｙｅｒ、「Ｈａｓｈ−ｂａｓｅｄ  ＩＰ  Ｔｒａｃｅｂａｃｋ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００１年８月、ｐｇ３−１４［Ｓｎｏｅ  ０１］
【非特許文献８】Ｂ．Ｂｌｏｏｍ、「Ｓｐａｃｅ／Ｔｉｍｅ  ｔｒａｄｅ−ｏｆｆｓ  ｉｎ  ｈａｓｈ  ｃｏｄｉｎｇ  ｗｉｔｈ  ａｌｌｏｗａｂｌｅ  ｅｒｒｏｒｓ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ  １３、１９７０年７月１３日ｐｐ．４２２−４２６［Ｂｌｏｏ  ７０］
【非特許文献９】Ａ．Ｂｒｏｄｅｒ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｎｅｔｗｏｒｋ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒｓ：Ａ  Ｓｕｒｖｅｙ」、Ａｌｌｅｒｔｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、２００２、ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｓ．ｈａｒｖａｒｄ．ｅｄｕ／〜ｍｉｃｈａｅｌｍで入手可能、［Ｂｒｏｄ  ０２］
【非特許文献１０】Ａ．Ｂｒｏｄｅｒ、「Ｏｎ  ｔｈｅ  ｒｅｓｅｍｂｌａｎｃｅ  ａｎｄ  ｃｏｎｔａｉｎｍｅｎｔ  ｏｆ  ｄｏｃｕｍｅｎｔｓ」、Ｃｏｍｐｒｅｓｓｉｏｎ  ａｎｄ  Ｃｏｍｐｌｅｘｉｔｙ  ｏｆ  Ｓｅｑｕｅｎｃｅｓ（ＳＥＱＵＥＮＣＥＳ）、Ｐｏｓｉｔａｎｏ、Ｉｔａｌｙ、９７年６月［Ｂｒｏｄ  ９７］
【非特許文献１１】Ｊ．Ｂｙｅｒｓ、Ｊ．Ｃｏｎｓｉｄｉｎｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、Ｓ．Ｒｏｓｔ、「Ｉｎｆｏｒｍｅｄ  Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ａｃｒｏｓｓ  Ａｄａｐｔｉｖｅ  Ｏｖｅｒｌａｙ  Ｎｅｔｗｏｒｋｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００２年８月［Ｂｙｅｒ  ０２］。
【非特許文献１２】Ａ．Ｂｒｏｄｅｒ、Ｍ．Ｃｈａｒｉｋａｒ、Ａ．Ｍ．Ｆｒｉｅｚｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｍｉｎ−ｗｉｓｅ  ｉｎｄｅｐｅｎｄｅｎｔ  ｐｅｒｍｕｔａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｃｉｅｎｃｅｓ、６０（３）、２０００、ｐｐ．６３０−６５９．［Ｂｒｏｄ  ００］
【非特許文献１３】Ｐ．Ｆｌａｊｏｌｅｔ、Ｇ．Ｎ．Ｍａｒｔｉｎ、「Ｐｒｏｂａｂｌｉｓｔｉｃ  ｃｏｕｎｔｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｄａｔａｂａｓｅ  ａｐｐｌｉｃａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｃｉｅｎｃｅｓ、３１（２）、１９８５、ｐｐ．１８２−２０９［Ｆｌａｊ  ８５］
【非特許文献１４】Ｍ．Ｄｕｒａｎｄ、Ｐ．Ｆｌａｊｏｌｅｔ、「Ｌｏｇｌｏｇ  Ｃｏｕｎｔｉｎｇ  ｏｆ  Ｌａｒｇｅ  Ｃａｒｄｉｎａｌｉｔｉｅｓ」、ｓｕｂｍｉｔｔｅｄ  ｔｏ  Ｅｕｒｏｐｅａｎ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ａｌｇｏｒｉｔｈｍｓ、ＥＳＡ’２００３、２００３年４月［Ｄｕｒａ  ０３］
【非特許文献１５】Ｃ．Ｅｓｔａｎ、Ｇ．Ｖａｒｇｈｅｓｅ、Ｍ．Ｆｉｓｋ、「Ｃｏｕｎｔｉｎｇ  ｔｈｅ  ｎｕｍｂｅｒ  ｏｆ  ａｃｔｉｖｅ  ｆｌｏｗｓ  ｏｎ  ａ  ｈｉｇｈ  ｓｐｅｅｄ  ｌｉｎｋ」、ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ、３２巻３号２００２年３月［Ｅｓｔａ  ０２］
【非特許文献１６】Ｐ．Ｂ．Ｇｉｂｂｏｎｓ、Ｓ．Ｔｉｒｔｈａｐｕｒａ、「Ｅｓｔｉｍａｔｉｎｇ  Ｓｉｍｐｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｏｎ  ｔｈｅ  Ｕｎｉｏｎ  ｏｆ  Ｄａｔａ  Ｓｔｒｅａｍｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  ＳＰＡＡ、Ｃｒｅｔｅ  Ｉｓｌａｎｄ、Ｇｒｅｅｃｅ、２００１［Ｇｉｂｂ  ０１］
【発明の開示】
【課題を解決するための手段】
【０００５】
従来技術での進歩は、軽量トラヒック・ダイジェスト経由のトラヒック解析の分散構造（ＤＡＴＡＬＩＴＥ）と名付けられた、ネットワーク・トラヒック解析の効率的方法を通して達成され、大規模１０Ｇｂｐｓ＋パケット切り替えネットワークの、一般的なトラヒック測定および解析（ＴＭＡ）機能をサポートする、新しい分散アルゴリズムおよびプロトコルの組を導入する。これらの機能は、以下を含むがそれに限定はされない：
・トラヒック・フロー・パターン／経路監視、診断およびネットワーク維持；
・容量計画およびトラヒック工学目的の起点−終点（ＯＤ）トラヒック負荷マトリックスの推定；
・インターＩＳＰ（ＡＳｅｓ）料金支払およびエンドユーザ精算／課金目的のトラヒック測定；
・分散サービス妨害（ＤＤｏＳ）攻撃の攻撃パケットの発信地のトレース・バック
【０００６】
ネットワーク中のトラヒック測定／解析問題を、一連のセット濃度決定（ＳＣＤ）問題として、定式化する。蓋然的で明解なサンプル集計技術の最近の進歩をてこに使って、セット濃度にしたがってネットワーク中の関心あるトラヒック測定が、ネットワーク・ノードすなわちルータの間の極度に軽量なトラヒック・ダイジェスト（ＴＤ）の交換を経由して、分散の方法で計算されることができる。ＮのパケットのＴＤは、メモリ記憶のＯ（ｌｏｇｌｏｇＮ）ビットのみを必要とする。そのようなＯ（ｌｏｇｌｏｇＮ）サイズのＴＤの演算は、ワイヤ速度１０Ｇｂｐｓおよびそれ以上の効率的なハードウェアの具体化に従順である。
【０００７】
サイズの小さいＴＤを与えると、ＯＳＰＦリンク状態パケット（ＬＳＰｓ）またはＩ−ＢＧＰ制御メッセージのような、既存の制御メッセージ内部のオペイク・データ・オブジェクトとしてそれらをピギーバックすることにより、ノードのＴＤをドメイン内のすべてのルータに分散することができる。一度必要なＴＤが受信されると、一連のセット濃度決定問題を解くことにより、そのローカル・リンクの各々の関心のあるトラヒック測定を、ルータは推定することができる。我々が後に論じるように、関心のあるトラヒック測定は一般的にリンク毎、トラヒックが集まったパケット・カウント（またはフロー・カウント）毎の形式であり、ここでトラヒックの集まりは同じ起点および／または終点ノード（またはリンク）および／または同じ中間ノード（またはリンク）を共有する、パケットのグループにより定義される。ローカルな測定結果は次にドメイン内に分散され、したがって各々のルータが異なるトラヒック・コモデティの経路／フロー・パターンのネットワーク・レベルの概観を構築することができるが、ここでコモデティは同じ起点および／または終点のノードまたはリンクを共有するパケットのグループにより定義される。初期のネットワーク・レベルのトラヒック測定が受信された後は、ネットワーク・レベルのコモデティ・フロー節約制約に基づいて、ローカルに最少二乗誤差（ＭＳＥ）最適化を実行することにより、各々のルータは関連する測定／推定誤差をさらに削減することができる。
【０００８】
ネットワークが周期的に軽量ＴＤで溢れさせられ、結果としてローカル・トラヒックを推定する「放送」モードのサポートに加えて、ＴＤの分散とローカル・トラヒックの推定がオンデマンドかつ関係者のみに知らせる原則で、ネットワーク内の関連したノードの部分集合により、実行される「質問と回答」モードを経由して、ＤＡＴＡＬＩＴＥはトラヒック測定／解析を同様にサポートする。「質問と回答」モードは、超精細で高分解能のトラヒック測定／解析が必要である、臨時で特別なトラヒック調査をサポートするために特に有用である。
【０００９】
要約すると、直接測定アプローチをとることにより、ＤＡＴＡＬＩＴＥは無効なトラヒック・モデルや、ネットワーク・トモグラフィ・アプローチを悩ます動作上の仮定に起因する問題を避ける。ＤＡＴＡＬＩＴＥスキームと現存するトラジェクトリ・ベースのそれの間にいくつかの高度な共通性があるにもかかわらず、それらの間にはキーとなる差異がある：第１にトラヒック測定問題を一連のセット濃度決定問題として定式化することにより、最少の通信負荷でトラヒック解析を分散方式で実行するために、明解なサンプル集計技術の最近の進歩を、てこにすることができる。第２に、個々のパケット１つの代わりにトラヒック集合体の振る舞いの測定と解析に焦点を合わせることにより、ＤＡＴＡＬＩＴＥのためのシステム・メモリと通信帯域幅の要求が大いに削減された。結果的に、現存するトラジェクトリ・ベースのシステムにより採用される重量級の中央化アプローチとは反対に、ＤＡＴＡＬＩＴＥは分散演算モデルを取り入れることが可能になる。
【発明を実施するための最良の形態】
【００１０】
本発明のより完全な理解は、図面と共にする以下の詳細は発明の記述の考察から得られる。図では同様の参照番号は同様の要素を表す。
本発明は、データ・パケット・ネットワークのネットワーク測定および解析の改良された効率を提供する方法論である。本発明の例としての実施形態が従来の高速度ネットワークと組合せて記載されるが、無線ネットワークや輸送ネットワークのような、他のネットワークにも適用可能であることが、当業者には自明であろう。
【００１１】
［Ｓｎｏｅ  ０１］でＩＰトレース・バックをサポートする設計者には、任意の与えられた個々のパケットについてのトラジェクトリの質問に答える能力が必要であると考えられる一方で、以下で大抵のトラヒック測定／解析用途には、ＩＰトレース・バックを含めて、それは過剰であることを論じる。この議論は、これらのほとんどのアプリケーションにおいて、一連の分離した個別パケットのトラジェクトリおよび／またはトラフィック量の代わりに、所与のパケットのグループ又は、いわゆるトラフィック集合のトラジェクトリおよび／またはトラフィック量を知ることで十分であるという観察に基づく。［Ｓｎｏｅ  ０１］のシステムが、１つの特別なパケットの起点の追跡のような、より強力なネットワークの用途をサポートできると誰かが論じるかもしれない一方で、我々はネットワーク・レベルのトラヒック解析／監視がそのような機能を提供する最良の方法ではないと信じている。その代わりに、特定用途レベルの機能は、末端システムに近い用途レベルでよりよくサポートされることができる。ネットワーク・トラヒック監視／解析インフラストラクチュアは、経路診断、トラヒック工学およびフロー・パターン解析のような、ネットワークおよび／またはトランスポート・レイヤの機能のサポートにその努力をフォーカスするべきであると考えている。
【００１２】
多くの場合関心のあるトラヒックの集合体の定義は、用途の文脈で明らかに定義される。本発明では、軽量トラヒック・ダイジェスト経由のトラヒック解析の分散構造（ＤＡＴＡＬＩＴＥ）を以下で定義されるトラヒックの集合体に第１に焦点を当てる：
（１）それらの起点および／または終点のノード（またはリンク）または
（２）トラヒックのそのグループが通過している特定のリンクまたはノードの組。
以下に示すように、そのようなトラヒックの集合体は、ネットワークの故障診断と同様に、トラヒック・マトリックス推定、経路検査を含む実際的なトラヒック測定／解析（ＴＭＡ）用途の幅広い領域の中心なので、そのような集合体の定義に焦点を合わせることに決定した。これらの主要なトラヒックの集合体の型式に加えて、提案されるＤＡＴＡＬＩＴＥインフラストラクチュアはまた、主要なそれの部分集合である、例えば与えられたプロトコル型式および／またはポート番号のパケットのグループの、より精細なトラヒックの集合体をサポートする。
【００１３】
交差（共通集合）セット濃度決定問題としてのトラヒック測定／解析
この章では一連の交差セット濃度決定（ＩＳＣＤ）問題としてのトラヒック測定／解析（ＴＭＡ）問題の定式化を記述する。ネットワークＧの、有向グラフ表現を考慮されたい。Ｇ＝（Ｖ，Ｅ）ここで、Ｖはノードのセット、Ｅは方向リンクのセットである。（ｉ，ｊ）∈Ｅをノードｉからノードｊへの方向リンクとする。Ｌｉ，ｊを与えられた測定時間の長さＴ秒間にリンク（ｉ，ｊ）を通過しているパケットのセットとする。さて今、飛行中のパケットに起因するフリンジ効果が無視できるように、ネットワーク内の最大エンド−エンド遅延より十分に長い測定期間を仮定する。パス遅延の効果は、多重時間インデックス・ノード・トラヒック・ダイジェストを保持することにより明らかにすることができる。実際に、時間インデックストラヒック・ダイジェストは、ネットワーク・パス遅延測定のサポートに用いることができる。Ｏｉ（またはＤｉ）を、同じ測定期間内にノードｉから発された（または到着した）パケットのセットとする。用語「発された」（または「到着した」）により、実際にそのノードから生成された（またはそこからネットワークを出ていく）パケットを意味している。パケットは可能なソースアドレススプーフのために、それが主張しているソース・ノードで実は生成されていないかもしれないので、用語「ソース」または「デスティネーション」の使用を避ける。同様にパケットは、経路上の問題や消失のために、それが意図する宛先ノードには到着しないかもしれない。
【００１４】
与えられた測定期間内に、我々が関心を持つトラヒックの集合体が以上に定義したパケットのセットの交差として、容易に表されることができる。我々のアプローチを示すため、以下の２つの一般的な（かつ基礎的な）ＴＭＡタスクを考える。
【００１５】
サンプルＴＭＡタスク＃１：
このタスクの目的は、ネットワーク中のすべてのＯ−Ｄノード・ペアの間の、ルート・パターンおよびトラヒックの量を決定することである。このような目的で、それらのＯ−Ｄノード・ペアとしてリンク（ｉ，ｊ）∈Ｅ、ｋ＝（ｓ，ｄ）∈Ｖ×Ｖを通過するパケットのセット
【数１】
0004727275.tif 000002
を考える。
【数２】
0004727275.tif 000003
は上記に定義された他のパケットのセットの交差として表されることもできることに留意されたい
【数３】
0004727275.tif 000004
。キーとなる観察点は、このタスクには（トラヒック・マトリックス推定、フロー・パターン解析、トラヒック・トレース・バック、経路／ネットワーク故障検出／診断、トラヒック工学のような他のＴＭＡアプリケーションの広範な領域と同様に）、
【数４】
0004727275.tif 000005
の完全な詳細の代わりに、
【数５】
0004727275.tif 000006
すなわち
【数６】
0004727275.tif 000007
の濃度を知れば十分であることである。例えばサンプルＴＭＡタスク＃１の目的は、すべてのリンク（ｉ，ｊ）∈ＥおよびすべてのＯ−Ｄノード・ペアｋ＝（ｓ，ｄ）∈Ｖ×Ｖに対して
【数７】
0004727275.tif 000008
を知るのみで達成されることができる。
【００１６】
サンプルＴＭＡタスク＃２
このタスクで起点ノード、それらが寄与するトラヒック量およびいくつかのＤＤｏＳビクチムであるかもしれない、与えられたダウン・ストリーム・ノードｄに到着して終了する、パケットのグループのアップ・ストリーム・フロー・パターンを決定したい、トレース・バックアプリケーションを考察する。このタスクを実行するために、
【数８】
0004727275.tif 000009
およびｋ＝（＊，ｄ）であるすべてのリンク（ｉ，ｊ）∈Ｅについての
【数９】
0004727275.tif 000010
を決定する必要があるのみである（ここで＊はワイルドカードである）。同様に、
【数１０】
0004727275.tif 000011
およびｋ＝（ｓ，＊）であるすべてのリンク（ｉ，ｊ）∈Ｅに対し
【数１１】
0004727275.tif 000012
を決定することにより、与えられたノードｓから発したパケットの、終点、ダウン・ストリーム・ルート・パターンおよびフロー量をトレースすることができる。
上記の観察に基づいて、ＤＡＴＡＬＩＴＥの基本的なアイデアは、ネットワーク中どこでもできる方法で、
【数１２】
0004727275.tif 000013
の分散演算／推定をサポートするインフラストラクチュアを提供することである。ここで、
【数１３】
0004727275.tif 000014
は、以上で言及したＯｉ、ＤｄおよびＬｉ，ｊのようないくつかのパケットのセットの交差の形式で表されている。以下に議論されるように、（［Ｄｕｆｆ  ００，Ｓｎｏｅ  ０１］の場合と同様）
【数１４】
0004727275.tif 000015
の完全な詳細の代わりに、
【数１５】
0004727275.tif 000016
にフォーカスすることにより、ＤＡＴＡＬＩＴＥのシステム記憶と通信帯域幅の要求は、ＤＡＴＡＬＩＴＥが１０Ｇｂｐｓ＋ネットワークのＴＭＡをサポートできるようにするまでに、十分削減されることができる。
いくつかの特定のパケット・セットの交差として
【数１６】
0004727275.tif 000017
を表すことにより、我々の定式化は実質的にＴＭＡ問題を、一連のいわゆる交差セット濃度決定（ＩＳＣＤ）問題に変換する。異なるロケーションに分散された多重セットの交差の濃度の決定問題は、（１）ＷＷＷの類似のウェブページを特定するサーチ・エンジンを補助する文脈で最近調査された。Ａ．Ｂｒｏｄｅｒ、「Ｏｎ  ｔｈｅ  ｒｅｓｅｍｂｌａｎｃｅ  ａｎｄ  ｃｏｎｔａｉｎｍｅｎｔ  ｏｆ  ｄｏｃｕｍｅｎｔｓ」、Ｃｏｍｐｒｅｓｓｉｏｎ  ａｎｄ  Ｃｏｍｐｌｅｘｉｔｙ  ｏｆ  Ｓｅｑｕｅｎｃｅｓ（ＳＥＱＵＥＮＣＥＳ）、Ｐｏｓｉｔａｎｏ、Ｉｔａｌｙ、９７年６月［Ｂｒｏｄ  ９７］および（２）ピアトゥピアネットワーク上の効率的ファイルサーチ／スワップをサポートするプロトコルの設計、Ｊ．Ｂｙｅｒｓ、Ｊ．Ｃｏｎｓｉｄｉｎｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、Ｓ．Ｒｏｓｔ、「Ｉｎｆｏｒｍｅｄ  Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ａｃｒｏｓｓ  Ａｄａｐｔｉｖｅ  Ｏｖｅｒｌａｙ  Ｎｅｔｗｏｒｋｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  Ｓｉｇｃｏｍｍ、２００２年８月［Ｂｙｅｒ  ０２］。［Ｂｒｏｄ９７］と［Ｂｙｅｒ０２］は双方が、Ａ．Ｂｒｏｄｅｒ、Ｍ．Ｃｈａｒｉｋａｒ、Ａ．Ｍ．Ｆｒｉｅｚｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｍｉｎ−ｗｉｓｅ  ｉｎｄｅｐｅｎｄｅｎｔ  ｐｅｒｍｕｔａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｃｉｅｎｃｅｓ、６０（３）、２０００、ｐｐ．６３０−６５９．［Ｂｒｏｄ  ００］の技術をセットＡ、Ｂのペアのいわゆる類似比｜Ａ∩Ｂ｜／｜Ａ∪Ｂ｜を推定するために、適用している。しかしながら、この技術により要求される情報交換の量は、関心のあるセットのサイズ、すなわちＯ（｜Ａ｜）またはＯ（｜Ｂ｜）に比例している。｜Ａ｜又は｜Ｂ｜が、測定時間に所与のリンクを通過するパケットの数に対応する我々の高速ＴＭＡアプリケーションにとって、これは実効不能である。40バイトのパケット、40Ｇｂｐｓのリンクにつき測定時間を１０数秒とすれば、｜Ａ｜は容易に数十億の範囲に達してしまうのである。ノーダル・ブルーム・フィルタの交換に基づく代替のアプローチでは、（［Ｄｕｆｆ  ００，Ｓｎｏｅ  ０１］により暗示されているように）、対応するブルーム・フィルタの類似のＯ（｜Ａ｜）メモリの要求量のために、同様に過度の記憶／通信帯域幅問題につきあたる。
【００１７】
個別サンプル計数経由分散交差濃度決定
分散ＩＳＣＤ問題を解くために、本発明であるＤＡＴＡＬＩＴＥは新しいアプローチを取る。第１にＩＳＣＤ問題を１つまたは以上の連合セット濃度決定（ＵＳＣＤ）問題に変換する。次にＵＳＣＤ問題を分散方式で解くために、最近のＯ（ｌｏｇｌｏｇ｜Ａ｜）個別サンプル計数アルゴリズムを適用する。実際に我々のアプローチは、［Ｂｒｏｄ  ９７］および［Ｂｙｅｒ  ０２］での上記のアプリケーションをその能力と拡張性を徹底的に改善するために、使用することができる。
その図式として、サンプルＴＭＡ＃２を思い出されたい、ここで
【数１７】
0004727275.tif 000018
である。基本的なセット理論に基づいて、
【数１８】
0004727275.tif 000019
は
【数１９】
0004727275.tif 000020
の形式で表され：
ここで、｜Ｏｓ｜は、測定期間内にノードｓから発される個別パケットの数である。定義により生成されるすべてのパケットは個別であり、｜Ｏｓ｜はすべての起点となるネットワーク・ノードに対しある単一のパケット・カウント数として維持されることができる。｜Ｌｉ，ｊ｜は、リンク（ｉ，ｊ）を通過する個別パケットの数である。Ｆｌａｊｏｌｅｔ、Ｍａｒｔｉｎ、Ｄｕｒａｎｄにより独創された、確率的個別サンプル計数技術を、すべてのリンク（ｉ，ｊ）∈Ｅについての｜Ｌｉ，ｊ｜を把握するために適用する。Ｐ．Ｆｌａｊｏｌｅｔ、Ｇ．Ｎ．Ｍａｒｔｉｎ、「Ｐｒｏｂａｂｌｉｓｔｉｃ  ｃｏｕｎｔｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｄａｔａｂａｓｅ  ａｐｐｌｉｃａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｃｉｅｎｃｅｓ、３１（２）、１９８５、ｐｐ．１８２−２０９［Ｆｌａｊ  ８５］およびＭ．Ｄｕｒａｎｄ、Ｐ．Ｆｌａｊｏｌｅｔ、「Ｌｏｇｌｏｇ  Ｃｏｕｎｔｉｎｇ  ｏｆ  Ｌａｒｇｅ  Ｃａｒｄｉｎａｌｉｔｉｅｓ」、ｓｕｂｍｉｔｔｅｄ  ｔｏ  Ｅｕｒｏｐｅａｎ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ａｌｇｏｒｉｔｈｍｓ、ＥＳＡ’２００３、２００３年４月［Ｄｕｒａ  ０３］。そのような技術の基本的な利点は、パケットのセットＬｉ，ｊの必要な情報を要約するために、ダイジェストＯ（ｌｏｇｌｏｇＮｍａｘ）−ビットを維持することしか、要求しないことである。ここでＮｍａｘは、Ｌｉ，ｊ中の個別サンプルの最大数である。本発明の文脈では、このダイジェストを
【数２０】
0004727275.tif 000021
により表すＬｉ，ｊのトラヒック・ダイジェスト（ＴＤ）と称する。
【数２１】
0004727275.tif 000022
を維持する一方で、同じ測定期間内にそのリンクを通るパケットの単純なカウント数（複製を含む）を追跡するために、すべてのリンク（ｉ，ｊ）∈Ｅに対し単純パケット・カウンタＣｉ，ｊを導入する。Ｃｉ，ｊと｜Ｌｉ，ｊ｜の間の大きな相違は、リンク（ｉ，ｊ）が経路ループの一部になった可能性があるといった、潜在的な経路問題を表す。こうして
【数２２】
0004727275.tif 000023
の評価における残る企ては、｜Ｏｓ∪Ｌｉ，ｊ｜の計算である。ここで、｜Ｌｉ，ｊ｜の推定に用いられる確率的個別サンプル計数技術は、分散方式で｜Ｏｓ∪Ｌｉ，ｊ｜を計算するために同様に拡張することができる。これは、ノードｓおよびノードｉそれぞれによりローカルに維持され、
【数２３】
0004727275.tif 000024
、
【数２４】
0004727275.tif 000025
により表される、パケット・セットＯｓ、Ｌｉ，ｊに対する、Ｏ（ｌｏｇｌｏｇＮｍａｘ）サイズのＴＤの交換に基づいている。同様に、サンプルＴＭＡ＃１に対する
【数２５】
0004727275.tif 000026
は、以下として表示される。
【数２６】
0004727275.tif 000027
【００１８】
ここでも、式２のＲ．Ｈ．Ｓ．の連合セットの濃度の決定のために、上述のＯ（ｌｏｇｌｏｇＮｍａｘ）の個別サンプル計数技術を使用することができる。要約すると、ＴＭＡ問題はいくつかの特定のパケット・セットの連合の濃度の決定に変換されることができる。より重要なことに、Ｏ−Ｄノード・ペア分類に基づいて、｜Ｖ｜２型式のパケットに対する、全ネットワークの経路パターンおよびリンク毎のトラヒック量を決定するために、リンク毎の単一軽量ＴＤ（プラスリンク毎の単純パケット・カウンタ）のみを、このアプローチは必要とする。それを通ってパケットが実際にネットワークに入る（去る）ルータｉのリンクの特定により、それらのリンクのＴＤに基づいてルータｉを発した（到着した）パケット・セットのＴＤを導出することができる。そのためこれは、
【数２７】
0004727275.tif 000028
および
【数２８】
0004727275.tif 000029
を明示的に維持する必要がない。
【００１９】
一般的に、一連のセット連合の濃度に関する多重セットの交差の濃度を表現することは、可能である。特に、セットのリストＳ１，Ｓ２，．．．，Ｓｎに対し、
【数２９】
0004727275.tif 000030
である。
例えばリンクｌｉ，ｊを通過するＯ−Ｄペア（ｓ，ｄ）を有するすべての４０バイトＴＣＰパケットである、関心のあるトラヒックの集合体の定義を精選するために我々が追加のセットの交差を適用するときに、式３は有用である。式３に基づいて、ＩＳＣＤ問題が式３のＲ．Ｈ．Ｓ．のセット連合の濃度の計算に常に変換されることができる。これはその代わりに、個別サンプル計数技術を用いて、分散方式で実行することができる。要約すると、本発明の解法アプローチは以下の工程からなる。
１．関心のあるＴＭＡ問題を、関心のあるいくつかの交差セットの濃度決定問題、またはいわゆる交差セット濃度決定（ＩＳＣＤ）問題に変換する。
２．式３を用いて、ＩＳＣＤ問題を、関心のあるいくつかのセット連合の濃度決定問題、またはいわゆるセット連合濃度決定（ＵＳＣＤ）問題に変換する。
３．Ｆｌａｊｏｌｅｔ、Ｍａｒｔｉｎ、Ｄｕｒａｎｄにより独創された、個別サンプル計数技術を用いて分散方式でＵＳＣＤ問題を解く［Ｄｕｒａ  ０３］。
【００２０】
以下の章ではＦｌａｊｏｌｅｔ、Ｍａｒｔｉｎ、Ｄｕｒａｎｄによる、「ｌｏｇｌｏｇ個別サンプル計数」技術を復習し、次にそれがいかにＤＡＴＡＬＩＴＥ発明に適用できるのか、説明する。関連する注として、Ｃ．Ｅｓｔａｎ、Ｇ．Ｖａｒｇｈｅｓｅ、Ｍ．Ｆｉｓｋ、「Ｃｏｕｎｔｉｎｇ  ｔｈｅ  ｎｕｍｂｅｒ  ｏｆ  ａｃｔｉｖｅ  ｆｌｏｗｓ  ｏｎ  ａ  ｈｉｇｈ  ｓｐｅｅｄ  ｌｉｎｋ」、ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ、３２巻３号２００２年３月［Ｅｓｔａ  ０２］は、高速リンク上のローカル・ネットワーク・フローの計数の推定のための［Ｆｌａｊ  ８５］の個別サンプル計数アルゴリズムの変形をデザインしている。ＤＡＴＡＬＩＴＥではその要素（パケット）が地理的に分散された位置で観察される、パケットのセット連合の個別パケットの数を推定するために、［Ｄｕｒａ  ０３］の技術を適用する。分散セット連合に対する代替の個別サンプル計数技術はまた、Ｐ．Ｂ．Ｇｉｂｂｏｎｓ、Ｓ．Ｔｉｒｔｈａｐｕｒａ、「Ｅｓｔｉｍａｔｉｎｇ  Ｓｉｍｐｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｏｎ  ｔｈｅ  Ｕｎｉｏｎ  ｏｆ  Ｄａｔａ  Ｓｔｒｅａｍｓ」、Ｐｒｏｃｓ．ｏｆ  ＡＣＭ  ＳＰＡＡ、Ｃｒｅｔｅ  Ｉｓｌａｎｄ、Ｇｒｅｅｃｅ、２００１［Ｇｉｂｂ  ０１］。しかしながら、［Ｇｉｂｂ  ０１］で提案されるスキームのメモリ必要量は、［Ｄｕｒａ  ０３］のそれほどには魅力的でない。
【００２１】
ｌｏｇｌｏｇ個別サンプル計数技術
サンプルＳのセットを考える。ここで各々のパケットｓは、識別子ｉｄｓを有する。同じ識別子を備えるサンプルは、複製として扱われる。［Ｄｕｒａ  ０３］は、メモリのＯ（ｌｏｇｌｏｇＮｍａｘ）ビットを有する、Ｓ内の個別サンプルの数の計数、すなわち｜Ｓ｜の問題を解くが、ここでＮｍａｘはＳの個別サンプルの最大数である。これらのスキームは、以下の通りである。
第１に各々のサンプルの識別子が、ハッシュ関数ｈ（・）の入力として用いられ、ハッシュ関数は
【数３０】
0004727275.tif 000031
の領域上で均一に分散された、ランダムな負でない整数を出力するが、ここで
【数３１】
0004727275.tif 000032
はＮｍａｘより大でなければならない。Ｒｍａｘビット長のランダム二進ストリングとして、ハッシュ出力の二進表現を考察する。直感的に、ｈ（・）の出力は均一に分散しているので、Ｓ内にｎの個別サンプルがある場合、平均的にそれらのｎ／２ｋが、「１」のビットが後に続く（ｋ−１）連続したゼロを伴うｈ（・）の出力を有する。（複製のサンプルはｈ（）に同じ出力を有するので、それらは集団的に１回のランダムトライアルに寄与するのみである。）
【００２２】
入力として二進のストリングｘを取り、（１＋ｘの連続する先行のゼロの最大数）の値を出力する、関数ｒ（ｘ）を定義する。例えば、ｘ＝００００１ＸＸＸ．．に対しては、ｒ（ｘ）＝５；ｘ＝１ＸＸＸ．．に対してはｒ（ｘ）＝１で、ここでＸは「任意の数」である。入力としてＳ内のすべてのサンプル識別子を考察する一方で、
【数３２】
0004727275.tif 000033
を達成したｒ（ｈ（・））の最大値とする。それ故Ｒ（Ｓ）は、ｌｏｇ２ｎの値の大体の目安を与えるであろう。実際Ｒは、１＋パラメータ１／２のｎ独立幾何学的変数の最大値と同じように精密に分散している。Ｒが付加偏倚１．３３および標準偏差１．８７を伴うｌｏｇ２ｎを推定することを、示すことができる。実際、推定誤差を低減するため、複数のＲの値を得る異なるハッシュ関数を用い、ｌｏｇ２ｎを推定するためにそれらの平均値を用いることができる。代わりに、ｎ（または等価的に｜Ｓ｜）を推定するために、以下の工程でいわゆる確率平均アルゴリズム（ＳＡＡ）を用いることもできる。
１．セットＳサンプルをｍ＝２ｋバケットに、例えばサンプルのハッシュ出力の最後のｋビットに基づいて分離する。
２．Ｒｊを、ｊ番目のバケットに対するＲの値とする。ｒ（・）への各々のサンプルのハッシュ出力の（Ｒｍａｘ−ｋ）先頭ビットを入力することにより、Ｒｊを１≦ｊ≦ｍで計算する。
３．以下の式を用いて、
【数３３】
0004727275.tif 000034
、すなわち｜Ｓ｜の推定を計算する。
【数３４】
0004727275.tif 000035
ここで、αｍはｍの関数である修正計数である。
［Ｄｕｒａ  ０３］に示されているように、
【数３５】
0004727275.tif 000036
の標準誤差σは、以下で与えられる。
【数３６】
0004727275.tif 000037
例えば、ｍ＝２０４８に設定すると、２％の標準誤差が達成される。ＮｍａｘがＳの個別サンプルの最大数であることを思い出されたい。各々のバケット内の個別サンプルの平均数は約Ｎｍａｘ／ｍなので、したがってＲｍａｘで表されるＲｊの最大値に対し、
【数３７】
0004727275.tif 000038
であると規定するべきである。［Ｄｕｒａ  ０３］には、各々のｍＲｊの二進表現に必要なビット数は、以下に等しいことが示されている。
【数３８】
0004727275.tif 000039
このように、この確率的個別サンプル計数スキームに対する動作メモリの必要Ｍは、以下である。
Ｍ＝ｍｌｏｇ２Ｒｍａｘ  ｂｉｔｓ  ．．．．．．．．．．．．．．．．．  式（７）
上記の個別サンプル計数スキームは、セットＳのサンプルが別個の位置に観察（または記憶）される、分散の実現に容易に従順することを留意されたい：
【数３９】
0004727275.tif 000040
とし、ここでセットＳｐはＰの別個の位置に維持される。｜Ｓ｜（または
【数４０】
0004727275.tif 000041
）で表されるＳの個別サンプルの数を、分散方式で以下の工程で、分散マックス・マージ・アルゴリズム（ＤＭＡ）に従って、推定することができる。
１．各々の位置ｐで、Ｓｐのサンプルに基づいて、各々のｍバケットに対するｒの値を更新する。
【数４１】
0004727275.tif 000042
を、位置ｐでのｊ番目のバケットに対するＲの値とする。ここで、１≦ｊ≦ｍ、および１≦ｐ≦Ｐである。
【数４２】
0004727275.tif 000043
のｍ個の値の収集を、Ｓｐの軽量ダイジェストと考えることができる。
２．測定期間の最後に、すべてのＰの位置の間で、１≦ｊ≦ｍ、および１≦ｐ≦Ｐに対し
【数４３】
0004727275.tif 000044
の収集を交換する。
３．各々の位置で、１≦ｊ≦ｍに対し、
【数４４】
0004727275.tif 000045
の設定により、
【数４５】
0004727275.tif 000046
のマックス・マージを実行する。
４．任意のＰ位置において、上記に議論したＳＡＡの式４に工程３の結果であるマックス・マージしたＲｊを代入することにより、｜Ｓ｜（または
【数４６】
0004727275.tif 000047
）を推定する。
【００２３】
図１を参照して、上記の個別サンプル計数スキーム、すなわちＳＡＡおよびＤＭＡが、いかに本発明の文脈に適用されることができるか、説明する。この場合、ネットワーク内で関心のある種々のパケットのセットがサンプルセット１０になる。パケットは検査されるサンプルとなり、サンプル（またはパケット）識別子はパケット・ヘッダのいくつかの選択されるフィールドの連結から、および工程２０に示されるように、できるならばペイロードのある特定の部分から、構成される。パケット識別子の主要な要求は、ネットワークでのパケットの移動があっても不変に留まるべきである、ということである。その結果、ＩＰ・ヘッダ内のＴＴＬ−フィールドのようなあるフィールドは、望ましくはパケット識別子の一部として含まれるべきでない。ネットワークを通して移動するパケットのパケット識別子をうかつに変形する、例えばパケット経路沿いのＩＰ分解、またはネットワーク内での追加のカプセル化／トンネル化の使用のような、実際の課題に、我々は気がついている。パケットを特別な場合として普及したインパクトで扱い、かつ残りについては追加のトラヒック測定誤差として計量することにより、これらの課題に対処する。
【００２４】
関心のある与えられたパケットについて、ｍのＲｊの収集（ＳＡＡで定義されたような）が、パケット・セットのトラヒック・ダイジェスト（ＴＤ）になる。図１は、そのパケットからパケット・セットのＴＤがいかに抽出されるかを、要約している。例えば、工程３０で各々のパケットのパケット識別子（ＰＩＤ）がＲｍａｘ−ビットのハッシュ出力ｈ（ＰＩＤ）を得るために、ハッシュ関数に入力される。工程３０の出力は、工程４０のｍ−方向スプリッタに入力される。ここで、ｍ−方向スプリットはｈ（ＰＩＤ）の最後のｌｏｇ２ｍビットに基づいて発生する。各々の１からｍのバケットに対し、工程５０でＲｉが探知されるが、ここでＲiは、関数ｒ（）を用いることによって得られる、i番目のバケットに割り当てられたすべてのハッシュ出力ｈ（ＰＩＤ）の最初の（Ｒmax―log 2 m）ビットにおける連続する先行ゼロの最大数である。測定期間の終わりに、Ｒ１からＲｍまでの収集は、関心のあるＳｐのパケット・セットの軽量ＴＤとなるが、ここでＴＤのサイズはｍｌｏｇ２Ｒｍａｘビットである。
【００２５】
ＤＡＴＡＬＩＴＥの動作モデル
さてＴＭＡタスクをサポートするために、本発明のＤＡＴＡＬＩＴＥが可能なネットワーク内の動作工程を説明する。図示の例として先に記述した、サンプルＴＭＡタスク＃１を用いる。この場合各々のノードｉ∈Ｖは、軽量トラヒック・ダイジェストを（ＳＡＡのｍＲｊの収集の形式で）各々の関心のあるローカル・パケット・セット、すなわちそれを発したパケットのセット、（Ｏｉ）、それに到着したパケットのセット（Ｄｉ）およびその各々のリンク（ｉ，ｊ）∈Ｅを通過するパケットのセット（Ｌｉ，ｊ）について維持する。これらのパケットの対応するＴＤを、それぞれ
【数４７】
0004727275.tif 000048
、
【数４８】
0004727275.tif 000049
、
【数４９】
0004727275.tif 000050
と記述する。リンク毎のパケット・カウント（Ｃｉ，ｊ）を追跡するための単純カウンタの使用（パケットの複製を考慮しない）およびパケットの発生のカウント（｜Ｏｉ｜）に加え、各々のルータはローカルの関心のある個別パケットのカウント、すなわち｜Ｌｉ，ｊ｜、｜Ｄｉ｜を
【数５０】
0004727275.tif 000051
および
【数５１】
0004727275.tif 000052
に含まれる情報と共にＳＡＡを用いて、追跡する。さらに、ノードｉは式２の
【数５２】
0004727275.tif 000053
の値を、リンク（ｉ，ｊ）∈Ｅのすべて、およびすべてのｋ＝（ｓ，ｄ）∈Ｖ×Ｖに対し、すべてのノードｊ∈Ｖから
【数５３】
0004727275.tif 000054
、
【数５４】
0004727275.tif 000055
を受信した後に、推定することができる。特に、式２のＲ．Ｈ．Ｓ．上のセット連合の濃度は、Ｏｓ、ＤｄおよびＬｉ，ｊをＤＭＡのＳｐとして代入することにより、推定することができる。ここで、
【数５５】
0004727275.tif 000056
はノードｓおよびｄからノードｉにそれぞれ
【数５６】
0004727275.tif 000057
および
【数５７】
0004727275.tif 000058
の分散により、置換される。ノードｉにより
【数５８】
0004727275.tif 000059
の推定が一度計算されると、周期的な放送または質問−回答に基づくオンデマンドを経由して、他のネットワーク・ノードに分散されることができる。各々のノードは、
【数５９】
0004727275.tif 000060
の知識に基づいて、関心のあるトラヒックの集合体のネットワーク・レベルの概観を構成することができる。
【数６０】
0004727275.tif 000061
の測定／推定誤差をさらに削減するために、例えば［Ｄｕｒａ  ０３］のスキームの確率的性質から、
【数６１】
0004727275.tif 000062
に関連して表現される、ノード・レベルおよびネットワーク・レベルのフロー節約制約に基づいて、最少二乗誤差（ＭＳＥ）最適化を、各々のノードは付随的に実行することができる。そのようなＭＳＥ最適化の詳細は、次章で議論される。図２は、ＤＡＴＡＬＩＴＥが可能なノードにより、上記の動作工程を要約する。
【００２６】
図２を参照すると、本発明の方法論を具体化する単数または複数のプロセッサを有する、ノード１００についてのフロー図が示されている。図示のように、工程１では到来するパケットがノード１００に入り、関心のあるパケット・セットを決定するために、プリフィルタされる。工程２では、トラヒック・ダイジェスト（ＴＤ）が抽出され、例えばＯ（ｌｏｇｌｏｇＮ）サイズのＴＤが、先に述べた方法で抽出される。パケットはさらに、それらのデータ経路を進行する。図２の工程３において、ＴＤがネットワーク内、例えば関心のあるパケット・セット内の他の関連するノードに分散される。ＴＤは既知の方法で付随的に圧縮され、および／または現存するルーティングプロトコル制御メッセージまたは新しく、専用のクエリープロトコルのオペイク・データ・オブジェクトとして、フォーマットされる。工程４では、ネットワーク内の関連する他のノードからリモートＴＤが、ノード１００で受信される。工程５では、
【数６２】
0004727275.tif 000063
の与えられた集合体フローのローカルな推定が、ローカルＴＤおよび分散されたリモートＴＤに基づいて決定される。次に、与えられた集合体フローのローカルな推定は、他の関連するノードに分散される。工程７では、ネットワーク内の他の関連するノードからの推定された集合体フロー
【数６３】
0004727275.tif 000064
は、ノード１００で受信される。工程８で、ネットワーク内の他のノードから受信された集合体フローの推定で、トラヒック・フロー・パターンおよび量のネットワーク・レベルの外観の構成は、ローカルおよびリモート集合体フロー推定に基づいて決定される。工程９では、例えばネットワーク・レベルのフロー節約制約の適用による、推定誤差のさらなる削減のような、後処理が行われる。工程１０では、例えばネットワーク・レベルのトラヒック経路パターン、フロー量および／または可能な経路遅延統計のような、最終出力が行われる。出力はまた上記のパラメータの１つまたは複数の変化を検出する。
Ｌｉ，ｊのＴＤではなく、発せられたおよび到着したパケット（すなわちすべてのｉ∈ＶのＯｉ、およびＤｉ）のＴＤの分散のみにより、ＤＡＴＡＬＩＴＥの通信帯域幅の要求を相当に削減することに留意されたい。これは、
【数６４】
0004727275.tif 000065
の軽量特性によってさえ、それらは
【数６５】
0004727275.tif 000066
程には小さくないことを理由にする。また実際的なネットワークにはリンクよりノードが一般的にかなり少ないので、
【数６６】
0004727275.tif 000067
および
【数６７】
0004727275.tif 000068
の数は、
【数６８】
0004727275.tif 000069
よりかなり少ない。
【００２７】
ＤＡＴＡＬＩＴＥに必要なメモリおよび帯域幅の考察と最適化
主要な設計／工学上の挑戦は、（１）ＴＤのローカル・メモリ要求と、（２）内部ノードの通信帯域幅の要求を受け入れ可能なレベルに、関心のあるＴＭＡアプリケーションの推定誤差要求を充足しつつ、維持することである。この目的で、以下の多重尖端戦略を提案する。
【００２８】
１．ＴＤ当たりのメモリサイズの慎重な制御
１０Ｇｂｐｓ＋のネットワークでのＴＭＡタスクをサポートするＴＤのメモリ要求を考察する。４０Ｇｂｐｓリンクは毎秒４０バイトの最大１億２５００万パケット転送できるので、８０００秒の長さまでの測定期間を（式６の）Ｎｍａｘをサポートするためには、１０１２または２４０の値が適切であるべきである。式５によれば、個別のサンプルカウント推定に対し標準誤差σ≦２％を実行するために、ｍは≧２０４８であるべきである。式６にＮｍａｘ＝２４０およびｍ＝２０４８を代入すると、Ｒｍａｘ＝３２＝２５となる。言い換えると、ＴＤのＲｊの各々を符号化するために、５ビットを割り当てれば十分である。したがって、各々のＴＤのメモリの必要Ｍ＝ｍｌｏｇ２Ｒｍａｘ（ビット）は、ｍの値により決定される。対応する個別サンプルカウント推定の標準誤差２％に対応する、ｍ＝２０４８に対しＴＤのサイズは約１．７Ｋバイトである。これを、例えば先に議論したサンプルＴＭＡタスクの
【数６９】
0004727275.tif 000070
といった、関心のある究極の測定基準の評価を通じて、可能な推定誤差の蓄積および／または「増幅」を把握するための、各々のＴＤのメモリの必要量の下限であると考える。これは、式３によれば、式３のＬ．Ｈ．Ｓ．の項の推定誤差が、Ｒ．Ｈ．Ｓ．の各々の項の推定誤差の和であるからである。従って、Ｌ．Ｈ．Ｓ．項の設定交差の工程が多ければ、式3のＲ．Ｈ．Ｓ．の連合セット濃度についての推定誤差が蓄積されるため、推定誤差は大きくなる。さらに、
【数７０】
0004727275.tif 000071
は式３のＲ．Ｈ．Ｓ．の各々の連合セット濃度に関する「相対」推定誤差なので、式３のＬ．Ｈ．Ｓ．の交差項に対する、パーセント型の対応相対推定誤差は、絶対項で式３のＬ．Ｈ．Ｓ．の交差セットの濃度が、Ｒ．Ｈ．Ｓ．の連合セット項のそれよりかなり小さい場合に、増幅される。
【００２９】
実際には、ｍの実際の値、したがってＴＤ当たりのメモリサイズは、ＴＭＡアプリケーションの推定誤差要求に基づいて決定される。ラフな推定／測定で十分なこれらのＴＭＡアプリケーションに対しては、１．７Ｋバイトのような精度の粗い、小さいサイズのＴＤで十分である。このタイプのＴＭＡアプリケーションの例は、関心のあるイベントがトラヒック・フロー・パターンの一般的に劇的な変化を起こす、ＤＤｏＳ攻撃のトレース・バックと同じく、経路錯誤／構成ミス／検出変化を含む。結果的に、
【数７１】
0004727275.tif 000072
の値がそれらの名目上の値から相当に乖離しても、突然の乖離に関して推定誤差は軽微となる。数量的で高度に正確な測定が必要とされるＴＭＡアプリケーションに対しては、式３のＬ．Ｈ．Ｓ．の各々の「連合型」項の推定の際に、ｍを増加（したがってσを減少）させることができる。しかしながら、σの線形的減少はＴＤのサイズの二次の増加を必要とするので、そのようなメモリ対精度のトレードオフは思慮深い方法で行われるべきである。幸運にもＴＤの本来的な軽量性のおかげで、そのメモリサイズを増加させる十分な空きがある。例えば、ＴＤサイズの１．７Ｋバイトから、０．８７Ｍバイトへの５１２倍の増加は、σを０．０８％以下に削減することができる。さらに、０．８７ＭバイトのＴＤは、現在の高速メモリ技術においては、まだ十分道理にかなっている。すなわち今日では、１０Ｇｂｐｓラインカードに対するメモリ量は、約２Ｇビットである。これは、２００ｍ秒の価値があるバッファリングを提供する。この量のメモリの１０％、すなわち２５Ｍバイトの使用は、トラヒック測定／解析目的としては、各々のラインカードが２８以上の０．８７ＭバイトＴＤを備えることを意味する。この調査では、並行してＴＤのマルチプル・サイジングをサポートする手段を研究する。
【００３０】
２．リンク毎の多重トラヒック集合体（またパケット・セット）の効率的サポート
実際には、リンク毎の単一のパケット・セット、すなわちＬｉ，ｊの維持の代わりに、いくつかのＴＭＡアプリケーションは、例えばパケットのプロトコル型式および／またはポート番号に基づいて、パケット・セットのより高精度の定義を要求する。リンク毎のより高精度の多重パケット・セットの他の興味ある使用は、元の測定期間が多数のより小さい期間に分割された、「時間指標付」パケット・セットの使用であり、それによるとネットワーク内の異なるリンクに属する時間指標付パケットの交差濃度の計算により、明らかに限られた分解能でネットワーク内の経路遅延を推定することができる。
【００３１】
リンク毎の多重パケット・セットをサポートするために、素朴なアプローチは各々の関心のある高精度パケット・セットに対して個別のＴＤを割り当てる。しかしながら一般化したパケット・セット交差技術の導入により、ラインカード毎のＱＴＤのみの使用で、Ｏ（Ｑ２）型式の高精度トラヒック集合体のネットワーク・レベルのＴＭＡを、サポートすることができる。この基本理念は、以下の通りである。
【００３２】
リンク毎にＫ＝２ｋのパケット・セットをサポートする必要がある、と仮定する。Ｐ１，Ｐ２，．．．，Ｐｋで表示される各々のＫのパケット・セットにＴＤを割り当てる代わりに、
【数７２】
0004727275.tif 000073
である人為的なＱ個のパケット・セットＳ１，Ｓ２，．．．，ＳＱのリストを構成する。Ｓ１，Ｓ２，．．．，ＳＱは領域１≦ｑ１，ｑ２≦Ｑで１≦ｉ≦Ｋであるすべてのｉについて定義され、ここで、Ｐｉ＝Ｓｑ１∩Ｓｑ２である。言い換えると、各々のＰｉは人為的なセットのペアの交差から「回復」される。したがってそれぞれ
【数７３】
0004727275.tif 000074
と記載されるＱ個の人為的なセットＳ１，Ｓ２，．．．，ＳＱの各々に対し、ＴＤのみを維持することにより、その１つの成分としてＰｉを有する任意の交差またはセット連合の濃度を計算することができる。これは、第１にＰｉをＳｑ１∩Ｓｑ２として表現し、次に式３を適用して、先に議論した個別サンプル計数技術を使用することである。例えば、２７６のネットワーク・レベルの微細トラヒック集合体のＴＭＡを同時にサポートするために、リンク毎に２４のＴＤを維持する必要があるのみである。高分解能の０．８７ＭバイトＴＤについても、そのような構成のラインカード毎に必要な全ＴＤメモリは、今日の一般的な１０Ｇｂｐｓラインカードに見られる、２１Ｍバイトまたはメモリの８．４％（２Ｇビットまたは２００ｍ秒レベルのバッファリング）以下である。
【００３３】
理論的には、各々のＰｉを回復するために、２ｌｏｇ２Ｋの人為的セット（各々がＫの二進表現ｌｏｇ２Ｋビットのビット値に対応する）の間の交差のｌｏｇ２Ｋ工程を適用することにより、要求されるＴＤの数をラインカード毎に２ｌｏｇ２Ｋまでさらに削減することができる。しかしながら、累積推定誤差は、式３のＲ．Ｈ．Ｓ．の多数の項のために過大になるかもしれない。これは代わりに、工程毎の推定誤差を削減するために、各々のＴＤのメモリ要求を増加する。交差の工程数とＴＤ毎のメモリ要求の増加の間の詳細なトレードオフは、我々の調査の主題である。
【００３４】
３．ネットワーク・レベルのフロー節約制約の考察によるさらなる推定誤差の削減
ＴＤメモリを節約する他の方法は、初期の推定の後処理を経由した
【数７４】
0004727275.tif 000075
の実効推定誤差の削減による。このスキームでは、ネットワーク内のすべてのノードから
【数７５】
0004727275.tif 000076
の初期の推定を受信した後は、
【数７６】
0004727275.tif 000077
に関して表現されたノード・フローの節約制約に基づく最少二乗推定（ＭＳＥ）最適化を実行する。
【数７７】
0004727275.tif 000078
を、受信した
【数７８】
0004727275.tif 000079
の初期推定値とする。この最適化の動機は、ノード・フロー節約制約の観点でのそれらの不整合の調整による、初期推定
【数７９】
0004727275.tif 000080
の集合誤差を削減しようとすることである。
【数８０】
0004727275.tif 000081
を、ノード・フロー節約制約を充足する、
【数８１】
0004727275.tif 000082
の新しい推定値とする。
【数８２】
0004727275.tif 000083
から
【数８３】
0004727275.tif 000084
への変化に必要な摂動を、
【数８４】
0004727275.tif 000085
により表現する。次のＭＳＥ最適化問題を考察する。
【数８５】
0004727275.tif 000086
の最小化
ここで、
【数８６】
0004727275.tif 000087
である。
上記の最適化の解は、
【数８７】
0004727275.tif 000088
の「集合的」最少摂動、すなわち
【数８８】
0004727275.tif 000089
を生じ、それにより新しい推定
【数８９】
0004727275.tif 000090
は、
【数９０】
0004727275.tif 000091
の真の値の場合のように、少なくともノード・フロー節約制約を充足する。フロー節約制約（それは
【数９１】
0004727275.tif 000092
の真の値により充足されなければならない）を考察することにより、それらの真の値により近い推定をもたらすと推測する。
【００３５】
４．ノード間通信帯域幅の最適化
本発明のＤＡＴＡＬＩＴＥの通信帯域幅の要求の支配的な制御因子は、以下を含む。
（１）交換されるべきＴＤの数とサイズ
（２）ＴＤ交換の頻度とその結果のトラヒック・フローの推定器および
（３）それを通してＴＤとトラヒック・フロー推定器が、ネットワーク・レベルに分散される方法
（１）がいかに制御され削減されるかは、既に記述した。ここで、（１）に関しいくつかの追加の最適化の好機を述べる。第１にＴＭＡアプリケーション、すなわち関心のあるトラヒック測定、の必要性に依存して、ネットワーク内の他のノードに選択されたＴＤのセットの分散のみを必要とする。例えば、サンプルＴＭＡタスク＃１はネットワーク内のすべてのノードの間で、
【数９２】
0004727275.tif 000093
と
【数９３】
0004727275.tif 000094
のフル・メッシュ交換を必要とする一方で、サンプルタスク＃２はダウン・ストリームＤＤｏＳ攻撃犠牲ノードの
【数９４】
0004727275.tif 000095
の分散のみを要求する。測定期間の終わりにそれらを他の関連するノードに分散する前に、ＴＤを圧縮することができる。
【００３６】
ＤＡＴＡＬＩＴＥによりサポートされた動作の周期的放送およびオン・デマンド・クエリー・アンサーの２つのモードはまた、（２）の制御を助ける。実際、ＴＤ交換の頻度およびその結果のトラヒック・フロー推定は、アプリケーションの必要性により主に決定される。例えば、交換検出型のアプリケーション、例えば経路ミス構成／ネットワーク故障の検出については、検出時間を削減するために交換の頻度はかなり高い。幸いにもこれらは又、例えば少ないＴＤといった精緻性の低い測定／推定で十分なアプリケーションである。これらのアプリケーションにおいては、問題となる事象により、結果として引き起こされるフローパターン及びリンク毎のフローの値の変化が重大なものとなる傾向にあるからである。他方、より高い精度の測定／推定（およびより大きいＴＤ）を必要とするＴＭＡアプリケーションは、代わりに帯域幅を削減することを助ける、より長い測定期間に対してのみ有意である傾向にある。ＤＡＴＡＬＩＴＥスキームの他の利点は、測定期間Ｔと共に、ＴＤメモリの要求が非常にゆっくりと（Ｏ（ｌｏｇｌｏｇＴ））で増大することである。上記したように、一般的なトラヒック測定アプリケーションに対し適切である、８０００秒までの長さの測定期間に対し、ＴＤのサイズを効率よく維持することができる。
【００３７】
最終的に、ＴＤの分散パターンは、必要な分散頻度と共に、ＴＤの数とサイズに基づいて決定されるべきである。物事を概観するために、２つの極端なシナリオ（またはアプリケーションの必要性）を考察する。最初のシナリオでは、トラヒック・パターン変化／故障検出アプリケーションまたはＤＤｏＳトレース・バックに、１．７ＫバイトのＴＤが使用される。各々のノードの圧縮されない
【数９５】
0004727275.tif 000096
および
【数９６】
0004727275.tif 000097
がすべての他のノードに、超流（帯域幅方式の最も高価なオプション）を用いて１秒毎に分散されたとしても、ネットワークのすべてのリンクに生成される全ＴＤトラヒックは、２＊１．７＊８＊｜Ｖ｜Ｋｂｐｓ、すなわち１００ノードのネットワークのリンク毎に２．７２Ｍｂｐｓを超えないか、または１０Ｇｂｐｓリンクの能力の０．０３％より低い。第２のシナリオでは、ネットワーク・レベルの遅延時間統計および微細精度のトラヒック型式の振る舞いを測定するために、特別な１時間毎のトラヒック調査が行われる。ここで、２７６タイプのネットワーク・レベルのトラヒック集合体の挙動を（上記した一般化セット交差技術を用いて）解析するために、同じネットワーク内のすべてのノードの間のフルＩ−ＢＧＰを用いて、２４＊２の高精度０．８７Ｍバイト非圧縮ＴＤの各々が１時間毎に分散される。ノード毎の対応する到来ＴＤの帯域幅は、０．８７＊８＊２＊２４＊１００／３６００Ｍｂｐｓ＝９．２８Ｍｂｐｓであり、それでも１０Ｇｂｐｓのリンクの能力の０．１％以下である。
【００３８】
結論
要約すると、ネットワーク・トモグラフィ・アプローチを苦しめる、無効なトラヒックのモデル化または動作の仮定に起因する問題を、直接測定アプローチをとることにより、本発明のＤＡＴＡＬＩＴＥは回避している。本発明のＤＡＴＡＬＩＴＥスキームと現存するトラジェクトリ・ベースのものとの間には、高度の共通点があるにもかかわらず、それらの間には基本的な差異がある：第１に、一連のセット濃度決定問題としてトラヒック測定問題を定式化することにより、最少の通信余力で、分散方式のトラヒック解析を実行するために、個別サンプル計量での最近の進歩をてこにすることができる。第２に、個々のパケット１つずつの代わりに、トラヒック集合体の挙動の測定と解析に焦点を当てることで、本発明のＤＡＴＡＬＩＴＥに対するシステム・メモリおよび通信帯域幅の要求は、従来の方法に較べて大幅に削減される。結果的に、現存するトラジェクトリ・ベース・システムが採用する、重量、集中化アプローチとは異なり、ＤＡＴＡＬＩＴＥは分散計算モデルを採用することができる。
【００３９】
上記の記載は、本発明の原理を単に示すものである。当業者が多様な変更を工夫でき、それらが本文書に明白に記述または示されていなくとも、本発明の原理を具体化し、本発明の精神と範囲内であることが容易に理解される。さらに、すべての例と言及された条件言語は、そのような特に言及された例および条件への限定でなく解釈され、読者に我々によって技術を進歩させる本発明の原理と概念の理解を援助する目的で、基本的に例示の目的にのみ用いられている。さらにここで、その特定の例と同様、発明の原理、態様、および実施形態を言及した言葉は、その構造的および機能的な等価物の双方を包含するように意図されている。さらに、そのような等価物は、現在知られている等価物と同様に将来開発される等価物、すなわち構造にかかわらず同じ機能を奏する、開発された要素を含む。
【００４０】
以下の請求項では、特定の機能を実行する手段として表現された任意の要素は、例えばａ）該機能を実行する回路要素の組合せ、またはｂ）ファームウェア、マイクロコード等、該機能を実行するためのソフトウェアを遂行する適宜の回路との組合せを含む該機能を実行する任意の方法を、包含すると想定される。そのような請求項で定義される発明は、多様な言及された手段により提供される機能が、請求項が要求する方法で組合せられかつ共に提供される、という事実に存在する。出願人はしたがって、そのような機能を提供する任意の手段を、ここに示されたものの等価物とみなす。発明の原理の多くの他の変更とその応用は、当業者には自明であり、ここでの教示により考慮される。したがって本発明の範囲は、ここに添付された請求項のみにより限定される。
【図面の簡単な説明】
【００４１】
【図１】本発明に従う、パケット・セットからのトラヒック・ダイジェストの抽出の方法論の一例を示す。
【図２】本発明のトラヒック測定および解析技術を用いた、ネットワーク・ノードにより実行される工程の実施形態の例である。
【図１】
0004727275.tif 000098
【図２】
0004727275.tif 000099