Optimal Lower Bound: OPT-LB

We now introduce a very simple and practical offline algorithm called OPT-LB, which provides a very close lower bound on optimal multi-level caching performance. A better performing policy will have to demonstrate either lower average response time or lower inter-cache bandwidth usage. OPT-LB is the best known off-line multi-level caching policy that we are aware of.

The basic idea is to apply Belady's OPT algorithm in a cascaded fashion. We start with the highest cache level, $C_1$, and apply OPT to the request sequence $\sigma_1$, assuming a single cache scenario. We note the misses from $C_1$ with their timestamps and prepare another request sequence, $\sigma_2$, for the lower cache $C_2$. We repeat the same process at $C_2$, in turn generating $\sigma_3$. This is performed for each level and we keep a count of hits obtained at every level.

In other words, $h_i = hitOPT(\sigma_i, S_i)$ and $\sigma_{i+1} = traceOPT(\sigma_i, S_i)$, where $traceOPT$ is a trace of the misses when OPT is applied to the given request stream and cache size.

Once each level has learned its $\sigma_i$, all cache levels can operate together replicating the result in real-time. Since this can be done practically, this policy by definition serves as the lower bound for the offline optimal along any performance metric. Note that OPT-LB does not require any demotions or reloads from disks. Even though OPT-LB does not guarantee exclusivity of caches, we experimentally confirm that OPT-LB is indeed a very close lower bound for offline optimals for both average response time and inter-cache bandwidth usage in multi-level caches.