(57)【要約】データセンターでのアプリケーション依存パスを求める方法とシステムが開示されている。本方法とシステムは、複数のスイッチおよびエージェントで、サーバ上のアプリケーションのトラフィック量のデータを取得し、そのデータに基づいて、複数のアプリケーションのすべてのコンポーネントのアプリケーショントラフィック行列を生成し、特異値分解またはパワー因数分解剰余誤差法によるランク推定でトラフィック行列からデータセンターにおけるアプリケーションの数を推定し、推定したアプリケーションの数を用いてトラフィック行列を、非負行列因数分解処理で第１および第２の行列に分解する。第１の行列は、複数のアプリケーションの各々に属するコンポーネントの集合を表し、第２の行列は、時間とともに各アプリケーションによって生成されたトラフィックの量を表す。第１および第２の行列におけるノイズが、コンカレント体積比に基づく相関処理で除去される。
2013526237.tif 000002
【特許請求の範囲】
【請求項１】
複数のサーバと、複数の異なったアプリケーションと、を有し、各アプリケーションが複数のコンポーネントを有し、１つまたは２つ以上のコンポーネントが１つまたは２つ以上の他のアプリケーションで共有されているデータセンターにおいてアプリケーション依存パスを求める方法であって、
前記複数のサーバ上のアプリケーションのトラフィック量のデータを取得するステップと、
前記アプリケーションのトラフィック量のデータに基づいて、前記複数のアプリケーションのすべてのコンポーネントのアプリケーショントラフィック行列を生成するステップと、
前記トラフィック行列から前記データセンターにおける前記アプリケーションの数を推定するステップと、
前記推定したアプリケーションの数を用いて、前記トラフィック行列を、前記複数のアプリケーションの各々に属するコンポーネントの集合を表す第１の行列と、時間とともに各アプリケーションによって生成されたトラフィックの量を表す第２の行列と、に分解するステップと、を有する方法。
【請求項２】
前記複数のサーバ上のアプリケーションのトラフィック量のデータを取得するステップは、空間領域と時間領域とにおいて行われる、請求項１に記載の方法。
【請求項３】
前記アプリケーショントラフィック行列を生成するステップは、前記アプリケーションのグループのための、前記アプリケーショントラフィック行列によって表されるアプリケーション接続状態グラフを生成することを含む、請求項１に記載の方法。
【請求項４】
前記アプリケーションの数を推定するステップは、特異値分解またはパワー因数分解剰余誤差法によるランク推定により行われる、請求項１に記載の方法。
【請求項５】
前記パワー因数分解剰余誤差法による前記ランク推定は、パワー因数分解処理を用いる、請求項４に記載の方法。
【請求項６】
前記トラフィック行列を分解するステップは、非負行列因数分解処理により行われる、請求項１に記載の方法。
【請求項７】
前記第１および第２の行列からノイズを除去するステップをさらに有する、請求項１に記載の方法。
【請求項８】
前記ノイズを除去するステップは、コンカレント体積比に基づく相関処理で行われる、請求項７に記載の方法。
【請求項９】
複数のサーバと、複数の異なったアプリケーションと、を有し、各アプリケーションが複数のコンポーネントを有し、１つまたは2つ以上のコンポーネントが１つまたは２つ以上の他のアプリケーションで共有されているデータセンターにおいてアプリケーション依存パスを求めるシステムであって、
データ収集コンポーネントと、
前記データ収集コンポーネントとデータ通信する制御器と、を有し、
前記データ収集コンポーネントは、
各々が、前記複数のサーバ上のアプリケーションのトラフィック量のデータを取得するミラーポートを有する複数のスイッチと、
前記ミラーポートの各々を監視する監視エージェントと、を有し、
前記制御器は、
前記監視サーバによって取得された前記アプリケーションのトラフィック量のデータに基づいて、前記複数のアプリケーションの全てのコンポーネントのアプリケーショントラフィック行列を生成する前処理ユニットと、
前記接続状態グラフ化ユニットによって生成された前記トラフィック行列から、前記データセンターにおけるアプリケーションの数を推定し、前記推定したアプリケーションの数を用いて、前記トラフィック行列を、前記複数のアプリケーションの各々に属するコンポーネントの集合を表す第１の行列と、時間とともに各アプリケーションによって生成されたトラフィックの量を表す第２の行列と、に分解するアプリケーション分解ユニットと、を有するシステム。
【請求項１０】
前記複数のスイッチは、前記アプリケーションのトラフィック量のデータを空間領域と時間領域とにおいて取得する、請求項９に記載のシステム。
【請求項１１】
前記アプリケーショントラフィック行列は、前記アプリケーションのグループのためのアプリケーション接続状態グラフを表す、請求項９に記載のシステム。
【請求項１２】
前記アプリケーション分解ユニットは、前記データセンターにおけるアプリケーションの数を推定するために、特異値分解またはパワー因数分解剰余誤差法によるランク推定を行う、請求項９に記載のシステム。
【請求項１３】
パワー因数分解剰余誤差法による前記ランク推定は、パワー因数分解処理を用いる、請求項１２に記載のシステム。
【請求項１４】
前記アプリケーション分解ユニットは、前記トラフィック行列を前記第１および第２の行列に分解するために、非負行列因数分解処理を行う、請求項９に記載のシステム。
【請求項１５】
前記第１および第２の行列からノイズを除去する後処理ユニットをさらに有する、請求項９に記載のシステム。
【請求項１６】
前記後処理ユニットは、前記第１および第２の行列からノイズを除去するために、コンカレント体積比に基づく相関処理を行う、請求項１５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願はシステムの管理と運用に関する。特に、本願は、企業ネットワークおよびデータセンターにおけるアプリケーション依存状態ディスカバリを求めるシステムと方法に関する。
【０００２】
本願は、全開示が参照によってここに含まれる、２０１０年５月６日に出願された米国仮出願第６１／３３１，９６２号の利益を主張する。
【背景技術】
【０００３】
今日の企業ネットワークと現代のデータセンターは、異質なアプリケーション（たとえば、電子商取引、コンテンツ配信）とサービス（たとえば、ＤＮＳ、アクティブディレクトリ、電子メール、および認証）とを有し、これらは互いに複雑にインターリーブされている。具体的には、各サービスは、多数のアプリケーションをサポートし、特定のアプリケーションは、多くの様々なサービスに依存している。さらに、各アプリケーション自体が通常、多数のコンポーネントを有し、それらのいくつかは多数のアプリケーションと共有されることがある。各アプリケーションのコンポーネントとそれらの相互依存状態を理解し、識別することは、異常検出と故障診断、システムの改良と補修、アプリケーションの分離と移行といった、広範囲のシステム管理タスクにとって重要である。たとえば、多層構成のアプリケーションは、アプリケーションサーバのような共通の複数のコンポーネントを有する、オークションアプリケーション、電子商取引アプリケーションのような様々なアプリケーションを含むことがあり得る。
【０００４】
この問題に対する既存の方法は、アクティブサーバの使用から軽量のミドルウェアの配置、そしてネットワークトラフィックの非侵入式の監視に至る様々な技術を用いている。アプリケーション依存状態は、ネットワークおよびシステムの少なくとも一方について得られた追跡記録に対して相関分析を行うことによって推測される。これらの方法は、実際にはある限界を示すことがある対のフロー解析に依存している。特に、大規模なトランザクションシステムにおいて一般的であるマルチホップ（すなわち、３つ以上の）依存状態は、対の依存状態の情報からは決して推測することはできない。これは、マルチホップの重複する複数のアプリケーションの場合のように、単一のコンポーネントが多数のアプリケーションによって共用され、対の解析の正確さが低下する、重複するアプリケーションの存在下で特に言える。さらに、フロー対相関は、所与の時間間隔内でホスト毎に行われる。この間隔の適切な長さを選択することは、性能と正確さを求める上で重要であるが、誤検出が多くなる傾向もある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、自動化されたアプリケーション依存状態ディスカバリシステムと方法が、アプリケーションの大規模な成長とサービスのコンポーネント間の複雑な相互関係に直面している企業ネットワークおよびデータセンタの、日々のシステム管理および運用にとって必要である。
【課題を解決するための手段】
【０００６】
複数のサーバと、複数の異なったアプリケーションと、を有し、各アプリケーションが複数のコンポーネントを有し、１つまたは2つ以上のコンポーネントが１つまたは２つ以上の他のアプリケーションで共有されているデータセンターにおいてアプリケーション依存パスを求める方法が開示される。本方法は、複数のサーバ上のアプリケーションのトラフィック量のデータを取得するステップと、アプリケーションのトラフィック量のデータに基づいて、複数のアプリケーションのすべてのコンポーネントのアプリケーショントラフィック行列を生成するステップと、トラフィック行列からデータセンターにおけるアプリケーションの数を推定するステップと、推定したアプリケーションの数を用いて、トラフィック行列を、複数のアプリケーションの各々に属するコンポーネントの集合を表す第１の行列と、時間とともに各アプリケーションによって生成されたトラフィックの量を表す第２の行列と、に分解するステップと、を有する。
【０００７】
いくつかの実施態様において、本方法は、第１および第２の行列からノイズを除去するステップをさらに有する。
【０００８】
複数のサーバと、複数の異なったアプリケーションとを有し、各アプリケーションが複数のコンポーネントを有し、１つまたは2つ以上のコンポーネントが１つまたは２つ以上の他のアプリケーションで共有されているデータセンターにおいてアプリケーション依存パスを求めるシステムも開示される。本システムは、データ収集コンポーネントと、データ収集コンポーネントとデータ通信する制御器と、を有する。データ収集コンポーネントは、各々が、複数のサーバ上のアプリケーションのトラフィック量のデータを取得するミラーポートを有する複数のスイッチと、ミラーポートの各々を監視する監視エージェントと、を有する。制御器は、監視サーバによって取得されたアプリケーションのトラフィック量のデータに基づいて、複数のアプリケーションの全てのコンポーネントのアプリケーショントラフィック行列を生成する接続状態グラフ化ユニットと、接続状態グラフ化ユニットによって生成されたトラフィック行列から、データセンターにおけるアプリケーションの数を推定する個体数推定ユニットと、個体数推定ユニットにより推定されたアプリケーションの数を用いて、トラフィック行列を、複数のアプリケーションの各々に属するコンポーネントの集合を表す第１の行列と、時間とともに各アプリケーションによって生成されたトラフィックの量を表す第２の行列と、に分解するアプリケーション分解ユニットと、を有する。
【０００９】
いくつかの実施態様において、本システムの制御器は、第１および第２の行列からノイズを除去する後処理ユニットをさらに有する。
【図面の簡単な説明】
【００１０】
【図１】図１は、データセンターにおけるアプリケーション依存パスを求める、本開示によるシステムの代表的実施形態のブロック図である。
【図２】図２は、本開示のトラフィックグラフを表すトラフィック行列の代表的実施形態を示す図である。
【図３】図３は、本開示のシステムによって行われる、データセンターのアプリケーション依存状態ディスカバリ方法の代表的実施形態のフローチャートである。
【図４Ａ】図４Ａは、図３の方法において用いられたパワー因数分解処理の代表的実施形態のフローチャートである。
【図４Ｂ】図４Ｂは、図３の方法において用いられた、パワー因数分解剰余誤差処理によるランク推定の代表的実施形態のフローチャートである。
【図５】図５は、図３の方法において用いられた、非負行列因数分解に基づく依存状態分解処理の代表的実施形態のフローチャートである。
【図６】図６は、図３の方法において用いられた、隣接回線上のアプリケーショントラフィックを相互に関連付ける、コンカレント体積比（ＣＶＲ）ベース相関処理を図示化したものである。
【図７】図7はＣＶＲ相関処理の代表的実施形態のフローチャートである。
【発明を実施するための形態】
【００１１】
本開示は、時間とともに動的に構成された一時的グローバルアプリケーショントラフィックグラフと、データセンターの各サーバにおいて観察された空間局所的トラフィックとを用いて、企業ネットワーク、クラウドベースのデータセンター、そして他のデータセンターにおけるアプリケーション依存状態を抽出する行列因数分解システムと方法を提供する。データセンターは、複数の様々なアプリケーション（たとえば、電子商取引、コンテンツ配信）を実行する複数のサーバを含む。各アプリケーションは、複数のコンポーネント（たとえば、ウェブサーバ、アプリケーションサーバ、データベースサーバ）をアプリケーション依存パス内に有しており、１つまたは複数のコンポーネントが１つまたは複数の他のアプリケーションで共有される。
【００１２】
そのようなデータセンターは通常、多数の多層構成のアプリケーションのホストとなるので、複数のアプリケーションリクエストが空間領域および時間領域の両方において重複し、これが従来の対の統計的相関技術により、インターリーブされ、しかし独立した複数のアプリケーションを正確に抽出することが非常に困難にする。本開示のシステムおよび方法では、システムの複数のスナップショット、および、それらの通時的な変化の両方を取得するアプリケーショントラフィックの行列ベースの表現が用いられる。本システムおよび方法は、アプリケーショングラフの行列表現を、それぞれが単一のアプリケーションを表す小さい複数のサブグラフに分解した。このことは、本開示のシステムおよび方法を、マルチホップの複数のアプリケーションおよび重複する複数のアプリケーションの少なくとも一方の存在下で特に有効なものにする。
【００１３】
アプリケーションの数は、インターリーブされ、かつ重複する複数のアプリケーションリクエストのために、通常、先験的には知られておらず、それぞれのアプリケーションサブグラフの発見を困難にしている。本開示のシステムおよび方法では、アプリケーションの数は、完全なおよび不完全なトラフィックデータシナリオのもとで、理論的境界保証を有する特異値分解ベースのソルバーまたはパワー因数分解ベースのソルバーを有する低ランク行列推定を用いて求められる。
【００１４】
スイッチからのトラフィック盗聴は、スイッチと監視ホストの能力によって制限される。スイッチは通常、同時に少数のポートしか映し出すことができない。さらに、それぞれが多数のポートを有する多数のスイッチにわたって収集された監視データは、結果として、大量の総ネットワークトラフィックと、場合によってはパケット損失をもたらすことがある。両方の場合も監視データの著しい損失につながる。この問題を克服するために、本開示のシステムおよび方法は、十分な冗長をもたらす通時的なデータを有効に利用し、かつデータ損失および推定誤りに復元力を与えるパワー因数分解に基づく技術を用いる。本開示のシステムおよび方法は、データセンターにおけるアプリケーション依存パスを求めるために、ネットワークの分散監視と集中データ処理も用いる。
【００１５】
図１は、本開示のシステムの典型的実施形態のブロック図である。本システムは、データ収集コンポーネント１００と中央サーバ、すなわち中央制御器１１０を有する。データ収集ユニット１００は、複数のスイッチ１０２と、これらスイッチに接続され、これらからトラフィックデータを収集する複数の監視エージェント１０４を有し、中央制御器１１０は、前処理ユニット１１２と、依存状態分解ユニット１１４と、後処理ユニット１１６と、を有している。制御器１１０の前処理ユニット１１２、依存状態分解ユニット１１４、および、後処理ユニット１１６は、制御器１１０の１つまたは２つ以上のプロセッサ（不図示）によって実現される。１つまたは複数のプロセッサは、たとえば、制御器１１０の１つまたは２つ以上のメモリに格納され、制御器１１０がここに記載された、前処理、依存状態分解、および、後処理の方法および処理を実行するのを可能にする複数のプログラム命令を実行する。
【００１６】
データ収集コンポーネント１００は、データセンターのネットワーク分散監視を実行し、下り回線には、同じラックに存在するデータセンターの複数のサーバ（たとえば、２０から８０台のサーバ）が接続され、上り回線には、上層の集合スイッチが接続される、ネットワークのツリー構造内の最下層に位置する複数のラック上面（ＴＯＲ）スイッチ（エッジスイッチ）を含むことがある。ネットワークトラフィックは、エッジスイッチ１０２のミラーポートを介して専用の監視サーバ１０４（監視エージェント）に直接、接続されている各エッジスイッチ１０２において取得される。この種のポートミラーリングは、トラフィックを妨害するのに最小の影響を与えながら、その効率的なトラフィック取得能力のため、用いられている。周期的に、監視サーバは、収集されたデータを処理し（フローレベル情報を構文解析し、抽出し、現在の間隔における各フローに対するパケットの数を計数し）、各アプリケーション層回線のトラフィック量を計算し、そのデータを制御器１１０に送る。
【００１７】
各監視サーバから受信されたデータは制御器１１０によって一元処理され、制御器１１０は、複数の監視サーバから受信した情報を前処理し、依存状態分解し、後処理する。
【００１８】
前に述べたように、すべての監視エージェント１０４からデータが一旦受信されると、制御器１１０の前処理ユニット１１２は、該データを前処理する。前処理用ニット１１２はまず該データの浄化、たとえば、種々のスイッチ１０２に対する測定間隔の調整や、冗長の除去（たとえば、パケットが横切る２つのスイッチポートをシステムが同時に監視する場合、同じパケットが２度取得されることがある）を行う。データの浄化の後、前処理ユニット１１２は、すべてのアプリケーショングループについて完全なアプリケーション接続状態グラフを連続的に作成する。各グラフは、トラフィック行列Ｘによって表され、その例が図２に示されており、参照番号２００によって全体が示されている。トラフィック行列Ｘの各列は、対応する時間間隔の間に観察された全ての＜IP：ポート＞対間のトラフィック量を記録し、トラフィック行列Ｘの各行は、対応するアプリケーション回線（たとえば、回線Ａ-Ｂ（アプリケーションコンポーネントＡ、アプリケーションコンポーネントＢ））上のトラフィック量の履歴を表している。トラフィック行列Ｘは、空間領域と時間領域の両方にわたる全てのアプリケーションコンポーネントの動的接続関係を示している。
【００１９】
データの前処理後、制御器１１０の依存状態分解ユニット１１４は、データの依存状態分解処理を実行する。依存状態分解ユニット１１４は、特に、複数のシステムコンポーネントをアプリケーション毎に分解する際の重要なシステム情報である、データセンターにおいて実行中のアプリケーションの数の予備知識を持っていない。依存状態分解ユニット１１４は、データセンターにおいて実行中のアプリケーションの数を、パワー因数分解または特異値分解（ＳＶＤ）に基づく方法によるランク推定によって求め、または推定する。アプリケーションの数は、アプリケーション依存状態を発見するために依存状態分解アルゴリズムにおいてさらに用いられる。
【００２０】
依存状態分解ユニット１１４によって発見されたアプリケーション依存状態は制御器１１０の後処理ユニット１１６によって後処理される。前のコンポーネントにおいて生成されたアプリケーション依存状態は、測定ノイズによって影響され、誤検出を含むことがある。したがって、結果を相互検証し、不正確な推定を減らすために後処理が必要である。本開示の後処理ユニット１１６は、依存状態サブグラフ内の相互に関係付けられたエッジを、依存状態サブグラフの各ノード上の対の回線相関を用いて局所的に識別するために、コンカレント体積比（ＣＶＲ）を用いる。後処理ユニット１１６は、複数の依存状態グラフを融合、取り除くための規則も取り入れている。これらの規則は、トラフィック相関スコアの経験的観測のみならずオペレータの専門知識を利用している。
【００２１】
図３は、本開示のシステムによって行われる、データセンターのアプリケーションの依存状態の発見方法の代表的実施形態のフローチャートである。本方法は、ブロック３００において、空間領域と時間領域におけるサーバ上のアプリケーショントラフィック量を取得することで始まる。トラフィック量のデータは、関連する複数の監視エージェント１０４に直接、接続されている複数のエッジスイッチ１０２によって取得される。監視エージェント１０４は周期的に、収集されたデータを処理し、各アプリケーション層の回線のトラフィック量を計算し、該データを制御器１１０に送る。
【００２２】
ブロック３２０に移動して、制御器１１０の前処理ユニット１１２は、アプリケーション層の接続状態グラフを生成する。各グラフは、アプリケーションのトラフィック量のデータに基づく、アプリケーションの全てのコンポーネントのアプリケーショントラフィック行列（トラフィック行列Ｘ）によって表される。接続状態グラフ生成メカニズムは、（いくつかの入力接続部を用いて）複数のサービスノードを識別することと、一過性の接続を単一のエッジに集約することと、クライアントのＩＰアドレス配布に基づいてクライアントの方を向くノードを識別することを含む。多くの異なったクライアントＩＰアドレスを有するサービスノードが、クライアントの方を向くサービスノード（すなわち、接続状態グラフにおけるｓｒｃノード）である可能性がある。このステップはまた、大きく複雑なグラフを、それぞれのアプリケーショングループを表す、より簡単な複数のグラフに分割するために、全てのアプリケーション（たとえば、ＤＮＳ）によって使用される、データセンターの複数の共通サービスノードを識別し、除去する。
【００２３】
ブロック３４０において、トラフィック行列Ｘは、データセンター内のアプリケーションの数を推定するために、制御器１１０の依存状態分解ユニット１１４によって使用される。制御器１１０の依存状態分解ユニット１１４はブロック３６０において、トラフィック行列Ｘを、ブロック３４０において推定されたアプリケーションの数を用いて、第１、第２の行列Ｗ、Ｈ（図２においてそれぞれ参照番号２１０、２２０によって全体が示される）に分解する。第１の行列Ｗは、アプリケーションの各々に属する複数のコンポーネントのセット、すなわちアプリケーション依存状態パスを表し、第２の行列Ｈは、時間とともに各アプリケーションによって生成されたトラフィックの量を表す。制御器１１０の後処理ユニット１１６は、ブロック３８０において、第１、第２の行列Ｗ、Ｈからノイズを除去する。
【００２４】
図３のブロック３４０を再び参照すると、制御器１１０の依存状態分解ユニット１１４は、トラフィック行列Ｘの最適ランクを低ランク推定によって求めるために、完全および不完全なトラフィックデータシナリオのもとで特異ベクトル分解（ＳＶＤ）またはパワー因数分解に基づくソルバーを用いる。完全な入力データの場合、アプリケーションの数は、ＳＶＤソルバーによって、ランク最小化問題（ＲＭＰ）を解くことによって推定される。ＲＭＰは、
【００２５】
【数１】
2013526237.tif 000003
【００２６】
を最小化し、ここで、
【００２７】
【数２】
2013526237.tif 000004
【００２８】
Ｕはn×nの単位行列（すなわち、ＵＴＵ＝Ｉ）、Ｖはm×mの単位行列（すなわち、ＶＴＶ＝Ｉ）、そして
【００２９】
【数３】
2013526237.tif 000005
【００３０】
は、n×mの対角行列で、n×mの対角行列であるΣから最大でｋ個の特異値δiを有する。トラフィック行列Ｘの最良のランクｒの近似は、
【００３１】
【数４】
2013526237.tif 000006
【００３２】
ならばｋで、εはノイズの許容値である。不完全な入力データの場合、トラフィック行列Ｘは不足しているいくつかの事項であるので、パワー因数分解は、行列距離‖Ｍ・（Ｘ−ＡＢ）‖が最小となるように（ここで、Ｍは二値入力のマスク行列で、Ｘijが見当たらなければＭijは０に等しく、そうでなければＭijは１に等しい）、それぞれn＊r、r＊mの次元を有する２つの行列要素ＡとＢを計算する、数値的にロバストなソルバーである。ｒ<min(m,n)と仮定すると、本方法は、図４Ａのフローチャートに示されたパワー因数分解法を用いて、Ｘの最良のランクｒの近似を計算し、ｒは既知である。
【００３３】
図４Ａにおいて、トラフィック行列Ｘ、そのマスク行列Ｍ、ランクｒは、パワー因数分解法の入力４０１である。ブロック４０２において、パワー因数分解法は、大きさn＊rを有するランダム行列Ａ０で始まり、ｋ番目の繰り返しｋを０にセットする。ブロック４０３において、ｋ番目の繰り返しｋはｋ＋１にセットされる。ブロック４０４において、行列Ａｋ-１が与えられると、r＊mの大きさの行列Ｂkが、行列距離‖Ｍ・(Ｘ−Ａk-１Ｂk) ‖が最小となるように、計算される。次に、行列Ｂkが正規化される。ブロック４０５において、行列Ｂｋが与えられると、n＊rの大きさの行列Ａkが、行列距離‖Ｍ・(Ｘ−ＡkＢk) ‖が最小となるように、計算される。ブロック４０６において、行列ＡｋとＢｋが収束したかどうかが判定される。行列ＡｋとＢｋが収束したならば、行列ＡｋとＢｋが出力４０７に生成される。行列ＡｋとＢｋが収束していないならば、本方法のブロック４０３、４０４、４０５、そして４０６が、行列ＡｋとＢｋが収束するまで流れ線４０８において繰り返される。
【００３４】
パワー因数分解法は、トラフィック行列Ｘn＊m（ここで、nとmは行列Ｘの行と列の次元である）のランク情報を直接、予測することはできず、ここでランクｒは行列Ａn＊rとＢr＊mを最適化する前に知られていなければならない。しかしながら、妥当な範囲内でランクｒを検索し、行列距離（‖Ｍ・（Ｘ−ＡＢ）‖）の最終近似誤差をランクｒに対して描くことは、誤差曲線が鞍点を有する真のランク
【００３５】
【数５】
2013526237.tif 000007
【００３６】
を示す強力な経験則かもしれない。ランクｒが大きくなると、行列距離‖Ｍ・（Ｘ−ＡＢ）‖の誤差は単調に減少するが、真のランク
【００３７】
【数６】
2013526237.tif 000008
【００３８】
を通過した後は、それ程、小さくは減少しない。もしＡrとＢrが、ランクｒを所与のものとして、２つの行列要素を示すならば、εrはランクｒ近似に対する対応する適合誤差を示す。本開示は、パワー因数分解剰余誤差解析によって不完全行列Ｘのランクを推定する方法を要約する、図４Ｂのフローチャートに描かれている方法を提供する。パワー因数分解ソルバーは、収束まで各繰り返しにおいて用いられる。このパワー因数分解ソルバーは、完全な行列Ｘ、または、欠損値を有する行列Ｘの両方に対して適用可能である。
【００３９】
図４Ｂにおいて、トラフィック行列Ｘ、そのマスク行列Ｍ、そして閾値ε（適合誤差差に対する収束基準の閾値）は、パワー因数分解剰余誤差（ＲＥＰＦＲＥ）法によるランク推定のための入力４００である。ＲＥＰＦＲＥ法は、ランクｒを１に、Ａn＊r、Ｂr＊mを図４Ａのパワー因数分解法ＰＦに等しく設定し、ランクｒの適合誤差εrを‖Ｍ（Ｘ−Ａn＊rＢr＊m）‖として計算することによって、ブロック４１０において開始する。ブロック４２０において、ランクｒはｒ＋１に等しく設定される。ブロック４３０において、Ａn＊r、Ｂr＊mは図４Ａのパワー因数分解法ＰＦに等しく設定され、ランクｒ(ｒ＋１）に対して、適合誤差εrは‖Ｍ（Ｘ−Ａn＊rＢr＊m）‖として計算され、誤差の差ｄは
【００４０】
【数７】
2013526237.tif 000009
【００４１】
として計算される。ブロック４４０において、差ｄが閾値εよりも小さいかどうか判定される。もし差ｄが閾値εよりも小さければ、行列Ｘの推定されたランクは出力４５０においてランクｒと設定され、ここでｒはアプリケーションの数である。もし差ｄが閾値εよりも小さくなければ、ＲＥＰＦＲＥのブロック４２０、４３０、そして４４０は流れ線４６０で繰り返される。
【００４２】
図３のブロック３６０を再び参照すると、制御器１１０の依存状態分解ユニット１１４は、高次元のトラフィックデータにわたって従属アプリケーションサービス（特徴）を発見するために、非負行列の因数分解（ＮＭＦ）を用いることがある。ＮＭＦは、アプリケーションパターンの複数の組み合わせの非負の追加の性質に対して適用可能な非負の制約のもとでの行列因数分解の、管理されていない学習アルゴリズムである。非負のn＊mの行列Ｘが所与のものとすると、ＮＭＦは、
【００４３】
【数８】
2013526237.tif 000010
【００４４】
のように、非負のn＊r行列Ｗと非負のr＊m行列Ｈを求める。行列Ｘは、時間にわたって測定されたトラフィックを表すので、行列Ｗの各列ベクトルを用いて、異なった回線
【００４５】
【数９】
2013526237.tif 000011
【００４６】
上のトラフィック量がいくつかの線形相関を維持するアプリケーション依存状態サブグラフを解釈することができる。行列Ｈの各列ベクトルは、各時間サブショットにおける異なったリクエスト作業負荷に対するランクｒのアプリケーションの重みを示している。
【００４７】
一実施形態では、次の乗法更新規則は、行列ＷとＨ
【００４８】
【数１０】
2013526237.tif 000012
【００４９】
を得るために、目的関数‖Ｘ−ＷＨ‖2を最小にするように選択される。これらの更新規則は、行列Ｍを最適化するように行列Ｈを決定し、それから各最適化ループにおける行列を解くために行列Ｍを決定する双線形問題を解くものとして直接、実行し、代わりに採用する。収束は、通常の勾配降下法と比べて早い。第１の繰り返しにおける行列Ｈの初期化はランダムに選択することができる。ＮＭＦの他の重要な特性はその空間的局所性、すなわち局所化された観察からなる回線アプリケーションレベルのイベントの発見に特に適用できる、因数分解された基数の乏しさである。
【００５０】
アプリケーション依存状態分解におけるＮＭＦのアプリケーションの背後にある論法は３つの部分からなる。まず、観察されたトラフィック行列Ｘは、ＮＭＦ用の入力データに対する制約に当然一致する非負である。第２に、ＮＭＦは、両行列要素ＷとＨにおいて負の入力を許さない。これは、複数の基礎コンポーネントの付加的組み合わせのみが許されることを意味し、これは、各回線上のトラフィック測定値（もともと非負）が、複数のアプリケーションイベントによって引き起こされた複数の作業負荷の総和である、との本願の仮定と一致している。第３に、ＮＭＦは、考えられる意味解釈に対して、潜在的な、統計的依存状態トラフィックパターンをサブグラフとして発見または抽出することができる地球的規模のグラフ分解方法でもある。ＰＣＡや独立コンポーネント解析のような他の行列因数分解技術と比べて、ＮＭＦは、非負の制約のために、本願のトラフィックデータが所与として、意味論的により重要な結果をもたらす。
【００５１】
図５は、制御器１１０の依存状態分解ユニット１１４によって行われるＮＭＦベースの依存状態分解法の代表的実施形態のフローチャートである。トラフィック行列Ｘ、そのマスク行列Ｍ、ランクr、そして閾値δは、ＮＭＦベースの依存状態分解法のための入力５００である。ブロック５１０において、ＮＭＦベースの依存状態分解法は、n＊rの行列Ｗとr＊mの行列Ｈとをランダムに生成することで開始する。ブロック５２０において、行列ＷはＷ(ＸＨT)/(ＷＨＨT)と計算される。ブロック５３０において、行列ＨはＨ(ＷTＸ)/(ＷTＷＨ)と計算される。ブロック５４０において、行列距離‖Ｘ−ＷＨ‖が閾値δよりも小さいかどうか判定される。もし行列距離‖Ｘ−ＷＨ‖が閾値δよりも小さければ、行列Ｗ、Ｈが出力５５０に生成される。もし‖Ｘ−ＷＨ‖が閾値δよりも小さくなければ、本方法のブロック５２０、５３０、そして５４０が、‖Ｘ−ＷＨ‖が閾値δよりも小さくなるまで流れ線５６０において繰り返される。
【００５２】
図３のブロック３８０を再び参照すると、制御器１１０の後処理ユニット１１６は、たとえば、図６に示すように、特に、複数の入力または出力の接続が存在する場合について、隣接する複数の回線上のアプリケーショントラフィックを相互に関連付ける、コンカレント体積比（ＣＶＲ）ベースの相関技術を用いることがある。この方法は、依存状態分解法の結果の正当性を立証し、ノイズを除去する。
【００５３】
ＣＶＲ相関法では、ベクトルνiは、ある時間間隔Ｔにわたる、アプリケーションコンポーネント回線Ｌi上の総トラフィック量を表している。次に、２つの連続したアプリケーションコンポーネント回線ＬiとＬj上のＣＶＲ相関法は
【００５４】
【数１１】
2013526237.tif 000013
【００５５】
で測定され、ここで、ｌijは、同期した複数の時間間隔でベクトルνiとνjの同時並行性を示す０/１ベクトルである。具体的には、０/１ベクトル
【００５６】
【数１２】
2013526237.tif 000014
【００５７】
は、回線ＬiとＬjの両方が時間間隔ｔで通過するトラフィックを有するときに１にセットされ、他の場合には０にセットされる。回線ＬiとＬj上のトラフィックの因果関係を大雑把に推定するために、本願は、ＣＶＲスコア
【００５８】
【数１３】
2013526237.tif 000015
【００５９】
（ここで、上付き文字ｃはＬiによって引き起こされる割合Ｌjを表し、上付き文字ｅはＬjになるＬjの割合を表し、すなわち、アプリケーションコンポーネント回線同士間の因果関係を示すために）を用いる。直感的に、ＣＶＲスコア
【００６０】
【数１４】
2013526237.tif 000016
【００６１】
は、回線Ｌj上の総トラフィック量にわたって回線Ｌiによって引き起こされた回線Ｌj上のトラフィック量の割合を表し、ＣＶＲスコア
【００６２】
【数１５】
2013526237.tif 000017
【００６３】
は、回線Ｌi上の総トラフィック量にわたって回線Ｌj上のイベントを生ずる回線Ｌi上のトラフィック量の割合を計算する。
【００６４】
図６を再び参照すると、アプリケーションコンポーネント回線Ａ−ＢとＢ−Ｃ間の高ＣＶＲスコアは因果関係、すなわちＡ−Ｂ−Ｃは依存経路である。同様に、Ａ−ＢとＢ−Ｄ間の低ＣＶＲスコアは、Ａ−ＢとＢ−Ｄが独立した回線であることを示している。このことは、接続状態グラフを、２つの接続されたコンポーネント（またはアプリケーション）Ａ−Ｂ−ＣとＢ−Ｄに分割することになる。さらに、ＣＶＲスコアは、
【００６５】
【数１６】
2013526237.tif 000018
【００６６】
を、異なった時間間隔Ｔ、たとえば３００ミリ秒、５００ミリ秒、１秒、１０秒、・・・について評価することによって計算される。従属アプリケーション回線の場合、ＣＶＲスコアは異なった時間間隔にわたって安定であり、一方独立した回線の場合、特定の時間間隔においてＣＶＲスコアが突然低下することがある。これは、非常に短い時間間隔では高いリクエスト割合でさえ、総計されたトラフィック量が高いＣＶＲスコアを生じさせないからである。
【００６７】
一実施形態では、後処理の規則は次の通りである。単一の入力/出力の場合、ＣＶＲスコア
【００６８】
【数１７】
2013526237.tif 000019
【００６９】
がもし全ての時間間隔において高ければ、アプリケーションコンポーネント回線Ｌi、Ｌjは従属した対である。複数の出力を有する複数の入力の場合、ＣＶＲスコア
【００７０】
【数１８】
2013526237.tif 000020
【００７１】
を全ての回線ｉとjについて計算し、異なった時間間隔３０秒、１０秒、１秒、５００ミリ秒にわたるそれらの安定性を測定する。これに基づいて、従属した回線と独立した回線とが識別される。他の対の相関技術と同様に、ＣＶＲは、多段ネットワークにおける全依存経路を特定するのには適していない。その代わりに、分解段階（ＮＭＦ）の出力の正当性を立証し、誤検出を除去するのに有用である。一方、局所的な対の依存状態関係を識別し、複数の対をつなぎ、または縫い合わせて、高位のアプリケーションレベルの依存状態サブグラフを形成するためにＣＶＲを用いることができても、この処理はエラーが発生しやすい。その理由は、すべてのローカルな対が、識別され、かつ正確にグループ化される必要があるからであり、これは些細なことではない。データ行列の大域的な表現と、局所的なＣＶＲベースの検証が続く、トップダウンのアプリケーションレベルの分解を用いる戦略は、統計上のロバストさと正確さの良好なバランスを達成することができる。
【００７２】
図７は、制御器１１０の後処理ユニット１１６によって行われるＣＶＲ相関処理の流れ図である。制御器１１０の依存状態分解ユニット１１４の出力にある行列Ｗから導かれたアプリケーションの予想されるリストは、ＣＶＲ相関処理のための入力７００である。ブロック７１０において、各回線に対するアプリケーションコンポーネントの全ての回線と時系列が各予想されるアプリケーションについて行列Ｘから抽出される。ブロック７２０において、トラフィックの時系列が、共通の交点を有する各回線対（i,j）に対する異なった時間間隔について計算される。ブロック７３０において、ＣＶＲスコア
【００７３】
【数１９】
2013526237.tif 000021
【００７４】
は総和(νj*ｌij）/総和(νｊ)として計算される。ブロック７４０において、ＣＶＲスコア
【００７５】
【数２０】
2013526237.tif 000022
【００７６】
は総和(νj*ｌij）/総和(νi)として計算される。ブロック７５０において、ＣＶＲスコア
【００７７】
【数２１】
2013526237.tif 000023
【００７８】
は、評価された回線対について、ｘ軸上の時間間隔に対してプロットされる。ブロック７６０において、ＣＶＲスコアが回線(i,j)の間で安定しているかどうか判定される。もしＣＶＲスコアが回線iとjの間で安定しているならば、回線i,jが従属したエッジである指示が出力７７０に生成される。７７０におけるこの出力は、全処理の出力（３８０における出力）として各アプリケーションを最後に生じる前に後処理１１６において用いられる。
【００７９】
本開示の代表的な図面と特定の実施形態を記載し、説明したが、特許請求の範囲に記載された本発明の範囲は、説明した特定の実施形態に限定されないことが理解されるべきである。したがって、これら実施形態は、限定的よりも例示的と見なされるべきであり、以下の特許請求の範囲に記載された本発明の範囲と、それらの構造上および機能上の等価物から外れることなく、変形がこれら実施形態において当業者によってなされてもよいことが理解されるべきである。
【図１】
2013526237.tif 000024
【図２】
2013526237.tif 000025
【図３】
2013526237.tif 000026
【図４Ａ】
2013526237.tif 000027
【図４Ｂ】
2013526237.tif 000028
【図５】
2013526237.tif 000029
【図６】
2013526237.tif 000030
【図７】
2013526237.tif 000031
【国際調査報告】
2013526237.tif 000032
2013526237.tif 000033