Method and apparatus for improved queuing

• US 6,914,882 B2
• Filed: 03/30/2001
• Issued: 07/05/2005
• Est. Priority Date: 03/30/2001
• Status: Expired due to Fees

• Current Assignee: Nokia, Inc. (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Merani, Lalit, Bhat, Ravi Bail
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/823,636
• Publication Number:
  US 20020141425A1
• Time in Patent Office: 1,558 Days
• Field of Search: 370/336, 370/337, 370/345, 370/347, 370/348, 370442-444, 370/498, 370/229, 370/230, 370/230.1, 370/232, 370/235, 370/395.4, 370/412, 370/413, 370/414, 370/417
• US Class Current: 370/230
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• 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/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/623 Weighted service order

Abstract

A queue scheduler that distributes a partition worth of bandwidth to a plurality of queues according to a weight assigned to each of the queues. The plurality of queues are arranged from a highest priority to a lowest priority. The queues are serviced by the scheduler until each of the corresponding weights is consumed for each queue. The higher priority queues are serviced before the lower priority queues.

Claims

1. An apparatus comprising:

a plurality of users;

resources that are partitioned according to a ranking of bandwidth associated with users, wherein the resources are partitioned according to a highest bandwidth supported by a node and an amount of bandwidth provided to each of the plurality of users is ranked from highest to lowest; and

a queue scheduler that

a) schedules one or more packets within the node during scheduling cycles, wherein each scheduling cycle is partitioned into regions that are coextensive with the highest bandwidth supported by the node and each schedule cycle is coextensive with a highest counting modulo partitions, and

b) services users associated with the highest bandwidth in at least one partition during each scheduling cycle and services consecutive bandwidth partitions of user associated with lower bandwidths across several cycles, wherein a number of scheduling cycles between servicing of consecutive bandwidth partitions increases as the bandwidth associated with the user decreases and the partition spacing for servicing a lower bandwidth user is determined by multiplying a number of lower bandwidth users that can be serviced by the next highest bandwidth by a partition modulo of the next highest bandwidth.

16. The method of claim 1 wherein each of said packet identifiers further comprise the same Port_ID value that identifies a port to which said queues belong.

17. The method of claim 16 wherein said one of said queues is said highest priority queue.

2. A method comprising:

a) dividing a total amount of data, based upon an individual weight assigned to each of a plurality of queues, into an amount of data that each of said queues may service;

b) scheduling packets in the plurality of queues during scheduling cycles, wherein each scheduling cycle is partitioned into regions that are coextensive with a highest bandwidth being managed by a node and each schedule cycle is coextensive with a highest counting modulo partitions;

c) servicing queues associated with the highest bandwidth in at least one partition during each scheduling cycle and servicing consecutive bandwidth partitions of queues associated with lower bandwidths across several cycles, wherein a number of scheduling cycles between servicing of consecutive bandwidth partitions increases as the bandwidth associated with the queue decreases and partition spacing for servicing a lower bandwidth queue is determined by multiplying a number of lower bandwidth users that can be serviced by the next highest bandwidth by a partition modulo of the next highest bandwidth;

d) servicing one or more populated queues, each of said servicing of a populated queue continuing until said populated queue is no longer populated or said amount of data determined for said populated queue has been released; and

e) servicing one or more of said queues that remain populated, if any, until said total amount of data has been released from all of said queues in combination including said servicing of said populated queues.

3. A method, comprising

a) distributing a partition worth of data across a plurality of queues according to a weight assigned to each of said queues so that each of said queues has its own sub-partition worth of data, each of said queues capable of holding one or more packet identifiers, each of said one or more packet identifiers pointing to its own packet, said plurality of queues ranging from a highest priority queue to a lowest priority queue;

and

b) scheduling packets in the plurality of queues during scheduling cycles, wherein each scheduling cycle is partitioned into regions that are coextensive with a highest bandwidth beina managed by a node and each schedule cycle is coextensive with a highest counting modulo partitions, and

c) servicing queues associated with the highest bandwidth in at least one partition durin each scheduling cycle and servicing consecutive bandwidth partitions of queues associated with lower bandwidths across several cycles, wherein a number of scheduling cycles between servicing of consecutive bandwidth partitions increases as the bandwidth associated with the queue decreases and partition spacing for servicing a lower bandwidth queue is determined by multiplying a number of lower bandwidth users that can be serviced by the next highest bandwidth by a partition modulo of the next highest bandwidth; and

d) flowing a flow of one or more packet identifiers from an active populated queue, until;

1) its unpopulated if less than its sub-partition worth of data has flowed, or until

2) its sub-partition worth of data has flowed, or until

3) the combination of flows from those of said queues that have been active results in said partition worth of data having flowed from said those of said queues that have been active, as a whole.

4. The method of claim 3 wherein each of said packet identifiers further comprise the same Port_ID value that identifies a port to which said queues belong.

5. The method of claim 4, wherein said port handles packets destined to the same user.

6. The method of claim 4 wherein said one of said queues is said highest priority queue.

7. The method of claim 3 wherein one of said queues receives only those of said packet identifiers that each point to its own networking control packet.

8. The method of claim 7 wherein said one of said queues is a second highest priority queue.

9. The method of claim 3 wherein one of said queues receives only those of said packet identifiers that each point to its own real time traffic packet.

10. The method of claim 9 wherein said one of said queues receives only those of said packet identifiers that each point to its own traditional data traffic packet.

11. The method of claim 10 wherein each of said weights are equal.

12. The method of claim 3 wherein one of said queues receives only those of said packet identifiers that each point to its own fast data traffic packet.

13. The method of claim 3 wherein said partition worth of data is a scheduling cycle partition worth of data, wherein one scheduling cycle partition worth of data per scheduling cycle corresponds to a data rate that is a highest data rate managed by a networking system to which each of said queues belong.

14. The method of claim 3 wherein each of said weights add up to a value that represents 100% or less of said partition worth of data.

15. The method of claim 3 wherein each of said weights add up to a value that represents more than 100% of said partition worth of data.

18. The method of claim 15 wherein one of said queues receives only those of said packet identifiers that each point to its own networking control packet.

19. The method of claim 18 wherein said one of said queues is a second highest priority queue.

20. The method of claim 15 wherein one of said queues receives only those of said packet identifiers that each point to its own real time traffic packet.

21. The method of claim 20 wherein said one of said queues receives only those of said packet identifiers that each point to its own traditional data traffic packet.

22. The method of claim 21 wherein each of said weights are equal.

23. The method of claim 15 wherein one of said queues receives only those of said packet identifiers that each point to its own fast data traffic packet.

24. The method of claim 15 wherein said partition worth of data is a scheduling cycle partition worth of data, wherein one scheduling cycle partition worth of data per scheduling cycle corresponds to a data rate that is a highest data rate managed by a networking system to which each of said queues belong.

25. The method of claim 15 wherein said flowing one or more additional flows further comprises flowing packet identifiers from a next queue, said next queue following a previous queue that flowed an additional flow to consume a previous distribution of a partition worth of data.

26. The apparatus of claim 25 wherein each of said packet identifiers further comprise the same Port_ID value that identifies a port to which said queues belong.

27. The apparatus of claim 26 wherein said one of said queues is said highest priority queue.

28. The apparatus of claim 25 wherein one of said queues receives only those of said packet identifiers that each point to its own networking control packet.

29. The apparatus of claim 28 wherein said one of said queues is a second highest priority queue.

30. The apparatus of claim 25 wherein one of said queues receives only those of said packet identifiers that each point to its own real time traffic packet.

31. The apparatus of claim 30 wherein said one of said queues receives only those of said packet identifiers that each point to its own traditional data traffic packet.

32. The apparatus of claim 31 wherein each of said weights are equal.

33. The apparatus of claim 25 wherein one of said queues receives only those of said packet identifiers that each point to its own fast data traffic packet.

34. The apparatus of claim 25 wherein said partition worth of data is a scheduling cycle partition worth of data, wherein one scheduling cycle partition worth of data per scheduling cycle corresponds to a data rate that is a highest data rate managed by a networking system to which each of said queues belong.

35. The apparatus of claim 25 wherein each of said weights add up to a value that represents 100% or less of said partition worth of data.

36. The apparatus of claim 25 wherein if more than an active queue'"'"'s sub-partition worth of data had flowed while it was active, said scheduler takes the difference between the amount of data that flowed and said sub-partition worth of data and subtracts it from said active queue'"'"'s sub partition worth of data in order to reduce the flow the next time said active queue becomes active.

37. The method of claim 15 wherein if more than an active queue'"'"'s sub-partition worth of data had flowed while it was active, the difference between the amount of data that flowed and said sub-partition worth of data is subtracted from said active queue'"'"'s sub partition worth of data in order to reduce the flow the next time said active queue becomes active.

38. The apparatus of claim 37 wherein said port handles packets destined to the same user.

39. The method of claim 3, wherein if more than an active queue'"'"'s sub-partition worth of data had flowed while it was active, the difference between the amount of data that flowed and said sub-partition worth of data is subtracted from said active queue'"'"'s sub partition worth of data in order to reduce the flow the next time said active queue becomes active.

40. The method of claim 39 wherein said port handles packets destined to the same user.

41. A method, comprising

a) distributing a partition worth of data across a plurality of queues according to a weight assigned to each of said queues so that each of said queues has its own sub-partition worth of data, each of said queues capable of holding one or more packet identifiers, each of said one or more packet identifiers pointing to its own packet, said plurality of queues ranging from a highest priority queue to a lowest priority queue;

b) scheduling packets in the plurality of queues during scheduling cycles, wherein each scheduling cycle is partitioned into regions that are coextensive with a highest bandwidth being managed by a node and each schedule cycle is coextensive with a highest counting modulo partitions; and

c) servicing queues associated with the highest bandwidth in at least one partition during each scheduling cycle and servicing consecutive bandwidth partitions of queues associated with lower bandwidths across several cycles, wherein a number of scheduling cycles between servicing of consecutive bandwidth partitions increases as the bandwidth associated with the queue decreases and partition spacing for servicing a lower bandwidth queue is determined by multiplying a number of lower bandwidth users that can be serviced by the next highest bandwidth by a partition modulo of the next highest bandwidth;

d) flowing a flow of one or more packet identifiers from an active populated queue, until;

1) its unpopulated if less than its sub-partition worth of data has flowed, or until

2) its sub-partition worth of data has flowed, or until

3) the combination of flows from those of said queues that have been active results in said partifion worth of data having flowed from said those of said queues that have been active, as a whole,

wherein a populated queue is deemed active if it is the highest priority populated queue out of those of said populated queues that have not yet been deemed active, such that populated queues are deemed active in succession until the lowest priority populated queue has been deemed active or until the combination of flows from those of said queues that have been active results in said partition worth of data having flowed from said those of said queues that have been active, as a whole.

42. An apparatus, comprising:

a scheduler that

a) schedules packets in the plurality of queues during scheduling cycles, wherein each scheduling cycle is partitioned into regions that are coextensive with a highest bandwidth being managed by a node and each schedule cycle is coextensive with a highest counting modulo partitions, and

b) services queues associated with the highest bandwidth in at least one partition during each scheduling cycle and servicing consecutive bandwidth partitions of queues associated with lower bandwidths across several cycles, wherein a number of scheduling cycles between servicing of consecutive bandwidth partitions increases as the bandwidth associated with the queue decreases and partition spacing for servicing a lower bandwidth queue is determined by multiplying a number of lower bandwidth users that can be serviced by the next highest bandwidth by a partition modulo of the next highest bandwidth; and

c) schedules controls a flow of one or more packet identifiers from an active populated queue, until;

1) its unpopulated if less than its sub-partition worth of data has flowed, or until

2) its sub-partition worth of data has flowed, or until

3) the combination of flows from those of said queues that have been active results in said partition worth of data having flowed from said those of said queues that have been active, as a whole,

wherein a populated queue is deemed active if it is the highest priority populated queue out of those of said populated queues that have not yet been deemed active, such that populated queues are deemed active in succession until the lowest priority populated queue has been deemed active or until the combination of flows from those of said queues that have been active results in said partition worth of data having flowed from said those of said queues that have been active, as a whole.