System and method of high volume rule engine
First Claim
1. A method of screening data packets for matching rules by a packet filter comprising a processing unit, the method performed by the packet filter comprising:
- receiving data packets, by the packet filter;
generating for each received packet, one or more first lookup keys from one or more fields of the packet;
accessing a data structure comprising a hash table using the one or more first lookup keys, wherein the hash table comprises an array of pointers, wherein entries in the array of pointers include a four byte pointer field which either has a null value indicating there are no corresponding rules or includes a pointer to a linked list, wherein the pointer comprises a data unit which indicates a memory location having absolute address values and relative offsets, wherein the linked list includes one or more records of the hash table which each include (a) a corresponding key value for verification that the packet matches the record, and (b) further handling instructions, wherein the further handling instructions includes a pointer to a rule record generated by a rule database, wherein the rule record includes a test that needs to be applied to the packet to determine whether the packet matches a rule, wherein at least some of the records in the hash table indicate a second one or more lookup keys to be used in one or more additional accesses to the data structure;
performing the further handling instructions to determine whether the packet matches the rule; and
upon the packet matching a rule, applying the matching rule to the matching packets.
3 Assignments
0 Petitions
Accused Products
Abstract
A rule engine configured with at least one hash table which summarizes the rules managed by the engine. The rule engine receives rules and automatically adjusts the hash table in order to relate to added rules and/or in order to remove cancelled rules. The adjustment may be performed while the rule engine is filtering packets, without stopping. The rules may be grouped into a plurality of rule types and for each rule type the rule engine performs one or more accesses to at least one hash table to determine whether any of the rules of that type match the packet. In some embodiments, the rule engine may automatically select the rule types responsive to a set of rules provided to the rule engine and adapt its operation to the specific rules it is currently handling, while not spending resources on checking rule types not currently used.
-
Citations
11 Claims
-
1. A method of screening data packets for matching rules by a packet filter comprising a processing unit, the method performed by the packet filter comprising:
- receiving data packets, by the packet filter;
generating for each received packet, one or more first lookup keys from one or more fields of the packet;
accessing a data structure comprising a hash table using the one or more first lookup keys, wherein the hash table comprises an array of pointers, wherein entries in the array of pointers include a four byte pointer field which either has a null value indicating there are no corresponding rules or includes a pointer to a linked list, wherein the pointer comprises a data unit which indicates a memory location having absolute address values and relative offsets, wherein the linked list includes one or more records of the hash table which each include (a) a corresponding key value for verification that the packet matches the record, and (b) further handling instructions, wherein the further handling instructions includes a pointer to a rule record generated by a rule database, wherein the rule record includes a test that needs to be applied to the packet to determine whether the packet matches a rule, wherein at least some of the records in the hash table indicate a second one or more lookup keys to be used in one or more additional accesses to the data structure;
performing the further handling instructions to determine whether the packet matches the rule; and
upon the packet matching a rule, applying the matching rule to the matching packets. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
- receiving data packets, by the packet filter;
Specification