Hash collision avoidance in network routing

Abstract

Network device and method for routing a packet and setting up a new flow. The device includes a packet classifier, a field-selection table, a hash module, and a routing table. A packet is routed by finding an entry in the field-selection table using the packet classifier, selecting bits from the packet based on the entry in the field-selection table, and hashing the selected bits along with an identifier from the packet classifier or the field-selection table, using the hash module. The hash result is used to locate instructions in the routing table. When setting up a new flow, the hash module result may point to an existing entry in the routing table. In such instances, a new entry is added to the packet classifier, such that the hash module will produce a different result that points to an available entry in the routing table.

What is claimed is: 
     
       1. A network device, comprising:
 a packet classifier; 
 a field-selection table; 
 a hash module; 
 a routing table comprising entries each associated with a respective hash value; and 
 a routing module configured to route a packet by:
 determining an entry in the packet classifier using the packet, 
 retrieving a first identifier associated with the determined packet classifier entry, 
 choosing a first field-selection table entry using the first identifier, wherein the first field-selection table entry specifies a first set of bits, 
 generating a first hash module input by identifying values of the first set of bits of the packet specified by the chosen first field-selection table entry, 
 causing the hash module to compute a first hash result based on the first hash module input and based on the first identifier, 
 matching the first hash result to a first entry in the routing table, and 
 obtaining processing data for the packet from the first routing table entry associated, by the matching, with the first hash result; and 
 
 a maintenance module configured to resolve a collision between the first hash result associated with the first entry in the routing table and a second hash result for a new data communication flow by:
 adding, responsive to detecting the collision, a new entry to the packet classifier corresponding to the new data communication flow, wherein the new entry includes a new identifier that is different from the first identifier; 
 adding, to the field-selection table, a new field-selection table entry corresponding to the new identifier, wherein the new field-selection table entry specifies a second set of bits; 
 generating a second hash module input by identifying values of the second set of bits of a packet of the new data communication flow; 
 causing the hash module to compute a third hash result based on the second hash module input and the new identifier; and 
 adding, in association with the third hash result, an entry to the routing table comprising processing data associated with the new data communication flow. 
 
 
     
     
       2. The network device of  claim 1 , wherein the new entry added to the packet classifier matches at least one field of a packet associated with the new data communication flow. 
     
     
       3. The network device of  claim 1 , wherein the packet classifier is a ternary content addressable memory (TCAM). 
     
     
       4. The network device of  claim 3 , wherein the first identifier associated with the first packet classifier entry comprises an index in the TCAM. 
     
     
       5. The network device of  claim 1 , wherein the field-selection table comprises a table of byte-masks. 
     
     
       6. The network device of  claim 1 , wherein causing the hash module to compute the first hash result based on the first hash module input and based on the first identifier comprises causing the hash module to use the first identifier as a seed value. 
     
     
       7. The network device of  claim 1 , wherein the routing module is configured to match the first hash result to the first routing table entry by:
 deriving a routing table index from a first subset of a set of hash result bits, wherein the hash result bits are a binary representation of the hash result; 
 locating an entry in the routing table from the routing table index; 
 identifying a match data item stored in the entry; and 
 verifying that the match data item is equal to a second subset of the set of hash result bits, the second subset comprising at least one bit not in the first subset. 
 
     
     
       8. The network device of  claim 1 , wherein the first hash module input consists of the results of an application of a mask associated with the chosen first field-selection table entry to a single contiguous block of bits from the first packet, wherein the single contiguous block of bits comprises at least a portion of a header of the first packet. 
     
     
       9. The network device of  claim 1 , the maintenance module configured to detect the collision between the first hash result and the second hash result for the new data communication flow. 
     
     
       10. The network device of  claim 1 , the routing module configured to retrieve the first identifier associated with the first packet classifier entry by retrieving an index value of the first packet classifier entry. 
     
     
       11. The network device of  claim 1 , wherein the second set of bits specified in the new field-selection table entry is different from the first set of bits specified by the first field-selection table entry. 
     
     
       12. A method, comprising:
 receiving a first packet associated with a first data communication flow; 
 determining a first entry in a packet classifier using the received first packet; 
 retrieving a first identifier associated with the determined first packet classifier entry; 
 choosing a first field-selection table entry using the retrieved first identifier, wherein the first field-selection table entry specifies a first set of bits; 
 generating a first hash module input by identifying values of the first set of bits of the received first packet specified by the chosen first field-selection table entry; 
 causing a hash module to compute a first hash result based on the first hash module input and the retrieved first identifier; 
 matching the first hash result to a first entry in a routing table; 
 obtaining processing data for the first packet from the matching first routing table entry associated, by the matching, with the first hash result; 
 detecting a collision between a second hash result for a second data communication flow and the first hash result associated with the first entry in the routing table; 
 adding, responsive to detecting the collision, a new entry to the packet classifier corresponding to the second data communication flow, wherein the new entry includes a new identifier that is different from the first identifier; 
 adding, to the field-selection table, a new field-selection entry corresponding to the new identifier, wherein the new field-selection entry specifies a second set of bits; 
 generating a second hash module input by identifying values of the second set of bits of a packet of the new data communication flow; 
 causing the hash module to compute a third hash result based on the second hash module input and the new identifier; and 
 adding an entry to the routing table comprising processing data associated with the new data communication flow, the added entry associated with the third hash result. 
 
     
     
       13. The method of  claim 12 , wherein adding the new entry to the packet classifier comprises adding an entry that matches at least one field of a packet associated with the new data communication flow. 
     
     
       14. The method of  claim 12 , wherein retrieving the first identifier associated with the first packet classifier entry comprises retrieving an index value of the first packet classifier entry. 
     
     
       15. The method of  claim 12 , wherein the first hash module input consists of the results of an application of a mask associated with the chosen first field-selection table entry to a single contiguous block of bits from the received packet. 
     
     
       16. The method of  claim 12 , wherein matching the first hash result to the first routing table entry in the routing table comprises:
 deriving a routing table index from a first subset of a set of hash result bits, wherein the hash result bits are a binary representation of the hash result; 
 locating an entry in the routing table from the routing table index; 
 identifying a match data item stored in the entry; and 
 verifying that the match data item is equal to a second subset of the set of hash result bits, the second subset comprising at least one bit not in the first subset. 
 
     
     
       17. The method of  claim 12 , wherein the second set of bits specified in the new field-selection table entry is different from the first set of bits specified by the first field-selection table entry. 
     
     
       18. A non-transitory computer-readable medium storing computer-readable instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:
 receive a first packet associated with a first data communication flow; 
 determine a first entry in a packet classifier using the received first packet; 
 retrieve a first identifier associated with the determined first packet classifier entry; 
 choose a first field-selection table entry using the retrieved first identifier, wherein the first field-selection table entry specifies a first set of bits; 
 generate a first hash module input by identifying values of the first set of bits of the received first packet specified by the chosen first field-selection table entry; 
 cause a hash module to compute a first hash result based on the first hash module input and the retrieved first identifier; 
 match the first hash result to a first entry in a routing table; 
 obtain processing data for the first packet from the first routing table entry associated, by the matching, with the first hash result; 
 detect a collision between a second hash result for a second data communication flow and the first hash result associated with the first entry in the routing table; 
 add, responsive to detecting the collision, a new entry to the packet classifier corresponding to the second data communication flow, wherein the new entry includes a new identifier that is different from the first identifier; 
 add, to the field-selection table, a new field-selection entry corresponding to the new identifier, wherein the new field-selection entry specifies a second set of bits; 
 generate a second hash module input by identifying values of the second set of bits of a packet of the new data communication flow; 
 cause the hash module to compute a third hash result based on the second hash module input and the new identifier; and 
 add an entry to the routing table comprising processing data associated with the new data communication flow, the added entry associated with the third hash result. 
 
     
     
       19. The non-transitory computer-readable medium in  claim 18 , further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to add the new entry to the packet classifier by adding an entry that matches at least one field of a packet associated with the new data communication flow. 
     
     
       20. The non-transitory computer-readable medium in  claim 18 , further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to: retrieve the first identifier associated with the first packet classifier entry by retrieving an index value of the first packet classifier entry. 
     
     
       21. The non-transitory computer-readable medium in  claim 18 , wherein the first hash module input consists of results of an application of a mask associated with the chosen first field-selection table entry to a single contiguous block of bits from the received first packet. 
     
     
       22. The non-transitory computer-readable medium in  claim 18 , further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to match the first hash result to the first routing table entry in the routing table by:
 deriving a routing table index from a first subset of a set of hash result bits, wherein the hash result bits are a binary representation of the hash result; 
 locating an entry in the routing table from the routing table index; 
 identifying a match data item stored in the entry; and 
 verifying that the match data item is equal to a second subset of the set of hash result bits, the second subset comprising at least one bit not in the first subset. 
 
     
     
       23. The non-transitory computer-readable medium in  claim 18 , wherein the second set of bits specified in the new field-selection table entry is different from the first set of bits specified by the first field-selection table entry.