Fair weighted queuing bandwidth allocation system for network switch port

• US 6,687,781 B2
• Filed: 05/01/2001
• Issued: 02/03/2004
• Est. Priority Date: 05/01/2001
• Status: Active Grant

• Current Assignee: Microsemi Storage Solutions, Inc (Microchip Technology Incorporated)
• Original Assignee: Zettacom, Inc. (Renesas Electronics Corporation)
• Inventors: Wynne, John M., Divivier, Robert J.
• Primary Examiner(s): VO, TIM T
• Application Number:
  US09/847,078
• Publication Number:
  US 20020174279A1
• Time in Patent Office: 1,008 Days
• Field of Search: 710/29, 710/60, 710/316, 710/317, 709/231, 709/238, 709/240, 709/241, 370/229-233, 370/351-357
• US Class Current: 710/317
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/623 Weighted service order

Abstract

A traffic manager for a network switch port stores incoming cells in a cell memory and later forwards them out of the cell memory and the switch port. Each cell is assigned to one of several flow queues and each flow queue has an assigned minimum forwarding bandwidth with which cells of that flow queue must be forwarded from the cell memory and has an assigned maximum bandwidth with which cells of that flow queue may be forwarded. When any flow queue is active (i.e., when it has cells currently stored in the cell memory), the traffic manager allocates a sufficient amount of the switch port'"'"'s available cell forwarding bandwidth to each active flow queue so that cells of that flow queue are forwarded with at least the flow queue'"'"'s assigned minimum bandwidth. Each flow queue also has an assigned forwarding weight, and the traffic manager also dynamically allocates a portion of the switch port'"'"'s excess forwarding bandwidth, above that needed to accommodate each active flow queue'"'"'s minimum bandwidth, among all active flow queues in relative proportion to each active flow queue'"'"'s assigned forwarding weight. Thus the actual forwarding bandwidth allocated to each active flow queue is the sum of its assigned minimum forwarding bandwidth and its allocated portion of excess bandwidth. However the traffic manager limits the actual forwarding bandwidth allocated to any one flow queue so that it does not exceed the flow queue'"'"'s assigned maximum forwarding bandwidth.

Claims

1. A method implemented by a network switch port for receiving, storing and forwarding cells of network data transmissions, each cell being assigned to one of plurality of flow queues, wherein the switch port has a forwarding bandwidth with which it may forward cells, the method comprising the steps of:

a. separately assigning a forwarding weight to each flow queue of the plurality of flow queues;

b. receiving and storing the cells assigned to ones of the flow queues in a cell memory,

c. allocating a portion of the switch port'"'"'s forwarding bandwidth to each flow queue, wherein each flow queue'"'"'s allocated portion is a function of its assigned forwarding weight; and

d. forwarding cells assigned to each flow queue from the cell memory at a rate set in accordance with that flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth.

2. The method in accordance with claim 1 wherein each flow queue is allocated a portion of the switch port'"'"'s forwarding bandwidth only when at least one cell assigned to that flow queue resides in the cell memory.

3. The method in accordance with claim 1 wherein step c is repeated each time a cell is stored in the cell memory at step b.

4. The method in accordance with claim 1 wherein step c is repeated each time a cell is stored in the cell memory at step b and each time a cell is forwarded from the cell memory at step d.

5. The method in accordance with claim 1 wherein each flow queue'"'"'s allocated portion of the switch port'"'"'s allowable bandwidth is a function of that flow queue'"'"'s assigned forwarding weight relative to a sum of assigned forwarding rates of all flow queues having cells stored in the cell memory.

6. The method in accordance with claim 1

wherein each flow queue has associate therewith an assigned minimum forwarding bandwidth and an assigned maximum forwarding bandwidth, and

wherein the portion of the port'"'"'s forwarding bandwidth allocated to each flow queue having at least one cell stored in the cell memory comprises a lesser of the flow queue'"'"'s assigned maximum forwarding bandwidth and a sum of:

the flow queue'"'"'s assigned minimum forwarding bandwidth, and

a fraction of the switch port'"'"'s forwarding bandwidth determined in accordance with a ratio of the flow queue'"'"'s assigned forwarding weight to a sum of assigned forwarding weights of all flow queues having at least one cell stored in the cell memory.

7. The method in accordance with claim 6 wherein step c is repeated each time a cell is stored in the cell memory at step b and each time a cell is forwarded from the cell memory at step d.

8. A traffic manager for a network switch port for receiving, storing and forwarding cells of network data transmissions, each cell being assigned to one of plurality of flow queues, wherein the switch port has an forwarding bandwidth with which it may forward cells, the traffic manager comprising:

a cell memory;

first means for separately assigning a forwarding weight to each flow queue of the plurality of flow queues; and

second means for receiving and storing the cells assigned to ones of the flow queues in the cell memory, for allocating a portion of the switch port'"'"'s forwarding bandwidth to each flow queue, and for forwarding cells assigned to each flow queue from the cell memory at a rate computed in accordance with that flow queue'"'"'s allocated portion of the switch port'"'"'s allowable bandwidth, wherein the second means computes each flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth as a function of its assigned forwarding weight.

9. The traffic manager in accordance with claim 8 wherein the second means computes every flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth each time its stores a cell in the cell memory.

10. The traffic manager in accordance with claim 8 wherein the second means computes every flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth each time its forwards a cell from the cell memory.

11. The traffic manager in accordance with claim 8 wherein the second means computes every flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth each time its stores a cell in the cell memory and each time it forwards a cell from the cell memory.

12. The traffic manager in accordance with claim 8 wherein the second means computes each flow queue'"'"'s allocated portion of the switch port'"'"'s allowable bandwidth as a function of that flow queue'"'"'s assigned forwarding weight relative to a sum of assigned forwarding rates of all flow queues having cells stored in the cell memory.

13. The traffic manager in accordance with claim 8

wherein each flow queue has associated therewith an assigned minimum forwarding bandwidth and an assigned maximum forwarding bandwidth, and

wherein the second means computes an excess bandwidth of the switch port in excess of a portion of its forwarding bandwidth needed to forward cells of flow queues having at least one cell stored in the cell memory with their assigned minimum forwarding bandwidths;

wherein the second means computes the portion of the port'"'"'s forwarding bandwidth allocated to each flow queue having at least one cell stored in the cell memory as a lesser of the flow queue'"'"'s assigned maximum forwarding bandwidth and a sum of;

the flow queue'"'"'s assigned minimum forwarding bandwidth, and

a fraction of the switch port'"'"'s excess bandwidth, the fraction being determined in accordance with a ratio of the flow queue'"'"'s assigned forwarding weight to a sum of assigned forwarding weights of all flow queues having at least one cell stored in the cell memory.

14. The traffic manager in accordance with claim 13 wherein the second means computes every flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth each time it stores a cell in the cell memory and each time it forwards a cell from the cell memory.

15. The traffic manager in accordance with claim 13 wherein the second means comprises:

a first hash rate table for generating a flow queue (FQ) number referencing each flow queue for which at least one cell is stored in the cell memory at a first rate determined in accordance with the flow queue'"'"'s assigned minimum forwarding bandwidth,

a second hash table for generating the flow queue (FQ) number referencing each flow queue for which at least one cell is stored in the cell memory at a second rate determined in accordance with a difference between the flow queue'"'"'s allocated portion of the switch port'"'"'s forwarding bandwidth and the flow queue'"'"'s assigned minimum bandwidth, and

means for forwarding cells of each flow queue from the cell memory at a third rate influenced by the first and second rates at which the first and second hash rate tables generate FQ numbers referencing that flow queue.

16. The traffic manager in accordance with claim 13

wherein the second means further comprises a weighted fair queuing processor for controlling the rate at which the second hash rate table generates each FQ number,

wherein the weighted fair queuing processor computes the switch port'"'"'s excess bandwidth as a function of a rate at which cells are currently forwarded from the cell memory, and a rate at which the first hash rate table generates FQ numbers and computes the portion of the port'"'"'s forwarding bandwidth allocated to each flow queue having at least one cell stored in the cell memory.

17. A traffic manager for a network switch port, for storing and later forwarding incoming cells, wherein each incoming cell is assigned to one of a plurality of flow queues, wherein each flow queue has an assigned minimum forwarding bandwidth with which cells of that flow queue must be forwarded, wherein each flow queue also has an assigned maximum bandwidth with which cells of that flow queue may be forwarded, the traffic manager comprising:

a cell memory, and

a data path controller for storing incoming cells in the cell memory and for later forwarding each cell out of the cell memory at rate determined by input control signals, and

a queuing system for supplying the input control signals to the data path controller,

wherein when any flow queue is active in that it has cells currently stored in the cell memory the queuing system allocates each active flow queue its assigned minimum bandwidth,

wherein the queuing system assigns each flow queue a forwarding weight,

wherein the queuing system dynamically allocated allocates each active flow queue an additional forwarding bandwidth in relative proportion to its assigned forwarding weight such that each active flow queue has a total allocated forwarding bandwidth that is a sum of its assigned minimum forwarding bandwidth and its allocated additional forwarding bandwidth, and

wherein the queuing system signals the data path controller to forward cells of each active flow queue from the cell memory at a rate determined in accordance with the flow queue'"'"'s total allocated bandwidth.

18. The traffic manager in accordance with claim 17

wherein the queuing system limits the additional forwarding bandwidth it allocates to each active flow queue such that the flow queue'"'"'s total allocated forwarding bandwidth does not exceed that flow queue'"'"'s assigned maximum forwarding bandwidth.