Mapping network service dependencies

• US 9,628,553 B2
• Filed: 10/24/2014
• Issued: 04/18/2017
• Est. Priority Date: 10/24/2014
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: El Defrawy, Karim, Sylla, Pape Maguette
• Primary Examiner(s): BUI, JONATHAN A
• Application Number:
  US14/523,473
• Publication Number:
  US 20160119213A1
• Time in Patent Office: 907 Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A method and apparatus for discovering service dependencies. A plurality of connections is identified between nodes in a data network. A set of connection pairs is identified based on the plurality of connections identified. A set of time series is created for the set of connection pairs using monitoring data received from a plurality of sensors monitoring the data network. Service dependencies may be discovered using the set of time series.

Claims

1. A method for discovering service dependencies, the method comprising:

identifying a plurality of connections between nodes in a data network;

identifying a set of connection pairs based on the plurality of connections identified;

creating a set of time series for the set of connection pairs using monitoring data received from a plurality of sensors monitoring the data network, wherein the time series comprises a plurality of pairs of data transfer values; and

discovering the service dependencies using the set of time series;

wherein discovering the service dependencies comprises identifying a set of final time series for a set of service pairs using the set of time series, each service pair comprising two services having a connection duration;

wherein the set of final time series is formed for the set of service pairs by combining time series for connection pairs having a same service-service connection;

wherein discovering the service dependencies comprises computing a transfer entropy for a service pair from the set of service pairs using a corresponding one of the set of final time series; and

wherein discovering the service dependencies further comprises identifying a service dependency between a first service in the service pair and a second service in the service pair when the transfer entropy is greater than a selected threshold.

2. The method of claim 1, wherein identifying the set of connection pairs comprises:

determining whether a first connection duration of a first connection in the plurality of connections at least partially overlaps with a second connection duration of a second connection in the plurality of connections; and

establishing the first connection and the second connection as a connection pair in the set of connection pairs in response to a determination that the first connection duration at least partially overlaps the second connection duration.

3. The method of claim 2 further comprising:

generating first data transfer information for the first connection and second data transfer information for the second connection using the monitoring data, wherein the first data transfer information and the second data transfer information are used to create a pair of data transfer values for the connection pair.

4. The method of claim 3, wherein creating the set of time series comprises:

creating a plurality of time buckets for the connection pair; and

identifying a plurality of pairs of data transfer values for the connection pair in which at least a portion of the plurality of pairs of data transfer values correspond to the plurality of time buckets.

5. The method of claim 1, wherein identifying the set of final time series for the set of service pairs comprises:

combining time series from the set of time series for any of the set of connection pairs having a same type of second connection between a same initiating node and a same servicing node to form a final time series, wherein the same initiating node and the same servicing node form a service pair corresponding to the final time series.

6. The method of claim 1, wherein identifying the service dependency comprises:

determining whether the transfer entropy is greater than the selected threshold; and

identifying the service pair as the service dependency in response to a determination that the transfer entropy is greater than the selected threshold.

7. The method of claim 1 further comprising:

identifying service dependency clusters based on the service dependencies discovered, wherein a service dependency cluster comprises at least two service pairs, each of the at least two service pairs having a same service.

8. The method of claim 1 further comprising:

filtering the set of service pairs based on a set of criteria to form a final set of service pairs.

9. The method of claim 8 further comprising:

computing a transfer entropy for each of the final set of service pairs using the set of final time series.

10. The method of claim 9, wherein discovering the service dependencies comprises:

discovering the service dependencies in the data network based on the transfer entropy computed for the each of the final set of service pairs.

11. The method of claim 1, wherein identifying the plurality of connections comprises:

monitoring a flow of data over the data network using the plurality of sensors to generate monitoring data; and

identifying a plurality of fully established connections between the nodes using the monitoring data, wherein each of the plurality of fully established connections comprises one of a client-service connection and a service-service connection.

12. The method of claim 1 further comprising:

identifying service dependency clusters based on the service dependencies discovered, wherein a service dependency cluster comprises at least two service pairs, each of the at least two service pairs having a connection duration overlap.

13. An apparatus comprising:

a connection manager that identifies a plurality of connections between nodes in a data network and that identifies a set of connection pairs based on the plurality of connections identified;

a time series builder that creates a set of time series for the set of connection pairs wherein the time series comprises a plurality of pairs of data transfer values; and

a dependency evaluator that discovers service dependencies in the data network using the set of time series, wherein the dependency evaluator computes a transfer entropy for each of a final set of service pairs using the set of time series and identifies a service pair in the final set of service pairs as a service dependency when the transfer entropy computed for the service pair is greater than a selected threshold.

14. The apparatus of claim 13 further comprising:

a plurality of sensors associated with the nodes that provide monitoring data, wherein the monitoring data is used to create the set of time series.

15. The apparatus of claim 13, wherein each of the plurality of connections is one of a client-service connection and a service-service connection.

16. The apparatus of claim 13, wherein the dependency evaluator identifies service dependency clusters based on the service dependencies discovered.

17. A network manager comprising:

a connection manager that identifies a plurality of connections between nodes in a data network and that identifies a set of connection pairs based on the plurality of connections identified, wherein the nodes include a plurality of clients and a plurality of services;

a time series builder that creates a set of time series for the set of connection pairs using monitoring data received from a plurality of sensors monitoring the data network, wherein the time series comprises a plurality of pairs of data transfer values; and

a dependency evaluator that discovers service dependencies between the plurality of services in the data network using the set of time series, wherein the dependency evaluator computes a transfer entropy for each of a final set of service pairs using the set of time series and identifies a service pair in the final set of service pairs as a service dependency when the transfer entropy computed for the service pair is greater than a selected threshold.