System and method for filtering received data units
View Patent ↗A system for filtering received data units comprises a memory structure adapted to store a plurality of P tables, each table comprising a plurality of filter-keys and corresponding indices, each filter-key comprising one or more key-bits each corresponding to a filter configurable by a corresponding filter configuration value; and at least one processing element connected to the memory structure and comprising a digesting module adapted to generate the one or more key-bits of each of the filter-keys of the tables by splitting the corresponding filter configuration value into P configuration-pieces each having a number of bits, and to use each configuration-piece as a first index for setting a corresponding key-bit in the corresponding table; and a filtering module adapted to receive and split the data units into P data-pieces each having the number of bits, for each data-piece use the data-piece as a second index for reading the corresponding filter-key from the corresponding table, and generate a pass-indication key from a bitwise logical conjunction between the read filter-keys.
1. A method for filtering received data units on a system having a memory structure adapted to store a plurality of P tables, each table comprising a plurality of filter-keys and corresponding indices, each filter-key comprising one or more key-bits each corresponding to a filter configurable by a corresponding filter configuration value and at least one connected processing element, comprising:
receiving one or more filter configuration values;
splitting each of said one or more filter configuration values into P corresponding configuration-pieces, each of said P configuration-pieces having a number of bits and corresponding to one of said P tables; and
for each of said P configuration-pieces of each of said filter configuration values,
selecting said corresponding configuration-piece,
selecting said table corresponding to said configuration-piece and using a value of said configuration-piece as a first index for identifying a corresponding key-bit to be modified, and
setting said corresponding key-bit.
2. The method as claimed in claim 1 wherein
said receiving one or more filter configuration values comprises receiving a corresponding filter mask for at least one of said filters;
said splitting each of said one or more filter configuration values into P corresponding configuration-pieces comprises splitting said corresponding filter mask into P corresponding mask-pieces; and
said selecting said corresponding configuration-piece and selecting said table corresponding to said configuration-piece and using said value of said configuration-piece as said first index for identifying said corresponding key-bit to be modified comprises selecting said corresponding mask-piece and identifying each allowed bit combination for said masked configuration piece when generating said configuration-pieces and using each of said configuration-pieces as said first index for setting corresponding key-bits in said corresponding table.
3. The method as claimed in claim 1 wherein:
said receiving one or more filter configuration values comprises receiving for at least one of said one or more filter configuration values and one or more super-filter configuration values;
said splitting each of said one or more filter configuration values into P corresponding configuration-pieces comprises splitting said corresponding super-filter configuration values into P corresponding super filter configuration-pieces; and
said selecting said corresponding configuration-piece and selecting said table corresponding to said configuration-piece and using said value of said configuration-piece as said first index for identifying said corresponding key-bit to be modified comprises selecting said corresponding one or more super-filter configuration-pieces and identifying each one or more super-filter key-bits, wherein the identifying said one or more super-filter key-bits depends on said corresponding super-filter configuration value in addition to said key-bits depending on said filter configuration value for the same filter.
4. The method as claimed in claim 1 , comprising
receiving at least one data unit;
splitting said data unit into P data-pieces having said numbers of bits,
for each data-piece
using said data-piece as said second index for reading said corresponding filter-key from said corresponding table,
loading said corresponding filter-key and
updating a pass-indication key for said data unit from a bitwise logical conjunction between said corresponding filter-key and said pass-indication key.
5. The method as claimed in claim 2 wherein:
said receiving one or more filter configuration values comprises receiving for at least one of said one or more filter configuration values one or more superfilter configuration values;
said splitting each of said one or more filter configuration values into P corresponding configuration-pieces comprises splitting said corresponding superfilter configuration values into P corresponding super filter configuration-pieces; and
said selecting said corresponding configuration-piece and selecting said table corresponding to said configuration-piece and using said value of said configuration-piece as said first index for identifying said corresponding key-bit to be modified comprises selecting said corresponding one or more super-filter configuration-pieces and identifying each one or more super-filter key-bits depending on said corresponding super-filter configuration value in addition to said key-bits depending on said filter configuration value for the same filter.
6. The method as claimed in claim 2 , comprising:
receiving at least one data unit;
splitting said data unit into P data-pieces having said numbers of bits,
for each data-piece
using said data-piece as said second index for reading said corresponding filter-key from said corresponding table,
loading said corresponding filter-key, and
updating a pass-indication key for said data unit from a bitwise logical conjunction between said corresponding filter-key and said pass-indication key.
7. A system for filtering received data units, comprising:
a memory structure adapted to store a plurality of P tables, each table comprising a plurality of filter-keys and corresponding indices, each filter-key comprising one or more key-bits each corresponding to a filter configurable by a corresponding filter configuration value; and
at least one processing element connected to said memory structure and comprising:
a digesting module adapted to generate said one or more key-bits of each of said filter-keys of said tables by splitting said corresponding filter configuration value into P configuration-pieces each having a number of bits, and to use each configuration-piece as a first index for setting a corresponding key-bit in said corresponding table; and
a filtering module adapted to receive and split said data units into P data-pieces each having said number of bits, for each data-piece use said data-piece as a second index for reading said corresponding filter-key from said corresponding table, and generate a pass-indication key from a bitwise logical conjunction between said read filter-keys, wherein the at least one processing element comprising the digesting module and the filtering module is embodied in a circuit.
8. The system as claimed in claim 7 wherein at least one of said filters is a ternary filter configurable using said corresponding filter configuration value and a mask adapted to mask selected bits of said filter configuration value.
9. The system as claimed in claim 8 wherein said digesting module is adapted to use each allowed bit combination for said masked filter configuration value when generating said configuration-pieces and using each of said configuration-pieces as said first index for setting said corresponding key-bit in said corresponding table.
10. The system as claimed in claim 7 wherein said digesting module is adapted to set one or more super-filter key-bits depending on a corresponding super-filter configuration value in addition to said key-bits depending on said filter configuration value for the same filter.
11. The system as claimed in claim 7 adapted to pass said received data unit when said pass-indication key comprises at least one set bit.
12. The system as claimed in claim 7 wherein said each of said pluralities of P configuration-pieces and data-pieces comprise the same amount of bits.
13. The system as claimed in claim 7 wherein P is a power of two.
14. The system as claimed claim 7 comprising an input configured to receive said filter configuration values supplied by a user of the system.
15. The system as claimed in claim 7 comprising more than one processing elements adapted to access more than one tables and read filter-keys simultaneously.
16. The system as claimed in claim 7 wherein said system is a networking system for packet classification.
17. The system as claimed in claim 8 wherein said digesting module is adapted to set one or more super-filter key-bits depending on a corresponding super-filter configuration value in addition to said key-bits depending on said filter configuration value for the same filter.
18. The system as claimed in claim 8 adapted to pass said received data unit when said pass-indication key comprises at least one set bit.
19. The system as claimed in claim 8 wherein said each of said pluralities of P configuration-pieces and data-pieces comprise the same amount of bits.
20. A computer program product embodied as a non-transitory computer readable medium storing code portions for executing steps of a method as claimed in claim 1 when run on a programmable apparatus.