Elsayed, Karim ; Rizk, Amr (2023)
Time-to-Live Caching With Network Delays: Exact Analysis and Computable Approximations.
In: IEEE/ACM Transactions on Networking, 31 (3)
doi: 10.1109/TNET.2022.3207914
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
We consider Time-to-Live (TTL) caches that tag every object in cache with a specific (and possibly renewable) expiration time. State-of-the-art models for TTL caches assume zero object fetch delay, i.e., the time required to fetch a requested object that is not in cache from a different cache or the origin server. Particularly, in cache hierarchies this delay has a significant impact on performance metrics such as the object hit probability. Recent work suggests that the impact of the object fetch delay on the cache performance will continue to increase due to the scaling mismatch between shrinking inter-request times (due to higher data center link rates) in contrast to processing and memory access times. In this paper, we analyze tree-based cache hierarchies with random object fetch delays and provide an exact analysis of the corresponding object hit probability. Our analysis allows understanding the impact of random delays and TTLs on cache metrics for a wide class of request stream models characterized through Markov arrival processes. This is expressed through a metric that we denote delay impairment of the hit probability. In addition, we analyze and extend state-of-the-art approximations of the hit probability to take the delay into account. We provide numerical and trace-based simulation-based evaluation results showing that larger TTLs do not efficiently compensate the detrimental effect of object fetch delays. Our evaluations also show that unlike our exact model the state-of-the-art approximations do not capture the impact of the object fetch delay well especially for cache hierarchies. Surprisingly, we show for single caches that the impact of the delay on the hit probability can be non-monotonic and that the range of delays for which a positive effect exists arises as a root of a polynomial in the ratio of the expected TTL to the expected inter-request time.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2023 |
| Autor(en): | Elsayed, Karim ; Rizk, Amr |
| Art des Eintrags: | Bibliographie |
| Titel: | Time-to-Live Caching With Network Delays: Exact Analysis and Computable Approximations |
| Sprache: | Englisch |
| Publikationsjahr: | 1 Juni 2023 |
| Verlag: | IEEE |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | IEEE/ACM Transactions on Networking |
| Jahrgang/Volume einer Zeitschrift: | 31 |
| (Heft-)Nummer: | 3 |
| DOI: | 10.1109/TNET.2022.3207914 |
| Kurzbeschreibung (Abstract): | We consider Time-to-Live (TTL) caches that tag every object in cache with a specific (and possibly renewable) expiration time. State-of-the-art models for TTL caches assume zero object fetch delay, i.e., the time required to fetch a requested object that is not in cache from a different cache or the origin server. Particularly, in cache hierarchies this delay has a significant impact on performance metrics such as the object hit probability. Recent work suggests that the impact of the object fetch delay on the cache performance will continue to increase due to the scaling mismatch between shrinking inter-request times (due to higher data center link rates) in contrast to processing and memory access times. In this paper, we analyze tree-based cache hierarchies with random object fetch delays and provide an exact analysis of the corresponding object hit probability. Our analysis allows understanding the impact of random delays and TTLs on cache metrics for a wide class of request stream models characterized through Markov arrival processes. This is expressed through a metric that we denote delay impairment of the hit probability. In addition, we analyze and extend state-of-the-art approximations of the hit probability to take the delay into account. We provide numerical and trace-based simulation-based evaluation results showing that larger TTLs do not efficiently compensate the detrimental effect of object fetch delays. Our evaluations also show that unlike our exact model the state-of-the-art approximations do not capture the impact of the object fetch delay well especially for cache hierarchies. Surprisingly, we show for single caches that the impact of the delay on the hit probability can be non-monotonic and that the range of delays for which a positive effect exists arises as a root of a polynomial in the ratio of the expected TTL to the expected inter-request time. |
| Fachbereich(e)/-gebiet(e): | 18 Fachbereich Elektrotechnik und Informationstechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik > Kommunikationstechnik DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > B: Adaptionsmechanismen DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > B: Adaptionsmechanismen > Teilprojekt B4: Planung |
| Hinterlegungsdatum: | 11 Okt 2023 07:50 |
| Letzte Änderung: | 31 Okt 2023 10:22 |
| PPN: | 512788162 |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum