Flow key lookup involving multiple simultaneous cam operations to identify hash values in a hash bucket
A flow key is determined from an incoming packet. Two hash values A and B are then generated from the flow key. Hash value A is an index into a hash table to identify a hash bucket. Multiple simultaneous CAM lookup operations are performed on fields of the bucket to determine which ones of the fields store hash value B. For each populated field there is a corresponding entry in a key table and in other tables. The key table entry corresponding to each field that stores hash value B is checked to determine if that key table entry stores the original flow key. When the key table entry that stores the original flow key is identified, then the corresponding entries in the other tables are determined to be a “lookup output information value”. This value indicates how the packet is to be handled/forwarded by the network appliance.
1. A device, comprising:
a processor that receives a flow key and in response generates a lookup command,
a lookup engine that includes a plurality of Content Addressable Memory (CAM) lookup blocks, wherein the lookup engine can perform a plurality of simultaneous CAM lookup operations; wherein lookup engine determines a hash value A and a hash value B from the flow key, wherein the lookup engine uses the hash value A to identify a hash bucket in the hash table, wherein the hash bucket includes a plurality of hash bucket entry fields, and wherein the hash value B is stored in at least one of the hash bucket entry fields of the hash bucket, wherein each CAM lookup block simultaneously performs a CAM lookup operation on the content of a hash bucket entry field, and wherein each CAM lookup block outputs a CAM lookup output value that indicates if the content of the hash bucket entry field is the same as the hash value B;
a bus that communicates the lookup command from the processor to the lookup engine; and
a memory unit that stores a hash table, wherein the hash table includes a plurality of hash buckets, wherein CAM lookup output values identify one or more flow keys stored in a key table, wherein the key table is stored in the memory unit, wherein each identified flow key corresponds to a hash bucket entry field that stores the hash value B, wherein each flow key stored in the key table has a corresponding lookup output information value, wherein the lookup output information value is an action value, wherein the action value indicates one of a plurality of actions to be performed on the packet by the processor, wherein the device has a fast path whereby packets pass through the device without being processed by a host processor, wherein the device has a slow path whereby packets are processed by the host processor, and wherein the action is to transfer the packet to the host processor for slow path processing.
2. The device of claim 1 , wherein the flow key comprises at least a portion of an IP source address of a packet, at least a portion of an IP destination address of the packet, at least a portion of a TCP source port of the packet, and at least a portion of a TCP destination port of the packet.
3. The device of claim 2 , wherein lookup engine includes a comparator circuit, and wherein the comparator circuit determines which flow key that matches the flow key included in the lookup command and outputs the lookup output information value that corresponds to the one matching flow key determined by the comparator circuit.
4. The device of claim 3 , wherein the hash bucket further comprises a plurality of flag bit locations, wherein a multi-bit flag bit value is stored in the plurality of flag bit locations, wherein the multi-bit flag bit value indicates one of a plurality of actions.
5. The device of claim 3 , wherein the hash bucket further comprises a flag bit location, wherein a flag bit value is stored in the flag bit location, wherein the flag bit value indicates one of a plurality of actions.
6. The device of claim 3 , wherein the action is to output the packet from the device without modifying the packet.
7. The device of claim 3 , wherein the action is to drop the packet.
8. The device of claim 3 , wherein the packet is a packet of a flow, and wherein the action is to transfer initial packets of the flow from the processor of the device to a second processor of the device.
9. The device of claim 3 , wherein the hash bucket further comprises a flag bit location, wherein a flag bit value is stored in the flag bit location, and wherein the flag bit value along with the lookup output information value identified is used to determine how to process the packet.
10. The device of claim 1 , wherein the memory unit is a transactional memory.
11. The device of claim 1 , wherein some of the hash bucket entry fields are empty and do not store hash values.
12. The device of claim 2 , wherein the key table is one of a plurality of key tables, wherein the hash bucket further comprises a flag bit location, wherein a flag bit value is stored in the flag bit location, wherein the flag bit value identifies one of the plurality of key tables.
13. The device of claim 2 , wherein the key table is one of a plurality of key tables, wherein one of the key tables stores key values a first length, wherein another of the key tables stores key values of a second length, wherein the hash bucket further comprises a flag bit location, wherein a flag bit value is stored in the flag bit location, wherein the flag bit value identifies one of the plurality of key tables.
14. The device of claim 1 , wherein the bus is a Command/Push/Pull (CPP) bus, and wherein the processor is a microengine processor.
15. The device of claim 1 , wherein the device is a Island-Based Network Flow Processor (IB-NFP), wherein the processor is located on a first island within the IB-NFP, wherein the lookup engine is located in a second island within the IB-NFP, and wherein the memory unit is a transactional memory.