Distributed Caching Independent of the Network Size

摘要

We consider distributed caching strategies for networks in a model that takes in addition to remote accesses also local accesses into account. The goal is to minimize the congestion while obeying memory capacity constraints in the network. The on-line strategies are evaluated in a competitive analysis in which their costs are compared with the cost of an optimal off-line strategy. Previous results either depend on the network size or assume that the on-line strategies have increased memory capacity constraints in comparison to an optimal off-line strategy. Our main result is a strategy for complete networks. For each node v, we are given memory capacity m(v) and load d(v) for a remote access. The load for a local access is one. Note that, for uniform memory capacity TO and uniform load d for a remote access, the competitive ratio simplifies to O(log(min(d,m))). In addition, we give a lower bound which shows that the strategy is optimal in the uniform case. Furthermore, the impact of typical applications, i.e., those which exhibit significant locality of reference, is investigated. Finally, an universal caching strategy for arbitrary networks is presented which is based on a simulation of the strategy for complete networks. We show that the competitive ratio of this strategy depends primary on the routing capacity and degree of the network. Examples of networks, including Cayley and edge symmetric networks, are given for which the universal caching strategy achieves efficient competitive ratios.