System and method for scheduling bandwidth resources using a Kalman estimator with active feedback

• US 6,785,889 B1
• Filed: 06/15/2000
• Issued: 08/31/2004
• Est. Priority Date: 06/15/2000
• Status: Expired due to Term

• Current Assignee: Aurema (Cloud Software Group)
• Original Assignee: Aurema (Cloud Software Group)
• Inventors: Williams, Peter
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): Nguyen, Hai V.
• Application Number:
  US09/596,026
• Time in Patent Office: 1,538 Days
• Field of Search: 709/104, 709/229, 709/240, 718/104, 718/106
• US Class Current: 718/104
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

A community of collaborative software agents works together in a domain to provide functionality such as provision of communications services or control of a chemical process. A scheduler is built into each collaborative agent which schedules tasks allocated to that particular agent and tasks sub-allocated by the agent. The scheduler has a mechanism for over-booking tasks for any one agent. It can also make tentative booking which can be overwritten of timed out.

Claims

1. A bandwidth resource scheduler executing in a digital device using active feedback for determining the relative priority to be used when allocating schedulable resources to a resource consuming entity with allocated shares of the bandwidth resource, said scheduler comprising:

means for calculating bandwidth resource usage wherein the number of the bandwidth resource'"'"'s indivisible units that the resource consuming entity is receiving per unit of time, is a number between zero and the number of indivisible units that are available for consumption at each indivisible instant of time; and

means for calculating entitlements of the resource consuming entity as a ratio of the product of the number of indivisible units that are available for consumption at each indivisible instant of time and the number of shares held by that entity at that time, to the total number of shares held by all live entities at that time, to provide a number between zero and the number of indivisible units that are available for consumption at each indivisible instant of time, and

means for recording past demand usage and for estimating future usage by calculating a single variable metric based on the recorded past usage; and

active feedback loop responsive to said single variable metric calculated for each said entity and responsive to said calculated entitlements of each said resource consuming entity for calculating relative priorities of each resource consuming entity, such that priorities for the resource consuming entities are calculated and mapped to entities in a scheduler entity run queue.

2. A system as in claim 1 wherein the single variable metric is calculated using a moving average model for the estimation of future usage.

3. A system as in claim 2 wherein the moving average model comprises a numerical scheme which is numerically stable and bounded, providing little or no overshoot or undershoot while scheduling multiple resource consuming entities in an entity hierarchy allocating bandwidth resources and thereby generating an aggregate usage load with multiple shared resources.

4. A system as in claim 1 wherein entitlements are derived by creating hierarchies of entities such that access to bandwidth resources is distributed in a tiered policy fashion of allocating shares and reservations to resource consuming entities rather than a direct linear resource allotment to of the bandwidth to a user.

5. A bandwidth resource scheduler executing in a digital device using active feedback for determining the relative priority to be used when allocating schedulable resources to a resource consuming entity, said scheduler comprising:

means for calculating a stable metric based on an estimate of a moving average of the resource sharing entity'"'"'s usage; and

means for calculating the entitlements of the resource sharing entities under selected resource sharing policies; and

means responsive to said stable metric for matching an entities usage of said bandwidth resources with its entitlement to said bandwidth resources to derive relative priority of the resource sharing entities, such that priorities for entities as a result of the usage, anticipated usage and entitlement can be calculated and adaptively mapped to entities in a scheduler entity run queue.

6. System as in claim 5 using time averaging techniques for calculating said well behaved usage metrics.

7. A scheduler executing in a digital device using active feedback for determining the relative priority for scheduled resource consuming entities in entity hierarchies comprising:

means for providing entity hierarchies comprised of users, projects, groups and process groups; and

means for providing allocation policies for short term, long term or both short and long term usage requirements for the resource consuming entities on a running system; and

means for dynamic classification and scheduling of said entities in said resource consuming entity hierarchies according to said resource allocation policies such that resource sharing at the process level provides flexible higher granularity of resource sharing and a higher aggregate usage of bandwidth resources.