Markov Chain Analysis of Web Cache Systems under TTL-based Consistency
Date
2013-04-10
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Caching plays a crucial role in improving Web-based services. The basic idea of Web
caching is to satisfy the user’s requests from a nearby cache, rather than a faraway
origin server (OS). This reduces the user’s perceived latency, the load on the OS, and
the network bandwidth consumption.
This dissertation introduces a new analytical model for estimating the cache hit
ratio as a function of time. The cache may not reach the steady state hit ratio
(SSHR) when the number ofWeb objects, object popularity, and/or caching resources
themselves are subject to change. Hence, the only way to quantify the hit ratio
experienced by users is to calculate the instantaneous hit ratio (IHR). The proposed
analysis considers a single cache with either infinite or finite capacity. For a cache
with finite capacity, two replacement policies are considered: first-in-first-out (FIFO)
and least recently used (LRU). In addition, the proposed analysis accounts for the use
of two variants of the time-to-live (TTL) weak consistency mechanism. The first is
the typical TTL (TTL-T), specified in the HTTP/1.1 protocol, where expired objects
are refreshed using conditional GET requests. The second is TTL immediate ejection
(TTL-IE) whereby objects are ejected as soon as they expire. Based on the insights
from the analysis, a new replacement policy named frequency-based-FIFO (FB-FIFO)
is proposed. The results show that FB-FIFO achieves a better IHR than FIFO and
LRU.
Furthermore, the analytical model of a single cache is extended for characterizing
the instantaneous average hit distance (IAHD) of two cooperative Web caching systems, distributed and hierarchical. In these systems, the analysis considers fixed
caches that are always connected to the network, and temporary caches that randomly
join and leave the network. In the distributed cache system, the analysis
considers caches that cooperate via Internet cache protocol (ICP). In the hierarchical
cache system, the analysis accounts for two sharing protocols: leave copy everywhere
(LCE) and promote cached objects (PCO), which is a new protocol that is introduced
in this dissertation. The results show that PCO outperforms LCE in terms of the
IAHD, especially under TTL-T.
Description
Keywords
Engineering--System Science
Citation
Gomaa, H. (2013). Markov Chain Analysis of Web Cache Systems under TTL-based Consistency (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/26833