A Decentralized Caching Algorithm with Multiplicative Rate Improvement
03 January 2013
Caching (placing) popular contents in memories distributed in the network, closer to the end users, is a technique to reduce the peak-traffic rates. Conventionally, the main advantage of caching was to make part of the requested data locally available. In this paper, we proposed an algorithm which not only offers the gain of the conventional scheme, but also offers an additional gain which reduces the peak-rate significantly, up to the order of number of users. The additional gain relies on creating simultaneous multicasting opportunity, meaning that the server can form messages which are useful for more than one users, for any possible set of demands, even though users have asked for different files. The proposed algorithm has an important feature: the placement phase is performed in a decentralized fashion, without any coordination among the users, and even independent of the set and the number of the active users which share a bottle-neck link in the delivery phase. Nevertheless, still the performance of the algorithm is proved to be within a multiplicative gap of the optimality. As a result, the algorithm can optimality handle users with asynchronous demand and in a flexible topology.
