Open Access
- 24 July 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 329-338
Abstract
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) * k_ALG/(k_ALG-k_OPT+1)), where k_ALG and k_OPT 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)).Keywords
Funding Information
- Polish National Science Centre (DEC-2013/09/B/ST6/01538, 2016/22/E/ST6/00499)
This publication has 32 references indexed in Scilit:
- Leveraging Zipf's law for traffic offloadingACM SIGCOMM Computer Communication Review, 2012
- Randomized Competitive Algorithms for Generalized CachingSIAM Journal on Computing, 2012
- Achieving sub-second IGP convergence in large IP networksACM SIGCOMM Computer Communication Review, 2005
- Online companion cachingTheoretical Computer Science, 2004
- On-Line File CachingAlgorithmica, 2002
- Thek-server dual and loose competitiveness for pagingAlgorithmica, 1994
- Competitive paging algorithmsJournal of Algorithms, 1991
- A strongly competitive randomized paging algorithmAlgorithmica, 1991
- New Ressults on Server ProblemsSIAM Journal on Discrete Mathematics, 1991
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985