Optimizing server placement in distributed systems in the presence of competition.pdf

J. Parallel Distrib. Comput. 71 (2011) 62–76Contents lists available at ScienceDirect J. Parallel Distrib. Comput. journal homepage: /locate/jpdc Optimizing server placement in distributed systems in the presence of competition Jan-Jan Wu a,b,?, Shu-Fan Shih a,c, Pangfeng Liu c, Yi-Min Chung c a Institute of Information Science, Academia Sinica, Taipei, Taiwan, ROC b Research Center for Information Technology Innovation, Academia Sinica, Taipei, Taiwan, ROC c Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC a r t i c l e i n f o Article history: Received 17 February 2010 Received in revised form 30 July 2010 Accepted 18 August 2010 Available online 16 September 2010 Keywords: Competition-aware server placement Resource allocation Distributed system Grid and Cloud Maximizing benefit Minimizing construction cost Optimal algorithms Heuristic algorithms a b s t r a c t Although the problem of data server placement in parallel and distributed systems has been studied extensively, most of the existing work assumes there is no competition between servers. Hence, their goal is to minimize read, update and storage cost. In this paper, we study the server placement problem in which a new server has to compete with existing servers for user requests. Therefore, in addition to minimizing cost, we also need to maximize the benefit of building a new server. Our major results include three parts. First, for tree-structured systems, we propose an O(|V |3k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a treewith |V | nodes.We also propose anO(|V |3) time dynamic programming algorithm to find the optimal placement of extra servers that maximizes the benefit, without any constraint on the number of extra servers. Second, for general connected graphs, we prove that the server placement problems are NP-complete, and present three greedy heuristic algorithms, ca