Asymptotically Tight Approximation for Online File Caching With Delayed Hits and Bypassing
Haisheng Tan, Yi Wang, Chi Zhang, Guopeng Li, Haohua Du, Zhenhua Han, Shaofeng H.-C. Jiang, Xiang‐Yang Li · IEEE Transactions on Networking · 2025
In latency-sensitive file caching systems such as Content Delivery Networks (CDNs) and Mobile Edge Computing (MEC), the latency of fetching a missing file to the local cache can be significant. Recent studies have revealed that successive requests for the same missing file before the fetching process completes could still suffer latency (so-called delayed hits). Motivated by the practical scenarios, we study the online general file caching problem with delayed hits and bypassing,i.e., a request may be bypassed and processed directly at the remote data center. The objective is to minimize the total request latency. We present a general reduction that turns a traditional file caching algorithm into one that can handle delayed hits. Based on this reduction, we propose an efficient online file caching algorithm, calledCaLa, with an asymptotically tight competitive ratio as$O(Z \log K)$, whereZis the maximum fetching latency of any file andKis the cache size. Extensive simulations on the production data trace from Google and the Yahoo benchmark illustrate thatCaLacan reduce the latency by up to 8.48% compared with the state-of-the-art schemes dealing with delayed hits without bypassing, and this improvement increases to 26.00% if bypassing is allowed. Furthermore, by upgrading the method for estimating files’ weights inCaLa, we proposeCaLa+, which further reduces the total latency by more than 5%.