We characterize a cache management scheme of a caching system by acaching scheme and acache replacement policy. Acaching schemedecides whether a caching system stores an item in its cache. When a cache is in a full state, acache replacement policy decides which currently cached item is discarded before a new item enters the cache. Hit rate (or hit ratio) is commonly used to evaluate a caching system. It indicates a likelihood
that a caching system can provide the requested items to requesters. The higher a hit rate, the higher performance of a caching system.
5.2.1 Caching Scheme and Cache Replacement Policies
A caching system in each CCN router must keep up with the packet forwarding speed to fully exploit the benefit of CCN. Otherwise, the in-network caches may become a bottleneck in the network. This requirement constrains the caching scheme and cache replacement policy of a CCN router to be noncomplex. We therefore focus on a proba-bilistic caching scheme (P rob(q)) which is simple and scalable to a wide range of network sizes. P rob(q) lets each CCN router randomly cache a fraction of content objects car-ried by arriving Data packets. A caching event happens at caching probability q, where 0< q < 1. P rob(q) is simple to implement compared to other existing caching schemes.
Unlike the popularity-based caching schemes [13, 19] and collaborative caching schemes [20, 21],P rob(q) requires neither the past access information nor a synchronization among routers, and thus becomes a promising candidate of a cache management scheme for content-centric networks.
We consider three simple and fast cache replacement policies in our analysis: Random Replacement (RR), First In First Out (FIFO), and Least Recently Used (LRU).
• RR is the simplest replacement policy, where one of the items currently in the cache is randomly evicted in the uniform distribution whenever a replacement is invoked.
While RR has been rarely used in practice, its simplicity would be beneficial for the implementation of fast CCN routers.
• FIFO replaces the cached item that was first to enter a cache among the items currently in the cache. It has been widely used in data buffer of conventional routers.
• LRU tries to keep recently active items in a cache by discarding the least-recently-used item. It has been least-recently-used by various caching systems such as RAM, web browser and web proxies, and databases. We consider LRU as an upper bound for the complexity of the policies that can be implemented at line speed.
5.2.2 Request Traffic Model
We assume that the requests of items follow the Independent Reference Model (IRM) [99, 47], where a request of item a occurs with probability p(a) and is independent of previous requests for all items. Although the requests from an individual may exhibit a strong temporal locality, the IRM is a reasonable qualitative model in representing accesses to the router which provides services to a large number of users. We also assume Zero Download Delay (ZDD) [47]. Under a ZDD assumption, when a cache miss of an item request occurs at a cache, the requested item is assumed to be instantly downloaded to the cache. In practice, this assumption is possible if every request has been satisfied before the next one is generated.
5.2.3 Ergodicity of Markov Chains
We utilize Markov chains to model the behavior of a caching system. One of the properties of Markov chains can be stated as follows.
Definition 1. [47] Anergodic setof a Markov chain is a set of the states that every state can be reached from every other state through one transition or more, and that cannot be left once it is entered.
A Markov chain is quasi-ergodic if its state space consists of an ergodic set. Otherwise, the Markov chain is non-ergodic. The steady-state of a quasi-ergodic Markov chain does not depend on its initial-state but that of a non-ergodic one does. The ergodicity of the Markov chain of a caching system is subject to its replacement policy. Specifically, both RR and LRU characteristics correspond to quasi-ergodic Markov chains, whereas FIFO yields a non-ergodic one [47]. We will adopt the characteristics of cache replacement policies to establish several important properties of P rob(q).
The notations used in this chapter are summarized by Table 5.1.
Table 5.1: Summary of notations in our analytical model for cache analysis p(a) : probability of requesting itema
q : caching probability
X : set of items available for download C : caching capacity of a CCN router
π(⋆) : stationary distribution of state⋆ in a Markov chain Caching systems with RR
Γ : state space of the Markov chain of a discrete cache with RR A : state of a discrete cache with RR,A∈Γ
Si(A) : set of states that have one item different fromA
γ(a) : set of states that the cache currently stores itema,γ(a)⊂Γ RRR : hit rate of a discrete cache with RR
Ri : theith hop router in the cache hierarchy,i∈ {1,2}
A(i) : state of the cache of routerRi,A(i)∈Γ
∆ : state space of the cache hierarchy with RR
B : state of the cache hierarchy with RR,B = [A(1), A(2)],B∈∆ RHRR : hit rate of the cache hierarchy with RR
Caching systems with either FIFO or LRU Φ : state space of the Markov chain of a discrete cache
Ak : array ofC distinct items representing a state of a discrete cache a(k)i : item at theith position of a cache in stateAk
M(Ak) : set of items when a cache is in stateAk S′(Ak) : set of states where:
• itema(k)1 is not in the cache
• itemsa(k)2 , . . . ,a(k)C are at the 1st, . . . ,(C−1)th positions of the cache
• itemeis at theCth position of the cache, wheree∈X\M(Ak) β(a) : set of states when the cache currently stores itema
RF IF O : hit rate of a discrete cache with FIFO PA : set of permutations ofA
A(i) : cache state of routerRi in the cache hierarchy fori∈ {1,2}
Λ : state space of the Markov chain of the cache hierarchy B : state of the cache hierarchy,B= [A(1),A(2)],B∈Λ RHF IF O : hit rate of the cache hierarchy with FIFO
S′′(Ak) : set of states where:
• the items in the cache are the same as inAk
• the order of these items are particulary different fromAk such that
S′′(Ak) ={Ak′′∈Φ|Ak′′ = [a(k)2 , . . . ,a(k)m ,a(k)1 ,a(k)m+1, . . . ,a(k)C ] for 2≤m≤C}
RLRU : hit rate of a discrete cache with LRU RHLRU : hit rate of the cache hierarchy with LRU ak : arbitrary item inX, wherek∈ {1,2,3}