Systems for scheduling the transmission of data in a network device

• US 7,830,889 B1
• Filed: 02/06/2003
• Issued: 11/09/2010
• Est. Priority Date: 02/06/2003
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Siu, Daniel K., Lemaire, Thomas, Patnaude, Albert E. Jr.
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Haile; Feben
• Application Number:
  US10/359,215
• Time in Patent Office: 2,833 Days
• Field of Search: 370/230, 370/235, 370/395.4, 370/395.41, 370/395.42, 370/409, 370/412, 370/419, 370/229, 370/231, 370/236, 370/252, 370/389, 370/413
• US Class Current: 370/395.4
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/6275 based on priority
• CPC Class Codes: H04L 47/6295 using multiple queues, one for each individual QoS, connection, flow or priority
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

In a network device, a line card includes a first scheduler configured to perform scheduling for data units of a first type and a second scheduler that is connected in series to the first scheduler and configured to perform scheduling for data units of a second type. The schedulers may be configured in a variety of ways to achieve certain data unit flow characteristics.

Claims

1. A system for scheduling traffic, including a plurality of data units, in a network device, comprising:

a first scheduler, including a plurality of queues to store the data units, to route the data units to a second scheduler, where the first scheduler and the second scheduler are configured to operate in three different configurable modes selected from;

a first mode, in which the first scheduler determines which of a plurality of virtual channel (VC) nodes will route the data units to a corresponding one of a plurality of queues in the second scheduler, based on weights, determined via quality of service (QoS) scheduling, assigned to each of the VC nodes, and in which the second scheduler controls the routing of the data units, from the first scheduler, on a per VC basis;

a second mode, in which the first scheduler determines which of the plurality of VC nodes will route the data units directly to an output port, including a buffer, of the second scheduler; and

a third mode, in which the first scheduler includes a non-strict priority section that determines which of a plurality of virtual path (VP) nodes will route the data units to a plurality of queues in the second scheduler, based on weights, determined via quality of service (QoS) scheduling, and in which the first scheduler further includes a strict priority section that determines which of a second plurality of VP nodes will route the data units to the plurality of queues in the second scheduler, based on per-data unit strict priority; and

the second scheduler is configured to schedule the data units for transmission.

2. The system of claim 1 where the QoS scheduling includes weighted round robin scheduling.

3. The system of claim 2 where the QoS scheduling further includes per-data unit strict priority scheduling.

4. The system of claim 1 where the first scheduler and the second scheduler are formed on at least one application-specific integrated circuit.

5. The system of claim 1 where each of the first scheduler and the second scheduler includes memory.

6. The system of claim 1 where, in the first mode, each of the plurality of queues queue corresponds to one of the plurality of scheduler nodes, is associated with an upper threshold, and transmits a backpressure message to the corresponding VC node when contents of the corresponding queue exceeds the upper threshold, the backpressure message instructing the corresponding VC node to stop sending the traffic to the corresponding queue.

7. The system of claim 6 where the upper threshold is dynamically adjustable.

8. The system of claim 6 where each of the plurality of queues is associated with a lower threshold, which is different than the upper threshold, and

where each of the plurality of queues transmits a backpressure release message to the corresponding VC node when contents of the respective queue goes below the lower threshold, the backpressure release message instructing the corresponding VC node to resume sending the traffic to the corresponding queue.

9. The system of claim 1 where, in the second, the buffer is associated with an upper threshold, and transmits a backpressure message to the first scheduler when contents of the buffer exceeds the upper threshold, the backpressure message instructing the first scheduler to stop sending the traffic to the output port.

10. The system of claim 9 where the upper threshold is dynamically adjustable.

11. The system of claim 9 where each of the at least one output port is associated with a lower threshold, and

where each of the at least one output port transmits backpressure release message to the first scheduler when contents of the buffer goes below the lower threshold, the backpressure release message instructing the first scheduler to resume sending the traffic to the output port.

12. The system of claim 1 where, in the third mode, the non-strict priority section first scheduler performs weighted round robin scheduling.

13. In a network device, a line card to schedule traffic, including data units of a first type, the line card comprising:

a first scheduler to perform quality of service (QoS) scheduling of the data units of a first type and to route all of the traffic, based on the QoS scheduling, in the form of data units of a second type, to a second scheduler, connected in series to the first scheduler, to schedule the routed traffic, where the first scheduler and the second scheduler are configured to operate in one of multiple modes, where;

in a first of the multiple modes, the first scheduler includes a plurality of scheduler nodes, and the second scheduler includes a plurality of queues, where each queue corresponds to one of the plurality of scheduler nodes, each queue is associated with an upper threshold, and each queue transmits a backpressure message to the corresponding scheduler node when contents of the corresponding queue exceeds the upper threshold, the backpressure message instructing the corresponding scheduler node to stop sending the traffic to the corresponding queue,

in a second of the multiple modes, the second scheduler includes at least one output port including a buffer, the buffer being associated with an upper threshold, and the buffer transmitting a port backpressure message to the first scheduler when contents of the buffer exceeds the upper threshold, the port backpressure message instructing the first scheduler to stop sending the traffic to the output port, and

in a third of the multiple modes, the first scheduler performs weighted round robin scheduling and per-data unit strict priority scheduling, and the second scheduler performs round robin scheduling.

14. The line card of claim 13 where the first type of data units includes packets and the second type of data units includes asynchronous transfer mode (ATM) cells.

15. The line card of claim 13 where the scheduling performed by the first scheduler includes at least one of weighted round robin scheduling or per-data unit strict priority scheduling, and the scheduling performed by the second scheduler includes round robin scheduling.

16. The line card of claim 13 where each of the first scheduler and the second scheduler includes a buffer pool.

17. A method for transmitting traffic on an output link of a network device that includes a first scheduler to perform quality of service (QoS) scheduling of the traffic and to route all of the traffic, based on the QoS scheduling, to a second scheduler, the method comprising:

operating the network device in one of a plurality of user configurable modes, where

in a first of the plurality of user configurable modes, the first scheduler includes a plurality of scheduler nodes, and the second scheduler includes a plurality of queues, where each queue corresponds to one of the scheduler nodes, is associated with an upper threshold, and transmits a backpressure message to the corresponding scheduler node when a content of the corresponding queue exceeds the upper threshold, the backpressure message instructing the corresponding scheduler node to stop sending the traffic to the corresponding queue,

in a second of the plurality of user configurable modes, the second scheduler includes at least one output port including a buffer, the buffer being associated with an upper threshold, and transmits a port backpressure message to the first scheduler when a content of the buffer exceeds the upper threshold, the port backpressure message instructing the first scheduler to stop sending the traffic to the output port, and

in a third of the plurality of user configurable modes, the first scheduler performs weighted round robin scheduling and per-data unit strict priority scheduling, and the second scheduler performs round robin scheduling; and

transmitting data units on the output link based on the user configurable mode in which the network device operates.