language: en

Optimal Solution of Off-line and On-line Generalized Caching

Saied Hosseini-Khayat and Jerome R. Cox, Jr.
Washington University in St. Louis

Abstract. Network traffic can be reduced significantly if caching is utilized effectively. As an effort in this direction we study the replacement problem that arises in caching of multimedia objects. The size of objects and the cost of cache misses are assumed non-uniform. The non-uniformity of size is inherent in multimedia objects, and the non-uniformity of cost is due to the non-uniformity of size and the fact that the objects are scattered throughout the network. Although a special case of this problem, i.e. the case of uniform size and cost, has been extensively studied, the general case needs a great deal of study. We present a dynamic programming method of optimally solving the off-line and on-line versions of this problem, and discuss the complexity of this method.

Key words: Generalized caching, network traffic, network caching, file caching, optimal replacement, replacement algorithm.

I. Introduction