Signature matching methods and apparatus for performing network diagnostics

• US 7,355,981 B2
• Filed: 11/23/2001
• Issued: 04/08/2008
• Est. Priority Date: 11/23/2001
• Status: Expired due to Term

• Current Assignee: Appneta Inc (Broadcom, Inc.)
• Original Assignee: Appneta Inc (Broadcom, Inc.)
• Inventors: Jorgenson, Loki
• Primary Examiner(s): To; Doris H.
• Assistant Examiner(s): GREY, CHRISTOPHER P
• Application Number:
  US09/990,381
• Publication Number:
  US 20030103461A1
• Time in Patent Office: 2,328 Days
• Field of Search: 370241-253
• US Class Current: 370/241
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/50 Testing arrangements

Abstract

A system for identifying problems in networks receives test data which may include statistical information regarding packet loss on a path. The system creates a signature from the test data and compares the signature to example signatures corresponding to various network conditions. The system identifies one or more of the example signatures which match the test signature. The system may comprise an expert system which applies rules to identify an example signature that the test signature best matches.

Claims

1. A method for identifying network conditions affecting a computer network, the network having a mechanism for sending packet bursts along a path in the network and receiving said packet bursts at an end of the path, the method comprising:

providing a plurality of example signatures, each of the example signatures including information indicative of a specific network condition, and at least a part of one or more example signatures indicative of one or more of packet loss, packet ordering and packet timings, wherein each specific network condition causes a unique behavior directly indicative of data transmission performance in the computer network;

acquiring test data, which test data is based on actual propagation of test packets along the path;

creating a test signature from the test data, said test signature being an organized collection of information obtained from said test data, and at least a part of said test signature indicative of one or more of packet loss, packet ordering and packet timings, wherein the test signature comprises packet loss statistics for a plurality of positions within bursts of test packets of a first size;

comparing the test signature to the example signatures; and

,

identifying at least one of the example signatures which matches the test signature according to a match criterion, thereby identifying at least one network condition affecting the computer network.

2. The method of claim 1 wherein comparing the test signature to the example signatures comprises computing a similarity measure between the test signature and each of the example signatures.

3. The method of claim 2 wherein computing a similarity measure comprises performing a chi-squared calculation.

4. The method of claim 2 comprising normalizing the similarity measures corresponding to the example signatures before identifying at least one of the example signatures which matches the test signature.

5. The method of claim 4 wherein normalizing the similarity measures is based at least in part upon the similarity measure that would be obtained in a lossless network.

6. The method of claim 5 wherein normalizing the similarity measures is based at least in part upon the similarity measure that would be obtained if the test signature and example signature were identical.

7. The method of claim 6 wherein normalizing the similarity measures comprises evaluating for each similarity measure:

8. The method of claim 4 comprising adjusting one or more of the similarity measures based upon an individual set of rules associated with that similarity measure before identifying at least one of the example signatures which matches the test signature.

9. The method of claim 8 wherein the individual set of rules includes one or more rules based upon factors including one or more of:

a number of ICMP network unreachable messages;

a number of ICMP host unreachable messages;

a number of ICMP destination unreachable messages;

a number of ICMP port unreachable messages;

a number of ICMP protocol unreachable messages;

a number of ICMP fragmentation required messages;

a number of ICMP TTL expired messages;

a number of ICMP source quench messages;

a number of ICMP redirect messages;

a number of ICMP router advertisement messages;

a number of ICMP parameter problem messages;

a number of ICMP security problem messages;

a number of unsolicited packets;

a number of out-of-sequence packets;

a non-standard MTU detected; and

a number of timed out packets.

10. The method of claim 1 wherein

the test signature comprises a plurality of values,

each of the example signatures comprise a set of corresponding values and,

computing the similarity measure between the test signature and an example signature comprises computing a fit between each of the values of the test signature and the corresponding value of the example signature.

11. The method of claim 10 wherein computing a fit between a value of the test signature and a corresponding value of the example signature is performed by evaluating a function associated with the value.

12. The method of claim 10 wherein computing the fit between each of the values of the test signature and the corresponding value of the example signature comprises performing a computation substantially mathematically equivalent to:

G(x,m)=A exp(−

B(x−

m)²)

where x is a value in the test signature, m is the corresponding value of the example signature and A and B are coefficients.

13. The method of claim 10 wherein computing the fit between each of the values of the test signature and the corresponding value of the example signature comprises performing a computation substantially mathematically equivalent to:

14. The method of claim 13 wherein values for C and λ

are associated with each corresponding value of the example signature and performing the computation comprises using the values for C and λ

associated with the corresponding value of the example signature with which the fit to a value of the test signature is being computed.

15. The method of claim 13 wherein the test signature comprises a mean packet loss for bursts of packets of each of a plurality of sizes.

16. The method of claim 15 comprising determining the mean packet loss, BrAvg substantially as follows:

17. The method of claim 1 wherein the test signature comprises, packet loss statistics for a plurality of positions within bursts of test packets of a second size.

18. The method of claim 17 wherein one of the first and second sizes is not more than three times a minimum packet size for the path.

19. The method of claim 18 wherein the other one of the first and second sizes is within 10% of a maximum packet size for the path.

20. The method of claim 17 wherein one of the first and second sizes is within 10% of a maximum packet size for the path.

21. The method of claim 17 wherein the test signature comprises, packet loss statistics for a plurality of positions within bursts of test packets of a third size wherein the third size is intermediate the first and second sizes.

22. The method of claim 17 wherein the test signature comprises a first moment of packet losses within bursts of packets of the first size.

23. The method of claim 17 wherein the test signature comprises a first moment of packet losses within bursts of packets for bursts of packets of each of the first and second sizes.

24. The method of claim 23 comprising determining the first moment of packet losses, BrMom, substantially as follows:

25. The method of claim 17 wherein the plurality of example signatures comprise example signatures corresponding to two or more of:

a small queues condition;

a lossy condition;

a half-full duplex conflict condition;

a full-half duplex conflict condition;

an inconsistent MTU condition;

a long half-duplex link condition; and

a media errors condition.

26. The method of claim 1 wherein the test signature comprises a mean packet loss for bursts of packets of each of a plurality of sizes.

27. The method of claim 26 comprising determining the mean packet loss, BrAvg substantially as follows:

28. The method of claim 1 wherein the test signature comprises a first moment of packet losses within bursts of packets of a given size.

29. The method of claim 1 wherein the test signature comprises a first moment of packet losses within bursts of packets for bursts of packets of each of a plurality of sizes.

30. The method of claim 29 comprising determining the first moment of packet losses, BrMom, substantially as follows:

31. The method of claim 1 wherein the test data includes data regarding the propagation of datagrams along the test path.

32. The method of claim 31 wherein the test signature comprises one or more packet loss statistics for the datagrams.

33. The method of claim 32 wherein the test data comprises information regarding the propagation of datagrams of a plurality of sizes along the test path and the test signature comprises packet loss statistics for datagrams of each of the plurality of sizes.

34. The method of claim 1 wherein the path is a closed path.

35. The method of claim 34 wherein the packets comprise ICMP ECHO packets.

36. The method of claim 34 wherein one or more of the test packets are formatted using TCP protocol or UDP protocol.

37. The method of claim 36 wherein the one or more test packets formatted using TCP or UDP protocol are returned from an end host by software or hardware.

38. The method of claim 36 wherein the test signature comprises packet loss statistics derived from the one or more of the test packets formatted using TCP protocol or UDP protocol.

39. The method of claim 1 wherein the test signature further comprises additional measures.

40. The method of claim 39 wherein the additional measures include one or more of:

measures derived from packet or burst loss statistics;

measures derived from other statistics relating to propagation of test packets along the path;

relative measures; and

test conditions.

41. The method of claim 39 wherein the additional measures are based on ICMP messages from network devices along the path, the ICMP messages containing information relating to one or more of:

network errors;

network congestion; and

packet timeouts.

42. The method of claim 39 wherein the additional measures are based on information regarding network topology including one or more of:

maximum transfer unit, RMON message; and

SNMP message.

43. The method of claim 1 wherein the test data comprises information regarding one or more of:

connectivity, maximum transmission unit, network device responsivity; and

time for test packets to traverse the path.

44. The method of claim 1 wherein the test data comprises information regarding one or more of:

lost packets;

final inter-packet separation;

hop number, hop address, measured MTU, reported MTU, error flag and information relating to the packet bursts prior to sending along the path.

45. The method of claim 44 wherein the test data comprises information regarding derivatives of said information.

46. The method of claim 1 wherein the test signature comprises one or more functions, the one or more functions relating to one or more of:

packet loss statistics;

round trip time; and

final inter-packet spacing.

47. The method of claim 46 wherein the test signature comprises one or more higher-order functions derived from said one or more functions.

48. The method of claim 1 wherein the path is an open path wherein test packets are sent from one location and received at a different location.

49. The method of claim 48 wherein the test signature comprises packet loss statistics.

50. Apparatus for identifying network conditions affecting a computer network, the network having a mechanism for sending packets in bursts along a path in the network and receiving the packet bursts at an end of the path, the apparatus comprising:

a data store holding a plurality of example signatures, indicative of a plurality of specific network conditions, each of the example signatures including information indicative of a specific network condition, and at least a part of one or more example signatures indicative of one or more of packet loss, packet ordering and packet timings, wherein each specific network condition causes a unique behavior directly indicative of data transmission performance in the computer network;

an input for receiving test data, which test data is based on actual propagation of test packets along the path;

means for creating a test signature from the test data, said test signature being an organized collection of information obtained from said test data, and at least a part of said test signature indicative of one or more of packet loss, packet ordering and packet timings, wherein the test signature comprises packet loss statistics for a plurality of positions within bursts of test packets of a first size;

means for comparing the test signature to the example signatures; and

,

means for identifying at least one of the example signatures which matches the test signature, wherein said identifying determines at least one of said plurality of specific network conditions which is affecting the computer network.

51. The apparatus of claim 50 wherein the means for identifying at least one of the example signatures which matches the test signature comprises an expert system and a rule base.

52. The apparatus of claim 51 wherein the rule base includes rules which accept as input additional information other than the test signature.

53. The apparatus of claim 52 wherein the additional information comprises one or more of:

a number of ICMP network unreachable messages;

a number of ICMP host unreachable messages;

a number of ICMP destination unreachable messages;

a number of ICMP port unreachable messages;

a number of ICMP protocol unreachable messages;

a number of ICMP fragmentation required messages;

a number of ICMP TTL expired messages;

a number of ICMP source quench messages;

a number of ICMP redirect messages;

a number of ICMP router advertisement messages;

a number of ICMP parameter problem messages;

a number of ICMP security problem messages;

a number of unsolicited packets;

a number of out-of-sequence packets;

a non-standard MTU detected;

and a number of timed out packets.

54. The apparatus of claim 53 wherein the means for comparing the test signature to the example signatures comprises means for calculating a similarity measure between the test signature and each of the example signatures.

55. The apparatus of claim 54 wherein the test signature comprises a plurality of values, each of the example signatures comprise a set of corresponding values and, the means for calculating a similarity measure between the test signature and each of the example signatures comprises means for computing a fit between each of the values of the test signature and the corresponding value of the example signature.

56. The apparatus of claim 54 wherein the means for comparing the test signature to the example signatures comprises a neural network.

57. The apparatus of claim 50 wherein the example signatures comprise example signatures corresponding to two or more of:

a small queues condition;

a lossy condition;

a half-full duplex conflict condition;

a full-half duplex conflict condition;

an inconsistent MTU condition;

a long half-duplex link condition; and

a media errors condition.

58. Apparatus for identifying network conditions affecting a computer network, the network having a mechanism for sending packets in bursts along a path in the network and receiving the packet bursts at an end of the path, the apparatus comprising:

a data store holding a plurality of example signatures, indicative of a plurality of specific network conditions, each of the example signatures including information indicative of a specific and different network condition, and at least a part of one or more example signatures indicative of one or more of packet loss, packet ordering and packet timings, wherein each specific network condition causes a unique behavior directly indicative of data transmission performance in the computer network, wherein the example signatures comprise packet loss statistics for a plurality of positions within bursts of test packets of a first size;

an input for receiving test data, which test data is based on actual propagation of test packets along the path;

a test signature creation mechanism configured to create a test signature based upon the test data, said test signature being an organized collection of information obtained from said test data, and at least a part of said test signature indicative of one or more of packet loss, packet ordering and packet timings;

a comparison system configured to derive a similarity measure between a the test signature and each of the plurality of example signatures; and

,

a selection system configured to identify at least one of the example signatures which best matches the test signature, thereby identifying at least one network condition affecting the computer network.

59. The apparatus of claim 58 comprising a data processor wherein the test signature creation mechanism, comparison system, and selection system each comprise a set of software instructions in a program store accessible to the processor.

60. The apparatus of claim 58 wherein the example signatures comprise packet loss statistics for a plurality of positions within bursts of test packets of a second size.

61. The apparatus of claim 60 wherein the example signatures comprise packet loss statistics for a plurality of positions within bursts of test packets of a third size wherein the third size is intermediate the first and second sizes.

62. The apparatus of claim 61 wherein the example signatures comprise a mean packet loss for bursts of packets of each of a plurality of sizes.

63. The apparatus of claim 61 wherein the example signatures comprise a first moment of packet losses within bursts of packets of a size.

64. The apparatus of claim 61 wherein the example signatures comprise a first moment of packet losses within bursts of packets for bursts of packets of each of a plurality of sizes.

65. The apparatus of claim 61 comprising a test packet sequencer connected to dispatch a sequence of test packets along a network path.

66. The apparatus of claim 65 wherein the test packet sequencer is configured to generate and to dispatch onto the path multiple bursts of ICMP ECHO packets.

67. The apparatus of claim 58 comprising a set weighting coefficients, fitting coefficients, or both weighing and fitting coefficients associated with one or more of the example signatures.

68. A program product comprising a computer readable medium carrying a set of computer-readable signals comprising instructions which, when executed by a computer processor, cause the data processor to execute a method for identifying network conditions affecting a computer network, the network having a mechanism for sending packet bursts along a path in the network and receiving said packet bursts at an end of the path, the method comprising:

providing a plurality of example signatures indicative of a plurality of specific network conditions, each of the example signatures including information indicative of a specific and different network condition, and at least a part of one or more example signatures indicative of one or more of packet loss, packet ordering and packet timings, wherein each specific network condition causes a unique behavior directly indicative of data transmission performance in the computer network;

acquiring test data, which test data is based on actual propagation of test packets along the path;

creating a test signature from the test data, said test signature being an organized collection of information obtained from said test data, and at least a part of said test signature indicative of one or more of packet loss, packet ordering and packet timings, wherein the test signature comprises packet loss statistics for a plurality of positions within bursts of test packets of a first size;

comparing the test signature to the example signatures; and

,

identifying at least one of the example signatures which matches the test signature according to a match criterion, thereby identifying at least one network condition affecting the computer network.