Pointer based binary search engine and method for use in network devices

A fast filter processing circuit, comprising:

• a rules table having an input and output, and configured to store rules related to a network function;
• a masks table having an input and output, and configured to store masks related to said rules;
• a pointers table having an input and output;
• a signal generator coupled to said masks table and said pointers table, and configured to generate a next mask signal;
• a multiplier coupled to the output of said masks table and to a data packet input, said multiplier configured to multiply a mask output from said masks table and a data packet input from said data packet input and to output a product of said mask and said data packet;
• a comparator coupled to the output of said rules table and the output of said multiplier, and configured to compare said product with a rule output from said rules table and to generate a comparison signal;
• a multiplexer having a plurality of data inputs and a control input, said control input coupled to an output of said comparator, said multiplexer configured to output an address signal being one of said plurality of data inputs based on said comparison signal input to said control input;
• a feedback loop coupled to the output of said multiplexer and the input of said rules table, to a first input of said comparator, to a subtractor and to an adder;
• wherein data in said pointers table defines a number of steps for a search and a starting address for said search, said subtractor subtracts a jump value from an input and outputs an address less than a current address by the jump value to a second input of said multiplexer, said adder adds said jump value to an input and outputs an address greater than a current address by the jump value to a third input of said multiplexer, and said circuit outputs said output of said rules table, such that a rule matching said data packet based on said mask is output of said circuit.

A method of filtering a packet in a network device, said network device having a data packet input port and configured to perform at least one network function, said method comprising the steps of:

• providing a masks table, a rules table and a pointers table;
• relating mask data in said masks table to rules data in said rules table with a key, one of said mask data corresponding to one or more of said rules data;
• defining pointer data in said pointers tables defining a maximum and minimum address of corresponding rule data for each of said mask data
• receiving a data packet at said data packet input port;
• multiplying said data packet with one of said mask data to produce a product;
• searching said rules table based on said product and said maximum and minimum address data for said one of said mask data for a match between said product and rules data corresponding to said one of said mask data;
• and
• outputting said match to a function within said network device in order to perform said at least one network function.

A network device comprising:

• at least one network port;
• a masks table means for containing filter information and a mask key;
• a rules table means for corresponding rules to said filter information and being related to said masks table by said mask key;
• a pointers table means for containing boundary data related to said rules for corresponding filter information;
• and
• a fast filter processor means for coupling to said mask table, to said rules table and to said pointers table, and for performing at least one binary search for at least one rule related to a data packet received by said network device at said at least one network port, said binary search being limited based on said boundary data in said pointers table.

A fast filter processing circuit, comprising:

• a rules table means having an input and output, and for storing rules related to a network function;
• a masks table means having an input and output, and for storing masks related to said rules;
• a pointers table means having an input and output;
• a signal generator means coupled to said masks table means and said pointers table means, and for generating a next mask signal;
• a multiplier means coupled to the output of said masks table means and to a data packet input means, said multiplier means for multiplying a mask output from said masks table means and a data packet input from said data packet input means and outputting a product of said mask and said data packet;
• a comparator means coupled to the output of said rules table means and the output of said multiplier means, and for comparing said product with a rule output from said rules table means and generating a comparison signal;
• a multiplexer means having a plurality of data inputs and a control input, said control input coupled to an output of said comparator means, said multiplexer for outputting an address signal being one of said plurality of data inputs based on said comparison signal input to said control input;
• a feedback loop means coupled to the output of said multiplexer means and the input of said rules table means, to a first input of said comparator means, to a subtractor means and to an adder means;
• wherein data in said pointers table means defines a number of steps for a search and a starting address for said search, said subtractor means subtracts a jump value from an input and outputs an address less than a current address by the jump value to a second input of plurality of data inputs of said multiplexer means, said adder means adds said jump value to an input and outputs an address greater than a current address by the jump value to a third input of plurality of data inputs of said multiplexer, and said circuit outputs said output of said rules table means, such that a rule matching said data packet based on said mask is output of said circuit.