Automatic discovery of service/host dependencies in computer networks

• US 7,821,947 B2
• Filed: 04/24/2007
• Issued: 10/26/2010
• Est. Priority Date: 04/24/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: MacCormick, John, Goldszmidt, Moises, Barham, Paul
• Primary Examiner(s): Juntima; Nittaya
• Application Number:
  US11/739,312
• Publication Number:
  US 20080267083A1
• Time in Patent Office: 1,281 Days
• Field of Search: 370/252, 370/241, 370/242, 709/223, 709/224
• US Class Current: 370/241
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

An activity model is generated at a computer. The activity model may be generated by monitoring incoming and outgoing channels for packets for a predetermined window of time. To generate an activity model, an input and an output channel are selected. A probability distribution function describing the observed waiting time between packet arrivals on the selected input channel and the selected output channel is generated by mining the data collected during the selected window of time. A probability distribution function describing the observed waiting time between a randomly chosen instant and receiving a packet on the selected input channel is also generated. The distance between the two generated probability distribution functions is computed. If the computed distance is greater than a predefined confidence level, then the two selected channels are deemed to be related. Otherwise, the selected channels are deemed to be unrelated. The activity model is further generated by comparing each input and output channel pair entering or leaving a particular computer.

Claims

1. A method for detecting correlation between an input channel and an output channel, comprising:

generating packet data by observing packets sent and received through the input and output channels for a window of time;

generating, by a processor, a model of inter-arrival time of packets received on the input channel and packets sent on the output channel;

generating, by the processor, a model of predecessor waiting time for packets received on the input channel;

determining a difference between the model of inter-arrival time and the model of predecessor waiting time; and

determining that the input and output channels are correlated if the difference is greater than a threshold.

2. The method of claim 1, wherein the model of inter-arrival time is generated by mining the packet data for arrival times of packets received on the input channel, and for each packet received, identifying an elapsed time between receipt of the packet and a subsequent packet sent on the output channel.

3. The method of claim 1, wherein the model of inter-arrival time comprises a histogram.

4. The method of claim 1, wherein the model of predecessor waiting time comprises a histogram.

5. The method of claim 1, wherein the threshold is 99%.

6. The method of claim 1, wherein the difference between the model of inter-arrival time and the model of predecessor waiting time is calculated using the Kolmogorov-Smirnov test.

7. The method of claim 1, wherein generating, by the processor, a model of predecessor waiting time for packets received on the input channel comprises generating a model of inter-arrival times of packets received on the input channel, and converting the model of inter-arrival times to the model of predecessor waiting time.

8. A tangible computer-readable storage medium, excluding transmission media and carrier waves, with computer-executable instructions stored thereon that when executed by a processor perform a method comprising:

generating packet data by observing packets sent and received through an input channel and an output channel for a window of time;

generating a model of inter-arrival time of packets received on the input channel and packets sent on the output channel;

generating a model of predecessor waiting time for packets received on the input channel;

determining a difference between the model of inter-arrival time and the model of predecessor waiting time; and

determining that the input and output channels are correlated if the difference is greater than a threshold.

9. The tangible computer-readable storage medium, excluding transmission media and carrier waves, of claim 8, wherein the model of inter-arrival time is generated by mining the packet data for arrival times of packets received on the input channel, and for each packet received, identifying an elapsed time between receipt of the packet and a subsequent packet sent on the output channel.

10. The tangible computer-readable storage medium, excluding transmission media and carrier waves, of claim 8, wherein the model of inter-arrival time comprises a histogram.

11. The tangible computer-readable storage medium, excluding transmission media and carrier waves, of claim 8, wherein the model of predecessor waiting time comprises a histogram.

12. The tangible computer-readable storage medium, excluding transmission media and carrier waves, of claim 8, wherein the threshold is 99%.

13. The tangible computer-readable storage medium, excluding transmission media and carrier waves, of claim 8, wherein the difference between the model of inter-arrival time and the model of predecessor waiting time is calculated using the Kolmogorov-Smirnov test.

14. The tangible computer-readable storage medium, excluding transmission media and carrier waves, of claim 8, wherein generating a model of predecessor waiting time for packets received on the input channel comprises generating a model of inter-arrival times of packets received on the input channel, and converting the model of inter-arrival times to the model of predecessor waiting time.

15. A computer system comprising a processor and at least one input and one output channels, configured to:

generate packet data by observing packets sent and received through the input and the output channels for a window of time;

generate a model of inter-arrival time of packets received on the input channel and packets sent on the output channel;

generate a model of predecessor waiting time for packets received on the input channel;

determine a difference between the model of inter-arrival time and the model of predecessor waiting time; and

determine that the input and output channels are correlated if the difference is greater than a threshold.

16. The computer system of claim 15, wherein the model of inter-arrival time is generated by mining the packet data for arrival times of packets received on the input channel, and for each packet received, identifying an elapsed time between receipt of the packet and a subsequent packet sent on the output channel.

17. The computer system of claim 15, wherein the model of inter-arrival time comprises a histogram.

18. The computer system of claim 15, wherein the threshold is 99%.

19. The computer system of claim 15, wherein the difference between the model of inter-arrival time and the model of predecessor waiting time is calculated using the Kolmogorov-Smirnov test.

20. The computer system of claim 15, wherein generating a model of predecessor waiting time for packets received on the input channel comprises generating a model of inter-arrival times of packets received on the input channel, and converting the model of inter-arrival times to the model of predecessor waiting time.