Granted Patent B1

US 7,188,168 · App. 09/557,736 · Granted Mar 6, 2007

Abstract

Claims (58)

1. A method for identifying protocol encapsulation in received network data at a networking device comprising:

providing a language definition including a grammar;

receiving incoming network data; and

processing said incoming network data in accordance with a formal language processing technique using said language definition, including:

providing a deterministic finite automaton (DFA) based on a set of regular expressions;

performing lexical token scanning of said network data to produce plural lexical tokens including recognizing lexical tokens contained in said data packets using said DFA, said DFA including a representation of said lexical tokens;

parsing said network data using said grammar, said network data being organized into data packets, including parsing said lexical tokens to identify grammatical structure among said lexical tokens using said DFA to identity protocol encapsulation in said network data.

2. The method of claim 1 wherein said grammar is a grammar graph represented by said DFA.

3. In a data packet network switching device, a method for processing data packets comprising:

providing a language definition including a grammar;

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

for each data packet, processing said data packet according to a formal language processing technique using said language definition including

providing a deterministic finite automaton (DFA) based on a set of regular expressions,

lexically scanning said data packet to produce plural lexical tokens including using said DFA to recognize said lexical tokens, said DFA including a representation of said lexical tokens,

parsing said lexical tokens using said grammar to identify one or more protocol encapsulation including identifying grammatical structure among said lexical tokens using said DFA, and

processing said data packet based on said identified protocols.

4. The method of claim 3 further including compiling said grammar to produce a grammar graph.

5. The method of claim 3 further including compiling said regular expressions to produce said DFA.

6. The method of claim 5 further including incorporating said grammar graph into said DFA.

7. In a data packet receiving and forwarding device, a method for processing data packets constituting a data stream, said method comprising:

receiving a description of grammar rules in the form of a grammar packet classification language;

compiling said grammar packet classification language to produce a grammar graph;

providing a deterministic finite automaton (DFA) based on a set of regular expressions;

configuring a programmable grammatical packet classifier with said grammar graph;

processing said data stream in accordance with a formal language processing technique using said grammar packet classification language including:

performing lexical token scanning of said data stream to produce plural lexical tokens including recognizing lexical tokens contained in said data packets using said DFA, said DFA including a representation of said lexical tokens; and

parsing said data stream to identify a protocol structure in a received data packet, including parsing said lexical tokens to identify grammatical structure among said lexical tokens using said DFA to identify protocol encapsulation in said stream of data; and

processing said received data packet in accordance with said protocol structure.

8. The method of claim 7 further including:

receiving a description of classification rules in a lexical classification language;

compiling said classification language to produce said DFA; and

configuring said grammatical packet classifier with said DFA.

9. The method of claim 8 wherein said grammar graph is incorporated into said DFA.

10. The method of claim 8 wherein said regular expressions include arithmetic and logic operations.

11. The method of claim 10 wherein said regular expressions further include skip operations.

12. The method of claim 11 wherein said regular expressions further include data storage operations.

13. 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 defined by a language definition and representing a grammar graph and plural regular expressions; and

decompression logic operatively coupled to said memory assemblage and configured to process said stream of data according to a formal language processing technique using said language definition including a step of lexical token scanning to scan said stream of data with said DFA to find a matching one of said regular expressions thereby producing plural lexical tokens, said DFA including a representation of said lexical tokens,

said decompression logic further configured to parse said lexical tokens with said DFA to identify grammatical structure among said lexical tokens using said DFA to identify a protocol encapsulation in a received network data packet,

wherein processing of said network data packets depends on said protocol encapsulation.

14. The classifier of claim 13 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.

15. The classifier of claim 14 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.

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

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

18. The classifier of claim 13 wherein said DFA is in compressed form.

19. The classifier of claim 18 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.

20. The classifier of claim 19 wherein said memories are random access memories.

21. The classifier of claim 19 wherein said memories are read-only memories.

22. A network packet classifier comprising:

means for receiving an incoming network packets; and

means for identifying protocol structure in said network packets including means for processing said network packets in accordance with a formal language processing technique using a language definition, including means for scanning said network packets to match patterns in said network packets constituent data against plural regular expressions to produce lexical tokens and means for parsing through said lexical tokens using a grammar, said regular expressions and said grammar being defined by said language definition,

said means for scanning including a memory component configured with data to represent a deterministic finite automaton (DFA) based on said regular expressions, said DFA including a representation of said lexical tokens,

said means for scanning configured to recognize said lexical tokens contained in said network packet using said DFA,

said means for parsing configured to identify grammatical structure among said lexical tokens using said DFA to identify protocol encapsulation in said incoming network packet.

23. The classifier of claim 22 wherein said memory component is further configured to include said grammar.

24. The classifier of claim 22 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.

Assignments (8)