This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Tawarmalani, M. Articles by De, P. Search for Related Content

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

Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
mtawarma{at}purdue.edu
kkarthik{at}purdue.edu
pde{at}purdue.edu

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.

Key Words: collaborative cache management; resource sharing; peer-to-peer network; mathematical programming; game theory
History: Received: May 3, 2006;