The cache location problem
The cache location problem
复制标题
DOI：
10.1109/90.879344
复制
发表时间：
2000-10-01
影响因子：
3.7
通讯作者：
Shavitt, Y
中科院分区：
文献类型：
--
作者：
Krishnan, P;Raz, D;Shavitt, Y
本文研究了网络缓存的位置问题。重点是对客户端透明的缓存，因为它们更容易管理，并且不需要客户端的合作。我们的目标是通过在网络中放置给定数量的缓存来最小化总流量或平均延迟，我们制定了这些位置问题，一般缓存和透明的途中缓存（TERC），并确定，在一般情况下，他们是棘手的。给出了线网和环网的优化算法，并对某些特殊情况给出了封闭式公式。我们也提出了一个计算效率高的动态规划算法的单服务器的情况下。这最后一种情况是特别实际的兴趣。它模拟了一个网络，希望最大限度地减少平均访问延迟为一个单一的Web服务器我们实验研究我们的算法使用真实的Web服务器数据的影响。我们观察到，少量的TERC就足以显著减少网络流量。此外，随着时间的推移，来自服务器沿着路径的Web流量的相对量具有惊人的一致性，从而为我们的TERC定位解决方案提供了稳定性。我们的技术可用于网络提供商，以减少其网络中的流量负载。
This paper studies the problem of where to place network caches. Emphasis is given to caches that are transparent to the clients since they are easier to manage and they require no cooperation from the clients. Our goal is to minimize the overall flow or the average delay by placing a given number of caches in the network.We formulate these location problems both for general caches and for transparent en-route caches (TERCs), and identify that, in general, they are intractable. We give optimal algorithms for line and ring networks, and present dosed form formulae for some special cases. We also present a computationally efficient dynamic programming algorithm for the single server case.This last case is of particular practical interest. It models a network that wishes to minimize the average access delay for a single web server We experimentally study the effects of our algorithm using real web server data. We observe that a small number of TERCs are sufficient to reduce the network traffic significantly, Furthermore, there is a surprising consistency over time in the relative amount of web traffic from the server along a path, lending a stability to our TERC location solution. Our techniques can be used by network providers to reduce traffic load in their network.