Systems and methods for application dependency discovery

1. A method for discovering a set of applications that run on a network, the method comprising:

determining aggregate traffic volumes for pairs of nodes on the network over a plurality of time intervals;

building a traffic matrix denoting each of the pairs of nodes and denoting respective aggregate traffic volume histories of each of the pairs of nodes that are based on the determined traffic volumes, wherein the traffic matrix is formulated as a combination of bases vectors that model the set of applications;

determining, by a processor, the bases vectors by applying a covariance matrix adaptation evolutionary strategy (CMA-ES) based on the traffic matrix; and

outputting an indication of the set of applications that is based on the bases vectors, wherein the determining the bases vectors further comprises determining a number of the bases vectors that include disconnected components, and

wherein the determining the bases vectors further comprises imposing a discontinuity penalty in an objective function optimized by the CMA-ES and weighting the discontinuity penalty with the number of the bases vectors that include disconnected components.

2. The method of claim 1 , wherein the determining the number of the bases vectors that include disconnected components further comprises determining a connectivity graph for each of the bases vectors.

3. The method of claim 2 , wherein the determining the connectivity graph for each of the bases vectors further comprises computing a Laplacian matrix for each of the bases vectors and wherein the number of the bases vectors that include disconnected components is computed as a sum of the bases vectors that have a respective Laplacian matrix with a rank that is less than the size of the respective bases vector minus one.

4. The method of claim 1 , wherein the outputting further comprises outputting, for each of the applications, an indication of which of the nodes in the pairs of nodes compose the application.

5. The method of claim 4 , wherein the outputting further comprises outputting, for each of the applications, an indication of links between the nodes that compose the application.

6. The method of claim 1 , further comprising determining a total number of applications (r) in the set of applications, wherein the determining the bases vectors is based on the determined total number of applications in the set of applications.

7. The method of claim 6 , wherein the bases vectors are formulated as a bases matrix and wherein the method further comprises initializing the bases matrix by selecting r columns or rows of the traffic matrix and concatenating the columns or rows as a multivariate random variable for the CMA-ES.

8. A non-transitory computer readable storage medium comprising a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

determine aggregate traffic volumes between pairs of nodes on a network over a plurality of time intervals;

build a traffic matrix denoting each of the pairs of nodes and denoting respective aggregate traffic volume histories of each of the pairs of nodes that are based on the determined traffic volumes, wherein the traffic matrix is formulated as a combination of bases vectors that model the set of applications;

determine the bases vectors by applying a covariance matrix adaptation evolutionary strategy (CMA-ES) based on the traffic matrix; and

output an indication of a set of applications that run on the network that is based on the bases vectors,

wherein the determining the bases vectors further comprises determining a number of the bases vectors that include disconnected components, and

wherein the determining the bases vectors further comprises imposing a discontinuity penalty in an objective function optimized by the CMA-ES and weighting the discontinuity penalty with the number of the bases vectors that include disconnected components.

9. The non-transitory computer readable storage medium of claim 8 , wherein the computer readable program when executed on a computer causes the computer to output, for each of the applications, an indication of which of the nodes in the pairs of nodes compose the application.

10. A system for discovering a set of applications that run on a network comprising:

a controller, implemented by a processor, configured to determine aggregate traffic volumes between pairs of nodes on the network over a plurality of time intervals and to build a traffic matrix denoting each of the pairs of nodes and denoting respective aggregate traffic volume histories of each of the pairs of nodes that are based on the determined traffic volumes, wherein the traffic matrix is formulated as a combination of bases vectors that model the set of applications; and

at least one estimation module configured to determine the bases vectors by applying a covariance matrix adaptation evolutionary strategy (CMA-ES) based on the traffic matrix,

wherein the controller is further configured to output an indication of the set of applications that is based on the bases vectors,

wherein the at least one estimation module further includes an application population estimation module that is configured to determine a number of the bases vectors that include disconnected components, and

wherein the at least one estimation module further includes an application decomposition module that is configured to impose a discontinuity penalty in an objective function optimized by the CMA-ES and weight the discontinuity penalty with the number of the bases vectors that include disconnected components.

11. The system of claim 10 , wherein the application population estimation module is configured to determine the number of the bases vectors that include disconnected components by determining a connectivity graph for each of the bases vectors.

12. The system of claim 11 , wherein the application population estimation module is configured to determine the connectivity graph for each of the bases vectors by computing a Laplacian matrix for each of the bases vectors and to compute the number of the bases vectors that include disconnected components as a sum of the bases vectors that have a respective Laplacian matrix with a rank that is less than the size of the respective bases vector minus one.

13. The system of claim 10 , wherein the controller is further configured to output, for each of the applications, an indication of which of the nodes in the pairs of nodes compose the application.

14. The system of claim 13 , wherein the controller is further configured to output, for each of the applications, an indication of links between the nodes that compose the application.

15. The system of claim 10 , wherein the at least one estimation module includes a first module that is configured to determine a total number of applications (r) in the set of applications and wherein the at least one estimation module further comprises a second module that is configured to determine the bases vectors based on the determined total number of applications in the set of applications.

16. The system of claim 15 , wherein the second module is further configured to formulate the bases vectors as a bases matrix and wherein the controller is further configured to initialize the bases matrix by selecting r columns or rows of the traffic matrix and concatenating the columns or rows as a multivariate random variable for the CMA-ES.