Signature Matching Methods and Apparatus for Performing Network Diagnostics

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.

1 . A method for identifying one or more network conditions which affect a computer network, the network having a mechanism for sending packets along a path in the network and receiving said packets at an end of the path, the method comprising:
 a) providing a plurality of example signatures, each example signature exemplifying a unique network condition, wherein each example signature includes a set of idealized values indicative of the unique network condition which the example signature exemplifies;   b) acquiring test data regarding propagation of the packets along the path;   c) deriving a test signature from the test data, wherein the test signature includes a set of values;   d) comparing the test signature to each of the plurality of example signatures; and   e) selecting one or more of the plurality of example signatures which matches the test signature according to a match criterion;   thereby identifying one or more network conditions which affect the computer network.   
   
   
       2 . The method for identifying one or more network conditions according to  claim 1 , wherein at least a part of one or more example signatures is indicative of one or more of packet loss, packet ordering and packet timings. 
   
   
       3 . The method for identifying one or more network conditions according to  claim 1 , wherein the plurality of example signatures comprises a signature indicative of: a small queues condition, a lossy condition, a half-full duplex condition, a full-half duplex condition, an inconsistent maximum transmission unit condition, a long half-duplex link condition, a small buffers condition or a media errors condition. 
   
   
       4 . The method for identifying one or more network conditions according to  claim 1 , wherein the test data comprises information regarding one or more of: lost packets; final inter-packet separation; hop number; hop address; measured maximum transmission unit; reported maximum transmission unit; error flag; information relating to the packets prior to sending along the path; connectivity; maximum transmission unit; network device responsivity; and time for packets to traverse the path. 
   
   
       5 . The method for identifying one or more network conditions according to  claim 1 , wherein at least a part of the test signature is indicative of one or more of packet loss, packet ordering and packet timings. 
   
   
       6 . The method for identifying one or more network conditions according to  claim 1 , wherein the test signature comprises packet loss statistics. 
   
   
       7 . The method for identifying one or more network conditions according to  claim 1 , wherein the test signature comprises measures derived from packet loss statistics or measures derived from other statistics relating to propagation of the test packets along the path. 
   
   
       8 . The method for identifying one or more network conditions according to  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. 
   
   
       9 . The method for identifying one or more network conditions according to  claim 8 , comprising normalizing the similarity measures corresponding to the example signatures before selecting one or more of the plurality of example signatures which matches the test signature. 
   
   
       10 . The method for identifying one or more network conditions according to  claim 9 , wherein normalizing the similarity measures is based at least in part on the similarity measure that would be obtained in a lossless network. 
   
   
       11 . The method for identifying one or more network conditions according to  claim 9 , wherein normalizing the similarity measures is based at least in part on the similarity measure that would be obtained if the test signature and example signature are identical. 
   
   
       12 . The method for identifying one or more network conditions according to  claim 8 , comprising adjusting one or more of the similarity measures based upon an individual set of rules associated with that similarity measure before selecting one or more of the plurality of example signatures which matches the test signature. 
   
   
       13 . The method for identifying one or more network conditions according to  claim 1 , wherein at least some of the packets are configured as bursts. 
   
   
       14 . The method for identifying one or more network conditions according to  claim 1 , wherein the packets are formatted using ICMP protocol, TCP protocol or UDP protocol. 
   
   
       15 . The method for identifying one or more network conditions according to  claim 1 , wherein the path is a closed path, wherein said packets are sent from and received at the same location. 
   
   
       16 . The method for identifying one or more network conditions according to  claim 1 , wherein the path is an open path, wherein said packets are sent from one location and received at a different location. 
   
   
       17 . A method for identifying one or more network problems which affect a computer network, the network having a mechanism for sending packets along a path in the network and receiving said packets at an end of the path, the method comprising:
 a) providing a plurality of example signatures, each example signature uniquely exemplifying a network condition uniquely correspondent to a specific network problem, wherein each example signature is derived from observing behaviour of test packets as they pass through a test computer network configured with the specific network problem which the example signature uniquely exemplifies;   b) acquiring test data regarding propagation of the packets along the path;   c) deriving a test signature from the test data;   d) comparing the test signature to each of the plurality of example signatures; and   e) selecting one or more of the plurality of example signatures which matches the test signature according to a match criterion;   thereby identifying one or more network problems which affect the computer network.   
   
   
       18 . A method for identifying a network fault which affects computer network performance, the network having a mechanism for sending packets along a path in the network and receiving said packets at an end of the path, the method comprising:
 a) providing a plurality of example signatures, each example signature exemplifying a unique network condition, wherein a specific network fault causes the unique network condition when packets are sent across the computer network, said unique network condition uniquely indicative of said network fault;   b) acquiring test data regarding propagation of the packets along the path;   c) deriving a test signature from the test data, wherein the test signature includes a set of values;   d) comparing the test signature to each of the plurality of example signatures; and   e) selecting one or more of the plurality of example signatures which matches the test signature according to a match criterion;   thereby identifying one or more network faults which affect the performance of the computer network.   
   
   
       19 . An apparatus for identifying one or more network conditions which affect a computer network, the network having a mechanism for sending packets along a path in the network and receiving said packets at an end of the path, the apparatus comprising:
 a) a data store holding a plurality of example signatures, each example signature exemplifying a unique network condition, wherein each example signature includes a set of idealized values indicative of the unique network condition which the example signature exemplifies;   b) an input for receiving test data, said test data based on propagation of the packets along the path;   c) a test signature creation mechanism configured to create a test signature from the test data, wherein the test signature includes a set of values;   d) a comparison system configured to compare the test signature to each of the plurality of example signatures; and   e) a selection system configured to select one or more of the plurality of example signatures which matches the test signature according to a match criterion;   thereby identifying one or more network conditions which affect the computer network.   
   
   
       20 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the selection system comprises an expert system and a rule base. 
   
   
       21 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the rule base includes rules which accept as input additional information other than the test signature. 
   
   
       22 . The apparatus for identifying one or more network conditions according to  claim 19 , comprising a data processor wherein the test creation mechanism; comparison system and selection system each comprise a set of software instructions in a program store accessible to the processor. 
   
   
       23 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein at least a part of one or more example signatures is indicative of one or more of packet loss, packet ordering and packet timings. 
   
   
       24 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the plurality of example signature comprises a signature indicative of: a small queues condition, a lossy condition, a half-full duplex condition, a full-half duplex condition, an inconsistent maximum transmission unit condition, a long half-duplex link condition, a small buffers condition or a media errors condition. 
   
   
       25 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the test data comprises information regarding one or more of: lost packets; final inter-packet separation; hop number; hop address; measured maximum transmission unit; reported maximum transmission unit; error flag; information relating to the packets prior to sending along the path; connectivity; maximum transmission unit; network device responsivity; and time for packets to traverse the path. 
   
   
       26 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein at least a part of the test signature is indicative of one or more of packet loss, packet ordering and packet timings. 
   
   
       27 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the test signature comprises packet loss statistics. 
   
   
       28 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the test signature comprises measures derived from packet loss statistics or measures derived from other statistics relating to propagation of the test packets along the path. 
   
   
       29 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein the comparison system is configured to compute a similarity measure between the test signature and each of the example signatures. 
   
   
       30 . The apparatus for identifying one or more network conditions according to  claim 29 , wherein the selection system is configured to normalize the similarity measures corresponding to the example signatures before selecting one or more of the plurality of example signatures which matches the test signature. 
   
   
       31 . The apparatus for identifying one or more network conditions according to  claim 30 , wherein the selection system is configured to normalize the similarity measures based at least in part on the similarity measure that would be obtained in a lossless network. 
   
   
       32 . The apparatus for identifying one or more network conditions according to  claim 30 , wherein the selection system is configured to normalize the similarity measures based at least in part on the similarity measure that would be obtained if the test signature and example signature are identical. 
   
   
       33 . The apparatus for identifying one or more network conditions according to  claim 30 , comprising wherein the selection system is configured to adjust one or more of the similarity measures based upon an individual set of rules associated with that similarity measure before selecting one or more of the example signatures which matches the test signature. 
   
   
       34 . The apparatus for identifying one or more network conditions according to  claim 19 , wherein at least some of the packets are configured as bursts. 
   
   
       35 . A computer 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 one or more network conditions which affect a computer network, the network having a mechanism for sending packets along a path in the network and receiving said packets at an end of the path, the method comprising:
 a) providing a plurality of example signatures, each example signature exemplifying a unique network condition, wherein each example signature includes a set of idealized values indicative of the unique network condition which the example signature exemplifies;   b) acquiring test data regarding propagation of the packets along the path;   c) deriving a test signature from the test data, wherein the test signature includes a set of values;   d) comparing the test signature to each of the plurality of example signatures; and   e) selecting one or more of the plurality of example signatures which matches the test signature according to a match criterion;   thereby identifying one or more network conditions which affect the computer network.