Dynamic weighted round robin queuing

• US 6,438,135 B1
• Filed: 10/21/1999
• Issued: 08/20/2002
• Est. Priority Date: 10/21/1999
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Tzeng, Shrjie
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/422,591
• Time in Patent Office: 1,034 Days
• Field of Search: 370/412, 370/455, 370/230-232, 370/392-104, 370/422-430, 370/911, 370/389, 370/13, 370/360, 710/40-44, 710/72, 710/310, 455/525, 709/249, 709/224
• US Class Current: 370/412
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• 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 for transmitting a plurality of data packets through a network. Each data packet is assigned to one of a plurality of priority queues and each priority queue has a service weight. A priority weight is assigned to each of the data packets and each priority weight has a value. Data packets are delivered from one of the priority queues until a service satisfied condition is met. The service satisfied condition is met when a combination of the values of the priority weights for each of the delivered data packets is equal to or is greater than the service weight assigned to the priority queue. A queuing switch for implementing this method is also discussed. The queuing switch includes an incoming data packet processor and a plurality of priority queues.

Claims

1. A method of transmitting a plurality of data packets through a network, comprising the steps of:

assigning each data packet to one of a plurality of priority queues, each priority queue having a numerical service weight;

assigning a priority weight to each of the data packets, each priority weight having a numerical value; and

servicing each of the priority queues in round robin order by delivering data packets from one of the priority queues and transitioning to deliver data packets from a subsequent priority queue in the round robin order when a service satisfied condition is met for the priority queue being serviced, the service satisfied condition being met when a combination of the numerical values of the priority weights for each of the data packets delivered from the priority queue being serviced is equal to or is greater than the numerical service weight assigned to the priority queue being serviced.

2. The method of transmitting data packets according to claim 1, further comprising the step of collecting statistical information regarding data packet throughput and priority queue usage.

3. The method of transmitting data packets according to claim 1, wherein the service satisfied condition is met if no data packets are currently assigned to the one of the priority queues.

4. The method of transmitting data packets according to claim 1, further comprising the step of changing the priority queue assignment of an incoming data packet.

5. The method of transmitting data packets according to claim 1, further comprising the step of changing the priority weight of an incoming data packet.

6. The method of transmitting data packets according to claim 1, further comprising the step of changing the service weight of one of the priority queues.

7. The method of transmitting data packets according to claim 1, wherein data packets are delivered from each queue on a first-in-first-out basis.

8. A queuing switch, comprising:

an incoming data packet processor, the incoming data packet processor deriving a queue assignment for each of a plurality of incoming data packets and assigning a numerical priority weight to each data packet;

a plurality of priority queues, each priority queue having a numerical service weight, wherein the incoming data packet processor directs each data packet to one of the priority queues based on the queue assignment for each data packet; and

an outgoing data packet processor, the outgoing data packet processor servicing each priority queue in round robin order by delivering data packets from each of the priority queues towards a receiving device, the outgoing data packet processor transitioning from one priority queue to a subsequent priority queue in the round robin order when a service satisfied condition is met for the priority queue being serviced, the service satisfied condition being met when a combination of the numerical values of the priority weights for each of the data packets delivered from the priority queue being serviced is equal to or is greater than the numerical service weight assigned to the priority queue being serviced.

9. The queuing switch according to claim 8, wherein the outgoing data packet processor combines the priority weights of each of the sent data packets.

10. The queuing switch according to claim 8, further comprising a counter, the counter collecting statistical information regarding data packet throughput and priority queue usage.

11. The queuing switch according to claim 8, wherein the service satisfied condition is met if no data packets are currently assigned to the priority queue being serviced.

12. The queuing switch according to claim 8, wherein the priority queue assignment of an incoming data packet is changeable.

13. The queuing switch according to claim 8, wherein the priority weight of an incoming data packet is changeable.

14. The queuing switch according to claim 8, wherein the service weight of each of the priority queues is changeable.

15. The queuing switch according to claim 8, wherein data packets are delivered from each queue on a first-in-first-out basis.