Caching system in Content Delivery Networks . In this problem we consider the simplest possible caching system.

Caching system in Content Delivery Networks.

In this problem we consider the simplest possible caching system. We suppose the system has the capability to store a single file, and the universe consists of two files, File 1 and 2. Each time slot it is assumed that some user, say in Austin, requests File 1 with probability α =1/3 and File 2 with probability 1−α. If the file requested is the same as that currently in the cache, it serves the user. Otherwise, the request is propagated to a storage facility in California and file is transmitted back to the user and replaces the the file currently in the cache. This is called a Last Recent Used (LRU) replacement strategy.

1. Model this system as a DTMC (Discrete Time Marcov Chain).

2. Find the invariant distribution for the steady state.

3. Based on the computed invariant distribution, find the probability of a cache hit, i.e., that a user request finds the file currently in the cache.

4. Pablo claims that this replacement strategy is poor. Instead, he suggests that the Most Frequently Used (requested) file fileshould be cached. Under this scheme; what is the probability of a cache hit?

5. In general caches can store many more files that a single one, and the decision to decide which files to store is more complex. Suppose that in fact there are F files, and that p(f) denotes the probability that file f is requested for f = 1,...F. For simplicity also suppose the files have been indexed in decreasing popularity, i.e., p(f) ≥ p(f +1) for f = 1,...F −1. Suppose the cache has a capacity C < F. Assuming requests are IID ( independent and identically distributed) determine the optimal caching strategy and find an expression for the cache hit probability.

6. Suppose the popularity profile remains the same as in the previous question, yet requests are no longer IID. Explain why a dynamic policy such as LRU, which upon a cache miss, replaces the least recently used file with the one just requested might beat the optimal strategy proposed in the previous question.