Processor having systolic array pipeline for processing data packets

• US 7,418,536 B2
• Filed: 01/04/2006
• Issued: 08/26/2008
• Est. Priority Date: 07/30/2001
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mehrotra, Sharad, Li, Anthony, Lynch, William, Leung, Arthur Tung-Tak
• Primary Examiner(s): Phan; Raymond N
• Application Number:
  US11/326,253
• Publication Number:
  US 20060117126A1
• Time in Patent Office: 965 Days
• Field of Search: 710305-306, 710311-317, 710 36- 38, 709238-250, 708520-524, 712 18- 27, 712 10- 15
• US Class Current: 710/306
• 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 49/3009 Header conversion, routing tables or routing tags

Abstract

A processor for use in a router, the processor having a systolic array pipeline for processing data packets to determine to which output port of the router the data packet should be routed. In one embodiment, the systolic array pipeline includes a plurality of programmable functional units and register files arranged sequentially as stages, for processing packet contexts (which contain the packet'"'"'s destination address) to perform operations, under programmatic control, to determine the destination port of the router for the packet. A single stage of the systolic array may contain a register file and one or more functional units such as adders, shifters, logical units, etc., for performing, in one example, very long instruction word (vliw) operations. The processor may also include a forwarding table memory, on-chip, for storing routing information, and a cross bar selectively connecting the stages of the systolic array with the forwarding table memory.

Claims

1. A processor for use in a router receiving data packets from a network, the router having a plurality of input ports and output ports, each data packet having a header and a body, the processor comprising:

one or more input buffers for receiving data packets from the input ports of the router;

a packet buffer for storing the body of each of the data packets, wherein the packet buffer includes an input packet arbiter to examine the data packets; and

a systolic array pipeline for processing the header of each of the data packets to determine to which output port the data packets should be routed.

2. The processor of claim 1, wherein the systolic array pipeline includes a plurality of stages, and wherein a number of the plurality of stages includes at least one register file and at least one functional unit, wherein the functional unit is an adder.

3. A network processing unit for determining a destination of a packet comprising:

means for receiving data packets from input ports of the router;

means for storing the body of each of the data packets; and

means for processing a header of each of the data packets to determine to which one of an output port the data packets should be routed, wherein the means for processing comprises a systolic array pipeline with a plurality of stages capable of stroking each of the data packets, and wherein a number of the plurality of stages includes at least one register file and at least one functional unit.

4. A processor for use in a router receiving data packets from a network, the router having a plurality of input ports and output ports, each data packet having a header and a body, the processor comprising:

means for receiving data packets from the input ports of the router;

means for storing the body of each of the data packets;

means for stroking each of the data packets; and

means for processing the header of each of the data packets to determine to which output port the data packets should be routed, wherein the means for processing includes at least a first stage having a first register file and a second stage having a second register file, wherein the second register file receives an image of the first register file.

5. The processor of claim 4, wherein the means for processing includes a plurality of stages, and wherein a number of the plurality of stages includes at least one register file and at least one functional unit.

6. The processor of claim 5, wherein the at least one functional unit is an adder.

7. The processor of claim 5, wherein the at least one functional unit is a shifter.

8. A network processing unit for determining a destination of a packet, the unit comprising:

a parsing execution unit for forming a packet context which contains a destination address and descriptive data of the packet;

a lookup execution unit for determining a destination port of a router to which the packet is to be routed; and

a queuing execution unit for queuing the packet to an output queue corresponding to the destination port, wherein the parsing, lookup and queuing execution units are implemented using one or more programmable stages of a systolic array, and wherein operations of the parsing, lookup and queuing execution units are dynamically controllable.

9. A method of processing a packet, the method comprising:

extracting a header from the packet;

processing the header with a parsing execution unit to form a packet context of information relating to the packet;

determining a destination port using the packet context and a lookup execution unit, wherein the lookup execution unit comprises systolic array stages allowing programmable control;

modifying the packet context to reflect results of determining the destination port;

merging the modified packet context with the packet; and

writing to an output queue corresponding to the destination port.

10. The method of claim 9 wherein the packet context comprises a destination address contained in the packet header.

11. The method of claim 9 which comprises storing the packet while determining a destination port.

12. The method of claim 9 wherein processing the header with the parsing execution unit comprises extracting information comprising one or more of a source address, destination address, source port number, destination port number and packet type quality of service data from the header.

13. The method of claim 12 which comprises storing the extracted information in a register file.

14. The method of claim 13 wherein the lookup execution unit receives the extracted information via the register file.

15. The method of claim 9 which comprises performing quality of service and filtering operations using the lookup execution unit based upon the packet context.

16. The method of claim 9 wherein the systolic array stages include major stages and minor stages.

17. A machine-readable medium embodying instructions which, when executed by a machine cause the machine to:

extract a header from a packet;

process the header with a parsing execution unit to form a packet context of information relating to the packet;

determine a destination port using the packet context and a lookup execution unit, wherein the lookup execution unit comprises systolic array stages allowing programmable control;

modify the packet context to reflect results of determining the destination port;

merge the modified packet context with the packet; and

write to an output queue corresponding to the destination port.