Pipelined packet switching and queuing architecture

• US 7,715,419 B2
• Filed: 03/06/2006
• Issued: 05/11/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/368,776
• Publication Number:
  US 20070195777A1
• Time in Patent Office: 1,527 Days
• Field of Search: 370/392, 370/412, 370/229, 370/230, 370/419, 370/462
• 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 of a network interface. A high priority buffer and a low priority buffer can be assigned to each port of the network interface. The network interface can perform packet prioritization through buffer selection based on priority. High priority packets will be transmitted to an ingress packet processor before low priority packets for a given port.

Claims

1. An apparatus comprising:

a switch fabric line card comprising;

one or more network interfaces, wherein

each of the one or more network interfaces comprises one or more ports, and

each of the one or more network interfaces is configured to receive network packets from a corresponding network, and prioritize each network packet with a priority level;

a buffer memory coupled to the one or more network interfaces, wherein

the buffer memory comprises a plurality of queues configured to store the network packets, and

for each priority level, each of the one or more ports has a corresponding queue of the plurality of queues; and

a scheduler coupled to the buffer memory wherein the scheduler is configured to select a selected queue of the plurality of queues, wherein

the selected queue has a highest associated priority level of any queue comprising a stored network packet, and

the selected queue is selected due to the selected queue having the highest associated priority level, and

transmit a network packet stored in the selected queue to a packet processor of the switch fabric line card, wherein

the processor is configured to process the network packet due to the selection of the selected queue; and

a switch fabric coupled to the switch fabric line card.

2. The apparatus of claim 1 wherein the scheduler comprises:

a fair queue selection mechanism configured to

select the selected queue from queues having the same associated priority level, and

fairly allocate ingress bandwidth to the packet processor.

3. The apparatus of claim 2 wherein the fair queue selection mechanism comprises a deficit round robin selection mechanism.

4. The apparatus of claim 3 wherein the deficit round robin mechanism is configured to use an OSI Layer 2 packet length for calculation of a buffer deficit.

5. The apparatus of claim 3 wherein the deficit round robin mechanism is configured to use an OSI Layer 3 packet length for calculation of a buffer deficit.

6. The apparatus of claim 1, wherein the switch fabric line card is further configured to

monitor an amount of data stored in each of the plurality of queues, wherein

the amount of data in a queue comprises the network packets stored in that queue;

and

insert a queue threshold exceeded indication in each transmitted network packet if the amount of data stored in any of the plurality of queues exceeds a configured first threshold.

7. The apparatus of claim 6, wherein the switch fabric line card is further configured to

cease insertion of the queue threshold exceeded indication if the amount of data stored in each of the plurality of queues falls below a configured second threshold.

8. The apparatus of claim 1 wherein the scheduler is further configured to

send a first backpressure signal to the network interfaces in response to the scheduler receiving a second backpressure signal from the packet processor, wherein the second backpressure signal was sent in response to the packet processor being unable to timely process packets.

9. The apparatus of claim 1 wherein the scheduler is further configured to

send a first backpressure signal to the network interfaces based upon the fill state of the buffer memory.

10. An apparatus comprising:

a switch fabric line card comprising;

one or more network ports;

a packet processor;

means for receiving a network packet from an ingress port of the one or more ports;

means for prioritizing the network packet with a determined priority level of a plurality of priority levels;

means for storing the network packet, wherein

the means for storing is associated with both the ingress port and the determined priority level, and

for each of the plurality of priority levels, each of the one or more ports has an associated means for storing;

means for selecting a selected means for storing, wherein

the selected means for storing has a highest priority level of any associated means for storing that comprises a stored network packet, and

the selected means is selected due to the selected means having the highest associated priority level; and

means for transmitting to the packet processor a network packet stored in the selected means for storing due to the selection of the selected means; and

a switch fabric coupled to the switch fabric line card.

11. The apparatus of claim 10 wherein the means for selecting a selected means for storing further comprises a deficit round robin means for selecting.

12. The apparatus of claim 10 wherein the switch fabric line card further comprises:

means for monitoring an amount of data stored in each means for storing, wherein

the amount of data comprises the network packets stored in that means for storing;

means for determining if the amount of data stored in any of the plurality of means for storing exceeds a configured first threshold; and

means for inserting a queue threshold exceeded indication in each transmitted network packet, responsive to said means for determining.

13. The apparatus of claim 12 wherein the switch fabric line card further comprises:

means for determining if the amount of data stored in each of the plurality of means for storing falls below a configured second threshold; and

means for ceasing insertion of the queue threshold exceeded indication, responsive to said means for determining if the amount of data stored in each of the plurality of means for storing falls below the configured second threshold.

14. A method comprising:

receiving a network packet on an ingress port of a switch fabric line card, wherein a plurality of ports comprises the ingress port;

assigning a priority level to the network packet;

storing the network packet in association with an identification of the ingress port and the priority level;

selecting a selected network packet of a plurality of stored network packets, wherein

the selected network packet has a highest assigned priority level of priority levels assigned to each of the plurality of stored network packets, and

said selecting is performed due to the selected network packet having the highest assigned priority level; and

transmitting the selected network packet to a packet processor of the switch fabric line card due to said selecting, wherein

the assigning, storing, selecting, and transmitting are performed by the switch fabric line card, and

the switch fabric line card is coupled to a switch fabric.

15. The method of claim 14 wherein said selecting a selected network packet further comprises:

using a fair selection method to select the selected network packet from a subset of network packets of the plurality of network packets, wherein

the subset of network packets each have the same associated priority level.

16. The method of claim 15 wherein the fair selection mechanism is a deficit round robin method.

17. The method of claim 14 further comprising:

monitoring a stored amount of data associated with each port and priority level, wherein

the stored amount of data comprises network packets stored in association with a port and priority level;

determining if the stored amount of data stored in association with any port and priority level exceeds a configured first threshold; and

inserting a queue threshold exceeded indication in each selected network packet, in response to said determining.

18. The method of claim 17 further comprising:

determining if the stored amount of data stored in association with each port and priority level falls below a configured second threshold; and

ceasing insertion of the queue threshold exceeded indication, in response to said determining if the stored amount of data stored in association with each port and priority level falls below the configured second threshold.