Generalized connection caching
Susanne Albers · 2000
Cohen et al. [5] recently initiated the theoretical study of connection caching in the world-wide web. They extensively studied uniform connection caching, where the establishment cost is uniform for all connections [5, 6]. They showed that ordinary paging algorithms can be used to derive algorithms for uniform connection caching and analyzed various algorithms such as Belady's rule, LRU and Marking strategies. In particular, in [5] Cohen et al. showed that LRU yields a (2k - 1)-competitive algorithm, where k is the size of the largest cache in the network. In [6], they investigated Marking algorithms with different types of communication among nodes and presented deterministic k-competitive algorithms.