Pipelined packet switching and queuing architecture

• US 7,809,009 B2
• Filed: 02/21/2006
• Issued: 10/05/2010
• Est. Priority Date: 02/21/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Trainin, Oded, Tatar, Mohammed I., Oren, Eyal, Begin, Cedrik, Epps, Garry P.
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US11/358,860
• Publication Number:
  US 20070195773A1
• Time in Patent Office: 1,687 Days
• Field of Search: 370/392, 370/389, 370/412, 370/419
• US Class Current: 370/419
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/3045 Virtual queuing
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04L 49/506 Backpressure

Abstract

An architecture for a line card in a network routing device is provided. The line card architecture provides a bi-directional interface between the routing device and a network, both receiving packets from the network and transmitting the packets to the network through one or more connecting ports. In both the receive and transmit path, packets processing and routing in a multi-stage, parallel pipeline that can operate on several packets at the same time to determine each packet'"'"'s routing destination is provided. Once a routing destination determination is made, the line card architecture provides for each received packet to be modified to contain new routing information and additional header data to facilitate packet transmission through the switching fabric. The line card architecture further provides for the use of bandwidth management techniques in order to buffer and enqueue each packet for transmission through the switching fabric to a corresponding destination port. The transmit path of the line card architecture further incorporates additional features for treatment and replication of multicast packets.

Claims

1. An apparatus for switching packets, each packet having a header portion and a corresponding tail portion, the apparatus comprising:

a plurality of packet header buffers (PHBs); and

a plurality of header processing pipelines, wherein

each of the plurality of header processing pipelines comprises a plurality of pipeline stage circuits connected in a sequence, wherein

the plurality of pipeline stage circuits comprises at least a fetch stage circuit and a gather stage circuit,

each stage circuit of the plurality of pipeline stage circuits is configured to pass data to a next circuit,

the fetch stage circuit is configured to receive the header portion and store the header portion in one of the plurality of PHBs, and

the gather stage circuit is configured to output a modified header portion,

a pipeline stage circuit of the plurality of pipeline stage circuits is configured to copy data from a first PHB of the plurality of PHBs to a second PHB of the plurality of PHBs,

each of a first plurality of the plurality of pipeline stage circuits are configured to access the first PHB, and

the plurality of header processing pipelines are configured to concurrently process header portions in each header processing pipeline.

2. The apparatus of claim 1, wherein

for each stage circuit in the pipeline except the last stage circuit, the next circuit is a next stage circuit, and

for the last stage circuit in the pipeline, the next circuit is one or more of a preceding stage circuit and a circuit external to the pipeline.

3. The apparatus of claim 1, wherein

each of the plurality of pipeline stage circuits in one of the plurality of header processing pipelines is configured to begin an operation substantially simultaneously with each other of the plurality of pipeline stages in the one of the plurality of header processing pipelines.

4. The apparatus of claim 1, wherein

each stage circuit in a header processing pipeline can modify the header portion in a PHB associated with that stage circuit.

5. The apparatus of claim 1 further comprising:

a pre-fetch module comprising

a plurality of pre-fetch header buffers,

a state machine, and

a header distribution mechanism, wherein

the state machine is configured to

separate the header portion from the corresponding tail portion upon receiving the packet,

forward the tail portion to a buffer manager interface module, and

forward the header portion to the header distribution mechanism, and

the header distribution mechanism is configured to

distribute the header portion to a selected one of the plurality of pre-fetch header buffers, and

each of the plurality of pre-fetch header buffers corresponds to one of the plurality of header processing pipelines.

6. The apparatus of claim 5 wherein the header distribution mechanism is further configured to select the selected one of the plurality of pre-fetch header buffers in a cyclic manner.

7. The apparatus of claim 5 wherein the header distribution mechanism is further configured to select the selected one of the plurality of pre-fetch header buffers by determining which of the plurality of pre-fetch header buffers is least full.

8. The apparatus of claim 5 wherein the header distribution mechanism is further configured to select the selected one of the plurality of pre-fetch header buffers by matching a packet characteristic to a characteristic associated with a pre-fetch header buffer.

9. The apparatus of claim 5 wherein the pre-fetch module further comprises:

a buffer distributor configured to

distribute the header portion to a selected one of the plurality of header processing pipelines from the selected one of the plurality of pre-fetch header buffers.

10. The apparatus of claim 9 wherein the pre-fetch module further comprises:

the buffer distributor further configured to

perform selection of the selected one of the plurality of header processing pipelines using information regarding one or more of header recycling status of a header processing pipeline, and a backpressure status.

11. The apparatus of claim 1 further comprising:

a buffer manager interface module comprising

a tail buffer configured to receive the corresponding tail portion,

a plurality of pipeline header buffers, wherein

each one of the plurality of pipeline header buffers is coupled to a corresponding one of the plurality of header processing pipelines and is configured to receive a processed header portion, and

a transmit logic module configured to output the processed header portion and the corresponding tail portion.

12. The apparatus of claim 11, wherein

the gather stage circuit is coupled to the buffer manager interface module and the fetch stage circuit.

13. The apparatus of claim 11 wherein the buffer manager interface module further comprises:

a buffer select logic module coupled to the plurality of pipeline header buffers and configured to

analyze a sequence indication associated with each processed header portion associated with each one of the plurality of pipeline header buffers, and

select a selected processed header portion, wherein

the selected processed header portion has an earliest sequence indication of each modified header portion.

14. The apparatus of claim 1, wherein

the gather stage circuit is configured to

associate a sequence indication with a processed header portion, and

provide a recycled header portion to the fetch stage circuit, wherein the recycled header portion comprises

the processed header portion, and

the sequence indication associated with the processed header portion.

15. An apparatus for switching packets, each packet having a header portion and a corresponding tail portion, the apparatus comprising:

a plurality of packet header buffers (PHBs); and

a plurality of header processing pipelines comprising

a means for fetching the header portion comprising

a means for receiving the header portion, and

a means for storing the header portion in one of the plurality of PHBs,

a plurality of sequential means for processing the header portion, and

a means for outputting a modified header portion from the header processing pipeline, wherein

the means for fetching, the plurality of sequential means for processing, and the means for outputting each comprise a means for passing data to one of a next means for fetching, means for processing, or means for outputting,

a sequential means for processing the header portion of the plurality of sequential means for processing the header portion is configured to copy data from a first PHB of the plurality of PHBs to a second PHB of the plurality of PHBs,

each of a first plurality of the plurality of sequential means for processing the header portion are configured to access the first PHB, and

the plurality of header processing pipelines are configured to concurrently process header portions in each header processing pipeline.

16. A method for switching packets comprising:

receiving a packet comprising a header portion and a corresponding tail portion; and

processing the header portion using a head processing unit, wherein

the head processing unit comprises a plurality of packet header buffers (PHBs) and a plurality of header processing pipelines further comprising a plurality of pipeline stage circuits connected in sequence and at least a fetch stage circuit and a gather stage circuit,

each of a first plurality of the plurality of pipeline stage circuits are configured to access one of the plurality of PHBs, and

said processing comprises

passing data to a next circuit in the sequence when an operation performed by each of the plurality of pipeline stage circuits is completed,

reading and storing the header portion in one of the plurality of PHBs,

wherein said reading and storing is performed by the fetch stage circuit,

copying data from a first PHB of the plurality of PHBs to a second PHB of the plurality of PHBs,

outputting a modified header portion, wherein said outputting is performed by the gather stage circuit, and

performing said processing on the header portion concurrently with processing a plurality of header portions in each of the plurality of header processing pipelines.

17. The method of claim 16 wherein said processing further comprises:

each of the plurality of pipeline stage circuits in one of the plurality of header processing pipelines beginning an operation substantially simultaneously with each other of the plurality of pipeline stages in the one of the plurality of header processing pipelines.

18. The method of claim 16 further comprising:

pre-fetch processing the packet using a pre-fetch module, wherein

the pre-fetch module comprises a plurality of pre-fetch header buffers, a state machine and a header distribution mechanism, and

said pre-fetch processing comprises

separating the header portion from the corresponding tail portion upon receiving the packet, forwarding the tail portion to a buffer manager interface module, and forwarding the header portion to a header distribution mechanism, wherein said separating, receiving and forwarding is performed by the state machine, and

distributing the header portion to a selected one of the plurality of pre-fetch header buffers, wherein

said distributing is performed by the header distribution mechanism, and

each of the plurality of pre-fetch buffers corresponds to one of the plurality of header processing pipelines.

19. The method of claim 18 wherein said pre-fetch processing further comprises:

distributing the header portion to a selected one of the plurality of header processing pipelines from the selected one of the plurality of pre-fetch header buffers.

20. The method of claim 16 further comprising:

receiving the corresponding tail portion;

storing the corresponding tail portion in a tail buffer;

receiving a processed header portion from one of the plurality of header processing pipelines and storing the processed header portion in a corresponding one of a plurality of pipeline header buffers; and

transmitting the processed header portion and the corresponding tail portion.