(57)【特許請求の範囲】
【請求項１】
ネットワーク監視のためのコンピュータ実装方法であって、
仮想ネットワークにおける異なるタイプの複数の処理要素にわたって収集されたネットワーク監視のためのネットワークパケットトレースの要約及び特徴付けを提供することを含み、
前記要約は、個々のパケットイベントをパスベースのトレーススライスに組織化するためのトレーススライシングであり、
前記特徴付けは、前記トレーススライシングにおける前記トレーススライスを説明するトレーススライスベクトル及びパケット特性を生成するものであり、
前記提供が、前記トレーススライシングと前記特徴付けと、前記トレーススライスベクトル及びパケット特性のメトリクスに基づいて、パケットトレースをクラスタリング、ランク付け、及びクエリするためのパケットトレース分析と、を含み、
前記クラスタリングはパケットパスの類似性に基づくトレーススライスのクラスタの構築を含み、前記ランク付けは少なくとも１つのタイプのパケット特性ベクトルに基づくものであり、前記クエリは全てのクエリ条件を満たす項目のリストを生成するための全てのパケット特性ベクトルの横断を含み、
ネットワーク監視のための前記ネットワークパケットトレースの要約及び特徴付けが、前記ネットワークにおけるデータパスルーティング問題の診断を可能にし、かつ新しいネットワーク可視化及びトラフィック分析を可能にする、方法。
【請求項２】
前記トレーススライシングが、元の個々のパケットイベントを別個のトレーススライスに変換することを含み、各スライスが、ネットワークパケットが呼び出し、かつ前記ネットワークを横断したときに記録されたパケットトレース収集物からの全てのパケットイベントを含む、請求項１に記載の方法。
【請求項３】
前記トレーススライシングが、ターゲットネットワークから収集された全てのパケットイベントを前処理することと、全てのパケットイベントを集約することと、イベントタイムスタンプによって昇順で前記集約されたパケットイベントを分類することと、前記集約されたパケットイベントを順序リストデータ構造に記憶することと、を含む、請求項１に記載の方法。
【請求項４】
前記トレーススライシングが、各パケットイベントｅに対して、時間Ｔｅ、スイッチ識別ＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、及び
ペイロードＰｅを含む全てのパケットイベントの前処理を含む、請求項１に記載の方法。
【請求項５】
前記前処理が、前記ヘッダＨｅ及びペイロードＰｅに基づいてパケットシグネチャＳｅを作成することを含み、前記シグネチャＳｅが、前記ルーティングプロセスを通して変化しないイベントｅと関連付けられたパケットにおける不変コンテンツであり、前記ヘッダＨｅにおいて、ＩＰフロー情報［ソースＩＰアドレス、ソースポート、宛先ＩＰアドレス、宛先ポート］が、ＩＰトンネリングのための前記不変コンテンツの一部であり、内部ＩＰヘッダのフロー情報が不変である、請求項４に記載の方法。
【請求項６】
前記前処理が、前記ペイロードＰｅにおいて、前記コンテンツの全コンテンツ又はハッシュ値が、前記シグネチャの一部として使用され得ることを含み、前記シグネチャＳｅが、前記ヘッダＨｅ及びペイロードＰｅの両方から作成された不変コンテンツの組み合わせであり、次いで、各パケットイベントｅが、時間Ｔｅ、スイッチＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、及びシグネチャＳｅの５タプルオブジェクトに更新され、前記ペイロードが空間節約のために除去される、請求項４に記載の方法。
【請求項７】
前記トレーススライシングが、パケットイベントをスライスすることであって、１つのトレーススライス（ＴＳ）が、前記ネットワークを横断するときにネットワークパケットが呼び出した全ての記録されたパケットイベントを含む時間順序イベントシーケンスデータ構造＜Ｓ＞として定義される、スライスすることと、パケットシグネチャを使用して、収集されたパケットイベントからトレーススライスを生成することと、を含む、請求項１に記載の方法。
【請求項８】
パケットシグネチャを使用した収集されたパケットイベントからのトレーススライスの前記生成が、
空トレーススライスＴＳセットＴＳＳ＝｛｝を初期化することと、
順序リストデータ構造Ｍにおける第１のパケットイベントｅから開始して最後のものまで続けることと、以下の工程：
前記セットＴＳＳにおいてｅのシグネチャＳｅと同じシグネチャを有する任意の既存のＴＳを検索し、ＴＳが見つけられない場合、新しいＴＳを作成し、このＴＳの第１のイベントとしてｅを挿入し、そのシグネチャをＳｅとラベル付けし、継続する工程、そうでなければ、
あらゆる見つけられたＴＳについて、その最後のパケットイベントのタイムスタンプが、パケットが前記ネットワークにとどまることができる最大時間であり、かつネットワーク直径の関数であるＴＤだけｅのタイムスタンプよりも早い場合、新しいＴＳを作成し、このＴＳの前記第１のイベントとしてｅを挿入し、そのシグネチャをＳｅとラベル付けし、継続する工程、そうでなければ、
最後のパケットイベントのタイムスタンプがＴＤだけｅのタイムスタンプよりも早くない各見つけられたＴＳについて、ｅをこのＴＳの最後のイベントとして付加し、前記ＴＳセットＴＳＳを返す工程、を繰り返すことと、を含む、請求項７に記載の方法。
【請求項９】
前記特徴付けが、トレーススライスベクトル生成を含み、パケットが、多様なルートを有し得、各パケットの挙動を正確に分析し、かつそのルートを表すために、トレーススライスベクトルと呼ばれる定義されたマトリクスに応答して、前記トレーススライスベクトル生成がトレーススライスベクトルを生成する方法を提示する、請求項１に記載の方法。
【請求項１０】
前記特徴付けが、種々の様態における挙動を理解するためにトレース情報の新しい観点を生成するパケット特性の生成を含み、この情報が、パケット特性と呼ばれ、均一な方法でパケットイベントからパケット特性を生成するための伝達関数の定義が存在し、前記パケットイベントとパケット特性との間のマッピングが多様である、請求項１に記載の方法。
【請求項１１】
ネットワーク監視のためのコンピュータ実装方法を可能にするための命令を有する非一時的記憶媒体であって、前記ネットワーク監視のためのコンピュータ実装方法が、
仮想ネットワークにおける異なるタイプの複数の処理要素にわたって収集されたネットワーク監視のためのネットワークパケットトレースの要約及び特徴付けを提供することを含み、
前記要約は、個々のパケットイベントをパスベースのトレーススライスに組織化するためのトレーススライシングであり、
前記特徴付けは、前記トレーススライシングにおける前記トレーススライスを説明するトレーススライスベクトル及びパケット特性を生成するものであり、
前記提供が、前記トレーススライシングと前記特徴付けと、前記トレーススライスベクトル及びパケット特性のメトリクスに基づいて、パケットトレースをクラスタリング、ランク付け、及びクエリするためのパケットトレース分析と、を含み、
前記クラスタリングはパケットパスの類似性に基づくトレーススライスのクラスタの構築を含み、前記ランク付けは少なくとも１つのタイプのパケット特性ベクトルに基づくものであり、前記クエリは全てのクエリ条件を満たす項目のリストを生成するための全てのパケット特性ベクトルの横断を含み、
ネットワーク監視のための前記ネットワークパケットトレースの要約及び特徴付けが、前記ネットワークにおけるデータパスルーティング問題の診断を可能にし、かつ新しいネットワーク可視化及びトラフィック分析を可能にする、非一時的記憶媒体。
【請求項１２】
前記トレーススライシングが、元の個々のパケットイベントを別個のトレーススライスに変換することを含み、各スライスが、ネットワークパケットが呼び出し、かつ前記ネットワークを横断したときに記録されたパケットトレース収集物からの全てのパケットイベントを含む、請求項１１に記載の非一時的記憶媒体。
【請求項１３】
前記トレーススライシングが、ターゲットネットワークから収集された全てのパケットイベントを前処理することと、全てのパケットイベントを集約することと、イベントタイムスタンプによって昇順で前記集約されたパケットイベントを分類することと、前記集約されたパケットイベントを順序リストデータ構造に記憶することと、を含む、請求項１１に記載の非一時的記憶媒体。
【請求項１４】
前記トレーススライシングが、各パケットイベントｅに対して、時間Ｔｅ、スイッチ識別ＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、及びペイロードＰｅを含む全てのパケットイベントの前処理を含む、請求項１３に記載の非一時的記憶媒体。
【請求項１５】
前記前処理が、前記ヘッダＨｅ及びペイロードＰｅに基づいてパケットシグネチャＳｅを作成することを含み、前記シグネチャＳｅが、前記ルーティングプロセスを通じて変化しないイベントｅと関連付けられたパケットにおける不変コンテンツであり、前記ヘッダＨｅにおいて、ＩＰフロー情報［ソースＩＰアドレス、ソースポート、宛先ＩＰアドレス、宛先ポート］が、ＩＰトンネリングのための前記不変コンテンツの一部であり、内部ＩＰヘッダのフロー情報が不変である、請求項１４に記載の非一時的記憶媒体。
【請求項１６】
前記前処理が、前記ペイロードＰｅにおいて、前記コンテンツの全コンテンツ又はハッシュ値が、前記シグネチャの一部として使用され得ることを含み、前記シグネチャＳｅが、前記ヘッダＨｅ及びペイロードＰｅの両方から作成された不変コンテンツの組み合わせであり、次いで、各パケットイベントｅが、時間Ｔｅ、スイッチＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、及びシグネチャＳｅの５タプルオブジェクトに更新され、前記ペイロードが空間節約のために除去される、請求項１４に記載の非一時的記憶媒体。
【請求項１７】
前記トレーススライシングが、パケットイベントをスライスすることであって、１つのトレーススライス（ＴＳ）が、前記ネットワークを横断するときにネットワークパケットが呼び出した全ての記録されたパケットイベントを含む時間順序イベントシーケンスデータ構造＜Ｓ＞として定義される、スライスすることと、パケットシグネチャを使用して、収集されたパケットイベントからトレーススライスを生成することと、を含む、請求項１１に記載の非一時的記憶媒体。
【請求項１８】
パケットシグネチャを使用した収集されたパケットイベントからのトレーススライスの前記生成が、
空トレーススライスＴＳセットＴＳＳ＝｛｝を初期化することと、
順序リストデータ構造Ｍにおける第１のパケットイベントｅから開始して最後のものまで続けることと、以下の工程：
前記セットＴＳＳにおいてｅのシグネチャＳｅと同じシグネチャを有する任意の既存のＴＳを検索し、ＴＳが見つけられない場合、新しいＴＳを作成し、このＴＳの第１のイベントとしてｅを挿入し、そのシグネチャをＳｅとラベル付けし、継続する工程、そうでなければ、
あらゆる見つけられたＴＳについて、その最後のパケットイベントのタイムスタンプが、パケットが前記ネットワークにとどまることができる最大時間であり、かつネットワーク直径の関数であるＴＤだけｅのタイムスタンプよりも早い場合、新しいＴＳを作成し、このＴＳの前記第１のイベントとしてｅを挿入し、そのシグネチャをＳｅとラベル付けし、継続する工程、そうでなければ、
最後のパケットイベントのタイムスタンプがＴＤだけｅのタイムスタンプよりも早くない各見見つけられたＴＳについて、ｅをこのＴＳの最後のイベントとして付加し、
前記ＴＳセットＴＳＳを返す工程、を繰り返すことと、を含む、請求項１７に記載の非一時的記憶媒体。
【請求項１９】
前記特徴付けが、トレーススライスベクトル生成を含み、パケットが、多様なルートを有し得、各パケットの挙動を正確に分析し、かつそのルートを表すために、トレーススライスベクトルと呼ばれる定義されたマトリクスに応答して、前記トレーススライスベクトル生成がトレーススライスベクトルを生成する方法を提示する、請求項１１に記載の非一時的記憶媒体。
【請求項２０】
前記特徴付けが、種々の様態における挙動を理解するためにトレース情報の新しい観点を生成するパケット特性の生成を含み、この情報が、パケット特性と呼ばれ、均一な方法でパケットイベントからパケット特性を生成するための伝達関数の定義が存在し、前記パケットイベントとパケット特性との間のマッピングが多様である、請求項１１に記載の非一時的記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、２０１３年１２月２０日出願の仮特許出願第６１／９１８，９５７号、名称「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｎｅｔｗｏｒｋ  Ｐａｃｋｅｔ  Ｅｖｅｎｔ  Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ  ａｎｄ  Ａｎａｌｙｓｉｓ」への優先権を主張するものであり、その内容は、参照により本明細書に組み込まれる。
【背景技術】
【０００２】
本発明は、概して、ソフトウェアシステム性能診断に関し、より具体的には、ネットワークパケットイベント特徴付け及び分析に関する。
【０００３】
ネットワーク仮想化は、将来のインターネットワーキングパラダイムの多様化する特質として提唱されている。共有される物理的基板上に共生する複数の異種ネットワークアーキテクチャを導入することによって、ネットワーク仮想化は、革新及び多様化された適用を推進する。コアネットワーク仮想化技術のうちの１つとして、Ｏｐｅｎ  ｖＳｗｉｔｃｈ（ＯＶＳ）［１］は、生産品質、多層仮想スイッチである。それは、プログラム拡張を通じた大規模なネットワーク自動化を可能にしつつ、依然として、標準的な管理インターフェースアーキテクチャ及びプロトコル（例えば、ＮｅｔＦｌｏｗ、ｓＦｌｏｗ、ＳＰＡＮ、ＲＳＰＡＮ、ＣＬＩ、ＬＡＣＰ、８０２．１ａｇ）を支持するように設計される。ハイパーバイザ内で実行するソフトスイッチとして、かつスイッチングシリコンのための制御スタックとして、動作することができる。それは、複数の仮想化プラットフォーム及びスイッチングチップセットにポートされている。
【０００４】
しかしながら、この新しい分散環境に移動するとき、明瞭な可視性及びどのようにネットワークが性能しているかの理解を有する方法が存在した方が良い。問題が生じたとき、いずれのテナントに対するいずれのビジネスインパクトにも先立って、それらを解決するための診断及びトラブルシューティング能力を有することが不可欠である。
【０００５】
ネットワークを監視するための従来の抽象的概念及び機構は、しばしば、いくらか断片化される。ｎｅｔｆｌｏｗ及びシンプルネットワークマネージメントプロトコルＳＮＭＰ等のインターフェースアーキテクチャを使用して、ネットワーク要素を監視する、集中化されたソフトウェアアプリケーションが存在する。しかしながら、これらの機構は、機器にわたって一貫性のない実装に悩まされる可能性があり、しばしば、適切な粒度及び抽象的概念において、情報を公開しない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
したがって、以前には教示されていない、ネットワークパケットイベント特徴付け及び分析のための解決策に対する必要性が存在する。
【課題を解決するための手段】
【０００７】
本発明は、ネットワーク監視のためのコンピュータ実装方法を対象とし、仮想ネットワークにおける異なるタイプの複数の処理要素にわたって収集されたネットワークパケットトレースの要約及び特徴付けを支持することと、仮想ネットワークで何が起こっているかの集約図を提供することと、を含む、ネットワーク監視のためのネットワークパケットイベント特徴付け及び分析を提供することを含み、該提供は、個々のパケットイベントをパスベースのトレーススライスに組織化するためのトレーススライシング、それらのトレーススライスを説明する少なくとも２つのタイプの特性マトリクスを抽出するためのトレース特徴付け、並びに特性マトリクスのメトリクスに基づいて、パケットトレースをクラスタリング、ランク付け、及びクエリするためのトレース分析を含み、ネットワーク監視のためのネットワークパケットトレース要約及び特徴付けは、ネットワークにおけるデータパスルーティング問題を診断することを可能にし、かつ新しいネットワーク可視化及びトラフィック分析を可能にする。
【０００８】
本発明の類似の様態において、ネットワーク監視のためのコンピュータ実装方法を可能にするための命令を有する非一時的記憶媒体が提供され、該ネットワーク監視のためのコンピュータ実装方法は、仮想ネットワークにおける異なるタイプの複数の処理要素にわたって収集されたネットワークパケットトレースの要約及び特徴付けを支持することと、仮想ネットワークで何が起こっているかの集約図を提供することと、を含む、ネットワーク監視のためのネットワークパケットイベント特徴付け及び分析を提供することを含み、該提供は、個々のパケットイベントをパスベースのトレーススライスに組織化するためのトレーススライシング、それらのトレーススライスを説明する少なくとも２つのタイプの特性マトリクスを抽出するためのトレース特徴付け、並びに特性マトリクスのメトリクスに基づいて、パケットトレースをクラスタリング、ランク付け、及びクエリするためのトレース分析を含み、ネットワーク監視のためのネットワークパケットトレース要約及び特徴付けは、ネットワークにおけるデータパスルーティング問題を診断することを可能にし、かつ新しいネットワーク可視化及びトラフィック分析を可能にする。
【０００９】
本発明のこれらの及び他の利点は、以下の発明を実施するための形態及び添付の図面を参照することによって、当業者には明らかとなるであろう。
【図面の簡単な説明】
【００１０】
【図１】本発明に従う、ＦｌｏｗＶｉｅｗパケットトレース分析の図である。
【図２】ＦｌｏｗＶｉｅｗパケットイベントの例を示す。
【図３Ａ】本発明に従う、ＦｌｏｗＶｉｅｗトレーススライシング手順を示す。
【図３Ｂ】ＦｌｏｗＶｉｅｗトレーススライスの例を示す。
【図４】本発明に従う、ＦｌｏｗＶｉｅｗトレース特徴付けの図である。
【図５】本発明に従う、ＦｌｏｗＶｉｅｗトレース分析の図である。
【図６】エンド・ツー・エンドパケット待ち時間を伴うランク付けの例を示す。
【図７】トレーススライスにおけるリンクの数を伴うランク付けを示す。
【図８】パケットサイズを伴うランク付けを示す。
【図９】クエリ条件の例を示す。
【図１０】クエリ関数によって報告される一組のパケットトレースを示す。
【図１１】本発明を実施するための例示的なコンピュータの図である。
【発明を実施するための形態】
【００１１】
本発明は、異なるタイプの複数の処理要素にわたって収集されたＯｐｅｎ  ｖＳｗｉｔｃｈ  ＯＶＳトレース等のネットワークパケットトレースの要約及び特徴付けを支持し、かつ仮想ネットワークで何が起こっているかの集約図を提供するための方法を対象とする。それは、個々のパケットイベントをパスベースのトレーススライスに組織化するためのトレーススライシングスキームを含む。それはまた、それらのトレーススライスを説明する２つのタイプの特性マトリクスを抽出するためのスライス特徴付けスキーム、並びにそれらの特性メトリクスに基づいてパケットトレースをクラスタリング、ランク付け、及びクエリするための一組のトレース分析アルゴリズムを含む。
【００１２】
図１は、本発明−ＦｌｏｗＶｉｅｗパケットトレース要約及び分析のプロセスを示す。フローチャートは、以下の通りに詳細に説明される：
【００１３】
ブロック１０１は、パケットトレース収集を表す。この工程は、ターゲットネットワークからネットワークパケットトレースを収集する。かかるパケットイベントトレースは、オープンソースｌｉｂｐｃａｐベースのパケットキャプチャツール又は任意の専用パケットダンプツールで、ＯＶＳ又はスイッチ若しくはルータ等の物理的ネットワーク要素から得ることができる。パケットイベントｅは、５タプルオブジェクト［時間Ｔｅ、スイッチＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、ペイロードＰｅ］として定義され、ここで、時間Ｔｅは、イベントが記録された時間であり、スイッチＩＤ  ＳＷｅ、ポートＰｏｒｔｅ、及びＩＮ／ＯＵＴは、どのスイッチ及びポートで、パケットｅがＩＮ又はＯＵＴであったかを説明し、パケットヘッダＨｅ及びペイロードＬｅは、ネットワークヘッダ（イーサネット（登録商標）フレーム及びＩＰヘッダ）、並びにパケットｅのペイロードを記録する。
【００１４】
ブロック１０２は、トレーススライシングを表す。この工程は、元の個々のパケットイベントを別個のトレーススライスに変換し、各スライスは、ネットワークパケットが呼び出し、かつネットワークを横断したときに記録された１０１からの全てのパケットイベントを含む。
【００１５】
ブロック１０３は、トレース特徴付けを表す。この工程は、１０２によるトレーススライス出力から２つのタイプの特性マトリクスを抽出する。
【００１６】
ブロック１０４は、トレース分析を表す。この工程は、一組のデータ分析技術を、１０３による特性メトリクス出力に基づいて、１０２からのトレーススライスに適用する。
【００１７】
本発明の特徴は、１０２（トレーススライシング）及び１０３（トレース特徴付け）にある。これらの特徴の詳細は、以下で説明される。
【００１８】
図３は、以下の通り、ＦｌｏｗＶｉｅｗトレーススライシング手順の詳細を示す。
【００１９】
ブロック２０１は、収集されたパケットイベントを前処理するための工程を表す。以降は、ターゲットネットワークから収集された全てのパケットイベントにおける前処理手順である：ブロック２０１は、ａ）各パケットイベントｅに対して、［時間Ｔｅ、スイッチＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、ペイロードＰｅ］を含み、パケットシグネチャＳｅは、ヘッダＨｅ及びペイロードＰｅに基づいて作成される。シグネチャＳｅは、ルーティングプロセスを通じて変化しないイベントｅと関連付けられたパケットにおける不変コンテンツである。ヘッダＨｅにおいて、ＩＰフロー情報［ソースＩＰアドレス、ソースポート、宛先ＩＰアドレス、宛先ポート］は、不変コンテンツの一部である（ＩＰトンネリングに関して、内部ＩＰヘッダのフロー情報は、不変である）。ペイロードＰｅにおいて、全コンテンツ又はコンテンツのハッシュ値は、シグネチャの一部として使用することができる。シグネチャＳｅは、ヘッダＨｅ及びペイロードＰｅの両方から作成された不変コンテンツの組み合わせである。この工程後、各パケットイベントｅは、５タプルオブジェクト［時間Ｔｅ、スイッチＩＤ  ＳＷｅ、スイッチポートＰｏｒｔｅ、ＩＮ／ＯＵＴ、パケットヘッダＨｅ、シグネチャＳｅ］に更新され、ペイロードが空間節約のために除去される。
【００２０】
前処理後のＦｌｏｗＶｉｅｗパケットイベントの例が、図２に示される。
【００２１】
ブロック２０１は、ｂ）全てのパケットイベントを集約し、イベントタイムスタンプＴｅによって昇順でそれらを分類し、それらを順序リストデータ構造Ｍに記憶することを含む。
【００２２】
ブロック２０２は、スライスパケットイベントを表す。１つのトレーススライス（ＴＳ）は、ネットワークを横断するときにネットワークパケットが呼び出した全ての記録されたパケットイベントを含む時間順序イベントシーケンスデータ構造＜Ｓ＞として定義される。
【００２３】
以降は、工程２０１において生成されたパケットシグネチャを使用して、１０１における収集されたパケットイベントからトレーススライスを生成するためのスライシングアルゴリズムである。
【００２４】
ブロック２０２は、以下を含む：ａ）空のＴＳセットＴＳＳ＝｛｝を初期化すること、
２０２．ｂ−Ｍにおける第１のパケットイベントｅから開始して最後のものまで続けることと、以下の工程を繰り返すこと：
【００２５】
２０２．ｂ．１−セットＴＳＳにおいてｅのシグネチャＳｅと同じシグネチャを有するいずれかの既存のＴＳを検索し、ＴＳが見つけられない場合、新しいＴＳを作成し、ｅをこのＴＳの第１のイベントとして挿入し、そのシグネチャをＳｅとラベル付けし、継続し、そうでなければ、２０２．ｂ．２に進む、工程。
【００２６】
２０２．ｂ．２−あらゆる見つけられたＴＳについて、その最後のパケットイベントのタイムスタンプが、パケットがネットワークにとどまることができる最大時間であり、かつネットワーク直径の関数であるＴＤだけｅのタイムスタンプよりも早い場合、新しいＴＳを作成し、このＴＳの第１のイベントとしてｅを挿入し、そのシグネチャをＳｅとラベル付けし、継続し、そうでなければ、２０２．ｂ．３に進む工程。
【００２７】
２０３．ｂ．３−最後のパケットイベントのタイムスタンプがＴＤを超えて、ｅのタイムスタンプよりも早くない各見つけられたＴＳについて、ｅをこのＴＳの最後のイベントとして付加する工程。
【００２８】
２０２．ｃ−ＴＳセットＴＳＳを返すこと。
【００２９】
ＦｌｏｗＶｉｅｗトレーススライスの例が、以下で図３に示されている。スライスは、（スイッチＩＤ  ０００００ｅａ０ａｅｄ９０５４２、ポート１）、（スイッチＩＤ  ００００００３０４８９０ｆ９５ｄ、ポート２）、及び（スイッチＩＤ  ００００００３０４８９０ｆ９５ｄ、ポート１）を通って横断した１つのパケットに対する３つのネットワークイベントを含む。
【００３０】
図４は、以下の通り、ＦｌｏｗＶｉｅｗトレース特徴付け手順の詳細を示す。
【００３１】
ブロック３０１は、トレーススライスベクトル生成を表す。各パケットは、多様なルートを有し得る。各パケットの挙動を正確に分析し、そのルートを表すために、我々は、トレーススライスベクトルと呼ばれるマトリクスを定義した。この手順は、どのようにトレーススライスベクトルを生成するかを提示する。
【００３２】
入力：
一組のトレーススライス：Ｔ＝｛Ｔｋ｝であり、ｋは、スライスに対する指数であり、｜Ｔ｜＝Ｎ，１≦ｋ≦Ｎである。
【００３３】
トレーススライスは、パスリンクノードの時間順序リストである。Ｔｋ＝｛ｐ１，．．．，ｐｍ｝である。
【００３４】
パスノードは、パケットが通過するルータ又はスイッチの情報に関する。それは、ｐｍ＝｛タイムスタンプ，スイッチＩＤ，ポート，ＩＮ／ＯＵＴ，パケットヘッダシグネチャ｝からなる。
【００３５】
出力：
トレーススライスは、行がスイッチＩＤを表し、列がポート（＝ｖｋ［スイッチＩＤ］［ポート］）を表す、２次元マトリクスである、トレーススライスベクトルｖｋを有する。
【００３６】
アルゴリズム：ＧｅｎｅｒａｔｅＰａｃｋｅｔＰａｔｈＶｅｃｔｏｒ（Ｔ）
／／各トレースに対して
Ｔにおける各Ｔｋに対して：
ｖｋ＝Ｖ［ｋ］
ｖｋを初期化
Ｔｋにおける各パスリンクノードに対して：
ｖｋ［ｐ．ｓｗｉｔｃｈ  ｉｄ］［ｐ．ｐｏｒｔ］＋＝１
ｅｎｄ  ｆｏｒ
ｅｎｄ  ｆｏｒ
Ｖを返す。
【００３７】
ブロック３０２は、パケット特性の生成を表す。このコンポーネントは、種々の様態における挙動を理解するためにトレース情報の新しい観点を生成する。この情報は、パケット特性と呼ばれる（３０２）。我々は、均一な方法でパケットトレースイベントからパケット特性を生成するための伝達関数を定義する。トレースイベントとパケット特性との間のマッピングは、多様である。例えば、待ち時間は、パケットの伝送において費やしたエンド・ツー・エンド時間を測定する。パケットのリンクの数は、いくつのスイッチ／ルータを伝送において横断するかを表す。
【００３８】
入力：
一組のトレーススライス：Ｔ＝｛Ｔｋ｝であり、ｋは、トレーススライスに対する指数であり、｜Ｔ｜＝Ｎ，１≦ｋ≦Ｎである。
一組の伝達関数：Ｆ＝｛ｆｌ｝であり、ｌは、リソース伝達関数の指数である。
｜Ｆ｜＝Ｌ，１≦ｌ≦Ｌ
【００３９】
出力：
一組のパケット特性ベクトル：Ｒ
【００４０】
アルゴリズム：ＧｅｎｅｒａｔｅＰａｃｋｅｔＦｅａｔｕｒｅｓ（Ｔ，Ｆ）
【００４１】
【数１】
0006371852.tif 000002
【００４２】
／／各トレースに対して
Ｔにおける各Ｔｋに対して：
Ｆにおける各ｆｌに対して：
Ｒｋ，ｌ＝ｆｌ（Ｔｋ）
ｅｎｄ  ｆｏｒ
ｅｎｄ  ｆｏｒ
Ｒを返す。
【００４３】
伝達関数のいくつかの例は以下の通りである。
【００４４】
待ち時間特性は、第１及び最後のパスリンクノード間の時間である。
ｆｌａｔｅｎｃｙ（Ｔｋ）＝｜ｔＮ−ｔ１｜，ｅｊ∈Ｔｋ，Ｔｊは、ｅｊに対するタイムスタンプであり、１≦ｊ≦Ｎ。
【００４５】
リンクの数は、単に、スライスの内側のパスリンクノードの数である。
ｆｎｕｍｌｉｎｋ（Ｔｋ）＝｜Ｔｋ｜である。
【００４６】
パケットサイズ特性は、パスリンクにわたって一定であるはずであるパケットのサイズである。ｆｓｉｚｅ（Ｔｋ）＝パケットのサイズＴｋ
【００４７】
ブロック１０４は、パケットトレース分析手順を表す。Ｆｌｏｗｖｉｅｗトレース分析手順が、図５に示されている。ＦｌｏｗＶｉｅｗは、３つのタイプのパケットトレース分析：クラスタリング（４０１）、ランク付け（４０２）、及びクエリ（４０３）を提供する。これらの３つの関数は、多用途のパケットトレース分析関数を提供する。
【００４８】
トレーススライスクラスタリング４０１は、パケットのパスの類似性に基づいて、トレーススライスのクラスタを構築する。このパス類似性は、トレーススライスベクトルとして表されるスイッチＩＤ及びポート対の類似性として判定される。
【００４９】
トレーススライスは、トレーススライスベクトルを使用してクラスタリングされる。クラスタリング方法に関して、我々は、距離関数における閾値（ＴｈｒｅｓＣ）とともに、接続性に基づくクラスタリング（階層的クラスタリングとも呼ばれる）を使用した。このスキームは、凝集型方法（ボトムアップアプローチ）を使用し、単一結合（最近隣アプローチ）は、クラスタを接続するために使用される。ここで、ａ及びｂは、トレーススライスを表す。それらのトレーススライスベクトルは、ｖａ及びｖｂとして表される。Ａ及びＢは、トレースのクラスタである。
【００５０】
結合基準：ｍｉｎ｛ｄ（ａ，ｂ）：ａ∈Ａ，ｂ∈Ｂ，ｄ（ａ，ｂ）≦Ｔｈｒｅｓｃ｝
【００５１】
トレーススライスベクトルの比較のための距離関数は、Ｅｕｃｌｉｄｅａｎ距離に基づく：
【００５２】
【数２】
0006371852.tif 000003
【００５３】
トレースセットにおける各トレース対は、この距離関数をそれらのトレーススライスベクトルに適用することによって比較され、それらは、それらの距離が閾値未満である場合、接続される。
【００５４】
パケットランク付け４０２は、ユーザが、関心対象の所与のランク付けスキームにおけるパケットトレースの有意性を理解することができるように、パケットトレースのランク付けを提供する。
【００５５】
ユーザの関心に依存して、種々の特性ベクトルは、パケットをランク付けするために使用することができる。例えば、我々は、待ち時間、ホップの数、及びパケットサイズを使用して、３つの例のランク付けトレースを示す。トレースは、異なる特性によってランク付けされるが、ランク付け機構は、共通である。
【００５６】
入力：
ランク付け特性数：１
パケット特性ベクトル：Ｒ
トレース：Ｔ
【００５７】
出力：
ランク結果のプリント
【００５８】
アルゴリズム：ＲａｎｋＰａｃｋｅｔＴｒａｃｅｓ（ｌ，Ｒ，Ｔ）
【００５９】
【数３】
0006371852.tif 000004
【００６０】
（１，｜Ｔ｜）内の各ｋに対して：
Ｓ．ｐｕｓｈｂａｃｋ（ｋ，Ｒｋ，ｌ）
ｅｎｄ  ｆｏｒ
パケット特性Ｒｋ，ｌに関してＳを分類、
Ｒｋ，ｌの昇順でＳをプリント
【００６１】
図６は、待ち時間特性（Ｒｋ，ｌａｔｅｎｃｙ）を使用してランク付けされるパケットトレースを示す。
【００６２】
図７は、リンクの数（Ｒｋ，ｎｕｍｌｉｎｋ）を使用してランク付けされるパケットトレースを示す。
【００６３】
図８は、パケットサイズ（Ｒｋ，ｓｉｚｅ）を使用してパケットトレースをランク付けするランク付けの例を示す。
【００６４】
パケットクエリ４０３では、ユーザがある入力のパケットトレースを見つけたい場合、クエリ関数がかかる目標を達成することができる。一組の条件を前提として、この手順は、一組のトレーススライスをクエリし、クエリ条件に一致する組を報告する。
【００６５】
図９は、クエリ条件の例を示す。図１０は、クエリ関数によって報告される一組のパケットトレースを示す。
【００６６】
クエリアルゴリズムは、パケット特性ベクトルを横断し、全てのクエリ条件を満たすいずれかの一致した項目が存在する場合、それは、一致した項目をリストにプッシュする。横断後、それは、一致したパケットトレースのリストを提示する。
【００６７】
入力：
クエリ数：１
クエリ条件：Ｑ＝｛ｑ｝であり、クエリ条件は、「ａｎｄ」又は「ｏｒ」のいずれかで接続され得る。
パケット特性ベクトル：Ｒ
トレーススライス：Ｔ
【００６８】
出力：
クエリ結果のプリント
【００６９】
アルゴリズム：Ｑｕｅｒｙ（ｌ，Ｑ，Ｒ，Ｔ）
【００７０】
【数４】
0006371852.tif 000005
【００７１】
（１，｜Ｔ｜）内の各ｋに対して：
Ｒｋ，ｌが、Ｑにおける条件を満たす場合：
Ｓ．ｐｕｓｈｂａｃｋ（ｋ，Ｒｋ，ｌ）
ｅｎｄ  ｆｏｒ
Ｒｋ，ｌの昇順でＳをプリント
【００７２】
本発明は、ハードウェア、ファームウェア、若しくはソフトウェア、又はこれら３つの組み合わせにおいて実施され得る。好ましくは本発明は、プロセッサ、データ記憶システム、揮発性及び不揮発性メモリ、及び／又は記憶素子、少なくとも１つの入力装置、並びに少なくとも１つの出力装置を有する、プログラム可能なコンピュータにおいて実行されるコンピュータプログラムにて実施される。更なる詳細は、米国特許第８３８０５５７号で述べられており、その内容は、参照により組み込まれる。
【００７３】
例として、本発明を支持するためのコンピュータのブロック図が、次に図１１で述べられている。コンピュータは好ましくは、プロセッサ、ランダムアクセスメモリ（ＲＡＭ）、プログラムメモリ（好ましくは、書き込み可能な読み取り専用メモリ（ＲＯＭ）、例えば、フラッシュＲＯＭ）、及びＣＰＵバスにより接続された入力／出力（Ｉ／Ｏ）コントローラを含む。コンピュータは、任意に、ハードディスク及びＣＰＵバスに接続されたハードドライブコントローラを含み得る。ハードディスクは、本発明のようなアプリケーションプログラム及びデータを記憶するために使用され得る。あるいは、アプリケーションプログラムは、ＲＡＭ又はＲＯＭに記憶され得る。Ｉ／Ｏコントローラは、Ｉ／Ｏバスにより、Ｉ／Ｏインターフェースに接続される。Ｉ／Ｏインターフェースは、シリアルリンク、ローカルエリアネットワーク、ワイヤレスリンク、及び並列リンクなどの通信リンクを介して、アナログ又はデジタルの形態でデータを送受信する。任意により、ディスプレイ、キーボード、及びポインティング装置（マウス）がまた、Ｉ／Ｏバスに接続されてもよい。あるいは、Ｉ／Ｏインターフェース、ディスプレイ、キーボード、及びポインティング装置のために別個の接続（別個のバス）が使用されてもよい。プログラミング可能な処理システムが予めプログラムされてもよく、又はこれは別のソース（例えば、フロッピーディスク、ＣＤ−ＲＯＭ、又は別のコンピュータ）からプログラムをダウンロードすることにより、プログラム（及び再プログラム）されてもよい。
【００７４】
各コンピュータプログラムは、機械可読記憶媒体、又は汎用若しくは特定目的プログラム可能コンピュータにより読み取り可能な装置（例えば、プログラムメモリ、又は磁気ディスク）に有形に記憶され、記憶媒体又は装置がコンピュータにより読み込まれるときに、本明細書に記載される手順を実行するように、コンピュータの動作を構成及び制御する。本発明のシステムはまた、コンピュータプログラムを備えるものとして構成されるコンピュータ可読記憶媒体において実現されるものとみなすこともでき、このように構成された記憶媒体は、コンピュータを特定の規定の様式で動作させ、本明細書に記載される機能を実行する。
【００７５】
上述から、本発明は、それらのサイズ、分散状態、及びネットワーク仮想化によって導入される追加の複雑性により、大変な作業であり得る、動作ネットワークの監視及びトラブルシューティングを提供するということが理解され得る。ネットワークオペレータ／インテグレータに利用可能なトラフィック分析ツールセットは、限られている。本発明は、ネットワーク監視及びトラブルシューティングのためのネットワークパケットトレース要約及び特徴付けの技術を提供する。それは、オペレータ／インテグレータがデータパスルーティング問題を診断することを加速することに役立ち得、かつ新しいネットワーク可視化及びトラフィック分析を可能にする。該技術は、柔軟性があり、ネットワークトポロジ情報における事前要件がなく、完全又は部分的ルーティングパスのいずれかを変換するパケットトレースに対処することができる。
【００７６】
上述は、あらゆる点において、制限的ではなく、例解的かつ例示的であるとして理解されるものとし、本明細書において開示される本発明の範囲は、発明を実施するための形態からではなく、むしろ特許法によって許容される最も広い範囲に従って解釈される請求項から判断されるものとする。本明細書において図示及び説明される実施形態は、本発明の原理を例解するものであるにすぎず、当業者は、本発明の範囲及び趣旨から逸脱することなく、種々の修正を実装し得ることが理解されるものとする。当業者は、本発明の範囲及び趣旨から逸脱することなく、種々の他の特性の組み合わせを実装し得る。
【図１】
0006371852.tif 000006
【図２】
0006371852.tif 000007
【図３Ａ】
0006371852.tif 000008
【図３Ｂ】
0006371852.tif 000009
【図４】
0006371852.tif 000010
【図５】
0006371852.tif 000011
【図６】
0006371852.tif 000012
【図７】
0006371852.tif 000013
【図８】
0006371852.tif 000014
【図９】
0006371852.tif 000015
【図１０】
0006371852.tif 000016
【図１１】
0006371852.tif 000017