Non-renewal TTL-based Cache Replacement Policy and Applications: Case of Modern DNS Hierarchy

Caching is undoubtedly one of the most popular solution that easily scales up with a world-wide deployment of resources. Records in Domain Name System (DNS) caches are kept for a pre-set duration (time-to-live or TTL) to avoid becoming outdated. "Modern" caches are those that set locally the TTL regardless of what authoritative servers say. In this report, we introduce analytic models to study the modern DNS cache behavior based on renewal arguments. For both the single cache case and the network of caches case, we derive the cache performance metrics and characterize at each cache the miss process and the aggregate request process. We address the problem of the optimal caching duration and find that if inter-request times have a concave CDF, then the deterministic policy is the best. We validate our single cache model using real DNS traces and our network of caches model using event-driven simulations. Our models consider general caching durations and are tested with deterministic, hypo-exponential, exponential and hyper-exponential distributions. Our models are very robust as the relative error between empirical and analytic values stays within 1% in the first case and within 5% at the highest cache level in the network case. Our models successfully predict the CDF of the miss process even when the renewal assumption is not met.