Method and apparatus for programmable lexical packet classifier

• US 7,185,081 B1
• Filed: 03/29/2000
• Issued: 02/27/2007
• Est. Priority Date: 04/30/1999
• Status: Expired due to Fees

• Current Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Liao, Heng
• Primary Examiner(s): Salad; Abdullahi
• Assistant Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US09/538,132
• Time in Patent Office: 2,526 Days
• Field of Search: 709230-231, 709223-228, 709238-240, 709246-247, 709/220, 704/10
• US Class Current: 709/224
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A packet classification language (PCL) is provided to specify data packets in a routing device. The PCL uses regular expressions to match incoming data packets. Class identifiers associated with each regular expression identifies the class to which each recognized packet belongs for subsequent processing. A PCL compiler produces a DFA which recognizes the data packets as defined by the regular expressions. A hardware implemented DFA is used to scan the input stream which constitutes the data packets.

Claims

1. A method for classifying received network data in a network device comprising:

providing a language definition comprising regular expressions;

parsing said regular expressions to identify grammatical structure among said regular expressions to produce a deterministic finite automaton (DFA); and

processing incoming network data with said language definition in accordance with a formal language processing technique including scanning said network data using lexical token scanning according to said language definition, said scanning including recognizing one or more lexical tokens contained in said network data using said DFA, said DFA including a representation of said lexical tokens,

said processing resulting in identification of protocol encapsulation formats in said network data.

2. The method of claim 1 wherein said scanning includes identifying an arithmetic operation and performing said arithmetic operation.

3. The method of claim 1 wherein said network data is treated as a stream of input bytes and said scanning includes identifying a skip operation and in response thereto skipping over one or more subsequent input bytes.

4. The method of claim 1 further wherein said DFA comprises plural states and said network data is organized into data packets, said step of scanning including recognizing data packets using said DFA including transitioning from one state to another.

5. The method of claim 4 wherein said data packets are variable length data packets.

6. The method of claim 5 further including generating a grammar tree data structure representative of said regular expression, producing a non-deterministic finite automaton (NFA) from said grammar tree data structure, and converting said NFA to produce said DFA.

7. The method of claim 4 wherein some of said states include one or more associated computer instructions and wherein said computer instructions are executed in connection with transitioning to a state.

8. The method of claim 7 wherein some of said states further include a skip instruction.

9. In a network data switching device, a method for classifying data packets comprising steps of:

providing a language definition in the form of one or more regular expressions, each having an associated class identifier indicative of a protocol encapsulation format;

parsing said regular expressions to identify grammatical structure among said regular expressions to produce a deterministic finite automaton (DFA), said DFA including a representation of a plurality of lexical tokens;

receiving plural data packets, each having a length not necessarily equal to one another; and

for each data packet, processing said data packet in accordance with a formal language processing technique including determining a matching regular expression from among said regular expressions that matches said data packet, wherein said each data packet is classified according to the class identifier associated with said matching regular expression,

said determining comprising lexical token scanning of said data packet to identify said lexical tokens using said DFA.

10. The method of claim 9 wherein said data packets comprise a data stream and said determining includes lexically scanning said data stream.

11. The method of claim 9 wherein said DFA is in compressed form.

12. The method of claim 9 further including compiling said regular expressions to produce said DFA.

13. The method of claim 12 wherein said compiling produces a non-deterministic finite automaton (NFA) as intermediate data structure, said compiling further includes converting said NFA to produce said DFA.

14. The method of claim 13 further including reducing said DFA to a compressed form.

15. The method of claim 9 wherein said data packet comprises plural bytes, and said determining includes detecting an operator indicating a number of bytes to be skipped.

16. The method of claim 15 wherein said number is specified by the value of a current input byte.

17. The method of claim 15 wherein said number is specified in a register.

18. The method of claim 15 wherein said determining further includes detecting an operator indicating a value to be saved in a register.

19. The method of claim 18 wherein said determining further includes detecting an operator indicating a logical or mathematical operation to be performed on the contents of said register.

20. In a data packet receiving and forwarding device, a method for classifying received data packets constituting a data stream, said method comprising steps of:

receiving a description of classification rules in the form of a classification language definition, said classification language definition including regular expressions;

compiling said classification language definition to produce a deterministic finite automaton (DFA) comprising plural states, including parsing said regular expressions to identify grammatical structure among said regular expressions, said DFA including a representation of a plurality of lexical tokens;

configuring a programmable hardware packet classifier with said DFA; and

receiving said data stream and processing said data stream in accordance with a formal language processing technique including scanning said data stream with said hardware packet classifier to classify said received data packets into one of a plurality of protocol encapsulation formats, said scanning comprising using said DFA to identify said lexical tokens in said data stream.

21. The method of claim 20 wherein said compiling includes associating arithmetic and logic instructions with some of said states.

22. The method of claim 20 wherein said regular expressions include arithmetic and logic operations.

23. The method of claim 22 wherein said regular expressions further include skip operations.

24. The method of claim 23 wherein said regular expressions further include data storage operations.

25. The method of claim 20 wherein said DFA is in compressed format.

26. The method of claim 20 further including:

receiving a second description of classification rules in the form of a second classification language definition;

compiling said second classification language definition to produce a second DFA;

configuring a programmable hardware packet classifier with said second DFA; and

applying said data stream to said hardware packet classifier to classify said received data packets,

wherein said data packets are classified according to said second classification rules, thereby facilitating changing packetizing policies in said data packet routing device.

27. A network data packet classifier comprising:

an input port for receiving network data packets comprising a stream of data;

a memory assemblage configured with data representing a deterministic finite automaton (DFA), said DFA produced from a language definition comprising plural regular expressions by parsing said regular expressions to identify grammatical structure among said regular expressions; and

decompression logic operatively coupled to said memory assemblage and configured to process said stream of data using said language definition in accordance with a formal language processing technique including scanning said stream of data with said DFA to find a matching one of said regular expressions,

said regular expressions having corresponding class identifiers, each class identifier corresponding to a protocol encapsulation format,

said scanning comprising using said DFA to identify lexical tokens in said stream of data, said DFA including a representation of said lexical tokens,

wherein each of said network data packets is associated with the class identifier of said regular expression that matches said each network data packet.

28. The classifier of claim 27 wherein some of said regular expressions include arithmetic instructions and logic instructions, said memory assemblage further configured to contain said instructions, the classifier further including an arithmetic logic unit operatively coupled to said decompression logic and configured to execute said instructions.

29. The classifier of claim 28 further including at least one register operatively coupled to said arithmetic logic unit, said arithmetic logic unit further configured to store data into said register in response to a save instruction.

30. The classifier of claim 28 further including skip logic operatively coupled to said logic component and configured to skip over an amount of data in response a skip instruction.

31. The classifier of claim 27 wherein said network data packets can vary from one packet to another.

32. The classifier of claim 27 wherein said DFA is in compressed form.

33. The classifier of claim 32 wherein said DFA comprises plural non-default states and plural default states, and said memory assemblage comprises a base memory, a next-state memory, and a default-state memory;

said base memory configured to contain address locations of said next-state memory, said next-state memory representing all of said non-default states, said default-state memory representing all of said default states.

34. The classifier of claim 33 wherein said memories are random access memories.

35. The classifier of claim 33 wherein said memories are read-only memories.

36. A network data packet classifier comprising:

an input configured to provide a data packet comprising a stream of data;

a first system of memory configured with data representing a deterministic finite automaton (DFA), said DFA defined in accordance with a language definition comprising a set of regular expressions and produced by parsing said set of regular expressions to identify grammatical structure among said regular expressions, said DFA comprising plural states including an initial state and plural terminating states;

a system of logic circuits operatively coupled to said first system of memory and to said input, and configured to process said stream of data using said language definition in accordance with a formal language processing technique including a step to lexically scan said data stream with said DFA to produce a reached terminating state which corresponds to recognition of a lexical token; and

a second system of memory configured with data representing a class index corresponding to each of said terminating states and configured to output a class index in response to the production of said reached terminating state, said class index corresponding to a protocol encapsulation format.

37. The classifier of claim 36 further including a third system of memory configured to contain current state information for plural input channels, said system of logic circuits operatively coupled to said third system of memory to initialize said DFA in accordance with current state information corresponding to the input channel associated with said data packet.

38. The classifier of claim 36 wherein some of said states have one or more associated instructions, the classifier further including an arithmetic logic unit operatively coupled to said system of logic circuits and configured to execute said instructions.

39. The classifier of claim 38 further including at least one register operatively coupled to said arithmetic logic unit, said arithmetic logic unit further configured to store data into said register in response to a save instruction.

40. The classifier of claim 38 further including skip logic operatively coupled to said logic component and configured to skip over an amount of data in response a skip instruction.

41. The classifier of claim 36 wherein said stream of data is a stream of bytes.

42. The classifier of claim 36 wherein said data packets vary from one packet to another.

43. A network packet classifier comprising:

means for receiving an incoming network packet;

means for processing said network packet in using a language definition in accordance with a formal language processing technique including means for classifying said network packet by matching the pattern of constituent data of said network packet against plural regular expressions, each regular expression having a corresponding class identifier; and

means for outputting a class identifier of the regular expression which matches said network packet, said class identifier corresponding to a protocol encapsulation format,

said means for classifying including means for lexical token scanning to recognize one or more lexical tokens in said network packet using a deterministic finite automaton (DFA), said DFA including a representation of said one or more lexical tokens, said DFA produced by parsing said regular expressions to identify grammatical structure among said regular expressions.

44. The classifier of claim 43 wherein said means for classifying includes a memory component configured with data to represent said DFA.

45. The classifier of claim 44 wherein said means for outputting includes a second memory component configured with said class identifiers.

46. The classifier of claim 43 wherein said regular expressions include arithmetic specifiers and said means for classifying includes an arithmetic logic unit configured to perform operations in accordance with said arithmetic specifiers.

47. A network packet classifier comprising:

a dual-ported memory component;

first classification logic operatively coupled to a first port of said dual-ported memory component and having a first input for receiving a data stream; and

second classification logic operatively coupled to a second port of said dual-ported memory component and having a second input for receiving a data stream,

said memory component configured to contain a deterministic finite automaton (DFA) representative of a language definition and comprising plural states,

said DFA representing plural regular expressions of said language definition for matching data packets and produced by parsing said regular expressions to identify grammatical structure among said regular expressions,

said first and second classification logic each configured to process an associated data stream using said language definition according to a formal language processing technique including a step to scan said associated data stream using said DFA to identify data packets contained therein using said DFA to perform lexical token scanning of said data packets to produce plural lexical tokens, said DFA including a representation of said lexical tokens to classify identified data packets into one of a plurality of protocol encapsulation formats.

48. The classifier of claim 47 wherein said data packets are characterized in being variable in length.

49. The classifier of claim 47 wherein said regular expressions include arithmetic and logic operators.

50. The classifier of claim 47 wherein said regular expressions include a skip operator.