Pipelined packet switching and queuing architecture

• US 7,729,351 B2
• Filed: 03/01/2006
• Issued: 06/01/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/365,017
• Publication Number:
  US 20070195761A1
• Time in Patent Office: 1,553 Days
• Field of Search: 370/389, 370/390, 370/469, 370/419, 370/432
• US Class Current: 370/390
• 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. The transmit path of the line card architecture further incorporates additional features for treatment and replication of multicast packets. These features can include a recycle path coupling a gather stage circuit and a fetch stage circuit and can include sequence number logic configured to associate sequence numbers with multicast packet headers.

Claims

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

a header processing pipeline comprising 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;

an input buffer configured to receive a multicast packet header from a switch fabric interface queue;

sequence number logic configured to associate a first sequence number with the multicast packet header; and

a recycle path coupling the gather stage circuit and the fetch stage circuit, wherein the fetch stage circuit is configured to

provide the multicast packet header and first sequence number to a subsequent stage circuit in the header processing pipeline, and

the gather stage circuit is configured to

output the first sequence number and a modified multicast packet header corresponding to the multicast packet header, and

provide a multicast packet header replica to the fetch stage circuit via the recycle path, the multicast packet header replica being a replica of the multicast packet header.

2. The apparatus of claim 1, wherein:

the fetch stage circuit further comprises

a state machine configured to select an input from one of the input buffer and the recycle path,

sequence request logic coupled to the sequence number logic wherein the sequence request logic is configured to request a second sequence number to associate with the multicast packet header replica, wherein

the fetch stage circuit is further configured to provide the multicast packet header replica and the second sequence number to a subsequent stage circuit in the header processing pipeline; and

the gather stage circuit is further configured to output the second sequence number and a modified multicast packet header replica corresponding to the multicast packet header replica.

3. The apparatus of claim 2, wherein

the sequence request logic is further configured to request the second sequence number upon a determination that a recycled packet header is the multicast packet header replica.

4. The apparatus of claim 1, wherein the header processing pipeline further comprises:

a stage circuit comprising recycle logic configured to set a recycle indication if the multicast packet header should be recycled.

5. The apparatus of claim 4, wherein the stage circuit comprising recycle logic is a microsequencer coupled to an instruction memory, wherein

the instruction memory is configured to store a first set of instructions, executable by the microsequencer, configured to set a recycle bit associated with the multicast packet header in response to a determination that the multicast packet header should be recycled.

6. The apparatus of claim 4, wherein the recycle logic is further configured to analyze multicast packet header type and previous recycle information associated with the multicast packet, if any.

7. The apparatus of claim 1, further comprising:

a counter configured to count a number of multicast packet headers and recycled multicast packet headers concurrently processed by the header processing pipeline; and

backpressure logic responsive to the counter and configured to provide a backpressure signal to the switch fabric interface queue.

8. The apparatus of claim 7, further comprising:

a first configurable register; and

a second configurable register, wherein

the first configurable register is configured to store a first threshold value comprising a defined average number of multicast packet headers and multicast packet header replicas to be concurrently processed by the header processing pipeline, and

the second configurable register is configured to store a second threshold value comprising a defined peak number of multicast packet headers and multicast packet header replicas to be concurrently processed by the header processing pipeline.

9. The apparatus of claim 8, wherein the backpressure logic is further configured to:

provide no backpressure signal to the switch fabric interface queue if the counter value is less than the first threshold value;

provide a first backpressure signal to the switch fabric interface queue if the counter value is greater than the first threshold value and less than the second threshold value; and

provide a second backpressure signal to the switch fabric interface queue if the counter value is greater than the second threshold value.

10. The apparatus of claim 9, wherein:

the first backpressure signal comprises a signal to the switch fabric interface queue to supply a next multicast packet header only if there are no unicast packet headers in a queue configured to supply unicast packet headers; and

the second backpressure signal comprises a signal to the switch fabric interface queue configured to supply no multicast packet headers.

11. The apparatus of claim 1, further comprising:

a pre-fetch module, coupled to the header processing pipeline and the switch fabric interface queue, comprising;

the input buffer configured to receive the multicast packet header,

the sequence number logic,

a tail input buffer configured to receive a multicast packet tail corresponding to the multicast packet header,

identifier logic configured to associate an associated identifier with the multicast packet header and the multicast packet tail, and

wherein the pre-fetch module is configured to

output the multicast packet tail and the associated identifier, and

provide the multicast packet header, the first sequence number and the associated identifier to the header processing pipeline.

12. The apparatus of claim 11, further comprising:

an egress traffic management module, coupled to the header processing pipeline, comprising

an output tail buffer configured to receive the multicast packet tail,

one or more output header buffers configured to receive the modified multicast packet header and any modified multicast packet header replicas corresponding to the multicast packet header, and

wherein the egress traffic management module is configured to associate the multicast packet tail with each modified multicast packet header and modified multicast packet header replica having an associated identifier that matches the associated identifier of the multicast packet tail.

13. The apparatus of claim 11, further comprising:

a header processing unit comprising a first plurality of header processing pipelines, wherein

the first plurality of header processing pipelines comprises the header processing pipeline, and

the pre-fetch module further comprises

a second plurality of input buffers configured to receive multicast packet headers, and

a buffer distributor coupled to the first plurality of header processing pipelines and the second plurality of input buffers and configured to select a selected header processing pipeline of the first plurality of header processing pipelines to transfer a multicast packet header from one of the input buffers.

14. The apparatus of claim 13, wherein the pre-fetch module further comprises:

a counter configured to count a number of multicast packet headers and recycled packet headers concurrently processed by the header processing unit; and

backpressure logic responsive to the counter and configured to provide a backpressure signal to the switch fabric interface queue.

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

means for receiving a multicast packet header;

means for associating a first sequence number with the multicast packet header;

means for fetching the multicast packet header comprising means for providing the multicast packet header and the first sequence number to a subsequent one of a plurality of sequential means for processing;

means for outputting a modified multicast packet header and the first sequence number from an egress means for processing of the plurality of sequential means for processing; and

means for providing a multicast packet header replica to the means for fetching from the egress means for processing, wherein

the modified multicast packet header corresponds to the multicast packet header, and

the multicast packet header replica is a replica of the multicast packet header.

16. The apparatus of claim 15, further comprising:

the means for fetching further comprising

means for selecting from the multicast packet header and the multicast packet header replica,

means for associating a second sequence number with the multicast packet header replica, and

means for providing the recycled multicast packet header and the second sequence number to a subsequent one of the plurality of sequential means for processing; and

means for outputting a modified multicast packet header replica and the second sequence number from the egress means for processing, wherein

the modified multicast packet header replica corresponds to the recycled multicast packet header.

17. The apparatus of claim 16, wherein the means for associating a second sequence number with the multicast packet header replica further comprises:

means for requesting the second sequence number from a pre-fetch module in response to a means for determining that a multicast packet header replica is a replica of the multicast packet header.

18. The apparatus of claim 15, wherein the plurality of sequential means for processing further comprises:

means for determining that the multicast packet header should be recycled; and

said means for providing the multicast packet header replica to the means for fetching is responsive to said means for determining that the multicast packet header should be recycled.

19. The apparatus of claim 15, further comprising:

means for tracking a number of multicast packet headers and multicast packet header replicas concurrently processed by the plurality of sequential means for processing; and

means for providing a backpressure signal to a means for supplying multicast packet headers in response to the means for tracking.

20. The apparatus of claim 19, further comprising:

means for storing a first threshold value, wherein

the first threshold value comprises a defined average number of multicast headers to be concurrently processed by the plurality of sequential means for processing;

means for storing a second threshold value, wherein

the second threshold value comprises a defined peak number of multicast packet headers to be concurrently processed by the plurality of sequential means for processing; and

said means for providing a backpressure signal further comprises

means for providing a first backpressure signal if the number of multicast packet headers and multicast packet header replicas being concurrently processed by the plurality of sequential means for processing is greater than the first threshold value and less than the second threshold value, and

means for providing a second backpressure signal if the number of multicast packet headers and multicast packet header replicas being concurrently processed by the plurality of sequential means for processing is greater than the second threshold value.

21. The apparatus of claim 15, further comprising:

a pre-fetch module comprising

the means for receiving the multicast packet header,

the means for associating the first sequence number with the multicast packet header,

means for receiving a multicast packet tail corresponding to the multicast packet header,

means for associating an associated identifier with the multicast packet header and the multicast packet tail,

means for outputting the multicast packet tail and the associated identifier, and

means for providing the multicast packet header, first sequence number and the associated identifier to the means for fetching.

22. The apparatus of claim 21, further comprising:

egress traffic management means comprising

means for receiving the multicast packet tail from the pre-fetch module,

means for receiving the modified multicast packet header and any modified multicast packet header replicas corresponding to the multicast packet header, and

means for associating the multicast packet tail with the modified multicast packet header and each modified recycled multicast packet header associated with an associated identifier that matches the multicast packet tail associated identifier.

23. The apparatus of claim 21, further comprising:

a header processing unit comprising a first plurality of header processing pipelines wherein a first header processing pipeline comprises the plurality of sequential means for processing; and

the pre-fetch module further comprises

a second plurality of means for buffering multicast packet headers,

means for selecting a selected header processing pipeline of the first plurality of header processing pipelines, and

means for transferring a multicast packet header from one of second plurality of means for buffering to the selected header processing pipeline.

24. A method for switching packets comprising:

receiving a multicast packet header;

associating a first sequence number with the multicast packet header;

providing the multicast packet header and first sequence number to a first stage circuit of a header processing pipeline, wherein

the header processing pipeline comprises a plurality of pipeline stage circuits connected in sequence;

processing the multicast packet header in one or more of the stages of the header processing pipeline and generating a modified multicast packet header corresponding to the multicast packet header;

outputting the modified multicast packet header and the first sequence number; and

providing a multicast packet header replica to the first stage circuit of the header processing pipeline, wherein

the multicast packet header replica is a replica of the multicast packet header.

25. The method of claim 24, further comprising:

associating a second sequence number with the multicast packet header replica;

processing the recycled multicast packet header in one or more stages of the header processing pipeline and generating a modified multicast packet header replica corresponding to the multicast packet header replica; and

outputting the modified packet header replica and the second sequence number.

26. The method of claim 24, further comprising:

determining whether the multicast packet header should be recycled; and

performing said providing the recycled multicast packet header to the first stage circuit in response to said determining.

27. The method of claim 24, further comprising:

tracking a number of multicast packet headers and recycled multicast packet headers concurrently processed by the header processing pipeline; and

providing a backpressure signal to a queue configured to supply multicast packet headers, wherein said providing the backpressure signal is performed in response to the number of multicast packet headers and recycled multicast packet headers exceeding a threshold.

28. The method of claim 24, further comprising:

receiving a multicast packet tail corresponding to the multicast packet header;

associating an associated identifier with the multicast packet header and the multicast packet tail; and

outputting the multicast packet tail and the associated identifier.

29. The method of claim 28, further comprising:

associating the multicast packet tail with the modified multicast packet header and any modified multicast packet header replica having an associated identifier that matches the multicast packet tail associated identifier.

30. The method of claim 28, further comprising:

selecting the header processing pipeline from a plurality of header processing pipelines;

providing the associated identifier to the first stage circuit of the header processing pipeline;

outputting the associated identifier with the modified multicast packet header; and

associating the associated identifier with the multicast packet header replica.