System and method for determining application dependency paths in a data center

RELATED APPLICATIONS

This application claims the benefit of <patcit id="pcit0001" dnum="US61331962A" dnum-type="L"><text>U.S. Provisional Application No. 61/331,962, filed May 6, 2010</text></patcit>, the entire disclosure of which is incorporated herein by reference.

FIELD

This application relates to system management and operation. More particularly, this application relates to a system and method for determining application dependency discovery in enterprise networks and data centers.

BACKGROUND

Today's enterprise networks and modem data centers have heterogeneous applications (e.g., e-commerce, content delivery) and services (e.g., DNS, active directory, email, and authentication), which are interleaved with each other in a complicated manner. Specifically, each service may support multiple applications and a particular application may rely on many different services. Moreover, each application itself usually has multiple components, some of which may be shared with multiple applications. Understanding and identifying components and their inter-dependencies of each application is critical for a wide spectrum of system management tasks, such as anomaly detection and failure diagnosis, system upgrading and patching, and application isolation and emigration. For example, a multi-tier application can include different applications, such as an auction application and an e-commerce application, which have common components, such as an application server.

Existing approaches to this problem employ a variety of techniques ranging from active server instrumentation to light-weight middleware deployment, and to non-intrusive network traffic monitoring. Application dependencies are inferred by performing correlation analysis on the obtained network and/or system traces. These approaches rely on pairwise flow analysis, which may exhibit certain limitations in practice. Specifically, multi-hop (i.e., more than three) dependencies, which are common in large-scale transaction systems, can hardly be inferred from pairwise dependency information. This is especially true in the presence of overlapping applications where a single component is shared by multiple applications, and where the accuracy of pairwise analysis decreases, as in the case of multi-hop overlapping applications. Moreover, flow pair correlation is conducted on a per-host basis within a given time interval. Choosing a proper length of this interval is critical in determining the performance and accuracy, but is also prone to false positives.

Accordingly, an automated application dependency discovery system and method is needed for daily system management and operation of enterprise networks and data centers which are experiencing large-scale growth of applications and complicated interactions between service components.

The document: <nplcit id="ncit0001" npl-type="s"><text>XU CHEN MING ZHANG Z MORLEY MAO PARAMVIR BAHL MICROSOFT RESEARCH UNIVERSITY OF MICHIGAN: "Automating Network Application Dependency Discovery: Experiences, Limitations, and New Solutions", USENIX, 14 November 2008 (2008-11-14), pages 1-14</text></nplcit>, relates to experiences, limitations, and new solutions regarding automating network application dependency discovery.

The document:<nplcit id="ncit0002" npl-type="s"><text> PARAMVIR BAHL ET AL: "Towards highly reliable enterprise network services via inference of multi-level dependencies", ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, vol. 37, no. 4, 1 October 2007 (2007-10-01), page 13, ISSN: 0146-4833</text></nplcit>; relates to reliable enterprise network services via inference of multi-level dependencies.

The document <patcit id="pcit0002" dnum="US7590715B1"><text>US 7 590 715 B1</text></patcit> relates to identifying applications based on communicated packets between applications. Characteristics of communicated packets are used to identify the packet as being part of a communication between applications. Identification can be accomplished through the use of packet fingerprints or through a K nearest neighbor algorithm.

The document <patcit id="pcit0003" dnum="US2009070280A1"><text>US 2009/070280 A1</text></patcit> describes a method for performance bottleneck diagnosis and dependency discovery in distributed systems and computer networks includes receiving a real-valued end-to-end measurement matrix, a number of end-to-end measurements, a number of time points, a number of network components, a loss function, and a plurality of constraints on output matrices.

The document:<nplcit id="ncit0003" npl-type="b"><text> LEE D ET AL: "Algorithms for Non-negative Matrix Factorisation", 1 November 2001 (2001-11-01), ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS, MIT PRESS, US, PAGE(S) 556 - 562, ISBN: 978-0-262-56145-7</text></nplcit>; relates to algorithms for non-negative matrix factorization.

Finally, the document <patcit id="pcit0004" dnum="WO2009096970A"><text>WO 2009/096970</text></patcit> describes a computer-executed method for network management which automatically maps applications to network infrastructure. The method comprises monitoring network activity on one or more managed computers and collecting network activity data on the managed computers. The association of executable files to applications is identified and network activity data and the association of executable files to applications are analyzed. Connections from applications on the managed computers are established according to the analysis.

SUMMARY

The invention is defined in independent claims 1 and 9.

A method is disclosed for determining application dependency paths in a data center having a plurality of servers and a plurality of different applications, each of the applications having a plurality of components, one or more of the components being shared with one or more of the other applications. The method comprises the steps of: capturing application traffic volume data on the servers; generating an application traffic matrix of all the components of the applications based on the application traffic volume data; estimating the number of the applications in the data center from the traffic matrix; and decomposing the traffic matrix into a first matrix and a second matrix using the estimated number of applications, the first matrix representing a set of the components belonging to each of the applications and the second matrix representing the amount of traffic generated by each application over time.

In some embodiments, the method further comprises the step of removing noise from the first and second matrices.

Also disclosed is a system for determining application dependency paths in a data center having a plurality of servers and a plurality of different applications, each of the applications having a plurality of components, one or more of the components being shared with one or more of the other applications. The system comprises a data collection component; and a controller in data communication with the data collection component. The data collection component comprises a plurality of switches each having a mirror port for capturing application traffic volume data on the servers; and a monitoring agent for monitoring each of the mirror ports. The controller comprises a connectivity graphing unit for generating an application traffic matrix of all the components of the applications based on the application traffic volume data captured by the monitoring servers; a population estimating unit for estimating the number of the applications in the data center from the traffic matrix generated by the connectivity graphing unit; and an application decomposition unit for decomposing the traffic matrix into a first matrix and a second matrix using the estimated number of applications generated by the population estimating unit, the first matrix representing a set of the components belonging to each of the applications and the second matrix representing the amount of traffic generated by each application over time.

In some embodiments, the controller of the system further comprises a postprocessing unit for removing noise from the first and second matrices.

BRIEF DESCRIPTION OF THE DRAWINGS

<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a block diagram of an exemplary embodiment of a system for determining application dependency paths in a data center, according to the present disclosure.</li><li><figref idref="f0002">FIG. 2</figref> is an exemplary embodiment of a traffic matrix which represents a traffic graph of the present disclosure.</li><li><figref idref="f0003">FIG. 3</figref> is a flowchart of an exemplary embodiment of a data center application dependency discovery method performed by the system of the present disclosure.</li><li><figref idref="f0004">FIG. 4A</figref> is a flowchart of an exemplary embodiment of a Power Factorization process used in the method of <figref idref="f0003">FIG. 3</figref>.</li><li><figref idref="f0005">FIG. 4B</figref> is a flowchart of an exemplary embodiment of a Rank Estimation via Power Factorization Residue Errors process used in the method of <figref idref="f0003">FIG. 3</figref>.</li><li><figref idref="f0006">FIG. 5</figref> is a flowchart of an exemplary embodiment of a dependency decomposition process based on non-negative matrix factorization, which is used in the method of <figref idref="f0003">FIG. 3</figref>.</li><li><figref idref="f0007">FIG. 6</figref> is a graphical depiction of a concurrent volume ratios (CVR) based correlation process used in the method of <figref idref="f0003">FIG. 3</figref>, to correlate application traffic on neighboring links.</li><li><figref idref="f0008">FIG. 7</figref> is a flowchart of an exemplary embodiment of the the CVR correlation process.</li></ul>

DETAILED DESCRIPTION

The present disclosure provides a matrix factorization system and method to extract application dependencies in an enterprise network, a cloud-based data center, and other like data centers, using a temporal global application traffic graph dynamically constructed over time and spatial local traffic observed at each server of the data center. The data center comprises a plurality of servers running a plurality of different applications (e.g. e-commerce, content delivery). Each of the applications has a plurality of components (e.g., web server, application server, database server) in the application's dependency path, where one or more of the components are shared with one or more of the other applications.

Because such data centers typically host a large number of multi-tier applications, the applications requests are overlapped, both in the spatial and temporal domains, making it very difficult for conventional pairwise statistical correlation techniques to correctly extract these interleaved but independent applications. In the system and method of the present disclosure, a matrix-based representation of application traffic is used, which captures both system snapshots and their historical evolution. The system and method decomposesd the matrix representation of application graphs into small subgraphs each representing a single application. This makes the system and method of the present disclosure especially effective in the presence of multi-hop and/or overlapping applications.

The number of applications is usually unknown a priori due to interleaving and overlapping application requests, which further imposes a challenge to discovery of the individual application subgraphs. In the system and method of the present disclosure, the number of applications is determined using low rank matrix estimation either with singular value decompostion or power factorization based solvers, under complete and incomplete traffic data scenarios, with theoretical bound guarantee.

Traffic tapping from switches is limited by the capability of switches as well as the monitoring hosts. A switch typically can mirror only a few ports at the same time. In addition, monitoring data collected over multiple switches, each with multiple ports, may result in high-volume aggregate network traffic and potentially packet loss. Both cases lead to significant loss in the monitoring data. To overcome this problem, the system and method of the present disclosure effectively utilizes historical data to provide sufficient redundancy and employs power factorization based techniques to provide resilience to data loss and estimation errors. The system and method of the present disclosure also uses distributed network monitoring and centralized data processing to determine application dependency paths in a data center.

<figref idref="f0001">FIG. 1</figref> is a block diagram of an exemplary embodiment of the system of the present disclosure. The system comprises a data collection component 100 and a central server or controller 110. The data collection unit 100 has a plurality of switches 102 and a plurality of monitoring agents 104 connected to switches and collecting traffic data from them and the central controller 110 has a preprocessing unit 112, a dependency decomposition unit 114 and a postprocessing unit 116. The preprocessing, dependency decomposition, and postprocessing units 112, 114, 116 of the controller 110 are implemented by one or more processors (not shown) of the controller 110. The processor(s) execute program instructions stored, for example, in one or more memories of the controller 110, which enable the controller 110 to perform preprocessing, dependency decomposition, and postprocessing methods and processes described herein.

The data collection component 100 performs distributed network monitoring of the data center and may comprise top-of-rack (TOR) switches (edge switches), which are located in the lowest layer in the network's tree structure with down links connected to servers of the data center (e.g., 20 to 80 servers) residing in the same rack, and up links connected to an upper-layer aggregation switch. Network traffic is captured at each edge switch 102, which is directly connected to a dedicated monitoring server 104 (monitoring agent) via a mirror port of the edge switch 102. This type of port mirroring is used due to its efficient traffic capturing capabilities with minimal impact on traversing traffic. Periodically, the monitoring server processes the collected data (parses and extracts the flow level information, counts the number of packets for each flow in the current interval), calculates the traffic volume for each application layer link, and forwards the data to the controller 110.

The data received from each monitoring server is centrally processed by the controller 110, which sequentially preprocesses, dependency decomposes, and postprocesses the information received from the monitoring servers.

As stated earlier, once the data from all monitoring agents 104 is received, the preprocessing unit 112 of the controller 110 preprocesses the data. The preprocessing unit 112 first sanitizes the data, for example, aligning measurement intervals on different switches 102, and removing redundancy (for instance, the same packet may be captured twice if the system simultaneously monitors two switch ports where the packet traverses). After data sanitization, the preprocessing unit 112 continuously constructs complete application connectivity graphs for all application groups. Each graph is represented by a traffic matrix <i>X</i>, an example of which is shown in <figref idref="f0002">FIG. 2</figref> and generally denoted by reference numeral 200. Each column of the traffic matrix Xrecords the traffic volumes between all 〈<i>IP: port</i>〉 pairs observed during the corresponding time interval and each row of the traffic matrix <i>X</i> represents the history of traffic volume on the corresponding application link (e.g., link A-B (applicaton component A, application component B)). The traffic matrix <i>X</i> indicates the dynamic connectivity relationships of all application components over both the spatial and temporal domains.

After preprocessing the data, the dependency decomposition unit 114 of the controller 110 performs a dependency decomposition process on the data. The dependency decomposition unit 114 does not assume prior knowledge of the number of applications running in the data center, which is important system information, especially when decomposing system components on a per-application basis. The dependency decomposition unit 114 determines or estimates the number of applications running in the data center with a rank estimation via power factorization or singular value decomposition (SVD) based method. The estimated number of applications is further used in a dependency decomposition algorithm to discover the application dependencies.

The application dependencies discovered by the dependency decomposition unit 114 are postprocessed by the postprocessing unit 116 of the controller 110. Application dependencies generated in the previous components may be affected by measurement noise and contain false positives. Thus, postprocessing is necessary to cross-validate the results and reduce inaccurate inferences. The postprocessing unit 116 of the present disclosure uses a concurrent volume ratio (CVR) based correlation to locally identify correlated edges in the dependency subgraphs using pairwise link correlation on each node of the dependency subgraph. The postprocessing unit 116 also applies rules for fusion and pruning the dependency graphs. These rules leverage domain knowledge of the operator as well as empirical observation of the traffic correlation scores.

<figref idref="f0003">FIG. 3</figref> is a flowchart of an exemplary embodiment of the data center application dependency discovery method performed by the system of the present disclosure. The method commences in block 300 with the capturing of application traffic volume data on the servers in spatial and temporal domains. The traffic volume data is captured by the edge switches 102, which are directly connected to associated monitoring agents 104. The monitoring agent 104 periodically, processes the collected data, calculates the traffic volume for each application layer link, and forwards the data to the controller 110.

Moving to block 320, the preprocessing unit 112 of the controller 110 generates application-layer connectivity graphs. Each graph is represented by an application traffic matrix (traffic matrix <i>X</i>) for all the components of the applications based on the application traffic volume data. The connectivity graph generation mechanism involves identification of service nodes (using a number of incoming connections), aggregation of transient connections into a single edge and identification of client facing nodes based on client IP address distribution. A service node with many different client IP addresses is likely to be a client facing service node (or src node in the connectivity graph). This step also identifies and removes common service nodes of the data center which are used by all applications (e.g., DNS) to split a large complex graph into simpler graphs representing individual application groups.

In block 340, the traffic matrix <i>X</i> is used by the dependency decomposition unit 114 of the controller 110 to estimate the number of the applications in the data center. The dependency decomposition unit 114 of the controller 110 in block 360, decomposes the traffic matrix <i>X</i> into first and second matrices <i>W, H</i> (denoted generally by reference numerals 210 and 220, respectively, in <figref idref="f0002">FIG. 2</figref>) using the number of applications estimated in block 340. The first matrix <i>W</i> represents a set of the components belonging to each of the applications, i.e., the application dependency path, and the second matrix <i>H</i> represents the amount of traffic generated by each application over time. The postprocessing unit 116 of the controller 110, in block 380, removes noise from the first and second matrices <i>W, H.</i>

Referring again to block 340 of <figref idref="f0003">FIG. 3</figref>, the dependency decomposition unit 114 of the controller 110 uses singular vector decompostion (SVD) or Power Factorization based solvers under complete and incompete traffic data scenarios to find the optimal rank of the traffic matrix <i>X</i> by low rank estimation. In the case of complete input data, the number of applications is estimated by solving the rank minimization problem (RMP), via a SVD solver. The RMP minimizes ∥<i>X</i> - <i>X̃</i>∥, where <maths id="math0001" num=""><math display="inline"><mrow><mover><mi>X</mi><mrow><mo>˜</mo></mrow></mover><mo>=</mo><mi>U</mi><mrow><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></msubsup></mrow><mrow><mrow><mrow><msup><mi>V</mi><mi>T</mi></msup></mrow></mrow></mrow><mo>,</mo><mi>U</mi></mrow></math><img file="EP2567316B1_D0001.tif" /></maths> is a n×n unitary matrix (i.e., <i>U^TU</i> = <i>I</i>), <i>V</i> is a m × m unitary matrix (i.e., <i>V^TV</i> = <i>I</i>) and the matrix <maths id="math0002" num=""><math display="inline"><mrow><mrow><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></msubsup></mrow></mrow></math><img file="EP2567316B1_D0002.tif" /></maths> is n×m a diagonal matrix with the largest k singular values δ<i>_i</i> from Σ, which is a n×m diagonal matrix. The best rank <i>r</i> approximation of traffic matrix <i>X</i> is <i>k</i> if ∥<i>X - X̃</i>∥ ≤ ε, ε is the tolerance for noise. In the case of incomplete input data, because the traffic matrix X may be missing some items, Power Factorization is a numerically robust solver to compute two matrix factors <i>A</i> and <i>B</i> with dimensions <i>n*r</i> and <i>r</i>*<i>m</i> respectively, such that matix distance ∥<i>M ·</i> (<i>X - AB</i>)∥ is minimized (where <i>M</i> is a mask matrix of binary entries, <i>Mij</i> equals 0 if <i>X_ij</i> is missing, otherwise, <i>M_ij</i> is 1). Given <i>r &lt; min</i>(<i>m,n</i>)<i>,</i> the method may use the Power Factorization process depicted in the flow chart of <figref idref="f0004">FIG. 4A</figref> to compute the best rank <i>r</i> approximation of <i>X,</i> given <i>r</i> known.

In <figref idref="f0004">FIG. 4A</figref>, the traffic matrix <i>X,</i> its mask matrix <i>M,</i> and rank <i>r</i> are inputs 401 for the Power Factorization process. In block 402, the Power Factorization process commences with a random matrix <i>A</i>₀ having a size <i>n*r</i> and set k-th interation k equal to 0. In block 403, k-th interation k is set equal to k+1. In block 404, given matrix <i>A_k-1</i>, an <i>r*m</i> sized matrix <i>B_k</i> is computed so that matrix distance ∥<i>M·</i> (<i>X - A</i>_<i>k</i>-1<i>B_k</i>)∥ is minimized. Then, matrix <i>B_k</i> is normalized. In block 405, given matrix <i>B_k,</i> a <i>n*r</i> sized matrix <i>A_k</i> is computed so that matrix distance ∥<i>M ·</i> (<i>X - A_kB_k</i>)∥ is minimized. In block 406, a determination is made as to whether matrices <i>A_k</i> and <i>B_k</i> have converged. If matrices <i>A_k</i> and <i>B_k</i> converge, then matrices <i>A_k</i> and <i>B_k</i> are generated at output 407. If matrices <i>A_k</i> and <i>B_k</i> have not converged, blocks 403, 404, 405, and 406 of the process are repeated at flow line 408 until matrices <i>A_k, B_k</i> converge.

The Power Factorization process can not directly predict the rank information of traffic matrix <i>X_n*m</i> (where <i>n</i> and <i>m</i> are the row and column dimensions of matrix <i>X</i>) where rank <i>r</i> must be known before optimizing matrices <i>A_n*r</i> and <i>B_r*m</i>. However, searching rank <i>r</i> within a reasonable range and plotting the final approximation errors for matrix distance (∥<i>M ·</i> (<i>X - AB)</i>∥) against rank <i>r</i>, may be a strong heuristics indicating the true rank <i>r̂</i> (or the rank of matrix <i>X</i>) where the error curve has a saddle point. Note that with rank <i>r</i> increasing, the error for matrix distance ∥<i>M ·</i> (<i>X - AB)</i>∥ is monotonically decreasing though not too much smaller after passing the true rank <i>r̂</i>. If <i>A_r</i> and <i>B_r</i> denote the two matrix factors given any rank <i>r</i>, then error ε<i>_r</i> denotes the corresponding fitting error for rank r approximation. The present disclosure provides a process depicted in the flow chart of <figref idref="f0005">FIG. 4B</figref>, which summarizes a method for estimating the rank of the incomplete matrix <i>X</i> via Power Factorization residue error analysis. A Power Factorization solver is used in each iteration until convergence. This Power Factorization method is applicable for both a complete matrix <i>X,</i> or a matrix <i>X</i> with missing values.

In <figref idref="f0005">FIG. 4B</figref>, the traffic matrix <i>X</i>, its mask matrix <i>M</i>, and threshold ε (the threshold of converge criteria for fitting error difference), are inputs 400 for the Rank Estimation via Power Factorization Residue Errors (REPFRE) process. The REPFRE process commences in block 410 by setting rank <i>r</i> equal to 1, setting <i>A_n*r, B_r*m</i> equal to the Power Factorization process PF of <figref idref="f0004">FIG. 4A</figref>, and computing fitting error ε<i>_r</i> for rank <i>r</i> as ∥<i>M</i>(<i>X-A_n*rB_r*m</i>)∥<i>.</i> In block 420, rank <i>r</i> is set equal to <i>r</i>+1. In block 430, <i>A_n*r, B_r*m</i> is set equal to the Power Factorization process PF of <figref idref="f0004">FIG. 4A</figref>, the fitting error ε<i>_r</i> for rank <i>r</i> (<i>r</i>+1) is computed as ∥<i>M</i>(<i>X-A_n*rB_r*m</i>)∥ and the error difference <i>d</i> is computed as <i>d̃</i>_{(<i>i</i>-1,<i>i</i>)} = ε_<i>r</i>-1 - ε_r. In block 440, a determination is made as whether difference <i>d</i> is less than threshold ε. If difference d is less than threshold ε, then the estimated rank of matrix <i>X</i> is set as rank <i>r</i> at output 450, where rank <i>r</i> is the number of applications. If difference d is not less than threshold ε, then blocks 420, 430 and 440 of the REPFRE process are repeated at flow line 460.

Referring again to block 360 of <figref idref="f0003">FIG. 3</figref>, the dependency decomposition unit 114 of the controller 110 may use non-negative matrix factorization (NMF) to discover the dependent application services (features) over the high dimensional traffic data. NMF is an unsupervised learning algorithm for matrix factorization under the non-negativity constraints which are applicable for the non-negative additive nature of application pattern combinations. Given a non-negative <i>n*m</i> matrix <i>X</i>, NMF finds the non-negative <i>n</i>*<i>r</i> matrix <i>W</i> and non-negative <i>r</i>*<i>m</i> matrix <i>H</i> such that: <maths id="math0003" num=""><math display="block"><mrow><msub><mi>X</mi><mrow><mi>n</mi><mo>*</mo><mi>m</mi></mrow></msub><mo>≈</mo><msub><mi>W</mi><mrow><mi>n</mi><mo>*</mo><mi>r</mi></mrow></msub><mo>⋅</mo><msub><mi>H</mi><mrow><mi>r</mi><mo>*</mo><mi>m</mi></mrow></msub><mn>.</mn></mrow></math><img file="EP2567316B1_D0003.tif" /></maths> Because matrix represents the traffic measured over time, each column vector in matrix <i>W</i> can be used to interpret an application dependency subgraph where traffic volumes on different links <i>W</i>_{<i>i</i><sub2>1</sub2><i>*j</i>} and W_{<i>i</i><sub2>2</sub2>*<i>j</i>} keep some linear correlations. Each column vector in matrix <i>H</i> indicates the weights of range <i>r</i> applications for different request workloads at each time snapshot.

In one embodiment, the following multiplicative update rules are selected to minimize objective function ∥<i>X</i> - <i>WH</i>∥² to obtain matrices <i>W</i> and <i>H</i> : <maths id="math0004" num=""><math display="block"><mrow><msub><mi>W</mi><mrow><mi>i</mi><mo>⁢</mo><mi>α</mi></mrow></msub><mo>←</mo><msub><mi>W</mi><mrow><mi>i</mi><mo>⁢</mo><mi>α</mi></mrow></msub><mo>⁢</mo><mfrac><mrow><msub><mfenced><msup><mrow><mi>X</mi><mo>⁢</mo><mi>H</mi></mrow><mi>T</mi></msup></mfenced><mrow><mi>i</mi><mo>⁢</mo><mi>α</mi></mrow></msub></mrow><mrow><msub><mfenced><msup><mrow><mi mathvariant="italic">WH</mi><mo>⁢</mo><mi>H</mi></mrow><mi>T</mi></msup></mfenced><mrow><mi>i</mi><mo>⁢</mo><mi>α</mi></mrow></msub></mrow></mfrac></mrow></math><img file="EP2567316B1_D0004.tif" /></maths><maths id="math0005" num=""><math display="block"><mrow><msub><mi>W</mi><mrow><mrow><mi>α</mi><mo>⁢</mo><mi>μ</mi></mrow></mrow></msub><mo>←</mo><msub><mi>H</mi><mrow><mrow><mi>α</mi><mo>⁢</mo><mi>μ</mi></mrow></mrow></msub><mo>⁢</mo><mfrac><mrow><msub><mfenced separators=""><msup><mi>W</mi><mi>T</mi></msup><mo>⁢</mo><mi>X</mi></mfenced><mrow><mrow><mi>α</mi><mo>⁢</mo><mi>μ</mi></mrow></mrow></msub></mrow><mrow><msub><mfenced separators=""><msup><mi>W</mi><mi>T</mi></msup><mo>⁢</mo><mi>W</mi><mo>⁢</mo><mi>H</mi></mfenced><mrow><mrow><mi>α</mi><mo>⁢</mo><mi>μ</mi></mrow></mrow></msub></mrow></mfrac><mn>.</mn></mrow></math><img file="EP2567316B1_D0005.tif" /></maths> These update rules are straightforward to implement and employ alternatively as solving a bilinear problem: fixing matrix <i>H</i> to optimize matrix <i>M</i> and then fixing matrix <i>M</i> to solve matrix <i>H</i> in each optimization loop. They converge faster compared to regular gradient descend methods. The initialization of matrix <i>H</i> at first iteration can be chosen randomly. The other important property of NMF is its spatial locality or sparseness of factorized bases, which is particularly applicable to application level event discovery, composed of localized link observations.

The reasoning behind the application of NMF in application dependency decomposition is threefold. First, the observed traffic matrix <i>X</i> is non-negative which naturally matches with the constraints on input data for NMF. Second, NMF does not allow negative entries in both matrix factors <i>W</i> and <i>H.</i> It means only additive combinations of the basis components are allowed, which is consistent with our assumption that the traffic measurement (non-negative by nature) on each link is the summation of the workloads caused by multiple application events. Third, NMF is also a global-scaled graph decomposition method which can discover or extract the latent, statistical dependency traffic patterns as subgraphs, for possible semantic interpretation. Comparing with other matrix factorization techniques, such as PCA and Independent Component Analysis, NMF produces more semantically meaningful results given our traffic data due to the non-negative constraints.

<figref idref="f0006">FIG. 5</figref> is a flowchart of an exemplary embodiment of the NMF-based dependency decomposition process performed by the dependency decomposition unit 114 of the controller 110. The traffic matrix <i>X</i>, its mask matrix <i>M,</i> rank <i>r</i> and threshold δ are inputs 500 for the NMF-based dependency decomposition process. In block 510, the NMF-based dependency decomposition process commences with randomly generating an <i>n*r</i> matrix <i>W</i> and an <i>r</i>*<i>m</i> matrix <i>H.</i> In block 520, matrix <i>W</i> is computed as <i>W</i>(<i>XH^T</i>)/(<i>WHH^T</i>)<i>.</i> In block 530, matrix <i>H</i> is computed as <i>H(W^TX)</i>/<i>(W^TWH).</i> In block 540, a determination is made as to whether matrix distance ∥<i>X-WH</i>∥ is less than threshold δ. If matrix distance ∥<i>X-WH</i>∥ is less than threshold δ, then matrices <i>W, H</i> are generated at output 550. If ∥<i>X-WH</i>∥ is not less than threshold δ, then blocks 520, 530, and 540 of the process are repeated at flow line 560 until ∥<i>X-WH</i>∥ is less than threshold δ.

Referring again to block 380 of <figref idref="f0003">FIG. 3</figref>, the postprocessing unit 116 of the controller 110 may use a concurrent volume ratios (CVR) based correlation technique to correlate application traffic on neighboring links, especially for cases where multiple input or output connections are present, as shown for example in <figref idref="f0007">FIG. 6</figref>. This process validates the result of the dependency decomposition process and eliminates noise.

In CVR correlation process, vector <i>v_i</i> represents the aggregated traffic volume on application component link <i>L_i</i> over any certain time interval <i>T</i>. Then, the CVR correlation process on two consecutive application component links <i>L_i</i> and <i>L_j</i> are measured with: <maths id="math0006" num=""><math display="block"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>c</mi></msubsup><mo>=</mo><mfrac><mrow><mo>∑</mo><msub><mi>v</mi><mi>j</mi></msub><mo>*</mo><msub><mi>l</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow></msub></mrow><mrow><mo>∑</mo><msub><mi>v</mi><mi>j</mi></msub></mrow></mfrac><mspace width="1em" /><mi>and</mi><mspace width="1em" /><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>e</mi></msubsup><mo>=</mo><mfrac><mrow><mo>∑</mo><msub><mi>v</mi><mi>i</mi></msub><mo>*</mo><msub><mi>l</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow></msub></mrow><mrow><mo>∑</mo><msub><mi>v</mi><mi>i</mi></msub></mrow></mfrac><mo>,</mo></mrow></math><img file="EP2567316B1_D0006.tif" /></maths> where <i>l_ij</i> is 0/1 vector indicating the concurrency of vectors <i>v_i</i> and <i>v_j</i> in synchronized time intervals. Specifically, 0/1 vector <maths id="math0007" num=""><math display="inline"><mrow><msubsup><mi>l</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>t</mi></msubsup></mrow></math><img file="EP2567316B1_D0007.tif" /></maths> is set to 1 when both links <i>L_i</i> and <i>L_j</i> have traffic going through in time interval <i>t</i> and to 0 otherwise. We use CVR scores <maths id="math0008" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>c</mi></msubsup></mrow></math><img file="EP2567316B1_D0008.tif" /></maths> and <maths id="math0009" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>e</mi></msubsup></mrow></math><img file="EP2567316B1_D0009.tif" /></maths> (where superscript c represents the proportion <i>L_j</i> caused by <i>L_i</i> and superscript e represents the proportion of <i>L_i</i> resulting in <i>L_j</i>; i.e., to indicate causal relation between application component links) to roughly estimate the causal correlation of the traffic on links <i>L_i</i> and <i>L_j</i>. Intuitively, CVR score <maths id="math0010" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>c</mi></msubsup></mrow></math><img file="EP2567316B1_D0010.tif" /></maths> represents the ratio of the traffic volume on link <i>L_j</i> caused by link <i>L_i</i> over the total traffic volume on link <i>L_j</i>, and CVR score <maths id="math0011" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>e</mi></msubsup></mrow></math><img file="EP2567316B1_D0011.tif" /></maths> calculates the ratio of the traffic volume on link <i>L_i</i> that will result in events on link <i>L_j</i> over the total of the traffic volume on link <i>L_i</i>.

Referring again to <figref idref="f0007">FIG. 6</figref>, a high CVR score between application component links <i>A - B</i> and <i>B - C,</i> indicates causal relationship, i.e., <i>A - B - C</i> is a dependency path. Likewise, a low CVR score between <i>A - B</i> and <i>B - D,</i> indicates <i>A - B</i> and <i>B - D</i> are independent links. This leads to a splitting of the connectivity graph into two connected components (or applications) <i>A - B - C</i> and <i>B - D.</i> Furthermore, the CVR score is calculated by evaluating <maths id="math0012" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>c</mi></msubsup></mrow></math><img file="EP2567316B1_D0012.tif" /></maths> and <maths id="math0013" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>e</mi></msubsup></mrow></math><img file="EP2567316B1_D0013.tif" /></maths> for different time intervals <i>T</i>, e.g., 300 ms, 500 ms, 1 sec, 10 sec, ... Note that for dependent application links, the CVR score is stable over different time intervals, while for independent links, there is a sudden decrease in CVR score at a particular time interval. This is because at very small time interval even a high request rate does not cause aggregated traffic volumes to give high CVR scores.

In one exemplary embodiment, the the post processing rules may be as follows. For a single input/output, if CVR scores <maths id="math0014" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>c</mi></msubsup></mrow></math><img file="EP2567316B1_D0014.tif" /></maths> and <maths id="math0015" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>e</mi></msubsup></mrow></math><img file="EP2567316B1_D0015.tif" /></maths> are high in all time intervals, application component links <i>L_i, L_j</i> are dependent pair. For multiple input with multiple outputs, calculate CVR scores <maths id="math0016" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>c</mi></msubsup></mrow></math><img file="EP2567316B1_D0016.tif" /></maths> and <maths id="math0017" num=""><math display="inline"><mrow><msubsup><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow><mi>e</mi></msubsup></mrow></math><img file="EP2567316B1_D0017.tif" /></maths> for all links <i>i</i> and <i>j</i>, and measure their stability across different time intervals 30 sec, 10 sec, 1 sec, 500 ms. Based on this, dependent and independent links are identified. Like other pair wise correlation techniques, CVR is not suitable to identify the whole dependency path in multi-tier networks. Instead, it is useful to validate the output of decomposition stage (NMF) and filter out false positives. On the other hand, even though it is possible to use CVR to identify local pairwise dependency relationship, and then link or stitch pairs to form a higher-order application-level dependency subgraph, this process may be error-prone since all local pairs are required to be identified and grouped correctly, which is not trivial. The strategy of using a global data matrix representation, and top-down application-level decomposition followed by local CVR based validation can achieve a better balance of statistical robustness and accuracy.

<figref idref="f0008">FIG. 7</figref> is a flowchart of the CVR correlation process performed by the postprocessing unit 116 of the controller 110. The potential list of applications derived from matrix <i>W</i> at the output of the dependency decomposition unit 114 of the controller 110 are inputs 700 for CVR correlation process. In block 710, all the application component links and time series for each link are extracted from matrix <i>X</i> for each potential application. In block 720, traffic time series are calculated for different time intervals for each link pair (<i>i</i>, <i>j</i>) having a common vertex. In block 730, CVR score <maths id="math0018" num=""><math display="inline"><mrow><msup><mrow><msub><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow></msub></mrow><mi>c</mi></msup></mrow></math><img file="EP2567316B1_D0018.tif" /></maths> is computed as sum(<i>v_j</i>*<i>l_ij</i>)/sum(<i>v_j</i>). In block 740, CVR score <maths id="math0019" num=""><math display="inline"><mrow><msup><mrow><msub><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow></msub></mrow><mi>e</mi></msup></mrow></math><img file="EP2567316B1_D0019.tif" /></maths> is computed as sum(<i>v_j</i>*<i>l_ij</i>)/sum(<i>v_i</i>). In block 750, CVR scores <maths id="math0020" num=""><math display="inline"><mrow><msup><mrow><msub><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow></msub></mrow><mi>c</mi></msup></mrow></math><img file="EP2567316B1_D0020.tif" /></maths> and <maths id="math0021" num=""><math display="inline"><mrow><msup><mrow><msub><mi>V</mi><mrow><mi>i</mi><mo>⁢</mo><mi>j</mi></mrow></msub></mrow><mi>e</mi></msup></mrow></math><img file="EP2567316B1_D0021.tif" /></maths> are ploted against time interval on an x-axis, for evaluated link pairs. In block 760, a determination is made as to whether the CVR scores are stable between link (<i>i, j</i>). If the CVR scores are stable between link <i>i, j,</i> an indication that link <i>i, j</i> are dependent edges is generated at output 770. This output at 770 is used in the postprocessing 116 before finally giving the individual applications as the output of the overall process (output at 380).

While exemplary drawings and specific embodiments of the present disclosure have been described and illustrated, it is to be understood that that the scope of the invention as set forth in the claims is not to be limited to the particular embodiments discussed. Thus, the embodiments shall be regarded as illustrative rather than restrictive, and it should be understood that variations may be made in those embodiments by persons skilled in the art without departing from the scope of the invention as set forth in the claims that follow.