Weighted fair queuing approximation in a network switch using weighted round robin and token bucket filter

• US 6,862,265 B1
• Filed: 04/13/2000
• Issued: 03/01/2005
• Est. Priority Date: 04/13/2000
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Appala, Syam Sundar V., Erimli, Bahadir
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Nguyen, Toan
• Application Number:
  US09/548,613
• Time in Patent Office: 1,783 Days
• Field of Search: 370/230, 370/231, 370/235, 370/395.4, 370/395.41, 370/395.42, 370/412, 370/413, 370/395.21, 370/395.3, 370/395.43, 370/429
• US Class Current: 370/235
• 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
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

An integrated network switch having multiple network switch ports for outputting data frames also includes a dequeuing system for selectively supplying a data frame for output according to a specified priority by an output switch port. The dequeuing system includes, for each network switch port, a plurality of priority queues configured for holding assigned data frames based on respective priorities assigned by switching logic. A weighted round robin scheduler supplies the assigned data frames held in the priority queues to the output switch port according to a prescribed weighted round robin scheduling. In addition, the dequeuing system uses token bucket filters for selectively passing the assigned data frames to the respective priority queues in a manner that ensures that a given data frame having a large size does not interfere with bandwidth reserved for high-priority packets requiring guaranteed quality of service. Each token bucket filter selectively passes the corresponding assigned data frame to the corresponding priority queue based on a determined availability of at least a required number of tokens corresponding to a determined size of the corresponding assigned data frame. If the token bucket filter determines an insufficient number of tokens are available relative to the required number of tokens, the token bucket filter either drops the frame or shifts the frame to a lower priority queue. Hence, weighted fair queuing can be approximated using weighted round robin scheduling without interference by large-sized data packets.

Claims

1. A method in an integrated network switch, the method comprising:

assigning a received data packet to a selected one of a plurality of priority queues for an output switch port;

determining whether the selected one priority queue has at least a required number of tokens corresponding to a determined size of the received data packet, the selected one priority queue having an available number of tokens based on outputting data packets of respective determined sizes from the corresponding selected one priority queue relative to a prescribed token regeneration rate;

selectively supplying the received data packet to the selected one priority queue based on the selected one priority queue having at least the required number of tokens; and

outputting the received data packet from the selected one priority queue, relative to the plurality of priority queues, for transmission by the output switch port based on a prescribed weighted round robin scheduling between the priority queues.

2. The method of claim 1, wherein the selectively supplying step includes selectively one of dropping the received data packet and reassigning the received data packet to a lower priority queue, based on determining that the available number of tokens of the selected one priority queue is less than the required number of tokens.

3. The method of claim 1, further comprising deducting the required number of tokens from the selected one priority queue based on the supplying of the received data packet to the selected one priority queue.

4. The method of claim 3, further comprising setting each of the priority queue to have the corresponding prescribed token regeneration rate.

5. The method of claim 4, wherein the setting step further includes setting each of the priority queues to have a corresponding maximum capacity of tokens based on a corresponding prescribed quality of service.

6. The method of claim 3, wherein the outputting step includes:

accessing the selected priority queue according to a prescribed priority sequence specified by the prescribed weighted round robin scheduling;

outputting a first corresponding number of data packets specified by the prescribed weighted round robin scheduling, including the received data packet, from the selected priority queue for transmission by the output switch port.

7. The method of claim 6, further comprising:

accessing a second of the priority queues, following the selected priority queue, according to the prescribed priority sequence; and

outputting a second corresponding prescribed number of data packets, specified by the prescribed weighted round robin scheduling, from the selected priority queue for transmission by the output switch port.

8. The method of claim 3, wherein the deducting step includes deducting the required number of tokens corresponding to a number of data bytes in the received data packet.

9. The method of claim 8, further comprising adding new tokens for the selected one priority queue based on the corresponding prescribed token regeneration rate, up to a corresponding prescribed maximum capacity of tokens.

10. An integrated network switch comprising:

a plurality of network switch ports configured for outputting data frames;

switching logic configured for selecting, for a received data frame, at least one of the network switch ports as an output switch port and assigning a priority from an available plurality of priorities; and

a dequeuing system configured for selectively supplying the received data frame to the output switch port, the dequeuing system including, for each network switch port;

(1) a plurality of priority queues configured for holding assigned data frames based on the respective priorities assigned by the switching logic,

(2) token bucket filters configured for selectively passing the assigned data frames to the respective priority queues, each token bucket filter selectively passing each corresponding assigned data frame to the corresponding priority queue based on a determined availability of at least a required number of tokens corresponding to a determined size of the corresponding assigned data frame, and

(3) a weighted round robin scheduler configured supplying the assigned data frames held in the priority queues to the output switch port according to a prescribed weighted round robin scheduling.

11. The switch of claim 10, wherein each token bucket filter selectively one of drops the corresponding assigned data frame and reassigns the received data packet to a lower priority queue, based on determining that the corresponding available number of tokens is less than the required number of tokens.

12. The switch of claim 10, wherein each token bucket filter deducts the corresponding required number of tokens based on supplying the corresponding received data packet to the corresponding priority queue.

13. The switch of claim 12, wherein each priority queue adds new tokens based on a corresponding prescribed token regeneration rate, up to a corresponding prescribed maximum capacity of tokens.

14. The switch of claim 10, wherein the weighted round robin scheduler accesses the priority queues in a prescribed priority sequence, and supplies from each accessed priority queue a corresponding number of data frames to the output switch port.