Packet data analysis with efficient and flexible parsing capabilities

• US 6,952,425 B1
• Filed: 11/14/2000
• Issued: 10/04/2005
• Est. Priority Date: 11/14/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nelson, William M.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Mais, Mark A
• Application Number:
  US09/714,793
• Time in Patent Office: 1,785 Days
• Field of Search: 370/389, 370/390, 370/392, 370/393, 370/395.1, 370/396, 370/395.31, 370/395.4, 370/400, 370/432, 370/468, 370/477, 380/28, 380/36, 380/37, 380/42, 380/43, 713/160, 709/205, 709/220, 709/236
• US Class Current: 370/429
• CPC Class Codes: H04L 67/14 Session management for real-time applications in data packet communications networks H04L65/1066
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods and apparatus which facilitate the handling of data between platforms interconnected by any of a variety of network environments are disclosed. In general terms, the present invention represents an improvement over conventional packet parsing and searching mechanisms. The parse mechanism sequentially analyzes each character of the packet data and passes relevant characters to the search mechanism as soon as each character is reached. Preferably, the characters of each data field are parsed character-by-character. In one implementation, prior to searching a relevant data field, the parser initializes the appropriate search mechanism based on at least the data field type (e.g., the cookie field or URL field of an HTTP request). Each character of the relevant data is then passed sequentially to the search mechanism, where a search state are obtained for each passed character. Accordingly, the parser passes each character of the relevant data fields to the search mechanism. Since the parser passes the well-defined fields of standard protocols, such as HTTP and FTP, parsing may be efficiently performed without referencing memory (e.g., parsing is implemented in micro-code). When the parser reaches the end of the relevant data field, the parser may then cause the search mechanism to output search results associated with the search state of the last searched character. Alternatively, the parser may initiate another search for another data field, which is subsequently parsed and searched character-by-character as recited above for the first field.

Claims

1. A method for handling packet data having a plurality of data segments sent from a first node to a second node within a computer network, the method comprising:

obtaining a first parse state based on a first data segment of the packet data;

obtaining a first search state that is based at least on the first data segment and that is associated with obtaining the first parse state;

obtaining a second parse state based on a second data segment of the packet data and the first parse state;

obtaining a second search state that is based at least on the second data segment and the first search state and that is associated with obtaining the second parse state;

obtaining a third parse state based on a third data segment of the packet data and the second parse state; and

outputting search results based on the second search state and that is associated with obtaining the third parse state.

2. A method as recited in claim 1, wherein the first data segment, the second data second, and the third data segment are each a character within the packet data and are not a first character within the packet data.

3. A method as recited in claim 1, further comprising setting a first initial parse state based on a protocol of the packet data, wherein the first and second parse states are based on the first initial parse state.

4. A method as recited in claim 3, wherein the protocol is a session type.

5. A method as recited in claim 3, wherein the protocol is a virtual server identifier (VSID).

6. A method as recited in claim 1, wherein the obtaining of the first, second, and third parse states are implemented within micro-code without referencing memory.

7. A method as recited in claim 1, wherein the first and second data segments belong to a same first data field within the packet data.

8. A method as recited in claim 7, further comprising setting an initial search state prior to obtaining the first and second search states, wherein the first and second search states are based on the initial search state.

9. A method as recited in claim 8, wherein the first initial search state is based on at least a type of the first data field.

10. A method as recited in claim 9, wherein the first initial search state is further based on a direction of propagation of the packet data.

11. A method as recited in claim 10, wherein the type of first data field is selected from a group consisting of a Uniform Resource Location (URL) type, an Access Control List (ACL) type, a host type, and a cookie type.

12. A method as recited in claim 9, further comprising:

obtaining a fourth parse state based on a fourth data segment of the packet data and the third parse state;

obtaining a third search state that is based at least on the fourth data segment and that is associated with obtaining the fourth parse state;

obtaining a fifth parse state based on a fifth data segment of the packet data and the fourth parse state;

obtaining a fourth search state that is based at least on the fifth data segment and the third search state and that is associated with obtaining the fifth parse state;

obtaining a sixth parse state based on a sixth data segment of the packet data and the fifth parse state; and

outputting search results based on the fourth search state and that is associated with obtaining the sixth parse state,

wherein the fourth and fifth data segments belong to a same second data field that differs from the first data field.

13. A method as recited in claim 12, further comprising setting a second initial search state prior to obtaining the third and fourth search states, wherein the third and fourth search states are based at least on the second initial search state.

14. A method as recited in claim 13, wherein the second initial second search state is based on at least a type of the second data field and the second initial second search differs from the first initial search.

15. A method as recited in claim 14, wherein the second initial search state is further based on a direction of propagation of the packet data.

16. A method as recited in claim 14, wherein the type of the second data field is selected from a group consisting of a Uniform Resource Location (URL) type, an Access Control List (ACL) type, a host type, and a cookie type.

17. A method as recited in claim 1, wherein the first data segment belongs to a first packet and the second data segment belongs to a second packet, and the method further comprising:

receiving the first packet;

receiving the second packet after the first packet; and

storing the first search state and the first parse state, wherein obtaining the second parse state is based on the stored first parse state and obtaining the second search state is based on the stored first search state.

18. A method as recited in claim 1, wherein the search results facilitate load balancing.

19. A method as recited in claim 1, wherein the search results facilitate web caching.

20. A method as recited in claim 1, wherein the search results facilitate traffic security mechanisms.

21. A method as recited in claim 1, wherein the search results indicate a policy for handling the packet data.

22. A method as recited in claim 1, wherein the packet data is error-free and ordered.

23. A method as recited in claim 1, further comprising terminating parsing and searching based on the third parse state.

24. A method as recited in claim 1, further comprising replacing either the first or second segment with a replacement data segment so that either a first or a second search state is obtained for the replacement data segment.

25. A method as recited in claim 24, wherein the replaced first or second data segment is a character equivalent to an escape sequence.

26. A method as recited in claim 1, wherein the first and second search states are obtained based on a regular expression type search being performed for the first and second data segments.

27. A method as recited in claim 1, wherein the first and second search states are obtained based on a hashing type search being performed for the first and second data segments.

28. A computer system operable to handle packet data having a plurality of data segments sent from a first node to a second node within a computer network, the computer system comprising:

one or more processors;

one or more memory, wherein at least one of the processors and memory are adapted to;

obtain a first parse state based on a first data segment of the packet data;

obtain a first search state that is based at least on the first data segment and that is associated with the first parse state;

obtain a second parse state based on a second data segment of the packet data and the first parse state;

obtain a second search state that is based at least on the second data segment and the first search state and that is associated with the second parse state;

obtain a third parse state based on a third data segment of the packet data and the second parse state; and

output search results based on the second search state and that is associated with the third parse state.

29. A computer system as recited in claim 28 wherein the first data segment, the second data second, and the third data segment are each a character within the packet data.

30. A computer system as recited in claim 28, wherein at least one of the processors and memory are further adapted to set a first initial parse state based on a protocol of the packet data, wherein the first and second parse states are based on the first initial parse state.

31. A computer system as recited in claim 28, wherein the obtaining of the first, second, and third parse states are implemented within micro-code without referencing memory.

32. A computer system as recited in claim 28, wherein the first and second data segments belong to a same first data field within the packet data.

33. A computer system as recited in claim 32, wherein at least one of the processors and memory are further adapted to set an initial search state prior to obtaining the first and second search states, wherein the first and second search states are based on the initial search state.

34. A computer system as recited in claim 33, wherein the first initial search state is based on at least the a type of the first data field.

35. A computer system as recited in claim 34, wherein the first initial search state is further based on a direction of propagation of the packet data.

36. A computer system as recited in claim 34, wherein at least one of the processors and memory are further adapted to:

obtain a fourth parse state based on a fourth data segment of the packet data and the third parse state;

obtain a third search state that is based at least on the fourth data segment and that is associated with obtaining the fourth parse state;

obtain a fifth parse state based on a fifth data segment of the packet data and the fourth parse state;

obtain a fourth search state that is based at least on the fifth data segment and the third search state and that is associated with obtaining the fifth parse state;

obtain a sixth parse state based on a sixth data segment of the packet data and the fifth parse state; and

output search results based on the fourth search state and that is associated with obtaining the sixth parse state,

wherein the fourth and fifth data segments belong to a same second data field that differs from the first data field.

37. A computer system as recited in claim 36, wherein at least one of the processors and memory are further adapted to set a second initial search state prior to obtaining the third and fourth search states, wherein the third and fourth search states are based at least on the second initial search state.

38. A computer system as recited in claim 37, wherein the second initial second search state is based on at least the a type of the second data field.

39. A computer system as recited in claim 38, wherein the second initial search state is further based on a direction of propagation of the packet data.

40. A computer system as recited in claim 28, wherein the first data segment belongs to a first packet and the second data segment belongs to a second packet, and at least one of the processors and memory are further adapted to:

receive the first packet;

receive the second packet after the first packet; and

store the first search state and the first parse state, wherein obtaining the second parse state is based on the stored first parse state and obtaining the second search state is based on the stored first search state.

41. A computer system as recited in claim 28, wherein at least one of the processors and memory are further adapted to replace either the first or second segment with a replacement data segment so that either a first or a second search state is obtained for the replacement data segment.

42. A computer program product for handling packet data having a plurality of data segments sent from a first node to a second node within a computer network, the computer program product comprising:

at least one computer readable medium;

computer program instructions stored within the at least one computer readable product configured to cause a processing device to;

obtain a first parse state based on a first data segment of the packet data;

obtain a first search state that is based at least on the first data segment and that is associated with the first parse state;

obtain a second parse state based on a second data segment of the packet data and the first parse state;

obtain a second search state that is based at least on the second data segment and the first search state and that is associated with the second parse state;

obtain a third parse state based on a third data segment of the packet data and the second parse state; and

output search results based on the second search state and that is associated with the third parse state.

43. An apparatus for handling packet data having a plurality of data segments sent from a first node to a second node within a computer network, the apparatus comprising:

means for parsing the packet data;

means for initializing a search based on the parsing of the packet data; and

means for outputting search results based on a searching procedure performed on the packet data and the parsing of the packet data.

44. An apparatus as recited in claim 43, farther comprising means for initializing the parsing of the packet data.