High speed data classification system

Abstract

An optical network packet classification architecture is disclosed that addresses the packet classification requirements for OC-768 optical routers and beyond. The herein disclosed system is used for ultra-high speed packet classification of optical data at either the serial data stream level for maximum performance, or after it has been converted into parallel words of data. The presently preferred embodiment of the invention provides a system that operates in the receive path, where electronic data are provided by the optical interface to the data framer. The invention incorporates unique features into a traditional optical data framer chip and relies on a complex ASIC to permit the user to differentiate between up to 10,000 different patterns at ultra-high speeds. One purpose of the general purpose system disclosed herein is to eliminate the need for costly and power consumptive content addressable memory systems, or customer pattern specific ASICs, to perform network packet classification. The system operates on a principle of adaptive programmable randomization to permit a differentiation between the input vectors to be made. The invention dramatically reduces the processing burden required by high-speed optical routers or switches.

1 . In a network for high speed transmission of digital data, said network comprising a memory, an apparatus for rapid differentiation between input data, comprising: 
 a module comprising functional elements for each of adaptive, programmable, predictive, and sequential randomization of said digital data;    said module comprising at least one element for receiving parallel input data, at least one randomizer that is driven by said input data, wherein a final state of said at least one randomizer is used as an index into said memory to determine which if any input data pattern has been matched;    wherein input data pattern matching effects data classification.    
     
     
         2 . The apparatus of  claim 1 , wherein general probability theory is used to evaluate randomization of said input data.  
     
     
         3 . The apparatus of  claim 1 , wherein said element for predictive randomization comprises means for pre-calculating said randomization for each possible input data pattern.  
     
     
         4 . The apparatus of  claim 3 , wherein said pre-calculation is performed at a time that a new input data pattern is entered.  
     
     
         5 . The apparatus of  claim 1 , further comprising: 
 means for performing a full hardware calculation of expected randomizer outputs for each input that is applied.    
     
     
         6 . The apparatus of  claim 5 , wherein a plurality of randomizer feedback values are evaluated in real-time when a new input is applied.  
     
     
         7 . The apparatus of  claim 6 , further comprising: 
 means for storing said randomizer output values in said memory for each randomizer mapping that is being considered at a time.    
     
     
         8 . The apparatus of  claim 1 , wherein said element for high speed prediction permits a significant number of possible randomization mappings to be maintained in said memory at any time.  
     
     
         9 . The apparatus of  claim 1 , further comprising: 
 means for adjusting a possible randomization mapping after any data have been received if an existing randomization mapping is significantly less ideal than another randomization mapping that has been evaluated.    
     
     
         10 . The apparatus of  claim 1 , further comprising: 
 means for maintaining statistics on substantially all presently evaluated randomization mappings to determine a best randomization, as well as any randomization that may be no longer usable.    
     
     
         11 . The apparatus of  claim 1 , further comprising: 
 means for quickly bringing substantially all of said input data patterns back to evaluate other possible randomization patterns when a randomization is no longer usable.    
     
     
         12 . The apparatus of  claim 1 , further comprising: 
 means for implementing sequential masking operations on said input data to accomplish sequential randomization of said input data patterns.    
     
     
         13 . The apparatus of  claim 12 , further comprising: 
 means for permitting either of fixed or programmable masking of selected bit patterns within said input data.    
     
     
         14 . The apparatus of  claim 13 , wherein said masking operations permit a user to pre-program a series of masking decisions that can result in a final input data pattern match.  
     
     
         15 . The apparatus of  claim 1 , wherein said element for adaptive randomization comprises means for adjusting said randomization, over time, to handle changing input data patterns that are to be analyzed.  
     
     
         16 . An apparatus for rapid differentiation between received input data comprised of a limited number of input data bits, comprising: 
 a randomizer for providing a usable randomization pattern, for a random set of parallel inputs, based upon an effective mapping of received input data patterns to output vectors; and    means for handling a limited number of cases where two or more received input data patterns are mapped to a same output value.    
     
     
         17 . The apparatus of  claim 16 , said means for handling further comprising: 
 means for permitting a set value of multiple output cases where any of two, three, or four input data patterns map to a same output pattern;    wherein said means for permitting evaluates a number of paired, tripled, and quadrupled output vectors in determining which randomizer mapping to use, as well as to determine when a randomizer mapping should be discarded.    
     
     
         18 . The apparatus of  claim 16 , said randomizer further comprising: 
 a primary randomizer for mapping each received input data pattern to an output value;    wherein sufficient randomizer mappings are simultaneously evaluated to provide that a usable mapping is substantially always available.    
     
     
         19 . The apparatus of  claim 18 , said randomizer further comprising: 
 a secondary randomizer for differentiating between received input data patterns that have been mapped to a same output value;    wherein entries in each of multiple data input patterns are different from each other.    
     
     
         20 . The apparatus of  claim 16 , wherein for a given number of output states, a given number of input data patterns, and a given number of multiple outputs, said means for handling determines a probability that any specific randomizer maps said received input data patterns into a usable set of output states.  
     
     
         21 . A method for ultra-high speed data classification, comprising the steps of: 
 providing a data framer for framing input data;    providing a complex circuit for permitting a user to differentiate between a plurality of different patterns in said input data; and    performing parallel mode classification by providing fast classification of data that have already been stored in a memory as successive parallel words of data by performing adaptive programmable randomization.    
     
     
         22 . An apparatus for ultra-high speed data classification, comprising: 
 a data framer outputting parallel data;    an adaptive programmable randomizer; and    a complex circuit for controlling said adaptive programmable randomizer.    
     
     
         23 . The apparatus of  claim 22 , wherein said complex circuit maintains multiple input pattern mappings associated with different primary and secondary randomizer equations, determines a best randomizer selection, decides when to switch randomizer values, and determines when a randomizer value is no longer useful and an entirely new mapping should be generated.  
     
     
         24 . The apparatus of  claim 22 , wherein said complex circuit comprises any of the following: 
 a microprocessor interface for communicating to a host processor system;    a first memory interface for communicating with either of a stand alone memory or shared dual port memory, for storing data patterns to be matched;    a second memory interface for communicating with a dedicated memory that contains mappings for a plurality of primary and secondary randomizer settings; and    an interface for communicating with said data framer.    
     
     
         25 . A method for ultra-high speed data classification, comprising the steps of: 
 providing a data framer for framing received input data in parallel;    providing a complex circuit for permitting a user to differentiate between a plurality of different patterns in said input data;    said user loading input patterns into said complex circuit, said input patterns made up of a combination of data and, optionally, one or more masking steps that are performed on said input data in a potentially sequential fashion, said masking steps optionally comprising mapping a range of data values to a single mask step output and, when that mask step output is reached, executing additional programmable masking or verification;    wherein said optional one or more masking steps are responsible for enabling only those input register bits that a user is interested in examining; and    providing an equation mapper for generating a related randomizer value; 
 said equation mapper performing the step of: 
 calculating randomizer mappings for different equations simultaneously, wherein a randomizer value is calculated in a single cycle;  
 
   wherein said complex circuit adjusts adaptively to select optimal randomizer settings based on input patters and masking patterns that have been applied to said complex circuit.    
     
     
         26 . The method of  claim 25 , wherein input patterns are handled by an input manager control and state machine function where they are directed into an input register.  
     
     
         27 . The method of  claim 25 , wherein said input patterns are loaded into an external memory for use in cases where a mapping is discarded and a new mapping must be generated.  
     
     
         28 . The method of  claim 25 , further comprising the step of: 
 providing a mapper multiplexer for immediate selection between each of a plurality of possible randomizer outputs associated with each of a plurality of possible randomizer equations.    
     
     
         29 . The method of  claim 28 , further comprising the step of: 
 providing a mapper storage control and storage state machine for saving and retrieving values from a plurality of equation mapping tables.    
     
     
         30 . The method of  claim 29 , wherein said mapper storage control and storage state machine determines whether a present location pointed to by a primary randomizer value contains 0, 1, 2, 3, or 4 entries.  
     
     
         31 . The method of  claim 29 , wherein said mapper storage control and storage state machine is responsible for handling creation and destruction of multiple entries, and adjustment of multiple entry tables that dictate those entries that are used.  
     
     
         32 . The method of  claim 25 , further comprising the step of: 
 providing a masking engine for permitting a user to setup sequential masking operations.    
     
     
         33 . The method of  claim 25 , further comprising the step of: 
 providing a time accelerator for re-mapping a received randomizer value to generate a randomizer value that would have been received if zero values had been clocked into a randomizer for a fixed number of cycles after a received randomizer value was captured.    
     
     
         34 . The method of  claim 25 , further comprising the step of: 
 providing a mapper engine, statistics, and state machine for determining equations to be used, and for determining when said equations are no longer usable and need to be replaced.    
     
     
         35 . The method of  claim 34 , wherein said mapper engine, statistics, and state machine maintain statistics on all equation mappings that are maintained in a memory, selects a best mapping, and sends said to said data framer.  
     
     
         36 . A method for ultra-high speed data classification, comprising the steps of: 
 providing a data framer for framing input data;    providing a complex circuit for permitting a user to differentiate between a plurality of different patterns in said input data;    said user loading input patterns into said complex circuit, said input patterns made up of a combination of data and a plurality of masking steps that are performed on said input data in a potentially sequential fashion;    wherein said input patterns are loaded into a memory for use in cases where a mapping is discarded and a new mapping must be generated;    providing an equation mapper for generating a randomized value, said equation mapper performing the step of:    calculating randomizer values;    wherein said complex circuit adjusts adaptively to select optimal randomizer settings based on input patterns and masking patterns that have been applied to said complex circuit.    
     
     
         37 . The method of  claim 36 , wherein input patterns are handled by an input manager control and state machine function where they are directed into an input register.  
     
     
         38 . The method of  claim 36 , further comprising the step of: 
 providing a mapper multiplexer for immediate selection between each of a plurality of possible randomizer outputs associated with each of a plurality of possible randomizer equations.    
     
     
         39 . The method of  claim 36 , further comprising the step of: 
 providing a mapper storage control and storage state machine for saving and retrieving values from a plurality of equation mapping tables.    
     
     
         40 . The method of  claim 39 , wherein said mapper storage control and storage state machine determines whether a present location pointed to by a primary randomizer value contains 0, 1, 2, 3, or 4 entries.  
     
     
         41 . The method of  claim 39 , wherein said mapper storage control and storage state machine is responsible for handling creation and destruction of multiple entries, and adjustment of multiple entry tables that dictate those entries that are used.  
     
     
         42 . The method of  claim 36 , further comprising the step of: 
 providing a masking engine for permitting a user to setup sequential masking operations.    
     
     
         43 . The method of  claim 36 , further comprising the step of: 
 providing a time accelerator for re-mapping a received randomizer value to generate a randomizer value that would have been received if zero values had been clocked into a randomizer for a fixed number of cycles after a received randomizer value was captured.    
     
     
         44 . The method of  claim 36 , further comprising the step of: 
 providing a mapper engine, statistics, and state machine for determining equations to be used, and for determining when said equations are no longer usable and need to be replaced.    
     
     
         45 . The method of  claim 44 , wherein said mapper engine, statistics, and state machine maintains statistics on all equation mappings that are maintained in a memory, selects a best mapping, and sends said to said data framer.