Method and apparatus for scheduling a resource to meet quality-of-service restrictions

• US 7,191,273 B2
• Filed: 10/11/2004
• Issued: 03/13/2007
• Est. Priority Date: 10/12/2001
• Status: Expired due to Term

• Current Assignee: META Platforms Technologies LLC (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Original Assignee: Sonics Incorporated (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Weber, Wolf-Dietrich
• Primary Examiner(s): AUVE, GLENN ALLEN
• Application Number:
  US10/963,271
• Publication Number:
  US 20050086404A1
• Time in Patent Office: 883 Days
• Field of Search: None
• US Class Current: 710/244
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6265 past bandwidth allocation
• CPC Class Codes: H04L 47/6275 based on priority
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements

Abstract

The present invention is directed to a method and apparatus for scheduling a resource to meet quality of service guarantees. In one embodiment of three levels of priority, if a channel of a first priority level is within its bandwidth allocation, then a request is issued from that channel. If there are no requests in channels at the first priority level that are within the allocation, requests from channels at the second priority level that are within their bandwidth allocation are chosen. If there are no requests of this type, requests from channels at the third priority level or requests from channels at the first and second levels that are outside of their bandwidth allocation are issued. The system may be implemented using rate-based scheduling.

Claims

1. A method, comprising:

scheduling access to a resource to meet quality of service guarantees for requests within an apparatus;

storing a first request in a first channel, wherein the first channel is assigned with a first priority level;

keeping track of bandwidth usage from the first channel;

demoting a priority level of the first channel based on exceeding an allotted amount of bandwidth usage from the first channel in a specified period of time;

scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for requests within the apparatus; and

keeping track of the first channel'"'"'s bandwidth usage history by incrementing a rate counter every unit cycle and by incrementing an allocation counter every predetermined number of rate count and decrementing the allocation counter each time a request is received from the first channel.

2. A method, comprising:

scheduling access to a resource to meet quality of service guarantees for requests;

storing a first request in a first channel that is assigned with a first priority level;

keeping track of scheduling history from the first channel;

demoting a priority level of the first channel based on exceeding a tracked feature of scheduling history associated with the first channel in a specified period of time, wherein the tracked feature of scheduling history associated with the channel is a type of request within a request stream; and

scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for requests.

3. The method of claim 2, further comprising:

keeping track of bandwidth usage from the first channel; and

demoting a priority level of the first channel based on exceeding an allotted amount of bandwidth usage from the first channel in a specified period of time.

4. The method of claim 3, further comprising:

continuing to grant access to the resource to requests from the first channel, if the first channel is at an assigned highest priority and is within its allotted amount of bandwidth usage regardless of whether requests are waiting for access in lower priority channels.

5. The method of claim 3, further comprising:

granting access to the resource to a second request from a second channel at a second priority level that is within its allotted amount of bandwidth usage if there are no requests in channels at the first priority level that are within their allotted amount of bandwidth usage.

6. The method of claim 3, further comprising:

granting access to the resource to a third request from a third channel at a third priority level if there are no requests in channels at the first priority level or a second priority level that are within their allotted amount of bandwidth usage.

7. The method of claim 3, further comprising:

promoting the priority level of the first channel when the first channel is back within its allotted amount of bandwidth usage.

8. The method of claim 3, further comprising:

using scheduling history to decide whether the first channel is within its allocated amount of bandwidth usage.

9. The method of claim 3, further comprising:

using rate-based scheduling to decide whether the first channel is within its allocated amount of bandwidth usage.

10. A method, comprising:

scheduling access to a resource to meet quality of service guarantees for requests within an apparatus;

storing a first request in a first channel that is assigned with a first priority level;

keeping track of scheduling history from the first channel;

demoting a priority level of the first channel based on exceeding a tracked feature of scheduling history associated with the first channel in a specified period of time; and

scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for requests within the apparatus, wherein the tracked feature of scheduling history associated with the channel is an amount of time needed to access the resource relative to a current timing of accessing the resource.

11. The method of claim 10, further comprising:

keeping track of bandwidth usage from the first channel; and

demoting a priority level of the first channel based on exceeding an allotted amount of bandwidth usage from the first channel in a specified period of time.

12. The method of claim 11, further comprising:

continuing to grant access to the resource to requests from the first channel, if the first channel is at an assigned highest priority and is within its allotted amount of bandwidth usage regardless of whether requests are waiting for access in lower priority channels.

13. The method of claim 11, further comprising:

granting access to the resource to a second request from a second channel at a second priority level that is within its allotted amount of bandwidth usage if there are no requests in channels at the first priority level that are within their allotted amount of bandwidth usage.

14. The method of claim 11, further comprising:

granting access to the resource to a third request from a third channel at a third priority level if there are no requests in channels at the first priority level or a second priority level that are within their allotted amount of bandwidth usage.

15. The method of claim 11, further comprising:

promoting the priority level of the first channel when the first channel is back within its allotted amount of bandwidth usage.

16. The method of claim 11, further comprising:

using scheduling history to decide whether the first channel is within its allocated amount of bandwidth usage.

17. The method of claim 11, further comprising:

using rate-based scheduling to decide whether the first channel is within its allocated amount of bandwidth usage.

18. An apparatus, comprising:

means for scheduling access to a resource to meet quality of service guarantees for requests within the apparatus;

means for storing a first request in a first channel, wherein the first channel is assigned with a first priority level;

means for keeping track of bandwidth usage from the first channel;

means for demoting a priority level of the first channel based on exceeding an allotted amount of bandwidth usage from the first channel in a specified period of time;

means for scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for requests within the apparatus; and

means for keeping track of the first channel'"'"'s bandwidth usage history by incrementing a rate counter every unit cycle and by incrementing an allocation counter every predetermined number of rate count and decrementing the allocation counter each time a request is received from the first channel.

19. An apparatus, comprising:

means for scheduling access to a resource to meet quality of service guarantees for requests;

a first channel that is assigned with a first priority level to store a first request;

means for keeping track of bandwidth usage from the first channel;

means for demoting a priority level of the first channel based on exceeding an allotted amount of bandwidth usage from the first channel in a specified period of time;

means for scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for requests;

an allocation counter; and

a rate counter to keep track of the first channel'"'"'s bandwidth usage history by incrementing the rate counter every unit cycle and by incrementing the allocation counter every predetermined number of rate count and decrementing the allocation counter each time a request is received from the first channel.

20. An apparatus, comprising:

means for scheduling access to a resource to meet guality of service guarantees for requests within the apparatus;

means for storing a first request in a first channel, wherein the first channel is assigned with a first priority level;

means for keeping track of scheduling history from the first channel;

means for demoting a priority level of the first channel based on exceeding a tracked feature of scheduling history associated with the first channel in a specified period of time; and

means for scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for requests within the apparatus, wherein the tracked feature of scheduling history associated with the channel is a type of request within a request stream.

21. The method of claim 20, further comprising:

keeping track of bandwidth usage from the first channel; and

demoting a priority level of the first channel based on exceeding an allotted amount of bandwidth usage from the first channel in a specified period of time.

22. The method of claim 21, further comprising:

continuing to grant access to the resource to requests from the first channel, if the first channel is at an assigned highest priority and is within its allotted amount of bandwidth usage regardless of whether requests are waiting for access in lower priority channels.

23. The method of claim 21, further comprising:

granting access to the resource to a second request from a second channel at a second priority level that is within its allotted amount of bandwidth usage if there are no requests in channels at the first priority level that are within their allotted amount of bandwidth usage.

24. The method of claim 21, further comprising:

granting access to the resource to a third request from a third channel at a third priority level if there are no requests in channels at the first priority level or a second priority level that are within their allotted amount of bandwidth usage.

25. The method of claim 21, further comprising:

promoting the priority level of the first channel when the first channel is back within its allotted amount of bandwidth usage.

26. The method of claim 21, further comprising:

using scheduling history to decide whether the first channel is within its allocated amount of bandwidth usage.

27. The method of claim 21, further comprising:

using rate-based scheduling to decide whether the first channel is within its allocated amount of bandwidth usage.

28. An apparatus, comprising:

means for scheduling access to a resource to meet quality of service guarantees for requests;

a first channel that is assigned with a first priority level to store a first request;

means for keeping track of scheduling history from the first channel;

means for demoting a priority level of the first channel based on exceeding a tracked feature of scheduling history associated with the first channel in a specified period of time, wherein the tracked feature of scheduling history associated with the channel is an amount of time needed to access the resource relative to a current timing of accessing the resource; and

means for scheduling the first channel to issue the first request to a resource to meet quality of service guarantees for request.

29. An apparatus, comprising:

an arbiter configured to schedule access to a resource for requests from a plurality of channels within the apparatus, where one or more of the channels have an assigned priority level and convey to the arbiter requests to access the resource, the arbiter configured to determine if the resource is available to service requests within the apparatus, the arbiter configured to demote a priority level of a first channel based on exceeding a tracked feature of scheduling history associated with the first channel in a specified period of time, the arbiter configured with a quality-of-service (QOS) guarantee for requests from the first channel, the arbiter configured to schedule the first channel to issue a first request to the resource to meet the quality of service guarantee for the first request, wherein the tracked feature of scheduling history associated with the channel is an amount of time needed to access the resource relative to a current timing of accessing the resource.

30. The apparatus of claim 29, wherein the arbiter is configured to continuously grant access to the resource to requests from the first channel, if the first channel is at an assigned highest priority and is within its allotted amount of bandwidth usage regardless of whether requests are waiting for access in lower priority channels.

31. The apparatus of claim 29, wherein the arbiter is configured to promote the priority level of the first channel when the first channel is back within its allotted amount of bandwidth usage.