Method for allocating a resource among consumers in proportion to configurable weights

• US 8,305,889 B2
• Filed: 01/31/2010
• Issued: 11/06/2012
• Est. Priority Date: 01/31/2010
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Watts, Jonathan M.
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): CATTUNGAL, AJAY P
• Application Number:
  US12/697,267
• Publication Number:
  US 20110188507A1
• Time in Patent Office: 1,010 Days
• Field of Search: 370/229, 370/235, 370/235.1, 370/230.01, 370/395.41, 370/394, 370/395.4, 370/412, 370/465, 709/226
• US Class Current: 370/229
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 47/39 Credit based
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank

Abstract

A method for allocating a resource among a plurality of consumers of the resource is described herein. For each consumer of the plurality of consumers, a configurable weight associated with the consumer is determined. For each consumer of the plurality of consumers, credits assigned to the consumer at a first interval of a plurality of variable intervals are determined. The credits may be assigned in proportion to the configurable weight associated with the consumer. A consumer is selected for servicing based on the credits of the consumer. The selected consumer is serviced.

Claims

1. A method of allocating a resource among a plurality of consumers of the resource, the method comprising:

for each consumer of the plurality of consumers, determining a configurable weight associated with the consumer;

for each consumer of the plurality of consumers, determining credits assigned to the consumer at a first interval of a plurality of variable intervals, the credits assigned in proportion to the configurable weight associated with the consumer;

selecting, by a data processor, a consumer of the plurality of consumers for servicing based on the credits of the consumer;

servicing the selected consumer;

detecting consumers that are active during the first interval;

determining a sum of the configurable weights associated with the active consumers; and

allocating the sum of the configurable weights associated with the active consumers to a second interval.

2. The method of claim 1, further comprising:

for each consumer of the plurality of consumers, tracking the assigned credits using a credit counter;

tracking consumption of the resource for one or more of the plurality of variable intervals using an interval counter; and

deducting a number of credits from the credit counter of the selected consumer and the interval counter.

3. The method of claim 2, further comprising:

detecting that the interval counter is below an update threshold.

4. The method of claim 3, further comprising:

normalizing the configurable weight of each of the active consumers;

normalizing the sum of the configurable weights of the active consumers;

determining an updated count of the interval counter based on the normalized sum; and

for each of the active consumers, determining an updated count of the credit counter of the consumer based on the normalized configurable weight of the consumer.

5. The method of claim 4, wherein the configurable weight of each of the active consumers is normalized by bit-shifting a binary representation of the configurable weight of each of the active consumers by a shift amount.

6. The method of claim 4, wherein the sum is normalized by bit-shifting a binary representation of the sum by a shift amount.

7. The method of claim 2, further comprising:

determining the end of the first interval based on the interval counter;

allocating the sum of the configurable weights associated with the active consumers to a count of the interval counter for the second interval; and

for each of the active consumers, allocating the configurable weight associated with the consumer to a count of the credit counter of the consumer.

8. The method of claim 1, further comprising:

allocating the resource credits of an inactive consumer to the active consumers in proportion to the configurable weight associated with each of the active consumers.

9. A network switch device for use in a network for controlling transmission of data packets through the network switch, the switch comprising:

a plurality of ports; and

a switch controller coupled to the plurality of ports, wherein the switch controller is to designate a data packet to a buffer of a plurality of buffers associated with a port of the plurality of ports,

wherein the port is to;

for each buffer, determine a configurable weight associated with the buffer;

for each buffer, determine credits assigned to the buffer at a first interval of a plurality of variable intervals, the credits assigned in proportion to the configurable weight associated with the buffer;

select a buffer of the plurality of buffers for servicing based on the credits of the buffer;

transmit via the port a data packet from the selected buffer;

detect buffers that are active during the first interval;

determine a sum of the configurable weights associated with the active buffers; and

allocate the sum of the configurable weights associated with the active buffers to a second interval.

10. The network switch device of claim 9, wherein the port is further to:

track the assigned credits using a credit counter, for each buffer;

track consumption of bandwidth of the port for one or more of the plurality of variable intervals using an interval counter; and

deduct a number of credits from the credit counter of the selected buffer and the interval counter.

11. The network switch device of claim 10, wherein the port is further to:

detect that the interval counter is below an update threshold.

12. The network switch device of claim 11, wherein the port is further to:

normalize the configurable weight of each of the active buffers;

normalize the sum of the configurable weights of the active buffers;

determine an updated count of the interval counter based on the normalized sum; and

for each of the active buffers, determine an updated count of the credit counter of the buffer based on the normalized configurable weight of the buffer.

13. The network switch device of claim 12, wherein the configurable weight of each of the active buffers is normalized by bit-shifting a binary representation of the configurable weight of each of the active buffers by a shift amount.

14. The network switch device of claim 9, wherein the designation of the data packet to the buffer is based on at least one of a Quality-of-Service requirement and a Class-of-Service requirement.

15. The network switch device of claim 9, wherein the port is further to allocate bandwidth of an inactive buffer to the active buffers in proportion to the configurable weight associated with each of the active buffers.

16. A non-transitory computer-readable medium storing a plurality of instructions for controlling a data processor for allocating a resource among a plurality of consumers of the resource, the plurality of instructions comprising instructions that cause the data processor to:

determine, for each consumer of the plurality of consumers, a configurable weight associated with the consumer;

determine, for each consumer of the plurality of consumers, credits assigned to the consumer at a first interval of a plurality of variable intervals, the credits assigned in proportion to the configurable weight associated with the consumer;

select a consumer of the plurality of consumers for servicing based on the credits of the consumer;

service the selected consumer;

detect consumers that are active during the first interval;

determine a sum of the configurable weights associated with the active consumers; and

allocate the sum of the configurable weights associated with the active consumers to a second interval.

17. The non-transitory computer-readable medium of claim 16, wherein the plurality of instructions further comprise instructions that cause the data processor to:

track, for each consumer of the plurality of consumers, the assigned credits using a credit counter;

track consumption of the resource for one or more of the plurality of variable intervals using an interval counter; and

deduct a number of credits from the credit counter of the selected consumer and the interval counter.

18. The non-transitory computer-readable medium of claim 17, wherein the plurality of instructions further comprise:

instructions that cause the data processor to detect that the interval counter is below an update threshold.

19. The non-transitory computer-readable medium of claim 17, wherein the plurality of instructions further comprise instructions that cause the data processor to:

determine the end of the first interval based on the interval counter;

allocate the sum of the configurable weights associated with the active consumers to a count of the interval counter for the second interval; and

allocate, for each of the active consumers, the configurable weight associated with the consumer to a count of the credit counter of the consumer.

20. The non-transitory computer-readable medium of claim 16, wherein the plurality of instructions further comprise:

instructions that cause the data processor to allocate the credits of an inactive consumer to the active consumers in proportion to the configurable weight associated with each of the active consumers.