Dual Leaky Bucket Flow Control Method and System

• US 20080084824A1
• Filed: 10/09/2006
• Published: 04/10/2008
• Est. Priority Date: 10/09/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Chung, Edgar, Rao, Gopal Madhava, Chin, Ken
• Granted Patent: US 7,948,882 B2
• Time in Patent Office: Days
• US Class Current: 370/235.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/215 using token-bucket

Abstract

A method for scheduling a network resource comprises adding tokens to first and second accumulators at first and second fill rates, respectively. A number of tokens corresponding to a size of a packet is subtracted from the first accumulator and a highest priority is assigned to a queue with which the packet is associated, if a number of tokens in the first accumulator is greater than zero. The number of tokens is subtracted from the second accumulator, and a default priority assigned to the queue, if the number of tokens in the first accumulator is less than zero and a number of tokens in the second accumulator is greater than zero. The network resource is assigned for transmission of the packet from the queue using a schedule that is based on the priority assigned to the queue. The packet is transmitted using the assigned network resource.

Claims

1. A method for scheduling a network resource, comprising the steps of:

(a) adding tokens to first and second accumulators at first and second fill rates, respectively;

(b) subtracting a number of tokens corresponding to a size of a packet from the first accumulator and assigning a highest priority to a queue with which the packet is associated, if a number of tokens in the first accumulator is greater than zero;

(c) subtracting the number of tokens from the second accumulator, and assigning a default priority to the queue, if the number of tokens in the first accumulator is less than zero and a number of tokens in the second accumulator is greater than zero;

(d) assigning the network resource for transmission of the packet from the queue using a schedule that is based on the priority assigned to the queue; and

(e) transmitting the packet using the assigned network resource.

2. The method of claim 1, wherein step (c) is performed without subtracting the number of tokens from the first accumulator.

3. The method of claim 1, wherein packets from a plurality of queues are scheduled for transmission using the network resource, and steps (a), (b) and (c) are repeated for each respective queue.

4. The method of claim 3, wherein step (d) comprises:

scheduling the network resource to transmit all the packets from a first one of the queues with the highest priority before the network resource transmits packets from a second one of the queues with the default priority.

5. The method of claim 4, wherein:

two or more of the plurality of queues have respective default priorities, including a queue with a first default priority and a queue with a second default priority that is lower than the first default priority, and

step (d) comprises scheduling the network resource to transmit all the packets from the queue with the first default priority before the network resource transmits packets from the queue with the second default priority.

6. The method of claim 5, wherein two or more of the plurality of queues have the highest priority, and step (d) includes:

scheduling all the respective packets from the two or more queues having the highest priority according to a round-robin schedule before transmitting any packets from the queues having default priorities.

7. The method of claim 3, wherein two or more of the plurality of queues have the highest priority, and step (d) includes scheduling respective packets from the two or more queues having the highest priority according to a round-robin schedule.

8. The method of claim 3, further comprising scheduling the network resource to transmit packets from other ones of the plurality of queues, without scheduling the network resource to transmit further packets from the first one of the plurality of queues, if the number of tokens in the second accumulator corresponding to the first one of the plurality of queues is less than zero.

9. The method of claim 3, wherein two or more of the plurality of queues have the highest priority, and step (d) includes:

scheduling transmission of respective packets from the two or more queues having the highest priority according to a strict priority schedule.

10. The method of claim 1, wherein the network resource is one of the group consisting of a switch and a line.

11. The method of claim 1, wherein the network resource is an Ethernet switch.

12. A system for scheduling a network resource, comprising:

a first accumulator and a second accumulator, to which tokens are added at first and second fill rates, respectively; and

a storage portion containing a queue, the queue having a packet,

wherein a number of tokens corresponding to a size of the packet is subtracted from the first accumulator, and a highest priority is assigned to the queue, if a number of tokens in the first accumulator is greater than zero, and

the number of tokens is subtracted from the second accumulator, and a default priority is assigned to the queue, if the number of tokens in the first accumulator is less than zero and a number of tokens in the second accumulator is greater than zero;

a scheduler that schedules the network resource for transmission of the packet from the queue using a schedule that is based on the priority assigned to the queue.

13. The system of claim 12, wherein the number of tokens is subtracted from the second accumulator without subtracting the number of tokens from the first accumulator.

14. The system of claim 12, wherein the system includes a plurality of storage portions, each having a respective queue, and the first accumulator and the scheduler are used to schedule packets from each queue for transmission using the network resource.

15. The system of claim 14, wherein the scheduler schedules the network resource to transmit all the packets from a first one of the queues with the highest priority before the network resource transmits packets from a second one of the queues with the default priority.

16. The system of claim 12, wherein the network resource is an Ethernet switch.

17. A computer readable medium encoded with computer program code, wherein when the computer program code is executed by a processor, the processor performs a method for scheduling a network resource, comprising the steps of:

(a) adding tokens to first and second accumulators at first and second fill rates, respectively;

(b) subtracting a number of tokens corresponding to a size of a packet from the first accumulator, and assigning a highest priority to a queue with which the packet is associated, if a number of tokens in the first accumulator is greater than zero;

(c) subtracting the number of tokens from the second accumulator, and assigning a default priority to the queue, if the number of tokens in the first accumulator is less than zero and a number of tokens in the second accumulator is greater than zero;

(d) assigning the network resource for transmission of the packet from the queue using a schedule that is based on the priority assigned to the queue.

18. The computer readable medium of claim 17, wherein packets from a plurality of queues are scheduled for transmission using the network resource, and steps (a), (b) and (c) are repeated for each respective queue.

19. The method of claim 18, wherein step (d) comprises:

scheduling the network resource to transmit all the packets from a first one of the queues with the highest priority before the network resource transmits packets from a second one of the queues with the default priority.

20. The method of claim 19, wherein two or more of the plurality of queues have the highest priority, and step (d) includes scheduling respective packets from the two or more queues having the highest priority according to a round-robin schedule.