PDL Abstract

Learning Relaxed Belady for Content Distribution Network Caching

17th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’20). February 25–27, 2020. Santa Clara, CA.

Zhenyu Song2, Daniel S. Berger1,3, Kai Li2, Wyatt Lloyd2

1 Carnegie Mellon University
2 Princeton University
3 Microsoft Research


This paper presents a new approach for caching in CDNs that uses machine learning to approximate the Belady MIN (oracle) algorithm. To accomplish this complex task, we propose a CDN cache design called Learning Relaxed Belady (LRB) to mimic a Relaxed Belady algorithm, using the concept of Belady boundary. We also propose a metric called good decision ratio to help us make better design decisions. In addition, the paper addresses several challenges to build an end-to-end machine learning caching prototype, including how to gather training data, limit memory overhead, and have lightweight training and prediction.

We have implemented an LRB simulator and a prototype within Apache Traffic Server. Our simulation results with 6 production CDN traces show that LRB reduces WAN traffic compared to a typical production CDN cache design by 4–25%, and consistently outperform other state-of-the-art methods. Our evaluation of the LRB prototype shows its overhead is modest and it can be deployed on today’s CDN servers.