[PhD Thesis] Resource Allocation Policies for Service Provisioning Systems (2006)

Author(s): Palmer JG

    Abstract: This thesis is concerned with maximising the efficiency of hosting of service provisioning systems consisting of clusters or networks of servers. The tools employed are those of probabilistic modelling, optimization and simulation. First, a system where the servers in a cluster may be switched dynamically and preemptively from one kind of work to another is examined. The demand consists of two job types joining separate queues, with different arrival and service characteristics, and also different relative importance represented by appropriate holding costs. The switching of a server from queue i to queue j incurs a cost which may be monetary or may involve a period of unavailability. The optimal switching policy is obtained numerically by solving a dynamic programming equation. Two heuristic policies (one static and one dynamic) are evaluated by simulation and are compared to the optimal policy. The dynamic heuristic is shown to perform well over a range of parameters, including changes in demand. The model, analysis and evaluation are then generalized to an arbitrary number, M, of job types. Next, the problem of how best to structure and control a distributed computer system containing many processors is considered. The performance trade-offs associated with different tree structures are evaluated approximately by applying appropriate queueing models. It is shown that, for a given set of parameters and job distribution policy, there is an optimal tree structure that minimizes the overall average response time. This is obtained numerically through comparison of average response times. A simple heuristic policy is shown to perform well under certain conditions. The last model addresses the trade-offs between reliability and performance. A number of servers, each of which goes through alternating periods of being operative and inoperative, offer services to an incoming stream of demands. The objective is to evaluate and optimize performance and cost metrics. A large real-life data set containing information about server breakdowns is analyzed first. The results indicate that the durations of the operative periods are not distributed exponentially. However, hyperexponential distributions are found to be a good fit for the observed data. A model based on these distributions is then formulated, and is solved exactly using the method of spectral expansion. A simple approximation which is accurate for heavily loaded systems is also proposed. The results of a number of numerical experiments are reported.

    Notes: British Lending Library DSC stock location number: DXN098061

      • Institution: School of Computing Science, University of Newcastle upon Tyne
      • Publication type: Report
      • Bibliographic status: Published