Multi-tier message correlation

Abstract

A system and method determines correlations within multi-tier communications based on repeated iterations/episodes of executions of a target application. Content-based correlations are determined by encoding the content using a finite alphabet, then searching for similar sequences among the multiple traces. By encoding the content to a finite alphabet, common pattern matching techniques may be used, including, for example, DNA alignment algorithms. To facilitate alignment of the traces, structural and/or semantic breakpoints are defined, and the encoding in each trace is synchronized to these breakpoints. To facilitate efficient processing, a hierarchy of causality among tier-pairs is identified, and messages at lower levels are ranked and temporally filtered, based on activity intervals at higher levels of the hierarchy.

We claim: 
     
         1 . A method comprising:
 capturing a plurality of network traces, each network trace corresponding to original messages communicated between two nodes of a tier-pair during an execution episode of an application,   encoding, by a transaction analysis system, content of some or all of the original messages in each network trace into letters of a finite-alphabet set to form corresponding encoded messages, such that a single letter of the finite-alphabet in each encoded message corresponds to a plurality of bytes in the original message,   comparing, by the transaction analysis system, the encoded messages of a first episode to the encoded messages of a second episode to identify encoded messages that are similar to each other, and   identifying, by the transaction analysis system, original messages in at least one of the plurality of network traces corresponding to the encoded messages that are identified as being similar to each other.   
     
     
         2 . The method of  claim 1 , including filtering the network traces to identify the original messages of the tier-pair based on messages communicated between nodes of an other tier-pair. 
     
     
         3 . The method of  claim 2 , including grouping the messages of the other tier-pair into activity intervals, and filtering the network traces based on parameters associated with these activity intervals. 
     
     
         4 . The method of  claim 2 , including grouping the original messages of the tier-pair into first activity intervals, grouping the messages of the other tier-pair into second activity intervals, and filtering the network traces based on a correspondence in time between the first and second activity intervals. 
     
     
         5 . The method of  claim 4 , including scoring the first activity intervals based on the correspondences in time and filtering the network traces based on the scoring. 
     
     
         6 . The method of  claim 5 , wherein the scoring is based on:
 an overlap in time between the first and second activity intervals,   a correspondence in time between a start of the first activity interval and a start of the second activity interval, and   a correspondence in time between an end of the first activity interval and an end of the second activity interval.   
     
     
         7 . The method of  claim 1 , wherein the encoding includes a hashing of the plurality of bytes of the original message. 
     
     
         8 . The method of  claim 1 , including forming one or more of the plurality of bytes of the original message based on break points associated with the original message. 
     
     
         9 . The method of  claim 8 , wherein the break points are based on a structure of the original message. 
     
     
         10 . The method of  claim 8 , wherein the break points are based on content of the original message. 
     
     
         11 . The method of  claim 1 , wherein comparing the encoded messages of the first and second episodes includes forming k-tuples of letters of the first and second encoded messages and comparing the k-tuples of the first and second encoded messages. 
     
     
         12 . The method of  claim 11 , including comparing the first and second encoded messages based on k-tuples of a first size, then comparing at least parts of the first and second encoded messages based on k-tuples of a second size that is smaller than the first size. 
     
     
         13 . The method of  claim 11 , wherein comparing the first and second encoded messages includes creating a matrix of coincidences between the first and second encoded messages and assessing coincidences of k-tuples along diagonals of the matrix. 
     
     
         14 . The method of  claim 13 , wherein assessing the coincidences includes accumulating a count of sequential coincidences along the diagonals. 
     
     
         15 . The method of  claim 1 , wherein comparing the encoded messages of the first and second episodes includes determining a longest common sequence of coincidences of letters in the encoded messages. 
     
     
         16 . The method of  claim 1 , including comparing encoded messages of a third episode of the application to the encoded messages of the first and second episodes that are identified as being similar to identify encoded messages that are similar in the first, second, and third episodes. 
     
     
         17 . A method comprising:
 identifying, at a performance analysis system, a hierarchy of tier-pairs, such that messages at a higher level of the hierarchy have a causal relationship to one or more messages at a lower level of the hierarchy,   capturing traces of messages communicated within the tier-pairs,   identifying, by the performance analysis system, activity intervals at each tier-pair corresponding to sequences of messages at each tier-pair,   assessing, by the performance analysis system, the activity intervals at each lower level tier-pair based on parameters associated with activity intervals at a higher level tier-pair to identify activity intervals at the lower level tier pair that are potentially related to activity intervals at the higher level tier pair, and   comparing, by the performance analysis system, the messages of activity intervals at the lower level tier-pairs that are potentially related to activity intervals at the higher level tier pair to identify messages at the lower level tier-pairs corresponding to one or more activity intervals at a highest level tier-pair.   
     
     
         18 . The method of  claim 17 , wherein comparing the messages includes: encoding content of some or all of the messages into letters of a finite-alphabet set to form corresponding encoded messages, such that a single letter of the finite-alphabet in each encoded message corresponds to a plurality of bytes in the original message, and comparing the corresponding encoded messages. 
     
     
         19 . The method of  claim 17 , wherein the messages being compared at each tier-pair correspond to messages captured during repeated executions of an application. 
     
     
         20 . A non-transitory computer-readable medium that includes software that, when executed by a processor causes the processor to:
 receive a plurality of network traces, each network trace corresponding to original messages communicated between two nodes of a tier-pair during an execution episode of an application,   encode content of some or all of the original messages in each network trace into letters of a finite-alphabet set to form corresponding encoded messages, such that a single letter of the finite-alphabet in each encoded message corresponds to a plurality of bytes in the original message,   compare the encoded messages of a first episode to the encoded messages of a second episode to identify encoded messages that are similar to each other, and   identify original messages in at least one of the plurality of network traces corresponding to the encoded messages that are identified as being similar to each other.