Method and apparatus for providing multi-protocol, multi-stage, real-time frame classification

• US 6,904,057 B2
• Filed: 05/04/2001
• Issued: 06/07/2005
• Est. Priority Date: 05/04/2001
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: SLT Logic LLC
• Inventors: Sarkinen, Scott A., Sarkinen, Gregg T., Trivedi, Hemant Vrajlal
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/849,913
• Publication Number:
  US 20020163909A1
• Time in Patent Office: 1,495 Days
• Field of Search: 370/412, 370/469, 370/401, 370/392, 370/389, 711/104, 711/108, 711/100, 709/230, 709/236
• US Class Current: 370/469
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04Q 11/04 for time-division multiplexing H04Q11/0001 takes precedence
• CPC Class Codes: H04Q 2213/1302 Relay switches
• CPC Class Codes: H04Q 2213/13039 Asymmetrical two-way transmission, e.g. ADSL, HDSL
• CPC Class Codes: H04Q 2213/1304 Coordinate switches, crossbar, 4/2 with relays, coupling field
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13174 Data transmission, file transfer
• CPC Class Codes: H04Q 2213/13196 Connection circuit/link/trunk/junction, bridge, router, gateway
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13215 Code checking, CRC
• CPC Class Codes: H04Q 2213/13216 Code signals, frame structure
• CPC Class Codes: H04Q 2213/1324 Conference call
• CPC Class Codes: H04Q 2213/13248 Multimedia
• CPC Class Codes: H04Q 2213/1329 Asynchronous transfer mode, ATM
• CPC Class Codes: H04Q 2213/13292 Time division multiplexing, TDM
• CPC Class Codes: H04Q 2213/1332 Logic circuits
• CPC Class Codes: H04Q 2213/13349 Network management
• CPC Class Codes: H04Q 2213/13352 Self-routing networks, real-time routing
• CPC Class Codes: H04Q 2213/13376 : Information service, downloading of information, 0800/0900 services
• CPC Class Codes: H04Q 2213/13389 : LAN, internet

Abstract

A multi-protocol, multi-stage, real-time frame classifier is disclosed. A preliminary multi-protocol frame composition analyzer is provided for performing preliminary multi-protocol frame classification for incoming frames. A parsing instruction generator is provided for processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions. A multi-stage parsing engine provides multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame. An advanced level of data extraction is provided across various frame protocols without imposing a performance penalty. Longest prefix match searches and/or direct lookup searches are supported. Moreover, conditional extractions, instruction branching, multi-stage processing are all performed in real time.

Claims

1. A method for handling packets, comprising:

performing preliminary multi-protocol frame classification for incoming frames;

processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions; and

providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame;

wherein the processing further comprises;

storing an incoming frame in a memory buffer;

generating the parsing instructions for the incoming frame based upon the multi-protocol classification; and

aligning the generated parsing instructions with frame data selected from the incoming frames stored in the memory buffer.

2. The method of claim 1 wherein the performing preliminary multi-protocol frame classification further comprises resolving a composition for the incoming frame.

3. The method of claim 1 wherein the providing multi-stage parsing of the incoming frame further comprises:

reading at least a portion of the incoming frame from a memory buffer;

interpreting the parsing instructions; and

executing macros for performing parsing functions on at least the portion of the incoming frame using the interpreted parsing instructions.

4. The method of claim 1 wherein the providing multi-stage parsing of the incoming frame further comprises:

generating extractions instructions in response to the at least incoming frame and the preliminary multi-protocol frame classification;

using the extraction instructions to produce search queries; and

applying the search queries against a memory to produce the search results.

5. The method of claim 4 wherein the using the extraction instructions further comprises conditional extraction.

6. The method of claim 5 wherein conditional extraction comprises determining whether extracted bits of data from the packet meet a predetermined criteria.

7. The method of claim 4 wherein the providing multi-stage parsing of the incoming frame further comprises:

reprocessing the search results to generate refined parsing instructions; and

parsing of the incoming frame according to the refined parsing instructions to generate refined search results, the refined search results providing greater information about the incoming frame.

8. The method of claim 1 wherein the providing multi-stage parsing of the incoming frame further comprises:

reprocessing the search results to generate refined parsing instructions; and

parsing of the incoming frame according to the refined parsing instructions to generate refined search results, the refined search results providing greater information about the incoming frame.

9. The method of claim 1 wherein the processing at least the incoming frame and the preliminary multi-protocol frame classification further comprises processing the search results, the incoming frame and the preliminary multi-protocol frame classification to provide refined parsing instructions.

10. The method of claim 1 wherein the parsing instructions comprise a location identifier and an associated instruction to be applied to the frame at the position identified by the location identifier.

11. The method of claim 1 wherein the frame comprises one of a plurality of frame protocols, the performing preliminary multi-protocol frame classification further comprising classifying a protocol identity.

12. The method of claim 1 wherein the performing preliminary multi-protocol frame classification further comprises identifying each layer protocol and writing the frame into memory along with a protocol layer code.

13. The method of claim 12 wherein providing multi-stage parsing of the incoming frame further comprises using the protocol layer code as a start vector into an instruction memory, the instruction memory containing instructions for parsing the frame and pointers to access selected words of the frame in a frame buffer.

14. The method of claim 13 wherein the performing preliminary multi-protocol frame classification further comprises identifying each layer protocol and writing the frame into memory along with a protocol layer code, the method further comprising processing the instructions from the instruction memory, resolving the pointers according to the protocol layer table and aligning the frame data with the instruction words.

15. The method of claim 13 wherein the search results are fed back to an instruction controller to be used as data that a parsing engine can parse through a data pipe.

16. The method of claim 15 wherein the search results are fed back to an instruction controller to be used as a start vector for subsequent processing stages.

17. The method of claim 1 wherein the memory comprises a content addressable memory and the search queries are used to search the content addressable memory.

18. The method of claim 1 wherein the memory comprises a static random access memory and the search queries are indexed directly to a static random access memory.

19. The method of claim 1 further comprising providing a parser instruction set in the instruction memory to define microcode used for generating the parser instructions.

20. The method of claim 1 further comprising forwarding the frame and the search results.

21. The method of claim 1 wherein the search results include the frame classification.

22. The method of claim 1 wherein providing multi-stage parsing of the incoming frame further comprises performing conditional branching, the conditional branching allowing specific instructions to be performed based upon satisfaction of a predetermined criteria.

23. A multi-protocol, multi-stage, real-time frame classifier, comprising:

a preliminary multi-protocol frame composition analyzer for performing preliminary multi-protocol frame classification for incoming frames;

a parsing instruction generator for processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions; and

a multi-stage parsing engine for providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame;

wherein the parsing instruction generator processing further comprises;

a memory buffer for storing an incoming frame;

an instruction generator for creating the parsing instructions for the incoming frame based upon the multi-protocol frame classification; and

a data pipe for aligning the generated parsing instructions with frame data selected from the incoming frames stored in the memory buffer.

24. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the preliminary multi-protocol frame classifier resolves a composition for the incoming frame.

25. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the multi-stage parsing engine reads at least a portion of the incoming frame from a memory buffer, interpret the parsing instructions, and executes macros for performing parsing functions on at least the portion of the incoming frame using the interpreted parsing instructions.

26. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the multi-stage parsing engine generates extraction instructions in response to the at least incoming frame and the preliminary multi-protocol frame classification.

27. The multi-protocol, multi-stage, real-time frame classifier of claim 26 wherein the multi-state parsing engine performs conditional extractions using the extraction instructions.

28. The multi-protocol, multi-stage, real-time frame classifier of claim 27 wherein conditional extraction comprises determining whether extracted bits of data from the packet meet a predetermined criteria.

29. The multi-protocol, multi-stage, real-time frame classifier of claim 26 wherein the multi-stage parsing engine further comprises an extractor for using the extraction instructions to produce search queries and a memory for applying the search queries against to produce the search results.

30. The multi-protocol, multi-stage, real-time frame classifier of claim 29 further comprising a feedback path for allowing the search results to be reprocessed to generate refined parsing instructions that are used by the parsing engine to generate refined search results, the refined search results providing greater information about the incoming frame.

31. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the parsing instructions generator processes the search results, the incoming frame and the preliminary multi-protocol frame classification to provide refined parsing instructions.

32. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the parsing instructions comprise a location identifier and an associated instruction to be applied to the frame at the position identified by the location identifier.

33. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the frame comprises one of a plurality of frame protocols, the preliminary multi-protocol frame classifier classifying the incoming frame to identify a protocol identity.

34. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the preliminary multi-protocol frame classifier identifies each layer protocol and writes the frame into memory along with a protocol layer code.

35. The multi-protocol, multi-stage, real-time frame classifier of claim 34 wherein the multi-stage parsing engine uses the protocol layer code as a start vector for an instruction memory, the instruction memory containing instructions for parsing the frame and pointers to access selected words of the frame in a memory buffer.

36. The multi-protocol, multi-stage, real-time frame classifier of claim 35 wherein the parsing instructions generator identifies each layer protocol and writes the frame into memory along with a protocol layer code and wherein the multi-stage parsing engine processes the instructions from the instruction memory, resolves the pointers according to the protocol layer table and aligns the frame data with the instruction words.

37. The multi-protocol, multi-stage, real-time frame classifier of claim 35 wherein the search results are fed back to the parsing instructions generator to be used as data that a parsing engine can parse through a data pipe.

38. The multi-protocol, multi-stage, real-time frame classifier of claim 37 wherein the parsing instructions generator further comprises an instruction controller and wherein the search results are fed back to the instruction controller to be used as a start vector for subsequent processing stages.

39. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the memory comprises a content addressable memory and the search queries are used to search the content addressable memory.

40. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the memory comprises a static random access memory and the search queries are indexed directly to a static random access memory.

41. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the parsing instructions generator provides a parser instruction set in an instruction memory to define microcode used for generating the parser instructions.

42. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the multi-stage parsing engine forwards the frame and the search results.

43. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the search results include the frame classification.

44. The multi-protocol, multi-stage, real-time frame classifier of claim 23 wherein the multi-stage parsing engine performs conditional branching, the conditional branching allowing specific instructions to be performed based upon satisfaction of a predetermined criteria.

45. An article of manufacture comprising a program storage medium readable by a computer, the medium tangibly embodying one or more programs of instructions executable by the computer to perform a method for parsing frames in a network flow, the method comprising:

performing preliminary multi-protocol frame classification for incoming frames;

processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions; and

providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame ;

wherein the processing further comprises;

storing an incoming frame in a memory buffer;

generating the parsing instructions for the incoming frame based upon the multi-protocol classification; and

aligning the generated parsing instructions with frame data selected from the incoming frames stored in the memory buffer.

46. The article of manufacture of claim 45 wherein the performing preliminary multi-protocol frame classification further comprises resolving a composition for the incoming frame.

47. The article of manufacture of claim 45 wherein the providing multi-stage parsing of the incoming frame further comprises:

reading at least a portion of the incoming frame from a memory buffer;

interpreting the parsing instructions; and

executing macros for performing parsing functions on at least the portion of the incoming frame using the interpreted parsing instructions.

48. The article of manufacture of claim 45 wherein the providing multi-stage parsing of the incoming frame further comprises:

generating extractions instructions in response to the at least incoming frame and the preliminary multi-protocol frame classification;

using the extraction instructions to produce search queries; and

applying the search queries against a memory to produce the search results.

49. The article of manufacture of claim 48 wherein the using the extraction instructions further comprises conditional extraction.

50. The article of manufacture of claim 49 wherein conditional extraction comprises determining whether extracted bits of data from the packet meet a predetermined criteria.

51. The article of manufacture of claim 48 wherein the providing multi-stage parsing of the incoming frame further comprises:

reprocessing the search results to generate refined parsing instructions; and

parsing of the incoming frame according to the refined parsing instructions to generate refined search results, the refined search results providing greater information about the incoming frame.

52. The article of manufacture of claim 45 wherein the providing multi-stage parsing of the incoming frame further comprises:

reprocessing the search results to generate refined parsing instructions; and

parsing of the incoming frame according to the refined parsing instructions to generate refined search results, the refined search results providing greater information about the incoming frame.

53. The article of manufacture of claim 45 wherein the processing at least the incoming frame and the preliminary multi-protocol frame classification further comprises processing the search results, the incoming frame and the preliminary multi-protocol frame classification to provide refined parsing instructions.

54. The article of manufacture of claim 45 wherein the parsing instructions comprise a location identifier and an associated instruction to be applied to the frame at the position identified by the location identifier.

55. The article of manufacture of claim 45 wherein the frame comprises one of a plurality of frame protocols, the performing preliminary multi-protocol frame classification further comprising classifying a protocol identity.

56. The article of manufacture of claim 45 wherein the performing preliminary multi-protocol frame classification further comprises identifying each layer protocol and writing the frame into memory along with a protocol layer code.

57. The article of manufacture of claim 56 wherein providing multi-stage parsing of the incoming frame further comprises using the protocol layer code as a start vector into an instruction memory, the instruction memory containing instructions for parsing the frame and pointers to access selected words of the frame in a memory buffer.

58. The article of manufacture of claim 57 wherein the performing preliminary multi-protocol frame classification further comprises identifying each layer protocol and writing the frame into memory along with a protocol layer code, the method further comprising processing the instructions from the instruction memory, resolving the pointers according to the protocol layer table and aligning the frame data with the instruction words.

59. The article of manufacture of claim 57 wherein the search results are fed back to an instruction controller to be used as data that a parsing engine can parse through a data pipe.

60. The article of manufacture of claim 59 wherein the search results are fed back to an instruction controller to be used as a start vector for subsequent processing stages.

61. The article of manufacture of claim 45 wherein the memory comprises a content addressable memory and the search queries are used to search the content addressable memory.

62. The article of manufacture of claim 45 wherein the memory comprises a static random access memory and the search queries are indexed directly to a static random access memory.

63. The article of manufacture of claim 45 further comprising providing a parser instruction set in the instruction memory to define microcode used for generating the parser instructions.

64. The article of manufacture of claim 45 further comprising forwarding the frame and the search results.

65. The article of manufacture of claim 45 wherein the search results include the frame classification.

66. The article of manufacture of claim 45 wherein providing multi-stage parsing of the incoming frame further comprises performing conditional branching, the conditional branching allowing specific instructions to be performed based upon satisfaction of a predetermined criteria.