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 method performed by a device that receives streams of packet data from another device and that performs actions on said packet data, comprising:
(a) determining a hash value A and a hash value B from a flow key, 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;
(b) using the hash value A to identify a hash bucket in a hash table, wherein the hash bucket includes a plurality of hash bucket entry fields, wherein the hash value B is stored in at least one of the hash bucket entry fields of the hash bucket;
(c) performing a (Content Addressable Memory) CAM lookup operation on a content of each of the hash bucket entry fields thereby generating a CAM lookup output value for each of the hash bucket entry fields, wherein (c) involves performing a plurality of simultaneous CAM lookup operations, and wherein the CAM lookup output values generated in (c) identify which one or ones of the hash bucket entry fields store the hash value B;
(d) using the CAM lookup output values generated in (c) to identify one or more flow keys stored in a key table, wherein each identified flow key corresponds to a hash bucket entry field that stores the hash value B, and wherein each flow key stored in the key table has a corresponding lookup output information value;
(e) determining which one of the flow keys identified in (d) matches the flow key in (a); and
(f) identifying the lookup output information value that corresponds to the one matching flow key determined in (e).
2. The method of claim 1 , wherein (a) through (f) are performed by a device that performs actions on packets, wherein the lookup output information value is an action value, wherein the action value indicates one of a plurality of actions, the method further comprising:
(g) performing the one of the plurality of actions on the packet, wherein the action performed is indicated by the action value, and wherein (g) is performed by the device.
3. The method of claim 1 , wherein (a) through (f) are performed by a device that performs actions on packets, 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, the method further comprising:
(g) performing the one of the plurality of actions on the packet, wherein the action performed is indicated by the multi-bit flag bit value, and wherein (g) is performed by the device.
4. The method of claim 1 , wherein (a) through (f) are performed by a device that performs actions on packets, 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, the method further comprising:
(g) performing the one of the plurality of actions on the packet, wherein the action performed is indicated by the flag bit, and wherein (g) is performed by the device.
5. The method of claim 4 , wherein the action is to output the packet from the device without modifying the packet.
6. The method of claim 4 , wherein the action is to drop the packet.
7. The method of claim 4 , wherein the packet is a packet of a flow, and wherein the action is to transfer initial packets of the flow from a first processor of the device to a second processor of the device.
8. The method of claim 4 , 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 in (g) is to transfer the packet to the host processor for slow path processing.
9. The method of claim 1 , wherein (a) through (f) are performed by a device that processes packets, wherein the hash bucket further comprises a flag bit location, wherein a flag bit value is stored in the flag bit location, the method further comprising:
(g) using the flag bit value along with the lookup output information value identified in (f) to determine how to process the packet.
10. The method of claim 1 , wherein the hash bucket is stored in a transactional memory, and wherein the transactional memory performs the plurality of simultaneous CAM lookup operations of (c).
11. The method of claim 1 , wherein some of the hash bucket entry fields are empty and do not store hash values.
12. The method of claim 1 , wherein (a) through (f) are performed by a device, 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 method of claim 1 , wherein (a) through (f) are performed by a device, 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. A method performed by a device that receives streams of packet data from another device and that performs actions on said packet data, comprising:
(a) determining a hash value A and a hash value B from a flow key, 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;
(b) using the hash value A to identify a hash bucket in a hash table, wherein the hash bucket includes a plurality of hash bucket entry fields, wherein the hash bucket further comprises a set of flag bits for each of the hash bucket entry fields, wherein the hash value B is stored in at least one of the hash bucket entry fields of the hash bucket;
(c) performing a (Content Addressable Memory) CAM lookup operation on a content of each of the hash bucket entry fields thereby generating a CAM lookup output value for each of the hash bucket entry fields, wherein (c) involves performing a plurality of simultaneous CAM lookup operations, wherein the CAM lookup output values generated in (c) identify which one or ones of the hash bucket entry fields store the hash value B, and wherein the CAM lookup output values generated in (c) also include the flag bits for each hash bucket entry field that stores the hash value B;
(d) using the CAM lookup output values generated in (c) to identify one or more flow keys stored in a key table, wherein each identified flow key corresponds to a hash bucket entry field that stores the hash value B, and wherein each flow key stored in the key table has a corresponding lookup output information value;
(e) determining which one of the flow keys identified in (d) matches the flow key in (a);
(f) using flag bits of the CAM lookup output values generated in (c) to determine an action to perform on the packet; and
(g) performing the action determined in (f) on the packet, wherein (a) through (g) are performed by a device that performs actions on packets.
15. The method of claim 14 , wherein the hash bucket is stored in a transactional memory of the device, and wherein the transactional memory performs the plurality of simultaneous CAM lookup operations of (c).
16. The method of claim 15 , further comprising:
(h) maintaining and storing an actions table, wherein the actions table includes action values indicating actions to be performed on packets, and wherein the action performed in (g) is not determined by an action value stored in the actions table but rather is determined by the flag bits used in (f).
17. The method of claim 16 , wherein the action is to drop the packet.
18. A network appliance that receives streams of packet data from another device and that performs actions on said packet data, comprising:
a processing circuit adapted to determine a hash value A and a hash value B from a flow key, 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;
means for (a) using the hash value A to identify a hash bucket in a hash table, wherein the hash bucket includes a plurality of hash bucket entry fields,
wherein the hash bucket further comprises a set of flag bits for each of the hash bucket entry fields,
wherein the hash value B is stored in at least one of the hash bucket entry fields of the hash bucket, and
wherein the means is also for (b) performing a (Content Addressable Memory) CAM lookup operation on a content of each of the hash bucket entry fields thereby generating a CAM lookup output value for each of the hash bucket entry fields,
wherein the performing of the CAM lookup operation involves performing a plurality of simultaneous CAM lookup operations,
wherein the CAM lookup output values generated identify which one or ones of the hash bucket entry fields store the hash value B, and
wherein the CAM lookup output values generated also include the flag bits for each hash bucket entry field that stores the hash value B; and
a storage mechanism that stores at least a part of a key table,
wherein the network appliance uses the CAM lookup output values to identify one or more flow keys stored in the key table,
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, and
wherein the network appliance also identifies which one of the flow keys in the key table matches the flow key from which the hash values A and B were determined.
19. The network appliance of claim 18 , wherein the network appliance uses the flag bits of the CAM lookup output values to determine an action to perform on the packet, and wherein the network appliance then performs the action on the packet.
20. The network appliance of claim 18 , wherein the action is to transfer the packet to another processing unit of the network appliance for exception handling.
21. The network appliance of claim 18 , wherein the processing circuit includes a processor that executes instructions, wherein the means is a transactional memory, and wherein the storage mechanism is an amount of memory.