Back to search

Graduate Studies

Markov Chain Analysis of Web Cache Systems under TTL-based Consistency

Abstract

dc:description.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.

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 × 1

Rights

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

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Calgary
Base URL
ucalgary.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gomaa, Hazem. Markov Chain Analysis of Web Cache Systems under TTL-based Consistency. Graduate Studies, 2013. http://hdl.handle.net/11023/596