Nonlinear adaptive control of resource-distribution dynamics

• US 20060013132A1
• Filed: 06/16/2005
• Published: 01/19/2006
• Est. Priority Date: 06/16/2004
• Status: Abandoned Application

• Current Assignee: Creative Technology Ltd.
• Original Assignee: The Board of Regents of the University of Colorado (University of Colorado System)
• Inventors: Bradley, Elizabeth, Garnett, James G.
• Application Number:
  US11/155,535
• Publication Number:
  US 20060013132A1
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: G06F 11/0736 in functional embedded systems, i.e. in a data processing system designed as a combination of hardware and software dedicated to performing a certain function testing or monitoring of automated control systems G05B23/02
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

Abstract

Nonlinear adaptive resource management systems and methods are provided. According to one embodiment, a controller identifies and prevents resource starvation in resource-limited systems. To function correctly, system processes require resources that can be exhausted when under high load conditions. If the load conditions continue a complete system failure may occur. Controllers functioning in accordance with embodiments of the present invention avoid these failures by distribution shaping that completely avoids undesirable states. According to one embodiment, a Markov Birth/Death Chain model of the resource usage is built based on the structure of the system, with the number of states determined by the amount of resources, and the transition probabilities by the instantaneous rates of observed consumption and release. A control stage is used to guide a controller that denies some resource requests in real systems in a principled manner, thereby reducing the demand rate and the resulting distribution of resource states.

Claims

1. A method of controlling a resource management system, the method comprising:

modeling the resource management system with a Markov process;

empirically measuring a stationary distribution of resource states of the resource management system; and

modifying transition probabilities in the resource management system using feedback control to track a desired stationary distribution of the resource management system.

2. The method as recited in claim 1, wherein modeling the resource management system with a Markov process comprises estimating one or more resource request probabilities and one or more resource service probabilities, wherein one of the one or more resource request probabilities and one of the one or more of the resource service probability are used to estimate the transition probabilities in the resource management system.

3. The method as recited in claim 2, wherein estimating resource request probabilities comprises linear filtering.

4. The method as recited in claim 1, further comprising:

generating an error signal characterizing a difference between the empirically measured stationary distribution and the desired stationary distribution; and

applying a preconditioning transform to the error signal.

5. The method as recited in claim 4, wherein the preconditioning transform comprises applying a nonlinear transform to generate a modified error signal.

6. The method as recited in claim 1, wherein modifying transition probabilities comprises dropping one or more requests.

7. The method as recited in claim 1, wherein modifying transition probabilities comprises buffering requests.

8. The method as recited in claim 1, wherein the feedback control is determined by a proportional, integral, and derivative (PID) controller.

9. The method as recited in claim 8, wherein PID controller parameters are selected using analytical methods.

10. The method as recited in claim 8, wherein PID controller parameters are selected using experimental methods.

11. The method as recited in claim 8, wherein PID controller parameters are selected using the Ziegler-Nichols method.

12. The method as recited in claim 1, wherein the resource management system is a network subsystem.

13. The method as recited in claim 12, wherein the network subsystem is an OpenBSD networking subsystem.

14. The method as recited in claim 1, wherein the resource management system is a memory system.

15. The method as recited in claim 1, wherein the resource management system is a plurality of TCP/IP network routers.

16. The method as recited in claim 1, wherein the resource management system is a kernel table of an operating system.

17. The method as recited in claim 1, wherein the resource management system is a server software system.

18. The method as recited in claim 1, wherein the resource management system is a telephone switch system.

19. The method as recited in claim 1, wherein the resource management system is a transportation system.

20. The method as recited in claim 1, wherein the resource management system is a flight system.

21. A method of controlling access to system resources resulting in systematic service degradation, the method comprising:

developing a stochastic model of dynamic states of the system resources;

calculating a control ratio table by computing the ratio of input resource request to serviced resource request of the stationary probabilities of adjacent states in a Birth/Death Chain, wherein the control ratio table comprises ratios of admitted requests to serviced requests that must be maintained in order to satisfy a quality of service (QoS) specification;

receiving a resource request from one or more resource requestors;

utilizing the stochastic model to dynamically adapt to a system state;

controlling access of the resource requesters to the requested resources using feedback control to adjust probability distribution of the admission of the resource requests admitted to the system to cause an empirically measured distribution of the system to track a desired limit distribution.

22. A system for controlling access to one or more system resources through service degradation, the system comprising:

a memory having data representing a stochastic model of a dynamic state of the one or more system resources;

a resource manager configured to manage a plurality of resource requests granted access to the one or more system resources;

an input request filter configured to estimate an input request probability based on historical data, the input request probability representing a probability of receiving a resource request;

a service filter configured to estimate a service probability, the service probability representing a probability that a resource request will be serviced;

a distribution recorder configured to compute and record an empirical probability distribution characterizing a probability of a quantity of the one or more system resources being used;

a transition ratio table having data representing transition probabilities of changing from one state to another;

a control algorithm configured to utilize a difference between a desired limit distribution and the empirical probability distribution to produce a control signal; and

an admission controller configured to receive resource requests from one or more resource requesters and determine whether a received resource request should be granted access to the system resources, wherein the admission controller comprises a drop state calculator configured to use the estimate of the input request probability, the estimate of the service probability, and the control signal to generate a resource request denial probability which is used to determine whether the resource request should be granted access to the system resources.

23. The system of claim 22, wherein the memory has stored thereon computer executable instructions causing a computer to:

model the resource management system with a Markov process;

empirically measure a stationary distribution of the resource management system; and

modify the transition probabilities in the resource management system using feedback control to track a desired stationary distribution of the resource management system.

24. The system of claim 22 wherein the transition table is computed from a quality of service specification specifying a maximum allowed probability of a given resource state.

25. A computer-readable storage medium containing a set of instructions executable by a computer having a user interface, the set of instructions comprising:

(a) a first input routine operatively associated with said user interface, said first input routine enabling the computer to receive a desired limit probability distribution from said user interface;

(b) a second input routine operatively associated with said user interface, said second input routine enabling the computer to receive a desired set of controller parameters through said user interface;

(c) an analysis module empirically measuring a stationary distribution characteristic of a resource management system; and

(d) an admission controller modifying an admission policy of the resource management system by using feedback control to adjust probabilities of admittance and denial of resource requests from one or more resource requestors in order for said resource management system to track a desired stationary distribution of the resource management system.