30
IRUS Total
Downloads

Analyzing replacement policies in list-based caches with non-uniform access costs

File Description SizeFormat 
infocom.pdfAccepted version505.59 kBAdobe PDFView/Open
Title: Analyzing replacement policies in list-based caches with non-uniform access costs
Authors: Casale, G
Item Type: Conference Paper
Abstract: List-based caches can offer lower miss rates than single-list caches, but their analysis is challenging due to state-space explosion. We analyze in this setting randomized replacement policies for caches with non-uniform access costs. In our model, costs can depend on the stream a request originated from, the target item, and the list that contains it. We first show that, similarly to the uniform-cost case, the random replacement (RR) and first-in first-out (FIFO) policies can be exactly analyzed using a product-form expression for the equilibrium state probabilities of the cache. We then tackle the state space explosion by means of the singular perturbation method, deriving limiting expressions for the equilibrium performance measures as the number of items and the cache capacity grow in a fixed ratio. Simulations indicate that our asymptotic formulas rapidly converge to the cache equilibrium distribution.
Issue Date: 11-Oct-2018
Date of Acceptance: 27-Nov-2017
URI: http://hdl.handle.net/10044/1/54392
DOI: https://doi.org/10.1109/INFOCOM.2018.8485894
ISBN: 9781538641293
Publisher: IEEE
Journal / Book Title: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications
Copyright Statement: © 2018 The Authors.
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Commission of the European Communities
Funder's Grant Number: EP/L00738X/1
644869
Conference Name: IEEE International Conference on Computer Communications (INFOCOM) 2018
Publication Status: Published
Start Date: 2018-04-16
Finish Date: 2018-04-19
Conference Place: Honolulu, HI, USA
Online Publication Date: 2018-10-11
Appears in Collections:Computing
Faculty of Engineering