Graduate Studies
Markov Chain Analysis of Web Cache Systems under TTL-based Consistency
Abstract
dc:description.abstractCaching 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.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy (PhD)
- Discipline thesis:degree_discipline
- Electrical and Computer Engineering
- Grantor dc:publisher.institution
- Graduate Studies
- Year dc:date.issued
- 2013
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gomaa, Hazem
- Advisors dc:contributor.advisor
-
- Messier, Geoffrey
- Davies, Robert
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
- Language dc:language.iso
- eng