PATH IDENTIFICATION FOR NETWORK DATA

• US 20080195729A1
• Filed: 02/12/2007
• Published: 08/14/2008
• Est. Priority Date: 02/12/2007
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chand, Jagdish, Narayanareddy, Jagannatha, Antony, Suresh, Nadgir, Avanti, Bhargava, Rajesh
• Application Number:
  US11/673,857
• Publication Number:
  US 20080195729A1
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A solution is provided wherein a master process and two or more drone processes may be utilized to identify path information containing a pattern. The master process may send the pattern to the two or more drone processes, which may identify the pattern in path data. Each drone process may then send the paths that satisfy the pattern back to the master process, which may aggregate the path data so that two or more identical paths appearing in the path data are reduced to a single occurrence of a path.

Claims

1. A method for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the method comprising:

sending the pattern of path information to two or more drone processes;

receiving, from the two or more drone processes, path data containing paths satisfying the pattern along with payload information corresponding to the paths;

aggregating the path data received from the two or more drone processes so that two or more identical paths appearing in the path data are reduced to a single occurrence of a path; and

transmitting the aggregated path data to a top data identification process.

2. The method of claim 1, wherein the two or more drone processes are executed by different processors.

3. The method of claim 1, further comprising:

encoding the pattern in a format matching a format in which the path information is stored.

4. The method of claim 3, wherein mapping information relating to the encoding is stored in a mapping file separate from the path data.

5. The method of claim 1, wherein the top data identification process produces summary data containing a summary of the path data and a top number of results from the aggregated path data.

6. A method for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the method executed at a drone process and comprising:

receiving the pattern from a master process;

identifying all paths in the path information that satisfy the pattern; and

sending the paths that satisfy the pattern to the master process.

7. The method of claim 6, further comprising:

aggregating the paths that satisfy the pattern so that two or more identical paths appearing in the path data are reduced to a single occurrence of a path.

8. The method of claim 6, further comprising:

performing pattern matching on the paths that satisfy the pattern to identify patterns that satisfy additional constraints.

9. The method of claim 6, wherein the identifying includes:

identifying all paths in the path information that contain a first node in the pattern;

creating a data structure having, for each of the paths that contain the first node, an identification of a position in a path file of an offset to where path information relating to the path begins, an identification of a position of the first node in the pattern, and an identification of a position of the second node in the pattern, wherein the identifications of the positions of the second node are initialized to invalid;

identifying all paths in the data structure that contain the first and second nodes in the pattern; and

updating the data structure to fill in identifications of positions of the second node for paths in the data structure that contain the first and second nodes.

10. The method of claim 9, further comprising:

extracting paths from the path file corresponding to any paths in the data structure that contain valid position information for both the first and second nodes.

11. The method of claim 9, further comprising:

extracting paths from the path file corresponding to any paths in the data structure that contain valid position information for both the first and second nodes and that also contain a position for the first node that is less than a position for the second node.

12. The method of claim 9, wherein the data structure further includes an identification of a position of a third node in the pattern and wherein the method further comprises:

identifying all paths in the data structure that contain the first, second, and third nodes in the pattern; and

updating the data structure to fill in identifications of positions of the third node for paths in the data structure that contain the first, second, and third nodes.

13. A system for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the system comprising:

a master process;

two or more drone processes; and

a top path identification process;

wherein the master process is configured to send pattern information to the two or more drone processes, receive aggregated path data from the two or more drone processes, aggregate the aggregated path data from the two or more drone processes, and transmit the results of the aggregation to the top path identification process;

wherein the two or more drone processes are each configured to identify paths in different sets of path information that contain the pattern, aggregate the identified paths, and return the aggregated path data to the master process; and

wherein the top path identification process is configured to summarize and output a top number of results from the results transmitted from the master process.

14. An apparatus for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the apparatus comprising:

a two or more drone process pattern sender;

a satisfied pattern path data receiver;

a path data aggregator coupled to the satisfied pattern path data receiver; and

an aggregated path data top data identification process transmitter coupled to the path data aggregator.

15. A drone apparatus for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the drone apparatus comprising:

a master process pattern receiver;

a satisfied pattern path information identifier coupled to the master process pattern receiver; and

a master process satisfied pattern path data sender coupled to the satisfied pattern path information identifier.

16. An apparatus for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the apparatus comprising:

means for sending the pattern of path information to two or more drone processes;

means for receiving, from the two or more drone processes, path data containing paths satisfying the pattern along with payload information corresponding to the paths;

means for aggregating the path data received from the two or more drone processes so that two or more identical paths appearing in the path data are reduced to a single occurrence of a path; and

transmitting the aggregated path data to a top data identification process.

17. An drone apparatus for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the drone apparatus comprising:

means for receiving the pattern from a master process;

means for identifying all paths in the path information that satisfy the pattern; and

means for sending the paths that satisfy the pattern to the master process.

18. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the method comprising:

sending the pattern of path information to two or more drone processes;

receiving, from the two or more drone processes, path data containing paths satisfying the pattern along with payload information corresponding to the paths;

aggregating the path data received from the two or more drone processes so that two or more identical paths appearing in the path data are reduced to a single occurrence of a path; and

transmitting the aggregated path data to a top data identification process.

19. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for identifying path information containing a pattern, wherein the path information relates to network nodes visited by users of a computer network, the method executed at a drone process and comprising:

receiving the pattern from a master process;

identifying all paths in the path information that satisfy the pattern; and

sending the paths that satisfy the pattern to the master process.