Highly probable identification of related messages using sparse hash function sets

Abstract

Methods, systems, and apparatus for network monitoring and analytics are disclosed. The methods, systems, and apparatus for network monitoring and analytics perform highly probable identification of related messages using one or more sparse hash function sets. Highly probable identification of related messages enables a network monitoring and analytics system to trace the trajectory of a message traversing the network and measure the delay for the message between observation points. The sparse hash function value, or identity, enables a network monitoring and analytics system to identify the transit path, transit time, entry point, exit point, and/or other information about individual packets and to identify bottlenecks, broken paths, lost data, and other network analytics by aggregating individual message data.

1 . A computer-implemented method, comprising:
 calculating, by a processor, a sparse hash value for a first message at a plurality of observation points on a network using a first sparse hash function;   associating, by the processor, metadata with the sparse hash value of the first message;   tracking, by the processor, transit of the first message over the network; and   generating, by the processor, one or more network analytics for the first message over the network, wherein the one or more network analytics are generated from the associated metadata.   
     
     
         2 . The computer-implemented method of  claim 1 , further comprising calculating, by the processor, the sparse hash value of the first message for one or more invariant fields of the first message. 
     
     
         3 . The computer-implemented method of  claim 2 , further comprising treating, by the processor, one or more variant fields as a constant value during calculation of the sparse hash value. 
     
     
         4 . The computer-implemented method of  claim 1 , further comprising:
 calculating, by the processor, a sparse hash value for each of a plurality of messages at the plurality of observation points on the network using the first sparse hash function;   associating, by the processor, metadata with the hash value calculated for each of the plurality of messages;   tracking, by the processor, the transit of the plurality of messages over the network; and   generating, by the processor, the one or more network analytics for the plurality of messages over the network.   
     
     
         5 . The computer-implemented method of  claim 4 , wherein the first sparse hash function generates sparse hash values that are highly probable to be unique for the first plurality of messages. 
     
     
         6 . The computer-implemented method of  claim 4 , further comprising:
 calculating, by the processor, a sparse hash value for a second plurality of messages at the plurality of observation points on the network using a second sparse hash function, wherein the first sparse hash function and the second sparse hash function are different.   
     
     
         7 . The computer-implemented method of  claim 1 , wherein the one or more network analytics comprises at least one of throughput, loss, jitter, latency, errors, retransmits, and fragmentation of packets. 
     
     
         8 . The computer-implemented method of  claim 1 , further comprising mapping one or more variant fields of the first message to an invariant value that is used in the first sparse hash function. 
     
     
         9 . The computer-implemented method of  claim 1 , wherein the associated metadata comprises at least one of a size of the first message, a time of transmission of the first message, a trajectory of the first message through the network, a source of the first message, a destination of the first message, and a type of packet of the first message. 
     
     
         10 . The computer-implemented method of  claim 1 , further comprising determining an existence and a location of original fields of the first message. 
     
     
         11 . An apparatus comprising:
 a processor; and   
       a non-transitory computer-readable medium coupled to the processor, the non-transitory computer-readable medium configured to store computer program instructions that when executed by the processor are operable to cause the processor to:
 calculate a sparse hash value for a first message at a plurality of observation points on a network using a first sparse hash function; 
 associate metadata with the sparse hash value calculated for the first message; 
 track, the transit of the first message over the network; and 
 generate one or more network analytics for the first message over the network. 
 
     
     
         12 . The apparatus of  claim 11 , wherein the processor is further configured to calculate the sparse hash value of the first message using one or more invariant fields of the first message. 
     
     
         13 . The apparatus of  claim 12 , wherein the processor is further configured to treat one or more variant fields of the first message as a constant value during calculation of the sparse hash value. 
     
     
         14 . The apparatus of  claim 11 , wherein the processor is further configured to:
 calculate a sparse hash value for each of a plurality of messages at the plurality of observation points on the network using the first sparse hash function;   associate metadata with the sparse hash value calculated for each of the plurality of messages;   track the transit of the plurality of messages over the network; and   generate the one or more network analytics for the plurality of messages over the network.   
     
     
         15 . The apparatus of  claim 14 , wherein the first sparse hash function generates sparse hash values that are highly probable to be unique for the first plurality of messages. 
     
     
         16 . The apparatus of  claim 14 , wherein the processor is further configured to calculate a sparse hash value for a second plurality of messages at the plurality of observation points on the network using a second sparse hash function, wherein the first sparse hash function and the second sparse hash function are different. 
     
     
         17 . The apparatus of  claim 11 , wherein the one or more network analytics comprises at least one of throughput, loss, jitter, latency, errors, retransmits, and fragmentation of packets. 
     
     
         18 . The apparatus of  claim 11 , wherein the processor is further configured to map one or more variant fields of the first message to an invariant value that is used in the first sparse hash function. 
     
     
         19 . The apparatus of  claim 11 , wherein the associated metadata comprises at least one of a size of the first message, a time of transmission of the first message, a trajectory of the first message through the network, a source of the first message, a destination of the first message, and a type of packet of the first message. 
     
     
         20 . The apparatus of  claim 11 , wherein the processor is further configured to determine an existence and a location of original fields of the first message.