Files in this item
Files | Description | Format |
---|---|---|
application/pdf ![]() | (no description provided) |
Description
Title: | A Lyapunov analysis of LRU |
Author(s): | Brenner, Michael |
Advisor(s): | Srikant, Rayadurgam |
Department / Program: | Electrical & Computer Eng |
Discipline: | Electrical & Computer Engr |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Degree: | M.S. |
Genre: | Thesis |
Subject(s): | Lyapunov
Control Thoery Stochastic Systems Cache LRU Least recently used Markov Chain TTL |
Abstract: | Caches are segments of memory that store requested information in a system subject to a set of decision rules, defined as the caching algorithm. One of the most popular caching algorithms is the least recently used algorithm (LRU) due to its simplicity and effectiveness in a multitude of applications. LRU caches operate by storing objects in the order that they were most recently requested. Further, whenever an item is requested that is not currently in the cache, the requested item is placed at the head of the cache, and the least recently requested item is evicted. Many have suggested a tie between the performance of an LRU cache and a time to live (TTL) cache. In this thesis, we present a unique Lyapunov based proof for an asymptotically exact TTL approximation for the steady state distribution of our LRU Markov model. We further present ongoing theoretical extensions to other variants of LRU, as well as simulations that validate our model. We conclude by proposing a variance corrected model to better approximate hit rate over time. |
Issue Date: | 2020-05-11 |
Type: | Thesis |
URI: | http://hdl.handle.net/2142/107992 |
Rights Information: | Copyright 2020 Michael Brenner |
Date Available in IDEALS: | 2020-08-26 |
Date Deposited: | 2020-05 |
This item appears in the following Collection(s)
-
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering -
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois