Augmenting data plane functionality with field programmable integrated circuits

Abstract

Some embodiments use one or more FPGAs and external memories associated with the FPGAs to implement large, hash-addressable tables for a data plane circuit. These embodiments configure at least one message processing stage of the DP circuit to store (1) a first plurality of records for matching with a set of data messages received by the DP circuit, and (2) a redirection record redirecting data messages that do not match the first plurality of records to a DP egress port associated with the memory circuit. These embodiments configure an external memory circuit to store a larger, second set of records for matching with redirected data messages received through the DP egress port associated with the memory circuit. This external memory circuit is a hash-addressable memory in some embodiments. To determine whether a redirected data message matches a record in the second set of record, the method of some embodiments configures an FPGA associated with the hash-addressable external memory to use a collision free hash process to generate a collision-free, hash address value from a set of attributes of the data message. This hash address value specifies an address in the external memory for the record in the second set of records to compare with the redirected data message.

1 . An apparatus comprising:
 a switch comprising:
 multiple stage packet processing pipeline and 
 a field programmable gate array (FPGA) to perform hash table lookup, wherein different stages of the multiple stage packet processing pipeline are to access the FPGA perform table lookup. 
   
     
     
         2 . The apparatus of  claim 1 , wherein the switch comprises:
 a plurality of message processing pipelines, a memory circuit, a plurality of ingress ports, and a plurality of egress ports, at least one egress port associated with the memory circuit;   at least one message processing stage configured with (i) a first plurality of records for matching with a set of data messages received by a DP circuit, and (ii) a redirection record redirecting data messages that do not match the first plurality of records to the DP egress port associated with the memory circuit;   the memory circuit comprising a set of hash-addressable storages to store a second plurality of records to match with data messages redirected to the external memory through the DP egress port; and   a collision free hash generator to generate, from attributes of the redirected data messages, collision-free, hash-value addresses that identify, in a hash collision free manner, locations in the hash-addressable storage set of records from the second plurality of records to compare with the redirected data messages and wherein:   the set of hash-addressable storages comprises a first set of storages and a second set of storages;   the collision free hash generator is a perfect hash generator that generates, for a data message, at most two hash values, a first hash value and a second hash value;   the first hash value identifying in the first storage set a location storing a first set of values to compare to the data message's set of attributes or reference to a second storage set;   when the first set of values does not match the data message's set of attributes, the second hash value identifying in the second storage set a location storing a second set of values to compare to the data message's set of attributes.   
     
     
         3 . The apparatus of  claim 2 , wherein
 the perfect hash generator comprises first and second hash generators to generate the first and second hash values;   the first hash generator generating a same first hash value for first and second set of values stored in the first and second storage sets; and   the first set of values stored in the first storage set at the location identified by the first hash value, while the second set of values stored in the second storage set at the location identified by the second hash value.   
     
     
         4 . The apparatus of  claim 3 , wherein
 the second set of storages comprising a plurality of secondary storage sets;   the perfect hash generator comprises first hash generator and a plurality of secondary hash generators each corresponding to one of the plurality of secondary storage sets;   the first hash generator producing hash address values for the first storage set that are not collision free;   the plurality of secondary hash generator producing collision free hash address values for the secondary storage sets.   
     
     
         5 . The apparatus of  claim 4 , wherein no two set of values are stored in a particular secondary hash generator when the secondary hash generator for the particular secondary hash generator would produce a same hash address value for the two sets of values. 
     
     
         6 . The apparatus of  claim 1  further comprising a field programmable circuit that comprises the collision free hash generator. 
     
     
         7 . The apparatus of  claim 6 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is on a different integrated circuit (IC) die than the data plane circuit and the memory circuit. 
     
     
         8 . The apparatus of  claim 6 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is on a same integrated circuit (IC) die as the memory circuit but a different IC die than the data plane circuit. 
     
     
         9 . The apparatus of  claim 6 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is on a different integrated circuit (IC) chip than the data plane circuit and the memory circuit. 
     
     
         10 . The apparatus of  claim 6 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is in a same integrated circuit (IC) chip as the memory circuit but a different chip than the data plane circuit. 
     
     
         11 . A forwarding element for forwarding data messages within a network, the forwarding element comprising: 
     
     
         12 . The forwarding element of  claim 11 , wherein the circuitry comprises:
 a data plane (DP) circuit for forwarding data messages within a network, the DP circuit comprising:
 a plurality of message processing pipelines, a memory circuit, a plurality of ingress ports, and a plurality of egress ports, at least one egress port associated with the memory circuit; 
 at least one message processing stage configured with (i) a first plurality of records for matching with a set of data messages received by the DP circuit, and (ii) a redirection record redirecting data messages that do not match the first plurality of records to the DP egress port associated with the memory circuit; 
 the memory circuit comprising a set of hash-addressable storages to store a second plurality of records to match with data messages redirected to the external memory through the DP egress port; and 
   a collision free hash generator to generate, from attributes of the redirected data messages, collision-free, hash-value addresses that identify, in a hash collision free manner, locations in the hash-addressable storage set of records from the second plurality of records to compare with the redirected data messages and wherein:   the set of hash-addressable storages comprises a first set of storages and a second set of storages;   the collision free hash generator is a perfect hash generator that generates, for a data message, at most two hash values, a first hash value and a second hash value;   the first hash value identifying in the first storage set a location storing a first set of values to compare to the data message's set of attributes or reference to a second storage set;   when the first set of values does not match the data message's set of attributes, the second hash value identifying in the second storage set a location storing a second set of values to compare to the data message's set of attributes.   
     
     
         13 . The forwarding element of  claim 12 , wherein
 the perfect hash generator comprises first and second hash generators to generate the first and second hash values;   the first hash generator generating a same first hash value for first and second set of values stored in the first and second storage sets; and   the first set of values stored in the first storage set at the location identified by the first hash value, while the second set of values stored in the second storage set at the location identified by the second hash value.   
     
     
         14 . The forwarding element of  claim 13 , wherein
 the second set of storages comprising a plurality of secondary storage sets;   the perfect hash generator comprises first hash generator and a plurality of secondary hash generators each corresponding to one of the plurality of secondary storage sets;   the first hash generator producing hash address values for the first storage set that are not collision free;   the plurality of secondary hash generator producing collision free hash address values for the secondary storage sets.   
     
     
         15 . The forwarding element of  claim 14 , wherein no two set of values are stored in a particular secondary hash generator when the secondary hash generator for the particular secondary hash generator would produce a same hash address value for the two sets of values. 
     
     
         16 . The forwarding element of  claim 11  further comprising a field programmable circuit that comprises the collision free hash generator. 
     
     
         17 . The forwarding element of  claim 16 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is on a different integrated circuit (IC) die than the data plane circuit and the memory circuit. 
     
     
         18 . The forwarding element of  claim 16 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is on a same integrated circuit (IC) die as the memory circuit but a different IC die than the data plane circuit. 
     
     
         19 . The forwarding element of  claim 16 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is on a different integrated circuit (IC) chip than the data plane circuit and the memory circuit. 
     
     
         20 . The forwarding element of  claim 16 , wherein the field programmable circuit comprises a field programmable gate array (FPGA) that is in a same integrated circuit (IC) chip as the memory circuit but a different chip than the data plane circuit.