The Cache Location Problem

(Title was originally Transparent En-Route Cache Location) Caching improves network and system performance for WWW browsing. The way caches are currently deployed requires clients or caches to be aware of the location of nearby caches. This creates management and configuration problems, which may also lead to performance bottlenecks. In contrast, Transparent en-route caches (TERC) are devices that are placed at appropriate locations within the network and work obliviously. A TERC intercepts web requests and web data. If the requested item exists in the TERC's memory, the data is sent to the requester, otherwise the request is transparently forwarded up the routing path. In this work, we study the important problems of where to place network caches, and in particular, TERCs. We identify that the location at which the caches are placed play a prime role in the resulting traffic and load reduction. We formulate the location problems both for general caches and TERCs, and show that in general they are intractable.