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

• US 6,804,738 B2
• Filed: 10/12/2001
• Issued: 10/12/2004
• Est. Priority Date: 10/12/2001
• Status: Active Grant

• 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): Lefkowitz, Sumati
• Application Number:
  US09/977,602
• Publication Number:
  US 20030074507A1
• Time in Patent Office: 1,096 Days
• Field of Search: 710/240-244, 710/117, 710/124, 710/45, 711/147-153, 370/229-234, 370/345-348, 370/395--39
• 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:

determining if a resource is available to service requests;

if resource bandwidth is available;

if at least one channel of a first level comprises at least one request and is within allocation, issuing at least one request from at the least one channel of the first level;

if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if a channel of a second level comprises at least one request, issuing a request from the channel of the second level,

keeping track of a 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 a channel.

2. The method as set forth in claim 1, wherein if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if the channel of the second level does not comprise at least one of at least one request and exceeds allocation, and a channel of a third level comprises at least one request, issuing a request from the channel of the third level.

3. The method as set forth in claim 1, wherein if the channel of the first level comprises at least one request and exceeds allocation, issuing requests from the channel of the second level until the channel of the first level is within allocation, wherein requests of channels of the first level are given priority when operating within allocation.

4. The method as set forth in claim 1, wherein if the channel of the first level exceeds allocation, reassigning the channel to a third level lower in priority to the first level and second level such that requests of the channel of the first level are issued after requests of the channel of the second level.

5. The method as set forth in claim 4, wherein if the channel originally of the first level and currently at the third level is operating within allocation, reassigning the channel to the first level.

6. The method as set forth in claim 1, further comprising referencing at least one scheduling history of requests, said issuing also based upon the at least one scheduling history.

7. The method as set forth in claim 1, wherein the levels are representative of Quality of Service guarantees (QOS).

8. The method as set forth in claim 1, wherein the levels are representative of channels characterized from the group consisting of priority channels, allocated bandwidth channels and best effort channels.

9. The method as set forth in claim 1, wherein at least one channel comprises multiple requests, wherein ordering of issuance of requests within a channel is substantially independent of the issuance of requests from the channel to the resource.

10. A method comprising:

determining if a resource is available to service requests;

if resource bandwidth is available;

if at least one channel of a first level comprises at least one request and is within allocation, issuing at least one request from at the least one channel of the first level;

if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if a channel of a second level, lower in priority than the first level, comprises at least one request, issuing a request from the channel of the second level; and

if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if the channel of a second level does not comprise at least one request, issuing a request from a channel of the first level which exceeds allocation,

keeping track of a 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 a channel.

11. The method as set forth in claim 10, wherein if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if the channel of the second level does not comprise at least one of at least one request and exceeds allocation, and a channel of a third level comprises at least one request, the third level lower in priority than the first level and second level issuing a request from the channel of the third level.

12. The method as set forth in claim 10, wherein if the channel of the first level comprises at least one request and exceeds allocation, issuing requests from the channel of the second level until the channel of the first level is within allocation, wherein requests of channels of the first level are given priority when operating within allocation.

13. The method as set forth in claim 10, wherein if the channel of the first level exceeds allocation, reassigning the channel to a third level lower in priority to the first level and second level such that requests of the channel of the first level are issued after requests of the channel of the second level.

14. The method as set forth in claim 13, wherein if the channel originally of the first level and currently at the third level is operating within allocation, reassigning the channel to the first level.

15. The method as set forth in claim 11, wherein channels of the first level comprise priority channel, channels of the second level comprise allocated bandwidth channels and channels of the third level comprise best effort channels.

16. An arbiter coupled to receive requests from channels of a plurality of levels, each level comprising at least one channel configured to control conveyance of requests for a resource to process, said arbiter configured to determine if the resource is available to service requests, and if resource bandwidth is available and if at least one channel of a first level comprises at least one request and is within allocation, said arbiter controlling issuance of at least one request from at the least one channel of the first level;

and if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if a channel of a second level comprises at least one request, said arbiter controlling issuance of at least one request from the channel of the second level said arbiter further comprising a rate counter and allocation counter, the rate counter incremented every unit cycle, the allocation counter incremented every predetermined number of rate count and decremented each time a request is received from the channel.

17. The arbiter as set forth in claim 16, wherein each level represents a priority of Quality of Service (QOS) guarantees.

18. The arbiter as set forth in claim 16, further comprising a scheduling history and identifications of quality of service (QOS) guarantees for the channels, said arbiter further controlling issuance of at least one request based upon the scheduling history and QOS guarantees.

19. The arbiter as set forth in claim 18, wherein the scheduling history comprises bandwidth usage, said arbiter further comprising linked counters to keep track of a channel'"'"'s bandwidth usage history.

20. The arbiter as set forth in claim 18, wherein the scheduling history comprises bandwidth usage, said arbiter further comprising saturation logic such that the history of bandwidth usage of a channel is within a range specified by a saturation usage value.

21. The arbiter as set forth in claim 16, wherein the arbiter is further configured, if the channel of the first level does not comprise at least one of at least one request and exceeds allocation, and if the channel of the second level does not comprise at least one of at least one request and exceeds allocation, and a channel of a third level comprises at least one request, to issue a request from the channel of the third level.

22. The arbiter as set forth in claim 16, wherein the arbiter arbitrates requests to a dynamic random access memory (DRAM).

23. A system comprising:

at least one priority channel comprising at least one request for service from a resource, said priority channel providing a first predetermined allocation;

at least one allocated-bandwidth channel comprising at least one request for service from the resource, said allocated-bandwidth channel providing a second predetermined allocation; and

an arbiter comprising logic configured to determine ordering of requests using a rate-based scheduling process, wherein the arbiter comprises a rate counter and allocation counter, the rate counter incremented every unit cycle, the allocation counter incremented every predetermined number of rate count and decremented each time a request is received from a channel.

24. The system as set forth in claim 23, wherein the resource is a dynamic random access memory (DRAM).

27. The system as set forth in claim 23, wherein the allocation counter saturates at a saturation value such that the allocation counter value is within a range defined by positive saturation value and negative saturation value.

25. A system comprising:

at least one priority channel comprising at least one request for service from a resource, said priority channel providing a first predetermined allocation;

at least one allocated-bandwidth channel comprising at least one request for service from the resource, said allocated-bandwidth channel providing a second predetermined allocation; and

an arbiter comprising logic configured to determine ordering of requests using a rate-based scheduling process, where the rate-based scheduling process comprises incrementing a rate count every unit cycle, incrementing a first allocation count every predetermined number of rate count and decrementing the first allocation count each time a priority channel request is received, wherein when the first allocation count is below a specified threshold, requests from the allocated-bandwidth channel are processed before requests from the priority channel.

26. The system as set forth in claim 25, wherein the threshold corresponds to a saturation value, the first allocation count saturating at least one of the positive saturation value and negative saturation value.