# T-Move: A Light-Weight Protocol for Improved QoS in Content-Centric Networks with Producer Mobility
## 4 T-Move
### Trendiness-Based Cache Replacement Policy in T-Move  
Interest forwarding in T-Move is done as in the normal CCN architecture. Routers in T-Move (and CCN) maintain three important data structures--the CS, the PIT and the Forwarding Information Base (FIB). Upon receiving a request, a router (say R1) sends a copy of the data object from the CS or forwards the interest, depending on whether the object is cached at it or not. In the latter case, some other router along the path or the producer itself may reply with the data object. The data object travels along the reverse path (following the PIT entries) and reaches router \(R1\). Following on-path caching, \(R1\) now caches the data object. The important aspect that impacts the system performance here is the cache replacement policy followed by the router. Plain (vanilla) CCN uses FIFO for this. As discussed in Section 3, frequency and popularity-based cache replacement strategies show significant boost in performance for web caching. Web requests follow a Zipf distribution and the Zipf popularity distribution for content class \(k\) when there are \(N\) content classes is defined by \(q_{k}=\frac{c}{k^{\prime}\mathit{al\,pha}}\). The normalized value of \(c\) is \(\sum_{k=1}^{N}\frac{1}{k^{\alpha}}\), where \(\alpha\) is the _skewness of content popularity_. It has been shown that a cache hit ratio of about 70% can be obtained even when 2% to 7% of the web pages are stored for \(\alpha\) ranging between 2 and 1.2 [17]. This is very encouraging for in-network caching of popular content. However, existing off-line or online popularity-based caching schemes for content-centric networks are not suitable to networks with high rates of mobility and data rates (Section 3). In T-Move, we leverage the naming hierarchy of CCN and propose a simple but effective cache replacement policy. This is based on the fact that Zipf's Law can be applied not only to requests for single web documents, but for \"strides of requests\", i.e., a sequence of requests from a client [34]. When hierarchical naming is employed, this means that the demand for data with similar prefixes is higher. For example, if the producer has a web site with pages _a/b/c/p1_, _a/b/c/p2_, _a/b/c/p3_..., once a page is requested, there is a high likelihood of the rest of the pages being requested. If a video named _p/q/r/_, is requested, it may be returned as chunks named _p/q/r/c1_, _p/q/r/c2_.... Our policy uses prefix-matching and frequency for determining content that is currently in _trend_. Each router in T-Move maintains a _Trendiness Table TT_, which has three entries per data object in the router's cache--the name of the data object, the number of times it was requested (its _frequency_, denoted by _f_) and its \"_trendiness_\", denoted by \(t\) as shown in Figure 1. The trendiness of a data object is calculated based on the normalized frequency of access of _similar_ data objects in the name hierarchy using prefix-matching as below:  
\[t_{j}=\frac{\sum_{i=1}^{n}p_{i}*f_{i}}{P_{j}} \tag{1}\]  
where \(n\) is the number of data objects in the cache of the router, \(P\) is the number of prefixes of the \(j\)-th data object, \(p_{i}\) is the number of prefixes that match in the \(j\)-th data object and the \(i\)-th data object and \(f_{i}\) is the frequency of access of the \(i\)-th data object. For example, considering a data object with name _x/y/z/c1_, \(P_{j}\) is 4, as the name has four prefixes. Let a router have three data objects whose names match with this data object in some way. If this router's cache has a data object \(d_{1}\) with frequency of access \(f_{1}\) and name _x/y/z/c1_, the \(p_{1}\) value is 4, as there are four prefixes that match in the names. For a second data object \(d_{2}\) with name _x/y/z/c2_ cached in the router, \(p_{2}\) is 2, as two prefixes match. Let the frequency of \(d_{2}\) be \(f_{2}\). If the router has cached a third data object with name _x/u/v/c1_ and frequency \(f_{3}\) and \(p_{3}\) is 1.