Performance analysis methods for list-based caches with non-uniform access
File(s)
Supplementary information
Author(s)
Casale, Giuliano
Gast, Nicolas
Type
Journal Article
Abstract
List-based caches can offer lower miss rates than single-list caches, but their analysis is challenging due to state space explosion. In this setting, we propose novel methods to analyze performance for a general class of list-based caches with tree structure, non-uniform access to items and lists, and random or first-in first-out replacement policies. Even though the underlying Markov process is shown to admit a product-form solution, this is difficult to exploit for large caches. Thus, we develop novel approximations for cache performance metrics, in particular by means of a singular perturbation method and a refined mean field approximation. We compare the accuracy of these approaches to simulations, finding that our new methods rapidly converge to the equilibrium distribution as the number of items and the cache capacity grow in a fixed ratio. We find that they are much more accurate than fixed point methods similar to prior work, with mean average errors typically below 1.5% even for very small caches. Our models are also generalized to account for synchronous requests, fetch latency, and item sizes, extending the applicability of approximations for list-based caches.
Date Issued
2021-04-01
Date Acceptance
2020-12-02
Citation
IEEE ACM Transactions on Networking, 2021, 29 (2), pp.651-664
ISSN
1063-6692
Publisher
Institute of Electrical and Electronics Engineers
Start Page
651
End Page
664
Journal / Book Title
IEEE ACM Transactions on Networking
Volume
29
Issue
2
Copyright Statement
© 2020 IEEE. This is the Accepted Manuscript version of a published work that appeared in final form in IEEE/ACM Transactions on Networking, https://doi.org/10.1109/TNET.2020.3042869. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Sponsor
Commission of the European Communities
Identifier
https://ieeexplore.ieee.org/document/9298963
Grant Number
825040
Subjects
Networking & Telecommunications
0805 Distributed Computing
0906 Electrical and Electronic Engineering
1005 Communications Technologies
Publication Status
Published
Date Publish Online
2020-12-18