IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v83y2016i3d10.1007_s11134-016-9487-9.html
   My bibliography  Save this article

Transient and steady-state regime of a family of list-based cache replacement algorithms

Author

Listed:
  • Nicolas Gast

    (Inria, Univ. Grenoble Alpes, CNRS, LIG)

  • Benny Houdt

    (University of Antwerp - iMinds)

Abstract

We study the performance of a family of cache replacement algorithms. The cache is decomposed into lists. Some of these lists can be virtual in the sense that only meta-data are stored in those lists. An item enters the cache via the first list and jumps to the next list whenever a hit on it occurs. The classical policies FIFO, RANDOM, CLIMB, and its hybrids are obtained as special cases. We present explicit expressions for the cache content distribution and miss probability under the IRM model. We develop an algorithm with a time complexity that is polynomial in the cache size and linear in the number of items to compute the exact miss probability. We introduce lower and upper bounds on the latter that can be computed in a time that is linear in the cache size times the number of items. We introduce a mean-field model to approximate the transient behavior of the miss probability and prove that this model becomes exact as the cache size and number of items go to infinity. We show that the set of ODEs associated to the mean-field model has a unique fixed point that can be used to approximate the miss probability in case the exact computation is too time consuming. Using this approximation, we provide guidelines on how to select a replacement algorithm within the family considered such that a good trade-off is achieved between the cache reactivity and its steady-state hit probability. We simulate these cache replacement algorithms on traces of real data and show that they can outperform LRU. Finally, we also disprove the well-known conjecture that the CLIMB algorithm is the optimal finite-memory replacement algorithm under the IRM model.

Suggested Citation

  • Nicolas Gast & Benny Houdt, 2016. "Transient and steady-state regime of a family of list-based cache replacement algorithms," Queueing Systems: Theory and Applications, Springer, vol. 83(3), pages 293-328, August.
    • Handle: RePEc:spr:queues:v:83:y:2016:i:3:d:10.1007_s11134-016-9487-9
    DOI: 10.1007/s11134-016-9487-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-016-9487-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-016-9487-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ryo Hirade & Takayuki Osogami, 2010. "Analysis of Page Replacement Policies in the Fluid Limit," Operations Research, INFORMS, vol. 58(4-part-1), pages 971-984, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.

      Corrections

      All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:83:y:2016:i:3:d:10.1007_s11134-016-9487-9. See general information about how to correct material in RePEc.

      If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

      If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

      If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

      For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

      Please note that corrections may take a couple of weeks to filter through the various RePEc services.

      IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.