## 3 PF-ClusterCache: Popularity and Freshness-Aware Collaborative Cache Management  
PF-ClusterCache is a collaborative caching technique to manage and control the caches of a set of nodes as a global distributed storage pool. As such, PF-ClusterCache controls one large global Content Store, which is partitioned among the different nodes of an edge local cluster. In NDN, the size of the Content Store (CS) at each node is very limited compared with the huge amount of available named content (i.e., the catalogue size). The ratio of the cache size over the catalogue size should be within the interval \(\left[10^{-5};10^{-1}\right]\), as suggestedin [37]. PF-ClusterCache then represents a new way to have a much larger CS. This tacitly equates to better performance, as will be explored in the next section. PF-ClusterCache performs the caching of only popular and fresh retrieved content. It forces the caching to be done only at the edge of the network; core routers are then left as a fast switching fabric. Unlike the caching scheme proposed in [23], PF-ClusterCache caches popular content in only one node within the local cluster. A zero redundancy is then achieved within any cluster of nodes. The local caching node of any requested content, hereafter called the Surrogate Caching Node (SCN), is selected according to a hashing function applied on the requested content name. The hash function maps any requested content name to a node ID within the cluster. This node designates the unique SCN where the requested content might be cached or is to be cached if it turns out to be fresh content and of sufficient popularity. The hash function has to evenly distribute the requested content among the different nodes of the cluster. For the sake of this paper, we consider stable clusters where node membership is rarely changed. Clusters could be defined in many different ways. A cluster defines a set of nodes that are interconnected and geographically close to each other. Network service providers, knowing their needs, may define the various clusters in an ad hoc manner according to the requirements of different applications and working environments (e.g., enterprise, video streaming, schools, etc.). The underlying network topology being flat or hierarchical should not hinder the designation of nodes within the same cluster as long as these nodes are interconnected and within the same geographical neighborhood. However, certain network topologies, such as the Transit Stub (TS) topology, may tacitly designate the stubs as clusters. It is worth noting that not all nodes within a cluster should be members of the PF-ClusterCache. We may also adopt a clustering or partitioning algorithm to decide the clusters or the partitions [33; 34; 38]. However, doing so is only profitable for small networks and is not only time-consuming but also does not exclude network core routers to serve as caching nodes. The system design of PF-ClusterCache requires the identification of the current popularity of each piece of requested content. At each SCN node, a popularity table is defined to maintain the current popularity of the requested content within the cluster that is directed to this SCN. Unlike [23], where the table size may grow to very large, inadequate values, PF-ClusterCache uses rather a very efficient popularity table of a very small fixed size. This popularity table is maintained as a Least Frequently Used (LFU) storage, permitting it to insert a content name, retrieve a content name, or evict (delete) a content name. The table can be easily and efficiently implemented using a min heap data structure and a standard collision-free hash map. The min heap is maintained based on the popularity counts of the content names, and the hash table is indexed via the content names. Since all operations on a collision-free hash map are of order O(1), it follows that the time complexity of the insert, retrieve, and evict operations is O(log n), where n is the actual number of stored names capped at the size of the table.