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

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.

1 - 75 . (canceled)  
   
   
       76 . A system for adaptively parsing received frames that include data units having multiple field values formatted according to at least one of a set of network protocols used in a communication network, the system comprising: 
 a memory storing information suited to resolve the at least one of the set of network protocols;    a preprocessor configured to interact with the memory to provide a type classification for a first frame and generate a layer code based upon said type classification wherein said layer code delineates selected field values in said first frame corresponding to a protocol format of a resolved one of the set of network protocols;    a dual-port memory coupled to said preprocessor and operative to concurrently receive said first frame and said layer code;    an instruction memory operatively coupled to said dual-port memory, said instruction memory storing layer offsets associated with said selected field values delineated by said layer code and at least one instruction that is selected based upon the type classification of said first frame;    a parsing engine communicatively coupled to said instruction memory and said dual-port memory in a feed-forward data flow connection and a feed-back dataflow connection, the feed-forward dataflow connection operative to provide said parsing engine with the at least one instruction and with said layer offsets for accessing the selected field values in said first frame, said parsing engine being adapted to parse said first frame according to said at least one instruction and generate an output indicative of a classification of said first frame, said feed-back dataflow connection affecting communication between said parsing engine and at least one of said instruction memory and said dual-port memory by forwarding at least a portion of said output to said instruction memory for use in refining of said at least one instruction targeted for execution on and to said dual-port memory for re-inputting to said parsing engine through said feed-forward dataflow connection.    
   
   
       77 . The system of  claim 76  wherein said feed-back dataflow connection includes an extractor coupled to said parsing engine for receiving said output and constructing search words, said search words suitable for application against a contents-addressable memory (CAM) for obtaining search results embodying information about the first frame.  
   
   
       78 . The system of  claim 76  wherein said parsing engine is coupled to one or more of a mask unit, a compare unit, a register file and a arithmetic logic unit (ALU), wherein said mask unit is configured to mask a first portion of said first frame to provide masked frame data, said compare unit is adapted to compare the at least one selected field value in said masked frame data to a predetermined value to generate at least a partial identity of the protocol format of the resolved one of the set of network protocols, said ALU is adapted to process one or more of the at least one selected field, said partial identity of said protocol format to provide updated output indicative of the classification of said first frame.  
   
   
       79 . The system of  claim 76  wherein said parsing engine is provided with a data pipe and a instruction pipe disposed in said feed-forward dataflow connection in data communication with said dual-port memory and said instruction memory respectively that maintain said first frame and said at least one instruction substantially aligned with each other.  
   
   
       80 . The system of  claim 79  wherein said data units correspond to two or more frames and arrive in an interleaved sequence with said data pipe and said instruction pipe is operative to align said data units from the first frame with said at least one instruction that is selected responsive to the type classification of said first frame.  
   
   
       81 . The system of  claim 76  wherein said at least one instruction that is selected based upon the type classification of said first frame includes a first sequence of instructions having at least one branch instruction that enables said instruction memory to select a second sequence of instructions targeted for execution by said parsing engine, said second sequence of instructions being based on at least a partial parsing of the first frame using one or more of said first sequence of instructions.  
   
   
       82 . The system of  claim 76  wherein said at least one instruction comprises instructions drawn from the group consisting of EXTRACT, MASK, NOT, AND, OR, XOR, and Range.  
   
   
       83 . A method for classifying a frame composed of data-fields formatted according to protocol layers used in a communication network, the method comprising: 
 storing predetermined data in a first memory wherein said predetermined data enables at least a partial resolution of said protocol layers;    operating a preprocessor in interactive communication with the first memory to correlate at least a portion of the predetermined data with one or more data-fields to obtain class information for the frame, said class information including indicia pointing to boundaries between said protocol layers;    concurrently transferring said data-fields and said class information to be stored in a second memory;    selectively loading an instruction memory with a sequence of program instructions for subsequent processing of said frame responsive to said data-fields and said class information;    parsing said frame by operating on said data-fields, pointed to by said indicia, using said sequence of program instructions to output a first set of search words indicative of an identification of said data-fields at a first resolution;    iteratively refining said sequence of program instructions responsive to said first set of search words and causing said refined sequence of program instructions to operate on one or more of said data-fields and said first set of search words to generate a second set of search words indicative of the identification of said data-fields at a second resolution greater than said first resolution; and    outputting said data-fields and said second set of search words when said second resolution meets predefined criteria.    
   
   
       84 . The method of  claim 83  further including aligning said data-fields with the sequence of program instructions before said program instructions operate on said data-fields.  
   
   
       85 . The method of  claim 84  wherein said data-fields include two or more sets of data-fields corresponding to two or more arriving frames with each set of data-fields embodying differing protocol layers, said step of aligning said data-fields with the sequence of program instructions including aligning said a first set of data-fields with an associated first sequence of program instructions and a second set of data-fields with an associated second sequence of program instructions.  
   
   
       86 . The method of  claim 85  wherein said step of parsing said frame includes interleaving operation of both said first sequence of program instructions on said first data-fields and said second sequence of program instructions on said second data-fields during a single time span.  
   
   
       87 . The method of  claim 83  wherein said frame ingresses at a first bit-rate and egresses at a second bit-rate that is substantially equal to said first bit-rate.  
   
   
       88 . The method of  claim 83  wherein said predefined criteria corresponds to identification of all protocol layers for said frame.  
   
   
       89 . The method of  claim 83  wherein said step of outputting said first set of search results further includes: 
 using an extractor with an output of said parsing engine to build search keys; and    applying said search keys against a contents-addressable memory (CAM) to generate said first set of search results that contain a frame classification.    
   
   
       90 . The method of  claim 83  wherein parsing said frame includes the steps of: 
 receiving predetermined data corresponding to at least one protocol layer;    extracting said frame into a plurality of bit fragments of varying length using at least one data mask;    comparing said predetermined data with at least one bit fragment to generate at least one comparison result;    storing said at least one comparison result in a first register;    concatenating said comparison results from said register to obtain a search key; and    indexing a memory using said search key to generate a classification of said frame.    
   
   
       91 . The method of  claim 90  further comprising the steps of: 
 providing a content-addressable memory (CAM);    storing a plurality of instructions for handling said frame in said CAM;    receiving said search key at said CAM and outputting a set of instructions from said stored plurality of instructions responsive to said search key; and    reparsing said frame using said outputted set of instructions.    
   
   
       92 . A method of filtering data packets in a network device, said method comprising: 
 receiving an incoming packet from a port; extracting packet fields of the incoming packet; classifying the incoming packet and generating action instructions based on values contained in the extracted packet fields; and modifying the incoming packet based on the action instructions and a predetermined criteria set for the network device.    
   
   
       93 . A data filter for data packets in a network device, said data filter comprising: 
 receiving means for receiving an incoming packet from a port; extracting means for extracting packet fields of the incoming packet; classifying means for classifying the incoming packet and generating action instructions based on values contained in the extracted packet fields; and modifying means for modifying the incoming packet based on the action instructions and a predetermined criteria set for the network device.    
   
   
       94 . A data filter as recited in  claim 93 , wherein said network device comprises one of a switch and a router and the modifying means comprises processing means for discarding the incoming packet, forwarding the incoming packet, modifying the incoming packet or modifying a forwarding control message for the incoming packet.  
   
   
       95 . A data filter as recited in  claim 93 , wherein said network device comprises a network co-processor and the classifying means comprises classifying means for classifying the incoming packet based on protocol type and data payload of the incoming packet.  
   
   
       96 . A data filter as recited in  claim 93 , wherein said network device comprises a network interface controller and the classifying means comprises classifying means for classifying the incoming packet based on one of a flow identification for packets having a particular source and a particular destination and a flow identification parameter.  
   
   
       97 . A fast flexible filter processor for data packets in a network device, said fast flexible filter processor comprising: an inspection engine, configured to receive an incoming data packet and extract selected packet fields from the incoming data packet; a classification engine communicating with the inspection engine, configured to receive the extracted selected packet fields and generate action instructions based on the values contained in the extracted packet fields; a packet processing engine communicating with the classification engine, configured to receive the action instructions and the incoming data packet, modify the incoming packet and output the modified incoming data packet.  
   
   
       98 . A network device for network communications, said network device comprising: a data port interface supporting at least one data port; a programmable interface, said programmable interface configured to communicate with a CPU or a programming source; a memory, said memory communicating with said data port interface; and a fast flexible filtering processor configured to receive packets coming into the data port interface, extract packet fields from said packets, determine action instructions from values contained in the extracted packet fields and take selective filter action based upon the action instructions and a predetermined criteria set for the network device.  
   
   
       99 . A network switch as recited in  claim 98 , wherein said fast flexible filtering processor is configured to be programmable by inputs from the CPU or the programming source through the programmable interface.  
   
   
       100 . A network switch as recited in  claim 98 , wherein said data port interface, said programmable interface, said memory, and said fast flexible filtering processor are implemented on a common semiconductor substrate.  
   
   
       101 . A network switch as recited in  claim 98 , wherein the fast flexible filtering processor filters the packets independent of the programmable interface, and therefore without communicating with the CPU or the programming source.  
   
   
       102 . A method for searching network messages for pre-defined regular expressions, the method comprising the steps of: storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM); inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time; returning an output from the CAM; and identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.  
   
   
       103 . The method of  claim 102 , further comprising: storing the pre-defined regular expressions in a memory storage device, and also storing one or more actions that are to be applied to network messages matching the respective regular expressions in the memory storage device; and operating the memory storage device in interaction with the CAM.  
   
   
       104 . The method of  claim 102 , further comprising: using as the CAM a ternary content addressable memory (TCAM); storing the pre-defined regular expressions in a random access memory (RAM); and storing one or more actions that are to be applied to network messages matching the respective regular expressions in the random access memory (RAM).  
   
   
       105 . The method of  claim 102 , further comprising: configuring a logic circuit to extract one or more selected fields from network messages and to append those selected fields to the respective network messages prior to inputting the messages to the CAM.  
   
   
       106 . A pattern matching engine apparatus for use in searching network messages for pre-defined regular expressions, comprising: a content-addressable memory (CAM) having a plurality of entries containing the pre-defined regular expressions; a decoder circuit configured to control an input to the CAM, the input including a given network message or selected portion thereof for comparison with the regular expressions contained within the CAM; and an output from the CAM, and in response to the output from the CAM, identifying an action to be applied to the given network message or portion thereof, and the CAM configured such that each network message or portion thereof input to the CAM is compared against all CAM entries at the same time, allowing high-speed pattern matching of network messages.  
   
   
       107 . The apparatus of  claim 106 , further comprising: a memory storage device to store the pre-defined regular expressions, and also to store one or more actions that are to be applied to network messages matching the respective regular expressions; and operating the memory storage device in interaction with the CAM.  
   
   
       108 . A computer readable media, comprising: said computer readable media containing instructions for execution on a processor for the practice of a method for searching network messages for pre-defined regular expressions, the method having the steps of, storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM); inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time; returning an output from the CAM; and identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.  
   
   
       109 . Electromagnetic signals propagating on a computer network, comprising: said electromagnetic signals carrying instructions for execution on a processor for the practice of a method for searching network messages for pre-defined regular expressions, the method having the steps of, storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM); inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time; returning an output from the CAM; and identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.  
   
   
       110 . A processor configured to process contents of packets passing through a connection point on a computer network, the processor comprising: (a) a buffer for receiving at least some of the contents of each packet passing through the connection point; (b) a memory containing one or more instructions of an instruction set for the state processor; (c) an arithmetic logic unit (ALU) coupled to the buffer; (d) a control block coupled to the ALU and to the instruction memory for decoding instructions; and (e) a program counter coupled to the instruction memory and to the ALU for indicating the next state processor instruction in the memory to process, wherein the ALU includes a searching apparatus comprising one or more comparators for searching for a reference string in the contents of a packet.  
   
   
       111 . In a packet switching network for relaying information in frames among nodes, a node comprising a combination of receiving means for acquiring incoming information frames including header portions designating format information, frame alteration commands for designating changes to data in a frame, and packets containing information data; alteration means responsive to said header portions for modifying information contained in said frames; and output means for relaying altered frames to another node.  
   
   
       112 . The packet switching network of  claim 111  further including offset means for determining locations of data to be transformed; pointer means for indicating locations of data passing through said node; comparator means for indicating locations from the offset means and the pointer means are equal; and means responsive to equality signals from said comparator means for controlling insertion and passage of data to the output means.  
   
   
       113 . The combination of  claim 111  further including deletion means responsive to the decoder means for inhibiting passage of data to said output means.  
   
   
       114 . The combination in  claim 111  further including storage means for storing predetermined data patterns; selection means coupled to said storage means for selecting a desired predetermined data pattern; and application means responsive to the selection means for coupling a selected predetermined data pattern to the alteration means.