# Popularity-Aware Closeness Based Caching in NDN Edge Networks
## 3 PaC-Based Caching
### Caching Algorithm  
When an Interest for content \(x_{n}\) arrives at an ingress node \(v_{j}\), the latter updates the corresponding entry in the Popularity Table, checks if the content is popular, and then accesses the CS to find a matching Data packet to send back immediately. If the CS lookup fails, then \(v_{j}\) checks the PIT. If this lookup also fails, then \(v_{j}\) acts differently depending whether the content is popular, i.e., its average request rate is higher than the popularity threshold, or not. If it is not popular, then there is no need to cache it along the path. Therefore, \(v_{j}\) increases by one the hopCount field of the Interest, fills the rate field, in order to allow the next hop updating the Popularity Table, but leaves the pac field to the default zero value, to indicate that the content is not popular. The request will be forwarded towards the origin server according to the standard NDN forwarding fabric. Of course, it may happen that an edge on-path node belonging to multiple delivery paths has cached the content (because it is considered popular by another ingress node) and, therefore, the request can be still satisfied at the edge.  
The returning Data packet, being not popular, should not be cached. However, to make the best of the available storage space, unpopular Data packets can be cached in case the CS is not full, e.g., during the network bootstrap phases.  
Vice versa, if \(x_{n}\) is popular, then \(v_{j}\) updates all the new fields of the Interests, i.e., hopCount, rate, and pac, and transmits the packet to the next-hop, according to the FIB entry.  
The subsequent node \(v_{i}\) receiving the Interest performs a slightly different processing. First, it accesses the information from the Interest header fields and checks if the PopularityTable needs to be updated. In NDN, Interests cannot loop, therefore a newly received Interest carries consistent information in the header fields. The latter can be equal to the previously recorded one, if the request pattern has not changed. The node then performs a lookup in the CS for a match. If the Data packet is found, then \(v_{i}\) computes its PaC metric and compares it with the value in the pac field. If its value is greater, then it overwrites the field and sends the packet back. Vice versa, if its PaC value is smaller, it simply sends the Data packet without altering it. The receiving node with the highest PaC will also cache the Data, thus moving the copy closer to the consumers.  
In case the CS and the consequent PIT matching fail, \(v_{i}\) computes its PaC and, if its value is greater than the current one, it updates the pac, hopCount, and rate fields. Conversely, if the PaC is lower than the current one, it only updates the hopCount and rate fields. It then re-transmits the request according to the FIB and waits for the Data packet.  
When finally receiving the Interest, the origin server, or an intermediate cache, copies the PaC value from Interest to the corresponding field in the Data packet header and transmits the packet. The first node with the corresponding PaC will cache the Data. If the CS if full, an existing item is replaced according to the LRU policy.  
The flowcharts summarizing the Interest processing and Data processing for the PaC-based caching are depicted in Figure 4 and Figure 5, respectively.