Hash and Route Hardware with Parallel Routing Scheme

Abstract

A multiprocessor switching device substantially implemented on a single CMOS integrated circuit is described in connection with a parallel routing scheme for calculating routing information for incoming packets. Using the programmable hash and route routing scheme, a hash and route circuit can be programmed for a variety of applications, such as routing, flow-splitting or load balancing.

1 - 20 . (canceled) 
     
     
         21 . A multiprocessor switching chip, comprising:
 a receiver port;   a plurality of destination modules within the multiprocessor switching chip; and   a routing circuit coupled to receive a plurality of packets from the receiver port and programmably configured, for each received packet, to select a destination module for said received packet by calculating a routing signal using one or both of programmably selected control and data information extracted from the received packet as said received packet is being received, said routing circuit processing data from the received packet in parallel as each packet is received by applying a plurality of independent rules to the data from the received packet to generate a rule output from each independent rule, and combining the rule outputs to generate a routing signal for the received packet.   
     
     
         22 . The multiprocessor switching chip recited in  claim 21  wherein the routing signal is directly output as a routing result from the routing circuit to switch the received packet to a destination module identified by the routing result. 
     
     
         23 . The multiprocessor switching chip recited in  claim 21  wherein the routing signal is used as an index to a routing table to output a routing result to switch the received packet to a destination module identified by the routing result. 
     
     
         24 . The multiprocessor switching chip recited in  claim 21 , further comprising a hash circuit for hashing predetermined data from the received packet to generate a hash value, wherein the hash value and the routing signal are used to generate an index to a routing table to output a routing result to switch the received packet to a destination module. 
     
     
         25 . The multiprocessor switching chip recited in  claim 21 , further comprising an extract circuit for extracting predetermined data from the received packet to generate an extract value, wherein the extract value and the routing signal are used to generate an index to a routing table to output a routing result to switch the received packet to a destination module. 
     
     
         26 . The multiprocessor switching chip recited in  claim 21  wherein the routing circuit receives a plurality of interleaved packets on a respective plurality of input virtual channels and the routing signal is encoded in the form of an output virtual channel that is used by the multiprocessor switching chip to route packets to destination modules on the multiprocessor switching chip. 
     
     
         27 . The multiprocessor switching chip recited in  claim 23 , wherein the routing result comprises a switch hop routing signal that is used to route the received packet over a HyperTransport switch device coupled to the multiprocessor switching chip. 
     
     
         28 . The multiprocessor switching chip recited in  claim 21 , wherein the routing circuit calculates the routing signal without requiring processor intervention. 
     
     
         29 . The multiprocessor switching chip recited in  claim 21 , where the plurality of destination modules comprises a packet manager input circuit and at least one transmit circuit configured to transmit packets integrated on an integrated circuit. 
     
     
         30 . The multiprocessor switching chip recited in  claim 21 , comprising an offset circuit for specifying a location of data information in the received packet that is to be extracted by the routing circuit. 
     
     
         31 . The multiprocessor switching chip recited in  claim 21 , comprising an offset circuit for specifying a location of an offset pointer in the received packet, where said offset pointer specifies a location of data information in the received packet that is to be extracted by the routing circuit. 
     
     
         32 . The multiprocessor switching chip recited in  claim 21 , wherein each independent rule is applied to select data from the received packet and compare the selected data to an operand of the independent rule to generate a true/false result for each comparison which may be output as the rule output for the independent rule. 
     
     
         33 . The multiprocessor switching chip as recited in  claim 21 , where the routing circuit evaluates rule outputs to generate the routing signal that may be output directly as a first routing result or may be used as an index to a routing table to generate a second routing result. 
     
     
         34 . A method for routing a packet to one of a plurality of destinations in a multi-processor circuit, comprising:
 receiving at least a first packet on a receiver port of the multi-processor circuit;   decoding said first packet to extract packet data and packet control information;   calculating a routing decision for the packet data based upon programmably selected information from the packet data or packet control information while the first packet is being received;   generating a routing result based upon the routing decision by extracting and hashing a plurality of bytes from the packet data or packet control information to generate a hash value that is used to generate a routing result; and   transferring the first packet to a destination in the multi-processor circuit identified by the routing result.   
     
     
         35 . The method recited in  claim 34 , wherein an offset is determined when calculating the routing decision, where said offset defines a location in the packet data of the programmably selected information. 
     
     
         36 . The method recited in  claim 34 , wherein an offset is determined when calculating the routing decision, where said offset defines a location in the packet data of an additional offset which defines a location in the packet data of the programmably selected information. 
     
     
         37 . The method recited in  claim 34 , where generating a routing result directly identifies the destination in the multi-processor circuit for the first packet. 
     
     
         38 . The method recited in  claim 34 , where generating a routing result comprises using the routing decision to index into a routing table to output a routing result. 
     
     
         39 . The method recited in  claim 34 , where generating a routing result comprises extracting and hashing a plurality of bytes from the packet data or packet control information to generate a hash value that is used to index into a routing table to output a routing result. 
     
     
         40 . A hash and route circuit for routing packet data extracted from a packet received on an input virtual channel to an output virtual channel, comprising:
 a decoder for decoding a received packet to extract packet data and input virtual channel information for the packet; and   a routing circuit configured route the received packet to an output virtual channel by applying a plurality of programmable rules to the extracted packet data and input virtual channel information to obtain a plurality of rule outputs, and then combining the plurality of rule outputs to generate a routing signal specifying an output virtual channel for the received packet.