Field checking based caching of ACL lookups to ease ACL lookup search
In a network element cache operation is enhanced by extracting a set of fields from a packet, constructing a hash key from the extracted fields, and identifying a subset of the fields, wherein the field values thereof fail to exist in a set of classification rules. The hash key by is modified by masking the subset of the extracted fields. A hash lookup is performed using the modified hash key in a cache memory that stores a portion of the classification rules. The packet is processed responsively to the lookup.
1. A method, comprising the steps of:
storing a plurality of classification rules
storing a hash table in a cache memory, the hash table having entries comprising rule patterns that correspond to a portion of the classification rules;
extracting a set of fields from a packet received via a data network, the fields having respective field values;
constructing a hash key from the extracted fields; and
identifying a subset of the extracted fields, wherein when the field values of the subset of the extracted fields fail to exist in the classification rules performing the steps of:
modifying the hash key by masking the subset of the extracted fields;
identifying one of the entries using the modified hash key to perform a hash lookup to the hash table; and
transmitting the packet in accordance with the classification rule that corresponds to the rule pattern of the identified entry.
2. The method according to claim 1 , wherein constructing a hash key comprises generating a concatenation of the extracted fields.
3. The method according to claim 1 , wherein constructing a hash key further comprises:
adding a bit to each of the extracted fields; and
setting the bit to a predetermined value only in the extracted fields of the subset.
4. The method according to claim 1 , wherein one of the fields and at least a portion of the classification rules comprise respective internet protocol addresses, and identifying a subset comprises finding a longest prefix match between the internet protocol address of the one field and the internet protocol address of one of the classification rules.
5. The method according to claim 4 , wherein finding a longest prefix match is performed using a ternary content addressable memory (TCAM) that returns a length of a mask that can be used for caching.
6. The method according to claim 1 , wherein identifying a subset is performed using a Bloom filter.
7. An apparatus, comprising:
a network element, operative for receiving packets via a data network;
a processor in the network element;
a main memory storing a plurality of classification rules; and
a cache memory accessible to the processor, the cache memory storing a hash table, the hash table having entries comprising rule patterns that correspond to a portion of the classification rules, wherein the processor is operative for performing the steps of:
extracting a set of fields from a packet received via the data network, the fields having respective field values;
constructing a hash key from the extracted fields; and
identifying a subset of the extracted fields, wherein when the field values of the subset of the extracted fields fail to exist in the classification rules performing the steps of:
modifying the hash key by masking the subset of the extracted fields; and
identifying one of the entries using the modified hash key to perform a hash lookup to the hash table; and
transmitting the packet from the network element in accordance with the classification rule that corresponds to the rule pattern of the identified entry.
8. The apparatus according to claim 7 , wherein constructing a hash key comprises generating a concatenation of the extracted fields.
9. The apparatus according to claim 7 , wherein constructing a hash key further comprises:
adding a bit to each of the extracted fields; and
setting the bit to a predetermined value only in the extracted fields of the subset.
10. The apparatus according to claim 7 , wherein one of the fields and at least a portion of the classification rules comprise respective internet protocol addresses, and identifying a subset comprises finding a longest prefix match between the internet protocol address of the one field and the internet protocol address of one of the classification rules.
11. The apparatus according to claim 10 , wherein finding a longest prefix match is performed using a ternary content addressable memory (TCAM) that returns a length of a mask that can be used for caching.
12. The apparatus according to claim 7 , wherein identifying a subset is performed using a Bloom filter.
13. The method according to claim 1 , wherein identifying one of the entries is by performing a single hash lookup.
14. The apparatus according to claim 7 , wherein identifying one of the entries is by performing a single hash lookup.