Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1996-01-01

Filename

WUCS-96-25.PDF

Technical Report Number

WUCS-96-25

Abstract

We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm that we provided in [5]. These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer optimal but is competitive. We also prove that LRU remains competitive in the generalized case. This is an extension of a famous results by Sleator and Tarjan [12] on LRU. Finally, it is confirmed in the general case that prefetch does not reduce the total cost if "cost" reflects only the number of bytes transmitted.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7JQ0Z75

Download

Share

COinS