## 3 Model Statement
### Problem Formulation  
Since the NRS enables all cached replicas in the network to provide services to any user, it is important for caching nodes to cache contents properly. The cache hit ratio represents the ability of the cache to serve requests, so it is usually used as an indicator to evaluate caching strategies. In general, a caching strategy with a higher cache hit ratio also results in lower server load and network latency. In this paper, we consider the cache hit ratio as the optimization goal. For a caching node \(i\in V\), \(\lambda_{i}^{in}\) denotes the inflow request rate and \(\lambda_{i}^{out}\) denotes the outflow request rate. We use \(p_{i,k}\) to denote the inflow request probability of content \(k\) in node \(i\) for \(k\in C\), and we can easily find that \(\sum^{k\in C}p_{i,k}=1\). \(x_{i,k}\) represents a boolean variable indicating whether node \(i\) caches content \(k\). \(x_{i,k}\) is 1 if content \(k\) is cached in node \(i\) and 0, otherwise. When contents cached in the node \(i\) serve the corresponding requests, these requests would no longer be forwarded. Thus, the relationship between \(\lambda_{i}^{in}\) and \(\lambda_{i}^{out}\) can be further expressed as \(\lambda_{i}^{out}=\lambda_{i}^{in}\sum^{k\in C}(p_{i,k}(1-x_{i,k}))\). When \(\lambda_{i}^{in}\) equals 0 the cache hit ratio of node \(i\) (denoted as \(h_{i}\)) is obviously 0; when \(\lambda_{i}^{in}\) gets bigger, \(h_{i}\) can be estimated as \(h_{i}=\frac{\lambda_{i}^{in}-\lambda_{i}^{out}}{\lambda_{i}^{in}}=1-\sum^{k \in C}(p_{i,k}(1-x_{i,k}))=\sum^{k\in C}p_{i,k}x_{i,k}\). According to the above analysis, the cache hit ratio maximization problem can be expressed by the following equation:  
Maximize:  
\[h_{total}=\sum^{i\in V}h_{i}=\sum^{i\in V}\sum^{k\in C}p_{i,k}x_{i,k} \tag{1}\]  
Figure 1: An ICN caching scenario with an NRS. subject to:  
\[\sum_{k\in C}^{k\in C}s_{k}x_{j,k}\leq c_{i},i\in V \tag{2}\]  
where \(s_{k}\) is the size of content \(k\) and \(c_{i}\) is the size of cache equipped in node \(i\). In Equation (2), the total space occupied by cached contents from node \(i\) cannot exceed its original cache size. From Equation (1), it is easy to find that more popular contents bring a higher cache hit ratio. To promote the cache hit ratio, an intuitive way is to cache popular contents and replace unpopular contents. Therefore, we need to choose popular contents when making content placement decisions. As for the on-path caching strategy, a key question is how many copies need to be cached along the path. To improve the total cache hit ratio of the network, it is reasonable to place at most one copy at a time. When the popularity of the transferred content is low, it is not worth evicting popular content to cache it; on the contrary, for a particular delivery path, if the downstream node caches the content, requests for the content would not be forwarded upstream. Thus, placing more than one copy would waste the cache space of upstream nodes. In addition, the cache hit ratio of the network is impacted by the request hit location. If the request of a popular content is hit on a Source Server, replacing unpopular content on a caching node with the popular content will directly increase the cache hit ratio. If the request is hit on a caching node, caching the popular content will not increase the total cache hit ratio, as requests for the content are just hit at different caching nodes. However, from the user's perspective, getting content from closer caching nodes reduces more transmission latency. Therefore, the idea of caching popular contents at caching nodes closer to users has been used in many caching strategies, such as in Ref. [13]. Based on this, we aim to design a caching strategy that makes the caching nodes cache more popular contents. Another useful condition is that the NRS can provide information of contents, such as the number of copies in the network (the number of NAs mapped to the content).