Hash and route hardware with parallel routing scheme

• US 20050078601A1
• Filed: 10/14/2003
• Published: 04/14/2005
• Est. Priority Date: 10/14/2003
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Moll, Laurent, Sano, Barton J., Petersen, Thomas Albert
• Granted Patent: US 7,366,092 B2
• Time in Patent Office: Days
• US Class Current: 370/218
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/109 Integrated on microchip, e.g. switch-on-chip

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.

Claims

1. A multiprocessor switching chip, comprising:

a receiver port;

a plurality of destination modules; 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 comprising

a first table containing a plurality of independent rules that process data from the received packet in parallel as each packet is received to generate a rule table output for each rule contained in the first table; and

a second table containing a plurality of paths that combine the rule table outputs from the first table to generate a routing signal for the received packet.

2. The multiprocessor switching chip recited in claim 1 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.

3. The multiprocessor switching chip recited in claim 1 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.

4. The multiprocessor switching chip recited in claim 1, 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 identified by the hash value and the routing result.

5. The multiprocessor switching chip recited in claim 1, 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 identified by the extract value and the routing result.

6. The multiprocessor switching chip recited in claim 1 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.

7. The multiprocessor switching chip recited in claim 3, wherein the routing result comprises a switch hop routing signal that is used to route the received packet over an HT switch device coupled to the multiprocessor switching chip.

8. The multiprocessor switching chip recited in claim 1, wherein the routing circuit calculates the routing signal without requiring processor intervention.

9. The multiprocessor switching chip recited in claim 1, 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.

10. The multiprocessor switching chip recited in claim 1, comprising an offset circuit for specifying a location of data information in the received packet that is to be extracted by the routing circuit.

11. The multiprocessor switching chip recited in claim 1, 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.

12. The multiprocessor switching chip recited in claim 1, wherein each rule in the first table selects data from the received packet and compares the selected data to an operand of the rule to generate a true/false result for each comparison which may be output as the rule table outputs.

13. The multiprocessor switching chip as recited in claim 1, where the second table evaluates rule table outputs from the first table using a path table to generate the routing signal that may be output directly as a first routing result or may be used as an index to the routing table to generate a second routing result.

14. A method for routing a packet to one of a plurality of destinations in a processor circuit, comprising:

receiving at least a first packet on a receiver port of the 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; and

transferring the first packet to a destination in the processor circuit identified by the routing result.

15. The method recited in claim 14, 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.

16. The method recited in claim 14, 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.

17. The method recited in claim 14, the step of generating a routing result directly identifies the destination in the processor circuit for the first packet.

18. The method recited in claim 14, where the step of generating a routing result comprises using the routing decision to index into a routing table to output a routing result.

19. The method recited in claim 14, where the step of 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.

20. 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;

a rule table comprising a plurality of programmable rules, where each rule selects at least one byte from the packet data or the input virtual channel information and compares the selected at least one byte to an operand of the rule to generate a true/false result for the rule;

a path table coupled to receive the true/false results from the rule table, said path table comprising a plurality of entries which search for selected true/false results from the rule table and output path data from a matching entry; and

a routing table,

wherein the path data from the path table may be directly output as an output virtual channel or may be used as an index to the route table which outputs an output virtual channel or may be used to select an output of a hash function as an index to the route table.