Cooperative Cashing? : An Economic Analysis of Document Duplication in Cooperative Web Caching

Cooperative caching is a popular mechanism to allow an array of distributed caches to cooperate and serve each others' web requests. Monitoring and controlling duplication of documents across cooperating caches is a challenging operational problem faced by cache managers. In this paper, we analyze optimal duplication in a game-theoretic setting with two cooperating caches. We have three primary findings. First, our results suggest that intermediate levels of duplication - greater than that of CARP, a protocol that allows no duplication, but less than that of ICP, a protocol that does not monitor duplication - are desirable. Second, the game is a game of strategic substitutes wherein an increase in duplication by one cache results in a decrease in duplication by the other. Thus, a cache that can credibly signal that it is incapable of monitoring duplication levels can get higher contribution from other caches i.e., get other caches to eliminate more duplicate documents. Finally, decentralized decision-making by selfish caches can be quite inefficient (i.e., result in higher average latency) relative to the socially optimal solution. At the same time, the socially optimal solution can be highly asymmetric even when caches are symmetric and thus may not be acceptable to the cache that has to contribute the most resources. These factors should be accounted for when contracts for cooperative caching are structured by independent ISPs