JP2005295562A - 高速トラヒック測定および解析の方法論とプロトコル - Google Patents

Abstract

【課題】ネットワーク・レベルのトラヒック測定／解析問題を、一連のセット濃度決定（ＳＣＤ）問題として定式化する。
【解決手段】確率的個別サンプル計量技術の進歩を活用して、セット濃度、従ってネットワーク・レベルの関心のあるトラヒック測定が、ネットワーク・ノード、すなわちルータ間の極度に軽量なトラヒック・ダイジェスト（ＴＤ）の交換を経由して、分散方式で計算されることができる。一度必要なＴＤが受信されると、一連のセット濃度決定問題を解くことにより、そのローカル・リンクの各々の関心のあるトラヒック測定を、ルータは推定することができる。ローカルな測定結果は次にドメイン内に分散され、従って各々のルータがネットワーク・レベルの概観を構築することができる。トラヒック測定が受信された後は、ローカルに最少二乗誤差（ＭＳＥ）最適化を実行することにより、各々のルータは関連する測定／推定誤差を更に削減することができる。
【選択図】図１

Description

本出願は一般に通信ネットワークに関し、特に通信ネットワークのデータ・パケットの測定と解析に関する。

本出願は、２００４年３月３１日に出願され、本出願に参考として添付された出願番号第６０／５５８２３０号の仮出願の優先権を主張する。
近年世界は、高速データ・ネットワークの急増およびこれらのネットワークをサポートするプロトコル／サービスの組の急速な拡張を目撃している。ネットワークの監視およびトラヒック測定の技術の進展は、これまでのところこれらのネットワークの膨大な発展と共にその動作速度に追いついていない。この欠点のために、ネットワークのオペレータはこれらのネットワークで何が起こっているか正確に把握することがずっとできないでいる。これはしたがって、ネットワークを適切かつ効率的に動作させ管理する能力を危うくしている。大規模高速ネットワークに対する、包括的で展開可能なネットワークの監視および端末間のトラヒック解析の、インフラストラクチャの緊急な必要性が生じている。そのようなインフラストラクチュアは、通信フローの経路が異なる型式の、予期できるまたは予期できないイベントのためにセッションの途中で動的かつ予測不可能に変更される、インターネットのような無接続データ・ネットワークについて特に重要である。そのようなイベントは、ネットワーク要素の故障、非決定論的負荷平衡スキーム（例えば等費用多重経路（ＥＣＭＰ））、ソフトウェア／ハードウェアのバグ、プロトコルの誤構成を含む。現在のところ、多くのネットワーク・オペレータは、ネットワーク内の個々の通信フローの端末から端末までの経路のまったく不適切なサンプリングを得る、「トレースルート」のような原始的な診断ツールにのみ頼らざるを得ない。

トラヒック測定／解析の方法論およびインフラストラクチュアの最近の研究は、大規模ＩＳＰ用の起点−終点（ＯＤペア）トラヒック・マトリックス推定や、欺瞞ＤＤｏＳの攻撃と取り組むためのＩＰ−ベースのネットワークにおける、トレース・バックサービスのサポートのような、多数の重要な実生活のアプリケーションの要求により強く駆動されてきた。Ａ．Ｍｅｄｉｎａ、Ｎ．Ｔａｆｔ、Ｋ．Ｓａｌａｍａｔｉａｎ、Ｓ．Ｂｈａｔｔａｃｈａｒｙｙａ、Ｃ．Ｄｉｏｔ、「Ｔｒａｆｆｉｃ Ｍａｔｒｉｘ ｅｓｔｉｍａｔｉｏｎ：Ｅｘｉｓｔｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ ｎｅｗ ｄｉｒｅｃｔｉｏｎｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００２年８月［Ｍｅｄｉ ０２］、Ｙ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈａｎ、Ｎ．Ｄｕｆｆｉｅｌｄ、Ａ．Ｇｒｅｅｎｂｅｒｇ、「Ｆａｓｔ Ａｃｃｕｒａｔｅ Ｃｏｍｐｕｔａｔｉｏｎ ｏｆ Ｌａｒｇｅ−Ｓｃａｌｅ ＩＰ Ｔｒａｆｆｉｃ Ｍａｔｒｉｃｅｓ ｆｒｏｍ Ｌｉｎｋ Ｌｏａｄｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｍｅｔｒｉｃｓ、２００３年６月［Ｚｈａｎｇ ０３ａ］およびＹ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈ、Ｃ．Ｌｕｎｄ、Ｄ．Ｄｏｎｏｈｏ、「Ａｎ Ｉｎｆｏｒｍａｔｉｏｎ−Ｔｈｅｏｒｅｔｉｃ Ａｐｐｒｏａｃｈ ｉｎ Ｔｒａｆｆｉｃ Ｍａｔｒｉｘ Ｅｓｔｉｍａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００３年８月［Ｚｈａｎｇ ０３ｂ］で論じられたトラヒック・マトリックス推定問題では、その目的は大規模ＩＰネットワークのＯ−Ｄノード・ペアの間のトラヒック要求を、リンク−ロード測定のみを用いて推定することである。この問題の起源は、マーケットの最も営利的なギガビット・ルータによる、安価なスケーラブル・パーフロー・カウンタのサポートがないことから来ている。例えば、シスコネット・フロー・テクノロジー、シスコ、ＩＯＳネット・フローｈｔｔｐ：／／ｗｗｗ．ｃｉｓｃｏ．ｃｏｍ／ｗａｒｐ／ｐｕｂｌｉｃ／７３２／Ｔｅｃｈ／ｎｍｐ／ｎｅｔｆｌｏｗ／ｉｎｄｅｘ．ｓｈｔｍｌは、精密なパーフロー・トラヒック統計を集めるのに使用できる一方で、その恐ろしい記録および帯域幅の要求は、１０Ｇｂｐｓのネットワークでの使用を不適当にする。測定インフラストラクチュアにおけるそのような不適切／欠陥と取り組むために、必要とされるＯ−Ｄペア・トラヒック・マトリックスを推定するために、研究者はリンク−ロード測定をＯ−Ｄペア・トラヒック分布の追加の仮定と組合せる手段を用いてきた。例えば、［Ｍｅｄｉ ０２、Ｚｈａｎｇ ０３ａ、Ｚｈａｎｇ ０３ｂ］では、重力モデルの異なる変異体が、すべてのＯ−Ｄペアの間のネットワーク・トラヒック分布をモデル化するために、輸送分野から適用されており、［Ｖａｒｄ ９６］Ｙ．Ｖａｒｄｉ、「Ｎｅｔｗｏｒｋ Ｔｏｍｏｇｒａｐｈｙ：ｅｓｔｉｍａｔｉｎｇ ｓｏｕｒｃｅ−ｄｅｓｔｉｎａｔｉｏｎ ｔｒａｆｆｉｃ ｉｎｔｅｎｓｉｔｉｅｓ ｆｒｏｍ ｌｉｎｋ ｄａｔａ」、Ｊｏｕｒｎａｌ ｏｆ Ａｍｅｒｉｃａｎ Ｓｔａｔｉｓｔｉｃｓ Ａｓｓｏｃｉａｔｉｏｎ、９１、ｐｐ．３６５−３７７、１９９６年、［Ｖａｒｄ ９５］では、２次のリンク−ロード統計をＯ−Ｄペア・トラヒック分布と関連づけるためにポアソン仮定が用いられている。同様のガウス仮定が、Ｊ．Ｃａｏ、Ｄ．Ｄａｖｉｓ、Ｓ．Ｖ．Ｗｉｅｌ、Ｂ．Ｙｕ、「Ｔｉｍｅ−ｖａｒｙｉｎｇ ｎｅｔｗｏｒｋ ｔｏｍｏｇｒａｐｈｙ」、Ｊｏｕｒｎａｌ ｏｆ Ａｍｅｒｉｃａｎ Ｓｔａｔｉｓｔｉｃｓ Ａｓｓｏｃｉａｔｉｏｎ、９５、ｐｐ．１０６３−１０７５、２０００年［Ｃａｏ ００］でなされている。実のところ、リンク−ロード測定のみで与えられるＯ−Ｄトラヒック・マトリックス推定の問題は、「ネットワーク・トモグラフィ」と呼ばれる新しいフィールド・リサーチの形成につながっていた。不幸なことに現在までに提案されたネットワーク・トモグラフィベースのほとんどの解は、それらのトラヒック分布の仮定の有効性に関して高度に敏感であり、すなわち頑丈でなかった。このトモグラフィベースのアプローチはまた、それから測定／構成情報が抽出されて対照される、多重動作データベースの間の正確性、同期および一貫性に強く依存する。（そのようなデータベースは、リンク−ロード用のＳＮＭＰＭＩＢと同様に、ルータのフォワーディング・テーブル、ルータ構成ファイルを含む。）上記のモデル化と動作の仮定はまた、トモグラフィベースのトラヒック測定／推定のスキームを、ネットワーク要素／データベースの適切な機能もトラヒック分布の正規性も仮定されないネットワーク故障検出／診断に対して、ほとんど役に立たないものにならしめる。

最近、代案のパケット・トラジェクトリ・ベーストラヒック監視／解析アプローチが、Ｎ．Ｇ．Ｄｕｆｆｉｅｌｄ、Ｍ．Ｇｒｏｓｓｇｌａｕｓｅｒ、「Ｔｒａｊｅｃｔｏｒｙ Ｓａｍｐｌｉｎｇ ｆｏｒ Ｄｉｒｅｃｔ Ｔｒａｆｆｉｃ Ｏｂｓｅｒｖａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２０００年８月、ｐｐ．２７１−２８２［Ｄｕｆｆ ００］およびＡ．Ｃ．Ｓｎｏｅｒｅｎ、Ｃ．Ｐａｒｔｒｉｄｇｅ、Ｌ．Ａ．Ｓａｎｃｈｅｚ、Ｃ．Ｅ．Ｊｏｎｅｓ、Ｆ．Ｔｃｈａｋｏｕｎｔｉｏ、Ｓ．Ｔ．Ｋｅｎｔ、Ｗ．Ｔ．Ｓｔｒａｙｅｒ、「Ｈａｓｈ−ｂａｓｅｄ ＩＰ Ｔｒａｃｅｂａｃｋ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００１年８月、ｐｇ３−１４［Ｓｎｏｅ ０１］により提案され、それらでは各々のノード（ルータ）が最近取り扱ったすべてのパケットの圧縮された要約またはダイジェストを保持する。［Ｄｕｆｆ ００］、［Ｓｎｏｅ ０１］の双方で、ダイジェストはブルーム・フィルタの形式である。例えばＢ．Ｂｌｏｏｍ、「Ｓｐａｃｅ／Ｔｉｍｅ ｔｒａｄｅ−ｏｆｆｓ ｉｎ ｈａｓｈ ｃｏｄｉｎｇ ｗｉｔｈ ａｌｌｏｗａｂｌｅ ｅｒｒｏｒｓ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ １３、１９７０年７月１３日ｐｐ．４２２−４２６［Ｂｌｏｏ ７０］およびＡ．Ｂｒｏｄｅｒ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｎｅｔｗｏｒｋ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｂｌｏｏｍ Ｆｉｌｔｅｒｓ：Ａ Ｓｕｒｖｅｙ」、Ａｌｌｅｒｔｏｎ Ｃｏｎｆｅｒｅｎｃｅ、２００２、ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｓ．ｈａｒｖａｒｄ．ｅｄｕ／〜ｍｉｃｈａｅｌｍで入手可能、［Ｂｒｏｄ ０２］では、ノードに到着するすべてのパケットを更新し、文書記録の目的と同様に、将来のオフラインのトラヒック解析をサポートするために、中央のサーバに周期的にアップロードする。これらの大変有用なノード・トラヒック・ダイジェストで武装して、中央サーバはトラヒック・フロー・パターンとネットワーク・レベルのフロー毎／商品測定を構築できるばかりではなく、（近い）過去にネットワークを通った任意の与えられたパケットの、端末から端末までの経路、またはいわゆるトラジェクトリについての質問に答えることもできる。任意の与えられた個々のパケットに対するトラジェクトリの質問に回答できる能力には、多大な費用がかかる。すべての個々の到来するパケットの十分な情報を記録するために、ブルーム・フィルタは十分大きくなければならない。効率的なメモリ対ブルーム・フィルタの偽陽性トレードオフを備えていても、高い蓋然性でＮの異なるパケットの署名を捕らえて正しく区別するために、Ｏ（Ｎ）ビットのメモリを必要とする。［Ｓｎｏｅ ０１］では、そのようなシステムは、記憶装置内に単位時間当たりノードのリンク能力の約０．５％を必要とすると見積もっている。１０Ｇｂｐｓのリンクでは、これは監視時間の１秒毎に５０Ｍビットの記憶と換算される。そのような重量級のトラヒック・ダイジェストのアプローチは、システムのメモリ記録と通信の要求にストレスを与えるばかりでなく、リンク速度および／または監視期間の増加として悪い方向に作用する。
米国仮出願第６０／５５８２３０号 Ａ．Ｍｅｄｉｎａ、Ｎ．Ｔａｆｔ、Ｋ．Ｓａｌａｍａｔｉａｎ、Ｓ．Ｂｈａｔｔａｃｈａｒｙｙａ、Ｃ．Ｄｉｏｔ、「Ｔｒａｆｆｉｃ Ｍａｔｒｉｘ ｅｓｔｉｍａｔｉｏｎ：Ｅｘｉｓｔｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ ｎｅｗ ｄｉｒｅｃｔｉｏｎｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００２年８月［Ｍｅｄｉ ０２］ Ｙ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈａｎ、Ｎ．Ｄｕｆｆｉｅｌｄ、Ａ．Ｇｒｅｅｎｂｅｒｇ、「Ｆａｓｔ Ａｃｃｕｒａｔｅ Ｃｏｍｐｕｔａｔｉｏｎ ｏｆ Ｌａｒｇｅ−Ｓｃａｌｅ ＩＰ Ｔｒａｆｆｉｃ Ｍａｔｒｉｃｅｓ ｆｒｏｍ Ｌｉｎｋ Ｌｏａｄｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｍｅｔｒｉｃｓ、２００３年６月［Ｚｈａｎｇ ０３ａ］ Ｙ．Ｚｈａｎｇ、Ｍ．Ｒｏｕｇｈ、Ｃ．Ｌｕｎｄ、Ｄ．Ｄｏｎｏｈｏ、「Ａｎ Ｉｎｆｏｒｍａｔｉｏｎ−Ｔｈｅｏｒｅｔｉｃ Ａｐｐｒｏａｃｈ ｉｎ Ｔｒａｆｆｉｃ Ｍａｔｒｉｘ Ｅｓｔｉｍａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００３年８月［Ｚｈａｎｇ ０３ｂ］ ［Ｖａｒｄ ９６］Ｙ．Ｖａｒｄｉ、「Ｎｅｔｗｏｒｋ Ｔｏｍｏｇｒａｐｈｙ：ｅｓｔｉｍａｔｉｎｇ ｓｏｕｒｃｅ−ｄｅｓｔｉｎａｔｉｏｎ ｔｒａｆｆｉｃ ｉｎｔｅｎｓｉｔｉｅｓ ｆｒｏｍ ｌｉｎｋ ｄａｔａ」、Ｊｏｕｒｎａｌ ｏｆ Ａｍｅｒｉｃａｎ Ｓｔａｔｉｓｔｉｃｓ Ａｓｓｏｃｉａｔｉｏｎ、９１、ｐｐ．３６５−３７７、１９９６年、［Ｖａｒｄ ９５］ Ｊ．Ｃａｏ、Ｄ．Ｄａｖｉｓ、Ｓ．Ｖ．Ｗｉｅｌ、Ｂ．Ｙｕ、「Ｔｉｍｅ−ｖａｒｙｉｎｇ ｎｅｔｗｏｒｋ ｔｏｍｏｇｒａｐｈｙ」、Ｊｏｕｒｎａｌ ｏｆ Ａｍｅｒｉｃａｎ Ｓｔａｔｉｓｔｉｃｓ Ａｓｓｏｃｉａｔｉｏｎ、９５、ｐｐ．１０６３−１０７５、２０００年［Ｃａｏ ００］ Ｎ．Ｇ．Ｄｕｆｆｉｅｌｄ、Ｍ．Ｇｒｏｓｓｇｌａｕｓｅｒ、「Ｔｒａｊｅｃｔｏｒｙ Ｓａｍｐｌｉｎｇ ｆｏｒ Ｄｉｒｅｃｔ Ｔｒａｆｆｉｃ Ｏｂｓｅｒｖａｔｉｏｎ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２０００年８月、ｐｐ．２７１−２８２［Ｄｕｆｆ ００］ Ａ．Ｃ．Ｓｎｏｅｒｅｎ、Ｃ．Ｐａｒｔｒｉｄｇｅ、Ｌ．Ａ．Ｓａｎｃｈｅｚ、Ｃ．Ｅ．Ｊｏｎｅｓ、Ｆ．Ｔｃｈａｋｏｕｎｔｉｏ、Ｓ．Ｔ．Ｋｅｎｔ、Ｗ．Ｔ．Ｓｔｒａｙｅｒ、「Ｈａｓｈ−ｂａｓｅｄ ＩＰ Ｔｒａｃｅｂａｃｋ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００１年８月、ｐｇ３−１４［Ｓｎｏｅ ０１］ Ｂ．Ｂｌｏｏｍ、「Ｓｐａｃｅ／Ｔｉｍｅ ｔｒａｄｅ−ｏｆｆｓ ｉｎ ｈａｓｈ ｃｏｄｉｎｇ ｗｉｔｈ ａｌｌｏｗａｂｌｅ ｅｒｒｏｒｓ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ １３、１９７０年７月１３日ｐｐ．４２２−４２６［Ｂｌｏｏ ７０］ Ａ．Ｂｒｏｄｅｒ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｎｅｔｗｏｒｋ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｂｌｏｏｍ Ｆｉｌｔｅｒｓ：Ａ Ｓｕｒｖｅｙ」、Ａｌｌｅｒｔｏｎ Ｃｏｎｆｅｒｅｎｃｅ、２００２、ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｓ．ｈａｒｖａｒｄ．ｅｄｕ／〜ｍｉｃｈａｅｌｍで入手可能、［Ｂｒｏｄ ０２］ Ａ．Ｂｒｏｄｅｒ、「Ｏｎ ｔｈｅ ｒｅｓｅｍｂｌａｎｃｅ ａｎｄ ｃｏｎｔａｉｎｍｅｎｔ ｏｆ ｄｏｃｕｍｅｎｔｓ」、Ｃｏｍｐｒｅｓｓｉｏｎ ａｎｄ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ Ｓｅｑｕｅｎｃｅｓ（ＳＥＱＵＥＮＣＥＳ）、Ｐｏｓｉｔａｎｏ、Ｉｔａｌｙ、９７年６月［Ｂｒｏｄ ９７］ Ｊ．Ｂｙｅｒｓ、Ｊ．Ｃｏｎｓｉｄｉｎｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、Ｓ．Ｒｏｓｔ、「Ｉｎｆｏｒｍｅｄ Ｃｏｎｔｅｎｔ Ｄｅｌｉｖｅｒｙ Ａｃｒｏｓｓ Ａｄａｐｔｉｖｅ Ｏｖｅｒｌａｙ Ｎｅｔｗｏｒｋｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００２年８月［Ｂｙｅｒ ０２］。 Ａ．Ｂｒｏｄｅｒ、Ｍ．Ｃｈａｒｉｋａｒ、Ａ．Ｍ．Ｆｒｉｅｚｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｍｉｎ−ｗｉｓｅ ｉｎｄｅｐｅｎｄｅｎｔ ｐｅｒｍｕｔａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ、６０（３）、２０００、ｐｐ．６３０−６５９．［Ｂｒｏｄ ００］ Ｐ．Ｆｌａｊｏｌｅｔ、Ｇ．Ｎ．Ｍａｒｔｉｎ、「Ｐｒｏｂａｂｌｉｓｔｉｃ ｃｏｕｎｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄａｔａｂａｓｅ ａｐｐｌｉｃａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ、３１（２）、１９８５、ｐｐ．１８２−２０９［Ｆｌａｊ ８５］ Ｍ．Ｄｕｒａｎｄ、Ｐ．Ｆｌａｊｏｌｅｔ、「Ｌｏｇｌｏｇ Ｃｏｕｎｔｉｎｇ ｏｆ Ｌａｒｇｅ Ｃａｒｄｉｎａｌｉｔｉｅｓ」、ｓｕｂｍｉｔｔｅｄ ｔｏ Ｅｕｒｏｐｅａｎ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｌｇｏｒｉｔｈｍｓ、ＥＳＡ’２００３、２００３年４月［Ｄｕｒａ ０３］ Ｃ．Ｅｓｔａｎ、Ｇ．Ｖａｒｇｈｅｓｅ、Ｍ．Ｆｉｓｋ、「Ｃｏｕｎｔｉｎｇ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ａｃｔｉｖｅ ｆｌｏｗｓ ｏｎ ａ ｈｉｇｈ ｓｐｅｅｄ ｌｉｎｋ」、ＡＣＭ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ、３２巻３号２００２年３月［Ｅｓｔａ ０２］ Ｐ．Ｂ．Ｇｉｂｂｏｎｓ、Ｓ．Ｔｉｒｔｈａｐｕｒａ、「Ｅｓｔｉｍａｔｉｎｇ Ｓｉｍｐｌｅ Ｆｕｎｃｔｉｏｎｓ ｏｎ ｔｈｅ Ｕｎｉｏｎ ｏｆ Ｄａｔａ Ｓｔｒｅａｍｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ ＳＰＡＡ、Ｃｒｅｔｅ Ｉｓｌａｎｄ、Ｇｒｅｅｃｅ、２００１［Ｇｉｂｂ ０１］

従来技術での進歩は、軽量トラヒック・ダイジェスト経由のトラヒック解析の分散構造（ＤＡＴＡＬＩＴＥ）と名付けられた、ネットワーク・トラヒック解析の効率的方法を通して達成され、大規模１０Ｇｂｐｓ＋パケット切り替えネットワークの、一般的なトラヒック測定および解析（ＴＭＡ）機能をサポートする、新しい分散アルゴリズムおよびプロトコルの組を導入する。これらの機能は、以下を含むがそれに限定はされない：
・トラヒック・フロー・パターン／経路監視、診断およびネットワーク維持；
・容量計画およびトラヒック工学目的の起点−終点（ＯＤ）トラヒック負荷マトリックスの推定；
・インターＩＳＰ（ＡＳｅｓ）料金支払およびエンドユーザ精算／課金目的のトラヒック測定；
・分散サービス妨害（ＤＤｏＳ）攻撃の攻撃パケットの発信地のトレース・バック

ネットワーク中のトラヒック測定／解析問題を、一連のセット濃度決定（ＳＣＤ）問題として、定式化する。蓋然的で明解なサンプル集計技術の最近の進歩をてこに使って、セット濃度にしたがってネットワーク中の関心あるトラヒック測定が、ネットワーク・ノードすなわちルータの間の極度に軽量なトラヒック・ダイジェスト（ＴＤ）の交換を経由して、分散の方法で計算されることができる。ＮのパケットのＴＤは、メモリ記憶のＯ（ｌｏｇｌｏｇＮ）ビットのみを必要とする。そのようなＯ（ｌｏｇｌｏｇＮ）サイズのＴＤの演算は、ワイヤ速度１０Ｇｂｐｓおよびそれ以上の効率的なハードウェアの具体化に従順である。

サイズの小さいＴＤを与えると、ＯＳＰＦリンク状態パケット（ＬＳＰｓ）またはＩ−ＢＧＰ制御メッセージのような、既存の制御メッセージ内部のオペイク・データ・オブジェクトとしてそれらをピギーバックすることにより、ノードのＴＤをドメイン内のすべてのルータに分散することができる。一度必要なＴＤが受信されると、一連のセット濃度決定問題を解くことにより、そのローカル・リンクの各々の関心のあるトラヒック測定を、ルータは推定することができる。我々が後に論じるように、関心のあるトラヒック測定は一般的にリンク毎、トラヒックが集まったパケット・カウント（またはフロー・カウント）毎の形式であり、ここでトラヒックの集まりは同じ起点および／または終点ノード（またはリンク）および／または同じ中間ノード（またはリンク）を共有する、パケットのグループにより定義される。ローカルな測定結果は次にドメイン内に分散され、したがって各々のルータが異なるトラヒック・コモデティの経路／フロー・パターンのネットワーク・レベルの概観を構築することができるが、ここでコモデティは同じ起点および／または終点のノードまたはリンクを共有するパケットのグループにより定義される。初期のネットワーク・レベルのトラヒック測定が受信された後は、ネットワーク・レベルのコモデティ・フロー節約制約に基づいて、ローカルに最少二乗誤差（ＭＳＥ）最適化を実行することにより、各々のルータは関連する測定／推定誤差をさらに削減することができる。

ネットワークが周期的に軽量ＴＤで溢れさせられ、結果としてローカル・トラヒックを推定する「放送」モードのサポートに加えて、ＴＤの分散とローカル・トラヒックの推定がオンデマンドかつ関係者のみに知らせる原則で、ネットワーク内の関連したノードの部分集合により、実行される「質問と回答」モードを経由して、ＤＡＴＡＬＩＴＥはトラヒック測定／解析を同様にサポートする。「質問と回答」モードは、超精細で高分解能のトラヒック測定／解析が必要である、臨時で特別なトラヒック調査をサポートするために特に有用である。

要約すると、直接測定アプローチをとることにより、ＤＡＴＡＬＩＴＥは無効なトラヒック・モデルや、ネットワーク・トモグラフィ・アプローチを悩ます動作上の仮定に起因する問題を避ける。ＤＡＴＡＬＩＴＥスキームと現存するトラジェクトリ・ベースのそれの間にいくつかの高度な共通性があるにもかかわらず、それらの間にはキーとなる差異がある：第１にトラヒック測定問題を一連のセット濃度決定問題として定式化することにより、最少の通信負荷でトラヒック解析を分散方式で実行するために、明解なサンプル集計技術の最近の進歩を、てこにすることができる。第２に、個々のパケット１つの代わりにトラヒック集合体の振る舞いの測定と解析に焦点を合わせることにより、ＤＡＴＡＬＩＴＥのためのシステム・メモリと通信帯域幅の要求が大いに削減された。結果的に、現存するトラジェクトリ・ベースのシステムにより採用される重量級の中央化アプローチとは反対に、ＤＡＴＡＬＩＴＥは分散演算モデルを取り入れることが可能になる。

本発明のより完全な理解は、図面と共にする以下の詳細は発明の記述の考察から得られる。図では同様の参照番号は同様の要素を表す。
本発明は、データ・パケット・ネットワークのネットワーク測定および解析の改良された効率を提供する方法論である。本発明の例としての実施形態が従来の高速度ネットワークと組合せて記載されるが、無線ネットワークや輸送ネットワークのような、他のネットワークにも適用可能であることが、当業者には自明であろう。

［Ｓｎｏｅ ０１］でＩＰトレース・バックをサポートする設計者には、任意の与えられた個々のパケットについてのトラジェクトリの質問に答える能力が必要であると考えられる一方で、以下で大抵のトラヒック測定／解析用途には、ＩＰトレース・バックを含めて、それは過剰であることを論じる。この議論は、これらのほとんどのアプリケーションにおいて、一連の分離した個別パケットのトラジェクトリおよび／またはトラフィック量の代わりに、所与のパケットのグループ又は、いわゆるトラフィック集合のトラジェクトリおよび／またはトラフィック量を知ることで十分であるという観察に基づく。［Ｓｎｏｅ ０１］のシステムが、１つの特別なパケットの起点の追跡のような、より強力なネットワークの用途をサポートできると誰かが論じるかもしれない一方で、我々はネットワーク・レベルのトラヒック解析／監視がそのような機能を提供する最良の方法ではないと信じている。その代わりに、特定用途レベルの機能は、末端システムに近い用途レベルでよりよくサポートされることができる。ネットワーク・トラヒック監視／解析インフラストラクチュアは、経路診断、トラヒック工学およびフロー・パターン解析のような、ネットワークおよび／またはトランスポート・レイヤの機能のサポートにその努力をフォーカスするべきであると考えている。

多くの場合関心のあるトラヒックの集合体の定義は、用途の文脈で明らかに定義される。本発明では、軽量トラヒック・ダイジェスト経由のトラヒック解析の分散構造（ＤＡＴＡＬＩＴＥ）を以下で定義されるトラヒックの集合体に第１に焦点を当てる：
（１）それらの起点および／または終点のノード（またはリンク）または
（２）トラヒックのそのグループが通過している特定のリンクまたはノードの組。
以下に示すように、そのようなトラヒックの集合体は、ネットワークの故障診断と同様に、トラヒック・マトリックス推定、経路検査を含む実際的なトラヒック測定／解析（ＴＭＡ）用途の幅広い領域の中心なので、そのような集合体の定義に焦点を合わせることに決定した。これらの主要なトラヒックの集合体の型式に加えて、提案されるＤＡＴＡＬＩＴＥインフラストラクチュアはまた、主要なそれの部分集合である、例えば与えられたプロトコル型式および／またはポート番号のパケットのグループの、より精細なトラヒックの集合体をサポートする。

交差（共通集合）セット濃度決定問題としてのトラヒック測定／解析
この章では一連の交差セット濃度決定（ＩＳＣＤ）問題としてのトラヒック測定／解析（ＴＭＡ）問題の定式化を記述する。ネットワークＧの、有向グラフ表現を考慮されたい。Ｇ＝（Ｖ，Ｅ）ここで、Ｖはノードのセット、Ｅは方向リンクのセットである。（ｉ，ｊ）∈Ｅをノードｉからノードｊへの方向リンクとする。Ｌ_ｉ，ｊを与えられた測定時間の長さＴ秒間にリンク（ｉ，ｊ）を通過しているパケットのセットとする。さて今、飛行中のパケットに起因するフリンジ効果が無視できるように、ネットワーク内の最大エンド−エンド遅延より十分に長い測定期間を仮定する。パス遅延の効果は、多重時間インデックス・ノード・トラヒック・ダイジェストを保持することにより明らかにすることができる。実際に、時間インデックストラヒック・ダイジェストは、ネットワーク・パス遅延測定のサポートに用いることができる。Ｏ_ｉ（またはＤ_ｉ）を、同じ測定期間内にノードｉから発された（または到着した）パケットのセットとする。用語「発された」（または「到着した」）により、実際にそのノードから生成された（またはそこからネットワークを出ていく）パケットを意味している。パケットは可能なソースアドレススプーフのために、それが主張しているソース・ノードで実は生成されていないかもしれないので、用語「ソース」または「デスティネーション」の使用を避ける。同様にパケットは、経路上の問題や消失のために、それが意図する宛先ノードには到着しないかもしれない。

与えられた測定期間内に、我々が関心を持つトラヒックの集合体が以上に定義したパケットのセットの交差として、容易に表されることができる。我々のアプローチを示すため、以下の２つの一般的な（かつ基礎的な）ＴＭＡタスクを考える。

サンプルＴＭＡタスク＃１：
このタスクの目的は、ネットワーク中のすべてのＯ−Ｄノード・ペアの間の、ルート・パターンおよびトラヒックの量を決定することである。このような目的で、それらのＯ−Ｄノード・ペアとしてリンク（ｉ，ｊ）∈Ｅ、ｋ＝（ｓ，ｄ）∈Ｖ×Ｖを通過するパケットのセット

を考える。

は上記に定義された他のパケットのセットの交差として表されることもできることに留意されたい

。キーとなる観察点は、このタスクには（トラヒック・マトリックス推定、フロー・パターン解析、トラヒック・トレース・バック、経路／ネットワーク故障検出／診断、トラヒック工学のような他のＴＭＡアプリケーションの広範な領域と同様に）、

の完全な詳細の代わりに、

すなわち

の濃度を知れば十分であることである。例えばサンプルＴＭＡタスク＃１の目的は、すべてのリンク（ｉ，ｊ）∈ＥおよびすべてのＯ−Ｄノード・ペアｋ＝（ｓ，ｄ）∈Ｖ×Ｖに対して

を知るのみで達成されることができる。

サンプルＴＭＡタスク＃２
このタスクで起点ノード、それらが寄与するトラヒック量およびいくつかのＤＤｏＳビクチムであるかもしれない、与えられたダウン・ストリーム・ノードｄに到着して終了する、パケットのグループのアップ・ストリーム・フロー・パターンを決定したい、トレース・バックアプリケーションを考察する。このタスクを実行するために、

およびｋ＝（^＊，ｄ）であるすべてのリンク（ｉ，ｊ）∈Ｅについての

を決定する必要があるのみである（ここで^＊はワイルドカードである）。同様に、

およびｋ＝（ｓ，^＊）であるすべてのリンク（ｉ，ｊ）∈Ｅに対し

を決定することにより、与えられたノードｓから発したパケットの、終点、ダウン・ストリーム・ルート・パターンおよびフロー量をトレースすることができる。
上記の観察に基づいて、ＤＡＴＡＬＩＴＥの基本的なアイデアは、ネットワーク中どこでもできる方法で、

の分散演算／推定をサポートするインフラストラクチュアを提供することである。ここで、

は、以上で言及したＯ_ｉ、Ｄ_ｄおよびＬ_ｉ，ｊのようないくつかのパケットのセットの交差の形式で表されている。以下に議論されるように、（［Ｄｕｆｆ ００，Ｓｎｏｅ ０１］の場合と同様）

の完全な詳細の代わりに、

にフォーカスすることにより、ＤＡＴＡＬＩＴＥのシステム記憶と通信帯域幅の要求は、ＤＡＴＡＬＩＴＥが１０Ｇｂｐｓ＋ネットワークのＴＭＡをサポートできるようにするまでに、十分削減されることができる。
いくつかの特定のパケット・セットの交差として

を表すことにより、我々の定式化は実質的にＴＭＡ問題を、一連のいわゆる交差セット濃度決定（ＩＳＣＤ）問題に変換する。異なるロケーションに分散された多重セットの交差の濃度の決定問題は、（１）ＷＷＷの類似のウェブページを特定するサーチ・エンジンを補助する文脈で最近調査された。Ａ．Ｂｒｏｄｅｒ、「Ｏｎ ｔｈｅ ｒｅｓｅｍｂｌａｎｃｅ ａｎｄ ｃｏｎｔａｉｎｍｅｎｔ ｏｆ ｄｏｃｕｍｅｎｔｓ」、Ｃｏｍｐｒｅｓｓｉｏｎ ａｎｄ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ Ｓｅｑｕｅｎｃｅｓ（ＳＥＱＵＥＮＣＥＳ）、Ｐｏｓｉｔａｎｏ、Ｉｔａｌｙ、９７年６月［Ｂｒｏｄ ９７］および（２）ピアトゥピアネットワーク上の効率的ファイルサーチ／スワップをサポートするプロトコルの設計、Ｊ．Ｂｙｅｒｓ、Ｊ．Ｃｏｎｓｉｄｉｎｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、Ｓ．Ｒｏｓｔ、「Ｉｎｆｏｒｍｅｄ Ｃｏｎｔｅｎｔ Ｄｅｌｉｖｅｒｙ Ａｃｒｏｓｓ Ａｄａｐｔｉｖｅ Ｏｖｅｒｌａｙ Ｎｅｔｗｏｒｋｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ Ｓｉｇｃｏｍｍ、２００２年８月［Ｂｙｅｒ ０２］。［Ｂｒｏｄ９７］と［Ｂｙｅｒ０２］は双方が、Ａ．Ｂｒｏｄｅｒ、Ｍ．Ｃｈａｒｉｋａｒ、Ａ．Ｍ．Ｆｒｉｅｚｅ、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ、「Ｍｉｎ−ｗｉｓｅ ｉｎｄｅｐｅｎｄｅｎｔ ｐｅｒｍｕｔａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ、６０（３）、２０００、ｐｐ．６３０−６５９．［Ｂｒｏｄ ００］の技術をセットＡ、Ｂのペアのいわゆる類似比｜Ａ∩Ｂ｜／｜Ａ∪Ｂ｜を推定するために、適用している。しかしながら、この技術により要求される情報交換の量は、関心のあるセットのサイズ、すなわちＯ（｜Ａ｜）またはＯ（｜Ｂ｜）に比例している。｜Ａ｜又は｜Ｂ｜が、測定時間に所与のリンクを通過するパケットの数に対応する我々の高速ＴＭＡアプリケーションにとって、これは実効不能である。40バイトのパケット、40Ｇｂｐｓのリンクにつき測定時間を１０数秒とすれば、｜Ａ｜は容易に数十億の範囲に達してしまうのである。ノーダル・ブルーム・フィルタの交換に基づく代替のアプローチでは、（［Ｄｕｆｆ ００，Ｓｎｏｅ ０１］により暗示されているように）、対応するブルーム・フィルタの類似のＯ（｜Ａ｜）メモリの要求量のために、同様に過度の記憶／通信帯域幅問題につきあたる。

個別サンプル計数経由分散交差濃度決定
分散ＩＳＣＤ問題を解くために、本発明であるＤＡＴＡＬＩＴＥは新しいアプローチを取る。第１にＩＳＣＤ問題を１つまたは以上の連合セット濃度決定（ＵＳＣＤ）問題に変換する。次にＵＳＣＤ問題を分散方式で解くために、最近のＯ（ｌｏｇｌｏｇ｜Ａ｜）個別サンプル計数アルゴリズムを適用する。実際に我々のアプローチは、［Ｂｒｏｄ ９７］および［Ｂｙｅｒ ０２］での上記のアプリケーションをその能力と拡張性を徹底的に改善するために、使用することができる。
その図式として、サンプルＴＭＡ＃２を思い出されたい、ここで

である。基本的なセット理論に基づいて、

は

の形式で表され：
ここで、｜Ｏ_ｓ｜は、測定期間内にノードｓから発される個別パケットの数である。定義により生成されるすべてのパケットは個別であり、｜Ｏ_ｓ｜はすべての起点となるネットワーク・ノードに対しある単一のパケット・カウント数として維持されることができる。｜Ｌ_ｉ，ｊ｜は、リンク（ｉ，ｊ）を通過する個別パケットの数である。Ｆｌａｊｏｌｅｔ、Ｍａｒｔｉｎ、Ｄｕｒａｎｄにより独創された、確率的個別サンプル計数技術を、すべてのリンク（ｉ，ｊ）∈Ｅについての｜Ｌ_ｉ，ｊ｜を把握するために適用する。Ｐ．Ｆｌａｊｏｌｅｔ、Ｇ．Ｎ．Ｍａｒｔｉｎ、「Ｐｒｏｂａｂｌｉｓｔｉｃ ｃｏｕｎｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄａｔａｂａｓｅ ａｐｐｌｉｃａｔｉｏｎｓ」、Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ、３１（２）、１９８５、ｐｐ．１８２−２０９［Ｆｌａｊ ８５］およびＭ．Ｄｕｒａｎｄ、Ｐ．Ｆｌａｊｏｌｅｔ、「Ｌｏｇｌｏｇ Ｃｏｕｎｔｉｎｇ ｏｆ Ｌａｒｇｅ Ｃａｒｄｉｎａｌｉｔｉｅｓ」、ｓｕｂｍｉｔｔｅｄ ｔｏ Ｅｕｒｏｐｅａｎ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｌｇｏｒｉｔｈｍｓ、ＥＳＡ’２００３、２００３年４月［Ｄｕｒａ ０３］。そのような技術の基本的な利点は、パケットのセットＬ_ｉ，ｊの必要な情報を要約するために、ダイジェストＯ（ｌｏｇｌｏｇＮ_ｍａｘ）−ビットを維持することしか、要求しないことである。ここでＮ_ｍａｘは、Ｌ_ｉ，ｊ中の個別サンプルの最大数である。本発明の文脈では、このダイジェストを

により表すＬ_ｉ，ｊのトラヒック・ダイジェスト（ＴＤ）と称する。

を維持する一方で、同じ測定期間内にそのリンクを通るパケットの単純なカウント数（複製を含む）を追跡するために、すべてのリンク（ｉ，ｊ）∈Ｅに対し単純パケット・カウンタＣ_ｉ，ｊを導入する。Ｃ_ｉ，ｊと｜Ｌ_ｉ，ｊ｜の間の大きな相違は、リンク（ｉ，ｊ）が経路ループの一部になった可能性があるといった、潜在的な経路問題を表す。こうして

の評価における残る企ては、｜Ｏ_ｓ∪Ｌ_ｉ，ｊ｜の計算である。ここで、｜Ｌ_ｉ，ｊ｜の推定に用いられる確率的個別サンプル計数技術は、分散方式で｜Ｏ_ｓ∪Ｌ_ｉ，ｊ｜を計算するために同様に拡張することができる。これは、ノードｓおよびノードｉそれぞれによりローカルに維持され、

、

により表される、パケット・セットＯ_ｓ、Ｌ_ｉ，ｊに対する、Ｏ（ｌｏｇｌｏｇＮ_ｍａｘ）サイズのＴＤの交換に基づいている。同様に、サンプルＴＭＡ＃１に対する

は、以下として表示される。

ここでも、式２のＲ．Ｈ．Ｓ．の連合セットの濃度の決定のために、上述のＯ（ｌｏｇｌｏｇＮ_ｍａｘ）の個別サンプル計数技術を使用することができる。要約すると、ＴＭＡ問題はいくつかの特定のパケット・セットの連合の濃度の決定に変換されることができる。より重要なことに、Ｏ−Ｄノード・ペア分類に基づいて、｜Ｖ｜^２型式のパケットに対する、全ネットワークの経路パターンおよびリンク毎のトラヒック量を決定するために、リンク毎の単一軽量ＴＤ（プラスリンク毎の単純パケット・カウンタ）のみを、このアプローチは必要とする。それを通ってパケットが実際にネットワークに入る（去る）ルータｉのリンクの特定により、それらのリンクのＴＤに基づいてルータｉを発した（到着した）パケット・セットのＴＤを導出することができる。そのためこれは、

および

を明示的に維持する必要がない。

一般的に、一連のセット連合の濃度に関する多重セットの交差の濃度を表現することは、可能である。特に、セットのリストＳ_１，Ｓ_２，．．．，Ｓ_ｎに対し、

である。
例えばリンクｌ_ｉ，ｊを通過するＯ−Ｄペア（ｓ，ｄ）を有するすべての４０バイトＴＣＰパケットである、関心のあるトラヒックの集合体の定義を精選するために我々が追加のセットの交差を適用するときに、式３は有用である。式３に基づいて、ＩＳＣＤ問題が式３のＲ．Ｈ．Ｓ．のセット連合の濃度の計算に常に変換されることができる。これはその代わりに、個別サンプル計数技術を用いて、分散方式で実行することができる。要約すると、本発明の解法アプローチは以下の工程からなる。
１．関心のあるＴＭＡ問題を、関心のあるいくつかの交差セットの濃度決定問題、またはいわゆる交差セット濃度決定（ＩＳＣＤ）問題に変換する。
２．式３を用いて、ＩＳＣＤ問題を、関心のあるいくつかのセット連合の濃度決定問題、またはいわゆるセット連合濃度決定（ＵＳＣＤ）問題に変換する。
３．Ｆｌａｊｏｌｅｔ、Ｍａｒｔｉｎ、Ｄｕｒａｎｄにより独創された、個別サンプル計数技術を用いて分散方式でＵＳＣＤ問題を解く［Ｄｕｒａ ０３］。

以下の章ではＦｌａｊｏｌｅｔ、Ｍａｒｔｉｎ、Ｄｕｒａｎｄによる、「ｌｏｇｌｏｇ個別サンプル計数」技術を復習し、次にそれがいかにＤＡＴＡＬＩＴＥ発明に適用できるのか、説明する。関連する注として、Ｃ．Ｅｓｔａｎ、Ｇ．Ｖａｒｇｈｅｓｅ、Ｍ．Ｆｉｓｋ、「Ｃｏｕｎｔｉｎｇ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ａｃｔｉｖｅ ｆｌｏｗｓ ｏｎ ａ ｈｉｇｈ ｓｐｅｅｄ ｌｉｎｋ」、ＡＣＭ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ、３２巻３号２００２年３月［Ｅｓｔａ ０２］は、高速リンク上のローカル・ネットワーク・フローの計数の推定のための［Ｆｌａｊ ８５］の個別サンプル計数アルゴリズムの変形をデザインしている。ＤＡＴＡＬＩＴＥではその要素（パケット）が地理的に分散された位置で観察される、パケットのセット連合の個別パケットの数を推定するために、［Ｄｕｒａ ０３］の技術を適用する。分散セット連合に対する代替の個別サンプル計数技術はまた、Ｐ．Ｂ．Ｇｉｂｂｏｎｓ、Ｓ．Ｔｉｒｔｈａｐｕｒａ、「Ｅｓｔｉｍａｔｉｎｇ Ｓｉｍｐｌｅ Ｆｕｎｃｔｉｏｎｓ ｏｎ ｔｈｅ Ｕｎｉｏｎ ｏｆ Ｄａｔａ Ｓｔｒｅａｍｓ」、Ｐｒｏｃｓ．ｏｆ ＡＣＭ ＳＰＡＡ、Ｃｒｅｔｅ Ｉｓｌａｎｄ、Ｇｒｅｅｃｅ、２００１［Ｇｉｂｂ ０１］。しかしながら、［Ｇｉｂｂ ０１］で提案されるスキームのメモリ必要量は、［Ｄｕｒａ ０３］のそれほどには魅力的でない。

ｌｏｇｌｏｇ個別サンプル計数技術
サンプルＳのセットを考える。ここで各々のパケットｓは、識別子ｉｄ_ｓを有する。同じ識別子を備えるサンプルは、複製として扱われる。［Ｄｕｒａ ０３］は、メモリのＯ（ｌｏｇｌｏｇＮ_ｍａｘ）ビットを有する、Ｓ内の個別サンプルの数の計数、すなわち｜Ｓ｜の問題を解くが、ここでＮ_ｍａｘはＳの個別サンプルの最大数である。これらのスキームは、以下の通りである。
第１に各々のサンプルの識別子が、ハッシュ関数ｈ（・）の入力として用いられ、ハッシュ関数は

の領域上で均一に分散された、ランダムな負でない整数を出力するが、ここで

はＮ_ｍａｘより大でなければならない。Ｒ_ｍａｘビット長のランダム二進ストリングとして、ハッシュ出力の二進表現を考察する。直感的に、ｈ（・）の出力は均一に分散しているので、Ｓ内にｎの個別サンプルがある場合、平均的にそれらのｎ／２^ｋが、「１」のビットが後に続く（ｋ−１）連続したゼロを伴うｈ（・）の出力を有する。（複製のサンプルはｈ（）に同じ出力を有するので、それらは集団的に１回のランダムトライアルに寄与するのみである。）

入力として二進のストリングｘを取り、（１＋ｘの連続する先行のゼロの最大数）の値を出力する、関数ｒ（ｘ）を定義する。例えば、ｘ＝００００１ＸＸＸ．．に対しては、ｒ（ｘ）＝５；ｘ＝１ＸＸＸ．．に対してはｒ（ｘ）＝１で、ここでＸは「任意の数」である。入力としてＳ内のすべてのサンプル識別子を考察する一方で、

を達成したｒ（ｈ（・））の最大値とする。それ故Ｒ（Ｓ）は、ｌｏｇ_２ｎの値の大体の目安を与えるであろう。実際Ｒは、１＋パラメータ１／２のｎ独立幾何学的変数の最大値と同じように精密に分散している。Ｒが付加偏倚１．３３および標準偏差１．８７を伴うｌｏｇ_２ｎを推定することを、示すことができる。実際、推定誤差を低減するため、複数のＲの値を得る異なるハッシュ関数を用い、ｌｏｇ_２ｎを推定するためにそれらの平均値を用いることができる。代わりに、ｎ（または等価的に｜Ｓ｜）を推定するために、以下の工程でいわゆる確率平均アルゴリズム（ＳＡＡ）を用いることもできる。
１．セットＳサンプルをｍ＝２^ｋバケットに、例えばサンプルのハッシュ出力の最後のｋビットに基づいて分離する。
２．Ｒ_ｊを、ｊ番目のバケットに対するＲの値とする。ｒ（・）への各々のサンプルのハッシュ出力の（Ｒ_ｍａｘ−ｋ）先頭ビットを入力することにより、Ｒ_ｊを１≦ｊ≦ｍで計算する。
３．以下の式を用いて、

、すなわち｜Ｓ｜の推定を計算する。

ここで、α_ｍはｍの関数である修正計数である。
［Ｄｕｒａ ０３］に示されているように、

の標準誤差σは、以下で与えられる。

例えば、ｍ＝２０４８に設定すると、２％の標準誤差が達成される。Ｎ_ｍａｘがＳの個別サンプルの最大数であることを思い出されたい。各々のバケット内の個別サンプルの平均数は約Ｎ_ｍａｘ／ｍなので、したがってＲ_ｍａｘで表されるＲ_ｊの最大値に対し、

であると規定するべきである。［Ｄｕｒａ ０３］には、各々のｍＲ_ｊの二進表現に必要なビット数は、以下に等しいことが示されている。

このように、この確率的個別サンプル計数スキームに対する動作メモリの必要Ｍは、以下である。
Ｍ＝ｍｌｏｇ_２Ｒ_ｍａｘ ｂｉｔｓ ．．．．．．．．．．．．．．．．． 式（７）
上記の個別サンプル計数スキームは、セットＳのサンプルが別個の位置に観察（または記憶）される、分散の実現に容易に従順することを留意されたい：

とし、ここでセットＳ_ｐはＰの別個の位置に維持される。｜Ｓ｜（または

）で表されるＳの個別サンプルの数を、分散方式で以下の工程で、分散マックス・マージ・アルゴリズム（ＤＭＡ）に従って、推定することができる。
１．各々の位置ｐで、Ｓ_ｐのサンプルに基づいて、各々のｍバケットに対するｒの値を更新する。

を、位置ｐでのｊ番目のバケットに対するＲの値とする。ここで、１≦ｊ≦ｍ、および１≦ｐ≦Ｐである。

のｍ個の値の収集を、Ｓ_ｐの軽量ダイジェストと考えることができる。
２．測定期間の最後に、すべてのＰの位置の間で、１≦ｊ≦ｍ、および１≦ｐ≦Ｐに対し

の収集を交換する。
３．各々の位置で、１≦ｊ≦ｍに対し、

の設定により、

のマックス・マージを実行する。
４．任意のＰ位置において、上記に議論したＳＡＡの式４に工程３の結果であるマックス・マージしたＲ_ｊを代入することにより、｜Ｓ｜（または

）を推定する。

図１を参照して、上記の個別サンプル計数スキーム、すなわちＳＡＡおよびＤＭＡが、いかに本発明の文脈に適用されることができるか、説明する。この場合、ネットワーク内で関心のある種々のパケットのセットがサンプルセット１０になる。パケットは検査されるサンプルとなり、サンプル（またはパケット）識別子はパケット・ヘッダのいくつかの選択されるフィールドの連結から、および工程２０に示されるように、できるならばペイロードのある特定の部分から、構成される。パケット識別子の主要な要求は、ネットワークでのパケットの移動があっても不変に留まるべきである、ということである。その結果、ＩＰ・ヘッダ内のＴＴＬ−フィールドのようなあるフィールドは、望ましくはパケット識別子の一部として含まれるべきでない。ネットワークを通して移動するパケットのパケット識別子をうかつに変形する、例えばパケット経路沿いのＩＰ分解、またはネットワーク内での追加のカプセル化／トンネル化の使用のような、実際の課題に、我々は気がついている。パケットを特別な場合として普及したインパクトで扱い、かつ残りについては追加のトラヒック測定誤差として計量することにより、これらの課題に対処する。

関心のある与えられたパケットについて、ｍのＲ_ｊの収集（ＳＡＡで定義されたような）が、パケット・セットのトラヒック・ダイジェスト（ＴＤ）になる。図１は、そのパケットからパケット・セットのＴＤがいかに抽出されるかを、要約している。例えば、工程３０で各々のパケットのパケット識別子（ＰＩＤ）がＲ_ｍａｘ−ビットのハッシュ出力ｈ（ＰＩＤ）を得るために、ハッシュ関数に入力される。工程３０の出力は、工程４０のｍ−方向スプリッタに入力される。ここで、ｍ−方向スプリットはｈ（ＰＩＤ）の最後のｌｏｇ_２ｍビットに基づいて発生する。各々の１からｍのバケットに対し、工程５０でＲ_ｉが探知されるが、ここでＲiは、関数ｒ（）を用いることによって得られる、i番目のバケットに割り当てられたすべてのハッシュ出力ｈ（ＰＩＤ）の最初の（Ｒ_max―log ₂ m）ビットにおける連続する先行ゼロの最大数である。測定期間の終わりに、Ｒ１からＲｍまでの収集は、関心のあるＳ_ｐのパケット・セットの軽量ＴＤとなるが、ここでＴＤのサイズはｍｌｏｇ_２Ｒ_ｍａｘビットである。

ＤＡＴＡＬＩＴＥの動作モデル
さてＴＭＡタスクをサポートするために、本発明のＤＡＴＡＬＩＴＥが可能なネットワーク内の動作工程を説明する。図示の例として先に記述した、サンプルＴＭＡタスク＃１を用いる。この場合各々のノードｉ∈Ｖは、軽量トラヒック・ダイジェストを（ＳＡＡのｍＲ_ｊの収集の形式で）各々の関心のあるローカル・パケット・セット、すなわちそれを発したパケットのセット、（Ｏ_ｉ）、それに到着したパケットのセット（Ｄ_ｉ）およびその各々のリンク（ｉ，ｊ）∈Ｅを通過するパケットのセット（Ｌ_ｉ，ｊ）について維持する。これらのパケットの対応するＴＤを、それぞれ

、

、

と記述する。リンク毎のパケット・カウント（Ｃ_ｉ，ｊ）を追跡するための単純カウンタの使用（パケットの複製を考慮しない）およびパケットの発生のカウント（｜Ｏ_ｉ｜）に加え、各々のルータはローカルの関心のある個別パケットのカウント、すなわち｜Ｌ_ｉ，ｊ｜、｜Ｄ_ｉ｜を

および

に含まれる情報と共にＳＡＡを用いて、追跡する。さらに、ノードｉは式２の

の値を、リンク（ｉ，ｊ）∈Ｅのすべて、およびすべてのｋ＝（ｓ，ｄ）∈Ｖ×Ｖに対し、すべてのノードｊ∈Ｖから

、

を受信した後に、推定することができる。特に、式２のＲ．Ｈ．Ｓ．上のセット連合の濃度は、Ｏ_ｓ、Ｄ_ｄおよびＬ_ｉ，ｊをＤＭＡのＳ_ｐとして代入することにより、推定することができる。ここで、

はノードｓおよびｄからノードｉにそれぞれ

および

の分散により、置換される。ノードｉにより

の推定が一度計算されると、周期的な放送または質問−回答に基づくオンデマンドを経由して、他のネットワーク・ノードに分散されることができる。各々のノードは、

の知識に基づいて、関心のあるトラヒックの集合体のネットワーク・レベルの概観を構成することができる。

の測定／推定誤差をさらに削減するために、例えば［Ｄｕｒａ ０３］のスキームの確率的性質から、

に関連して表現される、ノード・レベルおよびネットワーク・レベルのフロー節約制約に基づいて、最少二乗誤差（ＭＳＥ）最適化を、各々のノードは付随的に実行することができる。そのようなＭＳＥ最適化の詳細は、次章で議論される。図２は、ＤＡＴＡＬＩＴＥが可能なノードにより、上記の動作工程を要約する。

図２を参照すると、本発明の方法論を具体化する単数または複数のプロセッサを有する、ノード１００についてのフロー図が示されている。図示のように、工程１では到来するパケットがノード１００に入り、関心のあるパケット・セットを決定するために、プリフィルタされる。工程２では、トラヒック・ダイジェスト（ＴＤ）が抽出され、例えばＯ（ｌｏｇｌｏｇＮ）サイズのＴＤが、先に述べた方法で抽出される。パケットはさらに、それらのデータ経路を進行する。図２の工程３において、ＴＤがネットワーク内、例えば関心のあるパケット・セット内の他の関連するノードに分散される。ＴＤは既知の方法で付随的に圧縮され、および／または現存するルーティングプロトコル制御メッセージまたは新しく、専用のクエリープロトコルのオペイク・データ・オブジェクトとして、フォーマットされる。工程４では、ネットワーク内の関連する他のノードからリモートＴＤが、ノード１００で受信される。工程５では、

の与えられた集合体フローのローカルな推定が、ローカルＴＤおよび分散されたリモートＴＤに基づいて決定される。次に、与えられた集合体フローのローカルな推定は、他の関連するノードに分散される。工程７では、ネットワーク内の他の関連するノードからの推定された集合体フロー

は、ノード１００で受信される。工程８で、ネットワーク内の他のノードから受信された集合体フローの推定で、トラヒック・フロー・パターンおよび量のネットワーク・レベルの外観の構成は、ローカルおよびリモート集合体フロー推定に基づいて決定される。工程９では、例えばネットワーク・レベルのフロー節約制約の適用による、推定誤差のさらなる削減のような、後処理が行われる。工程１０では、例えばネットワーク・レベルのトラヒック経路パターン、フロー量および／または可能な経路遅延統計のような、最終出力が行われる。出力はまた上記のパラメータの１つまたは複数の変化を検出する。
Ｌ_ｉ，ｊのＴＤではなく、発せられたおよび到着したパケット（すなわちすべてのｉ∈ＶのＯ_ｉ、およびＤ_ｉ）のＴＤの分散のみにより、ＤＡＴＡＬＩＴＥの通信帯域幅の要求を相当に削減することに留意されたい。これは、

の軽量特性によってさえ、それらは

程には小さくないことを理由にする。また実際的なネットワークにはリンクよりノードが一般的にかなり少ないので、

および

の数は、

よりかなり少ない。

ＤＡＴＡＬＩＴＥに必要なメモリおよび帯域幅の考察と最適化
主要な設計／工学上の挑戦は、（１）ＴＤのローカル・メモリ要求と、（２）内部ノードの通信帯域幅の要求を受け入れ可能なレベルに、関心のあるＴＭＡアプリケーションの推定誤差要求を充足しつつ、維持することである。この目的で、以下の多重尖端戦略を提案する。

１．ＴＤ当たりのメモリサイズの慎重な制御
１０Ｇｂｐｓ＋のネットワークでのＴＭＡタスクをサポートするＴＤのメモリ要求を考察する。４０Ｇｂｐｓリンクは毎秒４０バイトの最大１億２５００万パケット転送できるので、８０００秒の長さまでの測定期間を（式６の）Ｎ_ｍａｘをサポートするためには、１０^１２または２^４０の値が適切であるべきである。式５によれば、個別のサンプルカウント推定に対し標準誤差σ≦２％を実行するために、ｍは≧２０４８であるべきである。式６にＮ_ｍａｘ＝２^４０およびｍ＝２０４８を代入すると、Ｒ_ｍａｘ＝３２＝２^５となる。言い換えると、ＴＤのＲ_ｊの各々を符号化するために、５ビットを割り当てれば十分である。したがって、各々のＴＤのメモリの必要Ｍ＝ｍｌｏｇ_２Ｒ_ｍａｘ（ビット）は、ｍの値により決定される。対応する個別サンプルカウント推定の標準誤差２％に対応する、ｍ＝２０４８に対しＴＤのサイズは約１．７Ｋバイトである。これを、例えば先に議論したサンプルＴＭＡタスクの

といった、関心のある究極の測定基準の評価を通じて、可能な推定誤差の蓄積および／または「増幅」を把握するための、各々のＴＤのメモリの必要量の下限であると考える。これは、式３によれば、式３のＬ．Ｈ．Ｓ．の項の推定誤差が、Ｒ．Ｈ．Ｓ．の各々の項の推定誤差の和であるからである。従って、Ｌ．Ｈ．Ｓ．項の設定交差の工程が多ければ、式3のＲ．Ｈ．Ｓ．の連合セット濃度についての推定誤差が蓄積されるため、推定誤差は大きくなる。さらに、

は式３のＲ．Ｈ．Ｓ．の各々の連合セット濃度に関する「相対」推定誤差なので、式３のＬ．Ｈ．Ｓ．の交差項に対する、パーセント型の対応相対推定誤差は、絶対項で式３のＬ．Ｈ．Ｓ．の交差セットの濃度が、Ｒ．Ｈ．Ｓ．の連合セット項のそれよりかなり小さい場合に、増幅される。

実際には、ｍの実際の値、したがってＴＤ当たりのメモリサイズは、ＴＭＡアプリケーションの推定誤差要求に基づいて決定される。ラフな推定／測定で十分なこれらのＴＭＡアプリケーションに対しては、１．７Ｋバイトのような精度の粗い、小さいサイズのＴＤで十分である。このタイプのＴＭＡアプリケーションの例は、関心のあるイベントがトラヒック・フロー・パターンの一般的に劇的な変化を起こす、ＤＤｏＳ攻撃のトレース・バックと同じく、経路錯誤／構成ミス／検出変化を含む。結果的に、

の値がそれらの名目上の値から相当に乖離しても、突然の乖離に関して推定誤差は軽微となる。数量的で高度に正確な測定が必要とされるＴＭＡアプリケーションに対しては、式３のＬ．Ｈ．Ｓ．の各々の「連合型」項の推定の際に、ｍを増加（したがってσを減少）させることができる。しかしながら、σの線形的減少はＴＤのサイズの二次の増加を必要とするので、そのようなメモリ対精度のトレードオフは思慮深い方法で行われるべきである。幸運にもＴＤの本来的な軽量性のおかげで、そのメモリサイズを増加させる十分な空きがある。例えば、ＴＤサイズの１．７Ｋバイトから、０．８７Ｍバイトへの５１２倍の増加は、σを０．０８％以下に削減することができる。さらに、０．８７ＭバイトのＴＤは、現在の高速メモリ技術においては、まだ十分道理にかなっている。すなわち今日では、１０Ｇｂｐｓラインカードに対するメモリ量は、約２Ｇビットである。これは、２００ｍ秒の価値があるバッファリングを提供する。この量のメモリの１０％、すなわち２５Ｍバイトの使用は、トラヒック測定／解析目的としては、各々のラインカードが２８以上の０．８７ＭバイトＴＤを備えることを意味する。この調査では、並行してＴＤのマルチプル・サイジングをサポートする手段を研究する。

２．リンク毎の多重トラヒック集合体（またパケット・セット）の効率的サポート
実際には、リンク毎の単一のパケット・セット、すなわちＬ_ｉ，ｊの維持の代わりに、いくつかのＴＭＡアプリケーションは、例えばパケットのプロトコル型式および／またはポート番号に基づいて、パケット・セットのより高精度の定義を要求する。リンク毎のより高精度の多重パケット・セットの他の興味ある使用は、元の測定期間が多数のより小さい期間に分割された、「時間指標付」パケット・セットの使用であり、それによるとネットワーク内の異なるリンクに属する時間指標付パケットの交差濃度の計算により、明らかに限られた分解能でネットワーク内の経路遅延を推定することができる。

リンク毎の多重パケット・セットをサポートするために、素朴なアプローチは各々の関心のある高精度パケット・セットに対して個別のＴＤを割り当てる。しかしながら一般化したパケット・セット交差技術の導入により、ラインカード毎のＱＴＤのみの使用で、Ｏ（Ｑ^２）型式の高精度トラヒック集合体のネットワーク・レベルのＴＭＡを、サポートすることができる。この基本理念は、以下の通りである。

リンク毎にＫ＝２^ｋのパケット・セットをサポートする必要がある、と仮定する。Ｐ_１，Ｐ_２，．．．，Ｐ_ｋで表示される各々のＫのパケット・セットにＴＤを割り当てる代わりに、

である人為的なＱ個のパケット・セットＳ_１，Ｓ_２，．．．，Ｓ_Ｑのリストを構成する。Ｓ_１，Ｓ_２，．．．，Ｓ_Ｑは領域１≦ｑ１，ｑ２≦Ｑで１≦ｉ≦Ｋであるすべてのｉについて定義され、ここで、Ｐ_ｉ＝Ｓ_ｑ１∩Ｓ_ｑ２である。言い換えると、各々のＰ_ｉは人為的なセットのペアの交差から「回復」される。したがってそれぞれ

と記載されるＱ個の人為的なセットＳ_１，Ｓ_２，．．．，Ｓ_Ｑの各々に対し、ＴＤのみを維持することにより、その１つの成分としてＰ_ｉを有する任意の交差またはセット連合の濃度を計算することができる。これは、第１にＰ_ｉをＳ_ｑ１∩Ｓ_ｑ２として表現し、次に式３を適用して、先に議論した個別サンプル計数技術を使用することである。例えば、２７６のネットワーク・レベルの微細トラヒック集合体のＴＭＡを同時にサポートするために、リンク毎に２４のＴＤを維持する必要があるのみである。高分解能の０．８７ＭバイトＴＤについても、そのような構成のラインカード毎に必要な全ＴＤメモリは、今日の一般的な１０Ｇｂｐｓラインカードに見られる、２１Ｍバイトまたはメモリの８．４％（２Ｇビットまたは２００ｍ秒レベルのバッファリング）以下である。

理論的には、各々のＰｉを回復するために、２ｌｏｇ_２Ｋの人為的セット（各々がＫの二進表現ｌｏｇ_２Ｋビットのビット値に対応する）の間の交差のｌｏｇ_２Ｋ工程を適用することにより、要求されるＴＤの数をラインカード毎に２ｌｏｇ_２Ｋまでさらに削減することができる。しかしながら、累積推定誤差は、式３のＲ．Ｈ．Ｓ．の多数の項のために過大になるかもしれない。これは代わりに、工程毎の推定誤差を削減するために、各々のＴＤのメモリ要求を増加する。交差の工程数とＴＤ毎のメモリ要求の増加の間の詳細なトレードオフは、我々の調査の主題である。

３．ネットワーク・レベルのフロー節約制約の考察によるさらなる推定誤差の削減
ＴＤメモリを節約する他の方法は、初期の推定の後処理を経由した

の実効推定誤差の削減による。このスキームでは、ネットワーク内のすべてのノードから

の初期の推定を受信した後は、

に関して表現されたノード・フローの節約制約に基づく最少二乗推定（ＭＳＥ）最適化を実行する。

を、受信した

の初期推定値とする。この最適化の動機は、ノード・フロー節約制約の観点でのそれらの不整合の調整による、初期推定

の集合誤差を削減しようとすることである。

を、ノード・フロー節約制約を充足する、

の新しい推定値とする。

から

への変化に必要な摂動である、

により表現する。次のＭＳＥ最適化問題を考察する。

の最小化
ここで、

である。
上記の最適化の解は、

の「集合的」最少摂動、すなわち

を生じ、それにより新しい推定

は、

の真の値の場合のように、少なくともノード・フロー節約制約を充足する。フロー節約制約（それは

の真の値により充足されなければならない）を考察することにより、それらの真の値により近い推定をもたらすと推測する。

４．ノード間通信帯域幅の最適化
本発明のＤＡＴＡＬＩＴＥの通信帯域幅の要求の支配的な制御因子は、以下を含む。
（１）交換されるべきＴＤの数とサイズ
（２）ＴＤ交換の頻度とその結果のトラヒック・フローの推定器および
（３）それを通してＴＤとトラヒック・フロー推定器が、ネットワーク・レベルに分散される方法
（１）がいかに制御され削減されるかは、既に記述した。ここで、（１）に関しいくつかの追加の最適化の好機を述べる。第１にＴＭＡアプリケーション、すなわち関心のあるトラヒック測定、の必要性に依存して、ネットワーク内の他のノードに選択されたＴＤのセットの分散のみを必要とする。例えば、サンプルＴＭＡタスク＃１はネットワーク内のすべてのノードの間で、

と

のフル・メッシュ交換を必要とする一方で、サンプルタスク＃２はダウン・ストリームＤＤｏＳ攻撃犠牲ノードの

の分散のみを要求する。測定期間の終わりにそれらを他の関連するノードに分散する前に、ＴＤを圧縮することができる。

ＤＡＴＡＬＩＴＥによりサポートされた動作の周期的放送およびオン・デマンド・クエリー・アンサーの２つのモードはまた、（２）の制御を助ける。実際、ＴＤ交換の頻度およびその結果のトラヒック・フロー推定は、アプリケーションの必要性により主に決定される。例えば、交換検出型のアプリケーション、例えば経路ミス構成／ネットワーク故障の検出については、検出時間を削減するために交換の頻度はかなり高い。幸いにもこれらは又、例えば少ないＴＤといった精緻性の低い測定／推定で十分なアプリケーションである。これらのアプリケーションにおいては、問題となる事象により、結果として引き起こされるフローパターン及びリンク毎のフローの値の変化が重大なものとなる傾向にあるからである。他方、より高い精度の測定／推定（およびより大きいＴＤ）を必要とするＴＭＡアプリケーションは、代わりに帯域幅を削減することを助ける、より長い測定期間に対してのみ有意である傾向にある。ＤＡＴＡＬＩＴＥスキームの他の利点は、測定期間Ｔと共に、ＴＤメモリの要求が非常にゆっくりと（Ｏ（ｌｏｇｌｏｇＴ））で増大することである。上記したように、一般的なトラヒック測定アプリケーションに対し適切である、８０００秒までの長さの測定期間に対し、ＴＤのサイズを効率よく維持することができる。

最終的に、ＴＤの分散パターンは、必要な分散頻度と共に、ＴＤの数とサイズに基づいて決定されるべきである。物事を概観するために、２つの極端なシナリオ（またはアプリケーションの必要性）を考察する。最初のシナリオでは、トラヒック・パターン変化／故障検出アプリケーションまたはＤＤｏＳトレース・バックに、１．７ＫバイトのＴＤが使用される。各々のノードの圧縮されない

および

がすべての他のノードに、超流（帯域幅方式の最も高価なオプション）を用いて１秒毎に分散されたとしても、ネットワークのすべてのリンクに生成される全ＴＤトラヒックは、２^＊１．７^＊８^＊｜Ｖ｜Ｋｂｐｓ、すなわち１００ノードのネットワークのリンク毎に２．７２Ｍｂｐｓを超えないか、または１０Ｇｂｐｓリンクの能力の０．０３％より低い。第２のシナリオでは、ネットワーク・レベルの遅延時間統計および微細精度のトラヒック型式の振る舞いを測定するために、特別な１時間毎のトラヒック調査が行われる。ここで、２７６タイプのネットワーク・レベルのトラヒック集合体の挙動を（上記した一般化セット交差技術を用いて）解析するために、同じネットワーク内のすべてのノードの間のフルＩ−ＢＧＰを用いて、２４^＊２の高精度０．８７Ｍバイト非圧縮ＴＤの各々が１時間毎に分散される。ノード毎の対応する到来ＴＤの帯域幅は、０．８７^＊８^＊２^＊２４^＊１００／３６００Ｍｂｐｓ＝９．２８Ｍｂｐｓであり、それでも１０Ｇｂｐｓのリンクの能力の０．１％以下である。

結論
要約すると、ネットワーク・トモグラフィ・アプローチを苦しめる、無効なトラヒックのモデル化または動作の仮定に起因する問題を、直接測定アプローチをとることにより、本発明のＤＡＴＡＬＩＴＥは回避している。本発明のＤＡＴＡＬＩＴＥスキームと現存するトラジェクトリ・ベースのものとの間には、高度の共通点があるにもかかわらず、それらの間には基本的な差異がある：第１に、一連のセット濃度決定問題としてトラヒック測定問題を定式化することにより、最少の通信余力で、分散方式のトラヒック解析を実行するために、個別サンプル計量での最近の進歩をてこにすることができる。第２に、個々のパケット１つずつの代わりに、トラヒック集合体の挙動の測定と解析に焦点を当てることで、本発明のＤＡＴＡＬＩＴＥに対するシステム・メモリおよび通信帯域幅の要求は、従来の方法に較べて大幅に削減される。結果的に、現存するトラジェクトリ・ベース・システムが採用する、重量、集中化アプローチとは異なり、ＤＡＴＡＬＩＴＥは分散計算モデルを採用することができる。

上記の記載は、本発明の原理を単に示すものである。当業者が多様な変更を工夫でき、それらが本文書に明白に記述または示されていなくとも、本発明の原理を具体化し、本発明の精神と範囲内であることが容易に理解される。さらに、すべての例と言及された条件言語は、そのような特に言及された例および条件への限定でなく解釈され、読者に我々によって技術を進歩させる本発明の原理と概念の理解を援助する目的で、基本的に例示の目的にのみ用いられている。さらにここで、その特定の例と同様、発明の原理、態様、および実施形態を言及した言葉は、その構造的および機能的な等価物の双方を包含するように意図されている。さらに、そのような等価物は、現在知られている等価物と同様に将来開発される等価物、すなわち構造にかかわらず同じ機能を奏する、開発された要素を含む。

以下の請求項では、特定の機能を実行する手段として表現された任意の要素は、例えばａ）該機能を実行する回路要素の組合せ、またはｂ）ファームウェア、マイクロコード等、該機能を実行するためのソフトウェアを遂行する適宜の回路との組合せを含む該機能を実行する任意の方法を、包含すると想定される。そのような請求項で定義される発明は、多様な言及された手段により提供される機能が、請求項が要求する方法で組合せられかつ共に提供される、という事実に存在する。出願人はしたがって、そのような機能を提供する任意の手段を、ここに示されたものの等価物とみなす。発明の原理の多くの他の変更とその応用は、当業者には自明であり、ここでの教示により考慮される。したがって本発明の範囲は、ここに添付された請求項のみにより限定される。

本発明に従う、パケット・セットからのトラヒック・ダイジェストの抽出の方法論の一例を示す。 本発明のトラヒック測定および解析技術を用いた、ネットワーク・ノードにより実行される工程の実施形態の例である。

Claims (10)

1. パケット通信ネットワーク内のトラヒックの解析を実行する方法であって、
   前記ネットワーク内の特定のノードで、関心のあるパケットのセットに関するトラヒックの集合体を測定する工程と、
   前記トラヒックの集合体を用いて、前記ネットワークの測定されるべきパラメータの交差セット濃度決定を定式化する工程と、
   前記測定されるべきパラメータについて、前記セット濃度決定を解く工程とを含む方法。
2. 前記交差セット濃度決定を一連の連合セット濃度決定に定式化する工程をさらに含む、請求項１に記載の方法。
3. 前記連合セット濃度決定を分散方式で解くために、１つまたは複数のＯ（ｌｏｇｌｏｇ｜Ａ｜）個別サンプル計量アルゴリズムを適用する工程をさらに含む、請求項２に記載の方法。
4. パケット・セットＬ_ｉ，ｊの必要な情報を要約するために、基本Ｏ（ｌｏｇｌｏｇＮ_ｍａｘ）のビット・ダイジェストが用いられ、Ｎ_ｍａｘは、Ｌ_ｉ，ｊ内の個別サンプルの最大数である、請求項３に記載の方法。
5. 前記トラヒックの解析は、トラヒック経路パターンの解析、トラヒック・フロー・パターンの解析、および与えられた関心のあるパケットのグループが移動する中間ノードおよびリンクと共に、起点および終点をトレースすることからなるグループから選択される、請求項１に記載の方法。
6. パケット通信ネットワーク内のトラヒックの解析を実行する方法であって、
   前記ネットワーク内の選択されたノードから、与えられたパケット・セットのメンバーシップに基づいて、トラヒック・ダイジェストベースの集合体を抽出する工程と、
   前記ネットワーク内の前記選択された以外のノードに、関連するローカル・トラヒック・ダイジェストを分散する工程と、
   前記ネットワーク内の前記選択された以外のノードから、関連するリモート・トラヒック・ダイジェストを受信する工程と、
   前記ローカル・トラヒック・ダイジェストと前記リモート・トラヒック・ダイジェストに基づいて、特定のトラヒック・フローのローカルな推定を提供する工程と、
   前記他の選択されたノードから、前記特定のトラヒック・フローのリモート推定を受信する工程と、
   前記ローカルおよびリモートの特定のトラヒック・フローに基づいて、前記ネットワークの与えられたパラメータについて、セット濃度決定問題を解く工程とを含む方法。
7. 前記トラヒック・ダイジェストを抽出する工程が、
   ある特定のパケット・セットに属する各々のパケットから、パケット識別子を抽出する工程と、
   Ｒ_ｍａｘビットのハッシュ出力を受信するために、各々のパケット識別子をハッシュ関数に入力し、前記Ｒ_ｍａｘビットのハッシュ出力のｌｏｇ_２ｍビットがバケット指標を決定するために用いられる工程と、
   前記バケット指標に基づいて前記ハッシュ出力をｍのバケットに分割する工程と：
   前記ｍのバケットの各バケットｉについて、ｒ（）を用いることによって、ｉ番目のバケットに割り当てられたすべてのハッシュ出力ｈ（ＰＩＤ）の最初の（Ｒ_ｍａｘ−ｌｏｇ_２ｍ）ビットにおける連続する先行ゼロの最大数たる、Ｒｉを追跡する工程と、
   前記特定されたパケット・セットに対するトラヒック・ダイジェストとして、Ｒ_１からＲ_ｍを用いる工程とを含む、請求項６に記載の方法。
8. トラヒック・ダイジェスト測定期間と、同じ測定期間内にあるリンクを通過するパケットの数を追跡するために、すべてのリンク（ｉ，ｊ）∈Ｅに対しパケット・カウンタＣ_ｉ，ｊが維持され、Ｃ_ｉ，ｊの値と｜Ｌ_ｉ，ｊ｜の間の大きな差異は、潜在的な経路問題を表す、請求項６に記載の方法。
9. 「時間指標付き」パケット・セットをさらに含み、Ｑの人為セットを通して、ネットワーク内の異なるリンクに属する、時間指標付きのパケット・セットの交差濃度の計算により、ネットワーク内の経路遅延を推定するために、元の測定期間が多くのより小さい期間に分割される、請求項６に記載の方法。
10. パケット通信ネットワーク内の、トラヒックの解析を実行する方法であって、
    前記ネットワーク内の選択されたノードから、与えられたパケット・セットのメンバーシップに基づいてトラヒック・ダイジェストベースの集合体を抽出する工程と、
    前記ネットワーク内の前記選択された以外のノードに関連するローカル・トラヒック・ダイジェストを分散する工程と、
    前記ネットワーク内の前記選択された以外のノードから関連するリモート・トラヒック・ダイジェストを分散する工程と、
    前記ローカル・トラヒック・ダイジェストと前記リモート・トラヒック・ダイジェストに基づいて、特定のトラヒック・フローのローカルな推定を提供する工程と、
    前記他の選択されたノードから、前記特定のトラヒック・フローのリモート推定を分散する工程と、
    前記ローカルおよびリモートの特定のトラヒック・フローに基づいて、前記ネットワークの与えられたパラメータについて、セット濃度決定問題を解く工程とを含む方法。
    

Images