Resource management in large-scale services: models and algorithms
Dan Rubenstein, Daniel Antunes Maciel Villela · 2005
Many of the services in today's Internet (e.g. file transfer, streaming media, auctions) are offered by companies that either own or lease a fixed, static set of server resources to host these services. Under such a structure, a company can provision their serving resources for its typical loads or to conservatively handle peak demands. Either way has drawbacks. In the former, poor performance is expected when peaks of demand occur. In the latter, costly resources remain idle most of the time. This thesis explores provisioning alternatives that use pools of servers in novel ways that permit provisioning for typical loads but can still accommodate peak demands. Three specific problems are explored by constructing mathematical models and analyzing these models. First, we explore benefits for independent companies from pooling together of their own servers to jointly serve data delivery. This data may have real-time requirements (e.g., multimedia), or it may be elastic (e.g., file transfer). We show that such pooling can simultaneously benefit all companies participating in this arrangement, but that it is necessary for these companies to have similar demands and to offer similar quantities of serving resources. Second, we explore how to reduce transaction times for transaction-oriented services, such as an auction website. If such a service is replicated across multiple servers, these servers must be kept consistent, and replicating the service across many servers will do more harm than good, as the cost to maintain consistency will offset the gains made from distributing the load. We explore the performance of heuristic-based algorithms that identify provisionings that are close to optimal. Last, we consider a general provisioning problem for a business that owns a server farm, and must decide how to allocate its fixed pool of servers among a set of independent companies that offer transaction-oriented services. The optimal allocation is a function of the loads imposed by each company, the profit each company offers for a successful transaction, and the cost that the server farm must pay for each failed transaction. We derive three approximation methods for partitioning the fixed set of servers among the various companies.