Allocating Objects in a Network of Caches: Centralized and Decentralized Analyses

• 成果类型: Article
• 署名作者: Tawarmalani, Mohit; Kannan, Karthik; De, Prabuddha
• 署名单位: Purdue University System; Purdue University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1080.0923
• 发表日期: 2009
• 页码: 132-147
• 关键词: collaborative cache management; Resource sharing; peer-to-peer network; mathematical programming; game theory

摘要

We analyze the allocation of objects in a network of caches that collaborate to service requests from customers. A thorough analysis of this problem in centralized and decentralized setups, both of which occur in practice, is essential for understanding the benefits of collaboration. A key insight offered by this paper is that an efficient implementation of cooperative cache management is possible because, in the centralized scenario, the object allocation resulting in the best social welfare can be found easily as a solution to a transportation problem. For the decentralized scenario involving selfish caches, it is shown that pure equilibria exist and that the cache network always reaches a pure equilibrium in a finite number of steps, starting from any point in the strategy space. An auction mechanism is developed to derive prices that motivate the caches to hold objects in a manner such that the optimal social welfare is attained. In the special case of symmetric caches, simple algorithms are devised to find the optimal social welfare allocation, the best pure equilibrium, and the prices for sharing objects. The results obtained in this paper should be valuable in developing and evaluating cache-management policies. Resource-sharing problems with a similar cost structure exist in a variety of other domains, and the insights gained here are expected to extend to those scenarios as well.