Learning Relaxed Belady for Content Distribution Network Caching


Zhenyu Song, Princeton University; Daniel S. Berger, Microsoft Research & Carnegie Mellon University; Kai Li and Wyatt Lloyd, Princeton University


This paper presents a new approach for caching in CDNs that uses machine learning to approximate the Belady MIN algorithm. To accomplish this complex task, we introduce the Relaxed Belady algorithm, the Belady boundary, and the good decision ratio that inform the design of Learning Relaxed Belady (LRB). LRB addresses the necessary system 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 inference paths.

We implement an LRB simulator and a prototype within Apache Traffic Server. Our simulation using 6 production CDN traces show LRB reduces WAN traffic compared to a typical production CDN cache design by 5–24%, 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.

NSDI '20 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {246346,
author = {Zhenyu Song and Daniel S. Berger and Kai Li and Wyatt Lloyd},
title = {Learning Relaxed Belady for Content Distribution Network Caching },
booktitle = {17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)},
year = {2020},
isbn = {978-1-939133-13-7},
address = {Santa Clara, CA},
pages = {529--544},
url = {https://www.usenix.org/conference/nsdi20/presentation/song},
publisher = {USENIX Association},
month = feb

Presentation Video