Analysis of TTL-based Cache Networks

Voir aussi actes de la conférence : ValueTools - 6th International Conference on Performance Evaluation Methodologies and Tools - 2012 (2012) (http://hal.inria.fr/hal-00760915)This paper provides building blocks for the performance evaluation of Content Centric-like Networks (CCNs). In CCNs if a cache receives a request for a content it does not store ({\em miss}), it forwards the request to a higher-level cache, if any, or to the server. When located, the document is routed on the reverse-path and a copy is placed in each cache along the path. In this paper we consider a cache replacement policy based on Time-to-Lives (TTLs) like in a DNS network. A local TTL is set when the content is first stored at the cache and is renewed every time the cache can satisfy a request for this content (at each hit). The content is removed when the TTL expires. Under the assumption that requests follow a renewal process and the TTLs are exponential random variables, we determine exact formulas for the performance metrics of interest (average cache occupancy, hit and miss probabilities/rates) for some specific architectures (a linear network and a tree network with one root node and $N$ leaf nodes). For more general topologies and general TTL distributions, we propose an approximate solution. Numerical results show the approximations to be accurate, with relative errors smaller than $10^{-3}$ and $10^{-2}$ respectively for exponentially distributed and constant TTLs.Cet article développe des briques de base pour l'évaluation des performances de réseaux orientés contenus. Dans ces réseaux lorsqu'un n{\oe}ud ou cache reçoit une requête pour un contenu qu'il ne posséde pas il la transmet á un ou plusieurs caches de niveau supérieur. Une fois le contenu localisé il est envoyé et stocké á tous les caches qui ont reçu la requête ainsi qu'á l'utilisateur. Dans cet article nous nous intéressons á une politique de gestion des caches qui utilise des temporisateurs (TTL pour {\em Time-to-Live}). A chaque arrivée d'un contenu dans un cache un temporisateur est déclenché. Chaque nouvelle requête pour ce contenu régénére le temporisateur. Dés qu'un temporisateur expire le contenu correspondant est effacé du cache. Nous calculons de maniére exacte différentes mesures de performance (occupation moyenne des caches, probabilité et taux de succés) pour des architectures particuliéres (réseau linéaire, réseau arborescent composé d'une racine et de $N$ feuilles) dans le cas oú les requêtes succcessives aux feuilles forment des processus de renouvellement et oú les temporisateurs sont exponentiellement distribués. Des approximations trés précises (erreurs relatives de l'ordre de $10^{-2}$) sont proposées pour des architectures plus générales et/ou des distributions arbitraires des TTL