2016/02/27 by Marcin Bieńkowski, Marcin Bienkowski, Bienkowski, Marcin +8
Computer Science · Mathematics · #Cache #Caching and Content Delivery #Combinatorics #Computer network #Computer science #Context (archaeology) #Distributed systems and fault tolerance #Geography #Mathematics #Node (physics) #Optimization and Search Problems #Physics #Routing (electronic design automation) #Theoretical computer science #Tree (set theory) #Universe #cs.DS
paper · pdf · doi:10.48550/arxiv.1602.08563
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2016/02/27 · arxiv created 2017/05/14 · arxiv updated 2017/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate the study of a natural and practically relevant new variant of online caching where the to-be-cached items can have dependencies. We assume that the universe is a tree T and items are tree nodes; we require that if a node v is cached then the whole subtree T(v) rooted at v is cached as well. This theoretical problem finds an immediate application in the context of forwarding table optimization in IP routing and software-defined networks. We present an elegant online deterministic algorithm TC for this problem, and rigorously prove that its competitive ratio is O(height(T) * kALG/(kALG-kOPT+1)), where kALG and kOPT denote the cache sizes of an online and the optimal offline algorithm, respectively. The result is optimal up to a factor of O(height(T)).