在許多內容傳遞情境中，常使用內容傳遞網路（CDN）技術，將內容存放於靠近使用者的邊緣節點，以縮短傳輸距離、提升使用者體驗、降低來源站負載與頻寬成本等。為了充分發揮 CDN 快取效益，提升節點之物件命中率（Object Hit Rate, OHR）為一項重要課題。然而，由於CDN快取情境中物件大小差異巨大，若缺乏適當的准入機制容易發生低價值的大型物件進入快取造成大量污染，進而降低整體命中率，因此設計有效之准入策略顯得相當重要。
本研究提出一種基於自適應大小分區成本估計的快取准入策略。該方法將物件依大小劃分為多個區間，並以物件大小與重用距離（reuse distance）之乘積作為成本指標，透過指數移動平均（Exponential Moving Average, EMA）在線更新各大小區間之成本估計，再據此進行以成本為依據的准入決策。
為公平評估准入策略本身之效果，本研究固定替換策略（eviction policy）為LRU，僅比較不同准入策略(admission policy)所帶來的影響。本篇實驗結果顯示，本方法在所有比較方法中具有最佳的 OHR，且在執行效率方面僅次於 LRU 與 AdaptSize。此外，透過消融實驗分析，本研究驗證了各設計元件對整體效能之影響，結果顯示所提出方法之設計具有一致且穩定的效益。整體而言，本方法在維持低計算成本與線上運作能力的前提下，能有效提升 CDN 快取系統之命中率。

In recent years, Content Delivery Networks (CDNs) have become an essential infrastructure for supporting large-scale Internet services. However, due to the high heterogeneity of object sizes in CDN caching environments, without an effective admission mechanism, low-value large objects may enter the cache and cause cache pollution, thereby reducing the overall Object Hit Rate (OHR). Therefore, designing a cache admission policy that achieves both high hit rate and low computational cost has become an important research issue.
This study proposes RCA (Region-based Cost Admission), a CDN cache admission policy based on adaptive size-partitioned cost estimation. RCA partitions objects into multiple regions according to their sizes and defines the product of object size and reuse distance as the cost metric. An Exponential Moving Average (EMA) mechanism is adopted to update the estimated cost of each size region online, enabling cost-oriented admission decisions.
Experimental results show that RCA achieves the best Object Hit Rate (OHR) among all compared online methods and approaches the performance upper bound of the offline optimal method. In addition, this study conducts ablation studies to analyze the impact of different design components on overall performance, including cost representation, threshold estimation, probabilistic admission mechanisms, and cost aging mechanisms.
Overall, RCA effectively improves cache system performance under highly heterogeneous CDN workloads while maintaining good online operation capability.

[1] J. Dilley, B. Maggs, J. Parikh, H. Prokop, R. K. Sitaraman and B. Weihl, "Globally Distributed Content Delivery", IEEE Internet Computing, vol. 6, no. 5, pp. 50-58, Sep 2002.
[2] A.-M. K. Pathan and R. Buyya, "A Taxonomy and Survey of Content Delivery Networks," Grid Computing and Distributed Systems Laboratory, University of Melbourne, Australia, Technical Report GRIDS-TR-2007-4, pp. 1-44, Feb. 2007.
[3] J. Chen, T. Wo, J. Hu, C. Lin, and Y. Zhang, "A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications," IEEE Access, vol. 5, pp. 3902-3922, Mar. 2017.
[4] M. Arlitt, R. Friedrich and T. Jin, "Performance Evaluation of Web Proxy Caching," Performance Evaluation, vol. 36, pp. 143-164, Aug. 1999.
[5] J. Wang, "A Survey of Web Caching Schemes for the Internet", ACM SIGCOMM Computer Communication Review, vol. 29, no. 5, pp. 36-46, Oct 1999.
[6] G. Einziger, R. Friedman, and B. Manes, "TinyLFU: A Highly Efficient Cache Admission Policy," ACM Transactions on Storage (TOS), vol. 13, no. 4, pp. 1-31, Dec. 2017.
[7] V. Kirilin, A. Sundarrajan, S. Gorinsky and R. K. Sitaraman, "RL-Cache: Learning-Based Cache Admission for Content Delivery", NetAI'19: Proceedings of the 2019 Workshop on Network Meets AI & ML, pp. 1-6, Aug 2019.
[8] D. S. Berger, R. K. Sitaraman and M. Harchol-Balter, "AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network", Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI '17), pp. 483-498, Mar 2017.
[9] G. Vietri, L. V. Rodriguez, W. A. Martinez, S. Lyons, J. Liu, R. Rangaswami, M. Zhao and G. Narasimhan, "Driving Cache Replacement with ML-based LeCaR", Proceedings of the 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), pp. 1-6, July 2018.
[10] Z. Song, D. S. Berger, K. Li and W. Lloyd, "Learning Relaxed Belady for Content Distribution Network Caching", Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI '20), pp. 529-544, Feb 2020.
[11] P. Wang, Y. Liu, Z. Zhao, K. Zhou, Z. Huang and Y. Chen, "Adaptive Size-Aware Cache Insertion Policy for Content Delivery Networks", 2022 IEEE 40th International Conference on Computer Design (ICCD), pp. 195-202, Oct 2022.
[12] M. Z. Shafiq, A. X. Liu and A. R. Khakpour, "Revisiting Caching in Content Delivery Networks", Proceedings of the 2014 ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '14), pp. 567-568, Jun 2014.
[13] L. Breslau, P. Cao, L. Fan, G. Phillips and S. Shenker, "Web Caching and Zipf-like Distributions: Evidence and Implications", IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 126-134, Mar. 1999.
[14] D. A. Patterson and J. L. Hennessy, "Computer Organization and Design MIPS Edition: The Hardware/Software Interface", 6th ed., Morgan Kaufmann, Nov 2020.
[15] V. Almeida, A. Bestavros, M. Crovella and A. de Oliveira, "Characterizing Reference Locality in the WWW," Proceedings of the 4th International Conference on Parallel and Distributed Information Systems (PDIS '96), pp. 92-103, Dec. 1996.
[16] L. Cherkasova, "Improving WWW Proxies Performance with Greedy-Dual-Size-Frequency Caching Policy", HP Laboratories Technical Report, pp. 1-14, Nov 1998.
[17] Y. Guan, X. Zhang, and Z. Guo, "CACA: Learning-based Content-aware Cache Admission for Video Content in Edge Caching," in Proc. ACM Multimedia (MM), 2019, pp. 1020–1028.
[18] Q. Fan, X. Li, J. Li, Q. He, K. Wang, and J. Wen, "PA-Cache: Evolving Learning-Based Popularity-Aware Content Caching in Edge Networks," IEEE Transactions on Network and Service Management, vol. 18, no. 2, pp. 1746–1760, Jun. 2021.
[19] K. Liu, K. Wu, H. Wang, K. Zhou, P. Wang, J. Zhang, and C. Li, "SLAP: Segmented Reuse-Time-Label Based Admission Policy for Content Delivery Network Caching," ACM Transactions on Architecture and Code Optimization, vol. 21, no. 2, 2024.
[20] J. Yang, Z. Mao, Y. Yue, and K. V. Rashmi, "GL-Cache: Group-level Learning for Efficient and High-performance Caching," in Proc. USENIX FAST, pp. 115-133, 2023.
[21] A. Narayanan, S. Verma, E. Ramadan, P. Babaie, and Z.-L. Zhang, "Making Content Caching Policies ‘Smart’ using the DeepCache Framework," in Proc. ACM SIGCOMM Workshop (NetAI), pp. 48-53, 2018.
[22] R. L. Mattson, J. Gecsei, D. R. Slutz and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Systems Journal, vol. 9, no. 2, pp. 78-117, 1970.
[23] N. Megiddo and D. S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache," Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST '03), vol. 3, pp. 115-130, Mar. 2003.
[24] P. Cao and S. Irani, "Cost-Aware WWW Proxy Caching Algorithms," in Proc. USENIX Symposium on Internet Technologies and Systems (USITS), pp. 1-14, Dec. 1997.
[25] L. A. Belady, "A study of replacement algorithms for a virtual-storage computer," IBM Systems Journal, vol. 5, no. 2, pp. 78-101, Jun. 1966.
[26] A. Jain and C. Lin, "Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement," Proceedings of the 43rd ACM/IEEE Annual International Symposium on Computer Architecture (ISCA '16), pp. 78-89, Jun. 2016.
[27] G. K. Zipf, "Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology", Addison-Wesley Press, 1949.
[28] D. S. Berger, N. Beckmann, and M. Harchol-Balter, "Practical Bounds on Optimal Caching with Variable Object Sizes," Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS), vol. 2, no. 2, pp. 1–38, Jun. 2018.
[29] M. E. Crovella and A. Bestavros, "Self-similarity in World Wide Web traffic: evidence and possible causes," IEEE/ACM Transactions on Networking, vol. 5, no. 6, pp. 835-846, Dec. 1997.
[30] J. Quiñonero-Candela, M. Sugiyama, A. Schwaighofer and N. D. Lawrence, "Dataset Shift in Machine Learning", MIT Press, 2009.