Method and apparatus for establishing a quality of service model

• US 7,665,069 B2
• Filed: 10/31/2003
• Issued: 02/16/2010
• Est. Priority Date: 10/31/2003
• 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): RUTTEN, JAMES D
• Application Number:
  US10/698,905
• Publication Number:
  US 20050096970A1
• Time in Patent Office: 2,300 Days
• Field of Search: None
• US Class Current: 717/127
• CPC Class Codes: G06Q 10/06395 Quality analysis or management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2425 for supporting services specification, e.g. SLA
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 47/827 Aggregation of resource allocation or reservation requests

Abstract

In general, methods and apparatus for implementing a Quality of Service (QoS) model are disclosed. A Quality of Service (QoS) contract with an initiating network device may be satisfied. A request may be received from the initiating network device in a first time less than or equal to an ordinal number times an arrival interval. The ordinal number signifies a position of the request among a group of requests. The request that has been serviced may be returned to the initiator in a second time less than or equal to a constant term plus the ordinal number times a service interval.

Claims

1. A method for satisfying a Quality of Service (QoS) contract with an initiator in an Integrated Circuit, comprising:

receiving a request from the initiator in the Integrated Circuit in a first time less than or equal to an ordinal number times an arrival interval to satisfy an arrival model, wherein the ordinal number signifies a position of the request among a group of requests;

returning the request from the initiator that has been serviced by a target to the initiator in a second time less than or equal to a constant term plus the ordinal number times a service interval to satisfy a service model; and

measuring the first and second time at a boundary between the initiator and an interconnect in the Integrated Circuit.

2. The method of claim 1, further comprising:

determining whether the arrival model and the service model have been satisfied in order to satisfy the QoS contract.

3. The method of claim 1, further comprising:

satisfying the QoS contract using the initiator, a target, the interconnect, and a QoS unit that are all located on a chip.

4. The method of claim 3, wherein the service interval is greater than the arrival interval.

5. The method of claim 1, wherein the service interval is equal to the arrival interval.

6. The method of claim 1, further comprising:

determining the constant term specifically for the group of requests.

7. The method of claim 6, wherein the arrival interval is a predetermined accepted interval for requested arrivals.

8. A system, comprising:

an interconnect coupled between an initiator and a target, wherein an arrival model is satisfied by the initiator if a request arrives before a first time less than or equal to an ordinal number times an arrival interval, wherein the ordinal number signifies a position of the request among a group of requests;

a Quality of Service (QoS) logic unit coupled to the interconnect and is configured to satisfy a service model if the initiator satisfies the arrival model, wherein the logic unit satisfies the service model if the request is serviced before a second time less than or equal to a constant term plus the ordinal number times a service interval; and

wherein the Quality of Service (QoS) logic unit is configured to satisfy a QoS contract and is located at a boundary between the initiator and the interconnect and the QoS contract is based on the arrival model and the service model being satisfied.

9. The system of claim 8, wherein the service interval is greater than the arrival interval.

10. The system of claim 8, wherein the constant term is determined specifically for the group of requests.

11. The system of claim 10, wherein the QoS unit is coupled between the target and the interconnect.

12. The method of claim 8, wherein the QoS contract is satisfied using the initiator, the target, the interconnect, and the logic that are all located on a chip.

13. The system of claim 12, wherein the QoS unit is part of the interconnect.

14. The system of claim 8, wherein the QoS unit is part of the target.

15. A method for tracking service for two or more threads in an Integrated Circuit, comprising:

maintaining a first allocation count for a first thread to track whether the first thread is being serviced by a target in the Integrated Circuit, wherein the first thread is a bandwidth allocation thread;

establishing an adjustable positive limit having a first value for the first allocation count that establishes an initial maximum amount the first allocation count may go up to;

raising the adjustable positive limit for the first allocation count to a second value when the first value for the first allocation count has been reached and the first thread has yet to have a request fulfilled from the target during a regular interval of time;

satisfying a service model if an arrival model is satisfied by an initiator if a request arrives before a first time less than or equal to an ordinal number times an arrival interval, wherein the ordinal number signifies a position of the request among a group of requests; and

wherein the service model is satisfied if the request is serviced before a second time less than or equal to a constant term plus the ordinal number times a service interval.

16. The method of claim 15, further comprising:

reducing the positive limit from the second value to a third value for the first allocation count at a time when a second allocation count receives a credit and is positive.

17. The method of claim 16, wherein the positive limit is not reduced below the first value.

18. The method of claim 15, further comprising:

crediting the first and second allocation count at a regular interval;

debiting the first allocation count when the first thread is serviced; and

debiting the second allocation count when a second thread is serviced; and

establishing a negative limit having a fourth value for the first allocation count.

19. The method of claim 15, wherein raising comprises increasing the positive limit by an amount proportional to an allocation rate of the first thread.

20. The method of claim 19, wherein the amount proportional to the allocation rate of the first thread comprises a number of times the second thread was serviced by the target during the regular interval of time multiplied by the allocation rate of the first thread.

21. The method of claim 18, further comprising:

determining whether the first thread will be serviced according to the first allocation count.

22. The method of claim 21, further comprising:

servicing the first thread instead of the second thread when the second allocation count is less than the first allocation count.

23. The method of claim 15, wherein the second thread is a high-priority thread.

24. The method of claim 23, wherein the first thread is a bandwidth-allocation thread.

25. A system, comprising:

an interconnect coupled to an initiator and a target;

a first logic coupled to the interconnect, and configured to maintain a first allocation count for a first thread from the initiator to track bandwidth usage by the first thread;

a second logic coupled to the first logic, and configured to establish an adjustable positive limit having a first value for the first allocation count that establishes an initial maximum amount the first allocation count may go up to; and

a third logic coupled to the second logic, and configured to raise the adjustable positive limit from the first value to a second value when the first value for the first allocation count has been reached, then the first thread has not been service during a predetermined interval of time, and the first thread has one or more requests waiting to be serviced from the target, wherein the first thread is a bandwidth allocation thread;

an arrival model logic coupled to the interconnect and the first logic, the an arrival model logic is configured to satisfy a service model if an arrival model is satisfied by the initiator if a request arrives before a first time less than or equal to an ordinal number times an arrival interval, wherein the ordinal number signifies a position of the request among a group of requests; and

wherein the service model is satisfied if the request is serviced before a second time less than or equal to a constant term plus the ordinal number times a service interval.

26. The system of claim 25, further comprising:

a fourth logic coupled to the second logic, and configured to reduce the raised adjustable positive limit to a third value when a second allocation count receives a credit and is positive.

27. The system of claim 25, wherein the positive limit is raised by an amount proportional to an allocation rate of the first thread.