The cache location problem

This paper studies the problem of where to place network caches. Emphasis i s 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 o f caches in the network. We formulate these location problems both for general caches and for transp arent en-route caches (TERCs), and identify that, in general, they are intr actable. We give optimal algorithms for line and ring networks, and present dosed form formulae for some special cases. We also present a computationa lly efficient dynamic programming algorithm for the single server case. This last case is of particular practical interest. It models a network tha t wishes to minimize the average access delay for a single web server We ex perimentally study the effects of our algorithm using real web server data. We observe that a small number of TERCs are sufficient to reduce the netwo rk traffic significantly, Furthermore, there is a surprising consistency ov er 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 u sed by network providers to reduce traffic load in their network.