## 3 PF-ClusterCache: Popularity and Freshness-Aware Collaborative Cache Management
Upon the arrival of an Interest packet with a given content name, the SCN node consults its popularity table. If the content name already exists in the table, it increments its popularity count. However, if the name is not there, then the SCN inserts the name in the table. This insertion may first invoke the eviction of the oldest, least frequently used item (the oldest, least popular content name) from the table. The insertion, retrieve, and evict operations could be done in only O(1) time complexity. This can be achieved by maintaining two doubly linked lists: a doubly linked list on the popularity count and another for all name prefixes that have the same popularity count [39]. To keep the popularity table current, it is periodically adjusted and smoothed using the Exponentially Weighted Moving Average (EWMA) algorithm. At the end of each time interval \(i,i=1,2,3,\ldots\), the popularity count of each name prefix \(n\) currently in the table \(PopCount_{i}(n)\) is updated as follows:  
\[PopCount_{i}(n)=\alpha*IR_{i}(n)+(1-\alpha)*PopCount_{i-1}(n)\ \ \ \ \ i\geq 1 \tag{1}\]where \(\alpha\) is a predefined weight parameter \(0\leq\alpha\leq 1\), \(IR_{i}(n)\) is the number of interest packets with name prefix \(n\) received by the SCN during the current time interval \(i\), and \(PopCount_{i-1}(n)\) is the calculated popularity count during the previous time interval. PF-ClusterCache defines a popularity threshold used to decide whether to cache incoming data packets at their designated SCNs. Incoming data content is considered for caching in the SCN content store only if it is valid and its popularity exceeds the defined popularity threshold. Then, the data content is passed to the replacement technique to see whether there is a free place in the CS or content with lower popularity to be evicted. The PF-ClusterCache replacement technique is based on popularity and called the Least Popular First Replacement policy (LPF). LPF ensures that all admitted data content is valid (i.e., fresh), and that only the most popular content occupies the CS of any SCN. Algorithm 1 illustrates the proposed LPF replacement scheme. The incoming popular data content is automatically stored in the CS if there is still space. Otherwise, it is cached only if its popularity count is greater than that of the least popular content currently in the CS. ```
1:\(PT\): Popular Table
2:\(CS\): Content Store
3:\(PIT\): Pending Interest Table
4:\(INPUT\): popular data packet \(pkt\)
5:\(OUTPUT\): Caching decision in CS and Forwarding according to PIT
6:
7:functionCacheData(\(pkt\))
8:\(incoming\)= \(pkt\)
9:if\(pkt\) is valid then
10:if CS is full then
11:\(incoming.pop\)=PT.GetPopCount(\(pkt.nameprefix\))
12:\(lpc=LeastPopularDataCache\)
13:\(lpc.pop\) =PT.GetPopCount(\(pc.nameprefix\))
14:if\(incoming.pop\geq lpc.pop\)then
15: CS.erase(\(lpc\))
16:endif
17:endif
18: CS.insert(\(incoming\))
19: Forward \(pkt\) according to PIT
20:endif
21:endfunction
```  
**Algorithm 1** Least Popular First Replacement Scheme. The system design of PF-ClusterCache necessitates the addition of only one additional field for a second name within the NDN packet format of both Interest and Data. These names shall hereafter be referred to as Pkt.name1 and Pkt.name2. As such, each Interest or Data packet carries both the requested content name and its associated SCN name. The Interest forwarding as well as the Data forwarding are always accomplished using Pkt.name1. No additional field is required in the FIB or in the PIT; namely, the forwarding of Interest and Data packets is done in exactly the same way as specified by the NDN Network Forwarding Daemon (NFD). PF-ClusterCache has no specific requirements for the underlying routing, which could well be the Named Data Link State Routing Protocol (NLSR) or any other routing protocol. As illustrated in Figures 2 and 3, we consider a local cluster composed of six nodes (or routers) \(R1\), \(R2\), \(R3\), \(R4\), \(R5\), and \(R6\).