Automatic Discovery Of Service/Host Dependencies In Computer Networks

• US 20080267083A1
• Filed: 04/24/2007
• Published: 10/30/2008
• Est. Priority Date: 04/24/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goldszmidt, Moises, MacCormick, John, Barham, Paul
• Granted Patent: US 7,821,947 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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 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 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 the 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 the 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 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 computer-readable medium with computer-executable instructions stored thereon for performing the method of:

generating packet data by observing packets sent and received through an input 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 the 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 computer-readable medium 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 the elapsed time between receipt of the packet and a subsequent packet sent on the output channel.

10. The computer-readable medium of claim 8, wherein the model of inter-arrival time comprises a histogram.

11. The computer-readable medium of claim 8, wherein the model of predecessor waiting time comprises a histogram.

12. The computer-readable medium of claim 8, wherein the threshold is 99%.

13. The computer-readable medium 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 computer-readable medium 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 on input and output channel, adapted to:

generate packet data by observing packets sent and received through the input and the output channel 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 the 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 the 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.