TRANSACTION RECOGNITION AND PREDICTION USING REGULAR EXPRESSIONS

• US 20060031458A1
• Filed: 10/04/2002
• Published: 02/09/2006
• Est. Priority Date: 08/11/1998
• Status: Active Grant

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.), Platinum Technology Incorporated (Broadcom, Inc.), PLATINUM Technology IP, Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.), Platinum Technology Incorporated (Broadcom, Inc.), PLATINUM Technology IP, Inc. (Broadcom, Inc.)
• Inventors: Ross, Perry R.
• Granted Patent: US 6,990,521 B1
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 41/5054 Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The present invention is directed to a method and apparatus for identifying occurrences of transactions, especially in computer networks. A unique identifier, denoted “request identifier”, is associated with each service request. Accordingly, for a sequence of service requests detected, a corresponding sequence of request identifiers is generated. The request identifier sequence is compared to regular expressions that correspond to different transactions. If the request identifier sequence matches a regular expression, this sequence is deemed to represent an occurrence of that transaction.

Claims

1. A method for recognizing an occurrence of a transaction that is defined by a sequence of one or more service requests, comprising:

reading a service request that is transmitted between two computational components, the service request comprising at least a portion of a request by a first of the two computational components for processing by a second of the two computational components;

normalizing the service request into a service request representation to remove at least some service request-specific information from the service request;

combining the representation of the service request with a plurality of other service request representations to form a string of service request representations; and

automatically comparing the string of service request representations with a predetermined regular expression characterizing the transaction to determine if the string of service request representations corresponds to an occurrence of the transaction.

2. The method of claim 1, wherein the reading step comprises:

selecting a set of service requests from among a plurality of sets of service requests;

categorizing the selected set of service requests based upon at least one of a source and a destination of the service requests in the selected set.

3. The method of claim 1, wherein the service request includes a service request packet.

4. The method of claim 1, wherein each of the service requests in the string of service request representations is ordered by time and further comprising:

comparing a time interval between a second service request and a last service request, for corresponding representations in the string of service request representations, with a predetermined time interval to determine if the representation of the second service request is a part of the string of service request representations.

5. The method of claim 1, further comprising:

assigning to the service request a unique identifier characterizing the service request, wherein said identifier is included in the representation for the service request.

6. The method of claim 1, wherein each of the service request representations in the string has a unique identifier.

7. The method of claim 1, wherein the regular expression includes one or more of the following operators:

(a) an operator indicating that a service request occurs zero or more times;

(b) an operator indicating that a service request occurs one or more times;

(c) an operator indicating that a service request is optional; and

(d) an operator indicating that only one of a collection of one or more service requests can occur.

8. A system for recognizing an occurrence of a transaction that is defined by a sequence of one or more service requests, comprising:

means for reading a service request that is transmitted between two computational components, the service request comprising at least a portion of a request by a first of the two computational components for processing by a second of the two computational components;

means for normalizing the service request into a service request representation to remove at least some service request-specific information from the service request;

means for combining the representation of the service request with a plurality of other service request representations to form a string of service request representations; and

means for comparing the string of service request representations with a predetermined regular expression characterizing a transaction to determine if the string of service request representations corresponds to an occurrence of the transaction.

9. A method for predicting occurrences of transactions, comprising:

collecting a sequence of service request representations, each service request representation comprising a normalized service request to remove at least some service request-specific information from the service request and each service request comprising at least a portion of a request by a first computational component for processing by a second computational component;

partitioning the service request representations of the sequence into subsets, wherein each subset of service request representations is expected to be indicative of one or more occurrences of a single transaction type;

constructing a regular expression from the one or more occurrences, wherein each of the occurrences satisfy the regular expression; and

predicting whether an additional set of service requests is an instance of the transaction type by determining if the additional set of service request representations satisfy the regular expression.

10. A method for identifying an occurrence of a transaction, comprising:

decomposing a set of one or more service request identifiers, each service request identifier associated with a service request communicated between two network components and identified using a service request representation associated with the service request, each service request comprising at least a portion of a request by a first of the two network components for processing by a second of the two network components and the service request representation comprising a normalized service request to remove at least some service request-specific information from the service request; and

comparing the set with a predetermined regular expression characterizing the transaction.

11. The method of claim 10, further comprising:

sorting the service request representations based upon at least one of the source and destination of a corresponding service request represented by the service request representation.

12. The method of claim 10, wherein each of the service request representations in the set is ordered by time and further comprising:

comparing a time interval between a second service request and a previous service request, wherein both have representations in the set, with a predetermined time interval to determine if the representation for the second service request is a part of the set of service request representations.

13. The method of claim 10, further comprising:

assigning to a service request a unique identifier characterizing the service request, wherein said identifier is included in a corresponding service request representation for the service request.

14. The method of claim 13, wherein the regular expression comprises one or more service request identifiers.

15. The method of claim 10, wherein a plurality of the service request representations in the set each have a unique identifier.

16. A system for identifying an occurrence of a transaction, comprising:

means for decomposing a set of one or more service request identifiers, each service request identifier associated with a service request communicated between two network components and identified using a service request representation associated with the service request, each service request comprising at least a portion of a request by a first of the two network components for processing by a second of the two network components and the service request representation comprising a normalized service request to remove at least some service request-specific information from the service request; and

means for comparing the set with a predetermined regular expression characterizing the transaction.

17. A system for recognizing an occurrence of a transaction, comprising:

at least one recorder operable to monitor communication between two network components; and

a monitor coupled to the at least one recorder and operable to;

identify a service request that is transmitted between the two network components, the service request comprising at least a portion of a request by a first of the two network components for processing by a second of the two network components;

normalize the service request into a service request representation to remove at least some service request-specific information from the service request;

combine the representation of the service request with at least one other service request representation to form a string of service request representations; and

compare the string of service request representations with a predetermined regular expression characterizing a transaction to determine if the string of service request representations corresponds to an occurrence of the transaction.

18. A system for recognizing an occurrence of a transaction that is defined by a sequence of one or more service requests, comprising:

at least one computer readable medium; and

software encoded on the at least one computer readable medium and operable when executed by one or more processors to;

read a service request that is transmitted between two computational components, the service request comprising at least a portion of a request by a first of the two computational components for processing by a second of the two computational components;

normalize the service request into a service request representation to remove at least some service request-specific information from the service request;

combine the representation of the service request with a plurality of other service request representations to form a string of service request representations; and

compare the string of service request representations with a predetermined regular expression characterizing the transaction to determine if the string of service request representations corresponds to an occurrence of the transaction.

19. A system for recognizing an occurrence of a transaction, comprising:

a transaction analyzer operable to generate a set of one or more service request identifiers, each service request identifier associated with a service request communicated between two network components and identified using a service request representation associated with the service request, each service request comprising at least a portion of a request by a first of the two network components for processing by a second of the two network components and the service request representation comprising a normalized service request to remove at least some service request-specific information from the service request; and

a regular expression matcher operable to compare the set of one or more service request identifiers to at least one predetermined regular expression characterizing at least one identified transaction to determine whether the transaction representation corresponds to an occurrence of one of the identified transactions.

20. A system for identifying an occurrence of a transaction, comprising:

at least one computer readable medium; and

software encoded on the at least one computer readable medium and operable when executed by one or more processors to;

decompose a set of one or more service request identifiers, each service request identifier associated with a service request communicated between two network components and identified using a service request representation associated with the service request, each service request comprising at least a portion of a request by a first of the two network components for processing by a second of the two network components and the service request representation comprising a normalized service request to remove at least some service request-specific information from the service request; and

compare the set with a predetermined regular expression characterizing the transaction.