Pipelined Packet Switching and Queuing Architecture

• US 20080117913A1
• Filed: 10/31/2007
• Published: 05/22/2008
• Est. Priority Date: 02/21/2006
• Status: Active Grant

• Current Assignee: Cedrik Begin, Eyal Oren, Garry P. Epps, Mohammed I. Tatar, Oded Trainin
• Original Assignee: Cedrik Begin, Eyal Oren, Garry P. Epps, Mohammed I. Tatar, Oded Trainin
• Inventors: Trainin, Oded, Tatar, Mohammed I., Oren, Eyal, Begin, Cedrik, Epps, Garry P.
• Granted Patent: US 7,864,791 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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:

header processing pipeline, wherein

the header processing pipeline 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 a packet header buffer, and

the gather stage circuit is configured to

receive packet type information related to a packet type associated with the header portion from a preceding stage circuit of the plurality of pipeline stage circuits,

select a processing profile based on the Packet type information, process the header portion in accord with the processing profile to generate a modified header portion, and

output a modified header portion.

21. The apparatus for switching packets of claim 1, wherein the gather stage is further configured to:

determine whether the header portion should be re-processed; and

transmit modified header portion to the fetch stage circuit when the header portion should be re-processed.

22. The apparatus for switching packets of claim 21 wherein said determining whether the header portion should be re-processed is made when the packet is a multicast packet.

23. The apparatus for switching packets of claim 21 wherein said determining whether the header portion should be re-processed is made when the packet is a tunneling packet.

24. The apparatus for switching packets of claim 21 wherein said determining whether the header portion should be re-processed is made when the packet comprises a label requiring additional processing.

25. The apparatus for switching packets of claim 21, wherein

the header processing pipeline comprises a bus coupling the gather stage circuit to the fetch stage circuit, and

the gather stage circuit is configured to perform said sending using the bus coupling the gather stage circuit to the fetch stage circuit.

26. The apparatus for switching packets of claim 1 wherein the gather stage circuit is further configured to provide the modified header portion to a succeeding circuit configured to assemble the modified header portion to the corresponding tail portion.

2-20. -20. (canceled)

27. An apparatus for switching packets having a line card and a switch fabric, the line card comprising:

a plurality of buffer memory queues coupled to an ingress data path of the line card, wherein each buffer memory queue stores one or more ingress packets received from a corresponding network interface;

a loopback buffer memory coupled to an egress data path of the line card, wherein the loopback buffer memory stores one or more loopback packets received from the egress data path; and

a scheduler, coupled to the plurality of buffer memory queues and the loopback memory, configured to

select a selected packet from one of the plurality of buffer memory queues and the loopback buffer memory, and

provide the selected packet to a packet processor.

28. The apparatus of claim 27, wherein a loopback packet comprises:

a packet originating in the ingress data path of the line card that was sent via the switch fabric to a processor for service and subsequently returned to the egress data path of the line card.

29. The apparatus of claim 28 wherein the service comprises decryption.

30. The apparatus of claim 27 wherein the scheduler performs said selecting using fair bandwidth allocation.

31. The apparatus of claim 30 wherein said selecting using fair bandwidth allocation comprises performing deficit round robin selection from the plurality of buffer memory queues and the loopback buffer memory.

32. The apparatus of claim 27 wherein the plurality of buffer memory queues comprises:

a first high priority buffer memory queue and a first low priority buffer memory queue, wherein

the first high priority buffer memory queue and the first low priority buffer memory queue correspond to a first corresponding network interface.

33. The apparatus of claim 32 wherein the scheduler is further configured to:

perform said selecting by first selecting from the high priority buffer memory queue and then from the first low priority buffer memory queue.

34. An apparatus for switching packets having a line card and a switch fabric, the line card comprising:

an egress packet processor configured to process packets received from the switch fabric for transmission to a network interface; and

a switch fabric interface, coupled to the egress packet processor and the switch fabric, the switch fabric interface comprising

a first queue configured to store one or more unicast packet headers,

a second queue configured to store one or more multicast packet headers,

a third queue configured to store packet tail data, and

an arbiter configured to

receive information from the egress packet processor, and

select data from the first, second and third queues in response to the information received from the egress packet processor.

35. The apparatus of claim 34 wherein the information received from the egress packet processor is backpressure data.

36. The apparatus of claim 35 wherein the egress packet processor is further configured to:

provide multicast backpressure to limit a number of multicast headers concurrently processed by the egress packet processor to a pre-defined percentage of total header capacity in the egress packet processor.

37. The apparatus of claim 34 wherein the arbiter is further configured to:

perform said selecting using a packet-by-packet deficit round robin technique.

38. The apparatus of claim 37 wherein the packet-by-packet deficit round robin technique uses a quanta that is a fraction of a maximum transmission unit.

39. The apparatus of claim 34, wherein

the first queue comprises a unicast high priority queue and a unicast low priority queue for unicast packet headers,

the second queue comprises a multicast high priority queue and a multicast low priority queue for multicast packet headers, and

the arbiter is further configured to perform said selecting based upon relative priority of the queued header data.