Prioritized continuous-deficit round robin scheduling

• US 6,914,881 B1
• Filed: 11/28/2000
• Issued: 07/05/2005
• Est. Priority Date: 11/28/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Cooper, Jeffrey L., Mansfield, Todd H.
• Primary Examiner(s): Phan, Man U.
• Application Number:
  US09/724,488
• Time in Patent Office: 1,680 Days
• Field of Search: 370230-236, 370250-252, 370360-395, 370412-429, 370/229, 709226-235
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/365 Dynamic adaptation of the packet size
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/623 Weighted service order

Abstract

A method and apparatus for queue selection is described below as Prioritized Continuous-Deficit Round Robin (PC-DRR) Scheduling. In PC-DRR scheduling a queue is selected as a source for the shared datapath using a modified round-robin approach, where queues are cyclically, sequentially evaluated to determine whether or not there is data stored in the queue. In PC-DRR scheduling, each queue is assigned a weight, wherein the weight corresponds to a predefined bandwidth that is allocated to the queue. Thus, the weight defines a fixed allotment of transmit opportunities that are to be allowed for the associated queue during its transmit tenure. In a preferred embodiment, a minimum permissible weight that is assigned to a queue is equal to a Maximum Packet Size. As data are drained from the queue, the weight is decreased incrementally by the amount of data sent, providing a balance. Thus the balance represents the instantaneous count of the number of output transmits that are remain for the queue within its transmit tenure. The queue continues to drain until the quantity of data transmitted is greater than the remaining balance, at which point the balance associated with the queue will become negative or zero. Once one queue is drained, or has exceeded its balance, the next sequential queue that has data to transmit is selected, where its associated weight will correspond to the number of fined transmit opportunities that are permitted for the queue.

Claims

1. A method for fairly scheduling access to a shared resource by a plurality of sources, the method comprising the steps of:

selecting a source from the plurality of sources to access the resource responsive to a predetermined order of addressing the plurality of sources, a type of data forwarded from the source and an allocation of the resource to the source, wherein data stored at each of the plurality of sources comprises one or more data items, and wherein the step of selecting further comprises;

a) examining indicators stored with each of the plurality of sources in the order to determine a next source having an indicator set to indicate presence of data at the source;

b) adding a weight indicating an allocation amount for an associated source to a shared resource and associated with the next source to a balance;

c) forwarding a data item from the next source to the shared resource until data items of the data have been forwarded;

d) for each data item that is forwarded from the next source to the shared resource, decrementing the balance;

e) responsive to the balance being greater than zero, and the indicator indicating the presence of data at the source, repeating steps c-d until the balance is less than or equal to zero.

2. The method as recited in claim 1, wherein the step of selecting is performed independent of a size of data stored at each of the plurality of sources.

3. The method according to claim 1, wherein each of the plurality of sources is associated with a predetermined type of data.

4. The method according to claim 3, where the type of the data indicates a priority of the data.

5. The method according to claim 1, wherein each of the sources is a queue.

6. An apparatus for fairly scheduling access to a shared resource by a plurality of sources, the apparatus comprising:

an indicator, for each of the sources, for indicating that the source seeks access to the resource;

a selection mechanism for selecting one source from the plurality of sources to have access to the resource responsive to the indicator for each of the sources, an order of selection of each of the sources, a type of data forwarded by each one of the plurality of sources, and independent of a size of data stored by each of the sources, wherein data associated with the one source comprises a plurality of data items, the apparatus further comprising;

a storage device to store, for each of the sources, a weight indicating an allotment of the resource to each of the sources;

a device, coupled to the storage device, for allocating transmit cycles to the one source by;

a), adding the weight associated with the one source to a balance;

b) forwarding a data item from the one source to the shared resource until-all data items of the data have been forwarded;

c) for each data item that is forwarded from the one source to the shared resource, decrementing the balance;

d) responsive to the balance being greater than zero, and the indicator indicating the presence of data at the source, repeating steps b and c until the balance is less than or equal to zero.

7. The apparatus as recited in claim 6, wherein the selection mechanism operates to select the one source independent of a size of data stored by each of the sources.

8. A network device for coupling a plurality of sources to an output port, comprising:

a plurality of allocations, each allocation associated with one of the plurality of sources, for indicating an allocation of the network device to the associated source;

a plurality of indicators, each indicator associated with one of the plurality of sources, for indicating whether the associated source has packet data to forward to the output port; and

a selection mechanism for selecting one of the plurality of sources to forward packet data to the output port in response to an order of examining the indicators, a value of each of the indicators, a type of data forwarded from each one of the plurality of sources, the plurality of allocations, wherein the selection mechanism further comprises;

a storage device to store, for each of the sources, a weight indicating a desired bandwidth allocation for that source to the output port;

a device, coupled to the storage device, for allocating transmit cycles to the one source by;

a) adding the weight associated with the one source to a balance;

b) forwarding a data item from the one source to the shared resource until all data items of the data have been forwarded;

c) for each data item that is forwarded from the one source to the shared resource, decrementing the balance;

d) responsive to the balance being greater than zero, and the indicator indicating the presence of data at the source, repeating steps b and c until the balance is less than or equal to zero.

9. The network device of claim 8, wherein the selection mechanism operates to select the one of the plurality of sources independent of a size of the packet data stored at each of the sources.