Towards Cooperative Negotiation for Decentralized Resource Allocation in Autonomic Computing Systems

1 Resource Allocation in an Autonomic Computing System

An autonomic computing system is designed to drastically re­ duce the role of human administrators by automating most of the managerial decision making [Kephart and Chess, 2003]. Automated resource allocation is necessary for an autonomic computing system to optimize its performance. In the large, distributed autonomic computing systems we would expect in big businesses, resource allocation will occur at multiple scales. Local allocation decisions will be made within indi­ vidual elements (servers, databases, storage units, etc.) and small clusters of elements. Local clusters will contend for pools of resources in the larger domain, or across adminis­ trative domains. Although we can generally assume that ele­ ments in an autonomic computing system of a single corpo­ ration will be cooperative, sharing the common goal of op­ timizing total business value, the complexity of local infor­ mation will often preclude centralized allocation across the entire system. Cooperative negotiation, using preference elic­ itation techniques, can be an effective approach to decentral­ ization.

To motivate the problem, consider the problem of resource allocation within a data center. The data center provides information technology resources to multiple organizations, each in a separate domain governed by a workload manager (WLM). Each WLM decides how to allocate resources in its domain to maintain quality of service (QoS) for each of a set of n classes of transactions.

The QoS specification for a transaction class c includes terms describing monetary payments or penalties as a func­ tion of the measured attributes of the service provided to that class by the data center. For simplicity, we shall consider here just a single attribute, the response time tc for class c. We de­ note the revenue function for class c (including all rewards and penalties) by rc(tc).

IBM T.J. Watson Research Center 19 Skyline Dr.

Hawthorne, NY 10532, USA

{ rajarshi, kephart, wwalshl }@us.ibm.com

In a real system, a WLM can adjust various parameters J for multiple resources. Here, we assume a single resource, with quantity L. Given fixed L, J, and class demand vector J, and assuming that the resources have no incremental costs, the expected total revenue is then:

A WLM's internal resource optimization problem is to find a feasible J that maximizes Eq. (1 ).

To handle fluctuations in client demand, a single provi­ sioner at the data center periodically reallocates resources among the WLMs. Denoting an individual WLM by i, the resource allocation problem for the provisioner is to compute:

The provisioner can compute (2) centrally if it has a good model of the internal operation of each WLM and can ob­ tain all relevant state information. In a real system however, the model and data necessary to compute Pr(tc) may be com­ plex and large. Moreover, in a system with transient, hetero­ geneous components (e.g., differently configured WLMs or different components altogether), the internal models of the components may simply not be available to the provisioner. In these cases, it is necessary to decentralize the resource al­ location problem. That is, WLMs would perform local com­ putations and send summary information to the provisioner.

A natural division of labor is to have each WLM send its entire U; curve, so that the provisioner can compute Eq. (2). Figure 1 shows an example of curves from two WLMs, each with two transaction classes. 1 The provisioner wishes to find the peaks of the aggregate curve, also shown.

2 Cooperative Negotiation

To compute its full U; curve, a WLM must solve Eq. (3) for each feasible L;. If each rc is in a computationally manage­ able form (e.g., piecewise linear or quadratic) and we have a simple model for tc (e.g., MIMI I queue), then computing each U;(L;) point may be tractable. However, in typical real sys­ tems the dependency of the service attributes upon resources and demand is likely to be sufficiently complex as to require a combination of optimization and simulation to compute each U; (L; ) point. Moreover, WLMs will often have substitutable and complementary preferences over different quantities of multiple goods, giving rise to large, expensive-to-compute, multidimensional U; curves. Such complexities would make it infeasible for a WLM to send its entire U; to the provisioner.

1 We computed the utility curves assuming a simple MIMI I queue model for each lc. L is the total service rate available, and the f c component of] indicates the fraction of L given to class c.

Instead, we propose to model the resource allocation prob­ lem as cooperative negotiation. In the context of auto­ nomic computing, cooperative negotiation is not simply non­ cooperative negotiation with the simplifying assumption that agents are non-strategic. Rather, the objective is to achieve the right balance between global optimization and negoti­ ation time. We are developing preference elicitation tech­ niques [Boutilier, 2002] to address this problem. We can view the negotiation for resources between the WLMs and the pro­ visioner as involving computation or "elicitation" of relevant parts of the U; curves.

Partial elicitation may be feasible in the case of negotiation among WLMs for different resource levels. It will often be possible to identify the region of Z-space in which the opti­ mal allocation lies without complete knowledge of these util­ ity functions. The provisioner could be given a small number of samples ofthe utility functions U;(L;) for WLMs i. Mak­ ing simple monotonicity assumptions, the provisioner could determine the region of allocation space in which the opti­ mal allocation lies. 2 For instance, having samples of the two (lower) U; curves in Figure I at points L; = {10, 15,20} for i = A,B, is sufficient to determine that the optimal allocation lies somewhere in the region LA E [10, 15] .

We are currently developing incremental utility elicitation procedures in which the provisioner gradually narrows down the region in which the optimal allocation lies until a decision which is guaranteed to be £-optimal is found . A rough sketch of one such procedure is presented here. Assume that each WLM has provided evaluations of its utility function U; at a set of m .sample points 1:} < 'T:T < ... 1:7'; we assume that 1:;" is the maximum value of L; and bounds U; under any allocation. With this small set of samples, the provisioner is assured that U;(1:1) :::; U;(L) :::; U;('T:1+i) for any 1:7 :::; L :::; 'T:k+i. Armed with this information, it is reasonably straightfor~ard to determine the maximum regret of any allocation l. Furthermore, we can also determine the allocation that has minimax regret given this incomplete knowledge of the utility function:

2 Monotonicity of U; seems natural, corresponding to a "free dis­ posal" assumption.

Here il; ranges over the set of utility functions U; consistent with the bounds above. Minimax regret is a reasonable er­ ror criterion, and the minimax-optimal allocation z· can be determined using a tractable series of linear programs.

Incremental elicitation arises when the minimax-optimal allocation has a max-regret level that is too high, say, greater than £. In this case, the provisioner does not have enough information about the U; curves to determine an allocation whose worst-case error is less than £; this necessitates addi­ tional samples of the U; curves. We have developed intelli­ gent query strategies that efficiently determine points L; for which knowledge of U;(L;) will "quickly" reduce minimax regret. Once sufficiently many points have been evaluated minimax regret will reach an acceptable level and an allo~ cation whose error is bounded by £ can be offered. We do recognize that the procedure becomes more complicated with multidimensional U; curves.

This procedure obviates the need for WLMs to compute their entire utility curves. The complex optimization required to determine U;(L) need only be applied by WLM i at a small collection of points; and these points are determined by the provisioner based on information about the utility functions of other WLMs. In this sense, such incremental elicitation techniques can truly be viewed as a form of collective nego­ tiation between WLMs and the provisioner.

We are exploring error criteria other than minimax regret in our general model. Optimization w.r.t. specific utility con­ straints, and determining queries that reduce error, would both require tailoring to the specific criterion adopted; but the same incremental framework still applies. For instance, if distributional information over the U; curves is available, Bayesian decision criteria could be used (e.g., an allocation that maximizes expected utility w.r.t. Pr(ii)).