10.4: DYNAMIC MULTIRESOURCE ASSIGNMENT

10.4 DYNAMIC MULTIRESOURCE ASSIGNMENT

We continue our investigation of a general revenue/penalty-based multiresource allocation problem by building upon the optimal routing and scheduling of server resources at a relatively fine time scale of the previous section and by focusing on the related control problem of optimal server assignments at a relatively coarse time scale. In particular, one of the key tasks of the hosting service provider is to allocate servers to each of the Web sites to satisfy the agreed upon QoS performance guarantees for the different classes of incoming requests at each point in time, while maximizing its profits. Doing so requires consideration of what might happen over multiple periods of time. However, the number of scenarios to which the system can transition in just a short amount of time grows quickly with the system dimensions, making it computationally infeasible to find the optimal control policy for dynamically assigning servers, as well as adding new servers, within the context of the set of SLAs. We propose a solution to the Web server allocation problem based on approximate dynamic programming and compare our algorithm against a deterministic policy that optimizes the allocation based on the average Web site traffic.

The remainder of the section is organized as follows. Aspects of our formal framework for the resource allocation problem are presented in Section 10.4.1.

We then formulate the server allocation problem in the Markov decision process framework in Section 10.4.2 and discuss applications of approximate linear programming in Section 10.4.3. We...