Method and system for inline top N query computation

• US 7,882,262 B2
• Filed: 08/18/2005
• Issued: 02/01/2011
• Est. Priority Date: 08/18/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sasu, Gheorghe Mircea, Wang, Yuewei, Stevens, Eli Nathaniel, Bhattacharya, Partha
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): Gupta; Muktesh G
• Application Number:
  US11/207,329
• Publication Number:
  US 20070043703A1
• Time in Patent Office: 1,993 Days
• Field of Search: 709/238, 707/3, 707/703, 707/770, 726/22
• US Class Current: 709/238
• CPC Class Codes: G06F 16/24 Querying

Abstract

A system and method of generating an overall top N query result from multiple sets of sessionized network events that correspond to different time periods include identifying a subset within each set of network events whose event attributes satisfy a predefined query, generating an aggregation result table for each identified subset of network events in accordance with an aggregation attribute, identifying matching first and second entries in first and second aggregation result tables that have a same aggregation attribute value, generating a new entry in a query result table by merging the matching first and second entries together, and selecting entries in the query result table that have highest session counts as the overall top N query result.

Claims

1. A method of processing network events, comprising:

receiving multiple sets of network events, each set corresponding to a different respective predefined time period and each network event having an associated group of event attributes;

identifying a subset, within each set of network events, whose event attributes satisfy a predefined query;

generating a distinct aggregation result table for each identified subset of network events;

aggregating, in a first aggregation result table, information concerning a first identified subset of network events in accordance with at least one of the event attributes;

aggregating, in a second aggregation result table, information concerning a second identified subset of network events in accordance with the at least one of the event attributes; and

merging the first and second aggregation result tables so as to produce a merged set of results for the predefined query;

wherein the merging further comprises;

identifying a first entry in the first aggregation result table and a second entry in the second aggregation result table, wherein the first entry and the second entry have the same value for the at least one of the event attributes;

generating a new entry in a query result table by combining the first and second entries together;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the aggregating further includes:

assigning a session identifier to a network event in a particular identified subset;

identifying an aggregation entry in a particular aggregation result table, associated with the particular identified subset, in accordance with the network event'"'"'s value for the at least one of the event attributes, the aggregation entry including a set of session identifiers;

inserting the network event'"'"'s session identifier into the set of session identifiers if the network event'"'"'s session identifier is not included in the set of session identifiers; and

changing a position of the aggregation entry in the particular aggregation result table if a predefined condition is met.

3. The method of claim 2, wherein the aggregation entry includes a session count and the predefined condition is met if the aggregation entry'"'"'s session count is higher than the session count of a preceding entry in the particular aggregation result table.

4. The method of claim 2, wherein the aggregation entry includes a session count and the predefined condition is met if the aggregation entry'"'"'s session count is higher than or equal to the session count of a preceding entry in the particular aggregation result table.

5. The method of claim 1,

wherein each entry in each aggregation result table includes a respective session count, and the merging includes combining session counts associated with the first entry and the second entry.

6. The method of claim 1, wherein the merging further includes selecting entries in the query result table that satisfy a predefined criterion.

7. The method of claim 6, wherein the predefined criterion is satisfied if a selected entry in the query result table is among a group of entries having highest numbers of session identifiers in the query result table.

8. The method of claim 6, including associating a count with each entry in the query result table, wherein selecting comprises selecting a predefined number of entries in the query result table having highest counts.

9. The method of claim 1, wherein the merging includes associating a session count with each entry in the query result table, and sorting the entries in the query result table in accordance with their respective session counts.

10. The method of claim 1, wherein each of the different respective predefined time periods is less than an hour.

11. The method of claim 1, wherein the merged set of results for the predefined query comprise comprises query results for an aggregate time period of more than 10 hours.

12. The method of claim 1, wherein the aggregating further includes:

assigning a session identifier to a network event in a particular identified subset;

identifying an aggregation entry in a particular aggregation result table, associated with the particular identified subset, in accordance with the network event'"'"'s value for the at least one of the event attributes, the aggregation entry including a set of session identifiers, a link to a preceding entry and a link to a following entry in the particular aggregation result table;

inserting the network event'"'"'s session identifier into the set of session identifiers if the network event'"'"'s session identifier is not included in the set of session identifiers; and

updating the links to the preceding and following entries if a predefined condition is met.

13. A system for processing network events, comprising:

one or more central processing units for executing programs; and

an interface for receiving network events; and

a query analysis engine executable by the one or more central processing units, the query analysis engine further comprising;

receiving instructions for receiving multiple sets of the network events via the interface, each set corresponding to a different respective predefined time period and each network event having an associated group of event attributes;

an event filter for identifying a subset, within each set of network events, whose event attributes satisfy a predefined query;

generation instructions for generating a distinct aggregation result table for each identified subset of network events;

aggregation instructions for;

aggregating, in a first aggregation result table, information concerning a first identified subset of network events in accordance with at least one of the event attributes; and

aggregating, in a second aggregation result table, information concerning a second identified subset of network events in accordance with the at least one of the event attributes; and

query result instructions for merging the first and second aggregation result tables so as to produce a merged set of results for the predefined query;

wherein the query result instructions further comprise instructions for;

identifying a first entry in the first aggregation result table and a second entry in the second aggregation result table, wherein the first entry and the second entry have the same value for the at least one of the event attributes; and

generating a new entry in a query result table by combining the first and second entries together.

14. The system of claim 13, wherein the query analysis engine includes storing instructions for storing at least a portion of aggregated information concerning each identified subset of the network events, and the query result instructions include instructions for merging at least a subset of the stored aggregated information.

15. The system of claim 13, wherein the aggregation instructions include:

instructions for assigning a session identifier to a network event in a particular identified subset;

instructions for identifying an aggregation entry in a particular aggregation result table, associated with the particular identified subset, in accordance with the network event'"'"'s value for the at least one of the event attributes, the aggregation entry including a set of session identifiers;

instructions for inserting the network event'"'"'s session identifier into the set of session identifiers if the network event'"'"'s session identifier is not included in the set of session identifiers; and

instructions for changing a position of the aggregation entry in the particular aggregation result table if a predefined condition is met.

16. The system of claim 15, wherein the aggregation entry includes a session count and the predefined condition is met if the aggregation entry'"'"'s session count is higher than the session count of a preceding entry in the particular aggregation result table.

17. The system of claim 15, wherein the aggregation entry includes a session count and the predefined condition is met if the aggregation entry'"'"'s session count is higher than or equal to the session count of a preceding entry in the particular aggregation result table.

18. The system of claim 13, wherein the query result instructions include selecting instructions for selecting entries in the query result table that satisfy a predefined criterion.

19. The system of claim 13, wherein each entry in each aggregation result table includes a respective session count, and the query result instructions include instructions for combining session counts associated with the first entry and the second entry.

20. The system of claim 18, wherein the predefined criterion is satisfied if a selected entry in the query result table is among a group of entries having highest numbers of session identifiers in the query result table.

21. The system of claim 13, wherein the query analysis engine includes instructions for associating a session count with each entry in the query result table, and the query result instructions include instructions for combining session counts of matching entries in two or more of the aggregation result tables.

22. The system of claim 13, wherein the query analysis engine includes instructions for associating a session count with each entry in the query result table, and instructions for sorting the entries in the query result table in accordance with their respective session counts.

23. The system of claim 18, wherein the query analysis engine includes instructions for associating a session count with each entry in the query result table, and wherein the selecting instructions comprise instructions for selecting a predefined number of entries in the query result table having highest session counts.

24. The system of claim 13, wherein each of the different respective predefined time periods is less than an hour and the merged set of results for the predefined query comprises query results for an aggregate time period of more than 10 hours.

25. A computer program product stored in a non-transitory computer-readable storage medium, for use in conjunction with a computer system, comprising:

receiving instructions for receiving multiple sets of network events, each set corresponding to a different respective predefined time period and each network event having an associated group of event attributes;

an event filter for identifying a subset, within each set of network events, whose event attributes satisfy a predefined query; and

generation instructions for generating a distinct aggregation result table for each identified subset of network events;

aggregation instructions for;

aggregating, in a first aggregation result table, information concerning a first identified subset of network events in accordance with at least one of the event attributes; and

aggregating, in a second aggregation result table, information concerning a second identified subset of network events in accordance with the at least one of the event attributes; and

query result instructions for merging the first and second aggregation result tables aggregated information associated with the multiple sets of network events so as to produce a merged set of results for the predefined query;

wherein the query result instructions further comprise instructions for;

identifying a first entry in the first aggregation result table and a second entry in the second aggregation result table, wherein the first entry and the second entry have the same value for the at least one of the event attributes; and

generating a new entry in a query result table by combining the first and second entries together.

26. The computer program product stored in a non-transitory computer-readable storage medium of claim 25, wherein the aggregation instructions further include:

instructions for assigning a session identifier to a network event in a particular identified subset;

instructions for identifying an aggregation entry in a particular aggregation result table, associated with the particular identified subset, in accordance with the network event'"'"'s value for the at least one of the event attributes, the aggregation entry including a set of session identifiers;

instructions for inserting the network event'"'"'s session identifier into the set of session identifiers if the network event'"'"'s session identifier is not included in the set of session identifiers; and

instructions for changing a position of the aggregation entry in the particular aggregation result table if a predefined condition is met.

27. The computer program product stored in a non-transitory computer-readable storage medium of claim 26, wherein the aggregation entry includes a session count and the predefined condition is met if the aggregation entry'"'"'s session count is higher than the session count of a preceding entry in the particular aggregation result table.

28. The computer program product stored in a non-transitory computer-readable storage medium of claim 26, wherein the aggregation entry includes a session count and the predefined condition is met if the aggregation entry'"'"'s session count is higher than or equal to the session count of a preceding entry in the particular aggregation result table.

29. The computer program product stored in a non-transitory computer-readable storage medium of claim 25, wherein the query result instructions include selecting instructions for selecting entries in the query result table that satisfy a predefined criterion.

30. The computer program product stored in a non-transitory computer-readable storage medium of claim 25, wherein each entry in each aggregation result table includes a respective session count, and the query result instructions include instructions for combining session counts associated with the first entry and the second entry matching entries of the aggregation result tables comprise entries having a same value for the at least one of the event attributes.

31. The computer program product stored in a non-transitory computer-readable storage medium of claim 29, wherein the predefined criterion is satisfied if a selected entry in the query result table is among a group of entries having highest numbers of session identifiers in the query result table.

32. The computer program product stored in a non-transitory computer-readable storage medium of claim 25, wherein the query result instructions include analysis engine includes instructions for associating a session count with each entry in the query result table, and the query result instructions includes instructions for combining session counts of matching entries in two or more of the aggregation result tables.

33. The computer program product stored in a non-transitory computer-readable storage medium of claim 25, wherein the query result instructions include analysis engine includes instructions for associating a session count with each entry in the query result table, and instructions for sorting the entries in the query result table in accordance with their respective session counts.

34. The computer program product stored in a non-transitory computer-readable storage medium of claim 29, wherein the query result instructions include analysis engine includes instructions for associating a session count with each entry in the query result table, and wherein the selecting instructions comprise instructions for selecting a predefined number of entries in the query result table having highest session counts.

35. The computer program product stored in a non-transitory computer-readable storage medium of claim 25, wherein each of the different respective predefined time periods is less than an hour and the merged set of results for the predefined query comprises query results for an aggregate time period of more than 10 hours the query result instructions include instructions for producing a query result table having entries produced by merging matching entries of the aggregation result tables, and further includes instructions for selecting entries in the query result table that satisfy a predefined criterion.